Shortest Path Routing Algorithms in Multihop Networks (information science)

Introduction

The topic of shortest path algorithms is very fundamental and important in information science and technology. Shortest path algorithms have evolved over many years and have found applications in different domains such as telecommunication networks, military, and transportation. There has been a lot of work undertaken on this topic in this area in the past. A lot of research is still being conducted. The topic is still poorly understood. This article should be helpful to readers, because it reviews some of the important works conducted in the area, out of the plenty of works available on this topic. The problem is so fundamental that whatever the interest areas of the readers may be, they will find the article useful.

The popular traditional shortest path algorithms date back to 1958/1959 and were proposed by Dijkstra (1959), and Bellman (1958). Their algorithms found wide applications in the abovementioned domains for many years. However, they were static. Thereafter, many other algorithms were proposed in the last few decades, all of which can be classified to be either dynamic or semi-dynamic.

background

Multihop networks, such as the Internet and mobile ad hoc networks (MANETs) contain several routers and mobile hosts. The Internet typically employs routing protocols such as the open shortest path protocol (OSPF) and the intermediate system—intermediate system protocol (IS-IS), and the MANETs employ protocols such as the fisheye state routing (FSR), the optimized link state routing (OLSR), and the ad hoc on-demand distance vector routing (AODV).


In many of these protocols, each router (or a routing device) computes and stores a shortest path tree (SPT) from one router to all other routers and hosts in a routing domain (Moy, 1997; Peterson & Davie, 2000; Schwartz & Stern, 1980). Such networks, which can be modeled as graphs (Misra & Oommen, 2005b; Ramalingam & Reps, 1996), typically contain several routers/switches (nodes) connected by links (edges) with constantly changing costs (weights), link-ups (edge-insertions), and link-downs (edge-deletions).

single-source shortest path routing: dynamic versus static

The problem of computing and maintaining information about the shortest paths information in a graph (with a single source)—where the edges are inserted/deleted and edge-weights constantly increase/decrease—is referred to as the dynamic single source shortest path problem (DSSSP). Although this problem is important, it has received little attention in the literature. The importance of the problem lies in the fact that it is representative of many practical situations in daily life, where most environments are dynamically changing. In such environments, one needs to devise efficient solutions to maintain the shortest path even though there are updates on the structure of the graph by virtue of edge-insertion/deletion, or edge-weight increase/decrease, and hopefully this can be achieved without recomputing everything “from scratch” following each topology update. An example of a single-source shortest path graph, after the insertion of an edge is shown in Figure 1. The new edge C^F appears in the list of shortest paths, and the existing edge B^F, which was earlier in the list of shortest paths, ceases to be so.

Out of the four possible edge operations (insertion/ deletion and increase/decrease), it has been shown that edge-insertion is equivalent to edge-weight decrease, and edge-deletion is equivalent to edge-weight increase. Increasing or decreasing an edge-weight can be performed by inserting a new edge (with the new weight) parallel to the edge under consideration, and then deleting the old edge (Ramalingam & Reps, 1996). If all edge operations are allowed, the problem is referred to as the fully dynamic problem. If only edge-insertion/weight-decrease (or edge-deletion/weight-increase) is allowed, the problem is referred to as the semi-dynamic problem (Frigioni, Marchetti-Spac-camela, & Nanni, 1996).

Typically, with many present-day routing protocols,1 with a unit change in network topology (e.g., link-ups, link-downs, and link-cost changes), each router in the routing domain is intimated of the change. This change typically triggers recomputation of each router’s SPT.

There are well-known static solutions to the traditional combinatorial single source shortest path problem (Bellman, 1958; Dijkstra, 1959) which are unacceptably inefficient in such dynamic practical scenarios because using them would involve recomputing the shortest path tree from scratch each time a topology change occurs in the graph. Static algorithms are unarguably more effective in fixed-infrastructure networks because of their polynomial time complexity. But they are extremely inefficient for time-critical, rapidly changing infrastructures. For instance, if such an algorithm is used in a real-time, large network routing scenario, where there are fast link-state changes, such recomputations will delay the execution of important routing functions considerably.

Two of the earliest known works on the dynamic shortest path problem date back to the papers by Spira and Pan (1975) and McQuillan, Richer, and Rosen (1980). While the former is theoretically proven to be inefficient, the latter has neither been proven theoretically nor through simulations.

The most recent and well-known solutions to the DSSSP problem on general graphs with positive real-valued edge-weights were proposed by Ramalingam and Reps (1996), Franciosa, Frigioni, and Giaccio (1997), and Frigioni, Mar-chetti-Spaccamela, and Nanni (2000). However, the solution by Franciosa et al. (2000) is limited to the semi-dynamic problem only. Although these recent works are theoretical in nature, Ramalingam and Reps (1996)’s and Frigioni et al. (2000)’s results were recently experimentally evaluated through simulations (Demetrescu, Frigioni, Marchetti-Spac-camela, & Nanni, 2001; Frigioni, Ioffreda, & Nanni, 1998). While the former was found to be superior when it concerns running time, the latter was shown to be better suited when the worst-case time was the main concern, or when the number of edges to be updated had to be minimized.

