Routing and design in K-shared network
View Patent ↗Techniques for network routing and design are provided. A technique for determining a route for a demand in a network, wherein the network comprises primary paths and secondary paths, and at least two secondary paths may share a given link, comprises the following steps/operations. First, a graph representing the network is transformed. Edges of the graph represent channels associated with paths and nodes of the graph represent nodes of the network. The transformation is performed such that costs associated with the edges reflect costs of using channels in secondary paths. Then, the shortest path between nodes corresponding to the demand is found in the transformed graph. The shortest path represents the least-cost path in the network over which the demand may be routed. When the above route determination steps/operations result in a path with at least one loop, an alternative routing process may be executed so as to determine a loopless path for the demand. Further, integer linear program formulation design techniques are provided.
1. A method of determining a route for a demand in a network, wherein the network comprises primary paths and secondary paths, and at least two secondary paths may share a given link, the method comprising the steps of:
transforming a graph representing the network, wherein edges of the graph represent channels associated with paths and nodes of the graph represent nodes of the network, the transformation being performed such that costs associated with the edges reflect costs of using channels in secondary paths; and
finding the shortest path between nodes corresponding to the demand in the transformed graph, the shortest path representing the least-cost path in the network over which the demand may be routed.
2. The method of claim 1 , wherein the graph transformation step further comprises the step of transforming channels into nodes of the graph.
3. The method of claim 2 , wherein a path comprises one or more links and a link l between two nodes u and v is represented as (u, v) and a channel in the link is represented as l i such that the step of transforming channels into nodes further comprises creating two nodes u(l, i) and v(l, i) and an edge between them.
4. The method of claim 3 , wherein the cost of the created edge is a function of the channel.
5. The method of claim 4 , wherein the graph transformation step further comprises the step of representing channel connectivity.
6. The A method of determining a route for a demand in a network, wherein the network comprises primary paths and secondary paths, and at least two secondary paths may share a given link, the method comprising the steps of:
transforming a graph representing the network, wherein edges of the graph represent channels associated with paths and nodes of the graph represent nodes of the network, the transformation being performed such that costs associated with the edges reflect costs of using channels in secondary paths, wherein the cost of the created edge is a function of the channel; and
finding the shortest path between nodes corresponding to the demand in the transformed graph, the shortest path representing the least-cost path in the network over which the demand may wherein the graph transformation step further comprises the steps of transforming channels into nodes of the graph and representing channel connectivity;
wherein a path comprises one or more links and a link l between two nodes u and v is represented as (u, v) and a channel in the link is represented as l i such that the step of transforming channels into nodes further comprises creating two nodes u(l,i) and v(l,i) and an edge between them:
wherein a pair of channels maybe represented as l i and m j incident on a node u such that the channel connectivity representation step further comprises:
when the pair of channels are already connected at u, adding a zero-cost edge between u(l, i) and u(m, j); and
otherwise, when both of the channels have degrees less than a value K at u, connecting them with an edge having a cost ∈ , where cost ∈ is greater than zero and substantially smaller than one.
7. The method of claim 6 , wherein the cost ∈ is selected to prefer existing connections over new connections.
8. The method of claim 7 , wherein the graph transformation step further comprises the step of including the source nodes and the destination node t associated with the demand in the transformed graph.
9. The method of claim 8 , wherein the step of including the source node and the destination node in transformed graph further comprises creating node s ′corresponding to s such that when channel l i in link (s, x) is incident on s and when the degree of link (s, x) at s is less than K, s ′and s(l,i) are connected at zero cost.
10. The method of claim 8 , wherein the step of including the source node and the destination node in transformed graph further comprises creating node t′corresponding to t such that when channel l i in link (x, t) is incident on t and when the degree of link (x, t) at t is less than K, t′and t(t, i) are connected at zero cost.
11. The method of claim 1 , wherein when the route determination steps result in a path with at least one loop, executing an alternative routing process so as to determine a loopless path for the demand.
12. The method of claim 11 , wherein the alternative routing process further comprises the step of finding r shortest paths between the source node and the destination node associated with the demand in the graph.
13. The method of claim 12 , wherein the alternative routing process further comprises the step of, for each of the r shortest paths, computing a corresponding least-cost loopless path.
14. The method of claim 13 , wherein the alternative routing process further comprises the step of selecting the least-cost path among the r paths as a secondary path for the demand.
15. The method of claim 1 , wherein the transforming and finding steps are used to compute one or more paths for optical burst switching.
16. A method of designing a K-shared network based on a set of one or more demands, comprising the steps of:
computing candidate primary paths and candidate secondary paths based on the set of one or more demands, wherein at least two candidate secondary paths may share a given channel and the number of shared channels incident on another channel is a finite number K;
applying an integer linear program formulation to the computed candidate primary paths and candidate secondary paths; and
solving the integer linear program formulation applied to the computed candidate primary paths and candidate secondary paths so as to generate a K-shared network design.
17. Apparatus for determining a route for a demand in a network, wherein the network comprises primary paths and secondary paths, and at least two secondary paths may share a given link, the apparatus comprising:
a memory; and
at least one processor coupled to the memory and operative to: (i) transform a graph representing the network, wherein edges of the graph represent channels associated with paths and nodes of the graph represent nodes of the network, the transformation being performed such that costs associated with the edges reflect costs of using channels in secondary paths; and (ii) find the shortest path between nodes corresponding to the demand in the transformed graph, the shortest path representing the least-cost path in the network over which the demand may be routed.
18. The apparatus of claim 17 , wherein the graph transformation operation further comprises transforming channels into nodes of the graph.
19. The apparatus of claim 18 , wherein a path comprises one or more links and a link l between two nodes u and v is represented as (u, v) and a channel in the link is represented as l i such that the step of transforming channels into nodes further comprises creating two nodes u(l, i) and v(l, i) and an edge between them.
20. The apparatus of claim 19 , wherein the cost of the created edge is a function of the channel.
21. The apparatus of claim 20 , wherein the graph transformation operation further comprises representing channel connectivity.
22. Apparatus for determining a route for a demand in a network, wherein the network comprises primary paths and secondary paths, and at least two secondary paths may share a given link, the apparatus comprising:
a memory; and
at least one processor coupled to the memory and operative to: (i) transform a graph representing the network, wherein edges of the graph represent channels associated with paths and nodes of the graph represent nodes of the network, the transformation being performed such that costs associated with the edges reflect costs of using channels in secondary paths, wherein the cost of the created edge is a function of the channel; and (ii) find the shortest path between nodes corresponding to the demand in the transformed graph, the shortest path representing the least-cost path in the network over which the demand may be routed;
wherein the graph transformation operation further comprises transforming channels into nodes of the graph and representing channel connectivity;
wherein a path comprises one or more links and a link l between two nodes u and v is represented as (u, v) and a channel in the link is represented as l i such that the step of transforming channels into nodes further comprises creating two nodes u(l, i) and v(l, i) and an edge between them;
wherein a pair of channels maybe represented as l i and m j incident on a node u such that the channel connectivity representation operation further comprises, when the pair of channels are already connected at u, adding a zero-cost edge between u(l, i) and u(m,j), and otherwise, when both of the channels have degrees less than a value K at u, connecting them with an edge having a cost ∈, where cost ∈ is greater than zero and substantially smaller than one.
23. The apparatus of claim 22 , wherein the cost ∈ is selected to prefer existing connections over new connections.
24. The apparatus of claim 23 , wherein the graph transformation operation further comprises including the source node s and the destination node t associated with the demand in the transfonned graph.
25. The apparatus of claim 24 , wherein the operation of including the source node and the destination node in transfonned graph further comprises creating node s′corresponding to s such that when channel l i in link (s, x) is incident on s and when the degree of link (s, x) at s is less than K, s′and s(l, i) are connected at zero cost.
26. The method of claim 24 , wherein the operation of including the source node and the destination node in transformed graph further comprises creating node t′corresponding to t such that when channel l i in link (x, t) is incident on t and when the degree of link (x, t) at is less than K, t′and t(l, i) are connected at zero cost.
27. The apparatus of claim 17 , wherein when the route determination operations result in a path with at least one loop, executing an alternative routing process so as to determine a loopless path for the demand.
28. The apparatus of claim 27 , wherein the alternative routing process further comprises finding r shortest paths between the source node and the destination node associated with the demand in the graph.
29. The apparatus of claim 28 , wherein the alternative routing process further comprises, for each of the r shortest paths, computing a corresponding least-cost loopless path.
30. The apparatus of claim 29 , wherein the alternative routing process further comprises selecting the least-cost path among the r paths as a secondary path for the demand.
31. The apparatus of claim 17 , wherein the transforming and finding operations are used to compute one or more paths for optical burst switching.
32. Apparatus for designing a K-shared network based on a set of one or more demands, the apparatus comprising:
a memory; and
at least one processor coupled to the memory and operative to: (i) compute candidate primary paths and candidate secondary paths based on the set of one or more demands, wherein at least two candidate secondary paths may share a given channel and the number of shared channels incident on another channel is a finite number K; (ii) apply an integer linear program formulation to the computed candidate primary paths and candidate secondary paths; and (iii) solve the integer linear program formulation applied to the computed candidate primary paths and candidate secondary paths so as to generate a K-shared network design.