基于FPGA的MAC層地址表設(shè)計與仿真詳情解析

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

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

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

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

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

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

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

?

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

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

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

Ｐｏｒｔ＿ｉｄ：物理地址對應(yīng)的端口號。

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

?

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