服务质量选路的研究

　服务质量选路研究有助于提高网络效率，降低网络成本，同时使得网络运营商可为用户提供多种有区别的服务，因此现已成为研究的热点。

　　如何去寻找满足各种服务质量约束的路由，提供端到端的服务质量保证，同时使网络具有较好的资源利用率，是各种服务质量网络模型和方案的目标。因特网工程任务组(IETF)专门成立了约束路由工作组(PFWG)来指导相关研究工作。到目前为止，该工作组提出了多种模型和方案，比如因特网工程任务组的集成业务/资源预留(IntServ/RSVP)、区分业务(DiffServ)等IP QoS模型，以及多协议标记交换(MPLS)、流量工程和约束选路技术等。在这些模型和方案中，约束路由成为极为关键的部分[1-4]。有的文献认为约束选路和服务质量选路有差别，但人们通常将它们混用，目前已有较多文献对此进行研究。

　　与传统的“尽力而为”的路由选择相比，服务质量选路不仅关心源-宿的连通性，而且关心路由是否能够满足业务所提出的各种服务质量要求(比如时延约束、带宽约束、可靠性要求等)。因此，服务质量选路需要同时考虑业务需求和网络当前的可用资源状况，这包括两个方面：一是网络状态信息(比如可用资源)的管理，涉及到选择哪些网络状态信息来表述网络以方便于服务质量选路，如何保证网络节点保留信息的准确性(信息的准确性影响着服务质量选路算法的有效性)以及状态信息的更新等；二是利用获得的网络状态信息，使用选路算法计算相应的路由。

　　下面围绕网络状态信息管理、路由计算两个方面探讨服务质量选路中的相关问题及相应的解决方法。

　　1 网络状态信息管理

　　1.1 网络状态信息分类

　　对于服务质量选路算法，只知道网络连通性是不够的，还需要知道网络的当前可用资源情况(比如可用带宽、链路时延等度量参数)。常用的度量参数包括：带宽、代价、跳数、时延、时延抖动和丢失率。这些度量参数可以分为加性度量参数(比如代价、跳数、时延)、乘性度量参数(比如丢失率)和凹性度量参数(比如带宽)[1]。对于一条路径而言，加性约束意味着该路径的度量值是该路径所经过的各链路相应加性度量参数之和；乘性约束意味着路径的度量值是该路径所经过链路的相应乘性度量参数之积；凹性约束则意味着该路径的度量值为所经过链路中的最大或者最小凹性度量参数值。服务质量选路通常用一个或者多个度量参数作为选路标准，文献[4]证明，满足多个相互独立的参数限制的选路问题是非多项式完全(NP-complete)问题。对于非多项式完全问题，通常设计启发式算法加以解决。

　　1.2 网络状态信息处理

　　网络状态信息的收集和分发是服务质量选路的基础，包括两种方式：基于消息的(Message-based)信息处理和基于代理的(Agent-based)信息处理。基于消息式信息处理以消息方式在全网广播网络状态信息，如开放式最短路径优先(OSPF)和中间系统-中间系统(IS-IS)协议中的链路状态公告(LSA)消息。服务质量选路需要对路由协议进行相应的扩展，增加多种类型的链路状态公告。基于代理方式的信息处理具有一定的针对性，由一实体携带信息至目的地[5]。

　　路由信息的准确性影响着选路算法，路由信息的更新影响着网络中各节点记录的信息准确性，不准确的网络状态信息将可能造成路由选择的失败，重新进行路由计算、发送预约信令会增加网络开销和业务时延。在分布式路由中，不准确路由信息可能导致形成环路，出现死锁。网络状态信息更新的频率越高，则节点获得的信息准确性越高，但是引入的网络信息开销也越大。因此需要寻找一个合适的平衡点。通常更新方法可分为基于时间变化和基于带宽变化，有以下3种主要更新策略：

　　(1)周期性更新策略

　　周期性更新策略是基于时间变化的更新策略，每隔一个固定时间发送一次节点状态信息。

　　(2)带宽变化更新策略

　　带宽变化更新策略是基于带宽变化的更新策略。带宽变化更新策略每当带宽发生显著变化，发送一次状态信息。文献[6]提出了两种具体方式：一种是基于带宽门限的更新，当剩余带宽变化量超过一个门限时，就发送状态信息；一种是基于带宽分级的更新，即将带宽值分为几个等级，一旦剩余带宽从一个等级跳到另一个等级，则触发状态信息更新。

　　(3)有时间控制的更新策略

　　有时间控制的更新策略是在带宽变化策略基础上加入时间控制的更新策略。有时间控制的更新策略限制两次连续触发状态更新的最小时间隔，即设置钳制时间(Clamp-down timer)以控制状态信息的发送频率。

