Method and system for congestion avoidance in packet switching devices
First Claim
1. A method of regulating packet flow through a device having a processing fabric with at least one input port and at least one output port, a control entity connected to the at least one input port for regulating packet flow thereto, and a plurality of egress queues connected to the at least one output port for temporarily storing packets received therefrom, said method comprising:
- obtaining bandwidth utilization information regarding packets received at the egress queues;
determining, from the bandwidth utilization information, a discard probability associated with each egress queue; and
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.
9 Assignments
0 Petitions
Accused Products
Abstract
A method, apparatus and computer-readable storage medium for regulating packet flow through a device such as a router with a switch fabric. Congestion information, such as statistics on bandwidth utilization, is collected for each of a plurality of queues at an egress stage of the device. Based on the bandwidth utilization statistics, computations are performed to evaluate a “discard probability” for each queue. This information is transmitted to the ingress stage, either periodically or at other controlled time periods, such as when the discard probability changes significantly. The ingress stage can then proceed with controllable transmission or non-transmission of packets to the switch fabric, depending on the queue for which the packet is destined and also depending on the discard probability for that queue. In this way, congestion can be avoided even before it even has a chance to occur. This leads to improved bandwidth utilization, since packets which are discarded at the ingress stage will not unnecessarily take up other resources in the device.
62 Citations
58 Claims
-
1. A method of regulating packet flow through a device having a processing fabric with at least one input port and at least one output port, a control entity connected to the at least one input port for regulating packet flow thereto, and a plurality of egress queues connected to the at least one output port for temporarily storing packets received therefrom, said method comprising:
-
obtaining bandwidth utilization information regarding packets received at the egress queues;
determining, from the bandwidth utilization information, a discard probability associated with each egress queue; and
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. A drop probability evaluation module for use in a 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 bandwidth utilization information regarding packets received at the egress queues;
means for determining, from the bandwidth utilization information, 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.
- (ii) a control entity connected to the at least one input port for regulating packet flow thereto; and
-
38. A drop probability evaluation module for use in a 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 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. - View Dependent Claims (39)
- (ii) a control entity connected to the at least one input port for regulating packet flow thereto; and
-
40. 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 find (ii) determine bandwidth utilization information on the basis of the packets received at the 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
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. - View Dependent Claims (41, 42, 43)
-
-
44. A method of regulating packet flow through a device having a processing fabric with at least one input port and at least one output port, a control entity connected to the at least one input port for regulating packet flow thereto, and a plurality of egress queues connected to the at least one output port for temporarily storing packets received therefrom, each packet having a corresponding priority selected from a group of priorities, said method comprising:
-
obtaining bandwidth utilization information regarding packets received at the egress queues;
determining, from the bandwidth utilization information, a discard probability associated with each of the egress queues and each of the priorities; and
providing the discard probability associated with each egress queue and priority 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. - View Dependent Claims (45)
-
-
46. A method of regulating packet flow through a device having an ingress entity, an egress entity, a processing fabric between the ingress entity and the egress entity, and a control entity adapted to process packets prior to transmission thereof to the ingress entity, said method comprising:
-
obtaining congestion information regarding packets received at the egress entity; and
providing the congestion information to the control entity, for use by the control entity in processing packets prior to transmission thereof to the ingress entity. - View Dependent Claims (47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58)
-
Specification