Statistical Bandwidth Guarantees

In this section, we answer the question: What bandwidth guarantees are realizable on a virtual link?

Recall that the statistical bandwidth guarantee achievable along a virtual link is given by $c_{min}$ such that $P(c{<}c_{min}) = u$, where $c$ represents the instantaneous bandwidth along the virtual link, and $u$ represents the probability with which the guarantee is not met. The Rate Estimator module updates $c$ once every window of packets ($O$(RTT) sec) based on the feedback information received from the next OverQoS hop.

Figure 8: (a) Cumulative distribution of the bandwidth guarantee $c_{min}$ across $100$ separate measurements over $83$ unique overlay links measured across 7 different days from Jan14th - Jan28th. For each run along a single overlay link, we generated between 100,000 - 300,000 packets. All measurements are taken on weak-days (many of them during working hours). (b) Distribution of the fraction $c_{min}/c_{avg}$ across all the links. (c) Variation of $c_{min}$ across 4 different virtual links between Europe and North America. $c_{min}$ is measured as an on-line estimate over a maximum previous history of $5$ minutes (time to collect $20/u$ samples for $u=P(c<c_{min})=0.01$).

(a)

(b)

(c)

Figure 9: Variation of $\frac {c_{min}}{c_{avg}}$ as a function of $c_{avg}$

Across the $171$ pairs of nodes between the 19 end-hosts in our testbed, we monitored $83$ unique virtual links over a period of 7 working days. Figures 8(a) and (b) show the distribution of $c_{min}$ for $u=0.01$ and $u=0.005$. We make two observations. First, the value of $c_{min}$ is greater than $100$ Kbps for more than $80\%$ of the links. $20\%$ of the links are predominantly connected to broadband hosts. Second, in many cases, $c_{min}$ is at least $25\%$ of the average throughput along the virtual link. In specific cases, $c_{min}$ is as large as $90\%$ of the average throughput. The median value of $c_{min}/c_{avg}$ is $0.4$ and $0.35$ for $u=0.01$ and $u=0.005$ respectively. Figure 9 shows the variation of $c_{min}/c_{avg}$ as a function of $c_{avg}$. As $c_{avg}$ increases, we notice that the maximum value of $c_{min}/c_{avg}$ increases while the minimum value decreases. The minimum decreases because we notice self-induced losses across some of the links thereby causing MulTCP to drastically reduce its sending rate and thereby reducing $c_{min}$.

Stability of $c_{min}$: If the underlying distribution of $c$ is stable, the estimated value of $c_{min}$ will roughly be a constant. However under dynamic conditions, we need to continuously re-estimate $c_{min}$ and flows need to renegotiate their bandwidth reservations. For a given value of $u$, we estimate $c_{min}$ using $O(1/u)$ samples of $c$. As an example, given $RTT=100$ msec and $u=0.01$, we can calculate $c_{min}$ based on the last $20/u$ samples (representing a history of 200 seconds). In this scenario, flows renegotiate their bandwidth requirements every few minutes.

Figure 8(c) shows the variation as a function of time across four separate virtual links from Europe to North America. We make two observations: First, the value of $c_{min}$ is very stable compared to variations in the available bandwidth, $c$. Across these links, $c_{min}$ does not deviate more than $10\%$ around its mean value. Second, an on-line algorithm for estimating $c_{min}$ based on past history is a reasonable approach. While we set $P(c<c_{min})$ to be $1\%$, the actual value of $c$ is less than the estimated $c_{min}$ in no more than $1.3\%$ of the cases across all four virtual links.