The identification of misbehaving elements in a distributed system is an important task in many diverse settings that can be represented as graphs; this problem can be cast as the computation of a subset of the graph nodes by exploiting a pre-determined detection mechanism. In this paper we propose a simple yet accurate algorithm to compute the set of nodes of a graph suspected to be malicious that is based on the so called comparison detection model. In this framework, a node can play the role of the comparator for two of its neighbors and can provide a boolean result based on the actual status of both. The algorithm we propose has low computational complexity and linear space complexity; furthermore, it only requires one parameter to trade accuracy against computational cost. We also show it outperforms the state-of-the-art and performs equally very well on both synthetic and real world graphs.

We propose a simple model of an idealized online cultural market in which N items, endowed with a hidden quality metric, are recommended to users by a ranking algorithm possibly biased by the current items’ popularity. Our goal is to better understand the underlying mechanisms of the well-known fact that popularity bias can prevent higher-quality items from becoming more popular than lower-quality items, producing an undesirable misalignment between quality and popularity rankings. We do so under the assumption that users, having limited time/attention, are able to discriminate the best-quality only within a random subset of the items. We discover the existence of a harmful regime in which improper use of popularity can seriously compromise the emergence of quality, and a benign regime in which wise use of popularity, coupled with a small discrimination effort on behalf of users, guarantees the perfect alignment of quality and popularity ranking. Our findings clarify the effects of algorithmic popularity bias on quality outcomes, and may inform the design of more principled mechanisms for techno-social cultural markets.

Coding-based distributed storage systems (DSS) are employed in many diverse heterogeneous settings, e.g., cloud storage data centers, peer-to-peer systems, wireless sensor networks, fog/edge computing system, to provide better throughput, latency, reliability, scalability, load adaptation, geographical migration and fault tolerance with respect to traditional monolithic enterprise storage systems. Despite the undoubted advantages offered by coding, reliability and security are jeopardized by a pollution attack that can easily disrupt the entire system and degrade performance. In this paper we take an abstract view of a DSS and we investigate by means of mathematical modeling what are the availability, robustness, and timeliness of heterogeneous, coding-based DSS when storage nodes (SN) are unreliable and can be malicious. To this end, we focus on a class of allocations of coded fragments to SNs that we callfeasible allocations; the model takes into account bothreliabilityandreactivityof SNs. We definerobust availabilityandtimelinessof feasible allocations that we use to characterize the overall performance and robustness of the DSS in a reference scenario. Our analysis reveals that code redundancy is a double-edged sword in a DSS where malicious SNs come into play and that there exists an optimal value of code redundancy regardless all system parameters that maximizes the number of malicious SNs that can be tolerated to achieve maximum DSS performance. We also found that larger codes are preferred over short ones as they yield superior DSS performance in the presence of malicious SNs. Furthermore, when multiple feasible allocations yield the highest DSS performance timeliness can be used as a guide for the choice. Finally, heterogeneity plays a role in determining the timeliness of the maximally spread allocations in the case of targeted attacks.

Abstract Rateless codes (a.k.a. fountain codes, digital fountain) have found their way in numerous peer-to-peer based applications although their robustness to the so called pollution attack has not been deeply investigated because they have been originally devised as a solution for dealing with block erasures and not for block modification. In this paper we provide an analysis of the intrinsic robustness of three rateless codes algorithms, i.e., random linear network codes (RLNC), Luby transform (LT), and band codes (BC) against intentional data modification. By intrinsic robustness we mean the ability of detecting as soon as possible that modification of at least one equation has occurred as well as the possibility a receiver can decode from the set of equations with and without the modified ones. We focus on bare rateless codes where no additional information is added to equations (e.g., tags) or higher level protocol are used (e.g., verification keys to pre-distribute to receivers) to detect and recover from data modification. We consider several scenarios that combine both random and targeted selection of equations to alter and modification of an equation that can either change the rank of the coding matrix or not. Our analysis reveals that a high percentage of attacks goes undetected unless a minimum code redundancy is achieved, LT codes are the most fragile in virtually all scenarios, RLNC and BC are quite insensitive to the victim selection and type of alteration of chosen equations and exhibit virtually identical robustness although BC offer a low complexity of the decoding algorithm.

