0 引言

    隨著自動化測試^[1]技術的不斷發展，第四代自動化測試技術云測試^[2]應運而生，這就是智能云測試平臺^[3，4]。其平臺要求將測試資源進行集中化管理，面對多個測試小組進行資源共享，以提高資源利用率。同時，引進測試任務機制來分配資源、監控測試進度以及發布結果。智能云測試平臺強調資源的集中化管理，由此對于自動拓撲映射算法^[5]的方法提出了更高的要求。

    拓撲查找算法^[6，7]的實現就是在給定的物理組網中，查找滿足邏輯拓撲中所描述的設備和連接關系的物理設備及其連接的映射關系。一般情況下，測試床都有各個測試小組自行組件，根據其被測設備的特點來單獨搭建網絡。測試床的規模一般都是4～5臺，最大規模一般也不超過10臺設備，算法擴展性及保密性比較差，整體效率較低，設備數量增加時耗時較長，得到的可選設備范圍過大，不支持測試床中包含物理交換機的組網。

    智能云測試平臺引入后，自動化拓撲映射算法基于傳統ATF框架^[8-11]，主要從設備可選范圍、設備的排序和連接映射的處理表等方面進行探討，優化該算法的實現，使云平臺測試效率進一步得到提升。

1 ATF

    ATF(Automation Test Framework)框架提供了豐富的腳本運行和管理接口。在自動拓撲映射模塊的支持下，實現了腳本開發的拓撲環境與執行期實際物理組網環境無關?；贏TF框架的腳本主要由拓撲、測試床以及腳本這三類文件組成。其中測試床文件負責描述用戶的物理組網環境，拓撲文件用于描述邏輯拓撲環境，腳本文件用于完成實際測試步驟。而拓撲文件與測試床文件之間的映射關系則由自動拓撲映射模塊來完成。

1.1 ATF算法

    假設當前組網中存在物理設備M臺，邏輯拓撲中存在邏輯設備N臺，物理設備的連接關系分別為{M₁，M₂}、{M₁，M₃}…{M_n，M_m}，總連接數為m；邏輯設備連接關系分別為{N₁，N₂}、{N₁，N₃}…總連接數為n；從組網中找出滿足邏輯拓撲的設備及連接關系。

    首先根據設備類型和連接類型，找出各個邏輯設備的可選物理設備范圍，邏輯設備{N₁，N₂…N_n}分別在物理設備范圍{M₁，M₂…M_m}進行映射查找，得到{K₁，K₂…K_n}。其中：K₁、K₂…K_n分別代表每個邏輯設備對應的物理設備可選范圍個數，且K₁、K₂…K_n必然小于等于M。算法復雜度：T(n)=O(M×N)；然后在K₁×K₂…K_n的組合內遍歷，對每個組合組成N²的矩陣，與目標邏輯拓撲N²矩陣進行C次匹配，排除重復的設備組合，檢查邏輯拓撲連接是否匹配其物理設備連接。算法復雜度：

1.2 ATF算法優化

    ATF拓撲查找算法存在明顯的不足，沒有高效的排序依據，邏輯矩陣與物理矩陣中設備連接要進行一一匹配檢查，還需要考慮物理設備包含HUB和物理交換機時的情況，效率極低。所以在可選設備的判斷上，增加設備類型約束檢查，最大限度減小解空間，將輸出的矩陣范圍和邏輯設備列表進行排序，引入到智能云測試自動拓撲映射的算法實現上。

2 自動拓撲映射算法實現機制

2.1 智能云測試平臺

    智能云測試平臺以云為中心，將測試資源集中管理，按需動態分配，同時腳本集中在云端并發分布式執行。拓撲占用過程為智能云測試后臺某任務根據其拓撲以及要運行的物理組網，向拓撲映射模塊發起占用請求。拓撲映射模塊在整個物理組網中空閑資源上查找符合指定拓撲的設備及端口，并修改其占用狀態。拓撲釋放過程為：任務執行完畢后向拓撲映射模塊發起釋放請求，拓撲映射模塊根據其拓撲所映射的設備和端口來釋放相應的物理設備及端口狀態。達到對物理資源統一協調，并對上層應用透明的目的，在核心功能上通過調用自動拓撲映射核心算法提供的接口來進行處理。

