We present a WiFi signal-based, volatile key extraction system called RoomKey. We derive a room’s key by creating a deterministic key from the ever-changing WiFi environment and investigating the extraction capabilities of a designated area. RoomKey uses wireless beacon frames as a component, which we combine with a strong random key to generate and reconstruct the same volatile key in the room. We provide an exemplary use case using RoomKeyas an authentication factor using the location-specific WiFi environment as an authentication claim. We identified and solved two problems in using location as an authentication factor: location being sensitive to privacy and the location of a user constantly changing. We mitigate privacy concerns by recognizing a particular location without the need to localize its precise geographical coordinates. To overcome the problem of location change, we restrict locations to work environments for laptop usage and allow a per-location-predetermined, designated area (e.g., a room). With the concept RoomKey, we demonstrate the potential of including environmental WiFi measurements for volatile key extraction and show the possibility of creating location-aware and privacy-preserving authentication systems for continuous authentication and adaptive security measures.

Relying on Wi-Fi signals broadcasted by smartphones became the de-facto standard in the domain of pedestrian crowd monitoring. This method got the edge over other traditional means owing to the fact that insights are built upon data which uniquely identifies individuals and, thus, allows highly accurate crowd profiling over time. On the other hand, handling such uniquely identifying data in such a way that it does not expose the sensed individuals to potential privacy infringements proves to be a difficult task. Although several protection techniques were proposed, they yield data which, combined with other external knowledge, can still be used for tracing back to specific individuals. To address this issue, we propose a construction which protects the short-term storage and processing of privacy-sensitive Wi-Fi detections under strong cryptographic guarantees and makes available in the clear, as end results, only statistical counts of crowds. To produce these statistical counts, we make use of homomorphically encrypted Bloom filters as facilitators for oblivious set membership testing under encryption. We implement the system and perform evaluation on both simulated data and a real-world crowd-monitoring dataset, demonstrating that it is feasible to achieve highly accurate statistical counts in a privacy-friendly way.

Pedestrian dynamics are nowadays commonly analyzed by leveraging Wi-Fi signals sent by devices that people carry with them and captured by an infrastructure of Wi-Fi scanners. Emitting such signals is not a feature for devices of only passersby, but also for printers, smart TVs, and other devices that exhibit a stationary behavior over time, which eventually end up affecting pedestrian crowd measurements. In this paper we propose a system that accurately counts nonstationary devices sensed by scanners, separately from stationary devices, using no information other than the Wi-Fi signals captured by each scanner in isolation. As counting involves dealing with privacy-sensitive detections of people's devices, the system discards any data in the clear immediately after sensing, later working on encrypted data that it cannot decrypt in the process. The only information made available in the clear is the intended output, i.e. statistical counts of Wi-Fi devices. Our approach relies on an object, which we call comb, that maintains, under encryption, a representation of the frequency of occurrence of devices over time. Applying this comb on the detections made by a scanner enables the calculation of the separate counts. We implement the system and feed it with data from a large open-air festival, showing that accurate anonymized counting of nonstationary Wi-Fi devices is possible when dealing with real-world detections.

Security monitoring systems detect potentially malicious activities in IT infrastructures, by either looking for known signatures or for anomalous behaviors. Security operators investigate these events to determine whether they pose a threat to their organization. In many cases, a single event may be insufficient to determine whether certain activity is indeed malicious. Therefore, a security operator frequently needs to correlate multiple events to identify if they pose a real threat. Unfortunately, the vast number of events that need to be correlated often overload security operators, forcing them to ignore some events and, thereby, potentially miss attacks. This work studies how to automatically correlate security events and, thus, automate parts of the security operator workload. We design and evaluate DEEPCASE, a system that leverages the context around events to determine which events require further inspection. This approach reduces the number of events that need to be inspected. In addition, the context provides valuable insights into why certain events are classified as malicious. We show that our approach automatically filters 86.72% of the events and reduces the manual workload of security operators by 90.53%, while underestimating the risk of potential threats in less than 0.001% of cases.

Measuring pedestrian dynamics using the signals sent from smartphones has become popular. Notably, Wi-Fi-based systems are currently widely deployed. However, many such systems have also become subject to serious debate due to privacy infringement. For some time, secure hashing of a smartphone’s unique MAC address was considered to be sufficient, yet this method has been overruled by Europe’s General Data Protection Regulation which states that an individual should not be identifiable from any dataset without explicit prior consent.

Studying the movements of crowds is important for understanding and predicting the behavior of large groups of people. When analyzing crowds, one is often interested in the long-term macro-level motions of the crowd as a whole, as opposed to the micro-level short-term movements of individuals. A high-level representation of these motions is thus desirable. In this work, we present a scalable method for detection of crowd motion patterns, i.e., spatial areas describing the dominant motions within crowds. For measuring crowd movements, we propose a fast, scalable, and low-cost method based on proximity graphs. For analyzing crowd movements, we utilize a three-stage pipeline: (1) represents the behavior of each person at each moment in time as a low-dimensional data point, (2) cluster these data points based on spatial relations, and (3) concatenate these clusters based on temporal relations. Experiments on synthetic datasets reveals our method can handle various scenarios including curved lanes and diverging flows. Evaluation on real-world datasets shows our method is able to extract useful motion patterns which could not be properly detected by existing methods. Overall, we see our work as an initial step towards rich pattern recognition.

