WO2018130307A1

WO2018130307A1 - An architecture and coordination mechanism to distribute and parallelize any mcf solver

Info

Publication number: WO2018130307A1
Application number: PCT/EP2017/050727
Authority: WO
Inventors: Georgios Paschos; Ioannis STEIAKOGIANNAKIS; Mathieu Leconte
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2017-01-13
Filing date: 2017-01-13
Publication date: 2018-07-19
Anticipated expiration: 2019-07-13

Abstract

The present invention relates to systems, an apparatus and a method for computing a solution to an optimization problem within a communication network through the use of algorithms. The network uses a SDN architecture either with multiple controllers and a messaging protocol distributed amongst the multiple controllers or with a centralized controller and a messaging protocol distributed amongst multiple computing devices, each SDN controller comprising a respective computing device. In the former option, the network is split into a plurality of clusters assigned each to a respective SDN controller and the problem is locally solved at each respective cluster. In the latter option, the SDN controller is split into a plurality of parts assigned each to a respective computing device and the problem is locally solved at each respective part.

Description

TITLE

An architecture and coordination mechanism to distribute and parallelize any MCF solver

TECHNICAL FIELD The present invention relates to a system, apparatus and method for computing a solution to an optimization problem within a multi-controller software-defined networking (SDN) architecture.

BACKGROUND

The first manifestations of SDN technology put together the network control logic into one monolithic physical entity, the SDN controller, which decides the routing to globally optimize the network. Indeed, a single SDN controller can centrally optimize traffic engineering by having a global view of the network. The SDN controller solves a centralized optimization problem in frequent intervals in order to decide the optimal routing of packet flows. The cornerstone optimization problem for a SDN product is the minimum cost flow (MCF) problem (also denoted by minimum cost multi-commodity flow (MCF) problem), which consists in seeking for the packet flow for multiple commodities that minimizes the total cost. In the centralized form, MCF is a linear program (LP) solved by standard centralized optimization methods such as the column generation method and the interior-point method, which are however less efficient empirically when applied within a network of nodes of large size, usually a network of more than one thousand nodes.

For scalability reasons, the recent SDN architecture is based on multiple SDN controllers retaining either a centralized control logic like in the distributed control platforms ONIX for large-scale production networks and the Open Network Operating Systems (ONOS) or a distributed control logic like in the hierarchical control planes KANDOO and ORION, wherein each SDN controller has a view of the domain for which it is responsible and can make decisions. In a distributed SDN (dSDN), there are many SDN controllers and each controller is assigned to a part of the network, as depicted in Fig. 1 showing a vertical (a) and horizontal (b) approach with access to a distributed database system (DDBS) and wherein each part of the network is controlled by a single SDN controller. The vertical approach requires a DDBS allowing the SDN controllers to have a synchronized global view of the network. For example, when a new flow is admitted and its routing is decided by the controller 1, the DDBS is updated and the controller 2 is then informed of this decision by directly reading the DDBS. If the dSDN system has an available DDBS, then the MCF problem can be solved with the aforementioned standard centralized optimization methods provided that the global network is small enough to be handled by a single entity.

When there is no DDBS, centralized optimization methods do not apply since the SDN controllers do not have a global view of the system variables. Thus, the solution to solve the MCF problem is to resort to distributed optimization methods, the same being true for any other end-to-end traffic engineering optimization. To that extent, Fig. 2 shows a distributed SDN architecture 100 with multiple controllers (controller 1 to controller 3) arranged in a flat topology. Each SDN controller monitors a different domain or part (Dl to D3) of the network and its knowledge about topology and network state is limited to that respective domain. The SDN controllers of two neighboring network nodes can communicate with each other through an east-west controller-to-controller interface using an appropriate message exchange protocol. In Fig. 2, the optimal routing is globally studied. Thus, the SDN controllers act as agents in a distributed system, which exchange messages and perform local computations with the aim of reaching an agreement on the flow routing that minimizes the total cost. This problem of cost minimization can be solved by the classical fully distributed routing algorithms, which however suffer from slow convergence as they tend to explore many network paths before reaching the optimal solution.

