講演抄録/キーワード |
講演名 |
2015-12-03 14:35
CCNルータのためのハッシュテーブルと平衡木の併用によるメモリアクセスを削減したFIBの構築 ○島﨑健太(早大)・青木 孝・羽田野孝裕・大塚卓哉・宮崎昭彦(NTT)・津田俊隆・朴 容震・戸川 望(早大) VLD2015-75 DC2015-71 |
抄録 |
(和) |
従来のIPネットワークはユーザ・サーバ間通信を基本とし,サーバに負担が集中する問題がある.加えて,IPルータはユーザから受け取ったパケットを次のルータに横流しするだけであり,ルータは,ユーザが必要とするコンテンツを提供する機能を有していない.従来の転送機能に加え,キャッシュ機能を持つよう機能拡張されたルータにより構築されるネットワークがCCN (Content Centric Networking)であり,次世代ネットワークとして注目されている.CCNルータは,FIBと呼ばれるルーティングテーブルを持つが,FIBのメモリアクセス処理がボトルネックとなる.本稿では,ハッシュテーブルと平衡木を組み合わせたデータ構造を持つFIBを提案する.提案手法は,ハッシュによるテーブル探索を基本とし,ハッシュ値が衝突した際に,平衡木を用いてデータを保持する.こうすることでハッシュ値が衝突した際のメモリアクセス回数の増加を緩和し,FIB探索処理におけるメモリアクセス回数の削減を実現する.平衡木を用いることで,木構造のばらつきを抑え,安定的にメモリアクセス回数を少なくすることができる.
提案手法のメモリアクセス回数は,多分木で実装したFIB に比べ約
5.9%,ハッシュテーブルで実装したFIBに比べ約88.1%に削減すること
ができた. |
(英) |
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. |
キーワード |
(和) |
content centric networking (CCN) / forwarding information base (FIB) / メモリアクセス / ルータ / / / / |
(英) |
content centric networking (CCN) / forwarding information base (FIB) / memory access / router / / / / |
文献情報 |
信学技報, vol. 115, no. 338, VLD2015-75, pp. 243-248, 2015年12月. |
資料番号 |
VLD2015-75 |
発行日 |
2015-11-24 (VLD, DC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2015-75 DC2015-71 |