针对复杂多环网络拓扑的路由改进算法

荆 霞，周子韬，王永利

（1.南京审计大学 信息工程学院，南京 211899；2.南京理工大学 计算机科学与工程学院，南京 210014）

0 概述

随着网络技术的发展，一些流行网站的访问量呈现飞速增长的趋势，如何提供高质量、高效率及更安全稳定的服务已成为运营商必须要面对的问题［1-3］。环形结构网络可以提供更好的本地网络连接体验，能够满足生存性和安全性的要求，因此被应用于很多场景。目前网络运营商为大用户提供的光纤接入网，例如电力、电信、有线电视等，其主干网大多以环型网络的方式提供服务。此外，令牌环网络（Token-Ring Network，TRN）、光同步数字传输网（Synchronous Digital Hierarchy，SDH）［4］、局域网（Local Area Network，LAN）［5］和波分复用（Wavelength Division Multiplexing，WDM）［6-7］光传送网均离不开环网结构。

环网因其结构特点存在自身缺陷，环形结构网络传输效率低、延迟高，当节点或链路发生故障时，会变得不可靠、可扩展性差。许多基于环网结构的拓扑改进也因此被提出。WILLIAM 等［8］研究了4 种增强的环网络，这些网络以环网结构为基础，在仅适度增加结构复杂性的基础上，显著提高了环作为通信媒介的效率。文献［9］提出了节点在同心多环覆盖网络上进行逻辑互连的网络模型，不仅描述了同心多环网络覆盖拓扑，也提出了节点加入和离开方案，以及路由和资源查找算法。由于基于环的网络覆盖对于组通信具有固有可靠性和单一容错的特点，文献［10］提出利用改进的多环网络结构来实现安全和可扩展的群组通信。

为解决环网结构网络传输效率低、延迟高的问题，近年来，对环网的研究也从结构改进转移到在不同场景下环网路由算法的改进。ABRAHAM 等［4］研究了放置在环中有d个出度n个节点的贪婪路由，将路由复杂度从降低到。文献［11］提出基于主从结构的弦环网路由算法，该算法根据区域组成多个子环，在子环中推选出处理能力强的节点为超节点并让其彼此相连构成主环，从而减少路由跳数，提高路由延时性能。文献［12］将增强环网中的弦环网应用到分布式网络中，提出改进路由算法，使该网络结构能更好地适应大规模分布式系统。为解决如何在网络的任意节点之间有效地为消息寻路的核心问题，文献［13］提出一种基于增强环网的贪心路由算法。文献［14］通过添加虚节点和虚拟弧扩充网络，将原有问题转换为混合整数规划问题并提出一种启发式算法，将其作为WDM 环网中的路由算法，实验结果证明该算法效果显著。

上述文献是对单环网和特定场景下路由算法的研究，对于规模大、环数多、连接方式多样化的复杂多环网络仍缺乏性能优良的路由算法。本文在弦环网结构的启发下，提出一种面向复杂多环网的路由改进算法PRR。通过构建多种增强环网结构模型，探究其增强的原子操作及由增强环网结构衍生的复杂多环网络定义。同时，通过分析多环网络拓扑的特点，将网络中节点划分为通信节点和环内节点，并令PRR 算法只在节点数和边数较少的单个环以及预处理后的有向图上进行，从而避免算法过于复杂，提高算法运算速度。

1 增强环网结构模型

基于环型结构的网络有许多优点，如具有优良的可靠性及安全性、路由控制软件简单易操作等［20］，但也有明显的缺点。由于信息在环路中是串行地穿过各个节点，当环中节点过多时，势必影响信息在节点中的传输速率，使网络的响应时间延长。随着环上节点数量的增加，该问题越发明显。目前解决方法主要有2 种：一是将原有的大环拆成多个互连在一起的小环，这些环要么处于同一级，要么互连成1 个多层次结构的环，如此可以改善伸缩性；二是在环的内部或外部为不直接相连接的节点之间添加“弦”或者“弧”。这些方法也是增强环网结构原子操作的核心。

