（通信与信息系统专业论文）基于优化与控制理论的网络拥塞控制算法研究.pdf

_j t ? ! f i l ll lii i illl l l ii iiil y 17 5 5 5 9 4 t h er e s e a r c ho nn e t w o r k c o n g e s t i o nc o n t r o la l g o r i t h m b a s e do no p t i m i z a t i o na n dc o n t r o l t h e o r y 4d i s s e r t a t i o n s u b m i t t e dt on a n j i n gu n i v e r s i t y o fp o s t sa n dt e l e c o m m u n i c a t i o n s f o r t h ed e g r e eo f d o c t o ro fp h i l o s o p h y b y w e it a o s u p e r v i s e db y p r o f z h a n g s h u n - y i c o l l e g eo ft e l e c o m m u n i c a t i o n sa n di n f o r m a t i o ne n g i n e e r i n g n a n ji n gu n i v e r s i t yo fp o s t sa n dt e l e c o m m u n i c a t i o n s d e c e m b e r2 0 0 9 明 作及取得的研究成 含其它人已经发表 或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作过的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 研究生签名：衄日期： 南京邮电大学学位论文使用授权声明 l ， 别0 y 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。本文电子文档 的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借 阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京邮 电大学研究生部办理。 ， 研究生签名：墓雎导师签名： 学科： 工堂 专业： 适信生信：垦丕缠 研究方向：让箕扭通信圆终 作者：魏涛指导老师：张顺颐教授 题目：基于优化与控制理论的网络拥塞控制算法研究 t i t l e ：t h er e s e a r c ho nn e t w o r kc o n g e s t i o nc o n t r o la l g o r i t h mb a s e do no p t i m i z a t i o na n d c o n t r o lt h e o r y 关键词：拥塞控制；传输控制协议；主动队列管理；优化；线性控制；非线性控制 k e y w o r d s ：c o n g e s t i o nc o n t r o l ；t r a n s m i s s i o nc o n t r o lp r o t o c o l ；a c t i v eq u e u em a n a g e m e n t ； o p t i m i z a t i o n ；l i n e a rc o n t r o l ；n o n l i n e a rc o n t r o l 本论文得到以下基金项目资助 l 、 国家高技术研究发展计划“8 6 3 ”项目“基于业务感知的下一代网络q o s 分布式主动 检测管理技术 ( 编号：2 0 0 5 a a l 2 1 6 2 0 ) 2 、国家高技术研究发展计划“8 6 3 项目“自组织网络的监测、控制和管理研究( 编 号：2 0 0 6 a a 0 1 2 2 3 2 ) 摘要 摘要 单纯学术领域向通信、商业等多个领域的发展，以致i n t e r n e t 网络上的用户和应用快速增长，从而不可避免地出现网络拥塞现象，网络拥塞的发生造 成i n t e m e t 网络性能严重下降，因此，对网络进行拥塞控制成为改善i n t e m e t 网络性能、 提高服务质量的主要手段。本文分别从优化理论、经典线性控制理论、非线性控制理论 的角度来进行网络拥塞控制算法的设计，针对不同应用角度，提出了几种网络拥塞控制 算法。 基于p i 控制器的主动队列管理算法可以有效地消除队列控制中的“稳态误差 ， 然而，该算法中p i 控制积分项的引入也导致算法响应速度的降低，动态调节效果不甚 理想。本文提出一种基于最优非线性p i 控制器的主动队列管理算法，当网络流量处于 平稳状态，采用基于最优非线性p i 控制器的主动队列管理算法来控制路由器队列长度， 该算法具有更快的响应速度以及更小的稳态误差，。算法性能优于基于p i 控制器的主动 队列管理算法。 虽然基于最优非线性p i 控制器的主动队列管理算法在响应速度上优于基于p i 控制 器的主动队列管理算法，但是当网络流量处于较剧烈变化时，基于最优非线性p l 控制 器的主动队列管理算法可能引起“闭环不稳定 ，产生控制振荡现象。振荡可通过向 控制信号增加微分作用项来予以矫正，但其参数的设置比较困难。因此，本文提出一种 基于粒子群优化的p i d 主动队列管理算法。该算法通过将粒子群优化算法与p i d 控制器 相结合，既能解决p i d 控制器参数整定的问题，又可通过粒子群优化算法在线修正p i d 控制器参数来适应网络流量的变化，对较剧烈网络流量变化的适应能力较强。 p i 控制器、p i d 控制器均属于线性控制器，虽然基于经典线性控制理论所设计的控 制器增强了对路由器队列长度的控制能力，但在网络高速变化的动态环境下( t c p 连接 数目较多，变化较大，存在u d p 流) ，这些算法地很难抵抗负载扰动和噪声的干扰， 控制器参数难以整定，鲁棒性较差，算法稳定性难以保证。针对这一问题，本文从非线 性控制理论出发，利用非线性控制方法中的积分反步法设计了一种主动队列管理算法， 利用积分反步法所设计的主动队列管理算法具有较好的鲁棒性以及稳定性。 南京岫也人学博：l j 研究生学位论文 摘要 滑模变结构控制作为一种鲁棒控制方法引起人们极大的关注，滑模变结构控制与积 分反步法同属于非线性控制方法，与本文所提出的利用积分反步法进行主动队列管理算 法的设计相比，滑模变结构控制具有所产生的滑动模念对系统参数变化和扰动不敏感的 优点，抗干扰性强。在滑模变结构控制中，仅依赖于系统参数变化的界值，不要求受控 对象精确的数学模型，本文提出使用模糊滑模变结构控制策略，在t c p 往返时间王m 以及t c p 连接数目这些不确定参数和u d p 数据流扰动部分上界未知情况下，根据滑模 到达条件，利用模糊规则估计出控制律中的切换增益，可以有效地克服传统滑模变结构 控制切换中延迟造成的抖动。利用模糊滑模变结构控制方法所设计的主动队列管理算法 具有更好的鲁棒性以及稳定性。 本文前面部分从不同角度所设计的四个主动队列管理算法，主要是在路由器中实 现，不涉及t c p 拥塞控制与路由器中的拥塞控制算法配合机制，s h l o w 等人提出了 完整的t c p a q m 对偶性模型，该模型把现有的t c p 拥塞控制和a q m 算法看作是求解 具有适当效用函数的最优速率分配问题，把用户合适拥塞速率的求取归结为一个非线性 优化模型，在t c p a q m 对偶性模型中，采用梯度下降法来计算网络链路价格。i n t e m e t 网络流量瞬息万变，为了实现全局的最优化速率控制，必须提高拥塞控制算法的收敛速 度，针对梯度下降法计算网络链路价格收敛速度慢的问题，本文提出使用b f g s 方法来 进行网络链路价格的计算，b f g s 方法既保持了n e w t o n 法收敛速度快的优点，又摆脱 了h e s s i a n 矩阵的计算，减少了计算量。 关键词：拥塞控制；传输控制协议；主动队列管理；优化；线性控制；非线性控制 南京邮i 乜人学博1 ：研究生学位论文 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e m e ta p p l i c a t i o nf r o ma c a d e m i cf i e l dt oc o m m u n i c a t i o na n d c o m m e r c i a lf i e l d ，t h eu s e r sa n da p p l i c a t i o n sa r er a p i d l yi n c r e a s i n gi ni n t e r n e tn e t w o r k ，s ot h e c o n g e s t i o np h e n o m e n o no fn e t w o r ki sb o u n dt oa r i s e b e c a u s et h ec o n g e s t i o no fn e t w o r k d e g r a d e st h ep e r f o r m a n c eo fn e t w o r k ，t h ec o n g e s t i o nc o n t r o lb e c o m e st h em a i nm e t h o df o r i m p r o v i n gp e r f o r m a n c ea n dq u a l i t yo fs e r v i c ei ni n t e m e tn e t w o r k t h i sp a p e rp r e s e n t ss e v e r a l k i n d so fc o n g e s t i o nc o n t r o lm e t h o df r o mt h ev i e wo fo p t i m i z a t i o nt h e o r y ，c l a s s i c a ll i n e a r c o n t r o lt h e o r ya n dn o n l i n e a rc o n t r o lt h e o r yr e s p e c t i v e l y a c t i v eq u e u em a n a g e m e n ta l g o r i t h mb a s e do np ic o n t r o l l e rc a ne f f e c t i v e l ye l i m i n a t et h e s t e a d y - s t a t ee l l o ro ft h eq u e u ec o n t r 0 1 h o w e v e r , t h ep i c o n t r o l l e rh a sa l s o 1 e dt ot h e r e d u c t i o no fr e a c t i o ns p e e da n dp o o rd y n a m i c a lr e g u l a t i o nb e c a u s eo fi n t e g r a lf a c t o r i nt h i s p a p e r , a l la c t i v eq u e u em a n a g e m e n ta l g o r i t h mb a s e do no p t i m a ln o n l i n e a rp ic o n t r o l l e ri s p r e s e n t e d w h e nt h en e t w o r kt r a f f i ci s a tas t e a d ys t a t e ，b a s e do nn o n l i n e a ro p t i m a lp i c o n t r o l l e r , t h ea l g o r i t h mh a saf a s t e rr e s p o n s es p e e da n ds m a l l e rs t e a d y - s t a t ee r r o ri nt h e p r o c e s so fc o n t r o l l i n gt h er o u t e rq u e u el e n g t ha n dt h ea l g o r i t h mi ss u p e r i o rt oa c t i v eq u e u e m a n a g e m e n ta l g o r i t h mb a s e do np ic o n t r o l l e ri np e r f o r m a n c e a l t h o u g ht h ea c t i v eq u e u em a n a g e m e n ta l g o r i t h mb a s e do no p t i m a ln o n l i n e a rp ic o n t r o l l e r i ss u p e r i o rt oa c t i v eq u e u em a n a g e m e n ta l g o r i t h mb a s e do np ic o n t r o l l e ri nt h er e a c t i o nr a t e ， w h e nt h en e t w o r kt r a f f i ci nam o r ei n t e n s eo s c i l l a t i o n , t h ea c t i v eq u e u em a n a g e m e n t a l g o r i t h mb a s e do no p t i m a ln o n l i n e a rp ic o n t r o l l e rm a y l e a dt oi n s t a b i l i t yi nt h ec l o s e d - l o o p a n do s c i l l a t i o n f o rt h en e t w o r kt r a f f i ci nam o r ed r a m a t i co s c i l l a t i o n se n v i r o n m e n t ，ap i d a c t i v eq u e u em a n a g e m e n ta l g o r i t h mb a s e do np a r t i c l es w a r mo p t i m i z a t i o ni sp r o p o s e db y i n c r e a s i n gt h er o l eo fd i f f e r e n t i a lc o r r e c t i o nt oc o n t r o ls i g n a l t h ea l g o r i t h mi s f u l f i l l e db y p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mw i t hac o m b i n a t i o no fp i dc o n t r o la l g o r i t h m ，w h i c h c a nb ee f f e c t i v e l yc a r r i e do u ti na c c o r d a n c ew i t hc h a n g e si nf l o wb yt u n i n gp i dc o n t r o l l e r p a r a m e t e r s ，w h i c hc a na d a p tn e t w o r kt r a f f i ct ot h em o r ed r a m a t i cc h a n g e s p ic o n t r o l l e ra n dp i dc o n t r o l l e ra r el i n e a rc o n t r o l l e r t h o u g ht h ed e s i g no ft h ec o n t r o l l e r b a s e do nt h ec l a s s i c a ll i n e a rc o n t r o lt h e o r yc a ne n h a n c et h ec o n t r o lc a p a c i t yo ft h er o u t e r q u e u el e n g t h ，i nt h ed y n a m i c so fh i g h - s p e e dn e t w o r ke n v i r o n m e n t s ( ar e l a t i v e l yl a r g ea n dt h e l a r g e rc h a n g e sn u m b e ro ft c pc o n n e c ta n dt h ee x i s t e n c eo fu d ps t r e a m ) ，t h e s ea l g o r i t h m s i i i a r ed i 伍c u l tt or e s i s tt h el o a dd i s t u r b a n t ea n dn o i s ei n t e r f e r e n c ea n ds e t t i n go ft h ec o n t r o l l e r p a r a m e t e r si sd i 伍c u l t i nv i e wo ft h ef a c tt h a tp i ，p i dc o n t r o l l e rd e s i g nm e t h o d i sd i f f i c u l tt o g u a r a n t e et h ep e r f o r m a n c eo ft h ea l g o r i t h m i nt h ed y n a m i c so fh i g h s p e e dn e t w o r k e n v i r o n m e n t s ( ar e l a t i v e l yl a r g ea n dt h el a r g e rc h a n g e sn u m b e ro ft c pc o n n e c ta n dt h e e x i s t e n c eo fu d ps t r e a m ) ，t h i sp a p e rp r e s e n t sa na c t i v eq u e u em a n a g e m e n ta l g o r i t h mb y u s i n gi n t e g r a lb a c k s t e p p i n gm e t h o di nn o n l i n e a rc o n t r o lt h e o r y ，w h i c hh a sa b e r e rr o b u s t n e s s a n ds t a b i l i t y s l i d i n gm o d ev a r i a b l es t r u c t u r ec o n t r o lm e t h o da sa r o b u s tc o n t r o lm e t h o dh a sr a i s e df o ra g r e a t d e a lo fc o n c e r n s l i d i n gm o d ev a r i a b l es t r u c t u r ec o n t r o lm e t h o da n di n t e g r a l b a c k s t e p p i n gm e t h o da l l a r e t h en o n l i n e a rc o n t r o lm e t h o d c o m p a r e db yt h ei n t e g r a l b a c k s t e p p i n gm e t h o d ，s l i d i n gm o d ev a r i a b l es t r u c t u r ec o n t r o lm e t h o d w i t har e s u l t i n gs l i d i n g m o d eo nt h es y s t e mi sl e s ss e n s i t i v et op a r a m e t e rc h a n g ea n dd i s t u r b a n c ei nt h es y s t e m i nt h e s l i d i n gm o d ev a r i a b l es t r u c t u r ec o n t r o lm e t h o d ，o n l yd e p e n d e n to nt h es y s t e mp a r a m e t e r s c h a n g eb o u n d a r yv a l u e s ，t h ec o n t r o l l e do b j e c td o e sn o tr e q u i r e ap r e c i s em a t h e m a t i c a lm o d e l i nt h i sp a p e r ，f u z z ys l i d i n gm o d ev a r i a b l es t r u c t u r ec o n t r o ls t r a t e g yi su s e di n t h et c p r o u n d t r i pt i m er 订a n dt h et c pc o n n e c t i o nn u m b e ro f t h e s eu n c e r t a i np a r a m e t e r sa n du d p d a t as t r e a m sd i s t u r b e dp a r to ft h eu p p e rb o u n do ft h eu n k n o w nc i r c u m s t a n c e s f u z z ys l i d i n g m o d ev a r i a b l es t r u c t u r ec o n t r o la p p m a c hi su s e dt ot h ed e s i g no fa c t i v eq u e u em a n a g e m e n t a l g o r i t h m t h eu s eo ff u z z yr u l e st oe s t i m a t et h es w i t c h i n gc o n t r o ll a wg a i nc a ne f f e c t i v e l y o v e r c o m ej i t t e rc a u s e db yc o n t r o ld e l a yi nt h et r a d i t i o n a ls l i d i n gm o d ec o n t r o ls w i t c h t h e a c t i v eq u e u em a n a g e m e n ta l g o r i t h mh a sb e t t e rr o b u s t n e s sa n ds t a b i l i t yb yu s i n gf u z z ys l i d i n g m o d ev 撕a b l es t r u c t u r ec o n t r o lm e t h o d i nt h i sp a p e r , t h ea b o v ef o u ra c t i v eq u e u em a n a g e m e n ta l g o r i t h m s ，m a i n l ya r ef u l f i l l e di n t h er o u t e ra n dd on o ti n v o l v et h et c pc o n g e s t i o nc o n t r 0 1 s h l o wm a d eac o m p l e t et c p a q md u a l i t ym o d e lo ft h ee x i s t i n gt c pc o n g e s t i o nc o n t r o la n da q m a l g o r i t h m sa sau t i l i t y f u n c t i o nw i t ht h ea p p r o p r i a t es o l u t i o no ft h eo p t i m a lr a t ea l l o c a t i o n t h ec o n g e s t i o nr a t eo f t h eu s e rt os t r i k ei ss i m p l i f i e dt oan o n l i n e a ro p t i m i z a t i o nm o d e l i nt c p a q md u a l i t ym o d e l ， g r a d i e n td e s c e n tm e t h o di su s e dt oc a l c u l a t et h ep r i c eo fn e t w o r kl i n k s b e c a u s et h ei n t e r a c t t r a f f i cv a r i e sg r e a t l yf r o mt i m et ot i m e ，g r a d i e n td e s c e n tm e t h o df o ra d j u s t i n gt h el i n kp r i c ei s s l o w e rc o n v e r g e n c ei nt c p a q md u a lm o d e l t oa c h i e v eg l o b a lo p t i m a lr a t e ，t h eb f g s i v 南京i i l i n 乜人学博1 j 研究生学位论文 m e t h o dw i t haf a s t e rc o n v e r g e n c er a t ei su s e dt oc a l c u l a t et h el i n kp r i c ei nt h i sp a p e r w e p r e s e n tac o n g e s t i o nr a t ec o n t r o la l g o r i t h mb yu s i n gb f g sm e t h o dw h i c hc a no b t a i nt h e f a s t e rc o n v e r g e n c er a t ea n dl e s sc o m p u t a t i o n k e y w o r d s ：c o n g e s t i o nc o n t r o l ；t r a n s m i s s i o nc o n t r o lp r o t o c o l ；a c t i v eq u e u em a n a g e m e n t ； o p t i m i z a t i o n ；l i n e a rc o n t r o l ；n o n l i n e a rc o n t r 0 1 v 南京i i i l l l 【1 人学博l _ 7 i j f 究生学位论文 缩略语表 缩略语表 a c k a c k n o w l e d g e a i m d a d d i t i v ei n c r e a s em u l t i p l i c a t i v ed e c r e a s e a m e c n a d a p t i v em u l t i l e v e le c n a o p c a d a p t i v eo p t i m i z a t i o np r o p o r t i o n a lc o n t r o l l e r a q m a c t i v eq u e u em a n a g e m e n t a v q a d a p t i v ev i r t u a lq u e u i n g b f g s b r o y d e nf l e t c h e rg o l d f a r bs h a n n o c b r c o n s t a n tb i tr a t e c cc o n t r o lc o n n e c t i o n c w n d c o n g e s t i o nw i n d o w d c c p d a t a 伊锄c o n g e s t i o nc o n t r o lp r o t o c o l e c n 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 e w m a e x p o n e n t i a lw e i g h t e dm o v i n ga v e r a g e f t p f i l et r a n s f e rp r o t o c o l i c m p i n t e r a c tc o n t r o lm e s s a g ep r o t o c o l i p i n t e r n e tp r o t o c o l l m i l i l l e a rm a t i r xi n e q u a l i t y m s s 。 m a x i m u ms e g m e n ts i z e n s2 n t e w o r ks i m u l a t o r2 p d p r o p o r t i o n a ld e r i v a t i v e p f c p r o b a b i l i t yf u z z yc o n t r o l p i p r o p o r t i o n a li n t e g r a l p i d p r o p o r t i o n a li n t e g r a ld e r i v a t i v e p s o p a r t i c l es w a r mo p t i m i z e r r e d r a n d o me a r l yd e t e c t i o n 确认 和式增加积式减少 自适应多层e c n 自适应优化比例控制器 主动队列管理 自适应虚拟队列 布莱顿弗莱彻戈德香农 常比特速率 控制连接 拥塞窗口 数据报拥塞控制协议 显式拥塞指示 指数加权滑动平均 文件传输协议 互联网控制消息协议 网络互连协议 线性矩阵不等式 最大段长度 网络仿真器2 比例微分 概率模糊控制 比例积分 比例积分微分 粒子群优化算法 随机早期检测 南京【1 人学博i j 研究生学位论文 缩略语表 r t t s a p i s s t h r e s h t c p t f r c u d p r o u n dt r i pt i m e s t a b l ea d a p t i v ep r o p o r t i o n a li n t e g r a l s l o ws t a r tt h r e s h o l d t r a n s m i s s i o nc o n t r o lp r o t o c o l t c p f r i e n d l yr a t ec o n t r o l u s e rd a t a g r a mp r o t o c 0 1 v i i 往返时延 稳定自适应比例积分 慢启动阀值 传输控制协议 t c p 友好速率控制 用户数据报协议 南京邮l 【1 人学博i j 研究生学位论文图表说1 9 j 图表说明 图2 1吞吐量和响应时间随负载的变化6 图2 2i n t e r n e t 网络的不均衡性7 图2 3p o w e r 函数1 0 图3 1 简化的动态模型3 2 图3 2 时滞二阶闭环反馈控制模型3 2 图3 3p i 控制系统。3 3 图3 4 最优非线性p i 控制器的结构3 5 图3 5 网络拓扑结构3 8 图3 6 路由器队列长度随时间变化的仿真结果4 1 - 图4 1p i d 控制系统原理框图4 3 图4 2 简化的动态模型4 5 图4 3时滞二阶闭环反馈控制模型4 5 图4 4 基于粒子群优化的p i d 主动队列管理算法结构5 0 图4 5改进p s o 算法优化p i d 控制器参数流程图5 卜 图4 6 网络拓扑结构5 2 图4 7 路由器队列长度随时间变化的仿真结果5 4 图4 8 路由器队列长度随时间变化的仿真结果5 6 图5 1 积分反步法示意图6 1 图5 2 网络拓扑结构6 4 图5 3 算法性能对比6 5 图5 4 算法性能对比6 6 图5 5 算法性能对比6 7 图6 1滑模变结构控制下的典型相图7 0 图6 2 控制切换中延迟造成的抖动7 2 图6 3 模糊输入砖，的隶属度函数7 6 南京1 1 1 1 91 乜人学博：ij 研究生学位论义图表说i 刃 图6 4 模糊输出埘，的隶属度函数7 6 图6 5 网络拓扑结构7 7 图6 6 三种算法性能对比7 8 图6 7 三种算法性能对比：7 9 图6 8 三种算法性能对比一8 0 图6 9 网络拓扑结构8 2 图6 1 0 三种算法性能对比8 3 图6 1 1 三种算法性能对比8 4 图6 1 2 三种算法性能对比8 4 图6 1 3 三种算法路由器丢包率对比8 7 图6 1 4 三种算法路由器吞吐量对比8 7 图6 1 5 三种算法路由器丢包率对比8 8 图6 1 6 三种算法路由器吞吐量对比8 8 图6 1 7 三种算法路由器丢包率对比8 9 图6 1 8 三种算法路由器吞吐量对比8 9 图7 1一元凹、凸函数几何对比9 1 - 图7 2网络仿真试验拓扑结构9 7 图7 3 基于梯度下降法价格计算下速率、价格仿真结果9 8 图7 4 基于b f g s 方法的拥塞速率控制算法下速率、价格仿真结果9 8 表3 1f t p 流的仿真结果4 2 一 表4 1f t p 流的仿真结果5 4 表4 2 基于o n o f f 的c b r 流的仿真结果5 6 - 表5 1 数据流吞吐量的平均值以及标准差6 7 表5 2 数据流分组丢失率的平均值以及标准差6 7 表6 1 数据流吞吐量的平均值以及标准差8 0 表6 2 数据流分组丢失率的平均值以及标准差8 卜 表6 3 数据流带宽分配的公平性指标8 卜 南京i i i g t l l 人学博。i ：研究生学位论文 图表说i 删 表6 4数据流吞吐量的平均值以及标准差8 5 表6