Granted Patent B1

US 7,342,886 · App. 10/613,629 · Granted Mar 11, 2008

Abstract

Claims (82)

1. A traffic management processor for processing a plurality of different traffic flows on a per-flow basis, each traffic flow including any number of packets transmitted from the same source address to the same destination address and each packet including a flow identification (ID) indicating to which traffic flow the packet belongs, comprising:

means for tracking each packet according to its flow ID, wherein the means for tracking comprises a content addressable memory (CAM) device having a plurality of rows, each for storing the flow ID and a most recently received bit for a corresponding packet, wherein the most recently received bit indicates whether the corresponding packet is the most recently received packet for its traffic flow and is used for computing the departure time of the packet; and

means for scheduling each packet according to its flow ID.

2. The traffic management processor of claim 1 , wherein the means for tracking further comprises:

match flag logic having inputs coupled to the rows of the CAM device and having an output coupled to the means for scheduling.

3. The traffic management processor of claim 1 , wherein the flow ID is independent of a per-hop behavior selection.

4. The traffic management processor of claim 1 , wherein the CAM device is configured to compare the flow ID of an incoming packet with the flow IDs stored in the CAM device to generate a match flag indicating whether the incoming packet is part of a new traffic flow.

5. The traffic management processor of claim 4 , wherein the means for scheduling calculates a departure time for the incoming packet relative to the packet's arrival time if the match flag is not asserted and calculates the departure time for the incoming packet relative to the departure time of the previously received packet of the same flow if the match flag is asserted.

6. The traffic management processor of claim 5 , wherein the means for scheduling comprises:

a departure time calculator (DTC) circuit for generating the departure times; and

a departure time prioritizer coupled to the DTC circuit and for determining which of the departure times is the earliest.

7. The traffic management processor of claim 6 wherein the departure time prioritizer comprises:

a table having a plurality of rows, each row for storing the departure time for a corresponding packet and each row coupled to a corresponding row of the CAM device; and

compare logic coupled to the table, the compare logic configured to compare the departure times with each other to determine which row contains the earliest departure time.

8. The traffic management processor of claim 7 , further comprising:

a priority encoder coupled to the compare logic, the priority encoder generating an address of the row in the table that contains the earliest departure time.

9. The traffic management processor of claim 1 , further comprising:

means for independently policing each of the traffic flows.

10. The traffic management processor of claim 9 , wherein the means for independently policing comprises:

a parameter table having a plurality of rows, each for storing one or more flow parameters for a queued packet; and

policing logic coupled to the parameter table, the policing logic for generating a packet accept flag for an incoming packet in response to one or more flow parameters corresponding to a queued packet that has the same flow ID as the incoming packet.

11. The traffic management processor of claim 10 , wherein the policing logic comprises:

means for accessing a packet size parameter for the incoming packet;

means for accessing the one or more flow parameters from the parameter table for a previously queued packet that has the same flow ID as the incoming packet;

means for calculating a bucket size parameter using the one or more flow parameters; and

means for comparing the bucket size parameter with the packet size parameter to generate the packet accept flag.

12. The traffic management processor of claim 1 , wherein the different traffic flows are not aggregated.

13. A traffic management processor for managing a number of traffic flows each including one or more packets, wherein the packets of each flow are transmitted from the same source address to the same destination address, comprising:

a content addressable memory (CAM) device having a plurality of rows, each row for storing a flow identification (ID) and a most recently received bit for a corresponding packet, wherein the flow ID indicates to which traffic flow the packet belongs and wherein the most recently received bit indicates whether the corresponding packet is the most recently received packet for its traffic flow and is used for computing the departure time of the packet;

a departure time table including a plurality of rows, each coupled to a corresponding row of the CAM device and configured to store a departure time for the corresponding packet; and

compare logic having inputs coupled to corresponding rows of the departure time table, the compare logic for comparing the departure times with each other to determine which departure time is the earliest.

14. The traffic management processor of claim 13 , further comprising a priority encoder coupled to the compare logic, the priority encoder generating an address of the row in the departure time table that contains the earliest departure time.

15. The traffic management processor of claim 13 , wherein the flow ID is independent of a per-hop behavior selection.

16. The traffic management processor of claim 14 , wherein the priority encoder is configured to generate a next free address in the CAM device in response to the most-recently received bits.

