図面 (/)

技術 マルチキャスト転送経路計算装置

出願人 日本電信電話株式会社
発明者 宇賀雅則杉園幸司安川正祥
出願日 2003年10月27日 (17年2ヶ月経過) 出願番号 2003-365990
公開日 2005年5月19日 (15年7ヶ月経過) 公開番号 2005-130369
状態 特許登録済
技術分野 広域データ交換
主要キーワード 遅延コスト 計算依頼 転送ケーブル ツリートポロジ 予備リンク 進行方向毎 測定モジュール 設定依頼
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2005年5月19日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (11)

課題

途中ノードでの現用予備切り替えを可能とし、切り替え時間を短縮する。

解決手段

与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算し、主転送経路上の全リンクに対して予備転送経路を計算する。このときに、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎トラヒック状態計測し主転送経路を計算し、この計算された主転送経路上のリンク毎に予備転送経路を計算して求める。

概要

背景

コンピュータネットワーク上で、動画音声特定多数のユーザに配送するマルチキャスト転送が注目を集めている。この転送方式は、経路の始点と選択された1つ以上の終点とを結ぶ経路のうち、経路が分かれている部分において情報をコピーし、各終点へと情報を配送する。

特定多数の終点へ始点と一対一転送を行うユニキャスト転送を用いて情報を配送した場合には、終点の数だけ始点は情報を用意する必要がある。よって、マルチキャスト転送を用いることにより、ネットワーク内の情報量は減少する。

マルチキャスト転送では特定多数の終点をマルチキャストグループと呼ばれる管理単位で管理を行い、マルチキャストグループに対して1つの転送経路が設定される。この転送経路は始点からマルチキャストグループに属するすべての終点を接続するように設定される。経路上のリンク故障した場合には、ユニキャスト転送の場合には1対1の転送なので情報が届かなくなるといった影響を受ける終点は少ないが、マルチキャスト転送の場合には1対複数の転送であるため1つのリンク故障によって影響を受ける終点の数が多くなることがある。図10にその例を示す。

本例ではユニキャスト転送の場合には情報が届かなくなるのは1受信者のみとなるが、マルチキャスト転送の場合には6終点となる。そのためマルチキャスト転送においてマルチキャスト予備転送経路(以下、予備転送経路という)を持つことはユニキャスト転送に比べて重要である。

現在、リンクに対する予備転送経路ではなく主転送経路に対して予備転送経路を求めるアルゴリズムとして以下のような方式が公開されている(例えば、非特許文献1、2、3参照)。

これらの方式は、主転送経路と予備転送経路を同時に求めるアルゴリズムであり、特に、非特許文献1で紹介されている方式は、主転送経路と予備転送経路が利用する帯域を少なくすることを目的にしている。
M.Kodialem and T.Lakshman.Dynamicrouting of bandwidth guaranteed multicasts with failure backup.In ProceedingsofIEEEINFOCOM,June 2002.
Alon Itai and Michael Rodeh.Themulti-tree approach to reliability in distributed networks.In IEEE Symposium onFoundations of Computer Science,pages 137-147,1984.
M.M_edard,S.Finn,R.Barry,andR.Gallager.Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs.IEEE/ACMTransactions on Networking,7(5):641-652,1999.
V.Kompella 他,“Multicast routingfor multimedia communication,”IEEE/ACM Transactions on Networking,Volume:1Issue:3,pp.286-292,June 1993
Q.Zhu,他,“A source-based algorithmfor delay-constrained minimum-cost multicasting,”proc in IEEE INFOCOM’95,vol.1,pp.377-385,1995
E.Q.V.Martins,M.M.B.Pascal,andJ.L.E.Santos.Deviation Algorithms for Ranking Shortest Paths.InternationalJournal of Foundations of Computer Science.1999.

概要

途中ノードでの現用予備切り替えを可能とし、切り替え時間を短縮する。 与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算し、主転送経路上の全リンクに対して予備転送経路を計算する。このときに、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎トラヒック状態計測し主転送経路を計算し、この計算された主転送経路上のリンク毎に予備転送経路を計算して求める。

