Rossano Gaeta

Marco Grangetto

Riccardo Loti

Exploiting rateless codes and belief propagation to infer identity of polluters in MANET

Keywords: MANET, rateless codes, belief propagation, pollution attack, malicious node identification, statistical inference

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.

INTRODUCTION

Mobile Ad-hoc Networks (MANET) are characterized by open, distributed and dynamic architectures, built on top of the shared wireless medium; all features contribute to make MANET very vulnerable to attacks at any layer of the Internet model [START_REF] Wu | A survey of attacks and countermeasures in mobile ad hoc networks[END_REF], [START_REF] Yang | Security in mobile ad hoc networks: challenges and solutions[END_REF].

We consider a particular type of active, noncryptography related attack, where insider nodes corrupt data at the application level (this is also known as pollution attack). In this paper we deem as a use case a data dissemination application over a MANET. Nodes generate data chunks to be disseminated to all participants using rateless codes; some malicious nodes deliberately modify coded packets of a chunk before relaying them to prevent honest nodes from obtaining the original information.

In this paper we propose SIEVE a decentralized, accurate and robust technique to identify malicious nodes on top of an otherwise reliable and attacker-free architecture. Each node in SIEVE dynamically creates a bipartite graph (factor graph) whose vertexes are checks and uploading nodes. A check is a report created by a node upon decoding a data chunk; a check contains a variable length list of nodes identifiers that provided parts of the data as well as a flag to signal if the data chunk has been corrupted. Detection of the compromised chunks is achieved exploiting the constraints imposed by linear channel coding. The factor graph is periodically and independently analyzed by each node running an incremental version of the Belief Propagation (BP) algorithm [START_REF] Pearl | Probabilistic reasoning in intelligent systems: networks of plausible inference[END_REF], [START_REF] Mackay | Information Theory, Inference and Learning Algorithms[END_REF], [START_REF] Yedidia | Constructing free-energy approximations and generalized belief propagation algorithms[END_REF], [START_REF]Understanding belief propagation and its generalizations[END_REF]. The proposed algorithm allows each node to compute the probability of any other node being malicious; these latter probabilities are used to derive a suspect ranking of nodes in the MANET. Each node updates its local factor graph using the checks obtained by its own decoding operations as well as checks that are periodically gossiped by neighbor nodes.

Our contributions

The major contributions of the paper are the recasting of the problem of malicious nodes identification in terms of the estimation of the marginal probabilities on a bipartite graph and the proposal of a decentralized and accurate solution based on the BP algorithm. It is worth pointing out that the selected data dissemination application is just a quite popular use case [START_REF] Schierl | Rateless scalable video coding for overlay multisource streaming in manets[END_REF], [START_REF] Syrotiuk | Rateless forward error correction for topology-transparent scheduling[END_REF], whereas the proposed approach is by no means constrained to a single scenario. In particular, SIEVE can be used in any application that uses multi-party download or collaboration, provided that is possible to detect that a given set of collaborating entities is compromised by at least one malicious node. As opposed to cryptographic/algebraic techniques proposed in the area of network coding based wireless mesh networks, e.g., [START_REF] Agrawal | Homomorphic macs: Mac-based integrity for network coding[END_REF], [START_REF] Dong | Practical defenses against pollution attacks in intra-flow network coding for wireless mesh networks[END_REF], [START_REF] Li | Ripple authentication for network coding[END_REF], [START_REF] Newell | Split null keys: A null space based defense for pollution attacks in wireless network coding[END_REF] SIEVE does not rely on verification tools to check the integrity of every coded block. In SIEVE the BP algorithm is used to infer the identity of the malicious nodes resting upon only on a simple pollution detection mechanism; as an example, in our reference scenario, pollution detection is achieved as a by product of the data dissemination protocol based on rateless codes. Furthermore, the aforementioned solutions may not be suitable for MANET since mobility is likely to affect key predistribution, routing mechanisms, attack behavior, etc. SIEVE fits well two key MANETs features that must be accounted for when devising any security solution: it is fully decentralized and does not rely on any infrastructure (as opposed to some solutions in the area of peer-to-peer streaming where special well known nodes are necessary, e.g., [START_REF] Wang | MIS: Malicious nodes identification scheme in network-coding-based peer-topeer streaming[END_REF]). Furthermore, SIEVE requires small computational, storage, and communication costs for implementation.

Paper contributions are completed by a comprehensive experimental investigation of SIEVE capabilities. Our analysis is carried out by detailed simulations using ns-3; we show that SIEVE is accurate in letting each honest node identify all malicious nodes under several scenarios. We analyze the sensitivity of SIEVE performance to the nodes speed and we stress test SIEVE under several deceiving actions, colluding attacks launched by malicious nodes, and increasing number of malicious nodes. We also discuss an interesting trade-off between rateless code efficiency and SIEVE performance. The SIEVE technique has been partially presented in [START_REF] Gaeta | SIEVE: a distributed, accurate, and robust technique to identify malicious nodes in data dissemination on manet[END_REF]. The current paper includes a richer set of experimental results and a more detailed analysis of the obtained performance indexes, worked out on a larger set of system settings.

The paper is organized as follows: Section 2 describes the system model we consider, Section 3 presents the SIEVE technique, Section 4 discusses the simulation methodology and the accuracy, reactivity, and robustness results we obtained, Section 5 summarizes other works related to SIEVE, finally Section 6 draws conclusions and outlines directions for future developments.

A USE CASE FOR SIEVE

In this paper we consider a MANET composed of N wireless nodes moving in a given area. A set of N source nodes periodically produces a new data chunk to be disseminated to all others once every h seconds. All nodes cooperate to the diffusion of the data chunks by running a distributed dissemination algorithm based on Luby Transform (LT) codes [START_REF] Luby | LT codes[END_REF]. Data is transmitted by source nodes using LT codes [START_REF] Luby | LT codes[END_REF]: a chunk (whose size in bytes is fixed and is denoted as S) is divided in K equally sized blocks. The source node then creates and forwards coded packets using LT codes [START_REF] Luby | LT codes[END_REF], combining random subsets of the K blocks; the size of each coded packet is S cb = S K .

LT codes

LT codes have been proposed in [START_REF] Luby | LT codes[END_REF] and represents one of the first embodiment of the class of rateless codes: these are a particular family of erasure codes where the rate is not fixed by design, so that the number of coded packets can be decided and changed on the fly. LT codes are rateless based on the binary Galois field GF(2), i.e., coded packets are computed with simple binary XOR of random subsets of the K original data blocks. In [START_REF] Luby | LT codes[END_REF] it is shown that selecting the number of blocks to be combined, termed as the packet degree d, according to the Robust Soliton Distribution (RSD) 1 , one gets optimal asymptotic decoding performance. By optimal performance we mean that the so called decoding overhead, i.e. the number of coded packets to be received in excess of K, turns to be negligible for asymptotically large K. In particular, the original chunk can be obtained by any node able to collect any set of M = K • (1 + ) coded packets (on average), where is defined as the code overhead. The decoding algorithm can be viewed as the solution of a system of linear equations with K unknowns (the K original data blocks) and M ≥ K equations. In [START_REF] Luby | LT codes[END_REF] it is shown that a simple method based on the recursive cancellation of equations corresponding to packets with degree 1, i.e. representing one original data blocks, guarantees the desired asymptotic performance.

LT based dissemination protocol

The rateless principle and randomness of LT codes is used for spreading data in the MANET by letting source nodes transmit novel coded packets that can be generated randomly and on the fly. A coded packet conveys the XORed payloads of the corresponding original packets as well as a header signaling the indexes of the combined packets. The original chunk can be obtained by any node able to collect any set of K • (1 + ) coded packets without requiring any coordination among the source nodes. In turn, whenever a node is able to successfully decode a chunk, it can behave as a new source for the chunk, generating and disseminating novel coded blocks.

In Fig. 1 the algorithmic steps of the LT based dissemination protocol implemented by a node are graphically sketched. Each node can simultaneously collect coded packets for different chunks; to this end a window based mechanism is used where the w r most recent chunks can be concurrently downloaded and progressively decoded. As soon as a given chunk is decoded (this event happens on average when K • (1 + ) coded blocks of the chunk have been buffered), the corresponding data blocks are moved into a buffer storing the w t data chunks that have been decoded most recently. A simple round robin scheduling policy is used on the transmitter side, where 1. RSD is derived by the Ideal Soliton Distribution and depends on two free parameters usually identified with constants c and δ . one of the data chunk is selected, a novel LT coded packet is encoded and transmitted. A new coded packet is transmitted every T tx ms using UDP over an 802.11g wireless communication interface yielding an average transmission range of r meters.

Malicious nodes

The proposed dissemination protocol is an example of a distributed and collaborative approach that has the potential to simplify and accelerate the spreading of the information in the MANET thanks to node mobility. On the other hand, few malicious nodes may try to break the system by polluting, i.e. modifying some coded packets. In this paper we assume that a subset of P < N nodes is composed of malicious nodes, that deliberately modify the payload of the coded packets to prevent honest nodes from correctly reconstructing the original chunk. In the presence of coding even a single corrupted coded packet can prevent an honest node from decoding the original chunk.

THE SIEVE PROTOCOL

