（计算机科学与技术专业论文）ripng协议互操作性测试中控制与观察性的研究.pdf

0 i i i l i l liiu l l1 1 11 1u l liiil y 17 3 6 2 7 6 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成 果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得凼蒙直太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名毯醯 指导教师签名 日期：礁! q ：61f 墨日期： 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，l i p ：内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允 许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权，作者在学期间取得的研究成果( 含计算机软件、程序) 属于 内蒙古大学计算机学院。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内 蒙古大学计算机学院就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大 学计算机学院方可投稿或公开发表。 学位论文作善签名镒赴名导教师躲 日 期：2 堂i 望：f 乡 日期： 。 l ) 一田o z，2 i ， ，f， 一 内蒙古大学硕士学位论文 r i p n g 协议互操作性测试中控制与观察性的研究 摘要 r i p 协议是基于距离向量的路由协议，由于其操作简便，系统资源消耗小，适合应用于 小型网络。r i p n g 是基于i p v 6 的r i p 路由协议。为了保证网络中运行r i p n g 的路由器能够正 确互联互通互操作，需要对r i p n g 协议进行互操作性测试。在协议互操作性测试过程中，如 果能够实现控制和观察被测系统中的一个i u t ，将会更有助于对互操作测试的研究。本文利 用路由软件z e b r a 对r i p n g 协议互操作测试中的控制和观察问题进行了如下研究： 首先，分析了测试中关于控制和观察问题的研究现状，提出了协议互操作测试中控制和 观察问题的定义，在单边互操作测试环境中研究了带有控制和观察点的互操作测试架构。 其次，根据r i p n g 的r f c 文档，给出了r i p n g 的有限状态机( f s m ) 模型，采用可达图对 两个f s m 的互操作模型进行了描述。根据协议的实际运行情况，将可达图进行了化简。给出 了基于简化可达图的测试序列的生成方法，使用该方法基于简化的可达图生成了测试序列，介 绍了r i p n g 控制和观察点的布置实现。 接着，介绍了开源路由软件z e b r a 及其软件结构和功能，描述了采用z e b r a 作为研究对 象的原因，举例介绍了z e b r a 的工作过程。设计编写了测试例，实现了在z e b r a 中插入控制 和观察的代码，编写了r i p n g 路由信息发送工具，进行了可以实现对r i p n g 控制和观察的互 操作性测试。 最后，本文给出了下一步的工作。根据现有的工作，对互操作性测试中的控制和观察问 题进行更一般化的形式化研究，对r i p n g 互操作中的控制和观察问题进行更加详细的研究。 关键词：协议互操作测试，r i p n g ，有限状态机，z e b r a ，控制与观察 r i p n g 协议互操作性测试中控制与观察性的研究 r e s e a r c ho nc o n t r o l l i n ga n do b s e r 、7 ：a t i o no f i n t e r o p e r a b i l i t yt e s t i n go f r i p n gp r o t o c o l a b s t r a c t i u p p r o t o c o li sr o u t i n gp r o t o c o lw h i c hi sb a s e do nd i s t a n c ev e c t o r i ti ss u i t a b l e f o rs m a l ln e t w o r k sb e c a u s eo fi t ss i m p l ea n dc o n s u m i n gal i t t l e s y s t e mr e s o u r c e s r i p n gi sar o u t i n gp r o t o c o lb a s e do ni p v 6 r i p n gi sn e e d e di n t e r o p e r a b i l i t yt e s t i n gi n o r d e rt oe n s u r et h ec o r r e c tc o n n e c t i o na n di n t e r o p e r a b i l i t y t h ei m p l e m e n t a t i o no f c o n t r o l l i n ga n do b s e r v a t i o ni no n eo f t h ei u t so fi n t e r o p e r a b i l i t yt e s t i n gs y s t e mw i l l b eu s e f u lf o rt h er e s e a r c ho ft h ei n t e r o p e r a b i l i t yt e s t i n g t h i st h e s i st a k e sar e s e a r c h o nt h ec o n t r o l l i n ga n dt h eo b s e r v a t i o no fi n t e r o p e r a b i l i t yt e s t i n gw i t har o u t i n g s o t t w a r ec a l l e dz e b r a f i r s t l y , t h es i t u a t i o no ft h ec o n t r o l l b i l i t ya n dt h eo b s e r v a b i l i t yp r o b l e mi nt e s t i n g i si n t r o d u c e d t h ed e f i n i t i o no ft h ec o n t r o l l i n ga n dt h eo b s e r v a t i o ni np r o t o c o l i n t e r o p e r a b i l i t yt e s t i n gi sp r e s e n ta n dt h ea r c h i t e c t u r eo fi n t e r o p e r a b i l i t yt e s t i n gw i t h t h ep c op o i n t si nt h es i t u a t i o no fu n i l a t e r a lp r o t o c o l i n t e r o p e r a b i l i t yt e s t i n gi s a n a l y z e d s e c o n d l y , t h ef i n i t e s t a t em a c h i n e ( f s m ) o fr i p n ga c c o r d i n gt ot h er f c d o c u m e n ti s p r e s e n t e d 1 1 1 er e a c h a b i l i t yg r a p h i s a d o p t e d t od e s c r i b et h e i n t e r o p e r a b i l i t ym o d e lo ft h et w of s m s t h er e a c h a b i l i t yg r a p hi sr e d u c t e da c c o r d i n g t ot h er e a le x e c u t i o n at e s ts e q u e n c eg e n e r a t i o nm e t h o db a s e do nt h er e d u c t e d r e a c h a b i l i t yg r a p hi sg i v e n t h es e t t i n go f t h ep c o p o i n t si si m p l e m e n t e di nr i p n g f u r t h e r m o r et h ea r c h i t e c t u r ea n dt h ef u n c t i o n so fz e b r aa r ed e s c r i b e d t h e r e a s o n st h a tu s i n gz e b r aa r ee x p l a i n e d 1 1 1 ew o r k i n gp r o c e s so fz e b r ai si n t r o d u c e d b ya ne x a m p l e z e b r ac o d ei se x t e n d e dt os u p p o r tr e q u i r e dr i p n gc o n t r o l l i n ga n d o b s e r v a t i o na n dar i p n gp a c k e t ss e n d e ri si m p l e m e n t e d t h er i p n gi n t e r o p e r a b i l i t y t e s t i n gi st a k e n w i t ht h ee x t e n d e dz e b r aa n dt h es e n d e rt 0 0 1 f i n a l l y , t h i st h e s i sp r e s e n t st h ew o r ki nt h ef u t u r e t h em o r eg e n e r a lf o r m a l t t 内蒙古大学硕十学位论文 m e t h o do nt h ec o n t r o l l i n ga n dt h eo b s e r v a t i o no f t h ei n t e r o p e r a b i l i t yt e s t i n gi sw o r t h o fm o r ed e e pr e s e a r c h t h ec o n t r o l l i n ga n dt h eo b s e r v a t i o no f r i p n gi n t e r o p e r a b i l i t y t e s t i n gn e e dam o r ed e t a i ls t u d y k e y w o r d s ：i n t e r o p e r a b i l i t yt e s t i n g ，r i p n g ，f i n i t es t a t em a c h i n e ，z e b r a ， c o n t r o l l i n ga n d o b s e r v a t i o n 1 i i r i p n g 协议互操作性测试中控制与观察性的研究 目录 r i p n g 协议互操作性测试中控制与观察性的研究i 摘要i r e s e a r c ho nc o n t r o l l i n ga n do b s e r 、，a t i o no fi n t e r o p e r a b i l i t y t e s t i n go fr i p n gp r o t o c o l i i a b s t r a c t i i 目录 图e jj 录v i i 表e j ；灵v i i i 第一章绪论1 1 1 协议测试介绍1 1 2 协议互操作性测试介绍1 1 3 测试中的控制和观察问题的研究现状3 1 4r i p n g 协议测试的研究现状6 1 5 本文的研究工作6 1 6 文章结构划分7 第二章协议互操作性测试理论模型。8 2 1 互操作性测试的架构8 2 2 单边互操作性测试的结构9 2 3 协议互操作性测试中控制和观察问题9 2 4 有限状态机o 1 0 2 5 组合的有限状态机实例模型和可达图。1 1 2 6 可达图中控制和观察点的实现1 4 第三章r i p n g 协议概述1 6 3 1r i p 协议介绍_ 1 6 3 2r i p 协议消息结构16 3 2 1r i p v l 消息结构1 6 3 2 2 砌p v 2 消息结构17 i v 内蒙古大学硕+ 学位论文 3 3r i p n g 协议介绍18 3 4r i p n g 工作原理2 0 3 4 1r i p n g 的消息类型2 0 3 4 2r i p n g 的工作过程2 l 第四章r i p n g 互操作性测试的控制与观察模型2 4 4 1r i p n g 互操作性测试的控制与观察架构2 4 4 2r i p n g 的协议模型2 4 4 3r i p n g 互操作模型可达图2 7 4 4 测试生成2 8 4 5r i p n g 测试中控制和观察点的实现3 0 第五章实验部分3 5 5 1z e b r a 介绍3 5 5 1 1z e b r a 功能3 5 5 1 2z e b r a 架构3 5 5 2 选择z e b r a 的原因3 6 5 3z e b r a 中r i p n g 协议实现分析3 7 5 3 1 几个重要的数据结构3 7 5 3 2r i p n g 连接端口3 8 5 3 3r i p n g 认证3 8 5 3 4r i p n g 路由更新3 8 5 4 发送r i p n g 路由数据包工具的实现4 0 5 5z e b r a 的测试执行4 1 5 5 1z e b r a 中控制点的实现举例。4 l 5 5 2z e b r a 中观察点的实现举例4 2 5 6 测试总结。4 5 第六章工作总结和下一步的工作4 6 6 1 本文的工作总结4 6 6 2 下一步的工作4 6 参考文献4 8 附录l ：两个r i p n g f s m 模型的完整可达图5 1 v r i p n g 协议互操作性测试中控制与观察性的研究 附录2 ：简化后的可达图5 2 至炙谢5 3 攻读硕士期间发表的学术论文5 4 参加项目5 5 内蒙古大学硕+ 学位论文 图目录 图1 1 分布式测试系统中的观察序列问题4 图2 1 通用的互操作性测试结构图8 图2 2 单边互操作性测试结构9 图2 3 两个有限状态机组成的系统1 1 图2 4 输出序列图1 2 图2 5 两个有限状态机1 3 图2 6 合成f s m 的可达图1 4 图3 1r i p v l 消息结构1 7 图3 2 鼬p v 2 的消息结构1 8 图3 3r i p n g 的消息格式1 9 图3 4r t e 消息格式19 图4 1 带有控制和观察点的互操作架构2 4 图4 2r i p n g 的有限状态机2 6 图4 3 组合有限状态机部分可达图2 7 图4 4 内部状态转化中控制和观察点的设置3 0 图4 5 设置p c o 观察内部输出3 0 图4 6 控制和观察点布置流程图3 l 图4 7 实现控制和观察点代码流程图3 2 图5 1z e b r a 系统架构3 6 图5 2r i p n g 路由更新流程3 8 图5 3 数据包发送工具结构4 1 图5 4 测试结果4 2 v i l r i p n g 协议互操作性测试中控制与观察性的研究 表目录 表3 1r i p n g 与r i p v l 和r i p v 2 的不同之处2 0 表4 1 状态描述2 4 表4 2r i p n g 的变迁2 5 表4 3r i p n g 的状态变迁转化表2 5 表4 4 变迁对应关系表2 7 表4 5 测试例描述。2 9 表4 6 测试例示例3 2 表5 1 进程协议对照表3 5 表5 2r i p n g 测试结果。4 1 表5 3 测试例3 4 2 v i i i 内蒙古人学硕十学位论文 1 1 协议测试介绍 第一章绪论弟一早珀了匕 协议是通信双方关于如何进行通信的约定规则。通信双方只有实现相同的协议，才可以 正确有效的进行信息的传输。为了确定协议的实现是否正确，需要人们对协议进行测试。协 议测试技术是保证网络通信协议正确实现以及不同的网络设备之间正确互连的重要手段。研 究协议测试是由于一个标准化的r f c 协议文档都是由自然语言描述的，我们不能保证一个协 议的实现是完全j 下确的，也不能保证同一协议的不同实现之间能够完全成功地进行通信。因 为自然语言的描述不但难以保证其完备性，有时甚至还存在二义性，实现者对于同一协议的 不同理解会产生不同的实现，有的实现有时甚至是错误的，因此需要对协议进行测试。协议 测试是在软件测试的基础上发展而来的，因为一个协议实现本身就是一个软件。在软件测试 中，通常分为白盒测试和黑盒测试。白盒测试是对软件内部结构逐条语句进行测试，黑盒测 试是通过外部环境对系统进行输入，观察系统的输出，以此来判定系统的实现是否达到预期 的效果。协议测试是一种黑盒测试，协议测试是协议工程过程中的一个重要的步骤。协议测试 包括一致性测试、性能测试、互操作性测试和坚固性测试 1 。一致性测试是测试协议的实现 与协议的说明文档是否一致；互操作测试是测试同一协议说明文档的不同实现间的互连和互 操作的能力；性能测试是测试协议实现的性能参数；坚固性测试是测试协议在各种环境下运 行的能力，如信道被切断，断电等情况。一致性测试是最基本的协议测试方法，其目标是检 测协议实现是否与协议规范相一致。作为一致性测试的补充，互操作性测试的主要目标是测试 两个或更多的协议实现在网络操作环境中是否能够正确地交互，从而完成协议说明文档中规 定的功能，它对于通信产品的质量保证有着重要的现实意义。 1 2 协议互操作性测试介绍 互操作性测试是在一致性测试的基础上发展而来的，互操作性测试的研究工作可以大致 分成两类，第一类是对互操作性测试一般概念的研究和互操作性测试的实验，第二类是系统化 的互操作性测试序列生成。 互操作性测试作为一致性测试的后继步骤，其采用的很多方法都沿用于一致性测试，但由 l r i p n g 协议互操作性测试中控制与观察性的研究 于互操作性本身的特点，一致性测试的方法并不能直接在互操作性测试中套用。其一，在进行 一致性测试时，通常把被测体( i u t ) 放置在一个“孤岛”环境，由测试体( t e s t e r ) 模拟与其通 信的所有其他实体，而在互操作性测试中，为了测试两个或多个i u t s 的交互行为，i u t s 通常 放置在一个开放环境中测试，对于观察控制i u t 间的交互是互操作测试中的问题，因此需要有 新的测试方法和测试框架结构去满足。其二，互操作系统的形式化描述不能直接来自于协议规 范，必须先对通信双方分别进行形式化描述之后通过可达性分析等技术获取整个系统行为的 形式化描述。其三，互操作性测试至少涉及两个通信实体。 关于协议互操作性测试的理论研究和实际测试，国内外的许多科研组织和团体都做了大 量的工作。在理论研究方面，人们做出了很多成果，发表了很多文章。文章 2 较早地对互操 作性测试的各个方面进行了全面的探讨，关于对互操作性测试序列生成的研究是由文章 3 最早提出来的，文章采用一致性测试序列的生成方法生成互操作测试序列，将一致性测试技 术应用于互操作性测试中。此后人们对互操作性测试方法的研究做了很多工作。文章 4 提出 了基于有向图的最小完全覆盖互操作性测试序列生成算法，提出了最小完全覆盖准则，具体 方法为：对于两个测试序列，如果只是本地转化不同，所包含的互操作性转化是相同的，那 么这两个测试序列对于互操作性测试来说是等价的。文章 5 提出了基于多通信端口的模型， 被测系统包含两个以上的协议实现，其中每个组件包括多个端口，更适合实际情况，并且考 虑了状态爆炸问题，最后给出了基于单激励的生成算法，且添加了末状态验证序列，用来检 测变迁错误。文章 6 系统地研究了互操作性测试理论和方法。文中研究了基于有限状态机的 互操作性测试常用测试序列的生成方法，研究了有限状态机的错误模型和测试覆盖，给出了 基于贪心算法的次优互操作序列生成方法，研究了单边互操作性的测试方法和动态测试方法。 在实际测试中，n e wh a m p s h i r e 大学的互操作实验室i o l ( i n t e r o p e r a b i l i t yl a b ) 在协议互 操作性测试方面也做了大量的工作，目前他们对i p v 6 的测试包括测试i p v 6 的基本协议部分 以及i p v 6 的相关协议，并免费提供部分相关测试套 7 ，在支持i p v 6 的路由协议测试方面包 括b g p 4 + 、o s p f v 3 、r i p n g 的部分互操作性测试套。日本的t a h i 项目研究和开发了i p v 6 协议 的互操作性测试系统，他们在i p v 6 方面做了大量的工作，并且在官方网站上 8 公布了部分 测试套，而且也公布了最新的研究进程。e t s i 组织也对i p v 6 协议展开了大量的工作，该组 织成员来自5 5 个国家，并且与许多科研组织和相关工业组织合作，通过使用t t c n 一3 来进行 一致性测试。在国内，清华大学的计算机网络技术研究所在网络协议方面做了大量的研究实 践工作，完成了多项目国家级项目，发表相关论文多篇；中国科技大学也在协议的互操作性 测试方面作了很多工作。 2 内蒙古大学硕士学位论文 1 3 测试中的控制和观察问题的研究现状 在测试中，观察和控制问题一直是不可回避的问题，目前多数相关的研究工作都是在一 致性测试环境中讨论的。文章 9 较早提出了关于测试的可观察问题，在软件系统的一致性测 试中，经常会使用多个独立的测试器，每个测试器都会发送输入测试消息，并且也接收输出 的测试消息，当所有的观察者都观察到正确的消息时，最后的测试结果可能是j 下确的，但也 有可能是错误的，这种错误是由同时使用多个测试器引起的。该文章基于有限状态机( f s m ) 对于这种由于使用多个测试器而引起的错误进行了研究，定义了三种会导致观察错误的f s m 的错误实现，问题的解决方法是逐个输入单个的测试序列，如果结果正确，则输入下一个测 试序列，依次类推，最后将结果正确的测试序列连接起来，形成完整的测试序列。 人们对于分布式软件的一致性测试做了很多研究工作，在研究分布式测试系统时，可控 制和观察问题也是一直备受关注的问题。文章 1 0 研究了在测试分布式产品时采用远程测试 方法存在着的可控制和可观察问题。在远程测试中，每个测试器都是通过一个端口和被测系 统( i u t ) 进行连接和信息交互，这种测试中主要的问题是不能控制i u t ，如当i u t 同时从两 个端口得到消息时，不能确定先处理哪一个端口的消息。文章分析了当前人们对于该问题的 研究，指出了其中的不足，并针对这些不足提出了在分布式系统中通过使用协同信息来解决 测试中的控制和观察问题，给出了相关的算法，并对算法进行了理论证明。在该文章中虽然 分析了分布式测试中的可观察和可控制问题，并提出了自己的见解，但没有明确给出可观察 问题，可控制问题的概念。 文章 1 1 研究了分布式系统测试的可观察性问题，文中指出当观察者只能看到分布式系 统的消息序列时，会出现下列情形的观察性问题： 1 ) 当有多个观察器时，同一时间到达序列对于不同的测试器可能会观察不同的到达顺 序，如图1 1 ( a ) 中，0 和r 分别为两个观察器，对于事件b 和c ，由于传输的延迟，观察器o 观察到事件b 先于事件c 发生，而观察器r 观察到事件c 先于事件b 发生。这就会影响到测 试结果。 2 ) 由于时延问题，观察者观察到的序列可能不是正确的输出序列。如图1 1 ( b ) 所示， 由于a 的输出产生了时延，观察器r 会错误地认为事件c 先于事件a 发生。 3 ) 同一行为由于发生的时间不同，引发不同的输出序列。如图1 1 ( c ) 所示，p 和q 以 同样的方式运行两次，第一次运行时观察器0 看到事件c 先于事件b 运行，第二次运行时观 察器0 看到的顺序却是b 先于c 运行。 r l p n g 协议互操作性测试中控制与观察性的研究 p q ( a ) 卜一 i 一” ： l ： l ： l t)p q p q * i ： 卜一、 卜。 i ： i ： i i ： d ， ， ， ， ，。， ， ， ， ， c ， q ( c ) 图1 1 分布式测试系统中的观察序列问题 f i g u r e1 1p r o b l e mo fo b s e r v i n gs e q u e n c e si nd i s t r i b u t i n gs y s t e m 由于上述问题的存在，可能会出现错误的测试结果。对于该问题的解决文章采用时间戳 机制进行解决，文中共提出了四种时间戳方法。 ( 1 ) 本地实时时钟。将硬件时间作为时间戳的源。存在时间不同步问题。 ( 2 ) 全局实时时钟。在分布式系统中时钟都是同步的。实际很难实现。 ( 3 ) 采用逻辑时钟。每个处理器都有一个计数器。存在问题：如果两个测试器的某个测 试信息的计数器的值相等，二者的顺序问题难分先后。 ( 4 ) 部分逻辑时钟。每个处理器通过一个数组进行计数，由于数组的每一位对应于一个 测试器的测试信息计数器，因此该方法可以极大地缓解上述( 3 ) 中存在地问题。 在分布式测试中由于消息序列的到达顺序会影响到测试的结果，因此人们对于消息序列 的可控制和可观察问题也进行了很多研究。文章 1 2 对远程互操作测试中由于消息到达的时 序问题而引起测试结果的误差进行了研究，采用逻辑时钟解决对消息序列的可控制与可观察 问题。文章 1 3 提出了在分布式测试系统中使用协同信息时，会由于协同信息的时延而影响 到测试结果。文章对该问题的解决方法是不使用协同信息，而是通过在有限状态机( f s m ) 中 4 雹。!ii：露 ， ， 。l_ll!l露 ， ， ， ， p ， ， ， _ jr i ， l _ h 。，n。，。d 内蒙古大学硕士学位论文 加入限制条件，解决测试中存在的控制和观察问题。 文章 1 4 对通信软件的分布式测试系统进行了研究。在分布式测试中，如果某个测试器 没有发送上一个输入或者在上一个变迁中没有收到i u t 的输出，那么该测试器将无法确定何 时向i u t 发送下一个输入，此时会发生可控性( 同步) 问题。文章采用多端口有限状态机( n p o r t f i n i t es t a t em a c h i n e ，n p f s m ) 模型进行研究。关于可观察问题，文章指出与i i j t 中的输出移位错误有关，即输入和输出不能对应。文章分别采用不使用外部协同信息和使用 外部协同信息来解决可控制和可观察问题。 文章 1 4 中提出的关于输入和输出对应关系及输出移位的问题，也有不少研究人员做了 专门的研究。文章 1 5 采用图论的方法对输入输出问题进行了分析研究。对于一个给定的说 明( s e p e c i f i c a t i o n ) ，文章采用一个规则集将说明生成一个辅助的有向图，然后采用一种合 适的方法对有向图进行遍历，这样可以避免由于控制和观察而引出的输入输出是否对应的问 题。文章 1 6 研究了在异步分布式系统中因果事件的顺序出现顺序错乱的问题，文中采用矢 量时钟方法进行控制解决事件的因果联系。文章 1 7 描述了当一个系统含有多个测试端口时， 采用同步测试序列进行测试时会出现输出漂移问题，当用多端口有限状态机描述系统时，可 以将其转化为有向图，采用一种叫作p 一同步的方法对有向图进行遍历，解决输出漂移问题。 关于测试中的可控制性和可观察性问题，人们一直在研究，上述文献中都是给出了测试 中控制和观察的具体问题描述，没有明确给出具体的概念。 文章 1 8 给出了在一致性测试中可控制性和可观察性的概念。 可控制性：测试系统( t e s ts y s t e m ，t s ) 可以强制i u t 按顺序接受输入序列的能力，例如 给定一个一致性测试序列，其中x ，和x 都是i u t 的输入，正常顺序应为i u t 先得到x ，然后 得到x i + l ，若i u t 不能保证先得n x ，然后得至1 x i + l ( i t ) 时，就会出现控制问题。 可观察性：可观察性指的是测试系统( t s ) 能够观察到i u t 的输出，并且可以确定该输 出对应的是哪个输入。给定一个一致性测试序列旯= ( x 。) ( x ：r 2 ) ( x j r , ) ，可控制问题是当 测试系统t s 收到a ，：，不能确定a 是否是i u t 在得到x i 之后且在收到h 。前发出的。 文中指出在一致性测试中，如果i u t 能够得到期望的序列并且所有的输出错误都能够被 t s 监测到，就可以解决控制和观察问题。文章使用的方法是对测试系统t s 的反应时间 r t ( r e a c t i n gt i m e ) 和等待时间w t ( w a i t i n gt i m e ) 进行限制，解决了可控制和可观察问题。 关于协议测试中的可控制与可观察问题，人们也进行了一些研究 1 9 2 0 。 文章 1 9 研究了在协议测试中控制和观察性问题。在协议测试中，由于测试序列发送的 r i p n g 协议互操作性测试中控制与观察性的研究 顺序问题，会引起测试中的控制和观察问题，最后将会影响到协议测试的结果。文章提出的 方法是对于一个给定的协议，构建一个协议模型图，采用中国邮递员算法和通过加入协同消 息的方法来解决协议测试中控制和观察的问题。 文章 2 0 提出了互操作测试中的控制和观察问题。文章根据现有的一致性测试的概念提 出了互操作测试的形式化方法。文中详细列出了各种互操作测试的框架与场景，包括单边互 操作测试架构，双边互操作测试框架，全局互操作测试架构，层次互操作测试架构( 不是严 格满足前面三种测试架构的，都称为层次互操作测试架构) ，并给出了互操作测试的方法。对 于单边互操作性测试架构，只有两个i u t ，控制和观察点放置在其中一个i u t 即可；对于双边 互操作测试架构，每一个测试器都应该设置控制和观察点；对于全局互操作测试架构，控制 和观察点应设为全局监控。这对于研究互操作测试可控制性与可观察性问题提供了理论依据。 1 4r i p n g 协议测试的研究现状 r i p 协议属三大路由协议之一，发展历史悠久，协议简单易操作，适合使用于小型网络。 r i p 分为i p v 4 版本的协议r i p v l 、r i p v 2 和i p v 6 版本的协议r i p n g 。r i p v 2 现已广泛使用， 随着下一代网络技术的研究和发展，i p v 6 地址的广泛使用是必然的趋势，r i p n g 作为基于i p v 6 的r i p 协议，在小型i p v 6 网络也必然会得到广泛的使用。r i p n g 能否正确运行，不同的r i p n g 实现间能否正确进行互操作，对r i p n g 网络的正确运行至关重要，因此研究r i p n g 协议的测 试无论是从理论而言，还是从实际而言，都是很有现实意义的。 关于r i p n g 协议的测试，目前人们也做了很多工作，包括r i p n g 的一致性测试 2 卜2 3 和 互操作测试。文章 2 1 采用适合r i p n g 的多端口测试结构，设计了r i p n g 一致性测试集， 并在实际网络中对r i p n g 进行了测试。文章 2 2 也对r i p n g 的一致性测试进行了研究。文中 对现有的测试方法t 方法，d 方法，u i o 方法和w 方法进行了描述和比较，并针对d 方法的不 足，提出了一种o s d ( o u t p u ts e q u e n c eb a s e ddm e t h o d ) 测试序列生成方法，并进行了r i p n g 的一致性测试。文章 2 3 采用t t c n 一3 对r i p n g 进行t n 试研究，使用t t c n 一3 开发了r i p n g 的一致性测试套，并进行了实验。关于r i p n g 的互操作测试n e wh a m p s h i r e 大学的互操作实 验实i o l ( i n t e r o p e r a b i l i t yl a b ) 7 做了很多工作，免费提供了r i p n g 的互操作性测试套。 1 5 本文的研究工作 人们对于测试中控制和观察性的研究，基本都是在一致性测试中研究的，且都是在分布 6 内蒙古火学硕十学位论文 式系统中进行的，采用的方法也基本都是基于有限状态机进行的，在互操作性测试中关于控 制和观察性的研究还比较少，关于在互操作测试中设置内部控制和观察点的研究就更少了， 而这项工作在互操作测试中是很有意义的。以往的互操作测试工作，通过测试结果只能观察 到两个或多个被测间能否正常互操作，而对于不能实现互操作或者不是按照预期的设想进行 互操作的实体不能确定其原因。通过在内部设置观察控制点，我们可能会明确地观察到不能 互操作或不按预期设想互操作的原因，这对于研究工作有着重大的现实意义。 为此，本文在单边互操作环境中对r i p n g 协议的互操作中存在的控制和观察问题进行了 研究，所谓的单边互操作环境，即在测试系统中只对一个测试实体进行研究。本文对于r i p n g 协议互操作测试中控制和观察问题的研究主要分为以下几项工作： ( 1 ) 研读现阶段关于测试中控制和观察问题的文献，熟悉测试中控制和观察问题的研究 现状。根据自己的研究需要，给出控制和观察问题的形式化定义。 ( 2 ) 研究r i p n g 路由协议，对该协议进行形式化描述，构造协议的互操作模型。探讨r i p n g 的互操作测试中的控制和观察性问题。 ( 3 ) 在开源路由软件z e b r a 中添加可以实现控制和观察r i p n g 运行情况的代码，扩展 z e b r a 中r i p n g 部分的功能，实现对r i p n g 互操作性测试的控制和观察。 ( 4 ) 在l i n u x 中编程实现r i p n g 路由数据包工具，实现路由数据包的发送，进行r i p n g 互操作性测试中控制和观察问题的研究。 1 6 文章结构划分 本文主要分为以下几个部分：第二章介绍协议互操作理论基础；第三章介绍r i p n g 协议 及其工作原理；第四章研究带有控制点和观察点的互操作测试模型，将r i p n g 协议进行形式 化描述，给出r i p n g 互操作的模型，给出测试序列的生成方法和测试例，研究r i p n g 中控制 和观察点的实现：第五章是实验部分，介绍路由软件z e b r a ，采用z e b r a 实现r i p n g 互操作 性测试中控制和观察的研究；第六章为工作总结和下一步工作。 7 r i p n g 协议互操作性测试中控制与观察性的研究 第二章协议互操作性测试理论模型 2 1 互操作性测试的架构 在进行互操作性测试过程中，测试的是实体的互操作能力，因此互操作的实体至少要涉 及到两个或多个。通用的互操作性测试的体系结构如图2 1 z o 所示。 ，、 】 一一一1一 。 ii it 个 ii tt 个 u 1 2 uil ii ，办 4 - - 一 一 一4 - - 一 厂、 l t ) + - l t 2 u 】2 卜 一 l - - ( u k