Patent ID: 7003300

Claim:
A method of routing in a telecommunications network, comprising the steps of: partitioning a main graph of the network into partitions; creating a reduced graph of the partitions by constructing a dual graph of the network, and by reducing the main graph using connections restricted by characteristics of apparatuses on the network; and performing the routing on the reduced graph; wherein the reduced graph is created by: a) assigning each port of the main graph of fictitious node in the reduced graph; b) for each partition, dividing a set of ports of the network into input and output ports, and associating each fictitious node of an assigned port as a fictitious input node or a fictitious output node depending on a direction of the assigned port; c) connecting the fictitious input node or the fictitious output node to a network node in the main graph; d) assigning a zero cost to a bridge which has the fictitious output node at its upstream end; e) maintaining a cost of the bridge having the fictitious input node at its downstream end unvaried at a predetermined value to avoid counting the cost more than once; f) calculating paths from each fictitious input node to each fictitious output node, each path being characterized by a set of bridges of the main graph which connect a pair of input and output ports; and g) associating with each path characterized by a set of not empty bridges, a bridge in the reduced graph that connects the fictitious nodes representing the pair of input and output ports; if a path between two fictitious nodes does not exist and thus the set of bridges associated with this path is an empty set, then the bridge is not inserted in the reduced graph.