Extending the birkhoff-von neumann switching strategy for multicast - On the use of optical splitting in switches

The Birkhoff-von Neumann (BVN) strategy for single-stage input-queued crossbar switches does not support multicast, as it considers only permutation-based switch configurations. This paper extends the BVN strategy to multicast switching, where an input can simultaneously transmit to multiple outputs. Knowledge of the average rates of flows is used to compute an offline schedule. We begin by considering a system in which the fanout of each flow is split in a predecided manner. We call this static splitting (as opposed to dynamic splitting where no such constraint is imposed), and we study the rate region of the switch under this restriction. We provide a graph-theoretic formulation of the rate region. Such a formulation enables the use of results and algorithms from graph-theory literature, in the context of switch scheduling. Specifically, we show that the multicast rate region with no fanout-splitting is the stable set polytope of the traffic pattern's `' conflict graph `'. This result extends to the static splitting case as well. We construct examples to show that there is no single dominant static splitting strategy in terms of rate region. We show that deciding achievability of a given set of rates is NP-hard for static and dynamic splitting. We also show that, computing the offline schedule with static splitting reduces to fractional weighted graph coloring, which takes polynomial time for perfect graphs. We present several types of traffic patterns whose conflict graphs are perfect. For the more general case of arbitrary traffic patterns, we show that for K x N switches, where K is a constant with respect to N, fractional weighted coloring of the conflict graph can be performed in time, polynomial in the number of flows. Our study has implications for optical networks in the context of the time-domain wavelength interleaved network (TWIN) approach that was introduced by Ross et al. Here the entire optical network is viewed as a single switch, with buffering at the edges and time-division multiplexing of optical circuits in the core. This approach may obviate the need for optical packet header recognition. Inherently, the optical domain enables inputs to transmit to many outputs at once. The static splitting restriction is justified from a practical perspective, as it does not require the network to be reconfigured as often as dynamic splitting does. In addition, it also simplifies the queue management for multicast. We propose an online algorithm based on our conflict graph approach. Such algorithms do require header recognition. In optical networks, optimal algorithms based on matchings and extensions thereof may be incompatible with the speed requirements of optical switches. Thus, we envisage simplified algorithms with reduced complexity. We simulate our algorithm along with two other online algorithms - one based on a modification of ESLIP, and the other on a copy-and-use-i-SLIP strategy. Using these simulations, we demonstrate that no static splitting strategy is dominant, even in an online setting in a bigger switch.