[發明專利]基于硬件實現的快速路由更新電路結構及更新方法

有效

• 申請號: 202011008034.7
• 申請日: 2020-09-23
• 公開（公告）號: CN112134805B
• 公開（公告）日: 2022-07-08
• 發明（設計）人: 王乾;喬廬峰;陳慶華
• 申請（專利權）人: 中國人民解放軍陸軍工程大學
• 主分類號: H04L45/02
• 分類號: H04L45/02;H04L45/745;G06F12/02
• 代理公司: 北京力量專利代理事務所(特殊普通合伙) 11504
• 代理人: 毛雨田

本發明公開了一種基于硬件實現的快速路由更新電路結構及實現方法，該電路中的鏈表管理模塊用于記錄將trie分層后得到的子trie的具體結構，可對trie執行節點添加和刪除操作，更新完成后將涉及操作的前綴送到結構轉換模塊；頭指針管理模塊管理鏈表的頭指針，用于執行鏈表管理模塊發出的添加和刪除操作；共享存儲區管理模塊用于管理共享RAM的可用空地址，執行鏈表管理模塊發出的讀出，寫入操作；結構轉換模塊用于將鏈表轉換為查找設備使用的轉發表。本電路可以代替處理器實現路由更新和維護功能，并可實現路由表項的快速添加和快速刪除。

技術領域

本發明涉及電子電路技術領域，特別是一種基于硬件實現的快速路由更新電路結構。

背景技術

目前路由查找算法方案主要分為兩種，一種為基于軟件的方案另一種為基于硬件的方案。基于軟件的方案通常不依賴于特定的硬件因此靈活性較高方便移植到不同平臺上。大多數基于軟件的方法都集中在減少內存需求和減少內存訪問次數上。基于硬件的方案則利用專用硬件（包括TCAM，網絡處理器，FPGA和GPU）來實現更好的性能。

為發揮專用硬件高速并行的優勢，基于硬件的方案常通過使用可控前綴擴展技術限制前綴長度的數量，以此形成支持并行查找的轉發數據結構。例如DIR24-8，該方案通過前綴擴展將前綴長度限制為24和32，以此達到單次查找最高2次內存訪問的目的。雖然基于專用硬件的方案可以達到上百G的吞吐率，但是這些方案需要CPU協助維護基于trie樹的數據結構，用于將所有路由前綴更新和擴展為存儲在硬件中的轉發數據結構然而是trie樹結構復雜在trie樹中進行插入和刪除操作需要占用大量時鐘周期，隨著路由更新頻率的不斷提高路由更新給CPU造成較大負荷。

發明內容

本發明的目的在于提供一種可以提高路由更新速度，降低路由更新對CPU時鐘周期占用的基于硬件實現的快速路由更新電路結構。

實現本發明的技術解決方案為：一種基于硬件實現的快速路由更新電路結構，包括鏈表管理模塊、頭指針管理模塊、共享存儲區管理模塊、結構轉換模塊；

所述鏈表管理模塊用于管理轉換為鏈表結構的trie樹，記錄trie樹中子trie的具體結構，對trie樹執行節點插入和刪除操作，更新完成后將涉及操作的前綴及前綴攜帶的信息寫入prefix_FIFO；

所述頭指針管理模塊用于管理鏈表結構中的鏈表頭指針，執行鏈表管理模塊發出的查找、插入和刪除操作；

所述共享存儲區管理模塊用于管理共享存儲區中的可用空地址，執行鏈表管理模塊發出的獲得空地址、回寫空地址操作；

所述結構轉換模塊用于將鏈表轉換為查找設備使用的轉發表。

上述鏈表管理模塊包括插入操作子模塊、刪除操作子模塊、prefix_FIFO；

所述插入操作子模塊用于響應路由更新系統的插入命令，并將涉及的前綴條目插入到鏈表結構中；

所述刪除操作子模塊用于響應路由更新系統的刪除命令，并將涉及的前綴條目在鏈表結構中刪除；

所述prefix_FIFO緩存了結構轉換模塊需要的涉及操作的前綴的信息。

優選的是，本發明的頭指針管理模塊包括head_ptr_reg和head_ptr_RAM_2~head_ptr_RAM_n,其中n的數值由trie樹被切分的層數決定；

所述head_ptr_reg為寄存器，用于存儲第1層鏈表的頭指針；

所述head_ptr_RAM_2~head_ptr_RAM_n用于存儲第2~第n層鏈表的頭指針。

優選的是，本發明的共享存儲區管理模塊包括shared_RAM和free_addr_FIFO；

所述shared_RAM用于存儲所有鏈表的節點；