Technion AND

Abstract. This article studies approximate distributed routing schemes on dynamic communication networks. The work focuses on dynamic weighted general graphs where the vertices of the graph are fixed, but the weights of the edges may change. Our main contribution concerns bounding the cost of adapting to dynamic changes. The update efficiency of a routing scheme is measured by the time needed in order to update the routing scheme following a weight change. A naive dynamic routing scheme, which updates all vertices following a weight change, requires (Diam) time in order to perform the updates after every weight change, where Diam is the diameter of the underlying graph. In contrast, this article presents approximate dynamic routing schemes with average time complexity ˜(D) per topological change, where D is the local density parameter of the underlying graph. Following a weight change, our scheme never incurs more than Diam time; thus, our scheme is particularly efficient on graphs which have low local density and large diameter. The article als