Although the centralized and distributed SDN architectures scale out the control load, when more than one SDN controller is available, the distributed SDN architecture is advantageous with respect to the centralized SDN architecture for several reasons. Indeed, it is more easily scalable and can thereby work on larger networks. Moreover, it facilitates an incremental deployment and can thereby add other SDN controllers when the network is expanded. In addition, it offers privacy and can thereby work in a multi-operator environment in which confidential or sensitive network information is not leaked from one domain to another or from one vendor to another. Thus, although the centralized algorithms maintain only a small number of active paths and can be extremely efficient, they are nevertheless not directly applicable to the depicted distributed SDN architecture 100 so that a global network optimization using a group of SDN controllers in a distributed fashion becomes challenging. SUMMARY

It is therefore an object of the present invention to provide a system, apparatus and method for computing a solution to an optimization problem within a communication network, by means of which the centralized approach is modified to be rendered applicable to a distributed SDN architecture with a certain degree of distribution using a distribution or parallelization of sparse algorithms capable of retaining the sparsity property.

The object is achieved by the features of the independent claims. Further embodiments of the invention are apparent from the dependent claims, the description and the figures.

According to a first aspect, the invention relates to a system for computing a solution to a problem within a communication network, wherein the communication network is split into a plurality of clusters. The system comprises a plurality of software-defined networking (SDN) controllers configured to compute the solution by solving the problem at each respective cluster to which a respective SDN controller is assigned, and a messaging module configured to exchange a sequence of messages between each SDN controller amongst the plurality of SDN controllers, wherein the solution is based on the sequence of messages exchanged between each SDN controller.

Thereby, a global problem is solved using several SDN controllers, none of which has a global view of the communication network. Indeed, each SDN controller has a local view of the network, namely an intra-cluster view of the network. Thus, each SDN controller solves an equivalent local problem and brings a solution to it by finding, for example, some paths in the case of a MCF problem. Owing to the exchanged messages between each SDN controller associated to a respective cluster, the solution to the original problem can be reached by finding, for example, the entirety of the paths in the case of a MCF problem.

According to a first implementation of the system according to the first aspect, each SDN controller comprises a respective computing device, the respective computing device communicating with each other computing device through the messaging module. Thereby, the exchanged messages between each SDN controller can be processed through the computing device inside each SDN controller. Each computing device can be, for example, a computer system, a server system, a virtual machine or a central processing unit core in the case of a multi-core architecture.

According to a second implementation of the system according to the first implementation of the first aspect, each computing device comprises a respective problem solver configured to provide the computed solution, a respective coordination module configured to compute the sequence of messages using some information from the respective problem solver and the remaining problem solvers, and a respective driver module configured to interface the respective coordination module and the respective problem solver.

Thereby, each problem solver can solve its local problem while communicating with the remaining problem solvers by means of the exchanged messages.

According to a third implementation of the system according to the second implementation of the first aspect, the respective driver module provides the respective problem solver with a modified problem, which is defined by the respective driver module.

Thereby, the driver module that interfaces the problem solver and the coordination module can be a set of rules that feeds the problem solver with a modified problem with respect to the original problem. To solve the original problem, a particular calculation of, for example, Lagrange multipliers, will take place at each cluster that includes boundary values from neighboring clusters and a local sparse algorithm will be then used to obtain the optimal convergence. In the latter step, the algorithm will not solve the original problem but rather a modified problem based on the made calculation. According to a fourth implementation of the system according to the first aspect or any one of the preceding implementations of the first aspect, the problem is either a minimum cost flow (MCF) problem or a network utility maximization (NUM) problem.

Thereby, the problem can consist in minimizing the sum of the costs of flow over the links in the case of the MCF problem or maximizing the total utility as defined by "∑U^f( ^f)", where U^f is a concave function and ^f is the demand of the commodity f, in the case of the NUM problem. This latter formulation allows the consideration of a large number of problems, such as the congestion and admission control, the fairness among the commodities, the energy optimization and so on.

According to a fifth implementation of the system according to the fourth implementation of the first aspect when the problem is a MCF problem, the problem is solved using either a column generation algorithm or a simplex algorithm or a backpressure algorithm or an interior point algorithm.

Thereby, standard algorithms can be used to locally solve the MCF problem.