拓扑直径可定义为任意2 个节点之间最短距离的最大值，而平均直径定义为任意2 个节点之间最短距离的平均值。在网络拓扑尤其是环网中用直径去度量传输延迟。

1.1 增强环网结构

针对单环网的缺陷，研究人员提出多种改进环网结构，这些改进后的环网也被称为增强环网［8］。其中应用广泛的有以下3 种：

1）弦环网

弦环网指对于给定的N(N≥6)个节点的环网CHRm4(N，E，h1，h2)，其中：N、E分别表示节点与边值；h1、h2表示弦的连接值，且h1、h2必须为正整数且为偶数。对于任意的偶数节点，，节点i2k={0，2，…，N-2}会额外与节点i_(2k+h1) modN和节点i_(2k-h1) modN连接形成环中的弦链路。对于任意的奇数节点，节点i2k+1={1，3，…，N-1}会额外与节 点i_(2k+1+h2) modN和节点i_(2k+1-h2) modN连接形成环中其余部分的弦链路。对于CHRm4 中的N、h1、h2有gcd(N、h1、h2)=2。

弦环网通过添加非直接相连的节点与节点之间的链路来增强环网，可以将这条新的链路视为环的弦。弦环是最早提出的并行架构的成本效益互连网络之一，弦环网的优点主要在于当环内1 个节点出现故障时不会导致整个环网都瘫痪，且弦环网可以适当减小环形网络的直径。弦环网在分布式网络中有着重要的应用，图1（a）是四度弦环网CHRm4(10，1，2，4)的拓扑图。

2）边缘互连多环网

环与环之间通过环的边缘（即连续的多个节点）连接从而形成边缘互连多环网。每个环均可与其他多个环通过该方式连接且可以递归发生，这样的网络可以形成“环树”。“环树”的深度（环的递归的级别数）决定了路由开销的程度，深度值越大，路由的决策节点数量更多，路由开销则更高。同时，当网络结构的深度越大时，路径选择则更加多样化，该网络对边缘节点故障拥有更高的容忍度。边缘互连多环网在一定程度上与网格状网络类似，边缘互连多环网更加自由，每个节点的度数不必严格要求相同且可以是网格状网络的子图。边缘互连多环网如图1（b）所示。在实践中，边缘互连多环网常应用在SONET的通信中。

3）分层环网

环与环之间通过单个节点连接形成分层环网。与边缘互连多环网类似，环的连接也可以递归发生。因此，分层环网也可形成“环树”，其深度同样是重要的结构特征。

图1（c）为分层环网的示意图。边缘互连多环网和分层环网之间的主要区别在于边缘互连多环网中共享多个节点，而在分层环网中共享1 个节点。因此，分层环网也可以作为边缘互连多环网的子图。

图1 不同类型增强环网结构Fig.1 Different types of enhanced ring network structure

1.2 多环网络拓扑

多环网络是增强环网中重要的一部分。在拓扑上，多环网络可以分为3 类：1）环共享节点，其中包括单节点和多节点，连续的多节点又可以称为共享边；2）桥连接环网，也分为单桥、多桥；3）多环混合连接。多环网络拓扑如图2 所示。

图2 多环网络拓扑Fig.2 Multi-ring network topology

本文所研究的复杂多环网络拓扑，“复杂”主要表现在3 方面：1）网络中环与环的连接方式复杂，可能通过节点、边，也可能通过桥来连接；2）网络拓扑规模复杂；3）需要解决大批量大规模不同业务需求。

复杂多环网络拓扑的研究意义在于：

1）多环拓扑基于环，环可以通过带宽进行扩展，因为节点的工作负载与节点总数无关，所以这种复杂网络拓适用在某些真实网络场景下。

2）单环的主要缺点是对大量节点的高度依赖性，一个节点的故障可能会导致所有业务丢失，且平均延迟与节点总数成比例。将单个环转换成多环可以很好地改善这种情况，但这些都要基于一个良好的路由算法。在多环混合连接拓扑中，将功能强大的节点进行环与环之间的通信，吞吐量不再受功能较弱的节点限制。

