United States Patent (19)
`Callon
`
`54 MULTIPLE PROTOCOL ROUTING
`75 Inventor:
`Ross W. Callon, Bedford, Mass.
`73) Assignee:
`Digital Equipment Corporation,
`Maynard, Mass.
`21 Appl. No.: 245,856
`22 Filed:
`May 19, 1994
`
`60
`
`Related U.S. Application Data
`Continuation of Ser. No. 59,641, May 10, 1993, aban
`doned, which is a division of Ser. No. 577,437, Sep. 4,
`1990, Pat. No. 5,251,205.
`Int. Cl. ............................................. HO4L 12/46
`51
`52 U.S. C. ................................. 370/85.13; 370/94.1
`58) Field of Search.................... 370/85.13, 85.14, 54,
`370/94.1
`
`56
`
`References Cited
`U.S. PATENT DOCUMENTS
`Re. 31,182 3/1983 Crager et al. .................... 340/825.5
`4,27,507 6/1981 Gable et al. ........................ 370/94.1
`4,316,283 2/1982 Ulug ...............
`37094.1
`4,577.34 3/1986 Chu et al. ...
`... 370/60
`4,706,08 11/1987 Hart et al...
`... 370/61
`4,755,992 7/1988 Albal .................................. 370/94.1
`4,760,395 7/1988 Katzeff et al. .
`340/825.03
`4,766,591 8/1988 Huang.........
`... 370/60
`4,768, 190 8/1988 Giancario .......
`... 370/85.15
`4,831,620 5/1989 Conway et al.
`34Ow825.05
`4,893,307 1/1990 McKay et al. ..................... 370/94.
`4,897,841 1/1990 Gang, Jr. ...
`370/85.13
`4,901,312 2/1990 Hui et al. ...........
`... 370/85.14
`5,018,133 5/1991 Tsukakoshi et al.
`... 370/85.13
`5,031, 174 7/1991 Natsume ........................... 370/85.14
`OTHER PUBLICATIONS
`"Information Processing Systems-Open Systems In
`terconnection-Basic Reference Model', International
`Standard, ISO 7498–1984 (E), pp. 1-39.
`“IAB Official Protocol Standards', Internet Activities
`Board, Apr. 1989, pp. 1-14.
`"Transmission Control Protocol', Darpa Internet Pro
`gram, Protocol Specification, edited by Jon Postel,
`Sep., 1981, pp. i-iii, 1-85.
`"Requirements for Internet Hosts-Communication
`
`
`
`III IIHHHHHHHHH
`USOO543O727A
`11
`Patent Number:
`5,430,727
`45
`Date of Patent:
`Jul. 4, 1995
`
`Layers”, Internet Engineering Task Force, edited by R.
`Braden, Oct., 1989, pp. 1-116.
`“Requirements for Internet Hosts-Application and
`Support", Internet Engineering Task Force, edited by
`R. Braden, Oct., 1989, pp. 1-98.
`Braden, R. and J. Postel, "Requirements for Internet
`Gateways", RFC 1009, Jun. 1987.
`Callon et al., “Routing in Internetwork Environment',
`pp. 4-9.
`Djikstra, E. W., “A Note on Two Problems in Connex
`ion with Graphs", Numerische Matematki, pp. 269-271,
`1959.
`
`(List continued on next page.)
`Primary Examiner-Douglas W. Olms
`Assistant Examiner-Min Jung
`Attorney, Agent, or Firm-Fish & Richardson
`
`ABSTRACT
`57
`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 en
`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.
`8 Claims, 20 Drawing Sheets
`O OS ROUTER or END SYSTEM
`PRER of ENSSE
`
`Cloudflare - Exhibit 1079, page 1
`
`

