Springe direkt zu Inhalt

SPi - Service Placement in Ad Hoc Networks

Taking an application-centric view on ad hoc networks, cooperation between devices is structured by application-level clients and servers, i.e., certain nodes requesting services provided by other nodes. This gives rise to the question in how far the performance of the network can be increased by intelligently selecting which nodes are to host a particular service. The process of identifying the appropriate nodes to act as servers is referred to as service placement and invesigated using our SPi service placement framework. More information is available on the SPi homepage.

Brief Overview of Service Placement

The problem of service placement in ad hoc networks can be stated as follows: Given a physical network topology and service demands of client nodes, adapt the number and location of services in the network over time such that the service demands are met at a minimal cost. The cost function may include metrics such as network traffic, energy expenditure or service-dependant Quality of Service (QoS) metrics (availability, latency, etc.).

The key questions to be answered as part of solving the service placement problem are thus as follows:

  • Where in the network are services or service instances of a distributed service to be placed?
  • How many service instances are required for cost optimal operation?
  • When should the current configuration of services and service instances be adapted?

Our contribution to this field of research consists of the SPi service placement framework, an evaluation platform for placement algorithms, and the Graph Cost / Single Instance (GCSI) and Graph Cost / Multiple Instances (GCMI) placement algorithms.


SPi Service Placement Framework

In order to evaluate different approaches to service placement, we have created the SPi framework as an evaluation platform for service placement algorithms.


SPi Service Placement Framework

The three main components of the SPi service placement framework are the components for service discovery and routing, and the service placement middleware. Within this middleware, we have implemented the core functionality of network mapping and service replication as well as several placement algorithms. The framework is portable across different evaluation platforms ranging from network simulators over standard PC hardware to embedded devices.

SPi Service Placement Algorithms

Our approach to service placement encompasses two placement algorithms, one for centralized services with a single service instance, and one for distributed service with a variable number of service instances to be determined by the placement algorithm.

  • Graph Cost / Single Instance (GCSI): A placement algorithm for centralized services that migrates the service instance to the node that minimizes the service provisioning cost (based on usage statistics and a network map) as soon as the expected payoff exceeds the migration cost.
  • Graph Cost / Multiple Instances (GCMI): A placement algorithm for distributed services that adapts the service configuration, i.e., the number and the location of the service instances, in order to minimize the service provisioning cost whenever the expected payoff exceeds the adaptation cost.

We have implemented both placement algorithms on top of the SPi framework and evaluated them using simulations, emulations, and the Distributed Embedded Systems Testbed.

Example

This is an animation of service placement in a simulated wireless ad hoc network employing the SPi service placement framework and its Graph Cost / Multiple Instances placement algorithm (GCMI). It shows how multiple instances of a service are created depending on regional service demand, and how this results in an overall reduction of network traffic.

 

 

The initial service instance is created on node 22 (lower right-hand corner). Client nodes highlighted in green (and red when transmitting) locate this service instance and begin issuing service requests. In response to this service demand, the service configuration is adapted by replicating and migrating service instances. At 0:25, the initial service instance on node 22 is shut down and new service instances are created on the more suitably placed nodes 2, 12, 32, and 70. This process is repeated several times (at 1:21, 2:23, 3:08, 3:23, and 4:06) as the regional service demand changes. As a result, the clients' service request packets have to traverse less hops before reaching a service instance. Thereby, the overall network traffic is reduced while the quality of the service as perceived by the client nodes increases at the same time.

Resources


Relevant Publications

  • Georg Wittenburg. Service Placement in Ad Hoc Networks. PhD thesis, Department of Mathematics and Computer Science, Freie Universität Berlin, Berlin, Germany, October 2010. (available online)
  • Georg Wittenburg and Jochen Schiller. Service Placement in Ad Hoc Networks. In PIK - Praxis der Informationsverarbeitung und Kommunikation, 33(1):21-25, January 2010.
  • Georg Wittenburg and Jochen Schiller. Service Placement in Ad Hoc Networks. Kick-off Meeting GI/ITG KuVS Fachgespräch "NGN Service Delivery Platforms & Service Overlay Networks", Berlin, Germany, November 2009.
  • Georg Wittenburg and Jochen Schiller. A Survey of Current Directions in Service Placement in Mobile Ad-hoc Networks. In Proceedings of the Sixth Annual IEEE International Conference on Pervasive Computing and Communications (PerCom '08), Hong Kong, China, March 2008.


Contact: Georg Wittenburg