JP4231074B2

JP4231074B2 - マルチキャストラベルスイッチング方法

Info

Publication number: JP4231074B2
Application number: JP2006281971A
Authority: JP
Inventors: 正祥安川; 幸司杉園; 雅則宇賀
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 2003-02-07
Filing date: 2006-10-16
Publication date: 2009-02-25
Anticipated expiration: 2024-02-06
Also published as: JP2007014033A

Description

本発明は、マルチキャストラベルスイッチング方法に係り、特に、マルチキャスト通信ネットワークにおいて、上記マルチキャスト通信経路設定技術におけるマルチキャストソースノードからマルチキャストリーフノードグループまでの、効率的なマルチキャスト配信（転送）を可能とするマルチキャストラベルスイッチング方法に関する。

また、本発明は、マルチキャストラベルスイッチング方法をＶＰＮ（仮想閉域網）サービスに適用したマルチキャストラベルスイッチング方法に係り、ＭＰＬＳ（マルチプロトコルラベルスイッチングMulti Protocol Label Switching）を用いたＶＰＮ内で、ＰＥ（プロバイダエッジ）ルータ間に効率的に、各ＰＥルータが収容するＶＰＮサイトの条件に応じてプロバイダネットワーク内に最適なマルチキャストラベルスイッチング経路を設定するマルチキャストラベルスイッチング通信方法に関する。

コンピュータネットワーク上で、動画や音声を特定多数のユーザに配送するマルチキャスト通信が注目を集めている。この通信方式は、経路の始点と選択された１つ以上の終点を結ぶ経路のうち、経路が分かれる部分において情報をコピーし、各終点へと情報を配送する。特定多数の終点と始点とを１対１で通信を行うユニキャスト通信を用いて情報を配送した場合、終点の数だけ始点は情報を用意する必要がある。よって、マルチキャスト通信を用いることにより、ネットワーク内の情報量は減少する。マルチキャスト通信では特定多数の終点をマルチキャストグループと呼ばれる管理単位で管理し、マルチキャストグループに対して１つの転送経路が設定される。この転送経路は始点からマルチキャストグループに属する全ての終点を接続するように設定される。また、あるマルチキャストグループへと転送される情報を取得したいユーザは、マルチキャストグループに参加することで情報を取得する。このため、ユーザの参加状況に応じて転送経路は変化する。

マルチキャスト通信を用いるアプリケーションとして、テレビ会議やオンラインゲーム、映画やテレビ等の動画配送があげられる。このうち、テレビ会議ではデータ転送遅延が重要な性能項目となる。通常行われる会話では、音声が相手に届くまでの遅延が１００ｍｓ以下である場合、違和感なく会話ができることが分かっている。このため、これらのアプリケーションを使用してサービスを提供する際、顧客が満足するサービスを提供するためには、ある一定値以下の遅延を実現することが重要となる。このようなサービスを提供する手段として、始点から終点までのデータの転送経路を選択する際、アプリケーションが要求する遅延条件を満たす経路を選択する方法が存在する。

また、マルチキャスト通信における経路計算において、経路全体のコストを小さくすることが、ネットワーク管理者の作業の軽減や経路使用者が支払う経路使用料の観点から要求される。このため、テレビ会議などのサービスを実現する際には、遅延条件を満たしつつ、経路全体のコストを小さくすることを目的としたアルゴリズムが要求される。このような経路選択アルゴリズムをDelay constrained multicast algorithmと呼ぶ。近年、このような遅延に厳しいアプリケーションを提供するために、Delay constrained multicast algorithm の実現方法に注目が集まっている（例えば、下記非特許文献１、２参照）。

現在提案されている方式のうち、遅延条件を満たすコストの小さい経路を計算することで経路全体のコストを削減するという観点で優れている方式がある。この方式は以下のような手続を実行する。

(1) 始点と各終点を結ぶ最短経路を計算する。

(2) 計算された経路の中に存在する、始点、終点、経路の分岐点のうち、同種の２点間、もしくは異種の２点間を接続し、経路の中間点として始点、終点、経路の分岐点を含まない経路の中で、最も２点間のコストが大きいものを選択し、削除する。

(3) 削除した結果、２分割された経路木Ｔ１とＴ２が生成される。ここで、Ｔ１は始点を含む部分経路木、Ｔ２はそれ以外の部分経路木とする。

(4) ２つの経路木に属する任意の点を端点とし、始点、終点間で被る遅延が予め提示してある条件を満たす経路を削除した経路の補完経路として計算し、そのうち最もコストの小さいものを経路木に追加する。

(5) 続いて、次にコストの大きい項目(2)記載の経路を探索する。

(6) すべての経路の補完経路を探索し終わるまで(2)〜(5)の手続を繰り返す。

この技術をテレビ会議などのサービス実現時に適用することで、ある上限値以下の転送遅延を実現する転送経路を計算することが可能となる（例えば、非特許文献２参照）。

しかしながら、上記の遅延条件を満たすコストの小さい経路を計算することで経路全体のコストの削減を図る技術では、以下のような問題がある。当該技術では、計算に必要な時間が大きいことが報告されている。

また、当該技術は、リンクの上りと下りの遅延が同じであるとの想定のもとに計算を実行する。通常、ネットワーク内のリンクで被る遅延は方向によって異なる。従来技術をこのような状況に対応できるように拡張するには、次のような動作が必要となる。

（１）補完経路追加時に補完経路の終点（部分木Ｔ２内に存在する）からＴ２に存在する終点までの経路の再計算を実行。

（２）再計算結果に対し、始点−終点間で被る遅延値を計算し、遅延条件を満たすことを確認。条件を満たさない場合次にコストの小さい経路を選択し、（１）の処理を行う。

また、再計算の実施に伴い、変更前の経路では、遅延条件を満たしていない終点が変更後条件を満たさなくなるという事例が多く発生することが予想される。この事態による経路の再計算などの問題が生じるため、より計算時間が大きくなることが予想される。

迅速なサービスの提供を実現するためには、経路設定を短時間で行うことが求められる。しかし、上記の従来の方式を採用した場合、経路計算に多くの時間を消費するため、サービス開時間に遅延が生じる。

一方、上記マルチキャスト通信経路設定技術により計算された経路設定に基づきマルチキャスト転送経路を設定する技術として、ＭＰＬＳ（マルチプロトコルラベルスイッチング）を用いることができる。例えば、ＭＰＬＳによるポイント・ツー・マルチポイント（point-to-multipoint）のラベルスイッチング経路を設定し、ラベルスイッチング転送するものがある（例えば、非特許文献３参照）。

また、ＭＰＬＳを用いたＶＰＮ内でマルチキャスト転送を可能にする技術として、図２３に示すような技術がある。同図に示す例では、ＶＰＮサイト内のＰＩＭ（Protocol Independent Multicast)インスタンスとプロバイダネットワーク内のＰＩＭインスタンスを区別する。ＰＥルータには、収容するＶＰＮサイト毎にＰＩＭインスタンスをハンドリングするＶＲＦテーブルを具備する。さらに、プロバイダネットワーク側にはプロバイダネットワーク共通のＰＩＭインスタンスを具備する（例えば、非特許文献４参照）。

しかしながら、従来のＭＰＬＳを用いてマルチキャスト配信経路を設定する技術は、ＭＰＬＳによるポイント・ツー・マルチポイントのラベルスイッチング経路を設定し、ラベルスイッチング転送することは可能であるが、設定されるラベルスイッチング経路は、一階層のポイント・ツー・マルチポイントのラベルスイッチング経路であるため、当該ラベルスイッチング経路を用いてラベルスイッチされる入力トラヒックは、全て同一の宛先に転送される。つまり、ラベルスイッチング経路を構成する全リーフノードまでラベル転送される。図２４に当該技術の問題を示す。同図の例では、プロバイダエッジルータＰＥ＃１よりプロバイダエッジルータＰＥ＃２，３，４に第一階層のマルチキャストＬＳＰ（Label Switched Path）が設定されている。このため、プロバイダエッジルータＰＥ＃１が収容するカスタマエッジルータＣＥ＃Ａ１，Ｂ１，Ｃ１のトラヒックは、プロバイダエッジルータＰＥ＃２，３，４配下の各ブループの視聴状態に関わらず同一のトポロジで転送されてしまう。これは、ネットワークの転送効率の観点から考えると、不要なポイントにマルチキャストトラヒックを転送することに相当するので望ましくない。例えば、プロバイダエッジルータＰＥ＃２配下にはＣ１グループの受信者が存在しないが、Ｃ１グループのトラヒックを配信することにより、ネットワークリソースの過剰利用を引き起こしている。

