Hardwarenahe Programmierung / Vorlesung Ad-hoc-NetzwerkeAd-hoc-Netzwerke

Hardwarenahe Programmierung / Vorlesung

Ad-hoc-Netzwerke

Ad-hoc-NetzwerkeAd-hoc-Netzwerke


Ad-hoc-Netzwerke

AgendaAgenda

Einführung

Ad-hoc-Netzwerke

Routing in Ad-hoc-Netzwerken

DSDV

CGSR

DSR

AODV

Simulation von Ad-hoc-Netzwerken

Zusammenfassung


Ad-hoc-Netzwerke

EinführungEinführung

Ad-hoc-Netzwerke

ad-hoc = aus dem Augenblick

heraus entstanden (Duden)

besteht aus mehreren mobilen

Knoten

keine zentrale Administration

(keine Basistation)

jeder Knoten kann als

Datenquelle, Router oder

Datensenke arbeiten

Knoten haben drahtlose

Übertragungseinrichtung

MANET = Mobile Ad-hoc

NETwork


Ad-hoc-Netzwerke


Eigenschaften von Ad-hoc-Netzwerken

Knoten verfügen über

begrenzte Ressourcen

Energie

Speicher

asymmetrische Verbindungen

Multipath-Eigenschaft

Interferenzen

veränderliche Topologie

Hidden-Terminal-Problematik

An der Börse: Ad-hoc Meldungen beinhalten Informationen, die den Kurs einer Aktie beeinflussen können und müssen deshalb lt. Gesetz unverzüglich publik gemacht werden.


Ad-hoc-Netzwerke


Hidden-Terminal-Problematik (CSMA)

A B C

A kommuniziert mit B- C hört auf dem

Kanal und erkennt keine Übertragung

- C sendet Informationen gehen verloren


Ad-hoc-Netzwerke


Ad-hoc-Netzwerke vs. Sensornetzwerke

Größe

Ressourcen

Infrastruktur

unidirektional / multidirektional

Mobilität

...


Ad-hoc-Netzwerke

Routing in Ad-hoc-NetzwerkenRouting in Ad-hoc-Netzwerken

Routing = Art der Wegfindung durch ein Netzwerk

Warum sind klassische Routing-Algorithmen für Ad-hoc-Netzwerke ungeeignet?

Eine Wegwahl in Ad-hoc Netzwerken kann sich nicht auf Wissen der Vermittlungsschicht stützen.

Die Informationen von niedrigeren Schichten hinsichtlich der aktuellen Empfangssituation und Interferenz ist hilfreich, um einen richtigen Weg zu finden.

Zentralisierte Ansätze können wegen dynamischer Topologie und hohen Aufwand in Ad-hoc Netzwerken nicht richtig funktionieren .


Ad-hoc-Netzwerke


Strukturierung

Ad-hoc-Routing-Protokolle

proaktiv (table-driven) reaktiv (on-demand*)

* auch: Source-initiated on-demand

DSDV WRP

CGSR

AODV DSR LMR ABR

TORA SSR


Ad-hoc-Netzwerke


Bezeichnungen

DSDV = Destination-Sequenced Distance-Vector Routing (1994)

CGSR = Clusterhead Gateway Switch Routing (1997)

WRP = Wireless Routing Protocol (1996)

AODV = Ad-hoc On-Demand Distance-Vector Routing (1997)

DSR = Dynamic Source Routing (1996)

LMR = Lightweight Mobile Routing (1995)

TORA = Temporally Ordered Routing Algorithm (1997)

ABR = Associativity-Based Routing (1996)

SSR = Signal Stability Routing (1997)


Ad-hoc-Netzwerke


Zeitliche Einordnung

1994 1995 1996 20001997 1998 1999

proa

ktiv

reak

tiv

DSDV

WRP

CGSR

AODV

DSR

LMR TORA

ABR SSR


Ad-hoc-Netzwerke

DSDVDSDV

Destination-Sequenced Distance-Vector Routing

C. Perkins 1994

proaktiv (table driven)

