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