Abstract:
Methods for allocating blocks of addresses to nodes in an IP communications network determine an optimal set of serving subnets, referred to as resources, for a single node in an IP communications network with given input demands for blocks of addresses. An optimal set of resources is determined at the node to a relaxed problem that aggregates all the demands to a single large demand and deletes the constraints that each demand must be assigned to a single resource. Each of the original demands is assigned to a single resource from among those determined by the solution to the relaxed problem. The optimal solution balances the amount of excess addresses that are not used at the resources with the fragmentation of addresses at the node to too many resources with a discontinuous range of addresses. New resources can be allocated to nodes that already have existing resources. Specifically, it is possible to evaluate the desirability of returning existing resources to a pool of addresses in order to gain more flexibility in allocating new resources to the node. The methods can also be used to allocate subnets at all nodes in a tree network by solving repeatedly single-node problems, starting at the lowest level of the tree. The resulting serving subnets at nodes of one level are demands to nodes at the next higher level.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application claims the benefit of the filing date of U.S. Provisional Patent Application No. 60/623,808, filed Oct. 29, 2004, the disclosure of which is hereby incorporated herein by reference. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The present invention relates to internet protocol (IP) communications networks. More particularly, the invention relates to methods for allocating blocks of addresses to nodes in an IP communications network.  
       BACKGROUND OF THE INVENTION  
       [0003]     Internet Protocol (IP) communications networks have become critically important for voice, data and video communications. As a result, these networks are rapidly growing in size and complexity. IP communications networks route packets of information from sources to destinations using routing tables that include IP addresses. One or more blocks of IP addresses are allocated to a node. Each block of addresses comprises consecutive numbers. A block of addresses is called a subnet. Due to the significant increase in IP services, IP addresses are now recognized as a critical resource. While service providers must maintain a high utilization of their IP address pool, they also desire to limit the number of subnets at a node, since excessive fragmentation of addresses at a node leads to inefficient traffic routing. Telecommunications service providers, software providers, and equipment manufacturers have realized the need for software systems that effectively manage IP addresses using automated systems. However, current state-of-the-art systems use ad-hoc heuristic methods and IP communications network managers&#39; experience for the allocation of subnets among the nodes in the network. Optimization-based models for the optimal allocation of subnets at every node of an IP communications network would significantly enhance such automated systems. Many IP text books provide background material on the planning and management of IP addresses. For example, K. Washburn and J. Evans provide such background in Chapter 3 of their book  TCP/IP: Running a Successful Network , Addison-Wesley, Second Edition, 1996, which is incorporated herein by reference.  
       SUMMARY OF THE INVENTION  
       [0004]     The present invention provides methods for the optimal allocation of blocks of addresses, called subnets, in IP communications networks. Consider a single node in an IP communications network. This node may have to accommodate multiple demands. Each of these demands is a block of IP addresses whose size is a power-of-two integer. A demand may be a subnet allocated to a node at a lower level in the network or an external demand for addresses at the node. These demands are assigned to serving subnets at the node, also referred to as resources. Each resource is a power-of-two integer. The objective of the assignment is to select a set of resources that balances the amount of excess addresses that are not used at the resources with the fragmentation of addresses at the node to too many resources with a discontinuous range of addresses. To achieve this goal, a cost function is assigned to each resource that increases with the subnet size, but exhibits economies-of-scale savings. The maximal number of resources allowed at a node is restricted to a specified parameter. The methods described below find an optimal set of resources at the node. An optimal set implies that there is no other feasible set of resources with a lower combined cost of resources in the set than the set provided by the solution.  
         [0005]     To that end, first a method is developed that provides an optimal solution to a relaxed problem, where all the demands are aggregated to a single demand, while deleting the constraints that each demand is assigned to a single resource. There are two methods that determine an optimal set of resources for the relaxed problem. Then a further method is provided that takes the original demands and assigns each of them to a single resource that is in the solution of the relaxed problem. Again, this latter method takes advantage of the fact that all resources and demands are power-of-two integers. Thus, the optimal set of resources for the relaxed problem and the demand assignments that follow constitute an optimal solution to the original problem where each demand must be assigned to a single resource.  
         [0006]     The methods described above can also be used for allocating new serving subnets to nodes that already have existing serving subnets. Through the repeated application of the methods, it is possible to evaluate the desirability of returning existing subnets to a pool of addresses in order to gain more flexibility in allocating new serving subnets to the node.  
         [0007]     The methods described above can also be used to allocate resources to all nodes in a tree network. Starting at the nodes at the lowest level of the network, a single-node problem is solved for each of the nodes at that level. The resulting resources constitute demands to the nodes at the next level. Then a single-node problem is solved for each node at that level. The process proceeds in this way to solve single-node problems at each level, where the resources from one level become demands for the next level. Each node may also have external demands. The process terminates once the single-node problem at the root node has been solved.  
         [0008]     The present invention will be more clearly understood when the following description is read in conjunction with the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]      FIG. 1  shows the single-node problem, where an optimal set of resources is determined to serve demands.  
         [0010]      FIG. 2  shows the network problem where resources associated with nodes at one level become demands for nodes at a higher level. 
     
    
     DETAILED DESCRIPTION  
       [0011]     Referring now to the figures and to  FIG. 1  in particular, there is shown an example of a single node  101  in an IP communications network. The demands  102 - 106  imposed on the node are subnets or external demands, where each demand comprises a block of IP addresses. Thus, demand  102  is a block of 32 IP addresses, demand  103  is a block of 16 addresses, etc. The size of a demand is always a power-of-two integer (i.e., 1, 2, 4, 8, . . . ). The demands  102 - 106  imposed on the node must be assigned to serving subnets, referred to as resources. In  FIG. 1 , resource  107  is of size 64 and resource  108  is of size 16. A resource must also be of a size that is a power-of-two integer. Each of the demands  102 - 106  must be assigned to a single resource. For example, demands  102 ,  103  and  104  may be assigned to resource  107 , and demands  105  and  106  may be assigned to resource  108 .  
         [0012]     The goal is to determine a set of resources that attempts to balance the volume of excess addresses that are not used with fragmentation of addresses at nodes to too many resources with a discontinuous range of addresses. Current state-of-the-art assignment methods employed by IP communications network planners use ad-hoc methods comprising simple heuristic rules and IP communications network managers&#39; experience. E. G. Coffman, M. R. Garey, and D. S. Johnson present in their paper “Bin Packing with Divisible Item Sizes”,  Journal of Complexity , Volume 3, pages 406-428, 1987 a method for blocks with divisible sizes. Their method is not appropriate for IP address allocations since it does not take advantage of the power-of-two sizes, and would only minimize the volume of excess addresses at the expense of incurring significant fragmentation to too many resources with a discontinuous range of addresses.  
         [0013]     The present method assigns a cost to a resource that while increasing with its size, it exhibits economies-of-scale savings. This means that the cost per address decreases (or, at worst, does not increase) with the resource size. This implies that there will not be employed multiple resources of the same size at a node. Taking advantage that demands and resources are power-of-two integers, methods are provided that find an optimal set of resources at a node. This means that there does not exist any other set of resources whose cost is less than that provided by the present method.  
         [0014]     Now, formulate the model described in  FIG. 1  as follows: 
    k=Index for resources; k=1, 2, . . . , K, where K is the number of available resources of different size (number of addresses).     C k =Size of resource k; C k+1 &gt;C k  for k=1, 2, . . . , K−1. The size of resource k is C k =2 k−1 C for k=1, 2, . . . , K, where C 1 =C (the smallest resource size) is a power-of-two integer.     V k =Cost of resource k; V k+1 &gt;V k  and V k+1 /C k+1 ≦V k /C k  for k=1, 2, . . . , K−1.     N=The maximal number of resources that can be allocated.     r=Index for demands that need to be assigned to resources; r=1, 2, . . . , R, where R is the number of different demands that need to be assigned.     D r =The size of the r-th demand that needs to be assigned; D r+1 ≧D r , r=1, 2, . . . , R, and all demands are power-of-two integers.     D=Sum of all the demands; D=Σ r=1   R D r . The largest resource K is of size C K ≧D while C K−1 &lt;D.     x k =Decision variable, where x k =1 if resource k is allocated to serve demands at the node and x k =0 otherwise.     y rk =Decision variable, where y rk =1 if demand r is assigned to resource k and y rk =0 otherwise.    
 
         [0024]     Examples of cost functions for resources with smaller cost per address when the resource size is larger may include, but are not limited to, V k =A+BC k  or V k =A+Blg(C k ) (A, B&gt;0). Such cost functions are appropriate for IP subnet allocation because they facilitate balancing the cost of allocating too many addresses that are not used at a node versus the cost of allocating too many resources with discontinuous ranges of addresses.  
         [0025]     The resource allocation problem [Problem (1)] is formulated as follows:  
               Minimize     ⁢           ⁢       ∑     k   =   1     K     ⁢           ⁢       V   k     ⁢     x   k     ⁢           ⁢     so  that                 (   1.1   )                     ∑     r   =   1     R     ⁢           ⁢       D   r     ⁢     y   rk         ≤       C   k     ⁢     x   k         ,     k   =   1     ,   2   ,   …   ⁢           ,   K           (   1.2   )                     ∑     k   =   1     K     ⁢           ⁢     y   rk       =   1     ,           ⁢     r   =   1     ,   2   ,   …   ⁢           ,   R           (   1.3   )                     ∑     k   =   1     K     ⁢           ⁢     x   k       ≤   N     ,           (   1.4   )                   x   k     =   0     ,   1   ,           ⁢     k   =   1     ,   2   ,   …   ⁢           ,   K           (   1.5   )                   y   rk     =   0     ,   1   ,           ⁢     r   =   1     ,   2   ,   …   ⁢           ,       R   ⁢           ⁢   and   ⁢           ⁢   k     =   1     ,   2   ,   …   ⁢           ,     K   .             (   1.6   )             
 
         [0026]     Objective function (1.1) minimizes the cost of selected resources. Constraints (1.5) and (1.6) define the decision variables. Constraint (1.2) ensures that demands are assigned only to selected resources and that the demands assigned to any resource k do not exceed the size of resource k. Constraints (1.3) and (1.5) ensure that each of the R demands is assigned to a single resource. Constraint (1.4) ensures that the number of selected resources does not exceed N. Problem (1) can be readily extended by adding a demand whose size is not a power-of-two integer, as long as this demand can be partitioned into pieces which can be assigned to different resources. As will be described later, the solution methods will readily handle this additional case.  
         [0027]     The method will first solve a relaxed version of Problem (1), formulated by aggregating constraints (1.2) and (1.3) to a single constraint. In other words, aggregate all the R demands to a single demand of size D, while deleting the constraints that each demand is assigned to a single resource. Once an optimal solution is found to the relaxed problem [Problem (2)], a method is provided that assigns each of the demands to a single resource from among those determined by the solution to Problem (2), thus providing an optimal solution to Problem (1).  
         [0028]     Problem (2) is formulated as follows:  
               Minimize     ⁢           ⁢       ∑     k   =   1     K     ⁢           ⁢       V   k     ⁢     x   k     ⁢           ⁢     so  that                 (   2.1   )                     ∑     k   =   1     K     ⁢           ⁢       C   k     ⁢     x   x         ≥   D     ,           (   2.2   )                       ∑     k   =   1     K     ⁢           ⁢     x   k       ≤   N     ,     ⁢                   (   2.3   )                         x   k     =   0     ,   1   ,             k   =   1     ,   2   ,   …   ⁢           ,     K   .                   (   2.4   )             
 
         [0029]     Since C K ≧D, Problem (2) has a feasible solution and constraint (2.2) ensures that the sum of selected resource sizes is at least as large as the aggregated demand. Constraint (2.3) ensures that the number of selected resources does not exceed N.  
         [0030]     To find an optimal solution to Problem (1) D is rounded up to an integer multiple of C. It is possible (but not necessary) to normalize the demand and resource sizes to units of C. Hence, hereinafter, assume that D has been rounded up, and all resource capacities C k  and the demand D are expressed in units of C. For example, suppose D 1 =2, D 2 =8, D 3 =16 (R=3) and C=4. Then D=2+8+16=26 and is thus rounded up to 28. Suppose the possible resource sizes are C 1 =4, C 2 =8, C 3 =16, and C 4 =32. Expressing the resource sizes and the demand in units of C, we get C 1 =1, C 2 =2, C 3 =4, and C 4 =8, and D=7.  
         [0031]     Let S n (D) be a set of n resources of different sizes such that the sum of the sizes of these n resources, denoted as C[(S n (D)], satisfies C[(S n (D)]≧D. Let V[(S n (D)] be the sum of costs of the n resources in S n (D).  
         [0032]     A key definition is that S n (D) is an (n, D)-dominating set for demand D if and only if C[(S n (D)]&lt;C[(S′ m (D)] for any set S′ m (D) with m≦n.  
         [0033]     Since any resource can be selected at most once and the resource sizes are power-of-two integers, there is at most one (n, D)-dominating set for any given n. The set S 1 (D)={K} is the (1, D)-dominating set. There exists an optimal solution to Problem (2) that is an (n, D)-dominating sets for some n≦N.  
         [0000]     Method I  
         [0034]     The following is a method for determining an optimal set of resources for Problem (2) [this set of resources is also optimal for Problem (1)]
    Step 1: Initialization. 
        (a) Find the smallest K such that C K ≧D. Specifically, find K that satisfies 2 K−2 &lt;D≦2 K−1 .     (b) Record available resources k=1, 2, . . . , K with sizes C k =2 k−1  for k=1, 2, . . . , K.     (c) Set k 1 =K. Initialize a list, referred to as LIST, of dominating sets with set S 1 (D)={k 1 } (this is the (1, D)-dominating set). Set n=1.    
        Step 2: Find an optimal solution. 
        (a) If n=N or if C[S n (D)]=D for S n (D)∈LIST, compute cost V[S m (D)] for each (m, D)-dominating set S m (D)∈LIST (each m is an index from among 1, 2, . . . , n). Select the minimum cost (m, D)-dominating set as an optimal solution to problem (2). STOP.     (b) If n&lt;N and S n (D)∈LIST, go to Step 3.     (c) If n&lt;N and S n (D)∉LIST, go to Step 4.    
        Step 3: Find the (n+1, D)-dominating set S n+1 (D), given that S n (D)={k 1 , k 2 , . . . , k n }∈LIST. 
        (a) Compute δ=D−[C[S n (D)]−C k     n   +C k     n     −1 ].     (b) Find the smallest resource k′ such that δ≦C k′ &lt;C k     n     −1 . If it exists, add S n+1 (D)={S n (D)−k n +(k n −1)+k′} to LIST.     (c) Update n←n+1 and go to Step 2.    
        Step 4: Find the (n+1, D)-dominating set S n+1 (D), given that the last added set to LIST is S q ={k 1 , k 2 , . . . , k q } for some q&lt;n. 
        (a) Compute δ=D−[C[S q (D)]−C k     q   +C k     q     −1 +C k     q     −2 + . . . +C k     q     −(n−q+1) ]    (b) Find the smallest resource k′ such that δ≦C k′ &lt;C k     q     −(n−q+1) . If it exists, add S n+1 (D)={S q (D)−k q +(k q −1)+ . . . +[(k q −(n−q+1)]+k′} to LIST.     (c) Update n←n+1 and go to Step 2.    
       
 
         [0051]     The method is illustrated through two examples. Suppose D=37 (in units of C) and N=3. The largest resource that needs to be considered is of size 64, thus, K=7. Hence, the resources under consideration are of sizes (in units of C) C 1 =1, C 2 =2, C 3 =4, C 4 =8, C 5 =16, C 6 =32, and C 7 =64. Attempt to find the (n, 37)-dominating sets for n=1, 2 and 3. From Step 1, S 1 (37)={7}, with size C 7 =64, is the (1, 37)-dominating set. From Step 3, δ=37−[64−64+32]=5, implying k′=4 with size C 4 =8. Hence, S 2 (37)={6, 4}, with a combined size of C 6 +C 4 ==+8=40, is the (2, 37)-dominating set. Executing again Step 3, δ=37−[40−8+4]=1, implying k′=1 with size C 1 =1. Hence, S 3 (37)={6, 3, 1}, with a combined size of C 6 +C 3 +C 1 =32+4+1=37, is the (3, 37)-dominating set. Suppose the cost of resource k is V k =4+C k , for all k, where C k  is expressed in units of C. Then, the costs of the (n, 37) dominating sets are: V[S 1 (37)]=4+64=68, V[S 2 (37)]=2*4+40=48, and V[S 3 (37)]=3*4+37=49. Hence, S 2 (37)={6, 4} is optimal for problem (2) with a combined size of 32+8=40 and at a cost of 48.  
         [0052]     Now solve the same example for a demand D=55. Again, S 1 (55)={7} is the (1, 55)-dominating set. However, in the second iteration, from Step 3, δ=55−[64−64+32]=23, and there is no k′ that satisfies 23≦C k′ &lt;32. Thus, a (2, 55)-dominating set does not exist. This can readily be verified as follows. The (2, 55)-dominating set cannot include resource  7  with size 64, and the next two largest resources have a combined size of 32+16=48&lt;55, which is not large enough. Proceed to find the (3, 55)-dominating set and execute Step 4. Since q=1, δ=55−[64−64+32+16]=7, implying that k′=4 with size 8. Hence, S 3 (55)={6, 5, 4}, with a combined size of 32+16+8=56, is the (3, 55)-dominating set. The costs of the dominating sets are: V[S 1 (55)]=4+64=68 and V[S 3 (55)]=3*4+56=68. Hence, both dominating sets are optimal at a cost of 68.  
         [0053]     A second method is provided that solves Problem (2) for all demand values in the range 0&lt;D≦D max , where D max  and the resource sizes are expressed in units of C. Since it is possible to specify a D max  value that is a power-of-two integer, the resources of interest are therefore limited to resources k with sizes 2 k−1  for k=1, 2, . . . , K, where C K =D max . Construct all possible sets of resources, where each set has at most N resources with a combined size that does not exceed D max . Let S(i) be the i-th largest set with combined size C[S(i)]. Obviously, S(1)={K}. Call S(i) the minimal set for demand D in the range C[S(i+1)]&lt;D≦C[S(i)], since S(i) is the set with the smallest combined size that can handle any demand in this range.  
         [0054]     Let the binary vector B(i) be of dimension K. Then, the ordered list of S(i)&#39;s is derived by selecting values of B(i) in decreasing order, where the number of 1&#39;s in B(i) is up to N. Each 1 in B(i) represents a resource, where the left most position represents resource K, the next position represents resource K−1, and so forth. For example, let K=4 and N=2. B(1)=(1000) implies S(1)={4} with size 2 3 =8, B(2)=(0110) implies S(2)={3, 2} with a combined size of 4+2=6, B(3)=(0101) implies S(3)={3, 1} with a combined size of 4+1=5, B(4)=(0100) implies S(4)={3} with size 4, B(S)=(0011) implies S(5)={2, 1} with a combined size of 2+1=3, B(6)=(0010) implies S(6)={2} with size 2, and B(7)=(0001) implies S(7)={1} with size 1. Thus, S(1) is minimal for demand values 7 and 8, S(2) is minimal for demand value 6, and so forth.  
         [0055]     Now, it is possible to compute the cost V[S(i)] of each minimal set. Consider minimal sets S(i) and S(j) for some i&lt;j. If V[S(j)]≧V[S(i)], then S(j) can be deleted from the list since it has a smaller combined size than S(i) and costs at least as much. Once all such S(j) are deleted, each of the remaining sets is optimal for some values of D. Suppose S(i 1 ) and S(i 2 ) are two minimal sets that remain in the ordered list with i 1 &lt;i 2 , while all sets S(i), for i=i 1 +1, . . . , i 2 −1, were deleted. Then, S(i 1 ) is an optimal solution for Problem (2) for all demands in the range C[S(i 2 )]&lt;D≦C[S(i 1 )].  
         [0000]     Method II  
         [0056]     A method for determining optimal sets of resources for Problem (2) for all demand values in the range 0&lt;D≦D max , where D max  is a power-of-two integer [these sets of resources are also optimal for Problem (1)]. 
    Step 1: Initialization. 
        (a) Find K such that C K =2 K−1 =D max .     (b) Record available resources k=1, 2, . . . , K with sizes C k =2 k−1  for k=1, 2, . . . , K.    
        Step 2: Find all minimal sets. 
        (a) Construct an ordered list of all NSETS minimal sets S(i), where S(1)={K}, C[S(i)]&gt;C[S(i+1)] for i=1, 2, . . . , NSETS−1, and the number of resources in a set does not exceed N.     (b) Determine the values of D for which each S(i) is the minimal set. Specifically, if C[S(i)] and C[S(i+1)] are the sizes of sets i and i+1, then S(i) is the minimal set for the D values in the range C[S(i+1)]&lt;D≦C[S(i)]. (Step 2(b) is provided for expository purposes only. It may be omitted.)    
        Step 3: Find optimal solutions. 
        (a) Compute the cost V[S(i)] of minimal set S(i) for each i=1, 2, . . . , NSETS.     (b) Delete any minimal set S(j) with a combined size of C[S(j)] and cost V[S(j)] if there is a minimal set S(i), i&lt;j with cost V[S(i)])≦V[S(j)].     (c) Suppose S(i 1 ) and S(i 2 ) are two sets that remained in the list with i 1 &lt;i 2 , while all sets S(i), for i=i 1 +1, . . . , i 2 −1, were deleted. Then, S(i 1 ) is an optimal solution for Problem (2) in the demand range C[S(i 2 )]&lt;D≦C[S(i 1 )]. Record the values D for which each minimal set that remained on the list is optimal. STOP.    
       
 
         [0067]     Next is an example with D max =32, N=3. The largest resource needed is K=6 with size 32. Assume that the resource costs are V k =3+C k , k=1, 2, . . . , 6 (where C k  is in units of C). For this example, there are 26 minimal sets, where B(1)=(100000) and B(26)=(000001). The results for the largest 8 sets are shown in Table 1.  
                                           TABLE 1                                       Minimal           Optimal       i   B(i)   S(i)   C[S(i)]   for D   V[S(i)]   Delete   for D                   1   (100000)   {6}   32   29-32   35       26-32       2   (011100)   {5, 4, 3}   16 + 8 + 4 = 28   27-28   37   delete       3   (011010)   {5, 4, 2}   16 + 8 + 2 = 26   26   35   delete       4   (011001)   (5, 4, 1}   16 + 8 + 1 = 25   25   34       25       5   (011000)   {5, 4}   16 + 8 = 24   23-24   30       21-24       6   (010110)   {5, 3, 2}   16 + 4 + 2 = 22   22   31   delete       7   (010101)   {5, 3, 1}   16 + 4 + 1 = 21   21   30   delete       8   (010100)   {5, 3}   16 + 4 = 20   20   26       19-20                  
 
         [0068]     The columns i, B(i), S(i), C[S(i)], Minimal for D, and V[S(i)] are self-explanatory. Consider the second row with i=2. It includes the set S(2)={5, 4, 3} which has the largest possible size (C[S(2)]=28) below that of the set S(1)={6} with capacity 32. Thus, S(1) is the minimal set for 28&lt;D≦32. The cost of S(2) is its capacity plus 3×3, namely, 37. All 26 sets are minimal sets, however, due to their cost, some can be deleted. For example, minimal sets S(2) and S(3) are deleted since their costs are at least 35—the cost of minimal set S(1). The last column provides the values of D for which the remaining minimal sets are optimal. For example, set S(1)={6} is optimal for demands  26 - 32  and set S(5)=(5, 4} is optimal for demands  21 - 24 .  
         [0069]     Consider an optimal solution to Problem (2), with M selected resources M≦N. This solution is obtained by using Method I or Method II. Let SUPPLY={k 1 , k 2 , . . . , k M } be the set of the M selected resources (k 1 &gt;k 2 &gt; . . . &gt;k M ) that provides an optimal solution to Problem (2). The sizes of these resources satisfy C k     m   &gt;C k     m+1    for m=1, 2, . . . , M−1. Let DEMAND={1, 2, . . . , R} be the set of demands in Problem (1), where D r+1 ≧D r  for r=1, 2, . . . , R−1. Presented below is Method Assign that assigns each of the demands in DEMAND to a single resource in SUPPLY. Hence, by applying Method Assign to an optimal set SUPPLY for problem (2), there is a feasible and optimal solution to Problem (1).  
         [0000]     Method Assign  
         [0000]     While set DEMAND is not empty,  
         [0000]    
       
         
           
              Select the largest demand in DEMAND, say demand r of size D r .  
              Assign demand r to the resource in SUPPLY, say resource k m , with the least capacity C k     m    such that C k     m   ≧D r .  
              Delete demand r from DEMAND.  
              If C k     m   =D r , delete resource k m  from SUPPLY. If C k     m   &gt;D r , update C k     m   ←C k     m   −D r . 
 
 End. 
 
           
         
       
     
         [0074]     An example of Method Assign is as follows: Suppose the demands are: D 1 =2, D 2 =4, D 3 =8, D 4 =8, D 5 =16, D 6 =16, and D 7 =16, implying D=70, and suppose the solution to problem (2) has SUPPLY={4, 1} with sizes C 4 =64 and C 1 =8. Note that these demand and resource sizes are not translated to units of C=8. Although not done here, it is possible to express all demand and resource sizes in Method Assign in units of D 1 . Method Assign assigns demands as follows: 
        Demand 7 with D 7 =16 is assigned to resource  4  whose size is 64. The resource size is updated to 48.     Demand 6 with D 6 =16 is assigned to resource  4  whose updated size is 48. The resource size is again updated to 32.     Demand 5 with D 5 =16 is assigned to resource  4  whose updated size is 32. The resource size is again updated to 16.     Demand 4 with D 4 =8 is assigned to resource  1  whose size is 8. Resource  1  is deleted.     Demands D 3 =8, D 2 =4, and D 1 =2 are assigned to resource  4 .        
 
         [0080]     Upon termination, resource  1  is fully used and resource  4  has 2 units of excess capacity remaining unused.  
         [0081]     A node may also have an external demand that is not a power-of-two integer, as long as it is allowed to partition this demand into pieces that will be assigned to different resources. Apply Method I (or Method II) to solve Problem 2 where D also includes this external demand. Then, apply Method Assign to assign each of the demands in DEMAND (which does not include this external demand) to a single resource. Once this is completed, partition the remaining external demand to pieces that would fit into the resources.  
         [0000]     Method for Determining Optimal Mix of Existing and New Serving Subnets  
         [0082]     Suppose there are P≦N existing resources. Assign a gain of G p  for returning resource p, p=1, 2, . . . , P to a pool of resources. The gain from returning resource p will typically be smaller than the cost of a new resource of the same size, since it may be difficult to allocate the returned resource to a different node effectively. The gain may even be zero or negative due to expected service disruptions. If P is small, it is possible to enumerate all possible combinations of resource returns and solve Problem (1) for each of these combinations, where the number of new plus unreturned resources is not allowed to exceed N. The existing demands assigned to resources that were returned would then be handled as new demands. Alternatively, it is possible to solve Problem (1) for only some of these combinations at the risk of missing the best one. It may be reasonable to use only P combinations of returns, comprising returning the smallest existing resource, the two smallest existing resources, and so forth, up to all P existing resources. Again, for each of these combinations we solve Problem (1), where the number of existing plus new resources cannot exceed N. Then select the minimum-cost solution from among all those that were solved.  
         [0000]     The Network Problem  
         [0083]     The solutions to single-node problems are used to solve a network problem that has a tree structure like that shown in  FIG. 2 . IP communications networks typically consist of multiple tree networks, interconnected through a backbone network that connects the root nodes of the tree networks.  FIG. 2  depicts an example of a tree network problem, where resources associated with nodes at one level become demands for nodes at the next level. Level 1 includes nodes  201 - 205 . Each of these nodes serves blocks of demands, where each demand block is a power-of-two integer. It may also serve a demand that is not a power-of-two integer as long as that demand can be split and assigned to more than one resource. In the example shown in  FIG. 2 , node  201  serves demands  209 , node  202  serves demands  210 , node  203  serves demands  211 , node  204  serves demands  212 , and node  205  serves demands  213 . Apply at each of these nodes Method I or Method II, followed by Method Assign, to determine an optimal set of resources and to assign the demands to resources. These sets of resources are marked as  217  for node  201 ,  218  for node  202 ,  219  for node  203 ,  220  for node  204 , and  221  for node  205 . Consider now node  206 . Resources  217 ,  218  and  219  that were determined while solving the single-node problems at level 1 become demands to node  206 . Node  206  also may have external demands  214 . Now find an optimal set of resources  222  at node  206 . The optimal set of resources and assignment of demands to resources is again determined by applying Method 1 (or Method 2), followed by Method Assign. Similarly, solve the single-node problem at node  207 . Resources  220  and  221  become demands for node  207 . Node  207  must also serve demands  215 . Now that the two nodes at level 2 are solved, proceed to level 3, which as shown in the example in  FIG. 2  has only node  208 . This node must serve resources  222  and  223 , as well as demands  216 . An optimal set of resources  224  and assignment of demands to resources is determined at node  208  by using again Method 1 (or Method 2), followed by Method Assign.  
         [0084]     While there have been described and illustrated methods for allocating blocks of internet protocol addresses in networks, it will be apparent to those skilled in the art that modifications and variations are possible without deviating from the teachings and broad principles of the present invention which shall be limited solely by the scope of the claims appended hereto.