Connection routing based on link utilization

• US 7,443,857 B1
• Filed: 07/09/2003
• Issued: 10/28/2008
• Est. Priority Date: 07/09/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Palai, Mana, Chen, Rachel Yiwen, Hsu, Shawn
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Rivas; Salvador E
• Application Number:
  US10/616,613
• Time in Patent Office: 1,938 Days
• Field of Search: 370/395, 370/238
• US Class Current: 370/395.1
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5629 Admission control
• CPC Class Codes: H04L 2012/563 Signalling, e.g. protocols, reference model
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth

Abstract

A method and system for connection routing based on link utilization. A link utilization limit is accessed at a node of a network. The link utilization limit is compared to a utilization of a link coupled to the node. If the utilization of the link is greater than the link utilization limit, then the link is excluded from a virtual circuit.

Claims

1. An apparatus, comprising:

control circuitry; and

a memory coupled to the control circuitry comprising instructions executable by the control circuitry, the control circuitry operable when executing the instructions to;

exchange local peer group topology information updates with local nodes the local nodes contained within a local peer group of the apparatus and connected to the apparatus independently of any trunk links, the local peer group topology information updates exchanged over at least one local peer group horizontal link and independently of any trunk links;

receive, over at least one trunk link that connects the local peer group to a remote peer group, a call setup signaling message sent by a remote originating node, the call setup signal message to initiate routing of a virtual circuit connection;

inspect a predefined portion of the call setup signaling message for information formatted as one or more Asynchronous Transfer Mode (ATM) Generic Application Transport Information Elements (GATIE), and if such information is present, analyze the present ATM GATIEs for a link utilization threshold value;

generate a dynamic local peer group horizontal link utilization value of the local peer group horizontal link based at least in part on the local peer group topology information updates, the generated dynamic local peer group horizontal link utilization value corresponding to a current utilization of the local peer group horizontal link;

compare the dynamic local peer group horizontal link utilization value with the link utilization threshold value;

determine whether the dynamic local peer group horizontal link utilization value exceeds the link utilization threshold value according to the comparison; and

control whether the local peer group horizontal link is included in the virtual circuit connection according to said determination;

wherein the remote peer group is logically segmented from the local peer group the remote peer group maintaining network topology information independently of the local peer group topology information updates.

2. The apparatus of claim 1 wherein the control circuitry is further operable to:

identify a ratio of actual utilization of the local peer group horizontal link to a local peer group horizontal link utilization capacity;

generate link utilization cost information by, at least in part, multiplying the ratio by a cost indicator associated with the local peer group horizontal link; and

determine whether the local peer group horizontal link is included in the virtual circuit connection according to the generated link utilization cost information.

3. The apparatus of claim 1 wherein the apparatus is a conduit for the remote originating node to influence routing decisions through the local peer group based on local peer group topology information via the call setup signaling message.

4. A method comprising:

generating a signaling message in a local sending node of a local peer group to initiate routing of a virtual circuit connection through a remote peer group, the remote peer group comprising a remote receiving node;

wherein the local sending node is operable to synchronize local peer group routing information with other local peer group nodes, the local peer group nodes and the local sending node identifiable as members of the local peer group by a local peer group identifier;

wherein the remote receiving node is operable to synchronize remote peer group routing information with other remote peer group nodes, the remote peer group nodes and the remote receiving node identifiable as members of the remote peer group by a remote peer group identifier;

generating an information element having a predefined format, the information element representing a link utilization threshold value; and

formatting the generated signaling message to contain the information element, the presence of the information element in the predefined format to trigger the remote receiving node located in the remote peer group to;

use the link utilization threshold value to determine whether a remote peer group horizontal link utilization exceeds the link utilization threshold value based on the synchronized remote peer group routing information; and

select the remote peer group horizontal link for including in the virtual circuit connection according to the determination.

5. The method of claim 4 wherein the signaling message is sent using Private Network to Network Interface (PNNI) protocol wherein the predefined format is a Generic Application Transport Information Element (GATIE) format.

6. The method of claim 5 further comprising sending a soft rerouting message after the virtual circuit connection is established, the soft rerouting message including the same or a different link utilization threshold value formatted using the GATIE format.

7. The method of claim 6 wherein the soft rerouting message elicits formation of a new path prior to tear down of an existing path for the virtual circuit connection.

8. The method of claim 7 wherein the new path retains terminating nodes of the virtual circuit connection but excludes at least one midpoint node belonging to the existing path.

9. An apparatus, comprising:

control circuitry; and

a memory coupled to the control circuitry comprising instructions executable by the control circuitry, the control circuitry operable when executing the instructions to;