SIEVE uses LT codes decoding mechanism to detect modified chunks and exploits the Belief Propagation (BP) algorithm [START_REF] Pearl | Probabilistic reasoning in intelligent systems: networks of plausible inference[END_REF] to identify malicious nodes.

LT codes verification mechanism

According to the dissemination strategy described in Sect. 2 every node keeps collecting from different uploaders sets of coded blocks corresponding to different chunks. LT codes can be exploited to detect if modified blocks have been collected without the need of any supplementary verification mechanism.

Indeed, a node is able to detect pollution as soon as an inconsistency is found in the solution of the underlying system of linear equations. In particular, according to the procedure [START_REF] Luby | LT codes[END_REF] the decoder keeps canceling out all the already known data packets. This is achieved by observing that a coded packet with a degree 1 equation represents a data packet in the clear. Such data packet can be simplified from all the incoming equations. Since LT codes have a certain overhead some coded packets that are linearly dependent on the ones received previously are always collected before successful decoding; this amount to the reception of some equations whose terms are all already known. As soon as this condition is met the LT decoder can check the consistency of the payload carried by the coded packet; in other words, the same linear combination must be obtained combining a set of already known packets. If this constraint is violated the whole chunk is recognized as corrupted. Please note that the receiver node is not able to identify the corrupted block(s) but only that at least one of them has been maliciously manipulated.

Check construction and reporting

SIEVE is based on the concept of checks that are reports created by nodes upon decoding a chunk. A check contains the list of the identifiers of nodes that provided coded blocks of a chunk and a flag to label such chunk as corrupted or not. A check describing a corrupted chunk is called a positive check while it is termed a negative check otherwise. Each nodes n maintains a list of all checks created that is denoted as L n .

Each node, besides accumulating the checks from its local decoding operations, gossips them in the neighborhood. Each node n in the MANET transmits its checks in two cases:

• as soon as n decodes a chunk it inserts it in L n and broadcasts it; • once every T s seconds n randomly selects Q checks in L n and transmits them.

Identification based on belief propagation

The checks in L n and all checks received by n are used to build a factor graph G n =(U, C, E). G n is a bipartite graph where the vertex set U is the set of uploader nodes, the vertex set C is the set of checks, and an undirected edge {i, I} ∈ E exists if and only if check I ∈ C depends on uploader i ∈ U.

In the following we will refer to the set of uploaders involved in check I as U I and the set of checks that node i contributes as an uploader as C i . An example of factor graph with four uploaders (circles) and two checks (squares) is show in Fig. 2. The factor graph can be progressively created while decoding the chunks. In Fig. 2 we assume that a node has decoded two chunks corresponding to two checks in its local factor graph. The filled square represents a positive check due to the detection of a modified chunk concurrently downloaded by three nodes (in the figure we assume that the rightmost node is malicious). The remaining check is a negative one, appended when a chunk has been decoded successfully. From the point of view of any decoding node, each uploader i can be in one of two hidden states x i = 1 or x i = 0, depending on whether uploader i is or is not a malicious node. Each check can report one of The problem of identifying the malicious nodes from a given number of checks can be recast as an inference problem. The goal of the inference is the estimation of the hidden state of the nodes, i.e. being malicious or not, given a set of observations corresponding to the checks. Each check can be interpreted as an accusation raised against a set of uploader nodes by a witness node. In this paper we adopt the BP algorithm [START_REF] Pearl | Probabilistic reasoning in intelligent systems: networks of plausible inference[END_REF], [START_REF] Mackay | Information Theory, Inference and Learning Algorithms[END_REF], [START_REF] Yedidia | Constructing free-energy approximations and generalized belief propagation algorithms[END_REF], [START_REF]Understanding belief propagation and its generalizations[END_REF], that has been used to solve a number of inference problems in many different fields, e.g., iterative channel decoding [START_REF] Gallager | Low-Density Parity-Check Codes[END_REF], Bayesian networks [START_REF] Pearl | Probabilistic reasoning in intelligent systems: networks of plausible inference[END_REF] and computer vision [START_REF] Freeman | Learning low-level vision[END_REF] to mention a few.

The BP algorithm can be used to estimate from the factor graph the so called variable marginals (P (x i )) i∈U , i.e. the probability of node i being malicious. BP is an iterative algorithm based on the exchange of probability estimates (also called messages or beliefs), along the edges of the bipartite graph G n . In case of a Bayesian network BP represents a closed-form solution for the marginals. Nonetheless, the same algorithm has proven to be a robust estimator for the variable marginals of general factor graph [START_REF] Yedidia | Constructing free-energy approximations and generalized belief propagation algorithms[END_REF], [START_REF]Understanding belief propagation and its generalizations[END_REF].

In our setting it is convenient to distinguish between two classes of messages: message from uploader i to check I, m x iI , that is meant to be the probability that uploader i is in state x, given the information collected via checks other than check I (C i \ I); message from check I to uploader i, m x Ii is defined as the probability of check I having value c I if uploader i is considered in state x and all the other uploader states have a separable distribution given by the probabilities

{m x i I : i ∈ U I \ i}.

The BP algorithm is based on iterative refinements of the check messages m x

Ii based on the current values of the node messages m x iI (check pass), followed by updating of m x iI as a function of m x Ii (node pass). For the first check pass the messages are initialized to the values m 0 iI = m 1 iI = 0.5, since we assume that no prior information on the number and identity of the malicious nodes is available.

The check pass is based on the estimation of the probabilities m x Ii as follows:

m x Ii = {x i :i ∈UI \i} P (c I |x i = x, {x i : i ∈ U I \ i}) i ∈UI \i m x i i I (1)
Equation ( 1) depends on the probability of observing a certain check value c I , given the states of the uploaders of such check.

Given that a check turns out to be positive as soon as at least one of the uploaders is a malicious node, we can write:

P (c I = 1|{x i : i = 1, . . . , k}) = 0, if x i = 0, ∀i 1, otherwise (2)
Analogously, observing that a check can be negative if and only if all the uploaders are not malicious, we get

P (c I = 0|{x i : i = 1, . . . , k}) = 1, if x i = 0, ∀i 0, otherwise (3)
Plugging the last two expressions into Equation ( 1) we can simplify the check pass computation as follows:

m x Ii =        i ∈UI \i m 0 i I if c I = 0, x = 0 0 if c I = 0, x = 1 1 -i ∈UI \i m 0 i I if c I = 1, x = 0 1 otherwise (4)
The next BP step is constituted by the updating of the probabilities m x iI , using information from previous computation in the checks (node pass), according to (5):

m x iI = I ∈Ci\I m x I i (5)
After any node pass it is possible to get an estimate of the marginal P (x i = x) according to:

P (x i = x) = I ∈Ci m x I i (6)
We recall that the probability estimates given by Equation ( 5) and ( 6) are not guaranteed to be normalized; in the practical implementation we use proper normalization constants to avoid numerical issues as suggested in [START_REF] Mackay | Information Theory, Inference and Learning Algorithms[END_REF].

To conclude, the BP algorithm initializes the values of m x iI , then keeps iterating using Equations ( 4) and [START_REF] Yedidia | Constructing free-energy approximations and generalized belief propagation algorithms[END_REF]. A reliable estimate of P (x i = x) is computed after a certain number of such iterations using [START_REF]Understanding belief propagation and its generalizations[END_REF]. In all the experiments reported in this paper 3 iterations have been used to strike a balance between estimation accuracy and complexity.

BP complexity

The computational cost of single message update using Equation (4) amounts to |U I | -1 multiplications, where operator | • | evaluates the cardinality of a set. Since messages are associated to each edge of the bipartite graph we can conclude that the overall check pass takes on average |E|(z U -1) multiplications, z U being the average number of uploaders per check.

Using the same reasoning from (5) one can compute the cost of the node pass as |E|(z C -1) multiplications, where z C is the average number of checks per node.

Analogously, the final estimate in [START_REF]Understanding belief propagation and its generalizations[END_REF] takes |E|z C multiplications.

Finally, taking into accounts all the BP steps and assuming 3 iterations the overall computational complexity amounts to 3(|E|(z U -1) + |E|(z C -1)) + |E|z C multiplications.

Incremental BP estimation

In the previous description of the BP we have assumed that the factor graph G n is known in advance and kept fixed for all the iterations. In practice this assumption is not met in the proposed scenario. Nonetheless, the proposed algorithm can be implemented using an incremental (or sliding window) approach as follows.

Each node n keeps receiving checks from the other ones and it is allowed to run the BP on G n every T seconds considering only the checks received and created in a time window of the past w seconds. At time t, depending on the checks stored during a time window w, an updated factor graph G n,t,w is obtained by removing the old checks and adding the new ones; then, the corresponding estimates P t,w (x i = x) are computed through BP. The belief values m x iI are initialized to 0.5 when the i-th node is met for the first time; then, the partial estimates of m x iI are stored in memory and propagated to all the iterations and computation windows where such values are needed.

After every BP estimation of P (x i = x), a list of suspect nodes is obtained by setting a threshold on the probability P t,w (x i = 1) ≥ η. Each node n keeps a counter for each of its uploader nodes i: the nodes in the list of suspects after the BP run have their counter increased by 1. Finally, a suspects ranking R n over uploader nodes is defined by sorting their counters in decreasing order. As an example, the first node in the suspects ranking at time t is the uploader that more often has been included in the list of suspects after all the BP runs performed up to time t.

RESULTS

