网络服务商的拥塞控制策略研究

【作者】 陈波；

【导师】 华中生； 周亚平；

【作者基本信息】 中国科学技术大学 ， 管理科学与工程， 2007， 博士

【摘要】 随着网络技术的发展与应用的普及，Internet正面临着许多新的挑战，主要体现在：资源相对稀缺、网络拥塞、服务多样化及竞争的加剧。传统的“尽力而为”服务模式已经不能够满足消费者应用多样化的需求，网络服务商(Internet Service Provider，ISP)必须改变当前的服务模式，必要时还需提供有质量保证的服务以满足应用的需求。但在目前的网络服务中，ISP与消费者都是基于自身的性能目标做出相应的决策。ISP根据消费者的需求信息制定规则，与此同时，消费者则在ISP制定的规则下选择自己的消费模式。因此为了更有效地利用稀缺的网络资源，给消费者提供更满意的网络服务，有必要对ISP在网络服务控制中的行为进行研究。针对上述问题与挑战，本文运用经济学的方法探讨了ISP的价格控制、资源分配、呼叫接入控制(Call Admission Control，CAC)及供需市场上的均衡问题，目的是使系统在兼顾网络服务质量保证的前提下，最大化用户的满意度与ISP的收益，使网络资源得以更有效地利用。本文用定量与定性分析相结合的方法，研究了ISP的网络拥塞控制策略与系统均衡问题。在基于消费者需求信息的基础上，分别对基于价格控制策略的拥塞控制、基于资源分配策略的拥塞控制、基于呼叫接入控制策略的拥塞控制及在控制策略一般化基础上网络供需市场的供需均衡问题进行了深入探讨，为ISP在制定具体的控制策略时提供了一种理论分析与定量分析的参考依据。根据研究点的不同，文章可以分为以下两个部分：第一大部分是考虑单ISP的网络拥塞控制问题，主要章节是第2、3、4章。在基于价格控制策略的拥塞控制研究中，给出两种基于价格控制策略的拥塞控制方案。面对实际中ISP价格控制策略选择的问题，给出了一种基于消费者需求统计信息的价格控制策略比较选择方法，为ISP在制定新的定价策略、决定最优定价、比较不同定价策略优劣时提供了一种定量的参考依据。在基于资源分配策略的拥塞控制研究中，给出了两种基于不同目标的带宽分配策略，并从非合作博弈的角度分析了这两种带宽分配策略对ISP收益、消费者利益及系统均衡的影响。在基于CAC的拥塞控制研究中，分析了在不同服务价格条件下使期望报酬最大化的接入控制策略，以确定ISP的供应特性；此外还给出相应的仿真算法，比较了不同控制策略对ISP收益的影响，为ISP按照网络的实际状况选择合适的资源分配策略与接入控制策略提供了一个定量的分析方法。第二大部分是考虑多ISP市场中的拥塞控制问题，主要章节是第5章。在研究多ISP市场中的价格控制策略中，给出了一种基于消费者需求统计信息的价格控制策略的选择方法，给进入ISP在采用价格控制策略控制网络拥塞问题、决定最优定价、比较不同定价策略优劣时提供了一种定量的参考依据。最后本文将所研究的拥塞控制策略一般化，研究了多ISP非合作网络供需市场上的供需均衡问题，给出了传统经济理论中供求均衡稳定性条件的对策论意义，证明了经济理论中的供求均衡稳定性条件。本文的主要创新性工作如下：1．将消费者的效用函数、需求信息及ISP的收益考虑到价格策略的制定中，并给出了一种基于消费者需求统计信息的价格控制策略的比较选择算法；与现有价控策略相比，本文所制定的价格策略在实现ISP利润最大化与拥塞控制的同时，还兼有简便、公平的优点。2．将马尔科夫决策过程(Markov Decision Process，MDP)与排队网络性能势理论应用于对ISP供应特性的分析中。通过将系统的长期平均报酬转化为MDP中的稳态性能，给出了CAC基于长期平均报酬准则下的策略优化算法。该算法将对一个M*K维的整体寻优转化为K次M维的向量寻优，从而能够显著地降低由于高维状态所带来的计算复杂度。3．应用博弈论中的有关理论与压缩映象定理寻求一类多ISP非合作对策纳什均衡存在、唯一的充分条件，给出了传统经济理论中供求均衡稳定性条件的对策论意义，证明了经济理论中的供求均衡稳定性条件；说明了经济学中蛛网模型的稳定供求均衡实际上就是对策理论中的纳什均衡，从而给出了传统经济理论中关于这一结论的新解释。更多还原

