Search

Load balancing in datacenter networks (DCNs) is an important and challenging task for datacenter managers. A number of sophisticated technologies have been proposed to improve load balancing performance in a complicated circumstance, i.e., with various traffic characteristics. Many approaches need a high cost to implement, such as changing switch hardware. The efficiency problem has not been well addressed. MPTCP was proposed as a low-cost approach to improve data transmission in DCNs, which uses subflows to balance workloads across multiple paths. However, current MPTCP is not satisfying, especially when there are rack-local flows or many-to-one short flows. In this article, we propose DCMPTCP to improve the efficacy of MPTCP. We gradually develop three mechanisms. First, DCMPTCP identifies rack-local traffic and eliminates unnecessary subflows to reduce the overhead. Second, DCMPTCP estimates flow length and establishes subflows in a smarter way. Third, DCMPTCP strengthens explicit congestion notification to improve the congestion control performance on inter-rack many-to-one short flows. We have implemented DCMPTCP in both the Linux kernel and ns-3 simulator. Our comprehensive testbed experiments and simulations show that DCMPTCP outperforms MPTCP in both 1 Gbps testbed, and 10 Gbps large-scale simulation network. [ABSTRACT FROM AUTHOR]

Many optimization techniques for networking protocols take advantage of topological information to improve performance. Often, the topological information at the core of these techniques is a centrality metric such as the Betweenness Centrality (BC) index. BC is, in fact, a centrality metric with many well-known successful applications documented in the literature, from resource allocation to routing. To compute BC, however, each node must run a centralized algorithm and needs to have the global topological knowledge; such requirements limit the feasibility of optimization procedures based on BC. To overcome restrictions of this kind, we present a novel distributed algorithm that requires only local information to compute an alternative similar metric, called Load Centrality (LC). We present the new algorithm together with a proof of its convergence and the analysis of its time complexity. The proposed algorithm is general enough to be integrated with any distance vector (DV) routing protocol. In support of this claim, we provide an implementation on top of Babel, a real-world DV protocol. We use this implementation in an emulation framework to show how LC can be exploited to reduce Babel's convergence time upon node failure, without increasing control overhead. As a key step towards the adoption of centrality-based optimization for routing, we study how the algorithm can be incrementally introduced in a network running a DV routing protocol. We show that even when only a small fraction of nodes participate in the protocol, the algorithm accurately ranks nodes according to their centrality. [ABSTRACT FROM AUTHOR]

At present, soft real-time data center applications are in a booming development and impose stringent delay requirements on internal data transfers. In this context, many recently proposed data center transport protocols share a common goal of minimizing Flow Completion Time (FCT), and the Shortest Remaining Processing Time (SRPT) scheduling algorithm has attracted widespread attentions for its superior performance in average FCT. However, SRPT suffers from the instability problem, incurring more and more flows left uncompleted even if the traffic load is within the fabric capacity, which implies unnecessary bandwidth waste. To solve the problem, this paper proposes a backlog-aware flow scheduling algorithm (BASRPT) for both giant switch and general topologies. Because of taking into account queue backlogs other than flow sizes at scheduling, we prove that BASRPT is stable and still maintains good FCT performance. To overcome the huge computation overhead and enable distributed implementation, a fast and practical approximation algorithm called fast BASRPT is also developed. Extensive flow-level simulations show that fast BASRPT indeed stabilizes the queue length and obtains a higher throughput while being able to push the FCT arbitrarily close to the optimal value in the condition of feasible traffic loads. [ABSTRACT FROM AUTHOR]

As we enter the era of many-core, providing the shared memory abstraction through cache coherence has become progressively difficult. The standard directory-based coherence does not scale well with increasing core count. Timestamp-based hardware coherence protocols introduced recently offer an attractive alternative solution. This paper proposes a timestamp-based coherence protocol, called TC-Release++ , that efficiently supports cache coherence in large-scale systems. Our approach is inspired by TC-Weak, a recently proposed timestamp-based coherence protocol targeting GPU architectures. We first design TC-Release in an attempt to straightforwardly port TC-Weak to general-purpose many-cores. But re-purposing TC-Weak for general-purpose many-core architectures is challenging due to significant differences both in architecture and the programming model. Indeed the performance of TC-Release turns out to be worse than conventional directory protocols. We overcome the limitations and overheads of TC-Release by exploiting simple hardware support to eliminate frequent memory stalls, and an optimized lifetime prediction mechanism to improve cache performance. The resulting optimized coherence protocol TC-Release++ is highly scalable (storage scales logarithmically with core count) and shows better performance (3.0 percent) and comparable network traffic (within 1.3 percent) relative to the baseline MESI directory protocol. We use Murphi to formally verify that TC-Release ++ is error-free and imposes small verification cost. [ABSTRACT FROM PUBLISHER]

This paper develops an offset-based response-time analysis technique for analyzing complex distributed real-time systems where processing and communication resources use the time-partitioning strategy to isolate the operation of separate software components. Time partitioning may be provided in the processors by an ARINC 653 compliant operating system, and in the networks via the TTP communication protocol. The software components executed by the system may themselves be distributed and complex, composed of many concurrent tasks and with one or more end-to-end flows that may have end-to-end timing requirements. The developed analysis supports hierarchical scheduling where a primary scheduler performs time partitioning into separate partitions, and secondary fixed-priority schedulers dispatch the different concurrent tasks inside each partition. It also supports end-to-end flows that are either synchronized with the partition schedule or not. This is the first time that this kind of analysis is developed. An evaluation of an improvement introduced in the analysis is discussed. Two representative case studies are described. [ABSTRACT FROM PUBLISHER]

Modern planetary scale distributed systems largely rely on a State Machine Replication protocol to keep their service reliable, yet it comes with a specific challenge: latency, bounded by the speed of light. In particular, clients of a single-leader protocol, such as Paxos, must communicate with the leader which must in turn communicate with other replicas: inappropriate selection of a leader may result in unnecessary round-trips across the globe. To cope with this limitation, several all-leader and leaderless alternatives have been proposed recently. Unfortunately, none of them fits all circumstances. In this article we argue that the “right” choice of the number of leaders depends on a given replica configuration and the workload. Then we present \mathsf Droopy and \mathsf Dripple , two sister approaches built upon state machine replication protocols. \mathsf Droopy dynamically reconfigures the set of leaders. Whereas, \mathsf Dripple coordinates state partitions wisely, so that each partition can be reconfigured (by \mathsf Droopy ) separately. Our experimental evaluation on Amazon EC2 shows that, \mathsf Droopy and \mathsf Dripple reduce latency under imbalanced or localized workloads, compared to their native protocol. When most requests are non-commutative, our approaches do not affect the performance of their native protocol and both outperform a state-of-the-art leaderless protocol. [ABSTRACT FROM AUTHOR]

