アドホックネットワーク超入門

アドホックネットワークにおける
ネットワークトラフィックに適用した
コンテンツフラッディングモデルの提案
大薮勇輝
[email protected]
慶應義塾大学環境情報学部
本研究の背景

アドホックネットワークの現状
 不安定なネットワーク環境



無線通信の特徴
アドホックネットワークの特徴
アプリケーションの欠如

現在提案されているアプリケーション例


軍事目的
災害時のレスキューなど
日常的には利用されない
Application
Ad-hoc Network Issues
Wireless Issues
本研究の目的

不安定なネットワーク環境を考慮したアプリケー
ション基盤の実現


アドホックネットワークの以下の特徴を考慮
 各ノードの移動性
 移動しながら情報取得
 ネットワークの局所性
 地域的な情報流通
 フラットなネットワーク構造  距離≒ホップ数
通信方式としてフラッディングに注目
提案サービスモデル
アドホックネットワークを利用したロケーションベース広告配信サービス
コンテンツ伝播範囲
送信ノード
配信されるコンテンツ
- お勧めの曲
- 本日のランチ
- お買い得情報
データタイプ
- 映像・音声
- テキスト、画像
提案サービスモデル
コンテンツフラッディングの問題点
ノード密度の高いネットワークにおいて複数のデータフロー
が送信される場合、ネットワークが破綻する

フラッディングによるネット
ワークトラフィック発生要因



隣接する中継ノード数（Nb）
データフロー数（n）
データフローサイズ（XkPk）

本研究のアプローチ


複数データフローに起因する
ネットワークトラフィックの
抑制
対象となるアプリケーション

End-Endのデータ到達性、
データ品質を保障しない
ノード密度
複数データフロー
Network
Congestion
Distribution Range
ノード密度に起因するネットワークトラ
フィックを解決する既存技術

既存技術の利用

Simplified Multicast Forwarding (SMF)
 Multipoint Relay (MPR) set selection algorithm
Classical Flooding
N = 16
MPR Flooding
N=6
複数データフローに起因するネットワークトラフィック
の特徴
データフローの伝播範囲の重複地点において発生


送信ノードによる重複地点の予測・検知の困難性
①
②
③

予測・検知
の困難性
送信ノードが検知・予測の上で可能な対策






ネットワークトポロジの利用
重複地点に配置されるノードからの通知を利用
各送信ノードの伝播範囲（TTL）及び位置情報を利用
伝播範囲の縮小(n)
データフローの送信停止(n)
パケットの送信間隔の変更(p)
パケット送信回数/秒の削減(p)
パケットサイズの削減(x)
伝播範囲全体に影響
中継ノードによる過剰なネットワークトラフィック検知後の
対策が必要
複数データフローに起因するネットワークト
ラフィック抑制に関連する既存技術

データフロー数（


）の削減
Differentiated Service（DiffServ）
 優先度を利用したデータフローの分類
 複数の優先クラス間に対して相対的な転送性能差を設定
データフローサイズ（

）の削減
フレーム内圧縮、階層符号化圧縮を利用する既存技術
 DV Stream Control Proxy


フレーム内圧縮されたパケットを予め設定したレートに応じてサ
ンプリングした後、ユニキャストまたはマルチキャストを利用し
て再送する手法
階層符号化マルチキャスト

複数のマルチキャストアドレス宛に対して、階層符号化圧縮によ
り生成されたレイヤ群を割り当る手法
複数データフローに起因するネットワークトラ
フィックに対する本研究のアプローチ

過剰なネットワークトラフィックの回避



ネットワークトラフィックの常時監視
各データフローに優先度を設定
効率的なフローコントロール


ネットワークトラフィック・優先度に応じた再送制御
ネットワークトラフィック・優先度に応じたサンプリング処理

階層符号化圧縮、フレーム内圧縮技術を利用
送信ノード
a
a
中継ノード
c
b
本研究のアプローチ概要図
受信ノード
コンテンツフラッディングモデルの提案
Adaptive Application Flooding
Adaptive Application Flooding
Originator’s
Originator’s
Originator’s
application
application
A application
B
C
sampled
data
data
Network
Monitoring
Flow Control module
Receiver’s
Receiver’s
Receiver’s
application
application
A application
B
C
Forwarding
Request
Autonomous Flow Management
ユーザアプリケーションに対する機能
Delivery module
Delivery
module
- AFMヘッダの利用 Delivery module
- 複数アプリケーションからの同時利用
- ネットワークトラフィックの常時監視
- 受信アプリケーションへデータフローの転送
- ネットワーク状態に応じた優先制御
- Delivery moduleの受信するデータフロー情報表示
network
ポリシの動的設定
network
-Simplified
ポリシに対応した再送制御
Multicast Forwarding (SMF)
-- ポリシに対応したサンプリング処理
SMFヘッダの利用 Receiver
Originator
Relay
- 中継ノードの選択処理
wireless link
DM FC
Data
DM FC
Data
Autonomous Flow Managementの設計
Adaptive Application Flooding
AFM を構成する
モジュール群
Data sampling
module
AFM core module
ネットワーク状態通知 Network monitoring
module
処理された
パケット
データパケット
ネットワークトラ
フィックの監視
Network
delivery module
HELLOメッセージ
Autonomous Flow Management
AFMヘッダフォーマット
0
8
Sample flag
16
Reserved TTL
32
24
Sample level
Sample mode
Flow option
Sample flag
 サンプリングの可否
Reserved TTL
 優先度
Sample level
 適応されているサンプリングレベル
Sample mode
 適応するパケットサイズサンプリング手法（サンプリングレート
