不完全なトラヒック情報に基づくメッシュ網の帯域設計法
2007MI177

野原 謙太 2007MI187

大野 祐史

2007MI189

大崎 敬三

指導教員 奥村康行
ついて述べる.

1. はじめに1.1. 研究の背景
近年, 予測困難なトラヒックの需要変動に対する柔軟性の向上や, 故障, 災害時において高信頼なネットワークサービスを提供しつつ, ネットワーク資源を効率的に利用することができるような, 柔軟性と信頼性を両立させるネットワークが求められている.
通 信 網 に お け る 発 着 ノ ー ド ( 以 下 SourceDestination[SD])間を流れる交流トラヒックは, 網設計において有益な情報である. しかし, 交流トラヒックの取得は, 装置に対する負荷を要するものであるため, どのような形の通信網においても実施されるものではない.
先行研究[1]では, 交流トラヒックが取得できない状況下で, リンクにおいて取得するトラヒック情報から現用,及び, 迂回パスに必要な帯域を導出する方法を提案している. 提案法では, 必要帯域の上限値を線形計画法により規定するアプローチを採っている. 本研究では,メッシュ網に対しての提案法を適用することで実施した適用性評価の結果を出す.
1.2. 研究の目的
先行研究[1]では, 問題を定式化し, 説明すると共に,構成するノード数の異なる様々なサイズのリング網に対して提案法を適用し, 実施した適用性能評価の結果,考察を示している. 本研究では, 自己修復性があり,非常に信頼性の高いメッシュ網に置き換え, 提案法を適用, 実施した適用性評価の結果, 考察を示す.

2. 光パス網の設計と課題
2. 1. 光パスについて[2]ネットワークは, 一つ一つのノード間をつなぐリンクにによって構成されている．このリンク内には, 始点, 終点 と な るル ー タ 間 を つ な ぐ 「 光 パ ス （ OLSP: OpticalLabel Switched Path）」と呼ばれる「仮想的なパケットの通り道」が設定され, 各パケットはそれに沿って転送されることになる. 数多くの光パスの中で, さまざまな制約条件を考慮しつつ, 特定のリンクの障害を考慮した上で, ネットワークリソースを設計することを「光パス設計」と呼ぶ．
本研究では, 光パス網の設計とその課題, 解決策に

2. 2. 光パス網の設計と課題
光パス網を設計するにあたり, 発着ノード間を流れる交流トラヒックは有益な情報である. しかし, ノードに負荷がかかるため, 完全にすべての交流トラヒックの情報を取得することが困難な場合がある. そのため, 交流トラヒックの情報が欠けたり, また, 交流トラヒックの情報がまったく取得できない状況の中で, リンクにおいて必要な帯域を求める必要がある.
障害が発生せず現用パスが選択されている際に取得したリンクでのトラヒックにより, 現用パスに対し, 必要な帯域を設計することは可能である. しかし, ノードに負荷を与え, 完全な交流トラヒック情報を持たない場合,迂回パスに対し, 必要なリンクでの帯域を求めることができない.
2. 3. 解決策
この課題の解決策として, 本研究では, 線形計画法による定式化を用いる[1]. 先行研究では, 求められたリンクで取得するトラヒックから, 現用パス, 及び, 迂回パスの容量を合わせた必要帯域の上限値を求める問
題を線形計画法として定式化し, この問題を解くことで必要帯域を求める方法が提案された. 本研究では,メッシュ網に対し提案法を適用, 実施した適用性能評
価の結果, 考察を示す.
また, 他の解決策として, Network Tomography[3]を用いて, 外部からパケットを送り, 内部のトポロジーを推定する. その結果から得た交流トラヒックの推定結果を用いて必要帯域を導出するという方法が考えられる. しかし, 設計においては, 帯域不足を発生する危険を除外することが指摘されることから, 確実な必要帯域を求める方法としては, 前者の方法が望ましいと考える.

