電子情報通信学会論文誌 2009/5 Vol. J92–B No. 5

できるが，フロー数が増加するとすべてのフローに対
バースト長を考慮した確定的な end-to-end パケット
遅延上界し帯域を保証するのが難しくなり，ネットワークの拡

久保奈津美†

は，各フローへある程度の QoS 保証しかできないが，

中川健治†† a)（正員）

張に対応できないという問題点がある．一方 DiﬀServ

Deterministic End-to-End Delay Bounds of Packets Considering

フロー数が増えても決まったクラスのみ管理すればよ

Burst Length

いので，ネットワークの拡張への対応が容易であるとNatsumi KUBO† , Nonmember andKenji NAKAGAWA††a)いう利点がある．

, Memberend-to-end 確定的遅延上界導出法の従来の上界と†（株）フジシステムズ，横浜市

FUJI

SYSTEMS,INC.,

2–10–36

Kitasaiwai,

Nishi-ku,

Yokohama-shi, 200–0004 Japan††

して，Cruz [6] による上界がある．Cruz [6] は，ノードにおける入力トラヒックと出力トラヒックの差から

長岡技術科学大学・電気系，長岡市

Department of Electrical Engineering, Nagaoka University

ノードの最大キュー長を求め遅延上界を導出する方法

of Technology, 1603–1 Kamitomioka, Nagaoka-shi, 940–2188を提案した．この方式は，パラメータの大小関係によJapanり導出式が変化するため，フロー数が多くなっていくa) E-mail: nakagawa@nagaokaut.ac.jpと遅延上界の導出が複雑になってしまうという問題点がある．更に，フローごとの遅延上界導出法であり，あらましネットワークにおけるパケットの end-to-end 確定的遅延に対する上界について考察する．確定

DiﬀServ のようなクラス多重の場合に直接適用できない．

的遅延上界の研究として中村 [1]，Kim [2]，Cruz [6]，DiﬀServ 領域における end-to-end 確定的遅延上界導Jiang [7] 等がある．本研究では，多重フローの入力リ

出法の従来の上界として，中村 [1]，Kim [2]，Jiang [7]ンク容量がターゲットフローの入力リンク容量より小等による上界がある．これらの上界は，ともにノード

さいネットワークについて考える．そして，ターゲッに入力するフローをターゲットフローと多重フロー

トフローの最大バースト長が多重フローの最大バースに分けて考えている．ここで，ターゲットフローとは

ト長より短い場合，提案する上界が中村 [1] による上

end-to-end の遅延上界を求めるフローであり，多重界より精度良い上界が得られることを示す．

フローとはターゲットフローと多重化される同クラス

キーワード

確定的遅延上界，DiﬀServ，トークンのフローのことである．Kim [2] による上界では，多バケット，LR サーバ

重フローのバーストがターゲットフローに与える遅延

1. ま え が きは多重フローのエントリノードでのみで発生すると

近年，IP 電話や遠隔会議などの音声・画像を利用し考えている．また，ターゲットフローに与えられる帯

たリアルタイム通信が増加している．リアルタイム通域が一番狭いノードのみでターゲットフローのバース

信の普及により，遠隔地との交流が可能となった．しトによる遅延が発生するという LR サーバ [3] の性質

かし，ネットワークの遅延が大きくなると，会話がスを利用している．これにより，Kim [2] による上界はムーズにできなくなり満足なサービスが得られなくな

Jiang [7] による上界より多くの場合で精度良い上界がる．そのため，通信の品質 (Quality of Service) を保得られている．中村 [1] による上界では，Kim [2] によ

証するには，ネットワークの端末間の遅延を知ることる上界に更に入力トラヒックのリンク容量を考慮し，が必要である．

Kim [2] による上界より精度の良い上界が得られるよ

QoS 制御とは，ネットワーク上である特定のフロー

うに改善されている．

のための帯域を確保し，一定の通信速度を確実に保本研究では，中村 [1] による上界より精度良い端末間証する技術である．QoS 制御技術の代表的なものに，の確定的遅延上界を導出することを目的とする．そこ

