US 7,203,191 B2Grant

Method for loop-free multipath routing using predecessor information

Issue Date:2007-04-10

•58 Claims

•7 Drawing Sheets

Abstract

A method is described for routing network traffic based on distance information to provide multiple paths that need not have equal costs. The routing algorithm MPATH of the present method provide loop-free routing at every instant, without the need of internodal synchronization which spans more than a single hop. Paths are computed using shortest distances and predecessor information in the routing computation. The use of multiple-successors allows for load-balancing within the network. The algorithm is both distributed and scalable to large networks due to its use of only one-hop synchronization. A number of procedures are described by way of example, including path computation, main table updating, neighbor table updating, and a multipath (MPATH) algorithm.

Metadata

Assignee

The Regents of the University of California

Inventors

Jose Joaquin Garcia-Luna-Aceves
Srinivas Vutukury

Application Information

Application Number:US 09/975,556

Filing Date:2001-10-10

Priority Date:2000-10-10

Art Unit:2616

Classifications

IPC:

H04L12/28

Patent Drawings (7 sheets)

Description

Cross-Reference to Related Applications

[0001] This application claims priority from U.S. provisional application Ser. No. 60/239,420 filed on Oct. 10, 2000, incorporated herein by reference.

Statement Regarding Federally Sponsored Research or Development

[0002] This invention was made with Government support under Grant No. F30602-97-2-0338, awarded by the Air Force Office of Scientific Research (AFOSR). The Government has certain rights in this invention.

Reference to a Computer Program Appendix

[0003] Not Applicable

Background of the Invention

[0004] 1. Field of the Invention

[0005] The present invention generally pertains to computing routes within a network, and more particularly to a routing algorithm for computing multiple loop-free routes between each source-destination pair.

[0006] 2. Description of the Background Art

[0007] The most popular routing protocols used in today's internets are based on the exchange of vectors of distance, such as RIP and EIGRP; or topology maps, such as OSPF. It should be noted that RIP and a number of similar routing protocols which are based on the distributed Bellman-Ford algorithm (DBF) for shortest-path computation, suffer from the bouncing effect and counting-to-infinity problems, which limit their applicability to small networks using hop count as the measure of distance. While OSPF and algorithms based on topology-broadcast are hindered by excessive communication overhead, which forces the network administrators to partition the network into distinct areas which are interconnected by a backbone. As a result the use of OSPF leads to a complex solution, in terms of the required router configuration. The routing protocol EIGRP utilizes a loop-free routing algorithm called DUAL (Diffusing Update Algorithm), which is based on internodal coordination that can span multiple hops.

[0008] In addition to DUAL, several algorithms based on distance vectors have been proposed to overcome the counting-to-infinity problem of DBF. All of these algorithms rely on exchanging queries and replies along multiple hops, a technique that is sometimes referred to as diffusing computations, because it has its origin in Dijkstra and Scholten's basic algorithm.

[0009] A couple of routing algorithms have been proposed that operate using partial topology information to eliminate the main limitations of topology-broadcast algorithms. Furthermore, several distributed shortest-path algorithms have been proposed that use the distance and second-to-last hop to destinations as the routing information exchanged among nodes. These algorithms are often called path-finding algorithms or source-tracing algorithms. All of these algorithms eliminate DBF's counting to infinity problem, and some of them are more efficient than any of the routing algorithms based on link-state information proposed to date. Furthermore, LPA (the Loop-free Path-finding Algorithm) is maintained loop-free at every instant.

[0010] With the exception of DASM (Diffusing Algorithm for Shortest Multipath), all of the above routing algorithms focus on the provision of a single path to each destination. A drawback of DASM, however, is that it uses multi-hop synchronization, which limits its scalability. Recently a routing protocol referred to as MPDA (Multiple-path Partial-topology Dissemination Algorithm) has been proposed which is a method based on link-states that provides multiple loop-free path routing utilizing one-hop synchronization.

[0011] Therefore, a need exists for a routing protocol which is scalable, and provides multipath unequal cost routing based on distance vectors, which is assured to be loop-free. The present invention satisfies those needs, as well as others, and overcomes the deficiencies of previously developed protocols.

Brief Summary of the Invention

[0012] The present invention is a routing method that determines multiple loop-free paths between source and destination pairs, which utilizes shortest distances and predecessor information in its route computation. A variant of MPDA is herein presented which is referred to as MPATH, which is a routing algorithm based on distance vectors that: (a) provides multiple paths of unequal cost to each destination that are free of loops at every instant, both in steady state as well as during network transitions, and (b) utilizes a synchronization mechanism that spans only one hop, which makes it more scalable than routing algorithms based on diffusing computations spanning multiple hops. MPATH is a path-finding algorithm, and differs from prior similar algorithms in the invariants used to ensure multiple loop-free paths of unequal cost. The peculiar differences between MPATH and MPDA is a result of the differences in the kind of information that nodes exchange.

[0013] An object of the invention is to provide a routing protocol for computing multiple routes of unequal cost.

[0014] Another object of the invention is to provide a routing protocol in which the routes are assured to be loop-free at every instant.

[0015] Another object of the invention is to provide a routing protocol that does not require internodal synchronization which spans greater than a single hop.

[0016] Another object of the invention is to provide a routing protocol of low complexity, wherein the requirements for storage, time, computation, and communication are minimized.

[0017] Another object of the invention is to provide a routing protocol which always converges to a shortest distant route.

[0018] Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing preferred embodiments of the invention without placing limitations thereon.

Brief Description of the Drawings

[0019] The invention will be more fully understood by reference to the following drawings which are for illustrative purposes only:

[0020] FIG. 1 is pseudocode for a path algorithm according to an aspect of the present invention, shown with an initialization procedure and a path routing algorithm to each destination.

[0021] FIG. 2 is pseudocode for a neighbor table update algorithm according to an aspect of the present invention.

[0022] FIG. 3A is a topology diagram within which table updates are exemplified according to an aspect of the present invention, shown with adjacent links and neighbor tables.

[0023] FIG. 3B is a topology diagram with a distance table for illustrating the table update procedure within an aspect of the present invention, shown with a table of preferred neighbors.

[0024] FIG. 4A is a topology diagram which exemplifies tie-breaking rules according to an aspect of the present invention, shown with unit link costs.

[0025] FIG. 4B is a topology diagram which exemplifies tie-breaking rules according to an aspect of the present invention, shown with costs of adjacent links and shortest-path trees of neighboring nodes.

[0026] FIG. 4C is a topology diagram which exemplifies tie-breaking rules according to an aspect of the present invention, showing a tie-break resolution.

[0027] FIG. 5 is pseudocode which exemplifies updating of the main table according to an aspect of the present invention.

[0028] FIG. 6 is pseudocode which exemplifies multipath routing according to an aspect of the present invention.

Detailed Description of the Invention

[0029] Referring more specifically to the drawings, for illustrative purposes the present invention is embodied in the apparatus and methods generally shown in FIG. 1 through

[0030] FIG. 6. It will be appreciated that the apparatus may vary as to configuration and as to details of the parts, and that the method may vary as to the specific steps and sequence, without departing from the basic concepts as disclosed herein.

1. Distributed Multipath Routing Algorithm

