Hard-Real-Time Routing in Probabilistic Graphs to Minimize Expected Delay

Kunal Agrawal, Sanjoy Baruah, Zhishan Guo, Jing Li, Sudharsan Vaidhun

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


This work studies the hard-real-time routing problem in graphs: one needs to travel from a given vertex to another within a hard deadline. For each edge in the network, the worst-case delay that may be encountered across that edge is bounded. As far as this given bound is trustworthy at a very high level of assurance, it must be guaranteed that one will meet the specified deadline. The actual delays across edges are uncertain and the goal is to minimize the total expected delay while meeting the deadline. We propose a comprehensive solution to this problem. Specifically, if the precise a priori estimates of the delay probability distributions are available, we develop an optimal table-driven algorithm that identifies the route with the minimum expected delay. If those estimates are not precise (i.e., unknown or dynamic), we develop an efficient Q-Learning approach that leverages the table-driven algorithm to track the true distributions rapidly, while ensuring to meet the specified hard deadline. The proposed solution suggests a promising direction towards incorporating probabilistic information and learning-based approaches into safety-critical systems without compromising safety guarantees, when it is not feasible to establish the trustworthiness of the probabilistic information at the high assurance levels required for verification purposes.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 41st Real-Time Systems Symposium, RTSS 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages13
ISBN (Electronic)9781728183244
StatePublished - Dec 2020
Event41st IEEE Real-Time Systems Symposium, RTSS 2020 - Virtual, Houston, United States
Duration: Dec 1 2020Dec 4 2020

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Conference41st IEEE Real-Time Systems Symposium, RTSS 2020
Country/TerritoryUnited States
CityVirtual, Houston

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


  • guaranteed delay bounds
  • minimize expected delay
  • real-time routing
  • reinforcement learning


Dive into the research topics of 'Hard-Real-Time Routing in Probabilistic Graphs to Minimize Expected Delay'. Together they form a unique fingerprint.

Cite this