basiert auf Bellman-Ford Routing-Algorithmus (1957)

schleifenfrei

Funktionsweise

jeder mobile Knoten des Netzwerkes unterhält eine Routing-Tabelle

R.-Tabelle enthält alle möglichen Zielknoten und die Anzahl der Teilstrecken (Hops) zum Ziel

jeder Eintrag enthält Seq.-Nummer veraltete Routen können erkannt werden keine Schleifen

Routing-Tabellen-Updates werden regelmäßig ausgesendet

Charles Perkins, Nokia


Ad-hoc-Netzwerke

DSDVDSDV

Routing-Tabellen-Updates (Broadcasts)

full dump

sämtliche Routinginformation eines Knoten wird gesendet

wird selten durchgeführt, da viele Daten zu senden

kann mehrere PDUs umfassen (Protocol Data Unit)

incremental

überträgt nur die Routing-Informationen, die sich seit dem letzten full dump geändert haben

sollte in eine PDU passen


Ad-hoc-Netzwerke

DSDVDSDV

New-Route-Broadcasts enthalten

Zieladresse

Sequenznummer der Information, die den Broadcast ausgelöst hat

Sequenznummer des Broadcast

es wird immer die Route mit der neuesten Sequenznummer gewählt

bei Gleichheit wird die Route mit der kleinsten Metrik gewählt

Knoten beobachten Einschwingzeit von Routen...

durch Verzögerung von Routen-Updates


Ad-hoc-Netzwerke

DSDVDSDVMH3 MH4

MH2MH6

MH7

MH8

MH5

MH1

Destination Next Hop Metric Seq. Nr. Install Stable_Data

MH1 MH2 2 S406_MH1 T001_MH4 Ptr1_MH1









Ad-hoc-Netzwerke

DSDVDSDVMH3 MH4

MH2MH6

MH7

MH8

MH5

MH1MH1

Destination Next Hop Metric Seq. Nr. Install Stable_Data










Ad-hoc-Netzwerke

CGSRCGSR

Clusterhead Gateway Switch Routing (proaktiv)

basiert auf DSDV

Unterschiede:

Adressierung

Netzwerkorganisation

einzelne Knoten werden zu Clusterköpfen bestimmt

Gateway-Knoten sind im Einzugsbereich mehrerer Clusterköpfe

Nachteil: Overhead durch Clusterbildung

Weiterentwicklung CGSR /LCC (Least Cluster Change)

LCC verringert Häufigkeit der Clusterneubildung

Mario Gerla, UCLA


Ad-hoc-Netzwerke

CGSRCGSR

Routing von Knoten 1 zu Knoten 8

1

2

3

5

8

4

7

6

einf. Knoten

Clusterkopf

Gateway


Ad-hoc-Netzwerke

CGSRCGSR

Funktionsweise

ein Paket, das ein Knoten aussendet, wird zuerst zum Clusterkopf

geroutet

vom Clusterkopf wird das Paket über einen Gateway zum nächsten

Clusterkopf weitergeleitet

der letzte Schritt wird solange wiederholt, bis der Clusterkopf des

Zielknotens erreicht wird

das Paket wird schließlich zum Zielknoten geroutet

jeder Knoten muss Cluster Member Table unterhalten


Ad-hoc-Netzwerke

CGSRCGSR

Vergleich DSDV - CGSR


Ad-hoc-Netzwerke

DSRDSR

Dynamic Source Routing (reaktiv)

Source Routing: Datenquelle kennt die komplette Route zum Empfänger

Datenpakete tragen komplette Route im Header

zwei grundlegende Mechanismen:

Route Discovery

wird veranlasst, wenn Knoten Szu Knoten D senden will und keineRoute kennt

Route Maintenance

wenn Knoten S erkennt, wenn Route zu D nicht mehr funktioniert und versucht eine Ausweichroute zu finden

David B. Johnson


Ad-hoc-Netzwerke

DSRDSR

Route Discovery

möchte S ein Paket an D versenden, schaut S zunächst in seinen Route Cache