In this section we describe the simulation methodology and the indexes we defined to evaluate the accuracy, reactivity, and robustness of SIEVE. In particular, we show how the structural properties of the factor graph G n and mobility impact the performance of SIEVE as well as how robust it is with respect to several deceiving actions operated by malicious nodes. Finally, we show a trade-off between coding efficiency and SIEVE accuracy.

Factor graph and performance

According to [START_REF] Luby | Improved low-density parity-check codes using irregular graphs[END_REF] when short cycles are absent in the factor graph G n it is best to have high degree nodes (i.e., uploaders that contribute to many checks) and low degree checks (i.e., checks obtained from a small number of uploaders). High degree nodes (both malicious and honest) tend to their correct marginal probability (P (x i )) i∈U (i.e. the probability of node i being malicious) quickly; on the other hand, the lower the number of uploaders in a check the more valuable the information it conveys.

Unfortunately, the actual factor graphs computed by nodes do contain cycles and it is well known that cycles in the factor graph negatively impact on the accuracy of the probability estimates yielded by the BP algorithm [START_REF] Luby | Improved low-density parity-check codes using irregular graphs[END_REF]. The shortest length of a cycle in a bipartite graph with at most one edge between any two nodes is 4 and is due to the presence of at least two common uploaders in a pair of checks, i.e. the cardinality of the intersection between the uploaders of a pair of checks is at least 2. If the cardinality of the intersection is x > 2, then each of the x 2 pairs defines one length 4 cycle. Equivalently, a cycle forms if any two nodes contributed to provide blocks of at least two common checks. It is easy to note that the higher the degree of nodes and/or checks the higher the number of cycles in the factor graph.

In this context, the benefits of high degree nodes and low degree checks are counter-balanced by the negative effects of cycles. Indeed, increasing the average number of checks per node improves the performance of the BP algorithm up to a point where the number of cycles increases too much and lowers the accuracy of the BP algorithm. Similarly, the benefits of a lower average check degree are offset by a high number of cycles.

Simulation methodology

The performance of SIEVE have been investigated by simulations using ns-3 version 3.12 [START_REF] Riley | The ns-3 network simulator[END_REF] on a Red Hat 4.4.6-3 machine using standard variable settings. In particular, we developed a node object implementing the sender and receiver functionalities according to the protocol described in Sections 2 and 3. The MANET is composed of N wireless nodes placed in a square area whose side length is l meters. Nodes move using different average speeds. N f ast nodes moving at V f ast m/s (e.g., cars, buses, motorcycles), N slow nodes at V slow m/s (e.g., pedestrian, bikes), and N still fixed nodes (e.g., sensors, relay stations, shops). As a consequence we have N = N f ast + N slow + N still . All non-fixed nodes movements are described by the same mobility model and moving nodes are randomly distributed across the simulation area at the beginning of the experiment. Still nodes are distributed on a grid to avoid clustering in a particular region. We used the ns-3 default transmission model composed of a propagation delay model (a constant value model) and a propagation loss model (based on a log distance model with a reference loss of 46.677 dB at a distance of 1 meter). Under these settings we derived the maximal transmission range r as 175 meters.

We conducted simulation experiments that terminate after 1 hour of simulated time. We used the independent replication method to obtain N EXP = 30 executions and computed 95% confidence intervals. Each execution is obtained with different streams of the random number generator provided by ns-3. The simulation output is made of a log file containing all checks received by each node that is post-processed by our analysis software to run the SIEVE protocol to detect malicious nodes.

All results have been obtained by setting as initial data sources only the N still still nodes; all N nodes contribute to the spreading of the information according to the policy described in Section 2. A subset of nodes (P = P f ast + P slow + P still < N ) are simulated as malicious nodes that modify the coded packets. All the system parameter values of the reference scenario considered in the following are summarized in Table 1.

Performance indexes

For each node n in the system we define: time to identify at least x malicious nodes in the top x positions of R n . In each independent replication trial we compute the following averages:

• p(n) an
• c (i) (t) = N n=1 p(n)cn(t) N n=1 p(n) , i.e.
, the fraction of honest nodes that detected the attack and have a non empty R; (t) , i.e., the average accuracy of honest nodes with non empty R. When a (i) (t) = 1 it means that all honest nodes with non empty R have correctly identified all malicious nodes.

• a (i) (t) = 1 P N n=1 p(n)cn(t)an(t) N n=1 p(n)cn
• tsi (i)

(x) = N n=1 p(n)(t n,hit (x)-tn,trigger) N n=1 p(n)
, i.e., the average time honest nodes require to unambiguously identify x malicious nodes. Finally, we computed averages and 95% confidence intervals over N EXP executions and considered c(t), a(t), and tsi(x) that we call completeness, accuracy, and time to identification, respectively. In all computations we set η = 0.99 (η is the threshold on the probability P t,w (x i = 1) for suspect identification) and iterated each run of the BP algorithm on a specific factor graph three times.

Sensitivity results

The first analysis we conducted is on the sensitivity of c(t), a(t), and tsi(x) to parameters w, T , T s , and Q used by SIEVE as defined in Section 3. To this end we considered integer multiples of 10s values for w ranging from 10s to 90s, T = {5, 10}s, T s = {5, 10, 15}s, and Q = {5, 10}. We analyzed all 108 combinations and observed that SIEVE performance is most sensitive to the value w.

Figure 3 shows the performance indexes a(t), c(t), and tsi(x) for some values of w, when T = T s = 10 s and Q = 10 (all 108 configurations yielded similar results so we selected a representative set of curves). It can be noted that too small or too large values for w yield the worst performance for all the performance indexes. Indeed, small window sizes do not allow the factor graph to include enough checks and nodes to accurately infer the node status; on the other hand, large values of w provide more checks and nodes in G n but increase the number of cycles in the factor graph which in turn impact on the accuracy of the probability estimates yielded by the BP algorithm, as discussed in Section 4.1.

We summarized the structural properties of G n in Table 2. It can be noted that the average number of nodes per check z U is not dependent on w (it mostly depends on the overall number of nodes, the mobility patterns, and the data exchange protocols). On the contrary, the size of G n (|C| and |U|) increases as w increases although the number of nodes saturates since it is upper bounded by N . Accordingly, the average number of checks per node z C increases and it positively impacts on SIEVE accuracy up to the value w = 60; for larger values the average number of cycles in the factor graph increases and nullifies the increase of z C .

It can also be noted that c(t) approaches 1 after about 4 minutes; the behavior of c(t) clearly depends on the delay after which a node has collected a sufficient amount of checks to start its own suspect ranking. As for SIEVE reactivity, we observe that w = 60s yields the lowest values for the time to identification tsi(x) (all graphs for tsi(x) are computed for the maximum x such that for each honest node n it is true at the end of the simulation experiment that r n = x). Based on the above discussion on the impact of w on the performance of SIEVE, we selected w = 60s as the value for all the following experiments.

Figure 4 shows a comparison among different choices of the values for parameters T , T s , and Q (please recall that each node executes a BP estimation once every T seconds and transmits a selection of Q checks once every T s seconds). In particular, we selected three settings for three different values of the number of checks transmitted per seconds ( Q Ts = 2, 1, 0.33). It can be noted that performance of SIEVE achieve their best when the BP estimation is run more frequently (T = 5s) and the the number of checks transmitted per seconds is the highest. Nevertheless, improved performance come at the cost of increased computation and communication burden on nodes; this may cause concerns for battery operated nodes whose lifetime could be shortened. Based on the above reasoning, we selected a compromise between performance and energy consumption awareness using the following setting for the rest of the paper: w = 60s, T = T s = 10s, Q = 10.

Mobility and SIEVE performance

The first interesting observations we made is that mobility affects SIEVE performance. In particular, the performance depends not only on the speed but also on the mobility model adopted for nodes.

Figure 5 shows the performance of SIEVE in the reference scenario with different mobility models available in ns-3, i.e. 2D random walk, random direction, Gauss-Markov and steady state random waypoint; clearly, all mobility models have been compared for the same node speeds. It can be noted that the 2D random walk mobility model selected for the reference scenario yields slightly worse performance with respect to other mobility models that more closely represent mobility in a urban environment.

Figure 6 shows the performance of SIEVE in the reference scenario but averaged over nodes in the same speed class (fast, slow, still). It can be noted that accuracy of fast nodes is higher with respect to slow and still nodes. Reaction times are also lower for fast moving nodes.

Figure 7 shows the overall performance of SIEVE in the reference scenario and in scenarios with different mixes of fast and slow nodes. The system where all moving nodes are fast yields much higher accuracy and much lower reaction times with respect to other extreme case where all nodes move slowly. Nevertheless, SIEVE accuracy is 0.83 at the end of the one hour long experiments and approaches 1 for longer runs.

Figure 8 shows results in the reference scenario and in scenarios where all malicious nodes are either fast or slow. This results show that malicious nodes can delay their identification if they move slowly; on the other hand if all malicious nodes move fast all of them are quickly identified.

Although SIEVE is able to identify all malicious nodes in the long run in any setting, in all three cases we can conclude that high speed is key to obtain both high accuracy and low reaction delays by honest nodes.

