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

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