Special Classes Of Graphs-based P2p Overlay Network Design And Analysis

The current work deals with the problem of resource management in structured P2P systems. The topological properties of the overlay networks are critical factors that dominate the performance of structured P2P systems.Therefore,it is very important to design a suitable topology for networks.It is well known that there are two important requirements for P2P network topologies. First,P2P networks always pursue a topology with arbitrary size and degree in order to deal with the uncontrolled dynamic operations of nodes,such as joining,departing and failing.Second,P2P networks attempt to design and implement a topology with as minimum diameter as possible given N nodes and fixed degree d.The Kautz digraph has some interesting properties for the design in networks,e.g.,constant degree and optimal diameter.In the third chapter we design a CAN network based on the Kautz digraph.However,the orders of Kautz digraph are a series of discrete integers but cannot cover all integers under a given degree d.To achieve an overlay network with arbitrary size and degree,we structure a network which based on the generalized Kautz digraph and rings(BGKR)in the fourth chapter.Byzantine faults in a peer-to-peer(P2P)system are resulted from adversarial and inconsistent node behaviors.Faulty nodes can disrupt the routing functions in the node joining and lookup schemes.Byzantine attackers may collude with each other to paralyze the entire P2P network operations. We discover a novel DHT-based overlay networks(REIK)with Byzantine fault tolerance in the fifth chapter.REIK based on a ring which embeds an inverse Kautz digraph IK(d,m),to enable multi-path P2P routing.The inverse Kautz network provides multiple entry points and multiple routes between node pair.The REIK overlay is the first constant degree and O(log n) diameter DHT scheme with constant congestion and Byzantine fault tolerance.For large d＞＞2, the REIK overlays handle random and Byzantine faults effectively,far beyond the capability of Chord and CAN.Large-scale P2P systems typically have hundreds of thousands of peers that involve frequent dynamic activities.Current structured overlays do not identify well the rhythm in the dynamic activities,thus resulting in high maintenance overhead.Empirical studies have shown that participating nodes in P2P systems are not equivalent.Some nodes,known as super peers,are more powerful and stable than the others.Such heterogeneity has been taken into account in the design of P2P systems.In the sixth chapter,we design a novel hierarchical REIK overlay network by exploiting super peers,HREIK.It reduces REIK system maintenance overhead and provides high quality routing service.The results show that HREIK reduces the maintenance overhead while delivering much better routing performance,as compared to current structured P2P systems.This thesis mainly studies the designs and analyses in structured P2P networks,and is divided into seven chapters.In the first chapter we illuminate background of our study and put forward of the problems, the work we do in the paper and the structure of the paper.The second chapter optimal routing and load balance for D2B.In the third chapter we structure a Kautz based content-addressable network (KZCAN).In the fourth chapter we design a P2P network based on generalized Kautz and ring with constant congestion.In the fifth chapter we use inverse Kautz digraph to handle Byzantine faults.In the sixth chapter we adopt hierarchical structure to reduce REIK system maintenance overhead.The seventh chapter mainly present the following problems for future research.