`

`5,430,727
`Page 2
`
`OTHER PUBLICATIONS
`Hendrick, C. L. and L. Boasack, "An Introduction to
`IGRP', Jul. 26, 1989.
`McQuillan, John, et al., "The New Routing Algorithm
`for the ARPANET.", IEEE, vol. Com-28, No. 5, May
`1980.
`Moy, J., “The OSPF Specification", RFC 1131, Oct.
`1989.
`Postel, J., “Internet Control Message Protocol",
`DARPA Internet, Program Protocol Specification,
`RFC 792, Sep. 1981.
`Shoch et al., "Mutual Encapsulation of Internetwork
`Protocols', IEN 140, Apr. 1980.
`
`"Protocol for Providing the Connectionless-Mode Net
`work Service', ISO 8473, Mar. 1987.
`"Intermediate System to Intermediate System In
`tra-Domain Routing Exchange Protocol for Use in
`Conjunction with the Protocol for Providing the Con
`nectionless-Mode Network Service', ISO 10589, Oct.
`15, 1989.
`"Information Processing Systems-Telecommunications
`and Information Exchange between Systems-End Sys
`tem to Intermediate System Routing Exchange Proto
`col for Use in Conjunction ... ', ISO 9542, Mar. 26,
`1988.
`"Internet Protocol', DARPA Internet Program, Proto
`col Specification, RFC 791, Sep. 1981.
`
`Cloudflare - Exhibit 1079, page 2
`
`

`

`U.S. Patent
`
`July 4
`
`s
`
`1995
`
`Sheet 1 of 20
`
`5,430,727
`
`
`
`
`WBISAS GNB 10 HunOH ISO O
`
`WELLSÅS CINE JO HELLOOH c?|T
`
`
`
`
`
`
`
`BELTlOH. ISO/CHI TV/TMCI[5]
`
`Cloudflare - Exhibit 1079, page 3
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 2 of 20
`
`5,430,727
`
`1 10
`
`DELIVER PACKETTOES
`
`
`
`1 O2
`
`
`
`
`
`RECEIVE PACKET
`ADDRESSED TO
`END SYSTEMZ
`
`
`
`1 O4
`
`1 O6
`
`108
`
`
`
`108
`
`
`
`
`
`1 1
`
`
`
`112
`
`REVIEW LSP'S
`TO DETERMINE
`ZS ROUTER
`(= ROUTERA)
`
`
`
`AM ROUTER A2
`NO
`FORWARD
`PACKETTOWARD
`ROUTERA
`
`FIG. 1B
`
`FORWARD
`PACKETTOWARD
`ROUTERA
`
`DETERMINE
`FIRST ROUTER
`IN PATH TO A
`
`SEND PACKET
`ONLINKTO
`FIRST ROUTER
`N PATH TO A
`
`FIG. 1C
`
`
`
`
`
`
`
`Cloudflare - Exhibit 1079, page 4
`
`

`

