  It has been shown that it is impossible to achieve both stringent end-to-end
deadline and reliability 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 packet arrivals, common
practice is to add redundancy by increasing link capacities. This paper studies
the amount of capacity needed to provide stringent performance guarantees. We
propose a low-complexity online algorithm and prove that it only requires a
small amount of redundancy to guarantee both end-to-end deadline and
reliability. Further, we show that in large networks with very high reliability
requirements, the redundancy needed by our policy is at most twice as large as
a theoretical lower bound. Also, for practical implementation, we propose a
fully distributed protocol based on the previous centralized policy. Without
adding redundancy, we further propose a low-complexity order-optimal online
policy for the network. Simulation results also show that our policy achieves
much better performance than other state-of-the-art policies.
