Virtual Output Queues are an input queuing strategy

Strategy

Strategy, a word of military origin, refers to a plan of action designed to achieve a particular goal. In military usage strategy is distinct from tactics, which are concerned with the conduct of an engagement, while strategy is concerned with how different engagements are linked...

 for use in telecommunications and computer network

Computer network

A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....

 switches. It addresses a common problem known as Head-of-line blocking

Head-of-line blocking

Head-of-line blocking is a performance-limiting phenomenon that occurs in buffered telecommunication network switches.-Description:...

.

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

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

. 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
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 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 maximum no of simultaneous data which each port might receive at a time.

So 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

Nick McKeown

Nicholas William McKeown, better known as Nick McKeown, is an English-American expert in computer networking. His career includes both education and starting companies in Silicon Valley.-Biography:Nick McKeown was born April 7, 1963 in Bedford, England....

 and a group at Stanford University

Stanford University

The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...

for example published a design in 1997.