Luigi Liquori

Hung Nguyen Chan

Giovanni Chiola

Fabrice Huet

Dr Marina Ribaudo

Dr Frederic Giroire

Carlos

A Backward

Peer-to-peer (P2P) systems are used by millions of users every day. In many scenarios, it is desirable for the users from dierent P2P systems to communicate and exchange content or services with each other. This requires co-operation between the P2P systems, which is often dicult or impossible, due to the two following reasons. First is the lack of an inter-overlay routing infrastructure throughout these systems, caused by the incompatibilities in overlay networks on top of which they are built. Second, there are incompatibilities in the application protocols of these systems.

The main topic of this thesis is enabling the cooperation between P2P systems. The thesis introduces a cooperation framework for backward-compatible cooperating heterogeneous P2P systems which constitutes two parts. The rst one is an inter-overlay routing framework which allows to inter-routing between heterogeneous overlay networks. The second one is the cooperation application, built on the top of the inter-overlay routing framework, which aims at solving the incompatibilities in the application protocols of P2P systems. However, due to the dierences in contexts of dierent application domains, in the cooperation framework, we only introduce the principles underpinning the building of cooperation application.

As a case study of the cooperation framework, we introduce a complete solution for cooperating P2P le-sharing networks which is applicable for all current P2P le sharing networks. The solution includes the cooperation application, running a protocol named Inter-network File-sharing Protocol (IFP), operating upon the inter-overlay routing framework. Through the experiments, we show the eciency of the inter-overlay routing framework as well as the eciency of the solution for cooperating P2P le-sharing networks.

While investigating the inter-overlay routing, we found that the inter-connecting P2P overlays can achieve important features including scalability, localization, resilience and self-organization. We believe that with these features, the inter-connecting P2P overlays are suitable to be communication architectures of many Cyber-Physical Systems (CPS).

) serves as the fundamental part of communication infrastructure of Advanced Metering Infrastructure (AMI) in smart grid. The analysis and experiments show the scalability and communication eciency of the proposed architecture. Chapter 2. Background and State of the art In [Liao et al 2006], authors introduced an inter-overlay optimization based scheme in which the resources are shared among dierent overlays to optimize streaming paths, improve service delay and streaming reliability, balance the trac, etc.

Motivations and research directions

The research for this thesis has followed two main directions. The rst one is cooperation of heterogeneous P2P systems and the second one is the ability of using inter-connecting P2P overlays as routing infrastructure for cyber-physical systems.

Cooperation of heterogeneous P2P systems

Many P2P systems have been introduced and become widely used today, such as P2P le-sharing networks, P2P instant messaging networks, P2P data storage systems, etc.

Those systems co-exist but normally are isolated and compete with each other. On the other hand, there are clear advantages for these systems to co-operate to share the content or services with each other. For instance, users in one P2P system can achieve the content or services in other P2P systems. Another advantage is the overall storage for storing data across P2P systems is reduced because the cooperation allows reducing the number of copies of stored data. The content redundancy is also easy to achieve by storing the data at dierent P2P systems.

However, these P2P systems, even with the same goals, are dierent from each other in both the overlay networks and the applications built on top of those networks. While the overlay networks are heterogeneous in many aspects such as structures, topologies, routing algorithms, message encoding algorithms, the applications are dierent from each other in data context, protocols for exchanging content or services, etc. These dierences result in an overall incompatibility across P2P systems which prevents the communication between P2P systems and at a higher level, the cooperation between them.

As a matter of fact, the main challenge for the cooperation between P2P systems is twofold. First is to introduce an inter-overlay routing infrastructure between isolated P2P systems. Second is to dene a common interface for various applications and map the interface of each P2P system to the common interface and vice versa. Another challenge of cooperating P2P systems is to ensure the back-ward compatibility, i.e. the Chapter 1. Introduction peers are unaware of the cooperation protocols still work normally. This is important requirement for co-operating already existing P2P systems. The main part of this thesis, presented in chapter 3 and chapter 4, addresses those challenges.

1.1.2 Application of the inter-connecting P2P overlays in Cyber-Physical Systems (CPS) A CPS is a system of collaborating computational elements controlling physical entities [CPS]. Many CPS constitutes a large number of sensors and actuators, deployed in vast geographical areas, monitoring and sending the data to control centers. These systems require scalable communication infrastructures to deal with the large amount of generated data. It is also desirable for these systems to be resilient with failure and self-organizing to reduce the operation and maintenance cost.

Of the communication architectures, the inter-connecting P2P overlays is a promising candidate. Beside the scalability and self-organization features, the overlays in the inter-connecting P2P overlays can be geographically distributed thus allow to bring the localization to the infrastructure. On the other hand, the fact that the overlays can be heterogeneous gives the great exibility in building the infrastructure.

In this thesis, we exploit the inter-connecting P2P overlays architecture for the Advanced Metering Infrastructure (AMI) [AMI] in smart grid, a typical CPS. AMI is a large geographic distributed system that provides an intelligent connection between consumers and system operators in modern electric grid. One of the biggest challenge that AMI faces is to scalable collect and manage a huge amount of data. We will show that the inter-connecting P2P overlays can address this challenge.

Thesis structure

This thesis is structured as following:

Chapter 2 constitutes twofold. First we present the background for our works, including denition, classication, characteristics and application of P2P. Second, we provide a literature review of the studies on cooperation of P2P systems and point out the dierence between the work done in this thesis and previous works.

Chapter 3 presents a cooperation framework for cooperating heterogeneous P2P systems. The cooperation framework constitutes an inter-overlay routing framework allowing to route the messages across dierent P2P systems and a cooperation application, built upon the routing infrastructure, allows to bridge those P2P systems at application level. However, each application domain has its own semantic, therefore it is dicult to introduce a cooperation application for all application domains. We introduce the principles for building the cooperation application which is applicable for all application domains instead. Based on the cooperation framework, one can develop a complete cooperation solution for each application domain. The cooperation framework allows the backward compatibility in the sense that the peers which are aware of the framework can transparently achieve the resources or services from other systems while the peers which are unaware of the framework can still work normally. The cooperation framework is the main contribution of our thesis.

In Chapter 4, as a case study of the cooperation framework, we introduce a complete cooperation solution for P2P le-sharing domain which is the most successful area of P2P.

Publications 3

The cooperation solution allows to backward compatible cooperating heterogeneous P2P le-sharing networks which is applicable for all current P2P le-sharing networks. In the cooperation solution, the IFP protocol is introduced as cooperation application solving the incompatibilities in application protocols of various P2P le-sharing networks.

In Chapter 5, we present an architecture of inter-connecting P2P overlays mixing with client-server model for the AMI in smart grid, a typical CPS. The inter-connecting P2P overlays constitutes multiple DHT overlays which are geographically distributed and hierarchically organized.

Chapter 6 resumes the presented works and introduces new direction for the research.

Publications

This thesis relies on following conference papers and reports:

1. Giang In this chapter, we present some basic knowledge on P2P including its denition, the development history, the layer architecture and the applications of P2P. We also provide a literature survey of previous studies on cooperating P2P systems and state the dierences between the approach presented in this thesis and the previous ones.

2.1

Background on P2P

P2P denitions

There has no precise denition of P2P in the literature today. Many denitions are proposed trying to capture main features of P2P systems. Following are typical denitions.

G. Camarillo. A system to be P2P if the elements that form the system share their resources in order to provide the service the system has been designed to provide. The elements in the system both provide services to other elements and request services from other elements [Camar 2009].

S. Androutsellis-Theotokis and D. Spinellis. Peer-to-peer systems are distributed systems consisting of interconnected nodes able to self-organize into network topologies with the purpose of sharing resources such as content, CPU cycles, storage and bandwidth, capable of adapting to failures and accommodating transient populations of nodes while maintaining acceptable connectivity and performance, without requiring the intermediation or support of a global centralized server or authority [START_REF] Andro | [END_REF].

Chapter 2. Background and State of the art R. Schollmeier. A distributed network architecture may be called a Peer-to-Peer (Pto-P, P2P,...) network, if the participants share a part of their own hardware resources (processing power, storage capacity, network link capacity, printers, ...). These shared resources are necessary to provide the Service and content oered by the network (e.g. le sharing or shared workspaces for collaboration). They are accessible by other peers directly, without passing intermediary entities. The participants of such a network are thus resource (Service and content) providers as well as resource (Service and content) requestors (Servent-concept) [Schol 2002].

The characteristics of P2P systems according to these denitions include:

Shared resources. Elements or participants in P2P systems share the resources with each other in order to provide the services or content oered by these systems.

Self-organized. P2P systems have ability to self-organize into network topologies. Dual role. Elements or participants in P2P systems both provide resources to others and request resources from others.

Stability. P2P systems have ability to adapt with failures and accommodate with transient populations of participants or elements.

Autonomy. Participants work without the support of a central servers or authority.

History of P2P

2.1.2.1 The early Internet ARPANET, the rst proto-Internet network, was originally designed in the late 1960s as a peer-to-peer system for the purpose of sharing the computing resources across U.S.

The rst few hosts, including UCLA, SRI, UCSB, and the University of Utah which were independent computing sites, are connected as equal computing peers. [START_REF] Oram | [END_REF]].

The early stage of Internet was open with no rewall. Two computers can send packets to each other without intermediate intervention. FTP and telnet are then the most popular applications. Although they based on client-server architecture, every host could FTP or Telnet to any other host, i.e. every host act as both client and server.

In this duration, USENET and Domain Name System (DNS), two paradigms of computer networking which include important peer-to-peer components, appeared.

In 1979, USENET was developed to exchange information in the Unix community.

Based on Unix-to-Unix-copy protocol, or UUCP, one Unix machine would automatically dial another, exchange les with it, and disconnect. Users could post news, read messages and exchange messages. USENET introduced the decentralized model of control that in some ways is the grandfather of later peer-to-peer applications such as Gnutella and Freenet [Usenet].

The DNS was originally designed in 1983 to distribute the information of mappings that each of which includes a human-friendly hostname and an IP address, across the Internet. DNS combines the peer-to-peer networking with a hierarchical architecture of information ownership. In DNS system, the namespace is hierarchically organized with each domain has an authority which is the name server keeping mapping hostnames and IP addresses of hosts in that domain. To know the IP address of a host, a peer send the query to the nearest name server, which normally, in turn, delegates the query to a higher authority. Name servers act both as clients and as servers. Several principles in 2.1. Background on P2P 7 DNS are used in P2P systems today. For instance, hosts play the dual role of both client and server; the load is naturally distributed over name servers; name servers can query each others, but normally, the communication follows a path up the chain of authority.

[DNS, Rfc1034, Rfc1035].

The peer-to-peer communication patterns in early Internet give experiences for designing P2P systems later.

The Internet explosion and the appearance of P2P applications

The explosion of the Internet in 1990s involved millions of ordinary users began to use the Internet to exchange email, access web pages, and buy things. This change shifted the equal sharing information model used before to the client-server model.

P2P attracts attention with the popularity of Napster in 1999, a P2P le-sharing application for sharing music. In Napster, central servers indexed the users and their shared les, and returned the information to users who wanted to download the les.

A user, upon receive the location information of the sough le, directly exchanged the le with the user who owned that le. One limitation of P2P architecture introduced by Napster is that the central server is the single point of failure. However, the actual problem which took the Napster down in 2001 is the copyright infringement. [Napst] At the end of Napster, P2P le-sharing networks such as Gnutella [Gnute], Kazaa [Kazaa] appeared removing the single point of failure problem in Napster. These networks introduced decentralized architectures in which peers are equal or a fraction of peers are automatically elected as super peers. These networks allowed users to download various kinds of les such as documents, movies, etc. After Napster was shut down, these P2P networks still exist because there is no single point can take the network down.

Many more P2P le-sharing networks have been introduced till now such as Kad [Kad],

eDonkey [eDonk] and BitTorrent [BitTo].

Beside le-sharing, P2P technology also has been used in many other areas such as video streaming, instant messaging and distributed computing.

The P2P architecture has been widely used because of its advantages which are as following [START_REF] Babao | [END_REF]].

Scalability. One important property of P2P networks is that the users contribute the resources. When the number of users increases, the capacity of the network also increases because of the additional resources brought by the new users. In contrast, in client-server applications, if the number of users increases, the more resources need to be added for serving the new users. Otherwise, the quality of service can reduce or the service can even stop.

Resilience. P2P architecture eliminates the single point of failure in client-server architecture, thus increase the robustness of the systems.

Cost-eciency. P2P networks require low cost of installation, management because of following reasons: (i) the users contribute their resources; (ii) P2P networks are self-organized systems; and (iii) they usually, does not require the dedicated servers which are expensive.

However, the P2P networks have limitation of security. The direct exchanging of resources between end users opens the hole to the computers of end users to malicious.

Chapter 2. Background and State of the art

P2P systems

We model the P2P systems in a layer architecture as illustrated in Figure 2.1. A P2P system constitutes three layers: underlying network, overlay network, and application.

• Underlying network is the communication networks to which peers connect for routing packet.

• Overlay network is the network of peers established at the OSI's application level.

The peers rely on underlying network for routing packet to each other. Overlay network is responsible for providing P2P services, such as storing and retrieving data, for P2P applications built on top of it. To accomplish its responsibility, overlay network performs many operations such as management of nodes, e.g.

constructing, maintaining the topology; management of resources, e.g. locating, replicating resources; management of security, etc. We will investigate the overlay network layer and the application layer of P2P systems in the two follow sections, respectively.

P2P overlays

Many P2P overlay networks have been introduced with dierent network structures, topologies, routing algorithms, etc. Based on the structure of the overlay networks, these P2P overlays can be classied into structured overlay, unstructured overlay, hybrid overlay and hierarchical overlay.

Unstructured overlays

Unstructured P2P systems organizes its peers in a random graph in which either all peers are equal or a faction of peers are elected as super peers having more functions than normal peers. In unstructured overlay, there is no constraint about which node stores a certain content, i.e. content are placed randomly over the nodes in the overlay.

Background on P2P 9

The main operation provided by overlay networks is looking up content. In unstructured overlay, peers use a routing algorithm such as ooding or random walks or hill climbing to query content in the overlay. A peer, who received the query, matches the query locally against its own content.

For purpose of routing, each peer builds and maintains a local routing table containing some neighbor peers. A peer periodically checks the aliveness of these neighbors for removing the unavailable ones and adding the new ones. To ensure the scalability, an overlay limits the maximum number of neighbors that a peer has.

At the bootstrap time, the new peer nds some already existing peers in the overlay via external mechanisms such as via websites. It then contacts with these peers and builds its routing table following the mechanism dened by the overlay.

The unstructured overlay has following advantages:

• It easily supports complex queries, a feature that is expected by many of P2P applications, because all the searches for content are performed locally on each peer.

• It is highly robust in the face of high rates of churn -that is, when large numbers of peers are frequently joining and leaving the network [START_REF] Lv | Can Heterogenity Make Gnutella Stable?[END_REF][START_REF]Unstructured Peer-to-Peer Network Architectures[END_REF].

• It is easy to build and maintain because there is no constrain about its topology [START_REF] Cherv | [END_REF].

Their disadvantages are as following:

• Scalability is a limitation of unstructured overlays due to the high network trac generated by peers using ooding algorithms which is shown in studies such as [Ripea et al 2002, Marka et al 2002].

• The topology and the location's content are decoupling thus desired data may not be found even if it is exist on the network, i.e. the routing is not exhaustive.

Examples of unstructured overlays are Gnutella[Gnute] , FreeNet [START_REF] Clark | Freenet: a distributed anonymous information storage and retrieval system[END_REF],

FastTrack/KazaA [Kazaa], Overnet/eDonkey2000 [eDonk] and BitTorrent [BitTo]. We will investigate Gnutella, i.e. an unstructured overlay, in more detail as a demonstration.

Gnutella description. In Gnutella 0.4, i.e. the rst version, all peers are equal and peers play the role of both client and server.

Message types. Gnutella employs four dierent kinds of messages for management and searching.

• PING message is used by peers to discover hosts on network.

• PONG message is used by peer for replying to PING message it received.

PONG message contains the information of the peer.

• QUERY message contains search string created by requester.

• QUERY HIT message: a peer, upon receiving the QUERY message, matches again its local shared les for the criteria in the QUERY message. If the match happens, the peer returns the QUERY HIT message containing the necessary information for downloading the le.

Chapter 2. Background and State of the art Time To Live. Gnutella messages contain a eld called Time To Live (TTL) for looping avoidance. TTL is the maximum number of hops that a message can go through.

Upon receive a message, each peer decrements the TTL before passing it on to another peer. When the TTL reaches 0, the message is dropped.

Bootstrapping. To join the network, a peer must nd at least another node by using address list of possibly available hosts delivered with the software or using updated web caches of known nodes or using UDP host caches. Once the rst connection is established, the new peer asks a list of working addresses from its connected host. It then connects to the known hosts to a certain quota and locally caches the untried host for later usage.

Search. To nd certain content, a peer sends the query to all of its active connected nodes which then forward the requests, and so on, until reaching the sought content or the TTL reaches 0.

Exchanging les. File downloading is performed directly between two peers, i.e. the peer initiating the search and the peer holding the content.

