.png){kind=icon}
.png){kind=icon}
Return
Bandwidth-Delay Optimal Segment Routing: Upper-Bound and Lower-Bound Algorithms
.png){kind=icon}
PRE
AI
DOI：10.1109/TNSM.2026.3678190.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Segment routing (SR) is a novel source routing paradigm that enables network programmability. However, existing research rarely considers multicriteria optimization problems in SR networks. Given the critical role of bandwidth and delay in quality-of-service (QoS) routing, we formally define the bandwidth-delay optimal SR (BDoSR) problem for the first time and prove its NP-hardness. By leveraging the label correcting algorithm schema, we design a suite of polynomial-time algorithms, including an upper-bound algorithm (BDoSR-UB) and a lower-bound algorithm (BDoSR-LB). BDoSR-UB enables rapid estimation of the optimal solution while BDoSR-LB is accuracy-adjustable and delivers (near-)optimal feasible solutions. We rigorously analyze their performance gap through carefully constructed network examples, providing deep insights into the adjustable parameters of BDoSR-LB. Finally, we validate our algorithms on realistic network topologies, demonstrating that both BDoSR-UB and BDoSR-LB frequently converge to the optimal solution in practice while offering superior computational efficiency compared to existing approaches.
Keywords:
Segment routing
quality-of-service routing
multicriteria optimization
labeling algorithm
Journal
IF:
5.4
Papers:
527
Citations:
9.2K