Internet service providers (ISP) and administrators of Local Area Networks (LAN) aim to provide a certain level of service to end-users. However, network elements such as routers and switches may malfunction, resulting in abnormal communication delays. When such delays are observed, network administrators try to diagnose which network elements cause the abnormal delays. While most common techniques use additional measurements to identify the faulty device, we propose a non-intrusive model-based approach. The first approach translates classical MBD terms to this problem and shows a complete and sound solution. The second approach uses linear programming to produce a single minimum cardinality diagnosis in polynomial time. Both approaches are analyzed and evaluated empirically using the standard NS2 network simulator, and are able to find diagnoses or the minimal cardinality diagnosis in less than half a second for network models with up to 1,000 nodes.
How to Cite
Model-based diagnosis, communication network
(Barabasi and Albert, 1999) A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509–512, 1999.
(Fijany and Vatan, 2005) A. Fijany and F. Vatan. New high-performance algorithmic solution for diagnosis problem. In IEEE Aerospace Conference (IEEEAC05), pages 3863 – 3873, 2005.
(Garey and Johnson, 1979) M. R. Garey and D. S. Johnson.
Computers and Intractability : A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, January 1979.
(Kandulaetal.,2009) Srikanth Kandula, Ratul Mahajan, Patrick Verkaik, Sharad Agarwal, Jitendra Padhye, and Paramvir Bahl. Detailed diagnosis in enterprise networks. SIGCOMM Comput. Commun. Rev., 39(4):243– 254, 2009.
(McCanne et al., 2001) Steven McCanne, Sally Floyd, and Kevin Fall. ns2 (network simulator 2), 2001.
(SandroT.FontaniniandMaragon,2002) Volnys Bernal Sandro T. Fontanini, Jacques Wainer and Silvio Maragon. Model based diagnosis in lans. In IEEE Workshop on IP Operations and Management (IPOM), 2002.
(Shavitt and Shir, 2005) Yuval Shavitt and Eran Dimes: let the internet measure itself. Computer Communication Review, 35(5):71–74, 2005.
(Wei et al., 2003) Wei Wei, Bing Wang, Don Towsley, and Jim Kurose. Model-based identification of dominant congested links. In Proceedings of ACM Internet Measurement Conference, 2003.
The Prognostic and Health Management Society advocates open-access to scientific data and uses a Creative Commons license for publishing and distributing any papers. A Creative Commons license does not relinquish the author’s copyright; rather it allows them to share some of their rights with any member of the public under certain conditions whilst enjoying full legal protection. By submitting an article to the International Conference of the Prognostics and Health Management Society, the authors agree to be bound by the associated terms and conditions including the following:
As the author, you retain the copyright to your Work. By submitting your Work, you are granting anybody the right to copy, distribute and transmit your Work and to adapt your Work with proper attribution under the terms of the Creative Commons Attribution 3.0 United States license. You assign rights to the Prognostics and Health Management Society to publish and disseminate your Work through electronic and print media if it is accepted for publication. A license note citing the Creative Commons Attribution 3.0 United States License as shown below needs to be placed in the footnote on the first page of the article.
First Author et al. This is an open-access article distributed under the terms of the Creative Commons Attribution 3.0 United States License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.