[發(fā)明專利]一種動(dòng)態(tài)鏈路故障保護(hù)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810457415.X
• 申請(qǐng)日: 2018-05-14
• 公開（公告）號(hào): CN108683579A
• 公開（公告）日: 2018-10-19
• 發(fā)明（設(shè)計(jì)）人: 盧薇至;吳斌;李伯宇
• 申請(qǐng)（專利權(quán)）人: 天津大學(xué)
• 主分類號(hào): H04L12/437
• 分類號(hào): H04L12/437;H04B10/032;H04B10/035;H04B10/275
• 代理公司: 天津市北洋有限責(zé)任專利代理事務(wù)所 12201
• 代理人: 程毓英

本發(fā)明涉及一種動(dòng)態(tài)鏈路故障保護(hù)方法，包括：交換機(jī)在工作中一定時(shí)間內(nèi)會(huì)積累流量矩陣，通過適應(yīng)算法重配置矩陣：構(gòu)建網(wǎng)絡(luò)拓?fù)洌捎谕負(fù)渲写嬖诮粨Q機(jī)，當(dāng)交換機(jī)的配置發(fā)生改變時(shí)，網(wǎng)絡(luò)拓?fù)湟舶l(fā)生改變；預(yù)置環(huán)是提前在網(wǎng)絡(luò)拓?fù)渲蓄A(yù)留一條環(huán)形鏈路，從J組環(huán)集中可以找到所在網(wǎng)絡(luò)拓?fù)渲凶畲蟮念A(yù)置環(huán)的數(shù)量為J；采用斥環(huán)法，從J組環(huán)集中找到J個(gè)預(yù)置環(huán)；給每個(gè)預(yù)置環(huán)分配合適帶寬，滿足鏈路的完全保護(hù)，并且最小化預(yù)置環(huán)的總代價(jià)，采用整數(shù)線性規(guī)劃可得到預(yù)置環(huán)；采用斥環(huán)法，尋求相應(yīng)合適的預(yù)置環(huán)，所有網(wǎng)絡(luò)拓?fù)涞念A(yù)置環(huán)形成一個(gè)集合稱為形成網(wǎng)絡(luò)規(guī)劃調(diào)度方案。

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

本發(fā)明涉及一種動(dòng)態(tài)鏈路保護(hù)方法，可在高性能計(jì)算支撐平臺(tái)下適用。

背景技術(shù)

在高性能計(jì)算平臺(tái)中，數(shù)據(jù)規(guī)模龐大，系統(tǒng)功耗高。采用光纖代替?zhèn)鹘y(tǒng)電纜是未來技術(shù)發(fā)展的主要方向。然而如果計(jì)算平臺(tái)中光纖鏈路故障，由于光纖傳輸效率極高，即使是極短的時(shí)間內(nèi)也會(huì)造成大量數(shù)據(jù)的丟失，所以在高性能計(jì)算平臺(tái)中設(shè)計(jì)一種在網(wǎng)絡(luò)鏈路發(fā)生故障時(shí)，快速高效找到替代路徑的保護(hù)措施是十分必要的。通過這種保護(hù)措施，使網(wǎng)絡(luò)具備一定的自我修復(fù)能力，可以減少故障所造成的經(jīng)濟(jì)損失及社會(huì)影響。

將高性能計(jì)算支撐平臺(tái)下的設(shè)備/服務(wù)器看作節(jié)點(diǎn)、鏈路看作邊，構(gòu)建一個(gè)網(wǎng)絡(luò)拓?fù)洹８咝阅苡?jì)算平臺(tái)中最適合的鏈路保護(hù)措施是預(yù)置環(huán)，利用空閑資源預(yù)先設(shè)定環(huán)形通道實(shí)現(xiàn)對(duì)高性能計(jì)算平臺(tái)中鏈路的快速保護(hù)。高性能平臺(tái)中存在TOR的布線方式，即每個(gè)服務(wù)器機(jī)柜的上端部署1-2臺(tái)兩臺(tái)接入交換機(jī)，由于交換機(jī)的配置是會(huì)更改的，每種配置對(duì)應(yīng)一種網(wǎng)絡(luò)拓?fù)洌绻麑?duì)每種拓?fù)涠碱A(yù)置環(huán)占用資源，那么會(huì)造成資源被過多占用的情況。因此需要考慮一種針對(duì)每個(gè)拓?fù)涠加袑?duì)應(yīng)的預(yù)置環(huán)，且在該預(yù)置環(huán)生效時(shí)，其他預(yù)置環(huán)所占用的資源都被釋放，這種動(dòng)態(tài)的調(diào)用使網(wǎng)絡(luò)利用率增高，傳輸更加靈活。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種動(dòng)態(tài)、高效的鏈路保護(hù)方案。通過配置矩陣、環(huán)定義、預(yù)置環(huán)、斥環(huán)法構(gòu)建約束，可以快速、高效的得出最合適當(dāng)前網(wǎng)絡(luò)拓?fù)涞囊慌A(yù)置環(huán)，從而對(duì)鏈路進(jìn)行動(dòng)態(tài)保護(hù)。本發(fā)明的目的通過以下技術(shù)方案實(shí)現(xiàn)：

一種動(dòng)態(tài)鏈路故障保護(hù)方法，包括以下步驟：

(1)交換機(jī)在工作中一定時(shí)間內(nèi)會(huì)積累一個(gè)N×N的流量矩陣C(T)，其最大總行數(shù)不超過T，即在一段時(shí)間內(nèi)交換機(jī)i入口到j(luò)出口所積累的流量對(duì)應(yīng)于流量矩陣中的c_ij；根據(jù)對(duì)流量矩陣進(jìn)行分解，分解成多個(gè)時(shí)隙以及相對(duì)應(yīng)的交換機(jī)重配置所形成的配置矩陣，設(shè)為取底符號(hào)，表示不超過x的整數(shù)中最大的一個(gè)，為取頂符號(hào)，表示不小于x的整數(shù)中最小的一個(gè)，通過下面的適應(yīng)算法重配置配置矩陣：

(a)計(jì)算重配置數(shù)量δ為重配置開銷，即對(duì)λN下取整，若令N_s＝N+1；

(b)構(gòu)建一個(gè)N×N的矩陣Q＝{q_ij}滿足

和

(c)從Q中構(gòu)造一個(gè)雙邊多重圖G_Q，Q的行和列轉(zhuǎn)換為G_Q中的左右兩個(gè)頂點(diǎn)A、B，每個(gè)入口q_ij∈Q轉(zhuǎn)變?yōu)閝_ij邊緣鏈接頂點(diǎn)i∈A和j∈A，找到G_Q的最小邊緣渲染，至少得到N_S-N個(gè)著色，這樣在同一個(gè)頂點(diǎn)上的邊事件有不同的著色，讓每個(gè)頂點(diǎn)都依次分別進(jìn)行著色；

(d)對(duì)于G_Q的邊緣著色中特定的著色，通過在P_n中設(shè)置相應(yīng)的入口為1，其他入口為0，來構(gòu)造來自于該著色邊緣的配置P_n；所以設(shè)置權(quán)重為重復(fù)(d)對(duì)于每一個(gè)G_Q中的邊緣著色構(gòu)造其對(duì)應(yīng)的配置；

(e)找到任何N個(gè)不重疊的配置P_n,n∈{N_s-N+1,...,N_s}，并為每個(gè)N配置設(shè)置相應(yīng)的權(quán)重能夠得到至少N_s個(gè)重配置和相應(yīng)的權(quán)重；