　　2 服务质量选路算法

　　在实际网络中要求服务质量选路算法效率高、复杂度低、扩展性强，并且能够灵活地适应变化的网络环境。根据度量约束的数量，服务质量选路算法可以分为单约束路由算法和多约束路由算法。单约束路由算法比较简单，当前研究较多的是多约束路由(MCP)问题，即要根据网络状态为源-宿节点对寻找满足多个约束限制的路由。当所求的路由是所有满足约束条件中的最优路由时，多约束路由被称为多约束最优路由(MCOP)问题，也被称为受限最短路由(RSP)问题。服务质量选路算法方法往往采用改进的Dijkstra算法或者改进的Bellman-Ford算法，根据算法对度量参数选择的不同以及改进的方法不同，不同的算法具不同的算法复杂度[2?3]。服务质量选路的核心问题是确定与网络状态相关的代价函数，并在网络拓扑中选择最优路由(或者选择可行路由)。

　　由于凹性约束可以通过选路预处理(删除不满足凹性约束的链路)加以处理，乘性约束可以通过对数处理方式将其转化为加性约束，因此下面我们只讨论典型的加性约束单播选路算法。

　　最为直接准确的选路方法是依次检查源-宿节点对之间的所有路由，看该路由是否满足约束条件，只要网络中存在一条可行路径，则受限Bellman-Ford(CBF)算法可以完成选路计算。还有一种完成选路计算算法为退却算法(Fallback algorithm)[7]，该算法按照顺序依次针对一个服务质量度量参数去选择最优路由，检查所得路由是否满足其他约束条件。

　　文献[8]针对双约束提出了拉格郎日松弛算法，其链路代价函数定义为一个线性函数l(i，j)=λ1w1+λ2w2 (其中，λ1和λ2是加权因子，是w1和w2链路的两个度量参数)。可以证明λ1=w1/(w1+w2)，λ2=w2/(w1+w2)时算法效率较高。同时文中建议使用非线性函数以便能更好地找到可行路由。文献[8]所提出的算法可以扩展到支持多个约束。

　　文献[9]针对双约束也提出两种在中间节点维护K条路由的启发式算法，要求节点记录多条最小组合权值的路由。

　　文献[10]使用后向-前向技术，提出了H_MCOP启发式算法，该算法寻找满足约束条件的可行路由，同时最小化一个非线性路由长度函数。文献[10]中使用了两个改进的Dijkstra算法：在反方向，构造新链路权值(该权值是链路所有度量参数的线性组合)，使用逆向Dijkstra算法计算所有节点到宿节点的最优路由，所得路由将用于H_MCOP的正向计算；在正向计算中，使用前向Dijkstra算法从源节点开始遍历节点。正向计算是基于整个源-宿路由的，由两部分构成：当前遍历所得的从源到中间节点的路由，反向计算时所得的从中间节点到宿节点的估计子路由。由于H_MCOP算法是在到达宿节点之前考虑整条路由，因此可以在搜索路由时预先知道路由的可行性。当路由可行时，算法才转向具有最小长度的可行路由上继续遍历，直到到达宿节点。

　　文献[11]和文献[12]提出的TAMCRA算法和SAMCRA算法基于以下3个概念：非线性函数作为路由长度函数；K条最短路由方法；非受控路由法则。参数K表示有K条最短路由纳入计算，其决定了算法的准确性。当K增加大到一定程度，TAMCRA将计算出一个准确最短路由。TAMCRA算法在中间节点只记录从源到当前节点的K条非受控路由，但TAMCRA找到的可行路由并不一定是最优路由。同时如果K过小，则不能保证一定找到网络中存在的可行路由。在文献[11]基础上，文献[12]提出了一个准确算法：SAMCRA，只要网络中有一条满足约束的路由，就一定能够找到。SAMCRA算法中每个节点记录的路由数目是不相同的，每个节点按需分配存储空间，而TAMCRA对每个节点分配相同的存储空间。

　　文献[13]通过构造函数将其中m-1个无界的实值参数映射为有界整数参数，将MCP问题转化为在新约束下最小化第一个参数的问题。该文中提出用扩展的Dijkstra算法和扩展的Bellman-Ford算法。当路由图比较稀疏并且节点数目比较多时，扩展的Bellman-Ford算法具有更好的性能。