このように、当該技術を用いたラベルスイッチングは、ポイント・ツー・マルチポイントと同一の転送トポロジのラベル転送を実現する。このため、設定したポイント・ツー・マルチポイントのラベルスイッチＬＳＰを共有し、ラベルスイッチＬＳＰを構成するリーフノードグループの部分集合であるサブグループにマルチキャスト配信しようとすると、サブグループを構成するリーフノード以外にもマルチキャストラベル転送されてしまい、部分マルチキャスト転送できない問題が生じる。

さらに、ＭＰＬＳのＶＰＮ上でマルチキャスト転送を実現する技術では、プロバイダネットワーク内にＰＩＭ−ＳＭマルチキャストルーティングプロトコルの実装を要求する。図２３に示すＶＰＮマルチキャスト技術では、ＶＰＮサイト内のＰＩＭインスタンスとプロバイダネットワーク内のＰＩＭインスタンスを区別する。ＰＥルータには、収容するＶＰＮサイト毎にＰＩＭインスタンスをハンドリングするＶＲＦテーブルを具備する。

さらに、プロバイダネットワーク側には、プロバイダネットワーク共通のＰＩＭインスタンスを具備する。このとき、プロバイダネットワークのＰＥルータ間にＶＰＮサイト毎にマルチキャスト配信経路を、ランデブーポイントを用いて形成する。図２３の例では、ＶＰＮ＃ＡとＶＰＮ＃Ｂのマルチキャスト経路が設定されている。ＰＩＭ−ＳＭ（Protocol Independent Multicast Sparse Mode）は広く知られているように、ＩＰマルチキャストルーティングプロトコルであり、マルチキャスト配信を実現する場合にランデブーポイントを要求するため、ランデブーポイントが単一障害ポイントとなり信頼性に欠ける点、さらに、ＩＰマルチキャストルーティングプロトコルであるため、プロバイダネットワークにマルチキャスト配信経路を設定するものの、ＱｏＳ（Quality of Service）を確保したパスの設定、トラヒックに応じたパス経路設定ができないため、ネットワークのエンド・エンドで厳密なＱｏＳ保証、トラヒックエンジニアリングが実現できない問題が生じる。

