کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
449167 | 693644 | 2010 | 12 صفحه PDF | دانلود رایگان |
Decision tree based schemes are widely used in designing high-speed packet classification algorithms. The primary objective is to construct a decision tree with minimal storage and searching time complexity. In this paper, we proposed a novel decision tree packet classification algorithm based on Efficient Multiple Bit Selection (EMBS). In the proposed algorithm, prefix fields are transformed to a set of independent bits; and multiple arbitrary bits are selected to cut nodes when building the decision tree. A Performance Estimate Function (PEF) and an efficient bit selecting algorithm are exploited to determine which bits should be selected to obtain an efficient decision tree with high performance. The proposed EMBS algorithm is capable of handling range match fields, and it is suitable for IPv6 packet classification as well as IPv4. Evaluation results show that EMBS provides a great improvement over recent decision tree based algorithms in both space requirement and searching performance.
Journal: Computer Communications - Volume 33, Issue 15, 15 September 2010, Pages 1773–1784