The well-known, fully dynamic algorithms (mentioned previously) are constrained by the following limitations:

1. The existing fully dynamic algorithms process unit changes to topology (i.e., edge-insertion/deletion or weight-increase/decrease) one change at a time, that is, sequentially. When there are several such operations occurring in the environment simultaneously, the algorithms are quite inefficient.

2. In environments where the edge-weights change stochastically and continuously, the existing algorithms (mentioned previously) would fail to converge to the actual underlying “average” solution.

The problems are worse in large topologies which have a large number of nodes and edges, and where a large number of topology changes can occur continuously at all times. In such cases the existing algorithms would fail to determine the shortest path information in a time-critical manner.

Since such scenarios are representative of the actual environments in which the dynamic shortest path algorithms are likely to operate, the existing solutions would be limitedly useful. Misra and Oommen (2005b) proposed a learning solution by taking the aforementioned aspects into consideration. To the best of my knowledge, other than their solution, there is no known solution to finding the shortest path in a real-weighted graph where multiple edges are changing stochastically at once, and at the same time, which is more efficient than calculating everything from scratch for every change. The work reported by them was inspired by the need for formulating an algorithm for finding the shortest path in such realistically occurring stochastic environments. Indeed, they sought to find the shortest path in the “average” graph (dictated by an “Oracle,” also called the environment). Since, on query, the edge-weights supplied by the environment are assumed to follow an underlying unknown distribution, there exists a mean solution to the problem to which the algorithm would converge to after a sufficiently long time. Their intention was to find the “statistical” shortest path in the average graph that will be stable—regardless of the (possibly) continuously changing weights provided by the environment. Their solution generates superior results (when compared to the previous solutions). However, unfortunately, their scheme does not consider the insertion/deletion of edges. Thus, the problem they have considered assumes that there is one fixed structure graph with randomly changing edge weights, and that the distribution of these random variables is unknown.

Figure 1. Graph after the insertion of the edge C^F with weight 0.5

Graph after the insertion of the edge C^F with weight 0.5

All-Pairs Shortest Path Routing: dynamic versus static

Contrary to the previous discussions, in which the idea was of computing the shortest paths from one node to all the other nodes in a network, the problem of computing and maintaining all-pairs shortest paths information in a graph where the edges are inserted/deleted and edge-weights constantly increase/decrease is referred to as the Dynamic all-pairs shortest paths problem (DAPSP) (Demetrescu & Italiano, 2003; Ramalingam & Reps, 1996). The DAPSP problem has found equal importance as the DSSSP problem, among researchers and practitioners alike. Both the problems aim to efficiently maintain shortest path solutions in environments that are representative of most practical situations in daily life, since most real-life environments are dynamically changing.

Similar to what was discussed for the DSSSP problem and for the DAPSP problem as well, it can be shown that edge-weight updates can be treated as edge-deletions and edge-insertions by setting the weights of edges to an infinitely large value (Demetrescu & Italiano, 2003). Likewise, an edge-update algorithm for the all-pairs shortest path problem is referred to as being fully dynamic if both weight-increase and weight-decrease operations are supported on the edges of the graph. A semi-dynamic algorithm handles only weight-increases or weight-decreases, but not both at the same time (Demetrescu & Italiano, 2003).

Like the static solutions of the single source shortest path problem, the well-known static solutions for the all-pairs shortest path problem, for example, the Floyd-Warshall’s algorithm (Floyd, 1962), the all-pairs adaptations of Bellman-Ford’s algorithm (Bellman, 1958), or the Dijkstra’s algorithm (Dijkstra, 1959), which recompute the shortest paths from scratch each time a topology change occurs in the graph, are certainly inefficient in such dynamic practical scenarios.

Over the last few decades, there has been a lot of research done to solve the DAPSP problem. The earliest papers were written by Loubal (1967), Murchland (1967), and Rodinov (1968). Many other dynamic algorithms were proposed in the literature (e.g., Even & Gazit, 1985; Ramalingam & Reps, 1996; Rohnert, 1985); however, their worst-case running times were no better than recomputing the all-pairs shortest paths from scratch. Thereafter, a few solutions (Ausiello, Italiano, Marchetti-Spaccamela, & Nanni, 1991; Fakcharoemphol & Rao, 2001; Henzinger, Klein, Rao, & Subramanian, 1997; King, 1999) were proposed whose running times are better than a total recomputation. However, these solutions only work for integer weights. The algorithm proposed by Ausiello et al. (1991) is only applicable for the semi-dynamic case (decrease-only), and requires positive integer weights less than a constant “C.” Their algorithm’s amortized running time per insertion operation is O(Cnlogn) (Ausiello et al., 1991). Although Henzinger et al. (1997) provide a fully dynamic solution to the all-pairs shortest paths problem, their solution is only for planar graphs with integral values of edge-weights. The running time of their algorithm is O(n4/3log(nC)) per update operation. The first fully dynamic solution on general graphs was proposed by King (1999). Her solution too only works with positive integer weights less than C, and the running time of the algorithm is O(n25(Clog n)1/2). Later, Demetrescu and Italiano (2001) published a paper containing a fully dynamic algorithm that would perform edge-update operations on general graphs with real-valued edge-weights. If S represents the number of different real values, the amortized running time per update operation for their algorithm is O(n25(Slog3n)). Finally, in 2003, Demetrescu and Italiano (2003) proposed a remarkable algorithm that solved the same problem for general digraphs with edge-weights that can assume positive real values but with a substantially improved running time per edge-update operation.

