Computer Science Department
School of Computer Science, Carnegie Mellon University


Locating Internet Bottlenecks:
Algorithms, Measurements, and Implications

Ningning Hu, Li Erran Li*, Zhuoqing Morley Mao**
Peter Steenkiste, Jia Wang***

April 2004

Keywords: Network measurements, bottleneck location, active probing, packet train, congestion

The ability to locate network bottlenecks along end-to-end paths on the Internet is of great interest to both network operators and researchers. For example, knowing where bottleneck links are, network operators can apply traffic engineering either at the interdomain or intradomain level to improve routing. Existing bandwidth measurement tools fail to identify the location of bottleneck links. In addition, they often require access to both end points and generate huge amount of probing packets. These drawbacks make them impractical. In this paper, we present a novel light-weight, single-end active probing tool -- Pathneck -- based a novel probing technique called Recursive Packet Train (RPT), which allows end users to efficiently and accurately locate bottleneck points to destinations on the Internet. We evaluate Pathneck using trace-driven emulations and wide area Internet experiments. In addition, we conduct extensive measurements on the Internet among carefully selected, geographically diverse probing sources and destinations to study Internet bottleneck properties. We find that Pathneck can successfully detect bottlenecks for over 70\% of paths, and most of the bottlenecks are fairly stable. We also report our success on bottleneck inference, using multihoming and overlay routing to avoid bottlenecks based on the bottleneck link location and bandwidth estimation provided by Pathneck.

30 pages

*Bell Laboratories
**Univeristy of Michigan
***AT&T Labs - Research

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by