Low-power wireless networks play an important role in the Internet of Things. Typically, these networks consist of a very large number of lossy and low-capacity devices, challenging the current state of the art in protocol design. In this context the Trickle algorithm plays an important role, serving as the basic mechanism for message dissemination in notable protocols such as RPL and MPL. While Trickle's broadcast suppression mechanism has been proven to be efficient, recent work has shown that it is intrinsically unfair in terms of load distribution and that its performance relies strongly on network topology. This can lead to increased end-to-end delays (MPL), or creation of sub-optimal routes (RPL). Furthermore, as highlighted in this work, there is no clear consensus within the research community about what the proper parameter settings of the suppression mechanism should be. We propose an extension to the Trickle algorithm, called adaptive-k, which allows nodes to individually adapt their suppression mechanism to local node density. Supported by analysis and a case study with RPL, we show that this extension allows for an easier configuration of Trickle, making it more robust to network topology.
The authors of @cite_5 were the first to consider the effect of the redundancy constant @math on RPL's performance. They show that if configured incorrectly, Trickle's suppression mechanism can lead to sub-optimal routes, especially in networks that are heterogeneous in terms of density, such as random spatial topologies. This is again due to the inherent unfairness of Trickle's suppression mechanism. They propose a modification of Trickle, which tries to remove this unfairness by prioritizing nodes that have not broadcasted for a long period of time.
@cite_5
2145512846 2088079708 1986442642 1966381945
It is well known that in a network with arbitrary (convex) latency functions that are a function of edge traffic, the worst-case ratio, over all inputs, of the system delay caused due to selfish behavior versus the system delay of the optimal centralized solution may be unbounded even if the system consists of only two parallel links. This ratio is called the price of anarchy (PoA). In this paper, we investigate ways by which one can reduce the performance degradation due to selfish behavior. We investigate two primary methods (a) Stackelberg routing strategies, where a central authority, e.g., network manager, controls a fixed fraction of the flow, and can route this flow in any desired way so as to influence the flow of selfish users; and (b) network tolls, where tolls are imposed on the edges to modify the latencies of the edges, and thereby influence the induced Nash equilibrium. We obtain results demonstrating the effectiveness of both Stackelberg strategies and tolls in controlling the price of anarchy. For Stackelberg strategies, we obtain the first results for nonatomic routing in graphs more general than parallel-link graphs, and strengthen existing results for parallel-link graphs, (i) In series-parallel graphs, we show that Stackelberg routing reduces the PoA to a constant (depending on the fraction of flow controlled). (ii) For general graphs, we obtain latency-class specific bounds on the PoA with Stackelberg routing, which give a continuous trade-off between the fraction of flow controlled and the price of anarchy, (iii) In parallel-link graphs, we show that for any given class L of latency functions, Stackelberg routing reduces the PoA to at most α + (1 - α) · ρ(L), where α is the fraction of flow controlled and ρ(L) is the PoA of class L (when α = 0). For network tolls, motivated by the known strong results for nonatomic games, we consider the more general setting of atomic splittable routing games. We show that tolls inducing an optimal flow always exist, even for general asymmetric games with heterogeneous users, and can be computed efficiently by solving a convex program. Furthermore, we give a complete characterization of flows that can be induced via tolls. These are the first results on the effectiveness of tolls for atomic splittable games. RPL (IPv6 Routing Protocol for Low Power and Lossy networks) is a routing protocol recently standardized by the IETF. RPL has been designed to operate in energy-constrained networks with thousands of nodes, and therefore it is one of the most promising candidate routing protocols for Advanced Metering Infrastructure (AMI) networks. In this paper a performance evaluation of RPL is presented. An extensive study of the protocol is carried out with particular focus on Trickle, the algorithm adopted to control routing update distribution across the network. The performance of the protocol is analyzed considering different Trickle parameters in order to capture their impact on route formation and node power consumption. Results highlight that the nondeterministic nature of Trickle can lead to sub-optimal route formation especially when high message suppression is per-formed. In order to mitigate this issue, an enhanced version of the protocol, namely Trickle-F, is proposed in order to guarantee fair broadcast suppression. Trickle-F is demonstrated to be effective in obtaining more efficient routes with the same power consumption of the original version. Several high-speed TCP variants are adopted by end users and therefore, heterogeneous congestion control has become the characteristic of newly emerging high-speed optical networks. In contrast to homogeneous TCP flows, fairness among heterogeneous TCP flows now depends on router parameters such as queue management scheme and buffer size. To the best of our knowledge, this is the first study of fairness performance among heterogeneous TCP variants over a 10 Gbps high-speed optical network environment. Our evaluation scenarios for heterogeneous TCP flows consist of TCP variants with substantial presence in current Internet; therefore, TCP-SACK, CUBIC TCP (CUBIC) and HighSpeed TCP (HSTCP) compete for bottleneck bandwidth. Experimental results for fairness are presented for different queue management schemes, such as Drop-tail, Random Early Detection (RED), CHOose and Keep for responsive flows CHOose and Kill for unresponsive flows (CHOKe), and Approximate Fair Dropping (AFD), with varying degree of buffer sizes. We observe heterogeneous TCP flows induce more unfairness than homogeneous ones. Active queue management (AQM) schemes, RED, CHOKe, and AFD, improve fairness for large buffer sizes as compared to Drop-tail, whereas AQM schemes lose the fairness advantage for small buffer sizes. This study provides preliminary results for fairness challenges to deploy all-optical routers with limited buffer size. “The Trickle Algorithm” is conceived as an adaptive mechanism for allowing efficient and reliable information sharing among nodes, communicating across a lossy and shared medium. Its basic principle is, for each node, to monitor transmissions from its neighbours, compare what it receives with its current state, and schedule future transmissions accordingly: if an inconsistency of information is detected, or if few or no neighbours have transmitted consistent information “recently”, the next transmission is scheduled “soon” - and, in case consistent information from a sufficient number of neighbours is received, the next transmission is scheduled to be “later”. Developed originally as a means of distributing firmware updates among sensor devices, this algorithm has found use also for distribution of routing information in the routing protocol RPL, standardised within the IETF for maintaining a routing topology for low-power and lossy networks (LLNs). Its use is also proposed in a protocol for multicast in LLNs, denoted “Multicast Forwarding Using Trickle”. This paper studies the performance of the Trickle algorithm, as it is used in that multicast protocol.