基于拓?fù)浞指钆c聚類分析的虛擬軟件定義網(wǎng)絡(luò)映射算法

陳 港，孟相如，康巧燕，陽勇

（空軍工程大學(xué)信息與導(dǎo)航學(xué)院，西安 710077）

0 引言

網(wǎng)絡(luò)虛擬化技術(shù)通過將網(wǎng)絡(luò)服務(wù)和網(wǎng)絡(luò)基礎(chǔ)設(shè)施在邏輯上進(jìn)行解耦，降低了網(wǎng)絡(luò)服務(wù)的局限性，增強(qiáng)了部署靈活性，實(shí)現(xiàn)了網(wǎng)絡(luò)資源的可靠管控，加速了網(wǎng)絡(luò)架構(gòu)和技術(shù)上的創(chuàng)新［1］。由于基于傳統(tǒng)網(wǎng)絡(luò)的網(wǎng)絡(luò)虛擬化存在諸多問題和限制，專家學(xué)者將軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）引入網(wǎng)絡(luò)虛擬化，形成虛擬軟件定義網(wǎng)絡(luò)（virtual SDN，vSDN）［2-4］，其中的一個(gè)關(guān)鍵技術(shù)問題是虛擬網(wǎng)絡(luò)映射。作為vSDN 中的映射，相較于一般的虛擬網(wǎng)絡(luò)映射［5］，它的映射約束、優(yōu)化目標(biāo)、網(wǎng)絡(luò)復(fù)雜度都具有更高的要求［6-7］。

Tan 等［8］考慮網(wǎng)絡(luò)時(shí)延和控制器與轉(zhuǎn)發(fā)設(shè)備之間的不相交路徑數(shù)，提高vSDN的生存性并降低網(wǎng)絡(luò)時(shí)延；Kuang等［9］考慮了交換機(jī)的流量和內(nèi)存約束，節(jié)點(diǎn)映射策略為將節(jié)點(diǎn)根據(jù)其重要度指標(biāo)進(jìn)行樹形拓?fù)涞慕敌蚺帕泻笫褂秘澙匪惴ㄟM(jìn)行匹配映射，鏈路映射策略為選擇帶寬富裕度高、跳數(shù)少的鏈路優(yōu)先映射；冉金鵬等［10］采用優(yōu)化的果蠅算法進(jìn)行映射方案的求解，在負(fù)載均衡、請(qǐng)求接受率和控制延遲等指標(biāo)上取得較好效果；王健等［11］基于蟻群混合遺傳算法映射節(jié)點(diǎn)，利用K-最短路徑算法映射鏈路，提高了接受率，并較好地改善了節(jié)點(diǎn)和鏈路的平均利用率以及映射的收益開銷比。文獻(xiàn)［8-11］中將節(jié)點(diǎn)和鏈路映射分開考慮，沒有注意到節(jié)點(diǎn)與鏈路之間的關(guān)聯(lián)性。Li等［12］提出了一種拓?fù)涓兄奶摂M軟件定義網(wǎng)絡(luò)映射方法：節(jié)點(diǎn)映射時(shí)，采用貪婪算法優(yōu)先映射虛擬網(wǎng)絡(luò)和物理網(wǎng)絡(luò)中資源度高的節(jié)點(diǎn)；鏈路映射時(shí)，分別采用K-最短路徑算法和多商品流算法映射控制鏈路和數(shù)據(jù)鏈路，采用節(jié)點(diǎn)重映射提高映射成功率。該方案有效提升了映射效率和收益開銷比，通過在鏈路映射失敗時(shí)采用節(jié)點(diǎn)重映射的方式較為粗略地考慮了節(jié)點(diǎn)與鏈路之間的拓?fù)渑c資源關(guān)聯(lián)性，但其算法開銷較大，同時(shí)未考慮vSDN 中交換機(jī)以及控制器內(nèi)存約束。Yan 等［13］提出了一種基于虛擬軟件定義網(wǎng)絡(luò)的啟發(fā)式要素感知的資源高效利用算法，該方案基于K-Means 聚類進(jìn)行節(jié)點(diǎn)的匹配映射，采用K-最短路徑算法完成鏈路映射。該方案提升了請(qǐng)求接受率，降低了通信延遲，但其僅根據(jù)節(jié)點(diǎn)的計(jì)算能力、內(nèi)存以及總的連接帶寬這三個(gè)要素進(jìn)行聚類匹配，忽略了節(jié)點(diǎn)與鏈路之間的關(guān)聯(lián)性，未考慮網(wǎng)絡(luò)的拓?fù)涮卣鳌?/p>

