Inhaltsverzeichnis *

Kapitel 1 Motivation und Aufgabenstellung *

Kapitel 2 Java *

Kapitel 3 Routing - Leitwegbestimmung in Rechnernetzen *

Kapitel 4 Interner Programmaufbau *

Kapitel 5 Zusammenfassung und Ausblick *

Anhang A Bedienerführung: *

Literaturverzeichnis: *

Das Projekt TeleTeaching der Universitäten Heidelberg und Mannheim sieht den gegenseitigen Austausch von Vorlesungen mittels eines digitalen Hochgeschwindigkeitsnetzes vor. Im SS1996 wurde die Vorlesung Rechnernetze von Prof. Effelsberg erstmals auf diese Weise nach Heidelberg übertragen. Begleitend zu dieser Vorlesung wird das Unterrichtsmaterial multimedial aufbereitet (Text, Graphiken, Video, Audio, etc.) und dem Studenten per WWW zur Nachbereitung und Prüfungsvorbereitung zur Verfügung gestellt. Gegenüber klassischen Medien, wie bspw. Bücher, bietet der Computer die Möglichkeit, interaktiv zu lernen, statt passiv zu konsumieren. Selbständiges Ausprobieren und Anwenden des Wissens optimiert den Lerneffekt. Basierend auf dem "Learning by doing" Paradigma sollen daher, zusätzlich zum reinen Vorlesungsstoff, interaktive Animationen/Simulationen entwickelt werden, die über WWW abrufbar sind.

Ziel dieser Studienarbeit ist die Entwicklung eines interaktiven Animations- bzw. Simulationsprogramms zur Visualisierung von Routingalgorithmen im Weitverkehrsbereich. Es sind folgende Algorithmen animiert worden: Shortest Path, Multipath, Backward Learning und Flooding.

Besonderer Wert ist hierbei auf eine objektorientierte Entwicklung gelegt worden. Die entwickelten Basisklassen sind so flexibel gestaltet worden, daß sie sich ohne signifikante Änderungen auch für Animationen in anderen Bereichen eignen.

Durch das objektorientierte Konzept ist auch eine problemlose Weiterentwicklung und Erweiterung des Programms garantiert.

Die Anwendung ist mit der neuen an C++ angelehnten Programmiersprache Java entwickelt worden. Das Programm ist mit dem Java Developers Kit 1.0 entwickelt worden.

In der Literatur findet (siehe auch [6], [7], [8]) man zu Java sehr viele Eigenschaften, die diese neue Sprache umschreiben. Es ist eine einfache, objektorientierte, robuste, sichere, architektur-unabhängige (plattformunabhängige), leistungsstarke, interpretierte, Thread-unterstützende, dynamische Programmiersprache.

Im folgenden werden die oben genannten Eigenschaften näher erläutert.

Die Sprache verbindet nur wenige ausgesuchte Konzepte. Das sind Klassen, Objekte, Schnittstellen, C-ähnliche Kontrollstrukturen, Ausnahmen und die Programmierung paralleler Abläufe mit Hilfe der Threads.

Die Entwickler verzichteten auf Zeiger, Zeigerarithmetik, Mehrfachvererbung, und automatische Typenkonvertierung.

Die Syntax entspricht weitgehend der Syntax der Programmiersprachen C und C++. Dadurch ist Java vielen Programmierern in ihren Darstellungsweise geläufig.

Java ist durch einen relativ kleinen Sprachumfang und eine umfangreiche Klassen-bibliothek (API) gekennzeichnet. Java-Programme bestehen aus Klassen. In der Sprache sind die wichtigsten Konzepte der Objektorientierung wie Informationskapselung, Polymorphie, Vererbung, Dynamisches Binden, Nachrichtenaustausch durch Methodenaufruf realisiert.

Programmierer können in Java weder direkt Zeiger definieren noch mittels Zeigerarithmetik auf bestimmte Adressen des Speichers zugreifen. Java verwendet statt dessen nur Referenzen auf Objekte. Die Speicherverwaltung übernimmt das Laufzeitsystem, welches nicht mehr referenzierte Objekte aus dem Speicher beseitigt (Garbage Collection). Durch die streng typisierte Sprache und die Kompatibilitätsregeln wird der Programmierer zu einer sauberen Programmierung gezwungen. Dies verhindert schwer aufzufindende Fehler. Desweiteren müssen Laufzeitfehler abgefangen werden, damit das Programm in Ausnahmefällen weiterarbeiten kann.

Java verbindet die Vorteile von interpretierten und compilierten Sprachen. Zunächst wird der Quelltext in ein Zwischenformat (Java-Byte-Code) compiliert und erst ein Interpreter führt das Zwischenformat aus. Java-Programme sind dadurch schneller als direkt interpretierte Programme und in der Entwicklungsphase leichter zu bearbeiten als compilierte Programme.

Durch die Definition der Zwischenrepräsentation wird die Sprache architekturunabhängig, wenn für jede Architektur ein Interpreter zur Verfügung steht.

Java ermöglicht die Verteilung und Ausführung von Software über ein Netz, vor allem über das World Wide Web. Ein Mittel, um die dazu benötigte Sicherheit zu erreichen, ist der Byte Code Verifier. Die Übertragung von Java-Programmen erfolgt weder im Quelltext noch in einem direkt ausführbaren Format, sondern im Java-Byte-Code-Format. Erst der Java-Interpreter führt Programme dieses Formates aus. Der Byte Code Verifier ist ein Teil des Interpreters, er soll korrumpierte Zeilen im Programmtext finden und Laufzeitregeln überprüfen.

Mit Hilfe von Threads kann der Programmierer parallele Abläufe beschreiben. Java bietet hierfür die Klasse Thread der Klassenbibliothek, auf der syntaktischen Ebene ein Mittel zur Synchronisation von Threads und im Laufzeitsystem einen Scheduling-Mechanismus an.

Es wird dynamisches Binden und dynamisches Laden verwendet. Referenzen zur Superklasse werden erst im Interpreter aufgelöst und beseitigt dadurch die Notwendigkeit zur Neuübersetzung von abgeleiteten Klassen nach Änderung der Superklasse.

Die Kombination all dieser Eigenschaften machen Java für das Internet tauglich.

Bereits in den 60er Jahren waren teilweise weltweite Rechnernetze vorhanden. Diese Netze hatten eines gemeinsam: Sie erfüllten ihre Aufgaben für einen sehr beschränkten Teilnehmerkreis. Es war Teilnehmern verschiedener Netzwerke nicht möglich, miteinander zu kommunizieren. Jedes dieser Netze samt ihren Datenendgeräten bildete ein sogenanntes geschlossenes System.

Diesen Mißstand erkannte die International Standard Organization (ISO) und entwickelte einen Standard für offene Systeme, nämlich den Open System Interconnection (OSI) Standard. Ein offenes System definiert ISO als einen Satz von Computern, Software, Peripherie und Übertragungsmedien, das dem OSI-Standard gehorcht. Durch diesen Standard wird nun erreicht, daß jedes Teilsystem mit jedem anderen System kommunizieren kann.

Das OSI Architekturmodell betrachtet ausschließlich die Belange der Interaktion zwischen offenen Systemen. Unter Interaktion (oder interconnection) wird nicht nur die Informationsübertragung zwischen den Systemen verstanden, sondern auch über die reine Datenübertragung hinausgehende Mittel zur Kooperation zwischen verteilten Systemen (z.B. Aushandeln einheitlicher Datenformate). Das bedeutet, daß die einzigen standardisierten Teile des Systems die Kommunikationsschnittstellen nach außen und die Schnittstellen der physikalischen Systemkomponenten untereinander sind [4].

Um diesen Standard zu verwirklichen zerlegt OSI jedes offene System in sieben Schichten mit eigenständigen Aufgaben. Die Schichten stehen zueinander in der einfachsten aller möglichen Beziehungen:

Jede Schicht verwendet die darunterliegende und unterstützt die darüberliegende Schicht. So entsteht eine Struktur von horizontalen Schichten in jedem der verbundenen offenen Systemen. Jede Schicht erfüllt eine genau umrissene, für beide Partnersysteme gemeinsame Teilaufgabe, die man den Dienst (service) der Schicht bezeichnet [4], [12].

Im folgenden kommt eine Aufzählung derjenigen Aufgaben, die für jede Schicht bestimmend ist. Jede Schicht stellt der darüberliegenden Schicht ihre Dienste zur Verfügung, jede höhere Schicht ergänzt die Dienste der darunterliegenden Schichten. Dies setzt sich bis zur höchsten, der Anwenderschicht fort.

Die Bitübertragungsschicht stellt ungesicherte Verbindungen zwischen Systemen für die Übertragung von Bits zur Verfügung.

Die Sicherungsschicht soll insbesondere Übertragungsfehler entdecken und korrigieren.

