服务质量路由

服务质量路由苏伟北京交通大学下一代互联网互联设备国家工程实验室第一部分服务质量路由概述服务质量的定义服务质量（QualityofService，QoS）是网络传输业务流时，业务流对网络服务的需求集合。其中业务流是指与特定QoS相关的从源到目的地的分组流。QoS是应用业务对网络传输服务所提的一组可度量的要求，包括带宽、端到端延迟、分组丢失率、抖动、花费的代价等。QoS需求可以通过一个限制集来描述。这里的限制包括链路限制、路径限制、树限制。QoSR定义QoSR（QualityofServiceRouting）是一种基于数据流QoS请求和网络可用资源进行路由的机制。与传统路由协议相比，QoSR包含的参数更广，而且往往同时包含多个参数。根据这些参数计算可行路径。根据可行路径算法模式不同，可分为预计算和在线计算。QoSR中的难点不同应用对QoS的要求差别很大，同一应用也可能涉及多个参数，这往往是个NPC(Non-determinsticPolynomialComplete)问题；网络状态不断动态变化，以及状态信息的传输延迟等问题，造成节点不可能具有整个网络当前时刻的状态信息，进而影响QoSR的性能；QoSR和当前尽力而为的路由协议体系相矛盾。网络模型可以用有权图G（V，E）表示。QoS度量可加性度量：延迟、抖动、花费、转发跳数可乘性度量：分组丢失率最小性度量：瓶颈带宽多重最小性度量可以在多项式时间内完成；多重可加性（可乘性）度量一般不能在多项式时间内完成。QoS中的状态信息网络状态信息是指与网络当前的状态有关的各种信息，是QoSR以及其他路由算法进行可行路径计算的依据。按照网络状态信息所在的位置，可以分为本地状态、全局状态和聚集状态三类。本地状态：节点或与节点直接相连链路具有的状态信息。全局状态：网络中各节点本地状态的集合。聚集状态：压缩后的全局状态。原始状态聚集后的状态状态信息的维护可采用链路状态协议或距离矢量协议交换。按交互间隔可分为：周期方式、触发方式、综合方式。有三种路由策略：源路由、分布式路由、层次化路由。多约束优化4类基本问题：链路优化问题、链路受限问题、路径优化问题、路径受限问题。前两者的参数是最小性度量，后两者的参数是可加性（可乘性度量）。多项式时间可解问题：链路受限－链路优化问题、多重链路受限问题、链路受限－路径受限问题、链路优化－路径受限问题等。NPC问题：路径受限－路径优化问题和多重路径受限问题等。第二部分单播QoSR算法多项式非启发类针对多项式可解问题，是其他QoSR算法的基础。经常使用B-F算法或Dijkstra算法。例如：带宽延迟受限的问题，先把不满足带宽要求的链路去掉，然后以延迟为参数按最短路径树算法计算。伪多项式非启发类典型代表：EBFA（扩展B-F算法）。解决问题：多重路径受限。核心思想：在偏序集中寻找最小元。注意：最优路径不唯一。节点u维护集合PATH(u)（所有从srt到u的最优路径），对每一条边（u，v），执行比较和判断。探测类基本思想：从源节点开始，逐个询问其他节点，逐步逼近并达到目标节点。为避免回路和重复消息，节点需记录大量探测数据。与资源预留结合的分布式多路路由算法。延迟受限的分布式算法：每个节点通过广播方式从源到目的传送累加了延迟的路由信息。转发时要满足一定的条件。上述算法的演变：探测在某个子集上进行；限制路径长度等。限定QoS度量类思想：除一类QoS度量外的所有QoS度量限定在一个有限集上，可以使问题由NPC转化为P问题。文献“OnFindingMulti-ConstrainedPaths.ChenS,NahrstedtK.IEEEICC,1998”例如，将QoS度量的取值范围从R或Z映射到一个有限集合C。路径子空间搜索类算法直接限制拓扑图中的某条路径或路径数量，在路径集合的子空间搜索可行路径。不同于探测类算法，在源节点或中间节点就可以计算可行路径，不一定询问到源节点。例如EBFA算法中，限制|PATH|≤X，若不满足则加入最短路径。QoS度量相关类若所有QoS度量与某一类度量相关，可以将所有度量转化为这一种度量。已经证明，当网络中使用一类加权公平队列时，端到端延迟、抖动、队列长度都是带宽的函数，从而可以简化该问题的求解。概率求解类在不精确的网络状态下，以一定的概率选择路径。算法的有效性分析路由回路问题：度量的多样性。避免回路：保序性。陈旧信息的影响。网络模型的影响：Well-known;随机拓扑结构；特定拓扑结构。QoS路由相关问题分析资源预留：（1）找到可行路径（2）沿着可行路径预留资源接纳控制：不