Maintenance. To deal with the changes in neighbors caused by the join/leave of peers, a peer periodically broadcast PING messages to all of its neighbors, which in turn, forward the message and return the PONG message containing contains information about the peer. A PING message is forwarded until the TTL reaches 0. With the pure decentralized model, Gnutella is very resilient with the churn, i.e.

QUERY

a fraction of peers join/leave the network. However, the ooding search used by Gnutella makes it not scalable.

To deal with the scalability problem of Gnutella 0.4, Gnutella 0.6 introduced a new model with the network consisting of super peers and leaf peers. In this model, a leaf peer connects to a small number of super peers (typically 3) while each super peer connects to more than 32 other super peers. The leaf peers and the super peers periodically exchange the content holding by the leaf peers. The searching happen in the super peer network is done by ooding algorithm. Introduction of super-peers has led to lower network bandwidth and improved scalability [START_REF] Miloj | [END_REF].

Structured overlays

In structured overlays, peers are organized into a geometric topology. Data is not placed randomly as in unstructured overlay but at specic locations. This makes the discovery of data more ecient.

Most of structured overlays implement a Distributed Hash Tables (DHT). Chord [START_REF] Stoic | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], Kademlia [START_REF] Maymo | [END_REF], Pastry [START_REF] Rowstron | [END_REF], CAN [START_REF] Ratna | [END_REF] are examples of DHT. A DHT bases on an abstract key space. Each participating node (peer) or data item is assigned a unique key taken from the key space using consistent hashing. A key is also called identier. Each DHT denes a distance metric between two identiers. A value is stored at the node that the distance between the value's key and the node's identier is minimal.

DHT provides two operations: put(key, value) and get(key) for storing and retrieving of data (or value) on the overlay network. Given a key, DHT route the put or get request to the node which is responsible for the key.

For routing purpose, each node maintains overlay links to a number of other nodes.

These links together form an overlay. The information of each of these nodes, including IP address and node's identier, is stored in the routing table of the local node. The routing forwards the requests across the overlay links closer and closer to the destination node, i.e. in a progressive manner.

At the time of bootstrapping, a peer retrieves information of several peers which exist in the overlay via external mechanisms such as from websites. Upon having the information, the new peer connects with the existing peer and builds its routing table.

To deal with the join/leave of peers, peers in a DHT periodically run a maintenance protocol for updating their routing tables.

There have been many structured overlays are introduced. They can be distinguished by several dimensions such as the maximum number of hops, the geometry topology, the degree of node, overlay maintenance, etc.

• Based on the maximum number of hops a request traverses in an overlay, current DHT can be classied in three categories: one-hop (Kelips [START_REF] Gupta | Kelips: Building an Ecient and Stable P2P DHT Through Increased Memory and Background Overhead[END_REF], D1HT [START_REF] Monnerat | [END_REF]), multi-hop (Chord [START_REF] Stoic | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], CAN [START_REF] Ratna | [END_REF], Koorde [START_REF] Kaashoek | [END_REF]) and variable-hop (Accordion [START_REF] Li | [END_REF], Chameleon [START_REF] Brown | [END_REF]).

• Overlay geometry denes the static model of the graph that routing algorithm constructs in no churn environment. DHT are designed with many overlay geometry, such as Ring (Chord, DSK [START_REF] Alima | [END_REF]), Plaxton Tree (Pastry [START_REF] Rowstron | [END_REF], Tapestry [START_REF] Zhao | [END_REF]), XOR (Kademlia [START_REF] Maymo | [END_REF]), Hypercube (CAN).

• Node degree is the number of entries in the routing table of node. Two important categories are constant degree and logarithmic degree. CAN, Kooder, Hypercup [Schlosser et al 2003], Viceroy [START_REF] Malkhi | [END_REF] are examples of the DHT with constant degree while Chord, Kademlia, Tapestry, P-Grid [START_REF] Aberer | [END_REF] are DHT with logarithmic degree.

Advantages and disadvantages. With the ability to nd the unpopular content by guaranteeing a maximum number of messages to locate any peer in the overlays, the advantage of structured overlay is the scalability. However, the structured overlay must maintain lists of neighbors that satisfy specic criteria. This makes them less robust in networks with a high rate of churn (i.e. with large numbers of nodes frequently joining and leaving the network) [START_REF] Lv | Can Heterogenity Make Gnutella Stable?[END_REF]. Additionally the structured overlay is unaware of underlying network due to the randomly assignment of key. This means one logical hop can corresponds to multi physical hops, therefore causes the ineciency in routing.

Kademlia description. Following, as an example of structured overlay, we will describe Kademlia protocol [START_REF] Maymo | [END_REF] in aspects which are general for all structured overlays, including geometry topology, mapping content onto peer, routing table, lookup process, node degree and routing cost, join, leave and maintenance.

Geometry topology. Kademlia organizes its nodes into a binary tree in which node's ids, randomly taken from 160 bit identier space, are the leaves of tree. The position of a leaf is determined by the shortest unique prex of the id.

In Figure 2.3, we illustrate the position of a node whose shortest unique prex is 0100 in a Kademlia binary tree.

111…111 000…000

Space of 160 bit numbers

0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 Figure 2.3: A Kademlia binary tree
Distance metric. Kademlia denes its distance metric between two identiers in the identier space as the value of the bitwise exclusive or (XOR) of the two identiers.

Node state. A node divides the binary tree into a series of successively lower subtrees that don't contain the node. The highest subtree contains the half the binary tree that does not contain the node. The next subtree contains the half of the remaining subtree which does not contain the node and so on. The node keeps a list of contact of nodes belonging to each of these subtrees for routing the messages. Contact of a node contains node IP address, UDP port and node ID. This also means that for 2.1. Background on P2P 13 each 0 ≤ i < 160, the node keeps list of contacts for nodes of the distance between 2 i to 2 i+1 from the node.

Mapping items onto node. An item is stored at the node such that the distance between item's id and node's id is minimal.

Lookup process.

Hybrid P2P systems

Hybrid P2P systems integrate unstructured and structured topologies to exploit the advantages of them. There are many ways of combination. In [START_REF] Castro | [END_REF], graph from structured are used for data placement while search strategies of unstructured overlays are used for locating data. In [START_REF] Ganes | [END_REF], nearby nodes are grouped into small DHTs and the routing between DHTs is performed using unstructured links between them. In [START_REF] Hui | [END_REF], peers in structured overlays are virtually organized in clusters which connected to each other via long links to emulate the small world properties [Small-world].

Hierarchical overlays

Hierarchical overlays bring the hierarchical structure into the at structured overlays. A hierarchical overlay organizes its peers into nested overlays, and connects these nested overlays in a tree. To send a message to a peer in a dierent overlay, a peer sends the Chapter 2. Background and State of the art message to the nearest common parent overlay with the destination peer. The hierarchical overlay are designed for improving the performance in such P2P systems that the locality is important in their operations. Many hierarchical overlays has been proposed, including TOPLUS [Garce et al 2003], Hieras [START_REF] Xu | HIERAS: a DHT based hierarchical P2P routing algorithm[END_REF], Canon [START_REF] Ganes | [END_REF],

Cyclon [Artig at al 2005], etc.

In summary, we present the overlay networks in a classication tree which is adopted from [START_REF] Buford | [END_REF] and more than half of the 6% of total bandwidth consumed by le sharing system.

The architecture of BitTorrent includes a central location for managing users' downloads. To publish a le, an user creates a .torrent le containing information about the le, its length, name, and hashing information, and URL of a tracker the user will register the .torrent le. Once registering the .torrent le with a tracker, the user distributes the .torrent le by conventional means such as web, mail, etc. The user then makes the le available through a BitTorrent node acting as a seed of this le. The le is divided into multiple pieces. This publishing peer is called initial seeder.

For every registered le, the tracker is responsible for keeping track of all the peers who have the le either partially or completely.

To download a le, a peer must rst obtain a .torrent le for the le. It then connects to the tracker, specied in the .torrent le, for a list of peers from which it can download pieces of the le. The initiating peer then connects to those peers to obtain the various pieces. If the swarm, i.e. the set of peers are sharing the le, contains only the initial seeder, the initiating peer connects directly to the initial seeder and begins to request pieces. When a peer receives a new piece of the le, it becomes a source of that piece for other peers. If the peer has not had all of the pieces, it is called a leech. Otherwise, it is called a seed.

The A peer can download pieces of a les in a non-sequentially manner and are rearranged into the correct order once all pieces are downloaded. A peer knows which pieces it needs 2.1. Background on P2P 17 as well as which pieces it has and can upload to other peers. This feature help BitTorrent peer resume the download previously halted without the loss of previously information.

Therefore, BitTorrent particularly is useful for downloading of large les.

BitTorrent peers employ tit-for-tat scheme [Tit-for-tat] for optimizing their download speed. A BitTorrent peer is prefer to send data to peers that send data back to them.

This scheme also allows discouraging free-riders.

On 2005, Azureus 2.3.0.0 [Azureus], a DHT implementation, was released introducing the distributed tracker model in which each peer in the DHT plays the role of the tracker.

This model allows the client to use torrents without having a working BitTorrent tracker.

Later, many BitTorrent clients such as ocial BitTorrent client [BitTorrent], µTorrent [µTorrent], BitCommet [Bitcomet], etc support distributed tracker.

Distributed Computing

A P2P distributed computing application breaks a task into multiple independent subtasks and distributes these subtasks to a number of peers in the overlay. These recipient peers perform the tasks using their resources and return the results which will be combined. The advantages of P2P distributed computing is to allow heavy tasks are solved by regular computers instead of powerful servers.

One example of P2P distributed computing system is SETI@home [Seti] which is a scientic experiment that uses Internet-connected computers in the Search for Extraterrestrial Intelligence (SETI). The objectives of SETI@home is to build a huge virtual computer by aggregating the computer processing power oered by voluntary computers which running client software in their idle time. SETI consisting of two parts: the databases server and the clients. The clients search for extra-terrestrial life while the server is responsible for distributing tasks to each participating computer and collecting the results. an open source peer-to-peer electronic cash system developed by Satoshi Nakamoto

[Bitcoin].

The Bitcoin system is decentralized with no central server or trusted parties. In this system, a user can have some Bitcoin addresses called wallet from which they can send or receive bitcoins. Each of the address is a cryptographic public key. The matching private key is stored at certain place such as in digital wallet or mobile device, etc.

The Bitcoin network protocol aims at solving the problems related to creating a decentralized currency and a peer-to-peer payment network. Bitcoins are mathematically generated by a procedure called Bitcoin mining. A coin contains public key of its owner.

A user transfers his coin to other user by signing the public key of the receiver to the coin.

However, the big problem with this model is double-spending. Bitcoin uses a peer-to-peer network which works as distributed timestamp server to eliminate the double-spending.

2.2

State of the art on cooperation of P2P systems

Classication of cooperation

We classify the studies about cooperation between P2P systems into three following categories: inter-system content sharing, merging systems and inter-system trac engineering.

• Inter-system content sharing. P2P systems co-operate to share the content resources or services with each other. Therefore, users in one P2P systems can exploit resources or services provided by other P2P systems.

• Merging P2P systems. P2P systems sharing similarities in goals, the number and the location of nodes can be merged into one system thus eliminating the competition of these systems.

• Inter-system trac engineering. P2P systems co-operate to optimize the routing performance in P2P systems, such as reducing the delay, increasing the bandwidth, etc.

While the objective of inter-system content sharing and merging systems is to enlarge the space of content resources or space of services of users, the inter-system trac engineering scheme is for improving the performance of P2P systems.

The work done in this thesis belongs to the rst category, i.e. allow the sharing content resources and services between P2P systems. Therefore, in this section, we deeply investigate the state of the art on the rst categories while briey survey the works in second and third categories.

Inter-system content sharing

Most of the previous works in this category, except [START_REF] Konis | [END_REF], only addressed the problem of routing a request between overlays which we hereby call inter-overlay routing.

In [START_REF] Konis | [END_REF], they proposed a scheme not only for inter-overlay routing but also for exchanging data in pure ooding P2P le-sharing networks.

Inter-overlay routing. Ecient inter-routing between overlays has served as an inspiration to a number of research eorts. These researches follow two approaches:

inter-routing via logical links [START_REF] Konis | [END_REF] and inter-routing via co-located nodes [Cheng 2007[START_REF] Liquo | [END_REF], Liquo at al 2010[START_REF] Cianc | [END_REF], Cianc at al 2012].

In [Cheng 2007], the authors proposed a solution for inter-routing between distributed hash tables (DHT). One subset of peers in a DHT is co-located nodes, while another subset of peers in that DHT is chosen as trackers to keep the information of those colocated nodes. The queries from peers in one DHT are sent to the trackers that, in turn, forward them to co-located nodes to reach other DHTs. The mechanisms of selecting trackers require the modication of all peers. Also, no simulations or experiments have been made.

In [START_REF] Liquo | [END_REF], the author introduced a protocol named Babelchord for interrouting between Chord overlays. A subset of peers in each overlay runs the Babelchord protocol, serving as gateways that forward messages between these overlays if the messages randomly touch Babelchord nodes in their paths. All peers are modied to add some extra information to their messages.

In [Liquo at al 2010], the authors introduced a protocol named Synapse for interrouting between dierent DHTs. They presented two models: white box and black box. Content cooperation of P2P le-sharing systems. In [START_REF] Konis | [END_REF], the authors proposed mechanisms for cooperating purely query ooding-based le-sharing networks. In their model, several pairs of peers from two networks establish logical links between the two networks serving as bridges to transfer the search requests and the found les between them. However, this work is only for unstructured, query ooding-based le-sharing networks which constitute a small portion of current le-sharing networks.

Discussion. Each P2P system is usually built with its own well-dened semantic.

Therefore, one of the fundamental tasks is the transcoding of the messages and data between dierent P2P systems.

In all previous works, the function of transcoding requests between P2P systems is built in in the routing function, i.e. the transcoding is dened by routing protocols. Other important dierence between current work and previous ones is the current work is applicable to heterogeneous overlays, i.e. both structured overlays and unstructured overlay while all of previous works are only applicable to homogeneous overlays, i.e. either structured overlays or unstructured overlay.

Merging overlays

Certain works have focused on merging several overlays into one. In [Datta at al 2006],

the authors provide an analysis of the problem of merging two dierent overlays, while

in [Shafa at al 2009], the authors give an algorithm describing the merging mechanism of two ring-based DHTs which requires modications of the key space, as well as the rearrangement of keys and requires to modied all of the peers in two DHTs.

Discussion. This approach eliminates the competition of P2P systems and the need of inter-systems co-ordination. However, merging systems require the changes from routing to data presentation in all peers, task which are fairly expensive in terms of time and power processing. Additionally, require to modify all peers is impractical for existing overlays. On the other side, the merging of heterogeneous overlays still remains impossible.

Inter-system trac engineering

In [START_REF] Kwon | [END_REF] author proposed an overlay internetworking architecture constitutes home overlay networks and super overlay called Synergy network including a number of peers from these normal overlays. A route on home overlays can be replaced by a route in the Synergy overlay, i.e. cross multiple home overlays, if the route in Synergy overlay brings better performance.

Authors in [START_REF] Jiang | [END_REF] investigate the interaction between multiple overlays, which are constructed on top of a physical network layer. They proposed the overlay optimal routing policy and model the interaction between multiple overlays using this routing policy in a game theoretic approach.

Introduction

In this chapter, we introduce a new model for sharing content between heterogeneous P2P systems. This model consists of two parts, which bridge the involved systems at the routing and application layers, respectively.

The rst part is the OGP routing framework, which is composed by two protocols namely Overlay Gateway Protocol (OGP) and lightweight OGP. The OGP protocol, an extension of Kademlia, allows ecient routing among existing heterogeneous overlay networks. OGP is run only by a small number of peers from each of the standard overlays, in addition to their native protocols. These peers form a super-overlay (the OGP overlay) equipped with ecient algorithms to perform unicast, broadcast, and multicast of messages from one standard overlay to the others. Peers forming the OGP overlay act as gateways for peers especially created for taking advantage of OGP which run the Chapter 3. A Backward Compatible Framework for Cooperation of Heterogenous P2P Systems lightweight OGP protocol, and can reach across standard overlays they are not members of. The lightweight OGP protocol is run by lightweight peers, i.e. peers with even small power and bandwidth capacities, to take advantage of the OGP overlay to reach the standard overlays of which they are not members. The OGP and lightweight OGP protocols together form a framework for inter-routing between heterogeneous standard overlays.

The second part of the model is a cooperation application that makes use of the OGP routing framework, and which is responsible for bridging the P2P systems at the application layer with tasks such as transcoding the messages and data from formats of the P2P systems to intermediary formats and vice versa. Since the particular tasks of the cooperation application depends on the application domain, in this chapter we only describe the principles of the cooperation application.

Our original approach ensures backward-compatibility, in the sense that:

• Native peers can continue to operate normally without any modications, in the presence of new protocols.

• Peers that are aware of new protocols can achieve resources from dierent systems in a transparent way.

