雜湊演算法的設計與實現

Abstract

在快速交換機（switch）中，封包的交換必需透過查表的結果才知道該往那個埠轉送（forwarding），所以對交換機而言設計出一個可快速查表的演算法是不可或缺的。 藉由媒介存取控制位址（MAC address）的特性以及移位折疊法（shift folding）的使用，我們找到兩個適合用來查表的雜湊函數。在本篇論文中我們提出雙層雜湊桶（double hashing buckets）的查表法，不但可以達到快速查表的目的且可有效地降低溢滿（overflow）的個數。 在我們提出的硬體設計查表法中，共有二個儲存媒介存取控制位址的裝置，分別為2K個可存放4筆項目（entry）的雜湊桶（hashing buckets）及一個可存放8筆項目的緩衝器（buffer）。由於搜尋雜湊桶與搜尋緩衝器可以平行處理，所以我們可以縮短搜尋時間，且搜尋緩衝器是採用對硬體而言非常易容實現的循序式搜尋法（sequential search）。另外我們也應用雜湊法達到負載平衡的目的並且不會造成封包重覆接收與更改封包次序的問題。

In a high-speed switch, the packets are delivered to their destined output ports based on the results of the table lookup. So a good fast lookup algorithm is indispensable to switch. By means of the characteristics of MAC (Media Access Control) addresses and the using of the shift folding, we can find two hashing functions that are suitable for table lookup. In this thesis, we propose a lookup scheme called double hashing buckets. In addition to fast lookup, our proposed scheme can reduce the possibility of overflow. In the hardware implementation of our proposed table lookup scheme, there are 2K hashing buckets and each bucket has 4 entries. Besides, there is a buffer for overflow and its size is 8 entries. Owing to the parallel search of both hashing buckets and the buffer, the search time can be reduced. Since we perform sequential search on the buffer, it is very simple for hardware implementation. Moreover, our proposed hashing scheme can be used for load balancing and it will not cause any problem like duplication of packet or packet re-ordering.