Network address translation within network device having multiple service units

The disclosure relates to computer networks and, more particularly, to network address translation in computer networks.

A computer network generally includes a number of interconnected network devices. Large networks, such as the Internet, typically include a number of interconnected computer networks, which in this context are often referred to as sub-networks or subnets. These subnets are each assigned a range of network addresses that can be allocated to the individual network devices that reside in the respective subnet. A server in each subnet may be responsible for allocating these network addresses in accordance with a network address allocation protocol, such as a dynamic host configuration protocol (DHCP).

Service provider networks typically assign private network addresses to the subscriber equipment (e.g., cable modems, DLS modems, mobile devices) utilized by their customers. For example, a DHCP server or Radius server may dynamically assign a private address to a subscriber device upon establishing a network connection for the subscriber equipment. When not in use, the network connection is torn down and the private address is returned to a pool of provider addresses utilized within the service provider network. These private addresses are not routable outside the service provider network. Instead, a network address translation (NAT) device translates the private addresses currently used by subscriber equipment to public network addresses that are routable within a public network, such as the Internet.

In general, techniques for deterministic network address translation (NAT) are described. In particular, techniques are describes for ensuring that inbound and outbound packet flows for a subscriber communication session are processed by a same one of a plurality of services processing unit (SPUs) internal to a NAT device even when network address translation is performed on the subscriber session such that the inbound and outbound packets of the subscriber communication session may have different 5-tuple information in their headers.

In one aspect, a network device having multiple service units receives an outbound packet of a communication session, wherein the outbound packet includes a private source network address and source port. Each of the service units is configured to perform network address translation (NAT) on the outbound packet. The network device applies a service unit selection function to at least a portion of a header of the outbound packet to produce a first result, and selects, based on the first result, one of the service units to perform NAT for packets of the communication session. The network device determines a port for network address translation that produces a second result equal to the first result when the service unit selection function is applied to the portion of the header when the portion includes a selected public network address and determined port. This allows the selected service unit to perform session-aware services upon both inbound and outbound packets of the communication session without redirecting any of the inbound packets or the outbound packets between the service units for application of the session-aware services.

In one example, a method includes receiving, with a network device having a plurality of service units, an outbound packet of a communication session for a subscriber, wherein the outbound packet includes a private source network address and source port, and wherein each of the plurality of service units is configured to perform network address translation (NAT), and applying a service unit selection function to at least a portion of a header of the outbound packet to produce a first result. The method also includes selecting, based on the first result, a first one of the service units to perform NAT for packets of the communication session, selecting, with the network device, a public network address for network address translation of the outbound packet for the communication session, determining, with the network device, a port for network address translation that produces a second result equal to the first result when the service unit selection function is applied to the portion of the header after the private source network address and source port of the inbound packet are replaced with the selected public network address and determined port, generating a translated packet from the packet, wherein the translated packet includes the selected public network address and the determined port in place of the private source address and source port, and forwarding the translated packet from the network device to a public network.

In another example, a network device includes a network interface to receive an outbound packet of a communication session for a subscriber, wherein the outbound packet includes a private source network address and source port, a plurality of service units configured to perform network address translation (NAT), a service unit selector configured to apply a service unit selection function to at least a portion of a header of the outbound packet to produce a first result, and select, based on the first result, a first one of the service units to perform NAT for packets of the communication session, and a NAT controller configured to select a public network address for network address translation of the outbound packet for the communication session, wherein the controller determines a port for network address translation that produces a second result equal to the first result when the service unit selection function is applied to the portion of the header after the private source network address and source port of the inbound packet are replaced with the selected public network address and determined port.

In a further example, a non-transitory computer-readable storage medium includes instructions for causing at least one programmable processor of a network device having a plurality of service units to receive an outbound packet of a communication session for a subscriber, wherein the outbound packet includes a private source network address and source port, and wherein each of the plurality of service units is configured to perform network address translation (NAT); apply a service unit selection function to at least a portion of a header of the outbound packet to produce a first result; select, based on the first result, a first one of the service units to perform NAT for packets of the communication session; select a public network address for network address translation of the outbound packet for the communication session; determine a port for network address translation that produces a second result equal to the first result when the service unit selection function is applied to the portion of the header after the private source network address and source port of the inbound packet are replaced with the selected public network address and determined port; generate a translated packet from the packet, wherein the translated packet includes the selected public network address and the determined port in place of the private source address and source port; and forward the translated packet from the network device to a public network.

