Check out the new USENIX Web site. next up previous
Next: OverQoS Cost Up: Evaluation Previous: Statistical Loss Guarantees


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$).
\includegraphics[width=2.2in,height=1.6in]{figures/guarbw.eps}
(a)
\includegraphics[width=2.2in,height=1.6in]{figures/cminvscavg.eps}
(b)
\includegraphics[width=2.2in,height=1.6in]{figures/cminstab.eps}
(c)

Figure 9: Variation of $ \frac {c_{min}}{c_{avg}}$ as a function of $ c_{avg}$
\begin{figure}\centering {
\small {
\begin{tabular}{\vert l\vert l\vert l\vert}
...
...line
$>1600$\ Kbps & 0.49 & $0.04-1.0$\ \\
\hline
\end{tabular}}}\end{figure}

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.


next up previous
Next: OverQoS Cost Up: Evaluation Previous: Statistical Loss Guarantees
116 2004-02-12