Routing engine for telecommunications network

• US 7,146,000 B2
• Filed: 01/25/2002
• Issued: 12/05/2006
• Est. Priority Date: 01/25/2002
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level Communications LLC
• Inventors: Yaworski, Geoff R., Hollman, Brett P., Henes, Alex J., Asalian, Kaveh, Bonewitz, Christopher M., Ryczek, Gary L., Train, Colin G., Martin, Jeffrey L., Joseph, George T.
• Primary Examiner(s): TIEU, BENNY QUOC
• Application Number:
  US10/057,362
• Publication Number:
  US 20030142808A1
• Time in Patent Office: 1,775 Days
• Field of Search: 37922106-22107, 379/114.02, 379/201.12, 709/220, 709/238, 709/241, 370/238, 370/238.1, 370254-256
• US Class Current: 379/221.06
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS

Abstract

A system for automated installation of a communication line using an optimal route between a source location and a destination location is disclosed. The system includes a routing engine providing an automated design process for rendering the optimal route. The routing engine utilizes a routing algorithm to select the optimal route from a graph of capacity links defining a plurality of possible routes between the source and destination locations. If, at any time during the design process, the optimal route or capacity links defining the optimal route are detected as unavailable for any reason, the routing engine re-initiates the design process and thereafter selects a new optimal route based upon a new capacity graph built without the previously unavailable capacity link. Once designed, the available optimal route is provided to a command and control engine, which, in turn, manages the installation of the communication line using the optimal route. The command and control engine manages the process for assigning the optimal route in the provisioning system.

Claims

1. An automated routing system for designing a route in a communications network through which a communication line may be installed between a source location and a destination location as specified in a service request for the communication line, the system comprising:

a find module identifying one or more possible capacity links within the communication network, each capacity link representing an ability to transport data over a predefined segment of the communication network between the source location and the destination location;

a build module constructing a capacity graph of the communication network depicting connectivity of each of the possible capacity links to an adjacent possible capacity link such that one or more possible routes are defined between a source node representing the source location and a destination node representing the destination location; and

a select module applying a routing algorithm to the capacity graph to select an optimal route from the one or more possible routes based on a calculated cost factor for installation of the communication line into each of the possible routes within the computer network.

2. The system of claim 1, further comprising:

an invoke module retrieving a route policy for the communication line specifying routing rules based on a given service type of the service request and bandwidth require for installation of the communication line and invoking the route policy such that the find module identifies only possible capacity links that satisfy the routing rules.

3. The method of claim 1, further comprising:

a route available test module testing whether the optimal route is available for use by the communication line.

4. The system of claim 3, further comprising:

a submit module submitting the optimal route to a command and control engine for installation of the communication line using the optimal route if the route available test module determines that the optimal route is available for use by the communication line.

5. The system of claim 3, wherein the select module re-applies the routing algorithm to the capacity graph to select a subsequent optimal route if the route available test module determines that the optimal route is not available for use by the communication line.

6. The system of claim 5, wherein the optimal route found not available for use by the communication line is eliminated as the one or more possible routes defined by the capacity graph.

7. The system of claim 1, wherein the calculated cost factor for each of the possible routes is determined based on a total distance of the predefined segments covered by the capacity links defining each possible route.

8. The system of claim 1, wherein the service request specifies intermediate locations through which the communication line must pass between the source location and the destination location, the system further comprising:

a define module defining an intermediate node corresponding to each intermediate location such that the find module identifies only possible capacity links that may be joined between adjacent intermediate nodes, a first intermediate node and the source node and a final intermediate node and the destination node.

9. The system of claim 1, wherein the routing algorithm is Dijkstra'"'"'s algorithm.

10. The system of claim 1, wherein the communication line is a private line.

11. The system of claim 1, wherein the communication line is an unprotected private line circuit.

12. The system of claim 1, wherein the communication line is a wavelength circuit.

13. An method for designing a route in a communication network through which a communication line may be installed between a source location and a destination location as specified in a service request for the communication line, the method comprising:

identifying one ore more possible capacity links within the communication network, wherein each capacity link represents an ability to transport data over a predefined segment of the communication network between the source location and the destination location;

building a capacity graph of the communication network depicting connectivity of each of the possible capacity links to an adjacent possible capacity link such that one or more possible routes are defined between a source node representing the source location and a destination node representing the destination location;

calculating a cost factor for each possible capacity link within the communication network; and