During a pollution attack, malicious nodes purposely transmit bogus data to the honest nodes to cripple the communication. Securing the communication requires identifying and isolating the malicious nodes. However, in network coding (NC) architectures, random recombinations at the nodes increase the probability that honest nodes relay polluted packets. Thus, discriminating between honest and malicious nodes to isolate the latter turns out to be challenging at best. Band codes (BCs) are a family of rateless codes whose coding window size can be adjusted to reduce the probability that honest nodes relay polluted packets. We leverage such a property to design a distributed scheme for identifying the malicious nodes in the network. Each node counts the number of times that each neighbor has been involved in cases of polluted data reception and exchanges such counts with its neighbor nodes. Then, each node computes for each neighbor a discriminative honest score estimating the probability that the neighbor relays clean packets. We model such probability as a function of the BC coding window size, showing its impact on the accuracy and effectiveness of our distributed blacklisting scheme. We experiment distributing a live video feed in a P2P NC system, verifying the accuracy of our model and showing that our scheme allows us to secure the network against pollution attacks recovering near pre-attack video quality.

Online social networks (OSN) have today reached a remarkable capillary diffusion. There are numerous examples of very large platforms people use to communicate and maintain relationships. People also subscribe to several OSNs, e.g., people create accounts on Facebook, Twitter, and so on. This phenomenon leads to online social internetworking (OSI) scenarios where users who subscribe to multiple OSNs are termed as bridges . Unfortunately, several important features make the study of information propagation in an OSI scenario a difficult task, e.g., correlations in both the structural characteristics of OSNs and the bridge interconnections among them, heterogeneity and size of OSNs, activity factors, cross-posting propensity, and so on. In this article, we propose a directed random graph-based model that is amenable to efficient numerical solution to analyze the phenomenon of information propagation in an OSI scenario; in the model development, we take into account heterogeneity and correlations introduced by both topological (correlations among nodes degrees and among bridge distributions) and user-related factors (activity index, cross-posting propensity). We first validate the model predictions against simulations on snapshots of interconnected OSNs in a reference scenario. Subsequently, we exploit the model to show the impact on the information propagation of several characteristics of the reference scenario, i.e., size and complexity of the OSI scenario, degree distribution and overall number of bridges, growth and decline of OSNs in time, and time-varying cross-posting users propensity.

The widespread diffusion of distributed and cloud storage solutions has changed dramatically the way users, system designers, and service providers manage their data. Outsourcing data on remote storage provides indeed many advantages in terms of both capital and operational costs. The security of data outsourced to the cloud, however, still represents one of the major concerns for all stakeholders. Pollution attacks, whereby a set of malicious entities attempt to corrupt stored data, are one of the many risks that affect cloud data security. In this paper we deal with pollution attacks in coding-based block-level cloud storage systems, i.e., systems that use linear codes to fragment, encode, and disperse virtual disk sectors across a set of storage nodes to achieve desired levels of redundancy, and to improve reliability and availability without sacrificing performance. Unfortunately, the effects of a pollution attack on linear coding can be disastrous, since a single polluted fragment can propagate pervasively in the decoding phase, thus hampering the whole sector. In this work we show that, using rateless codes, we can design an early pollution detection algorithm able to spot the presence of an attack while fetching the data from cloud storage during the normal disk reading operations. The alarm triggers a procedure that locates the polluting nodes using the proposed detection mechanism along with statistical inference. The performance of the proposed solution is analyzed under several aspects using both analytical modelling and accurate simulation using real disk traces. Our results show that the proposed approach is very robust and is able to effectively isolate the polluters, even in harsh conditions, provided that enough data redundancy is used.

