基于可重構(gòu)網(wǎng)絡(luò)的節(jié)能方法的研究

廖生權(quán)，吳春明，王濱，姜明

（1. 浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310027；2. 杭州電子科技大學(xué) 軟件與智能技術(shù)研究所，浙江 杭州 310018）

1 引言

在過去的幾十年中，互聯(lián)網(wǎng)取得了空前的成就。各種各樣的網(wǎng)絡(luò)業(yè)務(wù)也應(yīng)運(yùn)而生，這些業(yè)務(wù)不僅要求網(wǎng)絡(luò)能保障信息傳輸?shù)目煽啃?，而且要求網(wǎng)絡(luò)對(duì)信息的傳送過程具有可預(yù)見性，互聯(lián)網(wǎng)用戶甚至要求網(wǎng)絡(luò)能夠在任何情況下提供相對(duì)穩(wěn)定的服務(wù)，傳統(tǒng)的網(wǎng)絡(luò)體系結(jié)構(gòu)已經(jīng)無法滿足這些要求[1]?？芍貥?gòu)網(wǎng)絡(luò)模型為解決當(dāng)前互聯(lián)網(wǎng)的“供需”矛盾提供了契機(jī)。與傳統(tǒng)的網(wǎng)絡(luò)不同，可重構(gòu)網(wǎng)絡(luò)是面向業(yè)務(wù)支撐的，網(wǎng)絡(luò)提供的服務(wù)與網(wǎng)絡(luò)用戶之間是松耦合關(guān)系[2]。在這種體系結(jié)構(gòu)下，網(wǎng)絡(luò)的服務(wù)主要是通過構(gòu)建邏輯承載網(wǎng)(LCN, logical carrying network)的方式來提供的。邏輯承載網(wǎng)是按照用戶指定的要求（如出口節(jié)點(diǎn)、入口節(jié)點(diǎn)、帶寬及業(yè)務(wù)類型等）在物理網(wǎng)絡(luò)上構(gòu)建專用網(wǎng)絡(luò)[3]。由此可以看出，在面向業(yè)務(wù)的可重構(gòu)網(wǎng)絡(luò)構(gòu)架下，物理鏈路上的流量表現(xiàn)為運(yùn)載其上的邏輯承載網(wǎng)的流量的疊加。

國(guó)內(nèi)外的學(xué)者在可重構(gòu)網(wǎng)絡(luò)的研究方面均取得了十分顯著的成果，如邏輯承載網(wǎng)的構(gòu)建算法[4～6]，支撐邏輯承載網(wǎng)的路由技術(shù)[7]等。特別是文獻(xiàn)[7]中提出的路由器數(shù)據(jù)面和控制面相分離的 VROOM機(jī)制，對(duì)網(wǎng)絡(luò)的管理具有十分重要的意義。它保證了路由器上的路由任務(wù)能夠在各路由器之間進(jìn)行自由遷移，并且對(duì)用戶的業(yè)務(wù)影響十分微小，幾乎可以忽略不計(jì)。數(shù)據(jù)中心網(wǎng)絡(luò)中也存在著一種典型的任務(wù)遷移方案。該方案一般是關(guān)閉虛擬機(jī)，遷移虛擬機(jī)的狀態(tài)于另一臺(tái)機(jī)器上，重新開啟虛擬機(jī)并恢復(fù)其狀態(tài)。傳統(tǒng)的遷移方案在實(shí)施任務(wù)遷移任務(wù)過程中顯然無法保障用戶的QoS。與這種方案對(duì)比，VROOM 機(jī)制的優(yōu)勢(shì)在于遷移過程對(duì)用戶是透明的，對(duì)網(wǎng)絡(luò)的影響十分小。

與此同時(shí)，隨著網(wǎng)絡(luò)應(yīng)用的成功普及，其規(guī)模也相應(yīng)地呈指數(shù)級(jí)增長(zhǎng)。巨大的網(wǎng)絡(luò)規(guī)模也造成了整個(gè)網(wǎng)絡(luò)設(shè)施能耗的平行增加。文獻(xiàn)[8]中的數(shù)據(jù)顯示，在2007年互聯(lián)網(wǎng)消耗的電能約為9×1011kWh，占世界總耗電量的 5.5%，并且每年以大約20%～25%的比例增加。互聯(lián)網(wǎng)的節(jié)能必會(huì)在全球節(jié)能領(lǐng)域做出十分重要的貢獻(xiàn)，是可持續(xù)發(fā)展的客觀要求。因此，互聯(lián)網(wǎng)上的節(jié)能問題成了眾多學(xué)者關(guān)注的課題。他們的基本思想是根據(jù)物理網(wǎng)的拓?fù)浣Y(jié)構(gòu)和流量矩陣，采用流量工程的方式節(jié)能，目標(biāo)是用最小的網(wǎng)絡(luò)鏈路去承載當(dāng)前的網(wǎng)絡(luò)任務(wù)。

