為解決高速以太網鏈路接口中軟件方式實現的MAC層地址表機制在處理效率上受到制約的問題，提出了一種基于FPGA （現場可編程門陣列）硬件電路方式實現以太網交換機中MAC地址表的查找，學習和老化。該方法采用hashing算法建立地址表項索引值與MAC地址之間的對應關系，完成滿足平均時間復雜度為Ｏ （１）的地址查找。由于實際交換機中地址表容量有限，地址學習只能是MAC地址的子集，通過優化hashing函數降低地址沖突發生的概率以及設計一種地址老化機制提高地址表查找能力。仿真結果表明，地址表機制采用硬件電路方式實現比軟件方式處理效率更高。

引　言
在計算機網絡中，數據鏈路層完成節點到節點的通信，二層以太網交換機屬于數據鏈路層設備［１］。ＭＡＣ （介質訪問控制）地址是在網絡通信用來識別主機的標識。交換機的緩存中有一個ＭＡＣ地址表，需要轉發數據時，交換機會在地址表查詢是否有與目的ＭＡＣ地址對應的表項，如果有，交換機立即將數據報文往該表項中的轉發端口發送；如果沒有，交換機則會將數據報文以廣播的形式發送到除了接收端口外的所有端口，盡最大能力保證目的主機接收到數據報文。因此，交換機地址表的構建和維護決定了數據轉發的方向和效率。

ＭＡＣ層地址表存儲查找多基于ｈａｓｈ表。Ｈａｓｈｉｎｇ是一種用于以常熟平均時間插入、刪除和查找的技術，ｈａｓｈ表通過把關鍵碼值映射到表中一個位置來訪問記錄。這個映射函數叫做ｈａｓｈｉｎｇ函數，存放記錄的數組叫做ｈａｓｈ表。交換機地址表存儲的是全部ＭＡＣ地址的一個子集因此必然會發生地址沖突，文獻［２－３］對比了幾種解決沖突的方法。

ＭＡＣ地址表的容量是有限的，因此交換機采用老化機制來維護ＭＡＣ地址表，以保證最大限度地利用地址表項資源。交換機在構建某條表項時，會相應地開啟該表項的老化定時器［４］，如果在老化時間內，交換機始終沒有收到該表項中的ＭＡＣ地址的報文，交換機就會將該表項刪除，失效的表項不會繼續占用ＭＡＣ地址表資源。這樣，即使網絡中的設備更換或者移除，交換機的ＭＡＣ地址表始終能保持網絡中最新的拓撲結構記錄。合適的老化時間可以提高ＭＡＣ地址表項資源的利用率，但過長或過短的老化時間，反而影響交換機的性能。如果老化時間過長，交換機中保存的ＭＡＣ地址表項的數量過多會將地址表資源消耗完，網絡中的拓撲變化就無法及時更新；如果老化時間過短，則有效的ＭＡＣ地址表項會被交換機過早刪除，從而降低交換機的轉發效率。

傳統的ＭＡＣ地址表處理機制主要采用軟件的方式實現［５］。隨著以太網鏈路接口的速率從１Ｇｂ／ｓ發展到１０Ｇｂ／ｓ，基于軟件的算法在速度上受到串行計算機系統的制約。新一代現場可編程門陣列（ＦＰＧＡ）的出現以后，算法通過硬電路描述，所有的延遲只來源于門電路，而一般門電路的延遲都在ｎｓ級別。減少了系統運行所需的時鐘周期數，實現了真正的高速率。

１　地址表處理機制
本數字電路設計中，采用單一時鐘域的同步時序設計，所有的觸發器都是在同一個時鐘節拍下進行翻轉。這樣就簡化了整個設計，后端綜合、布局布線的時序約束容易實現。

地址表占用的空間由片內存儲器ＲＡＭ 提供，片內存儲器是基于ＦＰＧＡ的系統可使用的最簡單的存儲器，存儲、讀取是在ＦＰＧＡ內部完成，電路板上無需外部連線，具有最高吞吐量和最低反應延時的，適用于緩存和查找表。地址表表項中至少記錄ｍａｃ物理地址，端口號。每個ｍａｃ地址表項的數據結構見表１。

?

定義如下：
Ｖａｌｉｄ：表項有效指示，１代表有效表項，０代表空閑表項。

Ａｇｅ：老化比特，地址表更新時查詢的位段，１代表年輕，０代表老化。

Ｍａｃ　ａｄｄｒｅｓｓ：４８ｂｉｔ物理地址。

Ｐｏｒｔ＿ｉｄ：物理地址對應的端口號。

