[發明專利]一種基于層次化Q-routing規劃的路由方法

有效

• 申請號: 202110389260.2
• 申請日: 2021-04-12
• 公開（公告）號: CN113079093B
• 公開（公告）日: 2022-03-15
• 發明（設計）人: 李楨旻;翁曉峰;王鏡涵;李天瑜;馬宇晴;杜高明;宋宇鯤
• 申請（專利權）人: 合肥工業大學
• 主分類號: H04L45/12
• 分類號: H04L45/12;H04L41/12;H04L45/00;H04L45/24
• 代理公司: 安徽省合肥新安專利代理有限責任公司 34101
• 代理人: 陸麗莉;何梅生

1.一種基于層次化Q-routing規劃的路由方法，是應用于由w個路由器節點、w個資源節點和若干條互連通道所組成的片上網絡中，所述路由器節點包含輸入端口、輸出端口、擁塞感知器、多路選通器、訪問路由表；其特征是，在所述路由器節點中設置學習模塊；所述學習模塊包括：學習方式仲裁器、層次化控制模塊、路由表選擇模塊、3個子學習模塊、3個路由表；所述路由方法是按如下步驟進行：

步驟1：將所有路由器節點按照如下規則劃分三層網絡結構，從而形成金字塔結構；所述規則為：

在第1層網絡結構中將w個路由器節點以每x²個節點劃分為一組，從而構成由個虛擬路由器組所構成的第1層網絡結構；

在第2層網絡結構中將個虛擬路由器組以每y²個節點劃分為一組，從而構成由個虛擬路由器組所構成的第2層網絡結構；

在第3層網絡結構中將個虛擬路由器組以z²個節點劃分為一組，從而構成由1個虛擬路由器組所構成的第3層；

3個子學習模塊和3個路由表對應各個層的網絡結構；每個子學習模塊均包括：R矩陣、Q矩陣、Q值比較器；

令L₁^i,h表示第1層網絡結構中第i個路由器節點所對應的第h個子學習模塊，ix²，h＝1,2,3；

令L_jⁱ表示第j層網絡結構中第i個虛擬路由器組，j≠1；

令L₃ⁱ：L₂ⁱ表示第3層網絡結構的第i個虛擬路由器組中處于第2層網絡結構的第i個虛擬路由器組；

令L₃ⁱ：L₂ⁱ：L₁^i,h表示第3層網絡結構的第i個虛擬路由器組中處于第2層網絡結構中第i個虛擬路由器組內的第1層網絡結構中的第i個路由器節點所對應的第h個子學習模塊；

步驟2：各個路由器節點在各層網絡結構中進行擁塞程度感知與并行學習；

步驟2.1：以L₃ⁱ：L₂ⁱ：L₁^i,1作為當前路由器節點第1個子學習模塊；對于處于第1層網絡結構中當前路由器節點，通過自身的擁塞感知器對自身的輸入端口進行占用率計數，對自身的輸出端口進行流量計數，從而得出各條路徑上的第1層擁塞等級，并存入第1層網格結構中L₃ⁱ：L₂ⁱ：L₁^i,1所表示的第1個子學習模塊的R矩陣中；

對處于第2層網絡結構中L₃ⁱ：L₂ⁱ：L₁^i,2所表示的第2個子學習模塊，通過對第2層網絡結構中第i個虛擬路由器組內各節點的擁塞等級進行平均池化，得到池化后的擁塞等級并存入第2層網絡結構中L₃ⁱ：L₂ⁱ：L₁^i,2所表示的第2個子學習模塊的R矩陣中；

對處于第3層網絡結構中L₃ⁱ：L₂ⁱ：L₁^i,3所表示的第3個子學習模塊，通過對第3層網絡結構中第i個虛擬路由器組內各節點的擁塞等級進行平均池化，得到池化后的擁塞等級并存入最頂層網絡結構中L₃ⁱ：L₂ⁱ：L₁^i,3所表示的第3個子學習模塊的R矩陣中；

步驟2.2：初始化i＝0；

