| Presentation | 2017-05-12 An RBT Decision Tree Construction for Sparse Rules Takashi Harada, Ken Tanaka, Kenji Mikawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Packet classification problem is to determine the highest priority rule that matches with an incoming packet in a networking equipment among all the filtering rules implementing a packet classification policy. Since the number of rules $n$ in a rule list tends to increase, it is necessary to develop an algorithm to find the highest priority rule independent of $n$. Thus we proposed a data structure Run-Based Trie (RBT) and a classification algorithm using decision tree constructed on RBT[1],[2]. The decision tree classification method is independent of $n$. However, a space complexity of the decision tree is exponential order $O(n^{w})$ with $n$ rules of length $w$. Even for Rules with $w geq 18$ and sparse rules generated by ClassBench[3] the decision tree has not been constructed. In this paper, we propose a novel decision tree construction method that does not construct unnecessary nodes by referencing runs matched through the root node to a node $v$ when constructing a child node of $v$. The proposed method can construct the decision tree for sparse rules generated by ClassBench. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | packet classification / trie / decision tree / arbitrary bitmask |
| Paper # | COMP2017-2 |
| Date of Issue | 2017-05-05 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2017/5/12(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiro Ito(Univ. of Electro-Comm.) / 堀山 貴史(埼玉大) |
| Vice Chair | Yushi Uno(Osaka Pref. Univ.) |
| Secretary | Yushi Uno(Seikei Univ.) / (Kyushu Inst. of Tech.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An RBT Decision Tree Construction for Sparse Rules |
| Sub Title (in English) | |
| Keyword(1) | packet classification |
| Keyword(2) | trie |
| Keyword(3) | decision tree |
| Keyword(4) | arbitrary bitmask |
| 1st Author's Name | Takashi Harada |
| 1st Author's Affiliation | Kanagawa University(Kanagawa Univ.) |
| 2nd Author's Name | Ken Tanaka |
| 2nd Author's Affiliation | Kanagawa University(Kanagawa Univ.) |
| 3rd Author's Name | Kenji Mikawa |
| 3rd Author's Affiliation | Niigata University(Niigata Univ.) |
| Date | 2017-05-12 |
| Paper # | COMP2017-2 |
| Volume (vol) | vol.117 |
| Number (no) | COMP-28 |
| Page | pp.pp.9-15(COMP), |
| #Pages | 7 |
| Date of Issue | 2017-05-05 (COMP) |