雖然可重構(gòu)柔性網(wǎng)目前處于實(shí)驗(yàn)網(wǎng)階段，但是其新型的網(wǎng)絡(luò)架構(gòu)給互聯(lián)網(wǎng)節(jié)能方案帶來了新的挑戰(zhàn)。本文主要關(guān)注可重構(gòu)柔性網(wǎng)絡(luò)的節(jié)能問題，旨在提出一個(gè)匹配其構(gòu)架的節(jié)能方案，并與傳統(tǒng)的流量規(guī)劃做比較，分析出可重構(gòu)柔性網(wǎng)上節(jié)能方案的特點(diǎn)，為未來的該構(gòu)架下的節(jié)能研究提供一些思路。

2 相關(guān)工作

為了減少溫室效應(yīng)和環(huán)境污染，節(jié)能問題已經(jīng)是網(wǎng)絡(luò)研究領(lǐng)域的一個(gè)重要議題。在當(dāng)前的網(wǎng)絡(luò)下，IP流主要是根據(jù)各種路由協(xié)議進(jìn)行選路，這些協(xié)議算法實(shí)際上是選擇資源最大的鏈路帶寬或最短跳數(shù)進(jìn)行通信，這樣的選擇方式往往與節(jié)能的目標(biāo)背道而馳，所以，僅僅依靠當(dāng)前的網(wǎng)絡(luò)路由協(xié)議無法實(shí)現(xiàn)互聯(lián)網(wǎng)節(jié)能的目標(biāo)。

文獻(xiàn)[9]指出，承載于各種網(wǎng)絡(luò)類型中的鏈路上的流量負(fù)荷達(dá)到或者超過其帶寬容量的30%時(shí)，該鏈路的能耗與滿負(fù)荷時(shí)的能耗相等。因此，通過流量控制來實(shí)現(xiàn)網(wǎng)絡(luò)的節(jié)能是徒勞無功的。當(dāng)前，互聯(lián)網(wǎng)的節(jié)能研究主要是基于互聯(lián)網(wǎng)中的網(wǎng)絡(luò)設(shè)備具有休眠控制和動(dòng)態(tài)電壓控制的假設(shè)之上的[10]。網(wǎng)絡(luò)領(lǐng)域節(jié)能的基本思想是將網(wǎng)絡(luò)中的負(fù)荷重新映射到當(dāng)前物理網(wǎng)絡(luò)鏈路的一個(gè)子集上，從而可以調(diào)低鏈路電壓[11]或者休眠、關(guān)閉某些鏈路，實(shí)現(xiàn)節(jié)能的目的。文獻(xiàn)[12]是基于一個(gè)啟發(fā)式算法，在給定的流量矩陣中計(jì)算可以被關(guān)閉鏈路條數(shù)的最小值。同時(shí)，文獻(xiàn)[13]主要是根據(jù)流量矩陣找出最少的路由節(jié)點(diǎn)，用來支撐當(dāng)前網(wǎng)絡(luò)流量，使其他的路由器休眠。

可重構(gòu)網(wǎng)絡(luò)的構(gòu)架是多個(gè)邏輯網(wǎng)(LCN)與一個(gè)物理網(wǎng)的對(duì)應(yīng)關(guān)系，其上的流量的調(diào)整必然涉及邏輯承載網(wǎng)的重映射。大量的學(xué)者對(duì)邏輯承載網(wǎng)的映射做了深入的研究，并取得了豐富的成果。D.G.Andersen 提出了時(shí)間復(fù)雜度為O(log2k)的多通路算法來映射節(jié)點(diǎn)到實(shí)驗(yàn)床[5]。與此同時(shí)，文獻(xiàn)[14]對(duì)于Overlay網(wǎng)絡(luò)的映射問題提出了自己的策略。值得一提的是，華盛頓大學(xué)的J.Lu等為各種特殊的拓?fù)涮岢鰧ｉT的算法[15]以及佐治亞理工學(xué)院的Y.Zhu等提出的能夠根據(jù)網(wǎng)絡(luò)拓?fù)渥鲞m當(dāng)調(diào)整的映射算法[16]。最后，M.Yu總結(jié)了之前的虛擬網(wǎng)映射算法，并提出了分流映射的思想，大大提高了映射效率[6]。

以上的這些工作都沒有從能耗的角度去考慮邏輯承載網(wǎng)的映射問題。當(dāng)前，僅有少數(shù)的學(xué)者從流量工程的角度考慮網(wǎng)絡(luò)的節(jié)能，這些節(jié)能方法或者策略可以歸納到邏輯網(wǎng)映射的節(jié)能問題域。與邏輯網(wǎng)映射問題相似，他們都考慮了流束，從調(diào)整流的角度去釋放某些鏈路的負(fù)荷，再休眠或者關(guān)閉鏈路進(jìn)行節(jié)能。這些節(jié)能算法中的鏈路重映射的方法也不盡相同，其中一部分是基于單徑路由的映射[17]，另一部分是基于多商品流模型的多徑路由映射[18]。無論是基于單徑映射或者是多徑映射，在IP網(wǎng)中，一定要切斷鏈路改變網(wǎng)絡(luò)的邏輯拓?fù)?，進(jìn)而改變數(shù)據(jù)流路由實(shí)現(xiàn)節(jié)能。在當(dāng)前IP網(wǎng)中，網(wǎng)絡(luò)的邏輯拓?fù)浜臀锢砭W(wǎng)拓?fù)涫侵丿B的，流量規(guī)劃后，必然會(huì)依靠切斷物理鏈路進(jìn)行改變邏輯網(wǎng)絡(luò)，實(shí)現(xiàn)數(shù)據(jù)流重定向路徑。同時(shí)，切斷網(wǎng)絡(luò)的物理鏈路無疑會(huì)造成相應(yīng)網(wǎng)絡(luò)鏈路的大量分組丟失和網(wǎng)絡(luò)拓?fù)渲貥?gòu)。由于互聯(lián)網(wǎng)路由快速恢復(fù)策略未得到實(shí)際應(yīng)用，網(wǎng)絡(luò)的恢復(fù)時(shí)間基本上還是完全依靠互聯(lián)網(wǎng)協(xié)議重收斂。在這個(gè)收斂時(shí)間內(nèi)網(wǎng)絡(luò)無法給用戶業(yè)務(wù)提供持續(xù)的網(wǎng)絡(luò)服務(wù)，因此在此期間內(nèi)用戶的業(yè)務(wù)是中斷的。

3 問題描述

本文涉及的節(jié)能問題域與邏輯承載網(wǎng)映射關(guān)注的問題域不同。邏輯承載網(wǎng)的映射問題的核心問題是物理網(wǎng)資源的優(yōu)化配置：即在當(dāng)前的網(wǎng)絡(luò)資源下，接受盡可能多的LCN。而本文的節(jié)能問題域是在多個(gè)邏輯網(wǎng)與物理網(wǎng)映射關(guān)系的基礎(chǔ)上，調(diào)整邏輯網(wǎng)，使得用最少的物理網(wǎng)資源（節(jié)點(diǎn)和鏈路）去承載當(dāng)前網(wǎng)絡(luò)的負(fù)荷。最終，通過休眠或者關(guān)閉冗余的節(jié)點(diǎn)和鏈路，從而實(shí)現(xiàn)節(jié)能的目標(biāo)。

3.1 物理網(wǎng)定義

邏輯承載網(wǎng)表示為Gv=(Nv,Ev,,)。其中Nv表示邏輯承載網(wǎng)的節(jié)點(diǎn)的集合，Ev表示邏輯承載網(wǎng)的鏈路的集合；表示邏輯承載網(wǎng)的約束條件；表示邏輯承載網(wǎng)鏈路的約束條件。

3.2 邏輯承載網(wǎng)映射物理網(wǎng)過程

邏輯承載網(wǎng)映射到物理網(wǎng)分為節(jié)點(diǎn)映射和鏈路映射2個(gè)過程，故可以表示為

與傳統(tǒng)的網(wǎng)絡(luò)構(gòu)架不同，可重構(gòu)網(wǎng)路的路由節(jié)點(diǎn)可以同時(shí)加載多個(gè)路由構(gòu)件，其構(gòu)架如圖1所示，即在物理網(wǎng)中的同一個(gè)節(jié)點(diǎn)可以支撐多種不同類型的網(wǎng)絡(luò)。圖1中，邏輯承載網(wǎng)LCN1被映射到物理網(wǎng){R1→R4→R3}，邏輯承載網(wǎng)LCN2被映射到物理網(wǎng){R1→R2→R3}。LCN1和LCN2可以加載不同的協(xié)議構(gòu)建，因而不同類型的網(wǎng)絡(luò)可以共存于同一物理網(wǎng)。

3.3 算法的節(jié)能原理

在可重構(gòu)網(wǎng)絡(luò)構(gòu)架下，柔性網(wǎng)絡(luò)配置代理（FNCB, flexible network configure broker）負(fù)責(zé)對(duì)域內(nèi)路由節(jié)點(diǎn)資源信息和拓?fù)湫畔⑦M(jìn)行管理，并且可以在同一物理網(wǎng)中基于不同的策略，如貪心法、分流法[6]等，去構(gòu)建邏輯承載網(wǎng)[1]。由于這些策略不同，在映射邏輯承載網(wǎng)的過程中，運(yùn)用統(tǒng)一的節(jié)能策略將是十分困難和低效的。本文關(guān)注的可重構(gòu)網(wǎng)絡(luò)的節(jié)能研究在于當(dāng)映射完所有的邏輯承載網(wǎng)之后，針對(duì)物理網(wǎng)的當(dāng)前流量、拓?fù)浣Y(jié)構(gòu)以及邏輯承載網(wǎng)的分布狀況做統(tǒng)一的節(jié)能調(diào)度。

