論文

DiﬀServ 領域における end-to-end の確定的遅延上界に関する研究中村 博貴†

中川 健治†† a)

A Study on Deterministic End-to-End Delay Bounds for a Flowin DiﬀServ Network Domain
Hirotaka NAKAMURA† and Kenji NAKAGAWA††a)

あらまし インターネットにおいて通信の品質（Quality of Service）が近年重要な課題となっている．リア
ルタイムアプリケーションにとってネットワークにおける端末間遅延は QoS における重要な要素である．本論
文では，IP ネットワークの DiﬀServ（Diﬀerentiated Service）領域における端末間パケット遅延時間の確定的な上界を求めることを目的とする．従来の遅延上界の導出として，フローの多重ノードや具体的なトラヒック量などの細かなフロー情報を利用した方式と，細かなフロー情報を利用しない方式とがある．本論文では，それぞれの場合に対する，新たな遅延上界導出法を提案する．そして，様々な条件において提案法と従来法を比較し，提案法が精度の良い上界であることを示す．
キーワード

DiﬀServ，確定的遅延上界，トークンバケット

1. ま え が き

間遅延を知ることが必要である．つまり，今後のネッ

インターネットの普及に伴い，通信の品質（Qual-

クにおける端末間遅延の上界を解析することがリアル

ity of Service）が重要な課題となっている．この問題を解決するため，IETF（Internet Engineering Task
Force）は best-eﬀort に代わる新たなアーキテクチャを考えた．その代表的なものとして IntServ（Integrated

タイムアプリケーションの提供に対して重要となってトワークについても考慮すると，DiﬀServ ネットワー

くる．そこで本論文では，DiﬀServ ネットワークにおける end-to-end の確定的遅延上界の解析を行う．この確定的遅延上界の導出においてはいくつかの方式がService）と DiﬀServ（Diﬀerentiated Service）がある
が，QoS に対する可能な解決として現在 DiﬀServ が提案されているが，フローのパス情報を利用した場合注目されていて幅広く受け入れられている．

きる．ここで，パス情報を利用した場合とは，あるフとパス情報を利用しない場合の二つに分けることがで

近年増加しているトラヒックとして，IP 電話や遠ローが他のフローとどのノードで何本多重するかな

隔会議などのリアルタイム通信がある．これらは音

ど，各フローのネットワーク内の経路情報を利用した声・画像の通信であり，遅延に敏感なアプリケーショ

場合であり，遅延上界の精度は高いが多くの情報を必ンである．そのため，ネットワークの遅延が大きすぎ要とする．また，パス情報を利用しない場合とは，各るとサービスが成り立たなくなってしまう．そこで，フローのネットワーク内の経路情報を利用しない場合

コネクション受付制御が必要となる．そしてこの受付であり，遅延上界の精度は悪くなるが遅延上界導出に制御を行うためには，各フローのネットワーク内端末

おいて必要な情報が少ない．
パス情報を利用した遅延上界導出法には Jiang [3]，†Kim [1] の方式がある．Jiang [3] は，DiﬀServ におけCEC 新潟情報サービス株式会社，新潟市
CEC Niigata Information Service, 2–10–6 Abumi, Chuo-ku,
Niigata-shi, 950–0913 Japan

††の方式は，ノードへ入力する複数のフローをターゲッ

長岡技術科学大学・電気系，長岡市
Department of Electrical Engineering, Nagaoka Universityof Technology, 1603–1 Kamitomioka, Nagaoka-shi, 940–2188
Japana) E-mail: nakagawa@nagaokaut.ac.jp

440

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

る多重ネットワークに対する遅延上界を提案した．こトフローと多重フローとに分けて考え遅延上界を導出する方式である．Kim [1] は，Jiang [3] と同様にター
ゲットフローと多重フローとを分けた方式を提案しc （社）電子情報通信学会 2008
No. 4 pp. 440–449 論文／DiﬀServ 領域における end-to-end の確定的遅延上界に関する研究

た．Jiang [3] による上界と異なる点は，多重フローがターゲットフローの遅延へ与える影響を待ち時間（Latency）として考えて遅延上界を導出したところである．この方式は LR サーバ [2] の概念を DiﬀServ 領域に適用させたものであり，遅延上界の導出が非常に簡単で他の方式よりも精度が良いが，実測値（シミュレーション値）と比べるとまだ差がある．
パス情報を利用しない（任意のネットワークトポロ

図 1 DiﬀServNetwork
Fig. 1 DiﬀServNetwork.

