Method and system for traffic control

• US 6,947,996 B2
• Filed: 01/29/2001
• Issued: 09/20/2005
• Est. Priority Date: 01/29/2001
• Status: Expired due to Fees

• Current Assignee: Seabridge Ltd. (Siemens AG)
• Original Assignee: Seabridge Ltd. (Siemens AG)
• Inventors: Assa, Eyal, Berechya, David
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/771,906
• Publication Number:
  US 20020147829A1
• Time in Patent Office: 1,695 Days
• Field of Search: 709/232, 370230-234
• US Class Current: 709/232
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 41/082 the condition being updates or upgrades of network functionality
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/568 Calendar queues or timing rings
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A traffic control method and system are disclosed for scheduling fixed size traffic elements from a number of queues for transmission on a link. Each queue has associated traffic parameters. The system comprises a scheduler and a calendar in a memory for storing a transmission schedule of the queues. The scheduler shapes the transmission schedule by updating the schedule in the calendar in dependence on inputted traffic parameters of each queue. The system also includes an amplifier to amplify the traffic parameters by a factor K prior to input to the scheduler, the scheduler and calendar being adapted to operate using the amplified parameters.

Claims

1. A traffic shaping device or use in packet switched communication system for scheduling fixed size traffic elements from a number of queues for transmission on a link, each queue having associated traffic parameters, the system comprising a scheduler and a calendar in a memory for storing a transmission schedule of the queues, the scheduler shaping the transmission schedule by updating the schedule in the calendar in dependence on inputted traffic parameters of each queue, wherein the system includes an amplifier to amplify traffic-rate related parameters by a factor K prior to input to the scheduler, the scheduler and calendar being adapted to operate using amplified parameters.

2. A traffic shaping device according to claim 1, further comprising a parameter memory arranged to store the amplified parameters as integers for input to the scheduler.

3. A traffic shaping device according to claim 2, in which the traffic-rate related parameters include quality of service parameters.

4. A traffic shaping device according to claim 2, in which the transmission schedule for a respective queue is updated after a transmission from the queue.

5. A traffic shaping device according to claim 4, in which the calendar comprises a linear array having a number of indices, each index corresponding to a transmission time and being capable of referencing a list of queues, queues referenced by a low value index being transmitted before queues referenced by a higher value index, wherein the updating of the transmission schedule comprises recalculation of the index to refer to the queue.

6. A traffic shaping device according to claim 5, in which the scheduler recalculates the index using leaky bucket shaping.

7. A traffic shaping device according to claim 6, in which the scheduler uses single leaky bucket shaping for queues having CBR class traffic.

8. A traffic shaping device according to claim 7, in which the traffic-rate related parameters comprise the inverse of respective queue'"'"'s peak cell rate (1/PCR) and queue'"'"'s cell delay variation tolerance (CDVT), the parameters being calculated as:

$I=\mathrm{Integer}<br><br>\left\{\frac{\mathrm{LinkPCR}<br><br>\left[\mathrm{cells}/s\right]}{\mathrm{QPCR}<br><br>\left[\mathrm{cells}/s\right]}*K\right\}$ 

L=Integer{CDVT[sec]*LinkPCR*K},

where LinkPCR is the PCR of the link and QPCR is the PCR of the respective queue.

9. A traffic shaping device according to claim 6, in which the scheduler uses dual leaky bucket shaping for queues having VBR class traffic.

10. A traffic shaping device according to claim 9, in which the traffic-rate related parameters for the first leaky bucket comprise the inverse of the respective queue'"'"'s peak cell rate (1/PCR) and the queue'"'"'s cell delay variation tolerance (CDVT), the parameters being calculated as:

$I=\mathrm{Integer}<br><br>\left\{\frac{\mathrm{LinkPCR}<br><br>\left[\mathrm{cells}/s\right]}{\mathrm{QPCR}<br><br>\left[\mathrm{cells}/s\right]}*K\right\}$ 