さらに、プロバイダネットワーク内のＰルータ（プロバイダルータ）にマルチキャスト状態（（Ｓ，Ｇ），(＊，Ｇ））のハンドリングを要求する、ＰＩＭ−ＳＭはマルチキャストトラヒックの視聴状態に応じてマルチキャストの経路上でマルチキャスト状態を頻繁に変更するため、プロバイダコアの高速Ｐルータにこのような頻繁な状態変化を高頻度で要求するため、ネットワーク全体としてスケールしない課題がある。

さらに、ＶＰＮ毎マルチキャスト経路を設定するため、プロバイダネットワーク内のマルチキャストコネクション数が増大する問題、さらに、マルチキャストコネクション内でのトラヒック配信パターンを制御できないため、ＶＰＮサイト内に複数のマルチキャストトラヒックが存在する場合には、不要なトラヒックを受信者がいないＶＰＮサイトにも配送してしまう問題がある。
V. Kompella 他、"Multicast routing for multimedia communication"IEEE/ACM Transactions on Networking, Volume: 1 Issue: 3, pp. 286-292, June 1993 Q. Zhu, 他、 "A source-based algorithm for delay-constrained minimum-cost multicasting" proc in IEEE INFOCOM '95, vol. 1, pp. 377-385, 1995 http://www.ietf.org/internet-draft/draft-yasukawa-mpls-rsvp-multicast-01.txt （Extended RSVP-TE for Multicast LSP Tunnels） IETF http://www.ietf.org/internet-draft/draft-rosen-vpn-mcast-04.txt （Multicast in MPLS/BGP VPNs） IETF

本発明は、マルチキャストラベルスイッチング経路内のリーフノードの異なる部分集合を構成するサブリーフグループ毎にマルチキャスト配信が可能になる、マルチキャストラベルスイッチング方法を提供することを目的とする。

さらなる本発明の目的は、仮想閉域網内でプロバイダエッジルータ間に共有マルチキャスト経路を設定しながらも、仮想閉域網内のトラヒックパターンに応じて最適なマルチキャスト配信を実現するマルチキャストラベルスイッチング方法を提供することである。

本発明の一態様によるマルチキャストラベルスイッチング方法は、マルチキャスト通信ネットワークにおいて、マルチキャストソースノードからマルチキャストリーフのグループノードにマルチキャスト配信用のラベルスイッチング経路を設定するマルチキャストラベルスイッチング方法において、
前記ソースノードから全てのリーフノードにポイント・ツー・マルチポイントの第一階層のラベルスイッチング経路を設定し、
設定されたポイント・ツー・マルチポイントの前記第一階層のラベルスイッチング経路のリーフノードグループより任意の宛先リーフノードを抽出した複数のサブグループに対して、該サブグループ毎に第二階層のラベルで前記第一階層のラベルスイッチング経路の部分ツリーを構成する複数の第二階層のラベルスイッチング経路を設定し、
階層化された前記第一階層のラベルスイッチング経路と前記第二階層のラベルスイッチング経路を用いてラベルスイッチングするときに、
入力側のラベルエッジルータは、前記第二階層のラベルに対応した宛先リーフグループ宛の宛先アドレスを持つトラヒックに対応する階層化ラベルを割り当て、付与し、
中継ラベルスイッチルータは、第一階層、第二階層のラベルペアに応じて、パケットをラベルスイッチし、
中継ノードは、前記第一階層のラベルスイッチング経路の分岐ノードとして指定される場合には、前記トラヒックを出力分岐毎にコピーし、その入力ラベルペアを複数の出力分岐に対応する出力ラベルペアに置き換え、
出力ラベルエッジルータは、入力されたトラヒックを階層化ラベルのグループを判定しながら、ラベル除去しながら出力ラインにスイッチングし、
ポイント・ツー・マルチポイントのラベルスイッチング経路内の、第一階層のリーフグループノードのうち、異なる宛先サブグループを構成する第一階層の部分ツリーを構成する複数の第二階層のポイント・ツー・マルチポイントのラベルスイッチング経路を用いて、前記第一階層のラベルスイッチング経路を共有しながら、第二階層のサブグループ毎にトラヒックをラベルスイッチングする。

上記のように、本発明は、マルチキャストラベルスイッチング経路を設定するときに、階層化ラベルを用いて、第一階層ラベルで共有マルチキャストラベルスイッチング経路を設定し、下位階層でサブグループ宛の部分マルチキャストラベルスイッチング経路を複数設定する点、さらに、中継ノードが階層化ラベルを判定して、階層化ラベル全体でラベルスイッチングする点を特徴とする。従来の技術では、マルチキャスト転送時には、階層化ラベルの技術が具備されても、同一トポロジですべてのリーフにマルチキャスト転送されてしまう点、階層化ラベルがあった場合には、第一階層のみラベルスイッチング情報として利用され、第二階層以下のラベルは分岐ポイントでラベル値を変更することなしに、コピーされてしまう点において大きく異なる。

また、本発明は、ＶＰＮマルチキャストに関しては、第一階層ラベルをRFC2547bisアーキテクチャと同様にＰＥルータ間を接続するための共有ポイント・ツー・マルチポイントのラベルスイッチパスのラベルスイッチ用に利用する点、第二階層のラベルをＰＥルータが収容するＶＰＮサイト用のラベルスイッチに利用する点、第三階層をＶＰＮサイト内のトラヒッククラスを区別するためのラベルスイッチに利用する点を主要な特徴とする。従来の技術とは、共有マルチキャストラベルスイッチングパスを用いることでプロバイダネットワーク内に効率的にマルチキャスト配信経路を設定している点、さらに設定マルチキャスト配信経路によりＶＰＮサイト内のトラヒック条件に合わせて最適な配信経路でマルチキャスト転送が可能なため、プロバイダネットワーク内に不要なマルチキャストコピートラヒックを発生することなく効率的なネットワーク運用が可能な点が異なる。

このように、本発明では、個々のマルチキャストトラヒックの宛先グループ、ＱｏＳ要求条件に応じて最適な共有マルチキャスト通信経路を設定することが可能となる。さらに、ネットワーク全体で帯域を有効活用できるので高性能なマルチキャスト配信ネットワーク、ＶＰＮネットワークを構築することが可能となる。

本発明のその他の目的、特徴、長所は、図面を参照して以下の詳細な説明を読めば明らかとなるであろう。

図１は、本発明の原理を説明するための図である。

本発明は、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されるマルチキャストネットワークにおいて、与えられた始点と複数の終点とをそれぞれ結ぶマルチキャスト転送経路をマルチキャスト転送経路計算装置により計算し、計算されたマルチキャスト転送経路をマルチキャスト経路設定装置が設定するマルチキャスト転送経路設定方法である。図１を参照して、各ステップについて説明する。

マルチキャスト転送装置は、マルチキャストネットワーク内のリンク毎に、かつ該リンクにデータが流れる際の進行方向毎にトラヒックの状態を計測する（ステップ１）。そして、計測結果をマルチキャスト転送経路計算装置に送信することにより、マルチキャスト転送経路計算装置にマルチキャスト転送経路の計算依頼を行う（ステップ２）。

マルチキャスト転送経路計算装置は、マルチキャスト転送装置から計算依頼として取得した計測結果に基づいて、始点と複数の終点を結ぶ最短経路を計算し（ステップ３）、最短経路上の任意のノードから各終点までの遅延を計算し（ステップ４）、計算した値を記憶媒体に記録する（ステップ５）。マルチキャスト転送経路計算装置は、その後、計算された最短経路上をデータが流れるときの最大遅延を計算し（ステップ６）、計算した最大遅延を予め与えられた遅延条件と比較する（ステップ７）。もし予め与えられた遅延条件に合わない場合には、該遅延条件を再設定する。もし最短経路に合致する条件が見つかった場合には、計算された最短経路において、始点と終点と経路の分岐点との３種類の異なる種類のいずれか２つのノード、もしくは同種の２つのノードを端点とし、かつ途中に、該３種類のノードを含まない任意の部分経路群から両端の２つのノード間のコストが最も大きい経路を検索し（ステップ８）、検索された該経路を該最短経路から削除して（ステップ９）、マルチキャスト転送経路を２つの経路木に分割する（ステップ１０）。そして別に計算された経路を該２つの経路木を結ぶために削除対象となった経路の補完経路として設定し（ステップ１１）、計算結果をマルチキャスト転送経路設定装置に通知する（ステップ１２）。

マルチキャスト転送経路設定装置は、受け付けた計算結果に従い、マルチキャスト転送経路を設定する（ステップ１３）。

図２は、本発明の原理構成図である。本発明に係る、マルチキャストネットワークにおけるマルチキャスト転送経路計算装置は、以下の手段を有する：マルチキャストネットワークにおけるトラヒック状態の計測結果を受信する計測結果受信手段１３０、受信した計測結果を記憶する計測情報記憶手段１１２、計測結果を計測情報記憶手段１１２に格納する計測結果格納手段１１１、計測結果を計測情報記憶手段１１２から読み取り、該計測結果に基づいて経路計算を行う経路計算手段１２０。

経路計算手段１２０は、さらに以下の手段を有する：始点と複数の終点を結ぶ最短経路を計算し、同時に、経路上の任意のノードから各終点までの遅延を計算し、計算した値を記憶媒体１２２に記録する最短経路遅延計算手段１２１１、計算された最短経路上をデータが流れるときの最大遅延を計算する最大遅延計算手段１２１２、最大遅延を予め与えられた遅延条件と比較し、該遅延条件に合わない場合には、該遅延条件を再設定し、該最短経路に合致する条件が見つかった場合には、最短経路計算手段１２１１で計算された該最短経路において、始点と終点と経路の分岐点との３種類の異なる種類のいずれか２つのノード、もしくは同種の２つのノードを端点とし、かつ途中に、該３種類のノードを含まない任意の部分経路群から両端の２つのノード間のコストが最も大きい経路を検索する最大コスト経路検索手段１２１３、検索された経路を該最短経路から削除して、マルチキャスト転送経路を２つの経路木に分割する経路木分割手段１２１４、及び別に計算された経路を該２つの経路木を結ぶために削除対象となった経路の補完経路として設定する補完経路計算手段１２１５。

以下、図面と共に本発明の実施の形態を説明する。

図３は、本発明の一実施の形態における概要を説明するための図である。なお、同図中の（）内の番号と以下の説明の番号は対応するものとする。

本発明は、始点から終点まで転送される際に被る遅延値に上限値が存在する場合のマルチキャストネットワーク内のマルチキャスト転送経路設定方法である。そして、当該マルチキャストネットワークは、マルチキャスト転送装置３００が設けられた複数のノードにより構成されており、また、各ノードのいずれかのノードにマルチキャスト転送経路計算装置１００または、マルチキャスト転送経路設定装置２００が設けられている。

そして、ネットワーク内のマルチキャスト転送装置３００が、各リンクで発生するデータ転送遅延などを示すネットワーク計測情報をデータが流れる方向毎に収集し（１）、そして、マルチキャスト転送装置３００がマルチキャスト転送経路計算装置１００やマルチキャスト転送経路設定装置２００にネットワーク計測情報を通知する（２）。そして、マルチキャストにより転送するデータの転送経路の設定の必然性が生じたときに、マルチキャスト転送経路設定装置２００とマルチキャスト転送経路計算装置１００によって後述する処理に従い、データの転送経路の設定が実行される。

本発明においては、マルチキャスト転送装置３００は、ノード間で転送されるデータのネットワーク計測情報を収集する機能を有し、マルチキャスト転送経路計算装置１００は、転送経路を計算する機能を有し、マルチキャスト転送経路設定装置２００は、転送経路を設定する機能を有する。また、１つのノードが複数の上述した装置の機能を有している場合もある。

ここで、マルチキャスト転送経路設定装置２００とマルチキャスト転送経路計算装置１００が異なる装置である場合には、マルチキャスト転送経路設定装置２００がマルチキャスト転送経路計算装置１００への転送経路計算を依頼する（３）。マルチキャスト転送経路計算装置１００は、自身の経路計算モジュールに経路計算を指示する（４）。また、マルチキャスト転送経路設定装置２００とマルチキャスト転送経路計算装置１００が同一装置である場合、マルチキャスト転送経路設定装置２００が自身の経路計算モジュールに経路計算を指示する（４）。そして、マルチキャスト転送経路設定装置２００もしくは、マルチキャスト転送経路計算装置１００の経路計算モジュールが、収集した情報をもとに転送経路を計算する（５）。そして計算結果は、マルチキャスト転送経路設定装置２００の経路設定モジュールに通知され（６）、当該計算結果を受信したマルチキャスト転送経路設定装置２００がデータのマルチキャスト転送経路を設定する。なお、上述のネットワーク計測情報を収集する機能においては、すでに提案されているＯＳＰＦ−ＴＥ（Open Shortest Path First-Traffic Engineering)や、ＩＳ−ＩＳ−ＴＥ（Intermediate System-Intermediate System-Traffic Engineering）などの隣接ノード間でのネットワーク計測情報を交換する機能が備わった経路計算プロトコルを拡張して用いることにより、ネットワーク計測情報を収集する。

