Flexible and hierarchical dynamic buffer allocation

• US 8,149,710 B2
• Filed: 07/05/2007
• Issued: 04/03/2012
• Est. Priority Date: 07/05/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bergamasco, Davide, Alaria, Valentina, Piglione, Chiara, Caramello, Michele
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Bokhari, Syed M
• Application Number:
  US11/825,631
• Publication Number:
  US 20090010162A1
• Time in Patent Office: 1,734 Days
• Field of Search: 370/235, 370/412, 370/395.41, 370/395.7, 370/331, 370/230.1, 710/52
• US Class Current: 370/235
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools

Abstract

In one embodiment, a method comprises the following steps: receiving a first set of inputs comprising a first plurality of entities and a first traffic behavior; determining a first region of a buffer corresponding to the first traffic behavior; assigning the first plurality of entities to the first region; determining hierarchical relationships between at least some of the first plurality of entities; determining a first shared buffer space of the first region; and assigning at least one threshold for each of the first plurality of entities. The threshold may comprise a maximum amount of the first shared buffer space that may be allocated to an entity. The method may also involve configuring a logic device to allocate the first shared buffer space dynamically according to the hierarchical relationships and the thresholds.

Claims

1. A method, comprising:

receiving a first set of inputs indicating a first plurality of entities and a first traffic behavior implemented by each of the first plurality of entities;

determining a first region of a buffer corresponding to the first traffic behavior;

assigning the first plurality of entities to the first region;

determining hierarchical relationships among the first plurality of entities implementing the first traffic behavior, wherein the hierarchical relationships are defined via a tree data structure;

determining a first shared buffer space of the first region;

assigning at least one threshold for each of the first plurality of entities, the threshold comprising a maximum amount of the first shared buffer space that may be allocated to an entity; and

configuring a logic device to allocate the first shared buffer space dynamically according to the hierarchical relationships and the thresholds.

2. The method of claim 1, wherein the assigning step comprises assigning static thresholds.

3. The method of claim 1, wherein the assigning step comprises assigning adaptive thresholds for at least a portion of the first plurality of entities.

4. The method of claim 1, further comprising:

receiving a second set of inputs indicating a second plurality of entities and a second traffic behavior implemented by the second plurality of entities;

determining a second region of the buffer corresponding to the second traffic behavior; and

assigning the second plurality of entities to the second region.

5. The method of claim 1, further comprising determining that the first traffic behavior is the only traffic behavior implemented by the first plurality of entities, wherein step of determining the first region of the buffer comprises determining that the first region comprises all of the buffer.

6. The method of claim 1, wherein the configuring step comprises configuring the logic device to allocate an entity'"'"'s buffer space among sub-entities of the entity.

7. The method of claim 1, further comprising determining a reserved buffer space for each of the first plurality of entities.

8. The method of claim 1, wherein the first traffic behavior is no drop behavior, the method further comprising establishing a latency buffer space within the first region, the latency buffer space reserved for implementing a flow control mechanism.

9. The method of claim 3, further comprising configuring the logic device to determine activity levels of the portion of the first plurality of entities and to change the adaptive thresholds according to determined activity levels.

10. The method of claim 9, wherein determining activity levels comprises determining a number of active entities in the first plurality of entities.

11. The method of claim 1, wherein a minimum amount of the first region of the buffer is reserved for each of the first plurality of entities.

12. The method of claim 1, wherein entities at a same level of the tree data structure share a corresponding sub-region of the first region of the buffer.

13. The method of claim 12, wherein buffer space of an entity is shared among sub-entities of the entity.

14. The method of claim 1, wherein buffer space reserved for an entity is determined by a sum of amounts of buffer space reserved for child nodes of the entity.

15. The method of claim 1, wherein the first plurality of entities are not at the same level of the tree data structure.

16. The method of claim 1, wherein the first plurality of entities are at two or more levels of the tree data structure.

17. An apparatus, comprising:

means for receiving a first set of inputs indicating a first plurality of entities and a first traffic behavior implemented by each of the first plurality of entities;

means for determining a first region of a buffer corresponding to the first traffic behavior;

means for assigning the first plurality of entities to the first region;

means for determining hierarchical relationships among the first plurality of entities implementing the first traffic behavior, wherein the hierarchical relationships are defined via a tree data structure;

means for determining a first shared buffer space of the first region;

means for assigning at least one threshold for each of the first plurality of entities, the threshold comprising a maximum amount of the first shared buffer space that may be allocated to an entity; and

means for configuring a logic device to allocate the first shared buffer space dynamically according to the hierarchical relationships and the thresholds.

18. The method of claim 17, wherein the assigning means comprises means for assigning adaptive thresholds for at least a portion of the first plurality of entities.

19. The method of claim 17,

wherein the receiving means comprises means for receiving a second set of inputs indicating a second plurality of entities and a second traffic behavior implemented by the second plurality of entities;

wherein the determining means comprises means for determining a second region of a buffer corresponding to the second traffic behavior; and

wherein the assigning means comprises means for assigning the second plurality of entities to the second region.

20. An apparatus, comprising:

a first plurality of ports;

a buffer; and

a logic device configured to do the following;

obtain a first set of inputs indicating a first plurality of entities and a first traffic behavior implemented by each of the first plurality of entities;

determine a first region of a buffer corresponding to the first traffic behavior;

assign the first plurality of entities to the first region;

determine hierarchical relationships among the first plurality of entities implementing the first traffic behavior, wherein the hierarchical relationships are defined via a tree data structure;

determine a first shared buffer space of the first region;

assign at least one threshold for each of the first plurality of entities, the threshold comprising a maximum amount of the first shared buffer space that may be allocated to an entity; and

configure a logic device to allocate the first shared buffer space dynamically according to the hierarchical relationships and the thresholds.

21. The apparatus of claim 20, wherein the logic device is further configured to modify a maximum amount of the shared portion of the buffer that is allocated to each port according to a corresponding port activity level.

22. The apparatus of claim 20, wherein the logic device is further configured to do the following:

determine a traffic behavior for a frame received via one of the plurality of ports; and

store the frame in a region of the buffer corresponding to the traffic behavior that has been determined.

23. The apparatus of claim 20, wherein the logic device is further configured to allocate a port'"'"'s buffer space among sub-entities of the port.

24. The apparatus of claim 22, wherein the traffic behavior is no drop traffic behavior and wherein the region is a no drop region.

25. The apparatus of claim 24, wherein no drop region comprises a latency buffer space reserved for implementing a flow control mechanism and wherein the logic device is configured for implementing, at least in part, the flow control mechanism.