| Presentation | 2015-11-06 A Pruning Method for the Decision Tree constructed on Run-Based Trie. Takashi Harada, Ken Tanaka, Kenji Mikawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Packet classification is a fundamental process in the control of network traffic that protects inner net- works from cyber threats. It determines whether to permit or discard incoming packets by comparing their headers with every rule of a rulelists. In implementation of packet classification, since linear search to a given rule lists is inefficient, many packets classification algorithms have been proposed. Srinivasan et al. proposed a novel lookup scheme using a hierarchical trie, which realizes faster packet classification with time complexity propotional to rule length rather than the number of rules. However, the hierarchical trie and its various improved algorithms can treat only single prefix rules. Since it is necessary for layer 4 and higher packet classifications to deal with arbitrary bitmask rulese, we proposed a Run-Based Trie based on the hierarchical trie. However the decision tree constructed on Run-Based Trie contains a lot of unnecessary paths and need to a large amount of memory. In this paper, we propose a pruning method for the decision tree. This method focus on 5 points that cause the decision tree redundancies. Our proposed method reduce the memory to construct the decision tree up to 16 bits length. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | packet classification / trie / decision tree / arbitrary bitmask |
| Paper # | ISEC2015-38,SITE2015-25,LOIS2015-32 |
| Date of Issue | 2015-10-30 (ISEC, SITE, LOIS) |
| Conference Information | |
| Committee | LOIS / ISEC / SITE |
|---|---|
| Conference Date | 2015/11/6(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kanagawa Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Manabu Okamoto(NTT) / Yukiyasu Tsunoo(NEC) / Noriaki Yoshikai(Nihon Univ.) |
| Vice Chair | Hiroyuki Nishi(Sojo Univ.) / Masahiro Mambo(Kanazawa Univ.) / Kazuto Ogawa(NHK) / Hitoshi Okada(NII) / Tetsuya Morizumi(Toyo Networks & System Integration) |
| Secretary | Hiroyuki Nishi(Tsuda College) / Masahiro Mambo(NTT) / Kazuto Ogawa(AIST) / Hitoshi Okada(Toshiba) / Tetsuya Morizumi(Shibaura Inst. of Tech.) |
| Assistant | Yu Ichifuji(NII) / Tetsuya Izu(Fujitsu Lab.) / Takaaki Mizuki(Tohoku Univ.) / Noritaka Yamashita(NEC) / Takahiro Haga(Gifu Shotoku Gakuen Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Life Intelligence and Office Information Systems / Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Pruning Method for the Decision Tree constructed on Run-Based Trie. |
| 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 | 2015-11-06 |
| Paper # | ISEC2015-38,SITE2015-25,LOIS2015-32 |
| Volume (vol) | vol.115 |
| Number (no) | ISEC-293,SITE-294,LOIS-295 |
| Page | pp.pp.11-17(ISEC), pp.11-17(SITE), pp.11-17(LOIS), |
| #Pages | 7 |
| Date of Issue | 2015-10-30 (ISEC, SITE, LOIS) |