% ****************************************************************************
% ****************************************************************************
% ****************************************************************************
\part{Fehlertoleranz}
\label{part:Fehlertoleranz}

% ****************************************************************************
\chapter{Grundlagen der Fehlertoleranz}
\label{sec:Grundlagen_Fehlertoleranz}

\sidenote{Systeme und Komponenten} Ein \emph{System} ist ein identifizierbarer Mechanismus, der sich durch sein Verhalten sowie durch seine Schnittstellen zur Außenwelt auszeichnet \cite{an81_fault}. Es enthält eine oder mehrere \emph{Komponenten}, wobei eine Komponente auch wieder ein System sein kann (in diesem Fall wird auch von einem Sub-System gesprochen). So ist das Gespann aus {\trans} und Proxy ein (Sub-)System, während {\trans} und Proxy einzeln betrachtet jeweils als Komponenten betrachtet werden.\footnote{Natürlich ist ein {\trans} bzw. ein Proxy für sich auch wieder ein System, jedoch ist die \emph{innere} Architektur dieser Systeme für die Betrachtung nicht von Bedeutung.}

\sidenote{Bedeutung der Fehlertoleranz} Keine Komponente eines Systems hat eine unendliche Lebenserwartung. Alterungserscheinungen, überschrittene Fertigungstoleranzen, Programmierfehler, Kommunikations-Übertragungsfehler und auch aufgezehrte Energiereserven sind mögliche Ursachen, die zu einem Versagen {\bzw} zum Ausfall von Komponenten führen können. Mit der Komplexität von Systemen steigt die Wahrscheinlichkeit, dass Fehler vorhanden sind, die Störungen hervorrufen. Je mehr funktionale Abhängigkeiten zwischen den Komponenten eines Systems bestehen, desto größer ist die Wahrscheinlichkeit, dass Störungen größere Bereiche eines Systems -- bis hin zum gesamten System -- beeinflussen oder gar zum Versagen führen. Dies wird insbesondere bei \emph{Seriensystemen} deutlich: Ist $R_i(t)$ die Zuverlässigkeit einer Komponente eines Systems, das aus $n$ Komponenten besteht, so ergibt sich die Gesamtzuverlässigkeit des Systems durch das Produkt der Zuverlässigkeiten der einzelnen Komponenten \cite{ja98_fault_tolerance}:

$$R_{series}(t) = \prod\limits_{i=1}^{n} R_i(t)$$

\sidenote{Design-inhärente und dedizierte Fehlertoleranzverfahren} Damit ist die Zuverlässigkeit bzw. Zeit bis zum Ausfall eines Seriensystems entsprechend geringer als die Zuverlässigkeiten der Einzelkomponenten. Dieser Zusammenhang ist insbesondere wichtig, da es sich bei einem System bestehend aus einem {\trans} und dem zugehörigen Proxy um ein Seriensystem handelt. Aus diesem Grund ist \emph{Fehlertoleranz} ein wichtiger Aspekt bei der Entwicklung Proxy-basierter Systeme. Viele Fehlertoleranzmerkmale eines Systems sind bereits \emph{Design-inhärent} -- so wird am Beispiel des Sindrion-Systems bei Ausfall eines Proxys automatisch ein neuer Proxy gestartet -- doch kann auf diese Weise keine umfassende Fehlertoleranz erreicht werden, da der Ausfall eines Proxys sich unmittelbar auf weitere Komponenten auswirken und \emph{Inkonsistenzen} hervorrufen kann. Daher sind weitere Protokolle und Verfahren notwendig, die als \emph{dedizierte Fehlertoleranz-Erweiterungen} betrachtet werden können und in diesem Teil der vorliegenden Arbeit diskutiert werden.

% ----------------------------------------------------------------------------
\section{Fehler, Störung und Versagen}
\label{sec:Fehler_Stoerung_Versagen}

\sidenote{Zusammenhang der Begriffe} Im Folgenden werden im Zusammenhang mit Fehlertoleranz die Begriffe \emph{Fehler}, \emph{Störung} und \emph{Versagen} in Anlehnung an die englischen Begriffen \emph{Fault}, \emph{Error} und \emph{Failure} verwendet \cite{ja98_fault_tolerance}. Die jeweiligen Bedeutungen der Begriffe werden in Abbildung~\ref{fig:Fehler_Stoerung_Versagen} veranschaulicht: Von Versagen (Failure) sprechen wir dann, wenn ein System oder eine Komponente sich nicht mehr spezifikationsgemäß verhält. Ein extremer Fall des Versagens einer Komponente ist ihr kompletter Ausfall. Man kann allerdings nur dann unmittelbar auf das bevorstehende Versagen einer Komponente oder eines Systems schließen, wenn zuvor eine Störung (Error) bemerkt wurde. Die Störung ist damit der Teil des Systemzustandes, der zum Versagen des Systems bzw. der Komponente führen kann (aber nicht muss). Das Versagen selbst ist erst observierbar, nachdem es eingetreten ist und auch nur, sofern eine Instanz das Verhalten der Komponente oder des Systems überwacht. Das Versagen eines Subsystems oder einer Komponente kann sich wiederum als Störung im übergeordneten System bemerkbar machen. Unmittelbare Ursache von Störungen sind Fehler (Faults).

\sidenote{Beispiele} Zwei Beispiele: Ein Computerprogramm kann Fehler enthalten ("`Bugs"' in der Dateizugriffsroutine), die sich im Betrieb in einer Störung manifestieren (Datei nicht zugreifbar). Wird die Störung nicht angemessen behandelt ({\zb} Laden von Default-Werten), kann sie zum Versagen des Programms (Ausfall bzw. Absturz) führen. Aber auch, wenn ein Mobiltelefon ausfällt (Versagen), weil sein Akku keine Energie mehr liefert (Störung), ist im weitesten Sinne ein Fehler die Ursache, da der Akku überbeansprucht bzw. nicht rechtzeitig geladen wurde (menschliches Versagen).

\begin{figure}[htbp]
  \vspace{1cm}
  \begin{center}
    \includegraphics[width=9.5cm, angle=0]{fig/Fehler_Stoerung_Versagen.pdf}
    \setzeBreite
    \caption{Zusammenhang von \emph{Fehler}, \emph{Störung} und \emph{Versagen}.}
    \label{fig:Fehler_Stoerung_Versagen}
  \end{center}
\end{figure}

\sidenote{Kaschieren von Störungen} Damit liegt die Ursache von Störungen bzw. vom Versagen in der Präsenz von Fehlern. Generell sind Fehler nicht gänzlich zu vermeiden, auch wenn man stets im Vorfeld bemüht ist, ihre Anzahl gering zu halten. Hinzu kommt, dass Fehler mitunter erst nach einer gewissen Zeit {\zb} aufgrund von Alterungserscheinungen auftreten. Die Auftrittswahrscheinlichkeit dieser Art von Fehlern kann {\zb} durch \emph{präventiven Austausch} von Komponenten vor Ablauf der erwarteten Lebensdauer reduziert werden.

Doch selbst wenn Fehler nicht gänzlich vermieden werden können, ist es jedoch möglich, mit den Auswirkungen der Fehler, also den Störungen, umzugehen, um Versagen zu vermeiden. Da man Störungen erst observieren kann, \emph{nachdem} sie aufgetreten sind, ist die einzige Reaktionsmöglichkeit, sie zu \emph{kaschieren}. Dies bedeutet, dass eine Störung für die übergeordneten Systemstrukturen transparent gemacht wird, indem ihre Auswirkungen abgefangen {\bzw} eingedämmt werden. Natürlich kann (und sollte) dies auch ein Beheben der zugrunde liegenden Fehler beinhalten.

% ----------------------------------------------------------------------------
\section{Grundbausteine fehlertoleranter Systeme}
\label{sec:Fehlertoleranzbausteine}

\sidenote{Ebenenmodell} Verfahren zum Aufbau fehlertoleranter Systeme können in ein Ebenenmodell eingeordnet werden, wie es in Abbildung~\ref{fig:Fehlertoleranzebenen} dargestellt ist. Fehlertoleranzverfahren sind oberhalb der Infrastrukturebene angeordnet und erweitern diese um entsprechende Fehlertoleranzmerkmale. Im Wesentlichen können drei allgemeine Ansätze als Beitrag zur Fehlertoleranz unterschieden werden:

\begin{itemize}

\item \sfb Migration von Code und Daten \normalfont\\ Wird ein drohendes Versagen eines Gerätes erkannt, so wird die Funktionalität des Gerätes (wenn möglich zur Laufzeit) auf ein alternatives Gerät migriert.

\item \sfb Anwendung von {\rr}-Verfahren \normalfont\\ Das System wird befähigt, beim Versagen einzelner Komponenten einen gültigen Zustand "`vor"' Auftreten der Störung wieder anzufahren.

\item \sfb Redundante Haltung von Code und Daten \normalfont\\ Sowohl Code als auch Daten können redundant im System vorgehalten werden, um bei Ausfall einer Komponente auf eine bereitstehende \emph{Schattenkopie} umzuschalten.

\end{itemize}

\sidenote{Grundbausteine} Die genannten Fehlertoleranzverfahren sind auf die Verfügbarkeit bestimmter Systemmerkmale angewiesen -- im Folgenden als \emph{Grundbausteine} bezeichnet \cite{ja98_fault_tolerance}. Diese sind:

\begin{itemize}

\item \sfb Fail-Stop-Prozesse \normalfont\\ Typischerweise stellt eine Komponente bei Auftritt einer Störung ihre Arbeit nicht unmittelbar ein (Fail-Stop). Eher verhält sie sich auf eine arbitrate Weise, die der Spezifikation der Komponente zwar eindeutig widerspricht, jedoch mitunter nur schwer als Versagen zu erkennen ist. Fehlertoleranzverfahren sind allerdings darauf angewiesen, dass ein Versagen zuverlässig und in endlicher Zeit (d.h. möglichst unmittelbar) erkannt wird. Um ein arbitrates Verhalten von Komponenten auf ein Fail-Stop-Verhalten abzubilden, existieren sog. \emph{Byzantine-Agreement-Protokolle}~\cite{ja98_fault_tolerance}. Dabei werden die Aussagen verschiedener möglicherweise gestörter Komponenten miteinander verglichen, um das Versagen einer dieser Komponenten zu erkennen. Ein weiterer gängiger Ansatz zur Realisierung von Fail-Stop-Prozessen sind \emph{Exception-Mechanismen}, wie sie von modernen Programmiersprachen wie Java oder den Sprachen der .Net-Familie verwendet werden.\goodbreak

\item \sfb {\stst} \normalfont\\ {\rr}-Verfahren sind auf die Verfügbarkeit eines ausfallsicheren Datenspeichers (\stst) angewiesen. Derartige Speichermedien stehen typischerweise in Form von RAID-Systemen zur Verfügung. Je nach Applikation kann aber auch eine einfache Festplatte oder ein anderer permanenter Datenspeicher als {\stst} betrachtet werden.

\item \sfb Zuverlässige Kommunikation \normalfont\\ Fehlertoleranzverfahren sind {\idr} darauf angewiesen, dass Kommunikationspartner zuverlässig erreicht werden und keinerlei Daten beim Austausch von Nachrichten unbemerkt verloren gehen. Zwar können physikalische Übertragungskanäle keine zuverlässige Übertragung garantieren, doch können hierzu entsprechende Protokolle eingesetzt werden.\footnote{Einer der bekanntesten Vertreter ist das \emph{Transmission Control Protocol (TCP)}, das zuverlässige Übertragungen in IP-basierten Netzwerken bereitstellt.}

%\enlargethispage{.5cm}

\item \sfb Synchrone Uhren \normalfont\\ Für viele Verfahren ist eine Synchronisation der Uhren der Komponenten eines verteilten Systems erforderlich. Hierfür existieren eine Reihe von Verfahren \cite{el03_synchronization, si04_synchronization}. Da allgemein keine absolute Uhrensynchronisation erreicht werden kann, werden {\idr} Verfahren angewendet, die gewährleisten, dass die Uhren des Systems maximal um einen definierten Wert "`auseinanderlaufen"'.

\end{itemize}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=12cm,angle=0]{fig/Fehlertoleranzebenen.pdf}
    \setzeBreite
    \caption{Ebenen der Fehlertoleranz.}
    \label{fig:Fehlertoleranzebenen}
  \end{center}
\end{figure}

% ****************************************************************************
\chapter{Konzeptionelle Überlegungen zur Fehlertoleranz} \label{sec:Konzeption_Fehlertoleranz}

\sidenote{Übersicht} In diesem Kapitel wird die Beschaffenheit des im ersten Teil der Arbeit entwickelten Systems untersucht und modelliert. Basierend auf den gewonnenen Erkenntnissen werden schließlich Ansätze aufgezeigt, mit denen das System um dedizierte Fehlertoleranzmerkmale erweitert werden kann.

% ----------------------------------------------------------------------------
\section{Systemmodell}
\label{sec:Systemmodell}

\sidenote{Einleitung} Bevor konkrete Fehlertoleranzkonzepte für das im ersten Teil der Arbeit vorgestellte System entwickelt werden können, müssen Modelle definiert werden, die den folgenden Überlegungen als Grundlage dienen. Diese Modelle sind ein \emph{Infrastrukturmodell}, das die Topologie des Systems beschreibt, sowie ein \emph{Fehlermodell}, das definiert, welche Ausprägungen von Fehlern bzw. Störungen im System erwartet werden.

\sidenote{Komponenten und Topologie} Im Folgenden betrachten wir das verteilte System $S = (T, P, C)$, das sich zusammensetzt aus den {\trans}n $T = \{t_1,\ldots,t_n\}$, den Proxies $P = \{p_1,\ldots,p_n\}$, sowie den {\cp}s $C = \{c_1,\ldots,c_n\}$. Die Topologie dieses Systems ist in Abbildung~\ref{fig:Systemmodell} dargestellt: Zu jedem {\trans} $t$ existiert ein Proxy $p$, während {\cp}s an sich in beliebiger Anzahl vorhanden sein können. Die Proxies werden von den {\am}n $AM = \{am_1,\ldots,am_m\}$ ausgeführt und sind untereinander verbunden durch Kommunikationsverbindungen $V_{pp} \subseteq P^2$, die durch die Middleware Universal Plug and Play bereitgestellt werden. Weiterhin existieren Kommunikationsverbindungen $V_{cp} \subseteq C \times P$ zwischen {\cp}s und Proxies, die ebenfalls Middleware-basiert sind. Zuletzt existieren Kommunikationsverbindungen $V_{pt} \subseteq \{(p_i, l_i)\}$ zwischen jeweils einem Proxy und dem jeweils zugehörigen {\trans}.\footnote{Diese direkten Verbindungen zwischen {\trans}n und Proxies sind \emph{logische} Verbindungen. Es ist durchaus denkbar, dass bzgl. der Vermittlungsschicht eine vermaschte Netztopologie zugrunde liegt.}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=13cm,angle=0]{fig/Systemmodell.pdf}
    \setzeBreite
    \caption{Darstellung des Systemmodells.}
    \label{fig:Systemmodell}
  \end{center}
\end{figure}

\sidenote{Charakteristik eines Message-Passing Systems} Bei dem betrachteten System handelt es sich um ein \emph{Message-Passing System}. In jedem {\trans} $t_i$, jedem Proxy $p_i$, sowie jedem Control Point $c_i$ können zwei Arten von Ereignissen auftreten: \emph{Sendeereignisse} und \emph{Empfangsereignisse}. Diese Ereignisse können den jeweiligen Zustand der Komponenten $t_i$, $p_i$ und $c_i$ verändern. Damit ist der Zustand einer Komponente definiert durch ihren Anfangszustand und der Sequenz aus Kommunika\-tionsereignissen. Sende- und Empfangsereignisse haben eine Reihenfolge, die auf Grundlage von Lamport's \emph{Happened-Before Relation} \cite{la78_events} bestimmt wird. Zwischen einem Empfangs- und einem Sendeereignis ist das Verhalten der Komponenten deterministisch -- es gilt damit die \emph{Piecewise Deterministic Assumption (PWD)} \cite{el02_rollback}.

\sidenote{Sindrion-Specials} Jeder {\trans} stellt neben seinem Proxy einen auf die Applikation des {\trans}s zugeschnittenen \emph{Specific {\cp}} (siehe Kapitel \ref{sec:Einleitung}) bereit. Neben einer Anpassung an die Applikation kann der Specific {\cp} auch spezielle Erweiterungen, wie eine Unterstützung für {\rr}-Protokolle, enthalten. Transceiver können das System spontan verlassen und einen Standby-Modus betreten, um Energie zu sparen. In dieser Zeit bleibt der Proxy für seinen {\trans} aktiv und beantwortet Anfragen von {\cp}s sofern möglich.

\sidenote{Typische Verwendung des Systems} Ein weiteres Charakteristikum des betrachteten Systems ist seine typische Verwendung in \emph{In-Haus-Netzwerken}. Daraus ergibt sich, dass Nachrichten, die an {\trans} geschickt werden, üblicher Weise einfach aufgebaute Kommandonachrichten zur Steuerung von Geräten sind. Eine derartige Nachricht hat eine durchschnittliche Länge von 20 - 40 Bytes und besteht aus einem Kommando und einem einfachen Satz an Parametern.

% ----------------------------------------------------------------------------
\section{Verfügbarkeit der Grundbausteine}
\label{sec:Verfuegbarkeit_Grundbausteine}

Bezüglich der in Abschnitt \ref{sec:Fehlertoleranzbausteine} vorgestellten Bausteine für fehlertolerante Systeme gelten folgende Annahmen, die in Tabelle \ref{tab:Verfügbarkeit der Grundbausteine} zusammengefasst werden:

\begin{itemize}

\item \sidenote{Fail-Stop} Es wird davon ausgegangen, dass sämtliche Komponenten des betrachteten Systems dem \emph{Fail-Stop-Modell} entsprechen. Daher wird im Folgenden der Begriff "`Ausfall"' als Synonym für das Versagen einer Komponente verwendet.

\item \sidenote{\stst} In der Regel werden {\am} auf leistungsfähigen Hosts wie {\zb} PCs ausgeführt. Es wird daher vorausgesetzt, dass mindestens ein {\am} im System ein \emph{{\stst}} bereit stellt, das jeder Komponente des Systems zur Ablage von Daten zur Verfügung steht.\footnote{Hier wird ein Datenspeicher auf einer Festplatte als {\stst} betrachtet. In der Praxis kann auch ein RAID-System verwendet werden.}

\item \sidenote{Zuverlässige Kommunikation} Die Kommunikationsverbindungen $V_{pp}$, $V_{cp}$ und $V_{pt}$ werden als prinzipiell zuverlässig angenommen, da sie alle auf dem \emph{Transmission Control Protocol (TCP)} basieren. Zwar setzt die für $V_{pp}$ und $V_{cp}$ verwendete UPnP-Middleware auch das unzuverlässige \emph{User Datagram Protocol (UDP)} ein, doch nutzen die für den Austausch von Kontrollnachrichten und Ereignissen verwendeten Komponenten des UPnP-Stacks das TCP-Protokoll, wie in Abbildung~\ref{fig:UPnP-Stack_TCP} illustriert.%\footnote{UPnP SOAP-Actions setzten grundsätzlich auf TCP auf und können somit als zuverlässig angesehen werden. Events werden über das GENA (Generic Event Notification Architecture) Protokoll verschickt, das zum Teil auf UDP und zum Teil auf TCP aufsetzt. Allerdings wird für Event Registrations und Notifications TCP verwendet, womit UPnP Events ebenfalls als zuverlässig angesehen werden können~\cite{upnp_spec}.}