17. The traffic management processor of claim 13 , wherein the CAM device is configured to compare a flow ID received for an incoming packet with the flow ID's stored in the CAM device.

18. The traffic management processor of claim 17 , further comprising:

match logic having a plurality of inputs, each coupled to a corresponding row of the CAM device, the match logic generating a match flag in response to match conditions in the CAM device; and

a departure time calculator (DTC) circuit having an input to receive the match flag.

19. The traffic management processor of claim 18 , wherein the DTC circuit calculates a departure time for the incoming packet relative to the departure time of a previously received packet of the same traffic flow if the match flag is asserted.

20. The traffic management processor of claim 18 , wherein the DTC circuit calculates a departure time for the incoming packet relative to the packet's arrival time if the match flag is not asserted.

21. The traffic management processor of claim 13 , further comprising:

a parameter table having a plurality of rows, each coupled to corresponding rows of the CAM device and the departure time table, each row of the parameter table for storing one or more flow parameters for a corresponding queued packet; and

policing logic coupled to the parameter table, the policing logic determining whether to accept or reject an incoming packet in response to one or more flow parameters selectively provided by the parameter table.

22. The traffic management processor of claim 21 , wherein the policing logic comprises:

means for accessing a packet size parameter for the incoming packet;

means for accessing one or more flow parameters from the parameter table for a previously received packet of the same traffic flow;

means for calculating a bucket size parameter using the one or more flow parameters; and

means for comparing the bucket size parameter with the packet size parameter to generate a packet accept flag for the incoming packet.

23. The traffic management processor of claim 13 , wherein the traffic flows are not aggregated.

24. The traffic management processor of claim 13 , wherein the traffic flows are managed on a per-flow basis.

25. A method for processing a number of different traffic flows on a per-flow basis, each traffic flow including one or more packets transmitted from the same source address to the same destination address, comprising:

receiving an incoming packet, wherein the incoming packet includes a flow identification (ID) indicating to which traffic flow the incoming packet belongs;

comparing the flow ID of the incoming packet with the flow ID's of previously queued packets using a content addressable memory (CAM) device configured to store the flow ID's for corresponding packets, and computing the departure time of the incoming packet based on a most recently received bit for the incoming packet in the CAM;

selectively asserting a match flag in response to the comparing; and

scheduling the incoming packet for departure according to which traffic flow the packet belongs.

26. The method of claim 25 , wherein the flow ID is independent of a per-hop behavior selection.

27. The method of claim 25 , wherein the scheduling comprises:

calculating a departure time for the incoming packet relative to the departure time of a previously received packet of the same traffic flow if the match flag is asserted; and

calculating a departure time for the incoming packet relative to the packet's arrival time if the match flag is not asserted.

28. The method of claim 27 , wherein the scheduling further comprises:

comparing the departure times of the packets with each other to determine which departure time is the earliest; and

transmitting the packet that has the earliest departure time.

29. The method of claim 25 , further comprising:

storing a most recently received bit for each packet.

30. The method of claim 29 , further comprising:

asserting the most-recently received bit for the incoming packet; and

de-asserting the most-recently received bit of a previously received packet of the same traffic flow as the incoming packet.

31. The method of claim 29 , further comprising:

storing the departure times for all packets together in a departure time table.

32. The method of claim 31 , further comprising:

selectively deleting entries from the table in response to the most recently received bit.

33. The method of claim 25 , further comprising:

policing the incoming packet for acceptance according to which traffic flow the packet belongs.

34. The method of claim 33 , wherein each traffic flow is independently policed using a leaky bucket technique.

35. The method of claim 33 , wherein the policing comprises, for the incoming packet:

accessing a packet size parameter for the incoming packet;

accessing a bucket size parameter for the incoming packet's traffic flow, the bucket size indicating the amount of data that may be accepted from the incoming packet's traffic flow during a sample period;

comparing the bucket size parameter to the packet size parameter; and

accepting the incoming packet if the packet size parameter is less than the bucket size parameter.

36. The method of claim 35 , further comprising:

decreasing the bucket size parameter by an amount of the packet size parameter if the incoming packet is accepted.

37. The method of claim 25 , wherein the traffic flows are not aggregated.

Assignments (8)