〈一般研究課題〉 パケット破棄確率の非線形化がTCP/REDに与える影響
助 成 研 究 者

中京大学

髙坂拓司

パケット破棄確率の非線形化がTCP/REDに与える影響髙坂 拓司（中京大学）

Effect of the packet drop probability with a nonlinearity on
TCP/REDTakuji Kousaka(Chukyo University)

Abstract：
Nonlinear Random Early Detection (RED) is an algorithm applying the nonlinear function to thepacket drop probability of TCP/RED and can change the nonlinearity continuously. In addition, thehigh throughput achieved by the nonlinear RED is confirmed by using Network Simulator-2 (NS-2).
This study aims to clarify the effect of the packet drop probability with a nonlinearity on thenonlinear RED. We propose a first-order discrete model for the nonlinear RED. By calculating thebandwidth utilization with various TCP senders using NS-2, we clarify the effect of the number of
TCP senders on the traffic loads. Moreover, we compare the average queue size in a router of theNS-2 and that of the model with various TCP senders and nonlinearities of the packet dropprobability. Our results show the reproducibility of the model regarding the average queue size.
1．はじめにネットワークにおける渋滞 (輻輳) は通信性能を大幅に低下させる要因の1つであり，通信端末からルータへ多数のアクセスが集中した際に生じる．近年，ネットワークの高帯域化およびバッファ容量の増加に伴い多くのパケットを同時に送信可能となり，高スループット化が実現されている．
しかし，新たな輻輳の要因として，バッファにおけるパケットの転送待ち時間(キューイング遅延)の増加が広く知られている．このように，輻輳の要因はネットワーク技術の発達に伴い変化するた－ 203 －

め，輻輳制御は通信性能の向上に必要不可欠である．以下，輻輳制御について考える．
Transmission Control Protocol (TCP) は通信の信頼性を保証するための規約であり，輻輳制御機構を持つ．また，現在に至るまで様々な輻輳制御法が提案されており，パケットロスに基づくLoss-basedの輻輳制御法が広く普及している．しかし，ルータにおけるバッファ容量が大きいネットワークでは，パケットロスが発生せずキューイング遅延が増加するため，Loss-basedの輻輳制御法単体での十分な制御は困難である．この問題に対して，Active Queue Management (AQM) [1]はルータ内のキュー長を積極的に管理するため，キューイング遅延の制御に効果的である．特に，Random Early Detection (RED) [2]はAQMの代表的な手法の1つであり，平均キュー長に基づく乱数的なパケット破棄により過剰なキューイング遅延の増加を抑制する．また，REDは一般的なLoss-basedの輻輳制御法 [3]と比べ，迅速な輻輳回避動作が可能であり，スループットの公平性においても高い性能を示すことが報告されている．
REDの制御性能は，パケット破棄確率に関する3つの閾値に強く依存するため，適切な閾値の設定が必要である．しかし，ネットワーク環境やトラフィックの状態により適切な閾値は異なるため，如何なる状況においても高い通信性能を実現することは困難である．また，従来のREDにおけるパケット破棄確率は平均キュー長に対して線形特性を示す．一方，高スループット化に最適なパケット破棄確率の特性は明らかになっていない．これらの課題を解決するため，パケット破棄確率に非線形関数を適用したRED (非線形RED) [4-7]が提案されている．文献 [4-7]はネットワークの研究および開発に広く利用されているNetwork Simulator-2 (NS-2) [8]を用いて，非線形REDによる高スループット化を示している．しかし，非線形REDによる高スループット化のメカニズムに関する報告は皆無であり，最も高スループットとなる非線形特性の強度を用いた設計は困難である．
先の研究報告[9]では，パケット破棄確率の非線形性が通信性能に及ぼす影響を調査するため，非線形特性の強度を連続的に変化可能なパケット破棄確率を用いた非線形REDを提案した．また，
NS-2を用いた通信シミュレーションを行い，非線形REDにおいて非線形性を強めるほど通信性能は向上する一方，過剰な非線形性はスループットを大幅に低下させることを明らかにした．
そこで本研究では，非線形REDによる高スループット化のメカニズムを解明するための第一歩として，ルータ内の平均キュー長に注目した1次元離散非線形REDモデルを提案する．はじめに，
NS-2を用いてTCP接続台数に対する帯域利用率を計算し，接続台数がネットワークの負荷に及ぼす影響を明らかにする．次に，NS-2および提案モデルを用いて，TCP接続台数と非線形特性の強度を変化させた際の平均キュー長に関する時系列波形を計算する．また，NS-2と提案モデルの計算結果を比較し，提案モデルの有効性を検証する．最後に，提案モデルを用いて非線形特性の強度に対する固定点解析を行い，非線形REDの力学的性質を調査する．
2．解析対象2.1

非線形RED

