利用加強資料分類搜尋之高速第四層封包交換

Abstract

封包分類技術是將網路上的封包依據它的標頭分成不同的類別。現今許多新興的網路服務需要有一個快速的封包分類技術來幫助完成它們的機制。例如網路安全、網路分級服務、流量分散、計帳服務等等。封包分類的方法大概可分成用硬體設計和軟體設計兩大類，但是目前所知道的方法在處理大量的過濾子時，通常都不能夠提供高速的封包分類或者是需要大量的記憶體空間。 在這一篇論文中，我們提出二個方法來改進封包分類的效率。一個是利用延展過濾子的方式來減少記憶體的需求，另一個方法是利用快取記憶體來過濾掉一些無謂的記憶體讀取，進而提升封包分類的速度。在我們的實驗中，在一個100,000過濾子的資料庫中，我們的方法能夠每秒分類2.3百萬封包，達到高速的封包分類技術。

Packet classification is a technique that classifies the flows into different classes.Nowadays the packet classification techniques play an important role for many new Internet services, such as security, QoS, load balancing, traffic accounting, etc. Currently, many packet classification algorithms were proposed and were categorized into two classes, the software solutions and the hardware solutions. But the existing layer-4 switching algorithms usually do not support high throughput or suffer from memory explosion problem with large filters. In this thesis, we focus on the problems how to perform two-dimensions packet classification efficiently. The tuple space search is one of the packet classification algorithms, but it still suffers from the memory explosion and other performance issues. We propose two schemes to improve the tuple space search algorithm. One is the concept of the filter expansion and the other is the compressed filter mechanism. The former reduces the memory requirement and the latter uses cache to filter out some unnecessary memory accesses to speed up the searching. According to the experiments, our schemes are able to achieve 2.3 millions packet classifications per second with 100,000 filters.