基于独立生成树的网络多路径传输方法研究

刘静　樊建席

摘要：将高性能并行计算中的独立生成树理论应用到企业网络传输中，首先将企业网络拓扑抽象为互连网络提出一种独立生成树可递归构造算法，生成多棵独立生成树，进而给出一种基于独立生成树的网络多路径传输方式并在传输时间、传输速度上进行了网络传输性能分析，指出其优势。

关键词：互连图；独立生成树；多路径传输

中图分类号：TP391.3 文献标识码：A DOI：10.3969/j.issn.1003-6970.2016.04.007

0 引言

随着两化融合的深入，信息化与工业化的融合程度越来越高，信息化带动工业化的发展。随着互联网络的普及，工业信息网络逐渐覆盖了各个领域。近年来国防、电网、城市轨交、天气预报等领域均出现庞大计算量的应用问题，这些问题对互连网络中的各节点性能提出了更高要求。

而现实生活中的计算机网络、移动互联网络及通讯网络等，常常会由于链路或节点故障而影响网络功能降低甚至失效。目前常用的树型结构和多路径结构都是平面结构，以独立生成树为基础的网络性能研究是高性能并行计算研究的热点，这一研究通常应用在立方体、超立方体、扭立方体等方面，以处理复杂计算问题，在高性能并行计算方面表现良好。多路径传输在网络性能优化方面被广泛使用。此本文提出一种基于独立生成树的工业企业网络多路径传输机制。

1 互连网络与独立生成树

1.1 互连网络

并行计算机的内部处理器或处理机，按照一定方式连接起来，形成的网络称为多处理器互连网络，即互连网。互连网络成为研究并行计算的核心，对互连网络拓扑结构及其性质研究是并行计算机系统的一个重要课题。常用的互连网络，如树、圈、网格等结构的构造是国内外网络研究的焦点。国内外研究者提出了多种不同的互连网络结构，如超立方体、树型网络、奇图、偶图、蝶形图等。无论哪种网络结构，其网络拓扑都可以用图来描述，在互连网研究中，网络一般定义为一个图，其中V为顶点集，E为边集，I。

1.2 独立生成树

运用“图”、“子图”、“路和连通性”等图论知识将企事业单位的局域网网络构建为基础理论研究中的互连图G，图G上的两棵生成树，如果具有相同根，且由根到树中任一顶点的两条路径（每棵生成树各一条）为顶点（边）不相交路径，则称这两棵树顶点（边）互相独立。若n棵生成树两两顶点（边）相互独立，则称之为n棵顶点（边）独立生成树（Vertex-Independent Spanning Trees），简称IST（Edge-Independent Spanning Trees，简称EIST）。顶点独立的生成树一定是边独立的生成树，因此在工程实践的互连网络图上，构建顶点独立生成树IST。

国内以FAN为代表的并行与分布式系统研究者针对超立方体等一类互连网络，通过构建独立生成树（Independent Spanning Tree，简称IST）进行理论研究，认为超立方体及其变型具有两个共性（一一对应连接和可递归构造性质），提出一一对应连接网络（Biiective Connection Network，简称BC网络）的概念，并在此基础上系统化地论证了BC网络中独立生成树的存在，给出独立生成树的可递归构造算法。

2 基于独立生成树的网络多路径传输机制

2.1 网络拓扑构建

无论是信息技术企业还是生产制造等非信息技术服务单位，其网络信息化应用程度比较高，都拥有一个比较复杂的企业局域网，通过分设不同的生产管理或服务部门，划分不同的子网络，这里既包括传统的固定网络，也包含新型的移动互联网络、无线网络等形式。根据企事业单位业务需求、规模大小，单位局域网的设计规划也有所不同，但总体采用树型结构设计。运用图论中的“图”、“子图”、“路和连通性”等知识将企事业单位的局域网网络构建为基础理论研究中的互连图，效果如图l所示。

2.2 构建独立生成树

利用图论中图的连通度、独立生成树的相关理论，研究构建的图Gl（V，E）的连通度n，这里n=4，独立生成树递归构造算法（uasual Independent Span-ning Tree）如下：

输入维度，的顶点集合（）.

输出一个图.

步骤1：if，then return=path<0，1，12，13>and=path<0，13，12，1>

else call，.

步骤2：将树复制成树：将的根节点进行转换；

步骤3：构造、、…、、

for t（）do

对，；

对，，

end for

结束

通过独立生成树递归构造算法，构建4棵独立生成树IST，，， ，，其中如图2所示：

2.3 构建基于IST的多路径传输机制

2.3.1 基于IST的多路径传输

任意两节点之间传输路径研究。以互连图Gl中任意2个节点间的数据传输为例，这里选择节点0和节点2，通过独立生成树进行数据包的传送，网络中有4棵独立生成树，那么数据包从节点n₀到节点n₂就可以通过4棵独立生成树进行传递，如图3所示，数据包沿着四条不相交的路径从n₀节点传送到n₂节点，与传统网络传输数据包相比，每个节点的数据包接受为原来的4倍，可有效解决丢包、数据失真问题。

2.3.2 基于IST的多路径传输速度比较

n棵独立生成树产生n条不相交的路径。假设网络中传输的每个数据包d，利用n条顶点不相交的独立生成树来进行分组传输，进而提高信息传输速度，如上图3所示。从单个数据包分包传送角度考量，每个数据包d可以通过4个IST上进行数据包的传送，每棵树上只需传送1/4个数据包s，就可实现从节点n₀到节点n₂的数据包的传送，如图4（a）所示。传统传送如图4（b）所示。理想状态下，在传送数据包s相同的情况下，IST上传输的时间为t，普通传输的时间则为4*t，那么独立生成树上传输的速度比在普通网络中传输的速度提高4倍。

3 结论

本文将高性能并行计算中的独立生成树理论运用到企业网络传输中，使用IOT可递归构造算法生成独立生成树，利用独立生成树的不相交理论，实现网络中任意两节点围绕独立生成树进行多路径传输，同时分析了基于IST的数据传输与传统传输在传输速度、时间方面的差异，显示基于独立生成树的多路径传输在传输速度、传输时间上的优势，为企业网络环境下的数据传输提供一种多路径传输的方法。