Search

This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles partition of the underlying communication graph. Dynamic routing schemes are ranked by their adaptability, i.e., the maximum number of sites to be updated upon a topology change. An advantage of our scheme is that it implies a small number of updates upon a topology change. In particular, for the case of a bounded degree network it is proved that our scheme is optimal in its adaptability by presenting a matching tight lower bound. Our bubble routing scheme is a combination of a distributed routing database, a routing strategy, and a routing database update. It is shown how to perform the routing database update on a dynamic network in a distributed manner.

We consider true broadcast systems for the secure communication of session keys. These schemes provide for parallel rather than serial construction of broadcast messages, while avoiding selective broadcasting. We begin by introducing a conceptual framework for true broadcasting and illustrate its design with a secure key broadcast scheme based on probabilistic encryption. The framework provides for a system requiring user anonymity, as a result of the absence of addressing for the broadcast message. We also illustrate how Shamir's threshold scheme can be altered to allow for parallel broadcasting. We then present a formal model and use information theoretic techniques to establish a lower bound on the size of the broadcast message for a class of true broadcast schemes. Finally, we improve upon the aforementioned threshold scheme such that it achieves the lower bound.

Three parameters characterize the performance of a probabilistic algorithm: T, the runtime of the algorithm; Q, the probability that the algorithm fails to complete the computation in the first T steps and R, the amount of randomness used by the algorithm, measured by the entropy of its random source.We present a tight tradeoff between these three parameters for the problem of oblivious packet routing on N-vertex bounded-degree networks. We prove a (1 - Q) log N/T - log Q - O(1) lower bound for the entropy of a random source of any oblivious packet routing algorithm that routes an arbitrary permutation in T steps with probability 1 - Q. We show that this lower bound is almost optimal by proving the existence, for every e3 log N ≤ T ≤ N1/2, of an oblivious algorithm that terminates in T steps with probability 1 - Q and uses (1-Q+o(1))logN/T-logQ independent random bits.We complement this result with an explicit construction of a family of oblivious algorithms that use less than a factor of log N more random bits than the optimal algorithm achieving the same run-time.