Pancake graphs for lookup acceleration and optimization in P2P networks

Abstract

Lookup services is still a key challenge in all distributed systems and particularly for P2P based services (e.g. distributed SDN node controllers, social networking…). In these networks, node searching for a specific service or resource has to discover the “best” path to the node offering the requested resource or service. Since P2P networking is implemented at application layer, the given optimized path from a source node to a destination one, in terms of number of hops is not necessarily the best path in terms of physical parameters (e.g. delay, physical proximity). For this, the lookup process optimization is still a real challenge in some environments, particularly for delay sensitive services. In this context, various topologies have been proposed in the literature such as: ring, tore, star, hypercub, De Bruijn graph, and skip graph.

In this paper, we propose a new approach using Pancake graphs, for structuring the P2P topology in order to optimize the lookup process. The proposed solution is compared to some main existing solutions. Under certain conditions, the simulation results show better performance compared to existing approaches.

Keywords

P2P Pancake graphs routing optimization

1. Introduction

The rapid evolution of networks (e.g. Cloud, SDN, NFV) combined with the exponential growth of users and terminals, require new network models, structures and topologies for better performances. For example, there is a need to provide a distributed architecture for the controller node in SDN networks (Software-Defined Networking), or for building a P2P distributed based SDN architecture, or for self configuration and organisation [29]. In this context, P2P model still represents an attractive research topic for performance optimization. The topology selection cost should also be taken into consideration. The existing shareable resources searching methods, have at least one of the following limitations: (1) they are applicable only to certain topology patterns, (2) single point of failure problem, or (3) generate a significant cost for maintenance [22].

The most important executed function or process in P2P systems is the routing and lookup function. Given this, the optimization of such function is still a challenge, particularly for delay sensitive applications or services [9] but also in critical environments such as P2P SDN/NFV, P2P sensor networks (Wireless body sensor networks) [7], P2P VoD [23] or Streaming [21]. In this context, new models have been proposed, each one presents some benefits but also some limitations, such as: bus topology, full mesh topology, ring topology, hypercub topology, a multi-agent-based content-sharing topology [32] … Even if some existing P2P models (e.g. Pastry) include some physical information (e.g. physical proximity) in their routing tables, they do not really exploit these information. Continuously, other types of topology are also proposed such as De Bruijn [12], Star [2], Pancake graphs and semantic search [18]. Pancake graphs is the focus of this paper.

The rest of the paper is organized as follows: Section 2 gives a background and related works regarding the Pancake graphs. In Section 3, we introduce our proposed solution for routing optimization and lookup acceleration in P2P networking using Pancake graphs. Section 4 presents some performance results regarding the proposed solution. Finally, in Section 5 we conclude this work and share ideas for future work.

2. Background and related works

Pancake graphs are proposed by Akers et Kirshnamurthy as an alternative to hypercube for processors interconnection in parallel computing [24]. Like other graphs, it is composed of nodes and edges. A group of nodes is clustered into a Pancake graph, and is assigned an identifier. This graph has the following properties: symmetric, recursive and not oriented. A Pancake graph is essentially based on the concept of symbols permutation. The graph and symbols represent the identifiers space for the peers [1].

Each peer of a Pancake graph is part of a separate Pancake group of nodes. The peer has connections with other peers of the same node, and peers of neighbouring nodes. In the case where peers join or leave the network, some of them can connect to other nodes, to keep some parameters constants (e.g. number of peers per node for a uniform nodes distribution). All nodes are connected to the same number of peers at any time. If the total number of peers increases or decreases respectively above or below a certain threshold, the order of the Pancake graph increases or decreases by one [25]. This, provides relevant and important properties to the Pancake graph.

In this section, we illustrate the main benefits of Pancake graphs and their importance in many research domains. The Pancake graph is directly related to discrete optimization problem. The ordered lists can be used to create networks of Pancakes in which a graph is created by representing each vertex list as distinct and connecting only two vertices, if it can obtain one from another using prefix permutation. The example illustrated on Fig. 1 shows how to sort an array using the well known permutations of Pancake graphs.

Fig. 1.

Array sorting using permutations in Pancake graphs.

2.1. Applications of Pancake graphs

Computer architectures has completely changed, from a simple refined processor to a parallel structure using many parties with relatively less capability requirements. In a parallel architecture, if the problem can be divided into parts and be executed separately and independently, results are obtained more rapidly compared to a single processor architecture. However, these processors must be interconnected, in order to share information as needed. For this purpose, there are different ways to connect these processors such as the Pancake structure [27].