ジーに適用できる）遅延上界導出法には Charny [5]や Jiang [3] などの方式がある．Charny [5] はネット
ワークの最大リンク利用率である α と最大バースト処
理時間である β を利用し，仮想的に遅延が最も大きくなるノードを考え，それをネットワークの最大ホップ
数倍することにより遅延上界を導出した．しかし，この方式は α が小さくないと遅延上界が発散してしまうという問題点がある．Jiang [3] はリンク容量によるト
ラヒックの上限を考慮することにより，Charny [5] による上界の精度を向上させ，利用できる α の値を大き

図 2 トークンバケット
Fig. 2 Token bucket.

くした．しかし，α の増加による遅延上界の発散に関しては解決できていない．

ここで，トークンとは許可信号であり，バケットと本論文では，DiﬀServ 領域において，細かなパス情

はトークンをためるバッファである．まず，トークン

報を利用した場合と細かなパス情報を利用しない（任はトークン生成レート ρ に従って生成され，サイズ σ

意のトポロジーに適用できる）場合の二つを考える．

のバケットに格納される．そして，リーキーバケット

パス情報を利用した場合では，従来法として Kim [1]に到着したトラヒックは，トークンを受け取ったもの

による上界と Jiang [3] による上界を考え，従来法よりだけ通過することができる．つまり，トークンを通過も精度を向上させた遅延上界の導出を行う．また，パスしたトラヒックは最大バースト長 σ [Byte]，平均レー情報を利用しない場合では，従来法として Charny [5]ト ρ [bit/s] 以下に整形され出力されることになる．こによる上界と Jiang [3] による上界を考え，リンク利の方式を利用すると，バケットサイズ以上連続するパ用率の増加に伴う遅延上界の発散の問題点を解決した

ケットが通過できなくなり，バースト的なトラヒック

新たな遅延上界の導出を行う．

を平滑化することができる．

1. 1 DiﬀServ ネットワーク
図 1 に示すように，DiﬀServ（Diﬀerentiated Ser-

vices）ネットワークではエッジルータと内部ルータの2. 利用するネットワークモデル
本論文で利用するネットワークは DiﬀServ 領域を考二つが存在する．エッジルータでは，ユーザとネット

える．ネットワークに入力するフロー i はすべて入力

ワーク間の事前の契約に基づいたトラヒックの識別，

ノード（エッジルータ）においてバケットサイズ σi ，少数のクラスへの分類，クラスに応じた優先度情報のトークン生成レート ρi のトークンバケット整形が適

DSCP（Diﬀerentiated Services Code Point）フィー

用される．また，ネットワークのすべてのリンク容量

ルドへの記述，そしてトラヒックシェーピングなどがを C とし，安定のため任意のノード k における同ク行われる．内部ルータでは，DSCP に応じた優先制

ラスのフローの平均レートの和がクラスに分配された

御，廃棄処理を行い，クラス間の QoS を差別化した

帯域以下となるように多重数を規制する．つまり，全パケット転送が行われる．ここでの処理は PHB（Per

クラスの平均レートの和は常に C 以下とする．

Hop Behavior）に従う．
1. 2 トークンバケット（Token Bucket）
図 2 にトークンバケット方式の概念図を示す．
441

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

3. パス情報を利用した上界の Kim [1] による上界のほかに Jiang [3] による上界

3. 1 Kim [1] による遅延上界をターゲットフローと多重フローとに分けて考え，遅がある．この方式は，ノードに入力する複数のフロー

Kim [1] は LR サーバの概念を DiﬀServ 領域に発展させ，end-to-end の遅延上界を導出した．この遅延上延上界を導出する方式である．

界は，ターゲットフローに多重される同クラス内のフトークンバケットによって整形されているとする．そローの影響を待ち時間（Latency）として考えている．

して，ノード k に入力する多重フローの入力リンク帯

そうすることで，LR サーバの概念を利用することが域の和を Cc とし，ターゲットフローのパス上のリンあるノード k に入力するクラス l のフローはすべてできる．ここでは Kim [1] による遅延上界について記

ク帯域を C0 とする．また，ノードへ入力する多重フ述する．

ローのバースト長の和を σc ，平均レートの和を ρc と

3. 1. 1 記号とその定義

し，ターゲットフローのバースト長を σ0 ，平均レート

まずはじめに，使用される記号とその定義についてを ρ0 とする．このとき，直列に K 個並んだノードにおける end-to-end の遅延 D0 に対する Jiang [3] によ

まとめたものを表 1 に示す．

3. 1. 2 end-to-end の遅延上界

る上界は次式で与えられる．