[0031] 1.1. Problem Formulation

[0032] A computer network is represented as a graph G=(N,L) where N is the set of nodes, typically routers, and L is the set of edges, links, connecting the nodes within the network. A cost is associated with each link that can change over time, but is always positive. Two nodes connected by a link are called adjacent nodes or neighbors. The set of all neighbors of a given node i is denoted by Nⁱ. Adjacent nodes communicate with each other using messages and messages transmitted over an operational link are received with no errors, in the proper sequence, and within a finite timeframe. Furthermore, such messages are processed by the receiving node one at a time in the order received. A node detects the failure, recovery and link cost changes of each adjacent link within a finite time.

[0033] The goal of the present distributed routing algorithm is to determine at each node i the successor set of i for destination j, which we denote by S_jⁱ(t) custom character

Nⁱ, such that the routing graph SG_j(t) consisting of link set {(m,n)|n∈S_j^m(t), m∈N} is free of loops at every instant t, even when link costs are changing with time. The routing graph SG_j(t) for single-path routing is a sink-tree rooted at j, because the successor sets S_jⁱ(t) have at most one member. In multipath routing, there can be more than one member in S_jⁱ(t) therefore, SG_j(t) is a directed acyclic graph with j as the sink node. There are potentially several SG_j(t) for each destination j; however, the routing graph we are interested is defined by the successor sets S_jⁱ(t)={k|D_j^k(t)<D_jⁱ(t), k∈Nⁱ}, where D_jⁱis the shortest distance of node i to destination j, which is referred to as a shortest multipath routing graph for destination j.

[0034] After a series of link cost changes which leave the network topology in arbitrary configuration, the distributed routing algorithm should work to modify SG_jin such a way that it eventually converges to the shortest multipath of the new configuration, without ever creating a loop in SG_jduring the process.

[0035] Since D_j^kis a local variable of node k, its value has to be explicitly or implicitly communicated to node i. If D_jkⁱis the value of D_j^kas known to node i, the problem now becomes one of computing S_jⁱ(t)={k|D_jkⁱ(t)<D_jⁱ(t)}. However, because of non-zero propagation delays during network transitions, discrepancies can exist in the value of D_j^kand its copy D_jkⁱat i, which may cause loops to form in SG_j(t). To prevent loops, therefore, additional constraints must be imposed when computing S_jⁱ. If the successor set at each node i for each destination j satisfies certain conditions called loop-free invariant conditions, then the snapshot at time t of the routing graph SG_j(t) implied by S_jⁱ(t) is free of loops. The solution within the present invention solves this problem in two parts: (1) computing D_jⁱusing a shortest-path routing algorithm called PATH, and (2) extending it to compute S_jⁱsuch that they satisfy loop-free invariant conditions at every instant.

[0036] 1.2. Node Tables and Message Structures

[0037] As in DBF, nodes executing MPATH exchange messages containing distances to destinations. In addition to the distance to a destination, nodes also exchange the identity of the second-to-last node, also called predecessor node, which is the node just before the destination node on the shortest path. In this respect MPATH is similar to several prior algorithms but differs in its specification, verification and analysis and, more importantly, in the multipath operation described in the next section.

[0038] The following information is maintained at each node:

[0039] 1. A Main Distance Table that contains D_jⁱand p_jⁱ, where D_jⁱis the distance of node i to destination j and p_jⁱis the predecessor to destination j on the shortest path from i to j. The table also stores for each destination j, the successor set S_jⁱ, feasible distance FD_jⁱ, reported distance RD_jⁱ, and two flags “changed” and “report-it”.

[0040] 2. A Main Link Table Tⁱthat is the node's view of the network and contains links represented by (m, n, d) where (m, n) is a link with cost d.

[0041] 3. A Neighbor Distance Table for neighbor k containing D_jkⁱand p_jkⁱwhere D_jkⁱis the distance of neighbor k to j as communicated by k, and p_jkⁱis the predecessor to j on the shortest path from k to j as notified by k.

[0042] 4. A Neighbor Link Table T_kⁱcontaining the view that neighbor k has of the network as known to i and contains link information derived from the distance and predecessor information in the neighbor distance table.

[0043] 5. An Adjacent Link Table that stores the cost l_kⁱof adjacent link to each neighbor k. If a link is down its cost is infinity.

[0044] Nodes exchange information using update messages which have the following format:

[0045] 1. An update message can one or more update entries. An update entry is a triplet [j,d, p], where d is the distance of the node sending the message to destination j and p is the predecessor on the path to j; and

[0046] 2. Each message carries two flags used for synchronization: query and reply.

[0047] 1.3. Computing D_jⁱ

[0048] As mentioned earlier, the strategy within the present invention is to first design a shortest-path routing algorithm and then make the multipath extensions to it. This subsection describes our shortest-path algorithm PATH and the next subsection describes the multipath extensions. FIG. 1 illustrates pseudocode for an example of the PATH procedure. INIT-PATH is called at node startup to initialize the tables, distances are initialized to infinity and node identities are initialized to a null value. PATH is executed in response to an event that can be either a receipt of an update message from a neighbor, or detection of an adjacent link cost or link status (up/down) change. PATH invokes procedure NTU, described in FIG. 2, which first updates the neighbor distance tables and then updates T_kⁱwith links (m, n, d) where d=D_nkⁱ−D_mk¹and m=p_nkⁱ. PATH then invokes procedure MTU, specified in FIG. 5, which constructs Tⁱby merging the topologies T_kⁱand the adjacent links l_kⁱ.

[0049] FIG. 3A and FIG. 3B illustrate updating of the main table 6 for an example network topology 2. FIG. 3A depicts adjacent links and neighbor tables 4 of node i, while FIG. 3B depicts the network topology 2 along with a table 6 of preferred neighbors along with the main link table of node i after merging the neighbor tables 4.

[0050] The merging process is straightforward if all neighbor topologies T_kⁱcontain consistent link information, but when two or more neighbors link tables contain conflicting information regarding a particular link, the conflict must be resolved. Two neighbor tables are said to contain conflicting information regarding a link, if either both report the link with different cost or one reports the link and the other does not. Conflicts are resolved as follows: if two or more neighbor link tables contain conflicting information of link (m, n), then Tⁱis updated with link information reported by the neighbor k that offers the shortest distance from the node i to the head node m of the link, such as l_kⁱ+D_mkⁱ=min{l_kⁱ+D_mkⁱ|k∈Nⁱ}. Ties are broken in a consistent manner; one way is to break ties always in favor of lower address neighbor. Because i itself is the head of the link for adjacent links, any information about an adjacent link supplied by neighbors will be overridden by the most current information about the link available to node i.

[0051] FIG. 4A through FIG. 4C shows the significance of the tie-breaking rule. FIG. 4A depicts an example network topology 12 with unit link costs. FIG. 4B illustrates node i having the costs of its adjacent links and the shortest path trees 14 of its neighbors p and q. The distances of nodes x and y from i is identical through both neighbors p and q. FIG. 4C illustrates that if MTU breaks ties in an arbitrary manner while constructing Tⁱ, it may choose p as the preferred neighbor for node x and choose q as the preferred neighbor for node y, which results in a graph 16 that has no path from i to j. It will be appreciated, therefore, that ties should not be broken in an arbitrary manner.