Privacy-preserved tracking of WiFi-enabled devices such as smartphones offers a highly scalable solution for large-scale crowd movement studies. However, extracting knowledge out of pedestrian-tracking data acquired this way is not simple. This is, generally, due to the inherent inaccuracy of the measurement technique. Segmenting an individual's trajectory data into periods of stops and moves is a fundamental step in analyzing crowds' movement. Such distinctions allow us to answer advanced questions regarding visited locations or even social behavior. Algorithms previously designed for distinguishing movements from stay periods, assume datasets are gathered using GPS, which offers precise positioning. WiFi tracking, however, does not offer such precision. The location of devices can at best be reduced to a large area around the WiFi scanner. In this paper, we study a set of established algorithms for detecting periods of stops and moves from GPS-based datasets and their applicability to WiFi-based data. Consequently, we propose possible improvements to such algorithms considering the inherent characteristics of WiFi tracking data.

Crowd Monitoring is receiving much attention. An increasingly popular technique is to scan for mobile devices, notably smartphones. We take a look at scanning for such devices by recording WiFi packets. Although research on capturing crowd patterns using WiFi detections has been done, there are not many published results when it comes to tracking movements. This is not surprising when realizing that the data provided by WiFi scanners is susceptible to many seemingly erroneous and missed detections, caused by the use of randomized network addresses, overlap between scanners, high variance in WiFi detection ranges, among other sources. In this paper, we investigate various techniques for cleaning up sets of raw detections to sets that can subsequently be used for crowd analytics. To this end, we introduce two different quality metrics to measure the effects of applying the various techniques. We test our approach using a data set collected from 27 WiFi scanners spread across the downtown area of a Dutch city where at that time a 3-day multi-stage festival took place attended by some 130,000 people.

Face-to-face proximity has been successfully leveraged to study the relationships between individuals in various contexts, from a working place, to a conference, a museum, a fair, and a date. We spend time facing the individuals with whom we chat, discuss, work, and play. However, face-to-face proximity is not the realm of solely person-to-person relationships, but it can be used as a proxy to study person-to-object relationships as well. We face the objects with which we interact on a daily basis, like a television, the kitchen appliances, a book, including more complex objects like a stage where a concert is taking place. In this paper, we focus on the relationship between the visitors of an art exhibition and its exhibits. We design, implement, and deploy a sensing infrastructure based on inexpensive mobile proximity sensors and a filtering pipeline that we use to measure face-to-face proximity between individuals and exhibits. Our pipeline produces an improvement in measurement accuracy of up to 64% relative to raw data. We use this data to mine the behavior of the visitors and show that group behavior can be recognized by means of data clustering and visualization.

Energy is the scarcest resource in ad hoc wireless networks, particularly in wireless sensor networks requiring a long lifetime. Intermittently switching the radio on and off is widely adopted as the most effective way to keep energy consumption low. This, however, prevents the very goal of communication, unless nodes switch their radios on at synchronized intervals—a rather nontrivial coordination task. In this article, we address the problem of synchronizing node radios to a single universal schedule in wireless mobile ad hoc networks that can potentially consist of thousands of nodes. More specifically, we are interested in operating the network with duty cycles that can be less than 1% of the total cycle time. We identify the fundamental issues that govern cluster merging and provide a detailed comparison of various policies using extensive simulations based on a variety of mobility patterns. We propose a specific scheme that allows a 4,000-node network to stay synchronized with a duty cycle of approximately 0.7%. Our work is based on an existing, experimental MAC protocol that we use for real-world applications and is validated in a real network of around 120 mobile nodes.

In many popular applications like peer-to-peer systems, large amounts of data are distributed among multiple sources. Analysis of this data and identifying clusters is challenging due to processing, storage, and transmission costs. In this paper, we propose GDCluster, a general fully decentralized clustering method, which is capable of clustering dynamic and distributed data sets. Nodes continuously cooperate through decentralized gossip-based communication to maintain summarized views of the data set. We customize GDCluster for execution of the partition-based and density-based clustering methods on the summarized views, and also offer enhancements to the basic algorithm. Coping with dynamic data is made possible by gradually adapting the clustering model. Our experimental evaluations show that GDCluster can discover the clusters efficiently with scalable transmission cost, and also expose its supremacy in comparison to the popular method LSP2P.

