講演抄録/キーワード |
講演名 |
2016-11-30 10:55
CCNルータのためのコンテンツのネーム長による分割ハッシュテーブルと平衡木によるFIBの構築 ○島崎健太(早大)・右近祐太・宮崎昭彦(NTT)・津田俊隆・中里秀則・戸川 望(早大) VLD2016-65 DC2016-59 |
抄録 |
(和) |
従来の IP ネットワークはユーザ・サーバ間通信を基本とし,サーバに負担が集中する問題がある.加えて, IP ルータはユーザから受け取ったパケットを次のルータに横流しするだけであり,ルータは,ユーザが必要とするコ ンテンツを提供する機能を有していない.従来の転送機能に加え,キャッシュ機能を持つよう機能拡張されたルータ により構築されるネットワークが CCN (Content Centric Networking) であり,次世代ネットワークとして注目され ている.CCN ルータは,FIB と呼ばれるルーティングテーブルを持つが,FIB のテーブルルックアップにかかる比 較数がボトルネックとなる.本稿では,分割ハッシュテーブルと平衡木を組み合わせたデータ構造を持つFIB を提案 する.提案手法は,ハッシュによるテーブル探索を基本とし,ハッシュ値が衝突した際に,平衡木を用いてデータを 保持する.ハッシュによるテーブル探索の前処理としてブルームフィルタによるフィルタリングを行い,さらに,コ ンテンツのネーム長が 4 以下のコンテンツ名によるハッシュ値とコンテンツのネーム長が 5 以上のコンテンツ名によ るハッシュ値の 2 つに分けて考えることで,ハッシュテーブルを分割する.フィルタリングと分割ハッシュテーブル を用いることで平衡木の高さを小さくし,比較数を削減できる.提案手法の比較数は,多分木で実装した FIB に比べ 約 92.5%,ハッシュテーブル (線形リスト) で実装した FIB に比べ約 40.7%,ハッシュテーブル (平衡木) で実装した FIB に比べ約 18.5%,ブルームフィルタ+ハッシュテーブル (線形リスト) で実装した FIB に比べ約 31.1%,ブルーム フィルタ+ハッシュテーブル (平衡木+分割なし) で実装した FIB に比べ約 5.14%削減することができた. |
(英) |
(Not available yet) |
キーワード |
(和) |
content centric networking (CCN) / forwarding information base (FIB) / 比較数 / ルータ / / / / |
(英) |
/ / / / / / / |
文献情報 |
信学技報, vol. 116, no. 330, VLD2016-65, pp. 123-128, 2016年11月. |
資料番号 |
VLD2016-65 |
発行日 |
2016-11-21 (VLD, DC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2016-65 DC2016-59 |