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

梁寧寧，蘭巨龍，張震

?

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

梁寧寧，蘭巨龍，張震

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

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

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

1 引言

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

為此，可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)通過(guò)為用戶構(gòu)建可重構(gòu)服務(wù)承載網(wǎng)的方式，實(shí)現(xiàn)其對(duì)功能可動(dòng)態(tài)重構(gòu)和擴(kuò)展的底層物理網(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ù)?、資源狀態(tài)等條件優(yōu)化考慮，構(gòu)建出的多個(gè)在底層物理資源上存在交集，能夠提供不同服務(wù)能力的承載子網(wǎng)，如圖1所示。

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

2 相關(guān)研究

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

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

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

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

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

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

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

鏈路映射(3)

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

1) 高效利用底層資源

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

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

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

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

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

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

(7)

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

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

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

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

4.1 資源度量

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

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

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

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

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

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

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

4.2 重構(gòu)算法

4.2.1 DTAR算法思想描述

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

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

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

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

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

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

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

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

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

(11)

(12)

(14)

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

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

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

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

過(guò)程：

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

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

()+1；

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

()；

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

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

()+1；

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

()；

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

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

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

輸出：

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

過(guò)程：

執(zhí)行2)；

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

end

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

計(jì)算和之間的最短路徑

end

4.2.4 緊要資源遷移

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

算法3 緊要資源遷移算法

過(guò)程：

if< 資源緊要度閾值

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

else≥資源緊要度閾值

執(zhí)行2)。

if 節(jié)點(diǎn)過(guò)載

執(zhí)行3)；

else 鏈路過(guò)載

執(zhí)行5)。

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

if 時(shí)延敏感型

else 帶寬敏感型

4) 對(duì)成功遷移節(jié)點(diǎn)以最短路徑進(jìn)行鏈路映射。

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

5 算法仿真與分析

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

5.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

5.4 資源均衡度

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

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

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

(16)

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

6 結(jié)束語(yǔ)

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

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

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

蘭巨龍（1962-），男，河北張北人，博士，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心總工程師、教授、博士生導(dǎo)師，主要研究方向?yàn)樾乱淮畔⒕W(wǎng)絡(luò)關(guān)鍵理論與技術(shù)。

張震（1985-），男，山東濟(jì)寧人，博士，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心講師，主要研究方向?yàn)榫W(wǎng)絡(luò)測(cè)量技術(shù)。