\item \sidenote{Synchrone Uhren} Eine Synchronisation von Uhren ist {\idr} nur mit viel Aufwand zu realisieren (Hardwareanforderungen an die Zeitgeber, Unterstützung von Synchronisationsprotokollen). Daher wird im Folgenden davon ausgegangen, dass synchrone Uhren im betrachteten System \emph{nicht} zur Verfügung stehen.

\end{itemize}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=9cm, angle=0]{fig/UPnP-Stack_Comm.pdf}
    \setzeBreite
    \caption[Zuverlässige Kommunikation über TCP.]{Für die Kommunikation auf Applikationsebene über SOAP und GENA verwendet UPnP das zuverlässige TCP-Protokoll.}
    \label{fig:UPnP-Stack_TCP}
  \end{center}
\end{figure}

\begin{table}[htbp]
\begin{center}
\begin{tabularx}{15cm}{p{3cm}lX}

  \toprule
  \rowcolor{dunkelgrau}
  \textbf{Grundbaustein} & \textbf{Verfügbarkeit} & \textbf{Anmerkung} \\
  \midrule

  \rowcolor{hellgrau1}
  Fail-stop-Verhalten & verfügbar & Wird als gegeben angenommen. Durch Java Exception-Modell unterstützt. \\

  \rowcolor{hellgrau2}
  {\stst} & verfügbar & Zum Beispiel UPnP-basierter {\stst}-Service denkbar. \\

  \rowcolor{hellgrau1}
  Zuverlässige Kommunikation  & verfügbar & UPnP verwendet für die wesentliche Kommunikation das TCP-Protokoll. \\

  \rowcolor{hellgrau2}
  Synchrone Uhren & nicht verfügbar & Nur aufwendig zu realisieren. \\
  \bottomrule

\end{tabularx}
\setzeBreite
\caption{Verfügbarkeit der Fehlertoleranz-Grundbausteine.}
\label{tab:Verfügbarkeit der Grundbausteine}
\end{center}
\end{table}

% ----------------------------------------------------------------------------
\section{Fehlermodell}
\label{Fehlermodell}

Im Folgenden wird diskutiert, welche Arten von Fehlern im betrachteten System auftreten können und welche Auswirkungen diese nach sich ziehen können. Folgende Ausfallszenarien werden im Fehlermodell berücksichtigt:

\begin{itemize}

  \item \sfb Ausfall des {\trans}s \normalfont\\ Der Ausfall des {\trans}s muss prinzipiell akzeptiert werden, da der {\trans} selbst kein fehlertolerantes System ist. Entsprechend dem \emph{Fail-Stop-Modell} wird bei Ausfall des {\trans}s $t_i$ der zugehörige Proxy $p_i$ automatisch beendet. Dieses Merkmal ist bereits Design-inhärent in der entwickelten Infrastruktur verankert und muss daher nicht durch dedizierte Verfahren erreicht werden.

  \item \sfb Ausfall des Proxys \normalfont\\ Ein Proxy $p_i$ kann als Folge des Ausfalls von $t_i$ beendet werden oder auch unabhängig von $t_i$ ausfallen. Wird $p_i$ als Folge des Ausfalls von $t_i$ beendet, so handelt es sich \emph{nicht} um eine Störung. Im anderen Fall wird der Proxy von dem selben oder einem anderen {\am} neu gestartet, sobald der Ausfall des Proxys detektiert wurde und der {\trans} seinen Zustand als \emph{ungebunden} signalisiert hat. Auch dieses Merkmal ist bereits Design-inhärent in der Infrastruktur vorhanden.\\Es ist jedoch möglich, dass mit dem Ausfall des Proxys Zustandsinformationen, die nur in $p_i$ und nicht in $t_i$ enthalten waren, verloren gehen. Sofern die Zustände von $t_i$ und $p_i$ abgeglichen wurden, bevor $p_i$ ausfällt, wird bei einem Neustart von $p_i$ der aktuelle Zustand automatisch von $t_i$ auf $p_i$ übertragen und ist somit mit dem Rest des Systems konsistent. Falls nicht, entstehen Inkonsistenzen zwischen den Zuständen der Kommunikationspartner von $p_i$, wie andere Proxies oder {\cp}s.

  \item \sfb Ausfall des {\am}s \normalfont\\ Wenn ein {\am} bzw. der Host, der den {\am} ausführt, ausfällt, sind davon sämtliche Proxies betroffen, die von diesem {\am} verwaltet bzw. auf dem Host ausgeführt werden. Im Prinzip handelt es sich also beim Ausfall eines {\am}s um einen mehrfachen Proxy-Ausfall. In einer solchen Situation greift derselbe Ansatz wie oben, wonach die betroffenen Proxies automatisch von anderen {\am}n neu gestartet werden. Natürlich besteht hier ebenfalls das Problem möglicher Inkonsistenzen beim Neustart der Proxies, sofern die Zustände mit den jeweiligen {\trans}n nicht abgeglichen wurden.

  \item \sfb Ausfall des {\cp}s \normalfont\\ Ein {\cp} kann prinzipiell jede Applikation sein, die den Dienst eines Proxys bzw. {\trans}s nutzt. Jede dieser Applikationen kann nach dem Fail-Stop-Modell ausfallen. Da {\cp}s jedoch per Definition lediglich Nutzer eines Dienstes sind, erzeugt ihr Ausfall keine weiteren Abhängigkeiten, wie es bei Ausfall eines Proxys der Fall wäre. Allerdings ist der {\cp} neben dem {\trans} in vielen Fällen eine Schnittstelle zur Außenwelt bzw. zum Benutzer. Daher ist es wichtig, dass ein nach einem Ausfall neu gestarteter {\cp} mit dem Rest des Systems konsistent ist. Es ist allerdings davon auszugehen, dass die Herstellung dieser Konsistenz von der verwendeten Middleware gewährleistet wird, da diese dafür sorgt, dass der Zustand der Dienstanbieter beim Start entsprechend abgefragt wird. Inkonsistenzen können jedoch dann entstehen, wenn die Applikation, die den {\cp} enthält, auch selbst wieder Dienstanbieter ist und applikationsspezifische Statusinformationen existieren, die bei einem Ausfall der Komponente verloren gehen.

  \item \sfb Ausfall von Kommunikationsverbindungen \normalfont\\ Im Prinzip kann jede Kommunikationsverbindung im System ausfallen. Im Folgenden gilt auch hier das Fail-Stop-Modell. Ferner wird der Ausfall einer Kommunikationsverbindung zwischen zwei Komponenten als Ausfall der sendenden Komponente betrachtet, wodurch der Ausfall von Kommunikationsverbindungen nicht gesondert behandelt werden muss.

\end{itemize}

\sidenote{Detektion von Fehlern und Verhalten} Wenn eine Komponente des Systems eine Nachricht an eine andere Komponente sendet, diese andere Komponente jedoch aufgrund einer Störung nicht antwortet, so wird der Verbindungsversuch nach einem Timeout abgebrochen. Erst in diesem Moment wird die Störung bemerkt. UPnP-basierte Komponenten des Systems, wie {\trans} und Proxies, realisieren über das Senden von Advertisements einen \emph{Heartbeat-Mechanismus}. Das heißt, eine ausgefallene UPnP-Komponente wird nach Ablauf ihres zuletzt gesendeten Advertisement automatisch bemerkt.

% ----------------------------------------------------------------------------
\section{Realisierungsansätze}
\label{sec:Realisierungsansaetze_Fehlertoleranz}

\sidenote{Analyse} Im Prinzip drehen sich die im vorherigen Abschnitt betrachteten Ausfallszenarien neben dem Ausfall von {\cp}s um den Ausfall von Proxies, da Proxies entweder eigenständig oder als Folge des Ausfalls ihres {\trans}s oder als Folge des Ausfalls ihres {\am}s ausfallen können. In manchen Fällen ist der drohende Ausfall von Proxies vorhersehbar und kann {\uu} vermieden werden. In vielen Fällen sind Ausfälle jedoch unvorhersehbar bzw. müssen hingenommen werden. Allerdings ist in diesen Fällen ein angemessener Umgang mit den Konsequenzen notwendig. Hierfür sind folgende Ansätze denkbar, die im Rahmen der vorliegenden Arbeit verfolgt wurden:

\begin{itemize}

\item \sfb Migration von Proxies \normalfont\\ Sofern ein drohender Ausfall eines Proxys erkannt wird -- {\zb}, wenn die Energiereserven des Hosts beinahe aufgebraucht sind oder die CPU- bzw. Speicherauslastung an eine vorgegebene Grenze stößt -- kann der Proxy zur Laufzeit auf einen anderen Host bzw. einen anderen {\am} \emph{migriert} werden.

\item \sfb {\rr} von Proxies und {\cp}s \normalfont\\ Sofern ein Proxy nicht durch Migration "`gerettet"' werden konnte, muss er im System neu gestartet werden. Hierbei ist essentiell, dass sich das Gesamtsystem nach den Neustart des Proxys wieder in einem konsistenten Zustand befindet. Um dies zu gewährleisten, können {\rr} Protokolle verwendet werden. Allerdings ist es wünschenswert, die {\trans} durch Anwendung von {\rr}-Verfahren nicht zusätzlich zu belasten. Im Idealfall braucht ein {\trans} das angewendete {\rr}-Protokoll selbst gar nicht unterstützen.

\end{itemize}

\sidenote{Scope der Arbeit} Die Migration von Proxies wird im folgenden Kapitel~\ref{sec:Migration} behandelt, während {\rr}-Verfahren in Kapitel~\ref{sec:Rollback-Recovery} untersucht werden. Darüber hinaus stehen weitere Ansätze zur Verfügung, die jedoch über den Rahmen der vorliegenden Arbeit hinaus gehen und nicht eingehend untersucht wurden:

\begin{itemize}

\item \sfb Transparenter Austausch von {\trans}n \normalfont\\ Wenn ein {\trans} ausfällt, kann der Ausfall {\uu} vom dahinter liegenden Proxy vor dem Rest des Systems für einen gewissen Zeitraum verborgen werden. Es ist denkbar, in der Zwischenzeit den {\trans} gegen ein gleichwertiges Gerät auszutauschen, {\bzw} auf ein alternatives Gerät umzuschalten. Anschließend muss der "`neue"' {\trans} mit dem Status des Proxys synchronisiert werden. Diese Möglichkeit ist allerdings stark applikationsabhängig. Weiterhin ist der Vorgang des Austauschs des {\trans} ein interner Vorgang im Subsystem bestehend aus Proxy und {\trans}. Daher kann dieser Vorgang nur schwer im Rahmen einer allgemeinen Lebenszyklusverwaltung von Proxies unterstützt werden.

\item \sfb Cloning von Proxies \normalfont\\ Eine zusätzliche {\bzw} zur Migration von Proxies alternative Möglichkeit besteht darin, redundante Kopien von Proxies auf anderen Hosts vorzuhalten. Allerdings ist hier speziell zu berücksichtigen, dass stets nur ein aktiver Proxy für die Kommunikation mit dem Transceiver zuständig sein kann. Ferner müssen geeignete Synchronisationsmechanismen angewendet werden, um den aktiven Proxy mit seinen Klonen abzugleichen \cite{pa03_sync}. Weiterhin ist der Ansatz des Cloning zu den anderen vorgestellten Verfahren orthogonal und kann als mögliche Erweiterung der vorliegenden Arbeit betrachtet werden.

\end{itemize}

% ****************************************************************************
\chapter{Migration von {\dproxies}}
\label{sec:Migration}

\sidenote{Übersicht} Im Rahmen der vorliegenden Arbeit wird die Migration von {\dproxies} als Mittel zur \emph{Fehlervermeidung} diskutiert. In diesem Kapitel werden die der Migration zugrundeliegenden Konzepte und Technologien vorgestellt. Es ist ferner eine Java-basierte Referenzimplementierung entstanden, deren Leistungsfähigkeit anhand von Messungen evaluiert wurde.

\sidenote{Grundvoraussetzung} Für eine erfolgreiche Anwendung von Proxy-Migration ist die Früherkennung von Ausfällen essentiell, da Proxies migriert werden müssen, \emph{bevor} ihr Host ausfällt. In vielen Fällen deutet sich ein drohender Ausfall frühzeitig an:

\enlargethispage{-.5cm}

\begin{itemize}

\item Die Ressourcen des Hosts des {\am}s erreichen eine kritische Stufe. So kann {\zb} die durchschnittliche CPU-Auslastung oder der zur Verfügung stehende Arbeitsspeicher in einem vorgegebenen Zeitfenster einen kritischen Wert erreichen. Ferner kann im {\am} eine Störung auftreten, die durch den Exception-Mechanismus abgefangen werden konnte, der {\am} sich jedoch in einem potentiell instabilen Zustand befindet.

\item Der Benutzer fährt den Host des {\am}s ordnungsgemäß herunter. Sobald der {\am} vom Betriebssystem das Signal zum Beenden erhält, kann er über einen \emph{Shutdown Hook}\footnote{Ein \emph{Shutdown Hook} ist ein Thread, der beim Beenden einer virtuellen Maschine automatisch ausgeführt wird und {\idr} Cleanup-Funktionen enthält.} einen Vorgang ausführen, der die momentan ausgeführten Proxies auf einen anderen Host "`evakuiert"'. Dieser Vorgang kann {\zb} auch in Gang gesetzt werden, wenn ein Host mit unterbrechungsfreier Stromversorgung (USV) bei einem Stromausfall das Signal zum Herunterfahren des Systems erhält.\footnote{Dies setzt natürlich voraus, dass die Netzwerkinfrastruktur nicht von dem Stromausfall betroffen oder selbst durch eine USV abgesichert ist.}

\end{itemize}

\sidenote{Weitere Möglichkeiten} Neben diesen einfachen Indizien bevorstehender Ausfälle sind auch komplexere Verfahren zur Früherkennung denkbar. So ist der Einsatz statistischer Verfahren möglich (Host wird regelmäßig zu einer bestimmten Uhrzeit herunter gefahren, die Belastung eines Hosts steigt zu bestimmten Zeiten aufgrund einer durchgeführten Datensicherung stark an, etc.). Darüber hinaus ist auch der Einsatz von \emph{Byzantine-Agreement-Protokollen} denkbar (siehe Abschnitt \ref{sec:Fehlertoleranzbausteine}), um ein arbitrates Verhalten eines fehlerhaften {\am}s zu erkennen. Allerdings müssen hierzu externe Überwachungsinstanzen eingesetzt werden, was den Implementierungsaufwand deutlich erhöht.

\sidenote{Migration} Sofern ein bevorstehender Ausfall des {\am}s erkannt wurde, können Proxies \emph{zur Laufzeit} auf einen anderen Host bzw. {\am} \emph{migriert} werden. Bei diesem Vorgang wird die Ausführung eines Proxys kurz unterbrochen, während \emph{Code und Daten} des Proxys auf einen anderen Host {\bzw} in eine andere virtuelle Maschine verschoben und dort die Ausführung fortgesetzt wird. Dieser Vorgang wird in Abbildung~\ref{fig:Proxy_Migration} veranschaulicht. Wie in der Abbildung dargestellt, ist allgemein zu beachten, dass Verbindungen zwischen den Proxies und ihren Kommunikationspartnern entsprechend "`umgebogen"' werden müssen. Somit sind an die Migration von Proxies folgende konkrete Anforderungen zu stellen:

\begin{enumerate}

\item \sfb Detektion des aktuellen Gerätezustandes \normalfont\\ Es müssen Verfahren verfügbar sein, um aus dem aktuellen Zustand des Gerätes auf sein bevorstehendes Versagen zu schließen. Dazu muss der aktuelle Zustand ermittelt werden können. Mögliche Ansätze hierzu wurden bereits in Abschnitt \ref{sec:Aushandlung_Proxy-Ausfuehrung} diskutiert. Um einen drohenden Ausfall im Systemmodell zu berücksichtigen, wird das Fail-Stop-Modell zum {\sog} \emph{Fail-stutter Fault Modell} erweitert \cite{tr05_survey}. Dieses Modell berücksichtigt einen Zustand, in dem eine Komponente zwar noch funktioniert, jedoch {\zb} aufgrund mangelnder Ressourcen eine unzureichende Performance aufweist.

\item \sfb Signalisierung des Migrationsvorgangs \normalfont\\ Es muss möglich sein, Kommunikationpartner eines zu migrierenden Proxys (andere Proxies oder {\cp}s) über den Vorgang der Migration zu informieren, damit diese den Vorgang nicht mit einer Störung des Proxys verwechseln.

\item \sfb Verschieben von Code und Daten des Proxys \normalfont\\ Das Programm des Proxys muss jederzeit unterbrochen werden können. Weiterhin müssen Code und Daten des Proxys auf einen anderen Host verschoben und dort an der Stelle, an der das Programm unterbrochen wurde, erneut zur Ausführung gebracht werden können.

\item \sfb Umgang mit lokalen Referenzen \normalfont\\ Sofern lokale Komponenten über Referenzen direkt mit dem zu migrierenden Proxy kommunizieren, müssen diese Referenzen geeignet behandelt werden, sodass sie nach erfolgter Migration nicht "`ins Leere"' zeigen und nach Möglichkeit sogar weiter verwendbar bleiben.

\end{enumerate}

Im Folgenden wird im Detail vorgestellt, auf welche Weise diesen Anforderungen entsprochen werden kann.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=11cm, angle=0]{fig/Proxy-Migration.png}
    \setzeBreite
    \caption{Migrationvorgang eines Proxys.}
    \label{fig:Proxy_Migration}
  \end{center}
\end{figure}

% ----------------------------------------------------------------------------
\section{Signalisierung des Migrationsvorgangs}

\sidenote{Beschreibung des Problems} Die Durchführung der Migration nimmt eine gewisse Zeit in Anspruch, während dieser der Proxy bzw. der Dienst des Proxys den {\cp}s nicht zur Verfügung steht. Dieser Zustand kann von einem {\cp} fälschlicher Weise als Ausfall des Proxys gewertet werden. Daher kann ein {\cp} eine Störung melden, obwohl es sich bei dem Vorgang lediglich um eine Migration handelt. Hinzu kommt, dass sich bei einer Migration die Netzwerk-Adresse des Proxys ändert. So kann ein Proxy zwar seine UUID\footnote{Universally Unique Identifier} beibehalten, doch wird sich auf jeden Fall die IP-Adresse des Proxys ändern. Laut Spezifikation darf ein Standard-konformes UPnP-Device allerdings nicht spontan seine IP-Adresse ändern, sondern muss seinen Dienst vor Änderung der IP ordnungsgemäß abmelden (\emph{Byebye-Message}) und ihn mit geänderter IP erneut anmelden \cite{upnp_spec}. Insbesondere hierdurch würde eine Migration von den {\cp}s fälschlicher Weise für ein Abmelden des Proxys aus dem System gehalten.

