ネットワークトポロジー生成方法及びノード
本発明は、物理層のネットワーク状況を考慮することによって、新たにネットワークトポロジーを生成するにあたって、ネットワーク遅延を平均的にかつ最小限に抑制することが可能なネットワークトポロジー生成方法を提供する。本発明に係るネットワークトポロジー生成方法は、新規ノードXが、複数のノードA乃至Dとの間でバーチャルコネクション#1乃至#4を確立する工程と、新規ノードXが、各バーチャルコネクション#1乃至#4を介した複数のノード#1乃至#4までの経路#A1乃至#A4〜#D1乃至#D4の平均メトリック値を算出する工程と、新規ノードXが、経路の平均メトリック値が最小となるバーチャルコネクション#1が確立されたノードDに対してコネクションを確立することによってネットワークに参加する工程とを有する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、複数のノードによって構成されるネットワークに新規ノードが参加するネットワークトポロジー生成方法に関する。また、本発明は、複数のノードによって構成されるネットワークに新規に参加するノードに関する。
【背景技術】
【0002】
図1乃至図5を参照して、従来のネットワークトポロジーの生成方法(Gnutellaで使用されている方法)について説明する。具体的には、ノード105が、ノード101乃至104を含むネットワークに新規に参加する動作について説明する。
【0003】
第1に、図1に示すように、ノード105は、ネットワークを構成する複数のノード101乃至104の中から、IPアドレス又はURLを知っているノード101との間でコネクションを確立する。
【0004】
第2に、図2に示すように、ノード105は、ノード101に対して、ノード105のIPアドレスを含むPingメッセージを送信する。
【0005】
第3に、図3に示すように、ノード101は、ノード101のIPアドレスを含むPongメッセージをノード105に返信するとともに、ノード105のIPアドレスを含むPingメッセージをノード102乃至104に転送する。
【0006】
第4に、図4に示すように、各ノード102乃至104は、それぞれのIPアドレスを含むPongメッセージをノード105に返信する。
【0007】
以上の手順が繰り返されることによって、ノード105は、PingメッセージのTTL(Time To Live)フィールドに指定された範囲内のノードのIPアドレスを取得することができる。
【0008】
第5に、図5に示すように、ノード105は、受信したPongメッセージに含まれるIPアドレスを参照して、ネットワークを構成するノード101乃至104の各々とコネクションを確立する。
【0009】
このようにして、ノード105は、ノード101乃至104によって構成されているネットワークに新規に参加することができる。
【0010】
上述のように、従来のネットワークトポロジーの生成方法では、新規ノード105は、Pingメッセージ及びPongメッセージを利用して、ランダム的にネットワークに参加するように構成されていた。
【0011】
しかしながら、従来のネットワークトポロジーの生成方法では、新たにネットワークトポロジーを生成するにあたって、物理層のネットワーク状況を考慮していないため、論理層において隣接するノード間であっても、ネットワーク遅延が相当大きい可能性があり、新規に生成されたネットワークにおいてデータ転送効率が低下する可能性があるという問題点があった。
【0012】
【特許文献0001】特開2003−304277号公報
そこで、本発明は、以上の点に鑑みてなされたもので、物理層のネットワーク状況を考慮することによって、新たにネットワークトポロジーを生成するにあたって、ネットワーク遅延を平均的にかつ最小限に抑制することが可能なネットワークトポロジー生成方法及びノードを提供することを目的とする。
【発明の開示】
【0013】
本発明の第1の特徴は、複数のノードによって構成されるネットワークに新規に参加するノードであって、前記複数のノードとの間でバーチャルコネクションを確立するバーチャルコネクション確立部と、各バーチャルコネクションを介した前記複数のノードまでの経路の平均メトリック値を算出する平均メトリック値算出部と、前記経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立することによって、前記ネットワークに参加するコネクション確立部とを具備することを要旨とする。
【0014】
かかる発明によれば、コネクション確立部が、物理層のネットワーク状況を考慮して算出される平均メトリック値が最小となるように、バーチャルコネクションが確立されたノードに対してコネクションを確立するため、新たにネットワークトポロジーを生成するにあたって、ネットワーク遅延を平均的にかつ最小限に抑制することができる。
【0015】
本発明の第1の特徴において、前記ネットワーク内の任意のノードから、該任意のノードの隣接ノードに係るノード間接続情報を取得する取得部をさらに具備し、前記平均メトリック値算出部が、前記ノード間接続情報を用いて前記平均メトリック値を算出するように構成されていてもよい。
【0016】
本発明の第1の特徴において、前記ノード間接続情報が、前記隣接ノードを識別するためのノードIDと、前記任意のノードと前記隣接ノードとの間の経路のメトリック値と、前記隣接ノードに隣接するノード数とを含むように構成されていてもよい。
【0017】
本発明の第1の特徴において、前記メトリック値が、ホップ数、ネットワーク帯域幅、通信コスト、遅延、負荷、MTU、信頼性の少なくとも一つを含むように構成されていてもよい。
【0018】
本発明の第1の特徴において、前記取得部が、前記任意のノードに対して、前記ノード間接続情報に含まれるべきメトリック値又はメトリック値の組み合わせの種類を通知するように構成されていてもよい。
【0019】
本発明の第2の特徴は、複数のノードによって構成されるネットワークに新規ノードが参加するネットワークトポロジー生成方法であって、前記新規ノードが、前記複数のノードとの間でバーチャルコネクションを確立する工程と、前記新規ノードが、各バーチャルコネクションを介した前記複数のノードまでの経路の平均メトリック値を算出する工程と、前記新規ノードが、前記経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立することによって、前記ネットワークに参加する工程とを有することを要旨とする。
【図面の簡単な説明】
【0020】
【図1】図1は、従来技術において、ノード105がノード101との間でコネクションを確立する動作を示す図である。
【図2】図2は、従来技術において、ノード105がノード101に対してPingメッセージを送信する動作を示す図である。
【図3】図3は、従来技術において、ノード101がノード104に対してPongメッセージを送信するとともに、各ノード102乃至104に対してPingメッセージを送信する動作を示す図である。
【図4】図4は、従来技術において、ノード102乃至104がノード101に対してPongメッセージを送信する動作を示す図である。
【図5】図5は、従来技術において、ノード101がノード102乃至104との間でコネクションを確立する動作を示す図である。
【図6A】図6Aは、本発明の一実施形態に係るノードXの機能ブロック図である。
【図6B】図6Bは、本発明の一実施形態に係るノードAの機能ブロック図である。
【図7】図7は、本発明の一実施形態に係るノードXがネットワークに新規に参加する動作を示すフローチャートである。
【図8】図8は、本発明の一実施形態に係るノードXがノードAからノード間接続情報を取得する動作を示す図である。
【図9】図9は、本発明の一実施形態に係るノードXによって取得されるノード間接続情報の一例を示す図である。
【図10】図10は、本発明の一実施形態に係るノードXがノードA乃至Dとの間にバーチャルコネクションを確立する動作を示す図である。
【図11】図11は、本発明の一実施形態に係るノードXがノードDとの間に確立したバーチャルコネクションを介したノードXからノードA乃至Dまでの経路情報を示す図である。
【図12】図12は、本発明の一実施形態に係るノードXがノードAとの間に確立したバーチャルコネクションを介したノードXからノードA乃至Dまでの経路情報を示す図である。
【図13】図13は、本発明の一実施形態に係るノードXがノードBとの間に確立したバーチャルコネクションを介したノードXからノードA乃至Dまでの経路情報を示す図である。
【図14】図14は、本発明の一実施形態に係るノードXがノードCとの間に確立したバーチャルコネクションを介したノードXからノードA乃至Dまでの経路情報を示す図である。
【図15】図15は、本発明の一実施形態に係るノードXが各バーチャルコネクションを介したノードA乃至Dまでの経路の平均メトリック値を算出する計算式を示す図である。
【図16】図16は、本発明の一実施形態に係るノードXが各バーチャルコネクションを介したノードA乃至Dまでの経路の平均メトリック値を算出する一例を示す図である。
【図17】図17は、本発明の一実施形態に係るノードXがノードDとの間にコネクションを確立する動作を示す図である。
【発明を実施するための最良の形態】
【0021】
(本発明の第1の実施形態に係るネットワークトポロジー生成方法を実現するノードの構成)
以下、図6A及び図6Bを参照して、本発明の第1の実施形態に係るネットワークトポロジー生成方法を実現するノードの構成について説明する。本実施形態において、ノードXは、複数のノードA乃至Dを含むネットワークに新規に参加することができるように構成されている。
【0022】
図6Aに示すように、本実施形態に係るノードXは、ノード間接続情報取得部11と、バーチャルコネクション確立部12と、平均メトリック値算出部13と、コネクション確立部14と、メトリック値指定部15とを具備している。
【0023】
ノード間接続情報取得部11は、ネットワーク内の任意のノード(例えば、ノードA)から、当該任意のノードの隣接ノード(例えば、ノードB乃至D)に係るノード間接続情報を取得するものである。なお、ノード間情報には、隣接ノードを識別するための「ノード名(ノードID)」と、隣接ノードの「ノードアドレス(例えば、IPアドレス)」と、任意のノードと隣接ノードとの間の経路の「メトリック値」と、隣接ノードに隣接する「ノード数」とを含む。また、「メトリック値」は、ホップ数、ネットワーク帯域幅、通信コスト、遅延、負荷、MTU、信頼性の少なくとも一つを含む。
【0024】
ここで、ホップ数は、物理層におけるホップ数、すなわち、当該ノードとの間で確立されているリンクにおけるルータ等のホップ数を示す。ネットワーク帯域幅は、当該ノードとの間で確立されているリンクにおいて使用可能な通信帯域(例えば、64kbps等)を示す。通信コストは、当該ノードとの間で確立されているリンクの通信料金を示す。遅延は、当該ノードとの間で確立されているリンクにおける伝播遅延時間を示す。負荷は、当該ノードとの間で確立されているリンクの使用状況(例えば、50%等)を示す。MTUは、当該ノードとの間で確立されているリンクにおいて使用される最小転送ブロックサイズ(Minimum Transfer Unit)を示す。信頼性は、当該ノードとの間で確立されているリンクにおける障害発生率をしめす。
【0025】
ノード間接続情報取得部11は、ネットワーク内の任意のノードからノード間情報を取得する際に、メトリック値指定部15によって指定されたメトリック値(又は、メトリック値の組み合わせ)の種類を通知するように構成されていてもよい。
【0026】
バーチャルコネクション確立部12は、ノード間接続情報取得部11によって取得したノード間接続情報内のノードアドレスを参照して、複数のノードA乃至Dとの間でバーチャルコネクションを確立するものである。
【0027】
平均メトリック値算出部13は、ノード間接続情報取得部11によって取得したノード間接続情報を利用して、各バーチャルコネクションを介した複数のノードまでの経路の平均メトリック値を算出するものである。なお、当該平均メトリック値の具体的な算出方法については後述する。
【0028】
コネクション確立部14は、経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立するものである。
【0029】
メトリック値指定部15は、ノードXがネットワークに新規に参加する際に、任意のノードから取得するノード間接続情報に含まれるべきメトリック値(又は、メトリック値の組み合わせ)の種類を指定するものである。なお、メトリック値指定部15によって所定のメトリック値が指定されない場合、任意のノードによって提供されるノード間接続情報には、デフォルトで設定されたメトリック値(又は、メトリック値の組み合わせ)が含まれる。
【0030】
図6Bに示すように、本実施形態に係るノードAは、ノード間接続情報取得部31と、ノード間接続情報記憶部32と、バーチャルコネクション確立部33と、ノード間接続情報提供部34と、コネクション確立部35とを具備している。
【0031】
ノード間接続情報取得部31は、ネットワーク内において、当該ノードXに隣接する隣接ノード(例えば、ノードB乃至D)から、当該隣接ノードに係るノード間接続情報を取得するものである。なお、各ノード間のリンクにおけるメトリック値は適宜更新されている。
【0032】
例えば、ノード間接続情報取得部31は、更新通知パケットを、ネットワーク内の全ノードにブロードキャストすることによって、定期的にノード間接続情報の更新結果を取得するように構成されていてもよい。
【0033】
また、ノード間接続情報取得部31は、TTL(Time To Live)を設定した範囲に更新通知パケットを送信することによって、定期的にノード間接続情報の更新結果を取得するように構成されていてもよい。
【0034】
ノード間接続情報記憶部32は、ノード間接続情報取得部31によって取得されたノード間接続情報を記憶するものである。
【0035】
バーチャルコネクション確立部33は、ノードXからのバーチャルコネクション確立要求に応じて、ノードXとの間でバーチャルコネクションを確立するものである。
【0036】
ノード間接続情報提供部34は、ノード間接続情報記憶部32からノードAに隣接する隣接ノードに係るノード間接続情報を取得して、バーチャルコネクション確立部33によって確立されたノードXとの間のバーチャルコネクションを介して当該ノード間接続情報をノードXに提供するものである。
【0037】
ノード間接続情報提供部34は、ノードXによってメトリック値(又は、メトリック値の組み合わせ)の種類が通知された場合、かかるメトリック値(又は、メトリック値の組み合わせ)を含むノード間接続情報を提供するように構成されていてもよい。
【0038】
また、ノード間接続情報提供部34は、ノードXによってメトリック値(又は、メトリック値の組み合わせ)の種類が通知されなかった場合、デフォルトで設定されているメトリック値(又は、メトリック値の組み合わせ)を含むノード間接続情報を提供するように構成されていてもよい。
【0039】
コネクション確立部35は、ノードXからのコネクション確立要求に応じて、ノードXとの間でバーチャルコネクションを確立するものである。
【0040】
(本実施形態に係るネットワークトポロジー生成方法の動作)
図7乃至図17を参照して、本実施形態に係るネットワークトポロジー生成方法の動作について説明する。具体的には、ノードXが、ノードA乃至Dを含むネットワークに新規に参加する際の動作について説明する。
【0041】
図7及び図8に示すように、ステップS1において、ノードXのノード間接続情報取得部11が、ノードAから、ノードAが管理しているノード間接続情報を取得する。ここで、ノードXのノード間接続情報取得部11は、取得するノード間接続情報に含まれるべきメトリック値(又は、メトリック値の組み合わせ)の種類を通知するように構成されていてもよい。
【0042】
図9に、本実施形態において、ノードAが管理しているノード間接続情報を示す。図9に示すように、ノードAの隣接ノードは、ノードB乃至Dである。なお、ノードBのノードアドレスは「BIP」であり、ノードCのノードアドレスは「CIP」であり、ノードDのノードアドレスは「DIP」である。また、ノードAとノードBとの間のメトリック値は「2」であり、ノードAとノードCとの間のメトリック値は「3」であり、ノードAとノードDとの間のメトリック値は「2」である。また、ノードBに隣接するノード数は「2」であり、ノードCに隣接するノード数は「2」であり、ノードDに隣接するノード数は「3」である。
【0043】
図7及び図10に示すように、ステップS2において、ノードXのバーチャルコネクション確立部12が、取得したノード間接続情報に含まれる「ノードアドレス」に基づいて、ノードA乃至Dとの間でバーチャルコネクションを確立する。
【0044】
ステップS3において、ノードXの平均メトリック値算出部13が、取得したノード間接続情報に含まれる「メトリック値」及び「ノード数」に基づいて、各バーチャルコネクションを経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値を算出する。
【0045】
具体的には、以下のように、平均メトリック値を算出する。なお、ノードXとノードDとの間に確立されたバーチャルコネクション#1のメトリック値は「1」であり、ノードXとノードAとの間に確立されたバーチャルコネクション#2のメトリック値は「5」であり、ノードXとノードBとの間に確立されたバーチャルコネクション#3のメトリック値は「3」であり、ノードXとノードCとの間に確立されたバーチャルコネクション#4のメトリック値は「1」である者とする。
【0046】
図11は、バーチャルコネクション#1を経由してノードXからノードA乃至Dの各々に到達する経路#A1乃至#D1における「メトリック値」及び各ノードA乃至Dに隣接する「ノード数」を関連付ける経路情報を示す。
【0047】
また、図12は、バーチャルコネクション#2を経由してノードXからノードA乃至Dの各々に到達する経路#A2乃至#D2における「メトリック値」及び各ノードA乃至Dに隣接する「ノード数」を関連付ける経路情報を示す。
【0048】
また、図13は、バーチャルコネクション#3を経由してノードXからノードA乃至Dの各々に到達する経路#A3乃至#D3における「メトリック値」及び各ノードA乃至Dに隣接する「ノード数」を関連付ける経路情報を示す。
【0049】
さらに、図14は、バーチャルコネクション#4を経由してノードXからノードA乃至Dの各々に到達する経路#A4乃至#D4における「メトリック値」及び各ノードA乃至Dに隣接する「ノード数」を関連付ける経路情報を示す。
【0050】
ノードXの平均メトリック値算出部13は、図11乃至図14に示す経路情報を用いて、図15に示す計算式によって、各バーチャルコネクション#1乃至#4を経由してノードXからノードiに到達する経路の平均メトリック値Viを算出する。図15に示す計算式において、nは、ネットワークに属する総ノード数を示し、VMiは、ノードXからノードiまで到達する経路のメトリック値を示し、Niは、ノードiの隣接ノード数に1を加えた値を示す。ここで、ノードAは、ノード1に該当し、ノードBは、ノード2に該当し、ノードCは、ノード3に該当し、ノードDは、ノード4に該当するものとする。
【0051】
図16は、本実施形態において、ノードXの平均メトリック値算出部13が、図11乃至図14に示す経路情報を参照して、各バーチャルコネクション#1乃至#4を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値を算出する様子の一例を示す。
【0052】
図16に示すように、ノードXがノードAとの間に確立したバーチャルコネクション#2を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値は「78/11」であり、ノードXがノードBとの間に確立したバーチャルコネクション#3を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値は「59/11」であり、ノードXがノードCとの間に確立したバーチャルコネクション#4を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値は「50/11」であり、ノードXがノードDとの間に確立したバーチャルコネクション#1を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値は「40/11」である。
【0053】
この結果に基づいて、ステップS4において、図17に示すように、ノードXのコネクション確立部14は、上述の経路の平均メトリック値が最小(「40/11」)であるバーチャルコネクション#1が確立されたノードDに対して、コネクションを確立することによって、ネットワークに新規に参加する。この結果、ネットワークトポロジーが変更される。すなわち、ノードXは、バーチャルコネクション#1を経由してノードA乃至D等を含むネットワーク内の全てのノードとの間で通信を行うことができる。
【0054】
(本実施形態に係るネットワークトポロジー生成方法の作用・効果)
本実施形態に係るネットワークトポロジー生成方法によれば、ノードXのコネクション確立部14が、物理層のネットワーク状況を考慮して算出される平均メトリック値が最小となるように、バーチャルコネクション#1が確立されたノードDに対してコネクションを確立するため、新たにネットワークトポロジーを生成するにあたって、ネットワーク遅延を平均的にかつ最小限に抑制することができる。
【0055】
以上、本発明を実施例により詳細に説明したが、当業者にとっては、本発明が本願中に説明した実施例に限定されるものではないということは明らかである。本発明の装置は、特許請求の範囲の記載により定まる本発明の趣旨及び範囲を逸脱することなく修正及び変更態様として実施することができる。従って、本願の記載は、例示説明を目的とするものであり、本発明に対して何ら制限的な意味を有するものではない。
【産業上の利用可能性】
【0056】
以上説明したように、本発明によれば、物理層のネットワーク状況を考慮することによって、新たにネットワークトポロジーを生成するにあたって、ネットワーク遅延を平均的にかつ最小限に抑制することが可能なネットワークトポロジーの生成方法及びノードを提供することができる。
【技術分野】
【0001】
本発明は、複数のノードによって構成されるネットワークに新規ノードが参加するネットワークトポロジー生成方法に関する。また、本発明は、複数のノードによって構成されるネットワークに新規に参加するノードに関する。
【背景技術】
【0002】
図1乃至図5を参照して、従来のネットワークトポロジーの生成方法(Gnutellaで使用されている方法)について説明する。具体的には、ノード105が、ノード101乃至104を含むネットワークに新規に参加する動作について説明する。
【0003】
第1に、図1に示すように、ノード105は、ネットワークを構成する複数のノード101乃至104の中から、IPアドレス又はURLを知っているノード101との間でコネクションを確立する。
【0004】
第2に、図2に示すように、ノード105は、ノード101に対して、ノード105のIPアドレスを含むPingメッセージを送信する。
【0005】
第3に、図3に示すように、ノード101は、ノード101のIPアドレスを含むPongメッセージをノード105に返信するとともに、ノード105のIPアドレスを含むPingメッセージをノード102乃至104に転送する。
【0006】
第4に、図4に示すように、各ノード102乃至104は、それぞれのIPアドレスを含むPongメッセージをノード105に返信する。
【0007】
以上の手順が繰り返されることによって、ノード105は、PingメッセージのTTL(Time To Live)フィールドに指定された範囲内のノードのIPアドレスを取得することができる。
【0008】
第5に、図5に示すように、ノード105は、受信したPongメッセージに含まれるIPアドレスを参照して、ネットワークを構成するノード101乃至104の各々とコネクションを確立する。
【0009】
このようにして、ノード105は、ノード101乃至104によって構成されているネットワークに新規に参加することができる。
【0010】
上述のように、従来のネットワークトポロジーの生成方法では、新規ノード105は、Pingメッセージ及びPongメッセージを利用して、ランダム的にネットワークに参加するように構成されていた。
【0011】
しかしながら、従来のネットワークトポロジーの生成方法では、新たにネットワークトポロジーを生成するにあたって、物理層のネットワーク状況を考慮していないため、論理層において隣接するノード間であっても、ネットワーク遅延が相当大きい可能性があり、新規に生成されたネットワークにおいてデータ転送効率が低下する可能性があるという問題点があった。
【0012】
【特許文献0001】特開2003−304277号公報
そこで、本発明は、以上の点に鑑みてなされたもので、物理層のネットワーク状況を考慮することによって、新たにネットワークトポロジーを生成するにあたって、ネットワーク遅延を平均的にかつ最小限に抑制することが可能なネットワークトポロジー生成方法及びノードを提供することを目的とする。
【発明の開示】
【0013】
本発明の第1の特徴は、複数のノードによって構成されるネットワークに新規に参加するノードであって、前記複数のノードとの間でバーチャルコネクションを確立するバーチャルコネクション確立部と、各バーチャルコネクションを介した前記複数のノードまでの経路の平均メトリック値を算出する平均メトリック値算出部と、前記経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立することによって、前記ネットワークに参加するコネクション確立部とを具備することを要旨とする。
【0014】
かかる発明によれば、コネクション確立部が、物理層のネットワーク状況を考慮して算出される平均メトリック値が最小となるように、バーチャルコネクションが確立されたノードに対してコネクションを確立するため、新たにネットワークトポロジーを生成するにあたって、ネットワーク遅延を平均的にかつ最小限に抑制することができる。
【0015】
本発明の第1の特徴において、前記ネットワーク内の任意のノードから、該任意のノードの隣接ノードに係るノード間接続情報を取得する取得部をさらに具備し、前記平均メトリック値算出部が、前記ノード間接続情報を用いて前記平均メトリック値を算出するように構成されていてもよい。
【0016】
本発明の第1の特徴において、前記ノード間接続情報が、前記隣接ノードを識別するためのノードIDと、前記任意のノードと前記隣接ノードとの間の経路のメトリック値と、前記隣接ノードに隣接するノード数とを含むように構成されていてもよい。
【0017】
本発明の第1の特徴において、前記メトリック値が、ホップ数、ネットワーク帯域幅、通信コスト、遅延、負荷、MTU、信頼性の少なくとも一つを含むように構成されていてもよい。
【0018】
本発明の第1の特徴において、前記取得部が、前記任意のノードに対して、前記ノード間接続情報に含まれるべきメトリック値又はメトリック値の組み合わせの種類を通知するように構成されていてもよい。
【0019】
本発明の第2の特徴は、複数のノードによって構成されるネットワークに新規ノードが参加するネットワークトポロジー生成方法であって、前記新規ノードが、前記複数のノードとの間でバーチャルコネクションを確立する工程と、前記新規ノードが、各バーチャルコネクションを介した前記複数のノードまでの経路の平均メトリック値を算出する工程と、前記新規ノードが、前記経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立することによって、前記ネットワークに参加する工程とを有することを要旨とする。
【図面の簡単な説明】
【0020】
【図1】図1は、従来技術において、ノード105がノード101との間でコネクションを確立する動作を示す図である。
【図2】図2は、従来技術において、ノード105がノード101に対してPingメッセージを送信する動作を示す図である。
【図3】図3は、従来技術において、ノード101がノード104に対してPongメッセージを送信するとともに、各ノード102乃至104に対してPingメッセージを送信する動作を示す図である。
【図4】図4は、従来技術において、ノード102乃至104がノード101に対してPongメッセージを送信する動作を示す図である。
【図5】図5は、従来技術において、ノード101がノード102乃至104との間でコネクションを確立する動作を示す図である。
【図6A】図6Aは、本発明の一実施形態に係るノードXの機能ブロック図である。
【図6B】図6Bは、本発明の一実施形態に係るノードAの機能ブロック図である。
【図7】図7は、本発明の一実施形態に係るノードXがネットワークに新規に参加する動作を示すフローチャートである。
【図8】図8は、本発明の一実施形態に係るノードXがノードAからノード間接続情報を取得する動作を示す図である。
【図9】図9は、本発明の一実施形態に係るノードXによって取得されるノード間接続情報の一例を示す図である。
【図10】図10は、本発明の一実施形態に係るノードXがノードA乃至Dとの間にバーチャルコネクションを確立する動作を示す図である。
【図11】図11は、本発明の一実施形態に係るノードXがノードDとの間に確立したバーチャルコネクションを介したノードXからノードA乃至Dまでの経路情報を示す図である。
【図12】図12は、本発明の一実施形態に係るノードXがノードAとの間に確立したバーチャルコネクションを介したノードXからノードA乃至Dまでの経路情報を示す図である。
【図13】図13は、本発明の一実施形態に係るノードXがノードBとの間に確立したバーチャルコネクションを介したノードXからノードA乃至Dまでの経路情報を示す図である。
【図14】図14は、本発明の一実施形態に係るノードXがノードCとの間に確立したバーチャルコネクションを介したノードXからノードA乃至Dまでの経路情報を示す図である。
【図15】図15は、本発明の一実施形態に係るノードXが各バーチャルコネクションを介したノードA乃至Dまでの経路の平均メトリック値を算出する計算式を示す図である。
【図16】図16は、本発明の一実施形態に係るノードXが各バーチャルコネクションを介したノードA乃至Dまでの経路の平均メトリック値を算出する一例を示す図である。
【図17】図17は、本発明の一実施形態に係るノードXがノードDとの間にコネクションを確立する動作を示す図である。
【発明を実施するための最良の形態】
【0021】
(本発明の第1の実施形態に係るネットワークトポロジー生成方法を実現するノードの構成)
以下、図6A及び図6Bを参照して、本発明の第1の実施形態に係るネットワークトポロジー生成方法を実現するノードの構成について説明する。本実施形態において、ノードXは、複数のノードA乃至Dを含むネットワークに新規に参加することができるように構成されている。
【0022】
図6Aに示すように、本実施形態に係るノードXは、ノード間接続情報取得部11と、バーチャルコネクション確立部12と、平均メトリック値算出部13と、コネクション確立部14と、メトリック値指定部15とを具備している。
【0023】
ノード間接続情報取得部11は、ネットワーク内の任意のノード(例えば、ノードA)から、当該任意のノードの隣接ノード(例えば、ノードB乃至D)に係るノード間接続情報を取得するものである。なお、ノード間情報には、隣接ノードを識別するための「ノード名(ノードID)」と、隣接ノードの「ノードアドレス(例えば、IPアドレス)」と、任意のノードと隣接ノードとの間の経路の「メトリック値」と、隣接ノードに隣接する「ノード数」とを含む。また、「メトリック値」は、ホップ数、ネットワーク帯域幅、通信コスト、遅延、負荷、MTU、信頼性の少なくとも一つを含む。
【0024】
ここで、ホップ数は、物理層におけるホップ数、すなわち、当該ノードとの間で確立されているリンクにおけるルータ等のホップ数を示す。ネットワーク帯域幅は、当該ノードとの間で確立されているリンクにおいて使用可能な通信帯域(例えば、64kbps等)を示す。通信コストは、当該ノードとの間で確立されているリンクの通信料金を示す。遅延は、当該ノードとの間で確立されているリンクにおける伝播遅延時間を示す。負荷は、当該ノードとの間で確立されているリンクの使用状況(例えば、50%等)を示す。MTUは、当該ノードとの間で確立されているリンクにおいて使用される最小転送ブロックサイズ(Minimum Transfer Unit)を示す。信頼性は、当該ノードとの間で確立されているリンクにおける障害発生率をしめす。
【0025】
ノード間接続情報取得部11は、ネットワーク内の任意のノードからノード間情報を取得する際に、メトリック値指定部15によって指定されたメトリック値(又は、メトリック値の組み合わせ)の種類を通知するように構成されていてもよい。
【0026】
バーチャルコネクション確立部12は、ノード間接続情報取得部11によって取得したノード間接続情報内のノードアドレスを参照して、複数のノードA乃至Dとの間でバーチャルコネクションを確立するものである。
【0027】
平均メトリック値算出部13は、ノード間接続情報取得部11によって取得したノード間接続情報を利用して、各バーチャルコネクションを介した複数のノードまでの経路の平均メトリック値を算出するものである。なお、当該平均メトリック値の具体的な算出方法については後述する。
【0028】
コネクション確立部14は、経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立するものである。
【0029】
メトリック値指定部15は、ノードXがネットワークに新規に参加する際に、任意のノードから取得するノード間接続情報に含まれるべきメトリック値(又は、メトリック値の組み合わせ)の種類を指定するものである。なお、メトリック値指定部15によって所定のメトリック値が指定されない場合、任意のノードによって提供されるノード間接続情報には、デフォルトで設定されたメトリック値(又は、メトリック値の組み合わせ)が含まれる。
【0030】
図6Bに示すように、本実施形態に係るノードAは、ノード間接続情報取得部31と、ノード間接続情報記憶部32と、バーチャルコネクション確立部33と、ノード間接続情報提供部34と、コネクション確立部35とを具備している。
【0031】
ノード間接続情報取得部31は、ネットワーク内において、当該ノードXに隣接する隣接ノード(例えば、ノードB乃至D)から、当該隣接ノードに係るノード間接続情報を取得するものである。なお、各ノード間のリンクにおけるメトリック値は適宜更新されている。
【0032】
例えば、ノード間接続情報取得部31は、更新通知パケットを、ネットワーク内の全ノードにブロードキャストすることによって、定期的にノード間接続情報の更新結果を取得するように構成されていてもよい。
【0033】
また、ノード間接続情報取得部31は、TTL(Time To Live)を設定した範囲に更新通知パケットを送信することによって、定期的にノード間接続情報の更新結果を取得するように構成されていてもよい。
【0034】
ノード間接続情報記憶部32は、ノード間接続情報取得部31によって取得されたノード間接続情報を記憶するものである。
【0035】
バーチャルコネクション確立部33は、ノードXからのバーチャルコネクション確立要求に応じて、ノードXとの間でバーチャルコネクションを確立するものである。
【0036】
ノード間接続情報提供部34は、ノード間接続情報記憶部32からノードAに隣接する隣接ノードに係るノード間接続情報を取得して、バーチャルコネクション確立部33によって確立されたノードXとの間のバーチャルコネクションを介して当該ノード間接続情報をノードXに提供するものである。
【0037】
ノード間接続情報提供部34は、ノードXによってメトリック値(又は、メトリック値の組み合わせ)の種類が通知された場合、かかるメトリック値(又は、メトリック値の組み合わせ)を含むノード間接続情報を提供するように構成されていてもよい。
【0038】
また、ノード間接続情報提供部34は、ノードXによってメトリック値(又は、メトリック値の組み合わせ)の種類が通知されなかった場合、デフォルトで設定されているメトリック値(又は、メトリック値の組み合わせ)を含むノード間接続情報を提供するように構成されていてもよい。
【0039】
コネクション確立部35は、ノードXからのコネクション確立要求に応じて、ノードXとの間でバーチャルコネクションを確立するものである。
【0040】
(本実施形態に係るネットワークトポロジー生成方法の動作)
図7乃至図17を参照して、本実施形態に係るネットワークトポロジー生成方法の動作について説明する。具体的には、ノードXが、ノードA乃至Dを含むネットワークに新規に参加する際の動作について説明する。
【0041】
図7及び図8に示すように、ステップS1において、ノードXのノード間接続情報取得部11が、ノードAから、ノードAが管理しているノード間接続情報を取得する。ここで、ノードXのノード間接続情報取得部11は、取得するノード間接続情報に含まれるべきメトリック値(又は、メトリック値の組み合わせ)の種類を通知するように構成されていてもよい。
【0042】
図9に、本実施形態において、ノードAが管理しているノード間接続情報を示す。図9に示すように、ノードAの隣接ノードは、ノードB乃至Dである。なお、ノードBのノードアドレスは「BIP」であり、ノードCのノードアドレスは「CIP」であり、ノードDのノードアドレスは「DIP」である。また、ノードAとノードBとの間のメトリック値は「2」であり、ノードAとノードCとの間のメトリック値は「3」であり、ノードAとノードDとの間のメトリック値は「2」である。また、ノードBに隣接するノード数は「2」であり、ノードCに隣接するノード数は「2」であり、ノードDに隣接するノード数は「3」である。
【0043】
図7及び図10に示すように、ステップS2において、ノードXのバーチャルコネクション確立部12が、取得したノード間接続情報に含まれる「ノードアドレス」に基づいて、ノードA乃至Dとの間でバーチャルコネクションを確立する。
【0044】
ステップS3において、ノードXの平均メトリック値算出部13が、取得したノード間接続情報に含まれる「メトリック値」及び「ノード数」に基づいて、各バーチャルコネクションを経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値を算出する。
【0045】
具体的には、以下のように、平均メトリック値を算出する。なお、ノードXとノードDとの間に確立されたバーチャルコネクション#1のメトリック値は「1」であり、ノードXとノードAとの間に確立されたバーチャルコネクション#2のメトリック値は「5」であり、ノードXとノードBとの間に確立されたバーチャルコネクション#3のメトリック値は「3」であり、ノードXとノードCとの間に確立されたバーチャルコネクション#4のメトリック値は「1」である者とする。
【0046】
図11は、バーチャルコネクション#1を経由してノードXからノードA乃至Dの各々に到達する経路#A1乃至#D1における「メトリック値」及び各ノードA乃至Dに隣接する「ノード数」を関連付ける経路情報を示す。
【0047】
また、図12は、バーチャルコネクション#2を経由してノードXからノードA乃至Dの各々に到達する経路#A2乃至#D2における「メトリック値」及び各ノードA乃至Dに隣接する「ノード数」を関連付ける経路情報を示す。
【0048】
また、図13は、バーチャルコネクション#3を経由してノードXからノードA乃至Dの各々に到達する経路#A3乃至#D3における「メトリック値」及び各ノードA乃至Dに隣接する「ノード数」を関連付ける経路情報を示す。
【0049】
さらに、図14は、バーチャルコネクション#4を経由してノードXからノードA乃至Dの各々に到達する経路#A4乃至#D4における「メトリック値」及び各ノードA乃至Dに隣接する「ノード数」を関連付ける経路情報を示す。
【0050】
ノードXの平均メトリック値算出部13は、図11乃至図14に示す経路情報を用いて、図15に示す計算式によって、各バーチャルコネクション#1乃至#4を経由してノードXからノードiに到達する経路の平均メトリック値Viを算出する。図15に示す計算式において、nは、ネットワークに属する総ノード数を示し、VMiは、ノードXからノードiまで到達する経路のメトリック値を示し、Niは、ノードiの隣接ノード数に1を加えた値を示す。ここで、ノードAは、ノード1に該当し、ノードBは、ノード2に該当し、ノードCは、ノード3に該当し、ノードDは、ノード4に該当するものとする。
【0051】
図16は、本実施形態において、ノードXの平均メトリック値算出部13が、図11乃至図14に示す経路情報を参照して、各バーチャルコネクション#1乃至#4を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値を算出する様子の一例を示す。
【0052】
図16に示すように、ノードXがノードAとの間に確立したバーチャルコネクション#2を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値は「78/11」であり、ノードXがノードBとの間に確立したバーチャルコネクション#3を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値は「59/11」であり、ノードXがノードCとの間に確立したバーチャルコネクション#4を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値は「50/11」であり、ノードXがノードDとの間に確立したバーチャルコネクション#1を経由してノードXからノードA乃至Dの各々に到達する経路の平均メトリック値は「40/11」である。
【0053】
この結果に基づいて、ステップS4において、図17に示すように、ノードXのコネクション確立部14は、上述の経路の平均メトリック値が最小(「40/11」)であるバーチャルコネクション#1が確立されたノードDに対して、コネクションを確立することによって、ネットワークに新規に参加する。この結果、ネットワークトポロジーが変更される。すなわち、ノードXは、バーチャルコネクション#1を経由してノードA乃至D等を含むネットワーク内の全てのノードとの間で通信を行うことができる。
【0054】
(本実施形態に係るネットワークトポロジー生成方法の作用・効果)
本実施形態に係るネットワークトポロジー生成方法によれば、ノードXのコネクション確立部14が、物理層のネットワーク状況を考慮して算出される平均メトリック値が最小となるように、バーチャルコネクション#1が確立されたノードDに対してコネクションを確立するため、新たにネットワークトポロジーを生成するにあたって、ネットワーク遅延を平均的にかつ最小限に抑制することができる。
【0055】
以上、本発明を実施例により詳細に説明したが、当業者にとっては、本発明が本願中に説明した実施例に限定されるものではないということは明らかである。本発明の装置は、特許請求の範囲の記載により定まる本発明の趣旨及び範囲を逸脱することなく修正及び変更態様として実施することができる。従って、本願の記載は、例示説明を目的とするものであり、本発明に対して何ら制限的な意味を有するものではない。
【産業上の利用可能性】
【0056】
以上説明したように、本発明によれば、物理層のネットワーク状況を考慮することによって、新たにネットワークトポロジーを生成するにあたって、ネットワーク遅延を平均的にかつ最小限に抑制することが可能なネットワークトポロジーの生成方法及びノードを提供することができる。
【特許請求の範囲】
【請求項1】
複数のノードによって構成されるネットワークに新規に参加するノードであって、
前記複数のノードとの間でバーチャルコネクションを確立するバーチャルコネクション確立部と、
各バーチャルコネクションを介した前記複数のノードまでの経路の平均メトリック値を算出する平均メトリック値算出部と、
前記経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立することによって、前記ネットワークに参加するコネクション確立部とを具備することを特徴とするノード。
【請求項2】
前記ネットワーク内の任意のノードから、該任意のノードの隣接ノードに係るノード間接続情報を取得する取得部を具備し、
前記平均メトリック値算出部は、前記ノード間接続情報を用いて前記平均メトリック値を算出することを特徴とする請求項1に記載のノード。
【請求項3】
前記ノード間接続情報は、前記隣接ノードを識別するためのノードIDと、前記任意のノードと前記隣接ノードとの間の経路のメトリック値と、前記隣接ノードに隣接するノード数とを含むことを特徴とする請求項2に記載のノード。
【請求項4】
前記メトリック値は、ホップ数、ネットワーク帯域幅、通信コスト、遅延、負荷、MTU、信頼性の少なくとも一つを含むことを特徴とする請求項3に記載のノード。
【請求項5】
前記取得部は、前記任意のノードに対して、前記ノード間接続情報に含まれるべきメトリック値又はメトリック値の組み合わせの種類を通知することを特徴とする請求項3に記載のノード。
【請求項6】
複数のノードによって構成されるネットワークに新規ノードが参加するネットワークトポロジー生成方法であって、
前記新規ノードが、前記複数のノードとの間でバーチャルコネクションを確立する工程と、
前記新規ノードが、各バーチャルコネクションを介した前記複数のノードまでの経路の平均メトリック値を算出する工程と、
前記新規ノードが、前記経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立することによって、前記ネットワークに参加する工程とを有することを特徴とするネットワークトポロジー生成方法。
【請求項1】
複数のノードによって構成されるネットワークに新規に参加するノードであって、
前記複数のノードとの間でバーチャルコネクションを確立するバーチャルコネクション確立部と、
各バーチャルコネクションを介した前記複数のノードまでの経路の平均メトリック値を算出する平均メトリック値算出部と、
前記経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立することによって、前記ネットワークに参加するコネクション確立部とを具備することを特徴とするノード。
【請求項2】
前記ネットワーク内の任意のノードから、該任意のノードの隣接ノードに係るノード間接続情報を取得する取得部を具備し、
前記平均メトリック値算出部は、前記ノード間接続情報を用いて前記平均メトリック値を算出することを特徴とする請求項1に記載のノード。
【請求項3】
前記ノード間接続情報は、前記隣接ノードを識別するためのノードIDと、前記任意のノードと前記隣接ノードとの間の経路のメトリック値と、前記隣接ノードに隣接するノード数とを含むことを特徴とする請求項2に記載のノード。
【請求項4】
前記メトリック値は、ホップ数、ネットワーク帯域幅、通信コスト、遅延、負荷、MTU、信頼性の少なくとも一つを含むことを特徴とする請求項3に記載のノード。
【請求項5】
前記取得部は、前記任意のノードに対して、前記ノード間接続情報に含まれるべきメトリック値又はメトリック値の組み合わせの種類を通知することを特徴とする請求項3に記載のノード。
【請求項6】
複数のノードによって構成されるネットワークに新規ノードが参加するネットワークトポロジー生成方法であって、
前記新規ノードが、前記複数のノードとの間でバーチャルコネクションを確立する工程と、
前記新規ノードが、各バーチャルコネクションを介した前記複数のノードまでの経路の平均メトリック値を算出する工程と、
前記新規ノードが、前記経路の平均メトリック値が最小となるバーチャルコネクションが確立されたノードに対してコネクションを確立することによって、前記ネットワークに参加する工程とを有することを特徴とするネットワークトポロジー生成方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6A】
【図6B】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図2】
【図3】
【図4】
【図5】
【図6A】
【図6B】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【国際公開番号】WO2005/062549
【国際公開日】平成17年7月7日(2005.7.7)
【発行日】平成19年12月13日(2007.12.13)
【国際特許分類】
【出願番号】特願2005−516529(P2005−516529)
【国際出願番号】PCT/JP2004/019411
【国際出願日】平成16年12月24日(2004.12.24)
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
【国際公開日】平成17年7月7日(2005.7.7)
【発行日】平成19年12月13日(2007.12.13)
【国際特許分類】
【国際出願番号】PCT/JP2004/019411
【国際出願日】平成16年12月24日(2004.12.24)
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
[ Back to top ]