Hop-by-hop routing with node-dependent topology information

[0002] This application claims the benefit of U.S. Provisional Application No. 60/091,109 filed Jun. 29, 1998, entitled “A Method of Hop-By-Hop Routing In Multiprotocol Networks With Overlaid Routing Domains,” which is incorporated herein by reference.

[0003] This invention relates to communication networks, and more particularly, to hop-by-hop routing in which different network nodes have different views of the network topology.

[0004] Networks are the principal means of exchanging or transferring information, which may be in the form of data, voice, text, video and the like, among different communication devices connected to the network(s), including I/O devices such as computer terminals, multimedia workstations, fax machines, printers, servers, telephones, videophones, and the like. A network typically comprises switching nodes connected to each other and to communication devices by communication links. Each link is characterized by link capacity, available bandwidth, link propagation delay, processing delay at the associated node, delay variation, and loss probability, among other things. Such characteristics are referred to as “metrics,” with some remaining constant, and others varying over time. Information input from the communication devices to the network may be in any form, but is often formatted into packets of either fixed or variable length. When information is to be exchanged between two communication devices, a path is established within the network connecting the nodes (called a source node and destination node) with which those devices are associated.

[0005] In many networks, a given communications stream between a specified source and destination is carried over a set of physical paths (i.e., paths comprising the source and destination nodes, and possibly one or more intermediate nodes, and communication links connecting the included nodes) within the network. An important element of network design is the process of selecting a set of physical paths for routing information through the network. This process may take into account various factors, such as network topology, currently available network resources, and quality of service (QoS) commitments made to network users, e.g., guaranteed bandwidth or maximum packet delay, among others. To support path selection, different network nodes maintain information about the network, including node adjacency and link incidence, reachability of different nodes, as well as various other link metrics. This information is stored in a so-called “topology database” of the node and constitutes the node's view of the network.

[0006] The routing of information packets from a source node to any other node in the network or a segment of the network, in which all nodes have the same view of the network topology is well established. Two existing routing paradigms in such networks are source routing and hop-by-hop routing. In source routing, the entire route taken by a packet from source to destination may be pre-computed and placed on the packet. As the packet is passed from the first node to a second node, the second node strips its address from the pre-specified route and passes the packet to the next node indicated in the packet header. In the alternative routing technique of hop-by-hop routing, no pre-computed route is employed. Each packet contains only the destination address. Upon receiving a packet, each intermediate node refers to its routing table, computed on the basis of its topology database, to forward the packet along the next hop towards the destination node.

[0007] Well-known methods, such as Dijkstra's shortest path algorithm, have been developed, which given the single static view of the network, determine under fairly general conditions the shortest routing path between any two network nodes. However, if different network nodes have different views of the network topology, such algorithms cannot guarantee loop-free and effective routing.

[0008] Recently, the focus in network routing has shifted, however, toward dynamic or state-adaptive routing. Beside reducing configuration work, such routing adapts quickly to changes in the available resources of the network and link failures. Several design solutions exist for dynamic routing in computer networks and are still under development, with distance vector and link-state protocol approaches being the ones well-known.

[0009] The basic idea of link state routing protocols is that each node sends local network topology information to its neighbors. This information is then propagated through the network using sophisticated “flooding” mechanisms. As the result, every node accumulates the view of the entire network in its topology database. The generation and flooding of information is repeated each time a node sees a significant change in available local resources. The distributed pieces of topology information, link state up-dates (LSU) or link state elements (LSE), carry a unique identifier and a version number increasing when the information inside of such an LSU is changing. Additionally, to prevent this process from being triggered too often, a dampening function controls the thresholds holding back non-significant changes. The topology database resulting from the execution of this latter “flooding” mechanism between nodes is used to compute routes to the desired destinations. Such routes are used, for example, in hop-by-hop forwarding of packets. The distance vector approach is based on a significantly different idea. Each node continuously diffuses information about the distances to different network sites reachable via that node. At the same time, it uses data received from other nodes and metrics of its own links to recompute the set of best routes, thus updating the distance information it distributes.

[0010] Despite the simplicity of the latter protocols, they are plagued by problems, such as long convergence times, forming of loops and lack of scalability in terms of topology sizes supported. Research is being performed to alleviate some of the problems. It should be noted that these link-state protocols also suffer from excessive amount of information being flooded in larger topologies. Therefore, newer link-state routing protocols incorporate a concept of “hierarchy,” where a part of the network running a link-state protocol collapses into a logical node in the view of distant nodes, and between such logical nodes, sometimes called areas, where some form of distance vector protocol is being executed.

[0011] Modern routing protocols, such as PNNI, are following the trend toward extensibility for future requirements, which abandon fixed packet formats and use TLV (type, length, value)—encoded packet schemes. The “type” describes the fixed part of the TLV transmitted and the “length” indicates the offset in the packet where the next TLV starts. In cases where the length exceeds the length of the fixed part of the TLV, embedded TLVs are present. Generally, TLV encoded packets transferring topology information in modern routing protocols can be interpreted as representations of lists of arbitrary elements embedded themselves in a recursive fashion into lists at a higher level.

[0012] An additional property of many of the prior art routing protocols is their ability to flood information elements even if they are opaque to the receiver since their type is not known. This allows newer protocol versions to be introduced as well as experimental features in an existing network to be deployed without the necessity of bringing all the nodes synchronously to the same release. To operate properly, guaranteeing packet delivery to the destination without creating loops, the link-state and distance vector protocols require that the topology databases of different network nodes converge to the same view of the network. In the networks deployed so far, however, different versions of link-state protocols cannot interoperate when new metrics or novel link properties are introduced, unless a translation between them is performed. Furthermore, network topologies are traditionally partitioned into disjoint domains corresponding to different routing protocols due to the possibility of loop creation.

[0013] The present invention presents a method to effect hop-by-hop routing in a network segment where different nodes have different views of the network topology. In particular, the methods of this invention are applicable when each node in a network or network segment may be aware of only a subset of the communication links in the network, without perceiving other communication links. Based on each node's individual view of the network, the method introduces the concept of a visibility set that includes all visible communication links. A network segment may contain an ordered hierarchy of such visibility sets and each visibility set may contain a subset of all communication links in the network segment.