The traditional single-level checkpointing method suffers from significant overhead on large-scale platforms. Hence, multilevel checkpointing protocols have been studied extensively in recent years. The multilevel checkpoint approach allows different levels of checkpoints to be set (each with different checkpoint overheads and recovery abilities), in order to further improve the fault tolerance performance of extreme-scale HPC applications. How to optimize the checkpoint intervals for each level, however, is an extremely difficult problem. In this paper, we construct an easy-to-use two-level checkpoint model. Checkpoint level 1 deals with errors with low checkpoint/recovery overheads such as transient memory errors, while checkpoint level 2 deals with hardware crashes such as node failures. Compared with previous optimization work, our new optimal checkpoint solution offers two improvements: (1) it is an online solution without requiring knowledge of the job length in advance, and (2) it shows that periodic patterns are optimal and determines the best pattern. We evaluate the proposed solution and compare it with the most up-to-date related approaches on an extreme-scale simulation testbed constructed based on a real HPC application execution. Simulation results show that our proposed solution outperforms other optimized solutions and can improve the performance significantly in some cases. Specifically, with the new solution the wall-clock time can be reduced by up to 25.3 percent over that of other state-of-the-art approaches. Finally, a brute-force comparison with all possible patterns shows that our solution is always within $1$ percent of the best pattern in the experiments. [ABSTRACT FROM PUBLISHER]

Replication plays an essential role for in-memory distributed transactional platforms, given that it represents the primary means to ensure data durability. Unfortunately, no single replication technique can ensure optimal performance across a wide range of workloads and system configurations. This paper tackles this problem by presenting MorphR , a framework that allows to automatically adapt the replication protocol of in-memory transactional platforms according to the current operational conditions. MorphR presents two key innovative aspects. On one hand, it allows to plug in, in a modular fashion, specialized algorithms to regulate the switching between arbitrary replication protocols. On the other hand, MorphR relies on state of the art machine learning techniques to autonomously determine the best replication in face of varying workloads. We integrated MorphR in an open-source in-memory NoSQL data grid, and evaluated it by means of an extensive experimental study. The results highlight that MorphR is accurate in identifying the best replication strategy in presence of complex realistic workloads, and does so with minimal overhead. [ABSTRACT FROM PUBLISHER]

In this paper,1 we investigate the throughput and delay in heterogeneous cognitive radio networks (HCRN), where the data source and the destination (S-D) is heterogeneously distributed following a rank based model and secondary users (SUs) provide relay service for primary users (PUs). We consider two scenarios: 1) PUs and SUs are both static; and 2) PUs are static and SUs are mobile. For scenario 1, we show that the primary network throughput is the same for different heterogeneous extents of S-D distribution owing to the flexible assistance of SUs, while the throughput of secondary networks is proven to be changing with the S-D heterogeneity exponent $\alpha$, which depicts the variation of different heterogeneous extents of S-D distribution. In addition, the delay of both primary and secondary networks are shown to be altering with $\alpha$. Further, we reveal that the number of SUs required to assist PUs can be dramatically reduced when considering the S-D heterogeneity, while achieving the same primary network throughput. For scenario 2, we utilize a modified uniform mobility (MUM) model to depict the motion of SUs and mainly focus on the analysis of throughput and delay for primary networks. It shows that the primary network throughput is also free of the heterogeneous extent of S-D distribution, while the delay changes with $\alpha$. Due to the mobility of SUs, a better delay-throughput tradeoff of primary networks is achieved compared with that in scenario 1. [ABSTRACT FROM AUTHOR]

Collecting histograms over RFID tags is an essential premise for effective aggregate queries and analysis in large-scale RFID-based applications. In this paper we consider an efficient collection of histograms from the massive number of RFID tags, without the need to read all tag data. In order to achieve time efficiency, we propose a novel, ensemble sampling-based method to simultaneously estimate the tag size for a number of categories. We first consider the problem of basic histogram collection, and propose an efficient algorithm based on the idea of ensemble sampling. We further consider the problems of advanced histogram collection, respectively, with an iceberg query and a top-$k$ query. Efficient algorithms are proposed to tackle the above problems such that the qualified/unqualified categories can be quickly identified. This ensemble sampling-based framework is very flexible and compatible to current tag-counting estimators, which can be efficiently leveraged to estimate the tag size for each category. Experiment results indicate that our ensemble sampling-based solutions can achieve a much better performance than the basic estimation/identification schemes. [ABSTRACT FROM AUTHOR]

Cooperative communication, which utilizes nearby terminals to relay the overhearing information to achieve the diversity gains, has a great potential to improve the transmitting efficiency in wireless networks. To deal with the complicated medium access interactions induced by relaying and leverage the benefits of such cooperation, an efficient Cooperative Medium Access Control (CMAC) protocol is needed. In this paper, we propose a novel cross-layer distributed energy-adaptive location-based CMAC protocol, namely DEL-CMAC, for Mobile Ad-hoc NETworks (MANETs). The design objective of DEL-CMAC is to improve the performance of the MANETs in terms of network lifetime and energy efficiency. A practical energy consumption model is utilized in this paper, which takes the energy consumption on both transceiver circuitry and transmit amplifier into account. A distributed utility-based best relay selection strategy is incorporated, which selects the best relay based on location information and residual energy. Furthermore, with the purpose of enhancing the spatial reuse, an innovative network allocation vector setting is provided to deal with the varying transmitting power of the source and relay terminals. We show that the proposed DEL-CMAC significantly prolongs the network lifetime under various circumstances even for high circuitry energy consumption cases by comprehensive simulation study. [ABSTRACT FROM AUTHOR]

Many wireless applications urgently demand an efficient neighbor discovery protocol to build up bridges connecting user themselves or to some service providers. However, due to intrinsic constraints of wireless devices, e.g., limited energy and error of clock synchronization, there is still absence of effective and efficient neighbor discovery protocols in the literature. In this work, we propose neighbor discovery protocols for the following two problems. First, we study Asynchronous Symmetry Neighbor Discovery problem, in which potential neighbor devices with asynchronous time clocks but the same duty cycle aim to find each other. Second, we propose an efficient protocol (utilizing Bouncing strategy) named BlindDatewith guaranteed worst-case performance 9\over 10 (1+\delta)^2x^2 where \delta is a small fraction of the length of a time slot unit and { 1\over x} is the duty cycle. Third, we extend this strategy to address Asynchronous Asymmetry Neighbor Discovery problem, in which both the time clock and the duty cycles of potential neighbors are considered to be heterogeneous. We conduct extensive experiments and simulations to examine the feasibility and efficiency of the proposed protocols, and results show that BlindDate greatly outperforms existing approaches in average-case. Compared with known protocols, BlindDate also achieves a better worst-case discovery latency bound (e.g., 10$ percent performance gain comparing with Searchlight [1]). [ABSTRACT FROM PUBLISHER]