Why is higher speed beneficial for SIEVE performance of honest nodes but detrimental for malicious nodes? Consider the case where different mixes of fast and slow nodes (Figure 7) are compared and assume an extreme scenario composed of all still nodes. Since nodes do not move it is possible to define a static geometric graph O describing connections among nodes where vertexes are nodes and an undirected edge between two vertexes exists if the corresponding nodes are within the transmission radio range r. For any node n ∈ O let N (n) denote the set of nodes connected to n (the neighborhood of n).

Consider one data source s and a chunk c; clearly, when s has transmitted K • (1 + ) coded packets, c is decoded by all nodes in N (s); in turn, these nodes start transmitting fresh coded packets for c and, if O is connected, all nodes will be able to decode c after some time. It can be noted that all coded packets produced by s will follow the same paths in O. This means that for any node n ∈ O chunks originating from s will be provided to n by the same set of uploaders U s (n) that is a subset of N (n). Of course, the same reasoning is valid for all checks describing chunks produced by any data source other than s. The final effect is that the set of checks created by each node n upon decoding chunks (L n ) is such that strong intersections exist among the uploaders of different checks (given that O is static and N (n) does not change over time); this translates into a high number of short cycles in the factor graph used by SIEVE that is a well known cause of poor performance of the BP algorithm, as discussed in Section 4.1.

Instead, when nodes move the geometric graph O becomes dynamic, i.e., for any node n its N (n) varies with time. Speed translates into higher rate of changes in N (n) that, in turn, reduces the number intersections among the uploaders of different checks (hence of short cycles in G n ) and increases the accuracy of BP algorithm. For the reference scenario we computed the structural properties of G n that are summarized in Table 3. It can be noted that the average number of nodes per check (z U ) and the average number of checks per node (z C ) for still nodes would suggest better performance with respect to fast and slow nodes. Nevertheless, the average number of length four cycles is much higher for still nodes and this is the main reason for worse performance.

Deceiving actions and SIEVE robustness

Besides following the data dissemination and SIEVE protocols, malicious nodes may also implement disturbing actions aiming at preventing or delaying their identification. In the following a number of deceiving actions are investigated.

• Reduced pollution intensity at the coded packet level: a malicious node modifies a coded packet with probability p poll (the reference scenario is analyzed with p poll = 1). Figure 9 shows how SIEVE performs when nodes lower their pollution intensity to p poll = 0.5, 0.25, 0.125 in the attempt of making their identification harder. It can be noted that SIEVE is able to spot malicious nodes in all cases although very low pollution intensities delay identification. Nevertheless, it is worth pointing out that tuning the pollution intensity yields a natural trade-off between speed of identification and average damage caused to honest nodes, i.e., the lower p poll the lower the number of polluted chunks and the longer the time to identification. • Reduced pollution intensity at the chunk level: a malicious node pollutes a chunk with probability c poll and the corresponding coded packets are modified with probability p poll . In Figure 10 we show results for c poll = 0.75, 0.5 and p poll = 1, comparing them to the reference scenario (analyzed with c poll = p poll = 1 ). Also in this case, we observe that malicious nodes are identified by SIEVE albeit at the price of some delay for low values of c poll . • Check status falsification: with probability p lie a positive check obtained by a malicious node is forwarded as negative and viceversa. Figure 11 shows that this trick is ineffective: indeed, the only effect is a limited increase in the values of tsi(x). Figure 12 also shows that SIEVE is able to achieve high accuracy even in extreme cases when half of the moving nodes is malicious. Indeed, provided that the system operates for long enough time, SIEVE is able to allow every node to identify all existing malicious nodes. • Honest nodes disparaging: malicious nodes always produce dummy positive checks involving a set of honest nodes. In this case malicious nodes flip a coin and, with probability p disparage , they replace the actual uploaders of a check with a set of honest nodes; the detection flag is marked as positive. Figure 13 shows SIEVE performance when p disparage = 1 and honest nodes are either randomly chosen or chosen in the same fixed order followed by all malicious nodes (this is a colluding attack to honest nodes).

It can be noted that, by colluding, malicious nodes only succeed in slightly delay their identification. As a matter of fact, SIEVE is able to correctly identify all malicious nodes anyway at the end of the simulation experiments.

• Increasing the number of malicious nodes: the last stress test for SIEVE is to consider its performance for an increasing number of malicious nodes that coordinate to launch the colluding attack. In Figure 14 we show results for up to P = 100 malicious nodes in the system (in all cases, P f ast = P slow = P 2 ). It can be noted that SIEVE reaches high accuracy at the end of the simulation experiments with an increase of the tsi(x) values, provided that the system runs for a long enough time.

Coding efficiency vs. SIEVE performance

Coding efficiency is defined as the capability of decoding with the smallest possible overhead . It is well known that LT codes overhead decreases as K increases [START_REF] Luby | LT codes[END_REF]; therefore high values of K are preferred in most cases. We compared the SIEVE performance for different values of K and S cb to keep the chunk size constant; in particular, Figure 15 shows results for K = 50, S cb = 1000 and K = 200, S cb = 250. It can be noted that small values of K yield better accuracy and lower reaction times. four cycles.

As a side effect of using a smaller value for K, the probability of receiving a coded packet from a malicious node is lower as confirmed by the attack damage, i.e., the average fraction of corrupted decoded chunks, that is equal to 0.20 for K = 50 and 0.33 for K = 200.

Bandwidth, memory and CPU costs

The bandwidth overhead required by a node to implement SIEVE is determined by the number of bits necessary to transmit a check when decoding a data chunk plus the bits required by the broadcasting of Q checks every T s seconds. In our simulations a check I is represented by using a message whose payload size is equal to b I = 32|U I | + 1 bits; in this expression 32|U I | bits are required to store the node identifiers represented as integers and one bit is used for the chunk corruption flag.

From the simulations of the reference scenario, we measured an average value of the bandwidth overhead equal to 301 bps per node (95% confidence interval [193,408]). We also measured the average throughput, defined as the number of decoded bits (of data chunks) per second, that is equal to 20483 bps (95% confidence interval [13162,27803]). It follows that SIEVE communication overhead, defined as the ratio between bandwidth overhead and throughput, is limited to about 1.5%. It is worth noticing that one contribution to the bandwidth overhead depends on Q and T s and can therefore be traded-off. As an example, the SIEVE communication overhead for Q = 5 and T s = 15s (see Fig. 4) turns out to be about the 0.5%. One of the main requirements a solution for MANET must satisfy is to have a low computational and memory cost. We measured the average CPU time experienced to run SIEVE on a single factor graph in our C++ implementation on an Intel(R) Core i5 2.80GHz CPU: we obtained 25ms. Of course, MANET nodes do not have the same computational power of a desktop PC but newer CPUs equipping tablets and smart phones are reducing the gap, e.g., the ARM Cortex-A9 MPCore has up to 4 cores, 2 GHz clock, and 10,000 DMIPS.

Furthermore, storage requirements are very low: the average number of checks in G n for fast, slow, and still nodes is 435, 423, and 742, respectively. The average number of nodes in G n is equal to 227, 224, and 228, respectively. The factor graph must be represented as a dynamic undirected bipartite graph. Several data structures can be used. In our implementation for each check I (received during the last w seconds) we store the set of uploaders i ∈ U I , each one representing an arc of the factor graph (represented as the pair of identifiers (I, i)). Each node/check identifier is represented as a 32 bit integer; therefore, the number of bits for storing the factor graph is equal to 2 • 32 • |E| bits. In our experiments, the average number of arcs of the factor graph is equal to 3823, 3962, and 5790 (for fast, slow and still nodes respectively). It follows that the average memory requirements is equal to 30.5 kB, 31.7 kB, and 46.3 kB, respectively.

RELATED WORK

MANET are vulnerable to attacks at any layer of the Internet model [START_REF] Wu | A survey of attacks and countermeasures in mobile ad hoc networks[END_REF], [START_REF] Yang | Security in mobile ad hoc networks: challenges and solutions[END_REF]. In the area of network coding several efforts have been devoted to devise on-the-fly verification techniques carried out by participants [START_REF] Krohn | On-the-fly verification of rateless erasure codes for efficient content distribution[END_REF], [START_REF] Gkantsidis | Cooperative security for network coding file distribution[END_REF], [START_REF] Li | On the practical and security issues of batch content distribution via network coding[END_REF], [START_REF] Kamal | Signatures for network coding[END_REF], [START_REF] Yu | An efficient signaturebased scheme for securing network coding against pollution attacks[END_REF], [START_REF] Kehdi | Null keys: Limiting malicious attacks via null space properties of network coding[END_REF], [START_REF] Yu | An efficient scheme for securing xor network coding against pollution attacks[END_REF] to identify the sources of corrupted data. The major drawback of these elegant methods is the high computational costs for verification and the communication overhead due to pre-distribution of verification information. In [START_REF] Agrawal | Homomorphic macs: Mac-based integrity for network coding[END_REF], [START_REF] Dong | Practical defenses against pollution attacks in intra-flow network coding for wireless mesh networks[END_REF], [START_REF] Li | Ripple authentication for network coding[END_REF] previous works have been extended to limit the communication overhead and achieve high level of robustness to pollution in the context of network coding applied to static wireless mesh networks.

