基于拓撲感知的可重構服務承載網動態重構算法

梁寧寧，蘭巨龍，張震

?

基于拓撲感知的可重構服務承載網動態重構算法

梁寧寧，蘭巨龍，張震

（國家數字交換系統工程技術研究中心，河南鄭州，450002）

可重構信息通信基礎網絡通過構建服務承載網的方式為業務提供自適應的承載服務。針對高效利用有限底層資源的問題，提出一種基于資源關鍵度進行動態映射的服務承載網構建算法。算法將通過節點或鏈路的最短路徑數作為資源關鍵度的衡量指標，區別對待底層資源；并實時動態感知關鍵資源的使用狀況，依據不同業務需求對服務承載網進行自適應調整。仿真結果表明，算法在構建成功率、收益花費比和資源均衡度等方面均具有良好性能。

拓撲感知；關鍵資源；動態映射；可重構服務承載網

1 引言

隨著當前網絡應用規模的不斷擴張、新興業務不斷涌現，現有的以IP為核心的網絡基礎架構已經不堪重負，帶來了網絡結構僵化、核心功能單一、可控性和演變能力低下等問題。加之當前網絡的剛性結構，而現有措施大多是對其進行修補或是簡單擴展，并未從根本上滿足泛在互聯、融合異構、可信可管可擴等需求[1]。

為此，可重構信息通信基礎網絡通過為用戶構建可重構服務承載網的方式，實現其對功能可動態重構和擴展的底層物理網絡的共享，從而為不同業務提供其根本需求和可定制的基礎網絡服務。所謂“可重構服務承載網（RSCN, reconfigurable service carrying network）”即是將業務需求與底層網絡資源狀態，如網絡拓撲、資源狀態等條件優化考慮，構建出的多個在底層物理資源上存在交集，能夠提供不同服務能力的承載子網，如圖1所示。

構建服務承載網即是在滿足用戶業務需求的基礎上，根據網絡的動態變化優化網絡資源配置，充分利用網絡資源。然而，在服務承載網構建中主要存在2個問題：1）不關心底層拓撲，沒有區分底層節點和鏈路的重要性；2）缺少對已映射的服務承載網構建請求的動態優化措施。基于此，本文提出了一種基于拓撲感知的可重構服務承載網動態重構（DTAR, dynamic topology awareness-based rscn reconfiguration）算法。算法定義“資源關鍵度”、“資源緊要度”作為衡量底層資源重要性的指標，在服務承載網構建時，將底層資源區別對待；并動態感知資源的使用狀態，發現緊要資源并進行相應遷移處理，從而大大提高了服務承載網請求的構建成功率。

2 相關研究

面對用戶數量和業務種類爆炸式地增長，可重構服務承載網的構建目標愈來愈明確，即在滿足用戶業務需求的基礎上，盡可能多地接受服務承載網構建請求，最大化利用有限的底層資源。以此為出發點，如何高效地利用底層資源進行服務承載網構建，是服務承載網構建中的核心問題。現有評估底層資源的方式主要包括兩方面。

1) 底層節點和鏈路資源

文獻[2]提出了一種節點映射與鏈路映射相分離的兩階段承載網映射算法。首先，算法以貪婪方式進行節點映射，將所有虛擬節點映射到具有更充足資源的底層節點，而后在鏈路映射階段分別使用了最短路徑和多商品流算法進行映射。文獻[3]使用混合整數規劃方法，提出節點與鏈路協調映射的承載網構建算法。文獻[4]提出了同時映射虛擬節點和虛擬鏈路的分布式算法，然而在性能和最優化方面都與集中式算法存在差距，且算法并未考慮構建請求的生存時間。文獻[5]提出了周期性地檢測底層資源負載情況，并據此對超負荷資源上的承載網進行重映射的算法。然而，這類算法在映射過程中僅考慮了節點CPU和鏈路帶寬的約束，忽略了節點和鏈路本身對映射造成的影響，片面地刻畫了底層資源的屬性，最終將導致底層資源利用率的降低。