[0014] In general, an efficient algorithm is disclosed for searching for a family of one-to-all optimal feasible paths in a communication network where different nodes may have different views of the network topology. Generally, the invention comprises the following steps:

[0015] (a) restricting the set of available paths to a destination node to the set of feasible paths from the source node to the destination node; and

[0016] (b) choosing as the optimal route the feasible path which has the lowest cost, wherein a path is a feasible path if (i) the path does not contain a cycle, and (ii) for each intermediate node visited by the path, the subpath from that intermediate node to the destination node is visible from the intermediate node.

[0017] The invention ensures that forwarding a packet along an optimal feasible path guarantees its eventual delivery to the destination node without being dropped or being routed to the same node twice. The present method provides for the execution of multiple dynamic routing protocols, possibly overlaying each other in the same address space, within a network with common kinds of metrics of arbitrary complexity. It also solves the problem of interoperability when new metrics or novel link properties are being introduced and eliminates the necessity to run different protocols and protocol versions within disjoint routing domains.

[0018] The features and advantages of the present invention will become more readily apparent from the following detailed description of the invention in which:

[0019] FIG. 1 illustrates routing with incomplete information; (a) shows a hypothetical sample graph, and (b)-(e) show visibility sets shared by the corresponding shaded vertices;

[0020] FIG. 2 illustrates how routing along a non-optimal feasible path may create a cycle;

[0021] FIG. 3 illustrates embedded visibility sets; (a) shows a sample graph with three classes of vertices distinguished by the density of shading, and (b)-(d) shows the visibility sets for each class and formal definitions;

[0022] FIGS. 4(a)-(c) illustrate the topologies induced by the three visibility sets (a) ₁; (b) ₂and (c) ₃, respectively;

[0023] FIG. 5 illustrates a graph for demonstrating the probabilistic advantage of forwarding a packet to a knowledgeable neighbor when no feasible path exists;

[0024] FIG. 6 is a flowchart of the feasible path algorithm employed in the present invention;

[0025] FIG. 7 is a flowchart of a so-called “modified Dijkstra algorithm” of FIG. 6; and

[0026] FIG. 8 shows the operation of the feasible path algorithm on the sample graph of FIG. 4, with capital letters denoting the identification of the vertex, italicized numbers denoting edge weights, and bold numbers denoting tentative distances from the source A.

[0027] The following detailed description of the inventive method is divided into the following sections. Section I, after introducing the basic definitions and describing the network communication model, formalizes the problem of routing in overlaid domains by considering the perceived cost of paths and nodes' visibility sets. Section I then defines the notion of a feasible path and proceeds by defining the routing policy rules which are necessary and sufficient for successful routing under general visibility conditions, as well as formulating the criterion of path feasibility in the particularly important case of embedded visibility sets. Section II specifies the algorithm searching for optimal feasible paths and proves its correctness. Several applications of immediate practical importance are considered in Section III, followed by the discussion of longer term perspectives in Section IV.

[0028] Let a computer communication network be modeled by a directed graph G=(V, E), where the vertices in set V represent the switching/routing nodes and the edges in E correspond to unidirectional communication links. Each edge e of the graph is assigned a unique weight w(e) from a cost class W representing some link configuration or state parameter, relevant to routing. In such a setting, the “length” of a link is most often not its true geometrical length, but can be a value representing any characteristic of that link. “Weight” will be used as the general term for such values, with the cost given by the sum of the weights, as set forth more fully herein below.

[0029] Although in many cases it is sufficient to think of the weight as a non-negative integer, we allow it to have a more complex structure. A cost class W could be any set which contains the elements, zero 0 and infinity ∞; is closed under a properly defined summation operation; and can be totally ordered with some “not worse than” relation. We refer to such set as an “abstract cost class.” To avoid confusion, the summation operation on the elements of W, which is referred to as formal addition, is denoted ⊕, whereas the notation ≦ is used for the ordering relation. As an example of a non-integer cost class, consider a system in which the available bandwidth is the primary routing criterion, while the number of hops is used as a tiebreaker. The corresponding cost class is a set of pairs (B, H), where B is real and H is an integer. The zero and infinity elements are represented by (∞,0) and (0,∞), respectively, and the definitions of formal addition and comparison are:

[0030] (b₁,h₁)⊕(b₂,h₂)=(min{b₁,b₂},h₁+h₂),

[0031] (b₁,h₁)≦(b₂,h₂)⇄(b₁>b₂) or (b₁=b₂and h₁≦h₂)

[0032] To ensure generality, we assume that relation established by E is reflexive, i.e., every node has a link to itself. Assume further that for any link e=(u,v)∈E, its weight w (e) is non-zero, if and only if vertices u and v are distinct.

[0033] A directed path π on graph G=(V, E) can be equivalently defined by a sequence of incident edges or by a sequence of adjacent vertices. A path is simple if it does not contain a cycle. A path containing no edges is called “degenerate” and is denoted φ.

[0034] Let π=(v₁,v₂, . . . ,v_n). Any path π_ij=(v_i,v_i−1, . . . ,v_j), such that 1≦i≦j≦n, is a “subpath” of π. In this case, π is an “extension” of π_ij. If π′=(v_n,u₁,u₂, . . . ,u_m), then ρ=(v₁,v₂, . . . ,v_n,u₁,u₂, . . . u_m) is a “concatenation” of π and π′.

[0035] Every subset of edges F⊂E defines a “partial graph” G_F=(V,F). Let F′ be a reflexive closure of F. We will refer to the set of all directed paths in G′_F=(V,F′) as a “topology” induced by F. Edge subset F is a “base set” of topology . A non-degenerate path belongs to topology , if and only if all its edges are elements of the base set F. For any two vertices s and d in V, vertex d is “accessible” in F from s, if topology induced by F contains a path π=π(s,d) from s to d.

