(57)【要約】  本願の課題は、候補として選択したリンクの追加・削除の判断をする際に、ネットワーク内の全ノードのコストの合計値への影響を精度よく反映したリンクの追加・削除の判断が可能な技術を提供することである。本願は、複数のノードを有するネットワークのトポロジを生成するトポロジ生成方法であって、追加又は削除するリンクを選択し、この選択したリンクがある場合と無い場合との前記ネットワーク上のノードのコストを算出する算出ステップと、前記算出したコストを比較し、この比較結果に応じて前記選択したリンクを追加又は削除するかを決定する決定ステップとを有することを特徴とする。
2011152456.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードを有するネットワークのトポロジを生成するトポロジ生成方法であって、
追加又は削除するリンクを選択し、この選択したリンクがある場合と無い場合との前記ネットワーク上のノードのコストを算出する算出ステップと、
前記算出したコストを比較し、この比較結果に応じて前記選択したリンクを追加又は削除するかを決定する決定ステップと
を有することを特徴とするトポロジ生成方法。
【請求項２】
前記決定ステップは、少なくとも、前記選択したリンクの接続元ノードと接続先ノードとにおける、前記リンクがある場合と無い場合とのコストを比較することを特徴とする請求項１に記載のトポロジ生成方法。
【請求項３】
前記決定ステップは、前記選択したリンクの接続元ノード及び前記接続元ノードから所定数ホップ以内にあるノードと、前記選択したリンクの接続先ノード及び前記接続先ノードから所定数ホップ以内にあるノードとにおける、前記リンクがある場合と無い場合とのコストを比較することを特徴とする請求項２に記載のトポロジ生成方法。
【請求項４】
複数のノードを有するネットワークのトポロジを生成するトポロジ生成システムであって、
追加又は削除するリンクを選択し、この選択したリンクがある場合と無い場合との前記ネットワーク上のノードのコストを算出する算出手段と、
前記算出したコストを比較し、この比較結果に応じて前記選択したリンクを追加又は削除するかを決定する決定手段と
を有することを特徴とするトポロジ生成システム。
【請求項５】
前記決定手段は、少なくとも、前記選択したリンクの接続元ノードと接続先ノードとにおける、前記リンクがある場合と無い場合とのコストを比較することを特徴とする請求項４に記載のトポロジ生成システム。
【請求項６】
前記決定手段は、前記選択したリンクの接続元ノード及び前記接続元ノードから所定数ホップ以内にあるノードと、前記選択したリンクの接続先ノード及び前記接続先ノードから所定数ホップ以内にあるノードとにおける、前記リンクがある場合と無い場合とのコストを比較することを特徴とする請求項５に記載のトポロジ生成システム。
【請求項７】
複数のノードを有するネットワークのトポロジを生成するトポロジ生成システムのノードであって、
追加又は削除するリンクを選択し、この選択したリンクがある場合と無い場合とにおける自ノードのコストを算出する算出手段と、
前記選択したリンクがある場合と無い場合との前記ネットワーク上のノードのコストを収集する収集手段と、
前記算出したコストと前記収集したコストとを用いて、前記選択したリンクがある場合と無い場合とを比較し、この比較結果に応じて前記選択したリンクを追加又は削除するかを決定する決定手段と
を有することを特徴とするトポロジ生成システム。
【請求項８】
前記決定手段は、少なくとも、自ノードと前記収集手段が収集した接続先ノードとにおける、前記リンクがある場合と無い場合とのコストを比較することを特徴とする請求項７に記載のトポロジ生成システム。
【請求項９】
前記決定手段は、前記算出した自ノードのコストと、自ノードから所定数ホップ以内にあるノードから収集したコストと、前記選択したリンクの接続先ノードから収集した、前記接続先におけるコスト及び前記接続先ノードから所定数ホップ以内にあるノードのコストとを用いて、前記リンクがある場合と無い場合とのコストを比較することを特徴とする請求項８に記載のトポロジ生成システム。
【請求項１０】
複数のノードを有するネットワークのトポロジを生成するトポロジ生成システムのノードのプログラムであって、前記プログラムは前記ノードを、
追加又は削除するリンクを選択し、この選択したリンクがある場合と無い場合とにおける自ノードのコストを算出する算出手段と、
前記選択したリンクがある場合と無い場合との前記ネットワーク上のノードのコストを収集する収集手段と、
前記算出したコストと前記収集したコストとを用いて、前記選択したリンクがある場合と無い場合とを比較し、この比較結果に応じて前記選択したリンクを追加又は削除するかを決定する決定手段と
して機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ポロジ生成方法、トポロジ生成システム、ノードおよびプログラムに関する。
【背景技術】
【０００２】
ルータやスイッチなどのネットワークノードが他のネットワークノードへのリンクを追加したり削除したりしながら、自律分散的にネットワークトポロジを構成するいくつかの方法が開示されている。【０００３】
例えば、オーバレイネットワークにおいて、各ノードがあるコスト関数を最小化するようにリンクを追加・削除する手順を繰り返すことによって、最終的にどのようなトポロジに収束するかが調べられている（例えば非特許文献１）。
以下に具体的に説明する。【０００４】
非特許文献１では、ノードｉにおけるコスト関数Ｃｉとして、（１）式が用いられる。
Ｃｉ＝αΣｔｊ＋Σｄ（ｉ，ｊ）  （１）【０００５】
ここで、右辺の第１項目は、隣接ノードｊへリンクをつくるためのコストｔｊを各隣接ノードについて合計した値に係数αを乗じた値である。また、第２項目は、オーバレイネットワーク内のノードｊへのホップ数ｄ（ｉ，ｊ）を各ノードについて合計した値である。第１項目の値と第２項目の値とを係数αにより重み付けして足し合わせた値をＣｉとしている。【０００６】
ここで、簡略化したケースとして、ｔｊを常に１とすることにより、第１項目をノードｉにおけるｄｅｇｒｅｅ（ノードｉにおけるリンク数）にαを乗じた値として取り扱うことにする。【０００７】
各ノードは、以下の１と２との手順を行い、この手順をノード１からノードｎまで順番に繰り返す。
１．ランダムに現在非隣接のノードｊを選び、ノードｊが隣接した場合のコストと現在のコストとを比較し、隣接した場合のコストの方が小さければノードｊに対してリンクを追加
２．現在隣接しているノードの各々（ノードｊ）に対し、ノードｊが非隣接になった場合のコストと現在のコストとを比較し、非隣接になったコストの方が小さければノードｊへのリンクを削除【０００８】
上記手順を各ノードが繰り返すことにより、どのノードもこれ以上リンクを追加または削除してもコストを小さくすることができない状態（ナッシュ均衡状態）でのトポロジを収束トポロジと呼ぶことにする。収束トポロジは、αの値や、ｔｊの関数の取り方、ｄ（ｉ，ｊ）の取り方などによって異なり、非特許文献１ではその特徴について調べられている。また、ノードｉにおけるコストＣｉを各ノードについて合計した値（ΣＣｉ）が最小化される状態のことをグローバル最適（文献中ではsocial optimum）と呼ぶ。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Byung-Gon Chun, Rodrigo Fonseca, Ion Stoica and John Kubiatowicz,"Characterizing Selfishly Constructed Overlay Routing Networks,"Proceedings in the IEEE Infocom 2004, Hong Kong, China, March 2004.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述のネットワークトポロジ制御方法は、以下に挙げる問題がある。【００１１】
グローバル最適となるトポロジと、収束トポロジとは必ずしも一致しない。
また、過渡状態において、グローバル最適からは遠ざかることになるリンクの追加・削除手順が行われることがある。すなわち、各ノードにおけるコストの合計値（ΣＣｉ）が大きくなるようなリンクの追加・削除が行われる。これはトポロジの収束を遅らせるばかりか、収束トポロジがグローバル最適ではなくなることの一因となる。【００１２】
上記の現象が発生する理由は、各ノードが自ノードｉのコスト関数Ｃｉだけを最小化するようにリンクを追加または削除するからである。グローバル最適からは遠ざかることになるリンクの追加・削除の例を図１および図２に示す。【００１３】
図１を参照すると、ノードＡ〜Ｅの５ノードから構成されるオーバレイネットワークが示されている。コスト関数として、
Ｃｉ＝２×（ノードｉにおけるｄｅｇｒｅｅ）＋（ノードｉから他のノードへのホップ数の合計）
を用いるものとする。【００１４】
初期状態として、図１の「（１）初期状態」に示すトポロジであるものとする。次に、ノードＡがリンクを上記のコスト関数Ｃｉに基づいて追加または削除を行おうとする。初期状態において、ノードＡのコストＣＡは、ｄｅｇｒｅｅ：２、合計ホップ数：７であるため、ＣＡ＝１１である。【００１５】
次に、ノードＡは、現在隣接していないノードのなかからランダムに選ばれたノードを選び、そのノードに対してリンクを追加することによりコストが小さくなるかどうかを調べる。ここでは、ノードＥが選ばれるとする。【００１６】
ノードＡがノードＥにリンクを追加した場合、ノードＡのコストＣＡは、ｄｅｇｒｅｅ：３、合計ホップ数：５となるため、ＣＡ＝１１となる。これは、初期状態におけるコスト（１１）よりも小さくならないため、ノードＡはノードＥに対してリンクを追加する必要がないと判断し、リンクを追加しない。【００１７】
しかしながら、ネットワーク全体で見ると、リンクを追加した場合は、ノードＡ〜Ｅのコストの合計値ΣＣｉは５２となり、初期状態におけるコストの合計値ΣＣｉである５４よりも小さくなっている。したがって、グローバル最適化を考えると、ノードＡはノードＥへリンクした方がネットワーク全体のコストを小さくできたということがわかる。【００１８】
別の例として、図２を参照すると、ノードＡ〜Ｅの５ノードから構成されるオーバレイネットワークが示されている。コスト関数として、
Ｃｉ＝４．５×（ノードｉにおけるｄｅｇｒｅｅ）＋（ノードｉから他のノードへのホップ数の合計）
を用いるものとする。【００１９】
初期状態として、図２の「（１）初期状態」に示すトポロジであるものとする。次に、ノードＡがリンクを上記のコスト関数Ｃｉに基づいて追加または削除を行おうとする。初期状態において、ノードＡのコストＣＡは、ｄｅｇｒｅｅ：１、合計ホップ数：１０であるため、ＣＡ＝１４．５である。【００２０】
次に、ノードＡは、現在隣接していないノードのなかからランダムに選ばれたノードを選び、そのノードに対してリンクを追加することによりコストが小さくなるかどうかを調べる。ここでは、ノードＥが選ばれるとする。【００２１】
ノードＡがノードＥにリンクを追加した場合、ノードＡのコストＣＡは、ｄｅｇｒｅｅ：２、合計ホップ数：６となるため、ＣＣ＝１５となる。これは、初期状態におけるコスト（１４．５）よりも小さくならないため、ノードＡはノードＥに対してリンクを追加する必要がないと判断し、リンクを追加しない。【００２２】
しかしながら、ネットワーク全体で見ると、リンクを追加した場合は、ノードＡ〜Ｅのコストの合計値ΣＣｉは７５となり、初期状態におけるコストの合計値ΣＣｉである７６よりも小さくなっている。したがって、グローバル最適化を考えると、ノードＡはノードＥへリンクした方がネットワーク全体のコストを小さくできたということがわかる。【００２３】
そればかりか、詳しく調べてみると、図２の場合は、（１）初期状態の直線状のトポロジでナッシュ均衡となっている。しかしながら、上記の記述より、このトポロジよりもコストが小さくなるトポロジが存在するのは明らかなため、初期状態のトポロジがグローバル最適ではないことがわかる。【００２４】
以上より、上述のネットワークトポロジ制御方法では、グローバル最適となるトポロジが必ずしも得られないという問題があった。このような状況は、上記の例とは異なるコスト関数を用いた場合や、各ノードにおいて用いるコスト関数が異なる場合などは、より頻繁に発生することがある。【００２５】
そこで、本発明が解決しようとする課題は、上記問題点を解決することであり、候補として選択したリンクの追加・削除の判断をする際に、ネットワーク内の全ノードのコストの合計値への影響を精度よく反映したリンクの追加・削除の判断が可能な技術を提供することである。
【課題を解決するための手段】
【００２６】
上記課題を解決するための第１の発明は、複数のノードを有するネットワークのトポロジを生成するトポロジ生成方法であって、追加又は削除するリンクを選択し、この選択したリンクがある場合と無い場合との前記ネットワーク上のノードのコストを算出する算出ステップと、前記算出したコストを比較し、この比較結果に応じて前記選択したリンクを追加又は削除するかを決定する決定ステップとを有することを特徴とする。【００２７】
上記課題を解決するための第２の発明は、複数のノードを有するネットワークのトポロジを生成するトポロジ生成システムであって、追加又は削除するリンクを選択し、この選択したリンクがある場合と無い場合との前記ネットワーク上のノードのコストを算出する算出手段と、前記算出したコストを比較し、この比較結果に応じて前記選択したリンクを追加又は削除するかを決定する決定手段とを有することを特徴とする。【００２８】
上記課題を解決するための第３の発明は、複数のノードを有するネットワークのトポロジを生成するトポロジ生成システムのノードであって、追加又は削除するリンクを選択し、この選択したリンクがある場合と無い場合とにおける自ノードのコストを算出する算出手段と、前記選択したリンクがある場合と無い場合との前記ネットワーク上のノードのコストを収集する収集手段と、前記算出したコストと前記収集したコストとを用いて、前記選択したリンクがある場合と無い場合とを比較し、この比較結果に応じて前記選択したリンクを追加又は削除するかを決定する決定手段とを有することを特徴とする。【００２９】
上記課題を解決するための第４の発明は、複数のノードを有するネットワークのトポロジを生成するトポロジ生成システムのノードのプログラムであって、前記プログラムは前記ノードを、追加又は削除するリンクを選択し、この選択したリンクがある場合と無い場合とにおける自ノードのコストを算出する算出手段と、前記選択したリンクがある場合と無い場合との前記ネットワーク上のノードのコストを収集する収集手段と、前記算出したコストと前記収集したコストとを用いて、前記選択したリンクがある場合と無い場合とを比較し、この比較結果に応じて前記選択したリンクを追加又は削除するかを決定する決定手段として機能させることを特徴とする。
【発明の効果】
【００３０】
本発明の効果は、リンクを追加・削除しながらトポロジを変更するにあたって、候補として選択したリンクの追加・削除の判断をする際に、ネットワーク内の全ノードのコストの合計値への影響を精度よく反映させたリンクの追加・削除の判断ができる。
【図面の簡単な説明】
【００３１】
【図１】コストに基づくリンク追加・削除の例を示す図
【図２】コストに基づくリンク追加・削除の例を示す図
【図３】本発明の第１の実施の形態を示す全体図
【図４】本発明の第１の実施の形態の構成を示すブロック図
【図５】本発明の第１の実施の形態におけるノード・リンクＤＢの例
【図６】本発明の第１の実施の形態におけるインターフェースリストの例
【図７】本発明の第１の実施の形態の動作を示す流れ図
【図８】本発明の第１の実施の形態の構成を示すブロック図
【図９】本発明の第２の実施の形態の動作を示す流れ図
【発明を実施するための形態】
【００３２】
本発明の特徴を説明するために、以下において、図面を参照して具体的に述べる。
【００３３】
〈第１の実施の形態〉
本発明を実施するための第１の実施の形態について図面を参照して詳細に説明する。
【００３４】
図３を参照すると、本発明の第１の実施の形態は、ノードと、リンクと、ベースネットワークとから構成されるネットワークシステムである。下記の説明では、ノードＡ１〜Ａ４、リンクＣ１２〜Ｃ１４及びＣ３４、ベースネットワークＤ１とから構成されるネットワークシステムを用いて説明するが、各個数はこれらに限定されないものとする。
【００３５】
本発明は、動的に開設・削除可能な論理的なリンクによりトポロジが構成されるネットワークにおいて適用可能な技術であるが、本実施の形態では、例としてオーバレイネットワークにおいて実施される場合について説明する。
【００３６】
ノードＡ１〜Ａ４は、ベースネットワークＤ１に接続されており、各ノード間を接続するリンクＣ１２〜Ｃ３４とともに、ベースネットワークＤ１の上にオーバレイネットワークを構成する。
【００３７】
リンクＣ１２〜Ｃ１４及びＣ３４は、図３に示すようにノードＡ１〜Ａ４間を接続するリンクであり、ＩＰトンネルなど、パケットのカプセル化によりエミュレートされる仮想的なリンクである。図３の例では、ノードＡ２−Ａ３間およびノードＡ２−Ａ４間以外の全てのノード間にリンクが存在するトポロジの例を示している。
【００３８】
ベースネットワークＤ１は、ノードＡ１〜Ａ４によって構成されるオーバレイネットワークのベースとなるネットワークである。例えば、オーバレイネットワークにおいて、ノードＡ１→Ａ２→Ａ３という経路で流れるパケットは、ベースネットワークＤ１のソース・宛先アドレスを含むヘッダでカプセル化される。そして、カプセル化されたパケットは、ベースネットワークＤ１内において、Ａ１→Ａ２の区間では、ノードＡ１から送信された、ノードＡ２を宛先とするパケットとして見える。また、Ａ２→Ａ３の区間では、ノードＡ２から送信された、ノードＡ３を宛先とするパケットとして見える。
【００３９】
ノードＡ１の構成の詳細を図４に示す。尚、ノードＡ１以外のノードも同様の構成である。
【００４０】
図４を参照すると、ノードＡ１は、トポロジ制御部１１と、仮想インターフェース部１２とから構成される。
【００４１】
トポロジ制御部１１は、ノード・リンクＤＢ（データベース）１１１と、リンク変更判断部１１２と、ローカルコスト計算部１１３と、コスト問合部１１４と、コスト合算部１１５と、リンク設定部１１６、コスト応答部１１７とから構成される。
【００４２】
ノード・リンクＤＢ１１１は、オーバレイネットワーク内に存在するノードおよびリンクのリストを記憶する機能を備える。ノード・リンクＤＢ１１１に登録されるノード・リンクのリストの例を図５のノード・リンクリスト１０１に示す。図５のノード・リンクリスト１０１を参照すると、オーバレイネットワーク内に存在するノードのＩＰアドレスのリストと、各ノードがもつリンクのリストが示されている。図５のノード・リンクリスト１０１の場合は、ＩＰアドレスが“１０．１．１．１”，“１０．２．２．２”，“１０．３．３．３”，及び“１０．４．４．４”の４ノードが存在することがわかる。また各ノードがもつリンクとして、１０．１．１．１のＩＰアドレスをもつノードは、“１０．２．２．２”，“１０．３．３．３”，及び“１０．４．４．４”のＩＰアドレスをもつ３つのノードに対してリンクをもっていることがわかる。同様に、１０．２．２．２のノードは“１０．１．１．１”、１０．３．３．３のノードは“１０．１．１．１”と“１０．４．４．４”、及び１０．４．４．４．は“１０．１．１．１”と“１０．３．３．３”のＩＰアドレスをもつノードに対してリンクをもっていることがわかる。
【００４３】
ノード・リンクＤＢ１１１は、リンク設定部１１６によるリンクの追加・削除の処理に基づいてノード・リンクリスト１０１の内容が変更され、リンクが追加されると、当該ノードのリンクのリストに該リンクの相手ノードのＩＰアドレスが追加され、反対にリンクが削除されると、当該ノードのリンクのリストから該リンクの相手ノードのＩＰアドレスが削除される。また、ノード・リンクＤＢ１１１は、他のノードにおけるリンクの追加・削除動作を反映するために、ノード・リンクリスト１０１の内容をネットワーク内のノード間で同期をとるプロトコルを利用する。このプロトコルの例として、ＯＳＰＦ(Open Shortest Path First)等で用いられる、リンクステート型のプロトコルが挙げられる。
【００４４】
リンク変更判断部１１２は、リンクの変更が必要であるかを判断し、リンク設定部１１５に対してリンクの追加・削除を指示する機能を備える。リンク変更判断部１１２のより具体的な動作を説明する。
【００４５】
まず、追加・削除する候補となるリンクを選択し、選択したリンクの追加・削除を判断する。ここで、リンク選択を各ノードが独立して行うとトポロジが収束しにくくなるため、各ノードが順番に実行するなど、オーバレイネットワーク内の各ノードが同期をとってリンクの追加・削除動作を順次行うのが望ましい。各ノードの同期の取り方としては、各ノードが順番にトークンを回し、トークンの受信をリンク選択のトリガとしてもよいし、実行する時刻が予め設定されていてもよい。また、選択するリンクは全リンクを順次選択しても、任意のリンクを選択してもよい。
【００４６】
リンク変更判断部１１２は、追加・削除の候補として選択したリンクのコストについて、ローカルコスト計算部１１３に問い合わせることにより、選択したリンクを追加・削除しない場合の自ノードのコストおよび追加・削除した場合の自ノードのコストを調べる。さらに、調べたコストをコスト問合部１１４に渡して選択したリンクを追加・削除しない場合の該候補リンクの相手ノードのコストおよび追加・削除した場合の相手ノードのコストを問い合わせる。これにより、選択したリンクを追加・削除しない場合の該候補リンクの相手ノードのコストおよび追加・削除した場合の相手ノードのコストを調べる。そして、コスト合算部１１５に問い合わせることにより、追加・削除の候補として選択したリンクについて、追加・削除しない場合の自ノードのコストと該候補リンクの相手ノードのコストとの合計値と、追加・削除した場合の自ノードのコストと相手ノードのコストとの合計値とを比較する。比較の結果、追加・削除を行った方がコストの合計値が小さくなる場合は、該リンクの追加・削除をリンク設定部１１６に対して指示する。
【００４７】
ローカルコスト計算部１１３は、予め登録されたコスト関数に基づき、ノード・リンクＤＢ１１１を参照して、自ノードにおけるコストを計算する機能を備える。コスト関数Ｃｉ（Ｃｉはノードｉにおけるコスト関数の値）の例として、
Ｃｉ＝α×（ノードｉにおけるｄｅｇｒｅｅ）＋（ノードｉから他のノードへのホップ数の合計）
や、
Ｃｉ＝α×（ノードｉにおけるｄｅｇｒｅｅの２乗）＋（ノードｉから他のノードへのホップ数の最大値）
などが挙げられる。
【００４８】
コスト問合部１１４は、相手ノードのトポロジ制御部２１に対してコスト問合せメッセージを送信し、コストを問い合わせる機能を備える。コスト問合せメッセージにおいては、リンク追加・削除の対象となる相手ノードに対して、該リンクがある場合と無い場合とのコストを問い合わせる。相手ノードのトポロジ制御部２１内においても、ローカルコスト計算部１１３と同様にコスト関数に基づき問い合わせがあったコストを計算する。相手ノードのコスト関数は、ローカルコスト計算部１１３で用いるコスト関数と同じでもよいし、異なっていてもよい。
【００４９】
コスト合算部１１５は、コスト問合部１１４により得たリンク追加・削除候補の相手ノードのコストと、ローカルコスト計算部１１３によって計算した自ノードのコストを用いて自ノードにおけるコストと相手ノードにおけるコストそれぞれの合計値を計算する機能を備える。すなわち、リンクを追加・削除しない場合の合計コストおよび、リンクを追加・削除した場合のコストを計算する。
【００５０】
リンク設定部１１６は、仮想インターフェース部１２に設定される仮想インターフェースを追加・削除することにより、リンクを追加・削除する機能を備える。
【００５１】
仮想インターフェース部１２は、ノード間を接続する仮想リンクに対応するインターフェースである。ノードＡ１が有する仮想リンクの数だけ仮想インターフェースが存在する。図６に仮想インターフェース部１２に設定される仮想インターフェースのリストの例を示す。図６の仮想インターフェースリスト２０１を参照すると、ＩＰトンネルにより仮想が構成され、インターフェースｉｆ１．２，ｉｆ１．３，ｉｆ１．４の３つのインターフェースが存在することがわかる。ｉｆ１．２は、ＩＰトンネルのリモート側のベースＩＰアドレスが２．３．４．５であり、仮想ＩＰアドレスは、ローカル側が１０．１．２．１、リモート側が１０．１．２．２であることが示されている。
【００５２】
コスト応答部１１７は、他ノードから受信したコスト問合せメッセージに対して、自ノードにおけるコストをローカルコスト計算部１１３が計算し、コスト応答メッセージを返す機能を備える。ここで、コスト問合せメッセージ内で指定されたリンクを追加・削除しない場合の自ノードのコスト、および追加・削除した場合の自ノードのコストを応答する。
【００５３】
次に、図７を参照して、本実施の形態においてノードＡ１のリンク変更判断部１１２がリンクを追加・削除する変更動作について詳細に説明する。この動作例では、図１のトポロジの例において、ノードＡが追加するリンクの候補としてノードＡ−ノードＥ間のリンクを選択し、コスト関数として
Ｃｉ＝２×（ノードｉにおけるｄｅｇｒｅｅ）＋（ノードｉから他のノードへのホップ数の合計）
を用いる場合を例にとって説明する。
【００５４】
まず、ノードＡ１において、リンク変更判断部１１２が、追加・削除する候補リンクを選択する（図７のステップＳ１０１）。ここでは、先に述べたようにノードＡ−ノードＥ間のリンクを、追加するリンクの候補として選択するものとする。
【００５５】
次に、リンク変更判断部１１２は、ステップＳ１０１で選択したリンクに対して、当該リンクがある場合および無い場合の自ノードのコストをローカルコスト計算部１１３に問い合わせることにより調べる（ステップＳ１０２）。図１の場合は、当該リンクがある場合および無い場合のノードＡのコストは、ともにＣＡ＝１１となる。
【００５６】
次に、リンク変更判断部１１２は、選択したリンクに対して、当該リンクがある場合の該候補リンクの相手ノードのコストおよび無い場合の相手ノードのコストを、コスト問合部１１４に問い合わせて調べる（ステップＳ１０３）。この時、問い合わせを受けたノードＥのローカルコスト計算部は、当該リンクがある場合と無い場合との自ノードのコストを計算してノードＡ１に通知する。図１の場合は、当該リンクがある場合および無い場合のノードＥのコストは、それぞれＣＥ＝１１，１０となる。
【００５７】
次に、ステップＳ１０２およびステップＳ１０３で調べた自ノードおよび該候補リンクの相手ノードのコストを基に、該候補リンクが無い場合の自ノードのコストと該候補リンクの相手ノードのコストとの合計値と、ある場合の自ノードのコストと相手ノードのコストとの合計値とを、コスト合算部１１５に問い合わせることにより比較する（ステップＳ１０４）。図１の場合は、当該リンクが無い場合およびある場合のノードＡ、Ｅのコストの合計値は、それぞれＣＡ＋ＣＥ＝２２，２１となる。
【００５８】
ステップＳ１０４の比較において、該候補リンクを追加・削除を行った方がコストの合計値が小さくなる場合は、リンク設定部１１６に指示することにより該候補リンクの追加・削除設定を行う（ステップＳ１０５）。ステップＳ１０４の比較において、該候補リンクを追加・削除を行ってもコストの合計値が小さくならない場合は、何もせず動作を終了する。図１の場合は、ステップＳ１０４において、ノードＡとノードＥとの間のリンクがある方がコストの合計値が小さくなるため、ノードＡはリンクＥへのリンクを追加する。自ノードのコストを用いて判断する構成の場合、ノードＡのコストはリンクを追加してもコストが下がらないためリンクを追加しないと判断していた。しかしながら、本実施の形態では、相手ノードのコストとの合計値を比較することにより、全ノードのコストの合計値を比較した場合（リンクを追加しない場合：５４→リンクを追加した場合：５２）と同じ判断ができている。
【００５９】
次に本実施の形態の効果について説明する。
本実施の形態では、リンクを追加・削除する際に自ノードのコストに加えて、相手ノードのコストとの合計値を比較して該リンクを追加・削除するかを判断する。追加・削除対象のリンクの両端のノードは、リンクの追加・削除によってコストが変化する度合いが大きい（特にｄｅｇｒｅｅや平均ホップ数を含むコスト関数を用いる場合）。そのため、リンクの追加・削除を判断する自ノードだけではなく、リンクの追加・削除相手となるノードのコストとの合計値を比較した方が、該リンクの追加・削除によってネットワーク内の全ノードのコストの合計値への影響を精度よく反映させることができる。このようにすることにより、全ノードのコストを調べなくても少ない数のノードのコストを調べるだけでグローバル最適に近い判断が可能となる。
【００６０】
〈第２の実施の形態〉
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
【００６１】
本発明の第２の実施の形態は、図４に示した本発明の第１の実施の形態と同様に、オーバレイネットワークを構成するノードによって実現される。
【００６２】
図８を参照すると、本実施の形態におけるノードＡ５が示されている。
【００６３】
ノードＡ５は、トポロジ制御部５１と、仮想インターフェース部５２とから構成される。
【００６４】
仮想インターフェース部５２については、第１の実施の形態で示した仮想インターフェース部１２と同様の機能・動作を行うため、詳細な説明は省略する。
【００６５】
トポロジ制御部５２は、ノード・リンクＤＢ（データベース）５１１と、リンク変更判断部５１２と、ローカルコスト計算部５１３と、近隣コスト問合部５１４と、遠隔コスト問合部５１５と、コスト合算部５１６と、リンク設定部５１７、コスト応答部５１８とから構成される。
【００６６】
ノード・リンクＤＢ５１１、コスト合算部５１６、リンク設定部５１７、コスト応答部５１８については、第１の実施の形態で示したノード・リンクＤＢ１１１、コスト合算部１１５、リンク設定部１１６、コスト応答部１１７と同様の機能・動作を行うため、詳細な説明は省略する。
【００６７】
リンク変更判断部５１２は、第１の実施の形態におけるリンク変更判断部１１２の機能・動作と比べ以下の点が異なる。
【００６８】
リンク変更判断部１１２は、追加・削除の候補として選択したリンクについて、自ノードおよび追加・削除の候補リンクの相手ノードのコストの合計値に基づいて、リンクの追加・削除の可否を判断していた。これに対し、本実施の形態におけるリンク変更判断部５１２は、自ノードを含む自ノードからｎホップ以内の全ノード、および、追加・削除の候補リンクの相手ノードを含む相手ノードからｎホップ以内の全ノードのコストの合計値に基づいてリンクの追加・削除の可否を判断する。ここで、ｎは整数であり、リンク変更判断部１１２に事前に設定される。ｎを大きくとると多数のノードのコストを調べる必要があるため、ｎ＝１や２といった小さい値を設定することが望ましい。もし自ノードからｎホップ以内のノードと該相手ノードからｎホップ以内のノードに重複がある場合は、重複させないようにコストの合計値を計算する。
【００６９】
ローカルコスト計算部５１３は、自ノードのコストおよび自ノードからｎホップ以内に存在する全ノードのコストを調べる機能を備える。自ノードのコストの調べ方はローカルコスト計算部１１３と同様であるが、自ノードからｎホップ以内に存在するノードに対しては、近隣コスト問合部５１４を用いてコスト問合せメッセージを送信することによりコストを問い合せる。
【００７０】
近隣コスト問合部５１４は、自ノードからｎホップ以内に存在するノードのトポロジ制御部６２に対して、リンク変更判断部５１２が選択したリンクを追加・削除しない場合のコストおよび該リンクを追加・削除した場合のコストを問い合わせる機能を備える。ここで、ＴＴＬをｎに設定してコスト問合せメッセージをフラッディング(Flooding)することにより、ｎホップ以内に存在する全ノードに対してコスト問合せメッセージを送り届ける。近隣コスト問合部５１４は、送信したコスト問合せメッセージに対する応答を集め、ローカルコスト計算部５１３へ応答する。
【００７１】
遠隔コスト問合部５１５は、リンク変更判断部５１２が選択したリンクの相手ノードおよび該相手ノードからｎホップ以内のノードに存在するノードに対して、該リンクを追加・削除しない場合のコストおよび該リンクを追加・削除した場合のコストを問い合わせる機能を備える。ここで、コスト問合せメッセージは、相手ノードのトポロジ制御部７１へまず送信される。そして、該コスト問合せメッセージを受信したノードは、ＴＴＬをｎに設定してフラッディング(Flooding)し、該メッセージをさらに転送することにより該相手ノードからｎホップ以内に存在する全ノードに対してコスト問合せメッセージを送り届ける。該相手ノードからフラッディングで転送されたコスト問合せメッセージを受信したノードは、指定された候補リンクを追加・削除しない場合のコストおよび該リンクを追加・削除した場合のコストを応答する。該応答メッセージは、相手ノードのトポロジ制御部７１に一旦集められ、まとめてノードＡ５へ応答される。遠隔コスト問合部５１５は、送信したコスト問合せメッセージに対する応答をリンク変更判断部５１２へ応答する。
【００７２】
次に、図９を参照して、本実施の形態においてノードＡ５のリンク変更判断部５１２がリンクの追加・削除を行う変更動作について詳細に説明する。この動作例では、図２のトポロジの例において、ノードＡが追加するリンクの候補としてノードＡ−ノードＥ間のリンクを選択し、コスト関数として、
Ｃｉ＝４．５×（ノードｉにおけるｄｅｇｒｅｅ）＋（ノードｉから他のノードへのホップ数の合計）
を用い、また、ｎ＝１の場合を例にとって説明する。
【００７３】
まず、ノードＡ５において、リンク変更判断部５１２が、追加・削除する候補リンクを選択する（図９のステップＳ２０１）。ここでは、先に述べたようにノードＡ−ノードＥ間のリンクを追加するリンクの候補として選択するものとする。
【００７４】
次に、リンク変更判断部５１２は、ステップＳ２０１で選択したリンクに対して、当該リンクがある場合、および、無い場合の自ノードおよび自ノードからｎホップ以内に存在するノードのコストをローカルコスト計算部５１３に問い合わせる（ステップＳ２０２）。図２の場合は、ｎ＝１としているため、ノードＡ（自ノード）およびノードＡから１ホップ以内にあるノードＢへコストを問合せる。当該リンクがある場合および無い場合のノードＡのコストは、それぞれＣＡ＝１４．５，１５であり、ノードＢのコストは、それぞれＣＢ＝１６，１５である。
【００７５】
次に、リンク変更判断部５１２は、ステップＳ２０１で選択したリンクに対して、当該リンクがある場合、および無い場合の相手ノードおよび相手ノードからｎホップ以内に存在するノードのコストを遠隔コスト問合部５１５に問い合わせる（ステップＳ２０３）。図２の場合は、ノードＥ（相手ノード）およびノードＥから１ホップ以内にあるノードＤへコストの問合せが行われる。当該リンクがある場合および無い場合のノードＥのコストはそれぞれＣＡ＝１４．５，１５であり、ノードＤのコストはそれぞれＣＢ＝１６，１５である。
【００７６】
次に、ステップＳ２０２およびステップＳ２０３で調べた各ノードのコストを基に、該候補リンクがある場合の各ノードのコストの合計値と、無い場合の自ノードのコストと相手ノードのコストとの合計値とを、コスト合算部５１６に問い合わせて比較する（ステップＳ２０４）。図２の場合は、当該リンクがある場合および無い場合のノードＡ，Ｂ，Ｄ，Ｅのコストの合計値は、それぞれＣＡ＋ＣＢ＋ＣＤ＋ＣＥ＝６１，６０となる。
【００７７】
ステップＳ２０４の比較において、該候補リンクを追加・削除を行った方がコストの合計値が小さくなる場合は、リンク設定部５１７に指示することにより該候補リンクの追加・削除設定を行う（ステップＳ２０５）。一方、ステップＳ２０４の比較において、該候補リンクを追加・削除を行ってもコストの合計値が小さくならない場合は、何もせず動作を終了する。図２の場合は、ステップＳ２０４において、ノードＡがノードＥへリンクを追加した方がコストの合計値が小さくなるため、ノードＡはリンクＥへのリンクを追加する。自ノードのコストを用いて比較する構成では、ノードＡのコストはリンクを追加してもコストが下がらないためリンクを追加しないと判断していた。しかしながら、本実施の形態では、自ノードおよび候補リンクの相手ノードのコストに加えて、それらのノードの周辺ノードのコストも含めて合計値を比較することにより、全ノードのコストの合計値を比較した場合（リンクを追加しない場合：７６→リンクを追加した場合：７５）と同じ判断ができている。
【００７８】
また、第１の実施の形態のように、自ノードおよび候補リンクの相手ノードとの合計値に基づいてリンクの追加・削除の判断をした場合、リンク追加しない場合：ＣＡ＋ＣＥ＝２９、リンク追加した場合：ＣＡ＋ＣＥ＝３０、となり、リンクを追加しないという判断になってしまう。しかしながら、本実施の形態では、周辺ノードのコストを含めて合計値をとることにより、精度の高い判断が可能となっている。
【００７９】
次に本実施の形態の効果について説明する。
本実施の形態では、リンクを追加・削除する際に、自ノードおよび候補リンクの相手ノードのコストに加えて、それらのノードの周辺ノードのコストも含めて合計値を比較して該リンクを追加・削除するかを判断する。
【００８０】
先に述べたとおり、追加・削除対象のリンクの両端のノードは、リンクの追加・削除によってコストが変化する度合いが大きい（特にｄｅｇｒｅｅや平均ホップ数を含むコスト関数を用いる場合）。しかしながら、追加・削除対象のリンクの両端のノードだけではなく、両端の周辺のノードもコストに対して影響を受ける。特に、両端のノードに近い（ホップ数が少ない）ほど、影響を受ける度合いが大きい。
【００８１】
そのため、リンクの追加・削除対象のリンクの両端ノードだけではなく、両端ノードの周辺のノードのコストも含めたコストの合計値を比較した方が、該リンクの追加・削除によってネットワーク内の全ノードのコストの合計値への影響を精度よく反映させることができるといえる。また、ｎを大きくとると精度が高くなる反面、コストを収集する負荷が高くなりスケーラビリティが低下するため、そのトレードオフを考えてｎを決定すべきである。
【００８２】
尚、上述した本発明の端末は、上記説明からも明らかなように、ハードウェアで構成することも可能であるが、コンピュータプログラムにより実現することも可能である。
【００８３】
プログラムメモリに格納されているプログラムで動作するプロセッサによって、上述した実施の形態と同様の機能、動作を実現させる。尚、上述した実施の形態の一部の機能のみをコンピュータプログラムにより実現することも可能である。
【００８４】
上記説明では、オーバレイネットワークにおけるトポロジの制御方法を開示しているが、より一般的には、動的に開設・削除可能な論理的なリンクによりトポロジが構成されるネットワークにおいて適用可能である。このようなネットワークの例は、
・ノード間リンクがＩＰトンネルやＵＤＰ（またはＴＣＰ）トンネルによって構成されるオーバレイネットワーク
・ノード間リンクがラベルパスによって構成されるＭＰＬＳ(Multi-Protocol Label Switching)ネットワーク
・物理配線切替スイッチによりノード間の物理配線を動的に切り替え可能なネットワーク
などが挙げられる。本発明では、オーバレイネットワークのみならず、このような動的に開設・削除可能な論理的なリンクによりトポロジが構成されるネットワークにおけるトポロジ制御に適用可能である。
【００８５】
また、上記説明のコスト合算部はローカルコスト計算部内に構成されていても良い。
【００８６】
以上、実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形し実施することが出来る。
【００８７】
この出願は、２０１０年６月２日に出願された日本出願特願２０１０−１２６５５１を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００８８】
Ａ１〜Ａ５  ノード
１１，５１  トポロジ制御部
１１１，５１１  ノード・リンクＤＢ
１１２，５１２  リンク変更判断部
１１３，５１３  ローカルコスト判断部
１１４  コスト問合部
１１５，５１６  コスト合算部
１１６，５１７  リンク設定部
１１７，５１８  コスト応答部
１２，５２  仮想インターフェース部
５１４  近隣コスト問合部
５１５  遠隔コスト問合部
２１，７１  相手ノードのトポロジ制御部
６１  ｎホップ以内のノードのトポロジ制御部
Ｃ１２，Ｃ１３，Ｃ１４，Ｃ３４  リンク
Ｄ１  ベースネットワーク
１０１  ノード・リンクＤＢ
２０１  インターフェースリスト
【図１】
2011152456.tif 000003
【図２】
2011152456.tif 000004
【図３】
2011152456.tif 000005
【図４】
2011152456.tif 000006
【図５】
2011152456.tif 000007
【図６】
2011152456.tif 000008
【図７】
2011152456.tif 000009
【図８】
2011152456.tif 000010
【図９】
2011152456.tif 000011
【国際調査報告】
2011152456.tif 000012
2011152456.tif 000013
2011152456.tif 000014