（计算机应用技术专业论文）网络应用系统的若干关键技术研究及应用.pdf

网络应用系统的若干关键技术研究及应用 摘要 经过不到十年的推广应用，网络已深入到了社会生活的各个角落，正发挥着 巨大的作用。但是，由于在全球网络中占绝对数量的还是i p 网络，其特点就是竞 争应用网络带宽，网络提供“尽力服务”，这种网络通信机制经常会降低网络的通 信性能，有时甚至导致网络完全陷于瘫痪状态。 为保证i p 网络的正常、可靠的工作，提高网络设备的的工作效率，研究者们 提出了各种i p 网络中的控制算法，并应用于网络设备。这些网络控制算法大致可 分为三大类：网络路由算法、网络拥塞控制算法、网络服务质量( q o s ) 控制算法。 本文在分析比较了一些路由算法及适用的网络环境基础上；给出了一种实际 网络应用过程中获得网络工作状态的方法，并以此作为种网络状态信息获取的 方法，为模拟网络工程师的思维来判定瞬络的路由路径创造了条件；提出了用网 络设备节点c p u 的负载率、c p u 的处理能力、网络链路的相对负载率、网络链路的 带宽四个参数来描述网络链路及网络设备的忙闲程度的向量表示，并用这种方法 实现了模拟网络工程师的思维来判定昭络的路由路径。 另外，对适合一般网络应用环境的基于模糊理论的拥塞控制方法和对传统的 速率相关的网络路由调度方法、基于多目标规划的q o s 路由选择算法的改进，都 取得了较好的应用效果。 这些算法研究，对本人在研究生论文阶段重点研究的多层次职业技术教育应 用系统具有实际的指导意义。第五章介绍了上述多种算法在该系统的某些关键设 备( 如多媒体d v b 信息发布网关、源媒体路由器s m r 、边缘媒体路由器e m r ) 中的 实现方法和相关技术。最后结合作者的研究成果和网络技术的研究现状，提出了 在网络技术研究的方向。 关键词：网络路由，拥塞控制，服务质量 s o m ek e yt e c h n o l o g yr e s e a r c ha n d a p p l i c a t i o ni nn e t w o r ka p p l i c a t i o ns y s t e m s a b s t r a c t n e t w o r ke x t e n d st oe v e r yc o r n e ro fs o c i e t y ，a l t h o u g hi th a so n l yb e e nw i d e l yu s e d f o rl e s st l m al o y e a r t h e s ed a y si pn e t w o r kd o m i n a t e st h em a j o r i t yo ft h eg l o b a l n e t w o r k i t sm a j o rc h a r a c t e ri n c l u d e sc o m p e t e n ta p p l i c a t i o nn e t w o r kb a n d w i d t ha n d p r o v i d i n g b e s t - e f f o r t t h i sk i n do fn e t w o r kc o m m u n i c a t i o nm e c h a n i s ma l w a y s d e c r e a s e st h ec a p a c i t yo fn e t w o r kc o m m u n i c a t i o n ，a n di ts o m e t i m e sr e s u l t si nt h e c r u s ho fn e t w o r k t oe n s u r ei pn e t w o r kt ow o r k e f f e c t i v e l ya n di m p r o v e t h ee f f i c i e n c yo fn e t w o r k e q u i p m e n t s ，r e s e a r c h e r s a d d r e s sv a r i o u sk i n d so fc o n t r o l a l g o r i t h m sa p p l i e d t o n e t w o r ke q u i p m e n t s t h e s ec o n t r o la l g o r i t h m sc a nb ed i v i d e di n t ot h r e ec a t e g o r i e s ： n e t w o r kr o u t i n ga l g o r i t h m ，n e t w o r kc o n g e s t i o nc o n t r o la l g o r i t h ma n dn e t w o r k q o s c o n t r o la l g o r i 曲m b a s e do n a n a l y s e o fs o m e r o u t i n g a l g o r i t b 。m s a n d a p p r o p r i a t e n e t w o r k e n v i r o n m e n t ，t h er e s e a r c hi st op r o p o s eam e t h o do fo b t a i n i n gt h ew o r k l o a df r o mt h e r e a ln e t w o r k a l s o ，u s i n gt h i ss o l u t i o na sam e a n st oo b t a i ni n f o r m a t i o no nn e t w o r k s t a t u sm a k e si t p o s s i b l e t od e t e r m i n et h e r o u t i n g t h a tb a s e do ns i m u l a t i o nt h e t h o u g h t so fn e t w o r ke n g i n e e r s t h i sp a p e ra l s op r e s e n t st h a tu s i n gt h ef o l l o w i n gf o u r p a r a m e t e r s ，e q u i p m e n tp o i n tc p u l o a dr a t e ，c a p a c i t yo fc p u ，r e l e v a n tl o a dr a t ea n d b a n d w i d t ho fn e t w o r kl i n kt oe x p l a i nt h ev e c t o ro fw o r k l o a do fn e h v o r ka n dn e t w o r k e q u i p m e n t s u c hs o l u t i o ns o l v e st h er o u t i n go nb a s i so ft h ei d e ao fs i m u l a t i n gn e t w o r k e n g i n e e r a d d i t i o n a l l y ，t h ep r o p o s e d m e t h o d p r o m p t s t h e b e t t e re f f e c t o nn e t w o r k a p p l i c a t i o ne n v i r o n m e n tt h a tb a s e do nf u z z yt h e o r yr e g a r d i n gc o n g e s t i o nc o n t r o l m e t h o d ，t r a d i t i o n a lv e l o c i t yr e l a t i v er o u t i n gs c h e d u l ea n di m p r o v e m e n to fm u l t i - o b j e c t i v eq o sr o u t i n ga l g o r i t h m s i i t h e p a p e r o nt h e s ea l g o r i t h m sb e n e f i t st h ek e yr e s e a r c ho na p p l i c a t i o n s y s t e mo f m u l t i - p l y v o c a t i o n a lt e c h n o l o g ye d u c a t i o nd u r i n gp o s t g r a d u a t es t u d i e s i nc h a l p t e r5i t i n t r o d u c e ss o m e a p p l i c a t i o na n dr e l e v a n tt e c h n o l o g i e sb yu s i n gt h ea b o v ea l g o r i t h m s i ns o m ek e ye q u i p m e n t so ft h em e c h a n i s m ( s u c ha sg a t eo fm u l t i - m e d i ad v b ，s m r a n d e m r ) t h ep a p e ra l s o a d d r 鹤s e st h ed i r e c t i o no fn e t w o r kr e s e a r c hi n c o m b i n a t i o no ft h ea u t h o r sr e s e a r c ha n dt h ec u r r e n ts i t u a t i o no fn e t w o r k t e c h n o l o g y k e y w o r d s ：n e t w o r k r o u t i n g ，c o n g e s t i o nc o n t r o l ，q u a l i t yo f s e r v i c e h i 7 7 4 9 b s g 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果，除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙 江工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明 的法律责任。 作者签名： 不丰弓 日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名：算彳汤 日期：年月日 导师签名：曼夕孑扣 日期：年月日 榔 浙江工业大学硬士论文网络应用系统的若干关键技术研究及应用 第一章概述 1 1 网络通信的产生和发展 当今社会中，信息技术的应用越来越广泛，而信息技术的关键是信息的获 取、存储、传送、处理及利用技术。随着电话、电视及计算机的有机融合，快速 经济地获取、存储、传送信息成为可能，计算机通信网络成为实现这种可能的一 种有效手段。 在计算机应用初期并没有产生网络通信。从1 9 5 4 年的电传打字机作为最初 的网络雏形开始，逐渐发展成了目前应用广泛的互联网。其过程也是漫长复杂 的，先后经历了三个阶段：1 具有集中器c 和前端网络处理机f n p 的、具有通 信功能的多机系统；2 以通信子网为中心的计算机网络；3 分层的o s i 参考模型 的第三代计算机通信网络。现在i n t e r n e t 己成为世界上最大的国际性计算机互联 网吐 如今，在网上传输的不但是字符、文字，而且包括声音、图像、动画、电视 等各种多媒体信息。随着微电子技术、大规模集成电路技术、光通信技术和计算 机技术不断发展，网络应用正迅速朝着高速化、实时化、智能化、集成化和多媒 体化的方向发展。 所以，网络盼传输速度、服务质量、安全性等问题是现今网络研究的重点。 1 2 网络通信技术的研究内容 1 2 ，1 网络拓扑结构 通信网络按照物理范围来划分，常可分为局域网、城域网和广域网，而两个 或多个网络连接起来就称为互联网。 根据连接分散的数字终端的方式，可将网络的拓扑结构分为以下几种【2 】： 1 星型结构 星型结构是最早出现的一种连接方式。 在多点网络结构中经常采用这种拓扑结构。星型结构有一个中心节点，由它 负责其它节点的中继。网络中的所有信息都经过中心节点，所以它的可靠性决定 了整个网络的可靠性。由一个中心节点来负责其它节点间的连接，往往容易造成 “瓶颈”现象。 目前使用得最广的是以太星型结构。处于中心位置的是集线器。各终端用户 之间的通信都要经过集线器，便于集中控制，易于维护和安全。而且某个终端用 户因为故障而停机也不会影响其它终端用户件的通信。当然，这种结构也有其弱 浙江工业大学硕士论文网络应用系统的若干关键技术研究及应用 点，那就是中心系统必须绝对可靠，否则， 于瘫痪。对此中心系统常采用双机热备份， 2 总线型结构 一旦中心系统出故障，整个网络将趋 以提高系统的可靠性。 总线结构是使用同一媒体或电缆连接所有终端用户的一种方式。 总线型网络结构简单，所有节点都连接在同一根总线上。通常用于广播式通 信。网络中的一个节点发送数据，其它节点均可收到。任何一个时刻，至多只有 一台机器是主机器，且只有它才可以传送数据。其它所有的机器都被禁止发送数 据。要保证端媒体发送数据时不出现冲突：在点到点的链路中，采用简单的机制 就可确保两个端用户轮流工作；在点到多点的结构中，依靠控制端的探询来确定 访问的线路；而在局域网中，则可采用一种在总线共享型网络中使用的媒体访问 方法：带有碰撞检测的载波侦听多路访问( c s m m c d ) 总线型结构具有费用低、数据端用户入网灵活、站点或某个端用户失效不会 影响其它站点或端用户，而且布线简单，扩充容易。尽管有一次只能一个端用户 发送数据，而其它用户必须等待发送、媒体访问机制较复杂的缺点，仍是一种使 用最普遍的局域网技术。 3 环型结构 ：型网络结构将信输媒体从一个端用户到另个端用户逐个连接起来，直到 所有端用户都连成了一个完整的环。 信息流只能是单方向的。每个收到信息包的站都向它的下游站转发该信息 包。、信息包在环网q 旅行一圈，最后由发送站进行回收。当信息包经过目标站 时，目标站根据信息包中的目标地址判断出自己是接收站，并把该信息包拷贝到 自已的接收缓冲区中。为了合理安排调配各站上的发送信息，平时在环上流通着 一个叫做令牌的特殊信息包。只有得到令牌的站可以发送信息。当一个站发送完 信息后就把令牌向下传送，以便下游的站可以得到发送的机会。当没有信息传送 时，环网上只有令牌流通。 这种网络结构消除了端用户通信对中心系统的依赖。但也带来了网上任一节 点或线路发生故障而导致整个网络瘫痪的问题。 4 网型结构 网型结构也称不规则型，其各节点有通信线路连成不规则的形状。连接原则 是根据各节点的地理位置、传输延时和建网费用等因素折衷考虑。网型结构是通 信网中最般的拓扑形式。 5 树型结构 树型结构是种自然分级控制结构。主要有两种形式，种是总线型的集 合，另一种是星型的派生。树型结构扩网容易，组网成本低。但也存在中间任一 节点的故障导致网络局部或全部失效的缺点。 2 浙江工业大学硕士论文网络应用系统的若干关键技术研究及应用 上述为数据通信网的基本结构形式。在实际大型网络中，不同网络部分可以 采用不同的拓扑结构，保证网络的合理性。此外，不同的网络介质在不同的网络 结构中的适应性及性能有所不同。 1 2 2 网络通信模型 网络按通信方式，可以分为单播、广播、组播。 1 单播 指i p 分组从源端传送到目的端一种通信方式。它的特点是源端和目的端之间 有单独的数据信道。当目的端不是很多时，一台主机( 作为源端) 同时拷贝几个 相同的分组给不同的目地端，不会有什么问题。但当有大量的目的端存在，都向 源端要求同一份分组时，源端必须向每个目的端发送它所申请的分组拷贝。一方 面，单播方式避免将数据发送给不需要的用户；另一方面，每一份拷贝都经过网 络传输，占用了很高的带宽和资源，容易造成网络拥塞，信息延迟，从而影响传 送效率和服务质量。常用的改进措施是增加硬件和带宽1 3 l 。 2 广播 指i p 分组由源端向多个目的端传送。简称一对多传送。它向每一个目的节点 传送一个分组的拷贝。传送方式可以是多个单次分组的传送，也可以是由单独的 连接传送分组的拷贝，在广播过程中，用户只能被动地接收数据流，不能控制 流。广播方忒可以将单独的数据流传送到整个网络，一般情况下，用户是通过把 分组分送给二个特殊的地址即广播地址来进行广播投递。这将消耗大量的主机资 源和网络资源；并且只能用于一个子网中，不能传到另一个子网去1 4 1 。同时，由 于其不辨目的地的发送方式很容易引起“广播风暴”，大量无用的广播信息将淹 没网络，消耗网络带宽和资源。通常可以通过设置路由器来阻止广播的传播，将 广播限制在一个物理或逻辑上的网段内。由于路由器将封锁广播通信，广播通信 将会增加非接收者的开销。 3 组播 指i p 分组由源端向目的端集中的每一个节点传送。分组被发送到特定的组播 组，只有属于该组播组的目的端才能接收此数据。该组以外的其它目的地( 客户 端用户) 均接收不到。组的成员是动态的，它可以在任何时候加入或离开一个 组，组的大小和位置没有限制，一个主机可以是多个组的成员。组播吸收了上两 种发送方式的长处，克服了它们的弱点。组播是将数据分组的单独一个拷贝发送 给需要的客户，不会复制数据分组的多个拷贝传输到网络上，造成网络拥堵；不 需要数据的客户也不会意外接收到数据，节省了开支【5 1 。采用组播方式发送数 据，单台服务器能对几十万台客户机同时发送连续数据流而无延时。媒体服务器 浙江工业大学硕士论文网络应用系统的若干关键技术研究及应用 只需要发送一个信息包，而不是多个，所有发出请求的客户端都能共享同一信息 包。信息可以发送到任意地址的客户机，减少了网上传输的信息包的总量，节省 网络带宽，提高传送速率，减少主干网出现拥塞的可能。组播组中的主机不同于 广播方式中的主机，它可以属于同一个子网，也可以分属于不同的物理网络。 广播和组播对于流媒体传输具有重要意义。因为流媒体的数据量往往很大， 需占用很大的网络带宽。若采用单播方式。那么多少个目的地就得传输多少份流 媒体，网络带宽就要成倍增加；而采用广播或组播方式，流媒体在源端只需传送 一份，组内或同一网段上的所有客户端均可接收到。大大降低了网络带宽的占 用。 1 2 3 网络路由技术 现在的网络规模庞大、结构复杂、流量又在不断变化，所面临的路由问题既 要满足用户不同应用的需求，又要能提高网络资源的利用率，因此寻求最佳路由 将是极其困难的。通过研究，可以将这类问题归结为一个多约束条件的复杂非线 性规划问题。解决这一问题的基本算法是d i j k s t r a 算法和b e l l m a n f o r d 算法。 d i j k s t r a 算法是图论中寻找最短路径的算法，它要求出从源节点到系统中所有节点 的最短路径，计算量偏大。b e l l m a n - f o r d 算法是寻找最短路径的分布式算法，允 许边的权是负的，但各节点的同步是一个问题，在不同步时可能得不到最优解。 、针对算法的不同，可以分成源路由算法、分布式路由算法和分级路由算法。 源路由算法属于距离矢量算法，它假定每个节点了解整个网络的全局状态，全局 状态可以通过广播获得，也可以通过邻节点周期性交换获得。当要发送信息时， 源节点就决定了整条路径。其缺点是计算量偏大。而分布式算法假定每个节点只 了解相邻节点的情况，即局部状态，只能决定下一跳应向哪里。分级路由算法是 假定网络节点分级，每个节点了懈聚合的全局状态，对上级节点只了解大概情 况。不够精确。 所以路由的关键是找出最优或最满足要求的解，同时又要能有效利用网络资 源，但这两个方面往往是矛盾的，只能有所侧重。 1 2 4 网络通信的拥塞控制 计算机的链路容量、交换节点中的缓冲区和处理机等，都是网络的资源。在 某个时间段内，若由网络承载的流量对网络中某一资源的需求超过了该资源所能 提供的可用资源总量，网络的整体性能就要变坏，这种情况叫做拥塞。显然。这 时流经拥塞点的业务流量的q o s 将无法得到保证。造成网络拥塞的原因有许多， 不单是节点的缓存空间不够、输出链路速率和节点处理机的处理能力不高的问 浙江工业大学硕士论文同络应用系统的若干关键技术研究及应用 题。其根本原因是整个系统中各部分资源能力不匹配，只有所有资源能力平衡 了，问题才会得到解决【6 】。 一般，拥塞控制可以分为开环控制和闭环控制两种。开环控制就是在设计网 络时，先将可能引起拥塞发生的因素尽可能考虑到，力求网络工作时不发生拥 塞。这类系统一旦运作将不能更改。闭环控制是基于反馈环路的概念。先监测网 络系统在何时、何地发生拥塞；再将拥塞信息传递到可采取行动的地方；最后调 整网络系统的运行解决出现的问题。 有效的拥塞控制避免机制能使网络更健壮。但过于频繁地采取行动以缓和网 络的拥塞可能会愤系统产生不稳定的振荡。 1 2 5 网络应用的q o s 控制 服务质量( q u a l i t y o fs e r v i c e ，简称q o s ) 是网络在传输业务流时，业务流对网 络服务的需求集合，其中业务流是指与特定q o s 相关的从源到目的地的分组流。 也就是说，q o s 时应用业务对网络传输服务提出的一组刻度量的要求，主要 包括带宽、端到端延迟、分组丢失率、抖动、花费等。网络在传输响应的数据业 务流时，必须满足这组要求。q o s 需求可以通过一个约束集来描述，包括链路约 束、路径约束和树约束。链路约束定义了从源到目的地的每一条链路的约束；路 径约柬定义了从源到目的地的每一条路径上的端到端q o s 需求；树约束定义了对 组播中整个组播树的约束。 1 、集成服务 、 集成服务模型是提交流量的节点在发送分组之前先向网络提出发送申请。申 请通过信令来完成。应用程序通过信令协议通知网络其所需的q o s 。在收到资源 预留请求后，传送路径上的网络节点实施接纳控制，验证用户的合法性并检查网 络资源的可用性，最终判定是否为应用程序预留资源。 一旦接纳申请并为应用程序分配了资源，则只要应用程序提交的流量在网络 运营者和用户实现约定的流量参数描述的范围内，网络按照承诺的q o s 需求提供 服务。预留路径上的网络节点可通过执行分组的分类、流量管制、低时延的排队 调度等q o s 控制机制，来实现对承载流量的q o s 保证。 当前，采用r s v p 协议的i n t s e r v 模型定义了两种业务：有保证型服务和负载 受控型服务【”。r s v p 是一个网络控制协议，它使来自i n t e r n e t 所承载的各类应用 的数据流获得不同的q o s 。有保证型服务通过提供有保证的带宽和时延限制来满 足应用的q o s 需求：负载受控型服务保证即使在网络过载的情况下，仍能对分组 提供“尽力而为”在未过载时的q o s ，即在网络拥塞时满足某些业务分组的低时 延、低丢包率的要求。 浙江工业大学硕士论文网络应用系统的若干关键技术研究及应用 i n t s e r v 尽管提供q o s 保证，但其扩展性差。因为它的工作方式是基于每个流 的，这就需要保存大量的与分组队列数成正比的状态信息。此外，r s v p 的有效 实施必须依赖予分组所经过路径上的每个路由器。在骨干网上，业务流的数目可 能很大，要求路由器的转发速率很高，这就使i n t s e r v 难以得到实施。 2 、区分服务 为了解决可扩展性网络的q o s ，人们提出了一种叫区分服务的模型，它既能 提供一定的q o s 保证，又保留了“尽力而为”的良好的可扩张性。 区分服务把1 p 网中路由器分成边界路由器和核心路由器两类。让边界路由器 负责按一定q o s 要求，实现分类、标记、整形、调度等复杂的功能，让核心路由 器按简短的标记负责对分组的高速转发。它将不像i n t s e r v 那样以流为基本传送单 位，在一个预留网络资源的通道上传送这个信息流【s 】。在区分服务中，由边界路 由器对各个分组进行分类等一系列处理后，再由多个核心路由器一跳一跳地按标 记转发。这样，当网络规模扩大时，它不需专门为每个业务流分别维护一系列状 态信息，因而降低了节点处理负担，使控制机制具有良好的可扩展性，适用于骨 干网的应用。但它的缺点是不能提供端到端的q o s 保证。 3 、多协议标签交换( m p l s ) i n t e r n e t 的迅速发展和各种多媒体业务的不断出现，使网络节点呈指数上升、 网络流量呈爆炸性增长。节点的延迟和流量控制的失调使i p 主干网难以满足多媒 体业务对网络性能的要求。人们针对i p 的无连接方式( 流控和延迟不易保障) 、 路由寻址的“机械”( 最优路径未必反映网络动矮状况) 、偏重于软件功能( 节 省通信平台费用，牺牲时间开销) 等特点，提出了由硬件实现，并能保证网络传 输速度和质量的多协议标签交换( m p l s ) 。 m p l s 是一种在开放的通信网上利用定长标签引导数据高速、高效传输的网 络新技术，它把数据链路层交换的性能特点与网络层的路由选择功能结合在一 起，使得服务提供商能适应业务量不断增长的状况，并为不同的服务提供有利环 境，而无需改变现有的网络低层结构【9 】。同时，由于它是一种独立于链路层的和 物理层的技术，因此它保证了各种各样网络的互联互通，使得各种不同的网络数 据传输技术在同一个m p l s 平台上统一起来。m p l s 的价值在于能够在一个无连 接的网络中引入连接模式。其优点是减少了网络复杂性，兼容现有各种主流网络 技术，降低网络成本，在提供i p 业务时能确保q o s 和安全性，具有流量工作能 力，又能解决虚拟专用网扩展问题和维护成本问题。 1 3 网络技术的研究现状 6 浙江工业大学硕士论文网络应用系统的若干关键技术研究及应用 1 3 1 网络的路由技术研究 路由技术就是为数据分组从源地址到目的地址选择一条或几条理想的路径。 它是通过路由协议在路由设备上运行来实现的。每个路由器都维护着一张路由 表，存储着网络的转发信息。路由器若要转发数据分组，则要根据数据分组的目 的地址来查找路由表表项，从中选择相应的下一站的地址进行新的转发。典型的 路由按路由选择策略有两种：静态路由和动态路由。 1 静态路由 由系统自己配置和网络管理员手工配置就可实现的路由算法。路由器之间不 交换路由信息。如果是直接相连的路由器则系统自动配置，如果不是直接相连 的，由网络管理员配置。路由器本身就是查询路由表并从相应接口转发分组。这 种路由策略对每个路由器只定义了一个输入或输出路径进行连接，因此具有较强 的安全性【1 0 】；另一方面，它不会占用很多资源，使用带宽较小，路由计算简单， 节省了。时间和内存。缺点是若网络存在问题或由于网络拓扑结构变化时，需网 络管理员手工调整。因为无法主动另觅可行路径，通信将被迫中断。这种路由策 略只适用于到某目标只有单个路径的小网络，或是对安全性能要求较高的网络。 2 动态路由 能根据当前泓量或估计的流量和拓扑结构，自动调整路由策略。一般分为距 离矢量路由策略、链路状态路由策略和分级路由策略。 距离矢量路由策略这种选择算法就是周期地发送路由选择专给真接连接的 路由器，使每个路由器都及时更新自己表中的距离矢量，从而形成新的路由选择 表，并通过直接转发告知与其相邻的路由器。这种逐步处理的方式使每个路由器 都知道了别的路由器的情况，形成了关于网络“距离”的累积透视图】。当然这 种知道网络资源“距离”信息还是比较模糊的，路由器并不了解其它路由器或网 络拓扑的确切信息。这种选择策略存在“坏消息传播得慢”的问题。在汇聚过程 中，网络对不一致的路由选择显得脆弱，可能引起死循环。它的优点是比静态路 由效果好，能动态地测试和纠正网络中的失效，易于配置，维护、使用较简单。 适用于极少冗余路径和对网络性能要求不高的非常小的网络。 支持距离矢量路由策略的协议有r i p 协议、b g p 协议。 r i p 协议是路由协议中使用时间最长、应用最广的内部网关协议。在默认 情况下，r i p 使用一种非常简单的度量制度：距离就是通往目的站点所需经过的 链路数，取值为1 1 5 ，数值1 6 表示无穷大。r i p 进程使用u d p 的5 2 0 端口发送 和接收r i p 分组。r i p 分组每隔3 0 s 以广播的形式发送一次，为防止出现“广播 风暴”，其后续的分组将作随机延时后发送。在r i p 中，如果一个路由在1 8 0 s 内未被刷新，则相应的距离就被设定为无穷大，并从路由表中删除该表项。r i p 7 浙江工业大学硕士论文网络应用系统的若干关键技术研究及应用 分组分为两种：请求分组和相应分组【1 2 1 。r i p 盼优点是，对于小型网络，r i p 所 占带宽小，易于配置、管理和实现。但也存在问题，当多个存在时会出现环路问 题。解决环路问题由两种方法，一种是分割范围法，即路由器部可以通过它的取 得的路由接口去宣告路由，这只能解决两个路由器之间的环路问题，无法防止3 个或更多的路由其形成的环路。另一种是触发更新法，它要求路由器在链路发生 变化时立即传输它的路由表。这将加速网络的聚合，也容易造成“广播风暴”。 总之，解决环路问题都要消耗一定的时间和带宽。并且，其网络内所经过的链路 数不能超过1 5 ，这就不能适用于大型网络。 b g p 协议甩来在a s 之间实现网络可达信息的交换，整个交换过程要求建 立在可靠的传输连接基础上。由于将所有的差错控制功能交给传输协议处理，网 络本身就变得简单了。这个协议的特点是采用路径向量的概念和对c i d r 技术的 支持。路径向量中记录了路由所经路径上所有a s 的列表，这就可有效地检测并 避免复杂拓扑结构可能带来的环路问题：对c i d r 的支持，则减少了路由表项， 加快了选路速度，也减少了路由期间所要交换的路由信息【l 。另外，b g p 一且与 其它b g p 路由器建立对等关系，只是在初始化过程中交换整个路由表，除非当自 身路由表发生变化时，b g p 才会更新报文发送给其它路由器，报文中只包含更改 的路由，这就减少了路由器的计算量，也节省了带宽。b g p 有4 种分组：打，开分 组用来建立连接：更新分组用来报告可达路由和撤销无效路由；周期性地发送存 活分组，以确保连接的有效性；当检测到一个差错时，就发送通告分组。 链路状态策略其原理是：( 1 ) 发现该路由器的邻居，获取它们的网络| 也址， 建立相邻关系，并测量到每个相邻路由器的开销和延迟。( 2 ) 将用于交换的信息收 集起来，构造包含这些信息的链路状态分组。( 3 ) 通过f l o o d ( 扩散) 算法，向所有 的其它路由器发送该分组。f l o o d 算法的好坏决定了链路状态算法的优劣。( 4 ) 根 据收集到的链路状态信息，通过d i j k s t r a 算法，计算本路由器到全网其它路由器 或网络的最短路径。o s p f 协议就属于这种策略。 o s p f 协议每个路由器维护一个相同的链路状态数据库，保存整个a s 的拓 扑结构。一旦每个路由器有了完整的链路状态数据路，该路由器就可自己为根， 构造最短路径树，再根据最短路径构造路由表。o s p f 路由器相互间交换信息， 这种信息不是路由信息，而是链路状态【l4 1 。o s p f 定义了5 中分组：h e l l o 分组用 于建立和维护连接；数据库描述分组初始化路由器的网络拓扑数据库。当发现数 据库中的某些过时信息后，路由器发送链路状态请求分组，向邻站请求更新信 息；链路状态更新分组可使路由器主动扩散自己的链路状态数据库或对链路状态 请求分组进行响应；由于o s p f 直接运行在i p 层，就由链路状态应答分组来对链 路状态更新分组进行确认。o s p f 协议的优点是：支持各种不同鉴别机制，也允 许采用不同的鉴别机制；提供负载均衡功能，若计算到某个目的站的几条路径费 浙江工业大学硕士论文网络应用系统的若干关键技术研究及应用 用相同，o s p f 路由器会把通信流量均匀地分配给这几条路径，由它们发送出 去；在一个自治系统内划分出若干个区域，每个区域可根据自己的拓扑结构计算 最短路径，从而减少了路由器的工作量。o s p f 属于动态的自适应协议，当网络 的拓扑结构发生变化时能迅速做出反应，进行相应调整，使路由表尽快稳定；相 比较其他协议，o p s f 在处理网络拓扑结构变化所需通信流量最少；o s p f 还提供 点到多点接口，支持c i d r 地址。它的缺点是协议本身庞大复杂，实现较困难。 分级路由策略：假定网络节点分级，每个节点了解聚合的全局状态，即自 己所在范围内的情况，而对远处的上级节点只了解大致情况。 1 3 2 路由器的拥塞控制算法 路由器中采用包调度算法和缓存管理技术对拥塞进行控制。采用的拥塞控制 算法主要有以下四种： 随机提前检测算法rr e d ) 该算法通过路由器缓冲区中队列的平均长度来探测拥塞，通过提前丢包，达 到控制拥塞的目的【1 5 】。 队尾丢弃算法( f i f o ) 该算法中路由器各个输出端口只有一个队列，当缓冲区被填满时，新来的分 组就被丢弃。 公平排队算法( f q ) 该算法对数据流进行分隔，使不同的数据流之间不产生影响，为数据流公平 地分配资源。 加权公平排队算法( w f q ) 该算法是对公平排队算法的改进。根据数据流的不同优先级，为每个数据流 分配一个加权值，这个加权值决定了路由器每次发往该队列的比特数。 1 3 3 网络q o s 控制算法的研究 q o s 路由功能负责为业务流量选择能够满足其q o s 需求的一条路径。q o s 路 由不是传统的最短路径，它是一种根据网络上可用的资源和流的q o s 需求决定流 的路由机制。其主要内容有两方面：一是收集网络状态信息并不断更新信息；另 一是根据已有信息来为新的连接请求选择一条合适的路由。所以，q o s r 是一种 动态路由协议。在其路径选择标准里可能包含可用带宽、链路和端到端路径利用 率、资源消费量、延迟、跳数及抖动等q o s 参数【1 6 】。 浙江工业大学颈士论文网络应用系统的若干关键技术研究及应用 一般，为了提供q o s 保证，数据传输通常先需要沿着计算好的路径，从源到 目的地传播一个消恳，用来通知路径上所有节点为这个q o s 业务保留相应的资 源，而后续的数据传输则沿着这条已经预留了资源的路径进行。 在q o s 路由中有两种基本闯题：最优化问题和性能界约束闳题。最优化闻题 是寻找对应q o s 度量的最优路径；而性能界约束问题是寻找大于对应q o s 度量 或小于对英q o s 度量的一条路径，即在满足性能界要求的集合中选择一个解路 由可以分为单播和多播两大类。下面分别讨论。 1 q a s 单播路由算法 最短路径算法 最短路径算法就是使网络中从源节点到接收节点的所选路径的链路权重之和 最小。以d i j k s t r a 算法和b e l l m a n f o r d 算法最为著名。最短路径算法可用来解决 路径约束问题。 启发式路由算法 启发式路由算法用于解决多限制条件下q o s 路由问题。它能降低算法的复杂 度，但不能保证发现一条可行的传输路径。较具代表性的算法如下： 1 c h e n 提出的算法：首先通过产生一个新的加权函数将n p 难得m c p 问题 转化为一个能够在多项式时间内求解的简单问题，然后利用改进的d i j k s t r a 算法 和b d | m a n - f o r d 算法来求解这个简单问题1 1 7 j 。 2 y u a nx i n 提出两种用于解决k ( k 2 ) 个限制条件的启发式q o s 路由算 法：有限路径启发式算法和有限粒度启发式算法【l ”。它们的基本思想是：限制在 每个节点所记录的最优路径数的大小来减少释放操作的时间和空间复杂度。这两 种算法的关键在于如何限制每个节点的路径数，同时又保持求解的效率。 3 k o r k m a z 提出了一个解决多受限路径优化问题的基于随机策略的启发式算 法。算法首先去掉所有不满足条件的链路，然后使用随机搜索的方法寻找一条 可行路径。这种方法类似于宽度优先搜索，但与宽度优先搜索不同的是：随机搜 索方法不是按照宽度优先的顺序选择下一节点，而是在可能满足条件的节点中随 机选择，这种随机选择避免了盲目搜索，提高了算法的性能。 2 基于某种调度策略的路由算法 基于某种调度策略的路由算法是把分组调度算法引入路由算法的度量值计算 中，可使路由计算得到简化，较好地解决多受限q o s 路由问题。有一种基于网络 分组调度机制w f q 的路由算法，该算法将两络底层的分组调度机制引入路由算 法中，有效地使用和平衡网络资源。当然，这种算法也有一定的局限性。 3 q o s 多播路由算法 在单播路由中通过对路径的优化或约束来实现q o s ，多播路由的算法则是通 过对路由树的操作来完成。 1 0 浙江工业大学硕士论文 网络应用系统的若干关键技术研究及应用 最短路径树 最短路径树是使多播树上从源节点到接收节点的每条路径上链路权重之和最 小。如果所有链路的权重都是l ，则为最小跳树。如果权中代表链路延时，则为 最小延迟树。最短路径树算法可用来解决树约束阀尉2 0 】。 最小生成树 最小生成树指覆盖所有组成员并且树权重最小的树。主要算法是p r i m 算法。 p r i m 算法是从任意一个根节点开始构造整棵树，直到其扩展到所有节点。在每一 步中，已连接的选择节点与未选择节点的权重最小的边被加入到树中【2 ”。算法采 用贪心策略，原因是在树的增长过程中，每次选择的边都是使树权重增加最小的 边。最小生成树算法可用来解决树最优化问题。 s t c i n e r 树 基于s t e i n e r 树的问题致力于使多播树的总代价最小。是n p 完全问题。如果 多播树包含了树中所有节点，s t c i n c r 树问题便转化为最小生成树问题。无约束条 件的s t e i n e r 树算法可用来解决树最优化问题，然而它们却无法满足端到端基础上 的约束条件，因此它们不能很好地满足带有此类要求的应用。现介绍几种典型的 算法： 1 启发式k m b k o u 等提出的启发式k m b 算法解决了基于时间约束s t e i n e r 树问题的路由选 择。该算法能够保证在多项式时间内找到合适解。其基本思想是：先求出图g 的 最小生成树t ，然后不停地搜索树口2 1 。若发现t 中的叶子节点不属于m ，则删去 该叶子节点及其相连的边，直到所有叶子节点都属于m 。这种算法只能找到局部 最优解，难以找到全局最优解。 2 c m s t 算法 s h ij i a n 等提出的m c m s t 算法的基本思想是：设由已知源节点可获得整个 网络的拓扑结构。采用d i j k s t r a 第k 条最短算法，可计算出每对节点满足延时约 束的路径集合【2 ”。作为下一步遗传算法的备选路径。m c m s t 算法能求解合适延 时与延时抖动要求的最小多播树并具有搜索速度快，效率高特点。 约束s t e i n e r 树 s t e i n e r 树问题可以扩展为包括其它的链路约束。通常这些问题是n p 完全 的，解决方法也采用启发式算法。 1 s p h 算法 目前求解有度约束的多播路由问题中性能较好的是s p h 算法。其基本思想 是：从只包括源节点的子图开始，寻找与之距离最近且不违反度约束的一个目的 节点，用最短路径将两节点相连，同时将最短路径上的节点加入图中，然后再找 浙江工业大学硕士论文网络应用系统的若干关键技术研究及应用 下一个与子图距离最近的不违反度约束的目的节点，将其加入，直到所有目的节 点全部加入到树中脚】 2 k p p 算法 这种算法的基本思想是：给定源节点s 和多播组m 。k p p 首先得到一个覆盖 s um 的延时约束闭包图g ，然后确定出从节点s 到节点v 的延时最小代价路径 1 2 5 1 。接着髓，p 使用p r i m 算法得到闭包图g 的一个最小生成树。然后从源节点开 始，一次增加一条选定的边，直到整棵树包含所有接收节点。每次选择的边满足 如下条件：连接树节点和非树节点：改变符合延时约束；使选择函数最小。k p p 算法存在时阊复杂度大和准确度低等问题。 3 v m a 算法 g e o r g en r o u s k a s 首次提出了满足端到端延时约束和延时抖动约束的多播路 由算法【2 6 1 。首先用d i j k s t r a 算法求源节点到m 个目的节点各自的最短路径，若满 足两个约束条件则返回。满足延时约束而不满足延时抖动约束则调用d v m a 算 法。d v m a 算法以最短路径有最大时延的目的节点为初始目的节点，采用 d i j k s t r a 第k 条最短路算法求出到它的前k 条最短路径，依次以这k 条最短路径为 扔始树构建路由树，满足两个约束时则返回，否则最后返回有最小延时抖动值的 路由树。每次构建路由树时，对于每次要连接的目的节点，从己成树上的每一个 非目的节点到此目的节点的前k 条最短路径中选取最好的连接路径进行连接。这 个算法的缺点是结构复杂。 最大带宽树 s h a c h a m 提出来最大带宽树算、法【2 “。它使用d i j k s t r a 算法来计算到所有目的 节点的最大单向带宽。算法如下：首先，计算从源节点到所有接收节点的最大可