\sidenote{Signalisierung} Um Fehlinterpretationen des Migrationsvorganges zu vermeiden, ist eine \emph{Migrations-Signalisierung} erforderlich. Das heißt, ein Proxy teilt seinen Kommunikationspartnern vor der Migration mit, dass er das System nicht permanent verlassen wird, sondern seine folgende Ab- und Anmeldung zu dem ordnungsgemäßen Migrationsvorgang gehört. In der im Rahmen der vorliegenden Arbeit entstandenen Referenzimplementierung sieht der Signalisierungsprozess so aus, dass der Proxy eine Ankündigungsnachricht an seine Kommunikationpartner schickt. Diese werten die darauffolgende Byebye-Message als Beginn der Migration und erwarten, dass sich der selbe Proxy in Kürze unter Beibehaltung seiner UUID wieder anmelden wird. Abgebrochen wird dieser Vorgang über einen Timeout.

\sidenote{Finden eines Ziel-AMs} Neben der Signalisierung der bevorstehenden Migration ist eine Abstimmung mit dem {\am} erforderlich, der den Proxy in Empfang nehmen soll. Mitunter muss ein geeigneter {\am} erst gefunden werden. Hierbei können die selben Mechanismen verwendet werden, die bereits bei der Aushandlung der Proxy-Ausführung zum Einsatz kamen (siehe Abschnitt \ref{sec:Aushandlung_Proxy-Ausfuehrung}).

% ----------------------------------------------------------------------------
\section{Verschieben von Code und Daten des Proxys}

\sidenote{Anforderungen an das RE} Bei der eigentlichen Migration wird die Programm\-ausführung des Proxys gestoppt, Programmcode und Daten des Proxys auf einen anderen Host verschoben und die Programm\-ausführung wird auf dem neuen Host fortgesetzt. Dieser Vorgang stellt spezielle Anforderungen an die Laufzeitumgebung:

\begin{itemize}

\item Die Laufzeitumgebung sollte \emph{plattformunabhängig} sein, da es durchaus denkbar ist, dass es sich bei der Zielplattform der Migration um einen anderen Typ als bei der Quellplattform handelt.

\item Die Laufzeitumgebung muss \emph{Serialisationsmechanismen} unterstützen, um Objekte in eine geordnete, transportable Form überführen zu können.

\end{itemize}

\sidenote{Erfüllung der Anforderungen} Diese Anforderungen werden von der \emph{Java Virtual Machine (JVM)} erfüllt, während das \emph{Common Runtime Environment} der \emph{.Net-Plattform} nur eingeschränkte Plattformunabhängigkeit bietet.

\sidenote{Ablauf der Serialisation} Bei der Serialisation werden Memberdaten mit Hilfe von \emph{Introspektionsmechanismen}\footnote{Introspektion ist die Fähigkeit einer VM, Objekte zur Laufzeit zu analysieren. Diese Funktion wird nicht von allen Laufzeitumgebungen unterstützt, da sie einen relativ hohen Ressourcenbedarf hat. So ist die VM der \emph{Connected Limited Device Configuration (CLDC)} der Java 2 Micro Edition nicht introspektionsfähig.} aus Objekten extrahiert und zusammen mit Strukturinformationen in einem Datencontainer abgelegt \cite{java_ser_api}. Dieser Container kann nun leicht auf einen anderen Host bzw. in eine andere virtuelle Maschine übertragen werden. Am Zielort werden die Memberdaten aus dem Container ausgelesen und mit Hilfe der gespeicherten Strukturinformationen in neu erzeugte Objekte eingepflegt. Sofern zu serialisierende Objekte auf andere Objekte verweisen, werden diese anderen Objekte ebenfalls serialisiert und übertragen. Hier ist jedoch zu beachten, dass ausschließlich \emph{plattformunabhängige} Objekte serialisierbar sind. Beispielsweise ist ein \emph{Socket-Objekt}, dass von einem Proxy zur Kommunikation verwendet wird, nicht serialisierbar.

\sidenote{Vorbereitung der Serialisation} Da ein Proxy aufgrund seiner Verbindung zum {\trans} auch nicht-serialisierbare Objekte enthält, muss der Proxy vor der eigentlichen Migration in einen serialisierbaren Zustand überführt werden.\footnote{Allgemein ist ein kooperatives Verhalten der Proxies notwendig, da der Thread eines Proxys nicht einfach angehalten werden kann. So ist die Methode Thread.stop() in der Java API als \emph{deprecated} markiert, da ihr Aufruf nur schwer überschaubare Folgen hat. Die Verwendung der Methode Thread.Abort() wird unter .Net aus dem selben Grund nicht empfohlen.} Das heißt, er muss eigenständig alle in ihm enthaltenen nicht-serialisierbaren Objekte terminieren, bzw. Referenzen zu anderen nicht-serialisierbaren Strukturen zurückziehen. Dies beinhaltet auch einen Abbau der Kommunikationsverbindung zum Transceiver sowie die Abmeldung von der Middleware-basierten Netzgemeinschaft. %Falls der Proxy in einer separaten virtuellen Maschine ausgeführt wird, ist es Aufgabe des \emph{Local Proxy Managers} (siehe Abschnitt \ref{sec:Ausführen_und_Beenden_der_Proxies}) den Proxy auf die Serialisation vorzubereiten {\bzw}, die serialisierten Daten zum Zielhost zu übertragen.

\sidenote{Trennung von Code und Daten} Generell muss bei der Serialisation beachtet werden, dass serialisierte Daten ausschließlich Memberdaten von Objekten sind, jedoch keinerlei Code der entsprechenden Klassen enthalten ist. Folglich muss der Code der jeweiligen Klassen auf dem Zielhost verfügbar sein, damit die Objekte wiederhergestellt werden können. Java kennt einen \emph{Codebase-Mechanismus}, der den normalen Klassenpfad um Remote-Adressen erweitert. Im Rahmen des betrachteten Systems bietet sich hierzu jedoch die Verwendung des verteilten Code-Repositorys an (siehe Abschnitt \ref{sec:Bereitstellung_Proxy-Code}). Das heißt, der Code eines zu migrierenden Proxys wird mit Hilfe des verteilten Code-Repositorys auf dem Zielhost verfügbar gemacht.

% ----------------------------------------------------------------------------
\section{Beispielablauf}

\noindent Die Migration eines Proxys gliedert sich in folgende Schritte, die im Sequenzdiagramm in Abbildung \ref{fig:Sequenzdiagramm_Migration} dargestellt sind:

\begin{enumerate}

\item \sfb Abstimmung mit dem Zielhost \normalfont\\ Der Quell-AM ermittelt entsprechend der in Abschnitt \ref{sec:Aushandlung_Proxy-Ausfuehrung} vorgestellten Verfahren einen geeigneten Zielhost und vereinbart mit dem Ziel-AM eine Übernahme des Proxys.

\item \sfb Stoppen des Proxys \normalfont\\ Der laufende Proxy erhält ein Signal, sämtliche Aktivitäten einzustellen, sodass sich sein Zustand nicht mehr verändert. Ab diesem Zeitpunkt nimmt er keine Anfragen von seinem {\trans} {\bzw} von {\cp}s mehr entgegen.

\item \sfb Signallisierung der Migration und Abmelden des Proxys \normalfont\\ Der Proxy meldet seinen Dienst im Netzwerk ab. Zuvor signalisiert er seinen Kommunikationspartnern, dass er die Netzgemeinschaft nur kurzzeitig ({\dhe} für die Dauer der Migration) verlassen wird.

\item \sfb Serialisation des Proxys \normalfont\\ Der Proxy überführt sich selbst in einen serialisierbaren Zustand. Anschließend wird er serialisiert.

\item \sfb Übertragen der serialisierten Daten \normalfont\\ Die serialisierten Daten des Proxys werden zum Zielhost übertragen. Der Zielhost fordert vor der folgenden De-Serialisierung den Klassencode des Proxys vom Quell-Host an. Hierzu wird das Repository des sendenden {\am}s verwendet.

\item \sfb Deserialisierung des Proxys \normalfont\\ Auf dem Zielhost wird der empfangene Code deserialisiert und ein neuer, lauffähiger Proxy erzeugt, dessen Zustand dem direkt vor der Serialisierung entspricht.

\item \sfb Erneutes Anmelden des Dienstes \normalfont\\ Der Proxy meldet seinen Dienst durch das Versenden von Notify-Messages erneut an. Dabei behält er seine UUID, während sich die IP-Adresse durch den gewechselten Host geändert hat.

\end{enumerate}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=14cm,angle=0]{fig/diagramme/Sequenzdiagramm_Migration.pdf}
    \setzeBreite
    \caption{Sequenzdiagramm der Migration eines Proxys.}
    \label{fig:Sequenzdiagramm_Migration}
  \end{center}
\end{figure}

% ----------------------------------------------------------------------------
\section{Umgang mit lokalen Referenzen}

\sidenote{Beschreibung des Problems} Sofern Proxies als Threads mit anderen Komponenten in einer gemeinsamen virtuellen Maschine ausgeführt werden, können lokale Referenzen zwischen den anderen Komponenten und den Proxies existieren. Wenn ein Proxy auf einen anderen Host migriert wird, werden Referenzen, die vom Proxy ausgehen, automatisch abgebaut, wenn er auf die Serialisation vorbereitet wird. Referenzen, die von anderen Komponenten auf den Proxy weisen, führen jedoch ins Leere, wenn der Proxy ohne weiteres entfernt wird. Nun bestünde ein Lösungsansatz darin, die äußeren Komponenten vor der Migration zu informieren, damit sie ihre Referenzen zurückziehen können. Es sind jedoch Situationen denkbar, in denen eine äußere Komponente auf eine Zugriffsmöglichkeit auf den Proxy angewiesen ist und nicht mehr funktionieren könnte, würde ihr diese Zugriffsmöglichkeit entzogen.

\sidenote{Wrapper} Dieses Problem kann gelöst werden, indem eine "`Weiterleitung"' für migrierte Objekte verwendet wird. Im Rahmen der vorliegenden Arbeit wurden hierzu \emph{Wrapper} eingeführt, die die zu migrierenden Objekte (also die Proxies) umschließen (siehe Abbildung~\ref{fig:Proxy-Migration_lokale_Referenzen}). Äußere Referenzen weisen ausschließlich auf den Wrapper, der dieselbe Schnittstelle besitzt, wie das in ihm enthaltene Objekt. Der Wrapper reicht einen Methodenaufruf direkt weiter an das in ihm enthaltene Objekt. Wird das Objekt auf einen anderen Host verschoben, so führt der Wrapper statt eines lokalen Aufrufs einen für den ursprünglichen Aufrufer transparenten Remote-Aufruf auf dem nunmehr entfernten Objekt durch. Entsprechend kann der Wrapper etwaige Rückgabewerte an die ursprünglichen Aufrufer vermitteln.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=11.5cm,angle=0]{fig/Proxy-Migration_lokale_Referenzen.pdf}
    \setzeBreite
    \caption{Weiterleitung lokaler Aufrufe durch den Wrapper.}
    \label{fig:Proxy-Migration_lokale_Referenzen}
  \end{center}
\end{figure}

\sidenote{RPC-Mechanismen} Für einen entfernten Aufruf sind RPC-Mechanismen notwendig. Bei diesen Mechanismen wird ein Stub-Skeleton-Schema verwendet, um Aufrufe transparent über ein Netzwerk zu senden. Bei Java-basierten Systemen bietet sich hier die Verwendung von \emph{Remote Method Invocation (RMI)} an. Zwar könnte auch UPnP für den Remote-Aufruf verwendet werden, jedoch ist das binäre RMI-Protokoll leistungsfähiger als ein Aufruf über das textbasierte SOAP-Protokoll. Hinzu kommt, dass die RMI-Bibliotheken unter Java den gesamten Vorgang des \emph{Parameter Marshalling} auf transparente Weise übernehmen. Ein letzter wichtiger Punkt ist, dass bei Verwendung von UPnP die Weiterleitungsfunktionen als Dienste im UPnP-Netz sichtbar wären, während eine Weiterleitung per RMI für den Benutzer unsichtbar "`Out-of-Band"' geschieht.

\sidenote{Garbage Collection} Sobald keine Referenzen von Aufrufern auf den Wrapper mehr existieren, kann der Wrapper entfernt werden. Virtuelle Maschinen wie die JVM nutzen hierzu einen \emph{Garbage Collector}. Der Garbage Collector entfernt Objekte aus dem Speicher, die nicht mehr referenziert werden. Ein Problem stellen hier die Referenzen dar, die der {\am} zu Verwaltungszwecken auf den Wrapper hält. Solange diese Referenzen bestehen, kann der Wrapper nicht entfernt werden und der {\am} kann seine Referenzen auf den Wrapper nicht entfernen, da er dann den Kontakt zum Wrapper endgültig verlieren würde. Eine Lösung stellt der Einsatz sog. \emph{schwacher Referenzen}\footnote{Engl.: \emph{Weak References}} dar. Schwache Referenzen werden vom Garbage Collector ignoriert. Das heißt, der Garbage Collector entfernt alle Objekte aus dem Speicher, auf die keine oder ausschließlich schwache Referenzen existieren. Solange der {\am} also schwache Referenzen zur Verwaltung des Wrappers verwendet, kann der Garbage Collector den Wrapper entfernen, sobald keine weiteren "`echten"' Referenzen mehr auf ihn existieren.

% ----------------------------------------------------------------------------
\section{Migrationsdauer}
\label{sec:Eval_Migrationsdauer}

\enlargethispage{-.5cm}

\sidenote{Beschreibung des Setups} Abbildung \ref{fig:Diagramm_Migrationsdauer} veranschaulicht die Dauer der Migration einer einfachen Java-Anwendung sowie eines aktiven UPnP-Proxys. Für die Messung wurde ein Setup bestehend aus zwei herkömmlichen PCs (1,6 und 2,5 GHz) verwendet, die über ein 100 Mbit/s LAN verbunden wurden. Als Softwareplattform wurde das Java Runtime Environment 6, sowie der im gesamten Rahmen dieser Arbeit eingesetzte Infineon UPnP-Stack verwendet.

\sidenote{Zeitaufteilung wie beim Start} Wie sich schon bei der Startzeit von Proxies gezeigt hat (siehe Abbildung \ref{fig:Diagramm_Proxy_Startzeit} in Abschnitt \ref{sec:Ausführen_und_Beenden_der_Proxies}), wird die meiste Zeit für die Bereitstellung des UPnP-Dienstes sowie, bei Ausführung als Prozess, für den Start der virtuellen Maschine benötigt. Sofern der Proxy als Thread in der virtuellen Maschine des {\am}s ausgeführt wird, werden für eine Migration ca. 2 Sekunden benötigt. Bei einer Ausführung in einer separaten VM (als Prozess) fallen knapp 4 Sekunden für die Migration an. Aufgrund der hohen Übertragungsgeschwindigkeit des Netzes spielt die Größe des Proxy Codes eine untergeordnete Rolle, wie Abbildung~\ref{fig:Diagramm_Migrationsdauer_vs_Groesse} zu entnehmen ist.

\begin{figure}[htbp]
  \begin{center}
    \subfigure[Einfluss von UPnP und Ausführungsart auf die Dauer des Migra\-tionsvorgangs.]
    {
      \label{fig:Diagramm_Migrationsdauer}
      \includegraphics[width=7cm]{fig/auswertung/Proxy_Migrationsdauer_vs_Ausfuehrung.pdf}
    }
    \hspace{.25cm}
    \subfigure[Dauer der reinen Datenübertragung.]
    {
      \label{fig:Diagramm_Migrationsdauer_vs_Groesse}
      \includegraphics[width=7cm]{fig/auswertung/Proxy_Migrationsdauer_vs_Groesse.pdf}
    }
    \setzeBreite
    \caption{Proxy-Migrationsdauer.}
  \end{center}
\end{figure}

\sidenote{Mögliche Optimierung} Der in diesem Kapitel vorgestellte, recht geradlinige Ansatz der Migration bietet noch Raum zur Optimierung. So ist es denkbar, an in Frage kommenden Zielorten der Migration Klone des Proxys bereit zu halten und bei Bedarf einfach auf einen der Klone "`umzuschalten"' \cite{cl05_migration}. Auf diese Weise wird der Vorgang der Migration beschleunigt, allerdings bedeutet dieser Ansatz auch einen erheblich größeren Verwaltungsaufwand.

% ****************************************************************************
\chapter{{\rr} in Proxy-basierten Systemen}
\label{sec:Rollback-Recovery}

\sidenote{Ziel des Rollback} {\rr}-Protokolle sind ein Mittel zur Wiedererlangung eines integren Gesamtsystems, nachdem einzelne Komponenten versagt und das System damit beeinträchtigt haben. Wie der Name sagt, wird das System durch die Anwendung der Verfahren befähigt, nach dem Auftreten von Störungen in einen gültigen Zustand "`zurückzurollen"'. Die Hauptaufgabe von {\rr}-Protokollen ist es dabei, das Auftreten von \emph{Inkonsistenzen} zu vermeiden.

\sidenote{Definition des konsistenten Zustandes} Ein Zustand eines Systems wird als \emph{konsistent} bezeichnet, wenn er bei einem fehlerfreien Betrieb des Systems erreicht werden \emph{kann}\footnote{Das heißt nicht, dass der Zustand schon einmal aufgetreten sein muss. Es geht lediglich darum, dass er im fehlerfreien Betrieb möglich ist.} \cite{ja98_fault_tolerance}. Ein inkonsistenter (und damit im fehlerfreien Betrieb unmöglicher) Systemzustand zeichnet sich durch das Auftreten \emph{verwaister Nachrichten} aus. Eine verwaiste Nachricht ist dadurch gekennzeichnet, dass eine Komponente $j$ eine Nachricht $m$ empfangen hat, obwohl $m$ von keiner anderen Komponente $i$ gesendet wurde. Ein solcher Zustand ist nicht denkbar und darf im System, nachdem ein {\rr}-Vorgang durchgeführt wurde, keinesfalls auftreten. Empfänger verwaister Nachrichten werden als \emph{verwaiste Prozesse} bezeichnet. \emph{Verlorene Nachrichten} kennzeichnen den umgekehrten Fall: Eine Nachricht $m$ wurde von einer Komponente $i$ gesendet, die von keiner anderen Komponente $j$ empfangen wurde. Verlorene Nachrichten charakterisieren allerdings keinen inkonsistenten Systemzustand, da es theoretisch denkbar ist, dass die Nachricht $m$ den Empfänger \emph{noch nicht} erreicht hat. In diesem Fall wird von einer \emph{In-Transit-Message} gesprochen \cite{el02_rollback}.

\sidenote{Was heißt das für das betrachtete System?} Inkonsistenzen in dem in dieser Arbeit betrachteten Proxy-basierten System können dann auftreten, wenn ein Proxy $p_i$ nach einem Ausfall als $p'_i$ neu gestartet wird. Sofern der {\trans} $t_i$ eine aktuelle Kopie des Zustandes von $p_i$ enthält, stellt $p_i$ seinen letzten Zustand mit Hilfe von $t_i$ wieder her. Allerdings kann es sein, dass der auf $t_i$ gespeicherte Zustand nicht dem Zustand von $p_i$ direkt vor seinem Ausfall entspricht. So kann $p_i$ einem anderen Proxy $p_j$ kurz vor seinem Ausfall eine Nachricht gesendet haben. Später wird der neu gestartete $p'_i$ "`im Glauben"' sein, diese Nachricht niemals gesendet zu haben -- was einen inkonsistenten Systemzustand darstellt.

