This will be a multi-part Blog that will attempt to explain the evolution of VOQ in the router industry. It will not cover all possible implementations of VOQ. But it will hopefully explain the rational of why VOQ was implemented and illustrate that there are a variety of implementations and they each have there own set of Pros and Cons.
The three parts are:
Part 1 will define the criteria used to evaluate VOQ systems will be defined.
Part 2 will provide a generalized overview of Back Plane interconnects as a framework
Part 3 will provide the evolution of the VOQ concept over time.
What is VOQ? Well in the networking industry it stands for Virtual Output Queuing. But what does that mean? That is a complex answer. The definition/meaning of VOQ has evolved over the years and varies from company to company. Rest assure that no two vendors implementation of VOQ is the same.
Virtual output queueing(VOQ) is the technique used ininput-queued switcheswhere rather than keeping all traffic in a single queue, separate queues are maintained for each possible output location. It addresses a common problem known ashead-of-line blocking.
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 thevirtualqueue for this particular egress port. Other packets in the same physical buffer destined to different (non-congested) output ports are in separatevirtualqueues 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 inHOLB.
It has been shown that VOQ can achieve 100% throughput performance with an effectivescheduling 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. The VOQ mechanism provides throughput at a much higher rate than thecrossbar switcheswithout it.
VOQ scheduling is often referred to as "arbitration" (resolving the concurrent access wishes), whereas the ordering of packets ("packetscheduling") is an additional taskfollowing the VOQ arbitration.
Nick McKeown actually sites a reference to a 1988 paper entitled "High Performance Multiqueue Buffers for VLSI Communication Switches" (June 1988) as one of the first proposals of VOQ.
So what is this Head Of Line Blocking (HOLB) problem and why do we need to fix it?
In the following document, the term “external port” will refer to a router’s LAN/WAN port, such as 1Gbps Ethernet port or a 10Gbps Ethernet port. The term “switch port” will refer to a router’s internal connection to the backplane (i.e. switch fabric).
 Y. Tamir, G. Frazier, "High Performance Multiqueue Buffers for VLSI Communication Switches," Proc. of 15th Annual Symp. on Computer Arch, Jun 1988.
Part 1: Evaluation Criteria
For the purposes of this blog, the criteria used to evaluate VOQ will be as follows:
Keeping output interface full (achieving line rate).
Reducing unintelligent drops (drops that occur without consideration of the current Quality of Service (QoS) policy, also referred to as Class of Service (CoS).
The above criteria are expanded in the following sub-sections. It is this criteria that VOQ has promised to address.
Head Of Line Blocking (HOLB)
Head of Line Blocking is exactly what you think it is. To put it non-computer savvy terms:
It is like when you go to Starbucks and there is a long line at the counter. The person at the front of the line is ordering 20 coffees for his friends/co-workers and each coffee is of course a different complex drink concoction, like say a Venti Caramel Macchiato, half-whole milk, ¼ cream, ¼ 1%, no foam, split quad: shots 1 1/3 decaf Peruvian Free-trade and 2 2/3 regular Kona. ½ whip, 1 packet Splenda, 2 sugars in the raw, a hint of mocha, a shot of hazelnut and a sprinkle of caribou dust”
Now you know what HOLB is. You are stuck behind the slowest moving customer for what seems to be an eternity and all you wanted was a plain Venti House Roast coffee.
In the router world, this is a really big issue. High priority packets waiting in a queue behind low-priority packets whose destination was congested or worse still it is another destination that is actually congested.
There is a strong desire to achieve line rate (100% utilization) on out going (egress) ports, if there is enough input bandwidth to achieve line rate. One of the primary causes for not achieving line rate on the egress ports is HOLB, as was discussed in the prior sub-section.
There are other reasons for a router not to be able to achieve line rate on its egress ports, such as buffer granularity, backplane cell size, etc. These typically yield a saw tooth pattern in the egress port's output rate as a function of packet size. However, this is not the subject of this paper.
Another reason is insufficient bandwidth between line cards. This is referring to the fabric bandwidth or backplane bandwidth. Routers typically have more bandwidth on their backplane connections than their front panel (external) ports. This is known as Fabric Speedup. It is a very important aspect of router design as it effects the router's ability to meet line rate on its egress ports as well as insure good Quality of Service (QoS) attributes. But it comes at a cost to the system:
Increased number of backplane interconnects
Adds complexity to the design
Direct correlation between bandwidth and power consumption
Increased power consumption means more heat to dissipate
So there is a strong desire to reduce the amount of fabric speedup in the system. But determining the right amount of speedup is non-trivial.
Unintelligent drops is another key issue that VOQ is attempting to solve. In a typical router, the QoS policies are typically applied at the egress line card, Like is illustrated in Figure 1 Typical Egress QoS Router. The queues labeled P0-P3 on the egress line card are the deep buffers, also known as Delay Bandwidth Buffers (DBB) and are typically 100ms or more in depth. The queues are typical referred to as per port Output Queues (OQ) that QoS policies are applied such as, priority scheduling, rate shaping, drop policy, etc. It is specifically the drop policy that this paper is concerned with.
Figure 1: Typical Egress QoS Router
A drop policy is configured for each of the P0-P3 OQs. The drop policy can be as simple as only allow this OQ to be of a certain number of bytes in size, known as a tail drop policy. Or it can have a more complex Weighted Random Early Drop (WRED) policy that defines a fill to drop percentage curve to be followed.
In order for the drop policy to be really effective, then ALL of the ingress traffic destined for a specific egress OQ MUST be sent to the egress line card. Otherwise, the drop decision is made with incomplete information. This is a very difficult goal to achieve. Because it would imply that an egress port's connection to the backplane be equal to or greater than the sum of ALL of the ingress ports in the system. Thus most routers have some amount of drops that occur on the ingress line cards. These drops are known as unintelligent drops, because they occurred before the egress drop policy could be applied to them.
In Figure 1, there is a single queue on the ingress line card that is labeled “VOQ”. The purpose of this queue is to help eliminate these unintelligent drops and is the topic of this paper. How this queue is implemented varies greatly across the industry and has evolved over time. How much “VOQ” is needed varies with the system architecture and is dependent on factors such as:
Total number of ports in the system
Total bandwidth of the ports
Aggregation of ports into backplane interconnect
Number of line cards
Number of backplane interconnects
To be continued...
In Part 2 of this series, a brief overview of backplane interconnects/switch fabrics will be presented. Primarily to provide a generalized understanding of how line cards are interconnected on a router. Its only purpose is to provide a framework for evaluating different VOQ architectures.