Hybrid and efficient method to sync NAT sessions

The method of synchronizes network address translation (NAT) records between an active gateway and a standby gateway. The method of some embodiments synchronizes NAT records of long-term data flows more frequently than those of short-term flows. Multiple data flows pass between a device at an internal source address and a device at an external destination address through the active NAT gateway. For each flow, the method generates a NAT record. The method then determines whether the data flow is a short-term flow or a long-term flow and synchronizes the NAT records of the long-term flows, but not the NAT records of the short-term flows, with the standby gateway. The method of some embodiments synchronizing NAT records more frequently when NAT records are being generated quickly relative to prior generation rates and less frequently when NAT records are being generated slowly relative to the prior generation rates.

BACKGROUND

In the field of network computing, the machines and devices in datacenters generally connect to external networks such as the Internet through gateways using IP addresses assigned to the datacenter. However, datacenters tend to have a larger number of devices and machines (physical and virtual) than they have assigned IP addresses. To address this mismatch, datacenters use network address translation (NAT) devices on the gateways of the datacenter. The NAT devices associate the internal source IP and internal source port addresses of connections from devices and machines in the datacenter to the available external source IP and external source port addresses assigned to the datacenter. The NAT devices maintain records of these associations and use the records to determine the appropriate external source IP/port address to apply to data packets sent out by a particular internal source IP/port address and vice versa for incoming data packets.

The NAT devices and gateways are vulnerable to failure (crashing, freezing, etc.). When the NAT device of an active gateway (or the gateway itself) fails without a standby device for backup, all of the existing associations are lost, disrupting any ongoing flows of data between the machines and devices of the datacenter and the external network. Accordingly, datacenters generally include multiple gateways, such as an active gateway and a standby gateway ready to handle any data flows should the active gateway or its NAT device fail. The standby NATs can only supply address translations for records that are synchronized to the records of the active gateway. Prior art active NATs send full copies of all NAT records to the standby NATs. However, this uses up bandwidth within the datacenter that could be used for other data. Accordingly, there is a need in the art for more efficient methods of synchronizing NAT sessions.

BRIEF SUMMARY

The inventions herein implement multiple different methods for increasing the efficiency of NAT record synchronization. These methods fall into three general categories. First, the amount of information can be reduced by sending the NAT records in an encoded form that requires fewer bits and bytes than the full NAT records. Second, the NAT records can be synchronized selectively, with the NAT records of longer-term data flows (sometimes called “elephant flows”) synchronized more frequently and NAT records of shorter-term data flows (sometimes called “mouse flows”) synchronized less frequently, or in some embodiments not synchronized at all. Third, the NAT records can be synchronized at intervals that adapt to how quickly new NAT records are being generated by the NAT device. Various embodiments may use methods that take advantage of any one, any two, or all three of these categories of methods.

In the category of sending encoded NAT records, the method of some embodiments, synchronizes NAT records between an active gateway and a standby gateway. The active gateway encodes a NAT record that includes at least an external source IP address. The encoded NAT record does not include the external source IP address but does include an identifier that uniquely specifies the external source IP address. The active gateway sends the encoded NAT record to the standby gateway.

In some embodiments, the NAT record includes an internal source IP address. The encoded NAT record does not include the internal source IP address but does include a subnet identifier and a host identifier. The combination of the subnet identifier and the host identifier uniquely specifies the internal source IP address. The internal source IP address may include a subnet prefix and the host identifier, where the subnet identifier is not the subnet prefix, but does uniquely specify the subnet prefix. In some cases, in embodiments that use an IP4 protocol, the subnet prefix includes three leading octets of the internal source IP address and the host identifier includes the ending octet of the internal source IP address. In other cases, the subnet prefix includes two leading octets of the internal source IP address and the host identifier includes two ending octets of the internal source IP address. Some embodiments use other addressing schemes than IP4 protocols. For example, some embodiments use an IP6 protocol. Such embodiments may use a subnet prefix with other numbers of octets, for example, two to five octets with a host identifier of one to four octets.

In some embodiments, the NAT record includes an external destination IP address and external destination port address and the encoded NAT record includes an identifier that does not include the external destination IP address and/or external destination port address, but does uniquely specify a combination of the external destination IP address and external destination port address. The encoded NAT records in embodiments that include such an identifier in a first NAT record may include additional encoded NAT records. In some such embodiments, the identifier that uniquely specifies the combination of the external destination IP address and external destination port address is stored at a particular offset within the first encoded NAT record. However, in a second NAT record, there is a pre-defined identifier at the particular offset, where the pre-defined identifier indicates that a full external destination IP address and full external destination port address of the second NAT record is included in the second encoded NAT record.

The method of some embodiments, before sending the encoded NAT record, stores, at the standby gateway, a set of decoding data that associates each of a set of multiple identifiers that uniquely specify an external source address with the external source address that the identifier specifies. The decoding data may be stored after at least one of (1) receiving decoding data from the active gateway, (2) determining decoding data from a set of configuration data applied to both the active gateway and the standby gateway, and (3) negotiating decoding data between the standby gateway and the active gateway.

In the category of synchronizing NAT records selectively, there are some NAT records that are more important than others. Generally, the loss of a NAT record representing a given long-term data flow results in more damage than the loss of a NAT record representing a given short-term flow. Additionally, waiting longer between synchronizations of short-term flows may result in those short-term flows ending and the NAT record being deleted before it ever needs to be sent to the standby NAT, reducing the number of NAT records to be synchronized.