を利用する手法またはセグメントの先頭バイトを利用する手法
の2種類が設定可能）
Flow option
 各サンプリングレベルにおけるサンプリングレートまたは棄却
するデータセグメントの先頭バイトを指定
AFM core moduleによる
優先制御ポリシの動的設定
3種類のネットワーク状態通知
CONGESTED
 サンプリングレベルを上げる
WARNING
 サンプリングレベルを保持
STALE
 サンプリングレベルを下げる
sampling module
ネットワーク状態通知
AFM core module
AFMヘッダ内の情報と
優先制御ポリシの比較
及び処理決定
CONGESTED
STALE
Delivery module
Network monitoring module
level 2
level 1
level 4
level 3
DROP
level 2
level 1
優先制御ポリシ
優先グループ
Reserved TTL = 1
優先グループ
Reserved TTL = 0
Network monitoring moduleによる
ネットワーク状態遷移の検知
CONGESTED
AFM Core moduleへの
ネットワーク状態通知.
WARNING
AFM Core moduleへの
ネットワーク状態通知.
AFM Core moduleが
通知を反映させた場合
ネットワーク
状態遷移
受信するネットワークトラフィックが1秒
以内にTraffic Thresholdを超えた場合
STALE
polling timeが経過するまでに
ネットワーク状態がCONGESTED
にならなかった場合
AFM Core moduleへの
ネットワーク状態通知.
Network monitoring module detects network
congestion by promiscuous mode.
Sampling moduleによるサンプリング処理

AFMヘッダ内 “Sample mode” の参照


サンプリング処理の決定
“Sampling level” 及び “Flow option” の参照

サンプリング処理におけるパラメータの決定
 サンプリングレート or セグメントの先頭バイト
0
8
Sample flag
16
Reserved TTL
32
24
Sample level
Flow option
Sample mode
Adaptive Application Flooding実装

実装言語：C言語
使用ライブラリ：zebra-0.95pre, libpthread, libpcap

実装内容


Delivery module


Flow Control module


Autonomous Flow Management for SMF extension
APIs for user’s application



smf6d
Forwarding Request
Information Request
動作環境

UNIX系OS全般
Autonomous Flow Managementの評価
評価実験環境の構築

Topology Emulator





Cent OS kernel 2.6.11
Xeon 1.8GHz
Memory 1024MB
10 ether port
Nodes










fec0::1 mac darwin kernel 8.2.0
fec0::2 mac darwin kernel 8.2.0
fec0::3 mac darwin kernel 8.2.0
fec0::4 mac darwin kernel 8.2.0
fec0::5 Debian Linux kernel-2.6.9
fec0::6 Cent OS kernel-2.6.11
fec0::7 FreeBSD-5.4
fec0::8 Debian Linux kernel-2.6.9
fec0::9 FreeBSD-5.4
fec0::10 Cent OS kernel-2.6.11
fec0::2
fec0::1
fec0::3
Target
fec0::6
Network
Congested Spot
R
fec0::10
fec0::8
fec0::4
fec0::5
fec0::9
fec0::7
Autonomous Flow Managementの評価
評価実験環境の構築
パケット送信アルゴリズム
while(1)
{
usleep(20000);
send_packet(1000byte);
}
想定するパケット構成
single video or audio frame only in a packet
1 frame
1/2 rate sampling
評価実験
Traffic Thresholdに応じて消費帯域が削減されるか
(A) AFM利用しない
Traffic threshold
625Kbyte
polling time
10sec
Sampling level and rate
level 1: 1/2 level 2: 1/3
level 3: 1/4 level 4: 1/5
(B)AFMを利用する
Reserved TTL（優先度）
fec0::1  1, fec0::2  2,
fec0::4  1, fec0::5  2,
fec0::7  2, fec0::9  1
評価実験
優先グループ毎にサンプリング処理が適用されるか
fec0::1 Mac
優先度  1
fec0::2 Mac
優先度  2
fec0::4 Mac
優先度  1
fec0::5 Debian Linux
優先度  2
fec0::7 FreeBSD
優先度  2
fec0::9 FreeBSD
優先度  1
評価実験
優先度のばらつきによる送受信バイト
に対する標準偏差の変化
ノードRの送信バイトの標準偏差(KB)
ノードRの受信バイトの標準偏差(KB)
40
1200
35
1000
30
800
25
20
600
15
400
10
200
5
0
0
基礎実験
実験１
実験２
実験３
基礎実験
実験１
実験２
実験３
本研究の結論

本研究の成果

アドホックネットワークにおけるネットワークトラフィッ
クに適応するコンテンツフラッディングモデルを実現した

本技術を利用することでアドホックネットワークの特徴を
活かしたアプリケーションが容易に構築可能となった

本技術を利用した複数のアプリケーションが展開されるこ
とによりアドホックネットワークの普及可能性を向上する
ことが出来る
本研究の結論

今後の課題

ネットワーク状態遷移検知に利用される閾値の動的設定

シミュレーション及び実環境における評価実験

本技術を利用するアプリケーションの提案・構築
フラッディングを利用したアプリケーション
Flooding Messenger
(implemented by yaboo and sora)
フラッディングを利用したアプリケーション
距離を利用した広告配信サービス
“HOP数≒どれだけ離れているか”を利用してコンテンツ
再生時に表現を変化させる（音量を変えるなど）
例）音楽配信
Tower Recordに近い方がお勧めの曲が大きく聞こえる
効果：曲を気に入った人は情報元に引き寄せられる
なんか聞こえる…
Distance
この曲いいな！
Tower Record行こう！
結構いい曲かも？
3hop
2hop
1hop
volume

Download Report