טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentBaron Asaf
SubjectThe Capacity Allocation Paradox
DepartmentDepartment of Electrical Engineering
Supervisors Professor Ran Ginosar
Professor Isaac Keslassy
Full Thesis textFull thesis text - English Version


Abstract

The Capacity Allocation Paradox (CAP) destabilizes a stable finite-buffer network when the capacity of a link is increased. Network designers typically assume that adding capacity can only improve performance. Thus, the principal goal of network design is assumed to be finding the minimum capacity needed for acceptable performance. Beyond that minimum capacity, any capacity should suffice. This paper shows that this assumption is not always true by introducing the CAP. CAP is demonstrated both analytically and using simulations in a basic 2x1 network topology; using simulations, it is shown to exist in more complex networks such as mesh networks. This work shows that it applies to fluid, wormhole and packet-switched networks, and proves that it applies to various scheduling algorithms such as fixed-priority, round-robin and exhaustive round-robin. The capacity regions for these arbitrations 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, this work shows networks with arbitrarily tight link-capacity stability regions, in which any small deviation from an optimal link capacity might make the network unstable, thus making the capacity allocation task extremely difficult when capacity is limited. Finally, this work suggests ways to mitigate CAP, e.g. by using GPS scheduling. It also suggests ways to restore network stability after increasing capacity, for example by choosing the right arbitration policy, or by adding buffer space.

In addition to the CAP, this work discusses the SpaceWire specification, which is used in onboard data-handling networks in spacecrafts. The work presents a benchmark for SpaceWire-based satellites, which will help in measuring and comparing performance, cost, and other attributes of SpaceWire networks. The thesis also demonstrates how the benchmark can be used. In addition, several problems in the network level of the SpaceWire specifications are shown, and optional solutions are presented.