MANET Autoconfiguration (AUTOCONF) Youngmin Kim Internet Draft Sanghyun Ahn Expires: August 28, 2007 University of Seoul Jaehwoon Lee Doongguk University February 28, 2007 Load-Balancing Proactive Internet Gateway Selection in MANET draft-kim-autoconf-gatewaysel-01.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. 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 This Internet-Draft will expire on August 28, 2007. Abstract The mobile ad hoc network (MANET) is a rapidly configurable multi-hop wireless network without an infrastructure and originally proposed for the military use. In order to make the MANET a more commonly used network in our daily lives, it may be necessary to connect the MANET to the global Internet. A MANET node can communicate with an Internet node via the Internet gateway. To support fault tolerance and increase the bandwidth, multiple Internet gateways can be deployed within a MANET and, in this case, the network performance can be Kim, et al. Expires August 28, 2007 [Page 1] Internet-Draft Internet gateway selection February 2007 improved by balancing the load among Internet gateways. In this draft, we propose load-balancing Internet gateway selection mechanisms for the MANET with multiple stationary Internet gateways. In addition to this, we propose a scheme that reduces the routing control message overhead in the MANET when a MANET node sets up the route to Internet gateway using global address. Table of Contents 1. Introduction..................................................3 2. Load-Balancing Proactive Internet Gateway Selection...........3 2.1. Overview of Gateway Selection Protocol...................3 2.2. Gateway Information Advertisement and Gateway Selection..5 2.3. Metrics for Gateway Selection............................5 2.3.1. Single metric.......................................5 2.3.1.1. Hop count......................................5 2.3.1.2. Traffic load of an IGW.........................6 2.3.1.3. Variance of the receiving interval of IGWADVs..6 2.3.2. Complementary metric................................7 3. Message Format................................................7 4. Path Setup in the MANET.......................................9 4.1. Limited Forwarding of Routing Control Messages...........9 5. Security Considerations.......................................9 6. IANA Considerations...........................................9 References......................................................10 Author's Addresses..............................................10 Intellectual Property Statement.................................11 Disclaimer of Validity..........................................11 Copyright Statement.............................................11 Acknowledgment..................................................12 Kim, et al. Expires August 28, 2007 [Page 2] Internet-Draft Internet gateway selection February 2007 1. Introduction The MANET is a multi-hop wireless network without any network infrastructure such as a base station and has the limited communication range. To increase the communication range and enhance the usability of the MANET, the Internet Gateway (IGW) is used for the connection of a MANET to the global Internet. In this network, we assume that stationary multiple IGWs connect the MANET to the Internet and broadcast their own global prefix information to the MANET, and MANET nodes move freely within the communication range. In order to connect a MANET to the Internet, mechanisms for default IGW (DIGW) selection, path setup from a DIGW to a MANET node, address autoconfiguration, duplicate address detection and session management after changing the DIGW are needed. In this draft, we focus on the DIGW selection mechanism and the path setup mechanism from a DIGW to a MANET node. With multiple IGWs, if any one of the IGWs fails, another IGW can take over the failed one. To increase the overall throughput of the MANET to the global Internet, balancing the load on IGWs is required. The existing load-balancing IGW selection mechanisms [1-3] for the MANET with multiple IGWs take the hop count between a MANET node and an IGW, the load of an IGW or the receiving interval of IGW advertisement (IGWADV) messages as the metric. We want to increase the total throughput of MANET nodes communicating with Internet nodes using the load-balancing. Therefore we propose enhanced mechanisms using the above-mentioned metrics complementarily. In addition to this, we propose a scheme that reduces the routing control message overhead in the MANET. 2. Load-Balancing Proactive Internet Gateway Selection 2.1. Overview of Gateway Selection Protocol IGW selection mechanisms can be categorized into proactive, reactive and hybrid approaches. In the proactive IGW selection approach, each IGW broadcasts an IGWADV message containing the IGW information periodically. Each MANET node selects its DIGW based on the information in an IGWADV message. In the reactive IGW selection approach, a MANET node gets the IGW information after it broadcasts an IGW solicitation message. When an IGW receives a solicitation message from a MANET node, the IGW unicasts its IGW information to the MANET node. In the hybrid IGW selection approach, each IGW Kim, et al. Expires August 28, 2007 [Page 3] Internet-Draft Internet gateway selection February 2007 broadcasts an IGWADV message periodically within a limited area and a MANET node which has not received any IGWADV message determines its DIGW using a reactive IGW selection mechanism. According to the performance evaluation of these three IGW selection approaches in [4-5], the proactive IGW selection approach produces the largest amount of control traffic due to periodic IGWADV messages. However, the proactive approach shows the highest performance in terms of data throughput because MANET nodes always have the IGW information of all IGWs. On the other hand, the reactive IGW selection approach produces the least amount of control traffic since a MANET node configures its DIGW only when it has data to send to an Internet node. However, it gives the lowest data throughput due to the on-demand IGW selection. The amount of control traffic and the data throughput of the hybrid IGW selection approach are located in between the proactive approach and the reactive approach. Because the objective of this draft is to achieve higher throughput by performing the load-balancing, the proactive approach is taken as the IGW selection mechanism. In the case when MANET nodes move frequently, the reactive IGW selection approach may cause the IGW solicitation message storm, so the proactive IGW selection approach may suit well to this situation since it allows only IGWs to broadcast IGWADV messages. When all IGWs broadcast IGWADV messages in a MANET with multiple IGWs, the number of IGWADV messages increases as the number of IGWs increases. [1-2] propose a scheme that limits the sending area of IGWADV messages to fix the total number of IGWADV messages even when the number of IGWs increases. When a MANET node having already configured its DIGW receives an IGWADV message from another IGW, it does not forward the IGWADV message any further. A MANET node receiving IGWADV messages from only one IGW chooses the IGW as its DIGW. A MANET node receiving IGWADV messages from two or more IGWs chooses the best IGW as its DIGW. An IGW and MANET nodes selecting the IGW as their DIGW form an area and, between two areas, a boundary is implicitly formed. This scheme can reduce the overhead of the proactive IGW selection approach. For the IGW selection, each IGW MUST be able to advertise its global address and address prefix length, and each MANET node SHOULD choose the best DIGW by referring to the received IGWADV messages. The Internet connectivity scheme for the case when multiple IGWs are considered as DIGWs is out of the scope of this draft. Kim, et al. Expires August 28, 2007 [Page 4] Internet-Draft Internet gateway selection February 2007 2.2. Gateway Information Advertisement and Gateway Selection All IGWs in a MANET broadcast IGWADV messages. In order to reduce the overhead due to the IGWADV messages, the following procedure can limit the range of the broadcast of the IGWADV messages and select the DIGW of each MANET node 1. When a MANET node having not decided its DIGW yet receives an IGWADV message from an IGW, it configures the IGW as its DIGW and forwards the IGWADV message to its neighbors. 2. When a MANET node having already configured its DIGW receives an IGWADV message from its DIGW, it updates the load metric of the IGWADV message and forwards the IGWADV message to its neighbors. 3. When a MANET node having already configured its DIGW (g) receives an IGWADV message from an IGW (g') which is not the DIGW, if the following two conditions are met, the DIGW of the MANET node is changed to g'. In this case, regardless of the change of the DIGW, the MANET node does not forward the IGWADV message to its neighbors. a. The time for which the MANET node takes g as the DIGW is longer than the predetermined time t. b. M_g' + Delta <= M_g By condition a and Delta in condition b, we can prevent a MANET node from changing its DIGW frequently. Moreover, by not allowing the MANET node to forward the IGWADV message to its neighbors, changing the DIGWs of MANET nodes at the same time is prevented. M_g in condition b means the metric of the IGW g and will be defined in section 2.3. 2.3. Metrics for Gateway Selection In this section, the metric (M_g) referred in section 2.2 is defined. There can be various types of metrics for the DIGW selection in the MANET with multiple IGWs. 2.3.1. Single metric 2.3.1.1. Hop count This is a simple metric which can be obtained from an IGWADV message. Each MANET node selects an IGW with the smallest hop count (H_g) as its DIGW. If MANET nodes are gathered near an IGW, the IGW selection Kim, et al. Expires August 28, 2007 [Page 5] Internet-Draft Internet gateway selection February 2007 scheme using this metric can not balance the traffic load. However, the smaller the hop count is, the higher the throughput achieved by MANET nodes communicating with Internet nodes is. 2.3.1.2. Traffic load of an IGW Each IGW measures the total amount of transmitting and receiving traffic for a predetermined period. Each IGW calculates the new traffic load of the IGW g (L_g) as follows: L_g = a * T_new / (t * C_g) + (1- a) * L'_g, where 0 < a <= 1 (1) where C_g is the capacity of the IGW g, T_new is the total amount of transmitting and receiving traffic for recent t time and L'_g is the old value of the load of the IGW g. An IGWADV message containing the measured L_g is broadcast to MANET nodes and each MANET node uses the information to choose its DIGW. Each IGW broadcasts an IGWADV message with L_g periodically and each MANET node selects its DIGW using L_g as M_g in condition b in section 2.2. The characteristic of this metric is that it can balance the load of IGWs but it can lower the throughput due to the selection of the IGW which is located farther away as its DIGW. 2.3.1.3. Variance of the receiving interval of IGWADVs The metric (V_n) of the RVM scheme [3] is defined as follows: mean(t_n) = a * t_n + (1- a) * mean(t_n-1), where 0 < a <= 1 (2) V_n = a*(t_n - mean(t_n))^2 + (1- a)*V_n-1, where 0 < a <= 1 (3) Here, t_n is the difference between the time when the n-th IGWADV message arrives at the MANET node and the time when the (n-1)-th IGWADV message arrives at that node. Mean(t_n) is the estimated average time of the interval of IGWADV messages when the MANET node receives the n-th IGWADV message. Each MANET node calculates this metric (V_n) using the receiving interval of IGWADV messages and selects its DIGW using V_n as M_g in condition b in section 2.2. The DIGW selection scheme using this metric does not need any additional information except the IGW address information, but this metric value can fluctuate in a highly mobile network. Kim, et al. Expires August 28, 2007 [Page 6] Internet-Draft Internet gateway selection February 2007 2.3.2. Complementary metric New three metrics are formed by combining two metrics from the three metrics in section 2.3.1. This can overcome the disadvantages of single metrics. 1. Hop count and traffic load of an IGW M_g = W * H_g + L_g (4) This considers both the hop count and the traffic load of the IGW g as the metric. W is the weight of H_g. 2. Hop count and variance of the receiving interval of IGWADV messages M_g = H * V_n (5) This considers both the hop count and the variance of the receiving interval of IGWADV messages. 3. Traffic load of an IGW and variance of the receiving interval of IGWADV messages M_g = L_g * V_n (6) This considers both the traffic load of IGW g and the variance of the receiving interval of IGWADV messages. 3. Message Format The IGW advertisement message consists of the IPv4 or IPv6 header, the UDP header, and the fields from packetbb [6]. Fig. 1 is the message header and body of the IGWADV message and Fig. 2 and 3 are the message TLV of the IGWADV message. The hop count is included in the message header of Fig. 1. When an IGW broadcasts its traffic load, it uses the message TLV of Fig. 3. Otherwise, it uses the message TLV of Fig. 2. Kim, et al. Expires August 28, 2007 [Page 7] Internet-Draft Internet gateway selection February 2007 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Type | Resv |1|0|0| Message Size = 20 or 24 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Internet Gateway Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Limit | Hop Count | Message Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Length | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Message TLV | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1 IGW advertisement 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 |Resv |M|0|1|0|0| Length = 1 | Prefix Len | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| Figure 2 Message TLV 1 of the IGW advertisement message. Type : TBA. Prefix Len : The prefix length for "Internet Gateway Address". 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 |Resv |M|0|1|0|0| Length = 5 | Prefix Len | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | Traffic Load of IGW | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3 Message TLV 2 of the IGW advertisement message. Type : TBA. Prefix Len : The prefix length for "Internet Gateway Address". Traffic Load of IGW : The traffic load of IGW, the originator of this message. Kim, et al. Expires August 28, 2007 [Page 8] Internet-Draft Internet gateway selection February 2007 4. Path Setup in the MANET A MANET node can communicate with other MANET nodes with the MANET or Internet nodes. A MANET node SHOULD have a global address to communicate with Internet nodes, but MANET local address [7] is sufficient for the communication between MANET nodes. If we use this scoped address, the path between MANET nodes is formed by the flooding of routing control messages in the communication between MANET nodes. However, in the communication between a MANET node and an Internet node, the amount of routing control messages within the MANET can be reduced by the scheme of section 4.1 4.1. Limited Forwarding of Routing Control Messages A route setup between a MANET node and its DIGW is necessary for the communication between the node and an Internet node. Current Internet connectivity mechanisms configure routes by broadcasting routing control messages to the entire MANET. However, if a network can be divided into areas by prefix boundaries, we can limit the forwarding area of routing control messages to the area with the same global prefix. Therefore, for the establishment of routes for the Internet connectivity, we propose the limited forwarding scheme in which only MANET nodes with the same global prefix as that of the originator of a routing control message are allowed to forward the message. This scheme can be used in all IGW selection mechanisms limiting the forwarding area of IGWADV messages. 5. Security Considerations There are no security considerations in this draft. 6. IANA Considerations There are no IANA considerations in this draft. Kim, et al. Expires August 28, 2007 [Page 9] Internet-Draft Internet gateway selection February 2007 References [1] C. Jelger, T. Noel and A. Frey, "Gateway and Address Autoconfiguration for IPv6 Ad Hoc Networks", IETF Internet draft, draft-jelger-manet-gateway-autoconf-v6-02, April 2004. [2] C. Huang, H. Lee and Y. Tseng, "A Two-Tier Heterogeneous Mobile Ad Hoc Network Architecture and its Load-Balance Routing Problem", IEEE VTC, Oct. 2003. [3] R. Brannstrom, C. Ahlund and A. Zaslavsky, "Maintaining Gateway Connectivity in Multi-hop Ad hoc Networks", IEEE WLN, Nov. 2005. [4] M. Ghassemian, et al., "Performance Analysis of Internet Gateway Discovery Protocols in Ad Hoc Networks", IEEE WCNC, March 2004. [5] P. M. Ruiz and A. Gomez-Skarmeta, "Adaptive Gateway Discovery Mechanisms to Enhance Internet Connectivity for Mobile Ad Hoc Networks", Ad Hoc and Sensor Wireless Networks, March 2005. [6] T. Clausen, C. Dearlove, J. Dean and C. Adjih, "Generalized MANET Packet/Message Format", IETF Internet draft, draft-ietf- manet-packetbb-02, July 2006. [7] C. Jelger, "MANET Local IPv6 Addresses", IETF Internet draft, draft-jelger-autoconf-mla-01, Oct. 2006. Author's Addresses Youngmin Kim University of Seoul 90, Cheonnong-dong, Tongdaemun-gu Seoul 130-743, KOREA Email: blhole@venus.uos.ac.kr Sanghyun Ahn University of Seoul 90, Cheonnong-dong, Tongdaemun-gu Seoul 130-743, KOREA Email: ahn@venus.uos.ac.kr Kim, et al. Expires August 28, 2007 [Page 10] Internet-Draft Internet gateway selection February 2007 Jaehwoon Lee Dongguk University 26, 3-ga Pil-dong, Chung-gu Seoul 100-715, KOREA Email: jaehwoon@dongguk.edu Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The IETF Trust (2007). Kim, et al. Expires August 28, 2007 [Page 11] Internet-Draft Internet gateway selection February 2007 This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Kim, et al. Expires August 28, 2007 [Page 12]