Preview only show first 10 pages with watermark. For full document please download

Ad Hoc Routing Protocols

   EMBED

  • Rating

  • Date

    August 2018
  • Size

    580.2KB
  • Views

    753
  • Categories


Share

Transcript

Ad Hoc 라우팅 표준(RFC3561)과 IPv6 적용기법 정재훈 (Jaehoon Paul Jeong) 한국전자통신연구원 표준연구센터 [email protected] http://www.adhoc.6ants.net/ 2003. 10. 23 제1회 IPv6 표준화워크샵 및 표준설명회 1 Contents   Introduction Ad Hoc Unicast Routing Protocols   AODV (RFC 3561)      Demand-driven Routing Protocols AODV Message Formats IPv6 AODV Autoconfiguration Technologies for IPv6 MANET Summary References 제1회 IPv6 표준화워크샵 및 표준설명회 2 Introduction (1/2)  Categories of Wireless Networks  Infrastructured Network   Infrastructureless Network   Cellular Network, Wireless LAN (WLAN) Ad Hoc Network Ad Hoc Network    Temporary network composed of mobile nodes without preexisting communication infrastructure, such as Access Point (AP) and Base Station (BS). Each node plays the role of router for multi-hop routing. Application  War-field communication, Emergency recovery, Homenetworking, Video-conferencing etc. 제1회 IPv6 표준화워크샵 및 표준설명회 3 Mobile Ad Hoc Networks Internet WLAN Cellular Mobile Ad Hoc Networks 제1회 IPv6 표준화워크샵 및 표준설명회 4 Introduction (2/2)  Issues in MANET       Ad Hoc Unicast Routing Ad Hoc Multicast/Broadcast Routing Power Saving Global Connectivity for MANET Addressing & DNS Automatic Support of Networking Facility in MANET  Autoconfiguration Technology 제1회 IPv6 표준화워크샵 및 표준설명회 5 Ad Hoc Unicast Routing Protocols Ad Hoc routing protocols Table-driven (Proactive) DSDV OLSR TBRPF AODV CGSR Demand-driven (Reactive) DSR Hybrid LMR ABR TORA SSR 제1회 IPv6 표준화워크샵 및 표준설명회 ZRP 6 Demand-driven Routing Protocols  Characteristics  Creation of routes only when desired by the source node   Route Discovery Process is completed     Until the destination becomes inaccessible along every path from the source Until the route is no longer desired Criterion of Classification of Routing Protocols   Once a route is found When all possible route permutations have been examined Maintenance of a Route   By Route Discovery Process Method by which route finding is performed Examples  AODV, DSR, LMR, TORA, ABR, SSR 제1회 IPv6 표준화워크샵 및 표준설명회 7 AODV (RFC 3561) Ad hoc On-Demand Distance Vector C. Perkins, E. Belding-Royer and S. Das, July 2003. 제1회 IPv6 표준화워크샵 및 표준설명회 8 Contents      Overview of AODV Route Discovery Route Maintenance Optimizations AODV Message Formats 제1회 IPv6 표준화워크샵 및 표준설명회 9 Overview of AODV (1/2)  AODV is improved DSDV algorithm    Reactive or On-demand Provides unicast and multicast communication (MAODV) AODV doesn’t maintain a complete list of routes as in DSDV algorithm.   Nodes that are not on a selected path don’t maintain routing information or participate in routing table exchanges. Loop-free  AODV utilizes destination sequence numbers to ensure all routes are loop-free. 제1회 IPv6 표준화워크샵 및 표준설명회 10 Overview of AODV (2/2)  Route Discovery process  When does it happen?   When source node doesn’t already have a valid route to a destination Route Discovery   It broadcasts a route request (RREQ) packet to its neighbors. Neighbors forward the request to their neighbors, and so on until either the destination or an intermediate node with a “fresh enough” route to the destination is located. 제1회 IPv6 표준화워크샵 및 표준설명회 11 Route Discovery (1/10) B S A C D 1. Node S needs a route to D in order to send data packets to D 제1회 IPv6 표준화워크샵 및 표준설명회 12 Route Discovery (2/10) B S A C D 1. Node S needs a route to D in order to send data packet to D 2. Creates a Route Request (RREQ) Enters D’s IP addr, seq#, S’s IP addr, seq# hopcount (=0) 제1회 IPv6 표준화워크샵 및 표준설명회 13 Route Discovery (3/10) B RREQ S A C D 2. Creates a Route Request (RREQ) Enters D’s IP addr, seq#, S’s IP addr, seq# hopcount (=0) 3. Node S broadcasts RREQ to neighbors 제1회 IPv6 표준화워크샵 및 표준설명회 14 Route Discovery (4/10) B RREQ S A C D 4. Node A receives RREQ  Makes reverse route entry for S dest = S, nexthop = S, hopcnt = 1 제1회 IPv6 표준화워크샵 및 표준설명회 15 Route Discovery (5/10) B RREQ S A C D 4. Node A receives RREQ   Makes reverse route entry for S dest = S, nexthop = S, hopcnt = 1 It has no route to D, so it rebroadcasts RREQ 제1회 IPv6 표준화워크샵 및 표준설명회 16 Route Discovery (6/10) B RREQ S A C D 5. Node C receives RREQ   Makes reverse route entry for S dest = S, nexthop = A, hopcnt = 2 It has a route to D, and the seq# for route for D is >=D’s seq# in RREQ 제1회 IPv6 표준화워크샵 및 표준설명회 17 Route Discovery (7/10) B S A RREP C D 6. Node C sends RREP   C creates a Route Reply (RREP) Enters D’s IP addr, seq # S’s IP addr, hopcount to D (=1) Lifetime Unicasts RREP towards A 제1회 IPv6 표준화워크샵 및 표준설명회 18 Route Discovery (8/10) B RREP S A RREP C D 7. Node A receives RREP   Makes forward route entry to D dest = D, nexthop = C, hopcount = 2, Lifetime Unicasts RREP to S 제1회 IPv6 표준화워크샵 및 표준설명회 19 Route Discovery (9/10) B RREP S A C D 8. Node S receives RREP  Makes forward route entry to D dest = D, nexthop = C, hopcount = 3, Lifetime 제1회 IPv6 표준화워크샵 및 표준설명회 20 Route Discovery (10/10) B S A C D 9. Node S sends data packets on route to D 제1회 IPv6 표준화워크샵 및 표준설명회 21 Route Maintenance (1/5) B S A RERR C D 1. Link between C and D breaks down  C can perform local repair for the route to D 제1회 IPv6 표준화워크샵 및 표준설명회 22 Route Maintenance (2/5) B S A RERR C D 1. Link between C and D breaks down  C can perform local repair for the route to D 2. Node C invalidates route to D in route table 제1회 IPv6 표준화워크샵 및 표준설명회 23 Route Maintenance (3/5) B S A RERR C D 3. Node C creates Route Error (RERR) message   C creates a Route Error (RERR) Enters DestCount (=1), D’s IP addr, seq # Lists all destinations which are now unreachable   “DestCount” field indicates the number of unreachable destinations included in the RERR message. Sends to upstream neighbors in precursor list 제1회 IPv6 표준화워크샵 및 표준설명회 24 Route Maintenance (4/5) B RERR S A RERR C D 4. Node A receives RERR   Checks whether C is its next hop on route to D Deletes route to D or invalidates the route to D according to N flag (No delete flag)   When N flag is set, A does not send RERR to S and may reinitiate route discovery for D. Forwards RERR to S 제1회 IPv6 표준화워크샵 및 표준설명회 25 Route Maintenance (5/5) B RERR S A C D 5. Node S receives RERR    Checks whether A is its next hop on route to D Deletes route to D Rediscovers route if still needed 제1회 IPv6 표준화워크샵 및 표준설명회 26 Optimizations (1/2)  Expanding Ring Search    It prevents flooding of network during route discovery Control Time To Live (TTL) of RREQ to search incrementally larger areas of network Advantage   Less overhead when successful Disadvantage  Longer delay if route not found immediately 제1회 IPv6 표준화워크샵 및 표준설명회 27 Optimizations (2/2)  Local Repair  It repairs breaks in active routes locally instead of notifying source.   Advantage   If the first repair attempt is unsuccessful, it sends RERR to source. Link repair with less overhead, delay and packet loss. Disadvantage  Longer delay and greater packet loss when unsuccessful 제1회 IPv6 표준화워크샵 및 표준설명회 28 AODV Message Formats 제1회 IPv6 표준화워크샵 및 표준설명회 29 Route Request (RREQ) Message Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |J|R|G|D|U| Reserved | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RREQ ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 제1회 IPv6 표준화워크샵 및 표준설명회 30 Route Reply (RREP) Message Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |R|A| Reserved | Prefix Sz | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination IP address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Lifetime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 제1회 IPv6 표준화워크샵 및 표준설명회 31 Route Error (RERR) Message Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |N| Reserved | DestCount | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unreachable Destination IP Address (1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unreachable Destination Sequence Number (1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | Additional Unreachable Destination IP Addresses (if needed) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Additional Unreachable Destination Sequence Numbers (if needed) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 제1회 IPv6 표준화워크샵 및 표준설명회 32 Route Reply Acknowledgement (RREP-ACK) Message Format 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  RREP-ACK message MUST be sent in response to a RREP message with the ‘A’ bit set.  This is typically done when there is danger of unidirectional links preventing the completion of a Route Discovery cycle. 제1회 IPv6 표준화워크샵 및 표준설명회 33 IPv6 AODV C. Perkins, E. Belding-Royer and S. Das, draft-perkins-manet-aodv6-01, November 2001. 제1회 IPv6 표준화워크샵 및 표준설명회 34 AODV for IPv6 Operation  Message Handling  The handling of IPv6 AODV for IPv6 AODV messages is analogous to IPv4 AODV.   ICMP Processing   AODV messages have the formats appropriate for use with 128bit IPv6 addresses. Whenever IPv4 AODV specifies use of ICMP, the operation for IPv6 uses ICMPv6. Configuration Parameters  IPv4 and IPv6 AODVs use the same parameters. 제1회 IPv6 표준화워크샵 및 표준설명회 35 Autoconfiguration Technologies for IPv6 MANET Reference Paper: http://www.adhoc.6ants.net/publications/ international-conference/icoin2004-jaehoon.pdf 제1회 IPv6 표준화워크샵 및 표준설명회 36 Autoconfiguration?  What is Autoconfiguration?   Issues of IETF Zeroconf Working Group      The technology that allows IP-enabled devices be able to communicate one another in infrastructureless environment. Unicast Address Autoconfiguration Multicast Address Allocation Name Resolution (DNS) Service Discovery Why is Autoconfiguration needed in MANET?  To provide the quick and easy configuration related to the networking in MANET with dynamic topology. 제1회 IPv6 표준화워크샵 및 표준설명회 37 Autoconfiguration Technology for IPv6 MANET  Unicast Address Autoconfiguration   Automatic configuration of a unique IPv6 address within MANET Multicast Address Allocation  Allocation of a unique multicast address for the application which needs a new multicast address Multicast DNS   Translation between name and IPv6 address Service Discovery  Discovery of the necessary service 제1회 IPv6 표준화워크샵 및 표준설명회 Autoconfiguration Technology for IPv6 MANET Multicast DNS  Service Discovery Unicast Address Autoconfiguration Multicast Address Allocation 38 Summary  AODV     It is a Reactive/On-demand Ad Hoc routing protocol.  Route Discovery cycle Sequence numbers are used for route freshness and loop prevention. It maintains only active routes. Optimizations can be used to reduce overhead and increase scalability.  IPv6 AODV  Autoconfiguration Technologies for IPv6 MANET 제1회 IPv6 표준화워크샵 및 표준설명회 39 References [1] C. Perkins, E. Belding-Royer and S. Das, “Ad hoc On-Demand Distance Vector (AODV) Routing”, RFC 3561, July 2003. [2] C. Perkins, E. Belding-Royer and S. Das, “Ad Hoc On Demand Distance Vector (AODV) Routing for IP version 6”, draft-perkins-manet-aodv6-01, November 2001. [3] Auto-Networking Technologies for IPv6 MANET, http://www.adhoc.6ants.net/publications/internationalconference/icoin2004-jaehoon.pdf [4] ETRI Ad Hoc Project, http://www.adhoc.6ants.net/ 제1회 IPv6 표준화워크샵 및 표준설명회 40