Accordingly, the method of some embodiments synchronizes NAT records of long-term data flows more frequently than those of short-term flows. More specifically, the method of some embodiments synchronizes network address translation (NAT) records between an active gateway and a standby gateway. Multiple data flows pass between a device at an internal source IP address and a device at an external destination address through the active NAT gateway. For each flow, the method generates a NAT record. The method then determines whether the data flow is a short-term flow or a long-term flow and synchronizes the NAT records of the long-term flows, but not the NAT records of the short-term flows, with the standby gateway.

In some embodiments, determining whether a particular data flow is a short-term flow or a long-term flow includes identifying a data type of the data flow and comparing the data type to a set of identifiers of each of a set of multiple data types as indicating a short-term flow or a long-term flow. The data type may include at least one of a video file, a video call, an HTML file, an audio file, an audio call, and a data file.

In some embodiments, the method determines whether a particular data flow is a short-term flow or a long-term flow by receiving a soft termination of the data flow and inspecting an application layer of at least one packet of the data flow. In some embodiments, determining whether a particular data flow is a short-term flow or a long-term flow includes identifying a packet size of packets of the flow. In some embodiments, the method determines whether a particular data flow is a short-term flow or a long-term flow by identifying an incoming request for data and determining an amount of data requested by the incoming request. The data flow is a TCP flow in some embodiments.

The method of some embodiments may perform multiple synchronizations of NAT records, where performing the multiple synchronizations of NAT records includes synchronizing the NAT records of the long-term flows more frequently and synchronizing the NAT records of the short-term flows less frequently.

In the category of synchronizing the NAT records at intervals that adapt to how quickly new NAT records are being generated by the NAT device, in some embodiments, the method of synchronizing NAT records between an active gateway and a standby gateway synchronizes the NAT records more frequently when the NAT records are being generated quickly relative to prior generation rates and less frequently when NAT records are being generated slowly relative to the prior generation rates.

More specifically, the method of some embodiments for synchronizing NAT records between an active gateway and a standby gateway iteratively performs multiple steps. The method waits a set interval, then synchronizes a set of NAT records generated since an immediately prior synchronization, then adjusts the interval. Adjusting the interval may include comparing a first number of NAT records synchronized in the immediately prior synchronization to a second number of NAT records synchronized in a current synchronization. Adjusting the interval may include increasing the interval when the first number is greater than the second number by a first particular amount and/or decreasing the interval when the first number is less than the second number by a second particular amount. In some cases, the first particular amount is calculated based on at least one of the first and second numbers and the second particular amount is calculated based on at least one of the first and second numbers. In some embodiments, the interval is bounded to remain between an upper bound and a lower bound.

DETAILED DESCRIPTION

The inventions herein implement multiple different methods for increasing the efficiency of NAT record synchronization. These methods fall into three general categories. First, the amount of information can be reduced by sending the NAT records in an encoded form that requires fewer bits and bytes than the full NAT records. Second, the NAT records can be synchronized selectively, with the NAT records of longer-term data flows (sometimes called “elephant flows”) synchronized more frequently and NAT records of shorter-term data flows (sometimes called “mouse flows”) synchronized less frequently or in some embodiments not synchronized at all. Third, the NAT records can be synchronized at intervals that adapt to how quickly new NAT records are being generated by the NAT device. Various embodiments may use methods that take advantage of any one, any two, or all three of these categories of methods.

The inventions described herein are operated in an environment of a datacenter or other individual local network with multiple machines or devices in the local network that connect to an external network through a relatively small (compared to the number of machines or devices of the datacenter) number of external IP addresses. These external IP addresses of the datacenter are called “external source IP addresses” herein in order to distinguish them from the IP addresses on the external network to which the machines and devices of the datacenter are connecting, which are called “external destination addresses” herein.

Due to the relatively small number of external source IP addresses, it is not possible to simply assign each machine or device of the datacenter an external source IP address of its own. However, each machine or device of the datacenter can be assigned an internal source IP address of its own. Each internal source IP address has a large number (e.g., 65,536) of port addresses associated with it as does each external source IP address.

Generally, each machine or device of a datacenter uses at most a relatively small number of the ports of its assigned IP address at any time. Accordingly, it is possible to pair each internal source IP address and port address combination with an external source IP address and port address combination. This pairing uses the many ports of each external source IP address to compensate for the small number of external source IP addresses. This pairing is done by a NAT device that receives outgoing packets from the machines of the network and converts their internal source IP and port addresses to the paired external source IP and port addresses and vice versa for return packets from the machines or devices at the external destination port addresses to the machines or devices on the network.

Connections between machines on networks are generally bidirectional and often involve repeated instances of communication between the same machines. Accordingly, the NAT device will consistently translate each particular pair of internal source addresses to the same corresponding pair of external source addresses. In order to translate consistently, the NAT device keeps records of the translation information for each data flow. A data flow is a set of data packets sent between two machines or devices in which each packet has the same source and destination IP and port addresses and protocol (with the source and destination addresses switched for reply packets) for each packet in the flow.

