Random early detection (RED) algorithm using marked segments to detect congestion in a computer network

A network device, comprising:

• a first linecard receiving input computer network packets from a computer network, said line card translating said packets into segments;
• a switching fabric receiving segments from said linecard, said switching fabric to route said segments to a desired output linecard, said switching fabric having at least one queue therein, said queue having a threshold such that in the event that a segment arrives at said queue and said queue is filled above said threshold, a bit of said segment is set as said segment is passed out of said queue, said bit being set “marking” said segment as that segment having passed through a queue filled above said lower threshold level;
• a second line card receiving said segments from said switching fabric, said second linecard translating said segments into a computer network packet for transmission by said second linecard out through a port connected to an output computer network;
• a circuit determining whether or not a particular segment of said segments received by said second linecard has said bit set indicating that said segment is marked, and in response to detecting a segment as being marked, discarding said output packet in accordance with a random probability, and in response to detecting that no segment of said output packet is marked, transmitting said output packet onto said computer network;
• said circuit counting a total number of segments received by said output linecard;
• said circuit counting a number of said segments received by said linecard which are marked;
• said circuit calculating a ratio R by dividing said number of marked segments by said total number of segments;
• said circuit calculating a random number, said random number having a value between zero and a maximum value of said ratio R;
• and
• said circuit causing said packet to be discarded in the event that said ratio R is greater than said random number.

A method for operating a network device, comprising:

• receiving computer network packets from an input computer network;
• translating said packets into segments;
• receiving said segments in a switching fabric, said switching fabric to route said segments to a desired output linecard, said switching fabric having at least one queue therein, said queue having a threshold such that in the event that a segment arrives at said queue and said queue is filled above said threshold, a bit of said segment is set as said segment is passed out of said queue, said bit being set “marking” said segment as that segment having passed through a queue filled above said threshold level;
• receiving said segment from said switching fabric by an output linecard, said output linecard translating said segments into a computer network packet for transmission by said output linecard out through a port connected to an output computer network;
• determining whether or not a particular segment of said segments received by said output linecard has said bit set indicating that said segment is marked;
• discarding said output packet, in response to detecting a segment as being marked, in accordance with a random probability, and in response to detecting that no segment of said output packet is marked, transmitting said output packet onto said computer network.

A method for operating a network device, comprising:

• receiving computer network packets from an input computer network;
• translating said packets into segments;
• receiving said segments in a switching fabric, said switching fabric to route said segments to a desired output linecard, said switching fabric having at least one queue therein, said queue having a threshold such that in the event that a segment arrives at said queue and said queue is filled above said threshold, a bit of said segment is set as said segment is passed out of said queue, said bit being set “marking” said segment as that segment having passed through a queue filled above said threshold level;
• receiving said segment from said switching fabric by an output linecard, said output linecard translating said segments into a computer network packet for transmission by said output linecard out through a port connected to an output computer network;
• determining whether or not a particular segment of said segments received by said output linecard has said bit set indicating that said segment is marked;
• discarding said output packet, in response to detecting a segment as being marked, in accordance with a random probability, and in response to detecting that no segment of said output packet is marked, transmitting said output packet onto said computer network;
• counting a total number of segments received by said output linecard;
• counting a number of said segments received by said linecard which are marked;
• calculating a ratio R by dividing said number of marked segments by said total number of segments, the value of ratio R having a maximum value;
• calculating a random number, said random number having a value between zero and said maximum value of ratio R;
• and
• causing said packet to be discarded in the event that said ratio R is greater than said random number.

A computer readable medium containing instructions for performing the method of,

• receiving computer network packets from an input computer network;
• translating said packets into segments;
• receiving said segments in a switching fabric, said switching fabric to route said segments to a desired output linecard, said switching fabric having at least one queue therein, said queue having a threshold such that in the event that a segment arrives at said queue and said queue is filled above said threshold, a bit of said segment is set as said segment is passed out of said queue, said bit being set “marking” said segment as that segment having passed through a queue filled above said threshold level;
• receiving said segment from said switching fabric by an output linecard, said output linecard translating said segments into a computer network packet for transmission by said output linecard out through a port connected to an output computer network;
• determining whether or not a particular segment of said segments received by said output linecard has said bit set indicating that said segment is marked;
• discarding said output packet, in response to detecting a segment as being marked, in accordance with a random probability, and in response to detecting that no segment of said output packet is marked, transmitting said output packet onto said computer network.

A method for use in a network device, the method comprising the steps of:

• receiving an input packet at an input linecard;
• translating the input packet into segments;
• forwarding the segments to a switching fabric, the switching fabric having at least one queue;
• setting a bit in a particular segment as “marked” in the event the particular segment passes through a queue filled above a threshold;
• forwarding the segments to an appropriate output linecard;
• translating the segments into an output packet;
• and
• discarding the output packet, in accordance with a random probability, in the event a particular segment of the output packet is marked.

A network device, comprising:

• means for receiving an input packet at an input linecard;
• means for translating the input packet into segments;
• means for forwarding the segments to a switching fabric, the switching fabric having at least one queue;
• means for setting a bit in a particular segment as “marked” in the event the particular segment passes through a queue filled above a threshold;
• means for forwarding the segments to an appropriate output linecard;
• means for translating the segments into an output packet;
• and
• means for discarding the output packet, in accordance with a random probability, in the event a particular segment of the output packet is marked.

A computer readable medium, comprising:

• the computer readable media containing instructions for execution on a processor for the practice of the method of,
• receiving an input packet at an input linecard;
• translating the input packet into segments;
• forwarding the segments to a switching fabric, the switching fabric having at least one queue;
• setting a bit in a particular segment as “marked” in the event the particular segment passes through a queue filled above a threshold;
• forwarding the segments to an appropriate output linecard;
• translating the segments into an output packet;
• and
• discarding the output packet, in accordance with a random probability, in the event a particular segment of the output packet is marked.