總結(jié)發(fā)現(xiàn)，大部分基于vSDN的映射算法沒有充分考慮節(jié)點(diǎn)與鏈路之間的相關(guān)性。虛擬網(wǎng)絡(luò)和物理網(wǎng)絡(luò)中的節(jié)點(diǎn)與鏈路之間存在著一定的拓?fù)浣Y(jié)構(gòu)以及對(duì)應(yīng)的計(jì)算資源和帶寬資源，分開考慮節(jié)點(diǎn)映射和鏈路映射時(shí)相當(dāng)于割裂了兩者之間在拓?fù)浣Y(jié)構(gòu)和資源數(shù)值之間的關(guān)聯(lián)性。為在vSDN 映射過程中更全面地考慮節(jié)點(diǎn)與鏈路約束，以及節(jié)點(diǎn)與鏈路之間的相關(guān)性，本文提出了一種基于網(wǎng)絡(luò)拓?fù)浞指钆c聚類分析的虛擬軟件定義網(wǎng)絡(luò)映射算法（Topology Segmentation and Clustering Analysis-vSDN mapping algorithm，TSCA-vSDN）。本文算法的主要思路如下：1）通過將物理網(wǎng)絡(luò)和虛擬請(qǐng)求網(wǎng)絡(luò)按照交換機(jī)到控制器的最短跳數(shù)值展開為樹狀拓?fù)鋱D，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)拓?fù)涞母兄头指?，并依?jù)節(jié)點(diǎn)的拓?fù)鋵傩詤^(qū)分出關(guān)鍵節(jié)點(diǎn)和鏈路，避免出現(xiàn)關(guān)鍵節(jié)點(diǎn)或鏈路過早高負(fù)荷映射，以提高整體的請(qǐng)求接受率；2）通過定義節(jié)點(diǎn)資源度和網(wǎng)絡(luò)資源度以及節(jié)點(diǎn)緊密度，使用聚類算法依據(jù)節(jié)點(diǎn)的多項(xiàng)屬性值進(jìn)行聚類分析，實(shí)現(xiàn)對(duì)底層物理網(wǎng)絡(luò)資源的動(dòng)態(tài)感知；3）通過將鏈路約束分散到節(jié)點(diǎn)帶寬資源以及節(jié)點(diǎn)的度約束考量，對(duì)不符合鏈路要求的節(jié)點(diǎn)進(jìn)行重映射，充分考慮節(jié)點(diǎn)與鏈路之間的資源與拓?fù)湎嚓P(guān)性。仿真結(jié)果表明，該算法有效地提升了基于SDN架構(gòu)的虛擬網(wǎng)絡(luò)映射在較低連通概率物理網(wǎng)絡(luò)下的請(qǐng)求接受率。

1 網(wǎng)絡(luò)模型與評(píng)價(jià)指標(biāo)

1.1 網(wǎng)絡(luò)模型

本文假設(shè)處理的物理網(wǎng)絡(luò)和虛擬請(qǐng)求網(wǎng)絡(luò)拓?fù)鋱D中任意兩點(diǎn)間直連邊的條數(shù)最多為1 條，物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)請(qǐng)求拓?fù)涠紴榉瞧椒驳暮?jiǎn)單連通圖。本文假設(shè)控制器為帶內(nèi)部署，且控制器不參與交換機(jī)之間的數(shù)據(jù)轉(zhuǎn)發(fā)，只負(fù)責(zé)控制信令的分發(fā)。

1.1.1 物理網(wǎng)絡(luò)

1.1.3 網(wǎng)絡(luò)特征分析

為了對(duì)不同的網(wǎng)絡(luò)作出區(qū)分，以更好地選擇適配的映射策略，本文針對(duì)物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)給出以下一系列定量的評(píng)價(jià)指標(biāo)。

定義節(jié)點(diǎn)資源度為p(ni)，為減小各節(jié)點(diǎn)因三項(xiàng)資源屬性值存在的偏差所導(dǎo)致的節(jié)點(diǎn)資源度誤差，設(shè)立系數(shù)α、β、γ，有：

參考文獻(xiàn)［12］，定義網(wǎng)絡(luò)Gi中節(jié)點(diǎn)ni的緊密度為CL(ni)，該名詞表征節(jié)點(diǎn)在拓?fù)鋱D中的中心程度。令緊密度CL(ni)為節(jié)點(diǎn)到其余各節(jié)點(diǎn)最短跳數(shù)倒數(shù)的和，計(jì)算式如下：

式（7）表明，到其余各節(jié)點(diǎn)最短跳數(shù)倒數(shù)的和越大的節(jié)點(diǎn)，其緊密度就越高，反之就越低。

定義節(jié)點(diǎn)控制中心度為CC(ni)，表征拓?fù)渚W(wǎng)絡(luò)中接近控制器的節(jié)點(diǎn)中心程度，以方便后續(xù)虛擬網(wǎng)絡(luò)根節(jié)點(diǎn)的映射。令節(jié)點(diǎn)控制中心度CC(ni)為節(jié)點(diǎn)緊密度和交換機(jī)節(jié)點(diǎn)到最近控制器節(jié)點(diǎn)最短跳數(shù)之間的比值，即：

式（8）表明，緊密度相同的節(jié)點(diǎn)中，到最近控制器節(jié)點(diǎn)最短跳數(shù)越小的節(jié)點(diǎn)，其節(jié)點(diǎn)控制中心度就越高，反之則越低。

定義節(jié)點(diǎn)關(guān)鍵度為節(jié)點(diǎn)控制中心度與節(jié)點(diǎn)的度之間的比值，記第i個(gè)節(jié)點(diǎn)的關(guān)鍵度為CR(ni)。為加快算法收斂，將關(guān)鍵度高于節(jié)點(diǎn)關(guān)鍵度平均值20%的節(jié)點(diǎn)視為關(guān)鍵節(jié)點(diǎn)。關(guān)鍵鏈路的篩選標(biāo)準(zhǔn)為：關(guān)鍵節(jié)點(diǎn)直連的鏈路。節(jié)點(diǎn)關(guān)鍵度計(jì)算式為：

式（9）表明，節(jié)點(diǎn)控制中心度相同的節(jié)點(diǎn)中，度越小的節(jié)點(diǎn)，其節(jié)點(diǎn)關(guān)鍵度就越高，反之則越低。

1.2 虛擬網(wǎng)絡(luò)映射模型

