[發明專利]一種跨域標簽交換路徑域間失效的恢復方法

無效

• 申請號: 201010567002.0
• 申請日: 2010-12-01
• 公開（公告）號: CN102065006A
• 公開（公告）日: 2011-05-18
• 發明（設計）人: 彭云峰;隆克平;王引
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 溫利平

1.一種跨域標簽交換路徑域間失效的恢復方法，其特征在于，包括以下步驟：

(1)、對于一條依次跨越域D(1)，D(2)，......D(N)的跨域標簽交換路徑，其源節點和目的節點分別在域D(1)和域D(N)，跨域標簽交換路徑在域D(i)內經過的節點失效，且無法用域內恢復方式恢復，形成域間失效跨域標簽交換路徑；用BNen(i)和BNex(i)分別代表域間失效跨域標簽交換路徑在域D(i)內經過的路徑入口邊界節點和路徑出口邊界節點，其中1≤i≤N；

(2)、域D(i)的路徑計算單元PCE(i)計算域D(i)的虛擬恢復路徑樹VRPT(i)；

若域D(i)的虛擬恢復路徑樹VRPT(i)計算失敗，則路徑計算單元PCE(i)向域D(i+1)的路徑計算單元PCE(i+1)正向發送LSP跨域恢復請求消息，LSP跨域恢復請求消息中包含域D(i)的路徑出口邊界節點BNex(i)，進入步驟(3)；

若虛擬恢復路徑樹VRPT(i)計算成功，路徑計算單元PCE(i)反向發送LSP跨域恢復請求消息到域D(i-1)的路徑計算單元PCE(i-1)，LSP跨域恢復請求消息中包含域D(i)的虛擬恢復路徑樹VRPT(i)，進入步驟(6)；

其中，虛擬恢復路徑樹VRPT(i)的計算為：

路徑計算單元PCE(i)首先在域D(i)拓撲中排除失效節點，然后在新拓撲中使用最短路徑算法，分別計算域D(i)所有入口邊界節點到路徑出口邊界節點BNex(i)，若在域D(N)，此節點為跨域標簽交換路徑的目的節點的最短路徑；

虛擬恢復路徑樹VRPT(i)的根節點為域D(i)的路徑出口邊界節點BNex(i)，葉節點為域D(i)的入口邊界節點；

虛擬恢復路徑樹VRPT(i)計算失敗是指在域D(i)內沒有入口邊界節點到路徑出口邊界節點BNex(i)，若在域D(N)，此節點為跨域標簽交換路徑的目的節點的最短路徑；虛擬恢復路徑樹VRPT(i)計算成功是指域D(i)內至少有一入口邊界節點到路徑出口邊界節點BNex(i)，若在域D(N)，此節點為跨域標簽交換路徑的目的節點的最短路徑；

(3)、域D(i+1)的路徑計算單元PCE(i+1)接收到域D(i)的路徑計算單元PCE(i)發送來的LSP跨域恢復請求消息后，路徑計算單元PCE(i+1)排除域D(i+1)中與路徑出口邊界節點BNex(i)相連接的路徑入口邊界節點BNen(i+1)后，計算域D(i+1)的所有入口邊界節點到域D(i+1)的路徑出口邊界節點BNex(i+1)，若在域D(N)，此節點為跨域標簽交換路徑的目的節點的最短路徑，并把這些路徑組成域D(i+1)的虛擬恢復路徑樹VRPT(i+1)；若域D(i+1)內至少有一入口邊界節點到路徑出口邊界節點BNex(i+1)，在域D(N)，此節點為跨域標簽交換路徑的目的節點的最短路徑，則計算成功，進入步驟(4)；否則計算失敗，向域D(i+2)的路徑計算單元PCE(i+2)發送LSP跨域恢復請求消息，LSP跨域恢復請求消息中包含域D(i+1)的路徑出口邊界節點BNex(i+1)，計算失敗為：域D(i+1)內沒有入口邊界節點到域D(i+1)的路徑出口邊界節點BNex(i+1)的路徑；