3）环之间通过共享环上单个或多个节点连接可以满足场景的实际需求，减少网络的节点数。而通过“桥”连接可以减少环与环之间的“耦合度”，“多桥”可以在桥之间起到互相保护的作用，1 个桥出现故障，业务可以通过其他桥继续正常传输。

4）不同结构的增强环网可转化成相应的多环结构。文献［2］中给出了详细的证明。因此，本文研究复杂多环网络拓扑下的路由算法对其他结构的环网路由算法均有借鉴作用，甚至可以应用在环网中。

1.3 多环网络拓扑定义

为更准确、清晰地描述本文算法，对本文所研究的多环网络拓扑给出以下定义：

1）多环网络。由N个节点所构成的多环网络MR(ZN，EN，RD，BC)，节点集ZN={0，1，…，N-1}，边集EN={{(i，i+1modN)|i∈ZN}∪BC}。RD={R1，R2，…，Rd}表示MR中包含的d个环，BC表示网络中的桥，以边的形式存储，表现为

2）环连接。环Ri(ZV，EV，CR) 由节点集ZV、边集EV和与这个环通过共享节点连接的环CR。对于含有j个节点的环，环上的边为，每一组数据表示与该环Vi连接的环信息，m、n分别表示与之相连的环为Rm、Rn，共享的节点为。

3）通信节点。环与环之间的共享节点以及桥上的节点称为通信节点。环内的其他节点，及不参与到与其他环交互和通信的节点，统称为非通信节点或环内节点。

增强环网的提出，使环网结构的网络更加灵活，拥有更好的伸缩性，在响应时间和网络延迟上也有一定程度的改善。然而，环网结构本身的传输效率低的缺点仍有待解决，如何针对不同结构的环网提出相应的路由算法，从而提升传输效率仍是一个重要的课题，也是本文的研究主题。

2 PRR 路由改进算法

环网拓扑在搜寻节点过程中每次都必须从当前节点沿着顺时针或逆时针遍历环上的其余节点，直到遇到通信节点才可以进入下一个环中进行遍历。因此，搜索空间和时间往往很大，延迟和延迟抖动更高。本算法的思想核心是“分而治之”，在原有的拓扑识别通信节点基础上构建新的拓扑，并在该拓扑中执行还原算法以保证网络不失真。算法流程如图3所示。

图3 改进路由算法的流程Fig.3 Procedure of improved routing algorithm

2.1 预处理

环网中传统路由算法先从当前节点搜寻到该环上的通信节点，之后从其节点搜寻到其他环，直到搜寻到包含目标节点的环，在该环上搜寻到目标节点。其过程由3 部分组成：从环上的环内节点到通信节点，从一个环搜寻到另一个环即通信节点到通信节点，以及从一个环上的通信节点到环内节点。在复杂多环网中，第2 部分的内容占据路由主要部分。因此，本文算法将通信节点到通信节点的路径通过预处理作为缓存，从而避免每次业务都需重新计算一次。

预处理算法的目的是除去整个网络拓扑图的冗余节点，主要操作是将环内节点剥离，同时构建一个新的预处理拓扑图G′并缓存下来以便后续调用数据，步骤如下：

1）遍历所有环的节点度数，如果节点的度数大于2，那么可以认定其为非环内节点（通信节点）。将每个环的通信节点加入到通信节点集（CNi→CN）

2）构建新的预处理拓扑图G′，将通信节点集中的节点加入G′，即CN→G′。

3）对于同一环内的通信节点，两两节点构成边，利用Dijkstra 算法计算他们之间的最短距离并将边加入到G′。算法过程如算法1 所示。

算法1Create new Preprocessing topologyG′（CPG）

“最短路径的最优子结构性质”指对于G中的路由ρ由函数ρ=V×V→E*，其中E*表示图G中所有可能的路径集合。当对于任意的x∈V，y∈V，且ρ(x，y)是最短路径时，则称ρ是最短路径的路由。如果图中的路由是连续的，对于路由ρ(x，y)=x…u1…um…y是节点对(x，y)最短路径的路由，那么ρ(u1，um)=u1，u2，…，um也是节点对(u1，um)的最短路径路由。

