全二重通信と半二重通信の混在環境における問題

P2P技術を用いた端末識別子と
位置情報の一貫性の改善に関する研究
九州大学システム情報科学府
情報知能工学専攻
岡村研究室修士2年
林健太朗
目次

研究背景




P2Pネットワークによる管理の提案



提案方式の構成
提案方式の規模適応性
シミュレーション



ロケータ/ID分離ネットワーク
DNSによるロケータ/ID管理方式
DNSによる方式の規模適応性の問題
結果
考察
まとめと今後の課題
2
IPアーキテクチャの限界


IPアーキテクチャは1970年代に開発され標準化された技術
当時は考えられていなかった用途や状況により、様々な問題
が出てきている
(例)移動透過性の問題
対向端末
TCP：通信相手
は1.0.0.1
1.0.0.0/24
2.0.0.0/24
1.0.0.1/24
2.0.0.1/24
3
Future Internet


IPアーキテクチャ上で問題を解決する場合、IPアーキテクチャ
の制限を受ける
また、様々な問題を解決するために開発されたプロトコル間で
冗長や競合が発生しているという問題もある
Future Internet
 既存のネットワークに依存せず，一から新しくこれからのネッ
トワークを考える研究分野
 根本から全体を見直すことで、現在のプロトコル間の冗長や
競合といった問題を一掃する
4
ロケータ/ID分離ネットワーク


Future Internetでは、位置情報(ロケータ)と端末識別子(ID)を
分離した新しいネットワークの研究が行われている
これをロケータ/ID分離ネットワークと呼ぶ


移動透過性、マルチホーム、経路表サイズの増加の解決
本研究における定義
ネットワーク上の端点(位置)を一意に特定する識別子
ロケータ
ID ネットワーク上の端末を一意に特定する識別子



接続するネットワークを変えるとロケータは変わる
2つのネットワークに同時に接続していれば2つのロケータを持つ
IDは端末ごとに固有で、同じIDを持つ端末は2つ以上存在しない
5
ロケータ/ID分離ネットワーク

パケット送信時、通信相手の宛先IDを指定
宛先IDを現在のロケータに変換し配送

IDをロケータに変換する仕組みが重要

移動透過性の解決
対向端末
※IDもIPアドレス
TCP：通信相手は
ID:A.B.C
1.0.0.0/24
2.0.0.0/24
送信の流れ
ID宛てのパケットを作成
宛先IDを現在のロケータに変換
ロケータを基に配送
ID：A.B.C
Loc:1.0.0.1
ID:A.B.C
Loc：2.0.0.1
宛先IDの端末が受信する
6
既存の提案プロトコル

ロケータ/ID分離ネットワークを実現するプロトコル



LISP (Locator/ID Separation Protocol)
HIP (Host Identity Protocol)
それぞれの研究では、DNS(Domain Name System)を用いた
ロケータ/ID管理方式が提案されている
DNS
 インターネットを用いた階層的なデータベースシステム
 現在はホスト名とIPアドレスの対応を管理するために使われ
ている
 問い合わせを受けたホスト名やIPアドレスに対応する情報を
返答する
7
DNSによるロケータ/ID管理方式

DNSサーバ






木構造のサーバ群によりロケータ情報を分散的に管理する
木構造は、右側を上位層とするIDの階層構造に基づいている
あるDNSサーバは、負荷分散と耐障害性向上のために、マスターサー
バとスレーブサーバに分かれる
スレーブサーバはマスターサーバの情報をコピー
サーバの更新はマスターサーバだけで済む
root
DNSキャッシュサーバ


サーバ
クライアントからの問い合わせを受け
DNSサーバへ問い合わせを行う
キャッシュ(問い合わせた情報を一時的
に保持)を持つ
ID：△.B.Cの
ロケータを管理
C
B
A
DNSサーバ
8
DNSによるロケータ/ID管理方式

問い合わせの流れ
DNSサーバ
root
サーバ
ID：A.B.C.Dの
問い合わせ
D
DNS
キャッシュサーバ
C
B
マスター
ID：A.B.C.Dの
問い合わせ
DNS
クライアント
ゾーン転送
スレーブ
9
規模適応性の問題

頻繁にアクセスを受ける移動端末のロケータ/ID管理


キャッシュサーバは移動端末のロケータをキャッシュしない
キャッシュがないためロケータを管理するサーバへアクセスが集中
Bネームサーバ
ID：A.B.C.D
100[回/s]アクセス
クライアント
マスターサーバ
ロケータ更新
ゾーン転送
キャッシュ
サーバ
スレーブサーバ
100[回/s]問い合わせ
100[回/s]問い合わせ
10
P2Pネットワークによる管理の提案

DNSによるロケータ/ID管理は規模適応性の問題がある



P2Pネットワークによるロケータ/ID情報の管理を提案



頻繁にアクセスを受ける移動端末を管理する、特定のサーバへアクセ
スが集中する
負荷分散のためにスレーブサーバを増設しても、更新にかかる処理が
増大
優れた規模適応性を持つ
頻繁にアクセスを受ける移動端末がある場合にも、問題が起きない
研究目的：DNSによるロケータ/ID管理方式の規模適応性の
問題を提案方式によって解決する
11
提案方式の構成

割り当てサーバ



各サブネットワークに設置
そのネットワークに接続する端末に対してロケータを割り当て
LI(ロケータ/ID)ノード