Die Vermittlungsschicht transportiert Pakete über die Teilstrecken des Netzes von Endsystem zu Endsystem.

Eine der wichtigsten Aufgaben der Vermittlungsschicht ist die Leitwegbestimmung mit ihren verschiedenen Algorithmen.

Die Transportschicht übermittelt die Daten von Endbenutzer zu Endbenutzer. Sie entlastet den Benutzer von den Details der Datenübertragung.

Die Kommunikationssteuerungsschicht regelt den Gesprächswechsel zwischen kommunizierenden Partnern und liefert Vorkehrungen zum Wiederanlaufen einer unterbrochenen Übertragung ab einem zwischen den Partnern vorher vereinbarten Punkt im Datenstrom (Synchronisationspunkt). Sie regelt den Betriebsablauf.

Die Darstellungsschicht stellt Ausdrucksmittel (z.B. Zeichenvorrat, Datentypen) zur Verfügung, die es den Anwendungsinstanzen ermöglichen, Begriffe eindeutig zu benennen und legt im Darstellungsprotokoll die Regeln fest, wie die in der gemeinsamen Sprache dargestellten Informationen auszutauschen sind.

Die Anwendungsschicht, die höchste Schicht des Referenzmodells, stellt die Mittel zur Kooperation zwischen verteilten Anwendungsprozessen zur Verfügung. Der Anwendungsprozeß hat ausschließlich über die Schicht 7 Zugang zum OSI-Netzwerk.

Tiefergehende Informationen zum ISO.OSI Modell finden sich in [4] und [12]. Der folgende Abschnitt behandelt einige Leitwegbestimmungsalgorithmen, dir zur Hauptaufgabe der Vermittlungsschicht gehören.

Die eigentliche Funktion der Vermittlungsschicht besteht darin, für Pakete Leitwege von der Quell- zur Zielmaschine zu bestimmen (Routing). In den meisten Netzen benötigen die Pakete bei dieser Reise mehrere Teilstrecken (Hops). Die Algorithmen zur Leitwegbestimmung und die von ihnen verwendeten Datenstrukturen sind beim Entwurf der Vermittlungsschicht das Hauptgebiet.

Der Leitwegbestimmungsalgorithmus eines Vermittlungsrechners (Knotens) entscheidet, auf welcher Ausgangsleitung ein eingegangenes Paket weitergeleitet wird. Wenn das Teilnetz Datagramme verwendet, muß diese Entscheidung für jedes Paket erneut gefällt werden. Bei virtuellen Verbindungen hingegen, müssen die Leitwege nur bei Erstellung der Verbindung bestimmt werden. Danach folgen die Pakete dem vorher festgelegten Leitweg. Dieser Fall wird manchmal Sitzungs-Leitwegbestimmung (session routing) genannt, da der Leitweg für die gesamte Benutzersitzung aktiviert bleibt.

Eine Gliederung der Routingalgorithmen kann in leitungsvermittel (Telefon, ISDN) oder paketvermittelt aufgeteilt werden. Zu den paketvermittelten Verfahren gehören die virtuelle Verbindungen (X.25) und die Datagramme (Internet, IP).

Unabhängig davon, ob Leitwege für jedes Paket einzeln oder nur bei Aufbau einer neuen Verbindung gewählt werden, sollte der Routing-Algorithmus folgende allgemeine Bewertungskriterien erfüllen [12]:

Bei gleichen Verhältnissen soll das Routing immer nach dem gleichen Verfahren ablaufen. Ein stabiles Netz verhält sich bezüglich seiner Kenngrößen, z.B. Antwortzeiten oder verfügbarer Kapazität, immer ähnlich, was für viele Anwendungen notwendig ist. In vielen Anwendungen ist es wichtig, daß die Reihenfolge der Pakete erhalten bleibt, denn es darf in der Regel während des Betriebs einer Verbindung die Route nicht geändert werden.

Ein robustes Netz paßt sich bei Änderung seiner Parameter automatisch der neuen Situation an. Solch ein selbstadaptierendes Verhalten wird mit gewissen Risiken bezüglich der Stabilität und Korrektheit erkauft, da die damit notwendig werdende Regelung der Wegewahl zu schwingendem Verhalten führen kann, Fehler provoziert und die Komplexität erhöht. Letzteres widerspricht der Forderung nach Einfachheit der Algorithmen.

Die Routing-Algorithmen sollen einfach zu verstehen, zu implementieren und gegebenenfalls zu verifizieren sein.

Die Korrektheit des Algorithmus soll garantieren, daß Pakete stets beim richtigen Empfänger eintreffen. Insbesondere bei dynamischen oder optimalen Routingstrategien können Pakete u.U. nur zwischen zwei Knoten oder zyklisch über mehrere Knoten im Kreis geschickt werden, ohne jemals den eigentlichen Zielknoten zu erreichen, was sehr schwierig zu erkennen ist, aber dennoch auf jeden Fall vermieden werden muß.

Wie jedes technische System, so müssen auch Rechnernetze insbesondere bezüglich der Kosten, optimiert werden. Andere Optimierungskriterien sind die Verzögerung, Sicherheit, Ausnutzung und Auslastung. Dennoch hängen die Kosten häufig von den Gebühren öffentlicher Anbieter ab (z.B. bei Leitungen der Deutschen Bundespost Telekom), die sich kurzfristig aus politischen Gründen ändern können. In solchen Fällen muß man sich mit suboptimalen Lösungen zufriedengeben.

Um die Kenngrößen zu bestimmen, sind entsprechende Formeln anzugeben, aus denen die jeweiligen Werte errechnet werden können. Die Verzögerung muß als Zeit angegeben werden, die von der Absendung einer Nachricht bis zu deren Empfang vergeht. Als Zeitpunkte kann man entweder den der Übergabe eines Pakets (der Referenz auf ein Paket) oder die Absendung des ersten Bits und Empfang des letzten Bits definieren. Dieses hängt jedoch u.U. stark von der jeweiligen Anwendung ab, so daß hier genaue Definitionen zu den jeweiligen Kennzahlen erforderlich sind.

Die Sicherheit eines Netzes wird in der Regel als Wahrscheinlichkeit angegeben, daß ein Paket korrekt beim Empfänger eintrifft. Sie kann nur als statistische Größe gesehen werden (wie die meisten anderen auch) und muß entsprechend durch ein statistisches Modell ermittelt werden.

Unter Auslastung wird das Verhältnis zwischen der Zeit, die ein System überhaupt arbeitet und der gesamten Zeit verstanden. Die Ausnutzung wird hingegen als das Verhältnis zwischen der geleisteten Arbeit und der maximal möglichen Arbeit eines Systems definiert. Beide Größen können bei Systemen, die mehrere Aufträge gleichzeitig bearbeiten können, sehr unterschiedlich sein. In Rechensystemen kann z.B. durch die Nutzung paralleler Einheiten die Ausnutzung vergrößert werden, während sich gleichzeitig die Auslastung verringern kann.

Fairneß ist nur dann gegeben, wenn alle Teilnehmer gleichberechtigt sind. Allerdings kann in manchen Umgebungen für gewisse Nutzergruppen die Dienstqualität verbessert werden, falls diese Nutzer bereit sind, höhere Kosten zu tragen. Ebenso können aufgrund rechtlicher oder technischer Bedingungen bestimmte Dienste bevorzugt werden, z.B. Alarme, Managementinformationen oder kurze Nachrichten. Daher kann Fairneß in der Regel nur bezüglich einzelner Nutzergruppen gefordert werden.

Diese Bewertungskriterien stehen auch in Konkurrenz. Es gilt, einen befriedigenden Durchschnitt zu erreichen.

Routingalgorithmen treffen eine Wegewahl zwischen einem Quellknoten und einem Zielknoten über mehrere Transitsysteme. Dabei unterscheidet man:

• nicht adaptive (statische) Verfahren und
• adaptive (dynamische) Verfahren.

Nicht adaptive oder statische Verfahren berechnen aufgrund der Topologie und der zu erwartenden Belastung der Leitungen den Weg zwischen der Quelle und der Senke vor der eigentlichen Inbetriebnahme des Netzes; diese Daten werden dann in den einzelnen Rechnern gespeichert. Wird während des Betriebes eine Änderung der Leitwegtabellen nötig, so muß der laufende Betrieb unterbrochen und eine Neuberechnung der optimalen Wege durchgeführt werden.

Hierzu zählen von den animierten Wegeermittlungsverfahren der Shortest Path, Multipath, sowie der Flooding Algorithmus.

Adaptive Verfahren passen den zu wählenden Weg an die augenblickliche Auslastung der verschiedenen Leitungen sowie an die aktuelle Topologie an. Man unterscheidet im wesentlichen drei verschiedene Kategorien adaptiver Verfahren.

