Virtual output queueing
 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
Virtual Output Queues (VOQ) are an input queuing strategy for use in telecommunications and computer network switches. It addresses a common problem known as head-of-line blocking.[1]
Description
In VOQ each input port maintains a separate queue for each output port. 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. VOQ mechanism provides throughput at a much higher rate than the crossbar switches without it.
For example, consider a 2×2 crossbar switch.
--------
a--->|-\--/-|--->--0
| \/ |
| /\ |
b--->| /--\ |---->-1
--------
Let's say that data "0" arriving at port A or B will go to output port 0. Similarly data "1" arriving at port A or B will go to output port 1. So the number of combinations that can happen at the input port A, B are: 00, 01, 10, and 11.
If data at the input is "00", this means both the input data at time t are contending for the same output port 0 and the output port 0 can't route both the data at the same time as it can handle only one unit data per time slot. So in this case the efficiency of the 2×2 switch (without VOQ) is 0.5.
Same is the case for data "11" in which the efficiency is 0.5. Similarly for data "01" and "10" the efficiency is 1 as there is no contention as both the data go to both output ports 0 and 1.
Since it's a 2×2 switch, the probability that any one of out of these four combinations of data will occur = 0.25. So the efficiency of this 2×2 switch is:
(0.25 * 0.5) --> for data 00 + (0.25 * 0.5) --> for data 11 + (0.25 * 1.0) --> for data 01 + (0.25 * 1.0) --> for data 10 --------------- = 0.75 (75%)
So we see that the 2×2 crossbar switch is working at 75% efficiency to give out data from input to output. As n increases, for n×n switches this causes further degradation in efficiency. VOQ overcomes this problem by introducing extra buffers (queues) per port.
Let's revisit the same scenario with 2×2 switch with VOQ support.
--------
a--->|-\--/-|-OO-->--0
| \/ |
| /\ |
b--->| /--\ |-OO--->-1
--------
Here each output port has n buffers per port to accommodate a given maximum number of simultaneous data packets that each port can receive at a time. This buffering mechanism removes the bottleneck per port on peak time and distributes it over a period of time increasing the switch performance.
There are many algorithms for design and implementation of fast VOQ. Nick McKeown and a group at Stanford University for example published a design in 1997.[2]
Quality of service and priority are extensions found in literature of the same time.[3] The 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.
See also
References
- ^ Mark W. Goudreau; Stavros G. Kolliopoulos; Satish B. Rao (2000). "Scheduling Algorithms for Input-Queued Switches: Randomized Techniques and Experimental Evaluation". Proceedings of IEEE INFOCOM: 1634–1643. doi:10.1109/INFCOM.2000.832562.
- ^ Nick McKeown; Martin Izzard; Adisak Mekkittikul; Bill Ellersick; Mark Horowitz (1997). "Tiny Tera: a packet switch core" (PDF). IEEE Micro: 26–33. doi:10.1109/40.566194.
- ^ Rainer Schoenen; Guido Post; Gerald Sander (1999). "Prioritized arbitration for input-queued switches with 100% throughput". Proceedings of ATM Workshop: 253–258. doi:10.1109/ATM.1999.786865.
- ^ Rainer Schoenen; Roman Hying (1999). "Distributed cell scheduling algorithms for virtual-output-queued switches". Proceedings of IEEE Globacom: 1211–1215. doi:10.1109/GLOCOM.1999.829963.