United States Patent (19)
`Callon et al.
`
`IIII
`
`SOO5251205A
`Patent Number:
`(11)
`(45) Date of Patent:
`
`5,251,205
`Oct. 5, 1993
`
`(54) MULTIPLE PROTOCOL ROUTING
`75) Inventors:
`Ross W. Callon, Bedford; Radia J.
`Perlman, Acton; Eric C. Rosen,
`Arlington, all of Mass.; John Harper,
`Reading, England
`(73) Assignee: Digital Equipment Corporation,
`Maynard, Mass.
`(21) Appl. No.: 577,437
`(22
`Filed:
`Sep. 4, 1990
`51) Int. Cl.......................... H04J 3/26; H04L 12/56
`52 U.S. Cl. ..................................... 370/60; 370/94.1;
`370/54; 370/79; 370/85.13
`58) Field of Search ................ 370/94.1, 85.13, 85.14,
`370/60, 79, 54
`
`56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,706,081 1/1987 Hart et al. ............................. 370/61
`4,831,620, 5/1989 Conway et al...
`... 340/825.05
`4,893,307 1/1990 McKay et al. ..................... 370/94.1
`5,018, 133 5/1991 Tsukakoshi et al. .
`... 370/85.13
`5,031,174 7/1991 Natsume ........................... 370/85.14
`OTHER PUBLICATIONS
`John M. McQuillan et al.; "The New Routing Algo
`rithm for the ARPANET'; IEEE vol. Com-28, No. 5;
`May 1980.
`E. W. Dijkstra; "A Note on Two Problems in Connex
`ion with Graphs"; Numerische Mathmatik, pp. 269-271
`1959.
`"Protocol for Providing the Connectionless-Mode Net
`work Service'; ISO 8473; Mar. 1987.
`"Intermediate system to Intermediate system In
`tra-Domain routeing exchange protocol for use in Con
`junction with the Protocol for providing the Connec
`tionless-mode Network Service'; ISO 10589; Oct. 15,
`1989.
`"Information processing systems-Telecommunications
`and information exchange between systems-End sys
`tem to Intermediate system routeing exchange protocol
`for use in conjunction . . . ;' ISO 9542; Mar. 26, 1988.
`"Internet Protocol," Darpa Internet Program, Protocol
`Specification; RFC 791; Sep. 1981.
`J. Postel; "Internet Control Message Protocol," Darpa
`
`
`
`
`
`Internet, Program Protocol Specification; RFC 792;
`Sep. 1981.
`R. Braden, J. Postel; “Requirements for Internet Gate
`ways,' RFC 1009; Jun. 1987.
`J. Moy; “The OSPF Specification," RFC 1131; Oct.
`1989.
`C. L. Hedrick, L. Bosack; "An Introduction to IGRP,'
`Jul. 26, 1989.
`Callon et al., "Routing in an Internetwork Environ
`ment,' pp. 4-9.
`Shoch et al., "Mutual Encapsulation of Internetwork
`Protocols," IEN 140, Apr. 1980.
`Primary Examiner-Douglas W. Olms
`Assistant Examiner-Min Jung
`Attorney, Agent, or Firm-Fish & Richardson
`(57)
`ABSTRACT
`A method for connecting a network so that TCP/IP
`and OSI 8473 packets may be routed in the same do
`main. The independence of the addresses is maintained:
`one device in the network may be assigned only a
`TCP/IP address, and another device may be assigned
`only a ISO 8473 address. Furthermore, all of the routers
`share link state information by using a common link
`state packet format (such as the ISO 10589 format); thus
`routes through the network may be computed without
`regard for the protocols supported by the routers along
`the route. Where necessary, packets are encapsulated
`and forwarded through routers which are not capable
`in the protocol of the packet. In some disclosed embodi
`ments, all of the routers in a given area support a given
`protocol (or, in fact, have identical capabilities, in
`which case encapsulation is not required). In these em
`bodiments, the encapsulation is performed by suitable
`modifications to each router's packet forwarding proce
`dures. In other disclosed embodiments, these topologi
`cal restrictions are removed, and the network is ex
`panded to support additional protocols. In these em
`bodiments, the Dijkstra algorithm is also modified to
`generate information on how to encapsulate and for
`ward packets through the network.
`
`24 Claims, 20 Drawing Sheets
`O OSIROUTER or END SYSTEM
`PROUTER of END SYSTEM
`o DUALIPIOS ROUTER
`
`Cloudflare - Exhibit 1078, page 1
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 1 of 20
`
`5,251,205
`
`WHISAS GN= 'o HalmOH ISO O
`
`WELLSÅS CINE JO HELT)OH c?|T
`
`
`
`Cloudflare - Exhibit 1078, page 2
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 2 of 20
`
`5,251,205
`
`1 1 O
`
`DELIVER PACKETTOES
`
`1 O2
`
`
`
`104
`
`O6
`
`1 O 8
`
`
`
`108
`
`
`
`
`
`1
`
`1
`
`
`
`112
`
`
`
`
`
`RECEIVE PACKET
`ADDRESSED TO
`END SYSTEMZ
`
`REVIEW LSP's
`TO DETERMINE
`ZS ROUTER
`( = ROUTERA)
`
`
`
`AM ROUTER A2
`NO
`FORWARD
`PACKETTOWARD
`ROUTERA
`
`FIG. 1B
`
`FORWARD
`PACKETTOWARD
`ROUTERA
`
`DETERMINE
`FIRST ROUTER
`N PATH TO A
`
`SEND PACKET
`ONLINK TO
`FIRST ROUTER
`N PATH TO A
`
`FIG. 1C
`
`Cloudflare - Exhibit 1078, page 3
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 3 of 20
`
`5,251,205
`
`
`WEIS?S GNB 10 HunOH ISO O
`
`
`WELLSÅS CINE JO HELLQOH CHI[]
`
`
`
`
`
`
`
`HELTTOH ISO/CHI TV/TMC)[5]
`
`Cloudflare - Exhibit 1078, page 4
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 4 of 20
`
`5,251,205
`
`
`
`38 '- || 1=Moš? ?AIBQ
`
`8 Z !
`
`ON
`
`SE OL92 ||
`
`
`
`ScHST NABIABH
`
`(V H-BLOOB =)
`EINIWNHELLECI O L
`
`HB 1 flOH SZ22 ||
`
`
`Z WELLSÅS CINE
`OLCESSE HOOV/02 ||
`
`
`
`Cloudflare - Exhibit 1078, page 5
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 5 of 20
`
`5,251,205
`
`126
`
`FORWARD PACKET
`TOWARD ROUTERA
`
`DETERMINE FIRST
`ROUTER IN
`PATH TO A
`
`133
`
`
`
`FIRST ROUTER
`N PATH TO A
`O
`
`34
`
`DUAL
`
`SPACKET P?
`
`No 136
`
`YES
`
`
`
`ENCAPSULATE -38 140
`PACKEN IP
`SEND PACKET
`HEADER. ADDRESS
`ONLINK TO
`TO AS DUMMY
`FIRST ROUTERN
`PEND SYSTEM
`PATH TOA
`
`IS PACKET. OSI?
`
`YES
`
`142
`
`No
`
`ENCAPSULATE
`PACKET NOS
`HEADER. ADDRESS
`TO AS DUMMY
`OSEND SYSTEM
`
`FIG. 2C
`
`Cloudflare - Exhibit 1078, page 6
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 6 of 20
`
`5,251,205
`
`
`
`s
`
`Cloudflare - Exhibit 1078, page 7
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 7 of 20
`
`5,251,205
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PLACE YOURSELF
`ATROOT OF
`ROUTING TREE
`
`18O
`
`PLACEYOUR
`NEIGHBORS BELOW
`YOUAS
`TENTATIVENODES
`
`182
`
`FIND CLOSEST
`TENTATIVENODE,
`MAKE PERMANENT
`
`ADO
`(CLOSER OR NEW)
`NEIGHBORS OF NEW
`NODE BELOW NEW
`NODEASTENTATIVE
`
`ARETHERE ANY
`TENTATIVENODES
`LEFT 2
`
`FG. 4A
`
`Cloudflare - Exhibit 1078, page 8
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 8 of 20
`
`5,251,205
`
`
`
`
`
`19 O
`
`Cloudflare - Exhibit 1078, page 9
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 9 of 20
`
`5,251,205
`
`PLACE YOUR
`NEIGHBORS BELOW
`YOUASTENTATIVE
`NODES
`
`182
`
`FIRST NEIGHBOR
`
`210
`
`212
`
`ISNEIGHBOR
`ALREADY TENTATIVE2
`
`YES
`
`NO
`
`218
`
`SEERTO "?"
`
`YES
`
`24
`S EXISTING
`TENTATIVE CLOSER
`(TiE BREAKER
`NO
`
`DELETE EXISTING
`TENTATIVE
`
`222
`
`
`
`
`
`NO DOES NEW NEIGHBOR 220
`SUPPORTOSI?
`
`21 6
`
`
`
`
`
`
`
`YES
`
`SET OSIFLAG
`
`
`
`NO
`
`DOES NEW NEIGHBOR
`SUPPORT P?
`
`221
`
`
`
`224
`
`
`
`YES
`
`CLEAR PFLAG
`
`SET PFLAG
`
`225
`
`226
`
`229
`
`NO
`
`MORENEIGHBORS
`LEFT2
`
`228
`
`YES
`
`F.G. 5B
`
`Cloudflare - Exhibit 1078, page 10
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 10 of 20
`
`5,251,205
`
`ADD(CLOSER OR NEW)
`NEIGHBORS OF NEW
`NODE BELOW NEW
`NODEASTENTATIVE
`
`186
`
`FIRST NEIGHBOR
`
`240
`
`SNEIGHBOR
`A READY
`PERMANENT
`NO
`244 ALEEve
`NO
`
`250
`
`SET ER, P, OSIFLAGS
`TO VALUES IN PARENT
`
`242
`
`246
`
`YES
`
`S EXISTING
`TENTATIVECLOSER YES
`TE BREAKER
`NO
`DELETE EXISTING
`TENTATIVE
`
`252
`
`NO
`
`248
`
`
`
`
`
`
`
`254
`
`260
`
`
`
`
`
`YES
`
`S PFLAG SET2
`
`YES
`
`256
`DOES NEIGHBOR
`SUPPORT IP?
`
`YES
`
`NO
`DOES NEW NEIGHBOR N2
`SUPPORTOSI?
`
`SEER TO
`PARENTS NAME
`
`262
`
`ADD NEIGHBOR
`TENTATIVELY
`
`264
`
`MORENEIGHBORS NO
`LEFT?
`
`265
`
`YES
`
`NEXT NEIGHBOR
`
`266
`
`FIG. 5C
`
`Cloudflare - Exhibit 1078, page 11
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 11 of 20
`
`5,251,205
`
`éudu=3SVYSLNOHUSI
`
`cu|882
`
`V8c
`
`VOLGassasyadv
`
`QayvaT
`
`OV1ddi
`
`
`
`NOLaxOWdGQHYYMYOs
`
`O1ANNLXAN
`
`ON
`
`élSOL3aHOVdSIOL2
`
`
`
`LayOVdGYUVMHOS
`
`
`
`VUSINOHGHYVMOL|gz}
`
`
`
`YAOVSHISOALVA
`
`
`HAQVSHISOALVAYO
`HAGVSHdi31VsaH9
`YAQVSHdiALWaYD
`
`SVYA.LNOYHOSHOSVYSLNOYMOSHO|Gauva1O
`98¢VHalnodc8e
`
`062
`
`
`
`L5xOVdGSLVINSdVONA
`
`
`
`LaNOVdALVINSdVONA
`
`
`
`QHVMdOd‘H30V3HNI
`
`OLNITLXANNO
`
`VHALNOY
`
`9‘Sis
`
`YaOLGS3SSSYHCdV
`
`3O1GaSSayudqv
`
`
`
`SVHALNOHSI
`
`é«én=YA
`
`BLc
`
`VOLaassayddy
`
`Cloudflare - Exhibit 1078, page 12
`
`Cloudflare - Exhibit 1078, page 12
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 12 of 20
`
`5,251,205
`
`
`
`HELLOOH ISO
`
`HELLÍTO}} di
`
`
`
`
`
`HELLOOH €d
`
`
`
`ISO-9d TV/TMC)
`
`HELITYOH
`
`bainoa NOV
`
`06 ||
`
`002
`
`Cloudflare - Exhibit 1078, page 13
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 13 of 20
`
`5,251,205
`
`PLACE YOUR
`NEIGHBORS BELOW
`YOUASTENTATIVE
`NODES
`
`182
`
`340 - FIRSTNEIGHBOR
`
`342
`
`SNEIGHBOR
`ALREADY TENTATIVE2
`
`NO
`
`344
`yes IS THE EXISTING
`TENTATIVE CLOSER2
`(TE BREAKER)
`NO
`
`ES
`
`
`
`NO DOES NEW NEIGHBOR
`SUPPORTOSI?
`
`DELETE EXISTING
`TENTATIVE
`
`YES
`
`SETOS FLAG
`
`350
`
`46
`3
`
`NO DOES NEW NEIGHBOR
`SUPPORT IP?
`
`352
`
`YES
`
`349
`
`353
`
`CLEAR PFLAG
`
`SET PFLAG
`
`354
`
`357
`
`NO DOES NEW NEIGHBOR
`SUPPORT P3?
`
`356
`
`YES
`
`CLEAR P3 FLAG
`
`SET P3 FLAG
`
`358
`
`NO
`
`MORENEIGHBORS
`LEFT?
`
`360
`
`364
`
`NEXT NEIGHBOR
`
`362
`
`FIG. 8B
`
`Cloudflare - Exhibit 1078, page 14
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 14 of 20
`
`5,251,205
`
`ADD(CLOSER OR NEW)
`NEIGHBORS OF NEW
`NODE BELOW NEW
`NODEASTENTATIVE
`
`186
`
`370
`
`FIRST NEIGHBOR
`
`SNEIGHBOR A READY
`PERMANENT
`37 2-
`NO
`SNEIGHBOR
`ALREADY TENTATIVE2
`
`374
`
`YES
`
`380
`
`SET OS, PP3 FLAGS
`st
`TO VALUES IN PARENT
`
`
`
`NO
`
`384
`
`NO
`
`390
`
`NO
`
`SOS FLAGSET2
`
`382
`
`YES
`DOES NEIGHBOR
`SUPPORTOS2
`
`N
`O
`
`ISP FLAG SET2
`YES
`DOESNEIGHBOR
`SUPPORT P?
`
`388
`
`No
`
`SP3 FLAG SET2
`
`394
`
`YES
`DOES NEIGHBOR
`SUPPORT P3?
`
`NO
`
`TENTATIVELY
`
`400
`
`LEFT2
`YES
`
`to
`
`4O6
`
`FIG. 8C
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`376
`
`ES
`S THE EXISTING
`TENTATIVE CLOSER2 TC
`(TE BREAKER)
`NO
`DELETE EXISTING
`TENTATIVE
`
`378
`
`CLEAR OS FLAG
`
`386
`392
`
`CLEARPFLAG
`
`398
`
`404
`
`cae
`
`Cloudflare - Exhibit 1078, page 15
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 15 of 20
`
`5,251,205
`
`FORWARD PACKET
`TOWARD ROUTERA
`
`126
`
`41 O
`
`CHECKROUTERA's
`OS FLAG
`
`CEAR
`
`SET
`
`FORWARD PACKET
`ONNEXT LINK
`TOA
`
`412
`
`408- IS PACKETOS1
`NO
`
`4 6
`
`LYES
`CLEAR CHECKROUTERA's
`EP FLAG
`
`IS PACKET P?
`
`is
`
`
`
`SET
`
`FORWARD PACKET
`ONNEXT LINK
`TOA
`
`418
`
`NO 414
`
`CHECK ROUTERAS
`P3 FLAG
`
`SET
`
`CLEAR
`
`420
`
`FORWARD PACKET
`ONNEXT LINK
`TOA
`
`422
`
`
`
`GETFLAGS OF
`A-PROTOCOL.
`ROUTER
`
`424
`
`426N ISOSIFLAGSET?
`
`432
`
`ENCAPSULATE IN
`PADDRESSTO
`ALL-PROTOCOL.
`
`
`
`YES
`
`434
`
`NN
`
`ENCAPSULATE IN 428
`OSIADDRESSTO
`ALL-PROTOCOL
`
`4. 3 O
`
`YES
`
`ENCAPSULATE IN
`P3ADDRESSTO
`ALL-PROTOCOL
`
`436
`
`SIP FLAGSET2
`
`SP3 FLAG SET2
`
`NO
`
`4.38
`
`GETFLAGS OF
`PARENNODE
`
`FG. 9
`
`Cloudflare - Exhibit 1078, page 16
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 16 of 20
`
`5,251,205
`
`190
`
`200
`
`192
`194
`196 - STATUS
`198-cost
`330
`332
`334
`
`
`
`440-s
`
`FIG. OA
`
`Cloudflare - Exhibit 1078, page 17
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 17 of 20
`
`5,251,205
`
`PLACE YOUR
`NEIGHBORS BELOW
`YOUASTENTATIVE
`NODES
`
`
`
`
`
`182
`
`340 - FIRSTNEIGHBOR
`
`
`
`344
`
`342
`
`SNEIGHBOR
`ALREADY TENTATIVE2
`
`YES IS THE EXISING
`TENTATIVE CLOSER7
`
`N
`O
`
`442 - SET EP TO "."
`
`N
`O
`
`DELETE EXISTING
`TENTATIVE
`
`349
`
`CLEAR OSIFLAG
`
`
`
`N O
`
`348
`
`DOES NEW NEIGHBOR
`SUPPORTOS?
`YES
`SEOS FLAG
`
`50
`3
`
`346
`
`N
`O DOES NEW NEIGHBOR
`SUPPORT P2
`
`352
`5
`
`54
`3
`
`356
`5
`
`58
`3
`
`6
`360
`
`362
`
`53
`3
`
`CLEARPFLAG
`
`YES
`SET PFLAG
`
`3
`57
`
`CLEAR P3 FLAG
`
`O
`N
`
`DOES NEW NEIGHBOR
`SUPPORT P3?
`YES
`SET P3 FLAG
`
`/
`
`NO
`
`MORENEIGHBORS
`LEFT?
`YES
`
`
`
`FIG. OB
`
`Cloudflare - Exhibit 1078, page 18
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 18 of 20
`
`5,251,205
`
`ADD(CLOSER OR NEW)
`NEIGHBORS OF NEW
`NODE BELOW NEW
`NODEASTENTATIVE
`
`186
`
`370
`
`FIRSTNEIGHBOR
`
`YES IS NEIGHBORALREADY
`PERMANENT2
`372
`NO
`SNEIGHBOR
`7
`374 NALREADYTENTATIVE?
`
`444
`
`SET FLAGS, ES
`TO VALUES IN PARENT
`
`
`
`
`
`
`
`
`
`39 O.
`
`NO
`
`
`
`
`
`
`
`
`
`ISOSIFLAGSET?
`YES
`
`DOES NEIGHBOR
`SUPPORTOSI?
`
`SIP FLAG SET2
`YES
`DOES NEIGHBOR
`SUPPORT IP?
`
`speFaest
`YES
`
`376
`
`YES
`
`IS THE EXISTING
`TENTATIVE CLOSER2
`
`YES
`
`NO
`ISTING
`DELE
`
`CLEAR OSFAG.
`SE EP TO "OS"
`
`386
`392
`
`CLEARPFLAG.
`SET EP TO "P"
`
`
`
`
`
`398
`
`388
`
`NO
`
`394
`
`396 DOESNEIGHBOR
`SUPPORT P3?
`
`NO
`
`CLEAR P3 FLAG.
`SET EP TO "P3"
`
`452 - AREANYFLAGSSET
`YES
`AODNEIGHBOR
`TENTATIVELY
`
`4 OO
`
`
`
`NO
`
`ADD EP, PARENT
`NAME TO END OFES.
`SET ALL FLAGS.
`
`NO
`
`MORENEIGHBORS
`LEFT2
`
`YES - NEXTNEIGHBOR
`
`404
`
`4O2
`
`FIG 10C
`
`4O6
`
`Cloudflare - Exhibit 1078, page 19
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 19 of 20
`
`5,251,205
`
`FORWARD PACKET
`TOWARD ROUERA
`
`126
`
`468
`
`456- is PACKETos?
`NO
`
`YES
`458
`
`CHECKROUTER ASSEI
`OS FLAG
`CEAR
`
`464
`
`SET
`
`CHECKROUTERA's
`PFLAG
`
`YES
`
`IS PACKET IP?
`
`CEAR
`
`CHECK PFLAG
`
`NO
`
`
`
`
`
`/
`466
`
`CHECKOSIFLAG
`
`
`
`CHECKOS FLAG
`
`
`
`
`
`ADO OSE HEAOER
`ADDRESSED TO A
`
`ADOP3 HEADER
`ADDRESSED TOA
`
`ADD PHEADER
`ADDRESSED TOA
`
`472
`
`47
`
`
`
`ADO HEADERS AND
`ADDRESSESNES.
`
`478
`
`FORWARD PACKET - 480
`TOFRSTNODE
`
`FIG 11
`
`Cloudflare - Exhibit 1078, page 20
`
`

`

