Research On Algorithmic Game Theoretic Optimization Technologies For P2P Networks

Large-scale P2P networks have become one of mature network applications in nowadays, in which decentralized interaction mechanisms are used, so that each P2P node in the network can access, share others’resource, including computing power, network bandwidth, storage space etc. And the field of P2P application ranges from the document distribution, distributed storage, real-time multimedia data transmission to computer-supported collaborative work. However, most P2P systems are built on the assumption that users are willing to provide shared resources, obviously this assumption ignores the node consider their own interests, the ability to act in accordance with the established protocol. Related study found that selfishness is the nature of P2P nodes can not be ignored, the selfish behavior of nodes in P2P network application will result in serious problems, such as node uncooperative behavior, routing hot spots caused by the unfair distribution of resources between nodes and node selfish routing behavior problems and so on. These problems will harm P2P network running quality and service quality.To solve these problems aforementioned, this work not only systemically analyzes the above issues existed in the P2P network, but uses algorithmic game theory as tools to overcome those problems. The main contributions of this work are as follows:(l)Motivated by how to find a mechanism to encourage nodes to share resources and provide services, this paper presents an Incentive Mechanism for Node’s Cooperation in P2P networks (IMNC for short), which encourages node’s service and voids the betrayal of node in P2P networks with the condition of P2P node’s bounded rationality and the social behaviors of nodes in P2P networks. Paper takes into account diversity of nodes types, complexity of node strategies, asymmetry of node information and uses replicate dynamics model to simulate node’s learning and strategic adjustment process in P2P application. In this model, node’s behaviors are divided into three types. The corresponding strategies adopted by each type of nodes at each stage in P2P application can be defined as mixed strategies of nodes. Based on such strategies, paper analyzes payoff matrix of the evolution game among various node strategies, the game’s evolutionary stability and also shows the transfer conditions for reaching P2P evolution strategy. Finally, simulations based on the evolutionary results with P2P network environment are carried out. Moreover, simulation gives us interesting insight into the overall nature of nodes’interactions and how system efficiency can be improved.(2)Aimed to improving the efficiency of self-interested P2P node’s routing traffic through a congested network and overcoming selfish routing in P2P networks, we introduce a Mechanism for Avoiding Selfish Routing (MASR for short) to study the selfish routing behaviors of nodes in P2P networks. In the paper, we model the routing behaviors of nodes as a noncooperative routing game, in which self-interested player’s route traffic through a congestion-sensitive network. We extend the model of selfish routing to study the dynamical behaviors of nodes, by adopting a generalized approach of imitative dynamics. We not only analyze the model’s stability and convergence, but reveal that the efficiency of P2P node’s routing can be improved when the model reach an equilibrium state. Finally we also give an algorithm and experiments on how to improve P2P traffic efficiency based on our evolutionary game model.(3) Strategy-proof P2P Replica Placement Mechanism (SPRPM for short) is introduced in this thesis. We treat the nodes as strategic agents and treat the replica allocation as a deliberate auction where node is incentivized to give his true quality of service for getting the replica. Our mechanism computes node utility for all possible replica destination and payments for those destination nodes; and the best appropriate node can be selected as the final placement destination. We show how to compute our mechanism with an allocation algorithm that is a straightforward extension to P2P allocation method and causes an overhead in convergence time. To illustrate the correctness and effectiveness of SPRPM, we give formal proof on how to achieve strategy-proof and convergence time. Furthermore, simulations are shown that nodes have no motivation to lie during the replica auction and the traffic quality of overlay network, the avoidance of hot spot congestion, quality of service in P2P file system have been distinctly improved by SPRPM.(4) VCG-based P2P Bandwidth Allocation Mechanism (VPBA for short) is introduced to study P2P bandwidth game--the bandwidth allocation in P2P networks. Unlike previous work which focuses either on routing or on forwarding, this paper investigates the game theoretic mechanism to incentivize node’s real bandwidth demands and propose novel methods that avoid congestion proactively, that is, prior to a congestion event. More specifically, we define an incentive-compatible pricing vector explicitly and give theoretical proofs to demonstrate that our mechanism can provide incentives for nodes to tell the true bandwidth demand. Finally, we evaluate our mechanism by simulations, and the simulation results show that the incentive pricing mechanism can distribute the bandwidth fairly and effectively and can also avoid the routing hotspot and congestion effectively.