2) 拓撲屬性

拓撲屬性作為網絡資源重要參數之一，在現有承載網構建中備受關注。文獻[6]提出了一種一階段回溯算法子圖同構檢測的動態映射方式。文獻[7]提出了一種能夠適應網絡環境變化的承載網拓撲控制算法。該算法基于生物系統中的吸引子模型，根據節點故障所引起的網絡環境變化，動態地重新配置吸引子結構，從而實現承載網拓撲的重建。但算法的復雜度較高，不易實現。利用小拓撲的靈活性，文獻[8]將每個虛擬網分裂成多個星型子網，并將星型子網中具有最高度的中心節點映射到具有最低CPU和可用帶寬的底層節點。一旦確定中心節點，其他具有較高度的節點將一個接一個地映射到具有較高資源占用率且距中心節點較近的底層節點之上。然而，算法假設底層網絡資源無限，且并不適用于許多特殊拓撲。文獻[9]提出了一種基于流量約束的虛擬網絡映射算法，然而，該算法也僅適用于拓撲結構為星型的構建請求。文獻[10]將Google PageRank算法引入Web搜索域中，提出了一種拓撲感知的底層資源度量方法，通過馬爾可夫隨機游動模型，基于當前資源及其拓撲屬性對節點排序，并依據其排序值進行貪婪映射。文獻[11]以資源連接度度量底層資源，這一參數的引入雖然凸顯了底層資源的差異性，但該指標并不能準確定義一個節點或是鏈路的重要性。例如，雖然一個節點的連接度很高，但與其相連的節點并不重要，那么該節點也并不一定重要；反之，若一個節點的連接度不高，但與它相連的節點大多非常重要，那么該節點在網絡中也可能非常重要。雖然，這類算法已或多或少的考慮了網絡拓撲對承載網映射的影響，但仍然存在2個方面的問題：1）沒有使用較為準確、合理的方式區分底層節點和鏈路的重要性；2）缺少對已映射的服務承載網構建請求的動態優化機制。

本文認為，不同的節點和鏈路在底層拓撲中的重要性大相徑庭，放棄使用非關鍵底層資源，而將業務需求過量映射到關鍵的底層節點和鏈路上，易造成資源瓶頸，引起底層網絡失效，從而嚴重影響服務承載網的構建成功率。因此，綜合地度量底層資源屬性，動態感知底層資源狀態，對于高效構建可重構服務承載網尤為重要。

基于此，本文提出了一種能夠將底層資源合理區別對待的服務承載網動態構建算法，該方法具有以下特點：1) 將通過底層節點和鏈路的最短路徑數作為衡量關鍵資源的指標，能夠較全面地反映該資源在全網中的重要性；2) 依據資源關鍵度對底層節點排序，將虛擬節點優先映射到滿足業務需求的非關鍵底層資源之上，合理高效地使用底層網絡資源；3) 通過對資源使用程度的動態感知，發現緊要資源并進行相應地遷移處理，有效避免了瓶頸資源的出現，增強了基礎物理網絡的可靠性。

3 可重構服務承載網構建模型

3.1 基礎物理網絡

3.2 業務需求模型

3.3 服務承載網映射

節點映射(2)

鏈路映射(3)

3.4 服務承載網目標

1) 高效利用底層資源

服務承載網是在共享的底層資源上構建出能夠提供不同服務能力的承載子網，其核心問題即是如何在有限的底層資源之上，構建盡可能多的服務承載網，高效地使用底層網絡資源。

定義1 收益(G)。成功為業務構建服務承載網所帶來收益的總和。

定義2 花費(G)。為成功構建服務承載網所消耗的底層資源的總和。

有效的服務承載網構建即是利用有限的底層資源構建盡可能多的服務承載網，滿足盡可能多的業務需求，換言之，即在構建相同數量的服務承載網時，最小化底層資源的使用。因此，相應給出以下2個定義。

定義3 服務承載網構建成功率accept。服務承載網成功構建的個數與構建請求總數之比，即