　　文献[14]通过扩展Bellman-Ford算法提出了有限粒度启发算法(LGH)和有限通路启发算法(LPH)。前者是文献[13]的推广，后者使用了TAMCRA算法中的非受控路由和在每个节点中维护K条路由的概念，与TAMCRA算法不同的是LPH只是记录前K条路，而不必在乎这K条路是不是最短路由。LPH在中间节点并不检查子路由是否满足约束，只是在宿节点处检查路由是否满足约束条件。由于每个节点不能记录所有的最优服务质量路由，因此只能尽量逼近最优解。如果网络中存在可行路由，则LPH找到该路由概率很高。当约束数目大于3时，LPH算法优于LGH算法。

　　文献[15]使用后向-前向技术，提出了随机化算法：首先计算各个节点到宿节点的针对各个参数的最优路由，删掉所有不能存在于可行路由上的链路，接着基于跳数，利用随机广度优先搜索去选择可行通路。该算法不能保证找到所有可行路由，但是只要找到一条路由，则该路由必定能满足所有约束条件。

　　针对通常服务质量选路算法在高负载时往往表现出比最小跳数路由算法性能更差的情况，文献[16]引入了算法弹性能力的概念，提出了压缩网络图(NGR)算法。该算法在计算路由之前，删掉网络中过分拥挤的链路，由于修改的图可能变成非连通图，因此最小跳数路由始终作为一种可能的解决方案而存在。NGR算法的思想可以应用于现有的服务质量选路算法之中去，能很好地适用于各种负载情况的选路计算。

　　文献[17]提出了基于探测(Probing)的分布式选路算法，其基本思想是沿多条路径为业务发送选路探测包，算法中每个节点仅需要保留部分网络信息。选择性探测算法是将探测包向满足服务质量和优化要求的路径上发送，减小了通信开销。基于Ticket的探测算法是为了进一步提高选择性探测算法的性能而采用，并根据网络资源的竞争等级确定Ticket的数量。蚂蚁路由算法[18]也是一种探测选路算法。基于探测包的分布式路由的主要开销是探测包开销，探测包越多，开销越大，但所选路由的可靠性就越高，也越接近最优路由。

　　文献[19]提出最小干扰选路算法。该算法的核心思想是考虑到不同源宿节点对之间业务的不均衡，当为某个业务选路时，应尽量使该业务对网络关键链路的影响降低到最小程度，使之对后来的业务选路干扰最小，从而使网络资源得到充分利用。

　　可以看到不同的选路算法具有不同的准确性和复杂度，通常使用以下几种技术：

　　(1)预处理技术

　　预处理技术利用凹性约束以及链路可用资源信息等在进行选路计算之前对拓扑图进行裁减。

　　(2)链路权值构造技术

　　链路权值构造技术将链路的各度量参数进行线性或者非线性组合，根据新的链路权值计算路由。

　　(3)反向-正向计算技术

　　反向-正向计算技术首先针对各度量参数计算各节点到宿节点的最优路，接着利用前面计算的信息，从源节点开始进行计算。

　　(4)主参数技术

　　主参数技术将一个参数作为主要优化目标进行选路，要么在找到路由后判断其他约束是否满足，要么将其他参数根据约束进行整数有界化。

　　(5)非受控路由技术

　　非受控路由技术在选路计算过程中对中间节点只维护从源到当前节点的非受控路由。

　　(6)K路由技术

　　K路由技术在中间节点维护K条从源到当前节点的路由，可以是K条非受控路由，或K条最短路，或K条满足约束的路由。

　　(7)探测技术

　　探测技术在分布式选路中向多条路径发送选路探测包。

　　(8)最小干扰技术

　　最小干扰技术尽量避免使用关键资源。

　　3 服务质量选路今后的研究方向

　　对于服务质量选路，由于还有很多问题需要研究，本文认为可以从以下几个方面予以讨论。

　　(1)服务质量选路的可扩展性研究

　　网络的规模在不断扩大，因此要求服务质量选路具有很强的扩展性，而层次式选路和分布式选路能很好地适应网络扩展性要求。实际使用中可以单独考虑这两类选路，也可以考虑将两者结合起来。

　　(2)多播网络中的服务质量选路

　　在多播网络环境中，需要寻找满足服务质量要求的多播树，这较单播服务质量选路复杂。多播网络中同时存在单播业务，如何公平地为这两类业务服务，值得研究。

　　(3)波分复用光网络中的服务质量选路

　　波分复用(WDM)光纤传输能提供大容量的通信，在WDM层直接提供满足各种服务质量要求的路由成为光网络研究的一个方向。同时由于IP是行之有效的、支持分组化业务的网络协议，因此，在WDM网络上直接运行IP，或者IP over WDM，成为业界关注和研究的热点。将服务质量选路直接引入这种模型[20]，能够更有效地提供各种服务质量要求的业务。

　　(4)无线自组织网络的研究

