Keywords

1 Introduction

1.1 Motivation

A P2P system is defined as a group of organized autonomous peers in which peers share distributed resources (files, computing and services) without any centralized coordinating entity. Chord [14] has long emerged as an efficient structured P2P architecture and system. With the growing interest in P2P networks, combined with the emergence of new computing paradigms such as Big Data and the Internet of things (IoT), a hierarchical design is desired to overcome disadvantages associated with pure P2P networks. These disadvantages include the challenge of managing a network when the number of nodes increases exponentially and thus deteriorates the performance of the entire network, as well the challenge of handling the exponential increase in the number of things in a IoT environment. More specifically, consider an IoT fleet management scenario where a large number of vehicles must be managed. The involved vehicles can be considered as the leaf nodes of a tree-like structure that is formed by Chord ring of further Chord rings and be organized around local rings with super-peers that can function as the points at which data can be merged on the local ring and then be passed to a hierarchically higher ring. The hierarchical model reduces the network traffic, decreases the workload and the lookup path length because the number of hops is significantly reduced in addition to the lookup latency. The goal of trust and reputation systems is to evaluate the trustworthiness of peers, provide value to any transaction made among peers, and distinguish good peers from bad peers based on previous interactions and feedbacks from peer transactions. So far, there has been no a serious investigation or study undertaken to implement trust and reputation in hierarchically structured P2P networks. Specifically, this paper proposes a hierarchical redesign of Chord as an efficient solution for managing the complexity of P2P networks amenable for IoT applications and a hierarchical EigenTrust, an extension of EigenTrust.

1.2 Problems

We are confronted to the problem of adequately structuring P2P networks in the presence of a gigantic number of peers. Henceforth there is a need to redesign trust and reputation algorithms that were designed in the context of flat structured P2P network to make those algorithms amenable for the hierarchically structured P2P network context. Due to its popularity in the last ten years, we have considered Chord rings as the existing P2P network to further restructure in order to master the complexity of gigantic P2P networks. We will focus on the design, analysis, and implementation (via simulation) of a trust and reputation algorithm for hierarchically structured Chord systems. Our choice was based EigenTrust because it is one of the earlier and mostly cited trust and reputation algorithms for structured P2P, also many recent algorithms are just trying to improve EigenTrust.

2 Related Work

Many structured P2P systems like Chord, CAN [11], Pastry [12] are P2P overlay networks that implement a key-based and deterministic algorithm for the routing of messages to the destination key that holds the searched content. These overlay networks support storage and search interfaces such as Distributed Hash tables (DHT), a lookup strategy to route and specify the location of objects in the P2P network. This allows them to perform lookup service in O(log N). In NodeRanking [10] the reputation value of a node i is evaluated by the number of references (emails, personal web pages) provided by other nodes in the network. PowerTrust [16] carefully and dynamically chooses a small number of power peers with hight reputation value. PowerTrust ameliorates global reputation accuracy as well as the rate of aggregation speed. Absolute Trust [1] is a algorithm for aggregation trust in P2P networks for peers that only exchange files. The algorithm and the metric used determine the true past behavior of peers. This algorithm does not need a normalization of trust, pre-trusted peers or any centralized authority.

3 Hierarchically Structured Chord

3.1 Chord

Chord organizes all peers in a ring (or circle) that maintains all keys in the range from \(2^{m}-1\). It maps keys with corresponding content nodes. Each node maintains a routing table called finger table that maintains the successors, predecessors and fingers of the node. Every finger table contains up to m entries, m being the number of bits in the hash key. Each node only possesses knowledge of its successors on the identifier circle in order to execute look up operations and knows little about distant nodes. Thus, each node can only maintain information for a small number of nodes, i.e. a total of O(log N) fingers [8]. In the finger table of a node n, the identifier of the first node s (at \(i^{th}\) entry) that comes after n is determined by \({s}={successor}({n}+ 2^{i-1})\). Node s is what is called the finger of n. When a query is sent to a node, the node first needs to inspect its own local storage to ensure if it carries the desired data item. If it holds the desired data item, it simply sends the result to the requester. Otherwise, it redirects the query to its nearest successor node according to its finger table.

Fig. 1.
figure 1

Hierarchical Chord model

Full size image

3.2 Extending Chord to a Hierarchical Structure

Each group in Figure 1 has a unique designated group id. The directed graph U, X, with X = \({\{g_{1},\ldots ,g_{I}\}}\) = Set of all groups and U = set of virtual edges among nodes (groups in this case). Each group contains at least one superpeer [3]. The lookup service is performed in two steps; first it locates the group that is in charge of the key, and inside the group it locates the peer that is in charge of the key. For N-tiers DHT, the lookup service should go deeper in the hierarchy, by passing through groups until it reaches the group that is in charge of the key. For two-tier DHT, operations are executed in the following orders: A superpeer of group \(S_{j}\) of superpeers of group j receives the query and can then transfer it to the peer \(p_{j}\) belonging to group \(G_{j}\) that is in charge of the key k. When \(p_{j}\) responds back to the query, the response can be transmitted using the reverse path used by the query message, or can be transmitted directly from peer j to the peer i. The lookup system at the top-level administers an overlay of groups. When a new peer p joins a group, it is provided with the id of the group to be recognized, such as the name of the group. Then p contacts a node p’ already participating in the group to request the IP address of the group’s superpeer(s)for the group key g.

