US005088032A
`1:5)
`United States Patent
`5,088,032
`[11] Patent Number:
`Bosack
`
`[45] Date of Patent: Feb. 11, 1992
`
`eT
`
`[54]
`
`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.
`
`[75]
`
`[73]
`
`[58]
`
`(56)
`
`[57]
`ABSTRACT
`An improved method and apparatus for routing data
`transmissions among computer networks. The com-
`[21]
`Appl. No.: 149,820
`puter networksare interconnected withaseries ofgate-
`way circuits. Each gateway identifies all destination
`{22]
`Filed:
`Jan. 29, 1988
`computers to which it is connected and identifies the
`{31}
`path or paths to each destination computer. For each
`[52]
`identified path, the gatewaystores 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-
`worksis broadcast periodically by each gatewaycircuit
`to its neighboring gateway circuits.
`
`Int. C15 occ H04Q 11/04; H04J 3/26
`
`US. Ch. cece sete tereeereeees 395/200; 370/94.1;
`364/284; 364/284.3; 364/284.4; 364/242.94;
`364/229; 364/229.3; 364/229.4; 364/229.5;
`364/DIG.1
`Field of Search ... 364/200 MS File, 900 MS File;
`370/94, 94.1, 94.3, 60.1
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,314,367 2/1982 Bakka et al. oo. eee 370/60
`4,532,625
`7/1985 Stover uu...
`w+» 370/58
`4,709,365 11/1987 Beale etal.
`.....
`+ 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 al.
`...
`340/825.02
`
`4,833,468
`5/1989 Larsonetal. .......
`see 340/825.8
`4,862,496
`8/1989 Kelly etal.
`.....
`wee 379/221
`
`4,905,233 2/1990 Cain et al.
`...........
`- 370/94.1
`4,939,726 7/1990 Flammeret al.
`........0..... 370/94.1
`
`64 Claims, 11 Drawing Sheets
`
`
`
`Page | of 22
`
`SAMSUNG EXHIBIT 1020
`
`Page 1 of 22
`
`SAMSUNG EXHIBIT 1020
`
`

`

