Method and apparatus for early random discard of packets

A method of randomly discarding a packet received from a network, comprising:

• identifying multiple regions in a packet storage device configured to store packets received from a network;
• maintaining a probability indicator configured to indicate a probability of discarding a packet received from the network, said probability indicator comprising N sub-indicators (N being a positive integer of 1 or more);
• maintaining a packet count, wherein said packet count:
• is incremented when a discardable packet is received from the network;
• and
• is repeatedly incrementable through N values;
• receiving a first packet from the network;
• and
• examining an Mth sub-indicator of said probability indicator to determine whether a packet stored in said packet storage device prior to said receiving is to be discarded when said packet count is M (M being a positive integer less than or equal to N).

A method of randomly discarding a packet received from a network, comprising:

• identifying multiple regions in a packet storage device configured to store packets received from a network;
• maintaining a probability of discarding a packet received from the network, wherein said probability comprises a set of indicators;
• receiving a first packet from the network;
• comparing said probability to a packet count to determine whether to discard a packet;
• discarding said packet if a first indicator of said set of indicators is in a first state, wherein said first indicator is associated with said packet count;
• and
• storing said packet in said packet storage device if said first indicator is in a second state.

A method of randomly discarding a packet received at a communication device from a network, comprising:

• identifying multiple regions in a packet queue, wherein said packet queue is configured to store packets received from a network;
• associating a probability indicator with one or more of said multiple regions;
• maintaining a counter configured to store a packet count, wherein said packet count is repeatedly incrementable through a pre-determined range of packet counts, and wherein said packet count is incremented when a discardable packet is received for storage in said packet queue;
• maintaining a traffic indicator to determine a level of traffic stored in said packet queue;
• receiving a packet from a network for storage in said packet queue;
• determining whether said packet is discardable;
• identifying a first region of said multiple regions, wherein said first region includes said level of traffic stored in said packet queue;
• examining said probability indicator to determine whether to discard said packet;
• and
• discarding said packet if said probability indicator comprises a first value.

A communication device for randomly discarding a packet received from a network, comprising:

• a packet buffer configured to store packets received from a network, wherein said packet buffer includes multiple regions and each said region is configured to store multiple packets;
• a packet counter configured to maintain a packet count, wherein said packet count is incremented only in response to receipt of a discardable packet from the network;
• a traffic indicator configured to identify a level of packets stored in said packet buffer;
• and
• a first probability indicator configured to indicate a probability of randomly dropping a packet when said level of packets is included in a first region of said multiple regions.

A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method for randomly discarding a packet from a network, the method comprising:

• identifying multiple regions in a packet storage device configured to store packets received from a network;
• maintaining a probability indicator configured to indicate a probability of discarding a packet received from said network, said probability indicator comprising N sub-indicators (N being a positive integer of 1 or more);
• maintaining a packet count, wherein said packet count:
• is incremented when a discardable packet is received from said network;
• and
• is repeatedly incrementable through N values;
• receiving a first packet from said network;
• and
• examining an Mth sub-indicator of said probability indicator to determine whether to discard said first packet when said packet count is M (M being a positive integer less than or equal to N).

A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of randomly discarding a packet received at a communication device from a network, the method comprising:

• identifying multiple regions in a packet queue, wherein said packet queue is configured to store packets received from a network;
• associating a probability indicator with one or more of said multiple regions;
• maintaining a counter configured to store a packet count, wherein said packet count is repeatedly incrementable through a pre-determined range of packet counts, and wherein said packet count is incremented when a discardable packet is received for storage in said packet queue;
• maintaining a traffic indicator to determine a level of traffic stored in said packet queue;
• receiving a packet from a network for storage in said packet queue;
• determining whether said packet is discardable;
• identifying a first region of said multiple regions, wherein said first region includes said level of traffic stored in said packet queue;
• examining said probability indicator to determine whether to discard said packet;
• and
• discarding said packet if said probability indicator comprises a first value.

A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of randomly discarding a packet from a network, the method comprising:

• identifying multiple regions in a packet storage device configured to store packets received from a network;
• maintaining a probability of discarding a packet received from the network;
• receiving a first packet from the network;
• comparing said probability to a packet count to determine whether to discard a packet;
• discarding said packet if a first indicator of said set of indicators is in a first state, wherein said first indicator is associated with said packet count;
• and
• storing said packet in said packet storage device if said first indicator is in a second state.

A communication interface configured for random early discard of packets, comprising:

• a packet buffer comprising multiple regions;
• a probability indicator configured to indicate a probability of discarding a packet received at the communication interface, said probability indicator comprising N sub-indicators (N being a positive integer of 1 or more);
• and
• a packet counter configured to maintain a packet count repeatedly incrementable through N values;
• wherein an Mth sub-indicator of said probability indicator is examined to determine whether to discard a packet when said packet count is M (M being a positive integer less than or equal to N).

A method of randomly discarding a packet received from a network, comprising:

• identifying multiple regions in a packet buffer configured to store packets received from a communication link, wherein each said region is configured to store multiple packets;
• maintaining a probability of discarding a packet received from the communication link;
• maintaining a packet count, wherein said packet count is incrementable only when a discardable packet is received from the communication link;
• receiving a first packet from the communication link;
• and
• applying said probability to determine whether to discard a packet.