Extending the Birkhoff-von Neumann switching strategy to multicast switching

The Birkhoff-von Neumann (BVN) strategy for offline switching does not support multicast, as it considers only permutation-based switch configurations. This thesis extends the BVN strategy to multicast switching. Using a graph theoretic model, we show that the capacity region for a traffic pattern is precisely the stable set polytope of the pattern's "conflict graph", in the no-fanout-splitting case. We construct examples to show that, if dynamic fanout splitting is excluded, there is no clear winner in terms of rate region among various fanout splitting strategies. The problem of deciding whether a given set of rates is achievable in a multicast switch is also addressed. We show that, in general, the problem is equivalent to the membership problem for the stable set polytope of a graph, and is therefore NP-hard. We also prove that the problem is NP-hard for the case that splitting of the set of destinations, or fanout, is allowed. However, in the no-splitting case, it is polynomial time solvable when the number of multicast flows in the N x N switch is O(logN). The algorithm naturally leads to a schedule to serve the flows in a stable manner, if the rates are achievable. For an arbitrary number of multicasts, we show that, computing the offline schedule is equivalent to fractional weighted graph coloring which takes polynomial time for perfect graphs. We present several types of traffic patterns whose conflict graphs are perfect. [18] proposed a simple online algorithm called i-SLIP based on parallel iterative matching, for online unicast scheduling. We propose an online algorithm for multicast, based on i-SLIP and the conflict graph idea, and compare them with ESLIP([19]) and the copy-and- use-i-SLIP strategy, through simulations.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2005

Author dc:creator

• Sundararajan, Jay Kumar, 1982-

Advisor dc:contributor.advisor

• Muriel Médard and Supratim Deb.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/30185

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/30185