Patent Description:
NAT leverages the notion of private IP addresses, such as the ones introduced with Request for Comment <NUM> (RFC1918). Private IP addresses are a small reserved subset of the <NUM>-bit address block (a few tens of millions) and are not publically routable. Accordingly, because private IP addresses need only be unique within a local network, a large organization with thousands of connected devices can operate with a small number of public IP address. NAT utilizes customer premises equipment (CPE) to translate between public and private IP addresses at the edge of the local network for communications occurring between the organization's devices and other Internet connected systems beyond the local network.

The downside with deploying NAT at the customer edge is that its effectiveness is somewhat limited. Firstly, a public IP is still required for connectivity of each distinct, connected network. Accordingly, NAT cannot be used to reduce public IP addresses for isolated devices connected in a point-to-point manner (e.g., mobile phones, industrial sensors in remote locations, etc.). Secondly, while the savings can be significant for large businesses and networks with hundreds of connected devices, the savings are rather small when it comes to home networks or small offices with only a handful of connected devices.

Large Scale NAT (LSN) alleviates the above issues to some extent by allowing carriers and service providers to deploy NAT at the network edge, as oppose to the customer edge. Specifically, using LSN, all connected systems on the customer edge of a service provider, e.g., CPEs, mobile phones, etc., are assigned a private IP address. The private IP address is only translated to a public IP address when it reaches an LSN appliance at the network edge. A dynamic routing protocol advertisement is used so that response traffic to the public IP address can reach the LSN appliance and be reverse-mapped to the appropriate private IP address.

As is the case with all carrier-grade computer systems, LSN appliances are typically deployed in a high-availability, active-standby mode to provide for redundancy in case of a unit's catastrophic failure or scheduled maintenance. In addition, LSN appliances have a well-defined capacity in terms of throughput, new sessions per second, concurrent sessions, etc. As is the case with all computer systems, if capacity is insufficient, (vertical) scale-up or (horizontal) scale-out is needed. Scale-up refers to replacing an appliance with a higher-capacity one, whereas scale-out refers to adding more appliances and operating in an N+<NUM> manner, with multiple active appliances.

While there are inherent benefits of being able to scale-out instead of scaling up, scaling out an LSN system in which more than one LSN appliance is utilized presents unique challenges. In particular, both outbound communications and inbound communications may be received by the set of LSN appliances in an arbitrary manner, i.e., the LSN system has no control over which appliance receives a given flow. For instance, ECMP (equal-cost multi-path routing) may be utilized to forward communications to the LSN system, which from the LSN system perspective, results in a completely arbitrary appliance selection.

Document D1 (<CIT>) describes a method including receiving a request for service in a first edge proxy; applying a hash function to a source address of an endpoint; and forwarding the request to a second edge proxy in response to a first result of the hash function, or servicing the request in the first edge proxy in response to a second result of the hash function <CIT> and <CIT> disclose clusters of NAT devices.

The claimed invention is defined by the independent claims. Embodiments are set out in the dependent claims.

Aspects of this disclosure provide a system, method and program product for implementing a technically enhanced LSN system that manages packet flow among a set of LSN appliances, can be easily scaled out, requires minimal computational and storage overhead, and requires no additional equipment.

The illustrative aspects of the present disclosure are designed to solve the problems herein described and/or other problems not discussed.

Embodiments of the disclosure provide technical solutions for provisioning an enhanced LSN system that includes a set of LSN appliances, each instrumented with smart features to manage network address translation at a network edge. The enhanced LSN system can be easily implemented and scaled out to allow LSN appliances to be added as demand requires. Further, the implementation requires minimal computational overhead, and no additional equipment to manage session tracking.

As noted, challenges arise using a system of LSN appliances because each appliance has a unique set of public IP addresses and sessions must be managed so that outbound requests having private IP addresses can be correlated with associated inbound responses having public IP addresses. If corresponding requests and responses are not handled by the same appliance, managing sessions can become extremely burdensome. <FIG> illustrates this challenge, in which an LSN system <NUM> having four LSN appliances (LSN-<NUM>, LSN-<NUM>, LSN-<NUM> and LSN-<NUM>) attempts to route packets between a wireless router <NUM> and the Internet <NUM>. Outbound communications from a subscriber <NUM> having a private IP address are passed through the wireless router <NUM> to an arbitrarily selected LSN appliance (e.g., using ECMP), which assigns a public IP address and forwards the communication to the Internet <NUM>. As shown, a first outbound communication <NUM> passes through LSN-<NUM> that assigns a first public IP address (Public IP-<NUM>) and a second outbound communication <NUM> passes through LSN-<NUM> that assigns a second public IP address (Pubic IP-<NUM>). Assuming both communications <NUM>, <NUM> are associated with the same session (e.g., a user interacting with a banking website, playing an online game, etc.), issues will arise since the end application will be seeing different public IP addresses.

