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

Han Deng, Tao Zhao, I. Hong Hou

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number8726331
Pages (from-to)1258-1271
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number3
StatePublished - Jun 2019


  • Competitive ratio
  • cyber-physical systems
  • multihop networks
  • online algorithms
  • optimal scheduling

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Online Routing and Scheduling with Capacity Redundancy for Timely Delivery Guarantees in Multihop Networks'. Together they form a unique fingerprint.

Cite this