Enabled by virtualization technologies, various multi-tier applications (such as web applications) are hosted by virtual machines (VMs) in cloud data centers. Live migration of multi-tier applications across geographically distributed data centers is important for load management, power saving, routine server maintenance and quality-of-service. Different from a single-VM migration, VMs in a multi-tier application are closely correlated, which results in a correlated VM migrations problem. Current live migration algorithms for single-VM cause significant application performance degradation because intermediate data exchange between different VMs suffers relatively low bandwidth and high latency across distributed data centers. In this paper, we design and implement a coordination system called VMbuddies for correlated VM migrations in the cloud. Particularly, we propose an adaptive network bandwidth allocation algorithm to minimize the migration cost in terms of migration completion time, network traffic and migration downtime. Experiments using a public benchmark show that VMbuddies significantly reduces the performance degradation and migration cost of multi-tier applications. [ABSTRACT FROM AUTHOR]

A data discovery and dissemination protocol for wireless sensor networks (WSNs) is responsible for updating configuration parameters of, and distributing management commands to, the sensor nodes. All existing data discovery and dissemination protocols suffer from two drawbacks. First, they are based on the centralized approach; only the base station can distribute data items. Such an approach is not suitable for emergent multi-owner-multi-user WSNs. Second, those protocols were not designed with security in mind and hence adversaries can easily launch attacks to harm the network. This paper proposes the first secure and distributed data discovery and dissemination protocol named DiDrip. It allows the network owners to authorize multiple network users with different privileges to simultaneously and directly disseminate data items to the sensor nodes. Moreover, as demonstrated by our theoretical analysis, it addresses a number of possible security vulnerabilities that we have identified. Extensive security analysis show DiDrip is provably secure. We also implement DiDrip in an experimental network of resource-limited sensor nodes to show its high efficiency in practice. [ABSTRACT FROM AUTHOR]

Cloud computing is an emerging data interactive paradigm to realize users’ data remotely stored in an online cloud server. Cloud services provide great conveniences for the users to enjoy the on-demand cloud applications without considering the local infrastructure limitations. During the data accessing, different users may be in a collaborative relationship, and thus data sharing becomes significant to achieve productive benefits. The existing security solutions mainly focus on the authentication to realize that a user’s privative data cannot be illegally accessed, but neglect a subtle privacy issue during a user challenging the cloud server to request other users for data sharing. The challenged access request itself may reveal the user’s privacy no matter whether or not it can obtain the data access permissions. In this paper, we propose a shared authority based privacy-preserving authentication protocol (SAPA) to address above privacy issue for cloud storage. In the SAPA, 1) shared access authority is achieved by anonymous access request matching mechanism with security and privacy considerations (e.g., authentication, data anonymity, user privacy, and forward security); 2) attribute based access control is adopted to realize that the user can only access its own data fields; 3) proxy re-encryption is applied to provide data sharing among the multiple users. Meanwhile, universal composability (UC) model is established to prove that the SAPA theoretically has the design correctness. It indicates that the proposed protocol is attractive for multi-user collaborative cloud applications. [ABSTRACT FROM PUBLISHER]

This paper aims to design an efficient data forwarding scheme based on local activity and social similarity (LASS) for mobile social networks (MSNs). Various definitions of social similarity have been proposed as the criterion for relay selection, which results in various forwarding schemes. The appropriateness and practicality of various definitions determine the performances of these forwarding schemes. A popular definition has recently been proven to be more efficient than other existing ones, i.e., the more common interests between two nodes, the larger social similarity between them. In this work, we show that schemes based on such definition ignore the fact that members within the same community, i.e., with the same interest, usually have different levels of local activity, which will result in a low efficiency of data delivery. To address this, in this paper, we design a new data forwarding scheme for MSNs based on community detection in dynamic weighted networks, called Local-Activity and Social-Similarity, taking into account the difference of members’ internal activity within each community, i.e., local activity. To the best of our knowledge, the proposed scheme is the first one that utilizes different levels of local activity within communities. Through extensive simulations, we demonstrate that LASS achieves better performance than state-of-the-art protocols. [ABSTRACT FROM PUBLISHER]

Time synchronization is one of the most fundamental services for wireless sensor networks. Prior studies have investigated the clock stability due to environmental dynamics. In this paper, we demonstrate by experiment that in spite of the surrounding environment, time synchronization is unavoidably impacted by in-network energy heterogeneity, which may incur up to 30-40 ppm clock uncertainty. We mathematically analyze the root cause of such clock uncertainty and propose a protocol called EATS. Sensor nodes with EATS can intelligently select the best synchronization parents that minimize the negative impact of the energy heterogeneity. The selection is robust to multiple impacting factors in the network and provides fine-grained synchronization accuracy. In addition, nodes can make use of local energy information and further calibrate the clocks. In light of this, the logic time maintained among different nodes is more consistent and the synchronization can be performed with a longer re-synchronization interval and less energy consumption. We implement EATS with TelosB motes and evaluate the effectiveness and efficiency of our design through extensive experiments and simulations. [ABSTRACT FROM PUBLISHER]

As a key approach to achieve energy efficiency in sensor networks, sensing coverage has been studied extensively in the literature. Researchers have designed many coverage protocols to provide various kinds of service guarantees on the network lifetime, coverage ratio and detection delay. While these protocols are effective, they are not flexible enough to meet multiple design goals simultaneously. In this paper, we propose a unified sensing coverage architecture for duty cycled wireless sensor networks, called uSense, which features three novel ideas: Asymmetric Architecture, Generic Switching and Global Scheduling. We propose asymmetric architecture based on the conceptual separation of switching from scheduling. Switching is efficiently supported in sensor nodes, while scheduling is done in a separated computational entity, where multiple scheduling algorithms are supported. As an instance, we propose a two-level global coverage algorithm, called uScan. At the first level, coverage is scheduled to activate different portions of an area. We propose an optimal scheduling algorithm to minimize area breach. At the second level, sets of nodes are selected to cover active portions. Importantly, we show the feasibility to obtain optimal set-cover results in linear time if the layout of areas satisfies certain conditions. Through extensive testbed and simulation evaluations, we demonstrate that uSense is a promising architecture to support flexible and efficient coverage in sensor networks. [ABSTRACT FROM AUTHOR]