3. 帯域設計法の前提条件
前提条件として, 以下の項目を規定する.
・ 全 SD 間の現用パスとその迂回パスの経路は予め決定されている.
・ トラヒック取得時においては, 現用パスが利用されている.
・ 障害発生時には, 障害リンクを有する現用パスは迂回パスに切り替えられる.
・ 単一リンクの障害（複数リンク同時障害は想定しない）に対して, 迂回パスによる復旧が可能なようにする.
・ 各リンクの各方向に対して,流れるトラヒックの和, 各ノード上の流入トラヒックの和と流出トラヒックの和が, トラヒック情報として取得されている.

4. 線形計画法による定式化[1]前章で述べた前提条件のもとに, 現用パスと迂回パスを疎通するのに必要な帯域を算出する帯域設計法について説明する.
なお, この帯域設計法は, 迂回パスで利用する帯域を該迂回パスに専有させることを前提とする
Dedicated Protection 方式, 及び, 迂回パスで利用する帯域が切り替え要因となる障害リンクを異にする迂回パス間で共有することを前提とする Shared Protection方式の両方式に対応可能なものである. ここでは,記述の重複を避けるため, Shared Protection 方式を例に定式化について記述する.
基本的な考え方は, 次のようなものである. まず,未知の SD 間の交流トラヒック量を変数とし, リンク上を流れるトラヒックとノード上を出入りするトラヒックに着目する. 変数である未知の SD 間の交流トラヒックの各リンクにおける和, ないし各ノードにおける和が, 観測されるリンク上のトラヒックやノード上のトラヒックに等しくなるという制約条件を置く. この線形制約条件を満たすように, 変数である未知の SD 間の交流トラヒックを定めると, 迂回パスを疎通するトラヒックは, 障害リンクを指定したとき一意に定まり, 両トラヒックを疎通できる, 各リンク上の帯域容量も一意に定まる.変数を, この線形制約条件の下で自由に動かした時, 各リンク上の帯域容量のとりうる最大値が求める解となる.
想定する障害リンク k に対して, 帯域容量を算出するリンク h を疎通しうる最大トラヒックを求める最大化問
題として定式化する. k を障害が起こり得るすべてのリンクについて変化させたとき, P[h,k]をリンク k に障害が起きることを想定したときのリンク h の必要帯域とすると,P[h,k]が取り得る最大値は, リンク h における帯域容量となる.
メッシュ網の場合は, さらにこのリンク h を変化させて取り得る最大の帯域容量を各リンク共通の帯域とすればよい.
最大化問題 P[h,k]の線形計画法としての定式化を以下に示す.
[表記]
V,E: それぞれ, ノード, （有向）リンクの集合.
i,j: ノードに対する index.

h,k,l: リンクに対する index.
[パラメータ]W ij : i , j  V , W ij  (1)

ノード i からノード j に至る現用パスを構成するリンクの集合.
Bij : i , j  V , Bij  (2)

ノード i からノード j に至る迂回パスを構成するリンクの集合.

Gk : k  , Gk  V  V(3)SD ペア(i,j)の現用パスが障害リンク k を含むような(i,j)の集合. この SD ペア(i,j)間は, 現用パスを疎通させることができないので迂回パスを疎通させることになる.

inin(4)
Di : i  V , Di  0
ノード i から通信網に流入する観測トラヒック量.
outout(5)
Di : i  V , Di  0
ノード i で通信網から流出する観測トラヒック量.
T l : l  , T l  0(6)

通信網上のリンク l における観測トラヒック量.
[変数]  

 i, j : i, j  V ,  i, j  0(7)

SD ペア(i,j)を流れるトラヒック量. 通常は現用パスを流れる. 現用パスが障害リンク k により疎通できなくなったときは迂回パスを流れる.
[目的関数]
maximize i, j  hWij& (i , j )Gk i, j (8)hBij & (i , j )Gk

