Routing engine for telecommunications network

• US 8,149,714 B2
• Filed: 12/04/2006
• Issued: 04/03/2012
• Est. Priority Date: 01/25/2002
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Hollman, Brett P., Martin, Jeffrey L., Joseph, George T., Henes, Alex J., Bonewitz, Christopher M., Asalian, Kaveh, Yaworski, Geoff R., Ryczek, Gary L., Train, Colin G.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Jiang, Charles C
• Application Number:
  US11/566,649
• Publication Number:
  US 20070091868A1
• Time in Patent Office: 1,947 Days
• Field of Search: 370/229, 370/235, 370/238, 709238-244
• US Class Current: 370/238
• 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 module configured to provide an automated design process for rendering the optimal route. The routing module 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 module 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. A 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:

one or more computer processors in communication with at least one memory, wherein the at least one memory stores a plurality of modules comprising;

a find module filtering all possible capacity links capable of transporting data between the source location and the destination location within the communication network, wherein the find module filters the capacity links to generate a filtered set of capacity links that satisfy a service type and a bandwidth specified in the service request;

a build module creating a list of one or more possible routes from the filtered set of capacity links, each route including a plurality of the capacity links that are each connected to an adjacent 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 attaching a weight to each capacity link in the routes, wherein each weight represents one or more parameters that distinguish the associated capacity link based on cost factors;

a select module selecting an optimal route from the one or more possible routes based on the weights attached to the capacity links in the one or more possible routes;

a provisioning module configured to provision and assign network elements to routes;

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

a command and control module engaging the provisioning module to provision and assign elements to the optimal route of the communication line if the test module determines that the optimal route is available for use by the communication line.

2. The system of claim 1, further comprising:

an invoke module invoking one or more routing rules of a route policy associated with the service type, the routing rules being dependent upon the service type and the bandwidth, whereby the find module filters the capacity links according to the routing policy.

3. The system of claim 1, wherein the select module selects a subsequent optimal route from the list of one or more possible routes if the test module determines that the optimal route is not available for use by the communication line.

4. The system of claim 3, wherein, prior to selecting the subsequent optimal route, the select module removes from the list of one or more possible routes the optimal route that is determined to be not available for use by the communication line.

5. The system of claim 1, wherein the weight 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.

6. 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 includes in the filtered set of capacity links only the 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.

7. The system of claim 1, wherein the provisioning module is configured to:

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

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

8. The system of claim 7, wherein the test module is configured to:

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

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

9. The system of claim 8, wherein the select module is configured to:

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

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

10. The system of claim 1, wherein the select module is configured to apply a routing algorithm to the list.

11. The system of claim 10, wherein the routing algorithm is selected from the group consisting of:

Bellman/Ford algorithm;

Johnson'"'"'s algorithm;

Floyd-Warshall algorithm; and

Dijkstra'"'"'s algorithm.

12. The system of claim 1, wherein the provisioning module assigns network elements to routes by marking each network element of a route as consumed against the service request.

13. The system of claim 1, wherein the provisioning module does not assign network elements to routes when a race condition exists with capacity consumed by a front end user of the provisioning system.

14. The system of claim 1, wherein the command and control module is configured to instruct a workflow module to generate worksite task lists for implementing end point connections associated with the service request.