Switch Scheduling via Randomized Edge Coloring

The essence of an Internet router is an n /spl times/ 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. We take 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 us to seek edge coloring algorithms for bipartite multigraphs that are fast, decentralized, and online. We present a randomized algorithm which has the desired properties, and uses only a near-optimal /spl Delta/ + o(/spl Delta/) colors on dense bipartite graphs arising in the context of switch scheduling. This algorithm extends to non-bipartite graphs as well. It leads to a novel switch scheduling algorithm which, for stochastic online edge arrivals, is stable, i. e. the queue length at each input port is bounded at all times. We note that this is the first decentralized switch scheduling algorithm that is also guaranteed to be stable.

Authors

• Gagan Aggarwal
• Rajeev Motwani 0001
• Devavrat Shah
• An Zhu

Keywords

• Switches
• Scheduling algorithm
• Packet switching
• Bipartite graph
• Communication switching
• Traffic control
• Hardware
• Internet
• Routing
• Stochastic processes
• Department Of Computer Science
• Edge Coloring
• Switch Scheduling
• Time Step
• Output Ports
• Input Port
• Multigraph
• Packet Arrival
• High Probability
• Rest Of The Paper
• Time Slot
• Nodes In The Graph
• Maximum Degree
• End Of Step
• Vertex Degree
• General Remarks
• Pair Of Vertices
• Types Of Edges
• Algorithm Running
• End Of Epoch
• Case Of Graphs
• Input-output Pairs
• Common Color