O(Congestion + Dilation) Hot-Potato Routing on Leveled Networks

摘要

We study packet routing problems, in which we route a set of N packets on preselected paths with congestion C and dilation D. For store-and-forward routing, in which nodes have buffers for packets in transit, there are routing algorithms with performance that matches the lower bound Ω(C + D). Motivated from optical networks, we study the extreme case of hot-potato routing in which the nodes are bufferless. In hot-potato routing, packets may be unable to follow the preselected paths towards the destination nodes; thus it may take more time for packets to be routed. An interesting question is how much is the performance of routing algorithms affected from the absence of buffers. Here, we answer this question for the general class of leveled networks, in which the nodes are partitioned into L + 1 distinct levels. We present a randomized hot-potato routing algorithm for leveled networks, which routes the packets in O(C + L) time with high probability. For routing problems with dilation O(L), this bound is within polylogarith-mic factors from the lower bound Ω(C + L). Our algorithm demonstrates that the benefit from using buffers is no more than polylogarithmic; thus, hot-potato routing is an efficient way to route packets in leveled networks. Our algorithm is online, that is, routing decisions are taken at real time at each node, while packets are routed in the network. A novel characteristic of our algorithm is that during the course of routing, packets may deviate from their preselected paths. To our knowledge, this is the first hot-potato algorithm designed and analyzed, in terms of congestion and dilation, for arbitrary leveled networks.