Using these records to consistently translate the addresses, the NAT device allows the machines and devices in the datacenter to communicate seamlessly with machines and devices of the external network. However, the NAT devices are subject to failures such as crashes, freezes, loss of power to the hardware implementing the NAT device, etc. If the NAT records are lost, the connections between the internal and external machines are broken. The connections can be replaced with new connections, but any data sent using the previous addresses after the NAT device fails will be lost. For some types of applications, establishing a new connection is not an inconvenience. For example, if a user of one machine is simply browsing web pages stored on the other machine, losing the connection may not even be noticed as the next click of a hyperlink establishes a new connection that provides the same information as the previous connection would have. However, if a user is engaged in a video call, the call may be interrupted. If a user is downloading a large file, the download may have to be restarted entirely, wasting the time and bandwidth already spent before the connection was lost.

To avoid the inconvenient loss of connections, datacenters use standby NAT devices to take over in the event that an active NAT device fails. In order to maintain an original connection, the standby NAT device requires the NAT record of that connection. Therefore active NAT devices synchronize their NAT records with the standby NAT devices. As described in the following sections, the methods herein provide a more efficient way of synchronizing some or all of the NAT records of an active NAT device with a standby NAT device. Section A describes methods of sending NAT records in an encoded format that reduces the size of each record, Section B describes methods of synchronizing NAT records selectively, prioritizing long-term data flows such as video calls or file downloads over short-term data flows such as HTML, requests, and Section C describes methods of adaptively synchronizing NAT records, more frequently when many records are being generated and less frequently when few records are being generated.

A. Sending Encoded NAT Records

The methods of some embodiments synchronize NAT records between an active gateway and a standby gateway. The active gateway encodes a NAT record that includes various types of data, such as data identifying (for a particular connection) the external source IP and port addresses, the internal source IP and port addresses, the external destination IP and port address, and the protocol. The methods of this section encode the NAT records of an active NAT device to reduce the amount of data that needs to be sent for each record in order for the standby NAT device to synchronize its NAT records with those of the active NAT device.

FIG. 1illustrates a NAT device using a datacenter gateway system with active and standby gateways.FIG. 1includes a datacenter100, with host machines102A and102B, executing machines105A-105B and105C, respectively, active gateway115, standby gateway135, and an external network170(e.g., the Internet).FIG. 2conceptually illustrates a process200of synchronizing stored NAT records of some embodiments.FIG. 2will be described in relation to the relevant elements ofFIG. 1.

As shown inFIG. 1, in some embodiments, host machines102A and102B in the datacenter may execute one or more machines105A-105C. These machines may be virtual machines, pods, containers, other virtual devices, and/or other software or hardware that is assigned one or more IP addresses within the datacenter. The machines105A-105C implement programs (e.g., web browsers, file downloading programs, streaming video programs, etc.) which may require contact with other machines and devices on the external network170. Each internal machine105A-105C has an internal IP address within the datacenter100, and when a machine (e.g., machine105A) requires a connection to a machine on the external network170, the machine105A sends the data out of the datacenter100through the active gateway115.

The active gateway115includes a NAT device120, an encoder125, and a NAT record storage130. As shown inFIG. 2the process200begins when the active gateway generates (at205) NAT records to translate between an internal source address (i.e., the IP address of a machine within the datacenter) and an external source address. InFIG. 1, the NAT device120(sometimes called a “NAT” herein) is a software implemented module or device that generates NAT records (not shown) in order to translate the internal network address of the machine105A to an external addresses used by the external network170. The external source address is used as a source address, on the external network170, for packets of a data flow between the machine105A and a machine on the external network170. To facilitate this translation, each time the NAT120receives a packet of a new data flow (i.e., a data flow with no existing NAT record) between an internal machine of the datacenter100and the external network170, the NAT120generates a new NAT record. The types of data stored in a NAT record are further described with respect toFIG. 3, below.

The NAT120of the active gateway115stores the NAT records in the NAT record storage130. In some embodiments, the NAT record storage130is an independent data recording medium specific to the active gateway115. In other embodiments, the NAT record storage130is a memory space in a larger memory system accessible by the NAT120.

The process200ofFIG. 2, encodes (at215) the NAT records at the active gateway (e.g., gateway115ofFIG. 1). The stored records are encoded to reduce their size before they are sent to the standby gateway135. The encoder125accesses the NAT record storage130to retrieve stored NAT records for conversion into an encoded format. The process200ofFIG. 2then sends (at220) the encoded NAT records to the standby router for the standby router to decode with previously provided decoding data. InFIG. 1, the encoded NAT records160are sent by the NAT120to a NAT140of the standby gateway135.

Various embodiments generate the decoding data in different ways. In some embodiments, the active NAT (or gateway) provides decoding data to the standby NAT (or gateway). In other embodiments, both the active and standby gateways are provided with configuration data from another machine or device of the datacenter, and the active and standby gateways (e.g., at the NATs of each gateway) each generate encoding/decoding data from the configuration data. In some embodiments, some encoding/decoding data is generated from configuration data while other encoding/decoding data is provided from the active gateway. In some embodiments, some or all of the encoding/decoding data is generated at least partly through negotiation between the active and standby gateways or the active and standby NATs. The decoding data of some embodiments is further described with respect toFIGS. 5A-5D, below.