The contribution of this chapter is the introduction of a new model for cooperation between heterogeneous P2P systems consisting of a new framework for ecient interrouting between heterogeneous overlays and principles underpinning the cooperation application for bridging these P2P systems at the application layer.

The rest of this chapter is structured as follows: Section 3.2 presents the system model, which was the motivation of this chapter. The routing framework based on OGP and lightweight OGP protocols and the cooperation application are described in Section 3.3. Section 3.4 evaluates the model. Finally, in Section 3.5, we present our conclusions and outline future work.

3.2

Framework Overview

Classication of peers

In our framework, the peers are classied into three following categories:

Full OGP peers, hereafter denoted as FOGP peers, simultaneously belong to one P2P system and the OGP overlay. In addition to their native protocols, they also run the OGP protocol and the cooperation protocol. They route messages from one P2P system to the others via the OGP overlay and serve as gateways for lightweight OGP peers to reach P2P systems to which they do not belong.

Lightweight OGP peers, denoted as LOGP peers, take advantage of the inter-overlay routing provided by the OGP overlay. They belong only to one P2P system, do not participate in the OGP overlay, but keep a list of FOGP peers. In addition to their native protocols, they run the lightweight OGP protocol for communicating with FOGP peers and the cooperation protocol. LOGP peers are introduced: (i)

to reach P2P systems they are not members of with low cost in terms of power processing and bandwidth, and (ii) to improve the scalability of the cooperation system by reducing the number of FOGP peers and the size of OGP overlay.

Blind peers are peers that belong to only one P2P system, are not aware of the existence of the new protocols and use only their native protocols.

Inter-routing schemes

The inter-routing algorithms are the heart of OGP protocol. The OGP protocol provides three new and ecient schemes that enable inter-routing between standard overlays:

OGP unicast, OGP multicast and OGP broadcast. A FOGP peer can use any of these schemes. For the sake of brevity, the operation of routing a request to a random FOGP peer belonging to the destination standard overlay is hereby described as routing that request to the destination overlay.

OGP Unicast. In the OGP unicast scheme, FOGP peers route requests into only one destination overlay dierent from the one the request originated from.

OGP Multicast. With the multicast scheme, a FOGP peer can selectively choose multiple destination overlays, and all of the responses are returned to the original sender.

OGP Broadcast. With the broadcast strategy, all standard overlays are chosen as destination, and all of the responses are returned to the sender, just like with the multicast. The structure of a LOGP peer, see Figure 3.2, is the same as the structure of a FOGP peer except that the OGP node which runs OGP protocol is replaced by the LOGP node which runs LOGP protocol.

Structure of a FOGP peer and a LOGP peer

Cooperation examples

In Second scenario. The LOGP peer F, belonging to overlay O1, is looking for some information located at the blind peer H in overlay O3 . It forwards, via OGP node, using OGP unicast routing, the message to G which is a FOGP peer in overlay O3.

ID = netID | nodeId 3.3.1.

The distance metric

A FOGP peer calculates the XOR distances, which is dened in Kademlia protocol, from itself to other FOGP peers and uses these distances to internally represent these nodes as a binary tree with the leaves of the tree are the shortest unique prex of these distances. One important property of this binary tree is that all FOGP peers connected to the same standard overlay share a single subtree. Let the identier of the current node be netIDi | nodeID. By properties of the XOR distances, we can easily see that the distance between the current node and any of the peers connected to the same overlay will share the same n-bit prex, and, therefore, the same subtree.

In Figure 3.4, we illustrate the binary tree representing FOGP peers from the view of the FOGP peer whose distance metric is 000...000. In this case, we have that n = 2, i.e. netID is represented by 2 bits. Here, FOGP peers can belong to one of the four standard overlays, whose identiers are netID1, netID2, netID3, and netID4.

111…111 000…000

Space of n+m bit numbers ing entries to peers with exponentially increasing distance in the id space with n is the number of nodes in the system. This principle allows the DHT to achieve its scalability and guarantees an expected routing cost of O(logn) between any two peers in the network. In OGP, by adding more pointers to some distance spaces farthest from the node identier, we reserve the scalability of typical DHTs and ensure the eciency of the OGP routing algorithms in terms of routing cost as well as make the broadcast and multicast algorithms robust to churn and make the load on nodes in one round of broadcast algorithm close to balance.

0 1 0 0 0 1 1 1 netID1 netID2 netID3 netID4
Let p be the number of bits of identiers of FOGP peers, i.e. p = m+n. Additionally, let U and V be two non-negative integer parameters which tune the ID space division and the number of hops a message traverses. Let U and V satisfy (i) U ≥ 1, and (ii) U • V ≤ p, and will be used throughout Section IV.

In OGP, the entire distance space is divided using the following rules:

1. The entire distance space is divided into p + 1 spaces, numbered from 0 to p, which, respectively, cover distances from 0 to 2 0 -1 , and from 2 i-1 to 2 i -1, with 1 ≤ i ≤ p, i.e. similar to the rules of typical DHTs.

2. The U • (V -1) farthest spaces, i.e. the spaces numbered from p down to

p -U • (V -1) + 1
are further divided into 2 U -1 equal subspaces; The U farthest spaces of the remaining spaces, i.e. the spaces numbered from

p -U • (V -1) down to p -U • V + 1 are, respectively, further divided into 2 U -i equal subspaces, with 1 ≤ i ≤ U .
3. The remaining spaces, i.e. the spaces numbered from p -U • V down to 0, are not divided any further.

The deepest subspaces, i.e. those are not further divided, obtained by applying Rule 2 and Rule 3 are the nal spaces. To route messages, a FOGP node keeps in its routing table a group of pointers up to k to each nal space with k is a system parameter.

The group of pointers is called k-bucket as in Kademlia paper [START_REF] Maymo | [END_REF] for simplicity. Each pointer has information about a node belonging to the nal space.

Example. Consider an 8-bits identier overlay in which 7 rst bits of identiers are used for representing the netID part. Assume that the overlay is fully occupied by peers and let U = 3 and V = 2. Consider the FOGP peer, denoted by A, with the ID of 00000000. The space division from the view of this peer is illustrated in Figure 3.5.

Final spaces are represented by black circles. A divides the entire space into 9 subspaces, numbered from 0 to 8. Each of the spaces numbered from 8 down to 6 are further divided into 2 U -1 = 4 equal subspaces. Each of the subspaces numbered from 5 down to 3 are, respectively, further divided into 2 U -i = 2 3-i equal subspaces with 1 ≤ i ≤ 3, i.e. into 2 2 , 2 1 and 2 0 equal subspaces, respectively. We adopt the principles of Kademlia in building the routing table of FOGP peers. We divide the routing table in buckets. Each bucket contains nodes with some common prex in their IDs. The routing table of FOGP node can be seen as a binary tree in which each leaf of the tree is a bucket. The position of a bucket in the binary tree is dened by the shortest unique prex of that bucket.

Like Kademlia, nodes in the routing tree of OGP nodes are allocated dynamically.

Initially, the routing tree of a node u has one bucket covers the whole identier space. Upon learning a new node, the node u inserts the new node into the appropriate bucket.

If the bucket is not full, the new node is simply inserted. Otherwise, if the bucket is full, and the bucket is not represent a nal space, the bucket is split into two new buckets represent two equal subspaces split from the space represented by the old bucket.

The process of building the routing table of the node with the distance of 00..00 is illustrated in the Figure 3.6. This example, parameters U and V are set as following: U = 2 and V = 1.

In the evolution of the routing table of a node, the whole space is split into subspaces that each of which is further split. The node keeps information of all of those spaces in its routing table. The Figure 3.7 illustrates the spaces in the routing table of the node with the distance of 00..00. In this gure, the whole space S 0 is divided into two equal subspaces S 1 and S 2 . The subspaces S 1 and S 2 are further divided and so on. All of those spaces form a tree of spaces. FOGP peer list. An FOGP peer keeps a x-sized list of other FOGP nodes, belonging to the same n-level subtree with it, which is provided to applications to exploit. Upon learning a new node, if the new node belongs to the same n-level subtree with current FOGP node, the current node inserts the new node into its FOGP peer list if this list has fewer contacts than the limit size. If the FOGP peer list is full; the new node is inserted to the candidate list. A FOGP node periodically runs the check aliveness process to remove the dead nodes from the FOGP peer list and the perspective candidate list. A dead node in the FOGP peer list is replaced by the rst alive node in the candidate list. 3.3.1.5 Routing in OGP Denitions. We rst introduce several notions and denitions.

n-level subtree. A n-level subtree of the OGP binary tree (illustrated in Figure 3.4) is a subtree whose prex length equals n. This means that all nodes connected to one standard overlay belong to a n-level subtree.

By sending a message to a subtree we mean sending a message to a random node belonging to the said subtree. We will henceforth use this expression, for the purpose of brevity.

11..11

Space of (n+m) bit bumbers 00..00

0 1 0 1 0 1 0 1 0 1 S 0 S 1 S 2 S 3 S 4 S 5 S 6 S 7 S 8
S 10 S 9 • The n-level unicast is an algorithm used by a FOGP peer to send a message to an n-level subtree of which it is not a member.

• The n-level multicast is used to send a message to a group of n-level subtrees of which it is not a member.

• The n-level broadcast is the sending of a message to all of the n-level subtrees of which it is not a member.

In all of the cases, each n-level subtree only receives one message.

Range of a distance space. The Range of a distance space S, denoted by ∆ S , is the XOR between the maximal (UB) and minimal (LB) numbers in S:

∆ S = UB ⊕ LB.
Depth of a distance space. The Depth of a distance space S in the space tree of a FOGP peer, denoted by δ S , is the number of bits of the space's prex in that tree.

Similarly to sending a message to a subtree, we hereby write sending a message to a subspace instead of sending a message to a random node belonging to the said subspace, for the sake of brevity.

The routing schemes provided by the OGP protocol are presented in the following sections.

Chapter 3. A Backward Compatible Framework for Cooperation of Heterogenous P2P Systems 3.3.1.6 n-level unicast.

Algorithm. The n-level unicast is a greedy algorithm aimed at sending a message to an n-level subtree, knowing its n-bit prex P n . The sending node, which is a FOGP node and has the identier ID 0 , rst generates an m-bit random number R m and concatenates it to P n to form an (n + m)-bit identier:

ID = P n • 2 n + R m .
The initiator node then sends a REPLICATE(message, ID) request to the FOGP node in its routing table closest to ID = ID ⊕ ID 0 . Upon receiving the REPLICATE request, the recipient node checks if its identier ID i and ID have the same n-bit prex. If so, the unicast is completed. Otherwise, the recipient node forwards the REPLICATE request to the FOGP node in its routing table closest to ID = ID ⊕ ID i . If there is no node in its routing table closer to ID than itself, the recipient node drops the request.

Example. An example of n-level unicast algorithm is illustrated in the Figure 3.8. In this example, n = 2 and four overlays are indentied by netID1, netID2, netID3 and netID4.

Node A belonging to the overlay netID1 wants to lookup certain content in overlay netID3. It rst generates a random m-bit number R m and concatenates it with netID3 to form (n + m)-bit identier:

ID = netID3 • 2 2 + R m
Node A then sends the request to the node closest to ID in its routing table which is node B belonging to netID4. Upon receive the request, node B check to see if the ID belongs its n-level subtree by comparing the n rst bits of its identier and the ID. Because the n rst bits of the two identiers are dierent, node B forwards the request to the node closest to ID in its routing table which is node C. Upon receive the request, node C knows the ID belongs to its n-level subtree thus it will proceed the request.

111…111 000…000

Space of n+m bit numbers subtree to an other n-level subtree to approach closer and closer to the destination nlevel subtree. At each n-level subtree, the request touches only one node. Hence, we can assume that each n-level subtree is a virtual node in the overlay with n-bit identier space.

0 1 0 0 0 1 1 1 netID1 netID2 netID3 netID4 A B C
Because the distance space division in the routing table, the distance of the message from the destination n-level subtree is reduced at least 2 U per round of request sending in the V rst rounds and is reduced at least twice per round of request sending in the round after. Assume that the number of n-level subtrees in OGP overlay is K. If log 2 U K < V , after log 2 U K rounds of sending the request, i.e. message traverses through log 2 U K hops, the distance from the message to the destination subtree is:

2 n 2 U •log 2 U K = 2 n K
Because the n-bit prexes of n-level subtrees are random numbers, the number of the n-level subtrees belonging to the distance 2 n K from the destination n-level subtree is 1, with high probability. That n-level subtree is the destination n-level subtree itself. Thus, if log 2 U K < V , it takes O(log 2 U K) hops to reach the destination. Otherwise, if log 2 U K > V , then after V hops, the distance from the message to destination subtree is:

2 n 2 U •V
The number of n-level subtrees that stay in this distance is:

2 n 2 U •V 2 n K = K U • V
With the same analysis, after log 2 K U • V hops more, the message touches the destination subtree with high probability. Therefore, if log 2 U K > V the message arrives the destination n-level subtree after

V + O(log 2 K U • V ) hops. 3.3.1.7 n-level broadcast.
Algorithm. This mechanism is used by a FOGP node to send a message to all n-level subtrees to which it does not belong.

The main idea is that the initiator node sends 2 U messages to 2 U nodes belonging to 2 U equal subspaces in its routing table which, together, cover the entire distance space. Each subspace contains at least one n-level subtree. The node belonging to a subspace and receiving the message is responsible for the further broadcast of the message in that subspace, by repeating the sending operation of the initiator node, except that the entire distance space is replaced by the subspace it is responsible for. This process is repeated at most V times. After that, upon receiving the message, a FOGP node sends the message Chapter 3. A Backward Compatible Framework for Cooperation of Heterogenous P2P Systems to all nal spaces in its routing table containing at least one n-level subtree, which belong to its responsible space, asking one FOGP node per nal space to be responsible for that space. In all cases, a recipient node always excludes the subspace covers the nlevel subtree containing it which already received the message from its responsible space before continuing to send the message. A node stops sending messages if the space it is responsible for has only one n-level subtree. The entire process stops when all of the n-level subtrees have received the message.

The n-level broadcast algorithm can be sketched as follows:

The initiator node. The initiator node sends the REPLICATE(message, ∆ Si , ∆ i ) request to every subspace S i which satisfy the following conditions:

1. δ Si ≤ min(n, U);

2. S i does not have any children S j which satisfy the previous condition;

with δ Si is the depth of the subspace S i and ∆ Si is the range of S i . Assume that ∆ is the range of one n-level subtree. ∆ i = ∆ if S i contains the initiator node. Otherwise, we have ∆ i = 0. For the subspace S i contains the node, the message is sent to the n-level subtree which is closest to the initiator. The condition Depth(S i ) ≤ min(n, m) means that S i must cover at least one n-level subtree The condition 1 ensures the number of subspaces which receive the message are not greater than 2 U . The recipient node. The recipient node, i.e. the node which has received the REPLICATE(message, ∆ Si , ∆ i ) request belongs to an n-level subtree to which that message was sent to. This node is also responsible for broadcasting the message further, to all n-level subtrees covered by ∆ S i which do not belong to the subspace ranging from ∆ i to 2 • ∆ i , i.e. the subspace cover the subtree which contains the sent node in the case that the recipient space contains the sent node. The recipient node calculates δ Si of the space S i for which it is responsible from using ∆ S i using following formula:

δ Si = (m + n) -log 2 ∆ S i If δ Si ≤ U • (V -1)
, the node does the following:

1. Sends the request REPLICATE(message, ∆ Sj , 0) to all subspaces S j which satisfy the following conditions:

• δ Sj ≤ min(n, δ Si + U)
• S j does not contain the node.

• S j does not have any children S k for which the rst condition is satised. with δ Sj is the depth of the subspace S j and ∆ Sj is the range of S j .

2. Sends the request REPLICATE(message, ∆ Sj , ∆ j ) to its closest n-level subtree of subspace S j that satises the following three conditions:

• δ Sj ≤ min(n, δ Si + U)

• S j contains the node.

• S j does not have any children S k which satisfy the rst condition.

Framework description 35

with δ Sj is the depth of the subspace S j and ∆ Sj is the range of S j . ∆ j = 2 • ∆ i .

3. Sends the REPLICATE(message, ∆ Sj , 0) request to all subspaces S j in the space ranging from 0 to ∆ S j except the subspace ranging from ∆ i to 2 • ∆ i that satises the condition:

• δ Sj ≤ n with δ Sj is the depth of the subspace S j and ∆ Sj is the range of S j .

If δ Si > U • (V -1), the node does the following:

1. Sends the request REPLICATE(message, ∆ Sj , 0) request to all subspaces S j in the space ranging from 0 to ∆ S j except the subspace ranging from ∆ i to 2 • ∆ i that satises the condition:

• δ Sj ≤ n with δ Sj is the depth of the subspace S j and ∆ Sj is the range of S j .

The above process nishes once all of the n-level subtrees have received the message.

Example. Consider an 7-bits identier overlay in which 5 rst bits of identiers are used for representing the netID part, i.e. n = 5 . Assume that the overlay is fully occupied by peers and let U = 3 and V = 1. The range of whole distance space is ∆ S 0 = 2 7 . The distance covered by one n-level subtree is ∆ = ∆ S 0 2 5 . The FOGP peer, denoted by A, with the ID of 0000000 broadcasts a message to all n-level subtrees. The broadcast process happens as following:

Node A. The routing table of node A is illustrated in the Figure 3.9. In the routing table of A, 8 equals subspaces numbered from 0 to 7 at Depth 3 are satised conditions:

1. δ Si ≤ min(5, 3); 2. S i does not have any children S j which satisfy the previous condition; Therefore, A sends the request REPLICATE(message, ∆ Si , ∆ i ) with ∆ S i = ∆ S 0 2 3 and ∆ i = 0 to 7 random nodes in the subspaces numbered from 1 to 7. None of those spaces contains the node A. Each recipient node is responsible for broadcast the message to nlevel subtrees in the distance from the node itself to ∆ S 0 2 3 . Assume that node B, belonging to subspace numbered 5, is one of those recipient nodes. The operation performed by other recipient nodes is the same as the one performed by node B.

For the subspace numbered 0, i.e. contains the node A, node A sends the request

REPLICATE(message, ∆ Si , ∆ i ) with ∆ S i = ∆ S 0 2 3 and ∆ i = ∆ = ∆ S 0 2 5
to the n-level subtree which is closest to A, i.e. the subspace numbered 1 at Depth 5.

Assume that C is the recipient node. request subspace numbered 1 at Depth 5. Those subspaces are the ones that belongs the space ranging from 0 to ∆ S 0 2 3 and have the depth less than 5. Assume that E and D are recipient nodes belonging to recipient subspaces at Depth 4 and Depth 5 respectively.

Upon receive the request from node B, node D stops forwarding the request because the depth of subspace that it is responsible for is 5, i.e. not less than n with n = 5.

Node E is responsible for broadcast the message in a subspace at Depth 4, i.e. less than 5 therefore it forwards the request to node F which belonging to the subspace numbered 1 at Depth 5 in the routing table of node E, see Figure 3 The operation performed by node C is illustrated in the Figure 3.11a. Node C is responsible for broadcast the message to n-level subtree in the space ranging from 0 to ∆ S 0 2 3 except the subspace ranging from ∆ to 2 • ∆ with ∆ = ∆ S 0 2 5 . Because the depth of this space is 3 and 3

> U • (V -1) with U = 3 and V = 1, node B sends the request REPLICATE(message, ∆ S0 2 4 , 0)
request to the subspace numbered 1 at Depth 4 which is the one that belongs the space ranging from 0 to ∆ S 0 2 4 and has the depth less than n with n = 5. Assume that G is the recipient node.

Similar to node E, upon receive the replicate request, node G forwards the request to node H which stops forwarding the message, see Figure 3 virtual nodes in the n-bits overlay. In the rst V rounds of sending message, the range of the space one recipient node is responsible for broadcasting the message reduces at least 2 U per round and reduces at least twice per round after that. If log 2 U K < V , after log 2 U K rounds of sending request, i.e. message traverses through log 2 U K hops, the range of the space a node is responsible for broadcast is:

2 n 2 U • log 2 U K = 2 n K
The number of n-level subtrees belonging to this space is 1 with high probability. This subtree is the subtree containing the recipient node. Thus it takes O(log 2 U K) hops to broadcast the message to all n-level subtrees in this case. Otherwise, if log 2 U K > V , after V hops, the range of the space a node is responsible for broadcast is 2 n 2 U •V . The number of n-level subtrees stay in this space is:

2 n 2 U •V 2 n K = K U • V
With the same analysis, after log 2 K U • V hops more, the message touches all subtrees with high probability. Therefore, if log 2 U K > V , the message is broadcasted to all n-level subtrees after

V + O(log 2 K U • V ) hops.
If the routing table of nodes are full, the broadcast tree is balance to depth V and from the root, i.e. the initiator node, to the nodes in depth V , each node has 2 U children. This is important characteristic of n-level broadcast algorithm which makes the load on nodes quite balance and makes the algorithm robust to churn because each node is only responsible for a small part of the whole distance.

OGP broadcast tree. The broadcast tree of n-level broadcast algorithm in above example illustrated in Figure 3.12. In summary, the OGP peer A is the initiator node. It sends the messages to 2 U = 2 3 = 8 other nodes. These nodes then forward the message to 15 other nodes. Each of them either stops forwarding the message or sends the message to another node.

We expect the n-level broadcast algorithm to achieve scalability, resilient to churn and load balance. Scalability means the algorithm scales well with the increase of participants in terms of number of messages passing in the algorithm and the amount of overheads for maintaining the broadcast tree. Resilient to churn means the join/leave of participants does not seriously aected to the algorithm. Load balance means the work load is evenly distributed over the nodes at each depth of broadcast tree. The work load here means the size of identier space that a node is responsible for continuing to broadcast the message.

Under the churn condition, the nodes, which are closer to the root in the broadcast tree, play more important role than the nodes which are farther to the root. This because the closer nodes are the roots of larger subtrees, i.e. are responsible for broadcast the message to larger sizes of identier spaces. This means that in the broadcast tree, the resilient to churn and load balance of the nodes at depth p are more important than those of nodes at depth q with p < q.

In OGP, by adding more pointers to several farther spaces in routing table of nodes, we keeps the broadcast tree balance to depth V and each node at depth p with p < V is responsible for broadcast the message in the identier space of size ∆ 0 2 U * p with ∆ 0 is the size of whole identier space. This makes the OGP broadcast tree balance to the depth V . On the other hand, we can increase the U parameter to increase the resilient to churn.

In OGP broadcast, the number of messages passing only depends on the number of n-level subtree while does not depend on the number of nodes. To broadcast a message in an overlay with k subtrees, the algorithm need only (k -1) messages passing. This means the our broadcast tree achieves the scalability.

The adding of more pointer to a number of farther subtree increase the amount of maintenance overheads. However, we can control these additional overheads by tuning the U and V parameters. 3.3.1.8 n-level multicast. Algorithm. n-level multicast is an algorithm used by a FOGP node to send a message to a group of n-level subtrees on the OGP overlay of which it is not a member. This group is called the multicast group. The multicast group can be formed in dierent ways, e.g. by all n-level subtrees at distance ∆ from the current node, by all n-level subtrees with given n-bit prexes, or by all n-level subtrees with n-bit prexes belonging to a given range.

The multicast algorithm is similar to the broadcast algorithm with the following general idea: a node is responsible for multicasting the message within a certain distance space. The multicast process happens as following: The initiator node checks to see if there is overlap between the multicast group and the following spaces in its routing table:

1. The subspaces that each of which corresponds to one k-bucket and covers at least one n-level subtree.

2. The subspaces together cover one n-level subtree and each of which are further divided. corresponds to one k-bucket are represented by the subspace covers that

For each subspace that overlaps with the multicast group, if the routing table contains a contact belonging to both the subspace and the multicast group, that contact is chosen.

Otherwise, the node chooses a contact belonging to that subspace which is closest to the multicast group, i.e. the node whose n-bit prex is closest to n-bit prex of one of subtrees belonging to the multicast group.

The initiator node then sends the message to the chosen node and asks the chosen node to be responsible for multicasting the message to the n-level subtrees belonging to both that subspace and the multicast group.

The above process continues until all n-level subtrees in the multicast group have received the message.

Discussion and Analysis. Using the same analysis with broadcast algorithm discussion, if log 2 U K < V , it takes O(log 2 U K) hops to multicast the message to the destination n-level subtrees. Otherwise, it takes

V + O(log 2 K U • V ) hops.
3.3.1.9 Summary.

The routing cost in three OGP routing algorithms, illustrated in Tables 3.1, are the same and smaller than O(log 2 K). We notice that the routing cost only depend on the number of n-level subtrees and doesn't depend on the number of FOGP nodes.

Algorithms

Routing cost

n-level unicast O(log 2 U K) if log 2 U K < V V +O(log 2 K U •V ), if log 2 U K > V n-level broadcast n-level multicast Table 3.1:
The cost of routing in OGP routing algorithms.

Lightweight OGP protocol

The lightweight OGP protocol is performed by LOGP peers to communicate with FOGP peers. A LOGP peer maintains a routing list, which is a xed-size list containing information about some FOGP peers in the OGP overlay by periodically asking for the routing table of FOGP peers in its routing list and then using the information in these routing table for updating the routing list. At the bootstrap time, a LOGP peer known some bootstrap FOGP peers via external mechanisms such as from websites. A LOGP peer sends messages to standard overlays of which it is not member by simply sending these messages to the rst FOGP peer in its routing list which will forward its messages.

Cooperation application

We put the gure which illustrates the structure of a FOGP peer (Figure 3.1) here for the sake of clarity. The cooperation application in a FOGP peer is built on top of the OGP routing layer, and is responsible for following tasks:

Cooperation Application

• Launching the delivery of requests to P2P systems via the Native node or the OGP node or both and receiving results from these nodes.

• Transcoding of messages and data between formats of P2P systems and the intermediary formats dened by itself at interface level.

• Communication with each other.

The rst and the third tasks can be achieved easily. The intermediary formats, in the second task, vary from application to application. Therefore, we cannot introduce a common intermediary formats. In the next chapter, we introduce the IFP protocol, running on the top of OGP, which is an application allowing heterogeneous P2P lesharing networks to cooperate, together with the respective intermediary formats.

3.4

Evaluation of Protocols

Evaluation metrics

We characterized the OGP protocol by three metrics M 1 , M 2 , and M 3 . Here, M 1 is the success ratio for requests sent from a FOGP peer to the standard overlay containing the requested data and then back to the originator. M 2 is the number of hops in OGP overlay that a request passed in the successful routing, i.e. the routing cost while M 3 is the bandwidth generated by OGP protocol in a peer per minute, i.e. the cost for running OGP.

Similar to OGP protocol, the lightweight OGP protocol is evaluated by the three following metrics N 1 , N 2 , and N 3 . Here, N 1 is the success ratio of request sent to a Chapter 3. A Backward Compatible Framework for Cooperation of Heterogenous P2P Systems FOGP peer and the corresponding response is turned back, N 2 is the number of hops the request sent from a LOGP peer traversed to reach a FOGP peer, i.e. the routing cost, and nally N 3 metric represents trac generated by a LOGP peer in a given period of time, to discover and maintain its list of FOGP peers.

Experimental setup

To evaluate the OGP and lightweight OGP protocols, a complete system, in which the OGP overlay is used to interconnect dierent standard overlays, has been has been implemented and deployed in large scale infrastructure. The experiments consisted in testing the lookup of random data distributed across all of the standard overlays, with each piece of data unique. The FOGP and LOGP peers periodically looked up a random piece of data on any of the standard overlays. The FOGP peers used the n-level broadcast algorithm for the request broadcast which is the most comprehensive scenario. JOGP, a simple lookup protocol based on OGP and lightweight OGP, has been developed and implemented in Java for the experiments. Our experiments were performed on the French Grid5000 platform [G5k], which aims at providing a nation-wide testbed to study large scale parallel or distributed systems.

There are two experimental scenarios. The rst evaluates the metrics of the OGP protocol while the second for evaluating the metrics of the lightweight OGP protocol when performing data lookup with several kind of standard overlays. In both scenarios, twenty networks of various types -Chord, Kademlia, and Gnutella-are deployed. Each network constitutes 50 nodes. In the rst scenario, there are only FOGP peers and the percentage of FOGP peers varies from 6% to 40% while in the second scenario, the percentage of LOGP peers varying from 10% to 60% with the percentage of FOGP peer is set to 10% and 20%. The churn of nodes in all scenarios follows the Pareto distribution.

We evaluate the protocols in high churn environment which is expected to see in near future. In the rst scenarios, the lifetime mean of nodes is set to 900, while it is set to 1800 seconds in the second scenario. The parameters of the two scenarios are given in Each experiment includes 3 successive phases: initial phase, stabilizing phase and evaluation phase. In the initial phase, nodes are created and join overlays. After all nodes join the overlays, experiment goes to second phase, i.e. stabilizing phase in which nodes complete their routing table and the system becomes stable. The evaluation phase to collect statistics starts when the second phase nishes. The duration of each of two last phases is T with T is the sum of lifetime mean and deadtime mean of a node in that experiment.

Each experiment is run 5 times. Average values and corresponding standard deviations of the metrics are plotted in all of the gures illustrate the experiment results.

Software

The software for evaluating the OGP framework constitute twofold: JOGP: a P2P node client, which implements following protocols: OGP, lightweight OGP, Kademlia, Gnutella and Chord. It can be instantiated as OGP node, lightweight OGP node, Kademlia node, Gnutella node and Chord node. Every kind of node provides PUT and GET functions.

Manager: the experiment manager, which performs following tasks:

1. It automatically deploys the inter-connected overlays in large scale on Grid5000 platform using the conguration read from conguration le (a text le). In the conguration le, user can dene various experiment parameters such as the number of overlays, the protocol of each overlay, the percentage of OGP, LOGP nodes, the duration time of the experiment, the time interval for lookup data, etc.

2. It launch the processes of PUT and GET data of random nodes using the conguration read from conguration le.

3. It collects statistics of the experiments such as the success rate of GET operation, the number of hops of successful GET operations, the numbers of messages generated by each node, etc.

The software are available on the website: http://www-sop.inria.fr/members/ Giang.Ngo_Hoang/software.html

Experimental results

Lookup eciency

In this experiment, we evaluate the success rate of operations performed by the FOGP peers, i.e. the M 1 metric and the success rate of operations performed by the LOGP peers, i.e. the N 1 metric.

The OGP protocol. The results of the M 1 metric is illustrated in Figure 3.14. The Lifetime mean of 900s and Lifetime mean of 1800s lines represent the M 1 metric in the lookup system with the lifetime mean of nodes is set to 900s and 1800s, respectively.

From Figure 3.14, we see that the two lines share mostly the same shape and the line Lifetime mean of 1800s stays above the line Lifetime mean of 900s. The Lifetime mean of 1800s and Lifetime mean of 900s lines dramatically increase from 77% to 97% and from 68% to 94% respectively with the increase of the percentage of FOGP peers from 6% to 10%, but only slightly vary in the range from 97% to 99% and 94% to 98% respectively when the percentage of FOGP peers is increased from 10% to 30%. The standard deviations of two lines are about 3 as the percentage of FOGP peers is set to 6% and stay in the range from 1.5 to 2 as the percentage of FOGP peers is increased from 10% to 30% Discussion and analysis. The reason for the trend of values of M 1 metric is as follows: with 6% of FOGP peers, the number of FOGP peers per overlay is 6% • 50 = 3, meaning that there are 3 gateways to enter each standard overlay. In a high churn environment, Lifetime mean of 1800s The fact that values of M 1 varies from 94% to 98% and 97% to 99% when the percentage of the FOGP peers is ≥ 10% in cases the lifetime mean is set to 900s and 1800s respectively shows the eciency of the OGP protocol. If a piece of data exists in a standard overlay, a FOGP peer will reach that overlay and the found data will be forwarded back to that FOGP peer with a 94%-98% and 97%-99% probability respectively.

The low standard deviation when the percentage of the FOGP peers is ≥ 10% shows the stable of OGP routing. In higher churn rate, i.e. nodes join and leave the overlays more frequently, the probability of a contact in routing table of an FOGP node become unavailable is higher, then the probability of this entry fails to perform the OGP broadcast is higher. Therefore, the values of M 1 metric is lower in higher churn rate environment. That why the line Lifetime mean of 1800s stays above the line Lifetime mean of 900s.

The lightweight OGP protocol. Figure 3.15 illustrates the values of the N 1 metric.

The two lines FOGP peers of 10% and FOGP peers of 20% represent values of N 1 metric with 10% and 20% of FOGP peers, respectively. From the gure we can see that the two lines vary from 99% to 100% when the percentage of LOGP peers comes from 10% to 60%. The standard deviation are only 1 for all cases.

Discussion and analysis. The results show that when a LOGP peer performs a lookup, the percentage of requests successfully sent to FOGP peers, and the percentage of found data successfully sent back to that LOGP peer is nearly 100%, i.e. highly ecient.

Routing cost

In this section, we evaluate the M 2 metric of the OGP protocol, i.e. the routing cost or the number of hops that the request traversed over the OGP overlay in a successful We can see from the gure that the two lines both increase, from about 3.3 to about 3.6 as the percentage of FOGP peers rises from 6% to 10%, and then slightly vary in the range between 3.6 and 3.9 as the percentage of FOGP peers rises from 10% to 30%. The experiment shown that the values of M 2 metric is approximately the expected constant when the percentage of FOGP nodes larger than 10% while smaller than expected constant with the 6% of FOGP. The reason is as following. In high churn rate environment, the routing with more hops fails at higher probability than the routing with less hops (each hop has a certain probability of failure). In our experiment, at 6% of FOGP peers, the ratios of success routing, i.e. M 1 , are only 68% and 77% in cases the lifetime mean is set to 900s and 1800s respectively. This means the number Chapter 3. A Backward Compatible Framework for Cooperation of Heterogenous P2P Systems of routing with more hops which fails is considerably higher than the number of routing with less hops which fails. Hence the average hops of success routing, i.e. M 2 , is lower than the expected constant. When the percentage of FOGP nodes increases from 10% to 30%, values of M 1 are near to 100% thus values of M 2 also approximately the expected constant.

