[發(fā)明專利]一種基于約束路由的綠色虛擬拓?fù)湓O(shè)計方法

無效

• 申請?zhí)枺?/td>: 201310136979.0
• 申請日: 2013-04-19
• 公開（公告）號: CN104113480A
• 公開（公告）日: 2014-10-22
• 發(fā)明（設(shè)計）人: 郭兵;沈艷;伍元勝;徐闊海;劉凡;羅標(biāo);張強(qiáng);張俊濤
• 申請（專利權(quán)）人: 成都賽恩泰科技有限公司
• 主分類號: H04L12/751
• 分類號: H04L12/751;H04L12/801
• 代理公司: 暫無信息
• 代理人: 暫無信息

所屬技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)能耗優(yōu)化技術(shù)領(lǐng)域，尤其是涉及一種基于約束路由的綠色虛擬拓?fù)湓O(shè)計方法。

背景技術(shù)

近年來，Internet的流量逐年指數(shù)增長。從2007到2011年，Internet的流量和帶寬的年平均增長率分別達(dá)到了56%和58%。流量和帶寬的增長導(dǎo)致了Internet的能耗上升。據(jù)估計，2007年Internet的電力消耗達(dá)到了寬帶接入國家（其平均接入帶寬為30Mbps）總電量的1%，當(dāng)平均接入帶寬達(dá)到300Mbps時，這個比例將超過4%。按照目前的增長速度，到2050年網(wǎng)絡(luò)領(lǐng)域的耗電量將達(dá)到2006年的13倍。Internet能耗的快速增長不僅導(dǎo)致電力成本的持續(xù)上升，同時也造成溫室氣體的加速排放。因此，提高能量效率和降低能耗已成為Internet面臨的重大研究課題。目前，隨著網(wǎng)絡(luò)的扁平化發(fā)展，Internet的層次變得更加簡單，逐漸演變成由接入網(wǎng)和核心網(wǎng)兩部分組成。由于接入網(wǎng)的“光進(jìn)銅退”以及核心網(wǎng)對接入網(wǎng)流量的匯聚，核心網(wǎng)正經(jīng)歷比接入網(wǎng)更快的能耗增長。研究表明到2017年核心網(wǎng)能耗將超過接入網(wǎng)。因此，在整個Internet中，核心網(wǎng)的節(jié)能研究正變得日益重要。

在核心網(wǎng)中，IP網(wǎng)絡(luò)層通常構(gòu)建于高速的TDM(Time?Division?Multiplexing)網(wǎng)絡(luò)層或者WDM(Wavelength?Division?Multiplexing)網(wǎng)絡(luò)層之上，形成所謂的IP?over?SONET/SDH/OTN網(wǎng)絡(luò)或IP?over?WDM網(wǎng)絡(luò)。下層網(wǎng)絡(luò)（即TDM層或WDM層）向IP層提供通道傳輸服務(wù)（即TDM電路服務(wù)和光路服務(wù)，電路和光路統(tǒng)稱為傳輸通道），IP層通過使用下層提供的通道傳輸服務(wù)向其上層提供分組傳輸服務(wù)。IP層的鏈路由1條或多條具有相同源結(jié)點和目的結(jié)點的傳輸通道組成，這種鏈路不同于傳統(tǒng)的物理鏈路，因此被稱為邏輯鏈路，由邏輯鏈路構(gòu)成的網(wǎng)絡(luò)拓?fù)浔环Q為虛擬拓?fù)洌ɑ蜻壿嬐負(fù)洌８鶕?jù)給定的業(yè)務(wù)需求建立IP層邏輯鏈路的過程即為IP層的虛擬拓?fù)湓O(shè)計(VTD:Virtual?Topology?Design)過程。對于IP層，下層提供的傳輸通道組成了其邏輯鏈路；對于下層網(wǎng)絡(luò)，IP層請求建立的傳輸通道形成了其業(yè)務(wù)需求。

