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

無效

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

1.一種基于約束路由的綠色虛擬拓?fù)湓O(shè)計(jì)方法，其特征在于建立該方法的步驟如下：

1）GVTD（Green?Virtual?Topology?Design，綠色虛擬拓?fù)湓O(shè)計(jì)）模型主要包括：

◆網(wǎng)絡(luò)功耗模型，即GVTD模型的目標(biāo)函數(shù)，網(wǎng)絡(luò)功耗模型同時(shí)考慮網(wǎng)絡(luò)設(shè)備的靜態(tài)功耗和動(dòng)態(tài)功耗，靜態(tài)功耗指網(wǎng)絡(luò)設(shè)備獨(dú)立于業(yè)務(wù)負(fù)載的那部分功耗（即空閑狀態(tài)下的功耗），動(dòng)態(tài)功耗指網(wǎng)絡(luò)設(shè)備依賴業(yè)務(wù)負(fù)載的那部分功耗，根據(jù)網(wǎng)絡(luò)設(shè)備的模塊化結(jié)構(gòu)，靜態(tài)功耗可進(jìn)一步細(xì)分為接口功耗、線卡功耗和機(jī)框功耗；

◆業(yè)務(wù)路由，即GVTD模型的路由約束，為了避免多徑路由引發(fā)的時(shí)延抖動(dòng)，GVTD模型使用單徑路由；

◆資源配置，即GVTD模型的資源約束，該約束確定每個(gè)結(jié)點(diǎn)的活躍網(wǎng)絡(luò)資源，并按照多粒度睡眠機(jī)制使空閑的網(wǎng)絡(luò)資源睡眠；

◆虛擬拓?fù)湓O(shè)計(jì)，對(duì)應(yīng)于GVTD模型的鏈路容量約束，該約束確定網(wǎng)絡(luò)中需要建立的傳輸通道，此外，通過設(shè)定接口最大利用率參數(shù)，實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)擁塞的控制；

2）GVTD模型的形式化描述如下：

◆目標(biāo)函數(shù)定義如下：

MinΣ_i∈N[n^c(i)·p^c+n^l(i)·p^l+nⁱ(i)·pⁱ]+Σ_{i，j∈N：i≠j}t(i，j)·p^t??(1)

受限于:

Σj∈N:j≠iiδ(ii,jj,ii,j)-Σj∈N:j≠iiδ(ii,jj,j,ii)=1∀ii,jj∈N:d(ii,jj)>0---(2b)]]>

Σi∈N:i≠jjδ(ii,jj,i,jj)-Σi∈N:i≠jjδ(ii,jj,jj,i)=1∀ii,jj∈N:d(ii,jj)>0---(2c)]]>

Σj∈N:j≠iδ(ii,jj,i,j)≤1∀ii,jj,i∈N:d(ii,jj)>0---(2d)]]>

Σj∈N:j≠iδ(ii,jj,j,i)≤1∀ii,jj,i∈N:d(ii,jj)>0---(2e)]]>

t(i,j)=Σii,jj∈N:d(ii,jj)>0δ(ii,jj,i,j)·d(ii,jj)∀i,j∈N:i≠j---(3)]]>

t(i,j)≤d′(i,j)·α·C∀i,j∈N:i≠j---(4)]]>

ni(i)≥Σj∈N:j≠id′(i,j)∀i∈N---(5a)]]>

ni(i)≥Σj∈N:j≠id′(j,i)∀i∈N---(5b)]]>

nl(i)·mi≥ni(i)∀i∈N---(6)]]>

nc(i)·ml·mi≥ni(i)∀i∈N---(7)]]>

各式中參數(shù)定義如下：

N表示網(wǎng)絡(luò)結(jié)點(diǎn)集合，

i,j,ii,jj∈N表示網(wǎng)絡(luò)結(jié)點(diǎn)，

C表示接口的容量，

α表示接口（或鏈路）所允許的最大利用率，

