李焕(咸阳职业技术学院，咸阳 712000)

基于数据通信的网络多拓扑路由算法研究与分析

李焕
(咸阳职业技术学院，咸阳 712000)

近年来计算机技术的发展使得多拓扑路由已成为非常重要和流行的问题。在网络地理事件中，路由流失发生后即使稳定了也会导致产生的影响。对这项工作涉及的一些问题提出了一套算法，使用多拓扑路由(MTR)预测大的地理事件和切换到虚拟拓扑结构，减少路由的变化可能会导致连接到一个新的链路状态和最短路径树的建立。使用多拓扑路由，已经表明，在地理事件中被丢弃的连接的数目可以显着降低，从而降低了对网络的剩余部分的影响。

多拓扑路由； 虚拟拓扑结构； 链路状态

0 引言

分布式计算系统已经成为信息技术发展的重要方面。基本上有两类网络拓扑：物理拓扑结构和逻辑拓扑结构。物理网络拓扑结构强调与系统相关的硬件，包括工作站、远程终端、服务器以及相关的资产之间的布线[1]。相反，逻辑网络拓扑强调节点之间的数据流的表示。物理拓扑定义系统是物理连接的。这意味着通过实际的电缆传输数据的计算机网络上的装置的排列。

1 几种拓扑结构

这8种基本的拓扑结构。下面对这些拓扑结构进行简单的描述。基础拓扑结构不再赘述，拓扑结构大致有点对点型、总线型、星型、环型、网状型、树型、混合型、菊花链式。

星型网络中的各节点通过点到点的方式连接到一个中央节点上[2]，如图1所示。

由该中央节点向目的节点传送信息。网络中所有链路都正常工作时网络才保持连通，即网络可靠性，如式(1)。

RCstar(N)=(e-λt)N-1=e-(N-1)λt

(1)

在环型拓扑中，所有的节点或设备都相互连接成一个圆，如图2所示。

图1 星型拓扑

图2 环型拓扑

各节点通过环路接口连在一条首尾相连的闭合环型通信线路中，环路中各节点地位相同，环路上任何节点均可请求发送信息，请求一旦被批准，便可以向环路发送信息[3]。数据从一个设备传递到环布局的下一个，直到它到达目的节点。使公共传输电缆组成环形连接，数据在环路中只能单向传输[5]。对于有N个节点的环形拓扑结构，链路数为N，节点的度为2，对于模块化也比较方便，网络结构对称[4]。对于链路组成的环型网络，网络的可靠性，如式(2)。

RCring(N)=(e-λt)N=e-Nλt

(2)

图3 网状网络

当网络被广泛传播并被分成许多分支时，树结构最适合，是一种分级结构，如图4所示。

图4 树

在树型结构的网络中，任意两个节点之间不产生回路，每条通路都支持双向传输。这种结构的特点是扩充方便、灵活，成本低，易推广，适合于分主次或分等级的层次型管理系统[8]。即网络可靠性，如式(3)。

RCtree(N)=(e-λt)N-1=e-(N-1)λt

(3)

混合型拓扑结构的网络拓扑结构，如图5所示。

图5 混合型拓扑结构

由一个或多个互连的两个或两个以上的网络是基于不同的物理拓扑结构或类型的网络拓扑结构，由一个或多个互连的两个或两个以上的网络是基于相同的物理拓扑结构[7]，但是，从这样的互连产生的网络的物理拓扑结构不符合互连网络的原始物理拓扑的定义。一个主要的缺点是通常比其他网络更昂贵，因为它利用了其组件拓扑结构的特点。它比其他类型的网络拓扑结构需要更多布线之间的硬件设备。混合网络很难建立和排除故障。

一个菊花链式网络拓扑结构是所有的设备都是以链状或环形的方式连接的，如图6所示。

图6 菊花链拓扑

主控制器连接到从设备，这反过来又连接到另一从设备，连接到另一个从设备，等等。如果该环在某一特定链路上断开，则该传输可以通过反向路径发送，从而确保所有节点在一次故障的情况下总是连接在一起。如果你想在链或环中添加装置，网络将在过程中下降。这些网络的布线一般都是放在开放的空间，因此可能更容易受到意外断开了。