Similar issues exist for inbound communications, which will likewise be arbitrarily received by any of the LSN appliances. In the example shown, inbound communication <NUM> having public IP-<NUM> is received by LSN-<NUM>, which has no awareness of the existing session set up on LSN-<NUM>.

One approach for managing such an LSN system <NUM> would be to utilize session sharing in which the set of LSN appliances share and track different sessions amongst the group. Unfortunately, sharing sessions amongst LSN appliances is complex and expensive to implement. Another option would be to implement an additional piece of hardware, such as a border router, to ensure that the same LSN appliance is handling correlated inbound and outbound traffic. Public IP address network slicing could be utilized to assign ranges of public IP addresses to each appliance. This approach however not only requires an additional device such as a border router that sits between the LSN system and the Internet to direct inbound communication to the correct LSN appliance, but is also complex to scale when additional appliances are added. For example, scaling an LSN system from four to five LSN appliances requires a complete reworking of the network slices and a respective network redesign.

Referring to <FIG>, an enhanced LSN system <NUM> is shown that includes a set of LSN appliances 20a, 20b, 20c and 20d, each adapted to translate between a relatively large set of private IPv4 addresses and a relatively small set of public IPv4 addresses. In this example, LSN system <NUM> sits between a router <NUM> and the Internet <NUM>. Router <NUM> is for example provisioned by an Internet service provider (ISP) <NUM> that provides Internet access to subscribers <NUM> via homes, businesses, mobile device customers, etc. Each of the subscribers <NUM> are assigned one or more private IP addresses by the ISP <NUM> and are connected to the Internet <NUM> through the ISP's access network. Commercial subscribers may be directly connected to the ISP's access network while noncommercial subscribers are typically behind customer-premises equipment (CPE), such as routers and modems, which may also implement NAT. For the purposes of this disclosure, router <NUM> may comprise any networking device that can forward data packets between computer networks.

Each of the LSN appliances 20a-d are configured to receive subscriber packets having private IP addresses destined for the Internet <NUM> and translate private IP addresses to public IP addresses. Each appliance 20a-d only tracks sessions that it owns and does not track sessions occurring on other appliances in the LSN system <NUM>. Accordingly, each appliance 20a-d maintains a record of all active sessions owned by the appliance and maintains the mappings between subscriber (private) IP address and port, and NAT (public) IP address and port, for each session it owns. The owning appliance can recognize a response packet (received from the Internet <NUM>) belonging to a particular session it owns, can translate from the public IP address to the subscriber private IP address, and can send the translated packet to the subscriber <NUM>. Each LSN appliance 20a-d (e.g., appliance 20a) generally has no knowledge of sessions occurring on other appliances (e.g., appliances 20b-d). Each appliance generally is equipped with a set of LSN features <NUM>, including, e.g., NAT resource allocation for allocating public IP address and ports, IP pooling for managing sessions for subscribers <NUM>, mapping and filtering processes, and application layer gateway support for handling different communication protocols.

In order to implement a system of LSN appliances 20a-d, such as that shown, each appliance further includes a flow processor <NUM>. Flow processor <NUM> enables the management of sessions across the set of appliances 20a-d and allows the LSN system <NUM> to be scaled out to add (or remove) appliances as necessary to meet demand. Flow processor <NUM> generally includes: a hash function <NUM> that determines an owner appliance (from the set of LSN appliances 20a-d) for an outbound request received from a subscriber <NUM> based on the private IP address of the request; a look-up table <NUM> that determines the owner appliance for an inbound response received from the Internet <NUM> based on a public IP address of the response; and a packet routing system <NUM> that forwards a received request or a received response from the receiving appliance to the owner appliance.

Also included is a scale-out system <NUM> that can be utilized to manage a scale-out process in which new appliances are to be added (or removed). In particular, when a new appliance is added, a set of scale-out commands can be received and processed by the scale-out system <NUM> on each appliance to update the hash function <NUM> and/or look-up table <NUM> as needed. Scale-out commands can also be used to reallocate public IP addresses amongst each of the appliances to, e.g., accommodate a new appliance.