selecting an optimal route from the possible routes based on the calculated cost factor for each possible link.

14. The method of claim 13, wherein the calculating act comprise:

applying a routing algorithm to the capacity graph.

15. The method of claim 14, wherein the routing algorithm is Dijkstra'"'"'s algorithm.

16. The method of claim 13, wherein the identifying step comprises:

retrieving a route policy for the communication line specifying routing rules based on a given service type of the service request and bandwidth required for installation of the communication line; and

invoking the route policy to identify only possible capacity links that satisfy the routing rules.

17. The method of claim 13, wherein the selecting act comprises:

selecting a source network element for connecting the source node to a first customer demarcation located at the source location; and

selecting a destination network element for connecting the destination node to a second customer demarcation located at the destination location.

18. The method of claim 17, further comprising:

testing whether the source network element contains an incoming egress port for connecting to the first customer demarcation; and

testing whether the destination network element contains an outgoing egress port for connecting to the second customer demarcation.

19. The method of claim 18, further comprising:

if the source network element does not contain an incoming egress port, repeating the selecting act to select a subsequent source network element; and

if the destination network element does not contain an outgoing egress port, repeating the selecting act to select a subsequent destination network element.

20. The method of claim 13, further comprising:

testing whether the optimal route is available for use by the communication line.

21. The method of claim 20, further comprising:

submitting the optimal route to a command and control engine for installation of the communication line using the optimal route if the optimal route is available for use by the communication line.

22. The method of claim 20, wherein the selecting act comprises:

selecting a subsequent optimal route if the optimal route is not available for use by the communication line.

23. The method of claim 22, wherein the optimal route found not available for use by the communication line is eliminated as the one or more possible routes defined by the capacity graph.

24. The method of claim 13, wherein the calculating act comprises:

rendering the cost factor for each of the possible routes based on a total distance of the predefined segments covered by the capacity links defining each possible route.

25. The method of claim 13, wherein the service request specifies intermediate locations through which the communication line must pass between the source location and the destination location, the identifying act comprising:

defining an intermediate node corresponding to each intermediate location specified by the service request; and

limiting the possible capacity links to capacity links within the communication network that may be joined between adjacent intermediate nodes, a first intermediate node and the source node and a final intermediate node and the destination node.

26. A computer program product readable by a computing system and encoding a computer program of instruction for executing a computer process for designing a route in a communication network through which a communication line may be installed between a source location and a destination location as specified in a service request for the communication line, said computer process comprising:

identifying one or more possible capacity links within the communication network, wherein each capacity link represents an ability to transport data over a predefined segment of the communication network between the source location and the destination location;

building a capacity graph of the communication network depicting connectivity of each of the possible capacity link to an adjacent possible capacity link such that one or more possible routes are defined between a source node representing the source location and a destination node representing the destination location;

calculating a cost factor for each possible capacity link within the communication network; and

selecting an optimal route from the possible routes based on the calculated cost factor for each possible link.

27. The computer process in the computer program product of claim 26, wherein the calculating act comprises:

applying a routing algorithm to the capacity graph.

28. The computer process in the computer program product of claim 26, wherein the identifying step comprises:

retrieving a route policy for the communication line specifying routing rules based on a given service type of the service request and bandwidth required for installation of the communication line; and

invoking the route policy to identify only possible capacity links that satisfy the routing rules.

29. The computer process in the computer program product of claim 26, wherein the selecting act comprises:

selecting a source network element for connecting the source node to a first customer demarcation located at the source location; and

selecting a destination network element for connecting the destination node to a second customer demarcation located at the destination location.

30. The computer process in the computer program product of claim 29, wherein the computer process further comprises:

testing whether the source network element contains an incoming egress port for connecting to the first customer demarcation; and

testing whether the destination network element contains an outgoing egress port for connecting to the second customer demarcation.

31. The computer process in the computer program product of claim 30, wherein the computer process further comprises:

if the source network element does not contain an incoming egress port, repeating the selecting act to select a subsequent source network element; and

if the destination network element does not contain an outgoing egress port, repeating the selecting act to select a subsequent destination network element.

32. The computer process in the computer program product of claim 26, wherein the identifying act comprising:

defining an intermediate node corresponding to each intermediate location specified by the service request; and

limiting the possible capacity links to capacity links within the communication network that may be joined between adjacent intermediate nodes, a first intermediate node and the source node and a final intermediate node and the destination node.