L=Integer{CDVT[sec]*LinkPCR*K},

and the traffic-rate related parameters for the second leaky bucket comprise the inverse of the respective queue'"'"'s sustainable cell rate (1/SCR) and the sum of the queue'"'"'s cell delay variation tolerance (CDVT) and burst tolerance(BT), the parameters being calculated as;

$I=\mathrm{Integer}<br><br>\left\{\frac{\mathrm{Link}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{PCR}<br><br>\left[\mathrm{cells}<br><br>\text{/}<br><br>s\right]}{Q<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{PCR}<br><br>\left[\mathrm{cells}<br><br>\text{/}<br><br>s\right]}*K\right\}$ 

L=Integer{BT[sec]*LinkPCR*K}+Integer{CDVT[sec]*LinkPCR*K}

where LinkPCR is the PCR of the link and QPCR is the PCR of the respective queue.

11. A traffic shaping device according to claim 5, further comprising a transmitter arranged to traverse the array from lowest index to highest traversing one index per transmission time, wherein the transmitter allows a queue to transmit if it is referenced by the index currently traversed.

12. A traffic shaping device according to claim 11, in which recalculation of the index results in the reference to the queue being moved to an index with a higher value.

13. A traffic shaping device according to claim 12, in which a recalculation resulting in an index value greater than the maximum index of the array is adjusted so as to wrap around the array.

14. A traffic shaping device according to claim 13, further comprising a memory for storing the number of transmission times passed since each queue'"'"'s last transmission, the value being used as a traffic-rate related parameter input to the scheduler.

15. A traffic shaping device according to claim 1, comprising a Field Programmable Gate Array (FPGA).

16. A traffic shaping device according to claim 1, comprising an application specific integrated circuit (ASIC).

17. A traffic shaping method scheduling fixed size traffic elements from a number of queues for transmission on a link, each queue having associated traffic parameters, the method comprising the steps of:

storing a transmission schedule of the queues in a memory; and

shaping the transmission schedule by updating the schedule in the calendar in dependence on inputted traffic parameters of each queue;

wherein the step of shaping includes the step of amplifying traffic-rate related parameters by a factor K, the memory and the shaping step being adapted to operate using amplified parameters.

18. A traffic shaping method according to claim 17, in which the amplified parameters are truncated as integers.

19. A traffic shaping method according to claim 17, in which the traffic-rate related parameters include quality of service parameters.

20. A traffic shaping method according to claim 17, in which the transmission schedule for a respective queue is updated after a transmission from the queue.

21. A traffic shaping method according to claim 17, in which the transmission schedule comprises a linear array having a number of indices, each index corresponding to a transmission time and being capable of referencing a list of queues, queues referenced by a low value index being transmitted before queues referenced by a higher value index, wherein the step of shaping includes the step of recalculating the value of the index that should refer to the queue.

22. A traffic shaping method according to claim 21, in which the step of shaping comprises leaky bucket shaping.

23. A traffic shaping method according to claim 22, in which single leaky bucket shaping is used for queues having CBR class traffic.

24. A traffic shaping method according to claim 23, in which the traffic-rate related parameters comprise the inverse of respective queue'"'"'s peak cell rate (1/PCR) and queue'"'"'s cell delay variation tolerance (CDVT), the parameters being calculated as:

$I=\mathrm{Integer}<br><br>\left\{\frac{\mathrm{Link}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{PCR}<br><br>\left[\mathrm{cells}<br><br>\text{/}<br><br>s\right]}{\mathrm{QPCR}<br><br>\left[\mathrm{cells}<br><br>\text{/}<br><br>s\right]}*K\right\}$ 

L=Integer{CDVT[sec]*LinkPCR*K},

where LinkPCR is the PCR of the link and QPCR is the PCR of the respective queue.

25. A traffic shaping method according to claim 22, in which dual leaky bucket shaping is used for queues having VBR class traffic.

