MBD Techniques for Internet Delay Diagnosis

Roni Stern and Meir Kalech
Submission Type: 
Full Paper
phmc_10_120.pdf1.02 MBSeptember 16, 2010 - 1:48am

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 model-based diagnosis terms to this problem and shows a complete and sound solution. % is achieved by pruning irrelevant network components.
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.

Publication Control Number: 
Submission Keywords: 
Model-based diagnosis
communication network
Submitted by: 

follow us

PHM Society on Facebook Follow PHM Society on Twitter PHM Society on LinkedIn PHM Society RSS News Feed