第7章 QoS路由.ppt

服务质量 为什么要服务质量 为什么要服务质量 为什么要服务质量 怎样保证服务质量 服务质量的研究部门 端到端的QoS参考模型 集成服务网络和区分服务网络 集成服务体系结构 集成服务体系结构 IntServ模型 IntServ模型 资源预留协议 资源预留协议 RSVP 的资源预留建立过程 IntServ的优缺点 区分服务体系结构 区分服务的基本思想 区分服务的基本思想 DiffServ的框架示意图 DiffServ的优缺点 IntServ 和 DiffServ的比较 多协议标签交换 QoS的实现机制 约束路由 约束路由 策略路由 QoS路由 QoS路由 QoS度量参数 QoS度量参数 QoS路由研究的主要内容 路由信息不准确的原因 QoS路由算法的分类 QoS路由算法的分类 单混合度量参数路由算法 多度量参数路由算法 多度量参数路由算法 QoS路由算法的分类 源路由算法 源路由算法 源路由算法 分布式路由算法 分布式路由算法 分布式路由算法 分层路由算法 分层路由算法 分层路由算法 QoS路由算法的分类 单播路由算法 单播路由算法 典型的单播路由算法 多播路由算法 典型的多播路由算法 智能技术在QoS路由中的应用 QoSR用于传统IP：为每个TOS值计算不同的最短路由 QoSR与IntServ：QoSR(寻找路由)，RSVP(预留资源) QoSR与Diffserv：有待研究，可能采用基于PHB /DSCP的选路 QoSR与MPLS：QoSR为MPLS业务量工程提供了方便, 而MPLS显式路由为业务量工程提供预计路由的支持,可减小QoSR的开销 目前，QoS路由算法涉及的度量参数有：带宽、延时、延时抖动、丢包率、跳数和费用。 根据运算规则，它们可以分为 加性度量参数 乘性度量参数 凹性度量参数 设m(u,v)为链路e(u,v)∈E的某一度量参数，对于任意路径p(u,v)=(u,i,j,…,k,v),各种度量参数如下 加性度量参数：如果度量m满足m(u,v)=m(u,i)+m(i,j)+…+m(k,v),则称m是加性的。例如：延时、延时抖动、跳数和费用 乘性度量参数：如果度量m满足m(u,v)=m(u,i)×m(i,j)×…×m(k,v),则称m是乘性的。例如：丢包率 凹性度量参数：如果度量m满足m(u,v)=min{m(u,i),m(i,j),…,m(k,v)},则称m是凹性的。例如：带宽 从应用背景看，目前QoS路由的研究分为 单播路由 多播路由 单播路由和多播路由都要解决以下三点 路由信息不准确问题 度量参数选择问题 寻路问题 网络的动态性 大型网络的状态聚集 不精确的计算 被隐藏的信息 根据业务的不同和参与者的多少 单播路由算法 多播路由算法 根据度量参数的组合方式 单混合度量参数路由算法 多度量参数路由算法 根据路由状态信息的维护机制和路径的计算方法 源路由算法 分布式路由算法 分层路由算法 根据度量参数的组合方式，路由算法可分为 单混合度量参数路由算法 多度量参数路由算法 QoS路由算法的复杂度关系到QoS路由算法的可实现性 多个不相干可加度量的QoS路由问题是一个NP完全问题，是数学界尚未解决的数学难题 合理解决多参数问题，能够降低算法的复杂度，把NP问题转换为P问题 单混合度量参数通过一个参数来表现多个参数的特性，从而把多度量参数问题转换为单度量参数问题 常用方法是以多个度量参数为变量构建函数，以单一的函数值作为选路的度量标准 两个缺点 不同特性的度量参数，很难合理设定运算规则 很难保证每个参数都满足要求 多度量参数是指在路由选择中对支持的多个度量参数同时加以考虑，此类问题大多为NP完全问题 如何在满足QoS要求的前提下，简化问题，降低算法的复杂度是多度量参数选择的主要问题 目前，降低算法复杂度的方法是从度量参数的某些相关性和度量参数对业务的重要性入手 选择主要度量参数法 量化度量参数法 参数定界法 结合节点控制策略，相关化多个参数 选择主要度量参数法：根据业务对不同参数要求的差异性，选取一个主要的参数，先依照这个参数进行路由选择；当有多条路径同时满足业务要求时，再按照其余参数从这些路径中选择合适的路径 量化度量参数法：按照一定的精度量化参数可以减小算法的复杂度和路由信息的开销，并能够在一定程度上保证所选路由的可用概率 参数定界法：通过构造函数将无界的实值参数映射为有界的整数参数，从而解决多参数的NPC问题 结合节点控制策略，相关化多个参数：将路由调度与基于速率的调度策略相结合，为经过节点控制的业务选择路由 根据路由状态信息的维护机制和路径的计算方法 源路由算法 分布式路由算法 分层路由算法 源路由算法的一般过程 在源路由中，每个节点维护一个全局的路由状态表，包括网络的拓扑结构和每条链路的状态信