United States Patent
`Bosack
`Date of Patent:
`[45]
`Feb. 11, 1992
`
`[11]
`
`Patent Number:
`
`5,088,032
`
`[19]
`
`llllllllllllllllllllllllllllll
`usoosossoszA
`
`[54]
`
`[751
`
`[73]
`
`METHOD AND APPARATUS FOR ROUTING
`COMMUNICATIONS AMONG COMPUTER
`NETWORKS
`
`Primary Examiner—Gareth D. Shaw
`Assistant Examiner—Kevin A. Kriess
`Attorney, Agent. or Firm—Lyon & Lyon
`
`Inventor:
`
`Leonard Bosack, Atherton, Calif.
`
`Assignee: Cisco Systems, Inc., Menlo Park.
`Calif.
`
`' [2 1]
`
`Appl. No.: 149,820
`
`122]
`
`[5|]
`[52]
`
`[5 8]
`
`[56]
`
`Filed:
`
`Jan. 29, 1988
`
`Int. Cl.5 ......................... H040 11/04; H041 3/26
`
`US. Cl.
`.
`...................... 395/200; 370/941;
`364/284; 364/2843; 364/284.4; 364/242.94;
`364/229; 364/2293; 364/2294; 364/2295;
`364/DIG. 1
`364/200 MS File, 900 MS File;
`370/94, 94.1, 94.3, 60.]
`References Cited
`
`Field of Search
`
`U.S. PATENT DOCUMENTS
`
`4,314,367 2/1982 Bakka et al.
`.......................... 370/60
`4,532,625
`7/1985 Stover
`370/58
`4,709,365 11/1987 Beale et a].
`.. 371/11
`4,736,363
`4/1988 Aubin et al.
`.. 370/60
`4,748,658
`5/1988 Gopal et al.
`379/221
`
`4.825.206 4/1989 Brice, Jr. et a1.
`340/825.02
`
`4.833.468
`5/1989 Larson et al.
`.......
`340/8258
`4.862.496
`8/1989 Kelly et al.
`379/221
`
`...........
`4,905,233 2/1990 Cain et al.
`370/941
`.................. 2370/94.]
`4,939,726 7/1990 Flammer e1 a].
`
`[57]
`
`ABSTRACT
`
`An improved method and apparatus for routing data
`transmissions among computer networks. The com-
`puter networks are interconnected with a series of gate-
`way circuits. Each gateway identifies all destination
`computers to which it is connected and identifies the
`path or paths to each destination computer. For each
`identified path, the gateway stores the topological delay
`time for a transmission,
`the path bandwidth for the
`narrowest bandwidth segment of a path and a number
`corresponding to the reliability of the path. When a
`transmission is received. the gateway examines the vari-
`ous paths in accordance with a predetermined algo-
`rithm which also considers the channel occupancy of
`each path to determine a best path for transmision. The
`data transmission is then directed over the best path. If
`more than one path exists, the data may be directed in
`multiplex fashion over two or more paths with the
`amount of data on each path being related to the quality
`of the path. The routing information to destination net-
`works is broadcast periodically by each gateway circuit
`to its neighboring gateway circuits.
`
`64 Claims, 11 Drawing Sheets
`
`
`
`Page 1 of 22
`
`SAMSUNG EXHIBIT 1020
`
`Page 1 of 22
`
`SAMSUNG EXHIBIT 1020
`
`

`

`US. Patent
`
`Feb. 11, 1992
`
`Sheet 1 of 11
`
`5,088,032
`
`142214
`(fie/m Aer)
`
`
`
`
`4?
`
`£25.11.
`fee/0,9 A27)
`
`52’
`
`Page 2 of 22
`
`Page 2 of 22
`
`

`

`
`
`US. PatentUS. Patent
`
`
`
`Feb. 11,1992Feb. 11,1992
`
`
`
`Sheet 2 of 11Sheet 2 of 11
`
`
`
`5,088,0325,088,032
`
`
`
`
`
`
`
`Page 3 of 22Page 3 of 22
`
`Page 3 of 22
`
`

