One document matched: draft-cha-manet-aodv-internet-00.txt
Internet Draft Hyun-Wook Cha
Jung-Soo Park
Hyoung-Jun Kim
Document: draft-cha-manet-AODV-internet-00.txt PEC, ETRI
Expires: August 2004 February 2004
Support of Internet Connectivity for AODV
Status of this Memo
All Internet-Drafts must begin with ONE of the following three
statements:
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026 [i].
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026 except that the right to
produce derivative works is not granted.
This document is an Internet-Draft and is NOT offered in accordance
with Section 10 of RFC2026, and the author does not provide the IETF
with any rights other than to publish as an Internet-Draft
Any submission which does not include one (and only one) of the above
three statements will be returned to the submitter. The IETF
Secretariat will NOT add this text.
The following verbatim statement must follow the optional opening
sentence:
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
In this document, we propose another solution to support Internet
connectivity for AODV. In the design of our solution, several
Cha, Park, and Kim Expires - August 2004 [Page 1]
Support of Internet Connectivity for AODV February 2004
important limits of existing solutions are considered. Especially,
new route determination and forwarding algorithms are proposed.
Proposed route determination algorithm supports dynamic switching
between default route and host route in a sender node through which
enhanced performance can be achieved under frequent topological
changes. And proposed forwarding algorithm supports next hop
forwarding for default routes towards multiple gateways.
Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC-2119 [ii].
Table of Contents
1. Introduction...................................................2
2. Terminology....................................................4
3. Proposed Solution to Support Internet Connectivity for AODV....5
3.1 Auto-configuration of Global Addresses.....................5
3.2 Route Determination Algorithm in Sender Nodes..............6
3.3 Forwarding Algorithm in Intermediate Nodes.................8
Security Considerations...........................................9
References........................................................9
Author's Addresses................................................9
1. Introduction
Recently various approaches including [1], [2], [3] have been
presented to support Internet connectivity for IPv6 based MANETs. The
proposed solutions can be classified into two categories according to
the forwarding strategy for default routes toward Internet gateways;
one including [1], [2], [3] which use next hop forwarding for default
routes and the other including [1] which do not use next hop
forwarding and require that a sender specifies a gateway in routing
header.
The use of routing header has following advantages over the next hop
forwarding.
Firstly, intermediate nodes do not have to maintain default route
entry. If both a default route entry and a host route entry for the
actual gateway should be maintained in a node, inconsistency between
two routes can happen at any time under reactive routing protocols.
This can cause that packets destined to Internet nodes are forwarded
using default routes which may be longer or less fresh than those of
actual gateways. In addition, it is possible that a route entry for
Cha, Park, and Kim Expires - August 2004 [Page 2]
Support of Internet Connectivity for AODV February 2004
the actual gateway is still valid when a default route is invalidated
because a link on a disjoint sub-path between a path through default
routes and a path through route entries for the gateway has broken.
In this case, packets should be queued until new default route entry
is obtained although the route entry for the gateway is still
available.
Secondly, the use of routing header does not add additional
processing to forward packets destined to Internet nodes in
intermediate nodes since destination IPv6 address is the gateway
through which packets should be forwarded to the Internet.
Consequently, the simplicity of forwarding algorithm in original
routing protocol can be preserved. However, solutions using next hop
forwarding for a default route require that intermediate nodes should
know that a received packet was sent using host route entry or
default route entry by sender. If a node receives a packet sent using
host route by sender and does not have valid host route entry for the
destination, the node should broadcast RERR to notify the sender that
the path to the destination is not available rather than forward the
packet to the Internet. Also, if a node receives a packet sent using
default route by sender and has valid host route entry for the
destination, it is desirable that the node can notify to the sender
that direct path to the destination is available so that route
optimization may be achieved. Consequently, above requirement can
make forwarding algorithm in next hop default forwarding more complex
and inefficient than that in the use of routing header.
Thirdly, the use of routing header can maximize lifetime of an
address because a node can refresh address or prefix information as
long as the gateway which advertises the prefix or has assigned the
address is reachable.
Fourthly, the use of routing header can support Internet connectivity
through multiple gateways. Specifically, no additional modifications
are needed to utilize multiple gateways to obtain global addresses
and packets to forward to the gateway which advertises the prefix of
source addresses.
In spite of above advantages, the use of routing header shows
apparently its main overhead. All packets destined to Internet nodes
should have routing header specifying an exit gateway which aims only
efficient forwarding to the gateway within a MANET. On the other hand,
although this overhead can be saved, next hop forwarding for default
routes should tackle above issues efficiently as the use of routing
header does. It is observed that in [2] and [3], the forwarding
algorithm does not consider correct determination of host route entry
or default route entry and in [2], multiple gateways are not
supported, and in [3], the use of multiple global addresses is not
supported since one gateway among multiple gateways is chosen at any
Cha, Park, and Kim Expires - August 2004 [Page 3]
Support of Internet Connectivity for AODV February 2004
given time. As for route inconsistency with routing protocol, [2] can
resolve through periodic exchanges of an RREQ and an RREP between a
node and a gateway but [3] does not consider this issue. In addition,
in [3], it is difficult to maximize lifetime of an address because a
node relies on GW_INFO advertisements of neighborhoods in which
information of one gateway selected by each neighbor is contained to
increase lifetime of its address.
We propose another solution to support Internet connectivity for a
MANET. Goals of our design are
1. to maximize lifetime of an address,
2. preserve route consistency for default routes with routing
protocol,
3. support multiple gateways so that multiple addresses may be
configured and maintained,
4. propose a forwarding algorithm to support next hop forwarding for
default routes towards multiple gateways in which correct
determination of host route entry or default route entry is
considered,
5. propose a route determination algorithm to support dynamic
switching between default route and host route in a sender
through which enhanced performance can be achieved under frequent
topological changes,
6. minimize per packet overhead such as routing header and control
packet overhead.
In following sections, we present detailed specification of our
approach based on AODV [4].
2. Terminology
node
MANET local node which is not Internet gateway
gateway(gw)
Internet gateway with MANET routing protocols
GW_ADV
Gateway advertisement message containing gw_info as well as route
information of a prefix.
gw_info
information about a gateway conveyed in a GW_ADV.
gw_info_list
This list is maintained in a node which supports our solution. It
contains information about gateways learned from GW_ADV messages.
Cha, Park, and Kim Expires - August 2004 [Page 4]
Support of Internet Connectivity for AODV February 2004
affiliated global address
global addresses which are affiliated to the Internet and globally
reachable
known affiliated global address
global addresses with prefixes advertised by gateways
unknown affiliated global address
affliated global addresses which do not belong to prefixes advertised
by gateways
non-affiliated global address
global address assigned to a MANET node, which is not affiliated to
the Internet and globally unreachable.
host route forwarding
forwarding using host route entry
default route forwarding
forwarding using default route entry
3. Proposed Solution to Support Internet Connectivity for AODV
Our solution is composed of three parts; 1) auto-configuration of
global addresses, 2) route determination algorithm in sender nodes
and 3) forwarding algorithm in intermediate nodes.
Detailed specification is described in following sections.
3.1 Auto-configuration of Global Addresses
We do not introduce any new method for auto-configuration of global
addresses for MANET nodes. Instead, we adopt existing methods
including stateless one like [1] and stateful one like [5]. In
addition, our solution requires that following additional processing
should be inserted in underlying routing protocol such as AODV.
Specifically, updating a route entry (route entry) including
invalidating is accompanied with the following pseudo codes.
If (gw_info for destination of the route entry exists) {
if (next_hop of the route entry !=prev_next_hop of the route
entry)
set the DEF_ROUTE flag in the route entry to 0;
If (GW_ADV is received)
Set the DEF_ROUTE flag in the route entry to 1;
}
Cha, Park, and Kim Expires - August 2004 [Page 5]
Support of Internet Connectivity for AODV February 2004
This is necessary since for a given gateway, any other control
messages containing valid route information for the gateway than
GW_ADVs can change next hop node in the route entry for the gateway
in a MANET node differently than existing one set by the latest
GW_ADV for the gateway. If the next hop node has been changed, it is
not guaranteed that current next hop node also has GW_INFO for the
gateway and can perform default route forwarding using the GW_INFO.
So, we introduce the DEF_ROUTE flag to notify that next hop
forwarding for default route using a GW_INFO is available or not.
Through the exchange of periodic RREQs and GW_ADVs to refresh global
addresses or periodic GW_ADVs from gateways, default routes from a
MANET node to gateways can be refreshed so that next hop forwarding
for default route using a GW_INFO may be utilized as much as possible.
Detailed forwarding algorithm is presented at section 3.3.
3.2 Route Determination Algorithm in Sender Nodes
Basically MANETs assume that any address can be assigned to each node.
So, global address itself does not mean that it can be globally
reachable through the Internet. We believe that due to the dynamics
of MANETs, the current assumption or knowledge about the location of
the destination should be changeable (adaptable) dynamically rather
than fixed statically by address itself.
In [2], delay and control overheads can be reduced when nodes want to
communicate with Internet nodes which have unknown global addresses
since it does not perform route discovery. However, [2] does neither
consider non-affiliated global addresses which can be assigned to a
MANET statically or by any MANET specific methods independent to the
Internet, nor consider route optimization for affiliated global
addresses under multiple gateways.
On the other hand, [1] performs route discovery for all global
addresses before sending to the Internet via gateways. So, a node can
communicate with nodes which have non-affiliated or unknown
affiliated global addresses through direct multi-hop paths. However,
delay and control overheads by route discovery are not desirable when
nodes want to communicate with nodes with affiliated global addresses
because they are globally reachable. In addition, dynamic route
optimization between nodes with global addresses affiliated to
different gateways is not addressed.
We propose an efficient route management and determination algorithm
in sender nodes considering above issues. In our algorithm, an route
entry belongs to one of three types; default route (/0), prefix route
(/n), and host route (/128). Prefix routes are divided into two types
whether the prefix is advertising through a MANET interface of a
MANET Internet gateway or not. If so, the GW flag in the prefix route
Cha, Park, and Kim Expires - August 2004 [Page 6]
Support of Internet Connectivity for AODV February 2004
entry is set to 1. A prefix route is associated with the route entry
of the gateway or router advertising it.
In addition, we introduce the NOT_GLOBAL, NOT_MANET, and RO flags.
The NOT_GLOBAL flag means that a destination is not globally
reachable and this can be known through an ICMP Destination
Unreachable message. Also, it is possible that the destination node
is not a MANET node. Since a gateway can determine that a node being
discovered by a RREQ is a MANET node or not, we add following
additional operation to gateways. When a gateway receives an RREQ for
a destination address which belongs to the prefix being advertised
through its MANET interface, it replies whether it has a valid route
of the destination or not. If it has valid route entry for the
destination, it replies with an RREP containing valid route
information. If it does not have valid route entry and the
destination is a MANET node, it forwards received RREQ if TTL value
of the message is not zero and replies with RREP containing route
information of the prefix in which a specific flag (I flag) is set to
1 to indicate that this prefix route information is from a gateway.
If it does not have valid route entry and the destination is not a
MANET node route, it sends an RREP containing route information of
the prefix as well as the notification of the fact. And a specific
flag (I flag) in the message is set to 1 to indicate that this
information is from a gateway. If it is known that a destination is
not a MANET node through the reply message from a gateway, the
NOT_MANET flag in the host route entry is set to 1. The Route
optimization is triggered when a packet is forwarded using a prefix
route entry with the GW flag set as 1. If a route entry for the
destination does not exist, new invalid route entry with the RO flag
set as 1 is created and the route discovery is performed. The RO flag
means that this route entry is not used for forwarding decision but
controlling of RREQ broadcast for the route optimization. So, The RO
flag is reset when valid route information is obtained or the
NOT_MANET flag is set.
When a MANET node has a packet to be sent, it performs following
route determination algorithm.
The node looks up its routing table for the destination of the packet.
- If a valid host route entry is found, the node sends the packet
using that route.
- If the NOT_GLOBAL flag in the route entry is 1, the packet is
sent encapsulated. The source address/destination address in the
outer header is non_affiliated address of the node/destination in the
inner header.
- Otherwise, the packet is sent as it is.
- If an invalid host route entry is found and the RO flag in the
route entry is 0, and TTL is below specific threshold value or the
Cha, Park, and Kim Expires - August 2004 [Page 7]
Support of Internet Connectivity for AODV February 2004
NOT_GLOBAL flag in the route entry is 1, it inserts the packet into
the routing queue and performs the route discovery.
- Otherwise, it sends the packet using a corresponding prefix route
to the destination address or the default route. If a prefix route is
chosen, the packet is sent with routing header specifying the
corresponding router advertising the prefix.
- If a prefix route is used and the GW flag in the prefix route is
1, it determines that the route optimization can be performed by
referring the NOT_MANET flag in the host route entry for the
destination if available.
- If a host route entry for the destination does not exist or
NOT_MANET flag in the route entry is 0, the route discovery is
performed for the route optimization. If the route entry for the
destination exists, sending new RREQ may be controlled. If a host
route entry does not exist, new host route entry with the RO flag set
to 1 is created.
- If the NOT_MANET flag in the route entry is 1, the route
discovery is not triggered and the Lifetime of the entry is
incremented by ACTIVE_ROUTE_TIMEOUT. [4]
- If the default route is chosen, the node sends the packet using
host route entry for the right exit gateway according to the source
address of the packet.
- If a valid route entry for the gateway does not exist, the
packet is inserted to the routing queue and the route discovery for
the gateway is triggered. For fast recovery of a default route toward
the gateway, a modified RREQ message may be sent to require that a
replying node should answer with a GW_ADV in behalf of the gateway
instead of a normal RREP.
- If a valid route entry for the gateway exists and the DEF_ROUTE
flag in the route entry is 1, the packet is sent as it is.
- Otherwise, the packet with routing header specifying the
gateway is sent.
3.3 Forwarding Algorithm in Intermediate Nodes
When a MANET node has a packet to be forwarded, it performs following
forwarding algorithm.
The node looks up its routing table for the destination of the packet.
- If a valid host route entry is found, the packet is forwarded using
that route.
- Otherwise, the applicability of default route forwarding is checked
by looking up the gw_info_list with the prefix of the source address
of the packet.
- If corresponding gw_info entry in the gw_info_list is found,
following cases are possible.
Cha, Park, and Kim Expires - August 2004 [Page 8]
Support of Internet Connectivity for AODV February 2004
- If a valid route entry for the gateway which the gw_info entry
specifies does not exist, the packet is discarded and an RERR message
for the gateway as well as the destination of the packet.
- If a valid route entry is found and the DEF_ROUTE flag in the
route entry is 1, the packet is forwarded using the route entry. In
addition, an RERR message is broadcast since it is difficult to
determine that previous hop node forwarded the packet using a host
route or a default route. Since continuous RERR broadcasting caused
by the default route forwarding for traffics outgoing toward the
Internet can waste bandwidth and cause congestion, sending RERRs is
rate-limited through the RERR cache.
- Otherwise, the packet is sent encapsulated. The source
address/destination address in the outer header is non_affiliated
address of the node/address of the gateway. In addition, an RERR
message is broadcast, which is rate-limited through the RERR cache.
Security Considerations
Basically our algorithms are designed to extend the AODV routing
protocol and any security methods which are applicable to the AODV
can be also applicable for implementing proposed algorithms in this
draft. In further versions of this document, we will discuss specific
security threats to our algorithms.
References
1. Wakikawa, R., Malinen, J., Perkins, C., Nilsson, A. and A.
Tuominen, "Internet Connectivity for Mobile Ad hoc networks", I-D
draft-wakikawa-manet-globalv6-03.txt, November 2002.
2. P. Paakkonen, M. Rantonen, J. Latvakoski, "IPv6 addressing in a
heterogeneous MANET-network", I-D, draft-paakkonen-addressing-htr-
manet-00.txt, December 2003.
3. C. Jelger, T. Noel, "Gateway and address autoconfiguration for
IPv6 ad-hoc networks", I-D draft-jelger-manet-gateway-autoconf-v6-
01.txt. October, 2003.
4. C. Perkins, E. Belding-Royer, S. Das, "Ad hoc On-Demand Distance
Vector (AODV) Routing", RFC 3561. July, 2003.
5. H. Cha, J. Park, H. Kim, "Extended Support for Global Connectivity
for IPv6 Mobile Ad Hoc Networks", I-D draft-cha-manet-extended-
support-globalv6-00.txt. Work in progress.
Author's Addresses
Hyun-Wook Cha
ETRI / PEC
Cha, Park, and Kim Expires - August 2004 [Page 9]
Support of Internet Connectivity for AODV February 2004
161 Gajong-Dong, Yusong-Gu
Daejon 305-350, Korea
Phone: +82 42 860 1076
EMail: jafy@etri.re.kr
Jung-Soo Park
ETRI / PEC
161 Gajong-Dong, Yusong-Gu
Daejon 305-350, Korea
Phone: +82 42 860 6514
EMail: pjs@etri.re.kr
Hyoung-Jun Kim
ETRI / PEC
161 Gajong-Dong, Yusong-Gu
Daejon 305-350, Korea
Phone: +82 42 860 6576
EMail: khj@etri.re.kr
Cha, Park, and Kim Expires - August 2004 [Page 10]
| PAFTECH AB 2003-2026 | 2026-04-23 20:19:15 |