`U.S. Patent
`
`FL LA
`
`Sheet 1 of 11
`
`5,088,032
`
`Feb. 11, 1992
`
`(4000Alt)
`
`Page 2 of 22
`
`Page 2 of 22
`
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 2 of 11
`
`5,088,032
`
`
`
`Page 3 of 22
`
`Page 3 of 22
`
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 3 of 11
`
`5,088,032
`
`104
`
`BP
`
`126
`
`ROM
`
`/tb
`
`129
`
`RAM
`
`TIMER
`
`HO
`
`LL
`
`2
`
`4
`
`0R7
`l
`
`woRT
`Z
`
`fo
`
`:
`
`Aer
`N
`
`MG
`
`HG
`
`/L0
`
`LLG. ZF.
`
`Page 4 of 22
`
`Page 4 of 22
`
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 4 of 11
`
`5,088,032
`
`LATA PACLETARRIVES USING WTERFACE 1
`
`(A) DETERMME PROTOCOL USED BY DBLKET
`
`YES(FROCES$ GALKET W/
`PROTASECIL, WY
`
`YSCARDPALKET
`
`
`
`
`UG es|Baag?
`
`
`
`
`DURECTLY COMNECTED
`EMADSULATIONAPLRIIOMITE
`NETWARE
`10DROTOCM AMOLAWVE
`@)
`
`
`{9
`
`
`
`
`
`NO
`GeaOs
`
`70THEDESTUATION
`
`
`MOTDEALIVATED MOD.
`
`
`
`
`LYSCARD LACKET, UPFTECAN
`
`7) IDheWe
`
`@)
`
`YES
`
`CHOOSE NEXTPATHTIO LIE [FTHELEACEWORE THAN
`QE, ALTERNATEROUND-ROEI WITH FREQUENCY
`AROEORTIONAL 70 IWVERSE OFCOMOOLEMETEIC.
`
`SETNENTAG NEXTHOPFOL
`PATH CHOSENOREVOUS STEP
`
`SD PALLET 10 NEXTMOEO9NG
`ENCAPSULATION AOLROMIATE
`10 PLOTOLOL AUD DATA LINKVDE
`
`Page 5 of 22
`
`Page 5 of 22
`
`€
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 5 of 11
`
`5,088,032
`
`ROUTINGLATA RIVES (NISORE §FiL. Fa.
`
`USELATA AGSOLILTED WITHFURSTTUDELESERVICE SLPEICTED BYGAIEWAY
`
`EXAMINE FIRSTDESTIVATIONDSHAWI) UPDATE
`
`COMPUTE METRICSFORIATY P70D VA SU5EEIGE)
`
`NO
`
`7$
`
`THeBHP
`LOGE
`
`VES
`
`
`
`RUMMING
`
`
`COMPUTE NEW
`MUIIMUM
`COMPOWIE MERIC
`FOR LF ANY
`
`
`OTHER PATHS
`
`70 D ARE NOW
`
`DUTYIDE THE
`
`THENEW MUL,
`REMOVE THEA
`
`Aoi018.
`
`413,70
`
`
`[TRIGGER
`
`
` FU NEW METRIC
`ULDATE
`WEORMATION 1h/
`RAMaeYFOR
`
`
` LEACIVATE PB
`START DEACT-
`WATION TMER
`fie P
`
`
`
`
`
`40D PATH
`PTO RAW
`
`@)
`
`Page 6 of 22
`
`Page 6 of 22
`
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 6 of 11
`
`5,088,032
`
`RESET
`
`EXDIBATION
`TWEE FOR 2
`
`TPUGER
`
`EXAMINE|yee MORE
`
`MENT
`DESTIMMATIOUS WM
`DES MATION
`UPDATE YeBAG,
`
`
`
`
`WF
`
`FEDS.
`
`
`
`
`USE DATA
`ASSQUIATED
`
`WHT NEXT
`WHE DESERVILE
`
`
`
`Page 7 of 22
`
`Page 7 of 22
`
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 7 of 11
`
`5,088,032
`
`
`ALE O44.
` KEMOVE ? FROMRAM
`EXPIRED
`
`?P
`
`THE ONLY PRIM 10 114
`
`DESTINATION,
` START
`LESTIMATION
`
`
`PERIODIC FROCEGSNG
`
`EXAMINE F157 LECH P
`iN KAM
`
`2
`TLACTIVATED, OR.
`DEACTIVATION TMMER
`EXPIRED
`
`PS
`LEXAATION
`TUWMER
`
`REMOVEPERORAM
`
`TUNER FOR
`
`TRIGGER UPDATE
`
`
`
`
` EXAMINE
`
`
`
`Page 8 of 22
`
`Page 8 of 22
`
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 8 of 11
`
`5,088,032
`
`
`/6
`TIMER
`
`RUNING FOR
`
`2?
`
`
`
`
`
`
`
`
`HAS
`
`TMER
`
`
` EXAMINE FASTDESTMTIOND iRAM
`
`
`XPIRED
`CLEAR THERI
`
`
`
` LES:TMASIONS
`
`
`ARE
`
`HEREANYPATHS
`70 D IN RAM, NOT
`TEACWH
`
`
`
`REMOVE DFROMRAM
`
`Page 9 of 22
`
`Page 9 of 22
`
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 9 of 11
`
`5,088,032
`
`LXAMINEFUTNWTERFACE I
`
`KECALLULATE METRICS
`
`
`
`
`
`EXAMIVE NEXT
`WIERALCE I
`
`MORE
`INITERIALES
`?
`
`MO
`
`
`
`GO)
`SELONDOF
`SWLE LASTUPDATE
`LUT
`?
`
`©)|GER UPDATE
`
`END
`
`Page 10 of 22
`
`Page 10 of 22
`
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 10 of 11
`
`5,088,032
`
`
`
`FL 2.
`
`Aub LA.
`
`EXAMMIE L1RS7 IWITERFACET
`
`CREATE EMPTY UPDATEMESSAGE
`
`SHLELTFRET TYEEOFSERUICEREPORTED
`
`USE PATHLDESTWATION DATA
`FROM GELECTED TVIE OFGLRIICE
`
`LYAMINE HIRSTDESTINATION D
`IMI GELELTED $L7 LF DATA
`
`
`
`i?
` CREATE AN EVTEYFORD UM)UFDBIEMESSAGE,
`
`
`USING METEIC MORATIONFROM)AZBTA
`WITH MIVIVIAL COMPOSITEMETRIC GEE FIGB)
`
`
`THROUGA
`
`YES
`
`Page 11 of 22
`
`Page 11 of 22
`
`