Misra and Oommen (2005a) proposed a learning algorithm that finds all-pairs shortest paths for the statistical average network topology, and the solution converges irrespective of whether there are new changes in edge-weights or not. They showed that their solution has better performance than the Demetrescu and Italiano (2003)’s solution. In their solution, not all the edges in a stochastic network topology are probed, and even if they are, they are not all probed equally often. Indeed, their algorithm attempts to almost always probe only those edges that will be included in the final list involving all pairs of nodes in the graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. Their second contribution is the designing of a data structure, the elements of which represents the probability that a particular edge in the graph lies in the shortest path between a pair of nodes in the graph. Misra and Oommen (2005a)’s work is considered to represent the state of the art in this area.

applications

First of all, the application of shortest path algorithms in telecommunication is straightforward. They commonly find their use in routing equipments. In vast rapidly changing telecommunications wired or wireless networks, where links go up and down continuously and rapidly, and where there are simultaneous random updates in link costs, the existing algorithms are inefficient. Shortest paths need to be computed within a very short time (in the order of microseconds) with minimal number of nodes to be processed and edges to be scanned. Furthermore, in the transportation domain, there are complex road networks in urban areas. The costs of routing shipments from a warehouse to (all) other retail outlets constantly change. Changes occur because of a range of reasons such as road construction, accidents, traffic jams, office hours, and the presence of emergency vehicles. There are often several alternative routes that can be taken by a vehicle, whenever the predetermined route is unsuitable to deliver the shipments in time. Shipment vehicles may be equipped with suitable technology (like the global positioning system [GPS]) to guide them through alternative routes. The proposed learning algorithms can then be used to achieve such a vehicle routing. The same arguments would be true if airplanes have to be redirected adaptively to take care of changes.

In the military, the proposed learning algorithms also have several potential applications. For example, in complex military networks, ground forces may have to be rapidly rerouted based on sudden changes in enemy information and strategies along existing routes, and self-guided missiles may need to change their trajectories (within microseconds) to account for changes in the path along which it travels.

future trends

Interested researchers or practitioners could perform the following works to advance the state of the art in this area:

• Most of the aforementioned solutions (especially the recent ones) were reported on simulated networks of relatively small number of nodes. They have not been tested on massive sized networks. Testing the previous algorithms on large (on topologies with 10,000 to 100,000 nodes) simulated networks is required to understand their performance characteristics well.

• It is also required to test the performance of the algorithms in real-life networks, as most of the solutions mentioned previously have not been tried on such networks.

• Similarly, assessing the suitability of the aforementioned generic solutions in different application domains.

conclusion

In this article we reviewed different shortest path solutions that have been proposed since 1958/1959 when Bellman and Ford, and Dijkstra proposed their solutions for a static network. Of all the algorithms, the solutions proposed by Misra and Oommen (2005a) and Misra and Oommen (2005a) represent the state of the art. The experimental evaluation of their algorithms shows the superiority of their proposed algorithms. The characteristic of their algorithm is that once their algorithms have converged, the average number of processed nodes, scanned links, and the time per update operation is superior to the previously proposed algorithms by a few orders of magnitude. The advantage of their solution is that in stochastic network environments, it possesses a statistical shortest paths list that should be actual shortest paths irrespective of whether there are new changes in link costs taking place continuously. In such cases, their solution converges to a shortest paths list, while the existing algorithms would recalculate affected shortest paths after every change in link cost.

KEY TERMS

Algorithm: An algorithm is a set of clear steps that is used to define how a task or a set of tasks can be accomplished.

Dynamic Shortest Path Algorithm: An algorithm that is capable of finding a path that has the least distance (among all possible paths) between a pair of source and destination nodes in a network, when the status of nodes and links change with time.

Fully Dynamic All-Pairs Shortest Path Algorithm: If in a dynamic shortest-path algorithm, all edge operations (edge-insertion, weight-decrease, edge-deletion, weight-increase) are allowed, the algorithm is referred to as the fully dynamic algorithm.

Routing: The mechanism by which a path or a set of paths is selected to send information or commodities.


Semi-Dynamic Shortest Path Algorithm: If in a dynamic shortest-path algorithm, only edge-insertion/weight-decrease, or edge-deletion/weight-increase is allowed, the algorithm is referred to as the semi-dynamic algorithm.

Shortest Path Algorithm: An algorithm that is capable of finding a path that has the least distance (among all possible paths) between a pair of source and destination nodes in a network.

Static Shortest Path Algorithm: An algorithm that is capable of finding a path that has the least distance (among all possible paths) between a pair of source and destination nodes in a network, when all the nodes and links remain stationary.

Next post:

Previous post: