Internet Engineering Task Force M. Goyal
Internet-Draft University of Wisconsin Milwaukee
Intended status: Informational J. Martocci
Expires: September 3, 2010 Y. Bashir
T. Humpal
Johnson Controls
E. Baccelli
INRIA
March 2, 2010
A Performance Analysis of P2P Routing along a DAG in LLNs
draft-goyal-roll-p2p-performance-00
Abstract
In this draft, we analyze the point-to-point (P2P) routing
performance of RPL by comparing the shortest P2P route costs in a
sample network topology with the corresponding costs when routing
along a tree built to minimize the routing costs to the tree's root.
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 3, 2010.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
Goyal, et al. Expires September 3, 2010 [Page 1]
Internet-Draft draft-goyal-roll-p2p-performance-00 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. The Network Topology . . . . . . . . . . . . . . . . . . . . . 3
3. Comparing P2P Route Costs: Shortest Path Routing versus
Routing Along the Tree/DAG . . . . . . . . . . . . . . . . . . 4
4. Comparing P2P Route Costs When Routing Along the Tree/DAG:
Turning Around at First Common Ancestor Versus Turning
Around at Root . . . . . . . . . . . . . . . . . . . . . . . . 5
5. Traffic Load on the Links: Shortest Path Routing Versus
Routing Along the Tree/DAG . . . . . . . . . . . . . . . . . . 7
6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 8
7. Security Considerations . . . . . . . . . . . . . . . . . . . . 8
8. Informative References . . . . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9
Goyal, et al. Expires September 3, 2010 [Page 2]
Internet-Draft draft-goyal-roll-p2p-performance-00 March 2010
1. Introduction
In this draft, we analyze the point-to-point (P2P) routing
performance of RPL [I-D.ietf-roll-rpl] by comparing the shortest P2P
route costs in a sample network topology with the corresponding costs
when routing along a tree built to minimize the routing costs to the
tree's root. Such a tree represents an RPL directed acyclic graph
(DAG), which, in general, allows a node to have multiple parents as
opposed to a single parent allowed in a tree.
Point-to-point routing along a DAG, as described in RPL
specification, works in the following manner. Two nodes, in each
other's radio range, can send packets to each other directly.
However, if two nodes are not in each other's radio range, they can
send packets to each other only along the DAG links, which means that
a packet travels up the DAG until it reaches a node that knows of the
downwards route to the destination and then it travels down the DAG
towards its destination. A node that belongs to a DAG must maintain
one or more parents in the DAG that serve as the default next hops
for packet forwarding. In addition, a node may optionally maintain
downwards routing information for its descendants in the DAG. The
DAG root may need to maintain downwards routing information for all
the nodes in the DAG. In the best case point-to-point scenario in a
DAG, the packet travels up the DAG only till it encounters the first
common ancestor of the source and the destination. In the worst
case, the packet may need to travel all the way to the DAG's root
before it starts its downward journey towards the destination. The
routing cost along a DAG for a source-destination pair refers to the
sum of the link costs along the route between the source and the
destination along the DAG (up the DAG and then down). While routing
along a DAG is constrained to the links in the DAG, the shortest
route from a source to a destination is calculated without any
restrictions.
2. The Network Topology
The performance analysis, presented in this draft, was done on a
network of 1001 nodes distributed in a 632m X 632m region. This
number represents the expected upper limit on the number of nodes per
DAG in the future real deployments. The node locations were
determined one-by-one in the following manner. The x and y
coordinates of a new location were determined in a uniform random
fashion in range {0m,632m} under the constraint that the minimum
distance between a new location and an existing location should not
be less than 10m or larger than 30m. This was done to ensure that a
new location is always in the radio range of atleast one existing
location. The radio range for each node in these simulations was a
Goyal, et al. Expires September 3, 2010 [Page 3]
Internet-Draft draft-goyal-roll-p2p-performance-00 March 2010
circle with radius 31.45m. Thus, we ensured that there were no
partitions in the network topology.
Figure 1 illustrates various aspects of the network topology. Figure
1a gives a visual representation of the network topology and Figure
1b shows the connectivity in the topology in terms of the number of
nodes with a given number of neighbors in their radio range. Figure
1c shows the number of source-destination pairs with a given minimum
hop distance between them. The performance analysis presented in
this draft is based on both unit link costs as well as link costs
distributed between 1 and 16 in the following manner. As per RPL
specification, the link cost values 1, 4 and 16 signify a perfect,
normal and an almost unusable link respectively. The link cost
between two neighbor nodes in the network topology was determined as
2^x rounded to the closest integer, where x is a real number
uniformly distributed over range [0,4]. The same cost value was used
for both directions of the link. Figure 1d shows the distribution of
link costs calculated in this manner. Figures 1e and 1f show the
shortest path tree (representing a DAG), minimizing each node's cost
to reach the tree's root, based on the unit link costs and the link
costs calculated in the manner described above respectively.
3. Comparing P2P Route Costs: Shortest Path Routing versus Routing
Along the Tree/DAG
Figures 2 and 3 compare the costs of shortest routes with the costs
when routing along a DAG. In these figures, the DAG is represented
by a shortest path tree, referred to as the common tree in the
figures, minimizing each node's cost to reach the tree's root.
Figure 2 shows the results when using unit link costs (i.e. the
shortest routes are the minimum hop routes) and Figure 3 shows the
results when link costs are distributed between 1 and 16 in the
manner described earlier.
Consider figure 2a. The figure shows the cost comparison (when using
unit link costs) for the source-destination pairs whose shortest
routes are 2 to 5 hops long. Examining the cost comparison for these
source-destination pairs is important because, in many LLN
applications, point-to-point communication typically takes place
between nodes that are located close to each other although not
necessarily in each other's radio range. Since the network topology
used for performance comparison consists of 1001 nodes, there are a
total of 1001000 different source-destination pairs. Out of these,
160788 source-destination pairs were observed to be 2 to 5 hops apart
(19538 pairs 2 hops apart; 32634 pairs 3 hops apart; 47334 pairs 4
hops apart and 61282 pairs 5 hops apart). Figure 2a shows the
corresponding number of hops (in green) when routing between the
Goyal, et al. Expires September 3, 2010 [Page 4]
Internet-Draft draft-goyal-roll-p2p-performance-00 March 2010
source and destination takes place along the tree/DAG. The figure
also shows (in blue) the average number of hops traversed when
routing along the tree/DAG. For the nodes that are only 2, 3, 4 and
5 hops away from each other, the average number of hops when routing
along the tree/DAG becomes 7.41, 8.95, 10.11 and 11.1 respectively.
The corresponding worst case hop distance when routing along the
tree/DAG was observed to be 34, 33, 32 and 32 respectively. As
demonstrated later, this significant increase in the hop count when
routing along the tree/DAG translates into significant increase in
the traffic load on the links, which will result in a serious
deterioration in the packet loss rate and latency for LLN
applications. Figures 2b and 2c show the corresponding comparison
for source-destination pairs that are 6 to 10 and higher hops away
from each other respectively. These figures demonstrate that the
routing along the DAG results in packets traveling much higher number
of hops than what they would when using shortest routes.
Figure 3 shows the cost comparison between shortest routes and routes
along a DAG when link costs are distributed between 1 and 16. Figure
3a} shows the comparison for source-destination pairs that have
shortest route costs less than 10. Figures 3b and 3c show the
comparison for source-destination pairs that have shortest route
costs from 10 to 30 and higher respectively. These results are
similar to the results obtained with unit link costs and confirm that
the routing along the DAG may result in much higher route costs than
shortest (or minimum cost) routes.
4. Comparing P2P Route Costs When Routing Along the Tree/DAG: Turning
Around at First Common Ancestor Versus Turning Around at Root
RPL allows a destination to advertize itself to its ancestors in the
DAG via the destination advertisement option (DAO) mechanism.
However, a node that receives routing information about a descendant
in the DAG may choose not to store this information because of memory
constraints. In that case, the node simply adds itself to the
\emph{reverse route stack} stored in the DAO packet and forwards it
to a parent. Thus, the P2P route along the DAG from a source to a
destination may not always turnaround at the first common ancestor of
the source and the destination. In the worst case, a packet may have
to travel all the way to the DAG's root before moving downwards
towards its destination. In figures 2 and 3 discussed in the
previous section, the costs associated with DAG-based routing were
calculated assuming that the turnaround takes place at the first
common ancestor of the source and the destination. In this section,
we compare the costs associated with DAG-based P2P routing when the
turnaround takes place at the first common ancestor of the source and
the destination versus when the packet travels all the way to the
Goyal, et al. Expires September 3, 2010 [Page 5]
Internet-Draft draft-goyal-roll-p2p-performance-00 March 2010
DAG's root before turning around.
Figure 4 shows the cost comparison in two cases when all links have
unit costs. Figure 4a shows the comparison for the source-
destination pairs that are 2 to 5 hops away when routing along the
DAG and turning around at the first common ancestor. Figures 4b and
4c show the comparison for the source-destination pairs that are 6 to
10 and higher hops away when routing along the DAG and turning around
at the first common ancestor. For a given number of hops travelled
(shown in red) along DAG when turning around at the first common
ancestor of a source and a destination, these figures show the
corresponding number of hops travelled (shown in green) when the
packets have to go all the way to the root before turning around.
These figures also show (in blue) the average hop count when the
turnaround takes place at the root for the source-destination pair
with a particular hop count when the turnaround takes place at the
first common ancestor. As figure 4a shows, for the source-
destination pairs that have a small hop count when the turnaround
takes place at the first common ancestor, the hop count when the
turnaround takes place at the root can be much higher. However, as
the hop count with turnaround at the first common ancestor increases
(figures 4b and 4c), the difference with the hop count with
turnaround at the root decreases. As figure 4c shows, when a source
and a destination are far apart, in most cases the root itself is the
first common ancestor between the source and the destination and
hence the hop count is same in both cases.
Figure 5 shows the cost comparison when link costs are distributed
between 1 and 16. These results follow the same trend as the results
with unit link costs. Routing cost when the turnaround takes place
at the root could be significantly higher if the cost is small when
turnaround takes place at the first common ancestor (Figure 5a). As
the routing cost with turnaround at the first common ancestor
increases (Figure 5b), the difference with turnaround at the root
decreases. When routing cost with turnaround at the first common
ancestor itself is significant (Figure 5c), generally the root itself
is the first common ancestor and hence the routing cost is same in
both cases.
In Section Section 3, we demonstrated that the DAG-based P2P routing
costs (with turnaround at the first common ancestor) can be
significantly higher than the minimum route costs, especially when
the source and the destination are close to each other (but not in
the radio range). The trends described in figures 4 and 5 indicate
that the DAG-based P2P routing costs further deteriorate (especially
for closeby endpoints) when the turnaround takes place at the root
rather than at the first common ancestor. Thus, if an LLN
application employs many P2P flows and most P2P flows are between
Goyal, et al. Expires September 3, 2010 [Page 6]
Internet-Draft draft-goyal-roll-p2p-performance-00 March 2010
closeby endpoints, it may be beneficial to require most/all DAG nodes
to store downwards routing information about their descendants.
5. Traffic Load on the Links: Shortest Path Routing Versus Routing
Along the Tree/DAG
In this section, we demonstrate how the increase in hop-count/
route-cost with DAG-based routing (with turnaround at the first
common ancestor) translate in terms of increase in the traffic loads
on the links. For this purpose, we chose two sets of P2P flows and
calculated the link-level traffic loads on the network while carrying
these flows. The first set consisted of 1000 flows selected in the
following manner: each node in the network (except the root) randomly
selects a node in its 2 to 5 hop neighborhood (i.e. the nodes that
can be reached in 2 to 5 hops with shortest path routing) and sends 1
packet every second to this node. The second set consisted of 10000
flows with each node selecting 10 nodes in its 2 to 5 hop
neighborhood and sending each one of them 1 packet per second. Then,
we calculated the traffic load on each link when these flows are
routed along the common tree/DAG (with turnaround at the first common
ancestor) and when shortest path routing is used. The traffic load
on a link is calculated simply as the sum of traffic of all the flows
that pass through the link.
Figures 6a and 6b show the link level traffic loads in the network
with 1000 flows under unit link costs and costs distributed between 1
and 16 respectively. Figures 6c and 6d show the corresponding
results for 10000 flows. There are a total of 9044 links in the
topology and the figures do not show the links that were not used at
all. The values shown in these figures were first sorted in
increasing order of the traffic loads under DAG-based routing and
then under shortest path routing. The traffic loads were displayed
on a log scale to accomodate the vast range of traffic loads. These
figures clearly indicate that DAG-based routing results in large
overloads on a fraction of links that end up being a part of a large
number of flows. Notice that the DAG-based routing results shown in
these figures were based on the turnaround taking place at the first
common ancestor of the source and the destination. The traffic
overloads can be expected to be much worse in the links closer to the
DAG root if all the packets were to travel to the DAG root before
turning around.
Figure 7 shows the topological view of the traffic loads on the links
for 10000 flows under shortest path routing and DAG-based routingwith
turnaround at the first common ancestor of the source and the
destination. The links are color-coded in the following manner. All
links with traffic load more than 100 packets/sec have been colored
Goyal, et al. Expires September 3, 2010 [Page 7]
Internet-Draft draft-goyal-roll-p2p-performance-00 March 2010
red. Links with traffic load between 50 and 100 packets/sec have
been colored orange. Links with traffic load between 20 and 50
packets/sec have been colored green while the links with traffic load
less than 20 packets/sec (but more than 0) have been colored blue.
Links that are not used at all are not shown. A traffic load of 100
packets/sec or more can be considered excessive for links using
popular IEEE 802.15.4 MAC/PHY protocols. The maximum data rate
possible on an IEEE 802.15.4 link is 250 Kbps which translates to the
maximum capacity of 208 packets/sec when the PHY-level packet size is
133 bytes (the maximum possible value). In practice, because of
hardware-related issues and CSMA-based competition among nodes for
packet transmission, the achievable packet rates are much smaller. A
traffic load of 100 packets/sec on a link is likely to result in
excessive packet loss and large delays for packets that do manage to
get transmitted successfully. Even a traffic load between 50 and 100
packets/sec can be considered large and such links are likely to
suffer heavy packet loss and latency.
As figures 7a and 7c show, shortest path routing was able to support
10000 flows in the sample network topology with only very few links
exceeding the traffic load of 50 packets/sec. On the other hand,
DAG-based routing, even when the turnaround takes place at the first
common ancestor, results in a significant number of (orange/red)
links having a traffic load of more than 50 packets/sec (figures 7b
and 7d). Such heavily loaded links are likely to suffer heavy packet
losses and latency. Clearly, DAG-based routing is not able to
support as many P2P flows in a network as the shortest path routing.
6. Conclusion
In this draft, we compared the P2P routing cost of DAG-based routing
with optimal shortest path routing for a sample 1000 node topology.
The results clearly demonstrate the inadequacy of DAG-based P2P
routing. The difference in cost between DAG-based routing and
shortest path routing is particularly appalling for the source-
destination pairs that are close to each other. This difference is
likely to worsen as the number of nodes that constitute a DAG further
increases. Clearly, there is a need to develop additional P2P
routing mechanisms, either within RPL or as separate protocols, that
can provide more optimal P2P routes. A scenario where the DAG-based
routing is the only P2P routing option may not be acceptable to LLN
applications that rely heavily on P2P flows.
7. Security Considerations
TBD
Goyal, et al. Expires September 3, 2010 [Page 8]
Internet-Draft draft-goyal-roll-p2p-performance-00 March 2010
8. Informative References
[I-D.ietf-roll-rpl]
Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing
Protocol for Low power and Lossy Networks",
draft-ietf-roll-rpl-06 (work in progress), February 2010.
Authors' Addresses
Mukul Goyal
University of Wisconsin Milwaukee
3200 N Cramer St
Milwaukee, WI 53201
USA
Phone: +1 414 229 5001
Email: mukul@uwm.edu
Jerald Martocci
Johnson Controls
Milwaukee, WI 53202
USA
Email: Jerald.P.Martocci@jci.com
Yusuf Bashir
Johnson Controls
Milwaukee, WI 53202
USA
Email: Yusuf.Bashir@jci.com
Ted Humpal
Johnson Controls
Milwaukee, WI 53202
USA
Email: Ted.Humpal@jci.com
Goyal, et al. Expires September 3, 2010 [Page 9]
Internet-Draft draft-goyal-roll-p2p-performance-00 March 2010
Emmanuel Baccelli
INRIA
Paris
France
Email: Emmanuel.Baccelli@inria.fr
Goyal, et al. Expires September 3, 2010 [Page 10]