(57)【要約】本発明は、階層的アドレス付与方式を有するピア・ツー・ピア型ネットワークにおいてアドレス空間を再配置する方法に関連し、前記ネットワークは、複数の異なるネットワーク深さに位置するルータ機器をノードとして有する木構造を有する。前記ルータ機器の各々は、自身に割り当てられたアドレス空間を有し、前記アドレス空間は、前記ルータ機器の各々を識別するアドレス、子ルータに割り当てるべきアドレス空間を供給するための一つ以上のアドレス・ブロックおよび複数のエンド・デバイスに対してそれらの識別アドレスを供給するための追加のアドレス・ブロックを含む。前記再配置すること無しに一のルータ機器に割り当てられるアドレス空間のサイズは、所定の方法に従って前記一のルータ機器が位置するネットワーク深さに依存し、その結果、前記一のルータ機器に、特定のサイズのアドレス空間が割り当てられる。本発明に係る上記の方法は、前記アドレス空間が枯渇した第１のルータ機器が、参加しようとするルータ又は参加しようとする端末装置からの参加要求を受信するステップ；および、前記ネットワーク内の第２のルータ機器に対して、再配置要求を送信するステップであって、前記再配置要求は、要求されるアドレス・ブロックのサイズを表し、前記要求されるアドレス・ブロックの前記サイズは、所定のアドレス空間サイズのいずれか一つと等しい、ステップを備える。本発明はさらに、上述したようなネットワーク環境において使用するためのルータ機器であって、上述した方法を実行するのに適したルータ機器と関連する。
2013522997.tif 000002
【特許請求の範囲】
【請求項１】
階層的アドレス付与方式を有するピア・ツー・ピア型ネットワークにおいてアドレス空間を再配置する方法であって、前記ネットワークは、複数の異なるネットワーク深さに位置するルータ機器をノードとして有する木構造を有し、
前記ルータ機器の各々は、自身に割り当てられたアドレス空間を有し、前記アドレス空間は、前記ルータ機器の各々を識別するアドレス、子ルータに割り当てるべきアドレス空間を供給するための一つ以上のアドレス・ブロックおよび複数のエンド・デバイスに対してそれらの識別アドレスを供給するための追加のアドレス・ブロックを含み、
再配置することなしに一のルータ機器に割り当てられるアドレス空間のサイズは、所定の方法に従って前記一のルータ機器が位置するネットワーク深さに依存し、その結果、前記一のルータ機器に、特定のサイズのアドレス空間が割り当てられ、
当該方法は、
アドレス空間が枯渇した第１のルータ機器が、参加しようとするルータ又は参加しようとする端末装置からの参加要求を受信するステップ；および、
前記ネットワーク内の第２のルータ機器に対して、再配置要求を送信するステップであって、前記再配置要求は、要求されるアドレス・ブロックのサイズを表し、前記要求されるアドレス・ブロックの前記サイズは、所定のアドレス空間サイズのいずれか一つと等しい、ステップ；
を備える方法。
【請求項２】
前記再配置すること無しに一のルータ機器に割り当てられる前記アドレス空間の前記サイズは、全単射的な方法に従って前記一のルータ機器が位置するネットワーク深さに依存し、前記再配置要求は、目標とするネットワーク深さ（ＴＤ）により表される前記要求されるアドレス・ブロックの前記サイズを表す、請求項１記載の方法。
【請求項３】
前記第２のルータ機器は、前記第１のルータ機器の親である請求項１または２のいずれかに記載の方法。
【請求項４】
前記再配置要求は、距離カウンタ値（Ｃ）を含み、前記再配置要求を受け取った前記第２のルータ機器は、
前記距離カウンタ値（Ｃ）がゼロに等しいか否かを判定するステップ；
前記距離カウンタ値（Ｃ）がゼロに等しくないと判定されたならば、前記距離カウンタ値（Ｃ）を１だけ減算した上で、前記第２のルータ機器の親である第３のルータ機器に対して、前記再配置要求を転送するステップ；および、
前記距離カウンタ値（Ｃ）がゼロに等しいと判定されたならば、前記再配置要求に対して行うべき後続の処理を実行するステップ；
をさらに実行することを備える、請求項１から請求項３のいずれか一つに記載の方法。
【請求項５】
前記再配置要求に対して行うべき前記後続の処理を実行する前記ステップは、
前記目標とするネットワーク深さ（ＴＤ）が前記第２のルータ機器の配下にある複数の可能な子ルータが位置するネットワーク深さと等しいか否かを判定するステップ；
もしもそうなら、前記目標とするネットワーク深さ（ＴＤ）の値に従って要求されるサイズを有する少なくとも一つの未割り当てアドレス・ブロックが利用可能であるか否かを判定するための利用可能性検査を実行し、前記利用可能性検査の結果を含み、かつ、前記少なくとも一つのみ割り当てのアドレス・ブロックが利用可能な場合は、前記未割り当てのアドレス・ブロックのそれぞれを記述するパラメータをも含んでいる再配置応答を発行するステップ；および、
そうでなければ、前記再配置要求に対して行うべきその先の処理を実行するステップ；
をさらに備える、請求項４記載の方法。
【請求項６】
前記未割り当てのアドレス・ブロックを記述するパラメータは、開始アドレス（ＡＳ）および終端アドレス（ＡＥ）を備える請求項５記載の方法。
【請求項７】
前記目標とするネットワーク深さ（ＴＤ）が前記第２のルータ機器の配下にある複数の可能な子ルータが位置するネットワーク深さと等しくないと判定された場合、前記再配置要求に対して行うべき前記その先の処理を実行する前記ステップは、
前記第２のルータ機器の配下にある子ルータが存在するか否か、および前記目標とするネットワーク深さ（ＴＤ）が前記第２のルータ機器の配下にある複数の子ルータが位置するネットワーク深さよりも大きいか否かを判定するステップ；
上記に該当する場合、前記第２のルータ機器の配下にある一の子ルータに対して前記再配置要求を転送するステップ；および、
上記に該当しない場合、前記再配置要求を戻すステップ；
をさらに備える、請求項５または請求項６のいずれか一方に記載の方法。
【請求項８】
前記利用可能性検査に関する肯定的な結果を含む再配置応答が発行されるまで、前記第２のルータ機器の配下にある子ルータの各々に対して、前記再配置要求を連続的に転送する、請求項７記載の方法。
【請求項９】
請求項５から請求項８までのいずれか一つに記載された方法であって、一のルータ機器が前記再配置応答を受信した後に、
前記一のルータ機器は前記再配置要求を発行した最初のルータ機器であり、かつ、前記再配置要求は前記再配置応答が参照している再配置要求であるか否かを判定するステップ；
上記に該当する場合、前記再配置応答が前記利用可能性検査の肯定的な結果を表しているならば、前記アドレス・ブロック・パラメータを備える肯定的な応答を前記参加しようとするルータ機器に対して送信し、前記再配置応答が前記利用可能性検査の否定的な結果を表しているならば、新たな再配置要求を発行するステップ；および、
上記に該当しない場合、前記再配置応答が前記利用可能性検査の肯定的な結果を表しているならば、前記最初のルータ機器に向けて前記再配置応答を転送し、前記再配置応答が前記利用可能性検査の否定的な結果を表しているならば、前記再配置応答を戻すステップ；
をさらに実行することを備える、方法。
【請求項１０】
新たな再配置要求は、前記目標とするネットワーク深さ（ＴＤ）および／または前記距離カウンタ（Ｃ）に関して異なる値を使用する点で、後続の更なる再配置要求とは異なっている、請求項９記載の方法。
【請求項１１】
一の再配置要求に関する前記目標とするネットワーク深さ（ＴＤ）および／または前記距離カウンタ（Ｃ）の値は、所定の再配置戦略に従って決定される、請求項１から請求項１０までのいずれか一つに記載された方法。
【請求項１２】
ルータ機器の各々に関して、特定のルータ機器の子孫であって、最も低い深さの子ルータが位置するネットワーク深さの値を備える刈り取りテーブルを維持管理する、請求項１から請求項１１までのいずれか一つに記載された方法。
【請求項１３】
前記ネットワーク内の全てのルータ機器によって再帰反復的に実行される、請求項１から請求項１２までのいずれか一つに記載された方法。
【請求項１４】
前記ネットワーク内においてZigBee標準規格に従って実行される、請求項１から請求項１３までのいずれか一つに記載された方法。
【請求項１５】
階層的アドレス付与方式を有するピア・ツー・ピア型ネットワークにおいて使用されるルータ機器であって、請求項１から請求項１１までのいずれか一つに記載された方法に従ってアドレス空間を再配置する方法を実行することに適合したルータ機器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層的なアドレッシングを有するピア・ツー・ピア型ネットワークにおけるアドレス空間の再配置を行うための方法に関係する。さらに本発明は、当該方法を実施するのに適したピア・ツー・ピア・ネットワークにおいて使用されるルータ機器に関係する。
【背景技術】
【０００２】
ピア・ツー・ピア型ネットワーク、その中でも特に、無線のピア・ツー・ピア型ネットワークは、ビルの自動化、照明制御、監視アプリケーションおよび医療用アプリケーションなどの用途においてますます重要となってきている。
【０００３】
通常においては、ピア・ツー・ピア型ネットワークは、ネットワークの柔軟な組織化と再組織化を可能とするようなアドレッシング方式を採用し、これには、任意の時刻において、および多種多様なアクセスポイントにおいて、新たなデバイスがネットワークに参加するオプション（ad-hoc型ネットワーク）を含む。柔軟なピア・ツー・ピア型ネットワークの一例は、ZigBeeアライアンスが標準仕様を策定したZigBee標準規格によって実現される。
【０００４】
ZigBee標準規格は、複数のアドレスが分散的な態様で割り振られる階層型の方式を提案している。ZigBee標準規格は、物理リンク層（ＰＨＹ）および媒体アクセス制御層（ＭＡＣ）を定義するIEEE  802.15.4通信プロトコルに基づいたオープンな標準規格である。これらのプロトコル層に加えて、ZigBee標準規格は、ＰＨＹ層およびＭＡＣ層の上位に位置するネットワーク層とアプリケーション層を定義する。
【０００５】
通常においては、ZigBeeネットワークは、２つの異なる種類のデバイスを備える。第１の種類のデバイスは、ルータ機器と呼ばれるものである。ルータ機器は、他の複数のデバイスをネットワークに接続する機能を有し、さらに、ネットワークを経由する複数のパケットの経路制御を実行する機能を有する。この経路制御機能とは別に、ルータ機器は、通常さらに、例えば、センサ情報の読み込みや装置の制御などのアプリケーション機能を提供する。もう一方の種類のデバイスは、エンド・デバイスと呼ばれるものである。これらは、他のデバイスを接続する機能を有さず、ネットワークのユーザに対して自身のアプリケーション機能を提供するにとどまる。
【０００６】
階層的アドレッシングにおいては、ルータ機器は、複数の連続するアドレスから成るブロックを割り当てられ、当該ブロックは、当該ルータ機器のアドレス空間と呼ばれる。当該アドレス空間の一番最初のアドレスは、通常は、当該ルータ機器自体を識別するために使用される。残りの複数のアドレスは、以下のような方法で分割される。これら複数のアドレスから成る一方の部分は、複数のエンド・デバイスを接続するために当該ルータ機器によってとっておかれ、エンド・デバイスの各々は、当該アドレス空間のこの部分の中の単一のアドレスを割り当てられる。当該アドレス空間内のさらに残りのアドレス群は、所定の個数のアドレス・ブロックに均等に分割される。後続の新たな他のルータ機器がネットワークに参加する場合、これらのアドレス・ブロックの中の一つが後続の新たに参加したルータ機器に対してそのアドレス空間として割り当てられる。このルータ機器は、上記と同様に、そのアドレス空間を成す複数のアドレスの中の一つを自分自身のアドレスとして使用し、当該アドレス空間内の残りの部分を上記と同様の方法で分割する。当該アドレス・ブロックを割り当てた側のルータ機器は、当該アドレス・ブロックを受け取った側であるこのルータ機器にとっての親ルータとも呼ばれ、さらに、当該アドレス・ブロックを受け取った側のこのルータ機器は、当該親ルータの子供と呼ばれる。アドレス空間の上記したような分散型の割り当ては、木構造上の階層的なアドレッシング方式を結果としてもたらす。当該木構造の根ノードから見た一つのルータ機器（すなわち、木の一つのノードに相当する）までの距離（すなわち、親子間の世代という意味で）は、当該ルータ機器のネットワーク深さ、あるいはネットワーク・レベルと呼ばれる。
【０００７】
当該システム内において、当該木構造の根ノードに位置する第１のルータ機器は、所定のサイズである一のアドレス空間を備えており、このアドレス空間は、例えばZigBeeネットワークの場合には、２１６個のアドレスを含んでいる。上記した階層的なアドレス割り当て手順の結果として、当該ネットワークに参加する後続の新たなルータ機器に割り当てられるアドレス空間のサイズは、ネットワーク深さの増加に伴って減少して行く。ある時点において、一のルータ機器に割り当てられるアドレス空間は、小さ過ぎてこれ以上分割できない大きさになる。従って、階層的アドレッシングを有する一のネットワークに関して、ネットワーク深さの最大値は制限され、この最大値は、アドレス空間の全体サイズと上記した分割手順に関するパラメータとに依存する。
【０００８】
上記したような標準化された静的な分割手順を有する階層的アドレッシングの欠点は、ネットワークの木構造に関して結果的に生成されるトポロジーが柔軟性を欠くという点である。例えば、複数のルータ機器は、自分自身に後続の新たな子供を接続するために、アドレス・ブロックの残余数を超えて上記した手順を実行してしまうかも知れない。このような事態が起きるのは、上記した分割手順におけるアドレス空間毎のアドレス・ブロックの個数であると同時に、親ルータが持ち得る子供の最大数を定義する数として選ばれた値が小さ過ぎるからである（すなわち、深いけれども幅の細い木構造となる）。しかしながら、子供の最大数の値は、自由に増加させることが出来ない。何故なら、この値は、ネットワーク深さの上限値に影響するからである。ルータ機器の子供の個数として大き過ぎる値が選ばれれば、ネットワーク深さはあまりにも早く限界に達する（すなわち、浅いけれども幅の広い木構造となる）。ZigBee標準仕様に従って、例えば、アドレス空間のビット幅が16ビット幅に制限されると仮定するならば、各ルータ機器毎の子ルータの最大数とネットワーク深さの上限との間に妥協が図られなければならない。
【０００９】
上記した標準的なアドレス割り当て手順によって課される制限を克服するために、アドレス空間の再配置の仕組みが提案されている。例えば、以下の特許文献１は、新たなルータ機器からネットワークに参加するための要求を受け取ったルータ機器がその親ルータへ、さらにその祖先のルータへと階層的アドレス木構造の中を根ノードの方向に向かって再配置要求を送出する。当該再配置要求の送出は、これらのルータ機器の中のいずれかが利用可能な未割り当てアドレスを有しているか否かを問い合わせるために実行される。続いて、ネットワークへの参加要求を受け取ったルータ機器を介して当該新たなルータ機器に対して未割り当てのアドレスが割り当てられる。上記のようにして、アドレス空間は、論理的な意味で再配列され、あるいは再配置され、その結果、上記した分割手順によって予め定められていた元々の個数よりも多くの子供をルータ機器が持つことが出来る可能性を与える。上記した再配置手順の欠点は、フラグメント化されたアドレス空間を結果としてもたらしてしまう事である。
【００１０】
従って、アドレス空間のフラグメント化を防止するようなアドレス空間の再配置の方法を実現することは、従来技術よりも優位性がある。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】米国公開公報ＵＳ２００８／０１５９２８９号公報
【発明の概要】
【００１２】
本発明は、階層的アドレッシングを有するピア・ツー・ピア型ネットワークにおいてアドレス空間の再配置のための方法を発案するものであり、本発明においては、ネットワークは、複数の異なるネットワーク深さに位置する複数のルーティング装置を備えた木構造を有する。そして、各ルータ機器は、自身に割り当てられたアドレス空間を有し、当該アドレス空間は、当該ルータ機器の識別アドレス、さらに追加されるルータ機器に割り当てるべきアドレス空間を提供する一つ以上のアドレス・ブロック、および複数のエンド・デバイスに対して識別アドレスを提供するための更なるアドレス・ブロックを含む。再配置が行われること無しに一のルータ機器に対して割り当てられるアドレス空間のサイズは、所定の方法に従って、当該ルータ機器が位置するネットワーク深さに依存し、それにより、特定のサイズのアドレス空間が複数のルータ機器に割り当てられる結果となる。
【００１３】
本発明に係る方法は、以下の動作ステップを備える：まず、参加しようとするルータ機器または参加しようとするエンド・デバイスからの参加要求がネットワーク内においてアドレス空間が枯渇した第１のルータ機器によって受け取られる。続いて、第１のルータ機器は、ネットワーク内の第２のルータ機器に対して再配置要求を送信し、この時、当該再配置要求は、要求されるアドレス・ブロックのサイズを表し、当該要求されるアドレス・ブロックのサイズは、特定のアドレス空間サイズのいずれか一つと等しい。
【００１４】
一のルータ機器のアドレス空間をさらに小さな複数のアドレス・ブロックに分割し、これをさらに、当該ルータ機器の複数の子供に割り当てるという上記の標準化された手順に起因して、一のルータ機器に割り当てられるアドレス空間は、上記した分割手順のパラメータに依存した複数の特定サイズのみを取り得る。以下の記述においては、この複数の取り得る特定サイズのことを「本来のサイズ」とも呼ぶことにする。本発明によれば、参加要求を受け取ったが利用可能な未割り当てアドレスを全く持っていないルータ機器によって再配置要求が発せられた際、要求されるアドレス空間は、上記した分割手順によって結果的に得られる本来のサイズの中のいずれか一つである。このように、再配置されたアドレス・ブロックは、上記した標準化されたアドレス分割方式に無理なく適合するので、結果として、使用不可能なアドレス・ブロックの生成を回避することが可能であり、それにより、アドレス空間のフラグメント化を回避することが出来る。使用不可能なアドレス・ブロックとは、例えば、上記した標準化された分割方式において、単一のアドレス・ブロックとするには、単に小さ過ぎるサイズのブロック等である。
【００１５】
本発明に係る方法の好適な実施形態においては、要求されるアドレス・ブロックのサイズは、目標とするネットワーク深さの観点から述べられる。このように、要求されるアドレス・ブロックのサイズに関する短くて不明瞭さの無いサイズ指定が提供され、それにより、アドレス・ブロックは複数の特定サイズの中のいずれかの大きさで要求されることが保証される。
【００１６】
本発明に係る方法の好適な実施形態においては、再配置要求は、距離カウンタ値を含んでいる。受信された再配置要求は、これを受信したルータ機器の親ルータに転送され、この際、再配置要求を受信した時点で距離カウンタ値がゼロと等しくないと判定されたならば、距離カウンタは１だけ減らされる。このように、再配置要求は、まず、ネットワーク木構造の根ノードに向けて所定の（論理的な）距離だけ伝搬し、その後に更なる後処理をされる。従って、ネットワーク・アドレス空間の再配置処理が発生し得る（論理的な）最大距離の範囲が決定されることが可能となる。
【００１７】
本発明はさらに、関連するネットワークにおいて使用するためのルータ機器であって、上述した本発明に係る方法を実施するのに適したルータ機器を発案するものである。当該ルータ機器が有する優位性は、本発明に係る方法に関して上述した優位性と対応する。
【００１８】
本発明の更なる有利な実施形態は、対応する従属請求項において提供される。本発明の上記した以外の更なる優位性と利点は、本明細書に添付した図面と共に、以下において後述する実施形態の記載を参照することにより、自ずと明らかとなるであろう。
【図面の簡単な説明】
【００１９】
【図１】ネットワーク木構造の第１の例
【図２】ネットワーク木構造の第２の例
【図３】ネットワーク木構造の第３の例
【図４】アドレス空間を再配置するための方法の第１の部分を示すフローチャート
【図５】一のルータ機器およびその子供のルータ機器のアドレス空間を示す概略的な図
【図６】再配置要求を図示する概略図
【図７】アドレス空間を再配置するための方法の第２の部分を示すフローチャート
【図８】再配置要求に対する応答を図示する概略図
【図９】アドレス空間を再配置するための方法の第３の部分を示すフローチャート
【発明を実施するための形態】
【００２０】
図１は、ネットワーク１内における階層的アドレッシングの木構造を示す図である。ネットワーク木構造は、空のノード２（白抜きのシンボル）およびルータ機器３によって占有されたノード（影付きのシンボル）を備えている。上記した空のノード２およびルータ機器３は、当該ネットワーク木構造内での当該ノード２と当該ルータ機器３の位置を指定する２つの添え字を伴っている。最初の添え字は、ネットワーク深さＤを表し、これはさらに、図１の右側部分にも表示されている。２番目の添え字はネットワーク深さＤの各々のレベル内において各ノード（空のノード２およびルータ機器３が占有するノードの両方）に連続的に番号を割り振ったものである。当該木構造の葉の部分のノードはエンド・デバイスによって占有されることも可能である。
【００２１】
ルータ機器３０−０は、当該ネットワーク木構造の根を表す。このルータ機器３０−０は、利用可能なアドレス空間の総量を割り当てられている。例示の方法によれば、当該アドレス空間内の複数のアドレスの中の一つは、ルータ機器３０−０自身をアドレッシングするために使用され、幾つかのアドレスは、ルータ機器３０−０に対してエンド・デバイスを接続するために使用され、残りのアドレス群は、２つのアドレス・ブロックに均等に分割され、これらは後続の新たなルータ機器に割り当てることが可能である。
【００２２】
上記において示した具体例においては、当該２つのアドレス・ブロックのうちの一方は、１段階下のネットワーク深さレベルＤ＝１に位置するルータ機器３１−０に割り当てられ、他方、当該２つのアドレス・ブロックのうちの他方は、まだルータ機器を割り当てられていない。図１において、これは、空のノード２１−１として表示されている。ルータ機器３１−０は、ルータ機器３０−０の子供と呼ばれ、逆に、ルータ機器３０−０は、ルータ機器３１−０の親と呼ばれる。以下においては、複数のノードの相互間における関係、すなわち、ルータ機器とノードとの間の関係は、上記と同様の用語を使用してその特徴が記述される。
【００２３】
ルータ機器３１−０に割り当てられたアドレス空間は、上記と同様に、２つのアドレス・ブロックに分割され、当該アドレス・ブロックは、さらに一段階下のネットワーク深さレベルＤ＝２に位置するルータ機器に割り当てることが可能である。図１の例においては、両方のアドレス・ブロックは、子ルータ、即ち、ルータ機器３２−０とルータ機器３２−１に割り当てられる。空のノード２１−１に関して対応する子供ノードは、空のノード２２−２および２２−３として図示されている。
【００２４】
図に示された木構造は、アドレスの継承に関するルータ機器間の関係を表していることに留意されたい。図中において示されたルータ機器間の接続に沿って通信が可能であるが、図示された木構造において互いに直接には繋がっていないルータ機器間でも通信が可能な場合もある。この場合、既知の経路制御方法（ルーティング方法）および各ルータ機器内において経路制御テーブル（ルーティング・テーブル）を維持し、使用し、および更新する既知の方法を適用することが可能である。
【００２５】
図２は、図１のネットワーク１における木構造に関して、アドレス再配置が行われた後の階層的アドレス木構造を示す図である。アドレス再配置の過程において、ルータ機器３０−０における未割り当てのアドレス・ブロックは、ルータ機器３１−０に移行させられている。その結果、今度は、ルータ機器３１−０が、３つの子ルータにアドレス・ブロックを割り当てる。即ち、ルータ機器３１−０に対して既に子供として割り当て済みのルータ機器３２−０およびルータ機器３２−１に対するアドレス・ブロック割り当てに加え、ノード２１−１に位置を占めることとなる新たなルータ機器に対して追加のアドレス・ブロックを割り当てる。このネットワーク・ノード２１−１を占有するルータ機器は、続いて、ノード２２−２およびノード２２−３を占有する後続の新たなルータ機器に２つのアドレス・ブロックを割り当てることが可能である。
【００２６】
上記したアドレス再配置の過程に起因して、全体のアドレス空間は、明らかに変化しないものの、ネットワークは、本来であれば充足することが出来なかったルータ機器からの参加要求にも柔軟に対応することが出来るようになった。図２に示すネットワーク・システムは、子ルータの個数を局所的に増加させ（この例で言えば、ルータ機器３１−０について、２個の子供の代わりに３個の子供）、同時に、ネットワークの深さを局所的に延伸する（この例で言えば、ネットワーク深さレベルＤ＝３において、空のノード２２−２および２２−３を占めるべき２個の割り当て可能なルータによる深さレベルの延伸）。この場合、ルータ機器の通信伝送可能範囲が限られていることに起因して、ネットワークに参加しようとするルータ機器とルータ機器３１−０の代理として振舞うルータ機器３０−０との間のアドレス空間に関する直接の交渉は不可能でとなる場合がある。
【００２７】
図３は、本発明により可能なアドレス再配置過程の別の具体例を示す図である。図３に示されるアドレス再配置過程の出発点は、以下の相違点を除いて、図１に示した状況とほぼ同様である。即ち、図１の空のノード２１−１は、ルータ機器３１−１によって既に占有されている。図３に示すアドレス再配置に関して、ルータ機器３１−１のアドレス空間に含まれる２つの未割り当てのアドレス・ブロックのうちの一方のアドレス・ブロックはルータ機器３１−０に移行させられる。この例においては、Ｄ＝２となる最大のネットワーク深さレベルは変化せず、ネットワーク深さの各レベル内におけるノード割り当て可能なルータ機器の個数も変化しない。しかし、局所的に見るならば、１個のルータ機器に割り当てられる割り当て可能なルータ機器の個数はルータ機器３１−０に関して変化しており（この例で言えば、ルータ機器３１−０について、２個の子供の代わりに３個の子供）、ルータ機器３１−１に関しても変化している（この例で言えば、ルータ機器３１−１について、２個の子供の代わりに１個の子供）。
【００２８】
図２と図３の両者において示したアドレス再配置過程は、以下の図との関係において後述される本発明に従ったアドレス空間の再配置方法を適用することにより、実現される。例示による方法に基づき、かつ、本発明の範囲を一切限定することなく、以下において後述される本発明のアドレス空間再配置方法は、図１に示すネットワーク１を参照しながら説明される。本発明に係る方法は、中心的な役割を果たす調整機器によって全体の動作が協調させられるのではなく、ネットワーク・システム内に存在する全ての機器によって動作が実行される分散型ネットワーク・システムに対して適用可能であるので、ネットワーク内に存在するルータ機器の各々が本明細書に記載される方法を実行することが可能である。
【００２９】
図４は、アドレス空間を再配置する方法全体のうちの第１の部分を示すフローチャートである。最初のステップＳ１０において、ネットワーク内に既に存在しているルータ機器の中の一つが、未だに当該ネットワークの一部となっていないルータ機器又はエンド・デバイスからの「参加要求」とも呼ばれる「アソシエーション要求」を受信する。例示の方法によれば、当該「参加要求」は、以下において「これから参加しようとするルータ機器」と表記される一のルータ機器によって発行されるものとする。この場合、たとえ現段階では、当該「アソシエーション要求」の結果としてこのルータ機器がネットワーク内に組み込まれる保証が無くとも、このルータ機器のことをそのように表記する。例示の方法によれば、当該「参加要求」は、図１に示すネットワーク１内のルータ機器３１−０によって既に受信されている可能性もある。
【００３０】
続くステップＳ１１において、「アソシエーション要求」を受信したルータ機器は、「これから参加しようとするルータ機器」に対して割り当てるために利用可能な未割り当てアドレス・ブロックを有するか否かをチェックする。未割り当てアドレス・ブロックが利用可能であるならば、本発明に係る方法は、ステップＳ１２に進み、当該アドレス・ブロックを記述する複数のパラメータを決定する。これらのパラメータは例えば、当該アドレス・ブロックの開始アドレスＡＳや最終アドレスつまり終端アドレスＡＥ等であったりする。代替的に、当該アドレス・ブロックの開始アドレスＡＳとサイズが記述パラメータとして使用され得る。
【００３１】
アドレス・ブロックの当該パラメータの決定については、図５を参照しながら、以下においてより詳細に説明する。図５は、ネットワーク深さレベルＤ＝Ｎに位置するルータ機器３に対して割り当てられ、複数個の連続するアドレスから成るアドレス空間１０の図式的な表現であり、この時、Ｎは無作為に選ばれた任意の数を表す。アドレス空間１０は幾つかの部分に分割され、第１の部分１１は、ルータ機器自身を識別するアドレスを含み、これは、当該ネットワーク内における当該ルータ機器をアドレス指定するために使用される曖昧さの無いアドレスである。通常は、当該ルータ機器自身のアドレス１１はアドレス空間１０の先頭部分に配置されている。アドレス空間１０の末尾に配置され、複数のアドレスから成る１個のブロック１３は、複数のエンド・デバイスに対して割り当てるために予約されている。上記以外の残りの複数のアドレスは、均等に分割されて複数個のアドレス・ブロック１２とされ、この実施例にける例示的態様としては（そして、図１〜図３に示した例示的態様とは異なり）、以下の３つのアドレス・ブロック１２．０、１２．１、１２．２に分割される。エンド・デバイスへの割り当てのためにこれらのさらに後ろに有るアドレス・ブロック１３のサイズおよびアドレス・ブロック１２の個数は、予め規定されており、当該ネットワーク全体を通して同一に維持される。
【００３２】
図４に戻ると、続いて、次のステップＳ１３では、アドレス・ブロックのパラメータとして開始アドレスＡＳと終端アドレスＡＥを含んだ「アソシエーション応答」が「これから参加しようとするルータ機器」に対して送信される。続くステップＳ１４においては、「アソシエーション要求」を受信したルータ機器は、割り当てられたアドレス・ブロックの中の開始アドレスを使用して自身のルーティング・テーブルを更新する。何故なら、この開始アドレスが当該「これから参加しようとするルータ機器」の識別アドレスとなり、ネットワーク内において当該「これから参加しようとするルータ機器」に向けてメッセージを経路制御するのに使用されるアドレスとなるからである。
【００３３】
当該「これから参加しようとするルータ機器」に対して割り当てられるアドレス・ブロックは、当該「これから参加しようとするルータ機器」のアドレス空間を形成する。この様子は、図５の下の部分に図示されており、ここでは、ネットワーク深さＤ＝Ｎに位置するルータ機器に対して割り当てられたアドレス空間１０の中のアドレス・ブロック１２．０がネットワーク深さＤ＝Ｎ＋１においてネットワークに参加しようとするルータ機器にとってのアドレス空間10’（図中において拡大表示されている）を形成する。続いて、このアドレス空間は、「これから参加しようとするルータ機器」自身の識別アドレス11’、そこから先に繋がるルータ機器のための３個のアドレス・ブロック12’.0〜12’2、および複数のエンド・デバイスのために予約される更なるアドレス・ブロック13’にさらに分割される。
【００３４】
ステップＳ１４の後に、本発明に係る方法は実行を終了し、当該方法を最初から反復実行することにより、ステップＳ１０において、ルータ機器は後続の新たな「アソシエーション要求」を受け付けられるようになる。
【００３５】
ステップＳ１１において、未割り当てのアドレス・ブロックが全く利用可能でない、言い換えれば、「アソシエーション要求」を受け取ったルータ機器において、自身のアドレス空間が枯渇してしまっている場合、本発明に係る方法は、ステップＳ１５に進む。ステップＳ１５においては、一の再配置要求に関する識別番号ＩＤが生成される。当該ＩＤの生成プロセスは、生成されたＩＤがシステム内で一意的であることを保証する。そのようなＩＤを生成する可能な方法の一つは、当該ルータ機器にとって一意的な数字、つまり自身の識別アドレスを当該ルータ機器にとって局所的な生成時刻またはシーケンス番号（カウンタ）と組み合わせることである。当該生成プロセスはまた、ハッシュ・テーブルの生成を含むことも可能である。
【００３６】
続くステップＳ１６においては、再配置プロセスを制御するための再配置パラメータが決定される。この再配置パラメータは、目標とする（すなわち、望まれる）ネットワーク深さレベルＴＤおよび距離カウンタＣである。以下、当該２つのパラメータＴＤおよびＣの意味について詳細に説明する。予め規定された固定値がパラメータＴＤおよびＣの値として使用されることが可能である。本発明のその他の実施形態においては、目標とするネットワーク深さＴＤおよび距離カウンタＣの値は、先行する再配置要求の成否に依存することも可能である。
【００３７】
続きステップＳ１７においては、ＩＤを含む再配置要求、目標とするネットワーク深さＴＤおよび距離カウンタＣは、アソシエーション要求を受け取ったルータ機器の親に送信される。本発明に係る方法は、ステップＳ１７の後に実行を終了し、当該方法を反復実行することにより、再度ステップＳ１０において、当該ルータ機器は、後続の新たなアソシエーション要求をまた新たに受け付けることが出来るようになる。また、この時点で当該ルータ機器は、図９を参照しながら後述するように上記した再配置要求に対する再配置応答を受け取ることが出来るようになり、あるいは、図７を参照して後述するように、戻りメッセージとして送出された再配置要求又はそれ以外の異なる再配置要求のいずれかを受け取ることが出来るようになる。
【００３８】
送出された再配置要求２０のデータ構造が図６において図示されている。再配置要求２０のデータ構造は２つの部分を備えている。第１の部分は、使用されるネットワーク・プロトコルに依存した一つ以上のヘッダー部を含んでおり、第２の部分は、ペイロード部分であり、実体的な情報を含んでいる。図６において、当該２つの部分は、破線によって分離される形で図示されている。第１の部分は、ＭＡＣヘッダー２１に関するフィールド、コマンド・フレーム・ヘッダー２２に関するフィールドを含んでいる。ペイロード部分は、生成されたＩＤに関するフィールド２３、目標とするネットワーク深さＴＤに関するフィールド２４および距離カウンタＣに関するフィールド２５を含んでいる。
【００３９】
図７は、アドレス空間を再配置する方法全体の中の第２の部分を示すフローチャートである。当該方法のこの部分においては、再配置要求を受け取ったルータ機器の反応動作が実行される。
【００４０】
従って、最初のステップＳ２０においては、例えば、図４のステップＳ１７において送出され、識別番号ＩＤ、目標とするネットワーク深さＴＤおよび距離カウンタＣを含む再配置要求が受信側ルータ機器によって受信される。本発明に係る方法のうち、この図７に示す部分の動作を実行する受信側ルータ機器を図７の記載との関係において、「実行者ルータ」と呼ぶことにする。再び図１に示された具体例に参照すると、ルータ機器３１−０によって参加要求が受信されると、再配置要求は、ルータ機器３１−０の親ルータであるルータ機器３０−０に送信され、上記説明より、このルータ機器は、図７に示された方法ステップに関する「実行者ルータ」である。
【００４１】
続くステップＳ２１においては、「実行者ルータ」は距離カウンタＣがゼロよりも大きいか否か、および親ルータが存在するか否かをチェックする。両者共に真であれば、本発明に係る方法は、ステップＳ２２に進み、距離カウンタＣはデクリメントされてC’＝Ｃ−１とされる。
【００４２】
続くステップＳ２３においては、再配置要求は、受信した時のままである識別番号ＩＤと目標とするネットワーク深さＴＤおよび上記デクリメントされた距離カウンタC’を含んだ状態で「実行者ルータ」の親ルータに送出される。その後、本発明に係る方法は実行終了する。言い換えるならば、ここで起こっている事象は、再配置要求が階層的木構造の中を根ノードに向かって上向きにルータ機器からルータ機器へと手渡されてゆくということである。距離カウンタＣの初期値は、再配置要求に対する後続の処理に進む前に、再配置要求がネットワーク階層レベルの何段階上まで上向きに伝搬するかを記述している。従って、距離カウンタＣの初期値は、再配置要求の到達範囲を定め、また、アドレス空間の再構成が起こり得る論理的な範囲をも定めている。
【００４３】
ステップＳ２１において、距離カウンタＣの値がゼロに等しい、または木構造内の根ノードに既に到達していること等により親ルータが存在しない場合には、本発明に係る方法は、ステップＳ２４に進む。
【００４４】
ステップ２４およびそれ以降のステップにおいて実行される再配置要求に対する反応動作は、「実行者ルータ」の子ルータが位置するネットワーク深さレベルＤと比較した時の目標とするネットワーク深さＴＤの大きさに主として依存するようになる。図４のステップＳ１２およびＳ１３で記述され、さらに図５に示されたように、親ルータからアドレス・ブロックを子ルータへと割り当てる際のアドレス空間の分割動作に関する標準化された手順に起因して、一のルータ機器に割り当てられたアドレス空間１０は、当該ルータ機器が位置するネットワーク深さレベルＤに依存する。より具体的に言うと、一のルータ機器のネットワーク深さレベルＤと割り当てられたアドレス空間のサイズは、互いに全単射の依存関係にある。
【００４５】
再配置要求パラメータとしての目標とするネットワーク深さＴＤは、要求されるアドレス空間のサイズを決定するのに使用される。より具体的には、目標とするネットワーク深さＴＤは、ネットワーク深さレベルがＤ＝ＴＤとなるルータ機器が自身のアドレス空間として有するサイズと同一のサイズを有するアドレス空間の要求を表す。目標とするネットワーク深さＴＤの観点から要求されるアドレス空間サイズを特徴付けることにより、標準化されたアドレス空間分割手順に適合するようなアドレス空間サイズのみが要求され、割り当てられる。アドレス空間がこれ以外の他の単位、例えばバイト単位で要求されるならば、再配置過程において「これから参加しようとするルータ機器」に対してアドレス・ブロックの一部分しか割り当てられないという状況が生じ、その結果、当該アドレス・ブロックの中の割り当てられずに残った部分は未割り当てのままとなり、さらに悪いことに、当該未割り当て部分のサイズが小さ過ぎる場合には、利用不可能な部分となってしまう可能性まである。要求されるアドレス空間のサイズを特徴記述するために、目標とするネットワーク深さＴＤを使用することにより、全てのアドレス・ブロックは、標準化されたアドレス空間分割方式により生成されるブロック・サイズに対して互換性を有することが保証される。
【００４６】
従って、ステップＳ２４においては、「実行者ルータ」は目標とするネットワーク深さＴＤとして要求された値がその子ルータのネットワーク深さレベルＤと等しいか否かをチェックする。言い換えれば、「実行者ルータ」は、要求されたアドレス空間のサイズと自身が保有するアドレス・ブロックのサイズとが等しいか否かをチェックする。この条件に該当する場合、本発明に係る方法は、ステップＳ２５に進む。
【００４７】
ステップＳ２５においては、当該ルータ機器は、未割り当てのアドレス・ブロックが依然として利用可能であるか否かをチェックする。ステップＳ２５の結果に応じて、再配置応答に関するパラメータがステップＳ２６またはＳ２７においてそれぞれ決定される。未割り当てのアドレス・ブロックが利用可能である場合は、成功フラグＳＦの値が１に設定される。さらに、当該未割り当てのアドレス・ブロックを記述するパラメータ、例えば開始アドレスＡＳおよび終端アドレスＡＥ等が決定される。未割り当てのアドレス・ブロックが利用可能ではない場合は、成功フラグＳＦの値が０に設定され、アドレス・ブロックのパラメータＡＳおよびＡＥに関する値が０に設定されるか又は一切定義されないかのいずれか一方となる。どちらの場合であっても、本発明に係る方法は、ステップＳ２８に進み、再配置応答が実際に発行される。再配置応答は、再配置要求に関して受信した識別番号ＩＤ、（成功フラグＳＦの値が１に設定されている場合は特に）成功フラグＳＦの値、開始アドレスＡＳの値、および終端アドレスＡＥの値を含んでいる。再配置応答は、「実行者ルータ」が受け取った再配置要求の発行元であるルータ機器に対して送信されることが可能である。このようにして、再配置応答は、図９を参照しながら以下において詳細に後述するように、一番最初に再配置要求を発行したルータ機器に向けて戻る方向に一段階ずつ伝搬して行く。他の選択肢として、一番最初に再配置要求を発行したルータ機器に向けて直接的に再配置応答を送信することも可能である。このような事は、ルータ機器間の通信が階層型アドレス木構造中の経路に沿った通信に限定されないメッシュ構造型のネットワーク・システムにおいて可能である。
【００４８】
再び図１の具体例を参照すると、再配置要求は、目標とするネットワーク深さＴＤの値を１とし、距離カウンタＣの初期値を０としてルータ機器３１−０によって送信されている。ルータ機器３０−０は、利用可能な未割り当てのアドレス・ブロック（ノード２１−１に割り当てられるべきブロック）を有し、かつ、目標とするネットワーク深さＴＤ＝１と等しいネットワーク深さレベルＤ＝１となる子供ノードを有することにより、「実行者ルータ」としてのルータ機器３０−０は、ＳＦフラグが１に設定され、アドレス・ブロックのパラメータＡＳおよびＡＥを与える再配置応答をルータ機器３１−０に対して今回送信する。
【００４９】
図８は、再配置応答３０の図式的な表現を示す図である。図６に示した再配置要求２０とのアナロジーに従って、再配置応答３０は、ＭＡＣヘッダー３１とコマンド・フレーム・ヘッダー３２を含むヘッダー部分、および、ＩＤに関するフィールド３３、成功フラグＳＦに関するフィールド３６、開始アドレスＡＳと終端アドレスにそれぞれ関係するフィールド３７と３８を備えるペイロード部分とを備えている。
【００５０】
ステップＳ２４において、目標とするネットワーク深さＴＤとして要求された値と、「実行者ルータ」の子ルータが位置するネットワーク深さレベルＤとが等しくないと判定された場合、本発明に係る方法は、ステップＳ２９に進む。ステップＳ２９においては、子ルータが「実行者ルータ」に割り当てられているか否か、および目標とするネットワーク深さＴＤが「実行者ルータ」の子ルータに関するネットワーク深さレベルＤよりも大きいか否かが判定される。
【００５１】
この条件に該当する場合、ステップＳ３０において、再配置要求は「実行者ルータ」の最初の子供に対して転送される。この事は、要求されたアドレス空間が「実行者ルータ」のアドレス空間よりも小さい場合（即ち、目標とするネットワーク深さＴＤの値がより大きい場合に相当する）、要求されたアドレス空間のサイズがルータ機器のアドレス空間のサイズと等しくなるまで、当該再配置要求は、木構造内において下方向に向かって送信されてゆく。この仕組みは、アドレス空間のフラグメンテーションを回避するためのもう一つの手段である。
【００５２】
ステップ２９において、子ルータが存在しないと判定されるか、または目標とするネットワーク深さＴＤが「実行者ルータ」の子ルータに関するネットワーク深さレベルＤよりも大きくないと判定されたならば、再配置要求は、「実行者ルータ」がステップＳ２０において受け取った再配置要求の発行元であるルータ機器に戻される。いずれの場合であっても、ステップＳ３０またはＳ３１の後に、本発明に係る方法は実行終了し、当該方法を反復実行することにより、再度ステップＳ２０において、「実行者ルータ」は、後続の新たなアソシエーション要求をまた新たに受け付けることが出来るようになる。また、この時点で「実行者ルータ」は、図９を参照しながら後述するように上記した再配置要求に対する再配置応答を受け取ることが出来るようになり、あるいは、図４を参照して上述したように、アソシエーション要求を受け取ることが出来るようになる。
【００５３】
図９は、アドレス空間を再配置する方法全体の中の第３の部分を示すフローチャートである。本発明に係る方法のこの部分は、一のルータ機器が再配置応答を受信した際の反応動作を説明する。
【００５４】
従って、本発明に係る方法のこの部分は、最初のステップＳ４０において受信側ルータ機器により再配置応答を受信するところから始まり、当該再配置応答は、識別番号ＩＤ、成功フラグＳＦ、開始アドレスＡＳおよび終端アドレスＡＥによって特徴付けられる。本発明に係る方法のうち図９に示された部分を実行する受信側ルータ機器のことをこの図９の記載との関連において再度「実行者ルータ」と呼ぶことにする。
【００５５】
続くステップＳ４１においては、「実行者ルータ」は、自分自身がこの再配置応答の原因となった再配置要求を発行したか否かを判定する。これは、再配置応答に含まれる識別番号ＩＤに基づいて実行することが可能である。対応する再配置要求が当該ルータ機器自身によって発行されたものではない場合、本発明に係る方法はステップＳ４２に進む。そうでなければ、本発明に係る方法は、ステップＳ４８に進む。
【００５６】
ステップＳ４２においては、成功フラグＳＦが評価される。当該フラグの値として１が含まれていれば、再配置要求に対して肯定的な応答がされたことを意味し、本発明に係る方法は、ステップＳ４３に進む。このステップにおいては、「実行者ルータ」の経路制御テーブル（ルーティング・テーブル）が更新される。続くステップＳ４４では、図４に示した本方法の以前の実行過程中のステップＳ２０において「実行者ルータ」が受信した再配置要求の発行元であるルータ機器に対して再配置応答がさらに転送される。言い換えるならば、再配置応答は、当該再配置要求を一番最初に発行したルータ機器へと戻る方向に向かってネットワーク内を伝搬する。当該再配置応答は、当該再配置要求と同一の伝搬経路に沿っているけれども、当該再配置要求とは逆方向に伝搬する。ネットワーク内で交換され「これから参加しようとするルータ機器」へと向かう後続のメッセージが、一切のアドレス発見ルーチンを実行すること無しに「これから参加しようとするルータ機器」に対して直接的に送信され得るようにすることにより、ステップＳ４３での戻り方向に伝搬するルーティング・テーブルの更新動作は、さらに技術的利点を有することとなる。
【００５７】
ステップＳ４２において、（ＳＦの値が０である）否定的な応答が検出された場合、本発明に係る方法は、ステップＳ４５に進み、「実行者ルータ」は、図７に示したステップＳ３０の動作とのアナロジーに従って、再配置要求が転送され得るさらに多くの子ルータが存在するか否かをチェックする。さらに多くの子ルータが存在する場合、本発明に係る方法は、ステップＳ４６に分岐し、図７のステップＳ２０において受信された再配置要求は、その次の子ルータへと転送され、この時、識別番号ＩＤ、目標とするネットワーク深さＴＤ、およびこの場合に値がゼロに等しい距離カウンタＣに関するパラメータ群は変更されない。このようにして、ステップＳ４５とＳ４６は、図７中のステップＳ３０との関連において説明したアドレス空間のフラグメンテーションをさらに回避するために、再配置要求が木構造内を下方向に伝搬する可能な処理フローを完成させる。
【００５８】
さらに多くの子ルータが全く存在しない場合、本発明に係る方法はステップＳ４７に進み、ステップＳ４０において受信された再配置応答は、そのパラメータ群を変更しないまま、否定的な応答として、受信した再配置要求の発行元であるルータ機器に対して転送される。従って、ステップＳ４３およびＳ４４と同様に、ステップＳ４５およびＳ４７は、当該再配置要求を一番最初に発行したルータ機器へと戻る方向に向けて当該再配置応答を転送するという目的を有する。
【００５９】
もしも、ステップＳ４１において、受信した再配置応答が所属している再配置要求は、現在のルータ機器が自分自身で発行した再配置要求である事が発見されたならば、本発明に係る方法は、ステップＳ４８に進む。ステップＳ４８においては、再配置応答の成功フラグＳＦが評価される。成功フラグＳＦの値が１となる肯定的な再配置応答であった場合には、本発明に係る方法は、ステップＳ４９に進み、現在のルータ機器のルーティング・テーブルがステップＳ４３とのアナロジーに従って更新される。そして最後に、続くステップＳ５０において、アドレス・ブロックのパラメータである開始アドレスＡＳと終端アドレスＡＥを含んでいるアソシエーション応答が「これから参加しようとするルータ機器」に対して送信され、当該「これから参加しようとするルータ機器」は、図４中のステップＳ１０において受信されるアソシエーション要求を発行したルータ機器である。
【００６０】
一連のステップＳ４０、Ｓ４１、Ｓ４８、Ｓ４９およびＳ５０から成る動作シーケンスは、図１に示す具体例にあっては、図７中のステップ２８において、ルータ機器３１−０により発行された肯定的な再配置応答をルータ機器３１−０が受信することとなる場合に実行される。
【００６１】
もしも、ステップＳ４８において、ＳＦが０に等しい否定的な再配置応答が検出された場合、本発明に係る方法は、ステップＳ５１に進む。ステップＳ５１においては、新しい再配置要求に関して、新しい識別番号ＩＤ＊が生成される。続くステップＳ５２においては、目標とするネットワーク深さの新しいパラメータであるＴＤ＊および距離カウンタの新しいパラメータであるＣ＊を含む新しい再配置パラメータが追加的に決定される。
【００６２】
当然ながら、再配置パラメータの値は、再配置要求の成否に対して大きな影響を与える。例えば、計算時間と計算パワーを節約するために、再配置要求は、最初のうちは、距離カウンタの値を小さく設定して発行されることが可能である。その結果、再配置要求は要求発行元のルータ機器から見て非常に近接した範囲内においてのみ伝搬することとなる。その結果、目標とするネットワーク深さＴＤによって特徴付けられる適切なサイズのアドレス・ブロックがネットワーク内に存在したとしても、これらをネットワーク内から見つけることが出来ない可能性がある。何故ならば、これらのアドレス・ブロックは、再配置要求の伝搬範囲の外に存在し、未割り当てのアドレス・ブロックの存否に関してチェックを受けていないルータ機器に所属している可能性があるからである。同様の方法により、再配置要求は、最初のうちは、目標とするネットワーク深さＴＤの値を小さく設定して発行されることが可能であり、これは要求するアドレス空間のサイズを比較的大きく設定する場合と等価である。このように設定された再配置要求が否定的な再配置応答を返された場合であったとしても、より小さなサイズのアドレス空間の獲得のみを狙って、目標とするネットワーク深さＴＤの値をより大きく設定した新しい再配置要求を発行すれば、結果として肯定的な応答を返される可能性がある。
【００６３】
再配置要求のパラメータを決定するための複数の異なる戦略を本発明において実装することが可能であり、これらの戦略は、以下のような互いに競合する複数の目標同士の間でトレードオフを生じる。そのような目標の一つは、ネットワーク内の全てのデバイスを接続するのに必要な再配置の実行回数を最小化するというものであり、もう一つの目標は、ルーティング・テーブル内のエントリの総数を最小化するというものであり、さらに別の目標は、例えば、一回の再配置実行プロセスにおいて伝送される再配置要求と再配置応答の個数を最小化するというものである。
【００６４】
複数の所望される目標の重みに応じて、第１の戦略は、まず最初に目標とするネットワーク深さの値ＴＤ＝１を使用して大きなアドレス空間を割り当てることを試み、続いて、再配置が成功するまで、目標とするネットワーク深さの値を連続的に増加させてゆくものである。このようにして、ネットワークの最大の深さは急速に増加してゆき、特に一連のルータ機器の長い連鎖を有するネットワークは、非常に少ない回数の再配置実行プロセスのみを必要とするだろう。
【００６５】
第２の戦略は、まず最初にネットワーク内に現存する最大の深さ値を使用してアドレス・ブロックの探索を行い、目標とする深さ値を連続的に減少させてゆくことにより、依然として利用可能な最小サイズのアドレス・ブロックを再配置するというものである。この戦略は、数多くの子ルータを有する親ルータが殆ど存在しないネットワークにおいて好適である。
【００６６】
上述した２つの戦略の間のトレードオフ解は、以下に述べる第３の戦略によって与えられる。この第３の戦略は、図４のステップＳ１２およびＳ１３との関連において上述したアドレス空間の分割動作に関する標準化された手順によって予め規定される木構造をそのまま維持しようと試みるものである。この第３の戦略を実施する場合、一のルータ機器は、自分自身に既に接続されている自身の子ルータに与えられたアドレス・ブロックと同一サイズのアドレス・ブロックをまず最初に要求する。このようにして、当該木構造はそのまま維持される。
【００６７】
全ての場合および全ての戦略に関して、探索動作は、まず最初に要求発行元のルータ機器の近傍から実行されなくてはならない。つまり、探索動作は、まず最初に、距離カウンタＣの初期値を例えば０または１のような小さい値に設定して開始されなくてはならない。これ以降の探索動作においては、距離カウンタＣの初期値は必要に応じて段階的にのみ増加させてゆくべきである。
【００６８】
ステップＳ５２において、上述した再配置戦略またはさらに別の再配置船楽のいずれか一つに従って新しい再配置パラメータを決定した後に、ステップＳ５３において、新しいＩＤ＊および新しい再配置パラメータＴＤ＊およびＣ＊を含む新しい再配置要求が「実行者ルータ」の親ルータに対して送信される。
【００６９】
本発明に係る代替的な実施形態においては、いわゆる刈り取りテーブルと呼ばれるものがネットワーク内に新たに設けられる。当該刈り取りテーブルは、未使用のアドレス・ブロックを発見するための探索プロセスを高速化するものであり、特に、これらのアドレス・ブロックがより高いネットワーク深さに相当するネットワーク階層に位置している時に有効である。
【００７０】
既に述べたように、図７中のステップＳ２９とＳ３０は、図９中のステップＳ４５およびＳ４６と組み合わさることにより、未使用のアドレス・ブロックを目当てにした再帰反復的な探索動作を結果としてもたらし、この探索動作は、根ノードの方向に向かう再配置要求の直接伝搬経路から出発し、その結果、木構造内を下方向へ向かう探索動作を可能にする。
【００７１】
刈り取りテーブルは、一の特定のルータ機器の子孫である最も低い深さ位置にある子ルータのネットワーク深さ値を含んでいる。当該刈り取りテーブルは、この値を常に含むように連続的に更新され、この値は、当該ルータ機器の子供とその子孫によって再配置され得る最大のアドレス・ブロック・サイズを特徴付けている。デフォルトの状態において、新たに接続された子ルータに関する刈り取りテーブル内の当該値は当該子ルータが位置するネットワーク深さの値に１を加算した値として設定される。この子ルータよりも下に位置するネットワーク階層において、より大きなアドレス・ブロックの任意の新たな再配置動作が起きた場合、刈り取りテーブル内の値は更新される。後続の更なる再配置要求においては、複数のルータ機器は、図７のステップＳ３０および図９のステップＳ４６における再配置要求の転送動作を、当該再配置要求に関する目標とするネットワーク深さ値ＴＤと等しいかより小さい刈り取りテーブル値と関係付けられている子ルータに対してだけ実行する必要がある。再配置応答を処理する場合には、肯定的な再配置応答によって、以前に利用可能であったアドレス・ブロックが割り当てられたか割り当てられようとしている場合に、当該刈り取りテーブル中の値を更新することが可能である。
【００７２】
上記の記述および添付図面を使用して本発明の実施例が例示され、本発明の内容が説明されてきたけれども、そのような例示や説明は、単なる具体例又は例示的なものに過ぎず、本発明の範囲を制限するものではないと看做されるべきであり、本発明の技術的範囲は、本明細書に開示された実施形態にのみ限定されるものではない。本明細書の開示、本明細書に添付した図面、特許請求の範囲を熟読することにより、本明細書において特許請求されている発明を実施しようとする当業者は、本明細書に開示された実施形態以外の多種多様な変形実施例を自明なものとして理解し、実施することが出来る。本明細書に添付した請求項の記載において、用語「備える」は、他の構成要素や他の処理ステップを含み得る可能性を除外するものではない。複数の特定の仕組みや構造が互いに異なる従属請求項に記載されているという事実は、これらの仕組みや構造を互いに組み合わせることが不可能であったり、有意義ではないということを意味しない。
【図１】
2013522997.tif 000003
【図２】
2013522997.tif 000004
【図３】
2013522997.tif 000005
【図４】
2013522997.tif 000006
【図５】
2013522997.tif 000007
【図６】
2013522997.tif 000008
【図７】
2013522997.tif 000009
【図８】
2013522997.tif 000010
【図９】
2013522997.tif 000011
【手続補正書】
【提出日】平成25年2月20日(2013.2.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
階層的アドレス付与方式を有するピア・ツー・ピア型ネットワークにおいてアドレス空間を再配置する方法であって、前記ネットワークは、複数の異なるネットワーク深さに位置するルータ機器をノードとして有する木構造を有し、
前記ルータ機器の各々は、自身に割り当てられたアドレス空間を有し、前記アドレス空間は、前記ルータ機器の各々を識別するアドレス、子ルータに割り当てるべきアドレス空間を供給するための一つ以上のアドレス・ブロックおよび複数のエンド・デバイスに対してそれらの識別アドレスを供給するための追加のアドレス・ブロックを含み、
再配置することなしに一のルータ機器に割り当てられるアドレス空間のサイズは、所定の方法に従って前記一のルータ機器が位置するネットワーク深さに依存し、その結果、前記一のルータ機器に、特定のサイズのアドレス空間が割り当てられ、
当該方法は、
アドレス空間が枯渇した第１のルータ機器が、参加しようとするルータ又は参加しようとする端末装置からの参加要求を受信するステップ；および、
前記ネットワーク内の第２のルータ機器に対して、再配置要求を送信するステップであって、前記再配置要求は、要求されるアドレス・ブロックのサイズを表し、前記要求されるアドレス・ブロックの前記サイズは、所定のアドレス空間サイズのいずれか一つと等しい、ステップ；
を備える方法。
【請求項２】
前記再配置すること無しに一のルータ機器に割り当てられる前記アドレス空間の前記サイズは、全単射的な方法に従って前記一のルータ機器が位置するネットワーク深さに依存し、前記再配置要求は、目標とするネットワーク深さ（ＴＤ）により表される前記要求されるアドレス・ブロックの前記サイズを表す、請求項１記載の方法。
【請求項３】
前記第２のルータ機器は、前記第１のルータ機器の親である請求項１または２のいずれかに記載の方法。
【請求項４】
前記再配置要求は、距離カウンタ値（Ｃ）を含み、前記再配置要求を受け取った前記第２のルータ機器は、
前記距離カウンタ値（Ｃ）がゼロに等しいか否かを判定するステップ；
前記距離カウンタ値（Ｃ）がゼロに等しくないと判定されたならば、前記距離カウンタ値（Ｃ）を１だけ減算した上で、前記第２のルータ機器の親である第３のルータ機器に対して、前記再配置要求を転送するステップ；および、
前記距離カウンタ値（Ｃ）がゼロに等しいと判定されたならば、前記再配置要求に対して行うべき後続の処理を実行するステップ；
をさらに実行することを備える、請求項１から請求項３のいずれか一つに記載の方法。
【請求項５】
前記再配置要求に対して行うべき前記後続の処理を実行する前記ステップは、
前記目標とするネットワーク深さ（ＴＤ）が前記第２のルータ機器の配下にある複数の可能な子ルータが位置するネットワーク深さと等しいか否かを判定するステップ；
もしもそうなら、前記目標とするネットワーク深さ（ＴＤ）の値に従って要求されるサイズを有する少なくとも一つの未割り当てアドレス・ブロックが利用可能であるか否かを判定するための利用可能性検査を実行し、前記利用可能性検査の結果を含み、かつ、前記少なくとも一つのみ割り当てのアドレス・ブロックが利用可能な場合は、前記未割り当てのアドレス・ブロックのそれぞれを記述するパラメータをも含んでいる再配置応答を発行するステップ；および、
そうでなければ、前記再配置要求に対して行うべきその先の処理を実行するステップ；
をさらに備える、請求項４記載の方法。
【請求項６】
前記未割り当てのアドレス・ブロックを記述するパラメータは、開始アドレス（ＡＳ）および終端アドレス（ＡＥ）を備える請求項５記載の方法。
【請求項７】
前記目標とするネットワーク深さ（ＴＤ）が前記第２のルータ機器の配下にある複数の可能な子ルータが位置するネットワーク深さと等しくないと判定された場合、前記再配置要求に対して行うべき前記その先の処理を実行する前記ステップは、
前記第２のルータ機器の配下にある子ルータが存在するか否か、および前記目標とするネットワーク深さ（ＴＤ）が前記第２のルータ機器の配下にある複数の子ルータが位置するネットワーク深さよりも大きいか否かを判定するステップ；
上記に該当する場合、前記第２のルータ機器の配下にある一の子ルータに対して前記再配置要求を転送するステップ；および、
上記に該当しない場合、前記再配置要求を戻すステップ；
をさらに備える、請求項５または請求項６のいずれか一方に記載の方法。
【請求項８】
前記利用可能性検査に関する肯定的な結果を含む再配置応答が発行されるまで、前記第２のルータ機器の配下にある子ルータの各々に対して、前記再配置要求を連続的に転送する、請求項７記載の方法。
【請求項９】
請求項５から請求項８までのいずれか一つに記載された方法であって、一のルータ機器が前記再配置応答を受信した後に、
前記一のルータ機器は前記再配置要求を発行した最初のルータ機器であり、かつ、前記再配置要求は前記再配置応答が参照している再配置要求であるか否かを判定するステップ；
上記に該当する場合、前記再配置応答が前記利用可能性検査の肯定的な結果を表しているならば、前記アドレス・ブロック・パラメータを備える肯定的な応答を前記参加しようとするルータ機器に対して送信し、前記再配置応答が前記利用可能性検査の否定的な結果を表しているならば、新たな再配置要求を発行するステップ；および、
上記に該当しない場合、前記再配置応答が前記利用可能性検査の肯定的な結果を表しているならば、前記最初のルータ機器に向けて前記再配置応答を転送し、前記再配置応答が前記利用可能性検査の否定的な結果を表しているならば、前記再配置応答を戻すステップ；
をさらに実行することを備える、方法。
【請求項１０】
新たな再配置要求は、前記目標とするネットワーク深さ（ＴＤ）および／または前記距離カウンタ（Ｃ）に関して異なる値を使用する点で、後続の更なる再配置要求とは異なっている、請求項９記載の方法。
【請求項１１】
一の再配置要求に関する前記目標とするネットワーク深さ（ＴＤ）および／または前記距離カウンタ（Ｃ）の値は、所定の再配置戦略に従って決定される、請求項１から請求項１０までのいずれか一つに記載された方法。
【請求項１２】
ルータ機器の各々に関して、特定のルータ機器の子孫であって、最も低い深さの子ルータが位置するネットワーク深さの値を備える刈り取りテーブルを維持管理する、請求項１から請求項１１までのいずれか一つに記載された方法。
【請求項１３】
前記ネットワーク内の全てのルータ機器によって再帰反復的に実行される、請求項１から請求項１２までのいずれか一つに記載された方法。
【請求項１４】
前記ネットワーク内においてZigBee標準規格に従って実行される、請求項１から請求項１３までのいずれか一つに記載された方法。
【請求項１５】
階層的アドレス付与方式を有するピア・ツー・ピア型ネットワークにおいて使用されるルータ機器であって、請求項１から請求項１４までのいずれか一つに記載された方法に従ってアドレス空間を再配置する方法を実行することに適合したルータ機器。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
Zigbeeアライアンス2007年発行のZigbee標準仕様書における第3.6.1.6節、第370ページ〜第372ページに記載されているように、ZigBee標準規格は、複数のアドレスが分散的な態様で割り振られる階層型の方式を提案している。ZigBee標準規格は、物理リンク層（ＰＨＹ）および媒体アクセス制御層（ＭＡＣ）を定義するIEEE  802.15.4通信プロトコルに基づいたオープンな標準規格である。これらのプロトコル層に加えて、ZigBee標準規格は、ＰＨＹ層およびＭＡＣ層の上位に位置するネットワーク層とアプリケーション層を定義する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
上記した標準的なアドレス割り当て手順によって課される制限を克服するために、アドレス空間の再配置の仕組みが提案されている。例えば、以下の特許文献１は、新たなルータ機器からネットワークに参加するための要求を受け取ったルータ機器がその親ルータへ、さらにその祖先のルータへと階層的アドレス木構造の中を根ノードの方向に向かって再配置要求を送出する。当該再配置要求の送出は、これらのルータ機器の中のいずれかが利用可能な未割り当てアドレスを有しているか否かを問い合わせるために実行される。続いて、ネットワークへの参加要求を受け取ったルータ機器を介して当該新たなルータ機器に対して未割り当てのアドレスが割り当てられる。上記のようにして、アドレス空間は、論理的な意味で再配列され、あるいは再配置され、その結果、上記した分割手順によって予め定められていた元々の個数よりも多くの子供をルータ機器が持つことが出来る可能性を与える。その他のアドレス空間再配置の仕組みは、米国特許公開公報US2009/006596に記載され、この文献においては、利用可能なアドレス空間を全く持たない親の配下にルータ・ノードが参加しようと試みる場合、当該親は、子供ルータ・ノードからの、あるいは場合によっては、ネットワーク全体からの利用可能なアドレス空間の割り当てを要求する。利用可能なアドレス空間を発見し得る場合、それは割り当て解除されてネットワークに参加することを希望する上記ルータ・ノードに再度割り当てられる。上記した再配置手順の欠点は、フラグメント化されたアドレス空間を結果としてもたらしてしまう事である。
【国際調査報告】
2013522997.tif 000012
2013522997.tif 000013
2013522997.tif 000014