【Abstract】 Along with the development application and wide spread of network techniques, it is facing several new challenges, mainly including: relative lack of resources, network congestion, service diversity and competition rivalry. Traditional "best effort" service can no longer satisfy the requirements of varying customer applications. Therefore, Internet service provider (ISP) should change current service mode and provide guaranteed services if necessary in this case. But in current Internet service, ISP and customers make decisions that optimize their individual performance. ISP makes the rules and accordingly the customers select their consumption modes. To make more efficient use of sparse network resources, and provide satisfying services as well, it is necessary to investigate ISP’s behaviors in network control and competition. To solve the aforementioned problems and challenges, this research focuses on ISP’s price control, resource allocation, admission control and equilibrium in supply-demand market with the help of economic methods, in order to maximize customer satisfaction and ISP’s profit as well. In this way, network resources would be utilized more efficiently with the precondition of guaranteed services.This paper employs quantitative as well as qualitative method for analyzing congestion control and system equilibrium. Based on customer demand information, congestion policies based on internet pricing, resource allocation and call admission control (CAC) respectively have been discussed. Furthermore, these policies are generalized, then the corresponding equilibrium problem is analyzed as well. This work attempts to suggest a reference benchmark for making specific control.Therefore, this paper can be partitioned into two parts:The first part focused on sinle-ISP network congestion control problem. The discussions lie in chapter 2, 3 and 4. In studying congestion control based on pricing policy, two policies based on customer demand information are presented. To deal with practical choice problem of price control policies, a comparative method for policies choosing based on statistical information of customer demand is suggested. In studying of congestion control based on resource allocation, two different bandwidth allocation policies guaranteeing the Quality of Service based on the demand information of the customers have been proposed.Then the effects of different bandwidth allocation policies on ISP’s revenues, customer’s benefits and system equilibrium have been analyzed as well. In studying of congestion control based on CAC, the control policy which maximizes the expected rewards under several different service prices is investigated, so as to analyze the ISP’s supply characteristics. In the mean time, corresponding simulation algorithm is developed to compare influences caused by different control policies on ISP. This provides a quantitative analyzing method for ISP to choose appreciate resource allocation and admission control policies according to network status.The second part focused on multi-ISP network congestion control problem. The discussion lies in chapter 5. In studying of multi-ISP pricing policy, an analyzing method based on statistical information of customer demand is proposed. In the end, another implication in the sense of game theory is presented for the stability condition of supply-demand equilibrium in traditional economic theory after generalizing the above congestion control policies. It can demonstrate the stability condition for supply-demand equilibrium in economic theory.The innovations of this dissertation are summarized as followed:1. In making pricing policies, customer’s utility function, demand information and ISP’s revenues are considered; Furthermore, a comparative method for policies choosing based on statistical information of customer demand is suggested. Comparing to the existing pricing policies, these policies achieve ISP’s profit maximization and congestion control, at the same time, have the merits of simplicity and fairness.2. Markov decision process (MDP) and Performance Potential theory are applied to the analysis of supply characteristics. Through converting system’s long-run expected average reward into steady-state performance in MDP, a policy optimization algorithm under the rule of long-run expected average reward. This algorithm transform M * K-dimension global optimization into K times of M-dimension vector optimization. So the computing complexity brought by high-dimension state decreases evidently.3. By applying game theory and contraction mapping theorem, a sufficient condition for the existence and uniqueness of Nash equilibrium in a multi-person non-cooperative game is proposed. Another implication in the sense of game theory is presented for the stability condition of supply-demand equilibrium in traditional economic theory. It can demonstrate the stability condition for supply-demand equilibrium in economic theory. So the stable supply-demand equilibrium of cobweb model in economics is in fact equivalent to the Nash equilibrium in game theory. That is a brand-new explanation for the conclusion in traditional economic theory.更多还原