LMB: Towards Sufficient Utilization of Address and Port Resource against IPv4 Exhaustion

摘要

The crisis of IPv4 address exhaustion is driving the ISPs to allocate address resources in a granularity finer than per address. A+P was proposed as a basic strategy which allocates one address to multiple users with non-overlapped port ranges. However, as an essential challenge to the application of A+P, the resource allocation model has never been explored. The feature of variable resource granularity in A+P causes serious uncertainty in both resource utilization sufficiency and runtime efficiency. This paper formulates the problem into a resource utilization problem, and proposes a novel algorithm called LMB (Layered Merging and Bisection). LMB views the space as a collection of transformable port range units which are flexible for merging and bisection. Based on their granularity, LMB organizes these units into different lists which are adaptable to allocation and recycling. The two basic operations require only O(log n) time, yet LMB guarantees to find one of the smallest units for each allocation and keep the space neat. Evaluations show that LMB can utilize 80-90% of the space when processing random demand sequence. Moreover, the paper enhances LMB into Time-Intellective LMB algorithm, which further leverages the knowledge of recycling time to accurately choose among the candidate units found by LMB during an allocation. It can pick the one with the best timing match in consideration of both local and higher-layer merging. TI-LMB keeps the space even neater than LMB and utilizes the space even more sufficiently.