Ad Hoc Wireless RoutingCS 218- Fall 2003• Wireless multihop routing challenges• Review of conventional routing schemes• Proactive wireless routing • Hierarchical routing• Reactive (on demand) wireless routing• Geographic routingReadings• G. Pei, M. Gerla, and X. Hong, " LANMAR: Landmark Routing for Large Scale Wireless Ad Hoc Networks with Group Mobility," In Proceedings of IEEE/ACM MobiHOC2000, Boston, MA, Aug. 2000. • R. Ogier, F. Templin, M. Lewis, " Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) ," IETF Internet Draft , July 28 2003. • Thomas Clausen, Philippe Jacquet, " Optimized Link State Routing Protocol (OLSR) ," IETF Internet Draft , July 3 2003. • X. Hong, K. Xu, and M. Gerla, " Scalable Routing Protocols for Mobile Ad Hoc Networks " IEEE Network Magazine, July-Aug, 2002, pp. 11-21Wireless multihop routing challenges• mobility• need to scale to large numbers (100’s to 1000's)• unreliable radio channel (fading, external interference, etc)• limited bandwidth• limited power• need to support multimedia applications (QoS)Proposed ad hoc Routing Approaches• Conventional wired-type schemes (global routing, proactive):– Distance Vector; Link State• Hierarchical routing:• Scalable schemes:– Fisheye, OLSR, TBRPF, Landmark Routing • On- Demand, reactive routing:– Source routing; backward learning• Geo-routing:– etc– clustering• Motion assisted routingConventional wired routing limitations• Distance Vector (eg, Bellman-Ford, DSDV):– routing control O/H linearly increasing with net size– convergence problems (count to infinity); potential loops• Link State (eg, OSPF):– link update flooding O/H caused by frequent topology changesCONVENTIONAL ROUTING DOES NOT SCALE TO SIZE AND MOBILITYDistance Vector051243DestinationNext HopDistance0 2 31 2 2… … …Routing table at node 5 :Tables grow linearly with # nodesControl O/H grows with mobility and sizeLink State Routing• At node 5, based on the link state pkts, topology table is constructed:• Dijkstra’s Algorithm can then be used for the shortest path051243{1}{0,2,3}{1,4}{2,4}{2,3,5}{1,4,5}012345011000011111002011011301011040011115001011Topology reduction schemes–OLSR and TBRPF• The link state protocol explodes because of Link State update overhead• Question: how can we reduce the O/H?– (1) if the network is “dense”, use fewer forwarding nodes– (2) if the network is dense, advertise only a subset of the links• Two leading IETF Link State schemes enhance scalability in large scale networks: – OLSR : Optimal Link State Routing– TBRPF: Topology Broadcast Reverse Path RoutingOLSR Overview• In LSR protocol a lot of control messages unnecessary duplicated• In OLSR only a subset of neighbors Multipoint Relay Selectors retransmit control messages:– Reduce size of control message;– Minimize flooding• Other advantages (the same as for LSR):– As stable as LSR protocol;– Proactive protocol;– Does not depend upon any central entity;– Tolerates loss of control messages;– Supports nodes mobility.Multipoint Relays (MPR)•Designed to reduce duplicate retransmission in the same region•Each node chooses a set of nodes (MPR Selectors) in the neighborhood, which will retransmit its packets.•The other nodes in the neighborhood receive and process the packet, but do not retransmit it•MPR Selectors of node N - MPR(N)- one-hop neighbors of N - Set of MPR’s is able to transmit to alltwo-hop neighbors•Link between node and it’s MPR is bidirectional.Optimized Link state routing (OLSR)24 retransmissions to diffuse a message up to 3 hopsRetransmission node11 retransmission to diffuse a message up to 3 hopsRetransmission nodeMultipoint Relays (MPR) cont.• Every node keeps a table of routes to all known destination through its MPR nodes• Every node periodically broadcasts list of its MPR Selectors (instead of the whole list of neighbors).• Upon receipt of MPR information each node recalculates and updates routes to each known destination• Route is a sequence of hops through MPR’s from source to destination • All the routes are bidirectionalNeighbor sensing• Each node periodically broadcasts Hello message:– List of neighbors with bidirectional link– List of other known neighbors. (If node sees itself in this list it adds the sender to neighbors with bidirectional link)• Hello messages permit each node to learn topology up to 2 hops• Based on Hello messages each node selects its set of MPR’sExample of neighbor tableOne-hop neighbors……MPR4Unidirectional3Bidirectional2State of LinkNeighbor’s idTwo-hop neighbors……3151726Access throughNeighbor’s idAlso every entry in the table has a timestamp, after which the entry in not validMPR Selection• MPR set is calculated in a manner to contain a subset of one hop neighbors, which cover all the two hop neighbors• MPR set need not to be optimal (Moreover it is a hard problem to find an optimal set!)• The algorithm of selecting MPR is not presented in this paper.• MPR is recalculated if detected a change in one-hop or two-hops neighborhood topology• MPR Selector Table contains addresses of neighbors, who selected the node as MPR• MPR Selector Table has a Sequence Number, which is incremented after every MPR update.Conclusions• OLSR is a proactive protocol• Suitable for applications, which does not allow long time delays• Adapted for dense network (reduces control traffic overhead)TBRPF Overview• TBRPF (Topology Broadcast Based on Reverse-Path Forwarding) is a proactive, link-state protocol.• TBRPF-FT (Full Topology)– Each node is provided with the state of every link in the network.– Useful for sparse topologies and when full topology information is needed. • TBRPF-PT (Partial Topology):– Each node is provided with only enough information to compute min-hop paths to all other nodes.– Useful for dense topologies.• This presentation will focus on TBRPF-PT.TBRPF Overview (cont.)• TBRPF uses a parent-child relationship to maintain a dynamically changing min-hop broadcast tree rooted at each update source (advertising router). The parent p(u) for source u is the next node on the min-hop path to source u. A NEW PARENT message is sent when p(u) changes.• A node forwards the updates emanating from source u only for links (u,v) such that node v is not a leaf of the broadcast tree rooted at node u, i.e., such that
View Full Document
Unlocking...