地址表項寫入表中的位置即地址學習由源地址（ＭＡＣ地址）經過ｈａｓｈｉｎｇ算法求得的索引值決定。地址表項的讀取即地址表查詢由目的地址（物理地址）經過ｈａｓｈｉｎｇ算法求得的索引值決定。Ｈａｓｈｉｎｇ算法本身消耗一部分時序，物理地址的學習和查詢就需要等待這部分時序，為了使得地址表處理起來更加清晰、明確，整個設計分為３個模塊（如圖１所示）：地址表的輸入調整、地址表處理機制、地址表的輸出調整。

?

模塊劃分后，本級模塊向下一級模塊一次性交付需要處理的所有并行數據。

１．１　地址表輸入調整（ｆｉｆｏ＿ｉｎ）
Ｆｉｆｏ＿ｉｎ模塊完成兩種操作，對輸入的ＭＡＣ地址求解ｈａｓｈｉｎｇ索引值（ｘｘ＿ｍａｃ＿ｉｎｄｅｘ）；間隔４ｓ產生地址表更新信號（ｕｐｄ＿ｅｎ），更新信號為高電平有效，持續時間由地址表的深度決定，遍歷地址表，一個時鐘周期處理一個表項。

Ｈａｓｈｉｎｇ算法：為了快速的存取地址表項，采用ｈａｓｈｉｎｇ算法［６］建立地址表項索引值與實際ＭＡＣ地址之間的對應關系（每個ＭＡＣ地址只能對應一個索引值，但是每個索引值有可能對應多個ＭＡＣ地址，即發生了地址沖突）。

使用復雜的ｈａｓｈｉｎｇ算法，會延長計算索引的時間，降低地址表的查找速度，增加交換機的包轉發時延。

在交換控制芯片設計中本項目算法使用ＣＲＣ－ＣＣＩＴＴＤ多項式 為ｈａｓｈｉｎｇ函數，４８位ＭＡＣ地址由ＣＲＣ［７－８］校驗方法后的結果通過ｈａｓｈｉｎｇ函數求得１６位余數，取結果１６位余數中１１個比特用于２ＫＢ地址表項索引值。Ｈａｓｈｉｎｇ函數計算的狀態機如圖２所示。

?

交換機ＭＡＣ層容納的地址表大小是有限的，理論上實際的物理地址有２的４８次方個，地址表只能記錄其中一個很小的子集，因此ｈａｓｈｉｎｇ函數不可避免地將不同的ＭＡＣ地址映射到相同的地址表項索引值。如果以太網中地址表項索引值與ＭＡＣ地址存在多對一的情況，就是發生了“地址沖突”。地址沖突的存在也說明總有部分ＭＡＣ地址丟失，不能被交換機學習到。地址沖突的解決方法在１．２中予以實現。

?

地址表組織結構如圖３。圖３左邊列出的是地址表ＲＡＭ 中每個ｈａｓｈｉｎｇ桶內表項０在ＲＡＭ 中的地址。在開始地址存儲和查找時，通過ＣＲＣ校驗得到的索引值指向的ｈａｓｈｉｎｇ桶內表項０與表項１被讀出，通過對ＭＡＣ地址域進行比較確定匹配的表項，得到轉發端口的信息。

１．２　地址表處理機制的實現方法（ＡｄｄｒＬｉｓｔ＿Ｐｒｏｃ）
１．２．１　地址學習和查找的實現

以太網幀結構中的源地址（ｓａ＿ｍａｃ）用于地址學習。目的地址（ｄａ＿ｍａｃ）用于地址查找。

對于較大吞吐量的交換芯片，能做到平均時間復雜度滿足線性的學習和查找。學習和查找采用ｈａｓｈｉｎｇ算法，發生碰撞采用ｈａｓｈｉｎｇ算法，碰撞后采用相鄰空間開放定址法（ｏｐｅｎ　ａｄｄｒｅｓｓｉｎｇ　ｈａｓｈｉｎｇ）［９－１０］。

學習的過程如下：
（１）根據ｈａｓｈｉｎｇ索引值ｓａ＿ｉｎｄｅｘ，檢索ＭＡＣ 地址表。

（２）表項中Ｖａｌｉｄ字段若為１代表該表項已占用，轉（３），否則表項空閑，轉（７）。

（３）表項內容中的ＭＡＣ地址與ｓａ＿ｍａｃ進行比較，若相同Ｉ＿Ｆｉｎｄ置１，轉（７），否則轉（４），此時發生地址沖突。

（４）ｓａ＿ｉｎｄｅｘ＋１表項中Ｖａｌｉｄ字段若為１代表此處表項已占用，轉（５），否則表項空閑轉（７）。