Recent studies in the identification of genomes have highlighted issues in molecular biology very similar to the problem of Pancakes. Differences in genomes are usually explained by differences accumulated in the genetic material due to random mutations. In the 80s, another mechanism of evolution has been discovered. The gene sequences are identical in some plants, but differ only in the order. This has inspired some biologists to watch the mechanism that could confuse the order of genetic material. The only solution is to make the permutations in the Pancake graphs. The best known example in biology is the two plants Cabbage and Turnip which have the same elements but differ only in the placement order, one of them is obtained from the other one by doing permutations of Pancakes [27].

Let be $u = u_{1} u_{2} \dots u_{n}$ a permutation of n symbols from 1 to n. For each i ( $1 ⩽ i ⩽ n$ ), an operation $u (i)$ is defined as follows: $u (i) = u_{i} u_{i - 1} \dots u_{1} u_{i + 1} u_{i + 2} \dots u_{n}$ [28].

An undirected graph $G = (V, E)$ is called n-Pancake graph $P_{n}$ , if: $V = {u_{1} u_{2} \dots u_{n} | u_{1} u_{2} \dots u_{n} is a permutation of 1, 2, \dots, n}$ and $E = {(u, v) | u, v \in V, u = u^{(i)}, 2 ⩽ i ⩽ n}$ [28].

In a Pancake graph $P_{k}$ , a peer v is connected to a peer u if and only if the identifier of u can be obtained from v by inverting the i first symbols $(2 ⩽ i ⩽ k)$ . For example, in the graph P4 of Fig. 2, the peers 2134, 3214 and 4321 are obtained from the peer 1234 by reversing the two, three and four first symbols respectively. Figure 2 shows a Pancake graphs P2, P3 and P4 with orders 2, 3 and 4 respectively.

Fig. 2.

Pancake graphs: P2, P3 and P4.

Table 1

Pancake graph vs other topologies

	Number of nodes	Degree	Diameter
$P_{n}$	$n!$	$n - 1$	$⩽ 5 (n + 1) / 3$
$Q_{n}$	$2^{n}$	n	n
$T_{n}$	$n^{2}$	4	n
$S_{n}$	$n!$	$n - 1$	$3 / 2 (n - 1)$
$(B_{n}, k)$	$n^{k}$	$2 n$	k

In a n-Pancakes graph, a sub-graph is derived from the peers that have a common symbol k in the last position of their addresses. This sub graph constitutes a $(n - 1)$ -Pancakes graph. This sub-graph is specified by $P_{n - 1} k$ using the common symbol k as an index [16] (e.g. $P_{3} 1$ in Fig. 2 ). The number of peers, the degree, the number of edges and the graph connectivity of $P_{n}$ are respectively: $n, n - 1, (n - 1) * n! / 2$ and $(n - 1)$ [16].

2.2. Comparison with other topologies

Table 1 shows a comparison between the Pancake graph $P_{n}$ [5,17] with other well know topologies such as hypercub $Q_{n}$ [11], the Tore $T_{n}$ [10], the Star graph $S_{n}$ [20] and the De Bruijn graph $(B_{n}, k)$ [3]. We can notice that the n-Pancakes graph shows better performance against topologies $Q_{n}$ and $T_{n}$ giving the ability to connect many peers, with a given degree and diameter. The comparison with $S_{n}$ is not evident, nevertheless we know that the diameter of $P_{n}$ is smaller than that of $S_{n}$ , for all $n < 10$ [13]. $P_{n}$ is lower than $(B_{n}, k)$ in term of degree. However, $(B_{n}, k)$ is oriented while it is not symmetric nor recursive, which constitutes an obstacle for tasks with bidirectional communications. Therefore, Pancake graphs offer better performances compared to other topologies, in terms of degree, diameter, and symmetry for bidirectional communications.

In the pancake graph, nodes should maintain little information about others. In a Pancake graph with $n!$ nodes, each node maintains only $n - 1$ information about neighboring nodes, which is cost effective in terms of both memory space and maintenance.

2.3. Properties of Pancake graphs

Scalability: the order of Pancake graphs changes with the total number of peers in the system. Frequent arrivals and departures of nodes in the Pancake graphs lead to one of the two following situations: expansion or reduction. For the expansion, the node $u_{1} \dots u_{d}$ that belongs to $P_{d}$ is divided into $d + 1$ new nodes ${(d + 1) u_{1} u_{2} \dots u_{d}, u 1 (d + 1) u_{2} \dots u_{d}, \dots, u_{1} u_{2} \dots u_{d} (d + 1)}$ of $P_{d + 1}$ , and vice versa [25].