域D(i+2)的路徑計算單元PCE(i+2)收到LSP跨域恢復請求消息后，路徑計算單元PCE(i+2)排除域D(i+2)中與路徑出口邊界節點BNex(i+1)相連接的路徑入口邊界節點BNen(i+2)后，計算域D(i+2)的所有入口邊界節點到域D(i+2)的路徑出口邊界節點BNex(i+2)，若在域D(N)，此節點為跨域標簽交換路徑的目的節點的最短路徑，并把這些路徑組成域D(i+2)的虛擬恢復路徑樹VRPT(i+2)；若域D(i+2)內至少有一入口邊界節點到路徑出口邊界節點BNex(i+1)，在域D(N)，此節點為跨域標簽交換路徑的目的節點的最短路徑，則計算成功，進入步驟(4)；否則計算失敗，向域D(i+3)的路徑計算單元PCE(i+3)發送LSP跨域恢復請求消息，LSP跨域恢復請求消息中包含域D(i+2)的路徑出口邊界節點BNex(i+1)，計算失敗為：域D(i+2)內沒有入口邊界節點到域D(i+2)的路徑出口邊界節點BNex(i+1)的路徑；

如此遞歸，若到域D(N)時，在各域中，虛擬恢復路徑樹依然未計算成功，則跨域標簽交換路徑域間失效恢復失敗；

(4)、如果虛擬恢復路徑樹在域D(j)中計算成功，記為VRPT(j)，其中，i＜j＜＝N，路徑計算單元PCE(j)反向發送LSP跨域恢復響應消息到域D(j-1)的路徑計算單元PCE(j-1)，此LSP跨域恢復響應消息中包含虛擬恢復路徑樹VRPT(j)，虛擬恢復路徑樹VRPT(j)的根節點為域D(j)的路徑出口邊界節點BNex(j)，葉節點為域D(j)的入口邊界節點；

(5)、路徑計算單元PCE(j-1)接收到LSP跨域恢復響應消息后，組合域D(j-1)拓撲和虛擬恢復路徑樹VRPT(j)，重新計算域D(j-1)的虛擬恢復路徑樹VRPT(j-1)：域D(j-1)的所有入口邊界節點到域D(j)的虛擬恢復路徑樹VRPT(j)的根節點，即路徑出口邊界節點BNex(j)的最短路徑，虛擬恢復路徑樹VRPT(j-1)的根節點為域D(j)的路徑出口邊界節點BNex(j)，葉節點為域D(j-1)的入口邊界節點；

若虛擬恢復路徑樹VRPT(j-1)計算失敗，域D(j-1)中沒有入口邊界節點到域D(j)虛擬恢復路徑樹的根節點，即路徑出口邊界節點BNex(j)的路徑，則跨域標簽交換路徑域間失效恢復失敗；否則，路徑計算單元PCE(j-1)反向發送LSP跨域恢復響應消息到路徑計算單元PCE(j-2)；

路徑計算單元PCE(j-2)接收到LSP跨域恢復響應消息后，組合域D(j-2)拓撲和虛擬恢復路徑樹VRPT(j-1)，重新計算域D(j-2)的虛擬恢復路徑樹VRPT(j-2)：域D(j-2)的所有入口邊界節點到域D(j-1)的虛擬恢復路徑樹VRPT(j-1)的根節點，即路徑出口邊界節點BNex(j)的最短路徑，虛擬恢復路徑樹VRPT(j-2)的根節點為域D(j)的路徑出口邊界節點BNex(j)，葉節點為域D(j-2)的入口邊界節點；如此遞歸，直到LSP跨域恢復響應消息到達失效域D(i)中；

