Dr Luigi Liquori

Dr Roberto Roverso

Peerialism Ab

The original "selling point" for decentralized networks has been file exchange, using the decentralized approach to diffuse the bandwidth cost between all the participating nodes, augmenting the robustness by avoiding single point of failures and control by sharing the responsibility between all nodes. While the most decentralized approaches are very efficient in terms of resilience, they are, by the same reason, more performance limited and harder to analyze. This analysis is usually the prerogative of simulation tools, a quite inefficient way to analyze the possibility space. We thus developed and present here a mathematical model for network interconnection, enabling the study and exploration of equilibriums and, by virtue of the abstraction of the model, perfectly applicable to any interconnection of networks, be them communication networks, social networks, or physical distribution networks. We also focused on decentralized networks, called MANETs, where communication between mobile nodes is purely ad-hoc based, exploiting rateless coding to minimize data loss due to transmission unreliability, and detecting malicious nodes sending corrupted packets, a hard to detect and prevent problem in a strongly distributed environments, using SIEVE, a custom developed algorithm.

List of Figures

In this Chapter we introduce the works this Thesis is composed of and the needs the proposed solutions arise from.

Each topic is connected to each other in an overall effort to increase robustness and availability in distributed networks and such underlying "common thread" is analyzed in the final Section of this Chapter, as a way to see the whole Thesis homogeneously. Finally, Appendix A acts as reference for the tools used in various topics.

Opportunities and challenges

In computer usage evolution, and its ecosystem in modern society, a particular place is occupied by communication networks. Especially in the last 5 years, with the development of smaller and more powerful devices, there has been a substantial push of the interconnection and mobility aspect of those devices. New use cases migrate from the traditional single node concept with an op-tional connection to the outside world, to a cloud of nodes, each one part of a more complex system, usually distributed, which see each participant only as a functional part of the whole, making the interconnection between them a fundamental part of the system. Such decentralization of the concept of a "computer" opens the road to a whole range of new applications, usually impossible to realize before using a nondistributed approach. A list of a few common examples could be:

• a P2P file exchange, where the bandwidth resources load is distributed and scales with the whole network meanwhile giving the ability to avoid censorship and publishing delays of traditional channels;

• sensor networks, where every node, usually a low-power nano-sensor, exchanges data with others resulting in an exhaustive and robust autonomous coverage of an area;

• backup and data storage, for a totally distributed, set of files and data that can be preserved from physical harm and remotely accessed from every authorized device, everywhere on the globe;

• computational power aggregation, in which research or business institutions can distribute their computational workload among peers in a network;

• smart-grid / smart-city approach, where services and/or physical devices are made to talk with each other exchanging information and coordinating independently, offering a digital representation and access of the physical world;

• ad-hoc opportunistic wireless networking, like Delay Tolerant Networks (DTNs) and mesh networks, where interconnection between usually mobile nodes is made on the fly.

As a continual push to decentralization there is the perennial development of cheaper and more powerful platforms, moving the focus from the hardware, to the service itself, enabled by the software and this time with the hardware as just am e d i u mt oe n a b l ei t su s a g e . This interaction between computers rather than on the computer itself introduces aseriesofproblems,someofwhic hw ereofminorimportancebefore,whileother are completely new, for example:

• moving externally something that is traditionally considered internal to the computer, such as processing, storage, and retrieval of data, forces a particular attention on the performance aspect, where delays and latencies tend to grow by orders of magnitude, and are hardly estimable in advance, needing robust and adaptive protocols;

• the protocol having to manage a bigger probability that data will get lost or corrupted during the transit meanwhile having only minor control over the process, to the point of not being able to directly act even if negative behaviors are known;

• the necessity of data security mechanisms, where the presence in the system of various actor, seldom trusted or known, makes imperative to implement access limits to transiting data and related control mechanisms, this way guaranteeing privacy and correctness.

In the scope of augmenting the performance, as well as the efficiency and robustness of networks, this Thesis adopts a holistic approach, offering a set of different techniques to be optionally applied both in the planning phase of a network design and in the utilization phase of such network. Such techniques are applicable or related to a multitude of network topologies and structures, common denominator between them all the decentralized approach used.

Random graph modeling of overlay networks interconnection

First we describe a random graphs based mathematical model we developed for analyzing network interconnections, where independent networks are connected together by bridge nodes, belonging to two or more networks.

While well known mathematical models exist for modeling individual networks [START_REF] Newman | Networks: an introduction[END_REF], approaches modeling independent networks interconnected through shared nodes are few, and focuses on a hierarchical approach between the networks [START_REF] Martinez-Yelmo | Routing performance in a hierarchical dht-based overlay network[END_REF], or proposes a merging into a single equivalent network.

Both approaches are limiting, in the first case networks are considered not on the same level to each others, and in the second case the networks are either very similar to start with, or deeply modified by a merging like operation on all the networks.

The motivations for such model are to be searched in the computational and time costs associated with validating a specific configurations using simulation tools or limited scale prototyping, while variance in the building parameters can greatly influence performances and behaviors and as such justifies optimization analysis beforehand.

In interconnecting various networks together we are faced with a large number of combinations of parameters, such as the probability distributions describing the number of neighbors a node has, the number of nodes in each network belonging to more than one network, and so on. We focus only on a flooding routing strategy, common to many unstructured approaches (e.g.: P2P networks), so we add as parameters, the probability a node will forward a message (a query usually in communication networks).

Such large number of permutations easily renders any simulative approach quickly limited in its scope or completely inefficient at treating the optimization problem extensively enough, especially considering that many interesting behaviors emerge only when a considerable amount of nodes is present (in the range of 100 000 to 1 000 000 in our simulations), raising exponentially the resource consumption for any simulator or deployment solution.

Essentially, in the simulative approach, each node and each message, or at least a simplified model of them, must be kept in memory, and many parallel virtual events are coalesced in fewer processes leading to very intense use of computational resources like memory and computational power.

In our original testings with the the OmNET++ [3]s i m u l a t o re a c hs e to fp a -rameters run, on a quad core Intel Xeon workstation with 16GB of RAM, took about two real-time days for 5 simulated networks of 100 000 nodes each, while ah e a v i l ys i m p l i fi e da n dp a r a l l e l i z e dc u s t o ms i m u l a t o rw r i t t e ni nE r l a n g [START_REF] Ciancaglini | Interconnection of large scale unstructured p2p networks: Modeling and analysis[END_REF], optimized only to treat message passing and no transmissions details or contents, took, on the same machine, a few hours for each run, both software completely using the machine and using up to 8GB or RAM. Also this was only for a single run, while to have statistically significant data, at least a few runs for each parameters set have to be executed and averaged, linearly multiplying the time needed for the number of run repetition, then multiplying again for each set of parameters in the selected permutations, easily leading to weeks and weeks of continuos computing time for just exploring a small subset of all the possible permutations, all with the statistical relevance offered by the number of repetition for each run allowed.

Clearly this is not the best way to proceed, to this reason we developed a mathematical model representing the probability a node in a given network will find the resource he wants (meaning his query will reach a node owning the resource in a given number of jumps) and the average number of messages sent, given the number of networks, the probability distribution for neighbor nodes and for bridge nodes and the forwarding probability for the routing.

It may be noted that the number of nodes is not given as a parameters, as the model finds the probability a node will be reached in a number of steps, so it is agnostic to the number of nodes in the real implementation. This aspect is important to point out as the behavior of the model, explained before, shows up in the simulator and deployment only when a significative number of nodes is involved.

The gain in efficiency and pervasiveness is clearly visible as executing the model over a specific set of parameters takes only a few milliseconds and returns average values, not needing multiple runs, rendering possible to explore the same parameters that the simulators took weeks in less than a few hours on the same machine, with more precise (and reproducible) results obtained.

Polluter identification in MANETs

Another topic of our Thesis focuses on mobile, distributed, ad-hoc networks, and the inherent challenges in implementing a communication network which is both decentralized and restructured as possible and at the same time robust and efficient.

To this effect we initially approached the problem from related points of view:

• from perspective of the used coding, where we introduce the use of rateless coding to avoid data loss and availability problems in the network;

• from a pollution detection perspective, where we devise an efficient way of identifying malicious nodes in a completely distributed environment, especially important while used with the above encodings;

These two works are inherently connected to each other and are thus published, and presented here, together.

Ac e n t r a ls t e pi no u rs t u d yi st h eu t i l i z a t i o no fr a t e l e s sc o d i n gt e c h n i q u e si n completely distributed and unstructured networks, where knowledge of neighbors nodes is not exploited and only probabilistic flooding routing is available, thus rendering any centralized control or organization unneeded as long as two or more nodes are in range to communicate. The chosen encoding is LT Code [START_REF] Luby | Lt codes[END_REF] where encoding server nodes divides a message chunk in n blocks, then proceeds to encode packets by combining together d distinct blocks by logical XOR-ing them, where d<nand is randomly chosen by a Robust Soliton Distribution (RSD), guaranteeing that the chunk will be decoded in n • (1 + ")packetsreceived,where" tends to zero as n tends to infinite.

The server nodes than proceeds to wirelessly send the encoded packets around (similar to a fountain distributing water streams, from which the fountain coding synonym) which are received, stored and decoded when possible by decoder client nodes, which can, based on the scenario parameters, repeat the packets to their neighborhood to achieve better data diffusion at the cost of higher bandwidth usage and more difficult detection of eventual malicious nodes.

While the transmission overhead in respect to a sequential transmission of each block would be wasted in a reliable, non-lossy channel scenario between nodes, the repetition of data in the encoding helps circumvents the shortcomings of an ad-hoc wireless connection between wireless nodes, where node availability and transmission correctness can both not be guaranteed, nor expected.

Such peculiarities makes LT Codes a very well fit for all cases where there is a multitude of nodes, loosely or not hierarchically organized, in which the communication quality and reliance cannot be assured, such as wireless networks, P2P communications, and mobile ad-hoc wireless networks. All those topics represents in some way or another a strong point of this Thesis, making rateless coding a very helpful tool to have.

A topic which is a natural pairing to our rateless code based protocol is an efficient way to identify polluters, intended as nodes that voluntarily submit maliciously modified packets to corrupt the decoding process.

The more the network is lacking a central or local organization and collaboration, the clearer it becomes the threat that such malicious actors represents to the robustness and efficiency of the whole network and the harder it is to identify reliably bad acting nodes, especially recently appeared ones, either because they are fast moving or changing identity periodically.

Ac o m m u n i c a t i o nn e t w o r kl i k et h eo n ep r e s e n t e db e f o r e ,o ri ng e n e r a la n y ad-hoc distributed network, is vulnerable to many attacks at many layers. While protection against physical and transmission level attacks are out of the scope of this work and a few solution are available, we focuses on protecting against attacks on the decoding process by means of malicious nodes voluntarily sending malformed packets to pollute the overall chunk for unaware listening honest nodes.

As with many decentralized networks there is a clear advantage for a pollution detection algorithm to be completely distributed and all computation local to each node, which SIEVE [START_REF] Gaeta | Sieve: a distributed, accurate, and robust technique to identify malicious nodes in data dissemination on manet[END_REF] is, listening to other nodes reports, but constructing its beliefs only inside the node itself, without depending on any centralized authority. Also, to be usable in a mobile environment such algorithm execution must be energy efficient, another strong fit for SIEVE being based on simple Belief Propagation iterations.

Finally the approach, while here mated to our LT Code exploiting protocol, is not by any mean bound to it. It is usable with any protocol that at any point of the decoding process, not necessarily at the end, is able to return a check containing a status (polluted or clean) and a list of all the nodes that contributed to that chunk and how much they contributed. The usage with an erasure fountain code can be seen as a worst case scenario, as the check can be produced only at the end of the decoding process and usually a lot of nodes contributes to a single chunk.

CCN and CCN-TV

Another topic that we studied in our Thesis is a simulative study of CCN-TV, a CCN based approach to TV service via internet video streaming. Content-Centric Networking (CCN) [START_REF] Jacobson | Networking named content[END_REF]i sap r o m i s i n ga p p r o a c ht od a t a -c e n t r i c architecture, in which the routing is name based (instead of address based) and the search is initiated by the data user rather than the data provider, leveraging intermediary nodes caching techniques to enhance performances exploiting data locality.

The need for CCNs comes from an average utilization of communication networks more and more to deploy and consume contents, be them video, documents, music or generic data. In such context the ability to directly research and access wanted contents rather than having beforehand to know which nodes will serve which contents and then accessing their address, is indeed welcome.

Consider the case where someone wishes to access a video stream of a given social event, in the classic internet case he will have to beforehand known a provider of such service (and its address) or a service offering search services (and its address) such as a search engine. Once he has obtained the video service provider address he will contact it and request the desired content, awaiting (and hoping) for a positive reply and only then beginning the data transfer, usually directly between.

In comparison the CCN approach does not need any previous knowledge as he would send an Interest packet, stating that he wishes to receive such service, and the packet is routed, based on a categorization of names, after a certain amount of hops to a machine who does provide such services.

The machine will send back the data, using previously touched nodes as intermediaries, so that if a neighbor of the requester asks for the same content he will not have to reach back the remote server again, but the first intermediary node will respond positively to his Interest request.

While a complete and general implementation overlaying current internet is still very difficult, having to face problems such as devising and adopting an efficient ontology of contents, to permit efficient routing, a more limited scope implementation, such as video on demand and real-time video services, is very promising and robust, integrating resource discovery and local caching directly in the routing protocol.

A unifying view of the Thesis

The Thesis flows around the central concept of enhancing the robustness and resilience of distributed networks through distinct techniques, each facing the problems from a different, sometimes complementary, point of view. Two main directions are present in this work:

• the first one is using random graph modelization to exhaustively study the behavior of a system of interconnected networks over a set of common nodes called bridges; such study works toward efficiency and resilience by offering the tool needed to accurately study a network topology and its effects before deployment or modification;

• the second one is focusing on distributed networks by studying the effect of novel routing and content discovery protocol (CCN), and polluter identification techniques coupled with rateless coding content distribution.

Both contributions aim to make distributed networks more efficient and robust, one in the planning and analyzing phase, the other during execution.

Our contribution tackle the problems following both an off-line and on-line approach, with a set of conceptual tools to be exploited as needed.

Our original contributions, as better explained in the following Chapters, span over the two main topics.

For the first topic contribution we exploited random graphs to develop a mathematical model of network interconnection [START_REF] Ciancaglini | Interconnection of large scale unstructured p2p networks: Modeling and analysis[END_REF][START_REF] Gaeta | Modeling and analysis of large scale interconnected unstructured p2p networks[END_REF], where the model can be use to efficiently investigate the behavior of a given set of bridge-node interconnected networks, regarding the probability of finding a resource and the average number of query packets generated, given a certain number of hops permitted and the networks defined by a set of parameters.

The second line of work focuses on distributed mobile networks and ways to maximize their resilience during execution, such as developing a completely distributed polluter identification scheme called SIEVE [START_REF] Gaeta | Sieve: a distributed, accurate, and robust technique to identify malicious nodes in data dissemination on manet[END_REF][START_REF] Gaeta | Exploiting rateless codes and belief propagation to infer identity of polluters in manet[END_REF]w h i c hw o r k so v e ra P2P protocol we implemented base on rateless coding, or exploiting novel routing and content identification protocols such as CCN, focusing on real-time video streaming by adapting and studying the protocol in our CCN-TV approach [START_REF] Ciancaglini | Ccn-tv: a data-centric approach to real-time video services[END_REF], and successively extending the study to include crowd-sourced generated contents [START_REF] Piro | Providing crowd-sourced and real-time media services through a ndn-based platform[END_REF].

Chapter 2

State of the art

Chapter abstract:

In this Chapter we analyze, for each topic, the state of the art and related comparable works.

While a more in depth analysis is present in each topic dedicated Chapter in Part II, the present Chapter helps in pointing out the background of the field as well as strong and lacking points of related published works.

Random graph modeling of overlay networks interconnection

Network interconnection and cooperation is indeed of growing importance in the future.

The bulk of related modeling literature focuses on evaluating single network behavior, which limits the statistical analysis to the merging of networks together, a very expensive and rarely feasible approach.

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]a so n e 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]i sa na r c h i t e c t u r ef o rt h ei n t e r -c o o p e r a t i o no fo v e r l a y sw h i c h provides a cooperative forwarding mechanism of flows between networks in or-der to improve delay and throughput performances. Co-located nodes are, in the authors' opinion, good candidates for enabling such mechanisms and reduce traffic.

