09 September 2014

Protocols are distributed optimizer

In an amazing paper, F. Kelly, has shown that TCP/IP protocol is a perfect example of optimizer: its objective is to maximize the sum of source utilities (as functions of rates) with constraints on resources. And actually, each variant of congestion control protocol can be seen as a distributed algorithm maximizing a particular utility function. The exact shape of the utility function can be reverse engineered from the given protocol. Similarly, Border Gateway Protocols (BGPs) can be seen as a solution to the Stable Path Problem, and contention-based Medium Access Control (MAC) protocols as a game-theoretic selfish utility maximization. Other utility functions could be User satisfaction (e.g. User-generated pricing following end-to-end principle), resource allocation efficiency or different network economics fairness.

Then, modeling networks as a sets of optimizers, means considering management-control based on interacting controllers maximizing a combination (e.g. weighted sum) or an aggregation (e.g. in multiplicative form) of multiple utility functions. Or, alternatively, we may say that management-control should look for the network Pareto optimality (a state of allocation of resources in which it is impossible to make any one individual better off without making at least one individual worse off: the term is from Vilfredo Pareto (1848–1923), an Italian economist who used the concept in his studies of economic efficiency). But this would mean taking a different perspective in designing and operating networks: i.e., looking for a vertical and horizontal network decomposition and solving problems with multi-objective optimization. In fact, protocols are distributed optimizer !


In a SDN, control intelligence could be (logically) centralized in software-based controllers. Said controllers could provide visibility and control over the network, they can ensure that access control, routing, traffic engineering, QoS, security, and other policies are enforced consistently across the network infrastructures (whilst keeping in mind the CAP Theorem). The interactions of these (centralized vs distributed) controllers will allow managing and optimizing a SDN according to certain policies. Extend this concepts to all layers functions, up to L7 (i.e., consider NFV) and this seems paving the way to look at future networks in a different way, systemically decomposing them and letting ecosystems of resources being aggregated and managed by combinations of multi-objective optimization solvers.