Interface 2003

A Solution to the Bandwidth Allocation Problem for the Internet
William S. Cleveland, (Bell Labs),,
Jin Cao, (Bell Labs),, and
Don X. Sun, (Deephaven Capital Management),


The most basic problem of Internet traffic engineering is determining the bandwidth (bits/sec), or link speed, required to carry a traffic load (bits/sec) offered to a single link and satisfy specified quality-of-service requirements for the traffic. The offered load is packets of varying sizes arriving for transmission on the link. Packets can queue up and are dropped if the queue size (in bits) is bigger than the buffer size (in bits) in which they are stored. For today's predominant traffic on the Internet, best-effort traffic, the applicable quality metrics are the queueing delay and the packet loss.

This bandwidth allocation problem, a critical issue for efficient engineering of the Internet, has received much attention in the network research literature. While important insight has been gained, the problem, in practical terms, has resisted solution due to a lack of comprehensive, valid statistical models for the packet arrivals and sizes. The required bandwidth depends on the queue-length process which, in turn, depends heavily on the statistical properties of the arrivals and sizes.

Equipped with recently developed statistical models for arrivals and sizes, we develop a solution by finding the bandwidth, b, required for a traffic load, t, subject to the requirements of a maximum queueing delay, d (sec), and a packet loss (percent of packets), w. The solution, a statistical model for b as a function of t, d, and w, is quite simple and employs some elements of the classical Erlang queueing delay formula for Poisson arrivals and exponential service times.

Take me back to the main conference page.