The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.

FIG. 1 is a block diagram illustrating an exemplary network system that implements the network address translation techniques described in this disclosure.

FIG. 2 illustrates an example network device that incorporates the NAT functions described herein.

FIG. 3 is a flowchart illustrating example operation of a NAT device in accordance with the techniques described herein

FIG. 4 is a flowchart illustrating in further detail an example process of assigning a source port for NAT to ensure that inbound and outbound packet flows for a subscriber session are directed to the same services processing unit (SPU) of a device.

FIG. 5 is a schematic diagram illustrating data structure having a set of source port groupings utilized by the NAT techniques described herein.

FIG. 1 is a block diagram illustrating an exemplary network system 10 that implements the network address translation techniques described in this disclosure. As shown in the example of FIG. 1 , network system 10 includes a service provider network 20 and a public network 21 .

In the example of FIG. 1 , service provider network 20 operates as a private network that provides packet-based network access for subscribers associated with home gateways 18 A- 18 M (“HGWs” 18 ) or mobile devices 19 . HGWs 18 are service endpoint computing devices, such as personal computers, laptop computers or other types of computing device associated with the subscribers. In addition, service provider network 20 may provide data services to cellular mobile devices 19 A- 19 N (“mobile devices 19 ”). Mobile devices 19 may comprise, for example, a mobile telephone, a laptop or desktop computer having, e.g., a 3G wireless card, a wireless-capable netbook, a video game device, a pager, a smart phone, or a personal data assistant (PDA). Each of mobile devices 19 may run one or more applications, such as mobile calls, video games, videoconferencing, and email, among others.

In the example of FIG. 1 , HGWs 18 connect to a broadband network gateway (BGW) 36 via network switch 38 . In one example, HGWs may be DSL modems and network switch 38 may comprise a digital subscriber line access multiplexer (DSLAM) or other switching device. Each of HGWs 18 may utilize a Point-to-Point Protocol (PPP), such as PPP over ATM or PPP over Ethernet (PPPoE), to communicate with network switch 38 . For example, using PPP, one of HGWs 18 may request access to core network 31 and provide login information, such as a username and password, for authentication by AAA server 30 . PPP may be supported on lines such as digital subscriber lines (DSLs) that connect endpoint computing devices 18 with network switch 38 . In other embodiments, endpoint computing devices 18 may utilize a non-PPP protocol to communicate with network switch 38 . Other embodiments may use other lines besides DSL lines, such as cable, Ethernet over a T1, T3 or other access links.

Network switch 38 may communicate with broadband network gateway 36 over a physical interface supporting various protocols, e.g., ATM interface supporting ATM protocols. Broadband network gateway 36 typically includes Broadband Remote Access Server (BRAS) functionality to aggregate output from switches into a higher-speed uplink to core network 31 . In some embodiments, broadband network gateway 36 may comprise a router that maintains routing information between endpoint computing devices 18 and core network 31 .

Service provider network 20 may also include radio access network 25 in which one or more base stations communicate via radio signals with mobile devices 19 . Radio access network 25 is a transport network that enables base stations to exchange packetized data with core network 31 of the service provider, ultimately for communication with public network 21 . Radio access network 25 typically comprises communication nodes interconnected by communication links, such as leased land-lines or point-to-point microwave connection. The communication nodes comprise network, aggregation, and switching elements that execute one or more protocols to route packets between base stations and gateway device (“GW”) 28 . Core network 31 provides session management, mobility management, and transport services between backhaul network 27 and core network 31 to support access, by mobile devices 19 , to public network 21 and services of protected resources 14 . Core network 31 may comprise, for instance, a general packet radio service (GPRS) core packet-switched network, a GPRS core circuit-switched network, an IP-based mobile multimedia core network, or another type of transport network. Core network 31 typically includes one or more packet processing nodes to support firewall, load balancing, billing, deep-packet inspection (DPI), and other services for mobile traffic traversing the mobile core network.

