（计算机应用技术专业论文）基于博弈论的可生存网络资源管理研究.pdf

a b s t r a c t 摘要 网络可生存性是网络基本能力的保证，是网络提供服务质量( q o s ) 的前提和 保证。随着网络业务流量日益增大以及网络业务类型多样化，研究网络存在性 问题成为目前网络研究的一个热点，也为构建下一代互联网奠定基础。 网络可生存性通常是以网络连通性以及网络性能，业务容量等性能来度量， 影响网络可生存性因素很多，网络可生存性研究方面涉及问题也比较多。本文 研究了影响互联网可生存性的关键部件路由器，分析了其网络资源管理方法和 现存技术对网络可生存性问题的影响，提出了公平有效的网络资源分配方法， 避免或控制了网络拥塞现象发生，从而提高网络可存生性的研究思路a 本文主要从路由器队列管理技术和路由选择技术两个方面，运用博弈论思 想，研究路由器网络资源管理机制，提出了基于路由器的网络资源公平有效分 配方案，从而提高网络可生存性。 具体来说，本文主要研究内容和贡献如下： 1 研究了网络生存性的相关问题，分析了影响网络可生存性的关键部件， 表明保障这些关键部件正常、有效地工作是网络可生存性的基本保证。在此研 究基础上，表明针对网络关键部件路由器，寻求其公平有效地网络资源分配方 法，避免或控制网络拥塞现象发生，是保证和提高网络可生存性的关键所在。 2 介绍了博弈论相关概念和知识，着重介绍了博弈问题的解，即n a s h 均 衡存在条件以及最优性等相关问题，分析了博弈论在路由器资源管理中的应用 情况以及相关研究状况，为本文提出的解决方案奠定了基础。 3 介绍了目前路由器资源管理的方案和思路，并针对其中的路由器队列管 理方法和路由选择技术进行了分析和研究：基于博弈论思想，提出了将路由器 队列管理看作是路由器网络资源管理过程的概念，构建了路由器队列管理博弈 模型，确定了该博弈问题的n a s h 均衡条件；运用上述博弈模型的n a s h 均衡条 件，从理论上证明了目前典型路由器队列管理技术的非均衡性，并表明这种非 均衡性将导致网络资源分配的不公平。 i i a b s t r a c t 4 在实时业务和非实时业务等多种业务类型共存的网络环境下，研究了路 由器网络资源的公平性分配问题，提出了基于博弈论思想的路由器实时队列管 理新方法，该方法提高了网络资源分配的公平性，有效控制和避免网络中拥塞 现象，最终提高了网络可生存性。 文中首先介绍了基于博弈论思想的网络资源管理方法在路由器队列管理中 的研究状况：介绍了路由器队列管理博弈模型，研究了基于博弈论的路由器队 列管理方法的均衡性条件以及任务流条件；其次，研究了路由器队列管理中的 两种关键技术，即丢弃算法和调度算法，提出了基于博弈论路由器丢弃算法和 调度算法。另外，针对目前网络，尤其是下代网络中多媒体等实时任务广泛 应用情况，研究了路由器排队算法，提出了种适合实时特性路由器的排队算 法；再次，在结合上述路由器队列管理关键技术基础上，提出了一种基于博弈 论思想的路由器实时队列管理方法：最后，构建了算法实例，设计了实验模型 并用实验方法仿真了算法结果，同时对算法结果进行了分析和比较。 5 分析了路由器路由选择技术对影响网络可生存性的影响，表明了路由器 将业务均衡地转发网络各个路径上，能避免大量业务集中在最短路径或处理能 力强的路径上，导致网络拥塞现象，影响网络可生存性。文中针对i p v 6 协议中 任意播路由中的均衡路由问题，提出了基于博弈论思想的优化路由算法，即均 衡的路由算法，从路由角度提高网络连通性和效率，保证网络可存生性。 文中首先介绍了网络路由均衡性选择的研究状况：介绍了合作参与者问的 博弈理论；其次，构建了合作参与者间的博弈模型，提出了基于合作博弈的均 衡路由算法，并用实验方法仿真了算法结果；再次，在合作博弈模型基础上， 进而研究了实际网络路由状况，构建了非合作参与者间的博弈模型，提出了一 基于非合作博弈的均衡路由算法，并用实验方法仿真了算法结果。 关键词：网络可生存性路由器合作博弈非合作博弈n a s h 均衡 a b s t r a c t a b s t r a c t i n t e m e ts u r v i v a b i l i t ye n s u r e st h ei n t e m e tb a s i c a la b i l i t y ，a n di ti st h ep r e m i s e a n dg u a r a n t e eo fq o s w i t ht h ei n c r e a s i n go ft r a f f i ca n dm a n yk i n d so ft r a f f i c ，t h e r e s e a r c hi ni n t e m e ts u r v i v a b i l i t yi sb e c o m i n gaf o c u sp r o b l e ma tp r e s e n t i n t e r a c t s u r v i v a b i l i t yi sa l s oa b a s i cp r o b l e mi nt h en e x tg e n e r a t i o ni n t e m e t ( n g n ) g e n e r a l l y ，i n t e r n e ts u r v i v a b i l i t y i sm e a s u r e db yc o n n e c t i o n , c a p a b i l i t ya n d t r a f 矗ce f f i c i e n c y i n t e m e ts u r v i v a b i l i t yi sa f f e c t e db ym a n yf a c t o r sa n dt h e r ea l e m a n yq u e s t i o n si n v o l v e di nt h er e s e a r c h i nt h i sp a p e r ，t h er o u t e rw h i c hi sam a j o r c o m p o n e n t sa f f e c t i n gt h e i n t e m e ts u r v i v a b i l i t yi ss t u d i e d ，t h ei n t e r a c tr e s o u r c e m a n a g e m e n ta n dt h ei n f l u e n c eo fc u r r e n tt e c h n o l o g yt o i n t e r n e ts u r v i v a b i l i t yi s a n a l y s e d ，af a i ra n de f f e c t i v em e t h o dt od i s t r i b u t et h ei n t e r n e tr e s o u r c ei sp r e s e n t e d t h i si n v e s t i g a t i o nc a l la v o i do rc o n t r o lt h ei n t e m e n tc o n g e s t i o n , a n di m p r o v et h e i n t e m e ts u r v i v a b i l i t y t h em a i nc o n t e n to f t h i sp a p e ri s ：d i s c u s s e st h em a n a g e m e n tm e c h a n i s mo f t h e r o u t e ri n t e m e tr e s o u r c e ，p r e s e n t saf a i ra n de f f e c t i v em e t h o do nt h er o u t e rt o d i s t r i b u t et h ei n t e m e tr e s o u r c ew i t hg a m et h e o r yi nt w ow a y s ，t h a ti sr o u t e rq u e n e m a n a g e m e n t a n dr o u t e re l e c t i o nt e c h n o l o g y ，w h i c h i m p r o v e t h ei n t e r a c t s u r v i v a b i l i t y t h ei m p o r t m e mc o n t e n ta n dc o n t r i b u t i o ni sd e s c r i b e di nd e t a i la sf o l l o w ： 1 t h i sp a p e rd i s c u s s e st h er e l a t i v ep r o b l e mw i t hi n t e r a c ts u r v i v a b i l i t y ，a n a l y s e t h em a j o rp a r t sw h i c ha f f e c ti n t e r a c ts u r v i v a b i l i t y ，i n d i c a t e st h a tt h em a j o rp a r t s r u n n i n gn o r m a l l ya n de f f e c t i v e l yi st h eb a s i c a lg u a r a n t e eo fi n t e m e ts u r v i v a b i l i t y b a s e do nt h i si n v e s t i g a t i o n , t h ep a p e ri n d i c a t e st h a ti ti st h ek e yt oe n s u r ea n d i m p r o v e i n t e r a c ts u r v i v a b i l i t yo nt h er o u t e rt ol o o k i n gf o raf a i ra n de f f e c t i v em e t h o d t od i s t r i b u t et h ei n t e r a c tr e s o u r c e ，a v o i d i n go rc o n t r o l l i n gt h ei n t e m e n tc o n g e s t i o n 2 t h i sp a p e ri n t r o d u c e st h er e l a t i v ec o n c e p ta n dn a s ho ne m p h a s i so f t h eg a m e t h e o r y ，i n c l u d i n gt h er e l a t i v ep r o b l e mo f n a s he q u i l i b r i u ms u r v i v a lc o n d i t i o na n dt h e b e s ti n f o r m a t i o n i nt h i sp a p e r t h eg a m et h e o r ya p p l i a n c ea n dr e l a t i v er e s e a r c hs t a t u s a b s t r a c t i nr o u t e rr e s o u r c em a n a g e m e n ti sa n a l y s e d ，a n dt h eb a s i c a ls o l v i n gs c h e m eo ft h i s p a p e ri se s t a b l i s h e d 3 t h i sp a p e ri n t r o d u c e st h es c h e m eo fc u r r e n tr o u t e rr e s o u r c em a n a g e m e n t ， a n a l y s e st h er o u t e rq u e n em a n a g e m e n ta n dt h er o u t e rp a t hs e l e c t i o nt e c h n o l o g y u p t ot h e g a m et h e o r y ，t h i sp a p e rp r e s e n t s t h e c o n c e p tt h a tt h er o u t e rq u e u e m a n a g e m e n ti s c o n s i d e r e d 鹪ap r o c e s so fr o u t e ri n t e r n e tr e s o u r c em a n a g e m e n t b u i l d st h er o u t e rq u e n em a n a g e m e n tg a m em o d e l ，a n dc o n f o r m st h en a s h e q u i l i b r i u mc o n d i t i o no ft h eg a m e d u et ot h en a s he q u i l i b r i u mc o n d i t i o no ft h e g a m em o d e l ，t h eu n e q u i l i b r i u mo ft h ec u r r e n tt y p i c a lr o u t e rq u e n em a n a g e m e n t t e c h n o l o g yi sp r o v e di nt h e o r y ，a n dt h i si sc o n s i d e r e dt h a tw i l ll e a dt ou n f a i rr e s o u r c e d i s t r i b u t i o n 4 t h i sp a p e rd i s c u s s e st h ef a i rr o u t e ri n t e m e tr e s o u r c ed i s t r i b u t i o ni ni n t e m e t 硼出r e a lt i m et r a f i q ca n dn o n r e a it i m et r a 嚣c , a n dp r e s e n t st h en e wm e t h o do f r o u t e r q u e e nm a n a g e m e n tb a s e dt h eg a m et h e o r y t h i sm e t h o dc a ni m p r o v et h ef a i ri n t e r n e t r e s o u r c ed i s t r i b u t i o n , c o n t r o la n da v o i de f f e c t i v e l yi n t e m e tt r a f f i c ，a n di m p r o v et h e i n t e m e ts u r v i v a b i l i t yf i n a l l y f i r s t l y , t h i sp a p e ri n t r o d u c e st h er e s e a r c ho fi n t e m e tr e s o u r c em a n a g e m e n tb y g a m et h e o r yi nr o u t e rq u e n em a n a g e m e n t ，a n da l s oi n t r o d u c e st h er o u t e rq u e n e m a n a g e m e n tg a m et h e o r ym o d e l 。s t u d y s t h ee q u i l i b r i u mc o n d i t i o na n dt a s k c o n d i t i o no ft h er o u t e rq u e u em a n a g e m e n tw i t hg a m et h e o r y s e c o n d l y , t w o i m p o r t a n tt e c h n o l o g i e st h a ti st h ed r o pa n ds c h e d u l ea r i t h m e t i ci nt h er o u t e rq u e u e m a n a g e m e n ti sd i s c u s s e d ，a n dt h ed r o pa n ds c h e d u l ea r i t h m e t i cb yg a m et h e o r yi s p r e s e n t e d m o r e o v e r ，t h i sp a p e rp r e s e n t sar e a lt i m er o u t e rq u e n em e t h o df o ri n t e m e t w i t hr e a lt i m et r a f f i ca n dn o nr e a lt i m et r a f f i c t h i r d l y ，b a s e dt h er e s e a r c ho ft h e m a j o rt e c h n o l o g i e s ，ar e a lt i m er o u t e rq u e u ea r i t h m e t i cb a s e dg a m et h e o r yi s p r e s e n t e d a tl a s t ，t h i sa r i t h m e t i ca n dt h ee x p e r i m e n tm o d ea r eb u i l t ，t h i se x p e r i m e n t r e s u l ti sc o m p a r e dw i t ht h eo t h e rt y p i c a lm e t h o d s 5 i nt h i sp a p e r , t h ei n f l u e n c eo ft h er o u t e rp a t hs e l e c t i o nt ot h ei n t e m e t s u r v i v a b i l i t yi sa n a l y s e d ，a n dt h ec o n c l u s i o ni n d i c a t e st h a tt h ee q u i l i b r i u mr o u t e r p a t hs e l e c t i o nc a na v o i dm o r et r a f f i ci nt h es h o r t e s tp a t h ，w h i c hm a y l e a dt oi n t e r n e t c o n g e s t i o na n da f f e c t i n t e r u e ts u r v i v a b i l i t y t ot h ee q u i l i b r i u mr o u t e ri n i p v 6 a n y c a s t ，t h i sp a p e ro p t i m i z et h er o u t e ra r i t h m e t i c ，t h a ti sae q u i l i b r i u mr o u t e rc h o i c e a b s t r a c t v m e t h o d ，w h i c hc a ni m p r o v ei n t e m e tc o n n e c t i o na n de f f i c i e n c y ，e n $ n r et h ei n t e r n e s u r v i v a b i l i t y ， i nt h i sp a p e r , t h er e s e a r c ho ft h ee q u i l i b r i u mr o u t e rc h o i c ei si n t r o d u c e da n dt h e b a s i co ft h ec o o p e r a t i v ep l a y e rg a m et h e o r yi ss t u d e i df i r s t l y s e c o n d l y , t h eg a m e m o d e li sb u i l t ，ac o o p e r a t i v ep l a y e rg a m ea r i t h m e t i co nt h ee q u i l i b r i u mr o u t e ri s p r e s e n t e d ，a n dt h ee x p e r i m e mi n d i c a t e st h ep e r f o r m a n c eo ft h i sa r i t h m e t i c t h i r d l y , b a s e do nt h ec o o p e r a t i v ep l a y e rm o d e l ，t h ei n t e m e tr o u t e ri np r a c t i c ei ss t u d i e d ，a n o n c o o p e r a t i v ep l a y e rm o d e li sb u i l t a ne q u i l i b r i u mr o u t e rp a t hs e l e c t i o na r i t h m e t i c w i t ht h i sm o d e li sp r e s e n t e d ，a n dt h ee x p e r i m e n ti n d i c a t e st h ep e r f o r m a n c eo ft h i s a r i f l u n e f i c k e y w o r d ：i n t e r n e ts u r v i v a b i l i t y r o u t e r c o o p e r a t i v eg a m et h e o r y n o n c o o p e r a t i v eg a m et h e o r y n a s he q u i l i b r i u m 创新性( 或独创性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。+ 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：二脚 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本人签名：】& 妻必 导师签名： 晔 第一章绪论 第一章绪论 本章介绍了论文选题的背景和研究意义，分析了网络可生存性研究的必要 性以及影响网络可生存性的几个关键因素，说明了论文研究内容以及创新点， 最后，介绍了本文内容结构安排。 1 1 网络服务质量 计算机技术和通信技术的飞速发展，使得网络正以越来越快的速度进入到 工业、商业、教育和科研领域，进入到人们的日常生活中，深刻影响和改变着 人们的工作和生活方式。人们对网络的依赖性越来越强，如医疗、电力、电信 以及金融系统等都是依赖于网络系统而提供服务。 回顾网络发展过程，可知道互联网已经发展到所谓第三阶段，即下一代互 联网m g d 。n g i 将会成为世界上最大的商用网络，其特点是开放和高效，能够 提供对各种业务的综合支持，尤其提供对各种应用的不同服务质量保证。 总的来说，i n c r u e t 发展到今天，表现出两个重要特征； 1 网络流量不断增加 根据k g c o f f m a n 和a m o d l y z k o 估计，i n t e m e t 网络流量大约每年翻一番 ( 每年增长7 0 到1 5 0 ) 。 2 、网络传输业务类型的多样化 以前网络，主要“尽力而为”地传输无连接服务，主要针对电子邮件、 r e l n c t 、 f t p 等业务。而现在的网络开始承载丰富多彩的业务类型，如多媒体数据、语音、 视频等需要实时特性的或者是需要紧急处理的商业服务。 网络流量的急速增长和网络业务类型的多元化，使得人们对传统互联网提 出了更高要求：传统网络在有限资源环境下，提供更高服务质量( q o s ) ，以便满 足不同类型不同流量的业务对网络的需求。 i t u 在e 8 0 建议书中定义q o s 为：“服务性能的集中反映，它决定了用户对服 务的满意程度”。1 e t f 将q o s 定义为通过带宽、延迟和丢失率等参数描述的分 组传输的质量。目前己经提出了许多q o s 控制机制，如i e t f 提出的集成服务 ( i n t s e r v ) u 和x r - 分服务( d i f s e r v ) 删，分组调度和队列管理算法等。q o s 的保证实 现主要由网络的l s p 来完成，从 s p 角度来看，q o s 是通过一组定量、可测量、可 西安电子科技大学博七学位论文：基于博弈论的可生存网络路由资源管理研究 控制的参数来描述的，这些参数可以是：延迟和延迟抖动、吞吐量、丢包率等。 目前针对网络提供q o s 研究技术很多，主要是通过节点控制和全网控制或 局部网络控制来实现q o s 保证。节点控制在单节点完成，主要控制流量对节点 共享资源占用，包括共享链路、队列等，节点控制主要策略包括：业务流整形【”、 分组调度、队列管理1 4 i 等。全网和局部网络q o s 控制是通过对路由、信令进行控 制，以便实现对业务流和网络资源的控制，目前取得成果有r s v p ，m p l s 等技术。 然而，所有对网络提供的服务质量( q o s ) 的研究，是网络在多种业务类 型共存、网络流量急速增大的环境下，能保证提供最基本性能基础上而进行网 络性能的提高和完善。 因此，关于网络服务质量( q o s ) 研究技术的基础是网络基本能力的保证。 在目前网络环境下，面对多种业务类型，面对急速增长的网络流量，如何保证 网络提供最基本功能，成为了网络研究的一项重要内容，这也就是网络可生存 性问题。 1 2 网络可生存性 如上所述，网络更好地服务性能的前提条件是网络能提供最基本的功能和性 能。也就是说，网络提供良好服务的基本前提是网络处于正常运行状态下，如 果网络的正常运行都不能保证的，那么追求性能的卓越也是惘然。 然而，针对目前网络环境，网络在实际运行时，因为意外或者是攻击而不 能正常工作的情况屡见不鲜。例如：当年电信网络除夕之夜信息中断的情形、 互联网黑客攻击造成银行信用卡密码丢失现象等。这些意外或者突发事件出现， 不仅使得网络不能提供优质服务，而且可能连最基本的服务功能都不能提供， 给依赖于网络生活的人们带来很大危害。 因此，在对网络提供优质性能研究的同时，关于网络存在性的研究问题也 成为一个关键内容，该问题的研究也为构建下一代互联网奠定了基础。 在实际网络运行中，高速网络用户和提供商发现网络可生存性问题研究是 非常重要的，因为许多高速网络需要具有恢复和保护性能；电信网发现可生存 性研究很重要。是因为所有终端用户完全依赖于通信网，其一个最基本的关注 点就是网络最基本功能。 第一章绪论 最早关于网络可生存性研究是基于通信网络的，当时主要使用连通率来表 示网络的可生存性。连通率是指网络中任意给定的两节点之间，至少存在一条 路径的概率。随着下一代网络出现，目前网络生存性概念已经极大扩展，进一 步考虑了网络恢复能力，包括动态路由策略、故障维修和预防、冗余等，其意 义甚至比可靠性概念更一般，涵盖了网络鲁棒性( r o b u s t ) 的概念。 在网络环境中，终端用户通过调用各个网络节点提供的服务，从而完成自 身需求。因此，网络可生存性定义是与用户期望相关，关于网络可生存性的定 义在表述方式上不尽相同。 网络生存性( s u r v i v a b i l i t y ) 定义： 网络系统在意外故障出现或恶意攻击情况 下，使得系统继续工作的能力垆】。 从网络可生存性定义来看，包括以下两个方面含义： 1 ) 应用各种恢复技术，使网络性能恢复或者维持在能接受的水平上i 2 ) 应用各种预防或者保护技术，预防或减轻、转移因为网络故障而带来的 服务损耗。 网络可生存性和传统的安全防御含义是不同的，安全防御需要集中控制和 管理，可生存性问题是高度分布的，是在极其宽泛的网络环境中工作，没有集 中控制或者是统一的安全措施。 网络可生存性问题的研究焦点是：网络在受到攻击和危险时，能传递必要 的服务和保持必要的资源信息，并在攻击后，及时恢复全部服务和资源。 目前，网络可生存性研究如火如荼，表现在关于不同网络类型的可生存性 定义、需求、分析方法、以及构建可生存性网络关键技术等各个方面。 构建网络可生存性的技术依据网络可生存性的含义不同，表现为不同的因 素。如网络可用性( a v a i l a b i l i t y ) 表示在系统出现失败情况下，软件仍能执行的 可能性或者程度；网络连接性( c o n n e c t i v i t y ) 表示在所有结点和链路可用情况 下，系统的可执行程度；公平性( f a i r n e s s ) 表示网络系统正确地组织和路由信 息的能力；性能( p e r f o r m a n c e ) 表示网络提供的质量因素，等等。 网络可生存性的计算或度量，通常表现在网络连接性、网络性能、业务容 量三个方面。文献【6 】研究了通过图的方法找到最佳的k 个路径，这个问题的研 究结果为m i n i m u mc o s tn e t w o r kf l o w ( m c n f ) 问题，其网络可生存性表现为网 络连通性。文献【7 】通过业务容量而不是网络连通性测量网络的可生存性，可生 4 西安电子科技大学博七学位论文：基于博弈论的可生存网络路由资源管理研究 存性是通信网络受到破坏后，还能保留处理业务的百分比。文献【8 】通过网络成 功通信的可能性来计算网络可生存性，是基于网络性能来描述网络计算的。 综上所述，可以看出，网络可生存性的测量计算主要表现在3 个方面：可 连接性、网络性能、其它性能或代价的测量函数。而对于互联网来说，如同分 布式系统一般，对于提供最基本功能的网络结点不是总能了解，因此研究和构 建可生存性模型，如r e l i a b i l i t y l a t e n c y 模型【9 l 、s u r b i b a b i l i t y 函数模型加1 、n o d ea n d l i n kc o n n e c t i v i t y 模型【j 1 1 、管理可生存网络信息模拟模型是必要的。 1 3 网络可生存性的关键技术 如上所述，在多种业务共存和业务流量剧增的网络环境下，保证网络服务 质量和网络可生存性，是现代网络必须提供的能力，其中，网络可生存性是网 络服务质量的基础。不同网络类型，度量网络可生存性的方法不同，也就是说， 影响网络可生存性的因素各不相同。 在互联网环境下( 以下统称为网络) ，通常通过网络连通性以及网络性能 业务容量等性能来测量互联网的网络可生存性。那么，研究影响互联网可生存 性的关键技术，继而提出提高网络可生存性的某些方法和技术，对于提高网络 可生存性是必要的问题，这也就是本论文研究的目的。 图1 1 是互联网示意图，其中互联网是作为信息通信的承载体，多个用户的 多种业务类型请求通过多层路由器件( 或交换机) 的中转，最终到达目标服务 器接受处理，同时并将处理结果返回给用户。 图1 1 互联网示意图 通过图1 1 可以看出，用户、路由器( 或中嘲交换部件) 、目标服务器之间 的琏路利用率以及网络路由协议是影响网络可生存性的关键因素。保证这些 第一章绪论 关键部件正常、高性能工作，是网络可生存性的基本保证。 然而，目前，随着网络规模迅速扩大，网络上开放业务类型不断增加，网 络应用不断深入，工作在这种网络情况下的网络可生存性关键部件，可能会导 致网络性能急剧下降，甚至发生网络性能为0 的现象，从而严重影响网络可生 存性。这种网络可生存性关键部件性能急剧下降现象就是网络拥塞现象。 也就是说，网络拥塞现象的出现，是网络可生存性不复存在的一个致命因 素。如何使得路由器、链路协议以及路由协议等这些网络关键部件保证正常工 作，保证网络具有高性能的吞吐量、公平性以及较少的延迟特性，成为本文研 究的内容。为更好地说明本文研究内容，本文在这里用简单笔墨描述了网络关 键部件产生拥塞的原因以及目前用于控制拥塞现象的技术，从而引出本文研究 内容。 所谓拥塞现象，是指由于网络中存在过多数据包时，网络性能会下降的现象。 发生拥塞时，系统吞吐量下降，严重时会发生“拥塞崩溃”( c o n g e s n o nc o l l a p s e ) 1 1 3 】现象。拥塞控制机制包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控制 ( c o n g e s t i o nc o n t r 0 1 ) 两种策略。拥塞避免是一种“预防”措施，维持网络高吞吐、 低延迟状态，避免进入拥塞；而拥塞控制是一种“恢复”措施，使网络能从拥 塞中恢复过来，从而进入正常运行状态。 导致网络发生拥塞的直接原因是网络关键部件具有以下特点： 1 1 存储空间不足 网络资源毕竟是有限的，如图1 1 所示，几个输入数据流需要在同一端口输 出，必然会在这个端口上排队。如果没有足够的存储空间，也就是常说的缓存数 据包就会被丢弃，对突发数据流更是如此。增加存储空间在某种程度上可以缓 解这一矛盾，但如果路由器或者交换机有无限存储容量时，拥塞只会变得更坏而 不是更好，因为在网络里数据包经过长时间排队完成转发时它们早已超时，源端 认为它们已经被丢弃而这些数据包还会继续向下一路由器或交换机转发，从而 浪费网络资源加重网络拥塞。 2 1 带宽容量不足 低速链路对高速数据流的输入也会产生拥塞，根据香农信息理论任何信道带 宽最大值即信道容量c = b l o g ：( 1 + 导) ，其中，n 为信道自噪声的平均功率，s 为 信源的平均功率，b 为信道带宽。所有信源发送的速率r 必须小于或等于信道 容量c 。如果r c 则在理论无差错传输就是不可能的，所以在网络低速链路处 6 西安电子科技大学博七学位论文：基1 = 博弈论的可生存网络路由资源管理研究 就会形成带宽瓶颈，当其满足不了通过它的所有源端带宽要求时，网络就会发 生拥塞。 3 ) 处理器处理能力弱、速度慢 如果路由器或者交换机c p u 在执行排队缓存、更新路由表等功能时，处理 速度跟不上高速链路也会产生拥塞，同样低速链路对高速c p u 也会产生拥塞。 上述是早期网络产生拥塞的三个主要原因，t c p 拥塞控制较好地解决了这 三个原因造成的网络拥塞。如果所有的端用户能较好地遵守t c p 拥塞控制策略， 网络拥塞就会得到比较好的控制。然而事实上许多新的网络应用采用了与t c p 不同的拥塞控制策略，甚至是不采用任何的拥塞控制，这些给网络的稳定运行 带来了巨大的威胁。因此造成网络拥塞还有以下原因： 4 ) 恶意的数据流 网络中存在大量的多媒体实时应用和网络用户自己编写的网络程序，这类应 用为追求高的服务质量，采用恒定的发送速率，不响应网络拥塞通知，称为非 响应流( u n r e s p o n s i v ef l o w ) 1 4 1 ，是导致网络拥塞的又一个主要因素。当网络发 生拥塞时，有拥塞控制反应机制的t c p 响应流( r e s p o n s i v ef l o w ) 会按拥塞控制 步骤进入拥塞避免阶段，从而主动减小注入网络的数据量。但恶意数据流由于 没有端到端的拥塞控制机制，即使网络发出了拥塞指示( 如：分组丢失，往返 延迟增加等) ，也并不降低发送速率，结果导致遵守拥塞通知的t c p 响应流得 到的网络资源越来越少，而没有响应拥塞通知的恶意数据流得到越来越多的网 络资源，导致了网络资源分配的严重不公平。这种不公平最终会导致t c p 流“饿 死”，直至网络崩溃。所以研究如何判断在拥塞发生时各个数据流是否严格遵守 了t c p 拥塞控制( t c p f r i e n d l y ) ，以及如何“惩罚”不遵守拥塞控制协议( n o t t c p f r i e n d l y ) 的行为，成了目前研究拥塞控制的一个热点1 1 5 】。 5 1 组播应用 组播应用的推广一方面节省了网络资源，降低了网络管理费用，但与此同时 如果组播应用不能对网络拥塞做出正确响应，将会带来比网络单播( u n i c a s t ) 应用产生的拥塞更为严重的影响。这主要是因为：( 1 ) 组播流可能沿着多点投 递树广泛分布于整个网络。( 2 ) 组播流的接收者具有异构性，每个接收者的处 理能力不同，箕分组投递路径也可能有不同的带宽和差错特性。( 3 ) 组播发送 方需处理比单点投递多得多的反馈分组，对这些分组如果不加以处理，不仅可 能淹没发送方，而且它们本身也是网络资源的一种极大歼销。 由上分析可见网络产生拥塞的根本原因在于用户提供给网络的负载大于网 络资源容量和处理能力，表现为数据包时延增加丢弃概率增大上层应用系统性 能下降等。 第一章绪论 拥塞现象出现，表明网络中的负荷至少是暂时超过了网络的承受能力，所 以，通过增加资源或者降低网络负荷可以解决拥塞的出现。其中，最有效的方 法就是增加网络带宽。然而，实践证明，“无限的资源永远是有限的”，人的 欲望是无穷的，网络的业务量需求总归会超过可利用的网络资源，尤其是在下 一代互连网络出现的今天和将来，所以单纯依靠增加网络资源来解决拥塞现象 不是长久的解决办法。 而何况，网络流量不是呈现常态的，如电信网中节假日的呼叫流量远远大 于平时，出于代价考虑，网络资源也不可能是依据峰值流量而确定的。 由上述分析可以看出，控制拥塞现象，从而避免拥塞现象出现，是保证网 络可生存性的必要条件。本文就是针对这一网络现象，从路由器出发，研究其 中影响网络可生存性的关键问题，保证路由器端提供公平、高效、均衡的信息 传递和处理方式，在路由器各个控制管理阶段，避免拥塞现象的出现。 1 4 本文研究内容及创新点 本文主要研究内容和目标是：分析影响网络可生存性的关键部件，基于路 由器这一网络关键部件，运用博奔论思想，研究路由器网络资源公平性分配问 题，提出了路由器队列管理新方法和路由路径选择新方法，提高了网络资源分 配中的不公平问题，有效控制和避免网络中拥塞现象，最终提高了网络的可生 存性。 论文主要创新点如下： 1 提出了网络生存性研究问题； 2 将博弈论思想应用到路由器资源管理： 3 改进了基于n a s h 均衡的路由器业务丢弃方法； 4 提出了基于n a s h 均衡的路由器队列调度方法： 5 提出了针对实时业务和非实时业务共存的路由器实时排队方法： 6 提出了基于合作博弈的路由器路径选择方法； 7 提出了基于非合作博弈的路由器路径选择方法。 1 5 项目背景及本文内容安排 本论文的选题背景是来自于国家重点基础研究发展计划( 9 7 3 ) 项目“海量 信息的协同性和可生存性的理论与实践的研究”的课题“可生存的海量信息软 件设计理论”。该项日主要设计在无界网络上的海量系统软件可生存性的双规范 西安电子科技大学博十学位论文：基丁i 博弈论的可生存网络路由资源管理研究 说明语言、推理方法，研究可生存性的软件系统的开发模型、设计改善系统可 生存性的演化策略，并构造和使用各类程序分析工具。 另外，本论文具体研究内容来自于阿尔卡特一上海贝尔实际工程项目需求。 目前，本文提出的研究思想和方法为9 7 3 海量信息的协同性和可生存性理 论研究奠定了一定理论基础，并提出了解决该问题的新思路。另外，本文提出 的方法已经较好地应用在了阿尔卡特一上海贝尔实际工程项目之中。 本文内容安排如下； 第一章：主要介绍论文选题的背景以及研究意义和必要性，明确了论文研 究内容和创新点，介绍了本文结构安排。 第二章：介绍了博弈论相关概念和知识，着重介绍了博弈问题的解，即n a s h 均衡存在条件以及最优性等相关问题，分析了博弈论在路由器资源管理中的应 用情况以及相关研究状况，为本文解决方案奠定了基础。 第三章：介绍了目前路由器资源管理的方案和思路，并针对其中路由器队 列管理方法和路由选择技术进行了分析和研究；提出了将路由器队列管理看作 是路由器网络资源管理过程的概念，构建了路由器队列管理博弈模型，确定了 该博弈问题n a s h 均衡条件；基于针对该博弈模型的n a s h 均衡条件，从理论上 证明了目