（计算机应用技术专业论文）多服务网络资源分配模型和定价机制研究.pdf

东南大学博士学位论文 摘要 计算机网络的研究经历了开放系统互联、高速网络及协议实现、高性能网络等发展阶段，目前正在 进入高可用网络研究阶段。随着网络应用的日益普及和新型应用的不断涌现，网络的社会性也在不断增 强。并推动互联网从单纯的信息基础设施，逐渐发展成为社会的重要组成部分。在此过程中，网络资源 的控制和分配显得尤为重要，如何将有限的资源，以合适的方式，分配给适当的用户，发挥其应有的价 值，成为网络研究工作者必须考虑的问题采用经济学的理论和方法。对多服务网络的资源分配问题进 行建模分析和研究，近年来受到研究人员的普遍关注 论文从拥塞控制、q o s 提供等网络资源分配常用的技术手段和面临的困境入手，分析了经济学方法 应用于多服务网络资源分配问题中的必要性和可行性，并分别针对网络资源分配的优化目标、实现手段， 以及定价机制在多o o s 服务提供中的具体应用等方面存在的问题，进行了比较系统的探讨和研究。论 文包括三个部分的内容：第一部分( 第二、三章) ，在现状分析的基础上，研究并提出具有一定经济学 意义的网络资源分配优化模型；第二部分( 第四、五章) ，针对有连接接纳控制和无连接速率控制两种 情形，研究面向弹性非实时应用的网络定价和资源分配机制；第三部分( 第六、七、八章) ，针对硬实 时接纳控制、软实时速率控制，以及多服务网络优先级分配等情形，研究面向实时应用和特定q o s 要 求的网络定价和资源分配机制具体来说： 第二章介绍了一些基本的经济学概念和患想，如效用、效用最大化和用户需求、总效用和社会福利 最大化的资源分配目标等，分析了社会福利最大化目标与一些常用的公平性原则，如最大最小公平、 加权比例公平等的关系。概括了定价机制在网络资源分配问题中的应用和研究现状，介绍了拥塞定价和 q o s 定价的基本思想对定价方法、定价实现机制等进行了比较全面的归纳分析，并结合价格作用的时 问尺度、网络应用的连接特性和q o s 要求等，给出了定价机制应用于网络资源分配问题的基本思路。 第三章分析了网络服务的生产和消费特性，给出网络资源分配的生产消费概念模型，并采用福利 经济学的分析方法，得到资源分配问题的优化目标指出当社会福利函数取得最大值时，网络资源分配 达到效率和公平意义上的最优。通过对资源约束、q o s 约束等进行数学抽象，将资源分配的概念模型转 化为一个多约束优化模型n k a p ，并区分单节点和多节点情形，对模型做了进一步的分析，给出了求解 示例。 第四章面向有连接的弹性应用，探讨了基于可变连接价格的t c p 接纳控制问题。将该问题描述为 追求连接阻塞率最小化和活动连接时长最大化的多目标优化问题，分别考察了在连接请求确定和随机到 达时的连接价格确定问题，提出了在阻塞率不高于某一设定值的情况下，使得单位时间内期望活动连接 时长最大化的连接价格调整算法，并给出了基于s o c l 代理协议的实现方案。 第五章面向无连接的弹性应用，探讨了基于拥塞价格的速率控制问题。针对已有的梯度投影算法收 敛速度慢、效率不高的问题，提出了基于近似共轭梯度法的链路价格调整算法，分析了基于概率标记的 端到端价格传递机制，并重点探讨了价格估计中的样本量选择问题，以使价格估计具有较高的精度和一 定的可信度。在此基础上，把连接一级的接纳控制和分组一级的速率控制相结合，提出了基于多尺度拥 塞定价的资源分配思想，以适应网络协议和算法部署的实际需要。 第六章面向有明确q o s 要求的硬实时应用，探讨了基于有效带宽的接纳控制和网络定价问题。从 有效带宽的“生产函数”特性出发，分析了以价格为导向、以费用最小化为目标的有效带宽资源组合方 式，从相对价格和绝对价格调整两个层面，提出了追求分配步调一致和资源有效利用率的带宽缓冲区 东南大学博士学位论文 价格调整算法 第七章面向速率自适应和时延自适应的软实时应用探讨了带拥塞补偿的网络定价和速率控制问 题。对其网络费用构成进行了分析，提出了带拥塞补偿的网络定价机制和算法，对造成网络拥塞的数据 流收取额外的拥塞费用。对受到拥塞影响的数据流给予一定的价格补偿。给出了拥塞补偿价格的设置 原则，并分析说明了算法的激励相容性 第八章面向支持多种服务的区分服务，多优先级服务网络，探讨了基于区别定价的多q o s 服务选择 问题。将应用层面的q o s 选择和设定转化为技术层面的服务令牌分配问题进行研究，提出了基于预 算约束和效用最大化的服务令牌分配机制以及基于服务令牌的端用户d s c p 设定算法，并区分服务容量 固定不变和动态调整两种情形，给出了网络端自适应的多q o s 服务价格调整与资源分配算法。 实验结果表明本文提出的网络资源分配模型、算法思想和网络定价实现机制，具有相当的可行性 和一定的优越性。我们认为。将经济学理论和方法应用于网络资源分配问题中，将对网络体系结构的研 究及其协议和算法机制的设计产生深刻的影响，它有助于从理论上明确网络资源分配的目标和要求，进 而探讨有效的资源分配实现机制，为网络系统的设计和运行提供支持，并为最终解决网络中的服务定制， 资源控制和用户管理等三大问题提供有益、可行的思路。 关键词：资源分配，网络定价，福利经济学，效用最大化，接纳控制，速率控制。优先级分配 东南大学博士学位论文 a b s t r a c t d e v e l o p i n gt h r o u g h t h ep h a s e so fo p e ns y s t e m si n t e r c o n n e c t i o n ，h i g hs p e e dn e t w o r k s a n dh i g h p e r f o r m a n c en e t w o r k s ，t h en e t w o r kr e s e a r c hh a sc u r r e n t l ye n t e r e di n t ot h ep h a s eo f h i g ha v a i l a b i l i t yn e t w o r k s w i t ht h ep o p u l a r i t yo f n e t w o r k sa n dc o m i n gf o r t ho f n e wa p p l i c a t i o n s ，t h ei n t e m e th a se v o l v e dg r a d u a l l yf r o m i n f o r m a t i o ni n f r a s t r u c t u r ei n t oa ni m p o r t a n tp a r to fs o c i e t y d u et ot h es c a r c i t yo fn e t w o r kr c $ o u r o c s ，h o wt o a l l o c a t er e s o u r c e st oa p p m p r i a t eu s e r si nr e a s o n a b l em a i m e rb e c o m e sak e yc h a l l e n g et on e t w o r kr e s e a r c h e r s i nr e c e n ty e a r s ，t h et h e o r ya n dm e t h o d o l o g yo f e c o n o m i c sa r ei m p o r t e di n t ot h em o d e l i n ga n dp r o b l e m - s o l v i n g o fn e t w o r kr e s o u r c ea l l o c a t i o ni nm u l t i - c l a s ss e r v i c e sn e t w o r k , w h i c hi sr e g a r d e da sap r o m i s i n gr e s e a r c h d i r e c t i o na n da t t r a c t sm a n yr e s e a r c h e r s a t t e n t i o n s t a r t m gf r o mt h ed i l e m m a sf a c e dw i t ht e c h n i c a lm e a s u r e sf o rn e t w o r kr e s o t n x a l l o c a t i o n 。i n c l u d i n g c o n g e s t i o nc o n t r o la n dq o s ，w ee x a m i n et h eo p t i m a lo b j e c t i v eo fn e t w o r kr e s o u r o ea l l o c a t i o na n dd i s c u s st h e r o l eo fp r i c i n gm e c h a m s m si nt h ep r o v i s i o n i n go fq o ss e r v i c e s t h ed i s s e r t a t i o nc o n s i s t so ft h r e ep a r t s ： c h a p t e r2a n d3c o m p o s et h ef i r s tp a r tw h i c hf o c u s e so nt h ee c o n o m i ca n dm a t h e m a t i c a lm o d e l i n go f n e t w o r k r c $ o l t r c aa l l o c a t i o n ；t h es e c o n dp a r t , w h i c hi sc o m p o s e do fc h a p t e r4a n d5 ，s t u d i e st h er e s o n r c ea l l o c a t i o na n d p r i c i n gm e t h o d sf o ra p p l i c a t i o n sw i t he l a s t i ct r a f f i c ；t h et h i r dp a r tf o c u s e so nq o sp r i c i n ga n dr e s o u r c e a l l o c a t i o nm e c h a n i s m sw h i c ha r cd i s c u s s e di nc h a p t e r6 ，7a n d8 i nc h a p t e r2 ，s o m ee c o n o m i cc o n c e p t si n c l u d i n gu t i l i t y , u s e rd e m a n da n ds o c i a lw e l f a r ea r ei n t r o d u c e d f i r s t l y s p e c i f i c a l l yw ea n a l y z et h er e l a t i o n s h i pb e t w e e nw e l f a r em a x i m i z a t i o na n dt y p i c a lf a i r n e s sc r i t e r i as u c h a sm a x m i nf a i r n e s sa n dw e i g h t e dp r o p o r t i o n a lf a i r n e s s t h e nt h es t a t eo ft h ea r t i nn e t w o r kp r i c i n gi s e x a m i n e dt h o r o u g h l yi nw h i c hc o n g e s t i o np r i c i n ga n dq o sp r i c i n ga r ea n a l y z e di nd e t a i l a sf a ra st h et i m e f r a m eo fp r i c i n g ，t h ec o n n e c t i o nc h a r a c t e r i s t i c so fn e t w o r ka p p l i c a t i o n sa n dq o sr e q u i r e m e n t sa r cc o n c e m e d ， w ep r e s e n tt h eb a s i cv i e w p o i n tf o rt h ea p p l i c a t i o no fp r i c i n gm e c h a n i s m si nn e t w o r kr e s o u r c ea l l o c a t i o n p r o b l e m i nc h a p t e r3 ，ap r o d u c t i o n - c o n s u m p t i o nm o d e lf o rn e t w o r kr e s o u r c ea l l o c a t i o ni s p r e s e n t e df i r s t l y f o l l o w i n g t h e m e t h o d o l o g y o f w e l f a r e e c o n o m i c s ，i t i s i l l u s t r a t e d t h a t t h e n e t w o r kr e s o u l v ea l l o c a t i o np r o b l e m g e t si t so p t i m u ms o l u t i o ni nt e r m so f e f f i c i e n c ya n df a i r n e s si f f t h ec o r r e s p o n d i n gs w fr e a c h e si t sm a x i m u m v a l u e t h e nt h ec o n c e p t u a lm o d a li st r a n s f o r m e di n t oam a t h e m a t i c a lo p t i m i z a t i o nm o d e ln a m e da sn e t w o r k r e s o u r c ea l l o c a t i o np r o g r a m m i n g ( n r a p ) ，s u b j e c tt om u l t i p l ec o n s t r a i n t si n c l u d i n gr e s o u r c e ss e t , u s e r ss e t a n ds e r v i c er e q u i r e m e n t s t h em o d e li sf u r t h e ra n a l y z e du n d e rc i r c u m s t a n c e so fs i n g l e - n o d ea n dm u l t i - n o d e s w i t hd e m o n s t r a t i o n sp r e s e n t e d i nc h a p t e r4 a d m i s s i o nc o n t r o la n dp r i c i n gf o rc o n n e c t i o n - o r i e n t e de l a s t i ct r a f f i ca r cc o n c a m e d t c p a d m i s s i o nc o n t r o li sd e p i c t e da sam u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e mw i t hb l o c k e dr a t i om i n i m i z a t i o na n d a c t i v ec o n n e , a i o nd u r a t i o nm a x i m i z a t i o na so b j e c t i v e s a s s u m i n gt i mc o n n e c t i o nr e q u e s ta r r i v a l sa r e d e t e r m i n a t ea n ds t o c h a s t i cr e s p e c t i v e l y , w ed i s c u s sh o wt op r i c et c pc o n n e c t i o n s t h e nad y n a m i cp r i c i n g a l g o r i t h mi se x a m i n e dw h i c ha p p r o a c h e st h em a x i m u mo fa c t i v ec o n n e c t i o nd u r a t i o nw h i l ea s s u r i n gt h e b l o c k e dr a t i ou ta c c e p t a b l el e v e l f u r t h e r m o r ea p r i c en e g o t i a t i o ns c h e m eb a s e do ns o c k sp r o t o c o li sp r e s e n t e d w h i c hc a nb r i n gt h ep r i c i n ga l g o r i t h mi n t op r a c t i c a ln e t w o r k s m 东南大学博士学位沧文 i nc h a p t e r5 ，r a t ec o n t r o la n dp r i c i n gf o rc o n a a c t i o n l e s se l a s t i ct r a f f i cb e c o m et h et o p i c so f o u ri n t e r e s t a c o n j u g a t eg r a d i e n t - l i k ep r i c i n ga l g o r i t h mi sp r e s e n t e dt oa d j u s tt h en e t w o r kl i n kp r i c e si nd i s t r i b u t e dm a n n e r , w h i c hs h o w sf a s t e rc o n v e r g e n c et h a ng r a d i e n tp r o j e c ta l g o r i t h m t h e nt h ep r o h a b i l i s t i ce n d - t o - e n dp r i c e c o n v e y i n ga n de s t i m a t i o nm e t h o di sa n a l y z e df o r m a l l y , i nw h i c ht h ec h o i c eo f s a m p l i n gs i z ei so f i m p o r t a n c e a na d a p t i v ea l g o r i t h mf o rs a m p l i n gs i z ea d j u s t m e n ti sp r e s e n t e dt oa s s u r et h ep r e c i s i o na n dc r e d i t a b i l i t yo f p r i c ee s t i m a t i o n a f t e rt h a t , t h ei d e o l o g yo fm u l t i - s c a l ec o n g e s t i o np r i c i n gi sd i s c u s s e dw h i c hc o m b i n e st h e a d m i s s i o nc o n t r o la tc o n n e c t i o nl e v e la n dr a t ec o n t r o la tp a c k e tl e v e lt o g e t h e r i nc h a p t e r6 ，p r i c i n ga n da d m i s s i o nc o n t r o lf o rr e a l - t i m et r a f n cw i t hh a r dq o sr e q u i r e m e n t sa r ee x a m i n e d t h ec o n c e p to f e f f e c t i v eb a n d w i d t h , w h i c hc a nb er e g a r d e da sp r o d u c t i o nf u n c t i o ni ne c o n o m i c s 。i su t i l i z e dt o d e p l o ya d m i s s i o nc o n t r o lf o rs u c ha p p l i c a t i o n s a na d a p t i v ea l g o r i t h mf o rr e s o u r c ec o m p o s i t i o ni sp r o p o s e dt o m a i n t a i nt h e a l l o c a t i o no fb a n d w i d t ha n db u f f e rb e i n gi n s t e pw h i l ef o l l o w i n gt h eo b j e c t i v eo fc h a r g e m i n i m i z a t i o n t h e nt a k i n gi n t oa c c o u n ta b s o l u t er e s o u r c eu t i l i z a t i o nr a t i o ap r i c i n gm e c h a n i s mf o rn e t w o r k b a n d w i d t ha n db u f f e ra l l o a t i o ni sp r e s e n t e dt oe n f o r c ea d m i s s i o nc o n t r o lf o rr e a l - t i m ea p p l i c a t i o n s i nc h a p t e r 7 ，p r i c i n ga n dr a t ec o n t r o l f o rr e a l - t i m et r a f f i cw i t hr a t e - a d a p t i v eo rd e l a y - a d a p t i v e c h a r a c t e r i s t i c sa r ef o c u s e do n f o rs u c ht r a f f i ci ti sa c c e p t a b l et oa l l o wu s e r si n s t a n t a n e o u sr a t et ob em o r eo r l e s st h a nw h a th e s h er e q u i r e d w h i l en e t w o r kc o n g e s t i o ni so n s a t , i ti sn e c e s s a r yt od i s t i n g u i s ht h eu s e r ss oa s t op u n i s ht h em i s b e h a v i n gu s e r sb ye x t r ac o n g e s t i o nc o s ta n dc o m p e n s a t et h ei n n o c e n tu s e t “jb yp r i c ed i s c o u n t b a s e do nt h i ss t a n d p o i n t , t h er u l e sf o rs e t t i n gc o n g e s t i o np r i c ea n dc o m p e n s a t i o np r i c ea r ee x a m i n e di nd e t a i l a n dt h ei n c e n t i v ec o m p a t i b i l i t yi sa n a l y z e da sw e l l i nc h a p t e r8 ，p r i c i n ga n ds e r v i c es e l e c t i o nf o rd i f f e r e n t i a t e do rm u l t i - p r i o r i t ys e r v i c en e t w o r k sa r e d i s c u s s e d g i v e nn e t w o r ks e r v i c ep r i c e s ，u s e r sh a v et oa l l o c a t et h e i rb u d g e t sr e a s o n a b l yo od i f f e r e n ts e r v i c e s w h i c hc o r r e s p o n d 幻s p e c i f i cn u m b e ro fs a r v i c et o k e n s f o re a c hu s e r , t o k e na l l o c a t i o n h e m ec a nb ed e r i v e d f r o mu t i l i t ym a x i m i z a t i o n , w h i c ht h e ng u i d e st h ed s c ps e l e c t i o ni nd i f l s e r vn e t w o r k s o nt h eo t h e rh a n d , n e t w o r k sh a v et oa d j u s ts e r v i c ep r i c e sa n dc a p a c i t i e si na c c o r d a n c ew i t hu 钾培d e m a n dv a r i a t i o n ad y n a m i c r v i c op r i c i n ga n dp r o v i s i o n i n ga l g o r i t h mi s p r e s e n t e dw h i c hc o n v e r g e st ot o t a lu t i l i t ym a x i m u m a p p r o x i m a t e l y e x p e r i m e n ta n ds i m u l a t i o nr e s u l t ss h o wt h a tt h ei d e a sa n da l g o r i t h m sp r e s e n t e dj nt h i sd i s s e r t a t i o nc a nb e p u ti n t op r a c t i c e ，p e r h a p sw i t hs o l n em o d i f i c a t i o n s ，t os a t i s f yt h er e q u i r e m e n t so fm u l t i - c l a s ss e r v i c e sn e t w o r k r e s o u r c ea l l o c a t i o n w eb e l i e v et h a ti tw i l lh a v eg r e a ti m p a c to nt h er e s e a r c ho fn e t w o r ka r c h i t e c t u r ea n d d e s i g n i n go fn e t w o r kp r o t o c o l st oa p p l ye c o n o m i c st h e o r ya n dp d c i n gm a c h a n i s m si nn e t w o r kr 鹤o u r d e a l l o c a t i o n , b yi d e n t i f y i n gt h eo p t i m i z a t i o no b j e c t i v ef u r t h e ra n dp r o v i d i n gt h er e a s o n a b l ei m p l e m e n t a t i o n m e a s u i 船 k e y w o r & ：r a s o m v a l l o c a t i o n , n e t w o r kp c i n g ，w e l f a r ee c o n o m i c s ，u t i l i t ym a x i m i z a t i o n , a d m i s s i o n c o n t r o l ，r a t ec o n t r o l ，q o sp r o v i s i o n i n g 东南大学博士学位论文 图2 i 各类应用的效用曲线 图2 2 多媒体应用的满意度曲线 论文插图索引 图2 3d q m 算法示意 图3 1 网络资源分配的生产消费概念模型 。2 3 ：! l i 2 9 图3 2 生产契约曲线 图3 3 生产可能性边界和交换契约曲线 图3 4 效用可能性边界 图3 5 最大社会福利 图3 6 多节点n r a p 模型网络环境示例。 图4 1 基于s o c k s 协议的价格协商和认证过程 图5 1 链路价格调整算法实验拓扑。 图5 2 链路价格调整算法传输示意图。 2 9 2 9 3 5 图5 3 梯度投影法、类牛顿法、近似共轭梯度法链路价格调整对比。5 5 图5 4 基于价格的速率控制算法的仿真实现结构 图5 5 样本量固定不变的链路价格估计 图5 6 样本量自适应调整的链路价格估计 图5 7 效用同构情形下的链路价格和速率变化。 图5 8 效用异构情形下的链路价格和速率变化 图6 1 未启用相对价格调整算法时的资源利用率和请求接入情况 图6 2 启用相对价格调整算法时的资源利用率和请求接入情况 图6 3 基于有效带宽的接纳控制：各种情形下的性能对比 图7 1 带拥塞补偿的网络服务定价算法实现框架 图7 2 带拥塞补偿的网络服务定价过程示例。 图7 3 非拥塞状况下按约定速率计费时用户的策略选择 图7 4 非拥塞状况下按实际到达流量计费时用户的策略选择 图8 1 服务容量固定不变时的多q o s 服务价格调整 圈8 2 服务容量动态可变时的多q o s 服务价格调整 图8 3 多q o s 服务价格调整算法下的用户总效用 。6 2 6 3 7 3 7 4 7 5 8 3 。8 3 9 0 东南大学博士学位论文 论文表格索引 表3 1 社会福利函数形式对资源分配结果的影响 表5 1i p 报头中的e c n 标记位 表7 1 非拥塞状况下按约定速率计费时用户的支付矩阵 表7 2 非拥塞状况下按实际到达流量计费时用户的支付矩阵 - 3 6 5 6 8 l 东南大学学位论文独创性声明 本人声明所里交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材 料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 研究生签名：逊 日期： 撕5 一，一如 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办 理。 研究生签名：毽壶! 墨导师签 日期： 叼占一，二一， 第1 章引言 第1 章引言 在统一的分组交换网络中，提供包括数据、语音和视频在内的多种服务类型，满足网络应用多样的 q o s 需求实现有效的服务定制、资源控制和用户管理，是新一代计算机网络的发展方向和目标【l “i 当前网络的研究重点正在从传统的互联互通，向现代服务和应用过渡，高可用性成为网络发展的主要特 征和必然要求，其核心是如何有效地利用各类网络资源，运用各种技术和非技术手段，为用户提供所需 而又可控的服务，为网络的健康发展提供坚实的基础。作为网络系统设计和运行的基础，资源控制对于 上述目标的实现，显得尤为重要。近些年，研究人员从不同的角度和层面，对网络资源分配问题进行了 探索和研究。本文尝试采用经济学研究方法，对网络资源分配问题进行建模分析并利用定价机制和一 定的技术手段，来达到资源优化分配的目标，向用户提供有效的多o o s 服务支持。 1 1 立题背景 计算机网络中的资源大致可以分为以下几类：处理器( 计算) 资源、存贮器资源、软件和数据资源、 网络通信资源等基于对网络通信和数据传输服务的关注，本文中网络资源主要是指用于数据传输的通 信资源。包括链路带宽和缓冲区，其中带宽为数据传输的基础资源：缓冲区为辅助资源，主要用于平滑 流量突发。提高链路利用率。一般我们假定网络节点的处理能力不成为网络传输的瓶颈。正如后续章节 所述，链路带宽和缓冲区资源的量以及它们适当的组合方式，决定了网络的数据传输能力，这种抽象的 传输服务能力可以按照丢包、时延等q o s 特性进行分类和描述。 我们认为，尽管网络应用层出不穷、日新月异，但从网络传输的角度来看，仍可对其进行适当的归 类。根据其效用特性不同网络应用大致可分为弹性应用和非弹性应用，前者根据所采用的传输协议的 不同，分有连接和无连接应用，这类应用没有明确的q o s 要求，通常由网络向它们提供尽力而为的传 输服务：后者根据应用在带宽，时延等方面的不同要求，分硬实时和软实时应用。这类应用有相对明确 的q o s 要求，通常由网络通过接纳控制、资源预留、分组调度等手段来予以保证。在统一的i p 传输平 台之上，丽向不同的网络应用类型。提供与之相适应的数据传输服务。正在逐渐成为各方的共识，按照 这样一种理念构建出来的网络称之为多服务网络。 1 1 。1 分组调度与队列管理 和传统的电路交换网络不同，计算机网络中的链路带宽和缓冲区资源主要通过统计复用的方式，以 分组交换的形式为用户共享而没有显式的信令机制来完成资源分配。为提高链路带宽和缓冲区资源的 利用率，提高网络系统的整体吞吐量，针对这两种资源的分配与管理分别设计出了分组调度和队列管理 机制。 分组调度的主要功能是，对来自不同数据流的分组进行逻辑或物理的排序，在链路可用时优先调度 排在前面的分组。分组调度策略通过控制来自不同数据流的分组的调度次序和频度，决定了链路带宽在 各个数据流之间如何进行公平而有效率的分配，并影响到数据传输的端到端时延以及交换节点的缓冲区 分配与管理策略等。常用的分组调度机制包括：( 1 ) f c f s ，即先到先服务，数据包根据到达网络接口 的先后顺序依次获得调度：( 2 ) 轮次调度( r o u n d - r o b i n ) 网络接口维护多个队列，每个队列按照时间 片轮转，依次获得调度；( 3 ) 基于g p s 思想p l 的w f q 公平队列调度。为每一队列设定不同的权重。网 络接口按照权重比例，为各队列分配相应的调度机会。队列内部按f c f s 调度 队列管理的主要功能是，在数据分组到达网络发送接口时，决定其能否进入以及进入哪个发送队列， 东南大学博士学位论文 在排队期间占用缓冲区发送完成之后释放缓冲区常用的队列管理机制包括一( 1 ) 尾丢弃，数据按到 达顺序依次进入队列，在缓冲区满时丢弃新到达的数据包；( 2 ) 头丢弃，在缓冲区满时丢弃队列头部先 前到达的数据包；( 3 ) 主动队列管理，在缓冲区使用达到一定程度但尚未占满时，主动丢弃一定比例的 数据包，避免在缓冲区满时连续丢包造成的“排外”( 1 0 c k o u t ) 和“全局同步”现象i j 。 分组调度和队列管理是既紧密联系又各有侧重的两种资源分配机制，队列管理在数据包到达时决定 其能否进入缓冲区排队，分组调度则根据一定的调度规则和策略，决定以什么样的次序为队列中的数据 包提供调度服务。在实现上。往往是在数据包到达网络接口等待发送时，既要决定其能否进入队列还 要同时决定将该数据包插在哪个队列的哪个位置，为实际调度做好准备以p g p s 调度为例i j j ，分组到 达时，系统根据相应队列的权重设置和分组大小，计算分组的虚拟完成时间( r t u a lf i n i s ht i m e ) ，这个 时问即决定了分组随后获得调度的相对次序，而某一数据流对带宽的利用程度则取决于相应队列获得调 度的频率 1 1 2 网络拥塞控制与资源分配 队列管理主要关注网络中间节点的缓冲区资源的分配，它通过数据包入队和合理的丢弃策略，保证 缓冲区在网络服务提供中发挥应有的作用，同时也在必要时向端系统发出显式或隐式的网络拥塞信号 并期望端系统对此做出适当的反应，以此协调端系统和网络之间的行为。从这个意义上链路带宽和缓 冲区资源的分配，离不开网络端系统的积极参与，这正是网络拥塞控制所重点研究的内容。 一般而言，当用户注入网络的数据流量超出网络的传输容量时，将会出现网络拥塞，持续的网络拥 塞将造成网络性能的急剧下降，表现在丢包增加，时延增大，链路的有效利用率降低等出现网络 拥塞的根本原因在于用户需求是贪婪的，比如希望f t p 传输越快越好，而网络资源( 链路带宽，缓 冲区等) 则相对有限。当前网络主要依赖于t c p 协议的拥塞控制( 还包括流量策略机制) 和中间节点 的a q m 主动队列管理机制，来实现拥塞控制，前者约束用户的发送速率，后者协调网络资源的使用。 t c p 协议【姐7 1 【1 1 采取a i m d 方式的拥塞窗口更新机制。它以隐式的丢包指示作为网络拥塞的判断依 据，在出现拥塞时将拥塞窗口相应缩减，通过降低发送速率来解除拥塞，使网络保持在稳定可用的状态。 t c p 协议机制并不直接控制网络资源分配( 虽然t c p v b g 邪1 9 】等有隐含的缓冲区占用要求) ，而是通过调 整发送速率来向网络提出资源需求。 a q m 主动队列管理机制【”k 4 1 ，则是由网络中间节点通过估计到达速率或者跟踪队列长度的变化。 在网络出现拥塞之前，按照一定的概率主动丢弃或标记分组，目的是避免因连续丢弃分组而造成的t c p 全局同步，同时保持队长相对稳定，提高网络链路利用率。主动队列管理机制通常并不针对单个流进行 网络资源分配( 虽然s r e d 【“l 等有对活动流数目的估计) ，而是通过有选择的丢包和端系统的响应，来 间接决定数据流对网络资源的使用。 早期的拥塞控制方面的研究，多数都是在直观分析或经验判断的基础上，对协议或算法机制进行设 计，再通过仿真实验或实际应用对算法的性能做出评价和改进，本质上处于“摸着石头过河”的阶段 比如对t c p 协议，就是先设计出分组级的窗口调整机制，然后再来分析其流一级的稳态吞吐量和公平 性表现【”廿j ，并相应地做出改进近年来，研究人员开始自觉不自觉地从直观的经验分析方法，转向 系统化的、理论指导实践的研究方法，这不仅表现在以h i g h s p e e d 1 4 l 、s c a l a b l e ”j 、f a s tt c p 【“喀端系 统拥塞控制机制的设计上，还反映在以r e m ”、p i ”l 、a v q 1 9 l 等主动队列管理算法上 总的来说，网络拥塞控制是从网络的立场，关注网络的整体运行状况，其主要控制手段是通过显式 或隐式的拥塞指示信息，要求端系统调整其数据发送速率。这也是目前多数基于控制论方法开展网络问 2 一 第l 章引言 题研究的基础 t s x z 0 1 t 6 l ，它假定用户和网络之间是合作的，端系统在检测到网络出现拥塞时，会主动降 低自己的资源要求。但它对非响应流i ，】( 如基于u d p 的多媒体应用) 并不适用，同时存在一定的公平 性问题j 1 1 3 网络q o s 与资源分配 分组调度主