圖1 可重構(gòu)網(wǎng)絡(luò)的體系結(jié)構(gòu)

在IP網(wǎng)中，廣泛應(yīng)用的路由協(xié)議是OSPF協(xié)議和RIP協(xié)議。路由器總是根據(jù)它所搜集到的鏈路狀態(tài)信息（LSA, link state advertisement）運(yùn)用Dijkstra算法計(jì)算從當(dāng)前節(jié)點(diǎn)到其他網(wǎng)絡(luò)節(jié)點(diǎn)的最優(yōu)路徑樹（OPT, optimal path tree），按照這棵樹對(duì)路由表進(jìn)行更新，從而使得該路由器在路由時(shí)，可以選擇最優(yōu)的路徑。

網(wǎng)絡(luò)領(lǐng)域節(jié)能問題的本質(zhì)是求網(wǎng)絡(luò)拓?fù)涞囊粋€(gè)子集（ST, sub-topology）去承載當(dāng)前網(wǎng)絡(luò)的負(fù)荷，也就是說使用網(wǎng)絡(luò)拓?fù)渲斜M可能少的節(jié)點(diǎn)和鏈路，關(guān)閉或者休眠冗余的節(jié)點(diǎn)和鏈路，從而使得網(wǎng)絡(luò)的能耗降低。本文基于該思想提出了基于可重構(gòu)網(wǎng)絡(luò)的節(jié)能方法（ESMRN, energy-saving method based on the reconfigurable network）。

ESMRN主要將路由器分成3類：一類是關(guān)鍵路由器(KR, key router)，另一類是從屬路由器(AR,associate router)，第三類是普通路由器(NR, normal router)，它既不能化歸為從屬路由也不是關(guān)鍵路由。FNCB可以根據(jù)域內(nèi)路由器廣播的LSA得出網(wǎng)絡(luò)的拓?fù)湫畔ⅲ缓蟀凑斩葦?shù)的大小為權(quán)值評(píng)估出 KR集合(SKR, set of KR)，然后再確定AR集合（SAR，其偽代碼如算法1所示）和NR集合(SNR)。

算法1 divideSets的偽代碼

在本算法中，KR利用 Dijkstra算法根據(jù)當(dāng)前LSA信息庫(kù)計(jì)算 OPT，從而對(duì)自己的路由進(jìn)行更新，而從屬節(jié)點(diǎn)AR是先計(jì)算其鄰接的KR節(jié)點(diǎn)的OPT，然后旋轉(zhuǎn)OPT將自己調(diào)整為根節(jié)點(diǎn)得出自己的OPT，NR則按照OSPF正常路由。在圖2中假設(shè)節(jié)點(diǎn)a是KR節(jié)點(diǎn)，節(jié)點(diǎn)b是AR節(jié)點(diǎn)。圖2(a)是一個(gè)帶有OSPF權(quán)值的網(wǎng)絡(luò)拓?fù)鋱D，圖2(b)是a節(jié)點(diǎn)根據(jù)Dijkstra算法計(jì)算后得到的OPT，圖2(c)是b節(jié)點(diǎn)根據(jù)Dijkstra算法生成的OPT，而圖2(d)則是b節(jié)點(diǎn)根據(jù)ESMRN算法得出的OPT。經(jīng)過本算法處理后，可以得出鏈路lb,j(b, g)是可被關(guān)閉的候選鏈路。如果經(jīng)過重新映射，候選鏈路上的流量可以被規(guī)劃到其他的鏈路，那么關(guān)閉候選鏈路進(jìn)行實(shí)現(xiàn)節(jié)能的目標(biāo)。

圖2 算法的節(jié)能原理

4 基于可重構(gòu)網(wǎng)絡(luò)的節(jié)能方法

4.1 節(jié)能方法的機(jī)制