Error correction (and algebraic) approaches have been devised to deal with data corruption attacks in network coding [START_REF] Ho | Byzantine modification detection in multicast networks with random network coding[END_REF], [START_REF] Jaggi | Resilient network coding in the presence of byzantine adversaries[END_REF], [START_REF] Koetter | Coding for errors and erasures in random network coding[END_REF]; these methods introduce coding redundancy to allow receivers to correct errors but their effectiveness depends on the amount of corrupted information. Recently, [START_REF] Newell | Split null keys: A null space based defense for pollution attacks in wireless network coding[END_REF] has proposed an extension of previous work which aims at limiting the communication overhead required for verification of coded packets.

The data corruption attack we consider in this paper is a well-known plague in peer-to-peer streaming systems. Unfortunately, all solutions developed in that research are not easily adoptable in MANET. The work by Wang et al. [START_REF] Wang | MIS: Malicious nodes identification scheme in network-coding-based peer-topeer streaming[END_REF] proposes a detection scheme where each peer is able to detect receipt of corrupted blocks by checking the adherence of the decoded chunk to the specific formats of the video stream. Peers detecting polluted chunks send alert messages to the video server and the tracker. Upon receipt of an alert the server computes a checksum of the original chunk and disseminates it to all peers in the overlay. The checksum is used by peers to identify which uploader actually sent a corrupted block. Peers report their suspects to the server and a true polluters cannot lie (the authors develop a non repudiation protocol to ensure that peers cannot lie when reporting suspects to the servers). Sequence numbers are used to tag alerts to deal with cycles in the overlay. This solution requires a centralized monitoring and management point that is not available in MANET. Therefore, it is hard (if not impossible) to adapt in the context we consider in our work.

The work by Li and Lui [START_REF] Li | Stochastic analysis of a randomized detection algorithm for pollution attack in P2P live streaming systems[END_REF] presents a distributed detection algorithm and analyzes its performance. The technique is based on simple intersection operations performed by peers: each peer starts with a set of suspects that is equal to the entire neighborhood that is shrunk as long as chunks are downloaded from a random subset of uploaders independently chosen from the entire set of neighbors. The scheme allows malicious nodes to send corrupted blocks using a pollution probability. The technique is analyzed when the number of malicious nodes in the neighborhood is known in advance and an approximation is proposed when this quantity is unknown. The same approach has been also adopted in network coding wireless mesh networks [START_REF] Li | Identifying pollution attackers in networkcoding enabled wireless mesh networks[END_REF], [START_REF]Epidemic attacks in network-coding enabled wireless mesh networks: Detection, identification and evaluation[END_REF], where the analysis is restricted on the backbone network consisting of stationary (with minimal mobility) mesh routers. The technique is attractive thanks to its simplicity and fully distributed nature although performance deteriorates when multiple polluter exist. Nonetheless, the technique works when then neighborhood of a node does not vary with time. Also in this case a comparison with our work is quite difficult.

The work by Jin et al [START_REF] Jin | Detecting malicious nodes in peer-topeer streaming by peer-based monitoring[END_REF] proposed a monitoring architecture to build and maintain a reputation system that peers use to select neighbors. The focus of the paper is on reputation computation, storage and load balancing among monitoring nodes. The results show that the system is able to detect malicious nodes up to a certain degree of lies. Nevertheless, the technique relies on the assumption that each peer is able to compute the amount of corrupted blocks received by each uploader during a monitoring period. Unfortunately, this capability is not available in the system we consider in our work: the original chunk can only be obtained if there are no malicious nodes among the chunk providers and if corruption is detected the honest node only knows that at least one of the chunk providers is malicious. In this case, comparison with our work is simply not possible.

CONCLUSIONS

In this paper we have proposed the novel SIEVE technique for the identification of malicious nodes performing a pollution attack within a MANET. A data dissemination application based on the distribution of LT coded data packets has been considered as a use case, where malicious nodes aim at preventing the delivery of the information corrupting, i.e., polluting, coded packets. In turn, the reception of a single corrupted packet may break down the decoding of a whole data chunk. Fortunately, the LT decoding procedure can be used by each node to detect that a data chuck has been attacked; nonetheless, since parallel downloading form multiple nodes is used, such detection does not allow to identify the malicious nodes. This latter represents the core problem solved by SIEVE. In SIEVE node collaborations are represented by a bipartite graph linking nodes and detection opportunities, the checks. It is worth pointing out that such representation is quite general and can be used in many other collaborative scenarios other than the data dissemination use case analyzed in this paper.

SIEVE is a completely distributed technique that, using statistical inference based on the belief propagation algorithm, allows each node to independently analyze local snapshots of the bipartite graph of the collected checks to estimate the probability of nodes being malicious and to perform a progressive ranking of the suspect nodes. Our results, worked out using detailed ns-3 simulations, show that SIEVE is accurate in letting each honest node identify all malicious nodes under several scenarios. We have analyzed the sensitivity of SIEVE performance to the nodes mobility; we have discovered that SIEVE is very robust to several deceiving actions, colluding attacks launched by malicious nodes, and amount of malicious nodes inside the network. Future works will be focused in two main directions. From the one hand we will complete the design and experimentation of a full system to counteract an active attack within MANET, including both malicious node identification and their subsequent isolation or removal. The techniques adopted for the identification and the following removal of malicious nodes clearly require a joint and careful design to optimize the overall performance. The other research line will be devoted to better understand the features of the bipartite graph representation, e.g. presence of loops, average node and check degrees, that affect SIEVE accuracy. Such study is expected to let us further improve its performance by adding the checks in a smart and adaptive way guaranteeing better convergence of the BP algorithm.

Fig. 1 :

 1 Fig. 1: Node operations: LT encoding, decoding and dissemination protocol.

Fig. 2 :

 2 Fig. 2: Example of factor graph.

Fig. 3 :Fig. 4 :

 34 Fig. 3: Representative accuracy (left), completeness (middle), and time to identification (right) of SIEVE as a function of w.

Fig. 5 :

 5 Fig. 5: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different nodes mobility models.

Fig. 6 :Fig. 7 :Fig. 8 :

 678 Fig. 6: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different nodes speeds in the reference scenario.

Fig. 9 : 5 Fig. 10 :Fig. 11 :

 951011 Fig. 9: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different pollution intensities at the coded block level (p poll ).

Fig. 13 :Fig. 14 :

 1314 Fig. 13: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different disparaging attacks.

Fig. 15 :

 15 Fig. 15: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different values of K.

TABLE 1 :

 1 Parameter values for the reference scenario.

	Parameter	Description	Value
	N f ast , N slow	Number of fast/slow nodes	100
	N still	Number of still nodes	50
	P f ast , P slow	Number of fast/slow polluters	5
	P still	Number of still polluters	0
	K	Number of blocks	100
	S cb	Size of blocks	500 Bytes
	Ttx	Time between transmissions of	100 ms
		blocks
	c, δ	RSD parameters for LT encoder	0.01
	l	Square area side length	2000 m
	h	Time between data chunk gen-	600 s
		eration
	wr	Window size for concurrent	50
		chunk downloading
	wt	Window size for concurrent	6
		chunk uploading
	r	Maximal transmission range	175 m
	V f ast	Fast nodes speed	[10-40] m/s
	V slow	Slow nodes speed	[1-5] m/s
	-	Mobility model	2D RW

  indicator function whose value is equal to 1 if node n is not malicious and 0 otherwise; • c n (t) an indicator function whose value is equal to 1 if R n is non empty at time t and 0 otherwise; • a n (t) the number of actual malicious nodes correctly identified by node n at time t. More precisely, a n (t) = x if x nodes in the top P positions of R n are truly malicious; • r n (t) the number of actual malicious nodes correctly identified in the top positions of R n at time t. More precisely, r n (t) = x if top x nodes in R n are all actually malicious. If SIEVE at time t has identified P -1 out of P malicious nodes (a n (t) = P -1) but the first node in R n is not malicious then r n (t) = 0. • t n,trigger the time node n received the very first positive check that triggered the SIEVE activation; • t n,hit (x) = min t {t : r n (t) ≥ x}, that is, the minimum

TABLE 2 :

 2 Structural properties of G n for increasing values of w.

	w	|C|	z U	|U|	z C	length 4 cycles
	10	83.1688	8.53656	173.7	3.8633	1175.57
	30	247.617	8.55307	216.824 9.29914	8899.69
	60	492.807	8.5262	231.687 17.3395	32021.6
	90	735.944	8.49615	236.444 25.3386	68064.4

TABLE 3 :

 3 Structural properties of G n for different nodes speed in the reference scenario.

Table 4

 4 summarizes the structural properties of G n for different values of K. It can be noted K = 50 yields both lower average number of nodes per check and length

					Accuracy							Completeness						Time to safe identification
		1								1							3000	reference scenario
		0.8								0.8							2500			P=20 P=40 P=60
	a(t)	0.4 0.6				reference scenario P=20	c(t)	0.4 0.6			reference scenario P=20	TSI(x) (sec)	1000 1500 2000			P=80 P=100
		0.2					P=40 P=60 P=80		0.2					P=40 P=60 P=80		500
		0					P=100		0					P=100		0
		0	1000 2000 3000 4000 5000 6000 7000	0	50	100	150	200	250	300	0	0.05	0.1	0.15	0.2	0.25	0.3
					Time (sec)							Time (sec)						Fraction of malicious
	Fig. 12: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for p lie = 1 and increasing
	number of malicious nodes.
					Accuracy a(t)						Completeness c(t)						Time to identification tsi(x)
		1								1							700	no disparage
		0.8								0.8							600	random innocents same innocents
																	500
		0.6								0.6							400
		0.4								0.4							300
																	200
		0.2				no disparage random innocents		0.2			no disparage random innocents		100
		0				same innocents		0			same innocents		0
		0	500	1000	1500	2000	2500	3000	3500	0	50	100	150	200	250	300	0	1	2	3	4	5	6
					Time (sec)							Time (sec)							# malicious

