Unfairness Caused by Quadratic Backoff in a Packet-Radio Network
Abstract
This note contains the performance analysis of a prototype packet-radio pacing algorithm designed to prevent congestion by throttling traffic sources. In the pacing algorithm we analyze, each packet radio measures data-packet forwarding times on a neighbor-by-neighbor basis, and scales them to compute a lower bound on packet inter-transmission times, known as a pacing delay. The scale factor is chosen to prevent packet radios from sending data packets to their neighbors faster than they can forward them. In summary, the pacing algorithm applies flow control to prevent congestion. The prototype algorithm differentiates between packet transmissions at the head of a route and packet transmissions along a route. The pacing delays for the former case are scaled quadratically whereas the pacing delays for the latter case are scaled linearly. The objective is to prevent congestion by metering data packets into the network slower than they can traverse it. This source-throttling technique is called quadratic backoff. We derive a mathematical model for pacing-delay computations in a packet-radio network that demonstrates quadratic backoff introduces unfair stable equilibrium points. In other words, quadratic backoff causes a persistent situation to occur in which some routes get more bandwidth that others.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 19, 1989
- Accession Number
- ADA219635
Entities
People
- Melisse Leib
Organizations
- BBN Technologies