（计算机应用技术专业论文）面向服务质量的路由策略研究.pdf

山东理_ 丈学坝七学位论文 摘要 摘要 随着i n t e r n e t 的飞速发展，网络的应用正从单一的文本传输向多样化的多媒体应 片j 转变，比如p 电话、交互式多方游戏、网上视频播放等，未来还可能出现更多新 的应用。闵此，传统的所采用的“尽力而为”转发机制，已经不能满足用户的要求。 以提高网络资源利用效率、为用户提供高质量服务作为目标的q o s 研究是当前 i n t e r n e t 领域的热点之一。q o s 问题本质上是研究网络资源的管理和控制问题，由于 计算机网络本身存在的缺陷和i n t e r n e t 的复杂性，使得i n t e r n e t 的q o s 研究存在极大 的困难。但q o s 的研究对推动网络应用的发展，提高人们的二作效率，优化i n t e r n e t 的利用具有极其重要的意义。近几年的研究表明网络路由算法对实现网络保证质量的 服务起到了非常关键的作用，同时网络路由算法也是平衡网络负载和充分利用网络资 源的重要保证。 本文首先集中介绍了与本文研究内容有关的基础知识，综述了路由策略的分类方 法、基本的路由实现算法、评价标准以及相关热点问题的研究现状：其次，提出了一 种按需计算路由信息的智能化传播的算法，使用智能a g e n t 技术对路由表进行主动式 不间断检测，由a g e n t 及时读取最新更改的路由信息并交给传播a g e n t 进行传播，从 而避免了频繁传输路由表造成的带宽资源的浪费；最后，利用神经网络算法的快速收 敛性，借鉴人工智能的已肓成果，提出一种满足q o s 的按需计算路由算法，并对算 法的性能进行了理论分析与软件模拟，对实验结果进行了分析；在第五章总结了本文 的研究情况和有待解决的问题。 关键词： 路由，q o s ，智能a g e n t ，神经网络 山东理t 大学硕l 学位论文a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r n e t t h eu t i l i z a t i o no ft h en e t w o r ki s c h a n g i n gf r o ms i n g l et e x tt r a n s m i t t i n gt ov a r i e dm u l t i m e d i au t i l i z a t i o n ，s u c ha s t h ei pt e l e p h o n e ，g a m e sp l a y e db ys e v e r a lp e o p l et o g e t h e r ，a n dt h ev i d e ob r o a d c a s t o ni n t e r n e t t h e r ew i l lb em o r en e wu s a g e si nt h ef u t u r e t h e r e f o r e ，t h et r a d i t i o n a l b e s t e f f o r tm o d e lu s e di nt h ei n t e r u e tc a nn o tm e e tt h en e e do ft h eu s e r sa n yl o n g e r ， i no r d e rt oe n h a n c et h en e t w o r kr e s o u r c eu t i l i z a t i o nr a t i oa n ds a t i s f yt h eh i g h e r q u a l i t yo fs e r v i c eq o s ( q u a l i t yo fs e r v i c e ) r e s e a r c hh a sb e c o m eo n eo ft h eh o t s p o t si nt h ep r e s e n ti n t e r n e tf i e l d q o ss t u d i e st h em a n a g e m e n ta n dc o n t r o lo ft h e n e t w o r kr e s o u r c ee s s e n t i a l l y d u et ot h ec o m p l e x i t yo ft h ei n t e r n e ta n dt h e d i s a d v a n t a g e so ft h en e t w o r ki t s e l f ，t h e r ei sg r e a td i f f i c u l ti nt h eq o sr e s e a r c ho f t h ei n t e r n e t h o w e v e r ，t h er e s e a r c ho fq o si si m p o r t a n tt op r o m o t et h e d e v e l o p m e n to ft h eu t i l i z a t i o noft h en e t w o r k ，t oi n c r e a s et h ew o r ke f f i c i e n c yo f p e o p l ea n dt ob e t t e rt h eu t i l i z a t i o no ft h ei n t e r n e t r e c e n tr e s e a r c h e sh a v es h o w n t h a tt h en e t w o r kr o u t i n ga l g o r i t h mp l a y sa ni m p o r t a n tr o l e i n r e a l i z i n g q u a l i t y g u a r a n t e e dn e t w o r ks e r v i c e t h en e t w o r kr o u t i n ga l g o r i t h me n s u r e st o b a l a n c et h en e t w o r kl o a da n du t i l i z et h en e t w o r kr e s o u r c e sf u l l y t h eb a s i ck n o w l e d g er e l a t e dt ot h er e s e a r c ho ft h ep a p e ri sf i r s t l yi n t r o d u c e d i nt h ep a p e r ，a n dt h ec l a s s i f i c a t i o nm e t h o d soft h er o u t i n gp r o t o c o l ，t h eb a s i c r o u t i n ga l g o r i t h m sa n dt h ep r e s e n tr e s e a r c hc o n d i t i o n s r e l a t e dt ot h ep o p u l a r p r o b l e m sa r es u m m a r i z e d t h e n ，a ni n t e l l i g e n tt r a n s m i t t i n ga l g o r i t h ma c c o r d i n gt o t h en e e do ft h er o u t i n gi n f o r m a t i o ni ss h o w n ，w h i c hu t i l i z e si n t e l l i g e n ta g e n t t e c h n i q u et oc h e c kt h er o u t i n gt a b l ea c t i v e l ya n dc o n t i n u o u s l y ，a n dt h ea g e n tr e a d s t h en e w l yc h a n g e dr o u t i n gi n f o r m a t i o na n dg i v e si tt ot h et r a n s m i t t i n ga g e n tt o t r a n s m i t t h e r e f o r e ，t h e w a s t eo ft h eb a n d w i d t hs o u r c ec a u s e db yf r e q u e n t t r a n s m i t t i n gr o u t i n gt a b l ei sa v o i d e d f i n a l l y ，t h es w i f ta s t r i n g e n c yo ft h en e u r a l n e t w o r ka l g o r i t h mi su s e d ，a n dt h ee x i s t i n gr e s u l t so ft h ea r t i f i c i a li n t e l l i g e n c ei s q u o t e dt og i v ear o u t i n ga l g o r i t h m ，w h i c hs a t i s f i e sq o s ，a c c o r d i n gt ot h en e e do f t h ea l g o r i t h m t h ep a p e ra l s oa n a l y z e st h eq u a l i t yo ft h ea l g o r i t h mt h e o r e t i c a l l y a n di m i t a t e si tb ys o f t w a r e ，a n dt h ee x p e r i m e n t a lr e s u l t sa r ea n a l y z e d i nc h a p t e r f i v e ，t h er e s e a r c hs i t u a t i o na n dt h ep r o b l e m st ob es o l v e da r es u m m a r i z e d k e yw o r d s ：r o u t i n g ，q o s ，i n t e l l i g e n ta g e n t ，n e u r a ln e t w o r k 2 独创性声明 本入声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致瀚的地方外。论文中不包含其他入已经发表或撰 写过的研究成果，也不包含为获得山东理工大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的晚明并 表示了谢意。 研究生签名 谷孵 时间：洳年6 月f 7 只 关于论文使用授权的说明 本人完全了解山东理工大学有关保留、使用学位论文的规定，即：学校有权保留送 交论文的复印件和磁盘，允许论文被查阅和借阅；学校可以用不同方式在不同媒体上发 表、传播学位论文的全部或部分内容，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名 导师签名：袈 _ l 时间乏趣年6 月 i 时l h j ：渤s 耳易只 r 日 n 山东理t 大学坝i 学位论史 第一章绪论 第一章绪论 1 1 研究背景与意义 随着i n t e r n e t 业务和用户数量的急速增长，越来越多的人开始关注互联网技术。 i n t e m e t 作为我们这个时代最有影响力的技术，它呵以说已经或者l 卜在改变很多人的 生活。i n t e r n e t 正在发生着前所未有的变化，主要表现在：一方面是光通信技术的发 展给网络带来了比较富裕的带宽和廉价的传输能力，目前利用一根光纤能够传送每秒 太比特数量级的信息流；另一方面是网络的应用i f 从单一的文本传输向多样化的多媒 体应用转变，比如坤电话、交互式多方游戏、网上视频播放等，未来还可能出现更 多新的应用。但是，目前，基于存储转发机制的i n t e m e t ( i p v 4 标准) 只为用户提供 了“尽力而为( b e s t e f f o l l ) ”的服务，不能保证数据包传输的实时性、完整性以及到 达的顺序性，不能保证服务的质量，所以主要应用在文件传送和电子邮件服务。随着 i f l t e m e t 的飞速发展，人们对于在n t e m e t 上传输分布式多媒体应用的需求越来越大， 一般来说，用户对不同的分布式多媒体应用有着不同的服务质量要求，这就要求网络 应能根据用户的要求分配和调度资源，因此，传统的所采用的“尽力而为”转发机制， 己经不能满足用户的要求。为了解决在i n t e m e t 等计算机网上高质量地传输多媒体信 息地问题，美国于1 9 9 6 年底，开始了以提高网络服务质量研究为核心的i n t e m e t 以及 n g i ( 下一代h t e m e t ) 等研究项目。r r f ( n m m e te n 西n e e r i n gt a s kf o m e ) 也成立 了专门的工作小组来研究多媒体服务质量的定义和相关的标准。 服务质量( q u n i t yo fs e r v i c e ，简称q o s ) 是网络与用户之间以及网络上互相通 信的用户之间关于信息传输与共享的质的约定。服务质量可以由一些特定的参数来描 述，服务的提供者允许服务的使用者在建立连接时对各种服务参数指定希望的、可接 受的最低限度值，有些参数还可以用于无连接的传输服务。服务的提供者根据网络服 务的种类或它能够获得的服务来检查这些参数，决定能否提供所要求的服务。 1 些典 山东理t 丈学硕士学位论文 第一章绪论 型参数如下：网络带宽、传输延时、延时抖动、差错率等。在i n t e r n e t 上对网络服务 质量的要求也越来越高，例如，视频会议、网络电话的实时和带宽要求，大数据量数 据备份的完成时间要求等。如何在网络中实现多种服务质量是全世界通信领域竞相研 究的重点课题”1 。 q o s 的研究有多个方面，包括流量整形( t r a f f i cs h a p i n g ) 1 2 1 包调度算法( p a c k e t s c h e d u l i n g ) ( 3 1 路由算法( q o sr o u t i n g ) 4 1 、资源预留( r e s o u r c er e s e r v a t i n ) 1 5 1 、 接入控制( c a l la d m i s s i o nc o n t r 0 1 ) 同等的研究。在q o s 的早期研究中，主要的研究 集中于网络节点间的调度策略、接入控制策略上，而网络路由算法的研究一赢被忽视。 近几年的研究表明网络路由算法对实现网络保证质量的服务起到了非常关键的作用， 同时网络路由算法也是平衡网络负载和充分剥用网络资源的重要保证【4 l 。 以提高网络资源利用效率、为用户提供高质量服务作为目标的q o s 研究是当前 i n t e r n e t 领域的热点之一。q o s 问题本质上是研究网络资源的管理和控制问题，由于 计算机网络本身存在的缺陷和i n t e m e t 的复杂性，使得i n t e m e t 的q o s 研究存在极大 的困难。但q o s 的研究对推动网络应用的发展，提高人们的工作效率，优化i n t e r n e t 的利用具有极其重要的意义。 1 2i n t e r n e t 网络基础研究 技术和应用需求的发展，暴露了当前网络技术的瓶颈。从国际范围看，主要体现 在以下三个方面的矛盾；高速的传输信道( 千兆位传输网络) 与低速的协议软件处理( 如 l p 分组转发软件、代理服务器软件) 之间的矛盾；多种网络应用需求与单网络服务 之间的矛盾；动态应用需求( 在i n t e m e t 异构环境下，应用需求随着应用参与方网络接 入环境和主机环境的不同而动态变化) 与静态网络服务提供( 现在i n t e r n e t 服务尚不能 根据用户需要定制不同服务) 之间的矛盾。 从国内看，由于国内极其欠缺网络基础研究，我们在通信协议控制算法方面的研 2 山尔埋_ 人学坝十学位论文 第一章绪论 究至少比固际发达巨】家落后约1 5 到2 0 年，其结果是我什j 无法制造出像c i s c o 公司那 样的高档路出器，也没有设计出因际认可或业界默认的高性能网络协议，也就无法通 过技术优势参与新一代的国际竞争。因此，为了能与幽际计算机网络发展同步，全面 展丌高性能网络的研究，需要同时深入开展网络基础研究。 网络基础研究主要包括以下内容： ( 1 ) 网络体系结构。这是网络研究中最基本的课题。 ( 2 ) 网络协议模型。在现代高性能网络环境下，网络铷议已经扩展到多方交 互协议、具有时问限制的交互协议以及具有不同服务质量要求的交互协议。如何建立 这类高性能网络环境下的协议交互模型是一个重要的课题。有关专家建议研究：a ) 多点交互的协议模型，如应用于计算机会议系统的协议行为模型；b ) 具有服务质量 ( q u a l i t yo fs e r v i c e ) q o s 约束的协议模型，如具有时延限制的协议模型：c ) 具有主动性 的西议模型，如可编程协议模型和移动智能代理协议模型。 ( 3 ) 网络协议控制算法。如差错控制、拥塞控制以及流量控制算法等是决定协议 优劣的主要因素。a ) 多点交互协议中的差错控制、拥塞控制以及流量控制算法；b ) 具 有q o s 约束的协议中的差错控制、拥塞控制以及流量控制算法；c ) q o s 路由选择算 法和多播路由选择算法，其中q o s 路由选择算法是一个n p 完全的问题。 ( 4 ) 网络性能评价模型。将研究的成果最终映射为可以实现的网络系统。 技术发展、应用需求的发展提出了高性能网络的研究课题，例如在宽带网中，不 同的业务，如语音、数据、图像等在对时延、丢失率等网络传输性能方面有不同的要 求。语音业务对时延敏感而对丢失率不敏感，数据业务属于时延不敏感而丢失率敏感 类型，图像属予对时延敏感而丢失率不敏感的业务类型。这样，若以单一的度量值柬 作为各种不同业务的路由选择标准是不恰当的。对于多度量值的网络路由方案，它是 一个n p c o m p l e t e 问题，一般不能公式化为多个目标的最优化数学模型来求解。 山东理工人学硕i ：学位论史第一章绪论 在网络、链路状态的管理与控制模型中，自适应模型、动态模型和不确定模型这 三类模型是目前研究的热点。 自适应模型的研究目标是通过引入资源管理策略及其实现机制，为网络应用提供 可靠、高效、公平的系统服务。 动态模型的最显著特征是其动态特性，即系统必须在运行过程中实时地处理所出 现的异常、随机事件和局部故障，实现动态重构，而且，动态模型应该能够对分布实 时资源进行管理，及时监测外部环境和内部状态引发的分布应用负载变化，并依据性 能需求参数和当时的系统资源状况实时地调整资源分配，以保证分布任务集中可靠地 实时活动。 不确定模型是针对网络状态信息的不精确而提出的。由于在真实的网络中，网络 的流量存在突发性。网络的负荷也就很不平衡，这样就不可能做到随时更新网络状态 信息，加之网络规模的不断扩展和网络本身的分层结构，导致网络状念信息必然存在 某种程度上的不精确性。为此必须设计相应的算法提高网络信息利用的准确性。 1 3 研究内容与成果 1 3 1 具体内容安排 第一章绪论阐述研究背景和研究的重要意义，简述了本文的主要研究成果及 刨新点。 第二章研究综述集中介绍与本文研究内容有关的基础知识，综述了路由策略的 分类方法、基本的路由实现算法、评价标准以及相关热点问题的研究现状。 第三章多a g e n t 协作技术在路由信息传播中的应用随着网络规模越来越大， 路由表也越大，按需计算的路由表的传播所占的网络带宽就越大，严重影响网络性能。 该文使用智能a g e n t 技术对路由表进行主动式不间断检测，由a g e n t 及时读取最新更 改的路由信息交给传播a g e n t 进行传播，从而避免了频繁传输路由表造成的带宽资源 4 山东螋丁人学硕上学位论文筇章绪论 量鲁舅蔓蔓曼h l i i | 曼量皇鼍曼量皇堂皇暑! 巳罡曼鲁量量罾| 皇e 曼蔓蔓曼曼曼量鲁| 鼻 的浪费。 第四章使用神经网络进行路由的按需计算利用神经网络算法的快速收敛性 。引，借鉴人工智能的已有成果：智能a g e n t 技术，提出种满足q o s 需求的按需计算 路由算法，并对算法的性能进行了理论分析与软件的模拟，得出有参考价值的结论。 第五章总结与展望阐述了作者对研究方向的认识和一些正在研究尚未完成 的问题。 1 , 3 2 主要研究成果 1 、应用j a v a 语言和多a g e n t 协作技术设计了一个路由信息智能化传播方法。该 方法只考虑按需计算路由信息，这样每次只对所到达任务的特殊请求计算路由，对路 由表的更新是局部更新，路由信息变化的项目也相对较少。 2 、神经网络的实时计算和预测能力与多a g e n t 技术的分布处理及移动处理能力 相结合，建立了一个按需计算的分布式动态路由选择策略，并给出了浚策略的模型与 实现算法，算法是简单并且实用的。 山东理丁 学厩士学位论史 笫章锚论 的浪费。 第四章使用神经网络进行路由的按需计算利用神经网络算法的快速收敛性 州，借鉴人工智能的已有成果；智能a g e n t 技术，提出种满足q o s 需求的按需计算 路由算法，并对算法的性能进行了理论分析与软件的模拟，得出有参考价值的结论。 薷五章总结与展望阐述r 作者对研究方向的认识年u 一些正在研究尚未完成 的问题。 1 3 。2 主要研究成果 1 、麻用j a v a 语言和多a g e n t 协作技术躞讣了 个路由信息智能化传播方法n 该 方法只考虑按需计算路由信息，这样每次只对所到达任务的特殊请求计算路由对路 由表的更新是周部更新，路由信息变化的项目也相对较少。 2 、神经网络的实叫计算和预测能力与多a g e n t 技术的分布处理及移动处理能力 幅结台，建立了个接需计算的分布式动态路由选择策略，并给出了该策略的模型与 实现算法，算法是简单并且实用的。 实现算法，算法是简单并且实用的。 5 山东理工大学硕上学位论文第二幸 m e n l c t 路由相关理论和技术 第二章i n t e r n e t 路由相关理论和技术 2 、li n t e r n e t 的网络模型 传统的i n t e r n e t 的网络模型可以用以下几点来抽象0 i ： ( 1 ) 报文交换( p a c k e t s w i t c h e d ) i n 络与电路交换( c i r c u i t s w i t c h e d ) 十h 比报文交换通过 共享提高了资源的利用率。但在共享方式下，如何保证用户的服务质量是一个很棘手 的问题。 ( 2 ) 无连接( c o n n e c t i o n l e s s ) t n 络i n t e m e t 的结点之间在发送数据之前不需要建立连 接，无连接的网络模型简化了网络的设计，在网络的中间结点上不需要保存和连接有 关的状态信息，但是使用无连接的模型在用户需求大于网络资源时难以保证服务质 量，无连接也是网络中出现乱序报文的一个主要原因。 ( 3 ) b e s t e f f o r t 的服务模型b e s t - e f f o r t 即网络不对数据传输的服务质量提供保证。这 个选择与早期的网络应用有关。传统的网络应用主要是f t p ，t e l n e t ，s m t p 等，它 们对网络性能( 带宽、延迟、丢失率等) 的变化不敏感，b e s t e f f o r t 模型可以满足要求。 但b e s t - e f f o r t 模型不能很好的满足新出现的多媒体应用的要求，这要求网络在原有的 服务模型基础上进行扩充。 未来的统一网络将以i p 综合信息网络为主体1 ，包括光学口骨干网与宽带口 本地网络。g 位网络交换枫的出现，使得宽带i p 网络的结构越来越简化，而效率和 速率则越来越高。从网络层次结构来看，m 宽带网络综合信息平台分为三层：高性 能核心层、灵活的网络收集层和多种企业和用户接入层。如图2 1 所示。 6 山东理工大学坝f 学位论文 第二章i n t e r n e t 路由相关理论和技术 图2 11 p 综合信息网络 2 2 路由器、路由原理 2 2 1 路由器 一个典型的计算机网络包含了一定数量的局域网l a n 和广域礴w a n ，而这些网 络之间都是通过路由器来连接的。 随着计算机网络的普及，网络的规模越来越大，任何一个有一定规模的计算机网 络( 如企业网、校园网、智能大厦等) ，无论采用的是快速以太网技术、f d d i 技术， 还是a t m 技术，都离不开路由器，否则就无法正常运作和管理。路由器是计算机网 络的关键设备，而网络路由技术随着网络的日趋复杂化、大型化，已成为网络技术中 的最关键部分。 路由器工作在o s i 模型中的第三层，即网络层。路由器利用网络层定义的“逻辑” 。卜的网络地址( f l oi p 地址) 来区别不同的网络，实现网络的互连和隔离，保持各个网络 的独立性。路由器不转发广播消息，而把广播消息限制在各自的网络内部，发送到其 他网络的数据首先被送到路由器，再由路由器转发出去。路由器只转发i p 分组， 把其余的部分挡在网内( 包括广播) ，从而保持各个网络具有相对的独立性，这样可以 组成具有许多网络( 子网) 互连的大型的网络。由于是在网络层的互连。路由器可方便 地连接不同类型的网络，只要网络层运行的是碑协议，通过路由器就可互连起来。 7 山东理】大学硕士学位论文第二章i n t e r n e t 路由相关理论和技术 网络中的设备用它们的网络地址( t c p l p 网络中为p 地址) 互相通信。口地址是与硬 件地址无关的“逻辑”地址。路由器只根据i p 地址来转发数据。p 地址的结构有两 部分，一部分定义网络号，另一部分定义网络内的主机号。目前，在i n t e r n e t 中采用 子网掩码来确定口地址中网络地址和主机地址。子网掩码与m 地址一样也是3 2 b i t ， 并且两者是一一对应的，并规定，子网掩码中数字为“1 ”所对应的弹地址中的部分 为网络号，为0 所对应的则为主机号。网络号和主机号合起来，j 构成一个完整 的i p 地址。同一个网络中的主机口地址，其网络号必须是相同的，这个网络称为 子网。通信只能在具有相同网络号的伊地址之间进行，要与其它i p 子网的主机进行 通信，则必须经过同一网络上的某个路由器或网关( g a t e w a y ) 去。不同网络号的伊 地址不能直接通信，即使它们接在一起，也不能通信。路由器有多个端 f ，用于连接 多个i p 子网。每个端口的p 地址的网络号要求与所连接的p 予网的网络号相同。 不同的端口为不同的网络号，对应不同的口子网，这样才能使各子网中的主机通过 自己子网的1 p 地址把要求出去的i p 分组送到路由器上。 路由器主要呈以下三种发展趋势1 1 2 】：1 、越来越多的通道功能以硬件的方式来实 现；2 、采用并行处理技术；3 、放弃使用共享总线，而使用交换背板。 2 2 2 路由原理 p 子网中的一台主机发送口分组给同一i p 子网的另一台主机时，它只要直接把 i p 分组送到网络上，对方就能收到。而要送给不同p 子网上的主机时，它需要选择 一个能到达目的予网的路由器，把口分组送给该路由器，由路由器负责把碑分组送 到目的地。如果没有找到这样的路由器，主机就把m 分组送给一个称为“缺省网关 ( d e f a u l tg a t e w a y ) ”的路由器上。“缺省网关”是每台主机上的一个配置参数，它是接 在同一个网络上的某个路由器端口的口地址。路由器转发p 分组时，只根据i p 分 组目的i p 地址的网络号部分，选择合适的端口，把p 分组送出去。同主机一样，路 山东理工人学坝上学位论义第二审i n t e m e t 路由相关理论和技术 山器也要判定端口所接的是否是目的子网，如果是，就直接把分组通过端口送到网络 上，否则，也要选择下个路由器来传送分组。路由器也有它的缺省网关，用来传送不 知道往哪儿送的口分组。这样，通过路由器把知道如何传送的口分组正确转发出去， 不知道的i p 分组送给“缺省网关”路由器，这样一级级地传送，t p 分组最终将送到 目的地，送不到目的地的妒分组则被网络丢弃了。目前t c p i p 网络，全部是通过路 由器互连起来的，i n t e m e t 就是成千上万个l p 子网通过路由器豆连起来的国际性网络。 这种网络称为以路由器为基础的网络( r o u t e r b a s e d n e t w o r k ) ，形成了以路由器为节点的 “网间网”。在“网间网”中，路由器不仅负责对口分组的转发，还要负责与别的路 由器进行联络，共同确定“网间网”的路由选择和维护路由表。路由动作包括两项基 本内容：寻径和转发。寻径即判定到达达的地的最佳路径，由路由选择算法来实现。 由于涉及到不同的路由选择协议和路由选择算法，要相对复杂一些。为了判定最佳路 径，路由选择算法必须启动荠维护包含路由信息的路由表，其中路由信息依赖于所用 的路由选择算法而不尽相同。路由选择算法将收集到的不同信息填入路由表中，根据 路由表可将目的网络与下- - g ) h ( n e x th o p ) 的关系告诉路由器。路由器间互通信息进行 路由更新，更新维护路由表使之正确反映网络的拓扑变化，并由路由器根据量度柬决 定最佳路径。这就是路由选择协l s ( ( r o u t i n gp r o t o c 0 1 ) ，例如路由信息协议( r i p ) 、开放 式最短路径优先协议( o s p f ) 和边界网关协议( b g p ) 等。转发即沿寻径好的最佳路径传 送信息分组。路由器首先在路由表中查找，判明是否知道如何将分组发送到下一个站 点( 路由器或主机) ，如果路由器不知道如何发送分组，通常将该分组丢弃；否则就根 据路由表的相应表项将分组发送到下一个站口点，如果目的网络直接与路由器相连， 路由器就把分组直接送到相应的端口上，这就是路由转发协议( r o u t e dp r o t o c 0 1 ) 。路 由转发协议和路由选择协议是相互配合又相互独立的概念，前者使用后者维护的路由 表，同时后者要利用前者提供的功能来发布路由协议数据分组。 山东理工人学硕上学位论史第二蕈i n t e r n e t 路由相关理论嗣技术 2 3 路由选择策略 路由选择策略也称为路由协议( r o u t i n gp r o t o c 0 1 ) ，它是路由器之间实现路由信息 共享的一种机制，它允许路由器之问相互交换和维护各自的路由表。当一台路由器的 路由表由于某种原因发生变化时，它需要及时将这一变化通知与之相连接的其它路由 器，以保证数据的正确传递。目前路由器中常用于t c p i p 的路由协议包括r i p ( r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 、i g r p ( i n t e r i o rg a t e w a yr o u t i n gp r o t o c 0 1 ) 、o s p f ( o p e n s h o r t e s tp a t hf i r s t ) 、n l s p ( n e t w a r el i n ks e r v i c e sp r o t o c 0 1 ) 和e i g r pfe n h a n c e di g r p ) 等。 路由选择包含两个基本任务：收集状态信息并更新和基于收集的信息为一新的请 求寻找一可行的路径。习惯上，按照路由机制把路出选择策略简单地分为静态路出选 择策略和动态路由选择策略两种。 2 3 i 静态路由选择策略 静态路由策略是依靠手工输入的信息来配置路由表的方法，它不用测量也不需利 用网络信息，按照某种固定规则进行路由选择，其实现算法可分为泛射路由选择 ( u n i v e r s a l - c a s tr o u t i n g ) 、固定路由选择( r e g u l a rr o u t i n g ) 、随机路由选择( r a n d o m i z e d r o u t i n g ) 和分散通信量法四种算法1 3 1 。 静态路由是预编程的，其中的路出器早已编好程序为到来的分组预定了出口。在 目的结点地址和路由器一个端口确认建立联系之后，路由器便不再需要寻找和发现路 由甚至不再需要与其它各个路由器进行通信了。所以在静态路出中谈不上路由选择策 略，一般路由选择策略都是针对动态路出而言的。 静态路由最大的问题是：当网络变化时，它要求手工配置，一旦网络出现故障也 必须人工排除。所以，它的使用就受到了限制。然而，在稳定的网络中熟练地使用静 态路由能够减少路由选择问题和路由选择数据流的过载。静态路由的价值还表现在构 1 0 山东理t 大学坝l ：学位论文 第一章i n t e m e l 路由相关理论和技术 筑非常火型的网络中，各大区域通过- n 两条主链路连接。静态路由的隔离特征有助 于减少整个网络中路由选择协议的开销、限制路由选择发生改变和出现问题的范围。 2 3 。2 动态路由选择策略 结点的路由选择要依靠网络当前的状态信息来决定的策略，称动态路由选择策 略。这种策略能较好地适应网络流量、拓扑结构的变化，有利于改善网络的性能。但 由于算法复杂，会增加网络的负担。动态路由选择策略通常为以下三种“】：源端路由、 分布路由和层次路由。 l 、源端路由每个结点都维护完整的全局信息，源端结点根据全局信息计算一条可 行路径，然后沿着这条选出的路径发一个控制消息，通知中间结点其前驱和后继结点。 这种策略f ，每个结点使用链状态协议更新全局状态。源端路由以集中方式计算路由， 可以避免分布计算面临的一些问题，如死锁检测和预防等，还能确保没有循环的路径， 并且易于实现、评估、调试和升级。另外，为解决某些n p 完全的路由计算问题，集 中方式下的启发式算法比分布方式更容易设计。但源端路由有以下几个缺点，首先是 扩展性极差，为与不断变化的网络参数( 如带宽和时延) 保持一致，结点的全局状态必 须频繁更新，这对大型网络来说开销很大。其次，为减少开销而降低更新频率以及更 新消息本身有一定的传播时延，结点只能提供不太精确的状态信息。结果q o s 路由 可能发现不了实际存在的一条可行路径。另外，源端结点的计算负荷会很重，尤其是 在组播和多约束条件的q o s 路由情况下更是如此。 2 、分布式路由这种路由选择策略是每个结点周期性地从相邻的结点获得网络状态信 息， 同时也将本结点做出的决定周期性地通知周围的各结点，以使这些结点不断地 根据网络新的状态更新其路由选择决定。所以整个网络的路由选择经常处于一种动态 变化的状况。一般来说，一个分布式的路由选择方法包括以下三个要素：a 、对于 网络的某种特性的测量过程；b 、关于如何传播上述特性的测量结果的协议；c 、如 山东理t 大学硕上学位论文 第二章i n t e r n e t 路由相关理论和技术 何计算出所确定的路由 3 、层次路由网络中的结点都群集成组，然后这些组递归地再群集成更高级的组，形 成一个多级的层次结构。每个层的组都称为其上一层的逻辑结点。每个最底层的结点 ( 实际的网络结点) 都维护一个汇聚的全局状态信息。汇聚的全局状态信息也是分层 的，每一层的信息包括本层中同属一个组的逻辑结点和逻辑链路的详细信息和其它组 的汇聚信息。在最上层的逻辑结点间采用源端路由找到一条可行逻辑路径，然后一个 控制消息沿着这条逻辑路径发送以建立真实的连接。当路径上逻辑结点所代表的组的 边界结点( 即下层的逻辑结点) 收到消息后，则它在这个组内仍采用源端路由扩展路径 到该组的出口边界结点，递归这样的过程，直到真实的连接建立。 4 、三种路出策略的比较和有待解决的问题 由于以下原因，使源路由不具有良好的可扩容性；通信开销与网络规模和本地信 息的广播频率成正比；存储开销与网络规模成证比；计算开销为网络规模的多项式时 间，且与连接请求的频率成正比；全局信息的准确度与网络规模( 或网络半径) 和广播 频率成反比。当网络规模扩大时，其对应的通信行销、存储开销和计算开销都相应地 增长。降低网络信息更新频率并不能解决此问题，因为全局信息的准确度也会随之下 降。 分布式算法可以部分解决扩容性问题。例如基于选择性探测的分布式路由算法仅 需要局部信息，而基于令牌探测的分布式路由算法可以克服信息的不精确性问题，从 而可以降低网络的通信开销。 目前还没有处理n p - 完全问题的高效率分布式算法，特别是在组播通信中。这主 要是由于没有详细的拓扑信息和链路信息可供使用。而如果在不同节点的全局信息不 一致的话，就有可能产生环路。环路可以通过控制包到达同一节点两次来检测，但环 路将导致路由失败，因为距离向量信息不能给出足够的信息来确定替代路由。 山东埋丁丈学顿上学位论文 第一章i n t e m e t 路由相关理论和技术 层次路由对扩容性问题给出了清晰的解决方案。由于每个节点仅保存经聚合的全 局信息，远端物理节点的信息用经过聚合的逻辑节点信息代替，这种聚合信息的规模 仅是全局信息规模的对数函数。因而其具有良好的可扩容性。另外由于计算是分靠式 进 j ：的，因此也具有分布式路由的优点。然而，由于信息聚合会产生附加的不确定性， 其算法性能会随网络规模而急剧降低。因为q o s 路由对网络状态的不确定性比较敏 感，故而研究能适应网络不确定性的路由算法就变得t 分重要。另外，由于层次路由 是把有复杂拓扑结构的组用一个逻辑节点代替，因而在做本地计算时，远端节点的具 体信息是不可见的，从而使精确计算本地物理节点到远端物理节点的q o s 度量参数 值不可能。此问题在涉及多q o s 度量参数约束时，将更加复杂。因此，如何对状态 信息进行聚合目前还是个待解决的问题。 2 4 q o s 路由 q o s 路由和基于q o s 的传输调度是当前i n t s e r y 领域研究的热点问题。q o s 路由 需要在信息传输之前在源节点和目的节点之间寻找符合q o s 需求的传输路径，并通 过r s v p 协议为其预留资源。在i n t s e r y r s v p 模型中的q o s 路由算法的研究中，多 个限制条件下的q o s 路由算法、q o s 组播路由算法、q o s 路由实现及性能评测等问 题难度较大，需要更深入地研究。 2 4 1 加权图模型 网络的拓扑结构和资源容量可以抽象为一个加权图( v ，e ) 。其中节点( v ) 代表网 络中的交换设备，边( e ) 代表传输线路。如果传输线路是对称的，则对应的边是无向 的。因为对称线路对两个方向上的数据都有同样的特性。对于大多数实际的网络而言， 其链路一般都是非对称的，因而其每一条链路对应于模型中，就是两条有向的加权边。 每一条链路都有一个对应于相关q o s 度量的状态。而每一个节点也有相应的状态， 它可以单独表示出来，或者也可以把它折算到与节点相连的链路状态中去。 2 4 2 状态信息 “l 东理工太学坝t 学位论文第二章l n ! 舯脚路由相关理论和技术 ( 1 ) 本地信息 每一个节点都必须保持其最新的本地信息，包括链路传输时延、排队时延、输出 链路的剩余带宽以及其他网络资源的可用性信息。 ( 2 ) 全局信息 所有节点本地信息的总和就构成了全局信息。每个节点可以用链路状态协议或 者距离向量协议来发布、取得全局信息。链路状态协议通过让各节点广播其本地信 息来确定网络的拓扑结构和各链路的状态。距离一向量协议通过相邻节点定期交换其 距离向量来取得并扩散全局信息。每个节点保持的全局信息，总是对现有网络状态 的一种近似。这是由于信息传输时延造成的。而时延的不可避免性表明这种不确定性 会随着嗣络规模的增加两不断扩大。 ( 3 ) 状态信息的聚合 因为任何物理设备的存储资源和处理能力都是有限的，所以对全局信息的精确保 存，会带来扩容性问题，于是降低全局信息的规模就变得十分重要。这可以通过把一 个具有层次性结构的大型网络的局部信息进行聚合来完成，即把包含几个物理节点的 组抽象为一个逻辑节点，而逻辑节点又可以进一步聚合成更高一级的逻辑节点，如此 反复下去。在聚合过程中，必须把下层节点的网络度量特性聚集为本层逻辑节点的度 量特性。这种过程是复杂的，而不同的聚集方法对状态信息的影响也是一个开放性的 问题。如口的内部网关路由算法o s p f 支持两层的聚合信息发布，而a t m 可支持任 意多层的聚合。必须注意的是聚合引入了额外的不确定性，并且不确定性会随聚合层 次的增加而变大。聚合后的两个逻辑节点间的链路有可能对应于多条物理链路，从而 引入新的问题。 2 4 3q o s 度量 对于路径p = ( a ，b ，c ，f ，g ) ，用d ( a ，b ) 表示对应链路( a ，b ) 的度量，则q o s 4 山东理工大学坝。卜学位论殳 第一审l n l e m e t 路由柑关埋论用j 技术 度量可以按性质分为以下三类： ( 1 ) 5 性q o s 度量 如果d ( a ，g ) = m i n d ( a ，b ) ，d ( b ，c ) ，d ( f ，g ) ，那么度量由传输通道中的 瓶颈决定，即此度量仅与路径上的某个瓶颈链路的q o s 度量有关，如剩余带宽、剩 余缓存空间、链路速率等。 ( 2 ) 加性q o s 度量 如果d ( a ，g ) = d ( a ，b ) + d ( b ，c ) + + d ( f