Critical Node Matching Algorithm for Scheduling Switches with Input Queues

Packet switches are used in the Internet to forward information between a sender and receiver and are the critical bottleneck in the Internet. Without faster packet switch designs, the Internet cannot continue to scale-up to higher data rates. Packet switches must be able to achieve high throughput and low delay. In addition, they must be stable for all traffic loads, must efficiently support variable length packets, and must be scalable to higher link data rates and greater numbers of ports. Some unbalanced traffic loads result in instability for input queued (IQ) switches. Crossbars are main components of communication switches used to construct interconnection networks. Scheduling algorithms control contention in switch architecture. Several scheduling algorithms were proposed for input-queued crossbar switch architectures. This paper suggests a Critical Node Matching algorithm based on Maximum Node Containing matching (MNCM). This algorithm is the lowest complexity deterministic algorithm with good delay performance that delivers 100% throughput.