Mechanisms for providing stateful NAT support in redundant and asymetric routing environments

• US 7,227,872 B1
• Filed: 09/04/2002
• Issued: 06/05/2007
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Biswas, Kaushik P., Jayasenan, Siva S., Somasundaram, Mahadev, Denny, Mark A.
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): TRAN, PHUC H
• Application Number:
  US10/235,523
• Time in Patent Office: 1,735 Days
• Field of Search: 370/395.5, 370/466, 370/467, 370/465
• US Class Current: 370/465
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/58 Association of routers
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 61/2514 between local and global IP addresses
• CPC Class Codes: H04L 61/2532 Clique of NAT servers
• CPC Class Codes: H04L 61/2557 Translation policies or rules
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

Various techniques are described which may be used for improving traffic flows between private networks and public networks. According to one aspect of the present invention, a technique is described for implementing asymmetric routing in a NAT routing environment. Another aspect of the present invention provides a technique for implementing load balancing and resource allocation assignments among peers in a redundant, multiple NAT router environment.

Claims

1. A method for performing resource allocation among a plurality of peer routers in a private network, the plurality of peer routers being adapted to provide connectivity between nodes in the private network and nodes in a public network, at least a first portion of the plurality of peer routers being adapted to perform network address translation (NAT) for traffic flowing between the public and private networks, at least a second portion of the plurality of peer routers being adapted to provide failover capability for the at least one of the other peer routers, the method comprising:

sending, from a first peer router, a first Elect Master message to at least one other peer router;

the first Elect Master message including information relating to characteristics associated with the first peer router;

receiving, at the first peer router, a second Elect Master message from a second peer router;

the second Elect Master message including information relating to characteristics associated with the second peer router;

populating a local Peer Resource Assignment Table with information obtained from received Elect Master messages; and

determining an identity of a master peer router using information obtained from the local Peer Resource Assignment Table.

2. The method of claim 1 wherein said local Peer Resource Assignment Table includes priority information relating to a relative priority value associated with selected peer routers;

and

wherein the method further comprises using the priority information to determine the identity of the master peer router.

3. The method of claim 1 further comprising:

dynamically allocating NAT resource assignments from a common NAT pool to selected peer routers;

generating at least one Peer Resource Assignment Update message which includes NAT resource assignment information;

said NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to each of the selected peer routers; and

sending the at least one Peer Resource Assignment Update message to at least one of the other peer routers.

4. The method of claim 3 wherein the at least one Peer Resource Assignment Update message is used to cause at least one of the other peer routers to update its local Peer Resource Assignment Table using the NAT resource assignment information obtained from the at least one Peer Resource Assignment Update message.

5. The method of claim 3, wherein said dynamically allocating includes dynamically allocating selected global address assignments and selected global port assignments from a common NAT pool to each of the selected peer routers.

6. The method of claim 3 further comprising detecting which of the plurality of peer routers is currently on-line;

wherein the selected peer routers correspond to peer routers which have been detected as being on-line.

7. The method of claim 1 further comprising:

receiving a Peer Resource Assignment Update message which includes updated NAT resource assignment information;

said updated NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to selected peer routers;

the global address assignments and selected global port assignments being allocated from a common NAT pool; and

updating the local Peer Resource Assignment Table using the NAT resource assignment information obtained from the Peer Resource Assignment Update message.

8. The method of claim 1 further comprising:

updating the local Peer Resource Assignment Table with NAT resource assignment information;

said updated NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to selected peer routers;

the global address assignments and selected global port assignments being allocated from a common NAT pool; and

detecting a failure at least one peer router;

sending a third Elect Master message to at least one other peer router in response to detecting the failure at the least one peer router;

receiving at least one other Elect Master message from at least one other peer router; and

updating the local Peer Resource Assignment Table with updated NAT resource assignment information;

wherein the updated NAT resource assignment information includes information relating to selected global address assignments and selected global port assignments allocated to on-line peer routers.

9. The method of claim 1 further comprising:

updating the local Peer Resource Assignment Table with NAT resource assignment information;

said updated NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to each of the selected peer routers;

the global address assignments and selected global port assignments being allocated from a common NAT pool; and

detecting a failure at the second peer router;

identifying second peer NAT resource assignments allocated to the second peer router;