また、マルチキャスト転送経路計算装置１００は、マルチキャスト転送装置３００からネットワーク計測情報を受信する機能と、かつ転送経路の計算結果を送信するパケット転送機能と、経路計算に使用するアルゴリズムを実現するプログラム、ネットワーク計測情報や経路計算プログラムや経路計算結果を保存する記憶媒体と、並びに、経路計算を実行する経路計算機能とにより構成される。

また、本発明で使用する経路計算プログラムは、転送経路の始点から各終点までの最短経路を計算する機能と、最短経路の経路を行う手順の中で計算される経路上の点から各終点までの最短遅延を計算する機能と、最短経路を構成する経路のうち、始点、終点、経路の分岐点のいずれかを端点とし、経路の中間点に始点、終点、経路の分岐点を含まない一続きの経路から最大のコストを有する経路を検索する機能と、検索結果となる経路を削除し、削除された経路を補完する経路として、経路の終点が削除された経路の終点であり、経路の始点が、削除された経路の始点を含む最短経路の部分木を構成する任意のノードのうち最もコストの小さいものを選択する機能を有する。

上記の機能により、本発明では、補完経路の終点を削除対象の経路の終点に固定することで、最短経路の部分木のうち削除対象の経路の終点を根とする部分木の形状を変更することなく、マルチキャスト転送経路を作成することが可能である。

さらに、本発明では、補完経路を木全体のコスト削減に有効である選択基準に従い選択することで、従来広く用いられている始点と終点間の最短経路を転送経路に採用していたマルチキャスト転送経路計算装置に比べて、経路のコスト削減に有効である。また、本発明では、既存のネットワーク内のトラヒック状態を示すネットワーク計測情報の収集機能を利用するだけで、容易に転送経路の計算をすることが可能となる。そして、ネットワーク計測情報をマルチキャスト転送経路計算装置１００が取得することは容易であり、転送経路計算のために必要なネットワーク計測情報を収集するために新たなプロトコルの開発を必要としないという利点がある。

次に、本発明のマルチキャスト転送経路設定方式を実現するために必要なマルチキャスト転送経路計算装置１００とマルチキャスト転送経路設定装置２００について説明する。

図４は、本発明の一実施の形態におけるマルチキャスト転送経路計算装置１００の構成を示す。同図に示すマルチキャスト転送経路計算装置１００は、ネットワーク内のノードや各ノードをつなぐリンクで発生する遅延やコストに関するネットワーク計測情報を管理する情報管理部１１０と、転送経路を計算する経路計算部１２０と、送受信するパケットを処理するパケット処理部１３０より構成される。そして、マルチキャスト転送経路計算装置１００のパケット処理部１３０が、情報管理部１１０で管理されるネットワーク計測情報や経路計算依頼の受信や、経路計算部１２０が計算した転送経路の計算結果のマルチキャスト転送経路設定装置２００への送信を行う。

情報管理部１１０は、プロトコルを処理するルーティングプロトコルモジュール１１１と、そのプロトコルによって得られたネットワークのトポロジや遅延、コストなどのネットワーク計測情報を管理する計測情報記憶部１１２とを備えている。

また、経路計算部１２０は、転送経路を計算する経路計算モジュール１２１と、計算結果を記憶する計算結果記憶部１２２とを備えている。

また、パケット処理部１３０は、到着したパケットの種別を判断し、そのパケットを転送、または情報管理部１１０に送るパケット処理モジュール１３１とパケット転送先を記録するパケット転送テーブル記憶部１３２と、一または複数のネットワークインタフェース１３３とを備えている。

図５は、本発明の一実施の形態におけるマルチキャスト転送経路設定装置の構成を示す。

同図において、マルチキャスト転送経路設定装置２００は、ネットワーク内のノードやリンクで発生する遅延やコストに関する情報を管理する情報管理部２１０と、自身の処理により発生する遅延やコストなどを測定する測定部２２０と、新たなデータフローが発生したときに経路設定を行う経路設定用プロトコル処理部２３０と、到着したパケットを処理するパケット処理部２４０により構成される。

そして、情報管理部２１０の基本構成は、マルチキャスト転送経路計算装置１００の情報管理部１１０と同様であり、ルーティングプロトコルモジュール２１１と、計測情報記憶部２１２を備えている。

また、測定部２２０は、パケット処理部２４０が備えるネットワークインタフェース２４３（後述する）の状態や、ネットワーク上の各ノードの処理の遅延などの情報を測定する測定モジュールを備えている。

パケット処理部２４０は、到着したパケットの種別を判断し、パケットの転送を行い、また、新規の経路設定の決定を判断するパケット処理モジュール２４１と、パケットの転送先を記録するパケット転送テーブル記憶部２４２と、ネットワークインタフェース２４３を備えている。

また、マルチキャスト転送経路設定装置２００は、経路計算部２５０を備えており、経路計算部２５０は、転送経路を計算する計算処理モジュール２５１と、計算結果を記憶する計算結果記憶部２５２とを備えている。なお、転送経路の計算をマルチキャスト転送経路設定装置２００が行う場合には、この経路計算部２５０がマルチキャスト転送経路計算装置１００と同様の処理を行う。

経路設定用プロトコル処理部２３０は、パケット処理部２４０から経路設定依頼を受信し、その経路設定依頼のマルチキャスト転送経路計算装置１００への送信処理を行う。また、経路設定用プロトコル処理部２３０は、マルチキャスト転送経路計算装置１００から受信した転送経路の計算結果に従ってデータ転送のための転送経路を設定する機能を有する。

なお、マルチキャスト転送経路計算装置１００とマルチキャスト転送経路設定装置２００が同一ノードである場合には、そのノードは、マルチキャスト転送経路計算装置１００とマルチキャスト転送経路設定装置２００の各処理部を有し、上述の各処理を行う。また、マルチキャスト転送装置３００の機能が同一のノードに備えられる場合には、経路設定用プロトコル処理部２３０は、隣接するノードに対して経路計算依頼を行う。

次に、上記のマルチキャスト転送経路計算装置１００、マルチキャスト転送経路設定装置２００、マルチキャスト転送装置３００の動作を説明する。

ネットワーク内のマルチキャスト転送装置３００の機能を有するノードは、常にネットワークのトポロジや遅延やコストを表すネットワーク計測情報を隣接ノード間で交換する。そして、各ノードは、その交換処理によって得られたネットワーク計測情報を記憶する。

ノードが交換するネットワーク計測情報は、次ノードで計測したネットワーク計測情報のみならず、自ノードが保持する他ノードが計測したネットワーク計測情報も含む。これらの交換動作により、各ノードは、ネットワーク内の全ノードにおける接続情報や遅延などのネットワーク計測情報を保持する。そして、新たに転送経路を設定するマルチキャスト転送経路設定装置２００の機能を有するノードは、マルチキャスト転送経路計算装置１００の機能を有するノードに経路計算依頼をする。このとき、マルチキャスト転送経路計算装置１００の機能を有するノードは、情報管理部１１０で管理されているネットワーク内のトポロジや遅延などトラヒックに関するネットワーク計測情報と、経路計算依頼をしたノードから送られてきた終点の情報に基づいて転送経路を計算する。

図６は、本発明の一実施の形態における転送経路計算アルゴリズムのフローチャートである。

まず、マルチキャスト転送経路設定装置２００の機能を有するノードからの経路計算依頼をマルチキャスト転送経路計算装置１００が受け付ける。このとき、マルチキャスト転送経路計算装置１００は、マルチキャスト転送経路設定装置２００からデータ転送の終点の情報も受け付ける。すると、マルチキャスト転送経路計算装置１００の経路計算部１２０が情報管理部１１０の計測情報記憶部１１２（データベース）に記録されているネットワークのトポロジやトラヒック状態を示すネットワーク計測情報を読み取る（ステップ１０１）。

そして、経路計算モジュール１２１がネットワーク計測情報を用いて、データ転送の始点と終点までの遅延が最も小さい遅延最小経路を計算する（ステップ１０２）。このとき、経路計算モジュール１２１は、経路計算依頼を送信したノードを始点とし、データ転送の終点のノードまでの遅延最小経路を計算する。なお、遅延最小経路の計算には、ダイクストラのアルゴリズムを用いる。これより、経路計算依頼を発行したノードと各終点までの遅延最小経路が算出される。

