Method of Determining Minimum Cost Path

• US 20090132989A1
• Filed: 11/15/2007
• Published: 05/21/2009
• Est. Priority Date: 11/15/2007
• Status: Active Grant

• Current Assignee: LYFT Incorporated
• Original Assignee: AT&T Knowledge Ventures, L.P. (AT&T, Inc.)
• Inventors: Ou, Canhui, Li, Jian, Echeverria-Calvet, Orlando, Gemelos, Steven, Osato, Jerold Daizo, Mountford, Howard Scott, Cronin, Thomas, Jacobson, Brent Edward
• Granted Patent: US 7,941,778 B2
• Time in Patent Office: Days
• US Class Current: 716/129
• 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 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; and

determining 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 the plurality of edges comprise a plurality of fiber edges to represent fiber hops, the plurality of fiber edges comprising a plurality of existing-fiber edges to represent fiber hops that exist in the network at a time of determining the minimum cost path, the plurality of fiber edges comprising a plurality of potential-fiber edges to represent fiber hops that do not exist in the network at the time of determining the minimum cost path.

5. The method of claim 4 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.

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

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

8. 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.

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 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.

10. 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.

11. 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.

12. The method of claim 11 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 11 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. The method of claim 17 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.

19. The method of claim 17 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.

20. The method of claim 17 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.

21. The method of claim 17 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.

22. The method of claim 17 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.

23. 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.

24. A computer system 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; 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.

25. A 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; 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.