(12) United States Patent
`US 7,032,242 B1
`(10) Patent No.:
`(45) Date of Patent:
`Grabelsky et al.
`Apr. 18, 2006
`
`US007032242B1
`
`METHOD AND SYSTEM FOR DISTRIBUTED
`NETWORK ADDRESS TRANSLATION WITH
`NETWORK SECURITY FEATURES
`
`FOREIGN PATENT DOCUMENTS
`
`W0
`
`WO 01/31888
`
`5/2001
`
`(54)
`
`(75)
`
`Inventors: David Grabelsky, Skokie, IL (US);
`Michael S. Borella, Naperville, IL
`(US); Ikhlaq Sidhu, Vernon Hills, IL
`(US); Danny M. Nessett, Fremont, CA
`(US)
`
`(73)
`
`Assignee: 3Com Corporation, Marlborough, MA
`(US)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21)
`
`Appl. No.: 09/270,967
`
`(22)
`
`Filed:
`
`Mar. 17, 1999
`
`(63)
`
`(51)
`
`(52)
`
`(58)
`
`(56)
`
`Related US. Application Data
`
`Continuation-in-part of application No. 09/035,600,
`filed on Mar. 5, 1998, now Pat. No. 6,353,614.
`
`Int. Cl.
`H04K 1/00
`H04L 9/00
`G06F 15/16
`
`(2006.01)
`(2006.01)
`(2006.01)
`
`726/11; 726/3; 726/12;
`..............................
`US. Cl.
`726/26; 713/151; 713/153; 713/168; 709/201;
`709/225; 709/229; 380/28; 380/270
`
`Field of Classification Search ................ 713/201;
`370/351, 356, 389
`See application file for complete search history.
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,953,198 A
`5,159,592 A
`
`8/1990 Daly et al. .................... 379/61
`10/1992 Perkins
`
`(Continued)
`OTHER PUBLICATIONS
`
`Internet
`Internet Engineering Task Force,
`G. Montene,
`Draft, “Negotiated Address Reuse” (NAR), <draft-montene-
`gro-aatn-nar-00.txt>, May 1998, pp. 1 to 22.
`
`(Continued)
`
`Primary Examiner4ilberto Barron, Jr.
`Assistant ExamineriA. Nobahar
`
`(74) Attorney, Agent, or FirmiMcDonnell Boehnen
`Hulbert & Berghoif LLP
`
`(57)
`
`ABSTRACT
`
`A method and system for distributed network address trans-
`lation with security features. The method and system allow
`Internet Protocol security protocol (“IPsec”) to be used with
`distributed network address translation. The distributed net-
`work address translation is accomplished with IPsec by
`mapping a local Internet Protocol (“IP”) address of a given
`local network device and a IPsec Security Parameter Index
`(“SPI”) associated with an inbound IPsec Security Associa-
`tion (“SA”) that terminates at the local network device. A
`router allocates locally unique security values that are used
`as the IPsec SPIs. A router used for distributed network
`address translation is used as a local certificate authority that
`may vouch for identities of local network devices, allowing
`local network devices to bind a public key to a security name
`space that combines a global IP address for the router with
`a set of locally unique port numbers used for distributed
`network address translation. The router issues security cer-
`tificates and may itself be authenticated by a higher certifi-
`cate authority. Using a security certificate, a local network
`device may initiate and be a termination point of an IPsec
`security association to virtually any other network device on
`an IP network like the Internet or an intranet. The method
`and system may also allow distributed network address
`translation with security features to be used with Mobile IP
`or other protocols in the Internet Protocol suite.
`
`(Continued)
`
`33 Claims, 22 Drawing Sheets
`
`
`
`2
`ROUTER 5
`20
`10.0.“ imp). 0.30
`
` SOHO LAN
`30
`
`192.200.20.11
`
`0001
`
`EX. 1005
`
`Apple v. MPH Techs. Oy
`IPR2019-00822
`
`Ex. 1005
`Apple v. MPH Techs. Oy
`IPR2019-00822
`
`0001
`
`

