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]
Descriptionedit
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]
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.
Referencesedit
^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. CiteSeerX10.1.1.42.5126. doi:10.1109/INFCOM.2000.832562. ISBN978-0-7803-5880-5. S2CID 11834666.
^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. CiteSeerX10.1.1.668.8621. doi:10.1109/ATM.1999.786865. ISBN978-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. CiteSeerX10.1.1.29.4129. doi:10.1109/GLOCOM.1999.829963. ISBN978-0-7803-5796-9. S2CID 1649478.
February 29, 2024
virtual, output, queueing, technique, used, certain, network, switch, architectures, where, rather, than, keeping, traffic, single, queue, separate, queues, maintained, each, possible, output, location, addresses, common, problem, known, head, line, blocking, . 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 editIn 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 edit 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 a href Template Cite book html title Template Cite book cite book a 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 Retrieved from https en wikipedia org w index php title Virtual output queueing amp oldid 1168816870, wikipedia, wiki, book, books, library,
