Distributed shortest-path protocols for time-dependent networks

 This paper addresses algorithms for networks whose behavior changes with time according to known functions. Because the computation depends on the same functions it attempts to compute, its execution must obey strict timing constraints. When distributed versions of such algorithms are considered, a key difficulty is how to transfer local timing functions among the participating nodes. To that end it is necessary to characterize the parameterization of the functions and accommodate this parameterization in the computation. In particular, we consider the shortest-path problem in networks in which the delay of the edges changes with time according to continuous functions. We present distributed protocols for finding the shortest and minimum delay path under various waiting constraints. We investigate and analyze protocols that exchange local time-delay functions only within limited intervals yet allow every node to calculate its representation in the shortest path in time for it to be used. Received: November 1992 / Accepted: December 1995