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]