論文

拡散現象を指導原理とする自律分散フロー制御の実装に向けた
アクティブフロー数計測技術の検討
高野 知佐† a)

山内 正志††

会田 雅樹†††On Implementation Issues of Diﬀusion-Type Flow Control for Multiple Flows
Chisa TAKANO†a) , Tadashi YAMAUCHI†† , and Masaki AIDA†††

あらまし 筆者らはこれまで，高速ネットワークの制御に求められる短い制御遅延の要求を満足するために，
自律分散で動作する拡散型フロー制御技術を提案してきた．この技術は，局所的なネットワーク情報のみに基づ
くノードの自律動作によって，間接的にネットワーク全体を適切な状態に導く制御技術である．本論文では，自律分散システムとしてのモジュール構成を考慮しながらネットワークシミュレータ ns2 への実装を行い，動作特性の評価・分析を行った．この結果，複数フローが混在する環境での適切な制御動作を実現するためには，アクティブなフロー数に関する情報を局所的に推定する技術が必要であることが分かった．この課題を解決するため，拡散型フロー制御技術の改良方式を提案し，その効果を確認した．また，この改良により，複数フロー間のパケットスケジューリングを簡略化することが可能となり，より簡易な実装技術に結び付けることができた．
キーワード

トラヒック，フロー制御，拡散方程式，自律分散制御

適切に動作する制御を実現するためには以下の課題を

1. ま え が き解決する必要がある．

近年のインターネットの急速な普及・需要の拡大に•

局所的な状態情報のみで動作する制御機構

より，将来をにらんだ高速なネットワークの構築が進

超高速ネットワークでは，リンク伝搬遅延（光速度

められている．超高速ネットワークでは，光速度で決により決まる）によりネットワークの広範囲な状態情まる固定伝搬遅延に比べてノードの動作速度が相対報をリアルタイムに把握することができない．このた的に高くなり，ノードの高速動作を特徴づける時間ス

め，リアルタイムに知ることができる局所的な状態情

ケールにおいて，各ノードが収集可能な情報は非常に報のみで動作可能な制御が必要になる．

限られたものになる．遠くのノードから収集した情報•

超高速で動作する制御機構

は過去の情報であり，ネットワーク全体に関する現時

超高速ネットワークでは，ネットワーク状態が短時

点の状態を知ることはできないからである．この意味

間で大きく変化するため，非常に短い制御遅延で動作

で，ネットワークの高速化は各ノードが情報的に孤立するネットワーク制御技術が必要になる．

する状況を招く．また，高速ネットワークでは制御遅フロー制御の課題に対する多くの研究は，線形計画

延の影響が大きいため，非常に高速で動作する制御機問題として定式化される [1]〜[3]．これらの定式化で構が必要となる．このように，超高速ネットワークでは，ネットワークの状態情報を収集が可能であることを前提にしている．しかし，高速ネットワークでは広†範な状態情報をリアルタイムに収集することができな

広島市立大学情報科学研究科，広島市
Graduate School of Information Sciences, Hiroshima City††

University, Hiroshima-shi, 731–3194 Japanい．また，線形計画問題の求解には十分な時間が必要

東京都立科学技術大学工学部，日野市

なので，高速ネットワークに要求される非常に短い制

Faculty of Engineering, Tokyo Metropolitan Institute of

御遅延を満足することが難しい．このように，ネット

Technology, Hino-shi, 191–0065 Japan†††

首都大学東京大学院システムデザイン研究科，日野市

ワーク全体の情報を 1 箇所に収集することを前提とGraduate School of System Design, Tokyo Metropolitan Uni-

した集中制御の枠組みは，超高速ネットワークでのフversity, Hino-shi, 191–0065 Japana) E-mail: takano@hiroshima-cu.ac.jp1254

電子情報通信学会論文誌 B Vol. J91–B

ロー制御として適切でない．このため，自律分散制御
c （社）電子情報通信学会 2008
No. 10 pp. 1254–1266 

論文／拡散現象を指導原理とする自律分散フロー制御の実装に向けたアクティブフロー数計測技術の検討に基づくフロー制御機構が必要とされる．
現在，自律分散型のフロー制御として，例えば TCP

遅延の時間スケールは，ネットワークが高速化するのに伴い重要性が増す領域になっている．

のようなエンドホストによる制御が広く用いられ，そ

これまで，シミュレーションによって DFC によるの特性について活発に研究されている [4]〜[6]．エンド

ネットワーク状態の安定性，状態変化に対する適応性，ホストによるフロー制御では，タイムスケールはラウTCP との親和性を評価し，DFC がねらいどおりの性

ンドトリップタイム（RTT）程度となる．低速なネッ能を発揮することを確かめてきた [7]〜[10]．これらのトワークでは，RTT 程度の制御遅延による影響を無結果に加え，DFC が実ネットワークでも正しく動作視することが可能だが，ネットワークが高速化するとすることを確かめるためには，DFC の実装に向けた

RTT 程度の制御遅延が大きな影響を与えるようにな

技術課題として以下の課題を確認する必要がある．

る可能性がある．ネットワークの高速化に対して RTT
自身の物理的な値は不変であっても，ノードの動作速
度の時間スケールを時間の基準として見た RTT は大きくなるからである．これは，RTT 程度の時間内に•DFC が自律分散制御としての装置構成によって実装が可能であること．

•

自律分散制御として実装した DFC がねらいど

おりの性能を発揮すること．

ノードが処理するパケット数が増大することを意味し，

これまでの評価では，TCP と DFC との共存可能

より制御遅延の影響を強く受けるようになる．RTT

性や相互補完性を調べるために，ネットワークシミュ

よりも短い時間スケールで俊敏に動作する制御を実現

レータである ns2 [13] を利用し，DFC 機能を ns2 にするためには，ノードが局所情報に基づいて自律動作

実装することで評価を行ってきた．ns2 は本来，装置するタイプの制御機構が必要になる．

