P2P network is characterized by several important aspects: scalability, decentralization and dynamicity. One of the major problems posed by decentralization and dynamicity of P2P network is how to discover and access to a resource, since it is very difficult to get an overall view of all resources in the P2P community. The most important concern is how to locate a particular resource and identifying the optimized path, that reaches the peer responsible for this requested resource, with a minimum number of hops and an optimized delay.
In this paper, we propose a new scalable and hierarchical P2P architecture for lookup acceleration and optimization based on Pancake graph. This architecture can supports many type of applications such as: file sharing, collaborative work and asynchronous distributed group communication, etc. The performance evaluation shows that results are globally satisfactory.
S.Akers and B.Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE, Transactions on Computing (1989).
2.
M.Amad, D.Aïssani, A.Meddahi, M.Benkerrou and F.Amghar, De Bruijn Graph based solution for lookup acceleration and optimization in P2P networks, Wireless Personal Communications85(3) (2015), 1471–1486. doi:10.1007/s11277-015-2851-y.
3.
M.Amad, A.Meddahi and D.Aissani, P2P networks management survey, International Journal of Computer Sciences Issues (IJCSI)9(1) (2012), 139–148.
4.
S.Androutsellis-Theotokis and D.Spinellis, A survey of peer-to-peer content distribution technologies, ACM Computing Surveys36(4) (2004), 335–371. doi:10.1145/1041680.1041681.
5.
J.Aspnes and G.Shah, Skip graphs, In: Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, 12–14 January 2003, pp. 384–393.
6.
M.Camelo, D.Papadimitriou, L.Fàbrega and P.Vilà, Efficient Routing in Data Center with Underlying Cayley Graph, Springer International Publishing, Switzerland, 2014.
7.
A.Deng and Y.Wu, De Bruijn digraphs and affine transformation, Eur. J. Comb.26(8) (2005), 1191–1206. doi:10.1016/j.ejc.2004.06.018.
8.
Y.-P.Deng and X.-D.Zhang, Small cycles in the Pancake graph, ARS Mathematica Contemporanea7 (2014), 237–246.
9.
P.Desnoyers, D.Ganesan and P.Shenoy, TSAR: A two tier sensor storage architecture using interval skip graphs, in: SenSys 05, San Diego, California, USA, 2005.
10.
D.Eppstein, M.T.Goodrich and J.Z.Sun, The skip quadtree: A simple dynamic data structure for multidimensional data, in: 21st ACM Symp. on Computational Geometry (SCG), 2005.
11.
S.Femmam, M.F.Zerarka and M.I.Benakila, New Approach Construction for Wireless ZigBee Sensor Based on Embedding Pancake Graphs, Network and Communication Technologies1(1) (2012). Available at: http://www.ccsenet.org/journal/index.php/nct/article/view/17586. doi:10.5539/nct.v1n1p7.
12.
G.Fertin and A.Raspaud, A survey on knodel graphs, Discrete Applied Mathematics137 (2004), 173–195. doi:10.1016/S0166-218X(03)00260-9.
13.
G.Fertin, A.Raspaud, O.Sykora, H.Schorder and I.Vrto, Diameter of Knodel Graph, 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2000), Lecture Notes in Computer Science, Vol. 1928, Springer-Verlag, 2000, pp. 149–160. doi:10.1007/3-540-40064-8_15.
14.
P.Fraigniaud and P.Gauron, D2B: A De Bruijn based content-addressable network, Theor. Comput. Sci.355(1) (2006), 65–79. doi:10.1016/j.tcs.2005.12.006.
15.
A.-T.Gai and L.Viennot, Broose: A practical distributed hash table based on the De-Bruijn topology, in: Proceedings of the 4th International Conference on Peer-to-Peer Computing (P2P), Zurich, Suisse, 2004, pp. 167–174.
16.
M.T.Goodrich, M.J.Nelson and Z.J.Sun, The rainbow skip graph: A fault-tolerant constant-degree distributed data structure, in: SODA’06: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, New York, NY, USA, ACM, 2006, pp. 384–393. doi:10.1145/1109557.1109601.
17.
A.Gupta and L.K.Awasthi, Peer-to-peer networks and computation: Current trends and future perspectives, Computing and Informatics30 (2011), 559–594.
18.
H.Harutyunyan and J.He, A new peer-to-peer network, in: PerCom 2007 Workshops. Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, 2007, pp. 120–125.
19.
N.J.A.Harvey, M.B.Jones, S.Saroiu, M.Theimer and A.Wolman, Skip net: A scalable overlay network with practical locality properties, in: Proceedings of the 4th Conference on USENIX Symposium on Internet Technologies and Systems – Volume 4, USITS’03, Berkeley, CA, USA, 2003, pp. 9.
20.
M.F.Kaashoek and D.R.Karger, Koorde: A simple degree-optimal distributed hash table, in: 2nd International Workshop on Peer-to-Peer Systems (IPTPS’03), LNCS, Vol. 2735, Springer, Berlin/Heidelberg, Berkeley, California, USA, 2003, pp. 98–107.
21.
M.Karpovsky, L.Levitin and M.Mustafa, Optimal turn prohibition for deadlock prevention in networks with regular topologies, IEEE Transactions on Control of Network Systems1(1) (2014), 74–85. doi:10.1109/TCNS.2014.2304869.
22.
J.Kathryn and J.Sullivan, The pancake problem: Improving the bounds for sorting by prefix permutations, Mathematics, Discipline, University of Minnesota, Morris, April 2005.
23.
K.Kaneko and Y.Suzuki, Node-to-set disjoint paths problem in pancake graphs, in: IEICE TRANS, 2003.
24.
A.Lars, D.Eppstein and M.T.Goodrich, Skip-webs: Efficient distributed data structures for multi-dimensional data sets, in: ACM SIGAT-SIGOPS Symposium on Principles of Distributed Computing (PODC), ACM Press, New York, 2005, pp. 69–76.
25.
C.Lavault, Embeddings into the Pancake Interconnection Network, LIPN, CNRS ESA 7030, University Paris 13 Villetaneuse, France, April 1999.
26.
D.Loguinov, J.Casas and X.Wang, Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience, IEEE/ACM Trans. Network.13(5) (2005), 1107–1120. doi:10.1109/TNET.2005.857072.
27.
P.Maymounkov and D.Mazières, Kademlia: A peer-to-peer information system based on the xor metric, in: Proceedings of 1st International Workshop on Peer to Peer Systems (IPTPS’02), Cambridge MA, USA, 2002, pp. 53–65. doi:10.1007/3-540-45748-8_5.
28.
W.Pugh, Skip lists: A probabilistic alternative to balanced trees, Communications of the ACM33(6) (1990), 668–676. doi:10.1145/78973.78977.
29.
Y.Qifeng, X.Tianyin, Y.Baoliu, L.Sanglu and C.Daoxu, Skip stream: A clustered skip graph based on-demand streaming scheme over ubiquitous environments, in: IEEE, International Conference on Parallel Processing, Vienna, Austria, 2009.
30.
S.Ratnasamy, P.Francis, M.Handley, R.Karp and S.Shenker, A scalable content-addressable network, in: IN Proc. ACM SIGCOMM, 2001, pp. 161–172.
31.
I.Stoica, R.Morris, D.Karger, M.F.Kaashoek and H.Balakrishnan, Chord: A scalable peer-to-peer lookup service for Internet applications, in: ACM SIGCOMM’01, San Diego, California, USA, 2001, pp. 149–160.
32.
Y.Suzuki and K.Keiichi, An algorithm for node-disjoint paths in Pancake graphs, IEICE TRANS, INF. Syst.E86-D(3) (2003), 610–615.
