a2) United States Patent
`US 6,633,571 Bl
`(10) Patent No.:
`Oct. 14, 2003
`(45) Date of Patent:
`Sakamotoet al.
`
`
`US006633571B1
`
`(54) VPN COMPOSING METHOD, INTERWORK
`ROUTER, PACKET COMMUNICATION
`METHOD, DATA COMMUNICATION
`APPARATUS, AND PACKET RELAYING
`APPARATUS
`
`(56)
`
`(75)
`
`Inventors: Kenichi Sakamoto, Tokyo (IP);
`Kazuyoshi Hoshino, Fujisawa (JP);
`te
`+
`:
`KollWakayamajeeOP)Nobo
`,
`,
`Endo, Kodaira (JP)
`
`(73) Assignee: Hitachi, Ltd., Tokyo (JP)
`
`(*) 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/392,623
`
`(22)
`
`(30)
`
`Filed:
`
`Sep. 9, 1999
`
`Foreign Application Priority Data
`
`May 27, 1999
`
`(IP)
`
`voceececcecceceseseceesereeseeessteeeeeeees 11-147663
`
`(SV)
`
`Tint, C17 ieee cceeeeeeeceeeeeeeeeeneene HO4L 12/46
`
`(52) US. Cd. cece eeeeeeetees 370/401; 709/249
`
`(58) Field of Search 0.0.0.0... 370/356, 395.5,
`370/401; 709/249
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,390,173 A *
`2/1995 Spinneyet ale cesses 370/393
`eeeeeeeeceeereee 370/402
`5,394,402 A *
`2/1995 Ross oo
`
`F/L995S Callon wee eres 370/401
`5,430,727 A *
`
`9/1995 Perlman et al. 0... 370/392
`5,450,407 A *
`ton. Mecloghrie t a seeeees joo
`0530 a :
`.......
`219,
`cCloghrie et al.
`
`6,304,901 B1 * 10/2001 McCloghrie et al.
`...... 709/221
`6,392,997 B1 *
`5/2002 Chem 0... eee eeeeneee 370/252
`
`* cited by examiner
`
`Primary [E’-xaminer—Hassan Kizou
`Assistant Examiner—Dmitry Levitan
`(74) Attorney, Agent, or Firm—Antonelli, Terry, Stout &
`Kraus, LLP
`
`(57)
`
`ABSTRACT
`
`A method serves to compose a VPN (Virtual Private
`Network) over a plurality networks each of which is man-
`aged by different Internet Service Providers (ISP). When a
`packet with a first capsule header used for composing a VPN
`in a first ISP networkis transmitted to a second ISP network,
`a route for outputting packet to the second ISP network is
`determined based on the information both in the capsule
`header and in the IP header. In addition, a second capsule
`header used for composing a VPN in the second ISP network
`is determined based on the above information.
`
`5 Claims, 23 Drawing Sheets
`
`ROUTER
`
`INTERWORK
`
`2-4
`
`
`
`CAPSULE!~oop
`
`
`
`
`
`
`IP
`
`PHY
`
`
`
`CAPSULEICAPSULE
`
`
`PHY PHY
`
`
`
`1
`
`SAMSUNG 1074
`SAMSUNG1074
`SAMSUNG v. SMART MOBILE
`SAMSUNGv. SMART MOBILE
`IPR2022-01004
`IPR2022-01004
`
`1
`
`

`

`bdSl
`
`(¥‘dINOO)
`
`TANNVHS1V9ID5071
`
`yNVT
`
`
`
`NOILVINSdVONS3WLYV
`
`NOILVINSdYONGdi
`
`
`
`JANNVHO1V9IS0O71
`
`US 6,633,571 BI
`
`q-h
`
`aqNv1
`
`(@‘diNOD)
`
`CNVYAAVTdl
`
`
`
`YSAV1YSaMO1
`
`YOLVISNVYL
`
`OLMYOMYALNI
`
`YAaLNow
`
`BNV1
`
`(a“diNOd)
`
`e]
`
`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 1 of 23
`
`edSsl
`
`S1diN
`
`MYOMLAN
`
`LSld
`
`NOILWIANSdVONGAdi
`
`MYOMLAN
`
`(y¥"diNOD)
`
`LNW
`
`LoL
`
`2
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 2 of 23
`
`US 6,633,571 BI
`
`P-L
`
`€NVI
`
`(Vv‘diNOO)
`
`(¥‘diNOD)
`
`VANNVHS19915071
`
`yNVT
`
`NOILVINSdVONAALY
`
`NOILVWINSdVONGAdl!
`
`
`
`TANNVHSTVSISO71
`
`q-b
`
`qQNV7
`
`(a‘diINOD)
`
`TWAAZIML3Ydl
`
`GNvV
`
`YOLVISNVYL
`
`6Yalnod
`
`Y4MO7ONILVNIWYSL
`
`ONISYAWGNVYSAV1
`
`TAaA371diNO
`
`LdSI
`
`edSl
`
`ST1dil
`
`MYOMLAN
`
`éOld
`
`NOILVTINSdVONGdl
`
`MYOMLAN
`
`(Vv‘dINOO)
`
`LNW
`
`LL
`
`3
`
`
`

`

`U.S. Patent
`
`eld
`
`Oct. 14, 2003
`
`Sheet 3 of 23
`
`US 6,633,571 BI
`
` be
`
`MYOMAALNI
`
`YaLNow”
`
`4
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 4 of 23
`
`US 6,633,571 BI
`
`FIG.4
`
`INPUTTING PACKET
`
`200
`
`PHYSICAL LAYER
`(ELIMINATING FLAME)
`
` TERMINATING
`
`
` ELIMINATING ISP1 CAPSULE
`
`
`HEADER
`
`(TERMINATING)
`
`ROUTE RETRIEVAL
`BASED ON IP HEADER
`
`(TERMINATING)
`
`TRANSMITTING THE PACKET
`TO THE ROUTE BY SWITCH
`
`ADDING ISP2 CAPSULE
`HEADER
`
`201
`
`202
`
`203
`
`204
`
`205
`
`206
`
` TERMINATING
`
`
`PHYSICAL LAYER
`
`
`(ADDING FRAME)
`
`OUTPUTTING PACKET
`
`207
`
`PROCESSING FLOW IN ROUTER
`
`5
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 5 of 23
`
`US 6,633,571 B1
`
`FIG.5
`
`INPUTTING PACKET
`
`210
`
`
`TERMINATING
`
`
`PHYSICAL LAYER
`
`
`(ELIMINATING FLAME)
`
`ROUTE RETRIEVAL AND
`GENERATING ISP2 CAPSULE
`HEADER BASEDON ISP1
`CAPSULE HEADER AND
`
`IP HEADER
`
`
`
`ELIMINATING ISP1 CAPSULE
`
`HEADER
`
`(TERMINATING)
`
`ADDING ISP2 CAPSULE
`HEADER
`(TERMINATING)
`
`TO THE ROUTE BY SWITCH
`
`TRANSMITTING THE PACKET
`
`
` TERMINATING
`
`
`PHYSICAL LAYER
`
`
`(ADDING FRAME)
`
`217
`
`212
`
`213
`
`214
`
`215
`
`216
`
`OUTPUTTING PACKET
`
`217
`
`PROCESSING FLOW
`
`IN INTERWORK ROUTER
`
`6
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 6 of 23
`
`US 6,633,571 B1
`
`FIG.6
`
`INPUTTING PACKET
`
`220
`
`
`TERMINATING
`PHYSICAL LAYER
`
`
`(ELIMINATING FLAME)
`
`ROUTE RETRIEVAL AND
`GENERATING CAPSULE
`HEADER INDEX BASED ON
`ISP1 CAPSULE HEADER AND
`IP HEADER
`
`ELIMINATING ISP1 CAPSULE
`HEADER (TERMINATING)
`AND
`ADDING THE CAPSULE
`HEADER INDEX
`
`TRANSMITTING THE PACKET
`TO THE ROUTE BY SWITCH
`
`
`
`ADDING ISP2 CAPSULE
`HEADER ACCORDING TO
`THE CAPSULE HEADER INDEX
`(TERMINATING)
`
`TERMINATING
`PHYSICAL LAYER
`(ADDING FRAME)
`
`221
`
`222
`
`223
`
`224
`
`225
`
`226
`
`OUTPUTTING PACKET
`
`227
`
`PROCESSING FLOW
`
`IN INTERWORK ROUTER
`
`7
`
`

`

`Oct. 14, 2003
`
`Sheet 7 of 23
`
`US 6,633,571 BI
`
`MYHOMLAN
`
`MYOMLAN
`
`NOILVWINSdVONGdl¢dsl
`
`U.S. Patent
`STdWLdSI YaLnow
`
`L°9lA
`
`WYOMYSLNI
`
`8
`
`
`

`

`Oct. 14, 2003
`
`Sheet 8 of 23
`
`US 6,633,571 BI
`
`U.S. Patent
`
`8'Old
`
`8621149WLY
`(espO4u)STVVAGNOILWINSdVONSA
`QVOTAVddi|YS0V3SHdl
`bSZose
`
`8ST1590WLV
`SSzgz9gz.,igzigz
`
` +>QvOTAWdWLYMaQVSHWLYavoTAWdWLYwaqvaHWLY
`
`
`
`MaTIVeLsivv|avd|avo1AVddi|ugavaHdi|dvNSs/oT|waavaHsivv
`92£52esezz
`
`9
`
`
`

`

`
`+._+|:>SLIGPSLIGPSLIPPSLIDPSLID7SLIDPSLIGPSLIGP
`L43S4dd0LNSAWSVvadOvidNOILVOISILNAI
`
`
`
`
`WASHMISHSDYaqvsaH
`
`ddALTOD0LONd
`
`AAIOLSWIL
`
`
`
`
`
`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 9 of 23
`
`US 6,633,571 BI
`
`(HLON]AIATEVINVA
`
`ONIGaVd
`
`(HLONS1AISVINVA)NOILdO
`
`6'Old
`
`
`
`SSAwvddvV3DYNOS
`
`
`
`SSaYdddVNOILVNILS3Q
`
`10
`
`10
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 10 of 23
`
`US 6,633,571 BI
`
`(e€S8bO44)TANNNLdlAdNOILLVINSdVONS
`
`QVOTAVddlJSNNNL
`QVOTAVddil|YAQWVSHdi
`L9¢092
`
`OLDIF
`
`TIWNYALNI
`
`aYsqvsH
`YsaqVsH
`YAQqVSHdl
`
`
`
`
`
`AINSdVS
`
`
`
`v9e¢YAQVAH
`
`11
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 11 of 23
`
`US 6,633,571 B1
`
`FIG.11
`
`50
`
`CONTROL
`UNIT
`
`LOWER
`LAYER
`
`PROCESSING |
`
`UNIT
`(ATM)
`
`FROM
`ISP1
`
`TO
`ISP1
`
`FROM
`ISP2
`
`TO
`ISP2
`
`(IP CAPSULE)
`
`PACKET
`LAYER
`
`noneeenc |
`
`UNIT
`
`CORE
`SWITCH
`
`LOWER
`LAYER
`PROCESSING
`UNIT
`
`PACKET
`LAYER
`PROCESSING
`UNIT
`
`12
`
`12
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 12 of 23
`
`US 6,633,571 BI
`
`FIG.12
`
`VPN NUMBER
`TABLE
`IN RECEIVER
`
`
`
`PHYSICAL
`LAYER
`PROCESSING
`
`UNIT
`IN RECEIVER
`SIDE
`
`ATM LAYER
`
`IN RECEIVER
`SIDE
`(CLAD)
`
`PACKET
`LAYER
`
`PROCESSING
`UNIT IF
`
`HEADER
`GENERATING
`TABLE
`
`PHYSICAL
`LAYER
`PROCESSING
`
`ATM LAYER
`PROCESSING
`
`ATM
`HEADER
`DECIDING
`UNIT
`
`PACKET
`LAYER
`PROCESSING
`UNIT IF
`
`CONTROL
`SYSTEM
`IF
`
`TO CONTROL UNIT
`
`13
`
`13
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 13 of 23
`
`US 6,633,571 B1
`
`FIG.13
`
`300
`
`303
`
`ATM HEADER IN INPUT SIDE
`
`VPN NUMBER IN INPUT SIDE
`
`ee
`
`INTERNAL VPN
`
`VPI/VCI
`
`sf
`
`302
`
`INPUT KEY
`
`OUTPUT KEY
`
`14
`
`14
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 14 of 23
`
`US 6,633,571 B1
`
`FIG.14
`
`VPN NUMBER
`TABLE
`IN RECEIVER
`SIDE
`
`UNIT IF CONTROL
`
`PHYSICAL
`LAYER
`PROCESSING
`UNIT
`IN RECEIVER
`SIDE
`
`CAPSULE
`
`IN RECEIVER
`SIDE
`(HEADER
`ELIMINATION)
`
`PACKET
`LAYER
`PROCESSING
`
`HEADER
`GENERATING
`TABLE
`
`CAPSULE
`PHYSICAL
`LAYER
`LAYER
`PROCESSINGlq]CAPSULE
`PACKET
`PROCESSING
`HEADER
`LAYER
`DECIDING
`PROCESSING
`UNIT
`
`MPU
`WORK RAM
`
`SYSTEM
`IF
`
`TO CONTROL UNIT
`
`15
`
`15
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 15 of 23
`
`US 6,633,571 B1
`
`311
`
`CAPSULE
`
`HEADER(SA)
`
`|
`
`TOS
`
`INTERNAL VPN
`
`NUMBER
`
`FIG.15
`
`APSULE HEADER IN INPUT SIDE) VPN NUMBER IN INPUT SIDE
`
`305
`
`INPUT KEY
`
`OUTPUT KEY
`
`16
`
`16
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 16 of 23
`
`US 6,633,571 B1
`
`ROUTE RETRIEVAL TABLE
`AND
`VPN TABLE
`
`ROUTE RETRIEVAL AND
`
`VPNPROCESSING UNIT a IF
`
`WORK RAM FIG.16
`
`CORE
`SWITCH
`
`LOWER
`LAYER
`PROCESSING
`UNIT IF
`
`LOWER
`LAYER
`PROCESSING
`UNIT IF
`
`MPU
`
`CONTROL
`SYSTEM
`IF
`
`TO CONTROL UNIT
`
`17
`
`17
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 17 of 23
`
`92
`
`See
`
`E2E
`
`Océ
`
`ZL‘Old
`
`
`
`AdISLAdLNONI
`
`
`
`YagaiAnn
`
`YAGWNNAINSdVD
`
`
`ALNOYLAdLNO
`YAQVaHdi
`
`
`
`AQISLAdNINIYAGIWNNNdA
`
`a1NSdVO
`
`YagWnNNn
`
`NOILVNILS3G
`
`SSaydqgv
`
`YsaaWnn
`
`NdA1VNYSLNI
`
`Lee
`
`*eeeea«ee¢‘¢.ee
`
`18
`
`US 6,633,571 BI
`
`
`
`AAayLAdLNO
`
`AALAdNI
`
`18
`
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 18 of 23
`
`US 6,633,571 B1
`
`FIG.18
`
`330
`
`333
`
`332
`
`-
`
`CAPSULE NUMBER
`IN OUTPUTSIDE
`NUMBER Qos
`
`LOWER LAYER
`
`ATM HEADER
`IN OUTPUT SIDE
`
`pzff
`
`:
`
`INPUT KEY
`
`OUTPUT KEY
`
`19
`
`19
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 19 of 23
`
`US 6,633,571 BI
`
`6h‘S/d
`
`AINSdVDS
`
`
`
`AISLNdLNONIAdIsLNdLNONI
`
`
`
`SdIisLNAdLNONI
`
`
`
`SSayddvOVYSq0VsSHAINSdVOdl
`
`YAasWAN
`
`
`
`AdyLNAdLNO
`
`ABXLAdNI
`
`J1NSdV9dl
`
`YsaqvaH
`
`
`
`YSAV1YAMO1
`
`YagaWnAN
`
`LbE
`
`20
`
`20
`
`

`

`a9q3
`
`YaLnoy
`
`YaLnow
`
`02°Dld
`
`Oct. 14, 2003
`
`Sheet 20 of 23
`
`US 6,633,571 BI
`
`U.S. Patent &-4h
`
`WYOMHYALNI
`MYOMYALNIbe
`
`21
`
`21
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 21 of 23
`
`US 6,633,571 BI
`
`WYOMHYALNI
`
`YaLNOY
`
`(xn
`
`Le‘Old
`
`
`
`YaLNOYYaLNow
`
`
`
`MYOMYBLNIWYOMUSLNI£-Z
`
`260|=960k«eonfkqe0t
`
`AHd|ezop|AHd &-L
`repfeHs|ete|Celle[Cefay
`
`SINSdVOAINSdYAINSdVOANSdVAINSdVOSAINSdY:TNSdV.
`
`
`
`
`
`
`Tiddv¥
`
`AHd
`
`IZ04
`
`
`
`AHdazol
`
`ANSdY
`
`zo
`
`
`
`PZOL2204
`
`bh
`
`22
`
`22
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 22 of 23
`
`US 6,633,571 BI
`
`WddvV
`
`MYOMUYSLNI
`
`YaLnow
`
`(x1)
`
`ceOld
`
`bb
`
`0
`OL
`
`ate|e[ae||'1,9804
`
`
`
`AINSAVOAINSdV:TNSdVIAINSdYATINSdVOAINGdYrINSdvV.
`
`MYYOMYALNIMHYOMYALN£-Z
`
`YaLNO’YaLNoY
`960FkPo4qeot
`Pook220t
`‘atte"Ls[a]geari|!Jl1
`
`AHd|Pzop
`
`TNSdY
`
`AHd
`
`8z0L
`
`gzoL
`
`L
`
`oL
`
`AHd
`
`23
`
`23
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 2003
`
`Sheet 23 of 23
`
`US 6,633,571 B1
`
`FIG.23
`
`500
`
`CAPSULE HEADER ENTR
`IN INPUT SIDE
`
`,
`
`IN INPUT SIDE
`
`VPN NUMBER INDEX
`
`CAPSULE HEADER VPI/VCI
`
`CAPSULE HEADER CLP
`
`INTERNAL VPN NUMBER
`
`QoS
`
`507
`
`VPN CROSS CONNECT
`
`
`
`
`
`CROSS CONNECT INDEX
`IN INPUT SIDE
`
`
`
`INTERNAL VPN NUMBER
`
`DESTINATION IP ADDRESS
`IN INPUT SIDE
`
`OUTPUT ROUTE NUMBER
`
`CAPSULE NUMBER
`IN OUTPUT SIDE
`
`502
`
`CAPSULE HEADER ENTR
`IN OUTPUT SIDE
`
`
`
`
`
`
`
`ENCAPSULATION INDEX
`
`IN OUTPUT SIDE
`
`CAPSULE NUMBER
`IN OUTPUT SIDE
`
`VPIVCI
`IN OUTPUT SIDE
`
`QoS
`
`CLP IN OUTPUT SIDE
`
`24
`
`24
`
`

`

`US 6,633,571 Bl
`
`1
`VPN COMPOSING METHOD, INTERWORK
`ROUTER, PACKET COMMUNICATION
`METHOD, DATA COMMUNICATION
`APPARATUS, AND PACKET RELAYING
`APPARATUS
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates to a method of composing a
`VPN (Virtual Private Network) on the Internet and an
`interwork router used to connect Internet service providers
`to each other.
`
`10
`
`15
`
`2
`examination in such standardization groups as ITU-T SG13
`(International Telecommunications Union-
`Telecommunications Standardization Section, Study Group
`13),
`IETF (Internet Engineering Task Force), etc.
`In
`addition, ITU-T SG13 is also examining the Core Protocol
`of the Global Multi-media Network Connection Less
`(GMN-CL)for transferring packcts encapsulated according
`to E.164 addresses in the object network.
`“Access Network Systems and Edge Nodes Systems for
`the Next-Generation Computer Network”, pp.425—434,
`NTT R&D vol.47 No.4, 1998 (issued on Apr. 10, 1998) has
`also proposed a method for composing an edge node in an
`accessing system used to interwork between each of a
`plurality of user networks and the core network in the
`GMN-CL.
`
`SUMMARY OF THE INVENTION
`
`Various applications such as E-mail and WWW (World
`Wide Web) programs can be used on any Internet Protocol
`CIP) networks. In addition, such IP networks can be com-
`posed at lower costs than the conventional switching net-
`works that use are associated with telephones. This is why
`In recent years, the areas of activities in companies have
`the Internet has rapidly come into wide use in recent years.
`expanded more and more widely. For example, many Japa-
`Under such circumstances,
`intracompany networks
`nese companies have offices at overseas,
`including the
`(intranets) composed on the IP level are now indispensable
`United States of America and European countrics. Under
`for facilitating the activities of those companies.
`such circumstances, it would be natural for those companies
`Companies are often distributed unevenly in local areas.
`to consider it important to connect the intranets composed in
`In suchasituation, therefore, there will appear a demandthat
`their offices to each other via a VPN.
`the intranets in those local areas should be connected into
`
`one network as a logical consequence. In such a case, there
`are the following two methodspossible for connecting those
`intranets to each other in local areas.
`
`Firstly, private lines are used for connecting those intra-
`nets in local areas. In this case, each of those intranets can
`be isolated from external networks for ensuring security.
`Secondly, the IPsec (IP security protocol) technique is
`used to provide each terminal with a function for identifying
`packets of its own company’s network,so that those packets
`are transterred on the Internet as IP packets using global
`addresses. This identifying function, when combined with
`an encoding technique, can make up a Virtual Private
`Network (VPN) so as to be protected from the attacks of
`malicious users.
`
`If such private lines are used; however, some problems
`arise;
`for example,
`the network cost
`is increased, and
`furthermore, the VPN realized by the IPsec method cannot
`be protected from the attacks and invasions of malicious
`users who can crack the codes. In addition, the encoding
`processing becomesa bottleneck of increasing the speeds for
`fast networks and terminal costs are increased.
`
`Along with the rapid spread of the Internet, as well as the
`cost reduction of using the Internet, there have appeared
`strong demandsfor forming virtual private networks on the
`Internet using the functions of lower layers than the IP layer
`provided by networks, while suppressing the cost and iso-
`lating each of those virtual private networks from external
`networks so as ta assure the security and quality thereof.
`In order to meet such demands, the following VPN is
`proposed. A packet is encapsulated at the inlet of the object
`network of an Internet Service Provider (ISP) that provides
`the VPN. On the ISP network, each packet is transferred
`according to the capsule header, then the capsule header is
`removedat the outlet of the network. According to this VPN
`composing method,since a packet is encapsulated peculiarly
`to the VPN, the VPN is isolated from external networks,
`thereby assuring the security of the VPN. More concretely,
`for such an encapsulation protocol various methods are
`available, such as IP encapsulation, MPOA (Multi Protocol
`over ATM), MPLS (Multi Protocol Layer Switching), etc.
`Since February of 1999, those methods have been under
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`25
`
`On the other hand, since each ISP generally provides the
`services only in a specific area, the VPN must be composed
`over a plurality of ISPs in order to connect the networks
`(intranets) in those areas through the VPN.
`And, if a plurality of ISPs are connected to each other in
`such a way, an interwork gateway (interwork router) needs
`to be formed for such connection. In this interwork router,
`the interworkis realized so as to transfer each of the packets
`from one of the ISP networks to the other according to the
`IP header. In addition, a system referred to as an IX (Internet
`Exchange) is used for connecting both networks to each
`other so as to realize the interwork among a plurality of
`networks as described in “Commercial IX”, pp.146-155,
`Nikkei Communications 1997.12.15. And, this IX may also
`be used to transfer IP packets among those networks. Such
`an |X includes some methodsthat use a “layer 3 forwarding”
`function for identifying and transferring each of the IP
`packets, as well as a “layer 2 forwarding” function for
`transferring each of the IP packets byidentifying the header
`in the lower layer in the ATM (Asynchronous Transfer
`Modc) communication system, cte.
`The present inventors have examined the problems which
`arise when a VPN is composed over a plurality of ISP
`networks. At first, packets are encapsulated in order to
`compose a VPN for the network of each Internet Service
`Provider. Generally,
`the encapsulation protocol of each
`network differs from other networks. In this case,
`the IP
`header information of each IP packet is retrieved by the
`interwork router, thereby determining the route to the des-
`tination.In this case, the retrieving must also include a check
`to determine whetheror not the packetis to be transferred to
`another network. The IP header information is commonfor
`both of the networks.
`
`However, the interwork router terminates the protocol of
`each layer lowerthan the IP layer at the interface. Therefore,
`the capsule header given in the previous network so as to
`compose the VPNis removedin the processofretrieving the
`IP address, so that information as to the next leg of the route
`can be determined. After that, a new capsule header must be
`generated and addedto the packet so as to compose the VPN
`in the next network. Consequently, packets in the VPN are
`mixed with packets in other networks in the interwork
`
`25
`
`

`

`US 6,633,571 Bl
`
`3
`router. And, this might cause a problem that malicious users
`are able to change the headers to those packets and invade
`the VPN through the interwork router.
`Some companies do not use global addresses, but use
`private addresses for composing their VPNs. In such a case,
`once the interwork router removes the capsule header of a
`packet, the receiving ISP cannotdistinguish the packet from
`others if the packet has the same address as those of other
`packets. This is because each of a plurality of VPNs use
`internal addresses uniquely. Consequently, the receiving ISP
`receiving cannot determine the destination of the packet. If
`a VPN is composed overa plurality of ISPs on the Internet,
`therefore, the problem as described above be solved byall
`means.
`
`In addition, the types of services are not the same among
`ISPs. As for
`the communication quality,
`for example,
`assume that one ISP uses an ATM VC(Virtual Channel) for
`forming a communication path, thereby assuring the quality
`of each VPN and the other ISP uses Diffserv (Differentiated
`Services) to assure the quality of the communication. If the
`VPNs composed for both networks are to be connected to
`each other in such a case, it will be difficult to provide the
`communication quality on an end-to-endlevel.
`As described above, it is difficult to compose a VPN over
`a plurality of ISPs on the Internet for practical use.
`Under such circumstances, therefore, it is an object of the
`present invention to solve the above problems and provide
`a method of composing a VPN overa plurality of ISPs and
`provide an interwork router for connecting those ISPs to
`each other in such a VPN.
`
`In order to solve the above problems, the interwork router
`of the present
`invention is provided with functions for
`determining the route to output packets and for generating a
`capsule header for each of those packets to be used in the
`next ISP network (in output side) from the information set
`both in the capsule header, which is a VPN identifier, and in
`the IP header of the packet. Hereunder, a more detailed
`description will be made of an example of how to connect
`a plurality of ISPs to each other. Each of those ISPs is used
`to operate an MPLS network that uses an ATM as a lower
`layer. More concretely, header information is added to each
`packet to be transferred to the next network. Such header
`information is generated when header information such as
`VPI, VCI, etc. (capsule headers) of the ATM are used to
`identity the VPS, as well as to determine the next route and
`identify the VPN in the next network, which header infor-
`mation is generated with necessary data retrieved according
`to an IP address as a key. And, the header information is
`generated and transferred together with the packet to the
`next network.
`
`A VPNinterwork can thus be realized, thereby enabling
`the VPN to be composed on the Internet in areas covering a
`plurality of ISPs.
`The value ofthe field that indicates the QoS in the capsule
`header on the input side is mapped onthe value of the field
`that indicates the QoS in the capsule header for the output
`side. Consequently, quality information of both networks
`composing a VPN canbetransferred asis.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a schematic diagram showing an example of the
`operation of an interwork router according to the present
`invention.
`
`FIG. 2 is a schematic diagram illustrating an example of
`problems solved bythe present invention.
`
`4
`FIG. 3 is a diagram which shows the operation of the
`interwork router of the present invention using a protocol
`stack.
`
`FIG. 4 is a flow chart indicating an ISP interworking
`method that uses a conventional router.
`
`FIG. 5 is a flow chart indicating the operation of the
`interwork router of the present invention.
`FIG. 6 is a flow chart indicating the operation of the
`interwork router of the present invention.
`FIG. 7 is a diagram which illustrates a method for
`connecting an MPLS network with an IP encapsulation
`network using a protocol stack in an embodiment of the
`present invention.
`FIG. 8 is a diagram which shows how an IP packet is
`converted to ATM cells according to RFC1483.
`FIG. 9 is a diagram which showsthe format of IP packets
`according to RFC791.
`FIG. 10 is a diagram which showsthe configuration of an
`IP tunnel packet according to RFC1853.
`FIG. 11 is a block diagram of the interwork router of the
`present invention.
`FIG. 12 is a block diagram of a lower layer processing
`unit provided for the interwork router of the present inven-
`tion.
`
`FIG. 13 is a diagram of a VPN numbertable for receiving,
`provided in the lower layer processing unit of the present
`invention.
`
`FIG. 14 is a block diagram of the lower layer processing
`unit provided in the interwork router of the present inven-
`tion.
`
`FIG. 15 is a diagram of a VPN numbertable for receiving,
`provided in the lower layer processing unit of the present
`invention.
`
`FIG. 16 is a block diagram of a packet layer processing
`unit provided in the interwork router of the present inven-
`tion.
`
`10
`
`15
`
`30
`
`35
`
`40
`
`FIG. 17 is a diagram of a route retrieval table/VPN table
`provided in the packet layer processing unit of the present
`invention.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`FIG. 18 is a diagram of a header generating table provided
`in the lower layer processing unit of the present invention.
`FIG. 19 is a diagram of the header generating table
`provided in the lower layer processing unit of the present
`invention.
`
`FIG. 20 is a diagram showing an example of the interwork
`router in a network according to an embodiment of the
`present invention.
`FIG. 21 is a diagram showing an example of the interwork
`router in a network according to an embodiment of the
`present invention.
`FIG. 22 is a diagram showing an example of the interwork
`router in a network according to an embodiment of the
`present invention.
`FIG. 23 is a diagram showing an interface for directing
`the interwork router from an NMSsoasto set the tables in
`an embodimentof the present invention.
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`Hereunder, various embodiments of the present invention
`will be described with reference to the accompanying draw-
`ings.
`At first, a description will be made for how to compose a
`VPNovera plurality of ISPs, which are separated by a lower
`
`26
`
`26
`
`

`

`US 6,633,571 Bl
`
`6
`5
`sulation method for the IP layer and ATM encapsulation,
`layer, respectively, according to the present invention, as
`frame relay and HDLCprotocols may also be used for such
`well as the role of the interwork router of the present
`encapsulation.
`invention, with reference to FIGS. 1 and 2. A lowerlayer as
`mentioned here is a protocol for encapsulating the header of
`Next, a description will be made of an embodimentof the
`eachIP packet. This capsule header will also be described as
`present invention for a method of composing a VPN over a
`a header of the lower layer even when each IP packet is
`plurality of ISPs using a network configuration and a pro-
`encapsulated according to the IP header.
`tocol stack, with reference to FIG. 3. Any encapsulation
`protocol may be used in this embodiment. The ISP1 (2-1) is
`Hereunder, a description will be made of problemsthat
`connected to LAN1 (1-1) and LAN2 (1-2) via edge nodes
`will arise when a VPN is composed overa plurality of ISPs
`(3-1 and 3-2) respectively. In the same way, the ISP2 (2-2)
`using a conventionalrouter, with reference to FIG. 2. In FIG.
`is connectedto a plurality of networks including LAN3(1-3)
`2, both ISP1 (2-1) and ISP2 (2-2) are interworking using a
`and LAN4(1-4) via cdge nodes (3-3 and 34), respectively.
`conventional router (9). The ISP1 and ISP2 are used to
`Eachof those ISPs encapsulates each of the IP packets using
`compose a VPN byencapsulating packets in a layer lower
`the headerusedinside the network betweentheinlet and the
`than the IP layer. The ISP1 provides services in the area A
`outlet of the network. Since the ISP assigns a capsule header
`and includes LAN (Local Area Network) 1 (1-1), LAN2
`to cach of those IP packets uniquely to the subject VPN, the
`(1-2), and LANa (1-a). The ISP2 provides services in the
`VPNtraffic is identified amongother traffic on the network,
`area B and includes LAN3 (1-3), LAN4 (1-4), and LANb
`thereby enabling the VPN network to be a closed network.
`(1-b). LAN1 to LAN4 belong to company A, which is
`Both ISP1 (2-1) and ISP2 (2-2) interwork using the inter-
`planning to compose a VPN over those LANs. Both LANa
`work router (10), thus the packcts to the destination nctwork
`and LANb belong to company B, which is different from ,,
`are transferred via the interwork router (10).
`company A and whichis also planning to compose a VPN
`For example, if a VPN (VPN1in this case) connects both
`over those LANs.In suchacase, if an encapsulation channel
`LANI1and LAN2, each of the IP packets sent from LAN1 to
`is provided betweenaninlet and an outlet of a network in the
`LAN3is retrieved according to the IP address at the edge
`same ISP, packets of a specific user can be separated from
`node (3-1). Atfirst, the packet is recognized to be addressed
`packets of other users. A higher security network can thus be 5
`to the interwork router belonging to the VPN1,
`then a
`composed. However, if a VPN is to be composed over both
`capsule header (1032)
`is added so that
`the packet
`is
`ISP1 and ISP2, the conventional router terminates the lower
`addressed to the interwork router belonging to the VPN1.
`layer at the interface on the input side and merges packets on
`‘The packet can thus be received correctly by the interwork
`router (10). The interwork router (10) retrieves the packet
`the IP level, then executes the packet forwarding. And,this
`according to the capsule header (1032) and the IP address of
`causes a problem in that packets from a plurality of users are
`mixed on the IP level. In other words, packets in a VPN are
`each packet so as to be recognized as a packet addressed to
`the edge node (3-3) of the VPN1. Then, a capsule header
`mixed with packets of other networks. Consequently, this
`(1038) is addcd to the packet so that it is addressed to the
`makes it possible for malicious uscrs to enter the nctwork
`edge node (3-3) in the ISP2. The packetis thus transferred
`using false IP addresses. In addition,
`if two companies
`to the edge node (3-3) in the ISP2 according to the capsule
`compose a I.AN respectively using private addresses, each
`header information. At the edge node (3-3),
`the capsule
`of those companies assigns its addresses independently.
`Thus, both of the companies might assign the same IP
`header is removed from the packet. The packet is then
`addresses. In such a case, the conventional router cannot
`transferred to LAN3. Consequently, IP packets can be trans-
`transfer packets correctly due to conflict created by those
`ferred in the VPN composed over the two networks so as to
`addresses.
`be prevented from mixing with packets belonging to other
`traffic.
`
`10
`
`15
`
`30
`
`35
`
`40
`
`invention will solve the above
`Next, how the present
`problems will be described with reference to FIG. 1. For
`example, assume now that the company A sendsdata from
`LAN1 to LAN3 of the same company A.
`In this
`embodiment, the ISP1 composes a VPN by encapsulating IP
`packets and the ISP2 composes a VPN by encapsulating
`packets in a MPLS network, which uses the ATM. Packets
`received by the ISP1 (2-1) from LAN1are encapsulated as
`IP packets by the ISP1, and then they are received bythe
`interwork router through the IP encapsulation logical chan-
`nel (5-1). The interwork router (10) retrieves the output
`route from both of the [P-capsule header, indicating the IP
`encapsulation logical channel
`through which the object
`packetis received, and the headerof the original packet, and
`then creates a new capsule header for the packet, whichis to
`be used in the ISP2. In this embodiment, since the ISP2
`provides services using MPLS, the interwork router creates
`an ATMheaderfor the packet. Packets encapsulated by ATM
`are then transferred to LAN3 through the AIM logical
`channel (5-3). Since the interwork router retrieves the output
`route from both capsule header and IP header, it can transfer
`packets to the correct addresses even when both companies
`A and B useprivate addresses and a conflict occurs between
`IP addresses.
`
`Although a description has been made of two encapsu-
`lating methods as encapsulating protocols in this
`embodiment, that is, IP encapsulation, which is an encap-
`
`45
`
`50
`
`55
`
`60
`
`65
`
`IP packets, when they use global addresses, can be
`transferred just like they are transferred in the conventional
`networks, if both the destination (when capsule headers are
`used) and the capsule header of each packet are considered
`together without depending on the lower layer information.
`Next, the operation of the interwork router (10) will be
`described with reference to ['IGS. 4 to 6. PIG. 4 shows a
`
`processing flow of a conventional router. FIGS. 5 and 6
`show processing flows of the interwork router (10) of the
`present invention. The conventional router, when receiving
`packets, terminates the physical layer (step 201) used for
`transferring the packets in the ISP1 (2-1) and removesthe
`capsule header used for the transfer operation in the ISP1
`from each of those packets (step 202), and thenit retrieves
`the route to the next network according to the value in the
`IP header of the packet (step 203). Then, the conventional
`router transfers the packets along the desired route via a
`switch (step 204). After that, the conventional router adds a
`capsule header to each of those packets used for the transfer
`operation in the ISP2 (step 205), and then it executes a
`processing for the physical layer (step 206) so as to output
`the packets from the transmission path. In this processing
`flow, since the capsule header of each packet used in the
`transfer operation in the ISP1 is removedandthe route to the
`next ISP is determined only with the IP headerof the packet,
`the traffic of a plurality of VPNs are merged once.
`
`27
`
`27
`
`

`

`US 6,633,571 Bl
`
`7
`According to the interwork router of the present
`invention, however, such the problem can be avoided.
`FIG. 5 shows an algorithm executed by the interwork
`router (10) of the present
`invention. According to the
`algorithm, if a packet arrives,
`the interwork router (10)
`terminates the physical layer used for the transfer operation
`in the ISP1 (2-1) (step 211), and thenit retrieves the route
`to the ISP2 according to the capsule header and the IP header
`of the packet used in the transfer operation in the ISP1,
`thereby generating a new capsule headerfor the packet to be
`used in the ISP2 (step 212). After that, the router replacesthe
`capsule header used in the ISP1 with the new capsule header
`(step 213), to be used in the transfer operation in the ISP2
`(step 214), and thenit transfers the packet to the switch. The
`packetis thus transferred by the switch into the desired route
`(step 215). After that, the router executes a processing for the
`physical layer (step 216) to output the packet from the
`transmission path. Consequently, the packet traffic can be
`separated from the traffic of other networks. In addition,
`since naked IP packets from which the capsule header is
`removed are never supplied to the switch, no other invalid
`users can insert packets in the VPN from this switch. In other
`words,it is impossible for invalid IP packets, which are not
`provided with an internal header used in the JSP2
`respectively, are to be mixed with valid IP packets in the
`ISP2. Consequently, the security of the network is signifi-
`cantly improved.
`Next, another embodimentof the present invention will
`be described with reference to FIG. 6. The interwork router
`
`in this embodiment is provided with a table of correspon-
`dence between a set of capsule headers and IP header values
`used for the transfer operation in the ISP1 and capsule
`header indexes, as well as a table of correspondence between
`capsule header indexes and the capsule headers used for the
`transfer operation in the ISP2. The interwork router in this
`embodiment,if it receives a packet, terminates the physical
`layer used for the transfer operation in the ISP1 (2-1) (step
`221). Then, the interwo