本研究で取り扱う非線形 RED [9] は，ルータ内の平均キュー長qから決まるパケット破棄確率pにより輻輳を制御する．また，平均キュー長は指数加重移動平均を用いて計算し，式(1)に平均キュー長の更新則，式(2)に非線形特性を伴うパケット破棄確率をそれぞれ示す．

－ 204 －

ここで，非線形特性の強度γは非線形RED特有のパラメータ，重み係数wqは指数加重移動平均に関するパラメータ，最大パケット破棄確率pmax，最小平均キュー長qmin，最大平均キュー長qmaxはパケット破棄確率に関する3つの閾値をそれぞれ意味する．非線形REDでは，まずルータがパケットを受信した際，パケット破棄確率pおよび前回のパケット受信時における平均キュー長qを用いて，現在の平均キュー長を更新する．次に，現在の平均キュー長により決定されるパケット破棄確率pに基づき，乱数的にパケットを破棄することで平均キュー長を一定の長さに保つ．
一度に破棄するパケットの割合は，図1に示す平均キュー長に対するパケット破棄確率に基づき決定される．q ≤ qminの場合はパケットを破棄せず，q ≥ qmaxの場合はルータ内のパケットを全て破棄する．また，qmin < q < qmaxの場合はパケット破棄確率pに従い乱数的にパケットを破棄する．また，pは平均キュー長qに対して非線形特性を示す．ただし，γ=0におけるパケット破棄確率は，従来のREDと同様の線形特性を表し，γの値が大きいほど非線形特性の強度を強める．これらの特徴により，非線形REDは非線形特性の強度を連続的に変図1非線形特性を伴うパケット破棄確率化可能としている．
2.2

1次元離散非線形REDモデル

1次元離散非線形REDモデルは，ルータ内の平均キュー長q (k+1)を状態変数，非線形特性を伴うパケット破棄確率p(k)を依存変数とした1次元離散力学系である．平均キュー長は式(3)，パケット破棄確率は式(4)で定義される．

ここで，ボトルネック帯域幅C，往復伝搬遅延d，接続台数N，パケットサイズM，最大ウィンド
ウ幅rwnd，モデル定数R=√̅̅̅̅(3/2)はネットワークパラメータ，重み係数wqは指数加重移動平均に関するパラメータ，最大パケット破棄確率pmax，最小平均キュー長qmin，最大平均キュー長qmax，非線形特性の強度γは非線形REDに関するパラメータをそれぞれ意味する．

－ 205 －

3．1次元離散非線形REDモデルの有効性
3.1

仮想ネットワーク環境

Network Simulator- 2 (NS- 2) [ 8]は 米 国DARPAの 研 究 プ ロ ジ ェ ク トVINT (Visual InterNetTestbed)により開発された，ネットワークに関する研究および開発に広く用いられている通信シミュレータである．
図2は，本研究で使用する仮想ネットワーク環境 [2,10]を表す．図中のR1およびR2はルータを意味し，R1に非線形RED [9]，R2に最も基本的なキューイング方式であるTail-Drop [11]を実装している．また，表1,2にネットワークおよび非線形REDに関するパラメータをそれぞれ示す．以下，接続台数Nおよび非線形特性の強度γを変化させ，解析を進める．

図2 仮想ネットワーク環境

3.2

接続台数に対する帯域利用率

通信シミュレーションを行う．表3は，表1 ネットワークに関するパラメータ

従来のRED (γ=0)におけるNに対する帯域利用率を表す．Nに対する帯域利用率は増加傾向を示し，接続台数を増やすほどネットワークの負荷は増加している．また，帯域利用率の変化はNの増加に伴い小さくなり，帯域利用率はおよそN ≥2 におい て 97%，N ≥ 4 に お い て 99%を 上 回 る．
従 っ て，N =1は 低 負 荷 な ネ ッ ト ワ ー ク，
N =3, 10は高負荷なネットワークといえ

表2 非線形REDに関するパラメータ

る．
3.3

平均キュー長に関する時系列波形

次に，定常状態における平均キュー長についてNS-2と提案モデルの計算結果を比較し，ネットワークの負荷に対する提案モデルの有効性を検証する．図3,4,5にN =1, 3, 10における平均キュー長の時系列波形を示す．図中の(a)はγ=0, (b)はγ=5, (c)はγ=300における平均キュー長をそれぞれ表し，実線はNS-2によるシミュレーション結果，破線は提案モデルによる計算結果を意味する．

－ 206 －

TCPは，各送信元における送信パケット量(輻輳表3 従来のREDにおけるNに対する帯域利用率 (γ=0)

ウィンドウ幅)を調節することで輻輳を制御する．
また，輻輳ウィンドウ幅の変動はルータに到着するパケット量に影響を及ぼすため，NS-2の時系列波形は振動する．一方，提案モデルは輻輳ウィンドウ幅を簡素化しているため，定常状態における平均キュー長は常に一定の値を示す．
図 3において，NS-2の平均キュー長は多くの時刻でqminを下回る一方，提案モデルでは常にqmin ≤ q ≤ qmaxを満たすため，N=1における提案モデルの再現性は低い．ただし，非線形REDの動作時間は非常に短いため，低負荷なネットワークに対して非線形REDを実装する必要はない．