p^t表示網(wǎng)絡(luò)資源處理單位(1Gbps）業(yè)務(wù)負(fù)載的動(dòng)態(tài)功耗，

pⁱ,p^l和p^c分別表示單個(gè)接口、線卡和機(jī)框的功耗，

mⁱ,m^l分別表示每個(gè)線卡具有的接口數(shù)量和每個(gè)機(jī)框可配備的線卡數(shù)量，

D表示網(wǎng)絡(luò)的業(yè)務(wù)需求集合，

d(ii,jj)∈D表示從結(jié)點(diǎn)ii到結(jié)點(diǎn)jj的業(yè)務(wù)需求，

目標(biāo)函數(shù)(式(1))最小化整個(gè)網(wǎng)絡(luò)的功耗，網(wǎng)絡(luò)功耗由靜態(tài)功耗和動(dòng)態(tài)功耗兩部分組成，靜態(tài)功耗可進(jìn)一步分為機(jī)框功耗n^c(i)·p^c、線卡功耗n^l(i)·p^l和接口功耗nⁱ(i)·pⁱ，使用線性函數(shù)近似動(dòng)態(tài)功耗與業(yè)務(wù)負(fù)載的關(guān)系，即t(i,j)·p^t，路由約束（式(2a)～(2e)）為經(jīng)典的多品種流守恒約束，業(yè)務(wù)需求d(ii,jj)經(jīng)過單條路徑從源結(jié)點(diǎn)ii到達(dá)目的結(jié)點(diǎn)jj，式(3)計(jì)算經(jīng)過邏輯鏈路(i,j)的業(yè)務(wù)負(fù)載（即鏈路流量），鏈路的容量約束（式(4)）確保鏈路的流量不超過鏈路的容量，IP層的鏈路(i,j)為邏輯鏈路，由下層網(wǎng)絡(luò)提供的d′(i，j)條傳輸通道組成，每條傳輸通道的容量為C，并引入最大利用率α以應(yīng)對(duì)IP業(yè)務(wù)的動(dòng)態(tài)特性，IP層虛擬拓?fù)涞拇_立過程即為決策變量d′(i，j)的值的確立過程，因此，式(4)在實(shí)現(xiàn)鏈路容量約束的同時(shí)還實(shí)現(xiàn)了IP層的虛擬拓?fù)湓O(shè)計(jì)，實(shí)現(xiàn)了IP層的邏輯鏈路與下層網(wǎng)絡(luò)提供的傳輸通道的映射（即IP層與下層網(wǎng)絡(luò)的層間約束），式(5)-(7)為資源約束，其中，式(5a)和(5b)可確保結(jié)點(diǎn)提供足夠的活躍接口，即活躍接口不應(yīng)該少于傳輸通道所需的發(fā)送端口（式(5a)）和接收端口（式(5b)），式(6)和(7)確保結(jié)點(diǎn)能提供足夠的活躍線卡和活躍機(jī)框，即活躍線卡和活躍機(jī)框提供的接口數(shù)不少于活躍接口數(shù)；

◆GVTD模型的決策變量定義如下：

δ(ii,jj,i,j)∈{0,1}：業(yè)務(wù)需求d(ii,jj)的路徑是否經(jīng)過邏輯鏈路(i,j)，1表示經(jīng)過，0表示不經(jīng)過；

d’(i,j)∈Z⁺：邏輯鏈路(i,j)包含的傳輸通道數(shù)量，其中，Z⁺表示正整數(shù)集合，傳輸通道由下層網(wǎng)絡(luò)提供，而且每條傳輸通道需要消耗一個(gè)發(fā)送端口和接收端口；

t(i,j)∈R⁺：邏輯鏈路(i,j)上的總業(yè)務(wù)量，其中R⁺表示正實(shí)數(shù)集合；

nⁱ(i)∈Z⁺：網(wǎng)絡(luò)結(jié)點(diǎn)i的活躍接口數(shù)量；

n^l(i)∈Z⁺：網(wǎng)絡(luò)結(jié)點(diǎn)i的活躍線卡數(shù)量；

n^c(i)∈Z⁺：網(wǎng)絡(luò)結(jié)點(diǎn)i的活躍機(jī)框數(shù)量，

3）GVTD模型采用CBR-GVTD（Constraint-Based?Routing?Green?Virtual?Topology?Design，基于約束路由的綠色虛擬拓?fù)湓O(shè)計(jì)）啟發(fā)式方法求解

4）CBR-GVTD方法需要用到的式子如下：

◆nⁱ(i)，n^l(i)和n^c(i)的值由以下式子確定：

ni(i)=max(Σj∈N:j≠id′(i,j),Σj∈N:j≠id′(j,i))∀i∈N---(8)]]>

◆通過以下方式計(jì)算目標(biāo)函數(shù)的下界值：

Σ_{i，j∈N：i≠j}t(i，j)＝Σ_{i，j∈N：i≠j}d(i，j)??(12)

