Patent ID: 7477607

Claim:
A method for determining optimal number and sizes of resources to serve multiple demands where each of the demands is assigned to a single resource, wherein resource sizes and demand sizes are limited to power-of-two integers, the larger the resource size the higher its cost but the cost per size unit does not increase with the resource size, and the maximal number of allowed resources is limited to a specified parameter, where resources are subnets in a node of the Internet Protocol (IP) communications network that serve demands for blocks of addresses and demands are either subnets from other nodes in the Internet Protocol (IP) communications network or external demands, comprising the steps of: (a) finding an optimal solution to a relaxed problem wherein all demands are aggregated to a single demand and the constraints that each demand is assigned to a single resource are deleted by determining all dominating sets with a number of resources that does not exceed the maximal number of allowed resources and with a combined resource capacity that is equal to or larger than the aggregated demand, where a set of resources that can serve the aggregated demand dominates all other sets of resources with equal or less number of resources that can serve same aggregated demand if the sum of capacities of the former set is smaller than the sum of capacities of the latter sets, and selecting the minimum-cost dominating set as an optimal set of resources for the specified aggregated demand; and (b) taking the resource sizes of the optimal solution to the relaxed problem and assigning one at a time the largest unassigned demand into the resource whose remaining unused capacity is the smallest among all resources but at least as large as the demand.