Analyzing Nonblocking Switching Networks using Linear Programming (Duality)

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., strict- or wide-sense). We show that, in many cases, this task can be...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2012-04
Main Authors: Ngo, Hung Q, Atri Rudra, Le, Anh N, Nguyen, Thanh-Nhan
Format: Article
Language:English
Subjects:
Algorithms
Circuit design
Coloring
Linear programming
Multicast
Optical switching
Photonics
Switching theory
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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., strict- or wide-sense). We show that, in many cases, this task can be accomplished with a simple two-step strategy: (1) formulate a linear program whose optimum value is a bound for the minimum number we are seeking, and (2) 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. We illustrate 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. The switching architectures in the examples are of Clos-type and Banyan-type, which are the two most popular architectural choices for designing non-blocking switching networks. To prove the result in the multirate Clos network case, we formulate a new problem called {\sc dynamic weighted edge coloring} which generalizes the {\sc dynamic bin packing} problem. We then design an algorithm with competitive ratio 5.6355 for the problem. The algorithm is analyzed using the linear programming technique. A new upper-bound for multirate wide-sense non-blocking Clos networks follow, improving upon a decade-old bound on the same problem.
ISSN:2331-8422