Expansion: if the total number of peers exceeds a certain threshold, each node $u = u_{1} \dots u_{d}$ that belongs to $P_{d}$ is divided into $d + 1$ new nodes $u^{\exp} (1) = (d + 1) u_{1} u_{2} \dots u_{d}$ , $u^{\exp} (2) = u_{1} (d + 1) u_{2} \dots u_{d}, \dots$ , $u^{\exp} (i) = u_{1} u_{2} \dots u_{d} (d + 1)$ of $P_{d + 1}$ . The new neighbors of $P_{d + 1}$ node can be easily calculated by knowing the neighbors of the original node u belongs to $P_{d}$ [25]. Figure 3 illustrates the operation of the expansion of P2 to P3.

Fig. 3.

Example of “expansion” from P2 to P3.

Reduction: if the total number of peers per node in average decreases beyond a certain threshold, all nodes $(d + 1) u_{1} \dots u_{d} u_{1} (d + 1) u_{2} \dots u_{d} \dots u_{1} \dots u_{d} (d + 1)$ belonging to $P_{d + 1}$ are merged into a single node $u_{1} \dots u_{d}$ that belongs to $P_{d}$ . The reduction is as follows: First, the dominating set (the peers responsible for the clusters construction) in $P_{d + 1}$ is calculated, each node $u = u_{1} \dots u_{d + 1}$ with $u_{1} = d + 1$ becomes a super node or “ruler”. The group formed with its neighbors (dominated) is called a cluster. In the following, let be $u^{dom} (1) = (d + 1) u_{1} \dots u_{d}$ a dominator and $u^{dom} (i) = u (i) (u^{\exp} (1)) = u_{i - 1} u_{i - 2} \dots (d + 1) u_{i} \dots u_{d}$ its neighbor node with an inversion of length i prefix. The idea is to contract each cluster with dominator $u^{dom} (1) = (d + 1) u_{1} \dots u_{d}$ in a single node $u = u \dots u_{d}$ belongs to $P_{d}$ . However, clusters do not yet provide the desired reduction. To obtain the inverse of the expansion, each cluster must share a dominated node with each of its adjacent clusters, as follows: the cluster with the dominator $u^{dom} (1) = (d + 1) u_{1} \dots u_{d}$ sends its dominated node $u^{dom} (i + 1)$ to the cluster with the dominant $(d + 1) u^{(i)} (u_{1} \dots u_{d})$ , i belongs to $[2, d]$ . After the exchange of dominated nodes, each cluster with dominator $u^{dom} (1)$ consists of $u^{\exp} (1) = (d + 1) u_{1} \dots u_{d}, u^{\exp} (2) = u_{1} (d + 1) \dots u_{d} \dots, u^{\exp} (d + 1) = u_{1} \dots u_{d} (d + 1)$ node [25]. Some important properties of Pancake graph can be found in [15,19].

Figure 4 illustrates the process of reducing a Pancake graph P4 to P3. The dominating set, once determined, contains all the nodes that have their $u_{1} = 4$ (starting with 4): 4123, 4132, 4213, 4231, 4312 and 4321. Each peer of these groups is a ruler, it constitutes with its neighbors (dominated) a cluster. The cluster is shown in Fig. 4(a). These clusters do not contain peers that achieve the desired reduction. For this, exchange of dominated peers between clusters is required to reach the situation enabling the reduction. The exchange mechanism of dominated peers between clusters is shown in Fig. 4(a), new clusters that allow the reduction are shown in Fig. 4(b). Each one is merged into a node $u_{1} u_{2} \dots u_{d}$ as it is the case with the cluster dominated by 4123 which is merged to 123.

Fig. 4.

Example of “reduction” from P4 to P3.

Routing in Pancake graph is a key issue. Finding the optimum path in term of delay in a n-Pancakes graph with a polynomial algorithm is still a challenge [28]. So, some solutions are proposed in order to look for the “best” path which is not necessary the optimal one, particularly when the fault tolerance is considered [31]. In [14], the author propose a new model based Pancake graph for P2P lookup acceleration. The architecture is a hierarchical rings. The lookup process is based on the nearest peer with identifier numerically higher or equal to the identifier of the request ressource. Our proposed model is different to that in [14] in many ways, principally the resource keys assignment and the finger tables construction that defines the modified pancake graph architecture of the proposed model. Route [28] is another example of lookup algorithm based on Pancake graph. Algorithm 1 illustrates the functional principle of Route when n-Pancakes graph is used.

Algorithm 1

Algorithm Route ( $S = s_{1} s_{2} \dots s_{n}$ , $d = d_{1} d_{2} \dots d_{n}$ )

2.4. P2P lookup optimisation