定義4 長期收益花費比。構建服務承載網的收益與花費之比，即

(7)

2) 基于業務需求進行資源遷移

除了高效使用底層資源外，服務承載網構建的另一目標就是根據業務需求及底層資源運行狀態，對已構建的服務承載網進行動態調整。當感知到底層資源超負荷工作時，及時根據業務需求將緊要資源上的業務相應地進行遷移。

在進行資源遷移時，將根據業務類型選擇遷移對象。例如帶寬敏感型業務的性能目標是最大化帶寬，因此在遷移過程中，算法更傾向為其選擇具有充沛資源的底層節點或鏈路進行映射；而時延敏感型業務的性能目標是最小化平均時延，因此算法將會優先選擇低時延路徑遷移，即遷移到離原映射節點較近的底層節點之上。

4 基于拓撲感知的服務承載網動態重構算法

4.1 資源度量

DTAR算法定義資源關鍵度和資源緊要度分別作為底層資源屬性和度量底層資源使用程度的指標，并作如下定義。

定義5 資源關鍵度。資源關鍵度是指網絡中所有最短路徑之中經過該資源的個數，包括節點關鍵度和鏈路關鍵度。歸一化表示為

其中，P為節點與節點之間最短路徑的集合，和分別表示經過節點和鏈路的最短路徑的數量。

資源關鍵度是由拓撲屬性確定的定值。資源關鍵度越高，說明該資源越重要，倘若這些節點或鏈路失效，對網絡的影響也就越大。因此在映射過程中，將優先選擇關鍵度低的資源映射，確保網絡均衡可靠使用。

定義6 資源緊要度。指各底層節點或鏈路的已用資源與該節點或鏈路的總資源之比，包括節點緊要度和鏈路緊要度。表達式如下

其中，Bw()表示服務承載網在底層鏈路上為業務需求分配的帶寬資源，為底層鏈路的總帶寬；和分別表示底層節點上，業務需求被分配得到的緩存容量和CPU計算能力的使用情況，和則分別表示節點的緩存總量和CPU計算能力。

資源緊要度是隨著底層資源的使用情況而動態變化的，資源緊要度越大，說明該底層節點或鏈路上的負載越高，負擔越重。

4.2 重構算法

4.2.1 DTAR算法思想描述

雖然已有一些將業務需求映射到底層網絡的有效算法[12~15]，但隨著時間的推移，成功構建服務承載網數量的增加將使部分底層資源處于超負荷運轉狀態，甚至瀕臨癱瘓，最終致使構建其上的服務承載網無效。針對這一問題，DTAR算法分為3個階段進行。

Step1 關鍵資源感知。由底層網絡拓撲屬性區分關鍵資源，計算得到從每個節點到其他所有節點的最短路徑。那么，通過該資源的最短路徑數越多，說明該資源越關鍵。

Step2 服務承載網構建。DTAR算法基于資源關鍵度對底層資源降序排列，并依此序進行映射。考慮以關鍵度從小到大的順序映射的原因如下：1）為了增強網絡的可靠性；2）有利于網絡資源充分使用。

Step3 緊要資源遷移。DTAR算法通過感知底層資源的緊要度，將過載工作的底層節點或鏈路上的業務依據其需求進行相應遷移，將底層資源失效防范于未然。

圖2給出了基于拓撲感知的服務承載網動態重構的示意。在圖2(a)中，服務承載網構建請求RSCN1中的3個虛擬節點分別映射到底層節點{,,}。假設由底層拓撲屬性已計算出節點及鏈路的資源關鍵度，其中，節點{,,}為關鍵節點，設置資源緊要度閾值為80%，其他非關鍵資源的緊要度閾值為90%，即對具有不同重要性的節點或鏈路設置不同的資源緊要度閾值，資源越重要，其閾值設置越低。此時由于RSCN1的構建，感知到關鍵節點的資源緊要度已超過閾值80%，處于超負荷階段。

