Csaba Kiraly
email: kiraly@fbk.eu

Bruno Kessler Foundation -Irst

Timofei Istomin
email: timofei.istomin@unitn.it

Oana Iova

Gian Pietro Picco
email: gianpietro.picco@unitn.it

D-RPL: Overcoming Memory Limitations in RPL Point-to-Multipoint Routing

RPL, the IPv6 Routing Protocol for Low-Power and Lossy Networks, supports both upward and downward traffic. The latter is fundamental for actuation, for queries, and for any bidirectional protocol such as TCP, yet its support is compromised by memory limitation in the nodes. In RPL storing mode, nodes store routing entries for each destination in their sub-graph, limiting the size of the network, and often leading to unreachable nodes and protocol failures. We propose here D-RPL, a mechanism that overcomes the scalability limitation by mending storing mode forwarding with multicast-based dissemination. Our modification has minimal impact on code size and memory usage. D-RPL is activated only when memory limits are reached, and affects only the portion of the traffic and the segments of the network that have exceeded memory limits. We evaluate our solution using Cooja emulation over different synthetic topologies, showing a six-fold improvement in scalability.

I. INTRODUCTION

RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF], the standard IPv6 Routing Protocol for Low-Power and Lossy Networks, has been designed to connect thousands of resource-scarce devices. The protocol creates a Destination-Oriented Directed Acyclic Graph (DODAG) topology starting from the border router, called root. This topology enables nodes in the network to send packets to the root while keeping only minimal routing state information: all traffic is simply forwarded through a preferred parent. For the root to send packets to the nodes, however, additional control messages have to be used and, even more important, much more routing state needs to be stored. As it was highlighted in early deployments [START_REF] Clausen | A Critical Evaluation of the IPv6 Routing Protocol for Low Power and Lossy Networks (RPL)[END_REF], this is the Achilles' heel of RPL: when used with resource-scarce devices, the routing tables fill quickly (especially near the root), impairing its scalability. Problem statement. RPL creates downward paths by using additional control messages called DAOs: Destination Advertisement Objects. The paths are built in reverse order, as DAO messages, initiated by each potential destination node, propagate towards the root. In the so-called storing mode, DAOs are sent to a node's preferred parent, and optionally can be acknowledged by it. Then, the preferred parent is in charge of further propagating the DAOs, ensuring the sender's reachability. For example, in Fig. 1a, D announces itself as a destination to the root by sending a DAO message to its preferred parent C, which adds it to its routing table, acknowledges it, and then forwards it further up in the DODAG.

Naturally, if a node cannot store a routing entry for a new destination, it should not retransmit its advertisement, as it is unable to forward traffic for that destination. The RPL standard specifies an optional DAO-ACK message with a Rejection status code (we call it a DAO-NACK) to notify the DAO sender that the recipient is unwilling to act as a DAO forwarder (e.g., if it lacks space in the routing table ). Still, the standard does not define a mechanism to handle this rejection. In fact, in popular Contiki and TinyOS implementations of RPL, such DAO-NACK is not even sent. As a result, the DAO may be silently dropped, leaving the path partially built and useless, as the destination remains unknown to all routers higher in the DODAG, including the root. The root has no choice than to drop incoming packets with unknown destination. Continuing with our example in Fig. 1b, now it is a turn of node E to send a DAO, announcing itself as a destination. However, assuming that B's routing table is limited to 2 entries, it cannot store this new destination and have to reject it, optionally sending a DAO-NACK. If, as in current open source implementations, the rejection is ignored, the information about E will not propagate up the DODAG. Consequently, all the packets destined to E will be dropped.

Existing solutions [3] [4] have focused on mixing the storing mode of RPL with its non-storing mode, where the root is the only node keeping routing information. However, the mode of operation is assigned statically to the nodes, resulting in a rigid structure and potentially non-optimal routing. Solution. In this paper we propose D-RPL, an algorithm that enables downward packets to bypass the path-agnostic area of the DODAG using a multicast mechanism. All the nodes that failed to advertise a DAO (for themselves or for someone in their sub-DODAG) join a special multicast group, whose address is used by the root to send data to destinations for which it does not have a route. The normal RPL unicast operation is resumed as soon as the packet reaches a group member knowing a route to the destination. Compared to the previously mentioned solutions, D-RPL dynamically adapts to appearance of "hot spots" in the topology. We present a detailed description of D-RPL in the next section, and its performance evaluation using Cooja in Section III.

II. OUR SOLUTION: D-RPL