Owing to its attractive features such as fast identification and relatively long interrogating range over the classical barcode systems, radio-frequency identification (RFID) technology possesses a promising prospect in many practical applications such as inventory control and supply chain management. However, unknown tags appear in RFID systems when the tagged objects are misplaced or unregistered tagged objects are moved in, which often causes huge economic losses. This paper addresses an important and challenging problem of unknown tag identification in large-scale RFID systems. The existing protocols leverage the Aloha-like schemes to distinguish the unknown tags from known tags at the slot level, which are of low time-efficiency, and thus can hardly satisfy the delay-sensitive applications. To fill in this gap, two filtering-based protocols (at the bit level) are proposed in this paper to address the problem of unknown tag identification efficiently. Theoretical analysis of the protocol parameters is performed to minimize the execution time of the proposed protocols. Extensive simulation experiments are conducted to evaluate the performance of the protocols. The results demonstrate that the proposed protocols significantly outperform the currently most promising protocols. [ABSTRACT FROM AUTHOR]

For chip multiprocessor systems (CMPs), the interference on shared resources such as on-chip caches typically leads to unbalanced progress among threads. Because of the inherent synchronization primitives, such as barriers and locks, cores running fast threads have to waste precious cycles to wait for cores with slow progress, which leads to performance and energy inefficiency. For the purpose of improving performance and reducing energy consumption, this paper proposes to adapt the cache coherence policy for threads according to their delay-tolerant levels. Specifically, this paper proposes Thread progrEss Aware Coherence Adaption (TEACA) which utilizes the thread progress information as hints for coherence adaption. TEACA dynamically utilize the memory system statistics to estimate the progress of threads. Based on the estimated thread progress information, TEACA categorizes threads into leader threads and laggard threads. The thread categorization decisions are then leveraged for efficient coherence adaption on CMP systems supporting hybrid coherence protocols. Experimental results show that, on a 64-core CMP system, TEACA outperforms directory protocol in application execution time and a recently proposed hybrid protocol in both application execution time and energy dissipation. [ABSTRACT FROM AUTHOR]

This paper initiates the study of two specific security threats on smart-card-based password authentication in distributed systems. Smart-card-based password authentication is one of the most commonly used security mechanisms to determine the identity of a remote client, who must hold a valid smart card and the corresponding password to carry out a successful authentication with the server. The authentication is usually integrated with a key establishment protocol and yields smart-card-based password-authenticated key agreement. Using two recently proposed protocols as case studies, we demonstrate two new types of adversaries with smart card: 1) adversaries with pre-computed data stored in the smart card, and 2) adversaries with different data (with respect to different time slots) stored in the smart card. These threats, though realistic in distributed systems, have never been studied in the literature. In addition to point out the vulnerabilities, we propose the countermeasures to thwart the security threats and secure the protocols. [ABSTRACT FROM AUTHOR]

Time synchronization is a fundamental requirement for the wide spectrum of applications with wireless sensor networks (WSNs). However, most existing time synchronization protocols are likely to deteriorate or even to be destroyed when the WSNs are attacked by malicious intruders. This paper is concerned with secure time synchronization for WSNs under message manipulation attacks. Specifically, the theoretical analysis and simulation results are first provided to demonstrate that the maximum consensus based time synchronization (MTS) protocol would be invalid under message manipulation attacks. Then, a novel secured maximum consensus based time synchronization (SMTS) protocol is proposed to detect and invalidate message manipulation attacks. Furthermore, we prove that SMTS is guaranteed to converge with simultaneous compensation of both clock skew and offset. Extensive numerical results show the effectiveness of our proposed protocol. [ABSTRACT FROM PUBLISHER]

As the most widely used parallel job scheduling strategy, EASY backfilling achieved great success, not only because it can balance fairness and performance, but also because it is universally applicable to most HPC systems. However, unfairness still exists in EASY. Our simulation shows that a blocked job can be delayed by later jobs for more than 90 hours on real workloads. Additionally, directly employing runtime prediction techniques in EASY would lead to a serious situation called reservation violation. In this paper, we aim at guaranteeing strict fairness (no job is delayed by any jobs of lower priority) while achieving attractive performance, and employing prediction without causing reservation violation in parallel job scheduling. We propose two novel strategies, namely, shadow load preemption (SLP) and venture backfilling (VB), which are integrated into EASY to construct preemptive venture EASY backfilling (PV-EASY). Experimental results on three real HPC workloads demonstrate that PV-EASY is more attractive than EASY in parallel job scheduling, from both academic and industry perspectives. [ABSTRACT FROM PUBLISHER]

We motivate and present two designs for the composition of the authentication protocol, Kerberos, and the key transport protocol, Multimedia Internet KEYing (MIKEY) for authenticated transport of cryptographic keys for secure group-communication in enterprise and public-safety settings. A technical challenge, and our main contribution, is the analysis of the security of the composition. Towards this, we design our compositions to have intuitive appeal and thereby less prone to security vulnerabilities. We then employ protocol composition logic (PCL), a state-of-the-art approach for analyzing our composition. For this, we first articulate two properties that are of interest. Both properties are on the group key that is transported; we call them Group Key Confidentiality and Acquisition. Group Key Confidentiality is the property that if a principal possesses the key, then it is an authorized member of the group. Group Key Acquisition is the property that if a principal is a member of the group, then it is able to acquire the group key. In the course of our rigorous analysis, we discovered a flaw in our first design, which we point out, and which lead us to our second design. We have implemented both designs starting with the publicly available reference implementation of Kerberos, and an open-source implementation of MIKEY. Our implementations are available as open-source. We discuss our experience from the implementation, and present empirical results. [ABSTRACT FROM PUBLISHER]

The accurate and efficient operation of many applications and protocols in wireless sensor networks require synchronized notion of time. To achieve network-wide time synchronization, a common strategy is to flood current time information of a reference node into the network, which is utilized by the de facto time-synchronization protocol Flooding Time-Synchronization Protocol (FTSP). In FTSP, the propagation speed of the flood is slow because each node waits for a given period of time to propagate its time information about the reference node. It has been shown that slow-flooding decreases the synchronization accuracy and scalability of FTSP drastically. Alternatively, rapid-flooding approach is proposed in the literature, which allows nodes to propagate time information as quickly as possible. However, rapid flooding is difficult and has several drawbacks in wireless sensor networks. In this paper, our aim is to reduce the undesired effect of slow-flooding on the synchronization accuracy without changing the propagation speed of the flood. Within this context, we realize that the smaller the difference between the speeds of the clocks, the smaller the undesired effect of waiting times on the synchronization accuracy. In the light of this realization, our main contribution is to show that the synchronization accuracy and scalability of slow-flooding can drastically be improved by employing a clock speed agreement algorithm among the sensor nodes. We present an evaluation of this strategy on a testbed setup including 20 MICAz sensor nodes. Our theoretical findings and experimental results show that employing a clock speed agreement algorithm among the sensor nodes drastically improves the synchronization accuracy and scalability of slow-flooding. [ABSTRACT FROM AUTHOR]

