Dynamic Flow Routing and Scheduling for Time-Critical Network Services

Abstract

A key challenge in next-generation networks is providing intelligent network services to support time-sensitive applications such as AR/VR and the Internet of Military Things (IoMT). This work aims to answer the question: “How can we design a network service scheduling and flow routing scheme to satisfy the stringent demand and deadline requirements of tactical network applications?” We take a time-expanded graph-based approach to this study. Specifically, given a time-expanded graph constructed from an original network graph, we propose an optimization problem to find a subset of network services to maximize their total completion rewards such that the data of all services in this subset can be transmitted to their destination nodes by their deadlines. Unfortunately, solving this problem directly is challenging since it is a mixed-integer program. We propose a heuristic algorithm based on a sequential rounding approach where a linear programming (LP) feasibility problem is iteratively solved to update the network service subset, guided by a relaxed reward maximization problem that prioritizes high-reward requests. To further improve efficiency, we fine-tune the above LP feasibility problem from a static flow perspective, enabling fast feasibility checks on the original graph, and design the corresponding efficient heuristic algorithm. The simulation results demonstrate the trade-off among different approaches and validate the effectiveness of the proposed algorithms.