Online Routing and Scheduling with Capacity Redundancy for Timely Delivery Guarantees in Multihop Networks

It has been shown that it is impossible to achieve stringent timely delivery guarantees in a large network without having complete information of all future packet arrivals. In order to maintain desirable performance in the presence of uncertainty of future, a viable approach is to add redundancy by increasing link capacities. This paper studies the amount of capacity needed to provide stringent timely delivery guarantees. We propose a low-complexity online algorithm and prove that it only requires a small amount of redundancy to guarantee the timely delivery of most packets. Furthermore, we show that in large networks with very high timely delivery requirements, the redundancy needed by our policy is at most twice as large as the theoretical lower bound. For practical implementation, we propose a distributed protocol based on this centralized policy. Without adding redundancy, we further propose a low-complexity order-optimal online policy for the network. The simulation results show that our policies achieve much better performance than the other state-of-the-art policies.