(57)【要約】【課題】マルチレイヤネットワークにおける経路計算を大規模ネットワークへ拡張する。無効となる計算を無くし経路計算を効率良く行う。【解決手段】自己が属するネットワークは、複数のノードで構成されるセルに分割され、このセルは仮想ノードと定義され、仮想ノードの内部と外部とを接続しているリンクが存在する場合に、この仮想ノードの内部と外部との接点は仮想ノードのインタフェースと定義され、仮想ノードで構成された仮想ネットワークはさらにセル分割、仮想ノード化され、当該さらにセル分割、仮想ノード化された仮想ネットワークは当初の仮想ネットワークに対する上位レベルのネットワークと定義され、上記セル分割、仮想ノード化の操作を１回もしくは複数回行うことにより階層化ネットワークが構築され、発ノードから着ノードまでの経路計算をレイヤ毎に分散して段階的に行う。【選択図】　図１
2004129135.tif 000002
【特許請求の範囲】
【請求項１】
一つもしくは複数のレイヤからなるネットワークに設けられ、自ノードおよび自ノードに接続されているリンクの情報（以降、リンクステート情報と呼ぶ）を他ノードとの間で相互に交換する手段と、
この交換する手段により得られた前記ネットワーク中の一部もしくは全部のノードのリンクステート情報を保持する手段と、
パス設定要求にしたがってこの保持する手段に保持されたリンクステート情報に基づきひとつもしくは複数種類のレイヤのパスの経路を選択する手段と、
パス変更要求にしたがってこの選択する手段により選択されて設定された経路を前記保持する手段に保持されたリンクステート情報に基づき変更する手段と
を備えたノードにおいて、
自己が属するネットワークは、複数のノードで構成されるセルに分割され、このセルは仮想ノードと定義され、仮想ノードの内部と外部とを接続しているリンクが存在する場合に、この仮想ノードの内部と外部との接点は仮想ノードのインタフェースと定義され、仮想ノードで構成された仮想ネットワークはさらにセル分割、仮想ノード化され、当該さらにセル分割、仮想ノード化された仮想ネットワークは当初の仮想ネットワークに対する上位レベルのネットワークと定義され、上記セル分割、仮想ノード化の操作を１回もしくは複数回行うことにより階層化ネットワークが構築され、
自己が属する仮想ノード内の他ノードもしくは他仮想ノードから広告されるリンクステート情報を蓄積するリンクステートデータベースを備え、
仮想ノード内のノードもしくは仮想ノードのうち仮想ノード外部とのインタフェースの役割を果たしているノードをボーダノードと定義し、
自己がこのボーダノードに位置するときには仮想ノード内部のリンクステート情報をもとに仮想ノード外部に対するインタフェース情報を生成する手段を備えたリンクステート要約部と、
生成した当該インタフェース情報を仮想ノード外部に対して広告する広告部と
を備えたことを特徴とする階層化ネットワークノード。
【請求項２】
仮想ノード相互間を接続する複数のリンクの中で同一仮想ノード対地間を接続するリンク群を識別する手段と、
この識別する手段により識別されたリンク群に含まれるリンクをひとつの仮想リンクとみなして処理する手段と
を備えた請求項１記載の階層化ネットワークノード。
【請求項３】
仮想ノード相互間を接続する複数のリンクの中で同一仮想ノード対地間を接続する第一のリンク群を識別する手段と、
この識別する手段により識別された第一のリンク群をさらに同一のスイッチングケーパビリティを共有する第二のリンク群に分類する手段と、
この分類する手段による分類された第二のリンク群に含まれるリンクをひとつの仮想リンクとみなして処理する手段と
を備えた請求項１記載の階層化ネットワークノード。
【請求項４】
前記リンクステート要約部は、自ノードが属する仮想ノード内のスイッチングケーパビリティを自ノードに接続されているリンクでかつ自ノードが属する仮想ノードと外部とを接続しているインタフェースに対応するリンクに割当てを行うスイッチングケーパビリティ割当手段を備え、
前記インタフェース情報は、前記スイッチングケーパビリティ割当手段により前記インタフェースに割当てられたスイッチングケーパビリティの情報である
請求項１記載の階層化ネットワークノード。
【請求項５】
前記リンクステート要約部は、
自ノードが属する仮想ノード内のスイッチングケーパビリティを自ノードに接続されているリンクでかつ自ノードが属する仮想ノードと外部とを接続しているインタフェースに対応するリンクに割当てを行うスイッチングケーパビリティ割当手段と、
このスイッチングケーパビリティ割当手段により割当てられたスイッチングケーパビリティ毎に伝送コストを割当てるコスト割当手段と
を備え、
前記インタフェース情報は、前記スイッチングケーパビリティ割当手段により前記インタフェースに割当てられたスイッチングケーパビリティの情報および前記コスト割当手段により前記インタフェースのスイッチングケーパビリティに対して割当てられた伝送コストの情報である
請求項１記載の階層化ネットワークノード。
【請求項６】
前記インタフェースに割当てられたスイッチングケーパビリティの情報は、ボーダノードもしくは仮想ボーダノードとしての自ノードと同一仮想ノード内に属する他ボーダノードもしくは他仮想ボーダノードとの間に設定することができるパスのレイヤにそれぞれ対応して生成される請求項４または５記載の階層化ネットワークノード。
【請求項７】
前記インタフェースに割当てられたスイッチングケーパビリティの情報は、前記インタフェースとなっているリンクが直接接続されているボーダノードもしくは仮想ボーダノードのスイッチングケーパビリティに関する情報である請求項４または５記載の階層化ネットワークノード。
【請求項８】
前記広告部は、前記ボーダノードにおけるスイッチングケーパビリティに変化が生じる毎に仮想ノード外部に広告を行う手段を備えた請求項１記載の階層化ネットワークノード。
【請求項９】
前記広告部は、一定周期で仮想ノード外部に広告を行う手段を備えた請求項１記載の階層化ネットワークノード。
【請求項１０】
前記伝送コストの情報は、仮想ノード内に含まれる当該レイヤのスイッチングケーパビリティが割当てられている未使用インタフェース総数の逆数により生成される請求項５記載の階層化ネットワークノード。
【請求項１１】
前記伝送コストの情報は、仮想ノード内に含まれる当該レイヤのスイッチングケーパビリティが割当てられている使用インタフェース数および総インタフェース数に関して
使用インタフェース数／総インタフェース数
により生成される請求項５記載の階層化ネットワークノード。
【請求項１２】
前記伝送コストの情報は、仮想ノード内のボーダノードと当該ボーダノードと同一仮想ノード内に属する他ボーダノードとの間に、任意のレイヤのパスを設定する際のコストとして、設定されるパスのレイヤ毎に決定される情報である請求項５記載の階層化ネットワークノード。
【請求項１３】
前記コストは、仮想ノード内のボーダノードと当該ボーダノードと同一仮想ノード内に属する他ボーダノードとの間にパスを設定する際の経路に沿って、リンクのリンクコストと、ノードもしくは仮想ノードのノードコストとを足し合わせることで得られる値が最も小さくなる経路のコスト値を算出する手段を備えた
請求項１２記載の階層化ネットワークノード。
【請求項１４】
前記コストは、仮想ノード内のボーダノードと当該ボーダノードと同一仮想ノード内に属する他ボーダノードとの間に設定する最小ホップ数の経路に沿って、リンクのリンクコストと、ノードもしくは仮想ノードのノードコストとを足し合わせることで得られる値であり、
前記最小ホップ数の経路が複数ある場合には、複数の当該足し合わせることで得られる値の集合であるコスト値候補の中からその値が最も小さくなるものをコスト値として選択する手段を備えた
請求項１２記載の階層化ネットワークノード。
【請求項１５】
前記足し合わせることで得られる値は、前記経路に沿ってノード内に含まれる当該レイヤのスイッチングケーパビリティが割当てられている未使用インタフェース数の逆数である請求項１３または１４記載の階層化ネットワークノード。
【請求項１６】
前記足し合わせることで得られる値は、前記経路に沿ってノード内に含まれる当該レイヤのスイッチングケーパビリティが割当てられている使用インタフェース数および総インタフェース数に関して
使用インタフェース数／総インタフェース数
で与えられる請求項１３または１４記載の階層化ネットワークノード。
【請求項１７】
仮想ノードのインタフェースに相当するノードは、あらかじめ決められた時間間隔で前記伝送コストの情報または前記コストを前記リンクステート情報に基づき計算する手段を備えた請求項５、１２ないし１６のいずれかに記載の階層化ネットワークノード。
【請求項１８】
仮想ノードのインタフェースに相当するノードは、仮想ノード内部のインタフェースの使用状況の変化をリンクステート情報の広告によって通知され、インタフェースの使用状況が変化するたびに前記伝送コストの情報または前記コストを前記リンクステート情報に基づき計算する手段を備えた請求項５、１２ないし１６のいずれかに記載の階層化ネットワークノード。
【請求項１９】
請求項１ないし１８のいずれかに記載の階層化ネットワークノードを備えたことを特徴とするネットワーク。
【請求項２０】
請求項１記載の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するときに、
発ノードから着ノードまでの経路を選択する際に、最下位のレベル１の前記リンクステートデータベースを参照することによって、当該レベル１の仮想ノードの中で、発ノードを含む仮想ノード中に着ノードが存在するかを判断し、
発ノードと着ノードが同一仮想ノード内に存在しない場合は、ひとつ上位のレベル２の前記リンクステートデータベースを参照することによって当該レベル２の発ノードを含む仮想ノード中に着ノードが存在するかを判断し、
この判断を発ノードと着ノードとが同一仮想ノード中に含まれるまで繰り返すことで、発ノードと着ノードとの両者を含むレベルＮ（Ｎは自然数）の仮想ノードを選択し、
この選択されたレベルＮの仮想ノード中で発ノードから着ノードまでのレベルＮの経路を選択する際に、当該選択されたレベルＮの仮想ノード内に含まれる仮想ノード群の経路選択を当該レベルＮの前記リンクステートデータベースを基にして、当該レベルＮの前記選択する手段により選択し、
この選択されたレベルＮの経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−１）の前記選択する手段により選択し、これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行することを特徴とする階層化経路選択方法。
【請求項２１】
請求項１記載の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するとき、
発ノードから着ノードまでの経路を選択する際に、最上位レベルＮの仮想ノードからなるネットワークで、当該レベルＮの前記リンクステートデータベースを参照することで、発ノード、着ノードが同一仮想ノード内に存在するか否かを判断し、
発ノードと着ノードとが同一仮想ノード内に存在する場合は、この仮想ノード内のひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを参照することによって、この仮想ノード内のひとつ下位のレベル（Ｎ−１）のネットワークで発ノードと着ノードとが同一仮想ノード内に存在するか否かを判断し、
この判断を発ノードと着ノードとが異なる仮想ノード中に含まれるまで繰り返し、そのひとつ上位レベル（Ｎ−ｋ）（ｋは自然数）の仮想ノードを選択することで、発ノードと着ノードとの両者を含むレベル（Ｎ−ｋ）の仮想ノードを選択し、
この仮想ノード中で発ノードから着ノードまでのレベル（Ｎ−ｋ）の経路を選択する際に、当該選択されたレベル（Ｎ−ｋ）の仮想ノード内に含まれる仮想ノード群の経路選択を当該レベル（Ｎ−ｋ）の前記リンクステートデータベースを基にして、当該レベル（Ｎ−ｋ）の前記選択する手段により選択し、
この選択されたレベル（Ｎ−ｋ）の経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−ｋ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−ｋ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−ｋ−１）の前記選択する手段により選択し、
これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行することを特徴とする階層化経路選択方法。
【請求項２２】
前記発ノードと着ノードとの両者を含むレベルよりも下位のレベルの仮想ノードでは、自ノード内の経路を選択する計算を、その仮想ノード中に含まれるボーダノードのうち、当該経路の入出力インタフェースとして割当てられているボーダノードが行う請求項２０または２１記載の階層化経路選択方法。
【請求項２３】
前記発ノードと着ノードとの両者を含むレベルよりも下位のレベルの仮想ノードでは、自ノード内の経路を選択する計算を、その仮想ノード中に含まれるボーダノードのうち、あらかじめ代表ノードとして定められているボーダノードが行う請求項２０または２１記載の階層化経路選択方法。
【請求項２４】
情報処理装置にインストールすることにより、その情報処理装置に、請求項１記載の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するときに、
発ノードから着ノードまでの経路を選択する際に、最下位のレベル１の前記リンクステートデータベースを参照することによって、当該レベル１の仮想ノードの中で、発ノードを含む仮想ノード中に着ノードが存在するかを判断し、
発ノードと着ノードが同一仮想ノード内に存在しない場合は、ひとつ上位のレベル２の前記リンクステートデータベースを参照することによって当該レベル２の発ノードを含む仮想ノード中に着ノードが存在するかを判断し、
この判断を発ノードと着ノードとが同一仮想ノード中に含まれるまで繰り返すことで、発ノードと着ノードとの両者を含むレベルＮ（Ｎは自然数）の仮想ノードを選択し、
この選択されたレベルＮの仮想ノード中で発ノードから着ノードまでのレベルＮの経路を選択する際に、当該選択されたレベルＮの仮想ノード内に含まれる仮想ノード群の経路選択を当該レベルＮの前記リンクステートデータベースを基にして、当該レベルＮの前記選択する手段により選択し、
この選択されたレベルＮの経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−１）の前記選択する手段により選択し、
これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行させることを特徴とするプログラム。
【請求項２５】
情報処理装置にインストールすることにより、その情報処理装置に、請求項１記載の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するとき、
発ノードから着ノードまでの経路を選択する際に、最上位レベルＮの仮想ノードからなるネットワークで、当該レベルＮの前記リンクステートデータベースを参照することで、発ノード、着ノードが同一仮想ノード内に存在するか否かを判断し、
発ノードと着ノードとが同一仮想ノード内に存在する場合は、この仮想ノード内のひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを参照することによって、この仮想ノード内のひとつ下位のレベル（Ｎ−１）のネットワークで発ノードと着ノードとが同一仮想ノード内に存在するか否かを判断し、
この判断を発ノードと着ノードとが異なる仮想ノード中に含まれるまで繰り返し、そのひとつ上位レベル（Ｎ−ｋ）（ｋは自然数）の仮想ノードを選択することで、発ノードと着ノードとの両者を含むレベル（Ｎ−ｋ）の仮想ノードを選択し、
この仮想ノード中で発ノードから着ノードまでのレベル（Ｎ−ｋ）の経路を選択する際に、当該選択されたレベル（Ｎ−ｋ）の仮想ノード内に含まれる仮想ノード群の経路選択を当該レベル（Ｎ−ｋ）の前記リンクステートデータベースを基にして、当該レベル（Ｎ−ｋ）の前記選択する手段により選択し、
この選択されたレベル（Ｎ−ｋ）の経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−ｋ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−ｋ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−ｋ−１）の前記選択する手段により選択し、
これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行させることを特徴とするプログラム。
【請求項２６】
請求項２４または２５記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パスの経路選択やリアレンジなどのトラヒックエンジニアリングを行うパスネットワークの構成技術に関する。
【０００２】
【従来の技術】
複数のレイヤのネットワークが混在している場合に、それぞれのレイヤで個別のネットワーク管理が行われている場合が多い。このときネットワーク管理方法は、レイヤによって異なり、一つの装置がネットワーク全ての状態を把握し、制御を行う集中制御方式や、リンクステートを交換することでネットワーク中の全てのノードが情報を共有しあう分散制御方式などがある。
【０００３】
また、一つのレイヤの制御に限って、ネットワークを複数のエリアに区切って、それぞれのエリアで管理する方式もある。
【０００４】
【発明が解決しようとする課題】
複数のレイヤのネットワークが混在した状況で分散制御マルチレイヤトラヒックエンジニアリングを行う場合に、従来はネットワーク全体でトラヒックエンジニアリングを行っていたため、ＯＳＰＦ（Ｏｐｅｎ　Ｓｈｏｒｔｅｓｔ　Ｐａｔｈ　Ｆｉｒｓｔ）などに代表されるルーティングプロトコルで一括して取り扱う情報量が増え、また、トラヒックエンジニアリングの計算量も莫大になるため、大規模ネットワークへの拡張の実現が難しい。
【０００５】
本発明は、このような背景に行われたものであって、大規模ネットワークへの拡張を実現することができ、さらに、経路計算を必要とするレイヤの範囲を特定してから計算を行うことができるため、無効となる計算を無くすことができ、経路計算を効率良く行うことができる階層化ネットワークノードおよびネットワークおよび階層化経路選択方法およびプログラムおよび記録媒体を提供することを目的とする。
【０００６】
【課題を解決するための手段】
本発明は、発ノードから着ノードまでの経路計算をレイヤ毎に分散して段階的に行うことを特徴とする。これにより、ネットワーク全体でトラヒックエンジニアリングを行う従来の例と比較して個々のレイヤ毎の計算量を少なく抑えることができるため、大規模ネットワークへの拡張を実現することができる。さらに、経路計算を必要とするレイヤの範囲を特定してから計算を行うことができるため、無効となる計算を無くすことができ、経路計算を効率良く行うことができる。
【０００７】
すなわち、本発明の第一の観点は、一つもしくは複数のレイヤからなるネットワークに設けられ、自ノードおよび自ノードに接続されているリンクの情報（以降、リンクステート情報と呼ぶ）を他ノードとの間で相互に交換する手段と、
この交換する手段により得られた前記ネットワーク中の一部もしくは全部のノードのリンクステート情報を保持する手段と、パス設定要求にしたがってこの保持する手段に保持されたリンクステート情報に基づきひとつもしくは複数種類のレイヤのパスの経路を選択する手段と、パス変更要求にしたがってこの選択する手段により選択されて設定された経路を前記保持する手段に保持されたリンクステート情報に基づき変更する手段とを備えたノードである。
【０００８】
ここで、本発明の特徴とするところは、自己が属するネットワークは、複数のノードで構成されるセルに分割され、このセルは仮想ノードと定義され、仮想ノードの内部と外部とを接続しているリンクが存在する場合に、この仮想ノードの内部と外部との接点は仮想ノードのインタフェースと定義され、仮想ノードで構成された仮想ネットワークはさらにセル分割、仮想ノード化され、当該さらにセル分割、仮想ノード化された仮想ネットワークは当初の仮想ネットワークに対する上位レベルのネットワークと定義され、上記セル分割、仮想ノード化の操作を１回もしくは複数回行うことにより階層化ネットワークが構築され、自己が属する仮想ノード内の他ノードもしくは他仮想ノードから広告されるリンクステート情報を蓄積するリンクステートデータベースを備え、仮想ノード内のノードもしくは仮想ノードのうち仮想ノード外部とのインタフェースの役割を果たしているノードをボーダノードと定義し、自己がこのボーダノードに位置するときには仮想ノード内部のリンクステート情報をもとに仮想ノード外部に対するインタフェース情報を生成する手段を備えたリンクステート要約部と、生成した当該インタフェース情報を仮想ノード外部に対して広告する広告部とを備えたところにある。なお、本発明のノードを階層化ネットワークノードと呼ぶことにする。
【０００９】
このような階層化された構造を定義することにより、ネットワーク全体を一括して計算対象とする必要がなく、各階層毎に計算を行うことができるため、大規模ネットワークへの拡張を実現することができる。
【００１０】
仮想ノード相互間を接続する複数のリンクの中で同一仮想ノード対地間を接続するリンク群を識別する手段と、この識別する手段により識別されたリンク群に含まれるリンクをひとつの仮想リンクとみなして処理する手段とを備えることが望ましい。
【００１１】
これにより、ひとつの仮想リンクを、例えば、波長多重化されたひとつの光パスによって構成することができる。
【００１２】
あるいは、仮想ノード相互間を接続する複数のリンクの中で同一仮想ノード対地間を接続する第一のリンク群を識別する手段と、この識別する手段により識別された第一のリンク群をさらに同一のスイッチングケーパビリティを共有する第二のリンク群に分類する手段と、この分類する手段による分類された第二のリンク群に含まれるリンクをひとつの仮想リンクとみなして処理する手段とを備えることが望ましい。
【００１３】
これにより、同一のスイッチングケーパビリティを共有するひとつの仮想リンクを定義し、スイッチングケーパビリティ単位に、例えば、波長多重されたひとつの光パスを割当てることにより、ハードウェアの使用効率を高めることができる。
【００１４】
前記リンクステート要約部は、自ノードが属する仮想ノード内のスイッチングケーパビリティを自ノードに接続されているリンクでかつ自ノードが属する仮想ノードと外部とを接続しているインタフェースに対応するリンクに割当てを行うスイッチングケーパビリティ割当手段を備え、前記インタフェース情報は、前記スイッチングケーパビリティ割当手段により前記インタフェースに割当てられたスイッチングケーパビリティの情報であることができる。
【００１５】
すなわち、どのスイッチングケーパビリティがどのリンクに割当てられているかという情報をインタフェース情報とすることにより、各仮想ノードでは、仮想ノード相互間の接続関係をスイッチングケーパビリティ単位で把握することができる。
【００１６】
あるいは、前記リンクステート要約部は、自ノードが属する仮想ノード内のスイッチングケーパビリティを自ノードに接続されているリンクでかつ自ノードが属する仮想ノードと外部とを接続しているインタフェースに対応するリンクに割当てを行うスイッチングケーパビリティ割当手段と、このスイッチングケーパビリティ割当手段により割当てられたスイッチングケーパビリティ毎に伝送コストを割当てるコスト割当手段とを備え、前記インタフェース情報は、前記スイッチングケーパビリティ割当手段により前記インタフェースに割当てられたスイッチングケーパビリティの情報および前記コスト割当手段により前記インタフェースのスイッチングケーパビリティに対して割当られた伝送コストの情報であることができる。
【００１７】
これによれば、仮想ノード相互間の接続関係とともに、リンクを利用する場合の伝送コストも把握することができるため、単に、物理的な距離が短い経路を最短経路とするのではなく、伝送コストが最小となる経路を最短経路とすることができる。
【００１８】
前記インタフェースに割当てられたスイッチングケーパビリティの情報は、ボーダノードもしくは仮想ボーダノードとしての自ノードと同一仮想ノード内に属する他ボーダノードもしくは他仮想ボーダノードとの間に設定することができるパスのレイヤにそれぞれ対応して生成されることが望ましい。
【００１９】
これにより、各レイヤ毎に情報を取得することができ、各レイヤ毎の経路計算を行う上で利便性が高い。
【００２０】
また、前記インタフェースに割当てられたスイッチングケーパビリティの情報は、例えば、前記インタフェースとなっているリンクが直接接続されているボーダノードもしくは仮想ボーダノードのスイッチングケーパビリティに関する情報である。
【００２１】
前記広告部は、前記ボーダノードにおけるスイッチングケーパビリティに変化が生じる毎に仮想ノード外部に広告を行う手段を備えたり、あるいは、前記広告部は、一定周期で仮想ノード外部に広告を行う手段を備えることが望ましい。これにより、各仮想ノードは、最新情報を得ることができる。なお、一定周期で仮想ノード外部に広告を行う方がスイッチングケーパビリティに変化が生じる毎に仮想ノード外部に広告を行う場合と比較して広告負荷は低い場合が多い。
【００２２】
前記伝送コストの情報は、例えば、仮想ノード内に含まれる当該レイヤのスイッチングケーパビリティが割当てられている未使用インタフェース総数の逆数により生成される。
【００２３】
すなわち、未使用インタフェース総数が多ければ多いほど、インタフェースの受け入れ許容量が大きくなるので伝送コストは小さくなる。
【００２４】
あるいは、前記伝送コストの情報は、例えば、仮想ノード内に含まれる当該レイヤのスイッチングケーパビリティが割当てられている使用インタフェース数および総インタフェース数に関して
使用インタフェース数／総インタフェース数
により生成される。
【００２５】
すなわち、総インタフェース数に対する使用インタフェース数が少なければ少ないほど、インタフェースの受け入れ許容量が大きくなるので伝送コストは小さくなる。
【００２６】
また、前記伝送コストの情報は、仮想ノード内のボーダノードと当該ボーダノードと同一仮想ノード内に属する他ボーダノードとの間に、任意のレイヤのパスを設定する際のコストとして、設定されるパスのレイヤ毎に決定される情報であることが望ましい。
【００２７】
これにより、各レイヤ毎に情報を取得することができ、各レイヤ毎の経路計算を行う上で利便性が高い。
【００２８】
前記コストは、例えば、仮想ノード内のボーダノードと当該ボーダノードと同一仮想ノード内に属する他ボーダノードとの間にパスを設定する際の経路に沿って、リンクのリンクコストと、ノードもしくは仮想ノードのノードコストとを足し合わせることで得られる値が最も小さくなる経路のコスト値を算出する手段を備えることが望ましい。
【００２９】
これにより、リンクコストとノードコストとの双方を勘案して最もコストの小さくなる経路を選択することができる。
【００３０】
あるいは、前記コストは、例えば、仮想ノード内のボーダノードと当該ボーダノードと同一仮想ノード内に属する他ボーダノードとの間に設定する最小ホップ数の経路に沿って、リンクのリンクコストと、ノードもしくは仮想ノードのノードコストとを足し合わせることで得られる値であり、前記最小ホップ数の経路が複数ある場合には、複数の当該足し合わせることで得られる値の集合であるコスト値候補の中からその値が最も小さくなるものをコスト値として選択する手段を備えることが望ましい。
【００３１】
これにより、リンクコストとノードコストとの双方を勘案し、さらに、最小ホップ数により最もコストの小さくなる経路を選択することができる。
【００３２】
前記足し合わせることで得られる値は、例えば、前記経路に沿ってノード内に含まれる当該レイヤのスイッチングケーパビリティが割当てられている未使用インタフェース数の逆数である。
【００３３】
すなわち、未使用インタフェース数が多ければ多いほど、インタフェースの受け入れ許容量が大きくなるので前記足し合わせることで得られる値は小さくなる。既に説明した伝送コストと当該足し合わせることで得られる値との差異は、前記伝送コストは、リンク毎にあらかじめ定められた値であるのに対し、当該足し合わせることで得られる値は、経路に応じて算出される値である。
【００３４】
あるいは、前記足し合わせることで得られる値は、例えば、前記経路に沿ってノード内に含まれる当該レイヤのスイッチングケーパビリティが割当てられている使用インタフェース数および総インタフェース数に関して
使用インタフェース数／総インタフェース数
で与えられる。
【００３５】
すなわち、総インタフェース数に対する使用インタフェース数が少なければ少ないほど、インタフェースの受け入れ許容量が大きくなるので前記足し合わせることで得られる値は小さくなる。
【００３６】
仮想ノードのインタフェースに相当するノードは、あらかじめ決められた時間間隔で前記伝送コストの情報または前記コストを前記リンクステート情報に基づき計算する手段を備えたり、あるいは、仮想ノードのインタフェースに相当するノードは、仮想ノード内部のインタフェースの使用状況の変化をリンクステート情報の広告によって通知され、インタフェースの使用状況が変化するたびに前記伝送コストの情報または前記コストを前記リンクステート情報に基づき計算する手段を備えることが望ましい。これにより、各仮想ノードは、最新情報を得ることができる。なお、一定周期で計算を行う方がインタフェースの使用状況に変化が生じる毎に計算を行う場合と比較して計算負荷は低い場合が多い。
【００３７】
本発明の第二の観点は、本発明の階層化ネットワークノードを備えたことを特徴とするネットワークである。
【００３８】
本発明の第三の観点は階層化経路選択方法であって、本発明の特徴とするところは、本発明の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するときに、発ノードから着ノードまでの経路を選択する際に、最下位のレベル１の前記リンクステートデータベースを参照することによって、当該レベル１の仮想ノードの中で、発ノードを含む仮想ノード中に着ノードが存在するかを判断し、発ノードと着ノードが同一仮想ノード内に存在しない場合は、ひとつ上位のレベル２の前記リンクステートデータベースを参照することによって当該レベル２の発ノードを含む仮想ノード中に着ノードが存在するかを判断し、この判断を発ノードと着ノードとが同一仮想ノード中に含まれるまで繰り返すことで、発ノードと着ノードとの両者を含むレベルＮ（Ｎは自然数）の仮想ノードを選択し、この選択されたレベルＮの仮想ノード中で発ノードから着ノードまでのレベルＮの経路を選択する際に、当該選択されたレベルＮの仮想ノード内に含まれる仮想ノード群の経路選択を当該レベルＮの前記リンクステートデータベースを基にして、当該レベルＮの前記選択する手段により選択し、この選択されたレベルＮの経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−１）の前記選択する手段により選択し、これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行するところにある。
【００３９】
これによれば、まず、発ノードおよび着ノードを両方とも含むレベルを探索し、レベルの上限を特定する。これにより、これ以上の上位レベルを経路計算対象とすることなく、無効となる計算を省くことができる。このようにして探索した最上位レベルから下位レベルに向かって順次、各レベル毎に経路計算を行う。これにより、ネットワークが大規模化しても個々のレベルにおける計算量は限られているので、大規模ネットワークへの拡張を実現することができる。
【００４０】
あるいは、本発明の第三の観点は階層化経路選択方法であって、本発明の特徴とするところは、本発明の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するとき、発ノードから着ノードまでの経路を選択する際に、最上位レベルＮの仮想ノードからなるネットワークで、当該レベルＮの前記リンクステートデータベースを参照することで、発ノード、着ノードが同一仮想ノード内に存在するか否かを判断し、発ノードと着ノードとが同一仮想ノード内に存在する場合は、この仮想ノード内のひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを参照することによって、この仮想ノード内のひとつ下位のレベル（Ｎ−１）のネットワークで発ノードと着ノードとが同一仮想ノード内に存在するか否かを判断し、この判断を発ノードと着ノードとが異なる仮想ノード中に含まれるまで繰り返し、そのひとつ上位レベル（Ｎ−ｋ）（ｋは自然数）の仮想ノードを選択することで、発ノードと着ノードとの両者を含むレベル（Ｎ−ｋ）の仮想ノードを選択し、この仮想ノード中で発ノードから着ノードまでのレベル（Ｎ−ｋ）の経路を選択する際に、当該選択されたレベル（Ｎ−ｋ）の仮想ノード内に含まれる仮想ノード群の経路選択を当該レベル（Ｎ−ｋ）の前記リンクステートデータベースを基にして、当該レベル（Ｎ−ｋ）の前記選択する手段により選択し、この選択されたレベル（Ｎ−ｋ）の経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−ｋ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−ｋ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−ｋ−１）の前記選択する手段により選択し、これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行するところにある。
【００４１】
前者の方法と後者の方法とを比較すると、発ノードおよび着ノードの両方を含むレベルを探索する手順が異なる。前者の方法では下位のレベルから順に上位に向かって探索して行くが、後者の方法では上位のレベルから順に下位に向かって探索する。
【００４２】
前記発ノードと着ノードとの両者を含むレベルよりも下位のレベルの仮想ノードでは、自ノード内の経路を選択する計算を、その仮想ノード中に含まれるボーダノードのうち、当該経路の入出力インタフェースとして割当てられているボーダノードが行うものとすることができる。
【００４３】
あるいは、前記発ノードと着ノードとの両者を含むレベルよりも下位のレベルの仮想ノードでは、自ノード内の経路を選択する計算を、その仮想ノード中に含まれるボーダノードのうち、あらかじめ代表ノードとして定められているボーダノードが行うものとすることができる。
【００４４】
このようにして、あらかじめ経路計算を行うノードを決めておくことにより、計算処理を効率よく実行することできる。また、後者の場合には、代表ノードを一回の計算処理が終了する毎に順次別のノードに移行させることにより、計算負荷の偏りを低減させることができる。
【００４５】
本発明の第四の観点はプログラムであって、本発明の特徴とするところは、情報処理装置にインストールすることにより、その情報処理装置に、請求項１記載の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するときに、発ノードから着ノードまでの経路を選択する際に、最下位のレベル１の前記リンクステートデータベースを参照することによって、当該レベル１の仮想ノードの中で、発ノードを含む仮想ノード中に着ノードが存在するかを判断し、発ノードと着ノードが同一仮想ノード内に存在しない場合は、ひとつ上位のレベル２の前記リンクステートデータベースを参照することによって当該レベル２の発ノードを含む仮想ノード中に着ノードが存在するかを判断し、この判断を発ノードと着ノードとが同一仮想ノード中に含まれるまで繰り返すことで、発ノードと着ノードとの両者を含むレベルＮ（Ｎは自然数）の仮想ノードを選択し、この選択されたレベルＮの仮想ノード中で発ノードから着ノードまでのレベルＮの経路を選択する際に、当該選択されたレベルＮの仮想ノード内に含まれる仮想ノード群の経路選択を当該レベルＮの前記リンクステートデータベースを基にして、当該レベルＮの前記選択する手段により選択し、この選択されたレベルＮの経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−１）の前記選択する手段により選択し、これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行させるところにある。
【００４６】
あるいは、本発明の第四の観点はプログラムであって、本発明の特徴とするところは、情報処理装置にインストールすることにより、その情報処理装置に、請求項１記載の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するとき、発ノードから着ノードまでの経路を選択する際に、最上位レベルＮの仮想ノードからなるネットワークで、当該レベルＮの前記リンクステートデータベースを参照することで、発ノード、着ノードが同一仮想ノード内に存在するか否かを判断し、発ノードと着ノードとが同一仮想ノード内に存在する場合は、この仮想ノード内のひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを参照することによって、この仮想ノード内のひとつ下位のレベル（Ｎ−１）のネットワークで発ノードと着ノードとが同一仮想ノード内に存在するか否かを判断し、この判断を発ノードと着ノードとが異なる仮想ノード中に含まれるまで繰り返し、そのひとつ上位レベル（Ｎ−ｋ）（ｋは自然数）の仮想ノードを選択することで、発ノードと着ノードとの両者を含むレベル（Ｎ−ｋ）の仮想ノードを選択し、この仮想ノード中で発ノードから着ノードまでのレベル（Ｎ−ｋ）の経路を選択する際に、当該選択されたレベル（Ｎ−ｋ）の仮想ノード内に含まれる仮想ノード群の経路選択を当該レベル（Ｎ−ｋ）の前記リンクステートデータベースを基にして、当該レベル（Ｎ−ｋ）の前記選択する手段により選択し、この選択されたレベル（Ｎ−ｋ）の経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−ｋ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−ｋ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−ｋ−１）の前記選択する手段により選択し、これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行させるところにある。
【００４７】
本発明の第五の観点は、本発明のプログラムが記録された前記情報処理装置読み取り可能な記録媒体である。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００４８】
これにより、コンピュータ装置等の情報処理装置を用いて、大規模ネットワークへの拡張を実現することができ、さらに、経路計算を必要とするレイヤの範囲を特定してから計算を行うことができるため、無効となる計算を無くすことができ、経路計算を効率良く行うことができる階層化ネットワークノードおよびネットワークおよび階層化経路選択方法を実現することができる。
【００４９】
【発明の実施の形態】
（第一実施例）
はじめに、この階層化ネットワークノードが前提とするネットワークについての説明をする。このネットワークの概略図を図１に示す。このネットワークは複数のレイヤのネットワークで構成され、ここでは、ＩＰレイヤとＳＤＨレイヤと波長レイヤから構成されているものとする。このネットワークで各ノードが、ＩＰアドレスやリンクの最大帯域、使用帯域などの情報からなるリンクステートを広告する。
【００５０】
パスを設定するノードはこのリンクステートを元にして、ＩＰパスを設定するために新しくＳＤＨパスや波長パスを設定するかどうか、ＳＤＨパス、波長パスを新設する場合には、どの経路にパスを設定する方が最もコストが小さくなるかといった計算を行い、パスの設定を行う。また、あるＩＰパスの経路をリアレンジする際に、同時に下位レイヤの波長パスの経路の変更の必要性なども計算する。上記のようなネットワークでは、ネットワーク規模が大きくなるにつれてリンクステートの広告量や、経路計算の計算量などが増加していくため、ある一定規模でスケーラビリティを維持できなくなる。これは、一括で扱うレイヤ数が増えることについても同様のことがいえる。
【００５１】
上記のようなマルチレイヤネットワークをセル分割・仮想ノード化・階層化する様子を図２に示す。ここでは３階層（Ｌｅｖｅｌ３）まで階層化を行っている。また、図３にはネットワークを仮想ノード化した様子を示している。
【００５２】
第一実施例では、このようなネットワークを実現する。このためのノードの概略図を図４に示す。ノードは自ノードの状態や自ノードに接続されているリンクの状態であるリンクステート情報を収集してリンクステートデータベースＬＳＤＢ−Ｌ１に格納する。このリンクステート情報は広告部Ｐを通って他ノードへと広告される。また、自ノードと同一の仮想ノードに含まれている他ノードからもリンクステート情報が広告部Ｐを通して広告されてくる。広告部Ｐに広告されてきた情報の中からＬｅｖｅｌ１のリンクステート情報を選んでリンクステートデータベースＬＳＤＢ−Ｌ１に格納する。もし、このノードが仮想ノードのインタフェースにあたるところに配置されている場合（図３におけるノードＡ，Ｂ，Ｃ）、このノードはボーダノードの役割を果たすことになる。ボーダノードに選ばれたノードは、リンクステートデータベースＬＳＤＢ−Ｌ１のリンクステート情報をＬＳ要約部ＬＳ１において、Ｌｅｖｅｌ２用のリンクステート情報に要約し、これをリンクステートデータベースＬＳＤＢ−Ｌ２に格納するとともに、広告部Ｐを経由して、仮想ノードの外部に、仮想ノードのインタフェース情報として広告する。
【００５３】
同様にＬＳ要約部ＬＳ２は、リンクステートデータベースＬＳＤＢ−Ｌ２のリンクステート情報からリンクステートデータベースＬＳＤＢ−Ｌ３に格納するリンクステート情報を求めるという作業を、ネットワークの階層分だけ繰り返す。
【００５４】
（第二実施例）
第二実施例では図５に示すように、リンクステートデータベースＬＳＤＢ−Ｌ１に格納されているリンクステート情報をもとに、ＬＳ要約部ＬＳ１のスイッチングケーパビリティ割当部（ＳＣ割当部と図示する）ＳＣにおいて、Ｌｅｖｅｌ２の仮想ノードのインタフェースのスイッチングケーパビリティを求める。この結果をリンクステートデータベースＬＳＤＢ−Ｌ２に格納するとともに広告部Ｐを経由して仮想ノードの外部に広告する機能を有している。
【００５５】
同様にＬＳ要約部ＬＳ２は、リンクステートデータベースＬＳＤＢ−Ｌ２のリンクステート情報からリンクステートデータベースＬＳＤＢ−Ｌ３に格納するリンクステート情報を求めるという作業を、ネットワークの階層分だけ繰り返す。このときのノードの機能ブロック図を図５に示す。
【００５６】
（第三実施例）
第三実施例では図６に示すように、リンクステートデータベースＬＳＤＢ−Ｌ１に格納されているリンクステート情報をもとに、ＬＳ要約部ＬＳ１のスイッチングケーパビリティ割当部ＳＣにおいて、Ｌｅｖｅｌ２の仮想ノードのインタフェースのスイッチングケーパビリティを求めるとともに、コスト計算部Ｃにおいて、この仮想ノードを経由するのにかかるコストを計算する。この結果をリンクステートデータベースＬＳＤＢ−Ｌ２に格納するとともに広告部Ｐを経由して仮想ノードの外部に広告する機能を有している。
【００５７】
同様にＬＳ要約部ＬＳ２は、リンクステートデータベースＬＳＤＢ−Ｌ２のリンクステート情報からリンクステートデータベースＬＳＤＢ−Ｌ３に格納するリンクステート情報を求めるという作業を、ネットワークの階層分だけ繰り返す。このときのノードの機能ブロック図を図６に示す。
【００５８】
（第四実施例）
第四実施例では、第二および第三実施例で割当てているスイッチングケーパビリティを規定している。図７に仮想ノードのインタフェースにスイッチングケーパビリティを割当てる方法を示す。ここでは、仮想ノード内を経由してインタフェース間に設定することが可能なパスのレイヤをスイッチングケーパビリティとしてインタフェースに割当てる。よって入力ポートだけでなく、出力ポートにも依存したスイッチングケーパビリティの割当て方になる。
【００５９】
よって、図７の仮想ノードのインタフェースａ１のスイッチングケーパビリティは、インタフェースａ１、ａ２、ｃ２に対してはＰＳＣ（Ｐａｃｋｅｔ　Ｓｗｉｔｃｈｉｎｇ　Ｃａｐａｂｉｌｉｔｙ）＋ＬＳＣ（Ｌａｍｂｄａ　Ｓｗｉｔｃｈｉｎｇ　Ｃａｐａｂｉｌｉｔｙ）であるのに対し、インタフェースｂ、ｃ１に対してはＰＳＣとなる。このようにパスの出力ポートまで考慮したスイッチングケーパビリティの割当てを行うことによって、どのインタフェースを用いればどのレイヤのパスを設定することができるかを正確にセル外部に広告することが可能となる。
【００６０】
（第五実施例）
第五実施例では、第二および第三実施例で割当てているスイッチングケーパビリティを規定している。図８に仮想ノードのインタフェースにスイッチングケーパビリティを割当てる方法を示す。ここでは、仮想ノードのインタフェースに対するセル内のボーダルータのスイッチングケーパビリティを、仮想ノードのインタフェースのスイッチングケーパビリティとして割当てる方式である。
【００６１】
図８ではインタフェースａ１、ａ２はＬＳＣ、インタフェースｂ、ｃ１はＰＳＣ、インタフェースｃ２はＬＳＣ＋ＰＳＣのスイッチングケーパビリティを有することになる。このことによって、仮想ルータのスイッチングケーパビリティの広告量を削減することができる。
【００６２】
（第六実施例）
ネットワークにパスが設定されていくうちに、ネットワークリソースが消費されていき、仮想ノードのインタフェースが有するスイッチングケーパビリティが変化することが考えられる。このため第一〜第五実施例で示した仮想ノードのインタフェースが有するスイッチングケーパビリティが変化したことをトリガとして、他仮想ノードに広告することによって、パス設定時の経路選択が実際のネットワーク状態を正確に反映することが可能となる。
【００６３】
（第七実施例）
ネットワークにパスが設定されていくうちに、ネットワークリソースが消費されていき、仮想ノードのインタフェースが有するスイッチングケーパビリティが変化することが考えられる。このため第一〜第五実施例で示した仮想ノードのインタフェースが有するスイッチングケーパビリティの変化を定期的に他仮想ノードに広告することによって、広告負荷を下げつつ、パス設定時の経路選択が実際のネットワーク状態を正確に反映することが可能となる。
【００６４】
（第八実施例）
図９に仮想ノードネットワークにおけるパス設定コストの概要を示した。仮想ノードネットワークにおけるパス設定コストは、リンクのコストと仮想ノードを経由するコストである。すなわち、
仮想ノードネットワークにおけるパス設定コスト＝
リンクコストの総和＋仮想ノード経由コストの総和
である。このとき、仮想ノードは取り扱うことのできるパスのレイヤをスイッチングケーパビリティで表す。すなわち、仮想ノードのインタフェースにはスイッチングケーパビリティ属性が付与されている。このとき、仮想ノードを経由するコストは、仮想ノードのインタフェースが有しているスイッチングケーパビリティ毎に付与される。これは、仮想ノードを経由する際に、ＩＰレイヤのパスを通す場合と波長レイヤのパスを通す場合とで、コストが異なる場合があるためである。このレイヤ毎のコスト値の比較を行うことによってどのレイヤのパスを設定するのがよいかを決定することができる。
【００６５】
（第九実施例）
図１０に仮想ノードを経由するコストの付与方法について示した。仮想ノードの内部はネットワークで構成されており、セルの外部と接続しているリンクをインタフェースとする。このとき、仮想ノードに入力インタフェースと出力インタフェースとの間に設定することができるパスのレイヤはインタフェースによって異なる。入出力インタフェース対地間のマトリクスを構成すると図１０の例のようになる。ここで、入出力インタフェースが異なれば、セル内部の経路も異なるため、かかるコストも異なってくる。よって、仮想ノードの入出力インタフェース対地間のマトリクスのスイッチングケーパビリティそれぞれにコストを割当てることとする。
【００６６】
このとき、仮想ノードの入出力インタフェース対地間のマトリクスのスイッチングケーパビリティそれぞれに割当てるコストは、この入出力インタフェース間に設定可能な当該スイッチングケーパビリティレイヤパスの経路候補の中から、最小コストでパスを設定可能な経路をコスト選択部において選択する。このときの階層化ネットワークノードの機能ブロックを図１１に示す。図１１の機能ブロックは、図６の機能ブロックにさらにコスト選択部Ｃが追加された構成であり、スイッチングケーパビリティ割当部ＳＣによるスイッチングケーパビリティの割当て、コスト計算部Ｃによるコストの計算および割当てに加え、コスト選択部Ｓによる最小コストでパスを設定可能な経路の選択が行われる。こうして採用されたパスの設定コストを、仮想ノードのインタフェースのコストとして割当てる。
【００６７】
これによって、仮想ノードの経由コスト候補全てではなく、最小のものだけを外部に対して広告することになるため、広告量の削減につながる。
【００６８】
（第十実施例）
図１２に仮想ノードを経由するコストの付与方法について示した。仮想ノードの内部はネットワークで構成されており、セルの外部と接続しているリンクをインタフェースとする。このとき、仮想ノードの入力インタフェースと出力インタフェースとの間に設定することができるパスのレイヤはインタフェースによって異なる。入出力インタフェース対地間のマトリクスを構成すると図１２の例のようになる。ここで、入出力インタフェースが異なれば、セル内部の経路も異なるため、かかるコストも異なってくる。よって、仮想ノードの入出力インタフェース対地間のマトリクスのスイッチングケーパビリティそれぞれにコストを割当てることとする。
【００６９】
このとき、仮想ノードの入出力インタフェース対地間のマトリクスのスイッチングケーパビリティそれぞれに割当てるコストは、当該入出力インタフェースの組み合わせの間に設定することが可能な当該レイヤの最小ホップ数経路パスの設定コストであり、最小ホップ数経路が複数存在する場合は、候補中の最小コストである。
【００７０】
このように第一段階で最小ホップ数でパス設定が可能な経路に限定した後、第二段階で限定した候補の中から一つを選択する方式を用いているが、第一段階の検討である最小ホップ経路の検索はネットワークトポロジの変化が起こらない限り変化がないため、一度検索するだけで後は省略可能である。
【００７１】
この方法によって、より簡易に仮想ノードのインタフェースに割当てるコストを決定することが可能となる。
【００７２】
（第十一実施例）
図１３にノードのコスト付与方法について示した。経路のコストはリンクコストにノードコストを加算したものである。ノードを経由するコストは、このノードが有しているインタフェース数によって決定する。ノードを経由する任意のレイヤのコストは、このレイヤのスイッチングケーパビリティを有しているインタフェースのうち、未使用であるものの数の逆数とする。
【００７３】
（第十二実施例）
図１４にノードのコスト付与方法について示した。経路のコストはリンクコストにノードコストを加算したものである。ノードを経由するコストは、このノードが有しているインタフェース数によって決定する。ノードを経由する任意のレイヤのコストは、このレイヤのスイッチングケーパビリティを有しているインタフェースのうち、使用中であるものの数／総数とする。
【００７４】
（第十三実施例）
図１５に仮想ノードを経由するコストの付与方法について示した。仮想ノードを経由するコストを、仮想ノードが有するインタフェース毎に割当てるのではなく、まとめて一つの値として割当てる。この割当て方は、この仮想ノードに含まれているノードが有しているこのレイヤのスイッチングケーパビリティを有しているインタフェースのうち、未使用であるものの総数の逆数とする。
【００７５】
（第十四実施例）
図１６に仮想ノードを経由するコストの付与方法について示した。仮想ノードを経由するコストを、仮想ノードが有するインタフェース毎に割当てるのではなく、まとめて一つの値として割当てる。この割当て方は、この仮想ノードに含まれているノードが有しているこのレイヤのスイッチングケーパビリティを有しているインタフェースのうち、使用中であるものの総数／総数とする。
【００７６】
（第十五実施例）
仮想ノードを経由するコストは、その内部に存在するスイッチングケーパビリティ毎のインタフェースの空塞状況によって変化するため、仮想ノードのインタフェースに相当するノードは定期的にコストの再計算を行う。
【００７７】
（第十六実施例）
仮想ノードを経由するコストは、その内部に存在するスイッチングケーパビリティ毎のインタフェースの空塞状況によって変化するため、変化の通知を受けた仮想ノードのインタフェースに相当するノードは、即時コストとの再計算を行う。
【００７８】
（第十七実施例）
図１７に第十七実施例の経路選択のシーケンスを示す。まず、経路選択を行うネットワーク範囲を決定する。最下位レベルのセルのうち、発ノードが属しているセル中に着ノードが存在している場合は、このセルの中で経路選択を行う。もし、同一セル中に着ノードが存在しない場合は、一つ上のレベルのセルで発ノードを含むセルを選んで、このセルの中に着ノードが存在するかどうかを調査する。同一セル内に着ノードが存在する場合は、このセル内で経路選択を行うが、存在しない場合は、さらにもう一つ上位レベルのセルで同様の検討を行う。この一連の検討を、着ノードを発見するまで繰り返す。
【００７９】
このようにして決定した経路選択を行うネットワーク範囲において、仮想ノードネットワークの経路選択を当該レベルの経路選択部にて行う。ここで、中継ノードに選ばれた仮想ノードでは、このセル内で同様に仮想ノードネットワークの経路選択を当該レベルの経路選択部にて行う。この経路選択を最下位レベルまで繰り返すことによって発ノードから着ノードまでの経路を決定することが可能となる。このときの階層化ネットワークノードの機能ブロックを図１８に示す。図１８の機能ブロックは、図１１に示した機能ブロックにＬ１経路選択部ＲＳ１、Ｌ２経路選択部ＲＳ２、Ｌ３経路選択部ＲＳ３を追加した構成である。
【００８０】
このように、下位レベルから順に着ノードを発見するまで検討する範囲を広げていく方法を取ることで、近いノード間でパスを設定することが多いネットワークでは、早く着ノードを発見することが可能となる。
【００８１】
（第十八実施例）
図１９に第十八実施例のシーケンスを示す。
【００８２】
まず、経路選択を行うネットワーク範囲を決定する。
【００８３】
最上位レベルのセルのうち、発ノードと着ノードの両者を含むセルが存在するかどうかをチェックする。存在した場合には、このセル中のネットワークにおいて、同様に、発ノードと着ノードの両者を含むセルが存在するかどうかをチェックし、この一連のチェックを発ノードと着ノードが異なるセル中に含まれるようになるまで繰り返す。発ノードと着ノードが異なるセルに含まれていることを確認したら、これらのセルを含むネットワークを経路選択を行う範囲と決定する。
【００８４】
このようにして決定した経路選択を行うネットワーク範囲において、仮想ノードネットワークの経路選択を当該レベルの経路選択部にて行う。ここで、中継ノードに選ばれた仮想ノードでは、このセル内で同様に仮想ノードネットワークの経路選択を当該レベルの経路選択部にて行う。この経路選択を最下位レベルまで繰り返すことによって発ノードから着ノードまでの経路を決定することが可能となる。このときの階層化ネットワークノードの機能ブロックを図１８に示す。
【００８５】
このように、上位レベルから順に経路選択を行うネットワーク範囲を探していく方法をとることで、遠いノード間でパス設定することが多いネットワークでは、早く着ノードを発見することが可能となる。
【００８６】
（第十九実施例）
図２０に第十九実施例のネットワーク管理方式を示す。
【００８７】
第十七実施例、第十八実施例のようにして経路選択を行う場合には、仮想ノードの入出力インタフェースのみが決定された状態で、その仮想ノード内のネットワークにおける経路選択を行う必要が出てくる。
【００８８】
このときこの内部ネットワークの経路選択計算を、あらかじめ決定されている仮想ノードの入出力インタフェースに相当するノードもしくは仮想ノードで担当する方法が考えられる。
【００８９】
（第二十実施例）
図２１に第二十実施例のネットワーク管理方式を示す。第十七および第十八実施例のようにして経路選択を行う場合に、仮想ノードの入出力インタフェースのみが決定された状態で、その仮想ノード内のネットワークにおける経路選択を行う必要が出てくる。
【００９０】
このときこの内部ネットワークの経路計算を、仮想ノード内部から選ばれたノードもしくは仮想ノードが担当することが考えられ得る。さらに、選択するノードもしくは仮想ノードを計算する毎に変更することが可能である。この手法をとることによって、経路選択計算処理がボーダノードのみに集中することを防止することが可能となる。
【００９１】
（第二十一実施例）
図２２に第二十一実施例のリンクバンドリングの方式を示す。ネットワークを複数のセルに分割し、これを仮想ノードと定義すると、仮想ノード間はセル内部のノード同士を接続しているリンク数と同数のリンクで接続されることになる。このネットワークの仮想化を階層構造で行っていくと、この仮想ノード間は多数のリンクで接続されることになる。このとき、仮想ノード間でリンクステートを広告することを考えると、リンク本数の増加は広告リンクステートの増加を引き起こすと考えられる。
【００９２】
このため、仮想ノード対地間に複数本のリンクが存在する場合に、これら複数のリンクをバンドリングして、一本の仮想的なリンクとみなすことにより、リンクステートの増加を防止することが可能となる。このとき、この仮想リンクが結ぶインタフェースの広告方法としては、インタフェースに割当てられているコストが考えられる。
【００９３】
（第二十二実施例）
図２３に第二十二実施例のリンクバンドリングの方式を示す。ネットワークを複数のセルに分割し、これを仮想ノードと定義すると、仮想ノード間はセル内部のノード同士を接続しているリンク数と同数のリンクで接続されることになる。このネットワークの仮想化を階層構造で行っていくと、この仮想ノード間は多数のリンクで接続されることになる。このとき、仮想ノード間でリンクステートを広告することを考えると、リンク本数の増加は広告リンクステートの増加を引き起こすと考えられる。
【００９４】
このため、仮想ノード対地間に複数本のリンクが存在する場合に、これら複数のリンクをバンドリングして、一本の仮想的なリンクとみなすことにより、リンクステートの増加を防止することが可能となる。このとき、同一スイッチングケーパビリティを有するリンク同士をバンドルする方法が考えられる。このとき広告するコストは、バンドルしたリンクのインタフェースが有するコストの中で最小のものを広告することが考えられる。この方法によって、リンク本数を減らすとともに、スイッチングケーパビリティ毎に、その経路を通るときの最小コストを広告することが可能となる。このためより精度の高いトラヒックエンジニアリングが可能となる。
【００９５】
（第二十三実施例）
本実施例の階層化ネットワークノードおよびネットワークおよび階層化経路選択方法は、情報処理装置であるコンピュータ装置を用いて実現することができる。すなわち、第二十三実施例はプログラムであって、本実施例の特徴とするところは、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、本実施例の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するときに、発ノードから着ノードまでの経路を選択する際に、最下位のレベル１の前記リンクステートデータベースを参照することによって、当該レベル１の仮想ノードの中で、発ノードを含む仮想ノード中に着ノードが存在するかを判断し、発ノードと着ノードが同一仮想ノード内に存在しない場合は、ひとつ上位のレベル２の前記リンクステートデータベースを参照することによって当該レベル２の発ノードを含む仮想ノード中に着ノードが存在するかを判断し、この判断を発ノードと着ノードとが同一仮想ノード中に含まれるまで繰り返すことで、発ノードと着ノードとの両者を含むレベルＮ（Ｎは自然数）の仮想ノードを選択し、この選択されたレベルＮの仮想ノード中で発ノードから着ノードまでのレベルＮの経路を選択する際に、当該選択されたレベルＮの仮想ノード内に含まれる仮想ノード群の経路選択を当該レベルＮの前記リンクステートデータベースを基にして、当該レベルＮの前記選択する手段により選択し、この選択されたレベルＮの経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−１）の前記選択する手段により選択し、これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行させるところにある。
【００９６】
あるいは、第二十三実施例はプログラムであって、本実施例の特徴とするところは、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、本実施例の階層化ネットワークノードで構成されるネットワークで任意のレイヤのパスを設定するとき、発ノードから着ノードまでの経路を選択する際に、最上位レベルＮの仮想ノードからなるネットワークで、当該レベルＮの前記リンクステートデータベースを参照することで、発ノード、着ノードが同一仮想ノード内に存在するか否かを判断し、発ノードと着ノードとが同一仮想ノード内に存在する場合は、この仮想ノード内のひとつ下位のレベル（Ｎ−１）の前記リンクステートデータベースを参照することによって、この仮想ノード内のひとつ下位のレベル（Ｎ−１）のネットワークで発ノードと着ノードとが同一仮想ノード内に存在するか否かを判断し、この判断を発ノードと着ノードとが異なる仮想ノード中に含まれるまで繰り返し、そのひとつ上位レベル（Ｎ−ｋ）（ｋは自然数）の仮想ノードを選択することで、発ノードと着ノードとの両者を含むレベル（Ｎ−ｋ）の仮想ノードを選択し、この仮想ノード中で発ノードから着ノードまでのレベル（Ｎ−ｋ）の経路を選択する際に、当該選択されたレベル（Ｎ−ｋ）の仮想ノード内に含まれる仮想ノード群の経路選択を当該レベル（Ｎ−ｋ）の前記リンクステートデータベースを基にして、当該レベル（Ｎ−ｋ）の前記選択する手段により選択し、この選択されたレベル（Ｎ−ｋ）の経路に含まれる仮想ノード中で、さらに発ノードから着ノードまでのひとつ下位のレベル（Ｎ−ｋ−１）の経路を選択する際に、当該選択された仮想ノードにおけるひとつ下位のレベル（Ｎ−ｋ−１）の前記リンクステートデータベースを基に当該レベル（Ｎ−ｋ−１）の前記選択する手段により選択し、これを最下位のレベル１まで繰り返すことによって発ノードから着ノードまでの経路を選択する手順を実行させるところにある。
【００９７】
本実施例のプログラムは本実施例の記録媒体に記録されることにより、コンピュータ装置は、この記録媒体を用いて本実施例のプログラムをインストールすることができる。あるいは、本実施例のプログラムを保持するサーバからネットワークを介して直接コンピュータ装置に本実施例のプログラムをインストールすることもできる。
【００９８】
これにより、コンピュータ装置を用いて、大規模ネットワークへの拡張を実現することができ、さらに、経路計算を必要とするレイヤの範囲を特定してから計算を行うことができるため、無効となる計算を無くすことができ、経路計算を効率良く行うことができる階層化ネットワークノードおよびネットワークおよび階層化経路選択方法を実現することができる。
【００９９】
【発明の効果】
以上説明したように、本発明によれば、大規模ネットワークへの拡張を実現することができ、さらに、経路計算を必要とするレイヤの範囲を特定してから計算を行うことができるため、無効となる計算を無くすことができ、経路計算を効率良く行うことができる。
【図面の簡単な説明】
【図１】マルチレイヤネットワークの概略図。
【図２】第一実施例のマルチレイヤネットワークをセル分割・仮想ノード化・階層化する様子を示す図。
【図３】第一実施例のネットワークを仮想ノード化した様子を示す図。
【図４】第一実施例のノードの概略図。
【図５】第二実施例のノードの機能ブロック図。
【図６】第三実施例のノードの機能ブロック図。
【図７】第四実施例の仮想ノードのインタフェースにスイッチングケーパビリティを割当てる方法を示す図。
【図８】第五実施例の仮想ノードのインタフェースにスイッチングケーパビリティを割当てる方法を示す図。
【図９】第八実施例の仮想ノードネットワークにおけるパス設定コストの概要を示す図。
【図１０】第九実施例の仮想ノードを経由するコストの付与方法について示す図。
【図１１】第九実施例の階層化ネットワークノードの機能ブロック図。
【図１２】仮想ノードを経由するコストの付与方法について示す図。
【図１３】第十一実施例のノードのコスト付与方法について示す図。
【図１４】第十二実施例のノードのコスト付与方法について示す図。
【図１５】第十三実施例の仮想ノードを経由するコストの付与方法について示す図。
【図１６】第十四実施例の仮想ノードを経由するコストの付与方法について示す図。
【図１７】第十七実施例の経路選択のシーケンスを示す図。
【図１８】第十七実施例の階層化ネットワークノードの機能ブロック図。
【図１９】第十八実施例の経路選択のシーケンスを示す図。
【図２０】第十九実施例のネットワーク管理方式を示す図。
【図２１】第二十実施例のネットワーク管理方式を示す図。
【図２２】第二十一実施例のリンクバンドリングの方式を示す図。
【図２３】第二十二実施例のリンクバンドリングの方式を示す図。
【符号の説明】
ａ１、ａ２、ｂ、ｃ１、ｃ２　インタフェース
Ａ〜Ｅ　ノード
Ｃ　コスト計算部
ＬＳＤＢ−Ｌ１、ＬＳＤＢ−Ｌ２、ＬＳＤＢ−Ｌ３　リンクステートデータベース
ＬＳ１、ＬＳ２　ＬＳ要約部
Ｐ　広告部
ＲＳ１　Ｌ１経路選択部
ＲＳ２　Ｌ２経路選択部
ＲＳ３　Ｌ３経路選択部
ＳＣ　ＳＣ（スイッチングケーパビリティ）割当部
Ｓ　コスト選択部
【図１】
2004129135.tif 000003
【図２】
2004129135.tif 000004
【図３】
2004129135.tif 000005
【図４】
2004129135.tif 000006
【図５】
2004129135.tif 000007
【図６】
2004129135.tif 000008
【図７】
2004129135.tif 000009
【図８】
2004129135.tif 000010
【図９】
2004129135.tif 000011
【図１０】
2004129135.tif 000012
【図１１】
2004129135.tif 000013
【図１２】
2004129135.tif 000014
【図１３】
2004129135.tif 000015
【図１４】
2004129135.tif 000016
【図１５】
2004129135.tif 000017
【図１６】
2004129135.tif 000018
【図１７】
2004129135.tif 000019
【図１８】
2004129135.tif 000020
【図１９】
2004129135.tif 000021
【図２０】
2004129135.tif 000022
【図２１】
2004129135.tif 000023
【図２２】
2004129135.tif 000024
【図２３】
2004129135.tif 000025