封包分類之適應性線搜尋演算法

Abstract

快速封包分類已經是網際網路支援加值服務的關鍵技術，這些服務的共通性就是必須要能辨識使用者資料流。封包分類可看成在一個規則集合裡面尋找一個最好的匹配規則的過程，但由於網際網路協定階層化，封包分類通常是指對選自封包表頭欄位的處理程序，例如來源及目的位址、來源及目的埠、協定識別號及服務種類。一般而言，封包分類的複雜度與欄位數目、欄位寬度、匹配標準及規則數目有很大相依性。 在本論文中，我們提出Entry-pruning Line Search Algorithm 及 Adaptive Line Search Algorithm 兩種快速封包分類演算法，只要增加少量儲存空間，就可以大幅改善Line Search Algorithm的平均及最差情況搜尋效能。

Fast packet classification has become a key component to enable additional services in Internet applications. What these services have in common is their requirement for recognizing flows. Basically packet classification can be considered as a process looking for the best matching filter in a filter set. Because of the Internet protocol layers, packet classification is often performed for multiple fields selected from packet headers such as source and destination IP addresses, source and destination port numbers, protocol ID, and even type of service. In general, the search time and storage complexity of a packet classification depend heavily on the number of fields, lengths of fields, match criterion and the number of filters. In this thesis, we propose two fast packet classification algorithms: Entry-pruning Line Search algorithm and Adaptive Line Search algorithm, with increasing a little storage, the average and worst case search performance can be improved obviously.