圖2(b)中，將映射到關鍵資源的服務承載網RSCN1的虛擬節點遷移到能夠滿足其業務需求的底層節點，并同時釋放節點上的相應資源。

4.2.2 構建目標函數

高效構建服務承載網即是在構建過程中，最小化構建花費。

那么，最小化構建花費表示為

(11)

(12)

(14)

其中，式(11)表示構建服務承載網所選路徑的時延小于業務構建請求的時延需求；式(12)表示當前承載業務的虛擬節點消耗的緩存資源之和小于節點最大緩存容量；式(13)表示虛擬節點消耗的CPU計算資源之和小于底層節點最大CPU計算能力；式(14)表示虛擬鏈路消耗的帶寬資源之和小于底層鏈路的最大帶寬。

4.2.3 關鍵資源感知映射

DTAR算法為了更加合理地使用底層資源，由底層網絡拓撲結構計算資源關鍵度，確定關鍵資源，并為關鍵資源設置緊要度閾值，為非關鍵資源設置緊要度閾值，且<，即確保關鍵資源不能被過度使用；動態感知底層資源狀態，計算資源緊要度；將底層資源按照資源關鍵度遞減排序；進行節點映射時，選擇能滿足業務需求的資源關鍵度最小的資源依序進行映射，均衡充分地使用底層網絡資源；而后以最短路徑進行鏈路映射。算法1和算法2分別給出了關鍵資源感知以及基于關鍵資源的服務承載網構建的詳細步驟。

算法1 關鍵資源感知算法

過程：

2) 計算經過任意中間節點最短路徑的條數()

if在SPT()中出現

()+1；

else未在SPT()中出現

()；

3) 計算經過任意鏈路最短路徑的條數()

if在SPT()中出現

()+1；

else未在SPT()中出現

()；

5) 將每個節點的()值和每條鏈路的()值代入式(8)，分別計算每個節點和鏈路的資源關鍵度。

6) 確定關鍵資源，并設置資源緊要度閾值；對非關鍵資源設置閾值。

8) 將已用資源值代入式(9)，得到每個底層節點和鏈路的資源緊要度。

輸出：

算法2 基于關鍵資源的服務承載網構建算法

過程：

執行2)；

無法構建滿足業務需求的服務承載網絡。

end

5) 鏈路映射，以最短路徑映射。

計算和之間的最短路徑

end

4.2.4 緊要資源遷移

DTAR算法動態感知底層資源的資源緊要度，對于超過資源緊要度閾值的底層資源，將已映射其上的服務承載網按照業務需求進行遷移。對于時延敏感型業務，優先選擇將其遷移到離原映射節點近的底層節點，確保遷移后的服務承載網仍具有較小時延；對于帶寬敏感型業務，將在滿足時延需求的前提下，優先選擇節點或鏈路資源充沛的底層資源進行映射。算法3為緊要資源遷移的詳細步驟。

算法3 緊要資源遷移算法

過程：

if< 資源緊要度閾值

維持現有服務承載網構建狀態；

else≥資源緊要度閾值

執行2)。

if 節點過載

執行3)；

else 鏈路過載

執行5)。

3) 將過載節點上的已映射資源依據業務需求遷移。

if 時延敏感型

else 帶寬敏感型

4) 對成功遷移節點以最短路徑進行鏈路映射。

5)將過載鏈路上的已映射資源遷移至該鏈路所連接的2節點間（除該鏈路外）的最短路徑。

5 算法仿真與分析

在效能評估中，DTAR算法與基于底層資源負載狀況的G-SP[5]算法和基于連接度的WD-VNE[11]算法進行性能比較，主要從服務承載網構建成功率、構建收益花費比以及資源均衡度3個方面進行討論。

5.1 實驗設置

仿真實驗中的基礎網絡拓撲是由BRITE工具隨機產生的100個節點組成的，節點連接率為0.5，節點與鏈路資源服從50~100的均勻分布。RSCN節點個數需求滿足2~10的均勻分布，鏈路帶寬需求、節點CPU能力及緩存容量均為0~30的均勻分布，節點連接率為0.5。業務構建RSCN請求的到達過程服從時間單位為100，強度為10的泊松過程；每個RSCN的生存時間服從期望為1 000的指數分布。為了仿真結果的準確性，本文共進行仿真實驗20次，所取結果為所有實驗結果的平均值。

