(57)【要約】【課題】  Chordでのパケット転送は、同一ノード間を複数回転送することはないが、物理ネットワーク上で経由する経路で見ると同一物理リンクを複数回転送されることが有り得る。1つのパケットが同一リンクを複数回転送されることは、広帯域リンクでは問題にならないが、リンクの帯域が細い場合は、Chordネットワーク全体のスループットや転送遅延時間に悪影響を及ぼす。【解決手段】  本発明におけるオーバレイネットワークの構成方法は、オーバレイネットワーク（コードリング）を構成するシステムにおいて、コードリングを構成する各ノードがトポロジ情報を入手し、あるノードがコードリングに参加する時には、参加ノードのIDが、上流ノードと下流ノードのIDの間の値となり、参加ノードをコードリングのどこに配置するかを決定した後に、参加ノードが使用するIDが決定されるものである。【選択図】          図４
2009212791.tif 000002
【特許請求の範囲】
【請求項１】
オーバレイネットワーク（コードリング）を構成するシステムにおいて、
前記コードリングを構成する各ノードは、
ノード間のリンクの帯域を含むトポロジ情報を入手し、
あるノードが前記コードリングに参加する時には、前記参加ノードのIDが、上流ノードと下流ノードのIDの間の値となり、前記コードリングに参加している間は、当該IDが変更されず、
前記参加ノードを前記コードリングのどこに配置するかを決定した後に、前記参加ノードが使用するIDが決定される
ことを特徴とするオーバレイネットワークを構成する構成方法。
【請求項２】
コードリングに参加するノードのツリーを構成し、前記コードリングを構成する各ノードの下流ノードと前記ノードの数とについて、コードリングを構成する全ノードで共有する
ことを特徴とする請求項１に記載のオーバレイネットワークを構成する構成方法。
【請求項３】
あるノードと当該ノードの下流ノードとのリンクを経由する回数に基づく評価関数を設定し、
この評価関数の評価結果に基づき、
この評価関数の所定の条件を満たす上流ノード、下流ノードの候補の中から、前記ノードのコードリングへの参加後の評価関数が最小となるものを、ツリーのルートが選択し、前記ノードのコードリングへの参加位置を決定する
ことを特徴とする請求項１に記載のオーバレイネットワークを構成する構成方法。
【請求項４】
任意のノードXからコードリングへの参加要求を受けた、コードリングに既に参加しているノードAは、Ransubアルゴリズムを実行するツリーのルートノード(ノードR)にノードXの参加要求を通知し、
前記ノードRは、コードリングに参加している全ノードに、自ノードと下流ノードの間にノードXが参加した場合の評価関数の変化量を計算するように指示し、
コードリングに参加している各ノードは、前記ノードRに計算結果を報告し、計算結果の報告にあたり、Ransubアルゴリズムを使用し、各ノードは、ツリーの子ノードからの報告結果と自ノードの計算結果の中で、変化量が最も小さい結果のみを、ツリーの親ノードに報告する
ことを特徴とする請求項３に記載のオーバレイネットワークを構成する構成方法。
【請求項５】
ノードがコードリングから離脱する時や、物理ネットワークトポロジの変化時に、コードリングの再構築を行うために、ツリーのルートが、コードリングに参加するノードの中から1つを選び、そのノードがコードリングの別の場所に参加し直すことで評価関数をより小さくできるノードを探すことを、評価関数をより小さくできなくなるまで繰り返し、前記評価関数結果に基づき、コードリングを構成するノードに対して別の場所への参加を指示する
ことを特徴とする請求項１に記載のオーバレイネットワークを構成する構成方法。
【請求項６】
ノードのコードリングからの離脱や、物理ネットワークトポロジ変化を検出した時点で、ツリーのルートノード(ノードR)は、コードリングに参加している各ノードに対して、自ノードがコードリングを離脱して別の場所に参加した場合に、評価関数の変化量が最も小さくなる参加箇所と変化量を求めるように指示し、
各ノードは前記ノードRに計算結果を報告し、前記各ノードはツリーの子ノードからの報告結果と自ノードの計算結果の中で、変化量が最も小さい結果を、ツリーの親ノードに報告する
ことを特徴とする請求項１に記載のオーバレイネットワークを構成する構成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、オーバレイネットワークのトポロジ決定方法に関するものである。
【背景技術】
【０００２】
オーバレイネットワークを構築する手法の1つにコード(Chord)の非特許文献１に示される方法がある。
Chordでは、ノードに固有の情報に対してハッシュ関数を適用して得られる値をIDとして付与し、IDの昇順にノードをリング状に配置する（Chordリングと呼ぶ）。図１のように、あるノードAからみて、リング上での1つ前のノードを上流ノード(predecessor)、1つ後のノードを下流ノード(successor)と呼ぶ。IDは、ノードの固有情報（例 IPアドレス）にハッシュ関数を適用して決定する。IDがある程度均一に分散していることが必要となる。
【非特許文献１】I.Stoica, etal, "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications", SIGCOMM'01, Aug., 2001
【非特許文献２】D.Kostic,A.Rodriguez, etal, "Using Random Subsets to Build Scalable Network Services", Proceedings of 4th USENIX Symposium on Internet Technologies and Systems, March 2003
【発明の開示】
【発明が解決しようとする課題】
【０００３】
図２のように、Chordでのパケット転送は、Chordリングに参加するノード（以下、ノードと呼ぶ）間でのマルチホップ転送が基本である。1パケットの転送において、同一ノード間を複数回転送することはないが、物理ネットワーク上で経由する経路で見ると同一物理リンク（以下、リンクと呼ぶ）を複数回転送されることが有り得る。
1つのパケットが同一リンクを複数回転送されることは、広帯域リンクでは問題にならないが、リンクの帯域が細い場合は、Chordネットワーク全体のスループットや転送遅延時間に悪影響を及ぼす。
【０００４】
本発明は、帯域が細いリンクでのパケット転送回数を少なくする様に、Chordのトポロジを構築することを目的とする。
【課題を解決するための手段】
【０００５】
本発明におけるオーバレイネットワークの構成方法は、オーバレイネットワーク（コードリング）を構成するシステムにおいて、コードリングを構成する各ノードが、ノード間のリンクの帯域を含むトポロジ情報を入手し、あるノードがコードリングに参加する時には、参加ノードのIDが、上流ノードと下流ノードのIDの間の値となり、コードリングに参加している間は、当該IDが変更されず、参加ノードをコードリングのどこに配置するかを決定した後に、参加ノードが使用するIDが決定されるものである。
【発明の効果】
【０００６】
本発明の方法を取ることで、パケットがChordリングを一周する場合に経由するリンクの関数f()の値の総和ができるだけ小さくなる様に、Chordトポロジを構成することが可能となる。これにより、パケットがChordリングを一周する場合に帯域が細いリンクを使用する回数を減らすことができる。
【発明を実施するための最良の形態】
【０００７】
本発明の方法の実施例について説明する。
【０００８】
図４において、本発明の方法を実現するノードの構成例を示す。図４に示す各処理部の処理内容について説明する。物理ネットワークとしてIPネットワークを使用し、その上でChordリングを実現する場合を想定する。
(a)ID値決定処理部
元となるChordの処理方法と、本発明の処理方法との差分の中で、Ransubアルゴリズム実施に使用するツリー管理処理と評価関数計算処理以外の処理を行う。
Chordリングに未参加のノードがChordリングに参加する場合、ID値決定処理部は、既にChordリングに参加しているノードを最低1つは知っており、そのノードに対して参加要求をChordデータ転送処理部経由で送信する。そして、既にChordリングに参加しているノードのID値決定処理部に参加要求を送信し、自ノードがChordリングのどこに参加するべきかを決定する様に依頼する。参加要求を受信したノードのID値決定処理部は、以下の処理を実行し、参加要求を送信したノードがChordリングのどこに参加すべきかを決定する。そして、決定した結果を、参加しようとしているノードに参加応答で通知する。
【０００９】
(1)非特許文献１に示すChordの方法によりオーバレイネットワーク（Chordリング）を構成するシステムにおいて、あるノードがChordリングに参加する場合に使用するノードのIDを、Chordで用いられるハッシュ関数を適用して決定する代わりに、以下(1-1)〜(1-5)の方法を用いることにより、ノードをChordリング上のどこに配置するかを決定した後に、ノードが使用するIDを決定する。
Chordのリングを構成する各ノードは、リンクステートルーティングプロトコル(OSPF)等を利用して、ノード間を接続するリンク(物理リンク)の帯域を含むトポロジ情報を入手しており、IP層での経路計算もできることを前提とする。
(1-1)ノードのIDを、ノード（参加ノード）がChordリングに参加する時にpredecessorとsuccessorになるノードのIDの真ん中（間）の値にする。Chordリングに参加している間は、ノードのIDは変更しない。
(1-2)例えば、Chordリングに参加するノードのツリーを構成し（ツリーのルートは最小のIDを持つノード（ルートノード）とする）、そのツリー上でRansubアルゴリズム[非特許文献２]を実行し、Chordリングを構成する各ノードからsuccessorに至る時に経由するリンクが何かの情報とノード数を、Chordリングを構成する全ノードで共有する。
(1-3)評価関数として、E=ΣCi×f(Bi) [iはリンクの識別子]を設定する。Ciはリンクiを経由する回数であり、Chordリングを構成する各ノードからsuccessorに至る時に経由するリンクが何かの情報から求める。Biはリンクiの帯域値、f(Bi)は単調減少関数(値は0以上)。評価関数Eの値が小さくなる様にノードがChordリングに参加する位置を決定する。
(1-4)ノードXがChordリングに参加する時は、ノードを均一に分散させるため、predecessorになるノードのIDと、successorになるノードのIDの差が、(ID空間サイズ/Chordリング上のノード数)×α（α<=2）以上であることを条件とする。この条件を満たすpredecessor, successor候補の中で、ノードX参加後の評価関数Eを最小とするものを、ツリーのルートが計算し選択する。そして、結果をノードXに通知し、ノードXのpredecessor, successorを指示する。
(1-5)ノードがChordリングから離脱する時や、（ノードやリンクの障害等のための）物理ネットワークトポロジ変化時に、Chordリングの再構築を行うために、ツリーのルートが、Chordリングに参加するノードの中から1つを選び、そのノードがChordリングの別の場所に参加し直すことで評価関数Eをより小さくできるノードを探すことを、評価関数Eをより小さくできなくなるまで繰り返す。そして、計算結果を元に、Chordリングを構成するノードに対して別の場所への参加を指示する。
【００１０】
また、上述のID値決定処理部における評価関数計算(1-4)を、以下の方法で行う。
(1-4-1)ノードXからChordリングへの参加要求を受けた、Chordリングに既に参加しているノードAは、Ransubアルゴリズムを実行するツリーのルートノード(ノードR)にノードXの参加要求を通知する。
(1-4-2)ノードRは、Chordリングに参加している全ノードに、自ノードとsuccessorの間にノードXが参加した場合の評価関数Eの変化量を計算する様に指示する。
(1-4-3)Chordリングに参加している各ノードは、ノードRに計算結果を報告する。計算結果の報告にあたり、Ransubアルゴリズムを使用し、各ノードは、ツリーの子ノードからの報告結果と自ノードの計算結果の中で、変化量が最も小さい結果のみを、ツリーの親ノードに報告する。
【００１１】
参加応答を受信したノードのID値決定処理部は、指定されるID値を自ノードのIDとしてChordトポロジ管理処理部に通知し、通常のChordの方法でChordリングに参加することを、Chordトポロジ管理処理部に要求する。
ID値決定処理部は、Chordトポロジ管理処理部から通知されるChordリングトポロジ情報を元に、自ノードがRansubアルゴリズム実行用ツリーのルートになるかどうかを判断する。
具体的には、自ノードのpredecessorのID値が、自ノードのID値よりも大きいか等しい場合、自ノードがChordリング上で最もID値が小さいノードとなるため、ルートになると判断する。
物理ネットワークトポロジ管理処理部から、物理ネットワークトポロジ変化を通知された時に、ツリーのルートとなるノードはChordリング再構築処理を開始する。
Chordトポロジ管理処理部から通知されるChordリングトポロジ情報の変化から、ノード離脱を検出した場合、ツリーのルートとなるノードはChordリング再構築処理を開始する。
【００１２】
Chordリング再構築処理は、各ノードのID値決定処理部が、以下の処理を実行することで実現する。まずは、上述の(1)及び(1-1)〜(1-5)の処理を行うが、その内容は上述のとおり。
また、上述の評価関数計算(1-5)は、以下の方法で行う。
(1-5-1)ノードのChordリングからの離脱や、物理ネットワークトポロジ変化を検出した時点で、ツリーのルートノード(ノードR)は、Chordリングに参加している各ノードに対して、自ノードがChordリングを離脱して別の場所に参加した場合に、評価関数Eの変化量が最も小さくなる参加箇所と変化量を求めるように指示する。
(1-5-2)各ノードはノードRに計算結果を報告する。計算結果の報告にあたり、Ransubアルゴリズムを使用し、各ノードは、ツリーの子ノードからの報告結果と自ノードの計算結果の中で、変化量が最も小さい結果のみを、ツリーの親ノードに報告する。
【００１３】
次に、本発明を実現する図４の他の処理部の処理内容について説明する。
(b)Chordトポロジ管理処理部
ID値決定処理部が決定したID値を自ノードのIDとして使用し、Chordで規定される方法に従ってChordリングの維持管理を行う。Chordリング上での転送テーブル情報の管理も行い、転送テーブル情報をChordデータ転送処理部に通知する。Chordリングの維持のために他ノードとの間でやり取りする制御メッセージは、Chordデータ転送処理部の機能を用いて送受信する。
(c)Chordデータ転送処理部
Chordトポロジ管理処理部から通知される転送テーブル情報を元に、Chordリング上で転送するデータの転送処理を行う。
(d)ツリー管理処理部
Chordトポロジ管理処理部から通知されるChordリングトポロジ情報を利用して、Chordリング上に、Ransubアルゴリズム実行に使用するツリーネットワークを維持管理するための処理を行う。Ransubアルゴリズム実行はID値決定処理部が行うため、ツリートポロジ情報（ツリー上の親ノード,子ノードのIDが何かの情報）をID値決定処理部に提供する。
(e)評価関数計算処理部
物理ネットワークトポロジ管理処理部から提供される(1)物理ネットワークトポロジ、(2)各リンクの帯域、(3)ノード間のルート情報（任意の2つのノード間通信で使用するリンクが何になるかを、物理ネットワークトポロジの情報とルーティングプロトコル仕様に基づき決定する）と、Chordトポロジ管理処理部から提供されるChordリングトポロジ情報を用いて、ID値決定処理部から指定るChordリングトポロジ変化情報（新規参加ノードと参加位置の情報、離脱ノードの情報）に対して、上述の(1-3)に示す評価関数の値の計算を行い、その結果をID値決定処理部へ返す機能を有する。f(x)としては、例えば1/xをとることが考えられる。
(f)物理ネットワークトポロジ管理処理部
例えばOSPFといったリンクステートルーティングプロトコルを実行し、物理ネットワークのトポロジ、各リンクの帯域の管理を行う。また、指定された2ノード間の通信が使用するリンクが何かを、物理ネットワークで使用されるルーティングプロトコル仕様に基づき決定する機能を持つ。(1)物理ネットワークトポロジ、(2)各リンクの帯域、(3)ノード間のルート情報の情報を、評価関数計算処理部からの要求に対して応答する機能を持つ。物理ネットワークトポロジ変化が発生した場合に、そのことをID値決定処理部に通知する機能を持つ。IPパケット転送処理部の機能を使用し、ルーティングプロトコルパケットの送受信を行う
(g)IPパケット転送処理部
通常のIPネットワークでの規則に従って、IPパケットの送受信処理、および、ルーティング処理を行う機能ブロック。例えば、Linux, Windows（登録商標）等のOSに含まれるIPプロトコルスタックソフトウェアで実現される。
【００１４】
以上のことから、以下の効果が得られる。
本発明の方法を取ることで、パケットがChordリングを一周する場合に経由するリンクのf()の値の総和ができるだけ小さくなる様に、Chordトポロジを構成することが可能となる。これにより、パケットがChordリングを一周する場合に帯域が細いリンクを使用する回数を減らすことができる。
例えば、図2の場合に、仮にノード1とノード3が既にChordリングに参加している状態で、ノード2に対応するノードが新たにChordリングに参加する場合に、上述の方法をとることでノードのIDが2ではなく5になり、パケットがChordリング上でsuccessorを順に辿って転送される時に、各リンクを1回のみ経由するトポロジになる。これを図3に示す。
【００１５】
また、上述の(1-4-1)〜(1-4-3)や(1-5-1)〜(1-5-2)の方法により、本発明の方法による評価関数計算時間を短くし、新規ノード参加時、ノード離脱時、物理ネットワークトポロジ変化時にChordリング再構成にかかる時間を短くできる。
【００１６】
また、上述の(1-4)での計算量について、Chordリングを構成するノード数をNとすると、本発明では、ツリーのルートであるノードRの計算量がO(N)であるものを、ノード間メッセージがO(N)必要になるが各ノードでの計算量をO(1)に抑えることができる。また、ノード間通信時間よりも計算時間が処理時間において支配要因である場合、上述の(1-4-1)〜(1-4-3)の方法により、新規ノードがChordリングに参加するためにかかる時間を低減できる。
【００１７】
さらに、上述の(1-5-1)〜(1-5-2)の方法を用いることにより、(1-5)の計算量について、Chordリングを構成するノード数をNとすると、本発明では、ツリーのルートであるノードRの計算量が繰り返し計算の1回につきO(N2)であるものを、繰り返し計算の1回につき、ノード間メッセージがO(N)必要になるが、各ノードでの計算量をO(N)に抑えることができる。また、ノード間通信時間よりも計算時間が処理時間において支配要因である場合、(1-5-1)〜(1-5-2)の方法により、本発明の方法でノード離脱時や物理ネットワークトポロジ変化時にChordリング再構成にかかる時間を低減することができる。
【図面の簡単な説明】
【００１８】
【図１】Chordリングに関する概要説明図。
【図２】従来のオーバーレイネットワークを示す説明図。
【図３】本発明のオーバーレイネットワークを示す説明図。
【図４】本発明のオーバーレイネットワークを構成するノードに関する構成図。
【符号の説明】
【００１９】
１  ID値決定処理部、２  Chordトポロジ管理処理部、３  Chordデータ転送処理部、４  ツリー管理処理部、５  評価関数計算処理部、６  物理ネットワークトポロジ管理処理部、７  IPパケット転送処理部。
【図１】
2009212791.tif 000003
【図２】
2009212791.tif 000004
【図３】
2009212791.tif 000005
【図４】
2009212791.tif 000006