更具体地说，我们使用多拓扑路由(MTR)，是为了防止与地理相关的故障问题。简单地说，在其框架中，我们创建了一系列的拓扑结构，可能是有用的，在网络中用于潜在的破坏性事件处理。我们可以通过增加链接权重在特定的地理区域的网络中。总的效果是将最短路径树(SPT)远离受影响地区的拓扑。了解链路状态路由协议中的链路或节点故障时发生什么是必要的。首先，检测链路或节点状态的变化(如中断)发生。其次，受影响的路由器将创建链路状态广播LSA发送给他们的邻居。此信息将被淹没在路由区域，直到所有路由器具有相同的链路状态数据库[9]。如果数据库发生变化，每个路由器根据新的数据库独立地计算所有节点的最短路径树。

如果发生多个中断，可能会发生一些事情，上述恢复过程有负面影响。首先，涉及多个链接，链接可能会表现出重复和间歇性故障导致链接的拓扑行为[10]。这种行为通常会导致频繁的路由变化，导致路由不稳定。如果中断是非常重要的，多个LSA将淹没在网络造成的最短路径优先(SPF)计算每个节点的重复运行[11]。这是通常被称为SPF节流，其可以导致较长的收敛时间[12]。

调制信号就是把消息信号加载到高频电磁波信号上，高频电磁波利于传播而且损耗小，该信号称为载波信号。载波随着消息信号改变去改变，即调节载波的幅度、频率或相位。调制后的信号又称为已调信号，通过调制，消息信号的频谱被搬移到了更高的频段上[1]。

2 拓扑生成算法

由于有多种拓扑结构，包括覆盖多拓扑路由方法(gcMTR)和具体目标的多拓扑路由的方法(gtMTR)。在gcMTR，N的拓扑结构被创建，每个可以避免网络中的地理区域。gtMTR方法使用现有的知识对特定事件建立一个拓扑的目标，它是一个特定的地理区域。这里使用的符号是：G(V,E)：节点V和边E(链路)的网络图。

N：gcMTR或gtMTR所需的拓扑数。

Vi：脆弱区中心i

Ti：MTR拓扑i

Dij：Vi与Ti链路上最近点之间的距离j

Wij：对于Ti链路j上的链路权重

算法1(gcMTR)创建一组拓扑结构，提供覆盖整个网络防各种地理事件。避免基于覆盖计划，可以配置一个特定的网络。算法2(gtMTR)利用知识对特定事件类型创建专门为某个事件的拓扑结构。避免基于自定义预定义的地理事件的位置列表。

为了实现快速切换过程中的事件，它将需要路由器维护，可用于所有的拓扑结构[14]。为了最大限度地减少可以使用在路由器处理的方法。不使用的拓扑结构的计算应优先低于使用的拓扑结构。

有3个拓扑结构来证明的拓扑生成算法如图7所示。第一个是一个5×5网格，这是用于说明目的。图7a显示5×5网格拓扑(默认所有链接的权重的一个)。绿色显示链接权重。SPT源节点为4。当地理事件发生时，我们假设一个区域中的几个节点被删除。这可能在以一个最小的方式影响默认的SPT，如图7b所示；路由节点20和节点21时的影响，10，11，15，16被删除。图7c，拓扑结构产生的脆弱点Vi=(22, 57)，半径为R=20。拓扑结构将脆弱点移动到树的叶子上。然而，当节点1，2，6，7删除，图7d表明路由到10，11，12，15，16，17，20，21，22是由SPT变化影响的。显然，相对于SPT的主要部分的漏洞是位置的影响。图7e中显示的5×5网格与一个脆弱点生成的拓扑结构Vi=(40，24)，半径为R=20。

a 默认拓扑

b 网络与周围的节点(22，57)与半径r=20删除

c 拓扑创建Vi=(22，57)与半径R=20