The standby gateway includes the NAT140, a decoder145, and NAT record storage150. In the configuration illustrated inFIG. 1, the NAT140is in a standby mode, receiving encoded NAT records160from NAT120of the active gateway115, and in some cases other relevant data such as decoding data. While in standby mode, the standby gateway135of some embodiments does not handle outgoing or incoming connections unless and until the active gateway115ceases to function (e.g., crashing, freezing, hardware error, connection to the rest of the data network severed etc.). Accordingly, the NAT140does not provide any network address translation in standby mode. However, in standby mode, the NAT140does operate to receive the encoded NAT records160from the active NAT120. The NAT140passes these encoded records160to the decoder145which decodes the records160using the decoding data previously mentioned. Once decoded, the NAT records160are stored in the NAT record storage150.

Although the active gateway115is shown as having an encoder125while the standby gateway135is shown as having a decoder145, one of ordinary skill in the art will understand that in some embodiments, the active gateway115and the standby gateway135are provided by equivalent hardware or are provided by programs running on equivalent hardware with the active and standby roles being arbitrarily assigned. In such embodiments, each gateway115and135includes hardware and/or software for both an encoder125and a decoder145. In some embodiments, the same hardware and/or software may provide both encoding and decoding operations.

FIG. 3illustrates the data structure of NAT records300of some embodiments. As described with respect toFIG. 1, the NAT120generates NAT records and stores those NAT records in the NAT record storage130. NAT record300includes an external source IP address302, an external source port address304, an external destination IP address306, an external destination port308, an internal source IP address310, an internal source port312, and a protocol value314. The combination of the external source IP address302and external source port address304are used as a source IP and port addresses of packets sent out on the external network from the gateway of the datacenter for a particular data flow associated with the NAT record300. The external destination IP address306and external destination port308are the destination IP and port addresses of the packets of the particular data flow. The internal source IP address310and internal source port312are the IP and port addresses within the datacenter of the machine or device that is the source of the data flow. The protocol value314identifies the protocol used by the packets (e.g., TCP, UDP, etc.).

For a particular datacenter, several of the values for multiple records will be redundant and therefore encoding them can reduce the overall data necessary to supply the relevant information to a standby NAT of a standby gateway.FIG. 4illustrates unencoded and encoded NAT record types and examples.FIG. 4will be described with occasional references toFIGS. 5A-5D.FIGS. 5A-5Dillustrate examples of NAT synchronization record decoding/encoding data.

Although the unencoded external source IP addresses302in a NAT record use 4 bytes (32 bits) in the IP4 protocol, each NAT will only have access to a limited number of external source IP addresses (e.g., under 32, under 64, under 100, etc.). In the example of this figure, the NAT is capable of using to up to 64 external source IP addresses. The entire 4 byte IP address is necessary to provide a source address for a packet being sent out on the external network. However, the NAT records will only contain (at most) 64 different external source IP addresses. With only 64 possible external source IP addresses, each can be uniquely identified with a 6 bit number (2{circumflex over ( )}6=64 unique identifiers) giving encoding/decoding data for each external source IP address. For example, the unencoded external source IP address of unencoded NAT record410(202.2.3.4) which requires 4 bytes to express is represented in the encoded NAT record by a binary number (bin:000000), the unencoded external source IP address of unencoded NAT record414(208.24.1.5) is represented in the encoded NAT record by another binary number (bin:000001), etc.

In order to determine which external source IP addresses are identified by each binary number, the NAT uses decoding/encoding data, such as the data shown in external source IP table500inFIG. 5A. In table500, each external source IP address used by the NAT has an associated binary number. Accordingly, if both an encoder of an active NAT and a decoder of a standby NAT have access to the data in table500, then the encoder of the active NAT can encode any external source IP of the NAT using the associated 6 bit number, saving a total of 26 bits of data in each encoded record compared to each unencoded record. The decoder of the standby NAT can then use the decoding/encoding data to identify the external source IP of the original NAT record when decoding the encoded NAT record.

InFIG. 4, the external destination IP address and port in each unencoded record410,414, and418take up a total of 6 bytes. The gateways of datacenters are capable of addressing a packet to any IP address and port on the external network. This means that a comprehensive encoding solution that always reduces the size of the IP/port address is not possible for reasons that would be clear to one of ordinary skill in the art. However, during actual operations of a datacenter, there will often be some external destination port/IP addresses that are contacted in more than one flow (e.g., addresses at a popular retail site, a popular video site, etc.). Therefore, the encoding/decoding method of some embodiments maintains data associating the more commonly used IP/port addresses with a unique identifier. In this example, the identifier is a single byte (allowing 256 unique identifiers).FIG. 5Billustrates an external destination IP/port table510with various external destination IP address and port address combinations associated with a particular number (e.g., a 1 byte number). In the illustrated embodiment, the table510includes an entry associated with the number 255 without a specific IP or port address. This entry represents an escape code of some embodiments that notifies the encoder and decoder that the external destination IP and port combination of the record is not one of the common addresses stored in the encoding/decoding record and that therefore the entire 6 bytes of the combined IP and port address are included in the encoded NAT record. In some embodiments, the additional 6 bytes are appended to the end of an encoded record, while in other embodiments, the additional 6 bytes are placed somewhere within the encoded data record, such as immediately after the escape code. The escape code in some embodiments is designated as some number other than 255.