`

`U.S. Patent
`
`Feb. 11, 1992
`
`Sheet 11 of 11
`
`5,088,032
`
`EXAMIE NEXT)
`
`YES
`
`DESTIVATION
`WE OF GERVILE
`
`SELECT NEXT=|YES
`
`Q SEND UPDATEMESSAGE 70 ALL
`
`GATEWAYS REACHABLE
`THROUGH INTERPALE I
`
`EXAMINE NEXT\YES J M0@E
`
`
`
`INTERFACE T
`WTEREACES
`
`
`
`NO
`
`Page 12 of 22
`
`Page 12 of 22
`
`

`

`1
`
`5,088,032
`
`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 gatewaycir-
`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 examinesthe 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 comparedtoits 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
`[(K1/Be)+(K2D,)]r
`
`10
`
`20
`
`25
`
`30
`
`35
`
`METHOD AND APPARATUS FOR ROUTING
`COMMUNICATIONS AMONG COMPUTER
`NETWORKS
`
`The Appendix contains thedetails of the metric com-
`putations for the data paths.
`BACKGROUND
`
`The present inventionrelates to circuits for intercon-
`necting computer networks.
`Computer networksconsist 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. 1A showssuch 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 14 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 bridgecircuits.
`A system interconnected using bridge circuits is shown
`in FIG. 1B. A numberof bridge circuits 22-30 intercon-
`nect a numberof 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 §5 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 directit
`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 39 if it is so
`connected. An example of such a bridge circuit is de-
`scribed in U.S. 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.
`SUMMARYOF THE INVENTION
`
`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 gatewaycircuit
`
`Page 13 of 22
`
`45
`
`50
`
`35
`
`65
`
`where:
`Ki, K2=constants;
`B-=path bandwidth x(1—channel occupancy),
`D.=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 1 and another
`data path has a composite metric of 3, three times as
`many packets wil] 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 loopsin 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 gatewaycircuit.
`For a fuller understanding of the nature and advan-
`tages of the invention, reference should be madeto the
`ensuing detailed description taken in conjunction with
`the accompanying drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`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 gatewayis provided, including
`(a) the topological delay along the link (i.e., how longit
`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
`thata 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 $8, 60 and 112. All the gateways
`are programmedto 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:
`
`FIG.1A is a diagram ofa prior art repeater coupling
`together two computer networks;
`FIG. 1B 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. §B 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. 7B 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 56 interconnected by twolinks 58 and 60. Network
`systems 54 and 56 maybein different states, for exam-
`ple, and links 58 and 60 might be a land microwave
`repeaterlink 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 maybe 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 sénd 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 ETHERNETSand
`six serial ports.
`When a gatewayis 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
`
`20
`
`25
`
`30
`
`35
`
`45
`
`[(K1/B)+(K2D0)Ir
`
`Eq.
`
`}
`
`where:
`r=fractional reliability (% of transmissions that are
`successfully received at the next hop);
`D,=composite delay;
`(unloaded
`B.=effective
`bandwidth
`x(1—channel occupancy); and
`K1, K2=constants.
`The composite delay, D, is determined as follows:
`
`bandwidth
`
`50
`
`35
`
`D,-=D;+Deir+D,
`
`Eq. 2
`
`where:
`D;=switching delay;
`Der=circuit delay (propagation delay of 1 bit); and
`D,=transmission 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
`
`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 preventit
`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 ofthat 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
`changethan before byat 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 timerlasts for a
`period of time equal to the maximum timefor 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 maytrans-
`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 gatewaycircuits are designed to handle multiple
`“types of service” and multiple protocols. Type of ser-
`vice is 2 specification in a data packet that modifies the
`way paths are to be evaluated. For example, certain
`protocols allow the packetto 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 Ky and K2that 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
`K, and K2 must be chosen. A separate list of paths to
`each destination is kept in the RAMfor each type of
`service. This is done because paths are selected and
`ordered according to the composite metric defined by
`Eg. 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/OSI 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,
`
`Destination |
`
`Path A:
`Path B:
`Destination 2
`
`Path A:
`Destination 3
`Path A:
`Path B:
`Path C:
`
`Destination N
`Path Ac
`Path B:
`
`TABLE |!
`
`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
`Por 4, Next hop gateway 7 comp. metric = 3.0
`
`Port 1, Next hop gateway 2 comp. metric = 5.0
`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 repeatsitself until eventually
`each gateway knowsall 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 metricsis
`used to characterize paths. A single composite metric
`can be computed from this vector according to Eq.1.
`Use of a vector allows the gatewaycircuit 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 VM are kept. Traffic is
`distributed among multiple paths in inverse proportion
`to the composite metrics. Notraffic 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 whois farther away from the
`destination.
`3) Several features are introduced 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 algorithmsfor 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 broadcastsent out
`each interface must not include paths whose next hop
`gatewaycircuit 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 countis larger than the old by more than 2,
`that path is disabled. This is a “poison reverse”, which
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`5$
`
`&
`
`65
`
`Page 15 of 22
`
`Page 15 of 22
`
`