[0052] After merging the topologies, MTU runs Dijkstra's shortest path algorithm to find the shortest path tree and deletes all links from Tⁱthat are not in the tree. Because there can be more than one shortest-path tree, while running Dijkstra's algorithm ties are again broken in a consistent manner. The distances D_jⁱand predecessors p_jⁱcan then be obtained from T_i. The tree is compared with the previous shortest path tree and only the differences are then reported to the neighbors. If there are no differences, no updates are reported. Eventually all tables converge such that D_jⁱyields the shortest distances and all message activity ceases.

[0053] 1.4. Computing S_jⁱ

[0054] In this subsection, the final desired routing algorithm MPATH is derived by making extensions to PATH. MPATH computes the successor sets S_jⁱby enforcing the Loop-free Invariant conditions described below and using a neighbor-to-neighbor synchronization.

[0055] Let an “estimate” of the distance of node i to node j, be referred to as the feasible distance, FD_jⁱ; in a similar manner as FD_jⁱis equal to D_jⁱwhen the network is in a stable state, but to prevent loops during periods of network transitions, it is allowed to temporarily differ from D_jⁱ. Loop-free invariant conditions can be expressed as follows:
FD_jⁱ(t)≦D_ji^k(t)k∈Nⁱ (1)
S_jⁱ(t)={k|D_ji^k(t)<FD_jⁱ(t)} (2)

[0056] The invariant conditions (1) and (2) state that, for each destination j, a node i can choose a successor whose distance to j, as known to i, is less than the distance of node i to j that is known to its neighbors.

Theorem 1: If the LFI conditions are satisfied at any time t, the SG_j(t) implied by the successor sets S_jⁱ(t) is loop-free.

Proof: Let k∈S_jⁱ(t) then from Eq. 2 it follows that:
D_jkⁱ(t)<FD_jⁱ(t) (3)
At node k, because node i is a neighbor, from Eq. 1 above, it follows that:
FD_j^k(t)≦D_jkⁱ(t) (4)
Combining Eq. 3, and Eq. 4, it follows that:
FD_j^k(t)<FD_jⁱ(t) (5)
Eq. 5 states that, if k is a successor of node i in a path to destination j, then k's feasible distance to j is strictly less than the feasible distance of node i to node j. Now if the successor sets define a loop at time t with respect to node j, then for some node p on the loop, an absurd relation is arrived at wherein FD_j^p(t)<FD_j^p(t).
Therefore, the LFI conditions are sufficient for loop-freedom.

[0057] The invariants used in LFI are independent of whether the algorithm uses link states or distance vectors; in link-state algorithms, such as MPDA, the D_jkⁱare computed locally from the link-states communicated by the neighbors while in distance-vector algorithms, like the MPATH presented here, the D_jkⁱare directly communicated.

[0058] The invariants (1) and (2) suggest a technique for computing S_jⁱ(t) such that the successor graph SG_j(t) for destination j is loop-free at every instant. The key is determining FD_jⁱ(t) in Eq. (1), which requires node i to know D_ji^k(t), the distance from node i to node j in the topology table T_i^kthat node i communicated to neighbor k. As a result of non-zero propagation delays, T_i^kis a time-delayed version of Tⁱ. It will be appreciated that, if node i delays updating of FD_jⁱwith D_jⁱuntil k incorporates the distance D_jⁱin its tables, then FD_jⁱsatisfies the LFI condition.

[0059] FIG. 6 exemplifies pseudocode for MPATH which enforces the LFI conditions by synchronizing the exchange of update messages among neighbors using query and reply flags. If a node sends a message with a query bit set, then the node must wait until a reply is received from all its neighbors before the node is allowed to send the next update message. The node is said to be in ACTIVE state during this period. The inter-neighbor synchronization used in MPATH spans only one hop, unlike algorithms that use diffusing computation that potentially span the whole network, such as DASM.

[0060] Assume that all nodes are in a PASSIVE state initially with correct distances to all other nodes and that no messages are in transit or pending to be processed. The behavior of the network where every node runs MPATH is such that when a finite sequence of link cost changes occurs in the network within a finite time interval, some or all nodes to go through a series of PASSIVE-to-ACTIVE and ACTIVE-to-PASSIVE state transitions, until eventually all nodes become PASSIVE with correct distances to all destinations.

[0061] Let a node in PASSIVE state receive an event resulting in changes in its distances to some destinations. Before the node sends an update message to report new distances, it checks if the distance D_jⁱto any destination j has increased above the previously reported distance RD_jⁱ. If none of the distances increased, then the node remains in PASSIVE state. Otherwise, the node sets the query flag in the update message, sends it, and goes into ACTIVE state. When in ACTIVE state, a node cannot send any update messages or add neighbors to any successor set. After receiving replies from all its neighbors, the node is allowed to modify the successor sets and report any changes that may have occurred since the time it has transitioned to ACTIVE state, and if none of the distances increased beyond the reported distance, the node transitions to PASSIVE state. Otherwise, the node sends the next update message with the query bit set and becomes ACTIVE again, and the whole cycle repeats. If a node receives a message with the query bit set when in PASSIVE state, it modifies its tables and then sends back an update message with the reply flag set. Otherwise, if the node happens to be in ACTIVE state, it modifies the tables but because the node is not allowed to send updates when in ACTIVE state, the node sends back an empty message with no updates but the reply bit set. If a reply from a neighbor is pending, when the link to the neighbor fails then an implicit reply is assumed, and such a reply is assumed to report an infinite distance to the destination. Because replies are given immediately to queries and replies are assumed to be given upon link failure, deadlocks due to inter-neighbor synchronization cannot occur. Eventually, all nodes become PASSIVE with correct distances to destinations.

2. Correctness of MPATH

[0062] The following properties of MPATH are to be proven: (1) MPATH eventually converges with D_jⁱ; giving the shortest distances and (2) the successor graph SG_jis loop-free at every instant and eventually converges to the shortest multipath. PATH works essentially like PDA except that the kind of update information exchanged is different; PDA exchanges link-state while PATH exchanges distance-vectors with predecessor information. The correctness proof of PATH is identical to PDA and are reproduced here for correctness. The convergence of MPATH directly follows from the convergence of PATH because extensions to MPATH are such that update messages in MPATH are only delayed a finite amount of time.

[0063] Definitions: The n-hop minimum distance of node i to node j in a network is the minimum distance possible using a path of n hops, (links) or less. A path that offers the n-hop minimum distance is called n-hop minimum path. If there is no path with n hops or less from node i to j then the n-hop minimum distance from i to j is undefined. An n-hop minimum tree of a node i is a tree in which node i is the root and all paths of n hops or less from the root to any other node is an n-hop minimum path.

[0064] Let G denote the final topology of the network, as would be seen by an omniscient observer after all link changes have occurred. Without loss of generality, assume G is connected; if G is disconnected, the proof applies to each connected component independently.

[0065] It is presumed that a router i knows at least the n-hop minimum tree, if the tree contained in its main link table Tⁱis at least an n-hop minimum tree rooted at i in G, and there are at least n nodes in Tⁱthat are reachable from the root i. Note that Tⁱis such that the links with head nodes that are more than n hops away from i may have costs that do not agree with the link costs in G.

