Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 1 of 9
`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 1 of 9
`
`
`
`
`EXHIBIT B
`
`EXHIBIT B
`
`

`

`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 2 of 9
`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 2 of 9
`
`United States Patent
`Humblet
`
`[191
`
`[11] Patent Number:
`
`4,987,536
`
`[45] Date of Patent:
`
`Jan. 22, 1991
`
`[54] COWUNICATION SYSTEM FOR SENDING
`AN IDENTICAL ROUTING TREE TO ALL
`CONNECTED NODES TO ESTABLISH A
`SHORTEST ROUTE AND TRANSMITTING
`MESSAGES THEREAFTER
`
`[75]
`
`Inventor:
`
`Pierre A. Humblet, Cambridge,
`Mass.
`
`[73] Assignee: Codex Corporation, Mansfield, Mass.
`
`[21] Appl. No.: 193,391
`
`[22] Filed:
`
`May 12, 1988
`
`Int. Cl.’ .............................................. 60617 13/38
`[51]
`[52] US. Cl. ............................... 364/200; 364/242.94;
`364/2612; 364/2601; 370/60
`364/200MS File, 900 MS File,
`[58] Field of Search
`364/514; 370/60, 94, 16, 94.2, 94.3
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,466,060 8/ 1984 Riddle ................................. 364/200
`4,656,658 4/1987 King .................
`379/221
`
`......... 370/60
`4,736,363 4/1988 Aubin et al.
`.
`
`364/514 X
`4,748,660 5/1938 Deveze ........
`......................... 370/86
`4,771,424 9/ 1988 Suzuki et a1.
`
`OTHER PUBLICATIONS '
`
`Awerbuch et al. “A New Distributed Algorithm to
`Find Breadth First Search Trees", IEEE Trans. of
`Information Theory, vol. IT-33, No. 3, May, 1987, pp.
`315—322
`“Routing Data Networks", Data Networks, Bertsekas
`et al., Chapter 5. PP- 318-333, 1987.
`“Shortest-Path Routing”, Telecommunication Net-
`works: Protocols, Modeling and Analysis, Schwartz,
`pp. 267-281, 1987.
`
`Jacob Hagouel. “Issues in Routing For Large and Dy-
`namic Networks", 1983, pp. 30—92.
`
`Primary Examiner—Thomas C. Lee
`
`[57]
`
`ABSTRACT
`
`The communications network includes a plurality of
`interconnected nodes and communication links between
`nodes. Computing apparatus in provided for determin-
`ing a shortest path from a starting node to a destination
`node. The computing apparatus is adapted so that each
`node forms a routing tree having nodes with indentities,
`branches with weights, and a distinguished node called
`a root. The routing tree is the estimated shortest path to
`all of the nodes and each node communicates its routing
`tree to each adjacent node. Upon receipt of a routing
`tree by a reference node from an adjacent node, the
`reference node stores the routing tree and produces a
`large tree having roots and branches by placing the
`reference node as the root of the large tree and creating
`branches from the reference node to the roots of the
`routing trees of the adjacent nodes. The lengths of the
`branches are equal to the lengths of the Iinks from the
`reference node to the adjacent nodes. A breadth first
`search of the large tree is performed to determine a
`connected subset of the large tree where each node
`identity appears only once. The connected subset forms
`the new routing tree for the reference node. If the new
`routing tree differs from the previous routing tree, the
`new routing tree is broadcast to all adjacent nodes and
`the procedure is repeated until no new tree differs from
`a previous tree. thereby defining a final routing tree.
`The final routing tree includes the shortest path from
`the reference node to all connected nodes.
`
`15 Claims, 3 Drawing Sheets
`
`EACH NODE FORMS A ROUTING THEE
`THAT FEESENTS THE SHORT'EST PATH
`FROM THE MODE TO OTHER NODES
`
`EACH MOE SENDS IT'S ROUTING TREE
`TO ALL ADJACENT NODES
`
`,
`
`2
`
`COMMUTE!) NODES
`
`EACH NOIE STORES THE ROUTING TREES
`AND POEMS A LARGE TREE FROM THEM
`
`CFH'SLARGETFIEETOFOFIMAN
`fiOUI'INGT'BEE
`
`W NEW ROUTING TREE TO ALL
`ADJACENT NODES F (T DIFFEHS FROM
`PREVIOUS ROUTING TREE
`
`FINAL ROUTING TREE FOR NODE
`IMLUDES SHORTEST PATH TO ALL
`
`

`

`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 3 of 9
`Case 1:16—cv-02690-AT Document 109-3 Filed 07/19/16 Page 3 of 9
`
`US. Patent
`
`Jan.'22, 1991
`
`Sheet 1 013
`
`4,987,536
`
`RT_D(1 ,1)
`
`RT_D(2. 1)
`
`RT_D(3, 1)
`
`O
`
`INITIALLY
`
`LINK FAILURE
`
`|
`
`3
`
`5
`
`SEND (1 ,3)->
`<-SEND(1.4)
`
`SEND (1 ,5)->
`
`2
`
`4
`
`6
`
`LOOPING IN FORD-BELLMAN
`
`-—v
`
`2
`
`\
`3
`'I
`
`4
`
`|6
`
`/
`
`3
`
`4
`l'
`
`3
`
`I'
`T
`
`I
`
`2
`
`I
`
`‘
`
`BUILDING THE ROUTING TREE AT NODE 2 AFTER FAILURE OF LINK (1,2)
`NODE 2 REALIZES AT ONCE THERE IS NO PATH TO NODE 1
`
`RECONFIGURATION FOLLOWING A TOPOLOGY CHANGE
`F [(3.3
`
`

`

`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 4 of 9
`Case 1:16—cv-02690-AT Document 109-3 Filed 07/19/16 Page 4 of 9
`
`US. Patent
`
`Jan. 22, 1991
`
`Sheet 2 of 3
`
`4,987,536
`
`BUILDING THE ROUTING TREES
`
`
`
`NETWORK TOPOLOGY
`FIG. 20
`
`INDIVIDUAL NODE ROUTING TREES
`FIG. 2b
`
`r44
`
`3
`
`-———N——w-———-I>
`
`m
`
`BUILDING THE ROUTING TREE AT NODE 2
`FIG. 20
`
`

`

`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 5 of 9
`Case 1:16—cv-02690-AT Document 109-3 Filed 07/19/16 Page 5 of 9
`
`US. Patent
`
`Jan. 22, 1991
`
`Sheet 3 of3
`
`4,987,536
`
`
`EACH NODE FORMS A ROUTING TREE
`THAT REPRESENTS THE SHORTEST PATH
`
`
`FROM THE NODE TO OTHER NODES
`
`
`
`EACH NODE SENDS IT'S ROUTING TREE
`TO ALL ADJACENT NODES
`
`EACH NODE STORES THE ROUTING TREES
`AND FORMS A LARGE TREE FROM THEM
`
`
`
`.5:-'0'
`
`EACH NODE DOES A BREADTH FIRST SEARCH
`OF IT’S LARGE TREE TO FORM A NEW
`ROUTING TREE
`
`5
`
`6
`
`BROADCAST NEW ROUTING TREE TO ALL
`ADJACENT NODES IF IT DIFFERS FROM
`PREVIOUS ROUTING TREE
`
`FINAL ROUTING TREE FOR NODE
`INCLUDES SHORTEST PATH TO ALL
`CONNECTED NODES
`
`FIG.4
`
`

`

`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 6 of 9
`Case 1:16—cv-02690-AT Document 109-3 Filed 07/19/16 Page 6 of 9
`
`1
`
`4,987,536
`
`COMNIUNICATION SYSTEM FOR SENDING AN
`IDENTICAL ROUTING TREE TO ALL
`CONNECTED NODES TO ESTABLISH A
`SHORTEST ROUTE AND TRANSMITTING
`MESSAGES THEREAFI'ER
`
`BACKGROUND OF THE INVENTION
`
`This invention relates to a communications network
`including a distributed system to compute shortest paths
`in a network with changing topology.
`One of the oldest and best known distributed algo-
`rithms is the Ford-Bellman method to compute shortest
`paths between nodes in a network. It was originally
`introduced in the Arpanet and is now in use in a large
`number of networks. It basically works as follows:
`We have a network of links and nodes (processors).
`Each link (1,!) is characterized by a (direction depen-
`dent) length LEN(I,J) that can change with time The
`nodes execute the following distributed algorithm to
`keep track of the shortest distances between themselves
`and the other nodes.
`Two kinds of information are maintained: the routing
`table RT—D(I,J), whose (IJ)th entries are maintained
`at node I to contain the estimate of the minimum dis-
`tance between I and J;
`the neighbor table, NT—
`D(I,J,P), where the first two indices are node identities
`and the third is a link adjacent to the first node. If
`P=(I,M) NT—D(I,J,P) is used to save at I the latest
`value of RT——D(M,I) transmitted by M to I.
`The algorithm consists of the following steps:
`Initially RT—D(I,J) is set to so for all J, except
`RT—D(I,I) which is set to 0, and all links are Down.
`Whenever a link adjacent to I goes Up, node I sends
`records of the form (J, RT—DGJ» over it, for all
`nodes J.
`When a node I receives a pair (J,D) over a link P,
`with I=/=J, it sets NT—D(I,J,P) to D and it computes
`RT—D(I,J)=min(over p)NT-—-D(I.J.p)+LEN(p).
`If
`this results in a new value for RT—D(I,J), the record
`(J,RT—D(I,J)) is sent to all the neighbors of I.
`The same computation is also performed at I for all
`nodes 1 not equal to I whenever the length of any adja-
`cent link changes. In particular, the length of a Down
`link is considered to be infinite.
`This basic prior art algorithm and a number of varia-
`tions have been shown to converge to the correct dis-
`tances if the link lengths stabilize and all cycles have
`strictly positive length. However, the convergence can
`be very slow when link lengths increase. In a typical
`example (FIG. 1) node 1 becomes disconnected. Nodes
`2 and 3 keep executing the algorithm, slowly increasing
`their RT—D(.,l). This behavior is known as “counting
`to infinity”. While this goes on messages destined to
`node 1 may cycle back and forth between nodes 2 and
`3, a phenomenon called “routing table looping". In
`practice there are known upperbounds NN on the num-
`ber of nodes and MAXLEN on LENO and entries of
`RT—D that exceed (NN—l)‘MAXLEN are set to so.
`If not all Up links have the same length, a better alterna-
`tive is to keep track of the number of links in a shortest
`path, and to only accept paths up to a maximum number
`of links.
`The looping behavior problem is a major drawback
`of Ford-Bellman distributed algorithms. To prevent it,
`techniques have been developed to “freeze” part of the
`network while the news of an increase in length propa-
`gates. This approach requires new types of messages
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`2
`and sometimes delays a node from obtaining a correct
`distance. Another approach reduces the likelihood of
`looping but, in our opinion, does not always prevent it.
`It has often been noted that in the previous algorithm
`the RT—D(I,J)’s for different J‘s behave independently
`of each other and that one can focus on a single destina-
`tion. To the contrary we remark here that much can be
`gained by considering the interactions between differ-
`ent destinations.
`Assume we know the neighbor K next to the destina-
`tion on the shortest path from a node I to a destination
`J. The following statements must be true if we have
`valid paths to K and J and OéLENOéMAXLEN:
`(A) if a neighbor of I appears to be on a shortest path
`from I to J, it must also be on a shortest path from I to
`K.
`
`(B) distance (J) édistance (K)
`(C) distance (Dédistance (K)+MAXLEN
`This suggests that keeping track of the nodes next to
`the destinations (on shortest paths) is important (this is
`different from keeping track of the next node on a path,
`which is only marginally effective). Although the previ-
`ous relations could be used to quickly weed out un-
`reachable nodes in Bellman-Ford type algorithms and
`prevent routing table looping, we will not use them
`directly in the rest of the specification. Rather, we note
`that keeping information at a node I about the nodes
`next to destinations is equivalent to keeping track of an
`entire shortest path tree rooted at I. This the view that
`we will exploit.
`SUMMARY OF THE INVENTION
`
`The communications network according to the in-
`vention includes a plurality of interconnected nodes and
`communication links between the nodes. The links have
`lengths and the nodes have unique identities. Referring
`to FIG. 4, computing, apparatus is provided for com-
`puting shortest paths from a starting node to all destina-
`tion nodes, the computing apparatus adapted so that
`each node forms a routing tree having nodes with iden-
`tities, branches with lengths, and a distinguished node
`called a root (1). The routing tree is the estimated short-
`est path to all of the nodes and each, node communi-
`cates its routing tree to each adjacent node (2) wherein
`upon receipt of a routing tree by a reference node from
`an adjacent node, the reference node stores the routing
`tree and produces a large tree (3) having roots and
`branches by placing the reference node as the root of
`the large tree. Branches from this root node to the roots
`of the routing trees of the adjacent nodes (stored in the
`reference node) are created, the lengths of the branches
`being equal to the lengths of the links from the reference
`node to the adjacent nodes. A breadth first search (with
`respect to the branch lengths) of the large tree is per-
`formed to determine a largest connected subset of the
`large tree where each node identity appears only once,
`the connected subset forming the new routing tree for
`the reference node (4). If the new routing tree differs
`from the previous routing tree, the new routing tree is
`broadcast to all adjacent nodes, and the procedure is
`repeated until no new tree differs from a previous tree
`thereby defining a final routing tree (5). The final rout-
`ing tree includes the shortest path, from the reference
`node to all connected nodes (6).
`In a preferred embodiment, the procedure is repeated
`at predetermined intervals or whenever there is a
`change in link lengths in the network. Further, upon a
`
`

`

`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 7 of 9
`Case 1:16—cv-02690-AT Document 109-3 Filed 07/19/16 Page 7 of 9
`
`4,987,536
`
`4
`continued
`
`if (UNSEENU) AND
`((N'f—NGJPl-l) 0R (RT—LG.N'I'_—N(I.J.P‘))=P‘)))
`then { if ((RT_D(I.J)NT_D(IJ.P‘) + LEN(P‘)) 0a
`(RT—NOJ).NT_N(I.J.P‘)))
`then { RT_D(I.J)-NT_D(U.P‘)+LEN(P‘);
`RT—NflJlaN'f—Mmm‘):
`PACKETsPACKET U
`
`3
`link failure, the length of the failed link is set to infinity.
`The lengths of the links may be direction dependent.
`BRIEF DESCRIPTION OF THE DRAWING
`
`FIG. 1 is a schematic representation of a network
`illustrating looping:
`FIG. 2 which comprises FIGS. 20. b. and c are sche-
`matic representations of networks utilizing the inven-
`tion herein; and
`FIG. 3 is a schematic representation of a network
`illustrating reconfiguration following a
`topology
`change.
`FIG. 4 is a flow chart useful in understanding the
`invention.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`
`5
`
`[O
`
`15
`
`E(J.RT_D(IJ).RT.N(IJ));)
`fi—LGJFP':
`if (PACKET nil) then send PACKET on all Up links;
`
`This implementation is decomposed into two major
`parts: in the first part, a node observes local topology
`changes or receives update messages from neighbors;
`these updates are saved in NT. In the second major part
`(COMPUTE) each node I builds from NT—a large tree
`with weighted branches (FIGS. 2 and 3), where a node
`identity may appear many times; node I puts itself as the
`root and “hangs” on each adjacent link the shortest path
`trees communicated by its neighbors. This large tree is
`then scanned in a “breadth first” fashion (with respect
`to the cumulative branch weights from the root) to
`obtain a subtree where each node appears at most once.
`That subtree is adopted as the new “local” shortest path
`tree and changes (if any) with respect to the previous
`version are communicated to the adjacent nodes.
`In particular, FIG. 2(a) depicts a network topology
`10 including nodes 1-4 interconnected with links 12
`having lengths denoted by the integers adjacent to the
`links 12. FIG. 2(b) shows the individual node routing
`trees for the nodes of FIG. 2(a). FIG. 2(c) illustrates the
`building of a routing tree 14 at node 2. As shown in
`FIG. 3, a routing tree 16 is a reconfiguration of the
`reouting tree 14 of FIG. 2(c) after a failure of the link 12
`(FIG 2(a)) connecting nodes 1 and 2.
`More precisely, COMPUTEO at node I builds
`RT—D and RT—N starting with I, considering nodes
`in order of nondecreasing distances from I, and includ-
`ing a node in RT only if it has not been included yet and
`if its neighbor toward I in NT already is in RT. Thus the
`RT structure forms a directed tree (this would hold
`even if the N'I"s did not form trees) that is composed of
`a root node out of which subtrees from the NT’s hang.
`We will call that tree the Routing Tree.
`The description set out above leaves vague exactly
`when COMPUTED is executed, specifying only that it
`is executed within a finite time after a triggering event.
`Concrete possibilities will be suggested below.
`Because it uses breadth first searches (with respect to
`total length), our technique can be seen as an adaptive
`distributed version of Dijkstra’s algorithm. Other dis
`tributed but static implementations of Dijkstra’s method
`have been given. These approaches should not be con-
`fused with those relying on an explicit topology broad-
`cast followed by local computation.
`The fact that COMPUTEO involves sorting nodes
`and that messages include identities of nodes next to
`destination may seem prohibitive. We indicate here
`how simple data structures can alleviate much of the
`difficulty. Below, NN denotes the number of nodes in
`the network and A(I) the number of links adjacent to
`node I.
`
`For a given node I, nodes in the Routing Table and
`the Distance Tables can be organized as doubly linked
`lists, in order of increasing distances. Notice that COM-
`PUTE includes records (J,D,K) in an Update message
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`Ourgoalinthisinventionistokeeptrackofanesti-
`mated shortest path tree at each node, and the “replica"
`. of such a tree at the adjacent nodes. Although this could
`be done quite abstractly, we prefer extending the simple
`and explicit notation already used above.
`(1) To keep track of a shortest path tree at a node I we
`use three kinds of Routing Table entries. RT— D,
`RT—N and RT—L. RT—D(I,.l) is as before ;RT—N-
`(1,1) denotes the node next to J on the shortest path
`from I, while RT—L(I,J) indicates the link adjacent to
`I on a shortest path to I.
`Note that entries RT—N(I,I) are meaningless and
`they will never used. In contrast NT——N(M,I,P) is al-
`ways M at a node M adjacent to I, if P=(M,I).
`(2) The Neighbor Table now contains two kinds of
`entries, NT—D and NT—N. NT—D(I,J,P) is as before
`while NT—NUJJ’) is meant to be the node next to
`nodeJonashortestpathtoJfromnodeI, vialinkP.
`(3) Messages sent by a node I consist of packets of
`records, each record being a triple of the form
`(J.RT-D(IJ).RT-N(I.J))-
`The detail of the implementation appears below:
`
`PART I
`
`Initialization of node I
`RT—D(I.I)=0;
`
`Wf
`
`or each node I NT_D(IJ.P)= no;
`sendonl’apacketcontainingrecords
`(J,RT._D(IJ).RT.N(I,I)) for all nodes J;
`Node 1 detects a change in LEN(P) for link P (LEN(P)—
`ME.—
`within s finite time COMPUTE( );
`Node I receives an update packet
`from neighbor M on link P
`The packet is composed of records (J,D,K), where J is a
`nodeDisadistanceandKissnode.
`for each record (LDJC) in the packet {
`NT—DGJJ') = D:
`if (J=M) than NT—NUJ.P)= 1;
`$1” NT—N(IJ.P)= K4
`within a finite time COMPUTE( );
`PART 2
`
`Wf
`
`or all nodes J UNSEEN (J)=TRUE:
`UNSEENG) = FALSE;
`PACKET:- nil;
`For each link 1’, list the nodes .l in order of
`nondecrening NT_D(IJ,P). Let TOP(P) denote the
`element currently at the top of the list for link P.
`While any list is not empty {
`P‘=argmin(over P) NT_D(I,TOP(P).F) + LEN(P);
`J aTOKP‘);
`Remove J from list 1";
`
`

`

`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 8 of 9
`Case 1:16—cv-02690-AT Document 109-3 Filed 07/19/16 Page 8 of 9
`
`4,987,536
`
`5
`inorderofnondecrensingDsothatthelinkedlistfor
`NT can be updated with an amount of processing not
`worse than linear in NN. Running COMPUTEO at a
`node requires an amount of processing not worse than
`linear in NN‘A(I)‘10g(A(I)) as there are a total of
`NN‘AO) entries in the NT—linked lists and determin-
`ing P‘ during a step can be done in time proportional to
`log(A(I)). Also in a record (J,D,K) node K must appear
`before I in the updated NT list. Thus the identity of K
`can be encoded as a number, e.g. specifying the position
`of K in the list. This can make significant savings in
`networks where node identities are character strings.
`A more efficient (and complex) implementation is to
`keep a direct representation of trees for RT—and NT.
`When a new RT is computed, only the difference be-
`tween the new and old trees nwds to be communicated,
`eg. as a set of subtrees. Recall that a subtree of N nodes
`can be transmitted as N node identifies plus 2N bits.
`This can be done by walking along the subtree in depth
`first fashion, transmitting a node identity the first time it
`is met, transmitting a 0 bit each time a link is traversed
`away from the root, and a 1 bit when a link is traversed
`toward the root. If this is done, updating NT takes an
`amount of time proportional to the number of nodes in
`an update packet.
`Other savings can be realized by using information
`specific to each network. For example in networks
`where link lengths change by small amounts, it is likely
`that the structure of the Routing Tree will often remain
`unchanged, although the lengths of some links change.
`It is easy to invent coding schemes taking advantage of
`this feature.
`Various optimizations are also possible. For example
`when receiving an update message one can easily deter-
`mine if COMPUTEO needs to be rim. Also the subtree
`below I in a Routing Tree need not be sent to I while I
`is an adjacent node.
`We define the time complexity of the technique of the
`present invention as the largest time that can elapse
`between the moment the last topology change occurs
`and the moment all nodes have final shortest paths to all
`other nodes. The message complexity is defined as the
`maximum number of node identities exchanged during
`that same period.
`Before evaluating the complexity of the technique,
`we must precisely determine when COMPUTEO is
`evaluated after a triggering event in part 1 of the imple-
`mentation set forth above. There are two traditional
`possibilities, and we also suggest another
`(A) event driven: run COMPUTEO whenever a to-
`pology change occurs or an update message is received.
`One expects that this would be the fastest. However, if
`the output links have finite capacity this might result in
`update messages queueing for transmission.
`(B) periodic: run COMPUTEO at each node on a
`periodic basis, the periods need not be the same at all
`nodes. This has the effect of delaying propagation of
`changes, but may reduce the computational load and
`the number of transmitted messages.
`(C) The third possibility combines the advantages of
`(A) and (B): use (A) but avoid the possible queuing of
`messages by combining all messages queued on a link
`into a single one. That message indicates all the changes
`that must be made to NT at the receiving end in order
`to obtain there the image of the current RT at the
`source.
`
`If the procedure is operated in an event driven man-
`ner, little can be said about the time necessary for the
`
`6
`procedure to complete, or about the number of mes-
`sages that need to be exchanged. Examples can be de-
`vised to show that the number of messages may grow
`exponentially with the number of topology changes.
`Regarding the communication complexity, we can
`make a statement if one assumes both that all messages
`are processed within one time unit after being generated
`and that at most one message can traverse a link within
`a time unit. Those can be realistic assumptions in cases
`(B) and (C). Time bounds can then be transformed into
`bounds for the communication complexity; it does not
`exceed a function linear in NN‘NL‘min(NN,R‘Diam),
`where NL denotes the number of links, and Diam is
`defined as the maximum number of links in a shortest
`path.
`As we have seen above, the time complexity of the
`Ford-Bellman technique is much higher than that of our
`algorithm as routing table looping can occur. Shortest
`paths can also be computed by broadcasting the topol-
`ogy and performing local computation. This approach
`typically is faster and requires fewer messages. How-
`ever, it requires more storage and processing is not
`distributed; each node computes its Routing Tree inde-
`pendently, while in our approach a node benefits from
`the computation done by the neighbors. The difi'erence
`is striking in the case of nodes that have only one adja-
`cent link. Although we prefer the topology broadcast
`method if enough memory is available, we advocate the
`technique presented in this paper as a migration path for
`networks that currently use Ford-Bellman. Our method
`uses similar data structures and messages. but it does not
`suffer from routing table looping.
`What is claimed is:
`1. In a communications network in which a plurality
`of nodes having unique identities transmit messages
`over links that have lengths between the nodes, a ma-
`chine implemented method for sending massages from a
`first node to a destination node over a shortest path
`from the first node to the destination node, comprising
`the steps of:
`_
`forming a first routing tree for said first node that
`represents an estimated shortest path from said first
`node to other nodes and that includes all nodes that
`are connected by a link to said first node, one node
`in said first routing tree serving as a root of said
`first routing tree,
`sending. by said first node, an identical tree to all said
`nodes that are connected by a link to said first
`node, said identical tree comprising at least a por-
`tion of said first routing tree: receiving, by said first
`node, respective routing trees transmitted by said
`nodes that are connected by a link to said first
`node; and storing, by said first node, the received
`routing trees,
`forming a new routing tree for said first node using
`said received routing trees, said new routing tree
`including a group of said nodes one of which is said
`destination node,
`comparing said new routing tree to a previous rout-
`ing tree at said first node and, if said trees are differ-
`ent, determining a subsequent new routing tree that
`is not different from said previous routing tree,
`whereby said subsequent new routing tree defines
`the shortest paths from said first node to all of said
`nodes in said group, and
`transmitting messages from said that node to said
`destination node over the shortest path for said
`destination node defined by said new routing tree.
`
`5
`
`IO
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`Case 1:16-cv-02690-AT Document 109-3 Filed 07/19/16 Page 9 of 9
`Case 1:16—cv-02690-AT Document 109-3 Filed 07/19/16 Page 9 of 9
`
`4,987,536
`
`7
`2. The method of claim 1 wherein said step of form-
`ing said new routing tree comprises
`forming a large tree by placing said first node as the
`root of said large tree and creating branches that
`have lengths from said first node to roots of the
`routing trees of said nodes that are connected by a
`link to said first node, the lengths of said branches
`equaling the lengths of the links from said first node
`to said nodes, and
`determining said new routing tree based on said large
`tree.
`
`3. The method of claim 2 wherein said step of deter-
`mining said new routing tree comprises
`finding a largest connected subset of said large tree in
`which each node appears only once. said subset
`being said new routing tree.
`4. The method of claim 3 wherein said step of finding
`the largest connected subset
`includes performing a
`breadth first search of the large tree.
`5. The method of claim 4 wherein said step of deter-
`mining a subsequent new routing tree comprises broad-
`casting said new routing tree to all said nodes that are
`connected by a link to said first node and repeating said
`breadth first search, comparing, and broadcast steps
`until no new routing tree differs from a previous routing
`tree.
`
`6. The method of claim 1 further comprising storing
`said subsequent new routing tree.
`7. The method of claim 5 wherein said breadth first
`search, comparing, and broadcast steps are repeated at
`predetermined intervals or whenever there is a change
`in the lengths of the links in the network.
`8. The method of claim 1 further comprising setting
`the length ofa link to infinity upon a failure ofsaid link.
`
`B
`9. The method of claim 1 wherein the lengths of the
`links are direction dependent.
`10. The method of claim 5 wherein said step of deter-
`mining a subsequent new routing tree comprises broad-
`casting only the differences between the new routing
`tree and a previous routing tree to all nodes that are
`connected by a link to said first node and repeating said
`breadth first search, comparing, and broadcast steps
`until no new routing tree differs from a previous routing
`tree.
`
`11. The method of claim 1 comprising performing
`said steps of sending the first routing tree, receiving the
`respective routing trees from said nodes that are con-
`nected by a link to said first node, and forming said new
`routing tree whenever a change occurs in one or more
`of the links in said network.
`12. The method of claim 1 comprising performing
`said steps of sending the first routing tree, receiving the
`respective routing trees from said nodes that are con-
`nected by a link to said first node, and forming said new
`routing tree in response to receipt of a routing tree from
`another node.
`13. The method of claim 1 comprising performing
`said steps of sending the first routing tree, receiving the
`respective routing trees from said nodes that are con-
`nected by a link to said first node, and forming said new
`routing tree at predetermined time intervals.
`14. The method of claim 13 wherein the predeter-
`mined time interval for said first node is different than
`that for another node in said network.
`15. The method of claim 1 wherein said step of deter-
`mining said subsequent new routing tree includes re-
`0
`C
`$
`0
`O
`peating at least some of said steps at least once.
`
`[0
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`55
`
`65
`
`