Method and apparatus for performing high-speed traffic shaping

• US 6,904,014 B1
• Filed: 04/27/2000
• Issued: 06/07/2005
• 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): Ho, Duc
• Assistant Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US09/560,499
• Time in Patent Office: 1,867 Days
• Field of Search: 370412-428, 370/392, 370/395.42, 370/230.1, 709/206, 711/108, 713/502, 365/189.07, 365/49
• US Class Current: 370/230.1
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping

Abstract

A network traffic shaper includes a traffic shaper table for storing traffic specifiers, such as permissible data transmission rates, an arithmetic logic unit (ALU), and a high-speed forwarding trigger mechanism having at least one time-searchable data structure or queue and a retrieve time generator that substantially tracks, but never exceeds, a system time. As network messages are received, they are stored at a message buffer and certain message parameters, including message length and a corresponding traffic specifier, are provided to the traffic shaper. The traffic shaper determines when the message may be sent in accordance with the associated traffic specifier and stores this transmission start time along with the message'"'"'s buffer location in the time-searchable queue of the forwarding trigger. The forwarding trigger continuously examines the transmission start times for previously stored messages. When the transmission start time of a given message matches the retrieve time generator, the forwarding trigger mechanism signals that the message may be sent.

Claims

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

an arithmetic logic unit (ALU) configured to compute at least one transmission start time for a selected network message; and

a forwarding trigger mechanism coupled to the ALU, the forwarding trigger mechanism comprising a time-searchable queue and a retrieve time generator, whereby,

the forwarding trigger mechanism is configured to store the at least one transmission start time in the time-searchable queue, to generate a retrieve time in the retrieve time generator, and to issue a transmit trigger-signal for the selected network message when its at least one transmission start time matches the retrieve time, and

wherein

the retrieve time is allowed to equal but not exceed a system time.

2. The traffic shaper of claim 1 further comprising a traffic shaper table coupled to the ALU, the traffic shaper table comprising a plurality of records each containing data transmission rate information and a timestamp relating to a last time that data was transmitted at the respective rate,

whereby,

the ALU utilizes the data transmission rate information and associated timestamp from a specified record of the traffic shaper table to compute the at least one transmission start time for the selected network message.

3. The traffic shaper of claim 2 wherein the time-searchable queue includes a first memory device having a plurality of entries and each entry is configured to store one or more transmission start times as computed by the ALU for a respective network message.

4. The traffic shaper of claim 3 wherein the time-searchable queue further comprises a second memory device for storing message location information.

5. The traffic shaper of claim 4 whereby each entry of the first memory device of the time-searchable queue identifies a corresponding entry in the second memory device such that, for a given network message, the corresponding entries of the first and second memory devices store the one or more transmission start times and the message location information, respectively, for the given network message.

6. The traffic shaper of claim 5 wherein the forwarding trigger mechanism periodically searches the first memory device of the time-searchable queue for all entries having at least one transmission start time that matches the retrieve time and, upon identifying such an entry, utilizes the message location information from the corresponding entry in the second memory device to issue a transmit trigger-signal.

7. The traffic shaper of claim 6 wherein each network message is temporarily buffered in a respective location of a message buffer, and the forwarding trigger mechanism further comprises a plurality of first-in-first-out (FIFO) queues, and each record of the traffic shaper table further contains an indication whether the respective transmission rate information relates to Constant Bit Rate (CBR) traffic shaping or Committed Information Rate/Excess Information Rate (CIR/EIR) traffic shaping,

whereby,

for a network message subject to CBR traffic shaping as indicated by the corresponding record of the traffic shaper table, the second memory device is arranged to store a pointer to the respective location in the message buffer at which the network message is buffered, and

for a network message subject to CIR/EIR traffic shaping as indicated by the corresponding record of the traffic shaper table, the second memory device is arranged to store the identity of a selected FIFO queue which contains a pointer to the respective location in the message buffer at which the network message is buffered.

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

9. The traffic shaper of claim 8 wherein each entry of the CAM is a tuple comprising a pointer, a first timestamp, and a second timestamp, wherein the pointer identifies either a selected FIFO queue or a location in the message buffer depending on whether the respective network message is subject to CBR or CIR/EIR traffic shaping, and the first and second timestamps are the transmission start times as computed by the ALU.

10. In an intermediate network device having a forwarding engine for making forwarding decisions with respect to network messages, a message buffer for temporarily storing the network messages at corresponding locations, and a traffic shaper for use in determining transmission start times for the network messages, the traffic shaper comprising:

a traffic shaper table having a plurality of records each containing data transmission rate information and a timestamp relating to a last time that a respective network message was transmitted at the data transmission rate;

