Segment Routing is a recent network technology that helps optimizing network throughput by providing finer control over the routing paths. Instead of routing directly from a source to a target, packets are routed via intermediate waypoints. Between consecutive waypoints, the packets are routed according to traditional shortest path routing protocols. Bottlenecks in the network can be avoided by such rerouting, preventing overloading parts of the network. The associated NP-hard computational problem is Segment Routing: Given a network and a set of traffic demands (vertex pairs), the task is to find for each demand pair the placement of a given number of waypoints such that with shortest path routing along these waypoints, all demands are fulfilled without exceeding the capacities of the network. We investigate if special structures of real-world communication networks could be exploited algorithmically. Our results comprise NP-hardness on graphs with constant treewidth even if only one waypoint per demand is allowed. We further exclude (under standard complexity assumptions) the existence of efficient exact algorithms even if we assume a fixed number of waypoints per demand and a “small” amount of traffic demands. We complement these lower bounds with polynomial-time solvable special cases.

Nested Rollout Policy Adaptation (NRPA) is an approach using online learning policies in a nested structure. It has achieved a great result in a variety of difficult combinatorial optimization problems. In this paper, we propose Meta-NRPA, which combines optimal stopping theory with NRPA for warm-starting and significantly improves the performance of NRPA. We also present several exploratory techniques for NRPA which enable it to perform better exploration. We establish this for three notoriously difficult problems ranging from telecommunication, transportation and coding theory namely Minimum Congestion Shortest Path Routing, Traveling Salesman Problem with Time Windows and Snake-in-the-Box. We also improve the lower bounds of the Snake-in-the-Box problem for multiple dimensions.

Forthcoming 5G is envisioned to provide services to a diverse set of verticals with varying performance and QoS (Quality of Service) requirements. Network slicing is one of the key enabling technologies that allows this heterogeneous service delivery by running multiple virtual networks with different network characteristics on a common physical infrastructure. Naturally, various 5G use cases related to network slicing such as resource allocation, placement, and pricing of network slices have emerged. One of the crucial challenges is to model and simulate these use cases and test/train decision-making algorithms in a realistic environment before deployment in production. We tackle this problem by proposing an agent-based framework to model and simulate end-to-end 5G networks as well as implement its use cases. Furthermore, we demonstrate the capability of our simulator to integrate decision-making approaches by presenting algorithms implemented on our simulation environment for placing and pricing network slices.

In this paper, we consider the Unsplittable Shortest Path Routing (USPR) problem which arises in the field of traffic engineering for IP networks. This problem consists, given a bidirected graph and a set of commodities, to compute a set of routing paths and the associated link weights such that each commodity is routed along the unique shortest path between its origin and its destination, according to these weights. In this paper, we propose a novel extended formulation based on routing variables that is solved using a column generation procedure, further enriched by primal heuristics allowing to build of an efficient matheuristic. We show through a set of experiments that our algorithm allows to quickly identify good feasible solutions when compared to the results obtained by the state-of-the-art local search algorithm.