Patent ID: 8102850

Claim:
A multicast tree design apparatus for designing a multicast tree for transferring a packet from a source node to a plurality of destination nodes on a network that includes nodes and links connecting the nodes, the apparatus comprising: a problem creating unit; and a problem solving unit, wherein the problem creating unit includes: a multiple route constraint creating unit for creating first constraint expressions for constructing a plurality of routes that start from a source node and end at a plurality of destination nodes, said first constraint expressions being used for a mathematical programming problem; a tree constraint creating unit for creating second constraint expressions for superposing all the routes to construct a multicast tree, said second constraint expressions being used for the mathematical programming problem; a confluence constraint creating unit for creating third constraint expressions for preventing the plurality of routes from being superposed into a topology that causes a confluence of the routes, said third constraint expressions being used for the mathematical programming problem; and an objective function creating unit for creating an objective function for minimizing an evaluation index pertaining to the links or the nodes that constitute the multicast tree, said objective function being used for the mathematical programming problem, and wherein the problem solving unit solves the mathematical programming problem including the first, second, and third constraint expressions and the objective function created by the problem creating unit to determine a set of links that constitute the multicast tree.