The proposed algorithm, D-RPL, goes into action when node C receives the DAO-NACK from B (Fig. 1c). At this point, the downward path to the destination E is only partly In essence, D-RPL enhances RPL's storing mode by modifying the root's behaviour, and by proposing a straightforward mechanism to handle DAO-NACK messages. We focus our discussion to the case of a single root, but our mechanism supports RPL networks with multiple roots as well.

Root behavior. For each packet, the root first checks its routing table for normal IP forwarding. If there is no route entry for the destination address, instead of dropping the packet, the root forwards it to the D-RPL multicast channel. As we can see in Fig. 2, the root first changes the packet's destination address to the multicast group address, and adds a special D-RPL IPv6 extension header that contains the original destination address 1 . Routing table based forwarding is resumed at the moment the packet reaches a junction node that knows a route to the packet's original destination.

Junction node behavior. By subscribing to the D-RPL multicast channel, a junction node enables the delivery of packets from the root to all the destinations in its routing table, even those for which it received a DAO-NACK. If a node receives several DAO-NACKs for different destinations, it joins the group only once. Note that a junction node should keep track of destinations for which it received DAO-NACK messages by marking corresponding routing table entries, for the following reason: if all the junction nodes were to forward all the packets received on the D-RPL group for which they know (i.e. have a routing table entry to) the original destination, they would introduce duplicates in the network. For example, 1 The extension header is inserted after the RPL hop-by-hop option header. Other possibilities to achieve the same functionality could be the use of an IPv6 destination option header or to use generic IPv6 tunneling. let us assume that, in Fig. 1c, there is a node C between C and E, which is a junction node for other destinations, but not for E. In this case, both C and C would forward the packet, thus E would receive all the packets from the root in duplicate. To overcome this problem, the junction node should only act upon packets whose destination received a DAO-NACK. Otherwise, the message is dropped. Using this simple rule in our example, C is the only junction node in the network to resume routing table based forwarding for the packets that have E as a destination.

To reduce traffic overhead in space and time to the necessary minimum, nodes that have no more marked route entries can leave the D-RPL group.

Implementation. In principle, D-RPL could use any multicast protocol like MPL (Multicast Protocol for Low power and Lossy Networks) [START_REF] Hui | Multicast Protocol for Low power and Lossy Networks (MPL) draft-ietf-roll-trickle-mcast-12[END_REF], or SMRF (Stateless Multicast RPL Forwarding) [START_REF] Oikonomou | Stateless Multicast Forwarding with RPL in 6LowPAN Sensor Networks[END_REF], or build on a multicast already embedded in the RPL implementation, significantly reducing the need for extra code. We have implemented D-RPL on top of Contiki RPL, using the SMRF protocol that is already part of the Contiki codebase. SMRF has no per-packet state, and only very little structure-related state. In SMRF, multicast DAO messages are initiated by nodes joining the group and propagated up the RPL DODAG. Nodes receiving these messages, even if they did not join the group, store the multicast address in their routing table and forward the DAO message upwards. Thus, nodes that have exhausted their memory can still use SMRF, given that only a single multicast routing table entry is reserved for the D-RPL multicast address.

Our implementation of D-RPL includes some modifications to ContikiRPL and SMRF. First of all, we have extended ContikiRPL with the sending and reception of DAO-ACK and NACK messages: a requisite for D-RPL operation, but also an optional part of the standard. We have also corrected the handling of sequence numbers in forwarded DAO messages, necessary to match an ACK to the corresponding DAO. In SMRF, we improved the propagation of DAO ACK messages, and changed the separation between packet reception and forwarding, improving the group join time and reliability of SMRF, respectively. While the above changes are beneficial for D-RPL, they do not affect the performance of ContikiRPL.

The code specific to D-RPL includes a hook in the IPv6 packet forwarding logic to divert packets on the D-RPL channel and to add the D-RPL extension header; the handling of the D-RPL extension header in the incoming packet processing code; an extension of routing table entries with DAO-ACK/NACK status field; and the corresponding logic in the RPL DAO-ACK handling code.

Table I shows the overall code and data memory increase and its breakdown. The cost of D-RPL alone is only 722 B of Flash and 124 B of RAM, which is very small. Of course, we need to consider also the cost of the multicast layer, however, in applications that already use it, this is amortized.

III. PERFORMANCE EVALUATION

We evaluate D-RPL using Cooja emulator, which allows us to test exactly the binary that would run on real TelosB WSN nodes, and provides full freedom in evaluating radio environments and topologies. We fixed the routing table to 60 entries, which is the maximum number that fits in RAM if all the RAM is allocated for the network stack, without leaving any space for the application. ContikiMAC is used as the underlying duty-cycling MAC layer. For the radio model, we use Cooja's MRM code supporting SINR-based (Signalto-Interference-plus-Noise Ratio) reception and capture effect, with the addition of propagation path loss exponent. Table II summarizes the most important simulation parameters.

