(57)【要約】  複数の階層型移動ネットワークにおける移動エンティティ間の自律モードルーティングを可能にするための方法は、ルート移動エンティティ・アドレスを宣言する段階（３０５）と、宣言する段階に応じて、複数の階層型移動ネットワークを含む複数の移動エンティティの少なくとも一部における各移動エンティティからルーティング情報を含む登録要求を受信する段階（３１０）であって、登録要求の内の少なくとも１つが、自律モード中に受信される段階（３１０）と、登録要求からのルーティング情報を用いて、複数の階層型移動ネットワーク内においてルーティングを可能にするためのルート移動エンティティ結合キャッシュを生成する段階（３１５）と、を含む。
2009514272.tif 000002
【特許請求の範囲】
【請求項１】
ルーティングを可能にするための方法であって、
ルート移動エンティティ・アドレスを宣言する段階と、
前記宣言する段階に応じて、複数の階層型移動ネットワークに含まれる複数の移動エンティティのうち少なくとも一部の各移動エンティティからルーティング情報を含む登録要求を受信する段階であって、前記登録要求の内の少なくとも１つは、自律モード中に受信される、前記登録情報を受信する段階と、
前記複数の階層型移動ネットワーク内においてルーティングを可能にするために、前記登録要求からの前記ルーティング情報を用いてルート移動エンティティ結合キャッシュを生成する段階と、
を備える、方法。
【請求項２】
請求項１に記載の方法であって、更に、
宛先アドレスを含むパケットを受信する段階と、
前記結合キャッシュを用いて、前記宛先アドレスへの前記複数の階層型移動ネットワーク内における経路を決定する段階と、
前記決定された経路を用いて、前記宛先アドレスに前記パケットをルーティングする段階と、
を備える、方法。
【請求項３】
請求項２に記載の方法であって、前記パケットは、前記複数の階層型移動ネットワークに含まれる移動エンティティによってサービスが提供されるノードによって生成され、前記方法には、更に、
前記結合キャッシュを用いて、前記ノードにサービスを提供する前記移動エンティティから前記宛先アドレスへの前記複数の階層型移動ネットワーク内における第２経路を決定する段階と、
多重カプセル及びルーティングヘッダを含む単一カプセルの内の１つを用いて、前記ノードにサービス提供する前記移動エンティティによって前記ノードから前記宛先アドレスへの後続のパケットのルーティングを可能にするために、前記ノードにサービスを提供する前記移動エンティティに前記決定された第２経路を転送する段階と、
を備える、方法。
【請求項４】
請求項２に記載の方法であって、前記パケットは、多重カプセル及びルーティングヘッダを含む単一カプセルの内の１つを用いてルーティングされる、方法。
【請求項５】
請求項２に記載の方法であって、前記経路は、所定の方法に基づき決定された最適経路である、方法。
【請求項６】
請求項５に記載の方法であって、
前記パケットは、前記複数の階層型移動ネットワークに含まれる移動エンティティによってサービスが提供されるノードによって生成され、
前記結合キャッシュは、前記複数の階層型移動ネットワークに含まれる各移動エンティティに対応する入力項目を含み、各入力項目は、前記対応する登録要求において受信される対応する移動エンティティ内部インターフェイスアドレス及び対応する移動エンティティ気付アドレスを含み、前記所定の方法は、
前記結合キャッシュを繰り返し解析して、前記ノードにサービスを提供する前記移動エンティティからルート移動エンティティへの第１経路を形成する内部インターフェイスアドレスのリストを検索する段階であって、前記第１経路の第１内部インターフェイスは、前記ノードにサービスを提供する前記移動エンティティに対応する内部インターフェイスアドレスを含む、前記解析及び検索する段階と、
前記結合キャッシュを繰り返し解析して、前記ルート移動エンティティから前記宛先アドレスへの第２経路を形成する気付アドレスのリストを検索する段階と、
前記第１及び第２経路に基づき最適経路を決定する段階と、
を備える、方法。
【請求項７】
請求項６に記載の方法であって、前記第１及び第２経路に基づいて最適経路を決定する段階は、更に、
前記第１経路が、前記複数の階層型移動ネットワークに含まれる交差移動エンティティに対応する内部インターフェイスアドレスで終端し、前記第２経路が、前記交差移動エンティティに対応する第１気付アドレスで始まるように、前記第１及び第２経路を打ち切る段階と、
前記第２経路から前記第１気付アドレスを除去する段階と、
前記第１経路から前記第１内部インターフェイスアドレスを除去する段階と、
前記最適経路を形成するために、前記第２経路を前記第１経路に追加する段階と、
を備える、方法。
【請求項８】
請求項７に記載の方法であって、更に、前記ノードから前記宛先アドレスへの後続のパケットの自律モードルーティングを可能にするために、前記最適経路を記憶する段階を備える、方法。
【請求項９】
請求項１に記載の方法であって、各登録要求を含む前記ルーティング情報は、少なくとも気付アドレスと、対応する移動エンティティ用の移動ネットワークプレフィクス及びホームアドレスの内の１つとを含む、方法。
【請求項１０】
請求項１に記載の方法であって、ルート移動エンティティ・アドレスを宣言する前記段階は、少なくともルート移動ルータアドレスを含むルート移動ルータ宣言（ＲＭＲＡ）の選択肢を含むルータ宣言を伝達する段階を含む、方法。
【請求項１１】
請求項１０に記載の方法であって、前記ＲＭＲＡは更に、次のホップ移動ルータアドレスを含む、方法。
【請求項１２】
請求項１０に記載の方法であって、前記ルート移動ルータアドレスは、
内部インターフェイスに対応するアドレス、
ルート移動ルータホームアドレス、
ルート移動ルータ気付アドレス、
の１つを備える、方法。
【請求項１３】
請求項１に記載の方法であって、更に、
宛先アドレスを含むパケットを受信する段階であって、前記パケットは、前記複数の階層型移動ネットワークに含まれる移動エンティティによってサービスが提供されるノードによって生成される、前記受信する段階と、
前記結合キャッシュを用いて前記宛先アドレスへの経路を決定できない場合、前記パケットを廃棄する段階と、前記ノードにサービスを提供する前記移動エンティティによる前記パケットの他のルーティングを可能にするために、前記ノードにサービスを提供する前記移動エンティティに、宛先到達不可通知を伝達する段階との内の少なくとも１つを実施する段階と、
を備える、方法。
【請求項１４】
請求項１に記載の方法であって、更に、
前記結合キャッシュを用いる前記移動エンティティの少なくとも一部によって自律モードルーティングを可能にするために、前記複数の階層型移動ネットワークに含まれる前記移動エンティティの少なくとも一部に前記結合キャッシュを伝達する段階を備える、方法。
【請求項１５】
請求項１に記載の方法であって、更に、
前記複数の階層型移動ネットワークを含む移動エンティティから要求を受信して、前記要求側移動エンティティから宛先アドレスへの経路を決定する段階と、
前記結合キャッシュを用いて、前記要求側移動エンティティから前記宛先アドレスへの経路を決定する段階と、
多重カプセル及びルーティングヘッダを含む単一カプセルの内の１つを用いて、前記要求側移動エンティティによる前記宛先アドレスへのパケットの自律モードルーティングを可能にするために、前記要求側移動エンティティに前記決定された経路を伝達する段階と、
を備える、方法。
【請求項１６】
装置であって、
実行可能なソフトウェアを記憶するメモリと、
前記メモリに結合され、前記ソフトウェアを実行するプロセッサと、を備え、前記プロセッサは、
ルート移動エンティティ・アドレスを宣言する段階と、
前記宣言する段階に応じて、複数の階層型移動ネットワークに含まれる複数の移動エンティティのうち少なくとも一部の各移動エンティティからルーティング情報を含む登録要求を受信する段階であって、前記登録要求の内の少なくとも１つは、自律モード中に受信される、前記登録情報を受信する段階と、
前記複数の階層型移動ネットワーク内においてルーティングを可能にするために、前記登録要求からの前記ルーティング情報を用いてルート移動エンティティ結合キャッシュを生成する段階と、
を実施する、装置。
【請求項１７】
自律モードルーティングを可能にするための方法であって、
複数の階層型移動ネットワーク内においてルート移動エンティティを発見する段階と、
前記ルート移動エンティティがルート移動エンティティ結合キャッシュを生成できるようにするために、ルーティング情報を含む登録要求を前記ルート移動エンティティに伝達する段階と、
前記結合キャッシュを用いて、前記ルート移動エンティティによる前記宛先アドレスへの前記パケットの自律モードルーティングを可能にするために、宛先アドレスを含むパケットを前記ルート移動エンティティにルーティングする段階と、
を備える、方法。
【請求項１８】
請求項１７に記載の方法であって、更に、
前記ルート移動エンティティに対応する宛先アドレスを含み、更に、下位移動エンティティに対応するルーティング情報を含む登録要求を受信する段階と、
前記下位移動エンティティに対応する前記ルーティング情報を抽出する段階と、
前記受信された登録要求を前記ルート移動エンティティにルーティングする段階と、
前記複数の階層型移動ネットワーク内において自律モードルーティングを可能にするために、第２結合キャッシュを生成する段階と、
宛先アドレスを含むパケットを受信する段階と、
前記第２結合キャッシュを繰り返し解析して、下流経路を前記宛先アドレスに対して決定しできるかどうか判断する段階と、
前記宛先アドレスへの前記下流経路を決定できない場合、前記ルート移動エンティティへの経路上で前記パケットを、次のホップ移動エンティティにルーティングする段階と、
前記宛先アドレスへの前記下流経路を決定できる場合、次の段階、
多重カプセル及びルーティングヘッダを含む単一カプセルの内の１つを用いて、前記下流経路に沿って、前記パケットを前記宛先アドレスにルーティングする段階、
前記下流経路において、前記パケットを第１ホップ移動エンティティにルーティングする段階、
の内の１つを実施する段階と、
を備える、方法。
【請求項１９】
請求項１７に記載の方法であって、前記前記ルート移動エンティティを発見する段階は、
少なくともルート移動エンティティ・アドレスを含むルータ宣言を受信する段階と、
前記ルート移動エンティティ・アドレスを抽出する段階と、
各ルート移動エンティティに対応する入力項目を含む複数のルート移動エンティティに対応するルート移動エンティティリストを生成する段階であって、前記入力項目は、少なくとも前記ルート移動エンティティ・アドレスを含む、前記生成する段階と、
を備える、方法。
【請求項２０】
請求項１９に記載の方法であって、前記リストは、前記複数のルート移動エンティティの各々に対応する入力項目を含み、前記方法は、更に、前記複数のルート移動エンティティの少なくとも一部のために、
少なくとも１つの到達可能プレフィクスを受信する段階であって、各到達可能プレフィクスは、前記複数の階層型移動ネットワーク内における少なくとも１つの他の移動エンティティに対応する、前記受信する段階と、
前記複数の階層型移動ネットワーク内においてパケットをルーティングするための前記複数のルート移動エンティティの内の１つの選択を可能にするために、前記入力項目を修正して前記少なくとも１つの到達可能プレフィクスを含むようにする段階と、
を備える、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、通信ネットワークに関し、特に、最小信号伝達オーバーヘッドで、複数の階層型移動ネットワーク用の自律モードのサポートを可能にする集中型の手法に関する。
【背景技術】
【０００２】
移動体インターネットプロトコル（ＩＰ）は、移動ホストにＩＰセッション連続性を提供して、ホスト移動性サポートを可能にする。しかしながら、ネットワーク移動性サポートは、ネットワーク全体が、そのインターネット（コアネットワーク）への接続ポイントを変える移動ネットワークに必要である。移動ネットワークは、一般的に、一組のノード（本明細書では、移動ネットワークノード（ＭＮＮ）とも称する）と定義することができ、移動ルータ（ＭＲ）に接続された１つ又は複数のＩＰサブネットを含み、また、インターネットの他の部分に対して一団として移動可能である。
【０００３】
移動ネットワークが、１つのＩＰサブネットから他のＩＰサブネットへ移動する際、ネットワーク移動性（ＮＥＭＯ）基本サポートプロトコルは、移動ネットワークにおける任意ノードのセッションの連続性の維持を支援する。例えば、移動ネットワークの一部を形成するノードは、自身が属している移動ネットワークが動いている時、接続が途切れることは無い。そのような移動ネットワークは、直接ＭＲを介して又は他の移動ネットワークを介してインターネットの他の部分に接続するが、この場合、それは、階層型移動ネットワークと称される。ＮＥＭＯプロトコルは、ＭＲとＭＲに関連するホームエージェント（ＨＡ）との間における双方向のトンネルの確立に依拠し、ＭＲの移動中に、ＭＲ以降のセッションの連続性をＭＮＮに提供する。
【０００４】
ＭＲが訪問リンクに接続する場合、ＭＲは、気付アドレス（ＣｏＡ）と呼ばれるトポロジーが正しいアドレスを得て、ＭＲに関連するＨＡにＣｏＡを登録する。ＭＲは、トンネルを介して発信ＩＰパケットをそのホームネットワーク側に転送する。同様に、ＭＲのホームリンクに到着する任意のパケットは、パケットの宛先アドレスが移動ネットワークプレフィクス（ＭＮＰ）に合致する場合、ＨＡによって傍受され、トンネルを介してＭＲのＣｏＡ側に転送される。ＭＮＰは、インターネットトポロジ内における移動ネットワークを識別するＩＰアドレスのある数の最初のビットから成るビット文字列を含む。一般的に、移動ネットワークに属するノードは、同じ移動ネットワークプレフィクスを共有する。単一の移動ＩＰサブネットの場合、ＭＮＰは、サブネットのネットワーク識別子である。パケットルーティングは、ＭＲのホームアドレスに加えて、ＭＲのＨＡを拡張して、ＭＮＰ全体に対する転送をサポートすることによって達成される。
【０００５】
パケットが従う回り道の経路は、移動ネットワークが階層化されると、更に複雑になる。移動ネットワークの階層化は、移動ネットワークが他の移動ネットワークに接続する場合、例えば、（例えば、移動ルータ−ＭＲ２を介して接続された）移動ネットワーク２が、（移動ルータ−ＭＲ１を介して接続された）移動ネットワーク１に接続する場合に発生する。そのような場合には、ＭＲ２下における移動ネットワークノードＭＮＮ２からのパケットは、更に複雑な回り道の経路において、対応するノード（ＣＮ）（主ネットワークインフラ上にあって、ＭＲ以降の移動ネットワークノードと通信を行うノード）に進む。たどる経路は、ＭＮＮ２からＭＲ２へ、そして、ＭＲ１及びＭＲ１のホームリンクへ、そして、ＭＲ２のホームリンクへ、最後に、主ネットワークインフラ上のＣＮに至る。階層化のレベルが増加するにつれて、経路の複雑さは、大幅に増加する。
【０００６】
ＭＮＮ２及びＣＮが、同じ複数の階層型移動ネットワークの一部である場合でも、（例えば、２つの移動ネットワークが、その面に配備された同じネットワークに接続される場合）、パケットのルーティング経路は、依然として回り道のままである。これによって、同じ複数の階層型移動ネットワーク下において、そのような（隣り合った）移動ノード間に最適以下の経路が導入される。更に、パケットは、ホームリンクが配置された主ネットワークインフラ中を進まねばならないことから、複数の階層型移動ネットワークは、常に主ネットワークインフラに接続されねばならない。これによって、複数の階層型移動ネットワークが、主ネットワークインフラとのその接続を緩めると、複数の階層型移動ネットワーク下の２つの移動装置は、互いに通信できないため、他の重大な問題が起こる。ＮＥＭＯプロトコルの欠陥は、ルートＭＲとインターネットとの間の接続が切断された場合、２つの通信ノード間の接続を提供できないことである。
【０００７】
複数の階層型移動ネットワーク内において通信を処理する様々な方法があるが、それらのいずれも完全な解決策を提供しない。これらの方法は、３つの分類に大別できる。第１の分類は、主ネットワークインフラにおいて、最適化された送信を提供するが、自律モードをサポートしない。自律モードは、移動ネットワーク（それぞれ、階層型移動ネットワークの集合体）の能力を提供して、（１）この移動ネットワーク内の任意の２つのノード間（それぞれ、この階層型移動ネットワークの集合体内）における任意の進行中の通信を維持し、（２）移動ルータ（それぞれ、階層型移動ネットワークの集合体のルート移動ルータ）が、インターネットから切断される場合、任意の２つのノード間において新しい通信を確立させる。第２の分類は、複数の階層型移動ネットワーク内において最適化された送信を提供するが、複数の階層型移動ネットワークを主ネットワークインフラに接続する必要がある。第３の分類は、ルートＭＲが全階層型ＭＲのＨＡである場合等の制限された条件下で送信の自律モードをサポートする。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
従って、複数の階層型移動ネットワークが、主ネットワークインフラとのその接続を失った場合でも、そのような複数の階層型移動ネットワークの一部を形成する２つの装置が、互いに通信できるようにする集中的な方法を実現する必要がある。また、集合体の移動ネットワークの数が増加するにつれて、２つの通信ノード間においてパケットがたどる経路は、複数の階層型移動ネットワーク内における２つの通信ノードの深さの増大と共に複雑さが増す。従って、更に、複数の階層型移動ネットワークの一部を形成する２つの通信ノード間に最適経路を提供する必要性がある。
【発明を実施するための最良の形態】
【０００９】
添付図は、同様な参照数字が、個々の図全体において同じ又は機能的に同様な要素を指し、また、下記詳細な説明と共に、本明細書に引用され、その一部を形成するが、様々な実施形態を更に示し、また、本発明に基づき様々な原理及び利点全てを説明する役割を果たす。
【００１０】
本発明に基づく実施形態について詳細に述べる前に確認されたいことは、本実施形態が、本来、最小信号伝達オーバーヘッドで複数の階層型移動ネットワーク用の自律モードのサポートを可能にするための方法及び装置に関連した方法ステップ及び装置構成要素の組合せに存することである。従って、装置構成要素及び方法ステップは、適宜、図面において従来の符号によって表しており、本明細書の説明の恩典を有する当業者には自明の細目により本開示を不明瞭にしないように、本発明の実施形態の理解に関連する特定の詳細だけを示す。従って、説明を簡単明瞭にする目的で、商品化の視点から実現可能な実施形態において有用又は必要な通常の公知の要素は、これら様々な実施形態の理解を妨げることが無いようにするために、示さない場合があることを認識されたい。
【００１１】
本明細書において、第１及び第２、最上部及び底部等の関係を示す用語は、単に、１つのエンティティ又はアクションを他のエンティティ又はアクションと区別するために用いることがあり、必ずしも、そのようなエンティティ又はアクション間における何らかの実際のそのような関係又は順番を必要とする又は意味することはない。用語「含まれる」、「含まれている」、「有する」、「有している」、「含む」、「含んでいる」、「含有する」、「含有している」、又はそれらの他の何らかの派生語は、非排他的包含を網羅するように意図されており、一連の要素が含まれる、を有する、を含む、を含有するプロセス、方法、物、又は装置は、それらの要素だけでなく、明示的に列記されていない他の要素や、そのようなプロセス、方法、物、又は装置に固有の他の要素も含み得る。「・・・が含まれる」、「・・・を有する」、「・・・を含む」、「・・・を含有する」が続く要素は、更なる制約条件無しで、その要素が含まれる、を有する、を含む、を含有するプロセス、方法、物、又は装置において、他の同じ要素が存在することを除外しない。用語「実質的に」、「本質的に」、「大体」、「約」、又はそれらのいずれか他のバージョンは、当業者によって理解されるものと近いと定義し、１つの非限定的な実施形態では、この用語は、１０％以内、他の実施形態では、５％以内、他の実施形態では、１％以内、他の実施形態では、０．５％以内と定義する。本明細書に用いる用語「結合された」は、必ずしも直接とは限らず、また、必ずしも機械的にとは限らないが、接続されたと定義する。或るやり方で「構成された」装置又は構造は、少なくともそのやり方で構成されるが、列記されていないやり方でも構成されることがある。
【００１２】
本明細書に述べた本発明の実施形態には、１つ又は複数の従来のプロセッサと、本明細書に述べた最小信号伝達オーバーヘッドで複数の階層型移動ネットワーク用の自律モードのサポートを可能にするための方法及び装置の機能の一部、ほとんど、又は全てを或る非プロセッサ回路で実現するための１つ又は複数のプロセッサを制御する固有の記憶されたプログラム命令と、を含み得ることを認識されるであろう。非プロセッサ回路には、これらに限定するものではないが、無線受信機、無線送信機、信号ドライバ、クロック回路、電源回路、及びユーザ入力装置を含み得る。このように、これらの機能は、本明細書に述べた最小信号伝達オーバーヘッドで複数の階層型移動ネットワーク用の自律モードをサポートする方法のステップとして解釈し得る。他の選択肢として、幾つかのもしくは全ての機能は、記憶されたプログラム命令を有しない状態機械によって、又は１つもしくは複数の特定用途向け集積回路（ＡＳＩＣ）において実現でき、この場合、全機能の幾つかの各機能もしくは幾つかの組合せは、カスタム論理回路として実現される。もちろん、これら２つの手法の組合せを用いることができる。従って、これらの機能のための方法及び手段が、本明細書に記載されている。更に、当業者は、例えば、利用可能な時間、現在の技術、及び経済的な要件によって動機付けられる恐らく多大な労力や多くの設計の選択肢にもかかわらず、本明細書に開示された概念及び原理によって導かれると、最小の実験作業でそのようなソフトウェア命令やプログラム及びＩＣを容易に生成し得ることが期待される。
【００１３】
一般的に、様々な実施形態によれば、本発明は、複数の階層型移動ネットワークにおいて自律モードのサポートを提供するメカニズムを開示する。本メカニズムは、また、複数の階層型移動ネットワークにおける任意の２つの移動エンティティ間に最適なルーティング経路を提供する。本発明は、本来、複数の階層型移動ネットワークのルート移動エンティティ上において、ルーティング方法論を発見し、登録し、実現し、その後に続く複数の階層型移動ネットワークにおける移動エンティティへのルーティング情報の配信、及び移動エンティティ間に配信されたルーティング情報を用いてルーティングを行うためのシステム及び方法論を取り扱う。従って、本発明は、一般的に、ルート移動ルータ（ルートＭＲ）の観点から、複数の階層型移動ネットワークにおいて自律モードを実現するための集中型の手法に関する。本手法は、通常、複数の階層型移動ネットワークが自律モードである場合、複数の階層型移動ネットワークにおける任意の２つのノード間の通信を円滑化する段階を含む。それは、また、複数の階層型移動ネットワークが、接続モードである場合、複数の階層型移動ネットワークにおいて、最適化されたルーティングを任意の２つのノード間に提供する。本明細書に記載した上記認識された利点及び他の利点は、単に例示的であり、本発明の様々な実施形態の全利点の完全な表現であることを意味しないことに当業者は気付かれるであろう。
【００１４】
本開示に用いられる用語は、本明細書において説明する。この説明は、明瞭にする目的のために提供されたものであり、如何なる場合でも、特定の用語及びそれと共に用いられるあらゆる他の用語の意味を、本明細書に提供された説明に限定するものと解釈すべきでない。
【００１５】
移動ネットワークは、一組のノードとして理解可能であり、１つ又は複数のＩＰサブネットを含み、１つ又は複数の移動ルータ（ＭＲ）に接続され、また、それらによってサービスが提供され、ネットワーク又はインターネットの他の部分に対して一つのまとまったものとして移動可能である。移動ネットワークは、本明細書では、ＮＥＭＯとも称する。
【００１６】
移動ネットワークノード（ＭＮＮ）は、移動ネットワークにおけるノードである。
移動ネットワークは、移動ネットワークが他の移動ネットワークに接続される場合、階層化されると言われる。移動ネットワークの集合階層構造は、単一の階層型移動ネットワーク又は集合体になる。
【００１７】
ローカル移動ノード（ＬＭＮ）は、移動ルータ（ＭＲ）に対してトポロジーが移動し得る移動ノード（ＭＮ）であり、ホスト又はルータのいずれかであり、また、そのホームリンクは、ＭＲを介して接続された移動ネットワークに属する。
【００１８】
訪問移動ノード（ＶＭＮ）は、移動ルータ（ＭＲ）に対してトポロジーが移動し得る移動ノード（ＭＮ）であり、ホスト又はルータのいずれかであり、また、そのホームリンクは、ＭＲを介して接続された移動ネットワークに属さない。移動ネットワーク内における異種のリンクに接続されたＶＭＮは、そのリンク上のアドレス、即ち、気付アドレス（ＣｏＡ）を得る。
【００１９】
移動ネットワークプレフィクスは、ＩＰアドレスの複数の最初のビットを含むビット文字列であり、移動ネットワークプレフィクスは、インターネットトポロジ内における移動ネットワークを識別する。移動ネットワーク中の全ノードは、必然的にこのプレフィクスを含むアドレスを有する。
【００２０】
移動ルータ（ＭＲ）の内部インターフェイスは、移動ネットワーク内側のリンクに接続されたインターフェイスである。
ルートＭＲは、階層型移動ネットワークを固定インターネットに接続するために用いられるルートＮＥＭＯの移動ルータである。ルートＮＥＭＯは、階層構造の最上部にある移動ネットワークであり、集合階層型移動ネットワークをインターネットに接続する。
【００２１】
親ＭＲは、親ＮＥＭＯの移動ルータである。親ＮＥＭＯは、上流移動ネットワークであり、階層構造の更に下にある移動ネットワークにインターネットアクセスを提供する。
下位ＭＲは、親ＮＥＭＯに接続された下位ＮＥＭＯの移動ルータである。下位ＮＥＭＯは、階層構造上部の移動ネットワークに接続された下流移動ネットワークである。これは、親ＮＥＭＯに従属する。下位ＮＥＭＯは、親ＮＥＭＯを介してインターネットアクセスを得るが、親ＮＥＭＯにインターネットアクセスを提供しない。
【００２２】
移動装置に関して、隣接移動装置は、移動装置に接続され上流又は下流移動装置である移動装置である。
次に、図を参照すると、特に図１において、複数の階層型移動ネットワークのブロック図が示され、全体が１００として表記されている。複数の階層型移動ネットワーク１００は、説明を理解しやすいように、５つの階層型移動ネットワークで示す。しかしながら、本例示例の具体的細目は、本発明それ自体の具体的細目ではないこと、また、本明細書に記載された教示内容は、他の様々な状況でも適用可能であることを当業者は認識され理解されたい。例えば、記載した教示内容は、複数の階層型移動ネットワークを形成する階層型移動ネットワークの数に依存しないことから、本実施形態では、５つの階層型移動ネットワークを示すが、複数の階層型移動ネットワークにおける任意の数の階層型移動ネットワークに適用される。このように、複数の階層型移動ネットワークにおいて、異なる数の階層型移動ネットワークを用いる他の選択肢としての実施例が考えられ、記載した様々な教示内容の範囲内にある。従って、複数の階層型移動ネットワークは、更に多くの階層型移動ネットワーク、又は、通常、最小数は２つの移動ネットワークであるが、５未満の移動ネットワークを含み得ることに当業者は気付かれるであろう。階層型移動ネットワークには、複数の移動エンティティ又はノードに加えて、複数の固定されたエンティティ又はノード（説明を簡単にするために図示せず）を含み得る。移動エンティティは、移動ルータ又は移動ホストであってよく、移動ネットワーク（固定又は移動のいずれでもよい）における任意のノードは、移動ネットワークノード（ＭＮＮ）であると言われる。更に、階層型移動ネットワークは、移動ルータ（ＭＲ）を介して、複数の階層型移動ネットワークの集合体に接続される。
【００２３】
図１に戻ると、複数の階層型移動ネットワーク１００を示す一実施形態は、第１移動エンティティ１０８（ＭＲ４）を介して接続された第１移動ネットワークノード１５０（ＭＮＮ４）と、第２移動エンティティ１０６（ＭＲ３）を介して接続された第２移動ネットワークノード１４５（ＭＮＮ３）とを含むが、本明細書の移動エンティティは、例えば、移動ルータ（ＭＲ）である。第１移動エンティティ１０８は、第１階層型移動ネットワーク１１８に接続し、第２移動エンティティ１０６は、第２階層型移動ネットワーク１１６に接続する。複数の階層型移動ネットワーク１００の最上部では、ルート移動エンティティ１０２（ＭＲ１）が、一般的にインターネットと称するコアネットワークインフラ１５５に複数の階層型移動ネットワーク１００を接続し得る。ルート移動エンティティ１０２は、複数の階層型移動ネットワーク１００の最上部にあり、また、第１移動エンティティ１０８を第２移動エンティティ１０６に接続する。
【００２４】
一実施形態によれば、第１移動エンティティ１０８は、移動ネットワーク１１４に接続する第３移動エンティティ１０４（ＭＲ２）等の複数の移動エンティティを介して、ルート移動エンティティ１０２に接続される。同様に、第２移動エンティティ１０６は、複数の中間移動エンティティを介して、ルート移動エンティティ１０２に接続される。第１移動エンティティ１０８及び第２移動エンティティ１０６に接続する移動エンティティに加えて、複数の階層型移動ネットワーク１００には、追加の移動エンティティ、例えば、移動ネットワーク１２０に接続する第４移動エンティティ１１０（ＭＲ５）を含む。図示したものは、簡単にするために、単一のルート移動エンティティである。しかしながら、普遍性を失うことなく、１つ又は複数のルート移動エンティティを複数の階層型移動ネットワークに含み得ることに当業者は気付かれるであろう。更に、上述したように、移動ネットワークの階層化は、任意の数の階層化レベルまで行き着くことができ、階層化レベルは、ハードウェア及び他のネットワーキング制約条件によって制御される。
【００２５】
説明を簡単にするために、本明細書で説明する実施形態では、複数の階層型移動ネットワークには、複数の階層型移動ネットワークの一部を形成する５つの階層型移動ネットワーク（１１２、１１４、１１６、１１８、１２０）が含まれる。複数の移動エンティティ１０２、１０４、１０６、１０８、１１０に対応する複数のホームエージェント１６２（ＨＡ１）、１６４（ＨＡ２）、１６６（ＨＡ３）、１６８（ＨＡ４）、１７０（ＨＡ５）は、コアネットワークインフラ１５５に接続される。従来、複数の移動エンティティに対応するホームエージェントは、移動エンティティが、異種のネットワークにおいてローミングしている間、移動エンティティ間で送受信される情報のルーティングを管理してきた。複数の階層型移動ネットワーク１００は、本実施形態では、無線リンク１６０によって、コアネットワークインフラ１５５に接続される。
【００２６】
本発明の実施形態が提案することは、複数の階層型移動ネットワークにおける各移動エンティティ（移動エンティティは、本質的に、移動ルータである）は、複数の階層型移動ネットワークにおいて自律モードのサポートを提供するために、移動エンティティの移動ネットワークプレフィクス（ＭＮＰ）を移動エンティティの気付アドレス（ＣｏＡ）にマッピングする結合更新（ＢＵ）を送ることによって、ルート移動エンティティ（ルート移動ルータ）に登録するということである。そして、登録された移動エンティティは、ルート移動エンティティにある結合キャッシュ（ＢＣ）に入力される。結果的に生じる組のＢＣ登録項目により、ルート移動エンティティは、それ自体から一組の中間移動エンティティを介して複数の階層型移動ネットワークにおける任意のノードまでの経路を決定することが可能になる。自律モードの場合、これらの決定された経路により、移動エンティティは、そのホームエージェント（ＨＡ）を介する代わりに、上位移動エンティティを介して、発信パケットをルート移動エンティティに通すことが可能になる。しかしながら、複数の階層型移動ネットワーク内における移動ノードからのパケットもまた、ＨＡを介して宛先移動ノードに通し得るという場面が存在し、そのような場面が、本発明の範囲内にあることを当業者は認識されたい。通過したパケットを受信すると、ルート移動エンティティは、内部の元のパケットを検索し、その結合キャッシュ（ＢＣ）の繰り返し解析をパケットの宛先アドレスに用いて、ルート移動エンティティから宛先までの経路上にある中間移動エンティティの気付アドレスの順序付けしたリストを導出する。宛先に対する結合キャッシュの解析が成功するということは、宛先が、複数の階層型移動ネットワークの一部であること、また、パケットは、移動エンティティの気付アドレスのこの順序付けしたリストに沿って、多重カプセル又はルーティングヘッダのいずれかを用いることによって、発信元から宛先にルーティングし得ることを意味する。
【００２７】
次に、図２において、一実施形態が、移動エンティティ、例えば、移動ネットワーク２２０の一部を形成するＭＲ４と称する移動ルータ２１０と、階層型移動ネットワーク２１５の集合体の一部を形成するＭＲ３と称する隣接移動ルータ２３０との間の接続２００を示す。図示するように、ＭＲ４は、移動ルータＭＲ３の下で階層化されており、ＭＲ３及びＭＲ４双方共、複数の階層型移動ネットワーク２１５、２２０の一部を形成する。ＭＲ４＿２１０は、ＭＲ３＿２３０を介して接続された複数の階層型移動ネットワーク２１５に移動ネットワーク２２０を接続する。この図において、複数の階層型移動ネットワーク２１５は、移動ネットワーク２２０（及びそれに対応して下位ＭＲであるＭＲ４＿２１０）に対する親ＮＥＭＯであり（ルートＭＲ２０１は、ルート移動ルータであり）、移動ネットワーク２２０は、移動ネットワーク２１５に対する下位ＮＥＭＯである。移動エンティティ２１０とルート移動エンティティ２０１との間の接続には、複数の移動ルータ、例えば、ＭＲ１＿２０５、ＭＲ３＿２３０を含み得る。図示するように、移動ルータＭＲ４は、移動ネットワークノードＭＮＮ４＿２４０にサービスを提供し、一方、移動ルータ２２５（ＭＲ２）は、移動ネットワークノードＭＮＮ２＿２３５にサービスを提供する。接続には、ゼロ又は１つもしくは複数の移動ルータを含み得ること、また、本実施形態２００は、そのような接続を示す単なる例であり、理解しやすいように、また、説明を簡単にするために、このように記載していることを当業者は認識されたい。
【００２８】
移動エンティティＭＲ４＿２１０は、複数の階層型移動ネットワーク２１５への接続を確立するために、ルート移動エンティティ・ルートＭＲ２０１のアドレスを発見しなければならない。この目的のために、“ルート移動ルータ宣言”（ＲＭＲＡ）の選択肢を、ルータ広告（ＲＡ）メッセージのために導入し、これによって、ルート移動エンティティ・ルートＭＲ２０１は、複数の階層型移動ネットワーク２１５、２２０におけるそのアドレスを、例えば、ルートＭＲの内部インターフェイスを介して宣言する。一実施形態において、ＲＭＲＡの選択肢は、少なくともルート移動エンティティ・アドレス及び次ホップ移動エンティティ・アドレスを含む。
【００２９】
ルート移動エンティティ・アドレスは、ルート移動エンティティ２０１の内部インターフェイスのアドレス、又はルート移動エンティティ２０１のホームアドレス、又はルート移動エンティティ２０１の気付アドレスのいずれであってもよい。代表的な本発明の一実施形態において、内部インターフェイスアドレス又はホームアドレスは、ルート移動エンティティ・アドレスとして割り当てられる。ルート移動エンティティ２０１の気付アドレスは、一般的に、ルート移動エンティティ２０１が移動し、それに対応して気付アドレスが変化するため、好ましくない。その結果、他の移動エンティティＭＲ１＿２０５、ＭＲ２＿２２５、ＭＲ３＿２３０、及びＭＲ４＿２１０は、結合更新（ＢＵ）を新しいルート移動エンティティのアドレスに再送しなければならず、このため、追加のオーバーヘッドが生じる。
【００３０】
次ホップアドレスは、ルート移動エンティティ２０１側の経路上にある上位移動エンティティのアドレスである。この次ホップアドレスは、通常、複数の階層型移動ネットワークの一部である所定の移動ネットワークにおける移動エンティティにＲＭＲＡの選択肢を送る移動エンティティのアドレスである。例えば、移動エンティティＭＲ４＿２１０の場合、次ホップアドレスは、移動エンティティＭＲ３＿２３０のアドレスである。ＲＭＲＡの選択肢を受信する移動エンティティは、その情報を用いて、パケットをルート移動エンティティ２０１側に通す。
【００３１】
新しい移動エンティティＭＲ４＿２１０は、既定値として、それが、ルート移動エンティティであると仮定する。例えば、ＭＲ４は、その外部インターフェイスの内の少なくとも１つにおいて、例えば、ルートＭＲ２０１から有効なＲＭＲＡの選択肢を備えたルータ広告（ＲＡ）メッセージを受信しない限り、そのルート移動エンティティ・アドレスを選択し、その内部インターフェイスを介して、それをＲＭＲＡの選択肢の“ルート移動エンティティ・アドレス”フィールドで宣言する。ＲＭＲＡの選択肢が受信されなくなる時まで、そのことは、移動エンティティが、複数の階層型移動ネットワークに参加していないことを意味し、実際、それ自体のネットワークのルート移動エンティティであることを当業者は認識されるであろう。しかしながら、ＲＭＲＡの選択肢が、例えば、ルートＭＲ２０１から受信されると、移動ルータＭＲ４は、ルートＭＲが、複数の階層型移動ネットワーク２１５の一部であることを検出し、移動エンティティ・ルートＭＲステータスを割り当てる。そして、ＭＲ４は、受信されたＲＭＲＡの選択肢からのルート移動エンティティ２０１アドレスを、その全ての内部インターフェイスを介して送られるそれ自体のＲＭＲＡの選択肢において伝える。
【００３２】
同様に、ルート移動エンティティ２０１は、それが送るＲＭＲＡの選択肢の“次ホップ移動エンティティ・アドレス”フィールドにそのルート移動エンティティ２０１アドレスを置く。また他の選択肢として、ルートＭＲは、フィールドを空にして、その値が、ルート移動エンティティ２０１アドレスフィールドと同じであることを示す。ＲＭＲＡの選択肢を受信するＭＲ１＿２０５、ＭＲ２＿２２５、ＭＲ３＿２３０、ＭＲ４＿２１０等のルート移動エンティティ下の任意の移動エンティティが、それ自体のルータ広告において、ＲＭＲＡの選択肢を中継するが、それ自体の内部インターフェイスアドレスの内の１つを含むように“次ホップ移動エンティティ・アドレス”フィールドを変更し、移動ルータの内部インターフェイスを介してルートＭＲにアクセスし得ることを示す。移動ネットワークの任意の固定ルータは、選択肢が全移動ネットワークにおいて伝わることができるように、インターフェイスで受信されたＲＭＲＡの選択肢を、固定ルータが送るいずれかのルータ広告（ＲＡ）に伝える。固定ルータは、ＲＭＲＡの選択肢を修正することはなく、例えば、“次ホップアドレス”フィールドを変更することはない。
【００３３】
従って、ＲＭＲＡによって、複数の階層型移動ネットワークにおける移動エンティティ２０５、２３０、２２５、２１０、２１５は、ルート移動エンティティ・ルートＭＲ２０１、ルート移動エンティティ２０１側の次ホップ移動エンティティ、この次ホップ移動エンティティ側の外部インターフェイスを発見することができる。外部インターフェイスアドレスは、それ上でＲＭＲＡの選択肢が受信されたインターフェイスである。この情報は、パケットをルート移動エンティティ側へ上流にルーティングするために移動エンティティによって用いられる。ルート移動エンティティ宣言は、ルータ広告メッセージの拡張部を介する代わりに、別個のメッセージを介して実現し得ることを当業者は認識されるであろう。
【００３４】
ルートＭＲ２０１からＲＡ宣言の一部としてＲＭＲＡの選択肢を受信すると、移動エンティティＭＲ４＿２１０は、ＭＲ４の移動ネットワークプレフィクス（ＭＮＰ）２２０をＭＲ４の気付アドレス（ＣｏＡ）に結合するためのルートＭＲ２０１への結合更新（ＢＵ）メッセージを生成して、ＢＵをＭＲ４の次ホップ移動エンティティに、例えば、図示するように、ＲＭＲＡの選択肢が受信されたＭＲ４の外部インターフェイスを介して、ＭＲ３＿２３０に通す。ルート移動エンティティ２０１への経路上に中間移動エンティティ（ＭＲ３＿２３０、ＭＲ１＿２０５）がある状況では、これら各移動エンティティ（ＭＲ１＿２０５、ＭＲ３＿２３０）は、ＩＰトンネルを介して、ルートＭＲ側の経路上のそれら自体の次ホップ移動エンティティにＢＵをルーティングすることに当業者は気付かれるであろう。固定ルータが、ルートＭＲ側の経路上において移動エンティティとその次ホップ移動エンティティとの間に存在しない場合、ＩＰトンネルを飛ばして、その後、ルートＭＲに宛てられたＢＵを、次ホップ移動エンティティのリンク層（例えば、ＭＡＣ）アドレスに移動エンティティによって直接送ることができる。
【００３５】
ＢＵメッセージを受信すると、ルート移動エンティティ２０１は、その結合キャッシュ（ＢＣ）の既存の入力項目を追加又は更新することによって、ＢＵメッセージを処理し、移動エンティティＭＲ４＿２１０のＭＮＰ２２０をその気付アドレスに結合する。従って、ルート移動エンティティ２０１は、複数の階層型移動ネットワークにおけるそれらそれぞれの移動ルータの下の各移動ネットワーク用のそのようなＢＣを有する。ＢＣの登録項目は、内部の複数の階層型移動ネットワークの構成、例えば、どの移動エンティティが、どのＭＮＰにサービスを提供しているか、また、様々な移動エンティティ間の接続の概観をルート移動エンティティ２０１に提供する。
【００３６】
移動エンティティが、所定の期間、例えば、ＲＡ期間の数倍の期間、ＲＭＲＡの選択肢を受信しない場合、移動エンティティは、移動エンティティが、もはや複数の階層型移動ネットワークの一部ではないことを検出して、既定動作モードに切換わり、例えば、移動エンティティに対応するホームエージェント（ＨＡ）を介して、発信トラフィックを転送する。
【００３７】
次に、図３において、本発明の実施形態に基づく複数の階層型移動ネットワークを形成する移動装置間の自律モードルーティングを可能にする方法のフロー図を全体的に３００に示す。図示するように、ステップ３０５において、ルート移動エンティティは、複数の階層型移動ネットワークにおけるその存在を宣言して、図２を用いて開示したように、移動エンティティが、ルート移動エンティティを発見することができるようにする。ルートＭＲの発見の後、ルートＭＲは、複数の階層型移動ネットワークにおける非登録移動エンティティからのルーティング情報を含む登録要求（一実施形態において、結合更新）を受信する（ステップ３１０）。ルーティング情報は、少なくとも移動エンティティの気付アドレス及び移動エンティティ用の移動ネットワークプレフィクス（ＭＮＰ）又は移動エンティティ用のホームアドレスを含む。登録要求は、移動エンティティが、インフラに接続されている間に、又は、自律モードの間に受信可能であり、少なくとも１つの登録要求が、自律モード中に受信される。一実施形態において、自律モードは、移動ルータのホームエージェントを介したパケットのルーティングを不要にすることによって、複数の階層型移動ネットワークにおける移動ルータが互いにパケットを交信する時、使用可能にできる。
【００３８】
自律モード送信においてルーティング情報を後で使うために記憶する場合、ルート移動エンティティは、複数の階層型移動ネットワークにおける移動エンティティの登録要求から受信されたルーティング情報を用いて、ルート移動エンティティ結合キャッシュ（ＢＣ）を生成する（ステップ３１５）。ＢＣは、通常、更に定期的に更新されたり、又は、例えば、移動ルータのように、移動エンティティが、複数の階層型移動ネットワークを離れたりもしくはそれらに参加したり、又は、複数の階層型移動ネットワーク内に移動する場合、受信されたＢＵに基づく。結合キャッシュは、複数の階層型移動ネットワークに属する移動エンティティ用の登録項目だけでなく、例えば、インフラ全体で何らかの形態の経路最適化がサポートされている場合、インフラに接続された他の移動エンティティ用の登録項目も含み得ることを当業者は認識されるであろう。
【００３９】
ルートＭＲは、結合キャッシュ（ＢＣ）のどの登録項目が、複数の階層型移動ネットワークにおける階層型移動ネットワークを指すか決定することができ、こうして、これらの登録項目だけが、ルート移動エンティティのルーティング処理において考慮される。このルーティング処理には、例えば、ＢＣの繰り返し解析を含む。この目的のために、一実施形態では、新しい自律モード（ＡＭ）フラグを定義して、ルート移動エンティティのＢＣにおける各入力項目に追加する。通常、ＡＭフラグは、入力項目が、ルート移動エンティティによってサービスが提供される複数の階層型移動ネットワークの一部である移動ネットワークを意味する場合、１に設定され、そうでない場合、０に設定される。ＡＭフラグの値は、新しい入力項目がＢＣにおいて更新される度に、例えば、新しい結合更新を受信すると、更新される。更新には、更に、結合キャッシュにおける新しい入力項目の生成を含むが、この場合、ＡＭフラグが設定される。従って、新しい自律モード（ＡＭ）ビットが、結合更新メッセージにおいて定義される。このビットは、ＲＭＲＡの選択肢を受信する際検出されたそれらのルート移動エンティティ（又は、複数の階層型移動ネットワークに関連する多数のルート移動エンティティがある場合、それらのルート移動エンティティの内の１つ）に結合更新を送っている移動エンティティ又はノード（移動ルータ又は移動ホスト）によって、１に設定される。
【００４０】
次に、図４において、本発明の実施形態に基づき、複数の階層型移動ネットワークに属するノードから宛先アドレスにパケットをルーティングする方法のフロー図を示す。発信元ノード及び宛先ノードは、複数の階層型移動ネットワークにおける任意の移動ネットワークノードであってよいことに当業者は気付かれるであろう。複数の階層型移動ネットワークにおける任意の移動エンティティは、発信パケットをルート移動エンティティ側に通すことができ、ルート移動エンティティは、定期的に複数の階層型移動ネットワークにおける移動エンティティによって送られる結合更新に基づき、その結合キャッシュを更新している。ルートＭＲは、パケットを宛先ノードにルーティングするための集中型の手法を提供する。説明を簡単にするために、発信元ノードから宛先ノードへのパケットルーティングは、図２を参照することによって示すが、この場合、例えば、パケットは、複数の階層型移動ネットワークの外側にある宛先ノード（図示せず）に発信元ノードＭＮＮ４＿２４０からルーティングしなければならない。
【００４１】
ルートＭＲ２０１は、ノードＭＮＮ４＿２４０にサービスを提供する移動エンティティＭＲ４＿２１０から宛先アドレスを含むパケットを受信するが、この場合、パケットは、ノードＭＮＮ４＿２４０によって生成される（ステップ４０５）。移動エンティティ２１０は、一実施形態において、まず、宛先アドレスをＲＭＲＡの選択肢から分かっているルート移動エンティティ２０１アドレスに設定し、また、発信元アドレスをＭＲ４のＩＰアドレスに、例えば、その外部インターフェイスアドレスの内の１つに設定した状態で、ＩＰヘッダにパケットをカプセル化することによって、パケットをルート移動エンティティ２０１に通す。また、追加のトンネルを用いて、ルート移動エンティティ２０１側の次ホップ移動エンティティにパケットを転送するが、次ホップ移動エンティティは、ＲＭＲＡの選択肢から求められ、この場合、ＭＲ３＿２３０である。従って、最初のパケットは、２回通るが、最初は、ルートＭＲ２０１へ、２回目は、次ホップ移動エンティティＭＲ３＿２３０に至る。移動エンティティが、同じ外部インターフェイス上に幾つかの上流移動エンティティを有し得ることから、ＭＲ４＿２１０とＭＲ３＿２３０との間で第２カプセルが用いられ、そして、ルート移動エンティティ２０１に宛てられたパケットを、既定経路に沿って、誤った上流移動エンティティ側に、例えば、ルート移動エンティティ２０１側の次ホップではない移動エンティティ側にルーティングすることがある。
【００４２】
単一移動エンティティ移動ネットワークだけを考慮するならば、（ＲＭＲＡの選択肢における次ホップ移動エンティティ・アドレスと共に）移動エンティティと次ホップ移動エンティティとの間の第２の通過は、回避し得ることを当業者は認識されるであろう。同様に、移動エンティティと次ホップ移動エンティティとの間に固定ルータがない場合、第２の通過は、同様に回避される。この場合、移動エンティティは、１回通過した（ルート移動エンティティに宛てられた）パケットを次ホップ移動エンティティのリンク層（例えば、ＭＡＣ）アドレスに直接送る。
【００４３】
２回通過したパケットは、ＭＲ４＿２１０の外部インターフェイスを介して、次ホップ移動エンティティＭＲ３＿２３０側に送られる。次ホップ移動エンティティを含む後続の移動エンティティは、第１レベルのカプセルを除去し、内部パケットを検索されるが、このパケットは、ルート移動エンティティ２０１に宛てられる。それが受信したＲＭＲＡの選択肢を含む情報を用いて、パケットは、ルート移動エンティティ２０１に向けて次ホップ移動エンティティ側へ再度通される。ルート移動エンティティへの経路上にある最後の移動エンティティ、この場合、ＭＲ１＿２０５は、次ホップ移動エンティティが、実際、ルート移動エンティティ２０１であることを知り、追加のヘッダを追加しないと決定する。従って、発信元ノードＭＮＮ４＿２４０から宛先ノードへのパケットは、最初に、ルート移動エンティティ２０１に通される。そして、この通過したパケットは、ルート移動エンティティ２０１への経路に沿って、移動エンティティから次ホップ移動体エンティティへのＩＰトンネルを介して、移動エンティティＭＲ４＿２１０からルート移動エンティティ２０１にルーティングされる。
【００４４】
一旦、ルート移動エンティティ２０１が移動エンティティによって送られたパケットを受信すると（移動ルータＭＲ４＿２１０は、発信元ノードＭＮＮ４＿２４０にサービスを提供する）、発信元ノードＭＮＮ２４０によって送られた内部の最初のパケットを抽出する。そして、ルート移動エンティティ２０１は、それがパケットを宛先にルーティングし得るかどうか判断するために、パケットの宛先アドレスが、複数の階層型移動ネットワークの一部であるかどうか判断する（ステップ４１０）。この判断処理は、ルート移動エンティティ２０１から宛先アドレスへの経路を見つけるために、結合キャッシュの繰り返し解析を伴う。ルート移動エンティティから宛先アドレスへの経路は、ルート移動エンティティと宛先アドレスとの間の中間移動エンティティの順序付けしたリストの気付アドレスを含む。ルートＭＲ２０１が、結合キャッシュを用いて宛先アドレスへの経路を決定できない場合、例えば、宛先アドレスが、ルート移動エンティティ２０１によってサービスが提供される複数の階層型移動ネットワークの一部ではない場合、ルートＭＲ２０１は、ルートＭＲが“ルートＭＲ到達可能プレフィクス”（後述）の宣言を用いるならば、パケットを廃棄でき、又は、宛先アドレス側へのパケットの他のルーティングを可能にするために、ノードＭＮＮ４＿２４０にサービスを提供する移動エンティティＭＲ４＿２１０に“宛先到達不可通知”を送ることができる（ステップ４１５）。ルート移動エンティティ２０１は、発信元ＭＮＮ４＿２４０にサービスを提供する移動エンティティＭＲ４＿２１０に対して、それが、ルート移動エンティティ２０１を介して宛先アドレスに今後のパケットをルーティングしようとすべきでないが、その代わり、他のルート移動エンティティ（幾つか存在する場合）を用いるべきであり、又は、パケットをＨＡに通し得る既定モードを用いるべきであると通知する。
【００４５】
到着不可能な宛先アドレスに宛てられたルート移動エンティティ側へのあらゆるパケットの通過を停止するように、発信元ノードにサービスを提供する移動エンティティに通知する間、ルート移動エンティティは、パケットの発信元ノードにサービスを提供する移動エンティティのアドレスを検索できなければならず、また、ルート移動エンティティは、発信元ノードに対応するこの移動エンティティ側の経路を検索して、通知を送ることができるようにしなければならない。本発明の代表的な一実施形態において、発信元ノードにサービスを提供する移動エンティティのアドレス及びそれ側の経路の検索は、ルート移動エンティティが、その結合キャッシュの繰り返し解析の方法を用いて、ルートＭＲから発信元ノードアドレスへの経路を捜す場合、同時に行うことができる。経路における最後のアドレスは、発信元ノードにサービスを提供する移動エンティティ（例えば、移動ルータ）の気付アドレスであり、また、経路上の各移動ルータの他のアドレスは、ルート移動エンティティから発信元ノードにサービスを提供する移動エンティティへの経路を形成する。そして、ルートＭＲは、多重カプセル又はルーティングヘッダのいずれかを用いて、ルート移動エンティティから発信元にサービスを提供する移動エンティティへの識別された経路に沿って、発信元にサービスを提供する移動エンティティに宛てられた通知をルーティングする。
【００４６】
移動エンティティは、ルート移動エンティティ側の指定された宛先アドレスへのトラフィックの転送を停止するが、その代わり、他のルート移動エンティティ又は既定値ルーティングメカニズムを用いるように、ルートＭＲから受信する通知メッセージを追跡する。一実施形態において、移動エンティティは、特定の時間、指定された宛先アドレスへのトラフィックの転送を停止し、そして、定期的なチェックを実施して、宛先アドレスが到達可能かどうか判断する。更に、通知メッセージから受信された情報の記憶を可能にするために、自律モード宛先到着不可能キャッシュ（ＡＭＤＵＣ）と呼ばれる構成が、導入される。ＡＭＤＵＣは、各ルート移動エンティティにとって到着不可能な宛先アドレスのリストが（理想的には、各アドレスに関連する寿命と共に）を含む。寿命は、一般的に、アドレスがＡＭＤＵＣ内に置かれる場合、既定値に設定され、又は受信された通知メッセージにおいて示し得る値に設定される。アドレスは、寿命が切れると、ＡＭＤＵＣから除去される。これによって、移動エンティティは、宛先アドレスが、複数の階層型移動ネットワークに参加していると可能になり得るルート移動エンティティを介した経路最適化を定期的に再試行する。
【００４７】
本発明の一実施形態によれば、ルート移動エンティティは、それ自体の移動ネットワークプレフィクスと共に、複数の階層型移動ネットワークの一部である移動ネットワークの全プレフィクスのリストを宣言する。これらのプレフィクスは、ルート移動エンティティの結合キャッシュにおいて利用可能な登録項目から求められる。本実施形態は、ＲＭＲＡの選択肢における“到達可能プレフィクスリスト”と呼ばれる特別なフィールドを用いて、到達可能なプレフィクスのリストを宣言する段階を伴う。他の実施形態は、別個のメッセージを用いて、到達可能なプレフィクスを宣言する。“到達可能プレフィクスリスト”は、ルートＭＲによって設定され、それら個々のＲＭＲＡの選択肢における他の階層型移動エンティティによって中継される。ルートＭＲは、結合キャッシュの新しいプレフィクス登録項目が出現すると、又は、幾つかの登録項目の期限が切れた時、複数の階層型移動ネットワークにおいて宣言された“到達可能プレフィクスリスト”を更新する。
【００４８】
例えば、ルート移動エンティティは、新しい移動エンティティが、複数の階層型移動ネットワークに参加した場合、又は、移動エンティティが、複数の階層型移動ネットワークを離れる場合、又は、移動エンティティの結合更新の寿命が期限切れになった場合、その“到達可能プレフィクスリスト”を更新する。ＲＭＲＡの選択肢におけるこの“到達可能プレフィクスリスト”情報を用いて、複数の階層型移動ネットワークにおける任意の移動エンティティは、ルート移動エンティティ・アドレス、ルート移動エンティティ側の次ホップ移動エンティティ、この次ホップ移動エンティティ側の外部インターフェイス（ＲＭＲＡの選択肢が受信された側のインターフェイス）、“到達可能プレフィクスリスト”によって提供されたルート移動エンティティを介して到達可能なプレフィクスのリストを知る。従って、複数の階層型移動ネットワークにおける任意の移動エンティティは、宛先アドレスが到達可能プレフィクスリストの登録項目の内の１つに合致するかどうかに応じて、所定の宛先アドレスに宛てられたパケットをルート移動エンティティ側に通すべきかどうか決定する。
【００４９】
もし、ルート移動エンティティにおける結合キャッシュの繰り返し解析から、宛先アドレスへの経路が見つからないが、宛先アドレスが、ルート移動エンティティ２０１の移動ネットワークプレフィクスに合致する場合、ルート移動エンティティ２０１は、本来、ルート移動エンティティのルーティングテーブルに示されたルート移動エンティティの内部インターフェイスを介して、パケットを宛先にルーティングする。
【００５０】
しかしながら、ルート移動エンティティにおける結合キャッシュの繰り返し解析から、ルート移動エンティティ２０１から宛先アドレスへの経路が見つかった場合、例えば、少なくとも１つの中間気付アドレスが見つかった場合、パケットは、元のパケットの多重カプセル又は単一カプセル＋ルーティングヘッダのいずれかを用いて、この経路に沿って宛先側へ転送される（ステップ４２０）。一実施形態によれば、多重カプセル化を実施する間、元のパケットは、‘ｎ’を経路上の中間アドレス数とすると、異なるＩＰヘッダに‘ｎ’回カプセル化される。図２に示す状況では、パケットが、ノードＭＮＮ４＿２４０から宛先アドレスＭＮＮ２＿２３５に送られようとする場合、ルート移動エンティティ２０１と宛先ノード２３５との間に２つの中間移動エンティティＭＲ１及びＭＲ２があることから、‘ｎ’は、２である。全てのＩＰヘッダは、発信元アドレスとしてルートＭＲ２０１を有する。これらの異なるＩＰヘッダにおける宛先アドレスは、最上位から最内部カプセルへの順番に、例えば、ＭＲ１＿２０５のＩＰヘッダがＭＲ２＿２２５のＩＰヘッダをカプセル化する状態で演算された経路と同じ順番に並び替えられる。単一カプセルでは、元のパケットは、ルーティングヘッダを備えた単一のＩＰパケットにカプセル化される。カプセルヘッダの発信元は、ルート移動エンティティ２０１アドレスであり、宛先は、経路中の最初の中間気付アドレスに設定され、経路を形成する気付アドレスの順序付けしたリストの他の部分は、ルーティングヘッダに置かれる。
【００５１】
本発明の一実施形態によれば、パケットを生成するノードは、最適経路を介して、それを到達可能宛先アドレスにルーティングするが、この場合、最適経路は、ルート移動エンティティを含まないこともある。この最適経路は、所定の方法論を用いて、移動エンティティ又はルート移動エンティティのいずれかにおいて計算される。
【００５２】
本発明の一実施形態において、ルート移動エンティティは、その結合キャッシュ（ＢＣ）からの情報を用いて、自律モード結合キャッシュ（ＡＭＢＣ）を生成する。ＡＭＢＣは、一般的に、ルート移動エンティティ下において、複数の階層型移動ネットワークの一部である移動エンティティに関する結合キャッシュの全登録項目を含む。ルート移動エンティティの結合キャッシュが、ルート移動エンティティ下における複数の階層型移動ネットワークの一部ではない移動エンティティ用の幾つかの登録項目を含む場合、ルート移動エンティティは、ＡＭフラグを用いて、複数の階層型移動エンティティの一部である移動エンティティと、そうではないものとの間を区別する。従って、フラグは、複数の階層型移動ネットワークの一部である登録項目だけの場合、１に設定される。従って、ＡＭフラグが１に設定されたＢＣの全登録項目が、ＡＭＢＣ登録項目として選択される。
【００５３】
ＡＭＢＣにおける各入力項目は、階層型移動ネットワークにおける移動エンティティの移動ネットワークプレフィクス（又は単一移動ノードの場合、単にホームアドレス）、その気付アドレス、寿命（３つの全フィールドは、関連するＢＣ入力項目からコピーされる）を含み、更にまた、移動エンティティの内部インターフェイスアドレスを含む。ＢＣから導出されるこれらの登録項目に加えて、ルート移動エンティティは、それ自体の移動ネットワークプレフィクス（ルートＭＮＰ）用の他のＡＭＢＣ入力項目を追加する。追加のＡＭＢＣ入力項目には、少なくともルート移動エンティティのＭＮＰ、ルート移動エンティティの内部アドレス、ルート移動エンティティの気付アドレス、及び寿命が、既定値に設定されて含まれる。ＡＭＢＣは、理想的にはＢＣが変更される際、通常、結合更新を受信すると更新される。ルート移動装置下の複数の階層型移動ネットワークにおける各移動エンティティは、それがルート移動装置に送る結合更新メッセージ内にその内部インターフェイスアドレスを含み、これによって、この情報は、ルート移動装置のＡＭＢＣを含む。このことは、例えば、結合更新メッセージにおける新しい“移動ルータ内部アドレス”（ＭＲＩＡ）の選択肢で実現される。
【００５４】
次に、図５において、本発明の実施形態に基づき、パケットを生成する発信元ノードにサービスを提供する移動エンティティとパケット用の宛先アドレスとの間の最適経路を計算するための所定の方法を示すフロー図を示す。ノードにサービスを提供する移動エンティティ（移動ルータ）からルート移動エンティティに進む間にパケットがたどる経路は、ノードにサービスを提供する移動ルータとルートＭＲとの間の中間移動エンティティの内部アドレスを含み、これに対して、ルートＭＲから宛先アドレスに進む間にパケットがたどる経路は、ルートＭＲと宛先アドレスとの間の中間移動エンティティの気付アドレスを含む。
【００５５】
所定の方法によれば、自律モード結合キャッシュは、繰り返し解析され、パケットを生成するノードにサービスを提供する移動ルータからルートＭＲへの第１経路を形成する内部インターフェイスアドレスのリストが検索される（ステップ５０５）。例えば、図２に戻ると、ここでは、ノードＭＮＮ４＿２４０は、パケット用の発信元ノードであり、ＭＲ４＿２１０がＭＮＮ４＿２４０にサービスを提供しており、また、パケット用の宛先は、ＭＮＮ２＿２３５であり、ＭＲ２＿２２５がＭＮＮ２２３５にサービスを提供しているが、ＭＲ４＿２１０からルートＭＲ２０１への第１経路は、ＭＲ４＿２１０、ＭＲ３＿２３０、ＭＲ１＿２０５及びルートＭＲ２０１の内部アドレスをその順番で含む。自律モード結合キャッシュは、また繰り返し解析され、ルートＭＲから宛先アドレスへの第２経路を形成する気付アドレスのリストが検索される（ステップ５１０）。例えば、ルートＭＲ２０１からＭＮＮ２＿２３５への第２経路は、移動エンティティ、ルートＭＲ２０１、ＭＲ１＿２０５及びＭＲ２＿２２５の気付アドレスを含む。第１及び第２経路に基づき、最適経路が決定される（ステップ５１５）。
【００５６】
一実施形態において、最適経路は、第１経路が、複数の階層型移動ネットワークに属する交差移動エンティティ（第１及び第２経路が交差する位置の移動エンティティ、例えば、図２のＭＲ１＿２０５）の内部インターフェイスアドレスで終端するように、また、第２経路が、交差移動エンティティの気付アドレスで始まるように、第１及び第２経路を打ち切ることによって決定される（ステップ５２０）。そして、経路は、第２経路から第１気付アドレスを除去することによって（ステップ５２５）、また、第１経路から第１内部インターフェイスアドレスを除去することによって打ち切られる（ステップ５３０）。打ち切りを実施する間、ルートＭＲ２０１の気付アドレス及びＭＲ１＿２０５（交差移動エンティティ）の気付アドレスは、第２経路から除去され、第２経路が、ＭＲ２＿２２５の気付アドレスを含むように変更される。同様に、ルートＭＲ２０１内部インターフェイスアドレス及びＭＲ４＿２１０（移動エンティティにサービスを提供する）の内部インターフェイスアドレスは、第１経路から除去され、第１経路が、ＭＲ３＿２３０、ＭＲ１＿２０５の内部インターフェイスアドレスを含むように変更される。最適経路は、第１経路及び第２経路を追加することによって決定される（ステップ５３５）。図２に示すように、発信元ノードＭＮＮ４＿２４０にサービスを提供する移動エンティティＭＲ４＿２１０から宛先ＭＮＮ２＿２２５への最適経路には、ＭＲ３＿２３０内部アドレス、ＭＲ１＿２０５内部アドレス、及びＭＲ２＿２２５気付アドレスを含む。
【００５７】
一般的に、同様な発信元及び宛先ノード用の最適経路を再計算する必要性を回避するために、最適経路は、最適経路を演算するために用いられたＡＭＢＣが利用される間、記憶される。最適経路は、理想的には、発信元ノードにサービスを提供する移動エンティティから宛先アドレスへの最短経路である。本発明の一実施形態によれば、最適経路に沿ってパケットをルーティングするために、４つのルーティング情報配信手法、例えば、能動的プッシュ手法、受動的プッシュ手法、受動的プル手法、及び半集中型手法を用いられるが、その各々については、詳細に後に記載する。最初の３つの手法は、ルート移動エンティティから複数の階層型移動ネットワークにおける他の移動エンティティへのルーティング情報の配信に依拠する。それらは、ＡＭＢＣの使用にも依拠する。最後の１つは、ルート移動装置からのルーティング情報のどのような配信も伴わず、また、ＡＭＢＣの使用に依拠しない（例えば、“内部インターフェイス”フィールドは、必要ではない）。
【００５８】
次に、図６において、複数の階層型移動ネットワークにおいて、ルート移動エンティティによって他の移動エンティティにルーティング情報を配信するための“能動的プッシュ”手法を示すフロー図を、本発明の実施形態に基づき示す。“能動的プッシュ”手法時、ルートＭＲは、その自律モード結合キャッシュを複数の階層型移動ネットワークにおける移動エンティティの少なくとも一部に伝達する（ステップ６０５）。
【００５９】
ルート移動エンティティによって送られた自律モード結合キャッシュにより、自律モード結合キャッシュを受信する複数の階層型移動ネットワークにおける各移動エンティティは、このＡＭＢＣのコピーを維持することが可能になる。ＡＭＢＣは、ルート移動エンティティによってサービスが提供される集合体ツリーにおける各移動ネットワーク用の入力項目を含み、また、ルート移動エンティティ自体の移動ネットワークを含む。集合体ツリーは、所定のルート移動ルータによってサービスが提供される複数の階層型移動ネットワークである。従って、複数のルート移動ルータが、所定の複数の階層型移動ネットワークにサービスを提供する場合、多数の集合体ツリーが存在していると言うことができ、この場合、個別のＡＭＢＣは、多数の集合体ツリーにおける各集合体ツリーに関連付けられる。各入力項目は、少なくとも移動エンティティの移動ネットワークプレフィクス（ＭＮＰ）、移動エンティティの内部インターフェイス、移動エンティティの気付アドレス、及び寿命を含む。ルート移動エンティティの各ＡＭＢＣ登録項目用の新しいＡＭＢＣの選択肢は、移動エンティティが結合更新を送る時、結合確認応答（ＢＡ）と共に移動エンティティに送られる。ＡＭＢＣリフレッシュメッセージは、ＡＭＢＣ入力項目が変わると、複数の階層型移動ネットワークにおける全ての階層型移動エンティティに送られる。変更には、新しい入力項目の追加（例えば、新しい移動エンティティが、複数の階層型移動ネットワークに参加する）、既存の入力項目の更新（例えば、寿命更新、気付アドレスの変更等）、又は明示的に除去された入力項目（例えば、寿命がゼロに設定されたＢＵの受信）を含む。
【００６０】
本発明の一実施形態において、ＡＭＢＣリフレッシュメッセージは、新しいタイプの移動性ヘッダとして実現される。本発明の他の実施形態には、信号送信を最小にするために、例えば、幾つかのＡＭＢＣ登録項目が、短い時間間隔中に修正される時、単一のＡＭＢＣリフレッシュメッセージに幾つかのＡＭＢＣの選択肢を集約するルート移動エンティティを含む。更に本発明の他の実施形態において、ルート移動エンティティは、ＡＭＢＣリフレッシュを送る前、或る時間の間、待機して変更を集約する。また、ＡＭＢＣリフレッシュを定期的にのみ送ることが可能であり、この場合、各メッセージは、過去の期間中のＡＭＢＣ変更を集約する。他の選択肢として、ＡＭＢＣリフレッシュは、各移動エンティティにコピーを送る代わりに、ＡＭＢＣリフレッシュメッセージをブロードキャス又はマルチキャストするために、“ルートＭＲ到達可能プレフィクス”宣言を拡張することによって実現される。多数の集合体ツリーの場合、移動エンティティは、定期的に更新される各ルート移動エンティティ用のＡＭＢＣを有する。発信元ノードにサービスを提供する移動エンティティは、これによって、図５において説明した所定のアルゴリズムに基づき、そのＡＭＢＣを用いて、それ自体から宛先アドレスへの最適経路を演算する。
【００６１】
一旦、移動エンティティにおいて最適経路が演算されると、パケットが、多重カプセル又はルーティングヘッダを伴う単一カプセルを用いて、この経路に沿ってルーティングされて、自律モードルーティングが、自律モード結合キャッシュを用いる移動エンティティの部分によって可能になる（ステップ６１０）。しかしながら、経路上の後続の移動エンティティが、再度、パケット用の最適経路を演算する可能性がある。これを回避するために、経路を決定するために用いられたＡＭＢＣに対応するルート移動エンティティのアドレスを含む新しいルート移動ルータアドレス（ＲＭＲＡ）宛先の選択肢が、パケットに置かれる。ＲＭＲＡ宛先の選択肢は、単一カプセルがルーティングヘッダと共に用いられ、経路に沿う全ての中間移動エンティティに対してそれが可視であるようにする場合、ルーティングヘッダの前に置かれる。ＲＭＲＡ宛先の選択肢と共にパケットを受信すると、経路中の後続の移動エンティティは、パケット用の最適経路を（ＡＭＢＣに基づき）演算しようとせずにルーティングヘッダを処理した後、パケットが最終的に宛先アドレスに達し得るように、単にパケットを次の移動エンティティに転送する。ＲＭＲＡ宛先の選択肢にルート移動装置アドレスを含むことは、選択肢である。経路に沿った中間移動エンティティは、それを用いて、次ホップに達するために、どの外部インターフェイスを通ってパケットを転送すべきか決定される（次ホップアドレスが、中間移動エンティティのプレフィクスに合致しなければ、この場合、パケットは、内部インターフェイスを介して送られる）。このように含むことは、中間移動エンティティが、この決定を行うための他の手段（例えば、そのルーティングテーブル）を有し得るため、選択肢である。
【００６２】
次に、図７において、複数の階層型移動ネットワークにおいてルート移動エンティティによって他の移動エンティティにルーティング情報を配信するための“受動的プッシュ”手法を示すフロー図を、本発明の実施形態に基づき示す。受動的プッシュ手法では、複数の階層型移動ネットワークにおける移動エンティティは、移動エンティティから宛先アドレス側への最適経路を含むキャッシュを維持する。キャッシュは、自律モード発信元ルートキャッシュ（ＡＭＳＲＣ）と呼ばれる。ＡＭＳＲＣの入力項目は、宛先アドレス、宛先アドレス側への最適経路、及び寿命値を含む。ルート移動エンティティは、ＡＭＳＲリフレッシュメッセージを複数の階層型移動ネットワークにおける移動エンティティに送り、移動エンティティは、これを用いて、そのＡＭＳＲＣをメッセージに含まれる情報で更新される。
【００６３】
受動的プッシュモードでは、宛先アドレスに送られなければならないパケットの発信元にサービスを提供する移動エンティティによって、パケットは、ルート移動エンティティ側に通過し、ルート移動エンティティで受信される（ステップ７０５）。通過したパケットを受信すると、ルート移動エンティティそれ自体は、その自律モード結合キャッシュを用いて、図５において説明した所定の方法により、発信元にサービスを提供する移動エンティティから宛先アドレスへの最適経路を演算する（ステップ７１０）。ルート移動エンティティは、ＡＭＳＲリフレッシュメッセージを用いて、宛先に関連する演算された最適経路を寿命と共に、発信元にサービスを提供する移動エンティティに送る。宛先アドレスと経路との間の関連付けは、移動エンティティのＡＭＳＲＣに記憶されることにより、多重カプセル及びルーティングヘッダが含まれる単一カプセルの内の１つを用いて、ノードにサービスを提供する移動エンティティによるノードから宛先アドレスへの後続のパケットのルーティングが可能になる（ステップ７１５）。
【００６４】
幾つかの移動エンティティが複数の階層型移動ネットワークを離れることにより、移動エンティティのＡＭＳＲＣにおける幾つかの登録項目は、時間経過に伴い陳腐化する。本発明の一実施形態によれば、宛先到達不可通知は、パケットを更にルーティングできない経路中の中間移動エンティティによって、発信元ノードにサービスを提供する移動エンティティに送られる。通知を受信すると、到着不可能な経路に対応するＡＭＲＳＣ入力項目は、廃棄される。本発明の一実施形態によれば、宛先アドレスにサービスを提供する移動エンティティから発信元アドレスへの逆の経路が、図５において説明した所定の方法に基づき、ルート移動エンティティによって演算される。そして、この逆の経路は、宛先にサービスを提供する移動エンティティに送られる。逆の経路を移動エンティティに送ると、最適化された経路に沿って宛先から発信元に逆のパケットを送るのに必要な時間が大幅に低減される。
【００６５】
次に、図８において、複数の階層型移動ネットワークにおいてルート移動エンティティによって他の移動エンティティにルーティング情報を配信するための“受動的プル”手法を示すフロー図を、本発明の実施形態に基づき示す。受動的プル手法では、ルート移動エンティティは、発信元ノードにサービスを提供する移動エンティティから新しいＡＭＳＲ要求メッセージを受信して、宛先アドレス側の経路、理想的には最適経路を決定する（ステップ８０５）。そして、ルート移動エンティティは、その自律モード結合キャッシュを用いて、図５において説明した所定の方法に基づき、要求側移動エンティティから宛先アドレスへの経路、理想的には最適経路を決定し（ステップ８１０）、多重カプセル及びルーティングヘッダが含まれる単一カプセルの内の１つを用いて、決定された経路を要求側移動エンティティに伝達し、要求側移動エンティティによる宛先アドレスへのパケットの自律モードルーティングを可能にする（ステップ８１５）。ステップ８０５において移動エンティティによって送られる要求メッセージは、ＡＭＳＲ要求メッセージであり、ＡＭＳＲリフレッシュメッセージを送るようにルート移動エンティティに要求する。ＡＭＳＲ要求メッセージに応じて、ルート移動エンティティは、経路を決定し、ＡＭＳＲリフレッシュメッセージにおいて要求側移動エンティティにそれを送る。従って、この決定は、複数の階層型移動ネットワークにおける移動エンティティが、ルート移動エンティティに宛先アドレス側の経路を要求する時にのみ、ルート移動エンティティによって行われる。
【００６６】
次に、図９において、複数の階層型移動ネットワークにおいてパケットをルーティングするための集中型の手法を示すフロー図を、本発明の実施形態に基づき示す。移動エンティティ、例えば、移動ノード又は移動ノードにサービスを提供する移動ルータは、複数の階層型移動ネットワーク内にルート移動エンティティを発見する（ステップ９０５）。ルート移動エンティティを発見すると、ノードにサービスを提供する移動エンティティは、ルーティング情報を含む登録要求（例えば、結合更新）をルート移動エンティティに伝達し、ルート移動エンティティは、ルート移動エンティティ結合キャッシュを生成することが可能になる（ステップ９１０）。各登録要求を含むルーティング情報は、移動エンティティが移動ルータ（ＭＲ）であれば、少なくとも気付アドレス及び移動ネットワークプレフィクスを含み、また、移動エンティティが移動ノード（ＭＮ）であれば、気付アドレス及びホームアドレスを含む。そして、ノードにサービスを提供する移動エンティティは、ルート移動エンティティへの宛先アドレスを含むパケットをルーティングし、その結合キャッシュを用いて、宛先アドレスへのルート移動エンティティによるパケットの自律モードルーティングができるようにする（ステップ９１５）。
【００６７】
次に、図１０において、複数の階層型移動ネットワークの少なくとも一部において、ルーティング情報を配信するための半集中型の手法を示すフロー図を、本発明の実施形態に基づき示す。半集中型手法は、複数の階層型移動ネットワーク内におけるルーティング手順を更に最適化するために用いられる。複数の階層型移動ネットワークに属する各移動エンティティは、それ自体の後にあるトポロジーの概観を得る。もっと正確に言えば、複数の階層型移動ネットワークにおける各移動エンティティは、それ自体の下で階層化されている全ての移動エンティティ（及びそれらのプレフィクス）を知る。このことは、移動エンティティが、ルート移動エンティティに結合更新を送る際、移動エンティティの結合更新（そのプレフィクスをそのＣｏＡにマッピングすること）を、移動エンティティからルート移動エンティティへの経路上にある中間移動エンティティが取得できるようにすることによって達成される。
【００６８】
一実施形態において、下位移動エンティティ（移動ノード又は移動ルータ）からルートＭＲへの経路中にある各中間移動ルータは、ルートＭＲに対応する宛先アドレスを含み、また更に、下位移動エンティティに対応するルーティング情報を含む下位移動エンティティからの登録要求（例えば、結合更新）を受信する（ステップ１００５）。上記したように、下位移動エンティティは、下位ＭＲ、例えば、下位ＮＥＭＯの移動ルータであってよい。下位移動エンティティに対応するルーティング情報は、各中間移動ルータによって抽出される（ステップ１０１０）。ルーティング情報を抽出した後、受信された登録要求は、ルートＭＲにルーティングされる（ステップ１０１５）。中間移動ルータは、複数の階層型移動ネットワーク（下位ＮＥＭＯ）内における自律モードルーティングを可能にするための第２結合キャッシュを生成する（ステップ１０２０）。従って、下位移動エンティティからルートＭＲへの経路上の各中間移動ルータは、前記下位移動エンティティ用の結合キャッシュ入力項目を生成又は更新しており、この入力項目には、下位移動エンティティが移動ルータであれば、少なくとも下位移動エンティティプレフィクス及び気付アドレスを含み、また、下位移動エンティティが移動ノードであれば、ホームアドレス及び気付アドレスを含む。
【００６９】
複数の階層型移動ネットワークにおける各移動ルータに構築された結合キャッシュは、移動ルータ下の各下位移動エンティティ（移動ノード又は移動ネットワーク）用の入力項目を含んでおり、移動ルータによって用いられ、複数の階層型移動ネットワーク内において、最適化された経路に沿って任意のパケットがルーティングされる。所定の宛先アドレスに宛てられたパケットをルーティングする必要がある移動ルータは、宛先アドレスが移動ルータのプレフィクスに合致すれば、パケットを宛先に直接転送する。そうでなければ、移動ルータは、その結合キャッシュを用いて、宛先アドレスが、それ自体の下の階層型移動エンティティの組に属するかどうか、例えば、宛先アドレスが、その結合キャッシュにおける登録項目の内の１つに合致するかどうか判断する。そうである場合、移動ルータは、２つのやり方の内の１つを用いて、下流に向けてパケットを宛先にルーティングする。
【００７０】
第１の実施形態において、移動ルータは、その結合キャッシュの繰り返し解析を用いて、それ自体から宛先アドレスへの最適経路を演算し、多重カプセル又はルーティングヘッダを伴う単一カプセルの内の１つを用いて、この経路に沿ってパケットをルーティングする。他の実施形態において、移動ルータは、宛先に至る下流経路上の次のホップ移動ルータにパケットを（通常、ＩＰトンネルを用いて）転送するだけであり、次のホップ移動ルータは、それ自体の結合キャッシュに基づき、パケットをルーティングできる。最後に、宛先アドレスが、移動ルータ結合キャッシュに合致しない場合、移動ルータは、ルートＭＲに至る経路上の次のホップ移動ルータ側へ上流に向けてパケットを転送する。
【００７１】
本発明の一実施形態によれば、移動ルータが、多数の外部インターフェイスを有し、その結果、多数の上流ルートＭＲに接続し得る場面が存在することがある。また、移動ネットワークが、幾つかの移動ルータによってサービスが提供される時、それら各々が、異なる上流ルートＭＲに接続される場面が存在することがある。一般的に、多数の外部インターフェイスを備えた移動ネットワーク並びにそれに接続されたいずれか他の移動ネットワークは、潜在的に、異なるルート移動エンティティによってサービスが提供される多数の集合体ツリーの一部である。
【００７２】
図１１において、複数の階層型移動ネットワーク内における複数のルート移動エンティティに属するルート移動エンティティを選択する方法を示すフロー図を、本発明の実施形態に基づき示す。異なるルートＭＲのアドレスを発見するために、本発明によって、移動エンティティ、例えば、移動ルータは、その内部インターフェイス上でそれが送る幾つかのＲＭＲＡの選択肢をルータ広告（ＲＡ）に含んで、その外部インターフェイス上でそれが受信する全てのＲＭＲＡの選択肢を広告する。従って、複数の階層型移動ネットワークに属する移動エンティティは、複数の階層型移動ネットワーク内における少なくともルート移動エンティティ・アドレスを含むＲＡを受信する（ステップ１１０５）。上流ＲＭＲＡの選択肢は、異なる移動エンティティ外部インターフェイスを介して、又は同じ移動エンティティ内部インターフェイスを介するが異なる上流移動エンティティからのＲＡメッセージにおいて、又は同じ移動エンティティ内部インターフェイスを介して及び同じＲＡメッセージにおいて、受信される。
【００７３】
ＲＭＲＡの選択肢を受信すると、移動エンティティは、ルート移動エンティティのアドレスを抽出する（ステップ１１１０）。そして、移動エンティティは、複数のルート移動エンティティに対応するルート移動エンティティリスト（本明細書では、ルート移動ルータリスト（ＲＭＲリスト）とも称する）を生成する。各ルート移動エンティティに対応する入力項目は、一般的に、ＲＭＲリストを含む（ステップ１１１５）。ＲＭＲリストの各入力項目は、通常、少なくともルート移動エンティティ・アドレスを含み、また、理想的には、次ホップ移動エンティティ・アドレス、この次ホップ移動エンティティ側の移動エンティティの外部インターフェイス、及びルート移動エンティティ用の新しいＲＭＲＡの選択肢が受信される度にリフレッシュされる入力項目に関連する寿命を含む。次ホップ移動エンティティ側の外部インターフェイスは、それを介して、ルート移動エンティティ用のＲＭＲＡの選択肢が受信されたものである。
【００７４】
一実施形態において、“ルートＭＲ到達可能プレフィクス”宣言が用いられる場合、入力項目も、複数の階層型移動ネットワーク内における少なくとも１つの他の移動エンティティに対応する少なくとも１つの到達可能プレフィクスを含むルート移動エンティティ用の到達可能プレフィクスリストを含む（ステップ１１２０）。元のルート移動エンティティ入力項目は、複数の階層型移動ネットワーク内においてパケットをルーティングするための複数のルート移動エンティティの内の１つを選択できるようにするために、少なくとも１つの到達可能プレフィクスを含むように修正する（ステップ１１２５）。複数の階層型移動ネットワークのトポロジーに応じて、同じルート移動エンティティ及び異なる次ホップ移動エンティティの場合の幾つかのＲＭＲＡの選択肢が、所定の移動エンティティによって受信されることが起こり得る。この問題は、例えば、好適な次ホップ移動エンティティの順序付けしたリスト又はＲＭＲＡの選択肢に設定される優先順位フラグを予め構成することによって処理される。
【００７５】
多数の集合体ツリーに属する移動エンティティは、それらの内部インターフェイスを介して、その各ルート移動エンティティにＢＵを送る。各ルート移動エンティティにＢＵを送る際、移動エンティティのＭＮＰは、外部インターフェイスに構成された気付アドレスに結合する。移動エンティティは、発信パケットをルーティングする必要がある場合、これらのルート移動エンティティのどれを用いて、パケットを送ることができるか決定する。移動エンティティによって実現されるルーティング方法論は、上記したように、ルート移動エンティティ側へのパケットの移動エンティティルーティングを単純に一般化したものであってよく、また、後の選択肢が用いられる場合、ＡＭＤＵＣ又は“到達可能プレフィクスリスト”に依存する。
【００７６】
複数のルート移動エンティティに属するルート移動エンティティにパケットをルーティングする場合、パケットの発信元にサービスを提供する移動エンティティは、最初に、移動エンティティＲＭＲリストが空であるかどうかチェックする。リストが空である場合、既定モードにより、パケットをルーティングする。例えば、そのホームエージェント（ＨＡ）を介してパケットを通す。ＲＭＲリストが空でない（少なくとも１つの入力項目を有する）場合、移動エンティティは、宛先アドレスが、ＲＭＲリストに記載されたルート移動エンティティの内の１つと同じかどうかチェックする。宛先アドレスが、ＲＭＲリスト上のルート移動エンティティ・アドレスの内の１つに合致する場合、移動エンティティは、ＲＭＲリスト中のルート移動エンティティに関連する移動エンティティの外部インターフェイスを介して、そのルート移動エンティティ側の次ホップアドレスにパケットを通す。宛先アドレスが、ＲＭＲリスト上のどのルート移動エンティティ・アドレスにも合致しない場合、移動エンティティは、そのルート移動エンティティとして、ＲＭＲリスト中の最初のルート移動エンティティを選択する。
【００７７】
次に、移動エンティティは、“到達可能ルートＭＲプレフィクス”がルート移動エンティティによって用いられていない場合に備えて、宛先アドレスが、ルート移動エンティティ用のＡＭＤＵＣ（自律モード宛先到着不可能キャッシュ）にリスト化されているかどうかチェックする。宛先アドレスがＡＭＤＵＣに存在する場合、対応するルート移動エンティティは、パケットを宛先アドレスにルーティングするために用いることができず、このため、移動エンティティは、ＲＭＲリストにある次のルート移動エンティティを選択して、それを宛先アドレスに用い得るかどうか判断する。移動エンティティは、ＲＭＲリストの全てのルート移動エンティティがなくなるまで、この処理を継続する。この処理中、移動エンティティは、ルート移動エンティティのＡＭＤＵＣにリスト化されていない宛先アドレスを見つけた場合、パケットを宛先アドレスに向けて通し、そのルート移動エンティティに宛てる。こうして、パケットは通過し、ＲＭＲリストのそのルート移動エンティティに関連する外部インターフェイスを介して、ルート移動エンティティ側の次ホップアドレスに至る。全てのルート移動エンティティが試みられると、移動エンティティは、既定モードに従ってパケットをルーティングする。
【００７８】
“ルートＭＲ到達可能プレフィクス”が、ルート移動エンティティによって用いられる場合、移動エンティティは、ＡＭＤＵＣを用いる代わりに、そのＲＭＲリストに列記された各ルート移動エンティティの“ルートＭＲ到達可能プレフィクス”に宛先アドレスがあるかどうかチェックする。移動エンティティは、上記した同じ手順を用いて、宛先アドレスを含む“ルートＭＲ到達可能プレフィクス”を有するルート移動エンティティ側にパケットをルーティングする。そのようなルート移動エンティティが存在しない場合、移動エンティティは、既定モードにより、例えば、そのホームエージェントを介してパケットをルーティングする。
【００７９】
図１２において、複数の階層型移動ネットワーク内において自律モードルーティングを実行する装置１２００のブロック図を、本発明の実施形態に基づき示す。装置１２００は、大ざっぱに言うと、メモリ１２１０に結合されたプロセッサ１２０５を含む。複数の階層型移動ネットワークにおいて自律モードルーティングを可能にするようにプログラムされた実行可能なソフトウェア１２１５が、メモリ１２１０に記憶されている。このソフトウェアは、複数の階層型移動ネットワークにおけるルート移動エンティティを宣言し、引き続き、複数の階層型移動ネットワークに参加する様々な移動エンティティから登録要求を受信するようにプログラムされている。そして、ルート移動エンティティは、受信された登録要求を用いて、結合キャッシュを生成する。ルーティングのための自律モードが可能なように、どの移動エンティティでも複数の階層型移動ネットワークにおけるルート移動エンティティであり得ることから、ソフトウェアは、複数の階層型移動ネットワークの一部である全ての移動エンティティに常駐し得ることを当業者は認識されるであろう。
【００８０】
上記明細書において、本発明の特定の実施形態について記載した。しかしながら、当業者が理解されるように、以下の請求項に記載した本発明の範囲から逸脱することなく、様々な修正及び変更を行い得る。従って、明細書及び図は、限定的でなく例示的であると見なすべきものであり、また、そのような全ての修正は、本発明の範囲内に含まれるものとする。恩恵、利点、問題の解決策、及び何らかの恩恵、利点、又は解決策を生じさせる又はより顕著にさせるあらゆる要素（１つ又は複数）は、全ての請求項の決定的な、必要な、若しくは不可欠な特徴又は要素として解釈してはならない。本発明は、添付の請求項によってのみ規定され、本出願の係属中になされるあらゆる補正や発効時のそれら請求項の全ての等価なものを含む。
【図面の簡単な説明】
【００８１】
【図１】本発明の実施形態を実現する複数の階層型移動ネットワークを全体的に示すブロック図。
【図２】本発明の実施形態に基づく複数の階層型移動ネットワークの一部を形成する移動エンティティと隣接移動エンティティとの間の接続を示す図。
【図３】本発明の実施形態に基づく複数の階層型移動ネットワークを形成する移動装置間の自律モードルーティングを可能にする方法を示すフロー図。
【図４】本発明の実施形態に基づく複数の階層型移動体に属するノードから宛先アドレスにパケットをルーティングする方法を示すフロー図。
【図５】本発明の実施形態に基づく、パケットを生成するノードにサービスを提供する移動エンティティとパケット用の宛先アドレスとの間の最適経路を決定するための所定の方法を示すフロー図。
【図６】本発明の実施形態に基づく、複数の階層型移動ネットワークにおけるルート移動エンティティによってルーティング情報を他の移動エンティティに配信するための“能動的プッシュ”手法を示すフロー図。
【図７】本発明の実施形態に基づく、複数の階層型移動ネットワークにおいて、ルート移動エンティティによってルーティング情報を他の移動エンティティに配信するための“受動的プッシュ”手法を示すフロー図。
【図８】本発明の実施形態に基づく、複数の階層型移動ネットワークにおいて、ルート移動エンティティによってルーティング情報を他の移動エンティティに配信するための“受動的プル”手法を示すフロー図。
【図９】本発明の実施形態に基づく、複数の階層型移動ネットワークにおいて、情報をルーティングするための方法を示すフロー図。
【図１０】本発明の実施形態に基づく、複数の階層型移動ネットワークにおいてルーティング情報を配信するための“半集中型”手法を示すフロー図。
【図１１】本発明の実施形態に基づく、複数の階層型移動ネットワーク内において、複数のルート移動エンティティに属するルート移動エンティティを選択する方法を示すフロー図。
【図１２】本発明の実施形態に基づく、複数の階層型移動ネットワーク内において、自律モードルーティングを実行するための装置を示すブロック図。
【図１】
2009514272.tif 000003
【図２】
2009514272.tif 000004
【図３】
2009514272.tif 000005
【図４】
2009514272.tif 000006
【図５】
2009514272.tif 000007
【図６】
2009514272.tif 000008
【図７】
2009514272.tif 000009
【図８】
2009514272.tif 000010
【図９】
2009514272.tif 000011
【図１０】
2009514272.tif 000012
【図１１】
2009514272.tif 000013
【図１２】
2009514272.tif 000014