Switch Scheduling Via Randomized Edge Coloring

Date Added: Jan 2010
Format: PDF

The essence of an Internet router is an n x n switch which routes packets from input to output ports. Such a switch can be viewed as a bipartite graph with the input and output ports as the two vertex sets. Packets arriving at input port i and destined for output port j can be modeled as an edge from i to j. Current switch scheduling algorithms view the routing of packets at each time step as a selection of a bipartite matching. The paper takes the view that the switch scheduling problem across a sequence of time-steps is an instance of the edge coloring problem for a bipartite multigraph. Implementation considerations lead one to seek edge coloring algorithms for bipartite multigraphs that are fast, decentralized, and online.