`U.S. Paten
`t
`
`July 4, 1995
`
`Sheet 3
`of 20
`
`5,430,727
`
`O
`
`i i
`,
`; :
`3 2
`9 S
`if
`5 3
`5
`in
`3 it
`is
`in
`a
`O o
`
`
`
`
`
`3
`
`Cloudflare - Exhibit 1079, page 5
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 4 of 20
`
`5,430,727
`
` ZWALSASONS
`ALVINSdVONASIO
`YH3ANsSd
`AWWNGLISIvet
`
`
`
`L3y0VdAAI303Y
`
`OLGassauddvOcl
`
`
`
`8dS7MalAaY
`
`SINIWYSL30OL
`
`(¥YS.LNOH=)
`
`HALNOH$Z
`
`ool
`
`éWALSASON3
`
`éVY3ALNOY|WV
`
`ON
`
`L3anOVd
`
`
`
`LaxOVdGHVWMeOs
`
`deSis
`
`
`
`VHALLNOYGHWMOL
`
`91
`
`Cloudflare - Exhibit 1079, page 6
`
`Cloudflare - Exhibit 1079, page 6
`
`
`
`
`
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 5 of 20
`
`5,430,727
`
`126
`
`FORWARD PACKET
`TOWARD ROUTERA
`
`DETERMINE FIRST
`ROUTER IN
`PATH TOA
`
`133
`
`
`
`
`
`P
`134
`
`FIRST ROUTER
`IN PATH TO A
`
`No
`
`3 LYS
`
`
`
`ENCAPSULATE - 38
`PACKET INP
`HEADER, ADDRESS
`TO AS DUMMY
`IP END SYSTEM
`
`142
`
`No
`
`ENCAPSULATE
`PACKET IN OS
`HEADER, ADDRESS
`TO AS DUMMY
`OSEND SYSTEM
`
`1
`
`140
`SENDPACKE
`ONLINKO
`FIRST ROUTER IN
`PATH TO A
`
`FIG. 2C
`
`Cloudflare - Exhibit 1079, page 7
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 6 of 20
`
`5,430,727
`
`
`
`Cloudflare - Exhibit 1079, page 8
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 7 of 20
`
`5,430,727
`
`PLACE YOURSELF
`ATROOTOF
`ROUTINGREE
`
`18O
`
`PACE YOUR
`NEIGHBORS BELOW
`YOUAS
`TENTATMENODES
`
`182
`
`FIND CLOSEST
`TENTATIVENODE,
`MAKE PERMANENT
`
`ADD
`(CLOSER OR NEW)
`NEIGHBORS OF NEW
`NODEBELOW NEW
`NODEASTENTATIVE
`
`
`
`ARETHERE ANY
`TENAMENODES
`LEFT
`
`184
`
`186
`
`188
`
`FIG. 4A
`
`Cloudflare - Exhibit 1079, page 9
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 8 of 20
`
`5,430,727
`
`187
`
`187
`
`187
`
`187
`
`89
`
`
`
`Cloudflare - Exhibit 1079, page 10
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 9 of 20
`
`5,430,727
`
`PLACE YOUR
`NEIGHBORS BELOW
`YOUASTENTATIVE
`NODES
`
`182
`
`FIRSTNEIGHBOR
`
`
`
`21 O
`
`
`
`
`
`
`
`
`
`
`
`SNEIGHBOR
`212 ALREADYTENTATIVE
`
`YES
`
`NO
`
`218
`
`SETERTO "?"
`
`214
`
`YES
`
`IS EXISTING
`TENTATIVE CLOSER2
`IE BREAKER
`NO
`
`DELETE EXISTING
`TENTATIVE
`
`222
`
`No DOESNEWNBGHBOR 220 216
`SUPPORTOSI?
`
`YES
`
`CLEAR OS FLAG
`
`221
`
`No DOESNEW NEIGHBOR
`SUPPORT IP?
`
`224
`
`CLEARPFLAG
`
`
`
`SET PFLAG
`
`226
`
`as
`
`229
`
`FIG. 5B
`
`
`
`
`
`
`
`
`
`Cloudflare - Exhibit 1079, page 11
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 10 of 20
`
`5,430,727
`
`ADD(CLOSER OR NEW)
`NEIGHBORS OF NEW
`NODEBELOW NEW
`NODEASTENTATIVE
`
`186
`
`FIRSNEIGHBOR
`
`24 O
`
`
`
`
`
`
`
`
`
`
`
`YES
`
`SNEIGHBOR
`A READY
`PERMANENT
`NO
`
`242
`
`246
`
`YES
`IS EXISTING
`'Alive TENTATIVEcoSER YES
`E BREAKER
`NO
`NO
`
`TO VALUES IN PARENT
`
`TENTATIVE
`
`NO
`
`248
`
`YES
`
`256
`
`254
`
`SIP FLAG SETP
`
`YES
`
`DOES NEIGHBOR
`SUPPORT PP
`
`YES
`
`NO
`DOESNEW NEGHBOR ND
`SUPPORTOS2
`
`26 O
`
`SEERTO
`PARENTS NAME
`
`262
`
`ADO.NEGHBOR
`
`MORENEIGHBORS NO
`LEFT
`
`YES
`
`265
`
`Cloudflare - Exhibit 1079, page 12
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 11 of 20
`
`5,430,727
`
`
`
`
`
`HECIVEH ISO EL1\/EHO
`
`
`
`VOLGESSE HOON/
`
`062
`
`
`
`HE OLOESSE HOON/
`
`
`
`
`
`HECÍVEH ISO ELIVEHO
`
`ON
`
`
`
`
`
`& ISO LEXIOWEJ SI0./. Z
`
`w HB InOHGHWMOL | _ ga |
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`9 / 2
`
`\/EELITOH
`
`282SEW
`
`
`
`
`
`HE OLCESSE HOON/VOLOESSE HOON/
`
`082
`
`Cloudflare - Exhibit 1079, page 13
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 12 of 20
`
`5,430,727
`
`
`ISO-dl-EdJSYWHL
`wanoaYOV
`
`\/
`
`dOHSul
`
`
`ISO-di1wNd
`YaLNOYEdVlO)LO
`
`Y3LNOYISO
`YALNOYdi
`
`HALLNOW
`
`dl-€dWwnd
`Y=LLNOY
`WV
`
`
`
`Cloudflare - Exhibit 1079, page 14
`
`Cloudflare - Exhibit 1079, page 14
`
`
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 13 of 20
`
`5,430,727
`
`PLACEYOUR
`NEIGHBORS BELOW
`YOUASTENTATIVE
`NODES
`
`182
`
`340 - FIRSTNEIGHBOR
`
`
`
`342
`
`SNEIGHBOR
`ALREADY TENTATIVE
`
`NO
`
`NO DOES NEW NEIGHBOR
`SUPPORTOS2
`
`YES
`
`setosfag
`
`1350
`
`346
`
`349
`
`clearos rag
`
`353
`
`357
`
`NO DOESNEWNEGHBOR
`SUPPORT IP?
`YES
`
`352
`
`NO DOES NEW NEIGHBOR 356
`SUPPORT P3?
`YES
`
`CLEAR P3 FLAG
`
`SET P3 FLAG
`
`358
`
`
`
`
`
`
`
`NO MORENEGHBORS
`LEFT?
`
`
`
`YES
`
`364
`
`FIG. 8B
`
`Cloudflare - Exhibit 1079, page 15
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 14 of 20
`
`5,430,727
`
`ADD(CLOSER OR NEW)
`NEIGHBORSOF NEW
`NODE BELOW NEW
`NODEASTENTATIVE
`
`186
`
`SNEIGHBOR
`
`
`
`yes
`
`is THE EXISTING
`
`ES
`
`380 - SET OSI,IPP3FLAGS
`TO VALUESN PARENT
`
`NO
`
`384
`
`isos FLAG set
`YES
`DOESNEGHBOR
`
`NO
`EXISTING
`DEE.
`
`382
`
`378
`
`NO
`
`OS
`
`NO
`
`NO
`
`YES
`DOESNEGHBOR
`SUPPORT IP?
`ES
`
`s
`
`is parl Aast
`YES
`
`388
`
`NO
`
`394
`
`DOESNEGHBOR
`
`NO
`
`YES
`
`386
`392
`
`CLEARPFLAG
`
`398
`
`CEAR P3 FLAG
`
`
`
`
`
`
`
`Cloudflare - Exhibit 1079, page 16
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 15 of 20
`
`5,430,727
`
`E.
`
`126
`
`41 O
`CHECKROUTERA's CEAF
`OSFLAG
`SET
`
`408- Is Packerosi
`NO
`
`YES
`
`416
`
`CLEAR CHECKROUTERAS YES S PACKE IP?
`PFLAG
`
`SET
`
`NO 414
`
`HECKROUTERAs CEAR
`P3 FLAG
`
`FORWARD PACKET
`ONNEXT INK
`TOA
`412
`
`432
`
`426 Nisosaess. YES
`NO
`
`ENCAPSUAE IN
`PADDRESSTO
`A PROTOCOL
`
`YES
`
`434
`
`SIP FLAG SET2 430
`NO
`sparest. YES
`NO
`
`
`
`438
`
`GEFLAGSOF
`PARENTNODE
`
`ENCAPSULATEN
`
`436
`
`FIG. 9
`
`Cloudflare - Exhibit 1079, page 17
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 16 of 20
`
`5,430,727
`
`
`
`192
`FIRST NODE
`194
`196 - STATUS
`1 98-COST
`330
`OSFLAG
`332
`334
`440
`
`190
`
`2OO
`
`FIG. 1 OA
`
`Cloudflare - Exhibit 1079, page 18
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 17 of 20
`
`5,430,727
`
`PLACEYOUR
`NEGHBORS BELOW
`YOUASTENTATIVE
`NODES
`
`182
`
`340 - FIRSTNEIGHBOR
`
`344
`
`SNEIGHBOR
`342 ALREADYTENTATIVE
`
`YES IS THE EXISTING
`TENTAME CLOSER
`
`ES
`
`NO
`
`NO
`
`TENTATIVE
`
`346
`
`349
`
`NO DOES NEW NEIGHBOR
`SUPPORTOSI?
`YES
`
`CLEAROS FLAG
`
`SETOS FLAG
`
`350
`
`
`
`35
`
`NO DOES NEW NEIGHBOR
`SUPPORT IP?
`
`352
`
`CLEARPFLAG
`
`SETIP FLAG
`
`354
`
`357
`
`SUPPORT P3?
`YES
`
`NO
`
`MORENEIGHBORS
`LEFT2
`YES
`NEXTNEGHBOR
`
`360
`
`362
`
`364
`
`Cloudflare - Exhibit 1079, page 19
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 18 of 20
`
`5,430,727
`
`ADD(CLOSEROR NEW)
`NEGHBORSOF NEW
`NODEBELOWNEW
`NODEASTENTAME
`
`186
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`YES
`384 DOESNEGHBOR
`SUPPORTOS
`
`NO
`
`NO
`
`ES
`SPFLAGSET2
`YES
`
`DOESNEGHBOR
`SUPPORT IP?
`ES
`
`is parl Aest
`YES
`
`NO
`
`CLEAROS FAG.
`SETEPTO"OS"
`
`388
`
`NO
`
`394
`
`386
`
`392
`
`CLEARPFLAG,
`SETEPTO"IP"
`
`398
`
`DOESNBGHBOR
`SUPPORT P3?
`
`NO
`
`CLEARP3 FLAG.
`SET EP TO "P3
`
`ADDEP, PARENT
`NAMETOEND OFES.
`SETALFAGS.
`
`FIG. 10C
`
`Cloudflare - Exhibit 1079, page 20
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 19 of 20
`
`5,430,727
`
`
`
`
`
`
`
`CHECKIPFLAG
`
`
`
`ADOHEADERS AND
`ADDRESSESNES.
`
`480
`
`FIG. 11
`
`Cloudflare - Exhibit 1079, page 21
`
`

