Employing parallel processing for routing calls

A method for identifying a least-cost path between a node A of a network of nodes that are interconnected by links and a node B of the network, where associated with each link is a cost measure for traversing the link, comprising the steps of:

• dividing the network into a plurality of three more segments, where
• a first one of the segments contains node A, some of said nodes, some of said links, and a first plurality of half nodes formed from some of said nodes, which half nodes form a first interface to a remainder of the network,
• a second one of the segments contains node B, some of said nodes, some of said links, and a second plurality of half nodes formed from some of said nodes, which half nodes form a second interface to a remainder of the network, and
• remainder of said three or more segments between said first one of the segments and said second one of the segments, each one of said segments in said remainder of said three or more segments having a plurality of half nodes Nli and a plurality of half nodes Nri, and some of said nodes and some of said links interposed between the half nodes, where index i designates the segments;
• in connection with each of the three or more segments, executing an associated algorithm to compute path costs, where a path comprises links, and a path cost is a sum of the costs associated with the links of which the path is comprised, substantially concurrently with the execution of the algorithms of all of the segments;
• and
• identifying said least-cost path using results of the substantially concurrent executions of the algorithms associated with said segments.