(57)【要約】      （修正有）【課題】オーバーレイマルチキャストおいて、エンドノード間のマルチキャストトラヒックの転送遅延を短縮する。【解決手段】オーバーレイノードは、キャパシティ管理部と再接続管理部とを備える。キャパシティ管理部は、自ノードのキャパシティを算出し、自ノードのキャパシティ及びアドレスを示すキャパシティ通知メッセージを、下流側の次ホップノードに送信する。再接続管理部は、上流側から受け取るキャパシティ通知メッセージに応答して、再接続指示処理を行う。その再接続指示処理において、再接続管理部は、通知されたキャパシティを参照して、自ノードに現在接続されているローカルエンドノードから上記許容数以内のエンドノードを選択する。そして、再接続管理部は、選択エンドノードに対して、通知されたアドレスで指定される上流のオーバーレイノードへ再接続するように指示する。【選択図】図４
2010278777.tif 000002
【特許請求の範囲】
【請求項１】
オーバーレイネットワークを構成するオーバーレイノードであって、
前記オーバーレイネットワーク上にはマルチキャストツリーが構築され、
前記オーバーレイネットワークにおいて、マルチキャストグループへの参加要求の転送方向が上流方向と定義され、前記上流方向の逆方向が下流方向と定義され、
前記マルチキャストツリーにおいて、下流側に隣接するノードは次ホップノードであり、上流側に隣接するノードは前ホップノードであり、
あるオーバーレイノードのキャパシティは、前記あるオーバーレイノードに追加的に接続され得るエンドノードの許容数に相当するパラメータであり、
前記オーバーレイノードは、
自ノードの前記キャパシティを算出し、前記自ノードの前記キャパシティ及びアドレスを示すキャパシティ通知メッセージを前記次ホップノードに送信するキャパシティ管理部と、
上流側から受け取る前記キャパシティ通知メッセージに応答して、再接続指示処理を行う再接続管理部と
を備え、
上流側から受け取る前記キャパシティ通知メッセージで示される前記キャパシティ及び前記アドレスは、それぞれ、通知キャパシティ及び上流ノードアドレスであり、
前記再接続指示処理において、
前記再接続管理部は、前記通知キャパシティを参照して、前記自ノードに現在接続されているローカルエンドノードから前記許容数以内のエンドノードを選択し、
前記再接続管理部は、前記選択されたエンドノードに対して、前記上流ノードアドレスで指定されるオーバーレイノードである上流ノードへ再接続するように指示する
オーバーレイノード。
【請求項２】
請求項１に記載のオーバーレイノードであって、
前記再接続指示処理の後、前記再接続管理部は、前記上流ノードの前記キャパシティを再算出し、
前記キャパシティ管理部によって送信される前記キャパシティ通知メッセージは、前記自ノードの前記キャパシティ及び前記アドレスに加えて、前記上流ノードの前記キャパシティ及び前記上流ノードアドレスを示す
オーバーレイノード。
【請求項３】
請求項１又は２に記載のオーバーレイノードであって、
前記次ホップノードが複数存在する場合、前記キャパシティ管理部は、前記キャパシティを前記複数の次ホップノード間で分割し、前記複数の次ホップノード毎に前記キャパシティ通知メッセージを送信する
オーバーレイノード。
【請求項４】
請求項１乃至３のいずれか一項に記載のオーバーレイノードであって、
エンドノード管理部を更に備え、
あるエンドノードのキャパシティ消費量は、前記あるエンドノードとの通信によって消費される前記キャパシティの量であり、
前記エンドノード管理部は、前記ローカルエンドノードの前記キャパシティ消費量を監視し、
前記再接続管理部は、前記通知キャパシティと前記算出されたキャパシティ消費量とに基づいて、前記許容数以内のエンドノードを選択する
オーバーレイノード。
【請求項５】
請求項４に記載のオーバーレイノードであって、
前記エンドノード管理部は、前記ローカルエンドノードの前記キャパシティ消費量を示すエンドノード状態通知メッセージを前記前ホップノードに送信し、
下流側から前記エンドノード状態通知メッセージを受け取った場合、前記エンドノード管理部は、前記エンドノード状態通知メッセージに前記ローカルエンドノードの前記キャパシティ消費量を追加した後に、前記エンドノード状態通知メッセージを更に前記前ホップノードに転送する
オーバーレイノード。
【請求項６】
請求項５に記載のオーバーレイノードであって、
前記次ホップノード以遠のオーバーレイノードに接続された全エンドノードの前記キャパシティ消費量の合計は、後続キャパシティ消費量であり、
前記次ホップノードが複数存在する場合、前記エンドノード管理部は、下流側から受け取った前記エンドノード状態通知メッセージを参照して、前記複数の次ホップノード毎に前記後続キャパシティ消費量を算出し、
更に、前記キャパシティ管理部は、前記複数の次ホップノードの前記後続キャパシティ消費量に基づいて、前記キャパシティを前記複数の次ホップノード間で分割し、前記複数の次ホップノード毎に前記キャパシティ通知メッセージを送信する
オーバーレイノード。
【請求項７】
請求項６に記載のオーバーレイノードであって、
前記キャパシティ管理部は、前記キャパシティの分割量が前記後続キャパシティ消費量を上回る次ホップノードが無くなるように、前記キャパシティを前記複数の次ホップノード間で分割する
オーバーレイノード。
【請求項８】
請求項５に記載のオーバーレイノードであって、
前記エンドノード管理部は、前記キャパシティ消費量と共に前記ローカルエンドノードの優先度を前記エンドノード状態通知メッセージに記載し、
前記次ホップノード以遠のオーバーレイノードに接続された全エンドノードの前記キャパシティ消費量の合計は、後続キャパシティ消費量であり、
前記再接続管理部は、下流側から受け取った前記エンドノード状態通知メッセージを参照して、前記優先度毎に前記後続キャパシティ消費量を算出し、
前記再接続管理部は、前記優先度の順番で前記再接続指示処理を行い、
ある優先度の前記再接続指示処理において、前記再接続管理部は、前記次ホップノード以遠に位置する現在の優先度のエンドノードに割り当てられる前記キャパシティを予め確保する
オーバーレイノード。
【請求項９】
マルチキャストツリーが構築されたオーバーレイネットワークシステムであって、
マルチキャストグループへの参加要求の転送方向が上流方向と定義され、前記上流方向の逆方向が下流方向と定義され、
あるオーバーレイノードのキャパシティは、前記あるオーバーレイノードに追加的に接続され得るエンドノードの許容数に相当するパラメータであり、
前記マルチキャストツリーは、
第１オーバーレイノードと、
前記第１オーバーレイノードよりも下流側に位置する第２オーバーレイノードと
を備え、
前記第１オーバーレイノードは、前記第１オーバーレイノードの前記キャパシティを算出し、前記第１オーバーレイノードの前記キャパシティ及びアドレスを示すキャパシティ通知メッセージを下流に送信し、
前記第２オーバーレイノードは、前記キャパシティ通知メッセージで示される前記第１オーバーレイノードの前記キャパシティを参照して、前記第２オーバーレイノードに現在接続されているローカルエンドノードから前記許容数以内のエンドノードを選択し、前記第１オーバーレイノードの前記アドレスを示す再接続指示メッセージを前記選択されたエンドノードに送信し、
前記選択されたエンドノードは、前記再接続指示メッセージを受け取ると、前記第１オーバーレイノードに対して再接続要求を送信し、前記第２オーバーレイノードの代わりに前記第１オーバーレイノードを新たなエッジノードとする
オーバーレイネットワークシステム。
【請求項１０】
オーバーレイネットワーク上に構築されたマルチキャストツリーにおけるエンドノードの再接続方法であって、
マルチキャストグループへの参加要求の転送方向が上流方向と定義され、前記上流方向の逆方向が下流方向と定義され、
あるオーバーレイノードのキャパシティは、前記あるオーバーレイノードに追加的に接続され得るエンドノードの許容数に相当するパラメータであり、
前記マルチキャストツリーは、
第１オーバーレイノードと、
前記第１オーバーレイノードよりも下流側に位置する第２オーバーレイノードと
を備え、
前記再接続方法は、
前記第１オーバーレイノードにおいて、前記第１オーバーレイノードの前記キャパシティを算出するステップと、
前記第１オーバーレイノードの前記キャパシティ及びアドレスを示すキャパシティ通知メッセージを、前記第１オーバーレイノードから下流に送信するステップと、
前記第２オーバーレイノードにおいて、前記キャパシティ通知メッセージで示される前記第１オーバーレイノードの前記キャパシティに基づいて、前記第２オーバーレイノードに現在接続されているローカルエンドノードから前記許容数以内のエンドノードを選択するステップと、
前記第１オーバーレイノードの前記アドレスを示す再接続指示メッセージを、前記第２オーバーレイノードから前記選択されたエンドノードに送信するステップと、
前記再接続指示メッセージに応答して、前記選択されたエンドノードから前記第１オーバーレイノードに対して再接続要求を送信するステップと
を含む
再接続方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャストツリーが構築されたオーバーレイネットワーク、そのオーバーレイネットワークを構成するオーバーレイノード、及びマルチキャストツリーにおけるエンドノードの再接続方法に関する。
【背景技術】
【０００２】
ＩＰルータ等で構成される物理ネットワーク上に構築される仮想的なネットワークである「オーバーレイネットワーク」が知られている。図１は、オーバーレイネットワークを示す模式図である。オーバーレイネットワークを構成するノードは、以下「オーバーレイノード１００」と参照される。図１に示されるように、物理ネットワークにおいてノード間を実際に接続する物理リンクに対し、オーバーレイネットワークにおいてオーバーレイノード１００間を接続するリンクは、仮想リンクあるいは論理リンクと呼ばれている。
【０００３】
その一方で、一対多あるいは多対多の通信を行う方法として、マルチキャストが古くから注目されてきた。マルチキャストの実現方法としては、ＩＰマルチキャストが従来知られていた。しかしながら、ＩＰマルチキャストでは、ネットワーク上の全ルータがＩＰマルチキャストに対応している必要があったため、普及が進まなかった。今日では、他の実現方法として、オーバーレイネットワーク上でマルチキャストを行う「オーバーレイマルチキャスト」が注目を集めている（特許文献１参照）。オーバーレイマルチキャストでは、物理ネットワーク上のルータがＩＰマルチキャストに対応している必要がないため、普及に対する障害がＩＰマルチキャストに比べ少ない。そのため、動画データの同報配信や、株式情報やセンサ情報等のリアルタイム同報配信など、幅広い分野での利用が検討されている。
【０００４】
オーバーレイマルチキャストにおいてマルチキャストトラヒックの送信及び受信を担うノードは、以下「エンドノード２００」と参照される。オーバーレイネットワークを構成するオーバーレイノード１００は、そのオーバーレイネットワークにおいてマルチキャストトラヒックの転送を行う。オーバーレイマルチキャストは概ね、以下の４ステップで実現される。
【０００５】
（１）オーバーレイネットワークの構築
まず、各オーバーレイノード１００が、ＤＨＴ（Distributed Hash Table）やＳｋｉｐ  Ｇｒａｐｈなどに基づいて、オーバーレイネットワーク上での隣接ノードを決定し、隣接ノード間で仮想リンクを作成する。これにより、オーバーレイネットワークが構築される。
【０００６】
（２）エンドノードによるオーバーレイネットワークの発見及び接続
次に、エンドノード２００が、ブートストラップサーバを利用したり、検索メッセージをブロードキャストしたりすることにより、オーバーレイネットワークに接続するためのオーバーレイノード１００を発見する。例えばブートストラップサーバが利用される場合、そのブートストラップサーバは、オーバーレイノード１００のリストを保持しており、当該リスト中から何らかのポリシー（ランダム、オーバーレイノードの負荷、エンドノードからの物理的近傍性）に基づいていずれかのオーバーレイノード１００を選択し、選択したオーバーレイノード１００をエンドノード２００へ通知する。また、検索メッセージがブロードキャストされる場合、ブロードキャストを受信したオーバーレイノード１００はエンドノード２００へ返信し、エンドノード２００は最も早く返信を送り返してきたオーバーレイノード１００を選択するのが一般的である。
【０００７】
エンドノード２００は、選択されたオーバーレイノード１００に対して、ＩＰ、ＵＤＰ、ＴＣＰやＳＳＬ等を用いて接続する。以降、当該エンドノード２００は、オーバーレイネットワークを利用した他のエンドノードとのトラヒックのやりとりを、本ステップで発見・接続したオーバーレイノード１００を通じて行う。このようなエンドノード２００の接続先であるオーバーレイノード１００は、以下「エッジノード」と参照される。尚、エンドノード２００自身がＤＨＴやＳｋｉｐ  Ｇｒａｐｈを処理するのに十分な能力を有している場合は、エンドノード２００とエッジノードとが物理的に同一であることもある。
【０００８】
（３）マルチキャストグループの作成
企業の部門や地域コミュニティ等、物理的な組織や興味対象とする情報のカテゴリなどに応じて、マルチキャストグループが作成される。作成されたマルチキャストグループは、それへの参加方法と共に、ディレクトリサーバ等を通じてエンドノード２００に通知される。
【０００９】
（４）マルチキャストツリーの作成
マルチキャストグループへの参加を希望するエンドノード２００は、エッジノードに対して、マルチキャストグループへの参加要求を送信する。エッジノードは、エンドノード２００から受け取った参加要求を、オーバーレイネットワークを利用して他のオーバーレイノードに転送する。最終的には、同一マルチキャストグループに参加する全てのエンドノード２００のエッジノードをつなぐマルチキャストツリーが作成される。マルチキャストグループに向けて送信されるトラヒックは、当該マルチキャストツリー上で転送され、各エンドノード２００に到達する。マルチキャストツリーの方式に関しては、多数の研究が行われている。以下、いくつかの例を説明する。
【００１０】
図２は、「センダーベース方式」のマルチキャストツリーを示す模式図である。図２において、オーバーレイノード１００−Ａ、１００−Ｂ、１００−Ｃ、１００−ＳＥ、エンドノード２００−Ｂ１、２００−Ｃ１、２００−Ｃ２、２００−Ｓが示されている。エンドノード２００−Ｂ１は、オーバーレイノード１００−Ｂに接続されている。すなわち、オーバーレイノード１００−Ｂは、エンドノード２００−Ｂ１のエッジノードである。また、エンドノード２００−Ｃ１、２００−Ｃ２は、オーバーレイノード１００−Ｃに接続されている。すなわち、オーバーレイノード１００−Ｃは、エンドノード２００−Ｃ１、２００−Ｃ２のエッジノードである。また、エンドノード２００−Ｓは、マルチキャストトラヒックの送信者（以下、「送信者エンドノード」と参照される）である。送信者エンドノード２００−Ｓは、オーバーレイノード１００−ＳＥに接続されている。すなわち、オーバーレイノード１００−ＳＥは、送信者エンドノード２００−Ｓのエッジノード（以下、「送信者エッジノード」と参照される）である。
【００１１】
センダーベース方式では、あるマルチキャストグループの送信者エンドノード２００−Ｓが、オーバーレイネットワーク全体に、当該マルチキャストグループの情報をブロードキャストする。各エンドノード２００は、ブロードキャストを受信する。当該マルチキャストグループへの参加を希望するエンドノード２００は、宛先が送信者エンドノード２００−Ｓに設定された参加要求を、オーバーレイネットワーク（エッジノード）に送信する。その参加要求は、オーバーレイノード１００によってオーバーレイネットワーク上で順次転送され、最終的に送信者エンドノード２００−Ｓに到達する。参加要求の転送の際、各オーバーレイノード１００は、直前のノード（すなわち、参加要求の送信元）を自身のマルチキャストルーティングテーブルに登録しておく。マルチキャストトラヒックの転送時、各オーバーレイノード１００は、マルチキャストルーティングテーブルに登録されたノード（すなわち、参加要求の送信元）に対して、トラヒックを転送する。このようにして、送信者エンドノード２００−Ｓから各エンドノード２００へのパス、すなわちマルチキャストツリーが作成される。
【００１２】
尚、センダーベース方式は、もともとＩＰマルチキャストで開発されたＤＶＭＲＰ（Distance Vector
Multicast Routing Protocol）（参照：非特許文献１）をオーバーレイマルチキャストに応用したものである。
【００１３】
図３は、「ランデブーベース方式」のマルチキャストツリーを示す模式図である。ランデブーベース方式によれば、マルチキャストグループの作成時に、任意の１つのオーバーレイノード１００が「ランデブーノード１００−ＲＰ」として選択される。そして、当該マルチキャストグループへの参加を希望するエンドノード２００は、宛先がそのランデブーノード１００−ＲＰに設定された参加要求を、オーバーレイネットワーク（エッジノード）に送信する。その参加要求は、オーバーレイノード１００によってオーバーレイネットワーク上で順次転送され、最終的にランデブーノード１００−ＲＰに到達する。参加要求の転送の際、各オーバーレイノード１００は、直前のノード（すなわち、参加要求の送信元）を自身のマルチキャストルーティングテーブルに登録しておく。
【００１４】
図３に示されるように、当該マルチキャストグループの送信者エンドノード２００−Ｓは、エッジノード１００−Ｅにトラヒックを送信する。エッジノード１００−Ｅは、受信したトラヒックを、一旦、ランデブーノード１００−ＲＰに向けて転送する。ランデブーノード１００−ＲＰは、当該トラヒックを受信すると、同一マルチキャストグループに参加する他の全エンドノード２００に向けてトラヒックを送信する。各オーバーレイノード１００は、マルチキャストルーティングテーブルに登録されたノード（すなわち、参加要求の送信元）に対して、トラヒックを転送する。このようにして、ランデブーノード１００−ＲＰと各エンドノード２００との間に双方向のパス、すなわちマルチキャストツリーが作成される。
【００１５】
ランデブーベース方式は、例えば、非特許文献２や非特許文献３に開示されている。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２００４−３０４７９９号公報
【非特許文献】
【００１７】
【非特許文献１】D. Waitzman et al., “Distance Vector MulticastRouting Protocol”, IETF, RFC 1075, November 1988.
【非特許文献２】Peter R. Pietzuch, “Hermes: A scalableevent-based middleware”, Technical Report, Number 590, UCAM-CL-TR-590, ISSN1476-2986, University of Cambridge, 2004.
【非特許文献３】M. Castro et al., “SCRIBE:A large-scale and decentralized application-level multicast infrastructure”,IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 20, NO. 8, OCTOBER 2002.
【発明の概要】
【発明が解決しようとする課題】
【００１８】
従来技術によれば、オーバーレイネットワーク上に構築されるマルチキャストツリーにおけるホップ数が大きくなり、エンドノード２００間のマルチキャストトラヒックの転送遅延が増大する可能性があった。
【００１９】
その理由は、上記ステップ（２）においてエッジノードが選択される際に、オーバーレイネットワークのトポロジーが考慮されていなかったためである。従来、エッジノードは、オーバーレイノード１００の中からランダムに選択されたり、エンドノード２００との物理的近傍性に基づいて選択されたりしていた。このとき、当該エッジノードと上述のランデブーノード１００−ＲＰや送信者エッジノード１００−ＳＥとの間のオーバーレイネットワーク上のホップ数は考慮されていない。そのため、選択されたエッジノードが、オーバーレイネットワークにおいてランデブーノード１００−ＲＰや送信者エッジノード１００−ＳＥから多ホップ離れたものとなる可能性があった。結果として、エンドノード２００間のホップ数が大きなマルチキャストツリーが作成されてしまい、エンドノード２００間のマルチキャストトラヒックの転送遅延が増大する。
【００２０】
本発明の１つの目的は、オーバーレイマルチキャストおいて、エンドノード間のマルチキャストトラヒックの転送遅延を短縮することにある。
【課題を解決するための手段】
【００２１】
オーバーレイネットワーク上にはマルチキャストツリーが構築される。オーバーレイネットワークにおいて、マルチキャストグループへの参加要求の転送方向が上流方向と定義され、その上流方向の逆方向が下流方向と定義される。マルチキャストツリーにおいて、下流側に隣接するノードは次ホップノードであり、上流側に隣接するノードは前ホップノードである。また、あるオーバーレイノードの「キャパシティ」は、当該オーバーレイノードに追加的に接続され得るエンドノードの許容数に相当するパラメータである。
【００２２】
本発明の第１の観点において、オーバーレイネットワークを構成するオーバーレイノードが提供される。そのオーバーレイノードは、キャパシティ管理部と再接続管理部とを備える。キャパシティ管理部は、自ノードのキャパシティを算出し、自ノードのキャパシティ及びアドレスを示すキャパシティ通知メッセージを次ホップノードに送信する。一方、再接続管理部は、上流側から受け取るキャパシティ通知メッセージに応答して、再接続指示処理を行う。ここで、上流側から受け取るキャパシティ通知メッセージで示されるキャパシティ及びアドレスは、それぞれ、通知キャパシティ及び上流ノードアドレスと参照される。再接続指示処理において、再接続管理部は、通知キャパシティを参照して、自ノードに現在接続されているローカルエンドノードから上述の許容数以内のエンドノードを選択する。そして、再接続管理部は、選択されたエンドノードに対して、上流ノードアドレスで指定されるオーバーレイノードである上流ノードへ再接続するように指示する。
【００２３】
本発明の第２の観点において、マルチキャストツリーが構築されたオーバーレイネットワークシステムが提供される。そのマルチキャストツリーは、第１オーバーレイノードと、第１オーバーレイノードよりも下流側に位置する第２オーバーレイノードと、を備える。第１オーバーレイノードは、第１オーバーレイノードのキャパシティを算出し、第１オーバーレイノードのキャパシティ及びアドレスを示すキャパシティ通知メッセージを下流に送信する。第２オーバーレイノードは、キャパシティ通知メッセージで示される第１オーバーレイノードのキャパシティを参照して、第２オーバーレイノードに現在接続されているローカルエンドノードから上述の許容数以内のエンドノードを選択する。更に、第２オーバーレイノードは、第１オーバーレイノードのアドレスを示す再接続指示メッセージを、選択されたエンドノードに送信する。選択されたエンドノードは、再接続指示メッセージを受け取ると、第１オーバーレイノードに対して再接続要求を送信し、第２オーバーレイノードの代わりに第１オーバーレイノードを新たなエッジノードとする。
【００２４】
本発明の第３の観点において、オーバーレイネットワーク上に構築されたマルチキャストツリーにおけるエンドノードの再接続方法が提供される。当該マルチキャストツリーは、第１オーバーレイノードと、第１オーバーレイノードよりも下流側に位置する第２オーバーレイノードと、を備える。再接続方法は、（Ａ）第１オーバーレイノードにおいて、第１オーバーレイノードのキャパシティを算出するステップと、（Ｂ）第１オーバーレイノードのキャパシティ及びアドレスを示すキャパシティ通知メッセージを、第１オーバーレイノードから下流に送信するステップと、（Ｃ）第２オーバーレイノードにおいて、キャパシティ通知メッセージで示される第１オーバーレイノードのキャパシティに基づいて、第２オーバーレイノードに現在接続されているローカルエンドノードから上述の許容数以内のエンドノードを選択するステップと、（Ｄ）第１オーバーレイノードのアドレスを示す再接続指示メッセージを、第２オーバーレイノードから、上記選択されたエンドノードに送信するステップと、（Ｅ）再接続指示メッセージに応答して、選択されたエンドノードから第１オーバーレイノードに対して再接続要求を送信するステップと、を含む。
【発明の効果】
【００２５】
本発明によれば、オーバーレイマルチキャストおいて、エンドノード間のマルチキャストトラヒックの転送遅延を短縮することが可能となる。
【図面の簡単な説明】
【００２６】
【図１】図１は、オーバーレイネットワークを示す模式図である。
【図２】図２は、オーバーレイネットワーク上に構築されるセンダーベース方式のマルチキャストツリーを示す模式図である。
【図３】図３は、オーバーレイネットワーク上に構築されるランデブーベース方式のマルチキャストツリーを示す模式図である。
【図４】図４は、本発明の実施の形態におけるエンドノード再接続処理を説明するための概略図である。
【図５】図５は、本発明の第１の実施の形態に係るオーバーレイノードの構成を示すブロック図である。
【図６】図６は、マルチキャストルーティングテーブルの一例を示している。
【図７】図７は、マルチキャストツリーにおけるノード間の通信の一例を示している。
【図８】図８は、トラヒック情報の一例を示している。
【図９】図９は、本発明の実施の形態に係るエンドノードの構成を示すブロック図である。
【図１０】図１０は、第１の実施の形態における動作例を説明するための模式図である。
【図１１】図１１は、第１の実施の形態における動作例を説明するための模式図である。
【図１２】図１２は、本発明の第２の実施の形態に係るオーバーレイノードの構成を示すブロック図である。
【図１３】図１３は、本発明の第３の実施の形態に係るオーバーレイノードの構成を示すブロック図である。
【図１４】図１４は、第３の実施の形態における動作例を説明するための模式図である。
【図１５】図１５は、図１４中の各オーバーレイノード及び各エンドノードの状態を要約的に示すテーブルである。
【図１６】図１６は、本発明の第４の実施の形態に係るオーバーレイノードの構成を示すブロック図である。
【図１７】図１７は、第４の実施の形態における動作例を説明するための模式図である。
【図１８】図１８は、図１７中の各オーバーレイノード及び各エンドノードの状態を要約的に示すテーブルである。
【図１９】図１９は、エンドノード管理情報の一例を示している。
【発明を実施するための形態】
【００２７】
本発明の実施の形態でも、図１で示されたようなオーバーレイネットワーク（オーバーレイネットワークシステム）が構築される。また、オーバーレイネットワーク上には、図２や図３で示されたようなマルチキャストツリーが構築される。まず、本実施の形態において用いられる用語の定義を行う。
【００２８】
オーバーレイネットワークにおいて、マルチキャストグループへの参加要求の転送方向が「上流」方向と定義される（図２及び図３参照）。一方、上流方向の逆方向が「下流」方向と定義される。最上流のオーバーレイノード１００は、基点ノードと参照される。図２で示されたように、マルチキャストツリーがセンダーベース方式に基づく場合、基点ノードは送信者エッジノード１００−ＳＥである。図３で示されたように、マルチキャストツリーがランデブーベース方式に基づく場合、基点ノードはランデブーノード１００−ＲＰである。マルチキャストツリーにおいて、基点ノード（１００−ＳＥ，１００−ＲＰ）により近づく方向が上流方向であり、その基点ノードからより離れる方向が下流方向である。
【００２９】
また、マルチキャストツリーにおいて、自ノードの下流側に隣接するノードは、「次ホップノード」と参照される。一方、マルチキャストツリーにおいて、自ノードの上流側に隣接するノードは、「前ホップノード」と参照される。すなわち、自ノードに参加要求を送信した送信元が次ホップノードであり、自ノードが参加要求を転送する転送先が前ホップノードである。言い換えれば、次ホップノードは、自ノードよりも基点ノード（１００−ＳＥ，１００−ＲＰ）から遠く、前ホップノードは、自ノードよりも基点ノードから近い。図２で示されたセンダーベース方式の場合、次ホップノードは、マルチキャストトラヒックの転送先と一致する。
【００３０】
但し、図３で示されたランデブーベース方式の場合、次ホップノードは、マルチキャストトラヒックの転送先と必ずしも一致しない。例えば図３において、送信者エンドノード２００−Ｓとランデブーノード１００−ＲＰとの間に位置するオーバーレイノード１００−Ｅは、隣接するオーバーレイノード１００−Ｄに参加要求を転送する。従って、オーバーレイノード１００−Ｄは、オーバーレイノード１００−Ｅの前ホップノードである。そして、オーバーレイマルチキャストにおいて、オーバーレイノード１００−Ｅは、前ホップノードであるオーバーレイノード１００−Ｄにマルチキャストトラヒックを転送する。
【００３１】
また、あるオーバーレイノード１００をエッジノードとするエンドノード２００は、当該オーバーレイノード１００の「ローカルエンドノード」と参照される。あるオーバーレイノード１００のローカルエンドノード２００は、当該オーバーレイノード１００に直接接続されている。あるオーバーレイノード１００に接続可能なローカルエンドノード２００の総数は、最大接続可能台数ＮＭである。そのオーバーレイノード１００に現在接続されているローカルエンドノード２００の数は、現在接続台数ＮＣである。そして、最大接続可能台数ＮＭと現在接続台数ＮＣとの差分（ＮＭ−ＮＣ）は、追加接続許容台数ＮＡである。追加接続許容台数ＮＡは、当該オーバーレイノード１００に追加的に接続され得るローカルエンドノード２００の許容数である。
【００３２】
追加接続許容台数ＮＡは、オーバーレイノード１００のリソース残余量等に依存する。追加接続許容台数ＮＡは、オーバーレイノード１００のリソース残余量等のパラメータに基づいて推定可能である。追加接続許容台数ＮＡ、及びその追加接続許容台数ＮＡの推定に用いられるパラメータは、まとめて「キャパシティ」と参照される。つまり、キャパシティとは、追加接続許容台数ＮＡに相当するパラメータであると言える。本実施の形態では、オーバーレイノード１００に関して、このキャパシティという概念が用いられる。
【００３３】
次に、図４を参照して、本実施の形態に係る処理の概要を説明する。
【００３４】
図４には、あるマルチキャストグループに関するマルチキャストツリーの主要な構成が示されている。該マルチキャストツリーは、基点ノード（送信者エッジノード１００−ＳＥ、あるいは、ランデブーノード１００−ＲＰ）、第１オーバーレイノード１００−１、第２オーバーレイノード１００−２、及びエンドノード２００を備えている。第２オーバーレイノード１００−２は、第１オーバーレイノード１００−１よりも下流に位置している。すなわち、第１オーバーレイノード１００−１は、第２オーバーレイノード１００−２よりも基点ノードに近い。尚、上流側の第１オーバーレイノード１００−１と下流側の第２オーバーレイノード１００−２は、互いに隣接していなくてもよい。
【００３５】
エンドノード２００は、送信者エンドノードであっても受信者エンドノードであってもよい。本実施の形態に係る処理（エンドノード再接続）が実行される前の段階で、エンドノード２００は、第２オーバーレイノード１００−２に接続している。つまり、第２オーバーレイノード１００−２は、エンドノード２００のエッジノードである。本実施の形態によれば、次のような処理が実行される。
【００３６】
（１）第１オーバーレイノード１００−１は、自ノード（第１オーバーレイノード１００−１）のキャパシティを算出する。
【００３７】
（２）第１オーバーレイノード１００−１は、自ノード（第１オーバーレイノード１００−１）のキャパシティ及びアドレスを示す「キャパシティ通知メッセージＣＭＳＧ」を生成する。そして、第１オーバーレイノード１００−１は、そのキャパシティ通知メッセージＣＭＳＧを下流方向に送信する。
【００３８】
（３）第２オーバーレイノード１００−２は、上流側からキャパシティ通知メッセージＣＭＳＧを受け取る。受け取ったキャパシティ通知メッセージＣＭＳＧには、上流の第１オーバーレイノード１００−１のキャパシティ（通知キャパシティ）及びアドレス（上流ノードアドレス）が示されている。
【００３９】
（４）第２オーバーレイノード１００−２は、受け取ったキャパシティ通知メッセージＣＭＳＧで示される通知キャパシティと、自ノード（第２オーバーレイノード１００−２）に現在接続されているローカルエンドノード２００の状態とを照らし合わせる。そして、第２オーバーレイノード１００−２は、ローカルエンドノード２００から、第１オーバーレイノード１００−１に関する追加接続許容台数ＮＡ以内のエンドノード２００を選択する。
【００４０】
（５）第２オーバーレイノード１００−２は、選択されたローカルエンドノード２００に対して、より上流側の第１オーバーレイノード１００−１への“再接続”を指示する。より詳細には、第２オーバーレイノード１００−２は、選択されたローカルエンドノード２００に「再接続指示メッセージＲＭＳＧ」を送信する。再接続指示メッセージＲＭＳＧは、キャパシティ通知メッセージＣＭＳＧに含まれていた上流ノードアドレス、すなわち、第１オーバーレイノード１００−１のアドレスを示す。
【００４１】
（６）選択されたエンドノード２００は、再接続指示メッセージＲＭＳＧを受け取る。当該エンドノード２００は、受け取った再接続指示メッセージＲＭＳＧで指定された第１オーバーレイノード１００−１に対して、「再接続要求ＲＲＥＱ」を送信する。
【００４２】
（７）第１オーバーレイノード１００−１は、ローカルエンドノードではない下流のエンドノード２００から再接続要求ＲＲＥＱを受け取る。他のエンドノード２００からの要求を既に受け入れた等の理由によりキャパシティが不足している場合、第１オーバーレイノード１００−１は、再接続要求ＲＲＥＱを拒否する。新規ローカルエンドノードを接続可能な場合、第１オーバーレイノード１００−１は、再接続要求ＲＲＥＱを受け入れる。
【００４３】
（８）再接続要求ＲＲＥＱが受け入れられた場合、エンドノード２００は、マルチキャストグループへの参加要求を、第１オーバーレイノード１００−１に対して送信する。その結果、エンドノード２００は、第１オーバーレイノード１００−１に再接続し、第２オーバーレイノード１００−２の代わりに第１オーバーレイノード１００−１を新たなエッジノードとする。すなわち、エンドノード２００のエッジノード（接続先）が、基点ノード（１００−ＳＥ，１００−ＲＰ）から遠い第２オーバーレイノード１００−２から、基点ノードにより近い第１オーバーレイノード１００−１に変更される。尚、エンドノード２００は、元のエッジノードである第２オーバーレイノード１００−２に、脱退要求を送信してもよい。
【００４４】
以上に説明されたように、本実施の形態に係るエンドノード再接続処理によって、エンドノード２００のエッジノードが、基点ノードから遠い第２オーバーレイノード１００−２から、基点ノードにより近い第１オーバーレイノード１００−１に変更される。その結果、オーバーレイネットワーク上でのエンドノード間のホップ数が減少する。従って、オーバーレイマルチキャストおいて、エンドノード間のマルチキャストトラヒックの転送遅延が短縮される。
【００４５】
また、本実施の形態では、上流側の第１オーバーレイノード１００−１の追加接続許容台数ＮＡの範囲内で、再接続指示対象のローカルエンドノード２００が選択される。もし、第１オーバーレイノード１００−１に多数の新規エンドノードがむやみに接続されたとすると、その第１オーバーレイノード１００−１にかかる負荷が極端に増大し、転送遅延がかえって悪化するという問題が発生し得る。本実施の形態によれば、そのような問題は発生しない。
【００４６】
更に、本実施の形態では、エンドノード２００の接続先（エッジノード）が変更されるのみである。オーバーレイネットワークやマルチキャストツリーのトポロジーを変更する必要は一切無い。つまり、トポロジーを変更することなく、マルチキャストトラヒックの転送遅延を短縮することが可能である。トポロジー変更に伴うオーバーレイネットワークのルーティングテーブル及びマルチキャストルーティングテーブルの再構築は不要である。
【００４７】
１．第１の実施の形態
１−１．オーバーレイノード１００
図５は、第１の実施の形態に係るオーバーレイノード１００の構成を示すブロック図である。オーバーレイノード１００は、記憶部１１０、通信部１２０、参加要求転送部１３０、トラヒック転送部１４０、エンドノード管理部１５０、キャパシティ管理部１６０、及び再接続管理部１７０を備えている。以下、各部の機能を詳しく説明する。
【００４８】
（記憶部１１０）
記憶部１１０は、ＲＡＭやＨＤＤを含む記憶装置である。記憶部１１０には、本実施の形態に係る処理に必要な各種情報が格納される。例えば、記憶部１１０には、後述されるマルチキャストルーティングテーブルＲＴＮ、トラヒック情報ＴＦＣ、エンドノード管理情報ＥＮＤが格納される。
【００４９】
（通信部１２０）
通信部１２０は、オーバーレイネットワーク上において隣接する他のオーバーレイノード１００に対して仮想リンクを張り、それら隣接ノードとの間で通信を行う。以下に説明される各部は、この通信部１２０を通して外部から情報を受信し、また、外部へ情報を送信する。
【００５０】
（参加要求転送部１３０）
参加要求転送部１３０は、マルチキャストグループへの参加要求及びマルチキャストグループからの脱退要求を転送する。また、参加要求転送部１３０は、記憶部１１０に格納されたマルチキャストルーティングテーブルＲＴＮの更新（エントリの登録、削除）を行う。
【００５１】
具体的には、参加要求転送部１３０は、次ホップノード（つまり、ローカルエンドノード２００あるいは他のオーバーレイノード１００）から、参加要求または脱退要求を受け取る。参加要求や脱退要求には、マルチキャストグループのＩＤとその次ホップノードのアドレス（次ホップアドレス）が記載されている。参加要求を受け取った場合、参加要求転送部１３０は、マルチキャストグループＩＤ及び次ホップアドレスを新エントリとして、マルチキャストルーティングテーブルＲＴＮに登録する。脱退要求を受け取った場合、参加要求転送部１３０は、当該マルチキャストグループＩＤの次ホップアドレスを示すエントリを、マルチキャストルーティングテーブルＲＴＮから削除する。その後、参加要求転送部１３０は、自ノードのアドレスが記載された参加要求または脱退要求を、前ホップノードに送信する。尚、自ノードが基点ノード（送信者エッジノード１００−ＳＥあるいはランデブーノード１００−ＲＰ）である場合は、転送は行われない。
【００５２】
図６は、マルチキャストルーティングテーブルＲＴＮの一例を示している。マルチキャストルーティングテーブルＲＴＮには、マルチキャストグループＩＤと次ホップアドレス（すなわち、マルチキャストトラヒックを転送すべきノード）が登録される。例えば、オーバーレイノード１００がマルチキャストグループＧｒｏｕｐ−Ａ宛のマルチキャストトラヒックを受信した場合、そのマルチキャストトラヒックはオーバーレイノード１００−１０、１００−１５、及びローカルエンドノード２００−１、２００−２に転送される。
【００５３】
（トラヒック転送部１４０）
トラヒック転送部１４０は、他のノードからマルチキャストトラヒックを受信すると、上記マルチキャストルーティングテーブルＲＴＮを参照して、当該マルチキャストトラヒックを転送する。また、トラヒック転送部１４０は、マルチキャストトラヒックの転送処理に基づいてトラヒック情報ＴＦＣを生成・更新する。トラヒック情報ＴＦＣは、自ノードが処理しているマルチキャストトラヒックの状態を示す情報であり、記憶部１１０に格納される。
【００５４】
図７は、オーバーレイノード１００−Ｂが処理しているマルチキャストトラヒックの状態の一例を示している。オーバーレイノード１００−Ｂは、二つのマルチキャストグループＸ、Ｙのマルチキャストツリーに接続しているとする。図７において、マルチキャストグループＸに関する仮想リンク及び通信は実線で示され、マルチキャストグループＹに関する仮想リンク及び通信は破線で示されている。オーバーレイノード１００−Ｂには、オーバーレイノード１００−Ａ、１００−Ｃ、１００−Ｐ、１００−Ｑ、及びエンドノード（ローカルエンドノード）２００−ａ〜２００−ｃが接続されている。エンドノード２００−ｂは送信者エンドノードであり、エンドノード２００−ａ及び２００−ｃは受信者エンドノードである。
【００５５】
図８は、図７で示されたオーバーレイノード１００−Ｂが有するトラヒック情報ＴＦＣの一例を示している。トラヒック情報ＴＦＣは、トラヒックＩＤ、受信／送信、及び平均トラヒック量を示している。尚、図８において、トラヒックＩＤ：ＴＲ＿［Ｍ］−［Ｎ］［Ｌ］は、ノード［Ｎ］からノード［Ｌ］へ流れるマルチキャストグループ［Ｍ］のマルチキャストトラヒックを意味する。
【００５６】
（エンドノード管理部１５０）
エンドノード管理部１５０は、エンドノード２００の状態を管理する。エンドノード管理部１５０は、ローカルエンドノード監視部１５１を含んでいる。
【００５７】
（ローカルエンドノード監視部１５１）
ローカルエンドノード監視部１５１は、自ノードにつながるローカルエンドノード２００の状態を監視する。ここで、ローカルエンドノードの状態とは、ローカルエンドノード２００の台数、ローカルエンドノード２００への送出トラヒック量、ローカルエンドノード２００からの受信トラヒック量などを含む。図７及び図８で示された例の場合、「ローカルエンドノード台数＝３、２００−ａへの送出トラヒック量＝１０Ｍｂｐｓ、２００−ｂからの受信トラヒック量＝５Ｍｂｐｓ、２００−ｃへの送出トラヒック量＝５Ｍｂｐｓ」である。ローカルエンドノード監視部１５１は、これらローカルエンドノードの状態を、記憶部１１０に格納されたエンドノード管理情報ＥＮＤに記載する。
【００５８】
（キャパシティ管理部１６０）
キャパシティ管理部１６０は、自ノードのキャパシティを算出し、キャパシティ通知メッセージＣＭＳＧを次ホップノードに送信する。より詳細には、キャパシティ管理部１６０は、キャパシティ算出部１６１、キャパシティ按分部１６２、及び通知メッセージ生成部１６３を含んでいる。
【００５９】
（キャパシティ算出部１６１）
キャパシティ算出部１６１は、自ノードのキャパシティを算出（推定）する。具体的には、キャパシティ算出部１６１は、自ノードのリソース残余量を算出する。また、可能な場合には、キャパシティ算出部１６１は、リソース残余量から追加接続許容台数ＮＡを更に算出してもよい。キャパシティは、リソース残余量及び／あるいは追加接続許容台数ＮＡを含む。
【００６０】
＜リソース残余量の算出＞
リソースとしては、トラヒック受信／送出能力、ＣＰＵ使用率、メモリ使用量などが挙げられる。例えば、トラヒック受信／送出能力の場合、キャパシティ算出部１６１は、上述のトラヒック情報ＴＦＣを参照することによって、トラヒック受信／送出能力の残余量を算出することができる。以下、図７及び図８で示された例の場合のトラヒック受信／送出能力の残余量を説明する。
【００６１】
図８に示されるように、オーバーレイノード１００−Ｂの平均受信トラヒック量は、マルチキャストグループＸに関して１５Ｍｂｐｓ（ＴＲ＿Ｘ−ＡＢ＋ＴＲ＿Ｘ−ｂＢ）であり、マルチキャストグループＹに関して５Ｍｂｐｓ（ＴＲ＿Ｙ−ＰＢ）であり、合計２０Ｍｂｐｓである。また、オーバーレイノード１００−Ｂの平均送出トラヒック量は、マルチキャストグループＸに関して２５Ｍｂｐｓ（ＴＲ＿Ｘ−ＢＡ＋ＴＲ＿Ｘ−ＢＣ＋ＴＲ＿Ｘ−Ｂａ）であり、マルチキャストグループＹに関して１０Ｍｂｐｓ（ＴＲ＿Ｙ−ＢＱ＋ＴＲ＿Ｙ−Ｂｃ）であり、合計３５Ｍｂｐｓである。ここで、オーバーレイノード１００−Ｂは、全二重１００Ｍｂｐｓの帯域幅のリンクに接続しているとする。この場合、オーバーレイノード１００−Ｂに残されているトラヒック受信能力及びトラヒック送出能力は、それぞれ、８０Ｍｂｐｓ及び６５Ｍｂｐｓである。これらが、オーバーレイノード１００−Ｂのリソース残余量（受信／送出トラヒック残余量）である。
【００６２】
＜追加接続許容台数ＮＡの算出＞
追加接続許容台数ＮＡを算出するためには、ローカルエンドノード２００の追加接続によってキャパシティ消費量（つまり、リソース使用量）がどの程度増加するかを把握する必要がある。例えば、リソースとしてトラヒック受信／送出能力を考える場合、ローカルエンドノード２００の追加接続によって受信／送出トラヒック量がどの程度増加するかが分かればよい。既に接続されている各ローカルエンドノード２００の受信／送出トラヒック量（キャパシティ消費量）は、上述のエンドノード管理情報ＥＮＤに記載されている。従って、エンドノード管理情報ＥＮＤを参照することによって、追加接続許容台数ＮＡを算出（推定）することが可能である。
【００６３】
図７及び図８で示された例において、マルチキャストグループＸの受信者エンドノード２００−ａへの送出トラヒック量は、１０Ｍｂｐｓである。マルチキャストグループＸの送信者エンドノード２００−ｂからの受信トラヒック量は、５Ｍｂｐｓである。マルチキャストグループＹの受信者エンドノード２００−ｃへの送出トラヒック量は、５Ｍｂｐｓである。エンドノード管理情報ＥＮＤで示されるこれらパラメータは、各ローカルエンドノード２００のキャパシティ消費量である。
【００６４】
受信者エンドノードに関する追加接続許容台数ＮＡは、次の通りである。マルチキャストグループＸの場合、受信者エンドノード２００−ａへの送出トラヒック量は１０Ｍｂｐｓであり、マルチキャストグループＹの場合、受信者エンドノード２００−ｃへの送出トラヒック量は５Ｍｂｐｓである。また、オーバーレイノード１００−Ｂに残されているトラヒック送出能力は６５Ｍｂｐｓである。従って、マルチキャストグループＸの場合、追加接続許容台数ＮＡは６台であり、マルチキャストグループＹの場合、追加接続許容台数ＮＡは１３台である。
【００６５】
送信者エンドノードに関する追加接続許容台数ＮＡの算出はより複雑である。それは、送信者エンドノードが追加接続されると、オーバーレイノード１００は、当該送信者エンドノードからトラヒックを受信するだけでなく、受信したトラヒックを隣接ノードに更に送信するからである。すなわち、送信者エンドノードが追加接続されると、受信トラヒック量だけでなく送出トラヒック量も増加する。
【００６６】
図７及び図８で示された例において、マルチキャストグループＸの送信者エンドノード２００−ｂからの受信トラヒック量は５Ｍｂｐｓである。また、マルチキャストグループＸのトラヒックを受信すると、オーバーレイノード１００−Ｂは、そのトラヒックを３台のノード１００−Ａ、１００−Ｃ、２００−ａに転送する（トラヒックＩＤ＝ＴＲ＿Ｘ−ＢＡ、ＴＲ＿Ｘ−ＢＣ、ＴＲ＿Ｘ−Ｂａ）。すなわち、送信者エンドノードが１台追加接続されると、オーバーレイノード１００−Ｂの受信トラヒック量は５Ｍｂｐｓ増加し、その送出トラヒック量は１５Ｍｂｐｓ（＝５Ｍｂｐｓ×３台）増加する。オーバーレイノード１００−Ｂに残されているトラヒック受信能力及びトラヒック送出能力は、それぞれ８０Ｍｂｐｓ及び６５Ｍｂｐｓであるため、送信者エンドノードの追加接続許容台数ＮＡは４台である。
【００６７】
このように、送信者エンドノードに関する追加接続許容台数ＮＡを算出するためには、送信者エンドノードが送出するトラヒック量に加えて、受信トラヒックの転送先の数まで把握しておく必要がある。追加接続許容台数ＮＡの算出に用いられるこれらのパラメータも「キャパシティ」に含まれる。尚、サーバなどで全送信者エンドノードを管理しておき、サーバに問い合わせるなどして追加接続させる送信者エンドノードの送出トラヒック量を把握してもよい。
【００６８】
（キャパシティ按分部１６２）
キャパシティ按分部１６２は、必要に応じて、上記キャパシティを分割（按分）する。分割が必要な場合としては、自ノードが複数のマルチキャストグループに参加している場合や、同一マルチキャストグループの次ホップノードが複数存在する場合が挙げられる。
【００６９】
＜自ノードが複数のマルチキャストグループに参加している場合＞
例えば、図７及び図８で示された例において、オーバーレイノード１００−Ｂは、２つのマルチキャストグループＸ、Ｙに参加している。また、送出トラヒック残余量は６５Ｍｂｐｓである。この場合、例えば、キャパシティ按分部１６２は、マルチキャストグループＸに４５Ｍｂｐｓ（ＮＡ＝４に相等）を割り当て、マルチキャストグループＹに２０Ｍｂｐｓ（ＮＡ＝４に相等）を割り当てる。但し、分割比率は任意である。
【００７０】
＜同一マルチキャストグループの次ホップノードが複数存在する場合＞
この場合は、マルチキャストルーティングテーブルＲＴＮ（図６参照）において、同一マルチキャストグループＩＤに対して複数の次ホップアドレスが登録されている場合に相等する。この場合、キャパシティ按分部１６２は、当該マルチキャストグループに割り当てられたキャパシティを、それら複数の次ホップノード間で分割する。例えば、キャパシティ按分部１６２は、キャパシティを複数の次ホップノード間で均等に分割する。但し、分割比率は任意である。
【００７１】
（通知メッセージ生成部１６３）
通知メッセージ生成部１６３は、キャパシティ通知メッセージＣＭＳＧを生成する。キャパシティ通知メッセージＣＭＳＧは、該当するマルチキャストグループに関する自ノードキャパシティ及び自ノードのアドレス（自ノードへの接続情報）を示している。マルチキャストグループ間でキャパシティが分割された場合は、マルチキャストグループ毎にキャパシティ通知メッセージＣＭＳＧが作成される。また、次ホップノード間でキャパシティが分割された場合は、次ホップノード毎にキャパシティ通知メッセージＣＭＳＧが作成される。
【００７２】
通知メッセージ生成部１６３は、マルチキャストルーティングテーブルＲＴＮを参照して、キャパシティ通知メッセージＣＭＳＧを次ホップノードに送信する。キャパシティの分割により複数のキャパシティ通知メッセージＣＭＳＧが作成された場合、通知メッセージ生成部１６３は、それら複数のキャパシティ通知メッセージＣＭＳＧをそれぞれ対応する次ホップノードに送信する。以下の説明において、あるオーバーレイノード１００から下流に向けて送信されるキャパシティ通知メッセージＣＭＳＧは、「キャパシティ通知メッセージＣＭＳＧ−ＤＮ」と参照される場合がある。
【００７３】
（再接続管理部１７０）
オーバーレイノード１００は、前ホップノードから送信されたキャパシティ通知メッセージＣＭＳＧを受信する立場になることもある。以下の説明において、あるオーバーレイノード１００が上流から受け取るキャパシティ通知メッセージＣＭＳＧは、「キャパシティ通知メッセージＣＭＳＧ−ＵＰ」と参照される場合がある。
【００７４】
キャパシティ通知メッセージＣＭＳＧ−ＵＰを処理するのは再接続管理部１７０である。再接続管理部１７０は、エンドノード選択部１７１と指示部１７２を含んでいる。この再接続管理部１７０は、キャパシティ通知メッセージＣＭＳＧ−ＵＰに応答して、次に説明される「再接続指示処理」を行う。
【００７５】
（エンドノード選択部１７１）
エンドノード選択部１７１は、自ノードに現在接続されているローカルエンドノード２００の中から、再接続指示対象を選択する。この選択処理において、エンドノード選択部１７１は、キャパシティ通知メッセージＣＭＳＧ−ＵＰで示される上流ノードのキャパシティ（通知キャパシティ）を参照する。そして、エンドノード選択部１７１は、選択されるローカルエンドノード２００のキャパシティ消費量の合計が通知キャパシティ以下となるように、ローカルエンドノード２００を選択する。すなわち、エンドノード選択部１７１は、上流ノードに関する追加接続許容台数ＮＡ以内のローカルエンドノード２００を選択する。
【００７６】
例えば、通知キャパシティが、上流ノードのリソース残余量（例えば、受信／送出トラヒック残余量）である場合を考える。この場合、エンドノード選択部１７１は、上述のエンドノード管理情報ＥＮＤを参照して、各ローカルエンドノード２００のリソース使用量（例えば、受信／送出トラヒック量）を把握する。そして、エンドノード選択部１７１は、選択されるローカルエンドノード２００のリソース使用量の合計がリソース残余量以下となるように、ローカルエンドノード２００を選択する。これは、上述の＜追加接続許容台数ＮＡの算出＞で説明された手法で得られる追加接続許容台数ＮＡ以内でローカルエンドノード２００を選択することに相当する。
【００７７】
通知キャパシティが上流ノードの追加接続許容台数ＮＡそのものである場合、エンドノード選択部１７１は、その追加接続許容台数ＮＡ以内のローカルエンドノード２００をすぐに選択することができる。この場合は、選択されるローカルエンドノード２００の総数がキャパシティ消費量の合計に相当する。
【００７８】
（指示部１７２）
指示部１７２は、エンドノード選択部１７１によって選択されたローカルエンドノード２００に対して、“上流ノードへの再接続”を指示する。より詳細には、指示部１７２は、選択されたローカルエンドノード２００に再接続指示メッセージＲＭＳＧを送信する。再接続指示メッセージＲＭＳＧは、キャパシティ通知メッセージＣＭＳＧ−ＵＰに含まれていたアドレス（上流ノードアドレス）及びマルチキャストグループを示す。
【００７９】
１−２．エンドノード２００
図９は、本実施の形態に係るエンドノード２００の構成を示すブロック図である。エンドノード２００は、参加要求送信部２１０、トラヒック送受信部２２０、及び再接続処理部２３０を備えている。
【００８０】
参加要求送信部２１０は、マルチキャストグループへの参加要求あるいはマルチキャストグループからの脱退要求を作成する。そして、参加要求送信部２１０は、参加要求あるいは脱退要求を、指定されたオーバーレイノード１００（エッジノード、あるいは、再接続指示メッセージＲＭＳＧで指定された上流ノード）に送信する。
【００８１】
トラヒック送受信部２２０は、特定のマルチキャストグループ宛てのマルチキャストトラヒックをエッジノード１００へ送信する。また、トラヒック送受信部２２０は、特定のマルチキャストグループからのマルチキャストトラヒックをエッジノード１００から受信する。
【００８２】
再接続処理部２３０は、現在のエッジノードから上述の再接続指示メッセージＲＭＳＧを受け取る。その再接続指示メッセージＲＭＳＧは、上流ノードを指定する上流ノードアドレスを含んでいる。再接続処理部２３０は、上流ノードアドレスを参照し、当該上流ノードに対して再接続要求ＲＲＥＱを送信する。上流ノードが再接続要求ＲＲＥＱを受け入れた場合、再接続処理部２３０は、参加要求送信部２１０に対して、該当するマルチキャストグループへの参加要求を上流ノードに送信するよう指示する。その結果、エッジノードが、より基点ノードに近い上流ノードに変更される。またこのとき、元のエッジノードに対して脱退要求を送信してもよい。
【００８３】
１−３．動作例
次に、図１０及び図１１を参照して、本実施の形態に係るオーバーレイマルチキャストシステムの動作例を説明する。図１０及び図１１には、あるマルチキャストグループのマルチキャストツリーの一部が示されている。オーバーレイノード１００−Ａは、オーバーレイノード１００−Ｂの前ホップノードである。オーバーレイノード１００−Ｃ、１００−Ｅは共に、オーバーレイノード１００−Ｂの次ホップノードである。オーバーレイノード１００−Ｄは、オーバーレイノード１００−Ｃの次ホップノードである。オーバーレイノード１００−Ｂにはエンドノード２００−Ｂｘ、２００−Ｂｙ、２００−Ｂｚが接続されている。オーバーレイノード１００−Ｃにはエンドノード２００−Ｃｘが接続されている。オーバーレイノード１００−Ｅにはエンドノード２００−Ｅｘが接続されている。
【００８４】
以下、オーバーレイノード１００−Ｂがキャパシティ通知メッセージＣＭＳＧ−ＵＰを受信する場合と、オーバーレイノード１００−Ｂがキャパシティ通知メッセージＣＭＳＧ−ＤＮを送信する場合とに分けて説明を行う。尚、以下の説明において、エンドノード２００はすべて受信者エンドノードであるする。
【００８５】
１−３−１．キャパシティ通知メッセージ受信時の動作
図１０に示されるように、オーバーレイノード１００−Ｂは、オーバーレイノード１００−Ａからキャパシティ通知メッセージＣＭＳＧ−ＵＰを受信する。キャパシティ通知メッセージＣＭＳＧ−ＵＰは、オーバーレイノード１００−Ａのキャパシティとアドレスを示している。再接続管理部１７０は、通知キャパシティを参照して、ローカルエンドノード２００−Ｂｘ、２００−Ｂｙ、２００−Ｂｚの中から再接続指示対象を選択する。
【００８６】
例として、キャパシティ通知メッセージＣＭＳＧ−ＵＰが「受信者エンドノードに関する追加接続許容台数ＮＡ＝２」を示している場合を考える。この場合、再接続管理部１７０は、２台以内のローカルエンドノード２００を対象として選択する。対象は任意に選択されてもよいし、所定のポリシーに従って選択されてもよい。例えば、オーバーレイノード１００−Ｂに接続していた時間が長いものから優先的に選択したり、オーバーレイノード１００−Ｂからのトラヒック送出量が多いものから優先的に選択したりするといったポリシーが考えられる。このようなポリシーは、再接続管理部１７０に予め設定されていてもよいし、キャパシティ通知メッセージＣＭＳＧ−ＵＰに記載されていてもよい。
【００８７】
他の例として、キャパシティ通知メッセージＣＭＳＧ−ＵＰが「オーバーレイノード１００−Ａの送出トラヒック残余量（リソース残余量）＝６０Ｍｂｐｓ」を示している場合を考える。また、ローカルエンドノード２００−Ｂｘ、２００−Ｂｙ、２００−Ｂｚのそれぞれへの送出トラヒック量（リソース使用量）が、２０Ｍｂｐｓ、３０Ｍｂｐｓ、３０Ｍｂｐｓであるとする。この場合、再接続管理部１７０は、リソース使用量の合計が６０Ｍｂｐｓ以下となるようにローカルエンドノード２００を選択する。例えば、２台のローカルエンドノード２００−Ｂｙ、２００−Ｂｚが選択される。上述の同様に、対象は任意に選択されてもよいし、所定のポリシーに従って選択されてもよい。
【００８８】
更に、再接続管理部１７０は、選択されたローカルエンドノード２００に再接続指示メッセージＲＭＳＧを送信する。再接続指示メッセージＲＭＳＧは、オーバーレイノード１００−Ａのアドレス（上流ノードアドレス）を示す。
【００８９】
例えば、エンドノード２００−Ｂｙが再接続指示メッセージＲＭＳＧを受け取る。エンドノード２００−Ｂｙは、オーバーレイノード１００−Ａに対して再接続要求ＲＲＥＱを送信する。オーバーレイノード１００−Ａは再接続要求ＲＲＥＱを受け入れる。そして、エンドノード２００−Ｂｙは、脱退要求をオーバーレイノード１００−Ｂに送信し、参加要求をオーバーレイノード１００−Ａに送信する。その結果、エンドノード２００−Ｂｙは、オーバーレイノード１００−Ａに再接続し、オーバーレイノード１００−Ｂの代わりにオーバーレイノード１００−Ａを新たなエッジノードとする。すなわち、エンドノード２００−Ｂｙのエッジノード（接続先）が、基点ノードから遠いオーバーレイノード１００−Ｂから、基点ノードにより近いオーバーレイノード１００−Ａに変更される。
【００９０】
１−３−２．キャパシティ通知メッセージ送信時の動作
図１１を参照して、オーバーレイノード１００−Ｂがキャパシティ通知メッセージＣＭＳＧ−ＤＮを送信する場合を説明する。オーバーレイノード１００−Ｂのキャパシティ管理部１６０は、自ノードのキャパシティを取得する。キャパシティを取得するタイミングとしては、（１）前回のキャパシティ取得から一定時間が経過したとき、（２）図１０で示された再接続処理が完了したとき、などが考えられる。
【００９１】
更に、キャパシティ管理部１６０は、マルチキャストルーティングテーブルＲＴＮを参照して、２つの次ホップノード１００−Ｃ、１００−Ｅが存在することを認識する。この場合、キャパシティ管理部１６０は、上記取得したキャパシティを、それら２つの次ホップノード１００−Ｃ、１００−Ｅ間で分割する。
【００９２】
キャパシティ管理部１６０は、２種類のキャパシティ通知メッセージＣＭＳＧ−ＤＮ−Ｃ、ＣＭＳＧ−ＤＮ−Ｅを作成する。キャパシティ通知メッセージＣＭＳＧ−ＤＮ−Ｃは、次ホップノード１００−Ｃに割り当てられたキャパシティと、オーバーレイノード１００−Ｂのアドレスを示す。一方、キャパシティ通知メッセージＣＭＳＧ−ＤＮ−Ｅは、次ホップノード１００−Ｅに割り当てられたキャパシティと、オーバーレイノード１００−Ｂのアドレスを示す。そして、キャパシティ管理部１６０は、マルチキャストルーティングテーブルＲＴＮを参照して、キャパシティ通知メッセージＣＭＳＧ−ＤＮ−Ｃ、ＣＭＳＧ−ＤＮ−Ｅをそれぞれオーバーレイノード１００−Ｃ、１００−Ｅへ送信する。
【００９３】
オーバーレイノード１００−Ｃは、再接続指示メッセージＲＭＳＧをエンドノード２００−Ｃｘに送信し、エンドノード２００−Ｃｘは再接続要求ＲＲＥＱをオーバーレイノード１００−Ｂに送信する。オーバーレイノード１００−Ｂは、エンドノード２００−Ｃｘからの再接続要求ＲＲＥＱを受け入れる。エンドノード２００−Ｃｘは、参加要求をオーバーレイノード１００−Ｂに送信する。オーバーレイノード１００−Ｂの参加要求転送部１３０は、マルチキャストルーティングテーブルＲＴＮを更新し（エンドノード２００−Ｃｘをエントリに新たに追加する）、また、参加要求をオーバーレイノード１００−Ａに転送する。その後、オーバーレイノード１００−Ｂが当該マルチキャストグループ宛のマルチキャストトラヒックを受信すると、そのトラヒック転送部１４０は、マルチキャストトラヒックを少なくともエンドノード２００−Ｃｘに転送する。
【００９４】
オーバーレイノード１００−Ｅは、再接続指示メッセージＲＭＳＧをエンドノード２００−Ｅｘに送信し、エンドノード２００−Ｅｘは再接続要求ＲＲＥＱをオーバーレイノード１００−Ｂに送信する。このとき、オーバーレイノード１００−Ｂは、キャパシティ不足により、エンドノード２００−Ｅｘからの再接続要求ＲＲＥＱを拒否するとする。この場合、エンドノード２００−Ｅｘの再接続は行われない。
【００９５】
１−４．効果
以上に説明されたように、本実施の形態によれば、エンドノード２００のエッジノードが、基点ノードにより近いオーバーレイノード１００に変更される。その結果、オーバーレイネットワーク上でのエンドノード間のホップ数が減少する。従って、オーバーレイマルチキャストおいて、エンドノード間のマルチキャストトラヒックの転送遅延が短縮される。
【００９６】
また、本実施の形態では、上流ノード１００の追加接続許容台数ＮＡの範囲内で、再接続指示対象のローカルエンドノード２００が選択される。もし、上流ノード１００に多数の新規エンドノードがむやみに接続されたとすると、その上流ノード１００にかかる負荷が極端に増大し、転送遅延がかえって悪化するという問題が発生し得る。本実施の形態によれば、そのような問題は発生しない。
【００９７】
更に、本実施の形態では、エンドノード２００の接続先（エッジノード）が変更されるのみである。オーバーレイネットワークやマルチキャストツリーのトポロジーを変更する必要は一切無い。つまり、トポロジーを変更することなく、マルチキャストトラヒックの転送遅延を短縮することが可能である。トポロジー変更に伴うオーバーレイネットワークのルーティングテーブル及びマルチキャストルーティングテーブルの再構築は不要である。
【００９８】
２．第２の実施の形態
第１の実施の形態では、上流から受け取るキャパシティ通知メッセージＣＭＳＧ−ＵＰに、隣接する前ホップノードのキャパシティのみが記載されていた。そのため、ローカルエンドノード２００の再接続先候補は、前ホップノードだけであった。この場合、２ホップ以上上流側のオーバーレイノード１００へローカルエンドノード２００を再接続させるためには、再接続処理をホップ数分繰り返す必要があった。
【００９９】
第２の実施の形態では、下流へ送られるキャパシティ通知メッセージＣＭＳＧ−ＤＮに、自ノードのキャパシティだけでなく、自ノードよりも上流のオーバーレイノード１００のキャパシティも記載される。その結果、ローカルエンドノード２００の再接続先候補が、前ホップノードだけでなく、前ホップノードよりも更に上流側のオーバーレイノード１００にも拡張されることになる。この場合、ローカルエンドノード２００を、基点ノードにより近いオーバーレイノード１００に再接続させやすくなる。また、そのために再接続処理を繰り返す必要がなくなるため、処理時間が短縮される。
【０１００】
図１２は、第２の実施の形態に係るオーバーレイノード１００の構成を示すブロック図である。第１の実施の形態と比較して、本実施の形態に係る再接続管理部１７０は、更に上流キャパシティ再算出部１７３を備えている。第１の実施の形態と重複する説明は適宜省略される。
【０１０１】
（上流キャパシティ再算出部１７３）
第１の実施の形態と同様に、再接続管理部１７０（エンドノード選択部１７１、指示部１７２）は、上流から受け取るキャパシティ通知メッセージＣＭＳＧ−ＵＰに応答して、再接続指示処理を実行する。再接続指示処理の後、上流ノードのキャパシティにまだ余裕がある可能性もある。そこで、上流キャパシティ再算出部１７３は、再接続指示処理の後の上流ノードのキャパシティを再度算出する。
【０１０２】
キャパシティ通知メッセージＣＭＳＧ−ＵＰで示される上流ノードのキャパシティ（通知キャパシティ）をＣｕｐとする。また、エンドノード選択部１７１によって選択されたローカルエンドノード２００のキャパシティ消費量の合計をＣｃとする。このとき、上流キャパシティ再算出部１７３は、残留キャパシティＣｕｐ’＝Ｃｕｐ−Ｃｃを算出する。そして、キャパシティ再算出部１７３は、その残留キャパシティＣｕｐ’と上流ノードアドレス（キャパシティ通知メッセージＣＭＳＧ−ＵＰで示されるアドレス）を示す残留キャパシティ通知メッセージＣＭＳＧ−ＵＰ’を、キャパシティ管理部１６０に送る。
【０１０３】
例えば、図１０で示された例において、オーバーレイノード１００−Ｂが受け取るキャパシティ通知メッセージＣＭＳＧ−ＵＰは、「オーバーレイノード１００−Ａの送出トラヒック残余量＝６０Ｍｂｐｓ」を示している。ここで、再接続管理部１７０が、ローカルエンドノード２００−Ｂｙ（受信トラヒック量＝３０Ｍｂｐｓ）に対して、オーバーレイノード１００−Ａへの再接続を指示するとする。この場合、上流キャパシティ再算出部１７３は、残留キャパシティＣｕｐ’を３０Ｍｂｐｓと算出し、「オーバーレイノード１００−Ａの送出トラヒック残余量＝３０Ｍｂｐｓ」を示す残留キャパシティ通知メッセージＣＭＳＧ−ＵＰ’を、キャパシティ管理部１６０に送る。
【０１０４】
（キャパシティ管理部１６０）
キャパシティ管理部１６０は、残留キャパシティ通知メッセージＣＭＳＧ−ＵＰ’をキャパシティ通知メッセージＣＭＳＧ−ＤＮに組み込む。すなわち、下流へ送られるキャパシティ通知メッセージＣＭＳＧ−ＤＮは、自ノードのキャパシティ及びアドレスに加えて、上流ノードの残留キャパシティ及び上流ノードアドレスをも含む。尚、キャパシティ按分部１６２は、第１の実施の形態と同様に、自ノード及び上流ノードのキャパシティを分割してもよい。
【０１０５】
（再接続管理部１７０）
再接続管理部１７０は、上流からキャパシティ通知メッセージＣＭＳＧ−ＵＰを受け取る。そのキャパシティ通知メッセージＣＭＳＧ−ＵＰは、複数の上流ノードのそれぞれのキャパシティ及びアドレスを示している可能性がある。すなわち、ローカルエンドノード２００にとって複数の再接続先候補が存在する可能性がある。その場合、エンドノード選択部１７１は、ローカルエンドノード２００を再接続させる候補をも選択する。
【０１０６】
例として、オーバーレイノード１００−Ａの送出トラヒック残余量が６０Ｍｂｐｓであり、オーバーレイノード１００−Ａよりも上流のオーバーレイノード１００−Ｘの送出トラヒック残余量が３０Ｍｂｐｓである場合を考える。この場合に、再接続管理部１７０は例えば、ローカルエンドノード２００−Ｂｙ（受信トラヒック量＝３０Ｍｂｐｓ）に対してオーバーレイノード１００−Ｘへの再接続を指示し、ローカルエンドノード２００−Ｂｚ（受信トラヒック量＝３０Ｍｂｐｓ）に対してオーバーレイノード１００−Ａへの再接続を指示する。その後、上流キャパシティ再算出部１７３が、上流ノードのキャパシティを再算出する。
【０１０７】
尚、エンドノード選択部１７１は、再接続先候補をランダムに選択してもよいし、キャパシティの多いものから優先的に選択してもよい。あるいは、エンドノード選択部１７１は、基点ノードにより近い再接続先候補を選択してもよい。これは、各オーバーレイノード１００が、キャパシティ通知メッセージＣＭＳＧ−ＤＮに、自ノードの基点ノードからのホップ数を記載しておくことで実現することができる。基点ノードからのホップ数は、例えば次のようにして把握することができる。基点ノードは、マルチキャストツリーにデータを送信する際、当該データに転送回数記録用のフィールドを設けておく。各オーバーレイノード１００は、データ転送時に当該フィールドの値を１増加させる。各オーバーレイノード１００は、受け取ったデータの当該フィールドを参照することによって、基点ノードからのホップ数を把握することができる。
【０１０８】
本実施の形態によれば、第１の実施の形態と同じ効果が得られる。更に、エンドノード２００を基点ノードにより近いオーバーレイノード１００に再接続させやすくなる。また、エンドノード２００を基点ノードにより近いオーバーレイノード１００に再接続させるために要する処理時間が短縮される。
【０１０９】
３．第３の実施の形態
既出の図１１で示された例において、オーバーレイノード１００−Ｂは、マルチキャストツリーの分岐点に位置し、２つの次ホップノード１００−Ｃ、１００−Ｅを有していた。この場合、オーバーレイノード１００−Ｂは、キャパシティを２つの次ホップノード１００−Ｃ、１００−Ｅで分割し、２つのキャパシティ通知メッセージＣＭＳＧ−ＤＮ−Ｃ、ＣＭＳＧ−ＤＮ−Ｅを作成する。ここで、キャパシティの分割比率は任意であってもよいが、もしオーバーレイノード１００−Ｂがそれぞれの分岐先のエンドノード２００の状態を認識していれば、それぞれの分岐先に対してより適切な量のキャパシティを分配することが可能となる。そこで、第３の実施の形態では、次ホップ以遠のエンドノード２００の状態（台数やリソース使用量）を考慮にいれて、キャパシティの分割が実施される。
【０１１０】
図１３は、第３の実施の形態に係るオーバーレイノード１００の構成を示すブロック図である。第１の実施の形態と比較して、本実施の形態に係るエンドノード管理部１５０は、更に通知メッセージ処理部１５２を備えている。第１の実施の形態と重複する説明は適宜省略される。
【０１１１】
（通知メッセージ処理部１５２）
上述の通り、ローカルエンドノード監視部１５１は、自ノードにつながるローカルエンドノード２００の状態を監視し、そのローカルエンドノード２００の状態をエンドノード管理情報ＥＮＤに記載する。ローカルエンドノード２００の状態は、ローカルエンドノード２００の台数やキャパシティ消費量（送出／受信トラヒック量など）を含む。
【０１１２】
通知メッセージ処理部１５２は、エンドノード管理情報ＥＮＤに記載された情報を示す「エンドノード状態通知メッセージＥＭＳＧ」を作成する。そして、通知メッセージ処理部１５２は、エンドノード状態通知メッセージＥＭＳＧを、前ホップノードへ送信する。あるオーバーレイノード１００から上流に向けて送信されるエンドノード状態通知メッセージＥＭＳＧは、「エンドノード状態通知メッセージＥＭＳＧ−ＵＰ」と参照される場合がある。
【０１１３】
また、通知メッセージ処理部１５２は、次ホップノードから送られてきたエンドノード状態通知メッセージＥＭＳＧを受け取る。下流側から受け取るエンドノード状態通知メッセージＥＭＳＧは、「エンドノード状態通知メッセージＥＭＳＧ−ＤＮ」と参照される場合がある。エンドノード状態通知メッセージＥＭＳＧ−ＤＮを受け取ると、通知メッセージ処理部１５２は、そのエンドノード状態通知メッセージＥＭＳＧ−ＤＮに含まれる情報をエンドノード管理情報ＥＮＤに追記する。その結果、エンドノード管理情報ＥＮＤには、自ノードにつながるローカルエンドノードだけでなく、下流ノードにつながるエンドノード（リモートエンドノード）の状態も記載されることになる。尚、このようなエンドノード管理情報ＥＮＤの更新は、分岐点に位置するオーバーレイノード１００だけで行われてもよい。
【０１１４】
その後、通知メッセージ処理部１５２は、エンドノード状態通知メッセージＥＭＳＧを更新して、それを更に上流の前ホップノードへ送信する。すなわち、次ホップノードからエンドノード状態通知メッセージＥＭＳＧ−ＤＮを受け取ると、通知メッセージ処理部１５２は、それに自身のローカルエンドノード２００の状態を追加した後、エンドノード状態通知メッセージＥＭＳＧ−ＵＰとして前ホップノードへ更に転送する。このようにして、エンドノード２００の状態が累積的に上流方向に通知される。
【０１１５】
次に、図１４及び図１５を参照して、本実施の形態に係る処理の一例を説明する。
【０１１６】
図１４には、あるマルチキャストグループのマルチキャストツリーの一部が示されている。オーバーレイノード１００−Ａは、オーバーレイノード１００−Ｂの前ホップノードである。オーバーレイノード１００−Ｃ、１００−Ｅは共に、オーバーレイノード１００−Ｂの次ホップノードである。オーバーレイノード１００−Ｄは、オーバーレイノード１００−Ｃの次ホップノードである。エンドノード２００−Ａ１は、オーバーレイノード１００−Ａのローカルエンドノードである。エンドノード２００−Ｂ１、２００−Ｂ２は、オーバーレイノード１００−Ｂのローカルエンドノードである。エンドノード２００−Ｃ１、２００−Ｃ２、２００−Ｃ３は、オーバーレイノード１００−Ｃのローカルエンドノードである。エンドノード２００−Ｄ１、２００−Ｄ２は、オーバーレイノード１００−Ｄのローカルエンドノードである。エンドノード２００−Ｅ１は、オーバーレイノード１００−Ｅのローカルエンドノードである。図１５には、各エンドノード２００への送出トラヒック量、及び各エンドノード２００からの受信トラヒック量が示されている。
【０１１７】
例えば、図１４中のオーバーレイノード１００−Ｃが作成するエンドノード状態通知メッセージＥＭＳＧ−ＵＰには、次のような情報が記載される。
【０１１８】
＜例１＞オーバーレイノード毎に状態を記載
［オーバーレイノード１００−Ｃ］
（Ａ）エンドノードの台数
送信エンドノード＝２台、受信エンドノード＝１台
（Ｂ）各エンドノードへの送出トラヒック量、各エンドノードからの受信トラヒック量
２００−Ｃ１：送出＝１０Ｍｂｐｓ、受信＝  ０Ｍｂｐｓ
２００−Ｃ２：送出＝  ０Ｍｂｐｓ、受信＝１５Ｍｂｐｓ
２００−Ｃ３：送出＝  ０Ｍｂｐｓ、受信＝２０Ｍｂｐｓ
（Ｃ）合計トラヒック量（送出、受信）
合計送出トラヒック量＝１０Ｍｂｐｓ
合計受信トラヒック量＝３５Ｍｂｐｓ
［オーバーレイノード１００−Ｄ］
（Ａ）エンドノードの台数
送信エンドノード＝１台、受信エンドノード＝１台
（Ｂ）各エンドノードへの送出トラヒック量、各エンドノードからの受信トラヒック量
２００−Ｄ１：送出＝１５Ｍｂｐｓ、受信＝  ０Ｍｂｐｓ
２００−Ｄ２：送出＝  ０Ｍｂｐｓ、受信＝１０Ｍｂｐｓ
（Ｃ）合計トラヒック量（送出、受信）
合計送出トラヒック量＝１５Ｍｂｐｓ
合計受信トラヒック量＝１０Ｍｂｐｓ
【０１１９】
＜例２＞合算して記載
（Ａ）エンドノードの台数
送信エンドノード＝３台、受信エンドノード＝２台
（Ｃ）合計トラヒック量（送出、受信）
合計送出トラヒック量＝２５Ｍｂｐｓ
合計受信トラヒック量＝４５Ｍｂｐｓ
【０１２０】
また、図１４中のオーバーレイノード１００−Ｅが作成するエンドノード状態通知メッセージＥＭＳＧ−ＵＰには、次のような情報が記載される。
［オーバーレイノード１００−Ｅ］
（Ａ）エンドノードの台数
送信エンドノード＝１台、受信エンドノード＝１台
（Ｂ）各エンドノードへの送出トラヒック量、各エンドノードからの受信トラヒック量
２００−Ｅ１：送出＝１０Ｍｂｐｓ、受信＝１０Ｍｂｐｓ
（Ｃ）合計トラヒック量（送出、受信）
合計送出トラヒック量＝１０Ｍｂｐｓ
合計受信トラヒック量＝１０Ｍｂｐｓ
【０１２１】
オーバーレイノード１００−Ｂは、２つの次ホップノード１００−Ｃ、１００−Ｅのそれぞれから、上述のようなエンドノード状態通知メッセージＥＭＳＧ−ＤＮを受け取る。そして、オーバーレイノード１００−Ｂのエンドノード管理部１５０は、受け取ったエンドノード状態通知メッセージＥＭＳＧ−ＤＮを参照して、次ホップノード以遠のキャパシティ消費量の合計を算出する。次ホップノード以遠のキャパシティ消費量の合計は、以下「後続キャパシティ消費量」と参照される。エンドノード管理部１５０は、次ホップノード毎に後続キャパシティ消費量を算出し、算出結果をエンドノード管理情報ＥＮＤに記録する。本例の場合、次ホップノード１００−Ｃ、１００−Ｅのそれぞれに関する後続キャパシティ消費量は次の通りである。
【０１２２】
［次ホップノード１００−Ｃ］
後続キャパシティ消費量：送出＝２５Ｍｂｐｓ、受信＝４５Ｍｂｐｓ
［次ホップノード１００−Ｅ］
後続キャパシティ消費量：送出＝１０Ｍｂｐｓ、受信＝１０Ｍｂｐｓ
【０１２３】
この場合において、オーバーレイノード１００−Ｂにおけるキャパシティ通知メッセージＣＭＳＧ−ＤＮの作成は、次の通りである。オーバーレイノード１００−Ｂのキャパシティ管理部１６０（キャパシティ按分部１６２）は、２つの次ホップノード１００−Ｃ、１００−Ｅの間でキャパシティを分割する。このとき、キャパシティ管理部１６０は、エンドノード管理情報ＥＮＤを参照し、それぞれの次ホップノードに関する後続キャパシティ消費量に基づいてキャパシティを分割する。例えば、キャパシティ管理部１６０は、それぞれの後続キャパシティ消費量の比率を、キャパシティの分割比率とする。これにより、後続キャパシティ消費量に応じた適切な量のキャパシティが、各々の次ホップノードに割り当てられることになる。
【０１２４】
あるいは、ある次ホップノードに後続キャパシティ消費量を上回る過剰なキャパシティが割り当てられる一方、他の次ホップノードに後続キャパシティ消費量を下回るキャパシティしか割り当てられないといった不均衡がなくなるようなキャパシティ分割も可能である。典型的には、全ての次ホップノードの後続キャパシティ消費量の合計が、割り当て可能なキャパシティを上回っている場合に、そのような不均衡が発生し得る。その場合、キャパシティ管理部１６０は、キャパシティの分割量（割当量）が後続キャパシティ消費量を上回るような次ホップノードが無くなるように、キャパシティの分割を行う。これは、不必要に大きなキャパシティの割り当てを排除し、無駄をできるだけ削ることに相当する。その結果、上述のような不均衡が改善される。
【０１２５】
例えば、図１４及び図１５で示された例において、オーバーレイノード１００−Ｂの送出トラヒック残余量が３０Ｍｂｐｓである場合を考える。上述の通り、次ホップノード１００−Ｃに関する後続キャパシティ消費量（送出）は２５Ｍｂｐｓであり、次ホップノード１００−Ｅに関する後続キャパシティ消費量（送出）は１０Ｍｂｐｓである。従って、次ホップノード１００−Ｃ側には２５Ｍｂｐｓ以下のキャパシティが割り当てられ、且つ、次ホップノード１００−Ｅ側には１０Ｍｂｐｓ以下のキャパシティが割り当てられる。
【０１２６】
比較として、送出トラヒック残余量の３０Ｍｂｐｓが、次ホップノード１００−Ｃ、１００−Ｅで折半される場合を考える。この場合、次ホップノード１００−Ｃには後続キャパシティ消費量（＝２５Ｍｂｐｓ）を下回るキャパシティしか割り当てられないが、次ホップノード１００−Ｅには後続キャパシティ消費量（＝１０Ｍｂｐｓ）を上回る余剰なキャパシティが割り当てられる。これは、非効率的である。本実施の形態では、このような非効率が回避される。
【０１２７】
本実施の形態によれば、第１の実施の形態と同じ効果が得られる。更に、マルチキャストツリーの分岐点において、それぞれの分岐先に対してより適切な量のキャパシティを分配することが可能となる。非効率的なキャパシティ分配が防止されるため、エンドノードの再接続がより促進され、好適である。また、本実施の形態と第２の実施の形態とを組み合わせることも可能である。その場合、第２の実施の形態と同じ効果も得られる。
【０１２８】
４．第４の実施の形態
第４の実施の形態では、各エンドノード２００に対して「優先度」が与えられる。そして、優先度の高いエンドノード２００から優先的に再接続処理が実施される。
【０１２９】
図１６は、第４の実施の形態に係るオーバーレイノード１００の構成を示すブロック図である。第１の実施の形態と比較して、エンドノード管理部１５０は更に通知メッセージ処理部１５２を備え、再接続管理部１７０は更に上流キャパシティ再算出部１７３を備えている。既出の実施の形態と重複する説明は適宜省略される。
【０１３０】
上流キャパシティ再算出部１７３は、第２の実施の形態で説明されたものと同じである。つまり、上流キャパシティ再算出部１７３は、再接続指示処理の後の上流ノードの残留キャパシティを算出し、残留キャパシティ通知メッセージＣＭＳＧ−ＵＰ’をキャパシティ管理部１６０に送る。
【０１３１】
通知メッセージ処理部１５２は、第３の実施の形態で説明されたものと同様であり、エンドノード状態通知メッセージＥＭＳＧの処理を行う。但し、本実施の形態では、エンドノード状態通知メッセージＥＭＳＧは、エンドノード２００の台数やキャパシティ消費量（送出／受信トラヒック量など）に加えて、エンドノード２００の「優先度」も含んでいる。また、通知メッセージ処理部１５２は、エンドノード状態通知メッセージＥＭＳＧ−ＤＮを参照して、優先度毎に後続キャパシティ消費量を算出し、算出結果をエンドノード管理情報ＥＮＤに記録する。
【０１３２】
次に、図１７〜図１９を参照して、本実施の形態に係る処理の一例を説明する。
【０１３３】
図１７には、あるマルチキャストグループのマルチキャストツリーの一部が示されている。図１７において、オーバーレイノード１００−Ａ、１００−Ｂ、１００−Ｃ、１００−Ｄ、１００−Ｅが上流から下流に向かって順番につながっている。エンドノード２００−Ｃ１、２００−Ｃ２、２００−Ｃ３は、オーバーレイノード１００−Ｃのローカルエンドノードである。エンドノード２００−Ｄ１、２００−Ｄ２、２００−Ｄ３は、オーバーレイノード１００−Ｄのローカルエンドノードである。エンドノード２００−Ｅ１、２００−Ｅ２、２００−Ｅ３は、オーバーレイノード１００−Ｅのローカルエンドノードである。
【０１３４】
図１８には、各エンドノード２００への送出トラヒック量、及び各エンドノード２００の優先度が示されている。図１８に示されるように、各エンドノード２００には、三段階の優先度“１”〜“３”のうちいずれかが割り当てられている。ここで、優先度“１”が最も高く、優先度“３”が最も低い。
【０１３５】
図１９は、オーバーレイノード１００−Ｃのエンドノード管理情報ＥＮＤが示す後続キャパシティ消費量を示している。オーバーレイノード１００−Ｃにおける後続キャパシティ消費量は、下流側のオーバーレイノード１００−Ｄ、１００−Ｅに接続された全エンドノード２００のキャパシティ消費量の合計である。図１９に示されるように、オーバーレイノード１００−Ｃの通知メッセージ処理部１５２は、優先度毎に後続キャパシティ消費量を算出している。
【０１３６】
再接続指示処理は、「優先度」の順番で行われる。以下、オーバーレイノード１００−Ｃの再接続管理部１７０がキャパシティ通知メッセージＣＭＳＧ−ＵＰを受け取った際の再接続指示処理を説明する。
【０１３７】
オーバーレイノード１００−Ｃが受け取るキャパシティ通知メッセージＣＭＳＧ−ＵＰが、「オーバーレイノード１００−Ａの送出トラヒック残余量＝３０Ｍｂｐｓ、オーバーレイノード１００−Ｂの送出トラヒック残余量＝５０Ｍｂｐｓ」を示しているとする。キャパシティ通知メッセージＣＭＳＧ−ＵＰを受け取ると、再接続管理部１７０は、それぞれの送出トラヒック残余量（キャパシティ）を、一時キャパシティＴＣ−Ａ、ＴＣ−Ｂに代入する。その結果、ＴＣ−Ａ＝３０Ｍｂｐｓ、ＴＣ−Ｂ＝５０Ｍｂｐｓとなる。
【０１３８】
＜優先度＝１＞
まず、最高優先度“１”に関して再接続指示処理が実施される。再接続管理部１７０は、エンドノード管理情報ＥＮＤを参照して、優先度“１”のローカルエンドノード２００−Ｃ１のキャパシティ消費量（＝２０Ｍｂｐｓ）と後続キャパシティ消費量（＝１５Ｍｂｐｓ）の合算値を算出する。そして、再接続管理部１７０は、一時キャパシティから当該合算値を差し引く。これは、優先度“１”のエンドノード２００に関して、ローカルエンドノード２００−Ｃ１だけでなく、次ホップノード以遠に位置するリモートエンドノード２００−Ｄ１、２００−Ｅ１に割り当てられるキャパシティを予め確保しておくことに相当する。
【０１３９】
複数の一時キャパシティが用意されている場合は、自ノードからより遠いオーバーレイノード１００（すなわち、より基点ノードに近いオーバーレイノード１００）の一時キャパシティから優先的に当該合算値を差し引くことが好適である。本例では、オーバーレイノード１００−Ａがより上流側に位置するので、一時キャパシティＴＣ−Ａ（＝３０Ｍｂｐｓ）から当該合算値（＝３５Ｍｂｐｓ）が差し引かれる。ここで、一時キャパシティＴＣ−Ａが５Ｍｂｐｓ不足しているため、その分は次の一時キャパシティＴＣ−Ｂ（＝５０Ｍｂｐｓ）から差し引かれる。その結果、ＴＣ−Ａ＝−５Ｍｂｐｓ、ＴＣ−Ｂ＝４５Ｍｂｐｓとなる。
【０１４０】
その後、再接続管理部１７０は、既出の実施の形態と同様の手法で、優先度“１”に関する再接続指示処理を実行する。すなわち、再接続管理部１７０は、優先度“１”のローカルエンドノード２００−Ｃ１を選択し、当該ローカルエンドノード２００−Ｃ１に対して上流への再接続を指示する。再接続先は、一時キャパシティから除算が行われたオーバーレイノード１００−Ａである。
【０１４１】
＜優先度＝２＞
優先度が１段階落とされ、“２”に設定される。再接続管理部１７０は、エンドノード管理情報ＥＮＤを参照して、優先度“２”のローカルエンドノード２００−Ｃ２のキャパシティ消費量（＝１０Ｍｂｐｓ）と後続キャパシティ消費量（＝１５Ｍｂｐｓ）の合算値を算出する。一時キャパシティＴＣ−Ａは既に使い尽くされているため、再接続管理部１７０は、一時キャパシティＴＣ−Ｂから当該合算値（＝２５Ｍｂｐｓ）を差し引く。その結果、ＴＣ−Ａ＝−５Ｍｂｐｓ、ＴＣ−Ｂ＝２０Ｍｂｐｓとなる。その後、再接続管理部１７０は、優先度“２”のローカルエンドノード２００−Ｃ２を選択し、当該ローカルエンドノード２００−Ｃ２に対してオーバーレイノード１００−Ｂへの再接続を指示する。
【０１４２】
＜優先度＝３＞
優先度が１段階落とされ、“３”に設定される。再接続管理部１７０は、エンドノード管理情報ＥＮＤを参照して、優先度“３”のローカルエンドノード２００−Ｃ３のキャパシティ消費量（＝１０Ｍｂｐｓ）と後続キャパシティ消費量（＝１５Ｍｂｐｓ）の合算値を算出する。再接続管理部１７０は、一時キャパシティＴＣ−Ｂから当該合算値（＝２５Ｍｂｐｓ）を差し引く。その結果、ＴＣ−Ａ＝−５Ｍｂｐｓ、ＴＣ−Ｂ＝−５Ｍｂｐｓとなる。その後、再接続管理部１７０は、優先度“３”のローカルエンドノード２００−Ｃ３を選択し、当該ローカルエンドノード２００−Ｃ３に対してオーバーレイノード１００−Ｂへの再接続を指示する。
【０１４３】
このようにして、優先度“１”のローカルエンドノード２００−Ｃ１はオーバーレイノード１００−Ａに再接続され、優先度“２”、“３”のローカルエンドノード２００−Ｃ２、Ｃ３はオーバーレイノード１００−Ｂに再接続される。すなわち、優先度の高いエンドノード２００が、より基点ノードに近いオーバーレイノード１００に再接続されることになる。
【０１４４】
再接続指示処理の後、上流キャパシティ再算出部１７３は、上流ノードの残留キャパシティを算出する。本例では、オーバーレイノード１００−Ａの残留キャパシティは、１０Ｍｂｐｓ（＝３０Ｍｂｐｓ−２０Ｍｂｐｓ）であり、オーバーレイノード１００−Ｂの残留キャパシティは、３０Ｍｂｐｓ（＝５０Ｍｂｐｓ−１０Ｍｂｐｓ−１０Ｍｂｐｓ）である。このように、オーバーレイノード１００−Ａのキャパシティは未だ残っている。よって、オーバーレイノード１００−Ａのキャパシティを、次ホップノード１００−Ｄにおける再接続指示処理で使用することが可能である。上流キャパシティ再算出部１７３は、それら残留キャパシティを示す残留キャパシティ通知メッセージＣＭＳＧ−ＵＰ’をキャパシティ管理部１６０に送り、キャパシティ管理部１６０は、キャパシティ通知メッセージＣＭＳＧ−ＤＮを次ホップノード１００−Ｄへ送信する。
【０１４５】
オーバーレイノード１００−Ｄでの再接続指示処理の結果、優先度“１”のローカルエンドノード２００−Ｄ１（１０Ｍｂｐｓ）は、未だ余裕のあるオーバーレイノード１００−Ａに再接続されることになる。これは、先行処理において、優先度の高いエンドノード２００−Ｄ１に割り当てられるキャパシティが予め確保されたからである。このように、本実施の形態によれば、優先度の高いエンドノード２００を優先的に上流側に再接続させることが可能である。
【０１４６】
本実施の形態によれば、既出の実施の形態と同じ効果が得られる。更に、各エンドノード２００に優先度を割り当てることによって、所望のエンドノード２００を優先的に上流側に再接続させることが可能となる。
【０１４７】
以上、本発明の実施の形態が添付の図面を参照することにより説明された。但し、本発明は、上述の実施の形態に限定されず、要旨を逸脱しない範囲で当業者により適宜変更され得る。
【符号の説明】
【０１４８】
１００    オーバーレイノード
１００−ＳＥ  送信者エッジノード
１００−ＲＰ  ランデブーノード
１１０    記憶部
１２０    通信部
１３０    参加要求転送部
１４０    トラヒック転送部
１５０    エンドノード管理部
１５１    ローカルエンドノード監視部
１５２    通知メッセージ処理部
１６０    キャパシティ管理部
１６１    キャパシティ算出部
１６２    キャパシティ按分部
１６３    通知メッセージ生成部
１７０    再接続管理部
１７１    エンドノード選択部
１７２    指示部
１７３    上流キャパシティ再算出部
２００    エンドノード
２００−Ｓ    送信者エンドノード
２１０    参加要求送信部
２２０    トラヒック送受信部
２３０    再接続処理部
ＲＴＮ    マルチキャストルーティングテーブル
ＴＦＣ    トラヒック情報
ＥＮＤ    エンドノード管理情報
ＣＭＳＧ    キャパシティ通知メッセージ
ＲＭＳＧ    再接続指示メッセージ
ＲＲＥＱ    再接続要求
ＥＭＳＧ    エンドノード状態通知メッセージ
【図１】
2010278777.tif 000003
【図２】
2010278777.tif 000004
【図３】
2010278777.tif 000005
【図４】
2010278777.tif 000006
【図５】
2010278777.tif 000007
【図６】
2010278777.tif 000008
【図７】
2010278777.tif 000009
【図８】
2010278777.tif 000010
【図９】
2010278777.tif 000011
【図１０】
2010278777.tif 000012
【図１１】
2010278777.tif 000013
【図１２】
2010278777.tif 000014
【図１３】
2010278777.tif 000015
【図１４】
2010278777.tif 000016
【図１５】
2010278777.tif 000017
【図１６】
2010278777.tif 000018
【図１７】
2010278777.tif 000019
【図１８】
2010278777.tif 000020
【図１９】
2010278777.tif 000021