(57)【特許請求の範囲】
【請求項１】
ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードであって、
メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成手段と、
自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換手段と、
リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御手段と、
リンクステート情報交換手段が受信したリンクステート情報によって、当該リンクステート情報を送信したノードを認識するノード認識手段と、
仮想ネットワークに属する隣接ノードが設定されたテーブルを予め保持し、前記テーブルに設定された隣接ノードのうち、前記ノード認識手段が認識したノードを生存中の隣接ノードとして設定するテーブル設定手段とを備え、
リンクステート情報交換手段は、生存中の隣接ノードの情報を含むリンクステート情報を送信する
ことを特徴とするノード。
【請求項２】
ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードであって、
メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成手段と、
自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換手段と、
リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御手段と、
仮想ネットワークのトポロジに対する指針であるトポロジポリシを保持するトポロジポリシ保持手段と、
仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、受信したリンクステート情報に含まれるノード情報およびリンク情報が、前記トポロジポリシに合致しない場合、前記テーブルにおける隣接ノードの設定を、前記トポロジポリシに合致するように修正するテーブル設定手段とを備え、
リンクステート情報交換手段は、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信する
ことを特徴とするノード。
【請求項３】
ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードであって、
メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成手段と、
自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換手段と、
リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御手段と、
リンクステート情報交換手段が受信したリンクステート情報によって、仮想ネットワークに属するノードを認識するノード認識手段と、
仮想ネットワークの構成態様を指定する情報である態様指定情報を保持する態様指定情報保持手段と、
仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、ノード認識手段が仮想ネットワークに属するノードを認識したときに、前記態様指定情報が指定する構成態様を満たすように、前記テーブルにおける隣接ノードの設定を修正するテーブル設定手段とを備え、
リンクステート情報交換手段は、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信する
ことを特徴とするノード。
【請求項４】
態様指定情報保持手段は、仮想ネットワークの構成態様としてフルメッシュトポロジを指定する態様指定情報を保持し、
テーブル設定手段は、ノード認識手段が認識した各ノードを隣接ノードとして前記テーブルに設定する
請求項３に記載のノード。
【請求項５】
態様指定情報保持手段は、仮想ネットワークの構成態様としてリング型トポロジを指定する態様指定情報を保持し、
テーブル設定手段は、自ノードのノードＩＤより大きいノードＩＤを持つノードのうち、最も小さいノードＩＤを持つノードと、自ノードのノードＩＤより小さいノードＩＤを持つノードのうち、最も大きいノードＩＤを持つノードとを隣接ノードとして前記テーブルに設定する
請求項３に記載のノード。
【請求項６】
態様指定情報保持手段は、仮想ネットワークの構成態様としてスター型トポロジを指定する態様指定情報を保持し、
テーブル設定手段は、自ノードがスター型トポロジの中心となる特定のノードであるならば、ノード認識手段が認識した各ノードを隣接ノードとして前記テーブルに設定し、自ノードがスター型トポロジの中心となる特定のノードでないならば、前記特定のノードを隣接ノードとして前記テーブルに設定する
請求項３に記載のノード。
【請求項７】
態様指定情報保持手段は、仮想ネットワークの構成態様としてツリー型トポロジを指定する態様指定情報を保持し、
テーブル設定手段は、ノード認識手段が認識したノードのうち、自ノードの上位階層のノードおよび下位階層のノードを隣接ノードとして前記テーブルに設定する
請求項３に記載のノード。
【請求項８】
ノード認識手段が認識したノードが属する仮想ネットワーク上の経路計算を行う経路計算手段を備え、
テーブル設定手段は、複数の仮想ネットワークそれぞれに対応する複数のテーブルを保持し、
態様指定情報保持手段は、個々の仮想ネットワーク毎の態様指定情報を保持し、
テーブル設定手段は、個々の仮想ネットワーク毎に、当該仮想ネットワークに対して定められた態様指定情報に応じて、当該仮想ネットワークに対応するテーブルを設定し、
経路計算手段は、個々の仮想ネットワーク毎に経路計算を行う
請求項３から請求項７のうちのいずれか１項に記載のノード。
【請求項９】
仮想ネットワークに属するノードの死活監視を行う死活監視手段を備え、
リンクステート情報交換手段は、仮想ネットワークに属するノードの離脱が検出されたときに、個々の仮想ネットワーク毎に、前記ノードの離脱を示すリンクステート情報を送信する
請求項８に記載のノード。
【請求項１０】
リンクステート型ルーティングプロトコルは、Ｃｈｏｒｄであり、
ツリー配送制御手段は、Ｃｈｏｒｄ  Ｂｒｏａｄｃａｓｔにおけるブロードキャストツリーに沿ってリンクステート情報が転送されるようにリンクステート情報の転送先を定める
請求項１から請求項９のうちのいずれか１項に記載のノード。
【請求項１１】
仮想ネットワークに属するノードの死活監視を行う死活監視手段を備え、
リンクステート情報交換手段は、仮想ネットワークに属するノードの離脱が検出されたときに、当該ノードの離脱を示すリンクステート情報を送信する
請求項１から請求項１０のうちのいずれか１項に記載のノード。
【請求項１２】
ベースネットワーク上に設けられる仮想ネットワークに適用されるリンクステート型ルーティングプロトコルを用いた経路制御方法であって、
メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成し、
リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定め、
自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信し、
受信したリンクステート情報によって、当該リンクステート情報を送信したノードを認識し、
仮想ネットワークに属する隣接ノードが設定されたテーブルを予め保持し、前記テーブルに設定された隣接ノードのうち、認識した前記ノードを生存中の隣接ノードとして設定し、
生存中の隣接ノードの情報を含むリンクステート情報を送信する
ことを特徴とする経路制御方法。
【請求項１３】
ベースネットワーク上に設けられる仮想ネットワークに適用されるリンクステート型ルーティングプロトコルを用いた経路制御方法であって、
メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成し、
リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定め、
自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信し、
仮想ネットワークのトポロジに対する指針であるトポロジポリシを保持し、
仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、受信したリンクステート情報に含まれるノード情報およびリンク情報が、前記トポロジポリシに合致しない場合、前記テーブルにおける隣接ノードの設定を、前記トポロジポリシに合致するように修正し、
修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信する
ことを特徴とする経路制御方法。
【請求項１４】
ベースネットワーク上に設けられる仮想ネットワークに適用されるリンクステート型ルーティングプロトコルを用いた経路制御方法であって、
メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成し、
リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定め、
自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信し、
受信したリンクステート情報によって、仮想ネットワークに属するノードを認識し、
仮想ネットワークの構成態様を指定する情報である態様指定情報を保持し、
仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、仮想ネットワークに属するノードを認識したときに、前記態様指定情報が指定する構成態様を満たすように、前記テーブルにおける隣接ノードの設定を修正し、
修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信する
ことを特徴とする経路制御方法。
【請求項１５】
仮想ネットワークの構成態様としてフルメッシュトポロジを指定する態様指定情報を保持し、
認識した各ノードを隣接ノードとして前記テーブルに設定する
請求項１４に記載の経路制御方法。
【請求項１６】
仮想ネットワークの構成態様としてリング型トポロジを指定する態様指定情報を保持し、
自ノードのノードＩＤより大きいノードＩＤを持つノードのうち、最も小さいノードＩＤを持つノードと、自ノードのノードＩＤより小さいノードＩＤを持つノードのうち、最も大きいノードＩＤを持つノードとを隣接ノードとして前記テーブルに設定する
請求項１４に記載の経路制御方法。
【請求項１７】
仮想ネットワークの構成態様としてスター型トポロジを指定する態様指定情報を保持し、
自ノードがスター型トポロジの中心となる特定のノードであるならば、認識した各ノードを隣接ノードとして前記テーブルに設定し、自ノードがスター型トポロジの中心となる特定のノードでないならば、前記特定のノードを隣接ノードとして前記テーブルに設定する
請求項１４に記載の経路制御方法。
【請求項１８】
仮想ネットワークの構成態様としてツリー型トポロジを指定する態様指定情報を保持し、
認識したノードのうち、自ノードの上位階層のノードおよび下位階層のノードを隣接ノードとして前記テーブルに設定する
請求項１４に記載の経路制御方法。
【請求項１９】
複数の仮想ネットワークそれぞれに対応する複数のテーブルを保持し、
個々の仮想ネットワーク毎の態様指定情報を保持し、
個々の仮想ネットワーク毎に、当該仮想ネットワークに対して定められた態様指定情報に応じて、当該仮想ネットワークに対応するテーブルを設定し、
認識したノードが属する仮想ネットワーク上の経路計算を個々の仮想ネットワーク毎に行う
請求項１４から請求項１８のうちのいずれか１項に記載の経路制御方法。
【請求項２０】
仮想ネットワークに属するノードの死活監視を行い、
仮想ネットワークに属するノードの離脱が検出されたときに、個々の仮想ネットワーク毎に、前記ノードの離脱を示すリンクステート情報を送信する
請求項１９に記載の経路制御方法。
【請求項２１】
リンクステート型ルーティングプロトコルは、Ｃｈｏｒｄであり、
Ｃｈｏｒｄ  Ｂｒｏａｄｃａｓｔにおけるブロードキャストツリーに沿ってリンクステート情報が転送されるようにリンクステート情報の転送先を定める
請求項１２から請求項２０のうちのいずれか１項に記載の経路制御方法。
【請求項２２】
仮想ネットワークに属するノードの死活監視を行い、
仮想ネットワークに属するノードの離脱が検出されたときに、当該ノードの離脱を示すリンクステート情報を送信する
請求項１２から請求項２１のうちのいずれか１項に記載の経路制御方法。
【請求項２３】
ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードとなるコンピュータに搭載される経路制御プログラムであって、
前記コンピュータに、
メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成処理、
自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換処理、
リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御処理、
リンクステート情報交換処理で受信したリンクステート情報によって、当該リンクステート情報を送信したノードを認識するノード認識処理、および、
仮想ネットワークに属する隣接ノードが設定されたテーブルを予め保持し、前記テーブルに設定された隣接ノードのうち、前記ノード認識処理で認識したノードを生存中の隣接ノードとして設定するテーブル設定処理を実行させ、
リンクステート情報交換処理で、生存中の隣接ノードの情報を含むリンクステート情報を送信させる
ための経路制御プログラム。
【請求項２４】
ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードとなるコンピュータであって、仮想ネットワークのトポロジに対する指針であるトポロジポリシを保持するトポロジポリシ保持手段を備えたコンピュータに搭載される経路制御プログラムにおいて、
前記コンピュータに、
メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成処理、
自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換処理、
リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御処理、および、
仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、受信したリンクステート情報に含まれるノード情報およびリンク情報が、前記トポロジポリシに合致しない場合、前記テーブルにおける隣接ノードの設定を、前記トポロジポリシに合致するように修正するテーブル設定処理を実行させ、
リンクステート情報交換処理で、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信させる
ための経路制御プログラム。
【請求項２５】
ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードとなるコンピュータであって、仮想ネットワークの構成態様を指定する情報である態様指定情報を保持する態様指定情報保持手段を備えたコンピュータに搭載される経路制御プログラムにおいて、
前記コンピュータに、
メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成処理、
自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換処理、
リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御処理、
リンクステート情報交換処理で受信したリンクステート情報によって、仮想ネットワークに属するノードを認識するノード認識処理、および、
仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、ノード認識処理で仮想ネットワークに属するノードを認識したときに、前記態様指定情報が指定する構成態様を満たすように、前記テーブルにおける隣接ノードの設定を修正するテーブル設定処理を実行させ、
リンクステート情報交換処理で、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信させる
ための経路制御プログラム。
【請求項２６】
態様指定情報保持手段が仮想ネットワークの構成態様としてフルメッシュトポロジを指定する態様指定情報を保持するコンピュータに搭載され、
前記コンピュータに、
テーブル設定処理で、ノード認識処理で認識した各ノードを隣接ノードとして前記テーブルに設定させる
請求項２５に記載の経路制御プログラム。
【請求項２７】
態様指定情報保持手段が仮想ネットワークの構成態様としてリング型トポロジを指定する態様指定情報を保持するコンピュータに搭載され、
前記コンピュータに、
テーブル設定処理で、自ノードのノードＩＤより大きいノードＩＤを持つノードのうち、最も小さいノードＩＤを持つノードと、自ノードのノードＩＤより小さいノードＩＤを持つノードのうち、最も大きいノードＩＤを持つノードとを隣接ノードとして前記テーブルに設定させる
請求項２５に記載の経路制御プログラム。
【請求項２８】
態様指定情報保持手段が仮想ネットワークの構成態様としてスター型トポロジを指定する態様指定情報を保持するコンピュータに搭載され、
前記コンピュータに、
テーブル設定処理で、自ノードがスター型トポロジの中心となる特定のノードであるならば、ノード認識処理で認識した各ノードを隣接ノードとして前記テーブルに設定させ、自ノードがスター型トポロジの中心となる特定のノードでないならば、前記特定のノードを隣接ノードとして前記テーブルに設定させる
請求項２５に記載の経路制御プログラム。
【請求項２９】
態様指定情報保持手段が仮想ネットワークの構成態様としてツリー型トポロジを指定する態様指定情報を保持するコンピュータに搭載され、
前記コンピュータに、
テーブル設定処理で、ノード認識処理で認識したノードのうち、自ノードの上位階層のノードおよび下位階層のノードを隣接ノードとして前記テーブルに設定させる
請求項２５に記載の経路制御プログラム。
【請求項３０】
態様指定情報保持手段が個々の仮想ネットワーク毎の態様指定情報を保持するコンピュータに搭載され、
前記コンピュータに
ノード認識処理で認識したノードが属する仮想ネットワーク上の経路計算を行う経路計算処理を実行させ、
テーブル設定処理で、複数の仮想ネットワークそれぞれに対応する複数のテーブルを保持させ、個々の仮想ネットワーク毎に、当該仮想ネットワークに対して定められた態様指定情報に応じて、当該仮想ネットワークに対応するテーブルを設定させ、
経路計算処理で、個々の仮想ネットワーク毎に経路計算を行わせる
請求項２５から請求項２９のうちのいずれか１項に記載の経路制御プログラム。
【請求項３１】
前記コンピュータに、
仮想ネットワークに属するノードの死活監視を行う死活監視処理を実行させ、
リンクステート情報交換処理で、仮想ネットワークに属するノードの離脱が検出されたときに、個々の仮想ネットワーク毎に、前記ノードの離脱を示すリンクステート情報を送信させる
請求項３０に記載の経路制御プログラム。
【請求項３２】
前記コンピュータに、
分散ハッシュテーブル生成処理で、リンクステート型ルーティングプロトコルとしてＣｈｏｒｄを用いて分散ハッシュテーブルを生成させ、
ツリー配送制御処理で、Ｃｈｏｒｄ  Ｂｒｏａｄｃａｓｔにおけるブロードキャストツリーに沿ってリンクステート情報が転送されるようにリンクステート情報の転送先を定めさせる
請求項２３から請求項３１のうちのいずれか１項に記載の経路制御プログラム。
【請求項３３】
前記コンピュータに、
仮想ネットワークに属するノードの死活監視を行う死活監視処理を実行させ、
リンクステート情報交換処理で、仮想ネットワークに属するノードの離脱が検出されたときに、当該ノードの離脱を示すリンクステート情報を送信させる
請求項２３から請求項３２のうちのいずれか１項に記載の経路制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想ネットワークにおけるノード、経路制御方法および経路制御プログラムに関し、特に、ＶＰＮ(Virtual Private Network )やオーバレイネットワーク等のような、実ネットワーク上に構成された仮想的なネットワーク（仮想ネットワーク）において、リンクステート型ルーティングプロトコルを用いて経路制御を行うノード、およびそのノードに適用される経路制御方法、経路制御プログラムに関する。
【背景技術】
【０００２】
実ネットワーク上に構成された仮想ネットワークにおける経路制御方法には、リンクステート型ルーティングプロトコルが用いられている。また、リンクステート型ルーティングプロトコルは、仮想ネットワークのみならず、一般的な有線・無線ネットワーク上でのルーティングプロトコルとして用いられている。
【０００３】
リンクステート型ルーティングプロトコルは、コンピュータネットワークにおける経路計算を行うための代表的なルーティングプロトコルの１つとして広く用いられる。具体的なリンクステート型ルーティングプロトコルの代表例としては、ＯＳＰＦ(Open Shortest Path First)が挙げられる。
【０００４】
リンクステート型ルーティングプロトコルは、隣接状態などの各ノードにおけるリンク状態（リンクステート情報）を他のノードと共有することにより、ネットワーク全体のトポロジを把握し、経路計算を実現している。リンクステート情報は、定期的に送信される他に、隣接状態が変化した際もリンクステート更新を通知する情報として送信される。このように、隣接状態が変化し、ネットワーク全体のトポロジが不明である状況下においても確実に他の全てのノードに対してリンクステート情報を行き渡らせるために、フラッディングと呼ばれるメッセージ転送手法が用いられる。フラッディングとは、水があふれるように周り中にパケットを流し、多方面に連鎖的に転送してもらうメッセージ転送方式のことである。これによってパケットは、一定の生存期間中に無差別に転送される。
【０００５】
フラッディングには、確実にリンクステート情報を行き渡らせるという利点がある。しかし、その反面、上述のように連鎖的にメッセージ転送を繰り返すと、同じノードが同じメッセージを重複して受信することになり、無駄な転送によってネットワーク資源を浪費してしまうという問題がある。そのため、リンクステート型ルーティングプロトコルにおけるフラッディングによるトラフィック量を削減するための様々な方法が提案されている（例えば、非特許文献１参照）。非特許文献１には、ＯＬＳＲ（Optimized Link State Routing Protocol ）におけるＭＰＲ（Multipoint Relays ）を利用した方法が記載されている。
【０００６】
ＯＬＳＲでは、一般的なリンクステート型ルーティングプロトコルと同様、各ノードがＨｅｌｌｏメッセージを定期的に送信し、隣接ノードのセットを認識する。ＯＬＳＲではさらに、認識した隣接ノードのセットをＨｅｌｌｏメッセージに含めて広告を行う。これにより各ノードは、２ホップ先に存在するノードのセット（２ホップ隣接ノードセット）を認識することができる。２ホップ隣接ノードセットを認識すると、全ての２ホップ隣接ノードへ到達するために経由しなければならない最小の隣接ノードのセットを計算する。ここで計算される隣接ノードのセットがＭＰＲセットである。ＭＰＲに選択されたノードは、そのＭＰＲを選択したノード（ＭＰＲセレクタ）によって通知され、ＭＰＲセレクタによって送信されたノードから受信したフラッディングメッセージだけを転送するように動作する。
【０００７】
ＯＬＳＲでは、上述のように各ノードがＭＰＲを計算し、リンクステート情報を他のノードへフラッディングする際、ＭＰＲとして選択されたノードだけがリンクステート情報の転送を行う。そのため、フラッディングによるトラフィック量を削減することが可能となる。
【０００８】
このように、リンクステート型ルーティングプロトコルでは、制御メッセージによるトラフィック量を削減するために、フラッディングによって受信したリンクステート情報を転送するノードを最小限に絞り込むという方法が用いられていた。
【０００９】
また、一般的なリンクステート型ルーティングプロトコルでは、リンクステート情報の交換は、実際にユーザのデータが通る仮想ネットワークのトポロジ上か、あるいはその仮想ネットワークのトポロジを縮退したトポロジ上で行われる。また、Ｈｅｌｌｏメッセージも、実際にユーザのデータが通る仮想ネットワークのトポロジ上で交換される。
【００１０】
【非特許文献１】T. Clausen, P. Jacquet,”Optimized Link State Routing Protocol (OLSR)”, RFC3626, October 2003.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、仮想ネットワークにおいて、リンクステート型ルーティングプロトコルで用いる制御メッセージ量を非特許文献１に記載の方法で削減しようとする場合、Ｈｅｌｌｏメッセージによるトラフィック量が大きいという問題がある。その理由は、仮想ネットワークでは、隣接ノードとのリンクはＰｏｉｎｔ−ｔｏ−Ｐｏｉｎｔのトンネルによって構成されるため、Ｈｅｌｌｏメッセージはリンクごとに独立して流れるからである。すなわち、無線ネットワークのように１回のブロードキャストによって全ての隣接ノードへＨｅｌｌｏメッセージが届く仕組みではなく、各隣接ノードごとに個別にＨｅｌｌｏメッセージを送信しなければならない。一般的なリンクステート型ルーティングプロトコルでは、Ｈｅｌｌｏメッセージは全ての隣接ノード間で交換されるので、Ｈｅｌｌｏメッセージによるトラフィック量はネットワーク内のリンク数に比例する。この場合、リンク数が多いネットワーク（例えばフルメッシュトポロジなどのリンク密度が高いネットワーク）では、Ｈｅｌｌｏメッセージによるトラフィック量が無視できない。このように、トラフィック量が大きいという問題がある。
【００１２】
そこで、本発明は、制御メッセージのトラフィック量を削減可能な、仮想ネットワークにおけるリンクステート型ルーティングプロトコルを用いたノード、経路制御方法および経路制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明によるノードは、ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードであって、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成手段と、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換手段と、リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御手段と、リンクステート情報交換手段が受信したリンクステート情報によって、当該リンクステート情報を送信したノードを認識するノード認識手段と、仮想ネットワークに属する隣接ノードが設定されたテーブルを予め保持し、前記テーブルに設定された隣接ノードのうち、前記ノード認識手段が認識したノードを生存中の隣接ノードとして設定するテーブル設定手段とを備え、リンクステート情報交換手段が、生存中の隣接ノードの情報を含むリンクステート情報を送信することを特徴とする。
また、本発明によるノードは、ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードであって、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成手段と、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換手段と、リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御手段と、仮想ネットワークのトポロジに対する指針であるトポロジポリシを保持するトポロジポリシ保持手段と、仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、受信したリンクステート情報に含まれるノード情報およびリンク情報が、前記トポロジポリシに合致しない場合、前記テーブルにおける隣接ノードの設定を、前記トポロジポリシに合致するように修正するテーブル設定手段とを備え、リンクステート情報交換手段が、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信することを特徴とする。
また、本発明によるノードは、ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードであって、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成手段と、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換手段と、リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御手段と、リンクステート情報交換手段が受信したリンクステート情報によって、仮想ネットワークに属するノードを認識するノード認識手段と、仮想ネットワークの構成態様を指定する情報である態様指定情報を保持する態様指定情報保持手段と、仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、ノード認識手段が仮想ネットワークに属するノードを認識したときに、前記態様指定情報が指定する構成態様を満たすように、前記テーブルにおける隣接ノードの設定を修正するテーブル設定手段とを備え、リンクステート情報交換手段が、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信することを特徴とする。
【００１４】
また、本発明による経路制御方法は、ベースネットワーク上に設けられる仮想ネットワークに適用されるリンクステート型ルーティングプロトコルを用いた経路制御方法であって、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成し、リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定め、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信し、受信したリンクステート情報によって、当該リンクステート情報を送信したノードを認識し、仮想ネットワークに属する隣接ノードが設定されたテーブルを予め保持し、前記テーブルに設定された隣接ノードのうち、認識した前記ノードを生存中の隣接ノードとして設定し、生存中の隣接ノードの情報を含むリンクステート情報を送信することを特徴とする。
また、本発明による経路制御方法は、ベースネットワーク上に設けられる仮想ネットワークに適用されるリンクステート型ルーティングプロトコルを用いた経路制御方法であって、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成し、リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定め、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信し、仮想ネットワークのトポロジに対する指針であるトポロジポリシを保持し、仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、受信したリンクステート情報に含まれるノード情報およびリンク情報が、前記トポロジポリシに合致しない場合、前記テーブルにおける隣接ノードの設定を、前記トポロジポリシに合致するように修正し、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信することを特徴とする。
また、本発明による経路制御方法は、ベースネットワーク上に設けられる仮想ネットワークに適用されるリンクステート型ルーティングプロトコルを用いた経路制御方法であって、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成し、リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定め、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信し、受信したリンクステート情報によって、仮想ネットワークに属するノードを認識し、仮想ネットワークの構成態様を指定する情報である態様指定情報を保持し、仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、仮想ネットワークに属するノードを認識したときに、前記態様指定情報が指定する構成態様を満たすように、前記テーブルにおける隣接ノードの設定を修正し、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信することを特徴とする
【００１５】
また、本発明による経路制御プログラムは、ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードとなるコンピュータに搭載される経路制御プログラムであって、前記コンピュータに、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成処理、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換処理、リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御処理、リンクステート情報交換処理で受信したリンクステート情報によって、当該リンクステート情報を送信したノードを認識するノード認識処理、および、仮想ネットワークに属する隣接ノードが設定されたテーブルを予め保持し、前記テーブルに設定された隣接ノードのうち、前記ノード認識処理で認識したノードを生存中の隣接ノードとして設定するテーブル設定処理を実行させ、リンクステート情報交換処理で、生存中の隣接ノードの情報を含むリンクステート情報を送信させることを特徴とする。
また、本発明による経路制御プログラムは、ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードとなるコンピュータであって、仮想ネットワークのトポロジに対する指針であるトポロジポリシを保持するトポロジポリシ保持手段を備えたコンピュータに搭載される経路制御プログラムにおいて、前記コンピュータに、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成処理、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換処理、リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御処理、および、仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、受信したリンクステート情報に含まれるノード情報およびリンク情報が、前記トポロジポリシに合致しない場合、前記テーブルにおける隣接ノードの設定を、前記トポロジポリシに合致するように修正するテーブル設定処理を実行させ、リンクステート情報交換処理で、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信させることを特徴とする。
また、本発明による経路制御プログラムは、ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる前記仮想ネットワークの経路制御を行うノードとなるコンピュータであって、仮想ネットワークの構成態様を指定する情報である態様指定情報を保持する態様指定情報保持手段を備えたコンピュータに搭載される経路制御プログラムにおいて、前記コンピュータに、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する分散ハッシュテーブル生成処理、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信するリンクステート情報交換処理、リンクステート情報が当該リンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるツリー配送制御処理、リンクステート情報交換処理で受信したリンクステート情報によって、仮想ネットワークに属するノードを認識するノード認識処理、および、仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、ノード認識処理で仮想ネットワークに属するノードを認識したときに、前記態様指定情報が指定する構成態様を満たすように、前記テーブルにおける隣接ノードの設定を修正するテーブル設定処理を実行させ、リンクステート情報交換処理で、修正後の前記テーブルに設定された隣接ノードの情報を含むリンクステート情報を送信させることを特徴とする。
【発明の効果】
【００１６】
本発明によれば、リンクステート情報がそのリンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定めるので、リンクステート情報のトラフィック量を削減することができる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施形態を図面を参照して説明する。
【００１８】
実施形態１．
図１は、本発明の第１の実施形態のノードを示すブロック図である。図１に示す本発明の第１の実施形態のノードＡ１，Ａ２は、ベースネットワークＮ１を介して接続されている。なお、図１では、２つのノードＡ１，Ａ２を図示しているが、ベースネットワークＮ１を介して接続されるノードの数は２つに限定されない。各ノードＡ１，Ａ２は、仮想ネットワークに属するノードであり、それぞれ同一の構成を有する。そのため、以下、ノードＡ１を例に説明する。
【００１９】
ベースネットワークＮ１上に、各ノードが属する仮想ネットワークが設けられる。
【００２０】
ノードＡ１は、ＤＨＴプロトコル部Ａ１１と、ツリー配送制御部Ａ１２と、リンクステート情報交換部Ａ１３と、リンクステートデータベース記憶部Ａ１４と、仮想ネットワークトポロジ設定部Ａ１５と、経路計算部Ａ１６と、ルーティングテーブル記憶部Ａ１７とを備える。ノードＡ２も同様の要素を備えるが、図１では、ＤＨＴプロトコル部Ａ１１とリンクステート情報交換部Ａ１３のみを図示している。
【００２１】
ＤＨＴプロトコル部Ａ１１は、分散ハッシュテーブル(Distributed Hash Table; DHT)を構成するためのプロトコルに従って動作する。分散ハッシュテーブルのプロトコルとしては、Ｃｈｏｒｄ，Ｐａｓｔｒｙ，Ｔａｐｅｓｔｒｙ，ＣＡＮなどがあり、ＤＨＴプロトコル部Ａ１１は、いずれのプロトコルに従って動作してもよい。また、例示したプロトコル以外のプロトコルに従ってもよい。
【００２２】
Ｃｈｏｒｄについては、以下に示す参考文献１に記載されている。
【００２３】
［参考文献１］
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan,“Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications”,ACM SIGCOMM 2001, San Deigo, CA, August 2001, pp. 149-160.
【００２４】
Ｐａｓｔｒｙについては、以下に示す参考文献２に記載されている。
【００２５】
［参考文献２］
A. Rowstron and P. Druschel,“Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems”, IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, pages 329-350, November, 2001.
【００２６】
Ｔａｐｅｓｔｒｙについては、以下に示す参考文献３に記載されている。
【００２７】
［参考文献３］
B. Zhou, A. Joseph, J. Kubiatowicz,“Tapestry: A Resilient Global Scale Overlay for Service Deployment”,IEEE JSAC, Jan 2004.
【００２８】
ＣＡＮについては、以下に示す参考文献４に記載されている。
【００２９】
［参考文献４］
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker,“A Scalable Content-Addressable Network”, In Proceedings of ACM SIGCOMM 2001.
【００３０】
ＤＨＴプロトコル部Ａ１１は、各ノードに割り当てられたキーをもとに、分散ハッシュテーブルを構成（生成）する。ここで、各ノードのキーは、各ノードのＩＰアドレスやホストネームなどのユニークな識別子に対してハッシュをかけることによって作成すればよい。また、キー長としては１２８ビットや１６０ビットなどの互いに重複する可能性が現実的にゼロである十分な長さの値が用いられる。
【００３１】
分散ハッシュテーブルの構成方法はプロトコルの種類によって異なるが、その大きな特徴として、全てのノードを知らなくとも、予め決められた規則に従って隣接ノードを設定するだけで、全ての他のノードへたどり着くための構造化されたテーブルが構成されるという点が挙げられる。ここで、「隣接ノードを設定する」とは、あるキーの範囲に対応するノードにメッセージ（リンクステート情報）を到達させるために、そのメッセージを転送すべき次のホップノードを定めることを意味する。すなわち、いずれの分散ハッシュテーブルのプロトコルに従う場合であっても、各ノードのＤＨＴプロトコル部が、宛先ノードのキーの範囲に応じてメッセージを転送すべき次のノードを定めることで、メッセージを到達させるべきノードにメッセージを転送することができる。分散ハッシュテーブルのプロトコル（ＤＨＴプロトコル）を使わない場合、全てのノードへたどり着くためのテーブルを構成するためには、全体のノード数がＮである場合、１ノードあたり、Ｎの１乗のオーダーのコストがかかるが、ＤＨＴプロトコルでは、典型的にはｌｏｇＮのオーダーでテーブルを構成することができるため、スケーラビリティの高い方法であるといえる。また、ノードの追加・削除に対して自律分散的にテーブルを再構成できるという点も大きな特徴として挙げられる。
【００３２】
以下、ＤＨＴプロトコル部Ａ１１がＣｈｏｒｄプロトコルに従って動作する場合を例にして説明する。すなわち、あるキーの範囲に対応するノードにメッセージを到達させるために、そのメッセージを転送すべき次のホップノードを定める処理を、Ｃｈｏｒｄプロトコルに従って行う場合を例にする。Ｃｈｏｒｄプロトコルは、ハッシュ空間をリング状に見立ててテーブルを構成する手法である。Ｃｈｏｒｄを用いる場合、隣接ノードはｆｉｎｇｅｒと呼ばれる。ｆｉｎｇｅｒの最大数はハッシュ長によって決まり、ハッシュ長が２ｎビットの場合、ｎ個である。このとき、ｋ番目のｆｉｎｇｅｒをｆｉｎｇｅｒ（ｋ）と記す。なお、０≦ｋ≦ｎ−１である。ＤＨＴプロトコル部Ａ１１は、自分（自ノード）のキーをＸとすると、キーがＸ＋２ｋ以上であるノードのなかから、Ｘ＋２ｋに最も近い値のキーをもつノードをｆｉｎｇｅｒ（ｋ）として選択する。そして、Ｙというキーをもつ宛先ノードへ到達するためには、Ｙ以下で最もＹに近いキーをもつｆｉｎｇｅｒへ転送を行うように定める。換言すると、Ｘ＿（ｋ−１）＜Ｙ≦Ｘ＿ｋを満足するキーＹを有するノードにメッセージを到達させるためにメッセージを転送すべきノードがｆｉｎｇｅｒ（ｋ）であるというエントリを作成する。この動作は、メッセージを転送すべき次のノードを示す分散ハッシュテーブルの生成の一例である。ここで、Ｘ＿（ｋ−１）は、ｆｉｎｇｅｒ（ｋ−１）のキーであり、Ｘ＿ｋは、ｆｉｎｇｅｒ（ｋ）のキーである。各ノードのＤＨＴプロトコル部がこの動作を再帰的に繰り替えることにより（すなわち、各ノードのＤＨＴプロトコル部がそれぞれｆｉｎｇｅｒを定めることにより）、任意のキーをもつ宛先ノードへメッセージを到達させることができる。
【００３３】
また、ＤＨＴプロトコル部Ａ１１は、ＤＨＴプロトコルによって管理される隣接ノード（Ｃｈｏｒｄの場合はｆｉｎｇｅｒ）の状態を監視する。そして、隣接ノードのネットワークからの離脱が検出された場合、ＤＨＴプロトコル部Ａ１１は、そのノードの離脱をリンクステート情報交換部Ａ１３へ伝え、そのノードが離脱したことを示すリンクステート情報を送信させる。
【００３４】
リンクステート情報とは、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報である。ノード情報は、例えば、ノードを識別するノードＩＤ（ノード識別子）である。また、リンク情報は、例えば、隣接ノードのＩＰアドレス、隣接ノードとのリンクコスト、隣接ノードとのリンクのリンク品質などである。
【００３５】
また、ＤＨＴプロトコル部Ａ１１は、隣接ノードの死活監視を行う。すなわち、隣接ノードが仮想ネットワークに参加しているか離脱したかを判定する。例えば、ＤＨＴプロトコル部Ａ１１は、分散ハッシュテーブルにおける隣接ノード（Ｃｈｏｒｄの場合にはｆｉｎｇｅｒ）に対して定期的にｐｉｎｇパケットを送信し、閾値以上の回数分だけ連続して応答がなかった場合に、その隣接ノードが離脱したと判定し、離脱したと判定するまでの間は仮想ネットワークに参加していると判定すればよい。この判定方法は、死活監視の一例であり、他の方法で死活監視を行ってもよい。なお、Ｃｈｏｒｄプロトコルでは、ノードの死活監視はｆｉｎｇｅｒに対してしか行わない。
【００３６】
ツリー配送制御部Ａ１２は、ＤＨＴプロトコル部Ａ１１によって構成された分散ハッシュテーブルに基づいて、リンクステート情報交換部Ａ１３が送信するリンクステート情報を他の全てのノードへ到達するように配送制御する。各ノードのツリー配送制御部Ａ１２は、ノードＡ１だけではなく、他の全てのノードにおいても同じアルゴリズムで動作する。そして、ツリー配送制御部Ａ１２は、自ノードをルートとし他の全てのノードがリーフあるいは分節点となるブロードキャストツリーに沿ってリンクステート情報を転送する。例えば、ノードＡ１のツリー配送制御部Ａ１２は、自ノードであるノードＡ１をルートとし他の全てのノードがリーフあるいは分節点となるブロードキャストツリーに沿ってリンクステート情報を転送する。このように自ノードをルートとするブロードキャストツリー上にリンクステート情報を配送することによって、同じノードが同じメッセージを重複して受信する無駄な転送が発生しない。従って、フラッディングによって発生するトラフィック量を最小限に抑えることができる。
【００３７】
ＤＨＴプロトコル部Ａ１１によって構成された分散ハッシュテーブルに基づいてツリー配送を行う方法の例として、本実施形態では、Ｃｈｏｒｄ  Ｂｒｏａｄｃａｓｔを用いる場合を例にとって説明する。Ｃｈｏｒｄ  Ｂｒｏａｄｃａｓｔの詳細な動作については以下の参考文献５に記載されている。
【００３８】
［参考文献５］
Sameh El-Ansary, Luc Onana Alima, Per Brand and Seif Haridi,“"Efficient Broadcast in Structured P2P Networks”, The 2nd International Workshop On Peer-To-Peer Systems (IPTPS'03), (Berkeley, CA, USA), February 2003.
【００３９】
Ｃｈｏｒｄ  Ｂｒｏａｄｃａｓｔを用いたメッセージの配送方法について説明する。ここでは、ノードＡ１がメッセージの送信元であるソースノードである場合を例にする。ソースノードであるノードＡ１のツリー配送制御部Ａ１２は、全てのｆｉｎｇｅｒに対してメッセージを送信すると決定する。ここで、ノードＡ１のリンクステート情報交換部Ａ１３は、ｆｉｎｇｅｒ（ｋ）へ送信されるメッセージのヘッダに、Key_(k+1)を付加情報として入れる。なお、Key_k はｆｉｎｇｅｒ（ｋ）のキーを意味するものとする。ノードＡ１からメッセージを受信したｆｉｎｇｅｒ（ｋ）のツリー配送制御部Ａ１２は、ｆｉｎｇｅｒ（ｋ）のキーである Key_k から、Key_(k+1) 未満までのキーの範囲に存在する全てのｆｉｎｇｅｒに対して、受信したメッセージを転送すると決定する。以後、メッセージを受信したｆｉｎｇｅｒは、再帰的に同様の動作でメッセージを転送する。この結果、参加している全てのノードに対して同じメッセージを送り届けることができる。
【００４０】
リンクステート情報交換部Ａ１３は、自ノード（本例ではノードＡ１）がもつリンクステート情報を他ノードへ送信する。また、リンクステート情報交換部Ａ１３は、他のノードから送られてきたリンクステート情報を受信する。リンクステート情報の送受信は、ツリー配送制御部Ａ１２を介して行われ、無駄な転送を発生させないようにツリー上での配送が行われる。すなわち、リンクステート情報交換部Ａ１３は、ツリー配送制御部Ａ１２が上記のようにリンクステート情報を送信すると決定したノードに対してリンクステート情報を送信する。リンクステート情報交換部Ａ１３は、他のノードから受信したリンクステート情報をリンクステートデータベース記憶部Ａ１４へ渡す。また、自ノードのリンクステート情報を送信する際は、仮想ネットワークトポロジ設定部Ａ１５において、生存フラグが１である隣接ノードだけをリンクステート情報に含めて送信する。また、リンクステート情報交換部Ａ１３は、ＤＨＴプロトコル部Ａ１１によってノードの離脱の検出を伝えられた場合、そのノードが送信したリンクステート情報を消去（フラッシュ）するためのリンクステート情報を送信する。換言すれば、そのノードの離脱を示すリンクステート情報を送信する。フラッシュするためには、例えば、そのノードが送信したリンクステート情報の経過時間をＭａｘＡｇｅとして再送信する。ＭａｘＡｇｅの経過時間を有するリンクステート情報を受信したノードは、該リンクステート情報（離脱したノードが送信したリンクステート情報）を直ちに消去する。
【００４１】
リンクステートデータベース記憶部Ａ１４は、リンクステート情報交換部Ａ１３によって集められた自ノードを含む仮想ネットワーク内の全てのノードのリンクステート情報を蓄積し、接続しているノードのリストやリンクの接続状況を認識する機能を有する。例えば、リンクステートデータベース記憶部Ａ１４は、リンクステート情報を送信したノードのノードＩＤをリストアップすることによって、接続しているノードのリストを認識すればよい。また、リンクステートデータベース記憶部Ａ１４は、ノードのリストおよび各リンクステート情報において広告されている各ノードからの隣接ノードへのリンク情報により、リンクの接続情報を認識すればよい。さらに、リンクステートデータベース記憶部Ａ１４は、認識したノードのリストを仮想ネットワークトポロジ設定部Ａ１５に渡す。
【００４２】
仮想ネットワークトポロジ設定部Ａ１５は、自ノード（ここではノードＡ１）が属する仮想ネットワークにおいて、自ノード（ノードＡ１）がどのノードと隣接ノードとして仮想リンクを設定するかを示す情報が設定されている。自ノードがどのノードと仮想リンクを設定するのかを示す情報を仮想ネットワークトポロジ設定テーブルと記す。
【００４３】
図２は、仮想ネットワークトポロジ設定部Ａ１５において設定される仮想ネットワークトポロジ設定テーブルの例を示す説明図である。図２に示す例では、ノードＡ１の仮想ネットワークトポロジ設定テーブル１０１において、４つの隣接ノードが設定されていて、それぞれの隣接ノードのノードＩＤがＡ２，Ａ３，Ａ４，Ａ６となっている。なお、仮想ネットワークトポロジ設定テーブルのノードＩＤは、分散ハッシュテーブル（ＤＨＴ）においてノードを識別するためのＩＤとは別に定められている。また、図２に示す例では、各隣接ノードのベースＩＰアドレスが、“２．３．４．５”，“３．４．５．６”，“４．５．６．７”，“６．７．８．９”となっている。さらに、“２．３．４．５” のベースＩＰアドレスをもつ隣接ノードに対しては、仮想リンクを構成するために設定されるトンネルに振られる仮想ＩＰアドレスが、ローカル側（すなわちノードＡ１側）が“１０．１．２．１”に設定され、リモート側（隣接ノード側）が“１０．１．２．２”に設定されている。同様に、他の３つの隣接ノードに対しても仮想ＩＰアドレスが設定されている。
【００４４】
また、仮想ネットワークトポロジ設定テーブルでは、それぞれの隣接ノードに対して生存フラグを設定する。仮想ネットワークトポロジ設定部Ａ１５は、リンクステートデータベース記憶部Ａ１４によって生存していると認識されたノードに対しては“１”を設定し、そのように認識されていないノードに対しては“０”を設定する。
【００４５】
リンクステート情報交換部Ａ１３は、仮想ネットワークトポロジ設定部Ａ１５において生存フラグが“１”となっている隣接ノードの情報だけをリンクステート情報として広告する。このように動作することにより、現在オンラインであるノードについてのみ隣接ノードとして仮想リンクが設定され、仮想ネットワークトポロジを構成することができる。すなわち、オフラインであるノードを除いて仮想ネットワークトポロジが構成される。
【００４６】
経路計算部Ａ１６は、リンクステートデータベース記憶部Ａ１４によって認識されたリンクステート情報を用いて、仮想ネットワーク内の各ノードへ到達するための次ホップまたは経路全体を計算し、経路エントリとしてルーティングテーブル記憶部Ａ１７へ登録する。この動作の結果、リンクステート型ルーティングプロトコルによる仮想ネットワークの経路制御が実現される。経路計算部Ａ１６が用いる経路計算アルゴリズムとしては、リンクステート型ルーティングプロトコルで用いられるＤｉｊｋｓｔｒａアルゴリズムが一般的である。経路計算部Ａ１６は、例えば、Ｄｉｊｋｓｔｒａアルゴリズムに従って到達先までの経路計算を行えばよい。また、経路計算部Ａ１６は、リンクステートデータベース記憶部Ａ１４が認識するリンクステート情報に変化があった際に経路計算を行う。
【００４７】
ルーティングテーブル記憶部Ａ１７は、ルーティングテーブルを記憶する。ルーティングテーブルは、経路計算部Ａ１６によって計算された経路エントリが登録されるテーブルである。ルーティングテーブル記憶部Ａ１７が記憶するルーティングテーブルには、宛先ＩＰアドレスに対応する次ホップノードのＩＰアドレスだけが登録されてもよい。また、経路上の各ホップのＩＰアドレス（すなわち経路全体）が登録されてもよい。
【００４８】
図３は、本発明の第１の実施形態における制御メッセージ用トポロジと仮想ネットワークトポロジとの関係の例を示す説明図である。以下、図３を参照して、本実施形態においてリンクステート情報交換部Ａ１３がツリー配送制御部Ａ１２を介してリンクステート情報の交換を行った結果、経路計算部Ａ１６によって経路の計算が行われる対象となる仮想ネットワークのトポロジとの関係を示す。
【００４９】
図３に示す例では、ノードＡ１〜Ａ６が仮想ネットワークに接続している。また、図３に示す制御メッセージ用トポロジＴ１１は、ＤＨＴプロトコル部Ａ１１によって構成される分散ハッシュテーブルに基づいてリンクステート情報をツリー状に配送するための論理トポロジである。制御メッセージ用トポロジＴ１１で示している各矢印は、ノードＡ１を送信元として送信されるリンクステート情報の配送経路を示している。図３に示すように、ノードＡ１がリンクステート情報の送信元となる場合には、ノードＡ１を頂点（ルート）とし、他のノードＡ２〜Ａ６にそれぞれ到達するツリー状のトポロジとなる。仮想ネットワークトポロジＴ２１は、制御メッセージ用トポロジＴ１１を用いて行われたリンクステート情報交換の結果構成される。仮想ネットワークトポロジＴ２１は、実際にユーザのデータが通る仮想ネットワークのトポロジである。
【００５０】
本発明では、リンクステート情報の交換は、仮想ネットワークトポロジＴ２１ではなく、制御メッセージ用トポロジＴ１１上で行われる。また、本発明のノードは、仮想ネットワークトポロジＴ２１における全てのリンク上でＨｅｌｌｏメッセージを交換する必要はない。
【００５１】
一般的なリンクステート型ルーティングプロトコルにおけるＨｅｌｌｏメッセージは、本発明では、ＤＨＴプロトコル部Ａ１１がもつノードの死活監視機構によって代替される。
【００５２】
本実施形態では、図２に例示するような仮想ネットワークトポロジ設定テーブルが予め各ノードに設定され、各ノードが自ノードをルートとするブロードキャストツリーに沿ってリンクステート情報を送信する。そして、各ノードは、受信したリンクステート情報に応じて、仮想ネットワークトポロジ設定テーブルの生存フラグを更新して、仮想ネットワークを修正する。
【００５３】
次に、動作について説明する。
図４は、本発明の第１の実施形態のノードがリンクステート情報を受信した際の動作の例を示すフローチャートである。ノードＡ１を例にして動作を説明する。
【００５４】
まず、ノードＡ１のリンクステート情報交換部Ａ１３が隣接ノードからリンクステート情報を受信する（ステップＳ１０１）。すると、リンクステート情報交換部Ａ１３は、受信したリンクステート情報のヘッダを参照し、自ノードのＤＨＴキーとヘッダで内に情報として含められているキーの間の範囲内のキーをもつｆｉｎｇｅｒが存在するかどうかをツリー転送配送制御部Ａ１２に判定させる（ステップＳ１０２）。ツリー転送配送制御部Ａ１２は、自ノードのキーと受信したリンクステート情報のヘッダに含まれるキーとの間の範囲内のキーに対応するｆｉｎｇｅｒがあるか否かを判定する。
【００５５】
ツリー転送配送制御部Ａ１２がその範囲内にｆｉｎｇｅｒがあると判定した場合（ステップＳ１０２におけるＹｅｓ）、リンクステート情報交換部Ａ１３は、該当する全てのｆｉｎｇｅｒへ受信したリンクステート情報をコピーして転送する（ステップＳ１０３）。すなわち、上記の範囲内のキーに対応する各ｆｉｎｇｅｒに、リンクステート情報のコピーを送信する。このとき、リンクステート情報交換部Ａ１３は、リンクステート情報のヘッダ内にはキーとしてKey_(k+1)を含める。既に説明したように、Key_k はｆｉｎｇｅｒ（ｋ）のキーを意味する。従って、リンクステート情報交換部Ａ１３は、自ノードであるノードＡ１にとっての１つ先のｆｉｎｇｅｒのキーを、ヘッダ内に含めたリンクステート情報を送信する。
【００５６】
ステップＳ１０３の処理の後、あるいは、上記の範囲内にｆｉｎｇｅｒがないとツリー転送配送制御部Ａ１２が判定した場合（ステップＳ１０２におけるＮｏ）、リンクステート情報交換部Ａ１３は、ステップＳ１０１で受信したリンクステート情報をリンクステートデータベース記憶部Ａ１４へ渡す。リンクステートデータベース記憶部Ａ１４は、ステップＳ１０１で受信したリンクステート情報を参照し、以前に受信したリンクステート情報と比較して、リンクステート情報が変化しているか否かを判定する（ステップＳ１０４）。
【００５７】
ステップＳ１０４においてリンクステート情報に変化があると判定した場合、リンクステートデータベース記憶部Ａ１４は、そのリンクステート情報から認識されるノードのリストが、それまで認識していたノードのリストから変化しているか否かを判定する（ステップＳ１０５）。ここで、ノードのリストはリンクステートデータベース記憶部Ａ１４によって管理されている。
【００５８】
ステップＳ１０５においてノードのリストに変化があると判定した場合、リンクステートデータベース記憶部Ａ１４は、仮想ネットワークトポロジ設定部Ａ１５において設定されている隣接ノード設定の各エントリの生存フラグとの食い違いを調べる。そして、違いがあれば仮想ネットワークトポロジ設定部Ａ１５に、設定されている隣接ノードの生存フラグを修正させる（ステップＳ１０６）。
【００５９】
ステップＳ１０６の具体例を説明する。例えば、仮想ネットワークトポロジ設定部Ａ１５において、図２に例示する仮想ネットワークトポロジ設定テーブル１０１が設定されており、ステップＡ１０１で受信したリンクステート情報からノードＡ３が追加されたと認識されたとする。この場合、仮想ネットワークトポロジ設定部Ａ１５に、ノードＡ３に対する生存フラグを０から１に変更させる。また、例えば、受信したリンクステート情報から、ノードＡ４が消滅したと判断された場合は、ノードＡ４に対する生存フラグを１から０に変更させる。
【００６０】
ステップＳ１０６でデータトポロジ設定部Ａ１５が設定を変更すると、データトポロジ設定部Ａ１５は、その変更に基づいてリンクステート情報を更新する。このリンクステート情報は、自ノードに関するリンクステート情報である。すなわち、自ノードのノード情報および自ノードと隣接ノードとの間の各リンクに関するリンク情報を更新する。データトポロジ設定部Ａ１５は、他のノードへ送信すべく更新したそのリンクステート情報をリンクステート情報交換部Ａ１３に渡す（ステップＳ１０７）。また、ステップＳ１０７において、リンクステート情報交換部Ａ１３は、ツリー配送制御部Ａ１２を介して、ノードＡ１のｆｉｎｇｅｒの情報を取得し、各ｆｉｎｇｅｒに対してそのリンクステート情報を送信する。
【００６１】
ステップＳ１０７の処理を行った後、あるいは、ステップＳ１０５においてノードのリストに変化がないと判定された場合、経路計算部Ａ１６は、新しいリンクステート情報に基づいて経路計算を実行し（ステップＳ１０８）、計算結果に基づいてルーティングテーブル記憶部Ａ１７の更新を行う（ステップＳ１０９）。
【００６２】
また、ステップＳ１０４においてリンクステート情報に変化がないと判定された場合は、経路計算・ルーティングテーブル更新を行わず終了する。すなわち、ステップＳ１０５以降の処理を行わずに処理を終了する。
【００６３】
以上、本実施形態において、ノードＡ１においてリンクステート情報を受信した際の動作について説明した。
【００６４】
以上の説明では、ＤＨＴプロトコル部Ａ１１においてＣｈｏｒｄが用いられる場合について説明したが、その他のＤＨＴプロトコルを用いる場合でも適用が可能である。利用可能なＤＨＴプロトコルであるか否かの選択基準は、ツリー配送が可能であるか否かである。
【００６５】
他のＤＨＴプロトコルが使われる場合の例として、ＴａｐｅｓｔｒｙやＰａｓｔｒｙなどのＰｌａｘｔｏｎアルゴリズムを用いるＤＨＴプロトコルの場合について説明する。ここで、各ノードのもつキーは１６進数で４桁であるとする。すなわち、ｂ＝４，ｌ＝４であるとする。この“ｂ”は、キーの各桁の基数であり、１６進数の場合、１６＝２４であるので、ｂ＝４となる。ｌは、キーの桁数である。ソースノード（この場合ノードＡ１）のリンクステート情報交換部Ａ１３は、Ｐｌａｘｔｏｎアルゴリズムにおける全ての隣接ノードに対してメッセージを送信する。ここで、リンクステート情報交換部Ａ１３は、隣接ノードに対応する宛先キーをメッセージのヘッダに付加情報として入れる。例えば、送信するノードのキーが１Ａ７Ｄであり、１Ｅ＊＊（＊は任意の数字を示す）の宛先キーに対する経路エントリとして、１Ｅ２９というキーをもつ隣接ノードへメッセージを転送するとする。この場合、経路エントリの宛先キーである“１Ｅ＊＊”を付加情報としてヘッダに含める。このメッセージを受信したノードは、ヘッダに入っている付加情報に基づき、よりキーを絞り込む範囲の隣接ノードへメッセージを転送する。この際、同様に、隣接ノードに対応する宛先キーをメッセージのヘッダに付加情報として入れる。例えば、自ノードのキーが１Ｅ２９であり、“１Ｅ＊＊”が受信したメッセージのヘッダの付加情報に含まれていた場合、１Ｅ＊＊の＊＊の部分（この場合下位８ビット）をより絞り込む宛先キー（すなわち１Ｅ１＊，１Ｅ２＊，・・・といった宛先キー）に対応する経路エントリの隣接ノードへ、受信したメッセージを転送する。以上の動作を再帰的に繰り返すことにより、参加している全てのノードに対して同じメッセージを送り届けることができる。
【００６６】
また、本実施形態においては、ＤＨＴプロトコル部Ａ１１において、ＣｈｏｒｄやＰａｓｔｒｙなどの構造化ＤＨＴプロトコルが用いられる場合について説明したが、他にも、Ｇｎｕｔｅｌｌａなどの非構造型のＰ２Ｐ(Peer-to-Peer)プロトコルが用いられてもよい。
【００６７】
次に本実施形態の効果について説明する。
本実施形態では、ツリー配送制御部Ａ１２が、ＤＨＴプロトコル部Ａ１１によって自律分散的に構成された分散ハッシュテーブルに基づいて、リンクステート情報交換部Ａ１３が送信するリンクステート情報を他の全てのノードへ到達するように制御する。こうすることにより、フラッディングにおける問題であった、同じノードが同じメッセージを重複して受信する無駄な転送を防ぎ、フラッディングによって発生するトラフィック量を最小限に抑えることができる。すなわち、リンクステート情報のトラフィック量を削減することができる。
【００６８】
また、一般的なリンクステート型ルーティングプロトコルではＨｅｌｌｏメッセージを仮想ネットワークトポロジ上で交換しているが、本実施形態では、Ｈｅｌｌｏメッセージの交換を、ＤＨＴプロトコル部Ａ１１がもつノードの死活監視機構で代替している。すなわち、Ｈｅｌｌｏメッセージの交換を行わずに、ＤＨＴプロトコル部Ａ１１が隣接ノードの死活を監視する。ＤＨＴプロトコルでは、ノードの死活監視はＤＨＴプロトコル上での隣接ノード（Ｃｈｏｒｄの場合はｆｉｎｇｅｒ）に対してしか行わないため、そのトラフィック量は、仮想ネットワークトポロジにおけるリンク数に比例せず、フルメッシュトポロジのようなリンク密度が多い仮想ネットワークでも、ノードの死活監視のトラフィック量を一定に抑えることができる。
【００６９】
実施形態２．
図５は、本発明の第２の実施形態のノードを示すブロック図である。図５に示す本発明の第２の実施形態のノードＢ１，Ｂ２は、ベースネットワークＮ１を介して接続されている。第１の実施形態と同様に、ベースネットワークＮ１に接続されるノードの数は２つに限定されない。各ノードＢ１，Ｂ２は、仮想ネットワークに属するノードであり、それぞれ同一の構成を有する。そのため、以下、ノードＢ１を例に説明する。
【００７０】
ノードＢ１は、ＤＨＴプロトコル部Ｂ１１と、ツリー配送制御部Ｂ１２と、リンクステート情報交換部Ｂ１３と、リンクステートデータベース記憶部Ｂ１４と、仮想ネットワークトポロジ設定部Ｂ１５と、経路計算部Ｂ１６と、ルーティングテーブル記憶部Ｂ１７と、トポロジポリシ設定部Ｂ１８とを備える。これらの各構成要素のうち、ＤＨＴプロトコル部Ｂ１１と、ツリー配送制御部Ｂ１２と、リンクステート情報交換部Ｂ１３と、経路計算部Ｂ１６と、ルーティングテーブル記憶部Ｂ１７は、第１の実施形態のノードＡ１（図１参照）におけるＤＨＴプロトコル部Ａ１１と、ツリー配送制御部Ａ１２と、リンクステート情報交換部Ａ１３と、経路計算部Ａ１６と、ルーティングテーブル記憶部Ａ１７と同様の構成要素であり、説明を省略する。また、リンクステートデータベース記憶部Ｂ１４も、第１の実施形態のノードＡ１におけるリンクステートデータベース記憶部Ａ１４と同様の構成要素である。また、ノードＢ２もノードＢ１と同様の要素を備えるが、ＤＨＴプロトコル部Ｂ１１とリンクステート情報交換部Ｂ１３のみを図示している。
【００７１】
リンクステートデータベース記憶部Ｂ１４は、図１に示すリンクステートデータベース記憶部Ａ１４と同様に、リンクステート情報交換部Ｂ１３によって集められた自ノードを含む仮想ネットワーク内の全てのノードのリンクステート情報を蓄積し、接続しているノードの情報やリンクの情報（すなわち仮想ネットワークのトポロジ）を認識する機能を有する。リンクステートデータベース記憶部Ｂ１４は、認識されたノード情報およびリンク情報を、仮想ネットワークトポロジ設定部Ｂ１５へ渡す。
【００７２】
仮想ネットワークトポロジ設定部Ｂ１５は、第１の実施形態における仮想ネットワークトポロジ設定部Ａ１５（図１参照）が有する機能に加え、さらに、以下の処理も行う。仮想ネットワークトポロジ設定部Ｂ１５は、リンクステートデータベース記憶部Ｂ１４から受け取った仮想ネットワークのノード情報およびリンク情報がトポロジポリシ設定部Ｂ１８に設定されているトポロジポリシに適合するか否かを判断する。そして、そのノード情報およびリンク情報がトポロジポリシに適合していない場合、仮想ネットワークのトポロジを修正する機能を有する。トポロジポリシは、仮想ネットワークのトポロジに対する指針であり、換言すれば、仮想ネットワークの状態に応じて設定すべき設定内容を示す情報である。
【００７３】
図６は、第２の実施形態において仮想ネットワークトポロジ設定部Ｂ１５に設定される仮想ネットワークトポロジ設定テーブルの例を示す説明図である。図６に示す例では、本実施形態における仮想ネットワークトポロジ設定テーブル１０２の項目には、第１の実施形態における仮想ネットワークトポロジ設定テーブル１０１（図２参照）と同様に、ノードＩＤ、隣接ノードのベースＩＰアドレス、ローカル側およびリモート側の仮想ＩＰアドレス、生存フラグが含まれる。これらの項目に加えて、第２の実施形態ではさらに、修正フラグも仮想ネットワークトポロジ設定テーブル１０２に含まれる。
【００７４】
修正フラグは、ノードがトポロジポリシに適合していないために修正されたか否かを示すフラグである。修正フラグは、予め設定されている隣接ノードのエントリに対しては初期値（本例では“０”とする。）が設定される。そして、トポロジポリシ設定部Ｂ１８に設定されているトポロジポリシに適合しないために仮想ネットワークトポロジ設定部Ｂ１５において修正されたエントリに対しては、修正されたことを示す値（本例では“１”とする）が設定される。図６に示す例では、隣接ノードであるノードＢ４のエントリは新規に作成された隣接ノードのエントリであることがわかる。
【００７５】
トポロジポリシ設定部Ｂ１８は、トポロジポリシ（自ノードが属している仮想ネットワークのトポロジに対する指針）が設定されている。トポロジポリシ設定部Ｂ１８に設定されているトポロジポリシを、仮想ネットワークトポロジ設定部Ｂ１５が参照する。仮想ネットワークトポロジ設定部Ｂ１５は、ノード情報およびリンク情報が表している仮想ネットワークのトポロジがトポロジポリシに適合するか否かを判断する。
【００７６】
図７は、トポロジポリシ設定部Ｂ１８に設定されるトポロジポリシの例を示す説明図である。図７に例示するトポロジポリシ２０１は、仮想ネットワークが複数のセグメントに分離した場合の動作を示している。具体的には、仮想ネットワークが複数のセグメントに分離した場合、各セグメントの最も小さいＩＤをもつノード同士が仮想リンクを設定する状態にするという動作を示している。このトポロジポリシにより、仮想ネットワークが複数のセグメントに分離されないようにすることができる。
【００７７】
図８は、制御メッセージ用トポロジと仮想ネットワークトポロジとの関係の例を示す説明図である。図８を参照して、トポロジ修正の例を説明する。リンクステートデータベース記憶部Ｂ１４によって認識されたノード情報およびリンク情報では、ノードＢ１〜Ｂ３および、ノードＢ４〜Ｂ６の２つのセグメントに分かれていたとする。すなわち、図８における仮想ネットワークトポロジＴ２２に示すように、ノードＢ１〜Ｂ３が仮想ネットワークの１つのセグメントに属し、ノードＢ４〜Ｂ６が仮想ネットワークの他のセグメントに属しているとする。仮想ネットワークトポロジ設定部Ｂ１５がトポロジポリシに従ってトポロジを修正した結果、各セグメント内で最も小さいノードＩＤをもつノードＢ１，Ｂ４とを接続するリンクが構成される。本例の場合、例えば、ノードＢ１の仮想ネットワークトポロジ設定部Ｂ１５が、仮想ネットワークトポロジ設定テーブルにノードＢ４を追加し、ノードＢ４の仮想ネットワークトポロジ設定部Ｂ１５が、仮想ネットワークトポロジ設定テーブルにノードＢ１を追加すればよい。
【００７８】
ここでは、トポロジポリシの例として、仮想ネットワークが複数のセグメントに分離しないというポリシが記述される場合について説明したが、トポロジポリシの記述内容は本例の場合に限定されない。例えば、必ず２つ以上のノードに対して仮想リンクを構成するというポリシや、各ノードにおける仮想リンク数を一定数以下に抑えるというポリシなどが設定されていてもよい。また、仮想ネットワークトポロジ設定部Ｂ１５は、隣接ノードを追加する修正のほか、隣接ノードを削除する修正を行ってもよい。
【００７９】
次に、動作について説明する。
図９は、本発明の第２の実施形態のノードがリンクステート情報を受信した際の動作の例を示すフローチャートである。ノードＢ１を例にして動作を説明する。
【００８０】
第１の実施形態と同様の処理については、図４と同一の符号を付し、説明を省略する。すなわち、図９に示すステップＳ１０１〜Ｓ１０７およびステップＳ１０７〜Ｓ１０９の動作は、第１の実施形態における動作（図４参照）と同様の動作である。
【００８１】
本実施形態では、ステップＳ１０６の後、仮想ネットワークトポロジ設定部Ｂ１５は、リンクステートデータベース記憶部Ｂ１４から受け取った仮想ネットワークのノード情報およびリンク情報がトポロジポリシ設定部Ｂ１８に設定されているトポロジポリシに適合するかを調べる（ステップＳ２０７）。
【００８２】
ノード情報およびリンク情報がトポロジポリシに適合していると判断した場合（ステップＳ２０７のＹｅｓ）、ステップＳ１０７以降の処理を行う。
【００８３】
ノード情報およびリンク情報がトポロジポリシに適合していないと判断した場合（ステップＳ２０７のＮｏ）、仮想ネットワークトポロジ設定部Ｂ１５は、仮想ネットワークトポロジ設定部Ｂ１５に設定されている仮想ネットワークトポロジ設定テーブルに対して修正を行う（ステップＳ２０８）。すなわち、仮想ネットワークトポロジ設定テーブルの設定内容が、トポロジポリシに合致するように仮想ネットワークトポロジ設定テーブルの内容を修正する。例えば、特定の条件を満たすノードが仮想リンクを設定したり、仮想リンクを削除する場合、その条件を満たしているノードの仮想ネットワークトポロジ設定部Ｂ１５が仮想ネットワークトポロジ設定テーブルに隣接ノードを追加したり、削除したりする。図８に示した例では、「小さいノードＩＤをもつ」という条件に該当するノードＢ１，Ｂ４が隣接ノードを追加する場合を示した。仮想ネットワークトポロジ設定部Ｂ１５は、修正により追加または削除した隣接ノードのエントリの修正フラグを、修正されたことを示す値（“１”）とする。
【００８４】
このステップＳ２０８の後、ステップＳ１０７以降の処理を行う。
【００８５】
次に、本実施形態の効果について説明する。
第２の実施形態においても、第１の実施形態と同様の効果を得ることができる。また、第２の実施形態では、仮想ネットワークトポロジ設定部Ｂ１５が、リンクステート情報交換部Ｂ１３によって交換されたリンクステート情報に基づいて構成される仮想ネットワークのトポロジに対して、トポロジポリシ設定部Ｂ１８に設定されているトポロジポリシと適合するか否かを調べる。そして、適合しない場合は、トポロジの修正を行うべく、仮想ネットワークトポロジ設定部Ｂ１５における隣接ノードの追加・削除を行う。このように動作することにより、ノードの追加・離脱やリンクの追加・削除により仮想ネットワークが複数のセグメントに分断されてしまうなど、トポロジの最適性が損なわれる場合に、事前に設定したトポロジポリシに従って、トポロジを修正することが可能となる。すなわち、ノードの追加・離脱により仮想ネットワークのトポロジが変化したときであっても、仮想ネットワークのトポロジを最適化することができる。
【００８６】
実施形態３．
図１０は、本発明の第３の実施形態のノードを示すブロック図である。図１０に示す本発明の第３の実施形態のノードＣ１，Ｃ２は、ベースネットワークＮ１を介して接続されている。前述の各実施形態と同様に、ベースネットワークＮ１に接続されるノードの数は２つに限定されない。各ノードＣ１，Ｃ２は、仮想ネットワークに属するノードであり、それぞれ同一の構成を有する。そのため、以下、ノードＣ１を例に説明する。
【００８７】
ノードＣ１は、ＤＨＴプロトコル部Ｃ１１と、ツリー配送制御部Ｃ１２と、リンクステート情報交換部Ｃ１３と、リンクステートデータベース記憶部Ｃ１４と、仮想ネットワークトポロジ構成部Ｃ１５と、経路計算部Ｃ１６と、ルーティングテーブル記憶部Ｃ１７と、トポロジポリシ設定部Ｃ１８とを備える。これらの各構成要素のうち、ＤＨＴプロトコル部Ｃ１１と、ツリー配送制御部Ｃ１２と、リンクステート情報交換部Ｃ１３と、リンクステートデータベース記憶部Ｃ１４と、経路計算部Ｃ１６と、ルーティングテーブル記憶部Ｃ１７は、第１の実施形態のノードＡ１（図１参照）におけるＤＨＴプロトコル部Ａ１１、ツリー配送制御部Ａ１２、リンクステート情報交換部Ａ１３、リンクステートデータベース記憶部Ａ１４、経路計算部Ａ１６、ルーティングテーブル記憶部Ａ１７と同様の構成要素であり、説明を省略する。
【００８８】
仮想ネットワークトポロジ構成部Ｃ１５は、リンクステートデータベース記憶部Ｃ１４から渡されたノードのリストおよびトポロジポリシ設定部Ｃ１８において設定されているトポロジポリシに基づいて、仮想ネットワークのトポロジがトポロジポリシを満たすように隣接ノードの設定を行う。本実施形態におけるトポロジポリシは、仮想ネットワークの構成態様を指定する情報である。仮想ネットワークの構成態様として、例えば、フルメッシュトポロジ、リング型トポロジ、スター型トポロジ、ツリー型トポロジ等があり、本実施形態におけるトポロジポリシは、それらの構成態様のいずれかを指定する情報である。仮想ネットワークのトポロジがトポロジポリシを満たすように、仮想ネットワークトポロジ構成部Ｃ１５が隣接ノードの設定を行うことで、仮想ネットワークのトポロジが自動的に構成される。
【００８９】
例えば、トポロジポリシ設定部Ｃ１８において「フルメッシュトポロジ」という仮想ネットワークのポリシが設定されているとする。この場合、仮想ネットワークトポロジ構成部Ｃ１５は、リンクステートデータベース記憶部Ｃ１４において認識している他のノードの全てを隣接ノードとして設定する。すなわち、それらの各ノードを隣接ノードとして、仮想ネットワークトポロジ構成テーブルを設定する。  図１１は、仮想ネットワークトポロジ構成部Ｃ１５において設定される仮想ネットワークトポロジ設定テーブルの例を示す説明図である。トポロジポリシ設定部Ｃ１８において「フルメッシュトポロジ」というトポロジポリシが設定されているとすると、例えば、ノードＩＤ“Ｃ１”のノードの仮想ネットワークトポロジ構成部Ｃ１５は、図１１に例示する仮想ネットワークトポロジ構成テーブル１０３のように、自ノード（ノードＣ１）以外の他の全てのノードに対する隣接ノードのエントリを仮想ネットワークトポロジ構成テーブルに設定する。ただし、ここでは、ノードＣ１は、自ノード以外にノードＣ２〜Ｃ６を認識しているものとする。
【００９０】
また、例えば、トポロジポリシ設定部Ｃ１８において「リング型トポロジ」という仮想ネットワークのポリシが設定されているとする。この場合、仮想ネットワークトポロジ構成部Ｃ１５は、自ノードのノードＩＤと隣り合うノードＩＤを持つ２つのノードに対してそれぞれリンクを設定する（すなわち、その２つのノードを隣接ノードとして、仮想ネットワークトポロジ構成テーブルを設定する）。具体的には、リンクステートデータベース記憶部Ｃ１４によって認識されたノードのうち、自ノードのノードＩＤより大きいノードＩＤを持つノードのうち、最も小さいノードＩＤを持つノードに対して仮想リンクを設定する。また、自ノードのノードＩＤより小さいノードＩＤを持つノードのうち、最も大きいノードＩＤを持つノードに対して仮想リンクを設定する。
【００９１】
また、例えば、トポロジポリシ設定部Ｃ１８において「スター型トポロジ」という仮想ネットワークのポリシが設定されているとする。スター型トポロジは、ある特定のノードを中心として放射状に構成されるトポロジであり、この場合、中心となる特定のノードの仮想ネットワークトポロジ構成部Ｃ１５は、リンクステートデータベース記憶部Ｃ１４によって認識された他の全てのノードに対してリンクを設定する（その各ノードを隣接ノードとして仮想ネットワークトポロジ構成テーブルを設定する）。また、中心となる特定のノード以外の各ノードの仮想ネットワークトポロジ構成部Ｃ１５は、その特定のノードに対してリンクを設定する（特定のノードを隣接ノードとして仮想ネットワークトポロジ構成テーブルを設定する）。
【００９２】
また、例えば、トポロジポリシ設定部Ｃ１８において「ツリー型トポロジ」という仮想ネットワークのポリシが設定されているとする。ツリー型トポロジは、ある特定のノードを頂点とし、その他のノードが階層的に枝分かれしながら接続される構成のトポロジであり、この場合、仮想ネットワークトポロジ構成部Ｃ１５は、リンクステートデータベース記憶部Ｃ１４によって認識されたノードのうち、自ノードの上位階層のノードおよび下位階層のノードとリンクを設定する。すなわち、上位階層のノードおよび下位階層のノードを隣接ノードとして仮想ネットワークトポロジ構成テーブルを設定する。
【００９３】
なお、スター型トポロジにおいて中心となる特定のノードや、ツリー型トポロジにおいて頂点となる特定のノードは、事前に定めておけばよい。あるいは、最大または最小のノードＩＤ（ＩＰアドレスでもよい。）を持つノードを特定のノードとしてもよい。
【００９４】
トポロジポリシ設定部Ｃ１８には、仮想ネットワークトポロジ構成部Ｃ１５において自動的に構成される仮想ネットワークのトポロジ構成指針（トポロジポリシ）が設定されている。換言すれば、トポロジポリシ設定部Ｃ１８は、予め定められたトポロジポリシを記憶する。トポロジポリシの例として、フルメッシュトポロジ、リング型トポロジ、スター型トポロジ、ツリー型トポロジなどが挙げられる。既に説明したように、例えば、フルメッシュトポロジが設定される場合、リンクステートデータベース記憶部Ｃ１４によって認識された他ノードの全てに対して仮想リンクを設定するように隣接ノードの設定がなされる。また例えば、リング型トポロジが設定される場合、リンクステートデータベース記憶部Ｃ１４によって認識されている他のノードのうち、自ノードと隣り合うノードＩＤを有するノード（すなわち自ノードのＩＤより大きいＩＤをもつノードのうち、最も小さいＩＤをもつノードと、自ノードのＩＤより小さいＩＤをもつノードのうち、最も大きいＩＤをもつノード）に対してそれぞれ仮想リンクを設定するように隣接ノードの設定がなされる。
【００９５】
図１２は、第３の実施形態における制御メッセージ用トポロジと仮想ネットワークトポロジとの関係の例を示す説明図である。図１２に示す例では、仮想ネットワークトポロジとしてリング型トポロジが構成される場合の制御メッセージ用トポロジと仮想ネットワークトポロジとの関係を示している。各ノードＣ１〜Ｃ６のトポロジポリシ設定部Ｃ１８に「リング型トポロジ」が設定されているとすると、各ノードの仮想ネットワークトポロジ構成部Ｃ１５がそのトポロジポリシに応じて隣接ノードを設定し、図１２に例示する仮想ネットワークトポロジＴ２３のように、ノードＩＤの並びでリング型トポロジが構成される。
【００９６】
次に、動作について説明する。
図１３は、本発明の第３の実施形態のノードがリンクステート情報を受信した際の動作の例を示す説明図である。ノードＣ１を例にして動作を説明する。
【００９７】
第１の実施形態と同様の処理については、図４と同一の符号を付し、説明を省略する。すなわち、図１３に示すステップＳ１０１〜Ｓ１０５およびステップＳ１０７〜Ｓ１０９の動作は、第１の実施形態における動作（図４参照）と同様の動作である。
【００９８】
本実施形態では、ステップＳ１０５においてノードのリストに変化があると判定した場合（ステップＳ１０５のＹｅｓ）、仮想ネットワークトポロジ構成部Ｃ１５は、トポロジポリシ設定部Ｃ１８に設定されているトポロジポリシを参照する（ステップＳ３０６）。換言すれば、トポロジポリシ設定部Ｃ１８を参照し、自動的に構成すべきトポロジの形状に対するポリシを調べる。
【００９９】
次に、仮想ネットワークトポロジ構成部Ｃ１５は、参照したトポロジポリシに適合するように仮想ネットワークトポロジ構成テーブルの更新を行う（ステップＳ３０７）。例えば、フルメッシュトポロジというトポロジポリシが設定されているとする。また、ステップＳ１０５においてノードの追加が検出されたとする。この場合、仮想ネットワークトポロジ構成部Ｃ１５は、検出されたノードに対する仮想リンクを構成するための隣接ノード設定エントリを仮想ネットワークトポロジ設定テーブルに追加する。また、あるノードの離脱が検出された場合、仮想ネットワークトポロジ構成部Ｃ１５は、検出されたノードに対する隣接ノード設定エントリを、仮想ネットワークトポロジ設定テーブルから削除する。
【０１００】
ステップＳ３０７の後、更新された仮想ネットワークトポロジ構成テーブルに基づくリンクステート情報の送信など、ステップＳ１０７〜Ｓ１０９の処理を行う。
【０１０１】
次に本実施形態の効果について説明する。
本実施形態では、第１の実施形態と同様の効果を得ることができる。また、リンクステートデータベース記憶部Ｃ１４によって認識されたノードのリストに基づいて、仮想ネットワークトポロジ構成部Ｃ１５が、トポロジポリシ設定部Ｃ１８に設定されているトポロジポリシに応じて隣接ノードの設定を行う。このように動作することにより、ノードの追加・離脱などが発生しても自動的に事前に設定したトポロジポリシに従ってトポロジが再構成され、仮想ネットワークのトポロジの最適化を図ることができる。
【０１０２】
実施形態４．
図１４は、本発明の第４の実施形態のノードを示すブロック図である。図１４に示す本発明の第４の実施形態のノードＤ１，Ｄ２は、ベースネットワークＮ１を介して接続されている。前述の各実施形態と同様に、ベースネットワークＮ１に接続されるノードの数は２つに限定されない。各ノードＤ１，Ｄ２は、仮想ネットワークに属するノードであり、それぞれ同一の構成を有する。そのため、以下、ノードＤ１を例に説明する。
【０１０３】
ノードＤ１は、ＤＨＴプロトコル部Ｄ１１と、ツリー配送制御部Ｄ１２と、リンクステート情報交換部Ｄ１３と、リンクステートデータベース記憶部Ｄ１４と、仮想ネットワークトポロジ構成部Ｄ１５と、経路計算部Ｄ１６と、ルーティングテーブル記憶部Ｄ１７と、トポロジポリシ設定部Ｄ１８とを備える。これらの構成要素のうち、ＤＨＴプロトコル部Ｄ１１と、ツリー配送制御部Ｄ１２と、リンクステート情報交換部Ｄ１３と、リンクステートデータベース記憶部Ｄ１４は、第３の実施形態のノードＣ１（図１参照）におけるＤＨＴプロトコル部Ｃ１１、ツリー配送制御部Ｃ１２、リンクステート情報交換部Ｃ１３、リンクステートデータベース記憶部Ｃ１４と同様の構成要素であり、説明を省略する。
【０１０４】
仮想ネットワークトポロジ構成部Ｄ１５は、リンクステートデータベース記憶部Ｄ１４から渡されたノードのリストおよびトポロジポリシ設定部Ｄ１８において設定されているトポロジポリシに基づいて複数の仮想ネットワークのトポロジを自動的に構成する機能を有する。本実施形態では、トポロジポリシ設定部Ｄ１８には複数の仮想ネットワークを構成するためのトポロジポリシが設定されており、仮想ネットワークトポロジ構成部Ｄ１５は、それぞれの仮想ネットワークのトポロジポリシに基づいて隣接ノードの設定を行う。個々の仮想ネットワークごとの隣接ノード設定の方法は、図１０のトポロジポリシ設定部Ｃ１８において説明した方法と同様である。
【０１０５】
経路計算部Ｄ１６は、リンクステートデータベース記憶部Ｄ１４によって認識された、各仮想ネットワークのリンクステート情報を用いて、各仮想ネットワーク内の各ノードへ到達するための次ホップまたは経路全体を計算し、経路エントリとしてルーティングテーブル記憶部Ｄ１７へ登録する。すなわち、経路計算部Ｄ１６は、仮想ネットワーク単位で経路計算を行い、その結果導出した次ホップまたは経路全体をルーティングテーブル記憶部Ｄ１７に登録する。個々の仮想ネットワークごとに経路計算部Ｄ１６が行う処理は、第１の実施形態における経路計算部Ａ１６の処理と同様の処理でよい。また、経路計算部Ｄ１６は、各仮想ネットワークごとに異なる経路計算アルゴリズムで経路計算を行ってもよい。
【０１０６】
ルーティングテーブル記憶部Ｄ１７は、各仮想ネットワークごとにルーティングテーブルを記憶し、経路計算部Ｄ１６によって計算された各仮想ネットワークごとの経路エントリの登録を受け付ける。各仮想ネットワークごとの個々のルーティングテーブルは、第１の実施形態のルーティングテーブル記憶部Ａ１７におけるルーティングテーブルと同様である。
【０１０７】
トポロジポリシ設定部Ｄ１８は、複数の仮想ネットワークを構成するためのトポロジポリシが設定されている。図１５は、トポロジポリシ設定部Ｄ１８に設定されるトポロジポリシの例を示す。本実施形態におけるトポロジポリシは、第３の実施形態におけるトポロジポリシと同様に、仮想ネットワークの構成態様を指定する情報である。ただし、複数種類の各仮想ネットワークごとにトポロジポリシが設定される点で、第３の実施形態と異なる。図１５に示す例では、３つの仮想ネットワーク（仮想ネットワークＸ，Ｙ，Ｚ）に対応するトポロジポリシが設定されている。具体的には、仮想ネットワークＸに対応してフルメッシュトポロジが設定され、仮想ネットワークＹに対応してリング型トポロジが設定され、仮想ネットワークＺにはノードＤ１を中心とするスタートポロジを構成するとして設定がなされている。
【０１０８】
本実施形態では、トポロジポリシ設定部Ｄ１８において複数の仮想ネットワークごとにトポロジポリシが設定され、各仮想ネットワークごとに仮想ネットワークトポロジ構成テーブルの設定、および経路計算を実行する点が、第３の実施形態と異なる。他の点については、第３の実施形態と同様である。
【０１０９】
また、本実施形態では、ＤＨＴプロトコル部Ｄ１１は、分散ハッシュテーブルにおける隣接ノードの死活監視を行う。この動作は、第１の実施形態におけるＤＨＴプロトコル部Ａ１１と同様の動作である。そして、ＤＨＴプロトコル部Ｄ１１が、複数の仮想ネットワークのうちいずれか１つ以上の仮想ネットワークに属するノードの離脱を検出した場合、ツリー配送制御部Ｄ１２は、複数の仮想ネットワークのそれぞれに対する隣接ノードの設定に基づいて、仮想ネットワーク毎に個別にリンクステート情報をリンクステート情報交換部Ｄ１３に広告させる。このリンクステート情報を受信したノードは、各仮想ネットワークごとに仮想ネットワークトポロジ構成テーブルの設定、および経路計算を実行する。このように、ＤＨＴプロトコル部Ｄ１１は、ノードの死活監視を仮想ネットワーク毎ではなく共通的に行う。
【０１１０】
次に本実施形態の効果について説明する。
本実施形態では、第１の実施形態と同様の効果を得ることができる。また、リンクステートデータベース記憶部Ｄ１４によって認識されたノードのリストに基づき、仮想ネットワークトポロジ構成部Ｄ１５が、トポロジポリシ設定部Ｄ１８に設定されているトポロジポリシに応じて複数種類のそれぞれの仮想ネットワークごとに隣接ノードの設定を行う。すなわち、隣接ノードの設定を仮想ネットワーク単位で行い、結果的に複数の仮想ネットワークのそれぞれに対応するルーティングテーブルを作成することになる。このように動作することにより、異なるトポロジポリシをもつ複数の仮想ネットワークの構成を、ノードの追加・離脱などに追随して自動的に行うことができる。
【０１１１】
また、複数の仮想ネットワークを構成する場合において、それぞれの仮想ネットワークごとにＨｅｌｌｏメッセージによるノードの死活監視を行うとすると、仮想ネットワークの数に比例したトラフィックが発生してしまう。それに対し、本実施形態では、ノードの死活監視はＤＨＴプロトコル部Ｄ１１が共通的に行う。そのため、ノードの死活監視に必要なトラフィック量は仮想ネットワークの数に比例させずに一定に抑えることができる。
【０１１２】
上記の各実施形態において、ＤＨＴプロトコル部、ツリー配送制御部、リンクステート情報交換部、リンクステートデータベース記憶部、仮想ネットワークトポロジ設定部、経路計算部は、例えば、プログラム経路制御プログラムに従って動作するＣＰＵによって実現されていてもよい。また、ルーティングテーブル記憶部およびトポロジポリシ設定部は、例えば、コンピュータが備える記憶装置によって実現されていてもよい。
【０１１３】
次に、本発明の概要について説明する。図１６は、本発明の概要を示すブロック図である。本発明のノードは、ベースネットワーク上に設けられる仮想ネットワークに属し、リンクステート型ルーティングプロトコルによる仮想ネットワークの経路制御を行うノードである。そして、本発明のノードは、図１６に示すように、分散ハッシュテーブル生成手段７１と、リンクステート情報交換手段７２と、ツリー配送制御手段７３とを備える。
【０１１４】
分散ハッシュテーブル生成手段７１（例えば、ＤＨＴプロトコル部Ａ１１によって実現される。）は、メッセージを転送すべき次のノードを示す分散ハッシュテーブルを、リンクステート型ルーティングプロトコルを用いて生成する。
【０１１５】
リンクステート情報交換手段７２（例えば、リンクステート情報交換部Ａ１３によって実現される。）は、自ノードに関するノード情報と、隣接ノードとの各リンクに関する情報であるリンク情報とを含む情報であるリンクステート情報を送受信する。
【０１１６】
ツリー配送制御手段７３（例えば、ツリー配送制御部Ａ１２によって実現される。）は、リンクステート情報がそのリンクステート情報の送信元ノードをルートとするツリーに沿って配送されるようにリンクステート情報の転送先を定める。このように、リンクステート情報の転送先を定めるのでリンクステート情報のトラフィック量を抑えることができる。
【０１１７】
また、リンクステート型ルーティングプロトコルが、Ｃｈｏｒｄであり、ツリー配送制御手段７３が、Ｃｈｏｒｄ  Ｂｒｏａｄｃａｓｔにおけるブロードキャストツリーに沿ってリンクステート情報が転送されるようにリンクステート情報の転送先を定めてもよい。
【０１１８】
また、仮想ネットワークに属するノードの死活監視を行う死活監視手段（例えば、ＤＨＴプロトコル部Ａ１１によって実現される。）を備え、リンクステート情報交換手段７２が、仮想ネットワークに属するノードの離脱が検出されたときに、そのノードの離脱を示すリンクステート情報を送信してもよい。
【０１１９】
また、リンクステート情報交換手段７２が受信したリンクステート情報によって、そのリンクステート情報を送信したノードを認識するノード認識手段（例えば、リンクステートデータベース記憶部Ａ１４によって実現される。）と、仮想ネットワークに属する隣接ノードが設定されたテーブルを予め保持し、そのテーブルに設定された隣接ノードのうち、ノード認識手段が認識したノードを生存中の隣接ノードとして設定するテーブル設定手段（例えば、仮想ネットワークトポロジ構成部Ａ１５によって実現される。）とを備え、リンクステート情報交換手段７２が、生存中の隣接ノードの情報を含むリンクステート情報を送信してもよい。
【０１２０】
また、仮想ネットワークのトポロジに対する指針であるトポロジポリシを保持するトポロジポリシ保持手段（例えば、トポロジポリシ設定部Ｂ１８）と、仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、受信したリンクステート情報に含まれるノード情報およびリンク情報がトポロジポリシに合致しない場合、そのテーブルにおける隣接ノードの設定を、トポロジポリシに合致するように修正するテーブル設定手段（例えば、仮想ネットワークトポロジ設定部Ｂ１５によって実現される。）とを備え、リンクステート情報交換手段７２が、修正後のテーブルに設定された隣接ノードの情報を含むリンクステート情報を送信してもよい。
【０１２１】
また、リンクステート情報交換手段７２が受信したリンクステート情報によって、仮想ネットワークに属するノードを認識するノード認識手段（例えば、リンクステートデータベース記憶部Ｃ１４によって実現される。）と、仮想ネットワークの構成態様を指定する情報である態様指定情報を保持する態様指定情報保持手段（例えばトポロジポリシ設定部Ｃ１８によって実現される。）と、仮想ネットワークに属する隣接ノードが設定されたテーブルを保持し、ノード認識手段が仮想ネットワークに属するノードを認識したときに、態様指定情報が指定する構成態様を満たすように、そのテーブルにおける隣接ノードの設定を修正するテーブル設定手段（例えば、仮想ネットワークトポロジ設定部Ｃ１５によって実現される。）とを備え、リンクステート情報交換手段７２が、修正後のテーブルに設定された隣接ノードの情報を含むリンクステート情報を送信してもよい。
【０１２２】
また、態様指定情報保持手段（例えばトポロジポリシ設定部Ｃ１８）が、仮想ネットワークの構成態様としてフルメッシュトポロジを指定する態様指定情報を保持し、テーブル設定手段が、ノード認識手段が認識した各ノードを隣接ノードとしてテーブルに設定してもよい。
【０１２３】
また、態様指定情報保持手段（例えばトポロジポリシ設定部Ｃ１８）が、仮想ネットワークの構成態様としてリング型トポロジを指定する態様指定情報を保持し、テーブル設定手段が、自ノードのノードＩＤより大きいノードＩＤを持つノードのうち、最も小さいノードＩＤを持つノードと、自ノードのノードＩＤより小さいノードＩＤを持つノードのうち、最も大きいノードＩＤを持つノードとを隣接ノードとしてテーブルに設定してもよい。
【０１２４】
また、態様指定情報保持手段（例えばトポロジポリシ設定部Ｃ１８）が、仮想ネットワークの構成態様としてスター型トポロジを指定する態様指定情報を保持し、テーブル設定手段が、自ノードがスター型トポロジの中心となる特定のノードであるならば、ノード認識手段が認識した各ノードを隣接ノードとしてテーブルに設定し、自ノードがスター型トポロジの中心となる特定のノードでないならば、その特定のノードを隣接ノードとしてテーブルに設定してもよい。
【０１２５】
また、態様指定情報保持手段（例えばトポロジポリシ設定部Ｃ１８）が、仮想ネットワークの構成態様としてツリー型トポロジを指定する態様指定情報を保持し、テーブル設定手段が、ノード認識手段が認識したノードのうち、自ノードの上位階層のノードおよび下位階層のノードを隣接ノードとしてテーブルに設定してもよい。
【０１２６】
また、ノード認識手段が認識したノードが属する仮想ネットワーク上の経路計算を行う経路計算手段（例えば、経路計算部Ｄ１６によって実現される。）を備え、テーブル設定手段が、複数の仮想ネットワークそれぞれに対応する複数のテーブルを保持し、態様指定情報保持手段が、個々の仮想ネットワーク毎の態様指定情報を保持し、テーブル設定手段が、個々の仮想ネットワーク毎に、その仮想ネットワークに対して定められた態様指定情報に応じて、その仮想ネットワークに対応するテーブルを設定し、経路計算手段が、個々の仮想ネットワーク毎に経路計算を行ってもよい。
【０１２７】
また、仮想ネットワークに属するノードの死活監視を行う死活監視手段（例えば、ＤＨＴプロトコル部Ｄ１１によって実現される。）を備え、リンクステート情報交換手段は、仮想ネットワークに属するノードの離脱が検出されたときに、個々の仮想ネットワーク毎に、そのノードの離脱を示すリンクステート情報を送信してもよい。
【産業上の利用可能性】
【０１２８】
本発明は、例えば、ＶＰＮ(Virtual Private Network )やオーバレイネットワーク等のような、仮想ネットワークに属するノードに好適に適用される。
【図面の簡単な説明】
【０１２９】
【図１】本発明の第１の実施形態のノードを示すブロック図である。
【図２】本発明の第１の実施形態で設定される仮想ネットワークトポロジ設定テーブルの例を示す説明図である。
【図３】本発明の第１の実施形態における制御メッセージ用トポロジと仮想ネットワークトポロジとの関係を示す説明図である。
【図４】本発明の第１の実施形態のノードの動作の例を示すフローチャートである。
【図５】本発明の第２の実施形態のノードを示すブロック図である。
【図６】本発明の第２の実施形態で設定される仮想ネットワークトポロジ設定テーブルの例を示す説明図である。
【図７】本発明の第２の実施形態で設定されるトポロジポリシの例を示す説明図である。
【図８】本発明の第２の実施形態における制御メッセージ用トポロジと仮想ネットワークトポロジとの関係の例を示す説明図である。
【図９】本発明の第２の実施形態のノードの動作の例を示すフローチャートである。
【図１０】本発明の第３の実施形態のノードを示すブロック図である。
【図１１】本発明の第３の実施形態で設定される仮想ネットワークトポロジ設定テーブルの例を示す説明図である。
【図１２】第３の実施形態における制御メッセージ用トポロジと仮想ネットワークトポロジとの関係の例を示す説明図である。
【図１３】本発明の第３の実施形態のノードの動作の例を示すフローチャートである。
【図１４】本発明の第４の実施形態のノードを示すブロック図である。
【図１５】本発明の第４の実施形態で設定されるトポロジポリシの例を示す。
【図１６】本発明の概要を示すブロック図である。
【符号の説明】
【０１３０】
Ａ１，Ａ２  ノード
Ａ１１  ＤＨＴプロトコル部
Ａ１２  ツリー配送制御部
Ａ１３  リンクステート情報交換部
Ａ１４  リンクステートデータベース記憶部
Ａ１５  仮想ネットワークトポロジ設定部
Ａ１６  経路計算部
Ａ１７  ルーティングテーブル記憶部
７１  分散ハッシュテーブル生成手段
７２  リンクステート情報交換手段
７３  ツリー配送制御手段
【図１】
0005029373.tif 000002
【図２】
0005029373.tif 000003
【図３】
0005029373.tif 000004
【図４】
0005029373.tif 000005
【図５】
0005029373.tif 000006
【図６】
0005029373.tif 000007
【図７】
0005029373.tif 000008
【図８】
0005029373.tif 000009
【図９】
0005029373.tif 000010
【図１０】
0005029373.tif 000011
【図１１】
0005029373.tif 000012
【図１２】
0005029373.tif 000013
【図１３】
0005029373.tif 000014
【図１４】
0005029373.tif 000015
【図１５】
0005029373.tif 000016
【図１６】
0005029373.tif 000017