26. A traffic shaping method according to claim 25, in which the traffic-rate related parameters for the first leaky bucket comprise inverse of the respective queue'"'"'s peak cell rate (1/PCR) and queue'"'"'s cell delay variation tolerance (CDVT), the parameters being calculated as:

$I=\mathrm{Integer}<br><br>\left\{\frac{\mathrm{Link}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{PCR}<br><br>\text{\hspace{1em}<br><br>}\left[\mathrm{cells}<br><br>\text{/}<br><br>s\right]}{Q<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{PCR}<br><br>\text{\hspace{1em}<br><br>}\left[\mathrm{cells}<br><br>\text{/}<br><br>s\right]}*K\right\}$ 

L=Integer{CDVT[sec]*LinkPCR*K},

and the traffic-rate related parameters for the second leaky bucket comprise the inverse of the respective queue'"'"'s sustainable cell rate (1/SCR) and the sum of the queue'"'"'s cell delay variation tolerance (CDVT) and burst tolerance(BT), the parameters being calculated as;

$I=\mathrm{Integer}<br><br>\left\{\frac{\mathrm{Link}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{PCR}<br><br>\text{\hspace{1em}<br><br>}\left[\mathrm{cells}<br><br>\text{/}<br><br>s\right]}{Q<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{PCR}<br><br>\text{\hspace{1em}<br><br>}\left[\mathrm{cells}<br><br>\text{/}<br><br>s\right]}*K\right\}$ 

L=Integer{BT[sec]*LinkPCR*K}+Integer {CDVT[sec]*LinkPCR*K}

where LinkPCR is the PCR of the link and QPCR is the PCR of the respective queue.

27. A traffic shaping method according to claim 21, further comprising the step of traversing the array from the lowest index to the highest, traversing one index per transmission time, further comprising the step of allowing a queue to transmit if it is referenced by the index currently traversed.

28. A traffic shaping method according to claim 27, in which recalculation of the index results in the reference to the queue being moved to an index with a higher value.

29. A traffic shaping method according to claim 28, in which a recalculation resulting in an index value greater than the maximum index of the array is adjusted so as to wrap around the array.

30. A traffic shaping method according to claim 29, further comprising the step of storing the number of transmission times passed since each queue'"'"'s last transmission, the value being used as a traffic-rate related parameter input.

31. A computer-readable medium, on which is stored a computer program of instructions for a processor for use in a packet switched communication system to schedule fixed size traffic elements from a number of queues for transmission on a link, each queue having associated traffic parameters, the program comprising, in combination:

means for causing the processor to store a transmission schedule of the queues in a memory; and

means for causing the processor to shape the transmission schedule by updating the schedule in the calendar in dependence on inputted traffic parameters of each queue;

wherein the means for causing the processor to shape the schedule includes means for amplifying in the memory traffic-rate related parameters by a factor K, the means for causing the processor to shape the schedule being adapted to operate using amplified parameters.

32. A field programmable gate array for use in a packet switched communication system programmed to execute scheduling of fixed size traffic elements from a number of queues for transmission on a link, each queue having associated traffic parameters, the program comprising the steps of:

storing a transmission schedule of the queues in a memory; and

shaping the transmission schedule by updating the schedule in the calendar in dependence on inputted traffic parameters of each queue;

wherein the step of shaping includes the step of amplifying traffic-rate related parameters by a factor K, the memory and the shaping step being adapted to operate using amplified parameters.

33. An application specific integrated circuit for use in a packet switched communication system configured to execute scheduling of fixed size traffic elements from a number of queues for transmission on a link, each queue having associated traffic parameters, the program comprising the steps of:

storing a transmission schedule of the queues in a memory; and

shaping the transmission schedule by updating the schedule in the calendar in dependence on inputted traffic parameters of each queue;

wherein the step of shaping includes the step of amplifying traffic-rate related parameters by a factor K, the memory and the shaping step being adapted to operate using amplified parameters.