目的

本発明は、このような背景に行われたものであって、始点ではなく主転送経路上の各リンクに予備転送経路を準備することにより、途中ノードで切替えすることが可能となり、切替時間の短縮を実現できることを目的とする。

効果

実績

技術文献被引用数
0件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶマルチキャスト主転送経路(以下、主転送経路という)をマルチキャスト転送経路計算装置により計算するステップと、この計算された主転送経路をマルチキャスト経路設定装置が設定するステップと、前記計算した主転送経路上の全リンクに対してそれぞれマルチキャスト予備転送経路(以下、予備転送経路という)を前記マルチキャスト転送経路計算装置により計算するステップと、この計算された全予備転送経路をマルチキャスト転送経路設定装置により設定するステップとを実行するマルチキャスト転送経路設定方法であって、前記マルチキャスト転送経路計算装置は、前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の2つに分けるステップと、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのk個の最短経路(1≦k≦N:k、Nは1以上の整数)を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkthshortestpathアルゴリズムを用いて計算してk個の経路を求めるステップと、このk個の経路を求めるステップにより1つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定するステップと、前記k個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのk個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkthshortestpathアルゴリズムを用いて計算してk個の経路を求めるステップを最短経路が求まるまで繰り返し行うステップとを実行することを特徴とするマルチキャスト転送経路設定方法。

請求項2

前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了するステップを実行する請求項1記載のマルチキャスト転送経路設定方法。

請求項3

マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する手段と、前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する手段とを備えたマルチキャスト転送経路計算装置であって、前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の2つに分ける手段と、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのk個の最短経路(1≦k≦N:k、Nは1以上の整数)を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkthshortestpathアルゴリズムを用いて計算してk個の経路を求める手段と、このk個の経路を求める手段により1つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定する手段と、前記k個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのk個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkthshortestpathアルゴリズムを用いて計算してk個の経路を求める手順を最短経路が求まるまで繰り返し行う手段とを備えたことを特徴とするマルチキャスト転送経路計算装置。

請求項4

前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了する手段を備えた請求項3記載のマルチキャスト転送経路計算装置。

請求項5

情報処理装置インストールすることにより、その情報処理装置に、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する機能と、前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する機能とを備えたマルチキャスト転送経路計算装置に相応する機能を実現させるプログラムであって、前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の2つに分ける機能と、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのk個の最短経路(1≦k≦N:k、Nは1以上の整数)を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkthshortestpathアルゴリズムを用いて計算してk個の経路を求める機能と、このk個の経路を求める機能により1つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定する機能と、前記k個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのk個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkthshortestpathアルゴリズムを用いて計算してk個の経路を求める手順を最短経路が求まるまで繰り返し行う機能とを備えたマルチキャスト転送経路計算装置に相応する機能を実現させることを特徴とするプログラム。

請求項6

前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了する機能を実現させる請求項5記載のプログラム。

請求項7

請求項5または6記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体

技術分野

0001

本発明は、コンピュータネットワーク上で、動画音声特定多数のユーザに配送するマルチキャスト転送に利用する。特に、マルチキャスト主転送経路(以下、主転送経路という)の障害対策に関する。

背景技術

0002

コンピュータネットワーク上で、動画や音声を特定多数のユーザに配送するマルチキャスト転送が注目を集めている。この転送方式は、経路の始点と選択された1つ以上の終点とを結ぶ経路のうち、経路が分かれている部分において情報をコピーし、各終点へと情報を配送する。

0003

特定多数の終点へ始点と一対一転送を行うユニキャスト転送を用いて情報を配送した場合には、終点の数だけ始点は情報を用意する必要がある。よって、マルチキャスト転送を用いることにより、ネットワーク内の情報量は減少する。

0004

