Locating Internet bottlenecks : algorithms, measurements, and implications

Abstract: "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 bandwith measurement tools fail to identify the location of bottleneck links. In addition, they often require access to both end points and generate huge amount [sic] of probing packets. These drawbacks make them impractical. In this paper, we present a novel light-weight, single-end active probing tool -- Pathneck -- based [sic] 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."