2.2 自動拓撲映射核心算法

    設計上將拓撲映射算法的處理邏輯和數據分離。整體可分為三部分：輸入輸出部分、配置信息部分以及核心算法部分，如圖1。

    數據部分采用XML結構^[12]來封裝，以便后續擴展。輸入部分包括邏輯拓撲和測試床，輸出部分主要是涵蓋了設備及其接口的映射結果。配置信息主要包括設備類型樹、接口映射表等信息。核心算法邏輯如圖2所示。

    物理設備類型必須與邏輯設備類型相匹配。由于當前設備類型種類繁多，為便于擴展，將設備類型定義成XML樹型結構，同時封裝外圍接口來對其進行訪問。對于接口來說，存在接口類型以及封裝類型的映射規則。同樣的，將接口類型以及封裝類型定義成XML結構，同時封裝接口來對其進行訪問。邏輯拓撲和測試床信息都是對組網的結構描述，主要包括設備屬性和連接屬性。組網信息同樣采用XML結構來描述，并作為核心算法的輸入，設備節點由XML標簽進行封裝，包含基本屬性和訪問屬性兩大部分。基本屬性域用于描述設備基本屬性，用于拓撲映射算法，訪問屬性主要用于記錄該設備的訪問地址、用戶密碼等信息。該域并不用于拓撲映射算法，但該部分數據使得執行機能夠識別本組網結構，以實現自動地打開組網內包含的各類設備，連接節點用于記錄組網中的所有鏈接。對于邏輯拓撲來說，只包含普通P2P連接以及Hub連接，而對于物理測試床來說，該部分還可描述基于連接設備的連接。

2.3 核心算法初始化

    按照ATF拓撲映射算法，物理組網規模達到一定程度，如50臺設備的組網中獲取邏輯設備個數為8的拓撲，則其可能組合數是個天文數字，遍歷這些組合需要的時間耗費巨大，因此，需要一種更好的方式來完成算法。假設當前輸入的邏輯設備包括3臺設備，分別為DUT1、DUT2、DUT3，設備之間存在4條連接，對應的邏輯組網如圖3所示。

    輸入的物理測試床由6臺設備組成，其中包含一臺物理交換機作為連接設備。在物理組網中，存在5臺設備DEV1、DEV2、DEV3、DEV4、DEV5，其設備類型相同。其中DEV1、DEV2、DEV3分別兩兩相連，DEV2、DEV3、DEV4、DEV5分別與物理交換機設備連接，其對應的組網圖如圖4所示。

2.3.1 可選設備集合

    對于邏輯拓撲中的每個邏輯設備，在物理組網的物理設備中為其確定一個可選設備范圍。通過確定一系列規則對可選設備范圍進行過濾，從而縮小最終解空間。

    (1)邏輯拓撲中支持用戶設置某臺邏輯設備或者端口的映射結果。其可選設備范圍有且僅有一個。若其手工映射的物理設備不存在，意味著拓撲映射失?。?/p>

    (2)設備類型是過濾設備集合的最佳條件之一。在智能云測試系統設備類型豐富，根據不同邏輯拓撲中指定的設備類型，可以縮小其可選設備集合名單；

    (3)由于連接關系映射要求接口個數，能夠滿足映射的物理設備有效接口個數至少大于等于邏輯設備接口個數；

    (4)測試床中的物理設備還包含若干其他屬性，如是否雙主控設備等。所有邏輯設備的可選設備集合確定后，意味著本次拓撲映射的解空間范圍確定。假設DEV1～DEV5的設備類型相同均能夠與其邏輯設備類型相匹配。SW設備類型不能匹配，直接過濾。所以其可選設備集合為DUT1：{DEV2，DEV3}；DUT2：{DEV2，DEV3}；DUT3：{DEV1，DEV2，DEV3，DEV4，DEV5}。物理組網的設備進行編號，從0開始分別代表DEV1、DEV2、DEV3、DEV4、DEV5，最終得到的邏輯拓撲可選設備集合如圖5。

2.3.2 候選分組生成

    從每個可選設備物理設備集合中選取一個物理設備組成候選映射分組，并檢查該候選映射分組與邏輯拓撲是否能夠成功映射，映射失敗時重復上一動作取下一候選映射分組。假設DUT1為高位，DUT3為低位。對于示例邏輯拓撲所得到的可選設備集合，從低位變化，依次獲取的候選映射分組如圖6。

    由拓撲映射結果發現候選映射組合中含有重復設備的組合，顯然不能滿足條件。在實踐中采用進位表的方式來實現對重復分組的高效過濾，減少對映射組合的處理。

2.3.3 分組進位表

    構造一個N2的表，表中每個元素采用數字編號，其中N為邏輯設備個數。對于邏輯設備，包含兩列內容，分別為當前行的進位標記和當前行的最大進位閾值。當前行的最大進位標記默認為0，最大進位閾值為對應可選設備集合大小。對于邏輯拓撲，內容見表1。

    定義低位從行末即行2開始，從低位開始讀取進位表，首次取到{0  0  0}，對應的候選設備組合為{1  1  0}。分析發現該組合存在重復設備，從低位開始遍歷該組合，找到最低位的重復設備編號，由于1和1的重復設備的分組均無效，而是直接對當前最低重復為行1進行進位，得到如表2的進位表。

    讀取該進位表{0  1  0}，其對應的候選設備組合為{1  2  0}。經分析，該組合非重復組合，系統可以確定該分組為合法映射分組，并進行后續連接映射處理。若該組合連接映射失敗，繼續從進位表的最低位向右偏移，得到的進位表見表3。

    讀取當前進位表得到{1  1  0}，對應的候選設備組合為{1  2  1}。分析發現該組合存在重復設備，對行2進行遞增，并持續向上傳遞。同時進位后的地位需要清零。

    與最初的候選設備分組相比，引入進位表后，系統處理的候選設備列表如圖7所示。

    圖7中，雙刪除線組合為進位表直接進位過濾，不需要進入重復設備分析階段。最終進入連接映射階段設備分組數量為6，達到此階段，對于設備映射的分析基本結束。若候選設備分組不存在時，可直接返回拓撲映射失敗。 

