Per-flow dynamic buffer management

• US 7,215,641 B1
• Filed: 11/02/2004
• Issued: 05/08/2007
• Est. Priority Date: 01/27/1999
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheriton, David R., Bechtolsheim, Andreas V.
• Primary Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US10/979,928
• Time in Patent Office: 917 Days
• Field of Search: 370/235, 370/229, 370/230, 370/231, 370/389, 370/392, 370/395.31, 370/395.32, 370/401, 370/412, 370/428, 370/429
• US Class Current: 370/235
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9005 using dynamic buffer space allocation

Abstract

The present invention provides a per-flow dynamic buffer management scheme for a data communications device. With per-flow dynamic buffer limiting, the header information for each packet is mapped into an entry in a flow table, with a separate flow table provided for each output queue. Each flow table entry maintains a buffer count for the packets currently in the queue for each flow. On each packet enqueuing action, a dynamic buffer limit is computed for the flow and compared against the buffer count already used by the flow to make a mark, drop, or enqueue decision. A packet in a flow is dropped or marked if the buffer count is above the limit. Otherwise, the packet is enqueued and the buffer count incremented by the amount used by the newly-enqueued packet. The scheme operates independently of packet data rate and flow behavior, providing means for rapidly discriminating well-behaved flows from non-well-behaved flows in order to manage buffer allocation accordingly. Additionally, the present invention adapts to changing flow requirements by fairly sharing buffer resources among both well-behaved and non-well-behaved flows.

Claims

1. A system comprising a plurality of input devices a plurality of buffers, and a plurality of output queues interoperably connected to each other, the system further comprising a computer readable medium encoded with computer instructions executable by a processor for:

extracting at least one field from a data packet received via one of the plurality of input devices;

determining a flow table index value from the at least one field, wherein the flow table index value belongs to a first set of values, and wherein a maximum number of values in the first set of values is less than a maximum number of possible flows;

reading a flow table entry corresponding to the flow table index value; and

comparing the flow table entry with a buffer limit value.

2. The system of claim 1 wherein the at least one field from a data packet includes a source address field and a destination address field.

3. The system of claim 1 further comprising computer instructions for:

storing the flow table index value.

4. The system of claim 3 wherein the computer instructions for storing the flow table index value further comprise computer instructions for storing the flow table index value in a packet description field corresponding to a queue.

5. The system of claim 1 wherein the at least one field from a data packet includes a first field and a second field, and wherein the computer instructions for determining a flow table index value further comprise computer instructions for:

concatenating at least a portion of the first field and at least a portion of the second field to form a key.

6. The system of claim 5 further comprising computer instructions for:

accessing at least one of a content addressable memory and a cache memory using the key.

7. The system of claim 1 wherein the buffer limit value represents an upper bound of memory space to be allocated to the data packet.

8. The system of claim 1 further comprising computer instructions for:

reading the buffer limit value from a table.

9. The system of claim 1 further comprising computer instructions for:

computing the buffer limit value when needed.

10. The system of claim 1 wherein the buffer limit value is based on at least one parameter describing a queue.

11. The system of claim 10 wherein the buffer limit value is further based on a tuning parameter.

12. The system of claim 1 further comprising computer instructions for:

computing the buffer limit value using at least one of a maximum constraint and a minimum constraint.

13. The system of claim 1 further comprising computer instructions for:

computing the buffer limit value using at least one of a round-trip time of transmission and an estimated round-trip time of transmission.

14. The system of claim 1 further comprising for:

taking an action on the packet based on the comparing the flow table entry with a buffer limit value.

15. A system comprising a plurality of input devices, a plurality of buffers, and a plurality of output queues interoperably connected to each other, the system further comprising a computer readable medium encoded with computer instructions executable by a processor for:

extracting at least one field from a data packet received via one of the plurality of input devices, wherein the at least one field from a data packet includes a source address field and a destination address field;

determining a flow table index value from the at least one field, wherein the computer instructions for determining a flow table index value further comprise computer instructions for at least one of;

adding the source address field to the destination address field;

performing an exclusive OR (XOR) operation using the source address field and the destination address field as operands; and

adding the source address field to the destination address field to form a sum and performing a bit-wise shift operation on at least a portion of the sum;

reading a flow table entry corresponding to the flow table index value; and

comparing the flow table entry with a buffer limit value.

16. A system comprising a plurality of input devices, a plurality of buffers, and a plurality of output queues interoperably connected to each other, the system further comprising a computer readable medium encoded with computer instructions executable by a processor for:

extracting at least one field from a data packet received via one of the plurality of input devices;

determining a flow table index value from the at least one field, wherein the computer instructions for determining a flow table index value further comprise computer instructions for using a first hashing algorithm, and wherein the system further comprises computer instructions for;

determining a second flow table index value from the at least one field using a second hashing algorithm;

reading a flow table entry corresponding to the flow table index value; and

comparing the flow table entry with a buffer limit value.

17. The system of claim 16 wherein the first hashing algorithm and the second hashing algorithm differ by a seed value.

18. A system comprising a plurality of input devices, a plurality of buffers, and a plurality of output queues interoperably connected to each other, the system further comprising a computer readable medium encoded with computer instructions executable by a processor for:

extracting at least one field from a data packet received via one of the plurality of input devices;

determining a flow table index value from the at least one field;

reading a flow table entry corresponding to the flow table index value;

computing a table index based on at least one parameter describing a queue; and

reading a buffer limit value from a table, wherein the reading further comprises

selecting the buffer limit value from the table using the table index; and

comparing the flow table entry with the buffer limit value.

19. The system of claim 18 wherein the at least one parameter includes at least one of a maximum queue length value, a number of flows value, and a current queue length value.

20. A computer readable medium comprising program instructions executable on a processor, the computer readable medium being at least one of an electronic storage medium, a magnetic storage medium, or an optical storage medium, wherein the program instructions are executed to implement each of:

extracting at least one field from a data packet received via one of a plurality of input devices;

determining a flow table index value from the at least one field, wherein the flow table index value belongs to a first set of values, and wherein a maximum number of values in the first set of values is less than a maximum number of possible flows;

reading a flow table entry corresponding to the flow table index value; and

comparing the flow table entry with a buffer limit value.

21. The computer readable medium of claim 20 wherein the at least one field from a data packet includes a source address field and a destination address field.

22. The computer readable medium of claim 20 further comprising program instructions executed to implement:

storing the flow table index value.

23. The computer readable medium of claim 22 wherein the program instructions executed to implement storing the flow table index value further comprise program instructions executed to implement storing the flow table index value in a packet description field corresponding to a queue.

24. The computer readable medium of claim 20 wherein the at least one field from a data packet includes a first field and a second field, and wherein the program instructions executed to implement determining a flow table index value further comprise program instructions executed to implement:

concatenating at least a portion of the first field and at least a portion of the second field to form a key.

25. The computer readable medium of claim 24 further comprising program instructions executed to implement:

accessing at least one of a content addressable memory and a cache memory using the key.

26. The computer readable medium of claim 20 wherein the buffer limit value represents an upper bound of memory space to be allocated to the data packet.

27. The computer readable medium of claim 20 further comprising program instructions executed to implement:

reading the buffer limit value from a table.

28. The computer readable medium of claim 20 further comprising program instructions executed to implement:

computing the buffer limit value when needed.

29. The computer readable medium of claim 20 wherein the buffer limit value is based on at least one parameter describing a queue.

30. The computer readable medium of claim 29 wherein the buffer limit value is further based on a tuning parameter.

31. The computer readable medium of claim 20 further comprising program instructions executed to implement:

computing the buffer limit value using at least one of a maximum constraint and a minimum constraint.

32. The computer readable medium of claim 20 further comprising program instructions executed to implement:

computing the buffer limit value using at least one of a round-trip time of transmission and an estimated round-trip time of transmission.

33. The computer readable medium of claim 20 further comprising program instructions executed to implement:

taking an action on the packet based on the comparing the flow table entry with a buffer limit value.

34. A computer readable medium comprising program instructions executable on a processor, the computer readable medium being at least one of an electronic storage medium, a magnetic storage medium, or an optical storage medium, wherein the program instructions are executed to implement each of:

extracting at least one field from a data packet received via one of a plurality of input devices wherein the at least one field from a data packet includes a source address field and a destination address field;

determining a flow table index value from the at least one field;

wherein the program instructions executed to implement the determining a flow table index value further comprise program instructions executed to implement at least one of;

adding the source address field to the destination address field;

performing an exclusive OR (XOR) operation using the source address field and the destination address field as operands; and

adding the source address field to the destination address field to form a sum and performing a bit-wise shift operation on at least a portion of the sum;

reading a flow table entry corresponding to the flow table index value; and

comparing the flow table entry with a buffer limit value.

35. A computer readable medium comprising program instructions executable on a processor, the computer readable medium being at least one of an electronic storage medium, a magnetic storage medium, or an optical storage medium, wherein the program instructions are executed to implement each of:

extracting at least one field from a data packet received via one of a plurality of input devices;

determining a flow table index value from the at least one field;

wherein the program instructions executed to implement the determining a flow table index value further comprise program instructions executed to use a first hashing algorithm, and wherein the computer readable medium further comprises program instructions executed to implement;

determining a second flow table index value from the at least one field using a second hashing algorithm;

reading a flow table entry corresponding to the flow table index value; and

comparing the flow table entry with a buffer limit value.

36. The computer readable medium of claim 35 wherein the first hashing algorithm and the second hashing algorithm differ by a seed value.

37. A computer readable medium comprising program instructions executable on a processor, the computer readable medium being at least one of an electronic storage medium, a magnetic storage medium, or an optical storage medium, wherein the program instructions are executed to implement each of:

extracting at least one field from a data packet received via one of a plurality of input devices;

determining a flow table index value from the at least one field;

reading a flow table entry corresponding to the flow table index value;

computing a table index based on at least one parameter describing a queue; and

reading a buffer limit value from a table, wherein the reading further comprises selecting the buffer limit value from the table using the table index; and

comparing the flow table entry with the buffer limit value.

38. The computer readable medium of claim 37 wherein the at least one parameter includes at least one of a maximum queue length value, a number of flows value, and a current queue length value.