背景

トラヒックエンジニアリング (TE)`

現在のトラヒックに合致するようにネットワークの構成やルーティングを変更する
Multi layer Traffic Engineering (TE)` 想定している環境：`

物理ネットワーク上に光パスを構築
光パスで構成されるネットワークがIPネットワークに論理トポロジを提供
光構成論を提供` 動作：

論理トポロジの再構成
現在のトラヒックにあわせて、光パスの設定を変更

トラヒックマトリクスの取りうる範囲を考慮した
マルチレイヤトラヒックエンジニアリング
大阪大学 大下 裕一

1

2

背景

背景

トラヒックエンジニアリングの入力

トラヒックマトリクスの推定` 各対地間のトラヒック需要（トラヒックマトリクス）`

直接観測することは難しい` 一般的なトラヒックマトリクス推定手法：` 各リンクのトラヒック量を元に以下の連立方程式をたて、その条件にあうトラヒックマトリクスを求める
X = AT` フルメッシュにPacket LSPを構築する必要があり、大規模ネットワークでは適用困難

X:各リンクのトラヒック量
A：ルーティングを表す行列` T:トラヒックマトリクス``

直接観測可能なリンク使用率から推定`` 大規模ネットワークであっても適用可能` トラヒックマトリクス推定に用いている連立方程式の数が少ない
連立方程式の数が少ないために誤差が生じる

各リンクのトラヒック量はそこを経由するトラヒックの和となることを利用した連立方程式` 推定誤差がTEの性能に著しい影響を与える
34

背景

推定誤差の影響を低減する方法

研究の目的と方法` TEと連携して推定精度を向上させる` 目的：

トラヒックの取りうる範囲を考慮しつつ、目標達成可能なTE手法

TEでの経路変更をトラヒックマトリクス推定にフィードバック` 精度が向上するまでは、推定誤差の影響を受ける`` トラヒックマトリクスの取りうる範囲を考慮して経路設計を`

トラヒックマトリクスの推定誤差の影響は受けない`

トラヒックマトリクスの取りうる範囲が広い場合でも、適切な観トラヒクマトリクスの取りうる範囲が広い場合でも 適切な観測を行うことにより、範囲を適切に削減` トラヒックの取りうる範囲を考慮を取り入れたマルチレイヤTE行う`5

取りうる範囲が広すぎると、考慮する範囲が大きく、適切なTEを行うことができない` マルチレイヤTEを考慮した観測

61

範囲を考慮に入れたマルチレイヤTE手法

マルチレイヤTEの基本的アイデア

手法の概要` トラヒックマトリクスの取りうる範囲
リンク使用率の観測`

マルチレイヤTE

X = AT ` A：ルーティングを表す行列` マルチレイヤTE観測されたリンク使用率から定まるトラヒックマトリクスの取りうる範囲すべてを考慮して、論理トポロジ・経路を設計取りうるトラヒ ク トリクスの要素は０以上取りうるトラヒックマトリクスの要素は０以上` TEの方針` 取りうるトラヒックマトリクスの` 観測結果の追加`

各リンクのトラヒック量はそこを経由するトラヒックの和となることを利用した連立方程式

範囲内において、リンク使用率の最悪値の最小化

マルチレイヤTEを考慮した上で、TETEに影響を与えに影響を与え、かつ、条件が不足条件が不足している対地間トラヒックの観測結果を追加

7` T:トラヒックマトリクス

T ≥0

観測結果の追加`

以下の方程式が成り立つ範囲` X:各リンクのトラヒック量TEの目標が達成されない場合` MILPとして定式化

8

範囲を考慮に入れたマルチレイヤTE手法

マルチレイヤTEのためのトラヒックの観測

マルチレイヤTEの定式化

観測結果の追加` リンク使用率が閾値TH以上であれば` TE後のリンク使用率を閾値以下にできない場合には、`

目的関数：リンク使用率の最悪値の最小化``

TEに影響を与えるトラヒックの観測結果を追加する

minimize M

制約条件
構築される光パスがすべて収容可能追加される光パスはN本以下` 取りうるすべてのトラヒックマトリクスのついてリンク使用率の最大がM以下``` 観測結果の追加の方法``` リンク使用率が閾値TH未満であれば``目的関数：使用波長数の最小化
制約条件
構築される光パスがすべて収容可能` 取りうるすべてのトラヒックマトリクスのついてリンク使用率の最大がTH以下

一部の対地間トラヒックをサンプリングにより計測
経路変更をしてみて、経路変更前後のリンク使用率の変化を調べる` TEに影響がある対地間トラヒックを選択し、選択したトラヒックの観測が行えるように経路変更する`` TEへ与える影響が大きいトラヒックを観測対象として選択することが重要
910

マルチレイヤTEのためのトラヒックの観測

マルチレイヤTEのためのトラヒックの観測

観測対象の選択方法

手法１` 観測対象選択の基本的指針` 基本的アイデア