“最短路径代价不失真”指在线性时间内，如果原拓扑与预处理后的拓扑得到的两通信节点间的最短路径分别为p1、p2，其代价分别为c1、c2，那么有c1=c2且对于任意节点ν，若ν∈p1则ν∈p2。

证明如下：设在原拓扑中路由获得的最短路径p1由节点集{ν1，ν2，…，νi}组成，其中存在通信节点集{ν1，νj，…，νi}，源溯节点必为通信节点。若路径中不存在除源溯节点外其他通信节点，那么源溯节点必属于同一个环，此时p2={ν1，νi}，根据预处理步骤可得最短路径代价不失真理论；若路径中存在其他通信节点，根据最短路径的最优子结构性质可得相邻的两个通信节点（νj，νj+1)的路径{νj，…，νj+1}必定也是最短路径。而预处理的过程即将{νj，…，νj+1}简化为{νj，νj+1}，因此c1=c2，且p2中的通信节点都存在于p1中，否则p1、p2必定有一条不为最短路径。

2.2 源溯节点还原

新的拓扑图G′存在的问题可能是不包含业务需求中的源溯节点s、t，通过节点还原算法（RN）将原拓扑中的这部分节点和边信息还原到拓扑图G′中，步骤如下：

1）判断源溯节点s、t是否为通信节点，如果是则不需要下列步骤，否则执行下列操作。

2）遍历环内节点，寻找节点s、t所在的环。如果存储空间允许，且可在拓扑生成构建节点时存储节点所在环的信息，则不需要此步骤。

3）计算节点s、t到所在环的所有通信节点的距离。并对每个节点对构建边，并加入到新的拓扑图G′中。算法过程如算法2 所示。

算法2Recover Nodes，tinG'（RN）

图4 所示为预处理及源溯节点还原过程示意图。图4（a）为初始多环网络拓扑图，标黑节点s、t为源溯节点。图4（b）为预处理后的拓扑图，图中网格节点为保留的通信节点，加粗黑实线是预处理后拓扑中通信节点间形成的新边，黑色未加粗实线为源溯节点还原过程中形成的边。

图4 预处理及源溯节点还原过程Fig.4 Restoration process of preprocessing and source tracing nodes

2.3 路径还原

在预处理的拓扑中执行选路算法所获得的路径为只包括通信节点源溯节点的路径，路径还原算法RP 可以将同一环内通信节点间的路径还原为完整的最短路径。该算法还会删除RN 算法中添加的源溯节点及包含该节点的边从而还原为最初的预处理拓扑。实现步骤如下：

1）在拓扑图G′中获得初步的路径path，判断path 中所有边的端节点和末节点是否为同一个环中的节点。若不同，则不执行操作。

2）若该边的端节点和末节点属于同一个环中的节点，在该环中执行寻路算法，获得端节点到末节点的路径path'。

3）删除路径path 中该边，在path 中从节点p到q添加path′。

4）删除拓扑图G′的源溯节点及包含该节点的边。算法过程如算法3 所示。

算法3Recover Path in topology（RP）

路径还原算法过程在大多数情况下可以避免每次都运行。路径还原算法是为了还原同一环中通信节点的路径，而一个环中的通信节点的最短路径只有两种可能，顺时针或者逆时针。而通信节点的数量往往不多，因此，完全可以将路径还原所需要的数据预先计算好并存储下来。存储方式以path(s，t)=(s，t，0(or1))，其中s、t表示2个通信节点，0 和1表示顺时针或者逆时针获得路径。

“最短路径不失真”理论指的是在线性时间内，若网络拓扑直接执行路由算法和经过改进算法获得的非同一环内的节点间的最短路径分别为p1、p2，则p1=p2。

证明如下：对于节点对(s，t)，节点s、t不在一个环内。若p1≠p2，设p1由节点集{s，ν1，…，νi，t}构成，p2由节点集{s，u1，…，ui，t}构成。由于p1≠p2，设p1与p2路径中相异节点为{n1，n2，…，ni}，节点ni可能存在于{s，…，Ccn1}，{Ccni，Ccni+1，…，Ccni+n}或{Ccnj，…，t}路径中，其中Ccni表示路径中的通信节点。{s，…，Ccn1}，{Ccnj，…，t}由2.2 节可知均为最短路径算法获得，因此必定相同；若节点ni存在于{Ccni，…，Ccni+1}中，根据最短路径的最优子结构性质可得最短路径中的任意一段路径均为最短路径，由于ni在另一条路径中不存在，因此该路径上必定不同时存在Ccni和Ccni+1，说明p1、p2中通信节点存在不同，与最短路径代价不失真理论相悖，因此p1=p2。