<FIG> depicts a cluster traffic distribution according to the invention showing how outbound requests are processed by the enhanced LSN system <NUM> detailed in <FIG>. In the LSN system <NUM> shown, there are four appliances, and each appliance is assigned a range of public IP addresses, i.e., LSN-<NUM> has addresses <NUM>-<NUM>, LSN-<NUM> has address <NUM>-<NUM>, etc. In this case, a subscriber <NUM> initiates a first flow <NUM> which is arbitrarily received by LSN-<NUM>. The hash function <NUM> implemented on LSN-<NUM> determines that the appropriate owner appliance is LSN-<NUM> based on the private IP address of the subscriber <NUM>. The packet routing system <NUM> reroutes the packet to from LSN-<NUM> to LSN-<NUM>, and LSN-<NUM> performs a NAT operation and maps the subscriber's private IP address to a public IP address assigned to LSN-<NUM>, e.g., public-IP-<NUM>. The packet (along with the assigned public IP address) is then forwarded to the Internet <NUM>. Sometime thereafter, the subscriber <NUM> initiates a second flow <NUM> that is arbitrarily received by LSN-<NUM>. The hash function <NUM> implemented on LSN-<NUM> determines that the appropriate owner appliance is LSN-<NUM> for the subscriber's private IP address and the packet routing system forwards the packet to LSN-<NUM>. LSN-<NUM> identifies that there is an existing mapping for the subscriber <NUM> and re-uses public-IP-<NUM>. This process thus ensures that all outbound packets for a given subscriber <NUM> will be routed through a predetermined owner appliance, allowing for subscriber and public IP persistency.

Hashing function <NUM> may utilize any algorithm that can fairly distribute a large number of private IP addresses to a relatively small set of LSN appliances. One possible example includes a modulo operation, which finds the remainder after division of one number (i.e., the private IP address) by another number (i.e., total number of appliances). Thus, for a set of n appliances, the range of outputs is <NUM> to n-<NUM> for all inputted private IP addresses. It is understood that other algorithms could likewise be utilized. Other hashing functions may include, e.g., consistent hashing such as a jump hash, a cache array routing protocol (CARP) hash function, etc..

<FIG> depicts a cluster traffic distribution according to the invention showing how inbound responses from the Internet <NUM> are handled using the look-up table <NUM> installed on each appliance, e.g., as detailed in <FIG>. For simplicity, assume each appliance is assigned only two public IP address, i.e., LSN-<NUM> owns addresses <NUM>,<NUM>; LSN-<NUM> owns <NUM>,<NUM>; LSN-<NUM> owns <NUM>,<NUM>; and LSN-<NUM> owns <NUM>,<NUM>. In this example it can be seen that the outbound communication <NUM> was rerouted through LSN-<NUM> to LSN-<NUM>. At LSN-<NUM>, a NAT session was created and a public IP address was selected (e.g., public IP-<NUM>) for the outbound packet.

For the related inbound communication <NUM>, the packet and its associated public IP address <NUM> is arbitrarily received by LSN-<NUM>. To determine the owner appliance, LSN-<NUM> examines a look-up table <NUM> (<FIG>) that maps appliances to public IP addresses. An illustrative look-up table <NUM> is shown in Table <NUM>, in which it can be seen that public IP-<NUM> is mapped to LSN-<NUM>.

Appliances may be assigned public IP addresses in any manner, e.g., using a hash algorithm that fairly distributes public IP addresses to appliance nodes. Since the number of appliances and public IP addresses is well-known, the look-up table <NUM> can be easily precomputed and stored on each LSN appliance. Using this approach, each appliance processes packets for only the public IP addresses it owns. Table look-ups require only a small amount of computing overhead and the look-up table <NUM> itself requires only a small amount of storage space. For example, assuming four LSN appliances, a /<NUM> public IP subnet (<NUM> IPs) and four bytes per IP address, a modest storage amount of 64KB per appliance is needed (<NUM> entries, with <NUM> bytes for each LSN appliance).