情報不十分な箇所を観測` TEへの影響が大きい箇所``

現在の観測結果を元に計算した、取りうる範囲が広い対地間トラヒックほど情報が不足している` 選択手法

` 手順

手法１

`

`
`

`

手法３
` TE後の経路変更まで考慮して、影響の大きい箇所を観測

11

12

最大－最少が最も大きい対地間トラヒックを観測対象とする
トラヒックの取りうる範囲`

制約条件： X=AT、T>0

手法２` TE後にリンク使用率の最悪値が最大となる箇所を観測

各対地間トラヒックについて` 線形計画問題を解き、取りうる値の最大・最小を求める
線 計 問題を解きりうる値 最大 最 を求める

` 情報が不十分な箇所を観測

最も範囲が広いものを選択

対地間トラヒックのID

2

マルチレイヤTEのためのトラヒックの観測

マルチレイヤTEのためのトラヒックの観測

手法２

手法３

`

基本的アイデア````

TE後のリンク使用率が最大となる箇所を経由するトラヒックがTEの性能に影響を与える
リンク使用率の最悪値なら、論理トポロジ・経路を変更した時点で、計算可能

`

`

手順

基本的アイデア
TE後のリンク使用率が最大となるリンクが複数ある場合は、同時に複数のリンクの使用率に影響を与える対地間トラヒックが観測の効果が大きい

手順`

TE後の論理トポロジ・経路を計算`

現在の観測結果から、論理トポロジ・経路を設計``

設計後のリンク使用率の最悪値が最大となるリンクを経由している対地間トラヒックを抜き出す

各対地間トラヒックについて、トラヒック量が正確に把握できた場合に、影響を与えるリンクの集合を求める``

抜き出された対地間トラヒックに対して、手法１を適用し、最も取りうる範囲が大きい箇所を選択する

BA
リンク使用率が最大のリンクを経由しないトラヒックは選択しない

C

13E
リンク使用率が最大のリンク

D影響を与えるリンクの本数が最も大きい対地間トラヒックの集合に対して、手法１を適用し、観測する対地間トラヒックを確定する
２本のリンク使用率が最大のリンクに影響を与える
B
１本のリンク使用率が最大のリンクに影響を与える
AE

より多くのリンクに影響を与えるトラヒックを選択

C

リンク使用率が最大のリンク

14

D

評価

評価

評価環境

評価方法

` 物理トポロジ：` 観測対象の対地間トラヒック選択の有効性を評価`

Abileneトポロジ(11ノード、14リンク)`

どの対地間トラヒックを選択手法がもっとも有効なのか`

以下の観測結果を入力としてリンク使用率の最悪値を最小化` 初期トラヒック：`

対数正規分布にしたがって生成` 初期論理トポロジ：`` すべての論理リンクのリンク使用率` 手法１～３で選択された対地間トラヒックの観測結果
手法１ ３で選択された対地間トラヒ クの観測結果

初期トラヒ クに合わせて 光パス数を最小化したものを用いる
初期トラヒックに合わせて、光パス数を最小化したものを用いる選択された対地間トラヒックは正確に観測可能であると仮定` TEの際のトラヒック

Case 1：対数正規分布に従ってランダムに組み替える` Case 2：ランダムに選択した3本の対地間トラヒックを増加` Case 3：ランダムに選択したノード宛の対地間トラヒックのうち3本を増加
`

15

`

TE後のリンク使用率の最悪値を比較

16

評価

評価結果
`

`

`

まとめ

観測箇所を追加するにつれ、リンク使用率の最悪値は著しく削減可能
観測箇所を追加することは、範囲を考慮したマルチレイヤTEにとって有効選択手法3が最もリンク使用率を削減可能``

選択手法１ではTEに影響を与えない対地間トラヒックを選択してしまう
選択手法3では、多くのリンクに影響を与える対地間トラヒックを選択するため、選択手法2よりも少ない箇所の観測でリンク使用率を削減可能` マルチレイヤTEで必要なトラヒックマトリクスを直接観測することは難しい` 現在観測されたリンク使用率等から求まるトラヒックマトリクスの取りうる範囲を考慮してTEを行う` トラヒックマトリクスの取りうる範囲を十分に削減するた

めに観測結果を追加する

Case1のトラヒックの結果`TEを考慮して追加する観測対象を選択することにより、より効果的な観測が可能

他のトラヒックの場合も同様の結果
17183

今後の課題` 大規模ネットワークへの対応``

MILPを用いたTEでは、計算時間が大きくなってしまう発見的手法を構築する必要がある` TEとトラヒックの観測がより連携した手法`

TEに影響を与える対地間トラヒックのトラヒック量が把握されるような経路変更を行いつつ、適切にTEを行う手法
な経路変 を
適を` サンプリングによるトラヒック観測への応用`

トラヒックエンジニアリングを考慮したサンプリングレートの設
定手法

194