With a similar goal, authors in [START_REF] Junjiro | Design and Evaluation of a Cooperative Mechanism for Pure P2P File-Sharing Networks[END_REF]p r o p o s ea l g o r i t h m st a i l o r e dt ofi l es h a ring applications, enabling a symbiosis between different 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 effect 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 effect 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]m o d e la ni n t e r c o n n e c t e ds y s t e mb yc o n s i d e r i n gs p a c e sw i t h some degree of intersection between one another. They focus on different strategies to find a path between two overlays, and compare various routing policies analyzing which trade-offs lead to the best results. Trade-offs 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 different 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]s t u d i e st h ec o -e x i s t e n c eo fm u l t i p l eo v e r l a yn e t w o r k s ,n a m e l y Pastry and an unstructured overlay that uses a gossip protocol to improve its performance.

The topic of social network interconnection is a specific application of the network interconnection through bridging which is attracting a lot of interest due to the availability of multiple, expanded and existing social networks already deployed and in use.

The advantages offered by social inter-networking are centered about transparently "de-isolate" the single networks, exploiting the preexisting connections, which are compatible between the networks by mean of being based on the same social structures and relationships, effectively enabling a virtual "over-network" extending and exploiting all the single social networks contents.

As u m m a r yo fv a r i o u sw o r k si n [START_REF] Buccafurri | Bridge analysis in a social internetworking scenario[END_REF] analyses the social inter-networking from the point of view of bridge interconnection, yet to the best of our knowledge no specific modeling tool exists to better study the various behaviors of the overall system.

Polluter identification in MANETs

Research in the field of rateless coding is well established in literature, with major examples being LT Codes [START_REF] Luby | Lt codes[END_REF] and their conceptual evolution Raptor Codes [START_REF] Shokrollahi | Raptor codes[END_REF]. There have been interest in coupling rateless coding, and the relative concept of fountain encoding, with various fields interested by communication by many nodes and variably unreliable transmissions, like video streaming [START_REF] Grangetto | Rateless codes network coding for simple and efficient p2p video streaming[END_REF]orextending P2P BitTorrent file transfer [START_REF] Magnetto | Fountains vs torrents: the p2p toroverde protocol[END_REF][START_REF] Spoto | Bittorrent and fountain codes: friends or foes?[END_REF]a n dt h et e c h n i q u e sh a v eb e e ni n t e g r a t e di n part of the error control protocol for LTE mobile networks.

Works in the field have mainly fo cused on finding more efficient ways of decoding (referring to performance to energy consumption ratio) and implementing encoding and decoding over non fixed sliding-window chunks of data [START_REF] Fiandrotti | Band codes for energy-efficient network coding with application to p2p mobile streaming[END_REF].

The next generation of rateless codes implementations after LT codes is commonly agreed to be Raptor Codes [START_REF] Shokrollahi | Raptor codes[END_REF], having linear time encoding and decoding, but computationally more intensive by using two encoding stages for encoding, where the second stage is an LT encoding.

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-thefly 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 signature-based 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]h a sp r o p o s e da n 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 contribution 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-to-peer streaming[END_REF]p r o p o s e sad e t e c t i o ns c h e m ew h e r ee a c hp e e ri sa b l et od e t e c tr e c e i p to f 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 true polluters cannot lie (the authors developed 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 adopt 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]presentsadistributeddetectionalgorithmandanalyzes 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 network-coding enabled wireless mesh networks[END_REF][START_REF] Li | 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-to-peer 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.

Our work instead has been shown here to be very efficient, even with an unreasonably high number of malicious nodes, and computationally cheap, also being not limited to MANETs networks, but easily applicable to other more common P2P networks [START_REF] Gaeta | Dip: Distributedidentificationof polluters in p2p live streaming[END_REF][START_REF] Gaeta | Identification of malicious nodes in peer-topeer streaming: A belief propagation-based technique[END_REF].

CCN and CCN-TV

Internet usage patterns changed a lot in the last decade, where an ever-expanding multitude of sites and contents offers shifted the focus to content sharing and consumption, still offered on the IP underlying protocol.

Many Future Internet templates offer evolutions to what the current technical and social structure is, usually by shifting focus on content itself, rather than on the content provider, increasing role of P2P connectivity models, enabled by a greater ever-present connectivity between a plethora of devices, and considering the paradigm-breaking concept of pervasive mobility.

Many proposals move the data in a primary position, by adopting models like Publish-Subscribe [START_REF] Eugster | The many faces of publish/subscribe[END_REF], where a service provider publishes its offers in terms of datas and services and interested nodes subscribes and are then given the requested service, or caching approaches of Store-and-Forward, original of DTN networks [START_REF] Cerf | Delay-tolerant networking architecture[END_REF].

Amidst the multitude of proposals a common idea links many of them, where the contents are made central and are offered by providers and requested by consumers, adequately routed to each other by intermediary nodes based on their knowledge of the current offers of services. Local cache is used to avoid repeated traffic as much as possible if the contents are already "in the neighborhood". The main proposal is this field are CCN, sometimes referred also as Named Data Networks (NDN), [START_REF] Jacobson | Networking named content[END_REF].

While promising however the field is still loosely defined by the general rules of Interest and Data packets exchange and caching usage, but a lot of study is currently focusing on routing algorithms [START_REF] Choi | A survey on contentoriented networking for efficient content delivery[END_REF][START_REF] Baid | Comparing alternative approaches for networking of named objects in the future internet[END_REF]a n de v e ni nl e s so rm o r er a d i c a l modifications of the protocol to specific scopes, like our present work on CCN-TV.

A reference software implementation also exists, called CCNx [START_REF] Vv | Ccnx home page[END_REF], yet works have mostly been theoretical so far, with yet to assess the success and efficiency of a real-world deployed in the wild implementation of any kind.

Chapter 3 Thesis contributions

Chapter abstract:

In this Chapter we present the original contributions of our works and this Thesis.

While we reserve the more technical details to the Chapters in Part II, we describe the approach used in each work and, where relevant, the differences with the mainstream implementation (eg.

Section 3.3).

With the aim of making clear how each contribution is constructed we delegate the details to the specific Chapters, focusing on shortly, but clearly, explaining the whole process.

Random graph modeling of overlay networks interconnection

We describ e the network by means of its degree distribution p k ,i.e. theprobability arandomlychosennodehask connections in the same network, and a probability distribution s i ,meaningthefractiononnodesbelongingtoi distinct overlay, with 1  i  X,w h e r eX is the number of networks present.

The considered routing algorithm for the queries is flooding base, i.e. a node starting a search forwards the query (with probability p f (i)) to a random subset of its adjacent neighbors. They then forward the query to a random subset of their one-hop neighbors and so on, until the maximum number of hops, defined as Time To Leave (TTL), eventually forwarding the query up to the TTL if the receiving node has the resource, depending on the variation of the search algorithm chosen. To mo del the search we define the goal as to reach at least one no de containing the desired resource with the queries, which popularity is defined as 0  ↵  1, meaning the probability a random node will have the resource.

We mo del a single network as a random graph degree distribution G 0 (z)a n d derive G 1 (z) as the probability generating function (p.g.f.) of the adjacent neighbors connections excluding the edge we came from, chaining it to obtain the p.g.f. of a given TTL neighborhood, e.g. G 0 (G 1 (G 1 (z))) for TTL =3.

To then mo del the interconnection we consider that some p eers will b e bridges, called Synapses in the original work [START_REF] Liquori | Synapse: A scalable protocol for interconnecting heterogeneous overlay networks[END_REF], enabling the query to diffuse in other networks neighborhoods too. The related p.g.f., relative to probability distribution s i ,i sF (z), and by combining it with G 0 (z)w eo b t a i nM (z), the p.g.f. for the number the neighbors considering the bridges too. By extension, combining with G 1 (z)t o ow eo b t a i nN (z)t h ep . g . f . f o rt h en e i g h b o r h o o d ,e x c l u d i n gt h e selected edge. We are then finally able to define the p.g.f. for the number of neighbors t hops away as N t (z), such that N 1 (z)=M (z), N 2 (z)=M (N (z)), N 3 (z)=M (N (N (z))), and so on.

Once we modeled the interconnections, we combine our p.g.f. with our p f probability the query will be forwarded to define various p.g.f. leading to Q t (z), the p.g.f. for the probability distribution of the number of neighbors t hops away from a randomly chosen node that received a query, which product for each 1  t  TTL gives us T (z), yielding us the average number of queries m = T 0 (1).

Finally by introducing the ↵ resource distribution probability we define the p.g.f. H t (z)f o rt h ep r o b a b i l i t yd i s t r i b u t i o no ft h en u m b e ro fn e i g h b o r st hops away for a randomly chosen node that received a query and also possess a copy of the requested resource, which product for each 1  t  TTL gives us, as before, H(z), giving us the search hit probability p hit =1-H(0). We also alternatively defined a different R(z)toalsoexperimen twiththev arian tinwhic hanodeo wning the resource will not forward the query if it is received. A better description of the standard version and this variant is present in Section 4.3.3 and 4.3.5.

Polluter identification in MANETs

We exploited the non sequential and redundancy prop erties of erasure co des, LT Codes in particular, to raise the robustness and efficiency of unstructured ad-hoc wireless networks. Avoiding any kind of routing assumption and only basing our transmission on flooding patterns makes the approach readily applicable to any topology of networks or degree of mobility between the nodes, yet creates new efficiency and reliance problems, as there are no guarantees that the packet will be received or that the percentage of lost or corrupted ones will be under a certain threshold.

As e r v e rn o d e ,i . e . an o d et h a ta l r e a d yp o s s e s s e st h ec h u n ko fd a t at ob e transmitted and is willing to share it with others, will start encoding the packets to be sent out continuously. Differently from a direct transmission there is a sequential flow of packets after which the transmission ends, instead each packet payload is composed of 1 to n blocks encoded together using a XOR function, where n is the number of equal size blocks the chunk is divided into and the number of blocks a packet contains is called degree or d.

Necessary to the decoding in the packet header there is an hash h,iden tifying the chunk, the number n of blocks it has been divided into, the degree d of the current packet and a list L of the d distinct blocks that are encoded in the payload.

If a particular probability distribution is used to randomly choose the degree of the generated packets the decoding is mathematically proven to be possible after having received n • (1 + ✏)p a c k e t s ,w h e r e✏ tends to 0 when n tends to 1,m e a n i n ga l s ot h a tt h eo v e r h e a dg r o w ss m a l l e rt h em o r eb l o c k st h ec h u n k is divided into. Such distribution is called Robust Soliton Distribution (RSD) and it is a variant of the Soliton Distribution modified to guarantee the previous decoding assertion [START_REF] Luby | LT codes[END_REF].

It is to be noted that a packet with d =1a n dL = {k} (where of course 1  k  n)c o n t a i n si nt h ep a y l o a dt h ee x a c tk -th block and is the only packet that is readily decodable (not depending on other blocks to be decoded). For all d>1p a c k e t st h ep a y l o a dn e e d sa tl e a s to n ea l r e a d yd e c o d e db l o c kf o r mi t sl i s t L,t h ee x a c tn u m b e rd e p e n d i n go nt h ed e c o d i n ga l g o r i t h mu s e d ,t od e c o d et h e remaining information (blocks in L not already known), but it can be stored for later usage, when additional information has been received.

Finally the server broadcasts wirelessly the packet to all nodes who can hear it (hence the term fountain coding), not expecting any reply or acknowledge and thus keeping on encoding and sending packets until a certain prefixed condition has been met, like a timeout or a number of packets sent.

