光パスにおける再配置アルゴリズムの研究
2007MI204 佐田 裕輔 2007MI216 下村 亮二 2007MI271 吉田 亮史
指導教員 奥村康行

1.はじめに
1.1.研究の背景
近年, ネットワークトラヒックの増大やマルチサービス化が進んでいる. そして, 今後も FTTH サービスの利用者や動画コンテンツの増加が予想され, MPLS や GMPLSのようなラベルを利用したエンド・ツー・エンドの通信サービスが注目されている. その中で, 通信サービスに影響を与えずに効率的に光パス配置の変更, 追加ができる光パスの再配置方式に対する要求が高まりつつある.
1.2.研究の目的
先行研究[1]では, 新たな最適再配置方式が提案されているが, 定量的な比較がされていない． そこで本研
究ではこれまでに提案された再配置方式を述べると共に， それぞれの再配置法を定量的に比較する . その結果どの再配置方式が最適であるかを考察する.

2.GMPLS 技術
2.1.GMPLS の概要[2][3]「 パ ス 」 と い う 考 え 方 は , MPLS(multi-protocol labelswitching)という技術で使われている. これは, IP パケッ
トの先頭にパケットの「ラベル」を付加し, このラベルを識別することによってルーティングを行う技術である. さらに MPLS の概念を取り入れ, 下位のレイヤーまで拡張し一般化した GMPLS(generalized-MPLS)と言う技術がある. GMPLS は, IP パケットに識別のためのラベルを付加するのではなく, タイムスロットや波長といった物理的な対象をラベルとして扱う. これらの技術において, ラベルによって定められた仮想的なパケットの通り道を「パス」と呼ぶ. 特に光ネットワークにおいて, GMPLS のラベル付加によって定められた仮想的な光パケットの通り道を「光パス」呼ぶ. 光ネットワークが普及した昨今では, GMPLS の方が主流となっている.

3.光パスの再配置方式
本節では先行研究ににおいて提案されていた 3 つの再配置方式について図を用いて記述する. 光パスの再配置における操作はアルゴリズムによって多少異なるが基本的に最適経路探索, 光パス切断・解放, 光パス配置の 3 ステップからなる.

3.1.動的再配置方式[1][4]：現在の光パス(a) 初期状態

(c) 第2ステップ[光パス切断・解放]：代替経路(b) 第1ステップ[代替経路探索](d) 第3ステップ[光パス再配置]

図１ 動的再配置方式(1)動的再配置方式の概要
動的再配置方式の手順を図 1 に示す. 同図(b)の第 1ステップでは, 現行パスの再配置先である代替パスの検索を行う. A を始点, G を終点とする経路を探索した
場合 A→E→F→G という経路が最適であるという結果がでたので, これを代替経路と設定する. 同図(c)の第 2ステップでは現行パスの切断・解放を行う . このとき, このパスを利用していた通信は一時的に切断状態となる.
同図(d)の第 3 ステップでは, 第 1 ステップにて探索した代替経路に光パスを配置して再配置完了となる.
(2)動的再配置方式の課題
動的再配置方式の課題として, 第 2 ステップの光パスの切断解放から, 第 3 ステップの再配置完了までの期間は, 光パスが切断状態となり, その影響として通信サービスの中断, パケットロスのリスクがある. 通信サービ
ス中断時間は, 短時間であるほうが望ましいので, この部分は課題である.
3.2.計画的再配置方式[1][4](1)計画的再配置方式の概要
上記の動的再配置方式の課題を解決する方法として提案されたのが, 計画的再配置方式である. 計画的再配置方式の手順を図 2 に示す. 第 1 ステップでは, 動的再配置方式と同様に代替経路の探索を行う. 同図(a)の第 2 ステップでは, 第 1 ステップで探索した経路に光パスを配置し, 現行光パス(実線)から代替経路を使用した光パス(点線)への切替を行う. 同図(b)の第 3 ステップで不要となった元の経路の光パスを切断・解放し , リソースとして使用できるようにして再配置完了となる . このように先に代替パスへの切替を行ってから , 元の経路を切断・解放することにより , 動的再配置方式のステップ 2 と 3 の間に発生していた通信切断期間をなくし,通信の安定性を確保している.
：現在の光パス(c) 第2ステップ[光パス切断・解放]：代替経路(d) 第3ステップ[光パス再配置]

