Dynamic Queue Length Thresholds in a Shared Memory ATM Switch

1. Field of the Invention

This disclosure relates to packet-switched communications systems. More particularly, this disclosure is directed to a dynamic threshold system and method for regulating the queue lengths in a shared-memory asynchronous transfer mode (ATM) switch.

2. Description of the Related Art

Communication systems often require optimal allocation of resources such as available memory or bandwidth for reliable and/or efficient communications or to maximize channel capacity. The conventional approach is to use all of the available memory or bandwidth, as memory and bandwidth are generally limited.

Advantages may be obtained by purposefully not utilizing a portion of the memory or bandwidth. For example, as described in E. L. Hahne et al., "DQDB Networks With and Without Bandwidth Balancing" IEEE TRANS ON COMMUNICATIONS, VOL. 40, NO. 7, pp. 1192-1204, a distributed queue dual bus (DQDB) network protocol implements bandwidth balancing to equalize throughput by allocating a small amount of bus bandwidth in order to facilitate coordination among nodes currently using that bus. A maximum permissible nodal throughput rate is proportional to the unused bus capacity.

In the field of switched broadband ISDN (BISDN), asynchronous transfer mode (ATM) packet switching may be implemented using a shared-buffer-memory-based architecture, where incoming packets destined for different output ports are buffered in queues corresponding to those ports and the queues share a common memory.

As memory is limited, various arrangements have been developed to maximize memory capacity and to address memory overflow. Such an arrangement is described in commonly assigned U.S. Pat. No. 5,233,606 to Pashan et al.

In a shared-memory ATM switch with no buffer management procedures, a small number of output port queues may occupy a large portion of memory, so that other output ports may not be able to acquire enough memory to function efficiently. The throughput of the starved output queues may thus be diminished and their packet loss rates increase. The resulting service is unfair, and overall system efficiency can also suffer.

By adapting the approach of purposefully not utilizing a portion of memory, in a manner similar to the E. L. Hahne reference above for bandwidth balancing, a fairer and overall more efficient system may be achieved.

A system is disclosed for allocating memory space to queues in an asynchronous transfer mode (ATM) switch, including an ATM switch having a processor with stored programs, a shared memory, and a plurality of input and output ports. As instructed by the processor, the ATM switch receives a plurality of packets on its input ports, stores these packets temporarily in the memory, and transmits each packet on an appropriate output port.

The memory is configured for storing the packets in a plurality of queues, where each queue is associated with packets received for a corresponding one of the output ports. All the output port queues share the memory space in common.

The processor is configured for computing availability values based upon the total occupancy of the memory, for computing control thresholds as functions of these availability values, for computing output port queue lengths, for comparing the output port queue lengths to the control thresholds, and for controlling admittance of packets to the output port queues based on these comparisons.

When deciding whether to accept a packet, the particular availability value and, hence, the particular control threshold used by the processor, may depend on the priority of the packet.

A method is also disclosed for allocating memory space in a shared-memory ATM switch, including the steps of: maintaining a count of the length of each output port queue; maintaining a set of control thresholds, one for each packet priority level; and regulating the admission of packets to the memory. The step of maintaining the control thresholds involves performing the following steps whenever the occupancy of the shared memory changes (due to a packet being written into or read out from any output port queue in the shared memory): updating a set of availability values based upon the occupancy of the memory, with one availability value for each packet priority level; and computing each control threshold as a function of the corresponding availability value. The step of regulating the admission of a packet includes: receiving a packet at an input port; determining the priority of the packet; determining the output port for the packet; determining the length of the corresponding output port queue; determining an appropriate control threshold based on the packet priority; comparing the output port queue length to the control threshold; and, if this comparison is favorable, storing the packet in its output port queue. Inserting the packet into its output port queue causes the maintenance steps to update the length count for that output port queue and to update the availability values and control thresholds for all priority levels.

The features of the disclosed dynamic threshold system and method will become more readily apparent and may be better understood by referring to the following detailed description of an illustrative embodiment of the present invention, taken in conjunction with the accompanying drawings, where:

FIG. 1 illustrates a block diagram of the components of the packet communications module using the disclosed dynamic threshold system and method;

FIG. 2 illustrates a flow diagram of the portion of the disclosed dynamic threshold system and method that computes the control thresholds; and