AAA server 30 is typically an authentication, authorization and accounting (AAA) server to authenticate the credentials of a subscriber requesting a network connection. The AAA server 30 may be integrated within a router or gateway of broadband network or on a separate network device and may be, for example, a Remote Authentication Dial-In User Service (RADIUS) server. Upon authenticating a network access request from either an HGW 18 or a mobile device 19 , AAA server 30 assigns a private layer three (L3) network address (e.g., an IPv4 network address) for receiving data services within service provider network 20 . This may be accomplished in a variety of ways. For example, the private network address may be statically configured on the subscriber device or may be dynamically or statically assigned by AAA server 30 (or gateway 28 ). Typically, upon authentication of the subscriber, AAA server 30 selects a private IP address from a pool of private network addresses. In some cases, BGW 36 or GW 28 may send a Radius authentication request to AAA server 30 for authentication and assignment of an IP address.

Once authenticated, any of HGWs 18 or mobile devices 19 may send subscriber data traffic toward core network 31 in order to access and receive services provided by public network 21 , and such packets traverse network address translation (NAT) device 41 as part of at least one packet flow. The term “packet flow,” “traffic flow,” or simply “flow” refers to a set of packets originating from a particular source device and sent to a particular destination device. A single flow of packets, in either the outbound (sourced by one of HGWs 18 or mobile devices 19 ) or inbound (destined for one of HGWs 18 or mobile devices 19 ) direction, may be identified by, for example, the 5-tuple: <source network address, destination network address, source port, destination port, protocol>. A pair of outbound packets and inbound packets (i.e., packet flows) may be part of the same communication session. This 5-tuple generally identifies a packet flow to which a received packet corresponds. An n-tuple refers to any n items drawn from the 5-tuple. For example, a 2-tuple for a packet may refer to the combination of <source network address, destination network address> or <source network address, source port> for the packet. Moreover, a subscriber device may originate multiple packet flows upon authenticating to service provider network 20 and establishing a communication session for receiving data services.

NAT device 41 may be a gateway or other appliance that provides services, such as network address translation for private network addresses routable within service provider network to public network addresses routable within public network 21 . As described herein, NAT device 41 includes a plurality of services processing units (SPUs) 47 that apply network services to communication sessions associated with the subscribers

As described herein, NAT device 41 directs inbound and outbound packet flows for each individual session to SPUs 47 for processing based on a service unit selection function, such as a hash value of the 5-tuple within headers of packets of the given packet flow, where the 5-tuple specifies a combination of the private source network address, source port, a public destination network address, destination port and protocol specified in the header of the inbound packet. Moreover, the techniques described herein ensure that even though a selection function, such as a hash function, is used to distribute packet flows across SPU 47 , both outbound packets and inbound packets of a NATed session will have the same hash value and are directed to the same SPU even though the packet headers likely differ due to the NAT operation. As such, the techniques avoid potentially having to internally redirect the inbound packet for a session from one SPU to another to ensure that both inbound and outbound packet flows for a session are directed to the same SPU for proper application of services. This can be useful when the SPU must also apply session-aware services to inbound and outbound packet flows of the communication session, such as firewall operations, billing services, deep-packet inspection (DPI), for example. Avoiding a need to internally redirect inbound packets between SPUs can result in more streamlined packet processing, and potentially save time and computing resources.

FIG. 2 illustrates an example network device 50 that incorporates the NAT functions described herein. In this example, network device 50 may be a standalone device or a router or gateway device. Network device 50 may perform the functions described above with respect to NAT device 41 of FIG. 1 . As such example, network device 50 may, for example, be a high-end router or gateway capable of deployment within a service provider network.

In the example of FIG. 2 , the components of network device 50 may be logically organized into a routing plane 60 , a forwarding plane 62 and a service plane 64 . Routing plane 60 provides a routing engine 66 that is primarily responsible for maintaining a routing information base (RIB) 222 to reflect the current topology of a network and other network entities to which network device 50 is connected. For example, routing engine 66 provides an operating environment for execution of routing protocols 70 that communicate with peer routers and periodically update RIB 68 to accurately reflect the topology of the network and the other network entities. Example protocols include routing and label switching protocols, such as Border Gateway Protocol (BGP), Intermediate System-to-Intermediate System (IS-IS), Resource Reservation Protocol with Traffic Engineering Extensions (RSVP-TE) and Label Distribution Protocol (LDP). In some embodiments, network device 50 may be a mobile gateway having a distributed control plane for handling mobile subscribers, such as described within U.S. patent application Ser. No. 13/172,556, entitled “MOBILE GATEWAY HAVING DECENTRALIZED CONTROL PLANE FOR ANCHORING SUBSCRIBER SESSIONS,” the entire contents of which being incorporated herein by reference.