d 网络与周围的节点(40，24)与半径R=20删除

e 拓扑创建与Vi=(40，24)与半径R=20图7 SPT源= 4，SPT的链接是固体，链接权重显示

使用选定的拓扑结构，如表1所示。类似于实际事件的改进。一般来说，值得注意的是，如果事件断开连接的是默认SPT的重要组成部分，改善均显著优于如果项目位于SPT的叶子。事件2破坏了默认的路径。被选中的拓扑路由连接这方面改善断开服务的数量显着。事件中的平均路径距离，如表2所示。默认拓扑中的距离是最短的，在事件或选定拓扑中有更多的选项。

表1 在连接中丢失概率事件

表2 平均路径长度

3 ATT L1网络中评估

在ATT L1网络中，一系列的8种拓扑结构都是以相似的方式作为ATT L1网络覆盖的计划。如图8所示。图8a显示了8个地点的网格(Vi)和半径(Ri)用于创建覆盖拓扑结构。图8b显示ATT L1网络拓扑(默认所有链接的权重= 1)。图8c显示事件后的SPT。图8d通过拓扑结构的选择，而源显示Vi=(-92，33)，半径为3.5。图8e显示在事件4下源的SPT。在此事件下1，3地区的节点和链接被删除。图8f，通过拓扑结构的选择源创建的SPT，显示Vi=(-92，41)，半径为3.5。

如表3所示。使用事件1的选定拓扑的实际连接的百分比增加。发生这种情况有两个原因。首先，选择的拓扑结构与该事件的面积不匹配。拓扑结构选择(见图8a位置(-92,33))为中心的南部明显为实际事件的中心。第二，事件本身并没有减少两大分支的SPT，穿越网络从东到西。该拓扑实际上重新路由连接到事件发生区域的北部。这可以在图8c图8d观察到。

a 拓扑覆盖计划

b 默认的拓扑结构

c 事件= 1，位置(-89.5 36.6)，半径为3.8

d 所选择的拓扑Vi=(-92，33)，半径为3.5

e 事件4，位置=(-90，40)，半径为3.5

f 所选择的拓扑Vi=(-92，41)，半径为3.5图8 ATT L1网络，SPT的链接是固体，链接权重显示

同时在表V，值得注意的是，SPT的一个主要分支，显著改善了通过切换到选定的拓扑期间。丢弃的连接数从20.5%更改为1.2%。其他两个事件也表现出显着的改善。在较大的网络的评估过程中，它似乎所选择的拓扑结构比在事件发生时的脆弱点更倾向于进一步路由周围的流量。路径长度在选定拓扑中稍长，如表4所示。

当事件大小与拓扑大小不一致时，使用默认拓扑和选定拓扑的连接百分比下降[13]。更值得探究的是，当事件大小小于拓扑半径时，性能与匹配的事件大小没有大的不同。然而，当事件的大小显着大于拓扑半径，性能迅速退化。当事件小于拓扑半径时，拓扑有效地绕过事件。但是，当事件显着大于拓扑半径，拓扑结构不路由交通从事件的适当距离。拓扑结构，性能下降接近默认拓扑结构的性能[15]。

表3 事件中连接丢失的概率

表4 平均路径长度

4 总结

在本文中，被认为是不同类型的拓扑结构的性能和研究。多拓扑路由(MTR)可以用来提高性能，这些改进是通过保持额外的拓扑结构，通过增加网络中的特定区域的链路权重创建。这具有推动该区域周围最短路径树的效果，限制节点在该区域突然失去服务时被断开的连接量。可以创建多个拓扑来预测网络中的多个事件。当拓扑结构被选中时，明显的地理事件已经发生。移至新的SPT导致事件的影响达到最小化。从本质上讲，在地理事件中网络流失的数量将会减少。提出3种算法。两种算法gcMTR和gtMTR提供的方法来创建的拓扑结构在网络广覆盖的方法和有针对性的方法，可以用来预测一个特定的事件。第三算法指定了一个方法来检测一个地理事件，并选择一个拓扑结构使用。