According to a sixth implementation of the system according to the fourth implementation of the first aspect when the problem is a NUM problem, the problem is solved using a local convex optimization algorithm.

Thereby, standard algorithms can be used to locally solve the NUM problem.

According to a seventh implementation of the system according to the fifth implementation of the first aspect, the MCF problem depends on a local determination of Lagrange multipliers.

Thereby, any arising flow conservation constraints at the borders of the neighboring clusters can be relaxed in order to solve the MCF problem with intra-cluster paths. The Lagrange multiplier can represent the price per unit of flow for deviating from the flow conservation at a border link. According to an eighth implementation of the system according to the seventh implementation of the first aspect, the exchange of the sequence of messages between each SDN controller is iteratively repeated until reaching a convergence of the Lagrange multipliers towards optimal Lagrange multipliers.

Thanks to the iteration, the Lagrangian multipliers can be updated and converge towards the optimal Lagrange multipliers.

The above object is also solved in accordance with a second aspect.

According to the second aspect, the invention relates to a software-defined networking (SDN) controller for computing a solution to a problem within a communication network, the SDN controller being split into a plurality of parts. The SDN controller comprises a plurality of computing devices configured to compute the solution by solving the problem at a respective part of the SDN controller, each part being assigned to a respective computing device, and a messaging module configured to exchange a sequence of messages between each computing device amongst the plurality of computing devices, wherein the solution is based on the sequence of messages exchanged between each computing device.

Thereby, a global problem is solved using several computing devices, none of which has a global view of the SDN controller. Indeed, each computing device has a local view of the SDN controller, namely an intra-part view of the SDN controller. Thus, each computing device solves an equivalent local problem and brings a solution to it by finding, for example, some paths in the case of a MCF problem. Owing to the exchanged messages between each computing device associated to a respective part, the solution to the original problem can be reached by finding, for example, the entirety of the paths in the case of a MCF problem.

According to a first implementation of the SDN controller according to the second aspect, each computing device comprises a respective problem solver configured to compute the solution by locally solving the problem, a respective coordination module configured to compute the sequence of messages using some information from the respective problem solver and the remaining problem solvers, and a respective driver module configured to interface the coordination module and the problem solver.

The above object is also solved in accordance with a third aspect.

According to the third aspect, the invention relates to a system for computing a solution to a problem within a communication network, the communication network being split into a plurality of clusters. The system comprises the system according to the first aspect, in which each SDN controller is as specified according to the second aspect.

The above object is also solved in accordance with a fourth aspect.

According to the fourth aspect, the invention relates to a method for computing a solution to a problem within a communication network, the communication network being split into a plurality of clusters. The method comprises the steps of computing the solution by solving the problem at each respective cluster, and exchanging a sequence of messages between each respective cluster amongst the plurality of clusters, wherein the solution is based on the sequence of messages exchanged between each cluster.

The above object is also solved in accordance with a fifth aspect.

According to the fifth aspect, the invention relates to a computer program comprising a program code for performing the method according to the fourth aspect when executed on a computer.

Thereby, the method can be performed in an automatic and repeatable manner.

The computer program can be performed by the above apparatus. The apparatus can be

programmably arranged to perform the computer program. More specifically, it should be noted that the above apparatus may be implemented based on a discrete hardware circuitry with discrete hardware components, integrated chips or arrangements of chip modules, or based on a signal processing device or chip controlled by a software routine or program stored in a memory, written on a computer-readable medium or downloaded from a network such as the internet.

It shall further be understood that a preferred embodiment of the invention can also be any combination of the dependent claims or above embodiments with the respective independent claim.

These and other aspects of the invention will be apparent and elucidated with reference to the embodiments described hereinafter.

BRIEF DESCRIPTION OF THE DRAWINGS

In the following detailed portion of the present disclosure, the invention will be explained in more detail with reference to the exemplary embodiments shown in the drawings, in which:

Fig. 1 shows a vertical (a) and horizontal (b) approach with access to a distributed database system (DDBS) wherein each part of the network is controlled by a single SDN controller;

Fig. 2 shows a distributed SDN architecture 100 with multiple controllers arranged in a flat topology;

