Service placement in ad hoc networks
Wittenburg, Georg

HaupttitelService placement in ad hoc networks
TitelvarianteDienstplatzierung in Ad-hoc-Netzen
AutorWittenburg, Georg
Geburtsort: Berlin
GutachterProf. Dr.-Ing. habil. Jochen H. Schiller
weitere GutachterProf. Dr.-Ing. habil. Andreas Mitschele-Thiel
Freie SchlagwörterService Placement; Ad Hoc Networks; Service Placement System; SPi; SPi Service Placement Framework; Service Placement Algorithm
DDC003 Systeme
ZusammenfassungService provisioning in ad hoc networks is challenging given the difficulties of communicating over a wireless channel and the potential heterogeneity and mobility of the devices that form the network. In order to optimize the performance of the network over which a service host provides a service to client nodes, it is necessary to continuously adapt the logical network topology to both external (e.g., wireless connectivity, mobility, churn) and internal (e.g., communication patterns, service demand) factors. Recent proposals advocate that nodes should dynamically choose which nodes in the network are to provide application-level services to other nodes. Services in this context range from infrastructural services such as the Domain Name System (DNS) to user-oriented services such as the World Wide Web (WWW).

Service placement is the process of selecting an optimal set of nodes to host the implementation of a service in light of a given service demand and network topology. The main questions addressed by service placement are: How many instances of the same service should be available in the network and cooperate to process clients' service requests; where these service instances should be placed, i.e., which nodes are best suited for hosting them; and when to adapt the current service configuration. The service instances of a distributively operating service are exact copies of the software component that provides the service, including both the executable binary and the application-level data. The set of nodes that host a service instance is referred to as the service configuration. A good service configuration increases the performance of a service according to application-specific quality metrics, while at the same time potentially reducing the overall network load. The key advantage of active service placement in ad hoc networks is that it allows for the service configuration to be adapted continuously at run time.

In this work, we propose the SPi service placement framework as a novel approach to service placement in ad hoc networks. The SPi framework takes advantage of the interdependencies between service placement, service discovery and the routing of service requests to minimize signaling overhead. We also propose the Graph Cost / Single Instance (GCSI) and the Graph Cost / Multiple Instances (GCMI) placement algorithms. The SPi framework employs these algorithms to optimize the number and the location of service instances based on usage statistics and a partial network topology derived from routing information. The GCSI and GCMI placement algorithms only require minimal knowledge about the service they are tasked with placing in the network. They are novel in that they take the communication between service instances into account which is required to synchronize the global state of the service. Furthermore, when calculating the optimal timing of their placement decisions, the two algorithms explicitly consider the overhead of the actions required for implementing changes to the current service configuration.

Our implementation of the SPi framework on top of a special low-level API allows us to run the framework on a variety of evaluation platforms including major operating systems and network simulation tools. We examine the properties of our approach to service placement and compare it with other recent proposals in simulations, emulations, and real-world experiments on an IEEE 802.11 wireless testbed. The results of this evaluation show that the SPi service placement framework and our placement algorithms, in particular GCMI, are able to find service configurations that are superior across a variety of scenarios to those found by other approaches. As a consequence, service provisioning improves significantly with regard to its reliability and timeliness, while at the same time causing less network traffic. Furthermore, our results show that distributed service provisioning with active service placement -- as implemented in SPi -- generally outperforms services that are implemented in a traditional client/server architecture. From these results we conclude that our approach to service provisioning in ad hoc networks is a viable alternative to established architectures.
Inhaltsverzeichnis1 Introduction
1.1 Service Placement in Ad Hoc Networks
1.1.1 Motivation
1.1.2 Problem Statement
1.1.3 Clarification of Terms
1.1.4 Assumptions
1.1.5 Potential Applications
1.2 Contributions
1.2.1 Research Questions
1.2.2 Proposed Solution
1.2.3 Scope
1.3 Structure of this Work

