MANET Working Group Sanghyun Ahn INTERNET-DRAFT Youngmin Kim Expired: April 2006 University of Seoul Yujin Lim University of Suwon Jaehwoon Lee Dongguk University October 2005 Load Balancing in MANET with Multiple Internet Gateways draft-ahn-manet-multigateway-00.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 April 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract In MANET, nodes wishing to communicate with nodes in the wired Internet, the global Internet connectivity is required and this functionality can be achieved with the help of the Internet gateway (IGW). For the support of reliability and flexibility, multiple IGWs draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 1] Internet Draft Load Balancing in MANET Oct. 2005 can be provisioned for a MANET. In this case, load-balancing becomes one of the important issues since the network performance such as the network throughput can be improved if the load of the IGW is well-balanced. In this draft, we categorize the load-balancing mechanisms for the IPv6-based MANET with multiple IGWs and define a new load-balancing metric computed from the hop distance and the number of routing table entries. Table of Contents: 1. Introduction...................................................3 2. Terminology....................................................3 3. Categorization of Load Balancing Mechanisms....................4 3.1 SMN........................................................4 3.2 SIGW.......................................................5 4. Message Format.................................................5 4.1 Message Format for SMN.....................................5 4.2 Message Format for SIGW....................................6 5. Security Considerations........................................8 References........................................................9 Author's Addresses................................................9 Intellectual Property Statement..................................10 Disclaimer of validity...........................................10 Copyright Statement..............................................10 draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 2] Internet Draft Load Balancing in MANET Oct. 2005 1. Introduction The Internet gateway (IGW) in an access network can provide the global Internet connectivity for nodes in a MANET. The IGW belongs to both the wired Internet and the MANET and connects them. For the support of reliability and flexibility, multiple IGWs can be provisioned for a MANET. It is important for MNs to discover available IGWs for the Internet connectivity. There are two major approaches, reactive and proactive [1]: - Reactive discovery A MN broadcasts a message which solicits the information on IGWs for the global connection within the MANET. IGWs receiving the message reply the MN with there IP prefix addresses. - Proactive discovery Each IGW periodically broadcasts its service and IP prefix information within the MANET. A MN receiving the message decides an IGW to connect to the Internet. These two approaches can be combined into a hybrid gateway discovery scheme [2]. Load-balancing is one of the important issues when MNs access the Internet via multiple gateways. The network performance can be improved if the load is balanced well among the gateways. In this draft, Internet gateway discovery mechanisms to improve the network throughput with balancing the load among multiple IGWs are categorized for the IPv7-based MANET, and a new metric to select an IGW and modified/new message formats for this metric are defined. 2. Terminology In this draft, we use the terms defined in [1], except for the term described below. IGW signaling message A message to announce the IPv6 address of an IGW's wired interface and the IGW load information to other IGWs via the wired Internet. draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 3] Internet Draft Load Balancing in MANET Oct. 2005 3. Categorization of Load-Balancing Mechanisms We assume that a MANET has fixed multiple gateways for the Internet connectivity and mobile nodes move within a limited area. The basic IGW operation for the global connectivity is adopted from [1]. Load-balancing mechanisms for multiple gateways are categorized as shown in table 1. The factors considered for the categorization are the chooser of the IGW for the Internet connectivity (the chooser can be a MN or an IGW) and whether the flooding of a control message is limited or not (i.e., the expanding ring search or the maximum TTL flooding). The expanding ring search scheme selects the locally optimal IGW among nearby IGWs and, on the other hand, the maximum TTL flooding scheme selects the globally optimal IGW among all IGWs. Table 1. Categories of load-balancing mechanisms +-----------------------+-------------------+-------------------+ | + Selection of an IGW | Selected by a MN | Selected by a IGW | | +---------------+ | | | | Flooding Scheme + | (SMN) | (SIGW) | +-----------------------+-------------------+-------------------+ | Expanding Ring Search | SMN-ERS | SIGW-ERS | | (ERS) | | | +-----------------------+-------------------+-------------------+ | Maximum TTL Flooding | SMN-MTF | SIGW-MTF | | (MTF) | | | +-----------------------+-------------------+-------------------+ 3.1 SMN In order to provide a MN with the load-balancing information which can be used for the optimal IGW selection, additional information is included in the IGW advertisement. The IGW advertisement may be disseminated proactively or reactively. A MN may receive more than one advertisement during a certain period (TIMER_MN). The MN selects the IGW with the minimum value of IGW_i^c computed according to equation 1. When two or more IGWs have the same value, the first received advertisement is chosen. Let i_in_G be any IGW. IGW_i^c is defined as: IGW_i^c = k*H + R, i_in_G (1) draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 4] Internet Draft Load Balancing in MANET Oct. 2005 where H is the hop distance between the IGW and the MN and k is the weighting factor. R is defined as the number of valid routing table entries. Under the low-load condition, H dominates IGW_i^c. When traffic is concentrated on a certain IGW, R gets increased and becomes the dominating part of IGW_i^c. Thus, the MN newly accessing the Internet selects the IGW with light load so that the traffic load can be distributed among IGWs. 3.2 SIGW In this mechanism, all IGWs in a MANET share the IGW_i^c information, and the only IGW with the minimum value can send an IGW advertisement message. To compute IGW_i^c, each IGW should receive the IGW solicitation message with the hop count information from the soliciting MN. The IGW calculates IGW_i^c based on the number of its routing table entries and the hop count from the IGW solicitation, and shares the calculated information with other IGWs over the wired Internet. To share the information, the IGW can multicast using the ALL_MANET_GW_MULTICAST address [1] or other dedicated multicast address, or can unicast to each IGW in the same MANET. 4. Message Format 4.1 Message Format for SMN Figure 1 shows the modified prefix information option of the IGW advertisement for the inclusion of the information needed for the defined load-balancing metric [1, 3]. draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 5] Internet Draft Load Balancing in MANET Oct. 2005 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Prefix Length |L|A|M|H| Resv. | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Valid Lifetime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | Preferred Lifetime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | Hop Count |# of Rout. Ent.| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | | +- -+ | | +- Prefix -+ | | +- -+ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: Modified prefix information option of the IGW advertisement message M: A flag bit to indicate that the Hop Count and the Number of Routing Entry field are valid. H: A flag bit to indicate that the Hop Count field needs to be increased by one whenever the message is processed by each intermediate MN on the path toward the MN. Hop Count: The number of hops from the IGW to a MN. No. of Routing Entry: The number of routing table entries that the IGW is currently maintaining. As explained previously, an IGW advertisement is sent out periodically or as a response to an IGW solicitation. In the case of a response to the solicitation, the Hop Count field has the number of hops that the IGW solicitation message has been forwarded. In the case of the periodic advertisement, the field is increased by one by each intermediate MN. 4.2 Message Format for SIGW Figure 2 shows the modified IGW solicitation message format for the inclusion of the hop count information. draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 6] Internet Draft Load Balancing in MANET Oct. 2005 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Code | Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |M|H| Reserved | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-++++++++++++++++++++++++++++++++| | | . . . Options . . . | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: Modified format of the IGW solicitation message H: A flag bit to indicate that the Hop Count field is valid and the Hop Count needs be increased by one whenever the message is processed by each intermediate MN on the path towards the IGW. Hop Count: The number of hops from the soliciting MN to the IGW. Figure 3 shows the format of the IGW signaling message defined to share IGW_i^c among all IGWs. By exchanging this message, each IGW can know the wireless and the wired interface address of other IGWs in the same MANET. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Count |# of Rout. Ent.| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-++++++++++++++++++++++++++++++++| | | +- -+ | | +- IPv6 Address -+ | | +- -+ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: Format of the IGW signaling message draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 7] Internet Draft Load Balancing in MANET Oct. 2005 Type: A value to identify the type of the IGW signaling message. Type = 1 means that this message is for the distribution of the IGW address to other IGWs. Type = 2 means that this message has the information on the hop count and the number of routing table entries of the IGW. Type = 3 means that the IGW has already sent out an IGW advertisement to the soliciting MN. Hop Count: The number of hops from the IGW to a MN. No. of Routing Entry: The number of routing table entries that the IGW is currently maintaining. IPv6 Address: For Type = 1, the IPv6 address of the IGW's wired network and, for Type = 2 or 3, the IPv6 address of the soliciting MN. Using the type-1 message (with Type = 1), each IGW disseminates its address to other IGWs. The source and the destination address of the type-1 IGW signaling message are the IPv6 address of the IGW's wireless network interface and the ALL_MANET_GW_MULTICAST address, respectively. Once an IGW receives an IGW solicitation message, the IGW sends to the wired Internet a type-2 IGW signaling message with setting valid values in the Hop count and the Number of Routing Entry field. After receiving an IGW solicitation, the IGW waits for the IGW signaling messages from other IGWS for a certain period (TIMER_IGW). After the certain period, if its IGW_i^c is smaller than the received IGW_i^cs, the IGW sends an IGW advertisement to the soliciting MN. Otherwise, the IGW drops the solicitation without sending an IGW advertisement. If no IGW signaling message is received during the period, the IGW sends an advertisement to the soliciting MN. When the IGW sends the IGW advertisement to the soliciting MN, it also sends a type-3 message to all IGWs through the Internet. The IGW receiving the type-3 message just drops the solicitation message. If the soliciting MN receives more than one advertisement, it selects the first one received. The type-2 or type-3 IGW signaling message are sent through the wired Internet to the IGWs in the same MANET using some kind of wired Internet multicast mechanism or unicast. And this is out of the scope of this draft. draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 8] Internet Draft Load Balancing in MANET Oct. 2005 5. Security Considerations There are no security considerations in this draft. References [1] R. Wakikawa, J. T. Malinen, C. E. Perkins, A. Nilsson and A. J. Tuominen, "Global connectivity for IPv6 mobile ad hoc networks", draft-wakikawa-manet-globalv6-04.txt, work in progress. [2] P. Ratanchandani and R. Kravets, "A hybrid approach to internet connectivity for mobile ad hoc networks", WCNC 2003, pp. 1522-1527, March 2003. [3] T. Narten, E. Nordmark and W. Simpson, "Neighbor Discovery for IP Version 6 (ipv6)", RFC 2461. Authors' Addresses Sanghyun Ahn University of Seoul 90, Cheonnong-dong, Tongdaemun-gu Seoul 130-743, KOREA Email: ahn@venus.uos.ac.kr Youngmin Kim University of Seoul 90, Cheonnong-dong, Tongdaemun-gu Seoul 130-743, KOREA Email: blhole@venus.uos.ac.kr Yujin Lim University of Suwon San 2-2, Wawoo-ri, Bongdam-eup, Hwaseong-si Kyeongi-do 445-743, Korea Email: yujin@suwon.ac.kr Jaehwoon Lee Dongguk University 26, 3-ga Pil-dong, Chung-gu Seoul 100-715, KOREA Email: jaehwoon@dongguk.edu draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 9] Internet Draft Load Balancing in MANET Oct. 2005 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 INTERNET SOCIETY 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 Internet Society (2005). 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. draft-ahn-manet-multigateway-00.txt Expires - April 2006 [Page 10]