On the impact of routing matrix inconsistencies on statistical path monitoring in overlay networks
Overlay networks can be used to find working paths when direct underlay paths are anomalously slow, e.g. because of a network fault. Overlay paths should not use links that are involved in a fault, so choosing which overlay path to use often requires path monitoring, which introduces an overhead. By using a routing matrix 'M' to define which links are used in each path, and sorting the matrix according to the degree of independence of paths, we can choose a reduced set of paths to monitor, and so reduce overheads. The state of the unmonitored paths are then predicted using statistical estimation techniques based on information inferred from the monitored paths. However, such methods assume knowledge of routing matrix. We investigate the impact on such methods when knowledge of the routing matrix is only approximate, e.g. as obtained using simple tools like traceroute which have been previously blamed for incorrect mapping of the topology of real world IP networks. This paper investigates the impact of routing matrix errors on such statistical path estimation approaches. We show that mitigation or removal of such errors leads to improved path metric prediction and anomaly detection.