Gradient-based routing using Bloom filters is an effective mechanism to enable data-centric queries in multihop networks. A node compressively describes its data items as a Bloom filter, which is then diffused away to the other nodes with information decay. The Bloom filters form an information potential that eventually navigates queries to the source node by ascending the potential field. The existing designs of Bloom filters, however, have critical limitations with respect to the feasibility of gradient-based routing. The compressed routing entries appear to be noisy. Noise in unrelated routing entries is very likely to equal to even outweigh information in right routing entries, thus blinding a query to its desired destination. This work addresses the root cause of the mismatch between the ideal and the practical performance of gradient-based routing using Bloom filters. We first investigate the impact of decaying model on the effectiveness of routing entries, and then evaluate the negative impact of noise on routing decisions. Based on such analytical results, we derive the necessary and sufficient condition of feasible gradient-based routing using Bloom filters. Accordingly, we propose a receiver-oriented design of Bloom filters, called Wader, which satisfies the necessary and sufficient condition. The evaluation results demonstrate that Wader guarantees the correctness and efficiency of gradient-based routing with high probability. [ABSTRACT FROM AUTHOR]

Piece-related algorithms, including piece revelation, selection, and queuing, play a crucial role in the BitTorrent (BT) protocol, because the BT system can be viewed as a market where peers trade their pieces with one another. During the piece exchanging, a peer selects some pieces revealed by neighbors, and queues them up for downloading. In this paper, we provide a deep understanding of these algorithms, and also propose some improvements to them. Previous study has shown that the piece revelation strategy is vulnerable to under-reporting. We provide a game-theoretic analysis for this selfish gaming, and propose a distributed credit method to prevent it. Existing piece selection strategies, though long believed to be good enough, may fail to balance piece supply and demand. We propose a unified strategy to shorten the download time of peers by applying utility theory. The design of the piece queuing algorithm has a conflict with that of piece selection strategy, because it is not possible to assume that the queued requests for a selected piece can always be available on multiple neighbors. We give a possible fix to address the conflict by allowing peers to dynamically manage their unfulfilled requests. To evaluate the performance of the proposed algorithms, we run several experiments in a live swarm. Our primary results show that they can achieve fast individual and system-wide download time. [ABSTRACT FROM PUBLISHER]

Topic-based publish/subscribe is at the core of many distributed systems, ranging from application integration middleware to news dissemination. Therefore, much research was dedicated to publish/subscribe architectures and protocols, and in particular to the design of overlay networks for decentralized topic-based routing and efficient message dissemination. Nonetheless, existing systems fail to take full advantage of shared interests when disseminating information, hence suffering from high maintenance and traffic costs, or construct overlays that cope poorly with the scale and dynamism of large networks. In this paper, we present StaN, a decentralized protocol that optimizes the properties of gossip-based overlay networks for topic-based publish/subscribe by sharing a large number of physical connections without disrupting its logical properties. StaN relies only on local knowledge and operates by leveraging common interests among participants to improve global resource usage and promote topic and event scalability. The experimental evaluation under two real workloads, both via a real deployment and through simulation, shows that StaN provides an attractive infrastructure for scalable topic-based publish/subscribe. [ABSTRACT FROM PUBLISHER]

Voice over Internet Protocol (VoIP) applications based on peer-to-peer (P2P) communications have been experiencing considerable growth in terms of number of users. To overcome filtering policies or protect the privacy of their users, most of these applications implement mechanisms such as protocol obfuscation or payload encryption that avoid the inspection of their traffic, making it difficult to identify its nature. The incapacity to determine the application that is responsible for a certain flow raises challenges for the effective management of the network. In this paper, a new method for the identification of VoIP sessions is presented. The proposed mechanism classifies the flows, in real-time, based on the speech codec used in the session. To make the classification lightweight, the behavioral signatures for each analyzed codec were created using only the lengths of the packets. Unlike most previous approaches, the classifier does not use the lengths of the packets individually. Instead, it explores their level of heterogeneity in real time, using entropy to emphasize such feature. The results of the performance evaluation show that the proposed method is able to identify VoIP sessions accurately and simultaneously recognize the used speech codec. [ABSTRACT FROM AUTHOR]

Small talk is an important social lubricant that helps people, especially strangers, initiate conversations and make friends with each other in physical proximity. However, due to difficulties in quickly identifying significant topics of common interest, real-world small talk tends to be superficial. The mass popularity of mobile phones can help improve the effectiveness of small talk. In this paper, we present E-SmallTalker, a distributed mobile communications system that facilitates social networking in physical proximity. It automatically discovers and suggests topics such as common interests for more significant conversations. We build on Bluetooth Service Discovery Protocol (SDP) to exchange potential topics by customizing service attributes to publish non-service-related information without establishing a connection. We propose a novel iterative Bloom filter protocol that encodes topics to fit in SDP attributes and achieves a low false-positive rate. We have implemented the system in Java ME for ease of deployment. Our experiments on real-world phones show that it is efficient enough at the system level to facilitate social interactions among strangers in physical proximity. To the best of our knowledge, E-SmallTalker is the first distributed mobile system to achieve the same purpose. [ABSTRACT FROM PUBLISHER]

Along with radio frequency identification (RFID) becoming ubiquitous, security issues have attracted extensive attentions. Most studies focus on the single-reader and single-tag case to provide security protection, which leads to certain limitations for diverse applications. This paper proposes a grouping-proofs-based authentication protocol (GUPA) to address the security issue for multiple readers and tags simultaneous identification in distributed RFID systems. In GUPA, distributed authentication mode with independent subgrouping proofs is adopted to enhance hierarchical protection; an asymmetric denial scheme is applied to grant fault-tolerance capabilities against an illegal reader or tag; and a sequence-based odd-even alternation group subscript is presented to define a function for secret updating. Meanwhile, GUPA is analyzed to be robust enough to resist major attacks such as replay, forgery, tracking, and denial of proof. Furthermore, performance analysis shows that compared with the known grouping-proof or yoking-proof-based protocols, GUPA has lower communication overhead and computation load. It indicates that GUPA realizing both secure and simultaneous identification is efficient for resource-constrained distributed RFID systems. [ABSTRACT FROM AUTHOR]

