(57)【要約】【課題】  情報の配信元となる始点とその情報の配信先である終点とを結ぶ経路のうち経路が分かれるノードにおいて情報をコピーして各終点へと転送するマルチキャストネットワークにおいて、マルチキャスト転送経路の計算速度の向上を実現し、かつ、経路全体の総メトリックの削減を実現できるようにする。【解決手段】１以上の終点のそれぞれについて、ネットワーク中の他の全てのノードからその終点までの最短メトリック経路を探索し、マルチキャスト転送経路の始点から各終点までの最短メトリック経路を比較して最もメトリックが小さいいずれか一つの終点に至る経路を選択し、選択された経路の各ノードからその経路には含まれない各終点までの最短メトリック経路を調査して最もメトリックが小さい経路をさらに選択し、これを全ての終点までの経路が選択されるまで繰り返す。【選択図】  図４
2005072869.tif 000002
【特許請求の範囲】
【請求項１】
情報の配信元となる始点とその情報の配信先である終点とを結ぶ経路のうち経路が分かれるノードにおいて情報をコピーして各終点へと転送するマルチキャスト転送手段が各ノードに設けられたマルチキャストネットワークにおいて、
与えられた始点と1以上の終点とをそれぞれ結ぶマルチキャスト転送経路を計算する転送経路計算手段と、
この転送経路計算手段にマルチキャスト転送経路の計算を依頼し、その計算結果に基づいてマルチキャスト転送経路を設定する転送経路設定手段と
を備え、
前記転送経路計算手段は、
前記１以上の終点のそれぞれについて、ネットワーク中の他の全てのノードからその終点までの最短メトリック経路を探索する手段と、
マルチキャスト転送経路の始点から各終点までの最短メトリック経路を比較して最もメトリックが小さいいずれか一つの終点に至る経路を選択する手段と、
選択された経路上の各ノードからその経路には含まれない各終点までの最短メトリック経路を調査して最もメトリックが小さい経路をさらに選択し、これを全ての終点までの経路が選択されるまで繰り返す手段と
を含む
ことを特徴とするマルチキャストネットワーク。
【請求項２】
前記探索する手段は、前記他の全てのノードをそれぞれ基点とする最短メトリック経路について、基点のノード、最短メトリック値、およびその経路を通るときの基点のノードの次のノードに関する情報をテーブルとして蓄える手段を含み、
前記繰り返す手段は、この蓄える手段のテーブルを参照して経路を選択する
請求項１記載のマルチキャストネットワーク。
【請求項３】
前記繰り返す手段は、選択された経路上の各ノードをその経路の終点から基点に向けて順番に走査し、ある終点に対して既に計算されたその終点までの最短メトリック経路より小さいまたは等しいメトリック値の経路があった場合にはそれを選択する請求項1記載のマルチキャストネットワーク。
【請求項４】
情報の配信元となる始点とその情報の配信先である１以上の終点とを結ぶ経路を計算するマルチキャスト転送経路計算方法において、
前記１以上の終点のそれぞれについて、ネットワーク中の他の全てのノードからその終点までの最短メトリック経路を探索するステップと、
マルチキャスト転送経路の始点から各終点までの最短メトリック経路を比較して最もメトリックが小さいいずれか一つの終点に至る経路を選択するステップと、
選択された経路の各ノードからその経路には含まれない各終点までの最短メトリック経路を調査して最もメトリックが小さい経路をさらに選択し、これを全ての終点までの経路が選択されるまで繰り返すステップと
を含むことを特徴とするマルチキャスト転送経路計算方法。
【請求項５】
前記探索するステップでは、前記他の全てのノードをそれぞれ基点とする最短メトリック経路について、基点のノード、最短メトリック値、およびその経路を通るときの基点のノードの次のノードに関する情報をテーブルとして蓄え、
前記繰り返すステップでは、このテーブルを参照して経路を選択する
請求項４記載のマルチキャスト転送経路計算方法。
【請求項６】
前記繰り返すステップでは、選択された経路上の各ノードをその経路の終点から基点に向けて順番に走査し、ある終点に対して既に計算されたその終点までの最短メトリック経路より小さいまたは等しいメトリック値の経路があった場合にはそれを選択する請求項４記載のマルチキャスト転送経路計算方法。
【請求項７】
請求項４ないし６のいずれか記載のマルチキャスト転送経路計算方法をコンピュータに実行させるためのマルチキャスト転送経路計算プログラム。
【請求項８】
コンピュータに、
終点ごとに、その終点に向けて、ネットワーク中の他の点から設定される経路のうち、経路の総メトリックが最も小さい経路を探索する機能と、
探索結果を、基点のノード、最短メトリック値および最短メトリック経路を通るときの基点のノードの次のノードに関する情報を、ネットワーク中の全ノードに対し、ノードごとに記録する機能と、
計算結果として確定しているノードから各終点までの最短メトリック経路を検出する機能と、
発見された最短メトリック経路のメトリックと基点を記憶する機能と、
終点ごとに調査した最短経路を比較し、その中での最短メトリック経路を計算結果に追加する機能と、
計算結果として選択されたノードから、各終点に向けて設定される経路のうち、メトリックが最小となる経路のメトリック値と、その経路の基点となる、計算結果として選択されたノードの情報とを記憶する機能と、
記憶された終点ごとのメトリック値を比較し、メトリックが最短となる経路を発見する機能と、
発見された経路を計算結果の一部として選択する機能と、
その経路を選択する際、経路上のノードを終点から始点に向けて走査する機能と、
操作中のノードから経路の一部として選ばれていない終点まで結ぶ最短メトリック経路を計算結果として選択された経路上のノードを走査し、計算結果の一部として選ばれていないマルチキャスト転送経路の終点までの最短メトリック経路を前記全ノードから各終点までの最短メトリック経路が記載された情報領域を参照することで調査する機能と、
終点ごとに記録された最短メトリック情報と調査した経路のメトリック情報とを比較する機能と、
前記調査した経路のメトリックが前記記録された最短メトリック情報より小さいときには前記記録された最短メトリック情報を前記調査した経路のメトリックで上書きし、かつ、調査した経路の基点をその経路の基点となる計算結果として選択されたノードの情報部分に上書きする機能と、
走査が終了した後に、終点ごとに記録した最短メトリック情報を終点間で比較し、選択済みの経路からのメトリックが最小となる終点を探索する機能と、
発見された終点に関連付けられた、その終点にむけて設定される、選択済みの転送経路からの最短メトリック経路を新たに計算結果の一部として選択する機能と、
選択された経路を前述の動作と同様に終点からその経路の始点に向けて走査、ならびにまだ選択されていない終点までの最短メトリック経路を調査する機能と、
これらの動作の繰り返しを選択されていないマルチキャスト経路の終点が存在しなくなるまで繰り返す機能と
を実現させるためのマルチキャスト転送経路計算プログラム。
【請求項９】
請求項7または８記載のマルチキャスト転送経路計算プログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報の配信元となる始点とその情報の配信先である終点とを結ぶ経路のうち経路が分かれるノードにおいて情報をコピーして各終点へと転送するマルチキャスト通信に関する。特に、与えられた始点と1以上の終点とをそれぞれ結ぶ最適なマルチキャスト転送経路を求める技術に関する。
【背景技術】
【０００２】
コンピュータネットワーク上で動画や音声を特定多数のユーザに配送する方式として、マルチキャスト通信が注目を集めている。この通信方式では、経路の始点と選択された１つ以上の終点とを結ぶ経路のうち、経路が分かれる部分において情報をコピーし、各終点へと情報を配送する。特定多数の終点へ始点と一対一で通信を行うユニキャスト通信を用いて情報を配送した場合には、終点の数だけ始点は情報を用意する必要がある。これに対して、マルチキャスト通信を用いることで、ネットワーク内の情報量が減少する。
【０００３】
マルチキャスト通信では、特定多数の終点をマルチキャストグループと呼ばれる管理単位で管理を行い、マルチキャストグループに対して１つの転送経路が設定される。この転送経路は、始点からマルチキャストグループに属するすべての終点を接続するように設定される。また、あるマルチキャストグループヘと転送される情報を取得したいユーザは、マルチキャストグループに参加すればよい。このため、転送経路はユーザの参加状況に応じて変化する。
【０００４】
マルチキャスト通信における転送経路は、リンクに与えられたメトリックと呼ばれる指標を用いて決定される。メトリックは、ネットワーク管理者のネットワーク設計方針に従って決定される。経路計算を行うアルゴリズムもまた、設計方針に従い選択される。多くの種類のアルゴリズムが存在し、代表的なものとしては、経路の始点から終点までのメトリックの総和を最小にするアルゴリズムと、経路を構成するリンクにつけられたメトリックの総和を最小にするアルゴリズムとがある。本発明は後者のアルゴリズムに属する。
【０００５】
経路を構成するリンクにつけられたメトリックの総和を最小にするアルゴリズムにはまた、２種類のアルゴリズムが存在する。１つは、ネットワーク中の全ノードを通る経路のうち、経路の総メトリック量が最も小さい経路を探索するアルゴリズムであり、最小木探索アルゴリズムと呼ばれる。もう１つは、ネットワーク中の特定のノードを通る経路のうち、経路の総メトリック量が最も小さい経路を探索するアルゴリズムである。このようなアルゴリズムはシュタイナー木計算アルゴリズムと呼ばれ、このような経路はシュタイナー木と呼ばれる。マルチキャスト経路計算には主にシュタイナー木計算アルゴリズムが使用される。最小木計算アルゴリズムは高速に経路計算を行うことが可能であるが、シュタイナー木計算アルゴリズムは有限時間内に解を出すことが非常に困難であることが証明されている。このため、有限時間内にシュタイナー木が実現する総メトリック値に近い値を実現するアルゴリズムが多く提案されている。
【０００６】
シュタイナー木計算アルゴリズムとして、例えば、下記の非特許文献１、２に示されたものがある。非特許文献１に示されたアルゴリズムは、高速なシュタイナー木計算アルゴリズムとして知られる。また、非特許文献２に記載されたアルゴリズムは、シユタイナー木計算アルゴリズムであるが、経路の始点から終点まで到達するのに必要とする遅延が制限されている経路を計算するアルゴリズムである。
【０００７】
経路の総メトリックの削減度という観点で両アルゴリズムを比較すると、非特許文献２のアルゴリズムは、始点終点間の遅延制限をとりはずすにつれ、非特許文献１のアルゴリズムより有効になる。しかし、非特許文献２の方式は非常に計算時間が大きくなるため、経路計算など短時間で解を出すことを要求するアプリケーションに適用することは困難となる。ここで、非特許文献１のアルゴリズムに注目する。
【０００８】
非特許文献１で紹介されている方式の動作について概略を説明する。非特許文献１では、シュタイナー木を計算するために以下の手続きを実行する。
１．始点と全終点を含んだノード集合Ｄを定義し、Ｄ中に存在するノード間を結ぶ経路のうち、総メトリックが最小の経路を探索する。
２．探索された経路を枝とし、Ｄ中のノードを点とする架空のメッシュ状のネットワークを構成する。枝のメトリックは１．で発見されたＤ中に存在するノード間を結ぶ経路の総メトリックとなる。
３．２．で構成されたネットワークに対し、最小木を探索する。前述の通り、最小木計算アルゴリズムは高速に動作するため、この動作は有限時間内に終了する。
４．３．で選ばれた総メトリック最小経路に相当する実ネットワーク内の経路を計算結果とする。
【０００９】
この技術をネットワーク中の経路計算に利用することで、収容トラヒツク量の増加などネットワーク管理者が定めた設計方針に従ってトラヒックの流れを決定することが可能となる。
【００１０】
【非特許文献１】L. Kou, G. Markowsky, and L.Berman, "A fast Algorithm for Steiner Tree", Acta Informatica. pp.141-145, 1981
【非特許文献２】Q. Zhu et al., "Asource-based algorithm for delay-constrained minimum-cost multicasting"
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上記の非特許文献１で紹介されている技術では、以下のような問題がある。
【００１２】
非特許文献１で紹介されている技術は高速にシュタイナー木の近似解を計算するが、総メトリックの削減度としては、改良の余地が存在する。それは、架空ネットワーク上での全ノードを結ぶ総メトリック最小経路を探索する過程で問題があるためである。
【００１３】
総メトリック最小経路計算の際、架空ネットワーク上のノードにつけられるメトリックは、経路決定の過程において、変わることはない。このため、すでに経路の一部として選択されているノードが実ネットワークにおいて付近に存在する場合も、近隣の送信者、終点から設定された経路を計算結果として採用する。このように、選択できる経路が制限されているため、コストの削減効果は非常に不十分なものとなる。
【００１４】
本発明は上記の点を鑑みてなされたもので、マルチキャスト転送経路の計算速度の向上を実現し、かつ、経路全体の総メトリックの削減を実現できることを目的とする。
【課題を解決するための手段】
【００１５】
本発明の第一の観点によると、情報の配信元となる始点とその情報の配信先である終点とを結ぶ経路のうち経路が分かれるノードにおいて情報をコピーして各終点へと転送するマルチキャスト転送手段が各ノードに設けられたマルチキャストネットワークにおいて、与えられた始点と1以上の終点とをそれぞれ結ぶマルチキャスト転送経路を計算する転送経路計算手段と、この転送経路計算手段にマルチキャスト転送経路の計算を依頼し、その計算結果に基づいてマルチキャスト転送経路を設定する転送経路設定手段とを備え、前記転送経路計算手段は、前記１以上の終点のそれぞれについて、ネットワーク中の他の全てのノードからその終点までの最短メトリック経路を探索する手段と、マルチキャスト転送経路の始点から各終点までの最短メトリック経路を比較して最もメトリックが小さいいずれか一つの終点に至る経路を選択する手段と、選択された経路上の各ノードからその経路には含まれない各終点までの最短メトリック経路を調査して最もメトリックが小さい経路をさらに選択し、これを全ての終点までの経路が選択されるまで繰り返す手段とを含むことを特徴とするマルチキャストネットワークが提供される（請求項１）。
【００１６】
前記探索する手段は、前記他の全てのノードをそれぞれ基点とする最短メトリック経路について、基点のノード、最短メトリック値、およびその経路を通るときの基点のノードの次のノードに関する情報をテーブルとして蓄える手段を含み、前記繰り返す手段は、この蓄える手段のテーブルを参照して経路を選択することが望ましい（請求項２）。
【００１７】
また、前記繰り返す手段は、選択された経路上の各ノードをその経路の終点から基点に向けて順番に走査し、ある終点に対して既に計算されたその終点までの最短メトリック経路より小さいまたは等しいメトリック値の経路があった場合にはそれを選択することが望ましい（請求項３）。
【００１８】
本発明の第二の観点によると、情報の配信元となる始点とその情報の配信先である１以上の終点とを結ぶ経路を計算するマルチキャスト転送経路計算方法において、前記１以上の終点のそれぞれについて、ネットワーク中の他の全てのノードからその終点までの最短メトリック経路を探索するステップと、マルチキャスト転送経路の始点から各終点までの最短メトリック経路を比較して最もメトリックが小さいいずれか一つの終点に至る経路を選択するステップと、選択された経路の各ノードからその経路には含まれない各終点までの最短メトリック経路を調査して最もメトリックが小さい経路をさらに選択し、これを全ての終点までの経路が選択されるまで繰り返すステップとを含むことを特徴とするマルチキャスト転送経路計算方法が提供される（請求項４）。
【００１９】
前記探索するステップでは、前記他の全てのノードをそれぞれ基点とする最短メトリック経路について、基点のノード、最短メトリック値、およびその経路を通るときの基点のノードの次のノードに関する情報をテーブルとして蓄え、前記繰り返すステップでは、このテーブルを参照して経路を選択することが望ましい（請求項５）。
【００２０】
また、前記繰り返すステップでは、選択された経路上の各ノードをその経路の終点から基点に向けて順番に走査し、ある終点に対して既に計算されたその終点までの最短メトリック経路より小さいまたは等しいメトリック値の経路があった場合にはそれを選択することが望ましい（請求項４）。
【００２１】
本発明の第三の観点によると、以上のマルチキャスト転送経路計算方法をコンピュータに実行させるためのマルチキャスト転送経路計算プログラムが提供される（請求項５）。
【００２２】
本発明の第四の観点によると、コンピュータに、終点ごとに、その終点に向けて、ネットワーク中の他の点から設定される経路のうち、経路の総メトリックが最も小さい経路を探索する機能と、探索結果を、基点のノード、最短メトリック値および最短メトリック経路を通るときの基点のノードの次のノードに関する情報を、ネットワーク中の全ノードに対し、ノードごとに記録する機能と、計算結果として確定しているノードから各終点までの最短メトリック経路を検出する機能と、発見された最短メトリック経路のメトリックと基点を記憶する機能と、終点ごとに調査した最短経路を比較し、その中での最短メトリック経路を計算結果に追加する機能と、計算結果として選択されたノードから、各終点に向けて設定される経路のうち、メトリックが最小となる経路のメトリック値と、その経路の基点となる、計算結果として選択されたノードの情報とを記憶する機能と、記憶された終点ごとのメトリック値を比較し、メトリックが最短となる経路を発見する機能と、発見された経路を計算結果の一部として選択する機能と、その経路を選択する際、経路上のノードを終点から始点に向けて走査する機能と、操作中のノードから経路の一部として選ばれていない終点まで結ぶ最短メトリック経路を計算結果として選択された経路上のノードを走査し、計算結果の一部として選ばれていないマルチキャスト転送経路の終点までの最短メトリック経路を前記全ノードから各終点までの最短メトリック経路が記載された情報領域を参照することで調査する機能と、終点ごとに記録された最短メトリック情報と調査した経路のメトリック情報とを比較する機能と、前記調査した経路のメトリックが前記記録された最短メトリック情報より小さいときには前記記録された最短メトリック情報を前記調査した経路のメトリックで上書きし、かつ、調査した経路の基点をその経路の基点となる計算結果として選択されたノードの情報部分に上書きする機能と、走査が終了した後に、終点ごとに記録した最短メトリック情報を終点間で比較し、選択済みの経路からのメトリックが最小となる終点を探索する機能と、発見された終点に関連付けられた、その終点にむけて設定される、選択済みの転送経路からの最短メトリック経路を新たに計算結果の一部として選択する機能と、選択された経路を前述の動作と同様に終点からその経路の始点に向けて走査、ならびにまだ選択されていない終点までの最短メトリック経路を調査する機能と、これらの動作の繰り返しを選択されていないマルチキャスト経路の終点が存在しなくなるまで繰り返す機能とを実現させるためのマルチキャスト転送経路計算プログラムが提供される（請求項８）。
【００２３】
本発明ではさらに、本発明の第三または第四の観点のマルチキャスト転送経路計算プログラムが記録されたコンピュータ読み取り可能な記録媒体が提供される（請求項９）。
【発明の効果】
【００２４】
本発明によれば、始点と終点間で発生する遅延の上限値を考慮した経路計算アルゴリズムを備えた経路計算用ノードを有するシステムを用いることで、短時間で、かつ高い精度を保持したシュタイナー木の近似解を可能となる。また、経路計算の時間を従来方式と比較して短縮することによって、サービスを提供するために必要な時間を短縮することが可能となる。これにより、ユーザに対し迅速にサービスを提供することが可能となる。
【発明を実施するための最良の形態】
【００２５】
本発明の一実施形態を図面を参殿して説明する。
【００２６】
図１は本発明の槻要を説明する図である。マルチキャスネットワーク内の各ノードにはマルチキャスト転送装置１０を備え、情報の配信元となる始点とその情報の配信先である1以上の終点とを結ぶ経路のうち経路が分かれるノードにおいて情報をコピーして各終点へと転送する。また、マルチキャストネットワーク内のいずれかのノードには、与えられた始点と複数の終点とをそれぞれ結ぶマルチキャスト転送経路を計算するマルチネャスト転送経路計算装置２０を備え、また、その同じノードまたは別のノードに、マルチキャスト転送経路計算装置２０にマルチキャスト転送経路の計算を依頼し、その計算結果に基づいてマルチキャスト転送経路を設定するマルチキャスト転送経路設定装置３０を備える。マルチネャスト転送経路の計算は、シュタイナー木計算アルゴリズムにより行う。
【００２７】
ネットワーク内の各マルチキャスト転送装置１０は、ネットワーク内で被る遅延やコスト情報、各リンクの残余帯域などのネットワーク計測情報をデータが流れる方向ごとに収集し、それをマルチキャスト転送経路計算装置２０に通知する。そして、マルチキャストにより転送するデータの転送経路の設定の必要が生じたときに、マルチキャスト転送経路設定装置３０とマルチキャスト転送経路計算装置２０とによって、後述の処理に従い、データの転送経路の設定が実行される。
【００２８】
ここではマルチキャスト転送装置１０、マルチキャスト転送経路計算装置２０およびマルチキャスト転送経路設定装置３０が別々のノードに設けられるものとして説明するが、これらの各装置をひとつのノードに設けることもできる。
【００２９】
マルチキャスト転送経路の設定の必要が生じると、マルチキャスト転送経路設定装置３０がマルチキャスト転送経路計算装置２０へ転送経路の計算を依頼する。マルチキャスト転送経路計算装置２０は、収集した情報をもとに転送経路を計算し、その結果をマルチキャスト転送経路設定装置３０に通知する。マルチキャスト転送経路設定装置３０は、計算結果を受信し、データのマルチキャスト転送経路を設定する。
【００３０】
ネットワーク計測情報の収集は、すでに提案されているＯＳＰＦ（Open
Shortest Path First-Traffic Engineering）やＩＳ−ＩＳ−ＴＥ（Intermediate
system-Intermediate system-traffic Engineering）などの隣接ノード間でのネットワーク計測情報を交換する機能が備わった経路計算プロトコルを拡張して用いることにより行う。収集されたネットワーク情報は記憶媒体に蓄えられる。
【００３１】
次に、マルチキャスト転送経路計算装置２０およびマルチキャスト転送経路設定装置３０の詳細について説明する。
【００３２】
図２はマルチキャスト転送経路計算装置２０の構成例を示すブロック図である。このマルチキャスト転送経路計算装置２０は、ネットワーク内のノードや各ノードをつなぐリンクで発生する遅延やメトリックに関するネットワーク計測情報を管理する情報管理部２１と、転送経路を計算する経路計算部２２と、送受信するパケットを処理するパケット処理部２３とにより構成される。そして、パケット処理部２３が、情報管理部２１で管理されるネットワーク計測情報や経路計算依頼の受信、および経路計算部２２が計算した転送経路の計算結果のマルチキャスト転送経路設定装置３０への送信を行う。
【００３３】
情報管理部２１は、トラヒック状態の情報の収集に使用するＯＳＰＦやＩＳ−ＩＳなどのルーチングプロトコルで使用される情報交換プロトコルを処理するルーチングプロトコルモジュール２１１と、そのプロトコルによって得られたネットワークのトポロジや遅延、メトリックなどのネットワーク計測情報を管理する計測情報記憶部２１２とを備える。経路計算部２２は、転送経路を計算する経路計算モジュール２２１と、計算結果を記憶する計算結果記憶部２２２とを備える。パケット処理部２３は、到着したパケットの種別を判断し、そのパケットを転送、または情報管理部２１に送るパケット転送処理モジュール２３１と、パケットの転送先を記録するパケット転送テーブル記憶部２３２と、ネットワークインタフェース２３３とを備える。
【００３４】
図３はマルチキャスト転送経路設定装置３０の構成例を示すブロック図である。このマルチキャスト転送経路設定装置３０は、ネットワーク内のノードやリンクで発生する遅延やメトリックに関する情報を管理する情報管理部３１と、自身の処理により発生する遅延やメトリックなどを測定する測定部３２と、新たなデータフローが発生したときに経路設定を行う経路設定用プロトコル処理部３３と、到着したパケットを処理するパケット処理部３４とにより構成される。
【００３５】
情報管理部３１の基本構成はマルチキャスト転送経路計算装置２０の情報管理部２１と同様であり、ルーチングプロトコルモジュール３１１と、計測情報記憶部３１２とを備える。測定部３２は、パケット処理部３４が備えるネットワークインタフェース３４３の状態や、ネットワーク上の各ノードの処理の遅延などの情報を測定する測定モジュールを備えている。パケット処理部３４は、到着したパケットの種別を判断し、パケットの転送を行い、また新規の経路設定の決定を判断するパケット処理モジュール３４１と、パケットの転送先を記録するパケット転送テーブル記憶部３４２と、ネットワークインタフェース３４３とを備える。
【００３６】
図３にはまた、マルチキャスト転送経路計算装置２０をマルチキャスト転送経路設定装置３０と同じノードに設ける場合の構成についても示す。装置２０、３０を同一ノードに設ける場合には、情報管理部２１、３１およびパケット処理部２３、３４をそれぞれ共通化し、マルチキャスト転送経路設定装置３０内に経路計算部２２と同等の経路計算部３５を設ける。この経路計算部３５は、転送経路を計算する経路計算モジュール３５１と、計算結果を記憶する計算結果記憶部３５２とを備える。
【００３７】
経路設定用プロトコル処理部３３はパケット処理部３４から経路設定依頼を受信し、その経路設定依頼のマルチキャスト転送経路計算装置２０への送信処理を行う。また経路設定用プロトコル処理部３３は、マルチキャスト転送経路計算装置２０から受信した転送経路の計算結果にしたがって、データ転送のための転送経路を設定する。
【００３８】
なお、マルチキャスト転送装置１０の機能がマルチキャスト転送経路設定装置３０と同一ノードに設けられる場合には、経路設定用プロトコル処理部３３は、隣接するノードに対して経路計算依頼を行う。
【００３９】
次に、マルチキャスト転送装置１０、マルチキャスト転送経路計算装置２０およびマルチキャスト転送経路設定装置３０の動作について詳しく説明する。
【００４０】
ネットワーク内のマルチキャスト転送装置１０の機能を有するノードは、常に、ネットワークのトポロジや遅延やメトリックを現すネットワーク計測情報を隣接ノード間で交換する。そして各ノードは、その交換の処理によって得られたネットワーク計測情報を記憶する。
【００４１】
ノードが交換するネットワーク計測情報は、次ノードで計測したネットワーク計測情報のみならず、自ノードが保持する他ノードが計測したネットワーク計測情報も含む。これらの交換動作により、各ノードはネットワーク内の全ノードにおける接続情報や遅延などのネットワーク計測情報を保持する。そして、新たに転送経路を設定するマルチキャスト転送経路設定装置３０の機能を有するノードは、マルチキャスト転送経路計算装置２０の機能を有するノードに経路計算を依頼する。このとき、マルチキャスト転送経路計算装置２０の機能を有するノードは、情報管理部２１で管理されているネットワーク内のトポロジや遅延などトラヒックに関するネットワーク計測情報と、経路計算依頼をしたノードから送られてきた終点の情報に基づいて、転送経路を計算する。
【００４２】
図４はマルチキャスト転送経路計算装置２０における経路計算の処理を示すフローチャートである。
【００４３】
マルチキャスト転送経路計算装置２０は、マルチキャスト転送経路設定装置３０の機能を有するノードからの経路計算依頼を受け付け、このとき、マルチキャスト転送経路設定装置３０からデータ転送の終点の情報も受け取る。これにより、マルチキャスト転送経路計算装置２０では、経路計算部２２内の経路計算モジュール２２１が、情報管理部２１の計測情報記憶部２１２に記録されているネットワークのトポロジやトラヒツク状態を示すネットワーク計測情報、もしくはそれらの情報を基に、ネットワーク管理者のネットワーク設計指針に従うよう計算されたメトリツクを読み取る（ステップＳ１）。
【００４４】
次に経路計算モジュール２２１は、マルチキャスト転送経路の終点ごとに、転送経路の計算結果として確定しているノードと調査中の終点との間の経路のうち最短メトリックを実現する経路のメトリックと、その経路の基点となる計算結果として確定したノードとを計算結果記憶部２２２に記録する。そして、これらの情報を用いて、ネットワーク上の全ノードからマルチキャスト転送経路の終点となるノードまでの最短メトリック経路を、マルチキャスト転送経路の終点ごとに探索する。計算された結果は個々のマルチキャスト転送経路の終点に特化した情報として保持される（ステップＳ２）。この最短経路計算は、ネットワーク中の２点間の最短メトリック経路を計算するアルゴリズムを使用し、アルゴリズムの種類は問わないものとする。
【００４５】
次に経路計算モジュール２２１は、経路の始点を基点とし、マルチキャスト転送経路の各終点までの最短メトリック経路を各終点間で比較し、最もメトリックの小さい経路を計算結果として選択し、ノードとリンクの情報を計算結果記憶部２２２に記憶する。（ステップＳ３）。
【００４６】
続いて経路計算モジュール２２１は、選択された経路を終点から始点の方向に走査する。このとき、走査中のノードから、まだ経路として選択されていない終点までの最短メトリック経路を、先に計算した全ノードから各終点までの最短メトリック経路情報を参照して、探索する。このとき、各終点に関連付けられた情報である転送経路の計算結果として確定しているノードと該終点の間の経路のうち、最短メトリックを実現する経路のメトリックと、探索された経路のメトリック値とを比較し、前者の方が大きければ前者の情報を後者の情報で上書きする。このとき、走査中のノードの情報が追加候補経路となる、その終点までの最短メトリック経路の基点として記録する（ステップＳ５）。
【００４７】
そして、各終点が保持する既に経路として選択されたノードからの最短メトリックを実現する経路のメトリック情報を、各終点間で比較する。この中で最もメトリックが小さい経路を計算結果の一部として新たに追加する。この経路の基点は、マルチキャスト転送経路の各終点が保持するその終点までの最短メトリック経路の基点情報内に記載されている基点となる（ステップＳ６）。
【００４８】
その後、ステップＳ５に戻る。ステップＳ５とＳ６は経路として選ばれていない終点が存在しなくなるまで繰り返される（ステップＳ４９）。
【００４９】
経路計算部２２は、このようにして計算した結果を、パケット処理部２３を介して、経路計算依頼を出したノードに返送する。
【００５０】
なお、本実施例において、マルチキャスト転送装置が遅延などのネットワーク計測情報を収集する際には、ＯＳＰＦ−ＴＥを用いる。ＯＳＰＦ−ＴＥはユニキャストのルーチングプロトコルであるＯＳＰＦのトポロジ情報交換情報に遅延などのネットワーク内のトラヒック情報を格納した通信プロトコルである。
【００５１】
また、本実施例では、データの転送経路を設定するプロトコルとして、明示的な経路指定を実施するＲＳＶＰ−ＴＥ（Resource Reservation Protocol-Traffic Engineering）を拡張したマルチキャストＭＰＬＳ（Multi
Protocol Label Switching）プロトコルを使用する。マルチキャストＭＰＬＳは、通常のＭＰＬＳで用いられるＲＳＶＰ−ＴＥに対して、ＬＳＰ（Label
Switched Path）を生成するメッセージ中にツリートポロジを格納できる情報要素を追加し、そのトポロジ情報に沿ってPoint-to-Multipoint
LSPを確立することができる技術である。
【００５２】
次に、本発明による転送経路を計算する処理の具体的な実施例について説明する。
【００５３】
図５は転送経路設定の対象となるマルチキャストネットワークを示し、図６ないし図１２は転送経路計算の各段階を示す。これらの図において、マルチキャスト転送経路設定装置３０の機能を有するノードがデータ転送経路の始点となり、終点１１〜１３のノードにデータが転送され、ノードＡ〜Ｋが始点と終点との間の中間ノードとなる。これらのノードはそれぞれ、マルチキャスト転送装置１０の機能を有している。
【００５４】
この実施例において、マルチキャスト転送経路設定装置３０、ノードＡ〜Ｋおよび終点１１〜１３が通信ケーブル（リンク）により接続されて、マルチキャストネットワークを構成する。各リンクは遅延とメトリックという２つの経路選択指標を持ち、データがリンクに進入する際の進入方向によって、異なる遅延特性とメトリック特性を有することが認められている。マルチキャスト転送経路設定装置３０は、マルチキャスト転送経路計算装置２０が計算した結果に基づいて、自らを始点として終点１１〜１３に対してデータを転送する。各ノード間のリンクで発生する遅延を示すネットワーク計測情報については、前述のＯＳＰＦ−ＴＥを用いて各ノードが収集する。そして当該ネットワーク計測情報があらかじめマルチキャスト転送経路計算装置２０に通知される。
【００５５】
本発明によるマルチキャスト転送経路の計算例を図６ないし図１２を参照して説明する。
【００５６】
まず、本発明では、マルチキャスト転送経路の終点１〜３毎に、ネットワーク中の全ノードから各終点の方向へ設定される最短メトリック経路を計算する。この最短メトリック経路計算には、２点間の最短経路を計算するアルゴリズムとして有名なダイクストラのアルゴリズムを用いることができる。
【００５７】
図６に、計算された最短メトリック経路を示す。経路Ｘは終点１までの最短メトリック経路であり、経路Ｙは終点２までの最短メトリック経路であり、経路Ｚは終点３までの最短メトリック経路である。
【００５８】
最短メトリック経路計算と同時に、各終点は、他のノードからの最短メトリックを記録するテーブルを作成する。テーブル４０は終点１１までの最短メトリック情報を示し、テーブル４１は終点１２までの最短メトリック情報を示し、テーブル４２は終点１３までの最短メトリック情報を示す。これらのテーブルには、ネットワーク中のノード、対象ノードからの最短メトリック値、および最短メトリック経路を通るときの対象ノードの次の点、が記載される。
【００５９】
図７に、各終点が保持する確定経路からの最短メトリックおよび最短メトリック経路の基点の初期情報を示し、さらに、最初に計算結果の一部が選択される動作を示す。アルゴリズム開始時に、図６中で計算した全ノードから各終点までの最短メトリック値を参照し、マルチキャスト転送経路の始点（マルチキャスト転送経路設定装置３０、以下「始点３０」という）からの最短メトリック経路を探索する。そして、各終点が保持する確定経路上のノードからの最短メトリックおよび最短メトリック経路の基点の情報として、始点３０からの最短メトリック経路のメトリック値と、その基点である始点３０の情報とを終点ごとに記憶する。情報５０〜５２はそれぞれ、終点１１〜１３が保持する前述の２つの情報を示す。
【００６０】
次に、記憶した前述の情報のうち、確定経路上のノードからの最短メトリックの値が最も小さい終点を選択し、始点３０から選ばれた終点までの経路を計算結果の一部として選択する。図７では終点１１までと終点１３までの最短メトリック値が同じ「４」となるが、ここでは、終点１１の方を選択する。これより、経路３０−Ａ−Ｄ−Ｆ−１１が計算結果として選択される。
【００６１】
次に、選択された経路を、経路の終点から始点の方向に走査する。走査の過程で、まだ計算結果の一部として選ばれていない終点までの最短メトリック値を計算する。
【００６２】
図８に経路の走査過程を示す。この例では、まず終点１１を走査し、次にノードＦ、Ｄ、Ａ、始点３０の順番に走査を行う。
【００６３】
終点１１に着目する。ここで、終点１１からまだ計算結果として選択されていない終点１２、１３までの最短メトリック値を、先に作成したテーブル４１、４２から調査する。このとき、終点１１から終点１２までのメトリック値は「４」で、終点１１から終点１３までのメトリック値は「４」となる。一方、終点１２、１３が管理しているメトリック値はそれぞれ「６」、「４」であり、新たに計算されたメトリック値と同じか大きい値が格納されていることになる。この場合には、終点１２、１３の保持している情報を更新する。これにより、終点１２の保持している情報は、計算結果の一部のノードから終点１２までの最短メトリックが「４」、最短メトリック経路の基点情報が「終点１１」に更新される。同様に終点１３の保持している情報は、計算結果の一部のノードから終点１３までの最短メトリックが「４」に、最短メトリック経路の基点情報が「終点１１」に更新される。
【００６４】
続いてノードＦに着目する。ここで、ノードＦからまだ計算結果として選択されていない終点１２、１３までの最短メトリック値を、先に作成したテーブル４１、４２から調査する。このとき、ノードＦから終点１２までのメトリック値は「３」で、ノードＦからノード１３までのメトリック値は「３」となる。このとき、終点１２、１３が管理している計算結果の一部からのメトリック値はそれぞれ「４」、「４」であり、新たに計算されたメトリック値と同じか大きい値が格納されていることから、これらの情報を更新する。この時点で、終点１２が保持する計算結果の一部のノードから終点１２までの最短メトリックは「３」に、最短メトリック経路の基点情報は「ノードＦ」に更新される。同様に、終点１３が保持する計算結果の一部のノードから終点１３までの最短メトリックは「３」に、最短メトリック経路の基点情報は「ノードＦ」に更新される。
【００６５】
続いてノードＤに着目する。ここで、ノードＤからまだ計算結果として選択されていない終点１２、１３までの最短メトリック値を、先に作成したテーブル４１、４２から調査する。このとき、ノードＤから終点１２までのメトリック値は「４」で、ノードＦから終点１３までのメトリック値は「２」となる。このとき、終点１２、１３が管理している計算結果の一部からのメトリック値はそれぞれ「３」、「３」であるが、終点１３にのみ新たに計算されたメトリック値と同じか大きい値が格納されているため、終点１３特有の情報を更新する。この時点で、終点１２が保持する計算結果の一部のノードから終点１２までの最短メトリックは「３」、最短メトリック経路の基点情報は「ノードＦ」のままである。これに対し、終点１３が保持する計算結果の一部のノードから終点１３までの最短メトリックは「２」、最短メトリック経路の基点情報は「ノードＤ」と更新される。
【００６６】
ノードＡと始点３０に注目した場合は、終点１２に関してはノードＦから経路を拡張する場合と比較し、終点３に関してはノードＤから経路を拡張する場合に比べて、それぞれ大きなメトリックが必要となる。このため、終点１２、１３が保持する情報は更新しない。
【００６７】
図９に走査の終了時点の状況を示す。ここで、終点１２と終点１３に関して、計算結果の一部のノードからそれぞれの終点までの最短メトリックの値を比較し、最も値の小さい値が関連付けられている終点を計算経路の一部として次に追加する。そして、選ばれた終点に関連付けられた最短メトリック経路の基点情報に記載されている計算結果の一部のノードからその終点までの経路を、計算結果の一部として追加する。
【００６８】
図９に示した例では、終点１２に関連づけられた最短メトリック値は「４」であるのに対し、終点１３に関連づけられた値は「２」となる。したがって、次に計算結果の一部として選ばれる終点は、終点１３である。同時に、終点１３に関連付けられた最短メトリック経路の基点情報に記載されているノードＤから終点１３に至る最短メトリック経路Ｄ−Ｅ−１３も計算結果の一部として追加される。
【００６９】
選択された最短メトリック経路Ｄ−Ｅ−１３を計算結果に追加する際、まだ計算結果の一部として選ばれていない終点までの最短メトリック値を計算する。走査は、図８における走査と同様に、終点から最短メトリック経路の基点に向けて行われる。
【００７０】
図１０に経路の走査過程を示す。この例では、まず終点１３を走査し、次にノードＥを走査する。
【００７１】
ノード３に着目する。ここで、終点１３からまだ計算結果として選択されていない終点１２までの最短メトリック値を、先に作成したテーブル４１から調査する。このとき、終点１３から終点１２までのメトリック値は「４」である。一方、終点１２が管理している計算結果の一部からのメトリック値は「３」である。新たに計算されたメトリック値の方が大きいため、情報は更新せずにそのまま残す。この時点で、終点１２が保持する計算結果の一部のノードから終点１２までの最短メトリックは「３」であり、最短メトリック経路の基点情報は「ノードＦ」である。
【００７２】
続いて、ノードＥに着目する。ここで、ノードＦからまだ計算結果として選択されていない終点１２、１３までの最短メトリック値を、先に作成したテーブル４１から調査する。このとき、ノードＥから終点１２までのメトリック値は「３」である。一方、終点１２が管理している計算結果の一部からのメトリック値は「３」である。新たに計算されたメトリック値と同じか大きい値が格納されているため、情報を更新する。この時点で、終点１２が保持する計算結果の一部のノードから終点１２までの最短メトリックは「３」に、最短メトリック経路の基点情報は「ノードＥ」に更新される。
【００７３】
最後に、まだ計算結果の一部として選ばれていない終点１２を計算結果の一部として選択し、その終点に関連付けられた最短メトリック経路の基点情報に記載されている計算結果の一部のノードからその終点までの経路を、計算結果の一部として追加する。
【００７４】
図１１に経路の追加の様子を示す。終点１２に到達する経路は、基点がノードＥであると記録されているため、経路Ｅ−Ｇ−Ｈ−１２が追加される。そして、最終的に図１２に示すような経路が計算結果として出力される。
【００７５】
得られた計算結果は、計算結果記憶部２２２からパケット処理モジュール２３１に送られ、パケット化されて、マルチキャスト転送経路設定装置３０に送られる。計算結果を受け取ったマルチキャスト転送経路設定装置３０は、計算結果に従って、マルチキャスト転送経路を設定する。マルチキャスト転送経路計算装置２０の機能とマルチキャスト転送経路設定装置３０とが同一ノードに存在する場合には、計算された転送経路に従って転送経路を設定するため、パケット処理モジュール３４１に送られて処理される。
【産業上の利用可能性】
【００７６】
本発明のマルチキャストネットワークは、既存のマルチキャストネットワークに本発明のマルチキャスト転送経路計算方法を実施する装置を接続することで、容易に実現できる。また、ネットワーク内のノードコンピュータに本発明のマルチキャスト転送経路計算プログラムをインストールすることでも、容易に実施できる。このマルチキャスト転送経路計算プログラムは、コンピュータ読み取り可能な記録媒体に記録されて取引されてもよく、ネットワーク上で特定のコンピュータにダウンロードさせることもできる。
【図面の簡単な説明】
【００７７】
【図１】本発明の槻要を説明する図。
【図２】マルチキャスト転送経路計算装置の構成例を示すブロック図。
【図３】マルチキャスト転送経路設定装置の構成例を示すブロック図。
【図４】マルチキャスト転送経路計算装置における経路計算の処理を示すフローチャート。
【図５】転送経路設定の対象となるマルチキャストネットワーク。
【図６】終点毎に計算されたネットワーク中の全ノードから各終点への最短メトリック経路を示す図。
【図７】各終点が保持する確定経路からの最短メトリックおよび最短メトリック経路の基点の初期情報、ならびに最初に計算結果の一部が選択される動作を示す図。
【図８】経路の走査過程を示す図。
【図９】走査の終了時点の状況を示す図。
【図１０】経路の走査過程を示す図。
【図１１】経路の追加の様子を示す図。
【図１２】最終的な経路の計算結果を示す図。
【符号の説明】
【００７８】
１０  マルチキャスト転送装置
２０  マルチネャスト転送経路計算装置
３０  マルチキャスト転送経路設定装置
２１、３１  情報管理部
２１１、３１１  ルーチングプロトコルモジュール
２１２、３１２  計測情報記憶部
２２、３５  経路計算部
２２１、３５１  経路計算モジュール
２２２、３５２  計算結果記憶部
２３、３４  パケット処理部
２３１、３４１  パケット処理モジュール
２３２、３４２  パケット転送テーブル記憶部
２３３、３４３  ネットワークインタフェース
３２  測定部
３３  経路設定用プロトコル処理部
１１、１２、１３  終点
４０〜４２  テーブル
５０〜５２  情報
Ａ〜Ｊ  ノード
【図１】
2005072869.tif 000003
【図２】
2005072869.tif 000004
【図３】
2005072869.tif 000005
【図４】
2005072869.tif 000006
【図５】
2005072869.tif 000007
【図６】
2005072869.tif 000008
【図７】
2005072869.tif 000009
【図８】
2005072869.tif 000010
【図９】
2005072869.tif 000011
【図１０】
2005072869.tif 000012
【図１１】
2005072869.tif 000013
【図１２】
2005072869.tif 000014