Theorem 2: If node i has adjacent link costs that agree with G and for each neighbor k, T_kⁱrepresents at least an (n−1)-hop minimum tree, then after the execution of MTU, the minimum cost tree contained in Tⁱis at least an n-hop minimum tree.

[0066] Proof: Let H_nⁱdenote an n-hop minimum tree rooted at node i in G and let M_nⁱbe the set of nodes that are within n hops from i in H_nⁱ. Let D_n^ijdenote the distance of i to j in H_nⁱ. Let d_ijbe the cost of the link i→j. Node i is called the head of the link i→j. The notation i custom character

j indicates a path from i to j of zero or more links; if the path has zero links, then i=j. The length of path i custom character

j is the sum of costs of all links in the path.
Property 1: From the principle of optimality (the sub-path of a shortest path between two nodes is also the shortest path between the end nodes of the sub-path), if H and H′ are two n-hop minimum trees rooted at node i and M and M′ are sets of nodes that are within n hops from i in H and H′ respectively, then M=M′=M_nⁱand M_nⁱ≧n. For each j∈M_nⁱthe length of path i custom character

j in both H and H′ is equal to D_n^ij. For h≧n, D_h^ij≦D_n^ij.

[0067] Let Aⁱ= custom character

_k∈N_iA_kⁱ, where A_kⁱis the set of nodes in T_kⁱ. Because T_kⁱis at least an (N−1)-hop minimum tree and node i can appear at most once in each of A_kⁱ, each A_kⁱhas at least N−1 unique elements. Therefore, Aⁱhas at least N−1 elements.

[0068] Let M_nⁱbe the set of n−1 nearest elements to node i in Aⁱ. That is, M_nⁱ custom character

Aⁱ, |M_nⁱ|=n−1, and for each j∈M_nⁱ, and ν∈Aⁱ−M_nⁱ, min{D_jkⁱ+l_kⁱ|k∈Nⁱ}≦min{D_νkⁱ+l_kⁱ|k∈Nⁱ}.

To prove the theorem it is sufficient to prove the following:

[0069] 1. Let G_nⁱrepresent the graph constructed by MTU on lines 2 and 3. (i.e., before applying Dijkstra in line 4). For each j∈M_nⁱthere is a path ij in G_nⁱsuch that its length is at most D_n^ij.
[0070] 2. After running Dijkstra on G_nⁱon line 4 in MTU, the resulting tree is at least an n-hop minimum tree.

[0071] Let us first assume part 1 is true and prove part 2. From the statement in part 1 for each node j∈M_nⁱthere is a path i custom character

j in G_nⁱwith length at most D_n^ij. In the resulting tree after running Dijkstra, we can infer there is a path i custom character

j with length at most D_n^ij. Because there are n−1 nodes in M_nⁱ, the tree constructed has at least n nodes including node i. From property 1, it follows that the tree constructed is at least an n-hop minimum tree.

[0072] To prove part 1, order the nodes in M_nⁱin non-decreasing order. The proof is by induction on the sequence of elements in M_nⁱ. The base case is true because for m₁, the first element of Mⁱ, l_m₁ⁱ=min{l_kⁱ|k∈Nⁱ} and l_m₁ⁱ=D₁^i,ms 1. As induction hypothesis, let the statement hold for the first m−1 elements of M_nⁱ. Consider the m^thelement j∈M_nⁱ. Let K be the highest priority neighbor for which D_jkⁱ+l_kⁱ=min{D_jkⁱ+l_kⁱ|k∈Nⁱ}. At most m−1 nodes in T_Kⁱcan have lesser or equal distance than j which implies path K custom character

j exists with at most m−1 hops. Let ν be the neighbor of j in T_Kⁱ. Then the path K custom character

ν→j has at most m−1 hops. Because T_Kⁱis at least a (n−1)-hop minimum tree, the link ν→j must agree with G. Since D_νKⁱ+l_Kⁱ<D_jKⁱ+l_Kⁱ, from the induction hypothesis there is a path i custom character

ν in G, such that the length is at most D_n^i,ν.

[0073] The following now shows that the preferred neighbor for ν is also K, so that the link ν→j will be included in the construction of G_nⁱthus ensuring the existence of the path i custom character

j in G_nⁱ. If some neighbor K′ other than K is the preferred neighbor for ν then one of the following two conditions should hold: (a) D_νK′ⁱ+l_K′ⁱ<D_νKⁱ+l_Kⁱor (b) D_νK′ⁱ+l_K′ⁱ=D_νKⁱ+l_Kⁱand priority of K′ is greater than priority of K.

[0074] Case (a): Because D_jKⁱ+l_Kⁱ≦D_jK′ⁱ+l_K′ⁱit follows that the path ν custom character

j in T_K′ⁱ, is greater than cost of ν→j in G which implies that T_K′ⁱ, is not an (n−1) hop minimum tree, which contradicts the assumption. Therefore D_νkⁱ+l_kⁱ=min{D_νkⁱ+l_kⁱ|k∈Nⁱ}.

[0075] Case (b): Let Q_jbe the set of neighbors that give the minimum distance for j, such as for each k∈Q_j, D_jkⁱ+l_kⁱ=min{D_jkⁱ+l_kⁱ|k∈Nⁱ}. Similarly, let Q_νbe such that for each k∈Q_ν, D_νkⁱ+l_kⁱ=min{D_νkⁱ+l_kⁱ|k∈Nⁱ}. If k∈Q_νand k∉Q_j, then it follows from same argument as in case (a) that ν custom character

j in T_kⁱis greater than cost of ν→j in G implying T_kⁱis not a (n−1) hop minimum tree, which again is a contradiction of the assumption. Because K has the highest priority among all members of Q_jand Q_ν custom character

Q_jand k∈Q_ν, K also has the highest priority among all members of Q_ν. Therefore Q_ν custom character

Q_j. Also, from the same argument it can be inferred that K∈Q_ν. This proves that ν→j will be included in the construction of G_nⁱ. Because D_n^i,ν+d_νj=D_n^i,jin G, where d_νjis the final cost of link ν→j, and length of i custom character

ν in G_nⁱless than or equal to D_n^i,νfrom the induction hypothesis, the length of i custom character

ν in G_nⁱis less than or equal to D_n^i,j. This proves part 1 of the theorem.

Theorem 3: A finite time after the last link cost change in the network, the main topology Tⁱat each node i gives the correct shortest paths to all known destinations.

[0076] Proof: The proof is identical to the proof of Theorem 2 and is performed by induction on t_n, the global time when for each node i, Tⁱis at least an n-hop minimum tree. Because the longest loop-free path in the network has at most N−1 links where N is number of nodes in the network, t_N−1is the time when every node has the shortest path to every other node, wherein t_N−1should be shown to be finite. The base case of t_N−1is t₁, the time when every node has a one-hop minimum distance and because the adjacent link changes are notified within finite time, t₁<∞. Let t_n<∞ for some n<N. Given that the propagation delays are finite, each node will have each of its neighbors n-hop minimum tree in finite time after t_n. From Theorem 2 we can see that the node will have at least the (n+1)-hop minimum tree in finite time after t_n. Therefore, t_n+1<∞. From induction it will be appreciated that t_N−1<∞.

