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 2x2 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 2x2 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 2x2 switch, the probability that anyone of out of these 4 combinations of data will occur = 0.25. So the efficiency of this 2x2 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 2x2 crossbar switch is working at 75% efficiency to give out data from input to output. As n increases, for nxn switches this causes further degradation in efficiency. VOQ (Virtual Output Queuing) overcomes this problem by introducing extra buffers (queues) per port.
Let's revisit the same scenario with 2x2 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.
Quality of service and priority are extensions found in literature of the same time. 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 following the VOQ arbitration.
Read more about this topic: Virtual Output Queues
Famous quotes containing the word description:
“The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.”
—Freda Adler (b. 1934)
“The great object in life is Sensation—to feel that we exist, even though in pain; it is this “craving void” which drives us to gaming, to battle, to travel, to intemperate but keenly felt pursuits of every description whose principal attraction is the agitation inseparable from their accomplishment.”
—George Gordon Noel Byron (1788–1824)
“The next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St Paul’s, like the editions of Balbec and Palmyra.”
—Horace Walpole (1717–1797)