4 EigenTrust for Hierarchical Chord

4.1 EigenTrust

EigenTrust [7] is a distributed trust reputation system based on individual reputation and uses distributed control. A peer conserves a record of all previous transactions in a local trust vector \(\overrightarrow{c_{i}}\). Vector \(\overrightarrow{c_{i}}\) consists of all local trust values \(c_{ij}\) that peer i has attributed to other peers j. It can be represented as \(\overrightarrow{c_{i}}= (c_{i1}, c_{i2},c_{i3},\ldots ,c_{in})\). All \(c_{ij}\) are positives because there are normalized as \( c_{ij} = \dfrac{max(s_{ij},0)}{\sum (s_{ij},0)}\), and the sum of \((c_{i1}+ c_{i2}+c_{i3}+\ldots +c_{in}) = 1 \). All local trust values are represented in a matrix \([(c_{ij})]\) defined by C. A gossiping algorithm is used to assemble the global reputation \(t_{i}\) of the P2P network. The global trust value \(t_{i}\) determines the trust that the entire system places in the peer i. \(\overrightarrow{t}\) determines the global trust vector of the entire system. EigenTrust evaluates the left principal eigenvector of a matrix of normalized local trust values, so that it can calculate the global trust value of a peer. It computes local reputation and global reputation and it uses transitivity to measure trust. This system needs a group of honest peers, pre-trusted peers \(\overrightarrow{P}\) as start vectors to eliminate malicious peers.

4.2 Extending EigenTrust to Hierarchical Chord

Algorithm 1 represents the extended secure EigenTrust to hierarchical Chord. In this algorithm, some important information about group \(G_{j}\), \(RRM_{j}\) and pre-trusted peers (superpeers) \(P_{j}\) is added to improve the lookup process in the hierarchical structure [5]. Thus, at each level, pre-trusted peers are assumed to be involved in the computation of trust and reputation. The algorithm computes the local trust of peers by using score managers of each peer to keep the score, and then aggregating all trust scores of a peer to determine its global reputation in the network. Because this algorithm works in a hierarchical environment, transactions made outside a home ring, are used to bring the scores of all peers from other home rings to local ring in order to compute the global reputation of a local peer.

figure a

The number of local trust values reported by a peer i is limited because a network may have a huge number of peers. The algorithm adds a variable \({Rpeer_{j}}\) to limit the number of remote peers that can send scores of a peer i located in a local ring. This algorithm allows a peer to have its score managers only locally to optimize the algorithm and to reduce traffic in the network. Peers outside of a local ring can report scores of peers in another ring to their superpeers, which will then transfer scores to score managers of peers into their corresponding HR’s. We also assume that a group can only interact with a limited number of other groups. The number of hops from one ring to another rings for lookup purpose is determined and limited by the variable \(hops_{j}\). Small rings (home rings) will execute the algorithm faster than one large flat ring; this allows the algorithm to converge faster. To compute the complexity of the algorithm, we need to take into account the local and remote computation of node scores. Essentially, local computation involves many peers than the remote computation due to restriction of the number of hops and remote peers that can send feedback for a peer in a local HR. Also, the system allows the use of cache to keep results of queries. When the algorithm is run for the first time, it determines pre-trusted peers, the number of hops it is permitted to use while sending a query out-site of a local ring. The algorithm is executed in \(O(n^2)\). The idea in a hierarchical structure is to keep queries in the local ring. Finally, we assume that in the computation of the reputation of a node i, the number of HR’s from which peers will send feedback after having performed transactions with node i must be limited to increase the performance of the algorithm, and the number of remote peers from other HR’s to a local ring is limited to improve the performance of the algorithm.

5 Simulating Hierarchical Chord

