DISTRIBUTED SHORTEST-PATH PROTOCOLS FOR TIME-DEPENDENT NETWORKS

This paper addresses algorithms for networks whose behavior changes wi th 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 algorithm s are considered, a key difficulty is how to transfer local timing fun ctions among the participating nodes. To that end it is necessary to c haracterize the parameterization of the functions and accommodate this parameterization in the computation. In particular, we consider the s hortest-path problem in networks in which the delay of the edges chang es with time according to continuous functions. We present distributed protocols for finding the shortest and minimum delay path under vario us waiting constraints. We investigate and analyze protocols that exch ange local time-delay functions only within limited intervals yet allo w every node to calculate its representation in the shortest path in t ime for it to be used.