K 個の LR サーバ（Latency=Θkl , Rate=Rlk ,1 ≤k ≤ K ）が直列につながったネットワークにおいて，あるクラス l について考える．クラス l のフローはすD0 ≤べてトークンバケットによって整形されている．ター4. パス情報を利用しない遅延上界

ゲットフローのトークンパラメータを (σ0 , ρ0 ) とす

K

k=1

Cc
(σ0 + kσc )·(C0 + Cc ) − (ρ0 + ρc ) C0(2)

ると，このネットワークにおけるターゲットフローのDiﬀServ 領域における任意のネットワークに対する

end-to-end の遅延 D0 に対する Kim [1] による上界は

end-to-end の確定的遅延上界を導出した従来法として，Charny [5] や Jiang [3] の方式がある．ここでは，次式で与えられる．

D0 ≤



σ0

mink∈K Rlk −
+

⎧
⎨

k∈K


i∈F (k)ρi

それらの方式について記述する．



⎫
⎬

σi · I{k=ni }
Θkl +
Bi
⎩
⎭

4. 1 最大ネットワークリンク利用率 α，最大バー
スト処理時間 β
ネットワークに入力するフロー i は，エッジルータ(1)i∈F (k)

ここで，I は k = ni のとき 1，それ以外のときは 0 の指示関数である．

3. 2 Jiang [3] による遅延上界パス情報を利用した遅延上界導出法として，式 (1)表 1 記号とその定義
Table 1 Symbol and deﬁnition.
記号
K
F (k)
ni
Rk
l
Θk
l
B(k)i
Bi
σi
ρi

442

定義
ターゲットフローの end-to-end パス上のノード数
ノード k でターゲットフローと多重化されるフローの集合（k = 1, 2, · · ·, K ）フロー i のエントリノード
ノード k でクラス l に与えられた分配帯域
ノード k でクラス l が受けるスケジューラによる待ち時間
ノード k でのフロー i の最低保証帯域
フロー i の最低保証帯域
フロー i のバースト長（トークンパラメータ）
フロー i の平均レート（トークンパラメータ）

においてパラメータ (σi , ρi ) のトークンバケットによって整形されるとする．また，エッジルータの番号の集合を E = {1, · · · , n} とする．そして，E から j 個を取る組合せの集合を Ej とする．このとき，Ej の要素
を s とし，出力リンク帯域 C （または分配帯域）をも

つ任意のノード k において，i∈sρi ≤ C の条件で次式を定義する．

α=


1
max
ρi
s∈E
C
j
1≤j≤n

(3)

i∈s

この α は最大ネットワークリンク利用率と呼ばれ，

0 < α < 1 である．また，式 (3) の最大値を達成する
フローの集合 Ej のバーストパラメータを利用することにより次式を定義する．

β=

j

σi
i=1

C

β は最大バースト処理時間と呼ばれる．

(4)

論文／DiﬀServ 領域における end-to-end の確定的遅延上界に関する研究

4. 2 Charny [5] による遅延上界

るのでこれは自然な考え方である．しかし，Kim によ最大ネットワークリンク利用率を α，最大バースト

る上界は入力トラヒックの上限値は無限大である．す処理時間を β とする．ネットワークを渡る任意のフ

なわち，フローのバーストが一気にノードに入力する

ローの中で，最長パスをもつフローのホップ数（ネットと考えている．そこで，Kim による上界が実測値と比ワーク直径）を K とすると，任意のトポロジーをもつ

べまだ誤差が大きい原因はここにあると考え，本研究DiﬀServ ネットワークにおける任意のパケットの遅延

では Kim による上界にデュアルリーキーバケットのD に対する Charny [5] による上界は α < 1/(K − 1)

概念を導入することによって新たな遅延上界を導出すの条件のもとで，次式で与えられる．

る．トラヒックの上限を考慮すると，次の定理を述べ

D≤K

β1 − (K − 1)αることができる．

(5)

4. 3 Jiang [3] による遅延上界
Jiang [3] は入力リンク帯域が有限である場合を考え，Charny [5] による遅延上界を改良し，利用できる
リンク利用率を大きくした遅延上界を導出した．
最大ネットワークリンク利用率を α，最大バースト
処理時間を β とする．ネットワークを渡る任意のフローの中で，最長パスをもつフローのホップ数（ネットワーク直径）を K とすると，任意のトポロジーをもつ DiﬀServ ネットワークにおける任意のパケットの［定理 1］ K 個の LR サ ー バ（Latency=Θkl , Rate

