System and method of determining minimum cost path

• US 7,941,778 B2
• Filed: 11/15/2007
• Issued: 05/10/2011
• Est. Priority Date: 11/15/2007
• Status: Active Grant

• Current Assignee: LYFT Incorporated
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Mountford, Howard Scott, Cronin, Thomas, Jacobson, Brent Edward, Ou, Canhui, Li, Jian, Echeverria-Calvet, Orlando, Gemelos, Steven, Osato, Jerold Daizo
• Primary Examiner(s): Lin; Sun J
• Assistant Examiner(s): Memula; Suresh
• Application Number:
  US11/940,842
• Publication Number:
  US 20090132989A1
• Time in Patent Office: 1,272 Days
• Field of Search: 716/12, 716/126, 398/57, 398/58
• US Class Current: 716/126
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A network is represented using a graph. The graph comprises a plurality of vertices and a plurality of edges. The vertices comprise a source vertex, a destination vertex and a vertex u. The edges link corresponding adjacent pairs of the vertices. A minimum cost path in the graph is determined from the source vertex to the destination vertex, wherein the vertex u is in the minimum cost path. An edge from the vertex u in the minimum cost path introduces an additional capital expenditure cost that is dependent on how the minimum cost path traverses from the source vertex to the vertex u.

Claims

1. A computer-implemented method comprising:

representing a network using a graph, the graph comprising a plurality of vertices and a plurality of edges, the plurality of vertices comprising a source vertex, a destination vertex and a vertex u, the plurality of edges linking corresponding adjacent pairs of the plurality of vertices, the plurality of edges comprising edges corresponding to existing fiber optic cables;

augmenting the graph with additional edges representing potential new fiber optic cables such that an additional edge is added between any pair of adjacent vertices directly connected by an edge corresponding to one of the existing fiber optic cables, the additional edge having a cost corresponding to the cost of laying the new fiber optic cable; and

determining, in a processor, a minimum cost path in the graph from the source vertex to the destination vertex, wherein the vertex u is in the minimum cost path, and wherein an edge from the vertex u in the minimum cost path introduces an additional capital expenditure cost that is dependent on how the minimum cost path traverses from the source vertex to the vertex u.

2. The method of claim 1 wherein the additional capital expenditure cost depends on a loss from the source vertex to the vertex u.

3. The method of claim 1 wherein the additional capital expenditure cost depends on a composition of network elements from the source vertex to the vertex u in the minimum cost path.

4. The method of claim 1 wherein any pair of the vertices that are adjacent via a corresponding one of the existing-fiber edges are also adjacent via a corresponding one of the potential-fiber edges.

5. The method of claim 1 wherein the plurality of edges further comprise a plurality of Wavelength Division Multiplexing (WDM) edges to represent hops via WDM equipment.

6. The method of claim 5 further comprising distinguishing the plurality of fiber edges from the plurality of WDM edges.

7. The method of claim 1 wherein the edge introduces a first additional capital expenditure cost for a first path from the source vertex to the vertex u, wherein the edge introduces a second additional capital expenditure cost for a second path from the source vertex to the vertex u, wherein the first path differs from the second path, and wherein the first additional capital expenditure cost differs from the second additional capital expenditure cost.

8. The method of claim 1 wherein said determining the minimum cost path comprises, for each of a plurality of unsettled neighboring vertices of the vertex u, relaxing an unsettled neighboring vertex dependent on whether a segment start value for a path up to the vertex u represents a Reconfigurable Optical Add/Drop Multiplexer (ROADM) via lambda, a router, or ROADM via fiber.

9. The method of claim 1 wherein said determining the minimum cost path comprises, for each of a plurality of unsettled neighboring vertices of the vertex u, relaxing an unsettled neighboring vertex dependent on whether an edge from the vertex u to the unsettled neighboring vertex represents a Reconfigurable Optical Add/Drop Multiplexer (ROADM) hop, a hub ROADM auxiliary hop, a non-hub ROADM auxiliary hop, or a fiber hop.

10. The method of claim 1 wherein the additional capital expenditure cost introduced by the edge depends on a segment start value for a path up to the vertex u.

11. The method of claim 10 wherein if the segment start value for the vertex u indicates a Reconfigurable Optical Add/Drop Multiplexer (ROADM) via fiber and if the edge represents a fiber hop, then the additional capital expenditure cost introduced by the edge comprises a cost associated with a ROADM optic interface upgrade due to a link loss of the fiber hop.

