(57)【特許請求の範囲】
【請求項１】
出口ノードとある入口ノードとの複数の組み合わせの各々について対応する配信ツリーが生成されるように、複数の可能なマルチキャスト配信ツリーを初期化段階において生成するステップと、
あるセッションへの出口ノードの参加または離脱に応じて、前記初期化段階において生成された配信ツリーのうちの選択された別の配信ツリーへ配信ツリーを切替えるステップと
を含み、
前記初期化段階は、さらに、
不分岐のマルチキャスト集約ツリーを生成するステップと、
２つ以上の出口ノードをカバーする分岐したマルチキャスト集約ツリーを計算して生成するステップであって、分岐したツリーは、入口ルータと利用可能な出口ルータとを考慮して全ての前記不分岐のマルチキャスト集約ツリーを組み合わせることにより計算されるものである、ステップと、
分岐したマルチキャスト集約ツリーの各々へマルチキャストチャネルを割り当てるステップと
を含み、
前記不分岐のマルチキャスト集約ツリーを生成するステップは、
マルチキャストチャネルを配信経路へ割り当てた後に、該配信経路に沿ってＴＲＥＥメッセージを送信するステップであって、各コアノードは前ノードのＩＰアドレスをＭＲＩＢに追加するとともに前記メッセージをダウンストリームに伝搬させるものである、ステップと、
前記ＴＲＥＥメッセージを受信した後に、出口ノードが前ルータのＩＰアドレスを用いて前記ＭＲＩＢを更新し、マルチキャストツリーを生成するためにマルチキャストルーティングプロトコルをトリガするステップと
を含む、ネットワークにおけるマルチキャストツリー割当方法。
【請求項２】
前記マルチキャストツリーは、複数のマルチキャストグループが１つの配信ツリーを共有しているマルチキャスト集約ツリーを含むものである、請求項１に記載の方法。
【請求項３】
前記の配信ツリーを生成するステップは配信経路のフィルタリングを行うステップを更に含むものであり、
前記のフィルタリングを行うステップは、最善経路の選択または効率の悪い経路の破棄を含むものである、請求項１又は２に記載の方法。
【請求項４】
前記のフィルタリングを行うステップは、入口ルータがフォワーディングノード内にある経路を破棄するステップ、および／または、分岐点が入口ルータにある経路を破棄するステップを含むものである、請求項３に記載の方法。
【請求項５】
全ての可能な配信ツリーを前記初期化段階において生成するステップであって、これにより、あるセッションが、入口ノードまたは発信元ノードから１つ以上の出口ノードへのある配信経路を要求する場合には、対応する配信経路が前記初期化段階において既に生成されているものとなる、ステップを含む請求項１〜４のいずれか一項に記載の方法。
【請求項６】
生成された各配信ツリーは、セッションフローのエンターポイントである入口ルータのアドレスである発信元ＩＰアドレスと、ＩＰマルチキャストアドレスである宛先ＩＰアドレスとから成るマルチキャストタプルにより特定されるものである、請求項５に記載の方法。
【請求項７】
ネットワークにおいて利用可能な配信経路を発見し、不分岐の集約ツリーを生成するステップを更に含む請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記ネットワーク内の入口ノードが、初期化においてＴＲＥＥメッセージを用いて前記ネットワークをフラッディングし、前記ＴＲＥＥメッセージを受信すると、該ＴＲＥＥメッセージを受信したルータが、該メッセージを受信したインタフェース以外の各外部インタフェースに該メッセージを伝搬させるステップであって、ここで、各メッセージは、配信経路リストに含まれ、伝搬に用いられる外部インタフェースのローカルＩＰアドレスを搬送するものである、ステップと、
前記ＴＲＥＥメッセージを受信した後に、出口ノードが、受信したＴＲＥＥメッセージに対応するＲＥＳＰＯＮＳＥメッセージを作成し、該ＴＲＥＥメッセージの発信元である入口ルータへ該ＲＥＳＰＯＮＳＥメッセージを送信するステップであって、該ＲＥＳＰＯＮＳＥメッセージは、ローカル外部インタフェースと当該ＴＲＥＥメッセージの配信経路リストを搬送するものである、ステップと
を更に含む請求項７に記載の方法。
【請求項９】
ルートに分岐点を有する全てのツリーを破棄するステップと、
マルチキャストツリーを構成するために、全てのツリーへシグナリングメッセージを送信するステップと
を更に含む請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
リソースの浪費を回避すべく、生成された配信ツリーに対して１つ以上のセッションフローを伝搬させるために、セッション接続をコントロールするステップを更に含む請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
全ての可能な配信ツリーを初期化段階において生成するモジュールであって、これにより、あるセッションが、入口ノードまたはソースノードから１つ以上の出口ノードまでのある配信経路を要求する場合には、対応する配信経路が前記初期化段階において既に生成されているものである、モジュール
を備え、
前記初期化段階において、さらに、
不分岐のマルチキャスト集約ツリーを生成するモジュールと、
２つ以上の出口ノードをカバーする分岐したマルチキャスト集約ツリーを計算して生成するモジュールであって、分岐したツリーは、入口ルータと利用可能な出口ルータとを考慮して全ての前記不分岐のマルチキャスト集約ツリーを組み合わせることにより計算されるものである、モジュールと、
分岐したマルチキャスト集約ツリーの各々へマルチキャストチャネルを割り当てるモジュールと
を備え、
前記不分岐のマルチキャスト集約ツリーを生成するモジュールは、
マルチキャストチャネルを配信経路へ割り当てた後に、該配信経路に沿ってＴＲＥＥメッセージを送信するモジュールであって、各コアノードは前ノードのＩＰアドレスをＭＲＩＢに追加するとともに前記メッセージをダウンストリームに伝搬させるものである、モジュールと、
前記ＴＲＥＥメッセージを受信した後に、出口ノードが前ルータのＩＰアドレスを用いて前記ＭＲＩＢを更新し、マルチキャストツリーを生成するためにマルチキャストルーティングプロトコルをトリガするモジュールと
を備える、ネットワークにおけるマルチキャストツリー割当装置。
【請求項１２】
請求項２〜１０のいずれか一項に記載の方法を実行するモジュールを更に備える請求項１１に記載の装置。
【請求項１３】
請求項１〜１０のいずれか一項に記載の方法をコンピュータに実行させることを可能にするコンピュータプログラムコードを含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワークにおけるマルチキャストツリー割当方法に関する。
【背景技術】
【０００２】
次世代ネットワークは、配信経路に沿ってネットワーク内部またはネットワーク間でサポートされる接続制御スキームとは関係なく、セッションコンテンツを複数のユーザへ同時配信することが求められている。マルチユーザセッション（例えば、ＩＰＴＶ、ラジオ放送、ファイル配信およびプッシュメディア）は、アクセス技術が異なるネットワークに属するユーザにとっていつでもどこでも利用可能である。システムのスケーラビリティを損なうことなく、多くの同時マルチユーザセッションを調整し、かつそれらのライフタイム全体にわたって継続性を確保するには、効率の良いネットワークプロビジョンが必要である。この点を考慮して、制御スキームは現在のネットワーク性能を考慮して選択されなければならない。例えば、コンフィギュレーションのためのオンデマンドで機能するper-flowアプローチは、シグナリングおよびステートオーバヘッドを通じてネットワーク性能を悪化させる。
【０００３】
トランスポートの観点からすれば、マルチキャストはグループコミュニケーションにとって最も適した技術である。これにより、数人のユーザは加入したセッションのコンテンツを、パケットを複製することなく同時に取得することができ、それによりネットワーク帯域幅の利用を最適化できるからである。またルーティングの観点からすれば、セッション経路は、発信元から受信側に向けて計算しなければならない。最善のルートはこの方向に計算されるからである。しかしながら、マルチキャストリソースは反対方向（受信側から発信元への方向）に制御される。このため、例えば、ＱｏＳ（Quality of Service）経路がマルチキャスト処理の逆方向に計算されると、ＱｏＳアウェアなマルチキャストツリーの生成が危うくなる。このように、非対称ルートはＱｏＳ経路とは異なる経路におけるマルチキャストツリーの生成に影響を与える可能性がある。マルチキャストの別の欠点はper-flow（per tree）ベースであるということであって、このことはステートストレージの点でシステム性能に悪影響を及ぼす。例えば、パケット転送処理のパフォーマンスはアクティブなマルチキャストツリーの数が増加するにつれ過負荷状態になり、パケット複製のルックアップ作業に過剰な負荷がかかる。それ故、マルチキャストリソースは、システム性能にダメージを与えることなく、全てのセッションフローがメンバユーザに確実に配信されるように、効率的に供給（provision）されなければならない。
【０００４】
動的マルチキャストプロビジョニングは、リソースがオンデマンドかつ自動的に設定（configure）されることから、利用頻度の高いネットワークに対して静的プロビジョニングよりもうまく適合する。例えば、このアプローチはコンスタントな人間の介入を避けて必要なコンフィギュレーションとアップデートを実行する。しかしながら、コンフィギュレーションを必要とするリソースについて経路に沿ってエージェントに通知するためにシグナリングメッセージが必要となることから、ネットワーク性能は帯域幅消費の点で悪影響を受ける。
【０００５】
配信ツリーがフロー毎（per-flow）に割り当てられると、それらはステートストレージ（state strage）（例えばフォワーディングノードに過剰負荷をかけること）の点でシステムのスケーラビリティを低下させないように注意深くオーバプロビジョニングされなければならない。
【０００６】
ステートストレージは、集約（例えば同じセグメントを共有してパケットを配信する場合などに、いくつかの条件に合うセッションを単一の配信ツリーに割り当てる）を実行することによって最適化することができる。この点を考慮して、２つのメインノードが到来フローと集約ツリーとの接続を管理する。ここで、アグリゲータとデアグリゲータは、一般にそれぞれルートノードとリーフノードに配置される。それ故、フォワーディングノードは、per-flow配信ツリーの代わりに集約ツリーに関係するステートを保存するだけである。例えば、パケット転送処理は、マルチキャストアウェアネットワークにおけるパケット複製のルックアップにおけるオプション数を大きく減らすことによって最適化できる。
【０００７】
オーバプロビジョニングを通じてシグナリングおよびステートオーバヘッドを最適化する、研究団体が提案するほとんどのソリューションは、例えば帯域幅の過剰予約（over-reservation）を実行することによるなど、ＱｏＳリソースに集中している。マルチキャストツリーのオーバプロビジョニングをサポートする有効なソリューションは、リンク切れ、ノード故障およびメンバグループ離脱から保護することを目的として、過剰のマルチキャストリソースを生成する。非特許文献１および非特許文献２に記載のソリューションは、リソースの利用可能性を考慮して、リクエスト毎に（つまりper-flow ベースで）プライマリツリーとバックアップツリーを構築する。新しい経路におけるリソースのコンフィギュレーションはバックアップツリーが事前に生成されているので高速であり、さらにセクションの品質が損なわれることはない。しかしながら、これらのアプローチは、per-flowベースでマルチキャストツリーの生成をコントロールするために、システムスケーラビリティを危うくする。それ故、マルチキャストステート量がアクティブフロー数の２倍になると、システムのロバスト性は向上するのに対し、システムスケーラビリティは深刻な影響を受ける。
【０００８】
非特許文献３に記載のソリューションは、DiffServドメインにおけるアプリケーションレイヤマルチキャストを提案するものである。この場合、ステートレスコアルータは追加ヘッダに基づいてデータパケットを転送する。追加ヘッダに含まれる情報は、コアノードのＩＤ、適切な分岐情報、DiffServ-non-capableノードをバイパスするためのトンネリングビット、および異なる受信者による混成ＤＳＣＰ要件に適応するための適応的なDiffServフィールドを搬送する。しかしながら、このソリューションはユニキャスト接続に基づいてセッションパケットを配信しており、従ってＩＰマルチキャストをサポートしていない。
【０００９】
非特許文献４に記載のソリューションは、マルチキャストステートスケーラビリティを改善する新規のスキームを提案している。このスキームでは、複数のマルチキャストグループが１つの配信ツリー（集約ツリーと呼ばれる）を共有することが強いられ、これによりネットワーク内のツリーの数は大きく減少する。その結果、コアルータはグループ毎ではなく集約ツリー毎のステートを保持する必要があるだけなので、フォワーディングステートも減少する。このソリューションは、マルチキャストツリーの完全適合、リーキ（leaky）適合、不完全適合を考慮している。こうして、マルチキャストステートオーバヘッドは削減されるが、リーキ適合と不完全適合のおかげで非グループメンバノードへのマルチキャストデータの配信が可能となり、このアプローチは帯域幅の浪費の回避を保証するものではない。加えて、このソリューションは、シグナリングオーバヘッドの観点からすれば、ネットワークはオンデマンドで適切なルータにおいてステートをセットアップするよう信号伝達されなければならず、ネットワーク性能を危うくする可能性がある。
【非特許文献１】T. Braun, V. Arya, and T. Turletti, "A Backup Tree Algorithm for Multicast Overlay Networks", Networking 2005, Waterloo,  Canada, May 2005
【非特許文献２】M. Kodialem and T. Lakshman, "Dynamic routing of bandwidth guaranteed multicasts with failure backup",IEEE INFOCOM, New York, USA, Jun, 2002
【非特許文献３】A. Striegel and G. Manimaran, "DSMCast: a scalable approach for DiffServ multicasting", Computer Networks, vol. 44, New York, NY, USA, Apr. 2004
【非特許文献４】J. Cui et al, "Aggregated Multicast-A Comparative Study", Cluster Computing, vol. 8, Hingham,  MA, USA, Jan.2005
【発明の開示】
【課題を解決するための手段】
【００１０】
一実施形態によれば、出口ノードとある入口ノードとの複数の組み合わせの各々について対応する配信ツリーが生成されるように、複数の可能なマルチキャスト配信ツリーを初期化段階において生成するステップと、
あるセッションへの出口ノードの参加または離脱に応じて、前記初期化段階において生成された配信ツリーのうちの選択された別の配信ツリーへ配信ツリーを切替えるステップと
を含む、ネットワークにおけるマルチキャストツリー割当方法が提供される。
【００１１】
初期化段階において、言い換えれば「事前に」複数のマルチキャスト配信ツリーを生成することにより、必要な接続リソースを提供するためにそれほど多くのシグナリングを必要とせずに、変わりゆく環境に適応することが可能な効率的な適応メカニズムを実現するために用いられる接続リソースのオーバプロビジョニングがもたらされる。このようにして、このメカニズムはどんな状況においても最適な配信経路（distribution path）を実現するために、セッションに参加する一連の出口ノードの変化に適応することができる。
【００１２】
一実施形態によれば、全ての可能なマルチキャスト配信ツリーが初期化段階において生成される。このことは、出口ノード（egress node）とある入口ノード（ingress node）との組み合わせの各々（あるいは「現実的な」組み合わせの各々）について、例えばあるノードがセッションに参加したりあるいは離脱したりすることによる出口ノードの集合の変化に適応するために、生成された対応する配信ツリーであってツリー間で切替えるために用いることができる配信ツリーが存在する、ということを意味する。
【００１３】
したがって「全ての可能な」配信ツリーという用語は、全ての理論的に可能な配信ツリーを必ずしも含まないが（含むこともあり得るが）、この「全ての理論的に可能な配信ツリー」の集合（reservoir）から、現実的な観点で選ぶことができるものだけが含まれる、ようなものと解すべきである。これにより例えば、効率性の理由から一部の配信ツリー、例えば、入口ノードまたはエッジノードがツリーの中間ノードを形成しているツリーなどを排除することができる。
【００１４】
複数のマルチキャスト配信ツリーを初期化段階において生成することにより、ある入口ノードに対する出口ノードの異なる組み合わせを有し、それらの中から最も適したものを選ぶことができ、その中で環境に応じて、例えばセッションに参加している出口ノードに応じて切替えることができる、配信ツリーの「集合（reservoir）」または複数のマルチキャスト配信ツリーの「オーバプロビジョニング（過剰投資）」が得られる。
【００１５】
一実施形態によれば、マルチキャストツリーは、複数のマルチキャストグループが１つの配信ツリーを共有しているマルチキャスト集約ツリーを含む。
【００１６】
これにより、複数のマルチキャストグループが１つの配信ツリーを共有している集約ツリーの「分岐した（ramified）」ツリーの利用が可能となる。
【００１７】
一実施形態によれば、前記方法は、適切な集約ツリーを選択することによりセッションの接続をコントロールするステップであって、選択される集約ツリーは、セッションに参加していない出口ノードにより形成される空リーブノード（empty leave node）を持たず、更に、セッションに参加している各ノードに対して選択された集約ツリーの中にリーブノード（leave node）が存在する、ステップを更に含む。
【００１８】
これにより、利用可能なリソースを最適な方法で使用する集約ツリーの選択が可能となる。
【００１９】
一実施形態によれば、前記の配信ツリーを生成するステップは経路のフィルタリングを行うステップを更に含むものであり、
前記のフィルタリングを行うステップは、最善経路の選択または効率の悪い経路の破棄を含む。
【００２０】
これより本メカニズムの効率性が増す。
【００２１】
一実施形態によれば、前記のフィルタリングを行うステップは、入口ルータがフォワーディングノード内にある経路を破棄するステップ、および／または、分岐点が入口ルータにある経路を破棄するステップを含む。
【００２２】
これにより特に効率の悪い経路が避けることができる。
【００２３】
一実施形態によれば、前記方法は、全ての可能な配信ツリーを初期化段階において生成するステップであって、これにより、あるセッションが、入口ノードまたは発信元ノードから１つ以上の出口ノードへのある配信経路を要求する場合には、対応する配信経路が前記初期化段階において既に生成されているものとなる、ステップを含む。
【００２４】
初期化段階において前もって配信経路の集合（reservoir）を生成することにより、後でセッションの利用中に、大きなシグナリングオーバヘッドを必要とせず、または処理のために時間をロスすることなく、この集合から最も適した配信経路を選択することが可能となる。
【００２５】
一実施形態によれば、生成された各配信ツリーは、セッションフローのエンターポイントである入口ルータのアドレスである発信元ＩＰアドレスと、ＩＰマルチキャストアドレスである宛先ＩＰアドレスとから成るマルチキャストタプルにより特定される。
【００２６】
これにより、マルチキャストアウェアな環境において、生成されたツリーまたは経路を利用することが可能となる。
【００２７】
一実施形態によれば前記方法は、ネットワークにおいて利用可能な配信経路を発見し、不分岐の集約ツリーを生成するステップを更に含む。
【００２８】
（不分岐の）集約ツリーはリソースの効率的な利用を可能とする。
【００２９】
一実施形態によれば、前記方法は、前記ネットワーク内の入口ノードが、初期化においてＴＲＥＥメッセージを用いて前記ネットワークをフラッディングし、前記ＴＲＥＥメッセージを受信すると、該ＴＲＥＥメッセージを受信したルータが、該メッセージを受信したインタフェース以外の各外部インタフェース（outgoing interface）に該メッセージを伝搬させるステップであって、ここで、各メッセージは、配信経路リストに含まれ、伝搬に用いられる外部インタフェースのローカルＩＰアドレスを搬送するものである、ステップと、
前記ＴＲＥＥメッセージを受信した後に、出口ノードが、受信したＴＲＥＥメッセージに対応するＲＥＳＰＯＮＳＥメッセージを作成し、該ＴＲＥＥメッセージの発信元である入口ルータへ該ＲＥＳＰＯＮＳＥメッセージを送信するステップであって、該ＲＥＳＰＯＮＳＥメッセージは、ローカル外部インタフェースと当該ＴＲＥＥメッセージの配信経路リストを搬送するものである、ステップと
を含む。
【００３０】
これより配信ツリーの発見または生成が可能となる。
【００３１】
一実施形態によれば、前記初期化段階は不分岐のマルチキャスト集約ツリーを生成するステップを更に含むものであり、
該生成するステップは、
マルチキャストチャネルを配信経路へ割り当てた後に、該配信経路に沿ってＴＲＥＥメッセージを送信するステップであって、各コアノードは前ノードのＩＰアドレスをＭＲＩＢに追加するとともに前記メッセージをダウンストリームに伝搬させるものである、ステップと、
前記ＴＲＥＥメッセージを受信した後に、出口ノードが前ルータのＩＰアドレスを用いて前記ＭＲＩＢを更新し、マルチキャストツリーを生成するためにマルチキャストルーティングプロトコルをトリガするステップと
を含む。
【００３２】
このようにして、不分岐の集約ツリーを生成することができる。
【００３３】
一実施形態によれば、前記初期化段階は、
２つ以上の出口ノードをカバーする分岐したマルチキャスト集約ツリーを計算して生成するステップであって、分岐したツリーは、入口ルータと利用可能な出口ルータとを考慮して全ての不分岐ツリーを組み合わせる（combine）ことにより計算されるものである、ステップと、
分岐したマルチキャスト集約ツリーの各々へマルチキャストチャネルを割り当てるステップと
を含む。
【００３４】
このようにして、効率的な接続制御を実現するための接続制御に用いることができる一連の分岐した集約ツリーを生成することができる。
【００３５】
一実施形態によれば、前記方法は、ルートに分岐点を有する全てのツリーを破棄するステップと、
マルチキャストツリーを構成（configure）するために、全てのツリーへシグナリングメッセージを送信するステップと
を更に含む。
【００３６】
これにより、分岐した集約ツリーの効率的な生成が可能となる。
【００３７】
一実施形態によれば、前記方法は、リソースの浪費を回避すべく、生成された配信ツリーに対して１つ以上のセッションフローを伝搬させるために、セッション接続をコントロールするステップを更に含む。
【００３８】
このようにして、短いレスポンス時間と少ないシグナリングオーバヘッドで特に効率的な接続制御を実現するために、事前に生成された配信ツリーを利用することができる。
【００３９】
本発明によれば、複数の可能なマルチキャスト配信ツリーを初期化段階において生成するモジュールであって、出口ノードとある入口ノードとの複数の組み合わせの各々について対応する配信ツリーが生成されるように、前記複数の可能なマルチキャスト配信ツリーが生成される、モジュールと、
前記初期化段階において生成された配信ツリーのうちの選択された別の配信ツリーに配信ツリーを切替えるモジュールであって、出口ノードのセッションへの参加または離脱に応じて切替が行われる、モジュールと
を備える、ネットワークにおけるマルチキャストツリー割当装置が提供される。
【００４０】
一実施形態によれば、前記装置は、本発明の一実施形態に基づいて方法を実行するモジュールをさらに備える。
【００４１】
本発明の一実施形態に基づいて方法をコンピュータに実行させることを可能にするコンピュータプログラムコードを含むコンピュータプログラムが提供される。
【発明を実施するための最良の形態】
【００４２】
以下、本発明の実施の形態を説明するが、その前に以下の説明で用いる用語について説明する。
【００４３】
・アクセスルータ：受信者が属するアクセスネットワークへリンクされたルータ。
・ＡＳ（Autonomous Systems）：自律システム。
・ＢＲ（Border Router）：境界ルータ（入口または出口）。
・ダウンストリーム：入口ノードから出口ノードまたはアクセスノードへの方向。
・アップストリーム：出口ノードから入口ノードへの方向。
・ユニキャストルーティング情報ベース（Unicast Routing Information Base）：ユニキャストトポロジーテーブル。
・マルチキャストルーティング情報ベース（Multicast Routing Information Base）：一般的にユニキャストＲＩＢから得られるマルチキャストトポロジーテーブル。ＰＩＭプロトコルはＭＲＩＢを使用してjoinメッセージまたはpruneメッセージをどこに送信するかを決定する。
・指定経路（Reserved Path）−Reserveメッセージがリソースをコントロールした経路。
【００４４】
以下、（ここではコネクティビティリソースと見なされる）配信ツリーをオーバプロビジョンするためのメカニズムの実施形態について説明する。本メカニズムおよびその実施形態は、以下の説明においてＡＧＴｒｅｅ（Advanced Aggregation Tree Allocation、高度集約ツリー割当）と呼ばれる。実施の一形態におけるＡＧＴｒｅｅメカニズムは到来セッションフローの集約をコントロールし、それらのメンバユーザ全員に供給する配信ツリーにそれらを動的に割り当てる。これによりシグナリングおよびステートオーバヘッドは大きく削減され、システム性能は向上する。
【００４５】
ＡＧＴｒｅｅ（Advanced Aggregation Tree Allocation）は、コネクティビティリソース（つまり配信ツリー）をオーバプロビジョンし、ユニキャストおよびマルチキャストのセッションフローの集約ツリーへの割当を動的にコントロールするためのメカニズムである。実施の一形態におけるＡＧＴｒｅｅメカニズムは、オンデマンドアプローチから得られるシグナリングオーバヘッドのギャップを、コネクティビティリソースのオーバプロビジョニングとアドミッションコントロールを組み合わせることによって埋める。この際、per-requestシグナリングは行われない。per-flowアプローチに起因するステートオーバヘッドは集約を実行することによって解決され、動的セッション接続制御と組み合わされて、オーバプロビジョニングに起因するリソースの浪費を回避する。さらに、ＡＧＴｒｅｅメカニズムは、非対称ルートに起因する問題を、コネクティビティリソースのオーバプロビジョニングワークの際にＭＲＩＢ（Multicast Routing Information Base）へセッション経路を指示することによって回避する。
【００４６】
ＡＧＴｒｅｅメカニズムにおいて、実施の一形態によれば、配信ツリーは、リソースを設定するための処理（ステートマニピュレーションに起因する）と帯域幅消費（シグナリングに起因する）の点でシステム性能の劣化を抑えるために、システムブートストラップにおいてオーバプロビジョンされる。per-flowの代わりに、ＡＧＴｒｅｅメカニズムは、各ルートノードと利用可能なリーフノードとの間で設定することができる可能な関連付けの数を考慮して事前に配信ツリーを生成する。この状況において、ルートノードはセッションの入口ノード（つまり入口ルータ）であり、リーフノードはネットワークの出口ノード（つまり出口ルータまたはアクセスルータと呼ばれるユーザのアクセスポイント）である。ユニキャストドメインでは、各配信ツリー（不分岐（un-ramified）ツリーと呼ばれる）は、フォワーディングノードにおいてパケット複製が行われないので、ルートノードおよびリーフノードのペアとそれらの間にある一連のコアノードによって構成される。他方、マルチキャストドメインでは、配信ツリーは複数のリーフノードをサポートすることができる。この場合、パケットは分岐点（branching points）（分岐点をサポートする場合、分岐（ramified）と呼ばれる）と呼ばれるルータにおいて複製される。
【００４７】
実施の一形態におけるＡＧＴｒｅｅメカニズムは、セッションフローを集約ツリーに動的に割り当てることによってセッション接続をコントロールする。同じ配信経路を共有する全てのセッションフローは、それらの割当先のサービスクラス（ＣｏＳ：class of service）に関係なく、経路全体をカバーする同じ配信ツリーに集約される。それ故、ＡＧＴｒｅｅメカニズムは、多数の動的パラメータ（例えばセッションまたはフローのリクエストの数など）に依存する代わりに、入口と出口の関連付け（ingress-to-egress(s)associations）の数に基づいて事前に集約ツリーを生成する。実施の一形態におけるＡＧＴｒｅｅメカニズムは、ユニキャストトラフィックとマルチキャストトラフィックを同じ集約ツリー（全てのそのリーフノードが指示されたセッションのメンバを持つ場合は完全に適合する）に割り当てることができる。実施の一形態において、デフォルト設定により、ＡＧＴｒｅｅメカニズムはトンネルベースのアプローチを用いて到着セッションフローを集約ツリーに割り当てる。このアプローチの実施形態は後で詳しく説明する。
【００４８】
実施の一形態におけるＡＧＴｒｅｅメカニズムは、グループメンバのいないツリーのリーフノードへセッションコンテンツを配信することを、オンデマンドで集約ツリーの割当をコントロールすることによって回避する。ＡＧＴｒｅｅメカニズムはリクエストを受信するときはいつでも、指定されたセッションが要求する配信経路をカバーする別の集約ツリーを探索し、セッションの接続に影響を及ぼすことなく、それを適合したツリーにマージする。ＡＧＴｒｅｅがアクティブセッションへのリクエストを受信すると、その宛先が現在割り当てられているツリーによってカバーされていないことを確認し、そのセッションは、新しいものを含めて全てのアクティブメンバのリーフノードを持つ別の集約ツリーに切替えられる。実施の一形態によれば、集約ツリーのあるリーフにアタッチした単一ユーザがセッションを離脱するときにも同じようなアプローチが実行される。集約ツリーの事前の生成と組み合わせたこのローカルな動的切替スキームにより、発信元または故障したエレメントから遠く離れたあるポイントからのリルーティングのためにシグナリング交換を必要とするスキームと比較して、故障からの迅速な復帰（例えばリルーティング）が可能となる。
【００４９】
ＡＧＴｒｅｅメカニズムは、完全に適合した配信ツリーのローカルな利用可能性をチェックすることによってセッションのアドミッションをコントロールする。配信ツリーの事前の生成とアドミッションコントロールを組み合わせることにより、ＡＧＴｒｅｅメカニズムはコネクティビティリソースを設定するためのオンデマンドのメッセージ交換を回避することによりシグナリングオーバヘッドを減らす。さらに、ネットワーク性能はトラフィック集約とセッション接続コントロールを通じて向上し、パケット転送処理におけるper-flowマルチキャストステートストレージの影響は軽減される。実施の一形態によれば、本メカニズムは次のようなコンポーネントまたはオペレーションを含む。
・各受信者は、任意のオフラインまたはオンライン手段を用いて利用可能なセッションを送信者から取得する。
・セッションに参加することに興味を持つ各受信者は、セッションセットアップ時間に受信者が接続した先のネットワークのエージェント（アクセスルータと呼ぶ）に参加を要求する。
・ネットワークエージェントにおけるプロトコルまたはメカニズムは各ドメインにおいてセッションフロー毎にコネクティビティリソース（つまり配信経路の割当）を、参加に興味のあるユーザがアタッチした先のアクセスルータのＩＰアドレスを示すことにより要求する。
・外部メカニズムは、参加または離脱しなければならないマルチキャストチャネルを通知することにより、アクセスルータからメンバユーザへの接続をコントロールする役割を担う。例えば、メンバユーザ側のアプリケーションは、ＩＧＭＰｖ３（非特許文献「B. Cain et al., "Internet Group Management Protocol, Version 3", IETF, RFC 3376, Oct 2002」参照）またはＭＬＤｖ２（非特許文献「R. Vida and L. Costa, "Multicast Listener Discovery Version 2 (MLDv2) for IPv6", IETF, RFC 2710, Jun 2004」参照）をトリガする。さらに、このアプリケーションは、セッションがアクセスルータにメンバユーザを持たない時を知らせるために、ＡＧＴｒｅｅメカニズムをトリガすることができる。例えば、ＳＥＡＣＯＮと呼ばれるメカニズムは、アクティブメンバユーザがいない時を知らせることができる。ＳＥＡＣＯＮと呼ばれるこのメカニズムについては２００８年２月１８日に本願と同じ出願者によって日本国特許庁に出願された特許文献「日本国特許出願第２００８−３６４９３号」に記載されており、その内容を引用することにより本明細書の一部をなすものとする。ＳＥＡＣＯＮの更なる詳細についてはこの特許出願で引用された文献を参照されたい。
・通信ポートの範囲として、RegisteredまたはDynamic及び／またはPrivate（非特許文献「E. Kohler, M. Handley and S. Floyd, "Datagram Congestion Control Protocol (DCCP)", IETF, RFC4340, Mar 2006」参照））が利用可能であるべきで、ポートのプール（pool of ports）にファイルされるべきである。
・実施の一形態によるルータは、IP Routing Alert Option（例えば非特許文献「ＲＦＣ２１１３」参照）を認識する。
【００５０】
実施の一形態におけるＡＧＴｒｅｅメカニズムがサポートする機能は、それぞれＡＧＴｒｅｅＥｄｇｅエージェント（ＡＧＴｒｅｅ−Ｅ）とＡＧＴｒｅｅＣｏｒｅエージェント（ＡＧＴｒｅｅ−Ｃ）と呼ばれる、エッジルータとコアルータに位置するエージェントに実装される。ＡＧＴｒｅｅ−Ｅエージェントはセッションフローのアドミッションをコントロールするためにステートフル（statefull）であり、ネットワーク全体におけるコネクティビティリソースをコントロールするオペレーションを開始する。実施の一形態によるＡＧＴｒｅｅ−Ｅエージェントは、例えば他のＡＧＴｒｅｅエージェントとインタラクトし、外部のプロトコルまたはメカニズムと通信するために、内部および外部のインタフェースを実装する。これとは対照的に、実施の一形態によるＡＧＴｒｅｅ−Ｃはステートを減らしており、クラスごとに（per-class）入口ＩＰアドレスとマルチキャストチャネル（適用可能な場合）を記憶し、シグナリングを受けた際にコネクティビティリソースを設定するために内部インタフェースのみをサポートする。従って、システムのスケーラビリティは、コアノードはシンプルにしたまま、リソースをコントロールする複雑なオペレーションをエッジノードに押しつけることによって達成される。
【００５１】
環境によってサポートされるマルチキャストアプローチに関して、ＡＧＴｒｅｅは、中央の、または分散したエンティティと相互作用することができる。図１は３つのネットワーククラスタによって構成されるシナリオを示している。このシナリオにおいて、ドメインＡおよびＢはマルチキャストアウェアであり、ＰＩＭ−ＳＳＭ（例えば非特許文献「S. Bhattacharyya, "An Overview of Source-Specific Multicast (SSM)", IETF, RFC3569, Jul 2003」参照）とＰＩＭ−ＳＭ（例えば非特許文献「D. Estrin et al, "Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification", IETF, RFC2362, Jun 1998」参照）を実装し、ドメインＣはユニキャストをサポートする。実施の一形態におけるＡＧＴｒｅｅメカニズムは、分散方式でコネクティビティリソースをコントロールする働きをする。この際、マルチキャストルーティングプロトコルは、マルチキャストツリーを生成するために出口ルータでトリガされる。他方、ドメインＣはユニキャストであり、配信ツリーは入口ノードにおけるＡＧＴｒｅｅ−Ｅエージェントによって管理される。
【００５２】
実施の一形態によれば、ＡＧＴｒｅｅによってサポートされる機能性を実装するため、次のようなインタフェース（図２参照）が用意される。
・アプリケーションインタフェース：セッションオブジェクトを運ぶリクエストを用いてＡＧＴｒｅｅメカニズムをトリガするために、外部のメカニズムまたはプロトコルによって使用される。さらに、ＡＧＴｒｅｅメカニズムはこのインタフェースを使用してリクエスタアプリケーションに、リクエストされた作業の結果をフィードバックする。例えば、セッションフローがＡＧＴｒｅｅアウェア・クラスタに入る前に、外部アプリケーションはこのインタフェースを用いて到来フローのためのリソース（つまり配信経路）をリクエストする。ＡＧＴｒｅｅメカニズムは同じくこのインタフェースを用いて、前リクエストが成功裏に遂行されたことを確認するために、リクエスタアプリケーションをトリガする。加えて、ＡＧＴｒｅｅメカニズムは、新たなユーザが当該セッションに関心があるときに、またはユーザが別のドメインに移動したために、進行中のセッションフローのコネクティビティリソースを割り当てし直すための指示を受信することができる。
・マルチユーザコントロールインタフェース：集約ツリーを割り当てるためにユニキャストおよびマルチキャストのＩＰアドレスと通信ポートの割当を管理するために使用される。またこのインタフェースは、割り当てられた外部インタフェース（通信インタフェースによって取得される）のリプリケータを設定することによりマルチキャスト集約ツリーを生成するために使用される。マルチキャストツリーを生成または管理するためにマルチキャストプロトコルをトリガするだけでなく、ＭＲＩＢへのエントリの追加もこのインタフェースを通じて実行される。最後に、ＡＧＴｒｅｅメカニズムはこのインタフェースを使用して、マルチキャストツリーがインストールされた時点をチェックするため、またはＭＲＩＢから経路を検索するため、制御情報をクエリーする。
・通信・経路制御インタフェース：制御情報を運ぶメッセージを、オペレーションを実行するためのサポートとしてＡＧＴｒｅｅエージェント間で交換するためのサポートとして使用される。さらに、ＡＧＴｒｅｅメカニズムは、利用可能なユニキャストルーティングプロトコル（例えばＯＳＰＦ）と相互作用することによって、このインタフェースを介して更に処理するためのネットワークインタフェースを特定する。この場合、情報はＲＩＢ（ルーティング情報ベース）から検索される。実施の一形態におけるＡＧＴｒｅｅメカニズムはこのインタフェースを通じて、例えば、ＯＳＦＰが下層プロトコルによりネットワークインタフェースがダウンしていることを知らされたときなど、リルーティングイベントを検出することができる（例えば非特許文献「J. Moy, "OSPF Version 2", IETF, RFC2328, Apr 1998」参照）。
【００５３】
図２はＡＧＴｒｅｅエージェントのタイプに基づくインタフェースを示している。ＡＧＴｒｅｅエージェント間のコントロール情報を運ぶ交換メッセージは、通信インタフェースを通じて実装される。
【００５４】
以下、実施の一形態によるＡＧＴｒｅｅメカニズムのメッセージについて説明する。
【００５５】
ＡＧＴｒｅｅメッセージ：
・ＴＲＥＥ：このメッセージは、利用可能な配信経路を発見し、実施の一形態によればマルチキャストアウェアネットワーク（multicast-aware networks）における集約ツリーの生成を要求するために、ＡＧＴｒｅｅ−Ｅが使用する。後者に関して、実施の一形態によるメッセージには、マルチキャストチャネルがそれらの設定のサポートとして埋め込まれる。メッセージ固有フラグはＡＧＴｒｅｅエージェントの動作をコントロールすることができる。このフラグは例えばオペレーションが実行されてはならないかどうかを指示する。
・ＲＥＳＰＯＮＳＥ：このメッセージは、要求されたオペレーションについてＡＧＴｒｅｅ−Ｅエージェントにフィードバックするために使用される。このメッセージは、例えば配信経路を構成する一連のノードなど、特定の制御情報を含むことができる。ノードがルーティングプロトコルによりインタフェースがダウンしていることを知らされたときはいつでも、実施の一形態によれば、このメッセージはローカルに記憶された全ての入口ノードに対して、リルーティングイベントが検出されたことを示す固有フラグセットと共に送られる。
【００５６】
実施の一形態によれば、デフォルト設定により、ＡＧＴｒｅｅメカニズムはその機能を実行するためにエンド・ツー・エンドで機能する。しかしながら、外部のセッションコントローラと組み合わせられると、実施の一形態によればＡＧＴｒｅｅメカニズムはエッジ・ツー・エッジで動作し、そのオペレーションを各ネットワークに制限する。例えば、ネットワーク間エンド・ツー・エンドオペレーションを有するセッションコントローラは、各ネットワークのエッジ（入口ルータと出口ルータ）においてＡＧＴｒｅｅをトリガすることができ、ツリー集約はそのリクエストに対してネットワーク内部またはネットワーク間リンクにおいて処理されることが許される。
【００５７】
ＡＧＴｒｅｅメカニズムの実施形態は次のような利点を持つ。
・事前に配信ツリーを生成し、集約とセッション接続をコントロールするための独自のソリューションを用いることによって、システムの複雑度を低減し、その運営コストを削減する。
・セッションセットアップ時間を削減する。
・シグナリングおよびステートオーバヘッドを大きく削減する。
【００５８】
次にＡＧＴｒｅｅの実施形態について詳しく説明する。
【００５９】
各ＡＧＴｒｅｅ−Ｅエージェントは、アクティブなセッション、フローおよび配信経路のリストを記憶している。各アクティブセッションエントリはセッション識別子と関連するフローのリストとを含み、各フローエントリはそのフロー識別子、ＣｏＳ、ビットレート、送信元アドレス、宛先アドレス、出口アドレス、アクセスアドレスおよび配信経路を保持する。配信経路のリストの各エントリには、全体の経路を構成するコアノードのＩＰアドレスが埋め込まれる。マルチキャストアウェアネットワークでは、ＡＧＴｒｅｅは各外部インタフェースのマルチキャストステート（それらの関連するマルチキャストチャネルが埋め込まれている）を記憶している。ＡＧＴｒｅｅ−Ｃエージェントは適用可能なときにマルチキャストステートを格納するだけである。
【００６０】
次にコネクティビティリソースをオーバプロビジョンするためにＡＧＴｒｅｅメカニズムによって実現される機能について説明する。
【００６１】
以下、配信ツリーの事前生成について説明する。「事前」とはここでは、例えばシステムブートストラップなどの初期化段階の間、またはセッションを実際に配信する前に起こる任意の初期化段階の間を意味する。
【００６２】
全ての配信ツリー（実施の一形態において、入口ノードから出口ノードもしくは出口ノードの任意の組み合わせ、または入口ノードおよび出口ノードの任意の組み合わせに対する、全ての可能な配信ツリー）はＡＧＴｒｅｅメカニズムによって、例えばシステムブートストラップ時などの初期化段階において生成され、これによりライフタイム全体にわたって将来の全てのリクエストに備えて、リソース設定のための余分なシグナリングを要求することなく、環境をプロビジョンする。「全ての可能な」配信ツリーという用語については、配信ツリーは、必ずしも理論的に可能な全ての配信ツリーを包含しない（これも当然可能である）ものの、この「全ての理論的に可能な配信ツリー」の蓄積（reservoir）から現実的な観点で選ぶことができるものだけが含まれるようなものと解すべきである。これは、例えば効率性の理由から一部の配信ツリー（例えば入口ノードまたは出口ノードがツリーの中間ノードを構成しているツリーなど）を排除する場合がある。従って「全ての可能な配信ツリー」と言う代わりに、あるセッションに参加している所与の入口ノードおよび出口ノードに基づいてその「セッションのマルチキャスト配信のために選ぶことができる全ての配信ツリー」と言うことができる。その意図は、そのセッションに参加している入口ノードと出口ノードのある（または任意の）所与の組み合わせに対してその生成のためにシグナルオーバヘッドが必要とされることなく使用可能な対応する配信経路が既に存在しているような配信経路の蓄積を提供することにある。言い換えると、セッションが、入口ノードもしくは発信元ノードから１つ以上の出口ノードに対するある特定の配信経路を必要とする場合、対応する配信経路は初期化段階において既に生成されている。それ故、実施の一形態によれば、任意の一連の受信者（これらの受信者が接続されているある一連の出口ノードに対応する）と対応する入口ノード（多くのセッションが同時に実行されている場合は、それらの１つ以上）に対して、配信のために選択された適切な配信経路が存在し、一連の受信者（または出口ノード）が変化する場合には、新たな一連の受信者（または出口ノード）と適合する異なる配信経路への切替を実行することができる。同様に、入口ノード（または一連の入口ノード）が変化する場合には、切替を実行することができる。
【００６３】
生成された各配信ツリーは、発信元ＩＰアドレス（Ｓ）と宛先ＩＰアドレス（Ｇ）から構成されるマルチキャストタプルによって特定される。発信元ＩＰアドレスは、セッションフローのエンターポイントである入口ルータである。宛先ＩＰアドレス（Ｇ）は、実施の一形態によればマルチユーザコントロールインタフェースにより割り当てられるＩＰマルチキャストアドレスである。
【００６４】
実施の一形態によれば配信ツリーの初期化は、ユニキャストネットワークでは単一の段階で実行され、マルチキャストネットワークでは三段階で実行される。両方の接続タイプのサポートに共通する最初の段階は、ネットワーク内において利用可能な配信経路を発見し、不分岐の（un-ramified）集約ツリーを生成することから成る。
【００６５】
配信経路は、入口ルータによって初期化されるフラッディング（flooding）オペレーションによって発見される。このオペレーションは、固有フラグが、初期化を示すｏｎに設定されたＴＲＥＥメッセージと呼ばれる「フラッディングメッセージ」をネットワークにフラッド（flood）させることから成る。ＴＲＥＥ（Ｉ）メッセージを受信すると、ルータはそのメッセージを、メッセージを受信したものを除いて各外部インタフェースに伝搬させる。各メッセージは、伝搬に使用される外部インタフェースの、配信経路リストに記載される、ローカルＩＰアドレスを搬送する。ＴＲＥＥ（Ｉ）メッセージを受信した後、出口ルータは、受信したＴＲＥＥ（Ｉ）メッセージに対応するＲＥＳＰＯＮＳＥメッセージを作成し、それを当該ＴＲＥＥ（Ｉ）メッセージの送信元である入口ルータに送信する。ＲＥＳＰＯＮＳＥメッセージは、当該ＴＲＥＥメッセージの配信経路リスト、ローカル外部インタフェースおよび確認コード（ＯＫ）を搬送する。
【００６６】
実施の一形態によるフラッディングオペレーションは、ユニキャストルーティングプロトコルに基づいている。このようにして全ての利用可能な配信経路を提供する。配信経路を使用することから得られる利益（例えばパケット複製の回避）は、それらの形状に依存するので、実施の一形態によるＡＧＴｒｅｅは配信経路をフィルタリングし、最善経路だけを選ぶ。「フィルタリング」は、最善経路を選択すること、または効率の悪い経路を破棄すること、またはその両方を含む。マルチキャストツリーの性能は概してそのトポロジーに依存し、含まれるリンクの量やツリー内のどこで分岐が起こるかが考慮されなければならない。ツリーが長くなり伝送コストが大きくかさむ結果になると、実施の一形態におけるＡＧＴｒｅｅメカニズムは、入口ルータがフォワーディングノード内にある経路を破棄する。さらに、配信ツリーは、ブランチがそれらのルートに近づくにつれより多くのネットワークリソース（例えば帯域幅）を要求し、その結果、パケット複製量が増加する。マルチキャストの最悪のケースはツリーのルートが分岐点である場合なので、ＡＧＴｒｅｅは入口ルータに分岐点を持つ経路を破棄する。
【００６７】
図３は、リソースを初期化するための第１段階のオペレーションを示している。各入口ルータ（Ｉ１およびＩ２）にあるＡＧＴｒｅｅ−Ｅエージェントは、ネットワークをＴＲＥＥ（Ｉ）を用いてフラッディングする。ＴＲＥＥ（Ｉ）メッセージが届いた全てのコアノードは、パケットの送り先となる外部インタフェースのローカルＩＰアドレスを配信経路リストへ追加し、メッセージを受信したもの以外の全てのインタフェースへそれをフォワードする。ＴＲＥＥ（Ｉ）メッセージを受信した後、各出口ルータ（Ｅ１、Ｅ２およびＥ３）は受信した各ＴＲＥＥ（Ｉ）メッセージに対応するＲＥＳＰＯＮＳＥメッセージを作成し、そのローカルＩＰアドレスを配信経路リストに追加し、それを当該ＴＲＥＥ（Ｉ）の発信元である入口ルータへ送信する。ＲＥＳＰＯＮＳＥメッセージは、確認コード（ＯＫ）と当該ＴＲＥＥ（Ｉ）メッセージの配信経路リストを搬送する。Ｉ２がＩ１から送られたＴＲＥＥ（Ｉ）メッセージを受信すると、Ｉ２で構成された（comprised with）経路エントリを避けるためＲＥＳＰＯＮＳＥメッセージはＩ１には送られない。
【００６８】
受信した各ＲＥＳＰＯＮＳＥ（ＯＫ）メッセージにより提供された情報に基づいて、Ｉ１およびＩ２にあるＡＧＴｒｅｅ−Ｅエージェントは、ローカル配信経路情報を更新する。ＡＧＴｒｅｅは、マルチキャストタプル（Ｓ，Ｇ）を各配信経路エントリ（簡単のため図３には示されていない）へ割り当てることにより不分岐集約ツリーを生成する。発信元（ルートノード）はＲＥＳＰＯＮＳＥ（ＯＫ）メッセージを受信した入口ルータのＩＰアドレスであり、宛先はマルチユーザコントロールインタフェースにより割り当てられたマルチキャストＩＰアドレスである。
【００６９】
マルチキャストアウェアネットワークにおいて、配信ツリーの初期化は更に２つの段階を必要とする。第２段階は不分岐マルチキャスト集約ツリーをそれらの経路に沿ったノードに設定することを目的とし、これはユニキャストネットワークでは行われない。ＡＧＴｒｅｅメカニズムは、エンド・ツー・エンドのシグナリングの際にマルチキャストアドレスを外部インタフェースに直接的に設定するか、またはＭＲＩＢエントリを（エンド・ツー・エンドのシグナリングにおいて）コントロールし、マルチキャストツリーを生成するために出口ルータにおいて利用可能なマルチキャストルーティングプロトコルをトリガすることにより、マルチキャストツリーを２通りにコントロールすることができる。図４に示した図に関しては、ＡＧＴｒｅｅメカニズムは後者の方法で動作する。それ故、各入口ルータのＡＧＴｒｅｅ−Ｅエージェントは、最初にマルチキャストチャネル（宛先アドレスとポート）を各配信経路エントリへ割り当てる。
【００７０】
図４は、不分岐マルチキャスト集約ツリーを生成するためのオペレーションを示している。ここでは、簡単のため、シグナリングイベントは全体的には描かれておらず、Ｉ１におけるステートのみ説明する。Ｉ１からの経路のテーブルは、各配信経路のキーインデックス（テーブル中のインデックス）と、各経路を構成するノード（テーブル中のノード）と、各経路（Ｇｘ）に割り当てられたＩＰマルチキャスト宛先（テーブル中のＧ）とから構成される。このテーブルには発信元アドレスは記載されていない。それはローカルＩＰアドレス（例えば入口ルータのＩＰアドレス）であるからである。マルチキャストチャネルを配信経路に割り当てた後、ＡＧＴｒｅｅはＴＲＥＥメッセージを配信経路に沿って送信する。各ＡＧＴｒｅｅ−ＣエージェントはＭＲＩＢへ前ルータ（１つ前のルータ）のＩＰアドレスを追加し、そのメッセージをダウンストリームに伝搬させる。ＴＲＥＥメッセージを受信した後、出口ノードにあるＡＧＴｒｅｅ−ＥエージェントはＭＲＩＢを前ルータのＩＰアドレスに更新し、マルチキャストツリーを生成するためにマルチキャストルーティングプロトコルをトリガし、ＲＥＳＰＯＮＳＥ（ＯＫ）メッセージをリクエスタの入口ノードへ送信する。その後、この入口ノードは第３段階を実行する。
【００７１】
第３段階は、２つ以上の出口ノードをカバーする分岐したマルチキャスト集約ツリーを計算して生成することを目的とする。ＡＧＴｒｅｅは、入口ルータと利用可能な出口ルータを考慮に入れて全ての不分岐ツリーを組み合わせる（combine）ことにより分岐したツリーを計算する。その後、ＡＧＴｒｅｅはルートに分岐点を持つ全てのツリーを破棄し、マルチキャストツリーを構成するためにＴＲＥＥメッセージを用いて各ツリーへシグナリングする。
【００７２】
図５は、分岐したマルチキャスト集約ツリーのリスト（簡単のためＩ１に関するもののみ）を示している。計算されたそれぞれの分岐ツリーに対して、ＡＧＴｒｅｅはマルチキャストチャネルを割り当て、マルチキャストツリーを構成するためにＴＲＥＥメッセージを送信する。ＴＲＥＥメッセージは、分岐ツリー（ramified tree）を含む配信経路の各出口ルータへ送信される。ＡＧＴｒｅｅは、受信したメッセージに示されたマルチキャストチャネルを、メッセージの宛先（つまり出口ルータ）に向かう外部インタフェースに設定する。エージェントが、指示されたマルチキャストチャネルが検索したインタフェースに既に設定されていることを確認した場合には、そのオペレーションはスキップされる。ＴＲＥＥメッセージを受信した後、出口ルータはＲＥＳＰＯＮＳＥ（ＯＫ）メッセージを入口ルータに向けて送信する。
【００７３】
全ての集約ツリーが生成された後、実施の一形態によるＡＧＴｒｅｅメカニズムは、セッションフローを集約ツリーに伝搬させ、例えばアクティブなユーザメンバがいないツリーのリーフノードにおけるパケットの複製によるリソースの浪費を回避するように、セッション接続をコントロールする。
【００７４】
次に本発明の実施形態によるセッション接続制御について詳しく説明する。
【００７５】
セッション接続制御機能は、ライフタイム全体にわたってエンド・ツー・エンドのセッション経路に沿ってセッションの継続性を確保するためのサポートとしてＡＧＴｒｅｅメカニズムによって使用される。セッション経路は接続スキームの点で異種混合である場合があり、例えばユニキャストネットワークとマルチキャストネットワークによって構成される場合がある。
【００７６】
異種混合ネットワーク上のエンド・ツー・エンドの接続制御は、トンネルベース（例えば非特許文献「B. Zhang et al, "Host Multicast: A Framework for Delivering Multicast to End Users", Annual Joint Conference of the IEEE Computer and Communications Societies, June 2002」参照）、または変換ベース（例えば特許文献「E. Pearce et al, "System and Method for Enabling Multicast Telecommunications", Application Patent, US7079495 B1, July 2006（米国特許第７０７９４９５（Ｂ１）号）」参照）のアプローチを用いることによって実行することができる。実施の一形態によれば、デフォルト設定により、ＡＧＴｒｅｅはトンネルベースのアプローチを使用する。この場合、集約ノードは各セッションフローの到来パケットに追加ヘッダ（それらのオリジナルのＩＰヘッダの５タプル（IP header five tuple）で満たされている）を付加する。他方、ＩＰヘッダは適合した集約ツリーの５タプルの情報に更新される。デアグリゲータノード（出口）において、ＡＧＴｒｅｅはＩＰヘッダを追加ヘッダで運ばれた５タプルに更新し、それをパケットから取り除く。代替的には、ＡＧＴｒｅｅは外部のエンド・ツー・エンド接続制御ソリューション（例えば変換ベース）との組み合わせで機能する。こうして、ＡＧＴｒｅｅはアプリケーションに選択された集約チャネルの転送情報を与える。
【００７７】
さらに、ＡＧＴｒｅｅは望まない宛先へのパケット複製を避けるために集約ツリーの切替をコントロールする。図６に示された状態図は、ＡＧＴｒｅｅのオペレーションがオンデマンドでセッション接続をコントロールする様子を、集約ツリーの切替の観点から概要を示したものである。セッション（Ｓｉ）のセッションオブジェクト（Ｓｏｂｊ）と出口ルータＩＰ（Ｅ）を運ぶセッションリクエスト（Ｒｉ）を用いてトリガされたときはいつでも、ＡＧＴｒｅｅ−ＥエージェントはＲｉをマージするために完全に適合する集約ツリー（ＡＴｐｍ）をローカルに検索しなければならない。しかしながら、Ｓｉが別の出口ルータでローカルにアクティブになると、ＡＧＴｒｅｅは両方の出口ルータ（既存のものと新たなもの）を供給する別のＡＴｐｍを検索し、Ｓｉをその新たなＡＴｐｍに切替える。セッションが例えばハンドオフまたはセッション離脱に起因してアクセスルータまたは出口ルータにおいてもはやアクティブでないユーザメンバを持つ場合には、ＡＧＴｒｅｅはリソースの浪費を避けるためにセッションを別のマルチキャストツリーに切替えなければならない。従って、この検出を実行することが可能な外部メカニズム（非特許文献「E. Cerqueira et al. "Multi-user Session Contml in the Next Generation Wireless System", 4th ACM International Workshop on mobility Management and Wireless Access, Malaga, Spain, Oct 2006」参照）は、ＡＧＴｒｅｅ（Ｌｉ）にこの状況を報告し、次にＡＧＴｒｅｅ（Ｌｉ）は新たなＡＴｐｍを探索してＳｉをそれに応じて切替える。
【００７８】
実施の一形態によれば集約ツリーの切替は、ある特定のセッションのための所与の一連の出口ルータに対して「完全適合（perfect match）」または「最善適合（best match）」する集約ツリーが選ばれるように実行され、そして、そのセッションに参加している接続した受信者が存在する一連の出口ルータが（例えば新たな受信者が参加したり、またはある受信者が離脱したりしたために）変更される場合には、新たな集約ツリーが初期化段階の間に生成されたものから選ばれるように切替が実行される。「最善適合」または「完全適合」は、実施の一形態によればここでは、選択された集約ツリーがセッションに参加していない出口ノードによって形成される空リーブノード（empty leave nodes）を持っていないこと、そして更に、セッションに参加しているそれぞれについて選択された集約ツリーの中にリーブノード（leave node）が存在する、ということを意味する。このようにして、システムは、大きなシグナリングオーバヘッドなしに、変化する環境に適応することができる。
【００７９】
図７は、モビリティサポート（例えばモバイルＩＰ）とセッションコントロール（例えば上記日本国特許出願第２００８−３６４９３号に記載のＳＥＡＣＯＮメカニズムによって提供される）が考慮される一般的なシナリオにおいて、オンデマンドでセッション接続をコントロールすることにおけるＡＧＴｒｅｅにより実行されるオペレーションを集約ツリーの切替の観点から示している。簡単のため、モビリティおよびセッションのコントロールの動作は図示されていない。ドメインＡをＰＩＭ−ＳＳＭマルチキャストサポートのあるネットワークと考える。Ｎ１はセッションＳ１を供給する発信元サーバである。Ｉ１上の（既に言及した）ＳＥＡＣＯＮメカニズムは、Ｒ１がＥ１に結合したことによりＡＧＴｒｅｅ−ＥをＳ１のセッションリクエストＲ１でトリガする。集約ツリー０は専らＥ１にサービスしていることから、ＡＧＴｒｅｅはＳ１を集約ツリー０にマージし、次に、Ｒ１がＳ１のコンテンツを受信することができるよう、ＳＥＡＣＯＮメカニズムにチャネルＩＤを報告する。ツリー０はＩ１−Ｃ１−Ｉ１を含む。次にＳＥＡＣＯＮは、Ｒ２がＥ２に結合したことによりＡＧＴｒｅｅ−ＥをＳ１のセッションリクエストＲ２でトリガする。こうして、ＡＧＴｒｅｅ−Ｅは、Ｅ１とＥ２に同時にサービスするためにＳ１を集約ツリー０から集約ツリー１（Ｃ１におけるブランチとＣ１−Ｃ４−Ｅ２を更に含む）へ切替え、ＳＥＡＣＯＮに新たなチャネルのＩＤを報告する。このケースではＲ１はＩＧＭＰまたはＭＬＤを用いて古いツリーを離脱し、新しいツリーに参加する。Ｒ３がＥ３に結合したことにより同じことが起こる。この場合、ＡＧＴｒｅｅメカニズムは、Ｓ１を集約ツリー１から集約ツリー２（Ｉ１におけるブランチと経路Ｉ１−Ｃ２−Ｃ３−Ｅ３を更に含む）へ切替える。Ｒ３がＥ３からＥ２へ移動し、Ｅ３においてアクティブなユーザメンバがいない場合は、ＡＧＴｒｅｅメカニズムはＩ１において（ＳＥＡＣＯＮメカニズムにより）例えばＥ３からの離脱リクエスト（leave request）を用いてトリガされる。Ｒ３がＥ２にアタッチした後、ＡＧＴｒｅｅメカニズムはＥ２においてＳ１に参加するためのＲ３からのリクエストを用いてトリガされる。ＡＧＴｒｅｅはＳ１がＩ１においてアクティブになっておりＥ１とＥ２に供給していることを知っているので、ＡＧＴｒｅｅはＳ１を集約ツリー２から集約ツリー１へ切替える。
【００８０】
新たなハンドオフが起こる場合、ＡＧＴｒｅｅはＩ１においてトリガされた後、同様に動作する。新たな完全集約ツリーと適合すると、ＡＧＴｒｅｅは古いツリーから新しいツリーへの切替を実行する。
【００８１】
ここでは例示のためにいくつかの実施形態を説明した。実施の一形態によればブートストラップなどの初期化の際に一連のローカルマルチキャストツリーの構成が実行される。次に外部のマルチキャストツリーから事前に生成された内部のマルチキャストツリーへのマッピングを実行することができ、例えば受信者と選択されたマルチキャストツリーとの間のリーキな（leaky）または不完全な適合を避けるために、受信者の位置に基づいて外部のマルチキャストツリーのマッピングの調整を実行することができる。
【００８２】
本発明の１つの実施形態は次のようにまとめることができる。
ａ）集約されたマルチキャストツリーを事前に（例えばブートストラップまたは初期化段階で）生成する。
・ａ１）利用可能な配信経路を発見する。
・ａ２）不分岐ツリーを生成する。
・ａ３）分岐配信ツリーを生成する。
・ａ４）最善経路をフィルタリングによって選ぶ。
・・ａ４ｉ）入口ルータが中間ノードにあたる経路を破棄する
・・ａ４ｉｉ）分岐点が入口ルータにある経路を破棄する
ｂ）マルチキャストリクエストを集約ツリーにマッピングする。
・ｂ１）フローカプセル化に基づく。
・ｂ２）ユーザのいないリーフノードへデータを配信することを避けるためにマルチキャストツリーを切替える。
【００８３】
オペレーションａ１）は図３に、オペレーションａ２）は図４に、オペレーションａ４）は図５に概略的に示されている。マッピングは図７に概略的に示されている。
【００８４】
本実施形態および他の実施形態の変更は、当業者によって特に上記説明の特徴を明示的に開示されていない方法で組み合わせることによって実行できることは明らかである。しかしながら、上記開示は、１つの実施形態に関連して言及した特徴が別の実施形態に関連して使用されることもあることが明示的に言及されてはいないが当業者には明らかであるような特徴の組み合わせも包含すべきものであることを理解されたい。例えば、特徴の上記リストにおいて、ａ４ｉ）を外してａ４ｉｉ）のみがその他の特徴と組み合わせることができる場合がある。このような組み合わせが明示的に開示されていなくとも、当業者であれば、斯かる組み合わせは少なくとも暗に開示されたものと見なすべきことを理解されたい。
【００８５】
上記の実施形態は、ハードウェア、ソフトウェア、あるいはハードウェアとソフトウェアの組み合わせによって実施することができることは当業者であれば理解できよう。本発明の実施形態に関連して説明したモジュールおよび機能は、全体的または部分的に、本発明の実施形態に関連して説明した方法の通りに動作するように適切にプログラムされたマイクロプロセッサまたはコンピュータによって実現することができる。本発明の実施形態を実現する装置は例えば、本発明の実施形態で説明したセッションアウェアな接続制御を実行することができるように適切にプログラムされたネットワークにおけるノードその他の構成要素（例えばルータなど）を含む。
【００８６】
本発明の実施の一形態として、データキャリアに格納された、あるいは他の方法で記録媒体もしくは伝送リンクといった何らかの物理的手段によって具現化されたコンピュータプログラムであって、上記実施形態に従ってコンピュータを動作させることを可能にするコンピュータプログラムが提供される。
【００８７】
本発明の実施形態は、例えばネットワーク内のノード若しくはネットワーク内の他のエンティティであって上記マルチキャストツリー割当メカニズムに従って動作するようにプログラムされたものによって実現することができる。
【図面の簡単な説明】
【００８８】
【図１】本発明の実施形態が適用できる環境を示す図である。
【図２】本発明の実施の一形態によるノードのインタフェースを示す図である。
【図３】本発明の実施の一形態による配信経路生成方法の説明図である。
【図４】本発明の実施の更なる一形態による配信経路生成方法の説明図である。
【図５】本発明の実施の更なる一形態による配信経路生成方法の説明図である。
【図６】本発明の実施の一形態による状態図である。
【図７】本発明の実施の一形態によるマルチキャストツリー割当方法の説明図である。
【符号の説明】
【００８９】
Ｃ１〜Ｃ４  コアノード
Ｅ１〜Ｅ３  出口ノード
Ｉ１、Ｉ２  入口ノード
Ｎ１  セッションサーバ
Ｒ１〜Ｒ３  受信者
【図１】
0004654278.tif 000002
【図２】
0004654278.tif 000003
【図３】
0004654278.tif 000004
【図４】
0004654278.tif 000005
【図５】
0004654278.tif 000006
【図６】
0004654278.tif 000007
【図７】
0004654278.tif 000008