陳曉華,李春芝,陳良育,曾振柄,蔣云良

(1.湖州師范學(xué)院信息工程學(xué)院,浙江湖州 313000; 2.華東師范大學(xué)軟件學(xué)院,上海 200062;

3.華東師范大學(xué)計算機科學(xué)技術(shù)系,上海 200241; 4.上海大學(xué)數(shù)學(xué)系,上海 200444)

?

虛擬網(wǎng)絡(luò)映射高效節(jié)能運輸模型及算法

陳曉華1,2,李春芝1,3,陳良育2,曾振柄4,蔣云良1

(1.湖州師范學(xué)院信息工程學(xué)院,浙江湖州 313000; 2.華東師范大學(xué)軟件學(xué)院,上海 200062;

3.華東師范大學(xué)計算機科學(xué)技術(shù)系,上海 200241; 4.上海大學(xué)數(shù)學(xué)系,上海 200444)

摘要：網(wǎng)絡(luò)虛擬化使得智能能量感知網(wǎng)絡(luò)部署成為可能,已有研究忽略了節(jié)點映射能耗最優(yōu)化.本文把節(jié)點映射能耗優(yōu)化問題轉(zhuǎn)化為生產(chǎn)地與銷售地之間物資運輸代價最優(yōu)化問題,建立高效節(jié)能節(jié)點映射運輸模型.根據(jù)最大元素法,提出了混合一階段與兩階段映射算法,在鏈路映射的約束下找到節(jié)點分配最小能耗代價最優(yōu)解;利用主動休眠策略,提出了基于運輸模型的主動休眠虛擬網(wǎng)絡(luò)映射節(jié)能算法;利用節(jié)點可重復(fù)映射技術(shù),提出了基于運輸模型的節(jié)點可重復(fù)映射算法,進一步提高了底層網(wǎng)絡(luò)資源休眠數(shù)量.仿真結(jié)果驗證了本文所提算法能夠顯著降低系統(tǒng)能耗,適合大規(guī)模高效節(jié)能虛擬網(wǎng)絡(luò)映射.

關(guān)鍵詞:虛擬網(wǎng)絡(luò)映射;運輸模型;混合一階段與兩階段算法;高效節(jié)能

1引言

當前網(wǎng)絡(luò)為高峰負荷而設(shè)計,網(wǎng)絡(luò)資源超量供給確保了網(wǎng)絡(luò)的正常運行,然而也導(dǎo)致資源利用率低下.網(wǎng)絡(luò)虛擬化[1],是未來因特網(wǎng)、云計算和軟件定義網(wǎng)絡(luò)的重要技術(shù)[2～7].其管理底層網(wǎng)絡(luò)基礎(chǔ)設(shè)施以及分配虛擬網(wǎng)絡(luò)資源,使得智能能量感知網(wǎng)絡(luò)部署成為可能.虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化的關(guān)鍵技術(shù).當前大部分算法是基于代價的映射算法[8～10],然而,由于底層節(jié)點能耗與CPU利用率關(guān)系較大[11],基于代價的映射算法未考慮到節(jié)能,造成不必要的能耗.

當前基于能量感知虛擬網(wǎng)絡(luò)映射針對鏈路能耗對負載不敏感的設(shè)備,采用資源整合策略實現(xiàn)節(jié)能.如:文獻[12]提出混合整數(shù)規(guī)劃的能量感知最優(yōu)化模型,但是時間復(fù)雜度呈指數(shù)增長,難以適應(yīng)大規(guī)模網(wǎng)絡(luò)基礎(chǔ)設(shè)施的虛擬網(wǎng)絡(luò)映射;文獻[13]提出虛擬網(wǎng)絡(luò)重配置的最小化能耗的啟發(fā)式方法;蘇森等提出虛擬網(wǎng)絡(luò)映射能耗模型以及能量感知兩階段映射算法[14],在文獻[15]中考慮電價波動提出了能耗成本最小化模型以及能量感知兩階段映射算法:常曉林、王冰等提出混合整數(shù)規(guī)劃能耗模型及能量感知兩階段映射算法[16],文獻[17]在云數(shù)據(jù)中心應(yīng)用蟻群優(yōu)化算法求解虛擬網(wǎng)絡(luò)節(jié)能映射.文獻[18]提出了多目標決策虛擬網(wǎng)絡(luò)映射節(jié)能模型,并提出主動休眠底層網(wǎng)絡(luò)資源策略.此外,針對鏈路能耗對負載敏感的設(shè)備,文獻[19]考慮到路由能耗以及機箱能耗,提出擴展流量到網(wǎng)絡(luò)資源的節(jié)能方法.由上可見,已有文獻通過資源整合策略以及流量擴展策略實現(xiàn)節(jié)能,但忽略了節(jié)點映射能耗代價最優(yōu)化.

