Allocation of Resources of Modular Sizes with an Application to Internet Protocol (IP) Address Allocation

摘要

We consider a resource allocation problem, where resources of different capacities must satisfy multiple demands. The demand sizes and the resource capacities are limited to sizes that are power-of-two integers (i.e., 1, 2, 4, 8, ···)· The cost of the resources exhibit economies-of-scale savings, i.e., the cost per capacity unit is smaller for resources with larger capacity. The problem is to select the minimum-cost set of resources that satisfies the demands, while each of the demands must be assigned to a single resource and the number of selected resources does not exceed a specified upper bound. We present algorithms that take advantage of the special structure of the problem and provide optimal solutions in a negligible computing effort. This problem is important for the allocation of blocks of Internet Protocol (IP) addresses, referred to as subnets. In typical IP networks, subnets are allocated at a large number of nodes. An effective allocation attempts to balance the volume of excess addresses that are not used versus fragmentation of addresses at nodes to too many subnets with a discontinuous range of addresses. Due to the efficiency of the algorithms, they can readily be used as valuable modules in IP address management systems.