ch3-3(服务质量路由)-391107003

服务质量路由主要内容QoS路由（QoSR）的目标网络模型和QoS度量服务质量路由概述状态信息维护三类路由策略单播QoSR算法算法有效性分析QoS路由相关问题什么是QoSR[1]当前的InternetBesteffort基于单一度量的最短路径（最小跳数）进行路由服务质量是网络传输业务流时，业务流对网络服务的需求集合其中业务流是指与特定QoS要求相关的从源到目的地的分组流什么是QoSR提供QoS保证的路由QoSR是一种基于数据流QoS请求和网络可用资源进行路由的机制。或者QoSR是一种动态路由协议，并且在其路径选择标准里可以包含QoS参数。可用带宽链路和端到端路径利用率资源消费量延迟跳数抖动QoSR的目标为每一个接纳的QoS业务连接请求，找到满足其QoS要求的可行路径。优化全局资源利用率，平衡网络负载，从而最大化网络接受其他QoS请求的能力。主要内容QoS路由（QoSR）的目标网络模型和QoS度量服务质量路由概述状态信息维护三类路由策略单播QoSR算法算法有效性分析QoS路由相关问题网络模型－有权图QoS度量可加性度量延迟，花费等等可乘性度量丢失率最小性度量带宽多约束优化与NPC求解多个约束条件的优化路径是NPC问题。（1）链路优化问题，例如带宽优化路由是寻找具有最大瓶颈链路带宽的可行路径。（2）链路受限问题，例如带宽受限路由是寻找瓶颈链路带宽大于一定要求的可行路径。（3）路径优化问题，例如延迟最小路由是在所有可行路径中寻找从源到目的地延迟最小的路径。（4）路径受限问题，如延迟受限路由要求路径的总延迟满足一定的要求。主要内容QoS路由（QoSR）的目标网络模型和QoS度量服务质量路由概述状态信息维护三类路由策略单播QoSR算法算法有效性分析QoS路由相关问题IETF的服务质量路由框架分层的QoSR框架域内鼓励QoSR的多样性，QoSR所提供的服务不仅能够根据当前网络状态进行动态的路径计算，还应该能够为某些服务类型（ClassofService）提供静态配置的路径。域间QoSR则更强调稳定性和可扩展性，路由不应该依靠具有过高动态性的网络状态信息，同时域间所交换的状态信息应该保持相对稳定。状态信息维护和路由计算为完成QoSR的两个目标，QoSR的主要内容包括两方面：测量、收集并维护网络状态信息本地状态的获取状态信息的传播根据维护的网络状态信息计算优化的可行路径，主要由QoSR算法计算，而各种算法往往需要依据节点所维护的状态信息进行计算状态信息分类－本地状态一个节点或者该节点直接连接的链路所具有的状态信息称为本地状态。本地状态是其他状态信息的基础，具体包括传输延迟、排队延迟、抖动、CPU占用率、链路开销、可用带宽、丢失率等。研究QoSR问题时，通常假设每个节点已经采用某种方法知道所需要的各种本地状态。状态信息分类－全局状态网络中各个节点的本地状态的组合称为全局状态。基于全局状态的QoSR问题，较容易设计启发式算法，因此很多研究工作都是基于节点已知全局状态的。随着网络规模扩大，面临着全局状态爆炸的问题。一般来说，要求一个节点保存全局状态、并通过它计算可行路径，在空间和时间上都是不可行的。状态信息分类－聚集的（全局）状态为了减小网络全局状态的信息量、提高可扩展性，可以采用分层的网络结构，将低层网络的内部状态信息压缩聚集后再向高层传播。在此过程中，节点所获得的压缩后的全局状态，称为聚集（的全局）状态。状态信息交互对链路状态协议（OSPF）和距离向量协议（RIP）进行扩展，使其能交互多种本地链路状态信息。协议状态的交互间隔周期性交互网络状态的变化所触发变化触发和周期性交互相结合三类路由策略源路由分布式路由层次化路由三类路由策略－源路由每个源节点收集和维护完整的全局状态，只在发送数据的源节点计算从源节点到目标节点的完整的可行路径。为建立连接，源节点通过控制信息通知这条路径上的其他节点如何进行路由。源路由的主要问题：由于源路由需要通过链路状态交互，因而维护全局状态的开销很大；源节点根据全局状态计算可行路径，时间和空间开销很大；源节点所维护的全局状态，其陈旧性对路由的性能影响很大。三类路由策略－分布式路由每个节点收集和维护一定的网络状态信息，网络中的多个不同节点基于这些信息进行独立的分布式计算，从而获得可行路径的路由策略称为分布式路由。优点符合当前Internet的路由特点。减小了计算复杂性并具有良好的可扩展性。缺点分布式处理复杂，难以设计好的启发式算法。每个节点单独计算，可能由于信息不一致导致出现路由回路。三类路由策略－层次化路由网络中的节点通过聚集形成多层次的拓扑结构，每个物理节点保存聚集状态。为建立连接，源节点沿着可行路径发送控制信息，当一个组的边界节点作为代表这个组的逻辑节点而收到控制信息时，使用源路由的方式将可行路径扩展，直到通过这个组。提高了可扩展性。状态聚集容易造成信息丢失，给QoSR带来负面影响。主要内容QoS路由（QoSR）的目标网络模型和QoS度量服务质量路由概述状态信息维护三类路由策略单播QoSR算法算法有效性分析QoS路由相关问题单播QoSR算法多项式非启发类探测类限定QoS度量类路径子空间搜索类QoS度量相关类花费函数类概率求解类

