基于著色Petri網(wǎng)的IS-IS路由協(xié)議互操作性測試的研究＊

趙玉蘭，冀 超，蔣鳳仙，朱洋洋，雷厲霆，張志斌

（內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院，內(nèi)蒙古 呼和浩特 010021）

1 引言

協(xié)議測試是保證各網(wǎng)絡(luò)產(chǎn)品能夠正常使用的重要手段，包括一致性測試、互操作性測試、性能測試和魯棒測試。一致性測試是協(xié)議測試最基本的工作，其目的是檢測協(xié)議實(shí)現(xiàn)與協(xié)議說明之間是否相一致；互操作性測試重在檢測兩個或者多個協(xié)議實(shí)現(xiàn)之間能否進(jìn)行正確的通信和交互；性能測試的目的是檢測協(xié)議實(shí)現(xiàn)的各項(xiàng)性能指標(biāo)；魯棒測試的目的是檢測協(xié)議實(shí)現(xiàn)能否在各種惡劣條件下正常地工作。然而，由于受各種條件的制約，對協(xié)議進(jìn)行的一致性測試，無法進(jìn)行窮舉測試，再加上協(xié)議規(guī)范本身的靈活性，不同廠家對同一協(xié)議的理解不同，相應(yīng)的產(chǎn)品也不同；另外，對于協(xié)議可選項(xiàng)，不同廠家在生產(chǎn)產(chǎn)品的時候也會進(jìn)行不同的取舍，這些原因?qū)е铝思词雇ㄟ^了一致性測試的產(chǎn)品，也不能保證它們之間就能進(jìn)行正確的互操作。因此，在一致性測試之后，有必要再進(jìn)行互操作性測試。目前，對于互操作性測試的研究越來越被重視，一些大的組織，例如ETSI、ITU-T、ISO 等均已開展相應(yīng)的工作，并取得了一些成果[1～3]。

中間系統(tǒng)-中間系統(tǒng)IS-IS（Intermediate System to Intermediate System）路由協(xié)議，與路由信息協(xié)議RIP（Routing Information Protocol）、開放式最短路徑優(yōu)先OSPF（Open Shortest Path First）等協(xié)議一樣，是一種主流的內(nèi)部網(wǎng)關(guān)協(xié)議，具有分層的網(wǎng)絡(luò)路由、可擴(kuò)展性強(qiáng)、收斂速度快、穩(wěn)定性好等特點(diǎn)。在一些大型網(wǎng)絡(luò)中，IS-IS路由協(xié)議得到了越來越多的應(yīng)用，其性能要比OSPF協(xié)議好。許多廠商，例如思科、華為、中興等，都推出了支持ISIS協(xié)議的網(wǎng)絡(luò)產(chǎn)品。然而，相對于RIP、邊界網(wǎng)關(guān)協(xié)議BGP（Border Gateway Protocol）、OSPF 等協(xié)議，對IS-IS協(xié)議的研究相對較少。國內(nèi)外對IS-IS協(xié)議測試的研究，也多集中于一致性測試。因此，有必要對IS-IS協(xié)議進(jìn)行互操作性測試的研究。

2 IS-IS路由協(xié)議概述

IS-IS協(xié)議最早由國際標(biāo)準(zhǔn)化組織ISO 定義[4]，IETF 工作組將其進(jìn)行了改進(jìn)，使其能夠同時運(yùn)行在OSI和TCP／IP兩種網(wǎng)絡(luò)環(huán)境中[5]。ISIS協(xié)議是一種得到廣泛應(yīng)用的、功能強(qiáng)大的路由選擇協(xié)議，它支持分層路由，以便在大型網(wǎng)絡(luò)中管理選路和實(shí)現(xiàn)可擴(kuò)展路由選擇。一個運(yùn)行IS-IS協(xié)議的路由域被分成Level 1（L1）層和Level 2（L2）層。同一L1區(qū)域內(nèi)使用L1路由，不同區(qū)域間使用L2（L1／L2）路由器相連，只有同一層次的相鄰路由器才有可能形成鄰接關(guān)系[6]。IS-IS協(xié)議路由層的功能主要分為兩類：子網(wǎng)相關(guān)功能和子網(wǎng)獨(dú)立功能。子網(wǎng)相關(guān)功能負(fù)責(zé)與數(shù)據(jù)鏈路層相兼容，在各種類型的鏈路上檢測、形成和維護(hù)路由器的鄰接關(guān)系。子網(wǎng)獨(dú)立功能提供路由選擇及相關(guān)控制信息的管理和交換。