式(11)中，∑_j∈N:j≠id(i,j)和∑_j∈N:j≠id(j,i)分別表示結(jié)點(diǎn)i發(fā)送和接收的業(yè)務(wù)量的下界，α·C為每個(gè)接口允許的最大容量，將式（11）代入式(8)～(10)可以分別求得n^l(i)_lb和n^c(i)_lb，最后將這些決策變量代入目標(biāo)函數(shù)式（1）中可得目標(biāo)函數(shù)的下界為

5）CBR-GVTD方法描述如下：

◆輸入包括N,D,α,C,p^t,pⁱ,p^l,p^c,mⁱ,m^l和H

◆輸出為網(wǎng)絡(luò)功耗和步驟2）中定義的決策變量；

◆CBR-GVTD方法步驟如下：

①根據(jù)式(11)用下界值nⁱ(i)_lb初始化每個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)的接口數(shù)nⁱ(i)，

②按照從大到小的順序?yàn)槊總€(gè)業(yè)務(wù)需求d(i,j)建立從i到j(luò)的傳輸通道，并進(jìn)行單跳路由，每個(gè)傳輸通道消耗源結(jié)點(diǎn)i的一個(gè)發(fā)送端口和目的結(jié)點(diǎn)j的一個(gè)接收端口，直到到接口耗盡、沒有傳輸通道可以建立為止；

③在步驟②建立的虛擬拓?fù)浠A(chǔ)上，限制網(wǎng)絡(luò)的最大跳數(shù)為H，利用單跳路由的剩余帶寬，對(duì)剩余的業(yè)務(wù)需求按照從大到小的順序進(jìn)行CBR-Dijkstra（Constraint-Based?Routing?Dijkstra，基于約束路由的Dijkstra）路由；

④如果對(duì)業(yè)務(wù)需求d(i,j)路由失敗，則增加結(jié)點(diǎn)i和j的接口，為i到j(luò)建立傳輸通道并消耗相應(yīng)的接口數(shù)，這表明網(wǎng)絡(luò)的虛擬拓?fù)浒l(fā)生了變化；

⑤如果網(wǎng)絡(luò)虛擬拓?fù)浒l(fā)生變化，則迭代步驟①～④；

⑥初始化鏈路集合E’為當(dāng)前的邏輯鏈路集合E；

⑦從E’中取出剩余帶寬最大的邏輯鏈路(i，j)并將(i，j)從E’中去除；

⑧嘗試移除從i到j(luò)的1條傳輸通道，限制網(wǎng)絡(luò)的最大跳數(shù)為H，對(duì)經(jīng)過邏輯鏈路(i，j)的所有業(yè)務(wù)需求進(jìn)行CBR-Dijkstra重路由，如果重路由成功，則釋放該傳輸通道消耗的接口，否則恢復(fù)移除的傳輸通道；

⑨若E′中還有鏈路，則更新鏈路的剩余帶寬，轉(zhuǎn)到步驟⑦；

⑩移除每個(gè)結(jié)點(diǎn)剩余的接口，計(jì)算nⁱ(i)的最終值，通過式(3)、(9)和(10)分別確定t(i，j)、n^l(i)和n^c(i)，再通過式(1)計(jì)算整個(gè)網(wǎng)絡(luò)的功耗；

6）CBR-Dijkstra方法描述如下：

◆輸入包括業(yè)務(wù)需求d(i,j)，網(wǎng)絡(luò)結(jié)點(diǎn)集合N，網(wǎng)絡(luò)鏈路集合E，網(wǎng)絡(luò)鏈路的可用帶寬集合B和網(wǎng)絡(luò)的最大路由跳數(shù)H；

◆輸出為d(i,j)的路徑；

◆CBR-Dijkstra方法步驟如下：

①?gòu)脑唇Y(jié)點(diǎn)i開始，計(jì)算源結(jié)點(diǎn)i的最短路徑生成樹，直到計(jì)算出到目標(biāo)結(jié)點(diǎn)j的路徑時(shí)停止；

②只考慮可用帶寬大于業(yè)務(wù)需求的路徑，當(dāng)跳數(shù)相同時(shí)，選擇可用帶寬最小的路徑；

③如果計(jì)算的最短路徑小于網(wǎng)絡(luò)的最大跳數(shù)H，則路由成功，計(jì)算結(jié)果為前驅(qū)結(jié)點(diǎn)表示的最短路徑，否則結(jié)果為NIL，表示路由失敗。