IntServ (Integrated Services) と DiﬀServ (Diﬀeren-

で，多重フローの入力リンク容量がターゲットフロー

tiated Services) がある．IntServ が個別フローに対すの入力リンク容量より小さいネットワークについて考る性能保証を行うのに対し，DiﬀServ は個別フローをえる．そして，ターゲットフローの最大バースト長が複数の優先クラスに分類し，クラスごとにトラヒック

多重フローの最大バースト長より短い場合，提案するの優先制御を行うものである．IntServ はフローごと

上界が中村 [1] による上界より精度良い上界が得られに管理されるため厳格な QoS 保証を提供することがることを示す．

892

電子情報通信学会論文誌

c （社）電子情報通信学会 2009
B Vol. J92–B No. 5 pp. 892–897 

レ

タ

ー

本論文で考察する上記のモデルは，ターゲットフ
ローが音声や画像等のリアルタイムメディアトラヒッ

2. 3 解析するネットワークモデル
本研究で利用するネットワークは，DiﬀServ 領域をクであり，大容量で比較的 CBR (Constant Bit Rate)

考える．DiﬀServ ネットワークに入力するすべてのトに近いバースト性の低いトラヒックである．また，多ラヒックは，エッジルータにおいてレート無限大のト重フローは，ファイル転送等の比較的レートが低いト

ラヒックがトークンバケットによって整形される．まラヒックで TCP 等のウィンドウ制御によって発生すた内部ルータは LR サーバであるとする．そして，同る高いバースト性をもつ．リアルタイムメディアトラ

クラスの平均レートの和は，そのクラスに与えられた

ヒックはパケット遅延に対して厳しく，したがって遅割当レート以下になるようにし，ターゲットフローと

延上界について上記のモデルを解析することが実用上

多重フローの平均レートは，それぞれの入力リンク容重要である．

量以下とする．

2. ネットワークモデル

3. 従来の上界

2. 1 トークンバケット法

3. 1 Kim [2] による上界確定的な遅延上界を導出するためには，ネットワー

Kim [2] による上界は，ノードへ入力する複数のフクへ入力するフローを整形する必要がある．そのためローをターゲットフローと多重フローに分けて考えて本研究では，ネットワークへ入力する全フローにトーいる．一つのターゲットフローと M 個の多重フロー

クンバケット法を適用する．

からなるフローのクラス l を考える．これら M + 1 個

トークンバケット法は，激しいふくそう状態を避けのフローはすべてトークンバケットによって整形されるために送信側のトラヒックの転送速度をあらかじているとする．ターゲットフローのトークンバケット

め制限するアルゴリズムである．トークンはレート

パラメータを (σ0 , ρ0 ) とし，多重フローのトークンバ

ρ [bit/s] で生成されサイズ σ [Byte] のバケツに格納さケットパラメータを (σi , ρi ), i = 1, · · · , M, とする．

れる．到着フローは，トークンを受け取らなければ通LR サーバが直列に K 個つながったネットワークに過することができない．この結果として，整形後のフ

おいて，ターゲットフローの end-to-end の遅延 D0 に

ローは平均レートが ρ [bit/s] 以下，最大バースト長がσ [Byte] 以下になる（図 1 参照）．
2. 2 LR サーバ (Latency-Rate Server)
2. 2. 1 LR サーバの定義あるサーバ S において割当レート Ri とは，フロー iに保証された出力レートのこととする．フローの平均
到着レートが割当レート Ri 以上である区間をビジー
ピリオドという．τ をサーバ S におけるフロー i の j
番目のビジーピリオドの開始時刻，τ ∗ をビジーピリ
オド内に到着した最後のパケットがサーバ S を退去す
る時刻とする．区間 (τ, τ ∗ ] に属する任意の時刻を t と

図 1 トークンバケット法によるフローの整形
Fig. 1 Shaping ﬂow by token bucket algorithm.

し，区間 (τ, t) においてサーバ S によりフロー i に提S(τ, t) とする．あ供されるトータルサービス量を Wi,jる非負定数 CiS が存在して次の条件 (1) を満たすとき，
サーバ S を LR(Latency-Rate) サーバという [3]．





S
Wi,j
(τ, t) ≥ max 0, Ri (t − τ − CiS )(1)

