Introduction to ATM|Introduction to ABR|The Virtual Output Queue|Simulation Results|ABR Publications|ABR Links|Back to iPOINT
This page presents a concept, that allows ABR algorithms, designed for an output-buffered, single FIFO-queued switch to be used in an input-buffered and per-VC queued switch. This technique uses in-band communication to transmit data among the different modules of the switch. The supplementary information is carried in unused bytes of the RM-cell and therefore does not affect the throughput of the switch. The computational complexity of the virtual output queue is independent of the number of VCs.
Contents:
ABR algorithms need to measure the congestion of an outgoing link. Two schemes are possible: measurement of the link utilization and/or measurement of the queue length. The most powerful algorithms use queue length measurement.
It is not simple to characterize the outgoing queue length on an input-buffered switch with per-VC queueing. Consider the simple network as in figure 1, featuring one switch, three sources and one destination. Traffic is flowing from the three sources (S1, S2 and S3) to the corresponding destination (D). Three ports of the switch are connected to the three sources (S1, S2 and S3). The forth port of the switch is connected to the destination (D).
When the sources are not bottlenecked, they are able to transmit at the maximum speed of the link. In this case, the link connected to the destination would become congested. This link, becomes the bottleneck of the system.
For an input-buffered switch implementing ABR, this bottlenecked link trigger queue growth at each input port with incoming traffic.
Figure 1 Input-buffered switch
The ABR algorithms studied in the literature, are designed to be located where congestion takes place. In the example, the switch is congested at port 4. Therefore the instance of the ABR algorithm at the egress side of port 4 would conceptually provide the buffering.
In an output-queued switch, the queue of port 4 would grow and could be measured easily by the ABR algorithm, implemented at the same port.
In an input-queued switch, however, measurement of the queue length is distributed over several input ports, as shown in the example. In other words, the buffer for the cells heading to an certain link is partitioned into several queues located in physically different modules.
The goal of this work is to apply existing ABR algorithms to an input-buffered switch architecture. Since these algorithms assume a single FIFO output queue for ABR traffic, some steps have to be taken in order to simulate a similar architecture to the ABR algorithm. Figure 2 illustrates the problem of mapping the architecture of b) to the switch designed of a).
Figure 2 The problem of distributed queues
Transmitting Queue Length Information within the Switch
The concept of the virtual queue is to collect the queue length information of all VCs having a common output port and to transmit this information from the ingress module of the source input ports to the egress module of the common output port. Figure 3 illustrates this flow of information.
Figure 3 The virtual output queue
A key observation is that the RM-cell is an ideal carrier for this information:
Note that the Queue Length (QL) field of the RM-cell is not related to the virtual queue length. According to ITU-T I.371, it represents the maximum number of cells currently queued for this connection among those network elements supporting this parameter.
Assembling the Virtual Output Queue
The Virtual Output Queue pretends that there is a single FIFO queue for all ABR traffic at the egress of a port, although the cells are actually stored at the ingress part of one or more ports. The desired information at the egress is:
(1)
where QL stands for Queue Length.
A naive way to transmit the queue length would be to write the per-VC queue length directly into the RM-cell. At the egress, the queue length for each of the ABR VCs would be stored separately in a table. Scalability in terms of number of VCs and speed would be very limited. A significant amount of memory would be needed to store the per-VC queue lengths at the egress modules.
The solution proposed in this paper is to use differential information. Instead of writing the absolute length of the per-VC queue into the RM-cell, the difference of the current queue length (QLnew(VCi)) and the queue length at the time when the last RM-cell of VC i arrived at the ingress (QLold(VCi)) is stored within the RM-cell.
(2)
QLnew(VCi) is then written into QLold(VCi).
In order to calculate the length of the virtual output queue, the egress side totals the per-VC queue lengths. Each time a value D QL(VCi) arrives in a forward RM-cell at the egress, the Virtual_Output_QL is updated as shown below.
(3)
From equation (3), we can see that only one addition has to be performed when a forward RM-cell arrives at the egress side. As we also notice from this equation, the calculation complexity of the virtual output queue length is independent of the number of ABR VCs.
Note that the Virtual_Output_QL is delayed, since D QL(VCi) is written into the RM-cell when the RM-cell arrives at the per-VC queue of the ingress. The Virtual_Output_QL is updated when this RM-cell arrives at the egress.
Differential information is sensitive to errors. If D QL(VCi) were corrupt, the error would propagate and affect all the future calculations of the virtual output queue length. Fortunately, this problem does not occur for systems with a switch fabric that does not loose cells (such as iPOINT). While RM-cells can be lost at arrival at the switch because of queue overflow, the queue will know that they were dropped. D QL(VCi) is not written into the RM-cell and QLold(VCi) is not updated before it is assured that the queue has enough space to accommodate the incoming cell.
The following paragraphs present how the ABR algorithms must be split off and where the different parts must be placed within the switch.
Let us first consider a simplified input-buffered and per-VC queued switch, which is represented in figure 4. This example has one ABR connection entering the switch at port 1 and leaving at port 2. This is sufficient to explain the principle and can be easily generalized for a higher number of connections. Moreover, only two ports of the switch are represented in the figure. Each port includes of two blocks (1 and 2) containing parts of the ABR algorithm.
From the standpoint of a connection, Block 1 is further split into 1a and 1b modifying the RM-cells of a connection in different ports. Depending on the direction of the RM-cell, either 1a or 1b is executed. The DIR field of the RM-cell indicates the whether the cell travels from the source to the destination (forward RM-cell: RM.DIR=0) or vice versa (backward RM-cell: RM.DIR=1) (fig. 4).
Figure 4 Functional blocks of the ABR algorithms
Subblock 1a generates differential queue length and writes it into the forward RM-cell (fig. 5).
Subblock 1b computes the feedback and writes it into the backward RM-cell (fig. 5).
Block 2 collects the differential queue length and calculates the virtual ouput queue length. It further measures and calculates other values to determine the fair share rate. Block2 might also extracts values from forward RM-cells (fig. 6).
Introduction to ATM|Introduction to ABR|The Virtual Output Queue|Simulation Results|ABR Publications|ABR Links|Back to iPOINT
Last updated 04/09/98 by Matthias Bossardt