an arithmetic logic unit (ALU) coupled to the traffic shaper table, the ALU configured to compute at least one transmission start time for a selected network message based on the transmission rate information and timestamp from a record of the traffic shaper table corresponding to the selected network message; and

a forwarding trigger mechanism for receiving the transmission start times computed by the ALU and message buffer location information from the forwarding engine, the forwarding trigger mechanism having a time-searchable calendar queue for storing the transmission start times and network message location information and a retrieve time generator for generating a retrieve time,

whereby,

the forwarding trigger mechanism searches the time-searchable calendar queue for transmission start times that match the retrieve time and issues transmit trigger-signals to the forwarding engine for network messages whose transmission start time matches the retrieve time,

wherein,

the retrieve time is allowed to equal but not exceed a system time.

11. The traffic shaper of claim 10 wherein the time-searchable calendar queue comprises:

a first memory device having a plurality of entries for storing the transmission start times computed by the ALU;

a second memory device having a plurality of entries for storing the message location information, each entry of the second memory device being associated with a corresponding entry of the first memory device; and

insert/retrieve logic coupled to the first and second memory devices, the insert/retrieve logic configured to operate in either insert mode or retrieve mode such that, in insert mode, the insert/retrieve logic searches the first memory device for a free entry in which to store the transmission start times computed for a given network message and, in retrieve mode, the insert/retrieve logic searches the first memory device for transmission start times that match the retrieve time.

12. The traffic shaper of claim 11 wherein the time-searchable calendar queue further comprises:

a multiplexer operably coupled to the insert/retrieve logic, the multiplexer having an output that is coupled to the first memory device and a first input coupled to the retrieve time generator; and

a free pattern data structure coupled as a second input to the multiplexer,

wherein,

the insert/retrieve logic sets the multiplexer to output the free pattern when in insert mode and to output the retrieve time when in retrieve mode, so that the first memory device is correspondingly searched for either the retrieve pattern or the retrieve time.

13. The traffic shaper of claim 11 wherein the time-searchable calendar queue further comprises:

a system time generator configured to generate the system time; and

means for maintaining the retrieve time at a value that is less than or equal to a system time.

14. The traffic shaper of claim 13 wherein the maintaining means comprises:

a comparator that compares the system time with the retrieve time, and outputs a TRUE signal when the retrieve time is less than the system time, and a FALSE signal when the retrieve time is equal to or greater than the system time; and

a logic circuit operatively coupled to the retrieve time generator and further coupled to receive the TRUE and FALSE signals from the comparator and to receive a TRUE signal from the first memory device when no entries match the retrieve time and a FALSE signal from the first memory device when one or more entries match the retrieve time, the logic circuit configured to output a TRUE signal only where its two inputs are TRUE,

wherein the retrieve time generator increments only when it receives a TRUE signal from the logic circuit.

15. The traffic shaper of claim 14 wherein the logic circuit is an AND gate.

16. The traffic shaper of claim 13 wherein the time-searchable calendar queue further comprises a temporary data store for buffering the transmission start times and message location information before being stored in the first and second memory devices, the temporary data store coupled to the insert/retrieve logic.

17. The traffic shaper of claim 16 wherein the temporary data store comprises a plurality of first-in-first-out data structures (FIFOs), each FIFO associated with a start time range such that a given transmission start time and message location information are buffered in the FIFO whose start time range includes the given transmission start time.

18. The traffic shaper of claim 17 wherein the insert/retrieve logic is further configured to periodically identify the FIFO whose start time range is closest to the current time and to copy the transmission start time and message location information from the identified FIFO into the first and second memory devices.

19. A method for controlling the transmission time of network messages received at a traffic shaper in an intermediate network device, the method comprising the steps of:

computing one or more transmission start times for a given message in response to rate transmission information for the given message, a time at which a last message at a specified rate was sent, a length of the given message and a system time;

storing the one or more transmission start times in at least one entry of a content addressable memory (CAM);

generating a retrieve time;

comparing the entries of the CAM to the retrieve time; and

forwarding the given message when its one or more transmission start times matches the retrieve time in the traffic shaper, wherein the retrieve time is allowed to equal but not exceed the system time.

20. The method of claim 19 further comprising the steps of:

storing a pointer to the given message in an entry of a memory device that is associated with the CAM entry at which the one or more transmission start times for the given message is stored; and

in response to matching the one or more transmission start times for the given message with the retrieve time, retrieving the pointer to the given message in order to forward the given message.

21. The method of claim 19 wherein the step of storing the one or more transmission start times comprises the step of searching the CAM for an entry having a free pattern and storing the one or more transmission start times in that entry.

