Manuel Beetz Marcus Gottwald

Ad-hoc-NetzwerkeAd-hoc-Netzwerkeundund

Routing inRouting inAd-hoc-NetzwerkenAd-hoc-Netzwerken

Folie 2

Ad-hoc-Netzwerke „Ad hoc“: [lat] aus dem Moment heraus

(entstanden) Netzwerke mit nicht gleichbleibender

Infrastruktur Wired/wireless, mobile/immobile „MANET“: Mobile Ad-hoc NETwork,

üblicherweise schnurlos Autokonfiguration Relaying

Folie 3

Anwendungen 1 Conferencing:

Administrativa, Beispiele, Netzwerkzugriff Home Networking:

LAN-Partys, Kühlschrank-Inhalt, Notebooks Personal Area Networks:

Handy, PDA, Notebook; Bluetooth Emergency/Disaster:

Feuerwehr, Polizei, Netzausfälle

Folie 4

Anwendungen 2 Verkehr:

Stau, Unfall, Routenplanung, Blitzer, Parkplatz, Unterhaltung, Tourismus, ...

Terminodes, Prenzlnet, WaveWAN:großflächige Netzwerk-Versorgung

Electronic Dust Militärische Nutzung:

line of sight, temporäre Lager

Folie 5

Herausforderungen Energieverbrauch:

Forwarding, Beaconing Abdeckung (Coverage):

asymmetrische Funkverbindungen Netzwerk-Verkehr:

Daten-Verlust auf Funkstrecken Vermittlung und Wegewahl (Routing):

Dynamik, später mehr

Folie 6

Sicherheit der Daten Sicherheit =

Vertraulichkeit, Integrität und Verfügbarkeit Vertraulichkeit: Verschlüsselung Verschlüsselung:

Rechenleistung, Ende-zu-Ende? Integrität:

auf Schicht 1 oder bei Verschlüsselung Verfügbarkeit: großes Problem

Folie 7

Sicherheit 2 Sicherheit für mobile Teilnehmer:

Relaying Sicherheit für vorhandene Infrastruktur:

unbefugter Zugriff auf Ad-hoc-Netz, Interessenkonflikt:

Autokonfiguration/Sicherheit

Folie 8

Techniken IEEE 802.11b:

„Wavelan“, „Orinoco“ Bluetooth:

Personal Operating Space;Pikonetze, Scatternets

IEEE 802.15:Wireless Personal Area Networks

Folie 9

Routing Warum Routing? Warum neue Verfahren? Warum nicht RIP oder OSPF?

Folie 10

Routing — Ad-hoc-Netze Besonderheiten in Ad-hoc-Netzwerken:

Meist beschränkte Ressourcen (Energie, Sendeleistung)

Dynamische Netztopologie Asymmetrie der Verbindungen Interferenzen und Störungen

Folie 11

Verfahren

Link-State Distance-Vector

Proactive OSPF RIP, DSDV

Reactive DSR AODV

Folie 12

Link-State Jede Station erzeugt Sicht auf das gesamte

Netzwerk Wegewahl durch geeignete Algorithmen

(Dijkstra) Nicht geeignet für hochdynamische Netze

Folie 13

Distance-Vector Nur lokale Informationen notwendig Austausch von Informationen zur Wegewahl

nur mit den Nachbarn Gefahr von Kreisen Count-to-Infinity-Problem

Folie 14

Proactive / Reactive Proactive:

• Wege werden im Voraus ermittelt• Geringe Latenz• Viele überflüssige Routen gespeichert

Reactive:• Wege werden nach Bedarf ermittelt• Höhere Latenz• Kleine Routing-Tabellen

Folie 15

Modellierung als Graph Stationen im Netzwerk

= Knoten im Graph Funkverbindung zwischen Stationen

= Kante im Graph Routing im Netzwerk

= Wegewahl im Graph

Folie 16

Routing-Algorithmen Destination-Sequenced Distance-Vector

(DSDV)

Dynamic Source Routing (DSR)November 2001

Ad-Hoc On-Demand Distance-Vector (AODV)Januar 2002

Zone Routing Protocol (ZRP)Juni 2001

Folie 17

Verfahren

Link-State Distance-Vector

Proactive OSPF RIP, DSDV

Reactive DSR AODV

Folie 18

DSDV — Routing-Tabelle

Routing-Eintrag• Destination• Metric• Destination Sequence Number

Destination-Sequenced Distance-Vector Routing-Tabelle:

ein Eintrag für jeden bekannten Teilnehmer

Folie 19

DSDV — FunktionsweiseDestination-Sequenced Distance-Vector

Periodischer Austausch von Routing-Tabellen mit allen Nachbarn (ähnlich RIP)

Umgehende Benachrichtigung aller Nachbarn bei bedeutenden Veränderungen