identify whether a target link is a local peer group horizontal link contained within a local peer group of the apparatus, wherein the apparatus is associated with the local peer group comprising one or more local nodes and wherein the apparatus is operable to receive local peer group horizontal link utilization information flooded from other local peer group nodes via the local peer group horizontal link;

if the target link is local;

inquire within the local peer group for current local peer group horizontal link utilization information; and

directly control inclusion of the target link in a virtual circuit connection according to the local peer group horizontal link utilization information;

identify whether the target link is a remote peer group horizontal link contained within a remote peer group, wherein the remote peer group comprises a remote receiving node operable to receive remote peer group horizontal link utilization information flooded from other remote peer group nodes via a remote peer group horizontal link;

if the target link is remote;

generate a call setup signaling message to initiate routing of the virtual circuit connection; and

insert a link utilization limit into a predefined location within the call setup signaling message, the presence of the link utilization limit in the predefined location to trigger the remote receiving node to control inclusion of the remote target link in the virtual circuit connection according to the link utilization limit.

10. The apparatus of claim 9 wherein the control circuitry is further operable to format the link utilization limit as an ATM Generic Application Transport Information Element (GATIE) included in the call setup signaling message, the formatting of the link utilization limit as an ATM GATIE to cause remote devices inspecting the ATM GATIE to observe the link utilization limit and control link inclusion responsive to the observation.

11. The apparatus of claim 10 wherein the formatting of the link utilization limit as the ATM GATIE provides undisrupted forwarding of the call setup signaling message through remote devices that do not support controlling link inclusion according to the link utilization limit.

12. The apparatus of claim 11 wherein the call setup signaling message is transferred over a trunk link that couples the local peer group of the apparatus to the remote peer group.

13. The apparatus of claim 12 wherein the call setup signaling message allows the apparatus to remotely control inclusion of links outside the local peer group of the apparatus independently of whether the apparatus is provided with messages indicating the utilization of the remote peer group horizontal links.

14. A method, comprising:

receiving a call setup signaling message at a receiving node of a local peer group wherein the local peer group comprises one or more local nodes and the call setup signaling message is sent via a trunk link by a remote originating node of a remote peer group to initiate routing of a virtual circuit connection;

receiving topology information at the receiving node corresponding to one or more horizontal links of the local peer group wherein the topology information is sent from local nodes of the local peer group nodes identified as local peer group members via a peer group identifier;

observing an ATM GATIE included in the call setup signaling message, and responsive to observing the ATM GATIE, analyzing the ATM GATIE for a link utilization threshold value;

generating a dynamic link utilization value for a horizontal link contained within the local peer group based at least in part on the topology information;

comparing the dynamic link utilization value with the link utilization threshold value;

determining whether the dynamic link utilization value corresponds to the link utilization threshold value; and

controlling whether the horizontal link is included in the virtual circuit connection according to said determination.

15. The method of claim 14 wherein the dynamic link utilization value of the horizontal link corresponds to an amount of capacity that has been reserved on the horizontal link.

16. The method of claim 14 wherein the dynamic link utilization value of the horizontal local link corresponds to an amount of capacity that is actually being used on the horizontal link.

17. The method of claim 14 further comprising:

identifying a ratio of actual utilization of the link to the link utilization threshold value;

generating link utilization cost information by, at least in part, multiplying the ratio by a cost indication associated with the horizontal link; and

determining whether the horizontal link is included in the virtual circuit connection according to the generated link cost information.

18. A system comprising:

means for generating a call setup signaling message to establish a virtual circuit connection extending from an originating node;

means for formatting the call setup signaling message with an opaque information element, the opaque information element representing a link utilization threshold value;

means for sending the call setup signaling message having the opaque information element along a path through a network from the originating node contained in a local peer group to a remote node contained in a remote peer group;

wherein the local peer group comprises one or more local nodes configured to synchronize topology information associated with the local peer group;

wherein the remote peer group comprises one or more remote nodes configured to synchronize topology information associated with the remote peer group;

wherein the opaque information element is sent through both preconfigured remote nodes that are configured to inspect for the opaque information elements and through non-configured remote nodes that are not configured for said inspection;

wherein the opaque information element triggers the pre-configured remote nodes to select between links for the virtual circuit connection according to a comparison of the link utilization threshold value to utilization of the links according to synchronized topology information associated with the remote peer group; and

wherein the opaque information element is forwarded unmodified by the non-configured nodes.

19. The system of claim 18 wherein the opaque information element is an ATM GATIE.

20. The system of claim 18 wherein the call setup signaling message is a PNNI protocol setup message.

21. The system of claim 18 further comprising means for selecting between the links based on both the comparison and costs associated with the links.

22. The system of claim 18 wherein the utilization of the links corresponds to an amount of capacity that has been reserved.

23. The system of claim 18 wherein the utilization of the links corresponds to an amount of capacity that is actually being used.