Routing engine for telecommunications network

• US 8,238,252 B2
• Filed: 09/04/2009
• Issued: 08/07/2012
• Est. Priority Date: 01/25/2002
• Status: Active Grant

• 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): Gauthier, Gerald
• Assistant Examiner(s): King, Simon
• Application Number:
  US12/554,823
• Publication Number:
  US 20090323701A1
• Time in Patent Office: 1,068 Days
• Field of Search: 370/238, 370/406, 370/232, 370/237, 370/400, 709/238
• 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 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. A computer-implemented method for providing a telecommunications service between a source node and a destination node in a communications network, wherein the telecommunications service is associated with at least one service requirement, the method comprising:

(a) identifying a plurality of fiber segments within the communications network that provide capacity links between the source node and the destination node, wherein each of the plurality of fiber segments is associated with a cost;

(b) filtering the plurality of fiber segments to a set of candidate fiber segments for use in forming a route for the telecommunications service based on an analysis of the cost of each of the plurality of fiber segments against the at least one service requirement;

(c) selecting from the set of candidate fiber segments at least two fiber segments to form an optimal route for the telecommunications service;

(d) verifying whether the optimal route will satisfy the at least one service requirement, wherein the verifying act comprises;

(d)(i) identifying one or more network elements communicatively coupled to the at least two selected fiber segments for use in provisioning the telecommunications service over the optimal route;

(d)(ii) analyzing the one or more identified network elements to determine whether use of the one or more identified network elements in the optimal route conforms to the at least one service requirement; and

(d)(iii) based on the analyzing operation (d)(ii), if use of the one or more identified network elements in the optimal route does not conform to the at least one service requirement, then repeating the selecting operation (c), otherwise selecting the optimal route as the route for the telecommunications service.

2. A computer-implemented method as recited in claim 1, wherein the cost associated with each of the plurality of fiber segments relates to distance, the selecting operation (c) comprising:

selecting the at least two fiber segments having a shorter distance between the source node and the destination node relative to other routes that could be formed by other fiber segments therebetween.

3. A computer-implemented method as recited in claim 2, wherein the at least one service requirement relates, at least in part, to a speed at which data is transmitted using the telecommunications service.

4. A computer-implemented method as recited in claim 3, wherein the at least one service requirement is a bandwidth measurement.

5. A computer-implemented method as recited in claim 1, wherein the one or more identified network elements comprise at least a first network element and a second network element, the first network element and the second network element being co-located at a node, and wherein the analyzing operation (d)(ii) comprises:

analyzing the first network element to determine whether use of the first network element in the optimal route conforms to the at least one service requirement and, if the first network element causes the optimal route to fail to conform to the at least one service requirement, analyzing the second network element to determine whether use of the second network element in the optimal route conforms to the at least one service requirement.

6. A computer-implemented method as recited in claim 5, wherein the at least one service requirement relates, at least in part, to a speed at which data is transmitted using the telecommunications service.

7. A computer-implemented method as recited in claim 6, wherein the at least one service requirement is a bandwidth requirement.

8. A computer-implemented method as recited in claim 1, wherein the telecommunications service comprises a wavelength service.

9. A non-transitory computer-readable medium having instructions stored thereon, the instructions, when executed by one or more processing devices, enabling the one or more processing devices to perform operations comprising:

(a) identifying a plurality of fiber segments within a communications network that provide capacity links between a source node and a destination node in the communication network, wherein each of the plurality of fiber segments is associated with a cost;

(b) filtering the plurality of fiber segments to a set of candidate fiber segments for use in forming a route for a telecommunications service based on an analysis of the cost of each of the plurality of fiber segments against at least one service requirement associated with the telecommunications service;

(c) selecting from the set of candidate fiber segments at least two fiber segments to form an optimal route for the telecommunications service;

(d) verifying whether the optimal route will satisfy the at least one service requirement, wherein the verifying act comprises;

(d)(i) identifying one or more network elements communicatively coupled to the at least two selected fiber segments for use in provisioning the telecommunications service over the optimal route;

(d)(ii) analyzing the one or more identified network elements to determine whether use of the one or more identified network elements in the optimal route conforms to the at least one service requirement; and

(d)(iii) based on the analyzing operation (d)(ii), if use of the one or more identified network elements in the optimal route does not conform to the at least one service requirement, then repeating the selecting operation (c), otherwise selecting the optimal route as the route for the telecommunications service.

10. A non-transitory computer-readable medium as recited in claim 9, wherein the cost associated with each of the plurality of fiber segments relates to distance, the selecting operation (c) comprising:

selecting the at least two fiber segments having a shorter distance between the source node and the destination node relative to other routes that could be formed by other fiber segments therebetween.

11. A non-transitory computer-readable medium as recited in claim 10, wherein the at least one service requirement relates, at least in part, to a speed at which data is transmitted using the telecommunications service.

12. A non-transitory computer-readable medium as recited in claim 11, wherein the at least one service requirement is a bandwidth measurement.

13. A non-transitory computer-readable medium as recited in claim 9, wherein the one or more identified network elements comprise at least a first network element and a second network element, the first network element and the second network element being co-located at a node, and wherein the analyzing operation (d)(ii) comprises:

analyzing the first network element to determine whether use of the first network element in the optimal route conforms to the at least one service requirement and, if the first network element causes the optimal route to fail to conform to the at least one service requirement, analyzing the second network element to determine whether use of the second network element in the optimal route conforms to the at least one service requirement.

14. A non-transitory computer-readable medium as recited in claim 13, wherein the at least one service requirement relates, at least in part, to a speed at which data is transmitted using the telecommunications service.

15. A non-transitory computer-readable medium as recited in claim 14, wherein the at least one service requirement is a bandwidth requirement.

16. A non-transitory computer-readable medium as recited in claim 13, wherein the node comprises one of the source node and the destination node.