Die lokalen adaptiven Verfahren (isolated dynamic routing) waren die ersten dynamischen Verfahren. Diese Algorithmen laufen lokal und unabhängig auf den einzelnen Knotenrechnern ab und nutzen lediglich die in den Knoten vorhandene Information zur Wegeermittlung, z.B. die Länge der Warteschlange in den Leitungspuffern oder sie wählen eine zufällige Ausgangsleitung. Für die Wegewahl wird somit keine Information mit anderen Knoten ausgetauscht.

Hierzu zählt der Backward Learning Algorithmus.

Die zentralisierten Verfahren (centralized dynamic routing) gewinnen ihre Informationen zur Berechnung eines voraussichtlich optimalen Weges aus Daten, die aus dem gesamten Netz zusammengetragen und an einer ausgezeichneten Stelle (dem Routingkontrollzentrum) verarbeitet werden. Aus den so gewonnenen Informationen berechnet der zentrale Knoten dann die globalen Routinginformationen. Der wesentliche Nachteil dieses Verfahrens besteht darin, daß jeder Knoten, der eine Nachricht verschicken will, zuerst den zentralen Knoten kontaktieren muß, um die Daten für die Weiterleitung von Paketen zu erhalten. Diese Verfahren sind somit nur für verbindungsorientierte Protokolle geeignet, die eine Wegewahl nur einmal beim Aufbau einer virtuellen Verbindung treffen müssen.

Die verteilten Verfahren (distributed dynamic routing) benutzen eine Mischung aus globaler und lokaler Information, um ihre Entscheidung zu fällen. Ein bekanntes Beispiel ist das TCP/IP Internet, welches ein verteiltes dynamisches Routing anwendet. Bei diesem Verfahren tauschen die einzelnen IMPs (Internet Message Processors) in regelmäßigen Abständen Leitweginformationen mit ihren Nachbarn aus. Diese bestehen aus einer nach allen anderen IMP’s indizierten Leitwegtabelle mit jeweils einem Eintrag für jeden anderen IMP im Subnetz. Die Leitwegtabelle enthält die voraussichtlich optimale Ausgangsleitung und eine Näherung für die benötigte Zeit bzw. für die Entfernung.

Zur Erläuterung des Algorithmus wird ein weitverbreitetes Modell verwendet. Es wird ein Graph eines Subnetzes erstellt, wobei jeder Knoten des Graphen ein Rechner (IMP) und jede Kante eine Kommunikationsleitung darstellt. Zur Auswahl eines Leitweges zwischen einem gegebenen Paar von IMP’s sucht der Algorithmus den kürzesten dazwischenliegenden Pfad.

Die Beschriftung der ungerichteten Kanten im Graphen geben die Gewichtung der einzelnen Strecke an. Für die Meßweise der Gewichtung kommen viele Möglichkeiten in Frage. Sie könnte als eine Funktion von Entfernung, Bandbreite, Durchschnittsverkehr, Kommunikationskosten, mittlerer Warteschlangenlänge, gemessener Verzögerung und anderen Faktoren berechnet werden.

Eines der bekanntesten Verfahren ist der Algorithmus von Dijkstra, der im Programm implementiert wurde [5], [12].

Der erste Schritt des Algorithmus besteht darin, alle Knoten des Graphen mit einer initialen Marke (Länge (l), Vorgänger (v)) zu versehen. Der Wert l gibt die Länge des Pfades vom Startrechner bis zum Knoten an und v bezeichnet den Vorgängerknoten, auf dem der Startrechner mit der Länge l erreichbar ist.

Zu Beginn werden alle Längen mit unendlich (bzw. im Beispiel mit 100) versehen und als Vorgängerknoten der Rechner 0 eingetragen, da dieser nicht im Netz existiert.

Zur Erläuterung der Vorgehensweise des Algorithmus betrachten wir das Netzwerk in Abbildung 3.1 und suchen den kürzesten Weg zwischen Rechner 3 und Rechner 6.

Zu Beginn wird der Startrechner 3 als permanent (Arbeitsknoten) markiert. Nun wird vom Arbeitsknoten aus jeder benachbarte Rechner untersucht und mit seiner Entfernung zum Startrechner 3 beschriftet. In jeder neuen Beschriftung eines Knotens wird auch der Knoten vermerkt, von dem aus gemessen wurde (Vorgänger v), so daß der endgültige Pfad später rekonstruiert werden kann.

Nach der Untersuchung jedes Nachbarknotens von Rechner 3 untersucht man alle vorläufig beschrifteten Knoten im ganzen Netzwerk und markiert den Rechner mit der kleinsten Länge als permanent (s. Abb. 3.2).

Im Beispiel ist Rechner 1 neuer Arbeitsknoten. Nun wird von Rechner 1 jeder Nachbarknoten untersucht. Sollte die Länge von einem Nachbarknoten kleiner sein als die bisher vermerkte Länge, so wird die Beschriftung von Vorgänger und Länge aktualisiert.

Sind alle Nachbarknoten untersucht worden, wird der nächste Knoten mit der kleinsten Länge, der noch nicht Arbeitsknoten war, als permanent markiert. Im Beispiel ist das Rechner 4 (s. Abb. 3.3).

Diese Prozedur setzt sich fort, bis der Zielrechner erreicht ist und kein Rechner, der noch nicht Arbeitsrechner war, eine kleine Länge besitzt. Der kürzeste Weg wird nun ausgehend vom Endrechner rückwärts ermittelt, indem man immer zum Rechner der als Vorgänger eingetragen ist zurückgeht. Die Gesamtlänge des kürzesten Weges steht beim Endrechner unter Länge l. In Abbildung 3.4 ist der Shortest Path schwarz markiert.

Um eine gleichmäßige Auslastung der Verbindungsleitungen zu gewährleisten, kann der Datenverkehr nicht nur über eine Leitung von der Quelle zur Senke geführt werden. Es können mehrere Alternativen bereitstehen. Diese Technik, die zwischen zwei Knoten mehr als einen Verbindungsweg vorsieht, wird Mehrfach-Leitwegbestimmung (multipath routing) genannt [5], [11].

Die Mehrfach-Leitwegbestimmung ist bei Datagramm-Subnetzen und Subnetzen mit virtuellen Verbindungen anwendbar. Wenn in einem Netzwerk ein Paket zur Weitergabe einen Knoten erreicht, wird unter den verschiedenen Alternativen für dieses Paket gewählt, unabhängig von bereits getroffenen Entscheidungen für andere Pakete mit dem gleichem Ziel. Bei Netzen mit virtuellen Verbindungen wird ein Leitweg beim Aufbau einer Verbindung gewählt, aber für verschiedene virtuelle Verbindungen (von verschiedenen Benutzern) werden die Leitwege unabhängig voneinander zugeteilt.

Zur Realisation dieses Verfahrens muß in jedem Rechner des Netzwerkes eine Leitwegtabelle hinterlegt sein. Die Tabelle enthält für jeden möglichen Zielrechner eine Zeile. In den Spalten stehen die beste, zweitbeste, drittbeste usw. Ausgangsleitungen für dieses Ziel, zusammen mit einer relativen Gewichtung. Bevor ein Paket weitergegeben wird, erzeugt der Rechner eine Zufallszahl und wählt dann unter den Alternativen aus, indem er die Gewichtung als Wahrscheinlichkeiten benutzt. Die Tabellen werden manuell von Netzwerk-Operatoren ausgearbeitet, vor dem Hochfahren in die Rechner geladen und ab dann später nicht mehr verändert.

Für das in Abbildung 3.5 dargestellte Beispielnetzwerk,

zeigt die Abbildung 3.6 die Leitwegtabelle von Rechner 2.

Für jeden Rechner im Netzwerk gibt es einen Zeileneintrag in der Tabelle. Wenn im oben gezeigten Beispiel ein Paket von Rechner 2 nach Rechner 3 geschickt werden soll, gibt es für die Quelle drei Möglichkeiten das Paket los zu werden. Rechner 2 ermittelt eine Zufallszahl z im Bereich von 0 und 99. Anschließend vergleicht der Rechner die Zufallszahl mit den Wahrscheinlichkeiten in der Zeile für den Zielrechner und erhält dann nach folgendem Schema die Ausgangsleitung:

0 <= z < 65 Ausgangsleitung zu Rechner 3

65 <= z < 85 Ausgangsleitung zu Rechner 4

85 <= z < 100 Ausgangsleitung zu Rechner 1

Dieses Verfahren wird bei jedem zu versendenden Datenpaket neu gestartet.

