Dynamic Tree Routing under the "Matching with Consumption" Model

. In this paper we present an extensive study of dynamic routing on trees under the "matching with consumption" routing model. We present an asymptotically optimal on-line algorithm which routes k packets to their destination within d(k \Gamma 1) + d \Delta dist routing steps, where d is the degree of tree T on which the routing takes place and dist is the maximum distance any packet has to travel. We also present an off-line algorithm that solves the same problem within 2(k \Gamma 1) + dist steps. The analysis of our algorithms is based on the establishment of a close relationship between the matching and the hot-potato routing models. 1 Introduction In a packet routing problem on a connected undirected graph G we are given a collection of packets, each packet having an origin and a destination node, and we are asked to route them to their destinations as fast as possible. During the routing, the movement of the packets follows a set of rules. These rules specify the routing model. R..