FIG. 3 illustrates a flow diagram of the portion of the disclosed dynamic threshold system and method that regulates packet admission.

Referring now in specific detail to the drawings, with like reference numerals identifying similar or identical elements, as shown in FIG. 1, the present disclosure describes a shared-buffer-memory-based packet communications module 10 for processing packets, which are herein defined as units of data that are addressed with routing information. In the context of packet processing systems, the packets are allowed to be of any length, or may be of a length not greater than a predetermined maximum.

In the exemplary embodiment described herein, the disclosed dynamic threshold system and method are illustrated for a packet switch with multiple input ports and multiple output ports, such as an asynchronous transfer mode (ATM) switch, using fixed length packets. For example, the packets may be fixed to be exactly 53 bytes long, where such 53 byte long packets are termed "cells". Alternatively, the packets in a higher protocol layer may have a longer length and are termed "messages" which may be subdivided to generate a plurality of cells for ATM switching.

It is understood that other packet lengths, including packets of variable length, may be processed by the disclosed dynamic system and method.

The present disclosure describes an exemplary embodiment of a shared memory ATM switch implementing the dynamic threshold system and method. In alternative embodiments, the disclosed dynamic threshold system and method may also be used in conjunction with multiple-input, single-output packet systems (i.e., multiplexers) and single-input, multiple-output packet systems (i.e., demultiplexers). For multiplexers, the dynamic thresholds would be used to allocate memory among packets received from competing input ports.

In the exemplary embodiment, the disclosed packet communications module 10, as a shared memory ATM switch, is connected to one or more input ports 12 over which module 10 receives incoming packets, with individual packets having a priority level. The packet communications module 10 is also connected to one or more output ports 14 for outputting the switched packets. Input ports are connected to input and output (I/O) circuitry 16 which couples input ports to a processor 18 and a memory 20.

ATM switches are well known in the art. In the exemplary embodiment of the packet communications module 10 as an ATM switch, the I/O circuitry 16 may include such mechanisms as phase-alignment circuitry, serial-to-parallel and parallel-to-serial shift registers. Copies of header portions of incoming packets received from input ports are sent by I/O circuitry 16 to processor 18, and the packets are sent by I/O circuitry 16 to memory 20 for storage.

The shared memory 20 shown in FIG. 1 may be embodied as one or more RAMs that implement at least one queue 22 as an output port queue, with each output port queue dedicated to a specific output port. In an exemplary embodiment, the queues 22 in FIG. 1 are preferably implemented as logical queues in the form of linked lists, but in alternative embodiments, the queues 22 may be implemented as physical queues or some other data structures in memory 20. A count for the queue length may be implemented for each queue by the processor 18.

Referring again to FIG. 1, processor 18 controls storage of incoming packets in memory 20 and transmission of stored packets at the output ports. In the exemplary embodiment disclosed herein, the processor 18 may include associated memory 24 and control logic to maintain an input port counter 26, an output port counter 28, a queue-length counter 30, a control threshold value 32, and an availability value 34. A shifter 36 may be included as a register in the processor 18 or in the associated memory, and a comparator 38 may be included or implemented by the processor 18.

In another exemplary embodiment, an admission table (not shown) may be used to store and track the status of each queue according to packet priority values.

Based on the header of an incoming packet, received from I/O circuitry 16, the processor 18 determines the priority and the destination output port of the received packet. The input port counter 26 determines which input port to read and when to read the received packets therefrom.

Then the processor 18 causes the packet to be stored in a corresponding output port queue in memory 20, and increments that queue's corresponding length count in counter 30. The processor 18 also periodically accesses the output port queue that is identified by the present count of the output-port counter 28, retrieves therefrom an packet that is at the head of the queue, decrements that queue's corresponding length counter 30, and causes I/O circuitry 16 to transmit the retrieved packet on the corresponding one of the output ports.

The processor 18 allows the output queues 22 to occupy memory 20 in a conventional manner using procedures known in the art implemented either in hardware or in software.

The dynamic threshold system and method described herein regulate the sharing of memory among different output queues in the shared memory ATM switch module 10 by having the maximum permissible length for any individual queue at any instant of time be a function of the available buffer space in the shared memory 20. While many functions may be implemented, the preferred embodiment of the dynamic threshold system and method disclosed herein uses a linear function; for example the maximum permissible queue length is a proportion or fraction of the available memory, with a predetermined constant of proportionality. The dynamic threshold system and method presented herein improves fairness and switch efficiency by guaranteeing access to the buffer space for all output queues. As disclosed herein, the dynamic threshold system and method may be adapted to handle packets of different space priority classes, providing better loss performance to higher priority packets.

