论文部分内容阅读
随着Internet的不断普及，一些新型多媒体实时应用不断涌现，如远程教育、视频会议等，所有这些应用都需要服务质量QoS的保证。QoS作为一种网络安全机制，是用来解决网络延迟和阻塞等问题的一项重要技术，本文是在保证网络高效运行的基础上，对基于QoS的路由选择算法的研究。
一、路由选择算法的研究背景
目前，主要通过节点控制或者整网/局部网络控制两个途径来提高QoS。节点控制在单节点或单链路完成，其策略主要包括：管理节点缓冲区策略、业务流整形策略和业务调度策略，主要实现业务对单节点共享资源（包括共享的链路、缓存区、处理器资源等）占用情况的控制。整网/局部网络控制则是通过对信令和路由的控制来达到对业务流的控制的。由于路由能够直接关系到网络的性能，所以在解决QoS问题中，QoS路由技术是一项关键性的技术。
QoS路由技术是在保证网络资源的有效利用的条件下，为接入的业务选择满足其服务质量所要求的相应传输路径的技术。一般路由选择过程由寻路过程和节点间路由信息交互过程两部分组成。
二、 QoS实现原理
QoS实现环节如图1所示：
SOAP：简单对象访问协议，是一种轻量的、简单的、基于 XML 的协议，它被设计成在 WEB 上交换结构化的和固化的信息。
COPS：公共开放策略服务协议，是一种简单的查询和响应协议，主要用于在策略服务器（策略决策点PDP）与其客户机（策略执行点PEP）之间交换策略信息。
BRAS：宽带远程接入服务器，是面向宽带网络应用的新型接入网关，它位于骨干网的边缘层，可以完成用户带宽的IP/ATM网的数据接入。
DSLAM：指的是数字用户线路接入复用器。DSLAM是各种DSL系统的局端设备，属于最后一公里接入设备（the last mile），其功能是接纳所有的DSL线路，汇聚流量，相当于一个二层交换机。QoS实现原理如图2所示：
三、 基于QoS的路由选择机制
将网络抽象成由节点（路由器）和边（通信链路）组成的一张无向连通图。图上的每个节点都配备有限数量的CPU和缓冲区资源。当有一条媒体流（以下简称流）通过一个节点时，该流将占用该节点一定数量的CPU和缓冲区资源，同时通过一节点的不同流占用的资源量累加；当一节点的可用资源（CPU或缓冲区）量不足以满足新流的资源需求时，将拒绝新流通过。图上的每条边都配备有限数量的带宽资源。当有一条流通过一条边时，该流将占用该边一定数量的带宽资源，同时通过一条边的不同流占用的资源量累加；当一条边的可用带宽资源量不足以满足新流的带宽需求量时，将拒绝新流通过。流通过一节点时有排队延迟、发送延迟、出错率，通过边时有传播延迟、出错率。对于点对点通信，每条流涉及一个源节点和一个目的节点。基于QoS的路由选择的目的就是要在图上找出既满足流对节点的CPU资源、缓冲区资源、边的带宽资源的需求，又满足流对端到端延迟、端到端出错率要求的费用最低的路由。在进行基于QoS的路由选择时，不仅需要考虑连通性，而且需要同接纳控制、资源预约等机制相互配合。
四、基于QoS的路由选择算法的设计
（一）度量因素
Normal算法考虑到的是带宽、延迟，而QBR算法同时考虑了带宽、延迟和站点计数这三方面的因素。从资源的利用率和数据精确度来看，路由经过的站点越少，涉及到的节点和链路也就越少，占用的网络资源就越少，数据的出错率相应的也越少。
（二）问题描述
使用基于QoS的QBR算法，是为了能够从初选出的若干符合用户要求的初始路由中选出能够提供的QoS保证的最好的路由。
1.同时满足以下三个条件的路由才能够被初选出来 ：
（1）所选出的路由延迟带宽B大于等于由用户提出的带宽B0。
（2）路由时延D小于等于用户提出的时延要求D0。
（3）站点数H尽量小。
这一问题可用数学模型描述如下：
（1）max B。
（2）min D。
（3）min H。
（4）B≥B0。
（5）D≤D0。
可以看出，从初选出的路由中选择需要提供QoS保证，同时符合用户要求的最好路由的问题，演化成了一个多目标规划问题。
（二）算法设计
解决符合QoS要求的路由选择问题，就是解决多目标规划类的问题，在解决这类问题时，评价函数方法是常用的一类方法。评价函数方法的基本思想是：针对所需要解决的多目标规划问题，构造一个评价函数，然后解决问题。算法的设计分析如下：假设用可信度C（Credit）表示度量QoS的保证率，并将其都设定在0～1之间，在OSPF多区域网络中，每个非主干区域都与主干区域有连接时直接交换区域的路由信息，也就是说主干区域必须保持处于在全连通的状态下。
在数据传输过程中，足够的带宽是保证路径安全的必要条件之一，带宽越大，传输越安全。当路由带宽B刚刚满足用户提出的带宽要求B0 时，难以提供好的QoS保证，路由带宽B越大，越能提供好的QoS保证，但两者之间并不是绝对的成正比关系，当路由带宽B比用户提出的带宽要求B0 大出不是很多的时候，路由带宽B的变化对所提供QoS保证的影响较大；反之，路由带宽B的变化对所提供QoS保证的影响较小。
在数据传输过程中，足够小的延迟也是保证路径安全的必要条件之一。当路由延迟D刚刚等于用户提出的延迟要求D0时，难以提供好的QoS保证，路由时延D越小，越能提供好的QoS保证。当路由时延D接近用户提出的时延D0的时候，路由时延D的变化对所提供QoS保证的影响较大；反之，路由带宽B的变化对所提供QoS保证的影响较小。
在数据传输过程中，站点计数H越小，越能提供好的QoS保证。仅仅从站点技术来说，在所有初选出的路由中，提供QoS保证最好的一定是由站点计数H最小的路由提供的。要想得到提供的QoS保证的变化率越大，需要站点计数越接近最小站点计数；要想得到提供的QoS保证的变化率越小，需要站点计数越远离最小站点计数。
在实际应用过程中，就是先根据初选原则选出满足用户要求的所有路由，然后通过计算的方法，对比选出信用度最高的路由来作为最后选定路径的。
基于上一章所分析的Dijkstra算法和改进的Dijkstra算法存在不能保证QoS的局限性，研究了两种基于QoS的路由选择算法：Normal算法和QBR算法。通过理论上算法的分析对两种算法的优缺点的加以阐述，得到了基于QoS的QBR算法选出的路径更能合理利用网络资源。最后将符合QoS要求的路由选择算法演化成多目标规划类的问题，并实现了对这类问题的算法设计。
参考文献：
[1] 乔，郭晓雷. 高速网络中的QoS控制[M]. 北京：清华大学出版社，2004.
[2] 王兴伟，张应辉，刘积仁. 一种基于服务质量的点对点多媒体通信路由选择算法[J]. 计算机科学2000， 27： 87-89.
[3] McDysan D. IP与ATM网络中的QoS和业务量管理[M]. 北京：清华大学出版社， 2000.
一、路由选择算法的研究背景
目前，主要通过节点控制或者整网/局部网络控制两个途径来提高QoS。节点控制在单节点或单链路完成，其策略主要包括：管理节点缓冲区策略、业务流整形策略和业务调度策略，主要实现业务对单节点共享资源（包括共享的链路、缓存区、处理器资源等）占用情况的控制。整网/局部网络控制则是通过对信令和路由的控制来达到对业务流的控制的。由于路由能够直接关系到网络的性能，所以在解决QoS问题中，QoS路由技术是一项关键性的技术。
QoS路由技术是在保证网络资源的有效利用的条件下，为接入的业务选择满足其服务质量所要求的相应传输路径的技术。一般路由选择过程由寻路过程和节点间路由信息交互过程两部分组成。
二、 QoS实现原理
QoS实现环节如图1所示：
SOAP：简单对象访问协议，是一种轻量的、简单的、基于 XML 的协议，它被设计成在 WEB 上交换结构化的和固化的信息。
COPS：公共开放策略服务协议，是一种简单的查询和响应协议，主要用于在策略服务器（策略决策点PDP）与其客户机（策略执行点PEP）之间交换策略信息。
BRAS：宽带远程接入服务器，是面向宽带网络应用的新型接入网关，它位于骨干网的边缘层，可以完成用户带宽的IP/ATM网的数据接入。
DSLAM：指的是数字用户线路接入复用器。DSLAM是各种DSL系统的局端设备，属于最后一公里接入设备（the last mile），其功能是接纳所有的DSL线路，汇聚流量，相当于一个二层交换机。QoS实现原理如图2所示：
三、 基于QoS的路由选择机制
将网络抽象成由节点（路由器）和边（通信链路）组成的一张无向连通图。图上的每个节点都配备有限数量的CPU和缓冲区资源。当有一条媒体流（以下简称流）通过一个节点时，该流将占用该节点一定数量的CPU和缓冲区资源，同时通过一节点的不同流占用的资源量累加；当一节点的可用资源（CPU或缓冲区）量不足以满足新流的资源需求时，将拒绝新流通过。图上的每条边都配备有限数量的带宽资源。当有一条流通过一条边时，该流将占用该边一定数量的带宽资源，同时通过一条边的不同流占用的资源量累加；当一条边的可用带宽资源量不足以满足新流的带宽需求量时，将拒绝新流通过。流通过一节点时有排队延迟、发送延迟、出错率，通过边时有传播延迟、出错率。对于点对点通信，每条流涉及一个源节点和一个目的节点。基于QoS的路由选择的目的就是要在图上找出既满足流对节点的CPU资源、缓冲区资源、边的带宽资源的需求，又满足流对端到端延迟、端到端出错率要求的费用最低的路由。在进行基于QoS的路由选择时，不仅需要考虑连通性，而且需要同接纳控制、资源预约等机制相互配合。
四、基于QoS的路由选择算法的设计
（一）度量因素
Normal算法考虑到的是带宽、延迟，而QBR算法同时考虑了带宽、延迟和站点计数这三方面的因素。从资源的利用率和数据精确度来看，路由经过的站点越少，涉及到的节点和链路也就越少，占用的网络资源就越少，数据的出错率相应的也越少。
（二）问题描述
使用基于QoS的QBR算法，是为了能够从初选出的若干符合用户要求的初始路由中选出能够提供的QoS保证的最好的路由。
1.同时满足以下三个条件的路由才能够被初选出来 ：
（1）所选出的路由延迟带宽B大于等于由用户提出的带宽B0。
（2）路由时延D小于等于用户提出的时延要求D0。
（3）站点数H尽量小。
这一问题可用数学模型描述如下：
（1）max B。
（2）min D。
（3）min H。
（4）B≥B0。
（5）D≤D0。
可以看出，从初选出的路由中选择需要提供QoS保证，同时符合用户要求的最好路由的问题，演化成了一个多目标规划问题。
（二）算法设计
解决符合QoS要求的路由选择问题，就是解决多目标规划类的问题，在解决这类问题时，评价函数方法是常用的一类方法。评价函数方法的基本思想是：针对所需要解决的多目标规划问题，构造一个评价函数，然后解决问题。算法的设计分析如下：假设用可信度C（Credit）表示度量QoS的保证率，并将其都设定在0～1之间，在OSPF多区域网络中，每个非主干区域都与主干区域有连接时直接交换区域的路由信息，也就是说主干区域必须保持处于在全连通的状态下。
在数据传输过程中，足够的带宽是保证路径安全的必要条件之一，带宽越大，传输越安全。当路由带宽B刚刚满足用户提出的带宽要求B0 时，难以提供好的QoS保证，路由带宽B越大，越能提供好的QoS保证，但两者之间并不是绝对的成正比关系，当路由带宽B比用户提出的带宽要求B0 大出不是很多的时候，路由带宽B的变化对所提供QoS保证的影响较大；反之，路由带宽B的变化对所提供QoS保证的影响较小。
在数据传输过程中，足够小的延迟也是保证路径安全的必要条件之一。当路由延迟D刚刚等于用户提出的延迟要求D0时，难以提供好的QoS保证，路由时延D越小，越能提供好的QoS保证。当路由时延D接近用户提出的时延D0的时候，路由时延D的变化对所提供QoS保证的影响较大；反之，路由带宽B的变化对所提供QoS保证的影响较小。
在数据传输过程中，站点计数H越小，越能提供好的QoS保证。仅仅从站点技术来说，在所有初选出的路由中，提供QoS保证最好的一定是由站点计数H最小的路由提供的。要想得到提供的QoS保证的变化率越大，需要站点计数越接近最小站点计数；要想得到提供的QoS保证的变化率越小，需要站点计数越远离最小站点计数。
在实际应用过程中，就是先根据初选原则选出满足用户要求的所有路由，然后通过计算的方法，对比选出信用度最高的路由来作为最后选定路径的。
基于上一章所分析的Dijkstra算法和改进的Dijkstra算法存在不能保证QoS的局限性，研究了两种基于QoS的路由选择算法：Normal算法和QBR算法。通过理论上算法的分析对两种算法的优缺点的加以阐述，得到了基于QoS的QBR算法选出的路径更能合理利用网络资源。最后将符合QoS要求的路由选择算法演化成多目标规划类的问题，并实现了对这类问题的算法设计。
参考文献：
[1] 乔，郭晓雷. 高速网络中的QoS控制[M]. 北京：清华大学出版社，2004.
[2] 王兴伟，张应辉，刘积仁. 一种基于服务质量的点对点多媒体通信路由选择算法[J]. 计算机科学2000， 27： 87-89.
[3] McDysan D. IP与ATM网络中的QoS和业务量管理[M]. 北京：清华大学出版社， 2000.