（控制理论与控制工程专业论文）基于pmp机制的网络拥塞价控策略.pdf

i 一 ；ip；j ，繁 ；叠j嗡 at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g p r i c i n gc o n t r o ls t r a t e g yf o rn e t w o r k c o n g e s t i o nb a s e d o np m p b y ：t o n g l i s u p e r v i s o r ：p r o f e s s o rj i n gy u a n w e i n o r t h e a s t e r nu n i v e r s i t y d e c e m b e r2 0 0 7 ，毒 _1，驴丫li a ：j ! 露黔 _5篡11| ，lip ；i 、；w毋黢 *一?，、#；缸赫#妒 1 ； 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中 取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表 或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：殄m ，。7 一， 日期：列8 弓1 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：彳另百叼导师签名： 签字日期：调易多1 签字日期： 玎 li_|_i一 xj 1 参 东北大学硕士学位论文 摘要 基于p 机制的网络拥塞价控策略 于两要 随着i n t e m e t 业务量的迅速增长，网络资源特别是带宽资源出现了需求大于供给 的现象，网络拥塞日益加剧。而传统的拥塞控制和带宽分配方式缺乏合理的激励机 制，或者没有考虑用户的不同服务质量需求，存在明显的不足。因此，如何合理分 配有限的资源为不同q o s ( q u a l i t yo fs e r v i c e ) 需求的应用提供服务，提高资源使用效 率，是亟待解决的问题。把微观经济学方法引入计算机网络资源分配领域，帮助网 络管理者进行合理的价控，是具有重大意义的研究课题。对策论是微观经济学的重 要分枝。通过引入对策论的理论方法，使用拥塞计费等手段促使用户独立优化自己 的效用函数，更符合网络的分布特性，能够接近或达到资源利用的最佳效率。 本文在以对策论为基础的网络资源分配的模型的基础上，首先讨论了n a s h 均衡 点的性质和p a r e t o 最优的条件，从理论上分析了网络拥塞计费的作用。总结比较了 现有的基于价格的计费机制，重点阐述了p m p 的理论模型。针对该模型的不完善之 处，详细研究了平衡状态的存在以及定价机制的作用，提供了该方法的理论依据， 并给出了数值分析结果。 其次，基于p m p 的定价策略，把网络划分为不同的逻辑子网，讨论了分组进入 子网依赖于网络时延和子网的价格，给出了具体的定价模型，此外，在约束条件下 分析了模型解的存在，以及网络提供商利润的最大化，最后通过数值结果验证了模 型的有效性和正确性，并分析了子网在带宽分配不同的情况下，网络所获得的利润 变化。然后通过数据图示讨论了网络用户最大收益对网络带宽的分配、时延、以及 网络价格的敏感性，并比较了网络存在基于p m p 模型划分子网时的情况及没有子网 划分的情况，即没有p m p 机制的网络，此外，在此基础上分析了不同类型的数据包 产生不同延时的情况，并给出了解存在的必要条件。 最后，结论与展望部分总结了前面所做的工作，并对网络价格控制中存在的其 他问题进行了简单的分析，以及对未来可做的工作方向的阐述。 关健词：拥塞控制；对策论；n a s h 均衡；拥塞计费；p m p l ，ij 、 。 扫 p r i c i n gc o n t r o ls t r a t e g y f o rn e t w o r k c o n g e s t i o n b a s e do np m p a b s t r a c t w i t ht h er a p i dd e v e l o p m e n t o ft h ei n t e r n e t ，t h en e t w o r kr e s o u r c ee s p e c i a l l yb a n d w l d t n r e s o u f c eb e c o m e ss c a r o ea n dn e t w o r kc o n g e s t i o ni sa f u n d a m e n t a lp r o b l e mt o d a y h o w e v c r t r a d i t i o n a la p p r o a c h e st oc o n g e s t i o n c o n t r o la n dr e s o u r c ea l l o c a t i o ni g n o r et h eq o so f d i f f e f c n tu s e ra n dl a c kp r o p e ri n c e n t i v e m e c h a n i s m s o i ti si m p o r t a n tt os t u d yh o wt o a l l o c a t et h el i m i t e dr e s o u r c cr a t i o n a l l yf o rd i f f e r e n ta p p l i c a t i o n sa n di m p r o v e t h eu t i l i z a t l o ft h er c s o u r c e s r e c e n t l y ，t h er e s e a r c ho nn e t w o r k r e s o u r c ea l l o c a t i o nb a s e d0 nm l c f o e 。 n o m i ct h e o r vb r i n g su san e wi d e a , w h i c hw o u ! dh e l pt h es e r v i c ep r o v i d e m a k ep r o p e 。 p r i c i n g 、 t h eg a m et h e o r yi sa ni m p o r t a n tb r a n c ho fm i c r o e c o n o m i c b yt h ei n t r o d u c t i o n o f g a m et h e o f ya p p f o a c h e s ，n e t w o r k u s e r sc a ni n d e p e n d e n t l yo p t i m i z et h e i ru t i l i t yf u n c t i o n s a n da p p r o a c ht h ep a r e t oo p t i m i z a t i o no fr e s o u r c ea l l o c a t i o n i nt h e f i r s tp l a c e ，w ef o r m u l a t e am o d e lo fn e t w o r kr e s o u r c ea l l o c a t i o ni nn o n c o o p e r a t i v eg a m e ，g i v i n g ac h a r a c t e r i z a t l o n 0 fn a s he q u i l i b r i u ma n dp a r e t oo p t i m i z a t i o n w ee x p o u n dt h e p m pm o d e l ，p u t t i n g e m p h a s i so nt h ee q u i l i b r i u ma n d t h ee f f e c to fp r i c i n gm e c h a n i s mt h a tw e r en o td i s c u s s e dm f o 册e rr e f e f e n c e f o u n d e do na b o v ea n a l y s i s ，n e t w o r k s i m u l a t i o nu n d e rn se n v i r o n m e n ti s c o n d u c t e dt oe v a l u a t ep e r f o r m a n c e so fp m p ： s e c o n d l y w ea n a l y z et h es o c a l l e dp a r i sm e t r op r i c i n g s c h e m e ，w h i c hs e p a a t e st h e n e t w o r ki n t od i f f e r e n ta n di n d e p e n d e n ts u bn e t w o r k s ，e a c hb e h a v i n ge q u i v a l e n t l y ，e x c e p t t h a tt h e yc h a r g et h e i rc u s t o m e r sa t d i f f e r e n tr a t e s i no u rm o d e l ，e a c hs u bn e 细o f k1 ； r e p r e s e n t e db yas i n g l eb o t t l e n e c kq u e u e ，a n dt h ec u s t o m e r s ( d a t ap a c k e t s ) c h o o s e t h e 盯s u b n e t 、o r kt a k i n gi n t oa c c o u n tn o to n l yt h ep r i c e s ，b u ta l s o t h ee x p e c t e dd e l a y ，w h l c hl s s u p p o s e dt oh a v ea ne c o n o m i ci m p a c t w eo b t a i ns o m e n e c e s s a r ya n d s u f f i c i e n tc o n d i l i o n s f o r t h es t a b i l i t yo ft h es y s t e ma n do p t i m i z a t i o no fs e r v i c ep r o v i d e r ；w ea n a l y z et h ep r o b j e m o fm a x i m i z i n gt h en e t w o r kr e v e n u ea n dc o m p a r ei tw i t ht h ec a s eo fa s i n g l en e t 、o r ka n d ，誉j 东北大学硕士学位论文 a b s t r a c t p r e s e n tam u l t i p l i c a t i o ne x t e n s i o no ft h e m o d e l n u m e r i c a lr e s u l t si l l u s t r a t i n gs o m ek e y a s p e c t so ft h es y s t e ma r ep r o v i d e dt h r o u g h o u tt h ep a p e r ， f i n a l l y ，t h er e s e a r c hw o r ki nt h i st h e s i si sc o n c l u d e d ，a n dt h eo t h e rp r o b l e m s i np r i c i n g t h en e t w o r k sa r ea n a l y z e da n dt h ei n t e r e s t e dd i r e c t i o n si nt h ef u t u r ea r ed e s c r i b e d k e yw o r d s ：c o n g e s t i o n ；c o n t r o l ；g a m et h e o r y ；n a s he q u i l i b r i u m ；c o n g e s t i o np r i c i n g ； p a r i sm e t r op r i c i n g 摹j ， ，童0 0 东北大学硕士学位论文目录 目录 声明。i 摘要i i a b s l c t i i i 第一章绪论1 1 1 拥塞的概念和成因l 1 2 拥塞控制类型2 1 3 拥塞的控制方法4 1 4 网络模型：。5 1 5 本文主要工作。8 第二章对策论及网络n a s h 均衡。9 2 1 对策论的引入9 2 2 对策论的研究状况及发展。l l 2 3 网络拥塞的n a s h 均衡1 3 2 4 价格激励机制1 6 2 5 囚徒困境1 9 第三章基于p m p 的网络拥塞计费机制2 1 3 1 网络拥塞计费机制。2 l 3 2 基于p m p 的拥塞计费机制。2 3 3 2 1p m p 机制2 3 3 2 2p m p 机制的n a s h 均衡2 5 3 2 3p m p 的计费机制2 7 3 2 4 仿真结果2 8 3 3 本章小结2 3 8 第四章基于数学模型的p m p 定价机制。3 3 4 1 p m p 机帛0 3 3 4 2 考虑延时的p m p 的数学模型3 4 4 2 1 模型的描述3 4 4 2 2 稳定状态的存在性与唯一性3 5 4 2 3 优化问题3 7 4 3 数值结果分析。3 8 东北大学硕士学位论文目录 4 3 1 平衡区域。3 受 4 3 。2 总的时廷一4 i 4 4 最大收益的敏感性。钇 4 4 ：l 带宽分配的敏感性4 2 4 4 2 用户时延的敏感性4 5 4 5 比较分析：一。4 6 4 6 不同时延的平衡点4 8 4 7 本章小结。4 9 第五章结论与展望5l 参考文献5 3 致谢5 7 n ， 蟾， j 东北大学硕士学位论文第一章绪论 第一章绪论弟一旱珀。v 匕 i n t e m e t 自出现以来得到了蓬勃发展，近年来更以惊人的速度增长，现有的带宽 总难能完全满足用户的要求。随着计算机和通信技术的发展，用户数量激增，大量 新的业务和应用也蓬勃兴起，导致拥塞问题亦越来越严重。面对业务q o s ( q u a l i t yo f s e r v i c e ) 保证要求的日益高涨和超高速网络强劲的发展势头，拥塞控制在网络流量管 理中的作用显得尤为重要。因为很难想象一个时常发生拥塞，并可能导致拥塞崩溃 的网络能为用户提供良好的服务；超高速网络犹如繁忙的高速公路，如果没有合理 的交通疏导规则，局部的堵塞很可能酿成级联性的事故，进而导致系统瘫痪。现有 的拥塞控制协议已经远远无法满足当前与未来的需要。 1 1 拥塞的概念和成因 拥塞是一种过载的网络状态，此时用户对网络资源( 包括链路带宽、存储空间 和处理器处理能力等) 的需求超过了其固有的容量。拥塞导致的直接结果是分组丢 失率提高，端到端的时延加大，甚至有可能使整个系统发生崩溃。当通信量增加非 常快时，几乎没有分组能够送达，网络会完全瘫痪。 造成网络拥塞有很多因素【1 1 队列长度不够会造成分组丢失，这在一定程度上可 以通过增加内存来解决，但如果内存过大，当分组到达队列前面时已经超时，则副 本就会重发，所有这些分组会悉数转发到下一个路由器，从而增加了通往目的地所 有线路的载荷。 处理器速度慢也能导致网络拥塞。如果路由器的c p u 速度太慢以至于不能处 理诸如缓冲区排队和更新表等日常工作，那么即使有多余的线路容量，也可能使队 列饱和。 同样，低带宽线路以及网络业务的爆炸式增长，对网络资源的总需求已大大超 过了供给( 特别是在接入网和边缘网中) ，因此企图通过在网络规划阶段为所有业 务提供足够的资源是不现实的，而必须通过适当的拥塞控制策略来限制用户对网络 资源的过度使用。 东北大学硕士学位论文 第一章绪论 这里简单说明一下拥塞控制与流量控制舷区别。流量控制只与某发送者和某接 收者之间饷点到臻通信量有关，它的任务是确保发送者不能以高于接收者所能承受 的速率传输数据j 流量控制几乎总是涉及接收者，接收者要向发送者送回拐一端情 况的直接反馈：与之不同的是，拥塞控制必须确保通信子网能传输待传送的数据， 是全局性构问凰涉及到所有将导致酎弱通信子瞬负荷能力的因荣_ ，二者的联系在 予，有些拥塞控制算法在网络出现问题时，也要向源端发送反馈消息以降低发送速 度，这也是二者容易混淆的原因所在。 拥塞控制的主要目标是控制进入网络的数据流量，保证通信网络不会被用户发 送的数据流阻塞，并合理的使用瓶颈资源。拥塞控制可以在网络坍议的各个层次上 实施。由于数据链路层靠近拥塞的发生氘所以在数据链路层进行控制可以快速的 对拥塞做出反应，但它只能对短期的拥塞现象进行控制。一般来说，不同网络层次 中的控制机制具有不同的目标，拥塞现象持续的时间越长，实现控制的层次也应该 越高。所以，拥塞控制主要在网络层和传输层实现。 1 2 拥塞控制类型 从控制论的角度可以把拥塞解决方案分成开环和闭环两类 2 1 。开环控制( 又称预 防式控锖d 的解决方案致力于通过良好的设计来避免问题的出珊，在做出何时接受 新的通信、何时丢弃分组以及丢弃哪些分组等决定时并不考虑当前的网络的状况。 其基本原理是根据已有的网络，将设计好的控制策略加入网络中吟且该策略确保网 络不会发生拥塞，而网络一旦运行起来，就不再采取措施。这类控制机错较适合用 于音频和活动图像业务。例如，如果两个终端允许一个最小的数据率通过，则发送 端可以在不考虑其他进程的通信量的情况下，以这个速度来发送数据而不回发生数 据丢失。如果发送端有剩余的链路容量和空阕的可用缓存，则网络资源设有得到充 分的利厝，达不至最大效用 闭环控制是建立在反馈环路的概念之上，它需要监视系统何时何地发生拥塞并 将信息传送蓟各行动节点以调整操作来解决问题。在闭环控制中，为了防止网络拥 塞，达到较高的链路容量的效用，需要在通信进程的发送器和接收器之问建立一个 适当的握手算法。由于大的链路传播时延导致反馈信息的有效性减低，所以在发送 ，：憎1 东北大学硕士学位论文 第一章绪论 端需要一个额外的预测机制来发布控制消息避免缓存溢出，但这也增加了协议操作 的代价。 反映拥塞状况的信息包括：因减少缓冲区而丢失分组的比例，平均队列长度， 超时和重发的分组数，平均分组延迟及标准方差延迟等。反馈拥塞信息可以由检测 到拥塞的路由器向信流源发送分组，或者填充每个分组预先设定的拥塞标记位，也 可以由主机或路由器定期发送证实分组来显示地询问拥塞状况，在隐式算法中，源 端通过局部观察比如确认返回时间来判断拥塞状况。 从实施类型上，拥塞控制可以分为基于窗口( w i n d o w - b a s e d ) 和基于速率限a t e d b a s e d ) 两种。前者直接限制网络中的数据量以控制通信进程的数据流，而后者则限制 网络数据的传输率来控制数据流。 基于窗口的拥塞控制机制的控制环视端到端的或者是逐跳的。端到端的窗口机 制实现起来比较简单。但是路径上中间结点的缓存阻塞会导致较大的端到端的信源 传输时延，因此需降低信源返回到源端的速率，从而也降低了新到达网络中数据的 速率。逐跳的窗口机制以信元处理为代价来降低节点的缓存需求，使一次会晤的所 有包均匀分布在从源端到目的端的各节点上，这样就可以避免在某节点处发生拥 塞，而且可以更快的对网络拥塞做出反应。 但是，由于一些音频、视频等数据服务要求对数据包的传输时延和数据率进行譬 控制，窗口机制已不再适合。这是因为基于窗口的机制不能确保一个最小的通信 率，而且固有的开始发送停止发送数据模式会产生通信量的波动，同时还会影 响传输时延的变化。因此需要基于速率的拥塞控制。 基于速率的拥塞控制可以使开环的也可以是闭环的。在基于速率的拥塞控制机 制中，每次会晤分配一个数据率，该速率与本次会晤对整个网络的需求相匹配。这 个速率还受本次会晤的q o s 需求的限制。 一个严格的基于速率的开环拥塞控制给一次通信分配每秒传送g 个包的速率 ( 即允许每l 幻最多传送一个数据包) 。但是，由于网络采用时分复用技术，而且当 通信是突发时在发送端引入较大的数据包滞留，而在接受端留下过多的未使用的带 宽。这可以借助一个漏桶整形器加以改善，基于速率的拥塞控制机制适合高速数据 网。 东北大学硕士学位论文第一章绪论 此外，从推断网络状态的反馈信息韵类型上p 拥塞控制机制可分为显式的 ( e x p l i c i t ) 和隐式i 约( i m p l i c i t ) 从实施控制的位置，拥塞控制机制可以分为端到端的( e n d - t o - c n d ) 和基于路由器 的q 腑b a 啦 1 3 拥塞的控制方法 根据算法实现的物理位置，可以将拥塞控制算法分为两大类：源算法( s o u r c e a l g o r i t h m ) 和链路算法( l i n ka l g o r i t h m ) 1 2 1 。源算法工作在主机( e n dh o 蛐网络边缘 ( n e t w o r k - e d g e ) 设备上，作用是根据反馈信息调整发送速率。链路算法工作在网络设 备( 如路由器和交换机) 上，作用是检测子网传输路径端口上转发队列韵累积，产 生拥塞豹反馈信息。 源算法在拥塞控制的源算法方面，大量的工作集中在对t c p 协议的研究上。在 t c p 协议申采用了很多新的算法，包括慢启动( s l o ws t a r t ) 、拥塞避免( c o n g e s t i o n ? a v o i d a n c e ) 、快速重传( f a s t r e t r a n s m i o 和快速恢复( f a s tr e c o v e r y ) 、选择性应答 ( s a c k ) 等，大大提高了网络传输的性能。 目前，源算法方面的研究热点包括； ( 1 ) 对“慢启动”过程的改进。对于短数据的传输来讲，。慢启动一阶段更为重 要。对于长数据的传输来讲，“拥塞避免 阶段更为重要由于目前ti n 钯m e t 上的一 个主要应用h m 的大部分数据是短数据，所以在改善甜慢启动阶段的性能以减 小响应时间方面开展了很多研究工作。 ( 2 ) 基于速率的控制策略。在t c p 中使用的窗口控制策略本身机制存在一定的缺 陷，如：容易导致突发报文0 3 u r s t ) 的出现；速率受到窗口大小的限制、一个窗口内 多个报文的丢失不容易恢复等针对这些问题，一些研究者提出：了、r a t e - b a s e d p a c i n g ( p a p ) 的概念r 将基于窗口的控制和基于速率的控制结合起来。从直观上考 虑，这样的方案可以克服窗口机制的弊病，但是在拥塞发生时，r b p 可能会导致多 个连接同时丢失报文，从而出现。全局同步( o l o b a ts y n c h r o n i z a t i o n ) 修的现象，严重 降低网络的吞吐量的准确性和“乱序报文( o u t - o f - o r d e rp k m 盼出现都会影响 t c p 做出正确的判断。可以通过在应答报文中增加特殊的信息来解决这个问题 啊 东北大学硕士学位论文 第一章绪论 ( 5 ) “显式拥塞通知( e x p l i c i tc o n g e s t i o nn o t i f i c a t i o n ) 一。当拥塞发生时，网关通 过在报文中设定标志位通知端系统，而不等待发送方的时钟超时。这改变了原来 t c p 依赖报文丢失来判断拥塞发生的方法。 ( 6 ) “t c p 友好f f c ef r i e n d l y ) 的拥塞控制。“t c p 友好 ，定义为长时间的吞 吐量不超过相同条件下t c p 连接的吞吐量。“t c p 友好 的拥塞控制属于基于速率 的控制，速率的计算建立在t c p 吞吐量模型的基础上。针对特殊网络环境的拥塞控 制，包括无线链路、卫星链路和“非对称( a s y m m e t r i c ) 链路上t c p 的拥塞控制。 这些链路的特点为高延迟、高丢失率、两方向传输链路的性能不相同，在这些链路 上使用的拥塞控制算法需要增加特殊的考虑。 链路算法的研究目前集中在“主动队列管理( a c t i v eq u e u em a n a g e m e n t , a q m ) 算法方面和传统的“队尾丢弃( d r o pt a i l ) 的比较ja q m 在网络设备的缓冲溢出之 前就丢弃或标记报文。a q m 的主要优点是减少网关的报文丢失；减少报文通过网关 的延迟；避免t c p 全局同步。a q m 的重要代表是r e d ( r a n d o me a r l yd e t e c t i o n ) 1 3 1 。 研究表明r e d 比d r o pt a i l 具有更好的性能。随后涌现一批r e d 改进算法： s i z e d ，a r e d ，d r e d ，b l u e ，c h o k e 等。 近年来，非线性规划理论、系统控制理论和优化控制理论被引入到拥塞控制的 研究中来，一些研究者尝试使用严格的数学模型来描述由端系统和网关共同组成的 系统，例如h o l l o t 等人利用小信号分析的方法【4 】，在工作点处线性化，m i s r a 给出的 t c p a c m 控制模型，并根据这个模型，理论分析了r e d 稳定性，推动了拥塞控制 的研究。一些新的a q m 算法，如r e m ( r a n d o me x p o n e n t i a lm a r k i n g ) ，v q ( v i r t u a l q u e u e ) ，p i ，p d ，p ，以及适用于大时滞系统的内模补偿算法i s 等不断涌现，但是它 们缺乏在实际网络中的测试。 1 4 网络模型 一 拥塞控制是当今网络研究领域的热点问题。本文第四章中的论述主要针对因特 网的拥塞控制，建立网络模型、策略分析与改进及数据分析结果。 因特网拥塞控制最初的形式就是t c p 协议的流量控制，对不同的t c p 版本的流 量控制算法研究一直是拥塞控制的重要内容。 东北大学硕士学位论文 第一章绪论 在拥塞控制研究中网络模型的作用是分析网络性能t ，预测流量变化趋势特剐是 拥塞的发生、为可能采取的拥塞反馈信号和拥塞响应手段提供理论依据。可以从多 种角度来对网络模型进行分类。 从模型考察的状态变量上，可分为流量模型和机理模型，网络模型中最主要盼 状态变量就是流量，流量模型就是仅以网络流量为状态变量，而将其它网络参数的3 影响都聚合为过程噪声的一种模蝥一般来说通甩性较好，但准确性稍差，而机理 模型一般是针对各种具体的协议、网络类型等场景而建立的，包含其它网络参数作 为模型状态变量，具有较强的针对性 从网络状态来分，有平衡态( 稳定) 的网络模型和瞬态( 动态) 的网络模型， 当前的机理模型大部分都是平衡态的模型 从考察的时间尺度上，可分为宏观( 大尺度，小时级以上) 模型和微观模型， 拥塞控制研究应该与小时间尺度的微观模型关系更紧密些。 根据对状态变量的时间连续性处理上，可分为连续模型、离散模型和混杂系统 模型。 常见盼是流量模型有传统的基于短相关假设的p o i s s o n 。过程模型、伯努利到达过 程模型，自回归( a r ) 模型：、自回归滑动平均( a r m a ) 模型、自回：归积分滑动平均 ( a r i m a ，a u t or e g r e s s i v ei n t e g r a t e dm o v i n ga v e r a g e ) 模骛和基于长相关的模型， 如分形高斯噪声模型、分形a r i m a 模型、分形布朗运动模型等等。 以上这几种模型都属于平衡态的模型，而对于t c p 协议来说，研究它的慢启动 过程和快速恢复过程中的动态 6 1 ，对拥塞控制也是很有意义的j 实际的网络流量是以分组为单位的，与之相应的就是离散模型，而连续模型都 是在相比离散模型较大的时间尺度上对网络流量做了近似处理，所以离散模型更精 确，而且可以描述网络演化中的动态( 因为它的时阿尺度足够小) ，但显然所需的 计算消耗也较大。连续模型韵优点则是便于分析网络的状态参数对网络系统的性能 的影响。混杂模型特别适合于拥塞控制算法或协议的分析和设计。在计算复杂性 上，与基于离散模型的n s 仿真相比较，混杂模型也以相对快得多的速度体现出优 势。混杂系统模型填补了离散模型和连续模型之间盼空白，是一类很有前景的网络 模型。 j f 0 东北大学硕士学位论文 第一章绪垒 l 一 总结以上拥塞控制方法和网络模型的建立，可以得出以下结论： ( 1 ) 网络模型的研究是拥塞控制的基础工作，仍有待深入。在机理模型方面，对 t c p 协议流的模型已经有比较深入的研究，而u d p 协议流相对简单，应该是开环的 随机过程模型。 ( 2 ) 由于单纯的源端算法是无法解决公平性问题的( 因为涉及各个流的不同状 态，而在每个源端是看不到其它源端的状态的) ，所以目前新的源端算法都有采取 分布式形式的趋势，但即便是分布式算法，对降低各路由的延迟和丢包率能起的作 用也有限。 ( 3 ) a q m 算法，是目前拥塞控制研究中的热点，但是很多研究仅仅是单纯引入 控制理论的现有方法在此领域加以运用，而不是运用控制论、系统化的思想来研究 闯题。 ( 4 ) 公平性问题即不同流之间的协调控制问题是a q m 研究的一个重点和难点。 在公平性上a q m 比源端算法有本质的优越性，比调度算法又有本质的劣势性，这种 中问状态使得a q m 的公平性研究有很大的研究潜力。 ( 5 ) 网络运行状况的检测和性能评价缺乏系统理论，网络仿真研究缺乏统一的规 范和评价标准，都给拥塞控制研究的验证、比较和网络模型研究带来了很大的障 碍。 、 综合以上分析，现有网络面临着资源相对短缺而用户对q o s 要求越来越高等问 题，这就要求运营商采取有效的网络控制机制以提高现有资源的使用效率，为用户 提供尽可能满意的服务。传统的非经济的资源分配方法，如调度算法，没有考虑用 户愿付代价与用户满意度等因素对资源分配的影响，不能充分利用资源，做到物尽 其用。 为了解决这些问题，近年来研究者提出基于微观经济学方法的网络资源分配思 路，该方法具有以下优点： ( 1 ) 价格机制影响供需变化，根据供需关系进行价格调节，使用户在价格和性能 上寻求最佳结合点，最终达到合理使用资源，优化资源分配的目的。 ( 2 ) 价格机制体现服务质量的差别，选择不同价格的用户获得不同级别的服务， 从而使系统能够很好地提供区分服务。 东北大学硕士学位论文 第一章绪论 ( 3 ) 价格激励机制固有的分布性与网络资源的分布性相适应，为网络资源的管理 和控制提供有效手段。 ( 4 ) 经济模型提出合理的付费机截，为网络传输的商业运作提供基础。 1 5 本文主要工作 本文研究了基于p m p 机制的计算机网络价格控制的若干问题。 首先，第二章介绍了对策论的n a s l i 均衡及其理论模型及相关定理，明确了本文 所使用的工具和方法。 网络管理者所制定的价格以及用户的使用速率都关系到用户的效益，也影响着网 络的拥塞问题。因此，对策论中的策略是解决这些问题的重要手段之一。基于这种 观点在第三章讨论了基于p m p 的拥塞计费机制，完善了其理论上的n a s h 均衡模 型，给出了价格激励机制策略，并利用p o i s s o n 分布模型进行了验证。利用n s 软件 仿真，其结果表明用这种方法使用户合理地利用网络资源，提高了网络资源的利用 率，对于网络和用户双方都具有重要的意义。 第四章首先基于p m p 划分子网，并给出网络的模型，根据用户带宽需求和用户 期望的服务质量和时延及可用带宽资源的状况，以用户满意度最佳和系统效率最佳 为目标，计算出带宽资源的网络效用价格，讨论了该。p m p 模型在稳定状态下的解的 存在性和唯一性，并根据数值例子进行分析，用图表说明了网络的收益随各个参数 的变化趋势。然后比较了网络在没有划分子网的情况和基于p m p 模型的情况，并分 析了不同类型的数据包产生不同延时的情况，给出了解存在的必要条件 最后，结论与展望部分总结了前面所做的工作，并对网络价格控制中存在的其 他问题进行了简单的分析，以及对未来可做的工作方向的阐述。 8 - q j f ； 东北大学硕士学位论文第二章对策论及网络纳什均衡 第二章对策论及网络纳什均衡 2 1 对策论的引入 拥塞的实质是用户对网络资源的需求超过了网络的供给，因此拥塞控制必须以 资源的合理分配为基础。 现有的资源分配方式是由网络控制端根据用户需求，以某种先验目标确定资源 分配准则，其优化依赖于所有用户的信息即中心化控制方式忉。而i n t e r a c t 用户和用 户资源的分散性，网络规模的庞大都使得中心化控制非常困难；随着对网络资源需 求的增长和业务的多元化，现有的平坦计费由于没有考虑用户的不同服务质量需 求，无法利用价格杠杆形成正确的价格激励，因而可能加重资源的滥用和网络拥 塞。 非中心化控制的方法不存在集中的管理者，网络端用户提供有关费用协商的规 范( 如市场、价格) ，它随用户的需求而变化，资源分配和计费借此规范相互关 联。非中心化控制为网络资源管理和计费提供了分布式处理的可能，大大降低了在 中心化控制下基于使用计费的工程成本，从而可能达到资源利用的最佳效率。 对策论模型为网络的非中心化控制提供一个具体的分析框架，它假定用户间存 在对网络的竞争，这种竞争相当于经济学中的利益冲突，网络资源分配的目的是进 行用户问的利益协调。 在对策论模型下，通常假定用户和资源供应商独立优化各自的评研究价函数， 从而使资源分配达到某一特定的对策论均衡解。通过研究均衡解在工程上的含义， 可以对资源的利用效率给出评价，也为在用户不同的q o s 要求下如何避免网络拥塞 提供了一种新的评价准则阴。 对策论( g a m et h e o r y ) 又称博弈论，被认为是上世纪应用数学最重要的理论成果 之一，它是研究不同的主体在“策略相互依存( s t r a t e g i ci n t e r d e p e n d e n c e ) 情形下相 互作用的科学【引。在对策论的模型里，每个主体的收益不仅取决于它自身的行为，而 且也取决于其他人的行为。进而言之，个人所采取的最优策略取决于他对其他人所 东北大学硕士学位论文 第二章对策论及网络纳什均衡 采取的策略的预期；对策论被公认为研究不同主体决策互相影喻，行先交互的最佳 数学工具。 事实上，对策论数学模型的提出已有近六十年的历史，从最初的二人零和对策 到：目前已发展完备的非合作对策c 9 l ；对策论思想应用予经济和市场决策领域已经取得 广泛的成功，而网络用户恰恰也可以被视为单个的经济实俸，其追求效益最大化行 为韵决策过程，系统在局中人的作用下是否存在均衡解或稳定解，以及居中人采取 竞争与合作等不同策略对系统均衡解的影响，都是对策论的关注点。 首先，对策论分析方法假定用户不受中心化控制算法的限制，可以独立优化其 关于资源利用的评价函数；而且用户具有某种“自私”性，它只考虑自己的资源利 用效率而不考虑其他用户。 其次，对策论方法关心的是，在用户独立优化其评价函数时，资源提供者采用 何种策略处理用户间共享资源的公平性问题，同时达蓟资源分配的动态平衡。最 后，对策论方法还要设法回答系统由任一初始条件向均衡解移动的激励机制问题， 即非中心化控制具有多大的鲁棒性。 对策论方法只提供一种保证用户通过协议方式获取资源的机制，不同用户可以 合作，也可以竞争。在考虑用户问资源利用的公平性时，也应注意用户在传输协商 阶段会自由选择对自己有利的策略，它与其他用户的合作收益不能低于自己单独行 动在最坏情况下的收益。在p a r c t o 有效的均衡点处，任何用户收益的增加都将导致 其他用户收益的降低。 对策论在经济学领域的应用非常广泛也十分成熟，而市场机制固有的分布性与 网络资源的分布性也是相适应的；而且，相当于经济学中的居中人来说，网络用户 更符合“对策的参与者是理性的一这一对策论的基础性假设，因此，完全可以运甩 经济学里的对策论理论来研究网络工程，把用户看作购买商品的顾客，把网络资源 看作商品，通过合理的价格计费机制阙节供求关系，一方面为网络优化提供依据； 另一方面能够简化网络控制功能，实现有效的分布式资源控制和管理，这也是网络 资源管理的发展方向。 在网络资源分配和拥塞控帛l j 中引入对策论的理论方法涵盖了计算机网络与经 济学的交叉领域，其通过指定竞争规则来影响用户对资源附竞争的。市场化模 东北大学硕士学位论文第二章对策论及网络纳什均衡 式 ，更真实地反映了用户的利益协调，从系统均衡的角度实现了经济效益和工程 效益的评价，是一个新颖而又有前途的研究方向。 2 2 对策论的研究状况及发展 将对策论的方法引入网络工程，是一种全新的角度，相对于网络研究的其他热 点问题来说，仍处于起步阶段。在网络设计与规划阶段，研究用户在非合作环境下 的最优资源分配问题，比如增加新链路带宽产生的b r a e s s 悖论问题【1 0 1 。网络运行阶段 的选路问题。如应用二人零和理论使网络平均迟延最小的路由选择问题f l l l ；通过网 络管理者干预模型引导整个网络趋向最优的s t k e l b e 略激励问题【1 2 1 。在链路接纳控 制和拥塞控制方面，以效用论和n a s h 均衡为理论基础，实现资源的合理调度；特别 是结合经济学的价格模型实现资源的计费管理，利用供求相互作用机制价格调节机 制及对策论中的主从( s t a c k e l b e r g ) 激励策略【1 3 1 等微观经济学理论寻找用户满意度和网 络性能的最佳结合点，正逐渐成为相关研究的重点。 将对策论的方法用于网络资源分配特别是拥塞控制，国外的研究相对起步较 早，也去得了一些有重要意义的成果，涌现出m a c k i e - m a s o n ，s h e n k e r , o d l y z k o 和 k e l l y 等代表性的学者。但总体说来，这方面的研究只有很短的时间，还需要大量的 理论和实践工作才能逐步趋向完善；而对策论在国内开始受到重视也只是近几年的 事情，在这方面无论作为一般的理论分析还是提出具体实旌方案，都是一种有价值 的探索。 最早的对策思想可以追溯到几千年前中国古代的