5.2 服務承載網構建成功率

圖3為隨服務承載網構建請求數增多，不同算法的服務承載網構建成功率。由于G-SP算法在映射時，并未將底層資源的拓撲屬性考慮其中，僅針對底層負載狀況進行處理，因此其服務承載網構建成功率最低；而充分考慮了拓撲屬性的WD-VNE算法與DTAR算法將底層資源區別對待，均表現出較強的服務承載網構建能力。當底層資源充足時，2種算法的構建成功率相當；但隨著服務承載網構建請求數的增多，由于資源連接度并不能準確全面地描述底層資源的重要性，因此DTAR算法的構建成功率將略高于WD-VNE算法。

5.3 服務承載網構建收益花費比

圖4為不同算法的服務承載網構建收益花費比。隨著服務承載網構建請求數的增加，3種算法的收益花費比日趨均衡。由于DTAR算法以最小構建花費為目標進行服務承載網構建，且遷移時，僅針對過載資源上的部分服務承載網進行資源調整，因此其收益花費比率將高于不具備對已映射的服務承載網進行動態優化處理的WD-VNE算法，而未考慮底層資源差異性的G-SP算法的收益花費比最低。

5.4 資源均衡度

所謂資源均衡度是指構建的服務承載網對底層網絡資源的使用情況。分為網絡節點均衡度和網絡鏈路均衡度。

定義7 節點均衡度。服務承載網構建時，整個底層網絡上所用節點的平均處理能力與最大處理能力的比值。

定義8 鏈路均衡度。構建服務承載網時，整個底層網絡上所用鏈路的平均利用率與最大鏈路利用率的比值。

(16)

圖5和圖6分別給出隨服務承載網構建數量的增加，不同算法的資源均衡度情況。構建服務承載網時，DTAR算法首先選擇資源關鍵度低的節點映射，而避免對關鍵資源的過度使用，這必定使網絡資源得到充分使用，因此其資源均衡度最高。G-SP算法考慮到負載均衡問題，優先選用負載較低且距離較近的底層節點映射，而WD-VNE算法基于資源連接度和資源容量進行映射，對底層資源的使用相對集中，因此其資源均衡度最低。

6 結束語

高效地使用底層網絡資源，以期最大化構建成功率，是服務承載網構建的永恒主題。基于此，本文提出了一種基于拓撲感知的服務承載網動態重構算法。DTAR算法使用通過節點或鏈路的最短路徑數衡量資源重要性，給出了“資源關鍵度”的定義，并依據資源關鍵度對資源降序映射；定義了“資源緊要度”指標對底層資源使用狀態進行刻畫，并將動態感知到的緊要資源進行優化配置。仿真結果表明：在與算法G-SP和WD-VNE進行的性能對比中，DTAR算法在提高構建成功率的同時，具有較高的收益花費比和資源均衡度。

[1] 蘭巨龍, 程東年, 胡宇翔. 可重構信息通信基礎網絡體系研究[J]. 通信學報, 2014, 35(1):187-198.

LAN J L, CHENG D N, HU Y X. Research on reconfigurable information communication basal network architecture[J]. Journal on Communications, 2014, 35(1): 187-198.