Unterscheidung alter und neuer Nachrichten mittels vom Absender mitgeschickter Sequence Number

Folie 20

DSDV — BewertungDestination-Sequenced Distance-Vector

Vorteile:• Routen jederzeit verfügbar• Schnelle Reaktion auf Veränderungen

Nachteile:• Hoher Steuerungsaufwand• Permanenter Netzwerk-Verkehr auch

ohne zu übertragende Nutzdaten

Folie 21

Verfahren

Link-State Distance-Vector

Proactive OSPF RIP, DSDV

Reactive DSR AODV

Folie 22

DSR — FunktionsweiseDynamic Source Routing

Routen nur nach Bedarf ermittelt Nutzung einer Route bis zum Auftreten eines

Fehlers Wegewahl allein durch Absender

Folie 23

DSR — Route RequestDynamic Source Routing

Aussenden eines „Route Request“-Pakets Weiterleitung von Requests mittels

Broadcast (Fluten des Netzes)

Folie 24

DSR — Route ReplyDynamic Source Routing

Zielstation sendet „Route Reply“ an Initiator der Suche über gefundenen Weg.

Folie 25

DSR — Route MaintenanceDynamic Source Routing

„Route Error“-Paket bei Unterbrechung der vorgegebenen Route („Source Route“)

Folie 26

DSR — BewertungDynamic Source Routing

Vorteile:• Wenig überflüssiger Netzwerkverkehr• Erhöhte Sicherheit durch Source Routing• Nutzung unidirektionaler

Funkverbindungen möglich Nachteile:

• Größere Latenz

Folie 27

Verfahren

Link-State Distance-Vector

Proactive OSPF RIP, DSDV

Reactive DSR AODV

Folie 28

AODV — FunktionsweiseAd-hoc On-Demand Distance-Vector

Distance-Vector-Verfahren Austausch von Routing-Tabellen nur bei

Bedarf

Folie 29

AODV — Reverse PathAd-hoc On-Demand Distance-Vector

Aussenden eines „Route Request“-Pakets

Jeder Empfänger merkt sich vorläufig den Weg zur suchenden Station und leitet die Anfrage weiter.

Folie 30

AODV — Forward PathAd-hoc On-Demand Distance-Vector

Zielstation sendet „Route Reply“ über gefundenen Weg an Initiator der Suche.

Gefundener Weg wird damit bestätigt

Unbenutzte Wege verfallen

Folie 31

AODV — MaintenanceAd-hoc On-Demand Distance-Vector

Funkverbindungen auf bestätigten Wegen werden mittels „hello messages“ überwacht.

Bei Unterbrechung wird ein Update der Routing-Tabelle ausgesandt.

Bei Bedarf wird eine neue „Route Discovery“ ausgeführt.

Folie 32

AODV — BewertungAd-hoc On-Demand Distance-Vector

Vorteile:• Geringere Latenz• Wenig überflüssiger Netzwerkverkehr

Nachteile:• ???

Folie 33

ZRP — FunktionsweiseZone Routing Protocol

Setzt sich zusammen aus: IntrAzone Routing Protocol (IARP) IntErzone Routing Protocol (IERP) Bordercast Routing Protocol (BRP)

Folie 34

ZRP — Verfahren

Link-State Distance-Vector

Proactive IARP BRP

Reactive IERP

Zone Routing Protocol

Folie 35

ZRP — IARPIntrAzone Routing Protocol

Verwendet Link-State-Verfahren für Stationen in der eigenen Routing-Zone

Folie 36

ZRP — IERPIntErzone Routing Protocol

Verwendet Distance-Vector-Verfahren für Stationen außerhalb der eigenen Routing-Zone

Folie 37

ZRP — BRPBordercast Routing Protocol

Erreichen von Stationen außerhalb der Routing-Zone mittels Weiterleitung über Bordernodes

Folie 38

ZRP — BewertungZone Routing Protocol

Vorteile:• Wenig überflüssiger Netzwerkverkehr• Geringe Latenz• Robuste Routen

Nachteile:• Aufwendig zu implementieren

Folie 39

Routing-Algorithmen Wahl des Routing-Verfahrens abhängig von:

• Dynamik der Teilnehmer• Ressourcen der Geräte• Größe des Netzwerks

Folie 40

Cluster-Based Networks Unterteilung von Netzwerken in kleine

administrative Einheiten Stationen übernehmen spezielle Aufgaben in

der Einheit Cluster-Hierarchien können Routing

vereinfachen Clusterbildung und Aufgabenverteilung

erfolgt automatisch.

Folie 41

Alternative MetrikenLeast Interference Routing

Bisher: Metrik = #Hops Wegewahl anhand der geringsten Interferenz Maß für Interferenz einer Station:

Anzahl der Nachbarstationen