（计算机科学与技术专业论文）isis协议路由计算方法的研究和实现.pdf

国防科学技术大学研究生院学位论文 摘要 随着网络技术的飞速发展和网络规模的迅速扩大，路由设备的作用日益重要，对它的 性能要求也随之提高。路由协议在路由器之间实现信息交换，其本质就是收集网络中的路 由选择信息并选择到所有已知目的网段的最佳路径，因此路由计算过程和路由表的组织与 管理对于路由器的功能增强和性能提高起到关键的作用。 本文在深入理解i s i s ( i n t e r m e d i a t es y s t e m t o i n t e r m e d i a t es y s t e m ) 路由协议运 行机制的基础上，依据r f c 和i s o 的标准给出了i s - i s 路由计算算法的设计与实现；根据 当今网络前缀的分布特点，提出了一种基于h a s h 的路由表组织方法，并对这种方法进行 了改进；最后针对核心网络上具有多个路由节点的路由器提出了一种并行路由计算方法， 使得路由计算能够在多个节点中同时进行。 本文的主要工作包括： 1 i s i s 路由协议是一种链路状态路由协议，在利用路由信息进行路由计算的时候采 用的是最短路径优先( s h o r t e s tp a t hf i r s t ，s p f ) 算法。因此，首先对s p f 算法有比较 深入的了解，并在此基础之上设计及实现了i s - i s 路由协议的路由计算过程； 2 研究了路由表的高效组织与管理。分析了当前常用的路由表组织方法，提出了一种 基于h a s h 的路由表的组织方式，结合网络前缀的分布特点，对这神基于h a s h 的路由表组 织方法进行了改进和实验，在理论上分析了该算法的性能，并在实验中比较了该算法和其 它算法的性能差异； 3 针对目前大型网络中核心层采用的高性能核心路由器有多个路由节点的特点，将现 有的i s i s 路由域划分为路由子域( r o u t i n gs u b - a r e a ，r s a ) ，提出了一种由各个路由 节点并行计算路由表的方法，给出了算法的正确性以及可行性分析，在路由节点数目为n 的情况下，能将域内更新路由计算的加速比提高到n 至n 2 ，域外更新路由计算的加速比提 高到n 。 关键词：高性能路由器，i s i s ，链路状态路由协议，路由表，并行，路由计算 国防科学技术大学研究生院学位论文 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 en e t w o r kt e c h n o l o g ya n d q u i c ke x p a n s i o no ft h en e t w o r k s c a l e ，r o u t e r sh a v eb e c o m em o r ei m p o r t a n ta n dw eh a v eh i g h e rr e q u i r e m e n t so nt h e m ，r o u t i n g p r o t o c o l sa r ei nc h a r g eo fe x c h a n g i n gi n f o r m a t i o nb e t w e e nr o u t e r s ，w h i c he s s e n c ei st oc o l l e c t t h er o u t i n gi n f o r m a t i o na n dc h o o s et h eb e s tp a t ht ot h ee n t i r ek n o w nn e t w o r k s ot h ep r o c e s so f r o u t i n gc o m p u t a t i o na n dt h eo r g a n i z a t i o n ，m a n a g e m e n to fr o u t i n gt a b l ep l a yak e yr o l ei n i m p r o v i n gr o u t e r sp e r f o r m a n c e t h i st h e s i sp r o p o s e dad e s i g na n di m p l e m e n to fi s - i s ( i n t e r m e d i a t es y s t e m - t o - i n t e r m e d i a t e s y s t e m ) r o u t i n g - c o m p u t e da l g o r i t h m o nt h eb a s eo fd e e p l yu n d e r s t a n dt h em e c h a n i s m o fi s i s r o u t i n gp r o t o c o l ，w h i c hw a sa c c o r d i n g t ot h er f ca n di s os t a n d a r d a c c o r d i n gt od i s t r i b u t a r y s c h a r a c t e r i s t i co fn e t w o r kp r e f i x ，a no r g a n i z a t i o no fr o u t et a b l ew a sp r o p o s e d ，w h i c hw a sb a s e d o nh a s h ，a n dt h e ni m p r o v e di t i nt h ee n d ，w ep r o p o s e dap a r a l l e lr o u t i n gc o m p u t a t i o n ，w h i c h w a sa i m e da tt h es e a l a b l ea n dm u l t i r o u t en o d e si pr o u t e r so nc o r en e t w o r k t h ep r i m a r yc o n t r i b u t i o n so ft h i st h e s i si n c l u d et h ef o l l o w i n gf o u rp a r t s f i r s t l y ，i s i sr o u t i n gp r o t o c o li sal i n k s t a t er o u t i n gp r o t o c o l ，w h i c hu s e ds h o r t e s tp a t hf i r s t ( s p f ) a l g o r i t h mt oc o m p u t et h er o u t i n gp a t h s oo nt h eb a s eo fd e e p l yu n d e r s t a n dt h es p f a l g o r i t h m ，w ed e s i g n a n di m p l e m e n tt h ep r o c e s so fr o u t i n gc o m p u t a t i o nf o ri s i s r o u t i n g p r o t o c 0 1 s e c o n d l y ，t h eo r g a n i z a t i o na n dm a n a g e m e n to fr o u t i n gt a b l ew a ss t u d i e di nt h ep a p e r b a s e d o na n a l y s i so ft h ec o m m o no r g a n i z a t i o no fr o u t i n gt a b l e ，t h i st h e s i sp r o p o s e da no r g a n i z a t i o n m e t h o d ，w h i c hb a s e dh a s h ，a n dm o d i f i e di t w i t h e x p e r i m e n ta c c o r d i n gt od i s t r i b u t a r y s c h a r a c t e r i s t i co fn e t w o r kp r e f i x t h et h e s i sa l s oa n a l y z e dt h ep e r f o r m a n c eo ft h ea l g o r i t h mi nt h e t h e o r y ，a n dc o m p a r e di tw i t ho t h e ra l g o r i t h m sw i t he x p e r i m e n t s l a s t ，ag e n e r i cs c a l a b l ei pr o u t e rt h a tw a su s e di nn o w a d a y sc o r en e t w o r ki st y p i c a l l y c o m p o s e do fan u m b e ro fr o u t i n gn o d e s a i m e da tt h i sc h a r a c t e r ，b yd i v i d i n ga ni s - i sa r e ai n t oa n u m b e ro fd i s j o i n tr o u t i n gs u b - a r e a ( r s a s ) ，t h ec o m p u t a t i o nr e q u i r e dt oc a l c u l a t et h er o u t i n g t a b i ec a nb ed i v i d e di n t om u l t i p l ei n d e p e n d e n tp o r t i o n sa n dd o n eb yd i f f e r e n tr n si np a r a l l e l t h e nw ea n a l y z e dt h ef e a s i b i l i t ya n dc o r r e c t n e s so ft h i sa l g o r i t h m ，c o m p a r e dt oc o n v e n t i o n a l a p p r o a c h e s ，t h i sa p p r o a c hc a nh a v eas p e e d u pb e t w e e nna n dn 2f o rw i t h i n a r e al i n ks t a t e u p d a t e sa n d nf o ro u t s i d e a r e ai i n ks t a t eu p d a t e s w h e r eni st h en u m b e ro fr n si nt h er o u t e r k e y w o r d s ：h i g hp e r f o r m a n c er o u t e r , i s - i s ，l i n k - s t a t ep r o t o c o l ，r o u t i n gt a b l e ，p a r a l l e l ， r o u t i n gc o m p u t a t i o n 国防科学技术大学研究生院学位论文 图目录 图2 1o s i 参考模型与t c p i p 协议栈4 图2 2v x w o r k s 实时操作系统结构示意图7 图2 3v x w o r k s 操作系统的基本构成部件示意图8 图3 1 有向图1 2 图3 2i s i s 协议软件外部结构1 4 图3 3i s - i s 协议软件内部结构1 5 图3 4 路由转发体系结构1 6 图3 5i s - i s 主要数据结构2 0 图3 6i p v 6 下的i s i st l v 数据包，2 9 图3 7i p v 6 下的i s i s 子t l v 数据包3 0 图3 8i s i si p v 6 接口地址t l v 数据包3 0 图4 1 一个r a d i xt r i e 树3 6 图4 2 可变步距多分支t r i e 树3 7 图4 3h a s h 路由表3 8 图4 4 二分法搜索h a s h ，3 8 图4 5 压缩路由前缀3 9 图4 6 压缩后的二叉树3 9 图4 7 前缀分布( 纵向为对数尺度) 4 0 图4 82 4 8d i r 算法原理示意图4 0 图4 9h a s h 路由表组织4 2 图4 1 0 改进的h a s h 路由表组织，4 4 图5 1 可扩展路由器4 8 图5 2 路由域5 0 图5 3 路由子域5 0 国防科学技术大学研究生院学位论文 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：! ；二! ；进送竖直盐笠左这啦盟窥塑塞塑 学位论文作者签名：荽21 座连日期：删9 年，二月垢日 i f 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：! ；二! 边送整由盐簋虚壁的盟壅塑塞塑 学位论文作者签名 作者指导教师签名 盏。垃边 刍邕盟 日期：却移年五月穆日 日期：) ，f 年，l 月? d 日 国防科学技术大学研究生院学位论文 1 1 i 网络与高性能路由器 第一章绪论 1 1 课题背景及问题的提出 几十年来，计算机工业取得了惊人的发展。特别值得一提的是，计算机与通信的结合 对计算机系统的组织方式产生了深远的影响。单台计算机为机构中所有的计算机服务这一 工作模式很快被大量分散但又互联的计算机来共同工作的模式所代替。我们称这样的系统 为计算机网络。 高性能计算机和信息网络是国家经济信息系统的基础，它反映了一个国家的综合科技 实力。随着信息技术的高速发展，具有快速、及时、多样化等特点的网络媒体使从计算机 技术中发展起来的网络技术逐渐在国民经济建设和国防建设中处于日益重要的地位。当计 算机的速度以每一年半翻一番的速度增长的同时，网络带宽则以3 倍于计算机发展的速度 向前推进，即每六个月翻一番。先进计算机的信息处理能力已与支撑它的网络能力密切相 关，不发展高速计算机网络技术，先进计算机的信息处理能力就会受到限制。因此必须大 力发展与信息高速公路直接相关的高速计算机网络技术，它是国民经济及高技术发展的迫 切需要。 我国的国家网络基础设施应具有提供高速、高带宽、q o s 服务保证等多项服务的能力， 同时也对其在网络的安全、可靠性方面提出了更高的要求，特别是一些关系到国民经济建 设和国防军事的重要网络设施，必须要求具有极高的可靠性和防御外来侵扰的能力。而目 前我国网络建设主要基于国外网络产品集成，尽管有一些国产的低端网络设备，但网络中 枢、控制交换中心的网络设备基本上被国外产品占领。国产网络设备与国外产品存在很大 的差距，这种格局存在极大的网络安全隐患。从国家安全战略角度考虑，研制高性能路由 器是适应未来信息战的迫切需要。 i 1 2 链路状态路由协议 路由协议是确定两个节点之间路径的协议。链路状态路由协议适合用于单一网络域 内，因此它是i g p ( i n t r e n a lg a t e w a yp r o t o c 0 1 ) 协议。链路状态路由协议通过传播、分析、 计算、挑选路由实现如下功能： 行使域内路由选择协议功能。 呈现整个网络拓扑，决策最佳路由。 故障情况下提供快速收敛。 提供网络稳定性。 有效利用网络资源，例如路由器内存，c p u 周期和网络带宽。 第1 页 国防科学技术大学研究生院学位论文 i s i s 路由协议基于分层的结构，使用在大型网络上，是当前最流行的链路状态协议。 与r i p 等路由协议相比，它的开销很小，收敛快，不占用很多带宽，具备学习路由、广播 路由等基本的协议功能，因此非常适于大型网络使用。所以设计并实现i s i s 对于完善高 性能路由器的功能具有重要的意义。 路由协议启动之后，与网络上的路由器交换路由信息，然后根据这些路由信息采用特 定的算法计算出到达各个可达目的地的最佳路径，然后再进行报文的转发。路由协议中主 要采用的是距离向量算法和最短路径优先( s p f ) 算法。在i s i s 路由协议中采用的是最 短路径优先算法。高性能核心路由器一般由多个路由节点组成，让这些路由节点采用并行 计算的方法来计算最佳路由，能够直接迅速的提高路由器的性能。 在提高路由计算速度的基础上，随着主干网络互联的高性能核心路由器的接口速率的 飞速增长，对转发分组的速率要求也随之提高，因此路由表的高效组织与查找方式已经成 为近年来研究的热点。 1 2 主要研究内容以及取得的成果 本课题主要囝绕国家“8 6 3 i 计划“下一代互联网络试验环境”进行。在课题的研制 过程中，主要取得了如下几个方面的成果： 详细了解i s i s 的基本用途和各主要功能； 研究并实现高性能路由器i s i s 协议中的路由表的组织与管理以及路由计算算法，采 用s p f 算法对接收到的链路状态信息进行计算，保证能够正确快速的得到到达各个可达目 的地的最短路径； 设计并实现了部分集成i s i s 路由协议的用户界面，主要包括：i p 路由管理接口，使 用目前己定义的i p 路由管理函数，实现i p 路由的添f i n 删除、接收重发布的路由等功能； i p 接口管理接口，使用回调函数的注册机制，接收i p 接口状态或接口参数的变化消息， 并对之进行处理； 对路由表的高效组织与管理进行了研究，改进了风云路由器上用t r i e 树组织的路由 表，现已实现对路由表的两种h a s h 组织方法，针对这三种路由表的组织方法进行了实验， 分别对它们给出了路由查找的性能分析； 针对目前大型网络中核一f l , 层采用的高性能核一f l , 路由器有多个路由节点的特点，将现有 的i s i s 路由域划分为路由子域( r o u t i n gs u b a r e a ，r s a ) ，提出了一种由各个路由节 点并行计算路由表的方法，给出了算法的正确性以及可行性分析。 1 3 论文内容组织 论文共分六章： 第一章为绪论。本章介绍课题背景、主要研究工作和文章内容组织。 第二章为课题研究基础内容。本章主要介绍o s i 参考模型和t c p i p 协议栈相关理论 和路由器软件的开发环境。内容包括软件系统中极为重要的o s i 参考模型和t c p i p 协议 第2 页 国防科学技术大学研究生院学位论文 栈的构成( 第二章第一节：路由器软件中的协议栈) 、t o r n a d o 开发工具所具有的特点( 第 二章第二节：软件开发环境) 以及对v x w o r k s ( 第二章第三节；路由器实时操作系统) 的 系统介绍： 第三章从协议栈进一步引申到它的组成部分之一：i s i s 路由协议中路由计算算法的 设计与实现。该部分内容包括s p f 算法介绍( 第三章第一节：s p f 算法概述) 、实现技术、 算法流程、数据包的转发( 第三章第二节：i s i s 路由计算算法的设计与实现) 、在i p v 6 网络下的路由计算( 第三章第三节：路由i p v 6 报文) 以及当今最流行的两种链路状态路 由协议之间路由计算算法的比较( 第三章第四节：i s i s 0 s p f 路由计算算法比较) 等主要 工作。 本文的第四章首先介绍了i p 地址查找( 第四章第一节：i p 地址查找机理) ，然后综 述了当前主要的路由表查找方法( 第四章第二节：常用的路由表查找方法) ，在此基础之 上，详细给出了一种基于h a s h 的路由表组织与查找方法( 第四章第三节：h a s h 路由表的 设计) ，根据网络前缀的分布特点，对这种方法提出了改进( 第四章第四节：基于h a s h 路由表的改进) ，此外还有选择的对这几种查找算法进行了实验，得出了实验结果。 第五章介绍了核心路由器由多个路由节点组成的特殊结构( 第五章第一节：可扩展的 i p 路由器) ，然后综述了当前主要的并行路由计算方法( 第五章第二节：当前可扩展i p 路由表的计算方法) ，提出了一种由各个路由节点并行计算路由的方法( 第五章第三节： i s i s 的一种并行路由计算方法) 。采用并行路由计算的方法，可以在保证路由计算正确 的基础上，显著提高路由计算的速度，在域内的加速比为n ，域外的加速比为n 到n 2 。 第六章对已经完成的工作进行总结，并指出进一步研究的方向。 第3 页 国防科学技术大学研究生院学位论文 第二章课题研究基础内容 2 1 路由协议的基础 i s i s 协议是开放系统互联模型( o s i ) 的一部分，所以首先介绍开放系统互联模型( o s i ) 的组成。 o s i 协议实际上就是在物理网上运行的一组完整的网络协议“3 。o s i 的分层模型定义了 7 层，如果用与t c p i p 网络协议栈相同的层次模型来描述i s o 的开放系统互联模型( o s i ) ， 那么提供i p 服务的相当于网络层，提供t c p 服务的相当于传输层。其层次结构如图2 1 所示： t c p i p p i b d c “ tt c p n pp r o t 0 0 3 l k r c h i t e d o j r eis u i t e l w e r t i j 。p 。l a i c v a e t r i 。“l 卜n_一ls-一i同刚!”m| l h o s t t o - h o s t n 一 | l lt r a n s p o r t l a y e r b t 一唑坐 i n t e 卉a c e e t h e r n e t t ：i k n e o n a t m 一 图2 ，1o s i 参考模型与t c p i p 协议栈 从图2 1 中可以清晰地看出o s i 和t c p i p 协议栈之间的关系。o s i 的第一层和第二层 相当于网络接口层( n e t w o r ki n t e r f a c el a y e r ) ，它是o s i 的实现基础，如e t h e r n e t 、 t o k e nr i n g 、t o k e nb u s 等。 o s i 第三层相当于i p 、a r p 、i p 、i p ，其中互联网协议( i n t e r n e tp r o t o c o l ，i p ) 负责主机间数据的路由和网络上数据的存储，同时为i c m p 、t c p 、u d p 提供分组发送服务。 用户进程通常不需要涉及这一层。 o s i 第四层相当于t c p 、u d p ，其中传输控制协议( t r a n s m i s s i o nc o n t r o lp r o t o c o l ， t c p ) 是一种向用户进程提供可靠的全双工字节流的面向连接的协议。它要为用户进程提供 虚电路服务，并为数据的可靠传输执行正确性检查。大多数网络用户程序选择使用t c p 。 用户数据报协议( u s e rd a t a g r a mp r o t o c o l ，u d p ) 是向用户进程提供的面向无连接的协 议，它只传送数据而不执行正确佳检查。 o s i 第五层到第七层相当于f t p 、s m t p 、t e l n e t 、t f t p 、h t t p ，其中文件传输协议( f i l e 第4 页 国防科学技术大学研究生院学位论文 t r a n s f e rp r o t o c o l ，f t p ) 允许用户以文件操作的方式( 文件的增、删、改、查、传送等) 与另一主机相互通信。简单邮件传送协议( s i m p l em a i lt r a n s f e rp r o t o c o l ，s m t p ) 在 系统之间传送电子邮件。远程登录终端协议( t e l n e tt e r m i n a lp r o t o c o l ，t e l n e t ) 允许用 户以虚终端方式访问远程主机。超文本传输协议( h y p e r t e x tt r a n s f e rp r o t o c o l ，h t t p ) 是互联网w w w 的基础，它使丰富多彩的i n t e r n e t 以简单的方式展现给用户。简单文件传 输协议( t r i v i a lf i l et r a n s f e rp r o t o c o l ，t f t p ) 是f t p 的一种简化版本。 o s i 的核心部分是传输层、网络层和物理接口层，这三层通常在操作系统内核中实现。 操作系统的内核对一般用户是透明的。 i s i s 路由协议是独立的网络层协议，它与无连接网络服务( c l n s ) 和e s i s 共存于 o s i 参考模型的第3 层。i e t f 在r f c l1 9 5 中定义了“用o s ii s i s 实现在t c p i p 和双重 环境下的路由选择”，也就是著名的“集成i s i s ”。“集成i s i s ”修改了最初用于c l n s 环境的i s i s 协议，可以路由i p 数据包。在本论文中实现的路由表的组织和路由计算是 基于“集成i s i s ”的，符合r f c1 1 9 5 和i s o1 0 5 8 9 的定义。 2 2 软件开发环境 高性能路由器的软件开发过程是在t o r n a d o 开发工具的支持下开展的，因此有必要明 确该开发工具的特点及相关组件。 总的来说，t o r n a d o 具有良好的持续发展能力、高性能的内核以及友好的用户开发环 境。它有以下四个特点： ( 1 ) 十分灵活，具有多达1 8 0 0 个功能强大的应用程序接口( a p i ) ； ( 2 ) 适用面广，可以适用于从最简单到最复杂的产品设计； ( 3 ) 可靠性高，可以用于从刹车系统到星际探索的关键任务； ( 4 ) 适用性强，可以用于所有流行的c p u 平台。 2 3 1 简介 2 3 路由器实时操作系统 所谓实时，就是立即、及时的意思，是指计算机的运算和处理时问与被控过程或事务 处理所需的真实时间相适应。实时系统与其它类型系统的本质差别在于实时系统的及时 性。即实时系统能及时的响应外部事件的请求并在严格规定的时间内完成对该事务的处 理，控制实时设备和实时任务协调一致的运行。 v x w o r k s 操作系统是美国w i n d r i v e r 公司于1 9 8 7 年设计开发的一种嵌入式实时操作系 统( r t o s ) ，是t o r n a d oi i 嵌入式开发环境的关键组成部分。v x w o r k s 是w i n d r i v e r 公司 专门为实时嵌入式系统设计并开发的操作系统软件，为程序员提供了高效的实时任务调 度、中断管理，实时的系统资源管理以及实时的任务间通信等功能。应用程序员可以将尽 可能多的精力放在应用程序本身，而不必再去关心系统资源的管理。该系统主要应用在单 第5 页 国防科学技术大学研究生院学位论文 板机、数据网络( 以太网交换机、路由器) 和通信等诸多方面。通过对v x w o r k s 的研究 可以使我们对嵌入式操作系统的研究和开发更进一步。 2 3 2 特点 w i n d r i v e r 的v x w o r k s 实时系统主要有如下一些特点”1 ： ( 1 ) 可裁剪性：v x w o r k s 采用模块化的设计方式，最小的实时内核可以只有3 0 k ，用 户可以做到基于函数级的裁剪，可以根据应用的具体需要定制一个只包含应用所需a p i 函 数库的最小系统； ( 2 ) 丰富的系统组件和可选模块：支持1 1 0 系统、文件系统、t c p i p 网络协议、图 形界面、2 a v a 虚拟机、内存保护、多c p u 间任务通信和同步、f l a s h 系统管理、在线升级、 工控现场总线和应用组件( 如c a n 、o p c 、d c o m 等) 、设备总线( 如u s b 、i e e e l 3 9 4 、p c m c i a 等) ，并且提供面向汽车电子、网络设备和存储设备应用开发的解决方案，w i n d r i v e r 还 有近i 0 0 0 家的w i n d l i n k 合作伙伴提供面向各种嵌入式应用领域的完整解决方案； ( 3 ) 实时性：提供快速、确定的任务切换，快速的中断响应，快速的任务间同步和 通信机制以及有效的动态内存管理等功能； ( 4 ) 高可靠性：v x w o r k s 广泛的应用在航空航天、国防等对系统可靠性要求极其苛刻 的领域，设备都经过了系统长期运行的检测，十几年都没有发现v x w o r k s 内核的b u g 。而 且，v x w o r k s 通过了美国国防部d o - 1 7 8 b 的认证，在美国的n a s a 和中国的海军、空军、兵 器等系统中已经成为事实上的嵌入式操作系统的标准并且得到应用； ( 5 ) 支持标准编程接口：支持a n s ic 、b s ds o c k e t 和p o s i x 的编程接口，应用程序 具有可移植性： ( 6 ) 支持的c p u 和硬件平台最广：支持m o t o r o l a i b mp o w e r p c 、m o t o r o l ac o l d f i r e 、 m o t o r o l a6 8 k c p u 3 2 、i n t e la r o h i t e c t u r ef a m i l y 、i n t e ls t r o n g a r ma n dx s c a l e m i c r o a r c h i t e c t u r e s 、m i p s 、a r m 、h i t a c h is u p e r h 等几乎所有的3 2 位以上c p u ，w i n d r i v e r 还与i n t e l 、m o t o r o l a 、m i p s 、h i t a c h i 、i d t 等芯片厂家成立了卓越中心( c e n t e ro f e x c e l l e n c e ) ，共同为用户提供完整的嵌入式系统软硬件解决方案，提供所有流行的硬件 的系统移植： ( 7 ) 方便易用的调试工具：提供从软件系统设计、硬件板级调试到软件静态和动态 调试的整个软件开发过程中所要使用到的软件工具，开发和调试界面都是程序员所熟悉的 风格。 2 3 3 核心功能 第6 页 国防科学技术大学研究生院学位论文 v x w o r k s 实时操作系统包括微内核w i n d 、网络支持、文件系统和i 0 管理、c + + 和其 它标准支持等功能。如图2 2 所示： 图2 2v x w o r k s 实时操作系统结构示意图 目前v x w o r k s 操作系统的舨本为v x w o r k s5 4 ，其核心功能主要有： ( 1 ) 微内核w i n d ( 2 ) 可裁剪的运行软件 这些核心功能可以与w i n d r i v e r 系统的其它附件和t o r n a d o 合作伙伴的产品结合在一 起使用。下面具体说明这两个核心功能： ( 1 ) 微内核设计 内核仅包含一个操作系统执行的最重要的底层功能。正象一个统一结构的操作系统， 内核提供了在高层软件与下层硬件之间的抽象层。然而，内核仅提供了构造操作系统其它 部分所需的最小操作集。 处于v x w o r k s 实时操作系统核心的是高性能的微内核w i n d 。这个微内核支持所有的实 时特征：快速任务切换、中断支持、抢占式和时间片轮转调度等。微内核设计减少了系统 开销，从而保证了对外部事件的快速、确定的反应。 w i n d 还提供了有效的任务间通信机制，允许独立的任务在实时系统中与其行为相协 调。开发者在开发应用程序时可以使用多种方法：用于简单数据共享的共享内存，用于单 c p u 的多任务间信息交换的消息队列和管道、套接字，用于网络通信的远程过程调用以及 用于处理异常事件的信号等。 ( 2 ) 可裁剪的运行软件 第7 页 国防科学技术大学研究生院学位论文 v x w o r k s 之所以设计为具有可裁剪性，是为了使开发者能够根据自己的应用程序需要， 而不是根据操作系统的需要，来分配稀少的内存资源。从需要几个k b 字节内存的深层嵌 入式设计到需要更多的操作系统的功能的复杂的高端的实时系统，开发者也许需要从1 0 0 多个不同的选项中进行选择以产生上百种的配置方式。许多独立的模块都是在开发时要使 用而在产品中却不再使用。 而且，这些子系统本身也是可裁剪的，这样就允许开发者为最广泛的应用程序进行更 为优化的v x w o r k s 运行环境配置。例如，如果应用程序不需要某些功能模块，就可以将它 移出a n s ic 运行库：如果应用程序不需要某些特定的内核同步对象，这些对象也可以忽 略。另外，也可以根据需要将t c p 、u d p 、套接字和标准b e r k e l e y 服务移出或移入网络协 议栈。 这些配置选项可以通过t o r n a d oi i 的项目工具图形接口轻易的选择。开发者也可以 使用t o r n a d oi i 的自动裁剪特性，自动地分析应用程序代码并合并合适的选项。 2 3 4 基本构成 v x w o r k s 操作系统的基本构成部件参见图2 3 ，主要有以下五个部分构成 1 ，板级支持包b s p ( b o a r ds u p p o r tp a c k a g e ) 2 微内核w i n d 3 网络系统 4 文件系统 5 i o 系统 图2 3v x w o r k s 操作系统的基本构成部件示意图 第8 页 国防科学技术大学研究生院学位论文 v x w o r k s 操作系统包括了板级支持包b s p ( b o a r ds u p p o r tp a c k a g e ) 、进程管理、存 储管理、设备管理、文件系统管理、网络挤议及系统应用等几个部分。v x w o r k s 只占用了 很小的存储空间，并可高度裁减，保证了系统能以较高的效率运行。 下面分别说明各个组件的具体职能： i 板级支持包b s p ( b o a r ds u p p o r tp a c k a g e ) 板级支持包为各种板子的硬件功能提供了统一的软件接口，它包括硬件初始化、中断 的产生和处理、硬件时钟和计时器管理、内存地址映射和内存分配等等。每个板级支持包 包括一个r o m 启动( b o o tr o m ) 或其它启动机制。 2 高性能的实时操作系统核心w i n d ( 1 ) v x w o r k s 的核心被称为w i n d ，包括多任务调度( 采用优先级抢占方式) ，任务 间的同步和进程间通信机制，中断处理，看门狗和内存管理机制。一个多任务环境允许实 时应用程序以一套独立任务的方式构筑，每个任务拥有独立的执行线程和它自己的一套系 统资源。通信机制使得这些任务的行为能够同步、协调。 ( 2 ) w i n d 使用中断驱动和优先级的方式。它缩短了上下文切换的时间开销和中断的 时延。在v x w o r k s 中，任何线程都可以被启动为一个单独的任务，拥有它自己的上下文 和堆栈。还有一些其它的任务机制可以使任务挂起、继续、删除、延时或改变优先级。 ( 3 ) w i n d 提供信号量作为任务问同步和互斥的机制。在w i n d 核中有几种类型的信 号量：二进制信号量、计数信号量、互斥信号量和p o s i x 信号量，它们分别针对不同的 应用需求。所有的这些信号量都是快速和高效的，它们除了被应用在开发设计过程中外， 还被广泛地应用在v x w o r k s 高层应用系统中。对于进程间通信，w i n d 核也提供了诸如消 息队列、管道、套接字和信号等机制。 3 网络设旖 v x w o r k s 提供了对其它网络和t c p i p 网络系统的“透明”访问，包括与b s d 套接字 兼容的编程接口，远程过程调用( r p c ) ，s n m p ( 可选项) ，远程文件访问( 包括客户端 和服务端的n f s 机制以及使用r s h ，f t p 或t f t p 的非n f s 机制) 以及b o o t p 和a r p 代理。 无论是松耦合的串行线路、标准的以太网连接还是紧耦合的利用共享内存的背板总线，所 有的v x w o r k s 网络机制都遵循标准的i n t e r n e t 协议。 4 文件系统 v x w o r k s 提供的快速文件系统适合于实时系统应用。它包括几种支持使用块设备( 如 磁盘) 的本地文件系统。这些设备都使用一个标准的接口使文件系统能够灵活地在设备驱 动程序上移植。 v x w o r k s 也支持s c s i 磁带设备的本地文件系统。v x w o r k si 0 体系结构甚至还支持 在一个单独的v x w o r k s 系统上同时并存几个不同的文件系统。 v x w o r k s 支持四种文件系统：d o s f s 、r t l i f s 、r a w f s 和t a p e f s 。 另一方面，普通数据文件和外部设备都被作为文件进行统一处理。它们在用户面前有 相同的语法定义，使用相同的保护机制。这样既简化了系统设计又便于用户使用。 5 i o 系统 v x w o r k s 提供了一个快速灵活的与a n s ic 兼容的i 0 系统，包括u n i x 标准的缓冲 第9 页 国防科学技术大学研究生院学位论文 i o 和p o s i x 标准的异步i o 。 v x w o r k s 包括以下驱动程序：网络驱动、管道驱动、r a m 盘驱动、s c s i 驱动、键盘驱 动、显示驱动、磁盘驱动和并口驱动。 2 4 本章小结 i s i s 协议运行在o s i 协议栈的第三层和t c p i p 协议栈的i p 之上。通过本章对o s l 参考模型以及t c p i p 协议栈基本知识的介绍可以更加具体、直观的了解i s i s 的工作环 境和主要职能。 本章的第二部分介绍了路由器软件的开发工具t o r n a d o 。它在v x w o r k s 实时操作系统 的支持下成为一种公认的强大的开发平台。使用该平台为i s i s 及其它路由软件的顺利开 发提供了重要的条件。 下一章将会详细给出i s i s 协议中路由表的组织和路由计算的设计与实现过程。 第1 0 页 国防科学技术大学研究生院学位论文 第三章i s i s 协议路由计算的设计与实现 路由选择协议的本质就是收集网络中的路由选择信息并选择到所有已知目的网段的 最佳路径。这些功能由i s i s 协议体系中的路由更新进程和路径决策进程来执行。路由更 新进程负责i s i s 数据库的建立并确保数据库的完整性。路径决策进程根据链路状态数据 库信息，使用s p f 算法计算到所有已知目的网段的最佳路径。s p f 算法通过计算一个区域 内特定节点到其余节点的最短路径树，从而得出从这一特定节点到每一个目的网段的最佳 路由。 3 1s p f 算法概述 s p f 算法0 1 是路由选择协议决定最佳路径所使用的两种流行的算法之一，另一种是广 泛用于距离矢量路由选择协议的b e l l m a n f o r d 算法。b e l l m a n f o r d 算法和s p f 算法的区 别在于，b e l i m a n - f o r d 算法中每一个节点基于直连邻居的开销再加上邻居通告的其它路由 的