The Capacity Allocation Paradox

The Capacity Allocation Paradox (CAP) destabilizes a stable small-buffer network when a link capacity is increased. CAP is demonstrated in a basic 2 times 1 network topology. We 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, we 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, we suggest ways to mitigate CAP, e.g. by using GPS scheduling.