=Rlk , 1 ≤ k ≤ K ）が直列につながったネットワーク
において，あるクラス l について考える．クラス l のフ
ローはすべてトークンバケットによって整形されている．
トークンパラメータ (σ0 , ρ0 ) をもつターゲットフロー


の保証レートを g0 = mink∈K Rlk −Cb + Cin(K − 1)Cin + Cb

ρi と

遅延 D0 に対する上界は次式で与えられる．



D0 ≤

C − g0C − ρ0



⎧
⎨

σ0
g0



⎫
⎬

σ
·
I
i
{k=ni }
+
Θkl +
Bi
⎩
⎭
k∈K

(6)

(8)

i∈F (k)（証明） ターゲットフローの待ち時間として，Θ を次

の条件で

K(uβ)
D≤
1 − (K − 1)uαi∈F (k)

したとき，このネットワークにおける end-to-end の

遅延 D に対する Jiang [3] による上界はα≤

式によって定義する．

(7)

で与えられる．ここで Cin はノードへの入力リンク
帯域，Cb はノードの出力リンク帯域（ボトルネック帯域）である．また，u = Cin /(Cin + (1 − α)Cb ) である．

5. 提 案 法
5. 1 パス情報を利用した遅延上界
Kim [1] によるパス情報を利用した遅延上界は他の方式よりも導出方法が簡単であり，他の方式よりも精度が良いが，実測値（シミュレーション値）と比べるとまだ誤差が大きい．そこで，本研究では Kim [1] による遅延上界の精度を向上させることを考えた．
文献 [2] において，デュアルリーキーバケットを用いた場合の遅延上界について示している．これは，入力トラヒックの上限値が既知であるという概念である．
実際のネットワーク環境を考えた場合，トラヒックの上限値というものはリンク容量によって制限されてい

Θ=

⎧
⎨

k∈K

⎫
⎬

σ
·
I
i
{k=ni }
Θkl +
Bi
⎩
⎭
i∈F (k)ターゲットフローは (σ0 , ρ0 ) 整形されており，リンク容量は C であるので，区間 (τ, t) の間にネットワー
クの入力に到着するトラヒック量 Λ0 (τ, t) は

Λ0 (τ, t) ≤ min {σ0 + ρ0 (t − τ ), C(t − τ )}

(9)

となる．
次に，D0p を時刻 tp0 にネットワークの入力に到着したターゲットフローのパケット p が経験する end-to-end の遅延とする．つまり，tp0 + D0p 後にパケット p
はネットワークからサービスされる（ネットワークを出る）．したがって，時刻 tp0 までに到着したターゲッ
トフローのトラヒック量は，時刻 tp0 + D0p までにサービスされたターゲットフローのトラヒック量と等しい．
p

よって，区間 (τ, t0 ) を考えると，

W0 (τ, tp0 + D0p ) = Λ(τ, tp0 )

(10)
443

電子情報通信学会論文誌 2008/4 Vol. J91–B No. 4となる．また式 (9) より，

まうという問題点をもっている．そこで本研究では，

W0 (τ, tp0 +D0p ) = min {σ0 +ρ0 (tp0 −τ ), C(tp0 −τ )}(11)

5. 1 で述べたパス情報を利用した遅延上界をパス情報を利用しない遅延上界に発展させることにより，この問題を解決する．つまり，式 (8) と Charny [5] による上界を組み合わせた新たな遅延上界を提案する．式 (8)LR サーバの定義より，と Charny [5] による上界を組み合わせると，次の定W0 (τ, tp0 + D0p ) ≥ g0 (tp0 + D0p − τ − Θ)

(12)

理として述べることができる．
［定理 2］ K 個の LR サーバ（Latency=Θkl , Rate=

式 (11)，式 (12) より，

Rlk ,1 ≤ k ≤ K ）が直列につながったネットワークにおg0 (tp0 + D0p − τ − Θ)いて，あるクラス l について考える．クラス l のフロー

(13)

はすべてトークンバケットによって整形されている．

• ケース 1：C(tp0 − τ ) ≤ σ0 + ρ0 (tp0 − τ ) のときとし，トークンパラメータ (σ0 , ρ0 ) をもつターゲット

式 (13) より，

フローの保証レートを g0 = Rl − (αRl − ρ0 ) とする≤ min {σ0 + ρ0 (tp0 − τ ), C(tp0 − τ )}


D0p ≤

C − g0g0

(tp0 − τ ) + Θと，このネットワークにおける end-to-end の遅延 D0(14)

ここで，C(tp0 − τ ) ≤ σ0 + ρ0 (tp0 − τ ) より，tp0 − τ ≤
σ0
なので，
C−ρ0



D0p ≤

