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]