We provide a comprehensive characterization of band codes (BC) as a resilient-by-design solution to pollution attacks in network coding (NC)-based peer-to-peer live video streaming. Consider one malicious node injecting bogus coded packets into the network: the recombinations at the nodes generate an avalanche of novel coded bogus packets. Therefore, the malicious node can cripple the communication by injecting into the network only a handful of polluted packets. Pollution attacks are typically addressed by identifying and isolating the malicious nodes from the network. Pollution detection is, however, not straightforward in NC as the nodes exchange coded packets. Similarly, malicious nodes identification is complicated by the ambiguity between malicious nodes and nodes that have involuntarily relayed polluted packets. This paper addresses pollution attacks through a radically different approach which relies on BCs. BCs are a family of rateless codes originally designed for controlling the NC decoding complexity in mobile applications. Here, we exploit BCs for the totally different purpose of recombining the packets at the nodes so to avoid that the pollution propagates by adaptively adjusting the coding parameters. Our streaming experiments show that BCs curb the propagation of the pollution and restore the quality of the distributed video stream.

In this paper device-to-device (D2D) communication is proposed as a tool for enhancing the services provided by mobile cellular networks. The technique we discuss relies on the cooperation among the mobile users that participate in the service delivery process, under the control of the base station. In particular, the paper proposes an incentive mechanism encouraging terminals to organize into an optimal number of clusters from the point of view of both bandwidth capacity and power saving. The aspects inducing users to collaborate are analyzed and modelled, e.g., the amount of mobile battery power drained during collaboration, to better design incentives to switch to D2D. The proposed technique allows the base station to estimate the incentives to grant to the mobile terminals to optimize its cost. Through both analysis and simulations, we show that our scheme achieves a significant gain in terms of costs while increasing the bandwidth capacity of the whole cell.

Band Codes (BC) have been recently proposed as a solution for controlled-complexity random Network Coding (NC) in mobile applications, where energy consumption is a major concern. In this paper, we investigate the potential of BC in a peer-to-peer video streaming scenario where malicious and honest nodes coexists. Malicious nodes launch the so called pollution attack by randomly modifying the content of the coded packets they forward to downstream nodes, preventing honest nodes from correctly recovering the video stream. Whereas in much of the related literature this type of attack is addressed by identifying and isolating the malicious nodes, in this work we propose to address it by adaptively adjusting the coding scheme so to introduce resilience against pollution propagation. We experimentally show the impact of a pollution attack in a defenseless system and in a system where the coding parameters of BC are adaptively modulated following the discovery of polluted packets in the network. We observe that just by tuning the coding parameters, it is possible to reduce the impact of a pollution attack and restore the quality of the video communication.

Network coding (NC)-based peer-to-peer (P2P) streaming represents an effective solution to aggregate user capacities and to increase system throughput in live multimedia streaming. Nonetheless, such systems are vulnerable to pollution attacks where a handful of malicious peers can disrupt the communication by transmitting just a few bogus packets which are then recombined and relayed by unaware honest nodes, further spreading the pollution over the network. Whereas previous research focused on malicious nodes identification schemes and pollution-resilient coding, in this paper we show pollution countermeasures which make a standard NC scheme resilient to pollution attacks. Thanks to a simple yet effective analytical model of a reference node collecting packets by malicious and honest neighbors, we demonstrate that: i) packets received earlier are less likely to be polluted, and ii) short generations increase the likelihood to recover a clean generation. Therefore, we propose a recombination scheme where nodes draw packets to be recombined according to their age in the input queue, paired with a decoding scheme able to detect the reception of polluted packets early in the decoding process and short generations. The effectiveness of our approach is experimentally evaluated in a real system we developed and deployed on hundreds to thousands of peers. Experimental evidence shows that, thanks to our simple countermeasures, the effect of a pollution attack is almost canceled and the video quality experienced by the peers is comparable to pre-attack levels.