\sidenote{Vorteil durch Sindrion-Konzept} Prinzipiell ergibt sich bei {\rr}-Verfahren der Umstand, dass alle Teilnehmer das selbe Protokoll unterstützen müssen. Dies ist ein Problem, da {\rr}-Protokolle bisher nicht standardisiert sind. Im Umfeld des betrachteten Systems lässt sich jedoch ausnutzen, dass neben den Sindrion-Proxies auch die \emph{Specific Control Points (SCPs)} von den {\trans}n bereitgestellt werden (siehe Kapitel \ref{sec:Einleitung}) und somit erwartet werden kann, dass die SCPs das selbe {\rr}-Verfahren einsetzen, wie die Proxies.

\mybox{Für Sub-Systeme bzw. Komponenten, die als Einheit am {\rr} teilnehmen, werden im Folgenden die beiden in der Literatur üblichen Begriffe \emph{Recovery Unit (RU)} {\bzw} \emph{Prozess} verwendet.\\Für die Darstellung der Abläufe beim {\rr} wird im Folgenden eine in der Literatur übliche Art von Sequenzdiagrammen verwendet, die sich jedoch von der in der vorliegenden Arbeit bisher verwendeten Art von Sequenzdiagrammen unterscheidet.}

%\sidenote{Übersicht} Im folgenden Abschnitt wird eine Übersicht gängiger {\rr}-Protokolle gegeben. Anschließend wird in Abschnitt \ref{sec:Realisierung_Rollback} die Entwicklung eines geeigneten {\rr}-Verfahrens für das im ersten Teil der Arbeit entstandene System beschrieben.

% ----------------------------------------------------------------------------
\section{Übersicht gängiger {\rr}-Protokolle}
\label{sec:Uebersicht_Rollback-Recovery}

\sidenote{Einleitung} In diesem Abschnitt wird eine Übersicht gängiger {\rr}-Protokolle gegeben. Anschließend wird in Abschnitt \ref{sec:Realisierung_Rollback} die Entwicklung eines geeigneten {\rr}-Verfahrens für das im ersten Teil der Arbeit entstandene System beschrieben. Für weitergehende Informationen sei insbesondere auf das Buch von Pankaj Jalote "`Fault Tolerance in Distributed Systems"' \cite{ja98_fault_tolerance} sowie den Survey von Elnohazy et. al. "`A Survey of {\rr} Protocols in Message-Passing Systems"' \cite{el02_rollback} verwiesen.

\sidenote{Klassifizierung} {\rr}-Protokolle lassen sich in die Klassen der \emph{Checkpoint-basierten} Protokolle und der \emph{Log-basierten} Protokolle gliedern, wie in der Baumübersicht in Abbildung~\ref{tree:Rollback-Recovery-Protokolle} gezeigt. Diese beiden Familien werden in den folgenden Abschnitten \ref{sec:Checkpointing-basierte_Protokolle} und \ref{sec:Log-basierte_Protokolle} vorgestellt. In Abschnitt \ref{sec:Gegenueberstellung_RR-Protokolle} findet sich schließlich eine Gegenüberstellung der vorgestellten Verfahren. Der Unterschied zwischen den beiden Protokollfamilien liegt darin, dass Checkpoint-basierte Verfahren Zustandsabbilder (Checkpoints) erzeugen, um Komponenten später in zuvor gespeicherte Zustände zurückzuführen, während Log-basierte Verfahren Protokolle der Systemhistorie anlegen und im Fehlerfall auswerten, um das System wieder in einen konsistenten Zustand zu fahren.

Ein Vorgang, der bei allen Verfahren eine zentrale Rolle spielt, ist der {\sog} \emph{\oc}. Von einem {\oc} sprechen wir immer dann, wenn ein {\rr}-System mit seiner Außenwelt interagiert und diese damit beeinflusst. Das Problem ist, dass die zumeist zustandsbehaftete Außenwelt {\idr} nicht in der Lage ist, an einem Rollback-Vorgang teilzunehmen. Für {\rr}-Protokolle bedeutet dies, dass sie in der Lage sein müssen, den Systemzustand unmittelbar nach Beeinflussung der Außenwelt bei einem Rollback wieder anfahren zu können, da es ansonsten zu Inkonsistenzen mit der Außenwelt kommen würde.

\begin{sidewaysfigure}[htbp]
\narrow
\hspace{-1cm}
\begin{parsetree}
  \pthorgap{8pt}
  \ptvergap{55pt}
  (.\begin{tabular}{c}{\rr}-\\Protokolle\end{tabular}.
    (.Checkpointing.
      .unkoordiniert.
      (.koordiniert. .\begin{tabular}{c}Nachrichten-\\basiert\end{tabular}. .\begin{tabular}{c}Timer-\\basiert\end{tabular}.)
      (.induziert. .\begin{tabular}{c}Modell-\\basiert\end{tabular}. .\begin{tabular}{c}Index-\\basiert\end{tabular}.)
    )
    (.Logging. .pessimistisch.
      (.optimistisch. .\begin{tabular}{c}synchrones\\Recovery\end{tabular}. .\begin{tabular}{c}asynchrones\\Recovery\end{tabular}.)
      .kausal.
    )
  )
\end{parsetree}
\vspace{1.5cm}
\setzeBreite
\caption{Übersicht der {\rr}-Protokolle}
\label{tree:Rollback-Recovery-Protokolle}
\wide
\end{sidewaysfigure}

% ----------------------------------------------------------------------------
\subsection{Checkpoint-basierte Protokolle}
\label{sec:Checkpointing-basierte_Protokolle}

\sidenote{Asynchron vs. synchron} Allgemein gibt es zwei Ansätze für Checkpointing: \emph{\acp} und \emph{\scp} (oft auch als \emph{Distributed Checkpointing} bezeichnet). Beim {\acp} erstellen Komponenten Checkpoints unabhängig voneinander, während beim {\scp} die Erstellung der Checkpoints \emph{systemweit} durch einen Zeitpunkt oder ein Ereignis eingeleitet wird.

% ----------------------------------------------------------------------------
\subsubsection{\acp}
\label{sec:Asynchrones_Checkpointing}

\sidenote{Ansatz} Beim {\acp} erstellen Recovery Units ihre Checkpoints vollkommen unabhängig voneinander (asynchron) und legen sie auf einem {\stst} ab. Dabei wird in Kauf genommen, dass zu dem Zeitpunkt, an dem die Checkpoints erstellt werden, nicht gewährleistet werden kann, dass die Menge der aktuellsten Checkpoints in ihrer Gesamtheit einen konsistenten Systemzustand ergibt. Daher muss bei Einleitung eines \emph{Rollbacks} untersucht werden, \emph{welche} Checkpoints zusammen einen gültigen Systemzustand ergeben und damit eine sog. \emph{Recovery Line} bilden. Hierzu können {\zb} \emph{Journale} geführt werden, mit denen verfolgt werden kann, in welcher Weise die im System vorhandenen Recovery Units sich gegenseitig durch den Austausch von Nachrichten beeinflusst haben~\cite{ja98_fault_tolerance}.

\sidenote{Domino-Effekt} Der Hauptnachteil des {\acp} ist das mögliche Auftreten des \emph{Do\-mi\-no-Effekts}, bei dem unkontrollierte Rollbacks einzelner Prozesse auftreten und das System im ungünstigsten Fall lawinenartig bis in den Anfangszustand "`zurückfällt"'. Ein weiterer Nachteil ist, dass die Journale relativ groß werden können, wenn weit zurückliegende Systemzustände angefahren werden sollen. Das in Bezug auf die vorliegende Arbeit wohl größte Manko ist jedoch die Unfähigkeit des {\acp} -- aufgrund der vollkommenen Unabhängigkeit der {\ru}s -- einen \emph{\oc} durchzuführen.

Der Vorteil von {\acp} liegt in seiner Einfachheit, da keinerlei Koordinierung zwischen den Prozessen erforderlich ist. Allgemein bietet sich {\acp} an, wenn mit einem seltenen Auftreten von Fehlern zu rechnen ist und zudem relativ selten kommuniziert wird.

%Die Außenwelt eines Systems ist {\idr} nicht in der Lage, einen Rollback durchzuführen. Daraus folgt, dass immer dann, wenn eine Komponente des Systems den Zustand der Außenwelt \emph{verändert}, gewährleistet sein muss, dass das System zu einem Zustand zurückrollen kann in dem es mit der Außenwelt konsistent ist. Die Sicherstellung, dass solch ein Zustand erreicht werden kann, wird als {\oc} bezeichnet. Beim {\acp} ist aufgrund der vollkommenen Unabhängigkeit der {\ru}s kein {\oc} möglich.

\minisec{Anwendungsbeispiel} \label{Beispiel}

Um ein allgemeines Verständnis für die Problematik des {\rr} zu schaffen, wird im Folgenden ein einfaches Beispiel betrachtet, um den Vorgang des Recovery beim {\acp} näher zu beleuchten. Wir gehen von einem Setup bestehend aus den {\trans}n $t_1$, $t_2$ und $t_3$, sowie den zugehörigen Proxies $p_1$, $p_2$ und $p_3$ aus. Die {\trans} $t_1$ und $t_2$ repräsentieren zwei Lichtschalter mit den zugehörigen Proxies $p_1$ und $p_2$. $t_3$ repräsentiert eine Lampe, die von dem Proxy $p_3$ vertreten wird. Im Beispiel schaltet $t_1$ die Lampe $t_3$ ein, während $t_2$ den veränderten Status von $t_3$ automatisch anzeigen soll. In diesem Beispiel sei jede Komponente eine eigenständige Recovery Unit. Wir gehen weiterhin davon aus, dass zum Startzeitpunkt jede Komponente einen Initial-Check\-point $C_0$ erstellt hat. Jeweils nach Erhalt einer Nachricht wird ein weiterer Checkpoint erstellt. Beim Rollback wird das von Wang et al. vorgestellte Verfahren verwendet \cite{wa95_checkpoint}.

\noindent Folgende (vorerst fehlerfreie) Sequenz wird nun, wie in Abbildung~\ref{fig:Sequenzdiagramm_Recoveryline} dargestellt, durchlaufen:

\begin{enumerate}

\item Der Benutzer betätigt Schalter 1, worauf $t_1$ eine Nachricht an seinen Proxy $p_1$ sendet.

\item Der Proxy $p_1$ schickt eine Nachricht zum Einschalten der Lampe an $p_3$.

\item $p_3$ schaltet die Lampe durch Senden einer Nachricht an $t_3$ ein.

\item $t_3$ bestätigt das Einschalten der Lampe gegenüber $p_3$.

\item $p_3$ informiert $p_1$ und $p_2$ über die Statusänderung per Event.

\item $p_1$ und $p_2$ informieren ihre {\trans} über die
Statusänderung.

\end{enumerate}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=10.5cm,angle=0]{fig/diagramme/Sequenzdiagramm_Recoveryline_1.pdf}
    \setzeBreite
    \caption{Sequenzdiagramm für das Anwendungsbeispiel.}
    \label{fig:Sequenzdiagramm_Recoveryline}
  \end{center}
\end{figure}

\enlargethispage{-.5cm}

