Accurate estimates of the available bandwidth on a path through a network can lead to significant improvements in the performance of routing and congestion-control procedures, and aid overlay applications. Unfortunately, generating an accurate estimate involves saturating the path for a short period of time with a few high-rate packet trains. If this is done rarely, then the overhead is acceptable, but if many paths in a subnetwork are being monitored simultaneously, then due to shared links, the additional load can become unacceptable and the measurement process itself can significantly bias the estimates. In this talk, I will describe a distributed algorithm for simultaneously estimating the bandwidth of multiple paths through a network. The procedure exploits the fact that each packet train provides information not only about the path it traverses, but also about any path that shares a link with the monitored path. We form a graphical model to capture these relationships and propagate the measurement information using loopy belief propagation. In addition, we employ an active learning algorithm to decide which path to measure and at what rate to probe in order to maximize the information provided by the probe. Simulations and preliminary PlanetLab experiments indicate that this process can dramatically reduce the number of probes required to generate acceptably accurate available bandwidth estimates.
Copyright. All Rights Reserved.