2 Background
2.1 Overview
2.2 Ad Hoc Networks
2.2.1 Types of Ad Hoc Networks
2.2.2 Standards and Current Approaches
2.3 Facility Location Theory
2.3.1 The p-median Problem
2.3.2 The Uncapacitated Facility Location Problem
2.3.3 Applicability to the Service Placement Problem
2.4 Current Approaches to Service Placement
2.4.1 Design Space
2.4.2 General-purpose Service Placement
2.4.3 Service Placement of Composite Services
2.4.4 Clustering
2.4.5 Related Work in Other Fields
2.4.6 Evaluation
2.4.7 Candidates for Quantitative Comparison
2.5 Summary

3 Methodology
3.1 Overview
3.2 Portability Across Evaluation Methods
3.2.1 Software Interface
3.2.2 Integration into POSIX-compliant Operating Systems
3.2.3 Integration into the Network Simulator ns-2
3.3 Comparison with Other Approaches
3.3.1 Requirements and Evaluation Criteria
3.3.2 Exemplary Frameworks
3.3.3 Comparison
3.4 Summary

4 The SPi Service Placement Framework
4.1 Overview
4.2 Design Considerations and Rationale
4.3 Components
4.3.1 Routing Component
4.3.2 Service Discovery Component
4.3.3 Service Placement Middleware
4.4 Service Replication and Migration
4.4.1 Service States
4.4.2 Service Replication Protocol
4.4.3 Cost of Service Replication and Migration
4.4.4 Optimizations
4.4.5 Preliminary Evaluation
4.5 Summary

5 SPi Service Placement Algorithms
5.1 Overview
5.2 Service Provisioning Cost
5.2.1 Rationale and Alternatives
5.2.2 Modeling Synchronization Requirements
5.2.3 Formalization
5.3 Adapting the Service Configuration
5.3.1 Formalization of Adaptation Actions
5.3.2 Service Adaptation Cost
5.4 The Graph Cost / Single Instance Algorithm
5.4.1 Algorithm
5.4.2 Implementation Considerations
5.5 The Graph Cost / Multiple Instances Algorithm
5.5.1 Algorithmic Background and Rationale
5.5.2 Service Provisioning Cost Revisited
5.5.3 Algorithm
5.5.4 Preliminary Evaluation
5.5.5 Implementation Considerations
5.6 Deciding on the Timing of Service Adaptations
5.6.1 Motivation and Preconsiderations
5.6.2 Service Adaptation Condition
5.6.3 Discussion
5.7 Example
5.8 Summary

6 Evaluation
6.1 Overview
6.2 Metrics
6.3 Evaluation Setup
6.3.1 Simulation Setup
6.3.2 Emulation Setup
6.3.3 Testbed Setup
6.4 Placement of Centralized Services
6.5 Placement of Distributed Services
6.6 Service Placement under Varying Service Demand
6.7 Service Placement under Varying Synchronization Requirements
6.8 Service Placement under Varying Link Quality
6.9 Service Placement in Reality
6.10 Summary

7 Conclusion
7.1 Contributions
7.2 Future Work
7.2.1 Extensions of the Architecture
7.2.2 Refinements of the Implementation
7.2.3 Security
7.3 Concluding Remarks

A Evaluation of the DYMO Routing Protocol
A.1 Setup
A.2 Evaluation
A.2.1 Multiple Sources / Single Destination
A.2.2 Multiple Sources / Multiple Destinations

B Evaluation of Current Approaches to Service Placement
B.1 Placement of Centralized Services
B.2 Placement of Distributed Services

C Comparison of Evaluation Methods
C.1 Differences in Setup
C.2 Comparison

List of Figures
List of Tables
PDF-Datei von FUDISS_thesis_000000019398
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
SeitenzahlIV, 219 S.
Fachbereich/EinrichtungFB Mathematik und Informatik
Rechte Nutzungsbedingungen
Tag der Disputation27.09.2010
Erstellt am22.10.2010 - 11:22:30
Letzte Änderung13.12.2010 - 13:34:32
Statische URLhttp://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000019398