(57)【特許請求の範囲】
【請求項１】
リンクステートプロトコルにより制御されるネットワークにおいてマルチキャストルートの計算を行う方法であって、
既知の最短経路ツリーアルゴリズムを用いて、前記ネットワークにおける第1のノードから他の全てのノードへのスパニングツリーを算出するステップと、
前記ネットワークを複数のパーティションに分割するステップであって、各パーティションは、算出されたスパニングツリーにおける前記第1のノードの近隣ノードと、前記算出されたスパニングツリーにおける前記近隣ノードに従属する前記ネットワーク内のノードとを含む、ステップと、
所定の条件が満たされる場合、2つ以上の前記パーティションを併合するステップと、
最大のパーティション以外の総てのパーティションに属するノードを確認し、最短経路が前記第1のノードを通るノード対を特定するステップと
を有する方法。
【請求項２】
第1のパーティション及び第2のパーティションの各々が前記近隣ノードの各々を包含し、前記所定の条件は、包含される前記近隣ノード各々の間の最短経路が前記第1のノードを通らないことである、請求項1記載の方法。
【請求項３】
前記最短経路が直接的なリンクをなす、請求項2記載の方法。
【請求項４】
前記最短経路が、前記包含される前記近隣ノード各々の間でコストが等しい2以上の経路群の中から、対称的でローカルに矛盾しないタイブレーキング法により選択される、請求項2記載の方法。
【請求項５】
第1のパーティションが前記近隣ノードの内の1つを含み、第2のパーティションが前記近隣ノードの2つ以上を含むスーパーパーティションであり、前記所定の条件は、前記第1のパーティションの内の1つの近隣ノードと前記第2のパーティションの内の2つ以上の近隣ノードとの間の最短経路各々が、前記第1のノードを通らないことである、請求項1記載の方法。
【請求項６】
前記最短経路の内の少なくとも1つは直接的なリンクをなす、請求項5記載の方法。
【請求項７】
前記最短経路の内の少なくとも1つが、前記第1のパーティションの内の何れかの近隣ノードと前記第2のパーティションの2つ以上の近隣ノードの何れかとの間でコストが等しい2以上の経路群の中から、対称的でローカルに矛盾しないタイブレーキング法により選択される、請求項5記載の方法。
【請求項８】
第1のパーティションが前記近隣ノードの内の1つを含み、第2のパーティションが前記近隣ノードの2つ以上を含むスーパーパーティションであり、前記第1のパーティションの内の何れかの近隣ノードは、1つ以上の最短経路群により前記第2のパーティションの2つの近隣ノード各々に接続され、少なくとも1つの最短経路群は、対称的でローカルに矛盾しないタイブレーキング法により選択されたコストが等しい2つ以上の経路を含み、前記所定の条件は、所与の最短経路群に属するコストが等しい2以上の経路の何れもが、前記第1のノードを通らないことである、請求項1記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットネットワークにおけるトラフィック転送に関連し、特にプロバイダリンク状態ブリッジ(Provider Link State Bridging:  PLSB)による処理方法に関連する。
【背景技術】
【０００２】
ネットワークオペレータ及びキャリアは、回線交換網の代わりにパケット交換網を開発している。インターネットプロトコル(IP)ネットワークのようなパケット交換網の場合、ネットワーク内のIPルータ各々に保存されているルーティング方法に従って、IPパケットがルーティングされる。同様に、イーサネット網の場合、ネットワークのイーサネットスイッチ各々に保存されている転送方法に従って、イーサネットフレームが転送される。本発明は、任意のプロトコルデータユニット(PDU)に基づくネットワークを利用する通信網に適用可能であり、本願において、「パケット」、「パケット交換網」、「ルーティング」、「フレーム」、「フレームを用いるネットワーク」、「転送」及びその他の関連する用語は、任意のPDU、PDUを使用する通信網、及びネットワークノードからネットワークノードへPDUを選択的に送信すること等を包含するように意図されている。
【０００３】
データパケットのマルチキャスト転送(ソースノードから複数の宛先ノードへ事実上同時にパケットが送信されること)は、インターネットプロトコルテレビジョン(IPTV)及びビデオオンデマンド(VoD)等のサービスの需要が増えてくるにつれて益々重要になってくる。
【０００４】
アイエスアイエスシステム(Intermediate  System-Intermediate  System:  IS-IS)、オープンショーテストファースト(Open  Shortest  Path  First:  OSPF)及びマルチキャストOSPFは、トポロジ情報を配布し、複数のノードを相互接続するパスの計算の分散化を可能にし、それらのパスを実現するのに必要な転送方法(転送状態)をインストールするために使用される。OSPF及びIS-ISはネットワーク内に分散したノードにより実行され、例えばノードやリンクが故障したような場合にネットワークにトポロジ変更が生じると、その情報がプロトコル処理により全てのノードに送付され、そのネットワークトポロジに矛盾せずに不具合を回避するように、各ノードがローカルにパスを計算し直す。
【０００５】
イーサネットネットワークの場合、プロバイダバックボーントランスポート(PBT)(又は、プロバイダバックボーンブリッジトラフィックエンジニアリング(PBB-TE))は、英国突出願GB2422508において説明されているように、ユニキャストイーサネットトランスポート技術を使用している。本願出願人による米国特許出願第11/537,775号に記載されているようにプロバイダリンク状態ブリッジ(PLSB)は、IS-ISを用いてイーサネットネットワークにマルチキャスト伝送能力を持たせ、ユニキャストパス及びマルチキャストツリーの双方をネットワーク内に設定するのに使用される。上記の各特許出願は本願のリファレンスに組み入れられる。
【０００６】
本願において可能であるならばイーサネットという用語が使用されているが、本発明はイーサネットブリッジに対するルーティングシステム例に限定されない。例えば、フィルタリングデータベース(FDB)という用語は、情報ベース又はラベル情報ベースのようなパケット転送情報の情報リポジトリに関する如何なるものとも同義語とする。
【０００７】
例えば、PLSBネットワークにおけるマルチキャストツリーは、全最短対パスのマルチキャスト経路計算アルゴリズムを用いて算出され、これは例えば本願出願人による米国特許出願公開番号第20070165657号に説明されている。この方法の場合、ノードが、マルチキャストグループメンバーシップの変更又はネットワークトポロジの変更を(例えば、リンク状態プロトコルデータユニット(LSP)を介して)受信すると、そのノードはダイクストラアルゴリズムのようなアルゴリズムを使用して、計算しているノードを横切る最短経路で接続される一群のネットワークノード対(ペア)及びユニキャスト接続の双方を計算する。その一群のノード対に関し、ノードは、マルチキャストメンバーシップの交わりが生じる場所を判定し、必要なFDBエントリを決定し、それに応じてマルチキャストパスの一部を実現する。そして、計算されたパスを実現するユニキャスト及びマルチキャスト転送方法は、ノードのフィルタリングデータベース(FDB)にインストールされ、受信したパケットが、そのフレームの宛先アドレスに基づいてノードの適切な出力ポートに転送されるようにする。
【０００８】
理解されるように、最短経路各々が特定のノードを横切るノードペアを特定する演算負担は非常に重い。なぜならノード各々から他の全てのノードに延びるパスを検査しなければならないからである。場合によっては、許容される期間内に必要な計算を実行できるようにする観点から、ネットワークのサイズが制限されてしまう。明らかに、より強力なプロセッサを用いれば演算速度は向上するが、各ノードのコストを上昇させることは望まれていない。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】英国特許出願公開第2422508号明細書
【特許文献２】米国特許出願公開番号第2007−0165657号明細書
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従って、パケット交換網においてマルチキャストルートの演算効率を改善することが、依然として非常に望まれている。
【課題を解決するための手段】
【００１１】
一実施例による方法は、
リンクステートプロトコルにより制御されるネットワークにおいてマルチキャストルートの計算を行う方法であって、
既知の最短経路ツリーアルゴリズムを用いて、前記ネットワークにおける第1のノードから他の全てのノードへのスパニングツリーを算出するステップと、
前記ネットワークを複数のパーティションに分割するステップであって、各パーティションは、算出されたスパニングツリーにおける前記第1のノードの近隣ノードと、前記算出されたスパニングツリーにおける前記近隣ノードに従属する前記ネットワーク内のノードとを含む、ステップと、
所定の条件が満たされる場合、2つ以上の前記パーティションを併合するステップと、
最大のパーティション以外の総てのパーティションに属するノードを確認し、最短経路が前記第1のノードを通るノード対を特定するステップと
を有する方法である。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施例による方法の原理的なステップを示すフローチャート。
【図２ａ】ネットワークにおいて使用される図1に示すステップの処理を示す図。
【図２ｂ】ネットワークにおいて使用される図1に示すステップの処理を示す図。
【図２ｃ】ネットワークにおいて使用される図1に示すステップの処理を示す図。
【図２ｄ】ネットワークにおいて使用される図1に示すステップの処理を示す図。
【図２ｅ】ネットワークにおいて使用される図1に示すステップの処理を示す図。
【発明を実施するための形態】
【００１３】
本発明の一形態は、リンクステートプロトコルにより制御されるネットワーク(link state protocol controlled network)においてマルチキャストルートの計算を行う方法を提供する。既知のスパニングツリープロトコルを用いて、ネットワークにおける第1のノードから他の全てのノードへのスパニングツリーが算出される。そしてネットワークは2つ以上の部分(パーティション)に分割され、各パーティションは、第1のノードの近隣ノード(immediate neighbour node)とスパニングツリーにおける近隣に従属するネットワークの任意のノードとを含む。所定の条件が満たされる場合、2つ以上のパーティションが併合される。最大のパーティション以外の総てのパーティションに属するノードが確認され、確認された各ノードは、各自の最短経路が第1のノードを通るノードペアを特定するために検査される。
【実施例１】
【００１４】
添付図面と共に以下の詳細な説明を参照することで、本発明の更なる特徴及び利点は更に明らかになるであろう。
【００１５】
添付図面において、同様な要素は同様な参照番号で示されていることに留意を要する。
【００１６】
本発明は、所与のノードに関して最短経路をもたらす全てのノード対を発見する際に、検査を要するノード数を最小化するPLSB計算法を提供する。場合によっては、検査を要するノード数はゼロにまで減らすことができる。以下、本発明の実施例を単なる一例として図1−2eを参照しながら説明する。
【００１７】
始めに、本発明による方法は、計算される最短経路が対称的であるネットワーク(すなわち、無向グラフ(undirected graph)として表現可能であるネットワーク)に対して有用であり、コストが同じである2つ以上のパス又は経路が何らかの2つのノードの間で算出可能であった場合、選択された「最短」パスが対称的でローカルに矛盾がないものであるように、コストが等しい何れかのパスを選択するタイブレーキング法(tie breaking method)を使用する必要がある。この場合において、「ローカルに矛盾がない(locally consistent)」とは、タイブレーキング法により選択された等コストのパスの任意の部分的なパスが、それ自身、タイブレーキング法により選択された最短パスとならなければならないことを意味する。本発明の方法に関して使用されるタイブレーキング法については、本願出願人が西暦2007年12月26日に出願した米国特許出願第11/964,478号に説明されている。
【００１８】
図1は、本発明の一実施例による方法の原理的なステップを示すフローチャートであり、図2a-eは、ネットワーク各々において使用される図1に示すステップの処理を説明するための図である。
【００１９】
図2aを参照するに、代表的なPLSBネットワークはリンクにより相互接続された複数のノード(ノードA-Rとして示されている)を有する。通常、PLSBネットワークでは、図2a-eのネットワークに属する全てのノードが少なくとも他の2つのノードに接続されているが、そのようなことは必須ではない。好ましくは、本発明による方法は、全てのノードにおいて実質的に同時に実行されるように実現される。以下の説明において、本方法は、ノード「A」を通る最短経路を発見する具体例の観点から説明される。
【００２０】
図1及び図2bを参照するに、最初のステップにおいて、ノード「A」からネットワークにおける他の全てのノードに向かうスパニングツリーが、例えばダイクストラアルゴリズム(Dijkstra’s algorithm)のような従来の最短経路ツリーアルゴリズムを用いて算出される。図2bに示されているように、(図2b-eにおいて太い実線で示されている)スパニングツリーは、ノード「A」から近隣の隣接ノード(ノードB、C、D及びE)の各々に延びる複数の分岐を有する。このツリー構成によれば、ネットワーク上の全てのノードはこれらの分岐の内の何れかに属している。従って、理論上ネットワークを一群のパーティション(部分)に分割することが可能であり、パーティションの各々はスパニングツリーにおける各自の分岐を含む。
【００２１】
従って、このツリー構成によれば、パーティションの各々は、隣接ノードの内の各自対応するものと、スパニングツリーにおけるその隣接ノードに従属する全てのノードとを含む。説明の便宜上、ブランチ/パーティションの各々は、ブランチのルートとして機能する各自の隣接ノードの識別子を用いて表現される。従って、図2cにおいて、4つのパーティションが、各自のルートノードの身元を示すパーティション「B」、「C」、「D」及び「E」として示されている。
【００２２】
図2cに示されているように、ノード「A」を通る如何なる最短経路も或るパーティションから始まって別のパーティションで終わることを要する。ノード対又はノードペアの間のパスの対称性に起因して、最短経路が「A」を通るノード対全てを発見する際、検討を要するノード数は、一方のパーティションのみにおける全てのノードを考察することで削減できる。この削減法の利点は、ノードメンバ数の観点から最大のパーティションが、省略されるパーティションとして選択可能であり、より小規模の残りのパーティションに属するノードで終端するパスのみを考察すればよいことに気付くことで、最大化することができる。
【００２３】
検査を要するノード数を更に削減する方法は、パーティションに含まれているルートノード同士の間の経路が、ノード「A」を介する2ホップの経路より短い場合にその場合に限って、一方のパーティションの任意のノードと他の任意のパーティションの任意のノードとの間の最短経路はノード「A」を通らないことに気付くことで、得られる。例えば、図2の例におけるノードM及びRの間の経路を考察することにすると、これらはそれぞれパーティション「D」及び「E」に属している。この例において、最短経路の判断基準としてホップ数のみを考察することにするが、他の基準が同様に使用されてもよい。ネットワークを調べると、ルートノード「D」及び「E」はリンクによって直接的に接続されている。従って、ノードM及びR間の最短経路はルートノード「D」及び「E」のみを通るものであり、ノード「A」を通るものではない。パーティション「D」及び「E」の他のノードを検討すると、最短経路の全てがルートノード「D」及び「E」の間の直接リンクを通るわけではないが、直接リンクが存在するということは、これらの最短経路は何れもノード「A」を通るものではないことを保証していることが、分かる。従って、「A」に着目した計算を行う際、パーティション「D」及び「E」は1つの大パーティション(スーパーパーティション)「DE」に併合することができる。
【００２４】
パーティション又はスーパーパーティションの対におけるルートノード対同士の間で、より短い経路を発見し、十分な数の短い経路が発見された場合は常にパーティションを併合する上記のプロセスは、(a)全てのパーティションが1つのスーパーパーティションに併合されるまで(すなわち、そのようなスーパーパーティションはノード「A」以外のネットワーク全体を包含することになる)、又は(b)ノード「A」を介する2ホップより短い経路によってパーティションに属する全てのルートノードが相互接続されるようなパーティションの対が存在しなくなるまで反覆可能である。2つのパーティションが併合可能か否かは、併合を検討しているパーティションのルートノードを考察することで決定できる。パーティションの各々が1つのルートノードを有する一対のパーティションという簡易な場合を考察すると、2つのパーティションのルートノードがノード「A」を介する2ホップより短い経路により接続される場合であってその場合に限って、2つのパーティションは併合することができる。1つのルートノードを有するパーティションとN個(N＞1)のルートノードを有するスーパーパーティションとが存在する更に複雑な例の場合、パーティションのルートノードとスーパーパーティションのN個のルートノードとの間の最短経路の何れもがノード「A」を介するものでない場合に、2つのパーティションは併合することができる。
【００２５】
次に図2dを参照するに、引き続きホップ数を最短経路の基準として使用することにすると、パーティション「B」は、スーパーパーティション「DE」と併合され、スーパーパーティション「BDE」を生成することが可能である。なぜなら、ルートノード「B」はスーパーパーティション「DE」の2つのルートノードと直接的に接続されているからである。これは、ノード「A」を通るスーパーパーティション「BDE」内の任意のノード対の間には最短経路が存在しないことを保証する。一方、図2eを参照すると、パーティション「C」スーパーパーティション「BDE」とは併合できないことが示されている。なぜなら、ルートノード「C」とスーパーパーティション「BDE」のルートノード「E」との間に直接的なリンクが一切存在しないからである。すなわち、パーティション「C」はパーティション「E」とは併合できないし、パーティション「E」を含む如何なるスーパーパーティションとも併合できない。
【００２６】
図2eを参照するに、上記のパーティションの併合プロセスの結果、2つのパーティションに分割されたネットワークが得られ、2つのパーティションとは、パーティション「C」とスーパーパーティション「BDE」である。上述したように、関心のある全ての最短経路は、最大のパーティションを除くパーティション各々に属するノードを調べることで発見できる。図2eの場合、ノード「A」を通る全ての最短経路は、ノード「C」を検査し、ノード「A」を通るノード「C」から伸びる最短経路各々を検討することで発見できる。理解されるように、目下の例の場合、これはネットワークに必要なPLSB演算負担を大幅に削減する。なぜなら、唯1つのノードから伸びるパスしか考慮しなくてよいからである(この点、17個のノードを考察しなければならなかった従来技術と大きく異なる)。
【００２７】
パーティションを併合することで得られる恩恵はネットワークトポロジに依存することが理解されるであろう。全てのパーティションがネットワーク全体を包含する1つのスーパーパーティションに併合可能な場合、(パーティションを処理するオーバーヘッドステップの後に)検討を要するノード数はゼロになる。より典型的な例の場合、パーティションを併合するプロセスは、複数のパーティション及び/又はスーパーパーティションという結果になる。ノード「A」がデュアル接続エッジノード(dual connected edge node)であるという特殊なケースの場合、初期のパーティション数は2である。これら2つのパーティションが適切に併合できた場合、以後検査を要するノード数はゼロに減少する。併合できなかった最悪の場合、検査を要するノード数はネットワークのノード数の半分よりも僅かに少なく、それでも従来の方法に対してかなりの改善である。
【００２８】
当該技術分野で知られているように、アイエスアイエス(IS-IS)及びオープンショーテストパスファースト(OSPF)並びにマルチキャストOSPFのような経路算出法は、ノードペア同士の間でコストが等しい複数の経路を生成する可能性がある。そのような場合に、パーティションを併合する上記の方法が修正することなく使用されてもよい：その場合、経路各々の「コスト」はホップ数に比例し；或いは2つのパーティション同士の間の直接的なリンクの「コスト」は、関心のあるノード(図2の例ではノード「A」)を介する2ホップの経路の「コスト」より少ない。
【００２９】
ノード対の間でコストが等しい一群の経路の中から、「最短」の経路又は最短経路の部分集合を選択するために、タイブレーキングアルゴリズムを使用する必要がある。そのような場合、パーティションを併合する上記の方法を使用することが可能である。ただし、タイブレーキングアルゴリズムにより選択された「最短の」経路は対称的であり、ローカルに矛盾がないものであるとする。
【００３０】
例えば、図2のネットワークにおいて、経路の計算結果が、ノードC及びEの間でコストが等しい3つの経路を示した場合を考える。この場合に、タイブレーキングアルゴリズムを使用して、これら3つの等コスト経路の内の何れかを「最短」経路として選択する。この場合において、タイブレーキング法が、ノードB又はDを経由するがノードAを経由しない2つの経路の何れかを最短経路として選択した場合、上記の方法はパーティション「C」をスーパーパーティション「BDE」と併合してもよい。
【００３１】
理解されるように、同じ方法論がある場合に拡張可能であり、その場合とは、経路計算アルゴリズムがコストが等しい一群の経路を計算し、タイブレーキング法がそれらコストが等しい経路の内の2つ以上の部分集合を最短経路として選択した場合である。この場合、2つのパーティションを併合する基準は、目下考察しているノードを通る最短経路が一切選択されないことである。例えば、タイブレーキング法は、ノードC及びＥの間の任意の2つの経路を一群の最短経路として選択する可能性があり、上記の方法は、その一群の最短経路がノード「A」を通る経路を含んでいなかった場合に、パーティション「C」とスーパーパーティション「BDE」を併合することができる。
【００３２】
本発明の上記の実施例は例示にすぎないことが意図されている。従って本発明の範囲は添付の特許請求の範囲によってのみ規定される。
【図１】
0005385984.tif 000002
【図２ａ】
0005385984.tif 000003
【図２ｂ】
0005385984.tif 000004
【図２ｃ】
0005385984.tif 000005
【図２ｄ】
0005385984.tif 000006
【図２ｅ】
0005385984.tif 000007