C − g0C − ρ0



σ0
g0

(16)

ので，



(17)

（証明） パス情報を利用しない遅延上界を導出するため，Charny [5] による上界で使用されている最大ネッ
トワークリンク利用率 α，最大バースト処理時間 β を
Rl = mink∈K Rlk として次式 (18)，(19) で定義する．
ただし，記号と平均レートの和の条件は前節を参照の
こと．

β=

 σi
i∈s



Rl


ρi + ρ0

(18)

i∈s

+ σ0

(19)

提案法はターゲットフローが通過するパス上を考えているので，α と β の構成の中にはターゲットフローのパラメータ σ0 ，ρ0 が入っている．



式 (18)，式 (19) において，ターゲットフロー以外+Θのフローを多重フローの集合 F (k) として考えると，

2
5. 2 パス情報を利用しない遅延上界パス情報を利用しない（任意のネットワークトポロ
ジーに適用できる）遅延上界導出法には Charny [5] やJiang [3] などの方式があるが，どちらの上界も，最大リンク利用率が増加していくと遅延上界が発散してし
444

σ0
g0

K
Θ(k) +(βRl − σ0 )
Rl

1≤j≤n

σ0 (C − ρ0 ) − σ0 (g0 − ρ0 )+Θ≤g0 (C − ρ0 )
≤

k=1

1
α=
max
Rl s∈Ej

σ0(g0 − ρ0 )σ0+Θ−g0
g0 (C − ρ0 )

σ0
g0

 K






σ0
(g0 − ρ0 )≤ σ0 − g0 D0p + g0 Θ
C − ρ0(g0 − ρ0 )σ0+ g0 Θ
g0 D0p ≤ σ0 −C − ρ0D0 ≤C − g0C − ρ0(15)

σ0
なC(tp0 − τ ) > σ0 + ρ0 (tp0 − τ ) より，tp0 − τ > C−ρ0

C − g0C − ρ0++Θ(g0 − ρ0 )(tp0 − τ ) ≤ σ0 − g0 D0p + g0 Θに対する上界は次式で与えられる．

• ケース 2：C(tp0 − τ ) > σ0 + ρ0 (tp0 − τ ) のとき
式 (13) より

D0p ≤ネットワークのリンク容量はすべて Rl = mink∈K Rlk

ρ0 +



ρi ≤ αRl(20)

σi ≤ βRl(21)i∈F (k)σ0 +i∈F (k)となる．

論文／DiﬀServ 領域における end-to-end の確定的遅延上界に関する研究

式 (8) における保証レート g0 は次のようなものであった．

⎛
g0 = min ⎝Rlk −
k∈K

⎞



ρi ⎠

(22)

i∈F (k)図 3 ネットワークトポロジー
Fig. 3 Network topology.

上式を書き換えると



g0 = Rl − max
k∈K

ρi

(23)

i∈F (k)

遅延上界は真値の遅延上界に対して常に危険側となる．
一方，理論的に導出する遅延上界は真値に対して常にまた，式 (20) より

max
k∈K



安全側となる．つまり，シミュレーションによる遅延

ρi ≤ αRl − ρ0(24)

上界と理論的遅延上界との間に真値が存在することになる．よって，シミュレーション値を性能目標とする

i∈F (k)ことにより，理論的遅延上界の精度を調べることがで
式 (24) を式 (23) に代入してきる．

g0 ≥ Rl − (αRl − ρ0 )(25)

6. 1 パス情報を利用した遅延上界のシミュレーションを得る．式 (8) の右辺の第 3 項における指示関数 I は，

6. 1. 1 ネットワークモデル

多重ノードにおいてのみ，待ち時間を加算するための

図 3 に利用するネットワークトポロジーを示す．

ものである．フローのパス情報がない場合，すべての

図 3 に お い て ，N1 , · · · , NK は パ ラ メ ー タ

ノードが多重ノードである場合が考えられる．そこK(Θ1l , Rl1 ), · · · , (ΘKl , Rl ) をもつ LR サーバで，クラス単位の WFQ（Weighted Fair Queueing）を行う．
クラスごとの重みは 1 とする．各ノードへのアクセ
スリンクの容量は Cin であり，ボトルネックリンクので最長パスをもつフローのホップ数（ネットワーク直径）を K とし，多重ノードの遅延を K 倍すると考えると，

  σi · I{k=n }i
Bik∈K i∈F (k)

 σi

≤K

i∈F (k)Rl(26)

クラス ltarget であり，f0 , f1 , · · · , fK からなる．f0 がターゲットフローで，f1 , · · · , fK は多重フローであここに式 (21) を代入すると