As illustrated in <FIG>, LSN-<NUM> receives the response <NUM> and utilizes the look-up table <NUM> to determine the owner appliance for public IP-<NUM>. As shown in Table <NUM>, it can be seen that LSN-<NUM> is the owner appliance, and packet routing system <NUM> routes the packet from LSN-<NUM> to LSN-<NUM>. LSN-<NUM> processes the packet, recognizes that it belongs to a NAT session, reverse maps the public IP address to the private IP address, and sends the packet to the original subscriber <NUM>. Hence, the precomputed look-up table <NUM> allows for LSN scale-out without any session sharing, stateless load balancing by the wireless router <NUM> or network slicing on the Internet side.

The look-up table <NUM> can be further extended with precomputed hash values for handling a single unit failure, as shown in Table <NUM>. A consistent hash algorithm may be utilized to generate the extended table to ensure that only the failing appliance public IP addresses are redistributed. For example, as shown in Table <NUM>, if LSN-<NUM> fails, public IP addresses <NUM> and <NUM> are redistributed such that LSN-<NUM> owns public IP addresses <NUM>,<NUM>,<NUM>; LSN-<NUM> owns <NUM>,<NUM>,<NUM>; and LSN-<NUM> owns <NUM>,<NUM>. Accordingly, in case of an appliance failure in an N-appliance cluster, only <NUM>/Nth of traffic is affected. Hence only <NUM>% of the traffic is affected in the Table <NUM> example. Moreover, this approach can work without dedicated hot-standby appliances, and with all appliances being active at any given time.

As noted, very little memory is required to implement the look-up table <NUM>. For instance, storing pre-calculated hash values to allow for a single appliance failure extends memory consumption by only 256KB / appliance. Storing pre-calculated hash values to allow for two units to fail extends memory consumption by only 768KB / appliance. Hence, for a <NUM>+<NUM> LSN cluster, the present approach addresses all the deficiencies of LSN scale-out with a mere consumption of 1088KB of memory per appliance.

It can be mathematically shown that assuming N public IP addresses, M appliances and an M+<NUM> redundancy scheme, the per appliance memory impact is calculated as follows: <MAT> Even assuming a somewhat extreme example of /<NUM> public IP address block with a <NUM>+<NUM> LSN scale-out deployment, the total memory impact remains at 1GB, which is modest considering that 1TB on a single server is not uncommon.

Note that 1GB reflects the amount of memory required to store all possible lookup tables, specifically one lookup table for ten active devices, ten lookup tables for nine active devices (since any of the ten devices may fail), forty-five lookup tables for eight active devices (there are forty-five unique device pairs in a ten-device population) and one-hundred-twenty lookup tables for seven active devices (there are one hundred and twenty unique device triplets in a ten-device population). Since at any given moment there is a single lookup table in use, memory utilization can be optimized further. For example, one could load the 10MB "active" lookup table which corresponds to the current cluster state into more efficient memory (i.e. a CPU cache) and the remaining one hundred seventy five lookup tables into slower memory (i.e. RAM).

<FIG> depicts a flow diagram of a process for handling outbound packets by the enhanced LSN system <NUM> (<FIG>). At S1, a packet is received having a private IP address from a router / ISP subscriber at an arbitrarily selected ("receiving") LSN appliance. At S2, a hash function <NUM> is applied to the private IP address at the receiving LSN appliance to determine the owner appliance. At S3, a determination is made whether the owner appliance is different than the receiving appliance. If yes, then the packet is routed to the owner appliance at S4. Once the packet is routed, or if no at S3, a NAT operation is performed at S5 at the owner appliance and the private IP address is mapped to a public IP address. At S6, the packet with the public IP address is forwarded to the Internet.

<FIG> depicts a flow diagram of a process for handling inbound packets by the enhanced LSN system <NUM> (<FIG>). At S11, a packet is received having a public IP address from the Internet <NUM> at an arbitrarily selected ("receiving") LSN appliance. At S12, a table look-up is performed using the public IP address at the receiving LSN appliance to determine the owner appliance. At S13, a determination is made whether the owner appliance is different that the receiving appliance. If yes, then the packet is routed to the owner appliance at S14. Once the packet is routed, or if no at S13, a NAT operation is performed at S15 at the owner appliance and the public IP address is mapped to a private IP address. At S16, the packet with the private IP address is forwarded to a router / ISP subscriber.

The enhanced LSN system <NUM> accordingly overcomes numerous challenges associated with NAT processing at the edge of a network. For example, the present approach eliminates the need for a stateless load balancing layer on the ISP subscriber side; eliminates the need for any sort of network slicing; eliminates any requirement for computationally prohibitive session sharing; eliminates the need for a hot-standby; and minimizes the traffic impact when an appliance fails.

