針對復雜多環網絡拓撲的路由改進算法

荊 霞，周子韜，王永利

（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 的耗時，提升其在批量業務下的性能表現。