Die Kernidee dieses Algorithmus besteht darin, daß jeder Knoten aus den weiterzuleitenden Datenpaketen Informationen über den bisherigen Weg der Daten gewinnen kann. Eine einfache Implementierungsmöglichkeit besteht darin, daß die Daten neben der Information über ihren Quellknoten auch einen Zähler enthalten, in dem die Anzahl der bereits passierten Rechner angegeben ist. Damit ist es den Rechnern möglich, aus den Knotenzählern den Abstand zu dem Quellknoten zu berechnen. Diese Informationen werden in den Leitwegtabellen gespeichert. Besitzt ein empfangenes Paket den Wert 1, stammt das Paket von dem Nachbarknoten am anderen Ende der Verbindungsleitung, auf dem das Paket eingegangen ist. Trifft eine Nachricht ein, deren Knotenzähler einen geringeren Wert als den bisher in der Leitwegtabelle eingetragenen besitzt, wird der alte Wert durch den neuen überschrieben. Durch Verarbeitung und Speicherung der so erhaltenen Informationen lernt ein Knoten das ganze Netz und die Entfernung zu den anderen Knoten kennen.

Dieses Verfahren funktioniert nach einer bestimmten Einschwingphase sehr gut, besitzt jedoch den Nachteil, nur Verbesserungen des Netzwerkes zu erlernen. Fällt ein Knoten aus oder treten Überlastsituationen auf, so besteht keine Möglichkeit, auf diese neue Situation zu reagieren. Allerdings gibt es Ansätze, diese Nachteile des Rückwärtslernens auszugleichen, indem alle Knoten veranlaßt werden, ihre Informationen nach einer bestimmten Zeit zu vergessen, und die Topologie- und Abstandsinformation neu zu erlernen. Während der Einschwingphase ist der Algorithmus jedoch weit von einer optimalen Wegeermittlung entfernt, so daß eine zu häufig durchgeführte Erneuerung der Informationen zu völlig instabilen Routingentscheidungen führt. Werden die Tabellen hingegen nur sehr selten gelöscht, ist der Anpassungsprozeß an eine veränderte Netztopologie in der Regel zu langsam. Ein weiterer wesentlicher Nachteil dieses Verfahrens besteht darin, daß von einer symetrischen Leitungsbelastung in beide Übertragungsrichtungen ausgegangen wird. Das kann jedoch in den meisten Fällen nicht vorausgesetzt werden.

Die wohl extremste Form der Wegewahl ist das Fluten. Bei diesem Verfahren wird jede in einem Knoten ankommende Nachricht aus allen Ausgangsleitungen weitergesendet, außer auf diejenige, auf der sie eingetroffen ist. Um zu verhindern, daß durch dieses Verfahren unbeschränkt viele Duplikate einer Nachricht im Netz entstehen, müssen Vorkehrungen zur Begrenzung der Duplikate getroffen werden. Die hierfür einfachste Technik besteht darin, jedes Paket mit einem Zähler auszustatten und bei jedem Kopiervorgang des Paketes diesen Zähler zu dekrementieren. Erreicht der Zähler den Wert 0, so wird das Paket zerstört. Eine Voraussetzung für die Durchführbarkeit dieses Verfahrens besteht allerdings darin, daß der Sender einer Nachricht die Anzahl der Teilstrecken zum Empfänger kennt. Im besten Fall wird der Zähler diesen Startwert bekommen, andernfalls muß der Sender die maximale Anzahl der Teilstrecken zwischen zwei Knoten im gesamten Netz angeben, was wiederum zu einer starken Leistungsbelastung führt.

Eine andere Möglichkeit ist, in jedes abgesandte Paket eine Folgenummer eintragen zu lassen. Jeder Rechner benötigt dann pro Quellrechner eine Liste. Sie enthält, diejenigen Pakete, die von diesem Knoten kommen, und schon einmal da waren. Um zu verhindern, daß die Liste ins unendliche wächst, wird auch sie mit einem Zähler k ausgestattet, der angibt, daß alle Folgenummern bis einschließlich k bereits vorbeikamen. Wenn ein Paket ankommt, kann leicht festgestellt werden, ob es sich um ein Duplikat handelt und zerstört werden kann.

Der Hauptnachteil des Flutens liegt in der extrem großen Anzahl von Paketen, die während der Übertragung zwischen der Quelle und der Senke erzeugt werden und der damit verbundenen starken Belastung der Übertragungsleitungen. Andererseits besitzt dieses Verfahren auch einige bemerkenswerte Eigenschaften, wie die extreme Robustheit bei Veränderungen der Topologie eines Netzes oder die Fähigkeit, stets ein Paket auf dem kürzesten bzw. schnellsten Weg zu übertragen.

Diese Eigenschaften sind zum Beispiel bei militärischen Anwendungen von großer Bedeutung. Da jederzeit eine große Anzahl von Rechnern ausfallen kann ist die extreme Robustheit des Algorithmus sehr wünschenswert. Bei verteilten Datenbanken ist es manchmal notwendig, alle Datenbanken gleichzeitig auf den neuesten Stand zu bringen, wobei das Fluten nützlich sein kann. Außerdem bietet sich das Fluten als Bezugsverfahren für den Vergleich und die Bewertung anderer Wegewahlverfahren an, da immer der kürzeste Weg ausgewählt wird. Darüber hinaus sind keine Leitwegtabellen oder Berechnungen in den Knoten erforderlich.

Sofwareengineering (-entwicklung) befaßt sich mit der Planung (Analyse), dem Entwurf (Design) und der Implementierung von Softwaresystemen. Im Rahmen der Durchführung eines Softwareprojekts wird versucht, den Entwicklungsprozeß zu strukturieren und wiederholbar zu gestalten. Neben technischen Aspekten, wie dem Einsatz von geeigneten Methoden und Werkzeugen, sind auch nicht technische, wie die Kommunikation mit dem Anwender, Bestandteil des Softwareengineerings. Zu den eingesetzten Methoden zählen neben Softwareentwicklungsmethoden auch Techniken des Projektmanagements, die mit zunehmender Größe eines zu entwickelnden Systems an Bedeutung gewinnen. Ziele, die durch ein ingenieurmäßiges Vorgehen bei der Softwareentwicklung erreicht werden sollen, sind unter anderem:

• Korrektheit und Überprüfbarkeit,
• Robustheit,
• Erweiterbarkeit,
• Wiederverwendbarkeit,
• Effizienz,
• Benutzerfreundlichkeit sowie
• Wartungsfreundlichkeit des entstehenden Softwareprodukts.

Zur Beschreibung einer sinnvollen Vorgehensweise bei der industriellen Softwareentwicklung werden in der Literatur zahlreiche Ansätze vorgeschlagen. Die klassische Sichtweise unterteilt den Softwareentwicklungsprozeß in die Phasen Analyse, Design, Implementierung, Test und Wartung. Die einzelnen Phasen sollen zu vorhergeplanten Zeitpunkten beendet sein. Da eine streng sequentielle Vorgehensweise der Softwareerstellung in der Praxis jedoch kaum einzuhalten ist, sind in den heute üblichen Versionen des Modells Rückschritte in die jeweils vorangegangene Phase zugelassen [9].

Die einzelnen Phasen kann man wie folgt beschreiben:

Ziel einer Systemanalyse ist es, ein vollständiges und konsistentes logisches Ist-Modell des für die Softwareentwicklung relevanten Realweltausschnittes zu erstellen. Dabei werden die problemspezifischen Anforderungen an das Produkt festgelegt und in einer sowohl für den Anwender, als auch für den Systementwickler verständlichen Notation dargestellt. Hier ist ein intensiver Dialog zwischen diesen beiden Gruppen erforderlich. Seitens der späteren Anwender muß festgelegt und erklärt werden, welche Probleme zugrunde liegen, wie sie aktuell bearbeitet werden, wie man sich zukünftige Abläufe vorstellt und welche Leistungsmerkmale dabei wichtig sind. Aus Sicht der Entwickler muß dieser Bereich zunächst verstanden werden, damit der in den nachfolgenden Entwicklungsphasen erforderliche Übergang von der Realwelt in die entsprechenden Softwarekonstrukte gelingen kann und von möglichst wenigen Mißverständnissen behindert wird. Um den Anwendern ihre jeweils aktuelle Sicht des Problembereichs erfolgreich vermitteln zu können, sollten die Entwickler in dieser Phase Methoden verwenden, die in ihrer Notation unabhängig von der später zur Implementierung verwendeten Programmiersprache sind.

In der Designphase wird das im vorhergehenden Entwicklungsschritt erstellte Analysemodell um lösungsspezifische Komponenten erweitert. Hierbei stehen Fragen im Zusammenhang mit der Benutzerführung, dem Datenhandling, der Taskkoordination, der Verteilung von Systemkomponenten oder der vorgesehenen Hardware und Betriebssysteme im Mittelpunkt. Letzterer Punkt kann bei der Implementierung mit Java entfallen, da ja plattformunabhängig programmiert werden kann. Das Systemdesign kann daher nicht mehr unabhängig von der verwendeten Programmiersprache bzw. Softwareentwicklungsumgebung und den entsprechenden Kenntnissen der Entwickler sein.

