(57)【特許請求の範囲】
【請求項１】
ネットワークにおける送信元ルート選択転送のための方法であって、
ドメイン内のエッジノードにより、インタードメイン経路を介してデータパケットを受信するステップであって、前記データパケットには、送信元ルートホップリストを伝送するパケットヘッダが付加され、前記送信元ルートホップリストは、イントラドメイン経路セグメントに従って個々のホップを指定することなく、前記イントラドメイン経路セグメントの経路識別子を指定し、前記イントラドメイン経路セグメントは、前記ドメインを介して広がる前記インタードメイン経路の一部分である、ステップと、
前記エッジノードにより、前記経路識別子に関連付けられたホップリストを識別するステップであって、前記ホップリストは、前記イントラドメイン経路セグメントに従って一連のホップを指定する、ステップと、
前記パケットヘッダ中で前記経路識別子を前記ホップリストに置き換えるステップと、
前記ホップリストに従って、前記データパケットを前記イントラドメイン経路セグメントの次のホップに転送するステップと
を有し、
前記経路識別子をホップリストに関連付けるエントリが、前記ドメイン内のエッジノードに格納された転送テーブル内に記憶され、
前記方法は、
前記データパケットを前記イントラドメイン経路セグメントの前記次のホップに転送する前記ステップの後に、前記エッジノードにより、コントローラから制御メッセージを受信するステップであって、前記制御メッセージは、前記エントリを前記転送テーブルから除去するように前記エッジノードに命令する、ステップと
をさらに有する、方法。
【請求項２】
前記経路識別子に関連付けられたホップリストを識別する前記ステップが、
前記経路識別子を前記ホップリストに関連付けるエントリを、前記エッジノードに格納された転送テーブルから見つけ出すステップを含む、請求項１に記載の方法。
【請求項３】
前記エッジノードは、前記データパケットの受信と前記データパケットの転送との間の期間に外部のデバイスに問合せを行うことなく、前記ホップリストを識別する、請求項２に記載の方法。
【請求項４】
インタードメイン経路を介してデータパケットを受信する前記ステップよりも前に、前記エッジノードにより、前記コントローラから他の制御メッセージを受信するステップであって、前記他の制御メッセージは、前記エントリを前記転送テーブルに書き込むように前記エッジノードに命令する、ステップ
をさらに有する、請求項３に記載の方法。
【請求項５】
前記データパケットがデータを伝送し、
前記データパケットを前記イントラドメイン経路セグメントの前記次のホップに転送する前記ステップが、前記ネットワークのデータプレーンを介して前記データパケットを転送するステップを含む、請求項１に記載の方法。
【請求項６】
前記経路識別子の長さは、前記ホップリストの長さよりも短い、請求項１に記載の方法。
【請求項７】
前記経路識別子が、マルチプロトコル・ラベル・スイッチング（ＭＰＬＳ）ラベルを含む、請求項１に記載の方法。
【請求項８】
ドメイン内のエッジノードであって、
プロセッサと、
前記プロセッサによる実行のためのプログラムを格納した、コンピュータ読み取り可能な記憶媒体と
を具備し、
前記プログラムは、
インタードメイン経路を介してデータパケットを受信するための命令であって、前記データパケットには、送信元ルートホップリストを伝送するパケットヘッダが付加され、前記送信元ルートホップリストは、イントラドメイン経路セグメントに従って個々のホップを指定することなく、前記イントラドメイン経路セグメントの経路識別子を指定し、前記イントラドメイン経路セグメントは、前記ドメインを介して広がる前記インタードメイン経路の一部分である、命令と、
前記経路識別子に関連付けられたホップリストを識別するための命令であって、前記ホップリストは、前記イントラドメイン経路セグメントに従って一連のホップを指定する、命令と、
前記パケットヘッダ中で前記経路識別子を前記ホップリストに置き換えるための命令と、
前記ホップリストに従って、前記データパケットを前記イントラドメイン経路セグメントの次のホップに転送するための命令と
を含み、
前記経路識別子をホップリストに関連付けるエントリが、前記ドメイン内のエッジノードに格納された転送テーブル内に記憶され、
前記プログラムは、
前記データパケットを前記イントラドメイン経路セグメントの前記次のホップに転送した後に、コントローラから制御メッセージを受信する命令であって、前記制御メッセージは、前記エントリを前記転送テーブルから除去するように前記エッジノードに命令する、命令
をさらに含む、エッジノード。
【請求項９】
前記経路識別子に関連付けられたホップリストを識別するための前記命令が、
前記経路識別子を前記ホップリストに関連付けるエントリを、前記エッジノードに格納された転送テーブルから見つけ出すための命令を含む、請求項８に記載のエッジノード。
【請求項１０】
送信元ルート選択転送の方法であって、
コントローラにより、送信元ノードと宛先ノードとの間のインタードメイン経路を計算する要求を受信するステップと、
前記コントローラにより、ドメインを介して広がるイントラドメイン経路セグメントの経路識別子を取得するステップであって、前記イントラドメイン経路セグメントは、前記インタードメイン経路の一部分である、ステップと、
前記イントラドメイン経路セグメントに従って個々のホップを指定することなく、前記経路識別子を指定する送信元ルートホップリストを作成するステップと、
前記送信元ルートホップリストをデバイスに送信するステップであって、前記送信元ルートホップリストは、前記インタードメイン経路を介してデータパケットがやりとりされるよりも前に、前記送信元ノードにおいて前記データパケットに付加されるように構成される、ステップと
を有し、
前記経路識別子をホップリストに関連付けるエントリが、前記ドメイン内のエッジノードに格納された転送テーブル内に記憶され、
前記方法は、
前記インタードメイン経路を介して前記データパケットが伝送された後に、前記エッジノードに制御メッセージを送信するか、又は送信するように他のコントローラを促すステップをさらに有し、
前記制御メッセージは、前記エントリを前記転送テーブルから除去するように前記エッジノードに命令する、方法。
【請求項１１】
前記経路識別子は、前記イントラドメイン経路セグメントに沿った個々のホップについての情報を含まない、請求項１０に記載の方法。
【請求項１２】
前記ドメイン内のエッジノードに他の制御メッセージを送信するか、又は送信するように他のコントローラを促すステップをさらに有し、
前記他の制御メッセージは、前記経路識別子をホップリストに関連付けるエントリを転送テーブルに書き込むようにエッジノードに命令し、
前記ホップリストは、前記イントラドメイン経路セグメントに従って一連のホップを指定する、請求項１０に記載の方法。
【請求項１３】
前記他の制御メッセージは、前記インタードメイン経路を介して前記データパケットがやりとりされるよりも前に、前記エッジノードに送信される、請求項１２に記載の方法。
【請求項１４】
コントローラであって、
プロセッサと、
前記プロセッサによる実行のためのプログラムを格納した、コンピュータ読み取り可能な記憶媒体と
を具備し、
前記プログラムは、
送信元ノードと宛先ノードとの間のインタードメイン経路を計算する要求を受信するための命令と、
ドメインを介して広がるイントラドメイン経路セグメントの経路識別子を取得するための命令であって、前記イントラドメイン経路セグメントは、前記インタードメイン経路の一部分である、命令と、
前記イントラドメイン経路セグメントに従って個々のホップを指定することなく、前記経路識別子を指定する送信元ルートホップリストを作成するための命令と、
前記送信元ルートホップリストをデバイスに送信するための命令であって、前記送信元ルートホップリストは、前記インタードメイン経路を介してデータパケットがやりとりされるよりも前に、前記送信元ノードにおいて前記データパケットに付加されるように構成される、命令と
を含み、
前記経路識別子をホップリストに関連付けるエントリが、前記ドメイン内のエッジノードに格納された転送テーブル内に記憶され、
前記プログラムは、
前記インタードメイン経路を介して前記データパケットが伝送された後に、前記エッジノードに制御メッセージを送信するか、又は送信するように他のコントローラを促す命令をさらに含み、
前記制御メッセージは、前記エントリを前記転送テーブルから除去するように前記エッジノードに命令する、コントローラ。
【発明の詳細な説明】
【技術分野】
【０００１】
この出願は、２０１４年１月２０日付けで出願された「Multi-Domain Source Routed Forwarding Based on Collaborating Network Controllers」と題した米国仮出願第１４／１５９，０７２号の優先権を主張するものであり、引用により、上記米国出願の内容が本出願に組み込まれる。
【０００２】
本発明は、広くは、遠隔通信ネットワークに関し、詳細な実施態様においては、協働するネットワークコントローラに基づくマルチドメイン送信元ルート選択転送のための技術及び仕組みに関する。
【背景技術】
【０００３】
送信元ルート選択転送は、パケットの送信者に、そのパケットがネットワークを流れるルートを部分的に又は完全に指定させる。これは、送信元にトラフィックフロー経路を直接管理させることによって、パケットの再発送や輻輳が削減されるという点で有利となる。一般には、送信元ルート選択転送は、送信元ルート選択経路の個々のホップを指定する送信元ルートホップリストを用いて実現される。送信元ルートホップリストは、送信元ノードにおいてパケットヘッダ内にカプセル化され、パケットの転送を目的として、次のホップを決定するために各中間ノードによって使用される。従来の送信元ルート選択転送技術は、多くの場合、送信元と宛先との間のホップ数が比較的少ない小規模なネットワークに対して有効である。しかしながら、伝統的な送信元ルート選択転送技術は、長いパケットヘッダがオーバーヘッド割合を増大させる大規模なネットワークに対してはやや有効でない。さらに、送信元ルート選択転送は、送信元が外部のドメイントポロジの知識を有しないマルチドメインネットワークには適用できない。したがって、大規模な及び／又はマルチドメインのネットワークに対して送信元ドメインルーティングを効果的に拡張するための技術が必要とされている。
【発明の概要】
【課題を解決するための手段】
【０００４】
概して、技術的利点は、協働するネットワークコントローラに基づくマルチドメイン送信元ルート選択転送のための技術及び仕組みについて記述したこの開示の実施態様によって得られる。
【０００５】
一実施態様によれば、マルチドメインネットワークにおける送信元ルート選択転送のための方法が提供される。この例では、方法は、インタードメイン経路を介してデータパケットを受信するステップを有する。データパケットには、送信元ルートホップリストを伝送するパケットヘッダが付加される。送信元ルートホップリストは、イントラドメイン経路セグメントに従って個々のホップを指定することなく、イントラドメイン経路セグメントの経路識別子を指定する。イントラドメイン経路セグメントは、ドメインを介して広がるインタードメイン経路の一部分である。方法は、経路識別子に関連付けられたホップリストを識別するステップと、送信元ルートホップリスト中で経路識別子をホップリストに置き換えるステップと、データパケットを次のホップに転送するステップとをさらに有する。また、この方法を実行するための装置が提供される。
【０００６】
別の実施態様によれば、送信元ルート選択転送のための方法が提供される。この例では、方法は、送信元ノードと宛先ノードとの間のインタードメイン経路を計算する要求を受信するステップと、ドメインを介して広がるイントラドメイン経路セグメントの経路識別子を取得するステップとを有する。イントラドメイン経路セグメントは、インタードメイン経路の一部分である。方法は、イントラドメイン経路セグメントに従って個々のホップを指定することなく、経路識別子を指定する送信元ルートホップリストを作成するステップと、送信元ルートホップリストをデバイスに送信するステップとをさらに有する。送信元ルートホップリストは、インタードメイン経路を介してデータパケットがやりとりされるよりも前に、送信元ノードにおいてデータパケットに付加されるように構成される。また、この方法を実行するための装置が提供される。
【０００７】
本開示及びその利点のより完全な理解のために、以下では、添付の図面を参照して詳細な説明がなされる。
【図面の簡単な説明】
【０００８】
【図１Ａ】一実施形態による通信ネットワークを示す図である。
【図１Ｂ】一実施形態による通信ネットワークを示す図である。
【図２】従来技術による、ネットワークを介して広がる送信元ルート選択経路を示す図である。
【図３】従来技術による送信元ルート選択経路のための送信元ルートホップリストを示す図である。
【図４】一実施形態による、マルチドメインネットワークを介して広がるインタードメイン送信元ルート選択経路を示す図である。
【図５Ａ】一実施形態による、インタードメイン送信元ルート選択経路を介してパケットが転送されるように修正される送信元ルートホップリストを示す図である。
【図５Ｂ】一実施形態による、インタードメイン送信元ルート選択経路を介してパケットが転送されるように修正される送信元ルートホップリストを示す図である。
【図５Ｃ】一実施形態による、インタードメイン送信元ルート選択経路を介してパケットが転送されるように修正される送信元ルートホップリストを示す図である。
【図５Ｄ】一実施形態による、インタードメイン送信元ルート選択経路を介してパケットが転送されるように修正される送信元ルートホップリストを示す図である。
【図５Ｅ】一実施形態による、インタードメイン送信元ルート選択経路を介してパケットが転送されるように修正される送信元ルートホップリストを示す図である。
【図５Ｆ】一実施形態による、インタードメイン送信元ルート選択経路を介してパケットが転送されるように修正される送信元ルートホップリストを示す図である。
【図６】別の実施形態による、マルチドメインネットワークを介して広がるインタードメイン送信元ルート選択経路を示す図である。
【図７】一実施形態による、インタードメイン送信元ルート選択経路を確立するための通信シーケンスを示すプロトコル図である。
【図８】一実施形態による、インタードメイン送信元ルート選択転送を実現するための方法を示すフロー図である。
【図９】別の実施形態による、インタードメイン送信元ルート選択転送を実現するための方法を示すフロー図である。
【図１０】さらに別の実施形態による、インタードメイン送信元ルート選択転送を実現するための方法を示すフロー図である。
【図１１】一実施形態によるネットワークデバイスを示す図である。
【図１２】一実施形態による演算プラットフォームを示す図である。
【発明を実施するための形態】
【０００９】
通常、異なる図面中の対応する番号及び記号は、特に指定されない限り、対応する部位を指す。図面は、実施形態の関連性のある様相を明瞭に示すように描かれたものであって、必ずしも正確な縮尺で描かれてはいない。
【００１０】
以下、この開示の実施形態の作成法及び使用法について詳細に説明する。しかしながら、明細書中に開示される概念は、多種多様な特定の文脈で具体化できるのであって、明細書中に開示される特定の実施形態は、例示に過ぎず、特許請求の範囲を限定するためのものではないことを理解されたい。さらに、添付の特許請求の範囲によって規定されるこの開示の精神及び範囲から逸脱することなく、さまざまな変更形態、置換形態及び代替形態が形成可能であることを理解されたい。
【００１１】
この開示の諸態様は、送信元ノードにおいてパケットヘッダ中のイントラドメインホップリストの代わりに経路識別子を使用することによって、マルチドメインネットワークにおける効率の良い／拡張性のある送信元ルート選択転送を実現する。したがって、経路識別子（例えば、ラベル、アドレス等）は、対応するイントラドメイン経路セグメントを介してパケットが転送されるように、対応するドメインのイングレスエッジノードにパケットが到達したとき、イントラドメインホップリストに取り換えられる。特に、経路識別子は、イントラドメイン経路セグメントに従って個々のホップを指定せず、したがって、典型的に、イントラドメインホップリストよりも短いものとなる（例えば、数ビットからなる）。ここで提供される送信元ルート選択転送技術の実施形態を実現するために、対応するドメインのエッジノードの転送テーブルは、経路識別子を対応するイントラドメインホップリストに関連付けるように更新される。転送テーブルエントリは、インタードメイン経路計算の後に転送テーブルに書き込まれてよく、経路の解体中に転送テーブルから除去されてよい。以下、この開示のこれらの及びその他の態様についてさらに詳細に説明する。
【００１２】
図１Ａ及び図１Ｂは、複数のドメイン１１０，１２０，１３０，１４０と、複数のコアノード１１２，１２２，１３２，１４２と、複数のエッジノード１１４，１２４，１３４，１４４と、複数のドメインコントローラ１１６，１２６，１３６，１４６と、ルートコントローラ１５０とを含む、一実施形態のマルチドメインネットワーク１００を示す。図１Ａに示されるように、マルチドメインネットワーク１００は、個々のドメイン１１０，１２０，１３０，１４０のコアノード１１２，１２２，１３２，１４２とエッジノード１１４，１２４，１３４，１４４との間の相互接続によって形成されるデータプレーン（実線）を有する。図１Ｂに示されるように、マルチドメインネットワーク１００は、ルートコントローラ１５０と、ドメインコントローラ１１６，１２６，１３６，１４６と、コア／エッジノード１１２−１１４，１２２−１２４，１３２−１３４，１４２−１４４との間に形成されるコントロールプレーン（破線）を有する。
【００１３】
コアノード１１２，１２２，１３２，１４２は、各自のドメイン１１０，１２０，１３０，１４０内でイントラドメインルーティングを実行するように構成された任意のデータプレーン要素であってよい。一例として、コアノード１１２，１２２，１３２，１４２は、各自のドメイン１１０，１２０，１３０，１４０のイントラドメイントポロジの知識を有し得るが、他のドメインのインタードメインリンク及び／又はトポロジについての知識は有し得ない。エッジノード１１４，１２４，１３４，１４４は、ドメイン１１０，１２０，１３０，１４０への参加を提供又は規制するように構成されたデータプレーン要素であってよく、イントラドメイン及びインタードメインの両方のルーティング機能を有してよい。いくつかの実施形態において、各自のドメイン１１０，１２０，１３０，１４０のイントラドメイントポロジの知識だけでなく、例えば、隣接するドメインのエッジ構成要素の知識等、少なくともいくらかのインタードメインリンクの知識を有する。ドメインコントローラ１１６，１２６，１３６，１４６は、各自のドメイン１１０，１２０，１３０，１４０に対するイントラドメイン経路セグメントを計算可能な任意のコントロールプレーンエンティティであってよい。ルートコントローラ１５０は、例えば、ドメインコントローラ１１６，１２６，１３６，１４６によって計算されるイントラドメイン経路セグメントを集約し、インタードメインリンクを選択する等、インタードメイン経路を計算／生成可能な任意のコントロールプレーンエンティティであってよい。ここで使用される用語（ルート、ドメイン、その他の）「コントローラ（controller）」は、マルチドメイン送信元ルート選択転送を実現するように構成された任意のコントロールプレーンエンティティを指す。いくつかの実施形態において、ルートコントローラは、インタードメイン経路計算機能を有し、ドメインコントローラは、イントラドメイン経路計算機能を有する。コントローラは、スタンドアロン型のデバイスであってよく、又は他のネットワークデバイスと共同設置されてもよい。例えば、コントローラがエッジノード中のモジュールであったり、ドメインコントローラがルートコントローラと共同設置されたりなどしてもよい。
【００１４】
従来の送信元ルート選択転送技術は、典型的に送信元にネットワーク全体のトポロジ知識を要求するので、大規模ネットワークでの実施が困難となり得る。図２は、経路２０１が送信元２１１から宛先２３９に伸びるネットワーク２００を示す。従来の送信元ルート選択転送技術が使用される場合、送信元２１１は、送信元ルート選択経路のホップ１〜１１の各々の知識を含むネットワーク２００全体のトポロジ知識を有する必要があった。また、従来の送信元ルート選択転送技術は、非常に長い送信元ルートホップリストがデータパケットヘッダにおいてオーバーヘッドを著しく増大させるので、大規模ネットワークには効果的でなかった。図３は、従来の送信元ルーティング技術を使用した場合に生成されるであろう、経路２１０に対する送信元ルートホップリスト２５０を示す。図示されるように、経路２０１中のホップ１〜１１の各々が、送信元ルートホップリスト２０５において指定される。さらに、従来の送信元ルート選択転送技術は、送信元ノードが外部のドメインのトポロジ知識を有しないマルチドメインネットワークに適さない。
【００１５】
この開示の諸態様は、大規模な又はマルチドメインのネットワークにおける、効率がよく、かつ拡張性のある送信元ルーティングを実現するために、送信元ルートホップリストにおいて経路識別子を使用する。図４は、インタードメイン送信元ルート選択経路４０１が送信元４００から宛先４３９に伸びる、一実施形態のネットワーク４００を示す。示されるように、この実施形態のネットワーク４００は、複数のドメイン４１０，４２０，４３０と、複数のエッジノード４１９，４２１，４２９，４３１と、複数のコアノード４１５，４２５，４３５と、コントローラ４９０とを含む。この例では、経路識別子ＰＩＤ２及びＰＩＤ３が、ドメイン４２０，４３０のイントラドメイン経路セグメントを表すために使用され、これは、図５Ａに図示される送信元ルートホップリスト４５０中に見出すことができる。コントローラ４９０は、インタードメイン経路計算を実行して、インタードメイン送信元ルート選択経路４０１を計算する。その後、コントローラ４９０は、エッジノード４２１，４３１に、経路識別子ＰＩＤ２及びＰＩＤ３をドメイン４２０，４３０のイントラドメイン経路セグメントに対応するイントラドメインホップリストにそれぞれ関連付けるように各自の転送テーブルを更新するように命令する。具体的には、経路識別子ＰＩＤ２をイントラドメインホップリスト５−６−７に関連付けるために、エントリがエッジノード４２１において転送テーブルに書き込まれ、同時に、経路識別子ＰＩＤ３をイントラドメインホップリスト９−１０−１１に関連付けるために、エントリがエッジノード４３１において転送テーブルに書き込まれる。エッジノード４２１，４３１は、（それぞれ）ドメイン４２０，４３０に対するイングレス（進入）エッジノードであり、経路識別子ＰＩＤ２，ＰＩＤ３を伝送するパケットを受信したとき、これらの識別子を対応するイントラドメインホップリスト５−６−７，９−１０−１１に（それぞれ）置き換えるように構成される。ここで使用されたように、用語「送信元ルート選択経路（source routed path）」は、確立される任意の経路を指すか、又はその他、送信元ルート選択転送の原理と共に使用される。用語「送信元ルートホップリスト（source route hop list）」は、送信元ルート選択経路に関連したホップリストを指す。用語「イントラドメインホップリスト（intra-domain hop list）」は、イントラドメイン経路セグメント、例えば、ドメインを介して広がる送信元ルート選択経路のセグメントに関連したホップリストを指す。
【００１６】
図５Ａから図５Ｆは、パケットがインタードメイン送信元ルート選択経路４０１を介して転送されるよう、どのように送信元ルートホップリスト４５０が修正されるかを示す。図５Ａに示されるように、送信元ルートホップリスト４５０は、経路識別子ＰＩＤ２及びＰＩＤ３を含む。その後、図５Ｂに実際に示されるように、パケットが送信元４１１からエッジノード４２１に転送されるので、個々のホップ１−２−３−４は、送信元ルートホップリスト４５０から１つずつ除去される。次いで、エッジノード４２１は、ドメイン４２０を介して広がるイントラドメイン経路セグメントを介してパケットを送信するよりも前に、（図５Ｃに示されるように）ＰＩＤ２をイントラドメインホップリスト５−６−７に置き換える。パケットがエッジノード４２１からエッジノード４３１に転送されるので、個々のホップ５−６−７−８は、（図５Ｄに示されるように）送信元ルートホップリスト４５０から１つずつ除去される。パケットを受信したとき、エッジノード４３１は、（図５Ｅに示されるように）送信元ルートホップリスト４５０中のＰＩＤ３をイントラドメインホップリスト９−１０−１１に置き換え、修正されたパケットをドメイン４３０内の次のホップノード４３５に転送する。最後に、パケットがドメイン４３０を介して宛先４３９に転送されるので、個々のホップ９−１０−１１は、送信元ルートホップリスト４５０から１つずつ除去される。
【００１７】
いくつかの実施形態において、イントラドメイン経路セグメントは、分散したコントローラによって計算されてよい。図６は、インタードメイン経路６０１のイントラドメインセグメントがドメインコントローラ６１６，６２６，６３６によって計算される、一実施形態のネットワーク６００を示す。ドメインコントローラ６１６，６２６，６３６は、分散したコントローラであってよい。あるいは、ドメインコントローラ６１６，６２６，６３６は、ルートコントローラと共同設置されてもよい。この例では、ドメインコントローラ６１６，６２６，６３６は、各自のドメイン６１０，６２０，６３０のイントラドメインセグメントを計算する責任を負い、ルートコントローラ６９０は、イントラドメイン経路セグメントとインタードメインリンク４，８とを集約して、インタードメイン経路６０１を形成する責任を負う。また、ドメインコントローラ６１６，６２６，６３６は、各自のドメイン６１０，６２０，６３０内のデータプレーンエンティティとやりとりを行う責任を負う。例えば、ドメインコントローラ６２６，６３６は、エッジノード６２１，６３１に、エンティティを、各自の転送テーブルに書き込むように及び／又は各自の転送テーブルから除去するように（それぞれ）命令してよい。別の実施形態において、ドメインコントローラ６１６は、送信元６１１とルートコントローラ６９０との間でインタードメイン経路計算要求／応答を中継してよい。あるいは、送信元ルート選択経路計算要求／応答は、送信元６１１とルートコントローラ６９０との間で直接計算されてもよい。
【００１８】
図７は、インタードメイン経路６０１を確立するための通信シーケンス７００を示す。示されるように、通信シーケンス７００は、インタードメイン経路計算要求７１０が送信元６１１からルートコントローラ６９０に送信されるときに開始される。その後、ルートコントローラ６９０は、インタードメイン経路計算要求７１０を複数のイントラドメイン経路計算要求７２０に分解し、これらは、ドメインコントローラ６１６，６２６，６３６に転送される。イントラドメイン経路計算要求７２０の各々は、対応するドメインコントローラに割り当てられたドメインを介したイントラドメイン経路セグメントの計算を要求し得る。ドメインコントローラ６１６，６２６，６３６は、対応するイントラドメイン経路セグメントを計算する。各イントラドメイン経路セグメントは、イントラドメインホップリストに関連付けられるか、又はそれによって規定される。イントラドメインホップリストは、イントラドメイン経路セグメントに従って個々のホップのシーケンスを指定する。ドメインコントローラ６１６，６２６，６３６は、経路識別子をイントラドメインホップリストに関連付け、次いで、制御命令７３０をエッジノード６２１，６３１に伝達する。制御命令７３０は、イングレスエッジノード６２１，６３１に、経路識別子をイントラドメインホップリストに関連付けるエントリを各自の転送テーブルに書き込むように命令する。その後、ドメインコントローラ６１６，６２６，６３６は、イントラドメインホップリスト及び／又は経路識別子を示すイントラドメイン経路計算応答７４０をルートコントローラ６９０に伝達する。一実施形態において、イントラドメイン経路計算応答７４０は、ドメイン６１０に対するイントラドメインホップリストと、ドメイン６２０及びドメイン６３０に対する経路識別子とを指定する。イントラドメイン経路計算応答７４０を受信したとき、ルートコントローラ６９０は、イントラドメイン経路セグメントをインタードメイン送信元ルート選択経路に集約して、インタードメイン経路に対する送信元ルートホップリストを作成する。一実施形態において、送信元ルートホップリストは、ドメイン６１０に対応するイントラドメインホップリストと、それに続くインタードメインホップ４と、それに続くドメイン６２０に対応する経路識別子と、それに続くインタードメインホップ８と、それに続くドメイン６３０に対応する経路識別子とを含む。ルートコントローラ６９０は、送信元ルートホップリストを指定するインタードメイン経路計算応答７５０を送信元６１１に伝達する。ここで、送信元ルートホップリストは、インタードメイン経路を介してパケットを転送するために使用される。パケットのやりとりが完了すると、ルートコントローラ６９０は、ドメインコントローラ６１６，６２６，６３６に解体命令７７０を伝達する。解体命令７７０は、インタードメイン経路が解体されることを示し、制御命令７８０をエッジノード６２１，６３１に送信するよう、ドメインコントローラ６１６，６３６を促す。制御命令７８０は、エッジノード６２１，６３１に、前に追加したエントリを各自の転送テーブルから除去するように命令する。
【００１９】
この開示の諸態様は、明細書中に記載されるマルチドメイン送信元ルート選択転送技術に従ってエッジノードを動作させるための方法を提供する。図８は、エッジノードによって実行されるもののような、マルチドメインネットワークにおける送信元ルート選択転送を実現するための方法８００を示す。示されるように、方法８００は、ステップ８１０から開始され、ここで、エッジノードは、経路識別子をイントラドメインホップリストに関連付けるエントリをデータベースに書き込むための命令を受信する。次いで、方法８００は、ステップ８２０に進行し、ここで、エッジノードは、経路識別子をイントラドメインホップリストに関連付けるエントリを転送テーブルに書き込む。続いて、方法８００は、ステップ８３０に進行し、エッジノードは、経路識別子を指定する送信元ルートホップリストを伝送するパケットを受信する。次いで、方法８００は、ステップ８４０に進行し、ここで、エッジノードは、経路識別子を関連するイントラドメインホップリストに置き換えることによって、パケット中の送信元ルートホップリストを修正する。その後、方法８００は、ステップ８５０に進行し、ここで、エッジノードは、修正した送信元ルートホップリストによって指定された通りに、パケットを次のホップに転送する。ステップ８３０〜８５０は、経路識別子をイントラドメインホップリストに関連付けるエントリがエッジノードの転送テーブルに存在するうちは、経路識別子を伝送するパケット毎に繰り返されてよい。サービスフローに関係するすべてのパケットがインタードメイン経路を介して送信されたとき、方法８００は、ステップ８６０に進行し、ここで、エッジノードは、対応するエントリ（例えば、ステップ８２０の間に追加されたエントリ）を転送テーブルから除去するための命令を受信する。最後に、方法８００は、ステップ８７０に進行し、ここで、エッジノードは、対応するエントリを転送テーブルから除去する
【００２０】
この開示の諸態様は、明細書中に記載されるマルチドメイン送信元ルート選択転送技術に従ってコントローラを動作させるための方法を提供する。図９は、ドメインコントローラによって実行されるもののような、マルチドメインネットワークにおける送信元ルート選択転送を実現するための方法９００を示す。示されるように、方法９００は、ステップ９１０から開始され、ここで、ドメインコントローラは、ルートコントローラからイントラドメイン経路計算要求を受信する。その後、方法９００は、ステップ９２０に進行し、ここで、ドメインコントローラは、イントラドメイン経路セグメントを計算する。次いで、方法９００は、ステップ９３０に進行し、ここで、ドメインコントローラは、経路識別子を、計算したイントラドメイン経路セグメントのイントラドメインホップリストに関連付けるエントリを転送テーブルに書き込むように、イングレスエッジノードに命令する。続いて、方法９００は、ステップ９４０に進行し、ここで、ドメインコントローラは、経路識別子を指定するイントラドメイン経路計算応答をルートコントローラに送信する。その後、方法９００は、ステップ９５０に進行し、ここで、ドメインコントローラは、ルートコントローラから解体命令を受信する。典型的に、解体命令は、インタードメイン経路を介した通信が完了したときにやりとりされる。次いで、方法９００は、ステップ９６０に進行し、ここで、ドメインコントローラは、前に追加したエントリを転送テーブルから除去するように、イングレスノードに命令する。
【００２１】
図１０は、ルートコントローラによって実行されるもののような、マルチドメインネットワークにおける送信元ルート選択転送を実現するための方法１０００を示す。示されるように、方法１０００は、ステップ１０１０から開始され、ここで、ルートコントローラは、送信元からインタードメイン経路計算要求を受信する。いくつかの実施形態において、インタードメイン経路計算要求は、対応するドメインコントローラによってルートコントローラに中継される。別の実施形態において、インタードメイン経路計算要求は、送信元ノードから直接受信される。続いて、方法１０００は、ステップ１０２０に進行し、ここで、ルートコントローラは、ドメイン及びインタードメインリンクのシーケンスを選択することによって、インタードメイン経路を計算する。次いで、方法１０００は、ステップ１０３０に進行し、ここで、ルートコントローラは、イントラドメイン経路計算要求を対応するドメインコントローラに送信する。イントラドメイン経路計算要求は、ドメインコントローラに、各自のドメインを介するイントラドメイン経路セグメントを計算するように命令してよい。その後、方法１０００は、ステップ１０４０に進行し、ここで、ルートコントローラは、ドメインコントローラからイントラドメイン経路計算応答を受信する。イントラドメイン経路計算応答は、ドメインコントローラによって計算されたイントラドメイン経路セグメントに関連した経路識別子及び／又はイントラドメインホップリストを伝送し得る。いくつかの実施形態において、経路識別子を指定するイントラドメイン経路計算応答は、イントラドメインホップリストを含まなくてよく、その逆もまた同様である。続いて、方法１０００は、ステップ１０５０に進行し、ここで、ルートコントローラは、ドメインコントローラによって計算されたイントラドメイン経路と選択されたインタードメインリンクとを集約することによって、計算されたインタードメイン経路に対する送信元ルートホップリストを構築する。送信元ルートホップリストは、ドメインコントローラから伝達された少なくとも１つの経路識別子を含む。その後、方法１０００は、ステップ１０６０に進行し、ここで、ルートコントローラは、送信元ルートホップリストを指定するインタードメイン経路計算応答を送信元に送信する。インタードメイン経路計算応答は、送信元に直接送信されてよく、又は対応するドメインコントローラを介して中継送信されてもよい。次いで、方法１０００は、ステップ１０７０に進行し、ここで、ルートコントローラは、例えば経路解体要求を受信したときに、イントラドメイン経路を介した通信が完了したかを判定する。その後、方法１０００は、ステップ１０８０に進行し、ルートコントローラは、ドメインコントローラに解体命令を送信する。
【００２２】
図１１は、先に記載した１つ又は複数のデバイス（例えば、コントロールプレーンエンティティ、データプレーンエンティティ、ノード、コントローラ等）の等価物であってよい、一実施形態のデバイス１１００の構成図を示す。この実施形態のデバイス１１００は、プロセッサ１１０４と、メモリ１１０６と、複数のインタフェース１１１０〜１１１４とを含んでよく、これらは、図１１に示されるように配置されてよい（又はそのように配置されなくてもよい）。プロセッサ１１０４は、計算及び／又はタスクに関するその他の処理を実行可能な任意のコンポーネントであってよく、メモリ１１０６は、プロセッサ１１０４のためのプログラム及び／又は命令を格納可能な任意のコンポーネントであってよい。インタフェース１１１０，１１１２，１１１４は、この実施形態のデバイス１１００に他のネットワークデバイスとの通信を行わせる任意のコンポーネント又はそのようなコンポーネントの集合体であってよい。
【００２３】
図１２は、明細書中に開示されたデバイス又は方法を実施するために使用され得る処理システムの構成図を示す。特定のデバイスは、示されたコンポーネントのすべてを利用してよく、又はそのサブセットだけを利用してもよく、統合の水準は、デバイス毎に異なっていてよい。さらに、デバイスは、コンポーネントの複数のインスタンス、例えば、複数の処理ユニット、プロセッサ、メモリ、送信機、受信機等を含んでよい。処理システムは、１つ又は複数の入力／出力デバイス、例えば、スピーカ、マイクロフォン、マウス、タッチスクリーン、キーパッド、キーボード、プリンタ、ディスプレイ、及び同様のものなどを備えた処理ユニットを含んでよい。処理ユニットは、バスに接続された中央処理ユニット（ＣＰＵ）、メモリ、マスストレージデバイス、ビデオアダプタ、及びＩ／Ｏインタフェースを含んでよい。
【００２４】
バスは、メモリバス若しくはメモリコントローラ、周辺機器バス、ビデオバス、又は同様のものを含む任意のタイプのいくつかのバスアーキテクチャのうちの１つ又は複数であってよい。ＣＰＵは、任意のタイプの電子データプロセッサを含んでよい。メモリは、例えば、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、リードオンリー・メモリ（ＲＯＭ）、これらの組合せ、又は同様のものなど、任意のタイプのシステムメモリを含んでよい。一実施形態において、メモリは、起動に使用するためのＲＯＭと、プログラムのための及びプログラムの実行に使用されるデータストレージのためのＤＲＡＭとを含んでよい。
【００２５】
マスストレージデバイスは、データ、プログラム、及びその他の情報を格納するように、かつそのデータ、プログラム、及びその他の情報にバスを介してアクセスできるように構成された任意のタイプのストレージデバイスを含んでよい。マスストレージデバイスは、例えば、ソリッドステートドライブ、ハードディスクドライブ、磁気ディスクドライブ、光ディスクドライブ、又は同様のもののうちの１つ又は複数を含んでよい。
【００２６】
ビデオアダプタ及びＩ／Ｏインタフェースは、外部の入力及び出力デバイスを処理ユニットに接続するためのインタフェースを提供する。図示されるように、入力及び出力デバイスの例には、ビデオアダプタに接続されたディスプレイと、Ｉ／Ｏインタフェースに接続されたマウス／キーボード／プリンタとが含まれる。その他のデバイスが処理ユニットに接続されてもよく、追加の又はより少ないインタフェースカードが利用されてもよい。例えば、ユニバーサル・シリアル・バス（ＵＳＢ）（図示せず）などのシリアルインタフェースがプリンタのためのインタフェースを提供するために使用されてもよい。
【００２７】
また、処理ユニットは、１つ又は複数のネットワークインタフェースを含み、これは、ノード又は異なるネットワークにアクセスするための有線リンク、例えば、イーサネット（登録商標）ケーブル又は同様のもの、及び／又は無線リンクを含んでよい。ネットワークインタフェースは、処理ユニットにネットワークを介して遠隔ユニットとの通信を行わせる。例えば、ネットワークインタフェースは、１つ又は複数の送信機／送信アンテナと１つ又は複数の受信機／受信アンテナとを介して無線通信を提供し得る。一実施形態において、処理ユニットは、データ処理のためにローカルエリアネットワーク又はワイドエリアネットワークに接続され、遠隔デバイス、例えば、他の処理ユニット、インターネット、リモートストレージ設備、又は同様のものと通信を行う。
【００２８】
以上、詳細な説明がなされたが、添付の特許請求の範囲によって規定されるこの開示の精神及び範囲から逸脱することなく、さまざまな変更形態、置換形態及び代替形態が形成可能であることを理解されたい。さらに、開示の範囲は、明細書中に記載された特定の実施形態への限定を意図したものでなく、当技術分野における通常の知識を有する者であれば、既存の又はこれから開発されるプロセス、機械、製品、組成物、手段、方法、又はステップが、明細書中に記載された対応する実施形態と実質的に同一の機能を実行するか又は実質的に同一の結果を奏し得ることを、この開示から容易に認識できよう。したがって、添付の特許請求の範囲は、そのようなプロセス、機械、製品、組成物、手段、方法、又はステップを、その範囲内に包含することを意図する。
【符号の説明】
【００２９】
１００  マルチドメインネットワーク
１１０，１２０，１３０，１４０  ドメイン
１１２，１２２，１３２，１４２  コアノード
１１４，１２４，１３４，１４４  エッジノード
１１６，１２６，１３６，１４６  ドメインコントローラ
１５０  ルートコントローラ
２００  ネットワーク
２０１  経路
２１１  送信元
２３９  宛先
２５０  送信元ルートホップリスト
４００  ネットワーク
４０１  インタードメイン送信元ルート選択経路
４１０，４２０，４３０  ドメイン
４１１  送信元
４１９，４２１，４２９，４３１  エッジノード
４１５，４２５，４３５  コアノード
４３９  宛先
４５０  送信元ルートホップリスト
４９０  コントローラ
６００  ネットワーク
６０１  インタードメイン経路
６１０，６２０，６３０  ドメイン
６１１，７１１  送信元
６１９，６２１，６２９，６３１  エッジノード
６３９  宛先
６１６，６２６，６３６，７１６，７２６，７３６  ドメインコントローラ
６９０，７９０  ルートコントローラ
７００  通信シーケンス
７１０  インタードメイン経路計算要求
７２０  イントラドメイン経路計算要求
７３０  制御命令
７４０  イントラドメイン経路計算応答
７５０  インタードメイン経路計算応答
７７０  解体命令
７８０  制御命令
１１００  デバイス
１１０４  プロセッサ
１１０６  メモリ
１１１０，１１１２，１１１４  インタフェース
【図１Ａ】
0006571090.tif 000002
【図１Ｂ】
0006571090.tif 000003
【図２】
0006571090.tif 000004
【図３】
0006571090.tif 000005
【図４】
0006571090.tif 000006
【図５Ａ】
0006571090.tif 000007
【図５Ｂ】
0006571090.tif 000008
【図５Ｃ】
0006571090.tif 000009
【図５Ｄ】
0006571090.tif 000010
【図５Ｅ】
0006571090.tif 000011
【図５Ｆ】
0006571090.tif 000012
【図６】
0006571090.tif 000013
【図７】
0006571090.tif 000014
【図８】
0006571090.tif 000015
【図９】
0006571090.tif 000016
【図１０】
0006571090.tif 000017
【図１１】
0006571090.tif 000018
【図１２】
0006571090.tif 000019