【作者】 魏蛟龙；

【导师】 周曼丽； 柳健；

【作者基本信息】 华中科技大学 ， 通信与信息系统， 2004， 博士

【摘要】 随着网络业务量的迅猛增加和业务类型的多样化,以带宽为代表的计算机网络资源已成为一种典型的稀缺资源。网络资源的分配和控制对于提高用户对网络服务的满意度,优化网络系统的整体性能具有十分重要的意义。由于用户对资源的使用有不同的优化目标,而且用户对于自身行为策略的选择与其它用户的行为策略相关,因而引入博弈论来分析用户在资源分配中的互动是十分必要的。本文通过将计算机网络控制的工程方法与博弈论模型、经济分析相结合,对网络资源分配的理论方法和实现技术进行了深入的研究。本文首先对网络资源分配方法进行了详细综述,提出了IP网络资源分配博弈的一般模型,讨论了模型的构成要素,给出了纳什均衡和帕累托最优的存在条件,指出了基于博弈论模型的网络优化的一般策略和步骤,限定了该模型的适用条件。为网络资源分配方案的横向比较、性能分析及算法改进提供了统一的理论基础。针对IP网端到端QoS保障机制没有涉及分配策略的缺陷,以IP网络资源分配博弈模型为基础,讨论了IntServ、DiffServ和MPLS三个支持多业务的资源分配方案,推导出这些方案在集中化控制和非集中化控制之下,Nash均衡的存在性及其性质,得到了每种方案中各方参与者的优化问题的解,并给出了相应的物理解释。研究了在用户效用函数不可知条件下的博弈问题。从博弈论的角度分析了最大最小公平和流保护的重要性及其优点。通过在用户端实施支持媒体流传输的TCP友好协议,在网络端扩展SCORE机制,提出了支持多媒体业务流的TCP友好SCORE改进机制。通过将服务区分和优先级标签引入CHOKe机制,提出了可扩展的D-CHOKe算法。该算法可支持区分服务并在同一服务级别中提供流保护。通过与RED等其它缓存管理算法比较,验证了新算法的先进性。研究了闭环控制下的弹性业务的资源分配博弈,证明了当前Internet 资源分配效率低的原因是存在拥塞外部性,从博弈论的角度分析了改进流量控制的措施。讨论了ECN计费方案:在过载的网络上采用ECN标记分组,然后在网络边缘对被标记的分组收取<WP=4>固定价格的小额费用,给终端用户提供正确的信息和激励,使之合理地使用网络资源。在用户端,提出了基于少数者博弈模型来估计收到标记数目的流量控制算法。研究了开环控制下的非弹性业务的资源分配博弈,分析了基于FCFS的接纳控制所存在的问题。在基于Vickrey拍卖的接纳控制机制的基础上,提出了可扩展的统一价格拍卖方案。该方案拍卖规则简单,在网络环境下具有激励兼容性,并可以进一步扩展出衍生市场机制,解决资源预留与价格波动间的矛盾,实现一个可预测、低风险、易于用户决策的市场机制。与其他拍卖机制相比,该算法复杂度低,可扩展性强。研究了无线网络中的功率分配博弈,证明了干扰的外部效应使得无线网络功率控制的效率变低。通过研究WCDMA系统中上行链路的干扰情况,得出了WCDMA系统容量与业务性能指标的关系。通过定义网络资源份额,将功率控制问题转换为总量小于1的网络资源份额的分配问题。提出了基于计费的功率控制算法,利用统一价格拍卖对网络资源份额进行最优配置,使得发射功率这一重要无线资源合理地分配给对其评价最高的用户业务。该算法具有可预测、全局最优、可扩展性强的优点。更多还原

【Abstract】 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. <WP=6>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.更多还原