マルチキャスト転送では特定多数の終点をマルチキャストグループと呼ばれる管理単位で管理を行い、マルチキャストグループに対して1つの転送経路が設定される。この転送経路は始点からマルチキャストグループに属するすべての終点を接続するように設定される。経路上のリンク故障した場合には、ユニキャスト転送の場合には1対1の転送なので情報が届かなくなるといった影響を受ける終点は少ないが、マルチキャスト転送の場合には1対複数の転送であるため1つのリンク故障によって影響を受ける終点の数が多くなることがある。図10にその例を示す。

0005

本例ではユニキャスト転送の場合には情報が届かなくなるのは1受信者のみとなるが、マルチキャスト転送の場合には6終点となる。そのためマルチキャスト転送においてマルチキャスト予備転送経路(以下、予備転送経路という)を持つことはユニキャスト転送に比べて重要である。

0006

現在、リンクに対する予備転送経路ではなく主転送経路に対して予備転送経路を求めるアルゴリズムとして以下のような方式が公開されている(例えば、非特許文献1、2、3参照)。

0007

これらの方式は、主転送経路と予備転送経路を同時に求めるアルゴリズムであり、特に、非特許文献1で紹介されている方式は、主転送経路と予備転送経路が利用する帯域を少なくすることを目的にしている。
M.Kodialem and T.Lakshman.Dynamicrouting of bandwidth guaranteed multicasts with failure backup.In ProceedingsofIEEEINFOCOM,June 2002.
Alon Itai and Michael Rodeh.Themulti-tree approach to reliability in distributed networks.In IEEE Symposium onFoundations of Computer Science,pages 137-147,1984.
M.M_edard,S.Finn,R.Barry,andR.Gallager.Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs.IEEE/ACMTransactions on Networking,7(5):641-652,1999.
V.Kompella 他,“Multicast routingfor multimedia communication,”IEEE/ACM Transactions on Networking,Volume:1Issue:3,pp.286-292,June 1993
Q.Zhu,他,“A source-based algorithmfor delay-constrained minimum-cost multicasting,”proc in IEEE INFOCOM’95,vol.1,pp.377-385,1995
E.Q.V.Martins,M.M.B.Pascal,andJ.L.E.Santos.Deviation Algorithms for Ranking Shortest Paths.InternationalJournal of Foundations of Computer Science.1999.

発明が解決しようとする課題

0008

ここで、上記の非特許文献1、2、3で紹介されている技術では、故障発生始点ノードに伝わらない限り、切替えができないため、切替えに時間がかかるという問題があった。切替えに時間がかかると受信者に情報が届かなくなる時間が長くなることになる。

0009

本発明は、このような背景に行われたものであって、始点ではなく主転送経路上の各リンクに予備転送経路を準備することにより、途中ノードで切替えすることが可能となり、切替時間の短縮を実現できることを目的とする。

課題を解決するための手段

0010

本発明の第一の観点は、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路をマルチキャスト転送経路計算装置により計算するステップと、この計算された主転送経路をマルチキャスト経路設定装置が設定するステップと、前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を前記マルチキャスト転送経路計算装置により計算するステップと、この計算された全予備転送経路をマルチキャスト転送経路設定装置により設定するステップとを実行するマルチキャスト転送経路設定方法である。

0011

ここで、本発明の特徴とするところは、前記マルチキャスト転送経路計算装置は、前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の2つに分けるステップと、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのk個の最短経路(1≦k≦N:k、Nは1以上の整数)を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkth shortest pathアルゴリズムを用いて計算してk個の経路を求めるステップと、このk個の経路を求めるステップにより1つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定するステップと、前記k個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのk個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkth shortest pathアルゴリズムを用いて計算してk個の経路を求めるステップを最短経路が求まるまで繰り返し行うステップとを実行するところにある(請求項1)。前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了するステップを実行することができる(請求項2)。これにより、効率よく予備転送経路の最短経路を計算することができる。

0012

本発明の第二の観点は、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する手段と、前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する手段とを備えたマルチキャスト転送経路計算装置である。

0013

