US 6,556,578 B1 · Early fair drop buffer management method

Abstract

A method for managing a buffer pool containing a plurality of queues is based on consideration of both (a) when to drop a packet and (b) from which queue the packet should be dropped. According to the method a packet drop is signaled with the global average queue occupancy exceeds a maximum threshold and is signaled on a probabilistic basis when the global occupancy is between a minimum threshold and the maximum threshold. Each queue has a particular local threshold value associated with it and is considered to be “offending” when its buffer occupancy exceeds its local threshold. When a packet drop is signaled, one of the offending queues is selected using a hierarchical, unweighted round robin selection scheme which ensures that offending queues are selected in a fair manner. A packet is then dropped from the selected offending queue.

Claims32

Dependent claims

A method for managing a buffer pool receiving data packets from a plurality of flows and buffering said packets in a plurality of queues, said method comprising the steps of:

(a) determining a global average queue occupancy avg for the plurality of queues;
(b) determining that a packet must be dropped if the global average queue occupancy exceeds a predetermined maximum threshold maxth;
(c) determining for each one of said queues a local threshold and a buffer occupancy;
(d) evaluating at least one of said queues, in response to the determination that a packet must be dropped, to identify offender queues having a respective buffer occupancy exceeding the respective local threshold;
(e) selecting, in response to the identification of at least one offender queue, a particular one of said identified offender queues;
and
(f) dropping a packet from said selected offender queue.

4 more elements

A method for managing a buffer pool receiving data packets from a plurality of flows and buffering said packets in a plurality of queues, said buffer pool being organized as a hierarchically weighted tree having a root node and a plurality of descendant nodes including a plurality of leaf nodes in one-to-one correspondence with each of said plurality of queues, said method comprising the steps of:

(a) periodically determining a global average queue occupancy avg for the plurality of queues;
(b) determining that a packet must be dropped if the global average queue occupancy exceeds a predetermined maximum threshold maxth;
(c) determining for each of said plurality of descendant nodes a nominal buffer allocation;
(d) determining for each of said plurality of descendant nodes a buffer occupancy, wherein a descendant node is offending when the respective buffer occupancy exceeds the respective nominal buffer allocation;
(e) traversing the tree starting from the root node in response to the determination that a packet must be dropped until reaching a particular leaf node by selecting a traversal path at each level from among immediate descendant nodes which are offending;
and
(f) dropping a packet from the queue in correspondence with the particular leaf node.

4 more elements

A network node comprising:

at least one output port;
a plurality of input ports for receiving respective data packet flows;
a plurality of queues stored in a memory, each queue associated with a respective input port, data packets received at a particular input from the respective flow to be added to the respective queue associated with the particular input;
and
a processor configured to manage the contents of the queues in said network node, the processor configured to perform the following functions:
(a) determining a global average queue occupancy avg for the plurality of queues;
(b) determining that a packet must be dropped if the global average queue occupancy exceeds a predetermined maximum threshold maxth;
(c) determining for each one of said queues a local threshold and a buffer occupancy;
(d) evaluating at least one of said queues, in response to the determination that a packet must be dropped, to identify offender queues having a respective buffer occupancy exceeding the respective local threshold;
(e) selecting, in response to the identification of at least one offender queue, a particular one of said identified offender queues;
and
(f) dropping a packet from said selected offender queue.

9 more elements

A network node comprising:

at least one output port;
a plurality of input ports for receiving respective data packet flows;
a buffer pool including a plurality of queues stored in a memory, each queue associated with a respective input port, data packets received at a particular input from the respective flow to be added to the respective queue associated with the particular input, said buffer pool being organized as a hierarchically weighted tree having a root node and a plurality of descendant nodes including a plurality of leaf nodes in one-to-one correspondence with each of said plurality of queues;
and
a processor configured to manage the contents of the queues in said network node, the processor configured to perform the following functions:
(a) periodically determining a global average queue occupancy avg for the plurality of queues;
(b) determining that a packet must be dropped if the global average queue occupancy exceeds a predetermined maximum threshold maxth;
(c) determining for each of said plurality of descendant nodes a nominal buffer allocation;
(d) determining for each of said plurality of descendant nodes a buffer occupancy, wherein a descendant node is offending when the respective buffer occupancy exceeds the respective nominal buffer allocation;
(e) traversing the tree starting from the root node in response to the determination that a packet must be dropped until reaching a particular leaf node by selecting a traversal path at each level from among immediate descendant nodes which are offending;
and
(f) dropping a packet from the offender queue in correspondence with the particular leaf node.

9 more elements

Dependencies are inferred from the claim text.

Early fair drop buffer management method

Life of this patent

Early fair drop buffer management method

Life of this patent

Abstract

Claims32