Publish/subscribe (pub/sub) is a popular communication paradigm in the design of large-scale distributed systems. A fundamental challenge in deploying pub/sub systems on a data center or a cloud infrastructure is efficient and cost-effective resource allocation that would allow delivery of notifications to all subscribers. In this paper, we provide answers to the following three fundamental questions: Given a pub/sub workload, (1) what is the minimum amount of resources needed to satisfy all the subscribers, (2) what is a cost-effective way to allocate resources for the given workload, and (3) what is the cost of hosting it on a public Infrastructure-as-a-Service (IaaS) provider like Amazon EC2. To answer these questions, we formulate a problem coined Minimum Cost Subscriber Satisfaction (MCSS). We prove MCSS to be NP-hard and provide an efficient heuristic solution based on a combination of optimizations. We evaluate the solution experimentally using real traces from Spotify and Twitter along with a pricing model from Amazon. We show the impact of each optimization using a naive solution as the baseline. Using a variety of practical scenarios for each dataset, we also show that our solution scales well for millions of subscribers and runs fast.

Publish/subscribe (pub/sub) is a popular communication paradigm in the design of large-scale distributed systems. A provider of a pub/sub service (whether centralized, peer-assisted, or based on a federated organization of cooperatively managed servers) commonly faces a fundamental challenge: given limited resources, how to maximize the satisfaction of subscribers? We provide, to the best of our knowledge, the first formal treatment of this problem by introducing two metrics that capture subscriber satisfaction in the presence of limited resources. This allows us to formulate matters as two new flavors of maximum coverage optimization problems. Unfortunately, both variants of the problem prove to be NP-hard. By subsequently providing formal approximation bounds and heuristics, we show, however, that efficient approximations can be attained. We validate our approach using real-world traces from Spotify and show that our solutions can be executed periodically in real-time in order to adapt to workload variations.

Understanding the social dynamics of a group of people can give new insights into social behavior. Physical proximity between individuals results from the interactions between them. Hence, measuring physical proximity is an important step towards a better understanding of social behavior. We discuss a novel approach to sense proximity from within the social dynamics. Our primary objective is to construct a spatio-temporal social graph from noisy proximity data. We address the technical and algorithmic challenges of measuring proximity reliably and accurately. Simulations and real world experiments demonstrate the feasibility and scalability of our approach. Our algorithms doubles the sensitivity of proximity detections at the cost of a slight reduction in specificity.

We focus on a popular message dissemination protocol for wireless ad-hoc networks, Gossip3. Our contribution is twofold. First, we perform an extensive experimental evaluation of Gossip3 under fully utilized wireless channel and across diverse node densities. We identify the parameters of Gossip3 that need special configuration for the protocol to operate optimally. Second, we devise a self-configuration algorithm for Gossip3, that allows the protocol to work optimally for any network. We demonstrate through simulations that our protocol significantly outperforms the default configuration of Gossip3.

We consider a large wireless network constituting a radio telescope. Each of the anticipated 3000 nodes is triggered to collect data for further analysis at a rate of more than 200 Hz, mostly caused by noisy environmental sources. However, relevant cosmic rays occur only a few times a day. As every trigger has an associated 12.5KB of data, and considering the size of the telescope in number of nodes and covered area, centralized processing is not an option. We propose a fully decentralized event detection algorithm based on collaborative local data analysis, effectively filtering out only those triggers that need further (centralized) processing. As we show through performance evaluations, the crux in the design is finding the right balance between accuracy and efficient use of resources such as the communication bandwidth in the unreliable communication environment.

A number of recently proposed systems provide secure and privacy-preserving data dissemination by leveraging pre-existing social trust relations and effectively mapping them into communication links. However, as we show in this paper, the underlying trust graph may not be optimal as a communication overlay. It has relatively long path lengths and it can be easily partitioned in scenarios where users are unavailable for a fraction of time. Following this observation, we present a method for improving the robustness of trust-based overlays. Essentially, we start with an overlay derived from the trust graph and evolve it in a privacy-preserving fashion into one that lends itself to data dissemination. The experimental evaluation shows that our approach leads to overlays that are significantly more robust under churn, and exhibit lower path lengths than the underlying trust graph.

Malware researchers rely on the observation of malicious code in execution to collect datasets for a wide array of experiments, including generation of detection models, study of longitudinal behavior, and validation of prior research. For such research to reflect prudent science, the work needs to address a number of concerns relating to the correct and representative use of the datasets, presentation of methodology in a fashion sufficiently transparent to enable reproducibility, and due consideration of the need not to harm others. In this paper we study the methodological rigor and prudence in 36 academic publications from 2006 -- 2011 that rely on malware execution. 40% of these papers appeared in the 6 highest-ranked academic security conferences. We find frequent shortcomings, including problematic assumptions regarding the use of execution-driven datasets (25% of the papers), absence of description of security precautions taken during experiments (71% of the articles), and oftentimes insufficient description of the experimental setup. Deficiencies occur in top-tier venues and elsewhere alike, highlighting a need for the community to improve its handling of malware datasets. In the hope of aiding authors, reviewers, and readers, we frame guidelines regarding transparency, realism, correctness, and safety for collecting and using malware datasets.