この不等式を満たす非負定数 CiS の最小値をサーバのlatency と定義し，ΘSi と表す．式 (1) の右辺は，ビジーピリオド内でフロー i に要求されるサービスの下限を示す包括線を定義している（図 2 参照）．

図 2 LR サーバの振舞い
Fig. 2 Behavior of LR server.

893電子情報通信学会論文誌 2009/5 Vol. J92–B No. 5

対する Kim [2] による上界は，表 1 に示す記号のもとで，次式で与えられる．

⎛

提案する上界では，多重フローの入力リンク容量が⎞ σi · I{k=n }σ0  ⎝ k
i ⎠
+
Θl +
(2)
g0
Bi
K

D0 ≤

k=1

4. 提案する上界i∈F (k)ターゲットフローの入力リンク容量より小さいネット
ワークについて考え，更にターゲットフローのバース
ト長に注目する．
ターゲットフローの入力リンク容量を C ，多重フロー

ここで，g0 = min1≤k≤K Rlk −ρ であり，i∈F (k) i

i の入力リンク容量を Ci とし，C/Ci = r > 1, i =ターゲットフローの保証レートを表す．ターゲットフ

1, · · · , M を仮定する．また，ターゲットフローのトーク

ローに与えられる帯域が一番小さいノードのみでターゲ

ンバケットパラメータを (σ0 , ρ0 ) とし，多重フロー i のットフローのバーストによる遅延が発生していると考えトークンバケットパラメータを (σi , ρi ), i = 1, · · · , Mている．これは LR サーバの性質を利用したものである．

とする．ノード k でターゲットフローと多重化される

3. 2 中村 [1] による上界
Kim による上界 (2) は，入力トラヒックの上限が考する．すべてのパケットのサイズは一定値 p [Byte] と慮されていない．つまり，ターゲットフローのバース

し，バースト長 σ0 , σi , i = 1, · · · , M は p の整数倍

トがレート無限大で到着していることになっている．

とする．すなわち，

実際のネットワークでは，バーストは入力リンク容量で抑えられる．Kim による上界 (2) が実測値と大きな差があるのは，入力トラヒックの上限が考慮されていないのが原因だとして中村 [1] による上界が提案された．

多重フローの個数を m(k) = |F (k)|, k = 1, · · · , K と

σ0 = s0 p, s0 は整数(4)σi = si p, si は整数, i = 1, · · · , M

(5)

とする．
図 3 に提案する上界の考え方を示す．図 3 は（簡単タ ー ゲット フ ロ ー の 入 力 リ ン ク 容 量 を C と し ，
タ ー ゲット フ ロ ー (σ0 , ρ0 ) の 保 証 レ ー ト を g0 =min1≤k≤K Rlk −ρiのため p = 1 として）r = 4, m(k) = 1, σ0 = s0 =5, σ1 = s1 = 3 の例を示している．

としたとき，直列に多重フローの入力リンク容量がターゲットフローのK 個つながった LR サーバにおけるターゲットフロー

入力リンク容量より小さい場合，多重フローのバースの end-to-end の遅延 D0 に対する中村 [1] による上界

トにはすき間ができる．中村による上界 (3) では，多は次式で与えられる．

重フローのすべてのバーストを優先して処理していi∈F (k)C − g0C − ρ0

D0 ≤

+

K

k=1

⎛

⎝Θkl +

る．そのためターゲットフローは，多重フローのすべ

σ0
g0てのバースト長分の遅延を受けると考えている．一方，⎞
 σi · I{k=n }i ⎠i∈F (k)Bi

提案する上界では，多重フローのバーストのすき間に(3)

ターゲットフローのバーストが入り込むと考えている．
そのため，図 3 のように多重化したときにターゲッ
トフローのバースト長の方が短い場合，ターゲットフ

Table 1

表 1 記号とその定義
Symbols and their deﬁnitions.

記号

定義

K

ターゲットフローの end-to-end パス上のノード
数

F (k)

ノード k でターゲットフローと多重化されるフローの集合 (k = 1, 2, · · · , K)ni

フロー i のエントリノード

Rlk

ノード k でクラス l に与えられた分配帯域

Θkl

