Determining Paths In A Network With Asymmetric Switches

• US 20110080846A1
• Filed: 10/07/2009
• Published: 04/07/2011
• Est. Priority Date: 10/07/2009
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Inventors: Wang, Xi, Zhu, Kevin, Zhang, Qiong, Vobilisetti, Srinivas, He, Min, Naito, Takao, Palacharla, Paparao
• Granted Patent: US 8,831,012 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/128 for finding disjoint paths
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13148 Maximum profit routing
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

According to particular embodiments, determining paths in a network with asymmetric switches includes receiving a graph representing the network. Each asymmetric switch has defined degree connectivity between one or more pairs of degrees of the asymmetric switch. The graph is transformed to yield a transformed graph that accounts for the asymmetric switches. A routing process is applied to the transformed graph to yield one or more paths through the network.

Claims

1. A method comprising:

receiving a graph representing a network comprising a plurality of nodes, the plurality of nodes comprising one or more asymmetric switches, each asymmetric switch having defined degree connectivity between one or more pairs of degrees of the asymmetric switch;

transforming the graph to yield a transformed graph that accounts for the one or more asymmetric switches; and

applying a routing process to the transformed graph to yield one or more paths through the network.

2. The method of claim 1, the transforming the graph to yield the transformed graph further comprising:

if an asymmetric switch is a pass-through node, adding one or more virtual links to the asymmetric switch, each virtual link representing defined degree connectivity between a pair of degrees of the asymmetric switch.

3. The method of claim 1, the transforming the graph to yield the transformed graph further comprising:

if an asymmetric switch is an add/drop node, maintaining the defined degree connectivity of the asymmetric switch.

4. The method of claim 1, the one or more asymmetric switches comprising an intra-connected switch pair comprising a first switch and a second switch, the first switch having a first degree, the second switch having a second degree with degree connectivity to the first degree.

5. The method of claim 4, the transforming the graph to yield the transformed graph further comprising:

if the first switch and the second switch are pass-through nodes, adding one or more virtual links to the intra-connected switch pair, each virtual link representing defined degree connectivity between a pair of degrees.

6. The method of claim 4, the transforming the graph to yield the transformed graph further comprising:

if the first switch and the second switch are add/drop nodes, maintaining the defined degree connectivity of the first switch and the second switch.

7. The method of claim 4, the transforming the graph to yield the transformed graph further comprising:

if the first switch is an add/drop node, maintaining the defined degree connectivity of the first switch.

8. The method of claim 1, the applying the routing process to the transformed graph further comprising:

applying a shortest path routing process to the transformed graph.

9. The method of claim 1, the applying the routing process to the transformed graph further comprising:

repeating the following for a plurality of iterations until a stopping point is reached;

calculating a current shortest path between a source node and a destination node of the transformed graph;

computing a plurality of current disjoint paths for the current shortest path; and

determining if the current disjoint paths are optimal disjoint paths for the current iteration; and

when the stopping point has been reached, outputting the optimal disjoint paths of the current iteration at the stopping point.

10. The method of claim 1, the applying the routing process to the transformed graph further comprising:

determining if a plurality of current disjoint paths of a current iteration are optimal by;

calculating a current cost of the current disjoint paths; and

if the current cost that is less than a previous optimal cost of a plurality of previous optimal disjoint paths of a previous iteration, then determining that the current disjoint paths are optimal.

11. The method of claim 1, the applying the routing process to the transformed graph further comprising:

deciding the stopping point is reached by;

calculating a shortest path cost of a shortest path of a current iteration;

comparing the shortest path cost and a current optimal cost of a plurality of current optimal disjoint paths of the current iteration; and

deciding whether the stopping point is reached in accordance with the comparison.

12. An apparatus comprising:

one or more computer readable media configured to store a graph representing a network comprising a plurality of nodes, the plurality of nodes comprising one or more asymmetric switches, each asymmetric switch having defined degree connectivity between one or more pairs of degrees of the asymmetric switch; and

one or more processors configured to;

transform the graph to yield a transformed graph that accounts for the one or more asymmetric switches; and

apply a routing process to the transformed graph to yield one or more paths through the network.

13. The apparatus of claim 12, the one or more processors configured to transform the graph to yield the transformed graph by:

if an asymmetric switch is a pass-through node, adding one or more virtual links to the asymmetric switch, each virtual link representing defined degree connectivity between a pair of degrees of the asymmetric switch.

14. The apparatus of claim 12, the one or more processors configured to transform the graph to yield the transformed graph by:

if an asymmetric switch is an add/drop node, maintaining the defined degree connectivity of the asymmetric switch.

15. The apparatus of claim 12, the one or more asymmetric switches comprising an intra-connected switch pair comprising a first switch and a second switch, the first switch having a first degree, the second switch having a second degree with degree connectivity to the first degree.

16. The apparatus of claim 15, the one or more processors configured to transform the graph to yield the transformed graph by:

if the first switch and the second switch are pass-through nodes, adding one or more virtual links to the intra-connected switch pair, each virtual link representing defined degree connectivity between a pair of degrees.

17. The apparatus of claim 15, the one or more processors configured to transform the graph to yield the transformed graph by:

if the first switch and the second switch are add/drop nodes, maintaining the defined degree connectivity of the first switch and the second switch.

18. The apparatus of claim 15, the one or more processors configured to transform the graph to yield the transformed graph by:

if the first switch is an add/drop node, maintaining the defined degree connectivity of the first switch.

19. The apparatus of claim 12, the one or more processors configured to apply the routing process to the transformed graph by:

applying a shortest path routing process to the transformed graph.

20. The apparatus of claim 12, the one or more processors configured to apply the routing process to the transformed graph by:

repeating the following for a plurality of iterations until a stopping point is reached;

calculating a current shortest path between a source node and a destination node of the transformed graph;

computing a plurality of current disjoint paths for the current shortest path; and

determining if the current disjoint paths are optimal disjoint paths for the current iteration; and

when the stopping point has been reached, outputting the optimal disjoint paths of the current iteration at the stopping point.

21. The apparatus of claim 12, the one or more processors configured to apply the routing process to the transformed graph by:

determining if a plurality of current disjoint paths of a current iteration are optimal by;

calculating a current cost of the current disjoint paths; and

if the current cost that is less than a previous optimal cost of a plurality of previous optimal disjoint paths of a previous iteration, then determining that the current disjoint paths are optimal.

22. The apparatus of claim 12, the one or more processors configured to apply the routing process to the transformed graph by:

deciding the stopping point is reached by;

calculating a shortest path cost of a shortest path of a current iteration;

comparing the shortest path cost and a current optimal cost of a plurality of current optimal disjoint paths of the current iteration; and

deciding whether the stopping point is reached in accordance with the comparison.