Article ID: | iaor20072413 |
Country: | United States |
Volume: | 52 |
Issue: | 8 |
Start Page Number: | 713 |
End Page Number: | 723 |
Publication Date: | Dec 2005 |
Journal: | Naval Research Logistics |
Authors: | Luss Hanan |
Keywords: | programming: integer, communication |
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 exhibits 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.