Analyzing Nonblocking Switching Networks Using Linear Programming (Duality)

Free registration required

Executive Summary

The main task in analyzing a switching network design (including circuit-, multirate-, and photonic-switching) is to determine the minimum number of some switching components so that the design is non-blocking in some sense (e.g., strictor wide-sense). The paper shows that, in many cases, this task can be accomplished with a simple two-step strategy: formulate a linear program whose optimum value is a bound for the minimum number one is seeking, and specify a solution to the dual program, whose objective value by weak duality immediately yields a sufficient condition for the design to be non-blocking. The paper illustrates this technique through a variety of examples, ranging from circuit to multirate to photonic switching, from unicast to f-cast and multicast, and from strict-to wide-sense non-blocking.

  • Format: PDF
  • Size: 207.4 KB