基于着色Petri网的IS-IS路由协议互操作性测试的研究＊

赵玉兰，冀 超，蒋凤仙，朱洋洋，雷厉霆，张志斌

（内蒙古大学计算机学院，内蒙古 呼和浩特 010021）

1 引言

协议测试是保证各网络产品能够正常使用的重要手段，包括一致性测试、互操作性测试、性能测试和鲁棒测试。一致性测试是协议测试最基本的工作，其目的是检测协议实现与协议说明之间是否相一致；互操作性测试重在检测两个或者多个协议实现之间能否进行正确的通信和交互；性能测试的目的是检测协议实现的各项性能指标；鲁棒测试的目的是检测协议实现能否在各种恶劣条件下正常地工作。然而，由于受各种条件的制约，对协议进行的一致性测试，无法进行穷举测试，再加上协议规范本身的灵活性，不同厂家对同一协议的理解不同，相应的产品也不同；另外，对于协议可选项，不同厂家在生产产品的时候也会进行不同的取舍，这些原因导致了即使通过了一致性测试的产品，也不能保证它们之间就能进行正确的互操作。因此，在一致性测试之后，有必要再进行互操作性测试。目前，对于互操作性测试的研究越来越被重视，一些大的组织，例如ETSI、ITU-T、ISO 等均已开展相应的工作，并取得了一些成果[1～3]。

中间系统-中间系统IS-IS（Intermediate System to Intermediate System）路由协议，与路由信息协议RIP（Routing Information Protocol）、开放式最短路径优先OSPF（Open Shortest Path First）等协议一样，是一种主流的内部网关协议，具有分层的网络路由、可扩展性强、收敛速度快、稳定性好等特点。在一些大型网络中，IS-IS路由协议得到了越来越多的应用，其性能要比OSPF协议好。许多厂商，例如思科、华为、中兴等，都推出了支持ISIS协议的网络产品。然而，相对于RIP、边界网关协议BGP（Border Gateway Protocol）、OSPF 等协议，对IS-IS协议的研究相对较少。国内外对IS-IS协议测试的研究，也多集中于一致性测试。因此，有必要对IS-IS协议进行互操作性测试的研究。

2 IS-IS路由协议概述

IS-IS协议最早由国际标准化组织ISO 定义[4]，IETF 工作组将其进行了改进，使其能够同时运行在OSI和TCP／IP两种网络环境中[5]。ISIS协议是一种得到广泛应用的、功能强大的路由选择协议，它支持分层路由，以便在大型网络中管理选路和实现可扩展路由选择。一个运行IS-IS协议的路由域被分成Level 1（L1）层和Level 2（L2）层。同一L1区域内使用L1路由，不同区域间使用L2（L1／L2）路由器相连，只有同一层次的相邻路由器才有可能形成邻接关系[6]。IS-IS协议路由层的功能主要分为两类：子网相关功能和子网独立功能。子网相关功能负责与数据链路层相兼容，在各种类型的链路上检测、形成和维护路由器的邻接关系。子网独立功能提供路由选择及相关控制信息的管理和交换。

3 IS-IS路由协议互操作性测试模型的建立

3.1 CPN建模

Petri网是由德国人Petri C A 在其博士论文中提出的一种形式化模型。该模型建立在并发的概念上，能够直观地表示非确定性，可用于描述通信系统中异步成分之间的关系[7]。着色Petri网CPN（Colored Petri Nets）是由丹麦的Kurt J在Petri网的基础上定义的一种高级Petri网。CPN将Petri网的描述能力和编程语言处理能力进行了有机整合[8]，利用Petri网描述系统的同步、交互、并发等行为，同时用编程语言定义操作数值和数据类型，并引入color集和token集，使得模型变得清晰，且易于理解。作为一种形式化描述语言，CPN 提供了包括建模、仿真和分析等方面的可视化界面，采用自底向上或自顶向下的方式来进行，避免了Petri网在处理复杂问题时会产生过多的库所和变迁，使模型变得过于庞大和复杂，从而导致状态空间爆炸问题。CPN 通过减少Petri网的库所和变迁来简化Petri网，仍然满足原Petri网的性质[9]。在计算机（分布式系统、并行计算、网络工程、软件工程、人工智能等）、通信、自动化、工作流、机械设计与制造、航空航天等许多领域得到了广泛的应用。

3.2 IS-IS协议层次化建模分析

层次化的思想在计算机网络领域有着广泛的应用，OSI网络七层模型和目前广泛应用的TCP／IP网络结构，都采用了分层的思想。

出于以下几点原因考虑，本文将采用层次化的方法对IS-IS协议的互操作性测试进行研究：