図 2 計画的再配置方式(2)計画的再配置方式の課題
動的再配置方式では, 現行光パスの切断・解放を行った後で代替光パスの配置を行うので , 現行光パスが配置されているリンクも使用可能なリソースとして探索の候補に入れることができた. しかし, 計画的再配置方式
では, 現行光パスの切断・解放が行われるのは代替光パスの配置・切替を行った後になるので, 現行パスが配置されているリンクを使用可能なリソースとして探索の候補に入れることができない . 従って, リソース効率の悪さが課題である.
3.3.グリーディ再配置方式[1][4](1)グリーディ再配置方式の概要
グリーディ再配置方式は , 計画的再配置方式の通信サービス継続性の効果を維持しながら, リソースの制約の欠点を補う方式である. グリーディ再配置方式のフローチャートを図 3 に示す. (a)再配置の対象となる光パスの最適な再配置先(退避先)の探索を行う. (b)再配置の対象となる光パスがない場合は, 再配置終了となる.
(c)再配置の対象となる光パスが存在した場合, 検出された退避先によって分岐を行う. (d)既に退避先のリソースに現行ネットワーク構成で使用されている光パスが存在し, その光パス(妨害光パス)のせいで再配置を行えない場合は, 現在行っている再配置を一旦停止し ,アルゴリズムの再帰呼び出しにより妨害光パスの再配置を先に行う. (e)最適再配置先に対象となる光パスの切替を行う. (f)再配置された元の光パスを解放する. これにより, 妨害光パスが使用していた退避先のリソースに空きを作ることができ, 再配置を行うことができる.

図 3 グリーディ再配置方式(フローチャート)
本方式における光パスの切替の実行例を図 4 に示す.
①再配置対象パスの退避先(B-E)に妨害光パス 1 が存在するため再帰呼び出しにより妨害光パス 1の再配置を先に行う.
②再配置の命令を受けた妨害光パス 1 の退避先(CF)に妨害光パス 2 の存在のため, 再び再帰呼び出しを行い, 妨害光パス 2 の再配置を先に行う.
③再配置の命令を受けた妨害光パス 2 の退避先(DG)には, リソースの空きがあるため再配置を行う. この再配置により妨害光パス 1 の退避先(CF)にも空きができるので, 妨害光パス 1 の再配置も可能となり, 同様に配置対象光パスの再配置も可能となり再配置完了となる.
：再配置対象光パス：妨害光パス1①②：妨害光パス2③

図 4 グリーディ再配置方式(実行例)

(2)グリーディ再配置方式の課題
計画的再配置方式をベースに, 妨害パスがあった場合には, 再帰呼び出しにより先に妨害パスを再配置することにより通信を切断することなく, 安全にパスの再配置ができる本方式だが, 再帰呼び出しを使用するのでネットワークが混雑してきた場合, 再配置先の経路探索→妨害パス有り→妨害パスの再配置先の経路探索→妨害パス有り...といったように再帰呼び出しを繰り返すことになり他の 2 方式と比較して１回の再配置におけるオーバーヘッドが大きくなってしまう.

4.各方式の評価
4.1.シミュレーション
下記の手順でシミュレーションを行う.
STEP1. 初期パス配置: 最初にネットワーク内にパスを配置.
STEP2. リンク解放命令:パスが配置されているリンクのいずれか１ヶ所を使用不可とする命令を出し,対象リ ンクを利用しているパスが再配置を必要とする状況を発生させる.
STEP3. 配置に失敗した場合はその時点でシミュレーションを終了. 再配置に成功した場合は結果を出力し終了.
このシミュレーションを STEP1 において初期パスの配置本数を 1 から 7 本, 配置本数ごとに使用不可とするリンクの場所を変えて 3 回, 合計 21 回のシミュレーションを各方式ごとに行う. 1 リンクに配置可能なパスは１本のみとする. グリーディ再配置方式のシミュレーショ
ンでは, 光パス再配置の優先度は, 再配置の命令を受けた光パスを最も再配置の優先度の高いパスとして設定し, 再配置を行うようにプログラムを実装する.
4.2.評価観点
光パス再配置方式の評価項目には, ネットワークのリソース効率や通信サービス継続性等の指標が挙げられるが, 本研究では評価項目として再配置成功数とパス使用率の２つを設定し評価を行う. 以下はその 2 項目の説明である.
①再配置成功数：命令を受けて再配置を実行し,それが成功した回数. 指標の重要度としては下に記述するパス使用率よりも重要なものである.
②パス使用率：再配置後のパスがネットワーク全体に占める割合. たとえばノード間のリンクすべての距離の合計が 100 であるネットワークに距離 10 のパスが 2本配置されていた場合, この値は 0.20(20%)となる. 同条件で再配置を行った場合, この値が小さいほどリソース効率のよい再配置を行ったといえる. 今回のシミュレーションでは, 再配置後にネットワーク内に配置されていた全てのパスを対象とした使用率と, パスが配置されているリンクが使用不可となり再配置の対象となったパスのみを対象とした使用率の 2 つの結果を出力する.
また, 本研究において最適経路を求めるための評価指標を遅延や帯域などを考慮しないノード間の実距離とし, 探索アルゴリズムにダイクストラ法を採用した[5].
4.3.ネットワークモデル
米国大手通信事業者である Sprint で, 実際に使用されているネットワーク[6]をモデルとする. グローバルに展開されている MPLS ネットワーク網の中で, 北米エリアのネットワーク網を簡略化したモデルをシミュレーションに用いる.