本文提出節(jié)點分配能耗代價最小化運輸模型;以最小元素法為基礎(chǔ),設(shè)計高效節(jié)能虛擬網(wǎng)絡(luò)映射的混合一階段與兩階段算法;針對動態(tài)特征對底層休眠資源的影響,設(shè)計基于運輸模型的主動休眠節(jié)能算法;利用節(jié)點可重復(fù)映射技術(shù),提出了基于運輸模型的節(jié)點可重復(fù)映射算法,以降低系統(tǒng)能耗.

2虛擬網(wǎng)絡(luò)映射節(jié)能運輸模型及算法

2.1虛擬網(wǎng)絡(luò)映射與底層網(wǎng)絡(luò)能耗模型

當前處理器能耗與負載具有較好相關(guān)性[11].設(shè)定Pb為節(jié)點基本能耗,Pm為節(jié)點最大能耗,Pl=Pm-Pb,u為CPU利用率.定義第i個節(jié)點能耗為:

(1)

當前網(wǎng)絡(luò)設(shè)備對流量負荷的功耗不敏感[20],專有的減負引擎將部署在網(wǎng)絡(luò)虛擬化中[21～23],網(wǎng)絡(luò)鏈路的能耗為常量[22,24].定義第j條鏈路能耗為:

(2)

2.2虛擬網(wǎng)絡(luò)映射能耗代價最小化運輸模型

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

2.3虛擬網(wǎng)絡(luò)映射最小化能耗代價算法

為了求解模型,本節(jié)以最小元素法為基礎(chǔ),提出混合一階段與兩階段虛擬網(wǎng)絡(luò)映射算法,求解虛擬網(wǎng)絡(luò)映射節(jié)點分配最小能耗代價最優(yōu)解,如算法1所示.

第1步,構(gòu)造虛擬網(wǎng)絡(luò)映射節(jié)點分配最小能耗代價運輸模型,dist是承載運輸模型的數(shù)據(jù)結(jié)構(gòu),其中dist[i][j]表示從虛擬節(jié)點j分配到底層節(jié)點i的相關(guān)數(shù)據(jù),即dist[i][j].uPrice為分配虛擬節(jié)點j到底層節(jié)點i每個CPU資源量所消耗的CPU能耗單價;dist[sub.nodes][]為運輸模型數(shù)據(jù)結(jié)構(gòu)的最后一行,其中dist[sub.nodes][j].cpu為虛擬節(jié)點j請求的CPU資源量;dist[][req[index].nodes]為運輸模型數(shù)據(jù)結(jié)構(gòu)的最后一列,其中dist[i][req[index].nodes].cpu為底層節(jié)點i可用CPU資源量;req[index].nodes為第index個虛擬網(wǎng)絡(luò)的節(jié)點數(shù)量;sub.nodes為底層節(jié)點數(shù)量.當?shù)讓庸?jié)點i剩余的CPU資源量大于等于虛擬節(jié)點j請求的CPU資源量,則從i到j(luò)分配CPU資源的能耗單價為1.0/CPUSi;當?shù)讓庸?jié)點i的CPU資源量小于虛擬節(jié)點j請求的CPU資源量,則dist[i][j].uPrice=-1,表示底層節(jié)點資源量不足,不能分配CPU資源;第i個底層節(jié)點(生產(chǎn)地)生產(chǎn)產(chǎn)品的產(chǎn)量為dist[i][req[index].nodes].cpu=CPULi;第j個虛擬節(jié)點(銷售地)對產(chǎn)品的需求量為dist[sub.nodes][j].cpu=CPUVj.