步驟2.3：將L₃ⁱ：L₂ⁱ：L₁^i,h，h＝1,2,3所表示的子學習模塊里的獎勵值均初始化為目的獎勵值；將其他的路由器節點中子學習模塊里的獎勵值均初始化為0；

步驟2.4：對處于第1層網絡結構中L₃ⁱ：L₂ⁱ：L₁^i,1所表示的第1個子學習模塊，讀取與其鄰接路由器節點上的子學習模塊的最大獎勵值，并根據L₃ⁱ：L₂ⁱ：L₁^i,1所表示的第1個子學習模塊中R矩陣，對所讀取的最大獎勵值進行加權處理，得到加權后的獎勵值，并選擇加權后的最大獎勵值傳給所有的鄰接路由器節點；

對處于第2層網絡結構中L₃ⁱ：L₂ⁱ：L₁^0,2所表示的第2個子學習模塊，讀取與L₃ⁱ：L₂ⁱ：L₁^0,2所表示的第2個子學習模塊相鄰的虛擬路由器組中處于同一位置上的第2個子學習模塊的最大獎勵值，并作為L₃ⁱ：L₂ⁱ所表示的第i個虛擬路由器組中所有節點的最大獎勵值；根據第L₃ⁱ：L₂ⁱ：L₁^0,2所表示的第2個子學習模塊中R矩陣，對所讀取的最大獎勵值進行加權處理，得到加權后的獎勵值，并選擇加權后的最大獎勵值傳給與L₃ⁱ：L₂ⁱ：L₁^0,2所表示的第2個子學習模塊相鄰的虛擬路由器組中處于同一位置上的第2個子學習模塊；

對處于第3層網絡結構中L₃ⁱ：L₂ⁱ：L₁^0,3所表示的第3個子學習模塊，讀取與L₃ⁱ：L₂ⁱ：L₁^0,3所表示的第3個子學習模塊相鄰的虛擬路由器組中處于同一位置上的第3個子學習模塊的最大獎勵值，并作為第3層網絡結構中第i個虛擬路由器組L₃ⁱ中所有節點的最大獎勵值；根據第3層網絡結構中L₃ⁱ：L₂ⁱ：L₁^0,3所表示的第3個子學習模塊中R矩陣，對所讀取的最大獎勵值進行加權處理，得到加權后的獎勵值，并選擇加權后的最大獎勵值傳給與L₃ⁱ：L₂ⁱ：L₁^0,3所表示的第3個子學習模塊相鄰的虛擬路由器組中處于同一位置上的第3個子學習模塊；

步驟2.5：當得到各個路由器節點的各個子學習模塊的下一跳的路徑信息后，每個路由器節點的各個子學習模塊的下一跳的路徑信息并行傳輸至所述層次化控制模塊中；

步驟3：在所述層次化控制模塊中對路徑信息進行修正，即：自高層網絡結構向低層網絡結構進行路徑信息糾正，再將糾正后的路徑信息從自低層網絡結構向高層網絡結構進行方向反傳輸，從而使得路由器節點的各個子學習模塊均得到糾正后的路徑信息，并將糾正后的路徑信息存入至對應層網絡結構的路由表中；

步驟4：將i+1賦值給i后返回步驟2.3，直到i＝max-1為止，從而完成每個路由器節點作為目的節點的路徑規劃，其中max表示每層網絡結構中最大的虛擬路由器組內路由器節點數量；

步驟5：片上網絡數據包的傳輸：

片上網絡中的數據包通過訪問各個層網絡結構中的路由表，依次經過輸入端口和多路選通器，在多路選通器對學習模塊中的路由表選擇模塊進行訪問操作；

所述路由表選擇模塊讀取數據包中的目的路由器節點的位置信息，并按訪問規則訪問路由表并取出路由表中存儲的路徑信息：

根據路由表中所取出的路徑信息，如果所取出的路徑信息為返回信息，則目的路由器節點將數據包傳送到自身的收包器中，否則根據取出的路徑信息送入對應的輸出端口，從而完成數據包的傳輸。