Shared credit round robin queuing

Details Shared credit round robin queuing Shared credit round robin queuing

2000-03-31

2004-01-27

Hsu, Alpus H. (Department: 2665)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S417000

Reexamination Certificate

active

06683884

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention generally relates to the field of data communication networks. More particularly, the present invention relates to a novel system and method for ensuring bandwidth to different classes of traffic, limiting the classes of traffic to corresponding maximum bandwidths, and dynamically allocating bandwidth to classes needing more than their maximum bandwidth when there exists available bandwidth.
2. Description of Related Art
Most commercial communication networks incorporate network switching devices, such as computer switches or routers, for example, to aggregate streams of data onto a network link and funnel the data traffic to its destination. These switching devices typically employ queuing methodologies to manage the flow of data streams onto the network link. For very high-speed network links, it is important that queuing methodologies be computationally simple so that the switch or router does not become a bottleneck. One such methodology is the Deficit Round Robin (DRR) technique (M. Shreedhar and G. Varghese,
Efficient Fair Queuing Using Deficit Round Robin
, Washington University, St. Louis, Mo. (Oct. 16, 1995)). DRR was designed to ensure that each class of traffic being transmitted out of a particular network device output port receives a user-selectable percentage of the port's bandwidth.
FIG. 1
illustrates a representative system
100
, employing DRR. As indicated in
FIG. 1
, a plurality of input streams of packetized data, representing different classes of traffic, flow into the output port
105
of a network switching device. These streams are captured by queues
110
A-
110
M. As packets enter queues
110
A-
110
M, their lengths are stored in a manner that enables the queue servicing algorithm to quickly obtain the length of the packet from the head packet of each queue. The user assigns each of the queues
110
A-
110
M a “quantum” number of bytes, based on the class of traffic of each queue. The ratio of each of the queue's
110
A-
110
M quantum to the total of all quanta represents the fraction of port bandwidth that each queue should receive. For example, queue
110
A may represent a lower class of traffic and may be allocated a quantum of 500 bytes while queue
110
B may represent a higher class and may be allocated a quantum of 1000 bytes. Queue
110
C may represent an even higher class of traffic and may be allocated a quantum of 2000 bytes. If the total of all quanta is 10,000 bytes, then queue
110
A should receive at least 500/10,000, or 5% of the output bandwidth. Likewise, queue
110
B should receive 10% and
110
C 20% of the bandwidth.
DRR incorporates “deficit counters”
120
A-
120
M, which track how many bytes a queue may send. During an initialization stage, deficit counters
120
A-
120
M are initialized to zero. During operation, DRR examines each of the queues
110
A-
110
M in a round-robin fashion (i.e., returning to the first queue
110
A after the final queue
110
M has been observed). If there are no packets in the queue being examined, then that queue is skipped and the next queue is examined. If a queue, for example queue
110
C, has at least one packet to send, then the quantum corresponding to queue
110
C is added to its deficit counter
120
C. DRR then compares the length of the head packet of queue
110
C, with the number of bytes in deficit counter
120
C. If the length is less than or equal to deficit counter
120
C, the packet is dequeued and transmitted while deficit counter
120
C is decremented by the byte length of the packet. DRR then examines queue
110
C again to determined whether there exists another packet in queue
110
C, whose length is less than the number of bytes contained in deficit counter
120
C. If so, the packet is dequeued, transmitted, and deficit counter
120
C decremented.
This process is repeated until there are either no packets in queue
110
C or the length of the packet at the head of queue
110
C is greater than the number of bytes contained in deficit counter
120
C. If there are no packets in queue
110
C, deficit counter
120
C is set to zero and the next queue is examined.
It is to be noted, however, that there are situations in which one queue may need more than its allocated target bandwidth while other queues are dormant. There are other situations where it may be desirable to ensure a predetermined bandwidth to a queue while enabling it to operate at a higher bandwidth if there exists available bandwidth.
What is needed, therefore, is a method and system that ensures bandwidth to different classes of traffic, limits the classes of traffic to a maximum bandwidth, and enables pre-selected classes to use more than their maximum bandwidth when there is bandwidth available.


REFERENCES:
patent: 5905730 (1999-05-01), Yang et al.
patent: 5995511 (1999-11-01), Zhou et al.
patent: 6041040 (2000-03-01), Beshai et al.
patent: 6247061 (2001-06-01), Douceur et al.
patent: 6359861 (2002-03-01), Sui et al.
“Efficient Fair Queuing using Deficit Round Robin,” Shreedhar et al., Oct. 16, 1995, Washington University, St. Louis, MO, pp. 1-22.
“Link-sharing and Resource Management Models for Packet Networks,” Floyd et al., IEEE/ACM Transactions on Networking, vol. 3, No. 4, Aug. 1995, pp. 1-22.

Affiliated with

Also associated with

Rating

Shared credit round robin queuing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Shared credit round robin queuing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shared credit round robin queuing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3193546