CCNルータのためのハッシュテーブルと平衡木の併用によるメモリアクセスを削減したFIBの構築

摘要

従来のIPネットワークはユーザ·サーバ間通信を基本とし，サーバに負担が集中する問題がある．加えて，IPルータはユーザから受け取ったパケットを次のルータに横流しするだけであり，ルータは，ユーザが必要とするコンテンツを提供する機能を有していない．従来の転送機能に加え，キャッシュ機能を持つよう機能拡張されたルータにより構築されるネットワークがCCN（Content Centric Networking）であり，次世代ネットワークとして注目されている．CCNルータは，FIBと呼ばれるルーティングテーブルを持っが，FIBのメモリアクセス処理がボトルネックとなる．本稿では，ハッシュテーブルと平衡木を組み合わせたデータ構造を持つFIBを提案する．提案手法は，ハッシュによるテーブル探索を基本とし，ハッシュ値が衝突した際に，平衡木を用いてデータを保持する．こうすることでハッシュ値が衝突した際のメモリアクセス回数の増加を緩和し，FIB探索処理におけるメモリアクセス回数の削減を実現する．平衡木を用いることで，木構造のばらつきを抑え，安定的にメモリアクセス回数を少なくすることができる．提案手法のメモリアクセス回数は，多分木で実装したFIBに比べ約5.9%，ハッシュテーブルで実装したFIB に比べ約88.1%に削減することができた．