Client decoding works by collecting all the packets received by the client, then subdividing them by the h identifier, indicating different decoding sessions and data. Focusing on a specific hash generally the payload and relative metadata is extracted (degree d and list of blocks L) and passed to the used algorithm, in order of efficiency:

• Sequential,av eryinefficien ttest-onlyalgorithmonlyk eepingdistinctd =1 blocks and discarding all the others, effectively negating LT Code benefits;

• Belief Propagation,ab a s i ca l g o r i t h mc r o s s i n gk n o w nd e c o d e db l o c k sw i t h stored still un-decoded data to progressively trim down blocks;

• Gaussian Elimination,amoreefficien tcomparisonalgorithmthenBP ,permitting a faster decoding, even when there is scarcity of degree one blocks.

Then depending on the parameters passed to the nodes a client can, once obtained the decoded chunk, become a server for that chunk, simply repeated heard packets, be their chunk already decoded or not or simply do nothing other than receiving.

As seen previously, decoding is an incremental process in which various nodes collaborate in seeding the decoding pool, and which result is known only when a certain number of packets has been received, an average of n • (1 + ✏), where n is the number of blocks the original chunk has been divided into if the decoding and ✏ an overhead dependent on n.

The whole SIEVE [START_REF] Gaeta | Sieve: a distributed, accurate, and robust technique to identify malicious nodes in data dissemination on manet[END_REF]a p p r o a c hi sb a s e do nt h ec o n c e p to fc h e c k s ,w h i c ha r e produced by the receiving node and can be negative or positive,r e s p e c t i v e l yi f the decoding is successful or fail as soon as an inconsistency in the underlying system of linear equations for the decoding is found.

Each node internally maintains a list L n of all internally created checks and, to raise the availability of checks data, broadcasts the check each time it is produced and periodically, once every T s seconds, a set of random Q checks in L n .

The checks in L n and all received checks are used to build the bipartite factor graph G n =(U, C, E), where vertex set U is the set of uploader nodes, vertex set C is the set of checks, and an undirected edge {i, I}2E exists if and only if check I 2 C depends on uploader i 2 U.W ea l s or e f e rt ot h es e to fu p l o a d e r si n v o l v e d in check I as U I and the set of checks that node i contributes as an uploader as

C i .
The goal of the inference problem of identifying malicious nodes from a given number of checks is to estimate the hidden state of the nodes (malicious or not) and we adopt the Belief Propagation (BP) algorithm for the task [START_REF] Gaeta | Identification of malicious nodes in peer-topeer streaming: A belief propagation-based technique[END_REF].

From a neutral value of 0.5fortheprobabilit yofeac hnodeofbeingmalicious and honest each check works towards implying the set uploader nodes as honest or malicious depending if negative or positive,finallyextractinganestimateafter a reasonable amount of iterations has been collected.

To face the constantly changing environment the BP estimation is designed to be incremental, rather than a single iterative instance, utilizing a sliding window approach over a certain amount of time. Each time a given node is considered to be a suspect polluter over a certain threshold the node is included in the list of probable polluters or, if already present, its counter increased by one, then, the overall ranking, is produced based on sorting the counter value of each node in the probable polluter list.

We currently do not integrate a way to phase out probable p olluters over time, if ever this is to be considered a feature it would be easy to decrease the counter based on some heuristic, for example every given amount of time.

CCN and CCN-TV

In keeping in line with the content centric CCN vision the communication is initiated by the client, who generates an Interest message and expects to receives a Data message, the only two type of messages used.

The issued Interest packet serves to request a specific content and is routed by successive nodes until a provider for that content is found. The server will then reply with Data packets which will follow the inverse path of the Interest packet back to the original client requesting them. All the message exchanges happens between the nodes faces,w h i c ha r et h eC C Ne q u i v a l e n to fan e t w o r ki n t e r f a c e .

Every intermediate node is allowed, and usually expected if able, to keep in its cache the forwarded content, such that a subsequent independent Interest packet for the same content reaching the node won't have to be forwarded up to the server, but will be replied by the cached Data packets, thus easily resolving congestion on popular contents and raising data availability and speed for locally available contents.

In this scheme a few issues are of great importance and directly influences the overall performance of the protocol. The first and foremost is routing and by extension namespace definition,a st h eInterest packet is routed node by node by using the content requested as an "address", where usually a hierarchy of categories (e.g.: /media/video/sport/curling/olympics2006 )isdefinedinanamespace and such layers are used to route to nodes which are in the specific routing Tables responsible for that root name, in a manner reminiscent of subnet addressing in common IP routing.

Our specific approach, aimed at realtime video streaming, and called CCN-TV, specifies a few aspects of the base CCN protocol and adds a few fields to the Interest and Data to manage client bootstrap and requirements of live video feeds. Such addition are anyway easily adaptable to classic CCN message structure by merging them as additional fields in the content name and specifying a nocaching, direct forward policy on participating nodes for Interest packets working as bootstrap messages for a client.

Internally the node keeps the same structures as a standard CCN node:

• a Content Store (CS) which is a cache memory for received contents and managed by a chosen replacement policy;

• a Forwarding Information Base (FIB) which is a forwarding Before starting the real data transfer in the CCN-TV approach a client node bootstraps the channel between him an the server, by sending a particular Interest with the desired domain (the content provider) and channelID (the specific channel), the Status and Nonce (the added custom fields we noted before) respectively set to "BOOTSTRAP" and a random, but reasonably unique, numerical identifier, ensuring each distinct bootstrap request for the same content will be distinguishable.

The bootstrap Interest is specially treated by the intermediate nodes by simply forwarding it up to the server node, ignoring the caches for the same content they may have in the CS. This is to avoid sending the client a video frame not suitable to start the playing, i.e.: a frame which is not a key frame (called in jargon I-frame) or a stale (already expired) I-frame. The chunkID of the chunk containing the last generated not expired I-frame and the index for that frame is then sent back to the client with a Data packet, which will start the standard requesting exchange, with the only difference that the Interest is sent only once for astreamofData packets to reduce network load, acting more like a subscription.

A mechanism based on the delay on the bootstrap (and subsequent request) messages works as flow control, setting the size for the sliding window buffer of received frames, essential in live-streaming video, which must be big enough to avoid emptying it by delayed Data packets, but not too big to put un unreasonable delay in the video playing.

The last addition to the standard CCN scheme to conform to real-time video streaming is the ability to request a retransmission of a given chunk. By setting the Status field of an Interest packet to "Retransmission" the intermediate nodes replies with the content if the have it in their CS, otherwise they forward the Interest (if they a matching face in the FIB) regardless, eventually adding it to their PIT.

Part II

Detailed works Chapter 4

Random graph modeling of overlay networks interconnection

Overview

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 Thesis we consider interconnection of large scale unstructured P2P networks by means of special nodes (called Synapses)t h a t 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. 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 different interconnection costs and to provide some insight in the characteristics of the interconnection of a large number of P2P networks. Useful applications of interconnecting unstructured P2P networks spans from interoperability of existing data-bases ensuring backward compatibility, to the "hot" topic of Typed Smart Grid where users can be aware of the "type" of energy they want to produce and buy.

The last decade has seen the rise of peer to peer networks with a variety of ap-plications, such as file sharing, resource lookup, real time services, up to the most recent research in SmartGrids. Common issues which affect all P2P systems, such as scalability, fault tolerance and security, arise from the different 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 Thesis, 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 efficient and effective search algorithms and to control the cost of network 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.

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 different 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 work on model-based analysis of interconnection of large scale unstructured P2P networks.

The topic is organized as follows: Section 4.2 describes our system, Section 4.3 presents the mathematical derivation of the generalized random graph model we develop, Section 4.4 contains model validation through simulation, as well as model exploitation to study the performance of three search algorithms, Section 2.1 discusses related works, and in Section 7.1,w ed r a wc o n c l u s i o n sa n do u t l i n e ongoing activities that extend the current work.

System description

In this Thesis, 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})w h e r es 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.Ap e e rs t a r t i n gas e a r c h 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 Figure 4.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 ap r o b a b i l i t y 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 different peers for two reasons: a resource is popular and/or is owned by peers located in different 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 4.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 .T oc o r r e c t l yc h a r a c t e r i z et h en e i g h b o r h o o do fa 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 )a n d 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)d e n o t e s the first derivative of G 0 (z)w i t hr e s pe c tt oz 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)
.S t a r t i n gf r o mE q u a t i o n s defining G 0 (z)a n dG 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 .I fw ec o n s i d e ro n eo ft h eX 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 )t h e nt h en u m b e ro fc o n n e c t i o n si sr e p r e s e n t e db yG 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)f a c t o ri nt h ee q u a t i o nf o rM (z). The same reasoning is valid for Synapses whose degree is greater than 2.

As i m i l a re x p r e s s i o nc a nb ew r i t t e nf o rt h en e i g h b o r h o o do fan o d er e a c h e d 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)t h ep . g . f . f o rt h ep r o b a b i l i t yd i s t r i b u t i o no ft h en u m be ro f 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). (4.1)

Search algorithm

To model a flooding-based search in the interconnected system, we consider the set of probabilities {p f (i)},w h e r ei 2{ 1,...X}.Ap e e rb e l o n g i n gt oi 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 ap r o b a b i l i t yd i s t r i b u t i o n . 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)). (4.2)
If we denote as Q t (z)t h ep . g . f . f o rt h ep r o b a b i l i t yd i s t r i b u t i o no ft h en u m b e r 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}.I nt h i sc a s e ,w ew o u l do b t a i n :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 TTL t=1 Q t (z)y i e l d i n gt h eaverage number of queries m = T 0 (1). (4.3)

Hit probability

We mo del resource p opularity by 0  ↵  1t h a ti st h ea v e r a g ef r a c t i o no f 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)t h ep . g . f . f o rt h ep r o b a b i l i t y 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 TTL t=1 H t (z)y i e l d i n gt h es e a r c hhit probability p hit =1-H(0). (4.4)

A variation of the search algorithm

To mo del a search algorithm where p eers that own a copy of the resource do not forward a query message it suffices to redefine R(z)i nE q u a t i o n4.2.I n 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 ↵.I nE q u a t i o n 4.5 this is represented by the term ↵ that can be written as ↵ • p 0 • z 0 with p 0 =1. With probability 1 -↵ Equation 4.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)). (4.5)
The definition of Q t (z), and T (z), and m remains unchanged.

Results explained

In Sections 4.5 and 4.6,w ew i l lfi r s ts h o wt h er e s u l t so ft h em o d e lv a l i d a t i o n , 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 different routing policies that can be employed in our scenarios, modeled by defining the p f (i)m e n t i o n e di nS e c t i o n4.2.T h o s e are:

• p f (i)= 1 i
,h e n c e f o r t hr e f e r r e dt oa s1/i,i . e . t h ep r o b a b i l i t yo fs e l e c t i n ga 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,w h e r ez = 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,t w i c et h ea v e r a g en u m be ro fn e i g h bo r spe rn od e .

• p f (i)=1 ,h e n c e f o r t hr e f e r r e dt oa sflood,i . e . ar o u t i n gw h e r ee v e r yn o d e 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]f r o mr e a lw o r l da pplications and used already in [START_REF] Gaeta | Generalized probabilistic flooding in unstructured peer-to-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 4.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);eac hin terconnectedtopologyisusedtoobtain one realization of m and p hit .T h eh th realization is obtained as follows:

• We first generate a new top ology, 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 top ology 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 ↵,b ys e n d i n gaPUT(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 TTL 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 different 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 | Efficient 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 ) . F o rt h es a k eo fb r e v i t yw eo n l ys h o wt h er e s u l t sf o rt h eflood routing strategy, ↵ =0 .0001, and TTL =3 . T a b l e4.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 numb er of interconnected overlays (X =4),atTTL =3, 4a n dw i t hd i ff e r e n tv a l u e so f↵,d i ff e r e n tr o u t i n g policies and different distributions {s i }.W ec o n s i d e r e dt h ed i s t r i b u t i o nf o rt h e degree of Synapses summarized in Table 4.2. Furthermore, we validate the system against the alternative search algorithm detailed in Subsection 4.3.5.F o rt h es a k eo fb r e v i t y ,w ea r es h o w i n gr e s u l t so n l y for S 2 since the same conclusions can be drawn for S 1 and S 3 . Figure 4.2 (right) shows both p hit and m against different values of ↵,s in c ew ithth isalgo rith mth e 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 different 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 different routing policies

Afi r s te v a l u a t i o nc o n c e r n st h ec h o i c eo fas p e c i fi cr o u t i n gp o l i c yi nt h es y s t e m , i.e. the definition of different p f (i). In this case, we want to compare for values of ↵ down to 10 -6 ,t h ep e r f o r m a n c e si nt e r m so fp 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 =1 0 ,a n dTTL =3 . Please note that to achieve a reliable measurement via simulation for ↵ =1 0 -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). 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 )a n dm i n i m u mc o s t( 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 3v a l u e so ff (namely, f =2 , 3, 4) and compared the performances of every distribution {s i } with given f for TTL = 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 different distributions. This analysis required only a few seconds to complete with our model. 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 ;i ta p p e a r st h a tt h ei n t e r c o n n e c t i o nc o s tf alone is not directly bound to an increase in performances. There are, as a matter of fact, different configurations with f =3t h a tp e r f o r me q u a l l y( s o m e t i m e sv e r y slightly better) than those with a f =4 . F u r t h e r m o r e ,w i t h i nt h ec o n fi g u r a t i o n with f =2s o m ea r eb e t t e rt h a no t h e r si nt e r m so fp e r f o r m a n c ea n dc o s t s . Nevertheless, a clear relation exists between message cost m and p hit :t h el a r g e r the average number of messages the higher the p hit . The behavior shown in the Figures can be explained as following: the routing policy called zmax limits the number of messages that can be issued by a node to the value z max ,w h i c hi ss e ti no u re v a l u a t i o n st o2 z. Therefore, increasing the number connections in the interconnected system (f )b e y o n dc e r t a i nv a l u e s does not lead to a significant performance increase. That is why we observe a proportionally higher increase in the p hit from f =2t of =3t h a nf r o mf =3 to f =4.

Effects 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 TTL = 3 and ↵ =0.0001, for an increasing number of overlays (X)a n df o rd i ff e r e n td i s t r i b u t i o n s{s i },c h a r a c t e r i z e db y an increasing percentage of non-Synapse nodes s 1 ,w h i l et h er e m a i n d e ro ft h e distribution is equally distributed across the remaining s i . show four different 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 )i se q u a l l yd i s t r i b u t e d among the remaining X -1 values, i.e., s i = 1-s 1 X-1 for 1 <i X.I tc a nb en o t e d that at each given ratio of Synapses vs non-Synapses nodes the system behavior is

