Dynamic adaptation to congestion in connection-oriented networks

• US 20030016808A1
• Filed: 12/26/2000
• Published: 01/23/2003
• Est. Priority Date: 12/26/2000
• Status: Active Grant

• Current Assignee: Ciena Corporation
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Skalecki, Darek R., Hu, Qingwen, Aalders, Michael L.
• Granted Patent: US 7,127,056 B2
• Time in Patent Office: Days
• US Class Current: 379/221.03
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04M 3/2263 Network management
• CPC Class Codes: H04M 7/0096 Trunk circuits

Abstract

Dynamic adaptation of connection-oriented networks is introduced wherein, once congestion is encountered, dynamic adaptation steps may be performed. Four adaptation steps are proposed for reacting to various network congestion scenarios. It is further recommended that the steps are performed in a particular order such that the higher severity and longer sustentation of the network congestion the more strict step is performed to alleviate the network congestion. At a switch in the connection-oriented network, utilization of a trunk carried on a link connected to the switch is monitored and, if said utilization of said trunk exceeds a first threshold, a first degree of adaptation is initialized wherein use of the trunk by further connections is prevented. Subsequent degrees of adaptation are triggered when high utilization continues and surpasses higher thresholds. The subsequent degrees of adaptation involve rerouting connections that make use of the trunk.

Claims

1. A method of adaptively routing connections through a connection-oriented data network, said connection-oriented data network including a plurality of switches and a plurality of links connecting said switches, said method comprising:

at a given one of said plurality of switches,

receiving an indication of a utilization of a trunk carried on one of said plurality of links, where said one of said plurality of links connects to said given one of said plurality of switches; and

if said utilization of said trunk exceeds a first threshold, initializing a first degree of adaptation.

2. The method of claim 1 further comprising, responsive to said initializing said first degree of adaptation, consulting a policy database to determine a course of action.

3. The method of claim 1 wherein said first degree of adaptation comprises preventing new connections having specific characteristics from being established on said trunk.

4. The method of claim 3 wherein said specific characteristics relate to a priority of said new connections.

5. The method of claim 3 wherein said specific characteristics relate to a destination of said new connections.

6. The method of claim 3 wherein said specific characteristics relate to a source of said new connections.

7. The method of claim 1 wherein said initializing said first degree of adaptation comprises indicating to other switches of said plurality of switches that adaptation is active on said trunk.

8. The method of claim 7 further comprising, if said utilization of said trunk falls below said first threshold for a preset downgrade duration, indicating to other switches of said plurality of switches that adaptation is no longer active on said trunk.

9. The method of claim 1 further comprising, if said utilization of said trunk exceeds a second threshold, initializing a second degree of adaptation.

10. The method of claim 9 further comprising, responsive to said initializing said second degree of adaptation, consulting a policy database to determine a course of action.

11. The method of claim 9 wherein said second degree of adaptation comprises identifying a misbehaved connection, among a plurality of connections using said trunk.

12. The method of claim 11 further comprising sending a congestion notification to a source of said misbehaved connection.

13. The method of claim 11 further comprising altering said policy database to reduce a priority associated with said misbehaved connection.

14. The method of claim 9 further comprising, if said utilization of said trunk exceeds a third threshold, initializing a third degree of adaptation.

15. The method of claim 14 further comprising, responsive to said initializing said third degree of adaptation, consulting a policy database to determine a course of action.

16. The method of claim 14 wherein said third degree of adaptation comprises:

selecting a candidate connection, among said plurality of connections using said trunk, for rerouting, where said candidate connection is associated with a path between a source and a destination, where said trunk is a segment of said path and said trunk connects said given one of said plurality of switches to a second one of said plurality of switches; and

acting such that said candidate connection is switched to an alternate path between said source and said destination, where said alternate path excludes said trunk.

17. The method of claim 16 wherein said selecting said candidate connection is based on specific characteristics of said plurality of connections using said trunk.

18. The method of claim 16 wherein said acting comprises sending a rerouting request to a third one of said plurality of switches, where said third switch precedes of said given one of said plurality of switches in said path.

19. The method of claim 18 wherein said third switch is said source of said candidate connection.

20. The method of claim 18 wherein said rerouting request indicates that said candidate connection should be established on said alternate path before said candidate connection is removed from said path.

21. The method of claim 16 wherein said acting comprises determining an alternate path segment, where said alternate path segment connects said given one of said plurality of switches to said second one of said plurality of switches and excludes said trunk.

22. The method of claim 21 further comprising:

establishing said candidate connection on said alternate path; and

responsive to said establishing, removing said candidate connection from said trunk.

