09.2.18

新しいルーティング方法の必要性
 IP の問題点

Name-based Routing for
Future Networks

解決 IP アドレスの構造 : ルーティングテーブルの肥大
 ID/Locator の非分離 : 端末が ISP に依存

実現

 高度の情報検索

次世代ネットワークにおける名前にもとづくルーティング 資源にもとづくルーティング

新しいネットワークアーキテクチャが要求される大阪大学 大学院情報科学研究科
情報ネットワーク学専攻 村田研究室

レイヤー3におけるドメインネームルーティング

黄 恵聖 (HWANG, Haesung)

IP: Internet Protocol
ISP: Internet Service Provider
2009.2.18

研究の目標と評価指標

2008年度 修士論文発表会

1

システムアーキテクチャ
osaka-u.ac.jp

ドメインネームルーティングの実現可能性を明らかにする
ネットワーク資源

ハードウェア資源

システムアーキテクチャ
ドメインネームの登録ルーティングテーブルの交換
パケット転送ミラーリング
故障対応

 TCAM を利用したドメイ
ンネームの分散配置方法

3rd level domain
Top level domain.b.com
3rd level domain

Upperlevelcom.*************
net. *************
jp. **************

port P
port P
port P

Same
leveljp.ac.osaka-u.*****

port X

Lower
level

jp.ac.osaka-u.ist.*** port A

R3
A

2

Router R4’sRouting Tablecom.** port X
net.**
port Y
jp.**** port A

jp.**
net.**
com.*

Z

R4 A

V

R2 Q A X
R1 A

computer.ist.osaka-u.ac.jp
2009.2.18

2009.2.18

2008年度 修士論文発表会

3 FQDN にハッシュ関数をかけ，当てはまる ID を持つルータに分散する方法

R5com.******* port Q
net.******** port Q
jp.********* port Q
com.yahoo.** port AA 階層型最長アルファベットマッチ (Hierarchical longestalphabet match) 最長プレフィックスマッチに着想を得た方法

 ハイブリッド分散 (Hybrid Distribution)

com.************ port Q
ドメインネームは，
biz.yahoo.com
net. ************ port Q
IPjp. アドレスより長い可変長************* port Q⇒
ルーティングテーブルをjp.ac.***********
port X
jp.ac.osaka-u.**** port A
分散して格納する必要がある
TCAM
2008年度 修士論文発表会

 必要なルータ台数は最も少ないが非現実的

 TCAM の特徴を最も利用しているがルータ台数は最大

Router R2’s Routing TableX

 インターネットは Abilene-inspired topology に類似な形状
 Top レベルドメインネームルーティング情報 ⇒ バックボーンルータ
 2nd レベルドメインネームルーティング情報 ⇒ ローカルゲートウェイ 3rd レベルドメインネームルーティング情報 ⇒ エッジルータ

 ハッシュ分散 (Hash-based Distribution)

port Z
port V
port A

Router R5’sRouting Table

QP.a.jp

ドメインネームの分散配置方法

Router R3’sRouting Table

YX.c.jp.x.a.jp

ドメインネームルーティング
Router R1’s Routing Table.jp

2nd level domain

ハッシュ分散階層型最長アルファベットマッチ
ハイブリッド分散

2008年度 修士論文発表会

Top level domain.net.com

TCAM: Ternary Content Addressable Memory
2009.2.18

2nd level domain ハッシュ分散と，階層型最長アルファベットマッチの利点を利用した方法
 閉じたネットワークでのルーティングが可能，均等な分散FQDN: Fully Qualified Domain Name
4

2009.2.18

2008年度 修士論文発表会

51

09.2.18

最長アルファベットマッチ

ルータの使用率と必要な台数
ルータ

com.google.*
Port X
kr.ac.knu.*
Port Yjp.ac.osaka-cu.*
Port Ajp.ac.osaka-u.es.* Port B
jp.ac.osaka-u.e.*Port C?
ルータ
nal.ics.es.osaka-u.ac.jp

01*****

A~C

11000**

D~G

11001**

H~O

1101***

P~S

11100**

T~W

11101**

X~Z

1111***

2009.2.18

jp.a* ~ c*jp.-*
~ [0-9]*OtherTLDs

jp.d* ~ g*jp.t* ~ w*
jp.h* ~ o*

1.E+08

Number of necessary routers

Number of domain names

6301

60190112011501

1801

1151 301 451 601 751 901 1051 1201 1351

2009.2.18

Router ID (Number of routers)

2008年度 修士論文発表会

7

まとめと今後の課題

分散方法

ルータ台数

Hash-based Distribution

597

Hierarchical longest
alphabet match

1396

Hybrid Distribution

952

 まとめ
 ドメインネームルーティングの実現可能性を評価
 ネットワーク資源 :1.E+09

現存すルータ台数 : 約 228,260台†

Hybrid distribution
Hierarchical longest alphabet match

Number of necessary routers

Threshold=1
Threshold=0.75
Threshold=0.5

Router ID (Number of routers)

Hash-based distribution

100.5
0.25
01

Hybrid distribution

1.E+07Threshold=1
Threshold=0.75
Threshold=0.50

2008年度 修士論文発表会

1.E+060.75

0.5

ASCII code

Hierarchical longest alphabet match

11.E+05

0.75

0.25

分散方法の比較と閾値によるルータの台数
100

1jp.x* ~ z*jp.p* ~ s*Hybrid Distribution

1Utilization

Hyphen, digit(router memory size: 1台のルータには18 Mbit TCAM が10個あると仮定)

Hierarchical longest alphabet match

Utilization

TCAM cell

Utilization = number of entries in a router x 180 bits
router memory size0

<ルーティングテーブル>
Content• 閾値 (threshold) : 現存するドメインネームを格納できる最大限• 使用率 (utilization) : ルータに格納された比率

1

ドメインネームの登録，ルーティングテーブルの交換，パケット転送，ミラーリング，故障対応の方法を提案⇒ 将来のドメインネーム追加に対して拡張性がある
 ハードウェア資源 : ドメインネームルーティング情報を複数のルータに分散する3つの方法（ハッシュ関数，最長アルファベットマッチ，ハイブリッド）を提案⇒ 現存するルータの台数より2桁少ない
 今後の課題

3次スプライン補間法(cubic splineinterpolation) によるカーブ
フィッティング ドメインネームエントリのアップデートによる評価
 エントリの増加率
 新しく追加されるドメインネームの追加率† A. Lakhina, J. W. Byers, M. Crovella, and I. Matta, “On theGeographic Location of Internet Resources,” IEEE Journal on Selected
Areas in Communications, vol. 21, pp. 934-948, August 2003

2009.2.18

2008年度 修士論文発表会

8

 DNS サーバを無くすことによる効果の評価
2009.2.18

2008年度 修士論文発表会

9

ご清聴ありがとうございました2