ここで、本発明の特徴とするところは、前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の2つに分ける手段と、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのk個の最短経路(1≦k≦N:k、Nは1以上の整数)を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkth shortest pathアルゴリズムを用いて計算してk個の経路を求める手段と、このk個の経路を求める手段により1つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定する手段と、前記k個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのk個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkth shortest pathアルゴリズムを用いて計算してk個の経路を求める手順を最短経路が求まるまで繰り返し行う手段とを備えたところにある(請求項3)。前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了する手段を備えることができる(請求項4)。

0014

本発明の第三の観点は、情報処理装置インストールすることにより、その情報処理装置に、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する機能と、前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する機能とを備えたマルチキャスト転送経路計算装置に相応する機能を実現させるプログラムである。

0015

ここで、本発明の特徴とするところは、前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の2つに分ける機能と、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのk個の最短経路(1≦k≦N:k、Nは1以上の整数)を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkth shortest pathアルゴリズムを用いて計算してk個の経路を求める機能と、このk個の経路を求める機能により1つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定する機能と、前記k個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのk個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkth shortest pathアルゴリズムを用いて計算してk個の経路を求める手順を最短経路が求まるまで繰り返し行う機能とを備えたマルチキャスト転送経路設定装置に相応する機能を実現させるとこにある(請求項5)。前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了する機能を実現させることができる(請求項6)。

0016

本発明の第四の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である(請求項7)。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。

0017

これにより、汎用の情報処理装置を用いて、マルチキャスト転送でデータ転送を行っている際、リンク故障時にリンク毎の予備リンクを持つことで、故障発生の近隣ノードで予備転送経路に切替が可能となり、高速な切替が実現できるマルチキャスト転送経路計算装置を実現することができる。

発明の効果

0018

本発明によれば、マルチキャスト転送でデータ転送を行っている際、リンク故障時にリンク毎の予備リンクを持つことで、故障発生の近隣ノードで予備転送経路に切替が可能となり、高速な切替が実現できる。

発明を実施するための最良の形態

0019

以下、本発明の一実施形態によるマルチキャスト転送経路設定方法を、図面を参照して説明する。

0020

図1は本発明の概要を説明するための図である。本発明は、主転送経路上の全リンクに対して予備転送経路を設定するマルチキャスト転送経路設定方法である。そして、当該マルチキャストネットワークは、マルチキャスト転送経路設定装置が設けられた複数のノードにより構成されており、また、各ノードのいずれかのノードにマルチキャスト転送経路計算装置またはマルチキャスト転送経路設定装置が設けられている。

0021

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

0022

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

0023

ここで、マルチキャスト転送経路設定装置とマルチキャスト転送経路計算装置とが異なる装置である場合には、マルチキャスト転送経路設定装置がマルチキャスト転送経路計算装置へ主転送経路と予備転送経路の計算を依頼する。また、マルチキャスト転送経路設定装置とマルチキャスト転送経路計算装置とが同一装置である場合には、マルチキャスト転送経路設定装置が自身の経路計算モジュールに主転送経路計算と予備転送経路計算とを指示する。

0024

そして、マルチキャスト転送経路設定装置もしくはマルチキャスト転送経路計算装置の経路計算モジュールが、収集した情報をもとに主転送経路と予備転送経路とを計算する(5)。そして計算結果はマルチキャスト転送経路設定装置の経路設定モジュールに通知され(6)、当該計算結果を受信したマルチキャスト転送経路設定装置がデータの主転送経路と予備転送経路とを設定する。

0025

なお、上述のネットワーク計測情報を収集する機能においては、既に提案されているOSPF−TE(Open Shortest Path First-Traffic Engineering)やIS−IS−TE(Intermediate
system-Intermediate system-Traffic Engineering)などの隣接ノード間でのネットワーク計測情報を交換する機能が備わった経路計算プロトコル拡張して用いることによりネットワーク計測情報を収集する。

0026

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

0027

