Buffer management scheme employing dynamic thresholds

• US 6,788,697 B1
• Filed: 08/11/2000
• Issued: 09/07/2004
• Est. Priority Date: 12/06/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Aweya, James, Montuno, Delfin Y., Ouellette, Michel
• Primary Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US09/635,898
• Time in Patent Office: 1,488 Days
• Field of Search: 370/252, 370/229-237, 370/411-419, 370/395.41, 370/395.43, 709/214, 709/215, 709/229, 709/234, 709/235
• US Class Current: 370/412
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9026 Single buffer per packet
• CPC Class Codes: H04L 49/9036 Common buffer combined with individual queues
• CPC Class Codes: H04L 49/9052 with buffers of different sizes
• CPC Class Codes: H04L 49/9078 using an external memory or storage device

Abstract

An improved buffer management process is disclosed wherein the buffer is shared among a plurality of packet queues. The improved buffer management process comprises computing a common queue threshold value based upon the aggregate size of the plurality of packet queues and a predetermined buffer threshold value. The common queue threshold value is then used to manage the size of each of the plurality of packet queues and thereby manage the buffer.

Claims

1. An improved buffer management process, wherein the buffer is shared among a plurality of packet queues, the improvement comprising:

computing a common queue threshold value based at least in part on the aggregate size of the plurality of packet queues and a predetermined buffer threshold value; and

computing a packet drop probability for each of the plurality of packet queues based at least in part on the common queue threshold value;

wherein the common queue threshold value and the respective packet drop probability are used to manage the size of each of the plurality of packet queues and thereby manage the buffer.

2. The improved buffer management process as defined in claim 1, wherein the improvement further comprises:

recomputing the common queue threshold value at predetermined time intervals.

3. The improved buffer management process as defined in claim 1, wherein the improvement further comprises:

recomputing the packet drop probability for each of the plurality of packet queues based at least in part on the common queue threshold value.

4. The improved buffer management process as defined in claim 1, wherein a predetermined increment threshold value is used to compute the common queue threshold value.

5. The improved buffer management process as defined in claim 4, wherein the computed common queue threshold value is the smaller of the sum of a current common queue threshold value and the predetermined increment threshold value or the predetermined buffer threshold value if the aggregate size of the plurality of packet queues is less than the predetermined buffer threshold value.

6. The improved buffer management process as defined in claim 4, wherein the computed common queue threshold value is the larger of the difference of a current common queue threshold value and the predetermined increment threshold value or a predetermined minimum queue threshold value if the aggregate size of the plurality of packet queues is greater than or equal to the predetermined buffer threshold value.

7. The improved buffer management process as defined in claim 7, wherein the size of each of the plurality of packet queues is managed based at least in part on determining whether to drop one or more packets based at least in part on a comparison of the respective drop probability to a reference value.

8. The improved buffer management process as defined in claim 7, wherein the reference value includes a randomly generated value.

9. The improved buffer management process as defined in claim 7, wherein the reference value represents a number of packets to be admitted into the respective packet queue between dropped packets.

10. An improved buffer management apparatus, wherein the buffer is shared among a plurality of packet queues, the improvement comprising:

at least one threshold computation processor for computing a common queue threshold value based at least in part on the aggregate size of the plurality of packet queues and a predetermined buffer threshold value; and

at least one packet drop probability computation processor for computing a packet drop probability for each of the plurality of packet queues based at least in part on the common queue threshold value;

wherein the common queue threshold value and the respective packet drop probability are used to manage the size of each of the plurality of packet queues and thereby manage the buffer.

11. The improved buffer management apparatus as defined in claim 10, wherein the at least one threshold computation processor recomputes the common queue threshold value at predetermined time intervals.

12. The improved buffer management apparatus as defined in claim 10, wherein the at least one packet drop probability computation processor recomputes the packet drop probability for each of the plurality of packet queues at predetermined time intervals.

13. The improved buffer management apparatus as defined in claim 10, wherein a predetermined increment threshold value is used to compute the common queue threshold value.

14. The improved buffer management apparatus as defined in claim 13, wherein the computed common queue threshold value is the smaller of the sum of a current common queue threshold value and the predetermined increment threshold value or the predetermined buffer threshold value if the aggregate size of the plurality of packet queues is less than the predetermined buffer threshold value.

15. The improved buffer management apparatus as defined in claim 13, wherein the computed common queue threshold value is the larger of the difference of a current common queue threshold value and the predetermined increment threshold value or a predetermined minimum queue threshold value if the aggregate size of the plurality of packet queues is greater than or equal to the predetermined buffer threshold value.

16. The improved buffer management apparatus as defined in claim 10, wherein the size of each of the plurality of packet queues is managed based at least in part on determining whether to drop one or more packets based at least in part on a comparison of the respective drop probability to a reference value.

17. The improved buffer management apparatus as defined in claim 16, wherein the reference value includes a randomly generated value.

18. The improved buffer management apparatus as defined in claim 16, wherein the reference value represents a number of packets to be admitted into the respective packet queue between dropped packets.

25. The article of manufacture as defined in claim 13, wherein the size of each of the plurality of packet queues is managed based at least in part on determining whether to drop one or more packets based at least in part on a comparison of the respective drop probability to a reference value.

26. The article of manufacture as defined in claim 25, wherein the reference value includes a randomly generated value.

27. The article of manufacture as defined in claim 25, wherein the reference value represents a number of packets to be admitted into the respective packet queue between dropped packets.

19. An article of manufacture for improving a buffer management process, wherein the buffer is shared among a plurality of packet queues, the article of manufacture comprising:

at least one processor readable carrier; and

instructions carried on the at least one carrier;

wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to;

compute a common queue threshold value based at least in part on the aggregate size of the plurality of packet queues and a predetermined buffer threshold value; and

compute a packet drop probability for each of the plurality of packet queues based at least in part on the common queue threshold value;

wherein the common queue threshold value and the respective packet drop probability are used to manage the size of each of the plurality of packet queues and thereby manage the buffer.

20. The article of manufacture as defined in claim 19, wherein the instructions further cause the at least one processor to operate so as to:

recompute the common queue threshold value at predetermined time intervals.

21. The article of manufacture as defined in claim 19, wherein the instructions further cause the at least one processor to operate so as to:

recompute the packet drop probability for each of the plurality of packet queues based at least in part on the common queue threshold value.

22. The article of manufacture as defined in claim 19, wherein a predetermined increment threshold value is used to compute the common queue threshold value.

23. The article of manufacture as defined in claim 22, wherein the computed common queue threshold value is the smaller of the sum of a current common queue threshold value and the predetermined increment threshold value or the predetermined buffer threshold value if the aggregate size of the plurality of packet queues is less than the predetermined buffer threshold value.

24. The article of manufacture as defined in claim 22, wherein the computed common queue threshold value is the larger of the difference of a current common queue threshold value and the predetermined increment threshold value or a predetermined minimum queue threshold value if the aggregate size of the plurality of packet queues is greater than or equal to the predetermined buffer threshold value.

28. An improved buffer management apparatus, wherein the buffer is shared among a plurality of packet queues, the improvement comprising:

means for computing a common queue threshold value based at least in part on the aggregate size of the plurality of packet queues and a predetermined buffer threshold value; and

means for computing a packet drop probability for each of the plurality of packet queues based at least in part on the common queue threshold value;

wherein the common queue threshold value and the respective packet drop probability are used to manage the size of each of the plurality of packet queues and thereby manage the buffer.