利用位元壓縮法的快速封包分類演算法

Abstract

為了提供安全防護，虛擬私有網路，品質保證等等網際網路的服務。網際網路路由器需要將收到的封包進行快速的分類。封包分類是利用在封包標頭所包含的資訊與路由器中事先定義的規則表進行比對，一般而言，多重欄位的封包分類是一個相當困難的問題，已經有許多不同的演算法被提出來解決這個問題。在這篇論文中，我們提出一個稱為位元壓縮(bit compression)的封包分類演算法。如同眾所周知的位元圖交集(bitmap intersection)演算法，位元壓縮也採用多維區域查詢(multiple dimensional range lookup)的方法。觀察位元圖交集演算法中的位元向量(bit vector)，我們發現在位元向量中包含許多的0位元，利用這個特性，我們將位元向量進行壓縮，藉由保留有用的資訊，建立一個用來記錄剩餘位元相對應的規則號碼之索引表，以及移除位於位元向量中多餘的位元來達成壓縮的目的。此外，利用有百搭符號的規則(wildcarded rule)可以更進一步地提高壓縮的比例。透過實驗結果的觀察，位元壓縮演算法可以將儲存空間的複雜度由位元圖交集演算法的O(dN 2)減低為O(dN∙logN)，而不犧牲封包分類的效能，在這裡d表示維度的個數，而N表示規則的個數。在封包分類的效能上。因為位元壓縮演算法只需要比位元圖交集演算法更少的記憶體存取時間，而在封包分類的問題中，記憶體的存取往往決定了整體的查詢時間，所以，即使位元壓縮需要額外的解壓縮的步驟，仍會有比位元圖交集演算法更快的分類速度。

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 bit compression algorithm. Like the previously well known algorithm, bitmap intersection, bit compression is based on the multiple dimensional range lookup approach. Since the bit vectors of the bitmap intersection contain lots of ‘0’ bits. Utilizing those ‘0’ bits, the bit vectors could be compressed. We compress the bit vectors by preserving only useful information but removing the redundant bits of the bit vectors. An additional index table would be created to keep tract of the rule number associated with the remaining bits. Additionally, the wildcarded rules also enable more extensive improvement. Our experiment results show that the bit compression algorithm reduces the storage complexity from O( ) of the bitmap intersection algorithm to O(dN∙logN), where d denotes the number of dimensions and N represents the number of rules, without sacrificing the classification performance. On the classification performance, the bit compression algorithm requires much less memory access time than bitmap intersection algorithm. Since memory access dominates the lookup time. Even though extra processing time for decompression is required for the bit compression algorithm, the bit compression scheme still outperforms bitmap intersection scheme on the classification speed.