第2步,根據(jù)最小元素法求解虛擬網(wǎng)絡(luò)映射最小能耗代價.2.1步,num記錄成功映射虛擬節(jié)點數(shù)量,初始化為0;集合AE為已經(jīng)映射的節(jié)點集合,初始化為空集.2.2步,判斷所有的虛擬節(jié)點是否成功映射.2.3步調(diào)用GetMinNum()函數(shù),該函數(shù)在AE的補集(即未映射的底層節(jié)點和虛擬節(jié)點集合)中尋找最小能耗單價及未映射的虛擬節(jié)點最大CPU請求資源元素(sNode,vNode).2.5步循環(huán)調(diào)用FindNoEmbedVLink()函數(shù),直到?jīng)]有發(fā)現(xiàn)未映射的虛擬鏈路.FindNoEmbedVLink()函數(shù)在AE中(即已經(jīng)映射虛擬節(jié)點集合)檢測是否存在一條未映射的虛擬鏈路,并返回虛擬鏈路vFindLink相關(guān)信息,包括vFindLink帶寬bw、兩個虛擬端點(vNode、vFNode)以及映射的兩個底層節(jié)點(sNode、sFNode).2.6步調(diào)用EmbedLinkBySpfa()函數(shù),該函數(shù)在底層節(jié)點sNode到sFNode以最短路徑映射虛擬鏈路vFindLink,這條最短路徑的所有鏈路剩余帶寬必須大于等于bw,其中采用經(jīng)典最短路徑算法計算最短路徑.鏈路之間的距離設(shè)置如下:如果底層鏈路帶寬大于等于bw,則設(shè)置為1,表示該鏈路可以映射;如果底層鏈路小于bw,則設(shè)置為0,表示該底層鏈路不能映射,不參與最短路徑的計算.如果EmbedLinkBySpfa()找到了一條最短路徑映射虛擬鏈路,則2.7步記錄鏈路映射結(jié)果,并更新vFindLink虛擬鏈路映射標志,否則鏈路映射失敗,返回-1.

算法1是混合一階段和兩階段虛擬網(wǎng)絡(luò)映射算法;其不同于一階段映射算法,因為當映射一個虛擬節(jié)點后,并沒有映射與該節(jié)點連接的所有鏈路;也不同于兩階段映射算法,因為當映射一個虛擬節(jié)點后,立即檢查AE中未映射的鏈路.算法1采用最小元素法尋找虛擬網(wǎng)絡(luò)節(jié)點分配最小能耗代價最優(yōu)解.虛擬網(wǎng)絡(luò)映射運輸模型的特殊性,使得最小元素法找到的可行解即為最優(yōu)解.因為應(yīng)用閉回路檢驗法找不到閉回路,其檢驗數(shù)也不存在負數(shù),所以可行解即為最優(yōu)解.

算法1的時間復(fù)雜度主要集中在第2步,為o(n2·vl·m3),n為虛擬節(jié)點數(shù)量,vl為虛擬鏈路數(shù)量,m為底層節(jié)點數(shù)量,通常n和vl較小,能夠保證在線虛擬網(wǎng)絡(luò)映射的實時性.

2.4基于主動休眠方法的運輸模型節(jié)能算法

