[發明專利]層次化確定網絡中的多約束雙路徑路由方法

有效

• 申請號: 201810293525.7
• 申請日: 2018-04-04
• 公開（公告）號: CN108494601B
• 公開（公告）日: 2020-02-21
• 發明（設計）人: 盛立杰;秦丹
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/721
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

本發明公開一種層次化確定網絡中的多約束雙路徑路由方法，實現步驟是，將確定網絡劃分為幾個父網絡，每個父網絡由不同數量的子網絡組成，在獲取網絡拓撲圖中各條鏈路的服務質量參數和可靠性數值的情況下，基于啟發式多約束最優路徑算法的反向線性標記法和正向標記法，對網絡拓撲圖進行父網絡、子網絡和節點這三種簡化，獲得滿足多個約束要求的兩條路徑。本發明的優點是，獲得的多約束雙路徑不存在重復鏈路，保證了在第一條路徑發生故障的情況下，第二條路徑依然可以進行數據通信，同時本發明具有時間復雜度可確定性，且時間復雜度滿足工業化設計要求，可用于部署實際的大型互聯網絡。

技術領域

本發明屬于通信技術領域，更進一步涉及網絡通信技術領域中的一種層次化確定網絡DetNet(Deterministic Network)中的多約束雙路徑路由方法。本發明可用于在確定網絡中接受多約束參數的路由查找，得出滿足多個約束要求的兩條路徑，為確定網絡提供保證服務質量QoS(Quality of Service)的路由服務，有效提升網絡的復雜路由查找性能。

背景技術

服務質量QoS(Quality of Service)路由是一種基于網絡的可用資源和業務流的QoS要求來選擇路徑的路由機制，即包含多個QoS參數的動態多約束路由協議。確定網絡作為一種新興的網絡，為人們提供了多種網絡服務，不同的網絡服務有不同的參數約束，而單一的傳統網絡路由協議無法滿足不同服務對不同約束參數的需求，且現有的QoS路由機制無法直接應用于確定網絡，如何在確定網絡中提供滿足多約束的QoS路由成為一個重要的技術問題。

確定網絡可以為具有極低數據丟失率和有界延遲的實時應用傳送指定的單播或多播數據流。確定網絡中提供了擁塞保護CP(Congestion Protection)、顯式路由ER(Explicit Routes)和服務保護SP(Service Protection)三種機制來達到此效果。擁塞保護通過沿著確定數據流DF(DetNet Flow)的路徑預留資源來操作，例如緩存空間或鏈路帶寬。擁塞保護大大減少甚至完全消除由于網絡內的的輸出數據包擁塞而導致的數據包丟失問題，但它僅僅給在源端被限制到最大數據包大小和傳輸速率的確定數據流提供服務。服務保護主要包括數據包的復制和消除。其中，通過數據包的復制使得確定數據流在不同的路徑中得以傳輸，這是一種創新的實現思想。

此機制通過在多條路徑傳輸確定數據流，使得一些路徑的丟失不會造成任何數據包的丟失。首先在源端提供確定復合流DCF(DetNet Compound Flow)分組的排序信息,這可以通過添加序列號或時間戳作為確定數據流的一部分來完成，或者可以是分組的固有屬性，比如分組被接收的精確時間。然后，將這些分組復制到多個確定成員流DMF(DetNetMember Flow)中，并且沿著至少兩條不同的路徑將它們發送到目的端，從而保證了在一條路徑的某些鏈路發生故障的情況下，其他路徑的數據可以正常傳輸，這樣就大大提高了傳輸數據的可靠性，同時很大程度上降低了數據丟失率。最后消除重復分組。此操作可以在路徑的任何一個階段進行以節省網絡資源。通常情況下，在確定網絡的邊緣執行此操作，在終端基于序列號對分組進行丟失檢測和重新排序。

其中，在實現數據包復制方面，我們可以通過在確定網絡中尋找滿足多約束參數的兩條路徑來實現。為了使尋找的兩條路徑的可靠性達到最高，我們可以把確定網絡進行網絡規模的分層，比如父網絡和子網絡兩層，然后在網絡中尋找滿足多約束要求的兩條路徑，這樣做的目的，主要是為了使獲得的兩條路徑“相距的距離盡可能的遠”，也就是說，使兩條路徑不但沒有重復鏈路而且所處的網絡層次也盡可能不同，這樣的話，一旦一條路徑的某些鏈路發生故障，不會影響第二條路徑的數據傳輸，這樣就大大提高了傳輸數據的可靠性，同時大大降低了數據丟失率。