Wir nehmen nun an, dass bei $p_3$ eine Störung Auftritt ("'X"' in Abbildung~\ref{fig:Sequenzdiagramm_Recoveryline}), nachdem $p_2$ bereits per Event über die Statusänderung informiert wurde, jedoch bevor $p_1$ informiert werden konnte. Um das System nach dem Neustart von $p_3$ in einen konsistenten Zustand zu bringen, muss eine Recovery Line gefunden werden, die einen möglichst aktuellen Systemzustand widerspiegelt. Um die Recovery Line zu ermitteln, befolgen wir den in Listing~\ref{lst:Propagationsalgorithmus} dargestellten \emph{Propagationsalgorithmus}. Abbildung~\ref{fig:Checkpoint_Graph_1} zeigt einen {\sog} \emph{Checkpoint Graphen} \cite{wa95_checkpoint}, der die Vorgehensweise des Propagationsalgorithmus widerspiegelt. Anschießend ergibt sich die in Abbildung~\ref{fig:Checkpoint_Graph_2} dargestellte Recovery Line.

%\vspace{.3cm}

\pagebreak

\lstinputlisting[basicstyle=\footnotesize, caption=Propagationsalgorithmus nach Wang et al., label=lst:Propagationsalgorithmus] {fig/listings/Propagationsalgorithmus}

\vspace{1cm}

\begin{figure}[htbp]
  \begin{center}
    \subfigure[Ausgangszustand.]
    {
      \label{fig:Checkpoint_Graph_1}
      \includegraphics[width=6.5cm]{fig/diagramme/Sequenzdiagramm_Recoveryline_2.pdf}
    }
    \hspace{1cm}
    \subfigure[Erreichte Recovery Line.]
    {
      \label{fig:Checkpoint_Graph_2}
      \includegraphics[width=6.5cm]{fig/diagramme/Sequenzdiagramm_Recoveryline_3.pdf}
    }
    \setzeBreite
    \caption[Checkpoint Graph und Recovery Line.]{Checkpoint Graph und erreichte Recovery Line des Anwendungsbeispiels.}
  \end{center}
\end{figure}

% ----------------------------------------------------------------------------
\subsubsection{\scp}

\sidenote{\scp} Beim {\scp} stimmen sich die beteiligten Prozesse bei der Erstellung ihrer Checkpoints ab, um zu gewährleisten, dass der resultierende Systemzustand konsistent ist. Hierzu existieren im Wesentlichen zwei Ansätze:

\begin{itemize}

\item \sfb Timer-basierte Synchronisation \normalfont\\ Die gemeinsame Erstellung eines Checkpoints findet zu festgelegten Zeitpunkten statt. Dieser Ansatz ist allerdings auf die Verfügbarkeit synchroner Uhren angewiesen. Synchrone Uhren erfordern wiederum Zeitsynchronisationsprotokolle, die garantieren, dass die Uhren im System maximal um einen Zeitraum $\Delta t$ auseinander laufen. Wenn Recovery Units ihre Checkpoints erstellt haben, so müssen sie damit noch um $\Delta t$ abwarten, bevor sie ihre Arbeit wieder aufnehmen, um sicher zu stellen, dass alle Recovery Units des Systems ihre Checkpoints erstellt haben. Damit hängt die Performance von synchronem Checkpointing direkt von der Genauigkeit der verwendeten Uhren ab.\\Ein {\oc} ist bei diesem Ansatz generell nicht möglich, da die Zeitpunkte, an denen Checkpoints erstellt werden, unabhängig von der jeweiligen Situation im Vorhinein feststehen.

\item \sfb Nachrichten-basierte Synchronisation \normalfont\\ Eine alternative Möglichkeit der Abstimmung besteht darin, dass eine {\ru} allen anderen {\ru}s die Erstellung ihres Checkpoints über eine Nachricht sig\-nalisiert und damit eine systemweite Checkpoint-Erstellung forciert. Insbesondere wenn ein {\oc} durchgeführt werden soll, ist dieser Ansatz jedoch ungünstig, da jedesmal, wenn eine Recovery Unit mit der Außenwelt kommuniziert, alle anderen {\ru}s im System gezwungen werden, einen Checkpoint zu erstellen.

\end{itemize}

\sidenote{Recovery} Der eigentliche Recovery-Vorgang ist beim {\scp} relativ einfach, da lediglich zum letzten globalen Checkpoint zurückgesprungen werden muss und kein Domino-Effekt wie beim {\acp} auftreten kann.

% ----------------------------------------------------------------------------
\subsubsection{\cicp}

\sidenote{Was ist {\cicp}?} \emph{Communication-induced} (induziertes) oder auch \emph{quasi-asynchronous} Checkpointing ist eine Kombination aus {\acp} und {\scp}. Es vermeidet den Domino-Effekt und gestattet es Prozessen \emph{einige} ihrer Checkpoints ({\sog} \emph{Local Checkpoints}) unabhängig voneinander zu erstellen \cite{tr05_survey}. Allerdings können {\bzw} \emph{müssen} Prozesse gezwungen werden, zusätzliche Checkpoints ({\sog} \emph{Forced Checkpoints}) zu erzeugen, um eine gültige Recovery Line zu erzielen. Um erkennen zu können, wann die Erstellung von Checkpoints erzwungen werden muss, werden Metadaten auf gesendete Nachrichten aufgeprägt und von den Empfängern entsprechend ausgewertet. {\cicp} existiert im Wesentlichen in zwei Ausprägungen:

\begin{itemize}

\item Beim \emph{Model-based Checkpointing} wird bei Erkennung bestimmter Kommunikations-Pattern die Erstellung von Checkpoints erzwungen. Entsprechend erfolgt der Nachrichtenaustausch nach einem vorgegebenen Schema, wodurch diese Kommunikations-Pattern eingehalten werden \cite{wa97_checkpoints}.

\item Verfahren nach dem \emph{Index-based Checkpointing} prägen Indizes auf Nachrichten auf und erlauben anhand dieser Indizes eine Erkennung, wann die Erstellung von Checkpoints erzwungen werden muss \cite{br84_recovery}.

\end{itemize}

Die meisten Verfahren gehen bei der Erzeugung erzwungener Checkpoints prinzipiell konservativ vor und erzeugen mehr Checkpoints, als eigentlich erforderlich wäre. Daher wird allgemein angestrebt, die Zahl der Forced Checkpoints so gering wie möglich zu halten~\cite{je97_checkpoints}.

% ----------------------------------------------------------------------------
\subsection{Log-basierte Protokolle}
\label{sec:Log-basierte_Protokolle}

\sidenote{Einleitung} Log-basierte Protokolle nutzen neben dem bereits beschriebenen Checkpointing sog. \emph{Message Logs}, um Prozesse zu befähigen, einen gültigen Systemzustand vor Auftreten einer Störung wieder "`anzufahren"' \cite{al94_optimal,al96_optimal}. Der Vorgang des Anfahrens wird auch \emph{Replay} genannt. Die Anwendung Log-basierter Verfahren hat zwei wesentliche Vorteile:

\begin{itemize}

\item \sfb Effizienter {\oc} \normalfont\\ Die Interaktion mit der Außenwelt ({\oc}) kann effizienter durchgeführt werden, da ein Prozess nach einem Rollback den Zustand wieder anfahren kann, der konsistent mit der Außenwelt ist. Bei einer Anwendung rein Checkpoint-basierter Verfahren müsste vor einem {\oc} jedesmal ein neuer Checkpoint erzeugt werden, was sich aufwendig gestaltet {\bzw} je nach Verfahren gar nicht möglich ist (siehe Abschnitt \ref{sec:Checkpointing-basierte_Protokolle}).

\item \sfb Vermeidung des Domino-Effektes \normalfont\\ Der Domino-Effekt kann bei Log-basierten Verfahren prinzipiell nicht auftreten. Daher können die Verfahren sehr gut mit dem einfach zu realisierenden {\acp} ergänzt werden. Ein neu gestarteter Prozess beginnt stets bei seinem letzten Checkpoint und führt dann einen Replay entsprechend der Einträge in seinem Message Log durch.

\end{itemize}

\sidenote{Zustandsintervalle und Determinanten} Voraussetzung für die Anwendung Log-basierter Verfahren ist die Modellierbarkeit des zugrundeliegenden Systems als Folge von \emph{Zustandsintervallen} -- deterministischer Abläufe, die jeweils durch nicht-deter\-minis\-tische Ereignisse eingeleitet werden.\footnote{Die Annahme, dass dies zutrifft, wird \emph{Piecewise Deterministic Assumption (PWD)} genannt (siehe Abschnitt \ref{sec:Systemmodell}).} Der Empfang einer Nachricht ist solch ein nicht-deterministisches Ereignis, das ein neues Zustandsintervall einleitet. Ein Datensatz, der ein Zustandsintervall komplett beschreibt, wird \emph{Determinate} des Zustandsintervalls genannt. Es ist Aufgabe der Message Logs, die Determinanten sämtlicher Zustandsintervalle (und damit sämtlicher empfangener Nachrichten der Prozesse) aufzuzeichnen. Message Logs werden {\ia} im flüchtigen Speicher der Prozesse gehalten und gehen bei Ausfall der Prozesse verloren. Determinanten, die hingegen auf einem {\stst} abgelegt wurden, werden als \emph{stable} bezeichnet.

\sidenote{Wirkungsweise} Es soll nun betrachtet werden, unter welchen Bedingungen verwaiste Prozesse (Inkonsistenzen) im System durch Anwendung von Logging-Verfahren vermieden werden können: Es sei $e$ ein nicht-deterministisches Ereignis eines Prozesses $p$. Ferner gelte:

\begin{itemize}

  \item $Depend(e)$ sei die Menge der Prozesse, die nach \emph{Lamport's Happened Before Relation}~\cite{la78_events} von $e$ beeinflusst werden. In dieser Menge ist auch $p$ selbst enthalten.

  \item $Log(e)$ sei die Menge der Prozesse, die die Determinante von $e$ in ihrem \emph{flüchtigen} Speicher vorhalten.

  \item $isStable(e)$ sei ein Prädikat, das dann wahr ist, wenn die Determinante von $e$ auf dem {\stst} festgehalten wurde.

\end{itemize}

In einem System sind keine verwaisten Prozesse vorhanden, wenn gilt:

$$ \forall e: \neg isStable(e) \Rightarrow Depend(e) \subseteq Log(e) $$

\sidenote{\anoc} Dies bedeutet: \emph{Wenn im System Ereignisse aufgetreten sind, deren Determinanten nicht auf einem {\stst} abgelegt sind, dann ist die Menge der Prozesse, die von den Ereignissen abhängig sind, eine Teilmenge der Prozesse, die die Determinanten in ihren Message Logs vorhalten.} Solange diese Eigenschaft zutrifft, sind verwaiste Prozesse im System vermeidbar. Daher wird diese Eigenschaft in der Literatur auch als \emph{\anoc} bezeichnet \cite{el02_rollback}. Anschaulicher ausgedrückt bedeutet sie, dass verwaiste Prozesse vermieden werden können, solange die Determinanten aufgetretener Ereignisse entweder auf dem {\stst} oder in den Message Logs der Prozesse verfügbar sind.

% ----------------------------------------------------------------------------
\subsubsection{\pl}

\sidenote{Was ist {\pl}?} \emph{\pl} trägt seinen Namen aufgrund der Annahme, dass Fehler prinzipiell in \emph{jedem} Zustandsintervall auftreten können. Diese Annahme ist pessimistisch, da Fehler in der Regel viel seltener auftreten. Beim {\pl} wird die Determinante jedes nicht-deterministischen Ereignisses auf dem {\stst} abgelegt \emph{bevor} das Ereignis den Zustand der Komponente beeinflussen kann. Daher wird {\pl} oft auch als \emph{Synchronous Logging} bezeichnet. Formal betrachtet wird beim {\pl} eine striktere Fassung der {\anoc} umgesetzt, da sämtliche Determinanten unmittelbar auf dem {\stst} abgelegt werden:

$$ \forall e: \neg isStable(e) \Rightarrow |Depend(e)| = 0 $$

\sidenote{Beurteilung} {\pl} hat den Vorteil, dass es ein vergleichsweise einfach umzusetzendes Verfahren ist. Hinzu kommt, dass für den {\oc} kein spezielles Protokoll eingehalten werden muss. Als Nachteil sind die Latenzzeiten zu nennen, die durch die häufigen synchronen Zugriffe auf das {\stst} entstehen. {\pl} wird daher zumeist in Systemen favorisiert, in denen ein geringer Recovery-Overhead wichtiger ist als der normale Laufzeit-Overhead \cite{hu95_why}.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=11.5cm, angle=0]{fig/diagramme/Sequenzdiagramm_PL.pdf}
    \setzeBreite
    \caption{Beispiel-Sequenzdiagramm für {\pl}.}
    \label{fig:Sequenzdiagramm_PL}
  \end{center}
\end{figure}

\sidenote{Recovery} Beim Recovery stellt ein neu gestarteter Prozess über seinen aktuellsten Checkpoint einen Ausgangszustand her. Anschließend arbeitet er die aufgetretenen nicht-deter\-minis\-tischen Ereignisse mit Hilfe seines Message Logs ab (Replay). Hierbei ist es erforderlich, die nach dem letzten nicht-deterministischen Event zu sendenden Nachrichten \emph{physikalisch} neu zu senden. Alle anderen Sendevorgänge können "`intern"' abgehandelt werden, ohne sie wirklich zu verschicken. Betrachten wir hierzu Abbildung~\ref{fig:Sequenzdiagramm_PL} für ein Beispiel: Prozess $P_2$ stellt nach seinem Neustart den Ausgangszustand $C_1$ mit Hilfe des letzten Checkpoints wieder her. Anschließend fängt er an, sein Message Log zu durchlaufen, das er vom {\stst} bezogen hat. Das Log enthält die Determinanten der Nachrichten-Empfangsereignisse von $m_2$ und $m_5$. Da die Determinante von $m_5$ im Log enthalten ist, kann sich der Prozess sicher sein, dass $m_3$ gesendet wurde, da das Senden von $m_3$ zum deterministischen Ablauf gehört, der durch das nicht-deterministische Ereignis $m_2$ eingeleitet wurde. Der Empfang der Nachricht $m_5$ ist jedoch das letzte Ereignis im Log. Daher kann $P_2$ nicht wissen, ob $m_6$ bereits gesendet wurde oder nicht. Folglich muss $m_6$ physikalisch erneut gesendet werden -- selbst auf die Gefahr hin, dass es sich um eine Wiederholung handelt. Mit dieser möglichen Wiederholung muss der Empfänger der Nachricht umgehen können. Das heißt, er muss selbst nachhalten, welche Nachrichten er bereits empfangen hat und welche nicht. Hierzu können {\zb} Nachrichten-IDs {\bzw} Sequenznummern verwendet werden.

% ----------------------------------------------------------------------------
\subsubsection{\ol}
\label{sec:Optimistic_Logging}

\sidenote{Was ist {\ol}} Im Unterschied zu {\pl} geht \emph{{\ol}} davon aus, dass Fehler \emph{selten} auftreten bzw., dass der Logging-Vorgang jeweils vor Auftreten eines Fehlers abgeschlossen ist. Daher speichern {\ol} Verfahren ihre Log-Einträge \emph{asynchron} -- also während das Ereignis den Prozess bereits verändert -- auf dem {\stst}. Determinanten werden im Message Log im flüchtigen Speicher gehalten, das von Zeit zu Zeit auf das {\stst} geleert wird. {\ol} nimmt damit in Kauf, dass temporär verwaiste Prozesse entstehen können, stellt jedoch sicher, dass nach einem abgeschlossenen Rollback keine verwaisten Prozesse vorhanden sind.

%\enlargethispage{.5cm}

\sidenote{Beurteilung} Der Vorteil des {\ol} ist, dass Applikationen nicht bis zum Abschluss des jeweiligen Logging-Vorganges blockieren und damit keine Latenzzeiten wie beim {\pl} entstehen. Allerdings ist der Recovery-Vorgang wesentlich komplizierter -- schließlich ist es möglich, dass die in den Message Logs gespeicherte Determinanten beim Ausfall eines Prozesses verloren gehen, \emph{bevor} sie auf dem {\stst} gesichert werden konnten. Somit müssen Abhängigkeiten zwischen Prozessen, die durch den Austausch von Nachrichten zu Stande kommen, ständig nachgehalten werden und beim Rollback der maximal erreichbare Systemzustand zuerst ermittelt werden, bevor er angefahren werden kann~\cite{jo90_optimal,st85_optimal}.

\sidenote{Abstimmung beim {\oc}} Ein asynchroner Zugriff auf das {\stst} ist beim {\oc} allerdings nicht möglich: Hier erfolgt der Zugriff synchron, um Konsistenz mit der Außenwelt garantieren zu können. Hinzu kommt, dass beim {\oc} mitunter die Abstimmung mit anderen Prozessen notwendig ist: Ein Prozess, der die Außenwelt beeinflusst, muss nachvollziehen, welche anderen Prozesse \emph{indirekt} an dem {\oc} beteiligt sind. Diese Prozesse müssen benachrichtigt werden, damit sie ebenfalls eine Sicherung auf dem {\stst} durchführen. So muss in dem in Abbildung \ref{fig:Sequenzdiagramm_OL} dargestellten Beispiel der Prozess $P_0$, der zum Zeitpunkt $X$ einen {\oc} durchführt, nicht nur die Nachrichten $m_4$ und $m_7$ selbst auf dem {\stst} sichern -- er muss auch Prozess $P_2$ auffordern, die Nachrichten $m_2$ und $m_5$ zu sichern, um den globalen Systemzustand garantiert wiederherstellbar zu machen.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=11cm, angle=0]{fig/diagramme/Sequenzdiagramm_OL.pdf}
    \setzeBreite
    \caption{Beispiel-Sequenzdiagramm für {\ol}.}
    \label{fig:Sequenzdiagramm_OL}
  \end{center}
\end{figure}

% ----------------------------------------------------------------------------
\subsubsection{\cl}

%Hilfe: 2 Prozesse. A sendet an B eine Nachricht und damit seinen AG. Wenn A ausfällt, stellt er seinen letzten Checkpoint wieder her und fordert dann von B den AG an, der ja auch die Historie von A enthält. Mit dieser Information kann A seinen Replay durchführen und weiß im Unterschied zu {\pl} auch, welche Nachrichten er an B nach dem letzten nicht-deterministischen Ereignis gesendet hat. Nehmen wir nun an, dass beide Prozesse gleichzeitig ausfallen. Damit ist die AG-Information, die noch nicht auf dem {\stst} abgelegt ist, verloren. Trotzdem wird ein konsistenter Zustand wieder hergestellt...

\sidenote{Charakteristika} Bezogen auf seine Merkmale ist \emph{{\cl}} eine Mischform aus {\pl} und {\ol}: Es gestattet wie auch {\ol} einen asynchronen Zugriff auf das {\stst} (ausgenommen beim {\oc} -- da ist der Zugriff synchron). Wie auch {\pl} gestattet es den Prozessen, {\oc}s unabhängig voneinander durchzuführen. Dabei werden niemals verwaiste Prozesse erzeugt. {\cl} trägt den Namen, weil jeder Prozess im System die durch den Nachrichtenaustausch verursachten \emph{kausalen} Abhängigkeiten mitverfolgt, die \emph{kumulativ} den aktuellen Zustand des Prozesses bewirkt haben. Zwei bekannte Vertreter des {\cl} sind das \emph{Manetho}-Protokoll \cite{el92_manetho} sowie \emph{Family-based Logging} \cite{al96_tradeoffs}. Family-based Logging ist schlanker zu implementieren als Manetho, allerdings toleriert es nur einen Ausfall zu einer Zeit im System. Die folgenden Betrachtungen beziehen sich daher auf das Manetho-Protokoll.

\pagebreak

\sidenote{Antezedenzgraphen} Um die kausalen Abhängigkeiten im System zu verfolgen, benutzt das Manetho-Protokoll sog. \emph{Antezedenzgraphen} \cite{el92_manetho}. Der Antezedenzgraph $AG$ des $i$-ten Zustandsintervalls $\sigma$ eines Prozesses $p$, $AG(\sigma_{p,i})$, ist ein gerichteter azyklischer Graph. Ein Knoten im Antezedenzgraph repräsentiert ein Zustandsintervall $\sigma_{p,i}$, das durch ein nicht-deterministisches Ereignis (Empfang einer Nachricht) eingeleitet wird (siehe Abbildung~\ref{fig:Manetho-Hilfe}). Er hat stets zwei auf ihn zulaufende Kanten: eine von dem Knoten, der das vorherige Zustandsintervall des \emph{selben} Prozesses repräsentiert und eine von dem Knoten der das Zustandsintervall des \emph{sendenden} Prozesses repräsentiert. Abbildung~\ref{fig:Beispielsequenz_Manetho} zeigt eine Beispielsequenz mit zugehörigem Antezedenzgraph. Ein Knoten eines Antezedenzgraphen enthält folgende Informationen:

\begin{itemize}

  \item Den eindeutigen Identifier (ID) der {\ru},

  \item die ID des Senders der Nachricht,

  \item den Index des eingeleiteten Zustandsintervalls und

  \item eine eindeutige ID der empfangenen Nachricht.\footnote{Der Antezedenzgraph enthält \emph{keine} Kopien der empfangenen Nachrichten, da diese im Log des \emph{Senders} gespeichert werden.}

\end{itemize}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=9.5cm,angle=0]{fig/Manetho-Hilfe.pdf}
    \setzeBreite
    \caption[Erklärung des Zustandsintervalls.]{Ein Zustandsintervall $i$ wird in der verwendeten Art der Darstellung jeweils mit dem Bezeichner $\sigma_i$ eingeleitet.}
    \label{fig:Manetho-Hilfe}
  \end{center}
\end{figure}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=14cm,angle=0]{fig/diagramme/Sequenzdiagramm+AG_Manetho.pdf}
    \setzeBreite
    \caption{Manetho-Beispielsequenz mit zugehörigem Antezedenzgraphen.}
    \label{fig:Beispielsequenz_Manetho}
  \end{center}
\end{figure}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=14cm,angle=0]{fig/Manetho-Veranschaulichung.pdf}
    \setzeBreite
    \caption[Veranschaulichung des Manetho-Protokolls.]{Recovery Units (RUs) legen Antezedenzgraphen (AGs) und Logs auf dem {\stst} ab. AGs werden zusätzlich mit jeder Nachricht geschickt und beim Empfänger zusammengeführt.}
    \label{fig:Manetho-Veranschaulichung}
  \end{center}
\end{figure}

\sidenote{Informationen im flüchtigen Speicher} Neben dem Antezedenzgraphen des aktuellen Zustandsintervalls hält eine {\ru} ein Message Log in ihrem flüchtigen Speicher, das Inhalte und Identifikationsmerkmale jeder \emph{gesendeten} Nachricht enthält. Wird eine Nachricht gesendet, so wird der aktuelle Antezedenzgraph mit der Nachricht gesendet. Zu willkürlichen Zeitpunkten legt eine {\ru} einen Checkpoint ihres aktuellen Zustands auf einem {\stst} ab. Das Erstellen dieser Checkpoints wird nicht mit anderen RUs koordiniert. Das aktuelle Message Log sowie der aktuelle Antezedenzgraph $AG$ werden als Teil des Zustandes mit gespeichert. Antezedenzgraphen, die bereits auf dem {\stst} abgelegt sind, müssen nicht mehr mit den Nachrichten der {\ru} verschickt werden. Abbildung \ref{fig:Manetho-Veranschaulichung} veranschaulicht diese Vorgänge. Bevor ein {\oc} durchgeführt wird, legt eine {\ru} den Antezedenzgraphen des aktuellen Zustandsintervalls auf dem {\stst} ab. Auch hier ist keinerlei Koordination mit anderen RUs notwendig -- allerdings erfolgt der Zugriff auf das {\stst} synchron.

\sidenote{Inkarnationsnummern} Aufgrund allgemeiner Netzlatenzen ist es theoretisch denkbar, dass eine Nachricht ihren Empfänger erreicht, nachdem der Sender der Nachricht ausgefallen ist, der Empfänger jedoch bereits über den Ausfall des Senders informiert wurde. In diesem Fall hätte der Empfänger keine Möglichkeit zu ermitteln, ob die Nachricht vor dem Ausfall oder nach einem Recovery-Vorgang des Senders verschickt wurde. Aus diesem Grund führt das Manetho-Protokoll {\sog} \emph{Inkarnationsnummern} ein, die bei jedem Recovery-Vorgang inkrementiert und mit jeder Nachricht verschickt werden. Auf diese Weise kann der Empfänger einer Nachricht ermitteln, ob die Nachricht vor oder nach dem letzten Recovery-Vorgang gesendet wurde. In Anhang \ref{sec:Recovery-Protokoll_Manetho} befindet sich eine detaillierte Beschreibung des Recovery-Protokolls, das von Manetho verwendet wird.

%% ----------------------------------------------------------------------------
%\subsection{Garbage Collection}
%\label{sec:Garbage_Collection}
%
%Checkpoint- bzw. Log-Daten werden ab einem bestimmten Zeitpunkt obsolet und können verworfen werden, um Speicherplatz zu gewinnen. Beim {\scp} oder {\pl} ist dieser \emph{Garbage Collection} genannte Vorgang trivial, da stets nur der aktuellste Checkpoint eines Prozesses verwahrt werden muss. Beim {\acp} oder beim {\ol} muss aufwendig nachvollzogen werden, welche Checkpoints bzw. Log-Daten im Falle eines Rollbacks noch benötigt werden und welche obsolet sind, was zusätzliche Anforderungen an die {\ru}s stellt.

% ----------------------------------------------------------------------------
\subsection{Gegenüberstellung der vorgestellten Protokolle}
\label{sec:Gegenueberstellung_RR-Protokolle}

\sidenote{Siehe Tabelle!} Die im Wesentlichen der Arbeit von Elnohazy et. al. \cite{el02_rollback} entnommene Tabelle \ref{tab:Vergleich_Rollback-Recovery} stellt die in den Abschnitten \ref{sec:Checkpointing-basierte_Protokolle} und \ref{sec:Log-basierte_Protokolle} beschriebenen Protokolle gegenüber:

\begin{itemize}

\item \sidenote{PWD} Sämtliche Log-basierten Protokolle setzen architekturbedingt stückweisen Determinismus (PWD) voraus (siehe Abschnitt~\ref{sec:Log-basierte_Protokolle}). Checkpoint-basierte Protokolle sind auf stückweisen Determinismus hingegen nicht angewiesen.

\item \sidenote{Garbage Collection} \emph{Garbage Collection} -- das Aufräumen von Checkpoint- {\bzw} Log-Daten -- ist {\idr} ein komplexer Vorgang\footnote{Je nach Verfahren ist nicht unmittelbar ersichtlich, welche Checkpoint- {\bzw} Log-Daten zu einem bestimmten Zeitpunkt obsolet sind und damit verworfen werden können.}, lediglich im Falle des {\scp} und des {\pl} ist der Vorgang trivial, da die Prozesse lediglich ihren letzten Checkpoint {\bzw} das Message Log ab dem letzten Checkpoint verwahren müssen.

\item \sidenote{Checkpt. pro Prozess} {\acp}, {\cicp} und {\ol} erfordern die Aufbewahrung mehrerer Checkpoints pro Prozess. Bei {\scp}, {\pl} sowie beim {\cl} muss lediglich der letzte Checkpoint aufbewahrt werden.

\item \sidenote{Domino-Effekt} Das einzige Protokoll, bei dem der Domino-Effekt auftreten kann, ist {\acp}, alle anderen Protokolle lassen den Domino-Effekt nicht zu.

\item \sidenote{Verwaiste Prozesse} Verwaiste Prozesse sind bei {\acp}, bei {\cicp}, sowie beim {\ol} temporär möglich. Alle Protokolle gewährleisten jedoch, dass nach Abschluss des Rollbacks keine verwaisten Prozesse mehr vorhanden sind.