TABLE 4 :

 4 Structural properties of G n for different values of K.


Vincenzo Ciancaglini

Rossano Gaeta

Riccardo Loti

Luigi Liquori

Interconnection of large scale unstructured P2P networks: modeling and analysis ?

Interconnection of multiple P2P networks has 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 forwarding a query to all the P2P networks they belong to. Modeling and analysis of the resulting interconnected system is crucial to design e cient and e↵ective search algorithms and to control the cost of interconnection. To this end, we develop a generalized random graph based model that is validated against simulations and it is used to investigate the performance of search algorithms for di↵erent interconnection costs and to provide some insight in the characteristics of the interconnection of a large number of P2P networks.

Introduction

The last decade has seen the rise of peer to peer networks with a variety of applications, such as file sharing, resource lookup, real time services, up to the most recent research in SmartGrids. Common issues which a↵ect all P2P systems, such as scalability, fault tolerance and security, arise from the di↵erent peculiarities each class of applications might expose. Increasing the locality properties of such systems, be it geographical, semantic, network, or social-based locality, is one of the most valued approaches to face such challenges: by grouping together peers representing users, and increasing their connections with one another, one can improve scalability, fault tolerance, and security (consider the possible creation of a "circle of trust" amongst nearby peers).

In this paper, we consider the interconnection of large-scale unstructured P2P networks by means of special nodes called Synapses [START_REF] Liquori | Synapse: A scalable protocol for interconnecting heterogeneous overlay networks[END_REF], which are co-located in more than one network, and act as connectors by sending or forwarding a query to some or all the P2P networks they belong to. Modeling and analysis of the resulting interconnected system is crucial to design e cient and e↵ective search algorithms and to control the cost of network interconnection. Yet, simulation and/or prototype deployment based analysis can be very di cult -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.

Our contribution

To overcome this strong limitation, we develop a generalized random graph based model to represent the topology of one unstructured P2P network, the partition of nodes into Synapses, the probabilistic flooding based search algorithms, and the resource popularity. We validate our model against simulations and prove that its predictions are reliable and accurate. We use the model to investigate the performance and the cost of di↵erent search strategies in terms of the probability of successfully locating at least one copy of the resource and the number of queries as well as the interconnection cost. We also gain interesting insights on the dependency between interconnection cost and statistical properties of the distribution of Synapses. Finally, we show that thanks to our model we can analyze the performance of a system composed of a large number of P2P networks. To the best of our knowledge, this is the first paper on model-based analysis of interconnection of large scale unstructured P2P networks 3 .

The paper is organized as follows: Section 2 describes our system, Section 3 presents the mathematical derivation of the generalized random graph model we develop, Section 4 contains model validation through simulation, as well as model exploitation to study the performance of three search algorithms, Section 5 discusses related works, and in Section 6, we draw conclusions and outline ongoing activities that extend the current work.

System description

In this paper, we focus on unstructured P2P networks where peers organize into an overlay network by establishing application level connections among them. The topological properties of an overlay network are represented by the number of connections of any of its participants. To this end, we describe an overlay by means of the degree distribution {p k } that can be interpreted as the probability that a randomly chosen peer has k connections in the overlay ( P 1 k=1 p k = 1). We consider a set of X unstructured P2P networks that are interconnected thanks to a subset of peers that belong to multiple overlays (these special peers are denoted as Synapses). Any peer may then belong to i 2 {1, . . . , X} overlays: we denote i as the Synapse degree of a peer. The interconnected system is then described by {s i } (i 2 {1, . . . , X}) where s i is the fraction of peers belonging to i overlays ( P X i=1 s i = 1). The search algorithm we consider is flooding-based. A peer starting a search sends queries to a randomly chosen subset of its one-hop neighbors. These nodes forward the queries to a randomly chosen subset of their one-hop neighbors, excluding the query originator, and so on until the maximum number of allowed hops, i.e. the query time-to-live (TTL). A simple schema of interconnection through synapses and search is depicted in Fig. 1.

We also consider a variation of this search algorithm where a query is not forwarded by peers that own a copy of the resource. We focus on probabilistic versions of this general algorithm where any peer flips a coin before sending or forwarding a query to a specific neighbor. We allow the weight of this coin to be dependent on the Synapse degree of a peer; hence, a peer that belongs to i overlays sends/forwards a query to a particular neighbor with probability p f (i) (i 2 {1, . . . , X}). Please note that {p f (i)} (i 2 {1, . . . , X}) is not a probability distribution hence in general

P X i=1 p f (i) 6 = 1.
The goal of a search is to localize at least one resource related to the key we are looking for. There could be more replicas of the same resource hosted by di↵erent peers for two reasons: a resource is popular and/or is owned by peers located in di↵erent P2P networks. We represent resource popularity by 0  ↵  1, the average fraction of nodes that globally hold a copy of a given resource, and interpret it as the probability that a randomly chosen peer owns a copy of the resource.

System model

This section illustrates the random graph modeling approach to represent one overlay topology, the interconnection of X P2P networks, the search algorithm, and resource popularity as described in Section 2.

One overlay topology

Each P2P network is organized into an overlay that we model as a generalized random graph whose degree distribution is {p k } that can be interpreted as the probability that a randomly chosen peer has k connections in the overlay. The random graph degree distribution is a probability distribution therefore we consider its probability generating function (henceforth denoted as p.g.f.) that is equal to G 0 (z) = P 1 k=0 p k z k . To correctly characterize the neighborhood of a randomly chosen peer we also need to characterize the probability distribution of the number of connections of a peer reached by randomly choosing an edge of the overlay. This probability is proportional to the degree of the peer (kp k ) and it can be proved that its p.g.f. is given by

P k kp k z k P k kp k = z G 0 0 (z) G 0 0 (1)
where G 0 0 (z) denotes the first derivative of G 0 (z) with respect to z and G 0 0 (1) yields the average value of distribution {p k }. Finally, to characterize the number of connections excluding the edge we chose we obtain the p.g.f. G 1 (z) =

G 0 0 (z) G 0 0 (1)
. Starting from Equations defining G 0 (z) and G 1 (z) we can compute the p.g.f. for the number of two hops neighbors of a randomly chosen peer as G 0 (G 1 (z)). Similarly, the p.g.f. for three hops neighbor is given by G 0 (G 1 (G 1 (z))), and so on.

For a detailed overview on analyzing generalized random graphs using generating functions, we refer the reader to [START_REF] Newman | Random graphs with arbitrary degree distributions and their applications[END_REF].

Interconnection of multiple P2P networks

To interconnect multiple overlays we consider some peers as Synapses nodes: these peers belong to multiple P2P networks hence the interconnected system can be modeled by the probability distribution {s i } (with i 2 {1, . . . X}). The elements of this distribution describe the fraction of nodes belonging to multiple P2P networks: s i is the fraction of nodes that belong to k P2P networks. Its p.g.f. is given by F (z) = P 1 i=0 s i z i . If we consider one of the X P2P networks including the Synapse nodes then the p.g.f. for the number of connections of a randomly chosen peer can be written as

M (z) = s 1 G 0 (z) + s 2 G 2 0 (z) + . . . + s X G X 0 (z) = F (G 0 (z)
) that is, if the chosen node is a degree 1 synapse (this event has probability s 1 ) then the number of connections is represented by G 0 (z). If the node is a degree 2 synapse (this event has probability s 2 ), then the number of connections is represented by the sum of two independent random variables whose p.g.f. is G 0 (z); it is well-known that the generating function of the sum of two independent random variables is equal to the product of the respective generating functions yielding the G 2 0 (z) factor in the equation for M (z). The same reasoning is valid for synapses whose degree is greater than 2.

A similar expression can be written for the neighborhood of a node reached by following one randomly chosen edge excluding the selected edge:

N (z) = s 1 G 1 (z) + s 2 G 1 (z)G 0 (z) + . . . + s X G 1 (z)G X 1 0 (z) = G 1 (z) G 0 (z) F (G 0 (z)).
If we denote as N t (z) the p.g.f. for the probability distribution of the number of neighbors t hops away from a randomly chosen node we have that: N 1 (z) = M (z), and N 2 (z) = M (N (z)), and N 3 (z) = M (N (N (z))), and so on. From these p.g.f. the average number of neighbors can be computed by evaluating their first derivative w.r.t. z in z = 1.

As such, each probability distribution {s i } induces an interconnection cost that we define as the average number of P2P networks a randomly chosen node belongs to:

f = F 0 (1).
(1)

Search algorithm

To model a flooding-based search in the interconnected system, we consider the set of probabilities {p f (i)}, where i 2 {1, . . . X}. A peer belonging to i overlays sends/forwards a query to a particular neighbor with probability p f (i), where i 2 {1, . . . X}). Therefore, {p f (i)} is not a probability distribution. We denote as q h the probability that h first hop neighbors received a query from the peer that started the search. If the peer belongs to i overlays, it sends a query to one of its neighbors with probability p f (i). Therefore, the number of neighbors that receive the query follows a binomial distribution with parameter p f (i). Therefore, it is well known that the probability distribution {q h } has p.g.f. given by [START_REF] Newman | Random graphs with arbitrary degree distributions and their applications[END_REF]

