Effiziente Datenanalyse in Netzwerkgraphen: Durch User Defined Functions in PostgreSQL
Durch User Defined Functions in PostgreSQL
1st Edition
Published in August 2012
122 pages
978-3-8428-3161-2 (ISBN)
Description
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.
More details
Other editions
Additional editions
Andreas Redmer
Effiziente Datenanalyse in Netzwerkgraphen: Durch User Defined Functions in PostgreSQL
Durch User Defined Functions in PostgreSQL
Book
08/2012
1st Edition
Diplomica Verlag
€48.00
Shipment within 7-9 days
Person
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.
Content
1 - Effiziente Datenanalyse in Netzwerkgraphen:Durch User Defined Functions in PostgreSQL [Seite 1]
1.1 - Einleitung [Seite 3]
1.2 - Abstract [Seite 4]
1.3 - Inhaltsverzeichnis [Seite 5]
1.4 - Abbildungsverzeichnis [Seite 7]
1.5 - Tabellenverzeichnis [Seite 8]
1.6 - Verzeichnis der Listings [Seite 9]
1.7 - 1. Einleitung [Seite 11]
1.7.1 - 1.1. Aufbau der Arbeit [Seite 11]
1.7.2 - 1.2. Beschreibung des Mesh-Netzwerks als Graph [Seite 12]
1.7.3 - 1.3. Qualität der zu analysierenden Daten [Seite 13]
1.7.4 - 1.4. Ziel der Arbeit [Seite 17]
1.7.5 - 1.5. Vorausgesetzte Hard- und Software [Seite 20]
1.8 - 2. Stand der Technik [Seite 22]
1.8.1 - 2.1. Routing-Algorithmen [Seite 22]
1.8.2 - 2.2. Metriken [Seite 23]
1.8.3 - 2.3. Betrachtung der bestehenden Implementierung als Cloud-Service [Seite 24]
1.8.3.1 - 2.3.1. Algorithmische Komplexit¨at [Seite 25]
1.8.3.2 - 2.3.2. Vor- und Nachteile der Cloudl¨osung [Seite 29]
1.9 - 3. Vorbetrachtungen einer hochperformanten Lösung [Seite 31]
1.9.1 - 3.1. Wahl des DBMS und der Programmiersprache [Seite 31]
1.9.1.1 - 3.1.1. Wahl des Datenbankmodells [Seite 31]
1.9.1.2 - 3.1.2. Wahl des DBMS [Seite 36]
1.9.1.3 - 3.1.3. Wahl der Programmiersprache [Seite 38]
1.9.2 - 3.2. Schnittstellendefinition [Seite 42]
1.9.3 - 3.3. Möglichkeiten der Performancemessung [Seite 46]
1.10 - 4. Optimierungen in der Implementierung [Seite 50]
1.10.1 - 4.1. Algorithmische Optimierungen [Seite 50]
1.10.1.1 - 4.1.1. Optimierung des Dijkstra-Algorithmus [Seite 50]
1.10.1.2 - 4.1.2. Optimierung des Graphen [Seite 52]
1.10.1.3 - 4.1.3. Die"General-Gateway-Strategie" [Seite 53]
1.10.1.4 - 4.1.4. Nutzung stabiler Teilergebnisse bei ähnlichen Graphen [Seite 56]
1.10.2 - 4.2. Performanceoptimierter Programmierstil [Seite 61]
1.10.2.1 - 4.2.1. Quellcodedesign [Seite 61]
1.10.2.2 - 4.2.2. Zusammenhang zur algorithmischen Komplexität [Seite 63]
1.10.2.3 - 4.2.3. Design Pattern [Seite 64]
1.10.2.4 - 4.2.4. Implementierung von"unendlich" [Seite 65]
1.10.2.5 - 4.2.5. Adjazenzmatrix statt Adjazenzliste [Seite 66]
1.10.3 - 4.3. Parallelisierung [Seite 67]
1.10.3.1 - 4.3.1. Multithreaded Dijkstra [Seite 67]
1.10.3.2 - 4.3.2. Dijkstra auf der GPU [Seite 73]
1.10.4 - 4.4. Zusammenfassung und Ergebnisse [Seite 75]
1.11 - 5. Testläufe - Beispiele für Datenabfragen [Seite 78]
1.11.1 - 5.1. Alle Routen zu allen Zeitpunkten [Seite 80]
1.11.2 - 5.2. Routenänderungen zwischen zwei Zeitpunkten [Seite 81]
1.11.3 - 5.3. Routenänderungen bei Ausfall eines Knotens [Seite 83]
1.11.4 - 5.4. Routenänderungen bei Ausfall zweier Knoten [Seite 86]
1.11.5 - 5.5. Knoten die häufig auf Routen liegen [Seite 89]
1.11.6 - 5.6. Wichtige Knoten und Kanten [Seite 92]
1.11.7 - 5.7. Routenänderungen bei Ausfall einer Kante [Seite 94]
1.11.8 - 5.8. Suche nach Flaschenhälsen [Seite 97]
1.12 - 6. Zusammenfassung und Ausblick [Seite 100]
1.12.1 - 6.1. Zusammenfassung [Seite 100]
1.12.2 - 6.2. Ausblick [Seite 101]
1.13 - Literaturverzeichnis [Seite 104]
1.14 - A. Anhang: SQL Anfragen [Seite 107]
1.14.1 - A.1. Anzahl neuer Datensätze pro Minute [Seite 107]
1.14.2 - A.2. Prüfung der Vollständigkeit der Daten [Seite 108]
1.14.3 - A.3. Prüfung der Korrektheit der Daten [Seite 110]
1.14.4 - A.4. Maximale Knotenanzahl auf kürzesten Pfaden [Seite 111]
1.14.5 - A.5. Floyd-Warshall-Berechnung in SQL [Seite 113]
1.14.6 - A.6. Floyd-Warshall-Berechnung mit PL/Python [Seite 114]
1.14.7 - A.7. Test der General-Gateway-Strategie [Seite 115]
1.14.8 - A.8. Implementierung der Algebra aus Abschnitt 4.1.4 [Seite 116]
1.15 - B. Anhang: Suche nach einerPartitionierung [Seite 117]
1.1 - Einleitung [Seite 3]
1.2 - Abstract [Seite 4]
1.3 - Inhaltsverzeichnis [Seite 5]
1.4 - Abbildungsverzeichnis [Seite 7]
1.5 - Tabellenverzeichnis [Seite 8]
1.6 - Verzeichnis der Listings [Seite 9]
1.7 - 1. Einleitung [Seite 11]
1.7.1 - 1.1. Aufbau der Arbeit [Seite 11]
1.7.2 - 1.2. Beschreibung des Mesh-Netzwerks als Graph [Seite 12]
1.7.3 - 1.3. Qualität der zu analysierenden Daten [Seite 13]
1.7.4 - 1.4. Ziel der Arbeit [Seite 17]
1.7.5 - 1.5. Vorausgesetzte Hard- und Software [Seite 20]
1.8 - 2. Stand der Technik [Seite 22]
1.8.1 - 2.1. Routing-Algorithmen [Seite 22]
1.8.2 - 2.2. Metriken [Seite 23]
1.8.3 - 2.3. Betrachtung der bestehenden Implementierung als Cloud-Service [Seite 24]
1.8.3.1 - 2.3.1. Algorithmische Komplexit¨at [Seite 25]
1.8.3.2 - 2.3.2. Vor- und Nachteile der Cloudl¨osung [Seite 29]
1.9 - 3. Vorbetrachtungen einer hochperformanten Lösung [Seite 31]
1.9.1 - 3.1. Wahl des DBMS und der Programmiersprache [Seite 31]
1.9.1.1 - 3.1.1. Wahl des Datenbankmodells [Seite 31]
1.9.1.2 - 3.1.2. Wahl des DBMS [Seite 36]
1.9.1.3 - 3.1.3. Wahl der Programmiersprache [Seite 38]
1.9.2 - 3.2. Schnittstellendefinition [Seite 42]
1.9.3 - 3.3. Möglichkeiten der Performancemessung [Seite 46]
1.10 - 4. Optimierungen in der Implementierung [Seite 50]
1.10.1 - 4.1. Algorithmische Optimierungen [Seite 50]
1.10.1.1 - 4.1.1. Optimierung des Dijkstra-Algorithmus [Seite 50]
1.10.1.2 - 4.1.2. Optimierung des Graphen [Seite 52]
1.10.1.3 - 4.1.3. Die"General-Gateway-Strategie" [Seite 53]
1.10.1.4 - 4.1.4. Nutzung stabiler Teilergebnisse bei ähnlichen Graphen [Seite 56]
1.10.2 - 4.2. Performanceoptimierter Programmierstil [Seite 61]
1.10.2.1 - 4.2.1. Quellcodedesign [Seite 61]
1.10.2.2 - 4.2.2. Zusammenhang zur algorithmischen Komplexität [Seite 63]
1.10.2.3 - 4.2.3. Design Pattern [Seite 64]
1.10.2.4 - 4.2.4. Implementierung von"unendlich" [Seite 65]
1.10.2.5 - 4.2.5. Adjazenzmatrix statt Adjazenzliste [Seite 66]
1.10.3 - 4.3. Parallelisierung [Seite 67]
1.10.3.1 - 4.3.1. Multithreaded Dijkstra [Seite 67]
1.10.3.2 - 4.3.2. Dijkstra auf der GPU [Seite 73]
1.10.4 - 4.4. Zusammenfassung und Ergebnisse [Seite 75]
1.11 - 5. Testläufe - Beispiele für Datenabfragen [Seite 78]
1.11.1 - 5.1. Alle Routen zu allen Zeitpunkten [Seite 80]
1.11.2 - 5.2. Routenänderungen zwischen zwei Zeitpunkten [Seite 81]
1.11.3 - 5.3. Routenänderungen bei Ausfall eines Knotens [Seite 83]
1.11.4 - 5.4. Routenänderungen bei Ausfall zweier Knoten [Seite 86]
1.11.5 - 5.5. Knoten die häufig auf Routen liegen [Seite 89]
1.11.6 - 5.6. Wichtige Knoten und Kanten [Seite 92]
1.11.7 - 5.7. Routenänderungen bei Ausfall einer Kante [Seite 94]
1.11.8 - 5.8. Suche nach Flaschenhälsen [Seite 97]
1.12 - 6. Zusammenfassung und Ausblick [Seite 100]
1.12.1 - 6.1. Zusammenfassung [Seite 100]
1.12.2 - 6.2. Ausblick [Seite 101]
1.13 - Literaturverzeichnis [Seite 104]
1.14 - A. Anhang: SQL Anfragen [Seite 107]
1.14.1 - A.1. Anzahl neuer Datensätze pro Minute [Seite 107]
1.14.2 - A.2. Prüfung der Vollständigkeit der Daten [Seite 108]
1.14.3 - A.3. Prüfung der Korrektheit der Daten [Seite 110]
1.14.4 - A.4. Maximale Knotenanzahl auf kürzesten Pfaden [Seite 111]
1.14.5 - A.5. Floyd-Warshall-Berechnung in SQL [Seite 113]
1.14.6 - A.6. Floyd-Warshall-Berechnung mit PL/Python [Seite 114]
1.14.7 - A.7. Test der General-Gateway-Strategie [Seite 115]
1.14.8 - A.8. Implementierung der Algebra aus Abschnitt 4.1.4 [Seite 116]
1.15 - B. Anhang: Suche nach einerPartitionierung [Seite 117]
