P4LoF: Scheduling Loop-Free Multi-Flow Updates in Programmable Networks

The rapid growth of distributed data-centric applications and AI workloads increases demand for low-latency, high-throughput communication, necessitating frequent and flexible updates to network routing configurations. However, maintaining consistent forwarding states during these updates is challenging, particularly when rerouting multiple flows simultaneously. Existing approaches pay little attention to multi-flow update, where improper update sequences across data plane nodes may construct deadlock dependencies. Moreover, these methods typically involve excessive control-data plane interactions, incurring significant resource overhead and performance degradation. This paper presents P4LoF, an efficient loop-free update approach that enables the controller to reroute multiple flows through minimal interactions. P4LoF first utilizes a greedy-based algorithm to generate the shortest update dependency chain for the single-flow update. These chains are then dynamically merged into a dependency graph and resolved as a Shortest Common Super-sequence (SCS) problem to produce the update sequence of multi-flow update. To address deadlock dependencies in multi-flow updates, P4LoF builds a deadlock-fix forwarding model that leverages the flexible packet processing capabilities of the programmable data plane. Experimental results show that P4LoF reduces control-data plane interactions by at least 32.6% with modest overhead, while effectively guaranteeing loop-free consistency.