Joint Routing and Scheduling for Large-Scale Deterministic IP Networks

With the advent of 5G and the evolution of Internet protocols, industrial applications are moving from vertical solutions to general purpose IP-based infrastructures that need to meet deterministic Quality of Service (QoS) requirements. The IETF DetNet working group aims at providing an answer to this need with support for (i) deterministic worst-case latency and jitter, and (ii) zero packet loss for time-sensitive traffic. In this paper we focus on the joint routing and scheduling problem in large scale deterministic networks using Cycle Specified Queuing and Forwarding (CSQF), an extension of Cyclic Queuing and Forwarding (CQF) with multiple transmission queues and support of segment routing. In this context, we present two centralized algorithms to maximize traffic acceptance for network planning and online flow admission. We propose an effective solution based on column generation and dynamic programming. Thanks to the reinforcement of the model with valid inequalities, we improve the upper bound and the solution. We demonstrate on realistic instances that we reach an optimality gap smaller than 10% in a few seconds. Finally, we also derive an ultra-fast adaptive greedy algorithm to solve the problem at the cost of a small extra gap.