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.^[1]

Description

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.^{[citation needed]} 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.

There are many algorithms for design and implementation of fast VOQ. For example, Nick McKeown and a group at Stanford University published a design in 1997.^[2]

Quality of service and priority are extensions found in literature of the same time.^[3]

VOQ scheduling is often referred to as "arbitration" (resolving the concurrent access wishes), whereas the ordering of packets ("packet scheduling") is an additional task^[4] following the VOQ arbitration.

References

^ Goudreau, Mark W.; Kolliopoulos, Stavros G.; Rao, Satish B. (2000). "Scheduling algorithms for input-queued switches: Randomized techniques and experimental evaluation". Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064). Vol. 3. pp. 1634–1643. CiteSeerX 10.1.1.42.5126. doi:10.1109/INFCOM.2000.832562. ISBN 978-0-7803-5880-5. S2CID 11834666.
^ McKeown, Nick; Izzard, Martin; Mekkittikul, Adisak; Ellersick, Bill; Horowitz, Mark (1997). "Tiny Tera: a packet switch core" (PDF). IEEE Micro. 17: 26–33. arXiv:cs/9810006. doi:10.1109/40.566194. S2CID 1909255.
^ Schoenen, Rainer; Post, Guido; Sander, Gerald (1999). "Prioritized arbitration for input-queued switches with 100% throughput". IEEE ATM Workshop '99 Proceedings (Cat. No. 99TH8462). pp. 253–258. CiteSeerX 10.1.1.668.8621. doi:10.1109/ATM.1999.786865. ISBN 978-4-88552-164-5. S2CID 14749858.{{cite book}}: CS1 maint: date and year (link)
^ Schoenen, Rainer; Hying, Roman (1999). "Distributed cell scheduling algorithms for virtual-output-queued switches". Seamless Interconnection for Universal Services. Global Telecommunications Conference. GLOBECOM'99. (Cat. No.99CH37042). Vol. 2. pp. 1211–1215. CiteSeerX 10.1.1.29.4129. doi:10.1109/GLOCOM.1999.829963. ISBN 978-0-7803-5796-9. S2CID 1649478.

[1] Goudreau, Mark W.; Kolliopoulos, Stavros G.; Rao, Satish B. (2000). "Scheduling algorithms for input-queued switches: Randomized techniques and experimental evaluation". Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064). Vol. 3. pp. 1634–1643. CiteSeerX 10.1.1.42.5126. doi:10.1109/INFCOM.2000.832562. ISBN 978-0-7803-5880-5. S2CID 11834666.

[2] McKeown, Nick; Izzard, Martin; Mekkittikul, Adisak; Ellersick, Bill; Horowitz, Mark (1997). "Tiny Tera: a packet switch core" (PDF). IEEE Micro. 17: 26–33. arXiv:cs/9810006. doi:10.1109/40.566194. S2CID 1909255.

[3] Schoenen, Rainer; Post, Guido; Sander, Gerald (1999). "Prioritized arbitration for input-queued switches with 100% throughput". IEEE ATM Workshop '99 Proceedings (Cat. No. 99TH8462). pp. 253–258. CiteSeerX 10.1.1.668.8621. doi:10.1109/ATM.1999.786865. ISBN 978-4-88552-164-5. S2CID 14749858.{{cite book}}: CS1 maint: date and year (link)

[4] Schoenen, Rainer; Hying, Roman (1999). "Distributed cell scheduling algorithms for virtual-output-queued switches". Seamless Interconnection for Universal Services. Global Telecommunications Conference. GLOBECOM'99. (Cat. No.99CH37042). Vol. 2. pp. 1211–1215. CiteSeerX 10.1.1.29.4129. doi:10.1109/GLOCOM.1999.829963. ISBN 978-0-7803-5796-9. S2CID 1649478.

[1]

[2]

[3]

[4]

v t e Queueing theory
Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue
Arrival processes	Poisson point process Markovian arrival process Rational arrival process
Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network
Service policies	FIFO LIFO Processor sharing Round-robin Shortest job next Shortest remaining time
Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method
Limit theorems	Fluid limit Mean-field theory Heavy traffic approximation Reflected Brownian motion
Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue
Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering
Category