`

`
`
`US. PatentUS. Patent
`
`
`
`Feb. 11, 1992Feb. 11, 1992
`
`
`
`Sheet 3 of 11Sheet 3 of 11
`
`
`
`5,088,0325,088,032
`
`
`
`MyMy
`
`
`
`£044£044
`
`
`
`/Z)4/Z)4
`
`
`
`/Zé/Zé
`
`
`
`M?M?
`
`
`
`7/44527/4452
`
`
`
`Z!Z!
`
`
`
`”l7”l7
`
`
`
`..
`
`
`
`//Z//Z
`
`
`
`//4//4
`
`
`p027p027
`
`11
`
`
`mgrmgr
`
`ZZ
`
`
`
`..
`
`
`
`-.-.
`
`
`
`,,
`
`
`
`‘‘
`
`
`29,2729,27
`
`A/A/
`
`
`
`//é//é
`
`
`
`//i//i
`
`
`
`MyMy
`
`
`
`Page 4 of 22Page 4 of 22
`
`Page 4 of 22
`
`

`

`US. Patent
`
`Feb. 11, 1992
`
`Sheet 4 of 11
`
`5,088,032
`
`am wear/seems 1/5/4/6 Wide/9162‘ 1
`
`0 01-7601”sz pea/am; w?! 51/ mar
`
`WIMP/Mkff
`
`[V0
`
`Yffi
`
`
`
`M155
`05.574147701/
`
`711/My0‘
`A002!!!
`
`
`
`9
`
`
`5942400757
`
`
`”66:55.
`
`My
`
`
`
`flmrmzm/At am
`
`/5
`
`
`
`05%1/4/1’7/41/
`
`
`ammo! row/55w
`Ming/2g
`
`
`G
`
`V55
`
`i‘gémr/fififiifigm
`
`
`impjyupémwwflz/m
`
`
`mama MAM/7W
`
`
`
`70 ”IfMild/lflflfl
`
`
`
`
`
`4/5
`
`5510Mt”! — {Wit/£76
`[4952 ӣ55,455.
`
`A/flfifAZM/fl M7 am flit/(f7:
`
`
`
`
`)é’é
`
`(waif A’Mflm’fi 1&7 A‘WEMEMW my
`m6. AlfiiM/Z’Ial/A/fl-Zai/A/ mm meow/m!
`waiver/om; m M56! gammy/fame.
`
`fin/£1745 ”army/em
`mm (MfA/PIIVM 5&0
`
`55m may 75 M‘XfW/fi/A/é
`[MAW/[MW Mfllflflé/Aff
`m 49mm 4w mam/(rm:
`
`Page 5 of 22
`
`Page 5 of 22
`
`

`

`US. Patent
`
`Feb. 11, 1992
`
`Sheet 5 of 11
`
`5,088,032
`
`mwmm 466/fo Key/”ma 5
`
`’43-. £4.
`
` [/ffl/Mf Affli/fl/I‘fi W/f/lf/m71¢[fl’ 169/715 57/wa Z/éflf/V/W
`
`mm”; F/Uffliif/A/Af/JA/fl EflM/A/ My»???
`
`Kampazmwz’jmemmp/m mjfsziam)
`
`W
`
`17/5me
`
`v55
`
`WW VAé’M/Uti a;
`A/f/f/ my {40 w
`
`
`
`
`
`
`
`
`
`llfffl/t W/fil/A/
`7/446? 0/20
`V/W/AA/lfflf
`
`It/l/lé/A/fl
`”Hf/7M”
`
`
`(WW? Aflt/
`
`M/U/Mfllr/
`
`
`[ZIP/M5”! Mffi/t
`we L? /F All/V
`
`03ft? flAf/lé
`7d 17 ARE 410W
`
`fluff/0! ME
`VAE/AA/[i fl;
`
`rx/[A/fli/ MM,
`
`paint/i mm
`
`
`A P EV/flflfi.
`flf/p/Jfl
`
`@ 72/5559
`(/flfl/ifi
`
`
`
`
` 47/ MW Him/6'
`IA/Fflll/Mflfll/ M/
`RAM61/77!VFig
`
` 0fflt‘7/VAIE F
`
`55427 DEAJT-
`IVAf/Jll/ f/Mff
`
`me P
`
`Page 6 of 22
`
`Page 6 of 22
`
`

`

`US. Patent
`
`Feb. 11, 1992
`
`Sheet 6 of 11
`
`5,088,032
`
`'95”
`awe/may
`7/4/56 me P
`
`72mm
`”’1’”;
`
`EXAM/M
`$45”
`flfj /gA7/0A/
`
`yij
`
`
`
`
`flfif/l/xlf/flfl! ll/
`UPfl/Vf 5455.926
`
`
`
`
`
`
`
`
`
`0’55 DAM
`Affflt/Afffl
`W/f/l A/EXT
`
`7W5 flffffly/(f
`
`
`
`Page 7 of 22
`
`Page 7 of 22
`
`

`

`US. Patent
`
`Feb. 11, 1992
`
`Sheet 7 of 11
`
`5,088,032
`
`232/5176 macaw/5
`
`/4/ [AM
`
`[WM/i ”[57W P
`
`
`
`
`
`X254.
`
`
`
`
`
`
`p
`
`awmmae
`
`
`fifflé’f/VA/xm/ 77115?
`
`
`61742:?
`
` Pfflflyf 7 [MMW
`
`
`
` ”’5
`
`[Xfldéflf/flfl/
`7/1154
`EA’fl/Ay’ffl
`
`
`fiéflfltfi‘fl/WIAM
`
`
`
`
`fi/E am r 2.47;; 70 xi;
`Dig/MW”
`
` 57/127
`5E5f/1/Aflfll/
`
`7/1466 F02
`
` 73mm ”/1247?
`
`Page 8 of 22
`
`Page 8 of 22
`
`

`

`US. Patent
`
`Feb. 11, 1992
`
`Sheet 8 of 11
`
`5,088,032
`
`[MM/Alf [/257Milk/£103WW
`
`
`
`
`
`
` ME
`72750:.” AMI/filmy
`70 D //V ”M, 4’07
`ZFAZX/Wffl
`
`army: ”mam
`
` ((542 7/4452
`
`
`
`
` EXAM/ME
`
`m2!
`125‘f/A/Af/flA/S'
`foflgAf/M/
`
`
`
`
`A/EA’T
`
`
`
`Page 9 of 22
`
`Page 9 of 22
`
`

`

`US. Patent
`
`Feb. 11, 1992
`
`Sheet 9 of 11
`
`5,088,032
`
`[XAfl/A/E[/67M22916? .7
`
`
`
`
`
`
`
`4’0
`
`r’M 6'
`[HAM/fl
`flMfl/MI’V 6F]
`(’l/Aé/éffl
`
`
`
`@ TI/Mffl (/flfl/lff
`
`[4/0
`
`Page 10 of 22
`
`Page 10 of 22
`
`

`

`US. Patent
`
`Feb. 11, 1992
`
`Sheet 10 of 11
`
`5,088,032
`
`@214-
`
`
`
`!A’flMfl/f #1957 WIZQFAC'EI
`
`(£547! fllflf/ flflflA/Z‘Mffffli!
`
`5:757F/éyf ”44‘fl!5651/[fflfW/ffl
`/
`
`(/5; mrxx/pzmmwu mm
`[£014 mam? fWi flFffiV/tf
`
`ilflM/A/E 15/157Diff/A/Af/fl/t/ P
`/A/ 55152759 5f/ 17/ 2/77}?
`
`
`
`V59
`
`1U A/f/V
`PAW/3’ 727 D #AVf
`11/617 #92” (Kid/[P
`Wflflfléfl
`I .7
`
`
`
`
`
`
`
`
`
`(165475 All 51/59/5921) /,{///flMfE/Idi55/Mf,
`mm Miffl/t' /1//d€fi/lf/fll//EQM mm
`
`mm 44mm; [mam/z 445m: 5:: HM)
`
`
`Page 11 of 22
`
`Page 11 of 22
`
`

`

`US. Patent
`
`Feb. 11,1992
`
`Sheet 11 of 11
`
`5,088,032
`
`fMlM/t A/[J’
`flfiflI/Af/fll/
`
`Yf5
`
`MJRE
`Diff/é/Af/fllt/f
`
`
`
`
`
`”5
`
`924557 4/er W
`
`7% a; 5mm:
`
`1W
`
`@ 561/0 [159475 Miiffléi 70 All
`
`547%;ij away/15.45
`fl/ifl/Jfl/I’ /A/75€flt[
`.Z'
`
`EXAM/”f 4/177
`/A/75€FA&£ I
`
`V55
`
`‘ MM!
`IA/fiflg/Mff
`
`
`
`
`
`M?
`
`42:11.
`
`Page 12 of 22
`
`Page 12 of 22
`
`

`

`1
`
`5,088,032
`
`METHOD AND APPARATUS FOR ROUTING
`COMMUNICATIONS AMONG COMPUTER
`NETWORKS
`
`The Appendix contains the details of the metric com-
`putations for the data paths.
`BACKGROUND
`
`The present invention relates to circuits for intercon-
`necting computer networks.
`Computer networks consist of a number of computer
`systems coupled together with a bus, rings or other
`medium, so that they can communicate with each other.
`Examples of such a system are the Xerox ETHERNET
`System and the IBM Token Ring Systems. Oftentimes,
`it is desirable to connect two such networks together.
`FIG. IA shows such a configuration in which a number
`of hosts 12 are connected together with a bus 14 in a
`network A and a number of hosts 16 are connected
`together with a bus 18 in a network B. Buses l4 and 18
`are coupled together to interconnect the networks with
`a repeater 20.
`When more than two networks are coupled together,
`it is often desirable to replace the repeater with a circuit
`which can route a communication packet from a host
`computer in one network to a computer in another
`network. These circuits are often called bridge circuits.
`A system interconnected using bridge circuits is shown
`in FIG. 18. A number of bridge circuits 22—30 intercon-
`nect a number of networks 32—42. Networks 32—42 each
`consist of a bus or other medium, and several attached
`hosts, similar to networks A and B, in FIG. 1A. Links
`53 and 55 are shown as simple links. However, they
`could be full networks, with hosts connected to them.
`These bridge circuits receive a data packet from one
`network and send it out an appropriate port of the
`bridge circuit so that it will be directed to the appropri-
`ate destination network. For instance, a data packet
`from a computer in network 36 could be transmitted to
`bridge 24. Bridge 24 would then determine that net-
`work 38 is the destination. Accordingly,
`the packet
`would be sent out a port 44 of bridge 24 and not a port
`48. Bridge 22 would receive the packet and ignore it
`while bridge 26 would receive the packet and direct it
`out its port 50. A problem arises if there were to be a
`connection such as that shown in phantom as line 52,
`which would cause a loop. In this instance, bridge 24
`could send the data packet out port 48 and route it
`through network 42, bridge 30 and bridge 28 to bridge
`26 in the example just given. To avoid such loops, data
`path 52 will be ignored by bridges 28 and 30 if it is so
`connected. An example of such a bridge circuit is de-
`scribed in 0.5. Pat. No. 4,597,078 to Kempf.
`If there are multiple paths to a destination network,
`the prior art required bridge circuits to disable links
`until no loops remained in the system.
`SUMMARY OF THE INVENTION
`
`10
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`$5
`
`The present invention is an improved method and
`apparatus for routing data transmissions between com-
`puter networks. The computer networks are intercon-
`nected with a series of gateway circuits. Each gateway
`identifies all destinations for which it has a directly
`connected interface. Paths to other destinations are
`obtained through an interchange of routing transmis-
`sions with adjacent gateways. For each identified path,
`the gateway stores the identity of the gateway circuit
`
`65
`
`Page 13 of 22
`
`2
`which is the “next hop” on the path, and a vector of
`metric information describing the path. The metric
`information includes the topological delay time for a
`transmission,
`the path bandwidth for the narrowest
`bandwidth segment of the path, the channel occupancy
`of the path, and a count of the number of gateway cir-
`cuits through which the path runs (the “hop count”).
`Based on this metric information, a single “composite
`metric" is calculated for the path. When a data transmis-
`sion is received, the gateway examines the various paths
`in accordance with a predetermined algorithm which
`uses the composite metric to determine a best path for
`transmission. The data transmission is then directed
`over that best path. If more than one path exists, the
`data may be directed in multiplex fashion over two or
`more paths with the amount of data on each path being
`related to the quality of the path.
`The routing information to all destinations is broad-
`cast periodically by each gateway circuit to its neigh~
`boring gateway circuits. The list of paths received by
`each gateway is compared to its existing list. Any new
`destination and paths are added to the gateway’s inter-
`nal list. Information in the broadcast is also used to
`update channel occupancy and other information about
`existing paths. Similarly, paths with non-respondent
`circuits are deleted from the internal list, providing
`dynamic data to construct the topological map of the
`networks. This procedure is in accordance with the
`Ford algorithm for identifying interconnections. The
`Ford algorithm is modified in three critical aspects to
`generate a method which will work effectively in prac-
`tice. First, instead of a simple metric, a vector of metrics
`is used to characterize paths. Second, instead of picking
`a single path with the smallest metric, traffic is split
`among several paths, whose metrics fall into a specified
`range. Third, several features are introduced to provide
`stability in situations where the topology is changing.
`The determination of the best path is done in one
`embodiment by computing a metric composite accord-
`ing to the formula
`[(KI/Be) + (Kch)]r
`
`where:
`K}, K2=constants;
`B.=path bandwidth x(l—channel occupancy);
`Dc=topological delay; and
`r = reliability.
`The path having the smallest composite metric num-
`ber will be the best path. Where there are multiple data
`paths to the same destination, the gateway can route the
`data transmission packets over more than one path
`through multiplexing. This is done in accordance with
`the composite metric for each data path. For instance, if
`one data path has a composite metric of l and another
`data path has a composite metric of 3, three times as
`many packets will be sent over the data path having the
`composite metric of 1. However, only paths whose
`composite metrics are within a certain range of the
`smallest composite metric will be used.
`The present invention provides a system for intercon-
`necting computer networks which can handle a general
`graph topology including loops in a stable manner. The
`system maintains full path metric information,
`i.e.,
`it
`knows the path parameters to all other networks to
`which each gateway is coupled. Traffic can be distrib-
`uted over parallel paths and multiple path parameters
`can be simultaneously computed over the entire net-
`
`Page 13 of 22
`
`

`

`5,088,032
`
`3
`work. This information is routinely and dynamically
`updated for each gateway circuit.
`For a fuller understanding of the nature and advan-
`tages of the invention, reference should be made to the
`ensuing detailed description taken in conjunction with
`the accompanying drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1A is a diagram of a prior art repeater coupling
`together two computer networks;
`FIG. 18 is a diagram of a prior art system using
`bridge circuits to interconnect computer networks;
`FIG. 2 is a diagram of a plurality of computer net-
`works interconnected using gateways according to the
`present invention;
`FIG. 3 is a block diagram of a gateway according to
`the present invention;
`FIG. 4 is a flowchart of the program executed by the
`gateway of FIG. 3 for routing data packets;
`FIG. 5 shows how FIG. 5A and FIG. SB form a
`flowchart of the subroutine for processing a received
`routing update packet;
`FIG. 6 shows how FIG. 6A, FIG. 6B and FIG. 6C
`form a flowchart of the subroutine for periodic updat-
`ing of path information, and
`FIG. 7 shows how FIG. 7A and FIG. 73 forms a
`flowchart of the subroutine for generating a routing
`update packet for broadcast.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`FIG. 2 shows a pair of computer network systems 54
`and “interconnected by two links 58 and 60. Network
`systems 54 and 56 may be in different states, for exam-
`ple, and links 58 and 60 might be a land microwave
`repeater link and a satellite link, respectively. Network
`system 56 is composed of computer networks 62-74
`interconnected by gateway circuits 76—82. Computer
`network system 54 consists of computer networks
`84-98 interconnected by gateway circuits 100-108.
`In this figure and the following figures, networks
`shown as "N" include a bus, ring, or other communica-
`tions medium, and any attached computers. Lines
`shown connecting bridges or gateways may be point-to-
`point connections, or they may be networks with addi-
`tional computers attached.
`A block diagram of a typical gateway circuit accord-
`ing to the present invention is shown in FIG. 3. A plu-
`rality of ports 110, 112 and 114 are shown, with any
`other number of ports being possible. These ports are
`connected to external data communication media 116,
`118 and 120, respectively. The ports are also coupled to
`an internal data bus 122. Also connected to internal data
`bus 122 is a microprocessor 124, a random access mem-
`ory (RAM) 126, a read only memory (ROM) 128, and a
`timer 129.
`Basically, when a data packet is received through one
`of the ports, it is stored in RAM 126, examined by mi-
`croprocessor 124, and then transmitted out an appropri-
`ate port to send it along the best path to the destination
`computer. The timer is used to trigger certain changes
`in the routing data base, as will be described in connec-
`tion with FIG. 6. In a typical embodiment, a gateway
`might have three ports coupled to ETHERNETS and
`six serial ports.
`When a gateway is coupled into a system, it is first
`initialized. This may be done by an operator at a com-
`puter in the network coupled to the gateway, by using
`
`Page 14 of 22
`
`4
`information retained in a non‘volatile portion of RAM,
`or by reading remote information from configuration
`files into a gateway. A description of each datalink
`coupled to a port of the gateway is provided, including
`(a) the topological delay along the link (i.e., how long it
`takes a single bit to transverse the link), (b) the band-
`width of the link, and (c) the reliability of the link (ex-
`pressed as a probability that a packet sent on the link
`will arrive undamaged at the next hop).
`For instance, in FIG. 2, gateway 76 would be told
`that a first port is coupled on a link 110 to a network 62,
`a second port is coupled on a link 112 to a gateway 78,
`a third link is link 60 and a fourth link is link 58.
`Thus, initially, gateway 76 only knows that it can
`reach any destination computer in network 62, and that
`it is attached to links 58, 60 and 112. All the gateways
`are programmed to periodically transmit to their neigh—
`boring gateways the information which they have been
`initialized with, as well as information gathered from
`other gateways. Thus, gateway 76 would receive trans-
`missions from gateways 100 and 108 and learn that it
`can reach computers in networks 86 and 90 through
`gateway 100 and computers in networks 92 and 98
`through gateway 108. This information will propagate.
`For example, gateways 100 and 108 will learn the desti-
`nation computers coupled to gateways 102 and 106 and
`will transmit these to gateway 76 on the next periodic
`transmission. This process is repeated until each gate-
`way learns all the destination computers it can reach.
`Each gateway computes a metric composite to deter-
`mine the desirability of the data paths to destination
`computers. For instance, for a destination network 88,
`gateway 76 would compute metric functions for two
`paths. The first path would be along link 58 through
`gateway 100. The second data path would be along link
`- 60 through gateway 108. Note that paths are defined
`simply by the next hop. There are actually three possi-
`ble routes for a transmission, involving links 114, 121,
`and 122. However, the routes involving links 121 and
`122 both go through gateway 108. Gateway 76 thus
`need not choose between them, leaving the choice to
`gateway 108.
`The composite metric function computed for each
`data path is as follows:
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`[(Ki/Be)+(K2Dc)]r
`
`E4 1
`
`where:
`r=fractional reliability (% of transmissions that are
`successfully received at the next hop);
`D¢=composite delay;
`(unloaded
`13.: effective
`bandwidth
`x(l ~channel occupancy); and
`K1. K2=constants.
`The composite delay, Dc is determined as follows:
`
`bandwidth
`
`50
`
`55
`
`DC=DJ+Dcir+DI
`
`EQ- 2
`
`where:
`
`D5=switching delay;
`Barr—circuit delay (propagation delay of 1 bit); and
`D,=transrnission delay (the no-load delay for a 1500
`bit message).
`An example of a table stored in a RAM 126 of a
`gateway of FIG. 3 is as follows (Note that individual
`components of the metric vector are not shown, for
`simplicity. They would be present in RAM in an actual
`implementation):
`
`65
`
`Page 14 of 22
`
`

`

`5,088,032
`
`5
`TABLE 1
`
`Destination 1
`
`Path A:
`Path 13:
`Destination 2
`
`Path A:
`Destination 3
`Path A:
`Path B:
`Path C:
`
`Port 1. Next hop gateway 2 comp. metric = 1.7
`Port 2. Next hop gateway 3 comp. metric = 3.2
`
`Port 3. Next hop gateway 4 comp. metric = 4.0
`
`Port 1, Next hop gateway 2 comp. metric = 2.0
`Port 2, Next hop gateway 6 comp. metric = 1.0
`Port 4, Next hop gateway 7 comp. metric = 3.0
`
`6
`catches spurious routes (if the hop count increases by
`more than 2, it is assumed that counting to infinity has
`started). A record of the path is retained, to prevent it
`from being re-established. This record is retained for a
`period of time equal to the maximum time for a trans-
`mission to the most distant part of the system. At the
`end of that time, all record of the path is deleted. After
`that time, it may be re-established if it appears in subse-
`quent routing updates received from neighboring gate-
`ways.
`(c) When the metric information for a path is revised
`due to processing an incoming routing update, all paths
`to the same destination are examined. The smallest com-
`posite metric from any of the paths is identified before
`and after the change. If this value is larger after the
`change than before by at least a factor of 1.3, or if there
`is no usable path to the destination after the change, a
`timer (hold-down) is started for that destination. Until
`the timer expires, no change in paths is accepted that
`would decrease the composite metric of any existing
`path, nor are new paths accepted. The timer lasts for a
`period of time equal to the maximum time for a trans-
`mission to the most distant part of the system. This
`timer allows a change for the worse in a path to propa-
`gate throughout
`the system. Otherwise, a gateway
`which hasn‘t been informed of the bad path may trans-
`mit a better route, which in reality is no longer better.
`The value of 1.3 was chosen to prevent small changes
`from causing a revision, thus resulting in continuous
`revisions.
`
`The gateway circuits are designed to handle multiple
`“types of service" and multiple protocols. Type of ser-
`vice is a specification in a data packet that modifies the
`way paths are to be evaluated. For example, certain
`protocols allow the packet to specify the relative impor-
`tance of high bandwidths, low delay, or high reliability.
`Generally,
`interactive applications will specify low
`delay, whereas bulk transfer applications will specify
`high bandwidth. These requirements determine the
`relative values of K) and K2 that are appropriate for use
`in Eq. 1. Each combination of specifications in the
`packet that is to be supported is referred to as a “type of
`service“. For each type of service, a set of parameters
`K1 and K2 must be chosen. A separate list of paths to
`each destination is kepi in the RAM. for each type of
`service. This is done because paths are selected and
`ordered according to the composite metric'defined by
`Eq. 1. This is different for each type of service. Informa-
`tion from all of these lists is combined to produce the
`routing update messages exchanged by the gateways, as
`described in FIG. 7.
`The set of processes described in FIGS. 4—8 are in-
`tended to handle a single network protocol. e.g.
`TCP/IP, DECnet, or the ISO/OS] protocol. A single
`gateway circuit may process data which is specific to
`more than one protocol. Because each protocol has
`different addressing structures and packet formats, the
`computer code used to implement FIGS. 4—8 will gen-
`erally be different for each protocol. The process de-
`scribed in FIG. 4 will vary the most. The processes
`described in FIGS. 5—8 will have the same general
`structure. The primary difference from protocol
`to
`protocol will be the format of the routing update
`packet, which must be designed to be compatible with a
`specific protocol.
`Note that the definition of a destination may vary
`from protocol to protocol. The method described here
`can be used for routing to individual hosts, to networks,
`
`10
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`Destination N
`Port 1. Next hop gateway 2 comp. metric = 5.0
`Path At
`
`Path B: Port 2, Next hop gateway 3 comp. metric = 1.0
`
`This process of compiling a list of destinations and
`paths by each gateway transmitting its information to
`neighboring gateways is based on the Ford algorithm,
`originally developed for the solution of transportation
`problems. The basic premise of the algorithm is to tell
`neighbors and the process repeats itself until eventually
`each gateway knows all possible destinations.
`The present
`invention makes the Ford algorithm
`work in practice in a real environment by adding three
`features to the Ford algorithm.
`1) Instead of a simple metric, a vector of metrics is
`used to characterize paths. A single composite metric
`can be computed from this vector according to Eq. I.
`Use of a vector allows the gateway circuit to accommo-
`date different types of service. by using several different
`coefficients in Eq. 1. It also allows a more accurate
`representation of the characteristics of the network than
`a single metric.
`2) Instead of picking a single path with the smallest
`metric, traffic is split among several paths with metrics
`falling into a specified range. This allows several routes
`to be used in parallel, providing a greater effective
`bandwidth than any single route. A variance V is speci-
`fied by the network administrator. All paths with mini-
`mal composite metric M are kept. In addition, all paths
`whose metric is less than VxM are kept. Traffic is
`distributed among multiple paths in inverse proportion
`to the composite metrics. No traffic is sent along paths
`whose remote composite metric (the composite metric
`calculated at the next hop) is greater than the composite
`metric calculated at the gateway. This is because send-
`ing traffic to a gateway with a larger composite metric
`is like sending to someone who is farther away from the
`destination.
`
`3) Several features are introduéed to provide stability
`in situations where the topology is changing. These
`features are intended to prevent routing loops and
`“counting to infinity," which have characterized previ-
`ous attempts to use Ford-type algorithms for this type
`of application. The primary stability features are the
`following:
`(a) Routing broadcasts must be generated separately
`for each interface on a gateway. The broadcast sent out
`each interface must not include paths whose next hop
`gateway circuit is reached through that interface as the
`other gateways connected to that interface can reach
`the next hop directly.
`(b) Whenever the metric information for a path is
`revised due to processing an incoming routing broad-
`cast, the old and new hop counts are compared. If the
`new hop count is larger than the old by more than 2,
`that path is disabled. This is a “poison reverse“. which
`
`Page 15 of 22
`
`Page 15 of 22
`
`

`

`7
`for more complex hierachical address schemes.
`or
`Which type of routing is used will depend upon the
`addressing structure of the protocol.
`FIGS. 4-7 show a flow chart for a program which
`will be run by microprocessor 124 of FIG. 3. At the
`start of the program. acceptable protocols and parame-
`ters describing each interface are entered.
`The gateway will only handle certain protocols
`which are listed and, generally, any communication
`from a system using a protocol not on the list will be
`ignored. It is possible to construct hybrid devices that
`can act both as a bridge circuit of the prior art and a
`gateway circuit.
`The data inputs are (l) the networks and gateways to
`which the gateway is connected, (2) the bandwidth of
`the links to these networks and gateways, (3) the reli-
`ability of each of these links, and (4) the topological
`delay along each link. The metric function for each data
`path is then computed according to Eq. I. In addition,
`a value for the variance V is entered.
`Once this initial information is entered, operations in
`the gateway are triggered by events: either the arrival
`of a data packet at one of interfaces 110-114, or the
`expiration of timer 129. The processes described in
`FIGS. 4—7 are triggered as follows.
`When a packet arrives, it is processed according to
`FIG. 4. This results in the packet being sent out another
`interface, discarded, or accepted for further processing.
`When a packet is accepted by the gateway for further
`processing (e.g., when it is addressed to the gateway), it
`is analyzed in a protocol-specific fashion not described
`in this specification. If the packet is a routing update, it
`is processed according to FIG. 5. Otherwise, the packet
`relates to a function which is not a part of this invention.
`FIG. 6 shows events triggered by timer 129. The
`timer is set to generate an interrupt once per second.
`When the interrupt occurs, the process shown in FIG. 6
`is executed.
`FIG. 7 shows a routing update subroutine. Calls to
`this subroutine are shown in FIGS. 5 and 6.
`‘
`In addition, the Appendix shows details of metric
`computations referred to in FIGS. 5 and 7.
`These figures presuppose the following major data
`structures being stored in RAM 126. A separate set of
`these data structures is kept for each protocol supported
`by the gateway. Within each protocol a separate set of
`data structures is kept for each type of service to be
`supported. For each destination known to the system,
`there is a (possibly null) list of paths to the destination,
`and a timer. The timer is used to suppress certain classes
`of updates to the information pertaining to that destina-
`tion, as described in more detail in FIGS. 5 and 6.
`For each path to a destination, the data structure
`includes the address of the next hop in the path, a vector
`of metrics characterizing the path, including topologi-
`cal data, bandwidth, reliability and channel occupancy.
`Other information is also associated with each path,
`including hop count, the remote composite metric, and
`a composite metric calculated from numbers according
`to Eq. 1. There is also a flag indicating whether the path
`has been deactivated, and two timers: a path expiration
`timer and a deactivation timer. The path expiration
`timer is reset to a value of 270 seconds whenever the
`metric information for the path is updated (FIG. 5). If
`the timer expires (because 270 seconds have elapsed
`without such an update), the path is removed (FIG. 6).
`The deactivation timer is set to a value of 270 seconds
`whenever the flag is set to indicate that the path has
`
`Page 16 of 22
`
`5,088,032
`
`8
`been deactivated. At the end of 270 seconds the path is
`removed (FIG. 6).
`Other data may be stored in the RAM as necessary to
`implement the processes described in FIGS. 4-8. The
`following sections are intended to clarify certain por—
`tions of FIGS. 4-8.
`
`IO
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`FIG. 4: This process uses the list of supported proto-
`cols and the information about the interfaces entered
`when the gateway is initialized. Details of the packet
`processing depend upon the protocol used by the
`packet. This is determined in Step A. Step A is the only
`portion of FIG. 4 which is shared by all protocols. Once
`the protocol type is known, the implementation of FIG.
`4 appropriate to the protocol type is used.
`Details of the packet contents are described by the
`specifications of the protocol. These should be known
`to anyone familiar with the art. The specifications of a
`protocol must include a procedure for determining the
`destination of a packet, a procedure for comparing the
`destination with the gateway's own address to deter-
`mine whether the gateway itself is the destination, a
`procedure for determining whether a packet is a broad-
`cast, and a procedure for determining whether the desti-
`nation is a section of a specified network. These proce—
`dures are used in Steps B and C of FIG. 4. If the packet
`is determined to be addressed to the gateway, it is pro-
`cessed in a protocol-specific way. If it is a routing up-
`date, the subroutine of FIG. 5 is called. Otherwise, it is
`processed in a manner not related to this invention.
`The test in Step D requires a search of the destina-
`tions listed in the RAM. The test is satisfied if there is an
`entry in the RAM for the destination, and that destina-
`tion has associated with it at least one usable path. Note
`that the destination and path data used in this and the
`next step are maintained separately for each type of
`service supported. Thus, this step begins by determining
`the type of service specified by the packet, and selecting
`the corresponding set of data structures to use for this
`and the next step.
`A path is usable for the purposes of Steps D and E if
`it has not been deactivated, and if its remote composite
`metric is less than its composite metric. (A path whose
`remote composite metric is greater than its composite
`metric path has a next hop that is “farther away" from
`the destination, as measured by the metric. This is re-
`ferred to as an “upstream path") Step E computes the
`path. Paths that have been deactivated are not consid-
`ered. Paths whose remote composite metric is not less
`than their composite metrics are not considered. If more
`than one path is acceptable, such paths are used in a
`weighted form of round-robin alternation. The fre-
`quency with which a path is used is inversely propor-
`tional to its composite metric.
`FIG. 5 describes the processing of a routing update
`received from a neighboring gateway. Su