Performance of exhaustive matching algorithms for input-queued switches

Virtual output queue (VOQ) architecture is commonly used for avoiding head-of-line blocking in input-queued switches. Many algorithms have been developed for transferring the cells from the VOQs to the output ports. Traditional iterative algorithms such as iSLIP and DRRM, achieve 100% throughput under uniform traffic. But under non-uniform traffic, throughput drops significantly. Recently, a new paradigm of exhaustive matching (EM) has been introduced for handling non-uniform traffic while preserving the complexity of traditional iterative algorithms. In EM, a VOQ is served continuously until it becomes empty. Only the input ports that have finished serving a VOQ look for a new match. This strategy produces very good throughput and delay performance in uniform and non-uniform traffic. However under some traffic patterns, there is a starvation problem when a VOQ occupies an output port for an extended period of time. This problem can be eliminated by providing a priority service for a VOQ that has waited an excessively long time. The resulting algorithm, prioritized EM (PEM), eliminates starvation and achieves very high throughput for many traffic patterns.