Abstract
This chapter gives an insight into some challenging combinatorial optimization problems that have to be tackled to deliver efficient and appropriate decision algorithms to manage future networks. The first part of the chapter is dedicated to variants of routing optimization problems in future IP networks, and the second part is dedicated to two optimization problems related to network virtualization and 5G network slicing, the virtual network embedding problem and the service function chaining problem. Each of these optimization problems is described along with the main challenges to overcome, and a recent and extensive related state of the art is given, so as to highlight the most recent and promising approaches to solve them.
TopRouting Optimization In Software-Defined Networks
In spite of the promises of the MPLS forwarding scheme, most IP networks still heavily rely on shortest-path rules where weights are assigned to links by network administrators and the routers are then able to compute shortest routing paths. It has been acknowledged for a long time that this indirect control (by setting administrative weights only) on the overall routing scheme makes the TE (Traffic Engineering) tasks very difficult to execute. On the contrary, MPLS-based mechanisms allow network administrators to deploy almost any possible routing pattern. However, the introduction of such a powerful tool shifts the problem from “how do I set weights so that traffic uses (more or less) the routes I want?” to a new kind of problem, namely “how do I find the best set of routes?” Indeed, if traffic between any o-d (origin-destination) pair can be forwarded along any combination of paths, deciding the routes for all o-d pairs at the same time seems an intractable problem.
Fortunately, such problems are extremely well solved using sophisticated optimization techniques and powerful algorithmic tools. The rise of SDN is a major opportunity to wisely combine all these optimization approaches in order to derive efficient routing and forwarding policies.
Key Terms in this Chapter
5G Standardization: The fifth generation of mobile network is currently (2018) in the process of being standardized by 3GPP (3rd generation partnership project). The IETF (internet engineering task force) is also working on a lot of topics closely related to 5G networks, namely overlay networks, traffic engineering, service function chaining, etc.
Shortest Path: A path in the network between an origin node and a destination node that minimizes the sum of the weights of its composing edges.
ILP Formulation: An integer linear programming (ILP) formulation is the mathematical formulation of an optimization problem in which variables are restricted to integer values and the constraints and objective function are linear. Mixed integer linear programming (MILP) refers to optimization problems in which some of the variables are continuous.
Traffic Engineering: A set of mechanisms for better managing network resources and performance in order to deliver better services.
Optimized Routing: A routing pattern in an IP network that optimizes a given criterion (end-to-end one-way delay, network load, cost, etc.) while complying with a set of constraints.
Optimization Problem: A problem that is described by: a set of parameters (inputs of the problem), a set of continuous or discrete decision variables, a set of constraints (in the form of equalities or inequalities over the parameters and variables), and an optimization criterion that is expressed as an objective function to be optimized. The goal is to find the best solution of the problem, that is the values of the variables that optimize (i.e., minimize or maximize, depending on the problem) the objective function, among all the feasible solutions (the solutions that fulfill the set of constraints).
Survivable and Robust Networks: A network is said to be survivable if it implements one or several protection mechanisms allowing for resilience against link or node failures. The notion of robustness can be used for fault-tolerance but refers more often to the ability to effectively cope with uncertainties about traffic (or other input data).