現用パスと迂回パスを実際に流れるトラヒック量.
障害リンク k 一か所のみで障害が起きているとし,そのときに実際に流れるトラヒックを最大化する. トラヒッ
クの観測は障害リンク k とは異なる通信網上の 1 リンク
h にて行う.
[制約条件]

 i, j   Dini , i  VjV {i}(9) i, j   Doutj , j V

(10)iV { j}通信網の各ノードに着目し, そのノードから流入するトラヒックの総和と流出するトラヒックの総和が, それぞれ観測された流入トラヒック量と流出トラヒック量に等しいとする.

   i, j   T l , l  (11)iV jV {i} lWij

通信網の各リンクに着目し, その(有効)リンクをその向きに流れる現用パスの実トラヒック量の総和が, 観測された実トラヒック量に等しいとする.

ノード数 4 ではノード間を繋ぐリンク構造を図 1 に示すように定義する. 現用パス, 迂回パスを流れるトラヒック量は 0[Mbps]を除く 10[Mbps] までの中でランダムな値を取るように定義し, 現用パス, 迂回パスのルートは
図 2 で示すように定義する．同様にノード数 5, 6, 7 のメッシュ網のリンク構造, 現用パス, 迂回パスのルート, トラヒック量を定義し, また着目リンク h と障害リンク k をリンク構造から 1 本ずつ選ぶよう設定し, 制約条件が適用されるように, プログラムを作成する.
ノード数毎の制約条件と目的関数は, C 言語のプログラムで導出し, その値を ILOG CPLEX で読み込み,リンク毎の帯域を導出した．

5. メッシュ網への適用
5.1. メッシュ網への適用の経緯と方法
先行研究では, この問題を解決するため, リンクで取得するトラヒックから, 迂回パスの容量を会わせた必要帯域の上限値を求める問題を線形計画法として定式化していた. そして, 構成するノード数の異なる様々なサイズのリング網に対して帯域設計法を適用し, 必要帯域の平均値, 及び, その 95%の信頼区間を求めていた. それらを評価する事で, 尐数のノードから構成されるリング網における帯域設計においては効果が期待できることを示しているのみであり, その他のネットワー
クで、提案法が有効であるかを示せていない.
そこで, 本研究では, 4.で示した帯域設計法を一般的なメッシュ網に適用させて実施した評価例を示す. メッシュ網では, 構成する全ノード間を SD とするトラヒックが流れるものとした. ここで, 交流トラヒックを除く全ての情報は帯域設計の際に既知として扱うこととする. なお, メッシュ網においては任意に決めた現用パスに対し, 迂回パスは現用パスとは異なるパスを通るように決める.
5.2. ILOG CPLEX[4]によるプログラム
本研究においては, メッシュネットワークモデルにおける制約条件を明確にし, ILOG CPLEX の環境を用いて実際にリンクに必要な帯域を求めることを実施した.
プログラム内部においては, X（i,j）を現用パス, 迂回パスのトラヒック量とした. また, あらかじめ, メッシュ網のノード間を流れるトラヒック量と現用パス, 迂回パスのルートを設定することにより, リンクに必要な帯域を自明解とし, 線形計画法で求めた解と比較し正規化を行う.
5.3. プログラムの前提条件
実際には, ノード数は 4 から７までとし, 全ノード間でリンクを繋ぐフルメッシュネットワークを用いる. 例えば

図 1 ノード数 4 のメッシュネットワークのリンク構造

図 2 ノード数 4 のメッシュ網の現用パスと迂回パス実験の条件
1. パスの設定として現用パスを設定した上でその現用パスと完全に一致しないように迂回パスを決定する.
2. パスの再配置はしない.
3. トラヒック量は発着ノード間で流れ, 自然数の量が流れる.
4. 着目リンクと障害リンクは, 必ず同じリンクではないものにする.

5. 着目リンクと障害リンクは１つずつとする.

