Method and apparatus for performing high-speed traffic shaping

• US 6,950,400 B1
• Filed: 06/12/2001
• Issued: 09/27/2005
• Est. Priority Date: 04/27/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Systems, Inc.
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Tran, Christina H., Chen, Yan-ming, Lin, Yichou, Edsall, Thomas J., Gai, Silvano, Ullum, Daniel R.
• Primary Examiner(s): Ho, Duc
• Assistant Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US09/879,553
• Time in Patent Office: 1,568 Days
• Field of Search: 370/230.1, 370/236, 370/252, 370/395.4, 370412-428, 709/206, 711/108, 713/502, 365/189.07, 365/49, 710/37, 710/60
• US Class Current: 370/236
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping

Abstract

A network traffic shaper provides high-speed, multi-level shaping. The traffic shaper is in communicating relationship with a forwarding engine, and includes a queue controller having a plurality of queues for storing messages, a scheduler for computing release times, at least one time-searchable memory and a corresponding memory controller. Each queue is preferably associated with a corresponding traffic specifier, and a release time is computed for each queue and stored in the time-searchable memory. When a stored release time expires, the message at the head of the corresponding queue is retrieved and is either moved into a different queue or forwarded by the network device. By moving messages through two or more queues, each having its own release time computed in response to a different traffic specifier, the traffic shaper can perform multi-level shaping on network messages.

Claims

1. A traffic shaper for use in determining transmission start times for network messages, the traffic shaper comprising:

a plurality of queues for storing information relating to the network messages;

a queue controller operably coupled to the plurality of queues for storing the information in and retrieving the information from the plurality of queues;

a scheduler in communicating relationship with the queue controller, the scheduler configured to compute release times for the network messages;

a memory for storing the computed release times; and

a memory controller operably coupled to the memory, the memory controller configured to search the memory for computed release times,

wherein release times are computed and stored in the memory as information relating to the network messages is retrieved from the queues.

2. The traffic shaper of claim 1 wherein the information includes a network message length and a network message pointer.

3. The traffic shaper of claim 1 wherein each network message is associated with a shaper identification (SID) value, and the traffic shaper further comprises a queue control memory accessible by the queue controller, the queue control memory including a mapping of SID values to queues such that the information for a given network message is mapped by the SID value associated with the given message to a specific queue.

4. The traffic shaper of claim 3 wherein the queue control memory further includes data for each queue indicating whether the respective queue is empty.

5. The traffic shaper of claim 4 wherein the scheduler comprises a rate monitor configured to determine a rate at which network messages can be released, and a release timestamp generator for computing release times based on the determined rates.

6. The traffic shaper of claim 5 wherein the determined network message release rates are one of Committed Information Rate (CIR) and Excess Information Rate (EIR) values.

7. The traffic shaper of claim 3 wherein the memory comprises at least one content addressable memory structure for storing computed release times, and corresponding a random access memory structure for storing the SID values associated with the respective release times stored in the content addressable memory structure.

8. The traffic shaper of claim 7 wherein the memory controller comprises a retrieve time generator for producing retrieve times that are used to search the computed release times stored in the content addressable memory structure.

9. The traffic shaper of claim 8 further comprising a current time generator for producing a current time, wherein the retrieve time produced by the retrieve time generator can catch up to but not exceed the current time produced by the current time generator.

10. The traffic shaper of claim 9 wherein upon identifying a release time stored in the content addressable memory that matches the release time produced by the release time generator, the memory controller provides the SID value associated with the matching release time and the current time to the queue controller.

11. The traffic shaper of claim 10 wherein the queue controller, upon receiving a SID value from the memory controller, accesses the queue control memory to identify the queue corresponding to the received SID value, and retrieves the information from the head of identified queue, thereby releasing the corresponding network message from the traffic shaper.

12. The traffic shaper of claim 1 configured to support multiple levels of shaping.

13. A method for shaping network traffic by selectively releasing network messages, the method comprising the steps of:

providing a plurality of queues for storing data;

associating each queue with a corresponding shaper identification (SID) value;

receiving information related to a network message to be shaped, including a SID value;

storing at least some of the received information at the queue corresponding to the received SID value;

computing a release time for each queue containing network message information;

