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

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

在計(jì)算機(jī)網(wǎng)絡(luò)中，數(shù)據(jù)鏈路層完成節(jié)點(diǎn)到節(jié)點(diǎn)的通信，二層以太網(wǎng)交換機(jī)屬于數(shù)據(jù)鏈路層設(shè)備［１］。ＭＡＣ（介質(zhì)訪問控制）地址是在網(wǎng)絡(luò)通信用來識(shí)別主機(jī)的標(biāo)識(shí)。交換機(jī)的緩存中有一個(gè)ＭＡＣ地址表，需要轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，交換機(jī)會(huì)在地址表查詢是否有與目的ＭＡＣ地址對(duì)應(yīng)的表項(xiàng)，如果有，交換機(jī)立即將數(shù)據(jù)報(bào)文往該表項(xiàng)中的轉(zhuǎn)發(fā)端口發(fā)送；如果沒有，交換機(jī)則會(huì)將數(shù)據(jù)報(bào)文以廣播的形式發(fā)送到除了接收端口外的所有端口，盡最大能力保證目的主機(jī)接收到數(shù)據(jù)報(bào)文。因此，交換機(jī)地址表的構(gòu)建和維護(hù)決定了數(shù)據(jù)轉(zhuǎn)發(fā)的方向和效率。ＭＡＣ層地址表存儲(chǔ)查找多基于ｈａｓｈ表。Ｈａｓｈｉｎｇ是一種用于以常熟平均時(shí)間插入、刪除和查找的技術(shù)，ｈａｓｈ表通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄。這個(gè)映射函數(shù)叫做ｈａｓｈｉｎｇ函數(shù)，存放記錄的數(shù)組叫做ｈａｓｈ表。交換機(jī)地址表存儲(chǔ)的是全部ＭＡＣ地址的一個(gè)子集因此必然會(huì)發(fā)生地址沖突，文獻(xiàn)［２－３］對(duì)比了幾種解決沖突的方法。ＭＡＣ地址表的容量是有限的，因此交換機(jī)采用老化機(jī)制來維護(hù)ＭＡＣ地址表，以保證最大限度地利用地址表項(xiàng)資源。交換機(jī)在構(gòu)建某條表項(xiàng)時(shí)，會(huì)相應(yīng)地開啟該表項(xiàng)的老化定時(shí)器［４］，如果在老化時(shí)間內(nèi)，交換機(jī)始終沒有收到該表項(xiàng)中的ＭＡＣ地址的報(bào)文，交換機(jī)就會(huì)將該表項(xiàng)刪除，失效的表項(xiàng)不會(huì)繼續(xù)占用ＭＡＣ地址表資源。這樣，即使網(wǎng)絡(luò)中的設(shè)備更換或者移除，交換機(jī)的ＭＡＣ地址表始終能保持網(wǎng)絡(luò)中最新的拓?fù)浣Y(jié)構(gòu)記錄。合適的老化時(shí)間可以提高ＭＡＣ地址表項(xiàng)資源的利用率，但過長或過短的老化時(shí)間，反而影響交換機(jī)的性能。如果老化時(shí)間過長，交換機(jī)中保存的ＭＡＣ地址表項(xiàng)的數(shù)量過多會(huì)將地址表資源消耗完，網(wǎng)絡(luò)中的拓?fù)渥兓蜔o法及時(shí)更新；如果老化時(shí)間過短，則有效的ＭＡＣ地址表項(xiàng)會(huì)被交換機(jī)過早刪除，從而降低交換機(jī)的轉(zhuǎn)發(fā)效率。傳統(tǒng)的ＭＡＣ地址表處理機(jī)制主要采用軟件的方式實(shí)現(xiàn)［５］。隨著以太網(wǎng)鏈路接口的速率從１Ｇｂ／ｓ發(fā)展到１０Ｇｂ／ｓ，基于軟件的算法在速度上受到串行計(jì)算機(jī)系統(tǒng)的制約。新一代現(xiàn)場可編程門陣列（ＦＰＧＡ）的出現(xiàn)以后，算法通過硬電路描述，所有的延遲只來源于門電路，而一般門電路的延遲都在ｎｓ級(jí)別。減少了系統(tǒng)運(yùn)行所需的時(shí)鐘周期數(shù)，實(shí)現(xiàn)了真正的高速率。１地址表處理機(jī)制

本數(shù)字電路設(shè)計(jì)中，采用單一時(shí)鐘域的同步時(shí)序設(shè)計(jì)，所有的觸發(fā)器都是在同一個(gè)時(shí)鐘節(jié)拍下進(jìn)行翻轉(zhuǎn)。這樣就簡化了整個(gè)設(shè)計(jì)，后端綜合、布局布線的時(shí)序約束容易實(shí)現(xiàn)。地址表占用的空間由片內(nèi)存儲(chǔ)器ＲＡＭ提供，片內(nèi)存儲(chǔ)器是基于ＦＰＧＡ的系統(tǒng)可使用的最簡單的存儲(chǔ)器，存儲(chǔ)、讀取是在ＦＰＧＡ內(nèi)部完成，電路板上無需外部連線，具有最高吞吐量和最低反應(yīng)延時(shí)的，適用于緩存和查找表。地址表表項(xiàng)中至少記錄ｍａｃ物理地址，端口號(hào)。每個(gè)ｍａｃ地址表項(xiàng)的數(shù)據(jù)結(jié)構(gòu)見表１。

定義如下：

Ｖａｌｉｄ：表項(xiàng)有效指示，１代表有效表項(xiàng)，０代表空閑表項(xiàng)。Ａｇｅ：老化比特，地址表更新時(shí)查詢的位段，１代表年輕，０代表老化。Ｍａｃａｄｄｒｅｓｓ：４８ｂｉｔ物理地址。Ｐｏｒｔ＿ｉｄ：物理地址對(duì)應(yīng)的端口號(hào)。地址表項(xiàng)寫入表中的位置即地址學(xué)習(xí)由源地址（ＭＡＣ地址）經(jīng)過ｈａｓｈｉｎｇ算法求得的索引值決定。地址表項(xiàng)的讀取即地址表查詢由目的地址（物理地址）經(jīng)過ｈａｓｈｉｎｇ算法求得的索引值決定。Ｈａｓｈｉｎｇ算法本身消耗一部分時(shí)序，物理地址的學(xué)習(xí)和查詢就需要等待這部分時(shí)序，為了使得地址表