K σii∈F (k)Rl≤

K(βRl − σ0 )Rlる．これらのフローはすべてトークンバケット整形さ(27)

れており，パラメータ (σ0 , ρ0 ), (σ1 , ρ1 ), · · · , (σK , ρK )をもつ．もう一つのクラスはターゲットクラスではな

式 (25) と式 (27) を式 (8) に代入することで，定理の上界が得られる．

容量は Cb である．また，ネットワークにおいてクラスが二つある場合を考える．一つはターゲットフロー

2

6. 従来の上界及びシミュレーション値との比較

いクラス lother とする．このとき，ターゲットフロー

f0 の end-to-end の遅延上界を測定する．また，各結果に対する考察はまとめて次節で示すことにする．

6. 1. 2 シミュレーション 1-1：多重フローのバー
スト σ1 , · · · , σK を変化させたときの比較

ここでは，パス情報を利用した場合と利用しない場

ここでは，多重フローのバーストを変化させた場合合との二つの場合における従来法と提案法との比較をにおける従来法と提案法との比較を行う．具体的なシ行うため，シミュレーションを行う．シミュレーショ

ミュレーションパラメータを表 2 に示す．今回はノー

ンには ns-2 を用いた．

ド数 K = 2 とした．そして，シミュレーション結果

一般に，計算機シミュレーションにおいては，サンを図 4 に示す．

真値を無限時間シミュレーションにおいて得た遅延上

6. 1. 3 シミュレーション 1-2：多重フローの平均
レート ρ1 , · · · , ρK を変化させたときの比較界とすると，有限時間シミュレーションにより求めた

ここでは，多重フローの平均レートを変化させた場

プル数によって遅延の上限値は変化する．そのため，

445

電子情報通信学会論文誌 2008/4 Vol. J91–B No. 4
表 2 シミュレーション 1-1 の各パラメータ
Table 2 Parameter of simulation 1-1.
CinCb

Θ1ltarget , Θ2ltarget R1ltarget , R2ltarget

表 4 シミュレーション 1-3 の各パラメータ
Table 4 Parameter of simulation 1-3.
CinCb

Θ1ltarget , Θ2ltarget R1ltarget , R2ltarget

10[Mbit/s] 20[Mbit/s]

0.45[ms]

10[Mbit/s]

10[Mbit/s] 20[Mbit/s]

0.45[ms]

10[Mbit/s]

σ0ρ030[kByte] 3[Mbit/s]

σ1 , σ2
20〜100[kByte]ρ1 , ρ2
2[Mbit/s]

σ0ρ030[kByte] 3[Mbit/s]

σ1 , σ220[kByte]

ρ1 , ρ2
2[Mbit/s]

図 4 シミュレーション 1-1 の結果
Fig. 4 Result of simulation 1-1.

図 6 シミュレーション 1-3 の結果
Fig. 6 Result of simulation 1-3.

表 3 シミュレーション 1-2 の各パラメータ
Table 3 Parameter of simulation 1-2.
CinCb

Θ1ltarget , Θ2ltarget R1ltarget , R2ltarget

10[Mbit/s] 20[Mbit/s]

0.45[ms]

10[Mbit/s]

σ0ρ030[kByte] 3[Mbit/s]

σ1 , σ220[kByte]

ρ1 , ρ2
1〜7[Mbit/s]

図 7 ネットワークトポロジー
Fig. 7 Network topology.

6. 1. 4 シミュレーション 1-3：ノード数を変化させたときの比較
ここでは，ノード数を変化させた場合における従来法と提案法との比較を行う．具体的なシミュレーショ
ンパラメータを表 4 に示す．そして，シミュレーショ
図 5 シミュレーション 1-2 の結果
Fig. 5 Result of simulation 1-2.

ン結果を図 6 に示す．

6. 2 パス情報を利用しない遅延上界のシミュレー
ション

シミュレーションパラメータを表 3 に示す．今回ノー6. 2. 1 ネットワークモデル
図 7 に利用するネットワークモデルを示す．また，

ド数は K = 2 とした．ここで，多重フローの変化の

図 8 にシミュレーションで利用するネットワークモデ

範囲が 7 [Mbit/s] までなのは，7 [Mbit/s] のときリンルを示す．

合における従来法と提案法との比較を行う．具体的な

ク利用率が 1 になるためである．そして，シミュレー
ション結果を図 5 に示す．
446

図 7 はホップ数 K の DiﬀServ ネットワークに三つのフローが入力するモデルである．三つのフローは

