Network Resource Allocation Based On Game Theory

With the increasingly amount and the heterogonous nature of the network application, network resource such as bandwidth has become a kind of typical scare resource and requires careful allocating and control if optimal system performance and maximal user satisfaction are to be achieved. Because user has different optimizing strategy in maximizing its own benefit and its choice of action (strategy) will depend on those of other users, it is necessary to address the behavior of users in the framework of game theory. Based on combining fields of Game theory, economics and the engineering of computer networks, the theory and the techniques of network resource allocation are studied here in depth. First, the dissertation gives a summary of the research on network resource allocation in detail. Then a universal game theoretical model for resource allocation problems in IP networks is proposed. The conditions to guarantee the effectiveness of the model and the existence criteria of Nash equilibria and Pareto optimization are given. The general police and procedure of the game theoretical network optimizing are summarized. This game-theory-based universal model develops the theoretical foundation of discussing the internal relationships between different allocation schemes and analysis of their performance characteristics.In order to supply the lack of the resources allocation police in end to end IP QoS guarantee mechanisms, the approaches to design the police of IntServ and DiffServ are discussed. Based on the game theoretical model given in the chapter 2, a comprehensive analysis of centralized and decentralized control problems in IntServ and DiffServ are provided, complete characterization of Nash equilibria and their existence criteria of the game are given, and the conditions under which the solutions are system-optimal are analyzed.The resource allocation game when the utility functions of users are unknown is studied. The advantages and importance of flow protection and maximum-minimum fairness is analyzed from the view of game theory. By designing TCP-Friendly-Protocol supporting multimedia stream for end users and the progressive SCORE (Core stateless) at the routers, a new SCORE scheme to provide flow protection and priority of sub-flow is present. By introducing service differentiation and label of priority into CHOKe, a scalable algorithm called D-CHOKe which can support DiffServ and provide flow protection in the same service level is proposed. The resource allocation game with elastic users in closed-loop control is also studied. The existence of congestion externality in current Internet which leading to inefficient resource usage is proved. And the approach to enhance the efficiency of flow control mechanism is analyzed form the point of game theoretical view. By marking packets at overloaded resources with ECN algorithm and by charging a fixed small amount for each mark received, this new ECN pricing (congestion pricing) approach can provide end-users with the necessary information and the correct incentive to use the network efficiently. Using the Minority Game model to estimate the marks that the user will be received, this chapter proposes a new user's flow control algorithm. Studies of the resource allocation game with inelastic users in open-loop control are also given. The problem of FCFS-based admission control is analyzed. Previous works focused on Vickrey auction which is incentive compatible in classic auction theory are summarized. With discussing the faults of the most representative auction-based admission control mechanisms, a new scalable method called uniform-price auction, which has the simplest auction rule is proposed and its incentive compatibility in the network environment is also proved. Finally, the basic mode is extended to support applications which require minimum bandwidth guarantees for a given time period by introducing derivative market, and a market mechanism for network resource allocation which is predictable, riskless, and simple for end-users is completed.