摘要：随着互联网技术的迅猛发展，网络信息量及信息类型越来越多，传统网络Best Effort服务机制受到了互联网日益增加的信息类型及信息量的冲击越来越大，QoS算法已经成为人们研究的重点与热点。介绍了路由算法，对QoS及QoS路由进行了阐述，重点对计算机网络基于QoS路由算法进行了探讨，并对计算机网络QoS路由算法的发展进行了展望。
关键词：网络；QoS；路由算法
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）10-2202-02
随着互联网技术的迅猛发展，网络信息量及信息类型越来越多。尤其是到了二十世纪的九十年代，传统网络Best Effort服务机制受到了互联网日益增加的信息类型及信息量的冲击越来越大，因此，不同的实时多媒体应用程序使得传统的协议模式对于网络用户的需求不能满足。在此背景下，网络服务质量算法，即Quality of Service，简称QoS算法已经成为人们研究的重点与热点。
1 路由算法概述
路由指的是将信息自源通过网络向目的地进行传送。路由技术包括了最优路径的确定以及信息单元即数据包的传送两项基本活动。相对而言，进行数据包的传输与交换较为直接和简单，但是确定路由较为复杂。因此，确定路由算法必须充分考虑以下因素：①确定路由算法需要考虑最优化。路由算法的确定应该选择最佳路径能力；②确定路由算法需要考虑简洁性。路由算法的确定需要简洁，也就是通过尽可能少的开销及软件，实现最大的功能；③确定路由算法需要考虑坚固性。当路由算法处在不可预料的环境或者是非正常的环境时，包括出于负载较高的环境，操作失误，硬件出现故障等情况时，要求算法能够正常的工作。因此在网络的连接点上分布路由器，因此，当路由器发生故障时期后果非常的严重，所以，路由算法必须可以经受时间的考验，能够在不同网络环境中可靠稳定工作；④确定路由算法需要考虑快速收敛。对于最佳路径的判断全部的路由器都可以达到一致这就是收敛。如果因为网络事件造成了路由不可用或者可用，那么路由器就会进行信息的更新。因为进行路由信息更新时，涉及到整个的网络，所以必须对最佳路径进行重新的计算，直至出现全部路由器一致的最佳路径。当收敛速度慢时，就会出现网络中断甚至造成路径循环；⑤确定路由算法需要考虑灵活性。利用算法应该准确快速的满足不同的网络环境。比如，当某网段出现故障，那么路由算法应该及时发现算法，同时能够提供给使用该网段的全部路由最佳的另外的路径。
2 QoS及QoS路由概述
2.1 QoS概述
随着互联网技术的迅猛发展，交互式电视会议，远程教育，协同文档编辑等已经广泛的出现在人们的生活中。这些应用具有实时性，无一不涉及到网络服务质量QoS问题。QoS可以实现对数据包的科学合理的排队，优化含有内容标识的数据表，同时对于特定数据表进行更高优先级的赋值，使得优先级高的数据包首先进行传输，提高了数据表传输的速度。QoS是IP数据流基于网络性能，具有包括延迟，业务可用性，丢包率，可变延迟以及吞吐量等度量指标。对于不同的应用要求，QoS也不同，比如有些应用要求传输速率，有些应用要求吞吐量等。
当前Internet越来越普及，已经渗入到人们生活的各个方面，人们对网络性能，服务以及安全性等各方面的期望也越来越高。然而当前互联网中的Best Effort服务仍然是一种主要的服务类别，在网络中全部分组都被同等的对待，而任意一个拥塞的链路都会造成分组传输时间的增加，从而使得性能下降，数据出现抖动，甚至是出现数据包的丢失，因此服务质量得不到保障。基于此，随着QoS技术的不断发展，高效的QoS的重要性日益凸显，被越来越多的应用到计算机网络路由算法中。
2.2 QoS路由概述
2.2.1 QoS路由网络模型
对QoS网络的拓扑结构以及资源的容量进行抽象，得到加权图N（V，E），V表示了节点集，也就是网络内的交换的设备；E是双向链路集，也就是传输的路线。对于任何一个网络节点（u，v），当存在从u→v的链路，那么必定会存在从v→u的链路，基于链路的对称性可以得到，网络被分成了对称网络以及非对称网络。基于以上的描述，事实上网络包括了两种要素，即节点与链路。
2.2.2 QoS路由的度量
QoS路由算法的可实现性是由算法的复杂程度决定的。而QoS度量参数的选择对算法的复杂程度有着直接的影响，同时，路由选择算法的性能是由网络支持的度量参数体现的。支持度量参数越多，表明越能够有效的接入业务服务质量。然而同时增加了路由选择算法，降低了业务接入率。QoS应用业务对于网络服务提出包括带宽，丢包率，延时，延时抖动等可度量的参数。在计算机网络上进行数据业务的传输时，需要满足度量的要求。QoS能够利用约束集对度量进行描述。
3 计算机网络基于QoS路由算法的分析
3.1 不同路由策略特征
基于网络状态信息的维护形式以及路径搜索的形式进行分类，路由策略被分成了源路由，层次路由以及分布式路由。源路由内的任何一个节点都对全局信息的完整起到维护作用，维护网络拓扑结构以及任何一个链路状态信息，根据全局的信息在源节点进行最优路径的计算；对于层次路由而言，其解决的主要问题是可扩展性问题，将网络内的一部分节点进行聚合构成逻辑节点，之后，将这些逻辑节点进行聚合成上一层次的逻辑节点，进而能够获得树结构，从最上层逻辑节点开始进行路由计算；对于分布式路由机制来说，任何一个节点都不需要对全局的信息进行维护，通常只是清楚相邻节点信息，利用各个节点间的分布式的计算获得路径，在节点间实现信息控制，通过对每一个节点的保存在状态信息的综合使用对路径进行搜索，大多是分布式路由算法都要求链路状态协议或者是距离矢量协议，在任何一个节点通过距离矢量的形式对路由的相关信息进行维护与计算，基于上述距离矢量，路由过程进行一跳一跳的实现。
3.2 源路由
因为进行源路由的计算能够在同一个节点实现，因此，对于分布式计算中存在的死锁检测，分布计算终止检测等问题得到了有效的避免，同时确保了计算的路径不会出现回环。源路由存在以下不足：①会聚的信息量比较大。因为对于任何一个节点来说，都要对整个网络的状态信息起到维护的作用，因此，网络会聚信息量比价大，使得网络的整体的效率变低；②网络状态的准确性不高。因为网络的大量的状态信息都会向每一个节点会聚，而进行信息的会聚无疑需要时间，从而使得网络的实时情况不能得到很好的体现；③源点计算量过大。当节点在接收到会聚的网络的信息以后，对最短路径算法进行启动，基于整体网络拓扑信息对本节点到网络的全部的节点的最短的路径进行计算，进而生成路由表。对于任何一个节点来说，都需要进行计算，因此，计算量过大；④可扩展性存在问题。因为对于任何一个路由器来说，其存储量是有限的，基于此，随着网络规模的增加，支持源路由路由器网络信息维护量源路由大，就大规模的网络而言，路由器的存储空间不能满足源路由策略需要。
3.3 分层路由
分层路由通常被进行大规模网络路由计算中存在的可扩展性问题的解决。分层路由计算一般需要源路由策略与分布式路由策略相结合，这是由于任何一个节点仅维护聚合以后的部分网络的状态的信息。通常而言，对于同一层内能够将已有的源路由策略进行利用，分布于不同的逻辑层的计算结果进行结合从而获取最优路径。因此，实际上分成路由具有源路由以及分布式路由的优势。不过两种策略相结合的机制也存在一定的不足。①增强了状态信息的不精确性。将一部分的节点的状态进行会聚成为一个节点，通过一条逻辑链路信息对多条路径或者链路的综合信息进行表示，这样无疑使得网络节点中状态信息维护的不准确性增加；②对于多个的QoS参数节点不容易聚合成一个节点。就QoS路由来说，不同QoS参数需要不同的链路或者节点的聚合的形式，然而这些形式有时候会出现相互蓦地，基于此，要进行多个节点聚合为一个逻辑节点，而同时又要求聚合多个QoS参数，这是不容易实现的。介绍一个典型的层次路由算法。B Awerbuch等人对ATM网络内不同层次算法进行了对比，通过模拟实验发现层次算法性能优于非层次算法性能，就同一网络结构不同层次算法的性能表现及原因进行了分析，同时提出了改进的算法。
3.4分布式路由
对于分布式路由，进行路径的计算是分布于路径的节点间，因此，对于路径的要求需要满足响应快，计算量小的特点。因为，其节点不需要对全局信息进行保存，所以具有良好的可扩展性。其存在的不足包括：①由于会聚信息的类型比较多，因此管理不易；②对于某些NP路由问题以及NPC问题，特别是对于QoS路由问题不易设计启发式路由算法；③当状态信息不准确时容易发生回环的问题，因为节点维持的信息进行其他路径的选择，因此，回环问题的容易造成路由失败。
4 计算机网络QoS路由算法的展望
传统计算机互联网路由理论将网络的权值看做为不随着时间变化，是静态的，这无疑和实际不相符。事实上，为了对计算机互联网的运行的情况进行准确的描述，需要把链路权值当做是随时间变化的参数。当前，在理论上已经证明，传统最短路径算理论基础，在依赖时间的网络中被证明是不正确的。目前，已经提出了基于时间变化的网络模型，理论基础，并且在混合型时间网络分布式路由协议中得到了应用。
计算机网络不但存在时间的依赖性，同时计算机网络的链路权值，拓扑结构以及用户的产生都具有非常大的随机性，基于此，随机网络模型以及理论能够对计算机网络状态进行更好的描述。对于最短路径算法方面，特别是随机网络的最短路径算法的选择方面，已经有较为深入的研究，与此相关的算法以及计算机网络路由协议的移植的研究也有了非常大的进步。基于随机时间依赖模型以及理论描述对于计算机网络时间的随机性构建路由算法模型，是未来对于计算机网络QoS路由算法的发展趋势。
5 结束语
Internet网络的迅猛发展，其多媒体应用及实时应用业务发展迅猛，这就要求互联网能够满足高效的服务质量支持，然而传统的Best Effort网络机制并不能满足QoS通信的要求，因此，计算机网络中基于服务质量的QoS路由算法已经成为网络研究的重点与热点。对于QoS路由算法的研究对于网络理论及应用发展都具有非常重要的意义。
参考文献：
[1] 朱慧玲，杭大明.QoS路由：问题与解决方法综述[J].电子学报，2008，13（1）：110-116.
[2] 崔勇，吴建平，徐恪.基于模拟退火的服务质量路由算法[J].软件学报，2003，14（5）：877-884.
[3] 何小燕，费翔，罗军舟.Internet中一种基于遗传算法的QoS路由选择策略[J].计算机学报，2010（11）：1171-1178.
[4] 王征应，石冰心.基于启发式遗传算法的QoS组播路由问题求解[J].计算机学报，2001，24（1）：55-61.
[5] B Awerbueh.The Effect of Network Hierarchy Structure on Performance of ATM PNNI Hierarchical Routing[J].Computer Communication，2000，23（10）：980-986.
