MULTICAST TREE DESIGN APPARATUS, METHOD, AND PROGRAM PRODUCT

A multicast tree design apparatus designs a multicast tree by mathematical programming. The multicast tree design apparatus is one 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 including a problem creating unit and a problem solving unit, and wherein: the problem creating unit includes a multiple route constraint creating unit for creating constraint expressions for constructing a plurality of routes that start from a source node and end at a plurality of destination nodes, a tree constraint creating unit for creating a constraint expression for superposing all the routes to construct a multicast tree, a confluence constraint creating unit for creating a constraint expression for preventing the plurality of routes from being superposed into a topology that causes a confluence of the routes, 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; and the problem solving unit solves a mathematical programming problem including the constraint expressions and the objective function created by the problem creating unit to determine a set of links that constitute the multicast tree.