基於fpga的快速地址查找算法的製作方法

2023-06-05 15:42:46 3

專利名稱：基於fpga的快速地址查找算法的製作方法
技術領域：
本發明涉及區域網、廣域網等乙太網技術領域，可以內嵌在任何乙太網交換網或傳輸系統中，適用於點到點、點到多點連結來傳送多協議數據報文的通信方式，也涉及其它數據格式完成源端到目的端建立信息交換的應用模式。
背景技術：
乙太網技術是當今現有區域網最通用的通信協議標準，以IP為代表的數據業務的迅速發展，都給網絡傳輸提出了更高的容量和功能要求，為了減少數據交換和查找錶帶來的延遲，必須建立有效而且快速的地址查找算法。FLA算法採用動態存儲結構，將任意長度的二進位值映射為固定長度的較小二進位值，這個小的二進位值稱為關鍵字，關鍵字是一段數據唯一且極其緊湊的數值表示形式。 如果輸入數據中有變化，則關鍵字也會發生變化。而且把數據的存儲和查找消耗的時間大大降低，幾乎可以看成是常數時間，代價僅僅是消耗比較多的存儲空間，然而在當前可利用內存越來越多的情況下，用空間換時間的做法是值得的。另外，編碼比較容易也是它的特點之一。因此作為線性數據結構，與逐條的比較算法相比，FLA算法無疑是查找速度比較快、 經濟實用的一種算法。但按照關鍵字為每一個輸入值〃分類〃，然後將這個元素存儲在相應〃類〃所對應的地方，因此不能保證每個關鍵字與輸入值是一一對應的，極有可能出現對於不同的輸入值，卻計算出了相同的關鍵字，這樣就產生了"衝突"。可以採用重新FLA算法來解決該問題，簡單的說就是每次產生碰撞，都會根據關鍵字用另一個FLA函數重新算一個關鍵字， 直到探尋到一個不衝突的關鍵字。

發明內容
根據設定的FLA函數(使用好的函數公式，在輸入數據中所做的更改就可以更改結果關鍵字中的所有位)和處理衝突方法將網絡地址映射到一個有限的地址區間上，並以關鍵字為地址區間中的偏移地址，作為記錄在表中的存儲位置。本算法基於FPGA的硬體邏輯開發，不需要其它外部軟體或處理器的幹預，程序加載後自動完成地址的學習/查找過程，可以支持單播、組播、廣播多種通信方式。本發明的技術方案如下模塊組件包括1.地址表，用來存儲地址信息及接收數據的埠號；2.地址學習模塊，學習IP數據流中源地址信息，通過計算得到源地址的關鍵字， 並把地址信息寫入地址表中；3.地址查找模塊，查找IP數據流中目的地址，得到目的地址的關鍵字(也就是對應其它IP數據流中源地址信息)，查找地址表，由此知道IP數據流的輸出埠 ；4.地址老化模塊，可由外置的處理器模塊來配置老化的參數(使能、老化時間等級、老化時間周期等)和靜態地址。5.配置接口，提供標準的通信總線，連接外置的處理器晶片。注1 為了滿足其它的乙太網通信協議，地址表中可以增加其它信息來實現，如增加VLANID實現虛擬區域網技術。注2 地址表的空間大小由FPGA晶片內嵌或外擴的RAM來決定。注3 靜態地址不受老化時間的影響。任何一個埠的接收到IP數據流通過FLA算法，對新發現的地址信息加入到地址表中，最終形成整個交換網或傳輸系統的地址表項，一旦源埠需發送數據，可以快速從地址表中查找到目的地址信息和輸出埠，再由交換網或傳輸系統建立源埠到目的埠的傳送路徑，完成數據的可靠傳輸。為了節省地址空間，實現地址表的重複利用，開啟地址老化模塊，刪除地址表中超時不再使用的地址信息。


圖1所示為FLA算法在系統中的模型圖
具體實施例方式下面根據附圖和實例對本發明做進一步詳細說明實例系統簡化模型如圖1所示，以二個埠間單播數據為例，主機A(連接埠 1，IP 地址 192. 168. 1. 1, MAC 地址 00-aa-00-62-c6_01)向主機 B (埠 2，IP 地址 192. 168. 1. 2，MAC 地址 00-aa-00-62-c6_02)發送數據。1.當發送數據時，主機A會在自己的ARP緩存表中尋找是否有目標IP位址。如果找到了，也就知道了目標MAC地址，直接把目標MAC地址寫入幀裡面發送就可以了 ；如果在ARP緩存表中沒有找到目標IP位址，主機A就會在網絡上發送一個廣播，A主機MAC 地址是「主機A的MAC地址」，這表示向同一網段內的所有主機發出這樣的詢問「我是 192. 168. 1. 1，我的硬體地址是〃主機A的MAC地址〃.請問IP位址為192. 168. 1. 2的MAC 地址是什麼？ 」，這時FLA算法就從埠 1學到了 00-aa-00-62-c6-01，寫入地址表中。2.網絡上其他主機並不響應ARP詢問，只有主機B接收到這個幀時，才向主機A 做出這樣的回應"192. 168. 1. 2的MAC地址是00-aa-00-62-c6-02，，，從埠 2同樣學到了 00-aa-00-62-c6-02,寫入地址表中。3.主機A知道了主機B的MAC地址，而且地址表中也存儲了二條地址信息，主機A 向主機B發送數據時，交換網或傳輸系統立即查到了主機A的輸入埠 1，發送到主機B輸出埠 2，建立硬體邏輯通路，主機B就接收到了主機A的數據。以上所述，僅為本發明典型的具體實施方式
，但本發明的保護範圍並不局限於此， 任何熟悉該技術的人在本發明所揭露的技術範圍內，可輕易想到的變化或替換，都應涵蓋在本發明的保護範圍之內。
權利要求
1.基於FPGA的快速地址查找算法，包括地址表、地址老化模塊、地址學習模塊、地址查找模塊和配置接口。本發明涉及的系統，其特徵是算法由FPGA邏輯程序自動完成，不需要其它外部軟體或處理器的幹預。
2.根據權利要求1所述的算法，其特徵在於，作為地址提取和查找模塊，地址信息的多少不影響地址查找的時間，可以認為是恆定的時間周期內。
3.根據權利要求1所述的算法，其特徵在於，作為快速查找算法，運算過程不影響數據流的信號，不會產生數據交換的時延。
全文摘要
本發明旨在提供一種基於FPGA的快速地址查找算法，可以內嵌在任何乙太網交換網或傳輸系統中，適用於點到點、點到多點連結來傳送多協議數據報文的通信方式，適用於區域網、廣域網等乙太網技術領域。算法基於FPGA硬體平臺，包括地址表、地址老化模塊、地址學習模塊、地址查找模塊和配置接口。採用動態存儲結構，將任意長度的二進位值映射為固定長度的較小關鍵字，並以關鍵字為地址區間中的偏移地址，作為記錄在表中的存儲位置。算法不需要其它外部軟體或處理器的幹預，程序加載後自動完成地址的學習/查找過程，可以支持單播、組播、廣播多種通信方式。
文檔編號H04L29/12GK102299971SQ20101021161
公開日2011年12月28日 申請日期2010年6月25日 優先權日2010年6月25日
發明者高勝 申請人:深圳市邦彥信息技術有限公司