TCP-IP协议网络拥塞控制若干问题的研究

TCP/IP网络拥塞控制若干问题的研究,答辩人：何凌导师：井元伟教授,结论与展望,主要工作,绪论,第一章绪论,网络拥塞的基本概念拥塞是一种持续过载的网络状态。此时用户对网络资源的需求超过了其固有的容量。网络拥塞产生的原因存储空间不足带宽容量不足处理器速度慢、能力弱拥塞控制的基本思想采取某种控制措施减少或避免网络中出现拥塞现象。,图1.1网络负载与吞吐量及响应时间的关系,基于源端的TCP拥塞控制机制,“和式增加积式减少（AIMD）”,基于窗口的闭环控制方式,慢启动,拥塞避免,快速重传,快速恢复,第一章绪论,基于路由器的IP拥塞控制机制,通过路由器等中间节点设备采用队列算法实现,第一章绪论,在这类算法中TCP的连接是一种互动的行为，AQM控制器可以看作一个梯度优化问题，算法的目标是最大化网络利用率。Kelly等学者基于优化理论49提出了一个分散拥塞控制框架，从而建立了TCP速率控制的模型。Kunniyur在Kelly源端速率模型的基础上提出AVQ算法。Low等基于优化理论提出了TCP/AQM对偶性模型。,基于优化理论的拥塞控制算法,第一章绪论,基于控制理论的拥塞控制算法,第一章绪论,从控制理论角度，拥塞控制算法分为开环控制和闭环控制两大类。,Misra等63提出了TCP/AQM微分方程模型。,图1.8TCP拥塞控制与AQM算法组成的反馈控制模型,文献64运用经典控制理论证明了采用RED控制的的系统中稳定时控制器参数所要满足的条件,Hollot等65研究了在AQM中采用经典的PI控制器的设计方法。,文献67则直接运用状态反馈控制理论，给出了状态反馈控制器的设计。,现有算法存在的问题,第一章绪论,已有的AQM设计大多是依赖于确定的网络模型，没有考虑到参数的时变性以及模型的不确定性的影响。拥塞控制系统的稳定性分析是控制理论的难点课题。,第五章基于显式速率反馈的拥塞控制算法,第四章基于自适应灰色预测的VRC虚速率算法,第二章基于IMC-Smith算法的AQM策略,第一章绪论,第三章AQM中的模糊-Smith算法,第六章基于价格策略的拥塞控制机制,本文的主要工作,第七章网络拥塞控制算法的稳定性分析,TCP流量窗口控制机制动态模型：,第二章基于IMC-Smith的AQM策略,图2.5基于TCP流体模型的网络拥塞反馈控制结构图,网络控制系统建模,图2.2哑铃型拓扑结构的分组交换网络,Smith预估控制系统转换成如下图的等价结构：,得到Smith预估控制系统的内模控制结构,按照内模控制算法设计控制器,第二章基于IMC-Smith的AQM策略,(2.24),图2.7IMC-Smith控制系统结构框图,仿真研究,图2.8模型匹配时IMC-Smith控制算法仿真曲线,图2.9滞后时间变化时仿真曲线,第二章基于IMC-Smith的AQM策略,图2.10模型失配时仿真曲线,图2.11激活的TCP连接数变化时的仿真曲线,第二章基于IMC-Smith的AQM策略,本章小结本章从控制理论的角度描述了带AQM的网络拥塞闭环控制系统结构，给出了IP网络系统受控对象的一种传递函数模型。并提出了一种结合内模控制器和Smith预估补偿控制器的IMC-Smith控制算法，通过仿真实验表明，该策略能有效克服网络时延的影响，对网络模型参数的变化具有较好的鲁棒性。,第三章AQM中的模糊-Smith算法,设计目标：基于模糊Smith设计一个AQM控制器来稳定路由器中的队列长度使其在目标队列附近,图3.1模糊-Smith系统结构,图3.4改进的Smith预估补偿控制原理图,第三章AQM中的模糊-Smith算法,在原对象模型与Smith预估器模型的比较器之后串上一个低通滤波器，可以大大减少模型失配的敏感，增加Smith预估控制系统鲁棒性。,由二维模糊控制器实现,队列长度的误差及误差的变化率作为模糊控制器的输入,队列长度的误差分为五个模糊子集，为负小、负大、零、正小、正大,误差的变化率也分为五个模糊子集，为负小、负大、零、正小、正大,模糊控制器的设计,丢弃概率作为模糊控制器的输出,第三章AQM中的模糊-Smith算法,E,表3.3模糊控制器的控制规则表,模糊控制器的输出由下式给出：,(3.6),第三章AQM中的模糊-Smith算法,仿真,图3.8小时滞时三种控制器比较,图3.9大时滞时三种控制器比较,图3.10参数变化时三种控制器比较,第三章AQM中的模糊-Smith算法,本章小结本章从控制理论的角度描述了带AQM的网络拥塞闭环控制系统结构，提出了一种结合模糊控制器和Smith预估补偿控制器的模糊Smith控制算法，通过仿真实验表明，该策略能有效克服网络时延的影响，对网络模型参数的变化具有较好的鲁棒性。,第三章AQM中的模糊-Smith算法,第四章基于灰色预测自适应PID理论的VRC算法,图4.2灰色预测自适应PID网络控制系统框图,AQM算法分为两种类型：1)基于速率的拥塞控制，控制拥塞链路的数据流的速率；2)基于队列的拥塞控制，控制拥塞链路的队列长度。,文献97,98提出了一种虚速率控制算法(VRC),VRC的标记概率表达式：,(4.10),(4.14),我们采用自适应的形式，将上式写成,式中：,第四章基于灰色预测自适应PID理论的VRC算法,设：,(4.16),(4.18),(4.19),设系统的性能指标为,式中d为下文所指的预测时间。,第四章基于灰色预测自适应PID理论的VRC算法,灰色预测器的输入时间序列如下：,得到原始数据对t+d时刻的预测为,(4.20),(4.24),(4.25),(4.35),稳定性分析,设离散Lyapunov函数为：,第四章基于灰色预测自适应PID理论的VRC算法,当时，系统稳定,(4.36),(4.37),瓶颈链路中单路TCP连接,图4.3局域网无参数改变时的队列长度,仿真性能分析,图4.4局域网参数改变时的队列长度,第四章基于灰色预测自适应PID理论的VRC算法,图4.5广域网无参数改变时的队列长度,图4.6广域网参数改变时的队列长度,瓶颈链路中多路TCP连接,图4.7TCP连接带宽,第四章基于灰色预测自适应PID理论的VRC算法,图4.8局域网无参数改变时的队列长度,图4.9局域网参数改变时的队列长度,图4.10广域网无参数改变时的队列长度,图4.11广域网较坏网络状况时的队列长度,本章小结本章针对基于PID控制的虚速率VRC主动队列管理算法加以改进，提出了一种新的VRC算法。将二次型性能指标引入到PID控制器的整定过程中，按照性能指标的负梯度方向修改加权系数，实现了PID的自适应最优控制，同时将自适应PID与灰色预测器相结合，用预测结果代替被控对象测量值，补偿了网络时滞，实现了“事先调节”。并且对算法进行了稳定性分析。此外，本章通过细致的仿真实验分析了算法在改善网络性能方面的有效性。算法能稳定地适应网络环境动态变化，超调量小，振荡轻微，快速收敛于路由器队列长度期望值，自适应克服了网络干扰和滞后特性的影响。,第四章基于灰色预测自适应PID理论的VRC算法,缓冲器中某一TCP连接的队列长度可由下列方程所确定：,第五章基于显式速率反馈的拥塞控制算法,(5.1),控制器设计,控制性能指标：,稳定性条件：当，。充分利用带宽条件：当，队列长度。,图5.3控制系统图,系统的闭环特征方程为：,(5.4),令闭环特征方程在处有双重极点,(5.6),(5.7),第五章基于显式速率反馈的拥塞控制算法,设计滤波器,第五章基于显式速率反馈的拥塞控制算法,令输入到的期望传递函数为：,(5.8),令,(5.9),第五章基于显式速率反馈的拥塞控制算法,控制算法仿真研究,瓶颈链路中仅有单路TCP连接,图5.6局域网无参数改变时的队列长度,图5.7局域网参数改变时的队列长度,图5.8广域网无参数改变时的队列长度,图5.9广域网参数改变时的队列长度,瓶颈链路中多路TCP连接,图4.7TCP连接带宽,图5.11局域网无参数改变时的队列长度,图5.12局域网参数改变时的队列长度,图5.13广域网无参数改变时的队列长度,图5.14广域网较坏网络状况时的队列长度,第五章基于显式速率反馈的拥塞控制算法,第五章基于显式速率反馈的拥塞控制算法,本章小结,本章将Smith控制算法应用于TCP拥塞控制，较好地克服了网络的传播时延给拥塞控制所带来的不利影响，使源端的TCP发送窗口能快速响应网络状态的变化，即避免了拥塞的发生，又保证了瓶颈链路的带宽得到充分利用，使网络处于良好的运行状态。而且，当控制系统进入稳定后，能使TCP发送窗口的变化很平稳。控制系统的良好鲁棒性又使本方案具有很大的实用价值。,第六章基于价格策略的拥塞控制机制,系统模型与分析,考虑一个具有资源集合的网络，资源的有限容量为C,集合N中的用户以的速率来使用网络，对于整个网络来说，资源负载为,资源使用率为。对于每一个用户，其总体效用如下：,整个系统的总体效用如下：,(6.1),(6.2),用户效用最大化的解,系统效用最大化的解,第六章基于价格策略的拥塞控制机制,基于资源占有率的价格策略,规定在资源使用率为时，价格函数设定为。,令,第六章基于价格策略的拥塞控制机制,(6.11),基于激励Stackelberg的价格策略,Stackelberg激励策略是对策论中的一种策略，又称主从策略。在激励策略中，分为主方和从方。主方发布激励策略，当从方与主方提供的目标不一致时，惩罚函数将激励或迫使从方采取对整个整体有益的行为。一个资源分配向量构成Nash均衡,意味着没有用户有单方面改变自己策略(所使用资源的数量)的动机。,第六章基于价格策略的拥塞控制机制,在这里的这个策略中，网络商是主方，用户是满足Nash平衡点的从方，允许网络方和用户方任意改变速率xs，s=1,2,n。引入Stackelberg策略：其中是待确定的函数。是系统效用最大化的解。,(6.19),线性激励策略,假设为线性函数，即：,令,第六章基于价格策略的拥塞控制机制,(6.22),(6.23),非线性激励策略,当资源占有率小于等于20%，即时，考虑非线性策略：当资源占有率大于等于90%，即时，考虑非线性策略：,第六章基于价格策略的拥塞控制机制,(6.25),(6.26),数值例子和仿真,图6.2用户的效用函数曲线,图6.3系统的效用函数曲线,第六章基于价格策略的拥塞控制机制,图6.4采取了基于资源占有率的价格策略后用户的效用函数曲线,图6.5的情况下采取线性激励策略后的用户效用函数等高线图,图6.6情况下采取了非线性激励策略后用户效用函数的等高线图,图6.7情况下采取了非线性激励策略后的价格曲线,第六章基于价格策略的拥塞控制机制,本章小结本章从经济学的角度出发，应用价格手段来实现网络的拥塞控制提出了两种价格策略，首先将资源占有率引入到价格策略中，构造了基于资源占有率的价格策略；另外将网络中的效用函数模型同对策论中的激励Stackelberg策略相结合，提出了基于激励Stackelberg的价格策略。通过仿真实验，得到了理想的结果，证明了两种策略的有效性。,TCP/AQM对偶性模型主导思想,链路,源端（用户）,反馈,价格,发送速率,调整,影响,效用函数,第七章网络拥塞控制算法的稳定性分析,对偶控制算法,对效用函数有如下两个假设:,在区间中效用函数是单调增的、严格凹的，并且连续二次可微的。的曲率被限制远离零的,即在上:对所有的有,第七章网络拥塞控制算法的稳定性分析,原始问题（拥塞控制的目标）,选取发送速率，使得：,第七章网络拥塞控制算法的稳定性分析,(7.4),对偶问题,目标为选取拥塞度量(即对偶变量),使得：,定义Lagrangian式子,第七章网络拥塞控制算法的稳定性分析,(7.5),(7.9),(7.7),(7.8),对偶问题的梯度算法,第七章网络拥塞控制算法的稳定性分析,(7.11),(7.13),对偶梯度算法的全局稳定性分析,第个缓冲器中的队列将有如下排队动态变化,第七章网络拥塞控制算法的稳定性分析,(7.14),(7.16),定理1忽略传输时延的情况下，由式(7.9),(7.12),(7.14)以及(7.13)组成的闭环系统(7.16)是全局稳定的。,证明：定义如下Lyapunov函数：,第七章网络拥塞控制算法的稳定性分析,定义一对角矩阵,由假设(2)有0,这里是一指示函数，如果成立则，否则为0。,第七章网络拥塞控制算法的稳定性分析,定义如下矩阵,定理得证。,第七章网络拥塞控制算法的稳定性分析,定理2式(7.28)的单源单链路闭环系统全局稳定的条件是，。,证明：定义如下Lyapunov函数：,第七章网络拥塞控制算法的稳定性分析,(7.28),(7.29),考虑回路时延的稳定性条件(单用户单链路),假设是单调减函数,对于任意给定时刻t，存在有，。,第七章网络拥塞控制算法的稳定性分析,由假设：,定理得证。,第七章网络拥塞控制算法的稳定性分析,本章小结：研究了对偶控制算法的全局稳定性。考虑在单瓶颈网络拓扑中利用Lyapunov稳定性理论对该算法的稳定性条件作了分析。在不考虑网络传输时延时，能保证在一般网络拓扑中的全局稳定性。在考虑传输时延时得到了算法参数与最大传输时延、算法步长选取之间的关系。,探索更准确的网络模型描述方法，提高网络受控模型的精度；对于AQM技术的