由于虛擬網(wǎng)絡(luò)映射的動態(tài)性對底層網(wǎng)絡(luò)休眠節(jié)點和鏈路數(shù)量造成干擾,文獻[18]提出了主動休眠方法,能夠應(yīng)用在不同的虛擬網(wǎng)絡(luò)映射算法上,實現(xiàn)底層網(wǎng)絡(luò)節(jié)能.因此本文在虛擬網(wǎng)絡(luò)映射運輸模型基礎(chǔ)上,應(yīng)用主動休眠方法,設(shè)計基于運輸模型的虛擬網(wǎng)絡(luò)映射算法,如算法2所示.第1步,根據(jù)映射字典庫,計算主動休眠的底層節(jié)點和鏈路數(shù)量;第2步,在第一個時間窗設(shè)置底層節(jié)點和鏈路的休眠和激活標志;第3步,在設(shè)置激活標志的底層網(wǎng)絡(luò)資源中,采用算法1映射虛擬網(wǎng)絡(luò).

算法2的優(yōu)勢是抗干擾性:虛擬網(wǎng)絡(luò)到來和退出,引起底層網(wǎng)絡(luò)資源的分配和回收,引起底層網(wǎng)絡(luò)可休眠的節(jié)點和鏈路數(shù)量的動態(tài)變化,節(jié)能休眠狀態(tài)與激活狀態(tài)的切換必然導(dǎo)致底層網(wǎng)絡(luò)不必要的能耗開銷;算法2利用歷史數(shù)據(jù),能夠快速找到適合當前虛擬網(wǎng)絡(luò)的激活底層網(wǎng)絡(luò)資源集合,避免了底層網(wǎng)絡(luò)在兩種不同狀態(tài)頻繁切換.算法2是建立在虛擬網(wǎng)絡(luò)映射字典庫,且只在第一個時間窗內(nèi)計算激活的底層網(wǎng)絡(luò)休眠和激活標志,其時間復(fù)雜度與算法1相同.

2.5節(jié)點可重復(fù)映射的運輸模型節(jié)能算法

當前大部分虛擬網(wǎng)絡(luò)映射算法在映射單個虛擬網(wǎng)絡(luò)時,是在底層節(jié)點不可重復(fù)的條件下進行的.文獻[25]提出了節(jié)點可重復(fù)映射算法,但其未考慮到能耗因素.為此,本文考慮節(jié)點分配能耗代價最小化,提出基于運輸模型的節(jié)點可重復(fù)映射算法.在映射單個虛擬網(wǎng)絡(luò)時,多個節(jié)點可映射到一個底層節(jié)點上,對應(yīng)的虛擬鏈路則不需要映射.這樣使得一些底層節(jié)點空閑出來,進入休眠節(jié)能狀態(tài).具體見算法3.

3性能仿真

3.1仿真環(huán)境

本文采用GT-ITM工具創(chuàng)建對稱網(wǎng)絡(luò)拓撲結(jié)構(gòu).底層網(wǎng)絡(luò)包括100個節(jié)點、570條鏈路,每對節(jié)點以0.5的概率相連,相當于中等規(guī)模網(wǎng)絡(luò).底層節(jié)點CPU和鏈路帶寬資源服從50-100均勻分布.每個時間窗為100個時間單元.每個虛擬網(wǎng)絡(luò)請求節(jié)點個數(shù)服從2～20的均勻分布,每對虛擬節(jié)點以0.5的概率相連,每個虛擬網(wǎng)絡(luò)平均有12條鏈路;虛擬網(wǎng)絡(luò)請求過程模擬泊松過程,每個時間窗內(nèi)虛擬網(wǎng)絡(luò)請求到達個數(shù)服從均值為10的泊松分布,每個虛擬網(wǎng)絡(luò)生存時間服從均值為5個時間窗的指數(shù)分布,等待映射時間為1個時間窗.設(shè)置虛擬節(jié)點CPU與帶寬都服從0～6(非飽和狀態(tài))、0～20(飽和狀態(tài))的均勻分布.每次運行500個時間窗.與文獻[22,27]一致,設(shè)置2.1節(jié)定義的Pb、Pm和Pn分別為150W,300W和15W;由于鏈路功耗差異較大[28,29],比較了鏈路功耗在1、15、30W的系統(tǒng)能耗,如圖5、10所示.實驗記錄運行10個實例的平均值.