In this example, network device 50 includes a plurality of service processing units 80 , each configured to apply session-aware services to communication sessions associated with a plurality of the subscribers. Each of the SPUs 80 may, for example, be configured to perform network address translation, firewall operations, load balancing, billing, deep-packet inspection (DPI), and other services for subscriber sessions.

Forwarding plane 62 receives and forwards packets associated with network packet flows 76 . Forwarding component 74 maintains forwarding information base (FIB) 78 in accordance with RIB 68 , which associates network destinations or MPLS labels with specific next hops and corresponding interface ports of output interface cards of network device 50 . Routing engine 66 typically processes RIB 68 to perform route selection and generate FIB 78 based on selected routes. In this way, next hop information may be programmed into forwarding plane 62 . Routing engine 66 may generate FIB 78 in the form of a radix tree having leaf nodes that represent destinations within the network. U.S. Pat. No. 7,184,437, the content of which is incorporated herein by reference in its entirety, provides details on an exemplary embodiment of a router that utilizes a radix tree for route resolution.

When forwarding a packet, forwarding component 74 traverses the radix tree to a leaf node based on information within a header of the packet to ultimately select a next hop and output interface to which to forward the packet. Based on the selection, forwarding component may output the packet directly to the output interface or, in the case of a multi-stage switch fabric of a high-end router, may forward the packet to subsequent stages for switching to the proper output interface. Forwarding plane 62 may be provided by dedicated forwarding integrated circuits normally associated with high-end routing and forwarding components of a network router. U.S. Patent Application 2008/0044181, entitled MULTI-CHASSIS ROUTER WITH MULTIPLEXED OPTICAL INTERCONNECTS, describes a multi-chassis router in which a multi-stage switch fabric, such as a 3-stage Clos switch fabric, is used as a high-end forwarding plane to relay packets between multiple routing nodes of the multi-chassis router. The entire contents of U.S. Patent Application 2008/0044181 are incorporated herein by reference.

In this way, as shown in the example of FIG. 2 , network device 50 integrates service plane 64 and routing plane 60 to utilize shared forwarding plane 62 . Forwarding plane 62 may be a rich and dynamic shared forwarding plane, optionally distributed over a multi-chassis router. Moreover, forwarding plane 62 may be provided by dedicated forwarding integrated circuits normally associated with high-end routing components of a network router. Consequently, routing plane 60 and forwarding plane 62 may operate as a high-end router or gateway, and service plane 64 has been tightly integrated within network device 50 (e.g., by way of service processing units (SPUs) 80 ) so as to use forwarding plane 62 of the routing components in a shared, cooperative manner. Further details of one example embodiment of network device 50 can be found in U.S. Pat. No. 8,339,959, filed May 20, 2008, entitled “STREAMLINED PACKET FORWARDING USING DYNAMIC FILTERS FOR ROUTING AND SECURITY IN A SHARED FORWARDING PLANE,” the entire contents of which is incorporated herein by reference.

Forwarding plane 62 includes a service unit selector 88 to selectively direct packets of communication sessions to one or more of service processing units 80 of service plane 64 for processing. For example, service unit selector 88 receives incoming packet flows 76 (e.g., outbound packets sourced by subscribers or inbound packets destined to subscribers) and applies a service processing unit selection function to direct the packets to service plane 64 for processing by service processing unit 80 . For example, service unit selector 88 may apply a hash function to at least a portion of the header of each packet and then apply a modulo operation based on the number N of SPUs 80 installed in network device 50 to compute a remainder ranging from 0 -N. Based on the remainder N, service unit selector 88 selects the corresponding one of SPU and directs the packet flows to the selected SPU 80 for NAT and application of any other session-aware services. When applying the hash function, service unit selector 88 may apply the hash function to a 5-tuple of the header of the packet, where the 5-tuple specifies a combination of the private source network address, source port, a public destination network address, destination port and protocol specified in the header of the packet.

Service processing units 80 receive packets from a given packet flow from service unit selector 88 , computes NAT information as described herein to select a public network address and port for the packet flow, perform any additional services and relay the packets to forwarding plane 62 for forwarding by forwarding component 74 in accordance with FIB 78 . Service processing units 80 within service plane 64 may be installed along a backplane or other interconnect of network device 50 to perform a variety of other services on the packets received from forwarding plane 62 , such as NAT, filtering, logging, Intrusion Detection and Prevention (IDP) analysis, virus scanning, deep packet inspection. In some examples, service processing units 80 may comprise one or more service cards installed within router 50 . For example, one or more of service processing units 80 may be implemented as a removable card having an electronic interface suitable for removable installation within a communication backplane of network device 50 .

