1 Wireless Sensor Networks 5. RoutingChristian Schindelhauer Technische Fakultät Rechnernetze und Telematik Albert-Ludwigs-Universität Freiburg Version

2 ISO/OSI Reference model7. Application Data transmission, , terminal, remote login 6. Presentation System-dependent presentation of the data (EBCDIC / ASCII) 5. Session start, end, restart 4. Transport Segmentation, congestion 3. Network Routing 2. Data Link Checksums, flow control 1. Physical Mechanics, electrics

3 Protocols of the InternetApplication Telnet, FTP, HTTP, SMTP ( ), ... Transport TCP (Transmission Control Protocol)

UDP (User Datagram Protocol) Network IP (Internet Protocol) + ICMP (Internet Control Message Protocol) + IGMP (Internet Group Management Protocol) Host-to-Network LAN (e.g. Ethernet, Token Ring etc.)

4 TCP/IP Layers 1. Host-to-NetworkNot specified, depends on the local network,k e.g. Ethernet, WLAN , PPP, DSL 2. Routing Layer/Network Layer (IP - Internet Protocol) Defined packet format and protocol Routing Forwarding 3. Transport Layer TCP (Transmission Control Protocol) Reliable, connection-oriented transmission Fragmentation, Flow Control, Multiplexing UDP (User Datagram Protocol) hands packets over to IP unreliable, no flow control 4. Application Layer Services such as TELNET, FTP, SMTP, HTTP, NNTP (for DNS), ...

5 Example: Routing between LANsStevens, TCP/IP Illustrated

6 Routing Tables and Packet ForwardingIP Routing Table contains for each destination the address of the next gateway destination: host computer or sub-network default gateway Packet Forwarding IP packet (datagram) contains start IP address and destination IP address if destination = my address then hand over to higher layer if destination in routing table then forward packet to corresponding gateway if destination IP subnet in routing table then forward packet to corresponding gateway otherwise, use the default gateway

7 IP Packet Forwarding IP -Packet (datagram) contains... Packet HandlingTTL (Time-to-Live): Hop count limit Start IP Address Destination IP Address Packet Handling Reduce TTL (Time to Live) by 1 If TTL ≠ 0 then forward packet according to routing table If TTL = 0 or forwarding error (buffer full etc.): delete packet if packet is not an ICMP Packet then send ICMP Packet with start = current IP Address destination = original start IP Address

8 Static and Dynamic RoutingStatic Routing Routing table created manually used in small LANs Dynamic Routing Routing table created by Routing Algorithm Centralized, e.g. Link State Router knows the complete network topology Decentralized, e.g. Distance Vector Router knows gateways in its local neighborhood

9 Intra-AS Routing Routing Information Protocol (RIP)Distance Vector Algorithmus Metric = hop count exchange of distance vectors (by UDP) Interior Gateway Routing Protocol (IGRP) successor of RIP different routing metrics (delay, bandwidth) Open Shortest Path First (OSPF) Link State Routing (every router knows the topology) Route calculation by Dijkstra’s shortest path algorithm

10 Distance Vector Routing ProtocolDistance Table data structure Each node has a Line for each possible destination Column for any direct neighbors Distributed algorithm each node communicates only with its neighbors Asynchronous operation Nodes do not need to exchange information in each round Self-terminating exchange unless no update is available

11

12

13

14 Distance Vector Routing Examplefrom A
to via entry B C 1 8 6 3 D 2 9 E 7 4

15 via entry B C 1 3 D E via A C D 1 3 E 8 via A B E 3 5 D 8 1Informatik III Winter 2007/08 Rechnernetze und Telematik Albert-Ludwig-Universität Freiburg Christian Schindelhauer from A
to via entry B C 1 - 3 D E from B to via entry A C D 1 - 3 E 8 from C to via entry A B E 3 - 5 D 8 1

16 from B to via A C D 1 - 5 E 8 from C to via A B E 3 - 5 D 8 1Informatik III Winter 2007/08 Rechnernetze und Telematik Albert-Ludwig-Universität Freiburg Christian Schindelhauer from B
to via Entry A C D 1 - 5 E 8 from C
to via Entry A B E 3 - 5 D 8 1 from B
to via Entry A C D 1 8 - 5 13 E 6 from C
to via Entry A B E 3 6 - 5 D 8 13 1

17 “Count to Infinity” - ProblemGood news travels fast A new connection is quickly at hand Bad news travels slowly Connection fails Neighbors increase their distance mutally "Count to Infinity" Problem

18 “Count to Infinity” - Problem

19 Link-State Protocol Link state routersexchange information using Link State Packets (LSP) each node uses shortest path algorithm to compute the routing table LSP contains ID of the node generating the packet Cost of this node to any direct neighbors Sequence-no. (SEQNO) TTL field for that field (time to live) Reliable flooding (Reliable Flooding) current LSP of each node are stored Forward of LSP to all neighbors except to be node where it has been received from Periodically creation of new LSPs with increasing SEQNO Decrement TTL when LSPs are forwarded

20 Characteristics of routing in mobile ad hoc networksMovement of participants Reconnecting and loss of connection is more common than in other wireless networks Especially at high speed Other performance criteria Route stability in the face of mobility energy consumption

21 Unicast Routing Variety of protocolsAdaptations and new developments No protocol dominates the other in all situations Solution: Adaptive protocols?

22 Routing in MANETs Routing Protocol typesDetermination of message paths Transport of data Protocol types proactive Routing tables with updates reactive repairm of message paths only when necessary hybrid combination of proactive and reactive

23 Routing Protocols Proactive Routes are demand independentStandard Link-State und Distance- Vector Protocols Destination Sequenced Distance Vector (DSDV) Optimized Link State Routing (OLSR) Reactive Route are determined when needed Dynamic Source Routing (DSR) Ad hoc On-demand Distance Vector (AODV) Dynamic MANET On-demand Routing Protocol Temporally Ordered Routing Algorithm (TORA) Hybrid combination of reactive und proactive Zone Routing Protocol (ZRP) Greedy Perimeter Stateless Routing (GPSR)

24 Trade-Off Latency because of route discoveryProactive protocols are faster Reactive protocols need to find routes Overhead of Route discovery and maintenance Reactive protocols have smaller overhead (number of messages) Proactive protocols may have larger complexity Traffic-Pattern and mobility decides which type of protocol is more efficient

25 Flooding Algorithm Sequence numbers Packet always reaches the targetSender S broadcasts data packet to all neighbors Each node receiving a new packet broadcasts this packet if it is not the receiver Sequence numbers identifies messages to prevent duplicates Packet always reaches the target if possible

26 Informatik III Winter 2007/08Rechnernetze und Telematik Albert-Ludwig-Universität Freiburg Christian Schindelhauer

27 Packet for Receiver F Informatik III Winter 2007/08Rechnernetze und Telematik Albert-Ludwig-Universität Freiburg Christian Schindelhauer Packet for Receiver F

28 Possible collision at B Informatik III Winter 2007/08Rechnernetze und Telematik Albert-Ludwig-Universität Freiburg Christian Schindelhauer Possible collision at B

29 Receiver F gets packet and stopsInformatik III Winter 2007/08 Rechnernetze und Telematik Albert-Ludwig-Universität Freiburg Christian Schindelhauer Receiver F gets packet and stops Nodes G, H, I do not receive the packet

30 Flooding Advantage Disadvantage simple and robustthe best approach for short packet lengths, small number of participants in highly mobile networks with light traffic Disadvantage High overhead Broadcasting is unreliable lack of acknowledgements hidden, exposed terminals lead to data loss or delay