.png){kind=icon}
.png){kind=icon}
Return
Pulse+: DetNet Routing Under Delay-Diff Constraint
.png){kind=icon}
PRE
AI
DOI：10.1109/TON.2025.3586040.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Deterministic Networking (DetNet) is a rising technology that offers deterministic delay & jitter and extremely low packet loss in large IP networks. To achieve determinism under failure scenarios, DetNet requires finding at least two paths with close end-to-end delay, i.e., a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">delay-diff</i> constraint, for mission-critical flows. However, how to find two routing paths subject to the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">delay-diff</i> constraint remains open. We study the DetNet routing problem in two scenarios. First, given a primary path, we propose Pulse+, which finds a secondary path whose end-to-end delay is within a range determined by the end-to-end delay of the primary path and the delay-diff requirement. Second, we propose CoSE-Pulse+, which integrates Pulse+ with a divide-and-conquer approach to find a pair of paths that meet DetNet’s delay-diff constraint. Both Pulse+ and CoSE-Pulse+ guarantee solution optimality. Notably, although Pulse+ and CoSE-Pulse+ do not have a polynomial worst-case time complexity, their empirical solver running time is better than that of other algorithms. We evaluate Pulse+ and CoSE-Pulse+ against the K-Shortest-Path and Lagrangian-dual based algorithms using synthetic test cases generated over networks with up to 10000 nodes. Both Pulse+ and CoSE-Pulse+ can solve more test cases than other algorithms under a predefined time limit. Compared to the second best algorithm, Pulse+ achieves an average-time speedup of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$5\times $ </tex-math></inline-formula> and CoSE-Pulse+ achieves an average-time speedup of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$22\times $ </tex-math></inline-formula>. Our code and test cases are available at <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://gitee.com/zsz2019_shizhenzhao/drcr</uri>
Keywords:
DetNet
routing
delay-diff
bounded jitter
Journal
I
IF:
0
Papers:
543
Citations:
0