In der Implementierungsphase werden die Ergebnisse der beiden vorangegangenen Phasen in die Konstrukte der jeweiligen Programmierumgebung umgesetzt. Dies gelingt einfacher, wenn die in der Designphase eingesetzte Methodik gleiche oder ähnliche Konzepte bereitstellt, wie die zur Codierung benutzten Sprachen.

Getestet werden sowohl die einzelnen Programm-Module, als auch die externe Funktionalität des Softwareprodukts. Wichtig ist der Akzeptanztest bei den Anwendern, der alle Phasen der Entwicklung begleitet.

Unter Systemwartung werden schließlich die Aufgaben an der Software zusammengefaßt, die nach Fertigstellung und Inbetriebnahme des Systems notwendig werden.

Im folgenden werden die Phasen der Analyse und der Implementierung genauer betrachtet.

Die Notation, die im folgenden verwendet wird, um das statische Systemmodell darzustellen, ist von Coad und Yourdan. Dabei werden Klassen durch abgerundete Rechtecke dargestellt. Man unterscheidet abstrakte Klassen, die keine Objekte enthalten können und nicht abstrakte Klassen. Sie werden durch eine Umrandung des Klassensymbols modelliert. Das obere Drittel des Klassensymbols enthält den Namen der Klasse, das mittlere Drittel ist für die Angabe der Attribute, das untere Drittel ist für die Aufzählung der Methoden reserviert.

Für die Unterscheidung zwischen Klassen und ihren Objekten ist die korrekte Darstellung von Strukturen, Beziehungen und Nachrichten wichtig.

In diesem Abschnitt werden die Strukturen, Beziehungen und Nachrichten, sowie die Attribute und Methodennamen bewußt weggelassen, damit das Diagramm übersichtlich und lesbar bleibt. Im Schaubild werden die Vererbungsstrukturen durch einen Halbkreis dargestellt, wobei der Kreis in Richtung der Basisklasse und die Linie in Richtung der abgeleiteten Klassen zeigt.

Eine komplette Beschreibung der Klassen mit ihren Attributen, Methoden, Objektverbindungen und Nachrichtenverbindung folgt im Kapitel 4.2.2 Klassenspezifikation.

Das folgende Schaubild (Abb. 4.1) zeigt die Klassenhierachie des Programms. Klassen die mit dem Namen "java" beginnen sind hierbei Systemklassen, die in der Entwicklungsumgebung von Java integriert sind. Alle anderen Klassen werden natürlich an die bereits existierende Klassenhierachie von Java angepaßt.

Die Reihenfolge der Klassenbeschreibungen entpricht in etwa der Reihenfolge einer möglichen Abarbeitung. Den internen Programmablauf kann man mit Hilfe der Objektverbindungen nachvollziehen.

Bei den Beschreibungen von Teilklassen und Objektverbindungen tritt die Bezeichnung Kardinalitäten auf. Sie gibt jeweils die Anzahl der Objekte an, die zu einem bestimmten Zeitpunkt an der Struktur beteiligt sein können. Als Notation für diese Anzahl werden 0 bzw. 1,n oder m eingesetzt. Eine 1 bedeutet, daß jedes Objekt der ersten Klasse mit genau einem Objekt der zweiten Klasse verbunden ist, und 0,1 steht für höchstens eine Verbindung. Analog zeigen 1,n bzw. 0,n mindestens eine bzw. keine oder mehrere mögliche Verbindungen an.

Das ist die Hauptklasse des Programms. Sie wird beim Programmstart aufgerufen. Im wesentlichen erfolgt hier nur der Aufruf der Fenster Klasse.

1. Runnable

Kardinalitäten: Routing 1 – Runnable 1

Erzeugt einen Thread, der nur als Dummie benutzt wird um eine Threadgruppe zu erzeugen.

1. threadgroup

Datentyp: ThreadGroup

Erzeugt die Threadgruppe, der jeder Thread zugefügt wird.

1. Fenster

Kardinalitäten: Routing 1 – Fenster 1

Programmhauptfenster, in dem die gesamte Animation abläuft.

1. init

Argumente: keine

Funktionswert: void

Wird beim Starten der Klasse Routing ausgeführt und ruft den Konstruktor der Fenster Klasse auf.

Hier wird das Programmfenster erstellt. In ihm läuft die gesamte Animation ab.

1. Bild

Kardinalitäten: Fenster 1 – Bild 1

Stellt die Zeichenfläche für die Animation dar.

 

2. Sortest_Path

Kardinalitäten: Fenster 0,1 – Shortest_Path 1

Klasse zur Ausführung der Animation für den Shortest Path Algorithmus.

 

3. Multipath

Kardinalitäten: Fenster 0,1 – Multipath 1

Klasse zur Ausführung der Animation für den Multipath Algorithmus.

 

4. Backward_Learning

Kardinalitäten: Fenster 0,1 – Backward_Learning 1

Klasse zur Ausführung der Animation für den Backward Learning Algorithmus.

 

5. Flooding

Kardinalitäten: Fenster 0,1 – Flooding 1

Klasse zur Ausführung der Animation für den Flooding Algorithmus.

 

6. Eingabe

Kardinalitäten: Fenster 0,1 – Eingabe 1

Ermöglicht die Eingabe von Werten in einem neuen Fenster. Eingegeben werden Daten für die Netzwerte, den Paketzähler bei Flooding und der Animationsgeschwindigkeit.

 

7. Hilfe

Kardinalitäten: Fenster 0,1 – Hilfe 1

Zeigt den gewählten Hilfetext in einem separaten Fenster an.

 

8. AnzeigeLT_mp

Kardinalitäten: Fenster 0,1 – AnzeigeLT_mp 1

Zeigt die Leitwegtabelle beim Multipath Algorithmus für den gewünschten Rechner in einem eigenen Fenster an.

 

9. AnzeigeLT_bl

Kardinalitäten: Fenster 0,1 – AnzeigeLT_bl 1

Zeigt die Leitwegtabelle beim Backward Learning Algorithmus für den gewünschten Rechner in einem eigenen Fenster an.

1. Fenster

Argumente: Objektvariable Routing

Funktionswert: keine, da Konstruktor der Klasse

Es wird das komplette Layout des Fensters erstellt. Unter der Menüleiste, in der man sämtliche Funktionen des Programms auswählen kann, befindet sich eine TextArea in der Hinweise zum momentanen Stand der Animation erscheinen. In der Mitte des Fensters ist die Zeichenfläche (Klasse Bild). Dort entsteht das Netzwerk und spielt sich die Animation der Algorithmen ab. Unter der Zeichenfläche befinden sich noch 4 verschiedene Buttons.

 

2. action

Argumente: Objektvariablen Event und Object

Funktionswert: boolean

In dieser Methode werden sämtliche Ereignisse von der Menüleiste und den Buttons abgefangen und bearbeitet.

Das ist die Zeichenfläche, die in die Klasse Fenster eingebunden ist.

1. m

Datentyp: int[][]

Quadratische Matrix in der das gesamte Netzwerk abgespeichert wird. Jede Zeile und Spalt der Matrix steht für einen Rechner. Die Werte in der Matrix geben die Nummer des Netzes an, das die zwei Rechner miteinander verbindet. Steht ein 0, so verbindet die Rechner kein Netz.

Steht in der Matrix an der Position (2,3) eine 2, so bedeutet das, daß Rechner 2 mit Rechner 3 durch das Netz Nummer 2 verbunden ist. Der Wert 2 steht logischerweise auch bei der Position (3,2).

 

2. anz_rechner

Datentyp: int

Speichert die Gesamtanzahl der Rechner im Netzwerk.

 

3. anz_netz

Datentyp: int

Speichert die Gesamtanzahl der Netze im Netzwerk.

1. Rechner

Kardinalitäten: Bild 0,n – Rechner 1

Für jeden gezeichneten Rechner entsteht ein neues Objekt der Klasse Rechner. Die Objekte werden in einem Array abgespeichert.

 

2. Netz

Kardinalitäten: Bild 1,n – Netz 1

Für jedes gezeichnete Netz entsteht ein neues Objekt der Klasse Netz. Diese werden in einem Array abgespeichert.

1. paint

Argumente: keine

Funktionswert: void

Zeichnet das Bild neu mit dem in m gespeicherten Netzwerk.

 

2. standard

Argumente: keine

Funktionswert: void

Stellt den Anfangszustand des Netzwerkes wieder her. Dies ist zum einen die Farbe, sowie die Bezeichnungen der Rechner.

 

3. netzwerk

Argumente: keine

Funktionswert: void

Konstruiert ein Netzwerk mit 8 Rechnern und speichert es in m ab.

 

4. Netzwerk_klein

Argumente: keine

Funktionswert: void

Konstruiert ein Netzwerk mit 4 Rechnern und speichert es in m ab.

 

5. init_lt_mp

Argumente: keine

Funktionswert: void

Initialisiert die Leitwegtabellen für jeden Rechner im Netzwerk für den Multipath Algorithmus.

 

6. init_lt_bl