Fig. 3 shows a distributed SDN controller architecture 200 within a clustered communication network according to an embodiment of the present invention;

Fig. 4 shows an algorithmic flow chart describing the steps of obtaining the optimal Lagrange multipliers; and Fig. 5 shows a centralized SDN controller architecture 300 according to an embodiment of the present invention.

Identical reference signs are used for identical or at least functionally equivalent features.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

Fig. 3 shows a distributed SDN controller architecture 200 within a clustered communication network according to an embodiment of the present invention.

The depicted distributed SDN controller architecture 200 comprises a plurality of SDN controllers (denoted by SDN controller 1 and SDN controller 2) whose number is limited in the present embodiment to two for clarity reasons only, and a messaging module configured to exchange a sequence of messages between each SDN controller amongst the plurality of SDN controllers. The communication network is split into a plurality of clusters, for example, through a clustering algorithm, and each cluster is assigned to a respective SDN controller, which has thereby a local view of the global communication network. Each SDN controller comprises a respective computing device (CE), such as a computer system, a server system, a virtual machine (VM) and a central processing unit (CPU) core in the case of a multi-core architecture, and a respective south-bound interface. Through its respective south-bound interface, each SDN controller controls a plurality of routing devices, such as routers and switches, located in its respective cluster. Each computing device (CE) comprises a respective coordination module, a respective driver module and a respective problem solver configured to solve a problem, such as a minimum cost flow (MCF) problem (also named minimum cost multicommodity flow problem) and a network utility maximization (NUM) problem. Each driver module is configured to interface the respective coordination module and the respective problem solver through a set of rules.

The plurality of SDN controllers is configured together to compute a solution to an original problem, while none of the SDN controllers has a global view of the communication network. Indeed, each SDN controller is configured to solve an equivalent local problem by reducing the original problem at each respective cluster. The solution is based on the sequence of messages exchanged between each SDN controller through the messaging module using a respective interface (a), which interfaces the messaging module and the respective coordination module. Each problem solver is configured to provide the computed solution, and each coordination module is configured to compute the sequence of messages to be exchanged between each SDN controller using some information from its respective problem solver and the remaining problem solvers.

In the exemplary case of a MCF problem, the messages exchanged between, for example, two SDN controllers A (SDNA) and B (SDNB) can contain a set of identifiers for network elements (nodes or links) at the interface between SDNA and SDNB, a set of identifiers for commodities, a set of queue (i.e., Lagrangian multiplier) updates for the networks elements and the cited extended commodities, and an information about the time periods covered by the updates. As regards the set of identifiers for commodities, it can also be enlarged with some information about, for example, different stages of service (in the case of node inclusion, service chaining, multi-domain constraints, and so on), different shared risk link groups (S LGs) encountered and different values or range of cumulative constraints (delay, hop counts, and so on).

In the exemplary case of a MCF problem, the driver module of, for example, the SDN controller A (SDNA) can feed the MCF problem solver with an MCF problem modified by:

- adding, for each extended commodity, a virtual destination; - adding virtual links incoming to this virtual destination from all the interfaces of SDNA, and from the real destination if it is inside SDNA;

- setting the cost of these links to the queue value maintained for this extended commodity and interface;

- adding a virtual source for each extended commodity; - adding virtual links outgoing from this virtual source towards all the interfaces of SDNA, and towards each real source of the commodity that is inside SDNA; and

- setting the cost of these links to minus the queue value maintained for this extended commodity and interface. An alternate implementation requires MCF solvers able to deal with multiple sources and multiple destinations for each commodity and commodity-dependent costs. Such an alternate

implementation would not require adding virtual sources/destinations and associated virtual links, but would rather consider the set of incoming interface edges plus any source for the commodity inside the cluster as the source for an extended commodity, and the set of outgoing interface edges plus destination of the commodity if inside the cluster as the destination for an extended

commodity. It would also modify the costs on the interface edges in a commodity-dependent manner.

In the exemplary case of a MCF problem, the coordination module of, for example, SDNA can take the flow solution of the MCF problem solver at the interfaces of SDNA from the driver module, possibly apply a non-decreasing function to it, then form messages of the type described above and send them to the relevant neighboring SDN controllers, receive messages from the neighboring SDN controllers, combine them into a unique queue value per extended commodity and per interface by applying the non-decreasing function, and pass them to the driver module.