`

`7
`cr for more complex hierachical address schemes.
`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 (1) the networks and gateways to
`which the gateway is connected, (2) the bandwidth of
`the links to these networks and gateways, (3) thereli-
`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. 1. In addition,
`a value for the variance V is entered.
`Oncethis initial information is entered, operations in
`the gatewayare 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.
`Whena 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.
`Whena packetis accepted by the gateway for further
`processing (e.g., whenit 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 whichis nota part of this invention.
`FIG. 6 shows events triggered by timer 129. The
`timer is set to generate an interrupt once per second.
`Whenthe 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. § and 7.
`These figures presuppose the following major data
`structures being stored in RAM 126. A separate set of
`these data structuresis 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 timeris used to suppress certain classes
`of updates to the information pertaining to that destina-
`tion, as described in more detail in FIGS. § 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 (F1G. 6).
`The deactivation timer is set to a value of 270 seconds
`wheneverthe flag is set to indicate that the path has
`
`20
`
`25
`
`30
`
`35
`
`45
`
`60
`
`65
`
`5,088,032
`
`8
`been deactivated. At the end of 270 secondsthe path is
`removed (FIG.6).
`Other data may be stored in the RAM asnecessary to
`implement the processes described in FIGS. 4-8. The
`following sections are intended to clarify certain por-
`tions of FIGS. 4-8.
`FIG. 4: This process uses thelist of supported proto-
`cols and the information about the interfaces entered
`when the gatewayis 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 whichis shared byall 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 gatewayitself is the destination, a
`procedure for determining whether a packetis a broad-
`cast, and a procedure for determining whetherthe 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. Ifit is a routing up-
`date, the subroutine of FIG.5 is called. Otherwise,it is
`processed in a mannernotrelated to this invention.
`The test in Step D requires a search of the destina-
`tionslisted in the RAM. Thetest is satisfied if there is an
`entry in the RAM forthe destination, and that destina-
`tion has associated withit 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 pathis 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 hopthatis “farther away” from
`the destination, as measuredby 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. Such updates
`consist of a list of entries, each of which specifies infor-
`mation for a single destination. More than one entry for
`the same destination can occur in a single routing up-
`date, to accommodate multiple types of service. Each of
`these entries is processed individually, as described in
`FIG. 5.
`The entire process described in FIG. § must be re-
`peated once for each type of service supported by the
`gateway, using the set of destination/path information
`associated with that type of service. This is shown in the
`outer-most loop in FIG. §.
`In Steps B and C the RAMis searched to see whether
`this entry describes a path thatis already known. A path
`
`Page 16 of 22
`
`Page 16 of 22
`
`

`

`9
`in the RAM is defined by the destination with whichit
`is associated, and the next hop liste