P2P lookup optimization and acceleration consists of relaying rapidly each node with others, with few intermediaries, while maintaining only a minimum of contacts for each node. P2P networking is a self organisation and configuration network [30]. Peer-to-peer networks generally implement some form of virtual overlay network on top of the physical network topology, where the nodes in the overlay form a subset of the nodes in the physical network. Data is still exchanged directly over the underlying TCP/IP network, but at the application layer peers are able to communicate with each other directly, via the logical overlay links (it corresponds to a path through the underlying physical network). Overlays are used for indexing and peer discovery, they make the P2P system independent from the physical network topology. Based on how the nodes are linked to each other within the overlay network, and how resources are indexed and located, we can classify networks as unstructured or structured (or as a hybrid between the two). Lookup is the most frequently executed process, its optimization and acceleration is already a challenge. Most important works have been studied this process (see [ 33 ] for example). Recent applications have been emerged in P2P networking such as data collection [34] and Cryptocurrency Networks [8].

Routing process in P2P networking in general and in Pancake graph based P2P networking in particular is done at application layer. Consequently, the lookup process should be more optimized. This optimization still represents a real challenge, especially for critical and complex environments. Given this, we introduce a new optimized method for lookup acceleration based on modified Pancake graph.

3. Proposed solution

The key challenges of Peer-To-Peer networks are focused on research and services location also called lookup process. For example, if a peer $u_{1} u_{2} \dots u_{n}$ requests to access a resource (e.g. file) and determines that its location is on the peer $u^{(1, 2, \dots, i)} (u_{1} u_{2} \dots u_{n})$ (by succession permutation), this is equivalent to locate the peer directly using a search algorithm, based on the principle of permutations.

3.1. Keys assignment

A service or resource can be represented for example as a user terminal (e.g. SIP phone in case of VoIP type of applications), or video stream or data files. So, looking for a specific resource in a network could be done in different ways with different methods more or less complex. Among well known methods including keys assignment to resources with hash functions, to distinguish each one uniquely, such as in Chord [26], where keys are assigned to peers according to a defined law or technic (Higher first peer in Chord). So, to find a service in a network, the key (with the finger tables) is used to learn about the requested peer location. Figure 5 shows an example of key assignment used in our proposed solution.

Fig. 5.

Key assignments example.

Algorithm 2

Algorithm Local_Key ( $C = c_{1} c_{2} \dots c_{n}$ )

In our method, we apply the same principle of combination of keys used in Chord, as the key’s values are between the smallest and largest identifiers of peers in terms of numerical values. Then, a key is assigned to the closest peer in terms of numerical value. Regarding the search mechanism, peer which is looking for the file, analyses the key value and then finds the peer that contains it using the Algorithm 2 and then starts downloading.

Example.

In a Pancake graph P4, the numeric smallest identifier is 1234, and the largest identifier is 4321, so the key is between these two values (e.g. of keys: K2500, K1324 or K3333…etc.). For example, the key K2500 is between two peers whose identifiers are respectively 2431 and 3124 ( $2431 < 2500 < 3124$ ). A request from the peer 4231 for example, for a service key $K 2500$ , exploits the search algorithm illustrated below, for locating the target resource.

3.2. Determination of the node responsible for a specific key

Based on the algorithm Local_Key (), the peer 4231 takes into account that the closest peer responsible of the resource with key $K 2500$ is 2431. Then, a peer looking for a resource whose key is $K 2500$ , knows that peer 2431 is the target node, so it determines the shortest path to this peer to access the requested resource.

The main principle of the proposed algorithm is to calculate the minimum of difference between the key and each peers, and then returns the peer that presents the minimum difference with the requested key.

After locating the destination peer, which stores the requested key (service), an algorithm that seeks the shortest path is executed.

3.3. Algorithm source-destination

In this sub-section, we present a new method to locate the shortest path between any two peers in a graph of Pancakes (algorithm Sour_Dest ()). The proposed algorithm Sour_Dest () operates in three (03) different cases: the first case where the nth values of the source and destination end with different symbols, while the beginning of the destination and the nth value of the source are different (this means: $s_{n} \neq d_{n}$ , and $s_{n} \neq d_{1}$ ).

The 2nd case is when the nth values of the source and destination end with different symbols, while the beginning of the destination and the nth value of the source have the same value (this means: $s_{n} \neq d_{n}$ and $s_{n} = d_{1}$ ). Finally, the 3rd case is where the nth symbols of source and destination are the same, while the nth symbol of the source and the first symbol of the destination are the same also ( $s_{n} = d_{n}$ and $s_{n} = d_{1}$ ). In the following, the three cases are detailed.

