（计算机软件与理论专业论文）边界网关协议bgp4的互操作性测试研究.pdf

内蒙古大学硕十学位论文 边界网关协议b g p 4 + 的互操作性测试研究 摘要 随着互联网的迅速发展，高效稳定的路由协议成为保障网络性能的重要因 素，协议测试理论和测试方法的研究也显得日益重要。协议一致性测试和互操 作性测试是协议实现能够在实际环境中正确互连的重要保障。 我们的工作主要针对互操作性测试展开，包括以下三部分： 第一：针对路由协议的互操作性测试进行理论研究，主要包括：总结互操 作性测试和一致性测试的相互关系，指出对协议实现进行互操作性测试的几点 必要性。运用形式化的方法对被测协议进行建模，采用自动与手动相结合的方 法生成协议的互操作性测试套。 第二：分析b g p 4 + 协议一致性测试和互操作性测试的测试重点，采用形式 化方法对b g p 4 + 协议进行建模，并生成b g p 4 + 互操作性测试套。 第三：针对b g p 4 + 协议进行互操作性测试的实验工作，主要包括：在l i n u x 下用c 语言设计、开发互操作性测试工具，基于s o c k e t 直接发送用于测试的 网络数据包，使该工具能有效的协助互操作性测试的开展。同时对b g p 4 + 协议 的不同实现( 包括路由器c i s c o1 7 2 1 、模拟路由软件z e b r a - 0 9 5 和b i r d - 1 0 1 1 ) 进行了大量的互操作性测试实验，并且给出了测试报告。 关键词路由协议，互操作性测试，b g p 4 + ，x m l ，输入输出有限状态 机 边界嘲关协议b g p 4 + 的且操作性测试研究 i n t e r o p e r a b i l i t yt es t i n g r e s e a r c ho nb o r d e rg a t e w a y p r o t o c o lb g p 4 + a b s t r a c t w i mt h er a p i dd e v e l o p m e n to fn e x tg e n e r a t i o ni n t e r a c t ，t h ee f f i c i e n ta n ds t e a d y r o u t i n gp r o t o c o l sh a v et u r n e do u tt ob eak e yf a c t o rt oe n s u r et h eh i g hp e r f o r m a n c e o fn e t w o r k s ，a n dt h er e s e a r c ho nt h e o r i e sa n dm e t h o d sa b o u tp r o t o c o lt e s t i n g a p p e a r st ob em o r ei m p o r t a n tt h a n b e f o r e b o t ht h ec o n f o r m a n c et e s t i n ga n d i n t e r o p e r a b i l i t yt e s t i n gd e t e r m i n ew h e t h e r a p r o t o c o lw i l lp e r f o r mc o r r e c t l yi na r e a l n e t w o r ke n v i r o n m e n t o u rr e s e a r c hf o c u s e so ni n t e r o p e r a b i l i t yt e s t i n g ，a n dc o n s i s t so ft h ef o l l o w i n g t h r e ep a r t s ： f i r s t l y ，w ed os o m et h e o r e t i cr e s e a r c ho ni n t e r o p e r a b i l i t yt e s t i n go fr o u t i n g p r o t o c o l ，w h i c hm a i n l yi n c l u d e s ：s u m m a r i z i n g t h e r e l a t i o n s h i p b e t w e e n i n t e r o p e r a b i l i t yt e s t i n ga n dc o n f o r m a n c et e s t i n g ；e x p l a i n i n gs e v e r a ln e c e s s i t i e so f i n t e r o p e r a b i l i t yt e s t i n ga b i l i t y o fp r o t o c o l i m p l e m e n t a t i o n ；m o d e l i n gr o u t i n g p r o t o c o lu n d e rt e s tb yaf o r m a lm e t h o d ；g e n e r a t i n gi n t e r o p e r a b i l i t yt e s t s u i t e sb ya m e t h o dc o m b i n i n gm a n u a la n da u t o m a t i cm o d e s s e c o n d l y , w ea n a l y z et h e d i f f e r e n te m p h a s e so nc o n f o r m a n c et e s t i n ga n d i n t e r o p e r a b i l i t yt e s t i n gf o rb g p 4 + ，a n dc o n s t r u c tt h ef o r m a lm o d e la n dg e n e r a t e 内蒙古人学硕士学位论文 i n t e r o p e r a b i l i t yt e s ts u i t e sf o rb g p 4 + t h i r d l y , w ed oal o to fe x p e r i m e n t so ni n t e r o p e r a b i l i t yt e s t i n go fb g p 4 + ，w h i c h m a i n l yi n c l u d e s ：d e s i g n i n ga n dd e v e l o p i n gt o o l ss u p p o r t i n gi n t e r o p e r a b i l i t yt e s t i n g o nl i n u xp l a t f o r mu s i n gc i td i r e c t l ys e n d sn e t w o r kp a c k a g e su s e da st e s t i n gd a t a , w h i c hf a c i l i t a t e st e s tw o r kg r e a t l y m o r e o v e r , w ec a l t yo u tag r e a td e a lo f e x p e r i m e n t so nd i f f e r e n ti m p l e m e n t a t i o n so fb g p 4 + ( s u c ha sc i s c o1 7 2 1r o u t e r , r o u t i n gs o f t w a r ez e b r a - 0 9 5a n d b i r d - 1 0 11 ) ，a n dp r o v i d eaf i n a lt e s t i n gr e p o r t k e y w o r d sr o u t ep 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 g ，b g p 4 + ，x m l ， i n p u ta n do u t p u tf i n i t es t a t em a c h i n e s i i i 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成 果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得凼苤直厶堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名： 日期： 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允 许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后 使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意：若用 于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名： 日期：趁： 指导教师签名： 日期： 内蒙古大学硕上学位论文 引言 协议测试理论和技术在计算机网络的发展过程中起着举足轻重的作用，它是保证网络通 信协议有效地传输信息和网络设备之间正确互连的重要手段。协议测试是对协议实现进行评 价的有效方法，它包括多种类型。其中，一致性测试是基本的协议测试方法，其目标是检测 协议实现与协议规范的符合程度。互操作性测试的主要目的是测试两个或更多的协议实现在 实际的网络环境中是否能够正确的互连互通，从而提供一定的功能。此外，互操作性测试也 被i e t f ( 互联网工程任务组) 和e t s i ( 欧洲测试标准协会) 等国际标准化组织广泛应用到了协 议设计过程中。协议一致性测试和互操作性测试是协议实现能够在实际环境中正确工作的重 要保障。 由于下一代互联网技术的发展，面向i p v 6 的路由协议也得到了不断的完善和应用。在 下一代网络中，广域网的域问路由大多数使用边界网关协议b g p 转发路由信息。b g p 协议 主要位于边界网关上，它是确保自治系统间成功通信的核心协议。作为最基本和最重要的域 间路由协议，测试b g p 4 和b g p 4 + 协议实现的互连互通性具有重要的现实意义。 本文围绕互操作性测试的相关原理对i p v 6 协议族中的b g p 4 + 域间路由协议展开一系列 测试工作，主要包括以下几方面： 1 阅读国内外互操作性测试的相关论文，分析各篇论文的特点，总结了互操作性测试工 作的研究重点。通过比较国内外对互操作性测试的研究现状，指出了对网络协议产品 实现进行互操作性测试的几点必要性，并对互操作性测试和一致性测试的相互关系提 出自己的见解。针对b g p 4 + 域问路由协议，指出在互操作性测试和一致性测试中各自 的测试重点。 2 路由协议互操作性测试的目的是根据被测系统的形式化模型找到尽可能多的被测协议 实体之间的交互行为，并检查被测协议实现能否正确处理所交互的信息。我们使用输 入输出有限状态机( i n p u ta n do u t p u tf i n i t es t a t em a c h i n e s i o f s m ) 对b g p 4 + 协议进行 形式化建模，说明b g p 4 + 协议的状态及其交互行为，把已有的互操作性测试套自动生 成算法应用到b g p 4 + 协议中，自动生成b g p 4 + 测试套，这些测试套主要用来检测被测 协议实现之间的交互行为。同时，通过对协议说明的分析，手动生成一些测试套作为 补充，这些手动生成的测试套用于测试b g p 4 + 协议实现能否对交互信息进行正确处理。 3 在互操作性测试过程中，有时为了测试被测对交互信息的反应，需要向被测实现发送 边界网关协议b g p 4 + 的且操作性测试研究 一些具有特殊要求的数据包，为了满足这个需要，针对b g p 4 + 协议，我们用c 语言自 主开发了一个协助进行互操作性测试的工具，我们称之为互操作性测试工具。该工具 分为数据包编辑模块、执行模块和日志文件三部分。在编辑模块中采用x m l 文件保 存测试套；执行模块中采用s o c k e t 编程实现数据包的发送，并采用多线程技术支持多 个数据包的并发； 同志文件部分主要用来记录互操作性测试的执行过程。 4 基t 自己搭建的测试环境和生成的测试套集，我们针对b g p 4 + 协议的不同实现( 包括 路由器c i s e o l 7 2 1 ，模拟路由软件z e b r a - 0 9 5 和b i r d 1 0 1 1 ) 展开了互操作性测试实验， 并给出了测试结论。 本文共分六章：第一章介绍了路由协议的特点以及b g p 和b g p 4 + 协议概述；第二章介 绍了互操作性测试的相关理论，并分析了互操作性测试与一致性测试的异同；第三章介绍了 互操作性测试生成的形式化技术；第四章对b g p 4 + 协议进行形式化建模，并生成测试套的 集合；第五章介绍了互操作性测试工具的设计和实现，并且给出了b g p 4 + 互操作性测试的 实验举例，列出部分实验结果；第六章是总结和展望。 2 内蒙古人学硕+ 学位论文 1 1 路由协议概述 第一章边界网关协议b g p 概述 协议是计算机网络的灵魂，而路由协议则日益成为i n t e m e t 的灵魂。随着i n t e r a c t 的迅速 发展，网络规模不断扩大，网络结构日趋复杂，高效稳定的路由协议已成为保障网络性能 的重要因素之一，因此路由协议的测试理论和技术已成为计算机网络研究的热点。 协议是通信双方关于如何进行通信的约定规则。通信双方只有实现相同的协议，才可 以正确有效的进行信息的传输。常用的协议包括通信协议和路由协议。其中，t c p l p 图1 - 1 外部网关协议和内部网关协议应用示意图 f i g u r e1 - 1t h es k e t c hm a po f l g p a n de g p a p p l i c a t i o n ( t r a n s m i s s i o nc o n t r o lp r o t o c 0 1 i n t e r n e tp r o t o c 0 1 ) 协议族就是最常用的数据通信协 议。而路由协议可以分为两类：静态路由和动态路由。静态路由需要网络管理者手动的将到 达目的网络的路径添加到路由表中：而运行动态路由协议算法的路由器则不然，它们可以自 动的学习到达远端网络的路径信息。对于动态路由协议，根据其是否仅在一个自治系统( a s ) 内部使用，动态路由协议又可以分为内部网关协议和外部网关协议。这里的自治系统指一个 具有统一管理机构、统一路由策略的网络。自治系统内部采用的路由选择协议称为内部网关 协议，常用的有r i p 、o s p f 等；外部网关协议主要用于多个自治系统之间的路由选择与信息 交换，常用的是b g p ，如图1 1 所示。图中a s l 、a s 2 、a s 3 分别代表3 个不同的自治系统，3 个a s 内部分别运行各自的内部网关协议如r i p 、o s p f 、i s i s 等；3 个a s 之间运行外部网关 协议如b g p 。 3 边界州关协议b g p 4 + 的互操作性测试研究 为了能够有效地开展路由协议的测试工作，必须对路由协议进行深入的分析，从而对它 的特点有清晰的认识。与通信协议相比，路由协议的不同点在于i l 】： ( 1 ) 路由协议的功能是为路由计算提供所需的信息 2 1 ，正确地处理和发送网络拓扑信息是 路由协议的主要职责之一，它并不要求数据的“尽力转发”；而通信协议所传送的通 常是上层协议的数据，目的是将这些数据尽力、正确、迅速地传送。 ( 2 ) 所有的路由协议都要使用通信协议所提供的服务，如b g p 使用t p 服务，o s p f 使用i p 服务等。 ( 3 ) 路由协议具有分布式系统的特性。三大路由协议b g p 、r i p 、o s p f 虽然在复杂程度上 有很大的差异，但是都具有分布式系统的共性。各个自治系统内和系统之间的路由器 共同构成主干网和各级子网，各自运行自己的协议，相互交换数据信息，共同协作实 现一定的功能，有利于网络资源的分配和优化，保证了网络的强壮性和可靠性。 ( 4 ) 路由协议中有一个非常重要的概念就是数据库，用于存放路由信息。路由表是其中最 为重要的数据库，直接提供路由所需的信息。 ( 5 ) 路由协议中存在大量的内部处理过程。比如在b g p 4 中，主要的内部处理过程称为决 策处理，包括三个阶段：计算路由的优先度、路由选择、路由传播。这三个阶段既有 顺序的调用关系，又由于对数据库的访问需要相互排斥。在三个阶段的处理过程中， 应用了大量的规则和策略。 ( 6 ) 路由协议利用下层协议传送路由信息，没有“上层”协议存在；而通信协议第n 层使 用n 1 层的服务为n + i 层提供服务。 ( 7 ) 路由协议之间的交互较为复杂。以b g p 为例，路由器既要与b g p 对等体进行交互又要 与自治系统内部运行其它路由协议的路由器进行交互。 因此，在对路由协议的测试中要注意这些特点。测试中不但要考虑协议的数据包结构、 协议的状态机这些与通信协议测试很相似的内容，还要考虑到路由信息的交互和处理这一 路由协议特有的一大类内容。在具体的测试中，要考虑具体协议所涉及到的路由策略对互 操作性测试的影响。 1 2b g p 协议概述 b g p 边界网关路由协议是在外部网关协议e g p 3 巧1 的基础上定义的，并且在多个r f c 中进行了规定。r f c l l 0 5 1 6 i 描述了b g p 的第一个规范，之后在r f c l l 6 3 t 7 1 ，r f c l 2 6 7 8 1 进 行了改进，我们所熟悉的b g p 4 最初是在r f c l 6 5 4 1 9 1 中描述的，之后该标准被r f c l 7 7 1 1 o 】 4 内蒙古大学硕十学位论文 取代，在r f c l 7 7 1 中提出了一套新的机制来支持无类域白j 路由( c i d r , c l a s s l e s s i n t e r d o m a i n r o u t i o n ) 技术，这些机制包括广播m 地址前缀和取消网络中“类”的概念；b g p 4 还引入 路由聚合和路由过滤的机制，减少了b g p 发言者存储和交换的路由。b g p 4 的最新版本 r f c4 2 7 11 1 1 】完成于2 0 0 6 年1 月，它对引起b g p 状态变化的事件进行了更详尽的描述，取 代了r f c l 7 7 1 。在r f c l 7 7 1 中，b g p 事件只有1 3 个并且都是必须事件；但是在r f c4 2 7 1 中，b g p 事件共2 8 个，分为a d m i n i s t r a t i v e 事件，计时器事件，t c p 连接事件，b g p 消 息事件四类，其中必须事件共1 3 个，可选事件1 5 个，使得b g p 4 协议的处理能力更加完 善。 b g p 运行于传输协议t c p 之上，使用端口号1 7 9 来建立和维护连接。每个b g p 路由 器维护到特定网络的所有可用路径构成的路由表，它维持从对等路由器收到的路由信息直 到收到增量更新。b g p 设备在初始数据交换和增值更新后交换路由信息。当路由器第一次 连接到网络时，b g p 路由器交换它们的整个b g p 路由表，当连接稳定之后，如果路由表 发生改变，路由器则只发送路由表中改变的部分。b g p 路由器并不周期性发送路由更新， 它是触发更新的，并且更新只包含到某网络的最佳路径。b g p 周期性地发送k e e p a l i v e 信 息来验证与对等路由器的连接是否正常。 1 2 1 髓p 的功能 b g p 交互系统的主要功能是在自治系统问自动交换网络可达信息，通过交换带有自治 系统号( a s ) 序列的路由可达信息来构建自治区域的拓扑图，从而很好地避免了路由中的 环路问题。每个b g p 路由器都维护一个路由信息库，该信息库包含三部分：a d j r i b s i n 、 l o c - r i b 、a d j r i b s - o u t 。b g p 通过与邻居路由器交换路由信息来工作。 1 2 2 陷p 路由 在b g p 中存在三种类型的路由：a s 问路由、a s 内部路由、贯穿( p a s s t h r o u g h ) a s 路 由。其中： ( 1 ) a s 问路由发生在不同a s 的两个或多个b g p 路由器之间，这些系统的对等路由器使用 b g p 来维护一致的网络拓扑，a s 间通信的b g p 邻居必须处于相同的物理网络。因特网 就是使用这种路由的实例，它由多个a s ( 或称管理域) 构成，b g p 用于在a s 间提供最 佳路径。 边界蜘关协议b g p 4 + 的互操作性测试研究 ( 2 ) a s 内部路由发生在同一a s 内的两个或多个b g p 路由器间，同一a s 内的对等路由器 用b g p 来维护一致的网络拓扑。b g p 也用于决定a s 内的哪个路由器作为外部a s 的连 接点。 ( 3 ) 贯穿a s 路由发生在通过不运行b g p 的a s 交换数据的两个或多个b g p 对等路由器问。 在贯穿a s 环境中，b g p 通信既不源自a s 内，目的地也不属于该a s ，b g p 必须与该 a s 内使用的路由协议交互以便成功地通过a s 进而传输b g p 通信信息，如图1 - 2 。 1 2 3b 6 p 报文 障一u b g p s o u r c e d e s t i l l a t i o n 图1 - 2 贯穿a s 路由示例图 f i g u r e1 - 2t h ee x a m p l eo f p a s st h r o u g ha sr o u t e b g p 包括4 种报文类型：o p e n 、k e e p a l i v e 、u p d a t e 、n o t i f i c a t i o n 。其中： ( 1 ) o p e n 报文：用来交换各自b g p 的版本号、自治系统号、保持时间、b g p 标识等信息。 但) k e e p a l i v e 报文：b g p 对等路由器之间周期性地互发该报文，以确保其连接有效。 ( 3 ) u p d a t e 报文：携带更新路由信息，其中包括撤消路由信息和可达路由信息及其路径属性。 该类报文由不可达路由、路径属性和网络可达性信息三部分构成。该类报文有以下三种 情况： 一个u p d a t e 报文一次只能通告一个路由，但可以携带多个路径属性。 一个u p d a t e 报文一次可以通告多个路由，但它的路径属性必须相同。 一个u p d a t e 报文一次可以列出多个被撤消的路由。 ( 4 ) n o t i f i c a t i o n 报文：当b g p 路由器检测到连接中断、协商出错、报文差错时，关闭同对 等路由器的连接，并且通知对等路由器关闭连接的原因。 o p e n 报文首先建立邻居关系，其它对等路由器收到o p e n 报文后，以k e e p a l i v e 报文 做出响应，连接成功后开始发送u p d a t e 报文，之后b g p 路由器周期性地发送k e e p a l i v e 6 内蒙古大学硕上学位论文 报文以维持连接，防止会话超时。当检测到一个差错时，b g p 路由器发送n o t i f i c a t i o n 消息 报文到对等路由器。 以上四种类型的报文都具有一个1 6 个字节全l 的报头，后面跟2 个字节的长度字段和 1 个字节的类型字段。b g p 报文的长度包括报头的长度，最短的b g p 消息不会小于1 9 字节 ( 1 6 + 2 + 1 ) ，最大的b g p 消息不会超过4 0 9 6 字节，如图1 3 。 。 m a k e r l e g t h耐p e 1 3b g p 4 + 协议 图1 - 3b g p 消息报文头部格式示意图 f i g u r e1 - 3b g pm e s s a g eh e a d e rf o r m a t i n t e m e t 是由大量自治系统构成的复杂网络。在i n t e m e t 上，边界网关协议b g p 4 是目前 广泛使用的自治系统间的路由协议。随着i p v 6 的部署，原本只能支持i p v 4 的b g p 4 协议承 载路由信息的时候，无法达到期望的目标，为了使b g p 4 协议能够支持i p v 6 协议，i e t f 对 b g p 4 进行了扩充，修订完成了r f c 2 8 5 8 ( m u l t i p r o t o e o le x t e n t i o n sf o rb g p 4 ，即，b g p 4 + ) t 1 2 l 。 为了使b g p 支持多种协议，提供向后兼容性，r _ f c 2 8 5 8 主要做了以下几点修改：将b g p 中承载i p v 4 地址的三种属性做了适当的调整，把n e x t h o p 属性以及n l r i ( n e t w o r kl a y e r r e a c h a b i l i t yi n f o r m a t i o n ) 同一个特定的网络层协议联系起来。同时为了简化b g p - 4 多协议扩 展，r f c 2 8 5 8 定义了两个新的路径属性： m u l t i p r o t o e o l r e a c h a b l e n l r i ( m p _ r e a c h _ n l r i ) 和 m u l t i p r o t o e o l u n r e a c h a b l e n l r i ( m p _ u n r e a c h _ n l r i ) 。第一个属性( m p _ r e a c h _ n l r i ) 承载的信息包括可达目的地 信息与提供转发这些可达目的地信息的下一跳信息，第二个属性( m pu n r e a c h 以承载目的地不可达的信息。这两种属性都是可选非转发的路径属性。所谓可选的路径属性 就是不要求所有的b g p 路由器都支持这种属性，而非转发的则指包含这种属性的u p d a t e 消 息将不能被转发到邻居a s 的b g p 对等路由器。 1 4b g p 4 + 协议的工作过程 随着l n t c m c t 的发展和网络服务商业化进程的加快，i n t e m e t 的规模和复杂程度都在迅速 边界列关协议b g p 4 + 的且操作性测试研究 增长。从管理角度，i n t e m e t 由不同的a s 构成，所谓的a s 是相对独立的网络，在一个a s 内有自主的路由策略。这些a s 可能分别隶属于不同的i n t e r n e t 服务提供商( i n t e r a c t s e r v i c e p r o v i d e r 简称i s p s ) ，而不同的i s p s 可能重组成为新的i s p ，从而形成动态的管理组织结构。 在a s 内部，路由是通过域内路由协议来管理调度，如o s p f 、i s i s 和r i p 等；在a s 之间 它们通过公共网络访问点( p u b l i en e t w o r ka c c e s sp o i n t s 简称p n a p ) 和边界网关协议来接 收和转发网络信息。b g p 允许每一个a s 按自己的路由策略选择、通告和接收路由，而决定 路由策略的主要依据是i n t e r n e t 商业服务合同。b g p 是基于策略的路由协议，所有b g p 路 由器通过策略选择接收和传播路由信息，不向外暴露自己所在网络的拓扑结构。 根据制定好的路由策略要对运行b g p 的路由器进行路由配置，然后b g p 路由器之间需要 建立t c p 连接以交换路由信息，这种连接称为b g p 会话( s e s s i o n ) 。每一个会话包含了两个 端点路由器，这两个端点路由器称为相邻路由器( n e i g h b o r ) 或是对等路由器( p e e r ) 。t c p 连接成功之后，对等路由器要相互发送o p e n 消息进行参数协商。如：o p e n 消息中的版本号 字段用来协商双方所使用的b g p 协议版本，这个版本应该是双方都可以支持的最高版本， o p e n 消息的h o l dt i m e 字段用来协商双方互相发送消息的最长时间间隔，超出这个时间间隔 双方将断开连接。h o l dt i m e 的值可以为o 或大于3 秒的值，而最终值是通过双方o p e n 消息中 h o l d t i m e 值的最小值来确定的。b g p 4 + 中o p e n 消息的可选属性中可以采用b g p 能力宣告， 来决定在b g p 连接建立时是否与对等路由器使用多协议扩展传递路由信息，否则将无法获知 其它对等路由器是否可以支持这一扩展。图1 - 4 是一个能力通告的示例。从图1 4 中的a d d r e s s f a m i l yi d e m i f i e r 字段可以看出双方使用的b g p 协议是支持i p v 6 的，也就是说它们转发的 u p d a t e 消息是可以承载i p v 6 网络层可达信息的。 c a p a b i l i t i e sa d v e r t i s e m e n t 倡b y t e s ) p a r a m e t e rt y p e ：c a p a b i l i t i e s ( 2 ) p a r a m e t e rl e n g t h ：6b y t e s m u l t i p r o t o e o le x t e n s i o n sc a p a b i l i t y ( 6b y t e s ) c a p a b i l i t yc o d e ：m u l t i p r o t o c o le x t e n s i o n se a p a b i l i t y ( 1 ) c a p a b i l i t yl e n g t h ：4b y t e s c a p a b i l i t yv a l u e a d d r e s sf a m i l yi d e m i f i e r ：i p v 6 ( 2 ) r e s e r v e d ：1b y t e s u b s e q u e n ta d d r e s sf a m i l yi d e n t i f i e r ：u n i c a s t ( 1 ) 图1 4 能力通告示例 f i g u r ei - 4t h ee x a m p l eo f c a p a b l i t ya d v e r t i s e m e n t 内蒙古人学硕士学位论文 b g p 对等路由器连接建立成功之后，开始交换路由信息。在初始情况下，需要交换全部 路由表。此后，采用增量更新的方式进行路由刷新。b g p 4 + 的路由信息存储在相应的路由信 息库中，经过处理、计算并通过决策过程选择最好的路由发送给其它b g p 对等路由器，其中 包括两类操作：路由撤消和路由宣告。对于无效的路由信息，b g p 4 + 通过发送带有 m pu n r e a c h路径属性的 消息撤消路由，每一条被撤消的路由都包含一个二_ n l r iu p d a t e 元组 ，其中i p p r e f i x 是一个地址前缀，表示一个网络地址，其有效长度由 l e n g t h 说明；在一个u p d a t e 消息中可以撤消一条或多条路由信息。b g p 4 + 宣告的路由则是由 b g p 4 原来的路径属性和新增的m pr e a c hn l r i 进行说明。m pr e a c hn l r i 属性的网络 可达性信息由一个或多个 二元组构成，描述了通过n e x th o p 指明的网关 可以到达的网络。在交换路由信息的过程中，对等路由器会周期性的发送k e e p a l i v e 消息， 从而维持双方的连接。 b g p 对等路由器在完全建立连接之前会经历不同的状态，包括i d l e 状态、c o n n e c t 状态、 a c t i v e 状态、o p e n s e n t 状态、o p e n c o n a r m 状态和e s t a b l i s h e d 状态。图1 5 是b g p 对等路由器 连接建立过程的简化的有限状态机，变迁边上没有输入输出标记。b g p 4 + 与b g p 4 的连接建 立过程是相同的。 图1 5b g p 4 和b g p 4 + 连接建立过程 f i g u r e1 - 5t h ep r o c e d u r eo f b g pa n db g p 4 + c o n n e c t i n g 下面我们对b g p 4 + 连接建立过程进行简要的说明。开始时b g p 路由器处于i d l e 状态， 在这个状态下b g p 响应s t a r t 事件，初始化所有b g p 资源，启动c o n n e c t r e t r y 时钟，并向 远端对等路由器发起t c p 连接，开始监听远端对等路由器的连接状态。当监听到远端对等路 由器开始初始化连接时，状态改变为c o n n e c t 。在这个状态下b g p 等待t c p 连接完成，如果 t c p 连接成功，则完成初始化，同时发送0 p e n 消息到对等路由器并改变状态到o o e n s e n t ， 否则就转到a c t i v e 状态尝试再次连接。在a c t i v e 状态，如果尝试t c p 连接成功则转变到 9 边界嗍关协议b g p 4 + 的互操作性测试研究 o p e n s e n t 状态，否则将继续停留在该状态。在o r e n s e n t 状态时，等待来自对等路由器的o p e n 消息，如果收到正确的o p e n 消息，则转到0 p e n c o n f i r m 状态，否则发送n o t i f i c a t i o n 消息 到对等路由器并改变状态到i d l e 。在o p e n c o n f i r m 状态时，等待来自对等路由器的k e e p a l i v e 和n o t i f i c a t i o n 消息。如果收到k e e p a l i v e 消息，则改变状态到e s t a b l i s h e d ，b g p 连接成 功；如果收到n o t i f i c a t i o n 消息就转回到i d l e 状态。 1 0 内蒙古人学硕士学位论文 第二章互操作性测试理论 2 1 协议测试基本概念 协议测试理论是协议工程学的一个重要分支。研究协议测试理论的原因在于一个标准化 的协议并不能确保该协议的不同实现之间能够成功的进行通信。这是因为协议标准目前基本 上是使用自然语言描述的，实现者对于协议的不同理解会产生不同的协议实现，甚至有时会 是错误的实现。因此需要一种有效的方法来对协议实现的正确性和有效性进行判别，这就是 “协议测试”。 实际上，协议测试就是试图通过实验的方法找出错误的过程。在协议测试过程中既要 模拟协议实现正常工作的情况，也要模拟异常使用的情况；既要模拟协议实现单独运行的 情况，也要模拟协议实现之间互相通信的情况，这样才能确保在任何情况下协议实现的正 常工作。由于对一个协议实现进行穷举测试是不现实的，所以协议测试并不能保证一个协 议实现的完全正确，也就是说协议测试只能表明“存在错误”，而不能证明“不存在错误”， 这是协议测试的基本出发点。 协议测试是从软件测试的基础上发展而来，一般的软件测试可以分为功能测试和结构 测试两种。其中，结构测试又称为“白盒测试”，它是基于一个软件的内部结构进行的测 试，其目的是通过执行每条语句、遍历程序的各个分支来检查整个程序代码的正确性。与 此相反，功能测试只是依据软件的说明对从外部可以观察到的软件功能进行测试，所以也 称之为“黑盒测试”，即把被测试系统看作一个黑盒，仅仅通过观察外部行为来确定软件 的功能实现，而不涉及程序的内部结构。功能测试的目的是根据软件的说明确定软件实现 是否达到了要求，因此预先要有一个简洁明确的软件功能说明。协议测试属于功能测试， 即黑盒测试。 协议测试包括四种类型的测试“”：一致性测试( c o n f o r m a n c et e s t i n g ) ，互操作性测 试( i n t e r o p e r a b i l i t yt e s t i n g ) ，性能测试( p e r f o r m a n c et e s t i n g ) 和健壮性测试( r o b u s t t e s t i n g ) 。一致性测试旨在检测协议实现或系统本身与协议规范的符合程度；互操作性测 试则重在检测两个以上的协议实现或系统在接近真实的环境下互相操作互相通信的能力； 性能测试主要检测协议实现或系统的性能指标( 如数据传输速度、连接时间、执行速度等) ； 健壮性测试重点检测协议实现或系统在各种恶劣的环境下运行的能力( 如注入干扰报文、 边界嘲关协泌b g p 4 + 的互操作性测试研究 信道被切断等) 。其中，一个协议实现或系统能否通过一致性测试和互操作性测试是它能 否与其它实现成功互连互通的重要保障，因此对协议实现进行互操作性测试和一致性测试 都是非常重要的。 2 2 互操作性测试的研究现状 鉴于互操作性测试对产品推广应用的重要性，国内外的许多科研组织和团体投入了大量 的人力物力，开展了各种研究实践工作。其中：日本的t a h i 项目研究和开发了i p v 6 协议的 一致性测试系统和互操作性测试系统，并在自己的网站上“”免费公开研究成果；n e w h a m p s h i r e 大学的互操作实验室1 0 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 的相关协议， 并免费提供部分相关测试套，在支持i p v 6 的路由协议方面包括b g p 4 + 、o s p f v 3 、r i p n g 的部 分互操作测试套；全球i p v 6 论坛从2 0 0 3 年开始在全球各地开展“i p v 6r e a d y ”标识计划， 其下设“i p v 6r e a d y ”专业委员会。该委员会的委员均是全球i p v 6 论坛认可的互联网技术 专家，分别来自日本t a h i 、欧洲e t s i 、美国u n h 及中国天地互连公司( 简称b i i ) 。根据该 委员会的要求，参加该计划的产品必须通过产品测试和互操作性公开测试以及专业委员会审 核才能获得“i p v 6r e a d y ”标识，标识产品范围涵盖主机、路由器、操作系统、协议栈、应 用系统、移动终端、信息家电、嵌入式系统等支持i p v 6 的产品。在国内，清华大学在路由 协议测试领域开展了大量的测试工作，他们开发了协议集成测试系统( p r o t o c o li n t e g r a t e d t e s ts y s t e m ，p i t s ) “”，并对许多厂家的路由产品进行了测试；中科院计算所开发的协议一 致性测试系统是一个通用的完整的i p v 6 协议测试平台，采用自己定义的描述语言来描述测 试过程和测试报文，涵盖3 5 个r f c ，5 9 9 个测试套，能对i p v 6 及相关协议进行完整的一致 性测试；中国科技大学、兰州大学、上海交通大学等多所高校的i p v 6 实验室也开发了自己 的测试平台并对i p v 6 及其相关协议进行了测试。 在互操作性测试的理论研究方面，国际国内的学者也发表了一些相关的文章。其中：在 协议互操作测试生成方面，文献 1 7 中把一类通信协议称做对称的通信协议，在这类通信协 议中，同一协议的多个实现处于完全对等的角色，提供完全相同的功能，比如a t m 协议，文 章针对这类协议的控制部分，通过有限状态机对协议进行形式化建模，基于稳定状态和内部 交互消息提出了互操作性测试套的生成方法，并通过a t m 协议给出了生成测试套的例子，之 后考虑到对称协议的特点，对测试套生成过程进行了优化，避免了同一测试套执行两次，从 而使测试套的数目减小了一半。文献 1 8 提出了一种互操作测试套的生成算法，作者称这种 1 2 内蒙古大学硕十学位论文 算法很适用于像a t m b i s d n 这类通信协议，并且通过a t m b i s d n 给出了测试套生成的例子， 但是这种算法存在一定的局限性，就是只能处理两个内部消息交互的情况，也就是说由外部 输入激励的内部消息的数目小于等于二。而文献 1 9 3 针对文献 1 8 中所存在的问题，提出了 改进的互操作性测试套自动生成算法，能够处理类似t c p 三次握手协议这样协议的测试套生 成，并且把该算法应用到a t m b i s d n 和t c p 协议上，给出了测试套生成的示例，之后抽取了 两个t c p 互操作测试套进行了变迁覆盖分析。文献 2 0 在互操作性测试生成过程中，为了避 免状态爆炸问题，做了两个假设：( 1 ) 慢环境假设，即系统工作在慢环境中，所谓慢环境是指 只有当被测系统对前一个外部输入响应完毕之后，外界环境才可以向被测系统发送下一个外 部输入；( 2 ) 协议说明规范和协议实现中都不存在活锁(