wenn keine Route im Cache vorhanden Route Discovery

Bezeichnungen

S = Initiator des Route Discovery

D = Ziel des Route Discovery

D sendet Route Reply zurück an S

S A B C D"A" "A,B" "A,B,C" "A,B,C,D"

id=2 id=2 id=2 id=2


Ad-hoc-Netzwerke

DSRDSR

Route Maintenance

jeder Knoten entlang einer Route ist dafür verantwortlich, dass ein

Paket den nächsten Knoten der Route erreicht

im Beispiel: Knoten B wird so lange versuchen, das Paket zu C zu

übertragen, bis eine maximale Versuchszahl erreicht wird

anschließend wird eine Route Error-Nachricht an S zurückgesendet

S entfernt den toten Link aus seinem Route Cache und sucht nach

einer Alternativroute

falls Alternativroute im Cache Route wird gewählt

wenn keine Alternativroute im Cache S startet neuen Route

Request

S A B C DX


Ad-hoc-Netzwerke

DSRDSR

Beispiel mit mehreren möglichen Routen – Route Discovery

N1

N2

N3

N4

N5

N6

N7

N8

N1

N1

N1-N2

N1-N3

N1-N3-N4

N1-N2-N5

N1-N3-N4

N1-N3-N4

N1-N3-N4-N6

N1-N3-N4-N7


Ad-hoc-Netzwerke

DSRDSR

Beispiel mit mehreren möglichen Routen – Route Reply

N1

N2

N3

N4

N5

N6

N7

N8N1-N2-N5-N8

N1-N2-N5-N8N1-N2-N5-N8


Ad-hoc-Netzwerke

DSRDSR

Zusätzliche Eigenschaften des Route Discovery

Cachen von belauschten Routing-Informationen

ein Knoten, der ein Paket weiterleitet, kann die Routinginformationen dieses Paketes seinem eigenen Route Cache hinzufügen

Data-Packet, Route-Reply-Packet, Route-Request-Packet können dafür genutzt werden

Zwischenknoten antworten auf Route-Requests

erhält ein Knoten ein Route-Request und ist nicht der Zielknoten, kann er, wenn er die gewünschte Route im Cache hat, ein Route-Reply an den Initiator des Route-Request zurücksenden

Verhindern von Route-Reply-Stürmen

Zwischenknoten verzögern Route-Reply

Route-Request Hop-Limits

Route Requests, die Hop-Limit überschreiten werden verworfen


Ad-hoc-Netzwerke

DSRDSR

Beispiel Route-Reply-Sturm

G

F

E

D C

BA

BG

G

BG

ABG

CBG

- A sucht Route nach G- B, C, D, E, F erhalten Route Request- aller antworten quasi-gleichzeitig mit

Route aus dem Route-Cache Kollision!

??


Ad-hoc-Netzwerke

DSRDSR

Zusätzliche Route-Maintenance-Eigenschaften

Paket-Rettung (Packet-Salvaging)

rettet Paket, das einen Route-Error verursacht hat

Automatische Routen-Kürzung (Route Shortening)

unbenötigte Hops können ausgelassen werden

Cachen von Negativ-Informationen

tote Links werden nicht aus Route-Cache gelöscht, es wird stattdessen ein Hinweis gespeichert, dass der Link z. Zt nicht existiert.

Verstärkte Ausbreitung von Route-Error-Nachrichten

der Quellknoten einer Nachricht, die einen Route-Error verursacht hat, sendet einen Broadcast darüber an seine Nachbarn


Ad-hoc-Netzwerke

AODVAODV

Ad Hoc On-Demand Distance Vector Routing

basiert auf DSDV

verbessert DSDV durch Minimierung der

benötigten Broadcasts

Routen werden nur noch bei Bedarf ermittelt

Routingtabellen werden unterhalten

bei unbekannter Route Route Discovery

Datenquelle sendet RREQ-Paket per Broadcast

Datensenke antwortet mit RREP-Paket entlang

der gefundenen Route