said second peer NAT resource assignments including selected global address assignments and selected global port assignments allocated to the second peer router; and

re-assigning the second peer NAT resource assignments to a different peer router.

10. The method of claim 1 further comprising:

updating the local Peer Resource Assignment Table with NAT resource assignment information;

said updated NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to each of the selected peer routers;

the global address assignments and selected global port assignments being allocated from a common NAT pool; and

detecting at least one peer router coming on-line;

sending a third Elect Master message to at least one other peer router in response to detection of the at least one peer router coming on line;

receiving at least one other Elect Master message from at least one other peer router; and

updating the local Peer Resource Assignment Table with updated NAT resource assignment information;

wherein the updated NAT resource assignment information includes information relating to selected global address assignments and selected global port assignments allocated to on-line peer routers.

11. A method for performing resource allocation among a plurality of peer routers in a private network, the plurality of peer routers being adapted to provide connectivity between nodes in the private network and nodes in a public network, at least a first portion of the plurality of peer routers being adapted to perform network address translation (NAT) for traffic flowing between the public and private networks, at least a second portion of the plurality of peer routers being adapted to provide failover capability for the at least one of the other peer routers, the method comprising:

generating, at a first peer router, a local Peer Resource Assignment Table which includes NAT resource assignment information relating to selected global address assignments and selected global port assignments allocated to selected peer routers;

said NAT resource assignment information including first peer router information relating to global address assignments and selected global port assignments allocated to the first peer router;

receiving a first packet relating to a first flow between a private network node and a public network node;

allocating, using the first peer router information, a selected global address and a selected global port for the first flow;

creating a first NAT entry associated with the first flow, the first NAT entry including information relating to the selected global address and the selected global port allocated for the first flow;

sending at least one NAT Entry Update message to at least one other peer router; and

wherein the at least one NAT Entry Update message includes information relating to the first NAT entry.

12. A method for performing resource allocation among a plurality of peer routers in a private network, the plurality of peer routers being adapted to provide connectivity between nodes in the private network and nodes in a public network, at least a first portion of the plurality of peer routers being adapted to perform network address translation (NAT) for traffic flowing between the public and private networks, at least a second portion of the plurality of peer routers being adapted to provide failover capability for the at least one of the other peer routers, the method comprising:

generating, at a first peer router, a local Peer Resource Assignment Table which includes NAT resource assignment information relating to selected global address assignments and selected global port assignments allocated to selected peer routers;

said NAT resource assignment information including first peer router information relating to global address assignments and selected global port assignments allocated to the first peer router;

receiving a NAT Entry Update message from a second peer router, the NAT Entry Update message including information relating to a selected global address and a selected global port allocated for a first NAT entry;

reserving the selected global address and the selected global port associated with the first NAT entry; and

updating a local NAT Table with information relating to the first NAT entry.

13. A network device for performing resource allocation among a plurality of peer routers in a private network, the plurality of peer routers being adapted to provide connectivity between nodes in the private network and nodes in a public network, the network device comprising:

at least one processor;

at least one interface for providing a communication link to at least one other peer router; and

at least one memory;

the at least one processor or memory being configured to perform network address translation (NAT) for traffic flowing between the public and private networks;

the at least one processor or memory being further configured to provide failover capability for the at least one of the other peer routers;

the at least one processor or memory being further configured to send, from a first peer router, a first Elect Master message to at least one other peer router;

the first Elect Master message including information relating to characteristics associated with the first peer router, said characteristics including an identity and an address associated with the first peer router;

the at least one processor or memory being further configured to receive, at the first peer router, a second Elect Master message from a second peer router;

the second Elect Master message including information relating to characteristics associated with the second peer router, said characteristics including an identity and an address associated with the second peer router;

the at least one processor or memory being further configured to populate a local Peer Resource Assignment Table with information obtained from received Elect Master messages; and

the at least one processor or memory being further configured to determine an identity of a master peer router using information obtained from the local Peer Resource Assignment Table.

14. The network device of claim 13 wherein said local Peer Resource Assignment Table includes priority information relating to a relative priority value associated with selected peer routers;

and

wherein the priority information is used to determine the identity of the master peer router.

15. The network device of claim 13, the at least one processor or memory being further configured to:

