Lecture 13: Wireless RoutingWireless is Different• Variable: signal attenuates over space• Interference: other RF sources can interfere withsignal• Multipath: signal can self-interfere• Distributed: nodes cannot detect collisionsWired Routing Review• Goal: optimal routes• Link state protocols• Distance vector protocols• Assumption: topology is stable• Common metric: hop countWireless Routing• Network is much more dynamic• Not constrained by physical topology• Discovering and estimating links to neighbors• Discovering and maintaining routes to nodes• Four protocols: DSDV, AODV, OLSR, SrcrDestination Sequenced Distance VectorRouting (DSDV)• Every node maintains routes to every other node• Continuous maintenance, rather than on-demand• Major challenge: loops, as nodes can haveout-of-date stateLoop FormationPreventing Loops• A route to a destination has a sequence number• When a node advertises its distance vector, itreports sequence numbers of those routes• If node hears a distance vector reporting a newerroute to a destination, it immediately uses thatroute and the newer sequence number• Two cases for incrementing sequence numbers- When a link breaks: set cost to infinity- Destination can increment when it advertisesAdvertisement Damping• For a given sequence number, node route costs canchange significantly- Have to change to new route on larger sequence number- Can later hear better routes• Don’t want to advertise on every route change• Can compute settling time, expected time betweena new version and the optimal route (EWMA ofprior epoch settling times)DSDV Summary• Distance vector protocol• Continuously maintains routes to all nodes• Destination-controlled sequence numbers preventloops• Never really tightly specified or seriouslyimplementedAd-hoc On-demand Distance Vector Routing(AODV)• Nodes cache routes (next hop) to destinations• If a node needs to send a packet to a destinationfor which it does not have a next hop, it floods aroute request message• Receiving a route request implicitly sets up a route• If a node with a route receives a route request, itresponds with a route reply• Base case: destination itself responds with routereplyRoute Request Packett y p e ctrl reserved hopcountdestination IPdestination sequence numbersource IPsource sequence numberFlooding a Request• Each route request flood has a source sequencenumber to suppress duplicates- A broadcasts, B hears and forwards, A won’t reflood B’stransmission• Hopcount field, incremented on each hopSFigure 1. ReversePath FormationStimeoutFigure 2. ForwardPath Formation2.1.1. Reverse Path Setup2.1.2. Forward Path SetupControlling the Flood• Don’t want to flood the entire network for everyroute request• AODV uses expanding ring search- Send request with IP TTL of 1- Send request with IP TTL of 2- Send request with IP TTL of 3, etc.Request Procesing• Requests can set up forward and reverse routes• Source sequence number prevents reflooding• Receiver of request might already have a cachedroute, with which it can reply• Destination sequence number used to determine ifcached routes valid- Whenever a node’s link breaks for a route, it incrementsdestination sequence number- When you receive a route reply, fill in sequence number- If you receive a request with a higher destination sequencenumber, do not reply from cacheRoute Reply PacketReply Processing• Destination: increment sequence number if willbe equal to request number• Intermediate: fill in its own sequence number forthe destination, increment hopcount• Unicast replies along reverse route• Only forward reply if:- Destination sequence number is higher than earlier replies- Same sequence number with smaller hopcount- Suppresses redundancy when multiple nodes reply fromcacheAODV Summary• Distance vector protocol• Generate routes on-demand by flooding• Sequence numbers distinguish requests and routeversions• RFC 3561 (Experimental), superseded by DYMO• Benefits- Stable routes require little control traffic- No data traffic → no control traffic• Drawbacks- Dynamics can lead to significant request/reply floodingOptimized Link State Routing Protocol(OLSR)• Each node collects local link state information• Link state is flooded through entire network• Multi-Point Relays (MPRs) responsible forflooding- MPRs selected so only some nodes forward a flood- Reduces flooding cost and redundancyMulti-Point Relays (MPRs)• Nodes advertise what nodes they have links to• A node can discover its 2-hop neighborhood bytaking the union of all advertisements it hears• A node selects a subset of its neighbors to be itsmulti-point relays• Rule: union of neighborhood sets of MPRs mustbe the complete 2-hop neighborhoodMPR ExampleMPRs, Continued• Nodes locally announce their MPR sets• The MPR selector set of a node is the set of nodesthat have selected it as an MPR• When a node hears a message to flood, forwards itiff- Single hop origin is in selector set- Message is not a duplicate• MPRs have their own MPRsMPR Set Calculation• RFC 3626 suggests an algorithm• Add nodes which are the only node to provideaccess to a 2-hop neighbor• From nodes that provide access to at least one newnode, select nodes with highest “willingness”• Among nodes with same “willingness,” pick thosewith highest degreeOLSR Packet Formatpacket lengthpacket sequence numbermessage type vtime message sizeoriginator addressttl hopcount message sequence numberMESSAGEmessage type vtime message sizeoriginator addressttl hopcount message sequence numberMESSAGEOLSR Message Types• HELLO messages, for link maintenance, localdiscovery, and communication with MPRs (notforwarded)• TC (topology control) messages, which advertiselink state• MID, for declaring multiple interfaces• HNA, for advertising access to networks withoutOLSR (e.g., gateway)HELLO Messagereservedlink code reserved message sizeinterface addresshtime willingnessinterface addresslink code reserved message sizeinterface addressinterface addressTC MessageANSNneighbor addressreservedneighbor addressneighbor addressOLSR Routing• Use link state of network to iteratively computeroutes- Compute single hop routes from neighborhood- Compute 2-hop routes
View Full Document
Unlocking...