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

• Item type: SIG Technical Reports(1)
• 公開日: 2015-11-24
• タイトル: CCNルータのためのハッシュテーブルと平衡木の併用によるメモリアクセスを削減したFIBの構築
• タイトル / 言語: en
• タイトル: Hash-table and Balanced-tree based FIB Architecture for CCN Routers Reducing Memory Accesses
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: プロセッサとメモリ
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 日本電信電話株式会社ＮＴＴデバイスイノベーションセンタ
• 著者所属: 日本電信電話株式会社ＮＴＴデバイスイノベーションセンタ
• 著者所属: 日本電信電話株式会社ＮＴＴデバイスイノベーションセンタ
• 著者所属: 日本電信電話株式会社ＮＴＴデバイスイノベーションセンタ
• 著者所属: 早稲田大学国際情報通信研究センター
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science and Communications Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): NTT Device Innovation Center, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Device Innovation Center, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Device Innovation Center, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Device Innovation Center, NTT Corporation
• 著者所属(英): en
• 著者所属(英): Global Information and Telecommunication Institute, Waseda University
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science and Communications Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science and Communications Engineering, Waseda University
• 著者名: 島崎, 健太; 青木, 孝; 羽田野, 孝裕; 大塚, 卓哉; 宮崎, 昭彦; 津田, 俊隆; 朴, 容震; 戸川, 望
• 著者名(英): Kenta, Shimazaki; Takashi, Aoki; Takahiro, Hatano; Takuya, Otsuka; Akihiko, Miyazaki; Toshitaka Tsuda; Yong-Jin, Park; Nozomu, Togawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 従来の IP ネットワークはユーザ・サーバ間通信を基本とし，サーバに負担が集中する問題がある．加えて，IP ルータはユーザから受け取ったパケットを次のルータに横流しするだけであり，ルータは，ユーザが必要とするコンテンツを提供する機能を有していない．従来の転送機能に加え，キャッシュ機能を持つよう機能拡張されたルータにより構築されるネットワークが CCN(Content Centric Networking) であり，次世代ネットワークとして注目されている．CCN ルータは，FIB と呼ばれるルーティングテーブルを持つが，FIB のメモリアクセス処理がボトルネックとなる．本稿では，ハシシュテーブルと平衡木を組み合わせたデータ構造を持つ FIB を提案する．提案手法は，ハシシュによるテーブル探索を基本とし，ハシシュ値が衝突した際に，平衡木を用いてデータを保持する．こうすることでハシシュ値が衝突した際のメモリアクセス回数の増加を緩和し，FIB 探索処理におけるメモリアクセス回数の削減を実現する．平衡木を用いることで，木構造のばらつきを抑え，安定的にメモリアクセス回数を少なくすることができる．提案手法のメモリアクセス回数は，多分木で実装した FIB に比べ約 5.9％，ハシシュテーブルで実装した FIB に比べ約 88.1％に削減することができた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In conventional IP network, an IP router just forwards a packet to another router. Recently, Content Centric Networking (CCN) is paid attention to, where CCN routers do not only forward a packet to another router but it also has a network server function. A CCN router has a forwarding table called FIB (Forwarding Information Base) but its memory access can become a bottleneck. In this paper, we propose FIB data structure for CCN routers which can reduce the number of memory accesses. Our proposed FIB is constructed by effectively utilizing a hash table and a balanced binary-search tree. By using our FIB, the number of memory accesses cannot much increase even if hash collisions occur. Experimental results show that our proposed FIB can reduce the number of memory accesses by 5.9% and 88.1% compared to those implemented by using an n-ary tree and a hash table, respectively.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 研究報告システムとLSIの設計技術（SLDM）; 巻 2015-SLDM-173, 号 45, p. 1-6, 発行日 2015-11-24
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8639
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会