Virtual output queueing (VOQ) is a technique used in certain

network switch A network switch (also called switching hub, bridging hub, Ethernet switch, and, by the IEEE, MAC bridge) is networking hardware that connects devices on a computer network by using packet switching to receive and forward data to the destinat ...

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 Head-of-line blocking (HOL blocking) in computer networking is a performance-limiting phenomenon that occurs when a queue of packets is held up by the first packet in the queue. This occurs, for example, in input-buffered network switches, out-o ...

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 In computing, scheduling is the action of assigning resources to perform tasks. The resources may be processors, network links or expansion cards. The tasks may be threads, processes or data flows. The scheduling activity is carried out by ...

. 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 switch In electronics and telecommunications, a crossbar switch (cross-point switch, matrix switch) is a collection of switches arranged in a Matrix (mathematics), matrix configuration. A crossbar switch has multiple input and output lines that form a ...

es without it. There are many algorithms for design and implementation of fast VOQ. For example,

Nick McKeown Nicholas (Nick) William McKeown FREng, is a Senior Fellow at Intel, a professor in the Electrical Engineering and Computer Science departments at Stanford University, and a visiting professor at Oxford University. He has also started technology co ...

and a group at

Stanford University Leland Stanford Junior University, commonly referred to as Stanford University, is a Private university, private research university in Stanford, California, United States. It was founded in 1885 by railroad magnate Leland Stanford (the eighth ...

published a design in 1997.

Quality of service Quality of service (QoS) is the description or measurement of the overall performance of a service, such as a telephony or computer network, or a cloud computing service, particularly the performance seen by the users of the network. To quantitat ...

and priority are extensions found in literature of the same time. VOQ scheduling is often referred to as "

arbitration Arbitration is a formal method of dispute resolution involving a third party neutral who makes a binding decision. The third party neutral (the 'arbitrator', 'arbiter' or 'arbitral tribunal') renders the decision in the form of an 'arbitrati ...

" (resolving the concurrent access wishes), whereas the ordering of packets ("packet

scheduling A schedule (, ) or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things ...

") is an additional task following the VOQ arbitration.

References

{{Queueing theory Switches Queue management