Weighted round robin engine used in scheduling the distribution of ATM cells

• US 6,434,155 B1
• Filed: 12/22/1999
• Issued: 08/13/2002
• Est. Priority Date: 12/22/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel USA Sourcing L.P. (Nokia Corporation)
• Inventors: Nelson, Michael, Jones, James W.
• Primary Examiner(s): Yao, Kwang Bin
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/469,583
• Time in Patent Office: 965 Days
• Field of Search: 370/398, 370/230-236, 370/412-414, 370/229, 370/503, 370/517, 370/319, 370/328, 370/443, 370/348, 709/226
• US Class Current: 370/398
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5646 Cell characteristics, e.g. loss, delay, jitter, sequence integrity
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/562 Attaching a time tag to queues
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A weighted round robin (WRR) engine includes components to arbitrate emission of ATM cells assigned to different flows. In one embodiment termed an inter-QoS WRR, the flows are linked to quality of service (QoS) parameters. A tag value is further assigned to each QoS parameter. Whenever the QoS is selected by the Inter-QoS WRR to have a flow emit an ATM cell, the tag value for the QoS is incremented by a weight assigned to the QoS. The QoS selected by the Inter-QoS WRR is the QoS with the lowest tag. If two or more QoSs are tied with the lowest tag, the highest numbered QoS is selected by the WRR.

Claims

1. A weighted round robin (WRR) engine process for arbitrating emission of asynchronous transfer mode (ATM) cells identified by flows, wherein each of the flows has a tag and a rate limiting increment (I), the process comprising the steps of:

identifying one of the flows for emitting an ATM cell which is linked first in a chain;

adding the increment (I) assigned to the one flow identified for emission to its tag value; and

relinking flows in the chain based on their relative tag value.

2. A method of scheduling emission of asynchronous transfer mode (ATM) cells from an ATM cell queuing device comprising the steps of:

linking flows to time descriptors of a port shaper, wherein the flows each identify at least one of the ATM cells;

sequentially activating the time descriptors of the port shaper;

emitting one of the ATM cells identified by a given flow, and relinking the given flow from the active time descriptor to a subsequent time descriptor based on a weight assigned to the flow when the given flow is linked alone to the active time descriptor; and

submitting a weighted round robin (WRR) process request to arbitrate emission of ATM cells when multiple given ones of the flows are linked to the active time descriptor, wherein the given flows are linked to QoS indicators, the WRR process comprising the steps of;

comparing tag values assigned to the QoS indicators, and if one of the QoS indicators has the lowest tag value of the tag values assigned to the QoS indicators, identifying the one QoS indicator for providing an ATM cell for emitting an ATM cell;

identifying a given one of a number-of the QoS indicators with a highest QoS value for emitting an ATM cell when tag values assigned to the number of QoS indicators are tied for having the lowest tag value; and

adding a weight assigned to the QoS identified for emitting an ATM cell to its tag value.

3. A method of scheduling emission of asynchronous transfer mode (ATM) cells from an ATM cell queuing device comprising the steps of:

linking flows to time descriptors of a port shaper, wherein the flows each identify at least one of the ATM cells;

sequentially activating the time descriptors of the port shaper;

emitting one of the ATM cells identified by a given flow, and relinking the given flow from the active time descriptor to a subsequent time descriptor based on a rate limiting increment assigned to the flow when the given flow is linked alone to the active time descriptor; and

submitting a weighted round robin (WRR) process request to arbitrate emission of ATM cells when multiple given ones of the flows are linked in a chain to the active time descriptor, wherein the given flows has a tag and a rate limiting increment, the WRR process comprising the steps of;

identifying one of the flows for emitting an ATM cell which is linked first in the chain;

adding the rate limiting increment assigned to the one flow identified for emission to its tag value; and

relinking flows in the chain based on their relative tag value.