CCNルータのためのコンテンツのネーム長による分割ハッシュテーブルと平衡木によるFIBの構築

摘要

従来の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%削減することができた．