我们计划实施这些算法模拟，以评估他们如何在一个更逼真的设置中执行。生成高效的覆盖拓扑结构，优化的大小，数量和位置的拓扑结构是必要的。本文提供了一些处理拓扑相关问题的分析方法的知识。在本讨论中所涉及的技术可以适应相关的网络应用。这项研究工作也可以进一步扩展。

[1] Banerjee S, Jain V, Shah S. Regular multihop logical topologies for lightwave networks[J]. Communications Surveys amp; Tutorials. IEEE, 1999，2(1)：2-18.

[2] Cem Ersoy, Shivendra Pan War. Topological Design of Interconnected LAN-MAN Networks[C]. IEEE INFOCO, 1992： 2260-2269.

[3] F Backes. Transparent Bridges for Interconnection of IEEE 802 LANs[C]. IEEE Network, 1988：5-9.

[4] Li Chiou Chen. The Impact of Countermeasure Propagation on the Prevalence of Computer Viruses[J]. IEEE Transactions on Systems, MAN, and Cybernetics(PartB), 2004,34(2)：823-833.

[5] Geon Yoon, Dae Hyun Kwan, Soon Chang Kwon, et al.Ring Topology-based Redundency Ethernet for Industrial Network[C]. SICE-ICASE International Joint Conference, 2006：1404-1407.

[6] Nicholas F. Maxemchuk, Ram Krishnan. A Comparison of Linear and Mesh Technologies——DQDB and Manhattan Street Network[J]. IEEE Journal on Selected Areas in Communications, 1993，11(8)：.

[7] Bannister J A, Fratta L, Gerla M. Topological design of the wavelength-division optical network[C]. INFOCOM, Ninth Annual Joint Conference of the IEEE Computer and Communication Societies. 1990：1005-1013.

[8] C M Harris. Fundamentals of Queueing Theory[M]. NJ: John Wiley amp; Sons, 2008：.

[9] D Bertsekas, R Gallager. Data Networks(2nd ed)[M]. NJ: Prentice-Hall, 1992.

[10] Wikipedia.Network topology, the free encyclopedia[EB/OL]. 2008.

[11] A Kvalbein, A Hansen, T Cicic, S, et al. Fast IP network recovery using multiple routing confifigurations[C]. INFOCOM 2006. 2006：1-11.

[12] S Orlowski, R Wessaly, M. Piro, et al. SNDlib 1.0-survivable network design library[J]. Networks, 2010，55(3)：276-286.

[13] M S S Bryant, S. Previdi. IP fast reroute using not-via addresses[R].Working Draft, IETF Secretariat, Internet-Draft.

[14] M Shand, S Bryant. IP fast reroute framework[EB/OL]. (2010-01-30). http://www.rfc-editor.org/rfc/rfc5714.txt.

[15] T Cicic, A Hansen, A Kvalbein, M Hartmann, et al. Relaxed multiple routing confifigurations: IP fast reroute for single and correlated failures[J]. IEEE Transactions on Network and Service Management, 2009，6(1)；1-14.

AStudyandAnalysisonComputerNetworkMulti-TopologyRoutingAlgorithmforDataCommunication

Li Huan
(Xianyang Vocational Techical College, Xianyang 712000)

In recent days for computing, multi-topology routing has become very important and popular. During large geographic events in networks, the routing churn that occurs has been shown to cause signifificant impacts the following events, after stabilization. This work addresses some of those problems by proposing a set of algorithms that use multi-topology routing (MTR) to predict large geographic events and switch to virtual topologies. It can reduce the impact of routing changes that can result in dropped connections until a new link state, and the shortest path trees can be established. Using multi-topology routing, we have been able to show that the number of connections that are dropped during a geographic event can be reduced signifificantly, which reduces the impact to the remaining part of the network.

Multi-Topology Routing; Virtual Topologies; Link State

李 焕(1980-)，女，陕西富平人，硕士，讲师。研究方向：计算机网络、计算机应用技术。

1007-757X(2017)11-0056-05

TP393

A

2017.04.28)