ロケータとIDの対応情報を保持するサーバ
WAN
端末からのロケータ/ID情報登録を
P2Pネットワーク
受け付ける
LIノード
端末からのロケータ
問い合わせも受け付ける
他のLIノード同士で
ロケータ/ID
情報登録
P2Pネットワークを構築
割り当てサーバ
ロケータ
割り当て
LAN
端末
割り当てサーバ
割り当てサーバ
LAN
LAN
12
ロケータの問い合わせ

LIノードはP2Pネットワークに対して問い合わせをフラッディン
グ


フラッディング：送信元ノード以外の隣接する全ノードに対してコピーを
送信する操作。既に受け取った問い合わせを再度受け取った場合は
それを破棄する
問い合わせ情報は経由したLIノードのロケータを順番通り記
録しておく
LIノード
G
D
C
ロケータ登録
H
K
F
A
問い合わせ
ID：K1のLoc？
B
J
E
経由ノードＡ，Ｂ，Ｅの
ロケ－タを記憶
ID：K1
Loc：100
問い合わせ
の目的地
13
ロケータの返答



自身宛ての問い合わせをLIノードが受け取ったならば、問い
合わせ情報が経由したLIノードを逆にたどって返答を転送す
る
中継を行ったLIノードは返答内容のロケータ/ID情報および返
答を転送した隣接ノードをキャッシュする
キャッシュのTTLは端末が指定しておく
キャッシュ
LIノード
G
D
C
H
ＩＤ：K1 – Loc：100
転送先のロケータ：J
K
F
A
返答情報
ID：K1
Loc：100
B
E
J
ID：K1
Loc：100
キャッシュ
ＩＤ：K1 – Loc：100
転送先のロケータ：E
14
ロケータの更新




端末は割り当てサーバから新しいロケータを割り当てられると、それを決
まったLIノードへ登録する
登録を受けたLIノードは、キャッシュを参考に返答を転送した隣接ノードへ
更新情報を転送する
各LIノードが更新情報を隣接ノードへ転送することで全てのキャッシュが更
新される
キャッシュのTTLは更新しない
LIノード
G
D
C
ロケータ更新
100→200
H
K
F
A
更新情報
ID：K1
Loc：200
B
E
J
ID：K1
Loc：200
キャッシュ更新
ＩＤ：K1 – Loc：200
転送先のロケータ：E
15
規模適応性について

あるサーバへ問い合わせが集中する場合



更新について





最初はキャッシュが存在しないため、アクセスが集中する
しかし時間が経ち、キャッシュが広がると、アクセスは分散される
キャッシュの更新時における操作は、返答を転送した隣接ノードへの
転送のみであるため、オーバーヘッドが小さい
キャッシュは、問い合わせをした端末に向けてのみ作成されているの
で、アクセスのない端末に向けて無駄な更新をしない
よって、頻繁に更新が行われるIDを多く管理することができる
以上の事から、提案方式は優れた規模適応性を持つと予想
される
これをシミュレーションによって示す
16
シミュレーション設定

ネットワークの設定


サーバの設定





日本地図上で１辺10[km]の正方形をひとつの
ネットワークエリアとする
各県に一つずつ計47個，
DNSによる方式であればスレーブサーバ，
提案方式であればLIノードを設置
DNSサーバは，DNS NOTIFY機構に対応
LIノードは各ノード４つのリンクを持つと仮定
提案方式におけるキャッシュのTTLは1時間
移動端末の設定



毎秒a回アクセスを受ける
b[km/h]のスピードで直線に日本を縦断
ネットワークエリアをまたぐ度に接続を切り替え
17
結果：シミュレーション１
シミュレーション１：

移動端末へ100[回/s]アクセ
スがある時の、更新先サー
バが1分間に受ける問い合
わせ頻度の推移


移動端末からの問い合わせ
頻度に対して、どちらの方式
も問い合わせが分散されて
いる
提案方式では、最初の1秒の
み頻度が高い
1000
移動端末
問い合わせ頻度

100
更新元サーバ(提案方式)
10
更新元サーバ(DNS)
1
1
4
7
10 13 16 19 22 25 28 31
時間[秒]
18
結果：シミュレーション2
シミュレーション２：

シナリオ別の、1回の更新にお
けるシステム全体の更新情報
転送回数
シナリオA：全国から分散的
に100[回/s]アクセス
シナリオB：北海道からのみ
100[回/s]アクセス
シナリオC：端末へのアクセス
がない
シナリオA
シナリオB
60
DNS方式
50
更新情報転送数

提案方式
40
30
20
提案方式：値0
10
0
シナリオA シナリオB シナリオC
1
19
考察

シミュレーション１



シミュレーション２




移動端末へのアクセスに対し、両方式ともにアクセスが分散されてい
る
さらなる負荷分散のためにはサーバを多く設置することが重要
DNSによる方式は更新に対するオーバーヘッドが大きい
特に、端末へのアクセスがない場合にも更新処理を行っている
提案方式は問い合わせ元に対してキャッシュを作成、更新するためオ
ーバーヘッドが小さく、ノード数を増加させても問題がない
以上の結果から、サーバを増設しても更新に対するオーバー
ヘッドの小さい提案方式は、DNS方式よりも優れた規模適応
性を持つと言える
20
まとめと今後の課題

まとめ




DNSによるロケータ/ID管理方式のスケーラビリティの問題
P2Pネットワークを用いたロケータ/ID管理方式の提案
シミュレーションにより提案方式の規模適応性を示した
今後の課題

NS３(シミュレーションプログラム)を用いて、提案方式をより詳細にシミ
ュレーションする





ノード数を増やした時
問い合わせから返答を受けるまでの時間
成功率
問い合わせの分散度合い
更新を完了させるまでの時間
21

Download Report