Spatial-temporal routing for supporting end-to-end hard deadlines in multi-hop networks

We consider the problem of routing packets with end-to-end hard deadlines in communication networks. The problem is challenging due to the complex spatial-temporal correlation among flows with different deadlines. To tackle this challenging problem, we introduce the concepts of virtual links/routes to incorporate end-to-end deadline constraints into routing and propose a novel virtual queue architecture to guide the spatial-temporal routing which specifies where and when a packet should be routed. The proposed policy can support any periodic constant traffic within the network throughput region. Our simulations further show that the policy outperforms traditional policies such as backpressure and earliest-deadline-first (EDF) for general traffic flows.