ABSTRACT
Operational networks typically generate massive monitoring data that consist of local (in both space and time) observations of the status of the networks. It is often hypothesized that such data exhibit both spatial and temporal correlation based on the underlying network topology and time of occurrence; identifying such correlation patterns offers valuable insights into global network phenomena (e.g., fault cascading in communication networks). In this paper we introduce a new class of models suitable for learning, indexing, and identifying spatio-temporal patterns in network monitoring data. We exemplify our techniques with the application of fault diagnosis in enterprise networks. We show how it can help network management systems (NMSes) to effciently detect and localize potential faults (e.g., failure of routing protocols or network equipments) by analyzing massive operational event streams (e.g., alerts, alarms, and metrics). We provide results from extensive experimental studies over real network event and topology datasets to explore the effcacy of our solution.
- HP Open View. http://www.openview.hp.com.Google Scholar
- IBM Tivoli Monitoring. http://www01.ibm.com/software/tivoli/products/monitor/.Google Scholar
- H. Akaike. A new look at the statistical model identification. IEEE Trans. Auto. Cont., 19(6), 1974.Google ScholarCross Ref
- D. Banerjee, V. Madduri, and M. Srivatsa. A framework for distributed monitoring and root cause analysis for large ip networks. In SRDS, 2009. Google ScholarDigital Library
- A.-L. Barabási. Linked: The New Science of Networks. Perseus Publishing, 2002.Google ScholarDigital Library
- A.-L. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, 286(5439):509--512, 1999.Google Scholar
- E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. SIAM J. Comput., 32(5), 2003. Google ScholarDigital Library
- I. Cohen, S. Zhang, M. Goldszmidt, J. Symons, T. Kelly, and A. Fox. Capturing, indexing, clustering, and retrieving system history. In SOSP, 2005. Google ScholarDigital Library
- L. Fan, P. Cao, J. Almeida, and A. Broder. Summary cache: A scalable wide-area web cache sharing protocol. In IEEE/ACM Trans. Netw., 1998. Google ScholarDigital Library
- A. Feldmann, O. Maennel, Z. Mao, A. Berger, and B. Maggs. Locating internet routing instabilities. SIGCOMM Comput. Commun. Rev., 34(4), 2004. Google ScholarDigital Library
- A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD, 1984. Google ScholarDigital Library
- Y. Huang, N. Feamster, A. Lakhina, and J. Xu. Diagnosing network disruptions with network-wide analysis. SIGMETRICS Perform. Eval. Rev., 35(1), 2007. Google ScholarDigital Library
- Internet Engineering Task Force. OSPF version 2. http://www.ietf.org/rfc.Google Scholar
- I. Katzela and M. Schwartz. Schemes for fault identification in communication networks. IEEE/ACM Trans. Netw., 3(6), 1995. Google ScholarDigital Library
- A. Lakhina, M. Crovella, and C. Diot. Mining anomalies using traffic feature distributions. SIGCOMM Comput. Commun. Rev., 35(4), 2005. Google ScholarDigital Library
- L. Lewis. A case-based reasoning approach to the resolution of faults in communication networks. In IM, 1993. Google ScholarDigital Library
- J. P. Martin-Flatin, G. Jakobson, and L. Lewis. Event correlation in integrated management: Lessons learned and outlook. J. Netw. Syst. Manage., 15(4):481--502, 2007. Google ScholarDigital Library
- X. Meng, G. Jiang, H. Zhang, H. Chen, and K. Yoshihira. Automatic profiling of network event sequences: algorithm and application. In IEEE INFOCOM, 2008.Google ScholarCross Ref
- Y. Nygate. Event correlation using rule and object based techniques. In IM, 1995. Google ScholarDigital Library
- J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann Publishers Inc., 1988. Google ScholarDigital Library
- T. Wang, M. Srivatsa, D. Agrawal, and L. Liu. Learning, indexing, and diagnosing network faults. In KDD, 2009. Google ScholarDigital Library
- J. Wu, Z. Mao, J. Rexford, and J. Wang. Finding a needle in a haystack: pinpointing significant BGP routing changes in an IP network. In NSDI, 2005. Google ScholarDigital Library
- P. Wu, R. Bhatnagar, L. Epshtein, M. Bhandaru, and S. Zhongwen. Alarm correlation engine. In NOMS, 1998.Google Scholar
- K. Yamasaki, K. Matia, S. V. Buldyrev, D. Fu, F. Pammolli, M. Riccaboni, and H. E. Stanley. Preferential attachment and growth dynamics in complex systems. Phys. Rev. E, 74(3), 2006.Google ScholarCross Ref
- S. Yemini, S. Kliger, E. Mozes, Y. Yemini, and D. Ohsie. High speed and robust event correlation. Communications Magazine, IEEE, 34(5), 1996. Google ScholarDigital Library
- H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman. Sybilguard: defending against sybil attacks via social networks. In SIGCOMM, 2006. Google ScholarDigital Library
- J. Zhang, J. Rexford, and J. Feigenbaum. Learning-based anomaly detection in BGP updates. In MineNet, 2005. Google ScholarDigital Library
Index Terms
- Spatio-temporal patterns in network events
Recommendations
Spatio-temporal clustering of road network data
AICI'10: Proceedings of the 2010 international conference on Artificial intelligence and computational intelligence: Part IThis paper addresses spatio-temporal clustering of network data where the geometry and structure of the network is assumed to be static but heterogeneous due to the density of links varies cross the network. Road network, telecommunication network and ...
Temporal Changes in Connection Patterns of an Email-Based Social Network
WI-IAT '08: Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Volume 03Network motifs are small subgraphs that reflect local network topology and were shown to be useful for creating profiles that reveal several properties of the network. Analysis of three-node motifs (triads) was used in this paper to track the temporal ...
Explaining social events through community evolution on temporal networks
Highlights- Establish a connection between the evolution of social networks and real social events.
AbstractThe social network is closely related to people’s lives. And social events are the products of the human subjective initiative during the evolution of networks. Therefore, there is a close correlation between social events and network ...
Comments