のモジュール構成を反映したシミュレータとなってい我々は，高速ネットワーク環境でも適切に動作するため，自律分散制御としての装置構成を意識しながる フ ロ ー制 御 方 式 と し て ，拡 散 型 フ ロ ー 制御 技 術

ら DFC 機能を ns2 に実装することによって，DFC 機（diﬀusion-type ﬂow control：DFC）を提案してきた．

能の実装可能性を確認することができるはずである．

このフロー制御方式は，各ノードが自分自身で利用可

しかし，これまでの評価では DFC の構成を完全に自能な局所的情報のみに基づいて自律動作を行い，そ律分散制御の装置構成で実装したわけではないため，の結果としてネットワーク全体を安定させるものである．図 1 はネットワークの各種制御を，要求される

DFC の実装可能性が確認できていなかった．
ns2 に組み込んだ DFC 機能のこれまでの実装では，

制御遅延時間の大きさにより階層化したものである．

シミュレーションモデルとして「各ノードは自分を通

routing 制御，session initiation protocol（SIP）な

過するフロー数を知っている」という前提のもとで評どのシグナリング処理，TCP や explicit congestion
notiﬁcation（ECN）などの流量制御は，それぞれ数十
分，秒，RTT 程度の制御遅延をもつ．DFC は，RTT

た．自律分散的な装置構成では，すべてのフロー情報

よりも更に厳しい制御遅延の要求を満たすための制御

各ノードは自分自身で局所的に通過フロー数の情報技術として位置づけられる．DFC が対象とする制御を取得しなければならない．もしネットワーク内のフ価を行い，DFC が適切に動作することを確認してきを知っている管理装置の存在を仮定していないので，

ローが常にトラヒックを発生させていれば，到着パケッ
トを観測することでノードを通過するフロー数を知ることができる．しかし，一般にはフローが一時的にパケットを発生させない状態になることがあり得るし，発生させていてもパケット間隔が広く，適当な時間区
間ではパケットの発生がない場合も考えられる．したがって，自律分散的な装置構成をとる限り，各ノードは自分を通過する正確なフロー数を知ることができない．
図 1 各種ネットワーク制御の要求される制御遅延による階層化
Fig. 1 Hierarchical structure of network controls withrespect to their required control delay.

本論文では，モジュール構成を考慮した ns2 の特性を利用し，自律分散で動作するモジュールとして DFCの実装を行う．更に，実装した DFC の振舞いとこれ
1255

電子情報通信学会論文誌 2008/10 Vol. J91–B No. 10までのシミュレーション評価結果との違いから，通過い．しかしながら，温度分布は拡散方程式の解としてフロー数の情報取得に関連する問題点を明らかにし，

秩序ある振舞いを示す．このように，システムの各部その解決策を示す．更に改良した DFC がねらいどお分が局所情報のみに基づいて自律動作をしつつも，シりの特性を示すことを明らかにすることで，DFC のステム全体の状態に秩序を生むことが可能である．こ

実装可能性を確認する．

の仕組みをネットワークに適用すると，各ノードの動

本論文の構成は以下のとおりである．2. で，これ作ルールを適切に決めておけば，ノードの自律動作にまで評価してきた DFC の概要を示し，3. で，既存のより間接的にネットワークの全体性能を望ましい方向

DFC を ns2 に実装する方法を示す．また 4. で既存のDFC を ns2 に実装した場合の問題点を明らかにしたに誘導することが可能であると考えられる．DFC で後，5. で DFC の実装に向けた改良方法を示す．更に，

トフローを制御することにより，一部のノードへのパ

6. で，改良した DFC を評価し，その効果を実証する．
最後に 7. でまとめる．

ケットの集中を回避し，パケットロスの起きにくい状

2. 拡散型フロー制御の概要

は各ノードが拡散現象に似たルールで局所的なパケッ態を維持するように動作する．

2. 2 拡散型フロー制御方式
あるフローに沿って一次元的に連結したノード i

2. 1 制御の基本コンセプト（i = 1, 2, . . . , N ）を考え（図 3），ノード i とノード

インターネット型のネットワークにおいても，エンi + 1 の間のリンクの帯域を Bi とする．また，ノード i

ドツーエンドでの QoS 保証を要求するフローについとノード i + 1 の間のリンクを共有するフロー数を Miては，RSVP のように特定の経路を用いた通信を行とする．ノード i は，時刻 t における下流ノード i + 1う．本論文では，このような特定の経路をもつフロー

へのフロー j（j = 1, 2, . . . , Mi ）のパケット転送レーを対象とし，ノードではフローごとのパケットキュー

ト Jij (t) を自分が知り得る情報のみに基づいて決定し，イングが行われることを仮定する．

パケット転送を行う．また，上流ノード i − 1 に向けて

DFC は，各ノードが自分自身の知り得る局所情報のみに基づいて自律的に局所フローを制御し，間接的にネットワーク全体の状態を望ましい方向に誘導するj

ノード i の情報 Fi (t) をフィードバックする．パケッ
ト転送レート Jij (t) の決定は，下流ノード i + 1 から伝搬遅延 di を伴って通知される情報 Fji+1 (t − di ) の到フロー制御技術の枠組みである．具体的には，ネット

着ごとに実行する．上流ノード i − 1 に向けたフィー

ワークがふくそうに陥ることをを回避したり，ふくそドバック情報 Fi (t) の通知は，ノード i − 1 と i 間のう状態から回復するように動作する．各ノードが自律伝搬遅延 di−1 に比例した時間間隔で行う．

的に動作することで，状況の変化に即応した高速な制御動作が可能となる．

j以降では，パケット転送レート Jij (t) とフィードバッ

ク情報 Fji (t) の算出方法について述べながら，DFC

DFC は，ノードの局所的自律動作によってネットの全体像を説明するが，それに先立ち，DFC の説明

ワーク全体の状態を望ましい方向に誘導するために，に利用されるアクティブフローの概念について明らか

