Optimistische Replikation in mobilen ad-hoc Netzen

Abstract

Die vorliegende Arbeit untersucht die Verwendung von optimistischen Replikationsverfahren in mobilen ad-hoc Netzen (MANETs). Aufgrund der Mobilität und der Unzuverlässigkeit der Teilnehmer weisen MANETs eine hohe Dynamik auf, was zu langen Verbindungsunterbrechungen zwischen den Teilnehmern führen kann. Die Verwendung von optimistischen Replikationsverfahren gewährleistet trotz der Verbindungsunterbrechungen eine hohe Verfügbarkeit der Daten. Es ergibt sich jedoch durch kausal parallel ausgeführte Änderungsoperationen auf den gleichen Daten das Problem von Schreibkonflikten. Da es bisher nur wenig Erfahrung mit dem Einsatz von Replikationsverfahren in MANET-Szenarien gibt, wurde in dieser Arbeit ein optimistisches Replikationssystem entwickelt und untersucht, wie sich die Eigenschaften mobiler ad-hoc Netze auf dieses System auswirken. Die Methoden des Systems wurden für den Einsatz in MANETs entworfen und angepasst, da viele bisherige Replikationssysteme nicht für die Verwendung in MANETs geeignet sind. Um die Mobilität der MANET-Szenarien zu berücksichtigen, wurden zunächst Bewegungsmodelle und Datenverteilungsprotokolle für MANETs betrachtet. Das entwickelte Area Graph-based Bewegungsmodell modelliert sowohl die makroskopische als auch die mikroskopische Bewegung der mobilen Knoten und ist dadurch realistischer als Bewegungsmodelle, die sich nur auf die Modellierung der Makro- oder der Mikrobewegung beschränken. Die entwickelten Datenverteilungsprotokolle, adaptives probabilistisches Fluten und adaptive Synchronisation, wurden mit Hilfe von Netzsimulatoren mit anderen Protokollen verglichen. Die Ergebnisse zeigen, dass die beiden Protokolle weniger Netzlast verursachen als vergleichbare Ansätze. Das Konfliktlösungs- und -erkennungsverfahren unseres Replikationsansatzes basiert auf den kausalen Abhängigkeiten der Transaktionen. Die Abhängigkeiten werden im Replikationssystem von einer Datenstruktur, dem sogenannten Vorgängergraph, verwaltet. Um die verwendeten Replikationsverfahren möglichst realistisch zu testen, wurde das prototypische Replikationssystem Symore implementiert und in kleinen Szenarien auf Laptops und PDAs getestet. Ebenso wurden auf dem Replikationssystem aufbauend zwei Applikationen (verteiltes Puzzle und verteiltes Wiki) für mobile Geräte (Laptop, PDA) erfolgreich umgesetzt. Abschließend wurden die verwendeten Replikationsmethoden sowohl experimentell, mit Hilfe von Emulationen, als auch analytisch bewertet. Als Zielgröße wurde dabei die relative Anzahl der in Konflikt stehenden Transaktionen betrachtet. Die Ergebnisse der Bewertung zeigen, dass sich in den meisten der untersuchten MANET-Szenarien nur eine geringe Anzahl von Konflikten und somit auch weniger Transaktionsabbrüche ergaben. Insgesamt eignet sich das entwickelte Replikationssystem somit für den Einsatz in kleinen bis mittelgroßen MANET- Szenarien von bis zu 40 Teilnehmern.

Small computing devices combined with wireless networking technologies nowadays give rise to new kinds of mobile networks which feature different characteristics than conventional wired networks. The question arises whether conventional networking techniques are suitable to support applications to be deployed in such mobile networks. This work addresses the aforementioned question by evaluating the application of optimistic replication techniques to mobile ad-hoc networks (MANETs). Due to the mobility and unreliability of mobile nodes, MANETs are highly dynamic networks. To guarantee high data availability in the presence of broken network connections, optimistic replication techniques can be used. Here, a replication node updates the data first locally and then sends it to the other participants. The downside of this approach is that concurrent updates can occur causing write conflicts. So far, experience of replication in MANETs is limited, therefore we developed a mobile replication system and evaluated its performance in mobile ad-hoc networks. The techniques of the replication system have been designed or adapted for use in MANETs because conventional replication systems are not suitable. MANET scenarios are motivated by the lack of infrastructure, e.g., due to a disaster. Thus, it is not reasonable to use a central replication server, for example, connected to the mobile devices via UMTS or GPRS. To take the mobility of MANET scenarios into account, we considered mobility models and data dissemination protocols. We developed the Area Graph-based Mobility Model that considers the macroscopic as well as the microscopic motion of mobile nodes. We also developed two dissemination protocols, an adaptive push protocol and an adaptive pull protocol. Tests with simulated MANET scenarios show that both protocols produce less network load than existing dissemination protocols. The conflict detection and resolution techniques of our approach are based on the dependencies of the transactions. The dependencies are managed by the Predecessor Graph: a data structure enhancing a predecessor list. Furthermore, the data structure also allows commutative transactions. As a proof of concept, we developed the prototype replication system Symore and test it in small scenarios on PDAs and laptops. A mobile wiki and a mobile puzzle game have also been successfully implemented based on Symore. Finally, we evaluated these replication techniques experimentally (with emulations), as well as analytically by the number of conflicting transactions. The results show a small number of conflicting transactions for the majority of the tested scenarios and thus a small number of transaction aborts as well. In conclusion, we present an optimistic replication approach for mobile ad-hoc networks and demonstrate that it is suitable for use in small to medium-sized MANET scenarios with up to 40 participants.