System design with minimum requirements

Thanks to the high number of different 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 numb er of overlays X and the resource popularity ↵;b ys e t t i n gab o u n df o rt h em i n i m u md e s i r e dp hit ,w ec a nc o m p a r ed i ff e r e n t routing policies and TTL values and find the one that minimizes the average number of messages m.

Figures 4.7 and 4.8 (left) show a classification of distributions {s i } for two different routing policies and two different TTL values with respect to p hit and m for X =1 0a n d↵ =0 .0001 (each point in the graphs represents a particular distribution {s i }). In the first case (Figure 4.7), we decided to fix a cost factor and set f = 4, whereas in the second case (Figure 4.8 left), the fixed factor is the ratio of expected non-Synapse nodes in the system s 1 .W ea r ea b l et od i s c r i m i n a t e 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

Routing without propagation

We briefly present some evaluation results based on the mo del variation presented in Subsection 4.3.5.I nt h efi r s tv e r s i o no fo u rm o d e l ,t h er o u t i n go fam e s s a g e is assumed to continue until the TTL expires, regardless of a resource being found or not. This leads to an H t (z)a b l et od e s c r i b ed i ff e r e n tc a s e s ,s u c ha s 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)d e s c r i b e di nS u b s e c t i o n4.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 4.8 (right) shows the trend of m for different ↵, and two routing policies for X =1 0 ,TTL =3 ,a n dd i s t r i b u t i o nS 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. 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.

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 typ e of active, non-cryptography related attack, where insider nodes corrupt data at the application level (this is also known as pollution attack). In this Chapter 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 Chapter 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)w h o s ev e r t e x e sa r echecks 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] Yedidia | 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.

The major contributions of the Chapter 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-to-peer streaming[END_REF]). Furthermore, SIEVE requires small computational, storage, and communication costs for implementation.

Chapter 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]. This Chapter includes a richer set of experimental results and am o r ed e t a i l e da n a l y s i so ft h eo b t a i n e dp e r f o r m a n c ei n d e x e s ,w o r k e do u to na larger set of system settings.

The Chapter is organized as follows: Section 5.3 describes the system model we consider, Section 5.4 presents the SIEVE technique, Section 5.5 discusses the simulation methodology and the accuracy, reactivity, and robustness results we obtained, Section 2.2 summarizes other works related to SIEVE, finally Section 7.2 draws conclusions and outlines directions for future developments.

LT codes

LT co des have b een prop osed in [START_REF] Luby | LT codes[END_REF]a n dr e p r e s e n t so n eo ft h efi r s te m b o d i m e n t 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]itisshownthatselectingthenumber of blocks to be combined, termed as the packet degree d,accordingtotheRobust 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.I np a r t i c u l a r ,t h eo r i g i n a lc h u n kc a nb eo b t a i n e db ya n y node able to collect any set of M = K • (1 + ✏)codedpac k ets(ona v erage),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]i ti ss h o w nt h a tas i m p l em e t h o db a s e d on the recursive cancellation of equations corresponding to packets with degree 1, i.e. representing one original data blocks, guarantees the desired asymptotic performance.

A use case for SIEVE

In this Chapter we consider a MANET composed of N wireless nodes moving in ag i v e na r e a . As e to fN 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 based dissemination protocol

The rateless principle and randomness of LT codes (see Section 5.2)i su s e df o r 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 + ✏)c od e dp a c k e t sw i t h o u tr e q u i r i n g 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 Figure 5.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 + ✏)c o d e db l o c k so ft h ec h u n kh a v eb e e nb u ff e r e d ) ,t h e 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 one of the data chunk is selected, a novel LT co ded packet is enco ded and transmitted. A new co ded 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 Chapter we assume that a subset of P nodes, with

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]t oi d e n t i f ym a l i c i o u sn od e s .

LT codes verification mechanism

According to the dissemination strategy described in Section 5.3 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]t h ed e c o d e rk e e p sc a n c e l i n go u ta l lt h ea l r e a d yk n o w n 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 as e to fa l r e a d yk n o w np a c k e t s . I ft h i sc o n s t r a i n ti sv i o l a t e dt h ew h o l ec h u n ki s 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 Figure 5.2. The factor graph can be progressively created while decoding the chunks. In Figure 5.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 p oint of view of any deco ding no de, each uploader i can be in one of two hidden states x i =1orx i =0,dependingonwhetheruploaderi is or is not amaliciousnode. Eac hc hec kcanreportoneoft w oobserv ationsc I =0orc I =1 in case of negative or positive pollution detection, respectively.

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 Chapter 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] Yedidia | Understanding belief propagation and its generalizations[END_REF], that has been used to solve an u m b e ro fi n f e r e n c ep r o b l e m si nm a n yd i ff e r e n tfi e l d s ,e . g . ,i t e r a t i v ec h a n n e l 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]andcomputervision [START_REF] Freeman | Learning low-level vision[END_REF]tomen tionafew.

The BP algorithm can be used to estimate from the factor graph the so called variable marginals P (x i ) i2U , 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 .I nc a s e 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] Yedidia | 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 ,t h a ti sm e a n tt ob et h ep r o b a b i l i t y that uploader i is in state x,g i v e nt h ei n f o r m a t i o nc o l l e c t e dv i ac h e c k so t h e r 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 0 I : i 0 ∈ 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: 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:

m x Ii = X {x i 0 :i 0 2U I \i} P (c I |x i = x, {x 0 i : i 0 ∈ U I \ i}) Y i 0 2U I \i m x 0 i i 0 I ( 5
P (c I =1|{x i : i =1,...,k})= ( 0, if x i =0, ∀i 1, otherwise (5.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 (5.3)
Plugging the last two expressions into Equation (5.1)w ec a ns i m p l i f yt h ec h e c k pass computation as follows:

m x Ii = 8 > > > > > < > > > > > : Q i 0 2U I \i m 0 i 0 I if c I =0,x =0 0i f c I =0,x =1 1 - Q i 0 2U I \i m 0 i 0 I if c I =1,x =0 1o t h e r w i s e (5.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.5):

m x iI = Y I 0 2C i \I m x I 0 i (5.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)= Y I 0 2C i m x I 0 i (5.6)
We recall that the probability estimates given by Equation (5.5)a n d( 5.6)a r e 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 ,t h e nk e e p si t e r a ting using Equations (5.4)and(5.5). A reliable estimate of P (x i = x)iscomputed after a certain number of such iterations using Equation (5.6). In all the experiments reported in this Chapter 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 (5.4)a m o u n t s to |U I |-1m u l t i p l i c a t i o n s ,w h e r eo pe r a t o r|•| 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.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 (5.6)t a k e s|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,de pe n d in gonth ec h e c ks stored during a time window w,a nu p d a t e df a c t o rg r a p hG 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)arecomputedthroughBP .Thebeliefv aluesm 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 )≥ ⌘.E a c hn o d en keeps ac o u n t e rf o re a c ho fi t su p l o a d e rn o d e si:t h en o d e si nt h el i s to fs u s p e c t sa f t e r 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]w h e ns h o r tc y c l e sa r ea b s e n ti nt h ef a c t o rg r a p hG 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 ) i2U (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 ap o i n tw h e r et h en u m b e ro fc y c l e si n c r e a s e st o om u c ha n dl o w e r st h ea c c u r a c y 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 5.3 and 5.4.T h e 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 fast nodes moving at V fast 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 ac o n s e q u e n c ew eh a v eN = N fast + 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 exp eriments that terminate after 1 hour of simulated time. We used the independent replication method to obtain N EXP =3 0 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 still nodes; all N nodes contribute to the spreading of the information according to the policy described in Section 5.3.As u b s e to fn o d e s( P = P fast + 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 5.1.

Performance indexes

For each no de n in the system we define:

• p(n)anindicatorfunctionwhosevalueisequalto1ifnoden is not malicious and 0 otherwise; In each independent replication trial we compute the following averages:

• c n (t)
• c (i) (t)= P N n=1 p(n)cn(t) P N n=1 p(n) ,i .

e . ,t h ef r a c t i o no fh o n e s tn o d e st h a td e t e c t e dt h e attack and have a non empty R;

• a (i) (t)= 1 P P N n=1 p(n)cn(t)an(t) P N n=1 p(n)cn(t) ,i . e . ,t h ea v e r a g ea c c u r a c yo fh o n e s tn o d e sw i t h non empty R. When a (i) (t)=1i tm e a n st h a tall honest nodes with non empty R have correctly identified all malicious nodes;

• tsi (i) (x)= P N n=1 p(n)(t n,hit (x)-t n,trigger ) P N n=1 p(n)
,i . e . ,t h ea v e r a g et i m eh o n e s tn o d e sr equire 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)t h a tw ec a l lc o m p l e t e n e s s ,a c c u r a c y , 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)t o parameters w, T , T s ,andQ used by SIEVE as defined in Section 5.4.T ot h i se n d 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}.W ea n a l y z e da l l1 0 8c o m b i n a t i o n s and observed that SIEVE performance is most sensitive to the value w.

Figure 5.3 shows the performance indexes a(t), c(t), and tsi(x)forsomev alues of w,w h e nT = T s =1 0sa n dQ =1 0( a l l1 0 8c o n fi g u r a t i o n sy i e l d e ds i m i l a r results so we selected a representative set of curves 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 Subsection 5.5.1. We summarized the structural properties of G n in Table 5.2.I tc a nb en o t e d 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|)i n c r e a s e sa sw 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;forlargerv aluesthea v erage number of cycles in the factor graph increases and nullifies the increase of z C .

