Patent ID: 7590067
Filing Date: 2009-09-15
Classification: H04L

Abstract:
1. A method for computing paths through a data network that includes a subnetwork which introduces a subset intransitivity constraint on allowable paths through the data network, wherein each one of two adjacent links have sufficient capacity to convey traffic but it is not possible to transmit that traffic through both links in sequence, the method comprising: using an abstracted map of the network that includes network elements (NEs) and subnetwork elements (SNEs), with links between pairs of the NEs and the SNEs to construct a directed graph that compensates for the subset intransitivity constraint; and applying a routing algorithm to compute paths from a start node to the other nodes of the directed graph, wherein the constructing the directed graph comprises: creating a node in the directed graph to represent each NE in the abstracted network map; creating in the graph one ingress node and one egress node to represent each SNE in the abstracted network map, and defining an edge in the directed graph from the ingress node to the egress node; for each link between two SNEs in the same subnetwork, defining edges in the directed graph from an ingress node representing a first SNE of the pair to the an egress node representing a second SNE of the pair, and from the ingress node representing the second SNE of the pair to the egress node representing the first SNE of the pair; for each link between a SNE and a NE, defining an edge from the egress node representing the SNE to a node representing the NE, and an edge from the node representing the NE to the ingress node representing the SNE; and for each link between two NEs, defining two oppositely directed edges between the nodes representing the NEs.