虛擬網(wǎng)絡(luò)映射模型可抽象為帶權(quán)重的無向圖Gv到Gs子集的映射Gv(i)→Gs(i)∈Gs。該映射定義為將虛擬請(qǐng)求網(wǎng)絡(luò)中的虛擬節(jié)點(diǎn)和鏈路對(duì)應(yīng)映射到物理網(wǎng)絡(luò)中的物理節(jié)點(diǎn)和路徑，在映射過程中，需要滿足節(jié)點(diǎn)的CPU 約束，流表空間TCAM 約束，以及鏈路的帶寬（BW）約束。本文采用兩階段映射法，先映射節(jié)點(diǎn)后映射鏈路，如圖1所示。

圖1 虛擬SDN映射模型Fig.1 Virtual SDN mapping model

1.2.1 節(jié)點(diǎn)映射

對(duì)于同一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，每一個(gè)虛擬節(jié)點(diǎn)必須映射到不同的物理節(jié)點(diǎn)上，但同一個(gè)物理節(jié)點(diǎn)上可以存在多個(gè)不同虛擬網(wǎng)絡(luò)請(qǐng)求的虛擬節(jié)點(diǎn)。由于物理SDN 控制器節(jié)點(diǎn)采用帶內(nèi)部署，所以在映射虛擬交換機(jī)節(jié)點(diǎn)和虛擬SDN 控制器節(jié)點(diǎn)時(shí)可以將其統(tǒng)一考慮為虛擬節(jié)點(diǎn)映射。假設(shè)每一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求有且只有一個(gè)虛擬SDN 控制器負(fù)責(zé)該網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)和流量控制。如果虛擬節(jié)點(diǎn)映射到物理節(jié)點(diǎn)則為Xij=1；否則Xij=0。虛擬節(jié)點(diǎn)nv映射到物理節(jié)點(diǎn)ns的過程表示為MN，即：

約束條件如下：

其中：式（11）表示待映射虛擬節(jié)點(diǎn)CPU 資源需求不能大于被映射物理節(jié)點(diǎn)的剩余CPU 資源；式（12）表示待映射虛擬節(jié)點(diǎn)TCAM 資源需求不能大于被映射物理節(jié)點(diǎn)的剩余TCAM 資源；式（13）表示同一虛擬網(wǎng)絡(luò)中每一個(gè)虛擬節(jié)點(diǎn)只能映射到一個(gè)物理節(jié)點(diǎn)，任意物理節(jié)點(diǎn)至多承載同一個(gè)虛擬網(wǎng)絡(luò)中一個(gè)虛擬節(jié)點(diǎn)。

1.2.2 鏈路映射

對(duì)于虛擬網(wǎng)絡(luò)請(qǐng)求中的某一條鏈路而言，它可以對(duì)應(yīng)映射到物理網(wǎng)絡(luò)中的一條具體的鏈路，也可以映射到物理網(wǎng)絡(luò)中由多條鏈路組成的一條具體的路徑。為了在避免歧義的同時(shí)更準(zhǔn)確地描述鏈路的映射，將虛擬鏈路的映射過程定義為虛擬鏈路與該虛擬鏈路兩端節(jié)點(diǎn)映射后對(duì)應(yīng)物理節(jié)點(diǎn)間鏈路或路徑的映射。定義底層物理網(wǎng)絡(luò)兩點(diǎn)間任一條非閉環(huán)的路徑為。將虛擬鏈路ev映射到物理鏈路es的過程記為ME，即：

約束條件如下：

式（15）表示待映射的虛擬鏈路帶寬需求不能大于被映射物理節(jié)點(diǎn)的剩余帶寬資源。

1.3 評(píng)價(jià)指標(biāo)

定義1虛擬網(wǎng)絡(luò)請(qǐng)求接受率。

參考文獻(xiàn)［10］，定義為長期的時(shí)間段T中成功映射的虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量與收到的虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量的比值，表示為AR，如式（16）所示：

其中：vSDNRe(t)表示在時(shí)刻t成功映射的虛擬網(wǎng)絡(luò)個(gè)數(shù)；vSDNGe(t)表示在時(shí)刻t收到的虛擬網(wǎng)絡(luò)個(gè)數(shù)。

2 虛擬SDN請(qǐng)求映射算法

本章首先介紹拓?fù)浞指钗锢砭W(wǎng)絡(luò)，并計(jì)算物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)的拓?fù)浜唾Y源指標(biāo)，然后對(duì)物理網(wǎng)絡(luò)節(jié)點(diǎn)基于拓?fù)浜唾Y源指標(biāo)進(jìn)行聚類分析，將虛擬網(wǎng)絡(luò)的節(jié)點(diǎn)根據(jù)物理節(jié)點(diǎn)聚類分析結(jié)果進(jìn)行匹配映射，并在節(jié)點(diǎn)映射前進(jìn)行相關(guān)的鏈路約束判斷，節(jié)點(diǎn)映射成功后再映射鏈路，最后對(duì)算法的時(shí)間復(fù)雜度進(jìn)行計(jì)算說明。

2.1 物理網(wǎng)絡(luò)拓?fù)浞指詈唾Y源指標(biāo)計(jì)算

物理網(wǎng)絡(luò)拓?fù)浞指詈唾Y源指標(biāo)計(jì)算步驟如下：

圖2 物理網(wǎng)絡(luò)拓?fù)浞指钍纠鼺ig.2 Example of physical network topology segmentation

圖3 樹形拓?fù)渚W(wǎng)絡(luò)示例Fig.3 Example of tree topology network

