独立树的成长（共3篇）
独立树的成长 篇1
0 引言
随着两化融合的深入, 信息化与工业化的融合程度越来越高, 信息化带动工业化的发展。随着互联网络的普及, 工业信息网络逐渐覆盖了各个领域。近年来国防、电网、城市轨交、天气预报等领域均出现庞大计算量的应用问题, 这些问题对互连网络中的各节点性能提出了更高要求。
而现实生活中的计算机网络、移动互联网络及通讯网络等, 常常会由于链路或节点故障而影响网络功能降低甚至失效。目前常用的树型结构[1,2]和多路径结构[3,4]都是平面结构, 以独立生成树[5,6,7,8,9]为基础的网络性能研究是高性能并行计算研究的热点, 这一研究通常应用在立方体、超立方体、扭立方体等方面, 以处理复杂计算问题, 在高性能并行计算方面表现良好。多路径[10,11,12,13,14,15]传输在网络性能优化方面被广泛使用。此本文提出一种基于独立生成树的工业企业网络多路径传输机制。
1 互连网络与独立生成树
1.1 互连网络
并行计算机的内部处理器或处理机, 按照一定方式连接起来, 形成的网络称为多处理器互连网络, 即互连网络[10]。互连网络成为研究并行计算的核心, 对互连网络拓扑结构及其性质研究是并行计算机系统的一个重要课题。常用的互连网络[10], 如树、圈、网格等结构的构造是国内外网络研究的焦点。国内外研究者提出了多种不同的互连网络结构, 如超立方体、树型网络、奇图、偶图、蝶形图等。无论哪种网络结构, 其网络拓扑都可以用图来描述, 在互连网研究中, 网络一般定义为一个图, 其中V为顶点集, E为边集, |。
1.2 独立生成树
运用“图”、“子图”、“路和连通性”等图论知识将企事业单位的局域网网络构建为基础理论研究中的互连图G, 图G上的两棵生成树, 如果具有相同根, 且由根到树中任一顶点的两条路径 (每棵生成树各一条) 为顶点 (边) 不相交路径, 则称这两棵树顶点 (边) 互相独立[9]。若n棵生成树两两顶点 (边) 相互独立, 则称之为n棵顶点 (边) 独立生成树 (Vertex-Independent Spanning Trees) , 简称IST (Edge-Independent Spanning Trees, 简称EIST) 。顶点独立的生成树一定是边独立的生成树, 因此在工程实践的互连网络图上, 构建顶点独立生成树IST。
国内以FAN[9,10,11]为代表的并行与分布式系统研究者针对超立方体等一类互连网络, 通过构建独立生成树 (Independent Spanning Tree, 简称IST) 进行理论研究, 认为超立方体及其变型具有两个共性 (一一对应连接和可递归构造性质) , 提出一一对应连接网络[9 (]Bijective Connection Network, 简称BC网络) 的概念, 并在此基础上系统化地论证了BC网络中独立生成树的存在, 给出独立生成树的可递归构造算法。
2 基于独立生成树的网络多路径传输机制
2.1 网络拓扑构建
无论是信息技术企业还是生产制造等非信息技术服务单位, 其网络信息化应用程度比较高, 都拥有一个比较复杂的企业局域网, 通过分设不同的生产管理或服务部门, 划分不同的子网络, 这里既包括传统的固定网络, 也包含新型的移动互联网络、无线网络等形式。根据企事业单位业务需求、规模大小, 单位局域网的设计规划也有所不同, 但总体采用树型结构设计。运用图论中的“图”、“子图”、“路和连通性”等知识将企事业单位的局域网网络构建为基础理论研究中的互连图, 效果如图1所示。
2.2 构建独立生成树
利用图论中图的连通度、独立生成树的相关理论[16,17], 研究构建的图G1 (V, E) 的连通度n, 这里n=4, 独立生成树递归构造算法 (Uasual Independent Spanning Tree) 如下:
输入维度, 的顶点集合 () .
输出一个图.
步骤1:if, then return=path<0, 1, 12, 13>and=path<0, 13, 12, 1>
步骤2:将树复制成树;将的根节点进行转换;
.
步骤3:构造、、…、、
通过独立生成树递归构造算法, 构建4棵独立生成树IST, , , , , 其中如图2所示:
2.3 构建基于IST的多路径传输机制
2.3.1 基于IST的多路径传输
任意两节点之间传输路径研究。以互连图G1中任意2个节点间的数据传输为例, 这里选择节点0和节点2, 通过独立生成树进行数据包的传送, 网络中有4棵独立生成树, 那么数据包从节点n0到节点n2就可以通过4棵独立生成树进行传递, 如图3所示, 数据包沿着四条不相交的路径从n0节点传送到n2节点, 与传统网络传输数据包相比, 每个节点的数据包接受为原来的4倍, 可有效解决丢包、数据失真问题。
2.3.2 基于IST的多路径传输速度比较
n棵独立生成树产生n条不相交的路径。假设网络中传输的每个数据包d, 利用n条顶点不相交的独立生成树来进行分组传输, 进而提高信息传输速度, 如上图3所示。从单个数据包分包传送角度考量, 每个数据包d可以通过4个IST上进行数据包的传送, 每棵树上只需传送1/4个数据包S, 就可实现从节点n0到节点n2的数据包的传送, 如图4 (a) 所示。传统传送如图4 (b) 所示。理想状态下, 在传送数据包S相同的情况下, IST上传输的时间为t, 普通传输的时间则为4*t, 那么独立生成树上传输的速度比在普通网络中传输的速度提高4倍。
3 结论
本文将高性能并行计算中的独立生成树理论运用到企业网络传输中, 使用IOT可递归构造算法生成独立生成树, 利用独立生成树的不相交理论, 实现网络中任意两节点围绕独立生成树进行多路径传输, 同时分析了基于IST的数据传输与传统传输在传输速度、时间方面的差异, 显示基于独立生成树的多路径传输在传输速度、传输时间上的优势, 为企业网络环境下的数据传输提供一种多路径传输的方法。
摘要：将高性能并行计算中的独立生成树理论应用到企业网络传输中, 首先将企业网络拓扑抽象为互连网络, 提出一种独立生成树可递归构造算法, 生成多棵独立生成树, 进而给出一种基于独立生成树的网络多路径传输方式, 并在传输时间、传输速度上进行了网络传输性能分析, 指出其优势。
关键词：互连图,独立生成树,多路径传输
独立树的成长 篇2
小时候，梧桐树便是我的第二位母亲，是她，助我行走，在粗粗的树干边，在茂密的绿荫里，幼小的我扶着树干一直转圈，于是，就在这转着转着，我摇摇晃晃，第一次不扶东西的走向妈妈，感受独立行走的新鲜感。在梧桐树下，我学会了独立。
再大点，梧桐树便是我的第一位老师，是她，教我懂事，看墨绿的树叶时，听风吹树叶声中，愤怒的我看着窗外沐浴风雨的树，心情渐渐平稳，狂风暴雨下的她是那样淡然，任由风雨的激烈击打，也毫不畏惧的挺直腰板，屹立风雨中。在梧桐树下，我学会了坚强。
长大了，梧桐树便是我的第一位知己，是她，引我开朗，在肥沃的土壤下，在纤细的树枝上，烦闷的我找到了交流的好方法，我开始将一切烦心事都写在纸条上。或用石子系与纸条末端向树枝上抛，直至挂于树枝上不掉下来，或用一个小盒子将纸条全部装起，然后埋在梧桐树下。安置好纸条后，我便会做在梧桐树下闭目，听风把树叶奏的沙沙作响，慢慢的我开始向朋友敞开心扉，慢慢的我便不再烦闷。在梧桐树下，我学会了开朗。
树的成长 篇3
写这个当然得亲自动手试一试了。不过，冬天怎么种树呀?种下的树难道不会给冻死吗?那我日记还怎么写呀?我去问爸爸，爸爸却说冬天的树根是休眠的，在冬天种树不容易伤到树根，容易成活，所以种树一般都选在冬天或初春。原来是这样，我又明白了一点知识!
那么就开始行动吧。说干就干，我叫爸爸去帮我买了棵桃树苗，有我人这么高，比筷子粗点。我拿了树苗来到楼下绿化带的一块比较空旷的土地上，又从地下室里拿来一把小锄头，不费吹灰之力就在上面挖了一个不大不小的坑。可是，好像挖得不够深，于是我便接着往下挖。哎哟，下面的泥土怎么硬得跟砖头似的，叫我怎么挖呀?但不挖不行，我便只能硬着头皮挖。当挖得够深时，我早已累得满头大汗，真想躺下歇一会儿。我又把小桃树小心翼翼地放进坑里，盖上土。可是，它好像一点儿也不乐意，我手一松它就倒了。怎么回事呢?只见它四周的土都松得和面粉一样，怪不得它要倒呢。于是我便使劲地用脚把树根上的泥土跺得严严实实，又端来一盆水，浇在树根上，小桃树终于算是种好了。