Fast Binary Search Packet Classification Based On Decision Trees
| Autor: | Wei-En Lo, 羅偉恩 |
|---|---|
| Rok vydání: | 2008 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 96 With the rapid growth of internet requirement and the occurrence of network applications, backbone routers nowadays need to classify packets into flows in a short time. In this paper, we propose a new algorithm called fast binary search packet classification to improve the efficiency on both search speed and the memory storage. In our algorithm, we first partition the filter table with decision tree but process a binary search on leaf nodes instead of the traditional tree traversal. We use a hash- based bit selecting strategy to replace the range cutting method in order to reduce memory usage and the impact caused by unbalance environment. Our algorithm can be implemented in two schemes. Variable-selected-bit scheme chooses different bit on each node and thus has better memory utilization. Fixed-selected-bit scheme chooses same bit on each node in the same level in order to reduce the packet encoding time and then increase the search speed. At last we compare our algorithm with two well-known algorithm － HiCuts and HyperCuts. Result shows that variable- selected-bit scheme has better performance on memory usage in all kinds of filter tables than others; another fixed-selected-bit scheme performs 20% better than HiCuts on search in filter tables with uniform distribution and even more than 50% better in an unbalance environment. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|