3 IS-IS路由協(xié)議互操作性測試模型的建立

3.1 CPN建模

Petri網(wǎng)是由德國人Petri C A 在其博士論文中提出的一種形式化模型。該模型建立在并發(fā)的概念上，能夠直觀地表示非確定性，可用于描述通信系統(tǒng)中異步成分之間的關(guān)系[7]。著色Petri網(wǎng)CPN（Colored Petri Nets）是由丹麥的Kurt J在Petri網(wǎng)的基礎(chǔ)上定義的一種高級Petri網(wǎng)。CPN將Petri網(wǎng)的描述能力和編程語言處理能力進(jìn)行了有機(jī)整合[8]，利用Petri網(wǎng)描述系統(tǒng)的同步、交互、并發(fā)等行為，同時用編程語言定義操作數(shù)值和數(shù)據(jù)類型，并引入color集和token集，使得模型變得清晰，且易于理解。作為一種形式化描述語言，CPN 提供了包括建模、仿真和分析等方面的可視化界面，采用自底向上或自頂向下的方式來進(jìn)行，避免了Petri網(wǎng)在處理復(fù)雜問題時會產(chǎn)生過多的庫所和變遷，使模型變得過于龐大和復(fù)雜，從而導(dǎo)致狀態(tài)空間爆炸問題。CPN 通過減少Petri網(wǎng)的庫所和變遷來簡化Petri網(wǎng)，仍然滿足原Petri網(wǎng)的性質(zhì)[9]。在計(jì)算機(jī)（分布式系統(tǒng)、并行計(jì)算、網(wǎng)絡(luò)工程、軟件工程、人工智能等）、通信、自動化、工作流、機(jī)械設(shè)計(jì)與制造、航空航天等許多領(lǐng)域得到了廣泛的應(yīng)用。

3.2 IS-IS協(xié)議層次化建模分析

層次化的思想在計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域有著廣泛的應(yīng)用，OSI網(wǎng)絡(luò)七層模型和目前廣泛應(yīng)用的TCP／IP網(wǎng)絡(luò)結(jié)構(gòu)，都采用了分層的思想。

出于以下幾點(diǎn)原因考慮，本文將采用層次化的方法對IS-IS協(xié)議的互操作性測試進(jìn)行研究：

（1）互操作性測試是在一致性測試的基礎(chǔ)上發(fā)展起來的，可以借鑒一些一致性測試的方法，并將其引入到互操作性測試當(dāng)中。ISO／IEC 9646-1中描述了四種一致性測試的類型，都具有很明顯的層次化特性。因此，在進(jìn)行互操作性測試時，也可以考慮采用層次化的方法，將被測系統(tǒng)某一功能的測試從復(fù)雜的環(huán)境當(dāng)中抽取出來，減少了一些不必要的影響條件，使測試人員能夠更加專注于對某一功能的測試研究。

（2）IS-IS協(xié)議本身有著明顯的層次結(jié)構(gòu)特征，很適合采用層次化的方法進(jìn)行分析研究。而且，由于CPN 引入了層次化概念，這使得對IS-IS協(xié)議的建模更容易實(shí)現(xiàn)模塊化和規(guī)范化。

3.3 基于CPN 的IS-IS互操作性測試的交互模型

在建模的過程中，將IS-IS協(xié)議互操作性模型按照協(xié)議功能進(jìn)行分層，再根據(jù)網(wǎng)絡(luò)環(huán)境的不同，分別建立點(diǎn)對點(diǎn)網(wǎng)絡(luò)和廣播網(wǎng)絡(luò)環(huán)境下的相應(yīng)模型。由于篇幅所限，本文只給出在廣播網(wǎng)絡(luò)環(huán)境下的IS-IS協(xié)議的CPN 模型。在實(shí)際中，IS-IS路由器形成L1層鄰接關(guān)系、L2層鄰接關(guān)系或者同時形成L1層和L2層鄰接關(guān)系，只是發(fā)送的數(shù)據(jù)包類型不同，并不影響互操作模型的建立，因此在建模時不考慮路由分層的情況。

