Near-optimal hot potato routing on trees

In hot-potato (deflection) routing, nodes in the network have no buffers for packets in transit, so that some conflicting packets must be deflected away from their destinations. In this work, we study one-to-many batch routing problems on arbitrary tree topologies with n nodes. The routing time of a routing algorithm is the time for the last packet to reach its destination. Denote by rt ∗ the optimal routing time for a given routing problem. We construct the first hot-potato routing algorithms whose routing times are asymptotically near-optimal; that is, the incurred routing times are within polylogarithmic factors from optimal. More specifically, we present: 1. A deterministic algorithm whose routing time is O(δ · rt ∗ · lg n), where δ is the maximum node degree; thus, for bounded-degree trees, the routing time becomes O(rt ∗ · lg n). 2. A randomized algorithm whose routing time is O(rt ∗ · lg2 n) with high probability; randomization is used for adjusting packet priorities. Both algorithms are local, hence distributed, and greedy; so, routing decisions are made locally, and packets are advanced towards their destinations whenever possible, respectively