(57)【要約】【課題】  マルチレイヤネットワークにおいて、ネットワーク構成、ノード構成の如何を問わず、ネットワークリソースを有効利用する。【解決手段】  各レイヤのネットワークでそれぞれのトポロジに基づき経路を仮想的に設定した仮想グラフを作成する際に、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が一つのレイヤにのみ存在する場合は、このレイヤの線分を用い、複数レイヤに存在する場合は、この中からコストが最小のものを選択する。このときに、各レイヤ毎に重み係数を乗じた後、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が複数レイヤに存在する場合は、この中からコストが最小のものを選択する。【選択図】  図１
2005341292.tif 000002
【特許請求の範囲】
【請求項１】
複数の異なるレイヤのネットワークが階層化されて構成されるマルチレイヤネットワークで、発ノードから着ノードまでのパスが経由するレイヤおよびノードの最短経路を前記発ノードまたは前記着ノードあるいは前記ノードとは別途に設けられた経路選択装置により選択する最短経路選択方法において、
各レイヤのネットワークでそれぞれのトポロジに基づき前記経路を仮想的に設定した仮想グラフを作成する際に、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が一つのレイヤにのみ存在する場合は、このレイヤの線分を用い、複数レイヤに存在する場合は、この中からコストが最小のものを選択する
ことを特徴とする最短経路選択方法。
【請求項２】
各レイヤ毎に重み係数を乗じた後、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が複数レイヤに存在する場合は、この中からコストが最小のものを選択する請求項１記載の最短経路選択方法。
【請求項３】
前記重み係数を決定するときに、
各レイヤの当初の重み係数を用いて、経路選択を規定の回数行い、このとき着ノードまでの経路が見つからない場合の割合であるブロック率を計算した後、重み係数の値を微小な値だけ変化させた後、再度、規定回数だけ経路選択を行ってブロック率を計算し、前回計算したブロック率と比較し、ブロック率が低下した場合は、前記微小な値だけ変化させた後の値を新たな重み係数とする第一のステップを実行し、
この第一のステップを実行した結果としてブロック率が増加した場合は、前記当初の重み係数の値を前記第一のステップとは逆方向に微小な値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に微小な値だけ変化させた後の値を新たな重み係数とする第二のステップを実行し、
この新たな重み係数を前記当初の重み係数と置き替えることにより前記第一および第二のステップをブロック率の低下がみられる限り繰り返し実行する
請求項２記載の最短経路選択方法。
【請求項４】
前記第一および第二のステップを実行した結果としてブロック率の低下がみられないときには、
前記当初の重み係数の値を前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第三のステップを実行し、
この第三のステップを実行した結果としてブロック率が低下しなかった場合は、前記当初の重み係数の値を前記第三のステップとは逆方向に前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第四のステップを実行し、
この新たな重み係数を前記当初の重み係数と置き替えることにより前記第三および第四のステップをブロック率が閾値以下となるまで繰り返し実行する
請求項３記載の最短経路選択方法。
【請求項５】
前記第三および第四のステップを実行した結果としてブロック率の低下がみられないときには、順次前記微小な値をさらに半分ずつ小さくして前記第三および第四のステップを繰り返し実行する請求項４記載の最短経路選択方法。
【請求項６】
複数の異なるレイヤのネットワークが階層化されて構成されるマルチレイヤネットワークで、自ノードから着ノードまでのパスが経由するレイヤおよびノードの最短経路を選択する手段を備えたノードにおいて、
前記選択する手段は、各レイヤのネットワークでそれぞれのトポロジに基づき前記経路を仮想的に設定した仮想グラフを作成する手段を備え、
この作成する手段は、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が一つのレイヤにのみ存在する場合は、このレイヤの線分を用い、複数レイヤに存在する場合は、この中からコストが最小のものを選択する手段を備えた
ことを特徴とするノード。
【請求項７】
前記コストが最小のものを選択する手段は、各レイヤ毎に重み係数を乗じた後、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が複数レイヤに存在する場合は、この中からコストが最小のものを選択する手段を備えた請求項６記載のノード。
【請求項８】
前記重み係数を決定する手段を備え、
この決定する手段は、
各レイヤの当初の重み係数を用いて、経路選択を規定の回数行い、このとき着ノードまでの経路が見つからない場合の割合であるブロック率を計算した後、重み係数の値を微小な値だけ変化させた後、再度、規定回数だけ経路選択を行ってブロック率を計算し、前回計算したブロック率と比較し、ブロック率が低下した場合は、前記微小な値だけ変化させた後の値を新たな重み係数とする第一のステップを実行する手段と、
この第一のステップを実行した結果としてブロック率が増加した場合は、前記当初の重み係数の値を前記第一のステップとは逆方向に微小な値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に微小な値だけ変化させた後の値を新たな重み係数とする第二のステップを実行する手段と、
この新たな重み係数を前記当初の重み係数と置き替えることにより前記第一および第二のステップをブロック率の低下がみられる限り繰り返し実行する手段と
を備えた請求項７記載のノード。
【請求項９】
前記第一および第二のステップを実行した結果としてブロック率の低下がみられないときには、
前記当初の重み係数の値を前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第三のステップを実行する手段と、
この第三のステップを実行した結果としてブロック率が低下しなかった場合は、前記当初の重み係数の値を前記第三のステップとは逆方向に前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第四のステップを実行する手段と、
この新たな重み係数を前記当初の重み係数と置き替えることにより前記第三および第四のステップをブロック率が閾値以下となるまで繰り返し実行する手段と
を備えた請求項８記載のノード。
【請求項１０】
前記第三および第四のステップを実行した結果としてブロック率の低下がみられないときには、順次前記微小な値をさらに半分ずつ小さくして前記第三および第四のステップを繰り返し実行する手段を備えた請求項９記載のノード。
【請求項１１】
請求項６ないし１０のいずれかに記載のノードを備えたことを特徴とするマルチレイヤネットワーク。
【請求項１２】
情報処理装置にインストールすることにより、その情報処理装置に、
複数の異なるレイヤのネットワークが階層化されて構成されるマルチレイヤネットワークで、自ノードから着ノードまでのパスが経由するレイヤおよびノードの最短経路を選択する機能を備えたノードに相応する機能を実現させるプログラムにおいて、
前記選択する機能として、各レイヤのネットワークでそれぞれのトポロジに基づき前記経路を仮想的に設定した仮想グラフを作成する機能を実現させ、
この作成する機能として、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が一つのレイヤにのみ存在する場合は、このレイヤの線分を用い、複数レイヤに存在する場合は、この中からコストが最小のものを選択する機能を実現させる
ことを特徴とするプログラム。
【請求項１３】
前記コストが最小のものを選択する機能として、各レイヤ毎に重み係数を乗じた後、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が複数レイヤに存在する場合は、この中からコストが最小のものを選択する機能を実現させる請求項１２記載のプログラム。
【請求項１４】
前記重み係数を決定する機能を実現させ、
この決定する機能として、
各レイヤの当初の重み係数を用いて、経路選択を規定の回数行い、このとき着ノードまでの経路が見つからない場合の割合であるブロック率を計算した後、重み係数の値を微小な値だけ変化させた後、再度、規定回数だけ経路選択を行ってブロック率を計算し、前回計算したブロック率と比較し、ブロック率が低下した場合は、前記微小な値だけ変化させた後の値を新たな重み係数とする第一のステップを実行する機能と、
この第一のステップを実行した結果としてブロック率が増加した場合は、前記当初の重み係数の値を前記第一のステップとは逆方向に微小な値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に微小な値だけ変化させた後の値を新たな重み係数とする第二のステップを実行する機能と、
この新たな重み係数を前記当初の重み係数と置き替えることにより前記第一および第二のステップをブロック率の低下がみられる限り繰り返し実行する機能と
を実現させる請求項１３記載のプログラム。
【請求項１５】
前記第一および第二のステップを実行した結果としてブロック率の低下がみられないときには、
前記当初の重み係数の値を前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第三のステップを実行する機能と、
この第三のステップを実行した結果としてブロック率が低下しなかった場合は、前記当初の重み係数の値を前記第三のステップとは逆方向に前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第四のステップを実行する機能と、
この新たな重み係数を前記当初の重み係数と置き替えることにより前記第三および第四のステップをブロック率が閾値以下となるまで繰り返し実行する機能と
を実現させる請求項１４記載のプログラム。
【請求項１６】
前記第三および第四のステップを実行した結果としてブロック率の低下がみられないときには、順次前記微小な値をさらに半分ずつ小さくして前記第三および第四のステップを繰り返し実行する機能を実現させる請求項１５記載のプログラム。
【請求項１７】
請求項１２ないし１６のいずれかに記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＧＭＰＬＳ(Generalized Multi Protocol
Label Switching)に代表されるマルチレイヤネットワーク制御技術に関する。
【背景技術】
【０００２】
ファイバネットワーク、波長ネットワーク、ＴＤＭネットワーク、パケットネットワークなどの複数のネットワークからなるマルチレイヤネットワークは、階層化されており、ファイバのリンクからなるネットワークトポロジを用いて波長のパスを選択し、こうして設定された波長のパスは、さらに上位レイヤのパケットレイヤなどからみると、リンクとしてみなされ、波長のリンクで構成されるネットワークトポロジを用いて、パケットのパスの経路選択が行われる。
【０００３】
このような階層化されたマルチレイヤネットワークにおいて、経路を計算する際に、どの経路でどのレイヤのネットワークを経由してパスを設定するかという問題がある。これまでは、上位レイヤのパスを設定する際に、なるべく既存の下位レイヤのリンクを用いるのか、それとも新規の下位レイヤのパスを設定した後にこれを用いて上位レイヤのパスを設定するか、という点に着目した経路選択アルゴリズムおよびこれを用いるネットワーク制御技術が提案されている（例えば、非特許文献１参照）。
【非特許文献１】K.Sato,N.Yamanaka,Y.Takigawa,M.Koga,S.Okamoto,K.Shiomoto,E.Oki,andW.Imajuku,“GMPLS-based photonic multilayer router(Hikari router)architecture:anoverview of traffic engineering and signaling technology”,IEEECommun.Mag.,Vol.40,No.3,pp.96-101,Mar.2002
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ネットワークにおいて、パスの経路選択を行う際には、マルチレイヤネットワークのリソースを有効に活用することを目的として経路選択を行う。前記背景技術では、あらかじめ決められたポリシにしたがって経路選択を行っていたが、ネットワーク構成、ノード構成によってポリシの向き不向きがあり、場合によってはネットワークリソースの有効利用につながらない場合がある。
【０００５】
本発明は、このような背景に行われたものであって、ネットワーク構成、ノード構成の如何を問わず、ネットワークリソースを有効利用することができる最短経路選択方法およびノードおよびマルチレイヤネットワークを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の第一の観点は、複数の異なるレイヤのネットワークが階層化されて構成されるマルチレイヤネットワークで、発ノードから着ノードまでのパスが経由するレイヤおよびノードの最短経路を前記発ノードまたは前記着ノードあるいは前記ノードとは別途に設けられた経路選択装置により選択する最短経路選択方法である。
【０００７】
ここで、本発明の特徴とするところは、各レイヤのネットワークでそれぞれのトポロジに基づき前記経路を仮想的に設定した仮想グラフを作成する際に、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が一つのレイヤにのみ存在する場合は、このレイヤの線分を用い、複数レイヤに存在する場合は、この中からコストが最小のものを選択するところにある（請求項１）。
【０００８】
このように、経路の選択に先立って各レイヤのネットワークでそれぞれのトポロジに基づき前記経路を仮想的に設定した仮想グラフを作成し、これにより経路を選択することにより、複数レイヤを経由するコストが最小となる最短な経路を選択することができる。
【０００９】
各レイヤ毎に重み係数を乗じた後、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が複数レイヤに存在する場合は、この中からコストが最小のものを選択することができる（請求項２）。
【００１０】
すなわち、マルチレイヤネットワークでは、同じコストでも各レイヤ毎にそのトラヒック収容可能性が異なる場合があるため、コストを一律に設定することは難しい場合がある。このため、同一点間を結ぶ線分が複数レイヤに存在する場合には、レイヤ間でコストを比較してコストが最小のものを選択するが、このときに、必ずしも、コスト最小の経路が最短経路とは限らない場合がある。例えば、あるレイヤのネットワークにおける最小コストが“５”であるときに、他のレイヤのネットワークにおける最小コストが“１０”であるが、この二つのレイヤを経由する経路は同じ距離である場合がある。すなわち、実際には、いずれのレイヤを選択しても距離は変わらないのに、常に、コストの小さい方のレイヤが選択されてしまうといったトラヒック割当ての不均衡が起こり得る。あるいは、コストの大きい方のレイヤがコストの小さい方のレイヤよりもトラヒック収容可能性が大きいといったルールの逆転も起こり得る。各レイヤ毎に重み係数を乗じることにより、このようなコストの不均衡を改善することができる。
【００１１】
なお、ここでいう距離とは、単に物理的な距離に限らずに、帯域の広さやサービス品質などの様々な要素を含めたトラヒック収容可能性をいう。
【００１２】
前記重み係数を決定するときに、各レイヤの当初の重み係数を用いて、経路選択を規定の回数行い、このとき着ノードまでの経路が見つからない場合の割合であるブロック率を計算した後、重み係数の値を微小な値だけ変化させた後、再度、規定回数だけ経路選択を行ってブロック率を計算し、前回計算したブロック率と比較し、ブロック率が低下した場合は、前記微小な値だけ変化させた後の値を新たな重み係数とする第一のステップを実行し、この第一のステップを実行した結果としてブロック率が増加した場合は、前記当初の重み係数の値を前記第一のステップとは逆方向に微小な値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に微小な値だけ変化させた後の値を新たな重み係数とする第二のステップを実行し、この新たな重み係数を前記当初の重み係数と置き替えることにより前記第一および第二のステップをブロック率の低下がみられる限り繰り返し実行することができる（請求項３）。
【００１３】
これにより、ブロック率が最小となる経路を選択するために有効な重み係数を効率良く自動的に設定することができる。
【００１４】
さらに、前記第一および第二のステップを実行した結果としてブロック率の低下がみられないときには、前記当初の重み係数の値を前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第三のステップを実行し、この第三のステップを実行した結果としてブロック率が低下しなかった場合は、前記当初の重み係数の値を前記第三のステップとは逆方向に前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第四のステップを実行し、この新たな重み係数を前記当初の重み係数と置き替えることにより前記第三および第四のステップをブロック率が閾値以下となるまで繰り返し実行することができる（請求項４）。
【００１５】
前記第三および第四のステップを実行した結果としてブロック率の低下がみられないときには、順次前記微小な値をさらに半分ずつ小さくして前記第三および第四のステップを繰り返し実行することができる（請求項５）。すなわち、重み係数の変化幅を徐々に小さくすることにより、最終的に最適な重み係数に収束させることができる。
【００１６】
これにより、前記第一および第二のステップによって重み係数が定まらないときでも、この第三および第四のステップにより重み係数を定めることができる。
【００１７】
本発明の第二の観点は、複数の異なるレイヤのネットワークが階層化されて構成されるマルチレイヤネットワークで、自ノードから着ノードまでのパスが経由するレイヤおよびノードの最短経路を選択する手段を備えたノードである。
【００１８】
ここで、本発明の特徴とするところは、前記選択する手段は、各レイヤのネットワークでそれぞれのトポロジに基づき前記経路を仮想的に設定した仮想グラフを作成する手段を備え、この作成する手段は、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が一つのレイヤにのみ存在する場合は、このレイヤの線分を用い、複数レイヤに存在する場合は、この中からコストが最小のものを選択する手段を備えたところにある（請求項６）。
【００１９】
前記コストが最小のものを選択する手段は、各レイヤ毎に重み係数を乗じた後、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が複数レイヤに存在する場合は、この中からコストが最小のものを選択する手段を備えることができる（請求項７）。
【００２０】
前記重み係数を決定する手段を備え、この決定する手段は、各レイヤの当初の重み係数を用いて、経路選択を規定の回数行い、このとき着ノードまでの経路が見つからない場合の割合であるブロック率を計算した後、重み係数の値を微小な値だけ変化させた後、再度、規定回数だけ経路選択を行ってブロック率を計算し、前回計算したブロック率と比較し、ブロック率が低下した場合は、前記微小な値だけ変化させた後の値を新たな重み係数とする第一のステップを実行する手段と、この第一のステップを実行した結果としてブロック率が増加した場合は、前記当初の重み係数の値を前記第一のステップとは逆方向に微小な値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に微小な値だけ変化させた後の値を新たな重み係数とする第二のステップを実行する手段と、この新たな重み係数を前記当初の重み係数と置き替えることにより前記第一および第二のステップをブロック率の低下がみられる限り繰り返し実行する手段とを備えることができる（請求項８）。
【００２１】
さらに、前記第一および第二のステップを実行した結果としてブロック率の低下がみられないときには、前記当初の重み係数の値を前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第三のステップを実行する手段と、この第三のステップを実行した結果としてブロック率が低下しなかった場合は、前記当初の重み係数の値を前記第三のステップとは逆方向に前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第四のステップを実行する手段と、この新たな重み係数を前記当初の重み係数と置き替えることにより前記第三および第四のステップをブロック率が閾値以下となるまで繰り返し実行する手段とを備えることができる（請求項９）。
【００２２】
前記第三および第四のステップを実行した結果としてブロック率の低下がみられないときには、順次前記微小な値をさらに半分ずつ小さくして前記第三および第四のステップを繰り返し実行する手段を備える（請求項１０）。
【００２３】
本発明の第三の観点は、本発明のノードを備えたことを特徴とするマルチレイヤネットワークである（請求項１１）。
【００２４】
なお、ノードに備えた前記各手段を経路選択装置としてノードとは別途に設けることもできる。この経路選択装置によって、各ノードの経路選択を一元的に管理することができる。
【００２５】
本発明の第四の観点は、情報処理装置にインストールすることにより、その情報処理装置に、複数の異なるレイヤのネットワークが階層化されて構成されるマルチレイヤネットワークで、自ノードから着ノードまでのパスが経由するレイヤおよびノードの最短経路を選択する機能を備えたノードに相応する機能を実現させるプログラムである。
【００２６】
ここで、本発明の特徴とするところは、前記選択する機能として、各レイヤのネットワークでそれぞれのトポロジに基づき前記経路を仮想的に設定した仮想グラフを作成する機能を実現させ、この作成する機能として、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が一つのレイヤにのみ存在する場合は、このレイヤの線分を用い、複数レイヤに存在する場合は、この中からコストが最小のものを選択する機能を実現させるところにある（請求項１２）。
【００２７】
前記コストが最小のものを選択する機能として、各レイヤ毎に重み係数を乗じた後、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が複数レイヤに存在する場合は、この中からコストが最小のものを選択する機能を実現させることができる（請求項１３）。
【００２８】
さらに、前記重み係数を決定する機能を実現させ、この決定する機能として、各レイヤの当初の重み係数を用いて、経路選択を規定の回数行い、このとき着ノードまでの経路が見つからない場合の割合であるブロック率を計算した後、重み係数の値を微小な値だけ変化させた後、再度、規定回数だけ経路選択を行ってブロック率を計算し、前回計算したブロック率と比較し、ブロック率が低下した場合は、前記微小な値だけ変化させた後の値を新たな重み係数とする第一のステップを実行する機能と、この第一のステップを実行した結果としてブロック率が増加した場合は、前記当初の重み係数の値を前記第一のステップとは逆方向に微小な値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に微小な値だけ変化させた後の値を新たな重み係数とする第二のステップを実行する機能と、この新たな重み係数を前記当初の重み係数と置き替えることにより前記第一および第二のステップをブロック率の低下がみられる限り繰り返し実行する機能とを実現させることができる（請求項１４）。
【００２９】
さらに、前記第一および第二のステップを実行した結果としてブロック率の低下がみられないときには、前記当初の重み係数の値を前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第三のステップを実行する機能と、この第三のステップを実行した結果としてブロック率が低下しなかった場合は、前記当初の重み係数の値を前記第三のステップとは逆方向に前記微小な値を半分にした値だけ変化させた後、規定回数だけ経路選択を行ってブロック率を計算し、前記当初の重み係数の値の場合のブロック率と比較し、ブロック率が低下した場合は、前記逆方向に前記微小な値を半分にした値だけ変化させた後の値を新たな重み係数とする第四のステップを実行する機能と、この新たな重み係数を前記当初の重み係数と置き替えることにより前記第三および第四のステップをブロック率が閾値以下となるまで繰り返し実行する機能とを実現させることができる（請求項１５）。
【００３０】
前記第三および第四のステップを実行した結果としてブロック率の低下がみられないときには、順次前記微小な値をさらに半分ずつ小さくして前記第三および第四のステップを繰り返し実行する機能を実現させることができる（請求項１６）。
【００３１】
なお、ノードとして実現する前記各機能を経路選択装置としてノードとは別途に実現することもできる。この経路選択装置によって、各ノードの経路選択を一元的に管理することができる。
【００３２】
本発明の第五の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である（請求項１７）。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００３３】
これにより、汎用の情報処理装置を用いて、マルチレイヤネットワークにおいて、ネットワーク構成、ノード構成の如何を問わず、ネットワークリソースを有効利用することができるノードを実現することができる。
【発明の効果】
【００３４】
本発明によれば、マルチレイヤネットワークにおいて、ネットワーク構成、ノード構成の如何を問わず、ネットワークリソースを有効利用することができる。
【発明を実施するための最良の形態】
【００３５】
本発明実施例の最短経路選択方法およびノードを図１ないし図６を参照して説明する。図１はマルチレイヤネットワークの例を示す図である。図２は仮想グラフ作成手順を示すフローチャートである。図３は重み係数決定手順を示すフローチャートである。図４は重み係数収束手順を示すフローチャートである。
【００３６】
本実施例は、図１に示すように、複数の異なるレイヤのネットワークが階層化されて構成されるマルチレイヤネットワークで、発ノードから着ノードまでのパスが経由するレイヤおよびノードの最短経路を前記発ノードまたは前記着ノードあるいは前記ノードとは別途に設けられた経路選択装置により選択する最短経路選択方法である。
【００３７】
一般的には、自己がこれからデータを発信する発ノードが経路選択を行うことが合理的であるが、着ノードが発ノードまでの経路選択を行ってもよいし、あるいは、これらノードとは別途に設けられた経路選択装置が一元的に複数のノード間の経路選択を行ってもよい。いずれが経路選択を行っても本発明の本質には影響しない。
【００３８】
ここで、本実施例の特徴とするところは、図２に示すように、各レイヤのネットワークでそれぞれのトポロジに基づき前記経路を仮想的に設定した仮想グラフを作成する際に、各レイヤの仮想グラフを構成する線分のうち（Ｓ１）、同一点間を結ぶ線分が一つのレイヤにのみ存在する場合は（Ｓ２）、このレイヤの線分を用い（Ｓ４）、複数レイヤに存在する場合は（Ｓ２）、この中からコストが最小のものを選択する（Ｓ３）ところにある（請求項１）。
【００３９】
本実施例では、各レイヤ毎に重み係数を乗じた後、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が複数レイヤに存在する場合は、この中からコストが最小のものを選択する（請求項２）。
【００４０】
図３に示すように、前記重み係数を決定するときに、各レイヤの当初の重み係数αを用いて（Ｓ１１）、経路選択を規定の回数行い（Ｓ１２、Ｓ１３）、このとき着ノードまでの経路が見つからない場合の割合であるブロック率を計算した後（Ｓ１４）、重み係数の値αを微小な値＋Δだけ変化させた後（Ｓ１５）、再度、規定回数だけ経路選択を行ってブロック率を計算し（Ｓ１６、Ｓ１７、Ｓ１８）、前回計算したブロック率と比較し（Ｓ１９）、ブロック率が低下した場合は（Ｓ２０）、前記微小な値だけ変化させた後の値（α＋Δ）を新たな重み係数とする（Ｓ２７）第一のステップを実行し、この第一のステップを実行した結果としてブロック率が増加した場合は（Ｓ２０）、当初の重み係数の値αを前記第一のステップとは逆方向に微小な値−Δだけ変化させた後（Ｓ２１）、規定回数だけ経路選択を行ってブロック率を計算し（Ｓ２２、Ｓ２３）、当初の重み係数の値αの場合のブロック率と比較し（Ｓ２４）、ブロック率が低下した場合は（Ｓ２５）、逆方向に微小な値−Δだけ変化させた後の値（α−Δ）を新たな重み係数とする（Ｓ２６）第二のステップを実行し、この新たな重み係数（α＋Δ）または（α−Δ）を当初の重み係数αと置き替える（Ｓ２６、Ｓ２７）ことにより前記第一および第二のステップをブロック率の低下がみられる限り繰り返し実行する（請求項３）。このときに、前記第一および第二のステップを実行した結果としてブロック率の低下がみられないときには、図４に示す重み係数収束手順へ移行する（Ｓ２８）。
【００４１】
重み係数収束手順は、図４に示すように、当初の重み係数の値αを微小な値＋Δを半分にした値＋Δ／２だけ変化させた後（Ｓ３１、Ｓ３２）、規定回数だけ経路選択を行ってブロック率を計算し（Ｓ３３、Ｓ３４、Ｓ３５）、当初の重み係数の値αの場合のブロック率と比較し（Ｓ３６）、ブロック率が低下した場合は（Ｓ３７）、微小な値＋Δを半分にした値＋２／Δだけ変化させた後の値（α＋（Δ／２））を新たな重み係数とする（Ｓ４６）第三のステップを実行し、この第三のステップを実行した結果としてブロック率が低下しなかった場合は、当初の重み係数の値αを前記第三のステップとは逆方向に微小な値−Δを半分にした値−Δ／２だけ変化させた後（Ｓ３８）、規定回数だけ経路選択を行ってブロック率を計算し（Ｓ３９、Ｓ４０、Ｓ４１）、当初の重み係数の値αの場合のブロック率と比較し（Ｓ４２）、ブロック率が低下した場合は、逆方向に微小な値−Δを半分にした値−Δ／２だけ変化させた後の値（α−（Δ／２））を新たな重み係数とする（Ｓ４６）第四のステップを実行し、この新たな重み係数（α＋（Δ／２））または（α−（Δ／２））を当初の重み係数αと置き替えることにより前記第三および第四のステップをブロック率が閾値以下となるまで（Ｓ４４）繰り返し実行する（請求項４）。
【００４２】
前記第三および第四のステップを実行した結果としてブロック率の低下がみられないときには、順次前記微小な値をさらに半分ずつ小さくして（Ｓ４５）前記第三および第四のステップを繰り返し実行する（請求項５）。
【００４３】
すなわち、第四のステップを実行した際に、ステップＳ４３でブロック率が低下しなかった場合には、ステップＳ４５に示すように、ステップＳ３２で、重み係数αを＋Δ／４だけ変化させる。さらに、ステップＳ３７で、ブロック率が低下しなかった場合には、ステップＳ３８で、重み係数をα−Δ／４だけ変化させる。それでもまだブロック率が増加する場合には、以降、微小な値をさらに±Δ／８、±Δ／１６、±Δ／３２、…と順次半分にしていく。
【００４４】
図５は本実施例のノードのブロック構成図である。本実施例は、図１に示すように、複数の異なるレイヤのネットワークが階層化されて構成されるマルチレイヤネットワークで、図５に示すように、自ノードから着ノードまでのパスが経由するレイヤおよびノードの最短経路を選択する最短経路選択部１を備えたノードである。
【００４５】
ここで、本実施例の特徴とするところは、最短経路選択部１は、各レイヤのネットワークでそれぞれのトポロジに基づき前記経路を仮想的に設定した仮想グラフを作成する仮想グラフ作成部２を備え、この仮想グラフ作成部２は、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が一つのレイヤにのみ存在する場合は、このレイヤの線分を用い、複数レイヤに存在する場合は、この中からコストが最小のものを選択する最小コスト選択部４を備える（請求項６）。
【００４６】
この最小コスト選択部４は、各レイヤ毎に重み係数を乗じた後、各レイヤの仮想グラフを構成する線分のうち、同一点間を結ぶ線分が複数レイヤに存在する場合は、この中からコストが最小のものを選択する手段を備える（請求項７）。
【００４７】
前記重み係数を決定する重み付け演算部５を備え、この重み付け演算部５は、仮想グラフ作成情報格納部３に保持されたトポロジ情報およびコスト情報に基づきステップＳ１１〜Ｓ４６を実行する手段を備える（請求項８、９、１０）。
【００４８】
本実施例のマルチレイヤネットワークは、図１に示すように、本実施例のノードを備えたことを特徴とする（請求項１１）。
【００４９】
本実施例は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本実施例のノードに相応する機能を実現させるプログラムとして実現することができる（請求項１２、１３、１４、１５、１６）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項１７）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、最短経路選択部１、仮想グラフ作成部２、仮想グラフ作成情報格納部３、最小コスト選択部４、重み付け演算部５にそれぞれ相応する機能を実現させることができる。
【００５０】
また、本実施例では、図５はノードのブロック構成として説明したが、ノードとは別途に設けられた経路選択装置のブロック構成であっても同様に説明することができる。
【００５１】
また、情報処理装置に本実施例のプログラムをインストールすることにより、当該情報処理装置を本実施例のノードに相応する機能を有する装置とすることができると共に、情報処理装置に本実施例のプログラムをインストールすることにより、当該情報処理装置をノードとは別途に設けられた経路選択装置に相応する機能を有する装置とすることもできる。
【００５２】
以下では、本発明実施例をさらに詳細に説明する。
【００５３】
（第一実施例）
図１にマルチレイヤネットワークの例を示す。この例では、マルチレイヤネットワークはファイバネットワーク、波長ネットワーク、パケットネットワークからなる。それぞれのレイヤのネットワークにおいて、ノード間を結ぶ線もしくは点線はパスであり、上位レイヤからみるとこのパスはリンクとして認識される。
【００５４】
すなわち、ファイバレイヤのパスである直線は、波長レイヤからみるとリンクとして認識され、また、波長レイヤの曲線は、波長パスを示すと同時に、パケットレイヤからみると、リンクとしてみなされる。マルチレイヤネットワークではこのような階層ネットワークの特徴を持つ。
【００５５】
このようなマルチレイヤネットワークにおいて、ノードＣからノードＥまでパケットのパスを設定する場合には、このノード間は波長のパスで接続されている必要があると共に、このノード間が波長のパスで接続されるためにはファイバのパスで接続されている必要がある。
【００５６】
このとき、パケットパスを設定するために、どの経路で波長のパスを設定するのがよいか、または、既存の波長パスを利用するのがいいか、などの問題を解く必要がある。
【００５７】
本発明では、この経路計算を行う際に仮想グラフを用いる。この仮想グラフの作成方法を以下に述べる。まず、ファイバレイヤのネットワークのグラフを仮想グラフとする。次に波長レイヤのトポロジを構成する波長パスを一つずつ仮想グラフにコピーするが、このとき、既にあるファイバパス由来の仮想リンクのメトリックよりも小さい値を持つ場合は、この波長パスで上書きする。
【００５８】
例えば、ノードＡとノードＨとの間のファイバパスのメトリックの値が１０であるとする。このとき、仮想グラフのトポロジでＡ−Ｈ間はメトリック１０のリンクで接続されていることになる。もし、Ａ−Ｈ間に波長パスが設定されているとき、この波長パスのメトリックが１０より大きい場合は、現在のファイバパス由来の値がそのまま仮想リンクのメトリックとして保持される。もし、波長パスのメトリックが１０よりも小さい場合（例えば５）には、波長パスによって仮想トポロジのリンクが上書きされて、Ａ−Ｈ間のリンクのメトリックは５となる。これを全てのパスを対象に行い、仮想トポロジのグラフを作成する。
【００５９】
このようにして作成された仮想トポロジのグラフを用いて最短経路を求める。このとき、最短経路上の仮想リンクが、波長パス由来のものである場合には、これは、既存の波長パスを利用したということになるため、設定するパケットパスは、該当する波長パスを経由する。もし、最短経路上の仮想リンクがファイバパス由来のものである場合には、これは、既存のファイバパスを用いて波長パスを新設し、この新設した波長パスを経由してパケットパスを設定することになる。このときは該当するファイバパスの経路上に波長パスを設定した後に、パケットパスを設定することになる（請求項１、６）。
【００６０】
（第二実施例）
第二実施例を図６を参照して説明する。図６はレイヤ毎の重み係数を示す図である。第一実施例で示したフローにしたがって、仮想トポロジのグラフを作成する上で、二つのノード間に異なる種類もしくは同一種類の複数のパスのメトリックを比較するケースがある。このときに、図６に示すとおり、ファイバトポロジのパスのメトリックには１倍率をかけるのに対し、波長トポロジのパスのメトリックにはα倍率をかけることにより、レイヤ毎に重み付けを行うことができる。
【００６１】
このようにすることにより、トライアンドエラーでαの値を変更することで、よりトラヒックを収容可能になるαを見付けることができる（請求項２、７）。
【００６２】
（第三実施例）
第二実施例では、第一実施例よりもさらに効率的なトラヒック収容が可能になるが、ネットワークのオペレータは運用過程で最適なαを見付けて設定する必要がある。この運用上の煩雑さを省略するために、第三実施例を提案する。
【００６３】
これは、あらかじめ設定されているαの値を用いて、一度はネットワークを運用する。一定時間（一定回数のパスの設定または開放）経過したら、この間のパスの設定の失敗確率（ブロック率）を保持しておく。その後、αの値を変化させて、再度一定時間経過の後、新しく計算したブロック率と以前の確率とを比較する。新しいブロック率の方が小さい場合は、新しいαを採用すると共に、再度、αを変化させる。もし、以前のブロック率の方が小さい場合は、最初のαの変化と逆方向へαを変化させる。これをαの変化の幅を徐々に小さくしていくことによって、あるαの値に収束していくとき、最終的なαの値を確定することとする（請求項３、４、５、８、９、１０）。
【００６４】
トラヒックは流動的なため、１ヶ月に一度、１週間に一度といった、ある期間でこれを定期的に繰り返すことにより、恒常的に効率的なネットワーク利用が可能となる。
【産業上の利用可能性】
【００６５】
本発明によれば、マルチレイヤネットワークにおいて、ネットワーク構成、ノード構成の如何を問わず、ネットワークリソースを有効利用することができるので、ネットワークのユーザおよび管理者の双方にとって、ネットワークの効率的運用に寄与することができる。
【図面の簡単な説明】
【００６６】
【図１】本実施例のマルチレイヤネットワークの例を示す図。
【図２】本実施例の仮想グラフ作成手順を示すフローチャート。
【図３】本実施例の重み係数決定手順を示すフローチャート。
【図４】本実施例の重み係数収束手順を示すフローチャート。
【図５】本実施例のノードのブロック構成図。
【図６】本実施例のレイヤ毎の重み係数を示す図である。
【符号の説明】
【００６７】
１  最短経路選択部
２  仮想グラフ作成部
３  仮想グラフ作成情報格納部
４  最小コスト選択部
５  重み付け演算部
【図１】
2005341292.tif 000003
【図２】
2005341292.tif 000004
【図３】
2005341292.tif 000005
【図４】
2005341292.tif 000006
【図５】
2005341292.tif 000007
【図６】
2005341292.tif 000008