Connection tracking records for a very large scale nat engine

Abstract

Some embodiments provide a novel method for performing network address translation to share a limited number of external source network addresses among a large number of connections. Instead of allocating an external source network address for an egressing packet just based on its internal source network address, the method of some embodiments allocates the external source network address based on the egressing packet's source network address and destination network address. This allows a limited number of external source network addresses to be re-used for different destination network address. For instance, in some embodiments, the method's network address allocation scheme allows the same 64K (e.g., 2{circumflex over ( )}16) external source ports to be used for 64K connections for each destination network address.

1 - 24 . (canceled) 
     
     
         25 . A method of allocating external source port addresses for a plurality of connections that share a limited set of external source IP addresses for connections to a destination IP address outside of a network, the method comprising:
 specifying a plurality of pre-allocated port groups with each group comprising a plurality of external source port addresses;   allocating, for new connections to the destination IP address, external source port addresses from the pre-allocated groups when external source port addresses are available in the pre-allocated groups; and   dynamically modifying a number of the pre-allocated groups as a number of connections increases or decreases to destinations outside of the network.   
     
     
         26 . The method of  claim 25 , wherein said specifying, allocating and dynamically modifying provide an efficient mechanism for (i) tracking source port addresses assigned to connections to the destination IP address, and (ii) allocating new source port addresses when no previously pre-allocated source port addresses are available. 
     
     
         27 . The method of  claim 25 , wherein each pre-allocated group includes a plurality of source port addresses. 
     
     
         28 . The method of  claim 27 , wherein the source port addresses in each pre-allocated group are contiguous addresses in a range. 
     
     
         29 . The method of  claim 25 , wherein the plurality of pre-allocated groups is a first set of pre-allocated groups, and dynamically modifying the number comprises
 identifying a new connection for which an external source port has to be assigned;   determining that the first set of pre-allocated groups does not have an external source port address available to assign to the new connection; and   specifying a second set of pre-allocated groups of external port addresses and allocating an external port address from the second set of pre-allocated groups.   
     
     
         30 . The method of  claim 25  further comprising:
 determining that a pre-allocated group does not have any available port for allocation to a new packet flow; and 
 selecting another pre-allocated group from which a port should be selected for the new packet flow. 
 
     
     
         31 . The method of  claim 25  further comprising:
 defining different sets of pluralities of pre-allocated port groups, each set associated with a different external destination IP address; 
 identifying, for a new packet flow, the port-group set associated with an external destination IP address stored in a header field of the new flow; and 
 allocating, for the new packet flow, an external port address from a particular pre-allocated port group in the identified port-group set. 
 
     
     
         32 . The method of  claim 31  further comprising:
 defining, for each external destination IP address, a connection-tracking data store for storing connection-tracking records that map allocated external source port addresses to internal source IP and port addresses within the network, said connection-tracking records for use in performing network address translation on packets of flows exiting the network and performing destination address translation on packets of flows entering the network. 
 
     
     
         33 . The method of  claim 25  further comprising:
 allocating a bitmap of available source ports; 
 allocating contiguous blocks of source ports in the bitmap to different pre-allocated port groups; and 
 using the bitmap to identify the pre-allocated port groups and adjust the number of pre-allocated port groups. 
 
     
     
         34 . A non-transitory machine readable medium storing a program which when executed by one or more processing units allocates external source port addresses for a plurality of connections that share a limited set of external source IP addresses for connections to a destination IP address outside of a network, the program comprising sets of instructions for:
 specifying a plurality of pre-allocated port groups with each group comprising a plurality of external source port addresses;   allocating, for new connections to the destination IP address, external source port addresses from the pre-allocated groups when external source port addresses are available in the pre-allocated groups; and   dynamically modifying a number of the pre-allocated groups as a number of connections increases or decreases to destinations outside of the network.   
     
     
         35 . The non-transitory machine readable medium of  claim 34 , wherein said specifying, allocating and dynamically modifying provide an efficient mechanism for (i) tracking source port addresses assigned to connections to the destination IP address, and (ii) allocating new source port addresses when no previously pre-allocated source port addresses are available. 
     
     
         36 . The non-transitory machine readable medium of  claim 34 , wherein each pre-allocated group includes a plurality of source port addresses. 
     
     
         37 . The non-transitory machine readable medium of  claim 36 , wherein the source port addresses in each pre-allocated group are contiguous addresses in a range. 
     
     
         38 . The non-transitory machine readable medium of  claim 34 , wherein the plurality of pre-allocated groups is a first set of pre-allocated groups, and dynamically modifying the number comprises
 identifying a new connection for which an external source port has to be assigned;   determining that the first set of pre-allocated groups does not have an external source port address available to assign to the new connection; and   specifying a second set of pre-allocated groups of external port addresses and allocating an external port address from the second set of pre-allocated groups.   
     
     
         39 . The non-transitory machine readable medium of  claim 34 , wherein the program further comprises sets of instructions for:
 defining different sets of pluralities of pre-allocated port groups, each set associated with a different external destination IP address;   identifying, for a new packet flow, the port-group set associated with an external destination IP address stored in a header field of the new flow; and   allocating, for the new packet flow, an external port address from a particular pre-allocated port group in the identified port-group set.   
     
     
         40 . The non-transitory machine readable medium of  claim 39 , wherein the program further comprises sets of instructions for:
 defining, for each external destination IP address, a connection-tracking data store for storing connection-tracking records that map allocated external source port addresses to internal source IP and port addresses within the network, said connection-tracking records for use in performing network address translation on packets of flows exiting the network and performing destination address translation on packets of flows entering the network.   
     
     
         41 . The non-transitory machine readable medium of  claim 34 , wherein the program further comprises sets of instructions for:
 allocating a bitmap of available source ports;   allocating contiguous blocks of source ports in the bitmap to different pre-allocated port groups; and   using the bitmap to identify the pre-allocated port groups and adjust the number of pre-allocated port groups.