Despite the advances in high performance interdomain communications for virtual machines (VM), data intensive applications developed for VMs based on the traditional remote procedure call (RPC) mechanism still suffer from performance degradation due to the inherent inefficiency of data serialization/deserilization operations. This paper presents VMRPC, a lightweight RPC framework specifically designed for VMs that leverages the heap and stack sharing mechanism to circumvent unnecessary data copy and serialization/deserilization. Our evaluation shows that the performance of VMRPC is an order of magnitude better than traditional RPC systems and existing alternative interdomain communication optimization systems. The evaluation on a VMRPC-enhanced networked file system across a varied range of benchmarks further reveals the competitiveness of VMRPC in IO-intensive applications. [ABSTRACT FROM AUTHOR]

The growing importance of operations such as identification, location sensing, and object tracking has led to increasing interests in contactless Radio Frequency Identification (RFID) systems. Enjoying the low cost of RFID tags, modern RFID systems tend to be deployed for large-scale mobile objects. Both the theoretical and experimental results suggest that when tags are in large numbers, most existing collision arbitration protocols do not satisfy the scalability and time-efficiency requirements of many applications. To address this problem, we propose Adaptively Splitting-based Arbitration Protocol (ASAP), a scheme that provides efficient RFID identification for both small and large deployment of RFID tags, in terms of time and energy cost. Theoretical analysis and simulation evaluation show that the performance of ASAP is better than most existing collision-arbitration solutions and the time efficiency is close to the theoretically optimal values. [ABSTRACT FROM AUTHOR]

Equal cost multiple path (ECMP) forwarding is the most prevalent multipath routing used in data center (DC) networks today. However, it fails to exploit increased path diversity that can be provided by traffic engineering techniques through the assignment of nonuniform link weights to optimize network resource usage. To this extent, constructing a routing algorithm that provides path diversity over nonuniform link weights (i.e., unequal cost links), simplicity in path discovery and optimality in minimizing maximum link utilization (MLU) is nontrivial. In this paper, we have implemented and evaluated the Penalizing Exponential Flow-spliTing (PEFT) algorithm in a cloud DC environment based on two dominant topologies, canonical and fat tree. In addition, we have proposed a new cloud DC topology which, with only a marginal modification of the current canonical tree DC architecture, can further reduce MLU and increase overall network capacity utilization through PEFT routing. [ABSTRACT FROM AUTHOR]

We study the capacity scaling laws for the cognitive network that consists of the primary hybrid network (PhN) and secondary ad hoc network (SaN). PhN is further comprised of an ad hoc network and a base station-based (BS-based) network. SaN and PhN are overlapping in the same deployment region, operate on the same spectrum, but are independent with each other in terms of communication requirements. The primary users (PUs), i.e., the ad hoc nodes in PhN, have the priority to access the spectrum. The secondary users (SUs), i.e., the ad hoc nodes in SaN, are equipped with cognitive radios, and have the functionalities to sense the idle spectrum and obtain the necessary information of primary nodes in PhN. We assume that PhN adopts one out of three classical types of strategies, i.e., pure ad hoc strategy, BS-based strategy, and hybrid strategy. We aim to directly derive multicast capacity for SaN to unify the unicast and broadcast capacities under two basic principles: 1) The throughput for PhN cannot be undermined in order sense due to the presence of SaN. 2) The protocol adopted by PhN does not alter in the interest of SaN, anyway. Depending on which type of strategy is adopted in PhN, we design the optimal-throughput strategy for SaN. We show that there exists a threshold of the density of SUs according to the density of PUs beyond which it can be proven that: 1) when PhN adopts the pure ad hoc strategy or hybrid strategy, SaN can achieve the multicast capacity of the same order as it is stand-alone; 2) when PhN adopts the BS-based strategy, SaN can asymptotically achieve the multicast capacity of the same order as if PhN were absent, if some specific conditions in terms of relations among the numbers of SUs, PUs, the destinations of each multicast session in SaN, and BSs in PhN hold. [ABSTRACT FROM AUTHOR]

The resources especially energy in wireless sensor networks (WSNs) are quite limited. Since sensor nodes are usually much dense, data sampled by sensor nodes have much redundancy, data aggregation becomes an effective method to eliminate redundancy, minimize the number of transmission, and then to save energy. Many applications can be deployed in WSNs and various sensors are embedded in nodes, the packets generated by heterogenous sensors or different applications have different attributes. The packets from different applications cannot be aggregated. Otherwise, most data aggregation schemes employ static routing protocols, which cannot dynamically or intentionally forward packets according to network state or packet types. The spatial isolation caused by static routing protocol is unfavorable to data aggregation. To make data aggregation more efficient, in this paper, we introduce the concept of packet attribute, defined as the identifier of the data sampled by different kinds of sensors or applications, and then propose an attribute-aware data aggregation (ADA) scheme consisting of a packet-driven timing algorithm and a special dynamic routing protocol. Inspired by the concept of potential in physics and pheromone in ant colony, a potential-based dynamic routing is elaborated to support an ADA strategy. The performance evaluation results in series of scenarios verify that the ADA scheme can make the packets with the same attribute spatially convergent as much as possible and therefore improve the efficiency of data aggregation. Furthermore, the ADA scheme also offers other properties, such as scalable with respect to network size and adaptable for tracking mobile events. [ABSTRACT FROM AUTHOR]

The reader-to-reader collision problem represents a research topic of great recent interest for the radio frequency identification (RFID) technology. Among the state-of-the-art anticollision protocols, the ones that provide high throughput often have special requirements, such as extra hardware. This study investigates new high throughput solutions for static RFID networks without additional requirements. In this paper, two contributions are presented: a new configuration, called Killer, and a new protocol, called distributed color noncooperative selection (DCNS). The proposed configuration generates selfish behavior, thereby increasing channel utilization and throughput. DCNS fully exploits the Killer configuration and provides new features, such as dynamic priority management, which modifies the performance of the RFID readers when it is requested. Simulations have been conducted in order to analyze the effects of the innovations proposed. The proposed approach is especially suitable for low-cost applications with a priority not uniformly distributed among readers. The experimental analysis has shown that DCNS provides a greater throughput than the state-of-the-art protocols, even those with additional requirements (e.g., 16 percent better than NFRA). [ABSTRACT FROM AUTHOR]

Wireless sensor networks (WSNs) can be successfully applied in a wide range of applications. Efficient data dissemination is a fundamental service which enables many useful high-level functions such as parameter reconfiguration, network reprogramming, etc. Many current data dissemination protocols employ network coding techniques to deal with packet losses. The coding overhead, however, becomes a bottleneck in terms of dissemination delay. We exploit the concurrency potential of sensor nodes and propose MT-Deluge, a multithreaded design of a coding-based data dissemination protocol. By separating the coding and radio operations into two threads and carefully scheduling their executions, MT-Deluge shortens the dissemination delay effectively. An incremental decoding algorithm is employed to further improve MT-Deluge's performance. Experiments with 24 TelosB motes on four representative topologies show that MT-Deluge shortens the dissemination delay by 25.5-48.6 percent compared to a typical data dissemination protocol while keeping the merits of loss resilience. [ABSTRACT FROM PUBLISHER]

