進階區域式對角型Tuple Space 搜尋之快速封包分類演算法

Abstract

為了提供安全防護，虛擬私有網路，品質保證等等網際網路的服務。網際網路路由器需要將收到的封包進行快速的分類。封包分類是利用在封包標頭所包含的資訊與路由器中事先定義的規則表進行比對，一般而言，多重欄位的封包分類是一個相當困難的問題，已經有許多不同的演算法被提出來解決這個問題。在這篇論文中，我們提出一個稱為Addvanced Regional Diagonal Tuple Space Search的封包分類演算法，採用Diagonal Tuple Space Search之觀念，並利用分區搜尋，鏈結搜尋，單向搜尋等三種搜尋加以改良演算法：分區搜尋將整個Tuple space切割成許多區塊；鏈結搜尋使得搜尋進展能跳越至指定區域；單向搜尋則能將Diagonal seacr的至多三次二元搜尋減少為二次二元搜尋。透過實驗的觀察，可以將搜尋次數提升為只需2logw，w為維度之長度；同時對儲存空間的複雜度由O(n2wlog w)改變為O(nlogw + n2w)，n表示規則之總數。在封包分類的效能上。因為Addvanced Regional Diagonal Tuple Space Search只需要比Diagonal Tuple Space Search更少的記憶體存取時間，而在封包分類的問題中，記憶體的存取往往決定了整體的查詢時間，所以，即使Addvanced Regional Diagonal Tuple Space Search需要另外對區塊作搜尋的步驟，仍會有比Diagonal Tuple Space Search更快的分類速度。

In order to support Internet security, virtual private networks, QoS and etc., Internet routers need to classify incoming packets quickly into flows. Packet classification uses information contained in the packet header to look up the predefined rule table in the routers. In general, packet classification on multiple fields is a difficult problem. A variety of algorithms had been proposed. This thesis presents a novel packet classification algorithm, called advanced regional diagonal tuple space search algorithm using the concept of diagonal tuple space search algorithmand three search types: block seach, link-list search and single-direction search. Block search can divide all tuple space into many small blocks; link-list search can jump to assigned blocks to start process; single-direction search oly need two binary search. Our experiment results show that the advanced regional diagonal tuple space search algorithm only need 2 log w, where w denotes the length of dimensions, and the storage complexity from O(n2wlog w) of the diagonal tuple space search algorithm to O(nlogw + n2w), where n represents the number of rules. On the classification performance, the advanced regional diagonal tuple space search algorithm requires much less memory access time than diagonal tuple space search algorithm. Since memory access dominates the lookup time. Even though extra processing time for searching areas is required for the advanced regional diagonal tuple space search algorithm, the advanced regional diagonal tuple space search algorithm still outperforms diagonal tuple space algorithm on the classification speed.