Many datacenters have IP addresses for the internal machines and devices of the datacenter organized in subnets. Although each machine (e.g., host machine or VM on a host machine) has its own assigned 4 byte IP address, these IP addresses are not assigned arbitrarily. Instead, the machines are each assigned to a subnet with, for example, the first 3 bytes (sometimes called the first three “octets” as each byte is a set of 8 bits) in the IP address being the same for every computer in the subnet and the last octet of the IP address identifying a particular machine or device within the subnet. InFIG. 4, the internal source IP addresses310of unencoded NAT records410and414are on the same subnet as each other, specifically a subnet on which all IP addresses begin with 128.1.1. The internal source IP address310of unencoded NAT record418is on a different subnet from the other two, a subnet on which all IP addresses begin with 128.1.3, represented in the encoded record420by the number 2. The NAT encoding method of some embodiments encodes internal IP addresses by using a unique identifier for the subnet and including the last octet that identifies the machine or device within the subnet. Here, the internal source IP address 128.1.1.43 of unencoded record410has been replaced in encoded record412, by two bytes, one representing the subnet 128.1.1 and one representing the specific machine43.FIG. 5Cillustrates an internal subnet table520with subnet 128.1.1 associated with the number 1 for encoding/decoding purposes and subnet 128.1.3 associated with the number 2 for encoding/decoding purposes.

The illustrated examples use an IP4 protocol with the subnets represented by the first three octets of the IP address, with the specific machine within the subnet being represented by the last octet (allowing up to 256 machines/devices per subnet). However, in some embodiments, the subnets are represented by the first two octets of the IP address while the particular machine/device within the subnet is represented by the last two octets (allowing up to 65,536 machines/devices per subnet). In such embodiments, the encoded NAT record provides a one byte identifier for the subnet and a two byte identifier for the particular machine within the subnet. In embodiments that use an IP6 protocol, the subnet prefix may be from two to five octets, with the specific machine within the subnet being represented by from one to four octets. In such embodiments, even though a larger number of octets in the subnet prefix allows for a wider potential range of subnet numbers, as long as the total number of subnets actually in use by the datacenter remains at or below 256, all of the subnets can be identified in the encoded NAT records by one byte of data. One of ordinary skill in the art will understand the minimum number of bits and/or bytes would be necessary to uniquely identify a particular number of subnets in a set of encoded NAT records.

InFIG. 4, the protocol of the data flow (e.g., TCP or UDP) is represented in the unencoded records410,414, and418by one byte. However, most data sent via IP is either in a TCP or UDP format. In embodiments in which the gateway uses only those two protocols, or only any two specific protocols, the protocol of a data packet can be uniquely identified with a 1 digit binary number (1 bit). The encoded records412,416, and420each provide one bit to identify the protocol.FIG. 5Dillustrates a data table530that associates each protocol with a 1 bit number.

As shown inFIG. 4, in addition to the data from the original NAT records, the encoder of some embodiments includes an add/delete value402. The add/delete value is an extra byte of data appended to the record to indicate whether the encoded NAT record (once sent to the standby NAT and decoded) should be added to the NAT record tracking storage of the standby NAT or whether it represents a record, that is already in that storage, that should be deleted. Add or delete is a binary choice, therefore in the encoded NAT record one bit is used to indicate whether to add or delete the record. InFIG. 4, the command to add the record is represented by a binary number 0 and the command to delete the record is represented by the binary number 1. In some embodiments, the 6 bit identifier of the external source IP address is concatenated with the 1 bit identifier of the protocol and the 1 bit add/delete value to form a single byte in the encoded NAT record.

The above described encoding/decoding methods use specific numbers of bits or bytes for specific data, reducing the number of bytes in an unencoded NAT record from 20 bytes (including the add/delete value) to 8-9 bytes. However, one of ordinary skill in the art will understand that other amounts of encoded data may be used by other embodiments while remaining in the scope of the inventions described herein. For example, in some embodiments, the data table of most common external destination IP address port combinations has up to 65,536 entries (including an escape code in some embodiments), and the encoded IP/port combination is represented by two bytes. In the illustrated embodiments, the external source port addresses304and the internal source port addresses312are left in their original form rather than being encoded. However, in some embodiments restrictions on the available port values to use enable encoding to reduce the amount of data needed to uniquely identify the port addresses in the encoded NAT records.

B. Synchronizing NAT Records Selectively

As mentioned above, there are some NAT records that are more important than others. Generally, the loss of a NAT record representing a given long-term flow results in more damage, in terms of time and equipment resources to recover the connection, than the loss of a NAT record representing a given short-term flow. For some types of applications, establishing a new connection is not an inconvenience or is only a minor inconvenience. For example, if a user of one machine connected to a second machine through a NAT is simply browsing simple web pages stored on the second machine, losing the connection may not even be noticed as the user's next click of a hyperlink establishes a new connection that provides the same response from the second machine as the previous connection would have. However, if a user is engaged in a video meeting call, the call may be interrupted, requiring time to re-establish and possibly inconveniencing multiple parties in the meeting. If a user is downloading a large file, the download may have to be restarted entirely, wasting the time and bandwidth already spent before the connection was lost.

