Virtual output queueing

Last updated

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

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]

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.

Related Research Articles

Multiprotocol Label Switching (MPLS) is a routing technique in telecommunications networks that directs data from one node to the next based on labels rather than network addresses. Whereas network addresses identify endpoints, the labels identify established paths between endpoints. MPLS can encapsulate packets of various network protocols, hence the multiprotocol component of the name. MPLS supports a range of access technologies, including T1/E1, ATM, Frame Relay, and DSL.

Wormhole flow control, also called wormhole switching or wormhole routing, is a system of simple flow control in computer networking based on known fixed links. It is a subset of flow control methods called Flit-Buffer Flow Control.

Network congestion in data networking and queueing theory is the reduced quality of service that occurs when a network node or link is carrying more data than it can handle. Typical effects include queueing delay, packet loss or the blocking of new connections. A consequence of congestion is that an incremental increase in offered load leads either only to a small increase or even a decrease in network throughput.

Weighted round robin (WRR) is a network scheduler for data flows, but also used to schedule processes.

<span class="mw-page-title-main">Leaky bucket</span> Network traffic shaping and policing algorithm

The leaky bucket is an algorithm based on an analogy of how a bucket with a constant leak will overflow if either the average rate at which water is poured in exceeds the rate at which the bucket leaks or if more water than the capacity of the bucket is poured in all at once. It can be used to determine whether some sequence of discrete events conforms to defined limits on their average and peak rates or frequencies, e.g. to limit the actions associated with these events to these rates or delay them until they do conform to the rates. It may also be used to check conformance or limit to an average rate alone, i.e. remove any variation from the average.

<span class="mw-page-title-main">Random early detection</span> Algorithm

Random early detection (RED), also known as random early discard or random early drop, is a queuing discipline for a network scheduler suited for congestion avoidance.

A load-balanced switch is a switch architecture which guarantees 100% throughput with no central arbitration at all, at the cost of sending each packet across the crossbar twice. Load-balanced switches are a subject of research for large routers scaled past the point of practical central arbitration.

Generalized processor sharing (GPS) is an ideal scheduling algorithm for process schedulers and network schedulers. It is related to the fair-queuing principle which groups packets into classes and shares the service capacity between them. GPS shares this capacity according to some fixed weights.

Proportional-fair scheduling is a compromise-based scheduling algorithm. It is based upon maintaining a balance between two competing interests: Trying to maximize the total throughput of the network while at the same time allowing all users at least a minimal level of service. This is done by assigning each data flow a data rate or a scheduling priority that is inversely proportional to its anticipated resource consumption.

Fair queuing is a family of scheduling algorithms used in some process and network schedulers. The algorithm is designed to achieve fairness when a limited resource is shared, for example to prevent flows with large packets or processes that generate small jobs from consuming more throughput or CPU time than other flows or processes.

Head-of-line blocking in computer networking is a performance-limiting phenomenon that occurs when a line of packets is held up in a queue by a first packet. Examples include input buffered network switches, out-of-order delivery and multiple requests in HTTP pipelining.

In routers and switches, active queue management (AQM) is the policy of dropping packets inside a buffer associated with a network interface controller (NIC) before that buffer becomes full, often with the goal of reducing network congestion or improving end-to-end latency. This task is performed by the network scheduler, which for this purpose uses various algorithms such as random early detection (RED), Explicit Congestion Notification (ECN), or controlled delay (CoDel). RFC 7567 recommends active queue management as a best practice.

Weighted fair queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ). Whereas FQ shares the link's capacity in equal subparts, WFQ allows schedulers to specify, for each flow, which fraction of the capacity will be given.

<span class="mw-page-title-main">Nick McKeown</span>

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 companies in Silicon Valley.

<span class="mw-page-title-main">Forwarding plane</span>

In routing, the forwarding plane, sometimes called the data plane or user plane, defines the part of the router architecture that decides what to do with packets arriving on an inbound interface. Most commonly, it refers to a table in which the router looks up the destination address of the incoming packet and retrieves the information necessary to determine the path from the receiving element, through the internal forwarding fabric of the router, and to the proper outgoing interface(s).

Adisak Mekkittikul received his B.Eng. from King Mongkut's Institute of Technology Ladkrabang in Thailand and M.S. in electrical engineering from Wichita State University. He completed the Ph.D. degree in electrical engineering at Stanford University, Stanford, California in 1999, after defending dissertation titled "Scheduling Non-Uniform Traffic in High Speed Packet Switchers and Routers" which he wrote while being mentored by Nicholas William McKeown. He was a Senior Member of Technical Staff at Berkeley Concept Research Corp.

Blue is a scheduling discipline for the network scheduler developed by graduate student Wu-chang Feng for Professor Kang G. Shin at the University of Michigan and others at the Thomas J. Watson Research Center of IBM in 1999.

<span class="mw-page-title-main">Credit-based fair queuing</span> Network queuing discipline

Credit-based fair queuing is a computationally efficient alternative to fair queueing. Credit is accumulated to queues as they wait for service. Credit is spent by queues while they are being serviced. Queues with positive credit are eligible for service. The rate of credit accumulation and release can be adjusted on a queue-by-queue basis to produce a weighted queuing behavior.

Bufferbloat is a cause of high latency and jitter in packet-switched networks caused by excess buffering of packets. Bufferbloat can also cause packet delay variation, as well as reduce the overall network throughput. When a router or switch is configured to use excessively large buffers, even very high-speed networks can become practically unusable for many interactive applications like voice over IP (VoIP), audio streaming, online gaming, and even ordinary web browsing.

Design of robust and reliable networks and network services relies on an understanding of the traffic characteristics of the network. Throughout history, different models of network traffic have been developed and used for evaluating existing and proposed networks and services.

References

  1. ↑ 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.
  2. ↑ 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.
  3. ↑ 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.{{cite book}}: CS1 maint: date and year (link)
  4. ↑ 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.