Distributed network address allocation management

Patent metadata

Field	Value
Publication number	US-11575647-B1
Application number	US-202117535023-A
Country	US
Kind code	B1
Filing date	Nov 24, 2021
Priority date	Nov 24, 2021
Publication date	Feb 7, 2023
Grant date	Feb 7, 2023

Abstract

Disclosed are various embodiments for distributed network address allocation management. In one embodiment, a first instance of a plurality of instances of an allocation management service assigns a first portion of a network address space to the first instance and a second portion of the network address space to a second instance of the plurality of instances. The second instance receives a request to allocate a particular network address block. The second instance allocates the particular network address block from the second portion of the network address space by updating an allocation data structure. An allocation of the particular network address block is returned in response to the request. A copy of the allocation data structure maintained by the first instance is updated asynchronously based at least in part on the allocation of the particular network address block.

First claim

Therefore, the following is claimed:

1. A system, comprising:
a cloud provider network divided into at least a first subdivision and a second subdivision that are configured to fail independently of each other;
at least one first computing device in the first subdivision and implementing a first allocation management service;
at least one second computing device in the second subdivision and implementing a second allocation management service;
the at least one first computing device configured to at least:
assign a first portion of a network address space to the first allocation management service;
assign a second portion of the network address space to the second allocation management service, the first and second portions being non-overlapping; and
generate one or more allocations of network address blocks from the first portion of the network address space to requestors in the first subdivision; and

the at least one second computing device configured to at least:
generate one or more allocations of network address blocks from the second portion of the network address space to requestors in the second subdivision; and
asynchronously send a snapshot of an allocation data structure including the one or more allocations of network address blocks from the second portion of the network address space to the first allocation management service.

2. The system of claim 1 , wherein the allocation data structure corresponds to a prefix allocation tree comprising:
a plurality of nodes individually representing a respective network address block having a first prefix length divisible by a value, at least one of the plurality of nodes further representing a plurality of child network address blocks having respective second prefix lengths greater than or equal to the first prefix length but less than a next multiple of the value above the first prefix length, the at least one of the plurality of nodes includes at least one reference to a child node of the plurality of nodes having a third prefix length being a next multiple of the value above the first prefix length.

3. The system of claim 1 , wherein the allocation data structure comprises an attribute index that indexes one or more respective attributes associated with respective network address blocks, at least one of the one or more respective attributes corresponding to an attribute indicating whether a corresponding network address block is free to be allocated.

4. The system of claim 1 , wherein the at least one second computing device is further configured to at least:
release an allocation of a particular network address block by updating the allocation data structure, the snapshot indicating that the allocation has been released.

5. The system of claim 1 , wherein the snapshot of the allocation data structure is sent to the first allocation management service at a predictable rate.

6. The system of claim 1 , wherein the first allocation management service is configured to ignore a previous snapshot from the second allocation management service that has not been processed in response to a more recent snapshot from the second allocation management service being received.

7. A computer-implemented method, comprising:
assigning, by a first instance of a plurality of instances of an allocation management service, a first portion of a network address space to the first instance and a second portion of the network address space to a second instance of the plurality of instances;
receiving, by the second instance, a request to allocate a particular network address block;
allocating, by the second instance, the particular network address block from the second portion of the network address space by updating an allocation data structure;
returning an allocation of the particular network address block in response to the request; and
asynchronously updating a copy of the allocation data structure maintained by the first instance based at least in part on the allocation of the particular network address block by;
periodically generating, by the second instance, a snapshot of the allocation data structure; and
sending, by the second instance, the snapshot to the first instance at a predictable rate.

8. The computer-implemented method of claim 7 , further comprising:
assigning, by the second instance, a subportion of the second portion of the network address space to a third instance of the plurality of instances;
receiving, by the third instance, a request to allocate another particular network address block;
allocating, by the third instance, the other particular network address block from the subportion of the second portion of the network address space by updating the allocation data structure;
returning an allocation of the other particular network address block in response to the request; and
asynchronously updating another copy of the allocation data structure maintained by the second instance based at least in part on the allocation of the other particular network address block.

9. The computer-implemented method of claim 7 , wherein assigning, by the first instance, the first portion of the network address space to the first instance and the second portion of the network address space to the second instance further comprises asynchronously updating, by the first instance, the first portion of the network address space assigned to the first instance and the second portion of the network address space assigned to the second instance.

10. The computer-implemented method of claim 7 , wherein assigning, by the first instance, the first portion of the network address space to the first instance and the second portion of the network address space to the second instance further comprises using, by the first instance, at least one atomic compare-and-swap operation to update a transaction state.

11. The computer-implemented method of claim 7 , wherein sending, by the second instance, the snapshot to the first instance at the predictable rate further comprises generating one or more files from the snapshot that are padded to a fixed data size.

12. The computer-implemented method of claim 7 , further comprising automatically determining, by the first instance, a size of the second portion of the network address space based at least in part on an estimated demand for network addresses in a portion of a network that includes the second instance.

13. The computer-implemented method of claim 7 , wherein allocating, by the second instance, the particular network address block from the second portion of the network address space by updating the allocation data structure is performed irrespective of an operational status of the first instance.

14. The computer-implemented method of claim 7 , wherein the allocation data structure comprises a prefix allocation tree, the first portion of the network address space corresponds to a first top-level node in the prefix allocation tree, and the second portion of the network address space corresponds to a second top-level node in the prefix allocation tree.

15. The computer-implemented method of claim 7 , wherein the first instance and the second instance are in at least one of: different regions of a network, different availability zones of the network, or different data centers of the network.

16. A computer-implemented method, comprising:
receiving, by a first instance of a plurality of instances of an allocation management service, a request to allocate a particular network address block;
allocating, by the first instance, the particular network address block from a first portion of a network address sp

Assignees

• Amazon Tech Inc

Inventors

• Rubin-Smith Eric Andrew
• Das Shovan Kumar
• Kramer Jonathan Paul
• Untereiner Michael Erik
• Karimi Masood
• Schlachtenhaufen John Jeffrey
• Gupta Arushi
• Lough Samuel

Classifications

• H04L2101/604

  Address structures or formats · CPC title

• H04L61/5007 Primary

  Internet protocol [IP] addresses · CPC title

• H04L61/2514

  between local and global IP addresses · CPC title

• H04L61/5061

  Pools of addresses · CPC title

• H04L61/5046

  Resolving address allocation conflicts; Testing of addresses (testing when self-assigning an address H04L61/5092) · CPC title