次に、マルチキャスト転送経路計算装置１００の経路計算モジュール１２１は、ステップ１０２で求めた始点から終点までの遅延最小経路を構成するノードのうち、始点と、各終点と、経路の分岐点と、のいずれかに挟まれ、かつ途中に前述の３種類のノードを含まない部分経路を検索する（ステップ１０３）。

そして、計算された部分経路のうち、部分経路を構成するリンクのコストが最も大きい経路を選択し、これを前述の遅延最小経路から削除する。このとき、削除対象となる経路の終点の情報を計算結果記憶部１２２に記録する（ステップ１０４）。このとき、前述の遅延最小経路は２つの部分経路に分割される。次に、マルチキャスト転送経路計算装置１００の経路計算モジュール１２１は、擬似的な始点と、擬似的な始点から前述の分割された部分経路のうち、遅延最小経路の始点を含む部分経路に含まれるすべてのノードへとつながるリンクと、を情報管理部１１０の計測情報記憶部１１２に記録されているネットワークのトポロジに追加する。この後、前述の分割された部分経路のうち、始点を含まない部分経路が通過するリンクとノード、並びに当該ノードに接続されるすべてのリンクを前述のトポロジから削除する。但し、削除対象となる前述の部分経路の始点となるノード、並びに、当該ノードと部分経路を構成しないノードを結ぶリンクは、ネットワークトポロジからの削除対象としないものとする（ステップ１０５）。

次に、擬似的な始点と遅延最小経路の始点を含まない部分経路の始点を結ぶ経路を検索する。このとき、経路の検索のために、k-th shortest path algorithm と呼ばれる、最小遅延を実現する経路から数えてｋ番目に小さい遅延を実現する経路を計算するアルゴリズムを適用する。この種類のアルゴリズムは、ｋ−１番目に小さい経路を検索した後、ｋ番目に小さい経路の検索を行う。よって、許容する遅延の上限値を設け、上限値を下回る経路が全て発見されるまで該当アルゴリズムを実行することが可能となる。このようにして検索された経路は削除された経路を補完する経路の候補となる（ステップ１０６）。

次に、マルチキャスト転送経路計算装置１００の経路計算モジュール１２１は、k-th shortest path algorithmによって検索された経路のうち、経路を構成するリンクが保持するコストの経路全体の総和を計算し、最もコストが小さい経路を選択する。選択された経路は削除された経路を補完するために新たに経路として選択される（ステップ１０７）。

最後に、マルチキャスト転送経路計算装置１００の経路計算モジュール１２１は、上記のステップ１０３からステップ１０７までの動作を削除対象の経路と選択された補完経路が同一経路となるか判断する。同一経路となる場合、次にコストの大きい経路を探索し、すべての探索経路において、補完経路が探索経路と同一経路となるまで繰り返す（ステップ１０８）。

このようにして計算した結果を、経路計算モジュール１２１は、パケット処理部１３０を介して経路計算依頼を発行したノードに返送する（ステップ１０９）。

なお、本実施の形態では、マルチキャスト転送装置３００が遅延などのネットワーク計測情報を収集する際には、ＯＳＰＦ−ＴＥを用いる。ＯＳＰＦ−ＴＥは、ユニキャストのルーチングプロトコルであるＯＳＰＦのトポロジ情報交換情報に遅延などのネットワーク内のトラヒック情報を格納した通信プロトコルである。

また、本実施の形態では、データの転送を設定するプロトコルとして、明示的な経路指定を実施するＲＳＶＰ−ＴＥ（Resource Reservation Protocol-Traffic Engineering）を拡張したマルチキャストＭＰＬＳ（Multi Protocol Label Switching）プロトコルを使用する。マルチキャストＭＰＬＳは、通常のＭＰＬＳで用いられるＲＳＶＰ−ＴＥに対して、ＬＳＰ（Label Switched Path）を生成するメッセージ中にツリートポロジを格納できる情報要素を追加し、そのトポロジ情報に沿って、Point-to-Multipoint ＬＳＰを確立することができる技術である。

以下、図面と共に本発明の実施例を説明する。

図７は、本発明の一実施例のマルチキャストネットワークを示す。

同図において、２００はデータ転送経路の始点を示し、(1)〜(3)はデータ転送の終点を示す。また、Ａ〜Ｉは始点と終点との間の中間ノードであり、マルチキャスト転送装置３００の機能を有している。なお、マルチキャスト転送経路設定装置２００、ノードＡ〜Ｉ、終点(1)〜(3)の各ノードが通信ケーブル（リンク）により接続されてマルチキャストネットワークを構成している。そして、各リンクは、遅延とコストという２つの特性を持っている。リンクの遅延特性とコスト特性は、データがリンクに進入する際の進入方向によって、異なる遅延特性とコスト特性を有することが認められている。この場合、リンクＤ−Ｅのようにデータが右方向（DからEへ）に移動するときは、遅延特性が１でコスト特性が１０であり、逆方向（EからDへ）に移動するときは遅延特性が１でコスト特性が１となるリンクが存在する。そして、マルチキャスト転送経路設定装置２００は、マルチキャスト転送経路計算装置１００が計算した結果に基づいて、自らを始点として終点(1)〜終点(3)に対してデータを転送する。

なお、各ノード間のリンクで発生する遅延を示すネットワーク計測情報は、前述のＯＳＰＦ−ＴＥを用いて各ノードが収集する。そして、当該ネットワーク計測情報が予めマルチキャスト転送経路計算装置１００に通知される。

マルチキャスト転送経路設定装置２００が遅延の上限値が７である経路を計算する例を示す。

図８は、本発明の一実施例のデータ転送の始点と各終点を結ぶ経路のうち遅延最小経路を示す。

マルチキャスト転送経路計算装置１００は、マルチキャスト転送経路設定装置２００からの経路計算依頼を受けると、まず、始点となるマルチキャスト転送経路設定装置２００から各終点(1)〜終点(3)までの遅延最小経路を計算する。この時、マルチキャスト転送経路計算装置１００は、遅延最小経路の計算アルゴリズムとしてダイクストラのアルゴリズムを用いる。ダイクストラのアルゴリズムは、遅延最小経路を計算するアルゴリズムとしては一般的によく使用される。なお、マルチキャスト転送経路計算装置１００が計算した始点２００から終点(1)、(2)、(3)までの各遅延最小経路は、
・マルチキャスト転送経路設定装置２００→ノードＢ→終点(1)、
・マルチキャスト転送経路設定装置２００→ノードＢ→ノードＤ→ノードＥ→ノードＧ→終点(2)、
・マルチキャスト転送経路設定装置２００→ノードＢ→ノードＤ→ノードＥ→ノードＧ→ノードＨ→終点(3)
である。このとき、始点→終点間で被る遅延の最大値は始点２００と終点(3)を結ぶ経路上で被る遅延であり、その値は６であるため、遅延上限値に関する条件を満たす。

図９は、本発明の一実施例の削除対象経路計算を示す図である。

次に、遅延最小経路を分割した部分経路のうち、両端が始点、終点、経路の分岐点のいずれかのノードであり、かつ、経路の中間ノードに始点、終点、経路の分岐点を含まない経路を検索する。該当する経路は、
・始点２００→ノードＢ（部分経路３１）
・ノードＢ→終点(1)（部分経路３２）
・ノードＢ→ノードD→ノードE→ノードＧ（部分経路３３）
・ノードＧ→終点(2)（部分経路３４）
・ノードＧ→ノードH→終点(3)（部分経路３５）
である。このような経路のうち、経路を構成するリンクが持つコスト特性の総和が最も大きい経路を選択する。始点２００→ノードＢ（部分経路３１）のコストは１、ノードＢ→終点(1)（部分経路３２）のコストは１、ノードＢ→ノードＧ（部分経路３３）のコストは１２、ノードＧ→終点(2)（部分経路３４）のコストは１、ノードＧ→終点(3)（部分経路３５）のコストは２であるため、選択される経路はノードＢ→ノードＧ（部分経路３３）となる。図９は経路の検索結果を示しており、選択された部分経路を遅延最小経路として選択された経路から削除する。その結果、遅延最小経路は２つに分割される。ここで、始点を含む部分経路を４０、含まない経路を５０とする。この様子を図１０に示す。