圖4 延展后的樹形拓?fù)鋱DFig.4 Extended tree topology diagram

4）計(jì)算物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)的節(jié)點(diǎn)度d(ni)、緊密度CL(ni)、控制中心度CC(ni)。將虛擬網(wǎng)絡(luò)中緊密度最高的節(jié)點(diǎn)作為根節(jié)點(diǎn)，其余節(jié)點(diǎn)按照到該根節(jié)點(diǎn)的最短跳數(shù)作為層數(shù)轉(zhuǎn)化為樹形拓?fù)渚W(wǎng)絡(luò)。

5）計(jì)算物理樹形拓?fù)渚W(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)和關(guān)鍵鏈路，在映射時(shí)只有當(dāng)關(guān)鍵節(jié)點(diǎn)的剩余節(jié)點(diǎn)資源度與物理子拓?fù)渚W(wǎng)絡(luò)中平均節(jié)點(diǎn)資源度的比值大于一定值時(shí)才可以被映射，具體比值記為ratio，通過后續(xù)實(shí)驗(yàn)得出。但關(guān)鍵鏈路不受影響，即當(dāng)關(guān)鍵節(jié)點(diǎn)不被映射時(shí)依舊可以充當(dāng)其余節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)，與其直連的關(guān)鍵鏈路可以被虛擬鏈路映射。為避免出現(xiàn)關(guān)鍵鏈路過早耗盡帶寬的情況，在鏈路映射時(shí)設(shè)置鏈路權(quán)重隨鏈路剩余可用帶寬降低而提高。

2.2 節(jié)點(diǎn)聚類分析和鏈路映射

為了充分利用物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)的拓?fù)湫畔⒁约百Y源信息，首先針對(duì)物理網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)渲笜?biāo)進(jìn)行聚類分析，分割為k個(gè)節(jié)點(diǎn)拓?fù)鋵傩韵嘟募?；接著，?jì)算虛擬節(jié)點(diǎn)到各聚類中心的歐氏距離，選取歐氏距離值最小的集合作為虛擬節(jié)點(diǎn)待映射的物理節(jié)點(diǎn)集合；然后，按照虛擬網(wǎng)絡(luò)的樹形拓?fù)渚W(wǎng)絡(luò)，從根節(jié)點(diǎn)開始依據(jù)廣度搜索順序映射虛擬節(jié)點(diǎn)，并計(jì)算虛擬節(jié)點(diǎn)和選取集合中所有節(jié)點(diǎn)的資源指標(biāo)的歐氏距離，選取歐氏距離值最小的物理節(jié)點(diǎn)作為虛擬節(jié)點(diǎn)的映射節(jié)點(diǎn)；最后，除映射虛擬網(wǎng)絡(luò)根節(jié)點(diǎn)外，對(duì)每一個(gè)虛擬網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行鏈路約束初步判斷，當(dāng)所有節(jié)點(diǎn)鏈路約束符合后開始鏈路映射，若仍出現(xiàn)矛盾則進(jìn)行節(jié)點(diǎn)重映射，直至映射成功或遍歷后映射失敗。

映射算法流程如圖5 所示，圖中否1、否2、否3、否4 代表不同的轉(zhuǎn)折條件，分別為該節(jié)點(diǎn)不滿足約束但集合ki未遍歷、集合ki已遍歷但k個(gè)聚類集合未遍歷、k個(gè)集合已遍歷但拓?fù)渚W(wǎng)絡(luò)未遍歷、都已遍歷未找到合適節(jié)點(diǎn)。節(jié)點(diǎn)映射時(shí)，首先選擇合適的物理拓?fù)渚W(wǎng)絡(luò)并映射虛擬網(wǎng)絡(luò)的控制器，然后映射虛擬網(wǎng)絡(luò)交換機(jī)節(jié)點(diǎn)。

圖5 映射算法流程Fig.5 Flow chart of mapping algorithm

映射控制器時(shí)，首先計(jì)算物理子拓?fù)渚W(wǎng)絡(luò)與虛擬網(wǎng)絡(luò)的優(yōu)先級(jí)pr，然后計(jì)算優(yōu)先級(jí)變量pr()（簡(jiǎn)記為prs）和pr()（簡(jiǎn)記為prv）的歐氏距離d0，優(yōu)先考量歐氏距離值最小的物理拓?fù)渚W(wǎng)絡(luò)映射虛擬網(wǎng)絡(luò)。

其中各變量計(jì)算式如下：

若該物理拓?fù)渚W(wǎng)絡(luò)控制器節(jié)點(diǎn)滿足虛擬網(wǎng)絡(luò)控制器節(jié)點(diǎn)的資源約束，則確認(rèn)虛擬網(wǎng)絡(luò)控制器映射到該網(wǎng)絡(luò)的物理控制器，若不滿足則順序考量下一個(gè)物理子拓?fù)渚W(wǎng)絡(luò)，直至遍歷完全都不滿足約束時(shí)則映射失敗。

首先選取d1值最小的節(jié)點(diǎn)集合cluster(j)(j∈k)作為該虛擬節(jié)點(diǎn)的待映射物理節(jié)點(diǎn)集合，然后根據(jù)物理節(jié)點(diǎn)和虛擬節(jié)點(diǎn)的C(ni)、TC(ni)、Bw(ni)指標(biāo)，在集合cluster(j)中計(jì)算虛擬節(jié)點(diǎn)和物理節(jié)點(diǎn)三個(gè)資源指標(biāo)的歐氏距離d2，將集合中的節(jié)點(diǎn)按照歐氏距離d2升序排列。

