Implementation of distributed traffic rate limiters

• US 7,830,873 B1
• Filed: 01/09/2007
• Issued: 11/09/2010
• Est. Priority Date: 01/09/2007
• Status: Active Grant

• Current Assignee: Marvell Israel Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell Israel Limited (Marvell Technology Group Limited)
• Inventors: Arad, Carmi
• Primary Examiner(s): Vu; Thong H
• Application Number:
  US11/651,723
• Time in Patent Office: 1,400 Days
• Field of Search: 370/401, 370/389, 707/201, 707/200, 707/3, 711/219
• US Class Current: 370/389
• CPC Class Codes: H04L 47/52 by attributing bandwidth to queues
• CPC Class Codes: H04L 47/6235 Variable service order

Abstract

A method of processing packets and a network device are disclosed. Packets are received from separate ingress processing pipelines during a processing cycle. Control information for each packet is retrieved from one or more databases serving each pipeline and used to perform operations representative of different processing outcomes. Results of the operations are selected and used to update the databases, in some cases, based upon whether a relationship is detected between the packets.

Claims

1. A method of processing packets, comprising:

receiving, by a network device, first and second packets, the first and second packets having first and second index values respectively;

looking up, by the network device, first and second entries using said first and second index values;

performing, by the network device, first and second operations using said first and second entries; and

updating, by the network device, said first and second entries identically if a predetermined relationship is detected between said first and second index values, otherwise updating said first and second entries separately.

2. The method of claim 1 wherein said first and second packets are received from first and second ingress pipelines respectively, and further comprising synchronizing, by the network device, said packets to a same clock cycle before processing begins.

3. The method of claim 1 wherein said first and second entries contain rate limit parameters, and wherein said predetermined relationship is detected if said first and second packets are subject to a same rate limit.

4. The method of claim 1 wherein said first operation comprises updating a separate number of tokens corresponding to a rate limit for each of said first and second entries, and said second operation comprises updating a combined number of tokens for said first and second entries.

5. The method of claim 1 wherein said first packet comprises a first attribute and said second packet comprises a second attribute, the method further comprising:

maintaining, by the network device, a first table of control information having N entries, each entry associated with a different one of N index values;

maintaining, by the network device, a second table of control information having N entries, each entry associated with a different one of the N index values;

retrieving, by the network device, said first entry from said first table, said first entry corresponding to the first index value;

retrieving, by the network device, said second entry from said second table, said second entry corresponding to the second index value;

performing, by the network device, said first operation using said first entry and said first attribute to generate a first result;

performing, by the network device, said second operation using said second entry and said second attribute to generate a second result;

performing, by the network device, a third operation using said first and second entries and said first and second attributes to generate a third result; and

updating, by the network device, the first and second entries according to a value defined by the third result if the predetermined relationship is detected between said first and second index values.

6. The method of claim 5 further comprising:

updating, by the network device, the first entry according to a value defined by the first result if the predetermined relationship is not detected between said first and second index values;

updating, by the network device, the second entry according to a value defined by the second result if the predetermined relationship is not detected;

updating, by the network device, an entry in the first table corresponding to the second index value according to the value defined by the second result if the predetermined relationship is not detected; and

updating, by the network device, an entry in the second table corresponding to the first index value according to the value defined by the first result if the predetermined relationship is not detected.

7. The method of claim 6 wherein the predetermined relationship is detected if the first index value equals the second index value.

8. The method of claim 7 wherein the first attribute includes a first packet size and a first color value and the second attribute includes a second packet size and a second color value.

9. The method of claim 8 wherein said first entry includes a first fill rate, a first bucket value, a first burst-size and a first time stamp and said second entry includes a second fill rate, a second bucket value, a second burst-size and a second time stamp.

10. The method of claim 9 further comprising:

adjusting, by the network device, the first bucket value by a first number of tokens if the predetermined relationship is not detected;

adjusting, by the network device, the second bucket value by a second number of tokens if the predetermined relationship is not detected;

adjusting, by the network device, the first and second bucket values by a third number of tokens if the predetermined relationship is detected; and

adjusting, by the network device, the first time stamp and the second time stamp based upon a time reference.

11. The method of claim 5 wherein each entry includes two fill rates, two corresponding buckets values and a single time stamp.

12. The method of claim 5 wherein said first packet and said second packet are synchronized to a same clock cycle before processing begins.

13. A device configured to process packets, comprising:

first and second ingress pipelines configured to receive first and second packets having first and second index values respectively;

first and second memories comprising first and second tables;

a control block configured to look up first and second entries in said first and second tables using said first and second index values, perform first and second operations using said first and second entries from said tables, and update both tables identically if a predetermined relationship is detected between said first and second index values, otherwise update said tables separately.

14. The device of claim 13 wherein said first and second packets are synchronized to a same clock cycle before processing begins.

15. The device of claim 13 wherein said entries contain rate limit parameters, and wherein said predetermined relationship is detected if said first and second packets are subject to a same rate limit.

16. The device of claim 13 wherein said first operation comprises calculating a separate number of tokens corresponding to a rate limit for each of said first and second entries, and said second operation comprises calculating a combined number of tokens for said first and second entries.

