基于效用优化的网络拥塞控制研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
伴随着网络用户的急剧增加,网络拥塞控制问题显得越来越重要。然而传统的TCP拥塞控制协议是基于端系统的流量控制的,它们已经无法适应这些变化。微观经济学中效用和价格概念的引入为拥塞控制的研究提供了新的方向。价格工具能够有效的使各种市场达到平衡条件,它们同样可以用来控制复杂的网络系统。网络定价能够更好的来理解网络管理并让用户理性使用网络,而且对网络服务的适当定价能使用户选择合适的服务质量,满足应用服务器的平衡要求,以及正确评估不同级别和质量的服务。效用概念表达了用户对其所获得的网络服务的满意程度。效用最大化(NUM)问题已经得到多方面学者的注意,它结合了计算机网络、数学优化方法、控制理论和经济学等多方面的知识。拥塞控制和资源分配的关系密切,合理的资源分配是拥塞控制的一种手段。效用最大化模型提供了一种新的资源分配研究方法,它结合了资源分配的效率和公平性,能够从这两个方而进行统一的研究,从而更全面的衡量网络资源分配。
     对于NUM的研究方向主要是改变效用函数或者增加约束条件,这样会产生不同的定价方案,直接影响拥塞控制算法。本文介绍了效用最优化的一般模型和它的求解过程,文中都采用的是梯度投影算法来计算链路价格,分析了它的基本性能。本文综合考虑用户和链路,引入链路重要性结合效用做了两方面的工作:一是基于链路重要性提出了新的最短路算法,将其与效用模型相结合,产生了一种新的拥塞控制方法;二是将其引入到考虑链路成本的效用模型中。另外介绍了一个新的效用模型,它改进了原有的链路价格定价方案,引入了链路利用率变化因子,与原有链路拥塞价格一起来调节源端的发送速率。
     本文的目的分为两个方面:一是体现使用价格机制来管理网络的重要性和可行性。另一个就是说明将链路重要性和效用模型相结合的可行性,并通过最终的对比分析可以看出它的有效性,反映了链路端反馈的信息除了可以促使源端调整发送速率外,还可以优化路由选择。
Accompanying with the rapid increase of Internet users, it will be more important to control congestion. However, the traditional TCP congestion control protocols based on end system have been unable to adapt to these changes. Utility and prices in microeconomics provide a new direction for congestion control. Price instruments are useful in achieving market balance conditions in various markets. They can be also used for control of composite network systems. Internet pricing is essential not only for better possible understand of the network operation but it may also provide means to achieve rational behavior of the network users. Dynamic pricing may be useful, in particular, for balancing demand for access to application servers and for proper valuation of different classes and qualities of service. Utility can measure the user's satisfaction or happiness about the service they acquire. Network Utility Maximization (NUM) have caught the attention of many scholars, it involves various knowledge of the computer network, the mathematical optimization methods, control theory and economics. Congestion control involves with resource allocation, reasonable allocation of the network resources will control congestion. Utility maximization model optimizes allocation which involves efficiency and fairness, so it measures resource allocation more comprehensively.
     The main research direction for NUM is to change the utility function or increase the constraint conditions; this will produce a different pricing method, and then influence the congestion control algorithm. This paper introduces the general model of NUM and how to solve it:using gradient algorithm to calculate link prices, and analyses its basic performances. This paper consider utility involved link importance on tow points:First, proposing a new shortest path algorithm based on link importance, which combined with utility model, producing a new congestion method; Second, introducing a new utility model, which improves the original pricing method, introduce a link utilization change factor, together with the original link congestion prices to adjust the source rate.
     The objective in this paper has two sides:One is to present emerging, opportunities to use price mechanisms for management of computer networks. Another is to present opportunities to involve utility and the link importance, and the final contrast analysis shows the validity, in this method, the information which links feedback can not only make the source adjust rate, but also optimize routing.