12. The method of claim 10 wherein if the segment start value for the vertex u indicates a router and if the edge represents a fiber hop, then the additional capital expenditure cost introduced by the edge comprises a cost associated with a layer-3 network router interface optics upgrade due to a link loss of the fiber hop.

13. The method of claim 1, wherein if the edge represents a non-hub Reconfigurable Optical Add/Drop Multiplexer (ROADM) auxiliary hop from the vertex u to a vertex v, then the additional capital expenditure cost introduced by the edge comprises a ROADM optical interface cost dependent on a loss along a path to the vertex v.

14. The method of claim 1 wherein if the edge represents a Reconfigurable Optical Add/Drop Multiplexer (ROADM) hop from the vertex u to a vertex v, then the additional capital expenditure cost introduced by the edge comprises a cost associated with laying new fiber between the vertex u and a vertex v.

15. The method of claim 1 wherein if the edge represents a hub Reconfigurable Optical Add/Drop Multiplexer (ROADM) auxiliary hop from the vertex u to a vertex v, then the additional capital expenditure cost introduced by the edge comprises a cost associated with a lambda access module.

16. The method of claim 1 wherein the plurality of vertices comprise a vertex v that is adjacent the vertex u in the minimum cost path via the edge.

17. The method of claim 16 wherein said determining the minimum cost path comprises setting a value to indicate that a path up to the vertex v starts with a Reconfigurable Optical Add/Drop Multiplexer (ROADM) node via a lambda based on determining that the edge represents either a ROADM hop or a hub ROADM auxiliary hop.

18. The method of claim 16 wherein said determining the minimum cost path comprises setting a value to indicate that a path up to the vertex v starts with a Reconfigurable Optical Add/Drop Multiplexer (ROADM) node via fiber based on determining that the edge represents a non-hub ROADM auxiliary hop and a path up to the vertex u starts with a ROADM via lambda.

19. The method of claim 16 wherein said determining the minimum cost path comprises setting a value to indicate that a path up to the vertex v starts with a Reconfigurable Optical Add/Drop Multiplexer (ROADM) node via a lambda based on determining that the edge represents a non-hub ROADM auxiliary hop and a path up to the vertex u starts with either a router or a ROADM via fiber.

20. The method of claim 16 wherein said determining the minimum cost path comprises setting a value to indicate that a path up to the vertex v starts with a router based on determining that the edge represents a fiber hop and a path up to the vertex u starts with a router.

21. The method of claim 16 wherein said determining the minimum cost path comprises setting a value to indicate that a path up to the vertex v starts with a Reconfigurable Optical Add/Drop Multiplexer (ROADM) node via fiber based on determining that the edge represents a fiber hop and a path up to the vertex u starts with a ROADM via fiber.

22. The method of claim 1 further comprising:

routing at least a portion of a circuit from the source vertex to the destination vertex using the minimum cost path.

23. A computer system comprising:

a processor programmed to;

represent a network using a graph, the graph comprising a plurality of vertices and a plurality of edges, the plurality of vertices comprising a source vertex, a destination vertex and a vertex u, the plurality of edges linking corresponding adjacent pairs of the plurality of vertices, the plurality of edges comprising edges corresponding to existing fiber optic cables;

augment the graph with additional edges representing potential new fiber optic cables such that an additional edge is added between any pair of adjacent vertices directly connected by an edge corresponding to one of the existing fiber optic cables, the additional edge having a cost corresponding to the cost of laying the new fiber optic cable; and

determine a minimum cost path in the graph from the source vertex to the destination vertex, wherein the vertex u is in the minimum cost path, and wherein an edge from the vertex u in the minimum cost path introduces an additional capital expenditure cost that is dependent on how the minimum cost path traverses from the source vertex to the vertex u.

24. A non-transitory computer-readable storage medium encoded with a computer program, the computer program to cause a computer system to:

represent a network using a graph, the graph comprising a plurality of vertices and a plurality of edges, the plurality of vertices comprising a source vertex, a destination vertex and a vertex u, the plurality of edges linking corresponding adjacent pairs of the plurality of vertices, the plurality of edges comprising edges corresponding to existing fiber optic cables;

augment the graph with additional edges representing potential new fiber optic cables such that an additional edge is added between any pair of adjacent vertices directly connected by an edge corresponding to one of the existing fiber optic cables, the additional edge having a cost corresponding to the cost of laying the new fiber optic cable; and

determine a minimum cost path in the graph from the source vertex to the destination vertex, wherein the vertex u is in the minimum cost path, and wherein an edge from the vertex u in the minimum cost path introduces an additional capital expenditure cost that is dependent on how the minimum cost path traverses from the source vertex to the vertex u.