Dynamic color threshold in a queue

Abstract

A network device for dynamically allocating memory locations to plurality of queues. The network device includes means for determining an amount of memory buffers that is associated with a port, for assigning a fixed allocation of memory buffers to each of a plurality of queues associated with the port and for sharing remaining memory buffers among the plurality of queues. The remaining memory buffers are used by each of the plurality of queues after the fixed allocation of memory buffers assigned to the queue is used. The network device also includes means for setting a limit threshold for each of the plurality of queues. The limit threshold determines how much of the remaining memory buffer may be used by each of the plurality of queues. The network device further includes means for defining at least one color threshold for packets including a specified color marking and for defining a virtual maximum threshold. When one of the plurality of queues requests access to the remaining memory buffers and the remaining memory buffers is less than the limit threshold for the queue, the virtual maximum threshold is defined for the queue. The virtual maximum threshold replaces the limit threshold and packets associated with the at least one color threshold are processed in proportion with other color thresholds based on the virtual maximum threshold ceiling.

1 . A memory management controller of a network switching device having an ingress module for associating packets received at an ingress port of the network switching device with one of a plurality of colors, a memory management unit, and an egress module, the memory management unit associated with a plurality of queues for storing packets received from the ingress module prior to outputting the packets from the network device via the egress module, the memory management controller comprising:
 a resource guarantee module configured to determine a relative proportion of the plurality of colors to one another, and to determine memory locations available for use by the plurality of queues for the storing of the packets;   a memory allocation unit configured to receive a request for a subset of the available memory locations from one of the plurality of queues, and to determine that the request is associated with a potential inability of the memory management unit to maintain the relative proportion when storing the packets, and   a threshold determining unit configured to set a virtual maximum threshold for assigning the available memory locations to the plurality of queues, wherein   the memory allocation unit is configured to assign the memory locations to the plurality of queues in accordance with the virtual maximum threshold and the relative proportion, to thereby maintain the relative proportion during the storing of the packets.   
     
     
         2 . The memory management controller of  claim 1 , comprising:
 a determining unit configured to determine an amount of memory buffers of the memory locations that is associated with an egress port of the egress module, and configured to assign a fixed allocation of memory buffers to each of the plurality of queues associated with the port and for sharing remaining memory buffers of the memory locations among the plurality of queues, wherein the remaining memory buffers are used by each of the plurality of queues after the fixed allocation of memory buffers assigned to the queue is used; and   a setting unit configured to set a limit threshold for each of the plurality of queues, wherein the limit threshold determines how much of the remaining memory buffers may be used by each of the plurality of queues.   
     
     
         3 . The memory management controller of  claim 2 , comprising:
 a defining unit configured to define a plurality of color thresholds for each of the plurality of queues, wherein each of the plurality of color thresholds corresponds to the plurality of colors, and each of the plurality of color thresholds corresponds to a number of memory buffers,   wherein when one of the plurality of queues requests access to the remaining memory buffers and the remaining memory buffers is less than the limit threshold for the queue, the threshold determining unit is configured to set the virtual maximum threshold for the queue, wherein the virtual maximum threshold replaces the limit threshold.   
     
     
         4 . The memory management controller of  claim 3 , wherein the threshold determining unit is configured to calculate the virtual maximum threshold for each of the plurality of queues by dividing the remaining memory buffers by a sum of the number of queues and adding a quotient to a number of currently used buffers. 
     
     
         5 . The memory management controller of  claim 3 , further configured to track the remaining memory buffers with a dynamic register counter, wherein the dynamic register counter tracks the available memory buffers that are assigned to each port, to set an initial value of the dynamic register counter to a total number of memory buffers associated with the port minus a sum of the fixed allocation of memory buffers and to decrement the dynamic register counter when one of the plurality of queues uses one of the remaining memory buffers. 
     
     
         6 . The memory management controller of  claim 5 , further configured to increment the dynamic register counter when one of the plurality of queues releases one of the remaining memory buffers. 
     
     
         7 . The memory management controller of  claim 3 , wherein the determining unit is configured to determine if one of the plurality of queues has used less than its fixed allocation and to grant a buffer request by the one of the plurality of queues if queue has used less than the fixed allocation. 
     
     
         8 . The memory management controller of  claim 3 , wherein the determining unit is configured to determine if one of the plurality of queues has used more than its fixed allocation and to grant a buffer request by the one of the plurality of queues if an amount requested by the queue is less than the remaining memory buffer and less than the limit threshold for the queue. 
     
     
         9 . The memory management controller of  claim 1 , wherein the memory allocation unit is configured to drop packets based on their color and on the virtual maximum threshold in order to maintain the relative proportion. 
     
     
         10 . The memory management controller of  claim 1 , wherein the plurality of colors correspond to a priority level assigned to the packet. 
     
     
         11 . A method comprising:
 associating packets received at an ingress port of a network switching device with one of a plurality of colors; and   storing the packets at a memory management unit of the network switching device, the memory management unit associated with a plurality of queues for storing the packets prior to outputting the packets from the network device using an associated egress port thereof, the storing of the packets including
 determining a relative proportion of the plurality of colors to one another, 
 determining memory locations available for use by the plurality of queues for the storing of the packets, 
 receiving a request for a subset of the available memory locations from one of the plurality of queues, 
 determining that the request is associated with a potential inability of the memory management unit to maintain the relative proportion when storing the packets, 
 setting a virtual maximum threshold for assigning the available memory locations to the plurality of queues, and 
 assigning the memory locations to the plurality of queues in accordance with the virtual maximum threshold and the relative proportion, to thereby maintain the relative proportion during the storing of the packets. 
   
     
     
         12 . The method of  claim 11 , wherein determining the memory locations comprises determining an amount of memory buffers of the memory locations that is associated with an egress port of the egress module, and wherein assigning the memory locations comprises
 assigning a fixed allocation of memory buffers to each of the plurality of queues associated with the port,   sharing remaining memory buffers of the memory locations among the plurality of queues, wherein the remaining memory buffers are used by each of the plurality of queues after the fixed allocation of memory buffers assigned to the queue is used; and   setting a limit threshold for each of the plurality of queues, wherein the limit threshold determines how much of the remaining memory buffers may be used by each of the plurality of queues.   
     
     
         13 . The method of  claim 12 , comprising:
 defining a plurality of color thresholds for each of the plurality of queues, wherein each of the plurality of color thresholds corresponds to the plurality of colors, and each of the plurality of color thresholds corresponds to a number of memory buffers,   wherein when one of the plurality of queues requests access to the remaining memory buffers and the remaining memory buffers is less than the limit threshold for the queue, the virtual maximum threshold is set for the queue and replaces the limit threshold.   
     
     
         14 . The method of  claim 13 , wherein setting the virtual maximum threshold comprises setting the virtual maximum threshold for each of the plurality of queues by dividing the remaining memory buffers by a sum of the number of queues and adding a quotient to a number of currently used buffers. 
     
     
         15 . The method of  claim 13 , wherein storing the packets comprises:
 tracking the remaining memory buffers with a dynamic register counter, wherein the dynamic register counter tracks the available memory buffers that are assigned to each port,   setting an initial value of the dynamic register counter to a total number of memory buffers associated with the port minus a sum of the fixed allocation of memory buffers, and   decrementing the dynamic register counter when one of the plurality of queues uses one of the remaining memory buffers.   
     
     
         16 . The method of  claim 15 , comprising incrementing the dynamic register counter when one of the plurality of queues releases one of the remaining memory buffers. 
     
     
         17 . A network device for dynamically allocating memory locations to a plurality of queues, the network device comprising:
 an ingress module configured to associate packets received at an ingress port of the network switching device with one of a plurality of colors;   a memory management unit associated with a plurality of queues for storing packets received from the ingress module; and   an egress module configured to receive the packets from the memory management unit and configured to output the packets using an egress port of the network device,   wherein the memory management unit is configured to:   determine a relative proportion of the plurality of colors to one another, and to determine memory locations available for use by the plurality of queues for the storing of the packets;   receive a request for a subset of the available memory locations from one of the plurality of queues, and to determine that the request is associated with a potential inability of the memory management unit to maintain the relative proportion when storing the packets,   set a virtual maximum threshold for assigning the available memory locations to the plurality of queues, and   assign the memory locations to the plurality of queues in accordance with the virtual maximum threshold and the relative proportion, to thereby maintain the relative proportion during the storing of the packets.   
     
     
         18 . The network device of  claim 17 , wherein the memory management unit is further configured to:
 determine an amount of memory buffers of the memory locations that is associated with an egress port of the egress module;   assign a fixed allocation of memory buffers to each of the plurality of queues associated with the port and for sharing remaining memory buffers of the memory locations among the plurality of queues, wherein the remaining memory buffers are used by each of the plurality of queues after the fixed allocation of memory buffers assigned to the queue is used; and   set a limit threshold for each of the plurality of queues, wherein the limit threshold determines how much of the remaining memory buffers may be used by each of the plurality of queues.   
     
     
         19 . The network device of  claim 18 , wherein the memory management unit is further configured to:
 define a plurality of color thresholds for each of the plurality of queues, wherein each of the plurality of color thresholds corresponds to the plurality of colors, and each of the plurality of color thresholds corresponds to a number of memory buffers,   wherein when one of the plurality of queues requests access to the remaining memory buffers and the remaining memory buffers is less than the limit threshold for the queue, the threshold determining unit is configured to set the virtual maximum threshold for the queue, wherein the virtual maximum threshold replaces the limit threshold.   
     
     
         20 . The network device of  claim 19 , wherein the memory management unit is further configured to calculate the virtual maximum threshold for each of the plurality of queues by dividing the remaining memory buffers by a sum of the number of queues and adding a quotient to a number of currently used buffers.