(57)【要約】本発明は、パケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報を取得する方法を提供する、これは、パケットのグループに対する前記対象ノードのアップラインにある１つ以上のノードを判定し、パケットのグループに対するすべての入口ノードで、トレースリクエストが受信されるまで、該パケットのグループに対する対象ノードのアップラインにある各ノードにトレースリクエストを転送することによって、提供する。次に、各トレースリクエストそれぞれに応答するトレースリプライが生成され、かつ送信される。次に、少なくとも１つのトレースリプライが、対象ノードで受信される。パケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報は、対象ノードで受信されるトレースリプライから取得される。
2005516535.tif 000002
【特許請求の範囲】
【請求項１】
パケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報を取得する方法であって、
前記パケットのグループに対する前記対象ノードのアップラインにある１つ以上のノードを判定するステップと、
前記パケットのグループに対するすべての入口ノードで、トレースリクエストが受信されるまで、該パケットのグループに対する前記対象ノードのアップラインにある各ノードに前記トレースリクエストを転送するステップと、
前記トレースリクエストのそれぞれに応答するトレースリプライを生成し、送信するステップと、
前記対象ノードで少なくとも１つの前記トレースリプライを受信するステップと、
前記対象ノードで受信される前記トレースリプライからの前記パケットのグループに対する前記対象ノードで終端する、前記１つ以上の経路についての前記情報を取得するステップと
を備えることを特徴とする方法。
【請求項２】
前記１つ以上の経路についての前記情報に基づいて、１つ以上の前記ノードを調整するステップを更に備える
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記１つ以上の経路についての前記情報に基づいて、データベースを生成するステップを更に備える
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記１つ以上の経路についての前記情報に基づいて、データベースを更新するステップを更に備える
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記対象ノードは、出口ノードである
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記対象ノードは、中間ノードである
ことを特徴とする請求項１に記載の方法。
【請求項７】
前記パケットのグループに対する、前記対象ノード、入口ノード及び、該対象ノードと該入口ノード間のノードは、ルータあるいはスイッチである
ことを特徴とする請求項１に記載の方法。
【請求項８】
前記ルータあるいはスイッチは、ラベルスイッチングルータである
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記パケットのグループに対する、前記対象ノード、入口ノード及び、該対象ノードと該入口ノード間のノードは、マルチプロトコルラベルスイッチングドメインである
ことを特徴とする請求項１に記載の方法。
【請求項１０】
前記１つ以上の経路は、１つ以上のラベルスイッチ経路である
ことを特徴とする請求項１に記載の方法。
【請求項１１】
前記パケットのグループは、同位転送クラスである
ことを特徴とする請求項１に記載の方法。
【請求項１２】
前記情報は、前記１つ以上の経路の識別情報を含んでいる
ことを特徴とする請求項１に記載の方法。
【請求項１３】
前記情報は、前記１つ以上の経路内の各ノードで利用可能な１つ以上のリソースを含んでいる
ことを特徴とする請求項１に記載の方法。
【請求項１４】
前記情報は、前記１つ以上の経路内の各ノードの１つ以上の属性を含んでいる
ことを特徴とする請求項１に記載の方法。
【請求項１５】
前記情報をコンピュータモニタに図式的に表示するステップを更に備える
ことを特徴とする請求項１に記載の方法。
【請求項１６】
パケットのグループに対する対象ノードで終端する、１つ以上の経路の情報を取得する方法であって、
（ａ）前記パケットのグループに対する前記対象ノードのアップラインにある１つ以上のノードを判定するステップと、
（ｂ）前記アップラインノードそれぞれにトレースリクエストを送信するステップと、
（ｃ）前記アップラインノードそれぞれにおいて、
前記トレースリクエストが受信される場合には、前記パケットのグループに対する前記アップラインノードのアップラインにある任意のノードが存在するかを判定し、前記パケットのグループに対する前記アップラインノードのアップラインに任意のノードがある場合には、前記アップラインノードそれぞれに前記トレースリクエストを転送し、１つ以上のアップラインノードがなくなるまで、当該（ｃ）ステップを繰り返し、かつ前記パケットのグループに対する前記アップラインノードのアップラインにノードがない場合には、前記トレースリクエストを送信する前記ノードへトレースリプライを送信し、
前記トレースリプライが受信される場合には、前記アップラインノードのすべてで前記トレースリプライが受信されるまで、あるいはタイムアウトが発生するまで待機し、前記受信されたトレースリプライからシングルトレースリプライを生成し、前記トレースリクエストを送信する前記ノードへ前記シングルトレースリプライを送信し、前記アップラインノードが前記対象ノードとなるまで当該（ｃ）ステップを繰り返す
（ｄ）前記トレースリプライが前記対象ノードで受信される場合には、前記対象ノードで受信される前記トレースリプライから、前記パケットのグループに対する前記対象ノードで終端する、前記１つ以上の経路についての前記情報を取得するステップと
を備えることを特徴とする方法。
【請求項１７】
前記（ａ）ステップ〜（ｄ）ステップを繰り返すステップを更に備える
ことを特徴とする請求項１６に記載の方法。
【請求項１８】
前記（ａ）ステップ〜（ｄ）ステップは、定期的に繰り返される
ことを特徴とする請求項１７に記載の方法。
【請求項１９】
前記取得される情報間での違いを判定するステップを更に備える
ことを特徴とする請求項１６に記載の方法。
【請求項２０】
前記１つ以上の経路についての前記情報を取得するステップは、前記トレースリプライが前記アップラインノードのすべてから受信されるまで、あるいはタイムアウトが発生するまでは、実行されない
ことを特徴とする請求項１６に記載の方法。
【請求項２１】
前記１つ以上の経路についての前記情報に基づいて、１つ以上の前記ノードを調整するステップを更に備える
ことを特徴とする請求項１６に記載の方法。
【請求項２２】
前記１つ以上の経路についての前記情報に基づいて、データベースを生成するステップを更に備える
ことを特徴とする請求項１６に記載の方法。
【請求項２３】
前記１つ以上の経路についての前記情報に基づいて、データベースを更新するステップを更に備える
ことを特徴とする請求項１６に記載の方法。
【請求項２４】
前記対象ノードは、出口ノードである
ことを特徴とする請求項１６に記載の方法。
【請求項２５】
前記対象ノードは、中間ノードである
ことを特徴とする請求項１６に記載の方法。
【請求項２６】
前記パケットのグループに対する、前記対象ノード、入口ノード及び、該対象ノードと該入口ノード間のノードは、ルータあるいはスイッチである
ことを特徴とする請求項１６に記載の方法。
【請求項２７】
前記ルータあるいはスイッチは、ラベルスイッチングルータである
ことを特徴とする請求項２６に記載の方法。
【請求項２８】
前記パケットのグループに対する、前記対象ノード、入口ノード及び、該対象ノードと該入口ノード間のノードは、マルチプロトコルラベルスイッチングドメインである
ことを特徴とする請求項１６に記載の方法。
【請求項２９】
前記１つ以上の経路は、１つ以上のラベルスイッチ経路である
ことを特徴とする請求項１６に記載の方法。
【請求項３０】
前記パケットのグループは、同位転送クラスである
ことを特徴とする請求項１６に記載の方法。
【請求項３１】
前記情報は、前記１つ以上の経路の識別情報を含んでいる
ことを特徴とする請求項１６に記載の方法。
【請求項３２】
前記情報は、前記１つ以上の経路内の各ノードで利用可能な１つ以上のリソースを含んでいる
ことを特徴とする請求項１６に記載の方法。
【請求項３３】
前記情報は、前記１つ以上の経路内の各ノードの１つ以上の属性を含んでいる
ことを特徴とする請求項１６に記載の方法。
【請求項３４】
前記情報をコンピュータモニタに図式的に表示するステップを更に備える
ことを特徴とする請求項１６に記載の方法。
【請求項３５】
パケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報を取得するコンピュータ可読媒体上で実現されるコンピュータプログラムであって、
前記パケットのグループに対する前記対象ノードのアップラインにある１つ以上のノードを判定するコードセグメントと、
前記パケットのグループに対するすべての入口ノードで、トレースリクエストが受信されるまで、該パケットのグループに対する前記対象ノードのアップラインにある各ノードに前記トレースリクエストを転送するコードセグメントと、
前記トレースリクエストのそれぞれに応答するトレースリプライを生成し、送信するコードセグメントと、
前記対象ノードで少なくとも１つの前記トレースリプライを受信するコードセグメントと、
前記対象ノードで受信される前記トレースリプライからの前記パケットのグループに対する前記対象ノードで終端する、前記１つ以上の経路についての前記情報を取得するコードセグメントと
を備えることを特徴とするコンピュータプログラム。
【請求項３６】
前記１つ以上の経路についての前記情報に基づいて、１つ以上の前記ノードを調整するコードセグメントを更に備える
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項３７】
前記１つ以上の経路についての前記情報に基づいて、データベースを生成するコードセグメントを更に備える
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項３８】
前記１つ以上の経路についての前記情報に基づいて、データベースを更新するコードセグメントを更に備える
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項３９】
前記対象ノードは、出口ノードである
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項４０】
前記対象ノードは、中間ノードである
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項４１】
前記パケットのグループに対する、前記対象ノード、入口ノード及び、該対象ノードと該入口ノード間のノードは、ルータあるいはスイッチである
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項４２】
前記ルータあるいはスイッチは、ラベルスイッチングルータである
ことを特徴とする請求項４１に記載のコンピュータプログラム。
【請求項４３】
前記パケットのグループに対する、前記対象ノード、入口ノード及び、該対象ノードと該入口ノード間のノードは、マルチプロトコルラベルスイッチングドメインである
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項４４】
前記１つ以上の経路は、１つ以上のラベルスイッチ経路である
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項４５】
前記パケットのグループは、同位転送クラスである
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項４６】
前記情報は、前記１つ以上の経路の識別情報を含んでいる
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項４７】
前記情報は、前記１つ以上の経路内の各ノードで利用可能な１つ以上のリソースを含んでいる
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項４８】
前記情報は、前記１つ以上の経路内の各ノードの１つ以上の属性を含んでいる
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項４９】
前記情報をコンピュータモニタに図式的に表示するコードセグメントを更に備える
ことを特徴とする請求項３５に記載のコンピュータプログラム。
【請求項５０】
パケットのグループに対する対象ノードで終端する、１つ以上の経路の情報を取得するコンピュータプログラムであって、
（ａ）前記パケットのグループに対する前記対象ノードのアップラインにある１つ以上のノードを判定するコードセグメントと、
（ｂ）前記アップラインノードそれぞれにトレースリクエストを送信するコードセグメントと、
（ｃ）前記アップラインノードそれぞれに対するコードセグメントであって、
前記トレースリクエストが受信される場合には、前記パケットのグループに対する前記アップラインノードのアップラインにある任意のノードが存在するかを判定し、前記パケットのグループに対する前記アップラインノードのアップラインに任意のノードがある場合には、前記アップラインノードそれぞれに前記トレースリクエストを転送し、１つ以上のアップラインノードがなくなるまで、当該（ｃ）コードセグメントを繰り返し、かつ前記パケットのグループに対する前記アップラインノードのアップラインにノードがない場合には、前記トレースリクエストを送信する前記ノードへトレースリプライを送信し、
前記トレースリプライが受信される場合には、前記アップラインノードのすべてで前記トレースリプライが受信されるまで、あるいはタイムアウトが発生するまで待機し、前記受信されたトレースリプライからシングルトレースリプライを生成し、前記トレースリクエストを送信する前記ノードへ前記シングルトレースリプライを送信し、前記アップラインノードが前記対象ノードとなるまで当該（ｃ）コードセグメントを繰り返す
（ｄ）前記トレースリプライが前記対象ノードで受信される場合には、前記対象ノードで受信される前記トレースリプライから、前記パケットのグループに対する前記対象ノードで終端する、前記１つ以上の経路についての前記情報を取得するコードセグメントと
を備えることを特徴とするコンピュータプログラム。
【請求項５１】
前記（ａ）コードセグメント〜（ｄ）コードセグメントを繰り返すコードセグメントを更に備える
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項５２】
前記（ａ）コードセグメント〜（ｄ）コードセグメントは、定期的に繰り返される
ことを特徴とする請求項５１に記載のコンピュータプログラム。
【請求項５３】
前記取得される情報間での違いを判定するコードセグメントを更に備える
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項５４】
前記１つ以上の経路についての前記情報を取得するコードセグメントは、前記トレースリプライが前記アップラインノードのすべてから受信されるまで、あるいはタイムアウトが発生するまでは、実行されない
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項５５】
前記１つ以上の経路についての前記情報に基づいて、１つ以上の前記ノードを調整するコードセグメントを更に備える
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項５６】
前記１つ以上の経路についての前記情報に基づいて、データベースを生成するコードセグメントを更に備える
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項５７】
前記１つ以上の経路についての前記情報に基づいて、データベースを更新するコードセグメントを更に備える
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項５８】
前記対象ノードは、出口ノードである
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項５９】
前記対象ノードは、中間ノードである
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項６０】
前記パケットのグループに対する、前記対象ノード、入口ノード及び、該対象ノードと該入口ノード間のノードは、ルータあるいはスイッチである
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項６１】
前記ルータあるいはスイッチは、ラベルスイッチングルータである
ことを特徴とする請求項６０に記載のコンピュータプログラム。
【請求項６２】
前記パケットのグループに対する、前記対象ノード、入口ノード及び、該対象ノードと該入口ノード間のノードは、マルチプロトコルラベルスイッチングドメインである
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項６３】
前記１つ以上の経路は、１つ以上のラベルスイッチ経路である
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項６４】
前記パケットのグループは、同位転送クラスである
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項６５】
前記情報は、前記１つ以上の経路の識別情報を含んでいる
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項６６】
前記情報は、前記１つ以上の経路内の各ノードで利用可能な１つ以上のリソースを含んでいる
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項６７】
前記情報は、前記１つ以上の経路内の各ノードの１つ以上の属性を含んでいる
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【請求項６８】
前記情報をコンピュータモニタに図式的に表示するコードセグメントを更に備える
ことを特徴とする請求項５０に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
＜本発明の背景＞
同一転送クラス（「ＦＥＣ」）は、インターネットプロトコル（「ＩＰ」）パケットのグループの１つとして定義され、これは、同一手順で転送される（例えば、同一経路を介して、同一転送処理で）。従来のＩＰ転送においては、ＩＰパケットがネットワークを通過すると、各地点（hop）では、パケットを再検証し、それをＦＥＣに割り当てる。マルチプロトコルラベルスイッチング（「ＭＰＬＳ」）ネットワークでは、パケットがネットワークに進入する際に、特定パケットの特定ＦＥＣへの割当が一度だけ実行される。パケットが割り当てられるＦＥＣは、「ラベル」として知られる短固定長値に符号化される。パケットが自身の次の地点に転送される場合、ラベルがそれに従って送信される、つまり、送信される前に、パケットは「ラベル化（labeled）」される。次の地点では、パケットのネットワークレイヤヘッダの更なる解析は発生しない。むしろ、ラベルは、テーブルへのインデックスとして使用され、これは、次の地点と新規のラベルを特定する。古いラベルは、新規のラベルに置き換えられ、パケットは次の地点に転送される。ＭＰＬＳ転送パラダイムでは、パケットが一旦ＦＥＣに割り当てられると、次のルータは、更なる任意のヘッダ解析は実行しない、代りに、ラベルがすべてのパケット転送を実現する。
【０００２】
ＭＰＬＳ転送パラダイムによって形成されるラベルスイッチング経路（「ＬＳＰ」）の単一方向性のために、対象ノードでのＬＰＳ群の終端を検出するメカニズムは存在しない、この対象ノードは、通常、ラベルスイッチングルータ（「ＬＳＲ」）、あるいはこのようなＬＳＰ群についての任意の情報である。それゆえ、パケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報を取得する方法及び装置が必要とされている。
＜発明の要約＞
本発明は、パケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報を取得する方法及び装置を提供する。それゆえ、本発明は、ＭＰＬＳネットワーク及び、ＭＰＬＳドメインを介するＬＳＰ群の監視及び管理を可能にする。例えば、本発明は、ＬＳＰ群の様々な属性のセット（ＬＳＰ経路、ＬＳＰ経路上の様々なノードで利用可能なリソース、ＬＳＲのマージ情報からなるＬＳＰセット）を収集するために使用することができる。この情報は、ＦＥＣに対し、出口（egress）ＬＳＲ（ルート）のような対象ノード上で終端する、ＬＳＰ群のセットを監視／微調整するためのネットワーク管理を支援することができる。また、この情報は、ＭＰＬＳドメインにおいて、様々な属性のトラフィック設計（traffic engineered）（「ＴＥ」）経路を様々な時間に取得するデータベースを構築するために使用することができる。離散した間隔で取得される、出口ＬＳＲでのＦＥＣに対するバックトレース（back-traced）ＬＳＰツリーの２つの断片（snapshot）は、ＴＥ経路の変更（再転送ＬＳＰ群）、ＬＳＰ群の帯域幅のアップグレード／ダウングレード、ＬＳＰツリーへの新規のＴＥ経路の追加、ＬＳＰツリーからの既存ＴＥ経路の削除のような情報を明らかにすることができる。対象ノードは、かなり頻繁に出口ＬＳＲとなることになるが、本発明は、ＦＥＣに対する中間ＬＳＲとして動作する任意のノードから実行することができる。
【０００３】
より詳しくは、本発明はパケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報を取得する方法を提供する、これは、パケットのグループに対する前記対象ノードのアップラインにある１つ以上のノードを判定し、パケットのグループに対するすべての入口ノードで、トレースリクエストが受信されるまで、該パケットのグループに対する対象ノードのアップラインにある各ノードにトレースリクエストを転送することによって、提供する。次に、各トレースリクエストそれぞれに応答するトレースリプライが生成され、かつ送信される。次に、少なくとも１つのトレースリプライが、対象ノードで受信される。パケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報は、対象ノードで受信されるトレースリプライから取得される。この方法は、上述の機能がコードセグメントによって実現される、コンピュータ可読媒体上で実行されるコンピュータプログラムとして実現することができる。
【０００４】
また、本発明は、パケットのグループに対する対象ノードで終端する、１つ以上の経路の情報を取得する方法を提供する、これは、（ａ）パケットのグループに対する対象ノードのアップラインにある１つ以上のノードを判定し、（ｂ）アップラインノードそれぞれにトレースリクエストを送信し、（ｃ）各アップラインノードに対して以下に説明する処理を実行し、（ｄ）トレースリプライが対象ノードで受信される場合には、対象ノードで受信されるトレースリプライから、パケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報を取得することによって、提供する。アップラインノードでトレースリクエストが受信される場合には、本発明は、パケットのグループに対するアップラインノードのアップラインにある任意のノードが存在するかを判定する。パケットのグループに対するアップラインノードのアップラインに任意のノードがある場合には、アップラインノードそれぞれにトレースリクエストが転送され、１つ以上のアップラインノードがなくなるまで、（ｃ）ステップを繰り返する。一方、パケットのグループに対するアップラインノードのアップラインにノードがない場合には、トレースリクエストを送信するノードへトレースリプライを送信する。アップラインノードでトレースリプライが受信される場合には、本発明は、アップラインノードのすべてでトレースリプライが受信されるまで、あるいはタイムアウトが発生するまで待機し、受信されたトレースリプライからシングルトレースリプライを生成し、トレースリクエストを送信するノードへシングルトレースリプライを送信し、アップラインノードが対象ノードとなるまで（ｃ）ステップを繰り返す。この方法は、上述の機能がコードセグメントによって実現される、コンピュータ可読媒体上で実行されるコンピュータプログラムとして実現することができる。
【０００５】
本発明の他の特徴及び効果は、図面を参照して説明される以下の詳細な説明を参照することで、当業者には明らかとなるであろう。
【０００６】
＜本発明の詳細説明＞
以下では、本発明の様々な実施形態を構成し、使用することを説明するが、本発明が多くの適用可能な発明の概念を提供し、これが、広範囲で様々な特定の環境で実施できることが理解されるべきである。例えば、電気通信システムに加えて、本発明は、他の形態の通信あるいは汎用データ処理に適用することが可能である。他の形態の通信には、ネットワーク間の通信、衛星を介する通信、あるいは本発明の時点では当業者に知られていない任意の形態の通信が含まれる。本明細書で説明する特定の実施形態は、本発明を構成し、かつ使用するための特定の方法を単に示しているだけであり、本発明の範囲を制限するものではない。
【０００７】
本発明は、パケットのグループに対する対象ノードで終端する、１つ以上の経路についての情報を取得する方法及び装置を提供する。それゆえ、本発明は、マルチプロトコルラベルスイッチング（「ＭＰＬＳ」）ネットワーク、及びＭＰＬＳドメインを介するラベルスイッチング経路（「ＬＳＰ」）の監視及び管理を可能にする。例えば、本発明は、様々な属性のＬＳＰ群を１つのセット（ＬＳＰ経路、ＬＳＰ経路上の様々なノードで利用可能なリソース、ラベルスイッチングルータ（「ＬＳＲ」）のマージ情報からなるＬＳＰセット）に集約するために使用することができる。この情報は、同一転送クラス（「ＦＥＣ」）に対し、出口（egress）ＬＳＲ（ルート）のような対象ノード上で終端する、ＬＳＰ群のセットを監視／微調整するためのネットワーク管理を支援することができる。また、この情報は、ＭＰＬＳドメインにおいて、様々な属性のトラフィック設計（traffic engineered）（「ＴＥ」）経路を様々な時間に取得するデータベースを構築するために使用することができる。離散した間隔で取得される出口ＬＳＲでのＦＥＣに対するバックトレース（back-traced）ＬＳＰツリーの２つの断片（snapshot）は、ＴＥ経路の変更（再転送ＬＳＰ群）、ＬＳＰ群の帯域幅のアップグレード／ダウングレード、ＬＳＰツリーへの新規のＴＥ経路の追加、ＬＳＰツリーからの既存ＴＥ経路の削除のような情報を明らかにすることができる。対象ノードは、かなり頻繁に出口ＬＳＲとなることになるが、本発明は、ＦＥＣに対する中間ＬＳＲとして動作する任意のノードから実行することができる。
【０００８】
図１を参照すると、本発明の実施形態に従うネットワーク１００のブロック図が示される。このネットワークは、通信リンク１０６、１０８、１１０及び１１２を介して、１０２及び１０４のような１つ以上の他のネットワークと通信可能に接続されている。ネットワーク１００はＭＰＬＳドメインであり、これは、ラベル配信プロトコル（「ＬＤＰ」）を使用し、かつサービスプロバイダのパケットネットワークのすべてあるいは一部となり得る。ネットワーク１０２及び１０４は、ＭＰＬＳ−ＬＤＰネットワークあるいはいくつかの他のタイプのネットワークであり得る。当業者によって認識されるように、通信リンク１０６、１０８、１１０及び１２２の構成は、ネットワーク１００、１０２及び１０４間で使用されるインタフェースのタイプに依存して変化する。
【０００９】
ネットワーク１００は、例えば、１１４、１１６、１１８及び１２０のいくつかのノードを含み、これは、例えば、１２０、１２２及び１２４の通信リンクと相互に通信可能に接続されることで、ネットワーク１００を形成している。ノード１１４、１１６、１１８及び１２０は、典型的には、ルータであり、より詳しくは、ラベルスイッチングルータ（「ＬＳＲ」）である、但し、ルーティングあるいはスイッチング機能を実行する任意の装置でもあり得る。ネットワーク１００は、ＭＰＬＳ−ＬＤＰ規格に従って動作する。そのため、ＩＰパケットがネットワーク１００を通過する場合、各地点、例えば、１２０、１２２及び１２４は、パケットを再検証し、それをＦＥＣに割り当てる。ＦＥＣは、パケットのグループであり、これは、同一手順で転送される（例えば、同一経路を介して、同一転送処理で）。パケットがネットワーク１００に進入する際に、特定パケットの特定ＦＥＣへの割当が一度だけ実行される。パケットが割り当てられるＦＥＣは、「ラベル」として知られる短固定長値に符号化される。パケットが自身の次の地点に転送される場合、ラベルがそれに従って送信される、つまり、送信される前に、パケットは「ラベル化（labeled）」される。次の地点では、パケットのネットワークレイヤヘッダの更なる解析は発生しない。むしろ、ラベルは、テーブルへのインデックスとして使用され、これは、次の地点と新規のラベルを特定する。古いラベルは、新規のラベルに置き換えられ、パケットは次の地点に転送される。パケットが一旦ＦＥＣに割り当てられると、次のルータは、更なる任意のヘッダ解析は実行しない、代りに、ラベルがすべてのパケット転送を実現する。
【００１０】
ネットワーク１００で、ＦＥＣに対するＬＰＳ群が確立されたいくつかのＭＰＬＳ−ＬＤＰは、そのＦＥＣに対する同一の出口ノードあるいはＬＳＲで終端となり得る。これは、ＭＰＬＳドメイン内で、ＦＥＣに対するＬＳＰツリーのルートとなる出口ノードを有する、ＬＳＰツリーを構築する。ＦＥＣに対する、出口ノードあるいはルートは、ＬＳＰツリーの出口として動作する、これは、そこに集約するＬＳＰ群を監視するための最適な位置となる。ＦＥＣに対する出口ノードが与えられると、本発明は、ＭＰＬＳ−ＬＤＰによって確立されたＬＳＰ群の単一方向性を使用して、出口ノード上で終端となる、そのＦＥＣ対するＭＰＬＳ−ＬＤＰのＬＳＰすべてをバックトレース（逆追跡）する。
【００１１】
ここで、図２を参照すると、本発明の実施形態に従うネットワーク内の様々なタイプのノードのバックトレースメカニズムを示すブロック図が示される。ＦＥＣに対して与えられる任意のＬＳＰは、たいていは出口ノードとなる対象ノード２００として識別され、また、１つ以上の中間ノード２０２及び入口（ingress）ノード２０４として識別されることもある。動作としては、本発明は、対象ノード２００のアップラインノードを判定し、トレースリクエスト２００を各アップラインノード、例えば、中間ノード２０２へ送信する。各中間ノード２０２は、トレースリクエスト２０６をダウンラインノードから受信し、このダウンラインノードは、対象ノード２００あるいはダウンストリーム中間ノードであり得る。次に、中間ノード２０２は、中間ノード２０２のアップラインノードを判定し、トレースリクエスト２０８を各アップラインノードへ送信する、このアップラインノードは、入口ノード２０４あるいはアップライン中間ノードであり得る。トレースリクエストが、パケットのグループに対するすべての入口ノード２０４で受信されるまで、トレースリクエスト２０６、２０８は、そのパケットのグループに対する対象ノード２００のアップラインにある各ノードに、上記の処理を使用して転送される。
【００１２】
各入口ノード２０４で、トレースリクエスト２０８が処理されて、トレースリプライあるいは応答２１０を生成し、これは、中間ノード２０２のようなダウンラインノードに送信される。トレースリプライ２１０は、１つ以上の経路あるいはＬＳＰ群のセット（ＬＳＰ経路、ＬＳＰ経路上の様々なノードで利用可能なリソース、ＬＳＲのマージ情報からなるＬＳＰセット）、あるいはノード自身についての様々な情報あるいは属性を含んでいる。この情報は、ＦＥＣに対し、出口ノードあるいはＬＳＲ（ルート）のような対象ノード上で終端する、ＬＳＰ群のセットを監視／微調整するためのネットワーク管理を支援することができる。また、この情報は、ＭＰＬＳドメインにおいて、様々な属性のＴＥ経路を様々な時間に取得するデータベースを構築するために使用することができる。離散した間隔で取得される出口ＬＳＲでのＦＥＣに対するバックトレースＬＳＰツリーの２つの断片（snapshot）は、ＴＥ経路の変更（再転送ＬＳＰ群）、ＬＳＰ群の帯域幅のアップグレード／ダウングレード、ＬＳＰツリーへの新規のＴＥ経路の追加、ＬＳＰツリーからの既存ＴＥ経路の削除のような情報を明らかにすることができる。対象ノードは、かなり頻繁に出口ＬＳＲとなることになるが、本発明は、ＦＥＣに対する中間ＬＳＲとして動作する任意のノードから実行することができる。
【００１３】
ダウンライン中間ノード２０２は、すべてのアップラインノードからトレースリプライ２１０を受信して、そのトレースリプライ２１０に含まれる情報のすべてからシングルトレースリプライ２１２を生成する。次に、トレースリプライ２１２は、ダウンラインノードに送信され、このダウンラインノードは、対象ノード２００あるいはダウンライン中間ノードであり得る。対象ノード２００のすべてのアップラインノードが対象ノード２００へトレースリプライ２１２を送信するまで、すべての中間ノード２０２でこの処理が繰り返される。すべてのトレースリプライ２１２が一旦対象ノード２００で受信されると、トレースリプライ２１２及びそれに含まれる情報は、上述の１つ以上の目的のために処理される。例えば、この情報は、１つ以上のノードを調整する、あるいはデータベースを生成する、あるいはデータベースを更新するために使用することができる。加えて、この情報は、コンピュータモニタに図式的に表示することができる。
【００１４】
本発明は、（ａ）パケットのグループに対する対象ノード２００のアップラインにある１つ以上のノードを判定し、（ｂ）各アップラインノード２０２にトレースリクエスト２０６を送信し、（ｃ）各アップラインノード２０２で以下に説明する処理を実行し、（ｄ）トレースリプライ２１２が対象ノード２００で受信されるときには、その対象ノード２００で受信されるトレースリプライ２１２からのパケットのグループに対する対象ノード２００で終端する１つ以上の経路についての情報を取得することによって実現することができる。トレースリクエスト２０６がアップラインノード２０２で受信されると、本発明は、パケットのグループに対するアップラインノード２０２のアップラインに任意のノードが存在するかを判定する。パケットのグループに対するアップラインノード２０２のアップラインに任意のノードが存在する場合、アップラインノード２０２あるいは２０４が存在しなくなるまで、トレースリクエスト２０８を、各アップラインノード２０２あるいは２０４に転送され、ステップ（ｃ）が繰り返される。一方、パケットのグループに対するアップラインノード２０２のアップラインに任意のノードが存在しない場合、トレースリプライ２１０が、トレースリクエスト２０８を送信したノード２０２へ送信される。トレースリプライ２１０がアップラインノード２０２で受信されると、トレースリプライ２１０がすべてのアップラインノード２０２及び２０４から受信されるまで、あるいはタイムアウトが発生するまで、本発明は待機し、受信したすべてのトレースリプライ２１０からシングルトレースリプライ２１２を生成し、そのシングルトレースリプライ２１２をトレースリクエスト２０６を送信したノード２００へ送信し、アップラインノードが対象ノード２００になるまで、ステップ（ｃ）を繰り返す。タイムアウトは、シングルトレースリプライ２１２が生成される前に、トレースリプライ２１０を収集するための固定の期間である。タイムアウト期間は、構成依存であり、局所的に構成されるべきである。その後、シングルトレースリプライ２１２が、固定期間の待機時間内で受信したトレースリプライから生成され、かつノード２００へ送信される。
【００１５】
上述の２つの方法は、コンピュータ可読媒体上で実現されるコンピュータプログラムとして実現することができ、ここでは、上述の機能がコードセグメントによって実現される。加えて、これらの処理あるいは方法は、ネットワーク及びＬＳＰ群を監視し、管理するために、（１回、数回、定期的あるいは不定期に）繰り返すことができる。その結果、本発明によって取得される情報は、ＭＰＬＳドメイン内の様々な属性のＴＥ経路を取得するデータベースを構築し、かつ更新するために使用することができる。
【００１６】
図３Ａ、３Ｂ、３Ｃ及び３Ｄは、本発明の実施形態に従うバックトレースメカニズムの例を示すブロック図である。この例では、ネットワークあるいはＭＰＬＳドメイン３００（図１のネットワーク１００を参照）は、６つのノード３０２、３０４、３０６、３０８、３１０及び３１２を有し、かつ６つのリンクａ、ｂ、ｃ、ｄ、ｅ及びｆを含んでいる。細線の円で示されるノード３０２、３０４、３０６及び３０８は、ＭＰＬＳドメイン３００のエッジＬＳＲ群である。また、この例において、ノード３０８は、ＦＥＣ「Ｆ」に対する出口ノードであり、それに続くＬＳＰ群は、ＭＰＬＳドメイン３００内のＦＥＣ「Ｆ」に対して使用される：
ノード３０２から３０８へのＦＥＣ「Ｆ」に対するＬＳＰ→｛302、a、310、e、308｝
ノード３０４から３０８へのＦＥＣ「Ｆ」に対するＬＳＰ→｛304、f、310、e、308｝
ノード３０６から３０８へのＦＥＣ「Ｆ」に対するＬＳＰ→｛306、c、312、d、308｝
本発明に従う、ノード３０８からのＬＳＰバックトレースの起動は、図３Ｂに示されるＬＳＰツリーとなるできである。図３Ｃは、上述の場合に対するＬＳＰバックトレースリクエストリプライメッセージのフローを示しており、ここでは、バックトレースリクエストメッセージは実線で示され、バックトレースリプライメッセージは破線で示される。リンク３１４、３１６、３１８、３２０、３２２及び３２４を示す線は、説明を簡単にするために削除している。
【００１７】
出口ノード３０８は、トレースリクエストメッセージ３１４をノード３１２に送信し、また、トレースリクエストメッセージ３１２をノード３１０に送信する。逆に、ノード３１０は、トレースリクエストメッセージ３１８をノード３０２に転送し、また、トレースリクエストメッセージ３２０をノード３０４に転送する。ノード３１２では、トレースリクエストメッセージ３２２がノード３０６に転送される。ノード３０２、３０４及び３０６が、ＦＥＣ「Ｆ」に対する入口ノードであるとすると、それらは、バックトレースリプライメッセージ３２４、３２６及び３２８でそれぞれ応答する。各ノードからのバックトレースリプライメッセージは、それから派生するサブツリーを含んでおり、これは、ＦＥＣ「Ｆ」に対するノードでマージするＬＳＰ群のセットを示している。ノード３１０は、ノード３０２からバックトレースリプライ３２４を収集し、また、ノード３０４からバックトレースリプライ３２６を収集し、それらを自身の情報に付加し、それ自身がルートとなる新規のサブツリーを構築し、新規のバックトレースリプライ３３０をノード３０８へ送信する。ノード３１２は、ノード３０６からバックトレースリプライ３２８を受信し、それを自身の情報に付加し、それ自身がルートとなる新規のサブツリーを構築し、新規のバックトレースリプライ３３２をノード３０８へ送信する。ノード３０８は、ノード３１０からのバックトレースリプライ３３０とノード３１２からのバックトレースリプライ３３２内のサブツリーを収集し、それ自身がルートとなるＦＥＣ「Ｆ」に対する完全なＬＳＰツリーを構築する。
【００１８】
後半の時点で、ノード３０２からノード３０８へのＬＳＰが新規の経路｛３０２、ｂ、３１２、ｄ、３０８｝にリルートされるものとする。ＬＳＰバックトレースが再度起動される場合、得られるツリーは、図３Ｄに示されるようになるべきである。加えて、本発明は、経路が変化していないＬＳＰ｛３０４、ｆ、３１０、ｅ、３０８｝及び｛３０６、ｃ、３１２、ｄ、３０８｝内での任意の帯域幅の変更を検出することができる。
【００１９】
上述のメカニズムは、ＭＰＬＳドメイン内のＦＥＣに対する出口として動作するＬＳＲがルートとなるＬＳＰツリーを構築する。各ノードのＬＳＰバックトレースメッセージに追加情報を付加することも可能である。追加情報は、例えば、特定リンクを介するＬＳＰに対して割り当てられる帯域幅、リンク上の未予約帯域幅量、ＬＳＰに従って使用されるラベル、ノードのマージ機能（仮想経路「ＶＰ」）、仮想回線（「ＶＣ」）、ＡＴＭを介するＭＰＬＳの場合のＶＰ及びＶＣのマージ）、ラベルリソースの可用性及びＭＰＬＳネットワーク管理に対して有益である他のタイプの情報のような詳細を含むことができる。時には、ＬＳＰの入口をＭＰＬＳドメイン外にすることも可能である。このような状況では、バックトレースメッセージは、エッジ装置のローカル構成に依存して応答する。エッジ装置が、アップストリームＭＰＬＳドメインにバックトレースメッセージを転送するように構成されていない場合、ＬＳＰが実際の入口ではないことを示す追加情報を持つバックトレースリプライで応答することができる。バックトレースリクエストをダウンストリームＭＰＬＳドメインから受信する場合のエッジ装置の動作は、自身のローカル構成に依存する。ＬＳＰバックトレースは、ＭＰＬＳドメイン内のノードからできる限りの多くの情報を取得することができるようにするべきである。バックトレースメカニズムは、いくつかのＭＰＬＳドメインにまたがるＬＳＰツリーを構築するために使用することもできる。トンネル化ＬＳＰ群に対しては、ＬＰＳバックトレースメッセージは、それが同一のＬＳＰレベルの入口ノードに到達するまで、即ち、バックトレースメッセージが、それが発行されている以外の異なるレベルのＬＳＰにならない間は、生成したレベルと同一のＬＳＰレベルで転送されるべきである。バックトレースリプライメッセージは、バックトレースメッセージが受信されたレベル以外の異なるレベルのＬＳＰにはならない。バックトレース応答は、実際の逆経路、かつバックトレースリクエストメッセージによって転送されるＬＳＰレベルと同一のレベルに従わなければならない。
【００２０】
ＭＰＬＳアーキテクチャと一致する本発明で可能な一構成を説明する。ＭＰＬＳアーキテクチャの詳細は、インターネットソサエティ（http://www.ietf.org）で発行されている、マルチプロトコルラベルスイッチングアーキテクチャ、ＲＦＣ  ３０３１に記載されている。ＬＤＰは、ネットワークレイヤールーティング情報を直接データリンクレイヤー交換経路にマッピングすることによってネットワークを介してＬＳＲがＬＳＰを確立する処理及びメッセージのセットを含んでいる。ＬＤＰは、それを生成するＬＳＰと、ＦＥＣを関連付けている。ＬＳＰに関連付けられているＦＥＣは、どのパケットがＬＳＰにマッピングされるかを特定する。ＬＤＰは、インターネットソサエティによって発行されている、ＬＤＰ仕様  ＲＦＣ  ３０３６に記載されている。加えて、制限型（constraint based）ルーティング（「ＣＲ−ＬＤＰ」）を、ルーティングプロトコルに対してどのようなものが利用できるかに関係なく、経路をセットアップするために使用される情報を拡張するために使用することができる。ＣＲ−ＬＤＰは、インターネットソサエティによって発行されている、draft-ieft-mpls-cr-ldp-0.6txtである、ＬＤＰを使用する制限型ＬＳＰセットアップに記載されている。
【００２１】
本発明は、２つの新規なＬＤＰメッセージ：バックトレースメッセージ（トレースリクエストメッセージとも呼ぶ）と、バックトレースリプライメッセージを提供する。以下の新規なタイプレングス値（「ＴＬＶ」）である：ツリーＴＬＶ、入口フラグＴＬＶ、予約帯域幅ＴＬＶ及び集約ＴＬＶは、上述の新規なメッセージに対する符号化に適応するように追加される。これらのＴＬＶ群に対するタイプ値は、ＬＤＰ  ＴＬＶ空間で予約されている。
【００２２】
ここで、図４を参照すると、従来技術に従う標準ＬＤＰメッセージ４００に対する符号化が示されている。ＬＤＰメッセージ４００は、以下のフィールド：Ｕビット４０２、メッセージタイプ４０４、メッセージレングス４０６、メッセージＩＤ４０８、必須パラメータ４０１及びオプションパラメータ４１２を含んでいる。Ｕビット４０２は、未知のメッセージビットである。未知のメッセージの受信において、Ｕビット４０２がない（０である場合）、通知がメッセージ発信元に返信される、Ｕビット４０２が設定されている場合（１である場合）、未知のメッセージは無視される。メッセージタイプ４０４は、メッセージのタイプを識別する。メッセージレングス４０６は、メッセージＩＤ４０８、必須パラメータ４１０及びオプションパラメータ４１２の累積レングスをオクテット（octets）で示す。メッセージＩＤ４０８は、メッセージを識別するために使用される３２ビット値である。メッセージＩＤ４０８は、そのメッセージに適用することができる通知メッセージの識別を容易にするために送信するＬＳＲによって使用される。通知メッセージの応答において、その通知メッセージを送信するＬＳＲは、その通知メッセージによって搬送されるステータスＴＬＶ内に、このメッセージのメッセージＩＤを含めるべきである。必須パラメータ４１０は、可変長の必要とされるメッセージパラメータのセットである。いくつかのメッセージは、パラメータを必要としない。パラメータを要求するメッセージに対しては、要求されたパラメータは、後続するセクション内で個々のメッセージ仕様によって特定される順序で出現しなければならない。オプションパラメータ４１２は、可変長のオプションメッセージパラメータのセットである。多くのメッセージは、オプションパラメータを持っていない。オプションパラメータを持つメッセージに対しては、オプションパラメータは、任意の順序で出現することができる。
【００２３】
本発明に戻ると、バックトレースメッセージの受信においては、ＬＳＲは、バックトレースメッセージの処理時、かつ問い合わされた情報の返信時に、自身の構成制約に従って動作する。いくつかの行動計画が、ＬＳＲに対して可能である。１つ目には、ＬＳＲは、バックトレースメカニズムに対するメッセージを処理するためのコードをサポートしない。２つ目には、ＬＳＲは、バックトレースメカニズムに対するメッセージを処理するためのコードをサポートするが、任意のデータを返信しないように構成される。３つ目は、ＬＳＲは、バックトレースメカニズムに対するメッセージを処理するためのコードをサポートするが、問い合わされたデータの一部を返信しないように構成される。最後に、ＬＳＲは、バックトレースメカニズムに対するメッセージを処理するためのコードをサポートし、かつ問い合わされているデータすべてを返信するように構成される。本発明は、これらの場合のそれぞれを処理する柔軟性を提供する。
【００２４】
ＬＳＲがバックトレースメッセージをサポートしない場合では、ＬＳＲは、未知のメッセージタイプを受信するものとして動作する。それゆえ、Ｕビットを与えることになる。ＬＳＲが任意の情報を共有できない場合、ＬＳＲはバックトレースメッセージを復号し、かつ処理することができる。しかしながら、すべてのデータは秘匿するように構成され、メッセージを同位（peers）のアップストリームＬＳＰへ転送する。バックトレースリプライメッセージがアップストリームから受信される場合、ＬＳＲは、問い合わされたデータに対するゼロレングスのＴＣＶ群を符号化した後、ダウンストリームへリプライメッセージを転送することが要求される。出口ノードがリプライを再受信する場合、ＴＬＶ群が空であることを識別することができる、それゆえ、ゼロレングスのＴＬＶ群を無視し、かつ残りのデータを処理することができる。尚、ゼロレングスのＴＬＶの符号化は、ツリーＴＬＶ内のマージフラグ情報、実際の入口情報及びＬＳＰルートノード情報以外は、問い合わされたすべてのタイプの情報に対して使用することができる。ツリーＴＬＶ及び実際の入口情報は、以下で詳細に説明する。マージフラグ情報は、インターネットソサエティで発行されている、draft-ietf-mpls-lsp-query-03.txtである、ＭＰＬＳ  ＬＤＰ  クエリーメッセージ説明書に記載されている。
【００２５】
ＬＳＲがいくつかの問い合わされた情報を共有できない場合、ＬＳＲは、バックトレースメッセージを復号し、処理し、転送する。バックトレースリプライメッセージでは、ＬＳＲは、返信しようとするデータタイプに対する値と、秘匿されているデータに対する値に対するゼロレングスのＴＬＶ群を符号化する。尚、ゼロレングスのＴＬＶの符号化は、ツリーＴＬＶ内のマージ情報、実際の入口情報及びＬＳＰルートノード情報以外の、問い合わされたすべてのタイプの情報に対して使用することができる。ＬＳＲが自身のシブリング（sibling）情報を秘匿するように構成される場合、シブリングカウントをＴＬＶ内の２５５として符号化する。ＬＳＲが問い合わされたバックトレース情報を共有できる場合、通常のＬＳＲに対するものである場合、ＬＳＲの動作は、以下で説明されるバックトレース及びバックトレースリプライ処理に続くことになる。ＬＳＲがバックトレース情報を共有できることの決定は、局所的な構成を介して制御される。
【００２６】
上述したように、バックトレースメッセージは、ＦＥＣに対するＬＳＰツリーについての情報を収集する。これは、確立されたＬＳＰに対して任意の時間に送信することができる。より詳しくは、バックトレースメッセージは、ＦＥＣのＬＳＰツリーを形成するＬＳＲ、ＬＳＰツリーに従って使用されるラベル、ＬＳＲがＬＳＰツリー内の地点をマージすることについての情報、ＬＳＰツリーを形成するＬＳＰ群に従う未予約帯域幅、ＬＳＰツリーを形成するＬＳＰ群に対する割当帯域幅、ＬＳＰツリー内のＬＳＲ群で発生するＦＥＣ集約についての情報、ＴＬＶで計算され、かつ符号化される、ＭＰＬＳネットワーク管理に対して将来必要とされるものについての情報を収集するために使用することができる。バックトレース情報は、バックトレースリプライメッセージで符号化され、これは、バックトレースメッセージの応答として、ダウンストリームへ返信される。
【００２７】
図５を参照すると、本発明の実施形態に従うバックトレースメッセージ５００に対する符号化が示されている。バックトレースメッセージ５００は、以下のフィールド：ゼロであるＵビット５０２、バックトレースメッセージタイプ５０４、メッセージレングス５０６、メッセージＩＤ５０８、ＦＥＣ  ＴＬＶ５１０、クエリーＴＬＶ５１２、地点カウントＴＬＶ５１４及びオプションパラメータ５１６を含んでいる。メッセージレングス５０６は、メッセージＩＤ５０８、ＦＥＣ  ＴＬＶ５１０、クエリーＴＬＶ５１２、地点カウントＴＬＶ５１４及びオプションパラメータ５１６の累積レングスをオクテット（octets）で示している。メッセージＩＤ５０８は、メッセージを識別するために使用される３２ビット値である。ＦＥＣ  ＴＬＶ５１０は、バックトレースされるＦＥＣに対応する唯一のＦＥＣ要素を含んでいる。クエリーＴＬＶ５１２は、ＬＳＰツリー内のＬＳＰについての追加情報を問い合わせるために使用される。いくつかのクエリーＴＬＶ５１２の符号化は、インターネットソサエティによって発行されている、draft-ietf-mpls-lsp-query-03.txtであるＭＰＬＳ  ＬＤＰクエリーメッセージ説明書に記載されている。地点カウントＴＬＶ５１４は、メッセージが損失する前に通過することができるＬＳＲ地点数を示している。このフィールドは、典型的には、最大値２５５（あるいは、任意の場合は、固定値）で初期化される。バックトレースメッセージを受信する各ＬＳＲは、地点カウントＴＬＶ５１４の値から１減算する。地点カウントＴＬＶ５１４がゼロの値になると、バックトレースメッセージは損失していることになる。オプションパラメータ５１６は、将来定義される可能性のある任意のオプションパラメータに対して予約されている。
【００２８】
動作としては、たいていは出口ＬＳＲである対象ノードは、バックトレースメッセージ５００を初期化し、どのような種類の情報が、ＦＥＣに対するＬＳＰツリー内のすべてのノードからの収集対象であるかに従って、クエリーＴＶＬパラメータ５１２を設定する（populate）。但し、バックトレースメッセージ５００が、バックトレースされるＦＥＣに対するすべての入口ＬＳＲに到達しない状況が存在する。このような状況では、ＬＳＲについての少なくともいくつかの情報を収集することが、対象ノードに対しては有用であり、これは、ＬＳＲの１つが失敗するまでの経路に従う。ＬＳＰに対するバックトレースは、自身のＦＥＣによって実行される。バックトレースメッセージ５００の受信において、ＬＳＲは、ＦＥＣを復号し、発信ラベルを検出してバックトレースされるＬＳＰを識別する。ＬＳＲがＬＳＰを検出できない場合、「バックトレースするＬＳＰがない」ステータスを有する通知メッセージを返信する。一方、ＬＳＲが受信ラベルのセットを検出すると、これらは、既に検出されている発信ラベルにマージされる。次に、ＬＳＲは、受信ラベルセット内の各受信ラベルに対応する同位のアップストリームＬＳＲセット「Ｓ」を計算する。次に、アップストリームＬＳＲのみ含むサブセット「Ｓ」である別のセット「Ｐ」を計算し、これは、ＦＥＣに対するものであるラベルが公表され、これは、バックトレースメッセージ５００で受信されるＦＥＣに組み込む、あるいはバックトレースメッセージ５００内のＦＥＣによって組み込まれる。受信ラベルに対して同位のアップストリームを検出するメカニズムは、インターネットソサエティによって発行されている、draft-ietf-ldp-state-04.txtで参照することができる。
【００２９】
同位のアップストリームＬＳＲセットの計算後、ＬＳＲは、バックトレースメッセージ５００を、上述で計算されたセット「Ｐ」のメンバーすべてに転送する。時には、計算されたセット「Ｐ」の同一メンバーに、１つ以上のバックトレースメッセージ５００を送信する必要があるかもしれない。この状況は、ＬＳＲがいくつかのＦＥＣ−ラベルバインディングを同位のアップストリームに公表する場合に発生し、ここでは、公表されたＦＥＣのそれぞれがバックトレースリクエストで受信されるＦＥＣによって組み込むあるいは組み込まれる。バックトレースメッセージ５００が、ＬＳＰトンネルに進入する場合、それは、同一のＬＳＰレベルと同位のアップストリームＬＳＰに転送される、即ち、バックトレースメッセージ５００は、受信されＬＳＰレベルと異なるレベルと同位のＬＳＰには転送されるべきでない。
【００３０】
バックトレースメッセージ５００の受信において、入口ノードは、バックトレースリプライメッセージ６００（図６）で応答する。バックトレースリプライメッセージ６００は、クエリーＴＬＶ５１２を含んでおり、これは、バックトレースメッセージ５００で受信される。クエリーＴＬＶ５１２は、経路上のＬＳＲにどの情報が問い合わされているかを通知し、かつ中間ＬＳＲに、バックトレースリプライメッセージ６００上で問い合わされた自身の情報をピギーバックすることを可能にする。バックトレースリプライメッセージ６００は、ダウンストリームに転送され、かつバックトレースメッセージ５００の応答時に送信される。バックトレースリプライメッセージ６００が一杯である場合、ＴＣＰは、メッセージを細分化して、かつ再構成することによってそのメッセージを扱うことになる。
【００３１】
図６を参照すると、本発明の実施形態に従うバックトレースリプライメッセージ６００に対する符号化が示される。バックトレースリプライメッセージ６００は、ＬＳＰツリー上の任意のＬＳＲによって生成され、経路上の各ＬＳＲによってダウンストリームへ送信される。バックトレースリプライメッセージ６００は、以下のフィールド：ゼロであるＵビット６０２、バックトレースリプライメッセージタイプ６０４、メッセージレングス６０６、メッセージＩＤ６０８、クエリーＴＬＶ６１０、メッセージＩＤ  ＴＬＶ６１２、ツリーＴＬＶ６１４、オプションパラメータ６１６を含んでいる。メッセージレングス６０６は、メッセージＩＤ６０８、クエリーＴＬＶ６１０、メッセージＩＤ  ＴＬＶ６１２、ツリーＴＬＶ６１４及びオプションパラメータ６１６の累積レングスをオクテットで示している。メッセージＩＤ６０８は、そのメッセージを識別するために使用される３２ビット値である。クエリーＴＬＶ６１０は、バックトレースメッセージ５００（図５）に含まれるクエリーＴＬＶ５１２（図５）と同一である。メッセージＩＤ  ＴＬＶ６１２は、対応するバックトレースメッセージ５００（図５）のメッセージＩＤ５０８（図５）の値である。ツリーＴＬＶ６１４は、図７を参照して以下で説明する。オプションパラメータ６１６は、ＴＬＶとしてそれぞれが符号化される１つ以上のパラメータを含む可変長フィールドである。
【００３２】
オプションパラメータ６１６は、クエリーラベルＴＬＶ、ＩＰＶ４／６専用リンクフィードバックＴＬＶ、クエリーマージフラグＴＬＶ、入口フラグＴＬＶ、予約帯域幅ＴＬＶ、集約ＴＬＶを含むことができる。クエリーラベルＴＬＶは、インターネットソサエティで発行されている、draft-ietf-mpls-lsp-query-03.txtのＭＰＬＳ  ＬＤＰクエリーメッセージ説明書に記載されている。ＩＰＶ４／６専用リンクフィードバックＴＬＶは、インターネットソサエティで発行されている、draft-ietf-mpls-te-feed-03.txtのＬＳＰフィードバックを持つトポロジーデータベースの精度の改良に記載されている。クエリーマージフラグＴＬＶは、インターネットソサエティで発行されている、draft-ietf-mpls-lsp-query-03.txtのＭＰＬＳ  ＬＤＰクエリーメッセージ説明書に記載されている。入口フラグＴＬＶは、ビットの組のリストであり、これは、ＬＳＰツリー上のＬＳＲに対応するマスク内で可変長の２ビットからなる。入口フラグＴＬＶのレングス（長さ）は、次のバイトに切り上げられる。Ｑ７がクエリーＴＬＶに設定される場合、経路上の各ＬＳＲは、自身の対応するビットをマスク内に設定しなければならない。このビットは、ツリーＴＬＶ内のノードと同じ順序で設定される。予約帯域幅ＴＬＶは、境界外リンクを介するＬＳＰに対して割り当てられる帯域幅を通知する。Ｑ４がクエリーＴＬＶに設定される場合、ＬＳＰツリー上の各ＬＳＲが、この情報を与える（fill in this information）、これは、このような情報を明らかにするように構成される場合である。ＬＳＲがこのような情報を秘匿するように構成される場合、ゼロレングスのＴＬＶが符号化される。集約ＴＬＶは、ＬＳＰツリー内の経路上で発生するＦＥＣ集約を通知する。Ｑ５フラグがクエリーＴＬＶに設定される場合、ＬＳＰツリー上の各ＬＳＲが、この情報を与える、これは、このような情報を明らかにするように構成される場合である。ＬＳＲがＦＥＣ集約を実行する場合、符号化情報はＦＥＣを含み、これには、バックトレースされるＦＥＣによって組み込むあるい組み込まれる。上記のＴＬＶで符号化された情報は、各ＬＳＲによるものであり、ツリーＴＬＶ内の情報と同じ順序であるべきである。
【００３３】
動作においては、バックトレースリプライメッセージ６００は、バックトレースメッセージ５００を受信する任意のノードによって生成され、これは、そのノードが、受信されたＦＥＣに対するＬＳＰを識別できる場合である。ノードがＦＥＣを識別できない場合、「バックトレースするＬＳＰがない」ことを示すステータスを有する通知メッセージでリプライする。ノードがＬＳＰの入口ノードであり、かつ同位のダウンストリームが存在しない場合、バックトレースリプライメッセージ６００を同位のダウンストリームＬＳＰに直ちに送信することができる。ノードが、ＬＳＰに対する同位のアップストリームを有するＬＳＰの入口ノードあるいは入口ノードでない場合、上述したように、計算対象の同位のアップストリームＬＳＰ（シブリング）セット「Ｐ」内のＬＳＲから応答を待機する、あるいはタイムアウトが発生するまで待機する。同位のアップストリームＬＳＰからの応答に対する時間期間は、構成依存であり、かつ局所的に構成可能とすべきである。タイムアウト期間が一旦経過すると、ノードは、タイムアウト期間内で応答された、同位のアップストリームＬＳＰから収集された情報がどのようなものであっても、バックトレースリプライメッセージ６００を生成する。収集されたＬＳＰサブツリー情報は、バックトレースリプライメッセージ６００内のツリーＴＬＶ６１４として符号化される。タイムアウト期間後に受信される応答は、無視される。
【００３４】
ノードがバックトレースメッセージ５００を、任意の同位のアップストリームＬＳＰに転送できない場合、その自身の情報を有するバックトレースリプライメッセージ６００で直ちに応答する。この情報は、このノードが、バックトレースリプライメッセージ６００内の入口フラグＴＬＶを介して、バックトレースメッセージ５００で受信されるＦＥＣに対する実際の入口ノードでないことを示すことになる。加えて、バックトレースメッセージ５００の応答において、「バックトレース対象のＬＳＰがない」ことを示すステータスを有する通知メッセージが同位のＬＳＰから受信される場合、ＬＳＲは、その同位のＬＳＲからバックトレースリプライメッセージ６００の待機を停止する。
【００３５】
各ノードは、メッセージＩＤ  ＴＬＶ６１２をバックトレースリプライメッセージ６００に符号化する。バックトレースメッセージ５００とバックトレースリプライメッセージ間のマッピングは、メッセージＩＤ５０８及び６０８に基づいている。メッセージＩＤ  ＴＬＶ６１２以外は、各ノードは、問い合わされた情報（帯域幅、マージ情報、入口あるいは非入口ＬＳＲ、集約情報等）を符号化する。符号化の完了後、バックトレースリプライメッセージ６００は逆経路で対象あるいは出口ノードに返信される。ＬＳＰツリー上の各ＬＳＲは、どのようなクエリーフラグが設定されているかに従って、自身の情報を符号化する。バックトレースリプライメッセージ６００は、実際の逆経路及び、バックトレースメッセージ５００が通過する同一のＬＳＰレベルに従う。
【００３６】
クエリーＴＬＶ５１２は、バックトレースメッセージ５００で通過する、これは、それが、バックトレースメッセージ５００を更なるアップストリームへ転送できない入口ノードあるいはノードに到達するまである。次に、クエリーＴＬＶ５１２は、クエリーＴＬＶ６１０として、逆フローバックトレースリプライメッセージ６００にコピーし、また、これは、どんな情報がバックトレース内で問い合わされているかを把握するために、入口及び中間ＬＳＲで使用される。クエリーＴＬＶ５１２及び６１０への拡張は、以下のようになる。フラグＱ３及びＱ８は、バックトレースメッセージ５００で使用されない。それらが設定される場合、それらは、ＬＳＰツリー上のＬＳＲには無視される。フラグＱ４及びＱ７は、ＬＳＰツリー内の割当帯域幅及び入口情報を収集するために使用される。フラグＱ４は、帯域幅を問い合わせ、設定されている場合、バックトレースメッセージ５００を受信するＬＳＲは、ＬＳＰに対する境界外リンクを介して割り当てられた帯域幅を符号化する。フラグＱ５は、ＦＥＣ集約情報を収集する。フラグＱ７は、ＬＳＰツリー内のどのＬＳＲが、バックトレースメッセージ５００で受信されるＦＥＣに対する入口ノードとして動作するかを問い合わせる。
【００３７】
図７を参照すると、本発明の実施形態に従うツリーＴＬＶ６１４に対する符号化が示される。ツリーＴＬＶ６１４は、ツリーを再帰的に取得する構造である。ツリーＴＬＶ６１４は、以下のフィールド：ゼロであるＵビット７０２、ゼロであるＦビット７０９、ツリーＴＬＶタイプ７０６、レングス７０８、アドレスファミリ７１０、ＩＰアドレス７１２、シビリングカウント７１４、サブツリー１  ７１６及びサブツリー２  ７１８のような任意のサブツリーを含んでいる。レングス７０８は、アドレスファミリ７１０、ＩＰアドレス７１２、シビリングカウント７１４及びサブツリー１  ７１６及びサブツリー２  ７１８のような任意のサブツリーの累積レングスをオクテットで示している。ＩＰアドレス７１２は、ルートノードのＩＰ  Ｖ４／Ｖ６（境界外ポート）アドレスである。ＩＰアドレス７１２は、シビリングカウント７１４に続き、これは、現存（サブ）ツリールートに続くサブツリーの総数を示している。シビリングカウント７１４は、０〜２５５範囲の８ビット値であり、ここで、値２５５は、ＬＳＲがシビリングカウントを明らかにしたくないことを通知するために予約されている。サブツリー１  ７１６及びサブツリー２  ７１８のようなサブツリー構造は、シビリングカウント７１４に続く。シビリングカウント７１４の値は、ツリー内のリーフノードに対しては０となる。リーフノードは、ＬＳＰの入口地点にもっとも近い。ＬＳＲが実際の入口ノードであるかどうかは、入口フラグＴＬＶから検出することができる。
【００３８】
図８を参照すると、本発明の実施形態に従う入口フラグＴＬＶ８００に対する符号化が示される。入口フラグＴＬＶ８００は、以下のフィールド：ゼロであるＵビット８０２、ゼロであるＦビット８０４、入口フラグＴＬＶタイプ８０６、レングス８０８、ＬＳＲ数８１０、１つ以上の入口フラグ８１２を含んでいる。レングス８０８は、ＬＳＲ数８１０及び１つ以上の入口フラグ８１２の累積レングスをオクテットで示している。ＬＳＲ数８１０は、ＬＳＰツリー内のＬＳＲ数を記憶するための４バイトフィールドである。この数は、ツリーＴＬＶ６１４で符号化されるＬＳＲ数と同一である。入口フラグ８１２内の各２ビットは、ＬＳＲに対する入口ノード情報を示している。ＬＳＲが、バックトレースＬＳＰに対する実際の入口ノードである場合は、入口フラグ８１２には０１が設定される、そうでない場合は、１０が設定される。ＬＳＲが入口情報を秘匿したい場合、入口フラグは００に設定される。符号化長は、次のバイトに切り上げられる。各ＬＳＲは、ＬＳＲ数８１０を更新し、それに従って、対応する入口フラグ８１２を設定する。入口情報は、ツリーＴＬＶ６１４内のノードと同じ順序で符号化される。
【００３９】
図９を参照すると、本発明の実施形態に従う予約帯域幅ＴＬＶ９００に対する符号化が示される。予約帯域幅ＴＬＶ９００は、以下のフィールド：Ｕビット９０２、Ｆビット９０４、予約帯域幅ＴＬＶタイプ９０６、レングス９０８、ＬＳＰ  ＩＤ９１０、保持優先度９１２、割当帯域幅９１４、アドレスファミリ９１６、インタフェースＩＰアドレス（ニアエンド）９１８、インタフェースＩＰアドレス（ファーエンド）９２０、オプションパラメータ９２２を含んでいる。レングス９０８は、ＬＳＰ  ＩＤ９１０、保持優先度９１２、割当帯域幅９１４、アドレスファミリ９１６、インタフェースＩＰアドレス（ニアエンド）９１８、インタフェースＩＰアドレス（ファーエンド）９２０、オプションパラメータ９２２の累積レングスをオクテットで示している。ＬＳＰ  ＩＤ９１０は、バックトレースＣＲ−ＬＳＰのＩＤである。保持優先度９１２は、ＣＲ−ＬＳＰの保持優先度である。割当帯域幅９１４は、バイト／秒あたりの、ＣＲ−ＬＳＰの境界外リンクを介して割り当てられる帯域幅である。アドレスファミリ９１６は、ＴＬＶ内の２つのＩＰアドレスに続くアドレスファミリである。インタフェースＩＰアドレス（ニアエンド）９１８は、ニアエンドのインタフェースのＩＰアドレスである。インタフェースＩＰアドレス（ファーエンド）９２０は、ファーエンドのインタフェースのＩＰアドレスである。例えば、第１アドレスがＡ（ニアエンド）で、第２アドレスがＢ（ファーエンド）である場合、帯域幅は、ＡからＢ方向に予約される。ＬＳＰツリー上のＬＳＲは、予約帯域幅情報をバックトレースリプライメッセージ６００に追加する。このベクトル要素は、ツリーＴＬＶ内のノードと同じ順序で符号化される。例えば、ツリーＴＬＶ６１４｛Ｒ１、２、Ｓ１、０、Ｓ２、０｝が予約帯域幅ベクトル｛１０、１００｝を持っていると想定する。これは、Ｒ１及びＳ１間のリンク上で予約された帯域幅単位が１０であることを示し、リンクＲ１及びＳ２間で予約された帯域幅単位が１００であることを示している。リンクの各サイド上のＩＰアドレスと、ＬＳＰの保持優先度は、予約帯域幅ベクトルの個々の要素を復号することによって取得することができる。オプションパラメータ９２２は、将来のオプションパラメータ用に予約されている。
【００４０】
図１０を参照すると、本発明の実施形態に従う集約ＴＬＶ１０００に対する符号化が示される。集約ＴＬＶ１０００は集約要素のリストであり、以下のフィールド：Ｕビット１００２、Ｆビット１００４、集約ＴＬＶタイプ１００６、レングス１００８、ＬＳＲ数１０１０及び、集約要素１、集約要素２、．．．、集約要素ｎのような１つ以上の集約要素１０１２を含んでいる。レングス１００８は、ＬＳＲ数１０１０及び１つ以上の集約要素１０１２の累積レングスをオクテットで示している。ＬＳＲ数１０１０は、ＬＳＰツリー内のＬＳＲ数を記憶するための４バイトフィールドである。この数は、ツリーＴＬＶ６１４内で符号化されているＬＳＲ数と同じである。集約要素１０１２〜１０１６（ＦＥＣ要素）の順序は、ツリーＴＬＶ６１４内のＬＳＲの順序に対応する。集約ＴＬＶ１０００のレングスの符号化は、次のバイトに切り上げられる。
【００４１】
図１１を参照すると、本発明の実施形態に従う図１０で示される集約要素１０１２の符号化が示される。集約要素１０１２は、以下のフィールド：集約情報１１０２及びＦＥＣ要素１１０４を含んでいる。集約情報１１０２は、ＬＳＲに対する集約情報を示す２ビットである。ＬＳＲが集約を実行する場合、このビットは０１に設定され、そうでない場合は、１０に設定される。ＬＳＲが集約情報を秘匿したい場合、これらのビットは００に設定される。ＦＥＣ要素１１０４は、集約情報１１０２に続く。集約ビットが１０あるいは００に設定される場合、ＦＥＣ要素１１０４は明らかにされない。
【００４２】
本明細書で説明される実施形態及び例示は、本発明及びその実用的な用途を最適に説明するものであり、これによって、当業者に、本発明を構成し、かつ利用することを可能にする。しかしながら、当業者は、上述の説明及び例示が、図示及び例示のためだけの目的によって提示されていることが理解されるであろう。上述の説明は、本発明を、開示される構成そのもので完結し、かつ制限することを意図するものではない。請求項の精神及び範囲から逸脱しない、上述の教示の観点で、様々な変形及び変更が可能である。
【図面の簡単な説明】
【００４３】
【図１】本発明の実施形態に従うネットワークのブロック図である。
【図２】本発明の実施形態に従うネットワーク内の様々なタイプのノードのトレースバックメカニズムを示すブロック図である。
【図３Ａ】本発明の実施形態に従うトレースバックメカニズムの一例を示すブロック図である。
【図３Ｂ】本発明の実施形態に従うトレースバックメカニズムの一例を示すブロック図である。
【図３Ｃ】本発明の実施形態に従うトレースバックメカニズムの一例を示すブロック図である。
【図３Ｄ】本発明の実施形態に従うトレースバックメカニズムの一例を示すブロック図である。
【図４】従来技術に従う標準ラベル配信プロトコルの符号化を示す図である。
【図５】本発明の実施形態に従うバックトレースメッセージの符号化を示す図である。
【図６】本発明の実施形態に従うバックトレースリプレイメッセージの符号化を示す図である。
【図７】本発明の実施形態に従うツリータイプレングス値の符号化を示す図である。
【図８】本発明の実施形態に従う入口フラグタイプレングス値の符号化を示す図である。
【図９】本発明の実施形態に従う予約帯域幅タイプレングス値の符号化を示す図である。
【図１０】本発明の実施形態に従う集約タイプレングス値の符号化を示す図である。
【図１１】本発明の実施形態に従う図１０に示される集約要素の符号化を示す図である。
【図１】
2005516535.tif 000003
【図２】
2005516535.tif 000004
【図３Ａ】
2005516535.tif 000005
【図３Ｂ】
2005516535.tif 000006
【図３Ｃ】
2005516535.tif 000007
【図３Ｄ】
2005516535.tif 000008
【図４】
2005516535.tif 000009
【図５】
2005516535.tif 000010
【図６】
2005516535.tif 000011
【図７】
2005516535.tif 000012
【図８】
2005516535.tif 000013
【図９】
2005516535.tif 000014
【図１０】
2005516535.tif 000015
【図１１】
2005516535.tif 000016
【国際調査報告】
2005516535.tif 000017
2005516535.tif 000018
2005516535.tif 000019