Scheduled Hot-Potato Routing
Joseph Seffi Naor, Ariel Orda, Raphaël Rom · Journal of Graph Algorithms and Applications · 1998
This paper is concerned with fast, hot-potato routing, performed according to a predetermined schedule. At each time period each node selects an outgoing link, through which an incoming packet is sent. No buffers are used. We investigate first the problem of how to route a network-wide demand of packets, given the predetermined schedule. We show that certain versions of the problem have efficient solutions, while other versions are intractable. We then consider the problem of finding an optimal schedule given a network-wide demand of packets. We indicate that the problem is tractable for either a single source or single destination. However, for the multi-source multi-destination case we show that it is an NP-complete problem. We present an efficient heuristic for directed tree-networks, and adapt it to general topologies through a recursive scheme, for which an efficient performance bound is shown.