基于拓?fù)涓兄目芍貥?gòu)服務(wù)承載網(wǎng)動態(tài)重構(gòu)算法

梁寧寧，蘭巨龍，張震

?

基于拓?fù)涓兄目芍貥?gòu)服務(wù)承載網(wǎng)動態(tài)重構(gòu)算法

梁寧寧，蘭巨龍，張震

（國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南鄭州，450002）

可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)通過構(gòu)建服務(wù)承載網(wǎng)的方式為業(yè)務(wù)提供自適應(yīng)的承載服務(wù)。針對高效利用有限底層資源的問題，提出一種基于資源關(guān)鍵度進行動態(tài)映射的服務(wù)承載網(wǎng)構(gòu)建算法。算法將通過節(jié)點或鏈路的最短路徑數(shù)作為資源關(guān)鍵度的衡量指標(biāo)，區(qū)別對待底層資源；并實時動態(tài)感知關(guān)鍵資源的使用狀況，依據(jù)不同業(yè)務(wù)需求對服務(wù)承載網(wǎng)進行自適應(yīng)調(diào)整。仿真結(jié)果表明，算法在構(gòu)建成功率、收益花費比和資源均衡度等方面均具有良好性能。

拓?fù)涓兄魂P(guān)鍵資源；動態(tài)映射；可重構(gòu)服務(wù)承載網(wǎng)

1 引言

隨著當(dāng)前網(wǎng)絡(luò)應(yīng)用規(guī)模的不斷擴張、新興業(yè)務(wù)不斷涌現(xiàn)，現(xiàn)有的以IP為核心的網(wǎng)絡(luò)基礎(chǔ)架構(gòu)已經(jīng)不堪重負(fù)，帶來了網(wǎng)絡(luò)結(jié)構(gòu)僵化、核心功能單一、可控性和演變能力低下等問題。加之當(dāng)前網(wǎng)絡(luò)的剛性結(jié)構(gòu)，而現(xiàn)有措施大多是對其進行修補或是簡單擴展，并未從根本上滿足泛在互聯(lián)、融合異構(gòu)、可信可管可擴等需求[1]。

為此，可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)通過為用戶構(gòu)建可重構(gòu)服務(wù)承載網(wǎng)的方式，實現(xiàn)其對功能可動態(tài)重構(gòu)和擴展的底層物理網(wǎng)絡(luò)的共享，從而為不同業(yè)務(wù)提供其根本需求和可定制的基礎(chǔ)網(wǎng)絡(luò)服務(wù)。所謂“可重構(gòu)服務(wù)承載網(wǎng)（RSCN, reconfigurable service carrying network）”即是將業(yè)務(wù)需求與底層網(wǎng)絡(luò)資源狀態(tài)，如網(wǎng)絡(luò)拓?fù)洹①Y源狀態(tài)等條件優(yōu)化考慮，構(gòu)建出的多個在底層物理資源上存在交集，能夠提供不同服務(wù)能力的承載子網(wǎng)，如圖1所示。

構(gòu)建服務(wù)承載網(wǎng)即是在滿足用戶業(yè)務(wù)需求的基礎(chǔ)上，根據(jù)網(wǎng)絡(luò)的動態(tài)變化優(yōu)化網(wǎng)絡(luò)資源配置，充分利用網(wǎng)絡(luò)資源。然而，在服務(wù)承載網(wǎng)構(gòu)建中主要存在2個問題：1）不關(guān)心底層拓?fù)洌瑳]有區(qū)分底層節(jié)點和鏈路的重要性；2）缺少對已映射的服務(wù)承載網(wǎng)構(gòu)建請求的動態(tài)優(yōu)化措施。基于此，本文提出了一種基于拓?fù)涓兄目芍貥?gòu)服務(wù)承載網(wǎng)動態(tài)重構(gòu)（DTAR, dynamic topology awareness-based rscn reconfiguration）算法。算法定義“資源關(guān)鍵度”、“資源緊要度”作為衡量底層資源重要性的指標(biāo)，在服務(wù)承載網(wǎng)構(gòu)建時，將底層資源區(qū)別對待；并動態(tài)感知資源的使用狀態(tài)，發(fā)現(xiàn)緊要資源并進行相應(yīng)遷移處理，從而大大提高了服務(wù)承載網(wǎng)請求的構(gòu)建成功率。

