(57)【要約】【課題】起点ノードから中継ノードまたは終点ノードまでの距離が同一の場合に、リンクの使用状況に応じて経路を選択し、効率よくネットワークリソースを使用する。【解決手段】起点ノードからあるノードまでの距離が同一の場合に、当該ノードまでの経路上の距離以外の要因によりノードを選択する。つまり、距離を第一の指標として経路選択に用い、距離が同一の場合は、第二指標として、例えば、リンクの負荷を用いる。第二指標として、リンク負荷の代わりに、リンク遅延や使用帯域を用いてもよい。【選択図】　図１
2004007201.tif 000002
【特許請求の範囲】
【請求項１】
各リンクに最短経路探索の際の経路選択指標となる第一指標および第二指標を設け、
この第一指標は、ダイクストラ法に基づき最短経路を計算した結果求められた距離であり、
起点ノードから終点ノードまでの最短経路をダイクストラ法に基づき計算し、当該最短経路の途中のダイクストラ法によって最短経路を探索する過程で評価される経由ノードで、同一の第一指標を有する複数の経路がある場合には、第二指標に基づき、いずれか一方の経路を選択することを特徴とする経路選択方法。
【請求項２】
第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の和が最小になる経路を選択する請求項１記載の経路選択方法。
【請求項３】
第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の最大値が最小になる経路を選択する請求項１記載の経路選択方法。
【請求項４】
第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の最大値が同一の経路が複数あるときには、当該最大値と比較して二番目に大きい値を第二最大値と定義し、この第二最大値が最小となる経路を選択し、同様に、起点ノードから経由ノードまでの第二指標の第ｋ最大値が同一の経路が複数あるときには、第ｋ＋１最大値が最小となる経路を選択する請求項３記載の経路選択方法。
【請求項５】
第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の和が最大になる経路を選択する請求項１記載の経路選択方法。
【請求項６】
第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の最小値が最大になる経路を選択する請求項１記載の経路選択方法。
【請求項７】
第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の最小値が同一の経路が複数あるときには、当該最小値と比較して二番目に小さい値を第二最小値と定義し、この第二最小値が最大となる経路を選択し、同様に、起点ノードから経由ノードまでの第二指標の第ｋ最小値が同一の経路が複数あるときには、第ｋ＋１最小値が最大となる経路を選択する請求項６記載の経路選択方法。
【請求項８】
第二指標は、リンクの負荷である請求項１ないし７のいずれかに記載の経路選択方法。
【請求項９】
前記リンクの負荷は、使用帯域をリンク帯域で除した値で示される請求項８記載の経路選択方法。
【請求項１０】
前記リンクの負荷は、未使用帯域の逆数で示される請求項８記載の経路選択方法。
【請求項１１】
第二指標は、リンクの使用帯域である請求項１ないし７のいずれかに記載の経路選択方法。
【請求項１２】
第二指標は、リンクを通過する遅延時間である請求項１ないし７のいずれかに記載の経路選択方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、リンクの使用状況に応じて、最短経路の中で、リンクの使用状況に応じた経路を計算する方法を提供するものである。
【０００２】
【従来の技術】
ネットワークモデルを図６示す。各リンクには、リンクコストが与えられている。ノード１を起点として、起点ノードから各ノードへ最短経路を求めることを考える。最短経路とは、経由するリンクコストが最小となる経路である。最短経路を求める方法として、ダイクストラ（Ｄｉｊｋｓｔｒａ）法がある。
【０００３】
ダイクストラ法では、最短経路を求める計算の途中の段階でノードを３種に分類する。
【０００４】
Ａ：起点ノードから最短経路が見つかったときのノードの集合
Ｂ：集合Ａに加えられる候補となるノードの集合で、集合Ａ内の一つのノードから出るリンクの終点となっている。
【０００５】
Ｃ：残りのノードの集合。
【０００６】
図７に従来の最短経路計算例（その１）を示す。最初は、全てのノードをＣと仮定し、デフォルト値として、起点ノード１からの距離を９９９、前ノード番号を０としておく、ステップ１において、起点ノードＡからリンクされたノード２、４、５が候補としてＢになる。起点ノード２、４、５への距離は、それぞれ２、４、９であり、前ノード番号は、全て１である。
【０００７】
ステップ２において、Ｂのノードの中で起点ノードＡから距離（コスト）が最も短い（小さい）ノード２がＡにランクアップし、このノード２からつながっているノード３をＣからＢにする。ノード４は、既にＢになっており、起点からノード４の距離は４であり、ノード２を経由すると距離は８になるので、起点からノード４の距離は、４のままとなる。
【０００８】
ステップ３において、Ｂのノードの中で起点ノードＡから距離が最も短いノード４がＡにランクアップし、このノード４からつながっているノードをＣからＢにするが、既にノード５はステップ１でＢになっている。ただし、起点ノード１からノード５の経路は、ノード４の経路を経由した方が距離が短いので、ノード５の前ノードは、ノード４となり、距離は４＋４＝８に変更される。このように、Ｂの中から最短距離のノードをＡにして、それにつながるノードをＢにする手順を繰り返す。したがって、各計算ステップでノード一つがＢからＡにランクアップするので、７ノードのネットワークは、ステップ７でＢの状態のノードがなくなり、計算が終了する。図７に示した従来の最短経路計算により、得られた起点ノード１からの最短経路を図８に示す。
【０００９】
次に、図９に示すネットワークの場合を考える。各リンクのコストは、全て１で与えられている。起点ノードをノード１とする。ステップ１において、ノード１はＡ、ノード２、４はＢとなる。起点ノード１からノード２、４への距離は１である。ステップ２において、起点ノード１からノード２、４への距離が両方とも１なので、いずもか１つのノードをＡにランクアップさせる。ＢからＡへランクアップさせる場合には、距離が同じとなるノードが複数ある場合は、例えば、ノード番号の一番小さいノードを選択する。ステップ２では、ノード２を選択し、Ａには、ノード１、ノード２、Ｂには、ノード５、ノード３になる。ステップ３では、ノード４がＢからＡへランクアップされ、Ｂには、ノード３、ノード５、ノード７になる。ここで、ノード５の前ノードであるが、起点ノード１からノード５には、距離が２の経路で、ノード２を経由する場合と、ノード４を経由する２つの場合がある。複数の前ノードがある場合は、例えば、ノード番号の一番小さいノードを選択する。したがって、ステップ３のノード５の前ノードは、ノード２のままである。同様のプロセスを繰り返し、図１０に示した従来の最短経路計算により、得られた起点ノード１からの最短経路を図１１に示す。
【００１０】
【発明が解決しようとする課題】
中継ノードで距離が同一の場合には、ノード番号の一番小さいノードの経路を選択すると、起点ノード１から起点ノード９の経路を選択するとき、必ず１−２−３−６−９になる。
【００１１】
これに対し、ノード１からノード９までの距離が４の経路は、図６のネットワークモデルでは、１−２−３−６−９、１−２−５−６−９、１−２−５−８−９、１−４−５−６−９、１−４−５−８−９、１−４−７−８−９の６通りある。しかし、従来の方法にしたがうと、唯一の経路１−２−３−６−９を偏って選択してしまい、ボトルネックとなるリンクが生じるという問題がある。
【００１２】
本発明は、このような背景に行われたものであって、起点ノードから中継ノードまたは終点ノードまでの距離が同一の場合に、リンクの使用状況に応じて経路を選択し、効率よくネットワークリソースが使用できる経路選択方法を提供することを目的とする。
【００１３】
【課題を解決するための手段】
本発明は、起点ノードからあるノードまでの距離が同一の場合に、当該ノードまでの経路上の距離以外の要因によりノードを選択する。つまり、距離を第一の指標として経路選択に用い、距離が同一の場合は、第二指標として、例えば、リンクの負荷を用いるところに特徴がある。第二指標として、リンク負荷の代わりに、リンク遅延や使用帯域を用いてもよい。
【００１４】
すなわち、本発明は、経路選択方法であって、本発明の特徴とするところは、各リンクに最短経路探索の際の経路選択指標となる第一指標および第二指標を設け、この第一指標は、ダイクストラ法に基づき最短経路を計算した結果求められた距離であり、起点ノードから終点ノードまでの最短経路をダイクストラ法に基づき計算し、当該最短経路の途中のダイクストラ法によって最短経路を探索する過程で評価される経由ノードで、同一の第一指標を有する複数の経路がある場合には、第二指標に基づき、いずれか一方の経路を選択するところにある。
【００１５】
第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の和が最小になる経路を選択することができる。あるいは、第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の最大値が最小になる経路を選択することもできる。これにより、ネットワークリソースを最も有効利用できる経路を選択することができる。
【００１６】
また、第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の最大値が同一の経路が複数あるときには、当該最大値と比較して二番目に大きい値を第二最大値と定義し、この第二最大値が最小となる経路を選択し、同様に、起点ノードから経由ノードまでの第二指標の第ｋ最大値が同一の経路が複数あるときには、第ｋ＋１最大値が最小となる経路を選択することが望ましい。
【００１７】
または、第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の和が最大になる経路を選択することもできる。あるいは、第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の最小値が最大になる経路を選択することもできる。
【００１８】
これにより、ネットワークリソースの消費がなるべく大きな経路を積極的に選択することにより、ネットワークリソースの消費が少ない経路をなるべく温存するようにすることができる。このように、第二指標の定義を変えることにより、経路選択ポリシを任意に定めることができる。
【００１９】
第二指標に基づき、いずれか一方の経路を選択する際に、起点ノードから経由ノードまでの第二指標の最小値が同一の経路が複数あるときには、当該最小値と比較して二番目に小さい値を第二最小値と定義し、この第二最小値が最大となる経路を選択し、同様に、起点ノードから経由ノードまでの第二指標の第ｋ最小値が同一の経路が複数あるときには、第ｋ＋１最小値が最大となる経路を選択することが望ましい。
【００２０】
既に説明したように、第二指標は、例えば、リンクの負荷であり、前記リンクの負荷は、例えば、使用帯域をリンク帯域で除した値で示される。あるいは、未使用帯域の逆数で示される。
【００２１】
また、第二指標は、リンクの使用帯域であったり、あるいは、第二指標は、リンクを通過する遅延時間であることができる。
【００２２】
【発明の実施の形態】
（第一実施例）
第一実施例のネットワークモデルを図１に示す。第一指標であるリンクコスト（図１（ａ））と、第二指標であるリンク負荷（図１（ｂ））が与えられている。リンク負荷は、例えば、リンクに対して、使用帯域／リンク帯域で与えてもよい。または、１／未使用帯域で与えてもよい。
【００２３】
図２に、第一実施例の最短経路計算の例を示す。起点ノードをノード１とする。ステップ１において、ノード１はＡ、ノード２、４はＢとなる。起点ノード１からノード２、４への距離は１である。ステップ２において、起点ノード１からノード２、４への距離が両方とも１なので、いずれか１つのノードをＡにランクアップさせる。ＢからＡへランクアップさせる場合には、距離が同じとなるノードが複数ある場合は、例えば、ノード番号の一番小さいノードを選択する。
【００２４】
ステップ２では、ノード２を選択し、Ａには、ノード１、２、Ｂには、ノード５、ノード３になる。ステップ３では、ノード４がＢからＡへランクアップされ、Ｂには、ノード３、ノード５、ノード７になる。ここで、ノード５の前ノードであるが、起点ノード１からノード５には、距離が２の経路で、ノード２を経由する場合と、ノード４を経由する２つの場合がある。第一実施例では、距離が同一で、複数の前ノードがある場合は、起点ノードから当該ノードまでの、リンクの負荷の和が最小となるノードを前ノードとする。ステップ３では、ノード５において、１−２−５の距離は２であり、負荷の和が０．６、一方、１−４−５の距離は２であり、負荷の和が０．５であるので、前ノードを４とする。同様のプロセスを繰り返し、図２に示した第一実施例の最短経路計算により、得られた起点ノード１からの最短経路を図３（ａ）および（ｂ）に示す。第二指標として、リンク負荷の代わりに、リンク遅延や使用帯域を用いてもよい。
【００２５】
このように、距離が同一で、複数の前ノードがある場合は、起点ノードから当該ノードまでのリンクの負荷の和が最小となるノードを前ノードとすることにより、リンクの状態により、最短経路を適応的に選択してネットワークのリソースを効率よく使うことができる。
【００２６】
（第二実施例）
第二実施例では、距離が同一で、複数の前ノードがある場合は、起点ノードから当該ノードまでの経路上の負荷の最大値が最小になるような前ノードを選択する。図４に第二実施例の最短経路計算例を示す。図４に示した従来の最短経路計算により、得られた起点ノード１からの最短経路を図５（ａ）および（ｂ）に示す。
【００２７】
図５において、起点ノード１からノード５までに、１−２−５、１−４−５の経路がある。この場合には、それぞれの経路上のリンクの最大値は、０．３、０．４であるので、リンクの最大値が最小である１−２−５を選択する。
【００２８】
第二実施例では、複数の経路上のリンクの最大値も同一の場合は、経路上のリンクの第二最大値を比較して、第二最大値が最小の経路を選択している。例えば、起点ノード１からノード８までの経路を選択する際、ステップ８において、ノード８の前ノードの候補として、ノード５とノード７とを比較した場合に、経路上のリンクの最大値が０．４と同一であるため、第二最大値０．１と０．２とを比較して、前ノードとして、ノード７を選択している。第二指標として、リンクの負荷の代わりに、リンク遅延や使用帯域を用いてもよい。
【００２９】
このように、距離が同一で、複数の前ノードがある場合は、起点ノードから当該ノードまでの、リンクの負荷の最大値が最小となるノードを前ノードとすることにより、リンクの状態により、最短経路を適応的に選択して、ネットワークのリソースを効率よく使うことができる。
【００３０】
（第三実施例）
第一および第二実施例では、リンクの負荷がなるべく小さくなるようなポリシに基づいて経路を選択していた。また、別のポリシとして、帯域が大きい通信の要求に備えて、帯域の大きい経路を確保するために、残りの帯域が少ないリンクから積極的に使い、帯域の余っているリンクをなるべく使わないポリシもある。第三実施例では、第一実施例とは逆となり、距離が同一で、複数の前ノードがある場合は、起点ノードから当該ノードまでの、リンクの負荷の和が最大となるノードを前ノードとする。第二指標として、リンク負荷の代わりに、リンク遅延や使用帯域を用いてもよい。
【００３１】
（第四実施例）
第三実施例では、第二実施例とは逆となり、距離が同一で、複数の前ノードがある場合は、起点ノードから当該ノードまでの、リンクの負荷の最小値が最大となるノードを前ノードとする。第二指標として、リンク負荷の代わりに、リンク遅延や使用帯域を用いてもよい。
【００３２】
【発明の効果】
以上説明したように、本発明によれば、起点ノードから中継ノードまたは終点ノードまでの距離が同一の場合には、リンクの使用状況に応じて、経路を選択し、効率よくネットワークリソースを使用することができる。
【図面の簡単な説明】
【図１】第一実施例のネットワークモデルを示す図。
【図２】第一実施例の最短経路計算を示す図。
【図３】第一実施例の最短経路計算方法による最短経路を示す図。
【図４】第二実施例の最短経路計算を示す図。
【図５】第二実施例の最短経路計算方法による最短経路を示す図。
【図６】ネットワークモデル（その１）を示す図。
【図７】従来の最短経路計算例（その１）を示す図。
【図８】従来の最短経路計算方法による最短経路（その１）を示す図。
【図９】ネットワークモデル（その２）を示す図。
【図１０】従来の最短経路計算例（その２）を示す図。
【図１１】従来の最短経路計算方法による最短経路（その２）を示す図。
【符号の説明】
１〜９　ノード
【図１】
2004007201.tif 000003
【図２】
2004007201.tif 000004
【図３】
2004007201.tif 000005
【図４】
2004007201.tif 000006
【図５】
2004007201.tif 000007
【図６】
2004007201.tif 000008
【図７】
2004007201.tif 000009
【図８】
2004007201.tif 000010
【図９】
2004007201.tif 000011
【図１０】
2004007201.tif 000012
【図１１】
2004007201.tif 000013