In addition to it generally being less of an inconvenience to lose a connection of a short-term flow, waiting longer between synchronizations of short-term flows may result in some of those short-term flows ending and their NAT records being deleted before they are synchronized, thus reducing the number of records to be sent when a synchronization of short-term flows does occur. Accordingly, the methods of some embodiments synchronize NAT records of long-term flows more frequently than those of short-term flows. The method of some embodiments synchronize NAT records between an active gateway and a standby gateway. This synchronization method of this invention may be performed in conjunction with the previously described encoding method or may be performed without such an encoding method.

As previously described, in the NAT enabled datacenter of the present invention, multiple data flows pass between a device at an internal source IP address and a device at an external destination address through the active NAT gateway. For each flow, the method generates a NAT record. The method then determines whether the data flow is a short-term flow or a long-term flow and synchronizes the NAT records of the long-term flows, but not the NAT records of the short-term flows, with the standby gateway.

FIG. 6conceptually illustrates a process600of some embodiments for synchronizing NAT records of long-term flows but not short-term flows. The process600receives (at605), at an active gateway, a packet of a new data flow between an internal device (or machine) and an external device (or machine). The process600generates (at610) a NAT record for the data flow. In some embodiments, the NAT record includes the data types shown inFIG. 3. The process600, ofFIG. 6, determines (at615) whether the data flow is a long-term flow. If the data flow is a long-term flow, the process600designates (at620) the NAT record as a long-term flow for the purposes of synchronizing. In some embodiments, designating the NAT record as a long-term flow record comprises appending an identifier to the NAT record before storing it. In other embodiments, the designation may comprise using a different storage or a different area of the storage than the NAT records for short-term flows. Further details about how the methods of various embodiments determine whether a data flow is a short-term flow or a long-term flow are described with respect toFIGS. 8-10below.

The process600then determines (at625) whether it is time to synchronize the records. If it is not time to synchronize the records, the process600returns to operation605to receive a packet of another new data flow. If it is time to synchronize the records, the process600synchronizes (at630) the long-term flow NAT records. AlthoughFIG. 6shows the determination to perform the record synchronization as being a single operation that occurs a few operations after receiving a new data flow, one of ordinary skill will understand that in some embodiments, the determination of when to synchronize the records depends on a timer which may trigger a synchronization without waiting for a new flow to be received.

Although the methods of some embodiments synchronize only the NAT records of long-term flows, the methods of other embodiments may perform synchronizations of NAT records of both long-term and short-term flows. The methods of some embodiments perform the synchronizations of NAT records of the long-term flows more frequently and perform the synchronizations of the NAT records of the short-term flows less frequently.FIG. 7conceptually illustrates a process700for synchronizing NAT records of long-term flows more frequently than those of short-term flows.

The process700receives (at705), at an active gateway, a packet of a new data flow between an internal device (or machine) and an external device (or machine). The process700generates (at710) a NAT record for the data flow. In some embodiments, the NAT record includes the data types shown inFIG. 3. The process700, ofFIG. 7, determines (at715) whether the data flow is a long-term flow. If the data flow is a long-term flow, the process700designates (at720) the NAT record as a long-term flow for the purposes of synchronizing. If the data flow is a short-term flow, the process700designates (at725) the NAT record as a short-term flow for the purposes of synchronizing.

The process700then determines (at730) whether it is time to synchronize the long-term flow NAT records. If it is not time to synchronize the long-term flow NAT records, the process700returns to operation705to receive a packet of another new data flow. If it is time to synchronize the long-term flow NAT records, the process700synchronizes (at735) the long-term flow NAT records. The process700then determines (at740) whether it is time synchronize the short-term flow NAT records. If it is not time to synchronize the short-term flow NAT records, the process700returns to operation705to receive a packet of another new data flow. If it is time to synchronize the short-term flow NAT records, the process700synchronizes (at745) the short-term flow NAT records, and then returns to operation705.

Although the embodiment ofFIG. 7shows a process700in which the determination of whether to synchronize short-term flows (of operation740) is only made after each synchronization of long-term flows (of operation735) in other embodiments, the determination of when to synchronize records may be made based on independent timers without any specific relationship between how often short-term flow NAT records and long-term flow NAT records are made.

FIGS. 8-10illustrate various systems for determining whether a particular data flow is a short-term flow or a long-term flow. These methods are used in some embodiments to identify elephant flows in order to synchronize the NAT records of those elephant flows more frequently and synchronize mouse flows less frequently (or not at all in some embodiments).FIG. 8illustrates an active gateway815of some embodiments with a deep packet inspector830. The active gateway815includes a NAT820which provides a set of one or more data packets825of a new flow to the deep packet inspector (DPI)830. In some embodiments, the gateway815halts the data flow while the DPI830inspects the packets, while in other embodiments, the NAT820provides copies of packets in a data flow to the DPI830, and the DPI830inspects the copies while the original packet flow continues.

The DPI830determines whether the data flow of the packets is a long-term flow (elephant flow) or a short-term flow (mouse flow). The DPI830of some embodiments identifies a flow as an elephant flow or a mouse flow by examining the application layer (L7) parameter of a packet of the data flow. The DPI830then compares the L7 parameter with a list of L7 parameters associated with either long-term flows or short-term flows to determine whether that flow is a long-term or short-term flow. For example, if the L7 parameter indicates a file transfer service such as FTP, the DPI830may identify the data flow as a long-term flow. In contrast, if the L7 parameter indicates an HTTP request, the DPI830may identify the data flow as a short-term flow. More generally, determining whether a particular data flow is a short-term data flow or a long-term data flow may include identifying a data type of the data flow and comparing the data type to a pre-determined set of identifiers of multiple data types as indicating a short-term data flow or a long-term data flow (e.g., from a table or database associating each data type with either long-term or short-term flows). The data type may include at least one of a video file, a video call, an HTML file, an audio file, an audio call, and a data file.