Let be $S = s_{1} s_{2} \dots s_{n}$ , $D = d_{1} d_{2} \dots d_{n}$ the source and the destination node respectively, the algorithm is composed of the three cases below:

Case I: ( $s_{n} \neq d_{n}$ and $s_{n} \neq d_{1}$ ),

Case II: ( $s_{n} \neq d_{n}$ and $s_{n} = d_{1}$ ),

Case III: ( $s_{n} = d_{n}$ and $s_{n} = d_{1}$ ).

Case I: ( $s_{n} \neq d_{n}$ and $s_{n} \neq d_{1}$ )

In this case, the lookup service of a peer destination D, from the source peer S, is equivalent to look for the next recipient peer $D_{1} = d_{n} \dots s_{n}$ . This is in order to find a path that leads to the destination D (i.e. to the sub Pancakes where the destination D is located) by a minimal number of permutations. For this, we use the function $Lookup_path ()$ . Then, we apply the mirror of the destination $D_{1}$ , through the Mirror() function, that gives the next new source, denoted $S_{1}$ ( $S_{1} = mirror (D_{1})$ ). This algorithm is executed recursively, in a n-Pancakes graph until destination D is reached. Figure 6 illustrates this typical scenario.

Fig. 6.

Case I ( $s_{n} \neq d_{n}$ and $s_{n} \neq d_{1}$ ).

Case II: ( $s_{n} \neq d_{n}$ and $s_{n} = d_{1}$ )

In this case, the lookup for the peer destination D from the source peer S is done via a direct call to the Mirror() function, to determine the mirror destination. This is in order to find a path that leads to the source $S_{1}$ (i.e. to sub-Pancakes containing the source S). Then, the algorithm is executed recursively to reach the destination D through a serie of permutations. In n-Pancakes graph, the destination D is reached in $O (n)$ . Figure 7 is an example of such case.

Fig. 7.

Case II ( $s_{n} \neq d_{n}$ and $s_{n} = d_{1}$ ).

Case III: ( $s_{n} = d_{n}$ and $s_{n} = d_{1}$ )

In this case, both source and destination end with the same symbol, so they belong to the same sub-Pancakes. Therefore, the search process is limited to this sub-graph only. The algorithm ignores the ultimate symbol and decrements the index to compare the latest front symbols, and so on, by recursive calls to the algorithm. Figure 8 illustrates this case.

Fig. 8.

Case III ( $s_{n} = d_{n}$ and $s_{n} = d_{1}$ ).

Algorithm 3

Function Sour_Dest()

The function Miroir() has two arguments. The first one is the peer for which the function is applied to calculate the permutation. The second argument determines the position where the value has to be swapped. Then, it returns the new value with the desired permutation.

Algorithm 4

Function Miroir()

The function Lookup_path() accepts three arguments, the first two are the source S and destination D respectively. The third argument is the position where the permutation must be performed, to get the peer destination D from source S. Finally, the shortest path in terms of successive permutations between two peers (source and destination) is returned.

Algorithm 5

Function Lookup_path()

3.4. Execution of the algorithm Sour_Dest()

To illustrate the main function of the proposed solution, the execution of the Sour_Dest() algorithm in a 5-Pancake graph P5 for case I, case II and case III are illustrated below:

Case I:

Let be $S = 54132$ and $D = 34521$ two peers that represent source and destination peers respectively. A lookup for peer the D from peer the S is as follows:

For $i = 5$ : note that $s_{5} \neq d_{5}$ and $d_{1} \neq s_{5}$ , so it is equivalent to locate the following destination $D^{1} = 1 \dots 2$ by executing the line 5 of the algorithm Sour_Dest(). We obtain the following new source $S^{1} = 23541$ .

The path 1 is: $54132 \to 14532 \to 23541$ ;

For $i = 4$ : this iteration represents a lookup for the destination D from the source $S^{1} = 23541$ , and corresponds to a lookup request for the destination $D^{2} = 2 \dots 41$ since $s_{4} \neq d_{4}$ and $s_{4} \neq d_{1}$ . By executing the line 5 in the algorithm, we obtain the new source $S^{2} = 45321$ .

The path 2 is: $23514 \to 45321$ ;

For $i = 3$ : from $S^{2} = 45321$ , means to search for $D^{3} = 5.321$ . So, the new source is $S^{3} = 34521$ . The path 3 is: $45321 \to 54321 \to 34521$ .

For $i = 2$ and 1: terminated. The final path is then: $54132 \to 14532 \to 23541 \to 45321 \to 54321 \to 34521$ .

Case II:

Let be $S = 54132$ and $D = 25431$ two peers, source and destination peers respectively. A lookup for the peer D from the peer S is done as follow:

For $i = 5$ : note that $s_{5} \neq d_{5}$ and $s_{5} = d_{1}$ . By executing line 9 of algorithm Sour_Dest(), we obtain the following new destination $D^{1} = 13452$ .

The path 1 is: $25431 \to 13452$ ;

For $i = 4$ : this iteration, means searching for the destination $D 1$ from the source $S = 54132$ . Then the destination $D^{1} = 5 \dots 32$ is searched, since $s_{4} \neq d_{4}$ and $s_{4} \neq d_{1}$ . By executing the line 5 in the algorithm, we obtain the following new source $S^{1} = 31452$ .

The path 2 is then: $54132 \to 31452$ ;

For $i = 3$ : from $S^{1} = 31452$ , we look for $D^{1} = 13452$ , with a recursive call to the algorithm, the new source is $S^{2} = 13452$ .

The path 3 is: $54132 \to 31452 \to 13452$ ;

For $i = 2$ and $i = 1$ : Terminated.

The final path is then: $54132 \to 31452 \to 13452 \to 25431$ .

3.5. Elements of comparison

The main characteristic of the proposed algorithm is the better performance of the routing process, in terms of the number of hops needed to reach the requested destination. Indeed, if we consider an example of two peers $S = 4312$ and $D = 4321$ , then the algorithm Route finds the following path: $4312 \to 1342 \to 2431 \to 3421 \to 4321$ , giving 4 hops for the path length. However, if we consider the proposed algorithm, the path length is equal to 3 hops as following: $4312 \to 2134 \to 1234 \to 4321$ (see Fig. 9).

Fig. 9.

Comparison between Route() and Sour_Dest().

Nevertheless, the unbalanced distribution of keys between peers, could represent a critical issue for the proposed solution. In case of non uniform keys distribution, the number of keys managed by a peer could be significantly different between peers. A typical example is given by peer 1234 which has only 5 keys while the peer 1243 has 45 keys.

4. Performance evaluation

For validation purposes, a specific simulation tool (Java program) has been developed. All tests and results are obtained, based on a platform with the following characteristics for the computers: 2.16 GHz and 1 GB of RAM.

Lookup acceleration is evaluated according to some metrics. The most important are: number of hops from source node to destination node, the end to end delay and the false negative that can gives an idea about the rate of the successful request.

Number of hops: it mesures the number of intermediary nodes that should be considered in order to achieve the request to the correct destination. It is a virtual parameter.

End to end delay: it is a physical parameter. It mesures the time needed to achieve a request from source to destination.

False negative: request can be failed even if the resource is present in the system. The number of similar scenarios is called false negative. This parameter indicates the greedy aspect of the lookup process.

In order to evaluate the performance of the proposed algorithm, we consider the Route algorithm as the main existing solution based on the Pancake graph. The cost lookup is the main performance metric. Tests are performed for two different degrees (P4, P7) of the used Pancake graph.

Fig. 10.

Comparison in terms of number of hops for P4.

Fig. 11.

Comparison in terms of number of hops for P7.

Fig. 12.

Comparison in terms of end to end delay for P4.

4.1. Number of hops

The number of hops is an important parameter that indicates the performance of the lookup process. The obtained results are summarized in Figs 10 and 11. Test (i, j) indicates that the source is i and the destination is j.

For each scenario, the same source i and destination j are considered (X-axis). Figure 10 shows the number of hops order to process a request from a source to a destination in Pancake graph P4.

Figure 11 shows the number of hops in order to achieve a request from a source to a destination in Pancake graph P7. The proposed algorithm outperforms Route, in terms of number of hops in both P4 and P7. This is essentially due to the key assignment and the lookup process divided into three cases (scenarios).

Fig. 13.

Comparison in terms of end to end delay for P7.

4.2. Average end to end delay

The average end to end delay is a physical parameter that mesures the cost lookup such as the number of hops. However, the delay is more significant than the number of hops. Figure 12 (respectively Fig. 13 ) shows the average end to end delay (ms) in order to achieve a request from a source i to a destination j in the Pancake graphs P4 (respectively P7). Delay between two neighboring nodes is a randomly generated (between 0–150 ms). The average delay is almost less than 150 ms. This value (150 ms) represents a threshold that is compatible with delay sensitive applications (e.g. audio streaming) [4]. The proposed algorithm outperforms Route, in term of end to end delay; one of the most important physical parameters. The end to end delay is optimized because the number of hops to achieve request from source node to destination node is optimized.

Fig. 14.

Percent of False Negative in P7.

4.3. False negative