Trac

This section evaluates the trac generated by a FOGP peer on OGP overlay (M 3 metric) and a LOGP peer to maintain its OGP list (N 3 metric) in a period of time.

The OGP protocol. Figure 3.17 shows the trac generated by a FOGP peer on the OGP overlay during one minute when the percentage of FOGP peers increases from 6%

to 30% (the FOGP line) and the trac generated by a Kademlia node during one minute (the Kademlia line)

From Figure 3.17, we can see that the FOGP line rise from around 61 messages/node/minute to about 69 messages/node/minute and then around 97 messages/node/minute, as the percentage of FOGP peer increase from 6% to 10% and then to 30%, respectively. The gure also show us the Kademlia line is a horizontal line at around 58 messages/node/minute. Discussion and analysis. The trac generated by an FOGP peer is increased as the percentage of FOGP peer increase from 6% to 30% since with the increase of the percentage of FOGP peers per overlay, the size of the OGP overlay increases (from 60 nodes to 300 nodes) and so does the trac for maintaining it. In our scenario, as shown in the evaluation of M 1 metric, OGP achieves high exhaustiveness with only 10% of peers are FOGP peer, at this point the trac generated by a FOGP node is about 20 % higher than the trac generated by a Kademlia node. This shows the ecient of OGP protocol in term of generated trac.

The lightweight OGP protocol. Trac generated by a LOGP peer for maintaining its FOGP peer list (the N 3 metric) as the percentage of LOGP peer increase from 10% to 60% is illustrated in Discussion and analysis. LOGP peers generate little trac for maintaining its routing list (around 2 messages/node/minute), which also does not depend on the percentage of FOGP peers and the percentage of LOGP peers in the lookup system. This feature proves the scalability of inter-overlay lookup system with the participation of LOGP peers.

Related works

As discussed in the literature review, the largest distinguish feature of the cooperation model introduced by current work, comparing with other models, is the decoupling of inter-overlay routing function and application bridging function.

In this section, we compare the inter-overlay routing solution proposed by current work with the inter-overlay routing solutions proposed by other studies based on following dimensions: the types of applicable overlays, the back-ward compatible ability, the scalability, the routing scheme. This is much higher than trac generated by FOGP and LOGP in current solution.

Chapter summary

In this chapter, we have introduced an ecient model for backward-compatible cooperation of heterogeneous P2P systems. The model consists of the OGP framework for inter-overlay routing and the cooperation application on top of the OGP framework, mapping the interface of these P2P systems to a mediatory interface.

The evaluations of the OGP protocol indicate that having only 10% of peers as FOGP peers is sucient for achieving a high success ratio of round trip inter-overlay routing operations in high churn conditions: more than 94% and 97% success ratio is achieved when the lifetime mean of a node is 900s and 1800s, respectively. Both FOGP and LOGP peers are proven to be ecient in terms of the number of hops needed for data lookup.

LOGP peers need only one hop to reach FOGP peers while the number of hops a lookup traversed over the OGP overlay only depends on the number of overlays inter-connected by the OGP overlay. The experiments also show that a LOGP peer generates the trac nearly as same as that generated by a blind peer. This, coupled with control over the routing between standard overlays makes our inter-overlay routing solution scalable.

In the next chapter, we will develop a complete solution for cooperation of P2P le-sharing networks.

This chapter relies on following conference papers: In this chapter, we develop a complete cooperation solution for cooperating heterogeneous P2P le-sharing networks using the cooperation framework presented in Chapter 3.

P2P le sharing networks provides their users two main operations including uploading and downloading les so that the users can share their les to other users in the same network, and get les from them, respectively. However, current P2P le sharing networks use incompatible protocols and mechanisms for these operations. For the downloading le operation which is constituted by two phases, namely search and download, most of le sharing networks support the search capability while BitTorrent network, the current most widely used P2P le sharing network, doesn't support.

Moreover, the routing of search messages in the networks supporting search capability depend on the peculiar overlay networks which dier from each other in many aspects.

For example, in topologies and routing algorithms, overlays such as Kademlia are based on structured topologies with deterministic routing, while overlays based on Gnutella are based on unstructured topologies and ooding routing. Overlay networks can also use various types of queries as well as dierent encoding messages algorithms.

The mechanisms used in the download phase are also dierent between networks. In some P2P le sharing networks such as BitTorrent, KAD, peers download the expected le from multiple sources at once while in others like Gnutella, the le is downloaded from a single source. The protocols for exchanging les used in the above P2P le sharing networks are dierent from each other, too.

As a matter of fact, these incompatibilities prevent the cooperation between dierent P2P le-sharing systems while cooperation of these networks promises many benets.

For example, the resource space that a user can reach is largely increased; the overall storage is signicantly saved because the number of copy of a le is reduced; the content redundancy is easily to achieved.

In this chapter, we introduce a solution for co-operating heterogeneous P2P lesharing networks which is applicable for all current P2P le-sharing networks. In our

Cooperation schemes

Users are provided two schemes of cooperation, namely inter-network downloading and inter-network uploading. While the inter-network uploading scheme allows the users to upload their les to any network, the inter-network downloading allows users to download les from any network.

Currently, the P2P le-sharing networks can be classied into two categories: searchable network and non-searchable network based on whether the network supports the search capability or not. Most of these networks today are searchable network which allow users to search le information which is located at peers in the network using the search protocol of that network. Examples of searchable networks are Kad, Edonkey and Gnutella. There is only one non-searchable network today, i.e. BitTorrent which requires the users to download the .torrent le from outside sources such as websites.

We dierentiate these kinds of networks in the cooperation schemes.

Following, we describe the two cooperation schemes.

Inter-network uploading

The processes of inter-network uploading in which the destination network is searchable and the destination network is non-searchable are illustrated in Destination network is searchable. The uploading process for the case in which the destination network is searchable (see Figure 4.3(a)), happens as following.

Step 1. The initiator, which is a FOGP peer or a LOGP peer, sends upload requests, following OGP protocol via its OGP node or LOGP node respectively, to the recipients which are FOGP peers belonging to a group of networks to which the initiator wants to upload the le.

Step 2. Upon receiving the request, a recipient sends the response, following OGP protocol via its OGP node, notifying the initiator whether the upload request is accepted.

Step 3. Upon receiving the notication, if the upload request is accepted, the initiator peer sends the le to the recipient following the IFP protocol.

Step 4. The recipient then uploads the le to its standard network via its Native node which uploads the le using the uploading mechanism of that network. Upon nishing the upload operation, the recipient sends the acknowledgement back to the initiator following IFP protocol.

Chapter 4. Backward Compatible Cooperation of Heterogeneous File-Sharing Networks Destination network is non-searchable. The uploading process for the case in which the destination network is non-searchable, i.e. BitTorrent, (see Figure 4.3(b)) is dierent from the one for the case in which the destination network is searchable as following:

Step 4. Upon receiving the le from the initiator, the recipient create .torrent le for the le and register the .torrent le with some trackers. Then the recipient sends the torrent le back to the initiator.

Step 5. Upon receiving the .torrent le, the initiator uploads it to somewhere such as web sites.

Inter-network downloading

The inter-network downloading operation constitutes two phases. The rst phase includes delivering of search request to a group of networks and then receiving of search results from these networks. The second phase is to obtain the searched le from certain network. Among two above phases, the rst phase is enabled by OGP protocol while second phase is achieved by IFP protocol.

The inter-network downloading operation are illustrated in the Figure 4.4 and the The destination network is searchable. The process of inter-network downloading illustrated in Figure 4.4 is sketched as following:

Step 1. The initiator peer, belonging to one P2P le sharing network, deliveries the search request to another network or a group of other networks or to all other networks, via OGP overlay using OGP unicast, OGP multicast or OGP broadcast respectively.

Step 2. The recipient peer which is a FOGP peer and belongs to destination network, upon receiving the search request, convert the search request from format of IFP to format dened by its network. It then launches the search on its network using search mechanism of the network via its Native node.

Step 3. Upon receive the search result, the FOGP peer sends the result and its contact information to the initiator node via OGP overlay.

Step 4. Upon receiving the search result from the recipient peer, if the result indicates the searched le exist on the destination network, the initiator peer directly contacts with the recipient asking it to retrieve certain le using IFP protocol. Step 5. The recipient peer, upon receiving the download request, retrieves the list of peers hosting the le via its Native node which obtain this list following the protocol of that network.

Step 6. If the destination network support multiple sources download, the recipient peer can, via IFP protocol, ask some other FOGP peers belonging to the destination network, which are in its FOGP peer list, to download some parts of the le.

Otherwise, it is responsible for downloading the entire le.

Step 6. The le or the parts of le is then downloaded by these FOGP peers following the protocol of destination network.

Step 7. Upon receiving the le or the parts of le from hosting peers after issuing the download request, the FOGP peers including the recipient send the le or the le parts back to the initiator node following IFP protocol. In the later case, the information for joining the parts is sent along with these parts. The destination network is non-searchable. The inter-network downloading operation in the case in which the destination network is non-searchable (see Figure 4.5), has following dierences comparing to the case the destination network is searchable.

• In step 2, upon receiving the search request from the initiator peer, the recipient noties the initiator that its network doesn't support search capability instead of launches the search on its standard network.

• In step 3, upon receiving the notication, the initiator peer searches and retrieves the .torrent le from external server and then send the download request along with this information to the recipient.

From this point, the operations in two cases are the same.

IFP protocol

In a FOGP peer and a LOGP peer, the IFP protocol is run by Cooperation Application, therefore we use Cooperation Application with the meaning of IFP protocol in this section.

4.3. IFP protocol 59

Tasks

The IFP protocol is responsible for the following tasks:

1. Launching the processes of searching, downloading and uploading les on P2P lesharing network contains the peer and receiving the results via the Native node.

2. Launching the delivering of search requests or upload requests to P2P le-sharing networks don't contain the peer and receiving the results from these networks via the OGP node.

3. Introducing the intermediary formats of search requests, search results, download requests and upload requests and transcoding of those requests between the formats dened by P2P le-sharing networks and the intermediary formats.

4. Delivery of download requests on P2P le-sharing networks don't contain the peer and exchanging les.

5.

Communicating with, and transferring the les between nodes including both FOGP and LOGP nodes.

Transcoding of messages

In our model, there is a set of messages are transferred back and forth between P2P le-sharing networks and OGP overlay. These messages belong to following categories:

search request, search result, download request and upload request. Because the formats of these messages are various in dierent P2P le-sharing networks, the IFP protocol denes an intermediary format for each kind of message. As the messages cross back and forth between P2P le-sharing networks and OGP overlay, they are also transcoded between specic formats and intermediary formats respectively. The transcoding of these messages happens at the FOGP gateways. In this section, we describe the algorithm of IFP protocol for inter-network downloading scheme which allow user to download les from any P2P le-sharing network.

Algorithm description. The Cooperation Application, i.e. the IFP protocol, functions as follows:

Step 1. The Cooperation Application in the initiator peer asks the OGP node to send the search request to destination networks. The case that the initiator search les on its network is trivial, thus is not shown for the sake of clarity.

Step 2. The Cooperation Application in the recipient peer, which is a FOGP peer belonging to the destination network, upon receiving the search request, acts as follows: if the destination network is BitTorrent, it return BitTorrent indication i.e. no search capability via OGP node. Otherwise, the Cooperation Application converts the search request from IFP format to the format dened by the destination network. It then launches the search on this network via its Native node.

Upon receiving the search result, the Cooperation Application converts this result to the IFP format and then sends the result along with the information of peer to the initiator via the OGP node.

Step 3. Upon receiving the search result from the recipient peer, if the result indicates the destination network as BitTorrent, then the user himself has to search and download the torrent le from a website. The Cooperation Application then send the torrent le to the recipient in the download request. Otherwise, if the destination network is not BitTorrent and if the sought le exists on the destination network, the Cooperation Application in initiator peer contacts with the recipient asking it to retrieve the le.

Step 4. The Cooperation Application in the recipient peer, upon receiving the download request, retrieves the list of peers hosting the le via the Native node. If the destination network supports multiple-source download, the Cooperation Application can ask some other FOGP peer belonging to destination network, which are in its FOGP peer list, to download some parts of the le. Otherwise, it is responsible for downloading the entire le using the Native node.

Step 5. The Cooperation Application in the FOGP peer, upon receiving the request for downloading some parts of the le, downloads these parts via the Native node.

Step 6. Upon receiving the le or le parts from the hosting peers after issuing the download request, the Cooperation Application in the recipients send the le or le 4.3. IFP protocol 61 parts back to the initiator node and the information for joining the parts is sent along with these parts.

Pseudo code. In this paragraph, we present the pseudo code of above description.

First we introduce some notion used in the pseudo code.

• CooApp, OGP N ode, N ativeN ode are Cooperation Application, OGP node and Native node in a peer respectively.

• N ative_Search_M ess, IF P _Search_M ess are the search messages in the forms of native format and intermediary format respectively.

• N ative_Search_Result, IF P _Search_Result are search results in the forms of native format and intermediary format respectively.

• IF P _Download_M ess, Download_P art_Request are messages for downloading a le and some part of a le dened by IFP protocol respectively.

• contactInf o is the contact information of a peer.

• destN ets is destination P2P le-sharing networks which will receive the message.

• part_inf o is the information of some parts of a le.

• torrent_f ile is the .torrent le of a le which is got from websites.

• send(), transcoding(), download() are methods for sending messages, transcoding of messages and downloading le or parts of the le respectively.

Inter-network uploading

The inter-network uploading scheme allows the users to upload their les to any network.

Algorithm description. The algorithm of IFP protocol, i.e. the Cooperation Application, in the inter-network uploading scheme is as follows:

Step 1. The Cooperation Application in the initiator, which is a FOGP or a LOGP peer, sends the upload request to recipients which are FOGP peers belonging to a group of networks that the initiator wants to replicate the le to, via its OGP or LOGP node.

Step 2. Upon receiving the request, the Cooperation Application in a recipient sends the response notifying the initiator whether the upload request is accepted or not via its OGP node.

Step 3. Upon receiving the notication, if the upload request is accepted, the Cooperation Application in the initiator peer sends the le to the recipient.

Step 4. Upon receiving the le, if the recipient's network is BitTorrent, the Cooperation Application in the recipient creates a torrent le for the le and registers the torrent le with some trackers, using its Native node. Then the Cooperation Application sends the torrent le back to the initiator. If the recipient's network isn't BitTorrent, the Cooperation Application uploads the le to its standard network using the Native node and sends the acknowledgement back to the initiator.

Pseudo code. Beside the notion presented in the pseudo code of inter-network downloading algorithm, we introduce some more notion as following:

• U pload_Request, Acceptance_N otif y, Ack are messages dened by IFP protocol for requesting to upload a le, answering whether an upload request is accepted or denied and giving the acknowledgement respectively.

• f ile_attributes is attributes of a le.

• upload(), createT orrent(), register() are methods for uploading a le, creating the .torrent le of a given le and registering a le with certain tracker respectively. Manager: the experiment manager, which perform following tasks:

1. It automatically deploys the inter-connected le-sharing networks in large scale on Grid5000 platform using the conguration read from conguration le (a text le).

In the conguration le, user can dene various experiment parameters such as the number of overlays, the protocol of each overlay, the percentage of OGP, LOGP nodes, the duration time of the experiment, the time interval for lookup data, etc.

2. It launch the upload le, search and retrieve le processes of random nodes using the conguration read from conguration le.

3. It collects statistics of the experiments such as the success rate of upload le, download le operations.

The software is available on the website: http://www-sop.inria.fr/members/ Giang.Ngo_Hoang/software.html From the gure, we can see that the Rd and Ru has same trend and Ru line stays above Rd line. The Rd comes from around 92 % to 97% when the percentage of FOGP peer rises from 3% to 5% and then slightly vary in the range from 97% to 99% as the percentage of FOGP peer increase from 5% to 30%. The Ru value increase from round 95% to 99% and then slightly vary in the range from 99% to 100% as the percentage of FOGP peer grow from 3% to 5% and then to 30%.

The Figure 4.7 also show that the RSD values of Ru and Rd metrics vary in the range from 0.6% to 2.7% as the percentage of FOGP peers vary from 3% to 30%.

Analysis and discussion. The experiments shows an interesting result that our model can achieve cooperation eciency, namely Rd and Ru values are larger than 97% and 99% respectively, with only a small number of FOGP peer (not less than 5%). The low values of RSD show the stable of the experimental results.

The reason for the trend of Rd and Ru is as follows. Each le-sharing network has a number of FOGP peers serving as the gateways for exchanging message and data with other networks. In a high churn environment, some of them can go down for at certain time. During this time, if the number of FOGP peers in a network is too small, some FOGP peers in other networks do not have any backup gateways for the downed gateways of that network in their routing tables. With 3% of FOGP peer, each network has 3% • 100 = 3 gateways and this number is not enough for the FOGP peers to build their routing table with adequate number of backup. While with 5% of FOGP peers, The inter-network download process constitutes more communication hops than inter-network upload process. In churn environment, each communication hop has a probability of failure due to the failure of peers; hence the success probability of internetwork download operation is smaller than the one of inter-network upload operation.