Argumente: keine

Funktionswert: void

Initialisiert die Leitwegtabellen für jeden Rechner im Netzwerk für den Backward Learning Algorithmus.

 

7. mouseDown

Argumente: Objektvariable Event, sowie Integer x und y

Funktionswert: boolean

Hier werden alle Mausereignisse, die auf der Zeichenfläche passieren, abgefangen und abgearbeitet.

 

9. mouseDrag

Argumente: Objektvariable Event, sowie Integer x und y

Funktionswert: boolean

Hier wird das Verschieben eines Rechners mit gedrückter Maustaste abgearbeitet.

 

10. del_netz

Argumente: Integer del_netz

Funktionswert: void

Löscht das Netz mit der Nummer del_netz aus dem Netzwerk.

 

11. del_rechner

Argumente: Integer del_rechner

Funktionswert: void

Löscht den Rechner mit der Nummer del_rechner mit seinen Verbindungen zu anderen Rechnern aus dem Netzwerk.

1. Fenster

Die TextArea im Fenster wird dadurch immer aktualisiert.

Es wird ein Rechner auf die Zeichenfläche Bild gezeichnet.

1. lt

Datentyp: int[][]

Matrix, in der die Leitwegtabelle des Rechners für die Algorithmen Multipath und Backward Learning gespeichert wird.

1. zeichne

Argumente: Graphics

Funktionswert: void

Zeichnet einen Rechner.

 

2. Zeichne_sp

Argumente: keine

Funktionswert: void

Zeichnet einen Rechner für den Shortest Path Algorithmus, das bedeutet es werden auch die Daten für die Länge und den Vorgänger benötigt.

 

4. Zeichne_bl

Argumente: keine

Funktionswert: void

Zeichnet einen Rechner für den Backward Learning Algorithmus.

Desweiteren stehen noch Methoden für das Lesen der Positionswerte, sowie das Verändern der abgekapselten Daten zur Verfügung.

1. Bild

Damit der Rechner auf das Bild gezeichnet und evtl. Verschoben oder gelöscht werden kann.

Zeichnet eine Verbindungslinie zwischen zwei Rechnern.

1. von

Datentyp: int

Gibt den Rechner an, von dem ab das Netz gezeichnet wurde. Dies ist wichtig, das bei der späteren Animation die Richtung des Netzes bekannt sein muß.

Es stehen Methoden für das Lesen der Positionswerte, sowie das Verändern der Daten zur Verfügung.

1. Bild

Damit das Netz auf das Bild gezeichnet und evtl. gelöscht werden kann.

Die Klassen für die verschieden Algorithmen kann man zusammenfassen, da sie im Aufbau gleich sind und sich nur in ihrer run-Methode unterscheiden.

1. Runnable

Kardinalitäten: Algo’s 1- -Runnable 1

Stellt einen Thread bereit, der für die Animation des Algorithmus notwendig ist.

1. Punkt_sp, Punkt_mp, Punkt_bl oder Punkt_fl (Punkt_algo)

Kardinalitäten: Algo’s 1 – Punkt_algo 1

Ruft die Klasse für die Punktanimation von einem Rechner zum anderen auf.

1. run

Argumente: keine

Funktionswert: void

Hier findet der eigentliche Algorithmus statt. Es werden die Berechnungen der einzelnen Rechner durchgeführt und die einzelnen Punktanimationen gestartet.

1. Routing

Damit der Thread des Algorithmus zu der ThreadGroup in Routing zugeordnet werden kann.

 

2. Bild

Diese Verbindung ist notwendig, um die Animationen der Punkte auf der Zeichenfläche darzustellen.

Abstrakte Basisklasse für Punkt_sp, Punkt_mp, Punkt_bl und Punkt_fl. Diese Klassen unterscheiden sich nur in ihren Konstruktoren. Es wird immer die Klasse des Algorithmus übergeben.

1. t

Datentyp: Thread

Ermöglicht die Bewegung des Punktes von Start- zu Endrechner.

1. run

Argumente: keine

Funktionswert: void

In dieser Methode werden die einzelnen Werte der Bewegung des Punktes ermittelt, bis der Punkt sein Ziel erreicht hat.

1. Bild

Damit der fortlaufende Punkt auf das Bild gezeichnet werden kann.

Erzeugt ein Fenster für die Eingabe von verschiedenen Daten. Zum einen den Netzwert, den Paketzähler beim Flooding Algorithmus, sowie die Geschwindigkeitsregulierung der Animation. Die unterschiedlichen Eingabemöglichkeiten werden durch drei Konstruktoren realisiert.

1. art

Datentyp: int

Gibt an, um was für eine Dateneingabe es sich handelt, damit das Ergebnis auch korrekt zugewiesen werden kann.

1. Eingabe

Argumente: Bild, Netz, int x, int y

Argumente: Bild, Flooding, int x, int y

Argumente: Bild, int x, int y

Funktionswert: keiner, da Konstruktor

Hier wird der Polymorphismus in objektorientierten Systemen ausgenutzt. Es ist möglich durch Aufrufen der selben Methode (gleicher Name) mit unterschiedlichen Argumenten, unterschiedliche Konstruktoren anzusprechen. Dadurch ist beim Aufruf des Konstruktors sofort die Art der Dateneingabe bekannt.

 

2. action

Argumente: Event, Object

Funktionswert: boolean

In dieser Methode werden die Eingaben abgefangen und abgearbeitet.

Nachrichtenverbindungen hängen vom gewählten Konstruktor ab und gehen zum Bild, Flooding oder Netz.

Es werden neue Fenster erstellt, in denen die Leitwegtabelle des gewählten Rechners angezeigt wird. Dies gilt für die Algorithmen Multipath und Backward Learning.

1. Multipath oder Backward_Learning (Algo)

Kardinalität: Anzeige 1 – Algo 1

Während der Anzeige wird der Algorithmus angehalten.

1. paint

Argumente: Graphics

Funktionswert: void

Die Leitwegtabelle wird gezeichnet.

 

2. action

Argumente: Event, Object

Funktionswert: boolean

In dieser Methode werden alle Mausereignisse abgefangen und abgearbeitet.

1. Rechner

Verweist auf den ausgewählten Rechner, dessen Leitwegtabelle anzuzeigen ist.

Zeigt den gewählten Hilfetext in einem eigenen Fenster an.

1. i

Datentyp: int

Wert, der im Konstruktor einen bestimmten Text im Fenster anzeigt.

Es gibt Methoden mit den Funktionswert String, die einen Hilfetext zurückgeben.

Die Objektverbindungen der einzelnen Klassen finden gegenseitig statt. Die Verbindungen wurden bewußt nur in einer Richtung aufgenommen, um zum einen die Verbindungsrichtung darzustellen und zum anderen die Klassenspezifikation nicht noch mehr aufzublasen.

In diesem Kapitel wird kurz auf die Datenstrukturen der wesentlichen Bestandteile der Algorithmen eingegangen.

Im einzelnen sind das die Rechner, die Verbindungen zwischen den Rechnern (Netzte), sowie das komplette Netzwerk.

Wie im Abschnitt 4.2.2 erwähnt, werden sowohl die Rechner, wie auch die Netze in einem Array abgespeichert. Der Arrayindex gibt die Nummer des Rechners oder des Netzes an. Die Gesamtstruktur des Netzwerkes wird in einer Matrix abgespeichert, wobei jeder Eintrag an der Stelle (i,j) ungleich null der Nummer des Netzes entspricht, das Rechner i mit Rechner j verbindet. Ein Eintrag 0 bedeutet, daß die beiden Rechner nicht verbunden sind.

Mit Hilfe dieser Matrix kann man den Shortest Path Algorithmus relativ leicht realisieren. Zum einen ist es wichtig, die Nachbarrechner zu erkennen und zum anderen welches Netz sie verbindet. Um die Nachbarrechner von Knoten i zu bekommen, schaut man nach allen Einträgen in der Zeile i, deren Wert ungleich null ist. Die Spaltennummern entsprechen den Nummern der Nachbarrechner.

Beim Multipath und Backward Learning Algorithmus müssen Leitwegtabellen für jeden Rechner hinterlegt werden. Diese Leitwegtabelle wird wiederum mit Hilfe einer Matrix realisiert. Bevor ein Paket von einem Knoten versendet wird, wird in der Matrix nach der Ausgangsleitung mit Hilfe der entsprechenden Algorithmusvorschrift gesucht.

Einige Schwierigkeiten verursachte die Implementierung des Flooding Algorithmus. Auf den ersten Blick ist der Algorithmus sehr simpel. Jeder Knoten dupliziert das ankommende Paket und versendet es auf jeder Ausgangsleitung, außer auf der es angekommen ist. Die Animation dieses Algorithmus verlangt aber nicht die Sichtweise eines Rechners, sondern die des gesamten Netzwerkes. Bei jedem Durchlauf kann sich die Anzahl der Pakete potenzieren. Um diesem Sachverhalt gerecht zu werden, implementiert man eine Hilfsmatrix, in der für jeden Durchlauf eine neue Zeile mit allen Daten der zu versendenden Pakete eingetragen wird.