次に、２つの部分経路４０、５０を結ぶ補完経路を検索する。このとき、補完経路は、部分経路４０に含まれる任意の点を始点とし、削除経路の終点、すなわち部分経路５０の始点を終点とするような経路のうち、部分経路５０に属する点と途中で交わらず、経路を構成するリンクが保持するコスト特性の総和が最も小さいものを選択する。この計算法を以下に示す。

計算に使用するネットワークのトポロジは、計算対象のネットワークに以下のような修正を加えたものを使用する。まず、擬似的な始点７０を用意し、擬似的な始点７０から部分経路４０に属するすべてのノードに対しリンクを追加する。次に、部分経路５０を構成するリンクと部分経路５０の始点Ｇを除いたノード、並びに、当該ノードに接続するすべてのリンクを除去する。この結果、図１１に示すようなトポロジが完成する。

このトポロジに対し、擬似始点７０と部分経路５０の始点Gを結ぶ経路を、k-th shortest path algorithmを用いて計算する。k-th shortest path algorithmとは、遅延最小経路から数えてｋ番目に短い経路を探索するときに使用されるアルゴリズムであり、このような経路を探索するアルゴリズムはすでに提案されている。k-th shortest path algorithmの適用に際し、計算に使用される特性値としては遅延とコストが考えられる。

計算に使用する特性値が遅延である場合、始点と各終点の間に被る遅延が与えられた上限値を下回る間k-th shortest path algorithmを漸化的に適用する。即ち、ｋ−１番目に短い経路を計算した後、計算結果を用いてｋ番目に短い経路を検索する。これらの経路のうち、経路を構成するリンクが保持するコスト特性の各リンクに対する総和が最も小さいものを補完経路として選択する。

計算に使用する特性値がコストである場合、発見されたｋ番目に小さいコストを保持する経路を始点と各終点の間で被る遅延の上限値を初めて下回ったときに計算を終了し、その時点で計算された擬似始点を除く経路を補完経路として選択する。図１２に本実施例における計算結果を示す。擬似始点７０と部分経路５０の始点であるノードＧを結ぶ経路のうち、最もコストの小さい経路は、
擬似始点７０→ノードＢ→ノードＤ→ノードＦ→ノードＥ→ノードＧ
であるため、擬似始点７０を除いた、
ノードＢ→ノードＤ→ノードＦ→ノードＥ→ノードＧ
を補完経路として選択する。

遅延の上限値の評価には、部分経路５０の始点Ｇで記録されているノードＧからノードＧの下流に存在する各終点までに発生する遅延値を使用する。従来の方式では、部分経路５０のトポロジが補完経路の計算の際に変化するため、部分経路５０の再計算の後、新たな部分経路５０の始点から各終点までの遅延を計算する必要があった。本発明では、この作業を省くことで、計算時間を短縮している。遅延の最大値を評価した結果、補完経路接続時に実現される始点→終点間の最大遅延は始点２００と終点(3)を結ぶ経路上で被る遅延７となる。経路が許容する最大遅延が７という条件があるため、この場合遅延条件を満たす。上記の条件を満たす経路を補完経路とし、部分経路４０と部分経路５０を結ぶ経路として採用する。

ここで、アルゴリズムの終了条件について説明する。補完経路が削除された経路と同じ場合、もしくは、削除された経路より遅延が大きい経路である場合、削除された経路が補完経路となり、アルゴリズムを終了する。もし、異なる場合、補完経路に印を付け、両端が始点、終点、経路の分岐点のいずれかのノードであり、かつ、経路の中間ノードに始点、終点、経路の分岐点を含まない経路のうち、印を付けた経路以外でコストが最も大きい経路を選択し、削除の後、補完経路を見つける。この動作をすべての経路に印が付けられるまで繰り返す。このようにして図１３に示すような計算結果が算出される。

なお、上述のマルチキャスト転送経路計算装置やマルチキャスト転送経路設定装置は内部にコンピュータシステムを有している。そして、上述した処理の過程は、プログラムの形式でコンピュータ読み取り可能な記憶媒体に記憶されており、このプログラムをコンピュータが読み出して実行することによって、上記の処理が行われる。ここで、コンピュータ読み取り可能な記憶媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等を指す。また、このコンピュータプログラムを通信回線によってコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしてもよい。また、構築されたプログラムを、マルチキャスト転送経路計算装置として動作するコンピュータに接続されるハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、本発明を実施する際に、ＣＰＵにインストールすることも可能である。

上述のように、本発明によれば、始点と終点間で発生する遅延の上限値を考慮した経路計算アルゴリズムを備えた経路計算用ノードを有するシステムを用いることで、マルチキャスト通信において始点と各終点の間で発生する遅延に上限が存在するようなアプリケーションを提供する際に、遅延条件を満たしつつ経路全体のコストの削減を実現することが可能となる。

また、経路計算の時間を従来方式と比較して短縮することによって、サービスを提供するために必要な時間を短縮することが可能となる。これにより、ユーザに対し、迅速にサービスを提供することが可能となる。

このようなマルチキャスト通信経路設定技術によるマルチキャスト配信（転送）を実現する手段として、マルチキャストラベルスイッチング方法を利用したネットワークがある。以下、図面と共にマルチキャストラベルスイッチング方法に関する本発明の実施の形態を説明する。

最初に、マルチキャストラベルスイッチングの通信経路設定方式とパケット転送メカニズムについて説明する。

図１４は、本発明の一実施の形態における接続ＶＰＮサイト（ＣＥ）を考慮した最適プロバイダエッジ（ＰＥ）ルータ間マルチキャスト配信のパターンを示す。同図の例では、プロバイダネットワーク内に、プロバイダエッジルータＰＥ＃１，ＰＥ＃２，ＰＥ＃３，ＰＥ＃４と、それらとＰＥルータ間を接続するプロバイダ（Ｐ）ルータが存在する。

ＰＥ＃１には、ＶＰＮ＃Ａに所属するＣＥ＃Ａ１と、ＶＰＮ＃Ｂに属するＣＥ＃Ｂ１と、ＶＰＮ＃Ｃに属するＣＥ＃Ｃ１とが収容されている。さらに、ＰＥ＃２には、ＶＰＮ＃Ａに属するＣＥ＃Ａ２と、ＶＰＮ＃Ｂに属するＣＥ＃Ｂ２とが収容される。また、ＰＥ＃３には、ＶＰＮ＃Ａに属するＣＥ＃Ａ３と、ＶＰＮ＃Ｂに属するＣＥ＃Ｂ３と、ＶＰＮ＃Ｃに属するＣＥ＃Ｃ３とが収容される。また、ＰＥ＃４には、ＶＰＮ＃Ｂに属するＣＥ＃Ｂ４と、ＶＰＮ＃Ｃに属するＣＥ＃Ｃ４とが収容される。

このネットワークでＰＥ＃１から他のＰＥルータに送信されるマルチキャストトラヒックの最適な配信パターンを考察する。プロバイダネットワークの見地からは、ＰＥルータ間に複数のマルチキャストラベルスイッチングを設定することは、ラベルの有効利用、転送リソースの観点から望ましくない。そこでＰＥ＃１から、ＰＥ＃２，３，４にすべてのトラヒックで共有されるポイント・ツー・マルチポイントのＬＳＰ（Label Switched Path）を設定する。

この例では、同図中の土管のマークで図示されたパスがＬＳＰに対応する。このとき、各ＰＥルータに収容されるＶＰＮサイト情報を考慮すると、ＰＥルータに収容されるＶＰＮサイトに応じてＶＰＮ毎のサイト接続関係を考慮したＰＥルータ間のマルチキャストラベルスイッチング経路が必要になる。例えば、図１４の例では、ＶＰＮ＃Ａについては、ＰＥ＃２，ＰＥ＃３配下のみサイトが収容されるため、ＰＥ＃１がソース、ＰＥ＃２，３がリーフのマルチキャストサブラベルスイッチング経路が設定されることが望ましい。図１４の例では、破線の矢印で示されるマルチキャスト配信経路がこのマルチキャストサブラベルスイッチング経路に対応する。以下ＶＰＮ＃Ｂについては、一点鎖線の矢印ＶＰＮ＃Ｃについては、実線の矢印が対応する。

