The field of possible solutions must be explored intelligently: that is the aim of combinatorial optimisation.
Summary
Web-R is a tool developed by Orange and intended for all employees and subsidiaries of the Group. It provides decision aids for issues of placing. This type of problem is often met within the telecoms world, in particular by the architects who design networks, or by the operators who wish to evolve their infrastructure. Web-R can for example be a great help when designing future virtualised 5G networks, by working out optimal placing of controllers, or the deployment of virtual functions according to user needs. Thanks to its intuitive graphic interface, Web-R enables a non-expert person to apply high-level mathematical skills in a simple manner.
Full Article
Web-R is an internal tool that Orange Labs (the Orange Group’s Research and Development Department) makes available to the Orange Group and its subsidiaries to solve problems specific to the telecom world.
This tool is based on combinatorial optimisation, a branch of mathematics that is particularly useful for solving placement or routing problems. The best-known example of a problem in this branch is that of the travelling salesman, who has to visit all the villages in a region while minimising the journey. This problem is very difficult to solve for a fairly large number of villages. If we consider all the possible routes for a tour of 15 villages for example, we have to calculate the routes of more than 1,300 billion tours. For 20 villages, this rises to 2,400 trillion tours. This is what’s called a combinatorial explosion. Since it is impossible to calculate all possible routes, the field of possible solutions must be explored in an intelligent way. This is the purpose of combinatorial optimisation.
The travelling salesman problem. The black line represents the shortest possible route that connects the 36 points (left) or the 1,097 points (right).
Furthermore, virtualisation is an essential element for future networks (such as the future 5G mobile network, for example). This major network evolution raises a number of questions, in particular a number of research challenges in combinatorial optimisation.
Network Visualisation
At present, each piece of physical equipment making up a network has a very specific function. For example, a base station is used to manage radio channels with mobile phones, a firewall is used for port control, a router is used to transmit data, etc. In a virtualised network, the various functions of the network are executed by software, which runs on an ordinary calculation server.
The advantages of this approach are numerous. First of all, it facilitates the maintenance of the network equipment, since a simple software upgrade is all that is needed to upgrade it. Secondly, the network can be extended according to current needs. For example, if a device’s capacity limits are close to being reached, it is sufficient to increase the computing resources for the corresponding software. This is much simpler, faster and cheaper than installing new, more powerful equipment, as is currently done. In addition, it is easier to configure and control network functions when they are virtualised.
Virtualisation thus brings new possibilities but also new issues that we will detail now.
How do I do the routing?
On the Internet, data travels in the form of data blocks, known as IP (Internet Protocol) packets. These IP packets are routed through the network by routers. For example, if you are browsing an American site from France, your browser will generate an IP packet to the site in question. This packet will reach a French regional router, then go through a national router, then be sent to an American router, where it will continue on its way to its destination. This is called packet routing, because each router is connected to many other routers and each router must determine to whom it sends the packets it receives so that each packet arrives at the right port.
At the moment, routers have rules that are not very scalable to determine on which route to send packets based on their destination address. Thanks to virtualisation, routing rules can be controlled in detail and can be changed according to network load, for example. Thus, all routes can be recalculated in order to avoid congestion (i.e. queueing, which slows down packet processing). This route calculation corresponds to a combinatorial optimisation problem that can be handled using Web-R.
How to deploy controllers.
In a virtualised network, routers are directly controlled by a central decision point called a controller. The controller coordinates the routers so that data flows through the network as efficiently as possible. However, in order to be controlled efficiently, the routers must not be too far from the controller. Indeed, in the event of a network problem, the router will ask the controller where to send the data. For the response time to be reduced to a minimum, the controller must be close by. In addition, the controller can be broken down into several controllers that are synchronised with each other.
Thus the problem is where to place the controllers, so that they are both close to the routers they control and close to each other. This is to ensure that the controller-router and controller-controller communication time does not exceed a value beyond which the system could no longer function properly. For this reason, these constraints are called time constraints. In addition, a controller is limited by the number of routers it can manage. This is the load constraint.
Furthermore, a controller can crash. In this case, the remaining controllers must take over the management of the defective controller’s routers, while respecting the time and load constraints that have been set.
Problem of controller placement. Web-R indicates in green the best possible placement given the constraints.
Problem of controller placement. Web-R indicates in green the best possible placement given the constraints.
This placement problem respecting all set constraints can be solved with Web-R. You can visualise the graph of routers, the location of controllers and you can crash one or more controllers to see how the routers are redistributed across their new controllers.
Where to place and how to link virtual functions?
In a virtualised network, functions can be deployed on demand on routers. So if a firewall function is required, the firewall software is simply deployed on the path taken by the relevant data flow. The issue becomes more complicated when considering many data flows and the many functions to be applied to them. These functions must be applied in the right order, both the power consumed and the number of functions to be deployed must be minimised, and the most efficient routing for all flows must be performed.
Again, we are dealing with a combinatorial optimisation problem, which is handled by Web-R.
How to reduce the carbon footprint of data centres?
One of the advantages of virtualisation is to have a central decision-making point. This can be leveraged to achieve energy-efficient load sharing. If, for example, an Orange customer wants to watch video on demand on Orange TV, the TV set-top box sends a request to the nearest data centre. In the data centre, there is a calculation server that will process the request and send the requested video stream back. Sometimes, if the data centre has no more resources available to process the request, it redirects it to another data centre. This is called load sharing.
It is thus possible to implement load sharing that will reduce the carbon footprint of all data centres by exploiting two main levers.
The first lever exploits the standby mode of a data centre’s calculation servers when they are not in use. Requests are sent as a priority to where there are servers already in use. In this way, requests are grouped together on a minimum number of servers and the freed servers are put on standby.
The second lever consists of taking maximum advantage of the renewable energy produced locally by each data centre. This renewable energy comes from solar panels or wind turbines. By their nature, this energy production varies during the day. In addition, the time of day when this production is highest (e.g. midday for solar energy) does not correspond to peak demand (in the evening). Thanks to load sharing, this renewable energy can be exploited to the maximum and thus reduce CO2 emissions.
The question of how to distribute requests between data centres in order to minimise the number of calculation servers and the energy consumed is also a combinatorial optimisation problem that can be solved by Web-R.
Web-R
Thanks to its intuitive graphical interface, Web-R allows a non-expert to easily implement advanced mathematical techniques. This tool solves business problems commonly encountered in the telecom world. In just a few clicks, you can choose the constraints and characteristics of the problem to be solved.
Given the success of this tool and in order to respond to all requests, we decided to industrialise it so that it can be used by all employees of the Orange Group and its subsidiaries.
Web-R allows you to choose the constraints of the problems (“Requirements”) from a library of possible constraints (“Library”).
Find out more:
The Web-R tool is named after Alfred Weber (1868-1958), an economist and sociologist who studied placement problems extensively. In particular, he popularised and generalised the Fermat point of a triangle. The latter consists of locating a point D in relation to three points A, B and C so as to minimise the sum of the distances between D and each of the other three points.
What is combinatorial optimisation?
To avoid exploring all possible combinations of a problem, a widely used technique is “branch and bound“, which consists of calculating bounds for possible combination branches. In this way, we avoid exploring branches that we know do not contain an optimal solution. Other techniques such as “branch and price“, heuristics or metaheuristics, Benders decomposition, etc. can also be used.
The travelling salesman problem
What is network virtualisation?
