Rate shaping in per-flow output queued routing mechanisms for unspecified bit rate service

• US 6,377,583 B1
• Filed: 06/11/1997
• Issued: 04/23/2002
• 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: Lyles, J. Bryan, Rogers, Landis C., Kappler, Christopher J.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Lee, Andy
• Application Number:
  US08/872,906
• Time in Patent Office: 1,777 Days
• Field of Search: 370/229, 370/230, 370/233, 370/235, 370/236, 370/412, 370/413, 370/414, 370/416, 370/395, 370/428, 370/429, 370/465, 370/230.1, 370/235.1, 370/395.1, 370/395.2, 370/395.21, 370/395.4, 370/395.41, 370/395.43, 370/468
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

This invention provides rate shaping in per-flow output queued routing mechanisms for unspecified bit rate service.

Claims

1. A traffic shaper in a packet switched communication system for shaping a plurality of time multiplexed serial flow of packets to corresponding unspecified bit rate network traffic contracts where the traffic contracts defines a peak packet emission rate, the traffic shaper comprising:

a work conserving calendar queue for queuing entries for transmission from said packet switched communication system in a work-conserving manner;

a non-work conserving calendar queue for queuing entries for transmission from said packet switched communication system in a non work-conserving manner; and

,

a scheduler enqueuing packets of the given flow (i) on said work conserving calendar queue when a rate at which the packets are emitted from the traffic shaper is compliant with the unspecified bit rate traffic contract for the given flow, and (ii) on said non-work conserving calendar queue at a rate that is less than or substantially equal to the peak packet emission rate when the rate at which the packets are emitted from the traffic shaper is non-compliant with the unspecified bit rate traffic contract for the given flow.

2. The traffic shaper of claim 1, wherein said work conserving calendar queue and said non-work conserving calendar queue are dynamically reallocated segments of a real time indexed data structure, said real-time indexed data structure being indexed by a pointer that cyclically traverses said real-time indexed data structure as a function of real time.

3. The traffic shaper of claim 2, wherein packets of the given flow have a uniform, fixed bit length.

4. The traffic shaper of claim 1, wherein packets of the given flow are dequeued from said work conserving calendar queue in approximate round robin order with respect to the flows that have packets enqueued thereon.

5. The traffic shaper of claim 4, wherein packets of the given flow are fixed byte length cells for asynchronous transfer mode communications.

6. The traffic shaper of claim 1, wherein each of said packets is referenced by a pointer to said packet, and the scheduler enqueues said packets on said work conserving calendar queue and said non-work conserving calendar queue by placing an entry to said pointer in one of said queues.

7. A traffic shaper in a packet switched communication system for shaping a plurality of time multiplexed serial flow of packets to corresponding unspecified bit rate network traffic contracts where the traffic contracts defines a peak packet emission rate, the traffic shaper comprising:

a work conserving calendar queue for queuing entries for transmission from said packet switched communication system in a work-conserving manner;

a non-work conserving calendar queue for queuing entries for transmission from said packet switched communication system in a non work-conserving manner; and

,

a scheduler for enqueuing packets of the given flow by placing pointers to said packets (i) on said work conserving calendar queue when a rate at which the packets are emitted from the traffic shaper is compliant with the unspecified bit rate traffic contract for the given flow, and (ii) on said non-work conserving calendar queue when the rate at which the packets are emitted from the traffic shaper is non-compliant with the unspecified bit rate traffic contract for the given flow.

8. The traffic shaper of claim 7 wherein the scheduler enqueues packets on said non-work conserving queue at a rate that is less than or substantially equal to the peak packet emission rate.

9. A switch for a packet switched communication system including a traffic shaper for serially emitting packets of multiple time multiplexed flows in substantial compliance with individual network traffic contracts for the respective flows, at least one of said traffic contracts specifying an unspecified bit rate network traffic contracts, where the unspecified bit rate network traffic contracts defines a peak packet emission rate, the switch comprising:

a work conserving calendar queue for queuing entries for transmission from said packet switched communication system in a work-conserving manner;

a non-work conserving calendar queue for queuing entries for transmission from said packet switched communication system in a non work-conserving manner;

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

,

a scheduling mechanism coupled to said queuing mechanism, for scheduling pending packets of the respective flows by placing pointers to said packets (i) on said work conserving calendar queue when a rate at which the packets are to be emitted from the switch is compliant with an unspecified bit rate traffic contract for the given flow, and (ii) on said non-work conserving calendar queue when the rate at which the packets are to be emitted from the switch is non-compliant with said unspecified bit rate traffic contract for the given flow.

10. The switch of claim 9 wherein the rate at which the packets are to be emitted from the switch is compliant with an unspecified bit rate traffic contract when the Generic Cell Rate Algorithm test for said rate is false.

11. The switch of claim 9 wherein said pending packets are scheduled on said non-work conserving calendar queue according to a peak cell rate emission interval.

12. The switch of claim 9, wherein said work conserving calendar queue and said non-work conserving calendar queue are dynamically reallocated segments of a real time indexed data structure, said real-time indexed data structure being indexed by a pointer that cyclically traverses said real-time indexed data structure as a function of real time.

13. The switch of claim 10, wherein packets of the given flow have a uniform, fixed bit length.

14. The switch of claim 9, wherein packets of the given flow are dequeued from said work conserving calendar queue in approximate round robin order with respect to the flows that have packets enqueued thereon.

15. The switch of claim 12, wherein packets of the given flow are fixed byte length cells for asynchronous transfer mode communications.

16. The switch of claim 9, wherein each of said packets is referenced by a pointer to said packet, and the scheduler enqueues said packets on said work conserving calendar queue and said non-work conserving calendar queue by placing an entry to said pointer in one