Locating Internet Bottlenecks: Algorithms, Measurements, and Implications

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 bottle-neck 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.