この例でもわかるように、プロバイダネットワークのリソースを有効活用し、かつ収容されるＶＰＮサイトに応じたＰＥルータ間の最適マルチキャスト配信を実現するためには、２階層のポイント・ツー・マルチポイントのラベルスイッチングパスの設定が有効である。さらに、第二階層目のラベルスイッチングパスは第一階層のラベルスイッチングパスの部分集合になっていることに注意されたい。

図１４のマルチキャストラベルスイッチングパスを設定するシグナリングメカニズムを図１５に示す。マルチキャストラベルシグナリングは、例えば、既存のＲＳＶＰ−ＴＥ（Resource Reservation Protocol-Traffic Engineering）メカニズムをマルチキャスト拡張して設定される。図１５に示すように設定するマルチキャスト配信回路は、pathメッセージのＴＥＲＯ（Tree Explicit Route Object）により規定される。その具体的なフォーマットをネットワークトポロジに対応させて図１６に示す。

前述したように、本発明では、ＰＥルータ間に最適なマルチキャスト配信経路を設定するために２階層のマルチキャストラベルスイッチングパスを設定する。そのため設定するマルチキャストラベルスイッチングパスの設定経路を示すＴＥＲＯを２階層分用意する。図１６の例では、第一階層のＰＥ＃１（Ａ）からＰＥ＃２（Ｄ），ＰＥ＃３（Ｅ），ＰＥ＃４（Ｇ）に接続するマルチキャストラベルスイッング経路を規定する。ＴＥＲＯは、｛Ａ（０），Ｂ（１），Ｃ（２），Ｄ（３），Ｅ（３），Ｆ（２），Ｇ（３）｝で規定される。この規定方法は、Depth First Order アルゴリズムにより規定される。各ノードに付随する（）内の数値は、ソースノードＰＥ＃１（Ａ）からの距離（ホップ数）を示す。

図１５の例では、図１７に示すような接続構成のマルチキャスト配信経路となっている。Depth First Order アルゴリズムでは初めに深さ方向にパスを指定していくので、ＴＥＲＯの指定は、｛Ａ（０），Ｂ（１），Ｃ（２），Ｄ（３），Ｅ（３），Ｆ（２），Ｇ（３）｝となっている。さらに、この第一階層のマルチキャストＬＳＰの配下にＶＰＮ毎のマルチキャストＬＳＰを設定する。ＶＰＮ＃ＡのサブツリーはＰＥ＃１（Ａ）よりＰＥ＃２（Ｄ）、ＰＥ＃３（Ｅ）のサブツリーで図１８のような構成なので、第二階層のＶＰＮ＃ＡのＴＥＲＯは、
ＴＥＲＯ＝｛Ａ（０），Ｂ（１），Ｃ（２），Ｄ（３），Ｅ（３）｝、
ＶＰＮ＃ＣのＴＥＲＯは、
ＴＥＲＯ＝｛Ａ（０），Ｂ（１），Ｃ（２），Ｅ（３），Ｆ（２），Ｇ（３）｝となる。

このＴＥＲＯ情報により、図１５に示すようにPathメッセージがリーフノードまで伝達される。リーフノードまでPathメッセージが伝達されると、Resvメッセージにより下流から階層化ラベルがアサインされる。

図１９にこの動作で各ノードに設定される、ラベル変換テーブルとリンクで使用される階層化ラベルを示す。例えば、ノードＰＥ＃３（Ｅ）では、ＶＰＮ＃Ａ，Ｂ，Ｃを含む第二階層のＴＥＲＯが全て到達するので、ＣＥ間のリンクでＶＰＮ毎にＡ（１０１，３０），Ｂ（１０１，２５），Ｃ（１０１，５）のラベルが付与される。

さらにＰＥ＃２では、ＶＰＮ＃Ａ，Ｂを含む第二階層のＴＥＲＯしか到達しないので、ＶＰＮ＃Ｃ用のラベルは付与されることなく、リンクＣＤ間ではＡ（１，１），Ｂ（１，２５），Ｃ（１，Ｎｕｌｌ）となる。この情報がノードＣに到達して、ＢＣから入力したラベルパケットのＣＤ，ＣＥリンクへの転送関係がテーブルに設定される。図１９のノードＣのリンクでＶＰＮ＃Ｃ用のＣＤリンクへのラベルが付与されないので、ＣＥリンクのみの（１０１，５）の一つのラベルが設定されていることに注意されたい。

こうしてＶＰＮ＃Ａ，Ｂでは、ＢＣから到達したラベルパケットは必要なラベル交換が実施されてＣＤ，ＣＥに分岐されるが、ＶＰＮ＃ＣのラベルパケットはＣＤに転送されず、ＣＥのみにラベルスイッチングされていく。この操作がホップバイホップに送信ノードＡまで継続し、ＶＰＮ毎に階層化されたラベルスイッチング経路が形成される。こうして、ノードＡに入力されたパケットは、ＶＰＮ毎に階層化ラベルを付与されて中継ノードで階層化ラベルでラベルスイッチングされてリーフノードまでマルチキャスト配信される。

但し、上記のメカニズムだけではＶＰＮ内のマルチキャストトラヒックに対して最適なマルチキャスト経路配信が実現できない。図２０にＰＥ＃１配下のＶＰＮ＃Ｂ内にマルチキャストソースＭ＃Ａ，Ｍ＃Ｂ，Ｍ＃Ｃが存在して、それぞれ異なるマルチキャスト分配パターン（図２０左上）を持つ場合を想定する。この場合、２階層のラベルスイッチ経路ではＶＰＮ＃Ｂが収容される全てのＰＥルータ、ＰＥ＃２，ＰＥ＃３，ＰＥ＃４にＭ＃Ａ，Ｍ＃Ｂ，Ｍ＃Ｃが配信されてしまうので、ネットワーク効率が良くない。例えば、Ｍ＃Ａを受信しないＰＥ＃４にもマルチキャスト配信されてしまう。

このような無駄なマルチキャスト配信を防止するために、更に第三階層目のラベルを付与することも可能である。この例では、このラベルは、同一ＶＰＮサイト内の同一分配トポロジに属するマルチキャストソースグループということになる。

このような帰納的な階層化メカニズムを用いることで任意の配信パターンを実現できる。

次に、上記の実施の形態のマルチキャストラベルスイッチングを具備したＶＰＮマルチキャストスイッチングについて説明する。

ＶＰＮ内でマルチキャストトラヒックを最適なトポロジで配信するために、上記の実施の形態で説明した３階層のラベルスイッチング技術が有効である。

このとき、上記の実施の形態のメカニズムを用いてＶＰＮサイト間を閉域接続するためには、各ＶＰＮ内に収容されるマルチキャスト配信経路情報を、ＰＥルータ間で通常のユニキャスト経路交換と同様に交換する必要が生じる。その例を図２１に示す。同図に示すように、ｒｆｃ２５４７ｂｉｓで規定されているＭＰ−ＢＧＰで経路交換が可能である。図２１の例では、ＰＥ１にその他のＰＥルータが自身の収容するＶＰＮサイト内のマルチキャスト配信経路を配信する例を示す。

例えば、ＰＥ＃４は、ＶＰＮ＃Ａ、Ｂを収容しているので、ＶＰＮ＃Ａのマルチキャスト経路ＭＧ＃αと、ＶＰＮ＃Ｂのマルチキャスト経路ＭＧ＃βをＰＥ１にＭＰ−ＢＧＰを用いて配信している。この例では、一方向の経路交換例を示しているが、ＰＥルータ間で双方向にフルメッシュで経路交換することで、各ＰＥルータは対向するＰＥルータが収容するＶＰＮサイト内のマルチキャスト経路を全て把握可能となる。

