2026-04-13T14:10:40Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00176033 2025-01-20T06:02:06Z 1164:2036:8446:8973

CCNルータのためのコンテンツのネーム長による分割ハッシュテーブルと平衡木によるFIBの構築 Partitioned Hash-table and Balanced-tree based FIB Architecture 島崎, 健太 右近, 祐太 宮崎, 昭彦 津田, 俊隆 中里, 秀則 戸川, 望 Kenta, Shimazaki Yuta, Ukon Akihiko, Miyazaki Toshitaka, Tsukuda Hidenori, Nakazato Nozomu, Togawa セキュリティ，ネットワーク 従来の 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 % 削減することができた． 情報処理学会 2016-11-21 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/176033 2188-8639 AA11451459 研究報告システムとLSIの設計技術（SLDM） 2016-SLDM-177 23 1 6 https://ipsj.ixsq.nii.ac.jp/record/176033/files/IPSJ-SLDM16177023.pdf application/pdf 383.8 kB