引文
[1]魏蛟龙,张驰.基于拍卖的网络带宽分配方法的研究[J].电子学报,2003,31(6):891-894.
    [2]陈晓梅,卢锡城,王怀民.基于微观经济学方法的网络资源分配研究.计算机研究与发展,2001,38:1345-1353.
    [3]张冠湘,杨宗凯.基于计费的网络资源分配的研究.中国科学院上海冶金研究所,2000.
    [4]M.Falkner, M.Devetsikiotis, L.Lambadaris. An over-view of pricing concepts for broadband IP networks[J]. IEEE Communications Survey Tutorials, 2000,3(2).
    [5]闫友彪.基于价格的拥塞控制算法研究[D].2005.
    [6]Ratul Mahajanb, Sally Floydc. Controlling High Bandwidth Flows at the Congested Router[R]. AT&T Center for Internet Research at ICSI (ACIRI) Tech Report TR-01-001, April 2001.
    [7]Ao Tang, Jiantao Wang, S.H.Low. Understanding CHOKe[DB/OL]. In: Proceedings of IEEE INFOCOM, San Francisco, CA. http://citeseer.ist.psu.edu/570417.html, April 2003.
    [8]D.Katabi, M.Handley, C.Rohrs, Congestion control for high bandwidth delay product networks[DB/OL]. In Proceedings of ACM SIGCOMM, August 2002. http://www.ana.lcs.mit.edu/dina/XCP/, Feb 2004.
    [9]Nandita Dukkipati, Masayoshi Kobayashi, RuiZhang Shen et al. Minimizing the Duration of Flows[R]. Stanford HPNG Technical Report TR04-HPNG-061604, 2004.
    [10]F P Kelly, A Maulloo, D Tan. Rate Control for Communication Networks:Shadow Prices, Proportional Fairness and Stability[J]. Journal of Operations Research Society, 1998,49(3):237-252.
    [11]S.H.Low, David E Lapsley. Optimization Flow Control I:Basic Algorithm and Convergence[J]. IEEE/ACM Transactions on Networking, 1999, 7(6):861-874.
    [12]S.Boyd, L.Vandenberghe, Convex Optimization. Cambridge, U.K.:Cambridge Univ. Press, 2004.
    [13]S.H.Low. A Duality Model of TCP and Queue Management Algorithms[J]. IEEE/ACM Transactions on Networking, 2003,11(4):525-536.
    [14]J.Wang, L.Li,S.H.Low et al. Cross-layer optimization in TCP/IP Networks. IEEE/ACM Transactions on Networking, 2005,13(3):582-595.
    [15]J.He, M.Chiang, J.Rexford. TCP/IP interaction on congestion price:Stability and optimally. In Proceedings of ICC 2006, Istanbul, Turkey, 2006, vol.3,1032-1039.
    [16]J.Pongsajapan, S.H.Low. Reverse engineering TCP/IP-like networks using delay-sensitive utility functions. In proc. IEEE INFOCOM 2007, Anchorage, Alaska, USA,2007,418-426.
    [17]S.Athuraliya, S.H.Low, V.H.Li et al. REM:Active queue management. IEEE Network,2001,15(3):48-53.
    [18]D.X.Wei, C.Jin, S.H.Low, et al. FAST TCP:Motivation, architecture, algorithms, performance. IEEE/ACM Transactions on Networking, 2006, 14(6):1246-1259.
    [19]K.Jacobsson, L.L.Andrew, A.Tang et al. An improved link model for window flow control and its application to FAST TCP. IEEE Transaction on Automatic Control, 2009,54(3):551-564.
    [20]C.N.Long, B.Zhao, X.P.Guan et al. The YELLOW active queue management algorithm. Computer Network, 2005,47(4):525-550.
    [21]Kunniyur S, Strikant R. Analysis and design of an adaptive virtual queue(AVQ) algorithm for active queue management[A]. Proceedings of ACM SIGCOMM, San Diego, USA, 2001,31(4):123-134.
    [22]Kunniyur S, Strikant R. An adaptive virtual queue(AVQ) algorithm for active queue management[J]. IEEE/ACM Transitions on Networking, 2004, 12(2):286-299.
    [23]S.H.Low. Equilibrium bandwidth and buffer allocations for elastic traffics. IEEE/ACM Transactions on Networking, 2000, 8(3):373-383.
    [24]J.He, M.Bresler, M.Chiang, et al. Towards robust multi-layer traffic engineering: Optimization of congestion control and routing. IEEE Journal on Selected Areas in Communications,2007,25(5):868-880.
    [25]W.H.Wang, M.Palaniswami, S.H.Low. Application-oriented flow control: Fundamentals, algorithms and fairness. IEEE/ACM Transactions on Networking, 2006,14(6):1282-1291.
    [26]P.Hande, S.Zhang, M.Chiang. Distributed rate allocation for inelastic flows. IEEE/ACM Transactions on Networking, 2007,15(6):1240-1253.
    [27]J.W.Lee, R.R.Mazumdar, N.B.Shroff. Non-convex optimization and rate control for multi-class services in the Internet. IEEE/ACM Transactions on Networking, 2005, 13(4):827-840.
    [28]L.Shi, C.Liu, B.Liu. Network utility maximization for triple-play services. Computer Communications, 2008,31(10):2257-2269.
    [29]朱翠涛,杨宗凯,程文青等等.无线mesh网络中效用与链路强度联合优化的覆盖多播.计算机科学,2009,36(3):51-53.
    [30]M.Chiang. Balancing ransport and physical layers in wireless multichip networks: Jointly optimal congestion control and power control, IEEE Journal on Selected Areas in Communication,2005,2(1):104-116.
    [31]L.Chen, S.H.Low, M.Chiang et al. Cross-layer congestion control, routing and scheduling design in ad hoc wireless networks. In Proceedings of IEEE INFOCOM 2006, Barcelona, Catalonia, Spain, 2006, 676-688.
    [32]C.N.Long, B.Li, Q.Zhang et al. The end-to-end rate control in multiple-hop wireless networks:Cross-layer formulation and optimal allocation, IEEE Journal on Selected Areas in Communications,2008,26(4):719-731.
    [33]H.Yaiche, R.R.Mazumdar, C.Rosenberg. A game theoretic framework for bandwidth allocation and pricing in broadband networks[J]. IEEE/ACM Transaction on Networking, October 2000.
    [34]FP.Kelly. Mathematical modeling of the Internet. In Mathematics Unlimited-2001 and Beyoud, B.Engquist et al. Springer-Verlag, Berlin, 2001, 685-702.
    [35]高鸿业.西方经济学.北京:中国人民大学出版社,2001.
    [36]Afriat,S. Efficient Estimates of Production Functions[J]. International Economic Review. 1972:568-598.
    [37]S.J.Shenker. Fundamental Design Issues for the Future Internet. IEEE Journal on Selected Areas in Communications, Sept. 1995, 13(7):1176-1188.
    [38]武康平,高级微观经济学[M].北京:清华大学出版社,2001:26-75.
    [39]David McDysan. QoS & Traffic Management in IP & ATM Networks,清华大学出版社,2000.
    [40]R.Cocchi. Pricing in Computer Networks:Motivation, Formulation and Example. IEEE/ACM Transactions on Networking, Dec 1993,1(6):614-627.
    [41]L.A.DaSilva, D.W.Petr, N.Akar. Equilibrium Pricing in Multiservice Priority-Based Networks. In Proceedings of IEEE GLOBECOM, Phoenix, AZ, Nov 1997:38(6): 1-5.
    [42]H.Ji, J.Y.Hui, E.Karasan. QoS-Based Pricing and Resource Allocation for Multimedia Broadband Networks. In Proc. IEEE INFOCOM,1996: 1020-1027.
    [43]H.Jiang, S.Jordan. A Pricing Model for High-Speed Networks with Guaranteed QoS. In Proceedings of IEEE INFOCOM, 1996:888-895.
    [44]L.Murphy, J.Murphy, J.K.MacKie-Mason. Feedback and Efficiency in ATM Networks. Proc. IEEE ICC, Dallas, TX, June 1996:1045-1049.
    [45]Z.Cao, E.W.Zegura. Utility Max-Min: An Application-Oriented Bandwidth Allocation Scheme. Proc. IEEE INFOCOM, vol.2,1999:793-801.
    [46]L.A.DaSilva, D.W.Petr, N.Akar. Static Pricing and Quality of Service in Multiple Service Networks. Proc. 5th Joint Conf. Information Sciences, Feb.27-Mar. 3,2000, Atlantic City, NJ, vol.1:355-358.
    [47]F.P.Kelly. Charging and Rate Control for Elastic Traffic. European Transactions on Communications,1997,8:33-37.
    [48]J.Murphy, L.Murphy. Bandwidth Allocation by Pricing in ATM Networks. IFIP Transactions C:Communication Systems, no. C-24, 1994, available from URL http://www.eeng.dcu. ie/-murphyj/publ/publ.html,333-351.
    [49]J.Sairamesh, D.F.Ferguson, Y. Yemini. An Approach to Pricing, Optimal Allocation, and Quality of Service Provisioning in High-Speed Packet Networks. Proc. IEEE INFOCOM, Boston, MA, Apr. 1995:1111-1119.
    [50]S.Athuraliya, S.H.Low, V.H.Li et al. REM:Active queue management. IEEE Network, 2001,15(3).
    [51]K.Malinowski, E.Niewiadomska-Szynkiewicz, P.Jaskola. Price Method and Network Congestion Control. Journal of Telecommunications and Information Technology. Tues 2010.
    [52]姜禹,胡爱群,何明.基于网络传输特性的链路重要性评价方法.中国工程科学,2009,11(9):64-67.
    [53]张冠湘,基于计费的网络资源分配的研究[D].2005,12.
    [54]B.Wydrowski, M.zakerman. MaxNet:A congestion control architecture for max-min fairness[J]. IEEE Communication Lett, Nov 2002, Vol.6:512-514.
    [55]陈怡AdHoc网络带宽资源分配优化技术研究[D].2011,42-47.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700