UNIVERSAL CONTINUOUS ROUTING STRATEGIES

We analyze universal routing protocols, that is, protocols that can be used for any communication pattern in any network, under a stochastic model of continuous message generation, In particular, we present two universal protocols, a store-and-forward and a wormhole routing proto col, and characterize their performance by the following three paramet ers: the maximum message generation rate for which the protocol is sta ble, the expected delay of a message from generation to service, and t he time the protocol needs to recover from worst-case scenarios. Both protocols yield significant performance improvements over all previous ly known continuous routing protocols. In addition, we present adaptat ions of our protocols to continuous routing in node-symmetric networks , butterflies, and meshes.