本発明で使用する主転送経路計算プログラムは、公知のアルゴリズムを実装したプログラムを利用する。また、本発明で使用する予備転送経路プログラムは、求まった主転送経路上のリンク毎に予備転送経路を計算することを目的とする。

0028

計算した主転送経路に対する経路上のリンクの予備転送経路計算時に、このリンクを除くことで、マルチキャスト主転送経路を、マルチキャスト主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の2つに分け、前記始点を含む部分経路木に含まれる全ノードへ結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのk個の経路を前記計測結果に基づいて公知のkth shortest pathアルゴリズムによって求め、1つ以上の経路が求まった場合には求まった経路の中から所定の条件を満足するものを予備転送経路として決定する。

0029

もし、経路が求まらない場合には、仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのk個の最短経路をマルチキャスト転送装置により計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてkth shortest pathアルゴリズムを用いて計算してk個の経路を求める。以下上記と同様に、1つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定し、経路が求まらない場合には、仮終点の隣接ノードを仮終点とし、前記仮始点から当該仮終点までのk個の最短経路を前記トラヒック状況に基づいてkth shortest pathアルゴリズムを用いて計算してk個の経路を求める。これを1つの予備転送経路が求まるまで行う(請求項1、3)。

0030

なお、ここで所定の条件を満足する経路とは、例えば、主転送経路以上の帯域を確保できる経路であるとか、あるいは、主転送経路と同程度のリンクコストの経路である。

0031

前記計算した主転送経路に対する経路上のリンクの全リンクに対して、予備転送経路を求めた時点で予備転送経路の計算を終了する(請求項2、4)。

0032

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

0033

図2はマルチキャスト転送経路計算装置の構成を示す図である。図2に示すマルチキャスト転送経路計算装置は、ネットワーク内のノードや各ノードをつなぐリンクで発生する遅延コストに関するネットワーク計測情報を管理する情報管理部20と、主転送経路と予備転送経路を計算する経路計算部30と、送受信するパケットを処理するパケット処理部40により構成される。そして、マルチキャスト転送経路計算装置のパケット処理部40が情報管理部20で管理されるネットワーク計測情報や経路計算依頼の受信や、経路計算部30が計算した主転送経路と予備転送経路の計算結果のマルチキャスト転送経路設定装置への送信を行う。

0034

また、マルチキャスト転送経路計算装置の情報管理部20はトラヒック状態の情報の収集に使用するOSPFやIS−ISなどのルーチングプロトコルで使用される情報交換プロトコルを処理するルーチングプロトコルモジュール21とそのプロトコルによって得られたネットワークのトポロジや遅延、コストなどのネットワーク計測情報を管理する計測情報記憶部22とを備えている。また、経路計算部30は、主転送経路と予備転送経路とを計算する経路計算処理モジュール31と、計算結果を記憶する計算結果記憶部32とを備えている。

0035

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

0036

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

0037

そして、情報管理部50の基本構成はマルチキャスト転送経路計算装置の情報管理部20と同様であり、ルーチングプロトコルモジュール51と、計測情報記憶部52とを備えている。また、測定部60はパケット処理部80が備えるネットワークインタフェース83の状態や、ネットワーク上の各ノードの処理の遅延などの情報を測定する測定モジュール(図示省略)を備えている。

0038

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

0039

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

0040

経路設定用プロトコル処理部70はパケット処理部80から主転送経路設定と予備転送経路設定依頼を受信し、その経路設定依頼のマルチキャスト転送経路計算装置への送信処理を行う。また、経路設定用プロトコル処理部70はマルチキャスト転送経路計算装置から受信した主転送経路と予備転送経路の計算結果にしたがってデータ転送のための主転送経路とリンク故障対応のための予備転送経路を設定する機能を有する。

0041

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

0042

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

0043

