利用濃縮的位元向量之可擴充性的封包分類演算法

Abstract

封包分類的功能在下一世代的路由器設計上扮演了極其重要的角色。 對於支援防火牆，MPLS，QoS之類的應用來說，封包分類是一項最基 本的要求。當網際網路服務提供者（ISP）為了適應使用者不同的需 求時，路由器便需要提供分類各種封包的功能。如何快速的執行封 包分類的動作是這篇論文所想討論的問題。 位元向量演算法是一個在解決封包分類問題方面令人感興趣的硬體方 式。不同於其他利用Ternary CAM解決的硬體方式，它有效地利用記 憶體資源，在中型過濾資料庫的環境下達到非常好的效能。在這篇論 文中，我們試圖改進原有位元向量的方式以擴充至更大的過濾資料庫 。我們結合位元向量和線性搜尋的概念提出一個新的演算法稱為濃縮 位元向量。藉由觀察數個位元向量中相關的資訊，我們濃縮數個相關 的位元向量成為一個單一的位元向量。根據不同的方式濃縮數個位元 向量，我們可以提供適應不同網路環境的靈活性，這是我們演算法中 一個重要的特性。實驗中也證明我們的演算法在需求的空間與搜尋的 速度上遠遠優於原本的位元向量演算法。

Packet classification plays an important role in the design of new generation router. It is fundamental to the support of applications such as firewalls, MPLS, and QoS. Routers must provide this functionality to classify all kinds of incoming traffic, while ISPs try to offer these network applications for end users. Performing packet classification at wire speed is the main concern of this thesis. Bit vector algorithm proposed in [1] is an interesting hardware solution to solve the packet classification problem. Different from other hardware solutions such as ternary CAM, it efficiently utilize the memories to achieve an excellent performance in medium size filter database. In this thesis, we improve the original bit vector algorithm to scale up with the filter number increases. We proposed a novel algorithm called Bit Vector Condensation that combines the concept of both bit vector search and linear search and condense several bit vectors into one bit vector. With the flexibility of choosing different inclusion criteria, our algorithm could adapt to various environments in the backbone network. Experiments also showed that our proposed algorithm outperforms the bit vector algorithm in the storage requirements and search speed.