This paper presents a secure protocol for spontaneous wireless ad hoc networks which uses an hybrid symmetric/asymmetric scheme and the trust between users in order to exchange the initial data and to exchange the secret keys that will be used to encrypt the data. Trust is based on the first visual contact between users. Our proposal is a complete self-configured secure protocol that is able to create the network and share secure services without any infrastructure. The network allows sharing resources and offering new services among users in a secure environment. The protocol includes all functions needed to operate without any external support. We have designed and developed it in devices with limited resources. Network creation stages are detailed and the communication, protocol messages, and network management are explained. Our proposal has been implemented in order to test the protocol procedure and performance. Finally, we compare the protocol with other spontaneous ad hoc network protocols in order to highlight its features and we provide a security analysis of the system. [ABSTRACT FROM PUBLISHER]

We present the Secure SOurce-BAsed Loose Synchronization (SOBAS) protocol to securely synchronize the events in the network, without the transmission of explicit synchronization control messages. In SOBAS, nodes use their local time values as a one-time dynamic key to encrypt each message. In this way, SOBAS provides an effective dynamic en-route filtering mechanism, where the malicious data is filtered from the network. With SOBAS, we are able to achieve our main goal of synchronizing events at the sink as quickly, as accurately, and as surreptitiously as possible. With loose synchronization, SOBAS reduces the number of control messages needed for a WSN to operate providing the key benefits of reduced energy consumption as well as reducing the opportunity for malicious nodes to eavesdrop, intercept, or be made aware of the presence of the network. Albeit a loose synchronization per se, SOBAS is also able to provide $(7.24 \mu)$s clock precision given today's sensor technology, which is much better than other comparable schemes (schemes that do not employ GPS devices). Also, we show that by recognizing the need for and employing loose time synchronization, necessary synchronization can be provided to the WSN application using half of the energy needed for traditional schemes. Both analytical and simulation results are presented to verify the feasibility of SOBAS as well as the energy consumption of the scheme under normal operation and attack from malicious nodes. [ABSTRACT FROM PUBLISHER]

It is necessary to authenticate users who attempt to access resources in Wireless Local Area Networks (WLANs). Extensible Authentication Protocol (EAP) is an authentication framework widely used in WLANs. Authentication mechanisms built on EAP are called EAP methods. The requirements for EAP methods in WLAN authentication have been defined in RFC 4017. To achieve user efficiency and robust security, lightweight computation and forward secrecy, excluded in RFC 4017, are desired in WLAN authentication. However, all EAP methods and authentication protocols designed for WLANs so far do not satisfy all of the above properties. This manuscript will present a complete EAP method that utilizes stored secrets and passwords to verify users so that it can 1) fully meet the requirements of RFC 4017, 2) provide for lightweight computation, and 3) allow for forward secrecy. In addition, we also demonstrate the security of our proposed EAP method with formal proofs. [ABSTRACT FROM PUBLISHER]

Distributed processing through ad hoc and sensor networks is having a major impact on scale and applications of computing. The creation of new cyber-physical services based on wireless sensor devices relies heavily on how well communication protocols can be adapted and optimized to meet quality constraints under limited energy resources. The IEEE 802.15.4 medium access control protocol for wireless sensor networks can support energy efficient, reliable, and timely packet transmission by a parallel and distributed tuning of the medium access control parameters. Such a tuning is difficult, because simple and accurate models of the influence of these parameters on the probability of successful packet transmission, packet delay, and energy consumption are not available. Moreover, it is not clear how to adapt the parameters to the changes of the network and traffic regimes by algorithms that can run on resource-constrained devices. In this paper, a Markov chain is proposed to model these relations by simple expressions without giving up the accuracy. In contrast to previous work, the presence of limited number of retransmissions, acknowledgments, unsaturated traffic, packet size, and packet copying delay due to hardware limitations is accounted for. The model is then used to derive a distributed adaptive algorithm for minimizing the power consumption while guaranteeing a given successful packet reception probability and delay constraints in the packet transmission. The algorithm does not require any modification of the IEEE 802.15.4 medium access control and can be easily implemented on network devices. The algorithm has been experimentally implemented and evaluated on a testbed with off-the-shelf wireless sensor devices. Experimental results show that the analysis is accurate, that the proposed algorithm satisfies reliability and delay constraints, and that the approach reduces the energy consumption of the network under both stationary and transient conditions. Specifically, even if the number of devices and traffic configuration change sharply, the proposed parallel and distributed algorithm allows the system to operate close to its optimal state by estimating the busy channel and channel access probabilities. Furthermore, results indicate that the protocol reacts promptly to errors in the estimation of the number of devices and in the traffic load that can appear due to device mobility. It is also shown that the effect of imperfect channel and carrier sensing on system performance heavily depends on the traffic load and limited range of the protocol parameters. [ABSTRACT FROM AUTHOR]

Different from traditional P2P systems, individuals nodes of a Federated Service Providing (FSP) system play a more active role by offering a variety of domain-specific services. The service provision control (SPC) problem is an important problem of the FSP system and will be tackled in this paper within a stochastic optimization framework through several steps. The first step focuses on using stochastic differential equations (SDEs) to model and analyze the dynamic evolution of the service demand. Driven by the SDE model, expected future performance of a FSP system is analytically evaluated in the second step. Step three utilizes the differential evolution (DE) algorithm to identify near-optimal service-providing policies for each node. The service subscription protocol is further proposed in step four to help every node adjust its local policy in accordance with the services provided by other nodes. The four steps together implement a complete solution of the SPC problem and will be called the SDE-based service-provision control (SSPC) mechanism in this paper. Experimental evaluation of the mechanism has been reported in the paper. The results show that our approach is effective in tackling the SPC problem and may be therefore suitable for many practical applications. [ABSTRACT FROM AUTHOR]