（５）表項內容中的ＭＡＣ地址與ｓａ＿ｍａｃ進行比較，若相同Ｉ＿Ｆｉｎｄ置１，轉（７），否則轉（６），此時發生地址沖突。

（６）此時有超過兩個不同的ＭＡＣ地址映射同一索引值，并且先到的寫入ｓａ＿ｉｎｄｅｘ和ｓａ＿ｉｎｄｅｘ＋１處。后面到達的ＭＡＣ地址覆蓋掉ｓａ＿ｉｎｄｅｘ處表項，完成一次學習。

（７）寫入該位置，Ｖａｌｉｄ置１，Ａｇｅ置１，完成一次學習。

查找的過程如下：
（１）判斷是不是廣播包，若是轉（１０），否則轉（２）。

（２）根據ｈａｓｈｉｎｇ索引值ｄａ＿ｉｎｄｅｘ，檢索ＭＡＣ 地址表。

（３）ｄａ＿ｉｎｄｅｘ和ｄａ＿ｉｎｄｅｘ＋１的Ｖａｌｉｄ字段組成二元組＜ｖａｌｉｄ０，ｖａｌｉｄ１＞，＜０，０＞轉（４）、＜０，１＞轉（５）、＜１，０＞轉（６）、＜１，１＞轉（７）。

（４）ｄａ＿ｍａｃ不在地址表中，轉（９）。

（５）ｄａ＿ｉｎｄｅｘ＋１表項內容中ＭＡＣ地址與ｄａ＿ｍａｃ比較，若兩者相同，轉（８），否則轉（９）。

（６）ｄａ＿ｉｎｄｅｘ表項內容中ＭＡＣ地址與ｄａ＿ｍａｃ比較，若兩者相同，轉（８），否則轉（９）。

（７）ｄａ＿ｍａｃ在地址表中轉（８），否則轉（９）。

（８）讀取表項內容中的端口號，與ｄａ＿ｍａｃ組成一組數據發給到ｆｉｆｏ＿ｏｕｔ，完成一次查找。

（９）廣播該ＭＡＣ地址，發送ｄａ＿ｍａｃ和需要廣播標志位給ｆｉｆｏ＿ｏｕｔ，完成一次查找。

（１０）Ｉ＿Ｆｉｎｄ標志位為１代表地址表中有廣播請求的ＭＡＣ地址，不需要繼續廣播下去。Ｉ＿Ｆｉｎｄ標志位為０代表需要繼續廣播下去，轉（１１）。

（１１）發送ｓａ＿ｍａｃ和需要廣播標志位給ｆｉｆｏ＿ｏｕｔ，完成一次查找。

１．２．２　地址老化的實現
交換機通過端口發送和接收幀的源地址（源ＭＡＣ地址、端口號）將存儲到地址表中。老化時間是一個影響交換機學習進程的參數。為地址表中每條地址項添加一個計數器用于表示該地址項的更新時間，通過查詢計數器位是否為零判斷一個地址是否已經老化。在更新過程中，所有的輸出引腳處于“懸掛”。

老化過程如下：
（１）檢測到更新信號ｕｐｄ＿ｅｎ為高電平時，開始遍歷整個地址表。

（２）表項中Ａｇｅ字段為１，代表上一次遍歷周期到此遍歷周期內該表項對應的ＭＡＣ 地址被重新寫入過，轉（３），否則（４）。

（３）表項中的Ｖａｌｉｄ字段保持１，Ａｇｅ字段置０。

（４）表項中的Ｖａｌｉｄ字段置０ （刪除已老化的）。

（５）等待ｕｐｄ＿ｅｎ為低電平時停止遍歷，完成一次地址老化。

３　地址表的輸出調整（ｆｉｆｏ＿ｏｕｔ）
Ｆｉｆｏ＿ｏｕｔ模塊根據前一級提供的各種標志信號，實現對輸出的控制。輸入的數據信號有源地址，目的地址，查找到的表項，輸入的標志信號有ｎｄ＿ｂｒ＿ｐａｃｋｅｔ （需要廣播標志），Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ（是廣播包標志）。

Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝１，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝０代表“是廣播包，不需要廣播”，對應地址表處理機制中的事件—接收到廣播包中的ＭＡＣ地址存在地址表中。沒有輸出。

Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝１，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝１代表“是廣播包，需要廣播”，對應地址表處理機制中的事件—繼續廣播下去。ｓａ＿ｍａｃ經過封裝由ｄｏｕｔ０～ｄｏｕｔ３輸出。

Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝０，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝０代表“不是廣播包，不需要廣播”，對應地址表處理機制中的事件—單播包中目的地址存在地址表中。表項經過封裝，對應端口輸出。

Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝０，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝１代表“不是廣播包，需要廣播”，對應地址表處理機制中的事件—目的地址不存在地址表中。ｄａ＿ｍａｃ經過封裝由ｄｏｕｔ０～ｄｏｕｔ３輸出。