Um ein Paket zu versenden, benötigt man den Anfangsrechner und den Endrechner des zu verlaufenden Punktes. Damit es offensichtlich wird, wann die nächsten Daten für einen Punkt anfangen, muß noch eine Startmarke (-1) in die Matrix gesetzt werden.

Das folgende Beispiel soll den Aufbau der Hilfsmatrix verdeutlichen. Es wird das Netzwerk aus Kapitel 3.4.2 (Abb. 4.2) benutzt.

Die Daten sollen von Rechner 1 nach Rechner 4 versandt werden. Der Paketzähler wird auf 3 gesetzt, das bedeutet, wenn ein Paket bei der dritten Station angekommen ist, und noch nicht beim Zielrechner ist, wird es zerstört.

Im ersten Durchlauf versendet Rechner 1 das Paket zu Rechner 2 und Rechner 3. Im nächsten Durchlauf versendet Rechner 2 das Paket zu Rechner 3 und 4, und Rechner 3 versendet das Paket zu Rechner 2 und 4.Bereits in diesem kleinen Beispiel hat sich die Anzahl der Pakete verdoppelt. Im dritten und letzten Durchlauf versendet Rechner 2 das Paket zu Rechner 1 und 4 und Rechner 3 zu Rechner 1 und 4. Damit ist der Flooding Algorithmus abgearbeitet.

Die Hilfsmatrix hat folgende Werte:

Die Matrix nimmt enorme Ausmaße für nur wenig größere Rechnernetze an und die Erstellung ist mit großem Aufwand verbunden

Ziel dieser Studienarbeit ist die Entwicklung einer interaktiven Animation von Routingalgorithmen. Durch diese Animation sollen die Funktionsweisen der Algorithmen erlernt werden. Diese Ziele werden durch viele variable Eingabemöglichkeiten realisiert. Um den Lerneffekt zu verbessern, können die Algorithmen an selbsterstellten Netzwerken demonstriert werden. Dadurch entstehen immer wieder neue Situationen mit unterschiedlichen Schwierigkeiten. Da der Anwender selber in das Programm mit einbezogen wird, und es nicht nur eine Simulation ist, wird auf eine spielerische Art die Vorgehensweise der Algorithmen erklärt. Es besteht auch die Möglichkeit, jeden Schritt des Algorithmus einzeln darzustellen und erst nach dem dieser verstanden worden ist, kann der nächste Schritt ausgeführt werden.

Dadurch wird der "learning by doing" Effekt sehr gut ausgenützt.

Durch die häufigen Änderungen während der Erstellungsphase sind die Klassen nicht mehr optimal. So ist zwar eine Erweiterung möglich, doch müssen eventuell auch bereits bestehende Klassen geändert werden.

Eine Verbesserungsmöglichkeit besteht in der Darstellung der Rechner. Man könnte kleine Bilder von Computern benutzen, um die Rechner darzustellen. Desweiteren gibt es manchmal Probleme mit dem automatischen Zeichnen der Netze. Es gibt nur vier Ansatzpunkte der Netze am Rechner. Diese sind jeweils in der Mitte einer Kante des Rechners. Dadurch starten bzw. enden manchmal zwei Netze an einem Punkt. Es wäre besser, wenn das Netz dort gezeichnet wird, wo der Anwender mit der Maus hinklickt.

Andere Verbesserungsmöglichkeiten beziehen sich auf die Handhabung des Programms. Diese sind aber immer subjektiv, da die Vorstellungen von Anwender zu Anwender verschieden sind. Grundsätzlich kann mit dem Programm jedes Netzwerk erstellt werden und zur Animationszwecken verwendet werden.

Als Erweiterung kann ein Übungsmodus implementiert werden. Vor jedem Schritt, wird der Anwender nach einer Möglichkeit gefragt. Je nach Antwort, kann sie korrigiert werden mit entsprechendem Hilfetext oder bestätigt werden. Dadurch kann das Lernergebnis kontrolliert werden.

Beim Aufruf der HTML-Seite wird das Applet geladen. Es erscheint das Hauptfenster über dem Browser. In diesem Fenster finden die gesamten Animationen statt. Es unterteilt sich in vier Bereiche: Die Menüleiste, einem Textfeld (hier werden immer aktuelle Informationen angezeigt), einer Zeichenfläche und der Leiste mit den Knöpfen (im folgenden Button). Die Handhabung des Programms wird ausschließlich mit der Maus vollzogen. Zum Bestätigen der Menüpunkte oder der Button’s genügt die linke Maustaste. Die Anordnung der Menüpunkte, sowie der Button’s zeigt auch gleichzeitig eine Reihenfolge der Vorgehensweise an. Grauunterlegte Menüpunkte und Button’s sind deaktiviert und momentan nicht verfügbar.

Im folgenden werden die einzelnen Menüpunkte, Button’s und die Vorgehensweise erläutert.

Um ein Routingalgorithmus zu animieren, ist ein Netzwerk erforderlich. Es gibt mehrere Möglichkeiten, ein Netzwerk zu erstellen. Zum einen sind zwei vorgefertigte Netzwerke vorhanden und desweiteren besteht die Möglichkeit, selbst ein Netzwerk zu zeichnen. Wenn das Netzwerk fertiggestellt ist, muß der Algorithmus ausgewählt werden. Jeder Algorithmus benötigt zur Ausführung noch einen Start- und Endrechner, die man mit der Maus markieren kann. Durch Betätigen der Start-Taste beginnt die Animation.

Es gibt noch einige Variationen, die nun näher beschrieben werden.

Das Hauptfenster der Animation wird geschlossen und neu gestartet. Diese Funktion ist auch sinnvoll, wenn das erstellte Netzwerk nicht korrekt ist und man nochmals von neuem beginnen will. Nach dem Start des Hauptfensters, erscheinen Informationen im Textfeld über das Erstellen eines Netzwerkes, sowie über das Hilfsmenü.

Das Hauptfenster wird geschlossen. Es erscheint die HTML-Seite, auf der das Applet eingebunden ist.

Es wird ein vorgefertigtes Netzwerk gezeichnet das aus 8 Rechnern besteht.

Die Zahlen an den einzelnen Netzen bedeuten die Gewichtung des Netzes. Dieser Wert, sowie die unteren Hälften der Rechner, werden beim Shortest Path Algorithmus benötigt um den kürzesten Weg zu ermitteln (siehe Kapitel 3.4.1). Dieses Netzwerk ist hervorragend dazu geeignet, die Vorgehensweise vom Shortest Path Algorithmus zu veranschaulichen. Für die Algorithmen Multipath, Backward Learning und Flooding ist das Netzwerk stellenweise zu groß, um die teilweise sehr komplexe Vorgehensweise zu demonstrieren. Es steht unter Bearbeiten/Netzwerk klein ein günstigeres Netzwerk zur Verfügung. Natürlich können die Algorithmen trotzdem auf diesem Netzwerk gestartet werden. Als Vergleich ist dies eine sehr gute Übung.

Wenn das Netzwerk gezeichnet ist, muß unter dem Menüpunkt Algorithmen ein Routingalgorithmus ausgewählt werden.

Ein Netzwerk mit vier Rechnern wird gezeichnet. Wie oben beschrieben sind die Werte an den Netzen und die leeren unteren Hälften der Rechner für den Shortest Path gedacht. An diesem kleineren Netzwerk kann hervorragend nachvollzogen werden, wie der gewählte Algorithmus arbeitet. Wenn die Vorgehensweise verstanden ist, kann man sich den Algorithmus am großen Netzwerk veranschaulichen. Um das große Netzwerk zu erstellen, betätigt man einfach Bearbeiten/Netzwerk. Das aktuelle Netzwerk wird dann überschrieben.

Nach Auswahl des Menüpunktes muß ebenfalls, wie unter Bearbeiten/Netzwerk mit dem Menüpunkt Algorithmus weitergemacht werden.

Nach Betätigung dieses Menüpunktes kann durch einfaches Klicken mit der linken Maustaste auf die Zeichenfläche ein Rechner erstellt werden. Der Rechner bekommt die Bezeichnung "Rechner n", wobei n eine fortlaufende Zahl ist. Es können beliebig viele Rechner erstellt werden. Um die Rechner an die gewünschte Position zu bringen, kann durch Anklick und Halten der linken Maustaste der Rechner auf der gesamten Zeichenfläche verschoben werden.

Falls sich zu viele Rechner auf dem Bildschirm befinden, kann man beliebig viele Rechner löschen. Der Rechner muß mit der Maus markiert werden. Er erscheint nun hellgrau. Durch Betätigen der Taste "Loeschen" wird der markierte Rechner entfernt.