In the following, the fundamental theory behind the present invention to solve a problem is described in the exemplary case of a MCF problem. The communication network is assumed to be already split into K clusters, each cluster being assigned to a respective SDN controller, and the links that traverse two different clusters are called "border links". However, in the case where the communication network is still entire, it shall be split into several parts or clusters. Thus, the present invention is complemented with the aforementioned clustering algorithm whose goal is to split the communication network into K clusters. The proposed clustering algorithm seeks to make several parts of the communication network as equal in size as possible, which allows the computation time inside each cluster to be equalized, and to make the border links as small as possible. To that extent, let us consider the balance metric (B) for a partition of the network into K clusters, which is given by the relationship:

B(K) = max_{(i, j)} cut(k_i, k_j)/min_i | k_i | (1)

where K = {k_l, k_2, k_K}. This balance metric (B) shows how balanced is the partition K, and the most balanced partition K* will be given by the relationship:

K* = min_K B(K) (2)

The solution to this problem can then be approximated with the standard k-means algorithm.

Starting from the path formulation of a MCF problem in the case of a centralized SDN controller architecture, which is given by the following formulation:

where p is a path, f is the commodity allocated to the path p, c_p is the total cost of the path p corresponding to the sum of costs of all links in the path p, X_p ^f is the optimization variable that assigns some flows over the path p for the commodity f, _s ^f is the generated flow, which is equal to the demand of commodity f when s is a source node for this commodity f and equal to zero otherwise (knowing that a commodity may have multiple sources in our formulation), μ_θ is the capacity of the link e, and S^f is the set of sources of commodity f (which can be restricted to a single node or not). The goal is to find the correct paths and optimization variables X_p ^f such that the total cost of the flow is minimized. The standard way of solving such a problem is to use linear

programming methods, such as the "column generation" method and the "interior-point" method, which empirically work well but only for a network of nodes not exceeding one thousand (i.e., 1000).

Based on the above path formulation of an original MCF problem and the quoted linear

programming methods, the present invention in the case of our distributed SDN controller architecture 200 considers a modified MCF problem based on the original MCF problem using paths that are entirely contained inside single clusters. This modified problem requires introducing conservation constraints to make sure the value of the flows on the border links are preserved between the different clusters involved. Afterwards, the flow conservation constraints are relaxed and a Lagrangian function L(X, Θ), which can be entirely decomposed between each cluster and wherein the Lagrangian multipliers Θ represent the price per unit of flow for deviating from the flow conservation at the border link, is then obtained. Depending on these values Θ and the cluster congestion, each cluster may decide to deviate from flow agreements at the borders as long as the cost saved in this way is larger than the penalty imposed by the prices. The benefit of this relaxation is that the prices can be initialized and that the SDN controllers can afterwards try to allocate flows exploring the good inter-cluster paths and reaching a consensus.

Minimizing the intra-cluster Lagrangian function corresponds to a formulation of the intra-cluster problem as follows:

111111

where 9^f is the Lagrangian multiplier Θ for the commodity f, A_p9^f is the difference between the Lagrangian multipliers at the last edge of the path segment p and at its first edge (any of the two may be zero if the corresponding edge is not a border edge), E(K) is the set of edges of cluster K, is the virtual source for commodity f in cluster K, |X./ is the sum of the flow values X_p ^f for the path segments p leaving from the virtual source s' via its outgoing virtual edge towards a source s of commodity f which belongs to cluster K (intuitively, it is the amount of flow for commodity f actually entering the network at source s, as opposed to flow entering the cluster from another cluster), _s ^f is the amount of flow for commodity f that we have to carry from source node s, S^f is the set of source nodes of commodity f, V(K) is the set of vertices of cluster K, and P^f(K) is the set of all the acyclic paths contained in cluster K and which are valid for the commodity f, i.e., they connect the virtual source and the associated virtual destination. This is a local MCF problem that depends on the parameters Θ. Given the parameters, the local SDN controller can solve this problem using standard sparse algorithms, such as the column generation, locally. Owing to the sparsity property, the computation efficiency can be optimized while saving memory size. If the parameters are set equal to the optimal Lagrangian multipliers, denoted by Θ*, then the optimal solution of the dual of the global MCF problem can be obtained, which corresponds to the optimal solution of the global (i.e., original) MCF problem due to the strong duality. Hence, given the optimal Lagrangian multipliers, each SDN controller can solve the local MCF problem to find a cluster routing that guarantees the overall global optimality of the MCF problem. The optimal Lagrangian multipliers Θ* can be found by a sequence of messages exchanged between the SDN controllers acting as agents in order to reach agreements of flow routing on the cluster border links and by the way to minimize the global routing cost. In this context, the present invention suggests a distributed subgradient (DSA) algorithm to achieve the optimal global routing solution, and alternatively, an extension of the DSA algorithm through a proximal parallel alternate direction of multipliers (ADMM) algorithm (hereafter denoted by PPA algorithm), which further improves the convergence in the networks with numerous border links due to sophisticated convex optimization techniques.