基于可重構(gòu)網(wǎng)絡(luò)的節(jié)能方法（ESMRN, energy-saving method base on reconfigurable network）主要分成3個(gè)步驟，其偽代碼如算法2所示。第一步FCBN根據(jù)當(dāng)前的網(wǎng)絡(luò)狀態(tài)信息，劃分網(wǎng)絡(luò)節(jié)點(diǎn)的集合類型：SKR、SAR以及SNR。第二步物理網(wǎng)絡(luò)中的節(jié)點(diǎn)分別計(jì)算自己的路由。SKR集合中的節(jié)點(diǎn)根據(jù)Dijkstra算法計(jì)算自己的OPT；SAR中的節(jié)點(diǎn)先計(jì)算其鄰接的KR的OPT，然后旋轉(zhuǎn)該OPT，使得自己為根節(jié)點(diǎn)，再更新路由表；SNR集合中的根據(jù)傳統(tǒng)的OSPF協(xié)議進(jìn)行路由選擇。該算法的第三步統(tǒng)計(jì)SAR集合中的元素AR中可以被刪除的鄰接鏈路lij( i, j)，運(yùn)用多商品流模型將該鏈路上的流量fl映射到G( Np,Ep-l)。如果該流量可以被映射到該子圖上，則休眠該鏈路lij( i, j)，并更新節(jié)點(diǎn)和鏈路。

算法2 ESMRN偽代碼

在經(jīng)過EMRSN算法運(yùn)行到第2)步后，將獲得一個(gè)可關(guān)閉的候選鏈路集合CL。第3)步link_Optimization的功能是對(duì)候選鏈路lij( i, j)上的屬于各個(gè)虛擬網(wǎng)的流量在對(duì)應(yīng)的目標(biāo)子圖G( Np,Ep-l)上，以節(jié)點(diǎn)s, d為源節(jié)點(diǎn)和目的節(jié)點(diǎn)，將流量為帶寬進(jìn)行重新映射，如果該流量可以被重新映射，那么將該鏈路l添加到可刪除鏈路集合L，而node_Optimization則是節(jié)點(diǎn)檢測(cè)是否所有鄰接邊都處于休眠狀態(tài)，如果是，那么休眠該節(jié)點(diǎn)。

本質(zhì)上link_Optimization是一個(gè)多商品流的問題，多商品流問題是一個(gè)經(jīng)典的NP-hard問題。本文選擇利用整數(shù)線性規(guī)劃的方法來處理該問題，如算法3所示?；ヂ?lián)網(wǎng)中的節(jié)能問題歸根結(jié)底是休眠鏈路和節(jié)點(diǎn)，而節(jié)點(diǎn)的休眠實(shí)際上是鏈路休眠的一個(gè)副產(chǎn)品，其前提條件是節(jié)點(diǎn)的所有鄰接鏈路都已休眠。

Equation 1為線性規(guī)劃的目標(biāo)函數(shù)，其中，xij表示鏈路lij( i, j)或者節(jié)點(diǎn)i,j之間是否存在通路，如存在，取值為1，不存在則取值為0；Pij表示鏈路lij( i, j)消耗的電能，因此，T表示網(wǎng)絡(luò)中所有鏈路消耗的能量。Equation 2表示為經(jīng)典的流約束條件，其中，表示源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的經(jīng)過鏈路lij( i, j)的流量。Equation 3和Equation 6為多商品流模型的約束條件；Equation 3表示fij流量是由所有源節(jié)點(diǎn)和目的節(jié)點(diǎn)在鏈路lij( i, j)流量的分量組成，且每一組源節(jié)點(diǎn)和目的節(jié)點(diǎn)的分量之和為1。Equation 4中β為設(shè)置的最大的鏈路利用率(50%)，Cij為鏈路lij(i,j)的帶寬。Equation 5約束可刪除鏈路的搜索空間為CE。

算法3 link_Optimization的解法

4.2 算法的代價(jià)分析

物理網(wǎng)絡(luò)拓?fù)涫且粋€(gè)圖，因此EMSRN算法需要O( N2)的空間存儲(chǔ)物理網(wǎng)拓?fù)洹Ｃ恳粋€(gè)邏輯承載網(wǎng)是一張圖，每個(gè)物理網(wǎng)上對(duì)應(yīng)多個(gè)邏輯承載網(wǎng)，因此需要O( N3)的空間去存儲(chǔ)邏輯承載網(wǎng)與物理網(wǎng)鏈路的映射關(guān)系，綜合該算法的空間復(fù)雜度為O( N3)。EMSRN的第2)步(算法1)內(nèi)主要利用了經(jīng)典的最短路徑算法——Dijstra算法，需要O( N2)的時(shí)間，又因?yàn)槠涮幱谝粋€(gè)循環(huán)內(nèi)，故整個(gè)第2)步的時(shí)間復(fù)雜度為O( N2)。該算法的第3)步是多商品流的線性規(guī)劃處理過程，其具有多項(xiàng)式時(shí)間復(fù)雜度，第4)步則是O( N3)。因此，EMSRN具有多項(xiàng)式時(shí)間的復(fù)雜度，是處于可以被接受的范圍之內(nèi)。