多项式非启发类Wang和Crowcroft使用Dijkstra最短路径树算法[2]实现了带宽延迟受限的源路由求解。首先在网络拓扑图中将带宽不足要求的链路剪除掉，然后再以延迟为关键字使用最短路径树算法计算。这样求得的路径满足QoS要求，并且具有最短延迟。

多项式非启发类对于分布式算法，对最短最宽路径提出了预计算方式。两个节点间的最宽路径是指这两个节点之间所有的路径中，瓶颈带宽最大的路径。最短最宽路径（Shortest-WidestPath）是指在多条最宽路径中延迟最小的路径。每个节点通过链路状态协议维护全局状态，并使用扩展Bellman-Ford算法（或Dijkstra算法）算法为每个可能的连接目的地预先计算出下一跳（NextHop），这样在连接请求到达时只需要简单的查找路由表就可以了。在各个节点网络状态信息一致的情况下，算法保证无回路。

探测类探测类算法的思想是从源节点开始，通过逐个询问其他节点，逐步逼近并到达目标节点。算法通常基于广播和多路路由的机制，在多条路径中寻找可行路径的方式，而询问抵达目标节点前，不能断定可行路径。为了避免回路和扩散重复信息，节点需要记录大量探测数据，需要较大的开销。探测法往往需要较长的路由时间，但探测可以有效的与资源预留相结合。

探测类Shin和Chou设计了延迟受限的分布式算法[3]。每个节点不需要保存全局状态，而通过广播方式从源向目的节点传送累加了延迟的路由信息。中间节点在收到路由信息时，首先累加自己的延迟，如果仍然小于规定的延迟，则再转发给其他邻居。收到的路由信息必须满足以下两个条件之一：它是第一次收到该信息；信息中累计的延迟比该节点原来收到的小。路由信息的扩散路径就是延迟受限的可行路径。探测类Chen和Nahrstedt提出了一种分布式路由的框架[4]。该框架与广播机制类似，每个节点只保存本地状态，在连接请求时，使用基于广播的选择探测方法寻找可行路径。为降低上述Shin-Chou算法的通信开销(1)根据到目的节点的拓扑距离，探测只在一个有选择的子集上转发；(2)限制路径长度，并在探测失败时动态的增加这个长度。该算法实际上是在路由时间和通信开销之间选择的折衷，因为探测失败时，会增加路由时间和通信开销。限定QoS度量Chen-Nahrstedt设计了多重路径受限的源路由算法[5]。算法的思想是将QoS度量的取值范围R或Z映射到一个有限集合C，这样保证多项式可解。限定QoS度量路径子空间搜索Salama等人对复杂度为NPC的延迟受限的最小花费问题（DCLC）设计了分布式启发算法[6]。为每个可能的目的网络，每个节点保存一个花费向量和一个延迟向量。为建立DCLC可行路径，源节点向目的节点发送一个控制信息，已经部分建立的可行路径的末端节点收到该信息后，将信息继续向目标节点传递。设（i,j）是从i到目标节点的最小花费路径中下一跳的链路，（i,k）为最小延迟路径中下一跳的链路，则传递规则是：只要从j开始的最小花费路径的延迟加上从节点开始的路径延迟仍然满足QoS限制，节点就选择（i,j）；否则选择(i,k)。由于算法本质上可能产生回路，因此作者设计了检测回路并遇到回路时回退的方法。

算法的思想是优先选择最小花费路径。QoS度量相关如果所有的QoS度量都与某一类度量相关，那么QoSR问题也可在多项式时间内求解。基于这种思想，Ma-steenkiste证明当网络中使用一类加权公平队列（WFQ）（如调度算法[7]）时，端到端延迟、抖动、队列长度等都是带宽的函数，而不再彼此独立，这样原来多限制的NPC问题就可能简化[8]。

花费函数类为了降低QoSR算法的复杂度和提供更好的QoS支持，一种可能的方式是通过研究花费函数，从而保证所计算的最小花费路径能够满足QoS需求。[9]中提出了下面的花费函数主要内容QoS路由（QoSR）的目标网络模型和QoS度量服务质量路由概述状态信息维护三类路由策略单播QoSR算法算法有效性分析QoS路由相关问题算法有效性分析路由回路问题，回忆算法[6]。回路检测。回路避免，Sun和Landgendorfer[10]。算法有效性分析Sobrinho通过代数学方法详细研究了分布式QoSR中路由回路和最短路径问题[11]。定义了关于链路度量的二元操作和一个抽象的全序关系，以及在这个关系中路径度量的保序性。保序性是指，对任意两条路径P、Q，如果给这两条路径P、Q同时追加上路径L时，在序关系中P和Q的关系与（P+L）和（Q+L）的序关系相同（也就是说追加过程不改变原来路径度量的序关系）。文章证明，路径中QoS限制的度量函数的保序性，是能够成功使用通用Dijkstra算法计算最短路径的充要条件；否则计算过程中可能产生回路。