[2] YU M, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration [J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29.

[3] CHOWDHURY N, RAHMAN M, BOUTABA R. Virtual network embedding with coordinated node and link mapping[C]//IEEE INFOCOM. Rio de Janeiro, c2009: 783-791.

[4] HOUIDI I, LOUATI W, ZEGHLACHE D. A distributed virtual network mapping algorithm[C]//IEEE ICC. c2008:5634-5640.

[5] ZHU Y, AMMAR M. Algorithms for assigning substrate network resources to virtual network components[C]//25th IEEE International Conference on Computer Communications (INFOCOM). Barcelona, c2006:1-12.

[6] LISHKA J, KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection[C]//The 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. Barcelona, c2009:81-88.

[7] KOIZUMI Y, ARAKAWA S, KAMAMURA S, et al. Adaptability of virtual network topology control based on attractor selection against multiple Node Failures[C]//OptoElectronics and Communications Conference held jointly with 2013 International Conference on Photonics in Switching (OECC/PS). Kyoto, c2013:1-2.

[8] BAVIER A, FEAMSTER N, HUANG M, et al. In VINI veritas: realistic and controlled network experimentation [J]. ACM SIGCOMM Computer Communication Review, 2006, 36 (4): 3-14.

[9] LU J, TURNER J. Efficient mapping of virtual networks onto a shared substrate[R]. Department of Computer Science and Engineering, Washington University, 2006.

[10] CHENG X, SU S, ZHANG Z, et al. Virtual network embedding through topology-aware node ranking [J]. ACM SIGCOMM Computer Communication Review, 2011, 41(2): 39-47.

[11] YUAN Y, WANG C, ZHU N, et al. Virtual network embedding algorithm based connective degree and comprehensive capacity[C]//9th International Conference on ICIC 2013. Nanjing, c2013: 250-258.

[12] ZHANG S, QIAN Z H, WU J, et al. Virtual network embedding with opportunistic resource sharing [J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3): 816- 827.

[13] HU Q, WANG Y, CAO X J, et al. Virtual network embedding: an optimal decomposition approach[C]//International Conference on Computer Communication and Networks (ICCCN). Shanghai, c2014: 1-6.

[14] DIETRICH D, PAPADIMITRIOU P. Policy-compliant virtual network embedding[C]//International Conference on IFIP. Trondheim, c2014: 1-9.

[15] MELO M, SARGENTO S, KILLAT U, et al. Optimal virtual network embedding: node-link formulation [J]. IEEE Transactions on Network and Service Management, 2013, 10(4): 356- 368.

Dynamic topology awareness-based reconfigurable service carrying network reconfiguration

LIANG Ning-ning, LAN Ju-long, ZHANG Zhen

(National Digital Switching System Engineering & Technological Research Center, Zhengzhou 450002, China)

Reconfigurable information communication basal network supports self-adaptive services to applications by constructing reconfigurable service carrying network(RSCN). To effectively utilize the limited substrate network resources, an algorithm of dynamic topology awareness-based RSCN reconfiguration (DTAR) was proposed. The algorithm uses the number of shortest paths as resource critical degree which across the node or link to distinguish substrate resource. And it also dynamically awares the states of critical resources, reoptimises the RSCN according to service request. Experimental results show that comparing with the existing algorithms, the proposed algorithm achieves higher success ratio, gains higher revenue, cost ratio and load equilibrium for substrate network.

topology awareness, critical resource, dynamic embedding, reconfigurable service carrying network

TP393

A

10.11959/j.issn.1000-436x.2016032

2015-01-03；

2015-10-26

國家重點基礎研究發展計劃（“973”計劃）基金資助項目（No.2012CB315901,No.2013CB329104）；國家自然科學基金資助項目（No.61372121）；國家高技術研究發展計劃（“863”計劃）基金資助項目（No.2013AA013505）

The National Basic Research Program of China (973 Program) (No.2012CB315901, No.2013CB329104), The National Natural Science Foundation of China (No.61372121), The National High Technology Research and Development Program of China (863 Program) (No.2013AA013505)

梁寧寧（1982-），女，天津人，博士，國家數字交換系統工程技術研究中心講師，主要研究方向為寬帶信息網絡和下一代網絡。

蘭巨龍（1962-），男，河北張北人，博士，國家數字交換系統工程技術研究中心總工程師、教授、博士生導師，主要研究方向為新一代信息網絡關鍵理論與技術。

張震（1985-），男，山東濟寧人，博士，國家數字交換系統工程技術研究中心講師，主要研究方向為網絡測量技術。