Method and system for congestion avoidance in packet switching devices

A drop probability evaluation module for use in a physical device having (i) a processing fabric with at least one input port and at least one output port;

• (ii) a control entity connected to the at least one input port for regulating packet flow thereto;
• and (iii) a plurality of egress queues connected to the at least one output port for temporarily storing packets received therefrom, said drop probability evaluation module comprising:
• means for obtaining at a physical processing entity, bandwidth utilization information regarding packets received at the egress queues, wherein obtaining said bandwidth utilization information includes determining the amount of bandwidth consumed by packets received at each of said egress queues;
• means for determining, from the bandwidth utilization information and the amount of bandwidth consumed by packets received at each of said egress queues, a discard probability associated with each egress queue;
• and
• means for providing the discard probability associated with each egress queue to the control entity, for use by the control entity in selectively transmitting packets to the at least one input port of the processing fabric.

A drop probability evaluation module for use in a physical device having (i) a processing fabric with at least one input port and at least one output port;

• (ii) a control entity connected to the at least one input port for regulating packet flow thereto;
• and (iii) a plurality of egress queues connected to the at least one output port for temporarily storing packets received therefrom, said drop probability evaluation module including:
• an allocation processing entity, for determining an allocated traffic bandwidth for each of the egress queues;
• and
• a probability processing entity in communication with the allocation processing entity, said probability processing entity being adapted to receive the allocated traffic bandwidth for each of the egress queues from the allocation processing entity and also adapted to receive an average number of received traffic bytes, per time unit, for each of the egress queues from an external entity, the probability processing entity being operable to:
• compare the average number of received traffic bytes for each particular one of the egress queues to the allocated traffic bandwidth for the particular egress queue;
• and
• set the discard probability for the particular egress queue to the sum of a time average of previous values of the discard probability for the particular egress queue and either a positive or a negative increment, depending on whether the average number of received traffic bytes for the particular egress queue is greater or less than the allocated traffic bandwidth for the particular egress queue.

An apparatus, comprising:

• a processing fabric having at least one input port and at least one output port, the processing fabric being adapted to process packets received from the at least one input port and forward processed packets to the at least one output port;
• a plurality of egress queues, each connected to a corresponding one of the at least one output port of the processing fabric, each egress queue being adapted to (i) temporarily store packets received from the corresponding output port of the processing fabric and (ii) determine bandwidth utilization information on the basis of the packets received at the egress queues, by determining the amount of bandwidth consumed by packets received at each of said egress queues;
• a drop probability evaluation module connected to the egress queues, said drop probability evaluation entity being adapted to determine a discard probability associated with each of the egress queues on the basis of the bandwidth utilization information and the amount of bandwidth consumed by packets received at each of said egress queues;
• and
• a packet acceptance unit connected to the at least one input port of the processing fabric and to the drop probability evaluation module, the packet acceptance entity being adapted to (i) receive packets destined for the at least one output port of the processing fabric;
• (ii) identify an egress queue associated with each received packet;
• and (iii) on the basis of the discard probability associated with the egress queue associated with each received packet, either transmit or not transmit said received packet to one of the at least one input port of the processing fabric.