2.4 算法复杂度分析

多环网络中的路由问题很显然也是一个NPHard 问题，因此有必要对算法进行复杂度分析。假设该多环网络是双向网络，共有j个环，每个小环平均由g个节点构成，其中每个小环上平均有m个节点为通信节点。默认每个通信节点只与一个通信节点相连接，即不存在多对多、一对多、多对一的情况。那么该网络拓扑结果的总结点数为：|V|=j×g，边数为|E|=2j×g+mj。路由过程的底层算法均采用Dijkstra 算法，并以优先队列的方式存储。若不经处理直接在原始网络拓扑中执行路由算法，算法时间复杂度如下：

PRR 算法由3 部分组成。预处理部分首先判断所有的节点度数并标记其是否为通信节点，时间复杂度为O(j×g)；将所有的通信节点标记后，需要计算同一环内通信节点之间的代价值。即在每一个环内执行一次 Dijkstra 算法，时间复杂度为O(2g×lbg)。该步可以在不同环内并行进行，若串行执行该步骤，则算法复杂度为O(2j×g×lbg)。此步时间复杂度共为O(2j×g×lbg)+O(j×g)。

预处理后的拓扑为由m×j个节点构成的有向图。RN 算法将节点s与节点t加入到改进后的网络拓扑中，每执行一次，时间复杂度为O(2g×lbg)，因此时间复杂度为O(4g×lbg)。

拓扑还原后，原有的多环混合网络转换为有向图，执行寻路算法。有向图最多由m×j个通信节点和2 个源溯节点构成。而在这其中，同一环内形成的边数为2m条，不同环之间形成的边数为m×j，因此新的拓扑图总共有2m×j+m×j=3(m×j)条边。此步的算法时间复杂度为O(3(m+j)×lb(m×j+2))。

由此，算法时间复杂度如下：