Nodes are deployed in a 2D grid with 20 m distance from each other, and a small randomization (±2 m) to avoid tie situations due to unrealistic regularity. For the root placement, we studied both center and corner locations. After a 4 minute warm-up period, a message with 8 B of application data is sent with UDP over IPv6 every 10 s to a randomly selected node. 500 messages are being sent in each run. Simulations are repeated 30 times with different random seeds for statistical relevance, curves show mean and its 95% confidence interval. Scalability. The left plot of Fig. 3 shows the packet delivery ratio (PDR) averaged over all nodes and all messages sent 2 , as a function of the number of nodes in the network. ContikiRPL performance starts to degrade at 60 nodes, since the root, and nodes near the root, run out of routing table entries. The degradation is severe, proportional to the ratio of the routing table size to the number of nodes in the network, and independent of root placement. D-RPL yields considerably higher performance for the whole studied range.

In the case of D-RPL, there is a slight decrease of PDR with scale because: i) the network diameter increases, leading to occasional losses on longer multi-hop wireless paths; ii) more DAO messages (control packets used by RPL to create and maintain the downward routes) are sent, increasing congestion near the sink. Average PDR is somewhat lower with the root in the corner, due to larger hop counts; nevertheless it exceeds 60% with 529 nodes, while all the nodes remain reachable, achieving 6-fold improvement compared to ContikiRPL.

The center plot of Fig. 3 provides more insights into the differences in protocol operation by showing average radio duty cycle (including both listening and TX time). For less than 60 nodes, the two protocols behave almost the same, since D-RPL does not get activated. Slight differences are due to the extra signaling traffic of DAO-ACKs in the D-RPL case.

Above 60 nodes, two important changes can be noticed: ContikiRPL curves remain low, but this is due to the fact that it is delivering messages to only a small portion of the nodes. From a network operational point of view, these duty cycle values, corresponding to low delivery rates, are almost irrelevant. The modified protocol operation of D-RPL, instead, kicks in for an increasing portion of the traffic, and its effect can clearly be seen on both curves.

The average duty cycle of D-RPL is increasing with the network size, since a growing portion of the messages are sent as link-local broadcasts instead of unicasts that, due to the way duty-cycling MACs operate, means that longer packet trains are being transmitted in each hop. Further, messages diverted to the D-RPL channel are spawned to multiple junction forwarders, also increasing duty cycle; this is the price to pay for scalability in a network of memory-constrained devices.

Interesting is the decrease of average duty cycle at larger network sizes: while the duty cycle near the root is increasing, at the edges of the network it is decreasing. Considering also that there are more nodes to average over, the overall value could stabilize or even decrease as the network scales.

Finally, the right plot of Fig. 3 shows that end-to-end delay of D-RPL is also increasing. Naturally, larger networks mean 2 For lack of space, we do not discuss per-node spatial distribution of PDR.

q qq q q q q q q q q q q q q q q q q q q q 0.00 0.25 0.50 0.75 1.00 0 200 400 number of nodes Mean PDR q q q q q q q q q q q q q q q q q q q q q q 1.00 1.25 1.50 1.75 0 200 400 number of nodes Radio duty cycle, % q q q q q q q q q q q q q q q q q q q q q q 500 2500 4500 0 200 400 number of nodes Mean delay, ms q q D-RPL, center D-RPL, corner RPL, center RPL, corner Fig. 3. Average PDR, radio duty cycle and delivery delay vs. network size (2D grid).

longer delivery paths, however a part of the increase is due to SMRF delaying packet forwarding with 1-4 cycles (125-500 ms) in each hop to avoid collision of broadcast messages, a well-known inefficiency in duty-cycled networks.

To summarize, D-RPL does not alter performance in the conditions when ContikiRPL works, but it can make the network operate at scales where ContikiRPL would fail. In these latter cases, the relative cost of packets delivered by D-RPL is higher than that of packets delivered by RPL, but this cost is only paid for packets that would otherwise not be delivered at all. q q q q q q q q q q q q 5 10 15 20 10 20 30 node distance, m Mean # neighbors q q q q q q q q q q q q 0.00 0.25 0.50 0. Node density. Network operation-including signal interference, L2 behavior, the structure of the constructed DODAG, and the hop count of downward routes-is also greatly influenced by node density. Fig. 4 The right side of Fig. 4 shows average PDR for two network sizes: 49 nodes, where routing could work even without D-RPL, and 121 nodes, where ContikiRPL is expected to fail.