The foregoing drawings show some of the processing associated according to several embodiments of this disclosure. In this regard, each drawing or block within a flow diagram of the drawings represents a process associated with embodiments of the method described. It should also be noted that in some alternative implementations, the acts noted in the drawings or blocks may occur out of the order noted in the figure or, for example, may in fact be executed substantially concurrently or in the reverse order, depending upon the act involved. Also, one of ordinary skill in the art will recognize that additional blocks that describe the processing may be added.

As will be appreciated by one of skill in the art upon reading the following disclosure, various aspects described herein may be embodied as a system, a device, a method or a computer program product (e.g., a non-transitory computer-readable medium having computer executable instruction for performing the noted operations or steps). Accordingly, those aspects may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, such aspects may take the form of a computer program product stored by one or more computer-readable storage media having computer-readable program code, or instructions, embodied in or on the storage media. Any suitable computer readable storage media may be utilized, including hard disks, CD-ROMs, optical storage devices, magnetic storage devices, and/or any combination thereof.

The flow processor <NUM> and scale-out system <NUM> (<FIG>) may be implemented by any type of computing system that for example includes at least one processor, memory, an input/output (I/O), e.g., one or more I/O interfaces and/or devices, and a communications pathway or bus. In general, the processor(s) execute program code which is at least partially fixed in memory. While executing program code, the processor(s) can process data, which can result in reading and/or writing transformed data from/to memory and/or I/O for further processing. The pathway provides a communications link between each of the components in the computing device. I/O can comprise one or more human I/O devices, which enable a user to interact with the computing device and the computing device may also be implemented in a distributed manner such that different components reside in different physical locations. Flow processor <NUM> and scale-out system <NUM> may likewise be implemented either fully or partially in firmware or dedicated hardware, in which functionality is implemented using embedded processing.

LSN system <NUM> may be implemented in any network environment in which devices (i.e., subscribers) having assigned private IP addresses communicate with a TCP/IP network, such as the Internet, using public IP addresses. The LSN system <NUM> may for example be used to access a cloud computing environment that employs a network of remote, hosted servers to manage, store and/or process data, and may generally be referred to, or fall under the umbrella of, a "network service. " The cloud computing environment may include a network of interconnected nodes, and provide a number of services, for example hosting deployment of customer-provided software, hosting deployment of provider-supported software, and/or providing infrastructure. In general, cloud computing environments are typically owned and operated by a third-party organization providing cloud services (e.g., Amazon Web Services, Microsoft Azure, etc.), while on-premises computing environments are typically owned and operated by the organization that is using the computing environment. Cloud computing environments may have a variety of deployment types. For example, a cloud computing environment may be a public cloud where the cloud infrastructure is made available to the general public or particular sub-group. Alternatively, a cloud computing environment may be a private cloud where the cloud infrastructure is operated solely for a single customer or organization or for a limited community of organizations having shared concerns (e.g., security and/or compliance limitations, policy, and/or mission). A cloud computing environment may also be implemented as a combination of two or more cloud environments, at least one being a private cloud environment and at least one being a public cloud environment. Further, the various cloud computing environment deployment types may be combined with one or more on-premises computing environments in a hybrid configuration.

Claim 1:
A system for processing packets between a router (<NUM>,<NUM>) and a transmission control protocol/Internet protocol (TCP/IP) network, comprising:
a plurality of large scale network address translation (LSN) appliances (20a-20d);
wherein a first LSN appliance arbitrarily selected from the plurality of LSN appliances is configured to:
receive a request from the router (<NUM>,<NUM>), wherein the request includes a private IP address;
apply a hash function (<NUM>) to the private IP address to determine an owner appliance from the plurality of LSN appliances (20a-20d), and route the request to the owner appliance;
wherein the owner appliance is configured to forward the request to the TCP/IP network using a public IP address associated with the owner appliance, wherein the owner appliance creates a session that translates between the public IP address and the private IP address;
wherein a second LSN appliance arbitrarily selected from the plurality of LSN appliances (20a-20d) is configured to:
receive a response from the TCP/IP network, wherein the response includes the public IP address;
examine a look-up table (<NUM>) to determine the owner appliance based on the public IP address;
route the response to the owner appliance;
wherein the owner appliance is configured to forward the response along with the private IP address to the router (<NUM>,<NUM>).