Filtern
Dokumenttyp
- Bachelorarbeit (1)
- Dissertation (1)
Schlagworte
- Routing (2) (entfernen)
Institut
- Fachbereich 4 (1)
- Institut für Informatik (1)
In dieser Arbeit wird das in letzter Zeit zunehmend wichtiger werdende Thema der Routenaggregation und deren Auswirkung auf die Verhinderung von Routingschleifen behandelt. Als Basis für die Implementation und Evaluation dient das an der Universität Koblenz entwickelte RMTI-Protokoll, bei dem es sich um eine Weiterentwicklung des in RFC2453 spezifizierten Routing Information Protocol Version 2 handelt. Dieses Protokoll kommt, in dieser Arbeit, innerhalb der virtuellen Netzwerkumgebung Virtual Network User-Mode-Linux (VNUML) zum Einsatz. Mit VNUML ist es möglich konkrete Netzwerkszenarien virtuell zu betreiben und zu untersuchen. Der RMTI ist bereits in der Lage topologische Schleifen zu erkennen und dadurch das Entstehen von Routingschleifen nachweislich zu verhindern. Im Rahmen der Arbeit wird die Funktionsweise des RMTI beschrieben und anschließend darauf eingegangen, unter welchen Umständen eine Routenaggregation vorgenommen werden darf ohne das die Aggregation Routinganomalien nach sich zieht. Um diese Änderungen vornehmen zu können ist ein tieferes Verständnis der Struktur von Routingtabellen notwendig, daher wird deren Aufbau anhand von Beispielen erläutert. Im Anschluss wird beschrieben an welchen Stellen Änderungen am RMTI vorgenommen werden müssen um trotz Aggregation eine Verhinderung von Routingschleifen bewirken zu können. Am Ende der Arbeit findet abschließend eine Evaluation der Reorganisationsfähigkeit des virtuellen Netzes bei vorgenommener Routenaggregation statt.
Reaktiv lokale Algorithmen sind verteilte Algorithmen, die den Anforderungen großer, batteriebetriebener, Drahtloser Ad Hoc und Sensornetzwerke im besonderen Maße gerecht werden. Durch Vermeidung überflüssiger Nachrichtenübertragungen sowie Verzicht auf proaktive Ermittlung von Nachbarschaftstabellen (d.h. beaconing) minimieren solche Algorithmen den Kommunikationsaufwand und skalieren gut bei wachsender Netzgröße. Auf diese Weise werden Ressourcen wie Bandbreite und Energie geschont, es kommt seltener zu Nachrichtenkollisionen und dadurch zu einer Erhöhung der Paketempfangsrate, sowie einer Reduktion der Latenzen.
Derzeit wird diese Algorithmenklasse hauptsächlich für Geografisches Routing, sowie zur Topologiekontrolle, insbesondere zur Ermittlung der Adjazenzliste eines Knotens in zusammenhängenden, kantenschnittfreien (planaren) Repräsentationen des Netzgraphen, eingesetzt. Ersteres ermöglicht drahtlose multi-hop Kommunikation auf Grundlage von geografischen Knotenpositionen ohne Zuhilfenahme zusätzlicher Netzwerkinfrastruktur, wohingegen Letzteres eine hinreichende Grundlage für effiziente, lokale Lösungen einer Reihe algorithmischer Problemstellungen ist.
Die vorliegende Dissertation liefert neue Erkenntnisse zum Forschungsgebiet der reaktiven Algorithmen, zum Einen auf einer abstrakten Ebene und zum Anderen durch die Einführung neuer Algorithmen.
Erstens betrachtet diese Arbeit reaktive Algorithmen erstmalig im Ganzen und als eigenständiges Forschungsfeld. Es wird eine umfangreiche Literaturstudie zu dieser Thematik präsentiert, welche die aus der Literatur bekannten Algorithmen, Techniken und Anwendungsfelder systematisch auflistet, klassifiziert und einordnet. Weiterhin wird das mathematische Konzept der O- und Omega-reaktiv lokalen Topologiekontrolle eingeführt. Dieses Konzept ermöglicht erstmals die eindeutige Unterscheidung reaktiver von konventionellen, beacon-basierten, verteilten Topologiekontrollalgorithmen. Darüber hinaus dient es als Klassifikationsschema für existierende, sowie zukünftige Algorithmen dieser Art. Zu guter Letzt ermöglicht dieses Konzept grundlegende Aussagen über die Mächtigkeit des reaktiven Prinzips, welche über Entwurf und Analyse von Algorithmen hinaus reichen.
Zweitens werden in dieser Arbeit neue reaktiv lokale Algorithmen zur Topologiekontrolle und Geografischem Routing eingeführt, wobei drahtlose Netze durch Unit Disk bzw. Quasi Unit Disk Graphen modelliert werden. Diese Algorithmen berechnen für einen gegebenen Knoten die lokale Sicht auf zusammenhängende, planare, Euklidische bzw. Topologische Spanner mit konstanter Spannrate bzgl. des Netzgraphen und routen Nachrichten reaktiv entlang der Kanten dieser Spanner, wobei die Nachrichtenauslieferung garantiert wird. Alle bisher bekannten Verfahren sind entweder nicht reaktiv oder gewährleisten keine konstanten Euklidischen oder Topologischen Spannraten. Ein wesentliches Teilergebnis dieser Arbeit ist der Nachweis, dass die partielle Delaunay Triangulierung (PDT) ein Euklidischer Spanner mit konstanter Spannrate für Unit Disk Graphen ist.
Die in dieser Dissertation gewonnenen Erkenntnisse bilden die Basis für grundlegende und strukturierte Forschung auf diesem Gebiet und zeigen, dass das reaktive Prinzip ein wichtiges Werkzeug des Algorithmenentwurfs für Drahtlose Ad Hoc und Sensornetzwerke ist.