MBD Techniques for Internet Delay Diagnosis



Roni Stern Meir Kalech


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

Stern, R. ., & Kalech, M. (2010). MBD Techniques for Internet Delay Diagnosis. Annual Conference of the PHM Society, 2(2). https://doi.org/10.36001/phmconf.2010.v2i1.1929
Abstract 96 | PDF Downloads 54



Model-based diagnosis, communication network

(Bahl et al., 2007) Victor Bahl, Ranveer Ch, Albert Green- berg, Srikanth K, David A. Maltz, and Ming Zhang. To- wards highly reliable enterprise network services via inference of multi-level dependencies. In SIGCOMM, pages 13–24, 2007.

(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.
Poster Presentations