Block-level cloud storage (BLCS) offers to users and applications the access to persistent block storage devices (virtual disks) that can be directly accessed and used as if they were raw physical disks. In this paper we devise ENIGMA, an architecture for the back-end of BLCS systems able to provide adequate levels of access and transfer performance, availability, integrity, and confidentiality, for the data it stores. ENIGMA exploits LT rateless codes to store fragments of sectors on storage nodes organized in clusters. We quantitatively evaluate how the various ENIGMA system parameters affect the performance, availability, integrity, and confidentiality of virtual disks. These evaluations are carried out by using both analytical modeling (for availability, integrity, and confidentiality) and discrete event simulation (for performance), and by considering a set of realistic operational scenarios. Our results indicate that it is possible to simultaneously achieve all the objectives set forth for BLCS systems by using ENIGMA, and that a careful choice of the various system parameters is crucial to achieve a good compromise among them. Moreover, they also show that LT coding-based BLCS systems outperform traditional BLCS systems in all the aspects mentioned before.

In this paper, we consider a scenario where nodes in a MANET disseminate data chunks using rateless codes. Any node is able to successfully decode any chunk by collecting enough coded blocks from several other nodes without any coordination. We consider the problem of identifying malicious nodes that launch a pollution attack by deliberately modifying the payload of coded blocks before transmitting. It follows that the original chunk can only be obtained if there are no malicious nodes among the chunk providers. In this paper we propose SIEVE, a fully distributed technique to infer the identity of malicious nodes. A node creates what we termed a check whenever a chunk is decoded; a check is a pair composed of the set of other nodes that provided coded blocks used to decode the chunk (the chunk uploaders) and a flag indicating whether the chunk is corrupted or not. SIEVE exploits rateless codes to detect chunk integrity and belief propagation to infer the identity of malicious nodes. In particular, every node autonomously constructs its own bipartite graph (a.k.a. factor graph in the literature) whose vertexes are checks and nodes, respectively. Then, it periodically runs the belief propagation algorithm on its factor graph to infer the probability of other nodes being malicious. We show by running detailed simulations using ns-3 that SIEVE is very accurate and robust under several attack scenarios and deceiving actions. We discuss how the topological properties of the factor graph impacts SIEVE performance and show that nodes speed in the MANET plays a role on the identification accuracy. Furthermore, an interesting trade-off between coding efficiency and SIEVE accuracy, completeness, and reactivity is discovered. We also show that SIEVE is efficient requiring low computational, memory, and communication resources.

A key problem in network coding (NC) lies in the complexity and energy consumption associated with the packet decoding processes, which hinder its application in mobile environments. Controlling and hence limiting such factors has always been an important but elusive research goal, since the packet degree distribution, which is the main factor driving the complexity, is altered in a non-deterministic way by the random recombinations at the network nodes. In this paper we tackle this problem with a new approach and propose Band Codes (BC), a novel class of network codes specifically designed to preserve the packet degree distribution during packet encoding, recombination and decoding. BC are random codes over GF(2) that exhibit low decoding complexity, feature limited and controlled degree distribution by construction, and hence allow to effectively apply NC even in energy-constrained scenarios. In particular, in this paper we motivate and describe our new design and provide a thorough analysis of its performance. We provide numerical simulations of the BC performance in order to validate the analysis and assess the overhead of BC with respect to a conventional random NC scheme. Moreover, experiment in a real-world application, namely peer-to-peer mobile media streaming using a random-push protocol, show that BC reduce the decoding complexity by a factor of two with negligible increase of the encoding overhead, paving the way for the application of NC to power-constrained devices.

Peer-to-peer live streaming applications are vulnerable to malicious actions of peers that deliberately modify data to decrease or prevent the fruition of the media (pollution attack). In this article we propose DIP , a fully distributed, accurate, and robust algorithm for the identification of polluters. DIP relies on checks that are computed by peers upon completing reception of all blocks composing a data chunk. A check is a special message that contains the set of peer identifiers that provided blocks of the chunk as well as a bit to signal if the chunk has been corrupted. Checks are periodically transmitted by peers to their neighbors in the overlay network; peers receiving checks use them to maintain a factor graph. This graph is bipartite and an incremental belief propagation algorithm is run on it to compute the probability of a peer being a polluter. Using a prototype deployed over PlanetLab we show by extensive experimentation that DIP allows honest peers to identify polluters with very high accuracy and completeness, even when polluters collude to deceive them. Furthermore, we show that DIP is efficient, requiring low computational, communication, and storage overhead at each peer.

