[發明專利]一種動態鏈路故障保護方法

在審

• 申請號: 201810457415.X
• 申請日: 2018-05-14
• 公開（公告）號: CN108683579A
• 公開（公告）日: 2018-10-19
• 發明（設計）人: 盧薇至;吳斌;李伯宇
• 申請（專利權）人: 天津大學
• 主分類號: H04L12/437
• 分類號: H04L12/437;H04B10/032;H04B10/035;H04B10/275
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 程毓英

1.一種動態鏈路故障保護方法，包括以下步驟：

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

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

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

和

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

(d)對于G_Q的邊緣著色中特定的著色，通過在P_n中設置相應的入口為1，其他入口為0，來構造來自于該著色邊緣的配置P_n；所以設置權重為重復(d)對于每一個G_Q中的邊緣著色構造其對應的配置；

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

(2)以設備為節點、鏈路為邊構建網絡拓撲，由于拓撲中存在交換機，當交換機的配置發生改變時，網絡拓撲也發生改變；包含一個節點的環和完全不包含該節點的環組成一個環集，設網絡拓撲中存在J個節點，則形成J組環集；

(3)預置環是提前在網絡拓撲中預留一條環形鏈路，從J組環集中找到所在網絡拓撲中最大的預置環的數量為J；采用斥環法，從J組環集中找到J個預置環，其具體實現過程如下：

(a)將環上的分支定義為向量，環集CS_j中任意兩個節點間的鏈路(u，v)最多只有一個方向，采用u→v，定義節點u為頭，節點v為尾，以此類推；

(b)對于u→v的向量，給鏈路內經過的每個節點都臨時標上電壓值P，屬于第j個環集的節點v的電壓定義為節點u的電壓定義為斥環法中規定尾部電壓值高于頭部電壓值；

(c)一條邊的兩個節點都在環上，但這條邊不是組成環的邊，那么這條邊稱為跨接邊；同一環內兩個向量的尾節點相同，則這個尾節點稱為翻轉節點；同一環內兩個向量的頭節點相同，則這個頭結點稱為根節點；只有當同一個環中這兩者都存在時，環上所有向量的電壓值遵守尾高頭低的約束，否則環上可能會有電壓沖突；

(4)給每個預置環分配合適帶寬，滿足鏈路的完全保護，并且最小化預置環的總代價，采用整數線性規劃得到預置環；

(5)所有根據適應算法得到的配置矩陣，所生成的網絡拓撲都采用斥環法，尋求相應合適的預置環，所有網絡拓撲的預置環形成一個集合稱為形成網絡規劃調度方案；當采用一種拓撲結構時，根據其余拓撲形成的預置環所占用的資源在此時都將釋放；當某條鏈路損壞時，可根據預先制定的方式建立新的通路：

(a)當某條鏈接失效后，由于該鏈路一定在某個預置環中，直接切換到環的對側繼續進行傳輸；

(b)當某條在預置環中的跨接邊失效后，直接切換到該邊所分割的環的任意一側的鏈路進行傳輸。