２　不同ｈａｓｈｉｎｇ函數的沖突率
Ｈａｓｈｉｎｇ算法的主要原理就是把大范圍映射到小范圍，沖突率和ｈａｓｈｉｎｇ函數的選取有密切的關系，圖４中選取了４種不ｈａｓｈｉｎｇ函數下發生地址沖突的概率。情況一采用的Ｈａｓｈｉｎｇ函數為ＭＡＣ地址和自身倒序做異或運算所得的結果經過ＣＲＣ計算后取最后１１位索引值；情況二采用的Ｈａｓｈｉｎｇ函數為ＭＡＣ地址和自身倒序做異或運算所得的結果經過ＣＲＣ計算后取前１１位索引值；情況三采用的Ｈａｓｈｉｎｇ函數為ＭＡＣ地址平方后取中間１１位為索引值，情況四采用的Ｈａｓｈｉｎｇ函數為將ＭＡＣ地址分割成位數相同的３部分，疊加這三部分的和取后１１位為索引值。

仿真過程描述如下：
４８位二進制數表示的范圍劃分為三子段，每個子段隨機生成３０００個數。一共有９０００個隨機ＭＡＣ地址，依次按照４種情況提供的ｈａｓｈｉｎｇ函數計算結果，索引值一樣沖突加一，分別在不同的地址表容量下求沖突率。

不同ｈａｓｈｉｎｇ函數沖突率如圖４所示。

?

仿真結果表明地址表項容量和ＭＡＣ地址數量接近時基本不發生沖突，在地址表較小情況下對于本次實驗給出的信源情況三的ｈａｓｈｉｎｇ函數有較小的沖突率。所以在選取ｈａｓｈｉｎｇ函數時要結合該節點實際收發ＭＡＣ地址的概率模型，這樣才能有效的降低地址沖突發生。

３　設計與驗證
仿真過程中，時鐘周期１００ｎｓ，ＭＡＣ地址取４８ｂｉｔ中的后１６ｂｉｔ，地址表深度為６４，ｈａｓｈｉｎｇ算法采用ＣＲＣ８取結果的后６ｂｉｔ。這樣處理的理由有兩點：第一４８ｂｉｔ與１６ｂｉｔ原理相同，１６ｂｉｔ占用的資源少；第二ＭＡＣ地址前２４ｂｉｔ是由設備廠商分配的序列號，對于一部分ＭＡＣ地址只有后１６ｂｉｔ不同。

ｓａ＿ｍａｃ既是輸入也是輸出，ｆｉｆｏ＿ｉｎ內的寄存器保存一次輸入信號，待ｈａｓｈｉｎｇ算法后和索引值同步輸出，如圖５所示。

?

圖６的仿真結果中可以看到，１２００ｎｓ學習到ＭＡＣ地址（１６′ｈ７Ａ０Ｃ），１５００ｎｓ接收到對該ＭＡＣ地址的廣播包，停止繼續廣播下去。

?

圖７的仿真結果中可以看到２１００ｎｓ查詢的目的地址（１６’ｈＣ０Ａ７）存在于地址表中，它是２０００ｎｓ寫入地址表中的。

?

圖８中所示２６００ｎｓ開始地址更新，消耗６４個時鐘周期，遍歷所有的表項。９０００ｎｓ后的輸入和地址表更新前得輸入相同，可以看出有相同的輸出。

?

圖９所示不同的標志信號控制不同的輸出，可以看到１７００ｎｓ和１８００ｎｓ都是向端口２轉發數據。１４００ｎｓ向４個端口廣播。

?

４　結束語
對于以太網交換機來說，主要工作是根據收到數據幀中的目的ＭＡＣ地址，對ＭＡＣ地址表進行查找，把數據幀轉發到相應的端口。ＭＡＣ地址表的查表效率直接影響交換機的性能。Ｈａｓｈｉｎｇ算法可以實現高效率的存儲和查找，但存在地址沖突，選擇合適的ｈａｓｈｉｎｇ函數是解決問題的有效途徑之一。比如可以統計交換機各端口ｈａｓｈｉｎｇ索引值的概率分布，找出發生沖突較高的區域，對這些區域按照概率進行排序，ｈａｓｈｉｎｇ函數針對沖突域中概率大的幾個ＭＡＣ地址來構造。