Peer-to-peer (P2P) resource location techniques in grid systems have been recently investigated to obtain scalability, reliability, efficiency, fault-tolerance, security, and robustness. Query resolution for locating resources and update information on their own resource status in these systems can be abstracted as the problem of allowing one peer to obtain a local view of global information defined on all peers of a P2P unstructured network. In this paper, the system is represented as a set of nodes connected to form a P2P network where each node holds a piece of information that is required to be communicated to all the participants. Moreover, we assume that the information can dynamically change and that each peer periodically requires to access the values of the data of all other peers. A novel approach based on a continuous flow of control packets exchanged among the nodes using the random walk principle and rateless coding is proposed. An innovative rateless decoding mechanism that is able to cope with asynchronous information updates is also proposed. The performance of the proposed system is evaluated both analytically and experimentally by simulation. The analytical results show that the proposed strategy guarantees quick diffusion of the information and scales well to large networks. Simulations show that the technique is effective also in presence of network and information dynamics.

Peer-to-peer streaming has witnessed a great success thanks to the possibility of aggregating resources from all participants. Nevertheless, performance of the entire system may be highly degraded due to the presence of malicious peers that share bogus data on purpose. In this paper, we propose to use a statistical inference technique, namely, belief propagation (BP), to estimate the probability of peers being malicious. The detection algorithm is run by a set of trusted monitor nodes that receives notification messages (checks) from peers whenever they obtain a chunk of data; these checks contain the list of the chunk uploaders and a flag to mark the chunk as polluted or clean. Peers are able to detect if the received chunk is polluted or not but, since multiparty download is employed, they are not capable to identify the source(s) of bogus blocks. This problem definition allows us to define a factor graph of peers and checks on which an incremental version of the belief propagation algorithm is run by the monitor nodes to infer the probability of each peer being a malicious one. We evaluate the accuracy, robustness, and complexity of our technique by running a real peer-to-peer application on PlanetLab. We show that the proposed approach is very accurate and robust against malicious nodes misbehaving (different pollution intensity, presence of fake checks, churning, and total uncooperation from malicious nodes), increasing number and colluding behavior of malicious nodes.

We present Band Codes (BC), a novel class of rate less codes that makes possible to control the computational complexity of Network Coding (NC). NC increases throughput of the networks via packet recombinations at the network nodes. In a NC scenario based on rate less codes, the recombinations at the nodes alter the packet degree distribution selected at the source and increase the computational complexity of the packet decoding process. Unlike other classes of rate less codes, BC preserve the degree distribution of the encoded packets through the recombinations at the nodes. Furthermore, BC enable to control the decoding complexity of each network node independently from the rest of the network. We evaluate BC in a P2P scenario using a purposely designed random-push protocol for live video streaming. The experiments show that BC achieve high encoding efficiency, enable nodes with different computational capabilities to coexist within the same network and reduce the processor load on a real mobile device by nearly 50%.

In this paper we consider the following problem: nodes in a MANET must disseminate data chunks using rateless codes but some nodes are assumed to be malicious, i.e., before transmitting a coded packet they may modify its payload. Nodes receiving corrupted coded packets are prevented from correctly decoding the original chunk. We propose SIEVE, a fully distributed technique to identify malicious nodes. SIEVE is based on special messages called checks that nodes periodically transmit. A check contains the list of nodes identifiers that provided coded packets of a chunk as well as a flag to signal if the chunk has been corrupted. SIEVE operates on top of an otherwise reliable architecture and it is based on the construction of a factor graph obtained from the collected checks on which an incremental belief propagation algorithm is run to compute the probability of a node being malicious. Analysis is carried out by detailed simulations using ns-3. We show that SIEVE is very accurate and discuss how nodes speed impacts on its accuracy. We also show SIEVE robustness under several attack scenarios and deceiving actions.

