ALLOCATING IDENTIFIERS WITH MINIMAL FRAGMENTATION

• US 20170195283A1
• Filed: 03/22/2017
• Published: 07/06/2017
• Est. Priority Date: 08/30/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brandwine, Eric J.
• Granted Patent: US 10,237,233 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 2101/65 Telephone numbers
• CPC Class Codes: H04L 2101/695 using masks or ranges of addresses
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 61/5007 Internet protocol [IP] addresses
• CPC Class Codes: H04L 61/5061 Pools of addresses

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.

Claims

1. A computer-implemented method, comprising:

receiving a request to allocate an Internet Protocol (IP) address for an entity;

processing a plurality of blocks of IP addresses to determine a target block having at least as many unallocated IP addresses as any other block of the plurality of blocks;

processing, based at least in part on information with the entity, the target block to generate a first block and a second block, the first block comprising a first subset of the IP addresses of the target block, the second block comprising a second subset of the IP addresses, the second subset comprising a non-empty remainder of the IP addresses of the target block, the numerically lowest IP address of the second block being higher than the numerically highest IP address of the first block; and

allocating the second block to the entity.

2. The computer-implemented method of claim 1, wherein the first block is allocated to a different entity to which the target block was previously allocated.

3. The computer-implemented 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 computer-implemented method of claim 1, wherein processing the target block further comprises using a heuristic method that analyzes the information to determine a size of the first block or the second block

5. The computer-implemented method of claim 1, wherein the information is based on a usage history of the entity.

6. A system comprising:

one or more processors; and

memory that stores executable instructions that, when executed by the one or more processors, cause the one or more processors to at least;

generate, for at least a first entity requesting allocation of a network identifier, a target block of network identifiers from a plurality of blocks of network identifiers, the target block having at least as many unallocated network identifiers as any other block of the plurality of blocks;

determine a first block and a second block from the target block by at least;

determining, based on information associated with the first entity, a size for the second block;

processing the target block to generate the second block of the size, a lowest network identifier of the second block having a value higher than a lowest network identifier of the target blocks; and

allocating a remainder of the network identifiers of the target block outside of the second block to the first block; and

associate the second block with the first entity.

7. The system of claim 6, wherein the network identifiers are IP addresses.

8. The system of claim 6, wherein the first block and second block are equal in size.

9. The system of claim 6, wherein the executable instructions that, when executed, cause the one or more processors to determine the size for the second block, further cause the one or more processors to use a heuristic method to determine the size for the second block.

10. The system of claim 9, wherein the information includes a network identifier usage for the first entity.

11. The system of claim 9, wherein the information includes a quantity of network identifiers available for allocation by the system.

12. The system of claim 9, wherein the information is provided by the first entity as part of a request for the allocation.

13. The system of claim 6, wherein the executable instructions further cause the one or more processors to allocate the first block to a second entity to which at least a portion of the target block was allocated prior to a request by the first entity to allocate the network identifier.

14. One or more non-transitory computer-readable media that stores executable instructions which, when executed by one or more processors of a computer system, cause the computer system to:

receive a request to allocate a block of network identifiers to an entity;

select, based at least in part on information for the request, a target block from a plurality of blocks, the target block including at least as many unallocated network identifiers as any other block of the plurality of blocks;

determine, based at least in part on the information, a size for the second block;

generate, from the target block, the block having the determined size, a highest network identifier of the block having a value equal to a highest network identifier of the target block;

allocate the block to the entity; and

allocate at least some of a reminder of the target block outside of the block allocated to the entity to a different entity

15. The one or more non-transitory computer-readable media of claim 14, wherein the request is received from the entity.

16. The one or more non-transitory computer-readable media of claim 14, wherein the request is associated with a different request to allocate a network identifier of the block to the entity.

17. The one or more non-transitory computer-readable media of claim 14, wherein the entity includes a computing resource hosted by a programmable execution service using the one or more processors.

18. The one or more non-transitory computer-readable media of claim 14, wherein the information includes historical access data for the entity.

19. The one or more non-transitory computer-readable media of claim 14, wherein the executable instructions, when executed, further cause the computer system to determine the size using a heuristic method.

20. The one or more non-transitory computer-readable media of claim 14, wherein the request is received via an application programming interface (API) provided by the computer system.