IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
Optimal Memory-aware Sensor Network Gossiping (or How to Break the Broadcast Lower Bound)
Get PDFGossiping is a well-studied problem in Radio Networks. However, due to the strong resource limitations of sensor nodes, previous solutions are frequently not feasible in Sensor Networks. In this paper, we study the Gossiping problem in the restrictive context of Sensor Networks. We present a distributed algorithm that completes Gossiping with high probability in a Sensor Network of unknown topology and adversarial start-up. This algorithm exploits the geometry of sensor node distributions to achieve an optimal running time of Θ(D + ∆), where D is the diameter and ∆ the maximum degree of the network. Given that any algorithm for Gossiping also solves the Broadcast problem, this result shows that the classical Broadcast lower bound of Kushilevitz and Mansour does not hold if nodes are allowed to do preprocessing. The proposed algorithm requires that a linear number of messages be stored and transmitted per unit time. We also show an optimal distributed algorithm that solves the problem in linear time for the case where only a constant number of messages can be stored.TRUEpu
Framework for Loop-Free Convergence Using the Ordered Forwarding Information Base (oFIB) Approach
No full textISSN: 2070-1721This document describes an illustrative framework of a mechanism for use in conjunction with link-state routing protocols that prevents the transient loops that would otherwise occur during topology changes. It does this by correctly sequencing the forwarding information base (FIB) updates on the routers.
This mechanism can be used in the case of non-urgent
(management action) link or node shutdowns and restarts or link metric changes. It can also be used in conjunction with a fast reroute mechanism that converts a sudden link or node failure into a non-urgent topology change. This is possible where a complete repair path is provided for all affected destinations.
After a non-urgent topology change, each router computes a rank that defines the time at which it can safely update its FIB. A method for accelerating this loop-free convergence process by the use of completion messages is also described.
The technology described in this document has been subject to extensive simulation using pathological convergence behavior and real network topologies and costs. However, the mechanisms described in this document are purely illustrative of the general approach and do not constitute a protocol specification. This document represents a snapshot of the work of the Routing Area Working Group at the time of publication and is published as a document of record. Further work is needed before implementation or deployment
Modeling and Exploiting the Relation Between Packet Losses and Hidden Traffic
Get PDFNowadays, it is common to find multiple WLAN deployments coexisting in shared spaces. The resulting interference between transmissions represents an important source of performance degradation, specially those originating from hidden traffic. This note explores the relation between hidden traffic and packet losses, using renewal theory to show that losses constitute biased samples of hidden traffic. Building on the developed analytical model, the paper derives the optimal frame length that maximizes throughput in the presence of hidden traffic. The results are validated using an 802.11 WLAN in-lab setting.pu
Green wireless: towards minimum per-bit linear energy consumption in wireless communications
Get PDFDOI: http://dx.doi.org/10.1145/2507924.2517481Low-energy communications is becoming an increasingly relevant research area, due to both economic and environmental reasons. Low-energy is particularly relevant in wireless because of the limited energy available to terminals and the high consumption of the base stations derived from wide geographical coverage. Green wireless aims to formulate a long term research goal in the wireless environment. In the talk, the speaker will present the motivation and formulation of this research goal, with an overview of the associated research challenges. The talk will also address in more detail one specific case of energy-efficiency consisting in the cross-factor, which consists of the energy penalty derived from a packet traversing the system protocol stack.FALSEpu
Improving Resource Location with Locally Precomputed Partial Random Walks
Get PDFV. Gramoli and R. Guerraoui (Eds.): NETYS 2013, LNCS 7853, pp. 144–158, 2013.
Springer-Verlag Berlin Heidelberg 2013Random walks can be used to search complex networks for a desired resource. To reduce search lengths, we propose a mechanism based on building random walks connecting together partial walks (PW) previously computed at each network node. Resources found in each PW are registered. Searches can then jump over PWs where the resource is not located. However, we assume that perfect recording of resources may be costly, and hence, probabilistic structures like Bloom filters are used. Then, unnecessary hops may come from false positives at the Bloom filters. Two variations of this mechanism have been considered, depending on whether we first choose a PW in the current node and then check it for the resource, or we first check all PWs and then choose one. In addition, PWs can be either simple random walks or self-avoiding random walks. Analytical models are provided to predict expected search lengths and other magnitudes of the resulting four mechanisms. Simulation experiments validate these predictions and allow us to compare these techniques with simple random walk searches, finding very large reductions of expected search lengths.TRUEpu
On the Compound Impact of Opportunistic Scheduling and D2D Communications in Cellular Networks
Get PDFOpportunistic scheduling was initially proposed to exploit user channel diversity for network capacity enhancement. However, the achievable gain of opportunistic schedulers is generally restrained due to fairness considerations which im- pose a tradeoff between fairness and throughput. In this paper, we show via analysis and numerical simulations that opportunistic scheduling not only increases network throu- ghput dramatically, but also increases energy efficiency and can be fair to the users when they cooperate, in particu- lar by using D2D communications. We propose to leverage smartphone’s dual-radio interface capabilities to form clus- ters among mobile users. We design simple, scalable and energy-efficient D2D-assisted opportunistic strategies, which would incentivize mobile users to form clusters. We use a coalitional game theory approach to analyze the cluster for- mation mechanism, and show that proportional fair-based intra-cluster payoff distribution brings significant incentive to all mobile users regardless of their channel quality.TRUEpu
RAZOR: A Compression and Classification Solution for the Internet of Things
Get PDFThe Internet of Things is expected to increase the amount of data produced and exchanged in the network, due to the huge number of smart objects that will interact with one another. The related information management and transmission costs are increasing and becoming an almost unbearable burden, due to the unprecedented number of data sources and the intrinsic vastness and variety of the datasets. In this paper, we propose RAZOR, a novel lightweight algorithm for data compression and classification, which is expected to alleviate both aspects by leveraging the advantages offered by data mining methods for optimizing communications and by enhancing information transmission to simplify data classification.
In particular, RAZOR leverages the concept of motifs, recurrent features used for signal categorization, in order to compress data streams: in such a way, it is possible to achieve compression levels of up to an order of magnitude, while maintaining the signal distortion within acceptable bounds and allowing for simple lightweight distributed classification. In addition, RAZOR is designed to keep the computational complexity low, in order to allow its implementation in the most constrained devices. The paper provides results about the algorithm configuration and a performance comparison against state-of-the-art signal
processing techniques.pu
Graph-based Techniques for Topic Classification of Tweets (Técnicas basadas en grafos para la categorización de tweets por tema)
No full textSEPLN 2013 – XXIX Congreso de la Sociedad Española para el Procesamiento del Lenguaje Natural, co-located with the Spanish Informatics Conference (CEDI2013 – IV Congreso Español de Informática)Topic classification of texts is one of the most interesting challenges in Natural Language Processing (NLP). In this work we present a technique based on graph similarity to classify Twitter messages as being related to a specific topic.TRUEpu