论文部分内容阅读
摘 要：计算机互联网的发展，使得路由也要与时俱进，本文将讨论分布式路由算法QOS性能研究与仿真。
关键词：分布式路由算法 QOS性能 研究 仿真
随着Internet的快速发展，现在的Internet已由单一的数据传送网，尤其是以指数形式急剧增加，发展成传送数据、语音、视频等多媒体信息的综合业务网。人们对网络的需求由简单的数据传输向综合的多媒体业务发展，如何提高IP网络的服务质量（Quality of Service， QoS），已经成为众多国际组织、网络设备制造商和业务提供者研究和应用开发的焦点问题。而传统的点到点通信方式，一方面浪费大量的网络带宽，另一方面是效率很低，因为IP协议的无连接特性和IP网络松散的控制管理方式，使这项研究面临很大的挑战。那么如何采取一种有效地利用现有带宽的技术就是多播方式。路由选择是IP网络运行的核心问题，合理高效的路由选择方式不仅可以保障全网的正常运行，还能够提高网络的接通率。在高性能路由器中按需保证多种实时业务的服务质量（QoS）是目前网络新技术研究的重点。QOS路由根据多种不同的度量参数（如带宽、成本、每一跳开销、时延、可靠性等）来选择路由。QOS路由包括三个主要功能：链路状态信息发布，路由计算和路由表存储。QOS路由能够满足业务的QOS要求，同时提高网络的资源利用率。
一、动态路由中的分布式路由选择技术
路由器随着互联网的普及越来越重要，从而使得结构复杂、数量较多的主机组成的庞大网络构成一个有序的整体。动态路由中的分布式路由选择分别是距离向量路由选择与链路状态路由选择。现在互联网上大量运行的路由协议RIP（Routing Information Protocol 路由信息协议）、OSPF（Open Shortest Path First 开放式最短路径优先）就是分别基于距离向量路由选择与链路状态路由选择的。路由信息协议是应用较早、使用较普遍的内部网关协议（Interior Gateway Protocol，簡称IGP），适用于小型同类网络，是典型的距离向量协议。路由信息协议通过广播UDP报文来交换路由信息，每30秒发送一次路由信息更新，维护相邻路由器的关系，同时根据收到的路由表计算自己的路由表。RIP提供跳跃计数（hop count）作为尺度来衡量路由距离，跳跃计数是一个包到达目标所必须经过的路由器的数目。如果到相同目标有二个不等速或不同带宽的路由器，但跳跃计数相同，则RIP认为两个路由是等距离的。开放式最短路径优先通过传递链路状态（连接信息）来得到网络信息，维护一张有向网络拓扑图，利用最小生成树算法得到路由表。OSPF是基于链路状态的路由协议，它的优点是支持不同服务类型的不同代价，从而实现不同QOS的路由服务；路由器不再交换路由表，而是同步各路由器对网络状态的认识，即链路状态数据库，然后通过Dijkstra最短路径算法计算出网络中各目的地址的最优路由。不再采用跳数的概念，而是根据接口的吞吐率、拥塞状况、往返时间、可靠性等实际链路的负载能力定出路由的代价，同时选择最短、最优路由并允许保持到达同一目标地址的多条路由，从而平衡网络负荷。
二、分布式路由QOSPF及其仿真
网络应用一般分为非实时数据（或正文）传送、实时图像传送、实时声音传送、视频会议传送四种。在实际的应用中，除了要求找到一条从源到目的最短路径外，更高的要求还在于这条路径是否能满足一个或多个QOS条件。目前所提出的QOS路由协议中，QOSPF（Quality of Service Path First）根据RSVP PATH的Tspec及RSVP node执行Dijstra算法选择路径并缓存在forwarding表中，主要用于单播。
1、QOSPF。开放最短路径优先（OSPF）服务质量（QoS）扩展（QOSPF）算法中预剪枝高延时链路，目前对度量类型的扩展只包括链路可用带宽和链路传播延迟，并且在选择路径时只考虑满足流量的带宽需求，在此前提下尽量使得分配的网络资源最少（即跳数最少）。IETF 工作组提出的支持QOS 路由机制的OSPF 扩展（RFC2676）可以看作是OSPF协议在QOS方面的扩展。主要包括两个方面的优化，首先是链路状态更新方面的QOS扩展，包括QOS参数的蕴涵与表示，以及对QOS支持的表示；其次是对路由计算的QOS扩展，对满足带宽约束的路由算法进行的扩展。QOSPF通过对OSPF 链路状态宣告机制所进行的扩展以通告QOS 度量参数的更新，以及为满足QOS 请求而进行的路径选择算法的修改。
2、QOS算法仿真。QOSPF方法能在满足流量对带宽要求的同时，将流量在整个网络上进行合理分布，避免了所有流量竞争同一最短路径的情况，实现拥塞最小化，从而达到减少丢包率、缩短传输延迟、增大网络吞吐量的目的。为了有效地评价QOSPF协议的性能，我们采用网络仿真软件NS-2（Network Simulator）对QOSPF与传统的OSPF协议进行仿真比较。NS-2可以对网络上的TCP 协议，各种路由协议，多播协议等进行模拟。假设网络模型表示成一个有向图G = （V ，E） ， 其中V 是非空有限集合， 代表节点集合， 元素v∈V 称作图G的一个顶点， E代表连接节点的链路集合，元素eij ∈E ，即e （vi，vj） 为V 中元素的有序对，称为图G的一条从vi 到vj 的边（弧）。|V|，|E|分别表示节点的数量和链路的数量。令元素e ∈E 具有一组有序数列（ w1，w2，…，wk ） ， 作为e的属性， 则称G 为有权图， 其中（ w1，w2，…，wk） 称为弧e 的度量（权值） ，节点集V 可以表示路由器、交换机等网络节点设备，在研究路由问题时， V 中的元素为具有路由能力的交换节点； E 则为连接V 中两个节点的链路及具有的k 个属性（ w1，w2，…，wk） 。为此建立的网络拓扑，并模拟出三条带宽需求分别为1Mbps、500Kbps、300Kbps的路径。
结果， QOSPF中链路状态更新的触发机制主要有周期性的更新或触发式的更新，它对链路状态信息的更新仍然沿用了OSPF的洪泛链路状态更新机制。因而QOSPF仍然存在以下的问题：在大型网络中，大量的洪泛会导致网络负载过重；QOSPF采用的Route Pinning技术使得路由器在路径选择上缺乏扩展性，当链路状态改变，由LSA发现的新的比现存路径更优的路径时，由于路由器采用了Route Pinning技术固定了路由而不能新采用最优的路径；同时，Route Pinning技术对于IP多播也是不支持的 [5]。这些都是目前的QOS路由急需解决的问题。
参考文献
[1] 高晓燕. 基于QoS的P2P服务网络及其关键技术研究[D]. 中国矿业大学（北京） 2010
[2] 冯光升. 面向认知网络的自适应QoS感知与配置方法[D]. 哈尔滨工程大学 2009
关键词：分布式路由算法 QOS性能 研究 仿真
随着Internet的快速发展，现在的Internet已由单一的数据传送网，尤其是以指数形式急剧增加，发展成传送数据、语音、视频等多媒体信息的综合业务网。人们对网络的需求由简单的数据传输向综合的多媒体业务发展，如何提高IP网络的服务质量（Quality of Service， QoS），已经成为众多国际组织、网络设备制造商和业务提供者研究和应用开发的焦点问题。而传统的点到点通信方式，一方面浪费大量的网络带宽，另一方面是效率很低，因为IP协议的无连接特性和IP网络松散的控制管理方式，使这项研究面临很大的挑战。那么如何采取一种有效地利用现有带宽的技术就是多播方式。路由选择是IP网络运行的核心问题，合理高效的路由选择方式不仅可以保障全网的正常运行，还能够提高网络的接通率。在高性能路由器中按需保证多种实时业务的服务质量（QoS）是目前网络新技术研究的重点。QOS路由根据多种不同的度量参数（如带宽、成本、每一跳开销、时延、可靠性等）来选择路由。QOS路由包括三个主要功能：链路状态信息发布，路由计算和路由表存储。QOS路由能够满足业务的QOS要求，同时提高网络的资源利用率。
一、动态路由中的分布式路由选择技术
路由器随着互联网的普及越来越重要，从而使得结构复杂、数量较多的主机组成的庞大网络构成一个有序的整体。动态路由中的分布式路由选择分别是距离向量路由选择与链路状态路由选择。现在互联网上大量运行的路由协议RIP（Routing Information Protocol 路由信息协议）、OSPF（Open Shortest Path First 开放式最短路径优先）就是分别基于距离向量路由选择与链路状态路由选择的。路由信息协议是应用较早、使用较普遍的内部网关协议（Interior Gateway Protocol，簡称IGP），适用于小型同类网络，是典型的距离向量协议。路由信息协议通过广播UDP报文来交换路由信息，每30秒发送一次路由信息更新，维护相邻路由器的关系，同时根据收到的路由表计算自己的路由表。RIP提供跳跃计数（hop count）作为尺度来衡量路由距离，跳跃计数是一个包到达目标所必须经过的路由器的数目。如果到相同目标有二个不等速或不同带宽的路由器，但跳跃计数相同，则RIP认为两个路由是等距离的。开放式最短路径优先通过传递链路状态（连接信息）来得到网络信息，维护一张有向网络拓扑图，利用最小生成树算法得到路由表。OSPF是基于链路状态的路由协议，它的优点是支持不同服务类型的不同代价，从而实现不同QOS的路由服务；路由器不再交换路由表，而是同步各路由器对网络状态的认识，即链路状态数据库，然后通过Dijkstra最短路径算法计算出网络中各目的地址的最优路由。不再采用跳数的概念，而是根据接口的吞吐率、拥塞状况、往返时间、可靠性等实际链路的负载能力定出路由的代价，同时选择最短、最优路由并允许保持到达同一目标地址的多条路由，从而平衡网络负荷。
二、分布式路由QOSPF及其仿真
网络应用一般分为非实时数据（或正文）传送、实时图像传送、实时声音传送、视频会议传送四种。在实际的应用中，除了要求找到一条从源到目的最短路径外，更高的要求还在于这条路径是否能满足一个或多个QOS条件。目前所提出的QOS路由协议中，QOSPF（Quality of Service Path First）根据RSVP PATH的Tspec及RSVP node执行Dijstra算法选择路径并缓存在forwarding表中，主要用于单播。
1、QOSPF。开放最短路径优先（OSPF）服务质量（QoS）扩展（QOSPF）算法中预剪枝高延时链路，目前对度量类型的扩展只包括链路可用带宽和链路传播延迟，并且在选择路径时只考虑满足流量的带宽需求，在此前提下尽量使得分配的网络资源最少（即跳数最少）。IETF 工作组提出的支持QOS 路由机制的OSPF 扩展（RFC2676）可以看作是OSPF协议在QOS方面的扩展。主要包括两个方面的优化，首先是链路状态更新方面的QOS扩展，包括QOS参数的蕴涵与表示，以及对QOS支持的表示；其次是对路由计算的QOS扩展，对满足带宽约束的路由算法进行的扩展。QOSPF通过对OSPF 链路状态宣告机制所进行的扩展以通告QOS 度量参数的更新，以及为满足QOS 请求而进行的路径选择算法的修改。
2、QOS算法仿真。QOSPF方法能在满足流量对带宽要求的同时，将流量在整个网络上进行合理分布，避免了所有流量竞争同一最短路径的情况，实现拥塞最小化，从而达到减少丢包率、缩短传输延迟、增大网络吞吐量的目的。为了有效地评价QOSPF协议的性能，我们采用网络仿真软件NS-2（Network Simulator）对QOSPF与传统的OSPF协议进行仿真比较。NS-2可以对网络上的TCP 协议，各种路由协议，多播协议等进行模拟。假设网络模型表示成一个有向图G = （V ，E） ， 其中V 是非空有限集合， 代表节点集合， 元素v∈V 称作图G的一个顶点， E代表连接节点的链路集合，元素eij ∈E ，即e （vi，vj） 为V 中元素的有序对，称为图G的一条从vi 到vj 的边（弧）。|V|，|E|分别表示节点的数量和链路的数量。令元素e ∈E 具有一组有序数列（ w1，w2，…，wk ） ， 作为e的属性， 则称G 为有权图， 其中（ w1，w2，…，wk） 称为弧e 的度量（权值） ，节点集V 可以表示路由器、交换机等网络节点设备，在研究路由问题时， V 中的元素为具有路由能力的交换节点； E 则为连接V 中两个节点的链路及具有的k 个属性（ w1，w2，…，wk） 。为此建立的网络拓扑，并模拟出三条带宽需求分别为1Mbps、500Kbps、300Kbps的路径。
结果， QOSPF中链路状态更新的触发机制主要有周期性的更新或触发式的更新，它对链路状态信息的更新仍然沿用了OSPF的洪泛链路状态更新机制。因而QOSPF仍然存在以下的问题：在大型网络中，大量的洪泛会导致网络负载过重；QOSPF采用的Route Pinning技术使得路由器在路径选择上缺乏扩展性，当链路状态改变，由LSA发现的新的比现存路径更优的路径时，由于路由器采用了Route Pinning技术固定了路由而不能新采用最优的路径；同时，Route Pinning技术对于IP多播也是不支持的 [5]。这些都是目前的QOS路由急需解决的问题。
参考文献
[1] 高晓燕. 基于QoS的P2P服务网络及其关键技术研究[D]. 中国矿业大学（北京） 2010
[2] 冯光升. 面向认知网络的自适应QoS感知与配置方法[D]. 哈尔滨工程大学 2009