Binary Versus Analogue Path Monitoring in IP Networks

Monitoring systems that can detect path outages and periods of degraded performance are important for many distributed applications. Trivial pairwise probing systems do not scale well and cannot be employed in large networks. To build scalable path monitoring systems, two different approaches have been proposed in the literature. The first approach [1], which we call the continuous or analogue model, takes real measurement values and infers the performance metrics of unmeasured paths using traditional (+,) algebra. The second approach [2], which we call the Boolean model, takes binary values from measurements (e.g., whether the delay/loss of an end-to-end path is above a given threshold) and infers the performance quality of unmeasured paths using Boolean algebra. Both approaches exploit the fact that end-to-end paths share network links and hence that the measurements of some paths can be used to infer the performance on others. In this work, we are only in- terested in detecting whether the performance of a path is below an acceptable level or not. We show that when the number of beacons (nodes that can send probes and collect monitoring information) is small, the Boolean model requires fewer direct measurements; whereas for a large number of beacons the continuous model requires fewer direct measurements. When the number of beacons is significantly large, however, there is no difference in terms of the number of paths that we need to measure directly in both models. We verify the results by simulations on inferred network topologies and on real measurement data.