図 5 ネットワークモデル図

5.結果
5.1 再配置成功数
指標として最も重要とされる再配置の成功数について
は, シミュレーション 21 回中, 動的再配置方式が 18 回,計画的再配置方式が 16 回, グリーディ再配置方式は19 回となりグリーディ再配置方式がもっとも多いという結果になった.
5.2 平均パス使用率
パス使用率の結果をグラフにまとめたものを図 6,7 に示す. 縦軸にはパス使用率, 横軸には再配置後に有効となっているパスの本数をとった. 有効になっている
パスとは, 使用不可となっているリンクを使用していないパスのことで, 命令を受けたが再配置に失敗したパスは有効なパスとはみなさないものとする. シミュレーショ
ン条件上有効パス本数は初期配置パス本数と同じかそれよりも 1 本少ないかのどちらかとなる. 例えば初期配
置パス本数 4 本でシミュレートを行った際, 再配置に成功した場合は有効パス 4 本, 失敗した場合は有効パス3 本として扱う. 再配置失敗となった際は, 有効でないパスが使用しているリソースも使用率の計算に含めるものとする. グラフ縦軸の使用率はこれらの有効パス本数ごとの使用率の平均をとったものである. 図 6 は, 再配置後にネットワーク内に配置されていた全てのパスの使用率で, 図 7 は再配置の対象となったパスのみの使用率をまとめたものである. まず図 6 に注目する. 計画的再配置方式のパス使用率が他 2 方式のものよりも大きくなっており 3 方式の中ではもっと効率の悪い再配置を行っていることがわかる. 動的再配置方式とグリーディ再配置方式については , 前者の方がやや使用率が低くなっている. なお計画的再配置方式は有効パス 7本となるケースがなかったため値なしとした . 次に図 7に注目する. 再配置の対象となったパスのみの使用率に注目したグラフである. 再配置の対象となったパスの長さによって使用率はバラバラだが, どの点をみても再配置対象パスに限って言えばグリーディ再配置方式が他の 2 方式よりも少ない使用率で再配置を行えていることが分かる. この結果は, パスに優先度を設定し再配置を行うことのできるグリーディ再配置方式の優位性が出た形となっている.

6.考察
上記の結果より, 指標としてもっとも重要とされる再配置再成功数が最も高かったのはグリーディ再配置方式だった. リソース効率という点に関しては最も優れているのは動的再配置方式という結果がでた. しかし, グリーディ再配置方式との差は小さく, その差も有効パス本数が増えるにつれ小さくなっているのでネットワーク, トラフィック量が大きくなるにつれその差も埋まると考えられる. またグリーディ再配置方式は再配置の対象が優先度の高いパスの場合, 動的再配置方式よりも効率のよい再配置を行えるという利点も存在する. 従って, 複雑化, 大規模化が進んでいる現在のネットワーク事情を考慮すると再配置の成功率が高く, パスごとに優先度を設定し, 複雑なネットワークのパス管理も行うことができるグリーディ再配置方式が最も優れた再配置方式であると考えられる.

7.今後の課題
555045403530252015105

本研究では, 評価項目を再配置成功数とパス使用率の 2 つを出力し, 評価を行ったが光パス再配置方式の評価指標としては, 通信サービス継続性などの指標が存在し, それらの指標の選択により今回とは違った結果が得られると考えられる. 今回最も優れているという結果となったグリーディ再配置方式も再配置におけるオーバヘッドを指標に加味すれば結果もまた異なってくる可能性がある. よって評価指標を変えて, 別の視点でのシミュレーションということを今後の課題としたい.

動的再配置方式
計画的再配置方式
グリーディ再配置方式

1234567有効パス本数(本)参考文献

図 6 配置パス全体の使用率30
動的再配置方式
25

計画的再配置方式
グリーディ再配置方式

201510512345有効パス本数(本)図 7 再配置対象パスのみの使用率67[1]高井伸之, 別所雄三, 馬場義昌, “光パス最適再配置方式の提案,” 信学技報, vol.108, no.481,
ICM2008-79, pp. 121-126, 2009 年 3 月.
[2]中島隆, 松岡伸治, 渡辺篤, “レイヤー 1 ネットワーク
制御,” 日経コミュニケーション, 2009 年 12 月 15 日号 pp. 66-67.
[3]萩本和男, 山林由明, 今宿亙, “身近になる光ネットワーク （１７）光ネットとＩＰを統合する「ＧＭＰＬＳ」,” 日経コミュニケーション, 2005 年 12 月 15 日号 pp. 154-155.
[4]中平圭裕, ”光通信ネットワークにおける光パス再配置方法,” 公開特許広報 公開 2006-166316[5]滝根哲哉, 伊藤大雄, 西尾章治郎, “ネットワーク設計理論,” 岩波書店, pp. 158-162.
[6]Sprint ホームページ https://www.sprint.net/