Interconnection of multiple P2P networks has recently emerged as a viable solution to increase system reliability and fault-tolerance as well as to increase resource availability. In this paper we consider interconnection of large scale unstructured P2P networks by means of special nodes (called synapses) that are co-located in more than one overlay. Synapses act as trait d'union by sending/forwarding a query to all the P2P networks they belong to. Modeling and analysis of the resulting interconnected system is crucial to design efficient and effective search algorithms and to control the cost of interconnection. Yet, simulation and/or prototype deployment based analysis can be very difficult - if not impossible - due to the size of each component (we consider large scale systems that can be composed of millions of nodes) and to the complexity arising from the interconnection of several such complex systems. To overcome this strong limitation, we developed a generalized random graph based model that is validated against simulations and it is used to investigate the performance of search algorithms for different interconnection costs and to provide some insight in the characteristics of the interconnection of a large number of P2P networks.

Streaming services have grown rapidly in the last few years and providers of video on-demand, such as Netflix or YouTube, are increasing the number of users even more quickly. The majority of these companies implement their services using huge Content Delivery Networks that are as much powerful as expensive, e.g. Amazon and Akamai. In this paper we propose a hybrid CDN/P2P solution that aims at reducing the infrastructural costs exploiting local caching and P2P while guaranteeing an optimal quality of service. The proposed architecture uses a classic CDN complemented by a geographically distributed layer where P2P can be activated exploiting network, content awareness and locality. The performance of the proposed solution is evaluated by means of a prototype implementation that has been deployed using the PlanetLab network and the Amazon AWS cloud services. Our findings show that the proposed approach provides adaptive, flexible, scalable and content centric service to the end users while significantly reducing the infrastructural costs.

Rateless codes are designed to decode all the input symbols when a certain number of coded symbols have been received. However, it is possible to recover a subset of the input symbols from the actually received coded symbols: this process is called partial decoding and the number of recovered input symbols is termed the intermediate performance of rateless codes. In this paper we study the problem of the optimality of the partial decoding process: we say that a partial decoding algorithm is optimal if, given a rateless code, it is able to maximize the intermediate performance of the code, i.e. it is able to retreive the maximum number of input symbols when a certain number n of coded symbols have been received, for every n. We propose OPD, an optimal partial decoding algorithm for any rateless code, proving its optimality. The proposed algorithm is finally used to analyze the intermediate performance of LT codes.

In this paper, we propose a generalization of the basic flooding search strategy for decentralized unstructured peer-to-peer (P2P) networks. In our algorithm a peer forwards a query to one of its neighbors using a probability that is a function of the number of connections in the overlay network of both. Moreover, this probability may also depend on the distance from the query originator. To analyze the performance of the proposed search strategy in heterogeneous decentralized unstructured P2P networks, we develop a generalized random graph (GRG)-based model that takes into account the high variability in the number of application level connections that each peer establishes, and the nonuniform distribution of resources among peers. Furthermore, the model includes an analysis of peer availability, i.e., the capability of relaying queries of other peers, as a function of the query generation rate of each peer. Validation of the proposed model is carried out comparing the model predictions with simulations conducted on real overlay topologies obtained from crawling the popular file sharing application Gnutella.

In this paper we present ToroVerde, a novel push-based peer-to-peer (P2P) content distribution application exploiting the digital fountain concept through the use of rateless codes. We provide the protocol specification, then describe the simulator and the complete prototype we have developed for Planetlab deployment and testing. To this end, we consider flash crowd and steady arrival patterns as well as highly churning systems to perform a preliminary analysis of the potential advantages of introducing rateless codes. We present results from PlanetLab experiments compared against performance of BitTorrent, that is widely considered as the reference system for content distribution. We also present a few simulation results showing the behavior of ToroVerde as the number of peers in the systems increases. Our results suggest that ToroVerde has the potential of reducing the average download time for small-to-medium sized files in overlays composed of a few hundred peers with a small increase of the communication overhead.

