(57)【特許請求の範囲】
【請求項１】
パスを収容するノードが接続される転送網において、その転送網内のエッジノードとエッジノードとを結ぶパスの経路を設定する経路設定方法であって、
コンピュータが、
前記転送網内のトポロジおよびトラヒックをトラヒック行列として記憶手段に記録するトラヒック行列管理手順と、
前記トラヒック行列を元に網内のリンク利用率の大きいリンクを選択する対象リンク決定手順と、
前記選択されたリンクに収容されるパスからトラヒック量の多いパスを選択する対象パス決定手順と、
前記選択されたパスの経路計算を行い、その結果に基づいて経路の変更をノードに指示する経路計算手順と、
を実行することを特徴とする経路設定方法。
【請求項２】
前記対象リンク決定手順は、網のリンクについて、リンク利用率が最も高いリンクを選択し、前記対象パス決定手順は、選択したリンクが収容するパスで、トラヒック量が最も高いパスを選択することを特徴とする請求項１に記載の経路設定方法。
【請求項３】
前記対象リンク決定手順は、網のリンクについて、リンク利用率が最も高いリンクを選択し、前記対象パス決定手順は、選択したリンクが収容するパスで、トラヒック量が所定順位以上のパスを選択することを特徴とする請求項１に記載の経路設定方法。
【請求項４】
前記対象リンク決定手順は、網のリンクについて、リンク利用率が所定順位以上のリンクを選択し、前記対象パス決定手順は、選択したリンクそれぞれにおいて、収容するパスのトラヒック量が最も高いパスを選択することを特徴とする請求項１に記載の経路設定方法。
【請求項５】
前記対象リンク決定手順は、網のリンクについて、リンク利用率が所定値以上のリンクを選択し、前記対象パス決定手順は、選択したリンクそれぞれにおいて、収容するパスのトラヒック量が所定順位以上のパスを選択することを特徴とする請求項１に記載の経路設定方法。
【請求項６】
前記対象パス決定手順は、選択したリンクそれぞれにおいて、収容するパスに関するトラヒック量およびホップ数の積が所定順位以上のパスを選択することを特徴とする請求項１に記載の経路設定方法。
【請求項７】
前記対象パス決定手順は、選択したリンクそれぞれにおいて、収容するパスに関するホップ数が所定値以上、かつ、トラヒック量が所定順位以上のパスを選択することを特徴とする請求項１に記載の経路設定方法。
【請求項８】
パスを収容するノードが接続される転送網において、その転送網内のエッジノードとエッジノードとを結ぶパスの経路を設定する経路設定装置であって、
前記転送網内のトポロジおよびトラヒックをトラヒック行列として記憶手段に記録するトラヒック行列管理部と、
前記トラヒック行列を元に網内のリンク利用率の大きいリンクを選択する対象リンク決定部と、
前記選択されたリンクに収容されるパスからトラヒック量の多いパスを選択する対象パス決定部と、
前記選択されたパスの経路計算を行い、その結果に基づいて経路の変更をノードに指示する経路計算部と、
を有することを特徴とする経路設定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路設定方法および経路設定装置に関する。
【背景技術】
【０００２】
近年のＡＤＳＬ（Asymmetric Digital Subscriber Line）、光アクセスなどアクセス回線速度の向上とブロードバンドサービスの加入者の増加は急速なペースで進行している。さらにアクセス回線速度の高速化に伴い、Ｐ２Ｐ（Peer to peer）に代表される大容量ファイル転送などの新しいアプリケーション、コンテンツ配信といった高スループットの通信などの新しいデータ系サービスが急増し、バックボーントラヒックが増えつつある。
【０００３】
これらの大容量のトラヒックを効率的に転送するため、リソースを効率的に利用可能とするＴＥ（Traffic Engineering）機能が必要となる。これまでにバックボーン網におけるリソースの効率的な利用を達成するため、ＭＰＬＳ（Multiprotocol Label Switching）技術、ＧＭＰＬＳ（Generalized MPLS）技術、非同期転送モード（ＡＴＭ：Asynchronous Transfer Mode）技術等を用いたＴＥが広く適用されている。
【０００４】
なお、網内を流れるトラヒックは、時間が経過すると変更している場合（動的なトラヒックとなる場合）が多い。ある時点におけるトラヒックをもとに網内のパスの経路を計算しても、別の時点では適合しなくなることもある。そのため、網内のパスの経路計算は、１回だけでなく、現在の網内を流れるトラヒックを反映して、何度も行う必要がある。
【０００５】
従来技術のＴＥは、パスの経路を再計算することにより、網スループットの向上、輻輳の緩和といった効用が得られる。例えば、ＭＰＬＳ−ＴＥの従来技術であるＷａｎｇ法（非特許文献１）においては、網内のパスであるＬＳＰ（Label Switched Path）の経路を定期的に再計算する。しかし、Ｗａｎｇ法は、単に複数回パスの経路を計算するだけであり、トラヒックの変更と経路計算とのタイミングは全く独立であるため、動的なトラヒックの考慮を行っていない。
【０００６】
また、特許文献１においては、動的なトラヒックを考慮して、パスが取りうる複数の経路から、網内の網コストの最小化を実現する経路計算方法の提案が行われている。
【非特許文献１】Y.Wang,et al.,“Explicit Routing Algorithms for Internet Traffic Engineering,”、Eight International Conference on Computer Communications and Networks、Oct1999、pp.582-588
【特許文献１】特開２００２−２５２６３９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
なお、パスの経路を再計算することにより、現在アクティブであるパスを変更する必要がある。パスの変更においては、パスの経路を切り替えるときに、事前に設定したあるパスの解放および新たなパスの新設が必要となる。そのとき、変更するパスの本数が多いと、網に余分な負担をかけてしまう。負担とは、例えば、パス変更に伴う管理メッセージを処理するために、パスを設定するノードのＣＰＵ（Central Processing Unit）利用率が増大してしまうことである。
【０００８】
さらに、パスの変更のための管理メッセージ量は経路変更を伴うパス数に比例して多くなってしまうため、網が大規模化すると大きな問題となる。また帯域保証を行う網においては、経路切替を行った後であっても帯域保証を実現するために網資源を確保する必要がある。よって、経路変更を伴うパス数が多くなると、余分な網資源を確保しておかなければならない。
【０００９】
なお、特許文献１に記載の技術は、網コストを最小化することが目的であるが、再計算時に経路変更を伴うパスの数は考慮していなかった。そのため、網コストを最小化するために、経路変更を伴うパスの数は多くなりがちであった。つまり、特許文献１に記載の技術は、パスの変更に伴う利益（網コストの減少）のみに着目している。しかし、パスの変更に伴う不利益（管理メッセージの増大）が、パスの変更に伴う利益（網コストの減少）よりも大きいときには、パスの変更をしないほうが望ましい。
【００１０】
つまり、パスの再計算で算出された変更に伴う各パスについて、パスの変更を行う利益が大きいパスを変更対象として選択し、利益が小さいパスを選択しないことで、変更するパスの本数を抑制することが必要となる。その結果、パスの変更を行う利益および不利益をバランスよく享受できる。
【００１１】
そこで本発明の目的は、網資源の効率的な利用を達成しつつ、再計算時に経路変更を伴うパス数を削減することである。
【課題を解決するための手段】
【００１２】
前記課題を解決するために、本発明は、パスを収容するノードが接続される転送網において、その転送網内のエッジノードとエッジノードとを結ぶパスの経路を設定する経路設定方法であって、コンピュータが、前記転送網内ののトポロジおよびトラヒックをトラヒック行列として記憶手段に記録するトラヒック行列管理手順と、前記トラヒック行列を元に網内のリンク利用率の大きいリンクを選択する対象リンク決定手順と、前記選択されたリンクに収容されるパスからトラヒック量の多いパスを選択する対象パス決定手順と、前記選択されたパスの経路計算を行い、その結果に基づいて経路の変更をノードに指示する経路計算手順と、を実行することを特徴とする。
【００１３】
これにより、網のパス設定において網資源の効率的な利用と経路変更に伴うパス設定数の削減を行うことができる。
【００１４】
本発明は、前記対象リンク決定手順が、網のリンクについて、リンク利用率が最も高いリンクを選択し、前記対象パス決定手順が、選択したリンクが収容するパスで、トラヒック量が最も高いパスを選択することを特徴とする。
【００１５】
これにより、経路変更を伴うパス数が１本なので、パス解放および新設のための管理メッセージ量が少なくて済む。
【００１６】
本発明は、前記対象リンク決定手順が、網のリンクについて、リンク利用率が最も高いリンクを選択し、前記対象パス決定手順が、選択したリンクが収容するパスで、トラヒック量が所定順位以上のパスを選択することを特徴とする。
【００１７】
これにより、選択されるパスの本数を明示的に指定できるので、パスの変更にかかるオーバーヘッドを一定に抑えることができる。
【００１８】
本発明は、前記対象リンク決定手順が、網のリンクについて、リンク利用率が所定順位以上のリンクを選択し、前記対象パス決定手順が、選択したリンクそれぞれにおいて、収容するパスのトラヒック量が最も高いパスを選択することを特徴とする。
【００１９】
これにより、選択されるパスの本数を明示的に指定できるので、パスの変更にかかるオーバーヘッドを一定に抑えることができる。
【００２０】
本発明は、前記対象リンク決定手順が、網のリンクについて、リンク利用率が所定値以上のリンクを選択し、前記対象パス決定手順が、選択したリンクそれぞれにおいて、収容するパスのトラヒック量が所定順位以上のパスを選択することを特徴とする。
【００２１】
これにより、パスの本数に影響されずに、所定の水準以上の効率化を達成できる。
【００２２】
本発明は、前記対象パス決定手順が、選択したリンクそれぞれにおいて、収容するパスに関するトラヒック量およびホップ数の積が所定順位以上のパスを選択することを特徴とする。
【００２３】
これにより、選択されるパスの本数を明示的に指定できるので、パスの変更にかかるオーバーヘッドを一定に抑えることができる。
【００２４】
本発明は、前記対象パス決定手順が、選択したリンクそれぞれにおいて、収容するパスに関するホップ数が所定値以上、かつ、トラヒック量が所定順位以上のパスを選択することを特徴とする。
【００２５】
これにより、パスの本数に影響されずに、所定の水準以上の効率化を達成できる。
【００２６】
本発明は、パスを収容するノードが接続される転送網において、その転送網内のエッジノードとエッジノードとを結ぶパスの経路を設定する経路設定装置であって、前記転送網内のトポロジおよびトラヒックをトラヒック行列として記憶手段に記録するトラヒック行列管理部と、前記トラヒック行列を元に網内のリンク利用率の大きいリンクを選択する対象リンク決定部と、前記選択されたリンクに収容されるパスからトラヒック量の多いパスを選択する対象パス決定部と、前記選択されたパスの経路計算を行い、その結果に基づいて経路の変更をノードに指示する経路計算部と、を有することを特徴とする。
【００２７】
これにより、網のパス設定において網資源の効率的な利用と経路変更に伴うパス設定数の削減を行うことができる。
【発明の効果】
【００２８】
本発明によれば、網内のリンク利用率、パスのトラヒック情報、および、パスの経路をもとに、該当パスを選択することで、網のパス設定において網資源の効率的な利用と、経路変更に伴うパス設定数の削減とを行うことができる。
【発明を実施するための最良の形態】
【００２９】
以下に、本発明が適用される経路設定システムの一実施形態について、図面を参照して詳細に説明する。
【００３０】
本実施形態は、網資源の効率化を達成しつつ、再計算時に経路変更を伴うパス数を削減することを特徴とする。なお、網資源の効率化とは、網資源利用の平均化であり、具体的には各リンクのリンク利用率（トラヒックの使用帯域／リンクの通信可能帯域）の最小化を実現する網内のパスの経路を決定することである。これにより、各リンクのリンク利用率を均一化し、転送網全体のスループットを向上することができる。また、経路変更を伴うパス数を削減することで、網全体の資源の効率的な利用と経路変更によるサービス中断発生の予防、管理メッセージの抑制などができる。
【００３１】
なお、経路変更を伴うパス数を削減するために、変更対象とするパスは、例えば、リンク利用率の大きいリンクに収容されるパス、かつ、トラヒック量の多いパスとする。このような変更対象とするパスは、網内のリンク利用率を平均化する際、１本のパスがリンク利用率の平均化に与える影響が大きいため、その他のパスよりも経路変更を行う効果が大きい。
【００３２】
図１は、本実施形態における経路設定システムの構成の概略を表したものである。パケット転送網９内には、パスの終端点となるエッジノード２が配置されている。エッジノード２間には複数の中継ノード３が配置されており、エッジノード２間の転送パケットを中継するようになっている。パケット転送網内にはあらかじめエッジノード間でパスが設定されており、このパス上をデータ通信トラヒックは転送される。なお、図１では網内に経路計算装置を１つとしてあるが、各ノードに分散的に配備することも可能である。経路設定装置１は、エッジノード２および中継ノード３に、パスの設定を指示する。
【００３３】
図２に示す経路設定装置１は、機能部として、トポロジ管理部１１、パス管理部１２、トラヒック行列管理部１３、対象リンク決定部１４、対象パス決定部１５、および、経路計算部１６を有する。なお、経路設定装置１は、演算処理を行う際に用いられる記憶手段としてのメモリと、前記演算処理を行う演算処理装置と、データを入出力するためのインタフェースとを少なくとも備えるコンピュータとして構成される。なお、メモリは、ＲＡＭ（Random Access Memory）などにより構成される。演算処理を実行する各機能部は、ＣＰＵ（Central Processing Unit）によって構成される演算処理装置が、メモリ上のプログラムを実行することで、実現される。以下、各機能部を具体的に説明する。
【００３４】
トポロジ管理部１１は、入力されたトポロジおよびリンク利用率を集約し、網全体のトポロジおよび網内の全リンクのリンク利用率として記憶手段に記録する。パス管理部１２は、入力されたパスのトラヒック量およびパスの経路を集約し、網内の全パスのトラヒック量および経路として記憶手段に記録する。
【００３５】
トラヒック行列管理部１３は、集約パスのトラヒック量と集約パスの経路から網内のトラヒック行列を作成して記憶手段に記録する。なお、トラヒック行列は網内のノードから他のノードヘのトラヒック量を与える行列であり、縦軸、横軸はノード番号等で与えられる。トラヒック行列の作成方法としては、各パスのトラヒック量を測定することにより各ノード間のトラヒック量を求める方法、トラヒック量の測定を行わず、トラヒック行列そのものを推定する方法等が存在する。なお、トラヒック行列を推定する方法は、例えば、Simple gravity model、Global gravity model、および、Tomo-gravity modelなどを採用することにより、実現される。また、トラヒック行列を推定する方法および推定したトラヒック行列を用いたＴＥの有効性の評価方法は、文献（M.Roughan,et al.,“Traffic Engineering with Estimated Traffic Matrices,”ACM Internet Measurement Conference 2003,pp.248-258）に記載されている。
【００３６】
対象リンク決定部１４は、トラヒック行列を元に網内の任意のリンクを選択する。対象パス決定部１５は、パス管理部１２の情報および選択されたリンクから対象リンク内に収容されるパスから任意のパスを選択する。経路計算部１６は、選択されたパスの経路計算を行い、その結果に基づいて経路の変更を指示する旨の経路切替要求を送信する。
【００３７】
網機器は、受信したパスの経路切替要求に従って、パスの経路を変更する。なお、パスの経路を変更するためには、現在アクティブであるパスを停止させ、変更先のパスを新たに生成する必要がある。そこで、現在のパスの停止手順と、変更先のパスの可動手順との順序が問題となる。まず、現在のパスの停止手順→変更先のパスの可動手順とする手法では、現在のパスも変更先のパスも可動していない時間が存在するために、サービス中断の恐れがある。
【００３８】
なお、網機器は、変更先のパスの可動手順→現在のパスの停止手順とする手法（make-before-break）を採用することで、サービス中断を抑制できる。しかし、make-before-breakでは、経路変更に伴うパケットの到達順序逆転などが発生してしまう。なお、make-before-breakを採用するか否かは、あらかじめ網機器に設定しておいてもよいし、経路切替要求に含めてもよい。
【００３９】
図２における矢印は、各機能部間でやりとりされる情報を示す。以下、やりとりされる情報の具体的な内容を説明する。
【００４０】
トポロジ管理部１１は、トポロジおよびリンク利用率の入力を受け付ける。パス管理部１２は、パスのトラヒック量およびパスの経路の入力を受け付ける。なお、トポロジ管理部１１およびパス管理部１２が入力を受け付ける情報は、ノード等から収集するか、経路設定装置１が直接的に収集する。
【００４１】
トポロジ管理部１１は、集約したトポロジおよびリンク利用率を、トラヒック行列管理部１３および対象リンク決定部１４に通知する。パス管理部１２は、集約したパスのトラヒック量およびパスの経路を、トラヒック行列管理部１３および対象パス決定部１５に通知する。
【００４２】
トラヒック行列管理部１３は、トラヒック行列を、対象リンク決定部１４に通知する。対象リンク決定部１４は、選択したリンクを、対象パス決定部１５に通知する。対象パス決定部１５は、選択したパスを、経路計算部１６に通知する。経路計算部１６は、選択したパスの経路切替要求を、パスを設定する網機器（エッジノード２、中継ノード３）に通知する。
【００４３】
以下、図３のフローチャートを説明する。
【００４４】
トポロジ管理部１１およびパス管理部１２は、網の情報（トポロジおよびリンク利用率、ならびに、パスのトラヒック量およびパスの経路）を登録する（Ｓ１１）。経路計算部１６は、トラヒック行列をもとにパスの経路を計算する（Ｓ１２）。トラヒック行列管理部１３は、トラヒック行列に変動が有るか否かを判定する（Ｓ１３）。なお、トラヒック行列の変動を検知する方法は、動的な実測値をもとにしてもよいし、トラヒック行列が変動するであろう時刻をあらかじめ静的に入力しておいてもよい。トラヒック行列管理部１３は、変動がないときには（Ｓ１３，Ｎｏ）、変動が有るまで待つ。以下、変動があったとき（Ｓ１３，Ｙｅｓ）の動作を説明する。
【００４５】
対象リンク決定部１４は、リンク利用率をもとにリンクを選択する（Ｓ１４）。対象パス決定部１５は、選択されたリンクのトラヒック量をもとにパスを選択する（Ｓ１５）。経路計算部１６は、選択されたパスの経路を計算する（Ｓ１６）。なお、パスの経路を計算する方法は、例えば、数理計画法などにより最適化問題を解く方法、ダイクストラ法などの手法がある。経路計算部１６は、計算された経路に従ってパスの経路切替を要求する（Ｓ１７）。
【００４６】
なお、リンクの選択方法（Ｓ１４）およびパスの選択方法（Ｓ１５）の組み合わせは、様々な手法を採用することができる。以下、それらの組み合わせの一例を示す。
【００４７】
第１手法は、リンクの選択方法が１本のリンク（リンク利用率が最も高いリンク）であり、パスの選択方法が１本のパス（１本のリンクが収容するパスで、トラヒック量が最も高いパス）である。
【００４８】
第２手法は、リンクの選択方法が１本のリンク（リンク利用率が最も高いリンク）であり、パスの選択方法がＮ本のパス（１本のリンクが収容するパスで、トラヒック量が所定順位以上のパス）である。
【００４９】
第３手法は、リンクの選択方法がＭ本のリンク（リンク利用率が所定順位以上のリンク）であり、パスの選択方法がＭ本のパス（Ｍ本のリンクそれぞれにおいて、収容するパスのトラヒック量が最も高いパス）である。
【００５０】
第４手法は、リンクの選択方法がＰ本のリンク（リンク利用率が所定値以上のリンク）であり、パスの選択方法がＱ本のパス（Ｐ本のリンクそれぞれにおいて、収容するパスのトラヒック量が所定順位以上のパス）である。
【００５１】
第５手法は、リンクの選択方法がＲ本のリンク（リンク利用率をもとに選択）であり、パスの選択方法がＳ本のパス（Ｒ本のリンクそれぞれにおいて、収容するパスに関するトラヒック量およびホップ数の積が所定順位以上のパス）である。
【００５２】
第６手法は、リンクの選択方法がＸ本のリンク（リンク利用率をもとに選択）であり、パスの選択方法がＹ本のパス（Ｘ本のリンクそれぞれにおいて、収容するパスに関するホップ数が所定値以上、かつ、トラヒック量が所定順位以上のパス）である。
【００５３】
第１手法により選択された１本のパスは、網内のリンク利用率の平均化に対する寄与が最も大きい。よって、前記のパスの経路変更を行うことは、複数本の経路変更を行うことによる網資源利用の最適化とほぼ同様の効果を得ることができる。また、経路変更を伴うパス数が１本なので、パス解放および新設のための管理メッセージ量が少なくて済む。
【００５４】
一方、第２手法〜第６手法は、複数本のパスを経路変更対象とすることで、網資源の利用をさらに効率的にすることができる。なお、パスまたはリンクの選択方法として所定値を用いることにより、パスの本数に影響されずに、所定の水準以上の効率化を達成できる。一方、パスまたはリンクの選択方法として所定順位を用いることにより、選択されるパスの本数を明示的に指定できるので、パスの変更にかかるオーバーヘッドを一定に抑えることができる。
【００５５】
以下、本実施形態の手法と比較例とを比較することにより、本実施形態の手法を評価する。
【００５６】
図４の網トポロジ（Ｃｏｓｔ２３９モデル）は、トポロジのベンチマークとして一般的に用いられている。なお、Ｃｏｓｔ２３９モデルは、ヨーロッパに設置された物理的な光ネットワークであり、ＷＤＭ（Wavelength Division Multiplexing）により実現されている。また、トラヒック行列を事前に与える方法として、Ｇｒａｖｉｔｙモデルと呼ばれる方法により、各ノード間のトラヒックを決定した。Ｇｒａｖｉｔｙモデルは各ノード間のトラヒック量は各ノードの人口の積に比例し、各ノード間の距離の２乗に反比例するというものである。
【００５７】
図５は、図４にあるノード番号について、各ノードの人口を仮定した図である。このときの人口を人口Ａとする。また、トラヒック行列の動的変化を実現するため、本評価では各ノードの人口を変化させることとした。変化後の各ノードの人口も図５に併記する。このときの人口を人口Ｂとする。
【００５８】
まず、人口Ａのときのトラヒック行列をＧｒａｖｉｔｙモデルで計算し、このトラヒック行列を与えたときに、網内のリンク利用率を最小化するという目的関数を設定し、リンク利用率最小を実現する網内のパスの経路を決定する。次に人口Ｂに変化したトラヒック行列を用いて、前記と同様の計算を行う。このように計算した比較例の方式では、網内の各ノード間に存在するパスの経路について人口Ａの場合と変更があったパス数はパス総数１１０本に対し、３７本であった。また、この際の最大リンク利用率をＣとする。
【表１】
0004555769.tif 000002
【００５９】
一方、第２手法においては、上位６位のリンクに収容される最も高いトラヒック量のパス、つまり１１０本中６本のパスを変更させた場合、最大リンク利用率の値はＣの約１．０６倍であり、ほぼ最適解Ｃに近い値を有することがわかった。また、第３手法においては、上位６位のトラヒック量のパス、つまり１１０本中の６本のパスを変更させた場合、最大リンク利用率の値はＣの約１．０１倍となり、極めて最適解Ｃに近い値を得ることが可能となる。
【図面の簡単な説明】
【００６０】
【図１】本発明の一実施形態に関する経路設定システムを示す構成図である。
【図２】本発明の一実施形態に関する経路設定装置を示す構成図である。
【図３】本発明の一実施形態に関する経路設定処理を示すフローチャートである。
【図４】本発明の一実施形態に関するＣｏｓｔ２３９モデルの網トポロジを示すグラフである。
【図５】本発明の一実施形態に関するＣｏｓｔ２３９モデルにおける各ノードの人口を示す説明図である。
【符号の説明】
【００６１】
１      経路設定装置
２      エッジノード
３      中継ノード
１１    トポロジ管理部
１２    パス管理部
１３    トラヒック行列管理部
１４    対象リンク決定部
１５    対象パス決定部
１６    経路計算部
【図１】
0004555769.tif 000003
【図２】
0004555769.tif 000004
【図３】
0004555769.tif 000005
【図４】
0004555769.tif 000006
【図５】
0004555769.tif 000007