[發(fā)明專利]一種基于部分部署的分段路由網(wǎng)絡(luò)的流量工程方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201811234886.0
• 申請(qǐng)日: 2018-10-23
• 公開（公告）號(hào): CN109194577B
• 公開（公告）日: 2020-04-10
• 發(fā)明（設(shè)計(jì)）人: 王之梁;田瑩;尹霞;施新剛;郭迎亞
• 申請(qǐng)（專利權(quán)）人: 清華大學(xué)
• 主分類號(hào): H04L12/721
• 分類號(hào): H04L12/721;H04L12/751;H04L12/24
• 代理公司: 北京安信方達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 11262
• 代理人: 李紅爽;龍洪

1.一種基于部分部署的分段路由網(wǎng)絡(luò)的流量工程方法，其特征在于，包括：

獲取分段路由網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)湟约傲髁烤仃嚕?/p>

通過多次迭代運(yùn)算，確定所述分段路由網(wǎng)絡(luò)的最小化的最大鏈路利用率；其中，每次迭代運(yùn)算中分別進(jìn)行以下處理：

根據(jù)所述網(wǎng)絡(luò)拓?fù)洹⒅八阉鞯降淖顑?yōu)的網(wǎng)絡(luò)鏈路權(quán)重矩陣以及預(yù)設(shè)的重置比例，確定本次搜索得到的網(wǎng)絡(luò)鏈路權(quán)重矩陣；

根據(jù)所述網(wǎng)絡(luò)拓?fù)洹⑺隽髁烤仃嚒⒈敬嗡阉鞯玫降木W(wǎng)絡(luò)鏈路權(quán)重矩陣以及分段路由節(jié)點(diǎn)的部署率，確定本次選擇的分段路由節(jié)點(diǎn)集合；

根據(jù)所述網(wǎng)絡(luò)拓?fù)洹⑺隽髁烤仃嚒⒈敬嗡阉鞯玫降木W(wǎng)絡(luò)鏈路權(quán)重矩陣以及本次選擇的分段路由節(jié)點(diǎn)集合，確定本次運(yùn)算中所述分段路由網(wǎng)絡(luò)的最小化的最大鏈路利用率、所述流量矩陣中每條流的可用路徑以及在所述可用路徑上的最佳分流比；

當(dāng)?shù)螖?shù)等于預(yù)設(shè)次數(shù)，則將多次迭代運(yùn)算中得到的最大鏈路利用率的最小值確定為所述分段路由網(wǎng)絡(luò)的最小化的最大鏈路利用率；

當(dāng)所述迭代次數(shù)小于所述預(yù)設(shè)次數(shù)，則執(zhí)行下一次迭代運(yùn)算。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述網(wǎng)絡(luò)拓?fù)洹⒅八阉鞯降淖顑?yōu)的網(wǎng)絡(luò)鏈路權(quán)重矩陣以及預(yù)設(shè)的重置比例，確定本次搜索得到的網(wǎng)絡(luò)鏈路權(quán)重矩陣，包括：

通過弗洛伊德函數(shù)，計(jì)算出在之前搜索到的最優(yōu)的網(wǎng)絡(luò)鏈路權(quán)重矩陣下所述分段路由網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間的最短路；

根據(jù)計(jì)算得到的最短路以及所述流量矩陣，計(jì)算每條鏈路的利用率；

將所述分段路由網(wǎng)絡(luò)中的鏈路按照所述利用率從大到小的順序進(jìn)行排序；

根據(jù)所述重置比例，將排序后的鏈路分成三個(gè)集合；

分別調(diào)整所述三個(gè)集合中的鏈路的權(quán)重，確定本次搜索得到的網(wǎng)絡(luò)鏈路權(quán)重矩陣。

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述分別調(diào)整所述三個(gè)集合中的鏈路的權(quán)重，包括：

將第一集合中的鏈路的權(quán)重分別升高[0，x]間的一個(gè)隨機(jī)整數(shù)值；

將第二集合中的鏈路的權(quán)重分別降低[0，x]間的一個(gè)隨機(jī)整數(shù)值；

將第三集合中待重置權(quán)重的鏈路的權(quán)重按照均等概率隨機(jī)升高[0，x]間的一個(gè)隨機(jī)整數(shù)值，或者，降低[0，x]間的一個(gè)隨機(jī)整數(shù)值；

其中，x為正整數(shù)；所述第一集合中的鏈路的利用率大于所述第三集合中的鏈路的利用率，所述第三集合中的鏈路的利用率大于所述第二集合中的鏈路的利用率。

4.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述網(wǎng)絡(luò)拓?fù)洹⑺隽髁烤仃嚒⒈敬嗡阉鞯玫降木W(wǎng)絡(luò)鏈路權(quán)重矩陣以及分段路由節(jié)點(diǎn)的部署率，確定本次選擇的分段路由節(jié)點(diǎn)集合，包括：

通過弗洛伊德函數(shù)，計(jì)算出在本次搜索得到的網(wǎng)絡(luò)鏈路權(quán)重矩陣下所述分段路由網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間的最短路；

根據(jù)計(jì)算得到的最短路以及所述流量矩陣，計(jì)算每條鏈路的利用率；

針對(duì)每個(gè)節(jié)點(diǎn)，計(jì)算以所述節(jié)點(diǎn)為起點(diǎn)的鏈路的利用率的最大值，作為所述節(jié)點(diǎn)的最大鏈路利用率；

將所述分段路由網(wǎng)絡(luò)中的節(jié)點(diǎn)按照各自的最大鏈路利用率從大到小的順序進(jìn)行排序；

按照所述節(jié)點(diǎn)的最大鏈路利用率從大到小的順序，選擇目標(biāo)數(shù)目的節(jié)點(diǎn)加入分段路由節(jié)點(diǎn)集合，其中，所述目標(biāo)數(shù)據(jù)大于或等于待部署分段路由節(jié)點(diǎn)總數(shù)，所述待部署分段路由節(jié)點(diǎn)總數(shù)根據(jù)所述分段路由網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)與所述分段路由節(jié)點(diǎn)的部署率確定。

5.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述網(wǎng)絡(luò)拓?fù)洹⑺隽髁烤仃嚒⒈敬嗡阉鞯玫降木W(wǎng)絡(luò)鏈路權(quán)重矩陣以及本次選擇的分段路由節(jié)點(diǎn)集合，確定本次運(yùn)算中所述分段路由網(wǎng)絡(luò)的最小化的最大鏈路利用率、所述流量矩陣中每條流的可用路徑以及在所述可用路徑上的最佳分流比，包括：

根據(jù)所述網(wǎng)絡(luò)拓?fù)洹⑺隽髁烤仃嚒⒈敬嗡阉鞯玫降木W(wǎng)絡(luò)鏈路權(quán)重矩陣以及本次選擇的分段路由節(jié)點(diǎn)集合，計(jì)算出所述流量矩陣中每條流的可用路徑；

構(gòu)造線性規(guī)劃問題，其中，目標(biāo)為最小化所述分段路由網(wǎng)絡(luò)的最大鏈路利用率，變量為每條流在可用路徑上的分流比；

求解所述線性規(guī)劃問題，得到每條流在可用路徑上的最佳分流比以及所述分段路由網(wǎng)絡(luò)的最小化的最大鏈路利用率。