Patent ID: 6965944

Claim:
A method for designing tree-structured communication routes, in which plural ingress nodes, a single common egress node, plural connection nodes situated between said plural ingress nodes and said single common egress node, comprising the sequential steps of: determining a set of plural routes starting from each of said plural ingress nodes, via said plural connection nodes, to said common egress node; determining whether a first condition that any node, except said egress node, in a selected route successively selected from said set of plural routes, does not appear on another route, is satisfied, and when the first condition is satisfied, adding a predetermined point to a score of the route; determining whether a second condition that, when there is a common node, in addition to said common egress node, which appears in both said selected route and said another route, and said selected route agrees with said another route from said common node to said common egress node, is satisfied, and when the second condition is satisfied, adding the predetermined point to the score of the route successively selected from said set of plural routes; successively selecting said routes in reverse order of said scores of said routes; respectively generating a first tree, extending from at least two of said plural ingress nodes to said common egress node, from said route with a lowest score and said other routes based on shared routings, along said route and said other routes, to the common egress node; and successively generating other trees, extending from at least one of said plural ingress nodes to said common egress node, from said other routes which are unable to generate said first tree, based on shared routings along said other routes to the common egress node.