Multiple rate sensitive priority queues for reducing relative data transport unit delay variations in time multiplexed outputs from output queued routing mechanisms

• US 6,064,677 A
• Filed: 06/10/1997
• Issued: 05/16/2000
• Est. Priority Date: 06/27/1996
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kappler, Christopher J., Lyles, J. Bryan
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US08/872,327
• Time in Patent Office: 1,071 Days
• Field of Search: 370/230, 370/235, 370/395, 370/397, 370/465, 370/468, 370/412, 370/414, 370/415, 370/416-9
• US Class Current: 370/395.43
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5615 Network termination, e.g. NT1, NT2, PBX
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5625 Operations, administration and maintenance [OAM]
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 49/104 Asynchronous transfer mode [ATM] switching fabrics
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/503 Policing
• CPC Class Codes: H04L 49/505 Corrective measures
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Multiple rate sensitive priority queues reduce relative data transport unit delay variations in time multiplexed from output queued routing mechanisms.

Claims

1. In a packet switched communication system, an apparatus for granting packets of multiple constant bit rate flows time multiplexed, serial access during successive time slots to a shared resource of said system in substantial compliance with individual network traffic contracts for the respective flows, said apparatus comprising:

a queuing mechanism organizing pending packets of active flows in respective queues, with said queues having an oldest pending packet at head of queue order;

a scheduling mechanism coupled to said queuing mechanism, said scheduling mechanism scheduling the oldest pending packets of the respective flows for service at times which are selected in accordance with the respective network traffic contracts for such flows, said scheduling mechanism including a relatively high priority calendar queue and a relatively low priority calendar cueue and said scheduling mechanism preferentially resolving any scheduling conflicts between packets of flows having relatively high and relatively low contractually specified packet emission rates, respectively, in favor of servicing packets of said high emission rate flows first, thereby enforcing a serialized service schedule on the packets of said active flows, while preferentially distributing delay caused by such conflict resolution to the lower emission rate flows; and

a transmit mechanism coupled to said queuing mechanism and to said scheduling mechanism, said transmit mechanism transferring packets of said active flows to said shared resource in accordance with said serialized service schedule, said packets being logically transformed for subsequent operation of said traffic shaper from a pending state to a serviced state upon being transferred to said shared resource.

2. The apparatus of claim 1, wherein said scheduling mechanism further resolves scheduling conflicts by scheduling packets of said high emission rate flows on said relatively high priority calendar aueue and scheduling packets of said low emission rate flows on said relatively low priority calendar queue, whereby said scheduling conflicts are resolved by deferring to said relatively high priority calendar queue.

4. The packet switched communication system of any of claims 1-3 wherein said scheduling mechanism includes a virtual time stamp mechanism for scheduling said packets for service on said calendar queues.

5. The packet switched communication system of claim 4 wherein said packets have a uniform fixed bit length.

6. The packet switched communication system of claim 5 wherein said packets are fixed constant byte length cells for asynchronous transfer mode communications.

3. In a packet switched communication system, a traffic shaper for granting packets of multiple flows time multiplexed, serial access during successive time slots to a shared resource of said system in substantial compliance with individual network traffic contracts for the respective flows;

said traffic contracts establishing respective nominal rates and associated tolerances of specified strictness for said flows;

said traffic shaper comprising

a queuing mechanism for organizing pending packets of active flows in respective queues, with each of said queues having an oldest pending packet at head of queue order;

a scheduling mechanism coupled to said queuing mechanism for scheduling the oldest pending packets of the respective flows for service at times which are selected in accordance with the respective network traffic contracts for such flows;

said scheduling mechanism including a relatively high priority calendar queue and a relatively low priority calendar queue;

where packets of flows having relatively strict tolerances on their contractually established nominal rates are scheduled on said high priority calendar queue, and packets of flows having relatively loose tolerances on their contractually established nominal rates are scheduled on said low priority calendar queue, whereby any scheduling conflicts are resolved by deferring to said high priority queue to enforce a serialized service schedule on the packets of said active flows, while distributing delay caused by such conflict resolution to flows having relatively loose tolerances;

said high priority calendar queue having a relatively fine resolution to accommodate the scheduling of packets of flows having relatively tight tolerances to a precision which is on the order of a single one of said time slots; and

said low priority calendar queue having a coarser resolution to accommodate a less precise scheduling of packets of flows having a relatively loose tolerance

a transmit mechanism coupled to said queuing mechanism and to said scheduling mechanism for transferring packets of said active flows to said shared resource in accordance with said serialized service schedule, said packets being logically transformed for subsequent operation of said traffic shaper from a pending state to a serviced state upon being transferred to said shared resource.