Methods and apparatus for the fair allocation of bandwidth among MCR and best effort service connections in an ATM switch

• US 6,980,513 B2
• Filed: 09/24/2001
• Issued: 12/27/2005
• Est. Priority Date: 09/24/2001
• Status: Expired due to Fees

• Current Assignee: TR Technologies Foundation LLC (Intellectual Ventures LLC)
• Original Assignee: Transwitch Corporation
• Inventors: Novick, Ronald P.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Wong, Blanche
• Application Number:
  US09/961,837
• Publication Number:
  US 20030058869A1
• Time in Patent Office: 1,555 Days
• Field of Search: 370/395.4, 370/395.41, 370/395.42, 370/395.43, 370/412, 370/468, 370/230, 370/230.1, 370/252, 370/253
• US Class Current: 370/230
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/20 Support for services
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction

Abstract

Methods for allocating bandwidth among MCR and best effort connections include listing MCR connections in an MCR service list and best efforts connection in a best efforts (BE) service list. Assigning an MCR value to each MCR connection and setting a Cell Count Register (CCR) with it. During a service interval, dequeueing each MCR connection queue in round robin fashion according to the MCR service list and decrementing the associated CCR. If the CCR reaches zero before the end of the service interval and there are still cells in the queue, the connection is moved from the MCR service list to the BE service list for the remainder of the service interval. If the CCR reaches zero before the end of the service interval and/or there are no cells remaining in the queue, the connection is removed from the MCR service list. If all of the cell counts reach zero and/or if all of the MCR queues become empty before the end of the service interval, the connections on the BE service list are serviced by a separate scheduler. At the end of the service interval, the CCRs are reinitialized and the MCR connections which were moved to the BE service list are moved back to the MCR service list.

Claims

1. A method for allocating bandwidth among minimum cell rate (MCR) connections and best effort connections in an ATM switch, said method comprising:

a) associating each MCR connection with an individual queue;

b) associating each queue with a cell count register and a MCR register;

c) setting the values of the MCR registers based on guaranteed bandwidth of all the MCR connections and the presently available bandwidth of the associated port in the switch;

d) setting the values of each cell count register based on its associated MCR register value;

e) listing all of the MCR connection queues in an MCR service list;

f) dequeuing cells from the MCR connection queues in a round robin fashion according to the MCR service list during a service interval;

g) decrementing cell count registers as associated queues are dequeued; and

h) removing MCR connection queues from the MCR service list when the queues become empty or the cell count register for the queue goes to zero during the service interval whichever occurs first.

2. A method according to claim 1, further comprising:

i) listing all of the best efforts connections in a best effort service list; and

j) moving MCR connection queues from the MCR service list to the best effort service list for the duration of a service interval if the MCR connection queue is not empty but its cell count register goes to zero during the service interval.

3. A method according to claim 2, further comprising:

k) servicing the queues in the best effort service list during the remaining portion of the service interval after all of the MCR queue cell count registers have gone to zero.

4. A method according to claim 3, further comprising:

l) after the service interval expires, resetting the cell count registers and repeating steps a–

k.

5. A method according to claim 4, wherein:

said step of resetting the cell count registers includes adding the associated MCR register value to the value remaining in the cell count register at the end of the last service interval.

6. A method according to claim 4, wherein:

said step of resetting the cell count registers is performed for each cell count register the first time the queue associated with the cell count register is serviced in a service interval.

7. An apparatus for allocating bandwidth among minimum cell rate (MCR) and best effort connections in an ATM switch, said apparatus comprising:

a) a plurality of MCR queues, one for each active MCR connection;

b) a plurality of cell count register, one for each MCR queue;

c) a plurality of MCR registers, one for each MCR queue;

d) an MCR scheduler coupled to said queues and said registers;

e) an MCR service list coupled to said MCR scheduler, wherein

said MCR scheduler sets the values of the MCR registers based on guaranteed bandwidth of all active MCR connections and presently available bandwidth in the switch,

said MCR scheduler sets the values of each cell count register based on its associated MCR register value;

said MCR scheduler lists all of the MCR connection queues in the MCR service list;

said MCR scheduler dequeues cells from the MCR connection queues in a round robin fashion according to the MCR service list during a service interval;

said MCR scheduler decrements cell count registers as associated queues are dequeued; and

said MCR scheduler removes MCR connection queues from the MCR service list when the queue becomes empty or the cell count register for the queue goes to zero during the service interval whichever occurs first.

8. An apparatus according to claim 7, further comprising:

i) a best effort service list coupled to said MCR scheduler, wherein

said MCR scheduler moves MCR connection queues from the MCR service list to the best effort service list for the duration of a service interval if the MCR connection queue is not empty but its cell count register goes to zero during the service interval.

9. An apparatus according to claim 8, wherein:

said MCR scheduler indicates servicing the queues in the best effort service list during the remaining portion of the service interval after all of the MCR queue cell count registers have gone to zero.

10. An apparatus according to claim 8, wherein:

after the service interval expires, the MCR scheduler resets the cell count registers and begins a new service interval.

11. An apparatus according to claim 10, wherein:

said MCR scheduler resets the cell count registers by adding the associated MCR register value to the value remaining in the cell count register at the end of the last service interval.

12. An apparatus according to claim 10, wherein:

said MCR scheduler resets each cell count register the first time the queue associated with the cell count register is serviced in a service interval.

13. A method for allocating bandwidth among high priority connections and low priority connections in a packet switch, said method comprising:

a) associating each high priority connection with an individual queue;

b) associating each queue with a packet count register and a minimum packet rate register;

c) setting the values of the minimum packet rate registers based on guaranteed bandwidth of all the high priority connections and the presently available bandwidth of the associated port in the switch;

d) setting the values of each packet count register based on its associated minimum packet rate register value;

e) listing all of the high priority connection queues in a high priority service list;

f) dequeuing packets from the high priority connection queues in a round robin fashion according to the high priority service list during a service interval;

g) decrementing packet count registers as associated queues are dequeued; and

h) removing high priority connection queues from the high priority service list when the queues become empty or the packet count register for the queue goes to zero during the service interval whichever occurs first.