物理の近接作用の考え方に基づいた制御の仕組みを採にしておく．ノード i とノード i + 1 の間のリンクを用している．これを熱拡散現象を例にして説明する．

共有する，または共有する可能性のあるすべてのフ

図 2 のように鉄棒の一点を熱すると，温度分布は正規

ロー数を Mi としたとき，ある時点で必ずしもすべて分布となり拡散する．このとき，鉄棒の一点は鉄棒全のフローにパケットが流れているとは限らない．本論

体の温度分布に関する知識はなく，左右の温度差に比

文では，何らかの計測によってパケットが流れている

例した熱量を高温側から低温側に流しているにすぎな

Fig. 21256

図 2 熱拡散現象の例
Example of thermal diﬀusion phenomenon.

Fig. 3図 3 DFC の動作モデル
Node interactions in our ﬂow control model.

論文／拡散現象を指導原理とする自律分散フロー制御の実装に向けたアクティブフロー数計測技術の検討と判断されたフローをアクティブフローと呼ぶことに
（注 1）

する

．特定の時間帯においてあるノードがパケッ

トの流れを観測したときに，実際にパケットが観測さjを表す．つまり，あるフロー j の指定レート ri−1 (t)の上限は，帯域 Bi をアクティブフロー数で割った値になる．

れるかどうかについては，音声の無音区間やパケット

次に，DFC の直観的意味を説明する．議論を簡略化

レートの高低などのトラヒックの特性に影響を受ける．

するため，ノード ID を連続化し，i → x で表す．まこのため，どのフローがアクティブと判断されるかは，た，連続極限をとってリンクの伝搬遅延を di → 0 とす

時刻ごとやノードごとに一般に異なる結果となること

る．このとき，J˜ij (t) → J˜(x, t)，rij (t − di ) → r(x, t)，nji (t) → n(x, t) とすれば，式 (2) はがあり得る．
時刻 t，ノード i におけるフロー j の転送レート

Jij (t) はJij (t) = max(0, min(Lji (t), J˜ij (t)))(1)

J˜ij (t) = rij (t − di ) − Di (nji+1 (t − di ) − nji (t))(2)
jによって決定する．ここで，ni (t) は時刻 t でノード i に存在するフロー j のパケット数，rij (t − di )，nji+1 (t − di ) は下流ノード i + 1 からのフィードバッ

クにより，（リンク伝搬遅延 di を伴って）通知される
情報で，それぞれ下流からの指示レート，下流ノーj

ド内のフロー j のパケット数を表す．Li はノード iからノード i + 1 に向かうリンクにおけるフロー j（注 2）の利用可能帯域である．また Di は D（> 0）を定数として Di = D/di である．D は拡散係数と呼ばれ，0 < D < 1/2 の範囲の値をとる [11], [12]．フ
ロー j に関するパケット転送レート Jij (t) は，すべて∂n(x, t)J˜(x, t) = r(x, t) − κ∂x(6)の形で書ける．ここで κ > 0 は離散のときの D に対応する定数である．連続の式

