Allocating identifiers with minimal fragmentation

摘要

In certain embodiments, a system includes one or more memory units and one or more processing units. The memory units store blocks that each include a number of identifiers. The memory units include executable instructions that upon execution by the processing units cause the system to receive a request to allocate an identifier to an entity. The request includes data identifying the entity. A target block of identifiers is identified. The target block includes more unallocated identifiers than any other block. The target block is split into first and second blocks. The identifiers of the second block are each higher than any identifier of the first block. The second block is assigned to the entity, and a lowest identifier of the second block is allocated to the entity.

主权项

1. A computer-implemented method comprising:
receiving a request to allocate an Internet Protocol (IP) address, the request comprising data that identifies an entity requesting allocation of the IP address; determining, by one or more processing units, that a target block of a plurality of blocks of contiguous IP addresses comprises at least as many unallocated contiguous IP addresses as any other block of the plurality of blocks; splitting, by the one or more processing units, the target block into a first block and a second block of unequal size based at least on the determination that the target block comprises at least as many unallocated contiguous IP addresses as any other block of the plurality of blocks, the IP addresses of the second block each higher than any IP address of the first block, respective sizes of the first block and the second block being determined based at least in part on one or more parameters; and assigning the second block to the entity and allocating a lowest IP address of the second block to the entity.