It can also be noted that c(t)approaches1afterabout4minutes;thebehavior 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 =60syieldsthelo w estv aluesforthetimetoiden tificationtsi(x) (all graphs for tsi(x)arecomputedforthemaxim umx 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 =60sasthev alueforallthefollo wingexperimen ts. 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 =5 s )a n dt h et h en u m b e ro fc h e c k st r a n s m i t t e dp e rs e c o n d si s 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 work: w =6 0 s , 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.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. .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 5.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. 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 ( Consider one data source s and a chunk c;c l e a r l y ,w h e ns has transmitted K • (1 + ✏)c od e dp a c k e t s ,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.T h efi n a l 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)d o e sn o tc h a n g eo v e rt i m e ) ;t h i st r a n s l a t e si n t o 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 5.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 5.10 we show results for c poll =0.75, 0.5 and p poll =1 ,c o m p a r i n gt h e mt ot h er e f e r e n c es c e n a r i o( a n a l y z e dw i t h 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 apositiv ec hec kobtainedb y a malicious node is forwarded as negative and viceversa. that this trick is ineffective: indeed, the only effect is a limited increase in the values of tsi(x). Figure 5.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 ,t h e yr e p l a c et h ea c t u a lu p l o a d e r so fa check with a set of honest nodes; the detection flag is marked as positive. Figure 5.13 shows SIEVE performance when p disparage =1andhonestnodes 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 5.14 we show results for up to P =1 0 0m a l i c i o u sn o d e si nt h es y s t e m( i na l lc a s e s , P fast = 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)v alues, 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 ✏.I ti sw e l lk n o w nt h a tL Tc o d e so v e r h e a dd e c r e a s e sa sK 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 5.15 shows results for K =5 0 ,S cb =1 0 0 0a n d K =200,S cb =250. Itcanbenotedthatsmallv aluesofK yield better accuracy and lower reaction times. Table 5.4 summarizes the structural properties of G n for different values of K. It can be noted K =50yieldsbothlo w era v eragen um berofnodesperc hec kand length four cycles.

As a side effect of using a smaller value for K,t h ep r o b a b i l i t yo fr e c e i v i n ga 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 =50and0.33forK =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 =3 2 |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 =5andT s = 15s (see Figure 5.4)turnsouttobe about the 0.5%.

One of the main requirements a solution for MANET must satisfy is to have al o wc o m p u t a t i o n a la n dm e m o r yc o s t . W em e a s u r e dt h ea v e r a g eC P Ut i m e 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 ,e a c ho n er e p r e s e n t i n g an arc of the factor graph (represented as the pair of identifiers (I,i)). Each

K |C| z U |U| z C length

Published works

The work on polluter identification, based on the SIEVE protocol and our Foun-tainApplication module for the ns-3 simulator has been originally published in "SIEVE: a distributed, accurate, and robust technique to identify malicious nodes in data dissemination on MANET" [START_REF] Gaeta | Sieve: a distributed, accurate, and robust technique to identify malicious nodes in data dissemination on manet[END_REF]. Subsequently it evolved further and the expanded evolution has been publised in journal "Exploiting rateless codes and belief propagation to infer identity of polluters in MANET" [START_REF] Gaeta | Exploiting rateless codes and belief propagation to infer identity of polluters in manet[END_REF]. CCN and CCN-TV

Overview

Content-Centric Networking (CCN) [START_REF] Jacobson | Networking named content[END_REF] is a promising data-centric architecture, based on in-network caching, name-driven routing, and receiver-initiated sessions, which can greatly enhance the way Internet resources are currently used, making support for a broader set of users with increasing traffic demands possible. The CCN vision is, currently, attracting the attention of many researchers across the world, since it has all the potential to become ready to the market, to be gradually deployed in the Internet of today, and to facilitate a graceful transition from a host-centric networking rationale to a more effective data-centric working behavior.

At the same time, several issues have to be investigated before CCN can be safely deployed at the Internet scale. They include routing, congestion control, caching operations, name-space planning, and application design. With reference to application-related facets, it is worth noticing that the demand for TV services is growing at an exponential rate over time, thus requiring a very careful analysis of their performance in CCN architectures.

To this end, in the present contribution we deploy a CCN-TV system, capable of delivering real-time streaming TV services, and we evaluate its performance through a simulation campaign based on real-world topologies.

Due to the relevant importance that content sharing applications are going to play in the upcoming future [START_REF] Systems | Cisco visual networking index: Forecast and methodology, 2010-2015[END_REF][START_REF] Ahlgren | Content, connectivity, and cloud: ingredients for the network of the future[END_REF], the Content Centric Networking (CCN) rationale [START_REF] Jacobson | Networking named content[END_REF]h a sb e e np r o p o s e da sap o s s i b l ew a yt od r i v et h ec u r r e n thostcentric Internet paradigm towards a novel content-centric behaviour. It is based on in-network caching operations, receiver initiated data exchange, hierarchical content naming, and native support to security and privacy.

In a CCN, contents are split in chunks which are requested using opposite

Interest messages, generated at the client side. Each Interest is then routed until it reaches a node which has, in its own cache, a copy of the requested item.

Then, this copy is sent, as a Data message, back along the path the Interest had gone through. Intermediate nodes can cache the Data before forwarding it to the next node (more details on the CCN working behavior is provided in Section 6.2).

Since its birth, the CCN vision has gained a warm attention from both scientific and industrial communities to discover the bounds of its real potential from different perspectives.

Many studies have focused on modeling and designing caching strategies and data-transfer performance such as in [START_REF] Carofiglio | Modeling data transfer in content-centric networking[END_REF]- [START_REF] Rossi | On sizing CCN content stores by exploiting topological information[END_REF]. In that direction, it is now clear that the cache size may have a major impact on the overall performance of a CCN even if finding an optimal caching strategy is still an open problem to address. With respect to congestion control issues, instead, recent studies shown as the classic additive increase multiplicative decrease algorithm, at the foundation of TCP, could be inherited by CCN, provided that some countermeasures are employed to limit unfairness issues that could arise among contents with different popularities [START_REF] Grieco | AIMD and CCN: past and novel acronyms working together in the Future Internet[END_REF][START_REF] Carofiglio | Joint hop-by-hop and receiverdriven interest control protocol for content-centric networks[END_REF]. Another very relevant topic in CCN research covers routing operations, which are essential to properly drive the dissemination of receiver generated Interest packets. To this end, the adoption of Bloom filters appears a promising solution [START_REF] Tortelli | CCN forwarding engine based on bloom filters[END_REF][START_REF] You | Dipit: A distributed bloom-filter based pit table for ccn nodes[END_REF]t h a tm e r i t sf u r t h e ri n v e s t i g a t i o n s .

Starting from this premise, it is evident that all facets of CCN are going to be afforded in an ebullient panorama of activities that cover both the underlying mechanisms within the protocol architecture and the design of content oriented applications and services.

With reference to application-related features, it is worth to notice that the demand for TV services is growing at an exponential rate over the time [START_REF] Systems | Cisco visual networking index: Forecast and methodology, 2010-2015[END_REF], thus requiring a very careful analysis of their performance in CCN architectures. Ap r e l i m i n a r ys t u d yp r e s e n t e di n [START_REF] Li | Time-shifted TV in content centric networks:the case for cooperative in-network caching[END_REF]a d d r e s s e st i m es h i f t e da p p l i c a t i o n so n l y , whereas live streaming operations are currently under investigation as testified in the interesting contribution [START_REF] Xu | Live streaming with content centric networking[END_REF]. To complement the research efforts of the community in a so relevant domain, the present manuscript is intended to design a complete CCN-TV system encompassing all the main facets of typical live streaming video services.

The proposed CCN-TV has been tested through a solid simulation campaign based on real topologies. To this end, the ccnSim simulator [START_REF] Rossini | Large scale simulation of ccn networks[END_REF]h a sb e e np r o perly tailored to our purposes by adding window based flow control, handling of playout delay and real-time data, advanced logging functions, links with bandwidth constraints, and data session bootstrapping. Simulation results shown that in-network caching seems to play a minor role in live streaming video services, mainly because cached data looses its utility after the deadline is expired.

On the other hand, the way CCN handles client requests for TV contents helps improving the performance of the system with respect to a plain IP infrastructure.

The rest of the topic is organized as follows: Section 6.2 illustrates the core concepts of CCN. Section 6.3 describes the CCN-TV system we propose in this Thesis, which is then evaluated in Section 6.4. Finally, Section 7.3 summarizes the main findings of this contribution and draws future research.

Basic background on CCN

Internet usage has undergone a radical change during the last ten years: contentsharing applications are now dominant whereas the IP architecture still provides a connection-less service among remote hosts [START_REF] Ahlgren | Content, connectivity, and cloud: ingredients for the network of the future[END_REF]. Users ask for contents, looking for what they intend to retrieve from the Internet while the language spoken by the underlying IP infrastructure provides answers on where a packet should be sent. This mismatch is actually overcome by a number of workarounds at different levels of the protocol stack, which, indeed, limit the overall efficiency of the Internet.

The so-called Future Internet represents a family of possible solutions to the aforementioned issues, embracing novel communication models that can better accommodate and fulfill users' requirements related to efficiency, security, support to mobility, and integrated media experience [START_REF] Ahlgren | Content, connectivity, and cloud: ingredients for the network of the future[END_REF].

At the present stage, many valid proposals for the Future Internet exist, such as the Publish Subscribe Internet Routing Paradigm, the 4WARD NetInf project, and the Cache-and-Forward Network Architecture, the Data-Oriented Network Architecture and the CCN approach [START_REF] Jacobson | Networking named content[END_REF][START_REF] Ahlgren | A survey of information-centric networking[END_REF], having different levels of compatibility with the IP paradigm.

Among them, the CCN vision looks promising since, besides being "datacentric", it can be gracefully integrated with today's IP-based Internet. In a CCN, all content is unambiguously identified by a hierarchical name, allowing users to retrieve information without being aware about the physical location of servers (e.g. IP address). Also, commu-nication is receiver-driven and based on content chunk ex-change, name-based routing, and self-certifying packets [START_REF] Jacobson | Networking named content[END_REF].

Nevertheless, the real performance bounds of a CCN and the actual benefits it can bring to the Internet are still not entirely known, mainly because there are many open issues that surround the CCN architecture, such as those related to: (i) routing, (ii) congestion control, (iii) strategy layer design, (iv) name space definition, (v) semantic layer, (vi) accurate models, and (v) fairness among heterogeneous applications and contents having different popularities.

As specified before, CCN communications are driven by the consumer of data and only two types of messages are exchanged (namely Interest and Data). A user may ask for a content by issuing an Interest,whic hisroutedwithintheCCN towards the nodes in posses of the required information, thus triggering them to reply with Data packets.

The routing operations are performed by the strategy layer only for Interest packets. Data messages, instead, just follow the reverse path to the requesting user, allowing every intermediate node to cache the forwarded content.

CCN adopts a hierarchical structure for names,w h i c hl e a d st oaname tree. In particular, it is formed by several components, each one made by a number of arbitrary octets (optionally encrypted), so that every name prefix identifies a sub-tree in the name space. An Interest can specify the full name of the content or its prefix, thus accessing to the entire collection of elements under that prefix.

Finally, since contents are exchanged based on their names, multiple nodes interested in a particular data can share it using multicast suppression techniques over a broadcast medium. Analyzing a CCN node, it is possible to identify three main structures [START_REF] Jacobson | Networking named content[END_REF].

• the Content Store (CS): a cache memory that can implement different replacement policies as Least Recently Used (LRU) and Least Frequently Used (LFU);

• the Forwarding Information Base (FIB): is similar to an IP FIB except for the possibility to have a list of faces1 for each Content Name entry, thus allowing Interest packets to be forwarded towards many potential sources of the required Data;

• the Pending Interest When an Interest packet arrives to a CCN node, the CS is searched to discover whether a data item is already available as an answer to be sent immediately back to the requesting user. Otherwise, the PIT is consulted to find out if others Interest packets, requiring the same content, have been already forwarded towards potential sources of the required data. In this case, the Interest's arrival face is added to the PIT entry. Otherwise, the FIB is examined to search a matching entry, indicating the list of faces the Interest has to be forwarded through. At the end, if there is not any FIB entry, the Interest is discarded.

On the other hand, when a Data packet is received, the PIT Table comes into play, which, keeping track of all previously forwarded Interest packets, allows to establish a backward path to the node that requested the data.

CCN-TV architecture

Unlike Video-On-Demand, real-time video distribution has to deal with a specific class of problems to ensure the timely delivery of an ordered stream of chunks. Video chunks have to be received in playing order and within a given time interval (the playout delay), before they are actually played, thus "expiring". A chunk not delivered before its expiration will result in degradation of the rendered video, impacting the end user Quality of Experience; the extent of the video degradation may vary depending on the video codec and the type of the lost frame. To solve these challenges, client nodes implement a receiving buffer queue where the chunks are stored in order, that is emptied while the video is being played. Therefore, any chunk not received before its playing instant becomes useless. To reduce the chance of chunk loss several mechanisms can be put in place to retransmit requests for chunks close to expiration. Furthermore, in modern codecs, such as H.264 [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF], there are different types of video frames, encoded using intra-frame or inter-frame techniques, each having a different level of importance. For example, the so called I-frames, derived using intra-frame compression techniques, actually represent a full video image, providing a fundamental reference for subsequent inter-frame encoded images.

With this in mind in CCN-TV we considered a network of nodes requesting different real-time video streams, identified by a channelID,servedbyoneormore broadcast server.

Unlike canonical UDP/TCP-based streaming, in CCN-TV each video chunk, identified by a progressive chunk number, has to be requested individually, via a dedicated Interest.

Although this might look costly at a first sight, CCN's routing mechanisms ensure that Interests for the same chunk do not propagate twice along the same routing path (unless under specific conditions, as explained in Subsection 6.3.2), and the caching strategy implemented by every node can make sure that Interests for the most popular contents are served before going through the whole routing path. Moreover, the Interest/data exchange allows for a natural flow control mechanism, where each node can request for new chunks just when the old ones have arrived.

Herein we thoroughly describe the design rationale and all the details of the CCN-TV system this Thesis targets. Specifically, in what follows, we present: the bootstrap phase, the flow control strategy, and the management of retransmitted Interest packets.

Channel bootstrap

One challenge we are faced with in a real-time scenario is to bootstrap the channel to be received. Bootstrapping a channel involves the operations of finding a routing path to the nearest channel provider and locating the first valid chunkID of the video stream. Due to video codec requirements, the video stream can be visualized only once the first I-frame has been received. Therefore, a client has to first gather from the server the first chunk (and the corresponding chunkID) of the last generated I-frame. To do so, it sends an Interest packet for the URI: [domain]/[channelID],w i t ht h eStatus field set to BOOTSTRAP and the Nonce field set by the client, as in in Subsection 6.3.4. An Interest with Status = BOOTSTRAP would travel unblocked until it reaches the first good stream repository (i.e. a node who can provide a continuous real-time flow of chunks, not just cached ones). To this Interest,t h es e r v e rr e s po n d sw i t had a t am e s s a g ei nt h ef o r m a t[domain] / [channelID] / [chunkID],w i t hchunkID being the first chunk of the last generated I-frame, and the corresponding Frame ID field value. Upon receipt, the node starts asking for subsequent chunks, using the sliding window mechanism detailed in Subsection 6.3.2.T h eu s eo fanonce (a uniquely generated identifier) in the Interest URI allows the Interest to propagate to the server without being blocked along the routing path, as every bootstrap Interest for the same channel has a different nonce. It also avoids the retrieval of the data response from the cache of an intermediate node; the risk, in this case, is the retrieval of aboo t st r a pda t ames s a g efo rag i v enc h a n n elf r o maca c h eco n t a i n i n ga na l r e a d y expired chunk of an I-frame.

ward denoted as windowTimeout.

3. Transmit, for each slot that got freed by the received or expired chunks, the

Interest for a new one. #S e n dInterests for new chunk 16:

NNC ← W -size(PW)

17:

for i ← 1,NNC do 18:

send(Int(LC)) end for 23: end procedure Figure 6.2: Sliding window algorithm Furthermore, the same operations are performed if a node doesn't receive any data for at least windowTimeout seconds, in which case, all the Interests for non-expired chunks in the Pending Window are retransmitted, together with new chunks if new slots have been freed due to expired chunks. Figure 6.2 details the implemented algorithm; for the purpose of brevity and readability, the variable names have been contracted: PW is the Pending Window, W is the aforementioned system parameter, indicating how many Interests should a node have ongoing, WinT is the window timeout, after which Interests in the Pending Window are resent, Int is a new Interest message, CID is a chunkID in the pending window, lastTx is the transmission time of the most recent Interest for a given chunkID, LC is the chunkID of the most recent requested chunk and NNC is the number of new chunks to request, after the pending window has been purged.

To provide a further insight, we reported in Figure 6.3 an example of the conceived sliding window algorithm, in which we have set the value of W to be equal to 3.

Interest routing

As described in Section 6.2, CCN nodes along the routing path of an Interest will stop the propagation of said Interest,i ft h e yh a v ep r e v i o u s l yr o u t e da n o t h e r Interest for the same resource, and the correspondent data has note been sent back yet; instead, they will simply update their Pending Interest Table adding the face from where this newcomer Interest was originated, so to reroute the data back recursively along the path the Interest has gone through. This mechanism ensures flow control and limits the propagation of duplicate Interests,i nc a s es e v e r a ln od e si nt h es a m en e t w o r ka r ew a t c h i n gt h es a m ec h a nnel.

However, to make the Interest retransmission mechanism effective, a retransmitted Interest needs to propagate all the way up to the server, or to the first node with the desired chunk in cache. Therefore, retransmitted Interests carry the Status field set to Retransmission to mark if the Interest is a retransmission or not, and each node along the routing path propagates the Interests marked as retransmitted, thus skipping the usual CCN mechanism, unless the correspondent chunk is found in the cache.

Signature

Optional (for increased content authentication).

Stale Time

Set to the frame time of the frame the chunk belongs to. Frame ID ID of the frame the chunk belongs to.

Data

The request video chunk binary data.

CCN-TV messages

As detailed above, additional functionalities required by the system for real-time video streaming are implemented on top of existing CCN data and Interest messages via new fields carrying the required additional information. However, should the situation require the system to conform to classical CCN messages, all additional fields can be easily replaced by additional fields in the content name. Table 6.1 shows how we made use of the classical CCN message fields, together with the new fields and their use.

In particular, CCN-TV Interests carry an additional Status fields marking if the Interest is a bootstrap Interest (Subsection 6.3.1), a normal one or a retransmission (Subsection 6.3.3).

Concerning CCN data message, we extended the messages with an additional field, i.e., Frame ID, containing the ID of the frame to which the embedded chunk belongs to.

Simulation results

In this Section, we will evaluate performances of the proposed CCN-TV architecture. To this end, we implemented it within ccnSim,i . e . ,a no p e ns o u r c ea n d scalable chunk-level simulator of CCN [START_REF] Rossini | Large scale simulation of ccn networks[END_REF] built on top of the Omnet++ framework [3], dedicated to the evaluation of Video On Demand systems on top of CCN.

By itself, ccnSim models a complete video distribution systems, with a high degree of fidelity concerning catalogs, requests and repositories distribution, and network topologies. Since, however, it did not support the real-time constraints required by our evaluations, it has been modified and improved in the following ways:

• we added support for links with bounded capacity and packets with a well defined size, which was missing in ccnSim,tobeableandestimatetheCCN behavior under some bandwidth constraints;

• due to the datarate channels, we implemented a transmission queue for each face of each node, in order to properly manage the packet transmission;

• we added the support for synthetic video traces, so to be able to transmit and receive chunk of real videos, and consequently being able to reconstruct the received video and evaluate its PSNR;

• due to possible expiration of Interests,w ei m p l e m e n t e dac l e a n u pm e c h anism for each node's PIT, to avoid having in long term stale entries due to expired chunks;

• we improved and enriched the logging system, so to be able to record each node's received chunks and reconstruct the received video;

• we added more controls server-side, to send a data only for those chunks who have already been generated.

Furthermore, the following mechanisms, b eyond the provided ones, have b een implemented in the simulator:

• the sliding window mechanism described above, and all the related data structures;

• the Interest forceful propagation in case of retransmission;

• constant data reception, until a channel is changed.

The extended ccnSim simulator is available at [START_REF] Vv | Ccn-tv home page[END_REF].

The aim of our study is to evaluate how the behavior of the CCN-TV system is influenced by (i) the amount of the network bandwidth dedicated to real-time streaming services, (ii) the windowTimeout adopted by the sliding window mechanism, (iii) the playout delay, and (iv) the cache decision policy.

We focus the attention on the GEANT network, which interconnects the European research and education institutions and it is composed by 22 routers [START_REF] Vv | Geant project website[END_REF]. Every node of the network is considered to be a direct CCN node, i.e. no TCP or UDP encapsulation is implemented.

We assume the presence of only one small video streaming provider that offers 5p a r a l l e lr e a l -t i m et r a n s m i s s i o n st or e m o t ec l i e n t s . It is connected to one of the nodes forming the GEANT topology. In every simulation round, each video content is mapped to a video stream compressed using H.264 [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF]ataaveragecodingraterandomlychosenintherange [250,2000]kbps.

Clients, i.e., CCN nodes that download video contents from the server, are connected to remaining nodes (1 client per node). In order to catch the behavior of people watching TV, we modeled two groups of users: faithful and zapping. Faithful users are attached to one video channel for the whole simulation. Zapping users, instead, change frequently the channel among those offered by the server according to a Poisson process with parameter λ =0.0666.

Further, the channel selection process has been modeled considering that contents popularities follow a Zipf distribution, according to [START_REF] Rossi | Caching performance of content centric networks under multi-path routing (and more)[END_REF], the most of works presented in literature set the parameter ↵ of the Zipf distribution in the range [0.6, 2.5]. In line with these common settings, we set ↵ =1 .

Once a client decides to watch a specific channel, it performs the bootstrap process described in the previous Section and then starts sending Interest packets following the designed sliding window mechanism.

In our tests, we adopted the optimal routing strategy, already available within the ccnSim framework. According to it, Interest packets are routed towards the video server along the shortest path. On the other hand, three caching strategies have been considered in our study: no-cache, LRU,a n dFIFO [START_REF] Rossi | Caching performance of content centric networks under multi-path routing (and more)[END_REF]. When well known LRU or FIFO policies are adopted, we set the size of the cache to 100 chunks. The no-cache policy is intended to evaluate the performance of the CCN without using any caching mechanism.

The window size W has been set to 10, ensuring that faces of the server are almost fully loaded in all considered scenarios. Also, the transmission queue length associated to each face, Q,h a sbe e ns e t ,i no r d e rt obel a r g e rt h a n

Q =2• L c • P D (6.1)
where L c and P D represent link capacity and maximum propagation delay in the considered network topology. All simulation parameters have been summarized in Table 6.2.

Interest generation process

As a first step, we investigate the impact that the sliding window mechanism has on the amount of sent Interest packets, which is shown in Figure 6 of Interest messages sent by end users. When the windowTimeout increases, the probability that a given client does not receive any chunks within such a time interval decreases and, as a consequence, also the number of retransmitted Interest packets decreases as well. As a further confirm of this result, Figure 6.5 shows that the percentage of duplicated Interest packets increases when the windowTimeout decreases due to a high number of chunks that are unable to reach the client within the expected timeliness. As expected, the playout delay has a minor impact on the number of generated Interest messages, which, as is known from the theory on sliding window mechanisms [START_REF] Kurose | Computer Networking: A Top-Down Approach[END_REF], can be only influenced by window size (W )andwindowTimeout.

Also, caching operations do not have any significant impact on the number of generated Interest messages. The main reason being that chucks stored in cache memories lose their effectiveness after their deadline is expired.

On the other hand, the link capacity greatly influence the Interest transmission rate. From Figure 6.4 emerges, in fact, that the number of Interest lowers when the capacity of links decreases. This is because a limited bandwidth reduces the quota of received chunks, thus preventing a rapid advancement of the sliding window. In other terms, this result proves, once again, the effectiveness of the sliding window mechanism in CCN.

QoS and QoE

The first important parameter that describes how CCN-TV settings affect the quality of service offered to end users is the chunk loss ratio, which represents the percentage of chunks that have not been received in time (i.e., before the expiration of the playout delay)b yc l i e n t s .

From Figure 6.6,s h o w i n gt h ec h u n kl o s sr a t i om e a s u r e di na l lc o n s i d e r e d network scenarios, we note that playout delay plays a fundamental role. When the playout delay increases, in fact, the client could receive a Data packet within a longer time interval, thus reducing the amount of chunks discarded because out of delay.

On the other hand, a slight increment of the chunk loss ratio can be registered by increasing the windowTimeout.I ft h ec l i e n tr e t r a n s m i t sa nInterest packet after long time, there is the risk that the Data packet will be reached by the destination after the expiration of the playout delay.

In addition, we note that a reduction of the link capacities leads to a higher number of lost chunks, due to increased latencies induced by network congestion.

It is very important to remark that the presence of the cache can guarantee only a small reduction of the chunk loss ratio. With our study, we found that, in the presence of real-time flows, the cache does not represent an important CCN feature.

On the other hand, we noticed that the PIT plays a more relevant role. In fact, in presence of live video streaming services, clients that are connected to a channel request the same chunks simultaneously. In this case, a CCN router has to handle multiple Interest messages that, even though sent by different users, are related to the same content. According to the CCN paradigm, such a node will store all of these requests into the PIT, waiting for the corresponding Data packet. As soon as the packet is received, the router will forward it to all users that have requested the chunk in the past.

Following to these considerations, the use of the cache will not produce a relevant gain of network performances. Indeed, the PIT helps reducing the burden at the server side by avoiding that many Interest packets for the same chunk are routed to the server.

To conclude our study, we have computed Peak Signal to Noise Ratio (PSNR), which is nowadays one of the most diffused metrics for evaluating user satisfaction, together with interactivity level, in real time video applications [START_REF] Piro | Two-level Downlink Scheduling for Real-Time Multimedia Services in LTE Networks[END_REF]. Results shown in Figure 6.7 are in line with those reported for chunk loss ratio (the PNSR is higher in the same case in which the chunk loss ratio is lower). Again, link capacity greatly influences the quality of the TV service provided to users. According to [START_REF] Ohm | Multimedia Communication Technology[END_REF], the obtained PSNR values can be translated to a Mean Opinion Score (MOS) not less than 4, corresponding to satisfactory quality for almost all users.

Published works

Our implementation of the CCN protocol to implement a real-time video streaming architecture has been originally published in the article "CCN-TV: a datacentric approach to real-time video services" [START_REF] Ciancaglini | Ccn-tv: a data-centric approach to real-time video services[END_REF]a n das u b s e q u e n te x t e n s i o nh a s been requested as a book Chapter, integrating crowdsourced content in the infrastructure and analyzing the strong and weak points and performances. The book chapter, "Providing crowd-sourced and real-time media services through a NDN-based platform" [START_REF] Piro | Providing crowd-sourced and real-time media services through a ndn-based platform[END_REF], has been accepted and is currently awaiting publication.

Part III

Summarizing results and future evolutions

Chapter 7

Summarizing results and future evolutions

Chapter abstract:

In this Chapter we summarize the obtained results in the examined topics and discuss possible and ongoing future evolutions of the works.

For each topic a paragraph presents a sum of the results and evolutions explained in more details in Chapters 4 for Section 7.1, 5 for Section 7.2,a n d6 for Section 7.3. Furthermore Section 7.4 details an ongoing work to unify the above works for a robust CCNbased mobile network coded approach.

Random graph modeling of overlay networks interconnection

Using our random graphs based model for network interconnection we were able, after validating it with results obtained with a simple simulator, to generate all results in a given interval of parameters so to analyze, for various configurations and interconnections sets, the most efficient parameters to use. Using the homogenous initial version the results were promising, yet still limited in real case scenarios by the model own limits. We then removed those limits in developing the model heterogeneous version, providing for different configuration for each interconnected network.

While in the first case we were only able to demonstrate how, given the same configuration for all networks, the efficacy of the searches and the number of messages sent varied globally with changing parameters, with the second version of the model we were able to also study the influence of different interconnection topologies between the various network and more in depth the case where a single network contains the desired resource and is then connected to a previously established interconnected network, analyzing the resource diffusion and best parameters to use for maximize availability.

In this Thesis 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 mo del 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.

We are currently working, to be published following to this Thesis, to an heterogeneous evolution to the model, where each interconnected network does have its own interconnection degree distribution and resource availability. As such queries can be initiated from each network i obtaining the pertinent hit probability p i hit and average number M i of generated messages. Due to the highly abstract modelization of the networks and their relations, the model, especially the heterogeneous one, can be used to investigate different sce-narios. We choose to analyze in an ongoing work the interconnections of social networks, considering each social network as network in the model, the user's contacts as the interconnections between nodes and the same user on different social networks as the "bridge" nodes interconnecting the networks. Each query TTL is the number of jumps through the user contacts, and contacts' contacts, until the desired content is reached.

Polluter identification in MANETs

The results obtained are very encouraging: even in a completely decentralized and destructured ad-hoc mobile network, the list of most probable polluters correctly identifies all the active polluters in a reasonable amount of time with a very high accuracy.

Even if the detection occurs after a few decoding sessions have gone bad and usually takes in the order of a few minutes we have to consider that in the chosen encoding scheme there is simply no way to know if a chunk is corrupted until its decoding, and even then there is no way to directly identify which packet or packets were responsible for poisoning the blocks pool.

The results are even more positive when we analyze the robustness of the protocol to coordinated attacks, basically polluters coordinating to send coherent false checks or even worse accusing one or more specific non polluter nodes to be in fact malicious. If no more than half of the total nodes are malicious (a quite reasonable assumption) the protocol maintains its efficiency, correctly identifying all and only the polluter with a relevant margin of certainty, and only taking more time to correctly guess all of the polluters, even in unrealistically negative situations (a significant percentage of the nodes are polluters and they all coordinate, while the honest nodes aren't even aware of the neighbor presence).

Besides the protocol, being based on the Belief Propagation algorithm of obtained decoding observations is low in computational complexity, so even well suited for mobile and battery limited devices, and easily adaptable to other dis-tributed transmission protocols, as far as a relative check is produced during or after the decoding process.

In Chapter 5 we have proposed the novel SIEVE technique for the identification of malicious nodes performing a pollution attack within a MANET. Ad a t ad i s s e m i n a t i o na p p l i c a t i o nb a s e do nt h ed i s t r i b u t i o no fL Tc o d e dd a t a 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 deco ding pro cedure can b e used by each no de 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 Chapter. 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 b e fo cused 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.

The approach by itself is flexible and efficient, as shown by our results, so future works will work toward the two complementary directions of raising the SIEVE accuracy by better analyzing the underlying graph and devising ways to followup to the detection of polluters, so to pass the useful pollution detection informations generated by SIEVE to a pollution avoidance mechanism which will use such informations to actively avoid (or neutralize) polluters.

CCN and CCN-TV

Using a custom modified ccnSim simulator [START_REF] Vv | Ccn-tv home page[END_REF][START_REF] Vv | ccnsim home page[END_REF], itself a modified version of the Omnet++ network simulator [3], we simulated a network, based on the structure of the GEANT network, composed of CCN-TV nodes (meaning no TCP or UDP encapsulation) with one video streaming server offering 5 different streams with specific video parameters and a variable number on clients of two types faithful, sticking to one channel, and zapping,m o v i n gf r o mo n ec h a n n e lt oa n o t h e rw i t h ag i v e nf r e q u e n c y .

Routing Tables, handled by ccnSim, are always shortest path optimal and we tested with three different caching strategies for the intermediate nodes no cache, LRU and FIFO and a cache size of 100 chunks.

The results permitted us to show that the approach is working and to evaluate the behavior at the variation of the sliding window timeout for the clients and its impact on the Quality of Service by measuring chunk-loss. We also found that in the presence of real-time streams the cache actually reduces the chunk-loss only to a small amount, owning to the PIT structure already distributing multiple request over a single reply, and a very minute amount of subsequent requests for the same content.

Confronted with a classical CCN approach the CCN-TV alternative of not sending Interestsf o re v e r yData allows a sensible amount of bandwidth saving, leading to better performances and user experience.

In this work, the effectiveness of TV services in a CCN has been investigated. To this end, the ccnSim simulator has been modified to add several relevant features such as window-based flow control, handling of playout delay and realtime data, advanced logging mechanisms, and data session bootstrapping.

Preliminary results reported herein clearly show that the most relevant CCN feature to TV services is the management of Interest packets through the PIT data structure. In fact, such a mechanism limits the number of requests for the same chunk at the server side for multiple clients watching the same TV channel, thus decreasing the link and the computational load at the server.

Further research will explore: wider scenarios with many users and available channels, advanced optimization techniques for TV services in CCN (including routing and congestion control), and the adoption of scalable video coding. Moreover, a more deeply investigation on the relevance of the cache and the PIT in live TV services will be also conducted.

The CCN protocol, while facing many problems to be solved before becoming aw i d e s p r e a dg e n e r a ln e t w o r kp r o t o c o l( t h ep r o m i s e dF u t u r eI n t e r n e tP r o t o c o l ) , does indeed offers many advantages as presented in this work. Future works in the real-time video streaming field will fo cus on b etter understanding the behavior of larger networks with heterogeneous characteristics (mobility of nodes, link speeds and latency, ...) and multiple simultaneous video streams.

Rateless coding over mobile CCN

All the previous approaches examine a single solution to the wider problem of increasing robustness and resilience in a distributed decentralized scenario, either by employing particular encoding not penalized by lack of structural informations or message losses, by exploiting pollution detection techniques suited for a completely decentralized and inherently non trusted network, and by more efficient routing techniques based on contents rather than addresses.

Uniting those techniques together, especially introducing mobility to the CCN paradigm, and studying their perks and flaws is indeed an interesting and very applicable evolution, one that we present here as an initial study in such direction.

We called our approach "Rateless coding over mobile CCN" as a mean to define an open protocol to let use define and analyze the interaction between mobility, particular encodings and the CCN protocol.

As pointed out, decentralized ad-hoc mobile networks are of growing importance and interest nowadays. Yet the troubles they face, both in performance and robustness, requires innovative approaches in order to overcome what are currently the most central obstacles to wide adoption and deployment, as for example in urban traffic information scenarios or rural spontaneous network formation where infrastructures are lacking.

Introducing the element of mobility in a communication network greatly complicates the strategies used to ensure a reliable communication with satisfying performances as it directly reduces to ability to create a durable routing tree and trust in the neighbor nodes.

If the mobility also comprises from seldom moving slow nodes like hand-held laptops to continuously unpredictable fast moving nodes, such as vehicles then we can see that many wireless mesh protocols gradually becomes less and less efficient by losing their ability to grow a continuos path from source to destination, even if for the duration of a single transmission.

Promising old and new technologies like network coding and decentralized polluters detection has been shown in Chapter 5 to be robust and efficient, especially given the specific constraints of the scenario, while other like CCN can relay more on the contents rather than the inherently abstract address informations, as shown in Chapter 6.

Considering CCNs/NDNs the concept of introducing an underlying mobility aspect has been present since their conception [START_REF] Zhang | Named data networking (ndn) project[END_REF].

Various relevant work has already been done on pairing mobility with CCNs, both as general application study [START_REF] Tyson | A survey of mobility in information-centric networks[END_REF], or specifically in MANETs [START_REF] Zhu | A new perspective on mobility support[END_REF][START_REF] Lu | Information-centric delay-tolerant mobile ad-hoc networks[END_REF].

It is generally accepted that CCNs are well suited for mobile environments, needing few, if any, modification, and very resilient based on their focus on nodes IDs rather than addresses. For real-time, low latency applications however some structural decisions must be evaluated carefully during implementation, as they can impact heavily on the resulting performances.

Regarding coupling network coding with CCNs there are a few works available, all focusing on the central idea of augmenting data availability by multiple seeding from different sources [START_REF] Liu | Multisource dissemination in contentcentric networking[END_REF][START_REF] Miyake | Network coding and its application to content centric networking[END_REF][START_REF] Wu | Codingcache: multipath-aware ccn cache with network coding[END_REF]. All these approaches are shown to be valid and a substantial increase in performances over the non-coded case, yet to the best of our knowledge none of them considers a mobile topology, which could heavily influence the obtained results.

Fo cusing on p ollution detection and malicious no des attacks to the b est of our knowledge the current literature is a lot smaller in size, concentrating on specific attacks similar to the IP-based ones [START_REF] Wang | Rdai: Router-based data aggregates identification mechanism for named data networking[END_REF][START_REF] Wang | Modeling denial-ofservice against pending interest table in named data networking[END_REF]o rm o r ei n h e r e n tt ot h eC C N protocol structure [START_REF] Conti | A lightweight mechanism for detection of cache pollution attacks in named data networking[END_REF]. All of those approaches focuses on directly identifying corrupted data once received, which will not be usually possible using rateless coding, rendering them unapplicable in our case, at least without modifications.

We are analyzing, via a simulator, the b ehaviors and p erformances of different common ad-hoc routing protocols [START_REF] Lee | A performance comparison study of ad hoc wireless multicast protocols[END_REF], specifically OLSR, DSDV, AODV, and a custom flooding based one, over a mobile nodes wireless network, while they are exchanging data using the CCN protocol of Interest/Data to request and receive packets encoded using network coding, via our FountainApplication module for the ns-3 simulator.

We are also implementing different scenarios, varying in the ratio of slow and fast moving nodes, the number of different sources presents, as well as the caching and rebroadcasting policies adopted, to better identify strong and weak points of each routing protocol when underlying the CCN + coding protocol.

Finally we plan to briefly analyze the detection of malicious polluter nodes in our set using our SIEVE protocol, in a completely distributed and accurate way.

Preliminary results on the topic are positive, where the CCN model is confirmed to be well suited in distributed mobile environments, and initial implementation of network coding can greatly increase the data throughput, even in very sparse and fast moving scenarios.

Yet further work is still needed, and ongoing, to b etter evaluate the interaction between those aspects and the parameters influencing coding behaviors to avoid degraded performances or excessive noise. The tool has been realized to read all the parameters regarding the instance from the json file, such as the number of distinct networks, the TTL values to be calculated, the ↵ i resource distribution, C i,j fraction of nodes that also belong to network j,t h eP i,k distribution for the number of connection of each node, and pf t,i,j or pf i,j ,d e p e n d i n gi fi tv a r i e sw i t ht h eTTL t or not, probability that a node will forward a message from network i to j,f o re a c hn e t w o r ki. With the optimizer, so called as it permits to sweep the space of all parameters permutations in a feasible time in respect to a simulator and so to choose the optimal values range, an entourage of related small tools has been developed, such a configuration generator, able to generate ranges of json file iteratively, sets of shell scripts to automate as much as possible the "generate, calculate and parse" standard iter and also helping parse and group the obtained result files, and the relative tools and file format documentation.

A.2 Network simulator ns-3

• Tool name: ns-3

• Tool authors: M. Lacage, and various authors • License: GNU GPLv2

• Website: http://www.nsnam.org ns-3 is a discrete-event network simulator, targeted primarily for research and educational use.

The software is a C++ library which provides a set of network simulation models implemented as C++ objects and wrapped through Python. Users normally interact with this library by writing a C++ or a Python application which instantiates a set of simulation models to set up the simulation scenario of interest, enters the simulation "main loop", and exits when the simulation is completed (i.e. no more events are planned in the schedule).

A through and detailed description of the various APIs is present on the official site, togheter with a very helpful tutorial for initially understanding the basic internal organization of the modules.

A.2.1 The FountainApplication application

• Tool name: FountainApplication (ns-3 module)

• Tool authors: R. Loti

• License: GNU GPLv2 (Currently not released to the public)

• Website: Software available on request Over the ns-3 models system we wrote the FountainApplication module, as an Application in ns-3 terms.

A Node with a FountainApplication configured on it can, depending on the parameters passed, work both as client and server for receiving and decoding, and encoding and sending chunks, using a specified decoder:

• 0( F a k e ) :no actual decoding happens, the payload is considered decoded after n + ✏ packets have been received, where the overhead ✏ is specified based on statistical patterns relative to n;

• 1 (Linear): only packets of degree d =1 ,s oc o n t a i n i n ga nu n c o d i fi e d block in the payload, are considered, waiting for one of each of the n blocks. Equivalent to a standard n-blocks sequential transmission;

• 2 (Belief Propagation): the packets payload is decoded using the Belief Propagation algorithm, less efficient than the following, but also less computationally intensive;

• 3( O F G ) :the packets payload is decoded using the very efficient, but computationally intensive On-The-Fly Gaussian Elimination algorithm, based on the simpler, yet less flexible GE (Gaussian Elimination) algorithm;

or encoder:

• 0( F a k e ) : no actual encoding happens and so the payload is actually of a specified size, but empty, only populating the header. Usually used in conjunction with the fake decoder to avoid loading the simulator with big quantities of data;

• 1 (Sequential): only packets of degree d = 1 are generated, while the block order is random and not guaranteed to be sequential or non repeating before afulln blocks transmission is functionally similar to a standard, sequential data transmission;

• 2 (LT Code): standard encoding for LT Codes, using a RSD distribution ar a n d o md e g r e e1 d  n is chosen and as many distinct blocks in n are randomly selected to be xor -encoded in the payload.

A.2.2 The SieveApplication application

• Tool name: SieveApplication (ns-3 module)

• Tool authors: R. Loti

• License: GNU GPLv2 (Currently not released to the public)

• Website: Software available on request

In parallel with FountainApplication, but independent from it, we developed the SieveApplication module, also as a ns-3 Application type.

The application access the methods of the FountainApplication class to retrieve received and decoding statistics from each Node that has the application installed to pass to the SIEVE algorithm to progressively build the probable polluter list.

A.2.3 The ndnSIM module

• Tool name: ndnSIM (ns-3 module)

• Tool authors: A. Afanasyev, I. Moiseenko, and L. Zhang

• License: GNU GPLv2

• Website: http://ndnsim.net

The ndnSIM is a ns-3 module that implements the Named Data Networking (NDN) communication model [START_REF] Afanasyev | ndnSIM: NDN simulator for NS-3[END_REF].

ndnSIM is specially optimized for simulation purposes and has a cleaner and more extensible internal structure comparing to the existing NDN implementation (NDNx) as it works internally to ns-3, not as an external library as the DCE-ccnx module (a similar module for ns-3 in which a software "cradle" integrates the real ccnx library, see Section A.3), and in which every part of the protocol is independent and implemented as a distinct, and easily modifiable, submodule.

A.3 The CCNx protocol and library

• Tool name: CCNx • Tool authors: V. Jacobson, and various authors • License: GNU GPLv2, and GNU LGPLv2

• Website: https://www.ccnx.org

The CCNx protocol is the transport protocol for a communications architecture called Content-Centric Networking (CCN) built on named data.

CCN has no notion of host at its lowest level as a packet address names content, not location. The CCNx protocol efficiently delivers named content rather than connecting hosts to other hosts. Every packet of data may be cached at any CCNx router which combined with intrinsic support for multicast or broadcast delivery this leads to a very efficient use of the network when many people are interested in the same content. • Website: http://perso.telecom-paristech.fr/ ~drossi/index.php?n= Software.CcnSim ccnSim is a scalable chunk-level simulator of Content Centric Networks (CCN), written in C++ using the Omnet++ simulator as a base, which allows to assess CCN performance in scenarios with large orders of magnitude for CCN content stores and Internet catalog sizes, due to the focus on higher level workings than, for example, ns-3 [START_REF] Weingartner | A performance comparison of recent network simulators[END_REF].

In our works on CCN-TV we extended the ccnSim simulator to include our extensions of the protocol needed for live-tv streaming, but we maintained the efficient definition and mechanisms for routing and network structure.

4. 1 5 . 7 76 6. 1

 157761 Example of two P2P interconnected networks (X =2 )a n do n e degree 2 Synapse that belongs to both . . . . . . . . . . . . . . . 4.2 p hit for different ↵ and s i (left) and alternative search algorithm (right) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Routing policies comparison: p hit for different resource popularities ↵ ................................... 4.4 Average number of messages for different routing policies . . . . . 4.5 s i comparison at different f ..................... 4.6 Performance evaluation with different numbers of overlay X ... 4.7 Distribution of different routing policies with fixed f ....... 4.8 Distribution of different routing policies with fixed s 1 (left) and message evaluation at different ↵,fordifferentroutingpolicies(right) 5.1 Node operations: LT encoding, decoding and dissemination protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Example of factor graph . . . . . . . . . . . . . . . . . . . . . . . 5.3 Representative accuracy (left), completeness (middle), and time to identification (right) of SIEVE as a function of w ......... 5.4 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for best performance, lower energy consumption, and compromise setting . . . . . . . . . . . . . . . . . . . . . . . 5.5 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different nodes mobility models . . . . . . . 5.6 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different nodes speeds in the reference scenario v Accuracy (left), completeness (middle), and time to identification (right) of SIEVE where moving nodes range from all fast to all slow 66 5.8 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE where malicious nodes are either all fast or all slow 67 5.9 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different pollution intensities at the coded block level (p poll ). . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.10 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different pollution intensities at the chunk level (c poll ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70 5.11 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different lying intensities . . . . . . . . . . . 71 5.12 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for p lie = 1 and increasing number of malicious nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.13 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different disparaging attacks . . . . . . . . . 73 5.14 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for increasing number of colluding malicious nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.15 Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different values of K ............. Bootstrap handshake . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.2 Sliding window algorithm . . . . . . . . . . . . . . . . . . . . . . 85 6.3 Sliding window example . . . . . . . . . . . . . . . . . . . . . . . 86 6.4 Total number of Interest packets sent by clients with playout delay of (a) 10s and (b) 15s . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.5 Percentage of duplicated Interest packets sent by clients with playout delay of (a) 10s and (b) 15s . . . . . . . . . . . . . . . . . . . 94 6.6 Chunk loss ratio with playout delay of (a) 10s and (b) 15s . . . . 94 6.7 PSNR of the Y components of received videos with playout delay of (a) 10s and (b) 15s . . . . . . . . . . . . . . . . . . . . . . . . . 95

  Part I, Chapter 2 briefly introduces the state of the art for each topic, Chapter 3 will give a perspective of each work contribution to each topic. In Part II, Chapters 4 to 6 more deeply analyze each topic, offering a technical analysis of the contribution and results obtained, and in Part III, Chapter 7 summarizes the conclusions obtained from the results and future evolutions.

Figure 4 . 1 :

 41 Figure 4.1: Example of two P2P interconnected networks (X =2)andonedegree 2S y n a p s et h a tbe l o n g st obo t h

Figure 4 . 2 :

 42 Figure 4.2: p hit for different ↵ and s i (left) and alternative search algorithm (right)

Figure 4 . 2 (

 42 Figure 4.2 (left) shows a comparison between the computed p hit for different values of ↵ and the corresponding simulation results, while Table4.3 summarizes the same comparison for m.T h er e s u l t ss h o wt h a tb o t hp e r f o r m a n c em e t r i c sf a l l within the confidence interval of the simulation results.Furthermore, we validate the system against the alternative search algorithm detailed in Subsection 4.3.5.F o rt h es a k eo fb r e v i t y ,w ea r es h o w i n gr e s u l t so n l y for S 2 since the same conclusions can be drawn for S 1 and S 3 . Figure4.2 (right) shows both p hit and m against different values of ↵,s in c ew ithth isalgo rith mth e 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 different 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.

Figure 4 .

 4 3 show the values of p hit for the 3 different policies and different resource popularities, while Figure 4.4 depicts the average number of messages for the 3 policies in the case of propagation of queries up to TTL hops (Figure 4.4(b))andforthequerypropagationthatstopswhenreac hinganodeholdinga copy of the resource (Figure 4.4(a))m o d e l e di nS u b s e c t i o n4.3.5.I nt h ef o r m e r

Figure 4 . 3 :

 43 Figure 4.3: Routing policies comparison: p hit for different resource popularities ↵

Figures 4 .

 4 5(a) and 4.5(b)

  Query propagation of Subsection 4.3.5

Figure 4 . 4 :

 44 Figure 4.4: Average number of messages for different routing policies

Figures 4 .

 4 6(a) and 4.6(b)

X

  =5,TTL =2,↵ = 10 -4 , Routing=zmax f =2 f =3 f =4 (a) Hit probability p hit (b) Number of messages m

Figure 4 . 5 :

 45 Figure 4.5: s i comparison at different f

  Figure 4.7(b).

  ↵ = 10 -4 , Routing = zmax s1 =0.8 s1 =0.6 s1 =0.4 s1 =0.2 (a) p hit vs. X ↵ = 10 -4 , Routing = zmax s1 =0.8 s1 =0.6 s1 =0.4 s1 =0.2 (b) m vs. X

Figure 4 . 6 :

 46 Figure 4.6: Performance evaluation with different numbers of overlay X

Figure 4 . 7 :Figure 4 . 8 :

 4748 Figure 4.7: Distribution of different routing policies with fixed f

Figure 5 . 1 :

 51 Figure 5.1: Node operations: LT encoding, decoding and dissemination protocol

Figure 5 . 2 :

 52 Figure 5.2: Example of factor graph

. 1 )

 1 Equation (5.1)d e p e n d so nt h ep r o b a b i l i t yo fo b s e r v i n gac e r t a i nc h e c kv a l u ec I , given the states of the uploaders of such check.

Figure 5 .Figure 5 . 3 :

 553 Figure 5.3: Representative accuracy (left), completeness (middle), and time to identification (right) of SIEVE as a function of w

Figure 5 . 4 :

 54 Figure 5.4: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for best performance, lower energy consumption, and compromise setting

Figure 5 . 5 :

 55 Figure 5.5: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different nodes mobility models

Figure 5 .Figure 5 . 6 :

 556 Figure 5.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.Figure5.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.Figure5.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

Figure 5 . 7 )Figure 5 . 7 :

 5757 Figure 5.7: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE where moving nodes range from all fast to all slow

Figure 5 . 8 :

 58 Figure 5.8: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE where malicious nodes are either all fast or all slow

Figure 5 Figure 5 . 9 :

 559 Figure 5.9: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different pollution intensities at the coded block level (p poll )

5 Figure 5 . 10 :

 5510 Figure 5.10: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different pollution intensities at the chunk level (c poll )

Figure 5 . 11 :

 511 Figure 5.11: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different lying intensities

Figure 5 . 12 :

 512 Figure 5.12: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for p lie =1andincreasingn um berofmaliciousnodes

Figure 5 . 13 :

 513 Figure 5.13: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different disparaging attacks

Figure 5 . 14 :

 514 Figure 5.14: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for increasing number of colluding malicious nodes

Figure 5 . 15 :

 515 Figure 5.15: Accuracy (left), completeness (middle), and time to identification (right) of SIEVE for different values of K

Figure 6 . 3 :

 63 Figure 6.3: Sliding window example

]Figure 6 . 4 :

 64 Figure 6.4: Total number of Interest packets sent by clients with playout delay of (a) 10s and (b) 15s

Figure 6 . 5 :

 65 Figure 6.5: Percentage of duplicated Interest packets sent by clients with playout delay of (a) 10s and (b) 15s

Figure 6 . 6 :

 66 Figure 6.6: Chunk loss ratio with playout delay of (a) 10s and (b) 15s

Figure 6 . 7 :

 67 Figure 6.7: PSNR of the Y components of received videos with playout delay of (a) 10s and (b) 15s

  --model: the statistical model to use, 0 for independent, 1f o ri n d e p e n d e n tg l o b a l ,2f o rd e p e n d e n t[ D e f a u l t :2 ] -v or --verbose: a flag for having verbose output [Default: false] -t or --test: a flag for initiating selftest [Default:false] -n or --noderiv: a flag for reading all parameters from the json file, not calculating them as standard [Default: false]

A. 3 . 1

 31 The ccnSim simulator • Tool name: ccnSim • Tool authors: R. Chiocchetti, D. Rossi, and G. Rossini • License: GNU GPLv3

  Table, different from the IP one as a given content name can have more faces to allow Pending Interest Table (PIT) which is a Table keeping track of the forwarded Interest packets and the faces they come from, to be able to route back Data replies. At the reception of an Interest the node searches its CS if the requested content is already available, and if found is sent back to the requesting node. Otherwise the PIT is consulted to see if the node has already received other Interest packets for the same content, if yes the received Interest arrival face is added to the PIT and nothing more. If not the FIB is consulted to find the a matching entry to forward the Interest to, if one is found the Interest is added to the PIT and sent to the appropriate node, otherwise it is dropped, not being able to either satisfy of forward the request.

	Interests to be forwarded to more potential sources;
	• a

Table 4 .

 4

	1: m for different s i distributions: comparison between model and simu-
	lation	Model Simulation (95% C.I.)
	p hit	0.3733	0.373552 ± 0.003852
	m 4822.63	4821.57 ± 0.0498

Table 4 . 2 :

 42 Definition of the {s i } distributions used for validationS 1 s 1 =0.7,s 2 =0.1,s 3 =0.1,s 4 =0.1 S 2 s 1 =0.4,s 2 =0.3,s 3 =0.2,s 4 =0.1 S

3 s 1 =0.1,s 2 =0.2,s 3 =0.3,s 4 =0.4

Table 4 .

 4 3: m for different s i distributions: comparison between model and simu-

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

  results have been obtained by setting as initial data sources only the N still

	Parameter	Description	Value
	N fast , N slow	Number of fast/slow nodes	100
	N still	Number of still nodes	50
	P fast , 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 blocks	100 ms
	c, δ	RSD parameters for LT encoder	0.01
	l	Square area side length	2000 m
	h	Time between data chunk generation	600 s
	wr	Window size for concurrent chunk downloading	50
	wt	Window size for concurrent chunk uploading	6
	r	Maximal transmission range	175 m
	V fast	Fast no des sp eed	[10-40] m/s
	V slow	Slow nodes speed	[1-5] m/s
	-	Mobility model	2D RW

Table 5 .

 5

1: Parameter values for the reference scenario

  • 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},t h a ti s ,t h em i n i m u mt i m et oi d e n t i f ya t least x malicious nodes in the top x positions of R n .

	a ni n d i c a t o rf u n c t i o nw h o s ev a l u ei se q u a lt o1i fR n is non empty at
	time t and 0 otherwise;
	• a n (t)t h en u m b e ro fa c t u a lm a l i c i o u sn o d e sc o r r e c t l yi d e n t i fi e db yn o d en
	at time t.M o r ep r e c i s e l y ,a n (t)=x if x nodes in the top P positions of R n
	are truly malicious;
	• r n (t)t h en u m b e ro fa c t u a lm a l i c i o u sn o d e sc o r r e c t l yi d e n t i fi e di nt h et o p
	positions of R

