(57)【要約】  パターンベースのネットワーク管理方法及びシステムが、無線移動体ネットワークで使用される。エクスプローラメッセージ（Ｅ１、Ｅ２、Ｅ３）が、動的ネットワークを介して連続的に転送され、任意の動作リンクが検証される。この検証は、そのエクスプローラメッセージ（Ｅ１、Ｅ２、Ｅ３）を受信するノードが、送信元ノードへ返信される受信の応答確認をすることに基づいていることが好ましい。送信ノードは、これによって、その時点でどのノードに到達可能であるかを識別することができる。受信ノードは、そのエクスプローラメッセージ（Ｅ１、Ｅ２、Ｅ３）へのリプライを行い、連続的にそのリプライ（Ｒ１、Ｒ２、Ｒ３）をオリジナルノードへ返信する。このリプライは、オリジナルノードで編纂される。一実施形態では、リプライの編纂は、ネットワーク管理動作の基礎を形成することになる。別の実施形態では、エクスプローラメッセージ自身が、少なくとも１つの受信ノードで、ネットワーク管理動作に対する基礎を形成することになり、また、リプライは、そのような動作の結果についての情報を含んでいることが好ましい。
2008519482.tif 000002
【特許請求の範囲】
【請求項１】
動的通信ネットワーク（１）のネットワーク管理方法であって、
前記動的通信ネットワーク（１）を介して、第１ノード（１０Ａ、１０Ｈ）から連続的に制御メッセージ（Ｅ、Ｅ１−３）を伝送する工程（２１０）と、
前記伝送する工程（２１０）とともに、前記動的通信ネットワーク（１）の動作リンク（２０）を検証する工程（２２０）と、
前記制御メッセージ（Ｅ１−３）に基づいて、前記動的通信ネットワーク（１）の少なくとも１つのノード（１０、１０Ｂ−Ｇ、１０Ｉ−Ｑ）でネットワーク管理動作を実行する工程（２３０）と、
前記動的通信ネットワーク（１）のノード（１０、１０Ａ−Ｑ）で、前記制御メッセージ（Ｅ、Ｅ１−３）におけるリプライメッセージ（Ｒ１−３）を生成する工程（２４０）と、
前記動的通信ネットワーク（１）を介して、前記動作リンク（２０）の少なくとも１つにリプライメッセージ（Ｒ１−Ｒ３）を送信する工程（５２０）と、
前記第１ノード（１０Ａ、１０Ｈ）によって受信されるリプライメッセージ（Ｒ１−Ｒ３）を編纂する工程（２６０）とを備え、
前記伝送する工程は、
前記制御メッセージ（Ｅ、Ｅ１−３）を、少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）へ配信する工程と、
前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）における第１の時間に対して、前記制御メッセージ（Ｅ１−３）の受信の応答として、前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）から前記制御メッセージ（Ｅ１−３）を、前記動的通信ネットワーク（１）の少なくとも１つの次のノード（１０Ｄ、１０Ｇ、１０Ｎ−１０Ｑ）へ転送する工程とを備え、
前記リプライメッセージ（Ｒ１−３）は、存在する場合には、前記実行する工程（２３０）についての情報及びその結果についての情報の少なくとも一方を含んでいる
ことを特徴とするネットワーク管理方法。
【請求項２】
前記制御メッセージ（Ｅ、Ｅ１−３）を提供するリンク（２０Ａ）が中断されている場合、新規ルートに沿ってリプライメッセージ（Ｒ１−３）を送信する工程を更に備える
ことを特徴とする請求項１に記載のネットワーク管理方法。
【請求項３】
前記検証する工程（２２０）は、前記制御メッセージ（Ｅ、Ｅ１−３）に関係する応答確認メッセージ（Ａ１−２）の受信に基づいている
ことを特徴とする請求項１または２に記載のネットワーク管理方法。
【請求項４】
前記検証する工程（２２０）は、
前記制御メッセージ（Ｅ、Ｅ１−３）の受信に応じて、前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）から前記第１ノード（１０Ａ、１０Ｈ）へ、第１応答確認メッセージ（Ａ１−２）を送信する工程と、
前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）から、前記第１ノード（１０Ａ、１０Ｈ）で第１応答確認メッセージ（Ａ１−２）を受信する工程と
を備えることを特徴とする請求項３に記載のネットワーク管理方法。
【請求項５】
前記生成する工程（２４０）は、前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）でリプライメッセージ（Ｒ１）を生成する工程を備え、
前記送信する工程（２５０）は、前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）で生成された前記リプライメッセージ（Ｒ１）を前記第１ノード（１０Ａ、１０Ｈ）へ送信する工程を備える
ことを特徴とする請求項３に記載のネットワーク管理方法。
【請求項６】
前記生成する工程（２４０）は、前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）における第２あるいは次の時間で前記制御メッセージ（Ｅ１−３）の受信の応答として、該少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）で実行される
ことを特徴とする請求項５に記載のネットワーク管理方法。
【請求項７】
前記応答確認メッセージ（Ａ１−２）は、前記制御メッセージを前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）に提供するノードへ返信される、転送された制御メッセージによって構成される
ことを特徴とする請求項３または４に記載のネットワーク管理方法。
【請求項８】
前記検証する工程は、
前記転送された制御メッセージ（Ｅ２、Ｅ３）の受信に応じて、前記少なくとも１つの次のノード（１０Ｄ、１０Ｇ、１０Ｎ−Ｑ）から前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）へ、第１応答確認メッセージ（Ａ１−２）を送信する工程と、
前記少なくとも１つの次のノード（１０Ｄ、１０Ｇ、１０Ｎ−Ｑ）から、第１応答確認メッセージ（Ａ２）を、前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）で受信する工程と
を備えることを特徴とする請求項７に記載のネットワーク管理方法。
【請求項９】
前記少なくとも１つの次のノード（１０Ｄ、１０Ｇ、１０Ｎ−Ｑ）からの前記第１応答確認メッセージ（Ａ２）は、転送された制御メッセージによって構成される
ことを特徴とする請求項８に記載のネットワーク管理方法。
【請求項１０】
前記生成する工程（２４０）は、前記少なくとも１つの次のノード（１０Ｄ、１０Ｇ、１０Ｎ−Ｑ）でリプライメッセージ（Ｒ２）を生成する工程を備え、
前記送信する工程（２５０）は、前記少なくとも１つの次のノード（１０Ｄ、１０Ｇ、１０Ｎ−Ｑ）で生成された前記リプライメッセージ（Ｒ２）を前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）へ送信する工程を備える
ことを特徴とする請求項１に記載のネットワーク管理方法。
【請求項１１】
前記生成する工程（２４０）は、第１応答確認メッセージ（Ａ２）を前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）に提供するノードのすべてから、リプライメッセージ（Ｒ２）が受信される場合に、前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）で実行される
ことを特徴とする請求項１０に記載のネットワーク管理方法。
【請求項１２】
前記生成する工程（２４０）は、第１応答確認メッセージ（Ａ２）を前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）に提供するノードのすべてからリプライメッセージ（Ｒ２）が受信されない場合の、前記転送する工程の後の第１のタイムアウト期間に、前記少なくとも１つの第２ノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）で実行される
ことを特徴とする請求項１０または１１に記載のネットワーク管理方法。
【請求項１３】
前記転送する工程、前記第１応答確認メッセージ（Ａ１−３）を送信する工程、前記第１リプライメッセージを受信する工程、前記リプライメッセージを生成する工程及び前記リプライメッセージを送信する工程の少なくとも１つの工程は、前記動的通信ネットワーク（１）を介して連続的に実行される
ことを特徴とする請求項１乃至１２のいずれか１項に記載のネットワーク管理方法。
【請求項１４】
リプライメッセージ（Ｒ１−２）がまだ生成されていない場合、前記第１応答確認メッセージ（Ａ１−２）を送信後の所定期間に、次の応答確認メッセージ（Ｓ１Ａ１−２、Ｓ２Ａ２−２）を送信する工程を更に備える
ことを特徴とする請求項１乃至１３のいずれか１項に記載のネットワーク管理方法。
【請求項１５】
前記生成する工程（２４０）と前記実行する工程（２３０）は、各第１応答確認メッセージ（Ａ１−２）あるいは次の応答確認メッセージ（Ｓ１Ａ１−２、Ｓ２Ａ２−２）の受信からの前記所定期間内に、ノードのすべてからリプライメッセージ（Ｒ１−３）が受信される場合に、実行される
ことを特徴とする請求項１４に記載のネットワーク管理方法。
【請求項１６】
第２あるいは次の時間で前記制御メッセージ（Ｅ１−３）がノードから受信されている、そのノードについての情報を記憶する工程と、
前記第１の時間で前記制御メッセージ（Ｅ１−３）を提供するリンク（２０Ａ）が中断されている場合に、第２あるいは次の時間で前記制御メッセージ（Ｅ１−３）がノードから受信されている、そのノードへの新規ルートに沿ってリプライメッセージ（Ｒ１−３）を送信する工程と
を更に備えることを特徴とする請求項１乃至１５のいずれか１項に記載のネットワーク管理方法。
【請求項１７】
前記第１の時間で前記制御メッセージ（Ｅ１−３）を提供するリンク（２０Ａ）が中断されている場合に、前記動的通信ネットワーク（１）のノードへ新規ルートリクエストメッセージを送信する工程と、
前記新規ルートリクエストメッセージを受信する前記ノードから前記新規ルートリクエストメッセージを送信する前記ノードへ、前記第１ノード（１０Ａ、１０Ｈ）への接続を確認する工程と、
前記新規ルートリクエストメッセージを受信する前記ノードを介する新規ルートに沿って、前記第１ノード（１０Ａ、１０Ｈ）へリプライメッセージ（Ｒ１−３）を送信する工程とを更に備え、
前記新規ルートリクエストメッセージは、前記新規ルートリクエストメッセージを受信するノードが前記第１ノード（１０Ａ、１０Ｈ）への接続を有しているかどうかの問い合わせを含んでいる
ことを特徴とする請求項１乃至１６のいずれか１項に記載のネットワーク管理方法。
【請求項１８】
前記新規ルートリクエストメッセージは、前記リプライメッセージ（Ｒ１−３）を含んでいる
ことを特徴とする請求項１７に記載のネットワーク管理方法。
【請求項１９】
前記新規ルートリクエストメッセージを受信する前記ノードは、前記新規ルートリクエストメッセージを送信する前記ノードから、前記制御メッセージ（Ｅ１−３）を受信しているノードである
ことを特徴とする請求項１７または１８に記載のネットワーク管理方法。
【請求項２０】
前記新規ルートリクエストメッセージを受信する前記ノードは、前記新規ルートリクエストメッセージを送信する前記ノードから、前記制御メッセージ（Ｅ１−３）を受信していないノードである
ことを特徴とする請求項１７または１８に記載のネットワーク管理方法。
【請求項２１】
前記問い合わせは、前記新規ルートリクエストメッセージを送信する前記ノード以外の他のノードから前記制御メッセージ（Ｅ１−３）を、前記新規ルートリクエストメッセージを受信している前記ノードが受信しているかどうかの調査を含んでいる
ことを特徴とする請求項１７乃至２０のいずれか１項に記載のネットワーク管理方法。
【請求項２２】
前記伝送する工程は、パターンに従って実行される
ことを特徴とする請求項１乃至２１のいずれか１項に記載のネットワーク管理方法。
【請求項２３】
動的通信ネットワーク（１）におけるノード（１０、１０Ａ−Ｑ）であって、
前記動的通信ネットワーク（１）を介して制御メッセージ（Ｅ１−３）を連続的に伝送する手段（１２）と、
前記伝送する手段（１２）に接続されている前記動的通信ネットワーク（１）の動作リンク（２０）を検証する手段（７０）と、
前記受信された制御メッセージ（Ｅ１−３）に基づいて、ネットワーク管理動作を実行する手段（６２）と、
前記制御メッセージ（Ｅ、Ｅ１−３）におけるリプライメッセージ（Ｒ１−３）を生成する手段（５３）と、
前記動的通信ネットワーク（１）を介して、前記動作リンク（２０）の少なくとも１つにリプライメッセージ（Ｒ１−Ｒ３）を送信する手段（１２）と、
前記受信されたリプライメッセージ（Ｒ１−Ｒ３）を編纂する手段（６１）とを備え、
前記伝送する手段は、
前記制御メッセージ（Ｅ、Ｅ１−３）を、少なくとも１つの別のノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）へ配信するように構成されていて、
かつ、前記少なくとも１つの別のノード（１０、１０Ｂ、１０Ｃ、１０Ｅ、１０Ｆ、１０Ｉ−１０Ｍ）における第１の時間に対して、前記制御メッセージ（Ｅ１−３）の受信の応答として、前記受信された制御メッセージ（Ｅ１−３）を、前記動的通信ネットワーク（１）の少なくとも１つの次のノード（１０Ｄ、１０Ｇ、１０Ｎ−１０Ｑ）へ転送するように構成されていて、
前記リプライメッセージ（Ｒ１−３）は、存在する場合には、前記ネットワーク管理動作についての情報及びその結果についての情報の少なくとも一方を含んでいる
ことを特徴とするノード。
【請求項２４】
前記制御メッセージ（Ｅ１−３）を提供するリンク（２０Ａ）が中断される場合、新規ルートに沿ってリプライメッセージ（Ｒ１−３）を送信する手段（５８）を更に備える
ことを特徴とする請求項２３に記載のノード。
【請求項２５】
前記伝送する手段（１２）は、パターンメッセージを少なくとも別のノードへ配信するための手段を備え、
前記検証する手段（７０）は、
前記制御メッセージ（Ｅ１−３）の受信に応じて、前記制御メッセージ（Ｅ１−３）がノードから受信されている、そのノードへ第１応答確認メッセージ（Ａ１−２）を送信する手段（５４）と、
第１応答確認メッセージを受信する手段（５９）と
を備えることを特徴とする請求項２３または２４に記載のノード。
【請求項２６】
請求項２３乃至２５のいずれか１項に記載の少なくとも１つのノード（１０、１０Ａ−Ｑ）を備えることを特徴とする通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
技術分野
本発明は、一般的には、通信ネットワーク管理のための装置、システム及び方法に関するものであり、より詳しくは、動的ネットワークの分散管理のための装置、システム及び方法に関するものである。
【０００２】
背景
集中ネットワーク管理には、よく知られている欠点がある。これは、管理トラフィック、管理局における処理負荷、及び実行時間に関してのスケラービリティが貧弱なことである。また、集中ネットワーク管理方法は、ドメインが動的に構成される移動体無線環境においては容易に実現されない。
【０００３】
分散ネットワーク管理システムにおける分散管理方法は、例えば、非特許文献１−４で参照されるように、パターンベースの管理パラダイムに基づいて提供されている。グラフトラバーサルアルゴリズム（graph traversal algorithm）は、ネットワーク内部の管理情報の処理及び収集を制御し、調整するために使用される。ネットワーク管理者の観点からは、このアルゴリズムは、計算処理を大規模のノードのセットに渡って「拡散」あるいは分散させるための手段を提供する。この方法の重要な特徴は、この拡散及び収集のメカニズムと、実際の管理動作の制御とを分離するための機能である。このパラダイムは、２つの重要な概念：ナビゲーションパターンと収集部の整備によって達成している。前者は、分散制御を実現する一般的なグラフトラバーサルアルゴリズムを示していて、後者は、タスクを実現するために必要な計算を実現している。ナビゲーションパターンは、分散管理動作の実行のフローを制御する。これは、非同期ネットワークアルゴリズムによって説明され、これは、自身の複雑性及びスケラービリティ特性に対する解析を実行することができる。
【０００４】
パターンベースの管理の主要な利点は、それが、タスクの制御と、自身のフロー制御とを分離し、スケーラブル管理システムの構築を可能にし、かつ動的環境における管理を容易にすることである。
【０００５】
今までのところ、パターンベースの管理対象は、ネットワーク内のノード間で静的リンクを有する固定有線ネットワークを想定している。これは、ノード自身がどんな近隣ノードを有していて、どんなリンクがパターンを配信していて、かつどんなリンクが返信に対するリプライを期待しているかを、ノードが知っていることを意味するものである。また、この静的環境は高い信頼性があり、パケットが損失することはほとんどなく、ノードが停止あるいは切断することは決してなく、そして、ネットワーク内の移動性（モビリティ）も存在しない。ここで、整備されているパターンは、今までのところ、エラーのない環境を想定している。いくつかの変形例では、パターンが発行されている間にノードあるいはリンクが故障した場合のデッドロックに捕われないことを可能にするエコーパターンを提案している。これらは、２種類の耐性があるエコーパターンを提案している。スキップエコーパターンは、ノードが自身の近隣ノードの１つが停止することを通知する場合に、ノードリスト上の到来する応答を期待するノードから、その停止するノードを除くこと以外は、通常のエコーアルゴリズムとして動作する。ウェイトエコーパターンは、スキップエコーパターンに加えて、パターンが近隣ノード内で自身のタスクを完了する前に、ノードがアクティブ状態を返信する場合には、インアクティブ状態として以前に登録されているノードからの入力を受け付ける。３つ目の方法には、各ノードにタイマを設定することであり、このパターンは、そのタイマが満了するまで自身の近隣ノードからの入力を待機する。しかしながら、この動作も、有線の静的ネットワークを想定している。
【０００６】
一方、移動体及び無線ネットワークは、極めて動的な環境を想定しているものであり、この環境では、周辺を移動するノード及びネットワークと、アドホックを構成しかつ解消するネットワークと、現状の要件及び利用可能性に依存して、有線及び無線の複数のアクセス技術を選択するネットワークを有している。この環境は、パターンをこのような環境で使用可能にするために、多くの新規な要件を使用することになるパターンに課している。
【０００７】
【非特許文献１】ケイ．エス．リム及びアール．スタドラー：「パターンベース管理プログラムの開発」、第４回ＩＦＩＰ／ＩＥＥＥ国際会議、マルチメディアネットワークサービス（ＭＭＮＳ’０１）の管理、イリノイ州、シカゴ、２００１年８月／１１月、３４５−３５８ページ（K.S. Lim and R. Stadler: "Developing pattern-based management programs", 4th IFIP/ IEEE International Conference on Management of Multimedia and Network Services (MMNS'01), Chicago, Illinois, October/ November 2001, pp. 345-358）
【非特許文献２】ケイ．エス．リム及びアール．スタドラー：「分散ネットワーク管理」、ネットワークサービス管理における、ＩＥＥＥ電子議事録に提出（K.S. Lim, C. Adam and R. Stadler; "Decentralizing Network Management", submitted to IEEE electronic Transactions on Network and Service Management）
【非特許文献３】ケイ．エス．リム及びアール．スタドラー：「ウェーバー：商用ルータにおけるスケーラビリティ管理パラダイムの実現」、統合ネットワーク管理における第８回ＩＦＩＰ／ＩＥＥＥ国際シンポジウム、２４−２８、２００３年３月、コロラド州、コロラドスプリング、２００３年３月、４０９−４２４ページ（K.S. Lim and R. Stadler; "Weaver: realizing a scalable management paradigm on commodity routers", 8th IFIP/ IEEE International Symposium on Integrated Network Management , 24-28 March 2003, Colorado Springs, Colorado, March 2003, pp:409 - 424）
【非特許文献４】シー．アダム、アール．スタドラー：「ルーティング及び自己安定化用パターン」、ネットワーク動作＆管理シンポジウムの議事録（ＮＯＭＳ２００４）、韓国、ソウル、２００４年４月１９、２３日（C. Adam, R. Stadler, "Patterns for Routing and Self- Stabilization" in Proc. of Network Operations & Management Symposium (NOMS 2004), Seoul, Korea, April 19.23, 2004）
【０００８】
要約
移動体ネットワークは、極めて動的な環境を想定していて、この極めて動的な環境は、周辺を移動するノード及びネットワークと、アドホックを構成しかつ解消するネットワーク、現状の要件及び利用可能性に依存して、有線及び無線の複数のアクセス技術を選択するネットワークを伴うものである。従来技術に従うネットワーク管理に伴う一般的な問題は、移動体及び無線ネットワーク環境に対するネットワークの要件にあまり適合していないことである。
【０００９】
本発明の目的は、無線通信ネットワークにおけるネットワーク管理に対する方法、装置及びシステムを提供することである。本発明の別の目的は、移動性をサポートする通信ネットワークにおける、ネットワーク管理のための方法、装置及びシステムを提供することである。本発明の更なる目的は、動的通信ネットワークにおける、ネットワーク管理の耐性を向上することである。
【００１０】
上述の目的は、請求項に従う方法、装置及びシステムによって達成される。一般的に言えば、本発明は、パターンベースのネットワーク管理を、高頻度の動的性を伴う無線移動体ネットワークで使用することを可能にする。エクスプローラメッセージは、動的ネットワークを介して連続的に伝送される。このような伝送とともに、ネットワークの任意の動作リンクが識別される。この識別は、エクスプローラメッセージを受信するノードが、送信元ノードへ返信される受信を応答確認することに基づくことが好ましい。これによって、送信ノードは、どのノードにその時点で到達可能であるかを識別することができる。受信ノードは、エクスプローラメッセージへのリプライを行い、オリジナルノードへ連続的にリプライを返信する。別ノードからのエクスプローラメッセージのコピーを既に受信しているノードは、このエクスプローラメッセージのコピーをリプライする必要はない。このリプライは、オリジナルノードで編纂される。しかしながら、オリジナルノードで受信されるリプライは、収集フェーズ中に、他のノードによって部分的に編纂される。一実施形態では、リプライの編纂は、ネットワーク管理動作に対する基礎を形成することになる。別の実施形態では、エクスプローラメッセージ自身の内容は、受信ノードの少なくとも１つで、ネットワーク管理動作に対する基礎を形成することになる。即ち、エクスプローラメッセージによって搬送される情報は、実行対象のネットワーク管理動作を発生させることができ、そのリプライは、そのような動作の結果についての情報を含むことが好ましい。好ましくは、ノードは、すべての潜在的なノードのコピーを維持し、かつそのノードは、主要なリンクがこれ以上動作しない場合に、別のリンクを介してノードに対してリプライメッセージを送信するために、所定時間間隔でエクスプローラメッセージを受信する。
【００１１】
本実施形態では、ノードにリンクが依然として有効であるかどうかを知ることを可能にするために、任意の２つのノード間で、定期的に「キープアライブ（keep-alive）」メッセージが送信され、かつ応答確認される。また、エクスプローラメッセージが実行されている間にリンクが故障する場合、親ノードは、子ノードから出現するキープアライブメッセージを停止する時に、そのリンクを解放する。一方、子ノードは、リプライメッセージを自身の親ノードへ送信することを試行するまで、リンクの解放を実行しない可能性があるので、子ノードは、別の経路を検索することを試行することが好ましい。
【００１２】
本発明は、特定パターンに依存していない。本発明の基本概念は、通信ネットワーク環境内の使用に対して整備されている任意のパターンで使用することができる。
【００１３】
本発明の利点は、分散ネットワーク管理を実現することによる利点が、耐性のある方法で、無線移動体ネットワークでも利用可能にすることである。
【００１４】
詳細説明
本発明は、パターンベースのネットワーク管理を無線移動体環境で使用することを可能にするために、そのパターンベースのネットワーク管理に基本的な強化を施すものである。この無線移動体環境とは、ノード、リンク及びネットワークが、予測不可能な方法で接続し、切断を行う環境である。
【００１５】
図１は、無線移動体通信ネットワーク１を示していて、これは、いくつかのノード１０、１０Ａ−Ｇを備えている。各時点で、ノード１０、１０Ａ−Ｇは、リンク２０、２０Ａ−Ｃを動作させることによって互いに直接的にあるいは間接的に接続する。しかしながら、リンク２０、２０Ａ−Ｃは無線リンクであり、ネットワークノード１０、１０Ａ−Ｇは通常は移動体であるので、この状況は、ある時点で別の時点で変化し得る。今までは、無線環境で使用される分散管理処理の研究開発の作業はわずかしか向けられていない。この無線環境では、ノードは、どんな他のノードが自身の送信範囲内に存在するかはわからない可能性がある。また、動作しているリンクは、高ビットフレームあるいはリンクエラーレート（誤り率）を受ける可能性がある。また、このような動的ネットワークは、ネットワーク内及びネットワーク間の両方で、高い移動性を可能にするように構成されなければならない。
【００１６】
取り得る状況のいくつかの例を、図１を用いて説明する。ノード１０Ａとノード１０Ｂは、最初は、動作中のリンク２０Ａによって接続されている。ノード１０Ａがネットワーク管理動作を開始する状況では、メッセージは、動作中のリンク２０Ａ上を転送されることになり、ノード１０Ａは「親ノード」として見なされ、ノード１０Ｂは「子ノード」として見なされる。なんらかの理由で、リンク２０Ａが利用不可能になる場合、ネットワーク状況は変更されることになる。「子ノード」１０Ｂは、ノード１０Ｃに関しての唯一の子ノードとなり、その結果、ノード１０Ｃは、ノード１０Ａに対しては「孫ノード」となる。それでもなお、リンク障害がネットワーク管理処理中に発生する場合には、ノード１０Ａと１０Ｂ間のメッセージは、ノード１０Ｃを介して再ルーティングされなければならない。
【００１７】
別の状況では、ノード１０Ｄは、ノード１０Ｅを介して、ノード１０Ａと通信することができる。しかしながら、新規の動作リンク２０Ｂがノード１０とノード１０Ｂ間で生成される場合、ノード１０Ａとノード１０Ｄ間の通信は、これまでのように、ノード１０Ｅを介して、あるいは新規のリンク２０Ｂを使用するノード１０Ｂを介して、実行することができる。つまり、ノード１０Ａとノード１０Ｄは、それに関係するメッセージを実現することを管理しなければならず、また、同一のタスクが別のリンク上で受信されても良い。
【００１８】
更に別の状況では、ノード１０Ａは、ノード１０Ｆを介してノード１０Ｇと通信する。リンク２０Ｃに障害が発生すると、ノード１０Ｆとノード１０Ｇは一時的に孤立する。しかしながら、最終的には、ノード１０Ｆとノード１０Ｇの「島」が、矢印２５で示されるように移動すると、２４で示される位置でネットワークに再接続する。ノード１０Ａとノード１０Ｇ間の通信は再開することができるが、ここでは、完全に異なるセットのリンク上でなされることになる。
【００１９】
従来技術で示されるように、パターンベースのネットワーク管理は、実際の制御と、制御メッセージの配信とを切り離すことによって、分散ネットワーク管理を実行する有望な概念をもたらすことになる。パターンベースの管理は、移動体ネットワークの動的ネットワーク構成の環境において、接続性情報、例えば、フローパフォーマンスあるいはトラフィック統計値をほぼリアルタイムで提供するための強力な潜在能力を持っている。しかしながら、上述の状況にその概念を適用するためには、分散管理システムに、ネットワーク構成、例えば、ネットワークドメインとネットワークノード間の接続性における変更に順応することを動的に適合させることを少なくとも可能にするための手段を提供する必要がある。また、このパターンは、トポロジーの変更と接続性障害中に実行可能にするような耐性をもたせなければならない。それゆえ、本発明は、分散管理の環境において、有効なネットワーク管理を実現するための手段を提供することを目的としている。
【００２０】
本発明は、主に、固定有線ネットワークと、移動体無線ネットワーク間の主要な特徴の内の３つに関係するものである。これらの特徴は、使用されるパターンについて新規の要件を課すものである。このパターンは、耐性があるものでなくてはならず、また、無線環境と協調することを可能にしなければならず、更に、ノードとネットワークが周辺を移動する移動体環境で有効に動作しなければならない。
【００２１】
本発明の概念を視覚化するために、エコータイプパターンを、本開示では使用するようにする。しかしながら、本発明の概念は、無線移動体環境で使用される他のパターンにも適用することができる。使用することができる、非排他的な例の他のパターンには、進行波パターンと定常波パターンがある。これらは、インターネットルーティングプロトコルと、ピアツーピアネットワーク内の同位ノード間の対話とをそれぞれ更新するために使用することができる。
【００２２】
基本エコーパターンは、２つのフェーズの動作によって特徴付けられる。最初に、展開フェーズが発生する。このフェーズでは、エクスプローラメッセージ（制御メッセージ）のフローが、ネットワーク管理を開始するオリジナルノードから発生する。最初にエクスプローラメッセージを受信すると、ノードは、おそらくは、そのエクスプローラメッセージを発信したリンク以外の、ダイレクトリンクのすべてにコピーを送信し、エクスプローラメッセージで指定されるローカルネットワーク管理動作を実行する。このようなローカルネットワーク管理動作は、複雑のものとは異なるものにすることができ、また、いくつかのパラメータをできる限り簡単に読み出すようにしても良い。従前の訪問先ノードに到達するエクスプローラメッセージは、リプライメッセージの生成を誘因し、これは、エクスプローラメッセージを発信したノードへ返信される。このリプライメッセージは、エクスプローラメッセージが既に別のノードで受信されたことについてを、送信ノードに通知する。
【００２３】
エコーパターンの次のフェーズは構成フェーズである。このフェーズでは、ノードが各エクスプローラメッセージに対するリプライメッセージを受信して、送信するまで、そのノードは待機する。次に、ノードは、自身のネットワーク管理動作からの結果と、受信したリプライメッセージに含まれるものを収集し、そして、ノードは、その収集結果をリプライメッセージとともに返信する。
【００２４】
エコー時間の複雑性は、ネットワーク範囲に従って線形に増加し、これは、指数法則に従う接続性分散を伴うネットワーク（例えば、インターネット）における実行時間は高速となる。トラフィックの複雑性はネットワークリンク数に従って線形に成長し、かつこのパターンを実行することによって生成される管理トラフィックは、輻輳が発生し得るホットスポットを引き起こさずに、すべてのリンクに渡って均一に分散される。
【００２５】
無線環境、特に、移動体を伴うものは、そのような環境が使用されるパターンが協働しなければならないといういくつかの新規な要件をもたらす。固定ネットワークと比べて最も明らかに異なることの１つには、ノードが自身の送信範囲内にどんな近隣ノードがあるかを知る必要がないということである。これは、パターンメッセージの受信時に、ノードが自身のアクティブリンクのすべてにおいてこのメッセージを転送することを選択できず、かつノードは、まず、どんな他のノードが自身の送信範囲内にあるかを検出しなければならなず、更に、潜在的には、これらの他のノードの内のどのノードがメッセージの転送対象として関係しているかを検出しなければならないことを意味する。
【００２６】
このことを実行する方法の１つは、ノードに対して、最初に、近隣ノード用のリクエストメッセージをブロードキャストして、どのノードが送信範囲内にあり、かつアクティブであるかを検出するための回答を行う。これらのノードがリプライを行う場合、送信ノードは、どのノードが送信範囲内であるかがわかる。このことは、受信ノードに、リクエストメッセージの受信の応答確認を可能にすることによって実行される。この方法では、送信ノードは、どのノードにエクスプローラメッセージを送信するかがわかるので、実際のエクスプローラメッセージが連続的にこれらのノードに送信される。しかしながら、この方法の欠点は、リプライがあるタイムアウト時間内に収集されなければならず、これは、処理を著しく遅くさせる。
【００２７】
一方、本発明に従えば、送信ノードは、どの他ノードが送信範囲内にあるかの事前知識を持つことなく、エクスプローラメッセージを送信することができる。このエクスプローラメッセージを受信することができるノードは、この受信に対する応答確認を行う。オリジナルノードは、送信ノードが有効な臨機からの応答を期待している、その有効なリンクを有するノードとして、エクスプローラメッセージを応答確認することを、これらのノードに登録する。つまり、送信ノードが動作リンクについての完全な知識を持つ前に、このエクスプローラメッセージが実際に送信される。しかしながら、応答確認を編纂することによって、動的通信ネットワーク内の動作リンクが、このエクスプローラメッセージの伝送に関連して識別される。同一の原理が、通信ネットワークを介してエクスプローラメッセージを伝送する後続のステップに対しても使用されることが好ましい。
【００２８】
このエクスプローラメッセージは、このような状況では、２つの目的を持っている。１つの目的は、ネットワーク管理に関係して、取得される測定値をリクエストするノードのいくつかにメッセージを通信することである。もう１つの目的は、どの通信経路を介してエクスプローラメッセージが拡散されるかについての情報を生成することである。このような情報は、エクスプローラメッセージの送信前に利用可能である。また、少なくともエクスプローラメッセージの展開フェーズ中に、エクスプローラメッセージを連続的に拡散する際に関係するノードは、通信経路の最近接部分についての情報だけを有することなる。換言すれば、このエクスプローラメッセージは秘匿して送信される。一方、実際の通信経路はネットワーク構造によって間接的に判定され、通信経路の知識は、エクスプローラメッセージの提供に関連して連続的に収集される。エクスプローラメッセージを発信するノードは、通信経路の選択に積極的に関与する必要はない。
【００２９】
上述の概念は、図２の時系列図で示される。縦線は、異なる段階でのノードに対応する。第１ノードは、エクスプローラメッセージを発信するノードである。１つあるいはいくつかの第２ノードは、第１ノードからエクスプローラメッセージを受信する。１つあるいはいくつかの「次の」ノード群は、パターン伝送の階層構成のより下層の部分を示している。時間ｔ０で、エクスプローラメッセージＥ１は第１ノードから送信され、時間ｔ１で第２ノードによって受信される。第２ノードは、時間ｔ２で、第１ノードへ応答確認メッセージＡ１を返信し、時間ｔ３で、この応答確認メッセージＡ１は第１ノードによって受信される。ここで、第１ノードは、動作リンクを介して到達可能な第２ノードを認識する。時間ｔ２で、エクスプローラメッセージＥ２は次のノードに転送され、この次のノードは、時間ｔ３”で、エクスプローラメッセージＥ２を受信する。エクスプローラメッセージＥ１の実際の内容に依存して、エクスプローラメッセージＥ２は、エクスプローラメッセージＥ１と同一であっても良く、あるいはそれが修正されたものであっても良い。時間ｔ４で、次のノードは、エクスプローラメッセージＥ３を更なる下位層へ転送し、応答確認メッセージＡ２が第２ノードへ返信される。時間ｔ５で、第２ノードが応答確認メッセージＡ２を受信する場合、第２ノードは、次のノードへの自身の動作リンクを認識する。これが、本実施形態のエコーパターンの展開フェーズである。
【００３０】
時間ｔ６、ｔ７、ｔ８で、次のノードはエクスプローラメッセージＥ３に対するリプライメッセージＲ３を受信する。エクスプローラメッセージＥ３の受信を応答確認している、あるいはタイムアウトしているノードのすべてからリプライメッセージＲ３が受信される場合、リプライメッセージＲ３は、次のノード自身からの追加情報とともにリプライメッセージＲ２に編纂され、これは、時間ｔ１０で送信される。時間ｔ９、ｔ１１、ｔ１４で、エクスプローラメッセージＥ２に対する異なるリプライメッセージＲ２が第２ノード受信される。リプライメッセージＲ２がエクスプローラメッセージＥ２の受信を応答確認しているすべてのノードから受信される場合、リプライメッセージＲ２は編纂され、第２ノード自身の追加の情報がリプライメッセージＲ１へ追加され、これは、時間ｔ１６で送信される。第１ノードによって、エクスプローラメッセージＥ１に対する異なるリプライメッセージＲ１が時間ｔ１５、ｔ１７及びｔ２０で受信される。リプライメッセージＲ１がエクスプローラメッセージＥ１の受信を応答確認しているすべてのノードから受信される場合、リプライメッセージＲ１は最終的に編纂され、時間ｔ２１で、第１ノードは、エクスプローラメッセージの結果を評価することができる。オリジナルエクスプローラメッセージＥ１が送信された後の時間Ｔで、その評価が発生し得る。適切な場合、第１ノードは、編纂結果に基づいて、更なる必要なネットワーク管理動作を実行することができる。
【００３１】
特定の実施形態では、応答確認メッセージは、転送されたエクスプローラメッセージと同一となる。図２を参照すると、応答確認メッセージＡ１は、例えば、エクスプローラメッセージＥ２と同一となる。これが実現可能となるのは、応答確認メッセージが意図されている受信機、この場合、第１ノードが、受信したメッセージＡ１が、第１ノードがかなり最近に送信したエクスプローラメッセージＥ１と同一の関係にあることを検出することができるからである。メッセージＡ１は、明示的にあるいは暗黙的に、送信ノードについての情報を含んでいるので、これが第２ノードの１つである場合、第１ノードは、第２ノードが実際にオリジナルエクスプローラメッセージＥ１を受信していることを知っている。このことは、メッセージ生成処理を簡略化することができる。
【００３２】
通信ネットワークが動的なものであると想定されているので、エクスプローラメッセージが受信され、かつ応答確認されるが、リプライメッセージが返信される前に対応するリンクが故障しているという状況が発生し得る。このような場合、エスプローラメッセージを送信したノードは、早期の動作リンクを介して配信することができないリプライを待機する可能性がある。このリプライメッセージを送信するノードは、切断されているリンクについて分からない可能性がある。
【００３３】
このソリューションは、リプライメッセージの受信の応答確認にも適用することが好ましい。図２を参照すると、時間ｔ１１で、第２ノードがリプライメッセージＲ２を受信する場合、時間ｔ１２で、第２ノードは、リプライ応答確認メッセージＲＡ２をリプライメッセージを送信する次のノードへ返信する。この次のノードでは、ｔ１３で、リプライ応答確認メッセージＲＡ２が受信される。このリプライ応答確認メッセージＲＡ２を受信する次のノードは、リプライが受信され、かつリンクがまだ動作していることを知っている。合理的な時間内にリプライ応答確認メッセージＲＡ２が受信されない場合、次のノードは、リンクが切断していると見なして、かつそのリプライメッセージに対する代替ルートを検索することができる。このようなルーチンは、以下で更に説明する。同一のメカニズムがすべてのレベルで適用されることが好ましい。例えば、第１ノードがリプライメッセージＲ１を受信する場合、時間ｔ１８で、リプライ応答確認メッセージＲＡ１が受信される。時間ｔ１９で、対応する第２ノードは、リンクがまだ動作していることについての知識を持っているので、新規のルートに沿ってメッセージを送信するための更なる動作が実行されなければならないことはない。
【００３４】
転送されるエクスプローラメッセージを応答確認メッセージとして動作させるための方法と同様の方法で、ブロードキャストするリプライメッセージを、受信されるリプライメッセージに対する応答確認メッセージとして使用することができる。但し、リプライメッセージをブロードキャストすることによって、検出されないパケット衝突数が増加する可能性があるので、収集される情報の総数は減少することになる。また、そのメッセージを最初に生成するノードは、いずれにしても、常に、明示的な応答確認を送信しなければならない。
【００３５】
上述の処理中にリンクが故障すると、その状況を処理するためのいくつかの方法が存在し得る。リプライ応答確認メッセージを導入することによって、リプライを行うノードは、損失したリンクの認識を行うことができるかもしれないが、そのリプライを待機するノードは、損失したリンクを依然として認識できないので、デッドロックに落ち入る可能性がある。このことを解決するための基本的な方法では、リプライメッセージを待機するノードは、設定されているタイムアウト期間を持っていて、タイムアウト期間が終了すると、そのノードは、リンクが損失していると想定し、そのような状況のノードからの結果なしに処理を進めることになる。しかしながら、動作期間中にも、決定を行うことができる、あるいはリプライメッセージを生成することができまるまでの時間Ｔは長くなる、あるいは不定となる可能性があるので、遠くにあるノードからのリプライを確認することを可能にするために、そのタイムアウト期間はかなり長くなるように設定しなければならない。
【００３６】
別のソリューションは、パターンの伝送中に、ノード間で定期的に送信される、いくつかの「キープアライブ（keep-alive：存続維持）」メッセージを提供することである。このようなメッセージは、次の応答確認メッセージとして見なすことができ、また、送信ノードに、どのノードが依然としてリプライを期待しているかを追跡することを可能にする。
【００３７】
この処理は、図３Ａで示される。エクスプローラメッセージの伝送は、図２のように実行される。しかしながら、第２ノードが、時間ｔ２後の時間ＴＲで、（最初の）応答確認メッセージＡ１を送信している際に、リプライメッセージを準備していない場合は、時間ｔ２２で、次の応答確認メッセージＳ１Ａ１が第１ノードへ送信される。時間ｔ２３で、第１ノードが次の応答確認メッセージＳ１Ａ１を受信すると、第１ノードは、リンクが依然として動作していることを認識する。この処理は、ＴＲの周期で繰り返され、そうすることで、時間ｔ２４で、別の次の応答確認メッセージＳ１Ａ２が第２ノードから送信され、ｔ２５で、第１ノードに受信される。最終のリプライメッセージＲ１が返信されると、応答確認メッセージＡ１あるいは次の応答確認メッセージＳ１Ａ１、Ｓ１Ａ２の受信後の期間ＴＲ内で、それが受信される。
【００３８】
図３Ｂでは、切断しているリンクの状況がハッチング矩形Ｂによって示されている。この例では、切断しているリンクは、第２の次の応答確認メッセージＳ１Ａ２が第１ノードに到達することを阻んでしまう。応答確認メッセージＡ１あるいは次の応答確認メッセージＳ１Ａ１、Ｓ１Ａ２の受信後のＴＲ期間以降のタイムアウト期間ＴＯ、即ち、ｔ２６で、第１ノードは、第２ノードへ向かうリンクがこれ以上動作できないという結論を出すことができ、かつ結果的にリプライの評価を伴う処理に進むことができる。このタイムアウト期間ＴＯは、ＴＲより長くしなければならないが、典型的には、次の応答確認メッセージＳ１Ａ１、Ｓ１Ａ２を使用することなく、使用されなければならないタイムアウト期間よりもかなり短く設定することができる。但し、ＴＲ期間が短すぎると、通信ネットワークに、大量の次の応答確認メッセージＳ１Ａ１、Ｓ１Ａ２の負荷を与えることになる。
【００３９】
図３Ｃに示されるように、同一の方法を、各レベルのパターン伝送に適用することができる。ここで、次の応答確認メッセージＳ２Ａ１、Ｓ２Ａ２が、第（Ｎ＋１）ノードから第Ｎノードへ送信される。
【００４０】
パターンベースのネットワーク管理では、パターンは、ノードとリンクが故障している場合でさえ動作を継続しなければならず、かつ好ましくは、これらは、できる限り有効にこれらの故障を回復しなければならない。一般的には、収集される情報の量は、ノードあるいはリンクが故障する確率に伴って減少する。しかしながら、いくつかのリンクあるいはノードが故障するとしても、大量の情報が収集可能とされるべきである。パターン処理の耐性が向上すると、収集される情報の量を増加させることができる。例えば、別のノードからの情報に対するリクエストを受信しているノードは、そのノードが回答を伴うリプライを行うことを試行している場合に、リンクがこれ以上動作していないことを検出する。１つの方法は、ノードに収集されている情報に対して、ノードに別のリンク及びルートを検出させることである。
【００４１】
典型的な従来のパターンでは、ノードが、第２のあるいは次の時間で、エクスプローラメッセージと、それと同一のエクスプローラメッセージを受信する場合、そのノードは、これらの複数のエクスプローラメッセージを破棄し、かつ最初のものだけを提供する。可能であれば、そのノードは、次に、即時リプライメッセージを送信し、これは、送信ノードに、対象とするエクスプローラメッセージを既に受信していることを通知する。
【００４２】
しかしながら、本発明の実施形態に従えば、このノードは、そのノードが正常にエクスプローラメッセージに対する自身のリプライを配信するまで、暫定的なルートの情報を記憶する。故障が発生している場合、同一のエクスプローラメッセージを送信する他のノードの１つを介して、ルートの検出を支援することができる情報が存在している。エクスプローラメッセージが無視される場合、あるいはそのノードがエクスプローラメッセージの早期のコピーを既に受信していることをリプライを行っている場合でさえも、ノードは、どのノードからエクスプローラメッセージを受信しているかについてを特定の時間値の間、レジストリに保持することが好ましい。
【００４３】
もちろん、このことは、取り扱うための追加の情報を「予想外に」受信するという新規の要件をノードに課すことになる。但し、リプライは、自身を発生させるエクスプローラメッセージの識別情報と、リプライを送信するノードについての情報を含んでいる。それゆえ、リプライを「予想外に」受信するノードは、いずれにしても、どのリンクを介してリプライが到来することを期待していたかを識別することができる。
【００４４】
図４は、この状況の例示を示している。図４Ａでは、ノード１０Ｈは、エクスプローラメッセージＥを自身の近隣ノードのすべてに送信する。ノード１０Ｉ−Ｍは、図４Ｂに示されるように、そのエクスプローラメッセージＥを次のノードへ転送する。次に、ノード１０Ｍは、第２の時間でエクスプローラメッセージＥを受信し、ノード１０Ｌがノード１０Ｍからの通常のリプライを期待していないことを通知する、ノード１０ＬへダイレクトリプライメッセージＲが返信される。これについては、図４Ｃで示される。ここで、エクスプローラメッセージは、ネットワーク１の「リーフ（leafs）」に到達していて、エクスプローラメッセージに関係するタスクが実行される。「リーフ」によって、任意のメッセージを送信するための「子」をこれ以上持たないノードを示すことが意図される。これらのタスクは、ネットワーク管理動作が異なる種類の情報をリクエストする場合でさえも、ネットワーク管理動作として定義され得る。リプライの伝送中に、図４Ｄの×印で示されるように、ノード１０Ｍと１０Ｈ間のリンクが切断される。
【００４５】
図４Ｅでは、接続フェーズが開始する。ノード１０Ｊ−Ｋ、１０Ｎ−Ｑは、リプライメッセージＲを、第１エクスプローラメッセージを送信したノード１０Ｉ、１０Ｈ、１０Ｌ及び１０Ｍへ送信する。このリプライ情報は編纂され、図４Ｆに示されるように、更なるリプライメッセージＲがノード１０Ｉ及び１０Ｌからノード１０Ｈへ送信される。但し、ノード１０Ｍは、自身の第１エクスプローラメッセージをノード１０Ｈから直接受信しているので、ノード１０Ｈへ直接リプライを行うことを最初に試行する。但し、切断されているリンクが発見されると、ノード１０Ｍは、同一のエクスプローラメッセージが実際にノード１０Ｌからも受信されていることを自身のレジスタから検索する。それゆえ、ノード１０Ｍは、切断されているリンクについての追加情報を伴う、リプライメッセージＲ＊をノード１０Ｌへ送信する。そして、図４Ｇでは、ノード１０Ｌは、「予想外に」受信したリプライメッセージＲ＊を、オリジナルノード１０Ｈへ転送し、これは、ここで、切断されているリンク以外の、ネットワーク全体から情報を受信する。
【００４６】
発生し得る別の状況は、自身のアップストリームの近隣ノードがこれ以上接続可能でないことを認識し、かつそのノードが、自身のデータを送信するための別の登録されている近隣ノードがないことを認識する場合である。このような状況の問題を解決するための１つの方法は、更なるダウンストリームへデータあるいはリクエストを送信して、そのような子ノードに対して別のルートを検出させることを可能にすることである。図５は、このような状況の例を示している。このネットワークでは、ノード１０Ｐと１０Ｏ間での動作リンクが存在している。図５Ａでは、ノード１０Ｈは、エクスプローラメッセージＥをノード１０Ｉ−１０Ｍへ送信する。図５Ｂでは、ノード１０Ｉ、１０Ｌ及び１０Ｍは、そのエクスプローラメッセージＥをノード１０Ｎ−Ｑへ転送する。図５Ｃでは、ノード１０Ｏとノード１０Ｐは、そのエクスプローラメッセージＥを互いに転送し、図５Ｄでは、ノード１０Ｏとノード１０Ｐは、続けて、リプライメッセージＲを送信して、別の主要な利用可能なリプライ経路が存在していることを通知する。図５Ｅでは、リーフノード内でのリプライの伝送中に、ノード１０Ｍと１０Ｈ間のリンクが切断される。図５Ｆでは、構成フェーズが開始し、ノード１０Ｊ−Ｋ、１０Ｎ−Ｑは、リプライメッセージＲを、第１エクスプローラメッセージを送信したノード１０Ｉ、１０Ｈ、１０Ｌ及び１０Ｍへ送信する。このリプライ情報は編纂され、かつ、図５Ｇで示されるように、更なるリプライメッセージＲがノード１０Ｉと１０Ｌ乃至ノード１０Ｈへ送信される。但し、ノード１０Ｍは、自身の第１エクスプローラメッセージをノード１０Ｈから直接受信しているので、ノード１０Ｈへ直接リプライを行うことを最初に試行する。但し、切断されているリンクが発見されると、ノード１０Ｍは、任意の別の利用可能な「親」ノードが存在しているかどうかを自身のレジスタから検索する。尚、ここでは、この試行は、失敗する。
【００４７】
一方、ノード１０Ｍは、「子」ノードが任意の別の利用可能なルートを有しているかの問い合わせを行うために、リクエストメッセージＱをダウンストリームへ送信する。このリクエストメッセージＱは、リプライメッセージの情報を含んでいても良いし、あるいは本来のリクエストメッセージであっても良く、これによって、肯定回答においてはリプライ情報の提供が実行されなければならない。別の経路のダウンストリームに対するこのリクエストは、必要な場合には、いくつかのステップで処理することが好ましい場合がある。肯定回答が得られる場合には、この場合、ノード１０Ｍからノード１０Ｈへ送信されることが意図されているリプライ情報は、リプライメッセージＲ＊としてノード１０Ｐからノード１０Ｏへ送信される。これは、図５Ｈで示されるように、このリプライメッセージがオリジナルノードへ戻る別の経路を取得していることを示す特定フラグとともに送信される。図５Ｉでは、リプライメッセージＲがノード１０Ｌへ転送され、図５Ｊでは、リプライメッセージＲが最終的にノード１０Ｈへ転送される。そして、再度、すべての情報が、切断されているリンク以外から収集される。
【００４８】
通信ネットワーク内の移動性は、追加の要件をパターン処理に与える。パターンの経過中にノードが移動する可能性があり、これによって、他のノードとの新規の接続のセットアップ中に、そのノード自身といくつかのノードとの直接接続が切断される。パターンは、これらの状況と協働することが可能となるようにしなければならず、ここで、このパターンは、１つのリンクを出て、別のリンクに戻る可能性がある、あるいは、他の「パラレル（並行）」ノードとルートを介してアップストリームを通過する可能性がある。
【００４９】
このことは、送信機にリプライメッセージが返信されない状況、エクスプローラメッセージが送信されている他のリンクを介してリプライメッセージが到達する状況、ノードが任意のエクスプローラパターンを送信しないリンクを介してリプライメッセージが到達する状況それぞれを十分に切り抜けるための耐性を、上記の処理が持たなければならないことを意味している。パターンを認識できる移動性は、パターンが実行されている間、ノードあるいはネットワークが自身の接続ポイントを変更することを許容しなければならない。本発明に従うソリューションは、切断されているリンクを経験しているノードへの動作リンクを有する任意のあるいは少なくとも１つのノードへ、「新規ルート」リクエストメッセージを送信することに基づいている。新規ルートリクエストメッセージは、典型的には、新規ルートリクエストメッセージを受信するノードが、エクスプローラメッセージを最初に発信したノードとの接続を有しているかの問い合わせを含んでいる。この新規ルートリクエストメッセージは、動作リンクを持っていることを知っているノードだけに向けたものにする必要はないばかりか、「新規」ノードに向けられたものであっても良い。この問い合わせは、新規ルートリクエストメッセージを受信するノードが、任意の他のノードから対象とするエクスプローラメッセージを受信しているかどうかの調査を含んでいることが好ましい。
【００５０】
このような状況の例が、図６で示される。図６Ａでは、ノード１０Ｈは、エクスプローラメッセージＥをノード１０Ｉ−Ｍへ送信する。図６Ｂでは、ノード１０Ｉ、１０Ｌ及び１０ＭはそのエクスプローラメッセージＥをノード１０Ｎ−Ｑへ送信する。図６Ｃでは、リーフノードでのリプライの伝送中に、ノード１０Ｍと１０Ｈ間のリンクが切断される。一方で、ノード１０Ｍと１０Ｋ間の新規リンクが確立される。図６Ｄでは、構成フェーズが開始し、ノード１０Ｊ−Ｋ、１０Ｎ−ＱはリプライメッセージＲを、第１エクスプローラメッセージを送信したノード１０Ｉ、１０Ｈ、１０Ｌ及び１０Ｍへ送信する。このリプライ情報は編纂され、かつ、図６Ｅで示されるように、更なるリプライメッセージＲがノード１０Ｉ及び１０Ｌからノード１０Ｈへ送信される。但し、ノード１０Ｍは、自身の第１エクスプローラメッセージをノード１０Ｈから直接受信しているので、ノード１０Ｈへ直接リプライを行うことを最初に試行する。但し、切断されているリンクが発見されると、ノード１０Ｍは、任意の別の利用可能な「親」ノードが存在しているかを自身のレジスタから検索する。尚、ここでは、この試行は失敗する。自身の「子」ノード１０Ｐと１０Ｑへの別の経路についてのリクエストも失敗する。ノード１０Ｍは、通常の新規ルートリクエストメッセージＱを通信範囲内の任意のノードへ送信する。新規ルートリクエストメッセージＱは、対象とするエクスプローラメッセージが任意の段階で受信されているかの問い合わせを含んでいる。新規のルートリクエストメッセージＱは、本例では、新規リンクを介してノード１０Ｋ（また、ノード１０Ｐと１０Ｑにも）へ送信され、ノード１０Ｋは、エクスプローラメッセージを認識していることのリプライを行う。それゆえ、リプライメッセージＲ＊は、発信ノードへ戻る別の経路を取得するメッセージとして、このリプライメッセージをマークする特定フラグとともに、ノード１０Ｍとノード１０Ｋ（不図示）から送信される。選択的には、リプライメッセージＲは、新規ルートリクエストメッセージで直接構成することができる。そして、図６Ｆでは、ノード１０Ｋは、新規ルートリプライメッセージＲ＊をノード１０Ｈへ転送する。
【００５１】
新規ルートによる方法は、更に、発展させることができる。第１リクエストメッセージによって検出される新規ノードがない場合、子ノードは、新規ルートリクエストメッセージを次のノードへ転送することを指示され得る。別の経路が検出される場合、リプライメッセージはその経路に返信される。上述のように、いくつかの同一の回答が、エクスプローラメッセージを最初に生成しているノードに到着する可能性があるが、そのノードは、容易に、その冗長性を検出し、そのリプライの１つだけを使用することができる。
【００５２】
図７は、本発明に従う方法の実施形態の主要なステップのフロー図である。この処理は、ステップ２００で開始する。ステップ２１０で、エクスプローラメッセージが、動的通信ネットワークを介して、第１ノードから続けて伝送される。ステップ２１０は、好ましくは、部分ステップ群で構成される。ステップ２１２で、第１ノードは、エクスプローラメッセージを第２ノードへ送信する。ステップ２１４で、第２ノードは、エクスプローラメッセージを次のノードへ転送する。この連続的な伝送は、矢印２１６で示されるように、エクスプローラメッセージが意図するノードに到達するまで継続する。
【００５３】
ステップ２２０は、動的通信ネットワーク内の動作リンクを検証するステップである。これは、エクスプローラメッセージの伝送とともに実行される。また、このステップは、いくつかの部分ステップに分けられることが好ましい。ステップ２２２で、応答確認メッセージが、エクスプローラメッセージの受信への応答として送信され、ステップ２２４で、応答確認メッセージが、そのエクスプローラメッセージを送信したノードで受信され、これによって、そのノードに動作リンクについて通知する。
【００５４】
ステップ２３０で、ネットワーク管理動作が、エクスプローラメッセージを受信するノードで実行される。これは、そのような動作をそのエクスプローラメッセージがリクエストした場合である。ステップ２４０で、エクスプローラメッセージにおけるリプライメッセージが生成される。このリプライメッセージは、任意の種類及び異なる種類の少なくとも一方の種類のリクエストされたネットワーク情報が存在する場合における、ネットワーク管理動作の結果を典型的には含んでいる。典型的な情報には、例えば、プロセッサ空容量、近隣に対するリンク容量、及び様々種類のネットワーク情報がある。
【００５５】
ステップ２５０で、リプライメッセージは、動的通信ネットワークを介して動作リンク上を送信される。このステップは、好ましくは、いくつかの部分ステップを含んでいる。ステップ２５１で、任意の受信されたリプライメッセージがノード内で編纂され、そのノードからの任意の追加情報が追加される場合もある。ステップ２５２で、リプライメッセージは親ノードに送信され、この親ノードは、対応するエクスプローラメッセージを供給したものである。この処理は、矢印２５４で示されるように、動的通信ネットワークを介して繰り返される。各ステップで、「子」ノードからのリプライメッセージが編纂され、ネットワーク情報及びネットワーク管理動作結果の少なくとも一方が自身のノードから追加される。ステップ２５６で、このリプライメッセージは、エクスプローラメッセージを最初に発行しているノード、即ち、第１ノードへ送信される。
【００５６】
ステップ２６０で、このリプライメッセージは第１ノードで編纂される。ステップ２７０で、適切な場合には、その編纂結果に基づいて、更なるネットワーク管理動作の指示及び実行の少なくとも一方がなされる。この処理は、ステップ２９９で終了する。
【００５７】
本実施形態では、キープアライブ（keep-alive：存続維持）機能が、上述の原理に従って識別ステップ２２０に更に展開されている。また、本実施形態では、リンクが故障している場合に新規のルートに沿ってリプライメッセージを送信することが、上述の原理に従って送信ステップ２５０に更に展開されている。
【００５８】
図８は、本発明に従うノード１０の実施形態の主要部のブロック図である。ノード１０は、動的通信ネットワークと、例えば、インタフェース、本実施形態では、アンテナ３０を介して通信する。このノード１０は、受信機１１と送信機１２を備えている。処理部４０は、本実施形態では、本発明に対して重要な機能部群を備えている。処理部における様々な機能部群は、物理的に別々に分けられているユニットよりも、単なる機能的なユニット群として見なされるべきである。送信機１２は、メッセージ生成器５０に接続されている。このメッセージ生成器５０は、本実施形態では、エクスプローラメッセージ生成器５２、新規ルートメッセージ生成器５１、リプライメッセージ生成器５３、応答確認メッセージ生成器５４、次応答確認生成器５５及びリプライ応答確認メッセージ生成器５６を備え、これらのすべてが、メッセージを送信機１２を介して動的ネットワーク上に送信することが可能となるように構成されている。特に、エクスプローラメッセージ生成器５２は、ノードが接続されている動的通信ネットワークを介して続けてエクスプローラメッセージを伝送することを可能にするために、送信機１２を利用する。
【００５９】
受信機１１は評価部５７に接続されていて、ここで、受信されたメッセージが検証される。受信されたエクスプローラメッセージの場合には、この情報は、エクスプローラインタプリタ６０に提供される。エクスプローラインタプリタ６０は、エクスプローラメッセージのアイデンティティをチェックし、そのエクスプローラメッセージが第１の時間で受信される場合、エクスプローラインタプリタ６０は、応答確認生成器５４を起動し、そのエクスプローラメッセージを送信したノードへ返信する応答確認メッセージを生成する。同時に、エクスプローラインタプリタ６０は、エクスプローラメッセージ生成器５２を起動し、そのエクスプローラメッセージを通信ネットワークの他のノードへ転送する。そのエクスプローラメッセージが既に受信されている場合、エクスプローラインタプリタ６０は、代わりに、リプライメッセージ生成器５４を起動して、このパターンを既に受信していることを、送信ノードへ通知するリプライを生成する。エクスプローラメッセージの内容はエクスプローラインタプリタ６０で解釈され、任意の要求されているアクティビティ、例えば、ネットワークのデータあるいは状態の収集、あるいは他のネットワーク管理動作のようなアクティビティが、管理部６２で実行される。そのようなアクティビティからの結果は、以下で説明するように、編纂部６１へ提供される。
【００６０】
受信されたメッセージが応答確認メッセージあるいは次の応答確認メッセージである場合、このようなメッセージがどのノードから受信され、かつどのエクスプローラメッセージについて支援されるものであるかの情報が、リンク識別器５９に提供される。リンク識別器５９は、この情報を使用して、そのエクスプローラメッセージの送信時にどのリンクが動作しているかを識別する。即ち、どのノードから、リプライメッセージを取得することが期待されているかを識別する。次に、この情報は、編纂部６１に提供されることで、すべてのリプライが受信されているかどうかの判定が可能となる。リンク識別器５９と３種類の応答確認生成器５４、５５、５６とで、動的通信ネットワーク内の動作リンクを識別するための手段７０を形成する。この識別は、エクスプローラメッセージの実際の伝送とともに実行される。
【００６１】
リプライメッセージが受信される場合、それを送信するノードのアイデンティティと内容が編纂部６１に提供される。また、編纂部６１は、リプライ応答確認生成器５６を起動して、リプライ応答確認メッセージを生成し、それを、そのリプライを送信したノードへ送信する。編纂部６１は、対象とするノードからのエクスプローラメッセージを受信しているノードからのリプライ情報を編纂する。この編纂されたリプライ情報は、任意の場合に、管理部６２からの結果と統合される。リンク識別器５９からの情報に基づく判定として、利用可能なすべてのノードがリプライしている場合、あるいは適切なタイムアウト期間が経過している場合、編纂部６１は、リプライメッセージ生成器５３を起動して、受信したエクスプローラメッセージに対するリプライメッセージを生成する。送信機１２は、次に、動的通信ネットワークを介してリプライメッセージを送信するために利用される。また、リンク識別器５９は、リプライメッセージの送信について通知される。対象とするノードがエクスプローラメッセージを最初に生成しているノードである場合、編纂されたリプライ情報は、管理部６２によって、自身のノード内及びネットワークの少なくとも一方で、新規のパターンを開始することによって更なるネットワーク管理動作を開始するために利用することができる。
【００６２】
リンク識別器５９は、所定時間内に任意のリプライ応答確認メッセージを受信していない場合に、そのリンクは動作していないと想定する。新規ルート処理部５８に通知がなされると、適切な動作が開始される。これは、例えば、新規ルート生成器５１を起動して、適切なメッセージを生成することによってなされる。エクスプローラインタプリタ６０は、どのノードが同一のエクスプローラメッセージを提供しているかについての情報を与える。これは、上述のルーチンに従って、別のルートを検出するために使用することができる。
【００６３】
上述の実施形態は、本発明のいくつかの例示として理解されるべきである。本発明の範囲を逸脱することなく、様々な変形、組み合わせ及び変更を実現できることが当業者には理解されるであろう。特に、異なる実施形態の異なる部分のソリューションは、技術的に可能な部分については他の構成と組み合わせることができる。但し、本発明の範囲は、特許請求の範囲によって定義されるものである。
【図面の簡単な説明】
【００６４】
【図１】高頻度の移動性を有する無線通信ネットワークの実施形態を示す図である。
【図２】本発明に従う方法の実施形態に従って、送信されるメッセージのタイミングを示すメッセージフロー図である。
【図３Ａ】本発明に従う方法の実施形態に従う、様々な状況で送信されるメッセージのタイミングを示すメッセージフロー図である。
【図３Ｂ】本発明に従う方法の実施形態に従う、様々な状況で送信されるメッセージのタイミングを示すメッセージフロー図である。
【図３Ｃ】本発明に従う方法の実施形態に従う、様々な状況で送信されるメッセージのタイミングを示すメッセージフロー図である。
【図４Ａ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態を示す図である。
【図４Ｂ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態を示す図である。
【図４Ｃ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態を示す図である。
【図４Ｄ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態を示す図である。
【図４Ｅ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態を示す図である。
【図４Ｆ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態を示す図である。
【図４Ｇ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態を示す図である。
【図５Ａ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図５Ｂ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図５Ｃ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図５Ｄ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図５Ｅ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図５Ｆ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図５Ｇ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図５Ｈ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図５Ｉ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図５Ｊ】リンクが切断されている場合における、本発明に従う無線通信ネットワークの別の実施形態を示す図である。
【図６Ａ】別の親ノードが直接利用可能でなく、リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態の図である。
【図６Ｂ】別の親ノードが直接利用可能でなく、リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態の図である。
【図６Ｃ】別の親ノードが直接利用可能でなく、リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態の図である。
【図６Ｄ】別の親ノードが直接利用可能でなく、リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態の図である。
【図６Ｅ】別の親ノードが直接利用可能でなく、リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態の図である。
【図６Ｆ】別の親ノードが直接利用可能でなく、リンクが切断されている場合における、本発明に従う無線通信ネットワークの実施形態の図である。
【図７】本発明に従う方法の実施形態の主要なステップのフロー図である。
【図８】本発明に従う装置の実施形態の関連主要部分のブロック図である。
【図１】
2008519482.tif 000003
【図２】
2008519482.tif 000004
【図３Ａ】
2008519482.tif 000005
【図３Ｂ】
2008519482.tif 000006
【図３Ｃ】
2008519482.tif 000007
【図４Ａ】
2008519482.tif 000008
【図４Ｂ】
2008519482.tif 000009
【図４Ｃ】
2008519482.tif 000010
【図４Ｄ】
2008519482.tif 000011
【図４Ｅ】
2008519482.tif 000012
【図４Ｆ】
2008519482.tif 000013
【図４Ｇ】
2008519482.tif 000014
【図５Ａ】
2008519482.tif 000015
【図５Ｂ】
2008519482.tif 000016
【図５Ｃ】
2008519482.tif 000017
【図５Ｄ】
2008519482.tif 000018
【図５Ｅ】
2008519482.tif 000019
【図５Ｆ】
2008519482.tif 000020
【図５Ｇ】
2008519482.tif 000021
【図５Ｈ】
2008519482.tif 000022
【図５Ｉ】
2008519482.tif 000023
【図５Ｊ】
2008519482.tif 000024
【図６Ａ】
2008519482.tif 000025
【図６Ｂ】
2008519482.tif 000026
【図６Ｃ】
2008519482.tif 000027
【図６Ｄ】
2008519482.tif 000028
【図６Ｅ】
2008519482.tif 000029
【図６Ｆ】
2008519482.tif 000030
【図７】
2008519482.tif 000031
【図８】
2008519482.tif 000032
【国際調査報告】
2008519482.tif 000033
2008519482.tif 000034
2008519482.tif 000035
2008519482.tif 000036