図3

平均キュー長の時系列波形 (N =1)

図4

平均キュー長の時系列波形 (N =3)

図5

平均キュー長の時系列波形 (N =10)

－ 207 －図4,5より，N=3および10のような高負荷なネットワークでは，NS-2と提案モデルの平均キュー長は，Nおよびγに対してともに増大し，定性的性質は良く一致している．これらの結果より，提案モデルはネットワークの負荷に対して高い再現性を示すといえる．ただし，図5(c)のように平均キュー長が最大平均キュー長qmaxを上回る場合，提案モデルでは乱数的なパケット破棄が行われる
一方，NS-2でのパケット破棄確率は1となり，REDの制御動作が異なるため提案モデルの再現性は僅かに低下する．
4．非線形特性の強度に対する力学的性質
本研究において，定常状態における平均キュー長は一定の値を示し，これを固定点q*と呼ぶ．本項では，提案モデルに対して固定点解析を行い，非線形REDの力学的性質を明らかにする．式(3),(4)より，非線形特性の強度γに対する固定点の導関数を導出する．

式(5)は常に∂q*/∂γ>0を満たすため，非線形特性の強度γに対する固定点の単調増加を数学的に保証する．従って，非線形特性の強度の増加は高スループット化を示唆している．
5．まとめ
非線形REDによる高スループット化のメカニズムを解明するための第一歩として，ルータ内の平均キュー長に注目した1次元離散非線形REDモデルを提案した．まず，NS-2を用いて接続台数に対する帯域利用率を計算し，接続台数に対してネットワークの負荷が増加することを確認した．
次に，接続台数および非線形特性の強度に対する平均キュー長の時系列波形について，NS-2および提案モデルの計算結果を比較し，提案モデルの高い再現性を示した．最後に，非線形特性の強度に対する固定点解析を行い，非線形特性に対して平均キュー長は単調増加することを数学的に保証したことは，重要な学術的知見である． 今後，ウィンドウ幅を状態変数に加えた2次元離散非線形REDモデルを提案することで，より詳細な解析を進める．
参考文献［1］K. Nichols and J. Van,“Controlling queue delay,”Communications of the ACM, vol. 55, no. 7,
pp. 42–50, 2012.
［2］S
 . Floyd and J. Van,“Random Early Detection Gateways for Congestion Avoidance,”IEEE/ACM Trans. Netw., vol. 1, no. 4, pp. 397–413, 1993.
［3］S
 . Ha, R. Injong, and X. Lisong,“Cubic: a new tcp-friendly high-speed tcp variant,”ACM
SIGOPS operating systems review, vol. 42, no. 5, pp. 64–74, 2008.
［4］S
 . Floyd, G. Ramakrishna, and S. Scott,“Adaptive RED: An Algorithm for Increasing theRobustness of RED’s Active Queue Management,”http://www.icir.org/floyd/papers/
adaptiveRed.pdf, 2001.
［5］K . Zhou, K. L. Yeung, and V. O. Li,“Nonlinear RED: A simple yet efficient active queue－ 208 －management scheme,”Computer Networks 50, pp. 3784–3794, 2006.
［6］A. M. Alkharasani, M. Othman, A. Abdullah, and K. Y. Lun,“An Improved Quality-ofService Performance Using RED’s Active Queue Management Flow Control in Classifying
Networks,”IEEE Access, vol. 5, pp. 24467–24478, 2017.
［7］西内悠祐，上田哲史，太田能，“非線形曲線を導入したネットワークルータにおける輻輳制御,”電子情報通信学会信学技報, vol. 104, no. 584, pp. 43–48, 2005.
［8］S . McCanne and S. Floyd,“NS2 network simulator,”http://www.isi.edu/nsnam/ns/.
［9］加 藤海渡，加藤秀行，伊藤大輔，高坂拓司，“指数特性を持つパケット破棄確率を用いたTCP/RED について,”電子情報通信学会技術報告, vol. 120, no. 330, NLP2020-50, pp. 54–57, 2021.
［10］Z . Hussain, A. Ghulam, and H. Zahid,“A Lightweight Fairness-Driven AQM for Regulating
Bandwidth Utilization in Best-Effort Routers,” Journal of Network and Systems
Management, vol. 26, no. 2, pp. 486–517, 2018.
［11］N. Sharma, S. S. Rajput, A. K. Dwivedi, and M. Shrimali,“P-RED: probability based
random early detection algorithm for queue management in MANET,”Advances in
Computer and Computational Sciences, Springer, pp. 637–643, 2018.

－ 209 －