Virtual output queueing
Virtual output queueing (VOQ) is a technique used in certain network switch architectures where, rather than keeping all traffic in a single queue, separate queues are maintained for each possible output location. It addresses a common problem known as head-of-line blocking (HOLB).
In VOQ, the physical buffer of each input port maintains a separate virtual queue for each output port. Therefore congestion on an egress port will block only the virtual queue for this particular egress port. Other packets in the same physical buffer destined to different (non-congested) output ports are in separate virtual queues and can therefore still be processed. In a traditional setup, the blocked packet for the congested egress port would have blocked the whole physical buffer, resulting in head-of-line blocking.
It has been shown that VOQ can achieve 100% throughput performance with an effective scheduling algorithm. This scheduling algorithm should be able to provide a high speed mapping of packets from inputs to outputs on a cycle-to-cycle basis. The VOQ mechanism provides throughput at a much higher rate than the crossbar switches without it.
VOQ scheduling is often referred to as "arbitration" (resolving the concurrent access wishes), whereas the ordering of packets ("packet scheduling") is an additional task following the VOQ arbitration.
- Goudreau, Mark W.; Kolliopoulos, Stavros G.; Rao, Satish B. (2000). "Scheduling algorithms for input-queued switches: Randomized techniques and experimental evaluation". Proceedings of IEEE INFOCOM. CiteSeerX . ISBN 0-7803-5880-5. doi:10.1109/INFCOM.2000.832562.
- McKeown, Nick; Izzard, Martin; Mekkittikul, Adisak; Ellersick, Bill; Horowitz, Mark (1997). "Tiny Tera: a packet switch core" (PDF). IEEE Micro. 17: 26–33. doi:10.1109/40.566194.
- Schoenen, Rainer; Post, Guido; Sander, Gerald (1999). "Prioritized arbitration for input-queued switches with 100% throughput". Proceedings of ATM Workshop. ISBN 4-88552-164-5. doi:10.1109/ATM.1999.786865.
- Schoenen, Rainer; Hying, Roman (1999). "Distributed cell scheduling algorithms for virtual-output-queued switches". Proceedings of IEEE Globacom. ISBN 0-7803-5796-5. doi:10.1109/GLOCOM.1999.829963.