Hierarchical routing has often been mentioned as an appealing point-to-point routing technique for wireless sensor networks (sensornets). While there is a volume of analytical and high-level simulation results demonstrating its merits, there has been little work evaluating it in actual sensornet settings. This article bridges the gap between theory and practice. Having analyzed a number of proposed hierarchical routing protocols, we have developed a framework that captures the common characteristics of the protocols and identifies design points at which the protocols differ. We use a sensornet implementation of the framework in TOSSIM and on a 60-node testbed to study various trade-offs that hierarchical routing introduces, as well as to compare the performance of hierarchical routing with the performance of other routing techniques, namely shortest-path routing, compact routing, and beacon vector routing. The results show that hierarchical routing is a compelling routing technique also in practice. In particular, despite only logarithmic routing state, it can offer small routing stretch: an average of ∼ 1.25 and a 99th percentile of 2. It can also be robust, minimizing the maintenance traffic or the latency of reacting to changes in the network. Moreover, the trade-offs offered by hierarchical routing are attractive for many sensornet applications when compared to the other routing techniques. For example, in terms of routing state, hierarchical routing can offer scalability at least an order of magnitude better than compact routing, and at the same time, in terms of routing stretch, its performance is within 10--15% of that of compact routing; in addition, this performance can further be tuned to a particular application. Finally, we also identify a number of practical issues and limitations of which we believe sensornet developers adopting hierarchical routing should be aware.

Energy is the scarcest resource in ad-hoc wireless networks, particularly in wireless sensor networks requiring a long lifetime. Intermittently switching the radio on and off is widely adopted as the most effective way to keep energy consumption low. This, however, prevents the very goal of communication, unless nodes switch their radios on at synchronized intervals, a rather nontrivial coordination task. In this paper we address the problem of synchronizing node radios to a single universal schedule in very large scale wireless ad-hoc networks. More specifically, we focus on how independently synchronized clusters of nodes can detect each other and merge to a common radio schedule. Our main contributions consist in identifying the fundamental subproblems that govern cluster merging, providing a detailed comparison of the respective policies and their combinations, and supporting them by extensive simulation. Energy consumption, convergence speed, and network scalability have been the driving factors in our evaluation. The proposed policies are extensively tested in networks of up to 4,096 nodes. Our work is based on the GMAC protocol, a gossip-based MAC protocol for wireless ad-hoc networks.

Video-on-demand (VoD) is a next-generation Internet application of increasing interest allowing users to start watching a movie almost instantaneously by downloading the video on-the-fly. Provided that all users contribute to the system, shifting to the P2P paradigm allows efficient broadcast with a limited-bandwidth source. In VoD applications pieces are downloaded in order. This prevents us from directly applying a BitTorrent-like tit-for-tat incentive scheme. We advocate the use of a loose structure in P2P VoD applications to achieve high playback rates. In this paper we propose a decentralized piece dissemination scheme built on loosely coupled structures maintained using gossip. Peers are grouped into clusters depending on their playback position. Swarming is performed within the clusters while distributed feeding ensures that less advanced clusters get missing pieces from more advanced ones. Our simulations demonstrate that structured dissemination improves from 61% to 77% the achievable playback rate.

Superpeer architectures exploit the heterogeneity of nodes in a peer-to-peer (P2P) network by assigning additional responsibilities to higher capacity nodes. In the design of a superpeer network for file sharing, several issues have to be addressed: how client peers are related to superpeers, how superpeers locate files, how the load is balanced among the superpeers, and how the system deals with node failures. In this paper, we introduce a self-organizing superpeer network architecture (SOSPNet) that solves these issues in a fully decentralized manner. SOSPNet maintains a superpeer network topology that reflects the semantic similarity of peers sharing content interests. Superpeers maintain semantic caches of pointers to files, which are requested by peers with similar interests. Client peers, on the other hand, dynamically select superpeers offering the best search performance. We show how this simple approach can be employed not only to optimize searching, but also to solve generally difficult problems encountered in P2P architectures such as load balancing and fault tolerance. We evaluate SOSPNet using a model of the semantic structure derived from eight-month traces of two large file-sharing communities. The obtained results indicate that SOSPNet achieves close-to-optimal file search performance, quickly adjusts to changes in the environment (node joins and leaves), survives even catastrophic node failures, and efficiently distributes the system load taking into account superpeer capacities.

A recursive multihop area hierarchy has a number of applications in wireless sensor networks, the most common being scalable point-to-point routing, so-called hierarchical routing. In this paper, we consider the problem of maintaining a recursive multihop area hierarchy in large sensor networks. We present a gossip-based protocol, dubbed PL-Gossip, in which nodes, by using local-only operations and by periodically gossiping with their neighbors, collaboratively maintain such a hierarchy. Since the hierarchy is a complex distributed structure, PL-Gossip introduces special mechanisms for internode coordination and consistency enforcement. Yet, these mechanisms are seamlessly integrated within the basic gossiping framework. Through simulations and experiments with an actual embedded protocol implementation, we demonstrate that PL-Gossip maintains the hierarchy in a manner that addresses all the peculiarities of sensor networks. More specifically, it offers excellent opportunities for aggressive energy saving and facilitates provisioning energy harvesting infrastructure. In addition, it bootstraps and recovers the hierarchy after failures relatively fast while also being robust to message loss. Finally, it can seamlessly operate on real sensor node hardware in realistic deployment scenarios and can outperform existing state-of-the-art hierarchy maintenance protocols.