2 个算法的时间复杂度都含有O((j×g)×lbg)部分。因此，需要比较的部分为：O((j×g)×lbj+(m×j)×lb(j×g))与O((m×j)×lb(m×j)，其底数分别为j×g，m×j，即前者为所有的节点个数，后者为所有的通信节点个数，因此改进后的算法时间复杂度更优。当环的个数为1 时，算法的时间复杂度退化为Dijkstra 算法的时间复杂度。时间复杂度的减小无可避免地伴随着空间复杂度的增加，算法需要额外存储一个由m×j个节点和3(m×j)条边组成的新拓扑图，以及通信节点之间路径的数据，但是通信节点在实际拓扑中往往占比很小，因此不需要庞大的存储空间，算法具有应用的价值。

3 实验分析

3.1 实验数据和实验配置

仿真实验的硬件环境为Intel®CoreTMi5-4570 CPU@3.20 GHz，内存4.0 GB，操作系统Windows 10。在NS2 网络节点仿真软件上进行网络拓扑仿真，在Intellij idea 上进行算法的实现和实验对比。实验通过设置网络节点个数、环的个数、通信节点个数、节点间的平均度数（代价）、“桥”的平均度数来构建网络拓扑。通过搜索空间比、改进比以及算法执行时间作为实验结果参考数据。其中，搜索空间表示最短路径节点数和算法搜索总结点数的比值，搜索空间越接近1，说明算法效果越好。改进比表示两个算法的搜索空间的比值，改进比越大，说明算法相应的改进效果越明显。

3.2 实验结果和分析

复杂多环网络的路由算法测试实验的影响参数主要有环的节点个数、环的个数、环的通信节点个数（即每个环可与其他环连接个数）。在本实验中，网络规模大小（总节点个数）、环的个数和通信节点个数均可调整。原算法与PRR 算法的底层寻路算法采用Dijkstra算法，其中PRR 算法运行时间不包括生成缓存数据（同一环内通信节点代价及路径）的算法运行时间，每行数据由20 组不同源溯节点数据取平均值所得。实验主要分为3 部分，分别是同等规模下不同影响参数下的算法性能比较、不同规模下的算法性能比较以及批量业务下的算法性能比较。

1）同等规模不同影响参数下的算法性能对比结果如表1 所示。网络规模的节点总个数皆为10 000，当环个数为20、50 和100 时，PRR 相比于原方法的改进比为1.26～2.62，PRR 算法具有更好的表现效果。

表1 不同参数下实验结果Table 1 Experimental results under different parameters

令ρ=通信节点个数/环个数，从实验数据对比可发现，在一定程度内，随着ρ的不断增加，PRR 算法效果表现得越好。ρ也可以理解为每个环与其他环连接的个数占所有环个数比。所以，当ρ较大时，环与环之间的连接较为复杂，每个环可连接的环增加，而PRR 算法简化了此步的搜索。但并不是ρ越大，实验效果越好，对比表1 中实验序号2 和3 可知，出现这种结果的原因是此时的ρ太小，环与环之间连通性太高，导致节点与节点间路径大幅减小，效果不明显。后续实验发现当ρ<0.35 该结果成立。

当环个数不变时，通信节点个数增加，改进比虽然有较小提升，但原算法时间有明显减小，而PRR 算法运行时间明显增加。出现这种结果的主要原因是通信节点个数增加后，环与环之间连通性增强了，节点到节点间路径更短了，因此原算法运行时间减少，而改进算法由于通信节点的增加，构建新拓扑图复杂度则提升。

2）不同规模下的算法性能对比结果如表2 所示。从数据中可以观察，改进比均值为2.10，说明PRR 算法具有一定的优越性。网络中通信节点的个数设置为5，当环个数固定，随着每个环中节点个数增加，PRR 算法的表现越来越优于原算法；而当每个环中节点个数一定时，随着环个数增加，PRR 算法的表现也更加优良。因此可以得出当网络规模越大时，PRR 算法的效果越好。从表2 的实验数据1 可以看出，当网络规模较小时，PRR 算法运行时间甚至比原算法执行时间更长，主要原因是当网络规模较小时，寻路所用时间占比重较小。

表2 不同规模下实验结果Table 2 Experimental results at different scales

3）批量业务下算法性能对比结果如图5 所示，其中，（6，DJS 算法）中6 表示通信节点个数。前2 个实验的PRR 算法执行时间不包括生成缓存数据的执行时间，因为在实际情况下，一个网络往往需要处理成千上百万个业务，因此预处理的时间往往可以忽略不计。本次实验在10 000 个节点、100 个环的网络中测试不同通信节点个数下Dijkstra 算法和PRR 算法的性能表现。由图5 可知当业务数不超过20 时，改进算法的效果已经优于传统算法；当通信节点个数减少时，相交点来的更快。从图中可以看出，Dijkstra 算法处理批量业务的执行时间随着业务量的增加呈线性增长，而PRR 算法随着业务量的增长，算法执行时间不断增长，且速度较为平稳与缓慢。但PRR 在业务数量较小时，耗时较长。这是因为分治划分导致了额外开销，这是PRR 的不足之处。

图5 批量业务下算法的执行时间Fig.5 Algorithm execution time under batch business

4 结束语

本文提出一种针对复杂多环网络拓扑的路由改进算法PRR，采用分治法将一个大网络拓扑路由问题划分为多个小网络拓扑路由问题。PRR 算法只在节点数和边数较少的单个环以及预处理后的有向图上执行，可避免原有算法在复杂多环网络中由于节点和边数的数量较多而导致复杂度激增，同时PRR算法在将原有拓扑进行预处理后，通过还原算法保证寻路结果的正确性。实验结果表明，该路由算法与Dijkstra 算法相比，在复杂多环网络拓扑中具有更好的效果。下一步将通过业务摘要生成、近似计算等方法，缩短PRR 的耗时，提升其在批量业务下的性能表现。