[0077] A node generates update messages only to report changes in distances and predecessor, so after convergence no messages will be generated. The following theorems show that MPATH provides instantaneous loop-freedom and correctly computes the shortest multipath.

Theorem 4: For the algorithm MPATH executed at node i, let t_nbe the time when RD_jⁱis updated and reported for the n^thtime. Then, the following conditions always hold:
FD_jⁱ(t_n)≦min{RD_jⁱ(t_n−1),RD_jⁱ(t_n)} (6)
FD_jⁱ(t)≦FD_jⁱ(t_n)t∈[t_n,t_n+1] (7)
Proof: From the working of MPATH in FIG. 6, it is observed that RD_jⁱis updated at line 3c when (a) the node goes from PASSIVE-to-ACTIVE because of one or more distance increases; (b) the node receives the last reply and goes from ACTIVE-to-PASSIVE state; (c) the node is in PASSIVE state and remains in PASSIVE state because the distance did not increase for any destination; and (d) the node receives the last reply but immediately goes into ACTIVE state. The reported distance RD_jⁱremains unchanged during the ACTIVE phase. Because FD_jⁱis updated at line 3a each time RD_jⁱis updated at line 3c, Eq. (6) follows. When the node is in ACTIVE phase, FD_jⁱmay also be modified by the statement on line 3f, which implies Eq. (7).
Theorem 5: The safety property; at any time t, the successor sets S_jⁱ(t) which are computed by MPATH are loop-free.
Proof: The proof is based on showing that the FD_jⁱand S_jⁱcomputed by MPATH satisfy the LFI conditions. Let t_n, be the time when RD_jⁱis updated and reported for the n^thtime. The proof is by induction on the interval [t_n,t_n+1]. Let the LFI condition be true up to time t_n, we show that:
FD_jⁱ(t)≦D_ji^k(t)t∈[t_n,t_n+1] (8)
From Theorem 4 we have:
FD_jⁱ(t_n)≦min{RD_jⁱ(t_n−1),RD_jⁱ(t_n)} (9)
FD_jⁱ(t_n+1)≦min{RD_jⁱ(t_n),RD_jⁱ(t_n+1)} (10)
FD_jⁱ(t)≦FD_jⁱ(t_n)t∈[t_n,t_n+1] (11)
Combining the above equations we arrive at:
FD_jⁱ(t)≦min{RD_jⁱ(t_n−1),RD_jⁱ(t_n)}t∈[t_n,t_n+1] (12)

[0078] Let t′ be the time when a message sent by i at t_nis received and processed by neighbor k. Because of the non-zero propagation delay across any link, t′ is such that t_n<t′<t_n+1and because RD_jⁱis modified at t_nand remains unchanged in (t_n,t_n+1) it follows that:
RD_jⁱ(t_n−1)≦D_ji^k(t)t∈[t_n,t′] (13)
RD_jⁱ(t_n)≦D_ji^k(t)t∈[t_n,t_n+1] (14)
From Eq. (13) and (14):
min{RD_jⁱ(t_n−1),RD_jⁱ(t_n)}≦D_ji^k(t)t∈[t_n,t_n+1] (15)
From (12) and (15) the inductive step (8) follows. Because FD_jⁱ(t₀)≦D_ji^k(t₀) at initialization, from induction it is known that FD_jⁱ(t)≦D_ji^k(t₀) for all t. Given that the successor sets are computed based on FD_jⁱ(t), it follows that the LFI conditions are always satisfied. According to the Theorem 1 this implies that the successor graph SG_jis always loop-free.
Theorem 6: Liveness property; a finite time after the last change in the network, the D_jⁱgives the correct shortest distances and S_jⁱ={k|D_j^k<D_jⁱ, k∈Nⁱ}.
Proof: The proof is similar to the proof of Theorem 4. The convergence of MPATH follows directly from the convergence of PATH because the update messages in MPATH are only delayed a finite time as allowed at line 4 in algorithm PATH. Therefore, the distances D_jⁱin MPATH also converge to shortest distances. Because changes to D_jⁱare always reported to the neighbors and are incorporated by the neighbors in their tables in finite time D_jkⁱ=D_j^k, for k∈Nⁱafter convergence. From line 3a in MPATH, it is observed that when node i becomes passive FD_jⁱ=D_jⁱholds true. Because all nodes are passive at convergence it follows that S_jⁱ={k|D_jkⁱ<FD_jⁱ, k∈Nⁱ}={k|D_j^k<D_jⁱ, k∈Nⁱ}.
3. Complexity Analysis

[0079] The main difference between PATH and MPATH is that the update messages sent in MPATH are delayed a finite amount of time in order to enforce the invariants. As a result, the complexity of PATH and MPATH are essentially the same and are therefore collectively analyzed.

[0080] The storage complexity is the amount of table space needed at a node. Each one of the Nⁱneighbor tables and the main distance tables has size of the order O(|N|) and the main link table Tⁱcan grow, during execution of MTU, to size at most |Nⁱ|times O(|N|). The storage complexity is therefore of the order O(|Nⁱ||N|).

[0081] The time complexity is the time it takes for the network to converge after the last link cost change in the network. To determine time complexity it is assumed that the computation time is negligible in comparison with the communication time. If t_nis the time when every node has the n-hop minimum tree, because every node processes and reports changes in finite time |t_n+1−t_n| is bounded. Let |t_n+1−t_n|≦θ for some finite constant θ. From theorem 3, the convergence time can be at most |N|θ and, hence, the time complexity is O(|N|).

[0082] The computation complexity is the time taken to build the node's shortest path tree in Tⁱfrom the neighbor tables T_kⁱ. Updating of Tⁱwith T_kⁱinformation is O(|Nⁱ||N|) operation and running Dijkstra on Tⁱtakes O(|Nⁱ||N|log(|N|)). Therefore the computational complexity is O(|Nⁱ||N|+|Nⁱ||N|log(|N|)).

[0083] The communication complexity is the number of update messages required for propagating a set of link-cost changes. The analysis for multiple link-cost-changes is complex because of the sensitivity to the timing of the changes. So, therefore the analysis is provided only for the case of a single link-cost change. A node removes a link from its shortest path tree if only a shorter path using two or more links is discovered and the path is stored. Therefore, a removed link will not be added again to the shortest path which means that a link can be included and deleted from the shortest path by a node at most one time. It will be appreciated that since nodes report each change only once to each neighbor, that an update message can travel only once on a given link and therefore the number of messages sent by a node can be at most O(|E|).

[0084] For certain topologies and sensitively timed sequences of link cost changes the amount of communication required by PATH can be exponential. One industry example (Humblet) exhibits such behavior, and though PATH is different from the shortest-path algorithm utilized therein, it should be noted that PATH is not immune from such exponential behavior. However, it appears that such scenarios would require sensitively timed link-cost changes which are very unlikely to occur in practice. If necessary, a small hold-down time before sending update messages may be used to prevent such behavior.