storing the computed release times in a time-searchable memory structure; and

upon expiration of a computed release time, dequeuing network message information from the queue corresponding to the expired release time.

14. The method of claim 13 wherein a new release time is computed for a given queue in response to the step of dequeuing network message information from the given queue.

15. The method of claim 14 further comprising the step of searching the time searchable memory structure for expired release times.

16. The method of claim 15 wherein the network message information stored at the queues includes a message length and a message pointer.

17. The method of claim 14 further comprising the steps of:

associating each computed release time stored in the time-searchable memory structure with a corresponding SID value; and

upon expiration of a computed release time stored in the time-searchable memory structure, using the associated SID value to identify the queue from which network message information is to be dequeued.

18. The method of claim 17 wherein the step of computing a release time comprises the steps of:

determining, based on a rate at which network messages are being drained, whether an excess information rate (EIR) or a committed information rate (CIR) is to be used in the calculation; and

computing the release time based on the EIR or CIR as determined.

19. The method of claim 18 wherein the step of determining comprises the steps of:

computing a level at which network messages are draining from the respective queue;

comparing the level to a threshold;

if the new last updated level exceeds the threshold, selecting the CIR; and

if the new last updated level does not exceed the threshold, selecting the EIR.

20. The method of claim 19 further comprising the step of, upon dequeuing network message information from a first queue in response to an expired release time, enqueuing the network message information at a second queue.

21. A traffic shaper for use in determining transmission start times for network messages, the traffic shaper comprising:

a plurality of queues for storing information relating to the network messages;

means for storing the information in and retrieving the information from the plurality of queues;

means for computing release times for the network messages;

a memory for storing the computed release times; and

means for searching the memory for computed release times,

wherein release times are computed and stored in the memory as information relating to the network messages is retrieved from the queues.

22. The traffic shaper of claim 21 wherein the release time computing means comprises means for determining a rate at which network messages can be released, and the release time computing means computes release times based on the determined rates.

23. The traffic shaper of claim 22 wherein the searching means comprises means for producing retrieve times that are used to search the computed release times stored in the memory.

24. The traffic shaper of claim 23 further comprising means for generating a current time, wherein the retrieve time from the retrieve time producing means can catch up to but not exceed the current time produced by the current time generator.

25. A computer readable medium containing executable program instructions for shaping network traffic by selectively releasing network messages, the executable program instructions comprising program instructions for:

providing a plurality of queues for storing data;

associating each queue with a corresponding shaper identification (SID) value;

receiving information related to a network message to be shaped, including a SID value;

storing at least some of the received information at the queue corresponding to the received SID value;

computing a release time for each queue containing network message information;

storing the computed release times in a time-searchable memory structure; and

upon expiration of a computed release time, dequeuing network message information from the queue corresponding to the expired release time.

26. The computer readable medium of claim 25 wherein a new release time is computed for a given queue in response to the step of dequeuing network message information from the given queue.

27. The computer readable medium of claim 26 further comprising programming instructions for searching the time searchable memory structure for expired release times.

28. The computer readable medium of claim 27 wherein the network message information stored at the queues includes a message length and a message pointer.

29. The computer readable medium of claim 26 further comprising programming steps for:

associating each computed release time stored in the time-searchable memory structure with a corresponding SID value; and

upon expiration of a computed release time stored in the time-searchable memory structure, using the associated SID value to identify the queue from which network message information is to be dequeued.

30. The computer readable medium of claim 29 wherein the programming instruction for computing a release time comprises programming instructions for:

determining, based on a rate at which network messages are being drained, whether an excess information rate (EIR) or a committed information rate (CIR) is to be used in the calculation; and

computing the release time based on the EIR or CIR as determined.

31. The computer readable medium of claim 30 wherein the programming instructions for determining comprises the programming instructions for:

computing a level at which network messages are draining from the respective queue;

comparing the level to a threshold;

if the new last updated level exceeds the threshold, selecting the CIR; and

if the new last updated level does not exceed the threshold, selecting the EIR.

32. The computer readable medium of claim 31 further comprising programming instructions for, upon dequeuing network message information from a first queue in response to an expired release time, enqueuing the network message information at a second queue.