Q(z) = P X i=1 s i G i 0 (1 + p f (i)(z 1)
). Similarly, for the p.g.f. of the probability distribution describing the number of queries sent by a node reached by following a randomly chosen edge, we obtain:

R(z) = X X i=1 s i G 1 (1 + p f (i)(z 1)) G i 1 0 (1 + p f (i)(z 1)). (2)
If we denote as Q t (z) the p.g.f. for the probability distribution of the number of neighbors t hops away from a randomly chosen peer that received a query, we have that:

Q 1 (z) = Q(z), Q 2 (z) = Q(R(z)), and Q 3 (z) = Q(R(R(z))),
etc. As a special case, we may consider constant forwarding probabilities, i.e. p f (i) = p f , 8i 2 {1, . . . X}. In this case, we would obtain:

Q(z) = M (1+p f (z 1)) and R(z) = N (1 + p f (z 1)
). Since the p.g.f. of the probability distribution of the sum of independent random variables is given by the product of the corresponding p.g.f., the total number of queries generated by a search issued by a randomly chosen peer is described by: T

(z) = Q T T L t=1 Q t (z) yielding the average number of queries m = T 0 (1). ( 3
)

Hit probability

We model resource popularity by 0  ↵  1 that is the average fraction of peers that globally hold the given resource. We interpret this parameter as the probability that a randomly chosen node owns a copy of the resource.

If we denote as w h the probability that h first hop neighbors hold a copy of the requested resource and received a query from a peer that belongs to i overlays we note that the number of such neighbors follows a binomial distribution with parameter ↵p f (i). If we denote as H t (z) the p.g.f. for the probability distribution of the number of neighbors t hops away from a randomly chosen peer that received a query and hold a copy of the requested resource then we have that:

H 1 (z) = Q 1 (1 + ↵(z 1)), H 2 (z) = Q 2 (1 + ↵(z 1)), H 3 (z) = Q 3 (1 + ↵(z 1
)), and so on. Therefore, the total number of search hits is described by a probability distribution whose p.g.f. is given by:

H(z) = Q T T L t=1 H t (z) yielding the search hit probability p hit = 1 H(0). (4)

A variation of the search algorithm

To model a search algorithm where peers that own a copy of the resource do not forward a query message it su ces to redefine R(z) in Equation 2. In particular, when a peer owns a copy of the resource the number of its neighbors that receive the query is equal to 0: this happens with probability ↵. In Equation 5this is represented by the term ↵ that can be written as ↵p 0 z 0 with p 0 = 1.

With probability 1 ↵ Equation 2 holds, therefore we obtain the p.g.f. of the probability distribution describing the number of queries sent by a node reached by following a randomly chosen edge as:

R(z) = ↵ + (1 ↵) X X i=1 s i G 1 (1 + p f (i)(z 1))G i 1 0 (1 + p f (i)(z 1)). ( 5
)
The definition of Q t (z), and T (z), and m remains unchanged.

Results

In this section, we will first show the results of the model validation, performed via a heavily multi-threaded simulator, written in Erlang, that reproduces, in terms of message routing, the exact behavior of a system described by our model. Also, we will show the results of some broad system evaluations made possible by the use of our model to compute metrics that would otherwise, if performed by means of simulations, require too much in terms of simulation time and computational power.

In our analysis, we consider di↵erent routing policies that can be employed in our scenarios, modeled by defining the p f (i) mentioned in Section 2. Those are:

-p f (i) = 1 i
, henceforth referred to as 1/i, i.e. the probability of selecting a neighbor is inversely proportional to the number of overlays a node is connected to. This routing tends to maintain a constant number of messages, but "flattens" the interconnected topology, not allowing synapse nodes to exploit the extended neighborhood.

-p f (i) = min(1, z max zi
), henceforth referred to as zmax, where z = E[{p k }] is the average number of neighbors for a node based on the current degree distribution and z max is a system parameter, specified upon design, indicating the upper bound for the average number of forwarded messages. This policy allows for a better exploitation of Synapse nodes, while still finely limiting the number of messages in the system. In our evaluations, z max has been set to 2z, twice the average number of neighbors per node.

p f (i) = 1, henceforth referred to as flood, i.e. a routing where every node selects forwards a message to every neighbor, regardless of the number of connected overlays.

In both simulations and evaluations, the individual overlays have been modeled following the neighbors degree distribution measured in [START_REF] Bolla | A measurement study supporting p2p file-sharing community models[END_REF] from real world applications and used already in [START_REF] Gaeta | Generalized probabilistic flooding in unstructured peerto-peer networks[END_REF], in order to have an accurate overlay model.

Model validation

In order to evaluate the accuracy of our model in predicting the performance indexes of a real network, we validated the obtained results by means of simulation. The simulator employs standard statistical procedures to estimate 68% and 95% confidence intervals for the p hit and m indexes defined in Section 3.

Simulation methodology

The simulator has been developed from scratch in Erlang. The choice of Erlang has been driven by its native multi-threading capabilities and inter-process communication model based on the message passing paradigm embedded in the language, thus allowing for a rapid implementation of an accurate network model made of node processes running independently and exchanging messages with one another. Each process has a list of other processes it can exchange messages with, that constitutes its neighborhood. We consider N s independent realizations for the interconnected overlay topologies (in our experiments N s = 30); each interconnected topology is used to obtain one realization of m and p hit . The h th realization is obtained as follows: -We first generate a new topology, made of X overlays interconnected by synapse nodes, using as input parameter the number of nodes N = 500000, the nodes degree distribution {p k } [START_REF] Bolla | A measurement study supporting p2p file-sharing community models[END_REF], and the {s i } to be validated; -From the generated topology file, the simulator instantiates N node processes and assigns each the corresponding list of neighbors; -One or more resources are then seeded in the system, according to their respective popularity ↵, by sending a PUT(value) message to N↵ random nodes; -Separate worker processes take care of sending a query message SEARCH(value,TTL)

to each node process in the network. -Meanwhile, a listener process receives then the responses, either the resource being found or the T T L being reached, and of computes the statistics. Topology generation The generation of a network made of interconnected overlays mainly consists of generating first X individual overlay topologies, and then connecting them by "merging" nodes from di↵erent overlays in one Synapse node, thus creating nodes with extended neighborhoods spanning across all the connected overlays. In order to generate X random graphs with a specified degree {p k } we relied on the algorithm presented in [START_REF] Viger | E cient and simple generation of random simple connected graphs with prescribed degree sequence[END_REF], that provides short generation times while guaranteeing the respect of the specified degree.

Validation results

The first validation we performed was conducted for a system with only one overlay (X = 1). For the sake of brevity we only show the results for the flood routing strategy, ↵ = 0.0001, and T T L = 3. Table 1 shows the model is very accurate and faithfully predicts results when compared to the simulation output.

We then validated various scenarios with a higher number of interconnected overlays (X = 4), at T T L = 3, 4 and with di↵erent values of ↵, di↵erent routing policies and di↵erent distributions {s i }. We considered the distribution for the degree of synapses summarized in Table 2.

Figure 2 (left) shows a comparison between the computed p hit for di↵erent values of ↵ and the corresponding simulation results, while Table 3 summarizes the same comparison for m. The results show that both performance metrics fall within the confidence interval of the simulation results.

Furthermore, we validate the system against the alternative search algorithm detailed in Section 3.5. For the sake of brevity, we are showing results only for S 2 since the same conclusions can be drawn for S 1 and S 3 . Figure 2 (right) shows both p hit and m against di↵erent values of ↵, since with this algorithm the number of message is dependent of the resource popularity. Even in this scenario, the model results fall within the confidence interval estimated by the simulator.

Therefore, we can safely conclude that our model is accurate in predicting the behavior of the performance indexes in a broad range of di↵erent scenarios. Furthermore, while simulations required hours of CPU time to complete solving our model took less than one second with a solver implemented in C.

Model exploitation

After validating the model we conducted a few analysis to show its usefulness in the design phase of the interconnection of several peer-to-peer networks.

Comparison of di↵erent routing policies A first evaluation concerns the choice of a specific routing policy in the system, i.e. the definition of di↵erent p f (i). In this case, we want to compare for values of ↵ down to 10 6 , the performances in terms of p hit and m for the distribution of degree of synapses S 1 (results for the other two distributions suggested similar considerations and are omitted for the sake of brevity), X = 10, and T T L = 3. Please note that to achieve a reliable measurement via simulation for ↵ = 10 6 we would need to conduct complex simulations (at least 1000000 nodes) for a long simulation time (ideally each of them to be queried individually for multiple topology realizations).

Figure 3 show the values of p hit for the 3 di↵erent policies and di↵erent resource popularities, while Figure 4 depicts the average number of messages for the 3 policies in the case of propagation of queries up to T T L hops (Figure 4b) and for the query propagation that stops when reaching a node holding a copy of the resource (Figure 4a) modeled in Section 3.5. In the former case, the number of messages is independent of the resource popularity while in the latter case we note that reduction of the number of query messages can be obtained for popular resources, i.e., for ↵ > 0.01.