ノード k でクラス l が受けるスケジューラによる
待ち時間

Bi

フロー i の最大利用可能帯域

I{k=ni }894

ノード k がフロー i のエントリノードである
とき 1，それ以外で 0 となる関数

ローに遅延を与えない多重フローのパケットが存在す
る．図 3 では，多重フローのパケット 3 がターゲット

Fig. 3図 3 提案する上界の考え方
The idea of proposed delay bound.

レ

タ

ー

フローに遅延を与えない．中村による上界 (3) では，
ターゲットフローのバースト長を考慮せず，すべての多重フローのバーストが遅延を与えると考えているた
め，無駄な遅延まで考慮されている．具体的には，フロー i のバーストを構成する si 個のパケットの先頭のs0
r − m(k)

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

(6)個のパケットがターゲットフローのパケットを遅延させる．ここで，記号 x は実数 x の切上げ，すなわち，

x 以上の整数のうち最小のものを表す．
図 3 の場合，

s0
r − m(k)

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

 
=

5
3

=2

(7)

となり，ターゲットフローが 2 パケット分の遅延を受けることを表している．一方，(3) では σ1 = 3 パケッ
ト分の遅延を受けると考えているので，図 3 の考え方によると，より小さい遅延上界が得られる．
そこで，



+

K


(8)

⎝Θkl +

k=1

量は C0 ，多重フローの各ノードへのアクセスリンクの容量を C1 , · · · , CK ，ボトルネックリンクの容量はCb とする．また，すべてのシミュレーションにおい⎞ σ̃i I{k=n }i ⎠i∈F (k)Biて，Bi の値（表 1）は Bi = Ci , i = 1, · · · , K である．このとき，シミュレーション値と従来の上界 (2)，

(9)

σi >

(3) 及び提案する上界 (9) の比較を行う．ここでシミュ
レーション値とは，ターゲットフロー f0 の全パケッ
トの最大遅延のことである．全クラスの全フローは時(8) において

タ (σ0 , ρ0 ), (σ1 , ρ1 ), · · · , (σK , ρK ) で整形されている．
ターゲットフローの各ノードへのアクセスリンクの容

σ0
g0

⎛

はフロー f0 , f1 , · · · , fK からなる．f0 がターゲット
フローはすべてトークンバケット法により，パラメーとして，以下の新たな遅延上界を提案する．

C − g0C − ρ0クラス lother とする．ターゲットフロークラス ltarget
フローで，f1 , · · · , fK は多重フローである．これらのs0σ̃i ≡ min σi ,pr − m(k)D0 ≤合を考える．一つはターゲットフロークラス ltarget であり，もう一つのクラスはターゲットクラスではないs0pr − m(k)間的に同時にネットワークに流入する．また，シミュ(10)

レーションには ns-2 [5] を用いた．

5. 2 シミュレーション 1

が成り立つとき，(9) は従来の中村の上界 (3) よりもシミュレーション 1 では，図 4 のネットワークトポ

小さい上界となり，(10) が成り立たないとき (9) は中

ロジー 1 において，多重フローの最大バースト長 σ1 ，村の上界 (3) に一致する．すなわち，すべての場合に

σ2 を変化させたときのシミュレーション値と従来の上おいて提案する上界 (9) は中村の上界 (3) よりも精度

界 (2)，(3) 及び提案する上界 (9) の比較を行う．ここが良いかまたは等しい．

5. シミュレーション値及び従来の上界との比較
5. 1 ネットワークモデル
図 4，図 5 に 解 析 す る ネット ワ ー ク ト ポ ロ
ジ ー を 示 す．各 ノ ー ド N1 , · · · , NK は パ ラ メ ー タ

では，各ノードにおいてクラス単位の DRR (Diﬁcit

Round Robin) [5] を行い，ノード数 K = 2 とした．
シミュレーションパラメータは表 2 に示す．また，比較結果は図 6 に示す．
このシミュレーションでは，C0 = 10 [Mbit/s]，C1 ，K(Θ1l , Rl1 ), · · · , (ΘKl , Rl ) をもつ LR サーバである．

C2 = 5 [Mbit/s] であり，r = C0 /C1 = C0 /C2 =ここでは，ネットワークにおいてクラスが二つある場