為了控制模型的規(guī)模，盡量減少狀態(tài)爆炸的可能，在建立CPN 模型時，規(guī)定了如下的約束條件：

（1）在建立CPN 互操作測試交互模型時，只考慮兩臺路由器一對一的情況。

（2）在不影響模型的基礎(chǔ)上，對其進(jìn)行化簡，將與互操作無關(guān)的庫所和變遷刪除。

（3）在模型中，對于可能被多次點(diǎn)火的變遷，限制點(diǎn)火的次數(shù)。

（4）對于一些場景下的模型，約定一些限制條件。例如，在廣播網(wǎng)絡(luò)下，路由器IS＿1和IS＿2作為通信的雙方，都有可能被選舉為指派中間系統(tǒng)DIS（Designated Intermediate System），本文假設(shè)路由器IS＿2最終被選舉為DIS。

圖1是基于廣播網(wǎng)絡(luò)下IS-IS 協(xié)議子網(wǎng)相關(guān)功能的CPN 的交互模型。圖2是基于廣播網(wǎng)絡(luò)下IS-IS協(xié)議子網(wǎng)獨(dú)立功能的CPN 的交互模型。

Figure 1 CPN model of subnet dependent functions under broadcast network圖1 廣播網(wǎng)絡(luò)下子網(wǎng)相關(guān)功能CPN 模型

Figure 2 CPN model of subnet independent functions under broadcast network圖2 廣播網(wǎng)絡(luò)下子網(wǎng)獨(dú)立功能CPN 模型

表1列出了圖1和圖2中各庫所的符號和名稱。表2列出了圖1和圖2中各變遷的符號和名稱。

Table 1 Places of CPN model in IS-IS protocol表1 IS-IS協(xié)議的CPN 模型庫所

Table 2 Transitions of CPN model in IS-IS protocol表2 IS-IS協(xié)議的CPN 模型變遷表

4 基于CPN Tools的IS-IS互操作測試序列的生成

CPN Tools是由丹麥奧胡斯大學(xué)開發(fā)的一款集編輯、模擬、分析于一身的形式化建模工具，可以為用戶提供可視化的開發(fā)環(huán)境，支持功能強(qiáng)大的元語言，也可以進(jìn)行增量語法檢查和代碼生成，在一定程度上保證了模型的正確性。CPN Tools還可以自動生成和分析狀態(tài)空間[10]，根據(jù)自動生成的狀態(tài)空間可以設(shè)計(jì)測試序列，從而對協(xié)議實(shí)現(xiàn)一致性測試和互操作性測試。

圖3和圖4分別給出了由圖1和圖2所示模型生成的完全狀態(tài)空間。

Figure 3 Partial state space of subnet dependent model under broadcast network圖3 廣播網(wǎng)絡(luò)下子網(wǎng)相關(guān)模型的部分狀態(tài)空間

Figure 4 Full state space of subnet independent model under broadcast network圖4 廣播網(wǎng)絡(luò)下子網(wǎng)獨(dú)立模型的完全狀態(tài)空間

測試序列的自動生成方法的研究，即設(shè)計(jì)一種既能夠使用盡可能少的測試序列數(shù)目，又能檢測出盡可能多的錯誤的測試序列生成算法，是互操作測試研究中需要解決的一個重點(diǎn)問題。因此，測試序列的覆蓋率是衡量測試序列自動生成算法優(yōu)劣的一個重要指標(biāo)[11]。文獻(xiàn)[12]介紹了一種從Petri網(wǎng)可達(dá)圖生成測試序列的算法。鑒于本文所使用的完全狀態(tài)空間與可達(dá)圖類似，因此本文采用了文獻(xiàn)[12]的思想，由完全狀態(tài)空間生成測試序列。