[0085] Accordingly, it will be seen that this invention provides a routing algorithm based on distance information that provides multiple paths that need not have equal costs and that are loop-free at every instant, without requiring inter-nodal synchronization spanning more than one hop. The loop-free invariant conditions presented here are quite general and can be used with existing internet protocols. The multiple successors that MPATH makes available at each node can be used for traffic load-balancing, which is necessary for minimizing delays in a network as has been shown using other algorithms, such as MPDA. MPATH can therefore be used as an alternative to MPDA to get similar performance.

[0086] Although the description above contains many specificities, these should not be construed as limiting the scope of the invention but as merely providing illustrations of some of the presently preferred embodiments of this invention. Therefore, it will be appreciated that the scope of the present invention fully encompasses other embodiments which may become obvious to those skilled in the art, and that the scope of the present invention is accordingly to be limited by nothing other than the appended claims, in which reference to an element in the singular is not intended to mean “one and only one” unless explicitly so stated, but rather “one or more.” All structural, chemical, and functional equivalents to the elements of the above-described preferred embodiment that are known to those of ordinary skill in the art are expressly incorporated herein by reference and are intended to be encompassed by the present claims. Moreover, it is not necessary for a device or method to address each and every problem sought to be solved by the present invention, for it to be encompassed by the present claims. Furthermore, no element, component, or method step in the present disclosure is intended to be dedicated to the public regardless of whether the element, component, or method step is explicitly recited in the claims. No claim element herein is to be construed under the provisions of 35 U.S.C. 112, sixth paragraph, unless the element is expressly recited using the phrase “means for.”

Claims

What is claimed is:

1. A method for loop-free multipath routing of data in a network, comprising:

(a) maintaining at each node i in a network,

(i) a main distance table (MDT) containing D_jⁱand p_jⁱ, where D_jⁱis the distance of node i to destination j and p_jⁱis the predecessor to destination j on the shortest path from i to j,

(ii) said MDT further containing, for each destination j, successor set S_jⁱ, feasible distance FD_jⁱ, reported distance RD_jⁱ, and flags designated as changed and report-it,

(iii) a main link table (MLT) Tⁱwhich is the node's view of the network and contains links represented by (m, n, d) where (m, n) is a link with cost d,

(iv) a neighbor distance table (NDT) for neighbor k containing D_jkⁱand p_jkⁱwhere D_jkⁱis the distance of neighbor k to j as communicated by k and p_jkⁱis the predecessor to j on the shortest path from k to j as notified by k,

(v) a neighbor link table (NLT)T_kⁱwhich is the view that neighbor k has of the network as known to i and contains link information derived from the distance and predecessor information in the NDT, and

(vi) an adjacent link table (ALT) containing the cost l_kⁱof an adjacent link to each neighbor k, wherein said cost is infinity if a link is down;

(b) in response to receipt of an update message M from a neighbor k, detection of a change in cost of an adjacent link to k, or detection of a change in status of an adjacent link to k,

(i) updating the NDT and NLT for neighbor k with links (m, n, d) where d=D_nkⁱ−D_mkⁱand m=p_nkⁱ, and

(ii) constructing an MLT for neighbor k by merging topologies T_kⁱand adjacent links l_kⁱ; and

wherein at least one said loop-free path is determined using information in each of said tables at each node i.

2. A method as recited in claim 1, further comprising:

(d) for each destination j marked as changed, adding an update entry [j,D_jⁱ, p_jⁱ] to a new message M′; and

(e) within a finite amount of time, sending message M′ to each neighbor k.

3. A method as recited in claim 2, wherein an update message comprises:

at least one update entry;

said update entry comprising a triplet [j,d,p], where d is the distance of the node sending the message to destination j and p is the predecessor on the path to j; and

flags for synchronization designated as query and reply.

4. A method as recited in claim 1, further comprising:

updating the MLT with link information reported by the neighbor k that offers the shortest distance from the node i to the head node m of the link if two or more NLTs contain conflicting information of link (m, n).

5. A method as recited in claim 1, further comprising:

after merging topologies T_kⁱand adjacent links l_kⁱ, running Dijkstra's shortest path algorithm to find the shortest path tree and deletes all links from the MLT that are not in the tree.

6. A method as recited in claim 5, further comprising:

obtaining distances D_jⁱand predecessors p_jⁱfrom the MLT.

7. A method as recited in claim 6, further comprising:

comparing the tree with the previous shortest path tree and reporting only the differences to the neighbors.

8. A method as recited in claim 1, further comprising:

computing a successor set S_jⁱby, for each destination j, allowing a node i to choose a successor having a distance to j as known to i that is less than the distance of node i to destination j that is known to a neighbor of node i.

9. A method as recited in claim 8, further comprising synchronizing the exchange of update messages among neighbors using query and reply flags contained within the messages.

10. A method as recited in claim 9, wherein if a node sends a message with a query flag set, said node must wait until a reply is received from all of said node's neighbors before said node is allowed to send the next update message.

11. A method as recited in claim 10, wherein said node is deemed to be in an ACTIVE state when said node sends a message with a query flag set.

12. A method as recited in claim 11, wherein said node is deemed to be in a PASSIVE state when said node has no message with a query flag set that is in transit or pending to be processed.

13. A method as recited in claim 12:

wherein if a node in a PASSIVE state receives an event resulting in changes in its distances to a destination, before the node sends an update message to report a new distance, said node checks if the distance D_jⁱto any destination j has increased above the previously reported distance RD_jⁱ;

wherein if no distance has increased, then said node remains in a PASSIVE state; and

wherein if a distance has increased, said node sets the query flag in the update message, sends said message, and goes into an ACTIVE state.

14. A method as recited in claim 11;

wherein a node in an ACTIVE cannot send any update messages or add neighbors to any successor set;

wherein after receiving replies from all its neighbors, the node is allowed to modify the successor sets and report any changes that may have occurred since the time it has transitioned to ACTIVE state; and

wherein if none of the distances increased beyond the reported distance, the node transitions to PASSIVE state.

15. A method as recited in claim 12:

wherein if a node receives a message with the query flag set when in PASSIVE state, said node modifies said node's tables and sends back an update message with the reply-flag set; and

wherein if a node receives a message with the query flag set when in ACTIVE stage, said node modifies said node's tables and sends back an empty message with no updates and with the reply flag set.

16. A method for loop-free multipath routing of data in a network, comprising:

(a) maintaining at each node i in a network,

(i) a main distance table (MDT) containing D_jⁱand p_jⁱ, where D_jⁱis the distance of node i to destination j and p_jⁱis the predecessor to destination j on the shortest path from i to j,

(ii) said MDT further containing, for each destination j, successor set S_jⁱ, feasible distance FD_jⁱ, reported distance RD_jⁱ, and flags designated as changed and report-it,

(iii) a main link table (MLT) Tⁱwhich is the node's view of the network and contains links represented by (m, n, d) where (m, n) is a link with cost d,

(vi) an adjacent link table (ALT) containing the cost l_kⁱof an adjacent link to each neighbor k, wherein said cost is infinity if a link is down;

(b) in response to receipt of an update message M from a neighbor k, detection of a change in cost of an adjacent link to k, or detection of a change in status of an adjacent link to k,

(i) updating the NDT and NLT for neighbor k with links (m, n, d) where d=D_nkⁱ−D_mkⁱand m=p_nkⁱ, and

