Post on 14-Sep-2019
transcript
Software ubiquitärer Systeme (SuS)
Ad-hoc-Netzwerke
https://ess.cs.tu-dortmund.de/DE/Teaching/SS2017/SuS/
Constantin Timm, Olaf Spinczyk
olaf.spinczyk@tu-dortmund.dehttps://ess.cs.tu-dortmund.de/~os
AG Eingebettete SystemsoftwareInformatik 12, TU Dortmund
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 2
Inhalt● Motivation● Ad-hoc-Netzwerke● Ad-hoc-Routingprotokolle● Sicherheit in Ad-hoc-Netzwerken● Zusammenfassung
HardwareHardware
BetriebssystemBetriebssystem
MiddlewareMiddleware
DatenhaltungDatenhaltung
Anwendung/ProgrammierungAnwendung/Programmierung
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 3
Inhalt● Motivation● Ad-hoc-Netzwerke● Ad-hoc-Routingprotokolle● Sicherheit in Ad-hoc-Netzwerken● Zusammenfassung
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 4
Motivation
Hallo Stuhl 1!Hey Tür! Ist Stuhl 1 in
deiner Reichweite?
Klar!
Kannst du ihn fragen, ob er noch besetzt
ist?
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 5
Motivation
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 6
Motivation
Was braucht man hier? Richtig! Routingprotokolle.
Start
Ziel
Zwischenknoten
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 7
UbiCom-Netzwerke● Anforderungen
– Preiswert– Energiesparend– Robustheit (bzgl. dynamischer Topologieänderungen)– Sicherheit
● Konsequenzen– Einsatz preiswerter Technologie: Kleine Zellen durch geringe Reichweite, z.B.
Personal Area Networks– Minimierung der Kabelaufwands
● Nutzung vorhandener Infrastruktur: Telefonkabel, Stromkabel, Haut(!)● Kabelgebundene Grobverkabelung, kabelloser letzter Meter
– Ausnutzung von Lokationsinformation– Ad-Hoc-Kommunikation
● spontanes Hinzukommen/Verlassen● keine/einmalige Administration
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 8
Herausforderung Vielfalt● Unterschiedliche Netzwerktypen
– Anwendungsbereiche: Multimedia / Information, Echtzeit, Kontext
● Kommunikationsmodelle– Anwendungsorientiert (P2P)– Dienstorientiert (Master-Slave)
● Medien– oft mobil und kabellos– für Haustechnik und Multimedia auch kabelgebunden
● Durchsatz, Latenz- und Einbuchzeiten– Multimedia: hoher Durchsatz, längeres Einbuchen– Kontext: niedriger Durchsatz, kurzes Einbuchen
● Routingfähigkeiten– Netzwerk-Routing– Application Layer Bridges
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 9
Inhalt● Motivation● Ad-hoc-Netzwerke● Ad-hoc-Routingprotokolle● Sicherheit in Ad-hoc-Netzwerken● Zusammenfassung
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 10
„Mobile Ad-hoc Network“ (MANET)● Jochen Schiller, Mobilkommunikation:
„Ad-hoc-Netze kommen ohne jegliche Infrastruktur aus, insbesondere ohne eine ausgezeichnete Basisstation, welche den
Medienzugriff zentral steuert. Diese Netzvariante erlaubt die spontane, nicht vorab geplante Kommunikation zwischen mobilen Endgeräten, wobei einige oder alle Endgeräte auch
Daten von anderen Endgeräten weiterleiten können.“
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 11
Einordnung von MANETs
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 12
Eigenschaften von MANETs● Keine feste Infrastruktur● Dynamische Topologie
– Wegbrechen von Routen– Entstehung von neuen Routen
● Spontane Vernetzung– Jedes Gerät kann Endpunkt einer Kommunikation sein, aber auch
Daten einer Kommunikation weiterleiten müssen.
N1
N4
N2
N5
N3
N1
N4
N2
N5
N3
gute Verbindungschlechte Verbindung
Zeit = t1 Zeit = t2
N6N7
N6N7
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 13
Eigenschaften von MANETs (2)● Multihop-Umgebung● Stark begrenzte Bandbreite● Asymmetrische Verbindungen
– Durch unterschiedliche Sendeleistungen
● Beschränkte Möglichkeit der Energieversorgung– Abhängigkeit von Batterien oder Akkus– Große Anzahl von Geräten, damit in der Summe potentiell hoher
Energiebedarf
● Limitierte Möglichkeit das Netz vor physischen Einfluss zu schützen, z.B.– Denial-of-Service-Angriffe– Überwachungsangriffe– Verfälschen von Nachrichten
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 14
Inhalt● Motivation● Ad-hoc-Netzwerke● Ad-hoc-Routingprotokolle● Sicherheit in Ad-hoc-Netzwerken● Zusammenfassung
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 15
Routing im TCP/IP-Stack
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 16
Routing im ISO/OSI-Modell● Oft wird Routing mit der Wegsuche auf der
Vermittlungsschicht gleichgesetzt.● Aber: Es gibt Beispiele für Routingmechanismen auch auf
anderen Ebenen:– Bluetooth: Sicherungsschicht– P2P-Protokolle: Anwendungsschicht
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 17
Klassische Routingprotokolle● … aus dem Festnetzbereich versagen● Zu langsame Konvergenz
– Ad-Hoc-Netze weisen eine hohe Dynamik auf
● Zu großer Overhead– Typisch: geringe Bandbreite und geringe Rechenleistung
● Wichtige Metriken werden ignoriert(z.B. bei der Routenwahl)– Batterielaufzeit der Knoten– Zeit des Zusammenhalts der Knoten– Zuverlässigkeit der Verbindungen– Energiebedarf– …
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 18
Routingalgorithmen für Ad-Hoc-Netze… erfordern
● Hohe Skalierbarkeit● Flexibilität● Effizienz im Hinblick auf …
– Komplexität– Energieverbrauch – Speicherverbrauch
… werden intensiv erforscht● Dutzende Verfahren existieren● Implementierungen für Standard-Betriebssysteme, wie z.B. Linux
oder Windows, existieren– Nutzung von IP-Adressen zur Identifikation
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 19
Beispiel: DSDV● Destination-Sequenced Distance Vector Routing
– Ein Klassiker von 1994
● Routingtabellen werden per Broadcast verteilt– Updates werden periodisch („full dump“) und
bei Veränderung in der Topologie („incremental dump“) geschickt
– Aktualisierung von Routingtabellen-Zeilen bei eingehenden Updates:● neuere Sequenznummer: Übernahme der Zeile● gleiche Sequenznummer: Verwendung der Route mit der besseren Metrik (No. of Hops)
Destination Next Hop No. of Hops Seq. No. Install Time
A A 0 A 46 001000
B B 1 B 36 001200
C B 2 C 28 001500
Sicht von Knoten A
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 20
Ad-hoc Routingprotokolle● Flach
– FSLS Fuzzy Sighted Link State– FSR Fisheye State Routing– OLSR Optimised Link State Routing Protocol– TBRPF Topology Broadcast Based on Reverse
Path Forwarding– AODV Ad-hoc On Demand Distance Vector– DSR Dynamic Source Routing
● Hierarchisch– CGSR Clusterhead-Gateway Switch Routing– HSR Hierarchical State Routing– LANMAR Landmark Ad Hoc Routing– ZRP Zone Routing Protocol
● Geographisch– DREAM Distance Routing Effect Algorithm for Mobility– GeoCast Geographic Addressing and Routing– GPSR Greedy Perimeter Stateless Routing– LAR Location-Aided Routing
proaktiv
reaktiv
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 21
Proaktive Protokolle …● tauschen periodisch Kontrollnachrichten miteinander aus
– Linkstate-Protokolle● Jeder Router im Netzwerk teilt den anderen Knoten im Netzwerk den
Zustand der Verbindungen zu seinen Nachbarn mit● Jeder Router kennt explizit die komplette Topologie und kann mit dieser
eine Route berechnen, z.B. mit dem Shortest-Path-Algorithmus von Dijkstra
– Distanzvektor-Protokolle● Jeder Router kennt alle im Netzwerk vorhanden Knoten, aber nur in Form
des nächsten Hops und der Länge des Weges● Routenberechnung implizit durch Austausch der kompletten
Routingtabelle
● brauchen viel Bandbreite● sind relativ statisch
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 22
OLSR (1)● Optimized Link-State Routing● Spezifiziert in RFC (Request for Comments) 3626● Wichtige Eigenschaften
– Jeder Knoten hat globalen Überblick über alle Knoten im Netzwerk und den Verbindungen dort hin
● Erzeugt Last im Netzwerk!– Jeder Knoten berechnet die Route eigenständig
● Shortest-Path-Algorithmus– In OLSR haben nicht alle Knoten die gleichen Aufgaben
● Dynamisch gewählte „Multipoint-Relays“ übernehmen Aufgaben für umgebende Knoten
● Dadurch Reduzierung der Netzwerklast
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 23
OLSR (2)● Nachbarknoten (bis 2 Hops) werden mit
Hello-Nachrichten gefunden– Enthalten Adressen aller bekannten 1-Hop-Nachbarn– Werden nicht weitergeleitet– Basis für die Auswahl der Multipoint-Relays
● Minimale Menge an Knoten, um alle 2-Hop-Knoten erreichen zu können
● Kontrollpakete (TC) werden periodisch erstellt – Enthält Knotenadresse, Sequenznummer, Nachbarknoten mit
Distanzinformationen– Werden per Broadcast über Multipoint-Relays verteilt– Knoten erhält Distanzinformationen von allen anderen Knoten
● Komplette Netzwerktopologie wird aufgebaut
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 24
Standard Optimiert
OLSR (3)● Unterschied zu anderen Linkstate-Algorithmen
– Optimized LSR– Verteilte Auswahl sogenannter Multi-Point-Relays,
die Kontrollnachrichten weiterleiten dürfen● Es müssen aber alle Knoten im Netzwerk erreichbar sein
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 25
Reaktive Protokolle● tauschen Kontrollnachrichten nur aus, wenn eine Route
benutzt werden soll● brauchen weniger Bandbreite als proaktive Protokolle und
sind dynamischer● Die Routen müssen aus nur teilweiser Kenntnis des
Netzwerks errechnet werden
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 26
AODV● Ad-hoc On-Demand Distance Vector
– Reaktives Routingprotokoll
● Spezifiziert in RFC (Request for Comments) 3561– Ausgelegt für IPv4-Netze– Beliebige Anzahl von Knoten im Netzwerk
● Wichtige Eigenschaften– Knoten kennen nur den nächsten Teilnehmer einer Route und die
Länge der Route– Einfachpfad-Algorithmus
● Definiert zwei Routingmechanismen– Route Discovery– Route Maintenance
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 27
● Route Discovery– Zwei Routing-Nachrichtentypen zum Routenaufbau
● „Route-Request-Nachricht“ (RREQ) per Broadcast in Richtung Ziel(an die Adresse 255.255.255.255 bei IP)
● „Route Reply-Nachricht“ (RREP) per Unicast zurück zur Quelle– Bei bidirektionalen Verbindungen zwischen den Knoten wird auch eine
bidirektionale Route aufgebaut
● Route Maintenance– “Route-Error-Nachricht” (RRER) wird losgeschickt, wenn eine
gebrochenen Route entdeckt wird, z.B. durch einen Fehler auf der Sicherungsschicht (MAC-Schicht)
– RRER-Nachricht wird an Nachbarn geschickt
AODV
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 28
AODV
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 29
DSR● Dynamic Source Routing
– Reaktives Routingprotokoll
● Spezifiziert in RFC (Request for Comments) 4728– Ausgelegt für IPv4-Netze– Höchstanzahl der Zwischenknoten u.a. festgelegt durch vorhandenen
Platz im IP-Header (<10)
● Wichtige Eigenschaften– Quelle kennt die komplette Route– Route wird im Datenpaket mitgeschickt
● Definiert zwei Routingmechanismen– Route Discovery– Route Maintenance
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 30
DSR● Route Discovery
– Nur wenn wirklich ein Weg zum Senden von Daten zu einem bestimmten Ziel benötigt wird und noch keiner vorhanden ist
– Aussenden eines Broadcast-Pakets mit Zieladresse und Sequenznummer
– Bei Empfang eines Broadcast-Pakets● falls Empfänger, dann Rücksendung eines Route Replys an Absender● falls Paket bereits früher erhalten (Sequenznummer), verwerfen● sonst eigene Adresse anhängen und als Broadcast weiterleiten
– Das Ziel kann den Weg auslesen und auf diesem antworten (symmetrische Pfade!) oder startet das gleiche Verfahren in Gegenrichtung
– Sender erhält Paket mit aktuellem Weg (Adressliste) zurück
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 31
DSR
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 32
DSR● Route Maintenance
– Nach dem Senden● Warten auf die Quittung auf Sicherungsschicht● Mithören auf dem Medium, ob Paket weitergeleitet wird ● Anforderung einer expliziten Bestätigung
– Falls Probleme erkannt werden, kann der Sender informiert oder lokal ein neuer Weg gesucht werden
– nur während ein Weg aktuell benutzt wird, muss dafür gesorgt werden, dass er weiterhin funktioniert
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 33
Hierarchische Protokolle …● sehen unterschiedliche Rollen für die Knoten vor
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 34
CGSR● Clusterhead-Gateway Switch Routing
– Eigenschaften● Das Netzwerk wird in sich überlappende Cluster aufgeteilt● Für jedes Cluster wird ein sogenannter Clusterhead ausgewählt● Ein Knoten, der zu zwei Clustern gehört, wird Gateway genannt
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 35
CGSR● CGSR benutzt ein Distanzvektor-Protokoll
– Jeder Knoten speichert zwei Routingtabellen● Eine Distanzvektor-Routingtabelle, die zusätzlich zu den “normalen”
Routingeinträgen einen Routingeintrag mit der Route zum Clusterhead für jedes Cluster beinhaltet
● Eine “Cluster Member”-Tabelle, die für jeden Knoten den Clusterhead speichert
● CGSR reduziert die Größe der Routingtabelle signifikant im Hinblick auf klassische Distanzvektorprotokolle
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 36
Bio-inspirierte Routing-Protokolle …● ahmen das Verhalten der Natur nach, z.B.
– Bienen-Schwärme (z.B. BeeAdHoc)– Ameisenkolonien (z.B. AntHocNet)
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 37
AntHocNet● Agenten-basierter Algorithmus● Multipfad-Algorithmus● Basiert auf den „Ant Colony Optimization“ (ACO)–Prinzipien
– Ameisen haben folgende Eigenschaften:● Futtergebiete können erkundet werden ohne globale Sicht auf die
Oberfläche● Können Futter finden und dieses zum Hügel zurückbringen● Werden den kürzesten Pfad benutzen
– Ameisen arbeiten im Team:● … indem sie Pheromone hinterlassen● Pheromone dienen zur Kommunikation mit den anderen Ameisen
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 38
AntHocNet (2)● Wenn eine Datenübertragung an Knoten S mit Senke D startet,
wird überprüft, ob aktuelle Routinginformationen vorhanden sind.
● Falls nicht, werden Ameisen-ähnliche Agenten – die “Forward Ants” – losgeschickt, um eine Route zu D zu finden.
● Diese Ameisen sammeln Informationen über die Qualität der von ihnen benutzten Route. Am Ziel werden sie zu “Backward Ants”, die den Pfad zurückgehen und an den besuchten Knoten die Routingtabelle erneuern.
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 39
AntHocNet (3)● Wenn die Routen aufgebaut sind und die Datenübertragung
läuft, sendet S proaktive „Forward Ants“ zum Knoten D. Diese folgen der Pheromonspur genauso wie die Datenpakete und haben zusätzlich die Fähigkeit, alternative Routen zu erkunden.
● Im Falle von Verbindungsproblemen versuchen die Knoten, die Route lokal zu erneuern, oder schicken Warnmitteilungen an ihre Nachbarknoten.
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 40
Inhalt● Motivation● Ad-hoc-Netzwerke● Ad-hoc-Routingprotokolle● Sicherheit in Ad-hoc-Netzwerken● Zusammenfassung
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 41
Sicherheit in MANETs● Kommunikationspartner sind per Definition nicht
vertrauenswürdig, weil …– Offenes Medium– Teilnehmende Geräte können leicht in falsche Hände geraten– Keine zentrale Instanz– Dynamische Topologie
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 42
Sicherheit in MANETs (2)● Adhoc-Routingprotokoll-Spezifikationen sind oft nicht auf
Sicherheit eingestellt, z.B. :
– Vertraulichkeit der Daten: Informationen können mitgelesen werden– Integrität der Daten: Verfälschte Kontrollnachrichten
Currently, OLSR does not specify any special security measures. As a proactive routing protocol, OLSR makes a target for various attacks.
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 43
● Selfishness– Kontrollpakete nicht weiterleiten– Kontrollpakete zum eigenen Vorteil ändern
● Black-Hole-Angriff– Datenpakete nicht weiterleiten– Möglichst viele Routen über sich selbst leiten
Angriffsszenarien
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 44
Angriffsszenarien (2)● Denial of Service (DoS)
– Funkverbindung stören– Unnötige Pakete schicken
● Eavesdropping– Weitergeleitete Pakete mitlesen
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 45
SAODV● Grundgedanke: Kontrollnachrichten schützen
– Normale Datenpakete können verschlüsselt werden
● SAODV basiert auf AODV (Secure AODV)● Schützt feste und flexible Bereiche der Kontrollnachrichten
Route Request Route Reply
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 46
SAODV (2)● Digitale Signatur für nicht veränderbare Felder● Hash Chains schützen den Hop Count
– Bei jedem RREQ wird ein Seed-Wert erzeugt und ein Max_Hop_Count auf die TTL des AODV gesetzt.Max_Hop_Count und Top_Hash sind durch Signaturen geschützt:
Hash = seedTop_Hash = hMax_Hop_Count(seed)
– Beim Empfangen eines RREQ wird der Hop_Count geprüft …Top_Hash == hMax_Hop_Count–Hop_Count(Hash) ?
– und vor dem Losschicken wird die Hash-Funktion einmal auf den aktuellen Hash-Wert angewendet
Hash = h(Hash)
Hinweis zur Notation:h2(x) bedeutet h(h(x))Hinweis zur Notation:h2(x) bedeutet h(h(x))
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 47
Inhalt● Motivation● Ad-hoc-Netzwerke● Ad-hoc-Routingprotokolle● Sicherheit in Ad-hoc-Netzwerken● Zusammenfassung
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 48
Zusammenfassung● Ad-Hoc-Netzwerke sind für ubiquitäre Systeme wichtig
– mobile Knoten– dynamische Topologieänderungen
● Ad-Hoc-Routing-Protokolle berücksichtigen die speziellen Anforderungen– Proaktive Protokolle verbreiten permanent Routing-Infos im Netz
● Kontinuierlicher Ressourcenverbrauch (Bandbreite, Energie, …)● Schneller Verbindungsaufbau
– Reaktive Protokolle ermitteln Routen auf Anforderung● Kommen besser mit hoher Dynamik klar
– Wichtige weitere Ansätze● Hierarchische Verfahren: Reduzieren den Overhead● Bio-inspirierte Verfahren: Sind sehr flexibel
● Bei der Sicherheit gibt es prinzipielle Probleme– Man kann niemandem trauen!
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 49
Referenzen● Jochen Schiller, Mobilkommunikation, Addison-Wesley
– Dazu: Folienmaterial von der TU Berlin
● Gianni Di Caro, AntHocNet: an Ant-Based HybridRouting Algorithm for Mobile Ad Hoc Networks
● Alexander Berner, Sicherheitsaspekte beim Routing in MANETs
● Anouck Schlesser, Ad-hoc Workshop 2004, AODV, OLSR● D. Johnson, RFC 4728, The Dynamic Source Routing Protocol
(DSR) for Mobile Ad hoc Networks for IPv4
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 50
Referenzen● Christophe Ronkar, Ad-Hoc Workshop 2004, Reactive Routing,
DSR● Serge Kaiser, Ad-Hoc Workshop 2004, DSDV● S. Corson, RFC 2501, Mobile Ad hoc Networking (MANET):
Routing Protocol Performance Issues and Evaluation Considerations
● C. Perkins, RFC 3561, Ad hoc On-Demand Distance Vector (AODV) Routing
● Manel Guerrero Zapata, Secure Ad hoc On-Demand Distance Vector (SAODV) Routing
● Michael Beigl, Universität Karlsruhe, Ubiquitäre Informationstechnologien
● Prof. Dr. Otto Spaniol, Dr. rer. nat. Dirk Thißen, Lehrstuhl für Informatik IV, RWTH Aachen, Mobilkommunikation
13.06.2017 SuS: 04.1 Ad-hoc-Netzwerke 51
Referenzen● Johannes Faigle, Ad-hoc Routing Protocols● Gupta, WMU, Department of Computer Science, Wireless
Communications & Networks, Scalable Routing Protocols for Mobile Ad Hoc Networks