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]