In this paper we face the following problem: how to provide each peer local access to the full information (not just a summary) that is distributed over all \emph{edges} of an overlay network? How can this be done if local access is performed at a given rate? We focus on \emph{large and sparse} information and we propose to exploit the compressive sensing (CS) theory to efficiently collect and pro-actively disseminate this information across a large overlay network. We devise an approach based on random walks (RW) to spread CS random combinations to participants in a random peer-to-peer (P2P) overlay network. CS allows the peer to compress the RW payload in a distributed fashion: given a constraint on the RW size, e.g., the maximum UDP packet payload size, this amounts to being able to distribute larger information and to guarantee that a large fraction of the global information is obtained by each peer. We analyze the performance of the proposed method by means of a simple (yet accurate) analytical model describing the structure of the so called CS sensing matrix in presence of peer dynamics and communication link failures. We validate our model predictions against a simulator of the system at the peer and network level on different models of random overlay networks. The model we developed can be exploited to select the parameters of the RW and the criteria to build the sensing matrix in order to achieve successful information recovery. Finally, a prototype has been developed and deployed over the PlanetLab network to prove the feasibility of the proposed approach in a realistic environment. Our analysis reveals that the method we propose is feasible, accurate and robust to peer and information dynamics. We also argue that centralized and other distributed approaches, i.e., flooding and gossiping, are unfit in the context we consider.

This paper presents TURINstream, a novel P2P video streaming architecture designed to jointly achieve low delay, robustness to peer churning, limited protocol overhead, and quality-of-service differentiation based on peers cooperation. Separate control and video overlays are maintained by peers organized in clusters that represent sets of collaborating peers. Clusters are created by means of a distributed algorithm and permit the exploitation of the participant nodes upload capacity. The video is conveyed with a push mechanism by exploiting the advantages of multiple description coding. TURINstream design has been optimized through an event driven overlay simulator able to scale up to tens of thousands of peers. A complete prototype of TURINstream has been developed, deployed, and tested on PlanetLab. We tested our prototype under varying degree of peer churn, flash crowd arrivals, sudden massive departures, and limited upload bandwidth resources. TURINstream fulfills our initial design goals, showing low average connection, startup, and playback delays, high continuity index, low control overhead, and effective quality-of-service differentiation in all tested scenarios.

The goal of this paper is the development of network coding solutions able to improve the performance of video streaming applications over peer-to-peer overlays. Recent advances in P2P protocols have shown that rateless codes can be profitably applied to P2P video streaming with several advantages in terms of protocol efficiency and simplification, e.g. push based video delivery, no need of packet reconciliation at the decoder. In this paper existing and novel network coding techniques based on rateless codes are presented and compared, showing that rateless codes, besides simplifying the protocol design, can significantly reduce the startup and playback delays. The proposed protocol is evaluated on real topologies, obtained by crawling the widespread PPLive video streaming application. The reported experimental results show that the proposed protocol significantly reduces the startup and playback delay and allows one to increase the bitrate devoted to the video stream.

The P2P-IPTV is an emerging class of Internet applications that is becoming very popular. The growing popularity of these rather bandwidth demanding multimedia streaming applications has the potential to flood the Internet with a huge amount of traffic. In this paper we present an investigation of the popular P2P-IPTV application PPLive exploiting a measurement strategy that combines both active and passive measures. To this end, we use a crawler that allows the study of the topological characteristics of the overlay of one of the PPLive channels; concurrently, we perform passive measures on a PPlive client we run to join the crawled channel. We successively cross correlate information we obtained from the two measurements to assess the accuracy of the data captured by the crawler. Our results reveal the potentials and the limits of PPLive active measures strategies.

Abstract This paper develops a directed generalized random graphs based analytical modeling framework to compare several variations of the basic flooding search strategy in unstructured decentralized peer‐to‐peer networks. To validate the model predictions, we designed and implemented a distributed crawler architecture that is able to efficiently capture snapshots of the top‐level Gnutella overlay topology. The snapshots are used to obtain simulation results that are used to assess the accuracy of our model. The model predictions are then used to compute system‐oriented performance indexes (the average and the coefficient of variation of the number of query messages) as well as user‐oriented measures (the probability of finding at least one replica of a resource, the average search time). The trade‐off between the optimization of system‐oriented measures and the improvement of user‐oriented quality indexes is investigated for several variations of the basic flooding strategy suggesting that adding control parameters to the basic flooding mechanism might prove beneficial in this class of systems. Copyright © 2007 John Wiley & Sons, Ltd.