That is why the Ru line stays a bit higher than Rd line.

The cooperation eciency on percentage of LOGP

In this step, the percentage of FOGP peers is set to 5% and 10%, i.e. the percentage ensuring the cooperation eciency in the system without LOGP, while the percentage of LOGP peer varies from 10% to 60%. The parameters of this scenario are given in Table 4.1, Scenario 2.

The experimental results are illustrated in the Figure 4.8. As the experimental results when the percentage of FOGP peer is set to 10% and 5% are similar, we only show the results in the case the percentage of FOGP peer is set to 10% on the gure for the sake of clarity. The Figure 4.8 shows that the Rd and Ru values slightly vary in the range from 98% to 99% and from 99% to 100% respectively when the percentage of LOGP peers varies in the ranges from 10% to 60%. In case the percentage of FOGP is set to 5%, the Rd and Ru values also slightly vary in the range from 97% to 99% and from 99% to 100% respectively as the percentage of LOGP peers stays in the ranges from 10% to 60%. The RSD values are less than 1.5% in all cases.

Analysis and discussion. We can see that our model achieves cooperation eciency with every percentage of LOGP. This because the LOGP peers rely on FOGP peers for cooperation with peers in other networks while the communication between LOGP peers and FOGP peers is very ecient (this is shown in Chapter 3). The fact that our model achieves cooperation eciency with every percentage of LOGP is an important result.

It means that any user who has not enough resources to act as FOGP peer can act as LOGP peer with high cooperation eciency.

Tradeo between routing cost and load on FOGP peers

In this section, we investigate the tradeo between the routing cost of search messages on OGP overlay and the load on FOGP peers by analysis.

In our model, a peer can download a le which is in other network from one FOGP peer or multiple FOGP peers depending on the properties of the network containing the le. Each le or part of le is transferred though only one FOGP peer. Therefore, on average, we can assume if a le is downloaded, it is transferred though one FOGP peer.

When a peer uploads a le, the le is also transferred via only one FOGP peer. We also assume that all FOGP peers and LOGP peers periodically download and upload les at the same rate. We dene the unit of load is the number of les that a FOGP peer or a LOGP peer upload and download in a period of time.

The dependence of load on percentage of FOGP peers and percentage of LOGP peers and the dependence of routing cost on percentage of FOGP peers are shown in Figure 4.9 and Figure 4.10 respectively.

In Figure 4.9, the four lines with blue, red, green and brown colors illustrate the load on a FOGP peer in the cases the percentage of FOGP peers is set to 5%, 10%, 20% and 40% while the percentage of LOGP peers varies from 0% to 95%, 90%, 80% and 60% respectively. At 0% of LOGP peers, the load on each FOGP peer is one unit in all cases. As the percentage of LOGP peers increase while the percentage of FOGP peers is xed, the load on FOGP peers increase to 20, 10, 5 and 2.5 units respectively due to the increase of number of les which are uploaded and downloaded by LOGP peers transferred through the FOGP peers.

In Figure 4.10, the blue line illustrates the routing cost over OGP overlay with the U parameter in the table 3.1 is set to 1 while the percentage of FOGP peer increases from 5% to 100% and the unit of y-axis is the routing cost over OGP overlay when the 4.4. Evaluation 69 percentage is set to 5%. As the percentage of peer increase from 5% to 100%, from the table 3.1, we can see that the routing cost over OGP overlay crease from 1 unit to around

Related work

As mention in the Chapter 3, there has been only one previous work [START_REF] Konis | [END_REF] on cooperation of P2P le-sharing networks. However, this study proposed the mechanism for cooperating only purely queries ooding-based le-sharing networks which constitute a very small portion of current le-sharing networks.

Author in [START_REF] Konis | [END_REF] evaluated their model by simulating two unstructured and purely query ooding-based le-sharing networks cooperating with each other. However, due to the large dierence in application area, i.e. we evaluated our model with all three typical kinds of P2P le-sharing network today, therefore it is not adequate to compare the evaluation results between our work and the work in [START_REF] Konis | [END_REF]].

Hence we did not perform the comparison here.

Chapter summary

In this chapter, we have introduced a model for backward compatible heterogeneous A common feature of many CPS systems is the large amount of sensors and actuators are spread over wide geographic areas for purposes of monitoring and controlling. One of the challenges for these systems is to scalable collect and process the huge amount of data generated by those sensors and actuators. In this chapter, we investigate the ability of using inter-connecting P2P overlays to address above challenge in smart grid, a typical example of CPS, as a case study.

Smart Grid is a data communication network integrated into the electrical grid that collects and analyzes data captured in near-real-time about power transmission, distribution, and consumption. Using the data, Smart Grid technology can provide predictive information and recommendations to utilities, their suppliers, and their customers on how to better manage the electric power [Cisco 2009]. nologies that provides an intelligent connection between consumers and system operators.

In AMI system, smart meters measure and collect the energy consumption information, power quality from customers' premises. The metering data is, on-scheduled or ondemand, sent to Metering Data Management System (MDMS) which is a database with analytical tools allowing the interaction with system side applications such as Consumer Information System (CIS), Outage Management System (OMS), Enterprise Resource Planning (ERP). MDMS performs the validation, editing and estimation on the data and feeds the appropriate data to the system side applications to help optimize operations, economics and consumer service. 5.3. Related work and our focus 75 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Communication networks from the smart meters to local data concentrators.

Local data concentrator

Local data concentrators collect metering data from smart meters.

Back-haul communications networks from concentrators to corporate data centers.

Meter Data Management Systems (MDMS) is a database with analytical tools allowing the interaction with system side applications such as Consumer Information System (CIS) which manages the utility billing and customer information, Outage Management System (OMS) which processes outage reports and display outage information to utility operators, power quality management and load forecasting systems, Geographic Information System (GIS) which captures, stores, manipulates, analyzes, manages, and presents all types of geographical data. One of the main tasks of AMI is to perform validation, editing and estimation on the AMI data to ensure that the data, fed to system side applications, is complete and accurate.

Data integration into existing and new software application platforms, i.e. system side application platforms.

Related work and our focus

Several communication architectures for AMI have been proposed in the last few years. Metering Infrastructure in SmartGrid

The traditional communication architecture [ami 2008] being one central Operation Center (OC) receiving metering data from all customers through local data concentrators. With this centralized architecture, all metering data go through MDMS at OC which then feeds the appropriate data into system side applications. This architecture makes the system simple and easy to manage. However, as the scale of system ups to large, this architecture is suered from several non-scalable problems. First is the high possibility to create the data communication bottlenecks in the zones close to the OC, pointed out by Author of [START_REF] Jiazh | [END_REF]. Second is the unfeasibility in data processing due to the large data load, pointed out by Author of [Gerdes et al 2009].

The Author of [START_REF] Jiazh | [END_REF]] introduced a model with some similarities with Content Delivery Network (CDN) [CDN] in which a central MDMS connects to multiple distributed MDMSs. They introduced an algorithm to calculate the optimal deployment of distributed MDMSs in their model. The distributed architecture allows the aggregation of data thus solves the problem of non scalability in data collection.

The Author of [START_REF] Meili | [END_REF] proposed an infrastructure based on group communication using hybrid adaptive multicast over public networks. By relying on group communication over public networks, this approach reduces the cost of investment but the reliability of communication as well as the latency of data collection are not guaranteed.

The Author of [Arena et al 2010] investigate the storage and monthly billing processing architecture. They compared storage techniques including the centralized relational database, the distributed relational database and the key-value distributed database storage. Their work focuses on achieving the scalability in processing metering data rather than achieving the scalability in collecting the metering data.

The Author of [START_REF] Rusitschka | [END_REF] proposed a model of using cloud computing for smart grid data management. The advantages of computing are the ability to provide huge storage, powerful processing and communication. In their work, while focusing on providing sucient resources for smart grid data management, they do not investigate the distribution of necessary resources, i.e. points of data collection and management.

In our work, we focus on introducing a communication architecture for scalable data collection and management. Author of [START_REF] Jiazh | [END_REF]] also proposed a communication architecture for scalable data collection using a CDN like model for MDMSs network.

In our work, the MDMSs are connected by a P2P network which is more resilient with failure than the model proposed in [START_REF] Jiazh | [END_REF]. The scope of our work does not cover the investigation of data processing and integration algorithms.

AMI architecture

DHTs are scalable P2P architectures. However, their at structure is not suitable for the aggregation of metering data. Hierarchy is probably the most natural structure for this Each OC contains a MDMS for collecting and analyzing metering data from customers belonging to the area that the OC is responsible for. The MDMSs are equipped with analytical tools to interact with system-side applications which locate in that OC. As each OC has one MDMS, we use a cube to present both an OC and the perspective MDMS. Applications in an OC are presented by a can. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Data Concentrator

Smart Meter 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 The level-1 MDMS is responsible for whole area where AMI covers. The whole area is divided into multiple sub-areas that each of which is covered by a level-2 MDMS. An area covered by a level-2 MDMS can be further divided into multiple sub-areas that each of which is covered by a level-3 MDMS and so on.

The level-n MDMS managing area S n and the level-(n + 1) MDMS managing area S n+1 such that S n+1 ⊂ S n are called parent and child of each other respectively.

All MDMSs are connected in P2P architecture as following:

• All children of a level-n MDMS with n ≥ 1 are organized in a DHT overlay network.

The MDMS at level-n keeps contacts of all of its MDMSs children at level-(n + 1) Metering Infrastructure in SmartGrid

while a MDMS at level-(n + 1) maintains the contact of its parent and contacts of parent's neighbors in the parent's overlay. In case that the parent MDMS is at level-1, its children maintain the contact of parent only.

• When the parent of a MDMS fails, the MDMS replaces its parent by the closest neighbor of the parent. If the old parent recovers from failure, the MDMS automatically changes the parent back to the old one. A MDMS also periodically check the aliveness of its children and remove the failed children from its children list.

Each MDMS at highest level manages a number of data concentrators following the client-server model. Each of the data concentrator collects metering data from a number of smart meters.

Data collection and processing

The processes of collecting and processing data is illustrated in the Figure 5.3. The information can travel in the system in three directions: upward direction, downward direction and intra-overlay. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Data Concentrator

Smart Meter 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 A MDMS at highest level can send the data or command to all of its users or to a group of its users or even to a specic user.

Intra-overlay. In this direction, the data and commands or other information can be exchanged between MDMSs in one overlay. The communication follows the protocol of that overlay.

System-side applications are deployed in OCs at appropriate levels depend on their functions, characteristics and requirements on latency. The applications that is sensitive with latency such as OMS, Demand Response (DR) should be deployed in OC at highest level, i.e. close to the smart meters, while other applications which are less sensitive with latency such as Billing system can be located in OC at lower level.

The distribution of applications in high level OCs also help to reduce the throughput of data owing toward the lower level OCs thus make the system more scalable in term of data communication.

The MDMS and system-side applications co-located in one OC can interact with each other in several patterns. The MDMS can on-demand or on-scheduled feeds data to system-side applications. Other way of interaction exploits the Publish-Subscribe model [PubSub] in which these applications subscribe for certain kind of event such as the outage ags generated by AMI system so that these applications are notied when the events happen. To enable these interactions, the utility can deployed analytical tools or publish-subscribed applications a long with the MDMS to provide the appropriate data to the applications.

We note that the information from system-side applications can be sent to customers via other paths such as Internet instead of AMI infrastructure. However, these communication paths are outside the scope of this work.

System analysis

This section investigates the characteristics of our architecture. We rst dene the meaning of some notation used in this chapter. The ∆ = notation means equal while the << notation means much less than. The parameters of the model are denoted as following:

• M : the number of smart meters in the system;

• L: the largest level of OCs;

• λ i : the number of messages generated by a smart meter in a period of time;

• By turning the number of aggregation levels and the number of OCs at each level, i.e. turning L and K n , utility can control the load on each OC, i.e. control throughput and power processing requirement for each OC, thus eliminating the data transmission congestion as well as the overload in power processing. Failure resilience. The proposed communication architecture exploits the resilience with failure advantage of P2P in managing the MDMS network.

According to [Cascio], resilience means the capacity of a system to withstand sudden, unexpected failures, and (ideally) to be capable of recovering quickly afterwards. Resilience implies both strength and exibility in the sense that a resilient structure would bend, but would be hard to break.

In our proposed architecture, the data of a MDMS can be replicated at its neighbors in the DHT overlay. As the MDMS fails, the closest neighbor automatically replaces it.

On the other hand, a MDMS normally sends the data to its parent MDMS. In case the parent MDMS fails, the MDMS automatically send the data to the closest neighbor of the parent MDMS.

Similarly, a data concentrator normally sends the data to its parent. In case the parent fails, it will send the data to closest neighbor of the parent. To deal with the situation that the level-1 OC fails, utility can deploy P2P applications for retrieving, querying data over overlay of MDMS at level-2.

As a matter of fact, even if the failure happen in some MDMSs, the system will quickly recovers and then works normally.

Low cost of maintenance and operation. With the large scale and the growth of AMI infrastructure, the self-organization ability of the MDMS network is very important in the sense that it helps the utility reduces the operation and maintenance cost. When the failures happen, the network automatically recovers without the human intervention.

As the scale of system change, utility can easily add or remove MDMSs with little early conguration.

Evaluation of communication infrastructure

In this section, we evaluate the communication eciency, the maintenance trac and the scalability of the proposed communication architecture.

Implementation of communication architecture

We implemented and evaluated the fundamental part of the communication architecture in which one MDMS overlay at level-n connects to multiple MDMS overlays at level-Chapter 5. A Scalable Communication Architecture for Advanced Metering Infrastructure in SmartGrid

(n + 1). We extended the Chord [START_REF] Stoic | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], a typical DHT, to implement these MDMS overlays as a case study. Other DHTs can also be used instead.

The other parts, namely the MDMS level-1 connect to overlay of level-2 MDMS and a MDMS connects to data concentrators in client-server architecture, are well investigated architectures. Therefore we did not implement and evaluate these parts.

The implemented architecture is illustrated in Figure 5.4.

MDMS level n+1

MDMS level n

Chord overlay

Chord overlay

Chord overlay

Chord overlay Chord overlay We assign an unique p-bits identier to each MDMS as following:

• The level-1 MDMS is assigned a random p-bits number.

• Each of the level-2 MDMSs is assigned a p-bits number in which q rst bits is random and p -q last bit is set to 0.

• Assume that a level-n MDMS with n ≥ 2 has identier with rst (n -1) • q bits is m 0 . Its MDMSs children, i.e. the MDMSs in OC at level-(n + 1) has identiers specied as following: rst (n -1) • q bits is m 0 , next q bits is random and p -n • q last bits is set to 0. Let X@Y denotes X is child of Y. Assume that Z is successor of Y. ID X , ID Y and ID Z are identiers of X, Y and Z respectively. Then we have that: The values of experiment parameters are described in the Node: a P2P node client, which can be instantiated as child node or parent node. Manage: the experiment manager, which performs following tasks:

X@Y if ID X ∈ [ID Y , ID Z )
1. It automatically deploys the inter-connected DHTs in large scale on Grid5000 platform using the conguration read from conguration le (a text le). In the conguration le, user can dene various experiment parameters such as the number of children overlays, the number of nodes per child overlay, the duration time of the experiment, etc.

2. It launches the dierent communication schemes between children peers and parent peers. shows that additional trac generated in a child peer is very small.

We note that the maintenance trac of a peer, running DHT protocol, increases when the number of peers in the DHT overlay increases. In our experiment, when the number of children overlay increases from 10 to 40, i.e. the number of parent peer also increases, the line parent vs. chord is slightly decrease. This means that the maintenance trac of parent overlay increases with slower rate than the maintenance trac of Chord overlay as the size of the overlay increases. This proves the scalability of parent overlay in term of maintenance trac.

Experiment results: Summary. The experiments shows that our proposed communication architecture achieves high communication eciency and low maintenance trac for maintaining children overlays. The architecture also features by the scalability in term of both the communication eciency and the maintenance trac.

Chapter summary

In

Conclusions

This thesis documented our work on two topics in which we exploit the inter-connecting of P2P overlay networks to allow the cooperation between P2P systems based on those networks and to establish the communication infrastructure for cyber-physical systems respectively.

Cooperation of P2P systems. With many P2P systems currently co-exist and compete with each other in dierent domains such as P2P le-sharing, instant messaging, P2P data storage, the cooperation to share the resources or services between them is expected. This motivated us to investigate the cooperation between heterogeneous P2P systems.

In this thesis, we introduced a cooperation framework for cooperation between heterogeneous P2P systems. The framework constitutes two parts. The rst one is the OGP routing framework which allows the inter-overlay routing to enable the communication across P2P systems. The second part is cooperation application, which is built upon the routing infrastructure across P2P systems, bridging these P2P systems at application level.

The OGP routing framework allows to form an OGP overlay which conveys messages back and forth between heterogeneous P2P overlays including both structured and unstructured ones. The routing inside a P2P overlay follows the protocol native to that overlay while the routing on the OGP overlay follows the OGP protocol.

