DOC PREVIEW
UCLA COMSCI 218 - On-Demand Routing Protocols

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

On-Demand Routing Protocols• Routes are established “on demand” as requested by the source• Only the active routes are maintained by each node• Channel/Memory overhead is minimized• Two leading methods for route discovery: source routing and backward learning (similar to LAN interconnection routing)On Demand Routing - Readings• D. B. Johnson and D. A. Maltz, "Dynamic Source Routing in Ad-Hoc WirelessNetworks," Mobile Computing, 1994.Charles E. Perkins and Elizabeth M. Royer. "Ad hoc On-Demand Distance VectorRouting." Proceedings of the 2nd IEEE Workshop on Mobile Computing Systemsand Applications, New Orleans, LA, February 1999, pp. 90-100.Existing On-Demand Protocols• Dynamic Source Routing (DSR)• Associativity-Based Routing (ABR)• Ad-hoc On-demand Distance Vector (AODV)• Temporarily Ordered Routing Algorithm (TORA)• Zone Routing Protocol (ZRP)• Signal Stability Based Adaptive Routing (SSA)• On Demand Multicast Routing Protocol (ODMRP)Dynamic Source Routing (DSR)• Forwarding: source route driven instead of hop-by-hop route table driven• No periodic routing update message is sent• The first path discovered is selected as the route• Two main phases––Route DiscoveryRoute Discovery––Route MaintenanceRoute MaintenanceDSR - Route Discovery• To establish a route, the source floods a Route RequestRoute Requestmessage with a unique request ID• The Route Request packet “picks up” the node ID numbers••Route ReplyRoute Reply message containing path information is sent back to the source either by– the destination, or– intermediate nodes that have a route to the destination• Each node maintains a Route CacheRoute Cache which records routes it has learned and overheard over timeDSR - Route Maintenance• Route maintenance performed only while route is in use• Monitors the validity of existing routes by passivelylistening to acknowledgments of data packets transmitted to neighboring nodes• When problem detected, send Route ErrorRoute Error packet to original sender to perform new route discoveryAd hoc On-Demand Distance Vector Routing (AODV)• Primary Objectives– Provide unicast, broadcast, and multicast capability– Initiate forward route discovery only on demand– Disseminate changes in local connectivity to those neighboring nodes likely to need the information• Characteristics– On-demand route creation•Effect of topology changes is localized•Control traffic is minimized– Two dimensional routing metric: <Seq#, HopCount>– Storage of routes in Route TableRoute Table• Fields:– Destination IP Address– Destination Sequence Number– HopCount– Next Hop IP Address– Precursor Nodes– Expiration Time• Each time a route entry is used to transmit data, the expiration time is updated to current_time + active_route_timeoutNext HopSourceSourceAPrecursor NodesDestinationUnicast Route Discovery<Flags, Bcast_ID, HopCnt, Src_Addr, Src_Seq#, Dst_Addr, Dst_Seq#>• Node can reply to RREQ if– It is the destination, or– It has a “fresh enough” route to the destination• Otherwise it rebroadcasts the request• Nodes create reverse route entry• Record Src IP Addr / Broadcast ID to prevent multiple rebroadcastsSourceDestinationRoute Request Propagation•Source broadcasts Route Request (RREQ)Forward Path Setup• Destination, or intermediate node with current route to destination, unicasts Route Reply (RREP) to source<Flags, HopCnt, Dst_Addr, Dst_Seq#, Src_Addr, Lifetime>• Nodes along path createforward route• Source begins sending data when it receives first RREPSourceDestinationForward Path FormationPath Maintenance• Movement of nodes not along active path does not trigger protocol action• If source node moves, it can reinitiate route discovery• When destination or intermediate node moves, upstream node of break broadcasts Route Error (RERR) message• RERR contains list of all destinations no longer reachable due to link break• RERR propagated until node with no precursors for destination is reachedSourceDestination12343’SourceDestination1243’GloMoSim/Qualnet Simulation LayersApplication ProcessingPropagation Model MobilityFrame ProcessingRadio Status/SetupCS/Radio SetupRTS/CTSFrame WrapperAck/Flow ControlClusteringPacket Store/ForwardVC HandleFlowControlRoutingIP WrapperIP/Mobile IPRSVPTransport WrapperTCP/UDP ControlChannelRadioMAC LayerNetworkIPTransportApplicationRTP Wrapper RCTPPacket Store/ForwardClusteringRoutingLink LayerApplication SetupData PlaneData PlaneControl PlaneControl PlanePerformance Evaluation Enviroment• PARSEC simulation enviroment– 100 nodes– 1000mx1000m square area– transmission range: 100m– channel data rate: 2 Mbps– random mobility model– UDP traffic between randomly selected node pairs– cluster-token MAC layer protocol• HSR – 2 level physical partition– 1 level logical groupings, number of logical subnets varies withnetwork size• FSR– 2 level fisheye scoping– fisheye radius is 2 hopsControl O/H vs. number of nodes00.20.40.60.811.21.41.61.825 49 100 225 324 400Number of nodesControl O/H (Mbits/Cluster)On-demand DSDV HSR FSRControl O/H vs. Traffic PairsControl O/H vs. Mobility (100 pairs)Average Delay (ms)Location-Aided Routing (LAR)• Ko and Vaidya (Texas A & M)• Location assisted (requires GPS)• On-demand• No periodic messages• LAR works like DSR except it limits the flooded area of Route RequestsRoute Requests using location informationLAR (cont’d)•Scheme 1– The source specifies a request zone which includes the source and the area where the destination may reside– Nodes within the request zone propagate Route Route RequestsRequests•Scheme 2– The source specifies the distance between itself and the destination– Nodes forward Route RequestsRoute Requests if their distances to the destination is less than or equal to the distance indicated by the packetDREAM• Besagni, et al. (U of Texas, Dallas)• Location assisted (requires GPS)• Node coordinates (instead of routes) are recorded in the route table ••Distance EffectDistance Effect: Send location updates to nearby nodes more frequently• Location update frequencies are adjusted to mobility rateDREAM (cont’d)• The source partially floods data to nodes that are in the direction of the destination• The source specifies possible next hops in the data header using location information• Next hop nodes select their own list of


View Full Document

UCLA COMSCI 218 - On-Demand Routing Protocols

Documents in this Course
GSM

GSM

59 pages

Chord

Chord

30 pages

10_2

10_2

9 pages

13_4

13_4

10 pages

RAP

RAP

17 pages

46_4

46_4

9 pages

32_4

32_4

10 pages

umts

umts

39 pages

AdHoc-MAC

AdHoc-MAC

29 pages

rma

rma

8 pages

Lecture

Lecture

29 pages

Load more
Download On-Demand Routing Protocols
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view On-Demand Routing Protocols and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view On-Demand Routing Protocols 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?