ICS Theory Group

ICS 269, Winter 2004: Theory Seminar


19 Mar 2004:
Switch Scheduling
Gwendoline Chien

A router is a box that switches internet packets from input links to ouput links. The switch system must determine which inputs will transmit to which outputs in a given time slot. Mathematically, the switching component of a router reduces to solving a bipartite matching problem. The router must match as many input links as possible. However, there is tradeoff between fairness and throughput. In this talk, I will give a brief overview of switch scheduling problem and some algorithms that are being used.