˜ t)∂ J(x,∂n(x, t)=−∂t∂xを用いると，パケット密度 n(x, t) の時間発展は∂r(x, t)∂ 2 n(x, t)∂n(x, t)
=−
+κ
∂t
∂x
∂x2

(7)

と書ける．これは拡散型の方程式である．したがって，

DFC はノードが局所情報に基づいて自律動作をする
ことで，ネットワーク全体としてノード内パケット数を均一化する効果が期待できる．

2. 3 ネットワーク入口でのパケットレート制限法
DFC がサポートされているネットワークを DFCの j = 1, 2, . . . Mi について計算するのではなく，アがサポートされていないネットワークと接続するため

クティブフローについてのみ行う．ここで得られたパに，ネットワーク境界部分での境界条件を考える必要j
ケット転送レート Ji (t) により，アクティブフローのがある．

パケット転送レートを更新する．アクティブフローでないフローのパケット転送レートは 0 とする．
一方，ノード i が生成するフロー j に関するフィーj
ドバック情報 Fi (t) はjFji (t) = (ri−1(t), nji (t))

こで，Miact (t) =Mi

1{j=active}とし，ネットワーク入口での入力パケットレートは，
フィードバック情報 r0j (t − d0 ) で指定されたレートにシェーピング（バッファで遅延させることによるレー(3)からなり，これを上流ノード i − 1 に通知する．こjri−1(t) = max(0, min(J˜ij (t), Bi /Miact (t)))

ネットワーク外のノードまたはエンドホストは拡散型フロー制御方式をサポートしていないことを前提

トの調整）がされるものとする．ノード i = 1 が通知
j

する情報 r0 (t) は，ネットワーク外のノードまたはエンドホストのバッファに存在するパケット数を 0 と仮定し，式 (2) によってレート J˜0 (t) を計算する．つま(4)り，r0j (t) は式 (4) の代わりに，(5)

r0j (t) = J1j (t) − D0 nj1 (t)

(8)

j=1
j

とする．ただし，1{j=active} はフロー j がアクティブ
フローのとき 1，そうでなければ 0 となる指示関数であり，Miact (t) はその時刻 t でのアクティブフロー数を用いて決定する．r0 (t) はノード i = 1 で取得可能（注 1）：アクティブフローの判定方法は後述する．
（注 2）：Lji の決定方法は 2. 4 で述べる．

1257

電子情報通信学会論文誌 2008/10 Vol. J91–B No. 10

トワーク内部の DFC によるレートとの親和性を高め

J˜ij (t) を使用することができず，パケット密度のスムー
ズな平滑化を妨げる原因となり得る．Lji (t) の最も単j
純な決定方法は，アクティブフローごとに重み J˜ (t)ることができる．

を付けて帯域 Bi を分け合うことである．つまり，そな量のみによって計算することができる．これにより，ネットワーク外からの入力パケットレートとネッ

しかし，DFC は局所情報に基づくノードの自律動

i

れぞれのフローの重み Wij (t) を作を用いた制御なので，ネットワーク内の状態を高速に平滑化させる効果には優れるが，ネットワーク内に

Wij (t) = M˜k
k=1 1{k=active} × Ji (t)外部から流入する余分なパケットを防ぐ効果は少ない．そこで，必要に応じてネットワーク入口でパケッ
トレートを制限する機能を併用し，ネットワーク入口
でのパケット流入量を適切に制限することが必要とJ˜ij (t)i(13)とし，それぞれのフローの利用可能帯域を

Lji (t) = Bi × Wij (t)(14)
jなってくる．これを実現するためには，ネットワークとすることで，より大きい重み J˜i (t) をもったフロー

入口部分でフローに沿った経路上のネットワーク状態

がより大きい転送レートを確保でき，下流ノードによを把握し，その状態に合わせてネットワーク入口でのり多くのトラヒックを流すことができることになる．

パケットシェーピングを施すことが有効である．つまこのとき，重みの小さなフローは相対的に他のフロー

り，ノード i が生成するフィードバック情報 Fji (t) にの転送レートはより小さく制限されることになる．こ

リンクの最大利用可能帯域に関する情報 ji (t) を加え，jFji (t) = (ri−1(t), nji (t), ji (t))(9)

を上流ノード i − 1 に通知する．ji (t) は，

ji (t) = min(ji+1 , Bi /Miact (t))

用いる．この値で，式 (8) の値を制限することにより，ネットワーク内に外部から流入する余分なパケットを防ぐことができる．
リンク帯域は複数のフローで共有されているため，フロー間で適切に Lji (t) を調節する必要がある．
ノード i からノード i + 1 へのリンクの帯域を Bi とj

したとき，Li (t)（j = 1, 2, . . . , Mi ）は，

本章では，2. で示した既存の DFC 機能を実装した
ns2 の装置構成を示す．
3. 1 各モジュールの概要
ns2 に実装された DFC 機能は主に四つのモジューの概要を示す．

•DFCFlowQ

受信したパケットをフローごとにキューイングする．
また，あるフローのパケットが DFCQueue に存在しなければ，そのフローに関する DFCFlowQ の先頭パケッ

(11)

j=1

(j = active)

3. ns2 に実装された DFC の概要

ルから構成されている（図 4）．以下にそれぞれの機能

2. 4 各フローの利用可能帯域の決定方法

Lji (t) = 0

される．また，フローごとに利用可能帯域が適切に調向にノード内パケット数を平滑化する効果も得られる．

(10)

ちで一番小さい（とノード i が認識する）帯域の値を

1{j=active} × Lji (t) = Biるノード内パケット数のフロー間のばらつきが平滑化整されるため，ボトルネックに対してフローの下流方のように生成する．ji (t) の計算は，下流のリンクのうMiれによりフロー間で帯域が分配され，共通経路上にあ(12)を満たすとする．これは，アクティブフローのみの利

トを DFCDBAgent により定められた転送レート J˜ij (t)で DFCQueue へ転送する（図 5 参照）．

•

DFCQueue

DFCFlowQ から受信したパケットをリンクへ送出す
る．パケットを送出するフローは，各フローに定めら用可能帯域で全帯域を分け合うことを意味する．

れた重みにより weighted round robin（WRR）で決DFC では，転送レートの理想値は J˜ij (t) であり，
J j (t) は理想値 J˜j (t) を物理的に利用可能な帯域を上定される（図 5 参照）．

ii

限として制限したものである．多くのフローがある場•

DFCDBAgent

下流ノードからのフィードバック情報が記された

合，理想の転送レート J˜ij (t) は，

Mi ˜jj=1 Ji (t) > Bi と

DFC パケットを受信し，受信した値と自ノードの情なり，すべてのフローがそれぞれの理想の転送レート

報をもとに自ノードのフィードバック情報を算出する．

1258

論文／拡散現象を指導原理とする自律分散フロー制御の実装に向けたアクティブフロー数計測技術の検討

図 4 DFC のモジュール構成
Fig. 4 Modules of DFC function.

Fig. 5図 5 WRR 方式
WRR scheduling-based rate control.
Fig. 6図 6 従来のアクティブフロー数の測定
Measurements of the average number of active
ﬂows.

•

DFCAgent
DFCDBAgent により算出されたフィードバック情報
をパケット化し，DFCFlowQ を通して上流ノードへ送出する．

3. 2 DFCQueue からリンクへのパケット送出方法
DFCFlowQ から DFCQueue へのパケット転送レートは J˜ij (t) である．これは単一のフロー j に着目して算出された値であり，DFCQueue からリンクへのパケッ
jト送出時に，式 (1) のようにレート J˜ (t) はフロー j のjji

利用可能帯域 Li (t) によって Ji (t) に制限される．これを実現するために，これまでの実装では DFCQueue からリンクへのパケット送出方法を重み Jij (t) の WRR
方式としている．

3. 3 アクティブフロー数の測定方法
式 (4) と式 (10) で用いられている Miact (t) の測定方法について説明する．

DFCFlowQ から DFCQueue に送出が行われるごとに，パケットが到着したフロー数をアクティブフローとして測定し，フィードバック情報生成に必要なアクティ
ブフロー数 Miact (t) を計算するための値を保持する．
具体的には，

activeNum= (DFCFlowQ から DFCQueue への送出回数)
activeCount= (パケット到着のあったフロー数の累計)とし，図 6 のようにして，activeCount/activeNum
によりアクティブフロー数 Miact (t) を測定している．
また，activeNum，activeCount はフィードバック情報が生成されるごとにリセットされる．この方法では，
フィードバック情報が生成される間の平均アクティブ
フロー数を求めていることになる．

4. DFC 実装上の問題点と原因の分析
本章では，自律分散制御としての装置構成で既存のDFC の動作特性を評価し，問題点抽出と原因の分析を行う．具体的には，既存の DFC が実装された ns2を用いて，単純なモデルでシミュレーションを実行し，

DFC の動作特性を分析する．また，本論文の評価では，DFC のパラメータを D = 0.4，フィードバックj

情報 Fi (t) の送信間隔を di−1 とした．
1259

電子情報通信学会論文誌 2008/10 Vol. J91–B No. 10

図 7 シミュレーションモデル
Fig. 7 Simulation model.

4. 1 シミュレーションモデルとシナリオ
シミュレーションに用いるモデルは，あるフローに．ノー
沿った一次元ネットワークを考える（図 7 参照）

図 8 ノード内に存在するパケット数分布の経時変化
Fig. 8 Temporal evolution of the distribution of
stored packets in each node.

ド数を 30，各リンクの伝搬遅延を 0.1 ms でリンク長は固定，各ノードのバッファ容量 1800 パケット，1 パ
ケットは固定長 1500 Byte で，1 リンク上の最大パケッ
ト数は 100 パケットとした．ネットワーク内のノード
は DFC の機能をもつ．また，パケットの発生源としてソースノード 1 と 2 を配置した．これらは DFC 方式適用外（シェーピング機能はあり）のノードである．
各ソースノードのパケット生成レートは，フロー制御がかかっていない状態で単位時間当り 100 パケットとした．
シミュレーションシナリオは次のとおりである．ネッ
トワーク上にはフロー j = 1 とフロー j = 2 の二つの TCP フローを流す．ソースノード 1 で発生するフ

図 9 ノード内パケット数の総和の経時変化
Fig. 9 Temporal evolution of the total number ofstored packets in nodes.

ロー j = 1 は性能評価対象のフローで，ノード 1 から
ノード 30 へと流れる．ソースノード 2 で発生するフはフローの経路に沿ったノード ID を示しており，縦ロー j = 2 はフロー j = 1 の妨げとなる背景フローで，軸はそのノード内パケット数を表している．グラフ

対象フローの経路上のノード 15 に流入し，ノード 30

ごとに異なる時刻の状態を表示している．図 9 の横へと流れる．TCP の window size は両フローともに

軸は時刻を示しており，縦軸はその時刻でのノード

RTT の bandwidth-delay product より十分大きい値
として 10,000 とした．フロー j = 1 は t = 0.0 s，フ内パケット数の総和を表している．図 8 から，時刻t = 0.06 s にフロー 2 が流入したことによるふくそう

ロー 2 は t = 0.06 s にそれぞれ送信を始め，t = 0.12 sが，t = 0.073 s でいったん解消していることが分かでシミュレーション終了とする．フロー j = 2 が送信る．しかし，その後 t = 0.082 s で再び小さなふくそされ始めると，ノード 15 からノード 16 へのリンクはうを起こしている．図 9 によれば，1 度目のふくそう

ボトルネックとなり，二つのフローは DFC のルールが解消された後に，2 度目，3 度目の小さなふくそう

によって転送レートが規制されることになる．シミュが繰り返し起こっていることが分かる．つまり，ネッ

レーション結果より背景フローが流入直後からのネッ

トワーク内のノードに存在するパケット数が平滑化し，トワーク状態の時間変化を調べることで，DFC の従

いったんふくそうが解消したにもかかわらず，何らか来の実装について性能を評価する．

の原因で再度ふくそう状態が引き起こされていること

4. 2 シミュレーション評価結果になる．

フロー j = 2 が流入した直後からの，フロー j = 1

次に，フロー j = 1 のリンク上に存在するパケットのネットワーク内のノード上パケット数の振舞いを調数の総和の時間推移を図 10 に示す．この評価は，ネッ

べた結果が図 8 であり，また各時間のノード上パケッ

トワークがフロー 1 のパケットをどれだけ運んでいる

ト数の総和を示したものが図 9 である．図 8 の横軸かを示している．シミュレーション条件より 1 本のリ

1260

論文／拡散現象を指導原理とする自律分散フロー制御の実装に向けたアクティブフロー数計測技術の検討

図 10 リンク上パケット数の総和の経時変化
Fig. 10 Temporal evolution of the total number ofpackets on links.

Fig. 11

図 11 Bi /Miact (t) の値の時間変化
Temporal evolution of Bi /Mi at each nodes.

らのことから，ji (t) と rij (t) の決定に用いた Miact (t)ンク上に乗る最大パケット数が 100 なので，リンクのの振舞いが，DFC の適切な実装を妨げていることが帯域がフロー j = 1 とフロー J = 2 で公平に分けら分かる．

れたとするならば，フロー j = 2 が流入した後の，フロー j = 1 のリンク上のパケット数の総和の適切な値

5. DFC の実装に向けた方式の改良

は，約 1450 である．図 10 から，2 度目，3 度目のふ

前章で，DFC を実装するためには ji (t) と rij (t) のくそうが起こっていた付近で，リンク上のパケット数決定に用いられていた Bi /Miact (t) の値が DFC のねの総和の値が適切な値を超えていることが分かる．

らいどおりに変化していないことが分かった．これまこれまでの評価（ノードは通過フロー数を知っていで，シミュレーションモデルを用いた DFC の基本動るという状況下）では，1 度ふくそうが解消されると作特性の評価では，フィードバック情報計算の対象と再度ふくそうが現れるということはなく，ネットワー

なるフロー数，つまりノードを通過するアクティブフ

ク性能は安定していた．今回の評価において複数回ふ

ロー数 Miact (t) の情報はシミュレーションの初期設定

くそうが起こる原因として，ネットワーク内への過剰のパラメータとして決定され，ノードにとって既知のなパケット流入と，フロー j = 1 のノード 15 への過情報としていた．このようなシミュレーション条件で剰なパケット送出の 2 点が考えられる．

は，アクティブフロー数 Miact (t) の決定が不適切でネットワーク内へのパケット流入量を決定するときあっても DFC の動作に深刻な影響を与えることはなに用いられるのは，ji (t) であり，各ノードの転送レーかった．しかし，モジュール構成を意識した DFC のトの決定するときに用いられるのは rij (t) である．双方実装では，ノードがアクティブフロー数 Miact (t) の情

ともふくそうが複数回起きる原因となっているので，そ報を知ることができるとは限らない．そのため DFC

れぞれの値の決定に共通して用いられている Miact (t)を実装するモジュール内に，ノード自身がアクティブの決定方法に問題がある可能性が高い．これを確かめ

フローに関する情報を取得する仕組みを組み込まなけ

るため Bi /Miact (t) の値がどのように変化しているかればならない．

を検証する．図 11 は各ノードでのフロー当りの利用

本章では ji (t) と rij (t) の決定方法の考察とノード

可能帯域 Bi /Miact (t) をノードごとに表示し，グラフ自身がアクティブフローに関する情報を取得する仕組ごとに異なる時間の状態を表示したものである．各グ

みの考察を行い，DFC の方式改良を行う．

ラフの縦軸は利用可能帯域 Bi /Miact (t)，横軸はノー5. 1 ji (t) と rij (t) の制限方法
式 (2) の転送レート J˜j (t) はネットワーク内のノー

ド ID を表す．ノード 1 から 14 まではフロー j = 1 の1 本しか存在しないため，Bi /Miact (t)  12 Gbit/s 程

ド内パケット数平滑化のために計算された値である

i度となり，ノード 15 以降は 2 本のフローで帯域を分が，フロー j のみに着目して決定した値であり，他のけ合うため，その半分程度の値となるのが適切である．

フローの影響を考慮に入れていない．そのため，実際この図より，1 度目のパケット平滑化が行われた後，適のパケット送出のレート Jij (t) は，式 (1) に示すよう切な値から大きく外れていくことが確認できる．これに Lji (t) によって J˜ij (t) を制限した値となっている．
1261

電子情報通信学会論文誌 2008/10 Vol. J91–B No. 10
j

式 (14) から分かるように，Li (t) はノード内の他のアクティブフローを特定することができる．また，式

フローの転送レートの値を考慮して算出されたもので(13) により Wij (t) を計算し，式 (14) により Lji (t) をある．

決定することができる．

これまで，ji (t) と rij (t) の決定には Bi /Miact (t) の値で上限を決めていたが，転送レートの決定式 (1) とj

5. 3 パケット送出方法に関する考察
DFC の実ネットワークへの実装を考えるとき，DFC

同様に Li (t) の値を上限値として用いれば，他のフはデータリンク層で実現され，DFCQueue は例えばネッローの影響を考慮に入れた DFC の転送レート決定法

トワークカード内に実装されることが考えられる．こと整合がとれる．つまり，ji (t) と rij (t) の値をそれのため，もしリンクへのパケット送出方法を簡略することができれば，既存のネットワークカードに DFC

ぞれ，

ji (t) = min(ji+1 (t), Lji (t))(15)

rij (t) = max(0, min(J˜ij (t), Lji (t)))(16)

を実装することが容易になると考えられる．
従来の DFC では，DFCFlowQ から DFCQueue へのパケット転送レートを J˜ij (t) とし，DFCQueue からリンとすれば，ネットワーク全体のパケット平滑化というクへの転送レートを WRR を用いて Jij (t) に制限してねらいが考慮された値になると考えられる．Lji (t) をいた．しかし，今回の改良によりアクティブフロー数

れば，自然にアクティブフロー数 Miact (t) の値も明らの情報を DFCDBAgent が利用できるようになるので，
DFCFlowQ から DFCQueue へのパケット転送レートをJij (t) とすることが可能となった．この Jij (t) は，下流かになる．そのため，以降ではアクティブフローの判のリンク帯域と，他のフローの転送レートを考慮に入定法と Lji (t) の決定法を考察する．

れた値となっているので，DFCQueue からリンクへの適切に決定するにはアクティブフローの判定が必要であり，逆にアクティブフローの判定が適切に実行でき

5. 2

jアクティブフロー数の測定法と Li (t) の決

パケット送出をよりシンプルな Round Robin（RR）

定法

や Single Server Queue に変更しても，従来の性能をフィードバック情報が生成される間にどのフローが保つことができると考えられる（図 13 参照）．DFC

アクティブフローであるかを測定する方法は，従来の機能を実装を考えると，DFCQueue では単純な FIFO

アクティブフロー数の測定方法を変更することで実現できる（図 12）．具体的には，まず DFCQueue がパケットを更新するごとに，それぞれのフローについて，

DFCFlowQ と DFCQueue にパケットが存在しているか否かを調べる．調べたフローにパケットが存在するならば，そのフローのフロー情報にフラグを立てる．その後，DFCDBAgent がフィードバック情報を生成する
ごとにフラグをリセットする．この操作を行うことで，フィードバック情報が生成される間にどのフローがア
クティブであったかを測定することができる．

DFCDBAgent はこの得られた情報を参考に，パケッ
ト転送レートやフィードバック情報の計算対象となるFig. 121262

図 12 アクティブフロー数の測定
Measurement of the number of active ﬂows.

queue を用いた実装が可能となり，ハードウェアの簡略化が実現することに結び付く．ここで，DFCFlowQから DFCQueue へのパケット転送レート J˜ij (t) がMi

1{j=active} × J˜ij (t) < Bi

(17)

j=1

を満たすならば，アクティブフローでないフローのパケットであっても DFCFlowQ から DFCQueue へ転送することができる．そのときのパケット転送レート
は Bi −

 Mi

˜j
j=1 1{j=active} × Ji (t) となる．このため，

ノード i においてアクティブフローでないと判断され，

図 13 FIFO（Single Server Queue）方式
Fig. 13 Single server queue-based rate control.

論文／拡散現象を指導原理とする自律分散フロー制御の実装に向けたアクティブフロー数計測技術の検討

パケット転送レート 0 が割り当てられたパケットがしている．これを見ると，複数回起こっていたふくそ

ノード i に到着したとしても，混雑していなければ次うが起こらなくなり，それに伴ってリンク上のパケッのレート更新時刻を待たずに転送可能である．

ト数も改良前に比べて早い段階で安定した値になって

6. 評

価

上記の改良を行った ns2 を用いてシミュレーション

いることが分かる．
次に，ノード上の総パケット数及びリンク上の総パケット数に関して，DFC 機能による収束の速さを改を行い，自律分散制御の装置構成をもつ DFC 機能が良前後で比較する．図 16 は，横軸がふくそうが開始

適切な性能を発揮することを確認することで，改良してからの時間，縦軸がその時間以降のノード上のパした DFC の妥当性を評価する．なお，今回のシミュ

ケット数の総和の最大値を表す．実線が改良後，破線

レーションでは，DFCQueue からリンクへのパケットが改良前の値を示している．この図から改良後は改送出方法を Single Server Queue に変更した．

良前に比べてノード上の総パケット数が速やかに減少

6. 1 ふくそうの繰返しを避ける効果についてのシ
ミュレーションの評価結果
まず，4. 1 で用いたモデルとシナリオを用いて，ふしていることが分かる．例えば，ノード上のパケット数の総和が 30 個以下に収束する時間は，改良前では0.06 s，改良後では 0.015 s であり，改良前の約 25%まくそうの繰返しを避ける効果についての評価を行う．

で削減できる．また図 17 は，横軸がふくそうが開始

図 14 と図 15 はそれぞれ改良前と改良後のフローしてからの時間，縦軸がリンク上のパケット数の総和

j = 1 の，ノード上パケット数の総和の時間推移，リと理想値（1450）との差の比率を表す．この結果から，ンク上パケット数の総和の時間推移を示したものである．それぞれ，実線が改良後，破線が改良前の値を示

図 14 ノード上のパケット数の総和の時間変化の比較
Fig. 14 Comparison of temporal evolution of thetotal number of stored packets in nodes.

図 15 リンク上のパケット数の総和の時間変化の比較
Fig. 15 Comparison of temporal evolution of thetotal number of packets on links.

図 16 ノード上のパケット数の総和の収束の比較
Fig. 16 Comparison of the convergence of the total
number of stored packets in nodes.

図 17 リンク上のパケット数の総和の収束の比較
Fig. 17 Comparison of the convergence of the total
number of packets on links.

1263

電子情報通信学会論文誌 2008/10 Vol. J91–B No. 10て素早く理想値に近づいていることが分かる．例えJi1 (t) の値がフローが 2 本の場合の値（このとき存在するフローは j = 1, 3）に回復していき，t = 0.156 s

ば，理想値との誤差が 1%未満になる時間は，改良前にすべてのノードの転送レートの値が回復したことがでは 0.055 s，改良後では 0.024 s であり，改良前の約分かる．つまり，t = 0.156 s 付近からフロー j = 1 の40%まで削減できる．

リンク上パケット数の総和の値が，1450 パケット付近

改良後のリンク上のパケット数の総和が改良前に比べjj
これらのことから，i (t) と ri (t) の決定に用いら
jact
れていた Bi /Mi (t) を Li (t) に変更することで，フまで回復していれば，それぞれのノードでアクティブ
フロー数が適切に管理されていることが分かる．

ロー j = 1 の転送レートの値が適切な値となり，また図 20 はフロー j = 1 のリンク上パケット数の総和

ネットワーク入口部分のシェーピング機能がうまく働の時間推移を示したものである．これを見ると，それき，ネットワークへの過剰なパケット流入が抑えられ，

ぞれの時刻のフロー数に応じて，リンク上パケット数

ふくそうが複数回起こるという現象を解決できたことの総和が適切に変化していることが分かる．具体的が分かった．

には，アクティブフローが二つである t = 0.06 s から

6. 2 アクティブフロー数の適切な管理についてのシミュレーションモデルと評価結果
ここでは，アクティブフロー数が適切に管理されて

t = 0.09 s にかけては 1450 パケット付近，アクティブ
フローが三つである t = 0.09 s から t = 0.150 s にかけては 966 パケット付近，アクティブフローが一つ減

いるかについての評価を行う．この評価では，これまで用いたモデルを以下のように変更した．ノード 23に新たにソースノードを接続し，t = 0.09 s からノード 30 に向けてパケット送出を開始する（このフローを
フロー j = 3 とする）．更に同じ時刻に，フロー j = 2のパケット生成を停止させる．
まず，ネットワーク内からフロー j = 2 のパケットが消滅するまでの時間を調べるために，フロー j = 2のリンク上パケット数の総和の時間推移についてのグラフを示す（図 18）．この図からフロー j = 2 のすべてのパケットがノード 30 に到達した時刻が約 t = 0.15 s
であることが分かる．この時刻以降のフロー j = 1の転送レート Ji1 (t) の変化を調べたものが図 19 である．横軸はノード ID，縦軸はそのノードの転送レート Ji1 (t) を表し，それぞれのグラフは異なる時刻の状
態を表示している．
フロー j = 2 のパケットがネットワーク内から消滅

Fig. 19

すると，ノード 30 からノード 1 に向かって転送レート

図 18 フロー j = 2 のリンク上パケット数の総和の時間変化
Fig. 18 Temporal evolution of the total number ofﬂow 2’s packets on links.

1264

図 19 転送レート Ji1 の時間変化
Temporal evolution of the transmission rate
Ji1 at each node.

フロー j = 1 のリンク上パケット数の総和の時間変化
Fig. 20 Temporal evolution of the total number of
ﬂow 1’s packets on links.

図 20

論文／拡散現象を指導原理とする自律分散フロー制御の実装に向けたアクティブフロー数計測技術の検討

少した t = 0.150 s 以降は 1450 パケット付近となって

1999.
[3]

いることが分かる．

control algorithm for maximizing total user utility,”

これらのことから，ノード上でのアクティブフロー
数が適切に管理されていることが確認でき，本研究でK. Kar, S. Sarkar, and L. Tassiulas, “A simple rate
Proc. IEEE INFOCOM 2001, pp.133–141, 2001.

[4]

示したアクティブフロー数に関する情報の取得方法が

J. Mo and J. Walrand, “Fair end-to-end window
based congestion control,” IEEE/ACM Trans. Netw.,
vol.8, no.5, pp.556–567, Oct. 1999.

適切であることが確認された．
[5]

7. む す び

S. Kunniyur and R. Srikant, “A decentralized adaptive ECN marking algorithm,” Proc. IEEE GLOBECOM ’00, pp.1719–1723, 2000.

拡散型フロー制御（DFC）とは，拡散現象を指導原[6]理としたフロー制御で，局所的なネットワーク情報にDec. 2001.
[7]

C. Takano and M. Aida, “Stability and adaptability of autonomous decentralized ﬂow control in high-まで，DFC がねらいどおりの特性をもつことがシミュ

speed networks,” IEICE Trans. Commun., vol.E86-B,

レーションにより確かめられてきたが，その評価ではノードを通過するフロー数が既知であることを用いてDelays and stability,”

IEEE/ACM Trans. Netw., vol.9, no.6, pp.818–832,

基づいたノードの自律動作が，間接的にネットワーク
全体の状態を良好な特性に導く制御方式である．これ

R. Johari and D. Tan, “End-to-end congestion
control for the Internet:

no.10, pp.2882–2890, Oct. 2003.
[8]

C. Takano, M. Aida, and S. Kuribayashi, “Au-いた．実ネットワークに DFC を実装するためには，

tonomous decentralized ﬂow control in high-speed

ノードを通過するアクティブフロー数の情報をノード

networks with inhomogeneous conﬁgurations,” IEICE Trans. Commun., vol.E87-B, no.6, pp.1551–

が自律的に取得できる枠組みにする必要がある．
本論文では DFC の実装可能性を確かめるため ns2

1560, June 2004.
[9]

C. Takano and M. Aida, “Diﬀusion-type autonomousに DFC 機能を組み込み，自律分散制御として実装可

decentralized ﬂow control for end-to-end ﬂow in high-能であるかどうか検討を行った．その結果，従来のspeed networks,” IEICE Trans. Commun., vol.E88-B,

DFC の枠組みではノードの通過フロー数の情報を適

no.4, pp.1559–1567, April 2005.
[10]

C. Takano, K. Muranaka, K. Sugiyama, and M. Aida,

切に取得することができないため，ネットワーク内に“Mutual complementarity of diﬀusion-type ﬂow con-

流入するパケット数を制御する機構が正しく動作せ

trol and TCP,” IEICE Trans. Commun., vol.E89-B,

ず，ネットワークがふくそう状態から回復するまでに時間がかかってしまうことが分かった．これを解決す

no.10, pp.2850–2859, Oct. 2006.
[11]

C. Takano, K. Muranaka, K. Sugiyama, and M. Aida,“Parameter design for diﬀusion-type autonomous de-るために，フィードバック情報として通知される転送

centralized ﬂow control,” Lecture Notes in Computer

レートの制限方法にを改良し，更にノード自身が通過

Science, vol.4238, pp.461–470, Springer-Verlag Hei-

するアクティブフロー数を計測する方法を改良した．

delberg, 2006.
[12]

この改良により，DFC の実装に関して従来 weighted
round robin が必要であったパケットスケジューリン
グ部分を，単純な FIFO で置き換える単純化が可能となった．また，改良した DFC の特性を ns2 によりシ
ミュレーションを行い，その効果を実証した．

C. Takano and M. Aida, “Diﬀusion-type autonomous
decentralized ﬂow control for multiple ﬂows,” IEICE
Trans. Commun., vol. E90-B, no.1, pp.21–30, Jan.
2007.

[13]

The Network Simulator—ns2.
http://www.isi.edu/nsnam/ns/（平成 20 年 1 月 15 日受付，5 月 13 日再受付）

謝辞 本研究の一部は，情報通信研究機構（NICT）の委託研究「新世代ネットワークの構成に関する設計・評価手法の研究開発」により実施した．
文
[1]

高野

献

Y. Bartal, J. Byers, and D. Raz, “Global optimization using local information with applications to ﬂow

平 12 阪大・工・電子通信卒．平 20 首都大東京大学院博士後期課程了．平 12 NTT

tions of Computer Science, pp.303–312, Oct. 1997.

アドバンステクノロジ（株）入社．平 20
広島市大大学院・情報科学研究科・准教授．

S.H. Low and D.E. Lapsley, “Optimization ﬂow

通信トラヒック制御，自律分散制御技術のcontrol,” Proc. 38th Ann. IEEE Symp. on Founda[2]知佐 （正員）

control-I:

Basic

algorithm

andconvergence,”

IEEE/ACM Trans. Netw., vol.7, no.6, pp.861–874,

研究に従事．平 14 本会学術奨励賞，平 15
本会情報ネットワーク研究賞受賞．

1265

電子情報通信学会論文誌 2008/10 Vol. J91–B No. 10

山内

正志 （正員）平 18 都立科技大・工・生産情報システム
工卒．在学中は自律分散制御技術の研究に従事．現所属はトーワシップ債権回収（株）．

会田

雅樹 （正員）昭 62 立教大・理・物理卒．平元同大大学院博士課程前期原子物理学専攻了．同年
日本電信電話（株）入社．平 17 首都大東
京・システムデザイン学部・准教授．平 19
同大大学院・システムデザイン研究科・教授．博士（工学）．通信トラヒックの設計技
術，通信品質計測技術，自律分散制御技術，通信トラヒックのべき乗則の研究に従事．日本 OR 学会，IEEE 各会員．

1266