As dierent application domain has its own semantic, we could not introduce a framework for cooperation application for all application domains. Instead, we introduced principles underpinning the building of cooperation application which is applicable to all application domains. The separation of inter-overlay routing function and interapplication bridging function is the fundamental dierent between current work and others in which the transcoding of messages between dierent P2P systems is built in in the routing protocols. The new approach introduced by current work bring the great exibility to the cooperation model thus makes the model more practical. Current model also allows the backward compatible in the sense that the peers, who are unaware of new Chapter 6. Concluding Remarks and Directions for Further Work protocols, still work normally. This is also an important feature which makes the model more practical.

As a case study, we introduce a complete solution for co-operation of heterogeneous P2P le sharing networks. The cooperation application, IFP protocol, denes a set of intermediary messages. The transcoding of messages between format of P2P le sharing networks and intermediary format happen when the messages cross the border of the P2P le-sharing networks. Our solution ensures backward compatible and is applicable for all current P2P le-sharing networks.

We evaluated the inter-overlay routing framework and the cooperation solution for P2P le-sharing networks via experiment on large scale French's Grid 5000 platform.

Inter-connecting DHT routing infrastructure. In the second topic of this thesis, we investigate the ability of using the inter-connecting P2P overlays as routing infrastructure for cyber-physical systems via a case study in which inter-connecting DHTs serves as the fundamental part of the AMI communication infrastructure in smart grid.

In the vision of smart grid, AMI faces the challenge of scalable collecting and managing a huge amount of data from a large number of customers. In this topic, we address this challenge by proposing to use a communication architecture composed by the mixing of P2P and client-server models. In the architecture, the MDMSs of utility are geographically distributed and hierarchically connected by inter-connecting DHT overlays. The MDMSs at highest level collect the metering data from smart meters following the client-server model. Via analysis and experiment on large scale platform Grid5000, we show that the proposed architecture featured by following characteristics: scalability in collecting and management data, resilience with failure, scalability and eciency in communication.

Further Work

There are many further works remain in the directions of this thesis.

Cooperation of real P2P le-sharing networks. In this thesis, we introduced a cooperation solution to cooperate P2P le-sharing networks and evaluated the solution with simple prototypes of three typical P2P le-sharing networks. However, cooperation of real P2P le-sharing networks requires more investigation. For example, the qualication in term of bandwidth and processing capacity, that a peer must have to be a FOGP peer, need to be specied. Another work is to propose schemes for dealing with the ooding request attack toward FOGP peers. An investigation about the ecient data retrieval when multiple data sources are available would be improving the performance of the system.

A framework for cooperation application. In this thesis, we proposed the principles underpinning the build of cooperation application. The next step could be a framework of cooperation application for bridging P2P applications in typical application domains such as P2P le-sharing, P2P instant messaging, P2P storage. One approach is to build this framework as the integration of multiple frameworks that each of which is for an application domain. Another approach is to build a common interface for multiple application domains and dene the mapping between specic interface of each application domain and the common interface.

Further Work 93

Cooperation of real instant messaging systems. There are many instant messaging networks with incompatible instant messaging protocols [IM]. Currently, to have these networks cooperate, one can combine the many disparate protocols inside the IM client application or inside the IM server application. With this approach, the changes in one protocol result in the changes in every multi-protocol IM client or multi-protocol IM server which implements the changed protocol. Our model provides another promising solution. Similar to cooperation of real P2P le-sharing networks, the cooperation of heterogeneous instant messaging systems requires a cooperation application which bridges these instant messaging systems at application level. Using our approach, an IM client or an IM server need to implement only one IM protocol and the cooperation application thus eliminates the need of changing when other protocols change.

Cloud-based applications. Cloud systems such as Amazon EC2, or NoSql databases, such as Amazon SimpleDB [simpleDB] or Cassandra [cassandra] or Google BigTable [START_REF][END_REF] usually rely on a computer cluster; they oer complete control of the computing resources, such as CPUs or memory. The OGP framework can be used to form a routing infrastructure over the existing cloud systems while the cooperation applications on top of the OGP framework enable the exchanging data between these systems and resolves incompatibilities. While the performances will be surely aected by network artifacts, the scalability of this solution and the advantages of using overlay network federation make this approach attractive.

Cooperation of P2P clouds. Many studies such as [START_REF] Babaoglu | [END_REF], Kavalionak et al 2012] investigated the combination between cloud computing and P2P networks in which cloud is built upon the P2P network to take the advantages of P2P such as scalability, failure resilience, self-organization. These P2P clouds can achieve cooperation by relying on the OGP framework for establishing an routing infrastructure throughout the clouds and using a cooperation application for cooperating these clouds at application level.

Exploiting the inter-connecting overlays in cyber-physical systems. There are many cyber-physical systems in various domains. They often expand in large geographic

Figure 2 . 2 :

 22 Figure 2.2: An example of search in Gnutella

Figure 2 . 5 :

 25 Figure 2.5: BitTorrent architecture and operation

  schemes are not complete and so simple, all of the previous solutions are not practical[Cheng 2007[START_REF] Liquo | [END_REF], Liquo at al 2010[START_REF] Cianc | [END_REF], Cianc at al 2012], i.e. it is dicult to cooperate P2P systems or limit in application area, i.e.[START_REF] Konis | [END_REF] is only for unstructured and purely ooding based queries.All of previous solutions are only applicable homogeneous overlays. The solutions in[Cheng 2007[START_REF] Liquo | [END_REF], Liquo at al 2010[START_REF] Cianc | [END_REF], Cianc at al 2012] are only for inter-routing between DHTs, i.e.structured overlays. The model in [Konis at al 2006] is only for inter-routing between ooding-based unstructured overlays. The solution in [Liquo at al 2009, Liquo at al 2010] requires the modication of all peers in overlays, i.e. peers which are unaware of new protocols cannot operate, which is not practical in reality. Solutions in [Konis at al 2006, Cheng 2007, Cianc et al 2011, Cianc at al 2012] ensure the backward compatibility in the sense that the native peers which are not aware of new protocols can operate normally, which is suitable for interrouting between existing P2P overlays. Only [Konis at al 2006] dealt with the cooperation of applications running on top of overlays. However, in their model, applications are only the unstructured, oodingbased P2P le-sharing applications with the same mechanisms of search and download le which is quite simple to solve. The authors in [Cheng 2007, Liquo at al 2009, Liquo at al 2010, Cianc et al 2011, Cianc at al 2012] did not deeply investigate how the applications can exploit their models. The P2P applications are normally not just send a request to other peers and receive

A

  FOGP peer, see Figure3.1, has several components:

Figure 3

 3 Figure 3.1: A FOGP peer

Figure 3 .

 3 Figure 3.2: A FOGP peer

Figure 3 . 3 ,Figure 3 . 3 :

 3333 Figure 3.3: Examples of cooperation

Figure 3 .

 3 Figure 3.4: A Binary tree for OGP peers with n=2

Figure 3 . 5 :

 35 Figure 3.5: An example of space devision

Figure 3

 3 Figure 3.6: The evolution of the routing table

Figure 3 .

 3 Figure 3.7: The tree of space

Figure 3 .

 3 Figure 3.8: Example of n-level unicast

Figure 3 . 9 :

 39 Figure 3.9: Operation performed by node A

Figure 3 .

 3 Figure 3.10: a. Operation performed by node B b. Operation performed by node E

Figure 3 .

 3 Figure 3.11: a. Operation performed by node C b. Operation performed by node G

Figure 3 .

 3 Figure 3.12: Broadcast tree routed from FOGP node A

Figure 3 .

 3 Figure 3.13: A FOGP peer

Figure 3 .

 3 Figure 3.15: Success rate of operations of an LOGP node

Figure 3 .

 3 Figure 3.16: Routing cost of OGP broadcast algorithm

Figure 3 .

 3 Figure 3.17: Trac of a FOGP node on the OGP overlay.

Figure 3 .Figure 3 .

 33 Figure 3.18: Trac of a LOGP node.

Figure 3 .

 3 Figure 3.19: (a) Trac of a node of compared protocols (b) Trac of all nodes of compared protocols

1.

  Giang Ngo Hoang, Luigi Liquori and Hung Nguyen Chan. Backward-Compatible Cooperation of Heterogeneous P2P Systems. The 15th International Conference on Distributed Computing and Networking, ICDCN 2014, accepted. 2. Giang Ngo Hoang, Luigi Liquori, Vincenzo Ciancaglini, Petar Maksimovic and Hung Nguyen Chan. A backward-compatible protocol for inter-routing over het-Introduction

52Chapter 4 .

 4 Backward Compatible Cooperation of Heterogeneous File-Sharing NetworksConcerning to uploading le operation, the peers hosting certain les can keep the information of these les locally as in a Gnutella network, or put the information to other peers, e.g. in a Kad network, or send the information to external websites such as in a BitTorrent network.

Figure 4 . 2 :

 42 Figure 4.2: Structure of a LOGP peer

  Figure 4.3(a) and Figure 4.3(b), respectively.

Figure 4 . 3 :

 43 Figure 4.3: Inter-network uploading

Figure 4 . 5 .Figure 4 . 3 .

 4543 Figure 4.5. The Figure 4.4 represents the scenario in which the destination network, i.e. the one contains the peer receiving the search request, is searchable while the Figure 4.5 illustrates the scenario in which the destination network is non-searchable, e.g. BitTorrent. The rules for colors of lines in the Figures 4.4 and 4.5 are the same as the one in theFigure 4.3. The blank rectangles represent the format conversion happen in FOGP peer to convert the requests and responses between the formats dened by IFP protocol and by protocols of standard networks.Here the initiator can be a FOGP peer or a LOGP peer. The case in which a peer downloads les from P2P le-sharing network of which it is member is trivial, thus is not shown in the gures for the sake of clarity.

Figure 4 . 4 :

 44 Figure 4.4: Inter-network download: the destination network is searchable

Figure 4 . 5 :

 45 Figure 4.5: Inter-network download: the destination network is non-searchable.

  Intermediary messages are dened by IFP protocol as following: Search request. Most of P2P le-sharing networks have search capability with keyword search. The search criteria can include le attributes. One exception is BitTorrent, the most widely used P2P le-sharing network, which does not have search capability. However, BitTorrent users can still search the torrent les from websites using keywords. Therefore, IFP denes the intermediary search request containing keywords and le attributes Search result. P2P le-sharing networks return the list of matched les for each search request. Hence, the intermediary search result contains the notication of no search capability in case of BitTorrent or the list of matched les along with attributes in other cases. Download request. The intermediary download request contains the torrent le in case the destination network is BitTorrent and the information of the expected le in other cases. Upload request. The intermediary upload request contains le attributes based on which the recipient FOGP decides to accept or not. The four intermediary messages are illustrated in Figure 4.6.

Figure 4

 4 Figure 4.6: Formats of intermediary messages

Chapter 4 .

 4 Backward Compatible Cooperation of Heterogeneous File-Sharing Networks JNode: a P2P node client, which implements: IFP, OGP, lightweight OGP protocols and three simple le-sharing networks based on three protocols namely Kademlia, Gnutella and BitTorrent respectively. It can be instantiated as OGP node, lightweight OGP node, Kademlia node, Gnutella node and Chord node. Every kind of node allows the users to search and receive les.

4. 4 . 5

 45 The cooperation eciency on percentage of FOGP In this investigation, each network contains 100 nodes including only blind peers and FOGP peers with the percentage of FOGP peer varies from 3% to 30%. The experimental parameters are given in Table 4.1, Scenario 1. The experimental results are illustrated in the Figure 4.7 in which the Rd and Ru values are represented by the blue line and the red line respectively.

Figure 4 . 7 :

 47 Figure 4.7: Cooperation eciency vs. percentage of FOGP

Figure 4 . 8 :

 48 Figure 4.8: Cooperation eciency vs. percentage of LOGP

5. 3

 3 unit as illustrated in Figure4.10 From Figure4.9 and Figure4.10, we can see that when the percentage of FOGP peer increase while the percentage of LOGP peers is xed, the load on each FOGP peer decreases because the load generated by LOGP peers over each FOGP peer decreases.On the other hand, when the percentage of FOGP peer decrease, the size of OGP overlay also decreases results in the routing cost of search messages over OGP overlay decreases. Therefore, when building a system of cooperating le-sharing networks, one need to tradeo between the load on each FOGP peer and the routing cost of the search messages over OGP overlay, i.e. choosing a suitable percentage of FOGP peers. This tradeo can be achieved by using Figure4.9 and Figure4.10.