其中各變量計(jì)算式如下：

具體映射虛擬網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)，首先映射虛擬網(wǎng)絡(luò)的根節(jié)點(diǎn)，然后依照對(duì)樹形拓?fù)渚W(wǎng)絡(luò)的廣度搜索順序依次進(jìn)行虛擬節(jié)點(diǎn)的映射。具體過程為：排除掉物理控制器節(jié)點(diǎn)，然后針對(duì)關(guān)鍵節(jié)點(diǎn)判斷關(guān)鍵節(jié)點(diǎn)的節(jié)點(diǎn)資源度Rp()是否小于該物理子拓?fù)渚W(wǎng)絡(luò)節(jié)點(diǎn)資源度平均值的一半，若小于則跳過該關(guān)鍵節(jié)點(diǎn)；否則繼續(xù)考察物理節(jié)點(diǎn)的資源是否滿足虛擬節(jié)點(diǎn)的資源約束。若考察的物理節(jié)點(diǎn)滿足虛擬節(jié)點(diǎn)的資源約束則對(duì)節(jié)點(diǎn)進(jìn)行鏈路約束初步判斷，如果符合判斷則將該物理節(jié)點(diǎn)作為該虛擬節(jié)點(diǎn)的映射節(jié)點(diǎn)；若不滿足則順序考察下一個(gè)物理節(jié)點(diǎn)。若遍歷該集合cluster(j)都無法找到符合約束的節(jié)點(diǎn)則更換物理拓?fù)渚W(wǎng)絡(luò)。若遍歷所有物理拓?fù)渚W(wǎng)絡(luò)仍無法找到符合約束的物理節(jié)點(diǎn)，則表明無法成功映射該虛擬網(wǎng)絡(luò)所有節(jié)點(diǎn)，即映射失敗。其中，鏈路約束初步判斷的資源需求方為待映射虛擬節(jié)點(diǎn)與上層虛擬節(jié)點(diǎn)間的鏈路帶寬需求，資源供給方為待被映射物理節(jié)點(diǎn)與虛擬網(wǎng)絡(luò)根節(jié)點(diǎn)已映射物理節(jié)點(diǎn)間的鏈路帶寬資源。

3）鏈路映射時(shí)，采用K-最短路徑算法，在計(jì)算兩節(jié)點(diǎn)間最短路徑時(shí)，將鏈路權(quán)重設(shè)置為物理網(wǎng)絡(luò)鏈路帶寬最大值與鏈路剩余帶寬的差值加一，以規(guī)避關(guān)鍵鏈路被提前過度映射而降低請(qǐng)求接受率。如果沒有找到滿足需求的鏈路，在物理拓?fù)湮幢闅v完時(shí)采用下一個(gè)物理子拓?fù)渚W(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)重映射，若已遍歷所有物理子拓?fù)渚W(wǎng)絡(luò)，則進(jìn)行一次節(jié)點(diǎn)重映射，并盡量規(guī)避之前已被選擇的物理節(jié)點(diǎn)，若仍失敗則丟棄該虛擬網(wǎng)絡(luò)請(qǐng)求。如果映射成功則反饋成功。

4）本文提出的TSCA-vSDN 算法，輸入為物理拓?fù)渚W(wǎng)絡(luò)和虛擬拓?fù)渚W(wǎng)絡(luò)，輸出為節(jié)點(diǎn)映射表單和鏈路映射表單。具體內(nèi)容如算法1（TSCA-vSDN）所示，其中第1）～4）行計(jì)算物理網(wǎng)絡(luò)中交換機(jī)到控制器的最短跳數(shù)，并進(jìn)行拓?fù)浞指?；?）～8）行計(jì)算各子拓?fù)渚W(wǎng)絡(luò)的優(yōu)先度；第9）～12）行進(jìn)行聚類分析；第13）～27）行根據(jù)聚類結(jié)果和節(jié)點(diǎn)資源屬性進(jìn)行節(jié)點(diǎn)匹配映射，輸出節(jié)點(diǎn)映射表單；第28）～34）行采用K-最短路徑算法進(jìn)行鏈路映射，輸出鏈路映射表單。

算法1 TSCA-vSDN。

2.3 算法時(shí)間復(fù)雜度計(jì)算

3 算法評(píng)估

在相同的底層物理網(wǎng)絡(luò)環(huán)境下，面對(duì)不同的虛擬網(wǎng)絡(luò)請(qǐng)求，針對(duì)算法TSCA-vSDN 的請(qǐng)求接受率指標(biāo)進(jìn)行仿真實(shí)驗(yàn)分析，并與算法KCL-vSDN和To-vSDN進(jìn)行對(duì)比。三種算法的簡(jiǎn)要描述如下。

1）算法TSCA-vSDN。節(jié)點(diǎn)映射時(shí)，首先基于K-means 聚類方法對(duì)與虛擬節(jié)點(diǎn)拓?fù)鋮?shù)比例相似的候選物理節(jié)點(diǎn)進(jìn)行聚類，然后根據(jù)節(jié)點(diǎn)的計(jì)算資源選取比例最接近的進(jìn)行映射；鏈路映射時(shí)，選用K-最短路徑算法，在鏈路映射受阻時(shí)采用節(jié)點(diǎn)重映射提高映射成功率；算法映射單個(gè)虛擬網(wǎng)絡(luò)的時(shí)間復(fù)雜度為

