Institut für Informatik
Filtern
Dokumenttyp
- Diplomarbeit (24) (entfernen)
Schlagworte
- RIP-MTI (3)
- Routing (3)
- Konvergenz (2)
- RIP (2)
- XTPeer (2)
- API (1)
- Administration (1)
- Algorithm Engineering (1)
- Aussagenlogik (1)
- CMS (1)
Ein Netzwerk, wie beispielsweise das Internet, ist eine Menge von Netzen, die durch Router miteinander verbunden sind. Ein Router ist ein Computer, der mit mehreren Netzwerkschnittstellen ausgerüstet und an mehrere Netze angeschlossen ist, um zwischen diesen Pakete zu vermitteln. Man kann ein Netzwerk auch als Graph repräsentieren, wobei Router als Knoten und Netze als Kanten angesehen werden können. Diesen Graph nennt man die Topologie des Netzwerks. Soll ein Paket in ein anderes Netz als das eigene gesendet werden, so wird es normalerweise dem sogenannten Default-Router gesendet. Dieser besitzt (wie jeder Router) eine Tabelle (die sogenannte Forwardingtabelle), die alle Netze enthält. Zusätzlich ist in der Tabelle der jeweilige Router eingetragen, über den das Netz am besten erreicht werden kann. So wird das Paket von einem Router zum nächsten geleitet, bis es das Zielnetz erreicht. Dabei schlägt jeder Router in seiner Tabelle nach, welches der nächste Router auf dem günstigsten Weg zum Zielnetz ist. Ein Routingprotokoll kümmert sich um den automatischen Austausch von Informationen zwischen den Routern, um die Forwardingtabelle aufzubauen und auf dem aktuellen Stand zu halten. Sind die Tabellen aller Router auf dem aktuellen Stand, so befindet sich das Netzwerk in einem konvergenten Zustand. Die Zeit, die benötigt wird, um die Forwardingtabelle aufzubauen beziehungsweise sie nach einer Änderung der Topologie zu aktualisieren, wird Konvergenzzeit genannt. Das Routingprotokoll RIP ist ein bekanntes und gut erforschtes Distanzvektor-Protokoll. Jedoch gibt es bisher nur wenige Untersuchungen der Konvergenzeigenschaften (wie z.B. benötigte Zeit, um in einen konvergenten Zustand zu gelangen, oder das dabei erzeugte Trafficvolumen) dieses Protokolls. Ziel der Arbeit ist es einen Zusammenhang zwischen den Topologieeigenschaften eines Netzwerks und den Konvergenzeigenschaften bei Verwendung des RIP-Routingprotokills experimentell zu ermitteln. Hierfür wurden über 5000 Einzelmessungen mit verschiedenen Topologien durchgeführt und statistisch ausgewertet. Aus den Ergebnissen wurden Formeln abgeleitet, mit deren Hilfe sich für ein beliebiges Netzwerk die Konvergenzeigenschaften anhand seiner Topologieeigenschaften approximieren lassen.
RMTI (RIP with Metric based Topology Investigation) wurde in der AG Rechnernetze an der Universität Koblenz-Landau entwickelt. RMTI stellt eine Erweiterung zum RIP (Routing Information Protocol) dar, die das Konvergenzverhalten bei Netzwerkveränderungen, insb. bei Routingschleifen, verbessern soll. Dies geschieht durch Erkennen von Routingschleifen und Reduzieren des Count-to-infinity Problems. Um dieses gewünschte Verhalten nachweisen zu können, bedarf eine reichhaltige Evaluierung des RMTI- Algorithmus. Hierzu wurde in der gleichen Arbeitsgruppe die Client-/Server-Applikation XTPeer entwickelt. In Kombination mit anderen Software wie VNUML und Quagga Routing Suite lässt sich per XT-Peer der Algorithmus evaluieren. Die Applikation XTPeer generiert durch die Simulationen Daten. Diese können in Form von XML konforme SDF-Dateien exportiert werden. Diese können ohne weitere Auswertungen wieder in die XTPeer Applikation importiert werden. Die Evaluierung der Simulationen findet automatisiert nur an der aktuellen Simulation statt. Evaluierung über mehrere Simulationen muss der Benutzer manuell berechnen. Um diese Evaluierungsarbeiten für den Benutzer zu vereinfachen, verfolgt die vorliegende Diplomarbeit daher das Ziel, die XTPeer Applikation mit einem Auswertungsmodul zu erweitern. Die Auswertungen soll sich über alle gespeicherten Simulationsdaten und nicht wie bisher nur über die aktuell laufende Simulation erstrecken. Dies ermöglicht bessere statistisch verwertbare Aussagen. Zusätzlich können diese Auswertungsergebnisse grafisch unterstrichen werden.
Der RIPMTI-Algorithmus wurde entwickelt um die Schleifenerkennung in Rechnernetzen zu verbessern. Das Count-To-Infinity-Problem (kurz: CTI) führt dazu, dass ein Netzwerk nur sehr langsam in einen konvergenten Zustand gelangt. Der Hopcount-Wert 16, der als künstliche Beschränkung des CTI eingeführt wurde, beschränkt leider auch die maximale Topologietiefe eines Netzwerkes. Diese Arbeit soll zeigen wie sich eine schrittweise Erhöhung des Hopcount-Wertes und darüber hinaus die Änderung der Updatezeiten jedes Routers auf die Konvergenzzeiten unterschiedlicher Netzwerk-Szenarios auswirkt.
Ein Switch (engl. Schalter; auch Weiche) ist eine Netzwerk-Komponente zur Verbindung mehrerer Computer bzw. Netz-Segmente in einem lokalen Netzwerk (LAN). Da Switches den Netzwerkverkehr analysieren und logische Entscheidungen treffen, werden sie auch als intelligente Hubs bezeichnet. Die Funktionsweise eines Switches ist der einer Bridge sehr ähnlich, daher wurde anfangs auch der Begriff Multi-Port-Bridge genutzt 1. Ziel der Diplomarbeit ist es, eine Dokumentation auf die Beine zu stellen, der interessierten Studenten der Informationstechnologie die Möglichkeit bietet, einerseits anhand von physikalischen Switches Administrationsaufgaben nachzuempfinden und andererseits anhand von virtuellen Switches größere Netzwerktopologien aufzubauen. Diese Virtualisierung wird durch das von Virtual Square entwickelte Tool VDE erreicht. Die physikalischen Switches bestehen aus vier Catalyst 3500 XL. Im Laufe dieser Arbeit wird sowohl die Bedienung der einzelnen Systeme untereinander, wie auch die Vernetzung der virtuellen Switches mit den physikalischen Switches erläutert. In diesem Zusammenhang wird auch auf Protokolle und Methoden wie das Spanning Tree Protokoll oder die Virtualisierung eines Netzes durch VLANs eingegangen. Zum Schluss kann der Leser das gelernte in einigen praktischen Aufgaben anwenden.
Im Rahmen dieser Diplomarbeit wird ein Transaktionskonzept für die aktuelle Implementationsversion der TGraphenbibliothek JGraLab Carnotaurus umgesetzt. Nach einer grundlegenden Einführung in das Konzept der TGraphen werden die relevanten Implementationsdetails der TGraphenbibliothek erläutert. Anschließend erfolgt ein konzeptueller Entwurf, in dem die formalen Grundlagen des Transaktionskonzepts beschrieben werden. Das aus der Datenbankwelt bekannte ACID-Paradigma für Transaktionen dient dabei als wissenschaftliche Grundlage. In einem nächsten Schritt erfolgt der objektorientierte Feinentwurf der Integration des zu entwickelnden Transaktionskonzepts in das vorhandene Gesamtsystem, anhand dessen die Implementation durchgeführt wird. Eine Analyse und Bewertung des umgesetzten Transaktionskonzepts (vor allem im Hinblick auf den Speicherverbrauch und das Laufzeitverhalten) schließen die Arbeit ab.
Performanz von RIP-MTIfi
(2009)
Diese Diplomarbeit beschäftigt sich mit der Performanz von RIP-MTI, insbesondere mit der Performanz der Schleifenerkennung. Ziel der Arbeit ist es, die Zeitdauer der Schleifenerkennung von RIP-MTI zu untersuchen und Probleme, welche bei der Erkennung von Schleifen auftreten könen, aufzudecken und zu lösen.
Ziel dieser Arbeit war es, den in [Rhe06] dargestellten operationalen Ansatz zur Modelltransformation mit Hilfe der am Institut für Softwaretechnik der Universität Koblenz-Landau vorhandenen Bibliotheken "JGraLab" und "GReQL" in Java zu implementieren. Die Implementierung sollte beweisen, dass der aufgezeigte Transformationsansatz in der Praxis umsetzbar ist. Dies wurde durch verschiedene Beispiele bewiesen. Die geplante Verwendung in weiteren Projekten des IST wird für die Zukunft zeigen, ob sich weitere Transformationen umsetzten lassen oder wo die Grenzen des Ansatzes sind. Des weiteren ist denkbar, die Transformationen nicht mehr in zwei Schritten (Schematransformation vor Graphtransformation), sondern beide Schritte auf einmal ablaufen zu lassen. Dieser Schritt setzt jedoch voraus, dass JGraLab dies ebenfalls unterstützt.
Das Routing Information Protocol (RIP) ist ein Internet-Standard-Routing-Protokoll, das einst mit zu den am meisten eingesetzten Routing-Protokollen in IP-Netzwerken gehörte. Es basiert auf dem sogenannten Distanzvektoralgorithmus und ist in seiner Funktion und seinem Aufbau sehr einfach ausgelegt. Seit jeher leidet es allerdings unter dem sogenannten Counting-to-Infinity (CTI) Problem, bei dem die Erreichbarkeit einer eigentlich ausgefallenen Verbindung zu einem Ziel scheinbar aufrechterhalten wird. Die Distanz zu diesem Ziel wird aufgrund des fortwährenden Austauschs von nicht mehr gültigen Verbindungsinformationen zwischen in einem Ring geschalteten RIP-Routern hochgezählt, theoretisch bis ins Unendliche. Dabei entstehen Routingschleifen, die den Netzwerkbetrieb erheblich stören können, da die gesendeten Netzwerkpakete aufgrund der Schleife die selben Router immer wieder passieren und weder an ihr eigentliches Ziel gelangen noch verworfen werden können. Die Gefahr des Auftretens des CTI-Problems schränkt die Einsetzbarkeit von RIP enorm ein. Die Netzwerke, in denen RIP eingesetzt wird, können nicht beliebig wachsen, da die maximale Größe des Netzwerks auf eine relativ kleine Distanz zwischen den Routern begrenzt ist, um die Dauer und die Folgen des CTI-Problems im Falle des Auftretens gering zu halten. Je stärker auch die Topologie eines Netzwerks vermascht ist, um mit zusätzlichen, alternativen Verbindungen Ausfällen entgegenzuwirken, umso stärker steigt auch die Gefahr des Auftretens des CTI-Problems nach einem Ausfall. Bislang existierten für RIP lediglich Mechanismen, die das Risiko des Auftretens und die Auswirkungen des CTI-Problems verringern, das Problem selbst aber nicht beheben können. Mit "RIP with minimal topology information" (RIP-MTI) wurde in der AG Rechnernetze an der Universität Koblenz-Landau eine abwärtskompatible Erweiterung zu RIP geschaffen, die das CTI-Problem zu beheben verspricht. Der RIP-MTI-Algorithmus sammelt zusätzliche Informationen über die Topologie des Netzwerks und nutzt diese, um nach dem Ausfall einer Verbindung richtige Informationen über die Erreichbarkeit von Zielen von falschen Informationen unterscheiden zu können. In dieser Diplomarbeit wird die Implementierung des RIP-MTI-Algorithmus behandelt. Mit Hilfe der speziell entwickelten RIP-Netzwerk-Testumgebung XTPeer, in der das CTI-Problem kontrolliert provoziert werden kann, wird die Wirksamkeit der Implementierung eines Quagga RIP-MTI-Routers überprüft und entsprechend weiterentwickelt. Dafür wird der RIP-MTI-Algorithmus an die Implementierung des Quagga RIP-Routing-Software sowie an die der Netzwerk-Testumgebung XTPeer angepasst. Diese Diplomarbeit wird vom Autor selbst als fortgeschrittene Zwischenstation eingestuft, vor der Herstellung und Herausgabe der Implementierung einer RIP-MTI-Routing-Software, die auch in produktiven Netzwerken eingesetzt werden könnte.
In unserer heutigen Welt spielen soziale Netzwerke eine immer größere werdende Rolle. Im Internet entsteht fast täglich eine neue Anwendung in der Kategorie Web 2.0. Aufgrund dieser Tatsache wird es immer wichtiger die Abläufe in sozialen Netzwerken zu verstehen und diese für Forschungszwecke auch simulieren zu können. Da alle gängigen sozialen Netzwerke heute nur im eindimensionalen Bereich arbeiten, beschäftigt sich diese Diplomarbeit mit mehrdimensionalen sozialen Netzwerken. Mehrdimensionale soziale Netzwerke bieten die Möglichkeit verschiedene Beziehungsarten zu definieren. Beispielsweise können zwei Akteure nicht nur in einer "kennt"-Beziehung stehen, sondern diese Beziehungsart könnte auch in diverse Unterbeziehungsarten, wie z.B. Akteur A "ist Arbeitskollege von" Akteur B oder Akteur C "ist Ehepartner von" Akteur D, unterteilt werden. Auf diese Art und Weise können beliebig viele, völlig verschiedene Beziehungsarten nebeneinander existieren. Die Arbeit beschäftigt sich mit der Frage, in welchem Grad die Eigenschaften von eindimensionalen auch bei mehrdimensionalen sozialen Netzwerken gelten. Um das herauszufinden werden bereits bestehende Metriken weiterentwickelt. Diese Metriken wurden für eindimensionale soziale Netzwerke entwickelt und können nun auch für die Bewertung mehrdimensionaler sozialer Netzwerke benutzt werden. Eine zentrale Fragestellung ist hierbei wie gut sich Menschen finden, die sich etwas zu sagen haben. Um möglichst exakte Ergebnisse zu erhalten, ist es notwendig reale Daten zu verwenden. Diese werden aus einem Web 2.0-Projekt, in das Benutzer Links zu verschiedenen Themen einstellen, gewonnen (siehe Kapitel 4). Der erste praktische Schritte dieser Arbeit besteht daher darin, das soziale Netzwerk einzulesen und auf diesem Netzwerk eine Kommunikation, zwischen zwei Personen mit ähnlichen Themengebieten, zu simulieren. Die Ergebnisse der Simulation werden dann mit Hilfe der zuvor entwicklelten Metriken ausgewertet.
Diese Arbeit stellt ein Werkzeug zur Verfügung, das strukturierte Tests des RIP-MTI Algorithmus vereinfachen, beschleunigen und automatisieren kann. Die vormals zwei Dimensionen Topologie und Updatekonstellation, auf die die MTI-Erweiterung getestet werden musste, konnten auf den variablen Anteil der Topologie vereinfacht werden. Die zeitliche Reihenfolge des Auftretens der Updates kann zentral gesteuert werden. Bisher mussten Tests händisch und sehr aufwändig über Skripte auf der Konsole gesteuert werden. Die entwickelte Testumgebung "XTPeer" ermöglicht es, die gleichen und viele weitere Tests mit kleinem Aufwand durchzuführen.
Der an der Universität Koblenz-Landau entwickelte RIP-MTI-Algorithmus stellt eine Modifikation des Routingalgorithmus RIP dar, die es dem RIP-Algorithmus ermöglichen soll, die Häufigkeit des Auftretens des Counting-to-infinity-Problems (CTI) zu reduzieren. Um die Korrektheit und Zuverlässigkeit dieses Algorithmus nachweisen, aber auch Schwächen aufdecken zu können, bedarf es der Möglichkeit, das Verhalten des Algorithmus zu testen. Ziel der Arbeit ist die Nutzbarmachung der von unter VNUML laufenden RIP-Routern dezentral verwalteten Routing-Informationen, um die Entstehung von CTIs zentral protokollieren und analysieren zu können. Zu diesem Zweck wird eine Software entwickelt, die Informationen zur Netzkonfiguration, zu Erreichbarkeiten und Update-Aufkommen sammelt, verwaltet und analysiert. So können neben den bereits bekannten problematischen Netztopologien weitere für die einzelnen RIP-Ausprägungen problematische Topologien ermittelt werden.
Interactive video retrieval
(2006)
The goal of this thesis is to develop a video retrieval system that supports relevance feedback. One research approach of the thesis is to find out if a combination of implicit and explicit relevance feedback returns better retrieval results than a system using explicit feedback only. Another approach is to identify a model to weight existing feature categories. For this purpose, a state-of-the-art analysis is presented and two systems implemented, which run under the conditions of the international TRECVID workshop. It will be a basis system for further research approaches in the field of interactive video retrieval. Amongst others, it shall participate in the 2006 search task of the mentioned workshop.
Partielle Wissenskompilation
(2006)
Viele Probleme in der Aussagenlogik sind nur sehr aufwändig lösbar. Ist beispielsweise eine Wissensbasis gegeben, an die wir Anfragen stellen, wollen, so kann dies mitunter sehr mühsam sein. Um trotzdem effizient Anfragen beantworten zu können, hat sich die Vorgehensweise der Wissenskompilation entwickelt. Dabei wird die Lösung der Aufgabe in eine Offline- und eine Online-Phase aufgeteilt. In der Offline-Phase wird die Wissensbasis präkompiliert. Dabei wird sie in eine bestimmte Form umgewandelt, auf der sich die erwarteten Anfragen effizient beantworten lassen. Diese Transformation der Wissensbasis ist meist sehr aufwändig, muss jedoch nur einmalig durchgeführt werden. In der darauffolgenden Online-Phase können nun effizient Anfragen beantwortet werden. In dieser Diplomarbeit wird eine spezielle Normalform, die sich als Zielsprache der Präkompilation anbietet, untersucht. Außerdem wird die Präkompilation so in einzelne Schritte unterteilt, dass möglicherweise bereits nach einigen Teilschritten Anfragen beantwortet werden können.