Service placement in ad hoc networks [Elektronische Ressource] / vorgelegt von Georg Wittenburg

Georg Wittenburg

Sujets

• Informatik

Informations

• Publié par: freie_universitat_berlin
• Publié le: 01 janvier 2010
• Nombre de lectures: 14
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

Doctoral Dissertation
Service Placement in Ad Hoc Networks
Dissertation zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.) am Fachbereich
Mathematik und Informatik der Freien Universität Berlin
vorgelegt von
Georg Wittenburg, M.Sc.
Datum der Disputation: 27. September 2010
Gutachter: Prof. Dr.-Ing. habil. Jochen H. Schiller
Prof. habil. Andreas Mitschele-ThielAbstract
Service 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 imple-
mentation 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.
Inthiswork, weproposetheSPi serviceplacementframeworkasanovelapproachtoservice
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 andGCMI 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.Zusammenfassung
Die Diensterbringung in Ad-hoc-Netzen stellt eine Herausforderung dar, weil in diesen
Netzen die drahtlose Kommunikation per Funk sowie möglicherweise auch die Heterogenität
und Mobilität der am Netz teilnehmenden Geräte neue Fragestellungen aufwerfen. Um die
Leistungsfähigkeit des Netzes, über das die dienstanbietenden mit den dienstnehmenden
Knoten kommunizieren, zu optimieren, gilt es, die logische Netztopologie kontinuierlich
an sowohl externe als auch interne Faktoren anzupassen. Als Beispiele für diese Faktoren
sind die Konnektivität, die Mobilität, und die Abwanderungsrate der Knoten einerseits,
beziehungsweise das Kommunikationsverhalten und das Dienstanfragevolumen andererseits
zu nennen. In letzter Zeit wurde vermehrt vorgeschlagen, jene Knoten dynamisch auszu-
wählen, die im Netz Dienste auf Anwendungsebene für die anderen Knoten erbringen sollen.
Der Dienstbegriff umfasst in diesem Zusammenhang sowohl infrastrukturellen Dienste wie
beispielsweise das Domain Name System (DNS) als auch benutzerorientierte Dienste wie
das World Wide Web (WWW).
Die Auswahl einer optimalen Menge von dienstanbietenden Knoten angesichts der derzei-
tigen Nachfrage nach dem Dienst und der aktuellen Netztopologie wird Dienstplatzierung
(engl. „service placement“) genannt. Dienstplatzierung in Ad-hoc-Netzen umfasst folgende
Kernfragen: Wie viele Instanzen eines Dienstes sollten im Netz zur Verfügung stehen,
um gemeinsam die Anfragen der dienstnehmenden Knoten abzuarbeiten; wo sollten diese
Dienstinstanzen platziert werden, d.h. welche Knoten sind für die verteilte Diensterbringung
am besten geeignet; und wann sollte eine Dienstkonfiguration angepasst werden. Hierbei
sind die Dienstinstanzen eines verteilt arbeitenden Dienstes exakte Kopien der Software-
komponente, die den Dienst erbringt — einschließlich des ausführbaren Programms und
der Anwendungsdaten. Die Menge der Knoten, die jeweils eine Dienstinstanz beherbergen,
wird Dienstkonfiguration genannt. Eine gute Dienstkonfiguration verbessert die Qualität der
Diensterbringung gemäß anwendungsspezifischer Metriken bei gleichzeitiger Verminderung
der Netzlast. Der wesentliche Vorteil einer aktiven Dienstplatzierung in Ad-hoc-Netzen ist
die Möglichkeit zur kontinuierlichen Anpassung der Dienstkonfiguration zur Laufzeit.
In dieser Arbeit beschreiben wir das SPi Service Placement Framework, einen neuartigen
Ansatz zur Dienstplatzierung in Ad-hoc-Netzen. Das SPi Framework nutzt die wechselseiti-
gen Abhängigkeiten zwischen Dienstplatzierung, Dienstauffindung und dem Routing vonDienstanfragen aus, um den erforderlichen Signalisierungsverkehr zwischen den Knoten zu
minimieren. Wir beschreiben außerdem die Graph Cost/Single Instance (GCSI) und Graph
Cost/Multiple Instances (GCMI) Dienstplatzierungsalgorithmen. Das SPi Framework verwen-
det diese Algorithmen zur Optimierung der Anzahl und der Position von Dienstinstanzen
basierend auf Nutzungsstatistiken und einer partiellen, aus Routingdaten gewonnenen
Netztopologie. Die GCSI und GCMI Dienstplatzierungsalgorithmen benötigen hierfür nur
minimale Kenntnisse über den zu platzierenden Dienst. Sie gehen über den aktuellen Stand
der Technik hinaus, indem sie explizit die Kommunikation zwischen den Dienstinstanzen
berücksichtigen, die erforderlich ist, um den globalen Zustand des Dienstes über Instan-
zen hinweg synchron zu halten. Darüber hinaus beziehen die beiden Algorithmen bei der
Berechnung des optimalen Zeitpunktes zur Anpassung einer Dienstkonfiguration die zu
erwartende Netzlast der Maßnahmen ein, die für diese Anpassung erforderlich sind.
UnsereImplementierungdesSPi FrameworksaufeinereigensfürdiesenZweckentwickelten
Softwareschnittstelle ermöglicht es uns, das System mit Hilfe einer Vielzahl von Evaluations-
plattformen zu bewerten — einschließlich gängiger Betriebssysteme und Netzsimulatoren.
Wir untersuchen die Eigenschaften unseres Dienstplatzierungssystems und vergleichen es mit
anderen Ansätzen in Simulationen, Emulationen und Experimenten auf einem drahtlosen
IEEE 802.11 Testbed. Die Auswertung dieser Experimente zeigt, dass das SPi Service Pla-
cement Framework und seine Dienstplatzierungsalgorithmen – insbesondere GCMI – in der
Lage sind, in einer Vielzahl von Szenarien bessere Dienstkonfigurationen als andere Ansätze
zu finden. Daraus resultiert eine Verbesserung der Verlässlichkeit und des Laufzeitverhaltens
des platzierten Dienstes, während gleichzeitig weniger Datenverkehr im Netz für dessen
Erbringung erforderlich ist. Darüber hinaus zeigen unsere Experimente, dass eine verteilte
Diensterbringung mit aktiver Die