In this case, the model allows for a simple cost/benefit evaluation, based on the expected popularity of a resource. For one, we can notice an almost tenfold increase in the number of messages between the zmax and the flood policy, to which it does not correspond a proportional increase in the p hit .

f -cost based evaluation In a cost/benefit analysis of the interconnected system, we consider p hit as our benefit metric whereas m and f are considered as costs. Another kind of evaluation we performed consists of fixing the f cost and analyzing which distributions {s i } lead to better performances (p hit ) and minimum cost (m).

To this end we considered all distributions {s i } that can be defined for X = 5 where the individual probabilities are non-zero multiple of 0.05. We considered 3 values of f (namely, f = 2, 3, 4) and compared the performances of every distribution {s i } with given f for T T L = 2. Again, please note that this analysis would have required days of CPU time to be completed by means of simulation since even with a coarse granularity in the definition of {s i } (0.05) we tested hundreds of di↵erent distributions. This analysis required only a few seconds to complete with our model.

Figures 5a and5b show a subset of these distributions (each point in the graph corresponds to a particular distribution {s i }). We only plotted the ones with the highest p hit ; it appears that the interconnection cost f alone is not directly bound to an increase in performances. There are, as a matter of fact, di↵erent configurations with f = 3 that perform equally (sometimes very slightly better) than those with a f = 4. Furthermore, within the configuration with f = 2 some are better than others in terms of performance and costs. Nevertheless, a clear relation exists between message cost m and p hit : the larger the average number of messages the higher the p hit . The behavior shown in the figures can be explained as following: the routing policy zmax limits the number of messages that can be issued by a node to z max , which is set in our evaluations to 2z. Therefore, increasing the number connections in the interconnected system (f ) beyond certain values does not lead to a significant performance increase. That is why we observe a proportionally higher increase in the p hit from f = 2 to f = 3 than from f = 3 to f = 4.

E↵ects of granularity Another aspect we analyze is a performance comparison as the number of overlays to interconnect increases. In this case we chose to analyze the behavior of the zmax routing policy, in a system with T T L = 3 and ↵ = 0.0001, for an increasing number of overlays (X) and for di↵erent distributions {s i }, characterized by an increasing percentage of non-synapse nodes s 1 , while the remainder of the distribution is equally distributed across the remaining s i .

Figures 6a and 6b

show four di↵erent configurations, with an increasing number of non-synapse nodes in the system. The parameter s 1 indicates the share of non synapses nodes, while the remaining part (1 s 1 ) is equally distributed among the remaining X 1 values, i.e., s i = 1 s1 X 1 for 1 < i  X. It can be noted that at each given ratio of synapses vs non-synapses nodes the system behavior is roughly the same regardless the number of overlays. The e ciency is still tightly bound to the number of messages and both increase as s 1 decreases.

System design with minimum requirements Thanks to the high number of di↵erent configurations that can be evaluated with our model in a relatively short time, we conduct a further analysis to support the design of the interconnection of several peer-to-peer networks.

For instance, we set the number of overlays X and the resource popularity ↵; by setting a bound for the minimum desired p hit , we can compare di↵erent routing policies and T T L values and find the one that minimizes the average number of messages m.

Figures 7 and8 (left) show a classification of distributions {s i } for two different routing policies and two di↵erent T T L values with respect to p hit and m for X = 10 and ↵ = 0.0001 (each point in the graphs represents a particular distribution {s i }). In the first case (Figure 7), we decided to fix a cost factor and set f = 4, whereas in the second case (Figure 8 left), the fixed factor is the ratio of expected non-synapse nodes in the system s 1 . We are able to discriminate immediately those distributions {s i } that do not satisfy the imposed criteria of having p hit > 0.9. We also discriminate among those that do the distributions {s i } that minimize the number of messages m, as shown in Figure 7b.

Routing without propagation

We briefly present some evaluation results based on the model variation presented in Section 3.5. In the first version of our model, the routing of a message is assumed to continue until the TTL expires, regardless of a resource being found or not. This leads to an H t (z) able to describe di↵erent cases, such as the probability of finding multiple copies of a resource. However the system is not optimal message-wise. In case we are interested only in the first hit of a search query, and we want to optimize the number of messages employed, with the variant of R(z) described in Section 3.5 we are able to evaluate the system under the conditions that the routing in a node stops whenever a resource is found. Figure 8 (right) shows the trend of m for di↵erent ↵, and two routing policies for X = 10, T T L = 3, and distribution S 1 . While the number of messages was unrelated to the resource popularity before, here we see that, as routing stops upon first hit, the more popular a resource, the lower the number of messages per query.

Related work

Inter-cooperation of network instances has been identified in [START_REF] Siekkinen | Beyond the Future Internet-Requirements of Autonomic Networking Architectures to Address Long Term Future Networking Challenges[END_REF][START_REF] Fonte | Interdomain Quality of Service Routing: Setting the Grounds for the Way Ahead[END_REF] as one of the future trends in the current Internet architecture development. When discussing logical networks, various techniques to achieve inter-communication among them have been presented.

Synergy [START_REF] Kwon | Synergy: an Overlay Internetworking Architecture[END_REF] is an architecture for the inter-cooperation of overlays which provides a cooperative forwarding mechanism of flows between networks in order to improve delay and throughput performances. Co-located nodes are, in the authors' opinion, good candidates for enabling such mechanisms and reduce tra c.

With a similar goal, authors in [START_REF] Junjiro | Design and Evaluation of a Cooperative Mechanism for Pure P2P File-Sharing Networks[END_REF] propose algorithms tailored to file sharing applications, enabling a symbiosis between di↵erent overlays networks. They present hybrid P2P networks cooperation mechanisms and provide interesting observations on the appropriate techniques to perform network join, peer selection, network discovery, etc. Their simulations showed the e↵ect of the popularity of a cooperative peer on the search latency evaluation, that is the more a node has neighbors, the better, as well as the e↵ect of their caching mechanism which reduces (when appropriately adjusted) the load on nodes (but interestingly does not contribute to faster search).

Authors in [START_REF] Furtado | Multiple Dynamic Overlay Communities and Inter-space Routing[END_REF] model an interconnected system by considering spaces with some degree of intersection between one another. They focus on di↵erent strategies to find a path between two overlays, and compare various routing policies analyzing which trade-o↵s lead to the best results. Trade-o↵s are considered in terms of number of messages, number of hops to find a result and state overhead. They provide a comparative analytical study of the di↵erent policies. They show that with some dynamic finger caching and with multiple gateways tactfully laid out in order to avoid bottlenecks due to the overload of a single gateway, they obtain good performances. Their protocol focuses on the interconnection of DHTs, while we focus on unstructured overlays.

Finally, [START_REF] Maniymaran | Build one, get one free: Leveraging the coexistence of multiple p2p overlay networks[END_REF] studies the co-existence of multiple overlay networks, namely Pastry and an unstructured overlay that uses a gossip protocol to improve its performance.

Conclusions and future work

In this paper we considered interconnection of large scale unstructured P2P networks through co-located nodes called synapses: these nodes send/forward a query to all the P2P networks they belong to. We developed a generalized random graph based model to represent the topology of one unstructured P2P network, the partition of nodes into synapses, the probabilistic flooding based search algorithms, and the resource popularity. We validated our model against simulations and proved that its predictions are reliable and accurate. The model allowed the analysis of very large and complex systems: we believe that simulation and/or prototype deployment based analysis would be unfeasible in this case.

We are currently working to further extend our model in several directions. In particular, we are generalizing equations to represent heterogeneous topologies and resource availability. As a consequence, we are also extending the analysis to more refined partition of synapses, i.e., to consider the fraction of nodes that belong to a specific set of P2P networks. Furthermore, we are extending the model to represent nodes availability due to churning. Last but not least, we are generalizing the model to represent interconnection of both unstructured and structured P2P networks.

Fig. 1 :

 1 Fig.1: Example of two P2P interconnected networks (X = 2) and one degree 2 synapse that belongs to both.

Fig. 2 :

 2 Fig. 2: p hit for di↵erent ↵ and si (left) and alternative search algorithm (right).

Table 2 :Fig. 3 :

 23 Fig. 3: Routing policies comparison: p hit for di↵erent resource popularities ↵.

5 Fig. 4 : 5 , 2 f = 3 f = 4 (Fig. 5 :

 5452345 Fig. 4: Average number of messages for di↵erent routing policies.

Fig. 6 :

 6 Fig.6: Performance evaluation with di↵erent numbers of overlay X.

Fig. 7 :Fig. 8 :

 78 Fig. 7: Distribution of di↵erent routing policies with fixed f .

Table 1 :

 1 m for di↵erent si distributions: comparison between model and simulation.

	Model Simulation (95% C.I.)
	p hit 0.3733 m 4822.63	0.373552 ± 0.003852 4821.57 ± 0.0498

Table 3 :

 3 m for di↵erent si distributions: comparison between model and simulation.

	Model Simulation (95% C.I.)
	S 1 4598.02 S 2 4701.82 S 3 4449.57	4596.77 ± 2.38 4700.96 ± 0.49 4453.58 ± 3.41

This paper is the full version of a two pages poster paper presented in[START_REF] Ciancaglini | Modeling and analysis of large scale interconnected unstructured p2p networks[END_REF]

This work was partially supported by Università degli Studi di Torino and Compagnia di San Paolo under project AMALFI (ORTO119W8J).