\item \sidenote{Umfang des Rollbacks} Die Protokolle, die lediglich einen Checkpoint pro Prozess zulassen ({\scp}, {\pl}, sowie {\cl}), erlauben natürlich auch nur ein Rollback zum letzten Checkpoint. {\cicp}, und {\ol} erfordern mitunter einen Rollback über mehrere Checkpoints, während {\acp} aufgrund des Domino-Effektes im Extremfall über alle Checkpoints zurückrollen kann.

\item \sidenote{Recovery-Vorgang} Bei {\scp} sowie {\pl} ist der Recovery-Vorgang vergleichsweise simpel. Bei den anderen Protokollen müssen zum Teil komplexe Abhängigkeiten zwischen den Prozessen berücksichtigt werden, was den Vorgang des Recovery aufwendiger macht.

\item \sidenote{Gleichzeitige Ausfälle} Im Prinzip erlauben alle Protokolle bis auf Family-based Logging beliebig viele Ausfälle zur selben Zeit. Family-based logging erlaubt hingegen nur einen einzigen Ausfall zu einer Zeit, was das Verfahren für viele Anwendungszwecke ungeeignet macht.

\item \sidenote{{\oc}} Der im Fokus der vorliegenden Arbeit relevanteste Gesichtspunkt ist der {\oc}. Checkpoint-basierte Protokolle sind hier gänzlich ungeeignet, da sie entweder keinen {\oc} durchführen können ({\acp}) oder, wie im Falle von {\scp} oder {\cicp} nur sehr ineffizient arbeiten, da sie erfordern, dass mehrere Prozesse Checkpoints erstellen, obwohl lediglich ein einzelner Prozess den {\oc} durchführt.\\Log-basierte Protokolle sind hier generell geeigneter, unterscheiden sich allerdings auch hinsichtlich der Performance beim {\oc}. Das schnellste Verfahren ist hier {\pl}, da es kein spezielles Protokoll für den {\oc} erfordert. {\ol} ist aufgrund der notwendigen Multi-Host-Abstimmung beim {\oc} vergleichsweise langsam, während kausales Logging einen guten Kompromiss darstellt.

\end{itemize}

\begin{sidewaystable}[htbp]
\scriptsize
\begin{tabular}{p{2cm}p{2cm}p{2cm}p{2cm}p{2cm}p{2cm}p{2cm}}

  \toprule

  \rowcolor{dunkelgrau}
  & \multicolumn{3}{>{\columncolor{dunkelgrau1}}c}{\textbf{CHECKPOINTING}} & \multicolumn{3}{>{\columncolor{dunkelgrau2}}c}{\textbf{LOGGING}}\\

  \rowcolor{dunkelgrau}
  & \textbf{unkoordiniert} & \textbf{koordiniert} & \textbf{induziert} & \textbf{pessimistisch} & \textbf{optimistisch} & \textbf{kausal}\\

  \midrule

  \rowcolor{hellgrau1}
  \textbf{PWD vorausgesetzt} & nein & nein & nein & ja & ja & ja\\

  \rowcolor{hellgrau2}
  \textbf{Garbage Collection} & komplex & einfach & komplex & einfach & komplex & komplex (einfacher bei FBL)\\

  \rowcolor{hellgrau1}
  \textbf{Checkpoints pro Prozess} & mehrere & 1 & mehrere & 1 & mehrere & 1\\

  \rowcolor{hellgrau2}
  \textbf{Domino-Effekt} & möglich & nein & nein & nein & nein & nein\\

  \rowcolor{hellgrau1}
  \textbf{Verwaiste Prozesse} & möglich & nein & möglich & nein & möglich & nein\\

  \rowcolor{hellgrau2}
  \textbf{Umfang des Rollbacks} & beliebig & letzter globaler Checkpoint & mehrere Checkpoints möglich & letzter Checkpoint & mehrere Checkpoints möglich & letzter Checkpoint\\

  \rowcolor{hellgrau1}
  \textbf{Recovery-Vorgang} & komplex & einfach & komplex & einfach & komplex & komplex (einfacher bei FBL)\\

  \rowcolor{hellgrau2}
  \textbf{Gleichzeitige Ausfälle} & beliebig & beliebig & beliebig & beliebig & beliebig & beliebig (1 bei FBL)\\

  \rowcolor{hellgrau1}
  \textbf{{\oc}} & nicht möglich & sehr langsam & sehr langsam & sehr schnell & langsam & schnell\\

  \bottomrule

\end{tabular}
\setzeBreite
\caption{Vergleichsübersicht der {\rr}-Protokolle.}
\label{tab:Vergleich_Rollback-Recovery}
\end{sidewaystable}

% ----------------------------------------------------------------------------
\section{Realisierung eines {\rr}-Verfahrens für das betrachtete System}
\label{sec:Realisierung_Rollback}

\sidenote{Anforderungen} Im Folgenden wird ein geeignetes {\rr}-Verfahren für das im ersten Teil der Arbeit entwickelte System konzipiert. Mit Bezug auf die Eigenschaften dieses Systems (siehe Abschnitt \ref{sec:Systemmodell}), sind die folgenden Anforderungen an ein {\rr}-Verfahren zu stellen:

%\enlargethispage{-.5cm}

\begin{itemize}

\item \sfb Eignung für häufigen {\oc} \normalfont\\ Interaktion mit der Außenwelt erfolgt {\idr} über den Transceiver. Durch den typischen Einsatz von {\trans}n als Aktuatoren findet eine rege Interaktion mit der Außenwelt statt. Das angewendete {\rr}-Protokoll muss daher für einen häufigen {\oc} geeignet sein.

\item \sfb Zeitnahes Ansprechverhalten der Geräte \normalfont\\ Der Zugriff auf einen {\trans} darf durch das {\rr}-Protokoll nicht zu stark verlangsamt werden. Mehr als 200 ms Latenz bei Durchführung eines Schaltvorgangs wirken sich als störend für den Benutzer aus.\footnote{Wert empirisch ermittelt.}

\item \sfb Möglichst geringer Kommunikationsoverhead \normalfont\\ Um die teilnehmenden Geräte nicht unnötig zu belasten, sollte ein {\rr}-Protokoll ein möglichst geringes zusätzliches Datenaufkommen verursachen. Dies gilt besonders in Hinblick die {\trans}, deren Energiereserven und Bandbreiten sehr gering sind.

\item \sfb Umgang mit temporär abwesenden {\trans}n \normalfont\\ {\trans} können aufgrund ihrer \emph{Betriebszyklen} zeitweise im Standby-Betrieb sein und sind daher vorübergehend nicht erreichbar. Diese Eigenschaft darf dem Einsatz des {\rr}-Protokolls nicht im Wege stehen.

\end{itemize}

% ----------------------------------------------------------------------------
\subsection{{\trans} und Proxy als gemeinsame Recovery Unit}
\label{sec:Gemeinsames_Recovery_Unit}

\sidenote{Hybride Verfahren} Für Systeme, die Geräte unterschiedlicher Leistungsklassen enthalten, werden mitunter \emph{hybride Verfahren} für {\rr} vorgeschlagen \cite{hi98_recovery}. Dabei verwenden leistungsarme Geräte ein anderes {\rr}-Verfahren als Geräte höherer Leistungsklasse. Generell wäre eine Anwendung solch hybrider Verfahren auch auf das im Rahmen der vorliegenden Arbeit betrachtete System denkbar. Dies würde jedoch immer noch bedeuten, dass die {\trans} ein {\rr} Protokoll direkt unterstützen müssten, was ihre ohnehin knappen Ressourcen zusätzlich beanspruchen würde.

\sidenote{Gemeinsame RU} Allerdings kann bzgl. des betrachteten Systems ausgenutzt werden, dass pro {\trans} jeweils nur \emph{ein einzelner} Proxy existiert. Damit kann das Paar bestehend aus Proxy und {\trans} als Einheit bzw. in sich geschlossene Recovery Unit betrachtet werden, die sich intern synchronisiert (siehe Abbildung~\ref{fig:Update-Konzept}).

%\vspace{.5cm}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=13.5cm,angle=0]{fig/Update-Konzept.pdf}
    \setzeBreite
    \caption[Transceiver und Proxy als gemeinsame Recovery Unit.]{Der Transceiver synchronisiert sich mit seinem Proxy, während der Proxy am eigentlichen {\rr} teilnimmt.}
    \label{fig:Update-Konzept}
  \end{center}
\end{figure}

\sidenote{Vorteile dieses Ansatzes} Durch diesen Ansatz wird der Transceiver entlastet, da er für ein {\rr} Protokoll selbst keinerlei Unterstützung bieten muss. Ferner kann er seine "`gewohnten"' Betriebszyklen beibehalten und somit Energie einsparen.

% ----------------------------------------------------------------------------
\subsection{Auswahl eines {\rr} Protokolls als Basis}
\label{sec:Auswahl_Protokoll}

\sidenote{Einleitung} Im Folgenden wird untersucht, welche {\rr} Protokolle sich unter den {\og} Anforderungen auf das betrachtete System anwenden lassen. Dabei werden zuerst alle Protokolle ausgeschlossen, die die genannten Anforderungen nicht bzw. nur unzureichend erfüllen. Die in Frage kommenden Kandidaten werden schließlich einer weiteren Evaluierung unterzogen.

\sidenote{Ausschluss Checkpointing-basierter Verfahren} Ein System, wie es im Rahmen der vorliegenden Arbeit behandelt wird, interagiert regelmäßig und oft mit der Außenwelt. Da Checkpointing-basierte Verfahren in Bezug auf den {\oc} nur sehr ineffizient arbeiten oder ihn, wie im Falle von {\acp}, überhaupt nicht unterstützen, beschränkt sich die folgende Betrachtung daher auf Log-basierte Verfahren. Zwei mögliche Extreme stellen hier {\pl} und {\ol} dar, während sich {\cl} als interessanter Kompromiss dieser Ansätze darstellt.

%Dies ist ein Unterschied zum Beispiel zu Grid-Computing-Systemen, die {\idr} erst am Ende eines Vorgangs für die Übermittlung von Ergebnissen mit der Außenwelt kommunizieren. In diesen Systemen kommen daher oft Checkpointing-basierte Verfahren zum Einsatz. Allerdings sind rein Checkpointing-basierte Verfahren in Systemen, die häufig {\oc}s durchführen, wenn überhaupt, nur bedingt geeignet, da ein {\oc} entweder gar nicht unterstützt wird, wie im Falle des {\acp}, oder sehr ineffizient ist, wie im Falle von {\scp} bzw. {\cicp}. Die folgende Betrachtung beschränkt sich daher auf Log-basierte Verfahren. Zwei mögliche Extreme stellen hier \emph{{\pl}} und \emph{{\ol}} dar, während sich {\cl} als interessanten Kompromiss dieser Ansätze darstellt.

\sidenote{Ausschluss von {\ol}} Während {\pl} Log-Einträge unverzüglich auf einem {\stst} sichert und damit eine größere Latenz im fehlerfreien Betrieb in Kauf nimmt, sichert {\ol} Einträge asynchron auf dem {\stst}. Dies hat den Vorteil, dass der Kommunikationsoverhead im fehlerfreien Betrieb {\idr} geringer ist als beim {\pl}. Allerdings lässt {\ol} die Entstehung temporär verwaister Prozesse zu, wodurch ein größerer Aufwand im Recovery-Fall hingenommen werden muss und der {\oc} aufgrund des synchronen Zugriffs auf das {\stst} und der mitunter hinzukommenden Multi-Node-Abstimmung vergleichsweise langsam abläuft (siehe Abschnitt \ref{sec:Optimistic_Logging}). Weiterhin ist es möglich, dass eine vom {\oc} indirekt betroffene {\ru} ausgefallen ist, ihr Ausfall jedoch noch nicht bemerkt wurde. Der Kontaktierungsversuch würde erst nach einem Timeout abgebrochen. Allerdings würde der \emph{gesamte} laufende {\oc} derweil blockieren. Da im betrachteten System sehr häufig {\oc}s durchgeführt werden, wird {\ol} daher aus der weiteren Betrachtung ausgeschlossen.

Tabelle \ref{tab:Eignung der Protokolle} fasst die in diesem Abschnitt getroffenen Überlegungen nochmals zusammen. Aufgrund der gewonnenen Erkenntnisse beschränkt sich die weitere Betrachtung auf den möglichen Einsatz von {\pl} oder {\cl} als Alternative. Da jedoch auch für {\cl} gilt, dass ein asynchroner Zugriff auf das {\stst} nur möglich ist, wenn kein {\oc} durchgeführt wird, ist es fraglich ob sich der Einsatz des aufwendigeren {\cl} im Vergleich zum einfachen {\pl} im betrachteten System lohnt. Diese Frage soll im Folgenden durch eine nähere Evaluierung der beiden Verfahren beantwortet werden.

\begin{table}[htbp]
\begin{center}
\begin{tabularx}{15cm}{p{3.7cm}p{1.8cm}X}
  \toprule
  \rowcolor{dunkelgrau}
  \textbf{Verfahren} & \textbf{Eignung} & \textbf{Anmerkung} \\
  \midrule
  \rowcolor{hellgrau1}
  {\acp} & ungeeignet & Kein {\oc} möglich. \\
  \rowcolor{hellgrau2}
  {\scp} & ungeeignet & {\oc} sehr ineffizient. \\
  \rowcolor{hellgrau1}
  {\cicp} & ungeeignet & {\oc} sehr ineffizient. \\
  \rowcolor{hellgrau2}
  {\pl} & geeignet & Logging erfolgt stets synchron. Entstehung von Latenzzeiten.\\
  \rowcolor{hellgrau1}
  {\ol} & bedingt geeignet & {\oc} vergleichsweise ineffizient. Node-übergreifende Abstimmung beim {\oc} erforderlich.\\
  \rowcolor{hellgrau2}
  Manetho ({\cl}) & geeignet & Vergleichsweise aufwendig. Asynchroner Zugriff auf {\stst} nur möglich, wenn kein {\oc} durchgeführt wird. \\
  \rowcolor{hellgrau1}
  FBL ({\cl}) & ungeeignet & Funktioniert nicht bei mehreren gleichzeitigen Ausfällen. \\
  \bottomrule
\end{tabularx}
\setzeBreite
\caption{Eignung der Protokolle.} \label{tab:Eignung der Protokolle}
\end{center}
\end{table}

% ----------------------------------------------------------------------------
\subsection{Lazy {\oc}}
\label{sec:Lazy_OC}

\sidenote{Idee des Lazy {\oc}} In diesem Abschnitt wird mit dem \emph{Lazy {\oc}} eine im Rahmen der vorliegenden Arbeit entstandene Anpassung von {\rr}-Protokollen an Proxy-basierte Systeme vorgestellt. Der Lazy {\oc} stellt eine Verbesserung für Protokolle dar, die beim {\oc} über einen {\trans} einen synchronen Zugriff auf das {\stst} erfordern, wie es {\zb} beim {\pl} der Fall ist. Hierbei wird ausgenutzt, dass Zustandsinformationen einer {\ru} bestehend aus {\trans} und Proxy \emph{redundant} sowohl im {\trans}, als auch im Proxy zur Verfügung stehen. Der sich ergebende Vorteil ist, dass unter bestimmten Umständen die Zeit für den Zugriff auf das {\stst} eingespart werden kann, da dieser \emph{asynchron} zum Zugriff auf den {\trans} durchgeführt werden kann.

\sidenote{Analyse} Um den Lazy {\oc} zu verstehen, muss zuerst beleuchtet werden, wie ein herkömmlicher {\oc} über einen {\trans} abläuft: Bei Verwendung von Protokollen wie SOAP wird jeder \emph{Action Request} durch einen \emph{Action Response} quittiert. Abbildung \ref{fig:Sequenzdiagramm_SOAP_Action_PL} zeigt die Verarbeitung einer SOAP-Action unter Anwendung von {\pl}. Betrachten wir zunächst Abbildung~\ref{fig:Sequenzdiagramm_SOAP_Action_PL_ohne_Trans}. Der Ablauf entspricht einem Aufruf einer Action von einem {\cp} auf einem herkömmlichen UPnP Device. Entsprechend dem Grundgedanken des {\pl} speichern sowohl das Device als auch der {\cp} die Determinanten jeder empfangenen Nachricht auf dem {\stst}, bevor sie sie verarbeiten. Abbildung~\ref{fig:Sequenzdiagramm_SOAP_Action_PL_mit_Trans} veranschaulicht diese Zusammenhänge unter Einbeziehung eines {\trans}s. Hier zeigt sich, dass durch die Verarbeitung der Antwort des {\trans}s ein \emph{weiterer} Logging-Vorgang des Proxys hinzukommt. Damit führt ein Proxy bei einem einzelnen Aufruf einer Action durch einen {\cp} aufgrund der {\trans}-Interaktion \emph{zwei} synchrone Zugriffe auf das {\stst} durch.

\begin{figure}[htbp]
  \begin{center}
    \subfigure[Ohne Einbeziehung des {\trans}s.]
    {
      \label{fig:Sequenzdiagramm_SOAP_Action_PL_ohne_Trans}
      \includegraphics[width=16cm]{fig/diagramme/Sequenzdiagramm_SOAP_Action_PL.pdf}
    }
    \subfigure[Mit Einbeziehung des {\trans}s.]
    {
      \label{fig:Sequenzdiagramm_SOAP_Action_PL_mit_Trans}
      \includegraphics[width=16cm]{fig/diagramme/Sequenzdiagramm_SOAP_Action_PL_Trans.pdf}
    }
    \vspace{1cm}
    \setzeBreite
    \caption[Verarbeitung eines SOAP-Requests.]{Verarbeitung eines SOAP-Requests bei Verwendung von {\pl}.}
    \label{fig:Sequenzdiagramm_SOAP_Action_PL}
  \end{center}
\end{figure}

\sidenote{Was geschieht beim Lazy {\oc}?} Wie in Abbildung~\ref{fig:Sequenzdiagramm_SOAP_Action_PL_Lazy} dargestellt, erfolgt der Zugriff auf den {\trans} beim Lazy {\oc} asynchron zum Zugriff auf das {\stst}. Weiterhin wird nach Erhalt der Antwort des {\trans}s kein weiterer Logging-Vorgang durchgeführt. Solange der Zugriff auf den {\trans} gleich viel oder mehr Zeit in Anspruch nimmt, als der Zugriff auf das {\stst}, fällt der Logging-Vorgang zeitlich nicht mehr ins Gewicht. In diesem Fall wird die Zeit für einen Zugriff auf das {\stst} also komplett eingespart. Tabelle \ref{tab:Faelle_beim_Lazy_OC} betrachtet alle möglichen Ausfallszenarien beim Lazy {\oc} und zeigt, dass in keinem Fall die Konsistenz des Systems beeinträchtigt wird. Die einzige Bedingung, die an das Verfahren gestellt werden muss, ist, dass der {\trans} in der Lage sein muss, den Zustand des Proxys komplett zu sichern, da sonst unter bestimmten Umständen (\emph{Fall 3}) keine Konsistenz mit der Außenwelt garantiert werden kann.

\begin{figure}[htbp]
  %\begin{center}
  \hspace{-.5cm}
    \includegraphics[width=16cm, angle=0]{fig/diagramme/Sequenzdiagramm_SOAP_Action_PL_Lazy.pdf}
    \setzeBreite
    \caption{Lazy {\oc}.}
    \label{fig:Sequenzdiagramm_SOAP_Action_PL_Lazy}
  %\end{center}
