4003-543/4005-742 Ad Hoc Networks Module 3. Routing and Transport -- Lecture Notes Prof. Alan Kaminsky Rochester Institute of Technology -- Department of Computer Science Taxonomy of Ad Hoc Routing Protocols Proactive versus reactive Proactive: Routes to all destinations maintained at all times Pro: Can start forwarding data traffic immediately Con: Extra resources (CPU time, memory space, network bandwidth, battery power) consumed to maintain unused routes Best if there is much data traffic between most devices Reactive: Routes maintained only between sources/destinations with active data traffic Pro: Resources consumed only for the necessary routes Con: A route must be discovered if one does not exist; this will delay the forwarding of data traffic Best if there is little data traffic between few devices (Internet routing)   Communication pattern Point-to-point Broadcast Multicast   Taxonomy of ad hoc routing protocols     Point-to-point Broadcast Multicast Proactive DSDV OLSR TBRPF     Reactive AODV DSR       Acronyms Destination Sequenced Distance Vector (DSDV) Optimizing Link State Routing (OLSR) Topology Dissemination Based on Reverse Path Forwarding (TBRPF) Ad Hoc On-Demand Distance Vector (AODV) Dynamic Source Routing (DSR) Distance Vector Routing and DSDV Distance vector routing is used by the Internet's Routing Information Protocol (RIP) RFC 1058 (June 1988) -- "Routing Information Protocol" RFC 1388 (January 1993) -- "RIP Version 2 Carrying Additional Information" RFC 1723 (November 1994) -- "RIP Version 2 Carrying Additional Information" RFC 2453 (November 1998) -- "RIP Version 2"   Information maintained by each router Neighbor table Cost of the link to each directly connected neighbor Router's own distance vector Distance to each destination from this router Neighboring routers' distance vectors Distance to each destination reported by each neighboring router Forwarding table First hop for routing packets to each destination   Algorithm (quoted from Radia Perlman, Interconnections, Second Edition (Addison Wesley, 2000), pages 299-303)   Each router is configured with its own ID.   Each router is also configured with a number to use as the cost of each link. (Or a fixed value such as 1 is used as the cost of each link, or some sort of measurement is done to calculate a number to use as the cost.)   Each router starts with a distance vector consisting of the value "0" for itself and the value "infinity" for every other destination.   Each router transmits its distance vector to each of its neighbors whenever the information changes (as well as when a link to a neighbor first comes up and probably also periodically).   Each router saves the most recently received distance vector from each of its neighbors.   Each router calculates its own distance vector, based on minimizing the cost to each destination, by examining the cost to that destination reported by each neighbor in turn and then adding the configured cost of the link to that neighbor.   The following events cause recalculation of the distance vector.   Receipt from a neighbor of a distance vector containing different information than before.   Discovery that a link to a neighbor has gone down. In that case, the distance vector from that neighbor is discarded before the distance vector is recalculated.   Destination Sequenced Distance Vector routing is a modification of distance vector routing that eliminates routing loops while reacting to topology changes Each distance vector message is tagged with a sequence number Each distance vector entry is tagged with the sequence number of the message from which the distance information was derived Each node keeps only the highest-sequence-numbered distance vector entries -- more-recent paths override less-recent paths   DSDV is a proactive routing protocol   DSDV assumes all links are bidirectional   Further information: Charles E. Perkins and Pravin Bhagwat. Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers. In SIGCOMM '94: Proceedings of the conference on Communications architectures, protocols and applications, pages 234-244, 1994. Charles E. Perkins and Pravin Bhagwat. DSDV Routing over a Multihop Wireless Network of Mobile Computers. In Charles E. Perkins, editor, Ad Hoc Networking (Addison-Wesley, 2001), pages 53-74. Link State Routing and OLSR Link state routing is used by the Internet's Open Shortest Path First (OSPF) protocol RFC 1131 PDF (October 1989) -- "OSPF Specification" RFC 1247 (July 1991) -- "OSPF Version 2" RFC 1583 (March 1994) -- "OSPF Version 2" RFC 2178 (July 1997) -- "OSPF Version 2" RFC 2328 (April 1998) -- "OSPF Version 2"   Algorithm (quoted from Radia Perlman, Interconnections, Second Edition (Addison Wesley, 2000), pages 307-308)   Each router is responsible for meeting its neighbors and learning their names.   Each router constructs a packet known as a link state packet, or LSP, which contains a list of the names of and cost to each of its neighbors.   The LSP is somehow transmitted to all the other routers, and each router stores the most recently generated LSP from each other router.   Each router, armed now with a complete map of the topology (the information in the LSPs yields complete knowledge of the graph), computes routes to each destination.   How each step is done: Periodic "hello" messages Link costs typically hops LSPs are flooded throughout the network -- the most complicated part of the whole algorithm Shortest path algorithm, typically Dijkstra's Algorithm (see any algorithms textbook)   Optimized Link State Routing is a modification of link state routing that reduces (optimizes) the amount of messaging needed in Step 3 Each node selects a subset of the node's one-hop neighbors to act as multipoint relays (MPRs) All the node's two-hop neighbors are reachable from the node's MPR neighbors A node broadcasts link state packets to its one-hop neighbors, but only the MPR neighbors relay the link state packets further In a densely connected network, this greatly reduces the number of link state broadcasts   At Step 4, OLSR chooses routes using only MPRs as intermediate nodes between the source and destination This reduces the size of the link state packets This reduces the storage needed for the network topology in each node   OLSR is a proactive routing protocol   OLSR assumes all links are bidirectional (it ignores unidirectional links)   OLSR is advantageous in a densely connected network In a sparsely connected network, OLSR reduces to "regular" link state routing   Further information: P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot. Optimized link state routing protocol for ad hoc networks. In Proceedings of the IEEE International Multi Topic Conference (INMIC 2001), pages 62-68, 2001. TBRPF Like OLSR, Topology Dissemination Based on Reverse-Path Forwarding is a modification of link state routing that reduces the amount of messaging needed in Step 3 Each node computes the shortest-path tree to all destinations Each node reports a portion of this tree, the reported subtree (RT), to its neighbors The RT for node X includes node X itself; all of X's neighbors and their links; and the subtrees rooted at certain selected neighbors Y The subtree rooted at node Y is included if node X is on the shortest path from somewhere to node Y   Further information: R. Ogier, F. Templin, and M. Lewis. Topology Dissemination Based on Reverse-Path Forwarding (TBRPF). Internet RFC 3684, February 2004. AODV Ad Hoc On-Demand Distance Vector is a reactive version of DSDV Don't build and maintain a complete routing table to all destinations, only to those destinations actively receiving data traffic   Route discovery Route request (RREQ) packets Broadcast using flooding Broadcast using expanding ring search Route reply (RREP) packets Unicast back to the source Assumes the route from destination back to source is the reverse of the route from source to destination   Route maintenance Route error (RERR) packets Route aging   AODV is a reactive routing protocol   AODV assumes all links are bidirectional   Further information: C. E. Perkins and E. M. Royer. Ad-hoc on-demand distance-vector routing. In Proceedings of the Second Annual IEEE Workshop on Mobile Computing Systems and Applications, pages 90-100, February 1999. Charles E. Perkins and Elizabeth M. Royer. The Ad Hoc On-Demand Distance-Vector Protocol. In Charles E. Perkins, editor, Ad Hoc Networking (Addison-Wesley, 2001), pages 173-219. DSR The preceding protocols are variations of routing algorithms used in the Internet (distance vector, link state)   Source routing is not used in the Internet The source puts the complete route to the destination in each packet header, not just the destination address   Dynamic Source Routing (DSR) is a reactive version of source routing Don't build and maintain a complete routing table to all destinations, only to those destinations actively receiving data traffic   Route discovery Route request (RREQ) packets Route reply (RREP) packets Unicast back to the source Does not assume the route from destination back to source is the reverse of the route from source to destination May require a separate route discovery in the reverse direction   Route maintenance Route error (RERR) packets   DSR is a reactive routing protocol   DSR works with both bidirectional and unidirectional links   Further information: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In T. Imielinski and H. Korth, editors, Mobile Computing (Kluwer Academic Publishers, 1996), pages 153-181. David B. Johnson, David A. Maltz, and Josh Broch. DSR: The Dynamic Source Routing Protocol for Multihop Wireless As Hoc Networks. In Charles E. Perkins, editor, Ad Hoc Networking (Addison-Wesley, 2001), pages 139-172. Point-to-Point Transport Features of the Internet transport protocol, TCP Point-to-point connection-oriented Stream-oriented Reliable delivery (sequence numbers, acknowledgments, retransmissions) Flow control Congestion control   TCP congestion control in the Internet When congestion (routers' outgoing packet queues full) occurs, routers drop packets In the Internet, the Network Layer is not required to provide feedback to the Transport Layer about why a packet was dropped When TCP detects a lost packet, TCP assumes the reason was congestion, initiates congestion control, and reduces the packet transmission rate This is a good assumption in the Internet   TCP congestion control in a wireless network Packet losses are more likely due to poor wireless reception or radio interference, not congestion In that case, the proper response is to just retransmit the packet However, TCP assumes the packet loss was due to congestion and unnecessarily initiates congestion control TCP is designed for a wired network and is not well suited for a wireless network Since most ad hoc networks are wireless, TCP is not well suited for an ad hoc network   Fixing TCP, approach 1: Explicit feedback from the Network Layer When packets are lost, the Network Layer tells the Transport Layer something about what's going on, so the Transport Layer can do the right thing   K. Chandran, S. Raghunathan, S. Venkatesan, and R. Prakash. A feedback based scheme for improving TCP performance in ad-hoc wireless networks. In Proceedings of the 18th International Conference on Distributed Computing Systems (ICDCS '98), pages 472-479, May 1998. Their scheme is called "TCP-Feedback" (TCP-F) Does not address packet loss due to the wireless medium; assumes the Data Link Layer compensates for this Does address packet loss due to routing changes due to node mobility in an ad hoc network When the topology changes, packets can't be routed until new routes are established; in the meantime, packets must be dropped Network Layer sends Route Failure Notification (RFN) and Route Reestablishment Notification (RRN) packets to Transport Layer Upon receiving an RFN, Transport Layer goes into a "snooze" state until it receives an RRN or a timeout occurs Upon receiving an RRN, Transport Layer picks up where it left off (without changing its congestion control state)   D. Kim, C.-K. Toh, and Y. Choi. TCP-BuS: Improving TCP performance in wireless ad hoc networks. Journal of Communications and Networks, 3(2), June 2001. Their scheme is called "TCP with Buffering capability and Sequence information" (TCP-BuS) Similar to TCP-F with additional features: Explicit Route Disconnection Notification (ERDN) and Explicit Route Successful Notification (ERSN) messages Double the retransmission timeouts while routes are being reestablished Selective retransmission of lost packets requested by receiving node Receiving node suppresses fast retransmission requests (acknowledgments) after route reestablishment Extra measures taken to achieve reliable transmission of ERDN and ERSN messages   J. Liu and S. Singh. ATCP: TCP for mobile ad hoc networks. IEEE Journal on Selected Areas in Communications, 19(7):1300-1315, July 2001. Their scheme is called "Ad Hoc TCP" (ATCP) ATCP is a thin layer between the Transport Layer (TCP) and the Network Layer (IP) ATCP listens to feedback from the Network Layer and uses that to modify TCP's state Upon receiving an ICMP Destination Unreachable message (indicating a failed route), put TCP into the persist (frozen) state Upon receiving an Explicit Congestion Notification (ECN) message, initiate TCP congestion control without waiting for the usual timeout   Fixing TCP, approach 2: Be smarter about reacting to lost packets Don't just assume congestion is happening, look at other sources of information (while keeping TCP's philosophy of no feedback from the Network Layer)   F. Wang and Y. Zhang. Improving TCP performance over mobile ad-hoc networks with out-of-order detection and response. IN "Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC 2002), pages 217-225, June 2002. Their scheme is called "TCP with Detection of Out-of-Order and Response" (TCP-DOOR) Route changes due to node mobility often result in out-of-order packet delivery Packets are not lost But higher-numbered packets following a new, shorter route may arrive before lower-numbered packets following an old, longer route If three out-of-order packets arrive, the receiver will acknowledge the missing packet three times, the sender will receive a "triple ack," and the sender will inappropriately initiate congestion control Detecting out-of-order packets Sender detects out-of-order acknowledgment packets from receiver Receiver detects out-of-order data packets from sender, then notifies sender Both require additional data in the TCP header Responding to out-of-order packets Sender disables congestion control for a period of time Sender cancels congestion control if sender had already initiated congestion control   Fixing TCP, approach 3: Be aware of wireless links Do something different when a wireless link is known to be in use   A. Bakne and B.-R. Badrinath. I-TCP: Indirect TCP for mobile hosts. In Proceedings of the 15th International Conference on Distributed Computing Systems (ICDCS '95), pages 136-143, 1995. Their scheme is called "Indirect TCP" (I-TCP) Assumes a wired network with wireless used only for the last hop to the mobile device The regular TCP connection is actually set up between the mobile device's Mobile Support Router (MSR) and the far end A separate connection is set up between the MSR and the mobile device; this connection uses a different transport protocol The MSR relays data between the TCP connection and the wireless connection As the mobile device moves, the TCP connection is transferred from the old MSR to the new MSR   H. Balakrishnan, V.-N. Padmanabhan, S. Seshan, and R.-H. Katz. A comparison of mechanisms for improving TCP performance over wireless links. IEEE/ACM Transactions on Networking, 5(6):756-769, December 1997. Compared several approaches in three categories: End-to-end approach -- TCP receives feedback about the reasons for packet loss Split-connection approach -- The last (wireless) hop uses its own transport protocol, the rest of the (wired) hops use TCP Link-layer approach -- The Data Link Layer compensates for the unreliability of a wireless link using its own retransmissions or forward error correction Conclusion: "Of the schemes we investigated, the TCP-aware link-layer protocol with selective acknowledgment performs the best."   My approach: It doesn't make sense to use TCP in an ad hoc network Especially not for ad hoc collaborative applications with many-to-many communication patterns   Alan Kaminsky and Hans-Peter Bischof. New architectures, protocols, and middleware for ad hoc collaborative computing. In Middleware 2003 Workshop on Middleware for Pervasive and Ad Hoc Computing, Rio de Janeiro, Brazil, June 2003. (PDF, 243,645 bytes) "With this line of work, researchers are attempting to extend the Internet's (in particular, TCP's) concept of reliable data communications to the mobile wireless arena. However, trying to achieve reliable communications in an ad hoc collaborative system is ultimately futile, because devices enter and leave the system constantly. Any ad hoc collaborative application must build in, at the application level, the ability to "pump up" newly arrived devices with information they missed receiving while out of contact, and must build in the ability to accommodate the departure of a device as a normal occurrence rather than an exceptional situation. But if those abilities are built in at the application level, they will also compensate for loss of messages in the network. Therefore, it doesn't make sense to do a lot of processing at the network level to make network communication totally reliable. End-to-end reliability has to be built in at the application level." Multicast Transport Unreliable multicast: M2MP Problem: Too unreliable over wireless links Problem: Not very good flow control, no congestion control   Reliable multicast: Many protocols have been proposed See the Kaminsky & Bischof paper above Problem: Too heavyweight (memory, CPU, network bandwidth, battery power) for small devices Problem: Many must maintain the group membership, which is problematic in an ad hoc network where devices come and go all the time   NACK-Oriented Reliable Multicast (NORM) RFC 3940, "Negative-acknowledgment (NACK)-Oriented Reliable Multicast (NORM) Protocol" (November 2004) RFC 3941, "Negative-acknowledgment (NACK)-Oriented Reliable Multicast (NORM) Building Blocks" (November 2004) RFC 3452, "Forward Error Correction (FEC) Building Block" (December 2002) RFC 3453, "The Use of Forward Error Correction (FEC) in Reliable Multicast" (December 2002)   Features of NORM Supports single-sender or multiple-sender multicast groups Supports reliable multicast of arbitrarily large but finite-sized content (messages, files) Supports reliable multicast of stream content (like TCP) Receivers send negative acknowledgments (NACKs) to request repair of just the missing content As opposed to TCP, which sends positive acknowledgments (ACKs) for all content NACKs are sent at randomized times to avoid overwhelming the sender NACKs are suppressed if other receivers have already sent NACKs for the same content The sender aggregates the NACKs to decide what to repair To repair, the sender sends forward error correction (FEC) redundant information that lets the receivers compute the missing content As opposed to TCP, which retransmits all of the required content Falls back to retransmission if there is too much missing content for FEC to correct Devices can join the group at any time Ignore content items in progress and only start receiving new content items, or Request repair of content items in progress to recover data they missed before joining Sender does not need to maintain the group membership, sender just reacts to NACKs Supports congestion control using explicit feedback from receivers to senders As opposed to TCP, which does not use explicit feedback Measures the group greatest round trip time (GRTT), for setting timers   More about FEC Content divided into symbols Symbols grouped into encoding blocks An encoding block with N symbols consists of K content symbols and N-K redundant symbols If the receiver has any K of the N symbols in the encoding block, the receiver can compute the content symbols   Examples of FEC codes: Longitudinal parity Supports only one redundant symbol per encoding block (N = K+1) Can tolerate the loss of at most one symbol Redundant symbol = bitwise exclusive-or of content symbols Reed-Solomon code Supports a fixed number (more than one) of redundant symbols per encoding block Can tolerate the loss of several symbols Expandable codes Can generate an arbitrary number of redundant symbols per encoding block as needed Can tolerate the loss of any number of symbols PATENTED; BEWARE!   Use of FEC for reliable multicast transmission For each encoding block: Sender sends the K content symbols (each in its own packet) Receiver 1 receives them all, sends no NACK Receiver 2 missed one, sends NACK: "I need 1 more symbol" Receiver 3 missed two, sends NACK: "I need 2 more symbols" Receiver 4 missed one, sends no NACK because previous NACKs have already requested enough symbols Sender aggregrates all NACKs, sends 2 of the redundant symbols Receivers use those to compute the K content symbols This continues until a timeout occurs with no NACKs If the sender runs out of redundant symbols, sender must go back and retransmit the K content symbols   Difference between FEC and selective retransmission Suppose four receivers each missed a different packet (content symbol) With selective retransmission, the sender would have to re-send those four packets With FEC, the sender would have to send just one redundant packet -- less overhead This is a unique advantage of multicast communication (no such advantage with point-to-point communication) Ad Hoc Networks • 4003-543-01/4005-742-01 • Spring Quarter 2007 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2006 Alan Kaminsky. All rights reserved. Last updated 10-Apr-2006. Please send comments to ark­@­cs.rit.edu.