In some embodiments, an agent on a host machine determines whether a data flow is an elephant flow or a mouse flow.FIG. 9illustrates a host machine905with an elephant flow detector915. The host machine implements a virtual machine910. The virtual machine910sends data packets925to the active gateway (not shown). The packets925are intercepted on the host905by the elephant flow detector915which identifies the packet as an elephant flow or mouse flow (e.g., in a similar process to the process performed by the DPI830ofFIG. 8) and notifies the NAT of the active gateway of the determination (e.g., by sending additional data with a packet, as metadata, or separately that identifies the flow). The NAT of the active gateway then uses this additional data to classify the new data flow as an elephant flow or a mouse flow.

FIG. 10illustrates a host machine1005with a VM1010and an elephant flow module1020. The VM1010implements a guest introspection (GI) module1015to identify any flows to be sent out of the VM as elephant or mouse flows (e.g., in a process similar to the process performed by the DPI830ofFIG. 8) before they are sent out. The GI module1015ofFIG. 10then passes data identifying the flow and the determination of the flow as a mouse flow or an elephant flow to the elephant flow module1020on the host1005. The elephant flow module1020then sends this data to the active gateway (not shown) where the NAT uses the data to determine whether a particular flow is an elephant flow or a mouse flow (e.g., in order to back up NAT records of the elephant flows more frequently and NAT records of mouse flows less frequently or not at all).

Other embodiments may use other methods of determining whether a data flow is a long-term flow (elephant flow) or a short-term flow (mouse flow). In some embodiments, determining whether a particular data flow is a short-term data flow or a long-term data flow includes identifying a packet size of packets of the flow. In some embodiments, the method determines whether a particular data flow is a short-term data flow or a long-term data flow by identifying an incoming request for data and determining an amount of data requested by the incoming request.

C. Adaptive Synchronizing of NAT Records

Sending data to synchronize NAT records costs not only the time for sending and receiving the actual data, but also overhead in the form of start-up and shut down time for every component involved in the data transfer, regardless of how large or how small the data transfer is. Additionally, new NAT connections are not generated at a constant rate. The same length of time may include a large number of NAT records generated, or just a few. In order to determine efficient times to send synchronization data, the methods of some embodiments synchronize the NAT records according to an adaptive schedule.

Such embodiments synchronize NAT records at intervals that adapt to how quickly new NAT records are being generated by the NAT device. In some embodiments the method of synchronizing NAT records between an active gateway and a standby gateway synchronizes the NAT records more frequently when NAT records are being generated quickly relative to prior generation rates and less frequently when NAT records are being generated slowly relative to the prior generation rates. These embodiments can be used in conjunction with any of the other methods described herein, but can also be used independently of any other methods described herein.

FIG. 11conceptually illustrates a process1100of some embodiments for adaptively synchronizing records. First, the process1105synchronizes NAT records (e.g., NAT records generated since the last synchronization, if any). The process1100then compares (at1110) the current number of NAT records synchronized (during operation1105) with the number of NAT records synchronized in an immediately previous iteration (if any) of the process1100.

The process1100determines (at1115) whether the current number of NAT records synchronized (during operation1105) is greater than the number of NAT records synchronized (also during operation1105) during the immediately previous iteration of the process1100. For example, the threshold could be 1 NAT record. That is, the condition could be met as long as the current number of NAT records is greater than the previous number of NAT records. In other embodiments, the threshold could be other fixed values (e.g., 2, 5, 10, etc.) or the threshold could be proportional to the previous number or the current number (e.g., the condition could be met if the current number is larger than the previous number by at least 50%).

If the current number is larger by at least the threshold, then the process1100reduces (at1120) an interval setting of an interval to wait before performing the next synchronization operation. For example, the process1100may reduce the interval by one second in some embodiments. In some embodiments, the interval setting has a minimum level below which it cannot be reduced. Such embodiments may determine whether the interval is already at this level as a precondition for reducing the interval, or they may reduce the interval, determine that it is below the minimum and increase the interval back to the minimum level.

The process1100then stores (at1135) the current number of NAT records synchronized for reference in operation1110in the next iteration of the process1100. The process1100then waits (at1140) for the set interval to pass before starting the next iteration of the process1100by synchronizing (at1105) again.

If the process1100does not determine (at1115) that the number of NAT records synchronized in the present iteration is greater than in the previous iteration by the threshold amount, then the process1100determines (at1125) whether the current number of NAT records synchronized is less than the previous number by at least a threshold. If the number is less than the previous number by at least the threshold, then the process1100increases (at1130) the interval setting. The interval of some embodiments has a set maximum that is enforced in a similar manner to the set minimum interval discussed with respect to operation1120. Just as in iterations in which the interval was increased, the process1100then stores (at1135) the current number of NAT records before waiting (at1140) to start the next iteration of the process1100. If the process1100determines at1125that the current number of records synchronized is not less than the previous number by at least the threshold, then the process does not change the interval before proceeding to operation1135.