EMSRN算法在當(dāng)前網(wǎng)絡(luò)流量背景下，重映射LCN，使得某些鏈路能夠被釋放出來進(jìn)行節(jié)能。在這個(gè)過程中，必然會(huì)涉及到中心控制，鏈路切換等問題。事實(shí)上，IP網(wǎng)中的節(jié)能算法都會(huì)遇到這些問題，這些問題可能會(huì)在算法運(yùn)行的時(shí)間內(nèi)損害網(wǎng)絡(luò)的QoS，導(dǎo)致網(wǎng)絡(luò)中的節(jié)能算法具有一定的局限性。同時(shí)，網(wǎng)絡(luò)經(jīng)過調(diào)整后，網(wǎng)絡(luò)拓?fù)涞娜哂喽冉档?，在處理新的LCN請(qǐng)求時(shí)，其接受率會(huì)有所降低。

5 仿真實(shí)驗(yàn)與結(jié)果分析

5.1 實(shí)驗(yàn)環(huán)境

本模擬實(shí)驗(yàn)的物理拓?fù)鋱D是由Brite拓?fù)洚a(chǎn)生器[19]生成，它能模擬出最接近現(xiàn)實(shí)的網(wǎng)絡(luò)拓?fù)鋱D。拓?fù)鋱D的帶寬bw符合24～40之間的均勻分布的隨機(jī)數(shù)[16]，為了保證網(wǎng)絡(luò)能夠良好地運(yùn)行，規(guī)定映射時(shí)實(shí)際可用帶寬為β×bw[18]。同時(shí)，網(wǎng)絡(luò)的背景流量由一系列隨機(jī)生成的邏輯承載網(wǎng)映射后生成，這些邏輯承載網(wǎng)的鏈路流量符合3～5之間的均勻分布[16]。這里的拓?fù)鋱D和LCN集合都保存在文本文件中，因此，本實(shí)驗(yàn)?zāi)軌蛑噩F(xiàn)所有的背景流量進(jìn)行反復(fù)模擬。

為了使得實(shí)驗(yàn)更加完備和有說服力，Brite分別產(chǎn)生了節(jié)點(diǎn)數(shù)為{40, 60, 80, 100, 120, 140}的無向稀疏拓?fù)鋱D和無向稠密拓?fù)鋱D2種情況，其配置情況如表1所示。

表1 稀疏拓?fù)鋱D和稠密拓?fù)鋱D配置

EMSRN算法與目前已提交IETF草案的節(jié)能算法GreenTE[18]在上述背景下分別進(jìn)行節(jié)能調(diào)度，并在節(jié)能效果、網(wǎng)絡(luò)時(shí)延和分組丟失率3個(gè)方面做充分的比較。

5.2 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)的過程中，假設(shè)每條鏈路開啟時(shí)，其消耗的能量是相同的，均為，并且將鏈路的最大利用率β設(shè)置為50%。網(wǎng)絡(luò)領(lǐng)域節(jié)能的本質(zhì)是指鏈路的切斷或者休眠條數(shù)，當(dāng)節(jié)點(diǎn)的鄰接鏈路全部切斷或者休眠之后便可關(guān)閉或休眠節(jié)點(diǎn)實(shí)現(xiàn)節(jié)能的目標(biāo)。實(shí)際上，為了實(shí)現(xiàn)所有網(wǎng)絡(luò)節(jié)點(diǎn)的連通，需要的最少鏈路數(shù)為L(zhǎng)min：N-1。假設(shè)節(jié)能算法調(diào)度后，當(dāng)前網(wǎng)絡(luò)由LD條鏈路支撐，整個(gè)網(wǎng)絡(luò)的鏈路條數(shù)為L(zhǎng)D，那么節(jié)能效率η表示為：L-LD/L-Lmin。為了使得本實(shí)驗(yàn)更加具有說服力，針對(duì)每一組拓?fù)洚a(chǎn)生10組背景流量，最后取節(jié)能效果的均值，分別在在稀疏圖和稠密圖上進(jìn)行節(jié)能調(diào)度，其調(diào)度效率如圖3和圖4所示。

圖3 稀疏拓?fù)鋱D上的節(jié)能效率

圖4 稠密拓?fù)鋱D上的節(jié)能效率

同時(shí)，為了測(cè)定節(jié)能算法對(duì)網(wǎng)絡(luò)的影響，在NS-2網(wǎng)絡(luò)仿真器[20]分別部署這2個(gè)算法用于數(shù)據(jù)分組級(jí)模擬。這里的仿真僅僅需要查看算法對(duì)網(wǎng)絡(luò)鏈路的影響，為了方便說明問題，僅僅考慮單流的重定向問題，并將實(shí)驗(yàn)的拓?fù)湓O(shè)定為5個(gè)節(jié)點(diǎn)的全連接且假定這些節(jié)點(diǎn)之間的帶寬為2Mbit/s，然后，在節(jié)點(diǎn)上加載符合Pareto分布的流量[18]，取時(shí)間間隔為0.3s，分別觀察鏈路的分組丟失率與延時(shí)并取平均值，如圖5和圖6所示。