本文提出的算法1、2和3分別記為TR-VNE、 TR-AH-VNE和TR-VNE-S,其中算法2計算的主動休眠鏈路和節(jié)點數(shù)量分別為120和29.為了評價網(wǎng)絡(luò)虛擬化映射節(jié)能性能,與基于能耗感知啟發(fā)式算法[14]、元啟發(fā)式算法[17]、節(jié)點可重復(fù)映射算法[25]以及經(jīng)典啟發(fā)式算法[29],即EA-VNE、ACO-VNE、VNE-S及PR-VNE比較.基于整數(shù)規(guī)劃、線性規(guī)劃的映射算法難以滿足大規(guī)模虛擬網(wǎng)絡(luò)映射的實時性要求,因此本文不與它們比較.本文的主要貢獻在于節(jié)點映射,采用單路徑鏈路映射.

與現(xiàn)有文獻[14,18]相同,設(shè)定系統(tǒng)能耗、休眠節(jié)點數(shù)量、休眠鏈路數(shù)量、系統(tǒng)收益、收益成本比和接收率為性能評價指標,并在非飽和狀態(tài)與飽和狀態(tài)下,比較算法性能,其中系統(tǒng)收益是虛擬網(wǎng)絡(luò)帶寬與CPU總和.

3.2非飽和狀態(tài)下的仿真結(jié)果

(1)在非飽和狀態(tài)下,所提算法顯著減少了系統(tǒng)平均能耗,如圖1.因為TR-VNE,能夠最小化節(jié)點分配能耗代價;TR-AH-VNE進一步降低了虛擬網(wǎng)絡(luò)映射動態(tài)特征對底層網(wǎng)絡(luò)資源休眠數(shù)量的干擾;TR-VNE-S利用節(jié)點可重復(fù)映射技術(shù)顯著降低了底層網(wǎng)絡(luò)激活資源的數(shù)量.雖然TR-VNE休眠節(jié)點數(shù)量比PR-VNE少(如圖2),但提高了鏈路休眠數(shù)量(如圖3);TR-AH-VNE休眠節(jié)點數(shù)量比PR-VNE多,并且提高了鏈路休眠數(shù)量.

(2)隨著鏈路能耗的增大,所提算法節(jié)約能耗也越多.圖4顯示鏈路能耗在1、15和30,所提算法能減少系統(tǒng)能耗.這是由于當節(jié)點能耗不變的情況下,系統(tǒng)能耗變化部分集中在鏈路能耗上.由圖3可知,本文所提算法的可休眠鏈路數(shù)量比PR-VNE多.隨著鏈路能耗增大,節(jié)約能耗越多,這是由于節(jié)約能耗為ΔE=Pn·ΔL,不同鏈路能耗下ΔL是相同的,ΔE隨著Pn增大而增多.

(3)在非飽和狀態(tài)下,TR-VNE-S顯著提高了收益成本比.圖5顯示TR-VNE-S的收益成本比顯著提升,達到了1.06,這是因為TR-VNE-S通過節(jié)點可重復(fù)映射,即映射在同一個底層節(jié)點上的虛擬節(jié)點之間的鏈路不需要映射,減小了鏈路映射代價,從而顯著提高了收益成本比.PR-VNE是一個經(jīng)典映射算法,收益成本比較好,TR-VNE和TR-AH-VNE因為沒有考慮到鏈路映射代價,收益成本比低于PR-VNE.

3.3飽和狀態(tài)下的仿真結(jié)果

在飽和狀態(tài)下,TR-AH-VNE退化為TR-VNE.

(1)在飽和狀態(tài)下,所提算法顯著減少了系統(tǒng)能耗,如圖6顯示.這是因為TR-VNE能夠最小化節(jié)點分配能耗代價;TR-VNE-S能夠?qū)崿F(xiàn)底層網(wǎng)絡(luò)休眠資源量顯著增加(圖7、8所示);TR-VNE是沒有考慮負載平衡,在資源緊張情況下,導(dǎo)致休眠節(jié)點數(shù)量比PR-VNE少量增加,而與節(jié)點相連的鏈路利用率高,從而休眠鏈路數(shù)量顯著增加.