We consider multi-resolution storage, a technique for providing scalable adaptive data fidelity, necessary for many applications of large wireless sensor networks (WSNs). Although the previously proposed design of multi-resolution storage, based on quad trees and geographic routing, is conceptually simple, it exhibits inherent problems if applied to real-world WSNs. To address these problems, we revisit some of the networking assumptions and propose an alternative design that employs an overlay combining area and landmark hierarchies. Simulations and initial experiments with a prototype embedded implementation indicate that our solution can be scalable and can work on real hardware, which motivates further research.

Many large-scale utility computing infrastructures comprise heterogeneous hardware and software resources. This raises the need for scalable resource selection services, which identify resources that match application requirements, and can potentially be assigned to these applications. We present a fully decentralized resource selection algorithm by which resources autonomously select themselves when their attributes match a query. An application specifies what it expects from a resource by means of a conjunction of (attribute, value-range) pairs, which are matched against the attribute values of resources. We show that our solution scales in the number of resources as well as in the number of attributes, while being relatively insensitive to churn and other membership changes such as node failures.

Nodes in wireless ad hoc networks are often limited in terms of resources, such as storage, power, and bandwidth. A downside of this is the fact that local storage at one node cannot accommodate the vast amount of data contained in the network. In this paper, we present SharedState, a scheme for storage, replication, and distribution of common-interest data in wireless networks of resource-constrained devices (e.g. sensor nodes or embedded devices). SharedState works under the assumption that individual nodes would greatly benefit from having access to the wealth of information in the network, but are unable to store it locally at once. SharedState strives to make data available to every node by providing local access to a subset of the whole collection of data items in the network at any moment in time and ensuring that this subset is updated periodically. This is accomplished by probabilistic propagation and replication of data items, ensuring the availability and persistence of information in the face of changing network conditions. We evaluate the performance of SharedState by studying the effectiveness with which nodes can gather information from the network. In addition, we optimize the bandwidth usage of our proposed solution by minimizing unnecessary communication based on feedback from the local neighborhood.

Many techniques have been proposed to scale web applications. However, the data interdependencies between the database queries and transactions issued by the applications limit their efficiency. We claim that major scalability improvements can be gained by restructuring the web application data into multiple independent data services with exclusive access to their private data store. While this restructuring does not provide performance gains by itself, the implied simplification of each database workload allows a much more efficient use of classical techniques. We illustrate the data denormalization process on three benchmark applications: TPC-W, RUBiS and RUBBoS. We deploy the resulting service-oriented implementation of TPC-W across an 85-node cluster and show that restructuring its data can provide at least an order of magnitude improvement in the maximum sustainable throughput compared to master-slave database replication, while preserving strong consistency and transactional properties.

Abstract Most current peer‐to‐peer (P2P) file‐sharing systems treat their users as anonymous, unrelated entities, and completely disregard any social relationships between them. However, social phenomena such as friendship and the existence of communities of users with similar tastes or interests may well be exploited in such systems in order to increase their usability and performance. In this paper we present a novel social‐based P2P file‐sharing paradigm that exploits social phenomena by maintaining social networks and using these in content discovery, content recommendation, and downloading. Based on this paradigm's main concepts such as taste buddies and friends, we have designed and implemented the TRIBLER P2P file‐sharing system as a set of extensions to BitTorrent. We present and discuss the design of TRIBLER, and we show evidence that TRIBLER enables fast content discovery and recommendation at a low additional overhead, and a significant improvement in download performance. Copyright © 2007 John Wiley & Sons, Ltd.

In this paper we describe and evaluate a fully distributed P2P evolutionary algorithm (EA) with adaptive autonomous selection. Autonomous selection means that decisions regarding survival and reproduction are taken by the individuals themselves independently, without any central control.This allows for a fully distributed EA, where not only reproduction (crossover and mutation) but also selection is performed at local level. An unwanted consequence of adding and removing individuals in a non-synchronized manner is that the population size gets out of control too. This problem is resolved by addingan adaptation mechanism allowing individuals to regulate their own selection pressure. The key tothis is a gossiping algorithm that enables individuals to maintain estimates on the size andthe fitness of the population. The algorithm is experimentally evaluated on a test problem to show the viability of the idea and to gain insight into the run-time dynamics of such an algorithm. The results convincingly demonstrate the feasibility of a fully decentralized EA in which the population size can be kept stable.

