Allocating identifiers with minimal fragmentation

Patent metadata

Field	Value
Publication number	US-9608930-B1
Application number	US-201113221593-A
Country	US
Kind code	B1
Filing date	Aug 30, 2011
Priority date	Aug 30, 2011
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

Abstract

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.

First claim

What is claimed is:

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.

2. The method of claim 1 , the target block, the first block, and the second block each comprising a Classless Inter-Domain Routing (CIDR) block of IP addresses defined by a lowest IP address and a bit-length prefix, the bit-length prefix specifying the number of leading bits that are common among the IP addresses of the respective CIDR block.

3. The method of claim 1 , further comprising:
receiving a second request to allocate a second IP address to the entity;
determining that the second block is the largest block of a plurality of blocks assigned to the entity; and
allocating a lowest unallocated IP address of the second block to the entity.

4. The method of claim 1 , further comprising:
allocating each IP address of the second block to the entity;
receiving an additional request to allocate an additional IP address to the entity; and
assigning an additional block of unallocated IP addresses to the entity, the additional block comprising at least as many IP addresses as the second block.

5. The method of claim 1 , further comprising:
assigning an additional block of unallocated IP addresses to the entity, the additional block comprising at least as many IP addresses as the second block; and
marking a plurality of IP addresses of the additional block as allocated prior to receiving a request to allocate the plurality of IP addresses.

6. 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 IP addresses comprises at least as many unallocated 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 based of unequal size based at least on the determination that the target block comprises at least as many unallocated 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;
assigning the second block to the entity and allocating a lowest IP address of the second block to the entity;
receiving a request to deallocate an IP address that is allocated to the entity; determining a smallest block of a plurality of blocks assigned to the entity; and
deallocating an IP address of the smallest block.

7. The method of claim 6 , further comprising:
receiving a request to deallocate an IP address that is allocated to the entity;
determining a block that has the least number of allocated IP addresses of a plurality of blocks assigned to the entity; and
deallocating an IP address of the block.

8. The method of claim 6 , further comprising:
determining that a particular IP address allocated to the entity will be deallocated;
notifying the entity that the particular IP address will be deallocated after a predetermined amount of time; and
deallocating the particular IP address after the predetermined amount of time.

9. The method of claim 6 , the data comprising an identifier of a customer of a programmable execution service that provides resizable compute capacity to a plurality of customers.

10. A system comprising:
one or more memory units operable to store a plurality of blocks that each comprise a plurality of contiguous identifiers; and
one or more processing units coupled to the one or more memory units, the one or more memory units including executable instructions that upon execution by the one or more processing units cause the system to:
receive a request to allocate an identifier to an entity, the request comprising data that identifies the entity requesting allocation of the identifier;
determine that a target block of the plurality of blocks of identifiers comprises at least as many contiguous unallocated identifiers as any other block of the plurality of blocks, each block of contiguous identifiers assigned to a respective entity of a plurality of entities, at least one identifier of each block being allocated to the respective entity;
split 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 contiguous unallocated IP addresses as any other block of the plurality of blocks, the contiguous identifiers of the second block each higher than any identifier 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
assign the second block to the entity and allocate a lowest identifier of the second block to the entity.

11. The system of claim 10 , wherein the identifiers are IP addresses.

12. The system of claim 10 , wherein the first block and second block each comprise an equivalent number of identifiers.

13. The system of claim 10 , wherein the size of the second block is selected using a heuristic method.

14. The system of claim 10 , wherein the executable instructions upon execution by the one or more processing units further cause the system to:
receive a second request to allocate a second identifier to the entity;
determine that the second block is the largest block of a plurality of blocks assigned to the entity; and
allocate a lowest unallocated identifier of the second block to the entity.

15. The system of claim 10 , wherein the executable instructions upon execution by the one or more processing units further cause the system to:
allocate each identifier of the second block to the entity;
receive an additional request to allocate an additional identifier to the entity; and
assign an additional block of unallocated identifiers to the entity, the additional block comprising at least as many identifiers as the second block.

16. The system of claim 10 , wherein the executable instructions upon execution by the one or more processing units further cause the system to:
assign an additional block of unallocated identifiers to the entity, the additional block comprising at least as many identifiers as the second block; and
mark a plurality of identifiers of the additional block as allocated prior to receiving a request to allocate the plurality of identifiers.

17. The system of claim 10 , wherein the executable instructions upon exec

Assignees

• Brandwine Eric J
• Amazon Tech Inc

Inventors

• Brandwine Eric J

Classifications

• H04L47/70 Primary

  Admission control; Resource allocation · CPC title

• H04L43/0876

  Network utilisation, e.g. volume of load or congestion level · CPC title

• H04L61/5007 Primary

  Internet protocol [IP] addresses · CPC title

• H04L2101/695

  using masks or ranges of addresses · CPC title

• H04L61/5061

  Pools of addresses · CPC title