論文／DiﬀServ 領域における end-to-end の確定的遅延上界に関する研究
表 6 シミュレーション 2-2 の各パラメータ
Table 6 Parameter of simulation 2-2.

図 8 シミュレーションで利用するネットワークトポロジー
Fig. 8Cin
10 [Mbit/s]

Cb
10 [Mbit/s]

α
0.2

β
0.025〜0.25

σ030 [kByte]ρ0
1 [Mbit/s]

σ1 , σ2
β に合わせ決定ρ1 , ρ2
0.5 [Mbit/s]

Network topology of simulation.

表 5 シミュレーション 2-1 の各パラメータ
Table 5 Parameter of simulation 2-1.
Cin
Cb
10[Mbit/s] 10[Mbit/s]

α0.1〜1.0

β
0.052

σ0
ρ0
σ1 , σ2ρ1 , ρ2
30[kByte] 1[Mbit/s] 20[kByte],15[kByte] α に合わせ決定

図 10 シミュレーション 2-2 の結果
Fig. 10 Result of simulation 2-2.
表 7 シミュレーション 2-3 の各パラメータ
Table 7 Parameter of simulation 2-3.
Cin
Cb
10 [Mbit/s] 10 [Mbit/s]

図 9 シミュレーション 2-1 の結果
Fig. 9 Result of simulation 2-1.

α
0.2

β
0.052

σ0
ρ0
σ1 , σ2ρ1 , ρ2
30 [kByte] 1 [Mbit/s] 20 [kByte],15 [kByte] 0.5 [Mbit/s]

ネットワークの入り口においてトークンバケット整形（(σ0 , ρ0 ), (σ1 , ρ1 ), (σ2 , ρ2 )）される．パスを利用しない遅延上界における従来法は，DiﬀServ 領域におけるEF フローの遅延上界を導出したものであるため，こ
こでは待ち時間 Θkl をゼロとし，EF フロークラスのみを考える．

6. 2. 2 シミュレーション 2-1：最大ネットワーク
リンク利用率 α を変化させたときの比較
ここでは，最大ネットワークリンク利用率 α を変化させた場合における従来法と提案法との比較を行う．
今回はノード数 K = 4 とした．具体的なシミュレー
ションパラメータを表 5 に示す．そして，シミュレー

図 11 シミュレーション 2-3 の結果
Fig. 11 Result of simulation 2-3.

ション結果を図 9 に示す．

6. 2. 3 シミュレーション 2-2：最大バースト処理
時間 β を変化させたときの比較
ここでは，最大バースト処理時間 β を変化させた場合における従来法と提案法との比較を行う．今回はノード数 K = 4 とした．具体的なシミュレーション

パラメータを表 6 に示す．そして，シミュレーション
結果を図 10 に示す．

6. 2. 4 シミュレーション 2-3：ノード数を変化させたときの比較
ここでは，ノード数を変化させた場合における従来447

電子情報通信学会論文誌 2008/4 Vol. J91–B No. 4法と提案法との比較を行う．具体的なシミュレーショ

0.33）があるため，その値に近づくと遅延上界が発散

ンパラメータを表 7 に示す．そして，シミュレーショ

していることが分かる．Jiang による上界は Charny

ン結果を図 11 に示す．

による上界を改良したものであるので，Charny によ

7. 考

察

る上界よりも高いリンク利用率が利用できることが分かる．しかし Jiang による上界にも，リンク利用率に

7. 1 シミュレーション 1-1 の考察(Cb + Cin )/((K − 1)Cb + Cin ) という制限（今回の図 4 を見ると，提案法は従来法よりも精度が良く条件だと 0.5）があるため，遅延上界の発散が起こっなっていることが分かる．しかし，多重フローのバーている．これらに対し，提案法はリンク利用率が 1.0

ストが増加したときの遅延上界の増加幅は，Kim によの場合においても遅延上界の発散が起こっておらず，る上界・提案法ともに同じことが分かる．これは，提精度も良い．これは，Kim による上界のターゲットフ

案法が多重フローの影響を待ち時間として考えている

ローと多重フローとを分けた考え方のためである．つためである．つまり，多重フローのバーストの影響はまり，従来法に見られるノード遅延の足しすぎを抑え

Kim による上界と同様の考えを利用しているためである．そのため，今回のシミュレーションでは Kim にた結果，精度の良い値となったといえる．

よる上界のグラフをシミュレーション値側にシフトした形になっている．

7. 5 シミュレーション 2-2 の考察
図 10 を見ると，提案法は従来法よりも精度が良くなっていることが分かる．従来法，提案法ともに β は