網(wǎng)絡(luò)按照峰值業(yè)務(wù)需求超額供給網(wǎng)絡(luò)資源，并通冗余設(shè)計來提高網(wǎng)絡(luò)的可靠性，這導(dǎo)致了網(wǎng)絡(luò)資源的平均利用率低下，而當(dāng)前利用率對網(wǎng)絡(luò)資源的功耗影響卻較小，因此，提高網(wǎng)絡(luò)資源利用率并將空閑的網(wǎng)絡(luò)資源關(guān)閉（或轉(zhuǎn)入低功耗睡眠狀態(tài)）是目前降低網(wǎng)絡(luò)能耗的一個重要途徑。有研究者利用混合整數(shù)線性規(guī)劃(MILP，Mixed?Integer?Linear?Programming)技術(shù)建模功率感知的網(wǎng)絡(luò)設(shè)計和路由問題，通過為網(wǎng)絡(luò)節(jié)點選擇合適數(shù)量和類型的線卡最小化IP網(wǎng)絡(luò)的功耗，但卻沒有設(shè)計有效的啟發(fā)式方法來求解NP難的MILP模型。有研究者將IP網(wǎng)絡(luò)的綠色流量工程形式化為一個MILP模型，并提出了一種啟發(fā)式解法，通過預(yù)先為每對結(jié)點計算k條候選最短路徑來降低MILP問題的解空間和求解時間，但是，解空間依然隨結(jié)點對的數(shù)量指數(shù)增長。有研究者提出一種基于拉格朗日松弛的啟發(fā)式方法，將建立的形式化模型分解為容易求解的子問題，為鏈路設(shè)定合適的權(quán)值進(jìn)行動態(tài)路由，關(guān)閉盡多的鏈路以降低IP網(wǎng)絡(luò)的能耗。與通常改變已有的網(wǎng)絡(luò)拓?fù)洳煌袑W(xué)者研究如何確立網(wǎng)絡(luò)拓?fù)洌刺摂M拓?fù)湓O(shè)計問題。有學(xué)者考慮光收發(fā)器和電交換的功耗，將功率感知的虛擬拓?fù)湓O(shè)計的形式化為MILP問題，并提出一個簡單的貪婪方法和遺傳方法求解。該遺傳方法并沒有相應(yīng)的機(jī)制保證得到的后代個體滿足MILP模型的約束條件，而是簡單的舍棄不滿足約束的個體，這會導(dǎo)致方法有時找不到可行解。有學(xué)者只考慮線卡的功耗，將最小化能耗的虛擬拓?fù)湓O(shè)計問題形式化為一個簡單的整數(shù)線性規(guī)劃(ILP，Integer?Linear?Programming)模型，并提出了一個兩階段的啟發(fā)式解法。由于作者只考慮了線卡的功耗，建立的ILP模型過于簡單，網(wǎng)絡(luò)傾向于建立一個星型虛擬拓?fù)洌钚』溌返臄?shù)量。

現(xiàn)有工作存在以下不足。首次，都只考慮網(wǎng)絡(luò)設(shè)備的部分組件的功耗，如鏈路、收發(fā)器或線卡，忽略了其它部分的功耗，這樣使得最終得到的解只能使整個網(wǎng)絡(luò)中的這些組件的功耗最低，而不是整個網(wǎng)絡(luò)的功耗最低。其次，核心網(wǎng)絡(luò)的網(wǎng)絡(luò)設(shè)備通常采用模塊化設(shè)計，現(xiàn)有的工作沒有考慮網(wǎng)絡(luò)設(shè)備的模塊化結(jié)構(gòu)。第三，由于問題的復(fù)雜性（NP問題），現(xiàn)有工作要么建立的形式化模型過于復(fù)雜，以至于不能有效求解，要么建立的模型過于簡化而忽略重要特性，如有些只考慮鏈路或線卡功耗忽略了IP路由器處理流量的功耗。