dynamically allocate NAT resource assignments from a common NAT pool to selected peer routers;

generate at least one Peer Resource Assignment Update message which includes NAT resource assignment information, said NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to each of the selected peer routers; and

send the at least one Peer Resource Assignment Update message to at least one of the other peer routers.

16. The network device of claim 15 wherein the at least one Peer Resource Assignment Update message is used to cause at least one of the other peer routers to update its local Peer Resource Assignment Table using the NAT resource assignment information obtained from the at least one Peer Resource Assignment Update message.

17. The network device of claim 15, the at least one processor or memory being further configured to dynamically allocate selected global address assignments and selected global port assignments from a common NAT pool to each of the selected peer routers.

18. The network device of claim 15, the at least one processor or memory being further configured to detect which of the plurality of peer routers is currently on-line;

wherein the selected peer routers correspond to peer routers which have been detected as being on-line.

19. The network device of claim 13, the at least one processor or memory being further configured:

receive a Peer Resource Assignment Update message which includes updated NAT resource assignment information, said updated NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to selected peer routers, the global address assignments and selected global port assignments being allocated from a common NAT pool; and

update the local Peer Resource Assignment Table using the NAT resource assignment information obtained from the Peer Resource Assignment Update message.

20. The network device of claim 13, the at least one processor or memory being further configured to:

update the local Peer Resource Assignment Table with NAT resource assignment information, said updated NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to selected peer routers, the global address assignments and selected global port assignments being allocated from a common NAT pool; and

detect a failure at least one peer router;

send a third Elect Master message to at least one other peer router in response to detect the failure at the least one peer router;

receive at least one other Elect Master message from at least one other peer router; and

update the local Peer Resource Assignment Table with updated NAT resource assignment information;

wherein the updated NAT resource assignment information includes information relating to selected global address assignments and selected global port assignments allocated to on-line peer routers.

21. The network device of claim 13, the at least one processor or memory being further configured to:

update the local Peer Resource Assignment Table with NAT resource assignment information, said updated NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to each of the selected peer routers, the global address assignments and selected global port assignments being allocated from a common NAT pool; and

detect a failure at the second peer router;

identify second peer NAT resource assignments allocated to the second peer router, said second peer NAT resource assignments including selected global address assignments and selected global port assignments allocated to the second peer router; and

re-assign the second peer NAT resource assignments to a different peer router.

22. The network device of claim 13, the at least one processor or memory being further configured to:

update the local Peer Resource Assignment Table with NAT resource assignment information, said updated NAT resource assignment information including information relating to selected global address assignments and selected global port assignments allocated to each of the selected peer routers, the global address assignments and selected global port assignments being allocated from a common NAT pool; and

detect at least one peer router coming on-line;

send a third Elect Master message to at least one other peer router in response to detection of the at least one peer router coming on line;

receive at least one other Elect Master message from at least one other peer router; and

update the local Peer Resource Assignment Table with updated NAT resource assignment information;

wherein the updated NAT resource assignment information includes information relating to selected global address assignments and selected global port assignments allocated to on-line peer routers.

23. A network device for performing resource allocation among a plurality of peer routers in a private network, the plurality of peer routers being adapted to provide connectivity between nodes in the private network and nodes in a public network, the network device comprising:

at least one processor;

at least one interface for providing a communication link to at least one other peer router; and

at least one memory;

the at least one processor or memory being configured to perform network address translation (NAT) for traffic flowing between the public and private networks;

the at least one processor or memory being configured to provide failover capability for the at least one of the other peer routers;

the at least one processor or memory being further configured to generate, at a first peer router, a local Peer Resource Assignment Table which includes NAT resource assignment information relating to selected global address assignments and selected global port assignments allocated to selected peer routers, said NAT resource assignment information including first peer router information relating to global address assignments and selected global port assignments allocated to the first peer router;

the at least one processor or memory being further configured to receive a first packet relating to a first flow between a private network node and a public network node;

the at least one processor or memory being further configured to allocate, using the first peer router information, a selected global address and a selected global port for the first flow;

the at least one processor or memory being further configured to create a first NAT entry associated with the first flow, the first NAT entry including information relating to the selected global address and the selected global port allocated for the first flow;

the at least one processor or memory being further configured to send at least one NAT Entry Update message to at least one other peer router; and

