Determining paths in a network with asymmetric switches

• US 8,831,012 B2
• Filed: 10/07/2009
• Issued: 09/09/2014
• Est. Priority Date: 10/07/2009
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: He, Min, Zhu, Kevin, Vobilisetti, Srinivas, Naito, Takao, Palacharla, Paparao, Wang, Xi, Zhang, Qiong
• Primary Examiner(s): Lee, Jae Y
• Application Number:
  US12/574,972
• Publication Number:
  US 20110080846A1
• Time in Patent Office: 1,798 Days
• US Class Current: 370/401
• 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 graph comprising representations of the plurality of nodes and the links between the nodes, the plurality of nodes comprising one or more asymmetric switches, each asymmetric switch having defined degree connectivity between two or more pairs of degrees of the asymmetric switch, and where pass-through traffic can flow from an input degree to an output degree of the asymmetric switch only if degree connectivity between the input and output degrees has been defined;

transforming the graph to yield a transformed graph that accounts for the one or more asymmetric switches, wherein transforming the graph comprises, if an asymmetric switch is a pass-through node, adding two or more virtual links to the graph, each virtual link representing a defined degree connectivity between a particular pair of degrees of the asymmetric switch, each virtual link existing between a first node of the network connected to a first degree of the particular pair and a second node of the network connected to a second degree of the particular pair; 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 an add/drop node, maintaining the defined degree connectivity of the asymmetric switch.

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

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

if the first switch and the second switch are pass-through nodes, adding a second virtual link to the graph, the second virtual link representing the defined degree connectivity between the first degree of the first switch and the second degree of the second switch, the second virtual link existing between a third node of the network connected to the first degree of the first switch and a fourth node of the network connected to a second degree of the second switch.

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

6. The method of claim 3, 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.

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

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

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

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

11. An apparatus comprising:

one or more computer readable media configured to store a graph representing a network comprising a plurality of nodes, the graph comprising representations of the plurality of nodes and the links between the nodes, the plurality of nodes comprising one or more asymmetric switches, each asymmetric switch having defined degree connectivity between two or more pairs of degrees of the asymmetric switch, and where pass-through traffic can flow from an input degree to an output degree of the asymmetric switch only if degree connectivity between the input and output degrees has been defined; and

one or more processors configured to;

transform the graph to yield a transformed graph that accounts for the one or more asymmetric switches, wherein transforming the graph comprises, if an asymmetric switch is a pass-through node, adding two or more virtual links to the graph, each virtual link representing a defined degree connectivity between a particular pair of degrees of the asymmetric switch, each virtual link existing between a first node of the network connected to a first degree of the particular pair and a second node of the network connected to a second degree of the particular pair; and

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

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

13. The apparatus of claim 11, 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.

14. The apparatus of claim 13, 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 a second virtual link to the graph, the second virtual link representing the defined degree connectivity between the first degree of the first switch and the second degree of the second switch, the second virtual link existing between a third node of the network connected to the first degree of the first switch and a fourth node of the network connected to a second degree of the second switch.

15. The apparatus of claim 13, 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.

16. The apparatus of claim 13, 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.

17. The apparatus of claim 11, 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.

18. The apparatus of claim 11, 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.

19. The apparatus of claim 11, 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.

20. The apparatus of claim 11, 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.