In the example of FIG. 2 , service plane 64 includes a NAT controller 84 that operates to assign network addresses and ports to subscriber sessions in accordance with the techniques described herein. For example, NAT controller 84 responds to queries 85 from SPUs for a public network address and port for network address translation of a new packet flow. In response, NAT controller 84 selects an unused network address and applies the techniques described herein to select a port to be used in the network address translation, where this selection that ensures that inbound and outbound packet flows for a subscriber session are directed to the same services processing unit (SPU) of a device. In some examples, NAT controller 84 maintains a port lookup table 86 having a set of entries (e.g., row), each of the entries associates with a different group of ports. Moreover, NAT controller 84 constructs port lookup table 86 such that each group of ports specifies ports having port values such that any of the ports in the same group result in the same one of SPUs 80 being selected when the service selection function is applied.

Management daemon (MGD) 82 of routing engine 46 communicates with and programs service processing units 80 of service plane 64 . For example, routing engine 66 may present a user interface (UI) 89 to receive configuration data from administrator 70 . In response, MDG 82 programs SPUs 80 with corresponding configuration data, causing SPUs 80 of service plane 64 to perform the functions described herein when processing packets redirected from forwarding plane 62 .

FIG. 3 is a flowchart illustrating example operation of a NAT device (e.g., NAT device 41 of FIG. 1 or network device 50 of FIG. 2 ) in accordance with the techniques described herein. For purposes of example, the flowchart of FIG. 3 will be described with respect to network device 50 of FIG. 2 .

Upon initialization, network device 50 determines the number of SPUs and the number of ports available in the overall port space used during network address translation ( 90 ). For example, network device 50 may sense the number of SPUs 80 installed or may receive configuration information from administrator 70 .

Next, NAT controller 84 partitions the overall port space into groups of ports having port values that when the hash function is applied would result in selection of the same one of SPUs 80 . For example, assuming a total number of SPUs 80 equals 256 and a total port space of 65,536, NAT controller 84 may compute the number of port groups as 65,536/256=256 port groups. Each of the port groups consists of a set of ports having port values that produce selection of the same one of SPUs 80 . That is, in this example, each port value in a given group differs by an offset equal to the total number of SPUs N so as to yield the same remainder when the modulo operation is applied to the port value with the number of SPUs 80 . For example, a first one of the port groups may consist of ports {0, 256, 512, . . . }, while the second one of the port groups may consist of the ports {1, 257, 513 . . . }.

In one example, NAT control 84 constructs port lookup table 86 to have a set of entries, each of the entries associated with a respective one of the plurality of groups of ports. For example, port lookup table 86 may be a table or other data structure by which NAT controller 84 indicates whether a particular port of a particular port group is currently assigned for NAT for a current communication session. In one example, each of the entries of port lookup table 86 comprises a bit vector having a plurality of bits, each of the bits corresponding to a different one of the ports in the respective group of ports and indicating whether the respective port is currently assigned to a subscriber session for network address translation. Once NAT controller 84 has constructing port lookup table 86 , NAT controller 84 can initialize the data structure of port lookup table 86 by, for example, setting all bits in the matrix of bit vectors to an initial value, e.g., zero ( 91 ).

In operation, service unit selector 88 of network device 50 receives a first outbound packet of a new session ( 92 ) and applies the service unit selection function to select the handling SPU ( 93 ). For example, service unit selector 88 may perform a hash function on the current 5-tuple of the outbound packet to load balance the session among SPUs 80 ( 93 ). Once selected, the handling SPU issues a query 87 to NAT controller 84 , which in turn, selects the public IP address and port using techniques described herein and illustrated in FIG. 4 ( 94 ). NAT controller 84 communicates the public IP address and port information to the handling SPU ( 94 ). Network device 50 may then update port groupings of port lookup table 86 ( 95 ). Finally, the handling SPU may perform the NAT operation on the outbound packet ( 96 ), and perform any needed session-aware services ( 97 ), and forward the outbound packet.