Charles Perkins, Nokia

Elizabeth M. Royer, UCSB


Ad-hoc-Netzwerke

AODVAODV

Route Discovery

Annahme: Knoten S möchte Paket an Knoten D senden

Route in Routing-Tabelle von S?

wenn nicht Route Discovery wird gestartet

S erzeugt RREQ-Paket mit Zieladresse, Seq.-Nummer und

Broadcast-ID Broadcast

erhält ein Zwischenknoten das RREQ-Paket, schaut er nach,

ober er es schon kennt, wenn ja RREQ-Paket wird

verworfen

hat der Zwischenknoten eine aktuelle Route zu D, sendet er ein

RREP-Paket an S.

falls kein Zwischenknoten eine Route zu D kennt, dann sendet

schließlich D ein RREP an S.


Ad-hoc-Netzwerke

AODVAODV

Route Discovery Beispiel

Quelle

Ziel

Ausbreitung desRoute Request

Reverse Route Eintrag

Jeder Zwischenknoten erzeugt nur dann einen Reverse-Route-Eintrag, wenn er ein RREQ-Paket zum ersten mal erhält.

1


Ad-hoc-Netzwerke

AODVAODV

Route Maintenance

falls ein toter Link entdeckt wird Route Error (RERR)wird an Datenquelle gesendet

RERR enthält eine Liste mit allen Zielknoten, die nun nicht mehr erreichbar sind

Quelle Ziel

12

3

4

RERRRERR


Ad-hoc-Netzwerke

Vergleich DSR/AODVVergleich DSR/AODV

Gemeinsamkeiten

reaktiv (Routen werden nur bei Bedarf ermittelt)Route Discovery basiert auf Request- und Reply-ZyklenRouting-Informationen werden auch in Zwischenknoten gespeichert

Unterschiede

DSR hat Zugriff auf größere Menge von Routing-Informationen(Cache vs. Routing-Table)DSR antwortet auf alle Requests, die einen Zielknoten erreichen(Quelle lernt alternative Routen)AODV-Routing-Tabelle kennt dagegen nur einen Eintrag je ZielDSR kennt keinen Mechanismus, um veraltete Routen zu erkennen(obwohl einige veraltete Routen von RERR-Paketen gelöscht werden


Ad-hoc-Netzwerke

Simulation von Ad-hoc-NetzwerkenSimulation von Ad-hoc-Netzwerken

NS2 – Network Simulator

ereignisbasiert

objektorientiert, geschrieben in C++

OTcl-Interpreter als Frontend

C++, um Protokolle zu implementieren

OTcl für Konfiguration und Simulations-Setup

Graf. Frontend NAM: Network Animator


Ad-hoc-Netzwerke

Simulation von Ad-hoc-NetzwerkenSimulation von Ad-hoc-Netzwerken

Netzwerk-Simulator NS2

NAM – Network-Animator

Beispiel 2 Datenquellen, 1 Routing-Knoten mit Queue, 1 Datensenke


Ad-hoc-Netzwerke


Anteil der Pakete, die ihr Ziel erreichen (50 Knoten, 10 Datenquellen)

1500m x 300 m, random waypoint mobility


Ad-hoc-Netzwerke


Anteil der Pakete, die ihr Ziel erreichen (50 Knoten, 40 Datenquellen)



Ad-hoc-Netzwerke


Durschnittliche Verzögerung (50 Knoten, 10 Datenquellen)



Ad-hoc-Netzwerke





Ad-hoc-Netzwerke





Ad-hoc-Netzwerke

NetzwerksimulatorenNetzwerksimulatoren

kommerziell:

OPNET (Kosten: ab 10.000 €)

frei verfügbar:

NS2: http://www.isi.edu/nsnam/ns/

GlomoSim: http://pcl.cs.ucla.edu/projects/glomosim/

OMNeT++: http://whale.hit.bme.hu/omnetpp/

Documents

Hardwarenahe Programmierung / Vorlesung Ad-hoc-NetzwerkeAd-hoc-Netzwerke