Learning, indexing, and diagnosing network faults

ABSTRACT

Modern communication networks generate massive volume of operational event data, e.g., alarm, alert, and metrics, which can be used by a network management system (NMS) to diagnose potential faults. In this work, we introduce a new class of indexable fault signatures that encode temporal evolution of events generated by a network fault as well as topological relationships among the nodes where these events occur. We present an efficient learning algorithm to extract such fault signatures from noisy historical event data, and with the help of novel space-time indexing structures, we show how to perform efficient, online signature matching. We provide results from extensive experimental studies to explore the efficacy of our approach and point out potential applications of such signatures for many different types of networks including social and information networks.

REFERENCES

• 1: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, ACM SIGMOD Record, v.18 n.2, p.253-262, June 1989
• 2: Yanif Ahmad , Suman Nath, COLR-Tree: Communication-Efficient Spatio-Temporal Indexing for a Sensor Data Web Portal, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.784-793, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497487]
• 3: ]]H. Akaike. A new look at the statistical model identification. IEEE Trans. Auto. Cont., 19(6), 1974.
• 4: ]]A.-L. Barabási. Linked: The New Science of Networks. Perseus Publishing, 2002.
• 5: Edith Cohen , Eran Halperin , Haim Kaplan , Uri Zwick, Reachability and Distance Queries via 2-Hop Labels, SIAM Journal on Computing, v.32 n.5, p.1338-1355, 2003 [doi>10.1137/S0097539702403098]
• 6: Ira Cohen , Steve Zhang , Moises Goldszmidt , Julie Symons , Terence Kelly , Armando Fox, Capturing, indexing, clustering, and retrieving system history, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 7: ]]A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the em algorithm. J. Royal Stat. Soci. B, 39(1), 1977.
• 8: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 9: Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 10: ]]I. E. T. Force. OSPF version 2. http://www.ietf.org/rfc.
• 11: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, ACM SIGMOD Record, v.14 n.2, June 1984
• 12: Yiyi Huang , Nick Feamster , Anukool Lakhina , Jim (Jun) Xu, Diagnosing network disruptions with network-wide analysis, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
• 13: Irene Katzela , Mischa Schwartz, Schemes for fault identification in communication networks, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.753-764, Dec. 1995 [doi>10.1109/90.477721]
• 14: Anukool Lakhina , Mark Crovella , Christophe Diot, Mining anomalies using traffic feature distributions, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
• 15: Lundy M. Lewis, A Case-Based Reasoning Approach to the Resolution of Faults in Communication Networks, Proceedings of the IFIP TC6/WG6.6 Third International Symposium on Integrated Network Management with participation of the IEEE Communications Society CNOM and with support from the Institute for Educational Services, p.671-682, April 18-23, 1993
• 16: ]]X. Meng, G. Jiang, H. Zhang, H. Chen, and K. Yoshihira. Automatic profiling of network event sequences: algorithm and application. In IEEE INFOCOM, 2008.
• 17: Y. A. Nygate, Event correlation using rule and object based techniques, Proceedings of the fourth international symposium on Integrated network management IV, p.278-289, January 1995
• 18: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 19: ]]F. Salfner. Event-based failure prediction: an extended hidden markov model approach. Department of Computer Science, Humboldt-Universitat zu Berlin, Germany, 2008.
• 20: ]]M. Steinder and A. Sethi. A survey of fault localization techniques in computer networks. Sci. Comput. Prog., 53, 2004.
• 21: ]]P. Wu, R. Bhatnagar, L. Epshtein, M. Bhandaru, and S. Zhongwen. Alarm correlation engine. In NOMS, 1998.
• 22: ]]S. Yemini, S. Kliger, E. Mozes, Y. Yemini, and D. Ohsie. High speed and robust event correlation. Communications Magazine, IEEE, 34(5), 1996.
• 23: Chun Yuan , Ni Lao , Ji-Rong Wen , Jiwei Li , Zheng Zhang , Yi-Min Wang , Wei-Ying Ma, Automated known problem diagnosis with event traces, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 24: Jian Zhang , Jennifer Rexford , Joan Feigenbaum, Learning-based anomaly detection in BGP updates, Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080173.1080189]
• 25: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation

Keywords:
fault signature, network topology, online diagnosis