2）算法KCL-vSDN。節(jié)點(diǎn)映射時(shí)，首先基于K-means 聚類方法對(duì)與虛擬節(jié)點(diǎn)資源比例相似的候選物理節(jié)點(diǎn)進(jìn)行聚類，然后根據(jù)網(wǎng)絡(luò)演算得到的控制要素從集群中選擇出最優(yōu)的物理節(jié)點(diǎn)進(jìn)行匹配映射；鏈路映射時(shí)選用K-最短路徑算法［13］；算法映射單個(gè)虛擬網(wǎng)絡(luò)的時(shí)間復(fù)雜度為

3）算法To-vSDN。節(jié)點(diǎn)映射時(shí)，采用貪婪算法優(yōu)先映射虛擬網(wǎng)絡(luò)和物理網(wǎng)絡(luò)中資源度高的節(jié)點(diǎn)；鏈路映射時(shí)，先采用K-最短路徑算法映射控制器到交換機(jī)的虛擬控制鏈路，然后采用多商品流算法映射其余虛擬數(shù)據(jù)鏈路，在鏈路映射受阻時(shí)采用節(jié)點(diǎn)重映射增加映射成功率［12］；算法映射單個(gè)虛擬網(wǎng)絡(luò)的時(shí)間復(fù)雜度為

3.1 仿真環(huán)境設(shè)置

通過文獻(xiàn)［14-16］及本文仿真實(shí)驗(yàn)發(fā)現(xiàn)不同的底層物理網(wǎng)絡(luò)以及不同的虛擬網(wǎng)絡(luò)請(qǐng)求，對(duì)同一算法的性能有著較大的影響。參考數(shù)據(jù)中心常用拓?fù)?，采用facebook 數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)洌ê?jiǎn)記為topo-facebook）和fat-tree 網(wǎng)絡(luò)拓?fù)洌ê?jiǎn)記為topo-fat-tree）等兩類常見底層物理拓?fù)浣Y(jié)構(gòu)，以及依靠網(wǎng)絡(luò)節(jié)點(diǎn)和節(jié)點(diǎn)連通概率（KP）隨機(jī)生成的拓?fù)渚W(wǎng)絡(luò)（簡(jiǎn)記為topomesh），分別作為仿真環(huán)境的底層物理網(wǎng)絡(luò)。

topo-facebook 和topo-fat-tree 都有其較為固定的結(jié)構(gòu)，在給定節(jié)點(diǎn)數(shù)量的前提下，其鏈路數(shù)量是固定的，為方便對(duì)照，本文設(shè)置三類物理網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)都為200。實(shí)驗(yàn)中鏈路帶寬、交換機(jī)計(jì)算資源、存儲(chǔ)資源等數(shù)據(jù)參考文獻(xiàn)［17］進(jìn)行設(shè)置，具體見表1。

表1 底層物理網(wǎng)絡(luò)分類及參數(shù)設(shè)置Tab.1 Classification and parameter setting of underlying physical network

鏈路帶寬設(shè)為40 Gb/s，交換機(jī)節(jié)點(diǎn)計(jì)算資源CPU 為12×103，存儲(chǔ)資源TCAM 為250 × 103，控制器節(jié)點(diǎn)計(jì)算資源為交換機(jī)的4 倍。本文將其節(jié)點(diǎn)總數(shù)設(shè)為200，控制器個(gè)數(shù)為4。topo-mesh 為隨機(jī)網(wǎng)絡(luò)，為考察物理網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)以及連通概率對(duì)算法映射性能的影響，設(shè)定節(jié)點(diǎn)總數(shù)分別為200，控制器數(shù)量為4；KP為0.02 和0.03；數(shù)據(jù)鏈路帶寬以及計(jì)算資源CPU 和存儲(chǔ)資源TCAM 服從均勻分布，即，單位103］；控制鏈路帶寬為40 × 103，控制器計(jì)算資源為交換機(jī)計(jì)算資源的4倍。底層物理網(wǎng)絡(luò)分類見表1。

虛擬網(wǎng)絡(luò)采用topo-mesh 隨機(jī)網(wǎng)絡(luò)，考慮到虛擬網(wǎng)絡(luò)的大小不確定性以及持續(xù)時(shí)長不確定性，將其節(jié)點(diǎn)總數(shù)N設(shè)為N～U［2，20］的均勻分布，KP為0.5，將其持續(xù)時(shí)長T設(shè)為T～P(λ)，λ=120，240，360，480 的泊松分布（單位為s）。數(shù)據(jù)鏈路帶寬、節(jié)點(diǎn)計(jì)算資源CPU 和存儲(chǔ)資源TCAM 服從均勻分布，，單位為Mb/s，～U[5× 103，20 × 103]；控制鏈路帶寬為10 Mb/s，控制器計(jì)算資源和存儲(chǔ)資源為交換機(jī)的2倍。

3.2 結(jié)果分析

本文采用控制變量法共進(jìn)行了三組實(shí)驗(yàn)。實(shí)驗(yàn)一在固定物理環(huán)境和虛擬網(wǎng)絡(luò)請(qǐng)求生存時(shí)長的條件下，改變關(guān)鍵節(jié)點(diǎn)的剩余節(jié)點(diǎn)資源度與物理子拓?fù)渚W(wǎng)絡(luò)中平均節(jié)點(diǎn)資源度的比值ratio，探究使得算法TSCA-vSDN 的請(qǐng)求接受率最高的ratio值；實(shí)驗(yàn)二與實(shí)驗(yàn)三在固定物理網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)和相同連通概率（KP）的條件下，改變物理網(wǎng)絡(luò)類型和虛擬網(wǎng)絡(luò)請(qǐng)求生存時(shí)長，探究物理網(wǎng)絡(luò)類型和虛擬網(wǎng)絡(luò)請(qǐng)求生存時(shí)長對(duì)三種算法請(qǐng)求接受率的影響；同時(shí)實(shí)驗(yàn)三在實(shí)驗(yàn)二的基礎(chǔ)上，更換了一種物理網(wǎng)絡(luò)類型以及KP，探究不同網(wǎng)絡(luò)類型、不同物理網(wǎng)絡(luò)KP對(duì)三種算法請(qǐng)求接受率的影響。