\end{figure}

\sidenote{Wann ist Zugriff auf das {\stst} schneller?} Es bleibt zu klären, warum davon ausgegangen werden kann, dass der Zugriff auf den {\trans} {\idr} mehr Zeit in Anspruch nimmt, als der Zugriff auf das {\stst}: Ein Action Request $r_{proxy}$, der von einem {\cp} an den Proxy gesendet wird, enthält neben dem Namen der aufzurufenden Action $n_{action}$ auch einen Payload $p$. Der Payload kann aufgeschlüsselt werden in einen Teil, der lediglich dem Proxy zugestellt wird $p_{proxy}$ und einen Teil $p_{trans}$, der an den {\trans} durchgereicht wird. Formal: $$ r_{proxy} = n_{action} + p_{trans} + p_{proxy} $$

\sidenote{Regelfall} In der Regel gilt $p_{proxy} = 0$. Damit entspricht die Größe der Determinate, die vom Proxy auf das {\stst} gelogged wird, in etwa der Größe der Nachricht an den {\trans}. Da davon auszugehen ist, dass bei der \emph{schmalbandigen} Anbindung des {\trans}s der Zugriff auf den {\trans} $t_{transcomm}$ zuzüglich der Zeit für den {\oc} $t_{commit}$ mehr Zeit in Anspruch nimmt, als der Logging-Vorgang des Proxy, fällt dieser zeitlich nicht ins Gewicht: $$ t_{logging} < t_{transcomm} + t_{commit} $$

\sidenote{Sonderfälle} In einigen Fällen mag dies nicht zutreffen: Nämlich dann, wenn ein exklusiver Payload an den Proxy $p_{proxy}$ existiert, der gelogged werden muss oder, falls das {\stst} so langsam ist, dass der Logging-Vorgang entsprechend mehr Zeit in Anspruch nimmt. Allerdings macht dieser Fall die Anwendung des \emph{Lazy {\oc}} nicht unmöglich, sondern reduziert lediglich seine Wirkung. Schließlich wird auch in diesem Fall immer noch Zeit gewonnen, da der Zugriff auf den {\trans} und der Logging-Vorgang asynchron ablaufen.

\begin{table}[htbp]
\scriptsize
\begin{tabularx}{15cm}{rcp{.5cm}p{.5cm}Xr}

  \toprule
  \rowcolor{dunkelgrau}
  \textbf{\rotatebox{90}{Fall Nr.}} & \textbf{Ausfall} & \textbf{\rotatebox{90}{Committed}} & \textbf{\rotatebox{90}{Gelogged}} & \textbf{Auswirkung} & \textbf{\rotatebox{90}{Zulässig}}\\
  \midrule

  \rowcolor{hellgrau1}
  1 & Nur Proxy & ~ & ~ & Entspricht einer verlorenen Nachricht des {\cp}s an den Proxy. Nach dem Neustart des Proxys muss der {\cp} den Aufruf erneut schicken. & \checkmark \\

  \rowcolor{hellgrau2}
  2 & Nur Proxy & ~ & \checkmark & Der Proxy startet neu und führt einen Replay mit Hilfe des {\stst} durch. Danach ist sein Status zum Rest des Systems konsistent. & \checkmark \\

  \rowcolor{hellgrau1}
  3 & Nur Proxy & \checkmark & ~ & Der Proxy startet neu und führt einen Replay mit Hilfe des {\trans}s durch. Dies ist allerdings nur möglich, sofern der {\trans} den kompletten Status des Proxys sichern kann. & (\checkmark) \\

  \rowcolor{hellgrau2}
  4 & Nur Proxy & \checkmark & \checkmark & Entspricht \emph{Fall 2}. & \checkmark \\

  \rowcolor{hellgrau1}
  5 & {\trans} & ~ & ~ & Als Folge des {\trans}-Ausfalls wird der Proxy beendet. Entspricht damit \emph{Fall 1} mit dem Unterschied, dass {\trans} und Proxy das System endgültig verlassen. & \checkmark \\

  \rowcolor{hellgrau2}
  6 & {\trans} & ~ & \checkmark & Entspricht einer verlorenen Nachricht an die Außenwelt. Der Proxy würde als Folge des ausgefallenen {\trans}s beendet und zuvor eine Fehlermeldung an den {\cp} senden. & \checkmark \\

  \rowcolor{hellgrau1}
  7 & {\trans} & \checkmark & ~ & Der Ausfall des {\trans}s geschieht \emph{nach} Abschluss der Operation. Der Proxy wird aufgrund des {\trans}-Ausfalls beendet. & \checkmark \\

  \rowcolor{hellgrau2}
  8 & {\trans} & \checkmark & \checkmark & Entspricht \emph{Fall 7}. & \checkmark \\

  \rowcolor{hellgrau1}
  9 & Beide & ~ & ~ & Entspricht einer verlorenen Nachricht des {\cp}s an den Proxy. {\trans} und Proxy verlassen das System allerdings endgültig. & \checkmark \\

  \rowcolor{hellgrau2}
  10 & Beide & ~ & \checkmark & Entspricht \emph{Fall 9}. & \checkmark \\

  \rowcolor{hellgrau1}
  11 & Beide & \checkmark & ~ & Der Ausfall der Komponenten geschieht \emph{nach} Abschluss der Operation. & \checkmark \\

  \rowcolor{hellgrau2}
  12 & Beide & \checkmark & \checkmark & Entspricht \emph{Fall 11}. & \checkmark \\

  \bottomrule

\end{tabularx}
\setzeBreite
\caption[Mögliche Ausfallszenarien beim Lazy {\oc}.]{Mögliche Ausfallszenarien beim Lazy {\oc}. (\emph{Committed}: {\oc} durchgeführt. \emph{Gelogged}: Determinante der Nachricht auf dem {\stst} gesichert.)}
\label{tab:Faelle_beim_Lazy_OC}
\end{table}

% ----------------------------------------------------------------------------
\subsection{Aufbau eines UPnP-basierten Storage-Dienstes}
\label{sec:Stable_Storage_Aufbau}

\enlargethispage{-.5cm}

\sidenote{Aufgabe des Storage} Recovery Units sind auf ein \emph{Storage} angewiesen, mit dessen Hilfe sie Checkpoint- bzw. Log-Daten ablegen können. Von einem \emph{{\stst}} sprechen wir dann, wenn sichergestellt ist (oder davon ausgegangen wird), dass die abgelegten Daten nicht verloren gehen können. In diesem Abschnitt wird der Aufbau eines Storage-Dienstes für das im Rahmen der vorliegenden Arbeit entstandene System beschrieben. Dabei wird ausschließlich die Problematik des Zugriffs auf das Storage betrachtet, jedoch nicht, auf welche Weise Daten ausfallsicher verwahrt werden können. Da jedoch davon auszugehen ist, dass ein Storage auf einem leistungsfähigen Host im Netzwerk realisiert wird, können gängige Verfahren wie {\zb} RAID-Festplattenarrays eingesetzt werden, um Log-Daten bzw. Checkpoints sicher zu verwahren. Im Folgenden werden daher die Begriffe "`Storage"' und "`{\stst}"' als Synonyme verwendet.

\sidenote{Konzept des Storage} Das Storage muss von allen Geräten in der Netzgemeinschaft gefunden werden können. Aus diesem Grund liegt es nahe, Discovery-Mechanismen einzusetzen, um das Storage im System bekannt zu machen. Im Rahmen der vorliegenden Arbeit wurde hierfür, wie im gesamten System, UPnP verwendet. Geräte können damit gezielt nach einem Storage-Device im System suchen. Sobald ein Gerät eine Verbindung zu dem Storage geöffnet hat, kann es seine Checkpointing- bzw. Log-Daten dort ablegen. Dabei wird jedem Gerät ein "`privater"' Storage-Dienst zur Verfügung gestellt. Die Architektur des Storage ist dabei unabhängig von der Art der Daten, die dort abgelegt werden. Damit ist es Sache des jeweiligen Gerätes, welche Daten es in welcher Form dort ablegt.

\sidenote{Performanz textbasierter Protokolle} Sofern die verwendete Middleware keine binären Protokolle verwendet, so wie es bei UPnP der Fall ist, ist sie nur bedingt für den Transport der eigentlichen Log-Daten geeignet. Würde {\zb} für jeden Ablagevorgang von Log-Daten eine neue UPnP-Verbindung aufgebaut, so würden pro Vorgang Latenzzeiten in Höhe von ca. 70 Millisekunden anfallen -- wird hingegen ein binäres Protokoll direkt auf einer TCP-Verbindung verwendet, so fallen Latenzzeiten von unter zehn Millisekunden an, wie in Abbildung~\ref{fig:Diagramm_Latenz_Action} gezeigt.\footnote{Gemessen wurde in einem herkömmlichen 100 Mb/s LAN und in einem 54 Mb/s WLAN. Wie man an den geringen Zeitunterschieden zwischen der LAN- und der WLAN-Verbindung sehen kann (Abbildung \ref{fig:Diagramm_Latenz_Action}), wird bei Anwendung von UPnP die meiste Zeit für die Aufbereitung der XML-Daten benötigt, während die eigentliche Datenübertragung zeitlich kaum ins Gewicht fällt. Die Messung fand auf Grundlage des Java-basierten Infineon UPnP-Stacks statt.} Dieses Problem lässt sich jedoch mit Hilfe von \emph{Out-of-Band}-Verbindungen\footnote{Mit einer \emph{Out-of-Band}-Verbindung ist im Zusammenhang mit UPnP eine reine TCP-Verbindung ohne Verwendung des SOAP-Protokolls gemeint.} umgehen, wie es {\zb} bei \emph{UPnP-AV} \cite{upnp_av} im Rahmen von Multimedia-Anwendungen praktiziert wird.

\vspace{.5cm}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=8cm,angle=0]{fig/auswertung/Latenz_Action.pdf}
    \setzeBreite
    \caption{Latenzzeiten der UPnP Actions.}
    \label{fig:Diagramm_Latenz_Action}
  \end{center}
\end{figure}

\sidenote{Abwicklung der AOB-Kommunikation} Damit wird UPnP lediglich dazu verwendet, das Storage im Netzwerk zu finden und eine {\ru} an-, bzw. abzumelden. Der genaue Ablauf ist in Abbildung \ref{fig:Sequenzdiagramm_Storage} dargestellt: Nachdem eine RU den Storage-Dienst im Netzwerk gefunden hat, ruft sie die Action \emph{Register} auf und übergibt ihre eigene UUID als Kennung. Das Storage liefert der RU anschließend die Nummer eines der RU exklusiv bereitgestellten TCP-Ports zurück. Über diesen Port kann die RU eine TCP-Verbindung aufbauen und beliebige Datensätze auf dem Storage ablegen. Auf welche Weise die Nutzdaten strukturiert werden, ist allein Sache der {\ru}.\footnote{Allerdings muss die RU signalisieren, ob es sich bei einem Datensatz um einen Checkpoint oder einen Log-Eintrag handelt. Hierzu kann {\zb} das erste Bit einer jeweiligen Übertragung verwendet werden.} Über einen Aufruf der Action \emph{Goodbye} kann sich die RU ordnungsgemäß vom Storage abmelden.

%Es wurde Wert darauf gelegt, das Protokoll zum Ablegen der Datensätze so einfach wie möglich zu halten. Pro Datensatz wird eine TCP-Verbindung aufgebaut. Das erste Bit der Übertragung gibt an, ob es sich bei dem folgenden Datensatz um einen neuen Checkpoint oder einen Log-Eintrag handelt.

\vspace{.5cm}

\begin{figure}[htbp]
  %\begin{center}
  \hspace{2.5cm}
    \includegraphics[width=11cm,angle=0]{fig/diagramme/Sequenzdiagramm_Storage.pdf}
    \setzeBreite
    \caption[Zugriff auf das Storage.]{Zugriff auf das Storage im fehlerfreien Betrieb sowie beim Recovery.}
    \label{fig:Sequenzdiagramm_Storage}
  %\end{center}
\end{figure}

\sidenote{Recovery} Um nach einem Neustart einen Recovery-Vorgang durchführen zu können, meldet sich die {\ru} über die Action \emph{Recover} am Storage an. Als Parameter werden die UUID der RU sowie die Nummer eines Server-Ports angegeben, auf dem die RU die Daten ihres letzten Checkpoints bzw. ihre Log-Daten erwartet. Der erste Datensatz, den die RU vom Storage empfängt, ist der zuletzt abgelegte Checkpoint. Sobald sie ihren Status entsprechend den Informationen im Checkpoint wiederhergestellt hat, ruft die RU die Action \emph{Get\_Next} unter Angabe ihrer UUID auf dem Storage auf und bekommt den ersten Eintrag des Logs. Mit jedem Aufruf von \emph{Get\_Next} wird ein weiterer Log-Eintrag gesendet. Ist kein weiterer Log-Eintrag vorhanden, wird der String \texttt{END\_OF\_LOG} zurückgeliefert und der Vorgang ist abgeschlossen. Danach meldet sich die RU wieder über die Action \emph{Register} am Storage an und nimmt ihre Arbeit wieder auf.

\sidenote{Was muss gesichert werden?} Abbildung \ref{fig:Zustandssicherung} zeigt für die Erstellung von Checkpoints sicherungsrelevante Komponenten eines UPnP-Gerätes. Diese Komponenten sind zum einen die Statusvariablen, die für andere Komponenten sichtbar sind. Zum anderen kann jedes Gerät eine beliebige Menge an weiteren applikationsspezifischen Zustandsinformationen besitzen, die gesichert werden müssen. Ausgehend von einem \emph{UPnP Root Device} ist die Sicherung dieser Daten für jedes eingebettete Gerät vorzunehmen. %In welchem Format eine RU Checkpointing- bzw. Log-Daten auf dem Storage ablegt, ist Sache des RUs. Allerdings kann durch ein effizientes Ablageverfahren das Datenaufkommen im Storage reduziert werden. Hier bietet sich ein inkrementelles Ablegen von Daten an, wonach ein Datensatz $D_i$ lediglich die Differenz aus den Zustandsdaten $Z_i - Z_{i-1}$ enthält. Um ein Auslesen der Daten wiederum effektiv zu gestalten, wird in gewissen Abständen ein kompletter Datensatz abgelegt.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=12cm,angle=0]{fig/Zustandssicherung.png}
    \setzeBreite
    \caption{Zu sichernde Komponenten eines UPnP-Gerätes.}
    \label{fig:Zustandssicherung}
  \end{center}
\end{figure}

% ----------------------------------------------------------------------------
\section{Evaluierung von {\pl} und {\cl}}

\sidenote{Annahmen} Tabelle \ref{tab:Determinante_PLogging} zeigt, welche Datenmengen im Rahmen der folgenden Betrachtungen für Log-Einträge und Checkpoints angenommen wurden. Für einen typischen Aufruf eines Kommandos mit Parametern werden ca. 20 - 40 Byte angenommen. Eine im Log abzulegende Determinante enthält neben dem Inhalt der Nachricht die 28 Byte lange UUID des Senders sowie 8 Byte für eine zusätzliche Event-ID. Die Größe der Determinate wird daher mit 80 Byte überschlagen. Für einen Checkpoint, der die vollständigen Statusinformation einer {\ru} zu einem Zeitpunkt enthält, wurden großzügig 20 kB angesetzt.

\begin{table}[htbp]
\begin{center}
\begin{tabularx}{15cm}{lXl}
  \toprule
  \rowcolor{dunkelgrau}
  \textbf{Bezeichnung} & \textbf{Beschreibung} & \textbf{Größe}\\
  \midrule
  \rowcolor{hellgrau1}
  \emph{SenderID} & ID des Senders der Nachricht (UPnP UUID) & 28 Byte \\
  \rowcolor{hellgrau2}
  \emph{EventID} & ID, die die Reihenfolge der Events angibt & 8 Byte \\
  \rowcolor{hellgrau1}
  \emph{MessageContent} & Funktionenname + Aufrufparameter & 20 - 40 Byte \\
  \rowcolor{hellgrau2}
  \emph{CheckpointData} & Kompletter Status-Record einer RU & 20 kB \\
  \bottomrule
\end{tabularx}
\setzeBreite
\caption{Datenvolumen für Log-Einträge und Checkpoints.}
\label{tab:Determinante_PLogging}
\end{center}
\end{table}

\minisec{Zugriffslatenzen}

\sidenote{Setup} Für die Messungen der Latenzzeiten beim Zugriff auf das im letzten Abschnitt vorgestellte {\stst} wurde ein Setup bestehend aus zwei herkömmlichen PCs (1,6 und 2,5~GHz) verwendet, die über ein 100 Mbit/s LAN verbunden wurden. Die Referenzimplementierung des Storage-Dienstes wurde unter Verwendung der Java Standard Edition~6 vorgenommen. Wie in Abschnitt \ref{sec:Stable_Storage_Aufbau} beschrieben, erfolgt ein Zugriff auf das {\stst} direkt über eine TCP-Verbindung ohne Verwendung des SOAP-Protokolls. Ein einzelner Logging-Vorgang (80 Byte Log-Daten) nimmt ca. 5 ms in Anspruch. Ein Checkpoint mit einen Umfang von 20 kB wird in unter 15 ms verarbeitet.\footnote{Hier wird der Einfluss der Netzlatenz deutlich, da die Übermittlung des kleineren Datensatzes nur unverhältnismäßig weniger Zeit in Anspruch nimmt. Bei der Messung wurde nicht die Zeit zum Ablegen der Daten auf einem permanenten Datenspeicher wie einer Festplatte berücksichtigt.} Der Einfachheit halber wird im Folgenden eine Zugriffsdauer von rund 10 ms auf das {\stst} veranschlagt.

% Müsste theoretisch schneller sein: 100 Mbit LAN bedeutet 100.000 kbit/s oder 12.500 kB/s also ca. 12 MB/s. Durch Protokolloverhead geht die Hälfte runter. Also bleiben 6 MB/s = 6144 kB/s. Also wird für ein kB 0,00016 s benötigt = 0,16 ms. Bei 20 kB braucht man 3.2 ms. Der Rest ist also Overhead durch Netzlatenz u. Java...

\sidenote{Zugriffsdauer auf den {\trans}} Da im zeitlichen Rahmen der vorliegenden Arbeit keine Referenz-Hardware eines {\trans}s verfügbar war, kann die Dauer für einen Zugriff auf den {\trans} lediglich überschlagen werden: Wenn eine einfache Kommandonachricht von 20 Bytes an den {\trans} geschickt wird, so werden für die einfache Übertragung bei einer Nutzdatenrate von 30~kbit/s ca. 5 ms (ohne Latenz) für die reine Datenübertragung in eine Richtung benötigt. Für die Gesamtdauer, bis eine Bestätigung vom {\trans} erhalten wird, werden daher 10 ms veranschlagt: $$t_{trans} = 10~ms$$

%Da beim Lazy {\oc} der Zugriff auf das {\stst} asynchron zum Zugriff auf den {\trans} erfolgt, fällt der Zugriff auf das {\stst} somit kaum ins Gewicht. Die durch einen einfachen Aufruf eines Kommandos durch das {\pl} hervorgerufene Latenz beträgt damit unter 10 ms (nur Zugriff vom {\cp} auf das {\stst}).

