## Abstract

Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with n end hosts, existing systems either require O(n^{2}) measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Unlike other network tomography systems, we characterize end-to-end losses (this extends to any additive metrics, including latency) rather than individual link losses. We find a minimal basis set of k linearly independent paths that can fully describe all the O(n^{2}) paths. We selectively monitor and measure the loss rates of these paths, then apply them to estimate the loss rates of all other paths. By extensively studying synthetic and real topologies, we find that for reasonably large n (e.g., 100), k is only in the range of O(n log n). This is explained by the moderately hierarchical nature of Internet routing. Our scheme only assumes the knowledge of underlying IP topology, and any link can become lossy or return to normal. In addition, our technique is tolerant to topology measurement inaccuracies, and is adaptive to topology changes.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 2003 ACM SIGCOMM Internet Measurement Conference, IMC 2003 |

Pages | 216-221 |

Number of pages | 6 |

State | Published - Dec 1 2003 |

Event | Proceedings of the 2003 ACM SIGCOMM Internet Measurement Conference, IMC 2003 - Miami Beach, FL, United States Duration: Oct 27 2003 → Oct 29 2003 |

### Other

Other | Proceedings of the 2003 ACM SIGCOMM Internet Measurement Conference, IMC 2003 |
---|---|

Country/Territory | United States |

City | Miami Beach, FL |

Period | 10/27/03 → 10/29/03 |

## Keywords

- Network measurement and monitoring
- Network tomography
- Numerical linear algebra
- Overlay networks

## ASJC Scopus subject areas

- Engineering(all)