ノードが交換するネットワーク計測情報は、自ノードで計測したネットワーク計測情報のみならず、自ノードが保持する他ノードが計測したネットワーク計測情報も含まれる。これらの交換動作により、各ノードはネットワーク内の全ノードにおける接続情報や遅延などのネットワーク計測情報を保持する。そして、新たに主転送経路および予備転送経路を設定するマルチキャスト転送経路設定装置の機能を有するノードは、マルチキャスト転送経路計算装置の機能を有するノードに経路計算依頼をする。

0044

このとき、マルチキャスト転送経路計算装置の機能を有するノードは情報管理部20で管理されているネットワーク内のトポロジや遅延などのトラヒックに関するネットワーク計測情報と、経路計算依頼をしたノードから送られてきた終点の情報とに基づいて予備転送経路を計算する。また、このとき、ネットワーク計測情報は、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測した計測結果であり、当該計測結果に基づきリンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎に主転送経路に対する予備転送経路を計算する。

0045

図4はマルチキャスト転送経路計算装置における予備転送経路計算の処理を示すフローチャートである。まず、マルチキャスト転送経路設定装置の機能を有するノードからの主経路計算と予備転送経路計算依頼をマルチキャスト転送経路計算装置が受け付ける。このとき、マルチキャスト転送経路計算装置は、マルチキャスト転送経路設定装置からデータ転送の終点の情報も受け付ける。すると、マルチキャスト転送経路計算装置の経路計算部30が情報管理部20の計測情報記憶部22に記録されているネットワークのトポロジやトラヒック状態を示すネットワーク計測情報を読み取る(ステップS1)。

0046

そして、経路計算処理モジュール31がネットワーク計測情報を用いて、公知の主転送経路アルゴリズムを利用して、データ転送の始点と全終点までのコストの和が最小の主転送経路を計算する(ステップS2)。このとき、経路計算処理モジュール31は経路計算依頼を送信したノードを始点とし、データ転送の終点の全ノードまでのコストの和が最小の主転送経路を計算する。なお、主転送経路を求めるためのアルゴリズムは、例えば、非特許文献4、5により公知のアルゴリズムを利用する。

0047

次に、マルチキャスト転送経路計算装置の経路計算処理モジュール31はステップS2で求めた主転送経路上のリンク毎の予備転送経路を全リンクに対して求める。主転送経路上のあるリンクに対する予備転送経路をステップS3からステップS9で求める。予備転送経路は全リンクに対して求めるため、ステップS3からステップS9を全リンクに対して行う。

0048

主転送経路上にあるリンクに着目してそのリンクの予備転送経路を求める際、その着目したリンクを主転送経路から削除し、主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の2つに分ける(ステップS3)。始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成する(ステップS4)。始点を含まない部分経路木の頂点を仮終点とする(ステップS5)。仮始点から仮終点までのk個の最短経路を求める(ステップS7)。ステップS7でk個の最短経路を求める際には、例えば、非特許文献6のような公知アルゴリズムを利用する。

0049

ステップS7で1つ以上の経路が求まれば(ステップS8)、その経路から最適な経路を着目したリンクに関する予備転送経路として計算を終了する(ステップS9)。ステップS7で1つも経路が求まらない場合(ステップS8)には仮終点の木の下流隣接ノードを仮始点とする(ステップS6)。ただし仮終点の木の下流隣接ノードが複数ある場合には1のずつ仮終点としてステップS6からステップS7を下流隣接ノード分繰り返す。

0050

最後にこのようにして計算して得られた予備転送経路の結果を経路計算処理モジュール31は、パケット処理部40を介して経路計算依頼を出したノードに返送する。

0051

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

0052

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

0053

次に、本発明による転送経路を計算する処理の一実施例について説明する。図5はマルチキャストネットワークを示す図である。この図においてPはデータ転送の始点でマルチキャスト転送設定装置でもある。R1〜R4がデータ転送の終点である。またN1〜N10は始点と終点との間の中間ノードであり、マルチキャスト転送装置の機能を有している。なお、マルチキャスト転送設定装置P、ノードN1〜N10、終点R1〜R4は転送ケーブル(リンク)により接続されてマルチキャストネットワークを構成している。そして、各リンクは遅延とコストという2つの特性を持っている。そして、マルチキャスト転送経路設定装置Pは、マルチキャスト転送経路計算装置Cが計算した結果に基づいて、終点R1〜R4に対してデータを転送する。