3.2.1 實(shí)驗(yàn)一

基于topo-mesh（KP=0.026）網(wǎng)絡(luò)拓?fù)?，在?dāng)關(guān)鍵節(jié)點(diǎn)的剩余節(jié)點(diǎn)資源度與物理子拓?fù)渚W(wǎng)絡(luò)中平均節(jié)點(diǎn)資源度的比值ratio分別取0.1、0.3、0.5、0.7、0.9，且生存時(shí)長為480 時(shí)，對(duì)算法TSCA-vSDN的請(qǐng)求接受率進(jìn)行分析。

由實(shí)驗(yàn)一的圖6 可以看出，當(dāng)關(guān)鍵節(jié)點(diǎn)的剩余節(jié)點(diǎn)資源度與物理子拓?fù)渚W(wǎng)絡(luò)中平均節(jié)點(diǎn)資源度的比值取0.5 時(shí)，算法TSCA-vSDN 的請(qǐng)求接受率較高。后續(xù)實(shí)驗(yàn)中該比值ratio都取0.5。

圖6 不同比值時(shí)算法TSCA-vSDN的請(qǐng)求接受率對(duì)比Fig.6 Comparison of request acceptance rate of TSCA-vSDN algorithm with different ratios

3.2.2 實(shí)驗(yàn)二

基 于topo-facebook（KP≈0.018）網(wǎng)絡(luò)拓?fù)浜蛅opomesh(KP=0.018)網(wǎng)絡(luò)拓?fù)洌瑢⑷N算法在不同的生存時(shí)長條件下進(jìn)行映射性能對(duì)比。

實(shí)驗(yàn)二分別以topo-facebook 和對(duì)應(yīng)KP的隨機(jī)拓?fù)錇榈讓游锢砭W(wǎng)絡(luò)，分析了算法TSCA、KCL 以及To 在面對(duì)虛擬請(qǐng)求時(shí)長T～P(λ)，λ=120，240，360，480的映射性能對(duì)比情況。

從圖7～8 中可以看出，當(dāng)虛擬請(qǐng)求時(shí)長在120、240、360、480附近服從泊松分布波動(dòng)時(shí)，算法TSCA 的請(qǐng)求接受率（AR）絕大多數(shù)情況下為最高。當(dāng)虛擬網(wǎng)絡(luò)請(qǐng)求個(gè)數(shù)接近1000時(shí)，所有指標(biāo)都趨于平滑、穩(wěn)定，表明此時(shí)已基本消除虛擬網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)以及生存時(shí)長的隨機(jī)波動(dòng)影響，其數(shù)值具備一定的說服力。

圖7 基于topo-facebook（KP ≈0.018）物理網(wǎng)絡(luò)的算法請(qǐng)求接受率對(duì)比Fig.7 Comparison of algorithm request acceptance rate based on topo-facebook（KP ≈0.018）physical network

從圖7 分析得出，算法TSCA 穩(wěn)定時(shí)的AR隨著生存時(shí)長的增加出現(xiàn)明顯的降低，說明AR穩(wěn)定時(shí)，資源利用率基本已到達(dá)該算法利用極限，AR的數(shù)值受到了因生存時(shí)長增加導(dǎo)致的剩余可用資源的約束。著重分析圖7（d）可知，當(dāng)請(qǐng)求個(gè)數(shù)為50時(shí)，算法TSCA的AR值從1開始陡然下降，說明此時(shí)已到達(dá)該算法資源利用率極限，隨后的大部分虛擬請(qǐng)求映射失?。坏?dāng)請(qǐng)求個(gè)數(shù)接近120 時(shí)，算法TSCA 的AR值開始回升，因?yàn)榇藭r(shí)剛開始映射的虛擬請(qǐng)求生存周期已結(jié)束，剩余可用資源增加，接下來的部分虛擬請(qǐng)求成功映射，隨后AR在一定范圍內(nèi)波動(dòng)。

對(duì)比圖7 和圖8 可知，兩者的底層物理網(wǎng)絡(luò)topo-facebook和隨機(jī)拓?fù)涞腒P接近，節(jié)點(diǎn)總數(shù)、控制器數(shù)量相同，節(jié)點(diǎn)參數(shù)相近。分析后發(fā)現(xiàn)，三種算法都在隨機(jī)拓?fù)渖系腁R穩(wěn)定數(shù)值更高，算法TSCA 的AR仍然高于其余兩者算法，說明算法TSCA 相較于算法TSCA、KCL 更適應(yīng)topo-facebook 物理網(wǎng)絡(luò)，能很好地發(fā)揮出算法的映射性能，極大提高虛擬網(wǎng)絡(luò)的請(qǐng)求接受率。

圖8 基于topo-mesh（KP=0.018）物理網(wǎng)絡(luò)的算法請(qǐng)求接受率對(duì)比Fig.8 Comparison of algorithm request acceptance rate based on topo-mesh（KP=0.018）physical network