\sidenote{Gesamtlatenz bei PL} Bei Verwendung von \emph{\pl} und dem \emph{Lazy {\oc}} wird pro Kommunikationszyklus insgesamt zweimal auf das {\stst} zugegriffen: Einmal, beim eigentlichen {\oc} durch den Proxy und einmal durch den {\cp} nach Erhalt der Bestätigungsnachricht (siehe Abbildung~\ref{fig:Sequenzdiagramm_SOAP_Action_PL_Lazy}). Der Zugriff auf das {\stst} durch den Proxy wird allerdings zeitlich überlagert durch den zeitintensiveren asynchronen Zugriff auf den {\trans} und wirkt sich auf den Gesamtzeitbedarf nicht aus. Damit ergibt sich insgesamt eine Latenz von 10 ms für den Logging-Vorgang: $$t_{logging-PL} = 10~ms$$

%Da für den Zugriff auf den {\trans} ebenfalls 10 ms angesetzt wurden, ergibt sich eine Gesamtzugriffszeit von 20 ms.

\sidenote{Gesamtlatenz bei CL} Beim {\oc} im Falle des \emph{\cl} muss der Antezedenzgraph auf dem {\stst} abgelegt werden. Hierfür werden wieder rund 10 ms angesetzt. Damit entsteht bei Durchführung des {\oc} über den {\trans} eine durch das {\cl} hervorgerufene Gesamtlatenz von ca. 10 ms, während in den Fällen, in denen der Proxy eine Anfrage selbst beantworten kann und damit kein {\oc} durchgeführt wird, keine Latenz durch Anwendung des {\cl} entsteht. Unter der Annahme, dass der Proxy die Hälfte aller Anfragen eigenständig beantworten kann, entsteht eine gemittelte Gesamtlatenz bei Anwendung von {\cl} von 5 ms: $$\bar t_{logging-CL} = 5~ms$$

\sidenote{Gesamtzugriffszeit} Die Gesamtzugriffszeit beim Aufruf einer Aktion von einem {\cp} an einen {\trans} kann nun wie folgt überschlagen werden, wobei für den Zugriff über UPnP $t_{upnp} = 70~ms$ angenommen werden (siehe Abbildung \ref{fig:Diagramm_Latenz_Action}):

$$ t_{gesamt} = t_{upnp} + t_{trans} + t_{logging} $$

Bei {\pl}: $$ 70~ms + 10~ms + 10~ms = 90~ms $$

Bei {\cl}: $$ 70~ms + 10~ms + 5~ms = 85~ms $$

\sidenote{Resume} Bei dieser Überlegung wird die Verarbeitungszeit des Transceivers nicht berücksichtigt. Setzt man für die maximal zulässige Gesamtdauer einer Aktion 200 ms an\footnote{Bis zu diesem empirisch ermittelten Wert empfindet ein Benutzer die Antwort einer Aktion als \emph{unmittelbar}.}, so verbleiben in beiden Fällen gut 100 ms für die Verarbeitung des Kommandos durch den {\trans}. Insgesamt zeigt sich, dass unter den gegebenen Anforderungen und Systemeigenschaften bzgl. der Zugriffslatenz kein nennenswerter Vorteil durch Einsatz des {\cl} Protokolls gegenüber {\pl} zu erzielen ist.

\minisec{Kommunikationsoverhead}

\sidenote{Einleitung} Es wurde weiterhin untersucht, welcher Overhead bei der Anwendung von {\pl} im Vergleich zum Manetho-Protokoll ({\cl}) entsteht. Hierzu wurde eine Simulationsumgebung auf Basis der \emph{Diskreten-Event-Simulation} eingesetzt, die im Rahmen der vorliegenden Arbeit entwickelt wurde.% Eine Beschreibung der Architektur der Simulationsumgebung befindet sich in Anhang \ref{sec:Anhang_Architektur_des_Simulators}.

\enlargethispage{.5cm}

\sidenote{Setup und Annahmen} Es wurde angenommen, dass hinter jedem Proxy, der eine Nachricht empfängt, ein {\trans} steht und in 50 \% der Fälle die Nachricht an den {\trans} weitergeleitet und ein {\oc} durchgeführt wird.\footnote{Das heißt, bei Anwendung des Manetho-Protokolls muss der aktuelle Antezedenzgraph extra auf dem {\stst} gesichert werden.} Die Simulation wurde für 2 bis 10 Proxies durchgeführt, die entsprechend einem zufälligen Muster miteinander kommunizieren. Dabei wurde angenommen, dass jeweils doppelt so viele Nachrichten ausgetauscht werden, wie Proxies im System vorhanden sind. Bei 10 Proxies werden also 20 Kommandonachrichten ausgetauscht. Für die Bestimmung der anfallenden Datenmenge beim Manetho-Protokoll wurde jeweils über fünf Messungen gemittelt, da diese von dem jeweiligen Kommunikationsmuster abhängt. Neben der Betrachtung des einfachen Manetho-Protokolls wurden verschiedene Verbesserungs\-möglichkeiten, wie ein inkrementelles Senden der Antezedenzgraphen sowie periodisches Checkpointing untersucht \cite{el92_manetho}. Beim {\pl} wurde entsprechend den Abbildungen \ref{fig:Sequenzdiagramm_SOAP_Action_PL_mit_Trans} und \ref{fig:Sequenzdiagramm_SOAP_Action_PL_Lazy} der normale {\oc} mit dem Lazy {\oc} verglichen. Für die jeweiligen Nachrichtenlängen wurden die Werte gewählt, die in Tabelle \ref{tab:Determinante_PLogging} vorgestellt wurden.

\begin{sidewaysfigure}[htbp]
  \begin{center}
    \subfigure[Absoluter Overhead.]
    {
      \label{fig:Diagramm_Manetho_vs_PLogging_abs}
      \includegraphics[width=10cm]{fig/auswertung/Overhead_Manetho_vs_PLogging_abs.pdf}
    }
    \subfigure[Relativer Overhead.]
    {
      \label{fig:Diagramm_Manetho_vs_PLogging_rel}
      \includegraphics[width=10cm]{fig/auswertung/Overhead_Manetho_vs_PLogging_rel.pdf}
    }
    \subfigure[Optimale Checkpoint-Rate.]
    {
      \label{fig:Diagramm_Speicherrate}
      \includegraphics[width=10cm]{fig/auswertung/Checkpoint_Speicherrate.pdf}
    }
    \subfigure[Overhead vs. Nachrichtengröße.]
    {
      \label{fig:Diagramm_Nachrichtengroesse}
      \includegraphics[width=10cm]{fig/auswertung/Overhead_vs_Nachrichtengroesse.pdf}
    }
    \vspace{.5cm}
    %\setzeBreite
    \caption[Vergleich des Overheads.]{Vergleich des Overheads von Manetho (\cl) und {\pl}.}
    \label{fig:Diagramm_Manetho_vs_PLogging}
  \end{center}
\end{sidewaysfigure}

%\enlargethispage{.5cm}

\sidenote{Ergebnisse} Die Ergebnisse der Untersuchungen sind in den Abbildungen~\ref{fig:Diagramm_Manetho_vs_PLogging_abs} bis \ref{fig:Diagramm_Nachrichtengroesse} dargestellt. Abbildung \ref{fig:Diagramm_Manetho_vs_PLogging_abs} zeigt den absoluten Overhead des Manetho-Protokolls im Vergleich zu dem Overhead, der bei {\pl} entsteht. Es ist zu erkennen, dass der Overhead bei Manetho mit der Komplexität des zugrundeliegenden \emph{Kommunikationsmusters} steigt (nicht-linearer Anstieg): Wenn häufiger mit unterschiedlichen Partnern kommuniziert wird, entstehen mehr Abhängigkeiten zwischen den Kommunikationspartnern. Dies wirkt sich beim Manetho-Protokoll unmittelbar auf die Größe der Antezedenzgraphen aus. Wie zu erkennen ist, liegt der Overhead bei Manetho deutlich über dem von {\pl}. Selbst bei Anwendung verbesserter Verfahren wie inkrementelles Senden der Antezedenzgraphen und periodisches Checkpointing (über Checkpoints gesicherte Informationen müssen nicht mehr mit den Antezedenzgraphen gesendet werden) bleibt der Overhead des Manetho-Protokolls unter den gegebenen Randbedingungen deutlich größer als der von {\pl} -- zumal {\pl} durch Anwendung des Lazy {\oc} nochmals deutlich verbessert wird. Um eine geeignete Erstellungsrate der Checkpoints für das gegebene System bei Anwendung des Manetho-Protokolls zu ermitteln, wurde das Datenaufkommen bei verschiedenen Erstellungsraten ermittelt, wie in Abbildung~\ref{fig:Diagramm_Speicherrate} dargestellt. Schließlich wurde eine Rate von 4 (Erstellung des Checkpoints nach jeder 4. empfangenen Nachricht) für die weiteren Betrachtungen angenommen. Auch in Abbildung~\ref{fig:Diagramm_Manetho_vs_PLogging_rel} (relativer Overhead) lässt sich erkennen, dass die Größe der Antezedenzgraphen beim {\cl} stark abhängig ist vom Kommunikationsverhalten der Teilnehmer: Sofern die Teilnehmer in zufälligen Mustern (schwarze Linie) kommunizieren, entsteht mehr Overhead als bei geordneten Mustern (graue Linie).

\sidenote{Resume} Wie schon bei der Betrachtung der Zugriffslatenz zeigt sich auch hier, dass der Einsatz von {\cl} im Vergleich zum einfachen {\pl} unter den gegebenen Randbedingungen keinen Vorteil bietet -- zumal das Protokoll wesentlich komplexer ist als {\pl} und sein Einsatz damit mit entsprechend großem Aufwand verbunden ist. In der Literatur findet sich die Aussage, dass {\cl} einen geringeren Overhead erzeuge als {\pl} \cite{el92_manetho}. Diese Aussage ist richtig ab einer bestimmten Größe der übermittelten Nutzdaten: Erst wenn die Größe der Nachrichten bei {\pl} der Größe der Antezedengraphen des {\cl} im Mittel entspricht, erzeugen die Protokolle gleich viel Overhead. Dies ist in Abbildung~\ref{fig:Diagramm_Nachrichtengroesse} veranschaulicht. So würde bei dem gegebenen System der Einsatz des Manetho-Protokolls erst ab einer Nachrichtengröße von ca. 350 Byte lohnen. Unter den gestellten Annahmen liegt die Größe der Nachrichten jedoch im Bereich von unter 100 Byte.

% ****************************************************************************
\chapter{Systemintegration}

\sidenote{Worum geht es hier?} Auf Basis des im ersten Teil der vorliegenden Arbeit entwickelten Systems wurden im zweiten Teil dedizierte Fehlertoleranzerweiterungen entwickelt. Es bleibt zu klären, wie die drei entstandenen Komponenten, die Proxy-basierte Infrastruktur, die Mechanismen zur Migration von Proxies sowie die Unterstützung von {\rr}-Protokollen zwischen Proxies und ihren {\cp}s, möglichst nahtlos in ein Gesamtsystem integriert werden können.

\sidenote{Integrationskonzept} Bei der Integration kann ausgenutzt werden, dass die Durchführung der {\rr}-Verfahren intern zwischen den Proxies ({\bzw} den {\trans}n) und den {\cp}s geschieht und von den Proxies und {\cp}s \emph{aktiv} durchgeführt wird. Das heißt, für die {\am} findet die Durchführung der {\rr}-Verfahren transparent statt. Die Migration hingegen wird von den {\am}n bestimmt. Hier verhalten sich die Proxies passiv {\bzw} agieren erst auf Anweisung durch die {\am}. Dadurch sind beide Erweiterungen, die Migration und die {\rr}-Verfahren, klar voneinander abgegrenzte, modulare Komponenten, die der im ersten Teil der Arbeit entstandenen Infrastruktur bedarfsgerecht und in beliebiger Kombination hinzugefügt werden können.

\sidenote{Gesamtsystem} Das entstandene Gesamtsystem mit Proxy-Migration und {\rr}-Unter\-stütz\-ung ist in Abbildung \ref{fig:Gesamtszenarium} dargestellt. Im Unterschied zu Abbildung \ref{fig:Beispielszenarium} (Basissystem) ist ein Gerät hinzugekommen, das das in Abschnitt \ref{sec:Stable_Storage_Aufbau} vorgestellte {\stst} zur Verfügung stellt. Dieses Gerät kann einer der {\am} des Systems sein. Um zu entscheiden, welcher {\am} das {\stst} bereit stellt, können (abgesehen von einer manuellen Konfiguration) die in Abschnitt \ref{sec:Aushandlung_Proxy-Ausfuehrung} vorgestellten Aushandlungsverfahren eingesetzt werden. Alternativ können auch mehrere {\am} ein {\stst} bereit stellen.

\begin{sidewaysfigure}[htbp]
  \begin{center}
    \hspace{-1cm}
    \includegraphics[width=18cm,angle=0]{fig/Integrationsszenarium.pdf}
    %\setzeBreite
    \caption{Gesamtszenarium mit Migration und {\rr}.}
    \label{fig:Gesamtszenarium}
  \end{center}
\end{sidewaysfigure}

\sidenote{Wann lohnt Migration?} Es bleibt weiterhin zu klären, in welchen Fällen sich die Migration eines Proxys lohnt. Eine Alternative zur Migration liegt darin, den Ausfall eines Proxys einfach zuzulassen und seinen Zustand nach dem Neustart auf einem anderen Host durch den {\trans} oder ein angewendetes {\rr}-Verfahren wieder herzustellen. Durch den {\trans} kann der Zustand des Proxys generell nur dann wieder hergestellt werden, wenn der komplette Zustand des Proxys im Speicher des {\trans}s Platz findet. Doch selbst, wenn das der Fall ist, ist eine Übertragung der Zustandsdaten über das LAN im Rahmen der Migration schneller, als die Übertragung des Zustandes über die schmalbandige Verbindung zwischen {\trans} und Proxy -- zumal die Ressourcen des {\trans}s auf diese Weise nicht durch die Datenübertragung belastet werden. Würde ein {\rr}-Verfahren angewendet, um den Zustand des Proxys wieder herzustellen, so müsste der letzte Zustand in mehreren Schritten wieder angefahren werden, anstatt ihn in einem einzigen Vorgang wieder herzustellen, wie es bei einer Migration der Fall wäre. Dieses "`Anfahren"' ist in jedem Fall mit weiterem Kommunikationsoverhead verbunden wie dem Bezug der Antezedengraphen bei Anwendung des Manetho-Protokolls oder dem Neu-Senden von Nachrichten bei Einsatz von {\pl}. Zuletzt muss berücksichtigt werden, dass die Migration eines Proxys als Mittel zur Störungsvermeidung ein geordneter Vorgang ist, bei dem für die {\cp}s keine Störung sichtbar wird, während ein hingenommener Ausfall des Proxys unmittelbare Auswirkungen auf seine Kommunikationspartner haben kann.

% ****************************************************************************
\chapter{Fazit}
\label{sec:Fazit}

\sidenote{Zusammenfassung Teil 1} Der Fokus der vorliegenden Arbeit lag auf der Integration limitierter Geräte (sog. \emph{\trans}) in Service-orientierte Architekturen (SOA), die auf Middleware-Systemen aufbauen. Nachdem die Problematik aufgezeigt wurde, die zumeist Mikrocontroller-basierten {\trans} mit Middleware-Unterstützung auszustatten, wurde als gangbarer Weg die Verwendung von {\dproxies} gewählt: Jeder {\trans} bekommt einen Proxy zur Seite gestellt, der zum einen die Middleware-Anbindung für den {\trans} übernimmt, zum anderen aber auch applikationsspezifische Aufgaben des {\trans}s übernehmen kann. Um die Verwendung der {\dproxies} transparent zu gestalten, wurde im Rahmen der Arbeit ein System zur automatischen Lebenszyklusverwaltung von {\dproxies} entwickelt und für UPnP-basierte SOA implementiert. Die Kernkomponente dieses Systems, der \emph{{\am}}, ist Teil des \emph{Sindrion}-Systems, das mittlerweile in verschiedenen weiteren Forschungsprojekten eingesetzt wird.

\enlargethispage{-.5cm}

\sidenote{Zusammenfassung Teil 2} Generell wird die Ausfallwahrscheinlichkeit eines Systems durch den Einsatz von {\dproxies} ohne weitere Maßnahmen erhöht. Dies hat zwei Gründe: Zum einen fällt der Dienst eines {\trans}s nicht nur aus, wenn der {\trans} selbst ausfällt, sondern auch, wenn der zugehörige Proxy ausfällt. Zum anderen können beim Neustart eines Proxys Inkonsistenzen entstehen, die die System-Integrität beeinträchtigen. Um diesen Problemen zu begegnen wurden im Rahmen der Arbeit zwei Ansätze für die Vermeidung von {\bzw} den Umgang mit Störungen untersucht: Wenn der drohende Ausfall eines Proxys erkannt wird ({\zb} knappe Ressourcen des Hosts), so kann der Proxy zur Laufzeit auf einen anderen Host \emph{migriert} werden. Sofern der Ausfall eines Proxys sich nicht durch Migration vermeiden lässt oder spontan geschieht, wird er von einem {\am} automatisch neu gestartet. Um dabei mögliche Inkonsistenzen zu vermeiden, wurden \emph{{\rr}}-Verfahren eingesetzt. Hierzu wurden zuerst gängige {\rr}-Verfahren beleuchtet. Anhand einer Anforderungsanalyse wurden schließlich \emph{{\pl}} und \emph{{\cl}} als mögliche Kandidaten für den Einsatz als {\rr}-Protokolle für das betrachtete System ermittelt. Diese beiden Verfahren wurden im Anschluss eingehend evaluiert. Bei keinem der Verfahren wird der {\trans} weder zusätzlich belastet, noch muss er eine spezielle Unterstützung für die Verfahren mitbringen. Allerdings zeigte sich, dass das vermeintlich leistungsfähigere {\cl} seine Vorteile aufgrund der angenommenen häufigen Kommunikation mit der Außenwelt (\emph{\oc}) und den vergleichsweise kleinen Längen der übermittelten Nachrichten, nicht ausspielen kann. Ferner wurde gezeigt, dass der Overhead von {\pl} durch eine Anpassung an Proxy-basierte Systeme, die \emph{Lazy {\oc}} genannt wurde, erheblich verbessert werden konnte.

\sidenote{Anforderungen vom Anfang erfüllt} Damit können die in Abschnitt \ref{sec:Allgemeine_Anforderungen} gestellten Anforderungen als erfüllt betrachtet werden: So ist das entstandene System fähig zur Selbstkonfiguration, da limitierte Geräte automatisch erkannt, sowie Proxies automatisch bezogen und ausgeführt werden. Zuverlässigkeit ist zum einen Design-inhärent vorhanden, da Proxies {\zb} automatisch neu gestartet werden. Zum anderen wird Zuverlässigkeit durch dedizierte Fehlertoleranzmaßnahmen, wie die Migration von Proxies oder {\rr} erreicht. Zuletzt ist das entstandene System sehr nah an bestehende Standards angelehnt und in weiten Teilen sogar Standard-konform.

%Abschließend kann gesagt werden, dass die Robustheit eines Proxy-basierten Systems mit der eines Standalone-Systems durch die Anwendung von Verfahren zur Störungsvermeidung bzw. Störungsbehebung vergleichbar ist und die angewendeten Fehlertoleranzmaßnahmen die Effizienz des Systems nur unwesentlich beeinflussen. 