Mei Wang Dunn, L. (Cisco Syst.) Wei Mao Tao Chen (China Internet Network Information Center)
Appears in: Computer Communications and Networks, 2007. ICCCN 2007.
Publication Date: 13-16 Aug. 2007
On page(s): 371-376
http://ieeexplore.ieee.org/iel5/4317769/4317770/04317847.pdf

This paper introduce a "new" allocation scheme for address block that is growth-based. It uses growth rate information of customers for optimizing the allocation. An evaluation is made on historical date from APNIC and China.

Authors first explains the existing policies (RIRs ones) and so the size of blocks that should be allocated.
Then it explains the existing allocation algorithms that are used today: sequence (first free slot) and bissection scheme (place the new customer at the middle of the largest free space of address space).

Next, they introduce their "GAP: Growth-based Address Partitioning". In this scheme, each customer is associated with a growth rate value. Based on this, the next slot is allocated at the place that maximize the time before next collision (if all customers observe their growth)

They compare historical data from APNIC and China, between allocation that was really applied and what allocation would be if there was using GAP. They obtain a major fragmentation reduction with GAP in both case (+-90% of reduction). It is not really clear for me what they use as growth rate for the customers. I suspect they use the whole historical data to set the value of the growth rate when a customer is added, if so they use data that was unknown at the "adding moment" and the results are biased. If it is not the case, I suppose (not explained I think) that they fix a default growth value to the customers and that the already-placed-customers can obtain a growth-rate based on their previous growth. Can we really infer a growth-rate from a few month activity ?

I think the major issue of this solution is the estimation of this growth. If this value can be easily and correctly guessed, it is sure that this solution is probably the best one... if no, this solution is not better than the bisection scheme.

I looked at this problem a few month ago when I was design a protocol for automated address allocation and distribution whose some results was published in http://inl.info.ucl.ac.be/publications/secure-mechanism-address-block-al.... However, I made the hypothesis that no growth information (I supposed that this information was too difficult to know in advance) was known from customers and that customers can request any block size. Therefore, I was using a scheme that was a mixed between the sequential and the bisection scheme and that permitted to obtain quite good results for my simulations. My simulations were consisting in randomly removing/adding/enlarging/reducing customers.

An interesting problem... if you know other schemes in publications, please let me know !