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

Abstract

The invention is to use the ability of a switching fabric to set a congestion indicator bit in a segment if any queue through which the segment passes is filled above a lower threshold. The output linecard monitors the field of the congestion indicator bit as it receives segments from the switching fabric. The output linecard periodically calculates the ratio of segments having the congestion bit set to all segments routed to a particular port. The periodically calculated ratio is used as an input parameter to a Random Early Detection (RED) algorithm. The RED algorithm selects a packet for the output linecard to drop, by use of a random selection method. The destination computer then does not receive the packet. The random selection of packets to drop has the effect of helping to prevent undesirable network synchronization of transmission of replacement packets. With adaptive source computers, the network device then does not reach a congested state, thereby maintaining optimum throughput for the computer network. When an ATM switching fabric is used with ATM cells for the segments, then the Explicit Forward Congestion Indication Field (EFCI bit) of a data cell is used to mark a data cell which has passed through a queue which is filled above a lower threshold level. Data cells arriving at the output line card with the EFCI bit set are then counted, and this count is used in the periodic calculation of the ratio used as input to the RED algorithm.