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]