Stimmt die Anzahl der Rechner und deren Position, muß mit dem Menüpunkt "Bearbeiten/Netz zeichnen" fortgefahren werden.

Die Netze verbinden die Rechner zu einem Netzwerk. Um ein Netz zu zeichnen, klickt man nacheinander die beiden Rechner an, die miteinander verbunden werden sollen. Am Netz erscheint eine Null, welche die Gewichtung des Netzes oder den Netzwert angibt. Dieser Wert wird beim Shortest Path Algorithmus benötigt. Die Einstellung dieses Wertes wird unter "Bearbeiten/Netzwert eingeben" beschrieben.

Soll ein Netz wieder entfernt werden, muß es durch Anklicken markiert werden und anschließend der Button "Loeschen" betätigt werden.

Wenn das Netzwerk vollständig erstellt wurde, gibt es zwei Möglichkeiten fortzufahren:

Die Netzwerte werden ausschließlich für den Shortest Path Algorithmus benötigt.

Um die Werte den einzelnen Verbindungen zuzuordnen, muß der Netzwert (Standard 0) mit der Maus angeklickt werden.

Mit Hilfe der Zifferntasten kann jeder beliebige Wert eingegeben werden. Nach betätigen mit der "OK"-Taste wird die Gewichtung an das ausgewählte Netz geschrieben.

Dieser Vorgang muß bei allen Netzen wiederholt werden. Soll ein Netzwert geändert werden, kann dies auf gleiche Weise geschehen.

Wenn alle Netzwerke eingegeben sind, muß die Taste "Fertig/Reset" gedrückt werden um alle Einstellungen zu übernehmen. Danach kann mit dem Menüpunkt Algorithmen weitergemacht werden.

Die Funktionsweisen der Algorithmen sind unter 3.4 erklärt.

Nach Aktivierung des Menüpunktes erscheint eine kleine Erklärung von Shortest Path im Textfeld. Bei den Rechnern ist nun die untere Hälfte mit Leben erfüllt. Die Standardwerte von Länge ist 100 und der Vorgänger (Vorg.) ist jeweils 0.

Beim Ausführen des Algorithmus werden die Werte fortlaufend aktualisiert.

Um den kürzesten Weg zu berechnen, muß ein Start- und ein Endrechner im Netzwerk angegeben werden. Dies geschieht ganz einfach, in dem zuerst der Startrechner angeklickt wird und anschließend der Endrechner. Nach Auswahl werden die Rechner rot markiert und die Bezeichnungen ändern sich dementsprechend in Start und Ende (mit der jeweiligen Rechnernummer).

Mit der "Start"-Taste beginnt die Animation. Das Abfragen der einzelnen Netze, damit die Werte Länge und Vorgänger ermittelt werden können, wird durch einen fortlaufenden blauen Punkt dargestellt. Ist der Punkt bei einem Rechner angekommen, wird dieser aktualisiert. Nachdem alle Netze abgefragt wurden, steht die kürzeste Entfernung im Endrechner unter Länge und der Vorgänger, um auf diesem Weg zum Startrechner zu gelangen. Der kürzeste Weg wird dann ausgehend vom Endrechner rückwärts ermittelt. Diese Rückwärtsermittlung wird mit rot dargestellt.

Falls Pausen zwischen den einzelnen Stationen des Algorithmus gewünscht werden, existiert eine Step by Step - Funktion. Diese Funktion wird unter "Extras/Step by Step" näher beschrieben.

Desweiteren kann die Animationsgeschwindigkeit unter "Extras/Geschwindigkeit ..." eingestellt werden.

Nach Auswahl des Multipath Algorithmus müssen wiederum die Start- und Endrechner durch Mausklick markiert werden. Nach Betätigung der Start-Taste beginnt die Animation.

Es wird die Leitwegtabelle des Rechners eingeblendet, bei dem das Paket gerade ist. Die Ermittlung der Zufallszahl erfolgt im Textfenster. Hier erscheint dann auch der Ausgangsrechner, zu dem das Paket anschließend versandt wird. Sind die Werte berechnet worden, ist die Schliessen-Taste beim Leitwegtabellenfenster aktiv. Durch sie wird das Fenster geschlossen und die Animation wird fortgeführt. Das Versenden des Paketes wird wiederum durch einen fortlaufenden blauen Punkt dargestellt.

Nachdem das Datenpaket den Endrechner erreicht hat, ist der Algorithmus beendet. Um die Leitwegtabellen der einzelnen Rechner in Ruhe zu betrachten, steht der Menüpunkt Extras/Leitwegtabellen anzeigen zur Verfügung. Näheres Vorgehen wird unten beschrieben. Mit der Reset/Fertig-Taste wird wieder der Standardzustand des Netzes hergestellt und es kann wieder ein Algorithmus ausgewählt werden.

Auch hier steht die Step by Step Funktion zur Verfügung.

Wie bei jedem Algorithmus muß noch der Start- und Endrechner ausgewählt werden. Der Beginn der Animation erfolgt durch die Start-Taste.

In jedem Animationsschritt wird die Leitwegtabelle des aktuellen Rechners eingeblendet. Die Werte der Tabelle werden aktualisiert und anschließend ein Ausgangsrechner ermittelt, an den das Paket weiterversandt wird. Der Paketversand wird erst vorgenommen, wenn das Fenster mit der Leitwegtabelle geschlossen wird. Dieser Vorgang wiederholt sich bis das Paket den Endrechner erreicht hat.

Nach Beendigung kann ein neuer Start- und Endrechner ausgewählt werden und der Algorithmus nochmals gestartet werden. Erst nach mehreren Durchläufen kann das selbstlernende System des Backward Learning Algorithmus nachvollzogen werden.

Auch hier besteht die Möglichkeit, die Leitwegtabellen der einzelnen Rechner zu betrachten zur Verfügung. Näheres folgt unter Extras/Leitwegtabellen anschauen.

Wird kein neuer Durchlauf mehr erwünscht, kann mit der Reset/Fertig-Taste der Standardzustand des Netzes wieder hergestellt werden.

Für Pausen zwischen den Animationsschritten steht die Step by Step Funktion zur Verfügung.

Auch für diesen Algorithmus muß ein Start- und ein Endrechner des zu versendenden Paketes angegeben werden. Nachdem der Algorithmus gestartet wurde, muß noch der Paketzähler eingegeben werden. Dies erfolgt in einem extra Fenster, in dem man den Wert eingibt und mit der OK-Taste bestätigt.

Anschließend beginnt die Animation und endet erst, wenn der Paketzähler bei Null ist.

Mit der Reset/Fertig-Taste wird der Standardzustand wieder hergestellt.

Diese Funktion steht nach Auswahl der Algorithmen Shortest Path, Multipath oder Backward Learning zur Verfügung. Nach Aktivierung dieses Moduses hält die Animation nach jedem Schritt an und wird erst weitergeführt, nachdem die Step by Step-Taste betätigt wird.

Um die Funktion wieder auszuschalten muß nochmals der Menüpunkt ausgewählt werden.

Diese Funktion steht bei den Algorithmen Multipath und Backward Learning zur Verfügung. Durch anklicken eines Rechners wird die Leitwegtabelle in einem eigenen Fenster angezeigt. Es können beliebig viele Leitwegtabellen nacheinander angezeigt werden.

Um mit der Animation fortzufahren, muß der Anschaumodus durch nochmaliges Aktivieren des Menüpunktes wieder deaktiviert werden.

Es erscheint ein Dialogfenster in das eine Zahl zwischen 1 und 9 eingegeben werden kann. Der Standardwert beträgt 5. Je kleiner der eingegebene Wert ist, desto kürzer sind die Pausen in der Animation und desto schneller läuft sie ab. Nach Eingabe wird der Wert mit der OK-Taste übernommen.

Durch Aktivierung des entsprechenden Themas wird ein Hilfetext in einem separaten Fenster angezeigt.

Mit diesem Knopf kann nach dem Erstellen eines Netzwerkes die Eingaben gespeichert werden.

Desweiteren wird nach Beendigung eines Algorithmus mit diesem Button der Standardzustand wieder hergestellt.

Die Animationen werden gestartet.

Die Animationen werden gestoppt.

Ist der Step by Step Modus aktiviert kann, mit Hilfe dieses Knopfes die angehaltene Animation fortgesetzt werden.

Markierte Objekte, wie Rechner oder Verbindungen können wieder entfernt werden.

[1] Borowka, Petra – Brücken und Router, Datacom, 1996

[2] Huitema, Christian – Routing im Internet, Prentice Hall, 1996

[3] Jackson, Jerry R.; McClellan, Alan L. – Java by example, Sun Soft Press, 1996

[4] Kerner, Helmut – Rechnernetze nach OSI, Addison-Wessley, 1995

[5] Kowalk/Burke – Rechnernetze, Teubner, 1994