17. The device of claim 13 wherein:

said first packet includes a first attribute;

said second packet includes a second attribute;

said first table has N entries, each entry corresponding to a different one of N index values;

said second table has N entries, each entry corresponding to a different one of the N index values;

nd

said control block is configured to perform said first operation using said first attribute and said first entry to generate a first result, said second operation using said second attribute and said second entry to generate a second result, and a third operation using said first and second attributes and said first and second entries to generate a third result, said control block further configured to update said first and second entries according to a value defined by the third result if a predetermined relationship between the first index value and the second index value is detected.

18. The device of claim 17 wherein said control block is further configured to update the first entry according to a value defined by the first result if the predetermined relationship is not detected, to update the second entry according to a value defined by the second result if the predetermined relationship is not detected, to update an entry in the first table corresponding to the second index value according to the value defined by the second result if the predetermined relationship is not detected, and to update an entry in the second table corresponding to the first index value according to the value defined by the first result if the predetermined relationship is not detected.

19. The device of claim 18 wherein the predetermined relationship is detected if the first index value equals the second index value.

20. The device of claim 19 wherein said first packet attribute includes a first packet size and a first color value and said second packet attribute includes a second packet size and a second color value.

21. The device of claim 20, wherein said first entry includes a first fill rate, a first bucket value, a first burst-size and a first time stamp and said second entry includes a second fill rate, a second bucket value, a second burst-size and a second time stamp.

22. The device of claim 21, wherein said control block is further configured to adjust the first bucket value by a first number of tokens and the second bucket value by a second number of tokens if the predetermined relationship is not detected, to adjust said first and second bucket values by a third number of tokens if the predetermined relationship is detected, and to adjust said first time stamp and said second time stamp according to a time reference.

23. The device of claim 17, wherein each entry includes two fill rates, two corresponding bucket values and a single time stamp.

24. The device of claim 17 wherein said first packet and said second packets are received by said control block from said first and second ingress pipelines and wherein said control block synchronizes the packets to a same clock cycle before processing begins.

25. A device for processing packets, comprising:

means for receiving first and second packets, the first and second packets having first and second index values respectively;

means for looking up first and second entries using said first and second index values;

means for performing first and second operations using said first and second entries;

means for determining a relationship between said first and second index values; and

means for updating both said first and second entries identically if a predetermined relationship is detected between said first and second index values, otherwise updating said first and second entries separately.

26. The device of claim 25 further comprising means for synchronizing said packets to a same clock cycle before processing begins.

27. The device of claim 25 wherein said entries contain rate limit parameters, and wherein said predetermined relationship is detected if said first and second packets are subject to a same rate limit.

28. The device of claim 25 wherein said first operation comprises updating a separate number of tokens corresponding to a rate limit for each of said first and second entries, and said second operation comprises updating a combined number of tokens for said first and second entries.

29. The device of claim 25 wherein said first packet comprises a first attribute and said second packet comprises a second attribute, the device further comprising:

means for maintaining a first table of control information having N entries, each entry associated with a different one of N index values;

means for maintaining a second table of control information having N entries, each entry associated with a different one of the N index values;

means for retrieving said first entry from the first table, said first entry corresponding to the first index value;

means for retrieving said second entry from the second table, said second entry corresponding to the second index value;

means for performing a first operation using said first entry and said first attribute to generate a first result; and

means for performing a second operation using said second entry and said second attribute to generate a second result;

means for performing a third operation using said first and second entries and said first and second attributes to generate a third result;

means for updating the first and second entries according to a value defined by the third result if a predetermined relationship is detected between said first and second index values.

30. The device for processing packets recited in claim 29 further comprising:

means for updating the first entry according to a value defined by the first result if the predetermined relationship is not detected between said first and second index values;

means for updating the second entry according to a value defined by the second result if the predetermined relationship is not detected;

means for updating an entry in the first table corresponding to the second index value according to the value defined by the second result if the predetermined relationship is not detected; and

means for updating an entry in the second table corresponding to the first index value according to the value defined by the first result if the predetermined relationship is not detected.

31. The device for processing packets recited in claim 30 wherein the predetermined relationship is detected if the first index value equals the second index value.

32. The device for processing packets recited in claim 31 wherein the first attribute includes a first packet size and a first color value and the second attribute includes a second packet size and a second color value.

33. The device for processing packets recited in claim 32 wherein said first entry includes a first fill rate, a first bucket value, a first burst-size and a first time stamp and said second entry includes a second fill rate, a second bucket value, a second burst-size and a second time stamp.

34. The device for processing packets recited in claim 33 further comprising:

means for adjusting the first bucket value by the first number of tokens if the predetermined relationship is not detected;

means for adjusting the second bucket value by the second number of tokens if the predetermined relationship is not detected;

means for adjusting the first and second bucket values by the third number of tokens if the predetermined relationship is detected; and

means for adjusting the first time stamp and the second time stamp based upon a time reference.

35. The device for processing packets recited in claim 29 wherein each entry includes two fill rates, two corresponding bucket values and a single time stamp 35.

36. The device for processing packets recited in claim 29 wherein said first packet and said second packet are synchronized to a same edge of a same clock cycle before processing begins.