Recent advances in Internet measurement tools have made it possible to locate bottleneck links that constrain the available bandwidth of Internet paths. In this paper, we provide a detailed study of Internet path bottlenecks. We focus on the following four aspects: the persistence of bottleneck location, the sharing of bottlenecks among destination clusters, the packet loss and queueing delay of bottleneck links, and the relationship with router and link properties, including router CPU load, router memory load, link traffic load, and link capacity. We find that 20% - 30% of the source-destination pairs in our measurement have a persistent bottleneck; fewer than 10% of the destinations in a prefix cluster share a bottleneck more than half of the time; 60% of the bottlenecks on lossy paths can be correlated with a loss point no more than 2 hops away; and bottlenecks can be clearly correlated with link load, while presenting no strong relationship with link capacity, router CPU and memory load.

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 tools either fail to identify the location of bottlenecks, or generate a large amount of probing packets. In addition, they often require access to both end points. In this paper we present Pathneck, a tool that allows end users to efficiently and accurately locate the bottleneck link on an Internet path. Pathneck is based on a novel probing technique called Recursive Packet Train (RPT) and does not require access to the destination. We evaluate Pathneck using wide area Internet experiments and trace-driven emulation. In addition, we present the results of an extensive study on bottlenecks in the Internet using carefully selected, geographically diverse probing sources and destinations. We found that Pathneck can successfully detect bottlenecks for almost 80% of the Internet paths we probed. We also report our success in using the bottleneck location and bandwidth bounds provided by Pathneck to infer bottlenecks and to avoid bottlenecks in multihoming and overlay routing.

TCP slow start exponentially increases the congestion window size to detect the proper congestion window for a network path. This often results in significant packet loss, while breaking off slow start using a limited slow start threshold may lead to an overly conservative congestion window size. This problem is especially severe in high speed networks. In this paper we present a new TCP startup algorithm, called paced start, that incorporates an available bandwidth probing technique into the TCP startup algorithm. Paced start is based on the observation that when we view the TCP startup sequence as a sequence of packet trains, the difference between the data packet spacing and the acknowledgement spacing can yield valuable information about the available bandwidth. Slow start ignores this information, while paced start uses it to quickly estimate the proper congestion window for the path. For most flows. Paced Start transitions into congestion avoidance mode faster than Slow Start, has a significantly lower packet loss rate, and avoids the timeout that is often associated with slow start. This paper describes the paced start algorithm and uses simulation and real system experiments to characterize its properties.

The packet pair mechanism has been shown to be a reliable method to measure the bottleneck link capacity on a network path, but its use for measuring available bandwidth is more challenging. In this paper, we use modeling, measurements, and simulations to better characterize the interaction between probing packets and the competing network traffic. We first construct a simple model to understand how competing traffic changes the probing packet gap for a single-hop network. The gap model shows that the initial probing gap is a critical parameter when using packet pairs to estimate available bandwidth. Based on this insight, we present two available bandwidth measurement techniques, the initial gap increasing (IGI) method and the packet transmission rate (PTR) method. We use extensive Internet measurements to show that these techniques estimate available bandwidth faster than existing techniques such as Pathload, with comparable accuracy. Finally, using both Internet measurements and ns simulations, we explore how the measurement accuracy of active probing is affected by factors such as the probing packet size, the length of probing packet train, and the competing traffic on links other than the tight link.

Grid applications must increasingly self-adapt dynamically to changing environments. In most cases, adaptation has been implemented in an ad hoc fashion, on a per-application basis. This paper describes work which generalizes adaptation so that it can be used across applications by providing an adaptation framework. This framework uses a software architectural model of the system to analyze whether the application requires adaptation, and allows repairs to be written in the context of the architectural model and propagated to the running system. In this paper, we exemplify our framework by applying it to the domain of load-balancing a client-server system. We report on an experiment conducted using our framework, which illustrates that this approach maintains architectural requirements.