At D = 30 m, the topology gets disconnected, thus neither protocol can deliver packets. There are also issues with dense networks, as shown for D ≤ 10 m. When the neighbor table is saturated, ContikiRPL operates incorrectly due to the asymmetry in neighbor relations [START_REF] Istomin | Is RPL ready for actuation? A comparative evaluation in a smart city scenario[END_REF]. Our D-RPL inherits this issue from its underlying ContikiRPL implementation. Still, it manages to alleviate the effects due to the introduction of the junction node, improving protocol performance.

For middle densities (10 m < D < 25 m), instead, density has no significant impact on average PDR.

IV. CONCLUSIONS AND FUTURE WORK Downward routing in RPL is constrained by the amount of memory allocated to routing table entries; with current open source implementations and hardware, a routing table of 50-60 entries fits in RAM if all the RAM is allocated for the network stack, without leaving space for the application itself. This is a serious limitation for a protocol that targets the LLN (low-power and lossy network) ecosystem.

We proposed the D-RPL extension to the standard, enhancing scalability when the above limits are exceeded. In this initial evaluation, our fully functional prototype showed at least 6-fold scalability improvement. Moreover, through an example of ContikiRPL's issue with large node densities, we showed that D-RPL can also improve RPL's robustness.

Whether D-RPL shows the same scalability improvements in real deployments with different radio conditions and topologies, and how the protocol works under higher traffic loads, are still open for future evaluation.

  joins the D-RPL multicast group and becomes a junction node. a) Construction of downward routes: D announces itself to the root.

Fig.

  Fig.1. The D-RPL algorithm (routing table of B is limited to 2 entries).

Fig. 2 .

 2 Fig. 2. Flow chart of a RPL root that implements D-RPL

Fig. 4 .

 4 Fig. 4. Average PDR vs. network density.

  1. The D-RPL algorithm (routing table of B is limited to 2 entries).

built, ending at node C. With D-RPL, C still plays a critical role, enabling E's reachability from the root, but instead of making the root aware of E's existence, C subscribes to the special D-RPL multicast channel. When the root wants to send a packet to E, or to another node for which it does not have a route, it simply sends it to all the nodes subscribed to this multicast channel. Since C is situated at the crossroad of two delivery mechanisms, multicast dissemination and forwarding based on routing table, we call it a junction node.

  compares the performance of D-RPL with ContikiRPL on 2D grids with different distances between neighboring grid nodes. To put our performance results in perspective, the left side shows average neighborhood size (N ) as a function of grid distance between nodes (D). Instead of trying to give a geometric interpretation of our SINR-based radio model, we show N as seen by the Contiki protocol stack itself, i.e. as the number of nodes in the neighbor table. N is limited to 20 by default in ContikiRPL.

	Although this could be increased, we have intentionally kept
	this limit since additional neighbor entries would take away
	valuable RAM resources from the system. With D = 20 m,
	i.e. the value used earlier, N is around 9, i.e. nodes can
	communicate with their grid neighbors, diagonal neighbors,

and 1-2 other nodes. D = 25 m corresponds to seeing the four grid neighbors only, while with D ≤ 15 m nodes can communicate directly to multiple grid hops in each direction.


P Benard

D Sykora

Amélie Fondevilla

Adrien Bousseau

Damien Rohmer

Stefanie Hahmann

Marie-Paule Cani

Towards developable products from a sketch

Introduction

Developable surfaces are surfaces that can be unfolded onto a plane, without distortion, and are widely used in industry We propose an end-to-end system for the interactive modeling of developable objects from a single annotated photo, restricted to the case of symmetrical objects made by assemblies of planes and generalized cylinders. Our method is in two parts : we first analyze the 2D annotated photo to extract the location of symmetric points and the rulings of the cylindrical regions. Then we use this 2D information in a global system to lift the shape of the object in 3D. * 15], is a sketch-based modeling system that reconstructs fashion items from sketches drawn from two orthogonal viewing directions. In contrast, our input is a network of 2D curves traced over a single picture and we exploit properties of developable surfaces to lift the drawing to 3D while ensuring that the output model is developable.

Generally speaking, single-view reconstruction of 3D shapes is an ill-posed problem, as a 2D picture can represent an infinite number of different 3D surfaces. Prior work managed to address this problem in a few specific cases, by complementing re-projection error minimization with specific geometric constraints. These constraints included parallelism and orthogonality [LS07], exact mirror-symmetry [CSMS13], or orthogonality of cross-sections in the case of engineering design sketches [XCS * 14]. We complement these approaches with a new constraint on surface developability.