Super-peer architectures exploit the heterogeneity of nodes in a P2P network by assigning additional responsi- bilities to higher-capacity nodes. In the design of a super- peer network for file sharing, several issues have to be ad- dressed: how client peers are related to super-peers, how super-peers locate files, how the load is balanced among the super-peers, and how the system deals with node failures. In this paper we introduce a self-organizing super-peer net- work architecture (SOSPNET) that solves these issues in a fully decentralized manner. SOSPNET maintains a super- peer network topology that reflects the semantic similarity of peers sharing content interests. Super-peers maintain se- mantic caches of pointers to files which are requested by peers with similar interests. Client peers, on the other hand, dynamically select super-peers offering the best search per- formance. We show how this simple approach can be em- ployed not only to optimize searching, but also to solve gen- erally difficult problems encountered in P2P architectures such as load balancing and fault tolerance. We evaluate SOSPNET using a model of the semantic structure derived from the 8-month traces of two large file-sharing communi- ties. The obtained results indicate that SOSPNET achieves close-to-optimal file search performance, quickly adjusts to changes in the environment (node joins and leaves), sur- vives even catastrophic node failures, and efficiently dis- tributes the system load taking into account peer capacities.

BitTorrent is one of the most popular protocols for content distribution and accounts for more than 15% of the total Internet traffic. In this paper, we present an analytical model of the protocol. Our work differs from previous works as it models the BitTorrent protocol specifically and not as a general file-swarming protocol. In our study, we observe that to accurately model the download process of a BitTorrent client, we need to split this process into three phases. We validate our model using simulations and real-world traces. Using this model, we study the efficiency of the protocol based on various protocol-specific parameters such as the maximum number of connections and the peer set size. Furthermore, we study the relationship between changes in the system parameters and the stability of the protocol. Our model suggests that the stability of BitTorrent protocol depends heavily on the number of pieces a file is divided into and the arrival rate of clients to the network.

PL-Gossip is evaluated using packet-level event-driven simulator. Experiments are conducted with varying network sizes, densities, message loss rates, and node arrival and departure schemes . The experimental results verified that a node's state, as maintained by the protocol (i.e., the label and the routing table), grows logarithmically with the network size, which ensures scalability and small bandwidth requirements. In addition, the hierarchical network organization offers efficient routing: the average hop stretch does not exceed 25%. Moreover, the hierarchy is quickly bootstrapped or restored, also under significant node population changes, which minimizes disruptions caused to the applications. Finally, the experiments confirmed what the authors proved analytically, that is, the protocol recovers the network from any massive node failure or network partitioning, even when such incidents happen continuously and concurrently. PL-Gossip is also implemented in TinyOS. The implementation is subject to real-world tests while at the same time being integrated into a large-scale real-world system.

Ad hoc networks rely on nodes forwarding each other's packets, making trust and cooperation key issues for ensuring network performance. As long as all nodes in the network belong to the same organization and share the same goal (in military scenarios, for example), it can generally be expected that all nodes can be trusted. However, as wireless technology becomes more commonplace, we can foresee the appearance of very large, heterogeneous networks where the intentions of neighboring nodes are unknown. Without any security measures in place, any node is capable of compromising the integrity of the data it forwards. Our goal in this paper is to ensure the integrity of the data being disseminated without resorting to complex and expensive solutions. We achive this by discouraging malicious behavior in two ways: a) enforcing integrity checks close to the source and b) refusing to communicate with obviously malicious nodes. We find that by having nodes sample their traffic for corrupted messages, malicious nodes can be identified with high accuracy, in effect transforming our collection of nodes into a self-policing network.

Abstract We present versatile anycast, which allows a service running on a varying collection of nodes scattered over a wide‐area network to present itself to the clients as one running on a single node. Providing a single logical address enables the client‐side software to preserve the traditional service access model based on single access points. At the same time, the dynamic composition of anycast groups implemented by versatile anycast enables the server‐side service infrastructure to evolve and adapt to changing network conditions. We implement versatile anycast using Mobile IPv6, which decouples the logical addresses of mobile nodes from their physical location. We exploit that decoupling to implement logical service addresses that are not bound to any physical nodes, and employ standard MIPv6 mechanisms to dynamically map each such address onto individual service nodes. Our solution enables a service to transparently hand off clients among the service nodes at the network level while preserving optimal routing between the clients and the service nodes. We demonstrate that the overhead of versatile anycasting is very low. In particular, the client‐perceived handoff time is shown to be a linear function of the latencies among the client and the service nodes participating in the handoff. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract Much research on content‐based P2P searching for file‐sharing applications has focused on exploiting semantic relations between peers to facilitate searching. Current methods suggest reactive ways to manage semantic relations: they rely on the usage of the underlying search mechanism, and infer semantic relationships based on the queries placed and the corresponding replies received. In this paper we follow a different approach, proposing a proactive method to build a semantic overlay. Our method is based on an epidemic protocol that clusters peers with similar content. Peer clustering is done in a completely implicit way, that is, without requiring the user to specify preferences or to characterize the content of files being shared. In our approach, each node maintains a small list of semantically optimal peers. Our simulation studies show that such a list is highly effective when searching files. The construction of this list through gossiping is efficient and robust, even in the presence of changes in the network. Copyright © 2007 John Wiley & Sons, Ltd.

