複数制約条件下でのパス経路計算 156081 晒谷 光一 ［竹中研究室］

平成 18 年度卒業研究発表会（日本大学工学部情報工学科）
No-10
複数制約条件下でのパス経路計算
Routing algorithm with multi constrained
156081
１
晒谷
光一
はじめに
① active ノードは previous active ノードに remove
message を送信する。
② remove message を受け取った active ノードは、自身
を active ノードに設定して、remove massage が来た
リンクを、追加するリンクの候補から除外する。
近年、ビデオチャットや音声チャット、オンラインゲ
ームなどのリアルタイムアプリケーションが急速に増加
している。これらのアプリケーションは、遅延や QoS 等
の厳しい制限をネットワークに要求する。
本稿では、まず DCLC(Delay Constrained Least Cost)
問題について述べ、この問題の解決手法として提案され
た。DCUR(delay Constrained Unicast Routing)
Algorithm について述べたのち、提案方式との有効性を
比較する。
２
S
1
ループ発生
2
1
1
1
Delay Constrained Least Cost Problem
DCLC 問題は source ノードから destination ノードま
での経路の遅延の合計が、遅延の制約条件を上回らない
ように、cost の最小の経路を見つける問題で、NP-hard[2]
である。
３
［竹中研究室］
1
３．２
DCUR アルゴリズム
４
経路構築アルゴリズム
提案方式
既存方式の DCUR は、経路探索の際すべての経路の探
索を行わない。このため、最適な経路の発見ができない
可能性がある。本提案では、この問題を解決するための
提案手法、Algorithm1 と Algorithm2 を提案する。
① source ノードを active ノードに設定する。
② active ノードの outgoing link で、最も link cost の低
いリンクを一つ選択して経路に加える。
③ 経路に加えたリンク先のノードを active ノードに設
定する。
④ 経路にリンクを追加した際、経路の合計が遅延の制約
条件を満たすか確認する。
<遅延の制約を満たす場合>
⑤ 経路構築アルゴリズム①～④を destination ノードが
active ノードになるまで繰り返す。
<遅延の制約条件を満たさない場合>
⑤ active ノードを previous active ノードに設定し、制
約条件を上回ったリンクを、一時的に除外する。
⑥ active ノードの outgoing link で最も link 遅延の低い
リンクを active ノードに加える。
⑦ active ノードに加えたリンク先のノードを active ノー
ドに設定する。
⑧ 経路構築アルゴリズム②～④を destination ノードが
active ノードになるまで繰り返す。
３．１．２
DCUR の問題点
DCUR の問題点は、active ノードの outgoing link に
対して一つしか経路計算を行わない事である。このため、
経路探索の際すべての経路の探索を行うことが出来ない。
このため、発見された source ノードから destination ノ
ードまでに構築された経路が必ずしも最適であるとは限
らない。
DCUR は DCLC 問題を解決するヒューリスティクな
手法の一つである。DCUR は、遅延が制限された中で、
cost が最小となる Unicast Routing を行う。
３．１．１
D
図 1 DCUR アルゴリズムループ発生例
Delay Constrained Unicast Routing
３．1
2
４．１ Algorithm1
①
②
③
④
ループ除去アルゴリズム
DCUR アルゴリズムは、経路構築を行う際、outgoing
link の中で、一つしか経路計算を行わない、このため、
DCUR アルゴリズムはループが発生する可能性がある。
この問題を解決するため、以下にループ除去するアルゴ
リズムを示す。
コストをメトリックとした Dijkstra Algorithm を
用いて、shortest path tree を構築する。shortest
path tree にリンクを追加する際、tree にリンクを
追加した時の経路が、遅延の制約条件を満たすかを
確認する。
制約を満たさない場合、Dijkstra Algorithm で追加
するリンクを除外する。
Destination に到達するまで①～②を繰り返す。
destination ノードまでの経路が構築できば、アル
ゴリズムを終了する。しかし、①で destination ノ
ードまでの経路が構築できなければ、経路情報とネ
ットワークを計算前の最初の状態に戻す。
遅延をメトリックにして Dijkstra Algorithm を用
いて source-destination（以下、s-d）間に最短経路
を構築する。
４．１．１
Algorithm1 の特徴
Algorithm1 の特徴として、source ノードから、遅延を
メトリックとした Dijkstra Algorithm を行うことによっ
て、source ノードと destination ノードの間に遅延の制
約条件を満たす経路が存在すれば必ず発見することがで
きる。
20
平成 18 年度卒業研究発表会 No-10
４．２
Algorithm2
3.5
3
③
④
⑤
⑥
⑦
４．２．１
3
Algorithm2の特徴
Algorithm1 では、経路が構築できない場合、遅延をメ
トリックとした Dijkstra Algorithm を用い s-d 間に遅延
最小経路を構築する。Algorithm2 では、リンクを除外す
る際に網の接続性の確認を加えることによって、網の接
続 性 を 保 ち 、 コ ス ト を メ ト リ ッ ク と し た Dijkstra
Algorithm で s-d 間の経路を発見する可能性を高める。
５ シミュレーションによる評価
シミュレーション条件
z
網モデル：NSFNET (14 ノード 20 リンク)
z
Source ノード:ランダムに選択
z
Destination ノード：source ノード以外からランダ
ムに選択
リンクコスト：[0,1]でランダムな値
z
z
リンク遅延：[0,1]でランダムな値
z
遅延制約条件：任意の値
z
リクエスト数：50000 件
Algorithm1
Algorithm2
DCUR
2
1.5
1
0.5
Algorithm1
Algorithm2
DCUR
2
1.5
1
0
0
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9
delay_constrained
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9
delay_constrained
図4 確立したパスに対する平均経路コスト 図5 確立したパスに対する平均経路遅延
2.5
2
1.5
Algorithm1
Algorithm2
1
0.5
0
0 0.4 0.8 1.2 1.6 2 2.4 2.8 3.2 3.6
delay_constrained
4
図 6 確立したパスに対する平均経路計算回数
図 3 について、Algorithm1 と Algorithm ともに同様に
の結果を得た。両提案方式と DCUR アルゴリズムでは提
案方式の方がわずかに計算成功確立が高い。これは、提
案両方式は destinaiton ノードの孤立が発生したとき、
遅延をメトリックに s-d 間に遅延を最小とした経路を構
築するため、s-d 間に制約を満たす経路が存在する限り必
ず経路を発見できるのに対して、DCUR は孤立が発生し
たときに経路構築要求が棄却されてしまうためである。
図 4,5 でも Algorithm1 と Algorithm2 の評価結果で、
ほとんど差は見られなかった。これは、計算成功確率が
同じ事から、Algorithm1 と Algorithm2 で同一の経路を
発見していることがわかる。DCUR アルゴリズムは、提
案方式が経路コストの合計を見ているのに対して、隣接
のリンクコストしか見ていない。このため、DCUR アル
ゴリズムは遅延制約が緩い状況では、s-d 間に経路を構築
際、あえて遠回りをするような経路構築を行ってしまう
可能性がある。逆に遅延制約条件が厳しい状況では、迂
回する事がないため、提案方式と同じ経路を発見できる。
図 6 における計算回数とは、source ノードから経路構
築を行った回数を示す。Algorithm2 は Algorithm1 に比
べ網の接続性の確認を行い、source ノードから Reroute
を行う。このため、Algorithm2 の方が、計算回数が多い。
この事から、Algorithm2 より Algorithm1 の方が有効で
あると言える。
まとめ
本 稿 では 、 DCLC 問 題 の解 決 手法 で ある 、 DCUR
Algorithm を紹介、その問題点を挙げ、その問題を解決
す る方式の提案と評価を行った。今後の予定として、
DCUR のシミュレーション評価を行い、提案方式と
DCUR アルゴリズム性能を比較していきたい。
図 2 ネットワークモデル
success_probability
2.5
0.5
６
100
90
80
70
60
50
40
30
average_delay
2.5
計算回数
②
コストをメトリックとした Dijkstra Algorithm を
用いて shortest path tree を構築する。shortest
path tree にリンクを追加する際、tree にリンクを
追加した時の経路が、遅延制約条件を満たすかを確
認する。
遅延制約条件を満たす場合は、destination ノード
までの経路が構築できれば、アルゴリズムを終了す
る。構築できていない場合は①へ。
遅延制約条件を満たさない場合は、追加するリンク
を除外する。リンクを除外する際、網の接続性の確
認を行う（接続性確認の方法を記述する）。
網の接続性が保たれる場合は、リンクを除外し①へ、
網の接続性が保たれない場合は⑤へ。
接続性の確認手法として、既に構築された tree をさ
かのぼり、リンクを除外しても網の接続性が保たれ
るリンクがある場合、該当リンクを除外する。そし
て、経路情報を初期化し、①に戻る。
接続性が保たれるリンクがない場合は、ネットワー
クと経路情報を計算前の最初の状態に戻し、⑦へ。
遅延をメトリックとした Dijkstra Algorithm を用
いて s-d 間に最短経路を構築する。
average_cost
①
参考文献
Algorithm1
Algorithm2
[1] Douglas S.Reeves and Hussein F.Salama,”A
Distributed Algorithm for delay-Constrained
unicast Routing”,IEEE//ACM TRANSACTION ON
NETWORKING,Vlo.8,NO.2,APRIL 2000
[2] Xin Jin,Xiande Liu,Shiyuan Xiao,“An Effective
Algorithm for delay Constrained Least Cost
Unicast Routing”,IEEE//ACM TRANSACTION ON
DCUR
20
10
0
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9
delay_constrained
図 3 経路計算成功確率
21
NETWORKING,0-7803-8834,2005
22