Congestion management for packet routers

• US 7,215,639 B2
• Filed: 08/31/2001
• Issued: 05/08/2007
• Est. Priority Date: 08/31/2001
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: 4536631 Canada Incorporated (Lowe's Companies, Inc.)
• Inventors: Saheb, Eyad, Belanger, Jean, Norman, Richard S., De Maria, Marcelo A. R.
• Primary Examiner(s): Harper, Kevin C.
• Application Number:
  US09/943,004
• Publication Number:
  US 20030043742A1
• Time in Patent Office: 2,076 Days
• Field of Search: 370230-234, 370235-236, 370229-2301, 370/237, 370400-401, 370412-413, 370/415, 370/417, 370/422, 370428-429
• US Class Current: 370/235
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/265 sent by intermediate network nodes
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/20 Support for services
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics
• CPC Class Codes: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element

Abstract

A method and system for regulating packet flow to a downstream entity capable of forwarding packets to a plurality of intermediate destinations. The method includes maintaining a database of queues, each queue in the database being associated with packets intended to be forwarded to a corresponding one of a plurality of final destinations via a corresponding one of the intermediate destinations. Each queue in the database is further associated with a state that is either active or inactive. Upon receipt of a message from the downstream entity indicating a reduced (increased) ability of a particular one of the intermediate destinations to accept packets intended to be forwarded to a particular one of the final destinations, the method provides for rendering inactive (active) the state of the queue associated with packets intended to be forwarded to the particular final destination via the particular intermediate destination.

Claims

1. A method of regulating packet flow to a downstream entity capable of forwarding packets to a plurality of intermediate destinations, the method comprising:

maintaining a database of queues, each queue in the database being associated with packets intended to be forwarded to a corresponding one of a plurality of final destinations via a corresponding one of the intermediate destinations, each queue in the database being further associated with a state that is either active or inactive;

upon receipt of a message from the downstream entity indicating a reduced ability of a particular one of the intermediate destinations to accept packets intended to be forwarded to a particular one of the final destinations, rendering inactive the state of the queue associated with packets intended to be forwarded to the particular final destination via the particular intermediate destination; and

upon receipt of a message from the downstream entity indicating an increased ability of a particular one of the intermediate destinations to accept packets intended to be forwarded to a particular one of the final destinations, rendering active the state of the queue associated with packets intended to be forwarded to the particular final destination via the particular intermediate destination.

2. A method as defined in claim 1, further comprising:

providing storage for the packets associated with each queue.

3. A method as claimed in claim 2, further comprising:

for each intermediate destination, scheduling packets for transmission to said intermediate destination from amongst the packets belonging to those queues for which the state is active and that are associated with packets intended to be forwarded to any final destination via said intermediate destination.

4. A method as defined in claim 2, further comprising:

determining whether the downstream entity has an ability to receive at least one packet;

upon determining that the downstream entity has the ability to receive at least one packet, selecting at least one packet that has been scheduled for transmission to one of the intermediate destinations and transmitting at least one of the selected at least one packet to the downstream entity.

5. A method as defined in claim 4, wherein selecting at least one packet that has been scheduled for transmission to one of the intermediate destinations includes:

selecting an intermediate destination; and

selecting at least one packet that has been scheduled for transmission to the selected intermediate destination.

6. A method as defined in claim 1, said method being implemented in a congestion manager and further comprising:

maintaining information on memory utilization for each of a plurality of flows, each flow being associated with a corresponding one of the final destinations;

if memory utilization for a particular one of the flows exceeds a first threshold, generating a message indicative of a reduced ability of the congestion manager to accept packets intended to be forwarded to the final destination associated with the particular flow; and

if memory utilization for a particular one of the flows falls below a second threshold, generating a message indicative of an increased ability of the congestion manager to accept packets intended to be forwarded to the final destination associated with the particular flow.

7. A method as defined in claim 6, wherein the first and second thresholds are pre-determined.

8. A method as defined in claim 6, further comprising:

determining total memory utilization for a plurality of said flows; and

adjusting at least one of the first and second thresholds as a function of the total memory utilization for said plurality of said flows.

9. A method as defined in claim 6, further comprising:

receiving the packets from a plurality of upstream entities; and

sending the generated messages to the plurality of upstream entities.

10. A method as defined in claim 9, wherein sending one of the generated messages to the plurality of upstream entities includes broadcasting said one of the generated messages to the plurality of upstream entities.

11. A method as defined in claim 9, further comprising:

maintaining a second database of those upstream entities that have recently sent packets intended to be forwarded to the final destination associated with the particular flow;

wherein sending the generated messages to the plurality of upstream entities includes multicasting said one of the generated messages to those upstream entities in the second database.

12. A method as defined in claim 9, further comprising:

maintaining a second database indicative of the number of packets belonging to a given flow that have been received from each upstream entity since transmission to that upstream entity of a message indicative of a reduced ability of the congestion manager to accept packets intended to be forwarded to the final destination associated with the given flow.

13. A method as defined in claim 12, further comprising:

if the number of packets in the database exceeds a first threshold, for a particular flow and for a particular upstream entity, generating another message indicative of a reduced ability of the congestion manager to accept packets intended to be forwarded to the final destination associated with the particular flow and sending said other message to the particular upstream entity.

14. A method as defined in claim 13, further comprising:

if the number of packets in the database exceeds a second threshold greater than the first threshold, for a particular flow and for a particular upstream entity, generating an alarm message and sending the alarm message to an external entity.

15. A method as defined in claim 6, further comprising:

maintaining an acknowledgement database, wherein the acknowledgement database includes an entry for each combination of upstream source and final destination and an indication of whether the upstream source in each combination of upstream source and final destination has acknowledged receipt of a message previously sent to the plurality of upstream sources and indicative of an increased ability of the congestion manager to accept packets intended to be forwarded to said final destination.

16. A method as defined in claim 15, further comprising:

upon receipt of a message from a particular one of the upstream sources acknowledging receipt of a message previously sent to the plurality of upstream sources and indicative of an increased ability of the congestion manager to accept packets intended to be forwarded to a particular final destination, updating the entry in the acknowledgement database corresponding to the combination of particular upstream source and particular final destination.

17. A method as defined in claim 6, further comprising:

upon receipt of a first message from the downstream entity indicating an increased ability of a particular one of the intermediate destinations to accept packets intended to be forwarded to the final destination associated with a particular flow;

generating an acknowledgement message acknowledging receipt of the first message; and

sending the acknowledgement message to the particular intermediate destination.

18. A method as defined in claim 17, further comprising:

maintaining an acknowledgement database, wherein the acknowledgement database includes an entry for each combination of upstream source and final destination and an indication of whether the upstream source in each combination of upstream source and final destination has acknowledged receipt of a message previously sent to the plurality of upstream sources and indicative of increased ability of the congestion manager to accept packets intended to be forwarded to said final destination.

19. A method as defined in claim 18, further comprising:

upon receipt of a message from a particular one of the upstream sources acknowledging receipt of a message previously sent to the plurality of upstream sources and indicative of an increased ability of the congestion manager to accept packets intended to be forwarded to a particular final destination, updating the entry in the acknowledgement database corresponding to the combination of particular upstream source and particular final destination.

20. A method as defined in claim 6, further comprising:

maintaining an acknowledgement database, wherein the acknowledgement database includes an entry for each combination of upstream source and final destination and an indication of whether the upstream source in each combination of upstream source and final destination has acknowledged receipt of a message previously sent to the plurality of upstream sources and indicative of an increased or reduced ability of the congestion manager to accept packets intended to be forwarded to said final destination.

21. A method as defined in claim 20, further comprising:

upon receipt of a message from a particular one of the upstream sources acknowledging receipt of a message previously sent to the plurality of upstream sources and indicative of an increased or reduced ability of the congestion manager to accept packets intended to be forwarded to a particular final destination, updating the entry in the acknowledgement database corresponding to the combination of particular upstream source and particular final destination.

22. A method as defined in claim 6, further comprising:

upon receipt of a first message from the downstream entity indicating an increased or reduced ability of a particular one of the intermediate destinations to accept packets intended to be forwarded to the final destination associated with a particular flow;

generating an acknowledgement message acknowledging receipt of the first message; and

sending the acknowledgement message to the particular intermediate destination.

23. A method as defined in claim 22, further comprising:

maintaining an acknowledgement database, wherein the acknowledgement database includes an entry for each combination of upstream source and final destination and an indication of whether the upstream source in each combination of upstream source and final destination has acknowledged receipt of a message previously sent to the plurality of upstream sources and indicative of increased or reduced ability of the congestion manager to accept packets intended to be forwarded to said final destination.

24. A method as defined in claim 23, further comprising:

upon receipt of a message from a particular one of the upstream sources acknowledging receipt of a message previously sent to the plurality of upstream sources and indicative of an increased or reduced ability of the congestion manager to accept packets intended to be forwarded to a particular final destination, updating the entry in the acknowledgement database corresponding to the combination of particular upstream source and particular final destination.

25. A method as defined in claim 6, wherein the congestion manager is implemented in at least one of the intermediate destinations.

26. A method as defined in claim 1, said method being implemented in at least one of the intermediate destinations.

27. A method as claimed in claim 1, wherein the downstream entity is a switch fabric.

28. A method as claimed in claim 1, wherein the intermediate destinations include switch fabric nodes of an intermediate switching stage of a multi-stage packet router.

29. A method as defined in claim 28, said method being implemented in at least one of the intermediate destinations.

30. A computer-readable storage medium containing program instructions for causing execution in a computing device of a method as defined in claim 1.

31. A congestion manager for regulating packet flow to a downstream entity capable of forwarding packets to a plurality of intermediate destinations, comprising:

means for maintaining a database of queues, each queue in the database being associated with packets intended to be forwarded to a corresponding one of a plurality of final destinations via a corresponding one of the intermediate destinations, each queue in the database being further associated with a state that is either active or inactive;

means for rendering inactive, upon receipt of a message from the downstream entity indicating a reduced ability of a particular one of the intermediate destinations to accept packets intended to be forwarded to a particular one of the final destinations, the state of the queue associated with packets intended to be forwarded to the particular final destination via the particular intermediate destination; and

means for rendering active, upon receipt of a message from the downstream entity indicating an increased ability of a particular one of the intermediate destinations to accept packets intended to be forwarded to a particular one of the final destinations, the state of the queue associated with packets intended to be forwarded to the particular final destination via the particular intermediate destination.

32. A computer readable storage medium containing a program element for execution by a computing device to implement a congestion manager for regulating packet flow to a downstream entity capable of forwarding packets to a plurality of intermediate destinations, the program element including:

program code means for maintaining a database of queues, each queue in the database being associated with packets intended to be forwarded to a corresponding one of a plurality of final destinations via a corresponding one of the intermediate destinations, each queue in the database being further associated with a state that is either active or inactive;

program code means for rendering inactive, upon receipt of a message from the downstream entity indicating a reduced ability of a particular one of the intermediate destinations to accept packets intended to be forwarded to a particular one of the final destinations, the state of the queue associated with packets intended to be forwarded to the particular final destination via the particular intermediate destination; and

program code means for rendering active, upon receipt of a message from the downstream entity indicating an increased ability of a particular one of the intermediate destinations to accept packets intended to be forwarded to a particular one of the final destinations, the state of the queue associated with packets intended to be forwarded to the particular final destination via the particular intermediate destination.

33. A congestion manager capable of forwarding packets to a plurality of intermediate destinations, comprising:

a queue processor for maintaining information on a plurality of queues, each queue being associated with packets intended to be forwarded to a corresponding one of a plurality of final destinations via a corresponding one of the intermediate destinations; and

a controller in communication with the queue processor;

said controller being adapted to maintain information on a state of each queue, the state of a queue being either active or inactive;

said controller being further adapted to respond to a message from a particular one of the intermediate destinations indicative of a reduced ability of the particular intermediate destination to accept packets intended to be forwarded to a particular one of the final destinations by rendering inactive the state of the queue associated with packets intended to be forwarded to a particular one of the final destinations via the particular intermediate destination; and

said controller being further adapted to respond to a message from a particular one of the intermediate destinations indicative of an increased ability of the particular intermediate destination to accept packets intended to be forwarded to a particular one of the final destinations by rendering active the state of the queue associated with packets intended to be forwarded to a particular one of the final destinations via the particular intermediate destination.

34. A congestion manager as defined in claim 33, further comprising:

a memory for providing storage for the packets associated with each queue.

35. A congestion manager as defined in claim 34, the queue processor being further adapted to schedule packets for transmission to each particular one of the intermediate destinations from amongst the packets belonging to those queues for which the state is active and that are associated with packets intended to be forwarded to any final destination via the particular intermediate destination.

36. A congestion manager as defined in claim 35, the queue processor being further adapted to determine whether the downstream entity has an ability to receive at least one packet and, upon determining that the downstream entity has the ability to receive at least one packet, to select at least one packet that has been scheduled for transmission to one of the intermediate destinations and to cause at least one of the selected at least one packet to be extracted from the memory and transmitted to the downstream entity.

37. A congestion manager as defined in claim 33, further comprising:

a classifier connected to the queue processor and to the controller, for determining the final destination to which each packet in a received stream of packets is to be forwarded.

38. A method of regulating packet flow to a downstream entity capable of forwarding packets to a plurality of intermediate destinations, the method comprising:

maintaining a database of queues, each queue in the database being associated with packets of a corresponding one of a plurality of service classes intended to be forwarded to a corresponding one of a plurality of final destinations via a corresponding one of the intermediate destinations, each queue in the database being further associated with a state that is either active or inactive;

upon receipt of a message from the downstream entity indicating a reduced ability of a particular one of the intermediate destinations to accept packets of a particular one of the service classes intended to be forwarded to a particular one of the final destinations, rendering inactive the state of the queue associated with packets of the particular service class intended to be forwarded to the particular final destination via the particular intermediate destination; and

upon receipt of a message from the downstream entity indicating an increased ability of a particular one of the intermediate destinations to accept packets of a particular one of the service classes intended to be forwarded to a particular one of the final destinations, rendering active the state of the queue associated with packets of the particular service class intended to be forwarded to the particular final destination via the particular intermediate destination.

39. A method as defined in claim 38, further comprising:

providing storage for the packets associated with each queue.

40. A method as claimed in claim 39, further comprising:

for each intermediate destination, scheduling packets for transmission to said intermediate destination from amongst the packets belonging to those queues for which the state is active and that are associated with packets intended to be forwarded to any final destination via said intermediate destination.

41. A method as claimed in claim 40, further comprising:

maintaining a queue of active queues for each service class, wherein each queue in the queue of queues for a particular service class has a state that is active; and

for each intermediate destination, scheduling packets for transmission to said intermediate destination from amongst the packets in the queues contained in each queue of active queues.

42. A computer-readable storage medium containing program instructions for causing execution in a computing device of a method as defined in claim 38.