Figure 4 Figure 4 .Figure 4 .

 444 Figure 4.9: Load on a FCFS peer

  P2P le-sharing networks which can apply to all current P2P le-sharing networks. The model constitutes the IFP protocol, laying on OGP routing framework, for bridging P2P le-sharing networks at application level. This model serves as a case study of the framework for backward compatible cooperation of P2P systems presented in Chapter 3.The evaluations show that having the percentage of FOGP peers not less than 5% with any percentage of LOGP peers is sucient for achieving high cooperation eciency in churn conditions: Rd and Ru are not less than 97% and 99% respectively as the lifetime mean of peer is set to one hour. This leaves us a great exibility when choosing the percentage of FOGP peers. Our model also leaves us the ability to tradeo between the load per FOGP peer and the routing cost over OGP overlay of search messages.The experiments also show the scalability of our model with the Rd and Ru values are slightly vary in the ranges from 97% to 99% and from 99% to 100% respectively when the size of each network increase 4 times from 50 nodes to 200 nodes. This chapter relies on following conference paper: 1. Giang Ngo Hoang, Luigi Liquori and Hung Nguyen Chan. Backward-Compatible Cooperation of Heterogeneous P2P Systems. The 15th International Conference on Distributed Computing and Networking, ICDCN 2014, accepted. Introduction Cyber-Physical Systems (CPS) are integrations of computation, networking, and physical processes in which embedded computers and networks monitor and control the physical processes, with feedback loops where physical processes aect computations and vice versa [CPS]. Applications of CPS can be found in various areas. Smart grid, autonomous automotive systems, medical monitoring, process control systems, distributed robotics are some examples of CPS.

  By current standards, a few kilobytes of data is collected from each smart meter every 15 minutes[Stand 2010[START_REF] Bernaudo | [END_REF]. In addition, metering data can be collected on demand for billing inquiries, outage extent verication, and verication of restoration[START_REF] Khan | [END_REF]. When the system is up to large scale, many existing communication architectures are not sucient enough to deal with the waves of meter data due to the limitation in bandwidth.In this chapter, we address above challenge by introducing a mix P2P and clientserver communication architecture that allows scalable data collection, aggregation and management. The proposed communication architecture comprises multiple points of data collection and processing, i.e. MDMSs, which are geographically distributed and hierarchically organized. The metering data is collected, then is aggregated and transferred through multiple levels of MDMSs in a tree manner thus reduce the throughput of data after each level. While MDMSs are organized in P2P architecture to take the selforganization, scalability and resilience advantages of P2P, the connection from MDMSs to smart meters follows the client-server model as normally in order to be compatible with existing collectors and smart meters. As such, the main contribution of this chapter is the introduction of a new communication architecture for AMI featured by characteristics including scalability, resilience and partly self-organization, i.e. MDMSs network is self-organized.Our chapter is organized as follows. Section 5.2 presents the background on AMI system. In Section 5.3, we introduce the related work and our focus. In Section 5.4, we describe the proposed AMI communication architecture and investigate the characteristics of the architecture. The communication infrastructure is evaluated by experiments on large scale platform Grid5000 [G5k] in Section 5.5. Finally, we draw conclusions and introduce the future work in the Section 5fully congured infrastructure to provide an essential link between the grid, consumers and their loads, and generation and storage resources [ami 2008].Figure 5.1 illustrates the general architecture of AMI system.

Figure 5 . 1 :

 51 Figure 5.1: Overview of AMI

Figure 5 .

 5 Figure 5.2 illustrates the proposed AMI communication architecture. The AMI comprises multiple OCs which are geographically distributed and hierarchically organized.

Figure 5 .

 5 Figure 5.2: AMI proposed architecture

Figure 5 . 3 :Figure 5 . 3 .

 5353 Figure 5.3: AMI proposed architecture

  The adding or removing MDMSs to or from MDMS overlays can be achieved easily thanks to the self-organization advantages of P2P. If the change of load happens in a local area, utility only need to adapt the number of MDMSs in the OCs which are responsible for that area.The easiness of changing the resource pool to adapt with either the global changes or the local changes of load shows the load scalability of AMI based on our architecture.

Figure 5 . 4 :

 54 Figure 5.4: Evaluation communication architecture

Figure 5 .Figure 5 . 5 :

 555 Figure 5.5 illustrates a simple example of ID assignment. The inter-connecting DHT structure includes three levels (see Figure 5.3) in which one level-1 MDMS connects toan overlay network of level-2 MDMSs. Each of the level-2 MDMS connects to an overlay network of level-3 MDMSs. For the sake of simplicity, in the example, the identiers of MDMSs are presented by only 4 bits numbers, i.e. p = 4, here we set q = 2.

Figure 5 .

 5 Figure 5.6 illustrates an example in which the parent MDMS overlay, i.e. O1, connects to three children MDMS overlays, namely O2, O3 and O4. In the gure, MDMSs are denoted by black circles. A, B and C are MDMSs in O1. C is successor of B which is successor of A. D, E and F are MDMSs in O2 and are children of A because ID D , ID E and ID F belong to [ID A , ID B ). Similarly, G, H and I are MDMSs in O3 and are children of C while K, M and N are MDMSs in O4 and are children of B.

Figure 5 . 6 : 5 . 4 .

 5654 Figure 5.6: Parent children example

5. 5 . 3 .Figure 5 . 7 :

 5357 Figure 5.7: Success ratio in downward-multicast.

  this chapter, we have introduced a new AMI communication architecture for scalable data collection and management. The architecture is mixing of P2P and client-server model in which the MDMSs are geographically distributed and hierarchically organized in a P2P manner. The MDMSs at highest level play the roles of server managing data concentrators. The analysis shows that the AMI based on our communication architecture is scalable for data collection and management while being resilient with failure and allow reducing the operation cost. Utility can also plan the geographic distribution of MDMSs to have expected latency of collecting data. Smart Grid applications can be deployed in OCs at dierent levels depending on their characteristics and requirements on latency. The experiments shows the eciency of communication schemes in the proposed architecture in term of ratio of successful communication in both high churn and no churn environments. The communication is performed with at least 97% of success under the high churn and with 100% of success in no churn condition. The experiments also show that the children peers generate low maintenance trac, i.e. 1.1 times larger than a Chord peer in the same size network. The scalability of the communication architecture is shown in both aspects: communication eciency and maintenance trac. This chapter relies on following work: 1. Giang Ngo Hoang, Luigi Liquori and Hung Nguyen Chan. A Scalable Communication Architecture for Advanced Metering Infrastructure, Technical Report. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.2 Further Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

  areas and require scalable communication architectures for dealing with the intensive data generated by their sensors and actuators.Examples of these systems include autonomous automotive systems, medical monitoring, sensor-based communicationenabled autonomous, process control systems and distributed robotics. The interconnecting overlays architecture with the features such as scalability, failure resilience, self-organization, allowing locality and heterogeneity can address mentioned challenge in cyber-physical systems.

  Application of the inter-connecting P2P overlays in Cyber-Physical Systems (CPS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

		Introduction
	Contents
	1.1	Motivations and research directions . . . . . . . . . . . . . . . . .	1
		1.1.1 Cooperation of heterogeneous P2P systems . . . . . . . . . . . . .	1
		1.1.2

1.2 Thesis structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

  Background on P2P . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 P2P denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.2 History of P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.3 P2P systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.4 P2P overlays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.5 P2P applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

	Chapter 2
	Background and State of the art
	Contents
	2.1
	817-822, 2011.

Ngo Hoang, Luigi Liquori and Hung Nguyen Chan. Backward-Compatible Cooperation of Heterogeneous P2P Systems. The 15th International Conference on Distributed Computing and Networking (ICDCN) 2014, accepted. 2. Giang Ngo Hoang, Luigi Liquori, Vincenzo Ciancaglini, Petar Maksimovic and Hung Nguyen Chan. A backward-compatible protocol for inter-routing over heterogeneous overlay networks, in Proceeding of the 28th Annual ACM Symposium on Applied Computing (SAC), pp. 649-651, 2013. 3. Giang Ngo Hoang, Luigi Liquori and Hung Nguyen Chan. A Scalable Communication Architecture for Advanced Metering Infrastructure. Technical Report. 4. Vincenzo Ciancaglini, Luigi Liquori, Giang Ngo Hoang and Petar Maksimovic. An Extension and Cooperation Mechanism for Heterogeneous Overlay Networks, in Proceeding of the HetNETS Workshop, NETWORKING conference, pp. 10-18, 2012. 5. Vincenzo Ciancaglini, Luigi Liquori, Giang Ngo Hoang. Towards a Common Architecture to Interconnect Heterogeneous Overlay Networks, in Proceeding of the 17th International Conference on Parallel and Distributed Systems (ICPADS), pp.

2.2 State of the art on cooperation of P2P systems . . . . . . . . . . 18 2.2.1 Classication of cooperation . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 Inter-system content sharing . . . . . . . . . . . . . . . . . . . . . 19 2.2.3 Merging overlays . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.4 Inter-system trac engineering . . . . . . . . . . . . . . . . . . . . 21

  Kademlia employs iterative and concurrent lookup algorithm. To lookup an ID, the lookup initiator picks α random nodes from the non-empty kbucket which is closest to the ID or α closest nodes it knows of in case that bucket has fewer α nodes. The initiator then sends in parallel query to these α nodes that each of which possibly returns k closest nodes to the ID it knows of. Upon receiving the results, of the k nodes closest to the ID, the initiator resends the lookup message to α nodes has not yet queried. If a round of sending lookup messages fails to return a node which is closer than the closest already seen, the

initiator resends the lookup messages to all of k closest nodes which has not yet queried. The lookup process terminates when k closest nodes it has seen have been queried and have returned the responses. With the prex matching scheme, Kademlia resolves a lookup in O(log(N)) hops.

Join, leave and maintenance. To join the network, a new node connects to a preexisting node and then lookups IDs in dierent subtrees. The learnt nodes in the lookup processes are used to ll its routing table.

To deal with the leave of nodes, Kademlia uses a replacement cache of nodes eligible for replacing failed nodes in the k-bucket. When a node learns a new node and if the perspective k-bucket is full, the new node is inserted into the replacement cache. When a node in a k-bucket is not responsive, it is evicted and replaced by node in the replacement cache which is kept sorted by last time seen with the most recently seen node has highest priority for replacement candidate.

Kademlia uses lookup trac for maintaining the topology which minimizes the maintenance cost. Because the XOR distance dened by Kademlia is symmetric, a Kademlia node can use new learnt nodes from lookups for updating its routing table.

  Uponreceiving the message, G converts the message in accordance with the native protocol of O3, and forwards it to H via its Native node. The return path takes us back through G to F, following the native protocol of O3 rst, and then the OGP protocol. identies each standard overlay by a unique n-bit number we denote by netID. A FOGP peer is assigned an unique (n + m)-bit identier, denoted by ID, consisting of two parts: the n-bit identier of the standard overlay to which that peer belongs (netID), and a random m-bit number denoted by nodeID. Given this, and using | as a concatenation operator, we have that:

	3.3	Framework description
	3.3.1 OGP protocol
	3.3.1.1 ID assignment

OGP

Table 3

 3

	.2.
	Experimental parameters	Scenario 1	Scenario 2
	% of FOGP peers	6, 10, 20, 30, 40	10, 20
	% of LOGP peers	0	10, 20, 40, 60
	Lifetime mean (second)	900, 1800	1800
	No. of overlays	20
	No. of nodes per overlay	50
	Type of overlays	Chord, Kademlia, Gnutella
	Table 3.2: Values of experimental parameters.

  Delivery of the search, download, upload request to P2P le-sharing networks of which the node is not member and receiving the results via the OGP node.

		4.2. System Overview Chapter 4. Backward Compatible Cooperation of Heterogeneous File-Sharing Networks	53
		Blind peers are peers that belong to only one P2P le sharing network, are not aware of the existence of additional protocols, and use only the protocols native to their network. 2. 3. Communication and exchanging les with other FOGP, LOGP peers.
		FOGP peers , simultaneously belong to one P2P le sharing network and the OGP 4. Dening the intermediary formats of messages and data and introducing the
		overlay. They run following protocols: the native protocols of their P2P le sharing transcoding of messages and data between formats of P2P le-sharing net-
		networks, the OGP protocol of the OGP overlay and the IFP protocol for coor-works and intermediary formats.
		dinating the parts in the peer and exchanging data between dierent le-sharing
		networks.
		LOGP peers , belong only to one P2P le sharing system, do not participate in the A LOGP peer
		OGP overlay, but keep a list of OGP peers. They run following protocols: the na-Cooperation Application tive protocol of the P2P le sharing networks they belong to, and the lightweight OGP protocol for communicating with OGP peers and the IFP protocol for ex-(running IFP protocol)
		changing data between dierent le-sharing networks. Native LOGP
		4.2.2 Structures of FOGP peers and LOGP peers req/res req/res
		Native Structures of a FOGP peer is shown in the Figure 4.1 LOGP node node
		A FOGP peer
		Cooperation Application
		(running IFP protocol)
		Native	OGP
		req/res	req/res
	model, peers running OGP protocol or LOGP protocol, also run a protocol, named Native OGP Inter-network File-sharing Protocol (IFP) which is designed for bridging dierent P2P le-sharing networks at application level and coordinating dierent components in a node node
	peer. The bridging between dierent networks is enabled by transcoding of necessary
	messages in these networks to common messages dened by IFP. The peers running OGP
	protocol form a super-overlay (the OGP overlay) serving as the routing infrastructure for Figure 4.1: Structure of a FOGP peer
	communication between heterogeneous P2P le-sharing networks. The peers, running
	FOGP and LOGP protocols, in dierent P2P le-sharing network employs this routing A FOGP peer has several components:
	infrastructure for communicating with each other.
	The rest of this chapter is structured as follows: in Section 4.2 we briey introduce Native node is the peer of P2P le-sharing network that the FOGP belongs to. The
	the model for cooperation P2P le-sharing networks. Section 4.3 describes the IFP Native node launches the requests on this P2P le-sharing network and returns the
	protocol while the evaluation of the model is introduced in Section 4.4. The related results to the Cooperation application which runs IFP protocol. The requests can
	work is introduced in Section 4.5. Finally, in Section 4.6, we present our conclusions and be search request, download request or upload request while results can be search
	outline future work. result, or downloaded le, etc.
		OGP Node participates in the OGP overlay and provides unicast, multicast and broad-
	4.2	System Overview cast routing cross P2P le-sharing networks for the FOGP node.
	4.2.1 Peer classication

The classication of peers in the le-sharing cooperation model is an instance of the one in OGP framework and is as following:

Cooperation application runs IFP protocol and performs following tasks:

1. Launching the search, download, upload processes on P2P le-sharing network of which the peer is member and receiving the results via the Native node.

  In the two gures, the green lines illustrate the communication following OGP protocol while the blue lines represent the communication following the standard protocol of P2P le-sharing network which is denoted by Standard network. The communication performed by IFP protocol is illustrated by red lines. The case in which a peer uploads its le to the P2P le-sharing network of which the peer is member is trivial, thus is not shown in the gures for the sake of clarity.

	4.2. System Overview				55
	Initiator	Recipient (FOGP peer)	Standard network	Initiator	Recipient (FOGP peer)	Trackers
					<register >
		<info delivery>
		OGP protocol		Upload torrent file to websites
		IFP protocol		Standard protocol
	(a) Destination network is searchable	(b) Destination network is non-searchable

  Chapter 5. A Scalable Communication Architecture for Advanced Metering Infrastructure in SmartGrid According to [ami 2008], Advanced Metering Infrastructure (AMI) is a fundamental early step to grid modernization, i.e. Smart Grid. AMI is an integration of many tech-

Table 5

 5

	.1.

Table 5 .

 5 1: Values of experiment parameters5.5.2.3 SoftwareThe software for evaluating the AMI communication architecture constitute twofold:

Online at http://www.aeic.org/meterservice/

Acknowledgments

Metrics

We characterize the cooperation eciency of P2P le-sharing networks by two metrics:

Rd and Ru. Here, Rd is the ratio of successful inter-network download operation. The Rd value shows the probability of the user successfully download a le which does not exist in user's network but exist in other networks. The second metric, Ru, is the ratio of successful upload operations. The Ru value shows the probability of the user successfully upload its le to networks which it is not a member.

In the cooperation model, FOGP peers in one network play the roles of gateways for other FOGP peers in that network and LOGP peers to exchange les with peers in other networks. We dene some more metrics as following:

• The load on a FOGP peer is the number of les transferring through that peer on a period of time.

• The routing cost of search messages, i.e. the number of hops, on OGP overlay.

• The setting of a cooperating system is the percentage of FOGP peers and the percentage of LOGP peers in each network of that system.

Objectives and methodology

The evaluation section has three objectives. First is to identify the settings of evaluated systems which ensure the cooperation eciency. Second objective is to investigate the While the second objective is achieved by analyzing the routing cost of search messages and the load over FOGP peers, the third objective is obtained by investigate the cooperation eciency under the increase of networks' sizes.

Setup

In this chapter, we evaluate the cooperation of three typical kinds of P2P le-sharing networks: (i) the network without search capability, (ii) the network with the ooding search and (iii) the network with DHT search. To achieve this, a complete system including implementations of three le-sharing networks based on BitTorrent, i.e. no search capability, Gnutella, i.e. ooding search and Kademlia, i.e. DHT search, are deployed on the French Grid5000 platform [G5k], which aims at providing a nation-wide test bed to study large scale parallel or distributed systems.

In each le-sharing network, a subset of peers is FOGP peers, another subset are LOGP peers and the rest are blind peers. Files that each of which is unique are randomly distributed across all of the networks. The FOGP and LOGP peers periodically perform two operations. First is downloading random les on any of the networks the peers don't belong to. Second is uploading their les to random networks they don't belong to.

All experiments are performed in high churn rate condition with the churn follows the Pareto distribution and the lifetime mean of nodes is set to 3600 seconds. owing to the OC and the power processing needed to process these messages.

• β n : the number of messages that a MDMS at level n + 1 sent to its parent MDMS at level n in a period of time;

In case n=L, we let z L be the number of messages a data concentrator sent to MDMS managing it over the number of messages that it receives from smart meters.

• K n : the number of MDMSs in all OCs at level n;

We note that z n << 1 because MDMS only sent summary data to its parent. This results in K n << K n-1 .

Load scalability. According to [Scala], load scalability is the ability for a distributed system to easily expand and contract its resource pool to accommodate heavier or lighter loads or number of inputs. We dene the load on AMI is the number of messages generated by all smart meters in one period of time which is calculated as following:

with λ is the average trac generated by a smart meter in a period of time. Thus the number of messages received by operation centers at level-n is:

We note that in centralized model, the load on the central MDMS, denoted by α is:

From Formula 5.1 and Formula 5.2, we can see following points:

• By distributing the MDMSs and aggregating data at multiple levels, our model reduces the load on each OC comparing to the centralized model.

Upward communication is the communication from a MDMS to its parent MDMS.

A MDMS use upward-unicast to send information to its parent MDMS. For example, in the Figure 5.6, MDMSs K, M and N can send information to B which is their parent MDMS.

Combination scheme. The combination between intra-overlay communication and downward communication allows the utility to unicast, multicast or broadcast information, i.e. data or command, to a specic MDMS, a group of MDMSs or to all MDMSs in any area.

The idea of combination scheme is as following. The sending MDMS rst employs intra-unicast or intra-multicast or intra-broadcast to send the information to a specic MDMS or to a group of MDMSs or to all MDMSs in the same overlay with it. The receiving MDMS then forwards the information to one of its children or to group of its children or to all of its children.

The combination scheme constitutes three kind of communication as following:

• Combination-unicast: used by a MDMS at level-n to send information of a specic MDMS at level-(n + 1). For example, in the Figure 5.6, MDMS A can send information to a specic MDMS belonging to any of three overlays: O2, O3 and O4.

• Combination-multicast: used by a MDMS at level-n to send information of a group of MDMS at level-(n + 1). For example, in the Figure 5.6, MDMS A can send information to a group of MDMSs belonging to any of three overlays: O2, O3 and O4.

• Combination-multicast: used by a MDMS at level-n to send information of all MDMSs at level-(n + 1). For example, in the Figure 5.6, MDMS A can send information to all of the MDMSs in three overlays: O2, O3 and O4. The intra-overlay communication was evaluated in many previous studies such as [START_REF] Stoic | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], El-Ans et al 2003]. Therefore we focus on evaluating the eciency of combination scheme and upward communication including: combination-unicast, combination-multicast and upward-unicast.

In this work, the scalability of the communication architecture is evaluated through the change of communication eciency and the change of communication cost, i.e. generated trac, as the scale of the system increase. In the experiments, the scale of the On the other hand, the slightly changes or even no changes in ratio of successful communication in evaluated communication schemes (see Table 5.2) as the scale of the system increase 4 times, i.e. the number of parent MDMSs increase from 10 to 40 while the number of children MDMS increase from 500 to 2000, shows the scalability of the communication architecture.

Experiment results: Maintenance trac and Scalability

In this work, we extend Chord DHT to implement MDMS overlays. Therefore, in this section, we evaluate the maintenance trac of the proposed architecture by comparing the trac generated by a parent peer and a children peer with the trac generated by a Chord peer in the same condition. In the Figure 5.9, the two lines parent vs. chord and child vs. chord show the ratio of the trac generated by a parent peer and a child peer respectively over the trac generated a Chord peer in the same size network in churn condition. From the Figure 5.9, we can see that the line child vs. chord is horizontal at the value of 1.1. The line parent vs. chord is slightly decreases from 2.8 to 2.3 as the number of children overlay increase from 10 to 40. The standard deviations are approximately 0 in all cases.