情報通信技術論/インターネット工学

キューの役割と仕組み
演習第4回
情報通信技術論
インターネット工学
情報通信技術論/インターネット工学
キュー(バッファ)とは

パケット交換 = 蓄積交換
ルータ
キュー
(バッファ)
– パケットはルータのバッファに一時記憶される


パケットは待ち行列(キュー)を作りながら格納される
(Drop Tailでは)先に入ってきたパケットから順に転送される
– キューが一杯になるとパケットが廃棄される
1
情報通信技術論/インターネット工学
ノード、キュー、リンクの関係
パケット
ノード0



キュー
(バッファ)
ノード2
リンク
帯域(幅)
ノード
ノード3
ノード4
(NS2では)全てのリンクにキューがある
パケットは必ずキューを通ってからリンクに送出される
出力レートに対して入力レートが大きい(高速な)場合、差分がキューに溜まる
– トラフィックが一時的に増加した場合に対処可能
– キューサイズを超えるとパケットが破棄される
2
情報通信技術論/インターネット工学
パケットの流れ
40Mbps
6ms
ノード0
なぜ?
84ms
62ms
22ms
+
r
+
r
+
r
4Mbps
20ms
ノード2
0.062
0.062
0.0682
0.0682
0.1302
0.1522
0.1522
0.1522
0.1584
0
0
0
2
2
2
3
3
3
2
2
2
3
3
3
4
4
4
cbr
cbr
cbr
cbr
cbr
cbr
cbr
cbr
cbr
1000
1000
1000
1000
1000
1000
1000
1000
1000
40Mbps
6ms
ノード3
-------------------------------------------------------
0
0
0
0
0
0
0
0
0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
4.0
4.0
4.0
4.0
4.0
4.0
4.0
4.0
4.0
ノード4
62
62
62
62
62
62
62
62
62
62
62
62
62
62
62
62
62
62
あるパケット(ID=62)の流れに注目 (% awk ‘$12==62’ out.tr)
※実験1-1-(b)で帯域を4Mbpsにした場合 3
情報通信技術論/インターネット工学
パケットの転送に要する時間
ノード0
40Mbps
6ms
ノード2
4Mbps
20ms
ノード3
40Mbps
6ms
ノード4
ノード2からノード3にパケットが転送されるまでにかかる時間
62ms
2ms
20ms
キューでの
→ (キュー長)×(パケットの送出にかかる時間)
待ち時間
※キュー長: キューに保持されているパケットの数 (この例では31)
+
パケットの送出に
→ (パケットサイズ[bytes])÷(リンクの帯域[Mbps])
かかる時間
1000[bytes]
4[Mbps]
+
ノード間の伝送に → (リンクの遅延)
かかる時間
計 84ms
4
情報通信技術論/インターネット工学
パケットの流れ(ドロップされるパケット)
ドロップ
40Mbps
6ms
ノード0
ノード2
4Mbps
20ms
ノード3
40Mbps
6ms
ノード4
一度キューに入って(入ろうとして)からドロップされる
+
r
+
d
0.063
0.063
0.0692
0.0692
0.0692
0
0
0
2
2
2
2
2
3
3
cbr
cbr
cbr
cbr
cbr
1000
1000
1000
1000
1000
-------------------------------
0
0
0
0
0
0.0
0.0
0.0
0.0
0.0
4.0
4.0
4.0
4.0
4.0
63
63
63
63
63
63
63
63
63
63
あるパケット(ID=63)の流れに注目 (% awk ‘$12==63’ out.tr)
※実験1-1-(b)で帯域を4Mbpsにした場合
5
情報通信技術論/インターネット工学
実験1-2
0
4
CBR/UDP
40Mbps
キューサイズ:
2
帯域: Bw
40Mbps
B
3
(ボトルネックリンク)
1

5
以下の関係性を考察
–
–
–
–
送信トラフィックレート
ボトルネックリンクの帯域
キュー長
キューから廃棄されたバイト数
6
情報通信技術論/インターネット工学
【補足】 実験1-2の実行方法
% ns kadai1-2.tcl 1.0Mb 32
(Bw)
(B)
– out.tr out.nam out.queue out.udpが生成される
% gnuplot
gnuplot> l “kadai1-2.gp”
gnuplot> …
gnuplot> set term post color
gnuplot> set output “graph.ps”
gnuplot> rep
gnuplot> q

フォーマット(見た目)が気に入らない場合には、kadai1-2.gpを
適当に修正してください。
7
情報通信技術論/インターネット工学
【補足】 out.queueの中身

out.queue (キューのトレースファイル)
–
–
–
–
–
–
–
–
–
–
$1 : 時刻
$2, $3 : キューの場所(リンク)
$4 : キューに溜まっているデータ量(キュー長) [bytes]
$5 : キューに溜まっているパケット数 [packets]
$6 : キューに到着したパケット数 [packets]
$7 : キューから送出されたパケット数 [packets]
$8 : キューから破棄されたパケット数 [packets]
$9 : キューに到着したデータ量 [bytes]
$10 : キューから送出されたデータ量 [bytes]
$11 : キューから破棄されたデータ量 [bytes]
※ $5~$11はシミュレーション開始時からの累積値
8
情報通信技術論/インターネット工学
【補足】 out.udpの中身

out.udp (UDPのトレースファイル)
– $1 : 時刻
– $2 : 送信トラフィックレート [Mbps]
– $3 : ボトルネックリンクの帯域 [Mbps]
9
情報通信技術論/インターネット工学
グラフの例(注目ポイント)
31
※実験2でBwを1.0Mbps、Bを32kbytesにした場合
10