　　由于一方面无线网络信道资源匮乏且具有较高的信道误码率，另一方面网络拓扑结构动态变化，因此使得自组织(Ad Hoc)网络中的服务质量选路研究极具挑战性。综上所述，层次式服务质量选路、分布式服务质量选路以及在不同网络中的服务质量选路值得进一步研究。

　　参考文献：

　　[1] Xiao X, Ni L M. Internet QoS: A Big Picture [J]. IEEE Network, 1999,13(2):8-18.
　　[2] Chen S, Nahrstedt K. An Overview of Quality of Service Routing for Next-Generation High-Speed Networks: Problems and Solutions [J]. IEEE Network Magazine, 1998,12(6):64-79.
　　[3] Kuipers F, Korkmaz T, Krunz M. An Overview of Constraint-Based Path Selection Algorithms for QoS Routing [J]. IEEE Communications Magazine, 2002,40(12):50-55.
　　[4] Wang Z, Crowcroft J. Quality of Service Routing for Supporting Multimedia Applications [J]. IEEE Journal on Selected Areas in Communications, 1996,14(7):1228-1234.
　　[5] Oida K, Sekido M. An Agent-Based Routing System for QoS Guarantees [C]. IEEE SMC ´99 Conference Proceedings. 1999,3:833-838.
　　[6] Apostolopoulos G, Guérin R, Kamat S. Quality of Service Based Routing: a Performance Perspective [J]. ACM SIGCOMM Computer Communication Review. 1998,28(4):17-28.
　　[7] Izmailov R, Lee D S, Sengupta B.ATM Routing Algorithms with Multiple QoS Requirements for Multimedia Internetworking [J]. IEICE Trans. on Communications, 1996,E79-B(8): 999--1006.
　　[8] Jaffe J M. Algorithms for Finding Paths with Multiple Constraints [J]. IEEE Networks, 1984,14: 95-116.
　　[9] Jingchao Chen. Efficient Heuristic Algorithms for Finding Multi-Constrained Paths [C]. ICC 2002, IEEE International Conference on Communications, 2002,2:1074-1079.
　　[10] Korkmaz T, Krunz M. Multi-Constrained Optimal Path Selection [C]. Proceedings of the IEEE INFOCOM 2001 Conference, Anchorage, Alaska, April 2001,2:834-843.
　　[11] Neve H D, Mieghem P V. TAMCRA: A Tunable Accuracy Multiple Constraints Routing Algorithm [J]. Computer Networks, 2000,23: 667-679.
　　[12] Mieghem P V, Kuipers F A. On the Complexity of QoS Routing [J]. Computer Communications, 2003,36(4):376-387.
　　[13] Chen S, Nahrstedt K. On Finding Multi-Constrained Paths [C]. Proc ICC´98, 1998,2:874-879.
　　[14] Yuan X. Heuristic Algorithms for Multiconstrained Quality-of-Service Routing [J]. IEEE/ACM Transactions on Networking, 2002,10(2):244-256.
　　[15] Korkmaz T, Krunz M. A Randomized Algorithm for Finding a Path Subject to Multiple QoS Constraints [J]. Computer Networks, 2001,36(2/3):251-268.
　　[16] Casetti C, Cigno R L, Mellia M. A New Class of QoS Routing Strategies Based on Network Graph Reduction [J]. Computer Networks, 2003,41(4):475-487.
　　[17] Shigang C, Klara Nahrstedt. An Overview of Quality-of-Service Routing for the Next Generation High-Speed Networks: Problems and Solutions [J]. IEEE Network, 1998,(11/12):64-79.
　　[18] Schoonderwoerd R, Holland O,Bruten J. Ant-Based Load Balancing in Telecommunications Networks [J]. Adaptive Behavior, 1997,5(2):169-207.
　　[19] Kar K, Kodialam M, Lakshman T V. Minimum Interference Routing of Bandwidth Guaranteed Tunnels with MPLS Traffic Engineering Applications [J]. IEEE Journal on Selected Areas in Communications, 2000,18(12):2566-2579.
　　[20] 何荣希,李乐民,徐世中. 多光纤WDM网络中的QoS路由算法[J]. 电子与信息学报, 2002,24(11):1589-1596.

[摘要] 文章围绕网络状态信息管理和服务质量选路算法两个方面对服务质量选路技术的研究进行了综述，对服务质量选路方面需要进一步研究的问题进行了讨论。

[关键词] 服务质量选路；多约束选路问题；非多项式完全问题；启发式算法

[Abstract] From respects of management of network state information and routing algorithm, the paper focuses on the study on QoS routing technologies, and discusses problems in QoS routing that deserve further study.

[Keywords] QoS routing; Multi-constrained routing problem; NP-complete problem; Heuristic algorithm