Method and apparatus for performing high-speed traffic shaping

• US 7,130,272 B1
• Filed: 03/07/2005
• Issued: 10/31/2006
• Est. Priority Date: 04/27/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Edsall, Thomas J., Gai, Silvano
• Primary Examiner(s): To, Doris H.
• Assistant Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US11/074,261
• Time in Patent Office: 603 Days
• Field of Search: None
• 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 for shapping transmission of network messages includes a system time generator for generating a system time, an arithmetic logic unit (ALU) for computing a transmission start time for each network message in response to the system time, and a retrieve time generator adapted to increment a retrieve time at a rate faster than the system time. As network messages are received, they are stored in a queue along with an associated transmission start time for each message. A forwarding trigger transmits a store network messages when its associated transmission start time matches the retrieve time. Alternately, a second transmission start time representing an excess bandwidth transmission start time may be computed for each network message. If excess bandwidth is detected, a message may be transmitted when its second transmission start time matches the retrieve time.

Claims

1. A traffic shaper for shaping transmission of network messages, comprising:

a system time generator to generate a system time;

an arithmetic logic unit (ALU) to compute a transmission start time for a network message in response to the system time;

a retrieve time generator to increment a retrieve time at a rate faster than the system time;

a queue to store the network message and the transmission start time; and

a forwarding trigger to transmit the network message stored in the queue when the retrieve time matches the transmission start time of the message.

2. The traffic shaper of claim 1 wherein the retrieve time generator is blocked from incrementing while matches with the first transmission time are being determined.

3. The traffic shaper of claim 1 wherein the queue further comprises:

a first memory device to store a plurality of entries, each entry configured to store the first transmission start time of a network message.

4. The traffic shaper of claim 3 wherein the queue further comprises:

a second memory device interconnected to the first memory device, the second memory device to store message location information corresponding to each first transmission start time in the first memory device.

5. The traffic shaper of claim 3 wherein the first memory device is a content addressable memory (CAM) searchable by the retrieve time.

6. The traffic shaper of claim 3 further comprising:

insert/retrieve logic coupled to the first memory device, the inset/retrieve logic configured to operate in either an insert mode or a retrieve mode such that, in insert mode, the inset/retrieve logic searches the first memory device for a free entry in which to store a transmission start time, and in retrieve mode the insert/retrieve logic searches the first memory device for a transmission start time that matches the retrieve time.

7. The traffic shaper of claim 1 further comprising:

a transmit trigger-signal issued by the forwarding trigger in response to detecting the first transmission start time matching the retrieve time, the transmit trigger-signal issued to a message buffer to indicate a selected message should be forwarded.

8. The traffic shaper of claim 1 further comprising:

a second transmission start time, computed by the ALU, for a network message, the second transmission start time earlier in time than the first transmission start time; and

wherein the forwarding trigger is to transmit the network message stored in the queue when excess bandwidth is detected and the retrieve time matches the second transmission start time of the message.

9. A traffic shaper for shaping transmission of network messages, comprising:

a retrieve time generator to generate retrieve time;

a system generator to generate a system time, wherein the retrieve time is incremented at a faster rate than the system time;

an arithmetic logic unit (ALU) to compute a first and a second transmission start times for a network message in response to the system time, the first transmission start time representing a guaranteed transmission start time for the network message, the second transmission start time representing an excess bandwidth transmission start time;

a message/traffic flow controller interconnected to the ALU to inform the ALU when excess bandwidth exists for sending network messages; and

a forwarding trigger to transmit the network message stored in the queue when either the retrieve time matches the first transmission start time, or the retrieve time matches the second transmission start time and excess bandwidth exists.

10. A method for shaping transmission of network messages, comprising:

generating a clock signal;

generating a system time, the system time responsive to the clock signal;

computing a first transmission start time for a network message in response to the system time;

generating a retrieve time responsive to the clock signal, the retrieve time incremented at a rate faster than the system time;

storing a network message in a queue; and

transmitting the network message stored in the queue when the retrieve time matches the first transmission start time of the message.

11. The method for shaping transmission of network messages of claim 10 further comprising:

blocking the retrieve time from incrementing while matches between the retrieve time and the first transmission times are being determined.

12. The method for shaping transmission of network messages of claim 10 wherein the step of storing a network message further comprises:

storing the first transmission start time for the network message as an entry in a first memory device.

13. The method for shaping transmission of network messages of claim 12 wherein the step of storing a network message further comprises:

storing message location information corresponding to the network message in a second memory device interconnected to the first memory device.

14. The method for shaping transmission of network messages of claim 12 wherein the first memory device is a content addressable memory (CAM) searchable by the retrieve time.

15. The method for shaping transmission of network messages of claim 12 comprising:

selecting to operate in either an insert mode or a retrieve mode such that, in insert mode, an inset/retrieve logic searches the first memory device for a free entry in which to store a transmission start time, and in retrieve mode the insert/retrieve logic searches the first memory device for a transmission start time that match the retrieve time.

16. The method for shaping transmission of network messages of claim 10 comprising:

issuing a transmit trigger-signal to a message buffer upon detecting the first transmission start time matching the retrieve time to indicate a selected message should be forwarded.

17. The method for shaping transmission of network messages of claim 10 comprising:

computing a second transmission start time, the second transmission start time earlier in time than the first transmission start time; and

transmitting the network message when the retrieve time matches the second transmission start time of the message if excess bandwidth is detected.

18. A method for shaping transmission of network messages, comprising:

generating a retrieve time;

generating a system time, wherein the retrieve time is incremented at a faster rate than the system time;

computing a first and a second transmission start time for a network message in response to the system time, the first transmission start time representing a guaranteed transmission start time for the network message, the second transmission start time representing an excess bandwidth transmission start time;

determining when excess bandwidth exists for sending network messages; and

transmitting the network message stored in the queue when the retrieve time matches either the first transmission start time of the message or the retrieve time matches the second transmission start time of the message and excess bandwidth is detected.

19. A traffic shaper for shaping transmission of network messages, comprising:

means for generating a clock signal;

means for generating a system time, the system time responsive to the clock signal;

means for computing a first transmission start times for a network message in response to the system time;

means for generating a retrieve time responsive to the clock signal, the retrieve time incremented at a faster rate than the system time;

means for storing a network message; and

means for transmitting the network message stored when the retrieve time matches the first transmission start time of the message.

20. A traffic shaper for shaping transmission of network messages, comprising:

means for generating a retrieve time;

means for generating a system time, wherein the retrieve time is incremented at a faster rate than the system time;

means for computing a first and a second transmission start time for a network message in response to the system time, the first transmission start time representing a guaranteed transmission start time for the network message, the second transmission start time representing an excess bandwidth transmission start time;

means for determining when excess bandwidth exists for sending network messages; and

means for transmitting the network message stored in the queue when the retrieve time matches either the first transmission start time of the message or the retrieve time matches the second transmission start time of the message and excess bandwidth is detected.