Gossip-based communication protocols are appealing in large-scale distributed applications such as information dissemination, aggregation, and overlay topology management. This paper factors out a fundamental mechanism at the heart of all these protocols: the peer-sampling service. In short, this service provides every node with peers to gossip with. We promote this service to the level of a first-class abstraction of a large-scale distributed system, similar to a name service being a first-class abstraction of a local-area system. We present a generic framework to implement a peer-sampling service in a decentralized manner by constructing and maintaining dynamic unstructured overlays through gossiping membership information itself. Our framework generalizes existing approaches and makes it easy to discover new ones. We use this framework to empirically explore and compare several implementations of the peer-sampling service. Through extensive simulation experiments we show that---although all protocols provide a good quality uniform random stream of peers to each node locally---traditional theoretical assumptions about the randomness of the unstructured overlays as a whole do not hold in any of the instances. We also show that different design decisions result in severe differences from the point of view of two crucial aspects: load balancing and fault tolerance. Our simulations are validated by means of a wide-area implementation.

P2P systems that rely on the voluntary contribution of bandwidth by the individual peers may suffer from free riding. To address this problem, mechanisms enforcing fairness in bandwidth sharing have been designed, usually by limiting the download bandwidth to the available upload bandwidth. As in real environments the latter is much smaller than the former, these mechanisms severely affect the download performance of most peers. In this paper we propose a system called 2Fast, which solves this problem while preserving the fairness of bandwidth sharing. In 2Fast, we form groups of peers that collaborate in downloading a file on behalf of a single group member, which can thus use its full download bandwidth. A peer in our system can use its currently idle bandwidth to help other peers in their ongoing downloads, and get in return help during its own downloads. We assess the performance of 2Fast analytically and experimentally, the latter in both real and simulated environments. We find that in realistic bandwidth limit settings, 2Fast improves the download speed by up to a factor of 3.5 in comparison to state-of-the-art P2P download protocols

The Globe Distribution Network (GDN) is an application for the efficient, worldwide distribution of freely redistributable software packages. Distribution is made efficient by encapsulating the software into special distributed objects which efficiently replicate themselves near to the downloading clients. The Globe Distribution Network takes a novel, optimistic approach to stop the illegal distribution of copyrighted and illicit material via the network. Instead of having moderators check the packages at upload time, illegal content is removed and its uploader's access to the network permanently revoked only when the violation is discovered. Other protective measures defend the GDN against internal and external attacks to its availability. By exploiting the replication of the software and using fault-tolerant server software, the Globe Distribution Network achieves high availability. A prototype implementation of the GDN is available from http://www.cs.vu.nl/globe/.

We present GlobeDB, a system for hosting Web applications that performs autonomic replication of application data. GlobeDB offers data-intensive Web applications the benefits of low access latencies and reduced update traffic. The major distinction in our system compared to existing edge computing infrastructures is that the process of distribution and replication of application data is handled by the system automatically with very little manual administration. We show that significant performance gains can be obtained this way. Performance evaluations with the TPC-W benchmark over an emulated wide-area network show that GlobeDB reduces latencies by a factor of 4 compared to non-replicated systems and reduces update traffic by a factor of 6 compared to fully replicated systems.

Peer-to-peer (P2P) networks are generally considered to be free havens for pirated content, in particular with respect to music. We describe a solution for the problem of copyright infringement in P2P networks for music sharing. In particular, we propose a P2P protocol that integrates the functions of identification, tracking, and sharing of music with those of licensing, monitoring, and payment. This highly decentralized music-aware P2P protocol will allow access to large amounts of music of guaranteed quality; it merges in a natural way the policing functions for copyright protection and an efficient music-management infrastructure for the benefit of the user.

Replication in the World-Wide Web covers a wide range of techniques. Often, the redirection of a client browser towards a given replica of a Web page has to be explicit and is performed after the client's request has reached the Web server storing the requested page. As an alternative, we propose to perform the redirection as close to the client as possible in a fully distributed manner Distributed redirection ensures that we find a replica wherever it is stored and that the closest possible replica is always found first. By exploiting locality, we can keep latency low.

Pervasive messaging is the part of pervasive computing that enables users to communicate with each other. Many of today's electronic messaging systems have their own distinct merits and peculiarities. Pervasive messaging will have to shield the user from these differences. In this paper we introduce a taxonomy for electronic messaging systems, providing a uniform way to analyze, compare, and discuss electronic messaging systems. With this taxonomy, we analyze the current practice, demonstrating its shortfalls. To overcome these shortfalls, we introduce a novel messaging model: the unified messaging system. This system can, in fact, mimic any electronic messaging system, thus providing powerful unified messaging.

Large-scale distributed systems present numerous security problems not present in local systems. We present a general security architecture for a large-scale object-based distributed system. Its main features include ways for servers to authenticate clients, clients to authenticate servers, new secure servers to be instantiated without manual intervention, and ways to restrict which client can perform which operation on which object. All of these features are done in a platform- and application-independent way, so the results are quite general. The basic idea behind the scheme is to have each object owner issue cryptographically sealed certificates to users to prove which operations they may request and to servers to prove which operations they are authorized to execute. These certificates are used to ensure secure binding and secure method invocation. The paper discusses the required certificates and security protocols for using them.

