(57)【特許請求の範囲】
【請求項１】
自装置がコネクション機能網に属しているか否かを示す情報を載せたパケットを送信する送信手段と、
他の装置から受信したパケットから、該他の装置がコネクション機能網に属しているか否かに関する情報及び、ネットワークの構成に関する情報を抽出する受信手段と、
該受信手段が抽出した情報に基づき、どの装置がコネクション機能網に属するかを明示するネットワークのルーティングツリーを生成するツリー生成手段と、
前記ネットワークのルーティングツリーに基づいて、自装置がコネクション機能網の境界装置であるか否かを判断する判断手段と、
を備えることを特徴とするルーティング情報マッピング装置。
【請求項２】
前記ルーティングツリーと、コネクション機能網の境界装置に関する情報から、コネクション機能網に接続されている外部網に関する情報を取得する外部網情報取得手段、
を更に備えることを特徴とする請求項１に記載のルーティング情報マッピング装置。
【請求項３】
自装置が該境界装置であった場合、コネクション機能網と自装置に接続する外部網とのルーティング情報を対応付けるテーブルを生成するマッピング手段、
を更に備えることを特徴とする請求項２に記載のルーティング情報マッピング装置。
【請求項４】
前記送信手段は、自装置がどのコネクションプロトコルを使用しているかを示す情報を前記パケットに載せて送信することを特徴とする請求項１に記載のルーティング情報マッピング装置。
【請求項５】
各装置からネットワークの構成に関する情報と、自装置がコネクション機能網に属しているか否かを示す情報を各装置から受信し、得られた情報を格納し、各装置からの要求に従って、ネットワークの構成に関する情報と各装置がコネクション機能網に属しているか否かを示す情報とを、該要求を送信してきた装置に対して送信するサーバ手段を更に備えることを特徴とする請求項１に記載のルーティング情報マッピング装置。
【請求項６】
前記サーバ手段は、各装置がどのコネクションプロトコルを使用しているかを示す情報を各装置から受信し、該情報を格納し、各装置からの要求に従って、該情報を要求を行った装置に送信することを特徴とする請求項５に記載のルーティング情報マッピング装置。
【請求項７】
前記パケットは、ルーティングプロトコルを用いて送受信されることを特徴とする請求項１に記載のルーティング情報マッピング装置。
【請求項８】
前記パケットは、コネクションプロトコルを用いて送受信されることを特徴とする請求項１に記載のルーティング情報マッピング装置。
【請求項９】
他の装置から送信された、コネクション機能網と自装置に接続する外部網とのルーティング情報を対応付けるテーブルを、自装置においてルーティング情報として使用することを特徴とする請求項３に記載のルーティング情報マッピング装置。
【請求項１０】
前記テーブルが複数の他の装置から得られた場合、該テーブルを得たネットワークのルートに関して、コストを算出し、該コストの最適なルートを介して送信されてきた該テーブルを使用することを特徴とする請求項９に記載のルーティング情報マッピング装置。
【請求項１１】
（ａ）自装置がコネクション機能網に属しているか否かを示す情報を載せたパケットを送信するステップと、
（ｂ）他の装置から受信したパケットから、該他の装置がコネクション機能網に属しているか否かに関する情報及び、ネットワークの構成に関する情報を抽出するステップと、
（ｃ）該ステップ（ｂ）で抽出した情報に基づき、どの装置がコネクション機能網に属するかを明示するネットワークのルーティングツリーを生成するステップと、
（ｄ）前記ネットワークのルーティングツリーに基づいて、自装置がコネクション機能網の境界装置であるか否かを判断するステップと、
を備えることを特徴とするルーティング情報マッピング方法。
【請求項１２】
（ｅ）前記ルーティングツリーと、コネクション機能網の境界装置に関する情報から、コネクション機能網に接続されている外部網に関する情報を取得するステップ、を更に備えることを特徴とする請求項１１に記載のルーティング情報マッピング方法。
【請求項１３】
（ｆ）自装置が該境界装置であった場合、コネクション機能網と自装置に接続する外部網とのルーティング情報を対応付けるテーブルを生成するステップ、
を更に備えることを特徴とする請求項１２に記載のルーティング情報マッピング方法。
【請求項１４】
前記ステップ（ａ）は、自装置がどのコネクションプロトコルを使用しているかを示す情報を前記パケットに載せて送信することを特徴とする請求項１１に記載のルーティング情報マッピング方法。
【請求項１５】
（ｇ）各装置からネットワークの構成に関する情報と、自装置がコネクション機能網に属しているか否かを示す情報を各装置から受信し、得られた情報を格納し、各装置からの要求に従って、ネットワークの構成に関する情報と各装置がコネクション機能網に属しているか否かを示す情報とを、該要求を送信してきた装置に対して送信するステップを更に備えることを特徴とする請求項１１に記載のルーティング情報マッピング方法。
【請求項１６】
前記ステップ（ｇ）では、各装置がどのコネクションプロトコルを使用しているかを示す情報を各装置から受信し、該情報を格納し、各装置からの要求に従って、該情報を要求を行った装置に送信することを特徴とする請求項１５に記載のルーティング情報マッピング方法。
【請求項１７】
前記パケットは、ルーティングプロトコルを用いて送受信されることを特徴とする請求項１１に記載のルーティング情報マッピング方法。
【請求項１８】
前記パケットは、コネクションプロトコルを用いて送受信されることを特徴とする請求項１１に記載のルーティング情報マッピング方法。
【請求項１９】
他の装置から送信された、コネクション機能網と自装置に接続する外部網とのルーティング情報を対応付けるテーブルを、自装置においてルーティング情報として使用することを特徴とする請求項１３に記載のルーティング情報マッピング方法。
【請求項２０】
前記テーブルが複数の他の装置から得られた場合、該テーブルを得たネットワークのルートに関して、コストを算出し、該コストの最適なルートを介して送信されてきた該テーブルを使用することを特徴とする請求項１９に記載のルーティング情報マッピング方法。
【請求項２１】
プロセッサに、
（ａ）自装置がコネクション機能網に属しているか否かを示す情報を載せたパケットを送信するステップと、
（ｂ）他の装置から受信したパケットから、該他の装置がコネクション機能網に属しているか否かに関する情報及び、ネットワークの構成に関する情報を抽出するステップと、
（ｃ）該ステップ（ｂ）で抽出した情報に基づき、どの装置がコネクション機能網に属するかを明示するネットワークのルーティングツリーを生成するステップと、
（ｄ）前記ネットワークのルーティングツリーに基づいて、自装置がコネクション機能網の境界装置であるか否かを判断するステップと、
を備えることを特徴とするルーティング情報マッピング方法を実行させるプログラムを格納した記録媒体。
【請求項２２】
（ｅ）前記ルーティングツリーと、コネクション機能網の境界装置に関する情報から、コネクション機能網に接続されている外部網に関する情報を取得するステップ、
を更に備えることを特徴とする請求項２１に記載の記録媒体。
【請求項２３】
（ｆ）自装置が該境界装置であった場合、コネクション機能網と自装置に接続する外部網とのルーティング情報を対応付けるテーブルを生成するステップ、
を更に備えることを特徴とする請求項２２に記載の記録媒体。
【請求項２４】
前記ステップ（ａ）は、自装置がどのコネクションプロトコルを使用しているかを示す情報を前記パケットに載せて送信することを特徴とする請求項２１に記載の記録媒体。
【請求項２５】
（ｇ）各装置からネットワークの構成に関する情報と、自装置がコネクション機能網に属しているか否かを示す情報を各装置から受信し、得られた情報を格納し、各装置からの要求に従って、ネットワークの構成に関する情報と各装置がコネクション機能網に属しているか否かを示す情報とを、該要求を送信してきた装置に対して送信するステップを更に備えることを特徴とする請求項２１に記載の記録媒体。
【請求項２６】
前記ステップ（ｇ）では、各装置がどのコネクションプロトコルを使用しているかを示す情報を各装置から受信し、該情報を格納し、各装置からの要求に従って、該情報を要求を行った装置に送信することを特徴とする請求項２５に記載の記録媒体。
【請求項２７】
前記パケットは、ルーティングプロトコルを用いて送受信されることを特徴とする請求項２１に記載の記録媒体。
【請求項２８】
前記パケットは、コネクションプロトコルを用いて送受信されることを特徴とする請求項２１に記載の記録媒体。
【請求項２９】
他の装置から送信された、コネクション機能網と自装置に接続する外部網とのルーティング情報を対応付けるテーブルを、自装置においてルーティング情報として使用することを特徴とする請求項２３に記載の記録媒体。
【請求項３０】
前記テーブルが複数の他の装置から得られた場合、該テーブルを得たネットワークのルートに関して、コストを算出し、該コストの最適なルートを介して送信されてきた該テーブルを使用することを特徴とする請求項２９に記載の記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワークにおけるルーティング情報マッピング装置に関する。
【０００２】
【従来の技術】
現在インターネットの標準化団体ＩＥＴＦ（Internet  Engineering  Task  Force）において、ＭＰＬＳ（MultiProtocol  Label  Switching ）の標準化が進められている。ＭＰＬＳはＡＴＭ（Asynchronous  Transfer  Mode）やフレームリレーといった、コネクション型の網とＩＰ網を統合する技術であり、インターネットの世界で最も注目されている技術の一つである。
【０００３】
歴史的経緯を見ると、ＭＰＬＳはＡＴＭと密接な関係がある。現在のインターネットサービスプロバイダ（ＩＳＰ）のバックボーン網（基幹網）はＡＴＭ交換機で構成されているのが標準的であり、ＡＴＭ網内エッジ装置（ＩＰ網とＡＴＭ網の境界装置）間（すなわち、基幹網）は、メッシュ型ネットワークで、ＰＶＣ（Permannent  Virtual  Circuit）コネクションを手動で設定し、かつ、ＰＶＣと宛先ＩＰアドレスの組を示すテーブルを手動で網内装置に設定することで、運用されてきた。
【０００４】
この状況の中、ＡＴＭ交換機にルータ機能を搭載し、ＩＰ上で動作する独自のコネクション確立プロトコルを開発することで、自動でＩＰパケットのアドレスを元に、コネクションを確立するＭＰＬＳが提案された。
【０００５】
現在、ＩＥＴＦでは、ＭＰＬＳ網の重要なアプリケーションとして網の高度な運用を可能にするトラフィック・エンジニアリングの方式を議論している。その中で、網内でトラフィックの負荷分散（Load  Balancing ）を行うことが話題の中心である。
【０００６】
負荷分散を行うためには、ＭＰＬＳ網内において、一つの入り口境界装置（ＩＰ網からＭＰＬＳ網への入り口）と出口境界装置（ＭＰＬＳ網からＩＰ網への出口）間に複数のルートを確立する技術が必須である。この技術は、明示的ルーティング（Explicit  Routing ）と呼ばれている。明示的ルーティングを実現するためのプロトコルが、現在二つ提案されている。ＩＥＴＦのシグナリングプロトコルであるＲＳＶＰ（Resource  Reservation  Protocol ）を拡張したＲＳＶＰＬＳＰ−tunneling と、ＭＰＬＳのオリジナルプロトコルであるＬＤＰ（Label  Distribution  Protocol ）を拡張したＣＲ−ＬＤＰである。これらは、任意の入り口境界装置から、指定した出口境界装置との間にコネクションを確立する。
【０００７】
なお、ＲＳＶＰの詳細については、ＲＦＣ２２０５、Resource  ReSerVation  Protocol （ＲＳＶＰ）−−−Version １  Functional  Specification （入手場所  ｆｔｐ：／／ｆｔｐ．ｉｓｉ．ｅｄｕ／ｉｎ−ｎｏｔｅｓ／ｒｆｃ２２０５．ｔｘｔ）を参照されたい。
【０００８】
【発明が解決しようとする課題】
ただし、ＩＥＴＦで標準化されているのは、プロトコルのみで、
１）どのようにして入り口境界装置が出口境界装置のＩＰアドレスを知るか
２）どのようにして確立したコネクションにＩＰアドレスを関係づけるか
が全く規定されていない。従って、現実的には、上記課題を解決しない限り自動負荷分散は実現不可能である。
【０００９】
本発明に於いては、特に、ＩＰルーティングプロトコルに注目する。
ＩＰパケットのフローは厳密には、
0003790658.tif 000002
のパラメータ組で定義される。ＭＰＬＳの負荷分散は、ＩＰパケットを、フローのパラメータの任意の組み合わせなどによるＦＥＣ（Forward  Equivaent  Class ）というフローと比較して、より大きいフローの束で扱う。ＦＥＣの具体例は、
0003790658.tif 000003
が挙げられる。負荷分散は、このＦＥＣを複数のルートで分散することで実現する。コネクションプロトコルは、複数ルート、つまり複数コネクションを提供するが、ＦＥＣをコネクションに対応付ける方式が抜け落ちている。言い換えると、ＦＥＣ・コネクション間マッピング方式を確立しないと、自動負荷分散は実現できない。
【００１０】
現状は、ＭＰＬＳルータの開発を進めている各社ベンダとも手動設定で、マッピングテーブルを作る方法を取っている。手動設定であると、決めうちした二点間においてのみ負荷分散するといった、限定された使い方しかできない。この程度の負荷分散機能では、網パフォーマンス向上の効果は薄い。
【００１１】
本発明の課題は、ネットワークにおいて自動負荷分散を実現する上で必要不可欠なコネクション機能網とコネクションレス網との間のルーティング情報のマッピング方法を提供することである。
【００１２】
【課題を解決するための手段】
本発明のルーティング情報マッピング装置は、自装置がコネクション機能網に属しているか否かを示す情報を載せたパケットを送信する送信手段と、他の装置から受信したパケットから、該他の装置がコネクション機能網に属しているか否かに関する情報及び、ネットワークの構成に関する情報を抽出する受信手段と、該受信手段が抽出した情報に基づき、どの装置がコネクション機能網に属するかを明示するネットワークのルーティングツリーを生成するツリー生成手段とを備えることを特徴とする。
【００１３】
本発明のルーティング情報マッピング方法は、（ａ）自装置がコネクション機能網に属しているか否かを示す情報を載せたパケットを送信するステップと、（ｂ）他の装置から受信したパケットから、該他の装置がコネクション機能網に属しているか否かに関する情報及び、ネットワークの構成に関する情報を抽出するステップと、（ｃ）該ステップ（ｂ）で抽出した情報に基づき、どの装置がコネクション機能網に属するかを明示するネットワークのルーティングツリーを生成するステップとを備えることを特徴とする。
【００１４】
本発明によれば、ルーティングプロトコル、あるいは、コネクションプロトコルを介して、ネットワーク装置間で授受されるパケットに、パケットを送信した装置がコネクション機能網の装置か否かを示す情報を付加して他の装置に送信する。従って、この処理をネットワークの各装置が行うことによって、ネットワークの全ての装置が、どの装置がコネクション機能網装置であり、どの装置がそうでないかを自動的に判別することが出来る。
【００１５】
この機能を使えば、コネクション機能網の境界装置を判別することができ、境界装置において、コネクション機能網に接続されている外部網の情報を集めて、コネクション機能網のコネクションと、外部網のアドレスとの間に対応関係を付けるルーティング情報のマッピングを行うことが出来る。
【００１６】
従って、従来技術で述べたように、ルーティング情報のマッピング手段を提供することにより、ネットワークにおける負荷分散を効率的に行うことが出来る。
【００１７】
【発明の実施の形態】
本発明では、ＯＳＰＦ（Open  Shortest  Path  First ：ルータがルーティングプロトコルを共有する方式を規定したプロトコル）といった既存のインターネットルーティングプロトコル情報を利用して、完全自動で、ＦＥＣ・コネクション間マッピングを行い、その情報をコネクションプロトコルに伝達し、負荷分散に必要な複数ルートを確立する方式を提案する。ルーティングプロトコルへの変更は、新たに識別子を追加する程度の非常に小さい変更で済む。
【００１８】
これにより、ＭＰＬＳ網における負荷分散を自動化し、さらには網の任意リンクの負荷状態に応じて迂回経路の追加・削除を自律的に行うといった運用が実現でき、網の性能の大きな向上が期待できる。
【００１９】
なお、ＯＳＰＦの詳細については、ＯＳＰＦ  Version ２（入手場所  ｆｔｐ：／／ｆｔｐ．ｉｓｉ．ｅｄｕ／ｉｎ−ｎｏｔｅｓ／ｒｆｃ２３２８．ｔｘｔ）を参照されたい。
【００２０】
また、本発明の説明に使用するプロトコルなどの詳細については、「インターネットＲＦＣ辞典；アスキー出版局  ＩＳＢＮ４−７５６１−１８８８−７」を参照されたい。
【００２１】
図１は、本実施形態で説明する網の基本構成を示す図である。
図１に示す構成においては、周囲を囲むＩＰ網（コネクションレス型の網）の間にコネクション機能網（コネクション型の網：例えば、ＡＴＭ網等）が挟まった構成になっている。ＩＰ網とコネクション機能網との境界には、コネクション機能網境界装置が置かれ、コネクション機能網内には、コネクション機能網装置が置かれる。ここで、コネクション機能網装置やコネクション機能網境界装置は、コネクション機能網のルータである。
【００２２】
図１の左側のＩＰ網には端末Ｈ１、図１の右側のＩＰ網にはＩＰ網ルータＲ１と端末Ｈ２、Ｈ３、Ｈ４が位置する。
コネクション機能網装置（境界装置を含む）は、以下の機能を持つ。
・ＩＰルータ機能（ＩＰパケットのルーティング／フォワーディング機能）
・高機能ルーティングプロトコル
・コネクション型インターフェースとその制御機構
・コネクションプロトコル
・コネクション制御機構
すなわち、コネクション機能網装置は、コネクションプロトコルによってコネクション機能網内に確立するコネクションを管理し、併せて送信アドレス等のＩＰパケット情報とコネクションとの対応表を管理する。
【００２３】
ＩＰ網ルータは、以下の機能を持つ。
・ＩＰルータ機能（ＩＰパケットのルーティング／フォワーディング機能）
・高機能ルーティングプロトコル
端末は、以下の機能を持つ。
・ＩＰ端末機能（ＲＦＣ１１２２相当）
また、次のような条件を前提として考える。
○デフォルトコネクション
コネクション機能網装置間には、ルーティングプロトコルのメッセージとコネクションプロトコルの制御メッセージ転送用コネクションが存在する。コネクションとして、ポイント・ポイント・コネクションまたはポイント・マルチポイント・コネクションを使うことが出来るが、ルーティングプロトコル、コネクションプロトコルの特性に合ったコネクションを用意することが望ましい。
【００２４】
ここで、ルーティングプロトコルとは、音声パケット等をルーティングするために必要な情報をコネクション機能網装置やルータ等の間でやりとりするためのプロトコルであり、コネクションプロトコルとは、実際に音声パケット等を送受信するためのプロトコルである。
○ホスト端末のアドレス
図１に示す基本網構成において、端末Ｈ１〜Ｈ４は、ルーティングプロトコルを実装していない。そのため、端末Ｈ１〜Ｈ４のホスト（不図示）が直接接続されているルータ（例えば、ルータＲ１等であり、その他については図示していない）のルーティングテーブルに、端末Ｈ１〜Ｈ４のＩＰアドレスを登録していることを前提とする。
○ルーティングプロトコル
インターネットの標準化団体に相当するＩＥＴＦで標準化されたＯＳＰＦのような、自律的に網内のルーティングを解決する、ダイナミックルーティングプロトコルが各装置（ルータ、コネクション機能網装置、コネクション機能網境界装置）に実装されていることを前提とする。
【００２５】
図２は、ＭＰＬＳにおけるコネクションの確立手順を示す図である。
まず、ステップ１において、コネクション機能網装置ＬＳＲ１〜４及びルータＲ１は、ルーティングプロトコルであるＯＳＰＦを利用して、ルーティングテーブルの内容を交換し、同じルーティングテーブルを全てのコネクション機能網装置ＬＳＲ１〜４及びルータＲ１が共有する。
【００２６】
ルーティングテーブルは、パケットの送信先のアドレス（destination  address：d.a ）と、対応するアドレスへパケットを送信する場合に、パケットを出力すべきインターフェース（outgoing  interface ：ＯＩ）とを対にして格納している。
【００２７】
図２のステップ１におけるＯＳＰＦによるルーティングテーブルの授受は、レイヤ構造では、レイヤ３に属する処理である。
次に、ステップ２において、コネクション機能網に含まれるコネクション機能網装置ＬＳＲ１〜ＬＳＲ４の間にコネクションが確立される。
【００２８】
次に、ステップ３において、各コネクション機能網装置は、ＩＰパケットをコネクション機能網に収容するために、特定のd.a.とＯＩを有するＩＰパケットをどのようにルーティングするかを示すラベルテーブルをレイヤ２のレベルで保持している。このラベルテーブルは、in  label とout  labelとを対応させ、更に、これをルーティングテーブルに対応させることによって、実際にパケットをルーティングするものである。in  label やout  labelは、例えば、ＡＴＭ通信を例に取ると、in  label が入力するパケットのＶＰＩ／ＶＣＰ（Virtual  Path  Identifier ／Virtual  Channel  Identifier）であり、out  labelが出力する場合のＶＰＩ／ＶＣＩである。すなわち、in  label は、コネクション機能網装置にパケットが入力するときのコネクションの識別子であり、out  labelは、コネクション機能網装置からパケットが出力されるときのコネクションの識別子であり、これらの対応を各コネクション機能網装置において付けておくことにより、コネクションの確立を実現する。
【００２９】
また、ラベルテーブルは、レイヤ２のレベルで使用されるテーブルであり、コネクション機能網内では、レイヤ２のレベルでパケットの転送が行われるので、高速に転送が行われる。一方、ＩＰパケットなどの転送は、レイヤ３のルーティングテーブルによって行われるので、コネクション機能網境界装置ＬＳＲ１、ＬＳＲ３、ＬＳＲ４では、ラベルテーブルとルーティングテーブルとの対応を付けるようにする。このとき、例えば、端末Ｈ１から端末Ｈ２〜４にパケットを送信する場合、ＬＳＲ１においては、入力側がコネクションレスのＩＰ網であるため、入力コネクションの識別子が存在しないので、ＬＳＲ１が有するラベルテーブルにおいては、in  label の項は、空白となり、out  labelのみが登録されることとなる。逆に、ＬＳＲ３、４においては、out  labelの登録が空欄となり、in  label のみの登録が生じることになる。
【００３０】
以上のようにして、ＭＰＬＳにおいては、コネクションレスのパケットであるＩＰパケットに対してコネクションの確立を行う。
図３は、ＯＳＰＦの動作手順を示す図である。
【００３１】
同図では、ＯＳＰＦのパケットのやりとりを示している。ルータ（ＬＳＲ１〜４）起動時（同時に全ルータが起動したとする）に、お互いのインターフェース情報を交換しＡｕ。これをフラッディング（flooding）と言う。
【００３２】
パケットのやりとりのシーケンスは、
（１）各ルータから、隣のルータにＯＳＰＦメッセージを送信する。
（２）各ルータは、となりから受けたメッセージをメッセージ処理後、その次のルータに転送する。
（３）（２）と同様、新たに受けたメッセージを転送する。
【００３３】
同図のネットワークでは、１番遠いルータは、３ホップ（３段）なので、あるＯＳＰＦメッセージは、３段転送された後、転送終了となる。これにより、全ルータでルーティング情報が同期する。ここで、ホップとは、ネットワーク装置間に形成されるコネクションの単位のことであり、複数のネットワーク装置を介したコネクションは複数のホップからなる。
【００３４】
上記手順を詳述すると、まず、ＬＳＲ１から送信されるＯＳＰＦメッセージは、（１−ｂ）に示されるように、ＬＳＲ２で受信される。ＬＳＲ２は、ＬＳＲ１から受信したＯＳＰＦメッセージを（２−ｂ）で示されるように、ＬＳＲ３とＬＳＲ４に転送する。ＬＳＲ３で、ＯＳＰＦメッセージは終端される。一方、おＳＲ４では、その先にルータＲ１が接続されているので、（３−ｂ）で示されるように、ＯＳＰＦメッセージをルータＲ１に転送する。
【００３５】
ＬＳＲ２から送出されるＯＳＰＦメッセージは、（１−ａ）、（１−ｃ）、（１−ｅ）に示されるように、ＬＳＲ１、ＬＳＲ３、ＬＳＲ４に送られる。ＬＳＲ１とＬＳＲ３では、ＯＳＰＦメッセージを終端する。ＬＳＲ４では、ＬＳＲ２から受け取ったＯＳＰＦメッセージをルータＲ１に転送する（２−ｅ）。
【００３６】
ＬＳＲ３から送出されるＯＳＰＦメッセージは、（１−ｄ）に示されるように、ＬＳＲ２に送られ、更に、（２−ｄ）で示されるように、ＬＳＲ１とＬＳＲ４に転送される。ＬＳＲ１では、受信したＯＳＰＦメッセージを終端する。ＬＳＲ４では、（２−ｄ）で受け取ったＯＳＰＦメッセージをルータＲ１に転送する（３−ｄ）。
【００３７】
ＬＳＲ４から送出されるＯＳＰＦメッセージは、（１−ｆ）に示されるように、ルータＲ１とＬＳＲ２に送られる。ルータＲ１では、ＯＳＰＦメッセージを終端する。ＬＳＲ４からのＯＳＰＦメッセージを受け取ったＬＳＲ２は、（２−ｆ）に示されるように、ＬＳＲ１とＬＳＲ３にＯＳＰＦメッセージを転送する。
【００３８】
ルータＲ１から送出されるＯＳＰＦメッセージは、（１−ｇ）で示されるように、ＬＳＲ４に送られ、更に、（２−ｇ）で示されるように、ＬＳＲ２に送られる。ＬＳＲ２では、（３−ｇ）で示されるように、受信したＯＳＰＦメッセージをＬＳＲ１とＬＳＲ３に転送する。
【００３９】
次に、ＭＰＬＳにおけるＬ２コネクションへのＬ３ルーティング情報マッピング方式について説明する。
図４は、ルーティングプロトコルによるリンク情報配布の様子を示した図である。
【００４０】
図４において、端末Ｈ１から端末Ｈ４に通信する場合を考えると、ＩＰパケットはＩＰ網→コネクション機能網→ＩＰ網の順に転送される。ＩＰ網内は現在のルータでの処理に従い、ホップ・ホップ（各ルータ）でＩＰヘッダ処理を行い転送される。コネクション機能網では、二つの境界装置間に確立されているコネクション上を転送される。つまり、コネクション機能網内は、ＩＰヘッダ処理は行われず、コネクション機能網が持つラベルで転送処理される。コネクション機能網として、ＡＴＭ網を例に取ると、コネクション機能網内は、ＡＴＭセルのヘッダ中のＶＰＩ／ＶＣＩというラベルで転送される。
【００４１】
本実施形態は、全ての装置がＩＰルーティングプロトコルを実装していることを前提としている。つまり、コネクション機能網装置、コネクション機能網境界装置は、ＯＳＰＦといったルーティングプロトコルを実装し、ＩＰルーティング処理ができることが前提である。また、コネクション機能網装置は、コネクション機能を備えている。ＡＴＭスイッチ機能を備えたルータがこれに相当する。
【００４２】
どの装置も、ルーティングプロトコルの観点から見れば差はなく、同じルータに見えるので、どのルータがＩＰ網に属し、どれがコネクション網に属するかが分かるようにする。すなわち、どのルータがコネクション網機能を保有しているかを網全体に伝達することで、ＩＰ網とコネクション機能網との自動連携が可能になる。
【００４３】
ＭＰＬＳにおいて、ルーティングプロトコルとコネクション機能網装置（ＭＰＬＳルータ）が連携するために、どの装置が通常のルータで、どの装置がコネクション機能網装置であるかを自動で各装置が把握することを可能とする。これにより、各ノードにおいてルーティングツリーを形成する際、どの装置群がＩＰ網に属し、コネクション機能網に属するか、ネットワークマップを作ることができる。
【００４４】
ここで、どの装置群がＩＰ網に属し、どの装置群がコネクション機能網に属するかを各ルータが把握するための方策として、ルーティングプロトコルにおけるリンク情報交換パケット中に、コネクション機能網装置の識別子を追加する。
【００４５】
ルーティングプロトコルは、網全体に向けて、自己のインターフェースとそれにつながるリンク情報を広報する。その広報情報フィールド中に、コネクション機能網装置識別子を追加することで、網全体に、どの装置群がコネクション機能網に属するかの情報が伝達できる。
【００４６】
この情報を各装置で形成するルーティングツリーに反映させると、入り口境界装置、出口境界装置、また、出口境界装置の先にある網情報を得ることが可能である。
【００４７】
現在ＡＳ（Autonomous  System）内で主に利用されているルーティングプロトコルであるＯＳＰＦを例に取る。ＯＳＰＦは、ＬＳＡオブジェクトを用いて隣接ルータ間でリンク情報の交換を行う。
【００４８】
図５は、ＯＳＰＦにおける広報情報フィールドのうちのオプションフィールドを示した図である。
同図（ａ）に示すように、オプションフィールドには、様々なビットが設けられているが、両端にあるビットは使用されていない。
【００４９】
そこで、同図（ｂ）に示すように、使用されていないビットにＬビットというビットを新たに定義する。
Ｌビット：自装置がＭＰＬＳのＬＳＲ（Label  Switching  Router）であれば、１に設定する。もし、自装置がＭＰＬＳのＬＳＲでなければ、０に設定する。もし、このような拡張ビットを実装しないＯＳＰＦがあれば、Ｌビットの設定は行われないが、このような拡張ビットを実装するＯＳＰＦから見れば、自動的にＬビットは０とされたことと同じになるので、Ｌビットの設定ができないＯＳＰＦを使用したルータでは、コネクション機能網装置ではないと判断される。
【００５０】
図４に戻って説明をする。
図４は、ＯＳＰＦを用いた場合の情報配布シーケンスを示す。図中ではＬＳＲ４から生成されるリンク情報の伝達過程を示している。伝達は、ＯＳＰＦの情報伝達方法に完全に従う。各ルータでは、全てのルータは、ＯＳＰＦを実装しており、それぞれＬＳＲ４と同様にリンク情報をネットワークに伝達する。リンク情報を受け取った各ルータはコネクション機能網装置識別子をデータベースとして保管する。
【００５１】
ＭＰＬＳでの自動負荷分散を行うために必要なルーティング情報のマッピングを行うために必要な情報をルーティングプロトコル中に埋め込むので、非常に簡潔に実現することができる。ルーティングプロトコルの変更は識別子を記述するビットを一つ定義するのみであり、プロトコルへ要求される変更はほとんどない。
【００５２】
図６は、コネクション機能網装置識別子／クライアント・サーバモデルによるリンク情報の伝達方式を説明する図である。
図６の構成では、ネットワークにサーバを置き、そこにコネクション機能網装置識別情報を蓄積する。各ルータはクライアントとして、該情報を引き出したい時に、サーバにアクセスする。
【００５３】
サーバへの情報蓄積は、オペレータによる手動入力と、プロトコルによる情報伝達の方法が考えられる。
サーバに蓄積するコネクション機能網装置識別子は、トラヒックエンジニアリングの際、複数ルート検索を行うために使用するのが一つの目的である。つまり、ルーティング検索の基礎情報である、リンク情報データベースと共に使用されることが多い。従って、現実的には、サーバにルーティングのリンク情報と共に蓄積することが望ましい。
【００５４】
図７は、任意の装置をサーバとし、各コネクション機能網装置をＳＮＭＰクライアントとした構成を示す図である。
全ての装置にはＳＮＭＰ（Simple  Network  Management  Protocol ）が実装されているものとする。ＳＮＭＰサーバには、ネットワーク内全装置のエントリを持ち、どのクライアントがコネクション機能網装置であるかのエントリを予めオペレータが入力しておく。ＳＮＭＰサーバは、（各装置の起動時に）ＳＮＭＰクライアントにコネクション機能網装置識別情報を伝達する。
【００５５】
この実装は、既存のプロトコルには一切影響を与えずに、コネクション機能網と、その境界装置の情報が得られる。もしネットワークにＳＮＭＰサーバが存在すれば、それをデータ蓄積場所とできるので、実装が容易である。情報の管理の面から見ると、集中管理型であるので、メンテナンスは容易である。
【００５６】
また、ＭＰＬＳでトラフィック・エンジニアリングを実現するための手段として明示的ルーティングが必要であることは、前述したとおりであるが、これを実現するプロトコルは、複数提案されており、現在ＲＳＶＰ、ＬＳＰ−トンネリングとＣＲ−ＬＤＰが標準化される見通しである。ＭＰＬＳネットワーク内で、どのコネクション機能網装置がどのコネクションプロトコルを実装しているか知る必要がある。これを実装コネクションプロトコル識別子として、各コネクション機能網装置に伝達するようにする。上述した方式で伝達するコネクション機能網装置識別子情報に加え、実装コネクションプロトコル識別情報を持つことで、各装置はコネクション機能網で通信可能な相手のリストを知ることができる。
【００５７】
ＭＰＬＳにおいて、上記のような機能を設けることにより、ルーティングプロトコルとコネクション機能網装置（ＭＰＬＳルータ）が連携するために必要不可欠な技術であり、コネクション機能網装置が通信可能な相手を知ることが可能になり、ネットワークの確実な動作保証を提供することができる。
【００５８】
図８は、実装コネクションプロトコル識別子のルーティングプロトコルによる伝達方式を説明する図である。
本実施形態は、ルーティングプロトコルにおけるリンク情報交換パケット中に、装置に実装されているコネクションプロトコル識別子を追加する。
【００５９】
コネクションプロトコル識別子をルーティングプロトコルが交換する情報の中に埋め込む。ここでは、ＯＳＰＦを使用した場合の例を挙げる。例えば、ＯＳＰＦのオプションフィールド（８ビット）の１ビットを使用する。８ビット中、最右端のビット７をＲビットとして定義する。
【００６０】
Ｒビット：自装置がＲＳＶＰ  ＬＳＰ−トンネリングを実装するＬＳＲであれば、１を設定する。もし自装置においてＲＳＶＰ  ＬＳＰ−トンネリングが動作していなければ、０を設定する。もし、この拡張を実装しないＯＳＰＦがあれば、自動的に０を設定することになるので、ＲＳＶＰ  ＬＳＰ−トンネリングが動作しない装置であると見なされる。
【００６１】
このように、コネクションプロトコル識別子を埋め込むことで、ＯＳＰＦがリンク情報交換する際にネットワーク中に自動的にコネクションプロトコル情報が伝達される。
【００６２】
ＭＰＬＳ網での自動負荷分散を行うために必要なルーティング情報のマッピングを行う際に、必要な情報をルーティングプロトコル中に埋め込むので、非常に簡潔に実現することが出来る。ルーティングプロトコルの変更は識別子を記述するビットを一つ定義するのみであり、プロトコルへの影響はほとんどない。
【００６３】
図９は、ルーティングプロトコルによるコネクションプロトコル情報の配布の様子を示す図である。
図９では、コネクションプロトコル情報が、ＬＳＲ４から各ネットワーク装置に送信される様子を示している。上述したように、ＬＳＲ４は、ＯＳＰＦのオプションフィールドにＲビットを設定し、ルータＲ１とＬＳＲ２に情報を送信する。これにより、ルータＲ１とＬＳＲ２は、ＬＳＲ４が実装しているコネクションプロトコルを知ることができる。
【００６４】
また、ＬＳＲ２は、ＬＳＲ１とＬＳＲ３に、ＬＳＲ４から受け取った情報をそのまま転送する。従って、ＬＳＲ１とＬＳＲ３は、ＬＳＲ４からのＲビットの設定値を知ることができるので、やはり、ＬＳＲ４が実装しているコネクションプロトコルを知ることが出来る。
【００６５】
図１０は、実装コネクションプロトコル識別子のクライアント・サーバモデルによる伝達方式を説明する図である。
ネットワークにサーバを置き、そこにコネクション機能網装置識別情報を蓄積する。各ルータはクライアントとして、該情報を引き出したい時に、サーバにアクセスする。
【００６６】
サーバへの情報蓄積は、オペレータによる手動入力と、プロトコルによる情報伝達の方法が考えられる。
サーバに蓄積するコネクションプロトコル識別子は、トラフィックエンジニアリングの際、複数ルート検索を行うために使用するのが一つの目的である。つまり、ルーティング検索の基礎情報である、リンク情報データベースと共に使用されることが多い。従って、現実的には、サーバにルーティングのリンク情報と共に蓄積することが望ましい。
【００６７】
図１０は、任意の装置をサーバとし、各コネクション機能網装置をＳＮＭＰクライアントとした構成である。
全ての装置にはＳＮＭＰが実装されているものとする。ＳＮＭＰサーバには、ネットワーク内全装置のエントリを持ち、どのクライアントがコネクション機能網装置であるかのエントリを予めオペレータが入力しておく。ＳＮＭＰサーバは、（各装置の起動時に）ＳＮＭＰクライアントにコネクション機能網装置識別情報を伝達する。それにより、図１１のようなテーブルを構成でき、明示的なルーティングが通信可能である相手を判別することができる。
【００６８】
図１１は、サーバを保有するネットワークのどの装置のコネクション機能網装置であるか否か、及び、実装されているコネクションプロトコルを登録するテーブルである。
【００６９】
図１１においては、各装置のアドレスが登録されると共に、各アドレスによって特定された装置に、コネクション機能網装置識別子（Ｌビット）の値の検出結果と、コネクションプロトコル識別子（Ｒビット）の値の検出結果が登録される。
【００７０】
従って、図１１によれば、アドレスが１０．０．０１である装置は、コネクション機能網装置であり、ＲＳＶＰ  ＬＳＰ−トンネリングを実装していることが示され、アドレスが１０．２５．１．１の装置は、コネクション機能網装置であるが、ＲＳＶＰ  ＬＳＰ−トンネリングを実装していないことが示される。
【００７１】
図１０、１１で説明した実装方法は、既存のプロトコルには一切影響を与えずに、コネクション機能網とその境界装置の情報が得られるようになっている。もしネットワークにＳＮＭＰサーバが存在すれば、それをデータ蓄積場所とできるので、実装が容易である。情報の管理の面から見ると、集中管理型であるのでメンテナンスは容易である。
【００７２】
図１２は、コネクション機能網装置の本実施形態に関連する機能ブロックを示す図である。
各コネクション機能網装置は、ルーティングプロトコル１０を実装しており、ルーティングプロトコル１０は、以下の機能ブロックからなる。
【００７３】
すなわち、ネットワークのノードやリンク情報を有する、外部からのルーティングパケット（ＯＳＰＦパケット）を受信し、データベースに登録できる形に処理するパケット受信処理部１１が設けられている。パケット受信処理部１１は、受信したルーティングパケット（ＯＳＰＦパケット）から、ノード、リンク情報や、Ｌビット、Ｒビット情報を取得し、これをデータベースに格納することが出来るようなフォーマットに処理すると、ネットワークのノード、リンク情報及び、Ｌビット、Ｒビット情報を受信データのデータベース１２に送信する。受信データのデータベース１２では、受信したネットワークのノード（ルータ）、リンクの情報及びＬビット、Ｒビット情報を蓄積する。
【００７４】
ルーティング処理部１３は、パケットの経路を決定するためのルーティング機能を有する。ここで、追加機能として、自ルータからあらゆる地点までの経路を示すツリー情報を生成するツリー生成機能１４を設ける。ツリー生成機能１４で生成されたツリー情報は、トポロジーデータベース１５に渡される。ツリー情報の生成方法については後述する。
【００７５】
トポロジーデータベース１５は、ルーティング処理に際に生成したツリー情報を保持する。トポロジーデータベース１５は、どこの目的地に対して、どの経路を通り、また、ネットワークの中のどこが、コネクション機能網（ＭＰＬＳネットワーク）であるか、の情報を有する。
【００７６】
トポロジー判定処理部１６は、作られたトポロジーデータベース１５から、境界装置のリスト、及び、外部網情報を抽出するための処理機能を有する。トポロジー判定部１６で抽出された情報は、装置内のコネクション処理を行っているコネクション処理部へ受け渡される。
【００７７】
パケット送信処理部１７は、ルーティングプログラムであるＯＳＰＦに従って、ＯＳＰＦパケットを生成し、他のルータなどに送信する機能である。このとき、本実施形態においては、ＯＳＰＦパケットのオプションフィールドに、ＬビットとＲビットの設定を行う。ただし、パケット送信処理部１７のＬビット、Ｒビットの設定機能は、すべてのルータが有しているわけではなく、この機能を有しないルータから送出されるＯＳＰＦパケットには、Ｌビット、Ｒビットの設定は行われない。この場合、Ｌビット、Ｒビットの設定機能を有しないルータから送出されたＯＳＰＦパケットは、受信側において、自動的にＬビットとＲビットが０に設定されているものと判断される。
【００７８】
次に、コネクション機能網装置用ルーティング・ツリーの作成方式について説明する。
図４〜図１１で説明した方式で得られた、コネクション機能網装置の識別子情報とコネクションプロトコル識別情報をルーティングのリンク情報に追加し、リンク情報を元に二つの識別情報の追加されたルーティング・ツリーを作成する。
【００７９】
図１３は、ルーティングツリーのイメージを示す図である。
図１３（ａ）に従来の方式におけるＬＳＲ１が有するルーティングツリーを、図１３（ｂ）に本実施形態によるＬＳＲ１の有するルーティングツリーを示す。
【００８０】
図１３（ａ）に示すように、従来は、一つのルーティングエリア内では、コネクション機能網装置であるか、ＩＰルータであるか区別はつかない。また、実装コネクションプロトコル情報も持たない。従って、ルート（ＬＳＲ１）から見て、どの装置が境界装置であるか判断がつかない。
【００８１】
しかし、図１３（ｂ）に示すように、本実施形態によるルーティングツリーは、コネクション機能網装置識別子及びコネクションプロトコル識別子のビットがＯＮの場合、そのルータ（図１３（ｂ）の場合、ＬＳＲ１〜ＬＳＲ４）は、図中のように黒抜きの二重丸でしめすように、コネクション通信可能なコネクション機能網装置であると判断する。
【００８２】
また、図１３（ｂ）から分かるように、本実施形態に従って作成されたルーティングツリーでは、どの装置によりコネクション機能網が構成されており、どの装置が境界装置であるかの判断を行うことが出来る。
【００８３】
図１４に、ルーティングツリーを作成するための処理を示す疑似コードを示す。
ＯＳＰＦでは、リンク情報を元にＳＰＦ（Shortest  Path  First ）アルゴリズム（ＯＳＰＦを実現するためのアルゴリズムをこのように呼ぶ）が動作し、自装置をルートとしたルーティングツリーが作成される。また、その過程で、各destination に対するコストも計算される。注目する装置をポインタcurrent pointer で指し示す。
【００８４】
動作は、深さ方向に次々とエントリを探し、エントリが無くなったら（ツリーの先端まで到着したら）一つ戻り、エントリを探す、といった方式である。各エントリの追加判断の時（ルーチン中（１））、コネクション機能網装置識別子（Ｌビット）とコネクションプロトコル識別子（Ｒビット）を見て、両方ともビットが立っていれば、有効なコネクション機能網装置であると判断する。
【００８５】
次に、疑似コードを説明する。
まず、図１４において、初期化のステップでは、自ノードをツリーのルートとする。また、ポインタcurrent pointer を自ノードに設定する。次にＳＰＦルーチンを実行する。まず、while 文によって、以下の処理が繰り返し行われる。
【００８６】
まず、current pointer に隣接する（関連付けられた）リンク情報をＯＳＰＦＬＳＡ（Link  State  Advertisement）データベース（図１２の受信データのデータベースに対応し、隣のルータに送るべきデータを保持しているデータベースである）を検索して、取得する。
【００８７】
次に、IF文において、新しいエントリが発見されたか否かを判断する。もし、新しいエントリが見つかった場合には、新エントリをツリーに追加する。そして、エントリのリンク情報のオプションヘッダ（フィールド）のＬビットがＯＮかつＲビットがＯＮであるか否かを判断する。ＬビットとＲビットがＯＮの場合には、新エントリに対応する装置は、有効なコネクション機能網装置である旨判断し、その情報を保持してcurrent pointer を新エントリのノードに設定する。ＬビットとＲビットのいずれか、あるいは、両方がＯＮでない場合には、単に、current pointer を新エントリのノードに設定する。
【００８８】
次に、IF文で、エントリがまだ存在するか否かを判断する。エントリがある場合には、while 文の先頭に戻って、処理を繰り返す。エントリがない場合には、current pointer を一階層上位のノードに設定したのち、IF文で、current pointer がnullになったか、すなわち、一階層上位のノードが存在するか否かを判断し、存在する場合には、while文の先頭に戻って処理を繰り返す。一階層上位のノードが存在しない場合には、全てのノードのサーチが終了したとして、while 文を抜け、処理を終了する。
【００８９】
上記実施形態によれば、ルーティングプロトコルのメカニズムを利用し、効率的にネットワークトポロジーマップを描くことができる。
次に、境界装置判別方式について説明する。
【００９０】
上記実施形態で得られたルーティングツリーにおいて、どの装置がコネクション機能網境界装置であるか判定する。前述したように、トラフィック・エンジニアリングを行うために、任意のコネクション機能網境界装置は、他の全ての境界装置のアドレスを知る必要がある。あるコネクション機能網境界装置が、上記実施形態で得られたルーティングツリーを元に以下のルールに従って、境界装置を発見する。
・ツリー中で、コネクション機能網装置識別子ビット（Ｌビット）が立っている（ＯＮになっている）装置が連続しているツリー部をコネクション機能網とする。
・ツリー中のある位置で、注目しているノードにつながる枝の中で一つでもコネクション機能網装置識別子ビット（Ｌビット）がＯＦＦになっているとき、該位置の装置を境界装置として登録する。
【００９１】
これらのルールの元で、各境界装置は、コネクション機能網境界装置リストを得る。
図１５は、コネクション機能網境界装置リストの生成処理を示す疑似コードである。
【００９２】
また、図１６は、コネクション機能網境界装置リストの生成処理の概念を説明する図である。
更に、図１７は、ＬＳＲ１の保持する境界装置エントリの例を示す図である。
【００９３】
ここでは、コネクション機能網境界装置ＬＳＲ１が有するリスト作成を行う。上記実施形態で作られたツリーをＬＳＲ１は持っているとする。これを元に、図１５のアルゴリズムによって、図１６の（１）〜（３）のシーケンスでリストを得る。ツリー中で、ある位置の下につながる枝をchild と呼び、上につながる幹をparentと呼ぶ。どの位置においても、parentは一つ存在し、child は０から複数存在する。
【００９４】
図１６の例では、このアルゴリズムは以下のように動作する。
（１）ＬＳＲ１からスタートし、下方向に探索する。ＬＳＲ１−ＬＳＲ２−ＬＳＲ３と移動していき、ＬビットがＯＦＦになっているＲ１にたどり着く。この時点で、Ｒ１のparent、つまりＬＳＲ３がコネクション機能網境界装置であることが分かる。ＬＳＲ３を境界装置エントリに追加する。
（２）ＬＳＲ３−ＬＳＲ２の幹方向に戻り、まだ探索していない右部分であるＬＳＲ２−ＬＳＲ４方向に移動。ＬビットがＯＦＦであるＨ２にたどり着く。この時点で、Ｈ２のparentであるＬＳＲ４がコネクション機能網境界装置であることがわかる。ＬＳＲ４を境界装置エントリに追加する。
（３）Ｈ２からＬＳＲ４−ＬＳＲ２−ＬＳＲ１と幹方向に戻る。これで全ての装置を探索したことになるので終了。
【００９５】
最終的にＬＳＲ１の保持する境界装置エントリとして図１７のリストを得る。
図１５の疑似コードを説明する。
まず、初期化において、各位置のノードを探索したか否かを示す識別用のフラグtraced[]（探索済み＝１、未探索＝０）を用意し、ツリー中の現在位置current pointer をＬＳＲ１に設定し、境界装置エントリの配列edge entry[] を設け、合計境界装置エントリ数を表す変数edge entry numberを設ける。
【００９６】
次に、探索ルーチンを開始する。まず、while 文内で、最初に、current pointer が指す装置のchild の情報を見る。そして、IF文で、現在のchild が探索済みか否かを判断し、探索済みでない場合には、current pointer をchild に設定して、child のtracedフラグを探索済みにする。現在のchild が探索済みである場合には、次のELSE  IF文で、全child が探索済みか否かを判断する。全child が探索済みの場合には、current pointer をparentに設定し、次のIF文で、parentがnullか否かを判断する。parentがnullの場合には、全探索が終了したとして、while 文を抜けて、処理を終了する。parentがnullでない場合には、while 文の先頭に戻って、処理を繰り返す。
【００９７】
ここで、全child が探索済みでなかった場合には、IF文で、current pointer の示すＬビットが０か否かを判断する。０でない場合には、while 文の先頭に戻って処理を繰り返す。Ｌビットが０であった場合には、current pointer で示されるノードのparentが境界装置であることを意味するので、edge entry の配列であって、edge entry numberで示される番号の配列にparentの装置を示す識別子を設定する。そして、edge entry numberを１だけ増加し、current pointer をparentに設定して、while 文の先頭に戻って処理を繰り返す。
【００９８】
図１８は、本実施形態のＯＳＰＦと従来のＯＳＰＦの機能の違いを説明する図である。
図１８（ａ）は、従来のＯＳＰＦに従ったルーティングツリーのイメージと各ルータが有するルーティングテーブルのエントリ内容を示す図である。
【００９９】
また、図１８（ｂ）は、本実施形態におけるルーティングツリーのイメージと各ルータが有するルーティングテーブルのエントリ内容を示す図である。
同図（ａ）と（ｂ）を比較して分かるように、本実施形態においては、前述の実施形態に従って、境界装置のＩＰアドレスが分かるので、これをdestination  addressと、ＯＩと共に対応させて格納している。従って、ツリーの図に示されるように、どのルータが境界装置となり、どの範囲がコネクション機能網に含まれているかを知ることが出来る。
【０１００】
次に、境界装置における外部網情報作成方式と、出口境界装置−境界装置外網情報作成方式について説明する。
コネクション機能網装置の識別子情報を追加したルーティング・ツリーから、コネクション機能網出口境界装置を識別し、その出口境界装置より先のＩＰ網に存在する装置のリストを把握し、出口境界装置−ＦＥＣ対応表を確立する。
【０１０１】
上記実施形態で、得られた境界装置エントリの境界装置に対して、その先につながるネットワークの情報を対応させることで、ＭＰＬＳのトラフィック・エンジニアリングに必要な完全な情報が得られることになる。特に、トラフィック・エンジニアリングの負荷分散の観点からは、入り口境界装置はＩＰパケットのヘッダ中のdestination に対応する出口境界装置情報を自動で得ることが出来れば、完全に自律的なネットワークの負荷分散が実現できる。
【０１０２】
図１９は、境界装置に接続するネットワークのエントリを作成する処理の疑似コードを示す図である。
また、図２０は、境界装置における外部網情報の作成処理の概念を示す図である。
【０１０３】
更に、図２１には、ＬＳＲ１の保持する境界装置／外部網情報エントリの例を示す図である。
図２０の例では、このアルゴリズムは以下のように動作する。
（１）、（２）、（３）ＬＳＲ３からスタートし、下方向に探索する。Ｒ１−Ｈ４−Ｒ１−Ｈ３と探索する。Ｒ１、Ｈ４、Ｈ３は全てＬビットがＯＦＦなので、ＬＳＲ３につながる装置として登録する。
（４）、（５）同様に、ＬＳＲ４につながる装置Ｈ４のリストを登録する。
【０１０４】
最終的にＬＳＲ１の保持する境界装置エントリとして図２１のリストを得る。
図１９の疑似コードを説明する。
まず、初期化において、各位置のノードを探索したか否かのフラグを設定するtraced[]。このフラグは、探索済みの時、１に設定され、未探索の場合、０に設定される。また、ポインタcurrent Pointer をＬＳＲ１に設定する（ここでの実施形態は、ＬＳＲ１をルートとして説明している）。また、境界装置エントリを格納する配列edge entry[] を設ける。更に、合計境界装置エントリ数を格納する変数edge entry numberを用意する。
【０１０５】
探索ルーチンでは、while 文内で、まず、current pointer が示す装置のchild を見る。IF文で、child が探索済みか否かを判断する。探索済みでない場合には、current pointer をchild に設定し（未探索のchild に移動）、child の探索済みフラグを１に設定する。もし、child が探索済みであった場合には、ELSE  IF文で、全child が探索済みか否かを判断する。探索済みでない場合には、while 文の先頭に戻って処理を繰り返す。全child が探索済みであった場合には、current pointer をparentに設定し、parentがnullか否かを判断する。parentがnullの場合には、全探索が終了したとして、while 文を抜けて、処理を終了する。parentがnullでない場合には、while 文の先頭に戻って処理を繰り返す。
【０１０６】
child が未探索であった場合には、IF文でcurrent pointer の示すＬビットが０か否かを判断する。０であった場合には、edge entry number番目のedge entry 配列にparent装置を設定し、edge entry numberを１だけ増加する。次に、IF文でcurrent pointer の示すＬビットが０でないか否かを判断する。０でない場合には、current pointer の示すＩＰアドレスをedge entry[edge entry number] に対応させて、エントリの追加を行う。そして、while 文の先頭に戻って処理を繰り返す。
【０１０７】
次に、コネクションプロトコルによるコネクション機能網出口境界装置ルーティング情報伝達方式を説明する。
上記実施形態では、網リンク情報を、保持するルーティングプロトコルによって配布することを前提に話を進めた。ここでは、各装置が網全体のリンク情報をえることができないとき、どのようにして、上記実施形態と同様のエントリを作成するかについて述べる。
【０１０８】
まず、任意のコネクション機能網境界装置が他のコネクション機能網境界装置のエントリを持っているとする。この情報を元に、コネクションプロトコルは、入り口コネクション機能網境界装置から出口コネクション機能網境界装置間で動作することができる。コネクションプロトコルにより、入り口から出口の間に、コネクションを確立する際に、出口境界装置のルーティングプロトコルが保持しているルーティングテーブルをコネクションプロトコルにpiggybacking（ついでに載せる）する形で、出口から入り口に伝達する。これにより、境界装置／外部網情報エントリを構成することができる。
【０１０９】
コネクションプロトコルにＲＳＶＰを使用した場合の例を示す。
図２２は、本実施形態において新たに定義されるオブジェクトを説明する図である。
【０１１０】
ここでは、routing table request オブジェクトと、routing table オブジェクトを定義する。
routing table request オブジェクトは、PATHメッセージ（ＲＳＶＰ（Resource  Reservation  Setup  Protocol）の送信用メッセージ）に入るオブジェクトである。送信元（入り口境界装置）は、出口境界装置のルーティングテーブルエントリを得たい場合、routing table request オブジェクトをPATHメッセージに含めるようにする。
【０１１１】
routing table オブジェクトは、出口境界装置がrouting table request オブジェクトを含むPATHメッセージを受け取ったとき、routing table オブジェクトを含めたＲＥＳＶメッセージ（ＲＳＶＰの応答用メッセージ）をrouting table request の送信元に返す。このとき、routing table オブジェクト中に、ルーティングテーブルのファイルをコピーして転送する。
【０１１２】
図２３は、本実施形態のプロトコルシーケンスを示す図である。
すなわち、ＬＳＲ１がＬＳＲ４のルーティングテーブルを欲しい場合、ＬＳＲ１は、ＬＳＲ４に向けて、コネクションプロトコルを用いて、上記PATHメッセージをＬＳＲ２を介して送信する。ＬＳＲ４では、PATHメッセージを受け取ると、自装置のルーティングテーブルをコピーしてＲＥＳＶメッセージに含め、ＬＳＲ２を介してＬＳＲ１に送信する。このようにして、ＬＳＲ１は、ＬＳＲ４のルーティングテーブルを取得することが出来る。
【０１１３】
本方式は、コネクションプロトコルにオブジェクトを追加する必要が出てくる。前述の実施形態の様に付加的ルーティング情報をルーティングプロトコルを利用するか、コネクションプロトコルを使用するかの違いであるが、実装上は容易にできる方を採用すればよい。リンク情報を保持しないルーティングプロトコルとしてＲＩＰ（Routing  Information  Protocol）の実装が考えられる。本方式はＲＩＰとＲＳＶＰ（Resource  Reservation  Setup  Protocol）を使ったＭＰＬＳネットワークに適用できる。
【０１１４】
次に、出口境界装置ルーティング情報を用いる際の出口境界装置−境界装置外網情報の最適化方式について述べる。
また、図２４は、ルーティング情報の最適化を説明する図である。
【０１１５】
ルーティングプロトコルが網リンク情報を保持せずルーティングテーブルのみを持つ場合において、コネクションプロトコルを利用して、出口境界装置の保持するルーティングテーブルを入り口境界装置に伝達し、その情報を元にlabel-FEC テーブルを生成する。
【０１１６】
また、図２２、２３の方式は、ネットワークリンク情報から計算されたルーティングテーブルを入り口境界装置が集める方式であるため、集めたルーティング情報が入り口境界装置にとって必ずしも最適なルート情報であるとは限らない。そこで、ルート最適化を図る手段が必要となる。
【０１１７】
入り口境界装置は、複数の出口境界装置からルーティングテーブルを得る。それらのテーブルを比較すると、入り口境界装置から見た、あるdestination （宛先）に対して、複数の境界装置に通るルートが存在する可能性がある。そのとき以下のアルゴリズムに従い、最適化を図る。
１）ＬＳＲｉを通るルートのコストを算出。
cost(i) ＝（入り口境界装置−＞ＬＳＲｉのコスト）＋（ＬＳＲｉ−＞destination のコスト）
２）cost(i) （i=存在する全てのルート）の最小のものを見つける。
min[cost(i) （i=存在する全てのるーと）]
３）見つけた最小コストを持つルートをlabel-FEC テーブルエントリに採用する。
【０１１８】
図２４のネットワークを考える。端末Ｈ１から端末Ｈ３へのルートは、ＬＳＲ１−ＬＳＲ２−ＬＳＲ３経由とＬＳＲ１−ＬＳＲ２−ＬＳＲ４経由の２ルートがある。ＬＳＲ１は、出口境界装置であるＬＳＲ３とＬＳＲ４からルーティングテーブルを得るが、両方のルーティングテーブルには、端末Ｈ３のエントリが存在する。そこで、最適化アルゴリズムを適用して、ＬＳＲ１−ＬＳＲ２−ＬＳＲ３−Ｒ１−Ｈ３ルートとＬＳＲ１−ＬＳＲ２−ＬＳＲ４−Ｒ１−Ｈ３ルートの両方を比較し、コストの小さい方を採用する。
【０１１９】
ＲＩＰのようなリンク情報を保持しないルーティングプロトコルの場合、出口境界装置のルーティング情報を得るには、ルーティングテーブルを手に入れる手段をとるしかない。ただ、入り口境界装置は直接ネットワークのリンク情報を得るわけではないので、本当に最適化されたルート情報を得ているかは分からない。そこで、上記最適化方式をとることで、問題を回避出来る。
【０１２０】
なお、上記したＦＥＣとは、Forward  Equivalent  Classの略称である。ＦＥＣは、どのフロー（ユーザが生成するデータストリームのこと）が、ＭＰＬＳネットワークの入り口で、どのコネクションに対応するかを表現するものである。普通ＦＥＣは、ＦＥＣテーブルとして境界装置で保持される。フローというのは、ユーザのパケットストリームを表現する最小単位であるのに対し、ＭＰＬＳネットワークでは、ネットワーク内に流れるデータを扱う際の最小単位をＦＥＣ表現する。ＦＥＣの粒度（細かさ）は、最小ではユーザフローで考えることができ、最大で出口境界装置（つまり、ある出口境界装置行きのデータは全部一つのＦＥＣ）とすることができる。
【０１２１】
また、上記コストについては、従来、コスト計算はルーティングプロトコル内に実装されているのが通常である。アルゴリズムとしては、いくつか方式があるが、ＯＳＰＦプロトコルの場合はdijkstraアルゴリズムというよく知られたアルゴリズムが使われる。本発明においても、このアルゴリズムまたは、これに準ずるものを利用することを想定している。
【０１２２】
図２５は、入り口境界装置が保持するlabel −FEC テーブルの例を示す図である。
入り口境界装置が保持するlabel-FEC テーブルは図２５のような構成を取る。また、このテーブルは、出口境界装置の数だけ複数存在する。
【０１２３】
ＦＥＣは、基本的に外部から設定される。手動で書かれる場合もあれば、ある制御のために、入り口境界装置内にあるアプリケーションプログラムが自動でダイナミックにＦＥＣを書き換えることがある。ＦＥＣは、一番細かく指定するときで、d.a.、s.a.、d.p.、s.p.、proto の五つを指定する。例として、よく使われるパターンは、d.a.、d.p.の組を指定し、他は無指定である。
【０１２４】
Label は、ＭＰＬＳネットワーク内にコネクションを確立したものが、個々のエントリとされる。このテーブルを使うことで、入り口境界装置で各フローをＭＰＬＳネットワークの大きなトラフィックのコネクションに対応付ける。
【０１２５】
テーブル生成シーケンスは、
１．初期設定されているＦＥＣテーブルをファイルから読み込む。このときＦＥＣデータは、出口境界装置毎に初期設定が置かれている。これにより、同図のテーブルの左側が生成される。
２．入り口境界装置からＲＳＶＰでコネクションが確立された時点（最初は、システム起動時）で、テーブルの右側にlabel が一段目から書き込まれていく。
【０１２６】
図２６は、本発明の実施形態をソフトウェアで実現する場合に必要とされるルータのハードウェア構成を示す図である。
ルータ２０は、ＣＰＵ２５、メモリ２４、記憶装置２６、入出力装置２７、及び受信インターフェース２１と送信インターフェース２３を複数ずつ備える。
【０１２７】
ＣＰＵ２５は、複数ある受信インターフェース２１で受信されたパケットをバス又はスイッチ２２を介してメモリ２４に格納する。ＣＰＵ２５は、入出力装置２７のフロッピーディスクＦＤＤやＣＤ−ＲＯＭ、メモリカードなどから入力され、ハードディスクやフラッシュメモリなどの記憶装置に格納されているプログラムをメモリ２４に展開し、実行する。ＣＰＵ２５は、このプログラムを実行することによって、複数の受信インターフェース２１の１つから受信されたパケットを、どの送信インターフェース２３に出力するかを決定し、メモリ２４から読み出して、バス又はスイッチ２２を介して、送信インターフェース２３に送る。送信インターフェース２３は、メモリ２４から送られてきたパケットを回線に送出する。
【０１２８】
以上の説明においてＣＰＵ２５がメモリ２４に読み込んだプログラムは、ルーティングを行うためのプログラムであるが、本発明の上記実施形態を実現するプログラムも同時に読み込む。従って、ＯＳＰＦパケットのオプションフィールドにＬビットやＲビットを設定する処理を行う。また、ルーティングツリー作成処理も記憶装置２６から読み込んだプログラムに基づいて行うことが可能である。
【０１２９】
このように、本発明の実施形態を実現するプログラムは、ＦＤＤやＣＤ−ＲＯＭ、メモリカードなどによって各ルータ２０に配布され、これらに格納されているプログラムを記憶装置にインストールすることによって、ルータに本発明の実施形態の機能を持たせることが出来る。
【０１３０】
あるいは、従来のルータに対し、入出力装置２７からアップデート用のプログラムをインストールし、本発明の実施形態を実現するように機能拡張を行うことが出来る。
【０１３１】
【発明の効果】
ネットワークにおいて、自動負荷分散に必要なコネクション機能網とコネクションレス網との間のマッピングを自動的に行うことができる。
【図面の簡単な説明】
【図１】本実施形態で説明する網の基本構成を示す図である。
【図２】ＭＰＬＳにおけるコネクションの確立手順を示す図である。
【図３】ＯＳＰＦの動作手順を示す図である。
【図４】ルーティングプロトコルによるリンク情報配布の様子を示した図である。
【図５】ＯＳＰＦにおける広報情報フィールドのうちのオプションフィールドを示した図である。
【図６】コネクション機能網装置識別子／クライアント・サーバモデルによるリンク情報の伝達方式を説明する図である。
【図７】任意の装置をサーバとし、各コネクション機能網装置をＳＮＭＰクライアントとした構成を示す図である。
【図８】実装コネクションプロトコル識別子のルーティングプロトコルによる伝達方式を説明する図である。
【図９】ルーティングプロトコルによるコネクションプロトコル情報の配布の様子を示す図である。
【図１０】実装コネクションプロトコル識別子のクライアント・サーバモデルによる伝達方式を説明する図である。
【図１１】サーバを保有するネットワークのどの装置のコネクション機能網装置であるか否か、及び、実装されているコネクションプロトコルを登録するテーブルである。
【図１２】コネクション機能網装置の本実施形態に関連する機能ブロックを示す図である。
【図１３】ルーティングツリーのイメージを示す図である。
【図１４】ルーティングツリーを作成するための処理を示す疑似コードを示す。
【図１５】コネクション機能網境界装置リストの生成処理を示す疑似コードである。
【図１６】コネクション機能網境界装置リストの生成処理の概念を説明する図である。
【図１７】ＬＳＲ１の保持する境界装置エントリの例を示す図である。
【図１８】本実施形態のＯＳＰＦと従来のＯＳＰＦの機能の違いを説明する図である。
【図１９】境界装置に接続するネットワークのエントリを作成する処理の疑似コードを示す図である。
【図２０】境界装置における外部網情報の作成処理の概念を示す図である。
【図２１】ＬＳＲ１の保持する境界装置／外部網情報エントリの例を示す図である。
【図２２】本実施形態において新たに定義されるオブジェクトを説明する図である。
【図２３】本実施形態のプロトコルシーケンスを示す図である。
【図２４】ルーティング情報の最適化を説明する図である。
【図２５】入り口境界装置が保持するlabel−FECテーブルの例を示す図である。
【図２６】本発明の実施形態をソフトウェアで実現する場合に必要とされるルータのハードウェア構成を示す図である。
【符号の説明】
１０      ルーティングプログラム
１１      パケット受信処理部
１２      受信データのデータベース
１３      ルーティング処理部
１４      ツリー生成機能
１５      トポロジーデータベース
１６      トポロジー判定処理部
１７      パケット送信処理部
２０      ルータ
２１      受信インターフェース
２２      バス又はスイッチ
２３      送信インターフェース
２４      メモリ
２５      ＣＰＵ
２６      記憶装置
２７      入出力装置
【図１】
0003790658.tif 000004
【図２】
0003790658.tif 000005
【図３】
0003790658.tif 000006
【図４】
0003790658.tif 000007
【図５】
0003790658.tif 000008
【図６】
0003790658.tif 000009
【図７】
0003790658.tif 000010
【図８】
0003790658.tif 000011
【図９】
0003790658.tif 000012
【図１０】
0003790658.tif 000013
【図１１】
0003790658.tif 000014
【図１２】
0003790658.tif 000015
【図１３】
0003790658.tif 000016
【図１４】
0003790658.tif 000017
【図１５】
0003790658.tif 000018
【図１６】
0003790658.tif 000019
【図１７】
0003790658.tif 000020
【図１８】
0003790658.tif 000021
【図１９】
0003790658.tif 000022
【図２０】
0003790658.tif 000023
【図２１】
0003790658.tif 000024
【図２２】
0003790658.tif 000025
【図２３】
0003790658.tif 000026
【図２４】
0003790658.tif 000027
【図２５】
0003790658.tif 000028
【図２６】
0003790658.tif 000029