(2)不同鏈路能耗情況下,所提算法都能有效降低系統(tǒng)能耗;且隨著鏈路能耗增大,節(jié)約能耗越多.這是由于當節(jié)點能耗不變的情況下,系統(tǒng)平均能耗變化部分集中在鏈路能耗上,即由圖8可知,TR-VNE、TR-VNE-S可休眠的鏈路數(shù)量比其它算法都要多,隨著鏈路能耗增大,節(jié)約的能耗越多.同時,節(jié)點分配能耗代價最小化以及可重復(fù)映射,使得TR-VNE和TR-VNE-S有效節(jié)約了系統(tǒng)能耗如圖9所示.

(3)在飽和狀態(tài)下,TR-VNE-S顯著提高了系統(tǒng)收益成本比,如圖10所示.這是因為底層節(jié)點可重復(fù)映射,讓一部分虛擬鏈路不需要映射,從而顯著提高了收益成本比.TR-VNE比PR-VNE的收益成本比少1%,這是由于TR-VNE主要考慮節(jié)點映射的能耗代價最小化,導(dǎo)致一些底層節(jié)點映射較多虛擬節(jié)點,這些底層節(jié)點的鏈路可用資源減少,并未考慮負載平衡,從而影響了受益成本比,即TR-VNE節(jié)約能耗是以系統(tǒng)收益成本比為代價的.

(4)在飽和狀態(tài)下,TR-VNE-S提高了虛擬網(wǎng)絡(luò)接收率和系統(tǒng)收益,如圖11和12所示.這是因為底層節(jié)點可重復(fù)映射,降低了底層鏈路映射代價,從而提高了虛擬網(wǎng)絡(luò)接收率和系統(tǒng)受益.在虛擬網(wǎng)絡(luò)接收率和系統(tǒng)收益方面,TR-VNE與PR-VNE幾乎相當,這是由于底層網(wǎng)絡(luò)資源較豐富,TR-VNE主要考慮的是節(jié)點分配能耗代價最小化,未考慮到負載平衡.

3.3仿真時間的比較結(jié)果

映射時間比較:同一臺計算機模擬仿真,非飽和狀態(tài)與飽和狀態(tài)所用時間具有相似性,因此選擇非飽和狀態(tài)時間進行運行時間比較.在非飽和狀態(tài)下運行500個時間窗所用的時間,EA-VNE、PR-VNE、ACO-PE-VNE、VNE-S、TR-VNE、TR-AH-VNE和TR-VNE-S分別為22、30、400、11、21、 9和18秒.可以看出,所提算法運行時間較少,適合在大規(guī)模底層網(wǎng)絡(luò)上在線實時映射虛擬網(wǎng)絡(luò).

4總結(jié)

本文研究網(wǎng)絡(luò)虛擬化環(huán)境下的系統(tǒng)能耗問題.運用運輸模型,把虛擬網(wǎng)絡(luò)映射問題轉(zhuǎn)化為生產(chǎn)地與銷售地之間的運輸能耗代價最小化問題,并設(shè)計虛擬網(wǎng)絡(luò)映射高效節(jié)能算法,顯著降低了系統(tǒng)能耗.

參考文獻

[1]Chowdhury N M M K,et al.Network virtualization:state of the art and research challenges[J].Communications Magazine,IEEE,2009,47(7):20-26.

[2]Anderson T,et al.Overcoming the Internet impass through virtualization[J].IEEE Computer Magazine,2005,38(4):34-41.

[3]Sun G,et al.Optimal provisioning for elastic service oriented virtual network request in cloud computing[A].IEEE GLOBECOM[C].Anaheim:IEEE,2012.2517-2522.

[4]Drutskoy D,et al.Scalable network virtualization in software-defined networks[J].IEEE Internet Computing,2013,17(2):21-27.

[5]Sharkh M A,et al.Resource allocation in a network-based cloud computing environment:design challenges[J].IEEE Communications Magazine,2013,51(11):46-52.