This paper describes a novel peer-to-peer (P2P) environment for running distributed Java applications on the Internet. The possible application areas include simple load balancing, parallel evolutionary computation, agent-based simulation and artificial life. Our environment is based on cutting-edge P2P technology. We introduce and analyze the concept of long term memory which provides protection against partitioning of the network. We demonstrate the potentials of our approach by analyzing a simple distributed application. We present theoretical and empirical evidence that our approach is scalable, effective and robust.

Services for locating mobile objects are often organized as a distributed search tree. The advantage of this approach is that the service can scale as a system grows in size and number of objects. However, a potential problem is that high-level nodes may become a bottleneck affecting the scalability of the service. A traditional solution is to also distribute the location information managed by a single node across multiple machines. We introduce a method that radically applies distribution of location information such that the load is evenly balanced across all machines that form part of the implementation of the service, while at the same time exploiting locality.

To improve the scalability of the Web, it is common practice to apply caching and replication techniques. Numerous strategies for placing and maintaining multiple copies of Web documents at several sites have been proposed. These approaches essentially apply a global strategy by which a single family of protocols is used to choose replication sites and keep copies mutually consistent. We propose a more flexible approach by allowing each distributed document to have its own associated strategy. We propose a method for assigning an optimal strategy to each document separately and prove that it generates a family of optimal results. Using trace-based simulations, we show that optimal assignments clearly outperform any global strategy. We have designed an architecture for supporting documents that can dynamically select their optimal strategy and evaluate its feasibility.

In this paper we present work in progress on a worldwide, scalable multi-agent system, based on a paradigm of hyperlinked rooms. The framework offers facilities for managing distribution, security and mobility aspects for both active elements (agents) and passive elements (objects) in the system. Our framework offers separation of logical concepts from physical representation, distribution support, mobility support, and a security architecture.

The Globe Distribution Network (GDN) is an application for worldwide distribution of freely redistributable software packages. The GDN takes a novel, optimistic approach to stop the illegal distribution of copyrighted and illicit material via the network. Instead of having moderators check the software archives at upload time, illegal content is removed and its uploader's access to the network permanently revoked only when the content is discovered. An important feature of the GDN is that the objects containing the software can run on untrustworthy servers. A first version of the GDN has been implemented and has been running since October 2000 across four European sites.

A location service tracks and locates objects. Such a service should provide efficient means for updating and looking up an object's address, especially for those that are mobile. However, current location services have limited scalability due to poor exploitation of locality and ineffective caching. An important aspect of efficient caching in the presence of mobility is to identify boundaries of the region within which a mobile object usually remains. Caching a reference to such a region rather than to the object itself ensures that the cached entry remains stable. Identifying a region requires dynamically taking migration patterns into account. This paper describes a scalable location service that efficiently supports tracking mobile objects, partly by dynamically adapting to the mobile behavior of each object separately.

A non-formal motivation and description is given of ADL-d, a graphical design technique for parallel and distributed software. ADL-d allows a developer to construct an application in terms of communicating processes. The technique distinguishes itself from others by its rigid orthogonal approach to communication modeling, which is advantageous in many areas. Without being committed to one particular design method, ADL-d as a technique can be used from the early phases of application design through phases that concentrate on algorithmic design, and final implementation on some target platform. The authors discuss and motivate all ADL-d components, including recently incorporated features such as support for connection-oriented communication, and support for modeling dynamically changing communication structures.

A major problem in the development of distributed applications is that one cannot assume that the environment in which the application is to operate will remain the same. This means that developers must take into account that the application should be easy to adapt, A requirement that is often formulated imprecisely is that an application should be scalable. The authors concentrate on scalability as a requirement for distributed applications, what it actually means, and how it can be taken into account during system design and implementation. They present a framework in which scalability requirements can be formulated precisely. In addition, they present an approach by which scalability can be taken into account during application development. Their approach consists of an engineering method for distributing functionality, combined with an object-based implementation framework for applying scaling techniques such as replication and caching.

Despite the extensive use of caching techniques, the Web is overloaded. While the caching techniques currently used help some, it would be better to use different caching and replication strategies for different Web pages, depending on their characteristics. We propose a framework in which such strategies can be devised independently per Web document. A Web document is constructed as a worldwide, scalable distributed Web object. Depending on the coherence requirements for that document, the most appropriate caching or replication strategy can subsequently be implemented and encapsulated by the Web object. Coherence requirements are formulated from two different perspectives: that of the Web object, and that of clients using the Web object. We have developed a prototype in Java to demonstrate the feasibility of implementing different strategies for different Web objects.

We describe the algorithmic design of a worldwide location service for distributed objects. A distributed object can reside at multiple locations at the same time, and offers a set of addresses to allow client processes to contact it. Objects may be highly mobile like, for example, software agents or Web applets. The proposed location service supports regular updates of an object's set of contact addresses, as well as efficient look-up operations. Our design is based on a worldwide distributed search tree in which addresses are stored at different levels, depending on the migration pattern of the object. By exploiting an object's relative stability with respect to a region, combined with the use of pointer caches, look-up operations can be made highly efficient.