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.

Motivated by multi-domain Service Function Chain (SFC) orchestration, we define the Shortest-Longest Path (SLP) problem, prove its hardness, and design an efficient Fully Polynomial Time Approximation Scheme (FPTAS) using the scaling and rounding technique to compute an approximation solution with provable performance guarantee.

Monitoring packet losses at links is beneficial to network management and service quality improvement. Software-defined networking can conveniently obtain flow statistics. However, the packet loss rate of a link or path cannot be directly measured by acquiring the statistics of an ongoing flow. In addition, monitoring the packet loss directly based on statistics inquiries brings considerable extra overhead to the controller. In this paper, we propose a two-way link-level packet loss monitoring solution for the software-defined networks. We propose a packet loss probe structure consisting of distributed rings. The proposed probe structure contains every monitored directed link once and only once, thereby avoiding the mutual interference between different probe flows and thereby improves probe accuracy. We further study two optimization problems of the ring-based packet loss probe structure. The two problems build probe structures, with minimal maximum ring delay, for all the network links and selected network links. The two optimization problems are very complex, and we approximately solve them in polynomial time. A packet loss positioning algorithm, based on flow statistic inquiries and the symmetry design of probe rings, is also proposed. Our proposed solution can effectively monitor link-level packet loss but brings low and controllable overhead to the controller.

Traditional group multicast routing (TGMR) is well known for its difficulty. The technology of network coding bring a new light to this problem. This paper addresses the network coded group multicast routing problem (NCGMR). We propose a hierarchical decomposition model for the minimum cost routing of NCGMR, implement the model in a distributed fashion and extend the model to 0-1 linear programming for TGMR. Finally, we prove that our approach is feasible and evaluate its convergence performance by a numerical example.

Multi-commodity multicast has a wide variety of applications in today's Internet and consumes a large amount of bandwidth resource. In this paper, we propose a two-level decomposition (TLD) model for multi-commodity multicast. Since network coding is allowed, the proposed model can achieve minimum-cost traffic engineering in the presence of uncontrolled traffic. In addition, all the generated subproblems can be computed in parallel or implemented in a distributed manner.

Packet loss rate is an important consideration in the Quality of Service (QoS) measurement for a packet-switched network. The software-defined networking (SDN) technique can conveniently monitor flow statistics. However, the packet loss rate of a link or path cannot be directly measured by inquiring the statistics of an ongoing flow at the starting and ending points because it is impossible to accurately compute and control pairwise sampling moments. In this paper, we propose a two-way link-level packet loss measurement solution for software-defined networks. We solve the flow statistics sampling problem mentioned above by inquiring the statistics of a terminated probe flow. We propose a ring-based packet loss probe structure, which contains every measured directed link once and only once. The proposed probe structure effectively avoids the mutual interference between different probe flows, and thereby improves probe accuracy. The ring is implemented based on the flexible flow match capability of SDN. We further study an optimization problem of ring-based packet loss probe structure that strives to minimize the maximum delay of rings. This optimization problem is very complex, and we approximately solve it using a top-down-top graph partition method. A packet loss positioning method, based on flow statistic inquiries and the symmetry design of the probe ring, is also proposed herein.