The false negative mesures how many requests are not achieved to the requested destination despite this last is available in the system. This is generally due to the leave of nodes when the request is still running. The nodes exit follows the law of Poisson. Figure 14 shows some examples of the percent of false negative in Pancake graph P7. This percent is generally less than 3% except in some cases where it is equal to 10%. This rate is not important, it is due to the greedy aspect of the lookup process used in the proposed model. The difference between the values of this percent is due to the non-uniform key distribution.

5. Conclusion and future work

In this paper, we have proposed a new model for lookup services based on the Pancake graphs. This model references resources in the network by a keys distribution over all peers. So, a resource that belongs to such a peer is close in terms of numerical value. Then, a lookup algorithm for the shortest path is executed, allowing a peer to reach the requested destination. This algorithm is essentially based on the concept of permutations, which is considered as one of the main key properties for this type of graphs.

When comparing with the algorithm Route, the results show better performance in terms of the number of hops, needed to reach the destination (in a Pancake graph P4). This performance increases in graphs P5, P6 and so on. However, a limitation exists if a uniform keys distribution for the peers is not guaranteed.

In terms of perspective, firstly we envision to explore or extend our model, to assure an efficient keys allocation for a uniform distribution. We also envision to mesure the cost of expanding and reducing the graph given the dynamics of a P2P network. Secondly, we try to adapt the proposed architecture for distributed social networking such as ROUTIL [6].

Footnotes

Acknowledgement

The authors would like to thank Dr. Boudries AbdelMalek and Dr. Omar Mawloud from Bejaia University for their valuable comments and remarks.

References

S.B.

Akers and

Krishnamurthy , A group-theoretic model for symmetric interconnection networks, IEEE Transactions on Computing 38(4) (2002), 555–566. doi:10.1109/12.21148.

S.G.

Akl ,

Qiu and

Stojmenovic , Data communication and computational geometry on the star and Pancake interconnection networks, Technical Report N9l-301, Department of Computing and Information Science, Queen’s University, Kingston, Canada, 1991.

Amad ,

Aïssani ,

Meddahi ,

Benkerrou and

Amghar , De Bruijn graph based solution for lookup acceleration and optimization in P2P networks, Journal of Wireless Personal communications 85(3) (2015), 1471–1486. doi:10.1007/s11277-015-2851-y.

Amad ,

Meddahi and

Vanwormhoudt , A self-adaptive ALM architecture for P2P media streaming, in: CFIP/NOTERE 2015, 2015, pp. 1–6.

Asai ,

Kounoike ,

Shinano and

Kaneko , Computing the diameter of 17-pancake graph using a PC cluster, in: Proceedings of the 12th International Euro-Par Conference, Germany, 2006, pp. 1114–1124. doi:10.1007/11823285_117.

Badis ,

Amad ,

Aïssani ,

Benkerrou and

Bedjguelel , in: ROUTIL: P2P Routing Protocol Based on Interest Links, International Conference on Advanced Aspects of Software Engineering (ICAASE16), Constantine, Algeria, 2016.

Cheklat ,

Amad and

Boukerram , A limited energy consumption model for P2P wireless sensor networks, in: Wireless Personal Communications, Vol. 96, Springer, DOI, 2017, pp. 6299–6324. doi:10.1007/s11277-017-4478-7.

Delgado-Segura ,

Pérez-Sola ,

Herrera-Joancomartí ,

Navarro-Arribas and

Borrell , Cryptocurrency Networks: A New P2P Paradigm, Mobile Information Systems, Hindawi, Vol. 2018, 2018.

Diané ,

Niang and

Gueye , A Hierarchical DHT for Fault Tolerant Management in P2P-SIP Networks, 2010.

10.

Fenn , Low Dimentional Topology, London Mathematical Society Lecture Note, Vol. 95, 1982.

11.

S.M.

Figueira and

V.J.

Reddi , Topology-based hypercube structures for global communication in heterogeneous networks, in: Euro-Par’05 Proceedings of the 11th International Euro-Par Conference on Parallel Processing, Springer-Verlag, Berlin, 2005, pp. 994–1004.

12.

Ganesan and

D.K.

Pradhan , The hyper De Bruijn networks: Scalable versatile architecture, IEEE Transaction on parallel and Distributed System 4(9) (1993), 962–978. doi:10.1109/71.243525.

13.

W.H.

Gates and

C.H.

Papadimitriou , Bounds for sorting by prefix reversal, in: Discrete Mathematics, Vol. 27, Elsevier, 1979, pp. 47–57. doi:10.1016/0012-365X(79)90068-2.

14.

Hacini ,

Amad and

