Travel Tech

The Capacity Allocation Paradox

Free registration required

Executive Summary

The Capacity Allocation Paradox (CAP) destabilizes a stable small-buffer network when a link capacity is increased. CAP is demonstrated in a basic 2x1 network topology. The authors show that it applies to fluid, wormhole and packet-switched networks, and prove that it applies to various scheduling algorithms such as fixed-priority, round-robin and exhaustive round-robin. Their capacity regions are modeled and surprising phenomena are described. For instance, once increasing a link capacity destabilizes a stable network, increasing it further to infinity might never restore stability. Further, they exhibit networks with arbitrarily tight link capacity stability regions, in which any small deviation from an optimal link capacity might make the network unstable. Finally, they suggest ways to mitigate CAP, e.g. by using GPS scheduling.

  • Format: PDF
  • Size: 573.7 KB