7. 2 シミュレーション 1-2 の考察

分子にあるため，遅延上界の増加は線形になっている．

図 5 を見ると，提案法は従来法よりも精度が良く

しかし，提案法はこの β からターゲットフローのトーなっていることが分かる．しかし，多重フローの平均

クンパラメータ σ0 を引いており，ターゲットフロー

レートが 7 [Mbit/s] のとき，すなわち，ボトルネックと多重フローとを分けて計算しているため，従来法よリンクのリンク利用率が 1 となったとき，提案法とりも精度の良い遅延上界となっている．

Kim による上界は同じ値になっている．これは，リン

7. 6 シミュレーション 2-3 の考察

ク利用率が 1 になると提案法の式と Kim による上界

図 11 を見ると，提案法は従来法よりも精度が良くの式とが同じになってしまうためである．更に，リンなっていることが分かる．従来法はリンク利用率の制

ク利用率が 1 に近づくにつれ，Jiang による上界の方限値にノード数が含まれている．そのため，リンク利が提案法よりも精度が良くなっている．これも提案法

用率 α を固定し，ノード数を増やしていくと制限値の改善点が消えてしまったためといえる．

に近づいていくことになるため，遅延上界の増加幅が7. 3 シミュレーション 1-3 の考察

徐々に増加していってしまう．それに対し提案法は，リ

図 6 を見ると，提案法は従来法よりも精度が良く

ンク利用率に対する制限がなく，リンク利用率とノーなっていることが分かる．ここで，シミュレーション

ド数との間になんの関係もないため，ノード数が増え値に注目してみると，遅延上界はほぼ一定値である．

ても遅延上界が一定の増加となったといえる．

これは，ターゲットフローのバーストの弱まりによるものであるといえる．ターゲットフローは複数のノー

8. む す び

ドを通過するため，各ノードでフローが合流すること

本論文では，DiﬀServ 領域における end-to-end のになる．その結果，ターゲットフローのパケット間に確定的遅延上界を，パス情報を利用した場合とパス情

多くのすき間ができる（バーストが弱まる）ことにな報を利用しない場合とで解析した．そして，それぞれり，このような結果になったといえる．提案法・従来の場合における従来法の問題点を解決した新たな遅延法ともにバースト性の弱まりについては考慮していな

上界を提案した．また，提案法が従来法の問題点を解いため，ノードの増加に対して遅延上界がほぼ一定増決し，更に精度が良いことを ns-2 を用いたシミュレー

加している．

ションによって示した．

7. 4 シミュレーション 2-1 の考察
図 9 を見ると，提案法は従来法よりも精度が良く

文
[1]

献

G. Kim and C. Kim, “Deterministic edge-to-edge de-なっていることが分かる．Charny による上界はリン

lay bounds for a ﬂow under latency rate schedul-

ク利用率に 1/(K − 1) という制限（今回の条件だとing in a DiﬀServ network,” IEICE Trans. Commun.,448

論文／DiﬀServ 領域における end-to-end の確定的遅延上界に関する研究
vol.E88-B, no.7, pp.2887–2895, July 2005.
[2]

D. Stiliadis ans A.Varma, “Latency-rate servers: A
general model for analysis of traﬃc scheduling algorithms,” IEEE/ACM Trans. Netw., vol.6, no.5,
pp.611–624, Oct. 1998.

[3]

Y. Jiang and Q. Yao, “Impact of FIFO aggregation
on delay performance of a diﬀerentiated services network,” ICOIN’03, pp.216–225, Feb. 2003.

[4]

Y. Jiang, “Delay bounds for a network of guaranteed
rate servers with FIFO aggregation,” Comput. Netw.,
vol.40, no.6, pp.684–694, Dec. 2002.

[5]

A. Charny and J.-Y. Le Boudec, “Delay bounds in a
network with aggregate scheduling,” Proc. First International Workshop of Quality of Future Internet
Services (QOFIS’2000), 2000.

（平成 19 年 3 月 19 日受付，8 月 27 日再受付）

中村博貴

平 17 長岡技科大・工・電気電子情報卒．
平 19 同大大学院修士課程了．同年 CEC
新潟情報サービス株式会社入社．

中川

健治 （正員）昭 55 東工大・理・数学卒．昭 60 同大大学院博士課程満期退学．昭 60 NTT 研究所入社．平 4 長岡技科大工学部助教授．待ち行列理論，ネットワーク特性評価，大偏差理論等の研究に従事．理博．IEEE，情報理論とその応用学会，日本 OR 学会，日本数学会，日本工業教育協会各会員．

449