In these experiments, we evaluate the performance of the redesigned EigenTrust in an hierarchical structured P2P network using Chord lookup service. We use existing experiment of flat EigenTrust and extend it to a hierarchical structured P2P. We also consider that a main ring is composed of superpeers that connect other nodes to form a ring, and that an m-bit identifier is attributed to each peer and each key. The model we use is based on a cloud service provider (CSP) that is made up of many data centre disseminated around the globe. Thus, each continent can be connected to the super ring by using a Superpeer called “remote resource manager (RRM)”, a superpeer that connects two consecutive rings. We assume that when a flat network has 100 nodes, the entire hierarchical network will have 100 nodes. Then, we increase the number of nodes to 500, 1000 and 5000 respectively in both networks, and compare results. For the sake of clarity and fair comparison, we assume that both flat and hierarchical networks have the same number of nodes and that all rings in the hierarchical network have the same number of nodes. In the Hierarchical Chord simulation, we compare the fraction of download, the convergence speed and malicious collective for both flat and hierarchical EigenTrust. To capture the heterogeneity of the peers, we suppose that there are two categories of peers: Stable peers (for node 1 to node 10); Unstable peers for the other nodes. For the hierarchical organization, we select super-peers from a set of stable peers and we suppose that there is at least one stable peer in each group. For the organization, we choose nodes from the two categories randomly. Convergence is another aspect of concern since nonlinearity may result in a large number of iterations and render the system inefficient. We choose to have the same fraction of malicious peers in both hierarchical and at Chord, in order to readily compare the fraction of download from peers.

6 Simulation Results

6.1 Setup

we used an open-source simulator called PeerfactSim [13]. PeerfactSim does not currently support hierarchical Chord. One of the tasks was to modify the source code with an implementation of the flat Chord P2P system structure and extend it to hierarchical Chord. A user can specify the length of the tree and the number of nodes.

Fig. 2.
figure 2

Results of Fraction of downloads in Flat and Hierarchical EigenTrust for 100 nodes

Full size image

We use a standalone computer with Intel(R) Core(TM) i5-3320M CPU @2.60 GHz, 64 bits, using 8.00 GB. For coding we use Eclipse IDE for Java Developers, Version: Mars.1 Release(4.5.1) and jdk1.8.0_91. The Windows 7 Professional operating system was used. For the experiments, we want to compare simulation results from a flat chord P2P system(with only one ring) to that of a hierarchical Chord P2P system. Then We compare and analyze experimental results.

6.2 Results

Figure 2 represents the load distribution results of the simulation when the network has 100 nodes. We can see that load distribution for the Hierarchical Chord network is concentrated on nodes with higher stability in each level of the hierarchy. Conversely, in the flat EigenTrust network, load distribution is selecting data sources with more scattered patterns. We increase the number of nodes to 500 and 1000, to simulate malicious collectives in both algorithms. For 100 and 500 nodes, malicious peers represents 43% of nodes, while for 1000 nodes the number of malicious nodes represents 50% of the all nodes in the network. We limit the number of nodes to 16 in each ring. Figure 3 shows that, with more nodes, we can see that the percentage of inauthentic downloads increases very slightly compared to 100 nodes for EigenTrust. This proves that the hierarchical EigenTrust improved significantly in the hierarchical network. The hierarchical EigenTrust presents better performance that the flat EigenTrust, even when the percentage of malicious peers constitutes the half of the total number of peers in the network. EigenTrust downloads more files from malicious peers than hierarchical EigenTrust.

Fig. 3.
figure 3

Trust-based reduction of inauthentic downloads in hierarchical network with 100, 500 and 1000 nodes where a fraction of peers forms a malicious collective

Full size image

Figure 4 represents the convergence speed of both algorithms for 100, 500, 1000 nodes. Results show that even hierarchical network has many rings, the convergence speed is close to that of flat network. With 1000 nodes, we can see that the flat EigenTrust converges after at most 5 iterations, while the hierarchical EigenTrust converges at most 6 iterations in the network with many rings. Even when the number of nodes changes, the converge still close.

Fig. 4.
figure 4

Convergence speed of algorithms in hierarchical network

Full size image

7 Conclusion

We have redesigned the EigenTrust trust and reputation algorithm that was designed for flat-structured P2P networks to be used in hierarchically structured P2P networks. We chose Chord to this end and we extended its DHT mechanism to a hierarchical structure where peers are assembled in groups recognized by a unique identifier. We simulated the new algorithm as well as the old algorithm, and we evaluated them in terms of load distribution, residual curl, and malicious collective downloads. We compared the measures obtained for both EigenTrust and its hierarchical version. The results revealed that the hierarchical trust and reputation algorithm achieved better performance than the flat algorithm and converged faster and proportionally to the number of rings. We can therefore conclude that the reduced number of nodes per ring and their organization in hierarchies helped to improve the performance of the Chord P2P system. In the future, as our simulation have been performed on a hierarchically structured Chord P2P network limited to a three levels, we intend to extend our results to a Chord structure with an arbitrary number of levels. Furthermore, we will look into how to extend this research to other trust and reputation systems found in the literature and which were designed around different trust and reputation models such as PowerTrust [16], NodeRanking [10] or Absolute trust [1]. The results of simulations using our simulator will then be compared to determine which algorithm outperformed all others in a hierarchical network environment. We can also apply this research to IoT settings, such as the fleet management setting used in the introduction to this paper as motivation, by building an IoT fleet management network where nodes are hierarchically organized. Further future work can be focused on the extension of EigenTrust to lookup services based on other existing hierarchical overlay structures such as BATON [6], and HD Trees [4].