2 相關(guān)研究

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

1) 底層節(jié)點和鏈路資源

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

2) 拓?fù)鋵傩?/p>

拓?fù)鋵傩宰鳛榫W(wǎng)絡(luò)資源重要參數(shù)之一，在現(xiàn)有承載網(wǎng)構(gòu)建中備受關(guān)注。文獻[6]提出了一種一階段回溯算法子圖同構(gòu)檢測的動態(tài)映射方式。文獻[7]提出了一種能夠適應(yīng)網(wǎng)絡(luò)環(huán)境變化的承載網(wǎng)拓?fù)淇刂扑惴āＴ撍惴ɑ谏锵到y(tǒng)中的吸引子模型，根據(jù)節(jié)點故障所引起的網(wǎng)絡(luò)環(huán)境變化，動態(tài)地重新配置吸引子結(jié)構(gòu)，從而實現(xiàn)承載網(wǎng)拓?fù)涞闹亟ā５惴ǖ膹?fù)雜度較高，不易實現(xiàn)。利用小拓?fù)涞撵`活性，文獻[8]將每個虛擬網(wǎng)分裂成多個星型子網(wǎng)，并將星型子網(wǎng)中具有最高度的中心節(jié)點映射到具有最低CPU和可用帶寬的底層節(jié)點。一旦確定中心節(jié)點，其他具有較高度的節(jié)點將一個接一個地映射到具有較高資源占用率且距中心節(jié)點較近的底層節(jié)點之上。然而，算法假設(shè)底層網(wǎng)絡(luò)資源無限，且并不適用于許多特殊拓?fù)洹Ｎ墨I[9]提出了一種基于流量約束的虛擬網(wǎng)絡(luò)映射算法，然而，該算法也僅適用于拓?fù)浣Y(jié)構(gòu)為星型的構(gòu)建請求。文獻[10]將Google PageRank算法引入Web搜索域中，提出了一種拓?fù)涓兄牡讓淤Y源度量方法，通過馬爾可夫隨機游動模型，基于當(dāng)前資源及其拓?fù)鋵傩詫?jié)點排序，并依據(jù)其排序值進行貪婪映射。文獻[11]以資源連接度度量底層資源，這一參數(shù)的引入雖然凸顯了底層資源的差異性，但該指標(biāo)并不能準(zhǔn)確定義一個節(jié)點或是鏈路的重要性。例如，雖然一個節(jié)點的連接度很高，但與其相連的節(jié)點并不重要，那么該節(jié)點也并不一定重要；反之，若一個節(jié)點的連接度不高，但與它相連的節(jié)點大多非常重要，那么該節(jié)點在網(wǎng)絡(luò)中也可能非常重要。雖然，這類算法已或多或少的考慮了網(wǎng)絡(luò)拓?fù)鋵Τ休d網(wǎng)映射的影響，但仍然存在2個方面的問題：1）沒有使用較為準(zhǔn)確、合理的方式區(qū)分底層節(jié)點和鏈路的重要性；2）缺少對已映射的服務(wù)承載網(wǎng)構(gòu)建請求的動態(tài)優(yōu)化機制。

本文認(rèn)為，不同的節(jié)點和鏈路在底層拓?fù)渲械闹匾源笙鄰酵ィ艞壥褂梅顷P(guān)鍵底層資源，而將業(yè)務(wù)需求過量映射到關(guān)鍵的底層節(jié)點和鏈路上，易造成資源瓶頸，引起底層網(wǎng)絡(luò)失效，從而嚴(yán)重影響服務(wù)承載網(wǎng)的構(gòu)建成功率。因此，綜合地度量底層資源屬性，動態(tài)感知底層資源狀態(tài)，對于高效構(gòu)建可重構(gòu)服務(wù)承載網(wǎng)尤為重要。

基于此，本文提出了一種能夠?qū)⒌讓淤Y源合理區(qū)別對待的服務(wù)承載網(wǎng)動態(tài)構(gòu)建算法，該方法具有以下特點：1) 將通過底層節(jié)點和鏈路的最短路徑數(shù)作為衡量關(guān)鍵資源的指標(biāo)，能夠較全面地反映該資源在全網(wǎng)中的重要性；2) 依據(jù)資源關(guān)鍵度對底層節(jié)點排序，將虛擬節(jié)點優(yōu)先映射到滿足業(yè)務(wù)需求的非關(guān)鍵底層資源之上，合理高效地使用底層網(wǎng)絡(luò)資源；3) 通過對資源使用程度的動態(tài)感知，發(fā)現(xiàn)緊要資源并進行相應(yīng)地遷移處理，有效避免了瓶頸資源的出現(xiàn)，增強了基礎(chǔ)物理網(wǎng)絡(luò)的可靠性。

3 可重構(gòu)服務(wù)承載網(wǎng)構(gòu)建模型

3.1 基礎(chǔ)物理網(wǎng)絡(luò)

3.2 業(yè)務(wù)需求模型

3.3 服務(wù)承載網(wǎng)映射

節(jié)點映射(2)

鏈路映射(3)

3.4 服務(wù)承載網(wǎng)目標(biāo)

1) 高效利用底層資源

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

定義1 收益(G)。成功為業(yè)務(wù)構(gòu)建服務(wù)承載網(wǎng)所帶來收益的總和。

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

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

定義3 服務(wù)承載網(wǎng)構(gòu)建成功率accept。服務(wù)承載網(wǎng)成功構(gòu)建的個數(shù)與構(gòu)建請求總數(shù)之比，即

定義4 長期收益花費比。構(gòu)建服務(wù)承載網(wǎng)的收益與花費之比，即

(7)

2) 基于業(yè)務(wù)需求進行資源遷移

除了高效使用底層資源外，服務(wù)承載網(wǎng)構(gòu)建的另一目標(biāo)就是根據(jù)業(yè)務(wù)需求及底層資源運行狀態(tài)，對已構(gòu)建的服務(wù)承載網(wǎng)進行動態(tài)調(diào)整。當(dāng)感知到底層資源超負(fù)荷工作時，及時根據(jù)業(yè)務(wù)需求將緊要資源上的業(yè)務(wù)相應(yīng)地進行遷移。

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

4 基于拓?fù)涓兄姆?wù)承載網(wǎng)動態(tài)重構(gòu)算法

4.1 資源度量

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

定義5 資源關(guān)鍵度。資源關(guān)鍵度是指網(wǎng)絡(luò)中所有最短路徑之中經(jīng)過該資源的個數(shù)，包括節(jié)點關(guān)鍵度和鏈路關(guān)鍵度。歸一化表示為

其中，P為節(jié)點與節(jié)點之間最短路徑的集合，和分別表示經(jīng)過節(jié)點和鏈路的最短路徑的數(shù)量。

資源關(guān)鍵度是由拓?fù)鋵傩源_定的定值。資源關(guān)鍵度越高，說明該資源越重要，倘若這些節(jié)點或鏈路失效，對網(wǎng)絡(luò)的影響也就越大。因此在映射過程中，將優(yōu)先選擇關(guān)鍵度低的資源映射，確保網(wǎng)絡(luò)均衡可靠使用。

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

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

資源緊要度是隨著底層資源的使用情況而動態(tài)變化的，資源緊要度越大，說明該底層節(jié)點或鏈路上的負(fù)載越高，負(fù)擔(dān)越重。

4.2 重構(gòu)算法

4.2.1 DTAR算法思想描述

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

Step1 關(guān)鍵資源感知。由底層網(wǎng)絡(luò)拓?fù)鋵傩詤^(qū)分關(guān)鍵資源，計算得到從每個節(jié)點到其他所有節(jié)點的最短路徑。那么，通過該資源的最短路徑數(shù)越多，說明該資源越關(guān)鍵。

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

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

圖2給出了基于拓?fù)涓兄姆?wù)承載網(wǎng)動態(tài)重構(gòu)的示意。在圖2(a)中，服務(wù)承載網(wǎng)構(gòu)建請求RSCN1中的3個虛擬節(jié)點分別映射到底層節(jié)點{,,}。假設(shè)由底層拓?fù)鋵傩砸延嬎愠龉?jié)點及鏈路的資源關(guān)鍵度，其中，節(jié)點{,,}為關(guān)鍵節(jié)點，設(shè)置資源緊要度閾值為80%，其他非關(guān)鍵資源的緊要度閾值為90%，即對具有不同重要性的節(jié)點或鏈路設(shè)置不同的資源緊要度閾值，資源越重要，其閾值設(shè)置越低。此時由于RSCN1的構(gòu)建，感知到關(guān)鍵節(jié)點的資源緊要度已超過閾值80%，處于超負(fù)荷階段。

圖2(b)中，將映射到關(guān)鍵資源的服務(wù)承載網(wǎng)RSCN1的虛擬節(jié)點遷移到能夠滿足其業(yè)務(wù)需求的底層節(jié)點，并同時釋放節(jié)點上的相應(yīng)資源。

4.2.2 構(gòu)建目標(biāo)函數(shù)

高效構(gòu)建服務(wù)承載網(wǎng)即是在構(gòu)建過程中，最小化構(gòu)建花費。

那么，最小化構(gòu)建花費表示為

(11)

(12)

(14)

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

4.2.3 關(guān)鍵資源感知映射

DTAR算法為了更加合理地使用底層資源，由底層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)計算資源關(guān)鍵度，確定關(guān)鍵資源，并為關(guān)鍵資源設(shè)置緊要度閾值，為非關(guān)鍵資源設(shè)置緊要度閾值，且<，即確保關(guān)鍵資源不能被過度使用；動態(tài)感知底層資源狀態(tài)，計算資源緊要度；將底層資源按照資源關(guān)鍵度遞減排序；進行節(jié)點映射時，選擇能滿足業(yè)務(wù)需求的資源關(guān)鍵度最小的資源依序進行映射，均衡充分地使用底層網(wǎng)絡(luò)資源；而后以最短路徑進行鏈路映射。算法1和算法2分別給出了關(guān)鍵資源感知以及基于關(guān)鍵資源的服務(wù)承載網(wǎng)構(gòu)建的詳細(xì)步驟。

算法1 關(guān)鍵資源感知算法

過程：

2) 計算經(jīng)過任意中間節(jié)點最短路徑的條數(shù)()

if在SPT()中出現(xiàn)

()+1；

else未在SPT()中出現(xiàn)

()；

3) 計算經(jīng)過任意鏈路最短路徑的條數(shù)()

if在SPT()中出現(xiàn)

()+1；

else未在SPT()中出現(xiàn)

()；

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

6) 確定關(guān)鍵資源，并設(shè)置資源緊要度閾值；對非關(guān)鍵資源設(shè)置閾值。

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

輸出：

算法2 基于關(guān)鍵資源的服務(wù)承載網(wǎng)構(gòu)建算法

過程：

執(zhí)行2)；

無法構(gòu)建滿足業(yè)務(wù)需求的服務(wù)承載網(wǎng)絡(luò)。

end

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

計算和之間的最短路徑

end

4.2.4 緊要資源遷移

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

算法3 緊要資源遷移算法

過程：

if< 資源緊要度閾值

維持現(xiàn)有服務(wù)承載網(wǎng)構(gòu)建狀態(tài)；

else≥資源緊要度閾值

執(zhí)行2)。

if 節(jié)點過載

執(zhí)行3)；

else 鏈路過載

執(zhí)行5)。

3) 將過載節(jié)點上的已映射資源依據(jù)業(yè)務(wù)需求遷移。

if 時延敏感型

else 帶寬敏感型

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

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

5 算法仿真與分析

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

5.1 實驗設(shè)置

仿真實驗中的基礎(chǔ)網(wǎng)絡(luò)拓?fù)涫怯葿RITE工具隨機產(chǎn)生的100個節(jié)點組成的，節(jié)點連接率為0.5，節(jié)點與鏈路資源服從50~100的均勻分布。RSCN節(jié)點個數(shù)需求滿足2~10的均勻分布，鏈路帶寬需求、節(jié)點CPU能力及緩存容量均為0~30的均勻分布，節(jié)點連接率為0.5。業(yè)務(wù)構(gòu)建RSCN請求的到達過程服從時間單位為100，強度為10的泊松過程；每個RSCN的生存時間服從期望為1 000的指數(shù)分布。為了仿真結(jié)果的準(zhǔn)確性，本文共進行仿真實驗20次，所取結(jié)果為所有實驗結(jié)果的平均值。

5.2 服務(wù)承載網(wǎng)構(gòu)建成功率

圖3為隨服務(wù)承載網(wǎng)構(gòu)建請求數(shù)增多，不同算法的服務(wù)承載網(wǎng)構(gòu)建成功率。由于G-SP算法在映射時，并未將底層資源的拓?fù)鋵傩钥紤]其中，僅針對底層負(fù)載狀況進行處理，因此其服務(wù)承載網(wǎng)構(gòu)建成功率最低；而充分考慮了拓?fù)鋵傩缘腤D-VNE算法與DTAR算法將底層資源區(qū)別對待，均表現(xiàn)出較強的服務(wù)承載網(wǎng)構(gòu)建能力。當(dāng)?shù)讓淤Y源充足時，2種算法的構(gòu)建成功率相當(dāng)；但隨著服務(wù)承載網(wǎng)構(gòu)建請求數(shù)的增多，由于資源連接度并不能準(zhǔn)確全面地描述底層資源的重要性，因此DTAR算法的構(gòu)建成功率將略高于WD-VNE算法。

5.3 服務(wù)承載網(wǎng)構(gòu)建收益花費比

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

5.4 資源均衡度

所謂資源均衡度是指構(gòu)建的服務(wù)承載網(wǎng)對底層網(wǎng)絡(luò)資源的使用情況。分為網(wǎng)絡(luò)節(jié)點均衡度和網(wǎng)絡(luò)鏈路均衡度。

定義7 節(jié)點均衡度。服務(wù)承載網(wǎng)構(gòu)建時，整個底層網(wǎng)絡(luò)上所用節(jié)點的平均處理能力與最大處理能力的比值。

定義8 鏈路均衡度。構(gòu)建服務(wù)承載網(wǎng)時，整個底層網(wǎng)絡(luò)上所用鏈路的平均利用率與最大鏈路利用率的比值。

(16)

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

6 結(jié)束語

高效地使用底層網(wǎng)絡(luò)資源，以期最大化構(gòu)建成功率，是服務(wù)承載網(wǎng)構(gòu)建的永恒主題。基于此，本文提出了一種基于拓?fù)涓兄姆?wù)承載網(wǎng)動態(tài)重構(gòu)算法。DTAR算法使用通過節(jié)點或鏈路的最短路徑數(shù)衡量資源重要性，給出了“資源關(guān)鍵度”的定義，并依據(jù)資源關(guān)鍵度對資源降序映射；定義了“資源緊要度”指標(biāo)對底層資源使用狀態(tài)進行刻畫，并將動態(tài)感知到的緊要資源進行優(yōu)化配置。仿真結(jié)果表明：在與算法G-SP和WD-VNE進行的性能對比中，DTAR算法在提高構(gòu)建成功率的同時，具有較高的收益花費比和資源均衡度。

[1] 蘭巨龍, 程東年, 胡宇翔. 可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究[J]. 通信學(xué)報, 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

國家重點基礎(chǔ)研究發(fā)展計劃（“973”計劃）基金資助項目（No.2012CB315901,No.2013CB329104）；國家自然科學(xué)基金資助項目（No.61372121）；國家高技術(shù)研究發(fā)展計劃（“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-），女，天津人，博士，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心講師，主要研究方向為寬帶信息網(wǎng)絡(luò)和下一代網(wǎng)絡(luò)。

蘭巨龍（1962-），男，河北張北人，博士，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心總工程師、教授、博士生導(dǎo)師，主要研究方向為新一代信息網(wǎng)絡(luò)關(guān)鍵理論與技術(shù)。

張震（1985-），男，山東濟寧人，博士，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心講師，主要研究方向為網(wǎng)絡(luò)測量技術(shù)。