このようにして、マルチキャストラベルスイッチング経路設定者である送信ノードが対向するＰＥ内のマルチキャスト経路を意識した階層型のポイント・ツー・マルチポイントのＬＳＰを設定可能となる。図２２に本発明を適用したＶＰＮモデルを示す。本モデルを適用することにより、ＶＰＮサイトアニメーションのＰＩＭ−ＳＭのマルチキャストもＶＰＮ転送可能となる。

上述のように、本発明のマルチキャストラベルスイッチング方法及びＶＰＮマルチキャストラベルスイッチング方法によれば、マルチキャスト配信経路全体の転送コストを抑えながら、宛先受信グループに最適なトポロジでマルチキャスト配信可能なマルチキャスト転送網、ＶＰＮ網が構築できる。

そのため、効率的で高性能なマルチキャスト配信ネットワークを構築できる。

本発明は上記の実施の形態に限定されるものではなく、本発明の技術的範囲を逸脱することなく、様々なバリエーションや変更が可能である。

本発明の原理を説明するための図である。本発明の原理構成図である。本発明の一実施の形態における概要を説明するための図である。本発明の一実施の形態におけるマルチキャスト転送経路計算装置の構成図である。本発明の一実施の形態におけるマルチキャスト転送経路設定装置の構成図である。本発明の一実施の形態における転送経路計算アルゴリズムのフローチャートである。本発明の一実施例の対象ネットワークの一例である。本発明の一実施例のデータ転送の始点と各終点を結ぶ経路のうち遅延最小経路を示す図である。本発明の一実施例の削除対象経路計算を示す図である。本発明の一実施例のコスト最大経路削除後に作成される部分経路を示す図である。本発明の一実施例の補完経路計算用トポロジである。本発明の一実施例の補完経路計算結果を示す図である。本発明の一実施例の経路計算結果を示す図である。本発明の第１の実施の形態における接続ＶＰＮサイト（ＣＥ）を考慮した最適ＰＥルータ間マルチキャスト配信パターンである。本発明の第１の実施の形態における接続ＶＰＮサイト（ＣＥ）を考慮した最適ＰＥルータ間マルチキャストシグナリングである。本発明の第１の実施の形態における接続ＶＰＮサイト（ＣＥ）を考慮した最適ＰＥルータ間マルチキャスト配信接続を実現する階層化ツリー指定シングナリングである。本発明の第１の実施の形態におけるマルチキャスト配信経路の例である。本発明の第１の実施の形態におけるＶＰＮ＃Ａのサブツリーである。本発明の第１の実施の形態における最適ＰＥルータ間マルチキャスト配信接続を実現する階層化ツリー指定シグナリングで指定されるＭＰＬＳラベル交換テーブルである。本発明の第１の実施の形態におけるサイト内のマルチキャストソースの配信パターンを考慮した最適マルチキャスト配信経路設定法を示す図である。本発明の第１の実施の形態におけるＰＥ間のマルチキャスト配信経路交換メカニズムを説明するための図である。本発明を適用したＶＰＮモデルである。従来の技術におけるＶＰＮモデル（Rosen）である。従来のＰＥルータ間のマルチキャストコネクションとＶＰＮサイト内ＣＥへのマルチキャスト転送パターンである。

符号の説明

１１１計測結果格納手段
１１２計測情報記憶手段
１３０計測結果受信手段
１００マルチキャスト転送経路計算装置
２００マルチキャスト転送経路設定装置
３００マルチキャスト転送装置

Claims

マルチキャスト通信ネットワークにおいて、マルチキャストソースノードからマルチキャストリーフのグループノードにマルチキャスト配信用のラベルスイッチング経路を設定するマルチキャストラベルスイッチング方法において、
前記ソースノードから全てのリーフノードにポイント・ツー・マルチポイントの第一階層のラベルスイッチング経路を設定し、
設定されたポイント・ツー・マルチポイントの前記第一階層のラベルスイッチング経路のリーフノードグループより任意の宛先リーフノードを抽出した複数のサブグループに対して、該サブグループ毎に第二階層のラベルで前記第一階層のラベルスイッチング経路の部分ツリーを構成する複数の第二階層のラベルスイッチング経路を設定し、
階層化された前記第一階層のラベルスイッチング経路と前記第二階層のラベルスイッチング経路を用いてラベルスイッチングするときに、
入力ラベルエッジルータは、前記第二階層のラベルに対応した宛先リーフグループ宛の宛先アドレスを持つトラヒックに対応する階層化ラベルを割り当て、付与し、
中継ラベルスイッチルータは、第一階層、第二階層のラベルペアに応じて、パケットをラベルスイッチし、
前記中継ラベルスイッチルータは、前記第一階層のラベルスイッチング経路の分岐ノードとして指定される場合には、前記トラヒックを出力分岐毎にコピーし、その入力ラベルペアを複数の出力分岐に対応する出力ラベルペアに置き換え、
出力ラベルエッジルータは、入力されたトラヒックを階層化ラベルのグループを判定しながら、ラベル除去しながら出力ラインにスイッチングし、
ポイント・ツー・マルチポイントのラベルスイッチング経路内の、第一階層のリーフグループノードのうち、異なる宛先サブグループを構成する第一階層の部分ツリーを構成する複数の第二階層のポイント・ツー・マルチポイントのラベルスイッチング経路を用いて、前記第一階層のラベルスイッチング経路を共有しながら、第二階層のサブグループ毎にトラヒックをラベルスイッチングすることを特徴とするマルチキャストラベルスイッチング方法。
第二階層のマルチキャストラベルスイッチング経路内に、さらに、第二階層のラベルスイッチング経路を構成するリーフノードの部分集合を構成するリーフノード宛に、該第二階層のラベルスイッチング経路の部分トポロジを構成するサブツリーを用いて、第三階層のラベルスイッチング経路として、複数の第三階層ラベルスイッチング経路を備え、
さらに、サブグループ化が必要な場合には、下位階層のラベルスイッチング経路を帰納的に設定し、
帰納的に設定された階層化ラベルスイッチング経路を用いてサブグループ毎にマルチキャストラベルスイッチングを行う請求項１記載のマルチキャストラベルスイッチング方法。
前記請求項１記載のマルチキャストラベルスイッチング方法を、ＭＰＬＳを用いたＶＰＮサービスに適用する際に、
ＶＰＮサイトを収容する全てのプロバイダネットワークのプロバイダエッジルータ間に第一階層のポイント・ツー・マルチポイントのマルチキャストＬＳＰをフルメッシュで接続し、
さらに、前記プロバイダネットワークに収容されるＶＰＮサイト毎に対応して第二階層のマルチキャストラベルスイッチ経路を設定し、
前記第二階層のラベルスイッチ経路を設定する場合には、ＶＰＮを構成するプロバイダエッジルータがマルチキャストラベルスイッチ経路のリーフノードを構成するときに、各リーフに収容される、ＶＰＮサイトに応じて第二階層のラベルスイッチング経路を最適な部分ツリートポロジに調整し、
前記ＶＰＮ内で前記プロバイダエッジルータ間を接続する第一階層のマルチキャストツリー内に第二階層ツリーとして構成する請求項１記載のマルチキャストラベルスイッチング方法。
ＶＰＮサイト内に複数の異なるサイト宛先を持つマルチキャスト配信経路が存在する場合に、
前記第二階層の下位層の第三階層にそれぞれのマルチキャスト配信経路に対応するＶＰＮサイトのみを宛先リーフノードとして第二階層のマルチキャスト配信経路の部分ツリー経路として第三階層のマルチキャスト配信経路を設定し、
前記ＶＰＮの同一ＶＰＮに所属するトラヒックであっても、該ＶＰＮ内でマルチキャストトラヒックの受信を希望するＶＰＮサイトのみにマルチキャストトラヒックを配信する請求項３記載のマルチキャストラベルスイッチング方法。
通信方式をラベルスイッチルータ機能として具備し、
ラベルスイッチルータを、前記入力ラベルエッジルータ、中継ラベルスイッチルータ、または出力ラベルエッジルータとして動作させる請求項１記載のマルチキャストラベルスイッチング方法。