Future Networks: Overview of Optimization Problems in Decision-Making Procedures

Routing 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.