應用Kd-Tree架構於Tuple Space的封包分類機制

Abstract

為了提供封包不等同的服務，路由器(router)、防火牆(firewall)和端點路由器(edge router)必須能夠辨識網路封包，並根據管理者所訂定的規則(rule)分類封包，這樣的動作稱之為封包分類(packet classification)。封包分類的應用廣泛，除了可應用在提供服務品質(QoS)的路由器、提供安全保護的防火牆之外，尚可使用於網際網路服務提供者(ISP，Internet Service Provider)的端點路由器，以幫助企業建立虛擬私有網路(VPN，Virtual Private Network)。因此在過去幾年當中，許多研究者致力於設計適合高維應用的封包分類方法，希望能夠提供快速、低儲存量的分類機制。 在本篇論文當中，我們提出以Tuple space為基礎的封包分類機制，並使用多維的二元樹(multidimensional binary search tree)來改善搜尋的時間，可達到 的效能。除了滿足具彈性、可擴充的特性，同時還考慮到更新分類器(classifier)的需求及IDS的應用，提出低成本的擴充方式，使得我們的封包分類機制相對於其他方法具有較高的適應性。

Packet classification is to categorize network traffic in order to provide differential services to particular packet(s). It can be used within integrated or differentiated services in routers, security assurance in firewall and VPN tunnel, or payment in ISP edge routers. In last few years, many researchers were devoted to provide fast packet classification methods for high dimensional classifier. However, these methods either have undesirable performance and storage cost, or lack scalability of dimensions. In this paper, we propose a packet classification method based on tuple space search, and use the multidimensional binary search tree (Kd-tree) to improve search performance in search time with controlled storage (where d is the number of dimensions, W is the number of bit length of fields). Moreover, it can be extended with little cost to support both incremental update for future use and IDS applications, which makes our method more adaptive than others.