Network Working Group J. Park Internet-Draft ETRI Intended status: Informational H. Jeong Expires: September 8, 2010 D. Kim KNU H. Kim ETRI March 7, 2010 Analysis and Solution of generating the Multi-Path Routings draft-park-manet-multipath-analysis-scenarios-01 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 to IETF in full conformance with the provisions of BCP 78 and 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 September 8, 2010. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. Park, et al. Expires September 8, 2010 [Page 1] Internet-Draft Multi-path Analysis & solution March 2010 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 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 BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Applications using Multiple Path Routing . . . . . . . . . . . 3 3.1. Load-balancing and Anti-eavesdropping . . . . . . . . . . 4 3.2. The stable and reliable wireless backbones in Mobile Mesh Networks . . . . . . . . . . . . . . . . . . . . . . 4 3.3. High Quality of Services for Mobile Hosts under the control of MANET Routers . . . . . . . . . . . . . . . . . 4 3.4. Internet Connectivity through the Multiple Gateways . . . 5 4. Design Issues for Multiple Path Routings . . . . . . . . . . . 5 4.1. Supporting multiple interfaces . . . . . . . . . . . . . . 5 4.2. Defining multiple path selection criteria . . . . . . . . 5 4.3. Relation between link/path metrics and multiple paths . . 5 4.4. Multiple Internet Connectivity . . . . . . . . . . . . . . 6 4.5. Policy of using multiple paths . . . . . . . . . . . . . . 6 5. Types of Multiple Path Routing Protocols . . . . . . . . . . . 6 5.1. The number of interfaces . . . . . . . . . . . . . . . . . 6 5.2. Routing metrics . . . . . . . . . . . . . . . . . . . . . 7 5.3. Generation methods of multiple paths . . . . . . . . . . . 7 6. Multipath routing Protocol with path identifier . . . . . . . 7 6.1. Assumptions . . . . . . . . . . . . . . . . . . . . . . . 8 6.2. Link Metrics . . . . . . . . . . . . . . . . . . . . . . . 9 6.3. Path Metrics . . . . . . . . . . . . . . . . . . . . . . . 9 6.4. Multi-path Routing Algorithm . . . . . . . . . . . . . . . 9 6.5. Packet Transmission . . . . . . . . . . . . . . . . . . . 10 7. Extension of ad hoc routing protocol . . . . . . . . . . . . . 10 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 9. Security Considerations . . . . . . . . . . . . . . . . . . . 11 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 10.1. Normative References . . . . . . . . . . . . . . . . . . . 11 10.2. Informative References . . . . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 Park, et al. Expires September 8, 2010 [Page 2] Internet-Draft Multi-path Analysis & solution March 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 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 routing protocol 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. Applications using Multiple Path Routing The synonymous technologies of MANET networking are Mobile Packet Radio Networking, Mobile Mesh Networking and Mobile, Multihop, Wireless Networking. MANET applications are requred to support the Park, et al. Expires September 8, 2010 [Page 3] Internet-Draft Multi-path Analysis & solution March 2010 dynamic ad hoc networking technology. Herein, the 'dynamic' means moderate/high degrees of mobility and the 'ad hoc' means a temporary network. Therefore, the most important things are keeping reliable and long-lived routes for MANET applications. 3.1. Load-balancing and Anti-eavesdropping Each MANET router has a single wireless interface. The MANET routers may be spatially distributed and their communication ranges may be changed because they move. Therefore, all routers might communicate through one or more intermediate routers The MANET networks are more vulnerable. The eavesdropping on packet communciations is easy if intermediate routers are only attacked. If the traffic is dispersed by using MANET routers with multiple interfaces, the load-balancing service is supported and in the same time the probability of eavesdropping may be decreased. 3.2. The stable and reliable wireless backbones in Mobile Mesh Networks The Mobile Mesh networks are used as the wireless backbone to replace wired backbone. The mesh networks might be used as 'transit networks'. That is, they are normally used to support the last mile communication services to home network, city network, etc. But the mobile feature may be not considered currently. The Mesh networks might support more reliable and stable features in order to forward the packets like wired networks. Therefore, multiple path routings using homogeneous or heterogeneous multiple interfaces may be a candidate. In these cases, path and interface(channel) independency is most import issue. 3.3. High Quality of Services for Mobile Hosts under the control of MANET Routers The MANET means Mobile, Multihop, Wireless networks. Each MANET Router (MNR) has one or more MANET interfaces. The MANET interfaces recognize and process each routing protocol to ensure MANET communications. And The MANET interfaces also include zero or more non-MANET interfaces which forward the packets towards (mobile) hosts. These non-MANET aware interfaces do not have to be aware of MANETs' characteristics. But, we consider the mobile host's mobility features (e.g., moving speed, join/leave rate, etc.) and required the QoS of mobile host applications in order to decide to keep the number of multiple path between MANET routers. Park, et al. Expires September 8, 2010 [Page 4] Internet-Draft Multi-path Analysis & solution March 2010 3.4. Internet Connectivity through the Multiple Gateways The MANETs might consider Internet connectivities and moving MNR with multiple (mobile) hosts. The multiple gateways may be used to support high quality of services. In cases, multiple path routing is more useful between MNR(s) and gateway(s) or between MNR(s) and MNR(s). Herein, the gateway function may be implemented in MANET router, which do not support the mobility features. And the moving MNR is out of scope in this document. 4. Design Issues for Multiple Path Routings 4.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 IP prefixes and addresses, only used in their domain. They may also support each address autoconfiguration through one or more MANET interfaces. These address autoconfigurations may be used in either flat or hierarchical MNRs to support the packet communications among MNRs through the multiple paths. 4.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. 4.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. Park, et al. Expires September 8, 2010 [Page 5] Internet-Draft Multi-path Analysis & solution March 2010 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 protocols 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. 4.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. 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. 4.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. 5. 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 in this document. 5.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 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. Park, et al. Expires September 8, 2010 [Page 6] Internet-Draft Multi-path Analysis & solution March 2010 5.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 5.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 protocols 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. 6. Multipath routing Protocol with path identifier The new protocol is kind of independent reuse of existing ad hoc routing protocol. The main concept of this protocol is to find interface-disjoint paths during the route discovery pahse. 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. Park, et al. Expires September 8, 2010 [Page 7] Internet-Draft Multi-path Analysis & solution March 2010 6.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 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. Park, et al. Expires September 8, 2010 [Page 8] Internet-Draft Multi-path Analysis & solution March 2010 6.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 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. 6.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. 6.4. Multi-path Routing Algorithm The routing discovery procedure conforms to the general reactive rouing protocols, such as AODV and DYMO. In this protocol, 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 Park, et al. Expires September 8, 2010 [Page 9] Internet-Draft Multi-path Analysis & solution March 2010 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. 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. 6.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. 7. Extension of ad hoc routing protocol TBD 8. 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. Park, et al. Expires September 8, 2010 [Page 10] Internet-Draft Multi-path Analysis & solution March 2010 9. Security Considerations The security considerations can not be applied to this document since this document does not specify a new protocol. 10. References 10.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. 10.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-18 (work in progress), February 2010. [8] Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized Link State Routing Protocol version 2", draft-ietf-manet-olsrv2-10 (work in progress), September 2009. [9] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)", draft-ietf-manet-nhdp-11 (work in progress), October 2009. [10] Chakeres, I., Macker, J., and T. Clausen, "Mobile Ad hoc Network Architecture", draft-ietf-autoconf-manetarch-07 (work in progress), November 2007. Park, et al. Expires September 8, 2010 [Page 11] Internet-Draft Multi-path Analysis & solution March 2010 Authors' Addresses Jungsoo Park ETRI/SRC 161 Gajeong-dong, Yuseong-gu Daejeon, 305-700 Korea Phone: +82 42 860 6514 Email: fnumber@gmail.com 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 September 8, 2010 [Page 12]