Network-aware service placement and selection algorithms on large-scale overlay networks

Currently many service providers offer their services on a private and proprietary hard- and software infrastructure. These infrastructures often share many similarities. Hence we believe a generic service management architecture, that allows service providers to offer a large array of different services on a single infrastructure or multiple providers to offer their services cooperatively, would provide many advantages over current silo-based approaches. Additionally, by allowing the distributed service management components to cooperate in a peer-to-peer overlay network, scalability and resilience of the system could be greatly improved.In this paper we propose an optimal algorithm, based on an integer linear programming (ILP) formulation, and several heuristics to support such a generic overlay-based service management architecture. More specifically, we propose algorithms for dynamically allocating server and network resources to a set of services and selecting a suitable service instance for each client. Service instances are placed on a set of servers, taking into account server resource constraints (e.g. CPU and memory). Unlike existing algorithms for this problem, those proposed in this paper also support service level agreements (SLAs), which take the form of Quality of Service demands such as transmission latency constraints and bandwidth requirements. The optimisation goal is to maximise the percentage of satisfied demand (answered requests) and minimise the total number of required overlay servers, while satisfying the SLAs and resource constraints. Additionally, we propose an extension that allows the algorithms to find overlay routing paths to improve the transmission latency for latency-sensitive services.Extensive simulations were performed to evaluate the performance and scalability of the heuristics. They showed that in many cases the heuristics perform close to optimal and they scale well in terms of network size.