圖5 不同流量下的鏈路分組丟失率

圖6 不同流量下的鏈路延時(shí)

5.3 性能效果分析

本文所提出的EMSRN算法是針對(duì)可重構(gòu)網(wǎng)絡(luò)架構(gòu)而提出的，而GreenTE是基于當(dāng)前的IP網(wǎng)的OSPF協(xié)議和MPLS協(xié)議。圖3和圖4給出了2種節(jié)能算法對(duì)網(wǎng)絡(luò)的調(diào)度效益。

由圖3和圖4可知，當(dāng)物理網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)比較少時(shí)（稀疏圖節(jié)點(diǎn)數(shù)少于60，稠密圖節(jié)點(diǎn)數(shù)少于80），EMSRN算法的調(diào)度相當(dāng)于一個(gè)全局優(yōu)化算法，而GreenTE局限于網(wǎng)絡(luò)的聯(lián)通度局限與一個(gè)局部的搜索，因此EMSRN效果要優(yōu)于GreenTE；當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)比較大時(shí)，其調(diào)度效果略差。

GreenTE實(shí)際上是一個(gè)局部最優(yōu)的搜索算法，其搜索范圍局限于k-最短路徑算法定義的閾值，而EMSRN則是在全局范圍內(nèi)選候選鏈路以及在全局范圍內(nèi)重新映射該鏈路的流量，因此，可以判斷在物理網(wǎng)節(jié)點(diǎn)數(shù)較少的情況下，EMSRN的節(jié)能效益會(huì)優(yōu)于GreenTE。但是，在拓?fù)鋱D十分龐大的情況下，網(wǎng)絡(luò)的連通度很大，因此，閾值對(duì)k-最短路徑算法的影響比較小，即一個(gè)不大的閾值便可以搜索全網(wǎng)的路徑，它可以近似為一個(gè)全局的最優(yōu)化算法。在這種情況下，EMSRN專注于切斷AR的鄰接鏈路來實(shí)現(xiàn)節(jié)能的目標(biāo)，并沒有從全網(wǎng)流量規(guī)劃的角度去考慮總體的路徑優(yōu)化策略，導(dǎo)致了節(jié)能的效益相對(duì)于GreenTE略差。

從圖5和圖6中可以得出，EMSRN算法相對(duì)于 GreenTE具有較低的鏈路分組丟失率和延時(shí)。EMSRN算法的本質(zhì)是FCBN管理的一個(gè)靜態(tài)路由的管理框架。當(dāng)鏈路的路徑需要改變時(shí)，僅僅需要FCBN計(jì)算好鏈路后，重新發(fā)送路由配置命令對(duì)各關(guān)聯(lián)節(jié)點(diǎn)的路由進(jìn)行重新配置即可。GreenTE雖然利用了MPLS的方法來減輕OSPF的收斂過程對(duì)網(wǎng)絡(luò)QoS的影響，但是MPLS的構(gòu)建需要一個(gè)感知網(wǎng)絡(luò)拓?fù)渥兓倪^程和一個(gè)路由的適配過程，在這 2個(gè)過程中，該鏈路中對(duì)應(yīng)流量的數(shù)據(jù)分組則全被丟棄，嚴(yán)重影響了網(wǎng)絡(luò)的QoS。而FCBN則是根據(jù)現(xiàn)存的網(wǎng)絡(luò)拓?fù)湫畔⒌挠涗涍M(jìn)行選路，因此，沒有這個(gè)感知拓?fù)渥兓倪^程，從而導(dǎo)致了其網(wǎng)絡(luò)延時(shí)較少，分組丟失率也較小，其分組丟失的過程主要發(fā)生在重新適配路由的時(shí)間段，GreenTE除了該階段沒法正常提供服務(wù)外，也沒有能力在感知拓?fù)涞碾A段內(nèi)承擔(dān)數(shù)據(jù)分組的發(fā)送，故其分組丟失率會(huì)比較大，延時(shí)也相對(duì)較大。

6 結(jié)束語

互聯(lián)網(wǎng)中的節(jié)能必然要對(duì)物理鏈路或者物理路由器做休眠或者關(guān)閉等處理來實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的邏輯拓?fù)涞母脑?。傳統(tǒng)的IP網(wǎng)的邏輯拓?fù)浜臀锢硗負(fù)涫侵丿B的，切斷或者休眠物理鏈路肯定會(huì)對(duì)邏輯拓?fù)湓斐捎绊懀欢〞?huì)在一定程度上停滯或者中斷用戶業(yè)務(wù)，影響QoS保障。這種情況下，節(jié)能的研究用途并不大。