22. The method of claim 21 wherein the retrieve time is prevented from exceeding the system time.

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

an arithmetic logic unit (ALU) to compute a transmission start time for a selected network message; and

a forwarding trigger mechanism, coupled to the ALU, the forwarding trigger mechanism configured to store the transmission start time in a calendar queue, to generate a retrieve time, and to issue a transmit trigger-signal for the selected network message when the transmission start time matches the retrieve time

wherein, the retrieve time is allowed to equal but not exceed a system time.

24. A traffic shaper as defined in claim 23 comprising:

a traffic shaper table containing a plurality of records wherein each record contains data transmission rate information and a timestamp relating to a last time data was transmitted at a respective rate,

wherein the ALU utilizes the data transmission rate information and associated timestamp from a specified record of the traffic shaper table to compute the transmission start time for the selected network message.

25. A traffic shaper as defined in claim 24 further comprising a first memory for storing the transmission start time and a second memory for storing message location information associated with the selected network message.

26. A traffic shaper as defined in claim 25 wherein the forwarding trigger mechanism periodically searches the first memory to identify an entry having a transmission start time that matches the retrieve time and upon identifying such an entry, utilizes message location information in the second memory associated with the entry to issue a transmit trigger-signal.

27. A traffic shaper as defined in claim 26 comprising:

a network message buffer that buffers network messages; and

a plurality of first-in-first-out (FIFO) queues,

wherein each record of the traffic shaper table further contains an indication whether the respective transmission rate information relates to Constant Bit Rate (CBR) traffic shaping or Committed Information Rate/Excess Information Rate (CIR/EIR) traffic shaping,

whereby for a network message subject to CBR traffic shaping as indicated by the corresponding record of the traffic shaper table, the second memory is arranged to store a pointer to the respective location in the message buffer at which the network message is buffered, and for a network message subject to CIR/EIR traffic shaping as indicated by the corresponding record of the traffic shaper table, the second memory is arranged to store an identity of a selected FIFO queue which contains a pointer to the respective location in the message buffer at which the selected network message is buffered.

28. A traffic shaper as defined in claim 27 wherein the first memory is a content addressable memory (CAM) comprising a plurality of entries and is searchable by the retrieve time.

29. A traffic shaper as defined in claim 28 wherein each entry of the CAM is a tuple comprising a pointer, a first timestamp and a second timestamp, wherein the pointer identifies either a selected FIFO queue or a location in the message buffer depending on whether the respective network message is subject to CBR or CIR/EIR traffic shaping, and the first and second timestamps are the transmission start times as computed by the ALU.

30. A method for determining transmission start times for network messages in a traffic shaper, comprising the steps of:

computing a transmission start time for a selected network message;

storing the start time in a calendar queue;

generating a retrieve time; and

issuing a transmit trigger-signal for the selected network message when the transmission start time matches the retrieve time in the traffic shaper,

wherein, the retrieve time is allowed to equal but not exceed a system time.

31. A method as defined in claim 30 further comprising the steps of:

storing the transmission start time in a first memory having a plurality of entries; and

storing message location information associated with the selected network message in a second memory having a plurality of entries.

32. A method as defined in claim 31 comprising the steps of:

searching the first memory to identify an entry in the first memory having a transmission start time that matches the retrieve time; and

upon identifying such an entry in the first memory, utilizing message location information in an entry in the second memory that is associated with the identified first memory'"'"'s entry to issue a transmit trigger-signal.

33. A method as defined in claim 30 further comprising the step of:

utilizing data transmission rate information and an associated timestamp from a specified record of a traffic shaper table to compute the transmission start time for the selected network message.

34. A method as defined in claim 33 wherein the record contains an indication whether the respective transmission rate information relates to Constant Bit Rate (CBR) traffic shaping or Committed Information Rate/Excess Information Rate (CIR/EIR) traffic shaping.

35. A method as defined in claim 34 comprising the steps of:

for a network message subject to CBR traffic shaping as indicated by its specified record of the traffic shaper table, storing a pointer to the respective location in the message buffer at which the network message is buffered; and

for a network message subject to CIR/EIR traffic shaping as indicated by its specified record of the traffic shaper table, storing an identity of a selected FIFO queue which contains a pointer to the respective location in the message buffer at which the network message is buffered.

36. An apparatus for determining transmission start times for network messages in a traffic shaper, comprising:

means for computing a transmission start time for a selected network message;

means for storing the transmission start time in a calendar queue;

means for generating a retrieve time; and

means for issuing a transmit trigger-signal for the selected network message when the transmission start time matches the retrieve time in the traffic shaper,

wherein, the retrieve time is allowed to equal but not exceed a system time.