Algorithmic Game Theory

Analysing Strategic Behaviour in the Context of Network Function Virtualisation

Algorithmic game theory studies scenarios involving the interaction of rational agents. It is concerned with statements regarding the results of strategic behaviour when agents are in competition with each other and develops algorithms which are based on these results. Network Function Virtualisation is an example for a scenario here, which also occurs in the context of the Collaborative Research Centre 901 “On-The-Fly-Computing”.

Algorithmic game theory is concerned with issues relating to the results of strategic actions of autonomous actors. We investigate the computational complexity of outcome forecasts for the distributed allocation of resources, e.g. capacities in networks or the computing powers of servers. Furthermore, we examine the behaviour of dynamic adjustment processes when agents repeatedly respond to the actions of other agents: What time do such processes have? Do they converge to stable states? How inefficient are these systems?

Network Function Virtualization as an Example

The concept of Network Function Virtualisation (NFV) decouples network functions, such as DNS, firewall, load balancer, etc. from the proprietary hardware. Then, the services can be operated by software. Equivalent to the widespread server virtualisation, network components are deployed where they are needed, making it easy to dynamically adapt to changes in the requirements. The operation of a service usually requires several components, which can be positioned at the best possible locations in a network.

Different components of a service deployed to the network

Nowadays, the allocation of service components to network nodes is usually optimised centrally and the provider of the underlying infrastructure places the respective components. However, this is often not easy to implement. The infrastructure provider does not know the very heterogeneous interests of the service providers. They have different system requirements and various objective functions. For one group, latency is more important and, for another, bandwidth, depending on the services they offer.

If we now see the entire system as a game, we let the service providers act as strategic players. Everyone can choose the desired locations for their components according to their own goals. The resources of a node are shared fairly among the users. The quality of the solution is then, of course, of special interest. For this purpose, a central optimisation solution is compared with the result of the game theoretical solution.

In a second approach, we do not let the service providers act on their own, but rather use their dynamics as distributed algorithms for our system. Due to the size and complexity of thescenarios, a  central computation is often not possible or useful. By shifting the computation to the network, better performance can be achieved and the quality can be guaranteed byusing the mentioned comparison between the central optimum and the local solution.

Components of different services interact in the network

Supported by:

  • DFG Collaborative Research Centre 901 “On-TheFly Computing”, subproject A3