Method and system for managing congestion in a network

• US 6,657,962 B1
• Filed: 04/10/2000
• Issued: 12/02/2003
• Est. Priority Date: 04/10/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation, Alcatel SA (Nokia Corporation)
• Original Assignee: International Business Machines Corporation, Alcatel SA (Nokia Corporation)
• Inventors: Clemminck, Ivan Oscar, Jeffries, Clark Debs, Vrana, Miroslav, Calvignac, Jean Louis, Siegel, Michael Steven, Verplanken, Fabrice Jean, Heddes, Marco C., Bass, Brian Mitchell, Barri, Peter Irma August
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): LY, ANH VU H
• Application Number:
  US09/546,651
• Time in Patent Office: 1,331 Days
• Field of Search: 370/230, 370/230.1, 370/231, 370/232, 370/234, 370/235, 370/236, 370/389, 370/395.21, 370/395.42, 370/395.71, 370/395.72, 370/413, 370/419, 370/428, 370/429
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A system for minimizing congestion in a communication system is disclosed. The system comprises at least one ingress system for providing data. The ingress system includes a first free queue and a first flow queue. The system also includes a first congestion adjustment module for receiving congestion indications from the free queue and the flow queue. The first congestion adjustment module generates end stores transmit probabilities and performs per packet flow control actions. The system further includes a switch fabric for receiving data from the ingress system and for providing a congestion indication to the ingress system. The system further includes at least one egress system for receiving the data from the switch fabric. The egress system includes a second free queue and a second flow queue. The system also includes a second congestion adjustment module for receiving congestion indications from the second free queue and the second flow queue. The second congestion adjustment module generates and stores transmit probabilities and performs per packet flow control actions. Finally, the system includes a scheduler for determining the order and timing of transmission of packets out the egress system and to another node or destination. A method and system in accordance with the present invention provides for a unified method and system for logical connection of congestion with the appropriate flow control responses. The method and system utilizes congestion indicators within the ingress system, egress system, and the switch fabric in conjunction with a coarse adjustment system and fine adjustment system within the ingress device and the egress device to intelligently manage the system.

Claims

1. A system for minimizing congestion of data packets in a communication system comprising:

at least one ingress system, the ingress system including a first free queue, a first flow queue, a first congestion adjustment module for receiving congestion indications from the free queue and the flow queue, for generating and storing transmit probabilities and for performing per packet flow control actions;

a switch fabric for receiving data packets from the ingress system and for providing a congestion indication to the ingress system; and

at least one egress system for receiving the data from the switch fabric, the egress system including a second free queue;

a second flow queue;

a second congestion adjustment module for receiving congestion indications from the second free queue and the second flow queue, for generating and storing transmit probabilities and for performing per packet flow control actions, and a scheduler for adjusting data packets responsive to the first and second adjustment modules for determining the order and transmission of data packets out of the egress system.

2. The system of claim 1 wherein each of the first and second congestion adjustment modules comprises:

a coarse adjustment module for generating and storing transmit probabilities; and

a fine adjustment module which is responsive to the coarse adjustment module for performing per packet flow control actions.

3. The system of claim 2 wherein the coarse adjustment module comprises a per flow background update module.

4. The system of claim 3 wherein the per flow background update module comprises a plurality of queue accounting blocks for receiving congestion indications and for providing current system measurements, and a transmit probability engine coupled to the plurality of queue accounting blocks.

5. The system of claim 4 wherein fine adjustment module comprises a per packet action module for receiving the control response.

6. The system of claim 3 wherein the per packet module comprises a transmit probability memory for receiving current system measurements, packet classification information and transmit probability information, a comparator coupled to the transmit probability memory, a random number generator coupled to the comparator and a transmit block coupled to the comparator, for receiving the current system measurements and the packet classification information.

7. The system of claim 5 wherein each of the ingress system and egress system includes at least one per bit rate module, the at least one per bit rate module for providing a congestion indication to its associated per packet action module.

8. The system of claim 5 wherein the first free queue provides a congestion indication to its associated per packet action module.

9. The system of claim 5 wherein the second free queue provides a congestion indication to its associated per packet action module.

10. The system of claim 1 wherein the second free queue provides a congestion indication to the first free queue.

11. The system of claim 1 wherein each of the ingress system, egress system and switch fabric include a memory coupled thereto.

12. A system for minimizing congestion of data packets in a communication system comprising:

at least one ingress system, the ingress system including a first free queue, a first flow queue, a first congestion adjustment module for receiving congestion indications from the free queue and the flow queue, for generating and storing transmit probabilities and for performing per packet flow control actions;

a switch fabric for receiving data packets from the ingress system and for providing a congestion indication to the ingress system; and

at least one egress system for receiving the data from the switch fabric, the egress system including a second free queue;

a second flow queue;

a second congestion adjustment module for receiving congestion indications from the second free queue and the second flow queue, for generating and storing transmit probabilities and for performing per packet flow control actions, and a scheduler for adjusting data packets responsive to the first and second adjustment modules for determining the order and transmission of data packets out of the egress system wherein each of the first and second congestion adjustment modules comprises;

a per flow background update module for generating and storing transmit probabilities; and

a per packet action module which is responsive to the per flow background update module for performing per packet flow control actions.

13. The system of claim 12 wherein the per flow background update module comprises a plurality of queue accounting blocks for receiving congestion indications and for providing current system measurements, and a transmit probability engine coupled to the plurality of queue accounting blocks.

14. The system of claim 13 wherein the per packet module comprises a transmit probability memory for receiving current system measurements, packet classification information and transmit probability information, a comparator coupled to the transmit probability memory, a random number generator coupled to the comparator and a transmit block coupled to the comparator, for receiving the current system measurements and the packet classification information.

15. The system of claim 14 wherein each of the ingress system and egress system includes at least one per bit rate module, the at least one per bit rate module for providing a congestion indication to its associated per packet action module.

16. The system of claim 14 wherein the first free queue provides a congestion indication to its associated per packet action module.

17. The system of claim 14 wherein the second free queue provides a congestion indication to its associated per packet action module.

18. The system of claim 12 wherein the second free queue provides a congestion indication to the first free queue.

19. The system of claim 12 wherein each of the ingress system, egress system and switch fabric include a memory coupled thereto.