Furthermore, service selector unit 88 may receive inbound packets destined for subscribers, where the inbound packets are of the same subscriber session as the previously handled outbound packet flow ( 98 ) and apply the same service unit selection function in order to select one of SPUs 80 to which to direct the inbound packet flow ( 99 ). Based on techniques described herein, service selector unit applies the hash function, which results in selection of the same one of SPUs as was selected to handle the outbound packet flow for the subscriber session. The handling one of SPUs 80 performs reverse NAT on the inbound packet ( 100 ), as well as performing any needed session-aware services ( 101 ), and may then forward the inbound packet to the subscriber. In this manner, the techniques can apply NAT while avoiding potentially having to internally redirect the inbound packet for a session from one SPU to another to ensure that both inbound and outbound packet flows for a session are directed to the same SPU for proper application of services. This can be useful when the SPU must also apply session-aware services to inbound and outbound packet flows of the communication session, such as firewall operations, billing services, deep-packet inspection (DPI), for example. Avoiding a need to internally redirect inbound packets between SPUs can result in more streamlined packet processing, and potentially save time and computing resources.

FIG. 4 is a flowchart illustrating example operation of a NAT device (e.g., NAT device 41 of FIG. 1 or network device 50 of FIG. 2 ) when selecting a source port address such that the inbound packets of a NATed session have the same hash value and are directed to the same SPU as the outbound packets of the session. For example, FIG. 4 illustrates in further detail example operation of a device such as network device 50 when performing step 94 of FIG. 3 .

Upon receiving query 87 conveying the original 5-tuple of an outbound packet for a newly detected subscriber session, NAT controller 84 selects a free public network address and then computes the modulo of the 5-tuple and the number of SPUs to determine the first remainder ( 110 ). That is, NAT controller 84 applies the modulo operation to the original 5-tuple using the number N of SPUs 80 , where the 5-tuple specifies a combination of the private source network address, source port, a public destination network address, destination port and protocol specified in the original header of the outbound packet.

Next, NAT controller 84 computes the modulo for the 4-tuple that would be seen in any inbound packet (source port excluded) with the number of SPUs to determine the second remainder ( 111 ). Specifically, NAT controller 84 computes the modulo of a 4-tuple of the translated packet with the number of service units to determine a second remainder, wherein the 4-tuple specifies a combination of the public source network address selected by NAT controller 84 as well as the public destination network address, destination port and protocol specified in the header of the outbound packet.

NAT controller 84 computes the composite remainder by calculating the exclusive OR (XOR) result of the first and second remainder ( 112 ). This composite remainder is indicative of the remainder that will be produced when service unit selector 88 subsequently receives inbound packets destined for subscribers for the particular communication session. As such, NAT controller 84 traverses port lookup table 86 in order to select the port from the group of ports that would produce the necessary composite remainder, thereby leading to assignment of the same handling one of SPUs 80 ( 113 ). If no source port within the group of source ports associated with the composite remainder is available, NAT controller 84 may assign a random source port ( 114 ).

The following illustrates how a NAT device can select a source port address such that the inbound packets of a NATed session have the same hash value and are directed to the same SPU as the outbound packets of the session. Here, M1 stands for the original 5 tuple, and M2 stands for the 5 tuple after NAT. src_ip′, src_port′, dst_ip′, dst_port′ may be different from original wing.

We start with: M1% spu_num=M2% spu_num.

Since A∧B=B∧A, replace M2 with 5 tuple calculation:

M1% spu_num=(src_port′∧src_ip∧dst_ip′∧dst_port′∧protocol) % spu_num.

Let D replace src_ip′∧dst_ip′∧dst_port′∧protocol.

This gives:

M1% spu_num=(src_port′∧D) % spu_num.

If spu_num=2 n , then (A∧B) % 2 n =(A % 2 n )∧(B % 2 n ), and flow guarantees this assumption is always correct.

Thus, M1% spu_num=(src_port′% spu_num)∧(D % spu_num).

Since C=A∧B; A=C∧B, and B=C∧A, we have:

src_port′% spu_num=(D % spu_num)∧(M % spu_num).

FIG. 5 illustrates an example port lookup table 121 that may be an example implementation of port lookup table 86 . As shown in FIG. 5 , the example port lookup table 121 includes a set of entries (e.g., rows) 122 A- 122 N that effectively partition the overall port space into N port groupings. Each of entries 122 is associated with a different group of ports. Moreover, each group of ports specifies ports having port values such that any of the ports in the same group result in the same one of SPUs 80 being selected when the service selection function (e.g., a hash function) is applied.

