Paper - Lehre und Forschung Thorsten Strufe

Transcrição

Fakultät für Informatik und Automatisierung
Institut für Praktische Informatik
Fachgebiet Telematik
DIPLOMARBEIT ZUR ERLANGUNG DES
AKADEMISCHEN GRADES DIPLOMINFORMATIKER
Thema:
Ezientes Routing in kooperativen
Multimedia-Streaming-Systemen
vorgelegt der Fakultät für Informatik und Automatisierung
der Technischen Universität Ilmenau von
Verfasser:
Thomas Sesselmann
geboren am:
25. Februar 1980
Inv.-Nr.:
2005-03-21/015/IN99/2253
verantwortlicher Hochschullehrer:
Prof. Dr.-Ing. Dietrich Reschke
betreuender wiss. Mitarbeiter:
Dipl.-Inf. Thorsten Strufe
Ort und Abgabe der Diplomarbeit:
Ilmenau, den 21. Juni 2005
1. Kurzfassung
Die Diplomarbeit Ezientes Routing in kooperativen Multimedia-Streaming-Systemen beinhaltet die Entwicklung eines eigenen Routings für ein Multimedia-StreamingSystem.
Nach der Untersuchung existierender Ansätze konnten die Anforderungen für ein geeignetes Routing festgelegt werden. Das Routing klassiziert die ihm bekannten Peers
nach ihrer Lokalität. Diese wird anhand virtueller Positionskoordinaten im Peer-toPeer-Netzwerk berechnet und teilt für jeden Peer die bekannten Peers in Horizonte
ein. Nach der Implementierung des entworfenen Routings soll eine Integration in das
Multimedia-Streaming-System
ekStream
erfolgen und die Funktionalität durch einen
Test gezeigt werden.
2005-03-21/015/IN99/2253
3
1. Kurzfassung
4
2005-03-21/015/IN99/2253
Inhaltsverzeichnis
1. Kurzfassung
Inhaltsverzeichnis
2. Einleitung
3. Grundlagen
3
8
9
11
3.1.
Kooperatives System
3.2.
Routing
3.3.
Multicast
3.4.
Multicastrouting
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.5.
Lokalität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.6.
Peer-to-Peer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.6.1.
Organisationsformen für verteilte Systeme
. . . . . . . . . . . .
18
3.6.2.
Ziele von P2P-Systemen
. . . . . . . . . . . . . . . . . . . . . .
19
3.6.3.
Lookup in P2P-Systemen . . . . . . . . . . . . . . . . . . . . . .
20
3.7.
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Multimedia-Streaming
. . . . . . . . . . . . . . . . . . . . . . . . . . .
4. Verwandte Ansätze
4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
Host-Based Multicast . . . . . .
CoopNet . . . . . . . . . . . . .
SplitStream . . . . . . . . . . .
Layered Peer-to-Peer Streaming
Service Adaptive Multicast . . .
PeerCast . . . . . . . . . . . . .
2005-03-21/015/IN99/2253
21
23
. . . . . . . . . . . . . . . . . . . . . .
23
. . . . . . . . . . . . . . . . . . . . . .
24
. . . . . . . . . . . . . . . . . . . . . .
25
. . . . . . . . . . . . . . . . . . . . . .
26
. . . . . . . . . . . . . . . . . . . . . .
27
. . . . . . . . . . . . . . . . . . . . . .
28
5
Inhaltsverzeichnis
4.7.
Scattercast . . . . . . .
End System Multicast
Zigzag . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
28
. . . . . . . . . . . . . . . . . . . . . . . . . . .
29
. . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.10. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
4.8.
4.9.
5. Anforderungen
35
5.1.
Allgemeine Anforderungen an das System
. . . . . . . . . . . . . . . .
35
5.2.
Funktionale Anforderungen
. . . . . . . . . . . . . . . . . . . . . . . .
36
5.3.
Nicht funktionale Anforderungen
. . . . . . . . . . . . . . . . . . . . .
6. Entwurf
39
6.1.
P2P-Streaming-Modell
. . . . . . . . . . . . . . . . . . . . . . . . . . .
39
6.2.
Lokalität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
6.2.1.
Vivaldi
6.2.2.
Eigene Abwandlung des
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
6.3.
Routing
6.4.
Lokalisierung
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
6.4.1.
Fluten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
6.4.2.
Registrieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
6.4.3.
Eigene Ideen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
7.1.
Architektur von
7.2.
Routing
7.3.
7.4.
Vivaldi -Ansatzes .
41
. . . . . . . . . . . .
7. Implementierung
6
36
ekStream
49
. . . . . . . . . . . . . . . . . . . . . . . . .
49
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
7.2.1.
Schnittstellen
7.2.2.
Statisches Routing
7.2.3.
Einfaches dynamisches Routing
7.2.4.
Lokalitätsbewusstes dynamisches Routing
Lokalisierung
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
52
53
54
. . . . . . . . . . . .
62
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
7.3.1.
Schnittstellen
7.3.2.
Einfache Lokalisierung
Admission Control
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
. . . . . . . . . . . . . . . . . . . . . . .
72
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
7.4.1.
Schnittstellen
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.2.
Statisches Admission Control
. . . . . . . . . . . . . . . . . . .
77
77
2005-03-21/015/IN99/2253
Inhaltsverzeichnis
7.4.3.
Einfaches Admission Control . . . . . . . . . . . . . . . . . . . .
8. Test
78
81
8.1.
Testumgebung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
8.2.
Verlauf des Tests
84
8.3.
Auswertung der Logdateien
8.4.
Ergebnisse des Tests
8.5.
Auswertung und Ausblick
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
84
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
. . . . . . . . . . . . . . . . . . . . . . . . .
9. Schlussbemerkung
91
93
9.1.
Bewertung und Ausblick
. . . . . . . . . . . . . . . . . . . . . . . . . .
93
9.2.
Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
Literaturverzeichnis
Abbildungsverzeichnis
Tabellenverzeichnis
Abkürzungsverzeichnis
Thesen
Eidesstattliche Erklärung
A. Anhang
95
99
101
103
105
107
109
A.1. Übersicht über die Logdateien . . . . . . . . . . . . . . . . . . . . . . .
109
A.2. Datendatei für die Skripte
. . . . . . . . . . . . . . . . . . . . . . . . .
110
A.3. Perlskript zum sortierten Zusammenfügen zweier Logdateien . . . . . .
111
A.4. Perlskript zum Erzeugen der Dierenz zwischen zwei Logdateien . . . .
113
A.5. Perlskript zum sortierten Zusammenfügen aller Logdateien
. . . . . . .
115
A.6. Perlskript zum Teilen der kompletten Logdatei . . . . . . . . . . . . . .
117
A.7. Perlskript zum Berechnen der Abstände vieler Vektoren in einer Datei .
118
A.8. Perlskript zum Berechnen der Abstände zweier Knoten zu jedem Zeitpunkt119
A.9. Ausschnitt aus einer Logdatei
. . . . . . . . . . . . . . . . . . . . . . .
A.10.Vorgehen zum Ausführen eines Tests
A.10.1. Herunterladen des Projekts
2005-03-21/015/IN99/2253
120
. . . . . . . . . . . . . . . . . . .
122
. . . . . . . . . . . . . . . . . . . .
122
7
Inhaltsverzeichnis
A.10.2. Kompilieren der Testdateien . . . . . . . . . . . . . . . . . . . .
122
A.10.3. Kongurieren des Datenstroms
. . . . . . . . . . . . . . . . . .
123
A.10.4. Starten der Testdateien . . . . . . . . . . . . . . . . . . . . . . .
123
A.10.5. Starten des
8
mplayers
. . . . . . . . . . . . . . . . . . . . . . . .
124
2005-03-21/015/IN99/2253
2. Einleitung
Diese Diplomarbeit beschäftigt sich mit dem Thema Multimedia-Streaming. Dabei
werden besonders die Einüsse der Lokalität auf die Ezienz des Routings und des
Streamings betrachtet.
Mit der zunehmenden Verbreitung von Breitband-Internetzugängen haben viele die
Möglichkeit, Multimedia-Daten aus dem Internet zu beziehen. Dabei existieren eine
Menge Anwendungsmöglichkeiten, wie zum Beispiel das Streaming eines groÿen Ereignisses im Internet. Denkbar wäre da ein Konzert oder die Fuÿball-Weltmeisterschaft
2006.
Die Diensteanbieter haben dabei allerdings einen immensen Bandbreitenbedarf. Um
dies zu verdeutlichen, wird hier ein Rechenbeispiel mit einem Nachrichtenstream gezeigt. Der Stream hat eine Bitrate für Video von
Server ist mit
j
100M bit/s
396kbit/s
k
300kbit/s und 96kbit/s für Audio. Der
100M bit/s an das Internet angebunden. So können idealerweise maximal
= 252
Senken bedient werden. Für mehr Nutzer ist eine gröÿere Ausgangs-
kapazität notwendig. Ein weiterer Rechner mit weiteren
100M bit/s
kann das Problem
nur lösen, wenn der Flaschenhals nicht am Gateway des Providers liegt oder er müsste
an einem anderen Standort aufgestellt werden.
Die einfachste Möglichkeit wäre die Verwendung von IP-Multicast, das für die Kommunikationen an viele Empfänger gedacht ist. Allerdings wird IP-Multicast von den
meisten Routern im Internet nicht geroutet (siehe Abschnitt 3.3) und stellt daher keine
Lösung dar.
Einen Ausweg bietet ein Content Distribution Network (CDN). Hierzu werden viele Server global verteilt und über ein Netzwerk verbunden. Der Nutzer wird dann
zu einem freien Server weitergeleitet. Anbieter für solche Systeme sind zum Beispiel
2005-03-21/015/IN99/2253
9
2. Einleitung
Akamai1 , Speedera 2
und
Mirror Image Internet 3 .
Der Nachteil von solchen Systemen
sind die hohen Kosten, da die Kapazitäten bei den Anbietern gemietet werden müssen
(In [Heidenreich (2004) S.40] ist dieser Ansatz näher erläutert.). Somit kommt diese
Lösung nur für groÿe Firmen in Frage.
In dieser Diplomarbeit wird eine weitere Möglichkeit untersucht, dieses Problem zu
lösen. Die Teilnehmer werden in einem Peer-to-Peer-Netzwerk organisiert und arbeiten
kooperativ. Daher bieten alle Teilnehmer, die schon Daten empfangen haben, diese auch
anderen Teilnehmern wieder an. Hierbei existiert das Problem, dass die meisten Nutzer
Asymmetric Digital Subscriber Line
als breitbandigen Anschluss ADSL (
) verwenden
und daher zwar den kompletten Stream empfangen können, aber nur einen Bruchteil
der notwendigen Bandbreite wieder zur Verfügung stellen können.
Als Gesamtziel kann die eziente Nutzung der Ressourcen gesehen werden. Dies wird
durch einen Multisource-Ansatz, bei dem mehrere Teilnehmer einem gemeinsam die
Daten liefern können, erreicht. Ebenso wird versucht, lokalitätserhaltende Topologien
aufzubauen, um die Netzwerkressourcen zu schonen.
Die Arbeit gliedert sich wie folgt: Zuerst werden einige Grundlagen im Kapitel 3 gelegt
und anschlieÿend einige existierende Ansätze (Kapitel 4) vorgestellt. Darauf folgend
werden die Anforderungen (Kapitel 5) für das eigene System festgelegt und danach
die Komponenten Routing und Lokalisierung entworfen (Kapitel 6). Diese Komponenten werden dann im Kapitel 7 in das existierende System
ekStream 4
integriert und in
Kapitel 8 getestet. Abschlieÿend erfolgt eine Bewertung der Arbeit (Kapitel 9).
1 http://www.akamai.com
2 http://www.speedera.com
3 http://www.mirror-image.com
4 http://www.ekstream.org
10
2005-03-21/015/IN99/2253
3. Grundlagen
In diesem Kapitel werden die grundlegenden Begrie, die für das weitere Verständnis
dieser Arbeit notwendig sind, erläutert.
3.1. Kooperatives System
In einem kooperativen System stellt jeder Knoten seine Ressourcen, insbesondere die
von ihm empfangenen Daten, anderen Knoten zur Verfügung. Auf diese Art wird die
Gesamtkapazität des Systems erhöht, da nicht alle Senken ihre Daten von einem Server
beziehen müssen.
3.2. Routing
Im Internet sind Router die tragenden Elemente, da sie einzelne Netze miteinander
verbinden. Sie arbeiten auf Schicht 3 (Netzwerkschicht) des ISO/OSI-Referenzmodells
und wählen den Weg eines Paketes über das Netzwerk. Routen können statisch festgelegt werden, wie dies zum Beispiel bei dem Default-Gateway eines jeden Rechners der
Fall ist. In der Regel legen die Router im Internet ihre Routen allerdings dynamisch
fest bzw. ändern sie dynamisch, um eigenständig auf Änderungen (zum Beispiel Ausfall
eines Routers oder Überlastung einer Verbindung) reagieren zu können.
Die prinzipielle Aufgabe eines Routing-Verfahrens ist, die Entscheidung zu
fällen, zu welchem Ausgang ein eingegangenes Paket weitergeleitet werden
soll. Die primären Ziele sind hierbei ein allgemein hoher Netzdurchsatz und
eine geringe mittlere Paketverzögerung. Generell wird dabei versucht, ein
2005-03-21/015/IN99/2253
11
3. Grundlagen
Datenpaket von der Quelle zum Ziel über den Pfad mit den geringsten Kosten zu leiten. Als Kosten können hierbei z. B. die aktuelle Auslastung oder
Verzögerung einer Verbindung, die Kapazität oder Fehlerrate einer Verbindung, die tatsächlichen Kosten der Übertragung über eine Verbindung etc.
angesetzt werden. Die Entscheidung über das Kostenmodell liegt im Allgemeinen bei einem Netzbetreiber. [Krüger und Reschke (2004) S.156]
3.3. Multicast
Multicast ist eine Gruppenkommunikation, dabei werden die gleichen Daten an mehrere
Empfänger gleichzeitig verschickt. Bei Unicast ist immer nur die Übertragung von
einem Sender zu einem Empfänger möglich.
Üblicherweise wird mit Multicast die Multicast-Funktionalität des IP-Protokolls bezeichnet, womit das eziente Senden von Daten an viele Empfänger zur gleichen Zeit
in IP-Netzwerken möglich wird. Dazu werden spezielle Multicast-Adressen aus dem IPAdressbereich verwendet. Dabei liegt der Vorteil darin, dass die Daten auf jedem Link
jeweils nur einmal geschickt werden müssen und erst bei den angeschlossenen Routern
und Switchen dupliziert werden.
IP-Multicast wird von den meisten Routern im Internet allerdings aus verschiedenen
Gründen nicht geroutet (aus [Weber (2004)] und [Banerjee und Bhattacharjee (2002)]):
•
Es wird eine erweiterte Router-Software benötigt, die für jede Multicast-Adresse
einen extra Eintrag über ihren Zustand verwaltet. Die Komplexität des Routings
erhöht sich dadurch enorm bei gleichzeitigem Verlust der Skalierbarkeit.
•
Ein Angreifer könnte über Multicast viele Empfänger gleichzeitig überuten und
1
so leicht das Netzwerk überlasten (DoS -Attacke).
•
Die Trac-Berechnung, basierend auf der eingehenden oder ausgehenden Bandbreite, müsste angepasst werden.
•
Jeder Gruppe muss dynamisch eine Adresse aus dem globalen IP-MulticastAdressraum zugeordnet werden. Eine skalierbare und zuverlässige Verteilung der
1 Denial
12
of Service
2005-03-21/015/IN99/2253
3.3. Multicast
Adressen ist ein Problem.
•
Die Realisierung einer sicheren Übertragung ist auch deutlich schwieriger, da
die sichere Verteilung eines Sitzungsschlüssels an alle Gruppenmitglieder sehr
komplex ist.
•
Die Umsetzung von höheren Funktionen wie Flusskontrolle, Sicherheit oder Zuverlässigkeit ist deutlich schwieriger als bei Unicast.
•
Die Entwicklung von Multicastanwendungen scheitert meist an der nicht vorhandenen Infrastruktur. Des Weiteren besteht ohne entsprechende Anwendungen
kein Bedarf für die aufwändige Infrastruktur.
Auf Grund dieser Probleme sind viele Ansätze entstanden, einen Multicast auf der
Anwendungsebene zu implementieren. Die Aufgaben der Router, die Pakete zu vervielfältigen und weiterzuleiten, fällt den einzelnen Knoten (Mitgliedern der MulticastGruppe) zu. Diese Knoten werden dabei über ein selbstorganisierendes virtuelles Netz
miteinander verbunden, das sozusagen über das physikalische Netzwerk gelegt wird,
weshalb es Overlay-Netz heiÿt. Weiterleitungen von einem Knoten zu einem Anderen
können nur über Wege in diesem Overlay-Netz gehen. Im Weiteren wird der Multicast
auf der Anwendungsebene (Application-Layer-Multicast) Overlay-Multicast genannt.
In Abbildung 3.1 ist der Unterschied zwischen Unicast, IP-Multicast und OverlayMulticast dargestellt. Dieses Beispiel zeigt einen Server, der einen über Videokamera
aufgenommenen Stream anbietet und fünf andere Rechner, die auf diesen Stream zugreifen wollen. In Abbildung 3.1(a) ist die zugrunde liegende Netzstruktur mit drei
Routern zu sehen (grau). Nun werden die Knoten über ein virtuelles Netz verbunden,
das Overlay-Netz (rot). Die gepunkteten Pfeile (blau) in Abbildung 3.1(b) (Unicastübertragung), 3.1(c) (Übertragung mit IP-Multicast) und 3.1(d) (Übertragung mit
Overlay-Netz) symbolisieren die Datenübertragung. Dabei ist zu sehen, dass der Server
bei der Unicastübertragung unter hoher Last steht, da er alle Anfragen zu bearbeiten hat und jedem einzelnen Client antworten muss. Daher hat auch der Link nahe
der Quelle eine sehr groÿe Auslastung. Deswegen ist zu erkennen, dass IP-Multicast
die eektivste Datenübertragung bezüglich des Ressourcenverbrauchs (Serverlast und
Bandbreite im Netz) ist. Um bewerten zu können, wie gut eine bestimmte Implementierung von Overlay-Multicast ist, werden einige wichtige Performance-Metriken nach
2005-03-21/015/IN99/2253
13
3. Grundlagen
(a) Physikalische
Overlay-Netz
Topologie
und
(c) Übertragung mit IP-Multicast
(b) Übertragung mit Unicast
(d) Übertragung mit Overlay-Multicast
Abbildung 3.1.: Übertragung mittels Unicast, IP-Multicast und Overlay-Multicast
[Banerjee und Bhattacharjee (2002)] eingeführt:
Stress : Stress
wird pro Link oder Router der Topologie deniert und ist die Anzahl
der identischen Pakete, die über den Link oder Knoten gesendet werden. Bei IPMulticast existieren keine redundanten Pakete, daher ist der
Stress
für alle Links
im Netzwerk eins.
Stretch: Stretch ist pro Mitglied deniert und entspricht dem Verhältnis zwischen der
Länge des Pfades zur Quelle über das Overlay-Netzwerk und dem Pfad einer
direkten Unicast-Verbindung. Bei der klassischen Client/Server-Topologie ist der
Stretch
14
eins bei jedem Mitglied und damit optimal, da jeder Client zum Server
2005-03-21/015/IN99/2253
3.4. Multicastrouting
eine eigene direkte Unicast-Verbindung hat.
Kontroll-Overhead:
Jeder Knoten tauscht mit seinem Nachbarn im Overlay-Netzwerk
Aktualisierungsnachrichten aus. Diese Nachrichten werden als Kontroll-Overhead
bezeichnet und sind eine wichtige Metrik für die Skalierbarkeit.
Der
Stress
muss klein sein, damit die Knoten und Links nicht überlastet werden. Aller-
dings sollte auch der
Stretch
niedrig sein, damit die Ende-zu-Ende-Verzögerung gering
gehalten wird. Das Problem ist jedoch, dass dies zwei konkurrierende Ziele sind, sodass
ein guter Mittelweg gefunden werden muss.
Obwohl Overlay-Multicast ebenfalls Probleme besitzt, überwiegen die Vorteile. Er kann
einfach an die jeweilige Anwendung angepasst werden und funktioniert ohne den besonderen Support der Internet-Service-Provider.
3.4. Multicastrouting
Die Aufgabe des Multicastroutings ist es, ein möglichst ezientes Overlay-Netz aufzubauen.
Prinzipiell gibt es keine Einschränkungen für den Aufbau eines solchen Overlay-Netzwerkes. In Abbildung 3.2 sind die drei prinzipiellen Topologieformen veranschaulicht,
entweder ein Baum
2
wie in Abbildung 3.2(a), oder ein Netz. Das Netz kann entweder
kreisfrei (Abbildung 3.2(b)) sein oder Kreise enthalten (Abbildung 3.2(c)).
Während die Router im Internet stabil sind, können die Knoten jederzeit dem Netzwerk
beitreten oder es verlassen. Die groÿe Schwierigkeit besteht darin, dass diese Knoten
die Funktionalität der Router nachbilden sollen und derzeitige Routingalgorithmen im
Internet nicht auf eine solch starke Dynamik ausgelegt sind. Dies macht das Management des Netzwerkes bedeutend schwieriger und muss beim Aufbau des Overlay-Netzes
berücksichtigt werden.
2 In
diesem Fall wird auch vom Multicast-Baum gesprochen.
2005-03-21/015/IN99/2253
15
3. Grundlagen
(a) Multicastbaum
(b) Netz ohne Kreise
(c) Netz mit Kreisen
Abbildung 3.2.: Topologieformen für das Overlay-Netz
3.5. Lokalität
Verschiedene Hosts im Internet sind typischerweise über viele dazwischen liegende Router verbunden. Dabei ist die Verbindung zwischen ihnen im Allgemeinen stabiler, hat
eine kleinere Verzögerung und meist auch mehr Bandbreite, je weniger Komponenten
bzw. Router zwischen ihnen liegen. Daher liegt es nahe, die Lokalität im Peer-to-PeerNetzwerk zu berücksichtigen, um das Netzwerk weniger zu belasten und die Vorteile
der besseren Verbindung zu nutzen. Im Extremfall sind zwei Knoten innerhalb eines
lokalen LANs und könnten so sinnvollerweise die Daten nur einmal über ihren Uplink
beziehen.
Da so das Schicken der Daten über unnötig lange Pfade vermieden wird, kann auch
16
2005-03-21/015/IN99/2253
3.5. Lokalität
(a) Overlay-Netzwerk mit Berücksichtigung der Lokalität
Abbildung 3.3.: Einuss
der
Lokalität
(b) Overlay-Netzwerk ohne Berücksichtigung der Lokalität
auf
die
Netzwerk-Ezienz
des
Overlay-
Netzwerks
die Belastung der darunter liegenden Netzwerkstruktur vermieden werden, wie in Abbildung 3.3 zu sehen ist. Das lokalitätserhaltende Overlay-Netzwerk ist in Abbildung 3.3(a)
und das nicht lokalitätserhaltende Overlay-Netzwerk in Abbildung 3.3(b) veranschaulicht. Dabei sind die Router und die physikalischen Verbindungen grau dargestellt. Die
roten Pfeile stellen die logischen Verbindungen zwischen den Knoten im Overlay-Netz
dar und die blau gepunkteten Pfeile zeigen die Datenübertragung durch das physikalische Netzwerk.
Die Bestimmung der Lokalität kann dabei nicht über exakte geographische Entfernungen geschehen, da diese sehr schwer zu ermitteln und unter Umständen auch nicht
optimal sind. Besser und einfacher ist es, die Lokalität anhand von geeigneten be-
3
stimmbaren Netzwerkparametern, wie zum Beispiel Anzahl der Hops
und gemittelte
Antwortzeiten, zu bestimmen. [Strufe (2003)]
3 Die
Anzahl der Hops entspricht die Anzahl der Router entlang des Pfades zwischen zwei Endsystemen.
2005-03-21/015/IN99/2253
17
3. Grundlagen
3.6. Peer-to-Peer
Unter Peer-to-Peer (P2P) wird die Kommunikation unter Gleichgestellten verstanden.
In einem Peer-to-Peer-Netzwerk gibt es keine eindeutigen Server oder Clients, jeder
Client muss auch als Server auftreten. Aus diesem Grund wird auch nur von Peers oder
Knoten gesprochen. Ein wesentlicher Vorteil von P2P-Netzen ist, dass keine konkrete
oder feste Struktur existiert und somit das Netzwerk sehr ausfallsicher ist. P2P weist
eine n:m Kommunikationsbeziehung im Gegensatz zu Client/Server, wie zum Beispiel
bei einem Webserver, mit 1:n auf.
3.6.1. Organisationsformen für verteilte Systeme
Die Topologien von verteilten Systemen sind:
Zentralisiert:
Hierbei existiert eine zentrale Instanz, an die alle anderen Knoten ih-
re Anfragen senden. Diese Topologie ist keine P2P-Struktur, da nicht jeder die
gleichen Aufgaben übernehmen kann. Damit der zentrale Server diese Anfragen
(Lookup) beantworten kann, müssen die Ressourcen/Dienste bei ihm zuvor angemeldet werden. Somit stellt es sich als erheblich einfacher heraus, alle Ressourcen/Dienste im System bekannt zu machen. Allerdings ist dabei kein absolutes
Wissen möglich, sondern nur ein zeitlich begrenzter Ausschnitt. Diese zentrale
Struktur beinhaltet jedoch wieder die Schwachstelle, dass die Anfragen den Server überlasten können und somit der Server die Leistungsfähigkeit insbesondere
auch die Skalierbarkeit des Gesamtsystems bestimmt. Im schlimmsten Fall fällt
dieser zentrale Server aus und das gesamte restliche Netz ist funktionsunfähig, da
4
alle von ihm abhängig sind. Ein Beispiel für diese Struktur ist Napster .
Dezentralisiert:
Bei einem voll dezentralisierten System müssen alle Funktionen von
den Knoten selbst organisiert werden. Insbesondere können Dienste oder Ressourcen nicht registriert werden, weswegen ein Lookup-Service bedeutend schwieriger
zu realisieren ist. Dafür fallen aber auch alle Nachteile einer zentralen Architektur
weg, wie zum Beispiel beim Ausfall eines zentralen Servers. Ein Vertreter dieser
5
Struktur ist Gnutella .
4 http://www.napster.com
5 http://rfc-gnutella.sourceforge.net
18
2005-03-21/015/IN99/2253
3.6. Peer-to-Peer
Hybrid:
Bei der hybriden Architektur wird versucht, die Vorteile der zentralen und der
dezentralen Architektur zu vereinen. Meist existieren hierbei zwei Knoten-Typen,
die normalen Nodes und die Supernodes. Die meist ressourcenstärkeren Supernodes übernehmen dabei die anspruchsvollen Aufgaben wie Koordination der
Sucher und die Verwaltung der Knoten. Einfache Knoten können so ihre Ressourcen/Dienste bei den Supernodes registrieren, und auch dort nach Ressourcen
nachfragen. Die Supernodes übernehmen in diesem Fall also die Aufgabe des zentralen Servers, werden allerdings je nach Bedarf neu gewählt und koordinieren
6
sich untereinander. Ein Beispiel für diese Architektur ist FastTrack .
3.6.2. Ziele von P2P-Systemen
Die Ziele beim Einsatz von P2P-Systemen werden in [Heidenreich (2004)] genauer beschrieben, wobei hier nur die wichtigsten kurz beschrieben werden sollen.
Kostenteilung/-reduktion:
Da bei der klassischen Client/Server-Struktur, alle Cli-
ents von einem Server bearbeitet werden müssen, kann an dieser Stelle schnell
eine Überlastung auftreten. Die P2P-Architektur versucht die Last oder Kosten,
wie zum Beispiel Speicherplatz, Rechenkapazität oder Bandbreite auf mehrere
Knoten zu verteilen.
Zusammenfassen von Ressourcen:
Es können Ressourcen aller Peers zusammenge-
fasst werden, um eine gemeinsame Aufgabe zu erfüllen. Beispiele hierfür wären
das verteilte Rechnen von SETI@Home
7
8
oder Find-a-Drug .
Verbesserte Skalierbarkeit und Zuverlässigkeit:
Da Dienste nicht nur von einem
Server bereitgestellt werden, sondern auch von anderen Knoten, wird eine erheblich bessere Skalierbarkeit und auch Ausfallsicherheit erreicht.
Hohe Dynamik:
Peer-to-Peer-Systeme sind darauf ausgelegt, dass einzelne Knoten
sehr dynamisch handeln können und sind demnach auch in der Lage mit solchen
Situationen umzugehen.
6 http://www.fasttrack.nu
7 Zum
8 Zum
Finden von Spuren extraterrestrischen Lebens (http://setiathome.ssl.berkley.edu).
Finden von Heilmitteln für verschiedene Krankheiten (http://www.find-a-drug.org).
2005-03-21/015/IN99/2253
19
3. Grundlagen
Ad-hoc-Kommunikation:
Durch das grundsätzliche Fehlen eines zentralen Servers ist
es möglich mit P2P-Systemen einfach eine Ad-hoc-Kommunikation aufzubauen.
3.6.3. Lookup in P2P-Systemen
Da bei P2P-Systemen Ressourcen und Objekte sehr dynamisch beitreten und wegfallen
können, ist die Lokalisation dieser besonders schwierig. Um solche Objekte und Ressourcen aufzuspüren, ist ein so genannter Lookup-Dienst erforderlich, welcher aus zwei
Stufen besteht:
•
Lokalisierungsdienste bilden Bezeichner9 auf Referenzen10 ab
•
Namensdienste bilden Namen11 auf Bezeichner ab
Um nun solche Namens- und Lokalisierungsdienste zu realisieren, existieren grundsätzlich zwei Möglichkeiten für die Suche:
•
Speicherung und Abfrage in einer zentralen Registrierung
•
Durchsuchen des gesamten Systems
12
Das Durchsuchen des gesamten Systems wird zum Beispiel über ein Fluten
des Netz-
werkes mit Anfragen realisiert. Jeder Knoten muss eine an sie gestellte Anfrage lokal
überprüfen und an alle weiteren bekannten Knoten (auÿer dem Anfragenden) weiterleiten. Auf diese Art wird der gesamte Suchraum abgedeckt. Diese Suche führt dann
allerdings zu einem, auf die Anzahl der teilnehmenden Knoten bezogen, exponentiellen
Kommunikationsaufkommen und belastet so bei vielen Anfragen das System stark.
Eine bessere Variante ist eine Registrierung der Ressourcen. Bei der zentralen und
hybriden Architektur ist leicht ein Server zu nden, der für die jeweilige Registrierung
zuständig ist (selbst bei der hybriden Architektur hat ein Knoten nur einen oder eine
9 Ein
Bezeichner dient der eindeutigen Identizierung einer Ressource.
Hilfe einer Referenz kann die durch den Bezeichner festgelegte Ressource im Netzwerk adressiert
bzw. gefunden werden.
11 Ein Name dient meist der Adressierung mehrerer Ressourcen, die aber unterschiedliche Bezeichner
haben können.
12 Wie dies etwa bei Gnutella realisiert wird.
10 Mit
20
2005-03-21/015/IN99/2253
3.7. Multimedia-Streaming
sehr kleine Anzahl von Supernodes). Nun muss allerdings bei der hybriden Architektur
auch eine weitere Suche unter den Supernodes möglich sein. Dabei entsteht dasselbe
Problem wie bei der vollständig dezentralen Architektur, nur mit weniger Knoten und
deshalb weniger Aufwand. [Strufe (2003)]
3.7. Multimedia-Streaming
Der Begri Multimedia ist sehr vielschichtig, in dieser Arbeit soll aber darunter vordergründig die Verknüpfung von Audio und Video verstanden werden.
Als Streaming wird die kontinuierliche Übertragung eines Datenstromes von einer Quelle zur Senke bezeichnet. Zumeist bietet das Format (Kodierung) der übertragenen Daten die Möglichkeit, sie bereits anzuzeigen (nutzen), bevor sie vollständig übertragen
worden sind.
Bei dem Spezialfall Multimedia-Streaming, werden Multimedia-Daten in Form eines
Streams verschickt.
Dabei besitzen die Multimedia-Daten besondere Eigenschaften:
•
Es handelt sich meist um groÿe Datenmengen, die selbst komprimiert eine hohe
Bandbreite benötigen.
•
Es ist notwendig, dass die Daten zeitgenau abgespielt werden, da es sonst zu
Verfälschungen der Informationen kommt.
•
Der Aufbau der Daten ist strukturiert.
•
Es herrscht eine strikte zeitliche Abhängigkeit der Daten.
Daraus ergeben sich spezielle Anforderungen beim Multimedia-Streaming:
•
Die Daten müssen rechtzeitig vor dem Abspielzeitpunkt empfangen werden.
•
Die Daten müssen in einem Format kodiert sein, sodass die Nutzung ohne vollständige Daten ermöglicht wird (nicht streng abhängige Daten).
2005-03-21/015/IN99/2253
21
3. Grundlagen
•
Die Bandbreite muss groÿ genug sein, um mindestens so viele Daten pro Zeitraum
empfangen zu können, wie zum Abspielen pro Zeitraum notwendig ist (Datenrate
der Daten
≤
Bandbreite des Übertragungskanals).
Die Rechtzeitigkeitsanforderung stellt immer noch eine Herausforderung dar, da die
Standardkommunikationsprotokolle wie TCP/IP nicht für Zeitschranken ausgelegt sind.
Bei der Entwicklung dieser Protokolle wurde mehr Wert auf die Zuverlässigkeit gelegt.
Prinzipiell existieren zwei verschiedene Arten von Streaming-Methoden:
Live-Streaming:
Hierbei werden an der Quelle kontinuierlich neue Daten erzeugt. Zum
Beispiel wird per Kamera ein Fuÿballspiel aufgenommen und direkt mit Hilfe eines
Rechners digitalisiert und encodiert. Dies wird dann als Stream übertragen.
Video-on-Demand:
Im Gegensatz zum Live-Streaming sind vom Anfang an alle Da-
ten vorhanden und gespeichert. So ist es möglich zu einem beliebigen Zeitpunkt
(on demand) einen Stream anzufordern und sogar bei einem beliebigen Oset
anzufangen. Theoretisch ist es möglich, während des Streamings mehr Daten anzufordern, als gerade verbraucht werden können, wenn die verfügbare Bandbreite
des Übertragungsmediums gröÿer als die Datenrate des Streams ist.
Für den Nutzer besteht kaum ein Unterschied zwischen Live-Streaming und Videoon-Demand. Jedoch ist der Unterschied, dass bei Live-Streaming die Daten so schnell
wie möglich angezeigt werden sollen, während bei Video-on-Demand viel mehr Daten
im Voraus heruntergeladen bzw. gepuert werden können. Somit kann ein Fehler bei
der Übertragung bei Video-on-Demand eher durch nochmaliges Senden ausgeglichen
werden, als bei Live-Streaming.
22
2005-03-21/015/IN99/2253
Es existieren in der derzeitigen Forschung viele Anwendungen von Multimedia-Streaming in P2P-Netzwerken. In diesem Kapitel sollen nun einige Ansätze mit unterschiedlichen Lösungsmöglichkeiten vorgestellt werden.
Alle Ansätze stellen fest, dass Multicast in der Netzwerkschicht nicht anwendbar ist
(Begründung siehe Abschnitt 3.3) und daher eine Lösung auf der Anwendungsebene
entwickelt werden muss.
Anfangs werden mit
Host-Based Multicast
und
CoopNet
in den Abschnitten 4.1 und
4.2 zwei zentrale Ansätze vorgestellt und darauf folgen die verteilten Ansätze. Die
Abschnitte 4.3 und 4.4 beschreiben die zwei Systeme
to-Peer Streaming, die wie CoopNet
SplitStream
und
den Stream in mehrere Teilströme unterteilen und
dann auf unterschiedlichen Pfaden an den Empfänger senden. Mit
Multicast
Layered Peer-
Service Adaptive
(siehe Abschnitt 4.5) folgt nun ein Ansatz mit verteilten Hash-Tabellen und
Landmark-Vektoren. Bei
PeerCast,
im Abschnitt 4.6 vorgestellt, ist die Kernentwick-
lung eine Zwischenschicht zwischen Anwendung und Netzwerk.
Scattercast
und
End
System Multicast (siehe Abschnitt 4.7 und 4.8) verwenden ein Reverse-Path-Forwarding
Algorithmus, um Verteilungsbäume für die Daten aufzubauen. Zum Schluss wird im
Abschnitt 4.9
Zigzag
vorgestellt, dass auf einem hierarchischen Modell mit Clustern
basiert.
4.1.
Beim
[Roca und El-Sayed (2001)] (HBM) wird eine Gruppen-
kommunikation auf der Anwendungsebene entwickelt. Dabei wird zwischen den
Core-
Members, als Hauptteil der Verteilungsstruktur, und den Non-Core-Members, als einfache Blattknoten in der Topologie, unterschieden. Das Overlay-Netz wird von einem
2005-03-21/015/IN99/2253
23
zentralen
Rendezvous-Point
Members
benachrichtigt. Dieser
berechnet, der dann die
Rendezvous-Point
Core-Members
und die
Non-Core-
kennt alle Mitglieder und ihre Ent-
fernungen zueinander (Für die Denition der Entfernung können unterschiedliche Metriken verwendet werden.). Diese Abstände werden periodisch von den
und den
Non-Core-Members
berechnet und dem
Rendezvous-Point
Core-Members
mitgeteilt.
HBM besitzt, bedingt durch die zentrale Architektur, eine begrenzte Skalierbarkeit und
muss ein groÿes Vertrauen in die Verfügbarkeit des
Rendezvous-Point
haben. Auf der
anderen Seite ist dies eine einfache Lösung mit wenig Last auf der Knotenseite und ohne
Probleme mit Abhängigkeiten, die bei verteilten Algorithmen auftreten. Auÿerdem wird
eine relativ gute Topologie in Abhängigkeit zur Genauigkeit der Entfernungsmessung
erzeugt, die besondere Knoteneigenschaften berücksichtigen kann.
4.2.
Bei
CoopNet
Cooperative Networking (CoopNet ) [Padmanabhan u. a. (2002)] [Padmanabhan u. a.
(2003)] wird das Client-/Server-Modell nicht durch ein P2P-Netzwerk ersetzt, sondern
ergänzt. Nur wenn der Server in Zeiten groÿer Belastung nicht mehr in der Lage ist, die
Anfragen selbst zu bedienen, baut er eine Verteilungsstruktur auf, bei der alle Clients
kooperieren müssen, um ihn zu entlasten. Es wird davon ausgegangen, dass die Clients
dem Netzwerk nur zur Verfügung stehen, solange sie selbst Daten empfangen wollen.
Dies kann eine kurze Zeit von z. B. wenigen Minuten sein.
Die kooperative Verteilungsstruktur besteht aus mehreren Bäumen, die vom Server
verwaltet werden. Der Datenstrom wird mit Hilfe von
Multiple Description Coding
[Goyal (2001)] (MDC) in Teildatenströme aufgeteilt und auf je einem Baum an die
Clients verteilt. Um Redundanz zu erreichen, müssen die inneren Knoten jedes Baumes
unterschiedlich sein, idealerweise wird jeder Knoten nur in einem Baum als innerer
Knoten und sonst immer als Blattknoten verwendet. Als Quelle ist der Server auch die
Wurzel jedes Baumes.
Der Ausfall eines Knotens führt auf diese Art nur zum Verlust eines Teildatenstromes
für seine Kinderknoten. Dadurch nimmt nur vorübergehend die Qualität des Streams
ab und führt nicht zum kompletten Verlust.
Durch die zentrale Struktur ist die Verwaltung des Netzwerkes einfach, da der Server
24
2005-03-21/015/IN99/2253
4.3. SplitStream
alle Ressourcen kennt. Der Knotengrad jedes Knotens wird durch seine verfügbare
ausgehende Bandbreite beschränkt. Bei dem Beitritt eines Knotens meldet sich dieser
einfach beim Server und erhält von ihm eine Liste von Vaterknoten (für jeden Baum
genau einen Knoten). Die Auswahl der Vaterknoten durch den Server kann zufällig
oder deterministisch erfolgen, um die Bäume unterschiedlich aufzubauen.
Es stört wenig, dass der Server ein
Single Point of Failure
bei der Verwaltung des
Netzwerkes darstellt, denn er ist gleichzeitig Quelle der Daten und ohne Quelle ist die
Verteilungsstruktur überüssig. Allerdings wird auf diese Art die Skalierbarkeit des
Netzwerkes eingeschränkt, da durch die alleinige Verwaltung der Verteilungsbäume ein
groÿer Kontroll-Overhead bei dem Server herrscht.
4.3.
SplitStream
SplitStream
[Castro u. a. (2003)] ist ein System zum Verteilen von bandbreitenintensi-
ven Daten mit Hilfe von Multicast auf der Anwendungsebene. Dabei wird versucht, die
Unausgewogenheit von internen Knoten und Blattknoten in einem Multicast-Baum zu
lösen.
Ein baumbasierter Multicast passt leider von Natur aus nicht gut in eine kooperative
Umgebung, denn ein ezienter Multicast-Baum hat eine möglichst geringe Höhe und
damit wenig interne Knoten und viele Blattknoten. Die internen Knoten müssen viel
Arbeit in die Aufteilung und Weiterleitung der Daten stecken und die Blattknoten nehmen nicht aktiv an der Kooperation teil. Deshalb wird bei
geteilt (in
SplitStream
der Datenstrom
Stripes ) und jeder Teil über einen separaten Multicast-Baum geschickt. Nun
wird versucht, jeden Knoten nur in einen Multicast-Baum als inneren Knoten zu verwenden. Dadurch wird die Last gleichmäÿig auf alle Knoten verteilt.
Für Streaming-Daten wird dabei MDC verwendet. Wodurch auch die Robustheit des
Systems gegen einen Knotenausfall verbessert werden kann. Jeder Knoten ist nur einmal
interner Knoten und bei seinem Ausfall fehlt seinen Kindern nur ein kleiner Teil des
Datenstromes. Dadurch ist die Qualität zwar bis zur Reparatur dieses Baumes etwas
geringer, aber der Stream kann weiterhin abgespielt werden.
SplitStream beruht auf dem strukturierten P2P-Overlay-Netzwerk
Pastry
[Rowstron
und Druschel (2001)] und dem darauf aufgebauten Application-Layer-Multicast-System
2005-03-21/015/IN99/2253
25
Scribe
[Castro u. a. (2002)]. Nach eigenen Angaben ist die Konstruktion des Multicast-
Baumes balanciert und die Verzögerung und der
Stress
relativ klein.
Allerdings ist die Verwaltung dieser vielen Multicast-Bäume sehr komplex und aufwändig, da die Pfade unabhängig voneinander sein sollen und jeder Knoten nur einmal
innerer Knoten sein darf. Der Kontroll-Overhead steigt ebenfalls, weil jeder Baum extra
verwaltet werden muss.
4.4.
Layered Peer-to-Peer Streaming
Layered Peer-to-Peer Streaming [Cui und Nahrstedt (2003)] stellt eine P2P-Lösung zum
Verteilen von On-Demand-Multimedia-Daten dar. Es wird davon ausgegangen, dass
Nutzeranfragen asynchron ankommen und die Peers heterogene Netzwerkbandbreiten
besitzen.
Cache-and-Relay (zwischenspeichern und weiterleiten) und
Layer-encodiertes Streaming. Durch den Layer-encodierten Stream wird es den Peers
Die Schlüsseltechniken sind
1
ermöglicht, unterschiedliche Qualitäten eines Streams je nach der eigenen Leistungsfähigkeit (z. B. der eingehenden Bandbreite) zu empfangen.
Jeder Peer speichert den empfangenen Stream in einem lokalen Ringpuer und kann
Peers, die später diese Daten anfordern, als Quelle bedienen. Ein Peer kann verschiedene
Layer von unterschiedlichen Peers parallel empfangen.
Es wird ein
greedy
Ansatz vorgestellt, der immer die maximal mögliche, ausgehende
Bandbreite der Quelle mit der geringsten Anzahl an Layern verwendet. Damit erhält
ein Peer die maximal mögliche Anzahl an Layern. Der Algorithmus wird von jedem
Empfängerknoten selbst berechnet.
Nach eigenen Angaben wird eine eziente Nutzung der Bandbreitenressourcen der
Sender-Peers, eine Skalierbarkeit durch die Bandbreitenersparnis beim Server und eine
optimale Streaming-Qualität von allen Peers erreicht. Allerdings wird bei dem System
nur auf die Verteilung der Daten eingegangen und nicht auf die Verwaltung der Peers.
1 Der
Stream besteht aus {l0 , l1 , l2 , . . . , lL } Layern mit l0 als Basislayer und den restlichen Layern als
Erweiterungslayer. Die Layer bauen aufeinander auf und Layer li kann nur decodiert werden, wenn
alle vorhergehenden Layer (l0 bis li−1 ) ebenfalls vorhanden sind. Mit der Anzahl der Layer kann
die Qualität des Streams beeinusst werden.
26
2005-03-21/015/IN99/2253
4.5. Service Adaptive Multicast
4.5.
Service Adaptive Multicast
Ein weiterer Ansatz für Multimedia-Streaming mit Overlay-Multicast ist
daptive Multicast
Service A-
[Banerjee u. a. (2003)] (SAM).
SAM geht davon aus, dass verschiedene Nutzer die Daten auf unterschiedliche Weise
erhalten wollen. Zum Beispiel benötigt ein Nutzer die Daten verschlüsselt oder den
Audio-Stream in einer anderen Sprache, wobei ein anderer Nutzer einen transcodierten
Stream benötigt.
In SAM existiert eine globale Informationsbasis in Form einer skalierbaren, fehlertoleranten und verwaltungsfreien
verteilten Hash-Table
2
(DHT ). Dabei ndet eine DHT-
Topologie wie bei CAN [Ratnasamy u. a. (2001)] Verwendung. Mit Hilfe von einem
Landmark-Clustering wie in [Ng und Zhang (2001)] wird für jeden Knoten ein Lokalitätsvektor (Landmark-Vektor ) erzeugt. Anhand dieser Vektoren, können die Entfernungen zwischen zwei Knoten bestimmt werden. Da einfaches Landmark-Clustering
jedoch bei nahen Knoten relativ ungenau ist, wird hierarchisches Landmark-Clustering
verwendet. Zusätzlich erfolgt eine Adaptierung des Vektors mit Hilfe von Round Trip
Times (RTT). Bei hierarchischem Landmark-Clustering wird zuerst die grobe Position
mit Hilfe von globalen Landmarks bestimmt und dann durch lokalen Landmarks verfeinert. Mit diesen Lokalitäts-Informationen, die in der globalen DHT gespeichert sind,
wird ein Multicast-Baum erzeugt.
Nach eigenen Angaben besitzt SAM sehr schnelle Algorithmen zum Erstellen und Verändern des Baumes, bei denen zudem meist nur lokale Änderungen notwendig sind. Bei
dem Erzeugen von neuen Pfaden wird möglichst auf existierende nahe Pfade zurückgegrien. Die Mechanismen sind daher sehr skalierbar und können so mit einer sehr
groÿen Anzahl an Service-Anbietern und auch Service-Empfängern umgehen.
Bei SAM sind zwar mehrere Service-Anbieter vorgesehen, aber das kooperative Senden
von Daten von mehreren Sendern zu einem Empfänger wurde nicht realisiert. Jeder
Empfänger kann eigene Anforderungen an die Daten haben (z. B. nur einen AudioStream) und ist so möglicherweise inkompatibel zu anderen Knoten, die wiederum
andere Anforderungen aufweisen (z. B. Audio- und Video-Stream). Auf die daraus
resultierenden Probleme, dass dadurch nur noch eine ungenügende Anzahl von anbie-
2 Distributed
Hash Table
2005-03-21/015/IN99/2253
27
tenden Knoten existiert, wird nicht eingegangen.
4.6.
PeerCast
PeerCast [Deshpande u. a. (2002)] ist eine Live-Streaming Architektur über ein dynamisches P2P-Netzwerk. Ein Peering-Layer ermöglicht einen ezienten Aufbau und Pege
des Overlay-Netzes. Die Overlay-Struktur ist ein (Multicast-)Baum mit der Quelle als
Wurzel.
Das
Peering-Layer
ist hierbei die Kernentwicklung und bendet sich zwischen der
Transport- und Anwendungsschicht. Die Knoten koordinieren sich innerhalb dieses
Peering-Layers
selbst und pegen den Multicast-Baum. Existierende Anwendungen
müssen nicht geändert werden, um mit Hilfe dieses
Peering-Layers
Streaming zu be-
treiben.
Es ist auf einfache Art und Weise möglich mit hunderten autonomen und kurzlebi-
3
gen Knoten eine hochdynamische Gruppe zu bilden. Die nach Ausfall eines Knotens
abgetrennten Teile des Netzes werden wieder in den Baum eingegliedert, ohne dass
zu groÿe Datenverluste entstehen. Da jeder Knoten seine Ressourcen (Rechenleistung,
Speicher, Bandbreite) selbst am besten kennt, entscheidet jeder Knoten für sich wie
viele Clients er bedienen kann.
Ein neuer Knoten wird von der Wurzel des Baumes an immer weiter nach unten geleitet,
bis er einen Server gefunden hat, der noch über freie Kapazitäten verfügt. Für die
Auswahl des Kindknotens können verschiedene Methoden angewendet werden. Neben
der zufälligen oder
Round-Robin
Methode steht noch
4
wobei versucht wird anhand der Position
Smart-Placement
zur Verfügung,
im Netzwerk die Knoten weiterzuleiten.
Das kombinierte Senden von Daten von mehreren Servern an einen Knoten ist hier
nicht möglich und es existiert nur eine geringe Berücksichtigung der Lokalität.
3 im
Minutenbereich
Knoten wird zu dem Kindsknoten weitergeleitet, zu dem er die kürzeste Latenzzeit hat.
4 Der
28
2005-03-21/015/IN99/2253
4.7. Scattercast
4.7.
Scattercast
Scattercast
[Chawathe (2003)] ist ein Ansatz für Live-Streaming von einem auf ei-
ne Anwendung anpassbaren hybriden Overlay-Netzwerks mit
Scattercast Proxys.
Die
Proxys werden über ein Netz von Unicast-Verbindungen untereinander verbunden. Ein
Distance Vector Multicast Routing Protocol (DVMRP) [RFC 1075 (1988)] berechnet
dann einen Source-Routed-Reverse-Shortest-Path-Tree für jede Quelle. Die Clients verbinden sich dann zu einem lokalen Proxy und beziehen von ihm ihre Daten. An dieser
Stelle kann dann lokal auch Netzwerk-Multicast verwendet werden.
4.8.
[Chu u. a. (2002)] haben mit
5
(ESM ) einen Ansatz für eine
Gruppenkommunikation auf der Anwendungsebene entwickelt. Für die Realisierung
von ESM wurde das
Narada -Protokoll entwickelt, das die Endsysteme in einer selbst-
organisierenden Overlay-Struktur auf einer voll dezentralisierten Weise verwaltet.
Alle Gruppenmitglieder werden in einem Overlay-Netz verwaltet und sobald ein Sender
Daten an eine Menge von Empfängern senden will, wird ein Spannbaum aufgebaut.
Der Spannbaum wird mit Hilfe einer eigenen Version von DVMRP [RFC 1075 (1988)]
erzeugt. Durch die ständige Überwachung der Verbindungen wird die Qualität des
Netzes ständig verbessert, da die Verbindungen gegebenenfalls verändert werden um
einen guten Spannbaum aufzubauen.
Narada ist sehr robust gegenüber Ausfällen von Endsystemen und dynamischen Änderungen von Gruppenmitgliedschaften, da jedes Mitglied eine Liste über alle anderen
Mitglieder einer Gruppe verwaltet. Diese Listen müssen allerdings ständig aktuell gehalten werden, was einen erheblichen Verwaltungsaufwand darstellt und die Skalierbarkeit einschränkt, sodass das ESM auf kleine bis mittlere Gruppengröÿen (einige hundert
Mitglieder) beschränkt ist.
5 http://esm.cs.cmu.edu
2005-03-21/015/IN99/2253
29
4.9.
Zigzag
Zigzag
[Tran u. a. (2003b)] [Tran u. a. (2003a)] ist eine P2P-Technologie für das Live-
Streaming der bandbreitenintensiven Multimedia-Daten von einer Quelle zu einer groÿen
Menge an Empfängern im Internet. Dies wird über eine Implementierung eines Multicast auf der Anwendungsebene erreicht.
Jeder Knoten wird als ein Peer angesehen, der seine schon erhaltenen Daten weiteren
Knoten zur Verfügung stellen kann. Dabei wird ein Verteilungsbaum (Multicast-Baum)
aufgebaut, dessen Wurzel der Server
6
ist. Die Ende-zu-Ende-Verzögerung wird groÿ,
wenn viele Empfänger vor einem aktuell betrachteten Knoten liegen, also nahe den
Blättern im Baum. Um diese Verzögerung zu verringern, muss die Baumhöhe klein
sein. Mit kleiner Baumhöhe erhöht sich allerdings der Grad der Knoten. Dabei entsteht
ein Engpass bei diesem Knoten und die Verzögerung steigt wieder. Deswegen sollte der
Knotengrad durch eine Konstante beschränkt werden.
Für die Bewertung der Skalierbarkeit eines solchen Systems ist der Kontroll-Overhead
7
ein wichtiges Kriterium. Er sollte möglichst klein und lokal begrenzt (keine ServerInteraktion) gehalten werden.
Zigzag
administrative Organisation und
administrative Organisation organisiert
verwendet zwei verschiedene Strukturen: die
den darauf aufgebauten
Multicast-Baum.
Die
alle Empfänger in einer Hierarchie von Clustern, welche in der Gröÿe beschränkt
sind. Die Wege der Datenübertragung werden im
Multicast-Baum
festgelegt. In Ab-
bildung 4.1 werden diese zwei Strukturen veranschaulicht.
Eine
administrative Organisation
von Peers ist in der Abbildung 4.1(a) zu sehen. Hier-
bei handelt es sich um eine schichtenbasierte Clusterhierarchie, die nach folgenden
Regeln deniert ist (Nachfolgend gilt:
Knoten,
k>3
H
ist die Anzahl der Layer,
N
die Anzahl der
ist eine Konstante.):
•
Layer-0 beinhaltet alle Peers.
•
Peers in Layer-j (j<H−1) sind eingeteilt in Cluster der Gröÿe
[k, 3k].
6 Da
es nur eine Ursprungsquelle gibt, wird sie hier als Server bezeichnet.
Kontroll-Overhead entspricht dem Kommunikationsaufwand, der für die Aufrechterhaltung des
Netzwerkes (insbesondere des Multicast-Baums) notwendig ist.
7 Der
30
2005-03-21/015/IN99/2253
4.9. Zigzag
(a) Administrative Organisation
(b) Multicast-Baum
Abbildung 4.1.:
− 1)
Zigzag -Struktur [Tran u. a. (2003b)]
•
Layer-(H
•
Ein Peer in einem Cluster auf Layer-j wird zum
hat nur einen Cluster der Gröÿe
[2, 3k].
Head
dieses Clusters gewählt.
Dabei wird er automatisch Mitglied in einem Cluster auf Layer-j + 1 (j<H−1) . Der
Server ist
•
Head
aller Cluster, denen er angehört.
Ein Peer in einem Cluster auf Layer-j wird
dieser Peer jedoch nicht schon
der Server auf Layer-(H
− 1),
Head
dieses Clusters, wobei
dieses Clusters sein darf. Die Ausnahme ist
dort ist er
Die Beschränkung der Cluster nach oben mit
2005-03-21/015/IN99/2253
Associate-Head
Head
3k
und
statt
Associate-Head
2k
gleichzeitig.
dient der Vermeidung des
31
8
erneuten Unterlaufens nach dem Split
Der aus dieser Struktur gewonnene
in zwei Cluster.
Multicast-Baum
ist in Abbildung 4.1(b) zu sehen.
C-Rules (Connectivity Rules) aufgebaut
Peer, der weder ein Head noch ein Associate-Head darstellt.):
Er wird anhand der
•
(ein
Non-Head
ist ein
Ein Peer darf nur auf seinem höchsten Layer ein- und ausgehende Verbindungen
haben.
• Non-Head -Mitglieder
eines Clusters erhalten ihre Daten direkt von ihrem
Asso-
ciate-Head.
•
Associate-Head auf Layer-j , mit Head H , erhält die Daten von einem NonHead auf Layer-(j + 1) (j<H−1) , in dessen Cluster sich H bendet.
Der
Durch die daraus entstehende Zickzack-Struktur (engl. zigzag) hat
Zigzag
seinen Na-
men bekommen. Da ein Knoten auf einem höheren Layer in vielen Clustern
Head
ist,
kann dieser nicht zur Datenverteilung verwendet werden, sonst würden die Peers nahe
dem Server am stärksten ausgelastet sein und der Flaschenhals wäre nah bei der Quelle.
Associate-Head zur Datenverteilung hat den Vorteil der Ausfallsicherheit. Wenn der Head ausfällt, hätte dies keinen Einuss auf die Datenübertragung,
da der Associate-Head noch vorhanden wäre. Fällt dagegen der Associate-Head aus,
könnte der Head schnell einen neuen wählen.
Die Verwendung des
Die denierten Regeln garantieren einen
tengrad von
6k − 3
der Knoten und
k
Multicast-Baum
und einer maximalen Höhe von
mit einem Worst-Case-Kno-
2 logk N + 1 (N
ist die Anzahl
eine Konstante). Dadurch wird auch eine kleine Ende-zu-Ende-
Verzögerung erreicht. Die Eekte der Netzwerkdynamik, wie unvorhersehbares Verhalten der Empfänger, können gut behandelt werden, ohne die Regeln zu verletzen. Der
Kontroll-Overhead ist im Worst-Case
testen und
O(k)[sic!] (O(1))
O(k∗logk (N ))[sic!] (O(log(N ))) für den schlech-
für einen durchschnittlichen Empfänger. Das Beitreten
zum Netzwerk ist schnell und benötigt nur einen kleinen Aufwand, der unabhängig von
N
ist. Insbesondere kann die Fehlerbehandlung lokal erreicht werden, wobei nur eine
konstante Anzahl von existierenden Empfängern beeinusst wird (der Server meist gar
8 Nach
dem Überlauf bei 2k + 1 würde der Cluster in zwei Cluster der Gröÿe k und k + 1 geteilt. Bei
k − 1 würden die Cluster aber wieder zusammengeführt werden müssen.
32
2005-03-21/015/IN99/2253
4.10. Fazit
nicht). Weitere Aspekte wie die Sicherheit und die Heterogenität beim P2P-Streaming
werden in zukünftigen Entwicklungen betrachtet.
4.10. Fazit
Die hier vorgestellten Ansätze versuchen alle auf unterschiedliche Weise das Problem
des Streamings der bandbreitenintensiven Multimedia-Daten an eine groÿe Anzahl an
Empfängern zu lösen. Die groÿe Anzahl an existierenden Ansätzen zeigt die Schwierigkeit, eine allgemeine Lösung zu nden. So sind je nach Zielsetzung unterschiedliche
Ansätze entstanden und da die Entwicklung nicht abgeschlossen ist, werden sicher noch
weitere entstehen.
Alle Systeme erfüllen ihre selbstgestellte Aufgabe gut, allerdings entsprechen ihre Anforderungen nicht den vorliegenden (siehe Kapitel 5) und sind so nur bedingt geeignet.
Ein zentraler Ansatz ist von Natur aus stark in der Skalierbarkeit eingeschränkt und
zudem existiert ein
Single Point of Failure.
Systeme mit MDC- oder Layer-encodiertem Streaming, die mehrere Bäume für jeden
Teilstream verwalten, besitzen eine höhere Robustheit gegen den Ausfall eines Knotens.
Allerdings steigt dabei der Verwaltungsaufwand und die Berechnung von verschiedenen
Bäumen stellt sich als schwierig dar. Andere Systeme, die nur einen Baum als Datenverteilungsstruktur verwenden berücksichtigen auf diese Art nicht, dass mehrere Sender
einen Empfänger versorgen können, um auch Knoten mit ungenügender ausgehender
Bandbreite als Quelle nutzen zu können.
Auÿer
SAM, Scattercast
und
ESM
vernachlässigen die anderen Systeme auÿerdem die
Möglichkeit eines ezienten Routings oder einer ezienten Datenverteilung mit Hilfe
von Lokalitätsbetrachtungen der Knoten. Da auch diese drei Systeme nicht vollständig
unseren Anforderungen entsprechen, ist es notwendig ein eigenes System zu entwickeln.
2005-03-21/015/IN99/2253
33
34
2005-03-21/015/IN99/2253
5. Anforderungen
Es soll ein Multimedia-Streaming-System entwickelt werden, dass eine groÿe Anzahl
von Nutzern ezient bewältigen kann.
Zuerst werden im Abschnitt 5.1 die allgemeinen Anforderungen an das StreamingSystem vorgestellt. Danach werden im Abschnitt 5.2 und Abschnitt 5.3 die speziellen
Anforderungen für die in dieser Arbeit betrachteten Komponenten Routing und Lokalisierung beschrieben.
5.1. Allgemeine Anforderungen an das System
Streaming:
Das System soll einen oder mehrere Multimedia-Streams (Live oder Video-
On-Demand) an seine Teilnehmer verteilen. Durch die strikte zeitliche Abhängigkeit der Multimedia-Daten, müssen die Daten zudem rechtzeitig bei dem Empfänger ankommen (siehe Abschnitt 3.7).
Skalierbarkeit:
Bei der Erhöhung der Teilnehmeranzahl darf sich der Aufwand (Res-
sourcenverbrauch) nicht zu stark vergröÿern.
Geringe Verzögerung:
Die Verzögerung von der Urquelle
1
zu einem Teilnehmer soll-
te nicht zu groÿ sein. Da allerdings keine Interaktion zwischen den Teilnehmer
besteht, besitzt diese Anforderung eine geringere Priorität.
Eziente Netzwerkauslastung:
Die
Stress - und Stretch -Werte (siehe Abschnitt 3.3)
sollten möglichst klein gehalten werden.
1
Die Urquelle stellt der Server dar, der die Daten zuerst erhält. Typischerweise geschieht dies auÿerhalb des Systems (z. B. von Festplatte oder Kamera).
2005-03-21/015/IN99/2253
35
5. Anforderungen
Stabilität:
Da von einem sehr dynamischen Netzwerk ausgegangen wird, muss ein
Knotenausfall schnell und ezient behandelt werden. Es sollte dabei zu möglichst
wenigen weiteren Ausfällen kommen.
Qualität:
2
Die Anzahl der Paketverluste sowie der Jitter
sollten möglichst klein sein.
5.2. Funktionale Anforderungen
Lokalisierung:
Die Lokalisierung hat die Aufgabe nach vorhandenen Diensten wie zum
Beispiel einem Stream zu suchen. Dem anfragenden Scheduling soll dann eine Vorauswahl an Knoten, die den gesuchten Dienst (hier Stream) besitzen, übergeben
werden.
Routing:
Das Routing hat die Aufgabe ein Signalisierungsnetz aufzubauen und die
Steuerinformationen zwischen den einzelnen Knoten zu verschicken (zu routen).
Dabei muss bei unbekannten Empfängern entschieden werden, an welchen Knoten
die Nachricht geschickt werden soll.
5.3. Nicht funktionale Anforderungen
Eziente Suche:
Die Suche nach Diensten (z. B. Streams) und Anbietern im Netz-
werk sollte mit möglichst wenig Kommunikation verbunden sein.
Mehrere Streams:
Es muss berücksichtigt werden, dass mehrere Dienste im Netzwerk
existieren und speziell auch ein Knoten mehrere anbieten kann. Dies beinhaltet,
dass die Dienste einen eindeutigen Bezeichner erhalten müssen.
Ezienz:
Der Aufbau und die Verwaltung des Overlay-Netzes, als Aufgabe des Rou-
tings, sollte mit möglichst wenig Kommunikations- und Berechnungsaufwand verbunden sein. Da die beschränkende Komponente meist das Netzwerk zwischen
den Knoten darstellt, hat der Kommunikationsaufwand eine sehr hohe Bedeutung. Dazu sollten die
Stress -
und
Stretch -Werte
klein gehalten werden (siehe
Abschnitt 3.3).
2
Jitter (Zittern) beschreibt Schwankungen in der Übertragung oder Verarbeitung der Datenpakete.
36
2005-03-21/015/IN99/2253
5.3. Nicht funktionale Anforderungen
Stabilität:
Das Netzwerk muss trotz des dynamischen Knotenverhaltens (insbesondere
spontanes Verlassen des Netzwerkes) für die restlichen Mitglieder stabil bleiben.
Beständigkeit:
Durch häug ausfallende und sehr lose gekoppelte Knoten, kann es
3
schnell zu einer Fragmentierung
des Netzwerkes kommen, die verhindert werden
muss.
Skalierbarkeit:
Da eine möglichst groÿe Menge an Knoten mit Daten versorgt werden
soll, muss das System bezüglich der Knotenanzahl skalierbar sein. Daher darf
die Kommunikation nicht übermäÿig mit der Knotenanzahl im Netzwerk steigen.
Ideal wäre es, wenn die Knotenanzahl keinen Einuss auf die Verwaltung und das
Verhalten des Netzwerkes hätte, damit das Netzwerk beliebig groÿ sein kann.
Heterogenität:
Es muss berücksichtigt werden, dass die Knoten sehr heterogen bezüg-
lich vieler Eigenschaften, wie Rechenkapazität, Bandbreite und Betriebszeit sind.
Auch kann die ausgehende Bandbreite ungleich der eingehenden Bandbreite, also
asymmetrisch, sein.
Portabilität:
Damit das System universell eingesetzt werden kann, sollte es auf vielen
unterschiedlichen Architekturen oder Betriebssystemen einsetzbar bzw. lauähig
sein.
Lokalität:
Im Abschnitt 3.5 wurde erläutert, dass die Lokalität erheblichen Einuss
auf die Ezienz, bezüglich Netzwerkauslastung und damit auch Skalierbarkeit,
hat. Daher muss das System diese Lokalität berücksichtigen und zum Beispiel bei
der Suche nach Quellen eines Services möglichst nahe Knoten nden.
Vollständige Antwortmengen:
Beim Suchen bzw. Lokalisieren von Diensten (z. B.
Streams) im System sollte die Antwortmenge möglichst vollständig (bezüglich
der jeweiligen Lokalität) sein.
Erweiterbarkeit und Wartbarkeit:
Damit das System nach dieser Diplomarbeit wei-
terentwickelt werden kann und insbesondere auch andere Algorithmen oder Strategien eingesetzt werden können, sollte auf die Erweiterbarkeit und Wartbarkeit
geachtet werden.
3 Das
Netzwerk zerfällt in mehrere Teilnetze.
2005-03-21/015/IN99/2253
37
5. Anforderungen
38
2005-03-21/015/IN99/2253
6. Entwurf
Die Anforderungen aus Kapitel 5 werden nun verwendet, um ein Streaming-Modell zu
entwickeln. Danach wird die genaue Lokalitätsbestimmung im Abschnitt 6.2 vorgestellt,
welche vom Routing im Abschnitt 6.3 verwendet wird. In Abschnitt 6.4 werden einige
Möglichkeiten für die Lokalisierung von Ressourcen vorgestellt.
6.1. P2P-Streaming-Modell
Das Modell beinhaltet eine Menge
P
(Formel 6.1), die aus
N (N ∈ N)
Peers besteht.
Diese Peers agieren auf eine dezentrale lokalitätsbewusste kooperative Weise untereinander.
n
o
P = Pi | 1 ≤ i ≤ N
Dabei ist die Anzahl
N
(6.1)
der Peers dynamisch, da jeder Peer das Netzwerk zu jeder Zeit
verlassen oder ihm beitreten kann.
Alle Peers sind gleichberechtigt, besitzen die gleichen Rechte und Pichten und können
Dienste anfordern und anbieten. Sobald ein Peer
Pi
einen Dienst
a
er sich in der Menge Pr (Formel 6.2) und sobald er den Dienst
Pas (Formel 6.3). Die Mengen Pas und Par sind Teilmengen von
n
= Pra ∈ P | Pra
n
Pas = Psa ∈ P | Psa
Par
Wenn ein Peer einen Dienst
fordert Dienst
bietet Dienst
a
a
an
anfordert, bendet
a anbietet, in der Menge
P (Pas ⊆ P, Par ⊆ P).
o
o
an
a
(6.2)
(6.3)
a nutzt, kann er diesen wieder anderen Peers zur Verfügung
stellen. Insbesondere beim Empfangen eines Streams, als Form eines Dienstes, kann
2005-03-21/015/IN99/2253
39
6. Entwurf
der Peer die empfangenen Daten an andere Peers weiterleiten. Da jeder Peer auch noch
einen individuellen Puer besitzt, ist es sogar möglich, dass er eine gewisse Zeitspanne
an Daten anbietet. Die Gesamtkapazität wird ständig erhöht, da mit den Peers, die
den Dienst nutzen, auch die Anzahl der Peers steigt, die den Dienst anbieten.
Es ist vorgesehen, dass ein Peer
Pra
den Dienst
a
von mehreren Peers
Psa
nutzen kann.
Dies ist besonders bei Diensten in Form von Streams sinnvoll, da so die verwendete
Bandbreite auf mehrere Peers
Psa
aufgeteilt wird und auch bei Ausfall eines Peers
Psa
noch ein Teil der Daten empfangen werden kann. Die Berechnung der Datenanteile für
jeden Peer
Psa
kann beim Peer
Pra
erfolgen, da er seine Dienstanbieter (Quellen) selbst
wählt.
Die Auswahl der Quellen soll unter anderem anhand von Lokalitätskriterien erfolgen,
da nahe Knoten meist eine ezientere Übertragung (geringere Latenz, geringerer Jitter,
höhere Bandbreite) ermöglichen (siehe Abschnitt 3.5). Auf die Auswahl der Lokalitätskriterien wird im folgenden Abschnitt 6.2 eingegangen.
Jeder anbietende Peer
Psa
muss, mit Ausnahme der Urquelle, gleichzeitig die Daten
a
als anfordernder Peer Pr erhalten. Die Urquelle erhält die Daten von auÿerhalb des
Systems, beispielsweise von der Festplatte oder einer Videokamera (je nachdem, ob
Live-Streaming oder Video-on-Demand).
6.2. Lokalität
1
Als einfachstes Kriterium für die relativen Entfernungen (Lokalität) von Knoten in
einem Netzwerk, wie dem Internet, kann die Latenz verwendet werden.
Die Latenz
ergibt sich dabei aus der halben Umlaufzeit (RTT) eines Paketes.
Als erweitertes Kriterium könnte die Anzahl der physikalischen Hops zwischen den
Knoten verwendet werden. Dies ist allerdings schwieriger zu messen, sollte aber in
späteren Forschungsarbeiten weiter untersucht werden.
Da die Grundidee für die Lokalitätsberechnung, im Rahmen dieser Diplomarbeit, von
Vivaldi
[Cox u. a. (2003)] stammt, erfolgt zunächst eine kurze Zusammenfassung dieses
Ansatzes, bevor die eigene Variation erläutert wird.
1 Da absolute geographische Entfernungen nicht geeignet sind, werden relative Entfernungen bezüglich
Netzwerkparametern verwendet.
40
2005-03-21/015/IN99/2253
6.2. Lokalität
6.2.1.
Vivaldi
Vivaldi
[Cox u. a. (2003)] ist ein verteilter Algorithmus zur Berechnung von syntheti-
schen Koordinaten für Internetrechner. Dabei soll die euklidische Distanz der Koordinaten zweier Rechner der Latenz zwischen ihnen entsprechen.
Die Entwickler von
Vivaldi
wurden dabei von
Zhang (2001)] (GNP) angeregt.
Global Network Positioning
[Ng und
GNP demonstriert die Möglichkeit der Berechnung von
synthetischen Koordinaten, um Latenzen im Internet vorauszusagen. Dabei werden die
eigenen Koordinaten anhand von Latenzmessungen zu einer kleinen Anzahl (5 - 20)
von festen Punkten, so genannten
der
Landmarks
Bei
Vivaldi
Landmarks (engl. Grenzsteine), berechnet. Die Wahl
bestimmt dabei erheblich die Genauigkeit der Latenzvorhersagen.
werden keine solchen
voraussetzt, eignet sich
Vivaldi
Landmarks
benötigt. Da es keine feste Infrastruktur
auch für P2P-Netzwerke. Jedes Mal wenn ein Knoten
mit einem anderen kommuniziert, wird die Latenz zu diesem Knoten gemessen und es
werden die Koordinaten angepasst, um den Fehler zu minimieren. Die Anpassung der
Koordinaten erfolgt mit Hilfe einer Lernrate
kleiner wird und minimal
δ , die am Anfang 1.0 beträgt, schrittweise
0.05 ist. Dadurch werden anfangs gute Koordinaten schneller
erreicht und später ein Hin- und Herschwingen vermieden.
Vivaldi
Für
muss die Anwendung bei jedem Kontakt zu einem anderen Knoten La-
tenzinformationen ermitteln und
Vivaldi
übergeben. Auf diese Art ist es nicht nötig,
Vivaldi selbst Messpakete verschickt. Allerdings muss die Anwendung Platz für
Vivaldi -Koordinaten in ihren Paketen, die an andere Knoten geschickt werden,
dass
die
reservieren.
Als sehr vorteilhaft erweist sich, dass die Latenz zu einem Knoten auf Grund der
vorhandenen Koordinaten ohne explizite Messung berechnet werden kann. Sogar die
Latenz zweier anderer Knoten (nicht der eigene) untereinander kann bestimmt werden,
sofern dies notwendig sein sollte.
2005-03-21/015/IN99/2253
41
6. Entwurf
Vivaldi -Ansatzes
6.2.2. Eigene Abwandlung des
Bei
Vivaldi
wurde der Algorithmus nur anhand von Pseudocode erklärt. Hier wird
2
die eigene Abwandlung jedoch mit Hilfe einiger Formeln
erläutert.
Die verwendeten
Parameter sind zum besseren Verständnis in Tabelle 6.1 zusammengefasst.
D
→
−
x
Anzahl der Dimensionen der Lokalitätsvektoren
eigener Lokalitätsvektor des lokalen Knotens
−
→
y
Lokalitätsvektor eines anderen Knotens
RT Tcal
berechnete RTT aus zwei Lokalitätsvektoren
gekürzte Schreibweise für
RT Tmeas
−
→
x
und
(dies ist die ab-
−
→
RT Tcal (→
x ,−
y ))
gemessene RTT zwischen zwei Knoten (bezieht sich auf dieselben Knoten
wie
RT Tcal )
ε
Fehler zwischen berechneter und gemessener RTT
δ
→
−
x0
Lernrate
−
→
x 0δ=1
−
→
y
eigener Lokalitätsvektor nach dem Lernvorgang
eigener Lokalitätsvektor für
δ = 1.0
(dabei würde
ε
vollständig beseitigt
werden)
Tabelle 6.1.: Verwendete Variablen für die Lokalitätsberechnung
Jeder Knoten besitzt seinen eigenen
D-dimensionalen
Lokalitätsvektor, den er anfangs
zufällig wählt.
−
→
x
Der Abstand zweier Lokalitätsvektoren (
und
−
→
y)
soll der RTT entsprechen (siehe
Formel 6.4). Auf diese Weise kann relativ einfach die erwartete RTT (RT Tcal ) ohne
Messung bestimmt werden.
−
→
x = (x1 , x2 , . . . , xD )
→
−
y = (y1 , y2 , . . . , yD )
v
u D
uX
→
−
→
−
→
−
→
−
RT Tcal ( x , y ) = | x − y | = t (xi − yi )2
(6.4)
i=1
2 Die
Unterschiede zu
zu nden.
42
Vivaldi
sind nur bei der Berechnung von δ und den Berechnungszeitpunkten
2005-03-21/015/IN99/2253
6.2. Lokalität
Da die Lokalitätsvektoren anfangs zufällig gewählt werden, müssen sie an die richtige
RTT angepasst werden. Hierzu werden in bestimmten Abständen
τ
RTT-Messungen
3
(RT Tmeas ) zu einigen zufällig ausgewählten bekannten Knoten vorgenommen und der
jeweilige Fehler
ε
nach der Formel 6.5 berechnet.
ε = RT Tcal − RT Tmeas
(6.5)
Jeder Knoten ist dabei nur für seinen eigenen Lokalitätsvektor zuständig und nimmt
die Richtigkeit des anderen Lokalitätsvektors an. In Abbildung 6.1 ist solch ein Lernvorgang zu sehen, wobei der anfängliche lokale Lokalitätsvektor
−
→
x
und der andere
−
→
Lokalitätsvektor y entspricht. Als Erstes wird der Fehler ε, als Dierenz der berechneten und der gemessenen RTT (siehe Formel 6.5), berechnet. Um den Fehler
zu beseitigen, müsste der eigene Lokalitätsvektor
werden. Diese Stelle ist mit
6
−
→
x 0δ=1
−
→
x
um
ε
in Richtung
−
→
y
ε komplett
verschoben
gekennzeichnet.
*A
→
A r−
y
A
*
RT Tcal
→0
−
RT Tmeas
x δ=1
r
*A
→0
−
x
ε
r
A−
A
→
*
Ax
r
AA
ε·δ
-
Abbildung 6.1.: Berechnung des neuen Lokalitätsvektors.
Dabei besitzen allerdings temporär fehlerhafte Messungen einen genauso groÿen Einuss wie korrekte Messungen. Da sich ebenso die Lokalitätsvektoren der anderen Knoten mit groÿer Intensität verändern würden, entstehen so leicht starke Schwingungen.
3 Bei
Vivaldi
wurden die Messungen und damit auch die Mess- und Berechnungszeitpunkte in die
Anwendung verlagert.
2005-03-21/015/IN99/2253
43
6. Entwurf
Um dies zu verhindern, wird mit Hilfe einer Lernrate
δ
nur ein bestimmter Teil des
→0
−
ausgeglichen. Die Berechnung des neuen eigenen Lokalitätsvektors x erfolgt
→
−
→
y −−
x
→
−
der Verschiebungsrichtung des Vektors x .
nach der Formel 6.6. Dabei entspricht
RT Tcal
Fehlers
ε
→
−
→
y −−
x
−
→
→
−
0
·ε·δ
x = x + −
→
→
−
|y − x|
→
−
→
y −−
x
→
=−
x +
·ε·δ
RT Tcal
(6.6)
Die Entfernung nach dem Lernvorgang kann mit Formel 6.7 berechnet werden.
→
→
→
→
x0−−
y | = |−
x −−
y|+ε·δ
|−
(6.7)
= RT Tcal + ε · δ
Nun ist es möglich das Lernen, mit Hilfe der Parameter
δ
und
τ,
dynamisch zu beein-
ussen. Da anfangs die Lokalitätsvektoren noch zufällig sind, sollte
sein, damit der Fehler
ε
τ
klein und
schnell klein wird. Später wird der Parameter
erhöht und der Parameter
δ
τ
δ
groÿ
schrittweise
schrittweise verringert, damit ein Hin- und Herschwingen
vermieden wird. Auch sollten die Lokalitätsvektoren nach einiger Zeit relativ stabile
Werte erreicht haben und sich nur noch gering verändern, sodass sie nicht mehr so oft
aktualisiert werden müssen (τ kann groÿ sein).
4
Nun sollte aber nicht nur von der statischen
Variante ausgegangen werden, auch muss
die dynamische Veränderung der Abstände (RTT) zwischen den Knoten berücksichtigt
werden. Als Beispiel seien hier Funknetze genannt, bei denen sich potenziell alle Teilnehmer hin- und herbewegen können. Daher wird die Lernrate
verringert (wie bei
ε
δ
nicht ständig schrittweise
Vivaldi ), sondern anhand des Fehlers ε dynamisch angepasst. Falls
klein ist, das heiÿt der eigene Lokalitätsvektor einen guten Wert besitzt, wird die
Lernrate
δ
reduziert. Wenn allerdings
ε groÿ ist, wird die Lernrate δ
wieder erhöht, um
einen guten Wert für den eigenen Lokalitätsvektor zu erreichen.
Die Bewegung eines Knotens sollte nur zu einer Anpassung des Lokalitätsvektors von
diesem Knoten führen. Das Problem ist ohne globale Sicht festzustellen, welcher Knoten
4
44
Wenn sich die Latenzen der Knoten untereinander nicht verändern, kann die Situation als statische
Variante beschrieben werden.
2005-03-21/015/IN99/2253
6.3. Routing
sich bewegt hat, wenn nur Entfernungen bekannt sind. Dies wird durch die Betrachtung
des Fehlers
ε erreicht. Aus der Sicht des sich bewegenden Knotens haben sich alle seine
5
Entfernungen zu anderen Knoten verändert . Für einen sich nicht bewegenden Knoten
ist nur die Entfernung zu dem sich bewegenden Knoten anders. Daher sind beim sich
bewegenden Knoten alle Fehler
ε
bei den anderen Knoten fast alle
groÿ, sodass er seine Lernrate
ε
klein sind und so
δ
δ
erhöht. Wohingegen
klein bleibt.
6.3. Routing
Das Routing hat die Aufgabe zu entscheiden, an welches Ziel ein Paket versendet wird.
Diese Entscheidung stellt sich als besonders wichtig dar, wenn keine direkte Verbindung
zu dem Empfänger existiert oder bekannt ist. Dabei trägt das Routing ebenso die
Verantwortung über die Nachbarschaftswahl.
Das Routing soll neue Knoten kennen lernen und nicht mehr erreichbare Knoten vergessen. Eine gröÿere Knotenmenge verringert die Gefahr einer Partitionierung des Netzwerkes, wenn einige Knoten ausfallen. Allerdings ist die Verwaltung und vor allem die
Aktualisierung einer sehr groÿen Knotenmenge sehr aufwändig und birgt einen groÿen
Nachrichtenoverhead in sich. Da auch eine gröÿere Anzahl an bekannten Knoten die
Routingentscheidung unter Umständen vereinfacht, sollte die Gröÿe der Menge an bekannten Knoten sorgsam gewählt werden.
Das Kennenlernen der neuen Knoten gestaltet sich durch die starke Verbreitung von
Firewalls mit
Network Address Translator
[RFC 2663 (1999)] (NAT) schwierig, da die
Netzwerkadresse auf beiden Seiten der Firewall unterschiedlich sein kann. Dabei ist das
Lernen eines Knotens nur mit Hilfe eines dritten Knotens, der beide anderen Knoten
kennt, möglich.
Da beim Routing die Lokalität berücksichtigt werden soll, muss das Routing die Lokalitätsberechnung, die unter Abschnitt 6.2.2 vorgestellt wurde, vornehmen. Allerdings
sollte das Routing im System austauschbar sein. Aus diesem Grund können die Lokalitätsvektoren nicht in jeder Nachricht mitversendet werden (wie bei
Vivaldi ), sondern
es müssen separate Anfragen und Nachrichten versendet werden können.
5 Diese
Veränderung entspricht dem Fehler ε.
2005-03-21/015/IN99/2253
45
6. Entwurf
Die Knoten mit ihren Entfernungen werden anhand von Schwellwerten den Horizonten
zugeordnet. Mit Hilfe dieser Horizonte kann die Lokalisierung (Abschnitt 6.4) eine Vorauswahl für das Scheduling treen. Ebenso kann das Routing bei unbekannten Adressen
mittels der Lokalität entscheiden, zu welchen Knoten das Paket weitergeleitet werden
soll.
Für das Weiterleiten von Paketen stellt sich die Verwendung eines
Time To Live (TTL)-
Feldes als sinnvoll dar. Bei jedem Knoten wird diese TTL um Eins verringert. Wenn
sie Null erreicht, wird das Paket nicht mehr weitergeleitet. Dadurch wird bei Kreisbildungen im Netzwerk verhindert, dass ein Paket unendlich oft weitergeleitet wird und
sinnlos Ressourcen verbraucht werden.
6.4. Lokalisierung
Die Lokalisierung soll Anbieter mit ihren Diensten sowie Replikate im Netzwerk nden
(siehe Grundlagenkapitel Abschnitt 3.6.3).
Da hier ein Streamingsystem betrachtet wird, erscheint die Lokalisierung von Streams
als besonders wichtig. Dabei ist es entscheidend zu wissen, welche Streams existieren
und wer welchen Teil des Streams anbieten kann, um dem Scheduling eine Vorauswahl
an Knoten anbieten zu können.
Diese Informationen müssen hinterlegt und von der Lokalisierung regelmäÿig aktualisiert werden, da sich diese Daten sehr schnell ändern können.
Nach [Strufe (2003)] existieren prinzipiell zwei Möglichkeiten, um nach Diensten in
einem P2P-Netzwerk zu nden: durchsuchen des gesamten des Netzwerkes (z. B. durch
Fluten ) und Registrieren
der Informationen an einer Stelle im Netzwerk.
6.4.1. Fluten
Fluten ist die einfachste Möglichkeit, in einem dynamischen Netzwerk ohne zentrale
6
Stelle zu suchen. In der Version 0.4 von Gnutella
wurde diese einfache Möglichkeit des
Suchens implementiert. Jeder Knoten durchsucht seine eigenen Daten nach der Anfrage
6 http://rfc-gnutella.sourceforge.net/
46
2005-03-21/015/IN99/2253
6.4. Lokalisierung
und leitet sie auch an alle ihm bekannten Knoten, auÿer dem Senderknoten von dem
er die Anfrage erhalten hat, weiter.
Die Vorteile dieser Methode sind die Einfachheit der Implementierung und die Möglichkeit eine unscharfe Suche realisieren zu können, da die Suche lokal vorgenommen
wird. Der Nachteil ist, dass Fluten durch ein exponentiell steigendes Kommunikationsaufkommen [Ritter (2001)] nicht skaliert und somit für groÿe Netze nicht angewendet
werden kann. Ebenso dauert ein Suchvorgang im Netzwerk relativ lange.
6.4.2. Registrieren
Die Registrierung aller Ressourcen stellt eine weitere Möglichkeit dar. Allerdings ist
es nicht praktikabel für sehr groÿe und dynamische P2P-Netze, eine zentrale Stelle zu
wählen, um die Ressourcen zu registrieren [Strufe (2003)].
Eine andere Möglichkeit bietet die Verteilung der Informationen mit Hilfe von verteilten
Hash-Tabellen (DHT) wie in [Ratnasamy u. a. (2001)] beschrieben. Da sich aber die
Informationen über den Stream im vorliegenden Zeitraum sehr dynamisch ändern kann,
7
ist ein ständiges Umregistrieren
sehr aufwändig und daher nicht einsetzbar.
6.4.3. Eigene Ideen
Da beide Möglichkeiten, insbesondere das
Fluten,
Nachteile besitzen, entstanden eine
ganze Reihe von Abwandlungen und Kombinationen, die in [Strufe (2003)] nachgelesen
werden können.
Zum einen kann über einen TTL-Wert die Tiefe der Suche beim Fluten beschränkt
werden, um die Netzlast auf Kosten der Treerwahrscheinlichkeit zu verringern. Die
Breite der Suche kann auch reduziert werden, indem ein Knoten die Anfrage nicht an
alle bekannten Knoten weiterleitet, sondern nur an einen bestimmten Teil.
Eine einfache aber sehr eziente Methode für diese selektive Weiterleitung ist die Verwendung von
Random Walker
[Lv u. a. (2002)]. Der suchende Knoten sendet hierbei die
Anfrage an eine begrenzte Anzahl (maximal 64) anderer Knoten. Alle weiteren Knoten
7 Zudem
ergeben sich bei kleinen Änderungen der Information meist ganz andere Hash-Werte.
2005-03-21/015/IN99/2253
47
6. Entwurf
senden eine empfangene Anfrage nur an einen Knoten weiter. Bei nochmaligem Empfangen derselben Anfrage wird sie diesmal an einen anderen Knoten weitergeleitet. Auf
diese Art werden die Nachrichten nicht vervielfältigt, sodass die Tiefe der Suche sehr
groÿ sein kann.
Da die eigene Lokalisierung die Lokalität berücksichtigen sollte, bietet sich eine Abwandlung von
Random Walker
an. Dabei wird die Suchanfrage an einige lokale Knoten
weitergeleitet und an sehr wenige weiter entfernte Knoten. Auf diese Art sollte sich
die Suchanfrage schnell in lokalen Bereichen verbreiten, aber nicht zu sehr über weite Entfernungen. Unter Umständen ist es sinnvoll, den Anfragen einen abgewandelten
TTL-Wert mitzugeben, bei dem die Entfernung berücksichtigt wird. So kann sich die
Anfrage oft lokal, aber über weite Entfernungen nur begrenzt, verbreiten.
Eine weitere Möglichkeit ist, die Lokalität direkt zu berücksichtigen und lokale Cluster
Supernodes gewählt,
bei denen alle anderen Knoten Daten registrieren und abfragen können. Die Supernodes
zu bilden. In jedem Cluster wird dann eine begrenzte Anzahl an
müssen dann untereinander die Informationen austauschen.
48
2005-03-21/015/IN99/2253
7. Implementierung
Die Implementierung des Routings und der Lokalisierung erfolgt im kooperativen Streamingsystem
ekStream 1 ,
welches aufbauend auf dem
IlmStream -Projekt
([Kärst (2004)]
[Strufe (2004)]) entwickelt wird. Im Verlauf dieser Diplomarbeit entstand der erste
2
funktionsfähige Prototyp .
In diesem Kapitel wird nun zuerst die prinzipielle Architektur von
ekStream
erläutert
(Abschnitt 7.1) und dann folgen die eigenen Implementierungen des Routings (Abschnitt 7.2) und der Lokalisierung (Abschnitt 7.3).
7.1. Architektur von ekStream
In der Abbildung 7.1 wird die aktuelle Architektur von
ekStream
Im Rahmen dieser Diplomarbeit wurden die Komponenten
Admission Control
veranschaulicht.
Routing, Localisation
und
implementiert. Die hierfür wichtigen Teile der Architektur werden
im folgenden erläutert.
Routing kommuniziert
Nodes genannt werden.
Das
mit Hilfe des
Transport Layers
mit anderen Knoten, die
Node Roster verwaltet. Alle anderen KomRouting (Transport Layer und Network Measurement ) kennen
Das Wissen über andere Knoten wird im
ponenten auÿer dem
nur
Nodes
und müssen sich nicht um die Art und Weise der Nachrichtenübertragung
kümmern. Sie verschicken untereinander (intern und auch an andere Knoten)
Message -
Objekte.
1 http://www.ekstream.org
2
Die Mitarbeit am ekStream -Projekt umfasste im Rahmen dieser Diplomarbeit die SubversionRevisionen 236 bis 760. Somit beziehen sich sämtliche Code-Ausschnitte von ekStream auf die
Revision 760.
2005-03-21/015/IN99/2253
49
7. Implementierung
Source Nodes
Sink Nodes
syncObject
Receiver
Forwarder
Buffer
getLinks
Link Control
Scheduler
getSessionInfo
schedule
Admission
Control
select
acceptNewLink
listNodes
Localisation
updateNode
getAcceptingState
getNode
Message Center
getNode
Node Roster
addNode
updateNode
Routing
listNodes
deleteNode
sendBag
calculateRTT
Network Measurement
calculateBandwidth
Transport Layer
receiveBag
Peer Nodes
Communication using IP packets
RTT and Bandwidth Measurements
Multimedia data
Communication between
components
Abbildung 7.1.:
ekStream -Architektur
Routing verpackt dann diese Message -Objekte und schickt sie mit Hilfe des Transport Layers über das Netzwerk. Dabei ist das Transport Layer nur für den direkten
Das
Versand und Empfang von Netzwerkpaketen zuständig.
Nachrichten von anderen Knoten (oder auch von Komponenten innerhalb) werden über
das
Message Center
Die
Localisation
an die jeweilige Empfängerkomponente weitergereicht.
kann ebenfalls mittels
Messages
mit der
Localisation
anderer Kno-
ten kommunizieren und so Informationen austauschen. Die Informationen vom lokalen
Buer (und vom Admission Control ). Informationen über
andere Knoten werden im Node Roster verwaltet.
Knoten erhält sie direkt vom
50
2005-03-21/015/IN99/2253
7.2. Routing
Localisation
nete Nodes.
Die
Nachdem das
übergibt dem
Link Control
Scheduler 3 nach einer von ihm gestellten Anfrage geeig-
von einem anderen Knoten eine Anfrage nach Streaming-
daten erhalten hat, fragt es das
Admission Control, ob diese Anfrage bearbeitet werden
darf.
7.2. Routing
Alle Klassen des Routings sind in dem Paket
org.ekstream.routing
zusammenge-
fasst.
22 package org . ekstream . routing ;
Ein Klassendiagram ist in Abbildung 7.2 zu sehen. Es wurden drei unterschiedliche
Routingstrategien implementiert, auf die in den folgenden Abschnitten genauer eingegangen wird.
AbstractRouting
RoutingTable
<< use >>
StaticRouting
SimpleRouting
<< use >>
RoutingMessage
<< use >>
<< use >>
<< use >>
LocalityRouting
<< use, instantiate >>
LocalityVectorTable
BandwidthRequest
<< use, instantiate >>
<< use >>
<< use >>
LocalityVector
NetInfoTable
Abbildung 7.2.: Klassendiagram für die Routingklassen
späteren Versionen von ekStream wird diese Komponente in die Komponenten Scheduling und
Lastverteilung aufgeteilt, um einzelne Strategien noch genauer untersuchen zu können.
3 In
2005-03-21/015/IN99/2253
51
7. Implementierung
7.2.1. Schnittstellen
Damit einheitliche Schnittstellen für verschiedene Routingimplementierungen existieren, wurde die abstrakte Klasse AbstractRouting erstellt. Jede weitere Routingimplementierung wird nun von dieser abstrakten Klasse abgeleitet und deniert so die
vorgegebenen Schnittstellen.
47 p u b l i c
48
a b s t r a c t c l a s s AbstractRouting e x t e n d s Looper
implements PacketHandler {
Dort sind zunächst auch einige für andere Klassen wichtige Variablendenitionen, wie
der Wert für die entsprechenden Lokalitäten, enthalten.
50
p u b l i c s t a t i c f i n a l NodeId BROADCAST_NODEID = new IntegerNodeId ( -1) ;
51
52
p u b l i c s t a t i c f i n a l String ROUTING_LOOPER_NAME = " Routing ";
53
54
55
61
62
63
64
p u b l i c s t a t i c f i n a l i n t DEFAULT_TTL = TransportBag . DEFAULT_TIME_TO_LIVE ;
p u b l i c s t a t i c f i n a l i n t MAX_TTL = DEFAULT_TTL * 2;
public
public
public
public
static
static
static
static
final
final
final
final
String NODEPROPERTY_LOCALITY = " LOCALITY_INT ";
i n t LOCALITY_LOCAL = 1;
i n t LOCALITY_EXTENDED = 2;
i n t LOCALITY_GLOBAL = 3;
Eine der wichtigsten Methoden ist
send
zum Versenden von Nachrichten an andere
Knoten.
120
p u b l i c v o i d send ( Serializable data , NodeId nodeId ) {
send ( data , nodeId , DEFAULT_TTL ) ;
}
130
p u b l i c a b s t r a c t v o i d send ( Serializable data , NodeId nodeId , i n t timeToLive );
118
119
Zum entgegennehmen der Pakete, die vom
Methode
157
packetReceived
Transport Layer
empfangen wurden, ist die
zuständig.
p u b l i c a b s t r a c t v o i d packetReceived ( TransportBag bag );
Weiterhin sind die Methoden
bootstrap und update für das initiale Kennenlernen von
Knoten und für bestimmte periodische Vorgänge zur Aktualisierung verantwortlich.
174
p u b l i c a b s t r a c t v o i d bootstrap ( Vector addressVec );
180
p u b l i c a b s t r a c t v o i d update () ;
52
2005-03-21/015/IN99/2253
7.2. Routing
7.2.2. Statisches Routing
Das statische Routing ist in der Klasse StaticRouting implementiert.
55 p u b l i c
c l a s s StaticRouting e x t e n d s AbstractRouting {
Diese Klasse erhält initial durch die
bootstrap-Methode
eine Liste (implementiert als
Vektor) von Netzwerkadressen. Für alle Elemente dieser Liste wird eine
net. Mit Hilfe der
addNode-Methode wird die NodeId mit der dazugehörigen Netzwerk-
adresse in die Routingtabelle eingetragen. Ebenso wird ein
in den
258
259
260
261
262
263
264
265
266
267
NodeId berech-
Node Roster
Node-Objekt
erzeugt und
eingefügt.
p u b l i c v o i d bootstrap ( Vector addressVec ){
Enumeration addressEnum = addressVec . elements () ;
w h i l e ( addressEnum . hasMoreElements () ){
Object obj = addressEnum . nextElement () ;
i f (( obj != n u l l ) &&( obj i n s t a n c e o f SocketAddress )){
SocketAddress address = ( SocketAddress ) obj ;
addNode ( new IntegerNodeId ( address ) , address );
}
}
}
Da dies ein statisches Routing ist, wird kein (aktiver) Versuch unternommen, neue
Knoten kennen zu lernen und es müssen auch keine Informationen aktualisiert werden.
Aus diesem Grund ist die
273
274
275
update-Methode
leer.
p u b l i c v o i d update () {
// update of nodes not implemented in StaticRouting ( it 's static !)
}
Das Routing kann nur an bekannte Knoten Nachrichten verschicken. Da allerdings
Nachrichten anderer Knoten beantwortet werden sollen, müssen bei eingehenden Nachrichten unbekannter Knoten diese ebenfalls in die Routingtabelle und im
Node Roster
eingetragen werden.
207
220
p u b l i c v o i d packetReceived ( TransportBag bag ) {
i f (! routingTable . containsKey ( source )) {
221
SocketAddress address = bag . getAddress () ;
222
addNode ( source , address );
227
228
}
Dieses Routing ist sehr einfach und gut für Tests geeignet, da mit der
bootstrap-
Methode festgelegt werden kann, welcher Knoten welche Knoten kennt.
2005-03-21/015/IN99/2253
53
7. Implementierung
7.2.3. Einfaches dynamisches Routing
Das einfache dynamische Routing ist in der Klasse SimpleRouting implementiert.
47 p u b l i c
c l a s s SimpleRouting e x t e n d s AbstractRouting {
7.2.3.1. Nachrichten des Routings
Für den Nachrichtenaustausch des Routings mit dem Routing anderer Knoten existiert
die Klasse RoutingMessage mit verschiedenen Typen und einem Datenfeld.
34 p u b l i c
c l a s s RoutingMessage e x t e n d s Message {
35
36
p r i v a t e s t a t i c f i n a l l o n g serialVersionUID = 3618138970022950705 L;
37
38
39
40
41
42
43
44
45
73
/* *
* Collection of the types of the RoutingMessage .
*/
p u b l i c s t a t i c f i n a l i n t TYPE_PINGREQEST = 1;
from another node
// public static final int TYPE_PINGREPLY = 2;
p u b l i c s t a t i c f i n a l i n t TYPE_FINDNODE = 3;
address for a nodeId
p u b l i c s t a t i c f i n a l i n t TYPE_GETNODES = 4;
some nodeId , address maps
p u b l i c s t a t i c f i n a l i n t TYPE_RCVNODES = 5;
address map
// request a ( nulldata ) message
// request to another node for a
// request to another node for
// return another node a nodeId ,
p r i v a t e Serializable data ;
Bei dem Empfang einer Nachricht für das Routing des lokalen Knotens mit Hilfe der
packetReceived-Methode
wird die Nachricht der Methode
processRoutingMessage
übergeben. Dort erfolgt eine selektive Bearbeitung des jeweiligen Nachrichtentyps.
352
353
p r o t e c t e d v o i d processRoutingMessage ( RoutingMessage routMsg , NodeId source ,
TransportBag bag , i n t timetolive , Date rcvTime ) {
354
// PingRequest
i f ( routMsg . isPingReqest () ) {
Log . debug ( t h i s , " Received a PingRequest from Node " + source );
i f ( source . equals ( BROADCAST_NODEID )) {
Message msg = new RoutingMessage ( RoutingMessage . TYPE_PINGREQEST ,
nodeRoster . localNodeId () );
send ( msg , source ) ;
} else {
send ( n u l l , source );
}
return ;
355
356
357
358
359
360
361
362
363
364
365
54
2005-03-21/015/IN99/2253
7.2. Routing
}
366
367
// New NodeAddresses are known => have to be verified
i f ( routMsg . isRcvNodes () ){
368
369
// Request to find the NodeAddress for this Id
i f ( routMsg . isFindNode () ){
392
393
// Request for some NodeAddress
i f ( routMsg . isGetNodes () ){
445
446
469
}
7.2.3.2. Der Bootstrap-Vorgang
Anders als beim statischen Routing werden die initial erhaltenen Netzwerkadressen
nicht sofort als bekannt vorausgesetzt und eingetragen, sondern erst überprüft. Dies
erfolgt durch das Senden einer Nachricht (RoutingMessage), vom Typ
PINGREQUEST
an diese Adresse. Der andere Knoten antwortet auf diese Nachricht, falls die Adresse
richtig war und wird dann als bekannter Knoten eingetragen. Danach wird die
update-
Methode aufgerufen, damit die bekannten Knoten gleich nach weiteren Knoten gefragt
werden.
532
p u b l i c v o i d bootstrap ( Vector addressVec ) {
533
534
535
536
537
538
539
Log . debug ( t h i s ," Start bootstrap ." );
Enumeration addressEnum = addressVec . elements () ;
w h i l e ( addressEnum . hasMoreElements () ){
Object obj = addressEnum . nextElement () ;
i f (( obj != n u l l ) &&( obj i n s t a n c e o f SocketAddress )){
SocketAddress address = ( SocketAddress ) obj ;
Message message = new RoutingMessage ( RoutingMessage . TYPE_PINGREQEST ,
send ( message , BROADCAST_NODEID , address ); // send with BroadcastId , because
right Id isn 't known
} else {
Log . warn ( t h i s ," Bootstrap unexpected value in vector ( has to be a SocketAddress
)." );
}
542
543
544
545
546
547
}
548
549
550
551
552
// start Update to learn new nodes
f o r ( i n t i =0; i < 3; i ++) {
update () ;
}
2005-03-21/015/IN99/2253
55
7. Implementierung
553
554
}
7.2.3.3. Die Routingtabelle
Die Routingtabelle wurde als Klasse (RoutingTable) implementiert. Damit eziente
Anfragen sowohl nach der
NodeId als auch nach der Netzwerkadresse (SocketAddress)
möglich sind, werden zwei Hashtabellen verwendet. Eine Hashtabelle zur Auösung
von
NodeId
zu
SocketAddress
und eine umgekehrt. Damit sind Anfragen in beide
Richtungen schnell, allerdings entsteht dabei mehr Aufwand beim Aktualisieren von
Einträgen. Ebenso kennt die Routingtabelle den Zeitpunkt der letzten Aktualisierung,
um alte Einträge wieder löschen zu können.
81
82
83
84
85
86
87
88
89
90
p u b l i c s y n c h r o n i z e d v o i d addNodeAddress ( NodeId nodeId , SocketAddress address ) {
// overwrite if exists
i f ( lookupTable . containsKey ( nodeId )) {
Object obj = lookupTable . get ( nodeId ) ;
revLookupTable . remove ( obj );
}
lookupTable . put ( nodeId , address );
revLookupTable . put ( address , nodeId );
updateTimes . put ( nodeId , new Long ( System . currentTimeMillis () ));
}
Da nicht immer die Netzwerkadresse bekannt ist, werden auch Referenzeinträge auf
andere Knoten erlaubt, um eine Nachricht an einen Knoten schicken zu können. Auf
diese Weise kann eingetragen werden, dass Nachrichten für einen Knoten an einen
bestimmten anderen Knoten gesendet werden können.
7.2.3.4. Weiterleiten von Paketen
Da Pakete nicht immer direkt an den Empfänger verschickt werden können, existiert
die Möglichkeit der Weiterleitung.
So kann ein Paket an einen Knoten (Netzwerkadresse) mit einem anderen Empfänger
(NodeId) gesendet werden. Dann versucht dieser Knoten das Paket an diese
NodeId
weiterzuleiten. Der ursprüngliche Sender (NodeId) soll dabei erhalten bleiben, sodass
bei der Weiterleitung das ursprüngliche Paket als Daten in ein neues Paket eingepackt
und dann weitergeleitet wird.
56
2005-03-21/015/IN99/2253
7.2. Routing
217
308
309
310
311
// is this bag for me ? ( non forwarding of BroadcastNodeIds by Routing !)
i f (( nodeRoster . isLocal ( destination )) ||
BROADCAST_NODEID . equals ( destination )){
// Packet is for me => accept
312
336
337
338
339
340
341
} else {
// Packet is not for me => forward
i f ( timetolive > 1) {
send ( bag , destination , timetolive - 1) ;
}
}
Dies kann unter Umständen zu Kreisen im Netzwerk führen, sodass jedes Paket einen
TTL-Wert erhält um unendliches Weiterleiten zu verhindern. Dieser TTL-Wert wird
bei jeder Weiterleitung um Eins verringert. Das Paket wird nicht mehr weitergeleitet,
wenn der TTL-Wert Null erreicht hat.
7.2.3.5. Lernen neuer Knoten
Durch die starke Verbreitung von Firewalls mit NAT kann eine erhaltene Netzwerkadresse nicht als gültig angenommen werden, sondern muss überprüft werden.
Eine Netzwerkadresse wird immer dann in die Routingtabelle eingetragen, wenn ein
Paket mit unbekannten Sender empfangen wurde. Auf diese Art wurden auch die Netzwerkadressen im
217
238
239
240
241
242
243
244
245
246
247
Bootstrap -Vorgang (Abschnitt 7.2.3.2) überprüft.
// learn NodeAddress
s y n c h r o n i z e d ( routingTable ) {
i f (! routingTable . isAddress ( source )) {
// source not known
Log . debug ( t h i s ," Add NodeId " + source + " with address "
+ bag . getAddress () + " to RoutingTable .");
routingTable . addNodeAddress ( source , bag . getAddress () );
i f (! nodeRoster . containsNode ( source ) ) {
addNode ( source );
}
248
249
250
251
252
} else {
// source known
i f ( bag . getAddress () . equals ( routingTable . getNodeAddress ( source ) )) {
// address is the same :)
2005-03-21/015/IN99/2253
57
7. Implementierung
routingTable . updateTimeStamp ( source );
i f (( nodeRoster . containsNode ( source ) )
&&( nodeRoster . get ( source ). getProperties () . isRegistered (
NODEPROPERTY_FAILURE ))) {
nodeRoster . get ( source ). getProperties () . unregister ( NODEPROPERTY_FAILURE );
}
} else {
// address differ , ignore packet
Log . warn ( t h i s , " Ignore Packet from Node "
+ source + " with different SocketAddress as known ! ");
return ;
}
253
254
255
256
257
258
259
260
261
262
263
}
264
}
265
Bei einem weitergeleiteten Paket kann zusätzlich noch eine Referenz vom ursprünglichen Sender zum letzten Sender, eingetragen werden. Auf diese Art kann auch der
ursprüngliche Sender erreicht werden, da der letzte Sender ebenfalls mindestens einen
Referenzeintrag für diesen Knoten besitzt (Dies lässt sich bis zum Sender weiterführen).
// is this a bag in bag ? ( forwarded message )
i f ( data i n s t a n c e o f TransportBag ) {
bag = ( TransportBag ) data ;
274
275
276
// learn NodeAddress
s y n c h r o n i z e d ( routingTable ) {
i f (! routingTable . isKnown ( source )) {
routingTable . addNodeAddress ( source , bag . getSourceNode () );
} else {
i f ( System . currentTimeMillis () > routingTable . getTimeStamp ( source )
+ ROUTINGTABLE_ENTRY_TIMEOUT ) {
// address is to old => take new address
routingTable . delNodeAddress ( source );
routingTable . addNodeAddress ( source , bag . getSourceNode () ) ;
}
}
}
285
286
287
288
289
290
291
292
293
294
295
296
297
In Abbildung 7.3 ist zu sehen, welche Schritte notwendig sind, um die Adresse eines
Knotens zu erlernen. Dabei möchte Knoten A die Adresse von Knoten C kennen lernen.
Beide Knoten (A und B) kennen C und umgekehrt.
1. Knoten A fragt Knoten B, ob dieser die Adresse von Knoten C kennt (Routing-
Message
vom Typ
FINDNODE).
2. Knoten B kennt die Adresse von C und schickt sie Knoten A. Zusätzlich sendet er
die Adresse von Knoten A an Knoten C (RoutingMessage vom Typ
58
RCVNODES).
2005-03-21/015/IN99/2253
7.2. Routing
1. getAddr(C)
A
2. sendAddr(C)
B
2. sendAddr(A)
C
3. PingRequest
3. PingRequest
4. PingReply
4. PingReply
Abbildung 7.3.: Kennenlernen von Knoten C
3. Beide Knoten (A und C) versuchen sich gegenseitig eine Nachricht (Ping-Request)
zu schicken, die der jeweils andere beantworten muss (RoutingMessage vom Typ
PINGREQUEST).
4. Jeder Knoten, der einen Ping-Request erhält, antwortet auf diesen mit einem
Ping-Reply (Antwort mit einem leeren Paket, da nur die Adresse wichtig ist.).
Knoten A kann die Adresse von Knoten C erst eintragen, wenn er direkt von ihm eine
Nachricht erhalten hat. Dies erfolgt spätestens im 4. Schritt.
Es kann zwischen Knoten A und B sowie zwischen Knoten B und C eine Firewall mit
NAT existieren, wodurch sich vier Kombinationsmöglichkeiten ergeben:
1. kein NAT:
Alle Pakete kommen an und Knoten A kennt nach dem 3. Schritt die Adresse
von Knoten C.
2. NAT zwischen A und B:
Knoten A kann C nicht unter der von B angegebenen Adresse erreichen, aber
Knoten C kann A erreichen. Somit kennt Knoten A die Adresse von C auch nach
dem 3. Schritt und antwortet auf den Ping-Request, damit auch C die Adresse
von A kennt.
3. NAT zwischen B und C:
Knoten C kann A nicht unter der von B angegebenen Adresse erreichen, aber
2005-03-21/015/IN99/2253
59
7. Implementierung
Knoten A kann C erreichen. Somit kann Knoten C auf den Ping-Request von A
antworten. Knoten A kennt die Adresse von Knoten C nach dem 4. Schritt.
4. NAT zwischen A und B sowie zwischen B und C:
Da hier Knoten B die Adressen von A und C kennt, die auch Knoten A und C
zum Erreichen des jeweils anderen Knotens ansprechen müssen, ist das Verhalten
wie ohne NAT (siehe 1. Kombinationsmöglichkeit).
7.2.3.6. Senden von Nachrichten
Das Senden einer Nachricht wird in mehrere Methoden aufgeteilt, damit Grundfunktionen in abgeleiteten Klassen erhalten bleiben können.
118
p u b l i c v o i d send ( Serializable data , NodeId nodeId , i n t timetolive ) {
158
p r o t e c t e d v o i d sendBroadCast ( Serializable data , Vector ignoreNodeIds , i n t timetolive
) {
180
p r o t e c t e d v o i d send ( Serializable data , NodeId nodeId , SocketAddress address ){
194
p r o t e c t e d s y n c h r o n i z e d v o i d send ( Serializable data , NodeId nodeId ,
Falls die Nachricht nicht an mehrere Knoten geschickt werden soll (Broadcast) und der
Empfänger in der Routingtabelle bekannt ist, wird die Nachricht dorthin versendet.
Ansonsten wird die Nachricht als Broadcast an mehrere verschickt und ebenso eine
Suchanfrage nach diesem Knoten, um spätere Pakete direkt versenden zu können.
118
p u b l i c v o i d send ( Serializable data , NodeId nodeId , i n t timetolive ) {
i f (! nodeId . equals ( BROADCAST_NODEID )) {
// send to this node
Object obj = routingTable . getNodeAddress ( nodeId );
i f ( obj != n u l l ) {
// node is known
i f ( obj i n s t a n c e o f NodeId ) {
obj = routingTable . getNodeAddress (( NodeId ) obj );
}
send ( data , nodeId , ( SocketAddress ) obj , timetolive );
r e t u r n ; // finish
} else {
// node isn 't known => send FindNodeRequest
126
127
128
129
130
131
132
133
134
135
136
137
138
RoutingMessage message = new RoutingMessage ( RoutingMessage . TYPE_FINDNODE ,
nodeRoster . localNodeId () , new NodeAddress ( nodeId , n u l l ));
send ( message , BROADCAST_NODEID );
139
140
141
60
2005-03-21/015/IN99/2253
7.2. Routing
}
142
}
143
144
// now send to BROADCAST_NODEID or unknown NodeId !
145
146
sendBroadCast ( data , n u l l , timetolive ) ;
147
148
}
Das Senden der Nachricht erfolgt mit Hilfe des
194
195
196
197
198
199
Transport Layer.
p r o t e c t e d s y n c h r o n i z e d v o i d send ( Serializable data , NodeId nodeId ,
SocketAddress address , i n t timetolive ) {
Log . debug ( t h i s ," Send TransportBag to Node " + nodeId
+ " with address " + address + " and TTL " + timetolive ) ;
transportLayer . send ( bagFactory . createBag ( data , nodeId , address , timetolive ));
}
Bei einem Broadcast soll eine Nachricht an viele Knoten gesendet werden. Hier wird die
Nachricht an durchschnittlich zehn zufällig ausgewählte Knoten versendet, indem bei
jedem Eintrag in der Routingtabelle (ohne Referenzen) eine Zufallszahl erzeugt wird.
Ist die Zufallszahl kleiner als eine von der Anzahl der Einträge in der Routingtabelle
abhängige Schwelle, kann die Nachricht an diese Adresse gesendet werden. Zusätzlich
ist es möglich noch eine Liste (Vektor) an Knoten übergeben werden, an die diese
Nachricht nicht geschickt werden soll.
158
159
160
161
162
163
164
165
166
167
168
) {
// send to some random Nodes
Enumeration enumNodes = routingTable . listKnownNodes () ;
double threshold = ( double ) 10 / routingTable . getsize () ;
w h i l e ( enumNodes . hasMoreElements () ) {
NodeId aktNodeId = ( NodeId ) enumNodes . nextElement () ;
i f ( ignoreNodeIds . contains ( aktNodeId ) ) c o n t i n u e ;
i f ( Math . random () <= threshold ) {
send ( data , BROADCAST_NODEID , ( SocketAddress ) routingTable . getNodeAddress (
aktNodeId ) , timetolive );
}
}
169
170
}
7.2.3.7. Aktualisieren der Knotenliste
Da das Routing die Übersetzung von
nur
Node-Objekte
oder
NodeIds
2005-03-21/015/IN99/2253
NodeId zur Netzwerkadresse vornimmt und intern
bekannt sind, muss das Routing die
Node-Objekte
im
61
7. Implementierung
Node Roster
eintragen und löschen.
Zum Erzeugen und Löschen eines
477
Node-Objektes
existiert die
addNode-Methode.
p r o t e c t e d v o i d addNode ( NodeId nodeId ) {
Falls von einem Knoten für eine bestimmte Zeit (ROUTINGTABLE_ENTRY_TIMEOUT) kein
Paket empfangen wurde, wird er mit Hilfe der
tabelle und aus dem
504
Node Roster
removeNode-Methode
aus der Routing-
ausgetragen.
p r o t e c t e d v o i d removeNode ( NodeId nodeId ) {
In bestimmten Abständen (UPDATE_SLEEP_TIME) wird die
update-Methode
aufgeru-
fen. Falls nicht genug Einträge in der Routingtabelle vorhanden sind, fragt sie die ihr
bekannte Knoten nach weiteren Knoten. Ebenso werden
PINGREQUEST
RoutingMessages
vom Typ
an die Knoten gesendet, von denen lange Zeit kein Paket empfangen
wurde.
560
i f ( routingTable . getsize () < ROUTINGTABLE_SIZE_WANT ) {
// want to learn new nodes
570
571
572
w h i l e ( routEnum . hasMoreElements () ) {
NodeId remNodeId = ( NodeId ) routEnum . nextElement () ;
i f ( routingTable . isAddress ( remNodeId ) ) {
send ( new RoutingMessage ( RoutingMessage . TYPE_GETNODES , localNodeId ) ,
remNodeId );
} // else ignore
}
573
574
575
576
577
578
i f (( routingTable . isAddress ( remNodeId )) &&( aktTime
> routingTable . getTimeStamp ( remNodeId ) + ROUTINGTABLE_ENTRY_TIMEOUT /2 ))
{
// send pingrequest if nodeAddress known and relativly old
send ( new RoutingMessage ( RoutingMessage . TYPE_PINGREQEST , localNodeId ) ,
remNodeId );
}
585
586
587
588
589
7.2.4. Lokalitätsbewusstes dynamisches Routing
Das lokalitätsbewusste dynamische Routing ist in der Klasse LocalityRouting implementiert. Sie erbt alle Methoden des einfachen dynamischen Routings (Simple-
Routing), die so einfach wieder verwendet und erweitert werden können.
55 p u b l i c
62
c l a s s LocalityRouting e x t e n d s SimpleRouting {
2005-03-21/015/IN99/2253
7.2. Routing
7.2.4.1. Erweiterungen
Zusätzlich zum SimpleRouting kann das LocalityRouting die RTT- und die Bandbreitenbestimmung initiieren (siehe Abschnitte 7.2.4.2 und 7.2.4.3). Hierzu ist es notwendig, die Netzwerkadressen der jeweiligen Serverkomponente der anderen Knoten zu
kennen.
72
73
p r i v a t e NetInfoTable roundTripTimeTable ;
to the EchoService
p r i v a t e NetInfoTable bandwidthTable ;
Diese Adressen werden in
// RTTs with timestamp and address
// address to the BandwidthService
NetInfoTable-Objekten verwaltet, die eine Hashtabelle bein-
halten.
34 p u b l i c
46
47
48
49
50
51
52
53
c l a s s NetInfoTable {
/* *
* Contains a Vector to each given key ( NodeId )
* The Vector contains :
*
- an int - value
*
- a
timestamp for the int - value ( long )
*
- an
address ( SocketAddress ) => this mustn 't be null
*/
p r i v a t e Hashtable infos ; // contains a vector
Die Berechnung der Lokalität (Abschnitt 7.2.4.4) erfordert das Verwalten der Lokalitätsvektoren der anderen Knoten. Hierfür wird die Klasse LocalityVectorTable verwendet.
33 p u b l i c
c l a s s LocalityVectorTable {
34
35
36
37
p r i v a t e Hashtable dataTable ;
p r i v a t e Hashtable timestamps ;
// Contains a LocalityVector
// Contains a Long
Diese Klassen werden anstelle einer einfachen Hashtabelle verwendet, um für jeden
Eintrag einen separaten Zeitstempel verwalten zu können.
Damit diese Informationen unter den anderen Knoten ausgetauscht werden können,
werden die Nachrichtentypen der
RoutingMessage
erweitert. Es wird je ein Typ zum
Anfordern der Information und ein Typ zum Senden der Informationen benötigt.
34 p u b l i c
46
c l a s s RoutingMessage e x t e n d s Message {
p u b l i c s t a t i c f i n a l i n t TYPE_GETECHOADDRESS = 6;
SocketAddress of his DatagramEchoService
2005-03-21/015/IN99/2253
// request to another node for the
63
7. Implementierung
47
48
49
50
51
p u b l i c s t a t i c f i n a l i n t TYPE_RCVECHOADDRESS = 7; //
SocketAddress of the DatagramEchoService
p u b l i c s t a t i c f i n a l i n t TYPE_GETLOCALITY = 8;
//
localityVector
p u b l i c s t a t i c f i n a l i n t TYPE_RCVLOCALITY = 9;
//
localityVector
p u b l i c s t a t i c f i n a l i n t TYPE_GETBWADDRESS = 10;
//
SocketAddress of his DatagramBandwidthService
p u b l i c s t a t i c f i n a l i n t TYPE_RCVBWADDRESS = 11;
//
SocketAddress of the DatagramBandwidthService
Da sich die Funktion der bereits implementierten
return another node the
request to another node for the
request to another node for the
RoutingMessage-Typen
in Simple-
Routing nicht geändert haben, kann die Implementierung der Superklasse einfach nach
der Abarbeitung der neuen Typen aufgerufen werden.
314
p r o t e c t e d v o i d processRoutingMessage ( RoutingMessage routMsg , NodeId source ,
// Request of Addresses for RTTMeasurementService
i f ( routMsg . isGetEchoAddress () ){
317
318
// New Addresses of RTTMeasurementServices
i f ( routMsg . isRcvEchoAddress () ){
346
347
// Request of LocalityVectors
i f ( routMsg . isGetLocality () ){
369
370
// New LocalityVector is known
i f ( routMsg . isRcvLocality () ){
399
400
// Request of Addresses for BandwidthMeasurement
i f ( routMsg . isGetBWAddress () ){
433
434
// New Addresses of BandwidthMeasurement
i f ( routMsg . isRcvBWAddress () ){
461
462
// standard AddressTypes also relevant !
s u p e r . processRoutingMessage ( routMsg , source , bag , timetolive , rcvTime );
484
485
Ebenso müssen in der
update-Methode
die Aktualisierungen in der Superklasse (für
die Verwaltung der Routingtabelle) abgearbeitet werden.
174
175
176
l o n g akttime = System . currentTimeMillis () ;
s u p e r . update () ; // update routingTable in superclass
Die Berücksichtigung der Lokalität in der Implementierung der
sendBroadCast-Methode
konnte noch nicht vollendet werden. Dies sollte in späteren Revisionen von
ekStream
erfolgen.
64
2005-03-21/015/IN99/2253
7.2. Routing
156
159
) {
// ! TODO send to some nodes ( some local , and 1 exended and 1 global )
160
161
s u p e r . sendBroadCast ( data , ignoreNodeIds , timetolive );
7.2.4.2. Bestimmung der RTT
Die RTT wird mit Hilfe der Komponente
tieren in dem Paket
org.ekstream.net
Network Measurement
gemessen. Dazu exis-
die Klassen EchoManager und Datagram-
EchoService.
Der DatagramEchoService nimmt auf einen UDP-Socket Pakete entgegen und sendet sie unverzüglich an den Sender zurück.
Aufträge in Form einer
EchoSession
werden vom EchoManger entgegengenommen
und gleichzeitig bearbeitet. Dazu versendet er Messpakete an die in der
EchoSession
angegebenen Netzwerkadressen und misst die Zeitspanne bis zum Empfangen der Antwort.
Da das Routing die Übersetzung zwischen Netzwerkadresse und
NodeId
übernimmt,
muss es die Aufträge an den EchoManager übergeben. Da allerdings der Data-
gramEchoService eine separate Netzwerkadresse verwendet, verwaltet das Routing
diese extra.
Wenn eine
EchoSession
beendet wurde erhält das Routing eine Nachricht von Typ
EchoResult. Das Routing verarbeitet diese Nachricht und berechnet daraus einen neuen eigenen Lokalitätsvektor (siehe Abschnitt 7.2.4.4).
493
p u b l i c v o i d messageReceived ( Message message ) {
494
495
496
i f ( message i n s t a n c e o f EchoResult ) {
// this Message is a EchoResult
7.2.4.3. Bestimmung der Bandbreite
Die Bestimmung der Bandbreite übernimmt ebenfalls die Komponente
urement
im Paket
Network Meas-
org.ekstream.net. Dazu existieren die Klassen BandwidthMan-
ager und DatagramBandwidthManager.
2005-03-21/015/IN99/2253
65
7. Implementierung
Da das Routing die Bandbreite nicht verwendet, allerdings die Übersetzung zwischen
Netzwerkadresse und
NodeId übernehmen muss, ist hierbei die Bearbeitung etwas kom-
plizierter.
Das Routing nimmt
gegen, erzeugt eine
493
BandwidthRequest-Nachrichten
BandwidthSession
von anderen Komponenten ent-
und übergibt sie dem BandwidthManager.
// another component request BW - Measurement for a node
i f ( message i n s t a n c e o f BandwidthRequest ){
BandwidthRequest bwreq = ( BandwidthRequest ) message ;
559
560
561
BandwidthSession bwsession = new BandwidthSession (
bandwidthTable . getAddress (
bwreq . getRemNodeId () ) , bwreq . getResultTarget () ,
bwreq . getRemNodeId () ) ;
bwManager . addBandwidthSessionToQueue ( bwsession ) ;
567
568
569
570
571
Dieser bestimmt die Bandbreite und sendet eine
BandwidthResult-Nachricht
direkt
Lokalisierung
(siehe
an die anfordernde Komponente zurück. Dies ist zurzeit nur die
Abschnitt 7.3.2.2).
7.2.4.4. Lokalitätsbestimmung
Nun soll auf die Implementierung der in Abschnitt 6.2.2 vorgestellten Ansatzes zur
Lokalitätsbestimmung eingegangen werden.
Es wurde die Klasse LocalityVector für den Lokalitätsvektor erstellt, die den Vektor
und die Berechnungen beinhaltet.
34 p u b l i c
39
40
41
42
43
c l a s s LocalityVector implements Serializable {
/* *
* Size of the vector ( includes NodeId ).
* The dimension of the values are ( size -1) .
*/
p u b l i c s t a t i c f i n a l i n t VECTORSIZE = 6;
44
45
46
47
48
49
50
51
/* *
* The vector .
* On position 0 the NodeId is saved .
* The other values are Long .
*/
p r i v a t e Vector vector ;
66
2005-03-21/015/IN99/2253
7.2. Routing
Die Dimension
D
des Lokalitätsvektors entspricht der
Eins, da an der 1. Stelle noch die
NodeId
VECTORSIZE-Konstante
minus
gespeichert ist.
Beim Erzeugen eines Objektes dieser Klasse wird der Lokalitätsvektor zufällig gewählt.
t h i s . vector = new Vector ( VECTORSIZE );
t h i s . vector . add (0 , nodeId );
f o r ( i n t i =1; i < VECTORSIZE ; i ++) {
t h i s . vector . add (i , new Double ( Math . random () * 512 - 256 )) ;
}
64
65
66
67
68
Die Berechnung des Abstandes zu einem anderen Vektor wird in der
distance-Methode
vorgenommen.
p u b l i c s y n c h r o n i z e d double distance ( LocalityVector locVec ){
i f (! isCompatible ( locVec ) ) r e t u r n -1;
double dist = 0;
79
80
81
82
f o r ( i n t i = 1; i < VECTORSIZE ; i ++) {
double a = (( Double ) vector . get (i )). doubleValue () ;
double b = (( Double ) locVec . vector . get (i)). doubleValue () ;
a -= b ;
dist += a * a;
}
r e t u r n Math . sqrt ( dist );
83
84
85
86
87
88
89
}
90
calculate→
−
Lokalitätsvektor y , die
Wenn eine RTT zu einem anderen Knoten bestimmt wurde, wird die
Methode aufgerufen. Sie erhält als Parameter den anderen
gemessene
RT Tmeas
und die aktuelle Lernrate
δ.
Der Rückgabewert der Methode ist
der Abstand der Lokalitätsvektoren vor der Berechnung (RT Tcal ), um daraus den Fehler
ε
103
104
105
106
107
108
bestimmen zu können.
p u b l i c s y n c h r o n i z e d double calculate ( LocalityVector locVec ,
double roundTripTime , double learnrate ){
i f ( equalId ( locVec )) r e t u r n 0;
i f (! isCompatible ( locVec ) ) r e t u r n -1;
double distance = t h i s . distance ( locVec );
double failure = distance - roundTripTime ;
109
110
111
112
f o r ( i n t i = 1; i < VECTORSIZE ; i ++) {
double a = (( Double ) vector . get (i)) . doubleValue () ;
double b = (( Double ) locVec . vector . get (i )). doubleValue () ;
113
114
115
116
117
118
i f ( failure != 0) {
i f ( distance == 0) {
a += Math . random () * failure * learnrate ;
} else {
a += (b -a) * ( failure / distance ) * learnrate ;
2005-03-21/015/IN99/2253
67
7. Implementierung
}
vector . set (i , new Double (a ));
119
120
}
121
}
122
r e t u r n distance ;
126
127
}
Die Anpassung der Lernrate
Dazu wird der Fehler
ε
und ein relativer Fehler
δ
wird in der LocalityRouting-Klasse vorgenommen.
auf die Summe der berechneten und gemessenen RTT bezogen
α
berechnet (siehe Formel 7.1).
|ε|
RT Tmeas + RT Tcal
|RT Tmeas − RT Tcal |
=
RT Tmeas + RT Tcal
α=
Bei einem
α
von
0.5
oder berechnet). Bei
Wert
493
α
ist der Fehler
α = 0.3
ist
ε
ε
(7.1)
doppelt so groÿ wie die kleinere RTT (gemessen
6
etwas kleiner als die kleinere RTT ( ). Mit diesem
7
wird nun die Lernrate erhöht oder verringert.
// update local localityvector
LocalityVector localVector = localityTable . getVector (
double distance = localVector . calculate (
localityTable . getVector ( echoRes . getNodeId () ) ,
echoRes . getRTT () , LOCALITY_learn_rate );
Log . debug ( t h i s , " LocalLocalityVector recalculated : " + localVector
+ " failure was : " + ( distance - echoRes . getRTT () )
+ " by distance : " + distance );
509
510
511
512
513
514
515
516
517
518
// update thresholds and learnrate
519
520
double a = distance - echoRes . getRTT () ;
i f ( a < 0) a = -a;
521
522
523
i f ( a != 0 ) {
// now distance + RTT can 't be 0 !
a = a / ( distance + echoRes . getRTT () );
}
i f ( a > 0.6 ) LOCALITY_learn_rate += 0.01;
i f ( a < 0.5 ) LOCALITY_learn_rate -= 0.01;
i f ( a < 0.3 ) LOCALITY_learn_rate -= 0.01;
524
525
526
527
528
529
530
531
68
2005-03-21/015/IN99/2253
7.2. Routing
532
i f ( LOCALITY_learn_rate < 0.05) LOCALITY_learn_rate = 0.05;
i f ( LOCALITY_learn_rate > 0.3) LOCALITY_learn_rate = 0.3;
533
534
Das Aktualisierungsintervall
in der
τ (LOCALITY_UPDATE_TIME) zwischen RTT-Messungen wird
update-Methode bei jedem Durchlauf bis zu einem Maximalwert erhöht. Ebenso
erfolgt in dieser Methode eine Anforderung einer RTT-Messung, falls
τ
für den jewei-
ligen Lokalitätsvektor abgelaufen ist.
174
i f ( akttime - localityTable . getTimestamp ( remNodeId ) > LOCALITY_UPDATE_TIME ) {
// time to learn new => request RTT - Measurement
i f ( roundTripTimeTable . containsAddress ( remNodeId )){
// request RTT - Measurement
EchoSession echoRequest = new EchoSession ( remNodeId ,
roundTripTimeTable . getAddress ( remNodeId ) ,
getMessenger () , NumberOfPings );
Log . debug ( t h i s , " Start EchoSession to node " + remNodeId );
echoManager . startSession ( echoRequest );
} else {
253
254
255
256
257
258
259
260
261
262
// adapt the LOCALITY_UPDATE_TIME
i f ( LOCALITY_UPDATE_TIME < 20000) {
LOCALITY_UPDATE_TIME += 100;
}
299
300
301
302
Zur groben Einteilung der Entfernungen der Knoten werden die drei Horizonte
(local),
lokal
erweitert (extended) und global (global) verwendet. Mit Hilfe von Schwell-
werten kann jeder Knoten in einen Horizont eingeteilt werden. Bei jedem Durchlauf
der
update-Methode werden alle Nodes im Node Roster
überprüft, ob sich die jeweilige
Zuordnung in den Horizont geändert hat. Es ist nicht sinnvoll, dies bei jeder möglichen Änderung eines Lokalitätsvektors zu überprüfen, da bei der Neuberechnung des
eigenen Lokalitätsvektors alle
Nodes überprüft werden müssten. Dabei werden die An-
zahlen der jeweiligen Knoten in jedem Horizont gezählt, um damit die Schwellwerte
dynamisch ändern zu können.
174
219
220
221
222
223
224
225
// save locality - data in nodeproperty
s y n c h r o n i z e d ( nodeRoster ) {
double dist = localVector . distance ( localityTable . getVector ( remNodeId ) );
i f ( nodeRoster . containsNode ( remNodeId )) {
TypedProperties prop = nodeRoster . get ( remNodeId ). getProperties () ;
i f ( dist < LOCALITY_threshold_local ) {
numLocNodes ++;
2005-03-21/015/IN99/2253
69
7. Implementierung
i f (! prop . get ( NODEPROPERTY_LOCALITY ). equals ( LOCALITY_OBJECT_LOC ))
prop . put ( NODEPROPERTY_LOCALITY , LOCALITY_OBJECT_LOC );
} else {
i f ( dist < LOCALITY_threshold_extended ) {
numExtNodes ++;
i f (! prop . get ( NODEPROPERTY_LOCALITY ). equals ( LOCALITY_OBJECT_EXT ))
prop . put ( NODEPROPERTY_LOCALITY , LOCALITY_OBJECT_EXT );
} else {
numGloNodes ++;
i f (! prop . get ( NODEPROPERTY_LOCALITY ). equals ( LOCALITY_OBJECT_GLO ))
prop . put ( NODEPROPERTY_LOCALITY , LOCALITY_OBJECT_GLO );
}
}
226
227
228
229
230
231
232
233
234
235
236
237
238
}
239
}
240
7.3. Lokalisierung
Alle Klassen der Lokalisierung sind in dem Paket
org.ekstream.localisation
zu-
sammengefasst.
22 package org . ekstream . localisation ;
Die Lokalisierung wird in zwei Teile aufgeteilt: einen aktiven und einen passiven Teil.
Der aktive Teil sucht im Netzwerk nach Diensten (bzw.
Sessions)
und bearbeitet
auch die Anfragen von anderen Knoten. Der passive Teil ist die Schnittstelle zum
Scheduler,
über die dem
Scheduler
nach bestimmten Kriterien ausgewählte bekannte
Knoten geliefert werden.
Die Implementierung verschiedener Lokalisierungsstrategien konnten in dem zeitlich begrenzten Rahmen der Diplomarbeit nicht vorgenommen werden, da der Schwerpunkt
dieser Diplomarbeit beim Routing lag. Daher wurde eine einfache Lokalisierung entwickelt.
Die Schnittstellen der Lokalisierung sind in den abstrakten Klassen AbstractLocalisa-
tion und AbstractNetLocalisation deniert. Dabei ist der passive Teil AbstractLocalisation eine synchrone Schnittstelle zum
70
Scheduler. Der Methode select können
2005-03-21/015/IN99/2253
7.3. Lokalisierung
unterschiedliche Parameter übergeben werden, damit die entsprechende Auswahl getroen werden kann.
38 p u b l i c
a b s t r a c t c l a s s AbstractLocalisation {
130
p u b l i c a b s t r a c t Set select ( Stream session , i n t horizon );
139
p u b l i c a b s t r a c t Set select ( ElementaryStream stream , i n t horizon ) ;
153
p u b l i c a b s t r a c t Set select ( ElementaryStream stream , i n t horizon , l o n g minSecMaxTime ,
l o n g maxSecMinTime , i n t minBw );
154
AbstractNetLocalisation ist die Schnittstelle für den aktiven Teil. Dieser beinhaltet
die Suche nach bestimmten Diensten (Session) im Netzwerk und die Aktualisierung
der Informationen für die Knoten im
40 p u b l i c
a b s t r a c t c l a s s AbstractNetLocalisation e x t e n d s Looper {
Die gesuchten
108
109
110
112
113
114
116
117
118
120
121
122
Node Roster.
Sessions
können mit folgenden Methoden bearbeitet werden:
p u b l i c boolean addSession ( Stream session ) {
r e t u r n searchedSessions . add ( session );
}
p u b l i c Iterator listSessions () {
r e t u r n searchedSessions . iterator () ;
}
p u b l i c boolean containsSession ( Stream session ) {
r e t u r n searchedSessions . contains ( session );
}
p u b l i c boolean removeSession ( Stream session ) {
r e t u r n searchedSessions . remove ( session );
}
Die
search-Methode
ist für das Suchen von Knoten, die die gesuchten
Sessions
an-
bieten, zuständig.
124
p u b l i c a b s t r a c t v o i d search ( Stream session ) ;
Zum Aktualisieren von bekannten Informationen ist die
126
update-Methode
vorhanden.
p u b l i c a b s t r a c t v o i d update () ;
Die Behandlung der Standard-Nachrichten wird in separate Methoden unterteilt.
Lo-
cateSession wird zum Suchen einer Session, LocateSessionResult zum Empfangen
von Informationen der Knoten (z. B. als Antwort auf
LocateSession) und GetNodeInfo
zum Aktualisieren der Informationen eines Knotens verwendet.
2005-03-21/015/IN99/2253
71
7. Implementierung
128
p r o t e c t e d a b s t r a c t v o i d receivedGetNodeInfo ( GetNodeInfo msg );
130
p r o t e c t e d a b s t r a c t v o i d receivedLocateSession ( LocateSession msg ) ;
132
p r o t e c t e d a b s t r a c t v o i d receivedLocateSessionResult ( LocateSessionResult msg );
7.3.2. Einfache Lokalisierung
Die einfache Lokalisierung sucht im Netzwerk nicht nach Knoten mit einer
Session,
sondern aktualisiert nur die Informationen aller bekannten Knoten. Da die Knotenanzahl, die für den anschlieÿenden Test zur Verfügung stehen wird, kleiner als die gewünschte Mindestanzahl der bekannten Knoten für das dynamische
Routing
ist, reicht
diese Implementierung für die gegebenen Umstände aus. Die Klasse SimpleLocalisa-
tion ist die Implementierung des passiven Teils, während die Klasse SimpleNetLocalisation die Implementierung des aktiven Teils darstellt.
41 p u b l i c
c l a s s SimpleLocalisation e x t e n d s AbstractLocalisation {
53 p u b l i c
c l a s s SimpleNetLocalisation e x t e n d s AbstractNetLocalisation {
7.3.2.1. Passiver Teil
Die Klasse SimpleLocalisation versucht dem
Nodes
Scheduler
eine geeignete Menge an
zu übergeben, sofern diese vorhanden sind.
Dabei erfolgt die Bearbeitung jedes möglichen Kriteriums in einer separaten Methode.
Jede dieser Methoden kann mit einem Filter verglichen werden. Sie erhält eine Menge
an Knoten und gibt eine Menge der Knoten zurück, die das jeweilige Kriterium erfüllen.
Für die Kombination mehrerer Kriterien können diese Methoden nacheinander auf der
jeweils angepassten Ergebnismenge aufgerufen werden.
79
80
p u b l i c Set select ( ElementaryStream stream , i n t horizon , l o n g minSecMaxTime ,
l o n g maxSecMinTime , i n t minBw ) {
Set currentNodeSet = selectNodesHorizon ( nodeRoster . nodeSet () , horizon ) ;
currentNodeSet = selectNodesStream ( currentNodeSet , stream ) ;
84
85
86
currentNodeSet = selectNodesTimes ( currentNodeSet , stream , minSecMaxTime ,
maxSecMinTime );
currentNodeSet = selectNodesBandwidth ( currentNodeSet , minBw );
87
88
89
r e t u r n currentNodeSet ;
90
91
}
72
2005-03-21/015/IN99/2253
7.3. Lokalisierung
Die möglichen einzelnen Kriterien sind:
100
p r o t e c t e d Set selectNodesHorizon ( Collection nodes , i n t horizon ) {
145
p r o t e c t e d Set selectNodesSession ( Set nodes , Stream session ) {
176
p r o t e c t e d Set selectNodesStream ( Set nodes , ElementaryStream stream ) {
212
p r o t e c t e d Set selectNodesTimes ( Set nodes , ElementaryStream stream , l o n g
minSecMaxTime ,
265
p r o t e c t e d Set selectNodesBandwidth ( Set nodes , i n t minBandwidth ) {
Die Auswahl des Horizontes wird immer benötigt und kann deshalb als erstes Kriterium
verwendet werden. Dabei wird der Methode immer die gesamte Menge der bekannten
Knoten aus dem
Node Roster
übergeben. Bei der Auswahl des Horizontes ist zu beach-
ten, dass ein gröÿerer Horizont die kleineren beinhaltet.
100
101
102
103
104
105
106
107
p r o t e c t e d Set selectNodesHorizon ( Collection nodes , i n t horizon ) {
Set nodeSetHorizon = new HashSet () ;
Node currentNode ;
TypedProperties currentProperty ;
String key = NODEPROPERTY_LOC_TYPE ;
String key1 = NODEPROP_Busy ;
i n t locality = 0;
boolean busy = t r u e ;
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
s y n c h r o n i z e d ( nodeRoster ) {
Iterator nodesIt = nodes . iterator () ;
w h i l e ( nodesIt . hasNext () ) {
Object nodeObject = nodesIt . next () ;
i f ( nodeObject i n s t a n c e o f Node ) {
currentNode = ( Node ) nodeObject ;
currentProperty = currentNode . getProperties () ;
s y n c h r o n i z e d ( currentProperty ) {
i f ( currentProperty . isRegistered ( key ) ) {
locality = (( Integer ) currentProperty . get ( key )). intValue () ;
i f ( currentProperty . isRegistered ( key1 )) {
busy = (( Boolean ) currentProperty . get ( key1 )). booleanValue () ;
i f ( busy ) c o n t i n u e ;
}
i f ( locality <= horizon ) {
// also the nodes of the lower locality should be considered ,
therefore <=
nodeSetHorizon . add ( currentNode );
}
}
}
}
}
}
2005-03-21/015/IN99/2253
73
7. Implementierung
r e t u r n nodeSetHorizon ;
135
136
}
7.3.2.2. Aktiver Teil
Die Klasse SimpleNetLocalisation aktualisiert die Informationen über vorhandene
Sessions aller im Node Roster
diese
Session
bekannten Knoten. Dabei wird nicht berücksichtigt, ob
benötigt wird. Eine
Session
stellt zur Zeit nur eine Zusammenfassung
mehrerer einzelner Streams dar (z. B. Audio und Video), die zeitgleich abgespielt werden müssen. Jeder Knoten hat hierbei nur einen bestimmten Teil in seinem lokalem
Puer. Dies kann anhand von relativen Zeiten (StreamTimes) bestimmt werden. Da
der
Scheduler
mehrere Knoten als Quellen wählen kann, ist es sehr wichtig zu wissen,
welche Zeitpunkte bei jedem Knoten im Puer vorhanden sind. Diese Informationen
werden direkt bei jedem
Node-Objekt gespeichert, sodass der Scheduler
einfach auf die
Informationen zugreifen kann.
155
156
157
158
159
160
161
162
163
164
165
p r o t e c t e d v o i d receivedLocateSessionResult ( LocateSessionResult msg ) {
Vector dataVec = msg . getData () ;
// msg . getRequestID () ; // FIXME requestID
Log . debug ( t h i s , " Received a LocateSessionResultMessage ");
i f ( nodeRoster . isLocal ( msg . getRequestNodeId () )) {
Iterator dataVecIt = dataVec . iterator () ;
w h i l e ( dataVecIt . hasNext () ) {
NodeInfo info = ( NodeInfo ) dataVecIt . next () ;
l o n g rcvTime = System . currentTimeMillis () - info . getAgeOfNodeInfo () ; // FIXME
take real rcvTime !
Node node = nodeRoster . get ( info . getNodeId () );
updateNodeProperty ( info . getData () , node , rcvTime , info . isBusy () );
166
}
167
}
168
169
}
Die Bandbreite gehört ebenfalls zu den wichtigen Informationen eines Knotens. Diese
kann allerdings nicht übertragen werden, sondern muss für jeden Knoten separat gemessen werden. Die Messung wird mit Hilfe des
die
271
Sessions
Routings nur zu Knoten vorgenommen,
anbieten.
// measure bandwidth only if some NodeInfo known
i f ( prop . isRegistered ( NODEPROP_Bandwidth )) {
i f ( currentTime > UPDATETIME_Bandwidth
312
313
314
74
2005-03-21/015/IN99/2253
7.3. Lokalisierung
+ (( Long ) prop . get ( NODEPROP_BandwidthTime )) . longValue () ) {
// if bandwidth value too old => request a new bandwidth measurement
315
316
BandwidthRequest bwMessage = new BandwidthRequest ( node . getId () ,
getMessenger () );
bwMessenger . fireMessage ( bwMessage );
318
319
}
} else {
320
321
BandwidthRequest bwMessage = new BandwidthRequest ( node . getId () ,
getMessenger () );
bwMessenger . fireMessage ( bwMessage );
323
324
}
325
Nachdem die Bandbreite gemessen wurde, erhält die
Lokalisierung eine BandwidthResult-
Nachricht.
222
223
s u p e r . messageReceived ( message );
224
225
i f ( message i n s t a n c e o f BandwidthResult ) {
226
227
BandwidthResult resultMsg = ( BandwidthResult ) message ;
NodeId nodeId = resultMsg . getNodeId () ;
l o n g measureTime = resultMsg . getMeasureTime () ;
i n t measuredBW = resultMsg . getBandwidth () ;
228
229
230
231
property . put ( NODEPROP_Bandwidth , new Integer ( measuredBW ));
property . put ( NODEPROP_BandwidthTime , new Long ( measureTime )) ;
243
244
Die regelmäÿige Aktualisierung dieser Informationen erfolgt in der
bestimmten Zeitabständen wird dabei jedem Knoten eine
update-Methode. In
GetNodeInfo-Nachricht
ge-
schickt. Hat dieser Knoten nach einer doppelt so langen Zeit nicht geantwortet, werden
seine Informationen gelöscht, da sie vermutlich ungültig sind.
271
i f ( currentTime > UPDATETIME_RemoteNode
+ (( Long ) prop . get ( NODEPROP_Sessions_RcvTime )). longValue () ) {
// info is too old => request new
requestNodeInfo ( node ) ;
300
301
302
303
Damit die lokalen Informationen einem anderen Knoten gesendet werden können, müssen sie regelmäÿig von
4
Buer
und
Admission Control 4
abgefragt werden.
Das Admission Control beantwortet dabei nur die Frage, ob generell noch ausgehende Verbindungen
zu anderen Knoten zugelassen werden.
2005-03-21/015/IN99/2253
75
7. Implementierung
355
356
357
p r o t e c t e d v o i d updateLocalInfo () {
Vector data = new Vector () ;
l o n g aktTime = System . currentTimeMillis () ;
Iterator sessionIt = buffer . sessions () . iterator () ;
w h i l e ( sessionIt . hasNext () ){
Stream session = ( Stream ) sessionIt . next () ;
i f ( session != n u l l ) {
// Search for the StreamInfos
Vector sessionData = new Vector (2) ; // 0 = session , 1 = Vector of
SessionInfo
Vector streamVector = new Vector () ;
sessionData . add (0 , session );
SessionInfo sessionInfo = buffer . getSessionInfo ( session );
362
363
364
365
366
367
368
369
370
Iterator sessionInfoIt = sessionInfo . streamInfos () . iterator () ;
w h i l e ( sessionInfoIt . hasNext () ) {
StreamInfo streamInfo = ( StreamInfo ) sessionInfoIt . next () ;
i f ( streamInfo != n u l l ){
streamVector . add ( streamInfo );
}
}
sessionData . add (1 , streamVector );
sessionData . add (2 , new Long ( aktTime ) );
data . add ( sessionData );
378
379
380
381
382
383
384
385
386
387
}
}
updateNodeProperty ( data , nodeRoster . localNode () , aktTime , (! admissionControl .
isAcceptingLinks () ));
388
389
390
Da die Anzahl der
Sessions und die Streams einer Session unterschiedlich sein kann,
muss ein dynamisches Format verwendet werden, um diese Informationen an andere Knoten zu senden. Diese Informationen werden dabei in den Datenvektor eines
NodeInfo-Objektes
in folgendem Format gespeichert:
•
der Datenvektor ist ein
•
ein
SessionVektor
•
ein
StreamVektor
ist ein
ist ein
Vector
aus mehreren
Vector
aus einer
Vector
aus
SessionVektoren
Session
und einem
StreamVektor
StreamInfos
7.4. Admission Control
Das
Admission Control
wurde in dem Paket
org.ekstream.admissioncontrol imple-
mentiert.
76
2005-03-21/015/IN99/2253
22 package org . ekstream . admissioncontrol ;
Die Schnittstellen sind in der abstrakten Klasse AdmissionControl deniert.
31 p u b l i c
i n t e r f a c e AdmissionControl {
Die wichtigste Methode ist
acceptNewLink
die vom
Link Control
aufgerufen wird,
wenn eine ausgehende Datenverbindung zu einem anderen Knoten erzeugt werden soll.
p u b l i c a b s t r a c t boolean acceptNewLink ( ActivationRequest req ) ;
40
Die
isAcceptingLinks-Methode wird von der Lokalisierung verwendet, um festzustel-
len ob generell noch ausgehende Datenverbindungen zugelassen werden.
p u b l i c a b s t r a c t boolean isAcceptingLinks () ;
48
Da einige Implementierungen des AdmissionControl Informationen zu den schon
vorhandenen Links benötigen, wird der
LinkRoster
in der
setLinkRoster-Methode5
festgelegt.
p u b l i c a b s t r a c t v o i d setLinkRoster ( LinkRoster linkRoster ) ;
56
7.4.2. Statisches Admission Control
Das statische
immer
True
Admission Control
oder immer
False
der StaticAdmissionControl-Klasse gibt entweder
zurück. Dies kann für Tests verwendet werden, wenn
alle ausgehenden Datenverbindungen entweder zugelassen oder nicht zugelassen werden
sollen.
31 p u b l i c
c l a s s StaticAdmissionControl implements AdmissionControl {
32
p r i v a t e boolean accept ;
33
34
p u b l i c StaticAdmissionControl ( boolean accept ) {
t h i s . accept = accept ;
}
35
36
37
5
Das direkte Übergeben des LinkRosters ist nicht möglich, da er erst zu einem späteren Zeitpunkt
erzeugt wird.
2005-03-21/015/IN99/2253
77
7. Implementierung
49
50
51
57
58
59
p u b l i c boolean acceptNewLink ( ActivationRequest req ) {
r e t u r n accept ;
}
p u b l i c boolean isAcceptingLinks () {
r e t u r n accept ;
}
7.4.3. Einfaches Admission Control
Ein einfaches
Admission Control
wurde in der SimpleAdmissionControl-Klasse im-
plementiert.
36 p u b l i c
c l a s s SimpleAdmissionControl implements AdmissionControl {
Dort wird im Konstruktor, beim Erzeugen des Objektes, die maximale Anzahl und die
maximale Bandbreite für alle ausgehende Datenverbindungen festgelegt.
43
44
45
46
p u b l i c SimpleAdmissionControl ( i n t maxBandwidth , i n t maxLinks ) {
t h i s . maxBandwidth = maxBandwidth ;
t h i s . maxLinks = maxLinks ;
}
Dazu werden die Bitraten und die Anzahl aller existierenden ausgehenden Datenverbindungen aufsummiert. Sind beide festgelegten Maximalwerte mit der angeforderten
Datenverbindung noch nicht erreicht, wird sie zugelassen.
71
p u b l i c boolean acceptNewLink ( ActivationRequest req ) {
Iterator it = linkRoster . iterator () ;
w h i l e ( it . hasNext () ) {
Link link = ( Link ) it . next () ;
i f (( link i n s t a n c e o f OutboundLink ) && ( !( link i n s t a n c e o f ExportLink ))) {
OutboundLink olink = ( OutboundLink ) link ;
currentBW -= olink . getNominalBitRate () ;
currentLinks ++;
}
}
78
79
80
81
82
83
84
85
86
87
i f ( currentLinks >= maxLinks ) {
Log . info ( t h i s , " Deny ActivationRequest because maximum of accepted links ( "
+ maxLinks + ") reached ." );
return f a l s e ;
}
88
89
90
91
92
93
i f ( req . getFilter () . getFraction ()
* req . getStream () . getNominalBitRate () > currentBW ) {
94
95
78
2005-03-21/015/IN99/2253
Log . info ( t h i s , " Deny ActivationRequest because not enough available bandwidth ( "
+ currentBW + "). ");
return f a l s e ;
96
97
98
}
99
return true ;
104
105
}
110
p u b l i c boolean isAcceptingLinks () {
i f (( currentBW > 0) &&( currentLinks < maxLinks )) {
return true ;
} else {
return f a l s e ;
}
127
128
129
130
131
132
}
2005-03-21/015/IN99/2253
79
7. Implementierung
80
2005-03-21/015/IN99/2253
8. Test
Der Test der in Kapitel 7 beschriebenen Implementierung eines dynamischen lokalitätsbewussten Routings soll im Folgenden beschrieben werden.
Dabei wurden die Lokalitätsvektoren, die Lernraten und die Schwellen beobachtet, um
festzustellen, wie gut sich die Lokalitätsvektoren an die gemessenen RTTs anpassen
und wie die Knoten in Horizonte eingeteilt werden.
Zuerst wird die Testumgebung im Abschnitt 8.1 beschrieben. Danach folgen eine Erläuterung zum Testablauf (Abschnitt 8.2) und eine Auswertung der Testdaten (Abschnitt 8.3). Die Ergebnisse werden in den Abschnitten 8.4 und 8.5 gezeigt und erläutert.
8.1. Testumgebung
Das lokalitätsbewusste dynamische Routing aus dem Abschnitt 7.2.4 wurde in die Testklasse StreamingTestFullDynamic eingebunden. In Anhang A.10 ist das Vorgehen
zum Ausführen eines Tests beschrieben, sodass hier nur kurz ein Beispielaufruf genannt
wird:
user@eris:~/svn/ekStream/bin$ java \
org/ekstream/test/StreamingTestFullDynamic 20000 5000 2000 zazu:5000
In der Tabelle 8.1 sind die Rechner, die für den Test zur Verfügung standen, mit dem
1
jeweiligen Standort, dem Autonomen System
zum Knoten
zazu
und den mittels
ping gemessenen RTTs
aufgelistet. Die Zusammenhänge der Autonomen Systeme wurden
in der Abbildung 8.1 dargestellt.
1 http://www.fixedorbit.com
2005-03-21/015/IN99/2253
81
8. Test
*.tu-ilmenau.de
wotan.imb-jena.de
RIPE-ASNBLOCK-679
680
REACH
4637
KPN
286
ilmhost.de
HETZNER-AS
24940
TDC
3292
synchronity.de
CW
1273
ABOVENET
6461
TISCALI-BACKBONE
3257
HOSTEUROPE-AS
20773
TELIANET
1299
DTAG
3320
TISCALI-DE
12312
invalid147.dyndns.org
slipstream.milon.de
starburst.milon.de
orion.ilmenau.net
Abbildung 8.1.: Graph über die Verbindungen der Autonomen Systeme
Da dies vor allem ein Test für das Routing und die Bestimmung der Lokalität war,
wurde auf die Verwendung von Streaming-Daten verzichtet. Auf diese Art konnten
auch die Ressourcen der externen Rechner geschont werden, die für den Zeitraum des
Tests zur Verfügung gestellt wurden.
82
2005-03-21/015/IN99/2253
2005-03-21/015/IN99/2253
macheiss.prakinf.tu-ilmenau.de
diana.prakinf.tu-ilmenau.de
eris.prakinf.tu-ilmenau.de
telpc1.prakinf.tu-ilmenau.de
telcp3.prakinf.tu-ilmenau.de
vsbslab1.prakinf.tu-ilmenau.de
wotan.imb-jena.de
synchronity.de
ilmhost.de
slipstream.milon.de
starburst.milon.de
invalid147.dyndns.org
orion.ilmenau.net
mach
dian
eris
tel1
tel2
tel3
tel4
vsb1
vsb2
vsb3
vsb4
vsb5
vsb6
xWot
xAnd
xIlm
xSli
xSta
xKri
xOri
Ilmenau
Berlin
Köln
Köln
Nürnberg
Nürnberg
Uni-Jena
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
TU-Ilmenau
Standort
DTAG
TISCALI-DE
HOSTEUROPE-AS
HOSTEUROPE-AS
HETZNER-AS
HETZNER-AS
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
RIPE-ASNBLOCK-679
Autonomes System
Tabelle 8.1.: Daten zu den Testknoten
zazu.prakinf.tu-ilmenau.de
Domain
zazu
Kurzname
zu
10ms
75ms
13ms
13ms
13ms
14ms
3ms
0ms
0ms
0ms
0ms
0ms
0ms
0ms
0ms
0ms
0ms
0ms
0ms
0ms
-
RT Tmeas
zazu
8.1. Testumgebung
83
8. Test
8.2. Verlauf des Tests
Für den Test wurde das Routing jedes Knotens immer auf den Port 5000 eingestellt.
Dadurch war die
NodeId
jedes Knotens, ermittelt aus der IP-Adresse und dem Port,
immer dieselbe.
Der gesamte Test dauerte mehrere Stunden, wobei die Messwerte jedes Knotens in
Logdateien geschrieben wurden.
Um die Dynamik des Netzwerkes zu simulieren, wurden verschiedene Knoten ab und
zu aus dem Netz genommen und wieder hinzugefügt.
Mit der freundlichen Unterstützung verschiedener Betreiber von Rechnern im Internet,
konnte ein deutschlandweiter Test durchgeführt werden.
Die Auswertung der Testergebnisse wurde anhand der Logdateien im folgenden Abschnitt 8.3 vorgenommen.
8.3. Auswertung der Logdateien
Die erzeugten Logdateien umfassten ungepackt 728 Megabytes. Ein kleiner Ausschnitt
einer Logdatei ist im Anhang A.9 zu sehen.
Eine erste Übersicht über alle Logdateien wurde in
Anhang A.1). Dabei wurden der Dateiname, die
uebersicht.txt
erstellt (siehe
NodeId, die IP-Adresse und die Zeiten
der Logdatei zusammengefasst.
Da die Systemzeiten der Knoten nicht synchronisiert waren, musste dies nachträglich
in den Logdateien getan werden. Dafür wurde der Umstand verwendet, dass ein Lokalitätsvektor erst bei einem Knoten empfangen werden kann, wenn er zuvor vom anderen
Knoten berechnet wurde. Das Perl-Skript
makeDiffLog.pl (Anhang A.3) wurde dafür
implementiert. Es gibt alle Zeilen zweier Dateien sortiert nach der Zeit aus. Zusätzlich
kann für die Zeiten der zweiten Datei eine Dierenz angegeben werden. Damit kann
dann eine zuvor bestimmte Zeitdierenz relativ einfach überprüft werden.
Zusätzlich dazu wurde ein weiteres Perl-Skript (searchSyncTime.pl im Anhang A.4)
erstellt, welches versucht die Zeitdierenz zu bestimmen.
84
2005-03-21/015/IN99/2253
8.4. Ergebnisse des Tests
Die bestimmten Zeitdierenzen wurden in die Datei
filesdata.dat (siehe Anhang A.2)
zu den jeweiligen Logdateien eingetragen.
Nun wurden die wichtigen Daten aus den vielen Logdateien mit dem
makeOneLog.pl-
Skript (siehe Anhang A.5) extrahiert und in einer Logdatei zusammengefasst.
Da für die Auswertung allerdings nicht immer alle Daten gleichzeitig benötigt wurden,
erstellte das
splitOneLog.pl-Skript
(siehe Anhang A.6) viele Logdateien mit allen
Kombinationsmöglichkeiten aus gewünschter Information und Knoten (von dem die
Information stammt).
Nun wurden die Lokalitätsvektoren eines Zeitpunktes (55000) genommen und in einer
separaten Datei gespeichert. Diese Lokalitätsvektoren sind in Tabelle 8.2 zu sehen.
Dann wurden mit Hilfe des
calc.pl-Skriptes
(siehe Anhang A.7) die Abstände der
Lokalitätsvektoren untereinander berechnet. In der Tabelle 8.3 ist das Ergebnis der
Berechnung zu sehen.
Um den zeitlichen Verlauf des Abstandes zweier Knoten untereinander darstellen zu
können, wurde das
calcDist2.pl-Skript
(siehe Anhang A.8) implementiert.
Das Endstadium des Lernvorganges einiger Knoten (siehe Tabelle 8.2) ist in der Tabelle 8.3 zu sehen. Die Dimension
D
war fünf. Zur Verdeutlichung wurden die Zahlen
für kleine Abstände grün und für groÿe Abstände rot gefärbt. Die Rechner, die sich
im gleichen Autonomen System (siehe Tabelle 8.1 und Abbildung 8.1) benden, haben
erwartungsgemäÿ auch einen kleinen Abstand zueinander.
Ebenso ist zu erkennen, das eine reale Lokalität anhand von geographischen Entfernungen nicht verwendet werden kann. Der Knoten
xOri
bendet sich in derselben Stadt
(Ilmenau) nicht mehr als einen Kilometer von den Rechnern der TU-Ilmenau (vsb1-
vsb6 und dian) entfernt. Die Netzwerkpakete müssen allerdings noch über verschiedene
Autonome Systeme übertragen werden und gelangen erst dann wieder in das Netzwerk
der TU-Ilmenau. So hat der Knoten
xWot
an der Universität Jena eine viel geringe-
re Latenz, da er sich im gleichen Autonomen System im Deutschen Forschungsnetz
2
2 http://www.dfn.de
2005-03-21/015/IN99/2253
85
8. Test
x1
x2
x3
x4
x5
vsb1
-2.52
-25.59
-1.37
30.39
20.37
vsb2
-2.56
-25.62
-1.30
30.29
20.27
vsb3
-2.58
-25.79
-1.48
30.72
20.08
vsb4
-2.44
-24.67
-0.43
28.15
20.98
vsb6
-2.70
-25.93
-1.73
31.16
19.92
xIlm
-9.65
-27.19
2.32
22.54
11.96
xOri
-3.12
-30.20
-5.65
40.90
16.31
xWot
-0.68
-25.35
-1.22
31.01
19.64
xAnd
-9.48
-27.15
1.98
23.33
12.01
xSli
-10.34
-19.14
-8.98
31.03
24.01
xKri
5.64
6.02
-50.23
-9.21
52.45
dian
-2.55
-25.27
-0.88
29.34
20.41
Knoten
Tabelle 8.2.: Auistung der Lokalitätsvektoren für die Abstände in Tabelle 8.3
(DFN) bendet.
Die Abstände zwischen den Lokalitätsvektoren entsprachen auch ca. der gemessenen
RTT mit Hilfe von
ping.
Alle Zeiten, vom Knoten
zazu
aus gemessen, sind in der
Tabelle 8.1 zu sehen. Zusätzlich dazu waren die Zeiten zwischen Knoten
xAnd
86
ca. 15ms und zwischen Knoten
xKri
und
xAnd
xWot
und
ca. 75ms.
2005-03-21/015/IN99/2253
0.17
0.50
2.67
1.04
1.19
2.10
12.92
14.12
13.48
13.20
77.78
vsb2
vsb3
vsb4
vsb6
dian
xWot
xOri
xIlm
xAnd
xSli
xKri
vsb1
vsb1
Knoten
2005-03-21/015/IN99/2253
78.08
13.27
13.47
14.12
12.45
2.04
1.62
0.56
3.13
0.53
0.50
vsb3
76.63
13.55
12.86
13.37
15.58
3.76
1.53
3.68
3.13
2.60
2.67
vsb4
78.29
13.18
13.61
14.29
11.90
2.19
2.17
3.68
0.56
1.09
1.04
vsb6
77.42
13.41
12.90
13.49
14.06
2.64
2.17
1.53
1.62
1.10
1.19
dian
78.22
14.53
14.43
15.08
12.57
2.64
2.19
3.76
2.04
2.13
2.10
xWot
84.81
18.50
20.86
21.71
12.57
14.06
11.90
15.58
12.45
12.98
12.92
xOri
82.13
20.26
0.88
21.71
15.08
13.49
14.29
13.37
14.12
13.96
14.12
xIlm
82.15
19.71
0.88
20.86
14.43
12.90
13.61
12.86
13.47
13.32
13.48
xAnd
Tabelle 8.3.: Abstände der Lokalitätsvektoren in der Tabelle 8.2
77.83
13.27
13.32
13.96
12.98
2.13
1.10
1.09
2.60
0.53
0.17
vsb2
70.83
19.71
20.26
18.50
14.53
13.41
13.18
13.55
13.27
13.27
13.20
xSli
70.83
82.15
82.13
84.81
78.22
77.42
78.29
76.63
78.08
77.83
77.78
xKri
87
8. Test
Im Folgenden werden anhand der Testdaten der Knoten
xWot, xAnd
und
xKri
einige
Diagramme erstellt. In der Abbildung 8.2 ist der zeitliche Verlauf der Lokalitätsvektoren
zu sehen. Dargestellt ist der Abstand des Vektors zum Null-Vektor, der dem Betrag
des Vektors entspricht.
300
Betrag des Vektors von xWot
Betrag des Vektors von xAnd
Betrag des Vektors von xKri
250
Betrag
200
150
100
50
0
47000
48000
49000
50000
51000
52000
53000
54000
55000
56000
57000
Zeit
Abbildung 8.2.: Beträge dreier Beispiel-Lokalitätsvektoren
In der Abbildung 8.3 sind die Abstände der Lokalitätsvektoren untereinander dargestellt. Die anfangs zufällig gewählten Lokalitätsvektoren haben einen groÿen Abstand
zueinander und änderten sich stark. Nach einer kurzen Zeit erreichten die Lokalitätsvektoren einen relativ stabilen Wert und änderten sich nur noch wenig.
Nachdem die Lernrate
δ
anfangs groÿ war, ist sie sehr schnell kleiner geworden (siehe
Abbildung 8.4).
Der kleine unruhige Bereich in diesen drei Abbildungen (jeweils an der Stelle 50000)
ist der Zeitraum, in dem besonders viel Dynamik im Netzwerk simuliert wurde. Da an
diesen Stellen viele komplett neu berechnete Lokalitätsvektoren hinzugekommen sind,
die zufällig weit entfernt waren, veränderten sich auch die stabilen Lokalitätsvektoren
ein wenig. Allerdings war diese Veränderung nicht stark und wurde dann auch zurückgenommen, wie dies besonders in der Abbildung 8.2 zu sehen ist.
88
2005-03-21/015/IN99/2253
250
Abstand zwischen xWot und xAnd
Abstand zwischen xWot und xKri
Abstand zwischen xAnd und xKri
200
Abstand
150
100
50
0
49000
50000
51000
52000
53000
54000
55000
56000
57000
Zeit
Abbildung 8.3.: Abstände dreier Beispiel-Lokalitätsvektoren untereinander
0.3
Lernrate von xAnd
Lernrate von xWot
Lernrate von xKri
0.25
Lernrate
0.2
0.15
0.1
0.05
47000
48000
49000
50000
51000
52000
Zeit
53000
54000
55000
56000
57000
Abbildung 8.4.: Lernrate der drei Beispielknoten
2005-03-21/015/IN99/2253
89
8. Test
Durch eine Firewall beim Knoten
xKri
war es nur möglich die RTT von
xKri
aus zu
anderen Knoten zu messen, jedoch nicht umgekehrt. Trotzdem sind die Lokalitätsvektoren nach einiger Zeit bei korrekten Werten angekommen.
In der Abbildung 8.5 ist die Veränderung eines Schwellwertes dargestellt. Bei allen
Knoten waren genug lokale Knoten vorhanden, sodass die Schwelle wie beim Knoten
xWot
auf den minimalen Wert von 50 eingestellt wurde. Bei Knoten
xKri
waren die
Entfernungen zu allen Knoten groÿ. Anfangs waren daher für ihn alle anderen Knoten
im erweiterten Horizont. Da der Knoten
xKri
allerdings auch einige
lokale
und
globale
Knoten kennen wollte, versuchte er die Schwellwerte anzupassen. Der Schwellwert für
lokale
Knoten müsste nach oben angepasst werden, allerdings befand sich dieser an-
fangs schon auf den maximalen Wert von 50. Für die Einteilung der Knoten in den
erweiterten
und
globalen
Horizont konnte allerdings der Schwellwert verringert werden
und schwankte so zwischen einem Wert, an dem sich einige Knoten im
einige im
erweiterten
globalen
und
Horizont befanden.
200
Schwelle des erweiterten Horizontes von xWot
Schwelle des erweiterten Horizontes von xKri
180
160
Schwellwert
140
120
100
80
60
40
47000
48000
49000
50000
51000
52000
Zeit
53000
54000
55000
56000
57000
Abbildung 8.5.: Darstellung der Schwelle für die Einordnung der Knoten in den
terten
90
erwei-
Horizont
2005-03-21/015/IN99/2253
8.5. Auswertung und Ausblick
8.5. Auswertung und Ausblick
Der Test hat gezeigt, dass es möglich ist, Lokalität anhand von virtuellen Koordinaten
zu bestimmen. Korrekte Koordinaten wurden relativ schnell erreicht und blieben auch
stabil. So müssen diese Lokalitätsvektoren nicht zu oft ausgetauscht werden.
Nun kann in einem weiteren sehr ausführlichen Test versucht werden, verschiedene
Parameter zu optimieren, um die Ezienz weiter zu erhöhen. Ebenso ist ein Test mit
sich bewegenden Knoten in einem Funknetz notwendig. Zu optimierende Parameter
sind:
Lernrate δ:
Dazu gehören der maximale und der minimale Wert für
δ . Auÿerdem kann
auch der Zeitpunkt und die Art der Anpassung der Lernrate verändert werden.
Es sollte beachtet werden, dass ein kleiner Fehler bei einer kleinen Entfernung
eine gröÿeren Einuss besitzt, als bei einer groÿen Entfernung. Daher müsste der
Fehler relativ zur Entfernung bezogen werden. Auf welche Art und Weise dieser
relative Fehler und daraus die Änderung der Lernrate
δ
anders berechnet werden
kann, sollte noch genauer untersucht werden.
Aktualisierungsdauer τ :
Zur Zeit wird
τ
schrittweise bis zu einem Maximalwert er-
höht. Es ist aber auch möglich, sie ebenso wie die Lernrate wieder verringern zu
können. Auch kann die Schrittweite der Erhöhung und der Maximalwert verändert werden.
Dimension der Lokalitätsvektoren D:
Die Genauigkeit der Abstandsberechnungen
wird durch die Dimension der Lokalitätsvektoren bestimmt. Dabei steigt mit
D
die Genauigkeit und der Berechnungsaufwand. Während jedoch der Berechnungsaufwand linear mit
D
D
D≤2
ab. Dimensionen
Schwellen und Horizonte:
steigt, nimmt der Zuwachs der Genauigkeit mit höherem
sind nicht geeignet (siehe [Ng und Zhang (2001)]).
Es ist möglich, mehr als drei Horizonte zu verwenden, um
Knoten besser einteilen zu können. Die Anpassung der Schwellwerte und der
maximalen und minimalen Werte für eine Schwelle kann ebenso noch optimiert
werden.
2005-03-21/015/IN99/2253
91
8. Test
92
2005-03-21/015/IN99/2253
9. Schlussbemerkung
Die Implementierung eines ezienten Routings erfolgte mit Hilfe von Lokalitätsbetrachtungen der Knoten. Dabei wurden dezentral berechnete virtuelle Koordinaten verwendet, deren Abstände der
Round Trip Time
entsprechen.
9.1. Bewertung und Ausblick
Ein Test der Berechnung zeigte, dass die Verwendung von virtuellen Koordinaten gut
geeignet ist, um die Lokalitäten zu berechnen. Allerdings sind mehrere Parameter vorhanden, mit deren Hilfe die Ezienz weiter erhöht werden kann. Diese Parameter sind
vor allem die Lernrate
δ,
die Aktualisierungszeit
τ,
die Dimension
D
der Lokalitäts-
vektoren und die Schwellen für die Horizonte (siehe Abschnitte 6.2.2 und 8.5). Dabei
können nicht nur die Werte der Parameter verändert werden, auch existiert eine Vielzahl an Möglichkeiten diese Werte dynamisch anzupassen. Zum Beispiel ist es unter
Umständen nicht notwendig, die Lernrate anhand des relativen Fehlers zu berechnen,
sondern die Verwendung des absoluten Fehlers
ε
ist ausreichend.
Dem Lokalitätsvektor könnte noch ein Stabilitätswert hinzugefügt werden, sodass ein
stabiler Lokalitätsvektor nicht so oft aktualisiert werden muss. Um den eigenen Lokalitätsvektor zu verbessern, besteht die Möglichkeit dann die Messungen der
Times
Round Trip
bevorzugt zu Knoten mit stabilen Lokalitätsvektoren vorzunehmen.
Mit Hilfe der Lokalitätsvektoren können auch die Abstände von zwei beliebigen Knoten
bestimmt werden und so bei der Routingentscheidung verwendet werden, wenn die
Pakete nicht direkt versendet werden sollen.
Das implementierte Routing ist in der Lage dynamisch Knoten kennen zu lernen. Allerdings kann es nur den Eintrag für einen Knoten wieder löschen, wenn der andere
Knoten eine längere Zeit nicht mehr antwortet. Denkbar wären auch Methoden, die
2005-03-21/015/IN99/2253
93
9. Schlussbemerkung
bei einer zu groÿen Menge an bekannten Knoten einige wieder austragen. Dazu muss
untersucht werden, ob andere Komponenten, auÿer dem Routing, diese Knoten noch
benötigen.
In dieser Diplomarbeit wurde ein vollständig dezentrales Routing implementiert, welches eine hohe Ausfallsicherheit besitzt. Allerdings können auch weitere Routingstrategien untersucht werden, die beispielsweise lokale Cluster aufbauen und lokale
nodes
Super-
wählen. Eine solche Strategie wird derzeit im Rahmen einer Studienjahresarbeit
näher untersucht.
Für die Lokalisierung können die in Abschnitt 6.4 vorgestellten Ideen weiter untersucht
und implementiert werden.
Weiterführend existieren zwei Studienjahresarbeiten, die sich mit dem
trol
Admission Con-
und der Firewall-Problematik beschäftigen.
9.2. Zusammenfassung
Das Ziel dieser Diplomarbeit war die Entwicklung eines ezienten Routings für kooperative Multimedia-Streaming-Systeme.
Die Ezienz wurde mit der Berücksichtigung der Lokalität erreicht und als Lokalitäts-
Round Trip Time ) verwendet.
kriterium die Netzwerklatenz (
Damit die Latenz nicht von jedem Knoten jedes Mal berechnet werden muss, wurden
virtuelle Koordinaten eingeführt. Jeder Knoten besitzt und berechnet seine eigene virtuelle Koordinate und kennt die Koordinaten der anderen Knoten. Die Koordinaten
werden so berechnet, dass die Abstände der Koordinaten zweier Knoten der
Trip Time
Round
zwischen ihnen entsprechen.
Diese dezentrale Lokalitätsberechnung ist mit einem dynamischen Routing in das Multimedia-Streaming-System
ekStream
integriert worden. Ebenso wurde eine einfache Me-
thode für die Lokalisierung implementiert, damit das System komplett getestet werden
konnte.
94
2005-03-21/015/IN99/2253
Banerjee, S. ; Bhattacharjee, B.:
[Banerjee und Bhattacharjee 2002]
A compar-
ative study of application layer multicast protocols. 2002. URL: http://citeseer.
ist.psu.edu/banerjee01comparative.html
Banerjee, Sujata ; Xu, Zhichen ; Lee, Sung-Ju ; Tang, Chun-
[Banerjee u. a. 2003]
qiang:
Service Adaptive Multicast for Media Distribution Networks.
2003. URL:
http://citeseer.ist.psu.edu/banerjee03service.html
Castro, M. ; Druschel, P. ; Kermarrec, A. ; Nandi,
[Castro u. a. 2003]
A. ; Rowstron, A. ; Singh, A.:
erative environments.
2003. Splitstream: High-bandwidth multicast in coop-
URL:
http://citeseer.ist.psu.edu/article/
castro03splitstream.html
[Castro u. a. 2002]
Castro, M. ; Druschel, P. ; Kermarrec, A. ; Rowstron, A.:
SCRIBE: A large-scale and decentralized application-level multicast infrastructure.
In:
IEEE Journal on Selected Areas in communications (JSAC)
Bd. 20, Oktober
2002, S. 14891499. Special issue on network support for multicast communication.
[Chawathe 2003]
framework. In:
[Chu u. a. 2002]
Hui:
Chawathe, Yatin: Scattercast: an adaptable broadcast distribution
Multimedia Syst.
9 (2003), Nr. 1, S. 104118. ISSN 0942-4962
Chu, Yang-hua ; Rao, Sanjay G. ; Seshan, Srinivasan ; Zhang,
A case for end system multicast.
in Communications
Bd. 20, URL:
JSAC.CaseForESM.2002.pdf,
2005-03-21/015/IN99/2253
In:
IEEE Journal on Selected Areas
http://esm.cs.cmu.edu/technology/papers/
October 2002, S. 14561471
95
[Cox u. a. 2003]
Cox, R. ; Dabek, F. ; Kaashoek, F. ; Li, J. ; Morris, R.:
Distributed Network Coordinates.
2003. URL:
Practical
http://citeseer.ist.psu.edu/
article/cox03practical.html
Cui, Yi ; Nahrstedt, Klara: Layered peer-to-peer stream-
[Cui und Nahrstedt 2003]
NOSSDAV '03: Proceedings of the 13th international workshop on Network
and operating systems support for digital audio and video, ACM Press, 2003, S. 162
ing. In:
171. ISBN 1-58113-694-3
[Deshpande u. a. 2002]
Hector:
Deshpande, Hrishikesh ; Bawa, Mayank ; Garcia-Molina,
Streaming Live Media over Peers. 2002. URL: http://dbpubs.stanford.
edu:8090/pub/2002-21.
[Goyal 2001]
Zugrisdatum: 15.01.2005
Goyal, Vivek K.: Multiple Description Coding: Compression Meets
the Network. In:
IEEE Signal Processing Magazine Bd. 18, September 2001, S. 7493
Ezientes Multimedia Streaming auf Basis eines semi-dezentralisierten P2P-Netzwerks, Technische Universität Ilmenau, Di-
[Heidenreich 2004]
Heidenreich, Ronny:
plomarbeit, 2004
[Krüger und Reschke 2004]
Krüger, Gerhard ; Reschke, Dietrich:
Übungsbuch Telematik - Netze, Dienste, Protokolle.
3. Auage.
Lehr- und
Fachbuchverlag
Leipzig, 2004
Kodierverfahren für die verteilte Übertragung QoSsensitiver Datenströme über hochdynamische Netzwerke, Technische Universität Il-
[Kärst 2004]
Kärst, Holger:
menau, Diplomarbeit, 2004
[Lv u. a. 2002]
Lv, Qin ; Cao, Pei ; Cohen, Edith ; Li, Kai ; Shenker, Scott: Search
and replication in unstructured peer-to-peer networks. In:
the 16th international conference on Supercomputing.
ICS '02: Proceedings of
New York, NY, USA : ACM
Press, 2002, S. 8495. ISBN 1-58113-483-5
[Ng und Zhang 2001]
Ng, E. ; Zhang, H.:
with coordiantes-based approaches.
Predicting Internet network distance
2001. URL:
article/ng02predicting.html
96
2005-03-21/015/IN99/2253
Padmanabhan, V. ; Chou, P. ; Wang, H.: Resilient
[Padmanabhan u. a. 2003]
peer-to-peer streaming
/ Microsoft Research.
URL:
edu/padmanabhan03resilient.html, März 2003
http://citeseer.ist.psu.
(MSR-TR-2003-11). Forschungs-
bericht
Padmanabhan, Venkata N. ; Wang, Helen J. ; Chou,
[Padmanabhan u. a. 2002]
Philip A. ; Sripanidkulchai, Kunwadee:
Distributing streaming media content
NOSSDAV '02: Proceedings of the 12th international workshop on Network and operating systems support for digital audio and
video, ACM Press, 2002, S. 177186. ISBN 1-58113-512-2
using cooperative networking. In:
[Ratnasamy u. a. 2001]
Ratnasamy, Sylvia ; Francis, Paul ; Handley, Mark ;
Karp, Richard ; Shenker, Scott: A Scalable Content Addressable Network. Berkeley, CA, 2001 (TR-00-010). Forschungsbericht. URL:
http://citeseer.ist.
psu.edu/ratnasamy01scalable.html
Waitzman, D. ; Partridge, C.:
[RFC 1075 1988]
ing Protocol.
November 1988. URL:
http://www.faqs.org/rfcs/rfc1075.html
Handley, M. ; Jacobson, V.:
[RFC 2327 1998]
April 1998. URL:
[RFC 2663 1999]
Distance Vector Multicast Rout-
SDP: Session Description Protocol.
http://www.faqs.org/rfcs/rfc2327.html
Srisuresh, P. ; Holdrege, M.:
(NAT) Terminology and Considerations.
IP Network Address Translator
August 1999. URL:
http://www.faqs.
org/rfcs/rfc2663.html
[Ritter 2001]
URL:
Ritter, Jordan:
Why Gnutella Can't Scale. No, Really.
http://www.dakridge.com/~jpr5/doc/gnutella.html.
2001.
Zugrisdatum:
20.05.2005
[Roca und El-Sayed 2001]
Roca, Vincent ; El-Sayed, Ayman: A Host-Based Mul-
ticast (HBM) Solution for Group Communications. In:
ICN '01: Proceedings of the
First International Conference on Networking-Part 1, Springer-Verlag, 2001, S. 610
619. ISBN 3-540-42302-8
[Rowstron und Druschel 2001]
Rowstron, Antony I. T. ; Druschel, Peter: Pastry:
Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer
2005-03-21/015/IN99/2253
97
Middleware 2001: Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, Springer-Verlag, 2001, S. 329350.
Systems. In:
ISBN 3-540-42800-3
[Strufe 2003]
Strufe, Thorsten:
Klassikation von Namens- und Lokalisierungs-
diensten in dezentralen verteilten Systemen / Technische Universität Ilmenau. URL:
http://www.tu-ilmenau.de/site/telematik/fileadmin/template/startIA/
telematik/Mitarbeiter/strufe/strufe03klassifikation.pdf.
Zugrisda-
tum: 08.06.2005, 2003. Forschungsbericht. 9. Workshop 'Multimedia Informationsund Kommunikationssysteme (MIK)' im Rahmen der net.objectdays 2003, Erfurt,
24.9.2003, S. 322-335
[Strufe 2004]
Strufe, Thorsten:
IlmStream: Ecient Multimedia Streaming
in decentralised distributed systems
/ Technische Universität Ilmenau.
URL:
http://www.tu-ilmenau.de/site/telematik/fileadmin/template/startIA/
telematik/Mitarbeiter/strufe/Strufe04IlmStream.pdf.
Zugrisdatum:
08.06.2005, 2004. Forschungsbericht. 4th International Forum on Multimedia and
Image Processing (IFMIP) at the World Automation Congress 2004
[Tran u. a. 2003a]
Tran, D. ; Hua, K. ; Do, T.:
peer scheme for media streaming.
2003. URL:
Zigzag: An ecient peer-to-
tran03zigzag.html
[Tran u. a. 2003b]
Tran, Duc A. ; Hua, Kien ; Do, Tai:
chitecture for Media Streaming.
2003. URL:
A Peer-to-Peer Ar-
tran03peertopeer.html
[Weber
2004]
Weber, Kai:
Ezientes kooperatives Multimedia-Streaming in
Overlay-Netzen, Technische Universität Ilmenau, Diplomarbeit, 2004
98
2005-03-21/015/IN99/2253
3.1.
Übertragung mittels Unicast, IP-Multicast und Overlay-Multicast
. . .
14
3.2.
Topologieformen für das Overlay-Netz . . . . . . . . . . . . . . . . . . .
16
3.3.
Einuss der Lokalität auf die Netzwerk-Ezienz des Overlay-Netzwerks
17
4.1.
Zigzag -Struktur [Tran u. a. (2003b)]
31
6.1.
Berechnung des neuen Lokalitätsvektors.
7.1.
ekStream -Architektur
7.2.
Klassendiagram für die Routingklassen
. . . . . . . . . . . . . . . . . .
51
7.3.
Kennenlernen von Knoten C . . . . . . . . . . . . . . . . . . . . . . . .
59
8.1.
Graph über die Verbindungen der Autonomen Systeme
. . . . . . . . .
82
8.2.
Beträge dreier Beispiel-Lokalitätsvektoren
. . . . . . . . . . . . . . . .
88
8.3.
Abstände dreier Beispiel-Lokalitätsvektoren untereinander
. . . . . . .
89
8.4.
Lernrate der drei Beispielknoten . . . . . . . . . . . . . . . . . . . . . .
89
8.5.
Darstellung der Schwelle für die Einordnung der Knoten in den
terten
Horizont
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
43
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
erwei-
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2005-03-21/015/IN99/2253
90
99
100
2005-03-21/015/IN99/2253
Tabellenverzeichnis
6.1.
Verwendete Variablen für die Lokalitätsberechnung
. . . . . . . . . . .
42
8.1.
Daten zu den Testknoten . . . . . . . . . . . . . . . . . . . . . . . . . .
83
8.2.
Auistung der Lokalitätsvektoren für die Abstände in Tabelle 8.3
. . .
86
8.3.
Abstände der Lokalitätsvektoren in der Tabelle 8.2
. . . . . . . . . . .
87
2005-03-21/015/IN99/2253
101
Tabellenverzeichnis
102
2005-03-21/015/IN99/2253
ADSL . . . . . . . . .
Asymmetric Digital Subscriber Line
CDN . . . . . . . . . .
Content Distribution Network
DFN . . . . . . . . . .
Deutsches Forschungsnetz
DHT . . . . . . . . . .
Distributed Hash Table
DoS . . . . . . . . . . .
Denial of Service
DVMRP . . . . . . . Distance Vector Multicast Routing Protocol
ESM . . . . . . . . . .
GNP . . . . . . . . . .
Global Network Positioning
HBM . . . . . . . . . . Host-Based Multicast
LAN . . . . . . . . . .
Local Area Network
MDC . . . . . . . . . . Multiple Description Coding
NAT . . . . . . . . . .
Network Address Translator
P2P . . . . . . . . . . .
Peer-to-Peer
RTT . . . . . . . . . .
Round Trip Time
SAM . . . . . . . . . .
Service Adaptive Multicast
SDP . . . . . . . . . . . Session Description Protocol
TTL . . . . . . . . . . . Time To Live
2005-03-21/015/IN99/2253
103
104
2005-03-21/015/IN99/2253
Thesen
1. Kooperatives Multimedia-Streaming eignet sich gut für eine hohe Knotenanzahl,
da die ursprüngliche Quelle entlastet werden kann.
2. Lokalitätserhaltende Overlay-Netze sind ezient, da durch die bevorzugte Verwendung lokaler Knoten die Netzwerkressourcen geschont werden.
3. Die geographische Lokalität ist als Lokalitätskriterium nicht geeignet, da sie nicht
die Zusammenhänge im physikalischen Netzwerk berücksichtigt und schlecht bestimmt werden kann.
4. Latenzen sind für eine Lokalitätsbestimmung gut geeignet, da sie die tatsächlichen
Übertragungswege betrachten.
5. Anhand von Latenzmessungen sind die virtuellen Koordinaten gut berechenbar
und erreichen nach kurzer Zeit stabile Werte, die sich nur noch gering verändern
werden (mit Ausnahme von mobilen Netzen).
6. Durch die Benutzung virtueller Koordinaten ist die Bestimmung der Lokalität
ohne explizite Messung der Latenz möglich.
7. Für die Einteilung der Knoten in Horizonte sind dynamische Schwellen notwendig, da die Entfernungen zu anderen Knoten aus der Perspektive des jeweiligen
Knotens betrachtet werden.
8. Die Implementierung der einfachen Lokalisierung, die nur direkte Anfragen an alle
bekannten Knoten sendet, ist für kleine Knotenmengen ausreichend. Für gröÿere
Netze muss jedoch eine Suche implementiert werden.
2005-03-21/015/IN99/2253
105
Thesen
9. Ein dezentrales Routing benötigt kein vollständiges Wissen über das Netzwerk.
Somit kann es in einem dynamischen Peer-to-Peer-Netzwerk verwendet werden.
10. Mit dem implementierten dezentralen Routing wurden gute Rahmenbedingungen für das Multimedia-Streaming-System
ekStream
geschaen, da Knoten dy-
namisch gelernt werden und die Lokalität berücksichtigt wird. Es ist kein globales
Wissen über alle Knoten notwendig, sodass eine hohe Ausfallsicherheit erreicht
wird.
Ort
106
Datum
Unterschrift
2005-03-21/015/IN99/2253
Ich versichere an Eides statt, die von mir vorgelegte Arbeit selbstständig verfasst zu
haben. Alle Stellen, die wörtlich oder sinngemäÿ aus veröentlichten oder nicht veröffentlichten Arbeiten Anderer entnommen sind, habe ich kenntlich gemacht. Sämtliche
Quellen und Hilfsmittel, die ich für die Arbeit benutzt habe, sind angegeben. Die Arbeit
hat mit gleichem Inhalt bzw. in wesentlichen Teilen noch keiner anderen Prüfungsbehörde vorgelegen.
Ort
2005-03-21/015/IN99/2253
Datum
Unterschrift
107
108
2005-03-21/015/IN99/2253
A. Anhang
A.1. Übersicht über die Logdateien
uebersicht.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
Log
| ID ( P :5000) | IP
| LogTime
-- ---- ---- ---- --|- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- --- ---- ---zazu . log1
| 0 x8d1833a4 | 141. 24. 32. 28 | 13:13:28 - 13:39:31
zazu . log2
| 0 x8d1833a4 | 141. 24. 32. 28 | 13:39:50 - 14:21:33
diana . log1
| 0 x8d1833b4 | 141. 24. 32. 44 | 13:23:59 - 14:22:56
diana . log2
| 0 x8d1833b4 | 141. 24. 32. 44 | 13:06:54 - 13:23:37
eris . log0
| 0 x8d1833e6 | 141. 24. 32. 94 | 13:25:13 - 13:50:52
eris . log1
| 0 x8d1833e6 | 141. 24. 32. 94 | 14:03:45 - 14:33:59
macheiss . log1
| 0 x8d1833a5 | 141. 24. 32. 29 | 13:21:57 - 13:47:21
macheiss . log2
| 0 x8d1833a5 | 141. 24. 32. 29 | 13:55:14 - 14:21:49
telpc1 . log1
| 0 x8d1833b9 | 141. 24. 32. 49 | 13:23:06 - 14:10:43
telpc1 . log2
| 0 x8d1833b9 | 141. 24. 32. 49 | 14:11:19 - 14:21:06
telpc2 . log1
| 0 x8d1833b0 | 141. 24. 32. 40 | 13:43:25 - 14:16:42
telpc2 . log2
| 0 x8d1833b0 | 141. 24. 32. 40 | 14:16:55 - 14:21:24
telpc3 . log1
| 0 x8d183456 | 141. 24. 32.206 | 13:18:58 - 14:21:34
telpc4 . log1
| 0 x8d183457 | 141. 24. 32.207 | 13:16:20 - 13:49:37
telpc4 . log2
| 0 x8d183457 | 141. 24. 32.207 | 13:54:18 - 14:21:02
vsbslab1 . log1
| 0 x8d183423 | 141. 24. 32.155 | 11:32:01 - 12:54:00
vsbslab1 . log2
| 0 x8d183423 | 141. 24. 32.155 | 12:55:34 - 14:27:56
vsbslab2 . log1
| 0 x8d183424 | 141. 24. 32.156 | 12:55:34 - 13:46:38
vsbslab2 . log2
| 0 x8d183424 | 141. 24. 32.156 | 13:55:43 - 14:27:14
vsbslab3 . log1
| 0 x8d183425 | 141. 24. 32.157 | 12:55:43 - 14:25:42
vsbslab4 . log1
| 0 x8d183426 | 141. 24. 32.158 | 12:55:33 - 14:23:34
vsbslab5 . log1
| 0 x8d183427 | 141. 24. 32.159 | 12:55:26 - 14:22:54
vsbslab6 . log1
| 0 x8d183428 | 141. 24. 32.160 | 12:55:24 - 14:22:49
|
|
|
Andreas . log1
| 0 x550ad4db | 85. 10.193. 83 | 12:55:29 - 14:52:24
Christian . log1 | - ---- ---- --| --------------- | 12:44:08 - 14:40:00
ilmhost . log0
| 0 xd58577d6 | 213.133.100. 78 | 11:50:23 - 13:46:17
ilmhost . log1
| 0 xd58577d6 | 213.133.100. 78 | 13:59:09 - 14:29:59
Kristian . log1
| 0 xc0a81692 | 213. 54.227.229 | 12:07:33 - 14:42:30
orion . log1
| 0 xc19e7c71 | 193.158.104.233 | 12:57:56 - 14:29:58
slipstream . log1 | 0 x50ede194 | 80.237.206. 12 | 12:23:26 - 14:18:37
starburst . log1 | 0 xd9739e45 | 217.115.138.189 | 12:49:45 - 14:44:59
wotan . log1
| 0 xc07d0bb7 | 192.124.248. 47 | 13:53:42 - 15:25:33
|
|
|
|
|
|
telpc7
| 0 x8d183480 | 141. 24. 32.248 | ------------------jason
| 0 x8d183415 | 141. 24. 32.141 | ------------------|
|
|
2005-03-21/015/IN99/2253
109
A. Anhang
A.2. Datendatei für die Skripte
lesdata.dat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# filename
floh1zazu . log1 . clean
floh1zazu . log2 . clean
floh1diana . log1 . clean
floh1diana . log2 . clean
floh1eris . log0 . clean
floh1telpc1 . log1 . clean
floh1vsbslab1 . log1 . clean
floh1Andreas . log1 . clean
floh1ilmhost . log0 . clean
floh1ilmhost . log1 . clean
floh1Kristian . log1 . clean
floh1orion . log1 . clean
floh1slipstream . log1 . clean
floh1starburst . log1 . clean
floh1wotan . log1 . clean
# floh1eris . log1 . clean
# floh1macheiss . log1 . clean
# floh1macheiss . log2 . clean
# floh1telpc3 . log1 . clean
# floh1telpc4 . log2 . clean
# nodeid
0 x8d1833a4
0 x8d1833a5
0 x8d1833b4
0 x8d1833e6
0 x8d183415
0 x8d1833b9
0 x8d1833b0
0 x8d183456
0 x8d183457
0 x8d183480
0 x8d183423
0 x8d183424
0 x8d183425
0 x8d183426
0 x8d183427
0 x8d183428
0 x550ad4db
0 xd58577d6
0 xc0a81692
0 xc19e7c71
0 x50ede194
0 xd9739e45
0 xc07d0bb7
0 x8d18341d
110
shortname
zazu
zazu
dian
dian
eris
tel1
tel1
tel2
tel2
tel4
vsb1
vsb1
vsb2
vsb2
vsb3
vsb4
vsb5
vsb6
xAnd
xIlm
xIlm
xKri
xOri
xSli
xSta
xWot
eris
mach
mach
tel3
tel4
nodeid
0 x8d1833a4
0 x8d1833a4
0 x8d1833b4
0 x8d1833b4
0 x8d1833e6
0 x8d1833b9
0 x8d1833b9
0 x8d1833b0
0 x8d1833b0
0 x8d183457
0 x8d183423
0 x8d183423
0 x8d183424
0 x8d183424
0 x8d183425
0 x8d183426
0 x8d183427
0 x8d183428
0 x550ad4db
0 xd58577d6
0 xd58577d6
0 xc0a81692
0 xc19e7c71
0 x50ede194
0 xd9739e45
0 xc07d0bb7
0 x8d1833e6
0 x8d1833a5
0 x8d1833a5
0 x8d183456
0 x8d183457
timedrift
3338 w3338
3338 w3338
3977 w3977 -3978
3977 w3977 -3978
3093 w3093 -3094
3348 w3349
3348 w3347 -3348
3342 w3343 -3342
3342 w3340 -3343
3349 w3349 -3350
3349 # old !
3349 w3348 -3349
3349 w3349 -3350
3349 w3350 -3349
3349 w3349
3349 w3349
3349 w3349
3349 w3349 -3350
3353 w3353 -3354
3363 w3363 -3364
3363 w3364 -3363
3346 w3346 -3347
3338 w3338 -3339
4617 w4617 -4618
3036 w3036
0
w0
0
0
0
0
0
-
no
no
no
no
no
other nodes
routingmessages
routingmessages
routingmessages
other nodes
shortname
zazu
mach
dian
eris
jaso
tel1
tel2
tel3
tel4
tel7
vsb1
vsb2
vsb3
vsb4
vsb5
vsb6
xAnd
xIlm
xKri
xOri
xSli
xSta
xWot
ult5 # ultra5 -5. prakinf ...
2005-03-21/015/IN99/2253
A.3. Perlskript zum sortierten Zusammenfügen zweier Logdateien
A.3. Perlskript zum sortierten Zusammenfügen
zweier Logdateien
makeDiLog.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# !/ usr / bin / perl -w
# ##########################################################
#
# Can be used as an utility for syncronizing two files
#
# Read the data of two log files containing time fields .
# For the data of the second file a delta will be added
# before the sorted data of both files will be printed
# to stdout .
# Needed some data of the ' filesdata . dat '.
#
# ( w ) Thomas Sesselmann
#
# ###
my
my
my
my
$file1 = s h i f t ;
$file2 = s h i f t ;
$timedrift = s h i f t ;
$database = " filesdata . dat ";
p r i n t f "\ nSkript started .\ n" ;
i f (! d e f i n e d $file2 ) { d i e " Error : Usage :
synclogs . pl file1 file2 [ timedrift ]\ n" ; };
i f (! d e f i n e d $timedrift ) { $timedrift = 0; };
# # read data of file : filename shortname nodeid timedrift
my @database =() ;
open ( DATA , " < $database ") || d i e " Error : File ' $database ' not readable .\ n" ;
w h i l e (< DATA >) {
$_ =~ s /\ # .* $ //;
i f ( $_ =~ /^(\ S +) \ s +(\ S +) \ s +(0 x [0 -9a -f ]{8}) \ s +(\ d +) /) {
push @database , { filename => $1 , shortname = > $2 , nodeid => $3 , timedrift => $4 };
}
}
c l o s e DATA ;
# # important data
my % file2shortname ;
my % id2shortname ;
f o r e a c h ( @database ) {
i f ($_ - >{ filename } eq $file1 ) {
$file2shortname { $file1 }= $_ - >{ shortname };
$id2shortname {$_ - >{ nodeid }}= $_ - >{ shortname };
}
i f ($_ - >{ filename } eq $file2 ) {
$file2shortname { $file2 }= $_ - >{ shortname };
$id2shortname {$_ - >{ nodeid }}= $_ - >{ shortname };
}
}
##
my
my
my
my
read files
$time1 = -1;
$time2 = -1;
$line_f1 ;
$line_f2 ;
2005-03-21/015/IN99/2253
111
A. Anhang
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
open ( FILE1 ," < $file1 " ) || d i e " Error : File ' $file1 ' not readable .\ n ";
open ( FILE2 ," < $file2 " ) || d i e " Error : File ' $file2 ' not readable .\ n ";
w h i l e (! ( e o f ( FILE1 ) || e o f ( FILE2 ) ) ) {
i f ( $time1 < 0) {
$line_f1 = < FILE1 >;
$time1 = & readtime ( $line_f1 , 0) ;
next ;
}
i f ( $time2 < 0) {
$line_f2 = < FILE2 >;
$time2 = & readtime ( $line_f2 , $timedrift );
next ;
}
i f ( $time1 <= $time2 ) {
& outputline ( $file1 , $time1 , $line_f1 ) ;
$time1 = -1;
} else {
& outputline ( $file2 , $time2 , $line_f2 ) ;
$time2 = -1;
}
}
w h i l e (< FILE1 >) {
$time1 = & readtime ($_ , 0) ;
& outputline ( $file1 , $time1 , $_ );
}
w h i l e (< FILE2 >) {
$time2 = & readtime ($_ , $timedrift );
& outputline ( $file2 , $time2 , $_ );
}
c l o s e FILE2 ;
c l o s e FILE1 ;
p r i n t f ("\ n\ nSkript stopped .\ n \n" );
# ############################################
sub readtime ( $$ ) { # line , drift
my $line = s h i f t ;
my $drift = s h i f t ;
my $time = -1;
i f ( $line =~ /^(\ d {2}) :(\ d {2}) :(\ d {2}) /) {
$time = $1 *3600 + $2 *60 + $3 + $drift ;
}
r e t u r n $time ;
}
sub outputline ( $$$ ) { # file , time , line
my $file = s h i f t ;
my $time = s h i f t ;
i f ( $line =~ / LocalityRouting .*\[ Vector : Id : (0 x [0 -9a -f ]{8}) , Data : ([0 -9. -]+) , ([0 -9. -]+) , ([0 -9. -]+) , ([0 -9. -]+)
, ([0 -9. -]+) \]/) {
i f ( e x i s t s $id2shortname { $1 }) {
i f ( $id2shortname { $1 } eq $file2shortname { $file }) {
p r i n t f "%s : %5 u ---- %15.8 f %15.8 f %15.8 f %15.8 f %15.8 f \n" ,
$file2shortname { $file }, $time , $2 , $3 , $4 , $5 , $6 ;
} else {
112
2005-03-21/015/IN99/2253
A.4. Perlskript zum Erzeugen der Dierenz zwischen zwei Logdateien
129
p r i n t f "% s: %5 u %s %15.8 f %15.8 f %15.8 f %15.8 f %15.8 f \ n" ,
130
$file2shortname { $file }, $time , $id2shortname { $1 }, $2 , $3 , $4 , $5 , $6 ;
131
}
132
}
133
}
134
135 }
136
137
138
139 __END__
140
141
A.4. Perlskript zum Erzeugen der Dierenz zwischen
zwei Logdateien
searchSyncTime.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# ####################################################
#
# This script tries to find a time for which the
# two files can be synchronized .
#
# A locality vector has to be calculated for this
# node before the other node had received it .
#
#
# ###
my $own = " ----" ;
my
my
my
my
my
my
@data1other ;
@data1own ;
@data2other ;
@data2own ;
$name1 ="" ;
$name2 ="" ;
# readdata
my $fd ;
i f ( d e f i n e d $file ) {
open ( $fd , " < $file ") || d i e " Error : Can 't open file ' $file '\n ";
} else {
$fd = STDIN
}
w h i l e (< $fd >) {
i f ( $_ =~ /(\ w {4}) :\ s +(\ d +) \ s +(\ S {4}) \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +([0 -9. -]+) /) {
i f ( $name1 eq "" ){
$name1 = $1 ;
}
i f ( $1 eq $name1 ) {
i f ( $3 eq $own ){
push @data1own , [$2 ,$4 ,$5 , $6 ,$7 , $8 ]; # time , d1 , d2 , d3 , d4 , d5
} else {
push @data1other , [$2 , $4 ,$5 ,$6 ,$7 , $8 ]; # time , d1 , d2 , d3 , d4 , d5
}
next ;
2005-03-21/015/IN99/2253
113
A. Anhang
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
}
i f ( $name2 eq "" ){
$name2 = $1 ;
}
i f ( $1 eq $name2 ) {
i f ( $3 eq $own ){
push @data2own , [$2 ,$4 ,$5 , $6 ,$7 , $8 ]; # time , d1 , d2 , d3 , d4 , d5
} else {
push @data2other , [$2 , $4 ,$5 ,$6 ,$7 , $8 ]; # time , d1 , d2 , d3 , d4 , d5
}
next ;
}
}
}
c l o s e $fd ;
# comparing1
my $diff ;
my $td_min1 = 3600*24;
my $td_min2 = $td_min1 ;
my $td_max1 = - $td_min1 ;
my $td_max2 = $td_max1 ;
f o r e a c h $a ( @data1own ){
# $i => [ time , d1 , d2 , d3 , d4 , d5 ]
f o r e a c h $b ( @data2other ){
i f (( $a - >[1] == $b - >[1]) &&( $a - >[2] == $b - >[2]) &&( $a - >[3] == $b - >[3])
&&( $a - >[4] == $b - >[4]) &&( $a - >[5] == $b - >[5]) ){
$diff = $a - >[0] - $b - >[0];
i f ( $td_min1 > $diff ) { $td_min1 = $diff ;}
i f ( $td_max1 < $diff ) { $td_max1 = $diff ;}
}
}
}
printf
printf
printf
printf
" Name1 :
" Name2 :
" Minimal Diff 1 - >2:
" Maximal Diff 1 - >2:
' $name1 '\n" ;
' $name2 '\n" ;
' $td_min1 '\n" ;
' $td_max1 '\n" ;
# comparing2
f o r e a c h $b ( @data2own ){
# $i => [ time , d1 , d2 , d3 , d4 , d5 ]
f o r e a c h $a ( @data1other ){
i f (( $a - >[1] == $b - >[1]) &&( $a - >[2] == $b - >[2]) &&( $a - >[3] == $b - >[3])
&&( $a - >[4] == $b - >[4]) &&( $a - >[5] == $b - >[5]) ){
$diff = $a - >[0] - $b - >[0];
i f ( $td_min2 > $diff ) { $td_min2 = $diff ;}
i f ( $td_max2 < $diff ) { $td_max2 = $diff ;}
}
}
}
printf
printf
printf
printf
" Minimal
" Maximal
" Minimal
" Maximal
Diff
Diff
Diff
Diff
2 - >1:
2 - >1:
sum :
sum :
' $td_min2 '\n" ;
' $td_max2 '\n" ;
'%d '\ n" , $td_max1 < $td_max2 ? $td_max1 : $td_max2 ;
'%d '\ n" , $td_min1 > $td_min2 ? $td_min1 : $td_min2 ;
__END__
114
2005-03-21/015/IN99/2253
A.5. Perlskript zum sortierten Zusammenfügen aller Logdateien
A.5. Perlskript zum sortierten Zusammenfügen aller
Logdateien
makeOneLog.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# #######################################################
#
# This script synchronizes all log files of ' filedata . dat '
# by a given delta and put it in one file .
#
#
# ###
my $database = " filesdata . dat ";
my $outfile = " floh1all . log " ;
p r i n t f "\ nSkript started .\ n" ;
# # read data of file : filename shortname nodeid timedrift
my @data =() ;
my % ids ;
open ( DATA , " < $database ") || d i e " Error : File ' $database ' not readable .\ n" ;
w h i l e (< DATA >) {
$_ =~ s /\ # .* $ //;
i f ( $_ =~ /^(\ S +) \ s +(\ S +) \ s +(0 x [0 -9a -f ]{8}) \ s +(\ d +) /) {
my $fd ;
i f (! -f $1 ) { next ; }
push @data , { file = >$1 , fd = > $fd , shortname =>$2 , nodeid =>$3 , timedrift =>$4 , time = > -1};
}
i f ( $_ =~ /^(0 x [0 -9 a - f ]{8}) \ s +(\ w {4}) /) {
$ids { $1 }= $2 ;
}
}
c l o s e DATA ;
# # open files
f o r e a c h $en ( @data ) {
open ( $en - >{ fd } ," <$en - >{ file }" );
}
open ( OUTFILE , " > $outfile ");
# # read
my $run = 1;
my $fd ;
my $processtime = 0;
my $lines = 0;
w h i l e ( $run ) {
# read one line of all files and test $run
$run = 0;
f o r e a c h $en ( @data ){
$fd = $en - >{ fd };
i f (! e o f ( $fd )){
$run = 1;
i f ( $en - >{ time } < 0) {
$en - >{ line } = <$fd >;
2005-03-21/015/IN99/2253
115
A. Anhang
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
$en - >{ time } = & readtime ( $en - >{ line } , $en - >{ timedrift }) ;
}
}
}
# select first line for output
my $t_min = 3600*24;
my $dataentry ;
f o r (my $i = 0; $i < @data ; $i ++) {
i f ((%{ $data [ $i ]} - >{ time } > 0) &&( $t_min > %{ $data [ $i ]} - >{ time }) ) {
$dataentry = $data [ $i ];
$t_min = $dataentry - >{ time };
}
}
# output
& outputline ( $dataentry );
$lines ++;
i f ( $lines %1000 == 0) {
# if ( $processtime +100 < $dataentry - >{ time }) {
$processtime = $dataentry - >{ time };
p r i n t f " ProcessTime : %5 d now . Processing %10 d lines .\ n" , $processtime , $lines ;
}
$dataentry - >{ time }= -1;
}
## close files
f o r e a c h $en ( @data ) {
c l o s e $en - >{ fd };
}
c l o s e OUTFILE ;
p r i n t f ("\ n\ nSkript stopped .\ n \n" );
# ###########################################
sub readtime ( $$ ) { # line , drift
my $drift = s h i f t ;
my $time = -1;
i f ( $line =~ /^(\ d {2}) :(\ d {2}) :(\ d {2}) /) {
$time = $1 *3600 + $2 *60 + $3 + $drift ;
}
r e t u r n $time ;
}
sub outputline ($ ) { # file , time , line
my $entry = s h i f t ;
#
#
#
#
#
#
$time
$time
$time
$time
$time
$time
$name :
$name :
$name :
$name :
$name :
$name :
calcVector
rem_Vector
update_LR_
started_to
threashold
knownNodes
$vector failure : $failure distance : $distance
$remname $vector
$learnrate
$name
local : $1 extended : $2 updatetime : $3
sum : $1 local : $2 extended : $3 global : $4
# ownvector
i f ( $entry - >{ line } =~ / LocalityRouting .* calculated : \[ Vector : Id :
([0 -9. -]+) , ([0 -9. -]+) , ([0 -9. -]+) \] failure was ([0 -9. -]+)
p r i n t f OUTFILE " %6 d % s: calcVector
%15.8 f %15.8 f %15.8 f
$entry - >{ time }, $entry - >{ shortname } , $1 , $2 , $3 , $4 , $5 , $6 ,
}
0 x [0 -9a -f ]{8} , Data : ([0 -9. -]+) , ([0 -9. -]+) ,
by distance : ([0 -9. -]+) /) {
%15.8 f %15.8 f failure : %8.2 f distance %8.2 f\ n" ,
$7 ;
# remVector
116
2005-03-21/015/IN99/2253
A.6. Perlskript zum Teilen der kompletten Logdatei
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
i f ( $entry - >{ line } =~ / LocalityRouting .* New LocalityVector \[ Vector : Id : (0 x [0 -9a -f ]{8}) , Data : ([0 -9. -]+) ,
([0 -9. -]+) , ([0 -9. -]+) , ([0 -9. -]+) , ([0 -9. -]+) \]/) {
my $remName = " ----" ;
i f ( e x i s t s $ids { $1 }) { $remName = $ids { $1 }; }
e l s e { p r i n t f " debug >$1 <\ n" ;} # DEBUG
p r i n t f OUTFILE " %6 d % s: rem_Vector %s %15.8 f %15.8 f %15.8 f %15.8 f %15.8 f \n" ,
$entry - >{ time }, $entry - >{ shortname } , $remName , $2 , $3 , $4 , $5 , $6 ;
}
# learnrate
i f ( $entry - >{ line } =~ / LocalityRouting .* Update learn rate to : ([0 -9.]+) /) {
p r i n t f OUTFILE " %6 d % s: update_LR_ %4.2 f\n" ,
$entry - >{ time }, $entry - >{ shortname } , $1 ;
}
# started
i f ( $entry - >{ line } =~ / LocalityRouting .* Bootstrap to address (.*) /) {
p r i n t f OUTFILE " %6 d % s: started_to %s\n " ,
$entry - >{ time }, $entry - >{ shortname } , $1 ;
}
# threshold
i f ( $entry - >{ line } =~ / LocalityRouting .* Threashold_local : (\ d +) Threashold_extened : (\ d +) LOCALITY_UPDATE_TIME : (\
d +) /) {
p r i n t f OUTFILE " %6 d % s: threashold local : %4 d extended : %4 d updatetime : %4 d \n" ,
$entry - >{ time }, $entry - >{ shortname } , $1 , $2 , $3 ;
}
# knownnodes
i f ( $entry - >{ line } =~ / LocalityRouting .* SumNodes : (\ d +) localNodes : (\ d +) extendedNodes : (\ d +) globalNodes : (\ d +)
/) {
p r i n t f OUTFILE " %6 d % s: knownNodes sum : %2 d local : %2 d extended : %2 d global : %2 d\ n" ,
$entry - >{ time }, $entry - >{ shortname } , $1 , $2 , $3 , $4 ;
}
157
158
159
160
161 }
162
163 __END__
A.6. Perlskript zum Teilen der kompletten Logdatei
splitOneLog.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# #################################################
#
# This script splits the generated log file for
# different kinds :
# - each host in a separately file
# - each type of log entry in separately file
# - combining host and types ...
#
#
# ###
my $inputfile = s h i f t ;
i f (! d e f i n e d $inputfile ) { d i e " Error : No file specified .\ n" ; }
my % hosts ;
$hosts { alle }=1;
my % typs ;
2005-03-21/015/IN99/2253
117
A. Anhang
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
$typs { alle }=1;
$ |=1;
# flush
# find hosts and types
open ( FILE , " < $inputfile ") || d i e " Error : Can 't open file ' $inputfile '!\ n" ;
w h i l e (< FILE >) {
i f ( $_ =~ /^\ s *\ d +\ s +(\ w {4}) :\ s +(\ S {10}) \ s /) {
i f (! e x i s t s $hosts { $1 }) {
$hosts { $1 }=1;
}
i f (! e x i s t s $typs { $2 }) {
$typs { $2 }=1;
}
}
}
c l o s e FILE ;
# write hosts and types
f o r e a c h $host ( keys % hosts ) {
f o r e a c h $typ ( keys % typs ) {
open ( IFILE , " < $inputfile ");
i f ( $typ eq " alle " ){
p r i n t f " Write file ' $inputfile . $host ' ... " ;
open ( OFILE , " > $inputfile . $host ");
} else {
p r i n t f " Write file ' $inputfile . $host \ _$typ ' ... ";
open ( OFILE , " > $inputfile . $host \ _$typ " );
}
w h i l e (< IFILE >) {
i f ( $_ =~ /^\ s *\ d +\ s +(\ w {4}) :\ s +(\ S {10}) \ s /) {
i f ((( $1 eq $host ) ||( $host eq " alle " ))
&&(( $2 eq $typ ) ||( $typ eq " alle " )) ){
p r i n t f OFILE " $_ ";
}
}
}
c l o s e OFILE ;
c l o s e IFILE ;
p r i n t f " done .\ n" ;
}
}
A.7. Perlskript zum Berechnen der Abstände vieler
Vektoren in einer Datei
calc.pl
1
2
3
4
5
6
7
8
# #############################################
#
# Calculates all distances between the given
# vectors in the file .#
#
118
2005-03-21/015/IN99/2253
A.8. Perlskript zum Berechnen der Abstände zweier Knoten zu jedem Zeitpunkt
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#
# ###
i f (! d e f i n e d $file ) { d i e " Error : No file specified .\ n" ; }
my % vectors ;
# read vectors
open ( FILE , " < $file ");
i f ( $_ =~ /^\ s *\ d +\ s +(\ w {4}) :\ s + calcVector \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +/) {
$vectors { $1 } = [$2 , $3 ,$4 ,$5 , $6 ];
}
}
c l o s e FILE ;
# calculate distances
f o r e a c h $key1 ( keys % vectors ) {
my $vec1 = $vectors { $key1 };
f o r e a c h $key2 ( keys % vectors ) {
my $vec2 = $vectors { $key2 };
my $dist = 0;
f o r (my $i = 0; $i < 5; $i ++) {
$dist += (( $vec1 - >[ $i ]) - ( $vec2 - >[ $i ]) ) **2;
}
$dist = s q r t ( $dist );
p r i n t f " Distance from '%s ' to '% s ' is '%12.8 f '\n " ,
$key1 , $key2 , $dist ;
}
}
__END__
A.8. Perlskript zum Berechnen der Abstände zweier
Knoten zu jedem Zeitpunkt
calcDist2.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# ##############################################
#
# This script calculates the distance between
# the two given hosts any time one vector was
# changed and print the list to the stdout .
#
# If the second host isn 't given , the distance
# will be calculated to the constant null vector .
#
#
# ###
my $file = " floh1all . log . org " ;
my $name1 = s h i f t ;
my $name2 = s h i f t ;
i f (! d e f i n e d $name1 ) {
d i e " Usage : calcDist2 . pl < name1 > [ < name2 >]\ n" ;
}
2005-03-21/015/IN99/2253
119
A. Anhang
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
my @vec1 ;
my @vec2 ;
i f (! d e f i n e d $name2 ) {
$name2 = " blablub " ;
@vec2 = (0 ,0 ,0 ,0 ,0) ;
}
p r i n t f "# Distance from ' $name1 ' to ' $name2 '\n" ;
p r i n t f " plot '-' us 1:3\ n";
open ( FILE , " < $file ");
i f ( $_ =~ /\ s *(\ d +) \ s +(\ w {4}) :\ s + calcVector \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s +([0 -9. -]+) \ s /) {
i f ( $2 eq $name1 ) {
@vec1 = ($3 , $4 , $5 , $6 , $7 );
}
i f ( $2 eq $name2 ) {
@vec2 = ($3 , $4 , $5 , $6 , $7 );
}
i f ((( $2 eq $name1 ) ||( $2 eq $name2 )) &&( @vec1 == 5) &&( @vec2 == 5) ) {
my $dist = 0;
f o r (my $i = 0; $i < 5; $i ++) {
$dist += ( $vec1 [ $i ] - $vec2 [ $i ]) **2;
}
$dist = s q r t ( $dist );
# printf "%5 d distance '% s ' to '% s ' is %6.4 f \ n ", $1 , $name1 , $name2 , $dist ;
p r i n t f " %5 d distance : %8.4 f\n " , $1 , $dist ;
}
}
}
c l o s e FILE ;
Hier ein kleiner Ausschnitt aus der Logdatei vom Knoten wotan. Die Leerzeilen stehen
für viele weggelassene Zeilen.
oh1wotan.log1
1
2
3
4
5
6
7
8
9
10
11
12
13
13:53:42
13:53:42
13:53:42
13:53:42
13:53:42
13:53:42
LocalityRouting { main }: DEBUG : Routing : Adding handler : [ Looper : Routing , Thread [ Routingthread ,5 , main ]]
LocalityRouting { main }: DEBUG : Starting : [ Looper : Routing , Thread [ Routingthread ,5 , main ]]
LocalityRouting { Routingthread }: DEBUG : Start RoutingThread ...
LocalityRouting { main }: DEBUG : Start bootstrap .
LocalityRouting { main }: DEBUG : Bootstrap to address zazu . prakinf .tu - ilmenau . de /141.24.32.28:5000
UpdateThread { RoutingUpdateThread }: DEBUG : Start RoutingUpdateThread ...
13:53:47 SimpleNetLocalisation { NetLocalisation_UpdateThread }: ERROR : Catch NoSuchElementException from Buffer .
Ignore all new BufferData !
13:53:47 NodeProxy { Prototype 3 ekStream Applicationthread }: DEBUG : Routing message to :0 x8d183424
13:53:47 LocalityRouting { Prototype 3 ekStream Applicationthread }: DEBUG : Send TransportBag to Node 0 x8d183424 with
address /141.24.32.156:5000 and TTL 16
13:53:47 NodeProxy { Prototype 3 ekStream Applicationthread }: DEBUG : Routing message to :0 x8d183427
13:53:47 LocalityRouting { Prototype 3 ekStream Applicationthread }: DEBUG : Send TransportBag to Node 0 x8d183427 with
address /141.24.32.159:5000 and TTL 16
14
15
16 13:53:49 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Received TransportBag from Node 0 x8d183424
for 0 xc07d0bb7 with TTL 16
17 13:53:49 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Received a GetBWAddressMessage from node 0
x8d183424
120
2005-03-21/015/IN99/2253
18 13:53:49 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Send TransportBag to Node 0 x8d183424 with
address /141.24.32.156:5000 and TTL 16
19 13:53:49 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Received TransportBag from Node 0 x8d18341d
20 13:53:49 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Forward Message to localNode .
21 13:53:49 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Target for incoming message : org . ekstream .
peer . messaging . Messenger@126f75b
22
23
24 13:53:52 LocalityRouting { RoutingUpdateThread }: DEBUG : Send TransportBag to Node 0 xc0a81692 with address
/213.54.227.229:5000 and TTL 16
25 13:53:52 LocalityRouting { RoutingUpdateThread }: DEBUG : Send TransportBag to Node 0 x8d183425 with address
/141.24.32.157:5000 and TTL 16
26 13:53:52 LocalityRouting { RoutingUpdateThread }: DEBUG : Send TransportBag to Node 0 x8d183424 with address
/141.24.32.156:5000 and TTL 16
27 13:53:52 LocalityRouting { RoutingUpdateThread }: DEBUG :
:/141.24.32.155:5000
:/85.10.193.83:5000
:/141.24.32.149:5000
RoutingTableEntry : 0 x8d183423 with address
RoutingTableEntry : 0 x550ad4db with address
RoutingTableEntry : 0 x8d18341d with address
30
31
32 13:53:53 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Received a ReceivedLocalityMessage from node
0 x8d183423
33 13:53:53 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : New LocalityVector [ Vector : Id : 0 x8d183423 ,
Data : -42.03432219466149 , -15.67420793168601 , -50.581044849873834 , -2.844919892272732 , 36.76725785387105]
35 13:53:53 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Received a ReceivedBWAddressMessage from
node 0 x8d183423
36 13:53:53 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Received TransportBag from Node 0 x550ad4db
0 x550ad4db
38 13:53:53 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : New LocalityVector [ Vector : Id : 0 x550ad4db ,
Data : -40.03381088945788 , -15.263857885711674 , -44.4197838825483 , -6.370769219266864 , 30.34402236002108]
39 13:53:53 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : Received TransportBag from Node 0 x8d18341d
0 x8d18341d
41 13:53:53 LocalityRouting { DatagramSocketOutlet_ReceiverThread }: DEBUG : New LocalityVector [ Vector : Id : 0 x8d18341d ,
Data : -41.84716366691346 , -38.743675099701974 , -7.135595621997649 , -1.621440570720185 , 6.684067342929131]
43
44
45 13:54:20 LocalityRouting { Thread -2}: DEBUG : Routing : posted : [ EchoResult : , dst : telpc1 . prakinf .tu - ilmenau . de
/141.24.32.49:5002 , echos : 5, rtt : 2.856]
46 13:54:20 LocalityRouting { Thread -2}: DEBUG : Routing : posted : [ EchoResult : , dst : ultra5 -5/141.24.32.149:5002 , echos :
5, rtt : 2.8704000000000005]
47
48
49 13:54:20 LocalityRouting { Routingthread }: DEBUG : [ Looper : Routing , Thread [ Routingthread ,5 , main ], alive ] dispatching
50
51
52
: [ EchoResult : , dst : telpc1 . prakinf .tu - ilmenau . de /141.24.32.49:5002 , echos : 5, rtt : 2.856] to : [ Looper :
Routing , Thread [ Routingthread ,5 , main ], alive ]
13:54:20 LocalityRouting { Routingthread }: DEBUG : Received EchoResultMessage : nodeId : 0 x8d1833b9 RTT : 2.0
13:54:20 LocalityVector { Routingthread }: DEBUG : New LocalityVector calculated : [ Vector : Id : 0 xc07d0bb7 , Data :
5.262633320022353 , 103.15207738080089 , 71.20001786980765 , 171.57642593856121 , 25.263040277251456] failure was :
346.58465060732937 by distance : 348.58465060732937!
13:54:20 LocalityRouting { Routingthread }: DEBUG : New LocalLocalityVector calculated : [ Vector : Id : 0 xc07d0bb7 , Data :
5.262633320022353 , 103.15207738080089 , 71.20001786980765 , 171.57642593856121 , 25.263040277251456] failure was
346.58465060732937 by distance : 348.58465060732937
13:54:20 LocalityRouting { Routingthread }: DEBUG : Update learn rate to : 0.3
53
54
55
56 13:54:23 LocalityRouting { RoutingUpdateThread }: DEBUG : SumNodes : 15 localNodes : 9 extendedNodes : 6 globalNodes : 0
57 13:54:23 LocalityRouting { RoutingUpdateThread }: DEBUG : Threashold_local : 45 Threashold_extened : 180
LOCALITY_UPDATE_TIME : 2700
2005-03-21/015/IN99/2253
121
A. Anhang
A.10. Vorgehen zum Ausführen eines Tests
Auf den Knoten, die zum lokalem Test verwendet wurden, ist
Debian 3.1 1 (sarge ) in-
stalliert (Auf den externen Knoten für den deutschlandweiten Test ist das Betriebssystem nicht bekannt.). Die Implementierung der Quelltexte von
2
(Version 1.4) mit Hilfe der Entwicklungsumgebung Eclipse
ekStream erfolgte in Java
3.1. Im Folgenden werden
die einzelnen Schritte für die Ausführung der Testdateien von
ekStream
erläutert.
A.10.1. Herunterladen des Projekts
Als Versionsverwaltungssystem für das Projekt
ekStream wurde Subversion3 verwendet.
Die Benutzung von Subversion kann entweder in der Kommandozeile oder über das
Subclipse 4 (Version 0.9.28) geschehen.
Projektes ist über einen Checkout erhältlich:
Eclipse-Plugin
Eine aktuelle Arbeitskopie des
user@telpc2:~$ svn checkout svn://ekstream.org/ekStream/trunk/ekStream
Die Aktualisierung der Arbeitskopie kann folgendermaÿen vorgenommen werden:
user@telpc2:~$ svn update ekStream
A.10.2. Kompilieren der Testdateien
In dem Verzeichnis
ekStream/tests/org/ekstream/test
des heruntergeladenen Pro-
jekts benden sich die Dateien, mit denen der Test vorgenommen wurde:
user@telpc2:~/ekStream/tests/org/ekstream/test$ ls *.java
StreamingTestFullDynamic.java
StreamingTestStaticRoutingPlainScheduling.java
StreamingTestStaticRoutingRBCScheduling.java
...
Die Testdateien werden nach
ekStream/bin
wie folgt kompiliert:
1 http://www.debian.org
2 http://www.eclipse.org
3 http://subversion.tigris.org/
4 http://subclipse.tigris.org/
122
2005-03-21/015/IN99/2253
user@telpc2:~/ekStream/tests$ javac -d ../bin -classpath ../src \
org/ekstream/test/StreamingTest*.java
A.10.3. Kongurieren des Datenstroms
Bevor das Streaming gestartet werden kann, muss der Datenstrom konguriert werden.
Die Aufnahme und die Encodierung des Datenstroms erfolgt mit
grasche Oberäche von
mp4live
mp4live 5 .
Über die
ist es möglich, Parameter wie die Auösung, die
Bitrate und das Ziel (Urquelle) des Datenstroms einzustellen. Dabei kann eine SDPDatei (
Session Description Protocol, siehe [RFC 2327 (1998)]), die zum Abspielen des
Datenstroms benötigt wird, erzeugt werden.
Die Konguration des Datenstroms über
.mp4live_rc
metern
mp4live
eingestellt werden. Das Starten von
automatic
und
kann ebenso manuell in der Datei
mp4live
erfolgt dann mit den Para-
headless:
user@telpc7:~$ mp4live --automatic --headless
A.10.4. Starten der Testdateien
Über die Testdatei
StreamingTestFullDynamic.class
kann
ekStream
mit dem dy-
namischen lokalitätsbewussten Routing und der Schedulingstrategie RBCS gestartet
werden. Dabei wird beim Start mindestens ein Knoten als Bootstrapping-Punkt, auÿer
bei der Urquelle, angegeben. Die Parameter für den Start sind:
1. Parameter:
2. Parameter:
3. Parameter:
Port für den Empfang des Datenstroms (20000)
Port für die Kommunikation des Routings mit anderen Knoten (5000)
festgelegte Bandbreite in
breitenbestimmung und das
ab 4. Parameter:
kbit/s dieses Knotens für die statische Band-
Admission Control
Knotenliste, die das Routing für das
Bootstrapping
verwenden soll
Für die Urquelle ergibt sich damit folgender Aufruf:
5
http://mpeg4ip.sourceforge.net/documentation/index.php?readme=mp4live
2005-03-21/015/IN99/2253
123
A. Anhang
user@telpc7:~/ekStream/bin$ java org/ekstream/test/StreamingTestFullDynamic \
20000 5000 2000
Der Aufruf für einen anderen Knoten, der nicht die Urquelle ist, setzt sich wie folgt
zusammen:
user@telpc2:~/ekStream/bin$ java org/ekstream/test/StreamingTestFullDynamic \
20000 5000 2000 telpc7:5000
Durch den Start der Datei
wird
ekStream
StreamingTestStaticRoutingPlainScheduling.class
mit einem statischen Routing und der Schedulingstrategie Plain Sched-
uling aufgerufen.
Der Start der Datei
Aufruf von
StreamingTestStaticRoutingRBCScheduling.class
führt zum
ekStream mit einem statischen Routing und der Schedulingstrategie RBCS.
Zum Start dieser beiden Dateien werden die gleichen Parameter wie beim Start der
Datei
StreamingTestFullDynamic.class
verwendet. Durch die Benutzung eines sta-
tischen Routings in beiden Dateien müssen jetzt alle Knoten angegeben werden, die
dieser Knoten kennen soll.
Nach dem Starten einer Testdatei önet sich eine grasche Oberäche von
ekStream.
Unter den einzelnen Reitern können für den Knoten der Zustand des Puers für den
Audio- und Video-Datenstrom, die bekannten Knoten, die eingehenden und ausgehenden
Links
beobachtet werden.
Zusätzlich gibt
über die Datei
ekStream
in der Kommandozeile ein
logger.conf
A.10.5. Starten des
unter
ekStream/bin
Logging
aus. Das
Logging
kann
eingestellt werden.
mplayers
Um nun die empfangenen Multimedia-Daten des Datenstroms auf einem Knoten anzeigen zu können, kann der
mplayer 6 mit mplayer -vo xv sdp://capture.sdp gestartet
werden.
ekStream
sendet den Datenstrom (jeweils Video und Audio) lokal an einen Port, der
um zehn gröÿer als der Empfangsport (1. Parameter beim Aufruf der Testdatei) ist.
6 http://mplayerhq.hu/homepage/index.html
124
2005-03-21/015/IN99/2253
Daher muss dieser Port vor dem Start des
mplayers in der Datei capture.sdp geändert
werden. In dem folgenden Beispiel wird daher in der 10. Zeile 20010 (statt 20000) für den
Video-Datenstrom und in der 15. Zeile 20012 (statt 20002) für den Audio-Datenstrom
eingetragen.
capture.sdp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
v =0
o=- 1116950668999035 1116950668999036 IN IP4 141.24.32.248
s= capture . sdp
e= NONE
c= IN IP4 141.24.32.248
b= RR :0
t =0 0
a= mpeg4 - iod : " data : application / mpeg4 - iod ; base64 , AoCAgy4AT /// DwP / A4CAgHkAyUBGZGF0YTphcHBsaWNhdGlvbi9tcGVnNC1iaWZzLWF
1 O2Jhc 2 U2NCx3QkFTZ1RBcUJXMG1FRUg4QUFBQi9BQUFCRUtDS0NuNASAgIAVAg0AABgAAADAAAAAwAWAgIADAABgBoCAgBAARAAAAAAAAAA
AAAAAAAADA4CAgiQAZUD0ZGF0YTphcHBsaWNhdGlvbi9tcGVnNC1vZC1hdTtiYXNlNjQsQVlDQWdSVUJnSUNBT0FLZkE0Q0FnREVBQ2dBRWdJ
Q0FGRUFWQUQ2QUFBSDBBQUFCOUFBRmdJQ0FBaElRQm9DQWdCQUFSQUFBQUFBQUFBQUFBQUFBQUFBREFZQ0FnRk1GSHdPQWdJQk1BQlFBQklDQ
WdDOGdFUUNTZkFBRWsrQUFCSlBnQllDQWdCMEFBQUd3QXdBQUFiVUpBQUFCQUFBQUFTQUFoc1FBWnd3V0VFaFJqd2FBZ0lBUUFFUUFBQUFBQU
FBQUFBQUFBQUFBQXc9PQSAgIASAQUAAJoAAATQAAAE0AWAgIAABoCAgBAARAAAAAAAAAAAAAAAAAAD "
a= isma - compliance :1 ,1.0 ,1
m= video 20000 RTP / AVP 96
b= AS :300
a= rtpmap :96 MP4V - ES /90000
a= fmtp :96 profile - level - id =3; config =000001 b003000001b50900000100000001200086c400670c161048518f ;
a= mpeg4 - esid :20
m= audio 20002 RTP / AVP 97
b= AS :128
a= rtpmap :97 mpeg4 - generic /44100
a= fmtp :97 streamtype =5; profile - level - id =15; mode = AAC - hbr ; config =1210; SizeLength =13; IndexLength =3;
IndexDeltaLength =3; Profile =1;
a= mpeg4 - esid :10
2005-03-21/015/IN99/2253
125

Paper - Lehre und Forschung Thorsten Strufe

Transcrição

Documentos relacionados

Knoten für jedes FW-Mitglied - Kreisfeuerwehrverband Hersfeld

Manschaftsknoten 02 - 7tes-MSG

Institution Herzog Anton Ulrich-Museum Signatur ADürer AB 3.216H

Institution Herzog Anton Ulrich-Museum Signatur ADürer WB 3.218

2.1.3 Messbereichserweiterung 2 bei einem Drehspulinstrument ( ) ( )

Knotenkunde - Freiwillige Feuerwehr Elsholz

Du bist Suchma- schine!

TOR The Onion Routing

Anleitung Strickliesel VS.indd

Welche Behandlungsmethoden und Operationen bieten wir an?