The instantaneous proportionality of queue lengths to unused buffering in the ATM switch 10 is similar to bandwidth balancing in Distributed Queue Dual Bus (DQDB) networks as described above. The dynamic threshold system and method deliberately does not utilize a small amount of buffer space in memory 20, and attempts to equally share the remaining buffer space among the active output queues.

The dynamic threshold system and method is expected to improve fairness and switch efficiency by guaranteeing access to the buffer space for all output queues. In addition, the packet losses that occur with dynamic thresholds tend to be clustered at a few offending queues. This is a desirable feature in ATM systems, since it results in fewer messages being disturbed at higher protocol layers, and, hence, fewer message retransmissions. Dynamic thresholds are relatively easy to implement because packets are dropped before entering the buffer. Dynamic thresholds perform better than static thresholds because dynamic thresholds adapt to uncertain or changing load conditions.

In the present disclosure, the dynamic threshold system and method for an ATM switch is described without space (loss) priorities. When an ATM switch is overloaded, it is desirable to divide the memory fairly among the active output queues. All queues with sufficient traffic to warrant thresholding should obtain the same amount of space, called the control threshold. The control threshold value is determined by monitoring the total amount of unused buffer space in the shared memory.

The dynamic threshold system and method attempts to limit each output queue length to some function f of the unused buffer space, and output queues with less demand than this can have all the space they need. At time t, let T(t) be the control threshold and let Q.sup.i (t) be the length of queue i. Let Q(t) be the sum of all the queue lengths, i.e. the total occupancy of the shared memory. Then, if B is the total buffer capacity of the shared memory is

The simplest method is to set the control threshold to a multiple (or, alternatively, a fraction) of the unused buffer space by

which is stored in a register 32 in the associated memory 24 of the processor 18 as shown in FIG. 1, where the factor .alpha. is a constant of proportionality. As used herein, the term "multiple" is understood to include fractional values where .alpha.<1.

It is contemplated that, in alternative embodiments, other linear functions as well as non-linear functions may be implemented as per Eq. (1) above.

An arriving packet for queue i is blocked at time t if Q.sup.i (t).gtoreq.T(t). All packets going to this queue are blocked until the queue length drops below the control threshold.

Whenever the load changes, the dynamic threshold system goes through a transient response. For example, when a lightly loaded output queue suddenly becomes active, the total buffer occupancy goes up, the control threshold goes down, and queues exceeding the threshold have their arrivals blocked temporarily while they drain, freeing up more packet buffers for the newly active queue. If there are M queues, which are all very active, then their "steady state" queue lengths are ##EQU1##

The total buffer space used is ##EQU2##

In the worst case (i.e. M=1), the amount of unused memory is (B-.alpha.B/(1+.alpha.))=B/(1+.alpha.) .

The disclosed dynamic threshold system deliberately reserves a small amount of space in memory by not allocating it to any currently active output queue. This spare buffer space serves several functions. For example, the spare buffer space provides a cushion during transient periods when an output queue first becomes active and needs buffer space. This reduces packet loss during such transient periods.

When an output queue has such a load increase and begins taking over some of the spare buffer space, this action signals the buffer allocation mechanism that the load conditions have changed and that an adjustment of thresholds is now required. If there were not such built-in spare buffering, then the packet arrival rates and/or loss rates of the individual output queues would have to be monitored to determine when load conditions had changed.

The threshold value is very easy to compute, since it is based on the total buffer occupancy of the switch.

In another embodiment, the dynamic queue thresholds are applied to a system with multiple space (loss) priorities. The space priority classes are assigned numerical labels 0 through P, following convention by assigning small numerical labels to the more important ("higher priority") classes. For example, when there are two classes, Class 0 packets belong to the loss-sensitive class, while Class 1 packets can tolerate higher packet loss rates.

The single-priority dynamic queue threshold system and method admits packets of priority p to queue i if:

There are four ways to incorporate space priorities here:

1. vary the effective buffer size B according to priority level, such that Eq. (5) becomes:

2. vary the factor .alpha. according to priority level, such that Eq. (5) becomes:

3. instead of comparing the threshold T(t) to the queue length Q.sup.i (t), compare it to the number Q.sup.i.sub.p (t) of priority p packets in queue i, such that Eq. (5) becomes:

or compare T (t) to ##EQU3## in which case Eq. (5) becomes: ##EQU4## 4. replace the total buffer occupancy Q(t) with the number Q.sub.p (t) of packets of priority p; in which case Eq. (5) becomes:

or replace Q(t) with ##EQU5## in which case Eq. (5) becomes: ##EQU6##

Some of these methods of priority incorporation may work better in combination, and many combinations of these four ways are possible.

In an exemplary embodiment implementing the first method above, for each priority level p, there is a corresponding parameter B.sub.p to which the total buffer occupancy Q(t) is compared, where:

The effective buffer space A.sub.p available to packets of a priority level p is:

Whenever the total buffer occupancy Q(t) equals or exceeds B.sub.p, i.e. whenever A.sub.p .ltoreq.0, no packets of priority p are admitted to the buffer. If Q(t) is less than B.sub.p, then a packet of priority p may be admitted or blocked, depending on the length of the queue i that the packet would join. Specifically, packets of priority p are admitted to queue i if

The dynamics of this method are illustrated using two scenarios as follows: in the first scenario, a single overloaded queue i grows while the total buffer occupancy Q(t) is relatively stable. When Q.sup.i (t) crosses .alpha..multidot.(B.sub.p -Q(t)), no more priority P packets are admitted to queue i. If Q.sup.i (t) continues to grow to .alpha..multidot.(B.sub.p-1 -Q(t)), packets of priority P-1 are also denied admission to queue i. Ultimately, if Q.sup.i (t) reaches .alpha..multidot.(B-Q(t)), no more packets of any priority are admitted to queue i until the queue drains below this threshold again.

For the second scenario, assume that the total queue length Q(t) is growing, but not because of an extreme overload of any one queue. As Q(t) approaches B.sub.p, first the longer queues have their priority P traffic blocked. By the time Q(t) reaches B.sub.p, all queues have their priority P traffic blocked, because the individual queue length threshold .alpha..multidot.(B.sub.p -Q(t)) becomes zero at that point. During this buildup of Q(t) to B.sub.p, those very long queues i that were the first to lose their priority P arrivals might also start having their packets of priority P-1 blocked, provided Q.sup.i (t).gtoreq..alpha..multidot.(B.sub.p-1 -Q(t)). If Q(t) exceeds B.sub.p and approaches B.sub.p-1, eventually all queues have their traffic of priority P-1 blocked. As Q(t) crosses the various global threshold values B.sub.p, traffic of the corresponding priority levels is blocked. Finally if B.sub.1 .ltoreq.Q(t)<B.sub.0 =B, then only packets of priority 0 are admitted to the buffer. As the buffer becomes nearly completely full, the dynamic threshold system and method blocks even priority 0 packets from extremely long queues. If all queues have sufficient priority 0 traffic demand to engage this highest level of threshold control, then the queue lengths tend toward equal values given by Eq. (3) above.

In the preferred embodiment, each space priority level p=0, 1, 2, . . . , P will have a control threshold value T.sub.p (t) to which a queue length Q.sup.i (t) is compared whenever a packet of space priority p wants to join queue i. These queue control thresholds are the same for all queues, so there are only P+1 different queue control threshold values 32 to store and maintain in memory 24 associated with the processor 18.

In determining the available free space in the memory, the queue control threshold setting T.sub.0 for the highest priority class 0 is a function of the quantity A.sub.0 =(B.sub.0 -Q(t))=(B-Q(t)). This is simply the free space, which is the length of the free list, i.e. the list of unoccupied packet buffers in the shared memory. For general priority level p, the threshold setting T.sub.p is a function of A.sub.p =(B.sub.p -Q(t)), the free space available for packets of class p. There are several ways to compute this quantity A.sub.p :

(i) use one counter for each of the space priority classes p. This counter is initialized to B.sub.p and counts up or down for every packet departure or arrival respectively;

(ii) subtract a constant from the length of the free list as follows:

(B.sub.p -Q(t))=(B-Q(t))-(B-B.sub.p).