（1）互操作性测试是在一致性测试的基础上发展起来的，可以借鉴一些一致性测试的方法，并将其引入到互操作性测试当中。ISO／IEC 9646-1中描述了四种一致性测试的类型，都具有很明显的层次化特性。因此，在进行互操作性测试时，也可以考虑采用层次化的方法，将被测系统某一功能的测试从复杂的环境当中抽取出来，减少了一些不必要的影响条件，使测试人员能够更加专注于对某一功能的测试研究。

（2）IS-IS协议本身有着明显的层次结构特征，很适合采用层次化的方法进行分析研究。而且，由于CPN 引入了层次化概念，这使得对IS-IS协议的建模更容易实现模块化和规范化。

3.3 基于CPN 的IS-IS互操作性测试的交互模型

在建模的过程中，将IS-IS协议互操作性模型按照协议功能进行分层，再根据网络环境的不同，分别建立点对点网络和广播网络环境下的相应模型。由于篇幅所限，本文只给出在广播网络环境下的IS-IS协议的CPN 模型。在实际中，IS-IS路由器形成L1层邻接关系、L2层邻接关系或者同时形成L1层和L2层邻接关系，只是发送的数据包类型不同，并不影响互操作模型的建立，因此在建模时不考虑路由分层的情况。

为了控制模型的规模，尽量减少状态爆炸的可能，在建立CPN 模型时，规定了如下的约束条件：

（1）在建立CPN 互操作测试交互模型时，只考虑两台路由器一对一的情况。

（2）在不影响模型的基础上，对其进行化简，将与互操作无关的库所和变迁删除。

（3）在模型中，对于可能被多次点火的变迁，限制点火的次数。

（4）对于一些场景下的模型，约定一些限制条件。例如，在广播网络下，路由器IS＿1和IS＿2作为通信的双方，都有可能被选举为指派中间系统DIS（Designated Intermediate System），本文假设路由器IS＿2最终被选举为DIS。

图1是基于广播网络下IS-IS 协议子网相关功能的CPN 的交互模型。图2是基于广播网络下IS-IS协议子网独立功能的CPN 的交互模型。

Figure 1 CPN model of subnet dependent functions under broadcast network图1 广播网络下子网相关功能CPN 模型

Figure 2 CPN model of subnet independent functions under broadcast network图2 广播网络下子网独立功能CPN 模型

表1列出了图1和图2中各库所的符号和名称。表2列出了图1和图2中各变迁的符号和名称。

Table 1 Places of CPN model in IS-IS protocol表1 IS-IS协议的CPN 模型库所

Table 2 Transitions of CPN model in IS-IS protocol表2 IS-IS协议的CPN 模型变迁表

4 基于CPN Tools的IS-IS互操作测试序列的生成

CPN Tools是由丹麦奥胡斯大学开发的一款集编辑、模拟、分析于一身的形式化建模工具，可以为用户提供可视化的开发环境，支持功能强大的元语言，也可以进行增量语法检查和代码生成，在一定程度上保证了模型的正确性。CPN Tools还可以自动生成和分析状态空间[10]，根据自动生成的状态空间可以设计测试序列，从而对协议实现一致性测试和互操作性测试。

图3和图4分别给出了由图1和图2所示模型生成的完全状态空间。

Figure 3 Partial state space of subnet dependent model under broadcast network图3 广播网络下子网相关模型的部分状态空间

Figure 4 Full state space of subnet independent model under broadcast network图4 广播网络下子网独立模型的完全状态空间

测试序列的自动生成方法的研究，即设计一种既能够使用尽可能少的测试序列数目，又能检测出尽可能多的错误的测试序列生成算法，是互操作测试研究中需要解决的一个重点问题。因此，测试序列的覆盖率是衡量测试序列自动生成算法优劣的一个重要指标[11]。文献[12]介绍了一种从Petri网可达图生成测试序列的算法。鉴于本文所使用的完全状态空间与可达图类似，因此本文采用了文献[12]的思想，由完全状态空间生成测试序列。

图5给出了图3所示的完全状态空间中的一个测试序列。测试目的是广播网络下IS-IS路由器邻接关系建立成功，相应的标识为节点40，库所s3和s3′含有一个token，其余库所token数为0。初始标识为节点1。从节点40逆向搜索到结节1，将其中一条路径的变迁序列倒序排列，得到一条测试序列：t1t1′t2t2′t6t6′t7t7′。

Figure 5 Example of testing sequence图5 测试序列举例

使用上述生成测试序列的方法，对图3和图4的IS-IS协议的CPN 模型的完全状态空间进行了分析，共生成77个测试序列。

5 实验及结论