n at time t.M o r ep r e c i s e l y ,r n (t)=x if top x nodes in R n are all actually malicious. If SIEVE at time t has identified P -1o u to fP malicious nodes (a n (t)=P -1) but the first node in R n is not malicious then r n (t)=0;

Table 5 .

 5 ). It can be noted that too 2: Structural prop erties 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 5 .

 5 t i l l 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 3: Structural prop erties of G n for different nodes speed in the reference scenario

	speed	|C|	z U	|U|	z C	length 4 cycles
	fast	434.14	8.6891 232.594 15.8041	23240.5
	slow 428.937 8.91507 230.292 15.8437	29242.7
	still	737.88 7.42264 232.663 23.4016	55141.4

Table 5 .

 5 4: Structural prop erties of G n for different values of K 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.5k B ,3 1 .7k B ,a n d4 6 .3k B ,r e s pe c t i v e l y .

	4 cycles

  Table (PIT): is a Table used to keep track of the Interest packets that have been forwarded upstream towards content sources, combining them with the respective arrival faces, thus allowing the properly delivery of backward Data packets sent in response to Interests.

Table 6 .

 6

		1: Messages used in CCN-TV
	Packet type	Field	Content
	Chunk Interest	Content Name	[domain]/[channelID]/[chunkID].
		nonce	Used only for the bootstrap phase.
		Publisher Filter Not used.
		Status	Bootstrap, Normal, Retransmission.
	Chunk Data	Content Name	[domain]/[channelID]/[chunkID].
		Publisher ID	Optional.