23. The method of claim 16 further comprising, if said utilization of said trunk continues to exceed said third threshold for a preset duration, repeating said selecting and acting for an additional candidate connection.

24. The method of claim 14 further comprising, if said utilization of said trunk exceeds a fourth threshold, initializing a fourth degree of adaptation.

25. The method of claim 24 further comprising, responsive to said initializing said fourth degree of adaptation, consulting a policy database to determine a course of action.

26. The method of claim 24 wherein said fourth degree of adaptation comprises:

selecting a further candidate connection, among said plurality of connections using said trunk, for further rerouting, where said further candidate connection is associated with a further path between a further source and a further destination, where said trunk is a further segment of said further path; and

acting such that said further candidate connection is switched to a further alternate path between said further source and said further destination, where said further alternate path excludes said trunk.

27. The method of claim 26 wherein said selecting said candidate connection is based on specific characteristics of said plurality of connections using said trunk.

28. The method of claim 26 wherein said acting comprises sending a further rerouting request to a third one of said plurality of switches, where said third switch precedes of said given one of said plurality of switches in said further path.

29. The method of claim 28 wherein said further rerouting request indicates that said further candidate connection should be removed from said further path before said further candidate connection is established on said further alternate path.

30. The method of claim 9 further comprising, if said utilization of said trunk falls below said second threshold for a preset downgrade duration, reducing said degree of adaptation from said second degree of adaptation to said first degree of adaptation.

31. The method of claim 14 further comprising, if said utilization of said trunk falls below said third threshold for a preset downgrade duration, reducing said degree of adaptation from said third degree of adaptation to said second degree of adaptation.

32. A path administrator in a switch in a connection-oriented data network, said path administrator operable to:

receive an indication of a utilization of a trunk carried on a link connected to said switch; and

initialize a first degree of adaptation if said utilization of said trunk exceeds a first threshold.

33. A path administrator in a switch in a connection-oriented data network, said path administrator comprising:

a receiver for receiving an indication of a utilization of a trunk carried on a link connected to said switch; and

means for initializing a first degree of adaptation if said utilization of said trunk exceeds a first threshold.

34. The path administrator of claim 33 further comprising means for consulting a policy database to determine a course of action.

35. The path administrator of claim 34 further comprising means for preventing new connections having specific characteristics from being established on said trunk.

36. The path administrator of claim 33 further comprising means for indicating to other switches of said plurality of switches that adaptation is active on said trunk.

37. The path administrator of claim 36 wherein said means for indicating further comprises means for indicating to other switches of said plurality of switches that adaptation is no longer active on said trunk.

38. The path administrator of claim 33 further comprising means for identifying a misbehaved connection, among a plurality of connections using said trunk.

39. The path administrator of claim 33 further comprising:

means for selecting a candidate connection, among a plurality of connections using said trunk, for rerouting, where said candidate connection is associated with a path between a source and a destination; and

means for acting such that said candidate connection is switched to an alternate path between said source and said destination, where said alternate path excludes said trunk.

40. A computer readable medium containing computer-executable instructions which, when performed by a processor in a switch in a connection-oriented data network, cause the processor to:

receive an indication of a utilization of a trunk carried on a link connected to said switch; and

initialize a first degree of adaptation if said utilization of said trunk exceeds a first threshold.

41. The computer readable medium of claim 40 wherein said computer-executable instructions further cause the processor to consult a policy database to determine a course of action responsive to said initializing said first degree of adaptation.

42. The computer readable medium of claim 40 wherein said computer-executable instructions further cause the processor to prevent new connections having specific characteristics from being established on said trunk.

43. The computer readable medium of claim 40 wherein said computer-executable instructions further cause the processor to indicate to other switches of said plurality of switches that adaptation is active on said trunk.

44. The computer readable medium of claim 43 wherein said computer-executable instructions further cause the processor to indicate to other switches of said plurality of switches that adaptation is no longer active on said trunk if said utilization of said trunk falls below said first threshold for a preset downgrade duration.

45. The computer readable medium of claim 40 wherein said computer-executable instructions further cause the processor to identify a misbehaved connection, among a plurality of connections using said trunk.

46. The computer readable medium of claim 40 wherein said computer-executable instructions further cause the processor to:

select a candidate connection, among said plurality of connections using said trunk, for rerouting, where said candidate connection is associated with a path between a source and a destination, where said trunk is a segment of said path and said trunk connects said given one of said plurality of switches to a second one of said plurality of switches; and

act such that said candidate connection is switched to an alternate path between said source and said destination, where said alternate path excludes said trunk.