[6]魏祥麟,陳鳴,等.數(shù)據(jù)中心網(wǎng)絡(luò)的體系結(jié)構(gòu)[J].軟件學(xué)報,2013,24(2):295-316.

Wei X,Chen M,et al.Architecture of the data center network[J].Journal of Software,2013,24(2):295-316.(in Chinese)

[7]周燁,李勇,等.基于虛擬化的網(wǎng)絡(luò)創(chuàng)新實驗環(huán)境研究[J].電子學(xué)報,2012,40(11):2152-2157.

Zhou Y,Li Y,et al.Research of Network innovation exerpimental environment based on network virtualization[J].Acta Electronica Sinica,2012,40(11):2152-2157(in Chinese).

[8]Fischer A,et al.Virtual network embedding:A survey[J].IEEE Communications Surveys & Tutorials,2013,(99):1-19.

[9]姜明,王保進,等.網(wǎng)絡(luò)虛擬化與虛擬網(wǎng)映射算法研究[J].電子學(xué)報,2011,39(6):1315-1320.

Jiang M,Wang B,et al.Research on network virtualization and virtual network mapping algorithm[J].Acta Electronica Sinica,2011,39(6):1315-1320.(in Chinese)

[10]程祥,張忠寶,等.基于粒子群優(yōu)化的虛擬網(wǎng)絡(luò)映射算法[J].電子學(xué)報,2011,39(10):2240-2244.

Cheng X,Zhang Z,et al.Virtual network embedding based on particle swarm optimization[J].Acta Electronica Sinica,2011,39(10):2240-2244.(in Chinese)

[11]林闖,田源,等.綠色網(wǎng)絡(luò)和綠色評價:節(jié)能機制,模型和評價[J].計算機學(xué)報,2011,34(4):593-612.

Lin C,Tian Y,et al.Green network and green evaluation:mechanism,modeling and evaluation[J].Chinese Journal of Computers,2011,34(4):593-612.(in Chinese)

[12]Botero J F,et al.Energy efficient virtual network embedding[J].IEEE Communications Letters,2012,16(5):756-759.

[13]Botero J F,et al.Greener networking in a network virtualization environment[J].Computer Networks,2013,57 (9):2021-2039.

[14]Su S,et al.Energy-aware virtual network embedding through consolidation[A].Computer Communications Workshops[C].Orlando:IEEE,2012.127-132.

[15]Su S,et al.Energy-aware virtual network embedding[J].IEEE/ACM Transactions on Networking.2014.10:1-14.

[16]Wang B,et al.Reducing power consumption in embedding virtual infrastructures[A].Globecom Workshops (GC Wkshps)[C].Anaheim,CA:IEEE,2012.714-718.

[17]Chang X,et al.Green cloud virtual network provisioning based ant colony optimization[A].Proceeding of the Fifteenth Annual Conference Companion on Genetic and Evolutionary Computation Conference Companion[C].Amsterdam ACM,2013.1553-1560.

[18]陳曉華,李春芝,等.主動休眠節(jié)點鏈路的高效節(jié)能虛擬網(wǎng)絡(luò)映射[J].軟件學(xué)報,2014,25(7):1416-1431.

Chen X,Li C,et al.Energy efficient virtual network embedding based on actively hibernating substrate nodes and links[J].Journal of Software,2014,25(7):1416-1431.(in Chinese)

[19]Rasario G,et al.Does traffic consolidation always lead to network energy savings[J].IEEE Communication Letters,2013,17(9):1852-1855.

[20]Chabarek J,et al.Power awareness in network design and routing[A].IEEE INFOCOM[C].Phoenix:IEEE,2008.457-465.

[21]Turner J,et al.Supercharging planetlab:A high performance,multi-application,overlay network platform[J].ACM SIGCOMM Computer Communication Review,2007，37(4):85-96.

[22]Lu G,et al.Serverswitch:A programmable and high performance platform for data center networks[A].Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation[C].Boston:USENIX Association,2011.1-14.

[23]Unnikrishnan D,et al.Scalable network virtualization using FPGAs[A].Proceedings of the 18th Annual ACM/SIGDA International Symposium on Field Programmable Gate Arrays[C].Monterey:ACM,2010.219-228.