In the DSA algorithm, the Lagrangian multipliers Θ shall be updated in an iterative manner in order to converge towards the optimal Lagrangian multipliers Θ*. Thus, we compute the subgradient updates 0e as follows:

which guarantees a logarithmic convergence for a border edge going from the cluster κ^" to the cluster

To compute these updates, the present invention requires the neighboring values of flow to be obtained using messaging. Thus, the message exchanged at the iteration t from an i-th SDN controller (SDNi) towards a j-th SDN controller (SDNj) is a vector of real values with size

COMMODITIES x INTERFACES, and values equal to∑ X_p ^f for each interface. In the PPA algorithm, the present invention can make use of augmented Lagrangian functions instead of normal Lagrangian functions in order to make the global convergence of the Lagrangian multipliers Θ faster even though at the cost of harder intra-cluster problems. In that case, the obtained intra- cluster problem at iteration t can be formulated as follows:

where most of the symbols are defined in the above relationship (4), δΚ is the set of interface edges e leaving from cluster K towards another cluster, A_eY^f is the difference in total flow for the commodity f between the two clusters the interface edge e connects (refer to equation (5) for a detailed expression), A_tY_e ^f(K) is the difference between the total amount of flow for the commodity f on the interface edge e at the current iteration and at the previous iteration (all the variables are implicitly indexed by t, but only this term involves the value of variables at a different iteration than t), γ is a fixed step-size coefficient.

Thus, the local MCF problem is no longer a linear program (LP) but has become a more general convex problem, in particular a quadratic program, which can be solved by any methods for centralized convex flow problems or by specific methods for quadratic flow problems, while ensuring a faster global convergence. The Lagrangian multiplier updates at the iteration t are similar to the previous case as found in equation (5) (implemented with the prescribed step-size γ) and are given for each cluster by the relationship:

The convergence towards the optimal Lagrangian multipliers Θ* can then be obtained after a certain number of iterations.

Finally, the algorithm that will be basically used in the present invention is depicted in the flow chart of Fig. 4 in the case of the i-th SDN controller (SDNi). At the step of the so-called Update-routine, which runs continuously or sporadically at each call of the flow chart, the latest messages (9(j)) from other SDN controllers (j = 1, C) are received at SDNi and the costs c(t) are appropriately updated. At the step of the so-called Local_MCF(c(t)), the updated costs c(t) are received and the fractional MCF problem for the network of the local cluster with the updated costs c(t) at the interfaces can be solved by standard methods using, for example, the column generation algorithm, the simplex algorithm or the backpressure algorithm. At the step of the so-called Compute_multipliers_routine, the local solution to the fractional MCF problem is received and the Lagrange multipliers (9(i)) are computed at the interfaces of SDNi and transmitted in the form of messages (9(i)) towards the other SDN controllers. If the computed Lagrangian multipliers (9(i)) are sufficiently accurate the solution is then output, otherwise an iteration is requested to recalculate and optimize the Lagrangian multipliers (9(i)).

In summary, the MCF problem depends on a local determination of Lagrange multipliers (Θ), which can converge towards optimal Lagrange multipliers (Θ*) by iteratively repeating the exchange of the sequence of messages between each SDN controller.

