Forwarding Packets Greedily
This work provides the first progress on an open problem in network optimization, specifically for researchers and practitioners dealing with packet forwarding in line networks.
This paper addresses the problem of minimizing maximum flow time for online packet forwarding in a line network. For the specific case where packets require forwarding by one or two routers, a novel greedy algorithm achieves a competitive ratio of 2-2^(1-k), where k is the number of active routers.
We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its right. Each packet that is forwarded arrives at the next router one time step later. Packets are forwarded until they reach their destination. The flow time of a packet is the difference between its release time and the time of its arrival at its destination. The goal is to minimize the maximum flow time. This problem was introduced by Antoniadis et al.~in 2014. They propose a collection of natural algorithms and prove for one, and claim for others, that none of them are $O(1)$-competitive. It was posed as an open problem whether such an algorithm exists. We make the first progress on answering this question. We consider the special case where each packet needs to be forwarded by exactly one or two routers. We show that a greedy algorithm, which was not previously considered for this problem, achieves a competitive ratio of exactly $2-2^{1-k}$, where $k$ is the number of active routers in the network. We also give a general lower bound of $4/3$, even for randomized algorithms.