Locally efficient on-line strategies for routing packets along fixed paths
Petra Berenbrink, Christian Scheideler · 1999
Most of the work done in the area of static routing concentrates on minimizing the runtime of the whole schedule rather than minimizing the runtime of individual packets, using global parameters such as the congestion and dilation of a path collection. In this paper, we study the problem of minimizing the routing time of individual packets, using local parameters. In fact, we present the first (up to a log log factor) optimal, truly on-line routing protocols for the following problems: Packet switching: Assume that a fixed collection of paths is given. For every path p in this collection, let c p denote the maximum number of paths that share an edge with p, and let d p denote the length of p. Find a schedule (that does not require to know c p and d p ) such that the routing time of a packet following a path p merely depends on c p and d p . Virtual circuit switching: Assume that a fixed set of sessions is given. For every session i, packets are injected at a rate r i to f...