In an embodiment, the present invention can extend the MCF problem to the NUM problem. To this extent, instead of minimizing the sum of the costs of flow over the links as defined by "∑f,_pX_Pc_p" in the formulation (3), the NUM problem is formulated as to maximize the total utility as defined by "∑U^f( ^f)", where U^f is a concave function and ^f is the demand of the commodity f. Thereby, a large number of problems, such as the congestion and admission control, the fairness among the commodities and the energy optimization, can be considered. Thus, the present invention directly applies to the network utility maximization (NUM) with the difference that the intra-cluster problem is no longer a local MCF problem, but rather a local convex optimization problem, which can be solved with standard convex optimization techniques. In an embodiment, the present invention can introduce constraints, such as an additive delay, S LG constraints, backup paths and so on. Two scenarios can then occur according to whether the problem remains a linear program (LP) or becomes an integer linear program (ILP). In the former scenario (LP), the same messaging with respect to the case where no constraint is introduced can be used and only the local problem is to be adapted. For the local problem, the constrained problem can be solved by the standard methods. As there is no duality gap and as long as the local problem is optimally solved, our invention can then yield the globally optimal solution. In the latter scenario (ILP), there may be an integrality gap and our invention may no longer provide the optimal solution. Despite it, our invention can either use the value of its solution as a lower bound to the constrained MCF problem or project infeasible solutions to the feasible set in order to get a good approximation. Nevertheless, the second option has the disadvantage with respect to the first one to involve a projection operation depending on the problem and to be not always straightforward.

Although the present invention has been described based on fractional flows, it can also be applied to an integral flow, namely a flow that cannot be split into fractional flows, with the aim of yielding the optimal LP relaxation of the problem. Conventional rounding techniques, such as the randomized rounding technique proposed by: P. R P. Raghavan and C. D. Tompson, "Randomized rounding: A technique for provably good algorithms and algorithmic proofs", Combinatorica, vol. 7, no. 4, pp. 365-374, 1987, can be then used to obtain the integral flow.

Fig. 5 shows a centralized SDN controller architecture 300 according to an embodiment of the present invention.

The approach described for the distributed SDN controller architecture 200 of Fig. 3 applies to the depicted centralized SDN controller architecture 300, which structurally differs from the distributed SDN controller architecture 200 in that the SDN controller is now split into a plurality of parts and each part is assigned to a respective computing device (denoted by CE1, CE2, CEn), and which functionally differs from the distributed SDN controller architecture in that the above-mentioned local sparse algorithms are no longer distributed but rather parallelized. Thus, the plurality of computing devices (CE1, CE2, CEn) is configured to compute the solution through a respective problem solver as above-mentioned by locally solving the problem at a respective part of the SDN controller. In another embodiment (not depicted), the distributed SDN controller architecture 200 of Fig. 3 and the centralized SDN controller architecture 300 of Fig. 5 can be merged into a hybrid configuration.

In summary, the present invention relates to systems, an apparatus and a method for computing a solution to an optimization problem within a communication network through the use of algorithms. The network uses a SDN architecture either with multiple controllers and a messaging protocol distributed amongst the multiple controllers or with a centralized controller and a messaging protocol distributed amongst multiple computing devices, each SDN controller comprising a respective computing device. In the former option, the network is split into a plurality of clusters assigned each to a respective SDN controller and the problem is locally solved at each respective cluster. In the latter option, the SDN controller is split into a plurality of parts assigned each to a respective computing device and the problem is locally solved at each respective part. Thus, the network optimization can be achieved by computing cluster-boundary or part-boundary values and using a local sparse algorithm based on those computed values in order to solve a modified problem rather than the original problem.

It should be emphasized that the present invention allows to a solver to be re-used in the case of a centralized MCF problem so that there is no need to design a new special solver for solving the intra- cluster modified MCF problems. Thus, this applies only to the embodiments in which the nature of the intra-cluster problem is not modified, for example, from a linear problem into a quadratic problem.

