Distributed IP allocation and de-allocation mechanism in a communications network having a distributed S/PGW architecture

Patent metadata

Field	Value
Publication number	US-10171417-B2
Application number	US-201415517876-A
Country	US
Kind code	B2
Filing date	Oct 7, 2014
Priority date	Oct 7, 2014
Publication date	Jan 1, 2019
Grant date	Jan 1, 2019

Abstract

A non-transitory computer readable medium has instructions stored therein to be executed by a packet processing unit (PPU) in a communications network to allow a plurality of PPUs in the communications network to independently allocate IP addresses from a shared pool of IP addresses. The plurality of PPUs collectively maintain a distributed hash table (DHT). The DHT stores a distributed block allocation table (DBAT) and a plurality of distributed address allocation tables (DAATs). The DBAT includes an entry for each of a plurality of blocks of IP addresses to indicate which of the plurality of blocks are allocated to which of the plurality of PPUs. Each of the plurality of DAATs corresponds to one of the blocks in the DBAT and includes an entry for each of the IP addresses in that block to indicate which of the IP addresses in that block are allocated to which user entities.

First claim

The invention claimed is:

1. A non-transitory computer readable medium having stored therein instructions to be executed by a packet processing unit (PPU) in a communications network to allow a plurality of PPUs in the communications network to independently allocate IP addresses from a shared pool of IP addresses, the instructions when executed by the PPU cause the PPU to perform a set of operations comprising:
receiving, by the PPU, a request to allocate an IP address to a user entity (UE), wherein the plurality of PPUs in the communications network collectively maintain a distributed hash table (DHT), the DHT stores a distributed block allocation table (DBAT) and a plurality of distributed address allocation tables (DAATs), wherein the DBAT includes an entry for each of a plurality of blocks of IP addresses to indicate which of the plurality of blocks of IP addresses are allocated to which of the plurality of PPUs, and wherein each of the plurality of DAATs corresponds to one of the blocks identified in the DBAT and includes an entry for each of the IP addresses in that one block to indicate which of the IP addresses in that one block are allocated to which UEs;
choosing, from a first block of IP addresses currently allocated to the PPU, one of the IP addresses in the first block that a locally cached version of the DAAT corresponding to the first block indicates as being available;
looking up, using a DHT algorithm, which of the plurality of PPUs is responsible for storing the DAAT entry in the DHT for the chosen IP address;
causing the PPU responsible for storing the DAAT entry in the DHT for the chosen IP address to update that DAAT entry to indicate that the chosen IP address is allocated to the UE;
updating the locally cached version of the DAAT corresponding to the first block to indicate that the chosen IP address is allocated to the UE;
allocating the chosen IP address to the UE;
determining, by the PPU, that the PPU needs another of the blocks of IP addresses to be allocated to it;
choosing one of the blocks of IP addresses that a locally cached version of the DBAT indicates as being available;
looking up, using the DHT algorithm, which of the plurality of PPUs is responsible for storing the DBAT entry in the DHT for the chosen block;
causing the PPU responsible for storing the DBAT entry in the DHT for the chosen block to update that DBAT entry to indicate that the chosen block is allocated to the PPU;
updating the locally cached version of the DBAT to indicate that the chosen block is allocated to the PPU;
causing the others of the plurality of the PPUs to update their respective locally cached version of the DBAT to indicate that the chosen block is allocated to the PPU; and
creating a locally cached version of the DAAT corresponding to the chosen block.

2. The non-transitory computer readable medium of claim 1 , wherein the causing the PPU responsible for storing the DAAT entry in the DHT for the chosen IP address to update that DAAT entry comprises:
transmitting a request, to the PPU responsible for storing the DAAT entry in the DHT for the chosen IP address, to update that DAAT entry to indicate that the chosen IP address is allocated to the UE; and
receiving a reply, from the PPU responsible for storing the DAAT entry in the DHT for the chosen IP address, that indicates whether the update of that DAAT entry was successful.