3.2.3 實(shí)驗(yàn)三

基于topo-fat-tree（KP≈0.026）網(wǎng)絡(luò)拓?fù)浜蛅opo-mesh（KP=0.026）網(wǎng)絡(luò)拓?fù)?，將三種算法在不同的生存時(shí)長條件下進(jìn)行映射性能對(duì)比，結(jié)果如圖9～10所示。

圖9 基于topo-fat-tree（KP ≈0.026）物理網(wǎng)絡(luò)的算法請(qǐng)求接受率對(duì)比Fig.9 Comparison of algorithm request acceptance rate based on topo-fat-tree（KP ≈0.026）physical network

實(shí)驗(yàn)三分別以topo-fat-tree 和對(duì)應(yīng)KP的隨機(jī)拓?fù)錇榈讓游锢砭W(wǎng)絡(luò)，分析了算法TSCA、KCL 以及To 在面對(duì)虛擬請(qǐng)求時(shí)長T～P(λ)，λ=120、240、360、480的映射性能對(duì)比情況。

從圖9～10中可以看出，當(dāng)虛擬請(qǐng)求時(shí)長在120、240、360、480附近服從泊松分布波動(dòng)時(shí)，算法TSCA 的請(qǐng)求接受率（AR）絕大多數(shù)情況下為最高；當(dāng)虛擬網(wǎng)絡(luò)請(qǐng)求個(gè)數(shù)接近1000 時(shí)，所有指標(biāo)都趨于平滑、穩(wěn)定，說明此時(shí)已基本消除虛擬網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)以及生存時(shí)長的隨機(jī)波動(dòng)影響，其數(shù)值具備一定的說服力。

對(duì)比圖9 和圖10 可知，兩者的底層物理網(wǎng)絡(luò)topo-fat-tree和隨機(jī)拓?fù)涞腒P接近，節(jié)點(diǎn)總數(shù)、控制器數(shù)量相同，節(jié)點(diǎn)參數(shù)相近。分析后發(fā)現(xiàn)，三種算法大都在隨機(jī)拓?fù)渖系腁R穩(wěn)定數(shù)值更高，算法TSCA的AR穩(wěn)定數(shù)值仍然高于其余兩種算法，說明算法TSCA 相較于算法TSCA、KCL 更適應(yīng)topo-fat-tree 物理網(wǎng)絡(luò)，能很好地發(fā)揮出算法的映射性能，極大提高虛擬網(wǎng)絡(luò)的請(qǐng)求接受率。

圖10 基于topo-mesh（KP=0.026）物理網(wǎng)絡(luò)的算法請(qǐng)求接受率對(duì)比Fig.10 Comparison of algorithm request acceptance rate based on topo-mesh（KP=0.026）physical network

對(duì)比實(shí)驗(yàn)二與實(shí)驗(yàn)三可以看出，當(dāng)虛擬請(qǐng)求網(wǎng)絡(luò)的生存時(shí)長不高于360時(shí)，算法TSCA 在topo-fat-tree中能取得更好的AR；當(dāng)虛擬請(qǐng)求網(wǎng)絡(luò)的生存時(shí)長高于480 時(shí)，算法TSCA 在topo-facebook中能取得更高的穩(wěn)定AR值。

通過實(shí)驗(yàn)二與實(shí)驗(yàn)三可以看出，當(dāng)虛擬請(qǐng)求網(wǎng)絡(luò)的生存時(shí)長在120、240、360、480 附近服從泊松分布波動(dòng)時(shí)，針對(duì)連通概率較低的底層物理網(wǎng)絡(luò)，如topo-facebook 和topo-fat-tree以及隨機(jī)分布的物理網(wǎng)絡(luò)，算法TSCA 的請(qǐng)求接受率穩(wěn)定值都高于算法TSCA、KCL，能更好地發(fā)揮出算法的映射性能。

4 結(jié)語

本文所提出的算法TSCA-vSDN 首先通過拓?fù)浞指羁s小節(jié)點(diǎn)和鏈路映射搜索范圍；然后通過聚類分析節(jié)點(diǎn)的拓?fù)錁湫魏唾Y源屬性，優(yōu)化節(jié)點(diǎn)映射匹配過程；最后通過將鏈路約束作為節(jié)點(diǎn)約束的一部分，充分利用節(jié)點(diǎn)與鏈路相關(guān)性，提高映射請(qǐng)求接受率。

通過兩組對(duì)比實(shí)驗(yàn)，將算法TSCA-vSDN 與算法KCLvSDN 和To-vSDN 在不同底層物理網(wǎng)絡(luò)拓?fù)洌ㄈ鏵acebook 物理網(wǎng)絡(luò)、fat-tree 物理網(wǎng)絡(luò)以及隨機(jī)分布的物理網(wǎng)絡(luò)）、不同的虛擬網(wǎng)絡(luò)請(qǐng)求持續(xù)時(shí)長條件下的映射性能進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明算法TSCA-vSDN 在提高請(qǐng)求接受率方面性能較優(yōu)。本文所提出的算法TSCA 雖然對(duì)請(qǐng)求接受率有較為明顯的提升，但它的計(jì)算開銷也更大，如何在盡量保持較高請(qǐng)求接受率的條件下優(yōu)化計(jì)算流程，進(jìn)一步降低其計(jì)算開銷，同時(shí)增加對(duì)收益與成本比值和負(fù)載均衡等方面的優(yōu)化研究，將是下一步拓展加深的研究課題。