失效域D(i)的路徑計算單元PCE(i)組合域D(i)拓撲和域D(i+1)的虛擬恢復路徑樹VRPT(i+1)，并在組合拓撲中計算出虛擬恢復路徑樹VRPT(i)：域D(i)的所有入口邊界節點到域D(i+1)的虛擬恢復路徑樹VRPT(i+1)的根節點，即路徑出口邊界節點BNex(j)的最短路徑，若虛擬恢復路徑樹VRPT(i)計算失敗，域D(i)中沒有入口邊界節點到域D(i+1)的虛擬恢復路徑樹VRPT(i+1)的根節點，即出口邊界節點BNex(j)的路徑，則跨域標簽交換路徑域間失效恢復失敗；否則路徑計算單元PCE(i)反向發送LSP跨域恢復請求消息到PCE(i-1)，此LSP跨域恢復請求消息中包含虛擬恢復路徑樹VRPT(i)，其根節點為域D(j)的路徑出口邊界節點BNex(j)，葉節點為域D(i)的入口邊界節點；

(6)、域D(i-1)的路徑計算單元PCE(i-1)收到LSP跨域恢復請求消息后，路徑計算單元PCE(i-1)組合域D(i-1)拓撲和虛擬恢復路徑樹VRPT(i)，路徑計算單元PCE(i-1)在組合拓撲中計算域D(i-1)的路徑入口邊界節點BNen(i-1)，如果在D(1)中，此節點為源節點，至與虛擬恢復路徑樹VRPT(i)根節點的最短路徑，若計算成功，則此最短路徑即為恢復跨域標簽交換路徑，恢復成功；否則：路徑計算單元PCE(i-1)計算域D(i-1)中所有入口邊界點到虛擬恢復路徑樹VRPT(i)根節點的最短路徑，作為域D(i-1)的虛擬恢復路徑樹VRPT(i-1)，若域D(i-1)中沒有入口邊界點到虛擬恢復路徑樹VRPT(i)根節點的路徑，計算失敗，則跨域標簽交換路徑域間失效恢復失敗；否則，路徑計算單元PCE(i-1)向域D(i-2)的路徑計算單元PCE(i-2)反向發送LSP跨域恢復請求消息，LSP跨域恢復請求消息包含虛擬恢復路徑樹VRPT(i-1)，虛擬恢復路徑樹VRPT(i-1)的根節點為域D(i)虛擬恢復路徑樹VRPT(i)的根節點，葉節點為域D(i-1)的入口邊界節點；

域D(i-2)的路徑計算單元PCE(i-2)收到LSP跨域恢復請求消息后，路徑計算單元PCE(i-2)組合域D(i-2)拓撲和虛擬恢復路徑樹VRPT(i-1)，路徑計算單元PCE(i-2)在組合拓撲中計算域D(i-2)的路徑入口邊界節點BNen(i-2)，如果在D(1)中，此節點為源節點，至與虛擬恢復路徑樹VRPT(i)根節點的最短路徑，若計算成功，則此最短路徑即為恢復跨域標簽交換路徑，恢復成功；否則：路徑計算單元PCE(i-2)計算域D(i-2)中所有入口邊界點到虛擬恢復路徑樹VRPT(i-1)根節點的最短路徑，作為域D(i-2)的虛擬恢復路徑樹VRPT(i-2)，若域D(i-2)中沒有入口邊界點到虛擬恢復路徑樹VRPT(i-1)根節點的路徑，計算失敗，則跨域標簽交換路徑域間失效恢復失敗；否則，路徑計算單元PCE(i-2)向域D(i-3)的路徑計算單元PCE(i-3)反向發送LSP跨域恢復請求消息，LSP跨域恢復請求消息包含虛擬恢復路徑樹VRPT(i-2)，虛擬恢復路徑樹VRPT(i-2)的根節點為域D(i)虛擬恢復路徑樹VRPT(i)的根節點，葉節點為域D(i-2)的入口邊界節點；

如此遞歸，若到域D(1)時，在各域中，虛擬恢復路徑樹依然未計算成功，則跨域標簽交換路徑域間失效恢復失敗。