wherein the at least one NAT Entry Update message includes information relating to the first NAT entry.

24. A network device for performing resource allocation among a plurality of peer routers in a private network, the plurality of peer routers being adapted to provide connectivity between nodes in the private network and nodes in a public network, the network device comprising:

at least one processor;

at least one interface for providing a communication link to at least one other peer router; and

at least one memory;

the at least one processor or memory being configured to perform network address translation (NAT) for traffic flowing between the public and private networks;

the at least one processor or memory being further configured to provide failover capability for the at least one of the other peer routers;

the at least one processor or memory being further configured to generate, at a first peer router, a local Peer Resource Assignment Table which includes NAT resource assignment information relating to selected global address assignments and selected global port assignments allocated to selected peer routers, said NAT resource assignment information including first peer router information relating to global address assignments and selected global port assignments allocated to the first peer router;

the at least one processor or memory being further configured to receive a NAT Entry Update message from a second peer router, the NAT Entry Update message including information relating to a selected global address and a selected global port allocated for a first NAT entry;

the at least one processor or memory being further configured to reserve the selected global address and the selected global port associated with the first NAT entry; and

the network device being further configured or designed to update a local NAT Table with information relating to the first NAT entry.

25. A system for performing resource allocation among a plurality of peer routers in a private network, the plurality of peer routers being adapted to provide connectivity between nodes in the private network and nodes in a public network, at least a first portion of the plurality of peer routers being adapted to perform network address translation (NAT) for traffic flowing between the public and private networks, at least a second portion of the plurality of peer routers being adapted to provide failover capability for the at least one of the other peer routers, the system comprising:

means for sending, from a first peer router, a first Elect Master message to at least one other peer router;

the first Elect Master message including information relating to characteristics associated with the first peer router, said characteristics including an identity and an address associated with the first peer router;

means for receiving, at the first peer router, a second Elect Master message from a second peer router;

the second Elect Master message including information relating to characteristics associated with the second peer router, said characteristics including an identity and an address associated with the second peer router;

means for populating a local Peer Resource Assignment Table with information obtained from received Elect Master messages; and

means for determining an identity of a master peer router using information obtained from the local Peer Resource Assignment Table.

26. A system for performing resource allocation among a plurality of peer routers in a private network, the plurality of peer routers being adapted to provide connectivity between nodes in the private network and nodes in a public network, at least a first portion of the plurality of peer routers being adapted to perform network address translation (NAT) for traffic flowing between the public and private networks, at least a second portion of the plurality of peer routers being adapted to provide failover capability for the at least one of the other peer routers, the system comprising:

means for generating, at a first peer router, a local Peer Resource Assignment Table which includes NAT resource assignment information relating to selected global address assignments and selected global port assignments allocated to selected peer routers;

said NAT resource assignment information including first peer router information relating to global address assignments and selected global port assignments allocated to the first peer router;

means for receiving a first packet relating to a first flow between a private network node and a public network node;

means for allocating, using the first peer router information, a selected global address and a selected global port for the first flow;

means for creating a first NAT entry associated with the first flow, the first NAT entry including information relating to the selected global address and the selected global port allocated for the first flow;

means for sending at least one NAT Entry Update message to at least one other peer router; and

wherein the at least one NAT Entry Update message includes information relating to the first NAT entry.

27. A system for performing resource allocation among a plurality of peer routers in a private network, the plurality of peer routers being adapted to provide connectivity between nodes in the private network and nodes in a public network, at least a first portion of the plurality of peer routers being adapted to perform network address translation (NAT) for traffic flowing between the public and private networks, at least a second portion of the plurality of peer routers being adapted to provide failover capability for the at least one of the other peer routers, the system comprising:

means for generating, at a first peer router, a local Peer Resource Assignment Table which includes NAT resource assignment information relating to selected global address assignments and selected global port assignments allocated to selected peer routers;

said NAT resource assignment information including first peer router information relating to global address assignments and selected global port assignments allocated to the first peer router;

means for receiving a NAT Entry Update message from a second peer router, the NAT Entry Update message including information relating to a selected global address and a selected global port allocated for a first NAT entry;

means for reserving the selected global address and the selected global port associated with the first NAT entry; and

means for updating a local NAT Table with information relating to the first NAT entry.