Fouzi , A scalable and hierarchical P2P architecture based on Pancake graph for group communication, Journal of High Speed Networks, IOS Press 23 (2017), 287–309. doi:10.3233/JHS-170572.

15.

C.-N.

Hung ,

H.-C.

Hsu ,

K.-Y.

Liang and

L.-H.

Hsu , Ring embedding in faulty pancake graphs, Journal of Information Processing Letters 86 (2003), 271–275. doi:10.1016/S0020-0190(02)00510-0.

16.

Kaneko and

Suzuki , Node-to-set disjoint paths problem in Pancake graphs, IEICE Trans. Inf. Syst. E86-D(09) (2003), 1628–1633.

17.

C.-K.

Lin ,

H.-M.

Huang and

L.-H.

Hsu , The super connectivityof the pancake graphs and the super laceabilityof the star graphs, Theoretical Computer Science 339 (2005), 257–271. doi:10.1016/j.tcs.2005.02.007.

18.

Michele ,

di Sciascio and

Floriano , Concept abduction and contraction in semantic-based P2P environments, International Journal of Web Intelligence and Agent Systems 9(3) (2011), 179–207.

19.

Nguyen and

Bettayeb , On the genus of Pancake network, The International Arab, Journal of Information Technology 8(3) (2011), 289–292.

20.

D.M.

Pase , Contention and the star graph as a network topology, Technical Report No. CSfl 88-023, CSETech. Paper 176, 1988. http://digitalcommons.ohsu.edu/csetech/176.

21.

A.H.

Payberah ,

Dowling ,

Rahimain and

Haridi , Distributed optimization of P2P live streaming overlays, Journal of Computing 94 (2016), 621–647. doi:10.1007/s00607-012-0195-y.

22.

Qu ,

Zhou and

Kitsuregawa , Sharable file searching in unstructured Peer-to-peer systems, Journal of Supercomputing 51 (2010), 149–166. doi:10.1007/s11227-009-0282-9.

23.

Rocha ,

Kon ,

Cobe and

Wassermann , A hybrid cloud-P2P architecture for multimedia information retrieval on VoD services, Journal of Computing 98 (2016), 73–92. doi:10.1007/s00607-014-0428-3.

24.

Senoussi and Inst. Galilee, Embeddings into the Pancake interconnection network, in: High Performance Computing on the Information Superhighway, 1997. HPC Asia ’97, France, 1999, pp. 73–78. doi:10.1109/HPC.1997.592125.

25.

J.M.

Smit , A Churn-Resistant P2P-System Based on the Pancake Graph, Diploma Thesis, Distributed Computing Group, ETH, Zurich, Switzerland, 2005.

26.

Stoica ,

Morris ,

Karger ,

M.F.

Kaashoek and

Balakrishnan , Chord: A scalable peer-to-peer lookup service for Internet applications, ACM SIGCOMM Computer Communication Review 31(4) (2001), 149–160. doi:10.1145/964723.383071.

27.

K.J.

Sullivan , The Pancake Problem: Improving the Bounds for Sorting by Prefix Permutations, Mathematics Discipline University of Minnesota, Morris, 2005.

28.

Suzuki and

Kaneko , An algorithm for node-disjoint paths in Pancake graphs, IEICE Trans. Inf. Syst E86-D(03) (2003), 610–615.

29.

Wang and

Vanninen , Self-configuration protocols for P2P networks, in: Web Intelligence and Agent Systems, Vol. 4, IOS Press, 2006, pp. 61–76.

30.

Wang and

Vanninen , Self-configuration protocols for P2P networks, in: Web Intelligence and Agent Systems, Vol. 4, IOS Press, 2006, pp. 61–76.

31.

J.-S.

Wu ,

Y.-S.

Hou and

W.-Q.

Cai , Genome rearrangements: Efficient algorithm in pancake graphs with one faulty node, in: The 32nd Workshop on Combinatorial Mathematics and Computation Theory, Taiwan, 2015, pp. 130–134.

32.

Zhang and

Lesser , Forming and searching content-based hierarchical agent clusters in distributed information retrieval systems, in: Web Intelligence and Agent Systems, Vol. 4, IOS Press, 2006, pp. 353–370.

33.

Zhang and

Lesser , Forming and searching content-based hierarchical agent clusters in distributed information retrieval systems, in: Web Intelligence and Agent Systems, Vol. 4, IOS Press, 2006, pp. 353–370.

34.

Zhou ,

Yan ,

Fu and

Yao , A survey on network data collection, Journal of Network and Computer Applications, Elsevier 116(15) (2018), 9–23. doi:10.1016/j.jnca.2018.05.004.