In order to facilitate implementation, the dynamic threshold system and method may restrict the choice of factors .alpha.to integer powers of 2 (. . . , 1/8, 1/4, 1/2, 1, 2, 4, 8, . . . ), where the integer power may be positive, negative, or zero; that is, .alpha. may equal 2.sup.0 which equals 1. It is understood that other factors .alpha. may also be used. In the case of .alpha. as a power of 2 and .alpha..noteq.1, the thresholds T.sub.p (t) given by Eq. (12) above can be obtained by shifting A.sub.p either left or right using a shifter 36 as in FIG. 1.

The dynamic threshold method has three primary steps which are performed concurrently: maintaining a count of the length of each output port queue; maintaining a set of control thresholds, one for each packet priority level; and regulating the admission of packets to the memory. The length count for an output port queue is updated whenever a packet is written into or read from that output port queue. The process for maintaining control threshold values is illustrated in FIG. 2. This process starts in step 40 whenever the occupancy of the shared memory changes, due to a packet being written into or read out from any output port queue in the shared memory. Step 42 updates the availability value A.sub.p (t) for each packet priority level p, based upon the current total occupancy Q(t) of the shared memory: A.sub.p (t)=B.sub.p -Q(t). Then step 44 computes the control threshold value T.sub.p (t) for each packet priority level p; where the threshold is taken to be a multiple or fraction .alpha. of the current availability value A.sub.p (t):

The method waits at step 46 until the total buffer occupancy changes again, at which time the process continues in step 48 to loop back and continue to update the availability values in step 42.

FIG. 3 illustrates the operation that regulates packet admission. First the method starts operation in step 50, and then an arriving packet is received at an input port in step 52. Then its priority p is determined in step 54, and the output port queue i that the packet would join is determined in step 56. In steps 58 and 60, respectively, the length count Q.sup.i (t) for output port queue i and the control threshold value T.sub.p (t) for priority p are retrieved from the memory, and then these two quantities are compared in step 62. If the comparison is not favorable for admission; i.e. the queue length count equals or exceeds the control threshold value, then the received packet is not admitted to the shared memory in step 66. However, if the comparison is favorable for admission in step 64; i.e. the queue length count is less than the control value, then the received packet is admitted and stored in the appropriate output port queue in step 68. In step 70, the insertion of the packet into its output port queue causes the maintenance steps described above to update the length count for that output port queue and to update the availability values and control thresholds for all priority levels. In step 72, the method prepares to receive more packets by looping back to step 52.

In the exemplary embodiment described above, the disclosed dynamic threshold system and method are illustrated in conjunction with fixed-length ATM packets. In alternative embodiments, the disclosed dynamic threshold system and method may also be used in conjunction with any buffered communications, including systems with fixed packet lengths other than the ATM standard length of 53 bytes and systems with variable-length packets.

In the exemplary embodiment described above, the disclosed dynamic threshold system and method are illustrated for a single-stage switch. In another alternative embodiment, the disclosed dynamic threshold system and method may also be used in conjunction with multi-stage switches formed by connecting single-stage switches with other single-stage switches and/or multiplexers and demultiplexers. Each component single-stage switch or multiplexer or demultiplexer could use the dynamic threshold system and method to manage its own shared memory. For multiplexers, the dynamic thresholds are used to allocate memory among packets received from the competing input ports.

In the exemplary embodiment described above, the disclosed dynamic threshold system and method are illustrated for output port queues. In an additional alternative embodiment, the disclosed dynamic threshold system and method may also be used in a switch with scheduling classes (e.g., delay priority classes). In such a switch, packets destined for the same output port but having different scheduling classes are queued separately. Dynamic thresholds would be used to allocate space among all the scheduling-class queues for all the output ports in the switch.

In the exemplary embodiment described above, the disclosed dynamic threshold system and method are illustrated by blocking admission of all packets to queues over threshold. In further alternative embodiments, the disclosed dynamic threshold system and method may be used in conjunction with other controls such as rate control. Moreover, if a signaling scheme is also included, then such controls may be exercised at any point along the route between the traffic source and the congested switch.

While the disclosed dynamic threshold system and method has been particularly shown and described with reference to the preferred embodiments, it will be understood by those skilled in the art that various modifications in form and detail may be made therein without departing from the scope and spirit of the invention. Accordingly, modifications such as those suggested above, but not limited thereto, are to be considered within the scope of the invention.