通信装置、通信方法及びプログラム
【課題】利用するネットワーク資源を効果的に分散させることにより耐障害性を向上させる。
【解決手段】通信ネットワーク上のノード間の通信を行う通信装置は、通信ネットワークのトポロジ情報に基づいてノードごとに計算された中心性に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部と、通信相手となるノードごとに、第１のメトリックと第２のメトリックとを保持するデータ転送テーブルと、データ転送テーブルを参照し、メトリック切替制御部の制御に基づき第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、決定したノードにデータを転送するデータ転送部と、を有する。
【解決手段】通信ネットワーク上のノード間の通信を行う通信装置は、通信ネットワークのトポロジ情報に基づいてノードごとに計算された中心性に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部と、通信相手となるノードごとに、第１のメトリックと第２のメトリックとを保持するデータ転送テーブルと、データ転送テーブルを参照し、メトリック切替制御部の制御に基づき第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、決定したノードにデータを転送するデータ転送部と、を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク上のノード間の通信を行う通信装置、通信方法及びプログラムに関する。
【背景技術】
【０００２】
近年、将来の新世代ネットワーク基盤を構成する方式の候補の一つとして、オーバーレイ・ネットワークが研究されている。オーバーレイ・ネットワークは、下位層となる物理ネットワーク上に論理的に構築されたネットワークであり、下位層のネットワークでのノード配置における物理的なトポロジを意識することなく、柔軟なネットワーク通信を可能にするという特長を有する。
【０００３】
図７は、関連技術におけるオーバーレイ・ネットワーク通信のためのネットワーク構成例を示している。図７では、合計で１１個の通信ノードが設けられており、図示実線で示すように物理的な接続構成を有している。隣接する通信ノード間の接続をリンクと呼ぶ。説明の都合上、これらの通信ノードのうち、２つが送信ノード１０１（すなわち送信ノードＡと送信ノードＢ）であり、別の２つが宛先ノード１０２（すなわち宛先ノードＡと宛先ノードＢ）であるとする。通信ノードのうち、送信ノード１０１と宛先ノード１０２を除いた７個の通信ノードには、それぞれ、符号１００1〜１００7が付与されている。
【０００４】
ここで上述のように１１個の通信ノード（２個の送信ノード１０１と、２個の宛先ノード１０２と、送信ノードでも宛先ノードでもない７個の通信ノード１００1〜１００7）からなる物理ネットワーク上にオーバーレイ・ネットワークを構築して、送信ノードＡから宛先ノードＡに情報を伝達し、送信ノードＢから宛先ノードＢに情報を伝達する場合を考える。送信ノードＡは、図示点線で示すように、送信ノードＡから通信ノード１００1〜１００5及び宛先ノードＢをこの順で経由して宛先ノードＡに接続するオーバーレイ・ネットワークを形成し、送信ノードＢは、図示一点鎖線で示すように、送信ノードＢから通信ノード１００3〜１００5をこの順で経由して宛先ノードＢに接続するオーバーレイ・ネットワークを形成する。このとき、一部の通信ノードやリンクは、これら２つのオーバーレイ・ネットワークで共有される物理リソースということになる。このようなオーバーレイ・ネットワークを説明する先行技術文献の一例として、非特許文献１を挙げる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris, "Resilient Overlay Networks," Proc. 18th ACM SOSP, Banff, Canada, October 2001.
【非特許文献２】F. Tutzauer, "Entropy as a measure of centrality in networks characterized by path-transfer flow,'' Social Networks, Social Networks, 29, pp. 249-265, 2007.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
このように、同一の物理的なネットワーク基盤の上に仮想的な論理ネットワークを複数重畳させて設定し、オーバーレイ・ネットワークを形成して通信を行う場合、オーバーレイ・ネットワークとしては論理的に独立していても、複数のオーバーレイ・ネットワークはノードやリンクといった物理的な資源を共有しているのが一般的である。その際、物理ネットワークでのトポロジに依存して、使われやすいノードやリンクと、使われにくいノードやリンクとが生じ、ノードやリンクにおいて使用頻度の偏りが出やすくなる。使用頻度が高く、利用が集中するノードやリンクは、より高い確率で故障しやすくなり、また、利用が集中しているノードやリンクが障害となった場合に、通信ネットワーク・システムへ与えるインパクトは非常に大きなものとなってしまう。このように、関連技術でのオーバーレイ・ネットワークでは、ノードやリンクの使用頻度に偏りがあることに起因して、耐障害性が向上しないという課題がある。ノードを構成するネットワーク機器やリンクに障害が発生した場合においても高品位な通信サービスをユーザに提供でき、かつ、ネットワーク資源の効率的な利用が可能であるようにすることが、望まれている。
【０００７】
そこで本発明の目的は、例えばオーバーレイ・ネットワークを重畳的に構成する場合などに、利用するネットワーク資源を効果的に分散させることにより耐障害性を向上させることが可能な通信システム基盤を構成するための通信装置、通信方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明の通信装置は、通信ネットワーク上のノード間の通信を行う通信装置であって、通信ネットワークのトポロジ情報に基づいてノードごとに計算された中心性に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部と、通信相手となるノードごとに、第１のメトリックと第２のメトリックとを保持するデータ転送テーブルと、データ転送テーブルを参照し、メトリック切替制御部の制御に基づき第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、その決定したノードにデータを転送するデータ転送部と、を有する。
【０００９】
本発明の通信方法は、通信ネットワーク上のノード間の通信を行う通信方法であって、通信ネットワークのトポロジ情報に基づいてノードごとに計算された中心性に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択することと、通信相手となるノードごとに第１のメトリックと第２のメトリックとを保持するデータ転送テーブルを参照し、選択に基づき第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、その決定したノードにデータを転送することと、を有する。
【００１０】
本発明のプログラムは、通信ネットワーク上のノード間の通信を行うコンピュータに、通信ネットワークのトポロジ情報に基づいてノードごとに計算された中心性に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択する処理と、通信相手となるノードごとに第１のメトリックと第２のメトリックとを保持するデータ転送テーブルを参照し、選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、その決定したノードにデータを転送する処理と、を実行させる。
【発明の効果】
【００１１】
本発明では、物理的なネットワークの構成情報や既設の論理ネットワークの構成情報に基づくトポロジ情報からノードごとに計算された中心性に基づくメトリックを活用する。中心性に基づくメトリックは、後述するように、グラフ理論等でCentrality値（中心性値）として知られている値に基づくものであり、本発明では、中心性に基づくメトリックを第１のメトリックとして使用することによって、例えばオーバーレイ・ネットワークで利用するネットワーク資源や通信トラヒックがトポロジの中心方向へ集中しないように制御し、かつ、中心性に基づくメトリックとは異なる第２のメトリックを用いるデータ転送制御との併用を行うことによって、耐障害性を向上させている。第２のメトリックとしては、例えば、最短ホップ数に基づくメトリックなどを用いることができる。このような本発明によれば、ネットワーク資源及び通信トラヒックが分散され、耐障害性を向上させた通信サービスを提供することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の第１の実施形態の通信装置の機能構成を示すブロック図である。
【図２】本発明の第２の実施形態が適用される通信ネットワークの構成の一例を示す図である。
【図３】第２の実施形態の通信装置の機能構成を示すブロック図である。
【図４】Centrality値計算処理を示すフローチャートである。
【図５】図２及び図３に示す通信装置での通信データ転送処理を示すフローチャートである。
【図６】データ転送テーブルの内容の一例を示すである。
【図７】関連技術における通信ネットワークの構成の一例を示す図である。
【発明を実施するための形態】
【００１３】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００１４】
《第１の実施形態》
図１は、本発明の第１の実施形態の通信装置を示している。一般に通信ネットワークは、複数個の通信ノードとこれらの通信ノード間を接続するリンクとから構成されているが、図１に示す通信装置は、通信ネットワーク上で、隣接する通信ノードとの間で通信を行う通信ノードにおいてデータの送受信処理を行うものとして構成されるものであり、例えば、経路制御（ルーティング）を行って、物理ネットワーク上に重畳されるオーバーレイ・ネットワークにおける通信を媒介する。
【００１５】
この通信装置は、通信ネットワークのトポロジ情報に基づいて通信ノードごとに計算された中心性すなわちCentrality値に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部２０３と、通信相手となる通信ノードごとに、第１のメトリックと第２のメトリックとを保持するデータ転送テーブル２００と、データ転送テーブル２００を参照し、メトリック切替制御部２０３の制御に基づき第１のメトリック及び第２のメトリックのいずれかを用いて転送先の通信ノードを決定し、その決定した通信ノードにデータを転送するデータ転送部２０６と、を備えている。データ転送部２０６は、隣接する１以上の通信ノードに対し、隣接する通信ノードごとのリンクを介して接続するものである。第２のメトリックとしては、例えば、通信相手となる通信ノードまでの最短ホップ数を用いることができる。
【００１６】
通信ネットワークの構成が動的に変化しないとすれば、第１のメトリック及び第２のメトリックとも通信ネットワークの構成時に通信ノードごとに確定するものであるから、予めデータ転送テーブル２００に書き込んでおくことができる。通信ネットワークの構成が動的に変化する場合には、例えば、定期的に通信ネットワークのトポロジ情報を収集し、第１のメトリック及び第２のメトリックを算出してデータ転送テーブル２００を更新したり、他の通信ノードによって算出された第１のメトリック及び第２のメトリックを受信して、受信値によってデータ転送テーブル２００を更新したりすればよい。
【００１７】
本実施形態の通信装置は、物理的なネットワークや既設の論理ネットワークの構成情報を基にして、そのトポロジのCentrality値を第１のメトリックとして活用し、オーバーレイネットワークで利用するネットワーク資源や通信トラヒックがトポロジの中心方向へ集中しないように制御し、かつ、第２のメトリックによる通常のデータ転送制御との併用を行うことによって、耐障害性を向上させている。
【００１８】
《第２の実施形態》
図２は、第２の実施形態の通信装置が適用される通信ネットワークの構成の一例を示している。通信ネットワークでは、複数個の通信ノードがリンクを介して相互に接続している。通信ノードは、通信データを転送することが可能な端末であり、図２では、合計で１１個の通信ノードが設けられており、図示実線で示すように物理的な接続構成を有している。通信ノードの中には、データを送信する２個の送信ノード１０１（すなわち送信ノードＡと送信ノードＢ）、通信データの最終到達先である２個の宛先ノード１０２（すなわち宛先ノードＡと宛先ノードＢ）、Centrality値を計算する代表ノード１０３が含まれている。送信ノード１０１でも宛先ノード１０２でも代表ノード１０３でもない通信ノードには、符号１００1〜１００3，１００5〜１００7が付与されている。また、送信ノード１０１、宛先ノード１０２及び代表ノード１０３も含めて通信ノードを総称する場合には、符号１００を用いることとする。
【００１９】
本実施形態の通信装置は、各通信ノード１００において通信データの送受信処理を行う部分として構成されるものである。Centrality値とは、グラフ理論によって、通信ネットワークのトポロジ構成での中心性（Centrality）を示す値として算出されるものである。図２において、各通信ノードの下側に括弧書きで付記されている値が、ここで示した通信ネットワークのトポロジ構成における、各通信ノードのCentrality値の例を示している。
【００２０】
図３は、通信ノード１００の機能構成を示している。
【００２１】
通信ノード１００は、通信相手となる通信ノードとその通信ノードに対するCentrality値（第１のメトリック）と他の種類のメトリック（第２のメトリック）とを記載するデータ転送テーブル２００と、データ転送デーブル２００を管理し、特にデータ転送時にデータ転送テーブル２００へのアクセスを制御するデータ転送テーブル管理部２０１と、隣接する通信ノードおよび自通信ノードのCentrality値を保有して管理し、データ転送テーブル２００に書き込むCentrality値制御部２０２、データ転送をCentrality値ベースの制御を行うか、あるいは第２のメトリックをベースに制御するかの切り替えを制御するメトリック切替制御部２０３と、リーフノードに対してのデータ転送処理の制御などの例外的なデータ転送処理の制御を行う例外処理制御部２０４と、メトリック切り替え処理や例外処理のために利用するシステムパラメータなどの各種情報を保存する情報記憶部２０５と、他の通信ノードからデータを受信し、受信したデータを転送するデータ転送部２０６と、を備えている。データ転送テーブル２００及び情報記憶部２０５は、例えば、通信ノード１００に備えられるメモリ内の記憶領域として設けられる。データ転送テーブル２００には、通信相手となる通信ノードが、例えば、そのアドレスとその属するネットワークとによって示され、さらに、通信相手となる通信ノードごとに、Centrality値と第２のメトリックと、さらにどのインタフェースがそのネクストホップになるかが記録される。第２のメトリックとしては、例えば、最短ホップ数が用いられる。
【００２２】
データ転送部２０６は、データ転送制御部２０７と、リンクを介して他の通信ノードと接続する１または複数のインタフェース２０８と、を備えている。インタフェース２０８は、例えば、イーサネット（登録商標）によるインタフェースである。図示したものでは、Ｅ０〜Ｅ２の３つのインタフェース２０８が設けられており、このことは、図示した通信ノード１００が、最大３個の隣接する通信ノードと接続できることを意味している。データ転送制御部２０７は、いずれかのインタフェース２０８からデータを受信して転送するものであり、データを受信したときに、転送テーブル管理部２０１を介してデータ転送テーブル２００を参照し、メトリック切替制御部２０３及び例外処理制御部２０４の制御に基づきCentrality値及び第２のメトリックのいずれかを用いて転送先の通信ノードを決定し、その決定した通信ノードに対応するインタフェース２０８を介して転送する。
【００２３】
次に、本実施形態における具体的な処理について説明する。
【００２４】
まず、本実施形態における基本制御の一つとなるCentrality値の算出について説明する。Centrality値の計算処理は、図４に示すように、最初に通信ネットワーク内から代表ノード１０３を選定する処理（ステップＳ１０１）と、ステップＳ１０１の実行後、代表ノード１０３がトポロジ情報を収集する処理（ステップＳ１０２）と、ステップＳ１０２の実行後、代表ノード１０３がCentrality値を計算する処理（ステップＳ１０３）と、ステップＳ１０３の実行後、計算したCentrality値を他の各通信ノードへ配布する処理（ステップＳ１０４）と、ステップＳ１０４の実行後、各通信ノードが隣接する通信ノード間でCentrality値を情報交換する処理（ステップＳ１０５）とから構成される。
【００２５】
最初にステップＳ１０１では、通信ネットワークの中から、一つ以上の通信ノードを代表ノード１０３として選出する。この選出の手法としてはどのような手法を用いてもよく、例えば、ルーティング・プロトコルとして知られているＯＳＰＦ（Open Shortest Path First）においてセグメントごとに代表ルータ（designated router；ＤＲ）を選定する手法をそのまま用いることも可能である。あるいは、ネットワーク構築後に代表ノード１０３を選定するのではなく、予め代表ノード１０３を設置するという手法を用いてもよい。
【００２６】
ステップＳ１０２では、選定された代表ノード１０３が、通信ネットワーク内の全通信ノードから当該通信ノードのリンク接続情報を入手する。これにより、代表ノード１０３はネットワーク全体のトポロジ情報を保有することになる。
【００２７】
次にステップＳ１０３では、全体のトポロジ情報を基に、代表ノード１０３が各通信ノードのCentrality値を計算する。Centrality値の算出方法としては、いくつかの手法が知られているが、ここでは、Betweenness Centrality値の手法による計算例を以下に示す。ｇijを通信ノードｉから通信ノードｊに至る経路の数、及び
【００２８】
【数１】
【００２９】
を上述の経路のうちのノードｋを通過する経路の数とすると、このトポロジにおける通信ノードｋに対するCentrality値ｂkは以下の式で表すことができる。
【００３０】
【数２】
【００３１】
本発明において用いられるCentrality値としては、上述のようなBetweenness Centralityに限定されるものではなく、その他のCentrality値をベースとすることも可能である。一例として、非特許文献２に示されるようなエントロピーベースのCentrality値を用いることも可能である。
【００３２】
ステップＳ１０４では、代表ノード１０３が各通信ノードに対して、各通信ノードのCentrality値情報を配信する。
【００３３】
ステップＳ１０５では、全通信ノードが、自ノードと隣接する全ての通信ノードとの間でCentrality値情報を交換する。
【００３４】
以上の処理によって、全て通信ノードについてのCentrality値が計算され、それらの値が各通信ノードへ配信され、通信ノード間で必要な情報共有までが完了する。
【００３５】
次に、本実施形態におけるデータ転送制御処理について説明する。データ転送制御処理は、最初に転送データの受信を検知する処理（ステップＳ２０１）と、ステップＳ２０１の実行後、転送モードを選定する処理（ステップＳ２０２）と、ステップＳ２０２においてCentrality値モードが選択された場合に、データ転送テーブルを参照する処理（ステップＳ２０３）と、ステップＳ２０３の実行後、Centrality値ベースで転送先を選定する処理（ステップＳ２０４）と、ステップＳ２０２において通常モードが選択された場合に、データ転送テーブルを参照する処理（ステップＳ２０５）と、ステップＳ２０５の実行後、第２のメトリックベースで転送先を選定する処理（ステップＳ２０６）と、ステップＳ２０４またはＳ２０６の実行後、受信データを送信する処理（ステップＳ２０６）と、から構成されている。
【００３６】
ステップＳ２０１では、データ転送用のパケットディスクリプタなどを定期的にルックアップすることなどによって、インタフェース２０８において転送すべきデータを受信したことを検出する。
【００３７】
ステップＳ２０２では、メトリック切替制御部２０３が、データを転送する際の転送モードを確率的に選択する。ここでは、第２のメトリックとして最短ホップ数を用いることとし、Centrality値をメトリックとしてデータ転送を行うCentrality値モード、及び、最短ホップ数をメトリックとしてデータ転送を行う通常モードとを確率的に選択することを想定する。例えば、予めシステムパラメータとしてCentrality値モードと通常モードの各々の発生確率を保持しておき、一様乱数を発生させて、その発生確率に従って、転送モードを選択決定する。
【００３８】
ここで、図２に示した通信ネットワークを考えると、一例として、通信ノード１００5に保持されるデータ転送テーブル２００の内容を図６に示すようなものとなる。このデータ転送テーブル２００によれば、通信ノード１００5は、通信ネットワークにおいてそれぞれアドレスが192.168.1.1，192.168.2.1及び192.168.3.1で表される３つの通信ノードに対し、インタフェースＥ０，Ｅ１，Ｅ２を介して隣接しており、これらの隣接通信ノードのCentrality値は、それぞれ、３．０２８、２．８０６及び２．８０９である。ここで、この通信ノード１００5が、インタフェースＥ０から、宛先192.168.10.1のパケットを受信した場合を考える。
【００３９】
ステップＳ２０２においてCentrality値モードが選択された場合は、ステップＳ２０３においてデータ転送テーブル２００の内容を読み出し、ステップＳ２０４のCentrality値ベースでの転送先選定処理に移行する。インタフェースＥ０以外のインタフェースであるインタフェースＥ１，Ｅ２を介して接続された隣接通信ノードのCentrality値をみてみると、それぞれ２．８０６と２．８０９であるため、そられのCentrality値のうち、小さい方の値に対応する隣接通信ノードである192.168.2.1が転送先として選択決定される。こうすることにより、Centrality値が小さいノード（トポロジの中心から遠いノード）に対して流れるトラヒックを増加させ、Centrality値が大きいノード（トポロジの中心に近いノード）へのトラヒックを減少させることができるため、トラヒックやネットワーク資源の中央集中化を抑制することが可能となる。
【００４０】
一方、ステップＳ２０２において通常モードが選択された場合は、ステップＳ２０５においてデータ転送テーブル２００の内容を読み出し、ステップＳ２０６の他メトリックベースの転送先選定処理に移行する。宛先のネットワークである192.168.10.0/24のネクストホップがＥ２と設定されているため、転送先の通信ノードとしては、インタフェースＥ２に接続している192.168.3.1を転送先として選択決定する。仮に、この通常モードを用いずにCentrality値モードだけでの運用を行っていると、中心ではない方面へのトラヒックやネットワーク資源が逆に集中してしまうため、このように通常モードとの併用を行うことによって、その集中化を緩和して、より一層の資源の分散化を実現する。これにより耐障害性を向上させることが可能となる。
【００４１】
ステップＳ２０７では、上述のステップＳ２０４またはＳ２０６において選択決定された転送先ノードへ受信データを転送する。
【００４２】
図２に示した通信ネットワークにおいて、以上のようなデータ転送制御処理を行うと、送信ノードＡから宛先ノードＡへのデータ転送経路は、例えば、図示点線に示すように、送信ノードＡから通信ノード１００1〜１００3を経由して送信ノードＢに至り、再び通信ノード１００3に戻り、代表ノード１０３、通信ノード１００5〜１００7及び宛先ノードＢを経由して宛先ノードＡに接続するものとなる。また、送信ノードＢから宛先ノードＢへのデータ転送経路は、例えば、図示一点鎖線で示すように、送信ノードＢから通信ノード１００3、代表ノード１０３、通信ノード１００5を経由して宛先ノードＢに接続するものとなる。
【００４３】
ところで、ステップＳ２０４で選択された転送先がリーフノード、すなわち、隣接する通信ノードの数が１つである通信ノードである場合を考える。転送先はリーフノードではあるが転送データの宛先ノード自身ではない場合、Centrality値をベースとした転送を行った際には、そのリーフノードへデータ転送した後に、すぐに自通信ノードへそのデータが返送されるという経路をたどり、余計な通信経路増加を招くことになる。例えば、図２において点線で示した経路において、通信ノード１００3と送信ノードＢとの間で経路が往復で設定されているのは、このような余計な通信経路となる。そこで、本実施形態では、例外制御処理部２０４により、リーフノードを検出し、リーフノードがデータの宛先ノード自身でない場合にはリーフノードには転送しないようにデータ転送制御部２０７に指示することが好ましい。
【００４４】
以上の制御処理を行うことによって、通信ネットワークにおけるトラヒックの平滑化を実現することができ、また、オーバーレイ・ネットワークで通信を行う際の利用ネットワーク資源の分散化を実現でき、耐障害性を向上させた通信サービスを提供できる。
【００４５】
本実施形態によれば、共通な物理ネットワークの上に仮想的な論理ネットワークを重畳させてオーバーレイ・ネットワークにより通信を行うネットワークにおいて、通信トラヒックや使用するネットワーク資源の中央集中化を緩和することが可能な、耐障害性を向上させて通信システム基盤を提供することができる。
【００４６】
《第３の実施形態》
第２の実施形態では、一つの管理ドメインによって構成される通信ネットワークの場合について説明した。しかしながら本発明が適用される通信ネットワークは単一の管理ドメインを有するものに限定されるものではない。例えば、クラスタ分割を行うことによって複数のネットワークに分割した実施形態としても本発明は適用可能である。クラスタ分割した場合には、それぞれのクラスタ内でのCentrality値を計算すればよい。クラスタ内でのCentrality値を計算することによって、Centrality値の計算規模単位を小さくすることができ、それに伴って計算処理時間の高速化、省電力化を実現することが可能となるメリットを享受できる。また、Centrality値計算への寄与が小さいネットワーク資源を省いたネットワークトポロジを構成することも可能となるため、計算処理や省電力といった観点から、より効率的な通信システム構成を実現することが可能となる。
【００４７】
以上述べた以外の動作は第２の実施形態の場合と同じである。
【００４８】
《第４の実施形態》
第２の実施形態では、Centrality値の計算手法としては、Betweenness CentralityやエントロピーベースのCentralityを用いる場合を説明したが、本発明においてCentrality値の算出に用いる手法はこれらに限定されるものではなく、Betweenness CentralityやエントロピーベースのCentrality以外のCentralityによる中心性をメトリックとしてデータ転送を行うことも考えられる。その他のCentralityとして、例えば、Degree Centrality、Closeness Centrality、Eignevector CentralityといったCentrality指標を用いてもよい。これらのCentrality値手法を適宜切り替えて使用することも可能であり、トポロジに応じて柔軟なシステム構築を行うことが可能になるというメリットも享受できる。
【００４９】
以上述べた以外の動作は第２の実施形態と同じである。
【００５０】
《その他の実施形態》
以上本発明の各実施形態について説明したが、本発明は以上の実施形態にのみ限定されず、その他、各種の付加変更が可能である。また、上述した通信装置は、その有する機能をハードウェア的に実現できることはもちろん、コンピュータとプログラムとによって実現することもできる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施形態における通信装置として機能させ、前述した処理を行わせる。
【００５１】
上記の実施形態の一部又は全部は、以下の付記のようにも記載され得るが、以下には限られない。
【００５２】
（付記１） 通信ネットワーク上のノード間の通信を行う通信装置であって、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部と、
通信相手となる前記ノードごとに、前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルと、
前記データ転送テーブルを参照し、前記メトリック切替制御部の制御に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送するデータ転送部と、
を有する通信装置。
【００５３】
（付記２） 前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、前記データ転送部に対して当該リーフノードへのデータ転送を抑止させる例外処理制御部をさらに有する、付記１に記載の通信装置。
【００５４】
（付記３） 前記メトリック切替制御部は、前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリック及び第２のメトリックのいずれかを選択する、付記１または２に記載の通信装置。
【００５５】
（付記４） 前記第２のメトリックは最短ホップ数である、付記１乃至３のいずれかに記載の通信装置。
【００５６】
（付記５） 通信ネットワーク上のノード間の通信を行う通信方法であって、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択することと、
通信相手となる前記ノードごとに前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルを参照し、前記選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送することと、
を有する通信方法。
【００５７】
（付記６） 前記通信ネットワークのトポロジ情報を収集し、収集した前記トポロジ情報に基づいて前記ノードごとに中心性を計算することと、
前記計算の結果を各ノードに配信することと、
前記計算の結果の配信を受けたノードにおいて、前記計算の結果に基づく前記第１のメトリックを前記データ転送テーブルに格納することと、
をさらに有する、付記５に記載の通信方法。
【００５８】
（付記７） 前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、当該リーフノードへのデータ転送を抑止する、付記５または６に記載の通信方法。
【００５９】
（付記８） 前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリックに基づくデータ転送制御と前記第２のメトリックに基づくデータ転送制御とのいずれかが選択される、付記５乃至７のいずれかに記載の通信方法。
【００６０】
（付記９） 前記第２のメトリックは最短ホップ数である、付記５乃至８のいずれかに記載の通信方法。
【００６１】
（付記１０） 通信ネットワーク上のノード間の通信を行うコンピュータに、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択する処理と、
通信相手となる前記ノードごとに前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルを参照し、前記選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送する処理と、
を実行させるプログラム。
【００６２】
（付記１１） 前記コンピュータに、さらに、
前記通信ネットワークのトポロジ情報を収集し、収集した前記トポロジ情報に基づいて前記ノードごとに中心性を計算する処理と、
前記計算の結果を各ノードに配信する処理と、
を実行させる付記１０に記載のプログラム。
【００６３】
（付記１２） 前記コンピュータに、前記中心性に関する計算の結果を受け取った時に、該計算の結果に基づく前記第１のメトリックを前記データ転送テーブルに格納する処理
を実行させる付記１０に記載のプログラム。
【００６４】
（付記１３） 前記コンピュータに、
前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、当該リーフノードへのデータ転送を抑止する例外制御を実行させる、付記１０乃至１２のいずれかに記載のプログラム。
【００６５】
（付記１４） 前記選択する処理は、前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリックに基づくデータ転送制御と前記第２のメトリックに基づくデータ転送制御とのいずれかを選択する処理である、付記１０乃至１３のいずれかに記載のプログラム。
【００６６】
（付記１５） 前記第２のメトリックは最短ホップ数である、付記１０乃至１４のいずれかに記載のプログラム。
【符号の説明】
【００６７】
１００，１００1〜１００6 通信ノード
１０１ 送信ノード
１０２ 宛先ノード
１０３ 代表ノード
２００ データ転送テーブル
２０１ 転送テーブル管理部
２０２ Centrality値制御部
２０３ メトリック切替制御部
２０４ 例外処理制御部
２０５ 情報記憶部
２０６ データ転送部
２０７ データ転送制御部
２０８ インタフェース
Ｓ１０１〜Ｓ１０５，Ｓ２０１〜Ｓ２０７ ステップ
【技術分野】
【０００１】
本発明は、通信ネットワーク上のノード間の通信を行う通信装置、通信方法及びプログラムに関する。
【背景技術】
【０００２】
近年、将来の新世代ネットワーク基盤を構成する方式の候補の一つとして、オーバーレイ・ネットワークが研究されている。オーバーレイ・ネットワークは、下位層となる物理ネットワーク上に論理的に構築されたネットワークであり、下位層のネットワークでのノード配置における物理的なトポロジを意識することなく、柔軟なネットワーク通信を可能にするという特長を有する。
【０００３】
図７は、関連技術におけるオーバーレイ・ネットワーク通信のためのネットワーク構成例を示している。図７では、合計で１１個の通信ノードが設けられており、図示実線で示すように物理的な接続構成を有している。隣接する通信ノード間の接続をリンクと呼ぶ。説明の都合上、これらの通信ノードのうち、２つが送信ノード１０１（すなわち送信ノードＡと送信ノードＢ）であり、別の２つが宛先ノード１０２（すなわち宛先ノードＡと宛先ノードＢ）であるとする。通信ノードのうち、送信ノード１０１と宛先ノード１０２を除いた７個の通信ノードには、それぞれ、符号１００1〜１００7が付与されている。
【０００４】
ここで上述のように１１個の通信ノード（２個の送信ノード１０１と、２個の宛先ノード１０２と、送信ノードでも宛先ノードでもない７個の通信ノード１００1〜１００7）からなる物理ネットワーク上にオーバーレイ・ネットワークを構築して、送信ノードＡから宛先ノードＡに情報を伝達し、送信ノードＢから宛先ノードＢに情報を伝達する場合を考える。送信ノードＡは、図示点線で示すように、送信ノードＡから通信ノード１００1〜１００5及び宛先ノードＢをこの順で経由して宛先ノードＡに接続するオーバーレイ・ネットワークを形成し、送信ノードＢは、図示一点鎖線で示すように、送信ノードＢから通信ノード１００3〜１００5をこの順で経由して宛先ノードＢに接続するオーバーレイ・ネットワークを形成する。このとき、一部の通信ノードやリンクは、これら２つのオーバーレイ・ネットワークで共有される物理リソースということになる。このようなオーバーレイ・ネットワークを説明する先行技術文献の一例として、非特許文献１を挙げる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris, "Resilient Overlay Networks," Proc. 18th ACM SOSP, Banff, Canada, October 2001.
【非特許文献２】F. Tutzauer, "Entropy as a measure of centrality in networks characterized by path-transfer flow,'' Social Networks, Social Networks, 29, pp. 249-265, 2007.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
このように、同一の物理的なネットワーク基盤の上に仮想的な論理ネットワークを複数重畳させて設定し、オーバーレイ・ネットワークを形成して通信を行う場合、オーバーレイ・ネットワークとしては論理的に独立していても、複数のオーバーレイ・ネットワークはノードやリンクといった物理的な資源を共有しているのが一般的である。その際、物理ネットワークでのトポロジに依存して、使われやすいノードやリンクと、使われにくいノードやリンクとが生じ、ノードやリンクにおいて使用頻度の偏りが出やすくなる。使用頻度が高く、利用が集中するノードやリンクは、より高い確率で故障しやすくなり、また、利用が集中しているノードやリンクが障害となった場合に、通信ネットワーク・システムへ与えるインパクトは非常に大きなものとなってしまう。このように、関連技術でのオーバーレイ・ネットワークでは、ノードやリンクの使用頻度に偏りがあることに起因して、耐障害性が向上しないという課題がある。ノードを構成するネットワーク機器やリンクに障害が発生した場合においても高品位な通信サービスをユーザに提供でき、かつ、ネットワーク資源の効率的な利用が可能であるようにすることが、望まれている。
【０００７】
そこで本発明の目的は、例えばオーバーレイ・ネットワークを重畳的に構成する場合などに、利用するネットワーク資源を効果的に分散させることにより耐障害性を向上させることが可能な通信システム基盤を構成するための通信装置、通信方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明の通信装置は、通信ネットワーク上のノード間の通信を行う通信装置であって、通信ネットワークのトポロジ情報に基づいてノードごとに計算された中心性に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部と、通信相手となるノードごとに、第１のメトリックと第２のメトリックとを保持するデータ転送テーブルと、データ転送テーブルを参照し、メトリック切替制御部の制御に基づき第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、その決定したノードにデータを転送するデータ転送部と、を有する。
【０００９】
本発明の通信方法は、通信ネットワーク上のノード間の通信を行う通信方法であって、通信ネットワークのトポロジ情報に基づいてノードごとに計算された中心性に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択することと、通信相手となるノードごとに第１のメトリックと第２のメトリックとを保持するデータ転送テーブルを参照し、選択に基づき第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、その決定したノードにデータを転送することと、を有する。
【００１０】
本発明のプログラムは、通信ネットワーク上のノード間の通信を行うコンピュータに、通信ネットワークのトポロジ情報に基づいてノードごとに計算された中心性に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択する処理と、通信相手となるノードごとに第１のメトリックと第２のメトリックとを保持するデータ転送テーブルを参照し、選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、その決定したノードにデータを転送する処理と、を実行させる。
【発明の効果】
【００１１】
本発明では、物理的なネットワークの構成情報や既設の論理ネットワークの構成情報に基づくトポロジ情報からノードごとに計算された中心性に基づくメトリックを活用する。中心性に基づくメトリックは、後述するように、グラフ理論等でCentrality値（中心性値）として知られている値に基づくものであり、本発明では、中心性に基づくメトリックを第１のメトリックとして使用することによって、例えばオーバーレイ・ネットワークで利用するネットワーク資源や通信トラヒックがトポロジの中心方向へ集中しないように制御し、かつ、中心性に基づくメトリックとは異なる第２のメトリックを用いるデータ転送制御との併用を行うことによって、耐障害性を向上させている。第２のメトリックとしては、例えば、最短ホップ数に基づくメトリックなどを用いることができる。このような本発明によれば、ネットワーク資源及び通信トラヒックが分散され、耐障害性を向上させた通信サービスを提供することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の第１の実施形態の通信装置の機能構成を示すブロック図である。
【図２】本発明の第２の実施形態が適用される通信ネットワークの構成の一例を示す図である。
【図３】第２の実施形態の通信装置の機能構成を示すブロック図である。
【図４】Centrality値計算処理を示すフローチャートである。
【図５】図２及び図３に示す通信装置での通信データ転送処理を示すフローチャートである。
【図６】データ転送テーブルの内容の一例を示すである。
【図７】関連技術における通信ネットワークの構成の一例を示す図である。
【発明を実施するための形態】
【００１３】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００１４】
《第１の実施形態》
図１は、本発明の第１の実施形態の通信装置を示している。一般に通信ネットワークは、複数個の通信ノードとこれらの通信ノード間を接続するリンクとから構成されているが、図１に示す通信装置は、通信ネットワーク上で、隣接する通信ノードとの間で通信を行う通信ノードにおいてデータの送受信処理を行うものとして構成されるものであり、例えば、経路制御（ルーティング）を行って、物理ネットワーク上に重畳されるオーバーレイ・ネットワークにおける通信を媒介する。
【００１５】
この通信装置は、通信ネットワークのトポロジ情報に基づいて通信ノードごとに計算された中心性すなわちCentrality値に基づく第１のメトリックと、第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部２０３と、通信相手となる通信ノードごとに、第１のメトリックと第２のメトリックとを保持するデータ転送テーブル２００と、データ転送テーブル２００を参照し、メトリック切替制御部２０３の制御に基づき第１のメトリック及び第２のメトリックのいずれかを用いて転送先の通信ノードを決定し、その決定した通信ノードにデータを転送するデータ転送部２０６と、を備えている。データ転送部２０６は、隣接する１以上の通信ノードに対し、隣接する通信ノードごとのリンクを介して接続するものである。第２のメトリックとしては、例えば、通信相手となる通信ノードまでの最短ホップ数を用いることができる。
【００１６】
通信ネットワークの構成が動的に変化しないとすれば、第１のメトリック及び第２のメトリックとも通信ネットワークの構成時に通信ノードごとに確定するものであるから、予めデータ転送テーブル２００に書き込んでおくことができる。通信ネットワークの構成が動的に変化する場合には、例えば、定期的に通信ネットワークのトポロジ情報を収集し、第１のメトリック及び第２のメトリックを算出してデータ転送テーブル２００を更新したり、他の通信ノードによって算出された第１のメトリック及び第２のメトリックを受信して、受信値によってデータ転送テーブル２００を更新したりすればよい。
【００１７】
本実施形態の通信装置は、物理的なネットワークや既設の論理ネットワークの構成情報を基にして、そのトポロジのCentrality値を第１のメトリックとして活用し、オーバーレイネットワークで利用するネットワーク資源や通信トラヒックがトポロジの中心方向へ集中しないように制御し、かつ、第２のメトリックによる通常のデータ転送制御との併用を行うことによって、耐障害性を向上させている。
【００１８】
《第２の実施形態》
図２は、第２の実施形態の通信装置が適用される通信ネットワークの構成の一例を示している。通信ネットワークでは、複数個の通信ノードがリンクを介して相互に接続している。通信ノードは、通信データを転送することが可能な端末であり、図２では、合計で１１個の通信ノードが設けられており、図示実線で示すように物理的な接続構成を有している。通信ノードの中には、データを送信する２個の送信ノード１０１（すなわち送信ノードＡと送信ノードＢ）、通信データの最終到達先である２個の宛先ノード１０２（すなわち宛先ノードＡと宛先ノードＢ）、Centrality値を計算する代表ノード１０３が含まれている。送信ノード１０１でも宛先ノード１０２でも代表ノード１０３でもない通信ノードには、符号１００1〜１００3，１００5〜１００7が付与されている。また、送信ノード１０１、宛先ノード１０２及び代表ノード１０３も含めて通信ノードを総称する場合には、符号１００を用いることとする。
【００１９】
本実施形態の通信装置は、各通信ノード１００において通信データの送受信処理を行う部分として構成されるものである。Centrality値とは、グラフ理論によって、通信ネットワークのトポロジ構成での中心性（Centrality）を示す値として算出されるものである。図２において、各通信ノードの下側に括弧書きで付記されている値が、ここで示した通信ネットワークのトポロジ構成における、各通信ノードのCentrality値の例を示している。
【００２０】
図３は、通信ノード１００の機能構成を示している。
【００２１】
通信ノード１００は、通信相手となる通信ノードとその通信ノードに対するCentrality値（第１のメトリック）と他の種類のメトリック（第２のメトリック）とを記載するデータ転送テーブル２００と、データ転送デーブル２００を管理し、特にデータ転送時にデータ転送テーブル２００へのアクセスを制御するデータ転送テーブル管理部２０１と、隣接する通信ノードおよび自通信ノードのCentrality値を保有して管理し、データ転送テーブル２００に書き込むCentrality値制御部２０２、データ転送をCentrality値ベースの制御を行うか、あるいは第２のメトリックをベースに制御するかの切り替えを制御するメトリック切替制御部２０３と、リーフノードに対してのデータ転送処理の制御などの例外的なデータ転送処理の制御を行う例外処理制御部２０４と、メトリック切り替え処理や例外処理のために利用するシステムパラメータなどの各種情報を保存する情報記憶部２０５と、他の通信ノードからデータを受信し、受信したデータを転送するデータ転送部２０６と、を備えている。データ転送テーブル２００及び情報記憶部２０５は、例えば、通信ノード１００に備えられるメモリ内の記憶領域として設けられる。データ転送テーブル２００には、通信相手となる通信ノードが、例えば、そのアドレスとその属するネットワークとによって示され、さらに、通信相手となる通信ノードごとに、Centrality値と第２のメトリックと、さらにどのインタフェースがそのネクストホップになるかが記録される。第２のメトリックとしては、例えば、最短ホップ数が用いられる。
【００２２】
データ転送部２０６は、データ転送制御部２０７と、リンクを介して他の通信ノードと接続する１または複数のインタフェース２０８と、を備えている。インタフェース２０８は、例えば、イーサネット（登録商標）によるインタフェースである。図示したものでは、Ｅ０〜Ｅ２の３つのインタフェース２０８が設けられており、このことは、図示した通信ノード１００が、最大３個の隣接する通信ノードと接続できることを意味している。データ転送制御部２０７は、いずれかのインタフェース２０８からデータを受信して転送するものであり、データを受信したときに、転送テーブル管理部２０１を介してデータ転送テーブル２００を参照し、メトリック切替制御部２０３及び例外処理制御部２０４の制御に基づきCentrality値及び第２のメトリックのいずれかを用いて転送先の通信ノードを決定し、その決定した通信ノードに対応するインタフェース２０８を介して転送する。
【００２３】
次に、本実施形態における具体的な処理について説明する。
【００２４】
まず、本実施形態における基本制御の一つとなるCentrality値の算出について説明する。Centrality値の計算処理は、図４に示すように、最初に通信ネットワーク内から代表ノード１０３を選定する処理（ステップＳ１０１）と、ステップＳ１０１の実行後、代表ノード１０３がトポロジ情報を収集する処理（ステップＳ１０２）と、ステップＳ１０２の実行後、代表ノード１０３がCentrality値を計算する処理（ステップＳ１０３）と、ステップＳ１０３の実行後、計算したCentrality値を他の各通信ノードへ配布する処理（ステップＳ１０４）と、ステップＳ１０４の実行後、各通信ノードが隣接する通信ノード間でCentrality値を情報交換する処理（ステップＳ１０５）とから構成される。
【００２５】
最初にステップＳ１０１では、通信ネットワークの中から、一つ以上の通信ノードを代表ノード１０３として選出する。この選出の手法としてはどのような手法を用いてもよく、例えば、ルーティング・プロトコルとして知られているＯＳＰＦ（Open Shortest Path First）においてセグメントごとに代表ルータ（designated router；ＤＲ）を選定する手法をそのまま用いることも可能である。あるいは、ネットワーク構築後に代表ノード１０３を選定するのではなく、予め代表ノード１０３を設置するという手法を用いてもよい。
【００２６】
ステップＳ１０２では、選定された代表ノード１０３が、通信ネットワーク内の全通信ノードから当該通信ノードのリンク接続情報を入手する。これにより、代表ノード１０３はネットワーク全体のトポロジ情報を保有することになる。
【００２７】
次にステップＳ１０３では、全体のトポロジ情報を基に、代表ノード１０３が各通信ノードのCentrality値を計算する。Centrality値の算出方法としては、いくつかの手法が知られているが、ここでは、Betweenness Centrality値の手法による計算例を以下に示す。ｇijを通信ノードｉから通信ノードｊに至る経路の数、及び
【００２８】
【数１】
【００２９】
を上述の経路のうちのノードｋを通過する経路の数とすると、このトポロジにおける通信ノードｋに対するCentrality値ｂkは以下の式で表すことができる。
【００３０】
【数２】
【００３１】
本発明において用いられるCentrality値としては、上述のようなBetweenness Centralityに限定されるものではなく、その他のCentrality値をベースとすることも可能である。一例として、非特許文献２に示されるようなエントロピーベースのCentrality値を用いることも可能である。
【００３２】
ステップＳ１０４では、代表ノード１０３が各通信ノードに対して、各通信ノードのCentrality値情報を配信する。
【００３３】
ステップＳ１０５では、全通信ノードが、自ノードと隣接する全ての通信ノードとの間でCentrality値情報を交換する。
【００３４】
以上の処理によって、全て通信ノードについてのCentrality値が計算され、それらの値が各通信ノードへ配信され、通信ノード間で必要な情報共有までが完了する。
【００３５】
次に、本実施形態におけるデータ転送制御処理について説明する。データ転送制御処理は、最初に転送データの受信を検知する処理（ステップＳ２０１）と、ステップＳ２０１の実行後、転送モードを選定する処理（ステップＳ２０２）と、ステップＳ２０２においてCentrality値モードが選択された場合に、データ転送テーブルを参照する処理（ステップＳ２０３）と、ステップＳ２０３の実行後、Centrality値ベースで転送先を選定する処理（ステップＳ２０４）と、ステップＳ２０２において通常モードが選択された場合に、データ転送テーブルを参照する処理（ステップＳ２０５）と、ステップＳ２０５の実行後、第２のメトリックベースで転送先を選定する処理（ステップＳ２０６）と、ステップＳ２０４またはＳ２０６の実行後、受信データを送信する処理（ステップＳ２０６）と、から構成されている。
【００３６】
ステップＳ２０１では、データ転送用のパケットディスクリプタなどを定期的にルックアップすることなどによって、インタフェース２０８において転送すべきデータを受信したことを検出する。
【００３７】
ステップＳ２０２では、メトリック切替制御部２０３が、データを転送する際の転送モードを確率的に選択する。ここでは、第２のメトリックとして最短ホップ数を用いることとし、Centrality値をメトリックとしてデータ転送を行うCentrality値モード、及び、最短ホップ数をメトリックとしてデータ転送を行う通常モードとを確率的に選択することを想定する。例えば、予めシステムパラメータとしてCentrality値モードと通常モードの各々の発生確率を保持しておき、一様乱数を発生させて、その発生確率に従って、転送モードを選択決定する。
【００３８】
ここで、図２に示した通信ネットワークを考えると、一例として、通信ノード１００5に保持されるデータ転送テーブル２００の内容を図６に示すようなものとなる。このデータ転送テーブル２００によれば、通信ノード１００5は、通信ネットワークにおいてそれぞれアドレスが192.168.1.1，192.168.2.1及び192.168.3.1で表される３つの通信ノードに対し、インタフェースＥ０，Ｅ１，Ｅ２を介して隣接しており、これらの隣接通信ノードのCentrality値は、それぞれ、３．０２８、２．８０６及び２．８０９である。ここで、この通信ノード１００5が、インタフェースＥ０から、宛先192.168.10.1のパケットを受信した場合を考える。
【００３９】
ステップＳ２０２においてCentrality値モードが選択された場合は、ステップＳ２０３においてデータ転送テーブル２００の内容を読み出し、ステップＳ２０４のCentrality値ベースでの転送先選定処理に移行する。インタフェースＥ０以外のインタフェースであるインタフェースＥ１，Ｅ２を介して接続された隣接通信ノードのCentrality値をみてみると、それぞれ２．８０６と２．８０９であるため、そられのCentrality値のうち、小さい方の値に対応する隣接通信ノードである192.168.2.1が転送先として選択決定される。こうすることにより、Centrality値が小さいノード（トポロジの中心から遠いノード）に対して流れるトラヒックを増加させ、Centrality値が大きいノード（トポロジの中心に近いノード）へのトラヒックを減少させることができるため、トラヒックやネットワーク資源の中央集中化を抑制することが可能となる。
【００４０】
一方、ステップＳ２０２において通常モードが選択された場合は、ステップＳ２０５においてデータ転送テーブル２００の内容を読み出し、ステップＳ２０６の他メトリックベースの転送先選定処理に移行する。宛先のネットワークである192.168.10.0/24のネクストホップがＥ２と設定されているため、転送先の通信ノードとしては、インタフェースＥ２に接続している192.168.3.1を転送先として選択決定する。仮に、この通常モードを用いずにCentrality値モードだけでの運用を行っていると、中心ではない方面へのトラヒックやネットワーク資源が逆に集中してしまうため、このように通常モードとの併用を行うことによって、その集中化を緩和して、より一層の資源の分散化を実現する。これにより耐障害性を向上させることが可能となる。
【００４１】
ステップＳ２０７では、上述のステップＳ２０４またはＳ２０６において選択決定された転送先ノードへ受信データを転送する。
【００４２】
図２に示した通信ネットワークにおいて、以上のようなデータ転送制御処理を行うと、送信ノードＡから宛先ノードＡへのデータ転送経路は、例えば、図示点線に示すように、送信ノードＡから通信ノード１００1〜１００3を経由して送信ノードＢに至り、再び通信ノード１００3に戻り、代表ノード１０３、通信ノード１００5〜１００7及び宛先ノードＢを経由して宛先ノードＡに接続するものとなる。また、送信ノードＢから宛先ノードＢへのデータ転送経路は、例えば、図示一点鎖線で示すように、送信ノードＢから通信ノード１００3、代表ノード１０３、通信ノード１００5を経由して宛先ノードＢに接続するものとなる。
【００４３】
ところで、ステップＳ２０４で選択された転送先がリーフノード、すなわち、隣接する通信ノードの数が１つである通信ノードである場合を考える。転送先はリーフノードではあるが転送データの宛先ノード自身ではない場合、Centrality値をベースとした転送を行った際には、そのリーフノードへデータ転送した後に、すぐに自通信ノードへそのデータが返送されるという経路をたどり、余計な通信経路増加を招くことになる。例えば、図２において点線で示した経路において、通信ノード１００3と送信ノードＢとの間で経路が往復で設定されているのは、このような余計な通信経路となる。そこで、本実施形態では、例外制御処理部２０４により、リーフノードを検出し、リーフノードがデータの宛先ノード自身でない場合にはリーフノードには転送しないようにデータ転送制御部２０７に指示することが好ましい。
【００４４】
以上の制御処理を行うことによって、通信ネットワークにおけるトラヒックの平滑化を実現することができ、また、オーバーレイ・ネットワークで通信を行う際の利用ネットワーク資源の分散化を実現でき、耐障害性を向上させた通信サービスを提供できる。
【００４５】
本実施形態によれば、共通な物理ネットワークの上に仮想的な論理ネットワークを重畳させてオーバーレイ・ネットワークにより通信を行うネットワークにおいて、通信トラヒックや使用するネットワーク資源の中央集中化を緩和することが可能な、耐障害性を向上させて通信システム基盤を提供することができる。
【００４６】
《第３の実施形態》
第２の実施形態では、一つの管理ドメインによって構成される通信ネットワークの場合について説明した。しかしながら本発明が適用される通信ネットワークは単一の管理ドメインを有するものに限定されるものではない。例えば、クラスタ分割を行うことによって複数のネットワークに分割した実施形態としても本発明は適用可能である。クラスタ分割した場合には、それぞれのクラスタ内でのCentrality値を計算すればよい。クラスタ内でのCentrality値を計算することによって、Centrality値の計算規模単位を小さくすることができ、それに伴って計算処理時間の高速化、省電力化を実現することが可能となるメリットを享受できる。また、Centrality値計算への寄与が小さいネットワーク資源を省いたネットワークトポロジを構成することも可能となるため、計算処理や省電力といった観点から、より効率的な通信システム構成を実現することが可能となる。
【００４７】
以上述べた以外の動作は第２の実施形態の場合と同じである。
【００４８】
《第４の実施形態》
第２の実施形態では、Centrality値の計算手法としては、Betweenness CentralityやエントロピーベースのCentralityを用いる場合を説明したが、本発明においてCentrality値の算出に用いる手法はこれらに限定されるものではなく、Betweenness CentralityやエントロピーベースのCentrality以外のCentralityによる中心性をメトリックとしてデータ転送を行うことも考えられる。その他のCentralityとして、例えば、Degree Centrality、Closeness Centrality、Eignevector CentralityといったCentrality指標を用いてもよい。これらのCentrality値手法を適宜切り替えて使用することも可能であり、トポロジに応じて柔軟なシステム構築を行うことが可能になるというメリットも享受できる。
【００４９】
以上述べた以外の動作は第２の実施形態と同じである。
【００５０】
《その他の実施形態》
以上本発明の各実施形態について説明したが、本発明は以上の実施形態にのみ限定されず、その他、各種の付加変更が可能である。また、上述した通信装置は、その有する機能をハードウェア的に実現できることはもちろん、コンピュータとプログラムとによって実現することもできる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施形態における通信装置として機能させ、前述した処理を行わせる。
【００５１】
上記の実施形態の一部又は全部は、以下の付記のようにも記載され得るが、以下には限られない。
【００５２】
（付記１） 通信ネットワーク上のノード間の通信を行う通信装置であって、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部と、
通信相手となる前記ノードごとに、前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルと、
前記データ転送テーブルを参照し、前記メトリック切替制御部の制御に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送するデータ転送部と、
を有する通信装置。
【００５３】
（付記２） 前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、前記データ転送部に対して当該リーフノードへのデータ転送を抑止させる例外処理制御部をさらに有する、付記１に記載の通信装置。
【００５４】
（付記３） 前記メトリック切替制御部は、前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリック及び第２のメトリックのいずれかを選択する、付記１または２に記載の通信装置。
【００５５】
（付記４） 前記第２のメトリックは最短ホップ数である、付記１乃至３のいずれかに記載の通信装置。
【００５６】
（付記５） 通信ネットワーク上のノード間の通信を行う通信方法であって、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択することと、
通信相手となる前記ノードごとに前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルを参照し、前記選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送することと、
を有する通信方法。
【００５７】
（付記６） 前記通信ネットワークのトポロジ情報を収集し、収集した前記トポロジ情報に基づいて前記ノードごとに中心性を計算することと、
前記計算の結果を各ノードに配信することと、
前記計算の結果の配信を受けたノードにおいて、前記計算の結果に基づく前記第１のメトリックを前記データ転送テーブルに格納することと、
をさらに有する、付記５に記載の通信方法。
【００５８】
（付記７） 前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、当該リーフノードへのデータ転送を抑止する、付記５または６に記載の通信方法。
【００５９】
（付記８） 前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリックに基づくデータ転送制御と前記第２のメトリックに基づくデータ転送制御とのいずれかが選択される、付記５乃至７のいずれかに記載の通信方法。
【００６０】
（付記９） 前記第２のメトリックは最短ホップ数である、付記５乃至８のいずれかに記載の通信方法。
【００６１】
（付記１０） 通信ネットワーク上のノード間の通信を行うコンピュータに、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択する処理と、
通信相手となる前記ノードごとに前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルを参照し、前記選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送する処理と、
を実行させるプログラム。
【００６２】
（付記１１） 前記コンピュータに、さらに、
前記通信ネットワークのトポロジ情報を収集し、収集した前記トポロジ情報に基づいて前記ノードごとに中心性を計算する処理と、
前記計算の結果を各ノードに配信する処理と、
を実行させる付記１０に記載のプログラム。
【００６３】
（付記１２） 前記コンピュータに、前記中心性に関する計算の結果を受け取った時に、該計算の結果に基づく前記第１のメトリックを前記データ転送テーブルに格納する処理
を実行させる付記１０に記載のプログラム。
【００６４】
（付記１３） 前記コンピュータに、
前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、当該リーフノードへのデータ転送を抑止する例外制御を実行させる、付記１０乃至１２のいずれかに記載のプログラム。
【００６５】
（付記１４） 前記選択する処理は、前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリックに基づくデータ転送制御と前記第２のメトリックに基づくデータ転送制御とのいずれかを選択する処理である、付記１０乃至１３のいずれかに記載のプログラム。
【００６６】
（付記１５） 前記第２のメトリックは最短ホップ数である、付記１０乃至１４のいずれかに記載のプログラム。
【符号の説明】
【００６７】
１００，１００1〜１００6 通信ノード
１０１ 送信ノード
１０２ 宛先ノード
１０３ 代表ノード
２００ データ転送テーブル
２０１ 転送テーブル管理部
２０２ Centrality値制御部
２０３ メトリック切替制御部
２０４ 例外処理制御部
２０５ 情報記憶部
２０６ データ転送部
２０７ データ転送制御部
２０８ インタフェース
Ｓ１０１〜Ｓ１０５，Ｓ２０１〜Ｓ２０７ ステップ
【特許請求の範囲】
【請求項１】
通信ネットワーク上のノード間の通信を行う通信装置であって、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部と、
通信相手となる前記ノードごとに、前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルと、
前記データ転送テーブルを参照し、前記メトリック切替制御部の制御に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送するデータ転送部と、
を有する通信装置。
【請求項２】
前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、前記データ転送部に対して当該リーフノードへのデータ転送を抑止させる例外処理制御部をさらに有する、請求項１に記載の通信装置。
【請求項３】
前記メトリック切替制御部は、前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリック及び第２のメトリックのいずれかを選択する、請求項１または２に記載の通信装置。
【請求項４】
通信ネットワーク上のノード間の通信を行う通信方法であって、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択することと、
通信相手となる前記ノードごとに前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルを参照し、前記選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送することと、
を有する通信方法。
【請求項５】
前記通信ネットワークのトポロジ情報を収集し、収集した前記トポロジ情報に基づいて前記ノードごとに中心性を計算することと、
前記計算の結果を各ノードに配信することと、
前記計算の結果の配信を受けたノードにおいて、前記計算の結果に基づく前記第１のメトリックを前記データ転送テーブルに格納することと、
をさらに有する、請求項４に記載の通信方法。
【請求項６】
前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、当該リーフノードへのデータ転送を抑止する、請求項４または５に記載の通信方法。
【請求項７】
前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリックに基づくデータ転送制御と前記第２のメトリックに基づくデータ転送制御とのいずれかが選択される、請求項４乃至６のいずれかに記載の通信方法。
【請求項８】
通信ネットワーク上のノード間の通信を行うコンピュータに、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択する処理と、
通信相手となる前記ノードごとに前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルを参照し、前記選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送する処理と、
を実行させるプログラム。
【請求項９】
前記コンピュータに、さらに、
前記通信ネットワークのトポロジ情報を収集し、収集した前記トポロジ情報に基づいて前記ノードごとに中心性を計算する処理と、
前記計算の結果を各ノードに配信する処理と、
を実行させる請求項８に記載のプログラム。
【請求項１０】
前記コンピュータに、
前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、当該リーフノードへのデータ転送を抑止する例外制御を実行させる、請求項８または９に記載のプログラム。
【請求項１】
通信ネットワーク上のノード間の通信を行う通信装置であって、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択するメトリック切替制御部と、
通信相手となる前記ノードごとに、前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルと、
前記データ転送テーブルを参照し、前記メトリック切替制御部の制御に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送するデータ転送部と、
を有する通信装置。
【請求項２】
前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、前記データ転送部に対して当該リーフノードへのデータ転送を抑止させる例外処理制御部をさらに有する、請求項１に記載の通信装置。
【請求項３】
前記メトリック切替制御部は、前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリック及び第２のメトリックのいずれかを選択する、請求項１または２に記載の通信装置。
【請求項４】
通信ネットワーク上のノード間の通信を行う通信方法であって、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択することと、
通信相手となる前記ノードごとに前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルを参照し、前記選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送することと、
を有する通信方法。
【請求項５】
前記通信ネットワークのトポロジ情報を収集し、収集した前記トポロジ情報に基づいて前記ノードごとに中心性を計算することと、
前記計算の結果を各ノードに配信することと、
前記計算の結果の配信を受けたノードにおいて、前記計算の結果に基づく前記第１のメトリックを前記データ転送テーブルに格納することと、
をさらに有する、請求項４に記載の通信方法。
【請求項６】
前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、当該リーフノードへのデータ転送を抑止する、請求項４または５に記載の通信方法。
【請求項７】
前記第１のメトリックを選択する確率と前記第２のメトリックを選択する確率とが与えられて、乱数により、前記第１のメトリックに基づくデータ転送制御と前記第２のメトリックに基づくデータ転送制御とのいずれかが選択される、請求項４乃至６のいずれかに記載の通信方法。
【請求項８】
通信ネットワーク上のノード間の通信を行うコンピュータに、
前記通信ネットワークのトポロジ情報に基づいて前記ノードごとに計算された中心性に基づく第１のメトリックと、前記第１のメトリックとは異なる第２のメトリックとのいずれに基づいてデータ転送制御を行うかを選択する処理と、
通信相手となる前記ノードごとに前記第１のメトリックと前記第２のメトリックとを保持するデータ転送テーブルを参照し、前記選択に基づき前記第１のメトリック及び第２のメトリックのいずれかを用いて転送先のノードを決定し、該決定したノードにデータを転送する処理と、
を実行させるプログラム。
【請求項９】
前記コンピュータに、さらに、
前記通信ネットワークのトポロジ情報を収集し、収集した前記トポロジ情報に基づいて前記ノードごとに中心性を計算する処理と、
前記計算の結果を各ノードに配信する処理と、
を実行させる請求項８に記載のプログラム。
【請求項１０】
前記コンピュータに、
前記第１のメトリックに基づくデータ転送制御が選択され、かつリーフノードが宛先ノードではない場合に、当該リーフノードへのデータ転送を抑止する例外制御を実行させる、請求項８または９に記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１３−６２６６３（Ｐ２０１３−６２６６３Ａ）
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【出願番号】特願２０１１−１９９５１９（Ｐ２０１１−１９９５１９）
【出願日】平成２３年９月１３日（２０１１．９．１３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、独立行政法人情報通信研究機構「ダイナミックネットワーク技術の研究開発」は産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【出願日】平成２３年９月１３日（２０１１．９．１３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、独立行政法人情報通信研究機構「ダイナミックネットワーク技術の研究開発」は産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]