由测试序列得到测试例后，需要根据测试目的搭建测试环境，本文测试使用的是Windows XP操作系统，用GNS 3 0.7.2路由模拟软件模拟Cisco 7200、Cisco 3640等设备，用网络分析工具Wireshark软件和若干台PC机，对IS-IS协议进行了互操作性测试。本文测试环境的拓扑结构图如图6所示。

Figure 6 Topology of IS-IS protocol interoperability test environment图6 IS-IS协议互操作性测试环境拓扑图

图6中IUT 表示被测试例，终端通过路由器的console口对其进行配置，在PC 机上运行抓包工具，对IUT 之间交互的信息进行检测。

通过对IS-IS 协议互操作性测试结果分析发现，大部分测试例通过了测试，但仍有一小部分测试例没有通过测试，主要原因是路由器并未实现相关功能，或者是对协议说明中不确定的描述选取了不同的实现方式。另外，还有一部分测试例，因为测试条件不满足，如测试设备不符合要求、内部活动不可观察等原因无法进行测试。表3给出了测试结果。

Table 3 Results of IS-IS protocol interoperability test表3 IS-IS协议互操作性测试结果

6 结束语

通过对IS-IS 协议ISO10589 和RFC1195 相关标准的研究，对利用形式描述语言CPN 支持分层体系的IS-IS协议建立了互操作性测试的模型，包括点对点网络和广播网络环境下子网相关功能和子网独立功能CPN 模型；利用CPN Tools工具，根据建立的CPN 模型自动生成了完全状态空间；通过对完全状态空间进行分析，再根据测试目的生成了测试序列，并由测试序列编写了测试例；在Windows XP平台下，使用路由模拟软件GNS 3模拟Cisco 7200、Cisco 3640等设备，用得到的测试例对其进行了互操作性测试，并对测试结果进行了分析。下一步的研究工作，可以对建立的互操作性模型进行优化：一是在不影响已有覆盖度的前提下，研究如何减少模型的复杂度；二是对于模型没有描述的功能，对其进行补充，使其能够覆盖更多的协议功能。

[1]ETSI TS 102 237-1，V4.1.1，Telecommunications and internet protocol harmonization over networks（TIPHON）release 4；Interoperability test methods and approaches；Part 1：Generic approach to interoperability testing[S].France：ETSI，2003.

[2]ETSI EG 202 237，V1.1.2.Methods for testing and specification（MTS）；Internet protocol testing（IPT）；Generic approach to interoperability testing[S].France：ETSI，2007.

[3]ETSI TS 102 517，V2.0.1.Title methods for testing and specification（MTS）；Internet protocol testing（IPT）：IPv6 core protocol；Interoperability test suite[S].France：ETSI，2008.

[4]ISO DP 10589，Information technology-telecommunications and information exchange between systems-intermediate system to intermediate system intra-domain routing information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode network service （ISO 8473）[S].2002.

[5]Callon R.Use of OSI IS-IS for routing in TCP／IP and dual environments[R].RFC 1195，Massachusetts：DEC，1995.

[6]Zhao Yu-lan，Jia Ya-zhe，Zhang Hong-yu.The designing and implementation of protocol test cases automatically generating system based on TTCN-3[C]∥Proc of the 2nd International Conference on Future Computer and Communication，2010：2322-2325.

[7]Mehrpour H，Karbowiak A E.Modelling and analysis of DOD TCP／IP protocol using numerical petri nets[C]∥Proc of IEEE Region 10Conference on Computer and Communication Systems，1990：617-622.

[8]Jensen K.Colored petri nets：Basic concepts，analysis methods and practical use[M].Berlin：Springer-Verlag，1996.

[9]Jensen K.Colored petri nets：Basic concepts，analysis methods and practical use.Vol.2，Analysis methods[M].Berlin：Springer-Verlag，1995.

[10]Ratzer A V，Wells L，Lassen H M，et al.CPN tools for editing simulating，and analysing coloured petri nets[C]∥Proc of the 24th International Conference on the Application and Theory of Petri Nets，2003：450-462.

[11]LüXin-yan，Zhao Bao-hua，Zhou Hao.A dynamic protocol conformance testing method[J].Journal of University of Science and Technology of China，2005，35（3）：338-404.（in Chinese）

[12]Hang Cheng-bao.Research on interoperability testing of OSPFv3protocol[D].Hohhot：Inner Mongolia University，2009.（in Chinese）

附中文参考文献：

[11]吕欣岩，赵保华，周颢.一种动态协议一致性测试方法[J].中国科学技术大学学报，2005，35（3）：338-404.

[12]杭成宝.OSPFv3协议的互操作性测试研究[D].呼和浩特：内蒙古大学，2009.