JP2012507214A - マルチキャストルートを算出する方法 - Google Patents

マルチキャストルートを算出する方法 Download PDF

Info

Publication number
JP2012507214A
JP2012507214A JP2011533493A JP2011533493A JP2012507214A JP 2012507214 A JP2012507214 A JP 2012507214A JP 2011533493 A JP2011533493 A JP 2011533493A JP 2011533493 A JP2011533493 A JP 2011533493A JP 2012507214 A JP2012507214 A JP 2012507214A
Authority
JP
Japan
Prior art keywords
node
partition
nodes
network
partitions
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2011533493A
Other languages
English (en)
Other versions
JP5385984B2 (ja
Inventor
チアバウト，ジェロメ
アラン，デイヴィッド
ブラッグ，ニゲル
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nortel Networks Ltd
Original Assignee
Nortel Networks Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nortel Networks Ltd filed Critical Nortel Networks Ltd
Publication of JP2012507214A publication Critical patent/JP2012507214A/ja
Application granted granted Critical
Publication of JP5385984B2 publication Critical patent/JP5385984B2/ja
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H04L45/04—Interdomain routing, e.g. hierarchical routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/122—Shortest path evaluation by minimising distances, e.g. by selecting a route with minimum of number of hops
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/16—Multipoint routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/18—Loop-free operations
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/66—Layer 2 routing, e.g. in Ethernet based MAN's

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Small-Scale Networks (AREA)

Abstract

リンクステートプロトコルにより制御されるネットワークにおいてマルチキャストルートの計算を行う方法が使用される。既知のスパニングツリープロトコルを用いて、ネットワークにおける第1のノードから他の全てのノードへのスパニングツリーが算出される。そしてネットワークは2つ以上の部分(パーティション)に分割され、各パーティションは、第1のノードの近隣ノードとスパニングツリーにおける近隣に従属するネットワークの任意のノードとを含む。所定の条件が満たされる場合、2つ以上のパーティションが併合される。最大のパーティション以外の総てのパーティションに属するノードが確認され、確認された各ノードは、各自の最短経路が第1のノードを通るノードペアを特定するために検査される。

Description

本発明は、パケットネットワークにおけるトラフィック転送に関連し、特にプロバイダリンク状態ブリッジ(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」を併合することができる。
本発明の上記の実施例は例示にすぎないことが意図されている。従って本発明の範囲は添付の特許請求の範囲によってのみ規定される。

Claims (8)

  1. リンクステートプロトコルにより制御されるネットワークにおいてマルチキャストルートの計算を行う方法であって、
    既知の最短経路ツリーアルゴリズムを用いて、前記ネットワークにおける第1のノードから他の全てのノードへのスパニングツリーを算出するステップと、
    前記ネットワークを複数のパーティションに分割するステップであって、各パーティションは、算出されたスパニングツリーにおける前記第1のノードの近隣ノードと、前記算出されたスパニングツリーにおける前記近隣ノードに従属する前記ネットワーク内のノードとを含む、ステップと、
    所定の条件が満たされる場合、2つ以上の前記パーティションを併合するステップと、
    最大のパーティション以外の総てのパーティションに属するノードを確認し、最短経路が前記第1のノードを通るノード対を特定するステップと
    を有する方法。
  2. 第1のパーティション及び第2のパーティションの各々が前記近隣ノードの各々を包含し、前記所定の条件は、包含される前記近隣ノード各々の間の最短経路が前記第1のノードを通らないことである、請求項1記載の方法。
  3. 前記最短経路が直接的なリンクをなす、請求項2記載の方法。
  4. 前記最短経路が、前記包含される前記近隣ノード各々の間でコストが等しい2以上の経路群の中から、対称的でローカルに矛盾しないタイブレーキング法により選択される、請求項2記載の方法。
  5. 第1のパーティションが前記近隣ノードの内の1つを含み、第2のパーティションが前記近隣ノードの2つ以上を含むスーパーパーティションであり、前記所定の条件は、前記第1のパーティションの内の1つの近隣ノードと前記第2のパーティションの内の2つ以上の近隣ノードとの間の最短経路各々が、前記第1のノードを通らないことである、請求項1記載の方法。
  6. 前記最短経路の内の少なくとも1つは直接的なリンクをなす、請求項5記載の方法。
  7. 前記最短経路の内の少なくとも1つが、前記第1のパーティションの内の何れかの近隣ノードと前記第2のパーティションの2つ以上の近隣ノードの何れかとの間でコストが等しい2以上の経路群の中から、対称的でローカルに矛盾しないタイブレーキング法により選択される、請求項5記載の方法。
  8. 第1のパーティションが前記近隣ノードの内の1つを含み、第2のパーティションが前記近隣ノードの2つ以上を含むスーパーパーティションであり、前記第1のパーティションの内の何れかの近隣ノードは、1つ以上の最短経路群により前記第2のパーティションの2つの近隣ノード各々に接続され、少なくとも1つの最短経路群は、対称的でローカルに矛盾しないタイブレーキング法により選択されたコストが等しい2つ以上の経路を含み、前記所定の条件は、所与の最短経路群に属するコストが等しい2以上の経路の何れもが、前記第1のノードを通らないことである、請求項1記載の方法。
JP2011533493A 2008-10-28 2009-10-26 マルチキャストルートを算出する方法 Expired - Fee Related JP5385984B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US12/259,650 US8005016B2 (en) 2008-10-28 2008-10-28 Provider link state bridging (PLSB) computation method
US12/259,650 2008-10-28
PCT/CA2009/001506 WO2010048698A1 (en) 2008-10-28 2009-10-26 Provider link state bridging (plsb) computation method

Related Child Applications (1)

Application Number Title Priority Date Filing Date
JP2013209161A Division JP2014039314A (ja) 2008-10-28 2013-10-04 リンクステートプロトコルにより制御されるネットワークにおいて転送状態を算出する装置及び方法

Publications (2)

Publication Number Publication Date
JP2012507214A true JP2012507214A (ja) 2012-03-22
JP5385984B2 JP5385984B2 (ja) 2014-01-08

Family

ID=42117410

Family Applications (2)

Application Number Title Priority Date Filing Date
JP2011533493A Expired - Fee Related JP5385984B2 (ja) 2008-10-28 2009-10-26 マルチキャストルートを算出する方法
JP2013209161A Pending JP2014039314A (ja) 2008-10-28 2013-10-04 リンクステートプロトコルにより制御されるネットワークにおいて転送状態を算出する装置及び方法

Family Applications After (1)

Application Number Title Priority Date Filing Date
JP2013209161A Pending JP2014039314A (ja) 2008-10-28 2013-10-04 リンクステートプロトコルにより制御されるネットワークにおいて転送状態を算出する装置及び方法

Country Status (9)

Country Link
US (3) US8005016B2 (ja)
EP (1) EP2342864A4 (ja)
JP (2) JP5385984B2 (ja)
KR (1) KR20110079689A (ja)
CN (2) CN102197625B (ja)
BR (1) BRPI0919634A2 (ja)
CA (1) CA2742775A1 (ja)
RU (1) RU2517431C2 (ja)
WO (1) WO2010048698A1 (ja)

Families Citing this family (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8005016B2 (en) * 2008-10-28 2011-08-23 Nortel Networks Limited Provider link state bridging (PLSB) computation method
US8780696B2 (en) * 2008-11-17 2014-07-15 Telefonaktiebolaget L M Ericsson (Publ) System and method of implementing lightweight not-via IP fast reroutes in a telecommunications network
GB2469467B (en) * 2009-04-14 2015-05-20 Skype Optimising communications
US8619785B2 (en) * 2009-04-28 2013-12-31 Ciena Corporation Pre-computing alternate forwarding state in a routed ethernet mesh network
US8627137B1 (en) 2010-09-16 2014-01-07 Cisco Technology, Inc. Graceful handling of critical traffic blackholing faults
WO2014041811A1 (en) * 2012-09-13 2014-03-20 Nec Corporation Control apparatus, control method, communication system, and program
US9413637B2 (en) * 2012-10-22 2016-08-09 Avaya Inc. Architecture for virtualization and distribution of routing information used in a transport network
US9904721B1 (en) * 2013-01-25 2018-02-27 Gravic, Inc. Source-side merging of distributed transactions prior to replication
US9306856B2 (en) * 2013-03-15 2016-04-05 Cisco Technology, Inc. Optimal tree root selection for trees spanning multiple sites
CN107682415A (zh) * 2017-09-20 2018-02-09 郑州云海信息技术有限公司 一种对等网络传输邻居节点选择的方法及系统
US11671329B2 (en) 2018-04-04 2023-06-06 Arista Networks, Inc. Computation of network flooding topologies
US11218399B2 (en) 2018-06-20 2022-01-04 Arista Networks, Inc. Embedded area abstraction
US11296948B2 (en) * 2020-01-09 2022-04-05 Arista Networks, Inc. Topology partition detection
CN112787688A (zh) * 2020-12-31 2021-05-11 广东电网有限责任公司电力调度控制中心 一种组播树节点通信方法及装置

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2422508A (en) * 2004-04-06 2006-07-26 Nortel Networks Ltd Establishing network connections
US20070165657A1 (en) * 2005-10-05 2007-07-19 Nortel Networks Limited Multicast implementation in a link state protocol controlled Ethernet network

Family Cites Families (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4912656A (en) * 1988-09-26 1990-03-27 Harris Corporation Adaptive link assignment for a dynamic communication network
US6374311B1 (en) * 1991-10-01 2002-04-16 Intermec Ip Corp. Communication network having a plurality of bridging nodes which transmit a beacon to terminal nodes in power saving state that it has messages awaiting delivery
US7917145B2 (en) * 1992-11-02 2011-03-29 Broadcom Corporation Radio frequency local area network
US6667956B2 (en) * 1998-05-01 2003-12-23 Nortel Networks Limited Multi-class network
US6603769B1 (en) * 1998-05-28 2003-08-05 Cisco Technology, Inc. Method and system for improving traffic operation in an internet environment
AU6255199A (en) * 1998-09-17 2000-04-17 Tod Mcnamara System and method for network flow optimization using traffic classes
US6330605B1 (en) * 1998-11-19 2001-12-11 Volera, Inc. Proxy cache cluster
US20030026268A1 (en) * 2000-11-28 2003-02-06 Siemens Technology-To-Business Center, Llc Characteristic routing
US7096448B2 (en) * 2001-01-19 2006-08-22 Cadence Design Systems, Inc. Method and apparatus for diagonal routing by using several sets of lines
US7633942B2 (en) * 2001-10-15 2009-12-15 Avaya Inc. Network traffic generation and monitoring systems and methods for their use in testing frameworks for determining suitability of a network for target applications
US8031630B2 (en) 2003-03-03 2011-10-04 Alcatel Lucent Method and apparatus for updating provider domain due to customer TCNs
US7283552B2 (en) * 2003-04-30 2007-10-16 Lucent Technologies Inc. Method of scheduling bursts of data for transmission in a communication network
EP1571789A1 (en) * 2004-03-05 2005-09-07 Siemens Aktiengesellschaft Probabilistic link selection in routing algorithm
US20070036178A1 (en) * 2005-02-02 2007-02-15 Susan Hares Layer 2 virtual switching environment
KR100850912B1 (ko) * 2005-06-15 2008-08-07 삼성전자주식회사 무선통신시스템에서 전력 절약 장치 및 방법
EP1943782B1 (en) 2005-10-05 2012-03-28 Nortel Networks Limited Provider link state bridging
CN101310482B (zh) * 2005-10-11 2011-06-08 艾利森电话股份有限公司 生成生成树的方法
US20080107027A1 (en) * 2006-11-02 2008-05-08 Nortel Networks Limited Engineered paths in a link state protocol controlled Ethernet network
US8223668B2 (en) 2006-12-14 2012-07-17 Rockstar Bidco Lp Method and apparatus for exchanging routing information and the establishment of connectivity across multiple network areas
US20080159290A1 (en) * 2006-12-28 2008-07-03 Futurewei Technologies, Inc. Method of Preventing Transport Leaks in Hybrid Switching Networks
US7792050B2 (en) * 2007-10-26 2010-09-07 Motorola, Inc. Method for intelligent merging of ad hoc network partitions
US8005016B2 (en) * 2008-10-28 2011-08-23 Nortel Networks Limited Provider link state bridging (PLSB) computation method

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2422508A (en) * 2004-04-06 2006-07-26 Nortel Networks Ltd Establishing network connections
US20070165657A1 (en) * 2005-10-05 2007-07-19 Nortel Networks Limited Multicast implementation in a link state protocol controlled Ethernet network

Also Published As

Publication number Publication date
US8005016B2 (en) 2011-08-23
US20100103846A1 (en) 2010-04-29
JP2014039314A (ja) 2014-02-27
BRPI0919634A2 (pt) 2015-12-01
EP2342864A1 (en) 2011-07-13
KR20110079689A (ko) 2011-07-07
US20110292838A1 (en) 2011-12-01
US20140105071A1 (en) 2014-04-17
US8605627B2 (en) 2013-12-10
CN102197625B (zh) 2014-04-02
JP5385984B2 (ja) 2014-01-08
EP2342864A4 (en) 2012-03-07
WO2010048698A1 (en) 2010-05-06
RU2517431C2 (ru) 2014-05-27
RU2011121621A (ru) 2012-12-10
CN102197625A (zh) 2011-09-21
CA2742775A1 (en) 2010-05-06
CN103795628A (zh) 2014-05-14

Similar Documents

Publication Publication Date Title
JP5385984B2 (ja) マルチキャストルートを算出する方法
US12034632B2 (en) Fault protection method, node, and storage medium
EP1859561B1 (en) Algorithm for backup pe selection
US8199755B2 (en) Method and apparatus establishing forwarding state using path state advertisements
EP3200402B1 (en) Segment routing information obtainment method and segment routing network establishment method
EP2761827B1 (en) Incremental deployment of mrt based ipfrr
EP1820300B1 (en) Fast reroute (frr) protection at the edge of a rfc 2547 network
Lazzeri et al. Efficient label encoding in segment-routing enabled optical networks
US20100208733A1 (en) System and Method for Point to Multipoint Inter-Domain Multiprotocol Label Switching Traffic Engineering Path Calculation
CN104396197B (zh) 在802.1aq网络中使用分离的平局打破器在等成本最短路径之间选择
US8837329B2 (en) Method and system for controlled tree management
US9712426B2 (en) Multi-domain routing computation method and device, path computation element and routing network
CN113615132A (zh) 快速泛洪拓扑保护
CN106209625B (zh) 一种在分布式网络中支持集中控制的高效方法
Nagabhushanam et al. Enhancement in Loop Prevention Protocols: Dynamic Per-VLAN Multi-shortest Path Bridging (DV-MPB)
CN114513445B (zh) 一种发送报文的方法及装置
CN114050993B (zh) 基于接入侧的安全可信路径主动选择方法和装置
Faghani et al. Shortcut switching strategy in metro Ethernet networks
Balaraju et al. Avoid Link Failure Using Novel Re-routing Method

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20121019

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20130910

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20131004

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

LAPS Cancellation because of no payment of annual fees