然后，新型的可重構(gòu)網(wǎng)絡(luò)架構(gòu)是下一代網(wǎng)絡(luò)的發(fā)展方向，其路由的配置策略對(duì)網(wǎng)絡(luò)服務(wù)的影響輕微，從而使得網(wǎng)絡(luò)節(jié)能變?yōu)楝F(xiàn)實(shí)。本文僅僅分析了可重構(gòu)網(wǎng)絡(luò)下的節(jié)能方法，并與認(rèn)可度極高的基于流量規(guī)劃的節(jié)能算法——GreenTE做了詳細(xì)比較，分析了異同點(diǎn)和其優(yōu)勢(shì)。下一步的工作在于研究可重構(gòu)網(wǎng)絡(luò)下的節(jié)能協(xié)議以及如何構(gòu)建一個(gè)節(jié)能的下一代新型互聯(lián)網(wǎng)。

[1] 趙昕, 蘭巨龍等. 可重構(gòu)網(wǎng)絡(luò)中柔性網(wǎng)絡(luò)配置代理服務(wù)提供模型[J]. 信息工程大學(xué)學(xué)報(bào), 2009, 10(1): 61-63.ZHAO X, LAN J L, et al. Model of service-oriented for flexible network configure broker in the reconfigurable network[J]. Journal of Information Engineering University, 2009, 10(1): 61-63.

[2] 陳文龍, 徐恪等. 基于構(gòu)件的可重構(gòu)路由開發(fā)環(huán)境[J]. 信息工程大學(xué)學(xué)報(bào),2009,10(1):28-33.CHEN W L, XU K, et al. Components-based reconfigurable routing development environment[J]. Journal of Information Engineering University, 2009, 10(1): 28-33.

[3] 姜明, 閔嘯等. 邏輯承載網(wǎng)構(gòu)建中的數(shù)學(xué)模型[J]. 信息工程大學(xué)學(xué)報(bào), 2009, 10(1):50-52.JIANG M, MIN X, et al. Mathematical modeling in construction of logical carrying networks[J]. Journal of Information Engineering University, 2009, 10(1): 50-52.

[4] MOSHARAF N M, CHOWDHURY K, et al. Virtual network embedding with coordinated node and link mapping[A]. Proc IEEE INFOCOM 2009[C]. Rio de Janeiro, Brazil, 2009. 783-791.

[5] ANDERSEN D G. Theoretical approaches to node assignment[EB/OL]. http: //www.cs.cmu.edu/～dga/, 2002.

[6] YU M, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. Communication, 2008,38(2):17-29.

[7] WANG Y, et al. Virtual routers on the move: live router migration as a network-management primitive[A]. Proc ACM SIGCOMM 2008[C].Seattle, USA, 2008.231-242.

[8] KOOMEY J G. Estimating total power consumption by servers in the U S and the world[D]. Staff Scientist, Lawrence Berkeley National Laboratory and Consulting Professor, Stanford University, 2007.

[9] REVIRIEGO P, HERNANDEZ J A, LARRABEITI D, et al. Performance evaluation of energy efficient Ethernet[J]. IEEE Communications Letters, 2009, 13(9):697-699.

[10] MANDVIWALLA M, et al. Energy-efficient scheme for multiprocessor-based router line cards[A]. Symposium on Applications and the Internet[C]. 2006.

[11] SUGISONO K, et al. Path Engineering for Power Consumption[R].The Institute of Electronics, Information and Communication Engineers Technical Report NS2007-1, 2007.

[12] AKIKO Y, SATOSHI I, et al. A Path-based traffic control method for green network[A]. Proc of 8th APSITT[C]. Kuching, Malaysia, 2010.1-5.

[13] YAMADA A, et al. A study for green network (3)-eco routing[A].The Institute of Electronics, Information and Communication Engineers General Conference[C]. 2009.

[14] FAN J, et al. Dynamic topology configuration in service overlay networks: a study of reconfiguration polices[A]. Proc IEEE INFOCOM 2006[C]. Barcelona, Spain, 2006.

[15] LU J, et al. Efficient Mapping of Virtual Networks Onto a Shared Substrate[R]. Washington University, Tech. Rep. WUCSE-2006-35,2006.

[16] ZHU Y, et al. Algorithms for assigning substrate network resources to virtual network components[A]. Proc IEEE INFOCOM 2006[C]. Barcelona, Spain, 2006.

[17] LAI P, et al. Configuring network topology towards energy-efficient IP networks[A]. Proc IEEE ICCSN 2011[C]. Xi’an, China, 2011.

[18] ZHANG M G, YI C, LIU B, et al. GreenTE: Power-aware traffic engineering[A]. Proc of 18th ICNP[C]. Kyoto, Japan, 2010. 21-30.

[19] BRITE [EB/OL]. http://www.cs.bu.edu/brite/.

[20] Network Simulator ns-2[EB/OL]. http://www.isi.edu/nsnam/ns/.