[0036] We are interested in modeling the situation when different nodes see the network differently. In particular, “a view” of some vertex v∈V can be completely specified by the set of “perceived weights” {w_v(e)|e∈E} of all the edges. While perceived weights of the same edge may vary from vertex to vertex, the invariant value of w(e) will be referred to as the “proper weight” of an edge.

[0037] Definition 1 (Absolute cost) The absolute cost C(π) of a non-degenerate path π, such that π=(u₁,u₂, . . . ,u_n), is a formal sum of the proper weights of all its edges: $\begin{array}{cc}C\left(\pi \right)=\underset{1\le i\le n}{\oplus }w\left(u_i,u_{i+1}\right)& \left(1\right)\end{array}$

[0038] The absolute cost of a degenerate path is zero: C(φ)=0.

[0039] If in Eq. (1), the proper weights w are substituted by the perceived weights w_v, we obtain the definition of the “perceived cost” C_v(π) of the path. It follows immediately from these definitions that the cost of a concatenation of two paths is equal to a formal sum of the costs of these paths, and the cost of any subpath is not worse than the cost of the path itself. We restrict our attention to the case when each vertex either sees an edge with its proper weight or doesn't see it at all.

[0040] Definition 2 (Visibility set) For every v∈V, there exists a subset F_v⊂E, such that: $\begin{array}{cc}{w}_v\left(e\right)=\{\begin{array}{cc}w\left(e\right),& \mathrm{if}e\in F_v\\ \infty ,& \mathrm{otherwise}\end{array}& \left(2\right)\end{array}$

[0041] The subset F_v⊂E is called the visibility set of v.

[0042] Without any loss of generality, we assume that all outgoing edges of vertex v belong to F_v. We say that a path π “is visible from” v, if π belongs to the topology induced by the visibility set of v. The following fact, which characterizes our approach to visibility, follows immediately from the definitions of perceived cost and visibility set.

[0043] Theorem 1 The perceived cost of any given path is the same for all nodes for which the entire path is visible.

[0044] In the following presentation, C(π) denotes the absolute cost of path π invariant in the view of all nodes for which entire π is visible.

[0045] Definition 3 (Path optimality) Let (s,d) be a set of paths from s to d. Path π* is an optimal path in (s,d), if it is not worse than any other path in (s,d):

[0046] ∀π∈ (s,d): C(π*)≦C(π)  (3)

[0047] Clearly, the optimal path in any given set may not be unique.

[0048] Depending on the choice of set , different types of optimal paths can be obtained. If (s,d) is a subset of the topology induced by the edge set E, restricted to the paths from a given source s to a given destination d, then path π*(s,d) in Definition (3) is “absolutely optimal.” If is a similarly restricted subset of _v, a topology induced by the v's visibility set, then π* is an “optimal visible path.”

[0049] In a traditional setting, when the visibility sets of all nodes in the network (or part of the network) executing some link-state routing protocol are assumed to be identical, the routing process amounts to finding the optimal (shortest) path to the desired destinations in the entire network or subnetwork. Well-known methods, such as Dijkstra's shortest path algorithm, have been developed which allow to solve this problem efficiently under fairly general conditions. However, if the visibility set invariance assumption is relaxed, these algorithms can no longer guarantee loop-free and effective routing.

[0050] When a node makes a routing decision, it naturally considers only the paths that are visible from it. The best path among those, i.e., the optimal visible path, may differ from the absolutely optimal path if the latter is not visible from the node. Furthermore, forwarding a packet to the next node along the optimal visible path can guarantee neither that the packet will actually follow this path, nor even that the packet will eventually reach its destination.

[0051] The obvious reason is that, in general, the visibility set of any node receiving the packet “along the path” is different from that of the source. Therefore, this node may see a worse (or better) path to the destination or may not see a path at all. Consequently, it may deflect the packet from the path selected by the source or simply drop it. As an example, consider the routing of a packet from source node A to destination node G in a computer communication network represented by the graph of FIG. 1(a), with the visibility sets shared by the corresponding shaded vertices depicted in (b)-(e). The absolutely optimal path from A to G is (ADG) having cost 2. But since link (DG) does not belong to the A's visibility set, the path itself is not visible from A and, therefore, is not available for routing. Among the two visible paths, (ABEG) and (ACFG), path (ACFG) is clearly optimal having cost 12, as opposed to cost 24 of path (ABEG). However, if the packet is forwarded along the optimal visible path, then C, who does not see any path to the destination at all, may simply discard the packet. Assume that A forwards the packet along the non-optimal visible path (ABEG). Node E, which receives the packet after two forwarding operations, does not know anything about its previous history, and searches for the path to the destination within its own visibility set. Again, if E selects the optimal visible path (EADG), then the packet is routed back to the source thus creating a loop. On the other hand, the selection of a non-optimal path (EDG) succeeds; node D receives the packet and forwards it to the destination via link (DG) which belongs to visibility sets of both E and D.

[0052] Our objective is to establish a routing policy, i.e., a set of rules each node has to comply in order to perform routing successfully in the network where distinct nodes may have different visibility sets.

[0053] In accordance with the principles of the invention, the first rule of the routing policy (RP1) is postulated:

[0054] (RP1) If the destination is not accessible in the visibility set of a given node, this node may drop the packet.

[0055] The decision to route a packet is “successful,” if the packet is eventually delivered to the destination without being dropped or routed to the same node twice. The routing decision made by some node is “guaranteed,” if this node is able to prove the decision to be successful, based on its limited information about the network, under the assumption that all the nodes follow the same routing policy rules. Rule (RP1) implies that for a routing decision to be guaranteed, it is necessary to ensure that the destination is accessible, in the respective visibility set, from any other node that may receive the packet.

[0056] Definition 4 (Feasible path) A path from source to destination is feasible at the source, if:

[0057] (a) the path is simple, and

[0058] (b) for every node visited by the path, the subpath from that node to the destination is visible from that node.

[0059] Corollary 1 Any subpath of a feasible path is itself a feasible path.

[0060] Corollary 2 If path π=π (u,d) is feasible at u, and there exist a node s with an outgoing edge e=(s,u), such that π is visible from s, then an extension path π′=(s,u,d) is feasible at s.

[0061] Referring again to the sample graph of FIG. 1, observe that path (ABEG) is the only feasible path at source A, and paths (EDG) and (EG) are both feasible at E, among those (EDG) being optimal.

[0062] As the main result of this section, we formulate the second rule of the routing policy (RP2) and prove the following theorem about it.

[0063] (RP2) If there exists a feasible path from a given node to the destination, this node should forward the packet along a path which is optimal among all such feasible paths; otherwise the node should drop the packet.

[0064] Theorem 2 In a general network of nodes adherent to (RP1), for any routing decision to be guaranteed, it is necessary and sufficient that every node also complies with (RP2).

[0065] Proof. Necessity. We begin with showing that, if rule (RP2) is violated by some node, then it is not possible to prove the success of a routing decision. Let there exist a node, referred hereto as the source, that does not comply with (RP2). Without any loss of generality, assume that the destination is accessible in the source's visibility set. (If it was not the case, no routing decision could be possibly guaranteed, as the source could expect any node, to which the packet is forwarded, to drop it.)

[0066] If the source forwards the packet along a non-feasible path π, whether or not a feasible path exists, then, by the definition of feasibility, there exists a node u visited by π, such that the subpath π_u, from u to the destination is not visible from u. Therefore, the destination is not necessarily accessible from node u in its visibility set and this node could drop the packet according to (RP1).

[0067] Now consider the case where two feasible paths to the destination, π(s,d) and ρ(s,d), are visible from s. Let these paths differ in the first edge and let C(ρ)≦C(π), C(ρ)≠C(π). Assume the source forwards the packet along the non-optimal path π(s,d) as depicted in FIG. 2. There could exist a node u visited by path π with an outgoing edge e=(u,s), such that path ρ(s,d) is visible from u and w(e)⊕C(ρ)≦C(π_u(u,d)). Then by Corollary (2), the extended path ρ′=(u,s,d) is feasible at u, and C(ρ′)≦C(π_u(u,d)), so that node u, compliant with (RP2), would forward the packet back to s thus creating a loop.

[0068] Sufficiency. Let “source” be any node whose routing decision is assigned the first sequence number and prove the following statement by induction on the number of forwarding operations:

[0069] Lemma A node receiving the packet after n forwarding operations sees at least one feasible path to the destination and chooses such feasible path, that its cost is not worse than the cost of the original path chosen by the source.

[0070] Let π_n* be the path chosen by the node u_n, which receives the packet after n forwarding operations. For n=0, node u₀is in fact source s itself, and the statement trivially holds. Assume π_k* is feasible at u_kand C(π_k*)≦C(π₀*). The packet is forwarded by u_kto node u_k−1, which by definition of feasibility, sees the subpath of π_k* from itself to destination. This subpath is feasible at u_k+1, by Corollary (1). Since π_k+1which is chosen by u_k+1according to (RP2), is an optimal feasible path, it is not worse than the subpath of π_k* and, therefore, not worse than π_k* itself. Then by transitivity, C(π_k+1*)≦C(π₀*), which completes the proof of the inductive step.

[0071] According to the Lemma, node u_n, which receives the packet after n forwarding operations, sees at least one feasible path to destination. Since, by the premise of the Theorem, u_nis compliant to (RP2), it does not drop the packet, but forwards it along one of the available feasible paths. As the packet forwarding sequence can be restarted at any node, it is enough to show that the actual path taken by the packet does not contain a cycle at the source. To the contrary, assume that after n forwarding decisions, the packet is routed back to the source: u_n=u₀=s. Accounting for the cost of the cycle, we obtain: $C\left({\pi }_0^{*}\right)=C\left({\pi }_n^{*}\right)=C\left({\pi }_0^{*}\right)\oplus \left(\underset{0\le i<n-1}{\oplus }w\left(u_i,u_{i+1}\right)\right)$

[0072] which necessarily implies that, for all i, w(u_i,u_i+1)≡0. This is a contradiction with the definition of edge weights. Therefore, if all nodes comply with (RP2) as well as (RP1), no loop could be possibly created. It follows that under these rules, no edge is crossed more than once and, since the number of edges in the graph is finite, the packet eventually reaches destination.

[0073] Observe that the cost of the “actual route” taken by the packet, which is forwarded in compliance with the routing policy rules (RP1) and (RP2), lies between the costs of an absolutely optimal path and an optimal feasible path found at the source.

[0074] We now specialize for the case of “embedded” visibility sets. Let vertex set V be partitioned into K disjoint subsets V₁, V₂, . . . , V_K. Each of the subsets V_iis associated with a visibility set F_i⊂E such that all nodes in V_ishare the same view of the graph. Furthermore, let the visibility sets be hierarchically related:

[0075] E=F₁⊃F₂⊃ . . . F_K−1⊃F_k  (4)

[0076] As an example, consider the graph of FIG. 3. The visibility sets of each of the three node classes are determined by the value of the edge weights: if some weight exceeds a class-specific threshold, the corresponding edge is not visible from the nodes of the class.

[0077] For convenience of presentation, let Γ(e) and Δ(e) denote the initial vertex and the terminal vertex of a directed edge e, respectively, and define the following operators:

[0078] Class (.) applies to a node and returns the index r of the subset V_rto which the given node belongs;

[0079] View(.) applies to a node and returns the visibility set of the node: View(u)=F_Class(u);

[0080] Vis (.) applies to an edge and returns the “visibility index” of the edge, i.e., the largest index of a visibility set in hierarchy Eq. (4) which includes the given edge:

[0081] (Vis(e)=r)⇄(e∈F_rand (e∉F_r−1or r=K))

[0082] For each vertex subset V_i, 1≦i≦K and the visibility set F_i, we define a corresponding topology _i. The base set T_iof topology _iconsists of all such edges in F_i, whose initial vertex has a visibility set which includes F_i:

[0083] T_i≡{e∈F_i|F_i⊂View (Γ(e))}  (5)

[0084] Observe that for i=K, the base set of the topology coincides with the corresponding visibility set: T_K=F_K. For the sample graph presented above, the topologies induced by the visibility sets are shown in FIGS. 4: (a) ₁; (b) ₂; (c) ₃; and (d) ₄.

[0085] The following Theorem establishes the necessary and sufficient condition for a path to be feasible in the case of embedded visibility sets.

[0086] Theorem 3 (1) If source vertex u belongs to vertex subset V_r⊂V, which has visibility set F_rsatisfying hierarchy Eq. 4, and v∈V is some destination vertex, then all feasible paths from u to v can be represented as a concatenation:

[0087] π(u,v)=(t_z*t_z+1* . . . t_K*)  (6)

[0088] where t_i* is a (possibly degenerate) subpath in topology _iwith the base set T_iconstructed according to eq. (5), and z is the smallest visibility index among all edges in π(u,v):

[0089] r≦z=min_e∈π(u,v)Vis(e)

[0090] (2) All simple paths of the form Eq. (6) are feasible at u.

[0091] Proof. (1) Use induction on the number n of edges in the path. First, let n=1. Consider a path containing single edge e=(u,v). This path is feasible by the premise of the Theorem. Therefore, e∈View (u) which implies that View (u)⊃F_Vis(e), as the opposite statement, e∈View (u)⊂F_Vis(e), contradicts the definition of the visibility index. It follows that e∈T_Vis(e), and the basis of induction is established.

[0092] Let the statement hold for a path π_n=(u₁,v₁,v₂, . . . v_n) containing n edges:

[0093] π_n=(t_z*t_z+1* . . . t_K*)

[0094] where z≧r is the smallest visibility index achieved by some edge e in π_n, and consider a feasible extension π_n+1=(s,u,v₁,v₂, . . . v_n). By feasibility of π_n+1, e∈View(s) and View(s)⊃F_Vis(e)=F_z. Two cases are possible.

[0095] Case (a): Vis(s,u)≧Z. Then (s,u)∈F_zbelongs to the base set T_z, so the subpath ^t_z* can be extended to include link (s,u). The representation of eq. (6) holds for π_n+1with z unchanged.

[0096] Case (b): Vis(s,u)<z. Then by feasibility of π_n+1, (s,u)∈View(s) and View(s)⊃F_Vis(s,u). Therefore, (s,u)∈T_Vis(s,u). Concatenate representation for π_n, to subpath t_Vis(s,u)*=(s,u), complemented by (z−Vis(s,u)−1) degenerate subpaths. The result

[0097] π_n+1=(t_Vis(s,u)*φ_Vis(s,u)+1. . . φ_z−1t_z*t_z+1* . . . t_K*)

[0098] is of the form Eq. (6) with Vis(s,u) being the smallest visibility index among the edges of π_n+1. The proof of the inductive step is completed.

[0099] (2) Let π(u, v) be a simple path which can be represented in the form of (6). Choose arbitrary edge e in π and find index of its subpath in this representation; let it be i. By construction of topology _i,

[0100] View (Γ(e))⊃F_i

[0101] Consider subpath ρ=ρ(Γ(e),v)of π(u,v) from the initial node of e to destination v. By assumption, every edge d in ρ belongs to the base set T_jof some topology _j, where i≦j≦K. By construction, Eq. (5), it necessarily belongs to the corresponding visibility set F_j. Combining hierarchy eq.(4) with the results above, for any edge d of ρ, we obtain:

[0102] d∈F_jF_i⊂View (Γ(e))

[0103] Thus, for any vertex Γ(e) visited by path π(u,v), the subpath ρ=ρ(Γ(e), v) is visible from Γ(e). Path π(u,v) is feasible at u.

[0104] It follows from the Theorem 3 that in order to guarantee successful delivery in a general case, a node should drop the packet if no feasible path to destination exists. Note that, however, an attempt can be made to improve the probabilistic chances of the packet to be delivered to requested destination in the absence of feasible path while preserving the static no-loop guarantee. The sufficient condition of the packet discard could be relaxed as follows:

[0105] (RP2)′ A node should forward the packet along the path which is optimal among the feasible paths from that node to the destination, if such path exists. The node should drop the packet if and only if there exist no feasible path to the destination, and for all its outgoing edges, the terminal vertex of the edge belongs to the same or lower class of hierarchy (4) than the node itself. When no feasible path exists, but there is an outgoing edge, such that its terminal vertex belongs to the higher class of hierarchy, the node should forward the packet along such edge.

[0106] In a network of well-behaved nodes compliant with (RP2)′, the packet may not be forwarded back to the source neither as it passes up in the hierarchy, nor as it follows the feasible path discovered by some other node in the network; the latter case would imply existence of a feasible path from the source to destination. The loop-free property follows. The probabilistic advantage of rule (RP2)′ can be demonstrated using the graph on FIG. 5. Node S does not see a feasible path to destination, because link (BC) is outside its visibility set, whereas its more knowledgeable neighbor A does see a feasible path and may forward the packet successfully.

[0107] However, in a well-behaved static network, a node should not have received a packet destined to an unreachable node, at the first place, and therefore not included with the proposed algorithm below, but not excluded from the principles of the invention.

[0108] Referring to FIG. 6, discussed herein below is an algorithm applied to the case of embedded visibility sets of Eq. (4). It can be used to detect the existence of a feasible path from source s∈V_rto any destination d∈V and, if such path exists, to compute the next hop of an optimal feasible path in accordance with principles of the invention.

[0109] The information about the network available to each node includes the membership of this node in the specific disjoint subset of nodes, the weights of the edges in its own visibility set along with the edge membership in the visibility sets of the lower hierarchical levels. Given this incomplete information, at step 600, the source node first initializes the distance vector to infinity and then iteratively runs a variation of a shortest path algorithm or modified Dijkstra algorithm at step 610 on the gradually expanding partial graph. A flowchart for the modified Dijkstra algorithm of the present invention is set forth in FIG. 7.

[0110] In the specification of the proposed algorithm, we make use of the following notation:

[0111] r is the index of the vertex set partition to which the source (i.e., node running the algorithm) belongs;

[0112] k is the total number of partitions of the vertex set;

[0113] {V_i, i=1 . . . k} is a collection of vertex set partitions;

[0114] {F_i, i=r . . . k} is a collection of visibility sets of partitions on the same or lower hierarchical levels than that of the source;

[0115] {w(e),e∈F_r} is the set of perceived weights of edges in the visibility set of the source;

[0116] dist[1:N] is a vector of tentative distances to all nodes in the network, i.e., the costs of the best feasible paths from the source to the respective vertex v∈V found so far;

[0117] next_hop[1:N] is a vector of initial edges of the feasible paths leading to respective nodes in the network;

[0118] candidates and next_candidates are the ordered sets of vertices; sorting is performed in increasing order of the tentative cost of the feasible paths from the source to the respective vertex, in respect to relation ≦. Three operations on the ordered sets are available in the shortest path algorithm for the modified Dijkstra algorithm of FIG. 7:

[0119] 1. insert(set, v): insert node v into a proper position in set, in the increasing order of the dist vector;

[0120] 2. update(set,v): change position of node v in set using the modified value of dist[v], so that the increasing order of dist is maintained;

[0121] 3. remove(set): remove and return the first element of set.

[0122] Each node in the network maintains two vectors: vector dist [1:N] of distances to all other nodes in the network computed along the corresponding optimal feasible path, and vector next_hop[1:N] of initial links of those paths. When a packet destined to v is received at some node, it checks if the locally maintained value of dist[v] is finite. If it is the case, this node forwards the packet along the link specified by next_hop[v]. Otherwise, it drops the packet reporting the destination as unreachable. Alternatively, the implementation may attempt to improve the probabilistic chances of the packet to be delivered to the requested destination, while preserving the no-loop guarantee, by forwarding it to an adjacent node belonging to a higher class of hierarchy and having larger visibility set. However, in a well-behaved network when a routing protocol has converged to a stable state, a node should not have received a packet destined to an unreachable destination in the first place. Therefore, we do not consider this possibility further. To maintain dist [1:N] and next_hop [1:N] current, each node recomputes them either periodically or each time a significant change in link state parameters is detected.

[0123] Initially, in step 600 of FIG. 6 the source s sets to infinity all entries of the distance vector except its own, which is set to zero. Next, a set of communication links visible from the source node is chosen in step 710. For any edge (i.e., communication link) in this visibility set (step 730), the entry corresponding to the source node in the distance vector is computed or updated, if necessary, as shown in steps 740 and 760. Next, the node entry in the next hop vector corresponding to the source node is computed, as shown in step 750. These steps are repeated until all the edges in the visibility set being considered are exhausted. Next, a new visibility set is considered in step 710 and the entries in the distance and next hop vectors are again updated for all nodes in this visibility set. This is repeated until all visibility sets are considered, as in steps 770, 780. This completes execution of the modified Dijkstra shortest path algorithm for the network.

[0124] Listed hereto as an appendix is the pseudo-code for the procedure feasible_path ( ) of FIG. 6, which is used to update the local data structures for the proposed routing method of the present invention.

[0125] The operation of the algorithm on our sample graph of FIG. 3 is illustrated on FIG. 8. At the initialization stage (FIG. 8(a)), the source A sets to infinity all entries of the distance vector (except its own, which is initialized to zero), and keeps the entries of the next-hop vector undefined. At Step 1 (FIG. 8(b)), the shortest path algorithm is executed on the topology _iassociated with the visibility set of the source. As a result, the vertices accessible from the source in this topology, namely, B,C,D,E,F, and J, acquire finite distances, and the initial links of their corresponding feasible paths are now defined. Notice that after Step 1, the set of feasible paths forms a tree. It should be emphasized, that this set is shown on FIG. 8(b) for reference purposes only; the actual data maintained by the source can be found in Table I.

[0126] At Step 2 (FIG. 8(c)), the candidates set initially contains those and only those vertices that, have finite tentative distances at the end of Step 1. Removal of vertices from the candidates set occurs in the increasing order of their tentative distances and only those edges are considered by the shortest path algorithm which belong to the base set T₂of topology ₂(see FIG. 8(b)). The first to be removed is vertex A which has no outgoing edges in T₂. It is followed by vertex B, whose tentative distance is 16, which adds links (BC) and (BE), causing a change in the distance vector: dist[C]=28 and dist[E]=22, and redirecting next_hop[C] from link (AC) towards link (AB). Next, vertex is E is removed adding link (EH) which completes a feasible path to vertex H, so that dist [H] becomes 34, etc. Notice that from Step 2 on, the set of feasible paths no longer forms a tree: the tentatively optimal feasible path from source A to vertex F is (ABCF), whereas for vertex J it is (ACFJ).

[0127] At the beginning of Step 3, the candidates set is re-initialized again to contain vertices A, B, C, D, E, F, H, J, and the operation is repeated, but this time only edges in the base set T₃of topology ₃are considered. The distances of vertices F and D are reduced, due to discovery of feasible paths (ABEHF) and (ABEHFD), while vertices G and L are reached for the first time. Vertex K remains unreachable, since it does not have incoming edges in ₃. At this point the algorithm terminates, yielding the costs and identities of initial links of optimal feasible paths to all vertices, except K (FIG. 8(d)). Overall, the maximum number of times each edge is considered equals to the number of topologies this edge belongs to.

[0128] Based upon the teachings of the present invention, those skilled in the art will readily note that the proposed procedure is based on a variation of the well-known Dijkstra's shortest path algorithm applied repeatedly to a partial graph which is expanded according to the established rules set forth above. The correctness properties of Dijkstra's algorithm in the broader context of the different shortest path problems are analyzed in the prior art, as well as the proof of its finiteness and the discussion of its implementation strategies.

[0129] In its original form, Dijkstra's algorithm operates on a graph with non-negative integer edge weights and constructs a shortest path tree by scanning the vertices in the increasing order of their tentative distances from the start vertex. This is performed by labeling the outgoing edges of each scanned vertex, i.e., updating the distances and the tree pointers, if an edge under consideration creates a shorter path to its terminal vertex than all those found before. The variation of Dijkstra's algorithm employed above does not build a tree, maintaining a vector of initial links of the shortest paths instead, requires several iterations, and works with link weights of arbitrary structure. We will refer to this inventive variation as the Generalized Dijkstra's algorithm.

[0130] Let a pass of procedure feasible_path( ) be an iteration of the outermost while-loop.

[0131] Lemma If there exist a path π(s,v) from source s to some vertex v∈V which can be represented in the form of concatenation.

[0132] π(s,v)=(t_r*t_r+1* . . . t_r+n−1)  (7)

[0133] where t_i* is a subpath in topology _i, then after n passes of procedure feasible_path( ), dist[v] is equal to the cost of a path which is optimal among all paths from s to v allowing representation (7), and next_hop[v] points to the initial link of such a path. If no path allowing representation (7) exists, then after n passes dist[v]=∞ whereas next_hop[v] remains undefined.

[0134] Observe that the first pass of the procedure is equivalent to running Generalized Dijkstra's algorithm on topology _r, induced by the visibility set of the source s. Consequently, all optimal paths found by the algorithm belong to _r. By virtue of using a variation of Dijkstra's algorithm, the resulting value of dist[v] is equal to the cost of the shortest (i.e., optimal) path from in s to v in topology _r, if in this topology v is accessible from s, and remains infinite otherwise. In the same time, the resulting value of next_hop[v] points to the initial edge of such path, if one exists, otherwise remaining undefined. This establishes the basis of induction.

[0135] Let dist⁽ⁿ⁾[v] and next_hop⁽ⁿ⁾[v] be the local vector entries, corresponding to node v, after n passes of procedure feasible_path( ). Extend set E by fake edges f_vfrom the source s to each vertex v∈V, whose weights are defined as w(f_v)=dist⁽ⁿ⁾[v]. By assumption, w(f_v) is finite if and only if there exist a path π(s,v) from s to v representable in the form (7) and, furthermore, in that case w(f_v) is equal to the cost of an optimal one among such paths. Consider an augmented graph

[0136] G_n+1=(V,T_r+n∪{f_v=(s,v)})  (8)

[0137] By construction of procedure feasible_path( ) and definition (5), the (n+1)-th pass of the procedure is equivalent to running Generalized Dijkstra's algorithm on the augmented graph (8) initializing it to the state when all fake edges emanating from the source vertex, and only those edges, have already been labeled. If for some vertex v, the original graph G=(V,E) contains a path π(s,v) from s to v of the form

[0138] π(s,v)=(t_r*t_r+1. . . t_r+n−1*)  (9)

[0139] with u being the terminal vertex of subpath

[0140] π(s,v)=(t_r*t_r+1*t_r+n−1)

[0141] then the edge set of the augmented graph (8) contains a fake edge f_u=(s,u), such that w(f_u)≠∞. By definition, it also contains all edges T_r+n. Then, by virtue of running a variation of Dijkstra's algorithm on the augmented graph, dist⁽ⁿ⁺¹⁾[v] is finite and equal to the cost of an optimal path among those which can be represented as a concatenation of some fake edge f_uand a subpath belonging to topology _r+n. Recall that each fake edge in fact corresponds to an optimal path of the form (7). Therefore, dist⁽ⁿ⁻¹⁾[v] is equal to the cost of an optimal path of the form (9). The value of next_hop⁽ⁿ⁺¹⁾[v] in this case either coincides with next_hop⁽ⁿ⁾[u], if s≠u, or points to the initial edge of an optimal path (φ_r. . . φ_r+n−1t_r+n*), otherwise.

[0142] Finally, since all paths considered by Generalized Dijkstra's algorithm running on the augmented graph are concatenations of some fake edge f_uand a subpath in topology _r+n, the finite value of dist⁽ⁿ⁺¹⁾[v] would imply existence of a path represented as (9). If no such path exists, the resulting value of dist⁽ⁿ⁺¹⁾[v] is necessarily infinite with corresponding next_hop⁽ⁿ⁺¹⁾[v] undefined. This concludes the proof of the Lemma.

[0143] Combining the statement of this Lemma with the necessary and sufficient condition of Theorem 3 proves the following

[0144] Theorem 4 (Correctness) When procedure feasible_path( ) executing at node s terminates, dist[v] is equal to the cost of an optimal feasible path from s to v and next_hop[v] points to the initial link of such a path. If no feasible path exists, then upon termination, dist[v]=∞ whereas next_hop[v] remains undefined.

[0145] After completing the discussion of the theoretical background and the algorithmic part, we now focus on the practical applications of the proposed routing method. The examples given below should simplify the understanding of the theoretical discourse and demonstrate how the theory can be applied to the deployment and operation of routing protocols.

[0146] The directed graph model is a traditional abstraction of a communication network. As in most link-state routing protocols, it operates with a notion of an abstract node, attached to other nodes by virtual links. Each bidirectional communication link, as commonly and expectedly encountered in today's networks, is mapped onto a pair of unidirectional edges of the graph with possibly different weights w(e) corresponding to link-state parameters in the respective directions. Although presently the non-negative integer weights are predominant, the advent of QoS routing schemes strongly motivates the protocol generalizations which are capable to operate with link-state parameters of the more complex structure. With this aspect in mind, it is easy to see the equivalence of the shortest path and the optimal path concepts. Traditionally, the shortest paths are computed using a centralized, distributed or replicated version of appropriate algorithms with an underlying topology distribution mechanism, a functional conglomerate known as “routing protocol.”

[0147] The novelty of the proposed approach manifests itself in the fact that we do not assume that the routing protocols are running, “invisible” to each other, on disjoint parts of the network's topology. Neither do we imply that such separation is taking place by abstracting paths computed by an “underlying” routing protocol as virtual topology. Instead, we allow the protocols to overlap or contain each other's topologies. We assume such information to be “hierarchically” visible within multiple protocols or, expressed differently, that the protocols are “integrated.” This concept is formalized with a notion of a visibility set: each node v is able to see only a subset F_vof the communication link set E. Disregarding aggregation issues, a traditional routing protocol assumes that all nodes in the protocol's routing domain share the same visibility set. We show that this is not necessary and hop-by-hop forwarding can be utilized within protocols which abandon this assumption. We do not consider the problem of assuring the specified routing policies (RP1 and RP2) in general, but concentrate on the more practical case of embedded visibility sets. The partition of V into disjoint subsets, V₁, . . . , V_n, can be viewed as partitioning of the network into multiple routing domains, each running a different routing protocol or a different version of the same protocol with its own visibility set. The visibility sets of these domains do not have to be disjoint. On the contrary, it is assumed that they may overlap or be included within each other. The concept of topology _i, as introduced here, defines what can be naturally characterized as a trusted subset of a visibility set, i.e., the topology is built only on those links of the visibility set which are advertised by the nodes having the same or larger view of the network. In other words, while planning a route within the same topology, the source can expect that its original decision won't be changed unless the node, which changes it, has more information about the network than the source itself.

[0148] Assume that every unidirectional communication link in a network is assigned a weight w(e)∈W, and a restricted link weight space W′⊂W is defined. The set E of all links can be partitioned into two disjoint subsets E′ and E″ based on the fact whether or not the value of the corresponding link state parameter belongs to the restricted space W′. Assume further that nodes of two types, referred to as “blue” and “red,” are present in the network imposing a partition of the vertex set V into two disjoint subsets V_Band V_R. The blue nodes observe only those links whose link weights belong to a restricted set W′ and ignore all others (i.e., view them as if their weight was infinite). The red nodes observe all the links in the network with their actual weight.

[0149] We introduce two topologies, blue topology _Band red topology _R, by defining their corresponding base sets T_Band T_Ras follows:

[0150] T_B={e∈E|w(e)∈W′}

[0151] T_R={e∈E|e=(u,v),u∈V_R}

[0152] Note that an edge emanating from a red vertex and thus belonging to the red topology at the same time may or may not belong to the blue topology depending on whether or not its weight comes from a restricted space W′.

[0153] If the method proposed herein is used, then every blue node naturally searches for the best route to a requested destination among the paths which contain only links with the weights in the restricted set W′. On the other hand, every red node considers as possible candidates all paths which can be represented as a concatenation of two subpaths: red and blue.

[0154] Modern routing protocols such as IS-IS, PNNI and BGP are designed in a way that allows newer protocol versions to transparently pass information through older nodes. The particular mechanism employed is the convention that information elements are encoded as TLV (type, length, value)-triplets and all nodes are obliged to pass such elements even with a type unknown to them to their neighbors possibly taking into account the semantics of some globally known flags per TLV as well. A similar mechanism exists in distance- or path-vector protocols such as BGP. These mechanisms allow for upgrades with newer protocol releases without having to force all devices to execute the same version at a given point in time. However, when new metrics or link properties are introduced during a protocol upgrade, they may only translate partially into the old metrics. A method has not been known to operate two such versions of a protocol in an arbitrary, mixed topology and assure loop-free hop-by-hop forwarding in presence of new and old metrics. The described method allows to run both versions and utilize either metric to forward traffic if they are comparable. This holds under the assumption that the visibility set of the newer protocol version embeds the visibility set of the older one, which is natural if backward compatibility is maintained. Additionally, the newer version has to generate both, new and old information elements for the links on which the metric is still within the old range to assure that the old protocol includes new links within its visibility set as long as possible. Even when a link has purely “new” properties that are not visible to the old nodes, they are still obliged to pass the information, therefore allowing two partitions of the network executing the new protocol version to coordinate their visibility sets.

[0155] Today, routing devices within a data communication network rely mostly on a specific interface running a single routing protocol exclusively and to allow for global reachability by exchanging routes across protocols. The present routing method described herein allows to run multiple routing protocols on the same interface as long as their metrics are comparable and forward along the path with a better cost. This makes a magnitude of novel approaches towards network design possible. It is achievable to design a network running two routing protocols overlaid on top of each other, thus taking advantage of their different properties, e.g., one protocol can provide a fast convergence whether the other protocol can compute slowly optimal paths over the same topology. Such a design could increase robustness of the network, since it helps to avoid possible instability conditions and implementation problems within a single protocol, at an expense of additional bandwidth consumption. A precondition is of course that those protocols do not export routing information into each other and the necessary embedding of visibility sets is guaranteed.

[0156] Based on the observation that dynamic routing protocols traditionally restrict possible topological configurations during the deployment of newer versions and their operation in case of intersecting or overlaid domains is not well understood, we introduce a general methodology that formalizes the necessary conditions that have to be met to assure loop-freeness in such scenarios. Additionally, we present a novel algorithm that allows correct hop-by-hop forwarding within a network containing arbitrary mix of nodes running different protocol versions. The same algorithm introduces the possibility to overlap different routing domain as well, still assuring loop-free operation.

[0157] We expect the algorithm to prove useful in deployment of new versions of link-state routing protocols, which are still undergoing rapid changes. Missing capabilities, such as QoS support and ongoing development that necessitates new protocol versions can make use of the algorithm presented. Finally, a largely unexplored area is the possibility to run multiple routing protocols in an overlaid fashion to increase network stability or use different convergence algorithms and convergence properties to open new network design choices.

[0158] Many more variations of the preferred embodiment of the invention are possible without departing from the spirit, the essential criteria and the rules and methods of this invention. The proper scope of this invention is indicated by the appended claims, rather than by the foregoing description and all variations which come within the meaning and range of equivalency of the claims are therefore intended to be covered by the claims stated hereinafter.