Network Working Group J. Park Internet-Draft ETRI Intended status: Informational H. Jeong Expires: January 14, 2011 D. Kim KNU H. Kim ETRI July 13, 2010 The Multi-Path Routings Method based on Reactive Routing Protocol draft-park-manet-multipath-analysis-scenarios-02 Abstract This document discusses the use of multiple interfaces of Mobile Ad hoc NETworks (MANETs) nodes and multiple path MANET routings protocols with respect to traditional, single network interface based ones. It then describes the design principles and methods of multiple path routing over MANET nodes with multiple interfaces. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." This Internet-Draft will expire on January 14, 2011. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect Park, et al. Expires January 14, 2011 [Page 1] Internet-Draft Multi-path routing solution July 2010 to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Design Issues for Multiple Path Routings . . . . . . . . . . . 3 3.1. Supporting multiple interfaces . . . . . . . . . . . . . . 4 3.2. Defining multiple path selection criteria . . . . . . . . 4 3.3. Relation between link/path metrics and multiple paths . . 4 3.4. Multiple Internet Connectivity . . . . . . . . . . . . . . 4 3.5. Policy of using multiple paths . . . . . . . . . . . . . . 5 4. Types of Multiple Path Routing Protocols . . . . . . . . . . . 5 4.1. The number of interfaces . . . . . . . . . . . . . . . . . 5 4.2. Routing metrics . . . . . . . . . . . . . . . . . . . . . 5 4.3. Generation methods of multiple paths . . . . . . . . . . . 6 5. Multipath routing Protocol with path identifier . . . . . . . 6 5.1. Assumptions . . . . . . . . . . . . . . . . . . . . . . . 6 5.2. Link Metrics . . . . . . . . . . . . . . . . . . . . . . . 7 5.3. Path Metrics . . . . . . . . . . . . . . . . . . . . . . . 8 5.4. Multi-path Routing Algorithm . . . . . . . . . . . . . . . 8 5.5. Packet Transmission . . . . . . . . . . . . . . . . . . . 9 6. Extension of ad hoc routing protocols . . . . . . . . . . . . 9 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 8. Security Considerations . . . . . . . . . . . . . . . . . . . 9 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9.1. Normative References . . . . . . . . . . . . . . . . . . . 9 9.2. Informative References . . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10 Park, et al. Expires January 14, 2011 [Page 2] Internet-Draft Multi-path routing solution July 2010 1. Introduction A Mobile Ad hoc NETwork (MANET) consists of a loosely connected group of mobile devices (formally routers). The group means having the boundary of the packet reachability. The mobile devices are equipped with homogeneous or heterogeneous multiple network interfaces. In this document, these mobile devices are called by the MANET routers. That is, A MANET may be an autonomous and isolated system of MANET routers. MANET routers have methods of IP prefix allocation and address autoconfiguration on the multiple interfaces. The MANET routers(MNRs) may have multiple mobile hosts over wireless communications. They carry traffic originating at and/or destined for mobile hosts. Even though the mobile hosts being under the control of MANET routers are initiators or receivers of packet traffic, this document does not consider the mobile hosts . But, the number of mobile hosts, the moving speed of mobile hosts and the QoS of application of mobile hosts may be considered to decide the number of multiple paths between the MANET routers. In other words, the MANET routers may organize and maintain multiple interfaces which may be used to support the multiple paths. But the MANET WG do not discuss the routing protocols which are based on multiple paths. In this document, a new routing method which attempts to make efficient use of multiple interfaces using existing standard DYMO or OLSRv2 is described. From now on, the MANET has the connectivities to the fixed network (e.g., the public Internet) through the gateway(s). Many feasible application (e.g., vehicle communication) may be required the network connection to the Internet. And also high quality of services should be required and supported. Therefore, this document is focused on IPv6 networking and multiple path routing among the MANET routers, which are the multiple interfaces with dynamic multiple channels in each. 2. Terminology 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 [1]. 3. Design Issues for Multiple Path Routings Park, et al. Expires January 14, 2011 [Page 3] Internet-Draft Multi-path routing solution July 2010 3.1. Supporting multiple interfaces The MNRs might have their own naming and addressing because it may be isolated from public networks and may be temporary. That is, the MNRs might have IPv6 prefixes and addresses, only used in their domain. They may also support address autoconfiguration through one or more MANET interfaces in each. These address autoconfigurations may be used in either flat or hierarchical MNRs to support the packet communications among MNRs through the multiple paths. 3.2. Defining multiple path selection criteria Generally, the multiple path routings are used to improve the end-to- end throughput. In these cases, multiple paths might be selected in order to maximize the utilization of interfaces and their channels in MANET routers. There are two major issues. One is determining path/link metrics to guarantee the path independency fully for deterministic time period. The other is method to distinguish new one from already selected paths. That is, it is required to define the identifier of each path to select the new path easily during the path discovery of routing protocols. 3.3. Relation between link/path metrics and multiple paths In general, MANET routings do not influence deeply in the method of link/path metric. If we consider the multiple paths as the proper way, the selection of link/path metric is more important because the throughput of simultaneous use of multiple paths is determined from link/path-disjoint. Therefore, link-, interface- and node-disjoint are most import features of multiple path selection. For example, the interfaces of MANET routers have an asymmetric link feature. It means that their routers can not get the role of transmitter or receiver at the same time. Therefore, routing protocols, based on symmetric link, might be changed. Even though the DSR routing may support the asymmetirc feature in a single interface, new routing methods might consider the multiple, heterogeneous and symmetric/asymmetric interfaces. The pair of incoming and outgoing interfaces may be required to support the bi- directional services. 3.4. Multiple Internet Connectivity The MNRs may support the multiple Internet connectivities through the border gateway(s). To get the multiple connectivity to the Internet, the global IP addresses and public DNS services might be taken. Park, et al. Expires January 14, 2011 [Page 4] Internet-Draft Multi-path routing solution July 2010 The MANETs and their routers may support the high/moderate mobility. But the border gateways may not consider their mobility. If we only consider the mobile hosts under the control of their MNRs, the NEMO and MANEMO works may be good choices. 3.5. Policy of using multiple paths Even thought the source node should be scheduled to forward packets by dispersing traffic loads through multiple paths, the data transmission is only under the control of application users in MANET. 4. Types of Multiple Path Routing Protocols There are many types for distinction of multiple path routings. For example, the number of interfaces, disjoint and the method of multipath generation are considered. 4.1. The number of interfaces The multiple path routings could be implemented over the single or multiple interfaces of MNR node. Herein, multiple interfaces are based on homogeneous or heterogeneous radio technology. In case of the multiple path routings over the single interface, the key issue of generating multiple paths is selection of multiple channels. According to use of multiple channels on MNRs, node- disjoint based multiple paths might be selected. In case of multiple path routings over the multiple interfaces, the key issue of generating multiple paths is considering the distinction of multiple links, interfaces and nodes. 4.2. Routing metrics The link/path metrics may be considered to support the independency of multiple paths, which were made during routing discovery. In here, multiple path routings are distinguished by using routing metrics as follows: o Multiple path routing supporting link-disjoint metric o Multiple path routing supporting interface-disjoint metric o Multiple path routing supporting node-disjoint metric o Multiple path routing supporting the combination of metrics Park, et al. Expires January 14, 2011 [Page 5] Internet-Draft Multi-path routing solution July 2010 4.3. Generation methods of multiple paths In IETF MANET WG, the standard ad hoc routing protocols have been developing such as DYMO and OLSRv2. According the reactive routing like DYMO, this document suggests the generation methods of multiple paths as follows: o Extension of reactive routing protocol o Independent reuse of reactive routing protocol The first mechanism means that route request and reply message pair should be used just once. Therefore, routing protocol should be extended to make the multiple paths. The method should also select the proper routing metrics to maximize the link/node's disjoint. The second means that the same or different routing methods are used repeatedly through the single or multiple interfaces. In this case, path identifier should be required to distinguish the multiple paths. Routing protocol identifier (ex. Dymo IDentifer) should be also required to check and process the different routing protocols. 5. Multipath routing Protocol with path identifier The new routing methods are kind of independent reuse of existing ad hoc routing protocols. The main concept of this protocol is to find interface-disjoint paths during the route discovery paths. In here, Two path metrics are used. That is, multipath routing algorithm based on interface-disjointness and interface separion policy performs route discovery repeatedly to improve the utilization of network resource for fixed or mobile host with multi-channel and multi-interface. 5.1. Assumptions This protocol assumes that each node is equipped with multiple radios which are tuned to different channels permanently or for a long time period with the following assumptions and policies: o Interface disjointness: Traditional multipath protocols usually define two types of disjoint paths, namely node-disjoint and link- disjoint. The node-disjoint and link-disjoint paths requre that the different paths do not have any common nodes and links on their paths, respectively. However, node-disjoint path does not work in multi- interface environments, since multiple traffic flows can be transmitted simultaneously using its multiple interfaces even if they share the same node. Therefore, an Park, et al. Expires January 14, 2011 [Page 6] Internet-Draft Multi-path routing solution July 2010 interface- disjoint path is newly defined as a path which does not share any inteface of the node with other paths. That is, inteface-disjointness allows multiple paths between source and destination to share the same intermediate node without using the same interface. Although the interface-disjoint paths share the same node, packet transmissions over each path can be performed independently through the multiple interfaces, because they use different multi-channel interfaces. Moreever, finding interface- disjoint paths can increase the number of disjoint routes as compardd to finding node-disjoint paths. o Incoming-outgoing interface separtion: In order to allow the concurrency of packet reception and transmission while forwarding the source traffic, an intermediate node has to separate outgoing interface from incoming interface when finding a path to the destination. This con reduce the queuing delay and improve the interface utilization of intermediate nodes on the path. o Two path metrics: Two metrics are used for estinating the path cost and the available capacity of the path based on interface utilization of each node, channel diversity, and inter-flow interference. But this assumption may be changed as considering network environments. o Maximum two paths: In order to reduce the overhead that the multipaht rouing will have in its route discovery process, this protocol assume that maximum two paths are found between the source and destination nodes. In case that the single path can provide sufficient bandwidth for the data traffic between the source and destination nodes, this protocol does not find the additional path because of the lack of benefit in the throughput and end-to-end delay. 5.2. Link Metrics Improving network performance is to avoid the acquisition of paths having bottleneck links when finding paths between the source nad destination nodes. In here, the bottleneck link is defined as the link having the lowest network resources in a wireless multi-hop network. That is, both a heavy transmitting node and its neighbor nodes suffer from lack of wireless channel resources due to the characteristics of a broadcast medium. Therefore, this protocol considers two kinds of link metrics: hindrance and aid factor. Hindrance factor means the influence of neighbors' packet transmissions such as neighbor's packet transmission and reception and blocking time due to the other neighbors' packet transmissions. Aid factor means the available bandwith of a link, which means the amount of data rate which can be spent in transmitting and receiving Park, et al. Expires January 14, 2011 [Page 7] Internet-Draft Multi-path routing solution July 2010 packets over the link. In this document, hindrance and aid factor will be called by Link Busy Time (LBT) and Available Link Bandwidth(ALB) in each. The detail methods of determining the link metric is out of scope. 5.3. Path Metrics Two path metrics are introduced: Accumulated LBT (ALBT) and Available Path Bandwidth (APB). ALBT is determined by a path cost which consists of the sum of LBTs of each link over a path and the largest value among sums of LBTs for each channel. On the other hand, the APB indicates the available bandwidth which can be spent for packet transmissions. In here, the APB can be interpreted as the available link bandwidth of the path for the intra-flow interference caused by neighbor links using the same cahnnel becaue each link shares the wireless channel resource among links assigned the same channel in the interference range when forwarding packets along the route. The detail methods of determining the path metric is out of scope. 5.4. Multi-path Routing Algorithm The routing discovery procedure conforms to the general reactive rouing protocols, such as AODV and DYMO. In these protocols, when a node has data to transmit to the destination node, it finds two interface-disjoint paths to the destination node through the multipath route discovery phase so that the two paths can be determined toward maximizing the APB and minimizing ALBT. The multipath route discovery peforms twice of Route Request (RREQ) and Route Reply (RREP) exchange to establish the primary and secondar paths between source and destination nodes. In here, the RREQ message contains the path-identifier (Path-ID) and link metrics such as LBT and ALB of each link. Path-ID may be used to find multiple paths having the same or less hop-count because multiple RREQ messages with the same sequence number and hop-count are not forwarded and are dropped at the intermediate nodes. In addition, the path-ID can be used to identify the primary and secondary paths. In the primary path discovery pahse, this protocol firstly caculates the link metrics. And then, RREQ message with primary path-ID is created and flooded. After that, Link metrics are caculated and accumulated into RREQ message in the intermediate nodes. Finally, the destination node collects several RREQ messages for a period time. Based on the path metric, the destination node selects the primary path with larger APB than the bandwidth required by the source node as well as with mimimum ALBT. Park, et al. Expires January 14, 2011 [Page 8] Internet-Draft Multi-path routing solution July 2010 In the secondary path discover, the protocol tries to find the interface-disjoint one from primary path in order to identify multiple paths to the same destination node. That is, RREQ message with secondary path-ID is created and flooded. if the primary path can provide the source node with sufficient bandwidth, the secondary path discovery does not be run. 5.5. Packet Transmission After establishimg multiple paths between source and destination nodes, the source node transmits packets through the multiple paths which have different APB. Therefore, the source node has to use scheduling algorithms to forward packets according to the multiple paths. Specific scheduling algorithms are out of scope. 6. Extension of ad hoc routing protocols These methods are not easy to satify the whole design critaria. FFS. 7. IANA Considerations This memo includes no request to IANA. This is an informational document. IANA requirements for MANET related protocols will be developed within the protocol specifications for MANET protocols. 8. Security Considerations The security considerations can not be applied to this document since this document does not specify a new protocol. 9. References 9.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Corson, M. and J. Macker, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999. Park, et al. Expires January 14, 2011 [Page 9] Internet-Draft Multi-path routing solution July 2010 9.2. Informative References [3] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing", RFC 3561, July 2003. [4] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. [5] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4", RFC 4728, February 2007. [6] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format", RFC 5444, February 2009. [7] Chakeres, I. and C. Perkins, "Dynamic MANET On-demand (DYMO) Routing", draft-ietf-manet-dymo-20 (work in progress), July 2010. [8] Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized Link State Routing Protocol version 2", draft-ietf-manet-olsrv2-11 (work in progress), April 2010. [9] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)", draft-ietf-manet-nhdp-14 (work in progress), July 2010. [10] Chakeres, I., Macker, J., and T. Clausen, "Mobile Ad hoc Network Architecture", draft-ietf-autoconf-manetarch-07 (work in progress), November 2007. Authors' Addresses Jungsoo Park ETRI/SRC 161 Gajeong-dong, Yuseong-gu Daejeon, 305-700 Korea Phone: +82 42 860 6514 Email: fnumber@gmail.com Park, et al. Expires January 14, 2011 [Page 10] Internet-Draft Multi-path routing solution July 2010 Hong-Jong Jeong Kyungpook National University 1370 Sankyuk-dong, Buk-gu Daegu 702-701 Korea Phone: +82 53 940 8590 Email: hjjeong@monet.knu.ac.kr Dongkyun Kim Kyungpook National University 1370 Sankyuk-dong, Buk-gu Daegu 702-701 Korea Phone: +82 53 950 7571 Email: dongkyun@knu.ac.kr HyeongJun Kim ETRI/SRC 161 Gajeong-dong, Yuseong-gu Daejeon 305-350 Korea Phone: +82 42 860 6576 Email: khj@etri.re.kr Park, et al. Expires January 14, 2011 [Page 11]