We focus on a vehicular network supporting safety applications, and we present an application and a channel access mechanism for efficient multihop broadcasting. We study the performance of the proposed solution by developing an analytical framework, which provides several metrics relevant to message dissemination. Analytical results are compared with the performance obtained through ns

This paper exploits a previously developed analytical modeling framework to compare several variations of the basic flooding search strategy in unstructured decentralized peer-to-peer (P2P) networks. The model predictions are used to compute system-oriented performance indexes (the average and the coefficient of variation of the number of query messages) as well as user-oriented measures (the probability of finding at least one replica of a resource, the average search time). The trade-off between the optimization of system-oriented measures and the improvement of user-oriented quality indexes is investigated for several variations of the basic flooding strategy suggesting that adding control parameters to the basic flooding mechanism might prove beneficial in this class of systems.

This paper presents an application of basic concepts of statistical physics to devise an approximate model describing the dynamics of large peer-to-peer networks, based on fluid-diffusive equations. The model we propose is quite general and highly modular, and allows to represent several effects related to resources distribution among peers, user behavior, resource localization algorithms and dynamic structure of the overlay topology. Since the complexity of the model is largely independent of the system size, it provides a viable alternative to Montecarlo approaches for the analysis of very large P2P systems.

The behavior of large-scale wireless sensor networks has been shown to be surprisingly complex and difficult to analyze, both by empirical experiment and simulation. In this paper we develop a new analytical model of the behavior of wireless sensor networks, based on a fluid approach, i.e., we represent the sensor network by a continuous fluid entity distributed on the network area. The model accounts for node energy consumption, channel contention, as well as traffic routing; thus, it is well suited for describing the properties of sensor networks and understanding their complex behavior.

In order to cope efficiently with the dependability analysis of redundant systems with replicated units, a new, more compact fault-tree formalism, called Parametric Fault Tree (PFT), is defined. In a PFT formalism, replicated units are folded and indexed so that only one representative of the similar replicas is included in the model. From the PFT, a list of parametric cut sets can be derived, where only the relevant patterns leading to the system failure are evidenced regardless of the actual identity of the component in the cut set. The paper provides an algorithm to convert a PFT into a class of High-Level Petri Nets, called SWN. The purpose of this conversion is twofold: to exploit the modeling power and flexibility of the SWN formalism, allowing the analyst to include statistical dependencies that could not have been accommodated into the corresponding PFT and to exploit the capability of the SWN formalism to generate a lumped Markov chain, thus alleviating the state explosion problem. The search for the minimal cut sets (qualitative analysis) can be often performed by a structural T-invariant analysis on the generated SWN. The advantages that can be obtained from the translation of a PFT into a SWN are investigated considering a fault-tolerant multiprocessor system example.

The increasing complexity of automation systems, which combine high functional, real-time and fault-tolerant requirements, demands for techniques and tools to support design choices and validation phases. In this paper we investigate the possibility of using a class of high-level stochastic Petri nets known as stochastic well-formed nets (SWN) as a framework for specifying and deriving quantitative properties of FT mechanisms used in (electric) plant automation. A temporal redundancy technique adopted in several plants is taken as a case-study.

Colored Petri nets are a powerful formalism for the description of complex, asynchronous distributed systems. They can express in a very concise way the behavior of very large systems, especially in case these systems are composed of many replications of a few basic components that individually behave in a similar way. The simulation of such models is, however, difficult to perform in a computationally efficient way. For the specific class of stochastic well-formed nets (SWNs), we present a set of optimizations that allow a very efficient implementation of the event-driven simulation technique. Three approaches are followed to improve simulation efficiency: first, an efficient algorithm for the computation of the occurrences of a transition in a given marking; second, reduction of the amount of work needed to schedule or preempt the occurrence of a transition as a consequence of a marking change, taking into account the restrictions on color functions for the SWN formalism; third, reduction of the average length of the event list in the case of symmetric models where the so-called symbolic simulation technique applies. The approach is validated by performance measurements on several large SWN models taken from the literature.