(ii) constructing an MLT for neighbor k by merging topologies T_kⁱand adjacent links l_kⁱ;

(d) within a finite amount of time, sending message M′ to each neighbor k; and

(e) routing data through a loop-free path in the network;

wherein at least one said loop-free path is determined using information in each of said tables at each node i.

17. A method as recited in claim 16, wherein an update message comprises:

at least one update entry;

said update entry comprising a triplet [j,d,p], where d is the distance of the node sending the message to destination j and p is the predecessor on the path to j; and

flags for synchronization designated as query and reply.

18. A method as recited in claim 16, further comprising:

updating the MLT with link information reported by the neighbor k that offers the shortest distance from the node i to the head node m of the link if two or more neighbor link tables contain conflicting information of link (m, n).

19. A method as recited in claim 16, further comprising:

after merging topologies T_kⁱand adjacent links l_kⁱ, running Dijkstra's shortest path algorithm to find the shortest path tree and deletes all links from the MLT that are not in the tree.

20. A method as recited in claim 19, further comprising:

obtaining distances D_jⁱand predecessors p_jⁱfrom the MLT.

21. A method as recited in claim 20, further comprising:

comparing the tree with the previous shortest path tree and reporting only the differences to the neighbors.

22. A method for loop-free multipath routing of data in a network, comprising:

(a) maintaining at each node i in a network,

(i) a main distance table (MDT) containing D_jⁱand p_jⁱ, where D_jⁱis the distance of node i to destination j and p_jⁱis the predecessor to destination j on the shortest path from i to j,

(ii) said MDT further containing, for each destination j, successor set S_jⁱfeasible distance FD_jⁱ, reported distance RD_jⁱ, and flags designated as changed and report-it,

(iii) a main link table (MLT) Tⁱwhich is the node's view of the network and contains links represented by (m, n, d) where (m, n) is a link with cost d,

(vi) an adjacent link table (ALT) containing the cost l_kⁱof an adjacent link to each neighbor k, wherein said cost is infinity if a link is down;

(b) in response to receipt of an update message M from a neighbor k, detection of a change in cost of an adjacent link to k, or detection of a change in status of an adjacent link to k,

(i) updating the NDT and NLT for neighbor k with links (m, n, d) where d=D_nkⁱ−D_mkⁱand m=p_nkⁱ,

(ii) constructing an MLT for neighbor k by merging topologies T_kⁱand adjacent links l_kⁱ;

(c) computing a successor set S_jⁱby, for each destination j, allowing a node i to choose a successor having a distance to j as known to i that is less than the distance of node i to destination j that is known to a neighbor of node i; and

(d) routing data through a loop-free path in the network;

wherein at least one said loop-free path is determined using information in said tables at each node i.

23. A method as recited in claim 22, further comprising:

24. A method as recited in claim 22, further comprising:

after merging topologies T_kⁱand adjacent links l_kⁱ, running Dijkstra's shortest path algorithm to find the shortest path tree and deletes all links from the MLT that are not in the tree.

25. A method as recited in claim 24, further comprising:

obtaining distances D_jⁱand predecessors p_jⁱfrom the MLT.

26. A method as recited in claim 25, further comprising:

comparing the tree with the previous shortest path tree and reporting only the differences to the neighbors.

27. A method as recited in claim 22, further comprising synchronizing the exchange of update messages among neighbors using query and reply flags contained within the messages.

28. A method as recited in claim 27, wherein if a node sends a message with a query flag set, said node must wait until a reply is received from all of said node's neighbors before said node is allowed to send the next update message.

29. A method as recited in claim 28, wherein said node is deemed to be in an ACTIVE state when said node sends a message with a query flag set.

30. A method as recited in claim 29, wherein said node is deemed to be in a PASSIVE state when said node has no message with a query flag set that is in transit or pending to be processed.

31. A method as recited in claim 30:

wherein if no distance has increased, then said node remains in a PASSIVE state; and

wherein if a distance has increased, said node sets the query flag in the update message, sends said message, and goes into an ACTIVE state.

32. A method as recited in claim 29, wherein a node in an ACTIVE cannot send any update messages or add neighbors to any successor set.

33. A method as recited in claim 29:

wherein if none of the distances increased beyond the reported distance, the node transitions to PASSIVE state.

34. A method as recited in claim 30:

wherein if a node receives a message with the query flag set when in PASSIVE state, said node modifies said node's tables and sends back an update message with the reply flag set; and

wherein if a node receives a message with the query flag set when in ACTIVE stage, said node modifies said node's tables and sends back an empty message with no updates and with the reply flag set.

35. A method for loop-free multipath routing of data in a network, comprising:

(a) maintaining at each node i in a network,

(i) a main distance table (MDT) containing D_jⁱand p_jⁱ, where D_jⁱis the distance of node i to destination j and p_jⁱis the predecessor to destination j on the shortest path from i to j,

(ii) said MDT further containing, for each destination j, successor set S_jⁱ, feasible distance FD_jⁱ, reported distance RD_jⁱ, and flags designated as changed and report-it,

(iii) a main link table (MLT) Tⁱwhich is the node's view of the network and contains links represented by (m, n, d) where (m, n) is a link with cost d,

(vi) an adjacent link table (ALT) containing the cost l_kⁱof an adjacent link to each neighbor k, wherein said cost is infinity if a link is down;

(b) in response to receipt of an update message M from a neighbor k, detection of a change in cost of an adjacent link to k, or detection of a change in status of an adjacent link to k,

(i) updating the NDT and NLT for neighbor k with links (m, n, d) where d=D_nkⁱ−D_mkⁱand m=p_nkⁱ,

(ii) constructing an MLT for neighbor k by merging topologies T_kⁱand adjacent links l_kⁱ, and

(iii) running Dijkstra's shortest path algorithm to find the shortest path tree and deletes all links from the MLT that are not in the tree;

(d) routing data through a loop-free path in the network;

wherein at least one said loop-free path is determined using information in said tables at each node i.

36. A method as recited in claim 35, further comprising:

37. A method as recited in claim 36, further comprising:

obtaining distances D_jⁱand predecessors p_jⁱfrom the MLT.

38. A method as recited in claim 37, further comprising:

comparing the tree with the previous shortest path tree and reporting only the differences to the neighbors.

39. A method as recited in claim 35, further comprising synchronizing the exchange of update messages among neighbors using query and reply flags contained within the messages.

40. A method as recited in claim 39, wherein if a node sends a message with a query flag set, said node must wait until a reply is received from all of said node's neighbors before said node is allowed to send the next update message.

41. A method as recited in claim 40, wherein said node is deemed to be in an ACTIVE state when said node sends a message with a query flag set.

42. A method as recited in claim 41, wherein said node is deemed to be in a PASSIVE state when said node has no message with a query flag set that is in transit or pending to be processed.

43. A method as recited in claim 42:

wherein if no distance has increased, then said node remains in a PASSIVE state; and

wherein if a distance has increased, said node sets the query flag in the update message, sends said message, and goes into an ACTIVE state.

44. A method as recited in claim 41, wherein a node in an ACTIVE cannot send any update messages or add neighbors to any successor set.

45. A method as recited in claim 41:

wherein if none of the distances increased beyond the reported distance, the node transitions to PASSIVE state.

46. A method as recited in claim 42:

wherein if a node receives a message with the query flag set when in PASSIVE state, said node modifies said node's tables and sends back an update message with the reply flag set; and

wherein if a node receives a message with the query flag set when in ACTIVE stage, said node modifies said node's tables and sends back an empty message with no updates and with the reply flag set.

47. A method for loop-free multipath routing of data in a network, comprising:

(a) maintaining at each node i in a network,

(i) a main distance table (MDT) containing D_jⁱand p_jⁱ, where D_jⁱis the distance of node i to destination j and p_jⁱis the predecessor to destination j on the shortest path from i to j,

(ii) said MDT further containing, for each destination j, successor set S_jⁱ, feasible distance FD_jⁱ, reported distance RD_jⁱ, and flags designated as changed and report-it,

(iii) a main link table (MLT) Tⁱwhich is the node's view of the network and contains links represented by (m, n, d) where (m, n) is a link with cost d,

(vi) an adjacent link table (ALT) containing the cost l_kⁱof an adjacent link to each neighbor k, wherein said cost is infinity if a link is down;

(b) in response to receipt of an update message M from a neighbor k, detection of a change in cost of an adjacent link to k, or detection of a change in status of an adjacent link to k,

(i) updating the NDT and NLT for neighbor k with links (m, n, d) where d=D_nkⁱ−D_mkⁱand m=p_nkⁱ,

(ii) constructing an MLT for neighbor k by merging topologies T_kⁱand adjacent links l_kⁱ;

(d) synchronizing the exchange of update messages among neighbors using query and reply flags contained within the messages; and

(e) routing data through a loop-free path in the network;

wherein at least one said loop-free path is determined using information in said tables at each node i.

48. A method as recited in claim 47, further comprising:

49. A method as recited in claim 47, further comprising:

after merging topologies T_kⁱand adjacent links l_kⁱ, running Dijkstra's shortest path algorithm to find the shortest path tree and deletes all links from the MLT that are not in the tree.

50. A method as recited in claim 49, further comprising:

obtaining distances D_jⁱand predecessors p_jⁱfrom the MLT.

51. A method as recited in claim 50, further comprising:

comparing the tree with the previous shortest path tree and reporting only the differences to the neighbors.

52. A method as recited in claim 47, wherein if a node sends a message with a query-flag set, said node must wait until a reply is received from all of said node's neighbors before said node is allowed to send the next update message.

53. A method as recited in claim 52, wherein said node is deemed to be in an ACTIVE state when said node sends a message with a query flag set.

54. A method as recited in claim 53, wherein said node is deemed to be in a PASSIVE state when said node has no message with a query flag set that is in transit or pending to be processed.

55. A method as recited in claim 54:

wherein if no distance has increased, then said node remains in a PASSIVE state; and

wherein if a distance has increased, said node sets the query flag in the update message, sends said message, and goes into an ACTIVE state.

56. A method as recited in claim 53, wherein a node in an ACTIVE cannot send any update messages or add neighbors to any successor set.

57. A method as recited in claim 53:

wherein if none of the distances increased beyond the reported distance, the node transitions to PASSIVE state.

58. A method as recited in claim 54:

wherein if a node receives a message with the query flag set when in PASSIVE state, said node modifies said node's tables and sends back an update message with the reply-flag set; and

wherein if a node receives a message with the query flag set when in ACTIVE stage, said node modifies said node's tables and sends back an empty message with no updates and with the reply flag set.

Patent Citations (1)

Patent	Date	Inventor	Cited By
US5850537(A)	1998-12-01	Selvidge et al.	Examiner

Non-Patent Literature (16)

Dijkstra, Edsger W., Scholten, C.S.; Termination Detection for Diffusing Compuations, Information Processing Letters, vol. 11, No. 1, pp. 1 thru 4, Aug. 29, 1980.Applicant
Farinachi, D.; Introduction to Enhanced IGRP (EIGRP), Cisco Systems, Inc., pp. 1 thru 5, http://www.cisco.com/warp/public/103/1.html, Jul. 1993 (Sep. 21, 2001).Applicant
Garcia-Luna-Aceves, J.J.; “Loop-Free Routing Using Diffusing Computations,” IEEE/ACM Transactions on Networking, vol. 1, No. 1, pp. 130-141, Feb. 1993.Applicant
Garcia-Luna-Aceves, J.J., Behrens, J.; “Distributed, Scalable Routing Based on Vectors of Link States,” IEEE Journal on Selectred Areas in Communications, pp. 1-13, Oct. 1995.Applicant
Garcia-Luna-Aceves, J.J., Murthy, S.; “A Path-Finding Algorithm for Loop-Free Routing,” IEEE/ACM Transactions Networking, pp. 1-22, Feb. 1997.Applicant
Garcia-Luna-Aceves, J.J., Spohn, M.; “Scalable Link-State Internet Routing,” Proceedings International Conference on Network Protocols, pp. 1-10, Oct. 1998.Applicant
Hedrick, C.; Routing Information Protocol, Network Working Group, Request for Comments 1058, pp. 1-4, Jun. 1988.Applicant
Humblet, Pierre A., “Another Adaptive Distributed Shortest Path Algorithm,” IEEE Transactions on Communications, vol. 39, No. 6, pp. 995-1003, Jun. 1991.Applicant
Jaffe, Jeffrey M., Moss, Franklin H.; “A Responsive Distributed Routing Algorithm for Computer Networks,” IEEE Transactions on Communication, vol. COM-30, No. 7, pp. 1758-1762, Jul. 1982.Applicant
Merlin, Philip M., Segall, Adrian; “A Failsafe Distributed Routing Protocol,” IEEE Transactions on Communications, vol. COM-27, No. 9, pp. 1280-1287, Sep. 1979.Applicant
Moy, J.; “OSPF Version 2,” Network Working Group, Request for Comments: 2178, obsoletes RFC: 1583, pp. 1-5, 209-211, Jul. 1997.Applicant
Rajagopalan, Balasubramanian and Faiman, Michael; “A New Responsive Distributed Shortest-Path Routing Algorithm,” Reference pages pp. ii and 9, from Internetworking: Research and Experience, vol. 2, pp. 51-69, Mar. 1991.Applicant
Segall, Adrian: “Optimal Distributed Routing for Virtual Line-Switched Data Networks,” IEEE Transactions on Communications, vol. COM-27, No. 1, pp. 201-208, Jan. 1979.Applicant
Spinelli, John M. and Gallager, Robert G.; “Event Driven Topology Broadcast Without Sequence Numbers,” IEEE Transactions on Communications, vol. 27, No. 5, pp. 468-474, May 1989.Applicant
Vutukury, Srinivas, Garcia-Luna-Aceves, J.J.; “A Simple Approximation to Minimum-Delay Routing,” Proceedings of ACM SIGCOMM, pp. 1-12, (1999).Applicant
Zaumen, William T. and Garcia-Luna-Aceves, J.J.; “Loop-Free Multipath Routing Using Generalized Diffusing Computations,” Proceedings IEEE INFOCOM, pp. 1-10, Mar. 1998.Applicant

Abstract