2 [packet] となる．また，すべてのノードで多重数895電子情報通信学会論文誌 2009/5 Vol. J92–B No. 5
表 2 シミュレーション 1 のパラメータ
Table 2 Parameter of simulation 1.
C0
10 [Mbit/s]

C1 , C 2
5 [Mbit/s]

Cb
20 [Mbit/s]p
500 [Byte]

Θ1ltarget , Θ2ltarget

Rl1target , Rl2target

0.8 [ms]

10 [Mbit/s]

σ0
50 [kByte]

ρ0
3 [Mbit/s]

σ1 , σ 2
10〜100 [kByte]

表 3 シミュレーション 2 のパラメータ
Table 3 Parameter of simulation 2.
C0
10 [Mbit/s]

C1 , · · · , C K
2.5 [Mbit/s]

Θ1ltarget , · · · , ΘK
ltargetCb
20 [Mbit/s]

Rl1target , · · · , RlKtarget

0.6 [ms]
ρ1 , ρ2
2 [Mbit/s]

σ0
20 [kByte]ρ0
2 [Mbit/s]p
500 [Byte]

10 [Mbit/s]
σ1 , · · · , σ K
30 [kByte]ρ1 , · · · , ρK
1 [Mbit/s]

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

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

m(k) = 1，k = 1, 2 で あ る ．タ ー ゲット フ ロ ー

図 7 を見ると，提案する上界 (9) は中村による上の最大バースト長 σ0 を 50 [kByte] としたので，提界 (3) より精度良い上界が得られていることが分か

案 す る 上 界 (9) が 中 村 に よ る 上 界 (3) よ り 小 さ く

る．このシミュレーションでは，C0 = 10 [Mbit/s]，なるための条件は (10) より，多重数 m(k) = 1 でCi = 2.5 [Mbit/s] (i = 1, · · · , 8) より r = C0 /Ci =σi ≥ 50.5 [kByte] (i = 1, 2) の範囲であり，これ以外

4 [packet] となる．また，ノード N1 からノード N8 ま

では中村の上界 (3) に一致する．

ですべてのノードで多重数 m(k) = 1, k = 1, · · · , 8

図 6 を見ると，多重フローの最大バースト長 σ1 ，であるため，すべてのノードで提案する上界 (9) を適

σ2 が 50〜100 [kByte] のとき，提案する上界 (9) は中応できる条件 (10) を満たし，提案する上界 (9) はノー

村による上界 (3) より精度良い上界が得られているこド数が増えるにつれて中村による上界 (3) との差が大とが分かる．多重フローの最大バースト長 σ1 ，σ2 がきくなり，シミュレーション値に近づいている．

50 [kByte] 以上では提案する上界 (9) は一定値となっ

5. 4 シミュレーション 3ており，実際にシミュレーション値も多重フローの最シミュレーション 3 では，図 5 のネットワークトポ

大バースト長 σ1 ，σ2 が 40 [kByte] 以上では一定値とロジー 2 において，ノード数 K を変化させたときのシなっていることが分かる．

ミュレーション値と従来の上界 (2)，(3)，及び提案す5. 3 シミュレーション 2

る上界 (9) の比較を行う．ここでは，各ノードにおいシミュレーション 2 では，図 4 のネットワークトポてクラス単位の WFQ(Weighted Fair Queueing) [4]

ロジー 1 において，ノード数 K を変化させたときのを行い，ノード数 K = 8 とした．シミュレーション

シミュレーション値と従来の上界 (2)，(3)，及び提案

パラメータは表 4 に示す．また，比較結果は図 8 にする上界 (9) の比較を行う．シミュレーション 1 と同示す．

じトポロジーで，異なるキューイング方式によって特

このシミュレーションでは，C0 = 10 [Mbit/s]，Ci =性評価を行うためここでは，各ノードにおいてクラス

2.5 [Mbit/s] (i = 1, · · · , 8) であり，r = C0 /Ci =単位の WFQ (Weighted Fair Queueing) [4] を行う．

4 [packet] となる．ターゲットフローの最大バースト

ノード数 K = 8 とした．シミュレーションパラメー

長 σ0 = 20 [kByte]，p = 500 [Byte] より s0 = 40 で

タは表 3 に示す．また，比較結果は図 7 に示す．

あり，多重フローの最大バースト長 σi = 30 [kByte]

896

レ

タ

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

C0
10 [Mbit/s]

C1 , · · · , C K
2.5 [Mbit/s]

Cb
20 [Mbit/s]p
500[Byte]

提案する上界は従来の上界を改良しているが，場合によってはシミュレーション値と比較して大きな差がある．この理由として次のことが考えられる．上界のΘ1ltarget , · · · , ΘK
ltargetRl1target , · · · , RlKtarget

考え方は，ターゲットフローのパケットは多重フロー

0.6 [ms]

10 [Mbit/s]のパケットがすべて処理された後に処理されるとして

σ0
20 [kByte]ρ0
2 [Mbit/s]

σ1 , · · · , σ K
30 [kByte]ρ1 , · · · , ρK
1[Mbit/s]

いる．それに対してシミュレーションでは，どのフローも差別なく処理している．その違いが，場合によっては大きな差になると考えられる．
ネットワークを渡るトラヒックは，ノード数が大きくなるとバーストが弱まる．また，多重フローの出入りが激しいネットワークの場合，弱まったターゲット
フローのバーストのすき間に多重フローのバーストが入り込み，遅延が増えないという結果になる．本論文のシミュレーション 2 の結果から分かるように，ノード数に対する遅延上界の増加幅は徐々に小さくなっていく．従来の上界 (2)，(3) や提案する上界 (9) ではこのバーストの弱まりについては考慮していないため，

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

今後の課題としてこの点を改善する必要がある．
文である．ノード N1 ，N2 ，N3 において，多重数はそれ[1]

中村博貴，中川健治，“DiﬀServ 領域における end-to-endの確定的遅延上界に関する研究，” 信学論（B），vol.J91-B,[2]

G. Kim and C. Kim, “Deterministic edge-to-edge de-

ぞれ，m(1) = 1，m(2) = 2，m(3) = 3 なので，ノード N1 ，N2 ，N3 において (10) が成り立つことが簡単

献no.4, pp.440–449, April 2008.

な計算から分かる．したがって，得られる上界は中村

lay bounds for a ﬂow under latency rate schedul-の上界 (3) より精度が改善されている．ノード N4 以

ing in a DiﬀServ network,” IEICE Trans. Commun.,降では (10) は成り立たず，得られる上界は (3) と同

vol.E88-B, no.7, pp.2887–2895, July 2005.
[3]

D. Stiliadis and A. Varma, “Latency-rate servers:

様，すべての多重フローのバーストを処理する時間を

A general model for analysis of traﬃc scheduling

計算している．そのためノード N4 以降では，提案すalgorithms,” IEEE/ACM Trans. Netw., vol.6, no.5,

る上界 (9) は中村による上界 (3) からノード N1 ，N2 ，

N3 で改善できた分だけ減じた形になっている．

pp.611–624, Oct. 1998.
[4]

sharing approach to ﬂow control in integrated services networks: The single-node case,” IEEE/ACM

6. む す び
本研究では，DiﬀServ 領域において中村による上界(3) より精度の良い端末間の遅延上界を導出することを目的とした．結果として，バースト長を考慮するこTrans. Netw., vol.1, no.3, pp.344–357, 1993.
[5][6]

銭 飛，NS2 によるネットワークシミュレーション，森北
出版，2006.
R.L. Cruz, “A calculus for network delay, part I: Network elements in isolation,” IEEE Trans. Inf. Theory,とで，多重フローのリンク容量がターゲットフローのリンク容量より小さいネットワークに対しては，中村A. Parekh and G. Gallager, “A generalized processor

vol.37, no.1, pp.114–131, 1991.
[7]

Y. Jiang and Q. Yao, “Impact of FIFO aggregation

による上界 (3) より精度の良い遅延上界を導出するこ

on delay performance of a diﬀerentiated services net-とができた．

work,” ICOIN’03, pp.216–225, Feb. 2003.

（平成 20 年 9 月 11 日受付，21 年 1 月 5 日再受付）

897