In this example, the port lookup table is constructed with 256 total number of SPUs 256 and a total port space of 65,536, thus leading to 256 port groups. Each of the port groups consists of a set of ports having port values that produce selection of the same one of SPUs 80 . That is, in this example, each port value in a given group differs by an offset equal to the total number of SPUs N so as to yield the same remainder when the modulo operation is applied to the port value with the number of SPUs 80 . For example, a first one of the port groups may consist of ports {0, 256, 512, . . . } while the second one of the port groups may consist of the ports {1, 257, 513 . . . }.

In an example, a NAT device having 256 SPUs may receive a packet with 5-tuple values as follows: src ip=1.1.1.1, src port=100, dst ip=2.2.2.2, dst port=100, and protocol=6. In selecting an SPU, service unit selector 88 hashes the 5-tuple (1.1.1.1, 100, 2.2.2.2, 100, 6) by applying a service unit selection function that is defined as the byte XOR of the values within the 5-tuple and performing a modulo operation of the result using 256 as the number of SPUs in order to determine the remainder:

spu_id=(byte XOR(1.1.1.1, 100, 2.2.2.2, 100, 6)) % 256=6

In this example, the hash calculation yields a remainder of 6. Therefore, service unit selector 88 distributes the outbound packet to the SPU associated with a remainder of 6.

In this example, NAT controller 84 assigns a free public source network address of 4.4.4.4. In addition, assume for purposes of example that the packet also undergoes destination NAT such that, for example, the dst ip is to be changed to 3.3.3.3 and the dst port is to be changed to 200.

In order to ensure the inbound packets for the same communication session are distributed to the same SPU, NAT controller 84 selects a source port such that the hash of the inbound 5-tuple will be equal to the original outbound 5-tuple hash. In this example, the source translated port is determined by equating the 4-tuple remainder (excluding the source port) with MOD 256 , the number of SPUs, with the original 5-tuple remainder of 6. The byte XOR operation is be performed between the original 5-tuple remainder and the 4-tuple remainder yielding a composite remainder of 206 in this example. Next, NAT controller 84 traverses port look-up table 86 , described in detail above, in order to allocate a source port from a group of ports that are all associated with the remainder of 206 , thereby selecting a port that, when utilized in the 5-tuple for incoming packets, will produce a remainder of 6 and, therefore, be directed to the same SPU as outbound packets for the session. If all source ports associated with remainder 206 have been allocated, network device 50 may then allocate a random source port for the inbound packet.

The techniques described in this disclosure may be implemented, at least in part, in hardware, software, firmware or any combination thereof. For example, various aspects of the described techniques may be implemented within one or more processors, including one or more microprocessors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or any other equivalent integrated or discrete logic circuitry, as well as any combinations of such components. The term “processor” or “processing circuitry” may generally refer to any of the foregoing logic circuitry, alone or in combination with other logic circuitry, or any other equivalent circuitry. A control unit comprising hardware may also perform one or more of the techniques of this disclosure.

Such hardware, software, and firmware may be implemented within the same device or within separate devices to support the various operations and functions described in this disclosure. In addition, any of the described units, modules or components may be implemented together or separately as discrete but interoperable logic devices. Depiction of different features as modules or units is intended to highlight different functional aspects and does not necessarily imply that such modules or units must be realized by separate hardware or software components. Rather, functionality associated with one or more modules or units may be performed by separate hardware or software components, or integrated within common or separate hardware or software components.

The techniques described in this disclosure may also be embodied or encoded in a computer-readable medium, such as a computer-readable storage medium, containing instructions. Instructions embedded or encoded in a computer-readable medium may cause a programmable processor, or other processor, to perform the method, e.g., when the instructions are executed. Computer readable storage media may include random access memory (RAM), read only memory (ROM), programmable read only memory (PROM), erasable programmable read only memory (EPROM), electronically erasable programmable read only memory (EEPROM), flash memory, a hard disk, a CD-ROM, a floppy disk, a cassette, magnetic media, optical media, or other computer-readable storage media. It should be understood that the term “computer-readable storage media” refers to physical storage media, and not signals or carrier waves, although the term “computer-readable media” may include transient media such as signals, in addition to physical storage media.

Various embodiments of the invention have been described. These and other embodiments are within the scope of the following claims.