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

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

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

?

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

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

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

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

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

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

1引言

當(dāng)前網(wǎng)絡(luò)為高峰負(fù)荷而設(shè)計(jì),網(wǎng)絡(luò)資源超量供給確保了網(wǎng)絡(luò)的正常運(yùn)行,然而也導(dǎo)致資源利用率低下.網(wǎng)絡(luò)虛擬化[1],是未來(lái)因特網(wǎng)、云計(jì)算和軟件定義網(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ù).當(dāng)前大部分算法是基于代價(jià)的映射算法[8～10],然而,由于底層節(jié)點(diǎn)能耗與CPU利用率關(guān)系較大[11],基于代價(jià)的映射算法未考慮到節(jié)能,造成不必要的能耗.

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

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

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

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

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

(1)

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

(2)

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

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

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

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

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

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

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

2.4基于主動(dòng)休眠方法的運(yùn)輸模型節(jié)能算法

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

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

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

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

3性能仿真

3.1仿真環(huán)境

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4總結(jié)

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

參考文獻(xiàn)

[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é)報(bào),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)新實(shí)驗(yàn)環(huán)境研究[J].電子學(xué)報(bào),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]姜明,王保進(jìn),等.網(wǎng)絡(luò)虛擬化與虛擬網(wǎng)映射算法研究[J].電子學(xué)報(bào),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é)報(bào),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ò)和綠色評(píng)價(jià):節(jié)能機(jī)制,模型和評(píng)價(jià)[J].計(jì)算機(jī)學(xué)報(bào),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]陳曉華,李春芝,等.主動(dòng)休眠節(jié)點(diǎn)鏈路的高效節(jié)能虛擬網(wǎng)絡(luò)映射[J].軟件學(xué)報(bào),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é)點(diǎn)可重復(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é)院博士生.研究方向?yàn)橄乱淮W(wǎng)絡(luò)、云計(jì)算.

李春芝(通信作者)女,1982年生于江蘇淮安.湖州師范學(xué)院信息工程學(xué)院講師,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系博士生,研究方向?yàn)樽顑?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

作者簡(jiǎn)介

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

中圖分類號(hào):TP393

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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