Time-Triggered Flow Scheduling for Synchronization-Deviation-Tolerant TSN

Time-sensitive networking (TSN) has been widely used in industrial automation and automotive applications by precisely opening and closing the gates of packet queues. However, both clock drift and network congestion will likely result in timing misalignment when the clock synchronization protocol gPTP (802.1 AS) is used. This timing misalignment may, in turn, cause failure in forwarding packets at scheduled times and hence unexpected delay jitters, or even miss application deadlines. To address this acute problem, we propose a novel TSN scheduling algorithm, called SDT-TSN (Synchronization-Deviation-Tolerant TSN), to ensure that packets can still arrive on time and be transmitted deterministically even in the presence of inexact time synchronization. First, we formalize the linear constraint model of flow scheduling to maximize the tolerance of inexact time synchronization. Then, we propose an optimal algorithm based on SMT (Satisfiability Modulo Theories) and a fast heuristic algorithm to solve the packet scheduling problem under inexact network synchronization. SDT-TSN is the first to derive the maximum tolerable time-synchronization deviation. Finally, we evaluate SDT-TSN, demonstrating its capability of eliminating packet-forwarding failures due to the commonly-used/assumed constant time-synchronization deviation and increasing the tolerable synchronization deviation from 140µs to 480µs.