`

`U.S. Patent
`
`July 4, 1995
`
`Sheet 20 of 20
`
`5,430,727
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Routing Domain
`Net "17
`
`Area
`Subnet "17.33"
`"17. 133.43"
`
`Area
`Subnet "17.22"
`
`
`
`17. 133.5
`
`"17.133.57"
`
`
`
`Area
`Subnet "17.42"
`
`FIG. 12
`
`Cloudflare - Exhibit 1079, page 22
`
`

`

`1.
`
`MULTIPLE PROTOCOL ROUTING
`
`This is a continuation of application Ser. No.
`08/059,641, filed May 10, 1993, now abandoned, which 5
`was a divisional of Ser. No. 07/577,437, filed Sep. 4,
`1990, now issued as U.S. Pat. No. 5,251,205.
`BACKGROUND OF THE INVENTION
`This invention relates to routing algorithms which 10
`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- 15
`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- 20
`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 25
`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- 30
`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. 35
`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- 40
`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- 45
`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 50
`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'.
`55
`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 60
`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 65
`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
`
`5,430,727
`2
`generate new LSPs which supersede previously gener
`ated LSPs.
`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
`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 Applica
`tion and Support,” RFC 1100, "IAB Official Protocol
`Standards,” and RFC 1009, "Requirements for Internet
`Gateways,” and associated other RFCs, all available
`from SRI International, DDN Network Information
`Center, Room EJ291, 333 Ravenswood Avenue, Menlo
`Park, Calif. 94025, have recently been growing in in
`portance as a multi-vendor communications architec
`ture, and many networks are based on them. (TCP/IP
`terminology refers to routers as "gateways', and end
`systems as "hosts”.) At the same time, however, existing
`networks also use the Open Systems Interconnection
`(OSI) protocols such as described in International Or
`ganization for Standardization (ISO) 7498, "Informa
`tion Processing Systems-Open Systems Interconnec
`tion-Basic Reference Model, ' ISO 8473, "Protocol
`for Providing the Connectionless-mode Network Ser
`vice," ISO 9542, "End System to Intermediate System
`
`Cloudflare - Exhibit 1079, page 23
`
`

`

`O
`
`5
`
`5,430,727
`3
`4.
`Routing Exchange Protocol,” and ISO DP 10589 “In
`SIN requires that two complete sets of control packets
`termediate System to Intermediate System Intradomain
`be distributed through the two independent networks,
`Routing Exchange Protocol,' all available from BSi
`which doubles the control traffic overhead over that of
`a single integrated network. Finally, configuring and
`Standards, 2 Park Street, London England, W1A2BS,
`managing multiple independent networks is less effi
`and more are expected to be created as OSI 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
`calculating routes for sending user data packets through
`One known way to share routing resources among
`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
`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
`algorithm corresponding to the same routing protocol
`back.
`Each gateway router is configured to be fluent in
`(which is chosen from an arbitrary protocol suite) re
`25
`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.
`B header and places the protocol A user data packet,
`Preferred embodiments of this aspect include the
`30
`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.
`Link state packets conforming to the routing proto
`protocol A user data packet is then addressed to the
`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.
`The OSIIS-IS routing protocol is used to compute
`received at the second gateway router, the protocol B
`encapsulation header is removed, and the protocol A
`toutes.
`user data packet is forwarded to its destination through
`In another aspect, the invention features a method for
`calculating routes for sending user data packets via
`the protocol. A network.
`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
`dling devices include (a) single-protocol information
`ers aware of the gateway, so that user data packets
`handling devices capable of recognizing and forward
`destined to routers at the other end of the gateway are
`ing only user data packets which conform to a single
`forwarded to one of the gateway routers.
`45
`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
`path is added, the gateway routers must be manually
`automatically predetermine at which information han
`50
`dling devices to encapsulate and to decapsulate a given
`adjusted to effect the desired changes. Furthermore, the
`packet.
`gateway path is only available to the protocol A net
`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
`areas and all of the information handling devices within
`and communications must be re-routed through the
`a single area are at least capable of recognizing and
`protocol A network.
`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
`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
`tion handling devices capable of recognizing and for
`The shared resources multiplex between the supported
`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
`devices capable of recognizing and forwarding only
`With SIN, there is some degree of competition for
`resources, because implementing two protocols requires
`user data packets which conform to a second different
`protocol suite, and (c) at least one multi-protocol infor
`additional programming time as well as additional CPU
`mation handling device capable of recognizing and
`and memory resources in the routers. Furthermore,
`
`55
`
`35
`
`65
`
`Cloudflare - Exhibit 1079, page 24
`
`

`

`O
`
`5,430,727
`6
`5
`FIG. 7A illustrates a three-protocol network which
`forwarding user data packets which conform to the first
`does not have an all-protocol router.
`and second protocol suite (and/or every other protocol
`FIG. 7B illustrates a three-protocol network having
`suite that is used by any other information handling
`an all-protocol router.
`device in the area).
`FIG. 8A is a diagram of a data structure of the rout
`There are exactly two protocol suites, one which is 5
`ing tree of FIG. 4B as used in a dual-protocol router of
`the TCP/IP protocol suite and another which is the
`OSI protocol suite.
`F.G. B.
`FIG. 8B is a flow diagram of an algorithm for initial
`Link state packets conforming to the routing proto
`izing the routing trees in the dual-protocol routers of
`col used to compute routes are sent to the information
`FIG. B.
`handling devices, and routes are calculated based on
`FIG. 8C is a flow diagram of an algorithm for build
`information contained in the link state packets.
`ing the routing trees in the dual-protocol routers of
`The OSI IS-IS routing protocol is used to compute
`FG. T.B.
`routes and determine at which information handling
`FIG. 9 is a flow diagram of the user data packet
`devices to encapsulate and to decapsulate.
`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
`FG. B.
`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
`TB.
`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.
`a single address which is not an address of the device,
`7B.
`25
`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.
`F.G. 12 illustrates a common area Structure.
`F.G. 13 illustrates a router.
`DESCRIPTION OF THE PREFERRED
`EMBOOMENTS
`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
`define some terminology.
`segregated on a per-area basis which does not require is
`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
`FIG. 1C is a flow diagram of the user data packet 40
`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
`FG. A.
`"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
`ported protocols interconnect the dissinilar single
`lation.
`protocol routers. A router that is fluent in more than
`45
`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
`fluent in two protocols will be referred to as "dual
`routers of FIG. 2A.
`FIG. 2C is a flow diagram of the user data packet
`protocol routers; routers that are fluent in three proto
`forwarding algorithm to be followed by the dual- 50
`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
`protocols are supported, the terms multi-protocol, dual
`FIG. 4A is a flow diagram of an algorithm used to
`protocol, and all-protocol are synonymous; however,
`build routing trees.
`FIG. 4B is a diagram of a routing tree.
`this synonymity does not apply when more than two
`protocols are supported.)
`FIG. 5A is a diagram of a data structure of the rout
`ing tree of FIG. 4B as used in a dual-protocol router of
`There are two types of multi-protocol routers. A
`"simple multi-protocol router” will route user data
`F.G. 3.
`packets conforming to two or more protocols. How
`FIG. 5B is a flow diagram of an algorithm for initial- 60
`ever, a simple multi-protocol router is only able to for
`izing the routing trees in the dual-protocol routers of
`ward the user data packets; it is not able to perform
`FIG 3.
`encapsulation or decapsulation to make user data pack
`FIG. 5C is a flow diagram of an algorithm for build
`ets in one protocol compatible with another protocol.
`ing the routing trees in the dual-protocol routers of
`An "enhanced multi-protocol router" will not only
`FG. 3.
`route user data packets conforming to two or more
`FIG. 6 is a flow diagram of the user data packet
`protocols, but is also able to perform encapsulation or
`forwarding algorithm to be followed by the dual
`decapsulation to make user data packets in one protocol
`protocol routers of FIG. 3.
`
`30
`
`55
`
`SS
`
`Cloudflare - Exhibit 1079, page 25
`
`

`

`5
`
`5
`
`O
`
`5,430,727
`7
`compatible with another protocol. The extent to which
`reference to the protocol as modified to conform with
`enhanced multi-protocol routers may or may not sup
`the goals of the preceding paragraph.
`In an IP-OSI