Multidestination communications are a highly necessary capability for many coherence protocols in order to minimize on-chip hit latency. Although CMPs share this necessity, up to now few suitable proposals have been developed. The combination of resource scarcity and the common idea that multicast support requires a substantial amount of extra resources is responsible for this situation. In this work, we propose a new approach suitable for on-chip networks capable of managing multidestination traffic via hardware in an efficient way with negligible complexity. We introduce a novel multicast routing mechanism, able to circumvent many of the limitations of conventional multicast schemes. Adaptive-tree multicasting is able to maintain correctness for multiflit multicast messages without routing restrictions, while also coupling correctness and performance in a natural way. Replication restrictions not only guarantee the presence of enough resources to avoid deadlock, but also dynamically adapt tree shape to network conditions, routing multicast messages through noncongested paths. The performance results, using a state-of-the-art full system simulation framework, show that it improves the average full system performance of a CMP by 20 percent and network ED2P by 15 percent, when compared to a state-of-the-art router with conventional multicast support and similar implementation cost. [ABSTRACT FROM AUTHOR]

A fundamental challenge of supporting mutable data replication in a Peer-to-Peer (P2P) system is to efficiently maintain consistency. This paper presents a framework for Balanced Consistency Maintenance (BCoM) in structured P2P systems with heterogeneous node capabilities and various workload patterns. Replica nodes of each object are organized into a tree structure for disseminating updates, and a sliding window update protocol is developed for consistency maintenance. We present an analytical model to optimize the window size according to the dynamic network conditions, workload patterns and resource limits. In this way, BCoM balances the consistency strictness, object availability for updates, and update propagation performance for various application requirements. On top of the dissemination tree, two enhancements are proposed: 1) a fast recovery scheme to strengthen the robustness against node and link failures, and 2) a node migration policy to remove and prevent bottlenecks allowing more efficient update delivery. Simulations are conducted using P2PSim to evaluate BCoM in comparison to SCOPE [1]. The experimental results demonstrate that BCoM outperforms SCOPE with lower discard rates. BCoM achieves a discard rate as low as 5 percent in most cases while SCOPE has almost 100 percent discard rate. [ABSTRACT FROM AUTHOR]

Radio-Frequency Identification (RFID) technology brings many innovative applications. Of great importance to RFID applications in production economics is misplaced-tag pinpointing (MTP), because misplacement errors fail optimal inventory placement and thus significantly decrease profit. The existing MTP solution [1], originally proposed from a data-processing perspective, collects and processes a large amount of data. It suffers from time inefficiency (and energy-inefficiency as well if active tags are in use). The problem of finding efficient solutions for the MTP problem from the communication protocol design perspective has never been investigated before. In this paper, we propose a series of protocols toward efficient MTP solutions in large RFID systems. The proposed protocols detect misplaced tags using reader positions instead of tag positions to guarantee the efficiency and scalability as system scale grows, because RFID readers are much fewer than tags. Considering applications that employ active tags, we further propose a solution requiring responses from only a subset of tags in favor of energy saving. We also design a distributed protocol that enables each reader to independently detect misplaced tags. We then investigate how to apply the proposed protocols in scenarios with tag mobility. To evaluate the proposed protocols, we analyze their optimal performances to demonstrate their efficiency potential and also conduct extensive simulation experiments. The results show that the proposed protocols can significantly increase the time efficiency and the energy efficiency by over 70 percent on average when compared with the best existing work. [ABSTRACT FROM AUTHOR]

Decentralized attribute-based encryption (ABE) is a variant of a multiauthority ABE scheme where each authority can issue secret keys to the user independently without any cooperation and a central authority. This is in contrast to the previous constructions, where multiple authorities must be online and setup the system interactively, which is impractical. Hence, it is clear that a decentralized ABE scheme eliminates the heavy communication cost and the need for collaborative computation in the setup stage. Furthermore, every authority can join or leave the system freely without the necessity of reinitializing the system. In contemporary multiauthority ABE schemes, a user's secret keys from different authorities must be tied to his global identifier (GID) to resist the collusion attack. However, this will compromise the user's privacy. Multiple authorities can collaborate to trace the user by his GID, collect his attributes, then impersonate him. Therefore, constructing a decentralized ABE scheme with privacy-preserving remains a challenging research problem. In this paper, we propose a privacy-preserving decentralized key-policy ABE scheme where each authority can issue secret keys to a user independently without knowing anything about his GID. Therefore, even if multiple authorities are corrupted, they cannot collect the user's attributes by tracing his GID. Notably, our scheme only requires standard complexity assumptions (e.g., decisional bilinear Diffie-Hellman) and does not require any cooperation between the multiple authorities, in contrast to the previous comparable scheme that requires nonstandard complexity assumptions (e.g., q-decisional Diffie-Hellman inversion) and interactions among multiple authorities. To the best of our knowledge, it is the first decentralized ABE scheme with privacy-preserving based on standard complexity assumptions. [ABSTRACT FROM AUTHOR]

The dynamic composition of networked appliances, or virtual devices, enables users to generate complex, strong, and specific systems. Current MANET-based composition schemes use service discovery mechanisms that depend on periodic service advertising by controlled broadcast, resulting in the unnecessary depletion of node resources. The assumption that, once generated, a virtual device is to remain static is false; the device should gracefully degrade and upgrade along with the conditions in the user's environment, particularly the network's current performance requirements. Presently, schemes for infrastructure-less virtual device composition and management do not consider this adaptation. We present a distributed constraint satisfaction problem (distCSP) for virtual device composition in MANETs that addresses these issues together with simulations that show its effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

Gossip, or epidemic, protocols have emerged as a highly scalable and resilient approach to implement several application level services such as reliable multicast, data aggregation, publish-subscribe, among others. All these protocols organize nodes in an unstructured random overlay network. In many cases, it is interesting to bias the random overlay in order to optimize some efficiency criteria, for instance, to reduce the stretch of the overlay routing. In this paper, we propose X-BOT, a new protocol that allows to bias the topology of an unstructured gossip overlay network. X-BOT is completely decentralized and, unlike previous approaches, preserves several key properties of the original (nonbiased) overlay (most notably, the node degree and consequently, the overlay connectivity). Experimental results show that X-BOT can generate more efficient overlays than previous approaches independently of the underlying physical network topology. [ABSTRACT FROM AUTHOR]

Wireless reprogramming of sensor nodes is an essential requirement for long-lived networks because software functionality needs to be changed over time. The amount of information that needs to be wirelessly transmitted during reprogramming should be minimized to reduce reprogramming time and energy. In this paper, we present a multihop incremental reprogramming system called Hermes that transfers over the network the delta between the old and new software and lets the sensor nodes rebuild the new software using the received delta and the old software. It reduces the delta by using techniques to mitigate the effects of function and global variable shifts caused by the software modifications. Then it compares the binary images at the byte level with a method to create a small delta that needs to be sent over the wireless network to all the nodes. For the wide range of software change scenarios that we experimented with, we find that Hermes transfers up to 201 times less information than Deluge, the standard reprogramming system for TinyOS, and 64 times less than an existing incremental reprogramming system by Jeong and Culler. [ABSTRACT FROM AUTHOR]