頼区間の減尐と幅の減尐が起こると考える.

6. フルメッシュではあるがパスはランダムで決めるため,すべてのリンクを使わなくてもよい.

6. 今後の課題

5.4. プログラムの動作結果それぞれのノード数に対して, 着目リンク h と障害リン
ク k の組み合わせの全ケースによる帯域計算を実施した.
さらに, トラヒック量, パスの設定をかえて帯域容量を求め, それを正規化する. 求めた値から必要帯域の平均値, 及び, その 95% の信頼区間を求めた値を図 3に示す.

今後の課題として以下のことが挙げられる.
(1) フルメッシュネットワーク以外への適用
今回の研究では, フルメッシュネットワークを想定して適用し, 実装を行った. しかし, 今後の課題としてノード間が一部繋がっていないメッシュネットワークの場合の適用が求められる. メッシュネットワークの適用は,非常に理想的であると考えられるが, 現段階では, 設備面での投資が大きくなってしまう為, メッシュネットワークのみでの巨大なネットワークの構築は不可能である. もし, ノード間が一部繋がっていないメッシュネッ
トワークの帯域設計が適用できるのならば, この問題のコスト面での解決に一歩近づくことが期待される.
(2) 部分的に交流トラヒックが得られる場合の適用
今回は, 交流トラヒックまったく得られない状況を想定しているが, 部分的に交流トラヒックが得られる場合など, その情報を用いて提案法で得られる結果をもっと改善することが期待できる.

7. まとめ
図 3 メッシュ網への適用性評価
5.5. 考察
全試行において, 図 3 より様々なノード数のフルメッシュネットワークにおいて 1.5 倍以下の帯域容量を確保すればよいと考えられる. そしてノード数増加につれ、帯域容量の正規化した値が減尐している為, ノード数増加にも対応しており, 網のコストを削減する事が可能であることが分かった. 先行研究においては, 多数のノードから構成されるリング網で, 提案法を適用することにより得られる効果は小さくなっていたが, 本研究のフルメッシュネットワークにおいての適用では得られる効果が大きくなっていた.
ノード数を増加するとともに, 帯域容量も徐々に減尐することがわかる. このことより大規模なフルメッシュネッ
トワークになればなるほど, 帯域容量において削減できることがわかる. 95％ の信頼区間では 4 ノードでは大きな幅になっているがノード数が増加するとともに幅が狭くなっている.
ノード数が増加とともにリンクも増加する事から, 現用パスが障害リンクを通り, 迂回パスが着目リンクを通らない場合が多く起こる. この場合は正規化した値は1 となると考える. その 1 となる数がノード数増加とともに増加していく. よって平均値の減尐, 95% の信交流トラヒックが取得できない状況において, 取得可能なトラヒック情報から迂回経路用帯域を含めた必要帯域を線形計画法により求める方法をメッシュ網に適用した結果, 様々なノード数から構成されるメッシュ網において効果が期待できることを示した．
今回の研究では, フルメッシュネットワークを想定し,実装を行いこのような結果が示されたが, 今後は, ノード間が一部繋がっていないメッシュネットワークの場合などでも適用が可能であると期待できる．

参考文献
[1]

[2]

[3]

[4]

松村龍太郎, 辻野雅之, 岩下基, “不完全なトラヒ
ック情報下での帯域設計法－線形計画法による定式化と定量評価－,” 電子情報通信学会，信学技報，ICM2008-78, pp. 117-120, March 2009.
徳久正樹, 能上慎也, 阿部威郎, “フォトニックMPLS 網における光パス設計ソフトウェア,”
NTT 技術ジャーナル, Vol.15, No.7, pp.53-55,
July 2003.
田中良明, ザニケエフ・マラット, ”品質確保のためのネットワーク運用管理技術,” 電気通信普及
財団研究調査報告書, No.23, pp.422-426.
ILOG CPLEX User’s Manual, Oct. 2003.