In some embodiments, the threshold for the determination of operation1115is the same as the threshold for the determination at1125. In other embodiments, the threshold for the determination of operation1115is different from the threshold for the determination at1125. For example, in some embodiments, the threshold is 1 for the determination at1115and the threshold is half of the previous number of synched records for the determination at1125. In such an embodiment, the interval would decrease whenever the number of records in an interval was greater than in the previous interval, and the interval would increase when the number of records in an interval dropped below half the number in the previous interval.

In some embodiments, rather than adjusting the interval based solely on a comparison between the number of NAT records sent in the current iteration and the previous iteration, the method adjusts the interval based on comparisons with older iterations. For example, in some embodiments, the method tracks the high and low values of the number of NAT records sent in some or all previous iterations to compare against the number of NAT records sent in the current iteration. Some embodiments track statistical data such as the average and/or standard deviation of numbers of NAT records sent in multiple iterations to compare with the number of NAT records sent in the current iteration in order to determine whether and how to adjust the interval. Some embodiments may determine whether to change the interval based on a comparison between the number of NAT records sent in the current iteration and the number of NAT records sent in the iteration in which the interval was last changed.

Although much of the above description focused on NATs that use an IP4 for network addresses, one of ordinary skill in the art will understand that in some embodiments the NATs use other addressing systems. For example, some embodiments use an IP6 network addressing protocol with six octets defining an unencoded network address. In some such embodiments, a datacenter uses subnets defined by any of two, three, four, or five octets with an identifier of specific machines in a subnet using the remaining four, three, two, or one octets, respectively.

The description of the above embodiments included connections between machines (e.g., virtual machines, pods, and/or containers) executing on host machines of a datacenter and machines on an external network. However, one of ordinary skill in the art will understand that the datacenters of some embodiments may include individual hardware machines that are also assigned IP addresses within the datacenter. The NATs of some embodiments also translate the IP addresses of such hardware machines and include such IP addresses in NAT records.

FIG. 12conceptually illustrates an electronic system1200with which some embodiments of the invention are implemented. The electronic system1200can be used to execute any of the control, virtualization, or operating system applications described above. The electronic system1200may be a computer (e.g., a desktop computer, personal computer, tablet computer, server computer, mainframe, a blade computer etc.), phone, PDA, or any other sort of electronic device. Such an electronic system includes various types of computer-readable media and interfaces for various other types of computer-readable media. Electronic system1200includes a bus1205, processing unit(s)1210, a system memory1225, a read-only memory1230, a permanent storage device1235, input devices1240, and output devices1245.

The bus1205collectively represents all system, peripheral, and chipset buses that communicatively connect the numerous internal devices of the electronic system1200. For instance, the bus1205communicatively connects the processing unit(s)1210with the read-only memory1230, the system memory1225, and the permanent storage device1235.

From these various memory units, the processing unit(s)1210retrieve instructions to execute and data to process in order to execute the processes of the invention. The processing unit(s) may be a single processor or a multi-core processor in different embodiments.

The read-only-memory (ROM)1230stores static data and instructions that are needed by the processing unit(s)1210and other modules of the electronic system1200. The permanent storage device1235, on the other hand, is a read-and-write memory device. This device is a non-volatile memory unit that stores instructions and data even when the electronic system1200is off. Some embodiments of the invention use a mass-storage device (such as a magnetic or optical disk and its corresponding disk drive) as the permanent storage device1235.

Other embodiments use a removable storage device (such as a floppy disk, flash drive, etc.) as the permanent storage device1235. Like the permanent storage device1235, the system memory1225is a read-and-write memory device. However, unlike storage device1235, the system memory1225is a volatile read-and-write memory, such a random access memory. The system memory1225stores some of the instructions and data that the processor needs at runtime. In some embodiments, the invention's processes are stored in the system memory1225, the permanent storage device1235, and/or the read-only memory1230. From these various memory units, the processing unit(s)1210retrieve instructions to execute and data to process in order to execute the processes of some embodiments.

The bus1205also connects to the input and output devices1240and1245. The input devices1240enable the user to communicate information and select commands to the electronic system. The input devices1240include alphanumeric keyboards and pointing devices (also called “cursor control devices”). The output devices1245display images generated by the electronic system1200. The output devices1245include printers and display devices, such as cathode ray tubes (CRT) or liquid crystal displays (LCD). Some embodiments include devices such as a touchscreen that function as both input and output devices1240and1245.

Finally, as shown inFIG. 12, bus1205also couples electronic system1200to a network1265through a network adapter (not shown). In this manner, the computer can be a part of a network of computers (such as a local area network (“LAN”), a wide area network (“WAN”), or an Intranet, or a network of networks, such as the Internet. Any or all components of electronic system1200may be used in conjunction with the invention.

Hypervisor kernel network interface modules, in some embodiments, are non-VM DCNs that include a network stack with a hypervisor kernel network interface and receive/transmit threads. One example of a hypervisor kernel network interface module is the vmknic module that is part of the ESXi™ hypervisor of VMware, Inc.

It should be understood that while the specification refers to VMs, the examples given could be any type of DCNs, including physical hosts, VMs, non-VM containers, and hypervisor kernel network interface modules. In fact, the example networks could include combinations of different types of DCNs in some embodiments.