算法有效性分析在研究QoSR问题时，通常假设每个节点已知本地状态信息，并通过链路状态协议或距离向量协议的交互获得（聚集的）全局状态。然而，这些状态信息往往是不精确的（或者称为陈旧的）[12]，其原因包括以下三点：传播本地状态的过程中，有不可忽略的网络传输延迟和协议交互延迟；网络状态是不断更新的（如可用带宽、延迟），考虑到传输网络状态信息的开销，所以路由更新间隔不可能无限小（定期更新的时间间隔或者触发更新的触发门限）；层次化的网络结构造成信息压缩。算法有效性分析由于信息的陈旧性可能导致建连失败，因此可以考虑在陈旧信息下，如何求得以最大概率满足QoS限制的可行路径。基于源路由的链路状态模型，Guerin和Orda研究了在不精确的网络状态下，带宽和延迟分别受限的QoSR问题[13]。源节点对网络中的每条链路L具有概率分布函数PL(w)，表示链路具有剩余w个单位带宽的概率。带宽受限路由的任务就是寻找一条路径，能够以最大概率满足新的QoS连接请求所要求的x个单位带宽。这样，以为链路的度量，使用最短路径树算法即可求解。

主要内容QoS路由（QoSR）的目标网络模型和QoS度量服务质量路由概述状态信息维护三类路由策略单播QoSR算法算法有效性分析QoS路由相关问题QoS路由相关问题－接纳控制QoS业务流具有面向连接的特性，因此在业务流进入网络前，通常具有QoS连接请求和接纳控制的过程。对于接纳的QoS请求，网络应该提供足够的资源保证该业务的QoS要求。在两种情况下，网络拒绝接纳一个业务流的QoS连接请求：找不到具有足够资源的路径接纳该业务流。造成这种状况的原因是网络没有足够的资源，或者由于算法的制约没有能力找到满足QoS限制的路径。考虑到后续QoS请求，为达到平衡负载、最大化网络利用率和吞吐量，而拒绝不合理的QoS请求。

QoS路由相关问题－QoS协商对于不能接纳的QoS请求，可以依据网络的当前状况和已经找到的最佳路径，采用QoS协商的机制在业务和网络服务之间重新协商QoS要求。例如网络带宽不足以传输精确图象时，可以通过QoS协商降低带宽要求，传输经过进一步压缩的图象。QoS路由相关问题－流量工程流量工程（TrafficEngineering）研究的主要内容是如何通过平衡负载来降低业务流通过网络时拥塞的概率。如何通过QoSR来平衡负载是流量工程的一个重要内容，而通过平衡负载来提高网络的接纳能力也是QoSR研究的一个重要组成部分。流量工程并不能取代QoSR，例如QoSR可以通过区分业务类型，在不增加资源的前提下，使每个业务获得更为满意的服务。QoS路由相关问题－MPLSMPLS是一种快速交换的路由方案，这种机制对实现QoS很有帮助。MPLS域由具有MPLS交换功能的路由器组成，在域边界为每个分组加上标签，在域内部使用标签交换的方法转发分组。因此MPLS可以与QoSR结合起来，使用QoSR在域边界选择满足QoS要求的路径，然后通过MPLS转发。MPLS也可以为QoSR提供更为精确的网络状态信息，并可以扩展MPLS以预留资源。参考文献[1]崔勇,吴建平,徐恪.互联网络服务质量路由算法研究综述.软件学报.2002.11.[2]Z.WangandJ.Crowcroft,QoSRoutingforSupportingResourceReservation.IEEEJournalonSelectedAreasinCommunications,September1996.[3]K.G.ShinandC.-C.Chou,ADistributedRoute-SelectionSchemeforEstablishingReal-TimeChannel.SixthIFIPInt'lConf.onHighPerformanceNetworkingConf.(HPN'95),pages319-329},Sep.1995.[4]S.ChenandK.Nahrstedt,DistributedQuality-of-ServiceRoutinginHigh-SpeedNetworksBasedonSelectiveProbing.LocalComputerNetworks(LCN'98),Page(s):80-89,1998.[5]S.ChenandK.Nahrstedt,OnFindingMulti-ConstrainedPaths.IEEEICC'98,June1998.[6]H.F.Salama,D.S.Reeves,andY.Viniotis,ADistributedAlgorithmforDelay-ConstrainedUnicastRouting.IEEEINFOCOM'97,Japan,April1997.[7]J.BennettandH.Zhang,HierarchicalPacketFairQueueingAlgorithms.ACMSIGCOMM'96,August1996.参考文献[8]Q.MaandP.Steenkiste,Quality-of-ServiceRoutingwithPerformanceGuarantees.4thInternationalIF