In Link-State Rechnernetzen ist es üblich, dass jeder Knoten die Topologie des gesamten Netzwerks kennt und auf dessen Basis die Routing-Entscheidungen treffen kann. Um die Performance und Qualität des Netzwerks zu erhöhen, ist meist eine Datenanalyse notwendig. Dabei werden beispielsweise Knoten und Verbindungen gefunden, die eine hohe Wichtigkeit für das gesamte Netzwerk haben. Durch die regelmäßige Aufzeichnung der Topologieinformationen an einer Stelle im Netzwerk kann ein Datenbestand geschaffen werden, der bei geeigneter Analyse Rückschlüsse auf Schwachstellen im Netzwerk geben kann. Aufgrund der großen Menge an Daten kann die Datenanalyse sehr viel Zeit in Anspruch nehmen, was die Nützlichkeit ihrer Ergebnisse in Frage stellen kann. Deshalb wurde in einer Publikation von Mundt und Vetterick im Juli 2011 die Rechenleistung mittels Cloud Computing verstärkt und der Zeitaufwand somit verringert. Leider hatte diese Methode auch Nachteile, wie beispielsweise den teuren Upload der großen Datenmengen in die Cloud. In diesem Buch wird für denselben Datenbestand die Performance erhöht, indem User Defined Functions (UDF) in einem Datenbankmanagementsystem eingesetzt werden. Die Daten werden direkt auf dem Datenbankserver analysiert und die Ergebnisse mit SQL abgefragt. Gleichzeitig wird die bestehende Implementierung untersucht und ihre Komplexität verringert. Im Ergebnis kann die Analyse nicht nur schneller, sondern auch komfortabler für den Anwender durchgeführt werden. Viele Arten der Datenanalyse der Netzwerktopologiedaten können nun mit SQL, ohne zusätzliche Programme durchgeführt werden. Am Ende des Buches werden mehrere Beispiele für Datenanfragen aufgeführt, die den Einsatz der neuen Funktionen zeigen und Hinweise zur Laufzeit geben.

Textprobe: Kapitel 4.1.1., Optimierung des Dijkstra-Algorithmus: Im Abschnitt 1.4 wurde bereits festgestellt, dass eine effiziente Implementierung des Dijkstra-Algorithmus nötig ist um die Ziele dieser Arbeit zu erreichen. Im Abschnitt 2.3.1 (Listing 2.2, Seite 18) wurde der Dijkstra-Algorithmus beschrieben. Der große Teil des Zeitaufwandes für den Algorithmus liegt darin, die unbenutzten von den bereits benutzten Knoten zu trennen, von den unbenutzten Knoten den Nächstgelegenen zu finden und von diesem dann wieder alle unbenutzten Nachbarn zu betrachten. Diese Form der Exploration kann sehr zeitaufwändig sein, wenn die dafür benutzen Datentypen nicht korrekt gewählt werden. Der Dijkstra-Algorithmus wurde mit der Komplexität O(n + n2 + m) angegeben. Dabei ist das erste n lediglich die Initialisierung, die sich nicht optimieren lässt. Es wird dafür gesorgt, dass alle Knoten in die vorgesehenen abstrakten Datentypen eingefügt, Anfangswerte auf 0 gesetzt bzw. noch nicht ermittelte Abstände mit 8 (‘unendlich’) initialisiert werden. Je nach verwendeter Programmiersprache und abhängig von dem Wert, den man für ‚unendlich’ festlegt (vgl. Abschnitt 4.2.4), ist die Initialisierung optional. Somit wird nur die Optimierung des Terms O(n2 + m) betrachtet. Für die Verwaltung der noch nicht behandelten Knoten, wurde die Prioritätswarteschlange Q verwendet. Auf dieser Warteschlange, müssen verschiedene Operationen (wie z. B. Einfügen, Minimum finden, Löschen) ausgeführt werden. Im Listing 2.2 (Seite 18) wurde zunächst angenommen, dass die Warteschlange mit einer einfach verketteten Liste implementiert ist. Damit sind alle Operationen (außer Löschen) mit dem Aufwand O(1) möglich. Zum Löschen wird jedoch lineare Zeit (O(n)) benötigt. Während das Finden des Minimums, mittels einer zusätzlichen Variable, immer in konstanter Zeit ausgeführt werden kann, ändern sich die Zeitkomplexitäten für die anderen Operationen je nach verwendeter Datenstruktur. So ist es beispielsweise möglich einen Heap zu verwenden und damit einen Zeitaufwand für jede Operation von O(log(n)) zu haben. Der Zeitaufwand für den Algorithmus von Dijkstra läge damit bei O((n + m) _ log(n)). Im Jahre 1987 fanden Fredman und Tarjan eine Möglichkeit Fibonacci-Heaps sehr effizient im Dijkstra-Algorithmus zu verwenden [16]. Mit einem Fibonacci-Heap ist das Einfügen in konstanter Zeit und das Löschen in O(log(n)) möglich. Weiterhin stellten sie für den Fibonacci-Heap verbesserte Laufzeiten in der amortisierten Laufzeitanalyse fest, wobei der Worst-Case O(log(n)) nur sehr selten eintrat. Für die meisten Durchläufe im gesamten Dijkstra-Ablauf sind die Kosten für das Löschen ebenfalls O(1). Nach dieser amortisierten Betrachtungsweise ist die Laufzeit für den Dijkstra-Algorithmus auf O(n _ log(n) + m) gesunken. Die Verwendung von Fibonacci-Heaps ist heute die gängigste Methode um kürzeste Pfade mit dem Dijkstra-Algorithmus zu berechnen. Die Java-Klasse PriorityQueue verwendet lediglich eine verkettete Liste (bzw. ein dynamisch wachsendes Array) und ist somit für die Verwendung im Dijkstra-Algorithmus nicht optimal. Die freie Graphen-Bibliothek JGraphT [23] bringt jedoch eine Implementierung des Dijkstra-Algorithmus und eine FibonacciHeap-Klasse mit sich. Der Dijkstra-Algorithmus wurde im Rahmen dieser Arbeit neu implementiert, weil er sehr einfach ist und weil die Implementierung von JGraphT nicht unverändert übernommen werden konnte. So berechnete JGraphT nur den Weg von einem Startknoten zu einem Zielknoten und bricht die Berechnung dann ab. Wie aber im Abschnitt 1.4 schon erwähnt, darf der Dijkstra in unserem Projekt nicht abbrechen, sondern muss immer die kürzesten Wege von einem Startknoten zu allen anderen Knoten finden. Die Klasse FibonacciHeap wurde jedoch zunächst in diese Arbeit übernommen. Die Verwendung des Fibonacci-Heaps brachte für die Graphen, die in dieser Arbeit Verwendung finden, signifikante Unterschiede und wurde deshalb in der endgültigen Version beibehalten.

• Datenbank

• Performanceoptimierung

• Mesh-Netzwerk

• Datenbankmanagementsystem

• Ad-hoc Netzwerk

• Informatik

Andreas Redmer studierte Informatik an der Universität Rostock. Seit seinem Abschluss im Jahre 2011 arbeitet er am Lehrstuhl für Datenbank- und Informationssysteme der Universität Rostock an seiner Doktorarbeit.