[24]Sivaraman V,et al.Profiling per-packet and per-byte energy consumption in the netfpga gigabit router[A].IEEE Computer Communications Workshops (INFOCOM WKSHPS)[C].Shanghai:IEEE,2011.331-336.

[25]李文,吳春明,等.節(jié)點可重復(fù)映射和鏈路可分流的虛擬網(wǎng)映射算法[J].電信科學(xué),2010,26(10):114-120.

Li W,Wu C M,et al.Virtual network mapping algorithm with node repeatable embedding and link splitting[J].Telecommunications Science,2010,26(10):114-120.(in Chinese)

[26]Barroso L A,et al.The Datacenter as a Computer:An Introduction to the Design of Warehouse-Scale Machines[M].California:Morgan and Claypool Publishers,2009.1-108.

[27]Ananthanarayanan G,et al.Greening the switch[A].HotPower'08 Proceedings of the 2008 Conference on Power Aware Computing and Systems[C].Berkeley,CA,USA:USENIX Association,2008.

[28]Chiaraviglio L,et al.Energy-aware backbone networks:a case study[A].International Conference on Communications Workshop[C].Dresden,Germany:IEEE,2009.1-5.

[29]Cheng X,et al.Virtual network embedding through topology-aware node ranking[J].ACM SIGCOMM Computer Communication Review,2011,41(2):38-47.

陳曉華男,1977年生于江西九江.湖州師范學(xué)院信息工程學(xué)院講師,華東師范大學(xué)軟件學(xué)院博士生.研究方向為下一代網(wǎng)絡(luò)、云計算.

李春芝(通信作者)女,1982年生于江蘇淮安.湖州師范學(xué)院信息工程學(xué)院講師,華東師范大學(xué)計算機科學(xué)技術(shù)系博士生,研究方向為最優(yōu)化方法、圖像處理.

E-mail:lichunzhi82@126.com.

Transportation Model and Algorithms for Energy Efficient Virtual Network Embedding

CHEN Xiao-hua1,2,LI Chun-zhi1,3,CHEN Liang-yu2,ZENG Zhen-bing4,JIANG Yun-liang1

(1.SchoolofInformationandEngineering,HuzhouTeachersCollege,Huzhou,Zhejiang313000,China;2.SoftwareEngineeringInstitute,EastChinaNormalUniversity,Shanghai200062,China;3.DepartmentofComputerScienceandTechnology,EastChinaNormalUniversity,Shanghai200241,China;4.DepartmentofMathematics,ShanghaiUniversity,Shanghai200444,China)

Abstract:Network virtualization is an enabler for intelligent energy-aware network deployment.In the existing virtual network embedding algorithms,the minimization of energy consumption for mapping virtual nodes is ignored.In this paper,we create a transportation model for energy efficient virtual network embedding,in which energy consumption minimization for mapping virtual nodes is turned into the transportation model.An algorithm based on the largest element is proposed to obtain the optimization solution with node and link resource constraints,which is also a hybrid one-and-two stage algorithm.Besides,on the basis of the transportation model,we design an energy saving algorithm by use of the actively hibernating policy.If multiple virtual nodes in the same virtual network can be mapped to the same substrate node,a largest-element-and-transportation-model-based algorithm is proposed.These algorithms increase the number of substrate network hibernating resources.Simulation results show that the proposed algorithms can significantly reduce energy consumption.The theoretical analyses and the simulation results verify that our proposed algorithms suit energy efficient virtual network embedding for large scale substrate network.

Key words:virtual network embedding;transportation model;hybrid one-and-two stage algorithm;energy efficient

作者簡介

DOI:電子學(xué)報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.034

中圖分類號:TP393

文獻標識碼：A

文章編號：0372-2112 (2016)03-0725-07

基金項目:國家自然科學(xué)基金(No.61501184,No.61370173)

收稿日期:2014-07-23;修回日期:2014-11-10;責(zé)任編輯:藍紅杰