Capacity and token rate estimation for networks with token bucket shapers

Many cloud computing applications are bandwidth-intensive, and thus the cloud bandwidth information is important for their tenants to manage and troubleshoot the application performance. However, current bandwidth estimation methods face great challenges with clouds. One important reason is that traffic shapers such as token bucket shapers are widely used as a building block for rate limiting in clouds. In this paper, we propose two methods called NarrowLinkCapacity and NarrowTokenRate to actively estimate the capacity and token rate, respectively, of a path in a network with potentially multiple token bucket shapers. The capacity of a path is the slowest link capacity among all links on the path, and the token rate of a path is the slowest token rate among all token bucket shapers in the path. They are two important path properties determining the average rate of a train of packets on a path. Our evaluation results show that our methods work well under a variety of network conditions.