An Extension of Shortest-Path Algorithms and Their Properties

Antonis Dimakis
(Professor Jean Walrand)

I have been studying the structural properties of shortest path algorithms. The problem can be thought of as an inverse to the classical shortest path problem. In particular, assume that given a network of nodes, e.g., a network of autonomous systems (AS) in the context of BGP, each of these has totally ordered preferences over all possible paths that lead to a specified destination. The problem that we attempt to answer is whether link costs exist such that the ordering induced by such costs coincides with the order given originally.

Necessary and sufficient conditions in terms of the original path order are derived, which characterize when such costs exist. Interestingly, in some cases where appropriate link costs do not exist, if such cost existed, then the calculation of the optimal routes by each node could have been solved efficiently in a distributed fashion by employing some variant of the Bellman-Ford routing algorithm. It turns out that one can extend the notion of link cost to a transformation, and by appropriately defining the action of this transformation on the integers. The classical shortest path algorithm is a particular case of this formulation, where each integer corresponds to a transformation, and each transformation acts by translation by the associated integer. This extended formulation of shortest paths allows us to find appropriate extended link costs that match the given path preferences in cases where the classical formulation fails. Currently, I am looking at methods for efficiently implementing these extended link costs.

An application of this problem occurs in the design of routing algorithms that are robust under node or link failures. In general, the system operator has a fallback plan of alternative routes that are to be followed when failures occur. In the occurrence of failures, the surviving nodes do not need to solve a new optimization problem in order to calculate how failed routes need to be rerouted. In particular, by running a standard shortest path algorithm, e.g., Bellman-Ford, using extended link costs, perhaps each node can find the optimal rerouting.

In the future, I plan to study the properties of extended classes of shortest path algorithms. Although, a single set of extended costs which match arbitrary preferences over an arbitrary network topology exist, their implementation is intractable. What one wants is the construction of a universal set of extended costs that always give a solution in the cases where path preferences posses a pre-specified structure. Thus, I plan to devise a set of theoretical tools that give constructable solutions for the given preference structures.


Send mail to the author : (dimakis@eecs.berkeley.edu)


Edit this abstract