Seminar_27012004_AODV_JPro

Views:
 
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Ad hoc On-demand Distance Vector Routing Protocol:

Ad hoc On-demand Distance Vector Routing Protocol The presentation is based on a paper: C.E. Perkins, E.M. Royer, “Ad hoc On-Demand Distance Vector Routing” Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA '99, 25-26 Feb. 1999 M.Sc. (EE) Jarmo Prokkola University of Oulu, Telecommunication Laboratory & Centre for Wireless Communications P.O. Box 4500 (Tutkijantie 2 E) FIN-90014 University of Oulu, Finland proke@ee.oulu.fi, GSM: +358 40 706 1549 Telecommunication laboratory 27.01.2004

Contents:

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 2 Contents Introduction General information Basic functionality Path discovery Route tables Path maintenance Parameters of AODV The end discussion

Introduction:

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 3 Introduction Ad hoc network is a self-organizing network without centralized control, where each node acts as router to attain coverage over multiple hops. Routing protocol has a very important role Routing protocols have been studied widely and dozens of them have been presented Ad hoc On-demand Distance Vector (AODV) routing protocol is considered in this presentation Routing protocols Reactive Proactive Hybrid DSDV WRP CGSR AODV DSR LMR ABR LAR TORA SSA ZRP CBRP

General Information:

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 4 General Information Based on DSDV (Destination-Sequenced Distance Vector) routing protocol DSDV is effective in small networks DSDV is ineffective in larger networks because of the huge increase of control-information (of order n ²) Periodic update of the whole network topology Reactive on-demand routing protocol Route is formed only when needed Pure on-demand route acquisition protocol No periodic routing table updates More effective in larger networks => Less control-information than in table-driven protocols In principle, AODV is independent from lower layer functionalities as long as node’s can communicate with each other (basic connectivity). Symmetric links (not strictly required) Loop-free

Basic Functionality:

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 5 Basic Functionality Node has to be aware of the local connectivity Quick response time to local topology changes and route searches Local hello messages (a special form of RREP-packet) Passive routing table update (i.e. listen to neighbor’s transmissions) AODV relies on dynamically establishing route table entries at intermediate nodes instead of source routing (e.g. DSR) Packets do not carry the information of the whole route Less control information Fresh route information maintenance system is based on the method used in DSDV Monotonically increasing route sequence numbers are used to supersede stale cached routes

Path discovery (1/5):

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 6 Path discovery (1/5) Initiated, when node needs to communicate with new node (no routing information in table) Route Request (RREQ) packet is broadcasted to network An expanding ring search should be used TTL (Time to live) parameter in IP-header sets the lifetime in hops for packets TTL is first small and is then increased, if a route is not found until a limit is reached source_addr source_seq_num broadcast_id (RREQ_id) dest_addr dest_seq_num hop_cnt ctrl_info 64 bits 192 bits RREQ

Path discovery (2/5):

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 7 Path discovery (2/5) Example: Node A needs to communicate with F RREQ A->F is released to network Neighbors C and B receive RREQ and learn route to A A B C D E F RREQ RREQ

Path discovery (3/5):

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 8 Path discovery (3/5) Intermediate nodes C and B do not have route to F RREQ is broadcasted forward with increased hop count only if hop limit is not yet reached A receives it’s own RREQ Reverse paths to B and C are formed RREQ is discarded Intermediate node D receives multiple copies of RREQ form A Direct routes to C and B are formed The first arrived RREQ is set used to form route to A (e.g. B here) A B C D E F

Path discovery (4/5):

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 9 Path discovery (4/5) D forwards RREQ B and C discard duplicate RREQ and learn route to D Destination node F finally gets RREQ A B C D E F

Path discovery (5/5):

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 10 Path discovery (5/5) Route reply packet (RREP) is sent back to node A along reverse route In fact any node, which has a fresh route to destination can send RREP and therefore end route search Active forward path from A to F is created Intermediate nodes also have now active forward path to F Route is ready for data transmission A B C D E F RREP RREP RREP source_addr lifetime dest_addr dest_seq_num hop_cnt ctrl_info 64 bits 160 bits RREP

Routing tables:

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 11 Routing tables A B C D E F Route expiration times are updated when route is used Routes in AODV are in fact virtual routes! a single node do not know the complete route and therefore “route control” is distributed

Path maintenance (original AODV):

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 12 Path maintenance (original AODV) Example: Link D<->F is broken due to movement of F A special RREP is send upstream in path (now B->A) hop_count to lost destination (now F) is set to ∞ From RREP node A sees a broken link towards F New route is searched as in initial route search (RREQ) if needed A B C D E F F RREP (lost node) RREP (lost node) lost link RREP (lost node) RREP (lost node)

Path maintenance (AODV, July 2003):

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 13 Path maintenance (AODV, July 2003) If a link is broken, route repair is initiated (if active) Link failure detecting node initiates route search (Now, RREQ D->F) Route Error (RERR) is generated if repair is failed or deactivated All the routes concerning the lost link will be written to RERR Entries of the unreachable nodes are invalidated A DELETE_PERIOD is set to indicate final elimination of the route table entry RERR is send to all nodes affected by the link breakage A new route to known node is accepted if route’s sequence number is greater than the number of old route If hop count of a new route is greater, it is up to source node to decide what to do (RERR-notification is sent) A B C D E F F RREQ RREQ RREP RREP RREQ RREQ

About AODV parameters:

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 14 About AODV parameters Parameter name Default value (description) ACTIVE_ROUTE_TIMEOUT 3 (The timeout for route expiration) ALLOWED_HELLO_LOSS 2 HELLO_INTERVAL 1 (The interarrival time of hello-messages) BLACKLIST_TIMEOUT RREQ_RETRIES * NET_TRAVERSAL_TIME DELETE_PERIOD depends on the link-layer (delete-timeout for route entry) LOCAL_ADD_TTL 2 MAX_REPAIR_TTL 0.3 * NET_DIAMETER MIN_REPAIR_TTL should be at least the last known hop count to destination MY_ROUTE_TIMEOUT 2 * ACTIVE_ROUTE_TIMEOUT NET_DIAMETER 35 (the maximum number of hops between two nodes) NET_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME * NET_DIAMETER NEXT_HOP_WAIT NODE_TRAVERSAL_TIME + 10 s NODE_TRAVERSAL_TIME (Conservative estimate of the 1 hop packet delay) PATH_DISCOVERY_TIME 2 * NET_TRAVERSAL_TIME RERR_RATELIMIT 10 RING_TRAVERSAL_TIME 2*NODE_TRAVERSAL_TIME * (TTL_VALUE+TIMEOUT_BUFFER) RREQ_RETRIES 2 RREQ_RATELIMIT 10 TIMEOUT_BUFFER 2 TTL_START 1 TTL_INCREMENT 2 TTL_THERESHOLD 7 TTL_VALUE (the TTL in packet header in operation)

Properties of AODV:

AODV Routing Protocol M.Sc. (EE) Jarmo Prokkola 27.01.2004 University of Oulu, Centre for Wireless Communications 15 Properties of AODV Performs generally well in most cases Adapts easily to changing environment (mobility) The amount of control-information is reduced With pure on-demand nature, it enables huge networks Has been studied widely and the development of the protocol is in rather advanced state Is easy to implement over different lower layers Does not require anything else but a possibility to communicate with neighbors Difficult to be adapted with changing traffic load because of numerous parameters, even though the protocol itself is quite simple Often used as a comparison point for other routing protocols

authorStream Live Help