Table 6 .

 6

	2: Summary of simulation parameters
	Parameter	Value
	Top ology	GEANT with 22 routers
	Link capacity	40 Mbps and 100 Mbps
	Number of real-time service provides	1
	Number of clients	21
	Catalog size	5fi l e s
	Chunk size	10Kbytes
	Video average bit rate	250kbps, 600kbps, 1000kbps and
		2000kbps
	W( w i n d o ws i z e )	10
	Playout delay	10s and 15s
	Window timeout	1s, 3s, and 5s
	Caching strategy	No cache, LRU, and FIFO
	Cache size	100 chunks
	Client zapping behavior	50% fixed, 50% changing on average ev-
		ery 15s
	Simulation time	60s
	Number of seeds	5

.4.F r o mt h e s e plots it is evident that the highest windowTimeout,t h el o w e s tt h et o t a ln u m b e r

RSD is derived by the Ideal Soliton Distribution and depends on two free parameters usually identified with constants c and δ.

In CCN it is used the term "face" instead of the "interface" because packets are also exchanged between application process, besides being forwarded only over real network interfaces.

Flow control

From the moment a node receives the bootstrap data message, it can initiate the sliding window mechanism to request the subsequent chunks in an optimal way. Each node has a windows of size W to store W pending chunk. We define pending chunk achunkwhoseInterest has been sent by the node, and the window containing the pending chunks a Pending Window.T o g e t h e rw i t ht h ec h u n k I D , we store in the pending window other information, such as the timestamp of the first request and the timestamp of the last retransmission. Whenever a new data message is received, the algorithm described in Figure 6.2 runs over the Pending Window, to perform the following operations:

1. Purge the Pending Window from all the chunks who are expired, i.e., who have already been played, to free new space in the sliding window.

2. Retransmit all chunks that have not been received for a given timeout (on-Appendix A

Tools used

A.1 HSO -Heterogeneous Statistical Optimizer

• Tool name: HSO

• Tool authors: R. Loti, and R. Gaeta

• License: (Currently not released to the public)

• Website: Software available on request

To calculate the probability functions generating the the statistical mo del for network interconnection we have developed a dedicated software, called HSO (Heterogeneous Statistical Optimizer). The tool, evolution of a simpler, also internally developed, nameless tool specific to the homogeneous networks case, takes as parameters a json formatted configuration file, the results file name and a few optional parameters regarding the specific variation of the mathematical model to be used, the verbosity of the console output and how to manage missing values in the given configuration file. Following is the help text showing the usage pattern: