| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2015-11-06 09:50 Run-Based Trieから構成される決定木の枝刈り法 ○原田崇司・田中 賢（神奈川大）・三河賢治（新潟大）  ISEC2015-38 SITE2015-25 LOIS2015-32 |
|
| 抄録 | （和） | パケットケット分類は，サイバー脅威からの保護を主要な目的とするネットワークトラッフィク制御における基本的な処理である．パケット分類器は，到着するパケットのヘッダーとルールリストとを比較して到着するパケットの通過の可否を判断する．パケット分類の実装において，ルールリストをそのまま線型探索する方法は効率が悪い．この問題を解決するためにルールリストを最適化する方法とパケットに合致する最優先ルールを高速に見つける方法とが提案されてきた．Srinivasan らは，ルール数ではなくルールの長さに計算量が比例する階層型トライを用いた新しい探索手法を提案した．けれども，階層型トライとその改良アルゴリズムは，シングルプレフィックスのルールにしか適用できない．L4やより高層でのパケット分類では，任意のビットマスクを含むルールを扱う必要がある．我々は，階層型トライに基づいた任意のビットマスクルールを扱えるRun-Based Trieを提案した．Run-Based Trieから構成される決定木は，ビット長に対して不要なパスを大量に含み膨大なメモリを必要とする点が問題となる．本稿では決定木に冗長性をもたらす5つの点に着目した不要なパスの枝刈り法を提案する．提案する枝刈り法は，16ビットまでのルールに対し決定木の構築に必要なメモリを削減できることを確認した. |
| （英） | 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. | |
| キーワード | （和） | パケット分類 / トライ木 / 決定木 / 任意のビットマスク / / / / |
| （英） | packet classification / trie / decision tree / arbitrary bitmask / / / / | |
| 文献情報 | 信学技報, vol. 115, no. 294, SITE2015-25, pp. 11-17, 2015年11月. | |
| 資料番号 | SITE2015-25 | |
| 発行日 | 2015-10-30 (ISEC, SITE, LOIS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2015-38 SITE2015-25 LOIS2015-32 |
|
| 研究会情報 | |
| 研究会 | LOIS ISEC SITE |
| 開催期間 | 2015-11-06 - 2015-11-07 |
| 開催地（和） | 神奈川大学 1号館804会議室 |
| 開催地（英） | Kanagawa Univ. |
| テーマ（和） | 情報セキュリティ，ライフログ活用技術，ライフインテリジェンス，オフィス情報システム，一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | SITE |
| 会議コード | 2015-11-LOIS-ISEC-SITE |
| 本文の言語 | 日本語 |
| タイトル（和） | Run-Based Trieから構成される決定木の枝刈り法 |
| サブタイトル（和） | |
| タイトル（英） | A Pruning Method for the Decision Tree constructed on Run-Based Trie. |
| サブタイトル（英） | |
| キーワード(1)（和/英） | パケット分類 / packet classification |
| キーワード(2)（和/英） | トライ木 / trie |
| キーワード(3)（和/英） | 決定木 / decision tree |
| キーワード(4)（和/英） | 任意のビットマスク / arbitrary bitmask |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 原田 崇司 / Takashi Harada / ハラダ タカシ |
| 第1著者 所属（和/英） | 神奈川大学 (略称： 神奈川大) Kanagawa University (略称： Kanagawa Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 田中 賢 / Ken Tanaka / タナカ ケン |
| 第2著者 所属（和/英） | 神奈川大学 (略称： 神奈川大) Kanagawa University (略称： Kanagawa Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 三河 賢治 / Kenji Mikawa / ミカワ ケンジ |
| 第3著者 所属（和/英） | 新潟大学 (略称： 新潟大) Niigata University (略称： Niigata Univ.) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2015-11-06 09:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | SITE |
| 資料番号 | ISEC2015-38, SITE2015-25, LOIS2015-32 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | no.293(ISEC), no.294(SITE), no.295(LOIS) |
| ページ範囲 | pp.11-17 |
| ページ数 | 7 |
| 発行日 | 2015-10-30 (ISEC, SITE, LOIS) |
[研究会発表申込システムのトップページに戻る]