(57)【要約】【課題】アドホック、自己形成ピアツーピア（Ｐ２Ｐ）ネットワーク用のインターネットプロトコル（ＩＰ）アドレス割り当てを管理するための論理的分配サーバを生成する。【解決手段】論理的分散サーバは、Ｐ２Ｐネットワーク上のノードが自身およびそれに接続するクライアントに対するアドレスを割り当てるメッセージングスキームに従って生成する。各ノードは着信クライアント接続上でリスンするサーバを実装する。各ノードはアドレスデータベースの現在の状態を表すデータ構造を維持する。クライアントからのルーティング要求はノードが処理し、メッセージングスキームを他のノードにその行動を通知するのに使用し、それによってＰ２Ｐネットワーク上のすべてのノードの間に一貫したアドレス空間を維持する。【選択図】図４
2006148913.tif 000002
【特許請求の範囲】
【請求項１】
管理されたネットワークサービスが不在のときに、ルーティングされたＩＰアドレス空間を協調的に管理するためのコンピュータ実施方法であって、前記方法は、
バックボーンネットワーク上の協調エージェントを識別すること、
バックボーンネットワーク上の現在の協調エージェント用のバックボーンアドレスを選択すること、
現在の協調エージェントに対応するクライアントサブネットアドレスを選択すること、および
前記クライアントサブネットアドレス選択のための前記バックボーンネットワーク上の他の協調エージェントを通知すること
を備えることを特徴とするコンピュータ実施方法。
【請求項２】
前記バックボーンネットワーク上の協調エージェントを識別することは、メッシュネットワーク上のメッシュボックスを識別することをさらに含むことを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項３】
前記バックボーンネットワーク上の協調エージェントを識別することは、他の協調エージェントが現在の協調エージェントの通信範囲内にあるかどうかを判定する発見メッセージをブロードキャストすることをさらに含むことを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項４】
前記発見メッセージは、現在の協調エージェント用のバックボーンアドレスのランダムに選択した部分のインジケーションを、他の協調エージェントが選択したバックボーンアドレスの同一部分との比較のために含むことを特徴とする請求項３に記載のコンピュータ実施方法。
【請求項５】
現在の協調エージェント用の前記バックボーンアドレスのランダムに選択した部分と、他の協調エージェント用の前記同一部分との間のコンフリクトは、両方の部分を単一の共通値に設定することにより解消することを特徴とする請求項４に記載のコンピュータ実施方法。
【請求項６】
前記現在の協調エージェントは、前記発見メッセージをブロードキャストして他の協調エージェントからの応答を受信した後、指定された時間間隔の間は待機していることを特徴とする請求項３に記載のコンピュータ実施方法。
【請求項７】
前記バックボーンアドレスを選択する前に、現在の協調エージェントと近隣の協調エージェントに対応するルーティングテーブルを取得することをさらに備え、前記ルーティングテーブルは、近隣の協調エージェントによるアドレスの割り当てを含むことを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項８】
他の協調エージェントを通知することは、近隣の協調エージェントへ割り当てメッセージをブロードキャストすることをさらに含み、前記割り当てメッセージは、前記クライアントサブネットアドレスが現在の協調エージェントにより割り当てられていることを示すインジケータを含むことを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項９】
選択した時間間隔が経過した後、近隣の協調エージェントへ追加の割り当てメッセージをブロードキャストすることをさらに備え、前記追加の割り当てメッセージは、前記クライアントサブネットアドレスが現在の協調エージェントにより使用中であることを示すインジケータを含むことを特徴とする請求項８に記載のコンピュータ実施方法。
【請求項１０】
クライアントルーティング要求に応答して、前記クライアントサブネットアドレスから未使用のサブネット値を選択することをさらに備えることを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項１１】
クライアントルーティング要求の後、残りの未使用のサブネット値の数を判定することをさらに備え、追加のクライアントサブネットアドレスは、残りの未使用のサブネット値の数が指定された閾値未満の場合、現在の協調エージェントにより割り当てられることを特徴とする請求項１０に記載のコンピュータ実施方法。
【請求項１２】
他方の協調エージェントから、割り当てられたクライアントサブネットアドレスの通知を受信することをさらに備えることを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項１３】
前記受信した通知が適切かどうかを判定すること、
前記受信した通知が適切であると判定されたときに、前記受信した通知を近隣の協調エージェントへ転送すること、および
前記受信した通知が不適切であると判定されたときに、前記受信した通知を破棄することをさらに備えることを特徴とする請求項１２に記載のコンピュータ実施方法。
【請求項１４】
前記受信した通知は、前記受信した通知内に含むタイムスタンプと前記受信した通知に関連するホップカウントのうち、少なくとも１つに従って判定されることを特徴とする請求項１３に記載のコンピュータ実施方法。
【請求項１５】
前記受信した通知は、前記タイムスタンプがローカルヴァージョンのタイムスタンプよりも遅れて発生するときに、適切であることを特徴とする請求項１４に記載のコンピュータ実施方法。
【請求項１６】
前記受信した通知は、ホップカウントが選択されたホップリミットよりも大きいときに、不適切であることを特徴とする請求項１４に記載のコンピュータ実施方法。
【請求項１７】
管理されたネットワークサービスが不在のときに、ルーティングされたＩＰアドレス空間を協調的に管理するためのコンピュータ実行可能命令を含むコンピュータ可読媒体であって、前記命令は、
メッシュネットワーク上の隣接メッシュノードを識別すること、
いずれかの隣接するメッシュノードに対応し、隣接メッシュノードによるアドレス割り当てを含むルーティングテーブルを取得すること、
前記メッシュネットワーク上の現在のメッシュノード用のメッシュ面のアドレスを選択すること、
現在のメッシュノードに対応するアドレスのクライアントサブネットの範囲を選択すること、および
現在のメッシュノードによるクライアントサブネットの範囲の選択のための前記メッシュネットワーク上の他のメッシュノードを通知すること
を備えることを特徴とするコンピュータ可読媒体。
【請求項１８】
前記メッシュネットワーク上のメッシュノードを識別することは、他のメッシュノードが、現在のメッシュノードの通信範囲内にあるかどうかを判定する発見メッセージをブロードキャストすることをさらに含むことを特徴とする請求項１７に記載のコンピュータ可読媒体。
【請求項１９】
前記発見メッセージは、現在のメッシュノード用のメッシュ面のアドレスのランダムに選択した部分のインジケーションを、他のメッシュノードにより選択されたメッシュ面のアドレスの同一部分との比較のために含むことを特徴とする請求項１８に記載のコンピュータ可読媒体。
【請求項２０】
他のメッシュノードを通知することは、割り当てメッセージを隣接メッシュノードへブロードキャストすることをさらに含み、前記割り当てメッセージは、前記クライアントサブネットの範囲が、現在のメッシュノードにより割り当てられていることを示すインジケータを含むことを特徴とする請求項１７に記載のコンピュータ可読媒体。
【請求項２１】
選択した時間間隔が経過した後、隣接メッシュノードへ追加の割り当てメッセージをブロードキャストすることをさらに備え、前記追加の割り当てメッセージは、前記クライアントサブネットアドレスが現在のメッシュノードにより使用中であることを示すインジケータを含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２２】
管理されたネットワークサービスが不在のときに、ルーティングされたＩＰアドレス空間を協調的に管理するためのシステムであって、
その中に含まれるメッシュノードを有するメッシュネットワークと、
各々のメッシュノード上でコンピュータ実行可能命令を実行する構成のメッシュネットワーク全体にわたって分散された論理サーバとを備え、前記コンピュータ実行可能命令は、
他のメッシュノードが、現在のメッシュノードの通信範囲内にあるかどうかを判定する発見メッセージをブロードキャストすることにより、前記メッシュネットワーク上の隣接メッシュノードを識別すること、
いずれかの隣接メッシュノードに対応し、前記隣接メッシュノードによるアドレス割り当てを含むルーティングテーブルを取得すること、
前記メッシュネットワーク上の現在のメッシュノード用のメッシュ面のアドレスを選択すること、
現在のメッシュノードに対応するアドレスのクライアントサブネット範囲を選択すること、および
割り当てメッセージを、前記隣接メッシュノードへブロードキャストすることにより、前記クライアントサブネット選択のための前記メッシュネットワーク上の他のメッシュノードを通知することを備え、前記割り当てメッセージは、現在のメッシュノードにより割り当てられていることを示すインジケータを含むことを特徴とするシステム。
【請求項２３】
前記発見メッセージは、現在のメッシュノード用のメッシュ面のアドレスのランダムに選択した部分のインジケーションを、他のメッシュノードにより選択されたメッシュ面のアドレスの同一部分との比較のために含むことを特徴とする請求項２２に記載のシステム。
【請求項２４】
前記論理サーバは、選択した時間間隔が経過した後、隣接メッシュノードへ追加の割り当てメッセージをブロードキャストする構成になっており、前記追加の割り当てメッセージは、前記クライアントサブネットアドレスが現在のメッシュノードにより使用中であることを示すインジケータを含むことを特徴とする請求項２２に記載のシステム。
【請求項２５】
前記発見メッセージは、現在の協調エージェント用のバックボーンアドレスのランダムに選択した部分のインジケーションを、他の協調エージェントにより選択されたバックボーンアドレスの同一部分との比較のために含むことを特徴とする請求項２２に記載のシステム。
【請求項２６】
現在の協調エージェント用の前記バックボーンアドレスのランダムに選択した部分と、他方の協調エージェント用の前記同一部分との間のコンフリクトは、両方の部分を単一の共通値に設定することにより解消することを特徴とする請求項２５に記載のシステム。
【請求項２７】
前記コンピュータ実行可能命令は、
クライアントルーティング要求に応答して、クライアントサブネットの範囲から、未使用のサブネット値を選択すること、および
前記クライアント要求後、残りの未使用のサブネット値の数を判定することをさらに備え、追加のクライアントサブネットの範囲は、残りの未使用のサブネット値の数が指定された閾値未満である場合に、現在のメッシュノードにより割り当てられることを特徴とする請求項２２に記載のシステム。
【請求項２８】
前記コンピュータ実行可能命令は、
他方の協調エージェントから、割り当てられたクライアントサブネットアドレスの通知を受信すること、
前記受信した通知が適切かどうかを判定すること、
前記受信した通知が適切であると判定されたときに、前記受信した通知を近隣の協調エージェントへ転送すること、および
前記受信した通知が不適切であると判定されたときに、前記受信した通知を破棄することをさらに備えることを特徴とする請求項２２に記載のシステム。
【請求項２９】
前記受信した通知は、前記受信した通知内に含むタイムスタンプと前記受信した通知に関連するホップカウントのうち、少なくとも１つに従って判定されることを特徴とする請求項２８に記載のシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
デバイス間のピアツーピア通信はますます盛んに行われており、ネットワーク通信を提供する方法として定着している。ピアツーピアネットワークは、コンピューティングデバイス群における接続によって緩くバインドされたネットワークであり、これによりコンピューティングデバイスがリソースを直接に共有することができる。多数のピアツーピアネットワークが、他のネットワークインフラストラクチャのバックボーン上に作成されている。通常これらのネットワークインフラストラクチャは、インフラストラクチャがインターネットであれ、または別のローカルネットワークであれ、ある水準の管理を行う。この管理はしばしば、ネットワーク上で宛先をアドレス指定し、これらの宛先に情報をルーティングすることに関与する１または複数のサーバの形態をとる。アドレス指定方式は、宛先をアドレス指定し情報をルーティングするために、１または複数の様々な異なるプロトコルを用いてもよい。例えば、ネットワークインフラストラクチャプロトコルの１つがＤＨＣＰ(Dynamic Host Configuration Protocol)である。ＤＨＣＰは、ＴＣＰ／ＩＰを使用するコンピュータの構成を自動化するためのインターネットプロトコルである。ＤＨＣＰは、自動的にＩＰアドレスを割り当て、サブネットマスクやデフォルトルータのようなＴＣＰ／ＩＰスタック構成パラメータを配信し、タイムサーバに対するアドレスのようなその他の構成情報を提供するのに用いることができる。もともと、ＤＨＣＰを用いるネットワークは、ＤＨＣＰサーバと呼ばれる専用のコンピューティングデバイスによって管理されている。
【発明の開示】
【発明が解決しようとする課題】
【０００２】
標準的なＤＨＣＰを用いるネットワークのような従来モデルは、インフラストラクチャがないところでは機能しない。事前にネットワークインフラストラクチャまたは管理を必要としない、アドホックな自己形成するピアツーピアネットワークの考えは比較的新しく、越えなければならない障害が多数存在する。その障害の１つが、アドレス指定を管理するための専用コンピューティングデバイスがピアツーピアネットワーク上に備わっていないとき、どのようにアドレス指定方式を提供するか、ということである。
【課題を解決するための手段】
【０００３】
本発明の実施形態は、自己形成するピアツーピアネットワーク用の分散サーバを提供するシステムおよび方法に関するものである。本発明の一態様によれば、多数のメッシュボックスまたはメッシュノードを組み合わせてメッシュネットワークを形成する（ここでメッシュネットワークとは、ネットワークの協調エージェントとして働くメッシュボックスを含んでいるピアツーピアネットワークの１タイプである）。このメッシュネットワークにより、既存のネットワーク構造要素（すなわち、専用サーバなど）の要求がなくても、メッシュノードおよびメッシュノードに接続したクライアントの間にデータを転送することができる。本発明は、選択したメッセージングスキームに従うようにメッシュノードを構成することにより、論理的な、データベース主導型の分散サーバを提供する。このメッセージングスキームは、ネットワークおよびクライアントサブネットのアドレス空間の管理に対する責任を、メッシュネットワーク上に含まれるいろいろなメッシュノードにまで拡張する。
【０００４】
本発明の一態様によれば、管理されたネットワークサービスが不在の場合に、ルーティングされたＩＰアドレス空間を協調的に管理するためのコンピュータ実施方法を提供する。本方法は、バックボーンネットワーク上の協調エージェントの識別、バックボーンネットワーク上の現在の協調エージェントに対するバックボーンアドレスの選択、現在の協調エージェントに対応するクライアントサブネットアドレスの選択、およびバックボーンネットワーク上の他の協調エージェントへのクライアントサブネットアドレス選択の通知を含む。
【０００５】
本発明の他の態様によれば、コンピュータ可読媒体が提供され、それはメッシュネットワーク上の隣接メッシュノードを識別し、またどのような隣接メッシュノードにも対応するルーティングテーブルを取得するためのコンピュータ実行可能命令を含む。ルーティングテーブルは隣接メッシュノードが行ったアドレス割り当てを含む。この命令にはさらに、メッシュネットワーク上の現在のメッシュノードに対するメッシュ面のアドレスの選択、現在のメッシュノードに対応するアドレスのクライアントサブネット範囲の選択、およびメッシュネットワーク上の他のメッシュノードへの現在のメッシュノードによるクライアントサブネット範囲選択の通知を含む。
【０００６】
また本発明のさらに他の態様によれば、管理されたネットワークサービスが不在の場合に、ルーティングされたＩＰアドレス空間を協調的に管理するためのシステムは、そこに含まれるメッシュノードを持つメッシュネットワーク、およびメッシュネットワーク内に分散する論理サーバを含み、このサーバは、各メッシュノード上で一連のコンピュータ実行可能命令を実行するように構成されている。各メッシュノードにおいて、サーバ構成は、他のメッシュノードが現在のメッシュノードの通信範囲内にあるかどうかを判定する発見メッセージをブロードキャストすることにより、メッシュネットワーク上の隣接メッシュノードを識別する。それから現在のメッシュノードは、どのような隣接メッシュノードにも対応するルーティングテーブルを取得し、そこではルーティングテーブルは、隣接メッシュノードが行ったアドレス割り当てを含む。それから現在のメッシュノードに対応するアドレスのクライアントサブネット範囲と同様に、メッシュネットワーク上の現在のメッシュノードに対して、メッシュ面のアドレスを選択する。割り当てメッセージを隣接メッシュノードにブロードキャストすることにより、メッシュネットワーク上のその他のメッシュノードにクライアントサブネット範囲選択を通知する。この割り当てメッセージは、現在のメッシュノードによりクライアントサブネット範囲が割り当てられたことを示すインジケータを含む。
【発明を実施するための最良の形態】
【０００７】
本発明の実施形態を、添付図面を参照しながら以下でさらに十分に説明するが、これらの図面はその一部をなし、また図示により本発明を実施する特定の実施形態を示す。しかし、本発明は多数の異なる形態で実施してもよく、ここに示す実施形態に限定されると解釈してはならず、むしろこれらの実施形態は本開示が詳細で完全であるように、また当業者に本発明の範囲を完全に伝えられるように提供されるものである。特に、本発明は方法または装置として実施してもよい。したがって、本発明は完全にハードウエアの実施形態、完全にソフトウエアの実施形態、またはソフトウエアとハードウエアの態様を組み合わせた実施形態の形をとってもよい。したがって以下の詳細な説明を限定する意味で受け取ってはならない。
【０００８】
図１を参照すると、本発明を実施するための例示的システムは、コンピューティングデバイス１００のようなコンピューティングデバイスを含む。基本的構成において、コンピューティングデバイス１００は典型的に少なくとも１個の処理ユニット１０２とシステムメモリ１０４を含む。コンピューティングデバイスの正確な構成とタイプに応じて、システムメモリ１０４は揮発性（例えば、ＲＡＭ）、不揮発性（例えば、ＲＯＭ、フラッシュメモリなど）またはこの２つのある組合せであってもよい。システムメモリ１０４は典型的にオペレーティングシステム１０５、１または複数のアプリケーション１０６を含み、またプログラムデータ１０７を含んでもよい。この基本的構成を、点線１０８で囲んだそれらのコンポーネントによって図１に示す。
【０００９】
コンピューティングデバイス１００は、また追加の特徴または機能を持ってもよい。例えば、コンピューティングデバイス１００は、例えば、磁気ディスク、光学ディスク、テープのような追加のデータストレージデバイス（取り外し可能および／または固定）を備えてもよい。図１において、このような追加のストレージを取り外し可能ストレージ１０９と固定ストレージ１１０によって示す。コンピュータストレージ媒体には、コンピュータ可読命令、データ構造、プログラムモジュールまたはその他のデータのような情報のストレージのためにいろいろな方法や技術で実施した、揮発性および不揮発性、取り外し可能および固定の媒体を含む。システムメモリ１０４、取り外し可能ストレージ１０９および固定ストレージ１１０は、すべてコンピュータストレージ媒体の例である。コンピュータストレージ媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多様性ディスク（ＤＶＤ）またはその他の光学ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたはその他の磁気ストレージデバイス、あるいは所望情報を格納するために用いることができ、またコンピューティングデバイス１００がアクセスできるその他の媒体を含むが、これに限定されない。このようなコンピュータストレージ媒体は、どれもコンピューティングデバイス１００の一部であってもよい。コンピューティングデバイス１００はまた、キーボード、マウス、ペン、音声入力装置、タッチ入力装置などの入力装置１１２を有してもよい。ディスプレイ、スピーカ、プリンタなどの出力装置１１４もまた含んでもよい。これらのデバイスはすべてすでに良く知られており、ここで長々と論じる必要はない。
【００１０】
コンピューティングデバイス１００はまた、通信接続（群）１１６を含み、これにより、コンピューティングデバイスは、ネットワークまたは無線メッシュネットワーク上で、他のコンピューティングデバイス１１８と通信することができる。通信接続（群）１１６は通信媒体の一例である。通信媒体は典型的に、コンピュータ可読命令、データ構造、プログラムモジュールまたは、搬送波またはその他のトランスポート機構のような変調データ信号中のその他のデータを具現化する。「変調データ信号」という用語は、情報を信号で符号化するようなやり方で設定または変化された特性を１または複数有する信号を意味する。例えば、通信媒体は有線ネットワークまたは直接有線接続のような有線媒体および音声、ＲＦ、赤外線、その他の無線媒体のような無線媒体を含むが、これらに限定されない。ここで使っているコンピュータ可読媒体という用語には、ストレージ媒体と通信媒体の両方が含まれる。
【００１１】
一実施形態においては、アプリケーション１０６はさらに、本発明によるメッシュネットワーキング機能および／または分散サーバを実施するためのアプリケーション１２０含む。メッシュネットワークを設定し維持するために、アプリケーション１２０により表される機能を、追加の入力装置１１２、出力装置１１４、およびコンピューティングデバイス１００に含まれる通信接続（群）１１６によってさらに支援してもよい。
【００１２】
図２は、本発明の一例示的実施形態で使用されるモバイルコンピューティングデバイスを示す。図２を参照すると、本発明を実施するため一例示的システムは、モバイルコンピューティングデバイス２００のようなモバイルコンピューティングデバイスを含む。モバイルコンピューティングデバイス２００は、プロセッサ２６０、メモリ２６２、ディスプレイ２２８、キーパッド２３２を有する。メモリ２６２は一般に揮発性メモリ（例えば、ＲＡＭ）および不揮発性メモリ（例えば、ＲＯＭ、フラッシュメモリなど）の両方を含む。モバイルコンピューティングデバイス２００は、マイクロソフトコーポレーションのWindows（登録商標） ＣＥオペレーティングシステムまたはその他のオペレーティングシステムのようなオペレーティングシステム２６４を含み、これはメモリ２６２に常駐してプロセッサ２６０上で実行する。キーパッド２３２は、押しボタン数値ダイヤルパッド（典型的な電話にあるような）、マルチキーキーボード（通常のキーボードのような）などである。ディスプレイ２２８は、液晶ディスプレイ、またはモバイルコンピューティングデバイスにおいて一般に使われるその他のタイプのディスプレイであってもよい。ディスプレイ２２８は、タッチセンシティブであってよく、その場合は入力装置としても働く。
【００１３】
１または複数のアプリケーション２６６は、メモリ２６２にロードされ、オペレーティングシステム２６４の上で動作する。アプリケーションプログラムの例としてフォーンダイヤラープログラム、電子メールプログラム、スケジューリングプログラム、ＰＩＭ（personal information management個人情報管理）プログラム、ワードプロセッシングプログラム、表計算プログラム、インターネットブラウザプログラムなどを含む。モバイルコンピューティングデバイス２００はまた、メモリ２６２の中に不揮発性ストレージ２６８を含む。この不揮発性ストレージ２６８は、モバイルコンピューティングデバイス２００がパワーダウンしても失われてはならない永続的な情報を格納するのに用いてもよい。アプリケーション２６６は、ストレージ２６８において情報を使用し格納してもよく、この情報とは、例えば、電子メールアプリケーションが使用する電子メールまたはその他のメッセージ、ＰＩＭが使用するコンタクト情報、スケジューリングプログラムが使用する予約情報、ワードプロセッシングアプリケーションが使用する文書などである。
【００１４】
モバイルコンピューティングデバイス２００は、電源装置２７０を有し、それは１または複数のバッテリとして実装することができる。電源装置２７０は、さらにＡＣアダプタまたはバッテリを補充または充電する電源格納台（ｐｏｗｅｒｅｄ  ｄｏｃｋｉｎｇ）のような外部電源を有することも可能である。
【００１５】
モバイルコンピューティングデバイス２００は、２種類の外部通知機構、すなわちＬＥＤ２４０とオーディオインターフェース２７４を有している。これらのデバイスは電源装置２７０に直接接続してもよく、これによって、アクティブ化しているときバッテリ電力節約のため、プロセッサ２６０やその他のコンポーネントが遮断されても、通知機構によって指定されている時間だけオン状態である。ＬＥＤ２４０は、デバイスのパワーオン状態を指示するためにユーザが行動を起こすまでずっとオン状態であるようにプログラムしてもよい。オーディオインターフェース２７４は、可聴信号を送り、またユーザから可聴信号を受け取るために使用する。例えば、オーディオインターフェース２７４は、電話による会話を容易にするために、可聴出力を供給するためスピーカに、また可聴入力を受信するためにマイクロフォンに接続することができる。
【００１６】
モバイルコンピューティングデバイス２００は、無線周波数通信のような、送受信通信機能を果たす無線インターフェース層２７２を備えることもできる。無線インターフェース層２７２により、通信事業者またはサービスプロバイダを経由して、モバイルコンピューティングデバイス２００および外界間の無線接続が容易になる。無線インターフェース層２７２との間の送信は、オペレーティングシステム２６４の制御のもとに行う。言い換えれば、無線インターフェース層２７２により受信した通信は、オペレーティングシステム２６４を経由してアプリケーションプログラム２６６へ配布され、その逆も同様である。
【００１７】
一実施形態において、アプリケーション２６６はさらに、本発明によるメッシュネットワーキング機能および／または分散サーバを実装するためのアプリケーション２８０を含む。メッシュネットワークを設定し維持するために、アプリケーション２８０により表される機能を、モバイルデバイス２００に含まれる無線インターフェース層２７２における構造によってさらに支援してもよい。
【００１８】
図３は、本発明の１つの例示的実施形態に使用することができるメッシュネットワーク３００を示す。メッシュネットワーク３００は、メッシュノード、インターネットサービスプロバイダ、通信媒体のどのような接続形態を備えていてもよい。また、メッシュネットワーク３００は、本発明の精神と範囲を逸脱することなく静的あるいは動的接続形態を有することができる。
【００１９】
このメッシュネットワーク３００は、１つまたは複数のインターネットサービスプロバイダ３１０を含むが、これは１または複数のメッシュノードに対して複数のインターネットアクセスポイントを提供する。各メッシュノードは、メッシュネットワーク３００に接続されるいかなる装置をも備えることができる。メッシュノードは、データパケットを送受信でき、またメッシュネットワーク３００のルーティングプロトコルに従って他のメッシュノードにデータパケットを転送できる。このメッシュノードは、固定装置でもモバイル機器でも構わない。例えば、メッシュノードが図１に関連して記載されたコンピューティングデバイス１００と類似のコンピューティングデバイス３１２を含んでもよい。メッシュノードはまた、図２に関連して記載されたモバイルコンピューティングデバイス２００と類似のモバイルコンピューティングデバイス３１４を含んでもよい。他の実施形態においては、メッシュノードの他の構成を含んでもよい。例えば、メッシュノードが、メッシュボックス３１６のように１つのメッシュノードからもう１つのメッシュノードにデータパケットのルーティングするだけの専用コンピューティングデバイスを含んでもよい。
【００２０】
本発明の１つの例示的実施形態では、メッシュネットワーク３００が複数のメッシュノードがそのメッシュノード間のいくつかの冗長接続部と接続されているようなネットワーク接続形態を有する。メッシュネットワーク３００は、すべてのメッシュノードがメッシュネットワーク内で他のすべてのメッシュノードに接続されている全部のメッシュを含んでいてもよい。メッシュネットワーク３００はまた、いくつかのメッシュノードが全部のメッシュ内で組織され、また他のノードが１個か２個のメッシュノードにだけ接続されている部分的メッシュ接続形態を含んでいてもよい。他のメッシュ接続形態では、メッシュネットワークに接続した１または複数のクライアントサブネットを含んでいてもよい。これらのクライアントサブネットには、複数のクライアントが接続することができる。例えば、クライアントサブネットは、メッシュネットワーク以外に、ネットワーク接続を通じて特定のメッシュボックスに接続された１組のコンピューティングデバイスを有することができる。サブネットにおけるこれらのクライアントは、メッシュボックスを通じてトラフィックデータをメッシュネットワークにルーティングすることにより、他のリソースにアクセスできる。メッシュボックスを通じてメッシュネットワークへアクセスすることにより、メッシュボックスがデータのルーティングを管理するので、クライアントの装置はインターネットおよびその他のリソースにアクセスできる。メッシュネットワーク３００に対する多様な接続形態は無限にあるので、ここではこれ以上の説明を避ける。
【００２１】
参照番号３１８は、メッシュノード間の通信媒体を示す。一例として、通信媒体３１８には有線ネットワークあるいは直結有線接続のような有線媒体、さらに音声、ＲＦ、赤外線その他の無線媒体のような無線媒体が含まれるがこれに限定されない。参照番号３２０は、インターネットサービスプロバイダ３１０と１または複数のメッシュノードとの間の通信媒体を示す。通信媒体３２０には、有線ネットワークあるいは直結有線接続のような有線媒体、さらに音声、ＲＦ、赤外線その他の無線媒体のような無線媒体を含んでもよい。
【００２２】
メッシュネットワーク３００において、メッシュノードはデータパケットを他のメッシュノードおよびインターネットあるいはそのいずれかかと送受信できる。ルーティングテーブルは、一般的にはデータパケットがメッシュネットワークを通じてどのパスを通るかを判定する。データパケットのルーティングは通常はソースノードで規定される。言い換えれば、データパケットがメッシュネットワークを通じて通るルートは、データパケットを送るノードが判定してもよい。あるメッシュノードから別のメッシュノードへ行くようにルーティングされたデータパケットを通常「ホップ」と呼ぶ。例えば、メッシュノード３１４がデータパケットをメッシュノード３１６に送ろうとしたとき、メッシュノード３１４がアクセスできるルーティングテーブルで、ルーティングがメッシュノード３２２を通るように指示することができる。従って、データパケットは２回「ホップ」することになる（メッシュノード３１４からメッシュノード３２２へ、さらにメッシュノード３２２からメッシュノード３１６へ）。一般に、メッシュノードに到達するまでにデータパケットが行わなければならない「ホップ」数に比例して、待機時間が増加する。またルーティングテーブルは、目的地に到達するのにデータパケットが通れるいくつかのパスを指示することも可能である。ルーティングテーブルはさらに、「ホップ」の数が大きすぎることを理由に、その目的地のメッシュノードをアクセス不能と指示することもできる。しかし、ルーティングテーブルの使用は、メッシュネットワーク３００を通じたデータのルーティングのために、ネットワークノードがアドレスされていることを前提としている。
【００２３】
ピアツーピアネットワーク用分散サーバに関する例示的実施形態
本発明の実施形態は、アドホックネットワークのアドレス空間管理をネットワーク上に含まれる複数のコンピューティングデバイスに分散させることに関するものである。例えば、ネットワークは、１または複数のメッシュボックスあるいはメッシュノードを含んでもよい。これらのメッシュノードは、特定範囲内の他のメッシュボックスと無線ネットワークを自己形成するように構成されている。これらのメッシュノードの多くは、多数のクライアントコンピューティングデバイスをメッシュネットワークに接続させてもよい。他のメッシュノードは、メッシュネットワークに接続しているコンピューティングデバイスにインターネットの出口ポイント（ｅｇｒｅｓｓ  ｐｏｉｎｔｓ）を提供してもよい。本発明の提供するアドレッシングスキームにより、クライアントコンピューティングデバイスは、そのインターネットトラフィックを、メッシュネットワークを通して、また特定のインターネット出口ポイントに到達するように、ルーティングできる。このアドレッシングスキームは、ルートにおける多重ネットワークアドレス変換(ＮＡＴ)点を防止する一方で、データのこのルーティングが成立するようにネットワークアドレスを割り当てる。
【００２４】
一実施形態において、メッセージングスキームがメッシュノードにアドレス空間の状態およびそれに加えられた変更を知らせるのに用いられる。このメッセージングスキームにより、管理者あるいは専用サーバを使用することなくアドレス空間を管理するように、メッシュノードを調整する。
【００２５】
各メッシュボックスは、参入するクライアント（メッシュではなく）の接続をリスンするＤＨＣＰサーバを実現する。各メッシュボックスは、ＤＨＣＰデータベースの現在の状態を表すデータ構造を理解したときそれを維持する。メッシュボックスは、ＤＨＣＰの要求を処理（ｆｉｅｌｄ）し、前記のメッセージングスキームを他のメッシュボックスにその動きを知らせるのに用い、このようにしてすべてのメッシュボックスの間で一貫したアドレス空間が維持される。
【００２６】
図４は、本発明の一実施形態に関する例示的ピアツーピアトポロジを示す。システム４００は、ピアツーピア（Ｐ２Ｐ）ネットワーク４０２、ピアツーピア（Ｐ２Ｐ）コンピューティングデバイス（例えば、メッシュボックス）４０４、４０６、４０８、クライアントサブネット４１０、４２０、およびクライアントコンピューティングデバイス４１２、４１４、４１６、４２０、４２２、４２６を含む。
【００２７】
Ｐ２Ｐコンピューティングデバイス（例えば、４０６）をＰ２Ｐネットワークに付加するとき、それらを、アドレス空間の提供された部分を利用するか、あるいはアドレス空間の一部を割り当てるように調整する（図５参照）。自己形成し、自身で管理するＰ２Ｐネットワークにおいては、単一ＤＨＣＰサーバの概念はありえない。ＤＨＣＰサーバは誰か個人が（例えば、管理者）それを設定し、管理することを必要とする。Ｐ２Ｐネットワーク４０２において、管理者も制御ポイントも存在せず、ＤＨＣＰサービスについて依存できるネットワーク基盤も存在しない。本発明により、ＤＨＣＰはＰ２Ｐネットワーク４０２上の複数の位置や複数のデバイスから（例えば、４０６）アドレスを指定することができる。Ｐ２Ｐネットワーク４０２を自己形成するデバイス（例えば、４０６）は、単一の分散ＤＨＣＰデータベースにより動作する一方で、ＤＨＣＰサービスをまたそのクライアントコンピューティングデバイス（例えば、４１２）に提供する。例えば、自己形成するメッシュネットワーク（例えば、ネットワーク４０２）では、メッシュボックス（例えば、４０６）がお互いを発見し、互いに認証しあい、Ｐ２Ｐネットワークを形成する。本発明に従ってＰ２Ｐネットワークを構成することにより、あるメッシュボックス（例えば、４０６）に接続されたクライアント（例えば、４１２）はそのメッシュのどこかにある他のメッシュボックス（例えば、４０８）に付加されたクライアント（例えば、４２２）と通信できる。各メッシュボックス（例えば、４０６）は、ＩＰ（インターネットプロトコル）アドレスをそのクライアント（例えば、４１２）に提供する。これにより、このクライアントは、他のメッシュボックスに付加された他のクライアントもそれぞれのメッシュボックスから提供された固有のＩＰアドレスを持っているゆえに、それらと通信することができる。
【００２８】
一実施形態において、複数のメッシュボックスがバックボーンルーティングプロトコルに似た、1つのプロトコルに基づき、自身の中に単一の論理的ＤＨＣＰサーバを作り、そのプロトコルにより、それら複数のメッシュボックスが単一の論理的ＤＨＣＰサーバ上で動作する。メッシュボックスは、自分自身とそれに接続しているクライアントとにアドレスを割り当てることができる。アドレスはプライベートネットワーク１０．Ｂ．Ｃ．Ｄ空間から選択される。メッシュサブネットワークに対してデータベースが作成されると、第２の位置のために値をランダムに選択される。そのメッシュサブネットワーク内のすべてのノードが第２の位置にあるそのランダムに選択された値を用いる。例えば、値２１３を選択した場合、そのメッシュサブネットワークにあるすべてのノードのアドレスは１０．２１３で始まる。この例に対するサブネットマスクは、２５５．２５５．０．０である。本発明の精神または範囲を逸脱することなく、他の値およびサブネットマスクの値を選択してもよい。
【００２９】
他の実施形態においては、各メッシュボックスおよびそのクライアント群がアドレスのクライアントサブネットを共有する。クライアントサブネットサイズ（つまりホストの数）に対して選択するビット数は、通常のホームについて充分なアドレスを持つこととアドレス空間を無駄にしないこととの間のトレードオフである。例えば、各クライアントサブネットに対して４ビット空間を使用すると、１６台のホストを使用してもよい。しかしこのことは、メッシュボックスがそれに付加されているクライアントネットワークに対して、クライアントサブネットをいくつ割り当てられるかを制限するものではないことに留意が必要である。メッシュボックスがホストとなるクライアントコンピューティングデバイスに対して、クライアントサブネット上の空間を使い果たした場合、メッシュボックスは追加のクライアントサブネットを割り当てることができる。４ビット空間の例では、ＩＰアドレスを構成する残りの１２ビットはランダムに選択した値である。言い換えれば、メッシュボックスはサブネットを割り当てる際に、この範囲で自由にランダム値を選択できる。例えば、第２の位置として２１３がランダムに選択された値である前の例を用いると、このメッシュボックスに接続された装置に対するクライアントサブネットアドレスは１０．２１８．１．１６で、サブネットマスクは２５５．２５５．２５５．２４０となろう。
【００３０】
別の実施形態においては、本アドレッシングスキームを用いることにより、メッシュボックスが利用できるインターネット出口ポイントの中から選べるようなアルゴリズムを実施することができる。メッシュボックスが対応するクライアントコンピューティングデバイスにアドレスを渡すとき、メッシュボックスは自身のクライアント向きアドレスをデフォルトゲートウエイとして与える。このようにして、クライアントは出口ポイントの変更に基づいてその設定情報を変更する必要がない。
【００３１】
図５は、本発明によるパワーアッププロセスの例示的論理的フロー図を示す。プロセス５００は、メッシュネットワーク（例えば、図４に示すＰ２Ｐネットワーク４０２）上でメッシュノードあるいはメッシュボックスがパワーアップされる、ブロック５０２で始まる。メッシュノードは、クライアントサブネット（例えば、クライアントサブネット４１０）によってネットワークされた１または複数のクライアントコンピューティングデバイスを有してもよい。メッシュノードがパワーアップされ、メッシュネットワークに接続されると、処理はブロック５０４に続く。
【００３２】
ブロック５０４では、メッシュノードに対するＩＰアドレス（例えば、１０．Ｘ．Ｃ．Ｄ）の第２の位置あるいは第２のバイト用にランダムな値（Ｘ）を選択する。ランダム値を選択すると、処理はブロック５０６に移る。
【００３３】
ブロック５０６では、現在のメッシュノードの範囲内にある追加のメッシュノードに発見メッセージをブロードキャストする。一実施形態において、この範囲は現在のメッシュノードとその他のメッシュノードが隣接する、あるいは互いに直結していると見なされる範囲である。一実施形態においては、発見メッセージはＩＰアドレスの第２バイトに対応するＸ値を含む。発見メッセージがブロードキャストされると、処理はブロック５０８に続く。
【００３４】
ブロック５０８では、メッシュノードは規定した事象の間、初期化状態で待機する。一実施形態では、規定した事象というのは、タイムアウト特性に対応する規定秒数の経過である。メッシュノードが初期化状態で待機している間、処理は判定ブロック５１０に続く。
【００３５】
判定ブロック５１０では、待機状態の間に、現在のメッシュボックスが他のメッシュボックスから別の発見メッセージを受信しているかどうかを判定する。他のメッシュボックスから別の発見メッセージを受信している場合は、２つの割り当てられたアドレス空間のいずれかを選択するため、処理は判定ブロック５１２に移る。しかし他の発見メッセージを受信していない場合は、処理は判定ブロック５１６に進む。
【００３６】
判定ブロック５１２では、受信した発見メッセージに含まれるＸ値が、現在のメッシュボックスがランダムに発生したＸ値よりも大きいか判定する。受信したＸ値が現在のＸ値よりも大きい場合には、処理はブロック５１４に移る。しかし受信したＸ値が現在のＸ値よりも小さい場合には、処理はブロック５０８の初期化状態に戻る。
【００３７】
ブロック５１４では、Ｘの現在値を受信したＸ値に合わせて設定する。両方のメッシュボックスが初期化状態にあり、またメッシュネットワークがまだ存在しないとき、Ｘの現在値を変更することにより、隣接メッシュノードとの間のアドレス空間のコンフリクトを解決する。例えば、最初のメッシュノードがネットワーク上に現れて１０．１５．Ｃ．Ｄに対応するメッシュ面のアドレスの割り当てを示す発見メッセージを発信することができる。第２のメッシュノードは、同時にネットワーク上に現れて１０．２３．Ｃ．Ｄに対応するメッシュ面のアドレスの割り当てを示す発見メッセージを発信する可能性がある。２つのメッシュノードが同じアドレス空間に従って動作するためには、コンフリクトを解決するために最初のメッシュノードおよび第２のメッシュノードがもっと高いバイトレベルを選択するように設定される。したがって、最初のメッシュノードは、その２番目のバイトを２３に変更し、これによってメッシュネットワークのアドレス割り当ては、コンフリクトを回避した状態で進行することができる。この型のコンフリクト回避は、どちらかのメッシュノードが初期化状態を過ぎるか、あるいはどちらかのメッシュノードが初期化状態を過ぎた他のメッシュノードに遭遇する場合には発生しない。より高いバイトレベルに対応するＸの変化は、２つのメッシュノードが同時に発見メッセージをブロードキャストしている場合のために留保されている。したがって、Ｘの現在値がＸの受信値に対応するように変更されると、処理はブロック５０８の初期化状態に戻る。
【００３８】
判定ブロック５１６では、初期化状態の間にタイムアウト特性が終了しているか判定する。タイムアウト特性が終了していない場合には、処理はブロック５０８に戻り、メッシュノードは初期化状態に留まる。しかしタイムアウト特性が終了している場合には、メッシュノードは初期化状態を抜け、処理は判定ブロック５１８に移る。
【００３９】
ブロック５１８では、ブロードキャストした発見メッセージに応答して、メッシュネットワークの存在が見つかったかどうか判定する。現在メッシュネットワークが存在しない場合には、処理は判定ブロック５２２へと進む。しかし存在するメッシュネットワークが見つかった場合には、処理はブロック５２０に進む。
【００４０】
ブロック５２０では、隣接メッシュノードに対応するルーティングテーブルを検索する。各メッシュノードのルーティングテーブルはメッシュネットワーク上のあるメッシュノードの現在のアドレス割り当ての記述を提供する。ルーティングテーブルを検索すると、処理は判定ブロック５２２に移る。
【００４１】
判定ブロック５２２では、検索したルーティングテーブルに従って、割り当てのために任意に決定できる値が残されているか判定する。他のメッシュノードに対するＩＰアドレスの割り当てが、第２の位置の現在値（Ｘ）に対応するアドレス空間を消費してしまっている可能性がある。一実施形態においては、任意に決定できる値は、前述のクライアントサブネットに対する４ビット空間の割り当てにより残された、ランダムに発生した１２ビット値に相当する。現在割り当てられているアドレス空間に割り当て余地があると判定した場合には、処理はブロック５２６に進む。しかし、任意に決定できる値が残されていないと判定した場合には、処理はブロック５２４に進む。
【００４２】
ブロック５２４では第２の位置の新しい値（例えば、Ｙ）が、メッシュノードに対してアドレス空間を提供するために割り当てられる。第２の位置の新しい値（Ｙ）は、１つのアドレス空間のもとでメッシュネットワーク管理を継続するために、第２の位置の元の値（Ｘ）に合わせてもよい。第２の位置の新しい値が割り当てられると、処理はブロック５２６に続く。
【００４３】
ブロック５２６では、クライアントサブネットをメッシュノードおよびいずれかの付加されたクライアントコンピューティングデバイスに割り当てる。例えば、現在のメッシュノードのクライアントサブネットを区別するために、ルーティングテーブルが示しているように現在割り当てられていない１２の任意に決定できるビットのうちの１つの値を使用することができる。クライアントサブネットが割り当てられると、処理はブロック５２８に移る。
【００４４】
ブロック５２８では、メッシュネットワークのバックボーン上のアドレスを割り当てる。一実施形態において、メッシュ面のアドレスを１０．Ｘ．Ｂ．Ｃに対応する値を持つように選択する。ここでＸは事前に定義された第２の位置の値である。バックボーンあるいはメッシュ面のアドレスをメッシュノードに割り当てられると、処理はブロック５３０に続く。
【００４５】
ブロック５３０では、メッシュノードによるアドレスの割り当てに対応するタイマ（Ｔ）を設定する。タイマ（Ｔ）は、メッシュノードに対するアドレス割り当て確認の為の時間を制限する。タイマ（Ｔ）を選択した制限値（例えば、５分間）に設定すると、処理はブロック５３２に進む。
【００４６】
ブロック５３２では、クライアントサブネットおよびバックボーンアドレスにより定義されているように、割り当てメッセージを、メッシュノードの隣接ノードのために、隣接ノードにブロードキャストする。割り当てメッセ−ジは、このアドレスが「割り当てられた」ことおよび割り当てを確認するためにタイマ（Ｔ）により設定された時間の経過を待っていることを示すインジケータを含む。一実施形態において、割り当てメッセージは、割り当てメッセージがメッシュネットワーク内を伝搬するホップカウントを制限するホップカウントを含む。ホップカウントは、データがネットワークを通して或るホップカウント以上ルーティングされることを防ぐ、同様のホップ制限値に相当するものである。管理アドレス空間の一貫性の必要性がデータのルーティング範囲に限定されるので、メッシュネットワークを通して充分に離れているメッシュノードはコンフリクトを起こすことなく同じアドレスを持つことができる。
【００４７】
他の実施形態においては、割り当てメッセージは、現在のメッシュノードのルーティングテーブルが最後に変更された時間を表すタイムスタンプも含む。このタイムスタンプにより他のメッシュノードは、このメッセージを以前に見ている場合（つまりそれが送られて来てから以降変更されていない）、割り当てメッセージを無視することができる。
【００４８】
さらに、割り当てメッセージは、割り当てメッセージを発信したメッシュノードを一意的に識別できる連続番号も含むことができる。この連続番号は、コンフリクトする可能性のある割り当てメッセージ間の問題を解決する、ソースのもう１つのインジケータを提供する。割り当てメッセージをブロードキャストすると、処理はブロック５３４に進む。
【００４９】
ブロック５３４では、アドレス割り当てに対する確認時間を提供するタイマ（Ｔ）が始動する。タイマ（Ｔ）の始動は、割り当てメッセージのブロードキャストと同時に起こる。タイマ（Ｔ）が始動すると処理はブロック５３６に移る。
【００５０】
ブロック５３６では、メッシュノードがリスン状態に入る。リスン状態の間、メッシュノードは、クライアントコンピューティングデバイスからＤＨＣＰ要求を受け取ることができ（図６参照）、他のメッシュノードから他の割り当てメッセージを受け取ることができる（図７参照）、あるいはタイマ（Ｔ）時間が経過する。メッシュノードがリスン状態に入ったあと、処理は判定ブロック５３８に続く。
【００５１】
判定ブロック５３８では、タイマ（Ｔ）の時間が経過したか判定する。タイマ（Ｔ）時間が経過していない場合には、処理はメッシュノードがリスン状態であるブロック５３６に戻る。しかしタイマ（Ｔ）時間が経過した場合には、処理はブロック５４０に移る。
【００５２】
ブロック５４０では、クライアントサブネットおよびバックボーンアドレスによって定義されている隣接メッシュノードに更新した割り当てメッセージをブロードキャストする。この割り当てメッセージは、そのアドレスが「使用中」であり、さらなるコンフリクトを防ぐために、そのアドレスが現在のメッシュノードおよびそのクライアントサブネットに割り当てられていることを示すインジケータを含む。
【００５３】
図６は、本発明によるＤＨＣＰ要求ハンドリングプロセスの例示的論理フロー図を示す。プロセス６００は、図５の考察で説明したようにメッシュノードがリスン状態５３６にあり、接続しているクライアントコンピューティングデバイスからＤＨＣＰ要求を受信したところから開始する。処理はブロック６０２に続く。
【００５４】
ブロック６０２では、割り当てられたクライアントサブネット範囲から未使用の値に対して選択がなされる。例えば、上記のように４ビットのクライアントサブネット割り当てを使用すると、クライアントコンピューティングデバイスに可能な１６のクライアントアドレスの１つを割り当てることができる。未使用のクライアントサブネットアドレスを選択すると、処理は判定ブロック６０４に続く。
【００５５】
判定ブロック６０４では、図５の考察で説明したタイマ（Ｔ）の時間が経過したか判定する。タイマ（Ｔ）の時間が経過していない場合には、処理はブロック６０６に移る。しかしタイマ（Ｔ）の時間が経過している場合には、処理はブロック６０８に移る。
【００５６】
ブロック６０６では、メッシュノードは、ＤＨＣＰ要求が標準の更新制限時間よりも短い設定更新制限時間（例えば、５分間）に応答するように構成される。より短い更新制限時間を用いるのは、メッシュノードによるクライアントサブネット範囲割り当てがまだ有効になっていないからである。したがってコンフリクトの事例を減らすため、設定更新制限時間が切れたときメッシュノードがクライアントサブネットアドレス割り当てを有効とするようにＤＨＣＰの更新制限時間を設定する。処理は判定ブロック６１０に続く。
【００５７】
ブロック６０８では、タイマ（Ｔ）時間が経過しているので、メッシュノードはＤＨＣＰ要求に応答して標準の更新制限時間を設定する。クライアントサブネット範囲に対応するアドレス割り当ては既に有効である。したがって、メッシュノードは定期的にメッシュネットワークについてアドレス割り当てを確認するため、「ハートビート」期間として動作する標準の更新制限時間が使われる。処理は判定ブロック６１０に続く。
【００５８】
判定ブロック６１０では、クライアントサブネット範囲に残っているアドレスの数が選択した閾値よりも大きいか判定する。例えば、クライアントサブネット範囲の６０％がメッシュノードに接続したクライアントコンピューティングデバイスに割り当てられると、追加の範囲を割り当てる必要があると判定する。クライアントサブネットアドレスの数が閾値を越えてしまっている場合には、処理は図５に示すリスン状態５３６に戻る。しかし、クライアントサブネットアドレスの数が閾値を越えていない場合には、処理はブロック６１２に移る。
【００５９】
ブロック６１２では、アドレスの新しいクライアントサブネット範囲を割り当て、またメッシュネットワーク上にある他のメッシュノードに割り当てを通知するため通知プロセスを呼び出す。一実施形態においては、通知プロセスは図５のプロセスステップ５２６から５４０に相当する。他の実施形態では、追加のクライアントサブネットアドレスを割り当てるのに他のバックボーンアドレスを割り当てる必要がないため、プロセスステップ５２８を省略する。新しいクライアントサブネットアドレスを割り当てると、処理は図５に示すリスン状態５３６に戻る。
【００６０】
図７は、本発明による割り当てメッセージ受信ハンドリングプロセスの例示的論理フロー図を示す。プロセス７００は、メッシュノードが図５の考察で説明したリスン状態５３６にあり、他のメッシュノードから割り当てメッセージを受信したところから開始する。処理は判定ブロック７０２に続く。
【００６１】
判定ブロック７０２では、割り当てメッセージの発信者に関するタイムスタンプが、現在のメッシュノードが発信メッシュノードであったときのタイムスタンプよりも新しいか判定する。タイムスタンプが新しい場合には、処理はブロック７０４に移る。しかしタイムスタンプが新しくない場合には、処理はブロック７１２に移る。
【００６２】
ブロック７０４では、現在のメッシュノードが割り当てメッセージの送信者から発信したメッシュノードのルーティングテーブルを取得する。最初のホップの後では、割り当てメッセージの送信者と割り当てメッセージの発信者とは異なる。ルーティングテーブルを取得した後、処理は判定ブロック７０６に移る。
【００６３】
判定ブロック７０６では、受信した割り当てメッセージに従って行った割り当てのいずれかが、ローカルに割り当てた現在のメッシュノードのサブネットのどれかとコンフリクトしているか判定する。コンフリクトしていない場合には処理はブロック７１０に進む。しかしコンフリクトしている場合には、処理はブロック７０８に移る。
【００６４】
ブロック７０８では、現在のメッシュノードは割り当てメッセージの送信者に対しエラー通知で応答する。エラー通知は割り当てメッセージの発信者まで戻って伝達される。その場合には、そのバックボーンおよびサブネットアドレスを再割り当てすることを選択して、割り当てメッセージの発信者はコンフリクトを解決することができる。現在のメッシュノードがエラー通知に応答したあと、処理は図５で説明したリスン状態５３６に戻る。
【００６５】
コンフリクトしていない場合には、ブロック７１０で、発信者のタイムスタンプのローカルバージョンを更新して、発信したメッシュノードによる現在のアドレス割り当てを反映する。タイムスタンプのローカルバージョンを更新することにより、将来同じ発信メッシュノードからの割り当てメッセージを受信したとき区別することができる。処理はブロック７１４に続く。
【００６６】
判定ブロック７１２では、発信者のタイムスタンプがローカルバージョンより新しくない場合、現在のメッシュノードが発信メッシュノードに対応するこのタイムスタンプおよび連続番号を以前に見たかどうかを判定する。現在のメッシュノードがこのタイムスタンプおよび連続番号を以前に見た場合には、処理はブロック７１８へと進む。しかし、現在のメッシュノードがこのタイムスタンプおよび連続番号を以前に見ていない場合には、処理はブロック７１４に移る。
【００６７】
ブロック７１４では、受信した割り当てメッセージに伴うホップカウントをインクリメントする。ホップカウントをインクリメントすることは、現在のメッシュノードがそれを隣接メッシュノードに転送する準備ができていることを示す。ホップカウントをインクリメントした後、処理は判定ブロック７１６に移る。
【００６８】
判定ブロック７１６では、ホップカウントがホップ制限値を越えているかどうかを判定する。ホップ制限値は割り当てメッセージをさらに転送するのを防ぐために設定できる。ホップカウントの制限値により、アドレッシングが過剰な水準でコンフリクトすることなくネットワーク上で複製したアドレスを使用できる水準を制御することができる。ホップカウントがホップ制限値を越えていない場合には、処理はブロック７２０に進む。しかし、ホップカウントがホップ制限値を越えている場合には、処理はブロック７１８に移る。
【００６９】
ブロック７１８では、現在のメッシュノードはその割り当てメッセージを破棄する。割り当てメッセージが破棄される理由は、その割り当てメッセージがそのルーティングテーブルの現在の状態にふさわしくない（つまりタイムスタンプが新しくない、ホップカウントが超過している、など）と現在のメッシュノードが判定したからである。割り当てメッセージを破棄した後、処理は図５で説明したリスン状態５３６に戻る。
【００７０】
これとは反対に、ブロック７２０で割り当てメッセージがふさわしいとき、現在のメッシュノードはその割り当てメッセージを隣接メッシュノードに転送する。割り当てメッセージを転送することにより、メッシュネットワーク上のメッシュノード間でのアドレス空間に関する同期が確保される。割り当てメッセージを転送した後と、処理は図５で説明したリスン状態５３６に戻る。
【００７１】
別の実施形態においては、図６および図７で説明したプロセスは、説明したようなリスン状態に戻らず、その代わりに最適ルート決定、インターネット出口決定と整合性のある状態のようなさらなる処理のための新たな状態あるいはその他の別の状態に移動する場合がある。
【００７２】
さらに別の実施形態において、既にある２つのメッシュネットワークの間に新しいノードがオンラインとなり、それによって２つのメッシュネットワークと新しいノードとの内容を含む新しい論理的メッシュネットワークを作ることができる。本発明による更新して転送するプロセスを用いることにより、２つのメッシュノードの１つからのアドレス空間割り当てを新しいノードを通して、他のメッシュネットワークに伝搬することができる。割り当てメッセージがそれに対応するホップ制限値まで転送された後、２つのメッシュノードは論理的メッシュネットワークに対する共通アドレス空間に従って同期される。
【００７３】
さらに別の実施形態において、図５から図７で説明した本発明のステップを必要に応じて、ピアツーピアネットワークに関連して使用するインターネットプロトコルの現在のバージョンに適合するように修正することができる。例えば、あるプロトコルは、論理的分散ＤＨＣＰサーバを生成する必要性を回避できる。このプロトコルバージョンは、サブネットＩＤを発行する直接機能を提供することができ、したがってサブネットをＤＨＣＰサーバの支援なしに割り当て、管理することができる。Ｐ２Ｐネットワーク上の一貫性のあるアドレス空間を維持することに向けられた本発明の教示は、同様に本発明の精神と範囲を逸脱することなく他のプロトコルバージョンにも適用できる。
【００７４】
上記の仕様、実施例およびデータは本発明の構成の製作および使用法を完全に説明している。本発明の精神と範囲を逸脱することなく、本発明の多数の実施形態を作ることが可能であるから、本発明は添付の特許請求の範囲に準拠するものとする。
【図面の簡単な説明】
【００７５】
【図１】本発明の一例示的実施形態で使用される例示的コンピューティングデバイスの図である。
【図２】本発明の一例示的実施形態で使用される例示的モバイル機器の図である。
【図３】本発明の一例示的実施形態で使用される例示的メッシュネットワークの図である。
【図４】本発明の一実施形態のための例示的ピアツーピアトポロジの図である。
【図５】本発明によるパワーアッププロセスの例示的論理フロー図である。
【図６】本発明によるＤＨＣＰ要求ハンドリングプロセスの例示的論理フロー図である。
【図７】本発明による割り当てメッセージ受信ハンドリングプロセスの例示的論理フロー図である。
【符号の説明】
【００７６】
１００  コンピューティングデバイス
１０４  システムメモリ
１０５  オペレーティングシステム
１０６  アプリケーション
１２０  メッシュネットワーキング
１０７  プログラムデータ
１０２  処理ユニット
１０９  取り外し可能ストレージ
１１０  固定ストレージ
１１２  入力装置
１１４  出力装置
１１６  通信接続部
１１８  他のコンピューティングデバイス
２６０  プロセッサ
２２８  ディスプレイ
２３０  周辺装置ポート
２３２  キーパッド
２６２  メモリ
２８０  メッシュネットワーキング
２６８  ストレージ
２７０  電源装置
２７４  オーディオインターフェ―ス
２７２  無線インターフェース層
４０２  ピアツーピアネットワーク
４１０  クライアントサブネット
４２０  クライアントサブネット
【図１】
2006148913.tif 000003
【図２】
2006148913.tif 000004
【図３】
2006148913.tif 000005
【図４】
2006148913.tif 000006
【図５】
2006148913.tif 000007
【図６】
2006148913.tif 000008
【図７】
2006148913.tif 000009