0054

マルチキャスト転送経路計算装置Cは、マルチキャスト転送経路設定装置Pからの経路計算依頼を受けると、主転送経路を計算し、その結果を受けて予備転送経路を計算する。マルチキャスト転送経路設定装置PがN1からN9のリンクに対する予備転送経路を計算する例を示す。

0055

まず、図6に示すように、N1からN9のリンクを削除し、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の2つに分ける。次に、図7に示すように、始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成する。次に、図8に示すように、始点を含まない部分経路木の頂点を仮終点とし、仮始点から仮終点までのk個の最短経路を求める。このとき、仮始点から始点を含む部分経路木に含まれる全ノードを結ぶリンクのコストは全て同じ値にしても良いし、異なる値にしてもよい。ただしそのコストをもとに公知のアルゴリズムを用いてk個の最短経路を求める。本例では3個(k=3)の最短経路が求まった。この中でどの経路を予備転送経路として選択するかはオペレータやプログラムに委ねられるが、本例では、図9破線で示すように、マルチキャストデータの逆流をしないN2→N5→N7→N9を最適な経路として予備転送経路とする。

0056

例えばN1からN9のリンクに対する予備転送経路を求めようとしても、仮始点から始点を含まない部分経路木の頂点(N9)への経路が見つからない場合には、頂点の木の下流隣接ノード(N10、N8)を仮終点として図4で示したステップS6から、ステップS7を下流ノード回(本例の場合は2回)繰り返す。ここで1つ以上の経路が見つかれば予備転送経路の計算は終了する(請求項1、3)。計算した主転送経路上の全リンクに対し、予備転送経路を求めた時点で予備転送経路の計算を終了する(請求項2、4)。

0057

本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のマルチキャスト転送経路計算装置に相応する機能を実現させるプログラムとして実現することができる(請求項5、6)。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ(請求項7)、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、情報管理部20、経路計算部30、パケット処理部40にそれぞれ相応する機能を実現させることができる。また、マルチキャスト転送経路設定装置にマルチキャスト転送経路計算装置の機能が含まれている場合には、当該情報処理装置に、情報管理部50、経路計算部90、パケット処理部80にそれぞれ相応する機能を実現させることができる。さらに、マルチキャスト転送経路設定装置の機能として、経路設定用プロトコル処理部70、測定部60に相応する機能を実現させることもできる。

0058

本発明によれば、マルチキャスト転送でデータ転送を行っている際、リンク故障時にリンク毎の予備リンクを持つことで、故障発生の近隣ノードで予備転送経路に切替が可能となり、高速な切替が実現できる。これにより、ネットワークユーザサービス品質向上に寄与することができる。

図面の簡単な説明

0059

本発明の概要図。
本実施例のマルチキャスト転送経路計算装置の構成図。
本実施例のマルチキャスト転送経路設定装置の構成図。
本実施例の転送経路計算アルゴリズムのフロー図。
マルチキャストネットワーク例を示す図。
2つの部分経路木に分けた結果を示す図。
仮始点を作成した様子を示す図。
仮終点を作成し最短経路を求める様子を示す図。
求まった予備転送経路を示す図。
ユニキャスト転送とマルチキャスト転送とを比較する図。

符号の説明

0060

20、50情報管理部
21、51ルーチングプロトコルモジュール
22、52計測情報記憶部
30、90経路計算部
31、91経路計算処理モジュール
32、92計算結果記憶部
40、80パケット処理部
41、81パケット転送処理モジュール
42、82パケット転送テーブル記憶部
43、83ネットワークインタフェース
60測定部
70経路設定用プロトコル処理部
Cマルチキャスト転送経路計算装置
Pマルチキャスト転送経路設定装置
N1〜N10ノード
R1〜R4 終点

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