While the invention has been illustrated and described in detail in the drawings and the foregoing description, such illustration and description are to be considered illustrative or exemplary and not restrictive. The invention is not limited to the disclosed embodiments. From reading the present disclosure, other modifications will be apparent to a person skilled in the art. Such modifications may involve other features, which are already known in the art and may be used instead of or in addition to features already described herein. The invention has been described in conjunction with various embodiments herein. However, other variations to the disclosed embodiments can be understood and effected by those skilled in the art in practicing the claimed invention, from a study of the drawings, the disclosure and the appended claims. In the claims, the word "comprising" does not exclude other elements or steps, and the indefinite article "a" or "an" does not exclude a plurality. A single processor or other unit may fulfill the functions of several items recited in the claims. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage. A computer program may be stored/distributed on a suitable medium, such as an optical storage medium or a solid-state medium supplied together with or as part of other hardware, but may also be distributed in other forms, such as via the Internet or other wired or wireless telecommunication systems.

Although the present invention has been described with reference to specific features and embodiments thereof, it is evident that various modifications and combinations can be made thereto without departing from the spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded simply as an illustration of the invention as defined by the appended claims, and are contemplated to cover any and all modifications, variations, combinations or equivalents that fall within the scope of the present invention.

Claims

1. A system for computing a solution to a problem within a communication network, the communication network being split into a plurality of clusters, the system comprising: a plurality of software-defined networking (SDN) controllers configured to compute the solution by solving the problem at each respective cluster, each cluster being assigned to a respective SDN controller; and a messaging module configured to exchange a sequence of messages between each SDN controller amongst the plurality of SDN controllers, wherein: - the solution is based on the sequence of messages exchanged between each SDN controller.

2. The system of claim 1, wherein each SDN controller comprises: a respective computing device (CE), the respective computing device (CE) communicating with each other computing device (CE) through the messaging module.

3. The system of claim 2, wherein each computing device (CE) comprises: a respective problem solver configured to provide the computed solution; a respective coordination module configured to compute the sequence of messages using some information from the respective problem solver and the remaining problem solvers; and - a respective driver module (a) configured to interface the respective coordination module and the respective problem solver.

4. The system of claim 3, wherein the respective driver module (a) provides the respective problem solver with a modified problem, which is defined by the respective driver module (a).

5. The system of any one of the preceding claims, wherein the problem is either a minimum cost flow (MCF) problem or a network utility maximization (NUM) problem.

6. The system of claim 5 when the problem is a MCF problem, wherein the problem is solved using either a column generation algorithm or a simplex algorithm or a backpressure algorithm or an interior point algorithm.

7. The system of claim 5 when the problem is a NUM problem, wherein the problem is solved using a local convex optimization algorithm.

8. The system of claim 6, wherein the MCF problem depends on a local determination of Lagrange multipliers (Θ).

9. The system of claim 8, wherein the exchange of the sequence of messages between each SDN controller is iteratively repeated until reaching a convergence of the Lagrange multipliers (Θ) towards optimal Lagrange multipliers (Θ*).

10. A software-defined networking (SDN) controller for computing a solution to a problem within a communication network, the SDN controller being split into a plurality of parts, the SDN controller comprising: a plurality of computing devices (CE) configured to compute the solution by solving the problem at a respective part of the SDN controller, each part being assigned to a respective computing device (CE); and a messaging module configured to exchange a sequence of messages between each computing device (CE) amongst the plurality of computing devices (CE), wherein: - the solution is based on the sequence of messages exchanged between each computing device (CE).

The SDN controller of claim 10, wherein each computing device (CE) comprises a respective problem solver configured to compute the solution by locally solving the problem a respective coordination module configured to compute the sequence of messages using some information from the respective problem solver and the remaining problem solvers; and a respective driver module configured to interface the coordination module and the problem solver.

12. A system for computing a solution to a problem within a communication network, the communication network being split into a plurality of clusters, the system comprising: the system of claim 1, in which each software-defined networking (SDN) controller is as specified in claim 10.

13. A method for computing a solution to a problem within a communication network, the communication network being split into a plurality of clusters, the method comprising: computing the solution by solving the problem at each respective cluster; and exchanging a sequence of messages between each respective cluster amongst the plurality of clusters, wherein: the solution is based on the sequence of messages exchanged between each cluster.

14. A computer program comprising a program code for performing the method according to claim 13 when executed on a computer.