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:
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.
In order to evaluate different approaches to service placement, we have created the SPi framework as an evaluation platform for service placement algorithms.
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.
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.
We have implemented both placement algorithms on top of the SPi framework and evaluated them using simulations, emulations, and the Distributed Embedded Systems Testbed.
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.
Contact: Georg Wittenburg