3. The non-transitory computer readable medium of claim 1 , wherein the instructions when executed by the PPU cause the PPU to perform a further set of operations comprising:
receiving a request to de-allocate a first IP address that is currently allocated to a first UE being served by the PPU, wherein the first IP address is included in a second block of IP addresses;
looking up, using the DHT algorithm, which of the plurality of PPUs is responsible for storing the DAAT entry in the DHT for the first IP address;
causing the PPU responsible for storing the DAAT entry in the DHT for the first IP address to update that DAAT entry to indicate that the first IP address is available;
looking up, using the DHT algorithm, which of the plurality of PPUs is responsible for storing a DBAT entry in the DHT for the second block of IP addresses;
accessing, from the PPU responsible for storing the DBAT entry in the DHT for the second block of IP addresses, the one of the plurality of PPUs that is currently allocated that block; and
notifying the PPU that is currently allocated the second block that the first IP address is to be de-allocated.

4. The non-transitory computer readable medium of claim 1 , wherein the causing the PPU responsible for storing the DBAT entry in the DHT for the chosen block to update that DBAT entry comprises:
transmitting a request, to the PPU responsible for storing the DBAT entry in the DHT for the chosen block, to update that DBAT entry to indicate that the chosen block is allocated to the PPU; and
receiving a reply, from the PPU responsible for storing the DBAT entry in the DHT for the chosen block, that indicates whether the update of that DBAT entry was successful.

5. The non-transitory computer readable medium of claim 1 , wherein the instructions when executed by the PPU cause the PPU to perform a further set of operations comprising:
determining, for each of the IP addresses in the chosen block, whether that IP address is available based on queries to those of the DAAT entries in the DHT for the IP addresses in the chosen block; and
updating the locally cached version of the DAAT corresponding to the chosen block based on results of the queries to indicate which of the IP addresses in the chosen block are available.

6. The non-transitory computer readable medium of claim 1 , wherein the causing the others of the plurality of PPUs to update their respective locally cached version of the DBAT is performed using an epidemic protocol or a gossip protocol.

7. The non-transitory computer readable medium of claim 1 , wherein the locally cached version of the DBAT is stored as a bit vector where one or more indices of the bit vector corresponds to block indices and a bit value indicates whether the block is available or not.

8. The non-transitory computer readable medium of claim 1 , wherein the instructions when executed by the PPU cause the PPU to perform a further set of operations comprising:
receiving, by the PPU, a request to update the DBAT entry in the DHT for a particular one of the blocks to indicate that the particular block is allocated to a requesting one of the PPUs, wherein the receiving PPU is responsible for storing that DBAT entry;
updating the DBAT entry in the DHT for the particular block to indicate that the particular block is allocated to the requesting PPU;
starting a release timer for the particular block; and
transmitting a reply to the requesting PPU that indicates the updating of the DBAT entry in the DHT for the particular block was successful.

9. The non-transitory computer readable medium of claim 8 , wherein the instructions when executed by the PPU cause the PPU to perform a further set of operations comprising:
resetting the release timer for the particular block in response to receiving a keep-alive message for the particular block.

10. The non-transitory computer readable medium of claim 8 , wherein the instructions when executed by the PPU cause the PPU to perform a further set of operations comprising:
updating the DBAT entry in the DHT for the particular block to indicate that the particular block is available when the release timer expires;
updating the locally cached version of the DBAT to indicate that the particular block is available; and
causing the others of the plurality of PPUs to u

Assignees

• Ericsson Telefon Ab L M

Inventors

• Synnergren Per
• Kristiansson Johan

Classifications

• H04L69/40

  for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection (management of faults, events, alarms or notifications in data switching networks H04L41/06) · CPC title

• G06F12/00

  Accessing, addressing or allocating within memory systems or architectures (digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06) · CPC title

• H04L45/7453

  using hashing · CPC title

• H04W8/26

  Network addressing or numbering for mobility support · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title