3 進位表優化分析

    當P2P連接映射失敗時，必然是某個邏輯設備組間的連接無法在對應的物理P2P連接矩陣(實踐中分別為邏輯拓撲和物理測試床建立P2P連接矩陣，矩陣中的元素代表每組設備間的連接個數，系統只需要每個候選設備分組來構造一個物理P2P連接矩陣)中得到映射結果，從而導致P2P映射失敗。當候選設備組合映射失敗時，正常情況下是從最低位后取下一候選設備組合，若P2P映射失敗的設備組不包含最低位邏輯設備，后續的若干個候選設備組合仍然會在P2P連接映射階段失敗，此時會包含大量重復計算過程。在P2P連接映射失敗后，記錄當前映射失敗的設備組，并找到其對應的進位表的最低位所在行。若該行非實際最低位，則直接從該行位置進位。

    假設邏輯設備組DUT1和DUT2間的兩條連接分別為Serial連接和Ethernet連接；而物理設備組DEV2和DEV3間的連接為Ethernet連接，假設當前取到組合{0  1  0}，即對應的候選設備分組為{1  2  0}。此時的進位表內容見表4。

    進入P2P連接映射階段，對{1  2  0}分組構建連接矩陣進行P2P連接映射。發現邏輯設備組(DUT1，DUT2)間的連接映射失敗，個數吻合但連接類型不匹配。此時檢查該設備組的最低位設備DUT2對應進位表的行1，此時直接對行1進行進位檢查。此時的進位表內容如表5所示。

    引入P2P連接失敗進位后，系統處理的候選設備分組列表如圖8所示。

    以上列表中深色背景加刪除線的部分會直接通過進位法跳過，再次縮小解空間。本優化方法在邏輯拓撲中存在多條連接或者非以太鏈路的情況極為有效。所以根據連接進行進位的實質是提前將設備組間連接映射失敗的情況找出，才能通過進位過濾掉大批與其相關的候選設備組合。設計邏輯設備進位表的行順序時，應該盡量將連接個數多以及存在非以太網連接的設備放到前面，以便構造P2P連接矩陣時能夠盡快從較高位找出映射失敗的設備組。

4 結束語

    本文給出了智能云測試系統自動拓撲映射算法實現的方法，該方法應用到實際的智能云測試系統中，極大縮小了設備映射的解空間和占用到設備所用的時間，時間復雜度明顯降低，對核心算法邏輯結構的每部分進行了優化，支持測試床中包含物理交換機的組網。其中進位表的優化的方法更為容易理解，使智能云測試系統中測試設備得到充分利用，提升了整體的測試效率和可靠性。但在實際的應用中還存在不足之處，腳本調試的過程中修改拓撲后，占用測試床時自動拓撲映射不能靈活映射到新的設備，下一步將進行研究和改進。

參考文獻

[1] 柏瑩.基于NET平臺下Web自動化測試的研究與設計[D].西安：西安電子科技大學，2013.

[2] 李喬，何棟梁，王小林.云測試研究現狀綜述[J].現代計算機，2011（23）：25-30.

[3] LEAH R K，OSSI T，KARI S.Testing in the Cloud：Exploring the practice[J].IEEE Software，2012，29(2)：46-51.

[4] 丁小盼，周浩，賀珊，等.基于OpenStack的云測試平臺及其性能分析研究[J].軟件學報，2015（1）：6-10.

[5] 陳福，楊家海，楊揚.網絡拓撲發現新算法及其實現[J].電子學報，2008（8）：1620-1625.

[6] 姜譽，方濱興，胡銘曾.多點探測Internet路由器級拓撲[J].電信科學，2004（9）：12-17.

[7] 姚杰，程光鈞，李浩，等.基于數據驅動自動化測試框架研究和實現[J].工業控制計算機，2013，26(7)：67-69.

[8] 朱菊，王志堅，楊雪，等.基于數據驅動的軟件自動化測試框架[J].計算機技術與發展，2006，16(5)：68-70.

[9] 接卉，蘭雨晴，駱沛，等.一種關鍵字驅動的自動化測試框架[J].計算機應用研究，2009，26(3)：927-929.

[10] 張磊，王曉軍.基于STAF框架下的自動化測試[J].計算機技術與發展，2010，3（3）：117-119.

[11] 陳波，洪曉光.基于改進樹狀結構的XML文檔簡單路徑查詢多線程實現[C].中國數據庫學術會議，2004：382-387.

作者信息:

王  亮1，韓連鋼2，謝錫海1

(1.西安郵電大學 通信與信息工程學院，陜西 西安710061；2.西安航天動力技術研究所，陜西 西安710025）