0 引言

    随着自动化测试^[1]技术的不断发展，第四代自动化测试技术云测试^[2]应运而生，这就是智能云测试平台^[3，4]。其平台要求将测试资源进行集中化管理，面对多个测试小组进行资源共享，以提高资源利用率。同时，引进测试任务机制来分配资源、监控测试进度以及发布结果。智能云测试平台强调资源的集中化管理，由此对于自动拓扑映射算法^[5]的方法提出了更高的要求。

    拓扑查找算法^[6，7]的实现就是在给定的物理组网中，查找满足逻辑拓扑中所描述的设备和连接关系的物理设备及其连接的映射关系。一般情况下，测试床都有各个测试小组自行组件，根据其被测设备的特点来单独搭建网络。测试床的规模一般都是4～5台，最大规模一般也不超过10台设备，算法扩展性及保密性比较差，整体效率较低，设备数量增加时耗时较长，得到的可选设备范围过大，不支持测试床中包含物理交换机的组网。

    智能云测试平台引入后，自动化拓扑映射算法基于传统ATF框架^[8-11]，主要从设备可选范围、设备的排序和连接映射的处理表等方面进行探讨，优化该算法的实现，使云平台测试效率进一步得到提升。

1 ATF

    ATF(Automation Test Framework)框架提供了丰富的脚本运行和管理接口。在自动拓扑映射模块的支持下，实现了脚本开发的拓扑环境与执行期实际物理组网环境无关。基于ATF框架的脚本主要由拓扑、测试床以及脚本这三类文件组成。其中测试床文件负责描述用户的物理组网环境，拓扑文件用于描述逻辑拓扑环境，脚本文件用于完成实际测试步骤。而拓扑文件与测试床文件之间的映射关系则由自动拓扑映射模块来完成。

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)逻辑拓扑中支持用户设置某台逻辑设备或者端口的映射结果。其可选设备范围有且仅有一个。若其手工映射的物理设备不存在，意味着拓扑映射失败；

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