Back to results
US 8,831,012 B2Granted
Determining paths in a network with asymmetric switches
AssigneeFujitsu Limited
InventorsMin He, Kevin Zhu, Srinivas Vobilisetti, Takao Naito, Paparao Palacharla, Xi Wang, Qiong Zhang
Life of this patent
Estimating the term…
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.
Claims20
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.
1 more element
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.
3 more elements
Dependencies are inferred from the claim text.