| 講演名 | 2016-11-24 ポインタ付与によるRun-Based Trie探索の高速化 原田 崇司(神奈川大), 田中 賢(神奈川大), 三河 賢治(新潟大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Run-Based Trieは，アルファベット${0, 1, *}$上の長さ$w$の系列のリストによって定義された函数$f : {0, 1}^{w} to mathbb{N}$を計算することができるデータ構造である．パケット分類問題は，ネットワーク機器を通過するパケットと与えられているフィルタリングルールリストの各ルールとを照合して，パケットに合致する優先度の最も高いルールを求める問題である．この問題は，Run-Based Trieを上手く用いることができる問題の一つである．本稿では，Run-Based Trieの全てのノードにポインタを付与することにより，Run-Based Trie探索の時間計算量をルールリストのルール数$n$に関して$O(nw + w^{2})$から$O(nw)$へと減らす手法を提案する．また，計算機実験により提案手法の有効性を検証する． |
| 抄録(英) | |
| キーワード(和) | パケット分類 / トライ木 / 任意のビットマスク |
| キーワード(英) | packet classification / trie / arbitrary bitmask |
| 資料番号 | CAS2016-60,MSS2016-40 |
| 発行日 | 2016-11-17 (CAS, MSS) |
| 研究会情報 | |
| 研究会 | MSS / CAS / IPSJ-AL |
|---|---|
| 開催期間 | 2016/11/24(から2日開催) |
| 開催地（和） | 神戸情報大学院大学 |
| 開催地（英） | Kobe Institute of Computing |
| テーマ（和） | グラフ、ペトリネット、ニューラルネット及び一般 |
| テーマ（英） | |
| 委員長氏名（和） | 山根 智(金沢大) / 高橋 俊彦(新潟大) |
| 委員長氏名（英） | Satoshi Yamane(Kanazawa Univ.) / Toshihiko Takahashi(Niigata Univ.) |
| 副委員長氏名（和） | 名嘉村 盛和(琉球大) / 平木 充(ルネサス エレクトロニクス) |
| 副委員長氏名（英） | Morikazu Nakamura(Univ. of Ryukyus) / Mitsuru Hiraki(Renesas) |
| 幹事氏名（和） | 中田 充(山口大) / 豊嶋 伊知郎(東芝) / 越田 俊介(東北大) / 山口 基(ルネサスシステムデザイン) |
| 幹事氏名（英） | Mitsuru Nakata(Yamaguchi Univ.) / Ichiro Toyoshima(Toshiba) / Shunsuke Koshita(Tohoku Univ.) / Motoi Yamaguchi(Renesas) |
| 幹事補佐氏名（和） | 金城 秀樹(沖縄大) / 橘 俊宏(湘南工科大) / 中村 洋平(日立) |
| 幹事補佐氏名（英） | Hideki Kinjo(Okinawa Univ.) / Toshihiro Tachibana(Shonan Inst. of Tech.) / Yohei Nakamura(Hitachi) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Mathematical Systems Science and its applications / Technical Committee on Circuits and Systems / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ポインタ付与によるRun-Based Trie探索の高速化 |
| サブタイトル（和） | |
| タイトル（英） | A Fast Search Method for Run-Based Tries via Pointers |
| サブタイトル（和） | |
| キーワード(1)（和/英） | パケット分類 / packet classification |
| キーワード(2)（和/英） | トライ木 / trie |
| キーワード(3)（和/英） | 任意のビットマスク / arbitrary bitmask |
| 第 1 著者 氏名（和/英） | 原田 崇司 / Takashi Harada |
| 第 1 著者 所属（和/英） | 神奈川大学(略称：神奈川大) Kanagawa University(略称：Kanagawa Univ.) |
| 第 2 著者 氏名（和/英） | 田中 賢 / Ken Tanaka |
| 第 2 著者 所属（和/英） | 神奈川大学(略称：神奈川大) Kanagawa University(略称：Kanagawa Univ.) |
| 第 3 著者 氏名（和/英） | 三河 賢治 / Kenji Mikawa |
| 第 3 著者 所属（和/英） | 新潟大学(略称：新潟大) Niigata University(略称：Niigata Univ.) |
| 発表年月日 | 2016-11-24 |
| 資料番号 | CAS2016-60,MSS2016-40 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | CAS-315,MSS-316 |
| ページ範囲 | pp.13-18(CAS), pp.13-18(MSS), |
| ページ数 | 6 |
| 発行日 | 2016-11-17 (CAS, MSS) |