圖5給出了圖3所示的完全狀態(tài)空間中的一個測試序列。測試目的是廣播網(wǎng)絡(luò)下IS-IS路由器鄰接關(guān)系建立成功，相應(yīng)的標(biāo)識為節(jié)點(diǎn)40，庫所s3和s3′含有一個token，其余庫所token數(shù)為0。初始標(biāo)識為節(jié)點(diǎn)1。從節(jié)點(diǎn)40逆向搜索到結(jié)節(jié)1，將其中一條路徑的變遷序列倒序排列，得到一條測試序列：t1t1′t2t2′t6t6′t7t7′。

Figure 5 Example of testing sequence圖5 測試序列舉例

使用上述生成測試序列的方法，對圖3和圖4的IS-IS協(xié)議的CPN 模型的完全狀態(tài)空間進(jìn)行了分析，共生成77個測試序列。

5 實(shí)驗(yàn)及結(jié)論

由測試序列得到測試?yán)?，需要根?jù)測試目的搭建測試環(huán)境，本文測試使用的是Windows XP操作系統(tǒng)，用GNS 3 0.7.2路由模擬軟件模擬Cisco 7200、Cisco 3640等設(shè)備，用網(wǎng)絡(luò)分析工具Wireshark軟件和若干臺PC機(jī)，對IS-IS協(xié)議進(jìn)行了互操作性測試。本文測試環(huán)境的拓?fù)浣Y(jié)構(gòu)圖如圖6所示。

Figure 6 Topology of IS-IS protocol interoperability test environment圖6 IS-IS協(xié)議互操作性測試環(huán)境拓?fù)鋱D

圖6中IUT 表示被測試?yán)?，終端通過路由器的console口對其進(jìn)行配置，在PC 機(jī)上運(yùn)行抓包工具，對IUT 之間交互的信息進(jìn)行檢測。

通過對IS-IS 協(xié)議互操作性測試結(jié)果分析發(fā)現(xiàn)，大部分測試?yán)ㄟ^了測試，但仍有一小部分測試?yán)龥]有通過測試，主要原因是路由器并未實(shí)現(xiàn)相關(guān)功能，或者是對協(xié)議說明中不確定的描述選取了不同的實(shí)現(xiàn)方式。另外，還有一部分測試?yán)驗(yàn)闇y試條件不滿足，如測試設(shè)備不符合要求、內(nèi)部活動不可觀察等原因無法進(jìn)行測試。表3給出了測試結(jié)果。

Table 3 Results of IS-IS protocol interoperability test表3 IS-IS協(xié)議互操作性測試結(jié)果

6 結(jié)束語

通過對IS-IS 協(xié)議ISO10589 和RFC1195 相關(guān)標(biāo)準(zhǔn)的研究，對利用形式描述語言CPN 支持分層體系的IS-IS協(xié)議建立了互操作性測試的模型，包括點(diǎn)對點(diǎn)網(wǎng)絡(luò)和廣播網(wǎng)絡(luò)環(huán)境下子網(wǎng)相關(guān)功能和子網(wǎng)獨(dú)立功能CPN 模型；利用CPN Tools工具，根據(jù)建立的CPN 模型自動生成了完全狀態(tài)空間；通過對完全狀態(tài)空間進(jìn)行分析，再根據(jù)測試目的生成了測試序列，并由測試序列編寫了測試?yán)?；在Windows XP平臺下，使用路由模擬軟件GNS 3模擬Cisco 7200、Cisco 3640等設(shè)備，用得到的測試?yán)龑ζ溥M(jìn)行了互操作性測試，并對測試結(jié)果進(jìn)行了分析。下一步的研究工作，可以對建立的互操作性模型進(jìn)行優(yōu)化：一是在不影響已有覆蓋度的前提下，研究如何減少模型的復(fù)雜度；二是對于模型沒有描述的功能，對其進(jìn)行補(bǔ)充，使其能夠覆蓋更多的協(xié)議功能。

[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）

附中文參考文獻(xiàn)：

[11]呂欣巖，趙保華，周顥.一種動態(tài)協(xié)議一致性測試方法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報，2005，35（3）：338-404.

[12]杭成寶.OSPFv3協(xié)議的互操作性測試研究[D].呼和浩特：內(nèi)蒙古大學(xué)，2009.