Click - NICT

平成22年度「新世代ネットワークの構築に関する設計・評価手法の研究開発」の開発成果について
１．施策の目標
本研究課題では、ルーティングを根本原理から見直し、高度情報検索を情報流通の基本機能としてレイヤ３において実現することで、既存のネット
ワークにおいて情報検索に必要とされていた資源を削減し、トータルのエネルギー資源の削減を目指す。
２．研究開発の背景
ネットワークが社会の隅々にまで浸透する新世代ネットワーク時代では、計算機のみならずあらゆる機器がネットワークに接続され、互いに情報を交
換させることになる。また、情報量の爆発的な増加に対して、より効率的かつ確実な情報検索技術への期待が大きい。 また、新世代ネットワーク時
代においては、現在よりはるかに膨大なデータ量を扱うようになると予測され、電力消費量の爆発的な増加は避けられないとされている。そのため、
新しいルーティング機構においても、ネットワークのエネルギー消費を低減させる新しい技術が必要になる。
３．研究開発の概要と期待される効果
高度情報検索を可能な限りルータにおいて処理することで、(1) ユーザ側機器の消費電力削減、(2) 冗長トラヒックの削減によるトラヒック伝送の効
率化、(3) 検索ハードウェアの省電力化によるルータ消費電力の削減を実現し、ネットワーク全体のエネルギー消費を低減させる技術の研究開発を
実施する。高度情報検索をルータで提供し、ルータによる資源発見機構を実現することで、従来常時稼働が必須であったサーバ資源を不要とするこ
とを目標とする。特に少ないコストと消費電力でルータに高度情報検索を実現させることで、ネットワーク全体のエネルギー消費を低減させることが
できる。 加えて、本研究開発で作成した検索ハードウェアおよびパケットバッファは、従来のハードウェアと比較して大幅な大容量化、高機能化を実
現しており、将来ネットワークにおけるトラヒックの増大とアプリケーションの多様化に十分対応できるものである。
ルータによる資源発見機構の実現とエネルギー低減への貢献
z
z
z
高度情報検索をレイヤ3において実現→検索サーバ不要
常時稼働サーバの削減とエネルギー低減
冗長トラヒック削減によるエネルギー削減
新世代ネットワークに資するルータ・ネッ
トワークアーキテクチャによる
ネットワーク全体のエネルギー低減
課題 ウー１ 高度情報検索に対する柔軟性を有するルータアーキテクチャの設計開発
課題 ウー２ 高度情報検索に対する柔軟性を有するルーティングプロトコルの設計開発
課題 ウー３ 高度情報検索においてルータ資源を均一に利用するための検索情報分散配置技術
課題 ウー４ ドメインネームによる名前ベースルーティング実現可能性の検討
課題 ウー７ エネルギー消費量の定量評価および
さらなるエネルギー削減技術の検討
課題 ウー５ 高度情報検索に対応した大容量、高機能、かつ低消費電力を実現するアドレス検索ハードウェアの研究開発
課題 ウー６ 40Gbps かつ大量キューを実現する高速大容量パケットバッファの研究開発
４．研究開発の期間及び体制
平成20年度∼平成21年度（2年間）
ＮＩＣＴ委託研究（公立大学法人大阪市立大学、国立大学法人大阪大学、株式会社ルネサステクノロジ）
1
高度情報検索に対する柔軟性を有するルータアーキテクチャ・ルーティングプロトコルの研究成果
一般化ルーティングプロトコルの
設計
•既存のルーティングプロトコル機
能の抽象化
•任意の可変長アドレスのサポー
ト
•名前空間によるサービスの分別
一般化アドレスによるルーティング情報の交換
多種のレイヤ3アドレスを処理可
能な検索テーブル
•名前空間によりアドレス種類ごと
にテーブルを分割
•次ホップも名前空間を付加
•異なる名前空間を指定すること
でアドレス解決を実現
2
高度情報検索における検索情報分散配置技術および名前ベースルーティングの研究成果
大量のデータ (DNS におけるFQDN で約7億） を各ルータに均一配置
3種類の方法 (Hierarchical Longest Alphabet Match, Hash-based, Hybrid)
物理トポロジと検索トポロジのマッピング
階層化された名前ドメインを階層化トポロジの各レベルに対応づけ
必要ルータに関する評価：現存するルータ資源で名前ベースルーティングは可能
3
高度情報検索に対応したハードウェアの研究開発成果
TCAMの構造にとらわれない省電力検索LSI技術
本研究による新しい検索LSIアーキテクチャ
・例外措置対策にセカンダリーとして小容量TCAMを配置。
現状分析
・20Mb容量のTCAMで約20W 次世代80Mb容量TCAMでは約60Wの電力消費。
・電力消費の80%以上は、Match-lineやSearch-lineというTCAM特有成分に起因。
例外措置を必要とする検索
（全体の１％の格納能力）
テーブル
メインテナンス
TCAM
Request bus
Match-Line
46%
Others
17%
Data Bus
1%
Index
Key
研究課題
se
le
ct
o
r
サブアレイ＃１
比較器
TCAMの性能優位性を維持しつつ
新しい構造（アーキテクチャ）を持つ
検索LSIを研究開発する。
Global-SL
15%
Search-Line
21%
TCAM特有の構造による成分が
80%以上を占める。
Index
Key
se
le
ct
o
r
Index
Key
se
le
ct
o
r
サブアレイ＃２
比較器
・TCAMの物理構造に捉われない
・複雑なアルゴリズムは隠蔽し、
外部からのアクセス、インターフェースは
TCAMと同等
プライオリティ
エンコーダ
メインテナンス経路
サブアレイ＃３
検索経路
比較器
Reply bus
Index Key生成アルゴリズムの決定
・Prefix長に応じ、LSB側からIndex Keyを決定することで滑らかな分布が得られた。
700
600
800
RIPE (308,068)
Uoregon (311,177)
500
WIDE (304,255)
600
RIPE (308,068)
700
Uoregon (311,177)
600
WID E (304,255)
WIDE (304,255)
300
200
Uoregon (311,177)
①入力と
メンテナンス
300
400
300
RIPE (308,068)
500
400
500
400
FPGA実装と評価
・TCAMと等価なインターフェースで検索動作を確認。
200
BGP大容量
ルーティングテーブル
200
100
100
100
0
0
1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3
1 2 3 4 6 7 8 9 0 2 3 4 5 6 8 9 0 1 2 4 5
1 1 1 1 1 1 1 1 2 2 2 2 2
Index Key生成 (1/3)
0
1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3
1 2 3 4 6 7 8 9 0 2 3 4 5 6 8 9 0 1 2 4 5
1 1 1 1 1 1 1 1 2 2 2 2 2
1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3
1 2 3 4 6 7 8 9 0 2 3 4 5 6 8 9 0 1 2 4 5
1 1 1 1 1 1 1 1 2 2 2 2 2
Index Key生成 (2/3)
Index Key生成 (3/3)
更なる問題点、課題
・提案するアルゴリズムに当てはまらない（例外措置が必要）Prefixが約0.8%存在。
ルーティング
テーブル
プリフィックス
総数
②検索リクエスト
今回の研究による検索
ハードウェアの格納数
例外措置を必要とする
プリフィックス数
RIPE
308,068
101,859 x3
2,493 (0.8%)
UOregon
311,176
102,892 x3
2,501 (0.8%)
WIDE
304,255
100,586 x3
2,499 (0.8%)
③検索リプライ
本研究による大容量・省電力検索LSIの電力消費は従来の1/5
＝ 99%*(82%*1/256) + 1%(82%*1) + 18%
＝ 19.3% を示した。
4
高度情報検索に対応したハードウェアの研究開発成果
大量キューを実現する高速・大容量パケットバッファ技術
従来技術の問題点、課題
・制御側と各コンポーネントとの通信が煩雑化するため性能や電力消費を圧迫。
・ネットワークの品質、信頼性向上を目的とするキュー数を確保が困難。
バッファメモリ
の
空き領域管理
可変長フレームと
固定長セグメントの変換
本研究によるパケットバッファ
・パケットバッファ、キューイングについて包括的に管理するアーキテクチャを考案し
LSI間通信によるボトルネックを解消する。
可変長固定長変換
廃棄処
理
SRAM
MMU
SR
AM
I/F
リンクリスト
User
’s
I/F
バッファメモリ
空アドレス情
報
MMU
優先処
理
ポインタ
DRAM
MMU
DR
AM
I/F
Q #0
制御側
Q #1
CPU
I/F
各キューの統計情報
（動的に更新）
Q #N
キューイングFIFOと動的に更新可能な統計情報
試作
・パケットバッファ、キューイングについて包括的に管理するアーキテクチャを考案し
LSI間通信によるボトルネックを解消する。
本研究による包括管理パケットバッファをルータラインカードへ実装
Wt. x2
Rd. /2
PBS
空き
空き
空き
空き
負荷装置
試作したパケットバッファを搭載したルータ
への負荷試験と評価結果
ルータ端末
ルータ端末
128K個のキューをサポートすること。
達成
：試作機で実証
キューに対する優先順位処理、及び廃棄処理のプログラマビリティを提供すること。
達成
：試作機で実証
40Gbpsのワイヤスピードに対して、メモリアクセス遅延によるロスが発生しないこと。
達成
：試作機で実証
5
１．これまで得られた研究成果（特許出願や論文発表等）
新世代ネットワー
クの構築に関する
設計・評価手法の
研究開発
国内出願
外国出願
研究論文
その他研究発表
２
（２）
１
（１）
３
（３）
６
（５）
報道発表
展示会
標準化提案
• 得られた研究成果は国内研究会、国際会議、および論文誌を通じて広く公表している（予定含む）。
• 国内、海外ネットワーク機器メーカに対し、本研究の成果となる新しい検索LSIとパケットバッファを紹介し
LSI製品開発後の採用を目指した活動（継続）中である。
6