Method and apparatus for guaranteeing a minimum cell rate (MCR) for asynchronous transfer mode (ATM) traffic queues

• US 6,822,939 B2
• Filed: 05/20/2002
• Issued: 11/23/2004
• Est. Priority Date: 05/20/2002
• Status: Expired due to Term

• Current Assignee: F Poszat Hu LLC (Intellectual Ventures LLC), Syntheon LLC
• Original Assignee: Transwitch Corporation
• Inventors: Novick, Ronald P.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Hyun, Soon-Dong
• Application Number:
  US10/151,617
• Publication Number:
  US 20030214952A1
• Time in Patent Office: 918 Days
• Field of Search: 370/230, 370/230.1, 370/232-234, 370/235, 370/235.1, 370/236, 370/395.1, 370/395.4, 370/395.41, 370/395.42, 370/395.43, 370/395.61, 370/412, 370/413, 370/414, 370/418, 370/468
• US Class Current: 370/230.1
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• 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/566 Deadline varies as a function of time spent in the queue
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

An apparatus for guaranteeing MCR in an ATM device includes at least one queue for each service category, a scheduler for dequeuing cells from the queues, a queue status block for indicating which queues are empty, and an MCR service block. The MCR service block includes a plurality of timers, at least one for each service category. According to the methods of the invention, an MCR value is selected for each queue (or service category) and a timer in the MCR service block is set according to the MCR value. The scheduler dequeues cells in strict priority from non-empty queues as determined by the queue status block. The scheduler is preempted, however, by the MCR service block when a queue fails to be serviced before its associated timer expires. The arrangement of queues and associated timers is subject to alternate embodiments.

Claims

1. An apparatus for guaranteeing minimum cell rate (MCR) in an asynchronous transfer mode (ATM) device, said apparatus comprising:

a) a first plurality of queues, at least one for each service category;

b) a scheduler coupled to said queues for dequeuing cells from said queues in order of priority;

c) at least one timer associated with at least one of said queues; and

d) preemption means coupled to said at least one timer and to said scheduler for preempting said scheduler, wherein

said preemption means always causes said scheduler to dequeue a cell from said at least one queue associated with said at least one timer whenever said at least one timer expires if a cell from said at least one queue associated with said at least one timer is not dequeued by said scheduler before said timer expires.

2. An apparatus according to claim 1, wherein:

said at least one timer includes at least one timer for each class of service.

3. An apparatus according to claim 1, wherein:

said preemption means includes an MCR service register for indicating which queues are to be serviced when said at least one timer expires.

4. An apparatus according to claim 1, wherein:

said preemption means includes at least one queue service register for indicating which queues have been serviced.

5. An apparatus according to claim 2, wherein:

said preemption means includes a queue service register associated with each timer for indicating which queues have been serviced before the timer expires.

6. An apparatus according to claim 2, wherein:

said preemption means includes an MCR service register for indicating which queues are to be serviced when a timer expires.

7. An apparatus according to claim 4, wherein:

said preemption means includes an MCR service register for indicating which queues are to be serviced when a timer expires.

8. An apparatus according to claim 5, wherein:

said preemption means includes an MCR service register for indicating which queues are to be serviced when a timer expires.

9. A method for guaranteeing minimum cell rate (MCR) in an asynchronous transfer mode (ATM) device, said method comprising:

a) establishing at least one queue for each service category;

b) dequeuing cells from the queues in order of priority;

c) establishing at least one timer associated with at least one of said queues; and

d) always dequeuing a cell from the at least one queue associated with the at least one timer whenever the at least one timer expires if no cells have been dequeued from the at least one queue associated with the at least one timer before the timer expires.

10. A method according to claim 9, wherein:

said step of establishing at least one timer includes establishing at least one timer for each class of service.

11. A method according to claim 9, further comprising:

e) establishing an MCR service register for indicating which queues are to be serviced when the at least one timer expires.

12. A method according to claim 9, further comprising:

e) establishing at least one queue service register for indicating which queues have been serviced.

13. A method according to claim 10, further comprising:

e) establishing a queue service register associated with each timer for indicating which queues have been serviced before the timer expires.

14. A method according to claim 10, further comprising:

e) establishing an MCR service register for indicating which queues are to be serviced when a timer expires.

15. A method according to claim 11, further comprising:

f) establishing at least one queue service register for indicating which queues have been serviced.

16. A method according to claim 13, further comprising:

f) establishing an MCR service register for indicating which queues are to be serviced when a timer expires.