電子發(fā)燒友App
為解決高速以太網(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ù)。
１．１ 地址表輸入調(diào)整（ｆｉｆｏ＿ｉｎ）
Ｆｉｆｏ＿ｉｎ模塊完成兩種操作，對輸入的ＭＡＣ地址求解ｈａｓｈｉｎｇ索引值（ｘｘ＿ｍａｃ＿ｉｎｄｅｘ）；間隔４ｓ產(chǎn)生地址表更新信號（ｕｐｄ＿ｅｎ），更新信號為高電平有效，持續(xù)時間由地址表的深度決定，遍歷地址表，一個時鐘周期處理一個表項。
Ｈａｓｈｉｎｇ算法：為了快速的存取地址表項，采用ｈａｓｈｉｎｇ算法［６］建立地址表項索引值與實際ＭＡＣ地址之間的對應(yīng)關(guān)系（每個ＭＡＣ地址只能對應(yīng)一個索引值，但是每個索引值有可能對應(yīng)多個ＭＡＣ地址，即發(fā)生了地址沖突）。
使用復(fù)雜的ｈａｓｈｉｎｇ算法，會延長計算索引的時間，降低地址表的查找速度，增加交換機的包轉(zhuǎn)發(fā)時延。
在交換控制芯片設(shè)計中本項目算法使用ＣＲＣ－ＣＣＩＴＴＤ多項式 為ｈａｓｈｉｎｇ函數(shù)，４８位ＭＡＣ地址由ＣＲＣ［７－８］校驗方法后的結(jié)果通過ｈａｓｈｉｎｇ函數(shù)求得１６位余數(shù)，取結(jié)果１６位余數(shù)中１１個比特用于２ＫＢ地址表項索引值。Ｈａｓｈｉｎｇ函數(shù)計算的狀態(tài)機如圖２所示。
?
交換機ＭＡＣ層容納的地址表大小是有限的，理論上實際的物理地址有２的４８次方個，地址表只能記錄其中一個很小的子集，因此ｈａｓｈｉｎｇ函數(shù)不可避免地將不同的ＭＡＣ地址映射到相同的地址表項索引值。如果以太網(wǎng)中地址表項索引值與ＭＡＣ地址存在多對一的情況，就是發(fā)生了“地址沖突”。地址沖突的存在也說明總有部分ＭＡＣ地址丟失，不能被交換機學(xué)習(xí)到。地址沖突的解決方法在１．２中予以實現(xiàn)。
?
地址表組織結(jié)構(gòu)如圖３。圖３左邊列出的是地址表ＲＡＭ 中每個ｈａｓｈｉｎｇ桶內(nèi)表項０在ＲＡＭ 中的地址。在開始地址存儲和查找時，通過ＣＲＣ校驗得到的索引值指向的ｈａｓｈｉｎｇ桶內(nèi)表項０與表項１被讀出，通過對ＭＡＣ地址域進行比較確定匹配的表項，得到轉(zhuǎn)發(fā)端口的信息。
１．２ 地址表處理機制的實現(xiàn)方法（ＡｄｄｒＬｉｓｔ＿Ｐｒｏｃ）
１．２．１ 地址學(xué)習(xí)和查找的實現(xiàn)
以太網(wǎng)幀結(jié)構(gòu)中的源地址（ｓａ＿ｍａｃ）用于地址學(xué)習(xí)。目的地址（ｄａ＿ｍａｃ）用于地址查找。
對于較大吞吐量的交換芯片，能做到平均時間復(fù)雜度滿足線性的學(xué)習(xí)和查找。學(xué)習(xí)和查找采用ｈａｓｈｉｎｇ算法，發(fā)生碰撞采用ｈａｓｈｉｎｇ算法，碰撞后采用相鄰空間開放定址法（ｏｐｅｎ ａｄｄｒｅｓｓｉｎｇ?。瑁幔螅瑁椋睿纾郏梗保埃荨?/p>
學(xué)習(xí)的過程如下：
（１）根據(jù)ｈａｓｈｉｎｇ索引值ｓａ＿ｉｎｄｅｘ，檢索ＭＡＣ 地址表。
（２）表項中Ｖａｌｉｄ字段若為１代表該表項已占用，轉(zhuǎn)（３），否則表項空閑，轉(zhuǎn)（７）。
（３）表項內(nèi)容中的ＭＡＣ地址與ｓａ＿ｍａｃ進行比較，若相同Ｉ＿Ｆｉｎｄ置１，轉(zhuǎn)（７），否則轉(zhuǎn)（４），此時發(fā)生地址沖突。
（４）ｓａ＿ｉｎｄｅｘ＋１表項中Ｖａｌｉｄ字段若為１代表此處表項已占用，轉(zhuǎn)（５），否則表項空閑轉(zhuǎn)（７）。
（５）表項內(nèi)容中的ＭＡＣ地址與ｓａ＿ｍａｃ進行比較，若相同Ｉ＿Ｆｉｎｄ置１，轉(zhuǎn)（７），否則轉(zhuǎn)（６），此時發(fā)生地址沖突。
（６）此時有超過兩個不同的ＭＡＣ地址映射同一索引值，并且先到的寫入ｓａ＿ｉｎｄｅｘ和ｓａ＿ｉｎｄｅｘ＋１處。后面到達的ＭＡＣ地址覆蓋掉ｓａ＿ｉｎｄｅｘ處表項，完成一次學(xué)習(xí)。
（７）寫入該位置，Ｖａｌｉｄ置１，Ａｇｅ置１，完成一次學(xué)習(xí)。
查找的過程如下：
（１）判斷是不是廣播包，若是轉(zhuǎn)（１０），否則轉(zhuǎn)（２）。
（２）根據(jù)ｈａｓｈｉｎｇ索引值ｄａ＿ｉｎｄｅｘ，檢索ＭＡＣ 地址表。
（３）ｄａ＿ｉｎｄｅｘ和ｄａ＿ｉｎｄｅｘ＋１的Ｖａｌｉｄ字段組成二元組＜ｖａｌｉｄ０，ｖａｌｉｄ１＞，＜０，０＞轉(zhuǎn)（４）、＜０，１＞轉(zhuǎn)（５）、＜１，０＞轉(zhuǎn)（６）、＜１，１＞轉(zhuǎn)（７）。
（４）ｄａ＿ｍａｃ不在地址表中，轉(zhuǎn)（９）。
（５）ｄａ＿ｉｎｄｅｘ＋１表項內(nèi)容中ＭＡＣ地址與ｄａ＿ｍａｃ比較，若兩者相同，轉(zhuǎn)（８），否則轉(zhuǎn)（９）。
（６）ｄａ＿ｉｎｄｅｘ表項內(nèi)容中ＭＡＣ地址與ｄａ＿ｍａｃ比較，若兩者相同，轉(zhuǎn)（８），否則轉(zhuǎn)（９）。
（７）ｄａ＿ｍａｃ在地址表中轉(zhuǎn)（８），否則轉(zhuǎn)（９）。
（８）讀取表項內(nèi)容中的端口號，與ｄａ＿ｍａｃ組成一組數(shù)據(jù)發(fā)給到ｆｉｆｏ＿ｏｕｔ，完成一次查找。
（９）廣播該ＭＡＣ地址，發(fā)送ｄａ＿ｍａｃ和需要廣播標(biāo)志位給ｆｉｆｏ＿ｏｕｔ，完成一次查找。
（１０）Ｉ＿Ｆｉｎｄ標(biāo)志位為１代表地址表中有廣播請求的ＭＡＣ地址，不需要繼續(xù)廣播下去。Ｉ＿Ｆｉｎｄ標(biāo)志位為０代表需要繼續(xù)廣播下去，轉(zhuǎn)（１１）。
（１１）發(fā)送ｓａ＿ｍａｃ和需要廣播標(biāo)志位給ｆｉｆｏ＿ｏｕｔ，完成一次查找。
１．２．２ 地址老化的實現(xiàn)
交換機通過端口發(fā)送和接收幀的源地址（源ＭＡＣ地址、端口號）將存儲到地址表中。老化時間是一個影響交換機學(xué)習(xí)進程的參數(shù)。為地址表中每條地址項添加一個計數(shù)器用于表示該地址項的更新時間，通過查詢計數(shù)器位是否為零判斷一個地址是否已經(jīng)老化。在更新過程中，所有的輸出引腳處于“懸掛”。
老化過程如下：
（１）檢測到更新信號ｕｐｄ＿ｅｎ為高電平時，開始遍歷整個地址表。
（２）表項中Ａｇｅ字段為１，代表上一次遍歷周期到此遍歷周期內(nèi)該表項對應(yīng)的ＭＡＣ 地址被重新寫入過，轉(zhuǎn)（３），否則（４）。
（３）表項中的Ｖａｌｉｄ字段保持１，Ａｇｅ字段置０。
（４）表項中的Ｖａｌｉｄ字段置０ （刪除已老化的）。
（５）等待ｕｐｄ＿ｅｎ為低電平時停止遍歷，完成一次地址老化。
３ 地址表的輸出調(diào)整（ｆｉｆｏ＿ｏｕｔ）
Ｆｉｆｏ＿ｏｕｔ模塊根據(jù)前一級提供的各種標(biāo)志信號，實現(xiàn)對輸出的控制。輸入的數(shù)據(jù)信號有源地址，目的地址，查找到的表項，輸入的標(biāo)志信號有ｎｄ＿ｂｒ＿ｐａｃｋｅｔ （需要廣播標(biāo)志），Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ（是廣播包標(biāo)志）。
Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝１，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝０代表“是廣播包，不需要廣播”，對應(yīng)地址表處理機制中的事件—接收到廣播包中的ＭＡＣ地址存在地址表中。沒有輸出。
Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝１，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝１代表“是廣播包，需要廣播”，對應(yīng)地址表處理機制中的事件—繼續(xù)廣播下去。ｓａ＿ｍａｃ經(jīng)過封裝由ｄｏｕｔ０～ｄｏｕｔ３輸出。
Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝０，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝０代表“不是廣播包，不需要廣播”，對應(yīng)地址表處理機制中的事件—單播包中目的地址存在地址表中。表項經(jīng)過封裝，對應(yīng)端口輸出。
Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝０，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝１代表“不是廣播包，需要廣播”，對應(yīng)地址表處理機制中的事件—目的地址不存在地址表中。ｄａ＿ｍａｃ經(jīng)過封裝由ｄｏｕｔ０～ｄｏｕｔ３輸出。
２ 不同ｈａｓｈｉｎｇ函數(shù)的沖突率
Ｈａｓｈｉｎｇ算法的主要原理就是把大范圍映射到小范圍，沖突率和ｈａｓｈｉｎｇ函數(shù)的選取有密切的關(guān)系，圖４中選取了４種不ｈａｓｈｉｎｇ函數(shù)下發(fā)生地址沖突的概率。情況一采用的Ｈａｓｈｉｎｇ函數(shù)為ＭＡＣ地址和自身倒序做異或運算所得的結(jié)果經(jīng)過ＣＲＣ計算后取最后１１位索引值；情況二采用的Ｈａｓｈｉｎｇ函數(shù)為ＭＡＣ地址和自身倒序做異或運算所得的結(jié)果經(jīng)過ＣＲＣ計算后取前１１位索引值；情況三采用的Ｈａｓｈｉｎｇ函數(shù)為ＭＡＣ地址平方后取中間１１位為索引值，情況四采用的Ｈａｓｈｉｎｇ函數(shù)為將ＭＡＣ地址分割成位數(shù)相同的３部分，疊加這三部分的和取后１１位為索引值。
仿真過程描述如下：
４８位二進制數(shù)表示的范圍劃分為三子段，每個子段隨機生成３０００個數(shù)。一共有９０００個隨機ＭＡＣ地址，依次按照４種情況提供的ｈａｓｈｉｎｇ函數(shù)計算結(jié)果，索引值一樣沖突加一，分別在不同的地址表容量下求沖突率。
不同ｈａｓｈｉｎｇ函數(shù)沖突率如圖４所示。
?
仿真結(jié)果表明地址表項容量和ＭＡＣ地址數(shù)量接近時基本不發(fā)生沖突，在地址表較小情況下對于本次實驗給出的信源情況三的ｈａｓｈｉｎｇ函數(shù)有較小的沖突率。所以在選?。瑁幔螅瑁椋睿绾瘮?shù)時要結(jié)合該節(jié)點實際收發(fā)ＭＡＣ地址的概率模型，這樣才能有效的降低地址沖突發(fā)生。
３ 設(shè)計與驗證
仿真過程中，時鐘周期１００ｎｓ，ＭＡＣ地址取４８ｂｉｔ中的后１６ｂｉｔ，地址表深度為６４，ｈａｓｈｉｎｇ算法采用ＣＲＣ８取結(jié)果的后６ｂｉｔ。這樣處理的理由有兩點：第一４８ｂｉｔ與１６ｂｉｔ原理相同，１６ｂｉｔ占用的資源少；第二ＭＡＣ地址前２４ｂｉｔ是由設(shè)備廠商分配的序列號，對于一部分ＭＡＣ地址只有后１６ｂｉｔ不同。
ｓａ＿ｍａｃ既是輸入也是輸出，ｆｉｆｏ＿ｉｎ內(nèi)的寄存器保存一次輸入信號，待ｈａｓｈｉｎｇ算法后和索引值同步輸出，如圖５所示。
?
圖６的仿真結(jié)果中可以看到，１２００ｎｓ學(xué)習(xí)到ＭＡＣ地址（１６′ｈ７Ａ０Ｃ），１５００ｎｓ接收到對該ＭＡＣ地址的廣播包，停止繼續(xù)廣播下去。
?
圖７的仿真結(jié)果中可以看到２１００ｎｓ查詢的目的地址（１６’ｈＣ０Ａ７）存在于地址表中，它是２０００ｎｓ寫入地址表中的。
?
圖８中所示２６００ｎｓ開始地址更新，消耗６４個時鐘周期，遍歷所有的表項。９０００ｎｓ后的輸入和地址表更新前得輸入相同，可以看出有相同的輸出。
?
圖９所示不同的標(biāo)志信號控制不同的輸出，可以看到１７００ｎｓ和１８００ｎｓ都是向端口２轉(zhuǎn)發(fā)數(shù)據(jù)。１４００ｎｓ向４個端口廣播。
?
４ 結(jié)束語
對于以太網(wǎng)交換機來說，主要工作是根據(jù)收到數(shù)據(jù)幀中的目的ＭＡＣ地址，對ＭＡＣ地址表進行查找，把數(shù)據(jù)幀轉(zhuǎn)發(fā)到相應(yīng)的端口。ＭＡＣ地址表的查表效率直接影響交換機的性能。Ｈａｓｈｉｎｇ算法可以實現(xiàn)高效率的存儲和查找，但存在地址沖突，選擇合適的ｈａｓｈｉｎｇ函數(shù)是解決問題的有效途徑之一。比如可以統(tǒng)計交換機各端口ｈａｓｈｉｎｇ索引值的概率分布，找出發(fā)生沖突較高的區(qū)域，對這些區(qū)域按照概率進行排序，ｈａｓｈｉｎｇ函數(shù)針對沖突域中概率大的幾個ＭＡＣ地址來構(gòu)造。
工商網(wǎng)監(jiān)
評論