Interpretation of the 2D curves

Our input is an annotated photo, called sketch : it contains 2D cubic Bezier splines corresponding to the seams, borders, and silhouettes of the object, assumed to be viewed from a close to orthographic projection. Additional information are provided for a subset of curves: each silhouette is marked as being one, and the pairs of symmetrical borders or seams are also indicated. Finally, the user annotates symmetrical features in the photo which are used to recover the normal vector n of the symmetry plane. We compute the set of minimal closed contours made by the Bezier splines, and each of them corresponds to a so-called surface patch, i.e. the visible border of the orthographic projection of a smooth C 2 developable surface.

Find 2D symmetrical correspondences Let us consider a 3D object which global mirror-symmetry with respect to a plane of normal n. All pairs of symmetrical points of the object can therefore be linked by a vector which is collinear to n. Note that this remains valid for the 2D orthographic projection of the object. Thus, we compute the location of symmetrical points in the 2D sketch by linking points of two curves annotated as symmetrical in 3D with a vector that is collinear to the line of symmetry s = n| z=0 .

Find 2D rulings of the cylindrical parts in the sketch Developable surfaces are ruled surfaces with a constant tangent plane along each ruling. We consider the specific case of developable cylindrical surfaces, defined as surface for which all rulings are collinear to each other. Indeed, this property also holds on the 2D projection of the surface. Koenderink's theory [START_REF] Koenderink | What does the occluding contour tell us about solid shape?[END_REF] indicates that the silhouette of a smooth developable surface is a straight line corresponding to a ruling of the surface. We use this criteria to compute the rulings in the specific case of developable cylindrical surfaces, defined as surface for which all rulings are collinear each other, with a visible silhouette. Our algorithm works as folllows.

Rulings propagation S 0 S 1 is the silhouette An initial ruling on the surface patch is provided by the straight silhouette segment. We then propagate the rulings using parallel translation through the patch with respect to this first ruling and the symetry analysis output described in the previous secttion, leading therefore to the set of projected rulings of the surface.

Compute 3D curves and surfaces

We use both the global symmetry assumption and the developability assumption to lift the curves of the sketch into 3D. These curves are represented using cubic Bezier splines, and we keep this representation in the lifting : the variables of our system are the 3D coordinates of the corresponding 2D control points of the curves in the sketch. We minimize a quadratic energy functional E defined as below :

E = ω 0 E devel + ω 1 Esym + ω 2 E minvar + ω 3 E proj (1)
where -E devel expresses the criteria of developability : it ensures the planarity of the extremities of each pair of consecutive rulings in a patch -Esym expresses the 3D mirror-symmetry of the symmetrical vertices in the curves, -E minvar is the minimal variation energy, similar to the one presented in [XCS * 14], -E proj ensures that the projection of the 3D curves remains close to the sketch.

We then compute a mesh for every patch of the model. Patches containing existing rulings are simply triangulated. All remaining surfaces are computed by using a standard linear varia-tional Laplacian-based method interpolating the given 3D patch boundaries [SHBS16, BK04]. Developability of all non cylindrical patches is finally obtained by applying some local optimization steps [WT04].

Conclusion

Results Some of our results are presented in Fig. 1 and2.

Limitations We restrict our method to developable patches that are cylindrical. The method for propagating rulings remains correct if the patch contains planar parts, since all lines linking two boundary vertice of a planar patch is a ruling of the surface but cannot account for patches that contains conical parts.

Figure 1 :

 1 Figure 1: Our method reconstructs 3D volume of piece-wise developable objects from a single annotated sketch.

  c 2017 The Author(s) Eurographics Proceedings c 2017 The Eurographics Association.Amélie Fondevilla 1 , Adrien Bousseau 2 , Damien Rohmer 1,3 , Stefanie Hahmann 1 , Marie-Paule Cani 1

Figure 2 :

 2 Figure 2: Example of result : 2D interpretation (b,c) and 3D reconstruction (d) of the annotated photo (a)

  Developable surfaces are ubiquitous in design, architecture and fashion, which has motivated the development of dedicated modeling systems. Many such methods take as input an existing 3D model and deform it to achieve developability [WT04], or approximate it with developable panels [LPW * 06, KFC * 08, TBWP16].

	Alternatively, lofting methods find developable surfaces that inter-
	polate 3D boundary curves [Fre02, RSW * 07]. Closer to our work,
	SketchingFolds [JHR

c 2017 The Author(s) Eurographics Proceedings c 2017 The Eurographics Association.