RED 方式の性能向上のための最適パラメータの研究 106159 原田 学

平成 14 年度卒業発表会（日本大学工学部情報工学科）
A-3
RED 方式の性能向上のための最適パラメータの研究
Research on the optimal parameters for the improvement of RED performance
106159
１
原田
［竹中研究室］
はじめに
近年、インターネット利用者の急速な普及によるトラ
ヒックの増加とともに、インターネットの音声、画像メ
ディアの利用によるマルチメディア化に伴い、QoS (Quality of Service) 保証の実現が重要課題となっている。
また、インターネットの輻輳防止やユーザ間での公平な
利用を目的として、ルータにおける輻輳制御が提案され
るとともに実装されて来ている。こうしたルータの制御
方式の中では、RED (Random Early Detection) 方式[1]
が代表的である。しかし、RED 方式では、その制御パラ
メータが静的に設定されており、インターネットの動的
なトラヒック変動に必ずしも最適にチューニングされて
いるとはいえない。この問題に対処するため、動的なト
ラヒック変動に適応する dt-RED (RED with dynamic
threshold control)方式[2]が提案されその性能が評価さ
れている。しかしながら、dt-RED 方式のチューニング
パラメータの数も多く、その調整もそれほど容易ではな
い。
本研究は、RED ルータの性能の向上を図るため、その
輻輳制御パラメータのスループット特性に与える影響を
明確にするとともに、ネットワーク環境の変動に対して
安定した性能を保証するパラメータ設定法の確立を図る
ことを目的としている。
２
学
ルータにおける輻輳制御方式
２．１
RED 方式のアルゴリズム
RED 方式は、平均キュー長を用い確率的なパケット廃
棄を行うことでバースト的(連続的)なパケット廃棄の発
生を防止する。これにより、従来の DT(Drop Tail)方式
において発生するバースト的なパケット廃棄を防止する
ため、TCP コネクションのスループット、及び公平性の
向上が期待できる。
RED 方式 における平均キュー長( q )は、パケット到
着毎にローパスフィルタの重み係数(wq)を用い、現在の
キュー長(ｑ)から式(1)より求める。これにより、平均キ
ュー長の急激な変動を緩和する。
q ←(１−ｗｑ) q ＋ｗｑ･ｑ
(１)
この平均キュー長( q )を最大閾値( max th )、最小閾値
( min th )と比較し、到着パケットに対して以下のような
処理を行う。
(1)
q ≤ min th ならば到着パケットをバッファに全
て格納する。
(2)
min th ≤ q ≤ max th ならばパケット廃棄確率
以下の式(2)と(3)を用いて Pa を計算し、その確率
で廃棄する。(count:は廃棄確率を count の増加と
ともに緩やかに増大させるために使用される。)
Pb ←
q− max th
max p
max th − min th
(２)
Pa ←
(3)
２．２
Pb
1 − count × Pb
(３)
max th ≤ q ならば到着パケットを全て廃棄。
dt-RED 方式のアルゴリズム
dt-RED 方式は文献[2]で提案された RED 方式の改良
方式であり、ルータの輻輳状況により maxth、minth お
よび maxp を変動させる。
(1) maxth の制御
平均キュー長( q )が maxth に近づいた場合、maxth を
増加させ、バースト的なパケット廃棄を防止し、輻輳を
回避する。一方、平均キュー長( q )が minth に近づいた
場合、maxth を減少させ平均キュー長を短くすることに
よって、全体のパケット廃棄率を大きくし、平均キュー
長を短くすることを目的としている[2]。
(2) minth の制御
平均キュー長( q )が minth より小さい場合には、minth
を増加し、リンク利用率の向上を図る。リンク利用率が
増大すると minth を減少させ、確率的なパケット廃棄を
行い、輻輳を回避させる。
(3) maxp の制御
maxp の増加は、maxth の値を大きくしても平均キュ
ー長の増加を防止できない場合に行う。これにより、パ
ケット廃棄確率を増加させ、平均キュー長の増加を防止
し、輻輳の回避を行う。maxp の減少は、minth の値を
大きくとってもリンク利用率の低下を防止出来ない場合
に行い、パケット廃棄確率を小さくしリンク利用率が向
上する。
３
従来研究と問題点
これまでの研究では、フロー間の公平性に特に着目し、
シミュレーションにより、DT 方式と RED 方式の性能の
評価が行われている[2]。この中で、ネットワークの環境
と輻輳制御パラメータが適応している場合、フロー間の
公平性が保たれる事が示されている。しかし、ルータの
バッファサイズや TCP フロー数が変化した場合、固定の
輻輳制御パラメータを用いた場合では、必ずしもフロー
間の公平性を保証できない。
また文献[2]では、dt-RED 方式と、環境ごとに maxth
を変動させた RED 方式との比較評価が行われている。
この中で、DT 方式の性能を確認し、dt-RED 方式は、環
境ごとに maxth を変動させた RED 方式と同等以上の性
能がでることが示めされている。
しかし、dt-RED 方式は、2.2 で述べたように、多くの
制御パラメータのチューニングが必要であり、実際の運
用ではその調整が困難であることが想定される。また、
制御パラメータが動的に変動することより、パケット廃
棄確率も変動することになる。これにより、dt-RED 方
式では高い公平性を期待することが出来ないと推測でき
る。
そこで、本研究では、様々なネットワーク環境で、RED
方式のパラメータがどのような影響を与えるかを明らか
平成 14 年度卒業研究発表会 A-3
４
NS シミュレータによる評価
４．１ 評価対象パラメータ
シミュレーションによる事前評価により、文献[1]に示
された RED 方式の基準値パラメータでは、必ずしもフ
ロー間の公平性を実現することはできないことを確認し
た。しかし、この評価よりルータにおけるバッファサイ
ズに応じて maxth の変動させることにより、RED 方式
の公平性が向上することを確認できた。
そこで、本研究では maxth とバッファサイズの関係に
着目して RED 方式の性能評価を行う事にする。
４．２
シミュレーション構成
サイズに応じて maxth を変動させた RED 方式の公平性
が高いことがわかる。またその中でも、maxth をバッフ
ァサイズの 80%に設定すると公平性が高い。
1
fairness index
にし、ネットワーク環境の変化に対応できるパラメータ
設定法を明らかにすることを研究のねらいとしている。
0.95
0.9
0.85
0.8
0.75
100
maxth 15
図．２
シミュレータには、カリフォルニア大学バークレイ
校で開発されたネットワークシミュレータ ns-2 1b9a[3]
を用いる。
TCP Source １
1000
10000
buffer size
maxth 30
maxth 80
公 平 性 の 評 価 (BW=1.5[Mbps], 伝 播 遅 延 時 間
=4[msec],buffer size=100,1000,10000)
ボトルネックリンク帯域が広帯域になると、maxth に
関係なく公平性が高いことがわかる。また、この環境下
でも公平性の値が小さな変動であるが、バッファサイズ
の 80%に設定した maxth の RED 方式の公平性が高い。
Buffer B（packetｓ）
fairness index
1
100（Mbps），2（msec）
Drop Tail／ RED
Router
Destination
TCP Source ２
B W（ Mbps），
ｔ（msec）
100（Mbps），2（msec）
0.99
0.98
0.97
0.96
0.95
100
100（Mbps），2（msec）
1000
buffer size
maxth 15
maxth 30
10000
maxth 80
TCP Source 100
ＢＷ：ボトルネックリンクの帯域 ｔ：伝搬遅延時間
RED：初期のパラメータ
max_th＝１５（packets），
min_th=５（packets）
図.１:
max_p＝0.1，w_q＝0.002
ネットワークトポロジー
TCP Source を 100 本設置し、それぞれ 100Mb/s の送信レ
ートと 2msec の伝播遅延時間としたものをルータに接続する。
ルータから Destination へのリンクをボトルネックリンクとし、そ
の帯域と伝播遅延時間の値を変化させることにより、様々な
環境を想定する。この環境で、RED 方式の閾値である maxth
を基準パラメータ値 15 からバッファサイズの 30％、80％と変
動させていき maxth とバッファサイズの関係を評価する。
４．３
公平性の評価基準
公平性の評価指数として Fairness Index 値[4]を用い
る。Fairness Index 値は以下のように定義される。n を
フロー数、 xi (1 ≤ i ≤ n ) を n 個の ack 数とする、n 個
のサンプル値の公平性をあらわす指標
される。
(∑ xi )
n
f =
f
i =1
n
f
は以下で定義
2
n∑i =1 xi 2
図．３ 公平性の評価(BW=15[Mbps],伝播遅延時間
=4[msec], buffer size=100, 1000, 10000)
（1 ≤ i
≤ n）
(４)
は０以上１以下の値を取り、１に近いほど公平性が高
い。
４．４ 評価結果
ボトルネックリンク帯域が 1.5Mbps の環境では、既
存値パラメータの RED 方式の公平性より、各バッファ
ボトルネックリンク帯域に関係するネットワーク環境
では、制御パラメータである maxth をバッファサイズの
80%に固定することにより、高い公平性を実現すること
が確認できた。
５ むすび
RED 方式のチューニングパラメータである maxth を、
バッファ数に比例してある程度大きくすると既存の
RED 方式より公平性が向上することを明らかにした。そ
の中でも、maxth をバッファサイズの 80%に設定するこ
とが有効的である。
今後は、RED 方式の他のパラメータについても評価す
るとともに、様々なネットワーク環境で評価を行い、実
環境で用いる事のできる RED 制御パラメータを明らか
にする必要がある。
参考文献
[1]Sally Floyd and Van Jacobson
Random Early
Detection Gateways for Congestion Avoidance
IEEE/ACM Transactions on Networking, V.1 N.4,
August 1993
[2]長谷川 剛、他著
バックボーンルータにおけるＲ
ＥＤの動的閾値制御方式
電子情報通信学会技術研究
報告(NS2001−11)、April2001
[3]The Network Simulator -ns-2 http://www.isi.edu/ns
nam/ns/
[4]R.Jain,”throughput fairness index :An explanation,”
ATM Forum Contribution 99-0045,February1999.