`U.S. Patent
`
`Oct. 5, 1993
`
`Sheet 20 of 20
`
`5,251,205
`
`
`
`
`
`Routing Domain
`Net "17"
`
`Area
`Subnet "17. 133"
`"17. 133.43"
`
`Area
`Subnet "17.22"
`
`
`
`
`
`
`
`
`
`
`
`"17.13357"
`
`Area
`Subnet "17.42"
`
`F.G. 12
`
`Cloudflare - Exhibit 1078, page 21
`
`

`

`1.
`
`MULTIPLE PROTOCOL ROUTING
`
`15
`
`BACKGROUND OF THE INVENTION
`This invention relates to routing algorithms which
`support multiple protocols.
`The end systems (e.g., computers or printers) which
`form a computer network are interconnected by de
`vices known as routers. Each end system is attached to
`one of the network's routers and each router is responsi
`10
`ble for forwarding communications to and from its
`attached end systems.
`The routers transfer information to and from the end
`systems and among themselves along communications
`links in formatted packets. For example, when an origi
`nating end system wishes to transmit information to a
`destination end system, it generates a packet header in
`an appropriate format (this header includes, among
`other information, the address of the destination end
`system), and then fills the remainder of the packet with
`20
`the information to be transmitted. (In the following
`description, the term "user data packet' will refer to the
`entire packet, i.e. the formatted header and the informa
`tion that is to be transmitted from end system to end
`system.) The completed user data packet is then pro
`25
`vided to the router attached to (and responsible for) the
`originating end system, which forwards it toward the
`destination end system. Packets transmitted among the
`routers themselves (which will be referred to as "con
`trol packets') are similarly formatted and forwarded.
`30
`When a router receives a user data packet, it reads the
`user data packet's destination address from the user data
`packet header, and then transmits the user data packet
`on the link leading most directly to the user data pack
`et's destination. Along the path from source to destina
`35
`tion, a user data packet may be transmitted along sev
`eral links and pass through several routers, each router
`on the path reading the user data packet header and
`forwarding the user data packet accordingly.
`To determine how user data packets should be for
`40
`warded, each router typically knows the locations of
`the network's end systems (i.e., which routers are re
`sponsible for which end systems), the nature of the
`connections between the routers, and the states (e.g.,
`operative or inoperative) of the links forming those
`45
`connections. Using this information, each router can
`compute effective routes through the network and
`avoid, for example, faulty links or routers. A procedure
`for performing these tasks is generally known as a
`"routing algorithm'.
`In popular routing algorithms such as that described
`in "The New Routing Algorithm for the ARPANET'
`by McQuillan et al., IEEE Transactions on Communica
`tions, May, 1980, each router determines which end
`systems are attached to it, what links to other routers
`are available, the states of those links, and the identities
`of the routers on the other ends of those links. To initial
`ize the network, each router places this information in a
`control packet known as a Link State packet (LSP), and
`transmits this. LSP to all of the other routers in the
`network (i.e., "advertises' its neighbors and end sys
`tems to the network). Later, when changes in the net
`work occur (e.g., a link fails), one or more routers may
`generate new LSPs which supersede previously gener
`ated LSPs.
`65
`As long as the most recent LSPs are propagated
`reliably to all of the routers, each router will have com
`plete information about the topology of the network
`
`5,251,205
`2
`and can generate a routing database describing routes
`through the network (for example, using the algorithm
`described in "A Note on Two Problems in Connexion
`with Graphs" by Edsgar Dijkstra, Numerische Math
`ematik, Vol. 1, 1959, pages 269-271).
`In order for user data packets to be delivered to their
`destinations, each end system on the network must have
`an unambiguous address. There are several independent
`standards organizations which document and promul
`gate address allocation schemes, as well as control and
`user data packet formats which may be used for com
`municating under these schemes. Several networks of
`routers have been configured according to these ad
`dressing schemes and formats.
`In what follows, the term "routing protocol' will be
`used to describe the combination of an address alloca
`tion scheme and a format (or a group of related formats)
`that describes control packets and other information to
`be exchanged among routers, and which is used to cal
`culate the paths which the user data packets will take
`between routers. Routing protocols are often associated
`with their own routing algorithms, each routing algo
`rithm being documented and promulgated by the stan
`dards organization responsible for the associated rout
`ing protocol.
`Further, the term "protocol suite' will be used to
`describe the comprehensive set of protocols that is de
`signed to work together to coherently provide com
`plete communication capabilities. Two examples of
`protocol suites are the TCP/IP protocol suite and the
`OSI protocol suite. Each of these protocol suites in
`cludes one or more network layer protocols which
`define the format used for control and user data packets
`that are to be transferred by the network routers. For
`example, the IP protocol of the TCP/IP protocol suite
`defines the network layer protocol which makes up the
`format of the user data packets that are forwarded by
`the IP routers. Similarly, the OSI routers forward user
`data packets following the ISO 8473 network layer
`protocol.
`The Transmission Control Protocol (TCP) RFC 793,
`Internetwork Protocol (IP) RFC 791, the Internet Con
`trol Message Protocol RFC 792, and the TCP/IP pro
`tocol suite which is described in RFC 1122, "Require
`ments for Internet Hosts-Communication Layers,'
`RFC 1123, "Requirements for Internet Hosts-Ap
`plication and Support,' RFC 1100, "IAB Official Pro
`tocol Standards,” and RFC 1009, "Requirements for
`Internet Gateways,' and associated other RFCs, all
`available from SRI International, DDN Network Infor
`mation Center, Room EJ291, 333 Ravenswood Avenue,
`Menlo Park, Calif. 94025, have recently been growing
`in importance as a multi-vendor communications archi
`tecture, and many networks are based on them.
`(TCP/IP terminology refers to routers as "gateways',
`and end systems as "hosts'.) At the same time, how
`ever, existing networks also use the Open Systems In
`terconnection (OSI) protocols such as described in In
`ternational Organization for Standardization (ISO)
`7498, "Information Processing Systems-Open Systems
`Interconnection-Basic Reference Model,' ISO 8473,
`"Protocol for Providing the Connectionless-mode Net
`work Service,' ISO 9542, "End System to Intermediate
`System Routing Exchange Protocol," and ISO DP
`10589 "Intermediate System to Intermediate System
`Intradomain Routing Exchange Protocol," all available
`from BSi Standards, 2 Park Street, London England,
`
`50
`
`55
`
`Cloudflare - Exhibit 1078, page 22
`
`

`

`O
`
`5,251,205
`3
`4.
`W1A2BS, and more are expected to be created as OSI
`managing multiple independent networks is less effi
`is further developed.
`cient than configuring and managing a single integrated
`Because the several existing protocols (in particular
`network of the same total size; multiple networks must
`TCP/IP and OSI) have been developed independently,
`be configured independently, increasing overhead; and
`they are largely incompatible.
`multiple networks cannot be managed as efficiently as a
`Networks having incompatible protocols cannot
`single network because the implicit interactions be
`make their links and routers available to each other,
`tween the networks (such as the shared loads placed on
`which may result in excess redundancy and reduced
`routers and links) cannot be well characterized and
`efficiency. Also, each of the networks must be main
`controlled.
`tained independently, increasing the total management
`SUMMARY OF THE INVENTION
`effort over what would be required by a single, univer
`sally compatible network.
`In one aspect, the invention features a method of
`One known way to share routing resources among
`calculating routes for sending user data packets through
`networks having incompatible protocols is known as
`an interconnected network of information handling
`gateway encapsulation. In gateway encapsulation, a
`devices. Each of the user data packets includes destina
`15
`network using protocol A is provided with a path
`tion address information conforming to an addressing
`through a second network that uses protocol B. To
`convention of any one of two or more different inde
`form the path, two routers are manually configured to
`pendent protocol suites. The routes for user data pack
`provide gateways from protocol A to protocol B, and
`ets are always calculated using a single route calculation
`back.
`algorithm corresponding to the same routing protocol
`20
`Each gateway router is configured to be fluent in
`(which is chosen from an arbitrary protocol suite) re
`both protocol A and protocol B. When a user data
`gardless of the addressing convention to which the user
`packet formatted in protocol A is received, at a gateway
`data packet conforms. This calculation does not involve
`router, the gateway router "encapsulates' the user data
`converting the destination information from one ad
`packet in a protocol B header (i.e., generates a protocol
`dressing convention to another.
`25
`B header and places the protocol A user data packet,
`Preferred embodiments of this aspect include the
`including the protocol A header, into the data area of
`following features.
`the protocol B user data packet). The encapsulated
`There are exactly two protocol suites.
`protocol A user data packet is then addressed to the
`Link state packets conforming to the routing proto
`second gateway router, and transmitted through the
`col used to compute routes are sent to the information
`protocol B network.
`handling devices, and routes are calculated based on
`When the encapsulated protocol A user data packet is
`information contained in the link state packets.
`received at the second gateway router, the protocol B
`The OSI IS-IS routing protocol is used to compute
`encapsulation header is removed, and the protocol A
`routes.
`user data packet is forwarded to its destination through
`In another aspect, the invention features a method for
`35
`the protocol A network.
`calculating routes for sending user data packets via
`The routing algorithm used in the protocol A net
`information handling devices which are interconnected
`work is suitably modified to make the protocol A rout
`in a communications network. The information han
`ers aware of the gateway, so that user data packets
`dling devices include (a) single-protocol information
`destined to routers at the other end of the gateway are
`handling devices capable of recognizing and forward
`forwarded to one of the gateway routers.
`ing only user data packets which conform to a single
`One disadvantage of gateway encapsulation is that
`protocol suite, and (b) multi-protocol information han
`the gateway must be manually configured, and thus
`dling devices capable of recognizing and forwarding
`must also be manually maintained. If a change to the
`user data packets which conform to any one of two or
`gateway path is desired, or if an additional gateway
`more protocol suites. A routing protocol is used to
`45
`path is added, the gateway routers must be manually
`automatically predetermine at which information han
`adjusted to effect the desired changes. Furthermore, the
`dling devices to encapsulate and to decapsulate a given
`gateway path is only available to the protocol A net
`packet.
`work as long as the gateway routers themselves are
`Preferred embodiments of this aspect include the
`operational. If a gateway router fails, the pre-estab
`following features.
`lished path through the protocol B network is severed,
`The information handling devices are organized in
`and communications must be re-routed through the
`areas and all of the information handling devices within
`protocol A network.
`a single area are at least capable of recognizing and
`Another way to route multiple incompatible proto
`forwarding user data packets which conform to the
`cols is known as "ships in the night” (SIN). In the SIN
`same one of the protocol suites. This common protocol
`55
`approach, the same physical resources (e.g., routers and
`suite may be different for different areas.
`links) are used to route completely separate protocols.
`A given area may include (a) single-protocol informa
`The shared resources multiplex between the supported
`tion handling devices capable of recognizing and for
`protocols, and the protocols themselves operate more
`warding only user data packets which conform to a first
`or less independently.
`protocol suite, (b) single-protocol information handling
`With SIN, there is some degree of competition for
`devices capable of recognizing and forwarding only
`resources, because implementing two protocols requires
`user data packets which conform to a second different
`additional programming time as well as additional CPU
`protocol suite, and (c) at least one multi-protocol infor
`and memory resources in the routers. Furthermore,
`nation handling device capable of recognizing and
`SIN requires that two complete sets of control packets
`forwarding user data packets which conform to the first
`be distributed through the two independent networks,
`and second protocol suite (and/or every other protocol
`which doubles the control traffic overhead over that of
`suite that is used by any other information handling
`a single integrated network. Finally, configuring and
`device in the area).
`
`30
`
`50
`
`65
`
`Cloudflare - Exhibit 1078, page 23
`
`

`

`O
`
`15
`
`5,251,205
`5
`6
`There are exactly two protocol suites, one which is
`FIG. 8A is a diagram of a data structure of the rout
`the TCP/IP protocol suite and another which is the
`ing tree of FIG. 4B as used in a dual-protocol router of
`OSI protocol suite.
`FIG 7B.
`Link state packets conforming to the routing proto
`FIG. 8B is a flow diagram of an algorithm for initial
`col used to compute routes are sent to the information 5
`izing the routing trees in the dual-protocol routers of
`handling devices, and routes are calculated based on
`FIG. 7B.
`information contained in the link state packets.
`FIG. 8C is a flow diagram of an algorithm for build
`The OSI IS-IS routing protocol is used to compute
`ing the routing trees in the dual-protocol routers of
`routes and determine at which information handling
`FIG. 7B.
`devices to encapsulate and to decapsulate.
`FIG. 9 is a flow diagram of the user data packet
`forwarding algorithm to be followed by the dual
`In another aspect, the invention features a method of
`protocol routers of FIG. 7B.
`enabling user data packets to be forwarded from one
`FIG. 10A is a diagram of a data structure of the rout
`local area network to another by a device which is
`ing tree of FIG. 4B as used in the all-protocol router of
`capable of acting as a router to recognize and forward
`FIG. 7B.
`user data packets which conform to a first protocol suite
`FIG. 10B is a flow diagram of an algorithm for initial
`and is capable of acting as a bridge to recognize and
`izing the routing tree in the all-protocol router of FIG.
`forward user data packets which conform to at least a
`7B.
`second protocol suite. For a user data packet which
`FIG. 10C is a flow diagram of an algorithm for build
`conforms to the first protocol suite and is addressed to
`ing the routing tree in the all-protocol router of FIG.
`20
`a single address which is not an address of the device,
`7B.
`the devices acts as a bridge rather than as a router.
`FIG. 11 is a flow diagram of the user data packet
`Other features and advantages of the invention will
`forwarding algorithm to be followed by the all-protocol
`be apparent from the following description of the pre
`router of FIG. 7B.
`ferred embodiments and from the claims.
`FIG. 12 illustrates a common area structure.
`25
`DESCRIPTION OF THE PREFERRED
`FIG. 13 illustrates a brouter.
`EMBODIMENTS
`GENERAL DESCRIPTION
`We first briefly describe the drawings.
`Before discussing the invention, it will be useful to
`FIG. 1A is a diagram of a dual-protocol network 30
`define some terminology.
`segregated on a per-area basis which does not require
`A router that is fluent in only one of the protocols
`encapsulation.
`supported by the multi-protocol network will be gener
`FIG. 1B is a flow diagram of the user data packet
`ally referred to as a "single-protocol' router. Where
`receiving algorithm to be followed by the routers of
`necessary, the protocol supported by a single-protocol
`FIG. A.
`router may be indicated by explicit reference to the
`35
`FIG. 1C is a flow diagram of the user data packet
`protocol. For example, a single-protocol router which
`forwarding algorithm to be followed by the routers of
`is fluent in only protocol P1 may be referred to as a
`FIG. 1A.
`"P1-only" router.
`FIG. 2A is a diagram of a dual-protocol network
`Routers that are fluent in more than one of the sup
`segregated on a per-area basis which requires encapsu- 40
`ported protocols interconnect the dissimilar single
`lation.
`protocol routers. A router that is fluent in more than
`FIG. 2B is a flow diagram of the user data packet
`one of the supported protocols will be generally re
`receiving algorithm to be followed by the dual-protocol
`ferred to as a "multi-protocol' router. Routers that are
`routers of FIG. 2A.
`fluent in two protocols will be referred to as "dual
`FIG. 2C is a flow diagram of the user data packet 45
`protocol" routers; routers that are fluent in three proto
`forwarding algorithm to be followed by the dual
`cols will be referred to as "three-protocol" routers, and
`protocol routers of FIG. 2A.
`so on. Multi-protocol routers that are fluent in all of the
`FIG. 3 is a diagram of a dual-protocol network which
`protocols supported by a given network will be referred
`is not segregated on a per-area basis.
`to as "all-protocol' routers. (Note that where only two
`FIG. 4A is a flow diagram of an algorithm used to 50
`protocols are supported, the terms multi-protocol, dual
`build routing trees.
`protocol, and all-protocol are synonymous; however,
`FIG. 4B is a diagram of a routing tree.
`this synonymity does not apply when more than two
`FIG. 5A is a diagram of a data structure of the rout
`protocols are supported.)
`ing tree of FIG. 4B as used in a dual-protocol router of
`There are two types of multi-protocol routers. A
`FIG. 3.
`"simple multi-protocol router". will route user data
`55
`FIG. 5B is a flow diagram of an algorithm for initial
`packets conforming to two or more protocols. How
`izing the routing trees in the dual-protocol routers of
`ever, a simple multi-protocol router is only able to for
`FIG. 3.
`ward the user data packets; it is not able to perform
`FIG. 5C is a flow diagram of an algorithm for build
`encapsulation or decapsulation to make user data pack
`ing the routing trees in the dual-protocol routers of 60
`ets in one protocol compatible with another protocol.
`FIG. 3,
`An "enhanced multi-protocol router' will not only
`FIG. 6 is a flow diagram of the user data packet
`route user data packets conforming to two or more
`forwarding algorithm to be followed by the dual
`protocols, but is also able to perform encapsulation or
`protocol routers of FIG. 3.
`decapsulation to make user data packets in one protocol
`FIG. 7A illustrates a three-protocol network which 65
`compatible with anot