`

`US 7,032,242 B1
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`............... 370/352
`............... 379/58
`
`Ikhlaq Sidhu, Brian
`Michael Borella, DaVid Grabelsky,
`Petry,
`Internet Engineering Task Force,
`Internet Draft,
`“Distributed Network Address Translation,” <draft-b0rella-
`aatn-dnat-01.txt>, Oct. 1998, pp. 1 to 21.
`P. Srisuresh, G. Tsirsis, P. Akkiraju, A. Heffeman, Internet
`Engineering Task Force, Internet Draft, “DNS Extensions tO
`Network Address Translators” (DNSiALG), <draft-ietf-
`nat-dns-01.txt>, Oct. 1998, pp. 1 to 24.
`P. Srisuresh, Internet Engineering Task Force, Internet Draft
`“Security for
`IP Network Address Translator
`(NAT)
`Domains,” <draft-ietf-nat-security-00.txt.>, NOV. 1998, pp.
`1 tO 11.
`
`Internet Engineering Task Force,
`P. Srisuresh, K. Eg,
`Internet Draft, “The IP Network Address Translator” (NAT),
`<draft-rfced-infO-srisuresh-05.txt>, Feb. 1998, pp. 1 to 24.
`P. Srisuresh, K. EgeV, Internet Engineering Task Force,
`Internet Draft, “Traditional IP Network Address Translator
`(Traditional NAT),” <draft-ietf-nat-traditional-O1.txt>, Oct.
`1998, pp. 1 to 17.
`Internet Engineering Task
`P. Srisuresh, Matt HOldrege,
`Force,
`Internet Draft, “IP Network Address Translator
`(NAT) Terminology and Consideration,” <draft-ietf-nat-
`terrninOlogy-01.txt>, Oct. 1998, pp. 1 to 28.
`PraVeen Akkiraj u, YakOV Rekhter, Internet Engineering Task
`Force,
`Internet Draft, “A Multihoming Solution Using
`NATs” <draft-akkiraju-nat-multihoming-OO.txt>, NOV. 1998,
`pp. 1 to 32.
`R. G. MOSkOWitZ, Internet Engineering Task Force, Internet
`Draft, “Network Address Translation Issues with IPsec,”
`<draft-mOSkOWitZ-net66-Vpn-00.txt>, Feb. 5, 1998, p. 1 t0 8.
`R. Thay, N. Doraswa and R. Gle, Internet-Engineering-Task
`Force, Internet Draft “IP Security,” <drat-ietf-ipsec-dOC-
`roadmap-02.txt.>, NOV. 1997, pp. 1 to 12.
`T. Hain, Internet Engineering Task Force, Internet Draft,
`“Architectural
`implications Of NAT,” <draft-iab-nat-
`implications-02.txt>, Oct. 1998, pp. 1 to 14.
`WT. TeO, S.W. YeeOW, R. Singh, Internet Engineering Task
`Force,
`Internet Draft,
`“IP Relocation Through Twice
`Network Address Translator,” <draft-ietf-nat-rnat-00.txt>,
`Feb. 1999, pp. 1 to 20.
`WT. TeO, S.W. YeOW, R. Singh, Internet Engineering Task
`Force, Internet Draft, “ReVerse Twice Network Address
`Translators” (RAT), <draft-te0yeOW-mip-rat-01.txt>, Dec.
`1998, pp. 1 to 20.
`WT. TeO, Y. Li, Internet Engineering Task Force, Internet
`Draft, “MObile IP Extension for PriVate Internets Support,”
`<draft-te0yli-mObileip-mVpn-02.txt>, Feb. 1999, pp. 1 to 24.
`YakOV Rekhter, Internet Engineering Task Force, Internet
`Draft, “Implications Of NATs 0n the TCP/IP Architecture,”
`<draft-ietf-nat-arch-implicati0ns-00.txt>, Feb. 1999, pp. 1 t0
`7.
`
`K. EgeVang and P. Francis, “The IP Network Address
`Translator (NAT)”, RFC 1631, Internet Engineering Task
`Force, www.ietf.Org/rfc/rfcl631.txt, May 1994, pp. 1 to 10.
`Borella, Michael, Technology UpdateiProtocol Helps
`Stretch IPv4 Addresses, “Network World”, V01. 17, NO. 3,
`Jan. 17, 2000, p. 43.
`Kent, Stephen, Evaluating Certification Authority Security,
`Aerospace Conference, 1998 IEEE, Online, V01. 4, pp.
`319-327 (Mar. 21-23, 1998).
`Thayer, ROdney, Bulletproof IP With Authentication and
`Encryption IPSec Adds a Layer of Armor to IP, Data
`Communications, V01. 26, NO. 16, pp. 55-58, 60 (NOV. 21,
`1997).
`Borella, M., Grabelsky, D., LO, J., Tuniguchi, K., Internet
`Engineering Task Force, Internet Draft, “Realm Specific IP:
`PrOtOCOl
`Specification
`<draft-ietf-nat-rsip-prOtOCOl-.06.
`txt>”, Mar. 2000, pp. 1-48.
`
`0002
`
`7/1993 Vacon et al.
`5,227,778 A
`............. 364/717
`7/1994 Fujisaki et al.
`5,327,365 A
`
`3/1996 Bernard .............
`364/705.5
`5,497,339 A
`............. 370/60.1
`6/1996 Henley et al.
`5,526,353 A
`6/1996 Nilakantan et al.
`5,526,489 A
`8/1996 Gelb
`5,550,984 A
`2/1997 Iwami et al.
`5,604,737 A
`2/1997 Register et al.
`5,606,594 A
`6/1997 Fox et al.
`5,636,216 A
`8/1997 Koyama ..................... 370/355
`5,654,957 A
`1/1998 Toth et al.
`5,708,655 A
`4/1998 Civanlar et al.
`............ 370/352
`5,737,333 A
`4/1998 Baratz et al.
`370/356
`5,742,596 A
`
`5/1998 Nakazawa .................. 370/401
`5,754,547 A
`8/1998 Nemoto ................. 364/717.01
`5,793,657 A
`8/1998 Mayes et al.
`5,793,763 A
`9/1998 Rodwin et 31.
`5,812,819 A
`5,828,846 A * 10/1998 Kirby et al.
`370/351
`
`
`5,835,723 A
`11/1998 Andrews et al.
`395/200.56
`
`5,862,331 A
`1/1999 Herriot
`...........
`395/200.49
`...... 370/352
`5,867,495 A
`2/1999 Elliott et al.
`
`5,867,660 A
`2/1999 Schmidt et al.
`5,872,847 A
`2/1999 Boyle et 31.
`.......... 370/352
`5,889,774 A
`3/1999 Mirashrafi et al.
`5,892,924 A
`4/1999 Lyon et al.
`............ 395/200.75
`5,915,008 A
`6/1999 Dulman ...................... 379/201
`5,933,778 A
`8/1999 Buhrmann et al.
`......... 455/461
`5,950,195 A
`9/1999 Stockwell et al.
`5,968,176 A * 10/1999 Nessett et al.
`.............. 713/201
`5,983,350 A *
`11/1999 Minear et al.
`.............. 713/201
`6,011,782 A
`1/2000 DeSimone et 31.
`6,055,236 A
`4/2000 Nessett et al.
`6,055,561 A
`4/2000 Feldman et al.
`6,058,421 A
`5/2000 Fijolek et al.
`6,079,021 A
`6/2000 Abadi et 31.
`6,101,189 A
`8/2000 Tsuruoka .................... 370/401
`6,101,543 A
`8/2000
`.. 709/229
`6,104,711 A
`8/2000
`370/352
`6,115,751 A
`9/2000
`709/240
`6,134,591 A
`10/2000
`370/352
`6,137,791 A
`10/2000
`709/223
`6,157,950 A
`12/2000
`370/466
`..
`6,172,986 B1
`1/2001 Watanuki et al.
`370/230
`.
`6,185,184 B1
`2/2001 Mattaway et al.
`
`6,195,705 B1
`2/2001 Leung ........................ 709/245
`6,212,183 B1
`4/2001 Wilford ...................... 370/392
`6,212,563 B1
`4/2001 Beser ................
`709/227
`6,249,820 B1
`6/2001 Dobbins et al.
`709/238
`6,266,707 B1
`7/2001 Boden et al.
`709/245
`6,269,099 B1
`7/2001 Borella et al.
`370/389
`..
`6,353,614 B1
`3/2002 Borella et al.
`370/389
`..
`6,353,891 B1
`3/2002 Borella et al.
`.............. 713/201
`6,438,612 B1 *
`8/2002 Ylonen et al.
`.............. 709/249
`6,510,513 B1*
`1/2003 Danieli ....................... 713/156
`
`............ 709/200
`.............. 709/225
`
`
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`W0
`
`WO 01/31888 A1
`
`5/2001
`
`OTHER PUBLICATIONS
`
`George Tsirtis, Alan O’Neill, Internet Engineering Task
`Force, Internet Draft, “NAT Bypass for End 2 End ‘Sensi-
`tiVe’ Applications,” <draft-tsirtsis-nat-bypass-00.txt>, Jan.
`1998, pp. 1 t0 5.
`George Tsirtis, Pyda Srishuresh, Internet Engineering Task
`Force,
`Internet
`Draft,
`“Network
`Address
`TranslationiPrOtOCOl Translation” (NAT-PT), <draft-ietf-
`ngtrans-natpt-04.txt>, Jan. 1999, pp. 1 to 13.
`Jeffrey LO, K, Taniguchi, Internet Engineering Task Force,
`Internet Draft, “IP Host Network Address (and port) Transla-
`tion,” <draft-ietf-hnat-00.txt>, NOV. 1998, pp. 1 to 13.
`
`0002
`
`

`

`US 7,032,242 B1
`
`Page 3
`
`Borella, M., Grabelsky, D., Lo, J ., Tuniguchi, K., Internet
`Engineering Task Force, Internet Draft, “Realm Specific IP:
`Procotol
`Specification
`<draft-ietf-nat-rsip-protocol-.07.
`txt>”, Jul. 2000, pp. 1-49.
`Montenegro, G., Internet Engineering Task Force, Internet
`Draft, “RSIP Support for End-to-End IPsec,” <draft-ietf-nat-
`rsip-ipsec-04.txt>, Jul. 2000, pp. 1 to 17.
`Borella, M., Lo, J ., Grabelsky, D., Montenegro, G., Internet
`Engineering Task Force, Internet Draft, “Realm Specific IP:
`Framework <draft-ietf-nat-rsip-framework-05.txt>”,
`Jul.
`2000, pp. 1-30.
`Borella, M., Montenegro, G., RSIP: Address Sharing with
`End-to—End Security, USENIX Conference, San Francisco,
`California, Mar. 9, 2000, pp. 1-9.
`Handley, M., et al., SIP: Session Initiation Protocol,
`Network-Working Group, Request for Comments 2543,
`Mar. 1999, pp. 1 to 153.
`ITU-T Recommendation H.225.0, Call Signaling Protocols
`and Media Stream Packetization for Packet—Based
`Multimedia Communication Systems, Series H: Audiovisual
`and Multimedia Systemsilnfrastructure of Audiovisual
`ServicesiTransmission Multiplexing and Synchronization,
`(Feb., 1998).
`ITU-T Recommendation H.323, Packet-Based Multimedia
`Communications Systems, Series H: Audiovisual and
`Multimedia
`Systemsilnfrastructure
`of Audiovisual
`ServicesiSystems and Terminal Terminal Equipment for
`Audiovisual Services, (Feb. 1998).
`McCanne
`et
`al.,
`“The BSD Packet Filter: A New
`Architecture for User-Level Packet Capture,” Proceedings
`of the 1993 Winter USENIX Technical Conference (Jan.
`1993).
`Postel, J ., User Datagram Protocol , Request for Comments
`768, Aug. 1980, pp. 1 to 3.
`Postel, J ., Internet Protocol, Request for Comments 791,
`Sep. 1981, pp. 1 to 45.
`Postel J., Internet Control Message Protocol, Request for
`Comments 792, Sep. 1981, pp. 1 to 21.
`Postel, J., Transmission Control Protocol, Request for Com-
`ments 793, Sep. 1981, pp. i to 84.
`Postel, J ., File Transfer Protocol (FTP), Request for Com-
`ments 959, Oct. 1985, pp. 1 to 69.
`Jacobson, V., TCP Extensions for High Performance,
`Request for Comments 1323, May 1992, pp. 1 to 37.
`Droms, R., Dynamic Host Configuration Protocol, Request
`for Comments 2131, Mar. 1997, pp. 1 to 45.
`Stevens, W., Advanced Sockets API for IPv6, Request for
`Comments 2292, Feb. 1998, pp. 1 to 67.
`Gilligan, R. et al., Basic Socket Interface Extensions for
`IPv6, Request for Comments 2553, Mar. 1999, pp. 1 to 41.
`Srisuresh, P.,et al., IP Network Address Translator(NAI)
`Terminology and Considerations, Request for Comments
`2663, Aug. 1999, pp. 1 to 30.
`Maurice J. Bach, The Design of the Unix Operating System,
`Prentice Hall Software Series, 1986, pp. 382-390.
`Durand, Alain, Deploying Ipv6, IEEE Internet Computing,
`http://computer.org/intemet, Jan-Feb. 2001, pp. 79-81.
`3COM SIP Sloutions 1.0 benefits brochure. (4 total pages).
`Sidhu, Ikhlaq and Bezaitis, Andrew, Eat or be eaten, www.
`americasnetwork.com/issues/99issues/991101/991191ieat.
`htm, printed May 10, 2000. (6 total pages).
`Myers, Brad A.; Stiel, Herb; and Gargiulo, Robert, Col-
`laboration Using Multiple PDAs Connected to a PC,
`Proceedings of the ACM 1998 conference on Computer
`
`supported cooperative work, Nov. 14-18, 1998, Seattle, WA.
`(total 11 pages).
`Dalgic,
`Ismail; Borella, Michael; Dean, Rick; Grabiec,
`Jacek; Mahler, Jerry; Schuster, Guido; and Sidhu, Ikhlaq,
`True Number Portability and Advanced Call Screening in a
`SIP-Based IP Telephony System, IEEE Communications
`Magazine, vol. 37, No. 7, Jul. 1999, pp. 96-101. (8 total
`pages).
`Session
`SIP:
`Handley/Schulzrinne/Schooler/Rosenberg,
`Initiation Protocol, Internet Engineering Task Force, draft-
`ietf-sip-rfc2543bis-02.ps. Sep. 4, 2000. (131 pages).
`Borella, M., Lo., J., Grabelsky, D., Montenegro, G., IETF
`Proceedings presentation, Realm Specific IP: Protocol
`Specification <draft-nat-rsip-protocol-00.txt>, Apr. 9, 1999
`(13 pages).
`Marsan, Carolyn Duffy, The Next Best Things to Ipv6?
`Network World Fusion at http://www.nbwfusion.com/news/
`1999/0920ipv6.html, Mar. 29, 2000, pp. 1-3.
`Borella, M., Lo, J ., Grabelsky, D., Montenegro, G., Internet
`Engineering Task Force, Internet Draft, “Realm Specific IP:
`Framework <draft-ietf-nat-rsip-framework-.04.txt>”, Mar.
`2000, pp. 1-30.
`IETF Mar. 1999 Proceedings, 2.7.10 Network Address
`Translators (nat), pp. 1-13.
`Rosenberg, Jonathan D. and Shockey, Richard, The Session
`Initiation Protocol (SIP): A Key Component for Internet
`Telephony, ComputerTelephony.com, Jun. 2000, pp. 124-
`139.
`Fenner, W., Internet Group Management Protocol Version 2,
`RFC 2236, Nov. 1997, pp. 1-24.
`Mogul, J. et al., “Internet Standard Subnetting Procedure”,
`RFC 950, Aug., 1985, pp. 1-18.
`Schulzrinne et al., “RTP: A Transport Protocol for Real—
`Iime Applications”, RFC 1889, pp. 1-75.
`Privat Jermone, “Double Phase DHCP Configuration ”,
`<draft-privat-dhc-doublephase-01.txt>,
`Internet Engineer-
`ing Task Force, Sep. 1999, pps. 1-4.
`Maughan, D. et al., “Internet Security Association and Key
`Management Protocol”, RFC 2408, Nov. 1998, pps. 1-86.
`Karn, P., “Photuris Session—Key Management Protocol”,
`RFC-2522, Mar. 1999, pps. 1-58.
`“Random Number Generators”, Computational Science
`Education Projects, 1991, 1992, 1993, 1994, and 1995.
`Foster, Ian, “10 Random Numbers”, 1995.
`Borella, Michael et al., “Realm Specific IP: Protocol
`Specification ”, <draft-ietf.nat-rsip-protocol-02.txt>, Internet
`Draft, Aug. 1999, pps. 1-27.
`Gilligan, R. et al., “Transition Mechanisms for IPv6 Hosts
`and Routers”, RFC 1933, Apr. 1996, pps. 1-22.
`Afifi, H. et al., “Methodfor IPv4—IPV6 Transition”, Proceed-
`ings IEEE International Symposium on Computers and
`Communications, Jul. 6-8, 1999, pps. 478-484.
`“Cisco IOS Release 12.0 Network Protocols Configuration
`Guide, Part. 1”, Configuring IP Addressing, Cisco Systems,
`1998, pp. P1C-7 to P1C-58.
`International Search Report for PCT Application Serial No.
`PCT/US00/07057, Dated Aug. 9, 2000.
`“Cisco IOS Release 12.0 Network protocols Configuration
`Guide, Part 1”, Configuring IP Addressing, CISCO Systems,
`1998, pp. P1C-7 to PiC-58.
`International Search Report for PCT Application Serial No.
`PCT/US00/07057, Dated Aug. 9, 2000.
`
`* cited by examiner
`
`0003
`
`0003
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 1 of 22
`
`US 7,032,242 B1
`
`FIG. 1
`
`/1°
`
`{"3633}"""€010.03""'1'0.'6.'0T5"""""E
`=
`:
`Ii]
`PRINTER
`PC
`E
`_,__
`=
`E:
`: -:
`I
`““ 13
`5 PC
`
`14
`
`16
`
`=
`'
`I
`E
`5
`
`
`
`.
`%
`
`A
`
`I
`
`l
`
`E
`:
`E
`255
`3
`2::
`ROUTER!
`:198. 0.20.30
`10.0.0.7 :
`g
`g
`
`28
`
`32
`
`30
`
`i" """ '"‘\
`i
`: 34
`=
`:
`E
`E40
`: -__ 5
`——||— :
`.
`5
`:
`I
`: 38
`
`i
`:
`I
`i
`L--
`
`36
`
`39
`
`-
`192200203
`
`SOHO LAN
`
`‘3
`12
`
`0004
`
`0004
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 2 of 22
`
`US 7,032,242 B1
`
`FIG. 2
`
`PROTOCOL STACK
`
`/
`
`PROGRAMS
`
`APPLICATION
`
`NETWORK INTERFACE CARD DEVICE DRIVERS
`
`0005
`
`0005
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 3 of 22
`
`US 7,032,242 B1
`
`FIG. 3
`PORT ALLOCATION PROTOCOL (PAP)
`
`64
`
`J
`
`
`PAP REQUEST
`MESSAGE
`
`66
`
`
`
`PAP SECURITY
`
`REQUEST MESSAGE
`67
`
`
`PAP RESPONSE MESSAGE
`68
`
`
`
`PAP SECURITY
`RESPONSE MESSAGE
`
`68
`
`
`
`70
`PAP INVALIDATE MESSAGE
`
`
` PAP SECURITY
`INVALIDATE MESSAGE
`71
`
`
` COMBINATION NETWORK ADDRESS (COMMON EXTERNAL
`
` 72
`
`
`NETWORK ADDRESS/LOCALLY UNIQUE PORT)
`
`0006
`
`0006
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 4 of 22
`
`US 7,032,242 B1
`
`PAP REQUEST MESSAGE LAYOUT
`
`
`78
`
`/
`
`REQUESTED
`
`
`
`84
`82
`
`
`
`
`
`
`4 BYTES
`
`FIG. 5
`PAP RESPONSE MESSAGE9LAYOUT
`
`
`
`
`88
`
`CODE
`
`CHEC KSUM
`
`TOTAL
`
`85
`
`/
`
`
`
`
`
`96
`98
`94
`
`
`4 BYTES
`
`FIG. 6
`PAP INVALIDATE MESSAGE LAYOUT
`
`
`
`
`104
`
`100
`/
`
`
`
`
`
`
`
`4 BYTES
`
`0007
`
`0007
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 5 of 22
`
`US 7,032,242 B1
`
`FIG. 4A
`
`PAP SECURITY REQUEST MESSAGE LAYOUT
`77
`7
`
`
`
`9
`
`
`
`75
`
`
`
`73
`/
`
`
`
`
`
`REQUESTED
` 81
`
`V
`83
`
`
`
`
`4 BYTES
`
`85
`
`
`
`87
`
`
`
`89
`
`9 1
`
`FIG. 5A
`PAP SECURITY RESPONSE MESSAGE LAYOUT /
`
`
`CODE
`
`CHECKSUM
`
`
`
`
`
`93
`
`
`
`
`T°TAL””MBER°FSE°”R"YmVALUES RETURNED
`LOWEST LOCALLY UNIQUE SECURITY VALUE
`
`95
`
`4 BYTES
`
`FIG. 6A
`PAP SECURITY INVALIDATE MESSAGE LAYOUT
`
`97
`
`99
`
`
`
`101
`
`
`
`103
`
`CODE
`
`1
`
`os
`
`
`
`CHECKSUM
`
`LOCALLY UNIQUE SECURITY VALUE
`
`
`
`
`
`107
`
`
`
`
`
`
`4 BYTES
`
`0008
`
`0008
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 6 of 22
`
`US 7,032,242 B1
`
`FIG. 7
`
`114 COMBINATION NETWORK ADDRESS
`
`"2
`116 /
`
`EXTERNAL NETWORK ADDRESS
`
`LOCALLY UNIQUE
`
`(E.G., EXTERNAL IP ADDRESS)
`
`PORT
`
`198.10.20.30
`
`FIG. 8
`
`"8
`/
`
`124—». E4— 120 —>.<—— 122
`
`INTERNAL
`
`
`
` LOWEST PORT NUMBER OF PORTS
`NETWORK
`
`ADDRESS
`
`
`
`PORT-TO-lNTERNAL-N ETWORK
`ADDRESS TABLE
`
`0009
`
`0009
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 7 of 22
`
`US 7,032,242 B1
`
`FIG. 9
`START
`
`130
`/
`
`REQUEST ONE OR MORE LOCALLY UNIQUE PORTS ON A
`
`FIRST NETWORK DEVICE ON A FIRST NETWORK FROM A
`
`SECOND NETWORK DEVICE ON THE FIRST NETWORK
`
`USING A FIRST PROTOCOL
`
`132
`
`RECEIVE ONE OR MORE LOCALLY UNIQUE PORTS FROM
`
`THE SECOND NETWORK DEVICE ON THE FIRST NETWORK
`
`DEVICE USING THE FIRST PROTOCOL.
`
`134
`
`135
`
`REPLACE ONE OR MORE DEFAULT OR EPHEMERAL PORTS
`
`IN A PROTOCOL LAYER IN A LAYERED PROTOCOL STACK
`WITH ONE OR MORE LOCALLY UNIQUE PORTS
`
`CONSTRUCT A COMBINATION NETWORK ADDRESS USING A
`
`LOCALLY UNIQUE PORT AND A COMMON EXTERNAL
`
`NETWORK ADDRESS FOR COMMUNICATING WITH A
`
`
`
`
`
`SECOND EXTERNAL NETWORK WITHOUT NETWORK
`ADDRESS TRANSLATION
`
`
`138
`
`0010
`
`0010
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 8 of 22
`
`US 7,032,242 B1
`
`FIG. 10
`START
`
`140
`/
`
`
`
`SEND A REQUEST FOR A SECOND EXTERNAL NETWORK
`WITH A COMBINATION NETWORK ADDRESS FROM A FIRST
`
`
`NETWORK DEVICE ON A FIRST NETWORK TO A SECOND
`
`NETWORK DEVICE ON THE FIRST NETWORK
`
`142
`
`144
`
`146
`
`148
`
`ROUTE THE REQUEST FROM THE SECOND NETWORK
`
`
`
`DEVICE TO THE SECOND EXTERNAL NETWORK
`
`RECEIVE A RESPONSE ON THE SECOND NETWORK DEVICE
`
`
`
`ON THE FIRST NETWORK FROM THE EXTERNAL SECOND
`NETWORK AT THE COMMON EXTERNAL NETWORK
`ADDRESS FROM THE COMBINATION NETWORK ADDRESS
`
`
`
`
`
`
`DEVICE ON THE FIRST NETWORK USING A LOCALLY
`
`ROUTE THE RESPONSE FROM THE SECOND NETWORK
`
`DEVICE ON THE FIRST NETWORK TO THE FIRST NETWORK
`
`UNIQUE PORT FROM COMBINATION NETWORK ADDRESS
`
`0011
`
`0011
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 9 of 22
`
`US 7,032,242 B1
`
`152
`
`154
`
`DEFAULT PORT
`
`TRANSLATED PORT
`
`FIG. 11
`150
`SOURCE PORT TRANSLATION TABLE
`(SPTT)
`/
`
`
`
`TIMESTAMP
`
`
`
`158
`
`
`
`
`
`PROTOCOL
`
`156
`
`FIG. 12
`IP ADDRESS TRANSLATION TABLE
`162
`(IPATT)
`
`
`
`
`
`DESTINATION PORT
`
`INTERNAL DESTINATION
`[p ADDRESS
`
`PROTOCOL
`
`TIMESTAMP
`
`1 66
`
`168
`
`1
`
`64
`
`160
`/
`
`
`
`
`
`0012
`
`0012
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 10 of 22
`
`US 7,032,242 B1
`
`FIG. 13
`
`m
`
`
`
`
`LAYER
`
`172
`
`RECEIVE A DATA PACKET ON A NETWORK INTERFACE
`
`
`CARD DEVICE DRIVER IN A LINK LAYER FROM A NETWORK
`
`
`
`
`EXTERNAL DESTINATION
`IP ADDRESS?
`
`”0
`
`NO PORT TRANSLATION IS
`
`PERFORMED
`
`
`178
`180
`
`ADD OUTER IP HEADER WITH SOURCE IP ADDRESS SET TO
`
`NETWORK DEVICE'S INTERNAL IP ADDRESS AND
`
`DESTINATION SET TO ROUTER'S INTERNAL IP ADDRESS
`
`176
`
`TRANSLATE DEFAULT SOURCE PORT IN INNER IP HEADER
`
`INTO A LOCALLY UNIQUE PORT FOR THE NETWORK
`DEVICE USING A SPTT
`
`TRANSMIT PACKET WITH OUTER IP HEADER TO NETWORK
`
`HARDWARE
`
`0013
`
`0013
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 11 of 22
`
`US 7,032,242 B1
`
`FIG. 14
`
`184
`
`RECEIVE A DATA PACKET ON A NETWORK INTERFACE
`
`CARD DEVICE DRIVER IN A LINK LAYER FROM NETWORK
`
`INTERFACE HARDWARE
`
`186
`
`EXTERNAL SOURCE
`IP ADDRESS?
`
`”0
`
`
`
`
`YES ADDRESS TO INNER SOURCE IP
`ADDRESS
`
`
`COPY OUTER SOURCE IP
`
`TRANSLATE SOURCE PORT FROM INNER IP HEADER TO
`
`LOCALLY UNIQUE PORT USING A SPTT
`
`190
`
`194
`
`STRIP OFF OUTER IP HEADER
`
`192
`
`FORWARD PACKET TO NETWORK LAYER
`
`0014
`
`0014
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 12 of 22
`
`US 7,032,242 B1
`
`FIG. 15
`
`IP HEADER FORMAT
`
`TOTAL
`
`200
`
`/
`
`IDENTIFICATION
`m
`
`TIME-TO-LIVE
`
`PROTOCOL
`
`m
`
`m
`
`LENGTH
`
`M
`
`FRAGMENT OFFSET
`m
`
`HEADER
`
`CHECKSUM
`
`m
`
`L25
`
`SOURCE ADDRESS
`
`Z_2_Q
`
`DESTINATION ADDRESS
`
`&
`
`OPTIONS
`
`0015
`
`0015
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 13 of 22
`
`US 7,032,242 B1
`
`FIG. 16
`
`AH HEADER FORMAT
`
`226
`
`/
`
`NEXT
`HEADER
`m
`
`PAYLOAD
`LENGTH
`M
`
`RESERVED
`22
`
`218
`
`SECURITY PARAMETER INDEX ("SPI"
`M
`
`SEQUENCE NUMBER FIELD
`
`236
`
`AUTHENTICATION DATA
`
`0016
`
`0016
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 14 of 22
`
`US 7,032,242 B1
`
`FIG. 17
`
`ESP HEADER FORMAT
`
`24°
`/
`
`SECURITY PARAMETERS INDEX (“SPI”)
`m
`
`SEQUENCE NUMBER
`
`2%
`
`PAYLOAD DATA (VARIABLE)
`m
`
`2&1.
`
`PADDING (VARIABLE)
`fl
`
`PAD LEN
`&
`
`NEXT HEADER
`21E
`
`AUTHENTICATION DATA
`
`0017
`
`0017
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 15 of 22
`
`US 7,032,242 B1
`
`FIG. 18
`
`
`
`0018
`
`0018
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 16 of 22
`
`US 7,032,242 B1
`
`FIG. 19
`
`START
`
`2,4
`
`REQUEST ONE OR MORE LOCALLY UNIQUE SECURITY
`
`VALUES ON A FIRST NETWORK DEVICE ON A FIRST
`
`
`
`
`
`NETWORK FROM A SECOND NETWORK DEVICE ON THE
`
`FIRST NETWORK USING A FIRST PROTOCOL
`276
`
`
`
`
`
`RECEIVE ONE OR MORE LOCALLY UNIQUE SECURITY
`VALUES FROM THE SECOND NETWORK DEVICE ON THE
`
`
`FIRST NETWORK DEVICE USING THE FIRST PROTOCOL
`2 87
`
`
`
`STORE THE ONE OR MORE LOCALLY UNIQUE SECURITY
`VALUES ON THE FIRST NETWORK DEVICE FOR USE WITH A
`SECOND SECURE PROTOCOL
`
`
`
`280
`
`0019
`
`0019
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 17 of 22
`
`US 7,032,242 B1
`
`FIG. 20
`
`282
`/
`
`RECEIVE A REQUEST MESSAGE WITH A FIRST PROTOCOL
`
`ON A SECOND NETWORK DEVICE FOR ONE OR MORE
`
`LOCALLY UNIQUE SECURITY VALUES FROM A FIRST
`
`NETWORK DEVICE
`
`ALLOCATE ONE OR MORE LOCALLY UNIQUE SECURITY
`
`
`
` 284
`VALUES ON THE SECOND NETWORK DEVICE 286
`
`
`
` 288
`
`
`
`STORE A NETWORK ADDRESS FOR THE FIRST NETWORK
`
`DEVICE FROM THE REQUEST MESSAGE IN A TABLE
`
`ASSOCIATED WITH THE SECOND NETWORK DEVICE,
`WHERE THE TABLE IS USED TO MAINTAIN A MAPPING
`
`
`
`
`
`BETWEEN THE ONE OR MORE LOCALLY UNIQUE SECURITY
`
`VALUES AND THE NETWORK ADDRESS FOR THE FIRST
`
`NETWORK DEVICE FOR DISTRIBUTED NETWORK ADDRESS
`
`TRANSLATION
`
`
`MESSAGE WITH THE FIRST PROTOCOL
`
`SEND THE ONE OR MORE LOCALLY UNIQUE SECURITY
`
`VALUES TO THE FIRST NETWORK DEVICE IN A RESPONSE
`
`290
`
`0020
`
`0020
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 18 of 22
`
`US 7,032,242 B1
`
`FIG. 21
`E4—— 294—».4— 296
`
`
`
`292
`298—->:/
`
`INTERNAL
`NETWORK
`ADDRESS
`
`LOWEST SPI
`
`NUMBER OF SPls
`
`"L-
`
`"f"
`300
`
`302
`
`SPI-TO-lNTERNAL-NETWORK ADDRESS
`TABLE
`
`0021
`
`0021
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 19 of 22
`
`US 7,032,242 B1
`
`FIG. 22
`
`304
`
`REQUEST ONE OR MORE LOCALLY UNIQUE PORTS ON A
`
`FIRST NETWORK DEVICE FROM A SECOND NETWORK
`
`DEVICE
`
`SECURE VIRTUAL CONNECTION
`
`REQUEST ONE OR MORE LOCALLY UNIQUE SECURITY
`
`VALUES ON THE FIRST NETWORK DEVICE FROM THE
`
`SECOND NETWORK DEVICE
`
`RECEIVE A SECURITY CERTIFICATE FROM THE SECOND
`
`NETWORK DEVICE ON THE FIRST NETWORK DEVICE,
`WHERE THE SECURITY CERTIFICATE IS USED TO CREATE A
`
`0022
`
`0022
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 20 of 22
`
`US 7,032,242 B1
`
`FIG. 23
`
`m
`
`SEND ONE OR MORE LOCALLY UNIQUE PORTS TO A FIRST
`
`NETWORK DEVICE FROM A SECOND NETWORK DEVICE
`
`314
`
`SEND ONE OR MORE LOCALLY UNIQUE SECURITY VALUES
`
`FROM THE SECOND NETWORK DEVICE TO THE FIRST
`NETWORK DEVICE
`
`316
`
`SECURE VIRTUAL CONNECTION
`
`SEND A SECURITY CERTIFICATE FROM THE SECOND
`
`NETWORK DEVICE TO THE FIRST NETWORK DEVICE,
`WHERE THE SECURITY CERTIFICATE IS USED TO CREATE A 313
`
`0023
`
`0023
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 21 of 22
`
`US 7,032,242 B1
`
`FIG. 24
`START
`
`m
`/
`
`322
`
`324
`
`326
`
`RECEIVE A FIRST MESSAGE IN A SECOND SECURE
`
`PROTOCOL ON FIRST NETWORK DEVICE TO ESTABLISH A
`
`SECURE VIRTUAL CONNECTION To THE FIRST NETWORK
`DEVICE FROM A THIRD NETWORK DEVICE ON A SECOND
`EXTERNAL NETWORK
`
`SELECT A LOCALLY UNIQUE SECURITY VALUE FOR THE
`
`SECURE CONNECTION FROM A LIST OF LOCALLY UNIQUE
`
`SECURITY VALUES STORED ON THE FIRST NETWORK
`DEVICE
`
`THE SECOND NETWORK DEVICE
`
`SEND A SECOND MESSAGE IN THE SECOND SECURE
`
`PROTOCOL FROM THE FIRST NETWORK DEVICE TO
`
`ESTABLISH A SECURE VIRTUAL CONNECTION TO THE
`
`FIRST NETWORK DEVICE FROM THE THIRD NETWORK
`
`DEVICE, WHERE THE SECOND MESSAGE INCLUDES THE
`LOCALLY UNIQUE SECURITY VALUE AND A SECURITY
`
`CERTIFICATE SENT TO THE FIRST NETWORK DEVICE FROM
`
`0024
`
`0024
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 22 of 22
`
`US 7,032,242 B1
`
`FIG. 25
`START
`
`328
`/
`
`SEND A REQUEST FROM A FIRST NETWORK DEVICE ON A
`
`FIRST NETWORK TO A SECOND NETWORK DEVICE ON A
`
`FIRST NETWORK FOR A THIRD NETWORK DEVICE ON AN
`EXTERNAL SECOND NETWORK, WHERE THE REQUEST
`INCLUDES SECURITY INFORMATION
`
`33°
`
`ROUTE THE REQUEST FROM THE SECOND NETWORK
`DEVICE TO THE THIRD NETWORK DEVICE
`
`RECEIVE A RESPONSE MESSAGE ON THE SECOND
`
`NETWORK DEVICE FROM THE THIRD NETWORK DEVICE
`
`WHERE THE RESPONSE INCLUDES SECURITY
`INFORMATION FROM THE REQUEST
`
`334
`
`332
`336
`
`ROUTE THE RESPONSE MESSAGE FROM THE SECOND
`
`NETWORK DEVICE TO THE FIRST NETWORK DEVICE USING
`
`LOCALLY UNIQUE PORTS USED FOR DISTRIBUTED
`
`NETWORK ADDRESS TRANSLATION
`
`0025
`
`0025
`
`

`

`US 7,032,242 B1
`
`1
`METHOD AND SYSTEM FOR DISTRIBUTED
`NETWORK ADDRESS TRANSLATION WITH
`NETWORK SECURITY FEATURES
`
`CROSS REFERENCES TO RELATED
`APPLICATIONS
`
`This application is a Continuation-In-Part of US. appli-
`cation Ser. No. 09/035,600 filed on Mar. 5, 1998 now US.
`Pat. No. 6,353,614.
`FIELD OF INVENTION
`
`This invention relates to computer networks. More spe-
`cifically, it relates to a method and system for distributed
`network address translation with network security features.
`BACKGROUND OF THE INVENTION
`
`The Internet Protocol (“IP”) is an addressing protocol
`designed to facilitate the routing of traffic within a network
`or between networks. The Internet Protocol is used on many
`computer networks including the Internet,
`intranets and
`other networks. Current versions of Internet Protocol such as
`
`Internet Protocol version-4 (“IPv4”) are becoming obsolete
`because of limited address space. With a 32-bit address-
`field, it is possible to assign 232 different addresses, which is
`4,294,967,296, or greater than 4 billion globally unique
`addresses.
`
`However, with the explosive growth of the Internet and
`intranets, Internet Protocol addresses using a 32-bit address-
`field may soon be exhausted. Internet Protocol version-6
`(“IPv6”) proposes the use of a 128-bit address-field for IP
`addresses. However, a large number of legacy networks
`including a large number of Internet subnets will still be
`using older versions for Internet Protocol with a 32-bit
`address space for many years to come.
`Network Address Translation (“NAT”) has been proposed
`to extend the lifetime of Internet Protocol version 4 and
`
`earlier versions of Internet Protocol by allowing subnets to
`exist behind a single or small number of globally unique
`Internet Protocol addresses (see e.g., “The IP Network
`Address Translator”, by P. Srisuresh and K. Egevang, Inter-
`net Engineering Task Force (“IETF”), Internet Draft <draft-
`rfced-info-srisuresh-05.txt>, February 1998). A single glo-
`bal Internet Protocol address is used for communication with
`
`external networks such as the Internet. Internally, a sub-
`network (“subnet”) uses local addressing. Local addressing
`may be either any addressing scheme that is different from
`Internet Protocol addressing, or a non-unique usage of
`Internet Protocol addresses. In either case, local addresses
`on a subnet are not used on the external, global Internet.
`When a device or node using local addressing desires to
`communicate with the external world, its local address is
`translated to a common external Internet Protocol address
`
`used for communication with an external network by a
`network address translation device. That is, network address
`translation allows one or more global Internet Protocol
`addresses to be shared among a larger number of local
`addresses.
`
`There are several problems associated with using network
`address translation to extend the life of the Internet Protocol.
`Network address translation interferes with the end-to-end
`
`routing principle of the Internet that recommends that pack-
`ets flow end-to-end between network devices with changing
`the contents of any packets along a transmission route (see
`e.g. “Routing in the Internet,” by C. Huitema, Prentice Hall,
`1995, ISBN 0-131-321-927).
`
`2
`
`Current versions of network address translation replace a
`local network address in a data packet header with an
`external global network address on outbound traffic, and
`replace an external network address in a data packet header
`with a local network address on inbound traffic. This type of
`address translation is computationally expensive, causes
`security problems by preventing certain types of encryption
`from being used, or breaks a number of existing applications
`in a network that cannot provide network address translation
`(e.g., File Transfer Protocol (“FTP”)).
`Current versions of network address translation may not
`gracefully scale beyond a small subnet containing a few
`dozen nodes or devices because of the computational and
`other resources required. Network address translation poten-
`tially requires support for many different internal network
`protocols be specifically programmed into a translation
`mechanism for external protocols in a network address
`translation device such as a network address translation
`router.
`
`Computational burdens placed on a network address
`translation router may be significant and degrade network
`performance, especially if several network address transla-
`tion-enabled sub-networks share the same network address
`translation router.
`In a worst case scenario, a network
`address translation router translates every inbound and out-
`bound data packet. When network address translation is used
`to translate a Transmission Control Protocol/Internet Proto-
`
`col or User Datagram Protocol/Intemet Protocol data packet,
`the packet’s Internet Protocol, Transmission Control Proto-
`col or User Datagram Protocol checksums are recalculated.
`As is known in the art, Transmission Control Protocol
`(“TCP”) and User Datagram Protocol (“UDP”) are often
`used over IP in computer networks. Transmission Control
`Protocol provides a connection-oriented, end-to-end reliable
`protocol designed to fit into a layered hierarchy of protocols
`that support multi-network applications. User Datagram
`Protocol provides a transaction oriented datagram protocol,
`where delivery and duplicate packet protection are not
`guaranteed.
`When a port in a Transmission Control Protocol or User
`Datagram Protocol header is translated, the packet’s Trans-
`mission Control Protocol or User Datagram Protocol check-
`sums are also recalculated. This further increases the com-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`putational cost of translation in a network address translation
`router.
`
`50
`
`55
`
`60
`
`When an Internet Protocol address or port is translated
`with network address translation, a new length may result
`for the data packet and a possible change in a Transmission
`Control Protocol sequence number. A running sequence
`number offset
`(i.e., a delta) must
`then be maintained
`throughout the remainder of the connection. This delta must
`be applied to future traffic, including acknowledgment num-
`bers further increasing computational time in a network
`address translation router.
`In addition to Transmission Control Protocol or User
`
`Datagram Protocol, a network address translation router
`may also translate network addresses, po