(57)【要約】      （修正有）【課題】複数のデータパスがリソース制約またはその他の通信要件を満たす最良の利用可能なエンドツーエンド・データパスを決定する方法、システムおよびプログラムを提供する。【解決手段】マルチホップデータパスの各ノードにおいて、ＱｏＳまたは他の通信要件を満たすために、リソース制約情報をネットワーク内で伝播させる。伝播されるＱｏＳ情報には、要求されるアプリケーションスループット、遅延限界、ジッタ、許容可能な残留パケットロス率が含められる。各ノードにおけるリソース利用可能性が、エンドツーエンド・データフローの通信要件を満たすことが可能か否かが決定される。エンドツーエンド・データフローの通信要件を満たすことが可能なエンドツーエンド・データパスが選択され、ノード、およびそれらの関連リンクに対してリソースが割り当てられる。【選択図】図２
2014112852.tif 000002
【特許請求の範囲】
【請求項１】
分散型のマルチホップ時分割多元接続（ＴＤＭＡ）ネットワークにおいてエンドツーエンド・データパスを選択する方法であって、前記エンドツーエンド・データパスは、各ノードにおいて十分な利用可能なリソースを有する複数のエンドツーエンド・データパスから選択され、それによって、所望されるエンドツーエンド・データフローに関するサービス品質（ＱｏＳ）を保証し、前記方法は、
前記所望されるエンドツーエンド・データフローのために使用されるスロットの総数を最小限に抑えること、
前記選択されたエンドツーエンド・データパスにおける実質的にすべてのノードに最大数のスロットを残し、それによって、新たなデータフローが、それらのＱｏＳが満たされた状態で前記ネットワークに受け入れられる可能性を高めること、および、
前記選択されたエンドツーエンド・データパスにおける中間ネットワークノードの電力消費量を最小限に抑え、それによって、他のファクタが存在しない状況で、より長い時間にわたって経路利用可能性を保証すること、
のうちの少なくとも１つに少なくとも部分的に基づいて、前記所望されるエンドツーエンド・データフローのために少なくとも１つのエンドツーエンド・データパスを選択することを備える、方法。
【請求項２】
前記選択することは、ロバストなルーティングのために複数のエンドツーエンド・データパスを選択することを備える、請求項１に記載の方法。
【請求項３】
前記複数のエンドツーエンド・データパスに関してスロット割当てを分析して、前記所望されるエンドツーエンド・データフローのために使用されるスロットの総数を決定することをさらに備え、少なくとも１つのエンドツーエンド・データパスを前記選択することは、前記分析によって決定される前記所望されるエンドツーエンド・データフローのために使用される最小の総数のスロットを有するエンドツーエンド・データパスを選択する、請求項１に記載の方法。
【請求項４】
前記複数のエンドツーエンド・データパスに関してスロット割当てを分析して、前記所望されるエンドツーエンド・データフローのために使用された場合に前記エンドツーエンド・データパス内のノードに残るスロットの数を決定することをさらに備え、少なくとも１つのエンドツーエンド・データパスを前記選択することは、実質的にすべてのノードに最大数のスロットを残すエンドツーエンド・データパスを選択する、請求項１に記載の方法。
【請求項５】
前記所望されるエンドツーエンド・データフローのＱｏＳ要件を満たすように前記選択されたエンドツーエンド・データパスの各中間ノードにおいて上りリンクと下りリンクとの間でスロットを割り当てることをさらに備える、請求項１に記載の方法。
【請求項６】
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するための方法であって、
前記ネットワークのノードにリソース制約情報を伝播させること、
前記リソース制約情報を使用して、前記少なくとも１つのエンドツーエンド・データパスの各ネットワークノードにおけるリソース利用可能性が、前記エンドツーエンド・データフローの前記所望される通信属性を満たすことが可能か否かを決定すること、
前記エンドツーエンド・データフローを提供する際に使用するために、前記所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有すると決定された前記少なくとも１つのエンドツーエンド・データパスのうちのエンドツーエンド・データパスを選択すること、および
前記所望される通信属性を満たす前記エンドツーエンド・データフローを提供するために、前記選択されたエンドツーエンド・データパスの各ネットワークノードに通信リソースを割り当てること、を備える、方法。
【請求項７】
前記所望される通信属性は、所望されるサービス品質（ＱｏＳ）を備える、請求項６に記載の方法。
【請求項８】
エンドツーエンド・データパスを前記選択することは、
前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を最小限に抑えること、
前記選択されたエンドツーエンド・データパスにおける実質的にすべてのノードに最大数の通信リソースを残すこと、および、
前記選択されたエンドツーエンド・データパスのネットワークノードの電力消費量を最小限に抑えること、
のうちの少なくとも１つに少なくとも部分的に基づいて、選択を行う、請求項６に記載の方法。
【請求項９】
前記通信リソースは、時分割多元接続（ＴＤＭＡ）ネットワーク通信プロトコルのタイムスロットを備える、請求項８に記載の方法。
【請求項１０】
エンドツーエンド・データパスを前記選択することは、前記エンドツーエンド・データフローを提供するための複数のエンドツーエンド・データパスを選択することを備える、請求項６に記載の方法。
【請求項１１】
エンドツーエンド・データパスを前記選択することは、
少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析して、前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を決定すること、および、前記所望されるエンドツーエンド・データフローのために使用される最小の総数の通信リソースを有するリソース割当ておよびエンドツーエンド・データパスを選択することを備える、請求項６に記載の方法。
【請求項１２】
エンドツーエンド・データパスを前記選択することは、
前記少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析して、前記エンドツーエンド・データフローのために使用された場合に前記少なくとも１つのエンドツーエンド・データパス内のノードに残る通信リソースの数を決定すること、および、実質的にすべてのノードに最大数のスロットを残すエンドツーエンド・データパスおよびリソース割当てを選択することを備える、請求項６に記載の方法。
【請求項１３】
通信リソースを前記割り当てることは、
前記エンドツーエンド・データフローの前記通信属性を満たすように前記選択されたエンドツーエンド・データパスの各中間ノードにおいて上りリンクと下りリンクとの間で通信リソースを割り当てることを備える、請求項６に記載の方法。
【請求項１４】
通信リソースを前記割り当てることは、
前記選択されたエンドツーエンド・データパスの中間ネットワークノードに関して、
下りネットワークノードにおいて利用可能でない、前記中間ネットワークノードおよび上りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した上りリンクに通信リソースを割り当てること、
上りの要件が前記割当てによって満たされないままである場合、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記上りリンクに通信リソースを割り当てること、
前記上りネットワークノードにおいて利用可能でない、前記中間ネットワークノードおよび前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した下りリンクに通信リソースを割り当てること、および、
下りの要件が前記割当てによって満たされないままである場合、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記下りリンクに通信リソースを割り当てること、を備える、請求項６に記載の方法。
【請求項１５】
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するためのシステムであって、前記システムは、
メモリとプロセッサとを有するネットワークノードを備え、前記メモリは、隣接ネットワークノードに関するリソース制約情報を格納し、前記隣接ネットワークノードは、エンドツーエンド・データパスに関する上りネットワークノードと、前記エンドツーエンド・データパスに関する下りネットワークノードとを備え、前記メモリはさらに、前記エンドツーエンド・データパスの前記上りネットワークノードおよび前記下りネットワークノードに関する前記リソース制約情報を使用して、前記ネットワークノードにおけるネットワークリソース利用可能性が、所望されるエンドツーエンド・データフローの通信要件を満たすか否かを決定するように動作可能な前記プロセッサの動作を定義するコードを格納し、前記メモリはさらに、前記通信要件を満たす前記所望されるエンドツーエンド・データフローを達成するために前記ネットワークノードにおいてリソースを割り当てるように動作可能な前記プロセッサの動作を定義するコードを格納する、システム。
【請求項１６】
前記割り当てられたリソースは、時分割多元接続（ＴＤＭＡ）ネットワークプロトコルのタイムスロットを備える、請求項１５に記載のシステム。
【請求項１７】
前記ネットワークノードは、コンピュータ、携帯情報端末（ＰＤＡ）、電話、サーバ、ルータ、ゲートウェイ、スイッチ、マルチプレクサ、モデム、無線機、アクセスポイント、および基地局からなる群から選択されるノード構成を備える、請求項１５に記載のシステム。
【請求項１８】
メモリとプロセッサとを有する複数のネットワークノードを備えており、前記メモリは、隣接ネットワークノードに関するリソース制約情報を格納し、前記メモリはさらに、前記リソース制約情報を使用して、対応するネットワークノードにおけるネットワークリソース利用可能性が前記所望されるエンドツーエンド・データフローの通信要件を満たすか否かを決定するように動作可能な前記プロセッサの動作を定義するコードを格納し、前記メモリはさらに、前記通信要件を満たす前記所望されるエンドツーエンド・データフローを達成するために前記対応するネットワークノードにおいてリソースを割り当てるように動作可能な前記プロセッサの動作を定義するコードを格納する、請求項１５に記載のシステム。
【請求項１９】
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するためのシステムであって、
前記ネットワークのノードに関するリソース制約情報を使用して、前記少なくとも１つのエンドツーエンド・データパスの各ネットワークノードにおけるリソース利用可能性が、前記エンドツーエンド・データフローの前記所望される通信属性を満たすことが可能か否かを決定するための手段と、
前記エンドツーエンド・データフローを提供する際に使用するために、前記所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有すると決定された前記少なくとも１つのエンドツーエンド・データパスのうちのエンドツーエンド・データパスを選択するための手段と、
前記所望される通信属性を満たす前記エンドツーエンド・データフローを提供するために前記選択されたエンドツーエンド・データパスの各ネットワークノードに通信リソースを割り当てるための手段と、を備える、システム。
【請求項２０】
前記リソース制約情報を前記ネットワークの前記ノードに伝播させるための手段をさらに備える、請求項１９に記載のシステム。
【請求項２１】
前記通信リソースは、時分割多元接続（ＴＤＭＡ）ネットワーク通信プロトコルのタイムスロットを備え、前記リソース制約情報は、前記ＴＤＭＡ通信プロトコルのタイムスロットの利用可能性に関する情報を備える、請求項１９に記載のシステム。
【請求項２２】
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するためのコンピュータプログラム製品であって、前記コンピュータプログラム製品は、
コンピュータ実行可能コードを格納するコンピュータ可読媒体を備え、前記コンピュータ実行可能コードは、
前記ネットワークのノードに関するリソース制約情報を使用して、前記少なくとも１つのエンドツーエンド・データパスの各ネットワークノードにおけるリソース利用可能性が、前記エンドツーエンド・データフローの前記所望される通信属性を満たすことが可能か否かを決定するためのコード、
前記エンドツーエンド・データフローを提供する際に使用するために、前記所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有すると決定された前記少なくとも１つのエンドツーエンド・データパスのうちのエンドツーエンド・データパスを選択するためのコード、および、
前記所望される通信属性を満たす前記エンドツーエンド・データフローを提供するために前記選択されたエンドツーエンド・データパスの各ネットワークノードに通信リソースを割り当てるためのコード、を含む、コンピュータプログラム製品。
【請求項２３】
エンドツーエンド・データパスを選択するための前記コードは、前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を最小限に抑えること、前記選択されるエンドツーエンド・データパスにおける実質的にすべてのノードに最大数の通信リソースを残すこと、および、前記選択されたエンドツーエンド・データパスのネットワークノードにおける利用可能な電力、のうちの少なくとも１つに少なくとも部分的に基づいて選択を行うように動作可能である、請求項２２に記載のコンピュータプログラム製品。
【請求項２４】
エンドツーエンド・データパスを選択するための前記コードは、
少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析するためのコードと、
分析するための前記コードからの情報に少なくとも部分的に基づいて、前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を決定するためのコードと、
前記所望されるエンドツーエンド・データフローのために使用される最小の総数の通信リソースを有するエンドツーエンド・データパスおよびリソース割当てを選択するためのコードと、を備える、請求項２２に記載のコンピュータプログラム製品。
【請求項２５】
エンドツーエンド・データパスを選択するための前記コードは、
前記少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析するためのコードと、
分析するための前記コードからの情報に少なくとも部分的に基づいて、前記エンドツーエンド・データフローのために使用された場合に前記少なくとも１つのエンドツーエンド・データパス内のノードに残る通信リソースの数を決定するためのコードと、
実質的にすべてのノードに最大数のスロットを残すエンドツーエンド・データパスおよびリソース割当てを選択するためのコードと、を備える、請求項２２に記載のコンピュータプログラム製品。
【請求項２６】
通信リソースを割り当てるための前記コードは、
下りネットワークノードにおいて利用可能でない、中間ネットワークノードおよび上りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した上りリンクに通信リソースを割り当てるためのコードであって、上りの要件が前記上りリンクへのリソースの前記割当てによって満たされないままである場合、割り当てるための前記コードは、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記上りリンクに通信リソースを割り当てる、コードと、
前記上りネットワークノードにおいて利用可能でない、前記中間ネットワークノードおよび前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した下りリンクに通信リソースを割り当てるためのコードであって、下りの要件が前記下りリンクへのリソースの前記割当てによって満たされないままである場合、割り当てるための前記コードは、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記下りリンクに通信リソースを割り当てる、コードと、を備える、請求項２２に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【優先権の主張】
【０００１】
本特許出願は、参照によりその開示が本明細書に明確に組み込まれている、２００９年７月１５日に出願され、本特許出願の譲受人に譲渡されている、「Ｓｌｏｔ  Ａｌｌｏｃａｔｉｏｎ  ａｔ  Ｎｏｄｅｓ  ｆｏｒ  Ｍｅｅｔｉｎｇ  Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ  Ｃｏｎｓｔｒａｉｎｔｓ  ｉｎ  Ｍｕｌｔｉｈｏｐ  Ｕｌｔｒａ  Ｗｉｄｅｂａｎｄ  Ｎｅｔｗｏｒｋｓ  ａｎｄ  Ｒｅｓｏｕｒｃｅ  Ａｌｌｏｃａｔｉｏｎ  ａｎｄ  Ｓｃｈｅｄｕｌｉｎｇ  ｗｉｔｈ  Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ  ａｎｄ  Ｆａｉｒｎｅｓｓ  Ｒｅｑｕｉｒｅｍｅｎｔｓ  ｉｎ  ＴＤＭＡ  Ｂａｓｅｄ  Ｍｕｌｔｉｈｏｐ  Ｗｉｒｅｌｅｓｓ  Ｎｅｔｗｏｒｋｓ」という名称の米国特許仮出願第６１／２２５，５９９号の利益を主張するものである。
【技術分野】
【０００２】
本開示は、一般に、ネットワーク通信に関し、より詳細には、ネットワーク通信のためのリソース割当てに関する。
【背景技術】
【０００３】
様々な形態のネットワークによって提供される情報通信が、今日、世界中のほぼいたるところに普及している。無線リンクおよび有線リンクを使用して通信している複数のノードから成るネットワークが、例えば、音声データ、マルチメディアデータ、英数字データ、グラフィックデータなどの多くのタイプのデータペイロードを運ぶことが可能なデータパケットを搬送するために使用される。したがって、そのようなネットワークのノードは、コンピュータ、携帯情報端末（ＰＤＡ）、電話、サーバ、ルータ、スイッチ、マルチプレクサ、モデム、無線機、アクセスポイント、基地局などを備えることが可能である。データパケットフローが、所望されるネットワーク通信を提供するためにネットワークノード間に確立され、任意の特定の通信セッションに関するエンドツーエンド・データ通信は、複数のホップを利用すること（すなわち、１つまたは複数の中間ネットワークノードを通ってルーティングされること）が可能である。任意の数のネットワークノードが、任意の特定の時点で、そのようなフローを提供するためのネットワーク通信リソースを求めて競合していることがありうる。
【０００４】
ネットワークノード（例えば、無線ネットワークノード）のペアの間の伝送が、１つまたは複数の他のネットワークノードの通信に対して、これらの伝送が時間領域、周波数領域、および空間領域において重なり合う場合、干渉を引き起こす（例えば、ネットワークノードの異なるペアの間の別の伝送に干渉する）可能性がある。したがって、そのような伝送の成功は、そのような伝送が、前述した領域の少なくとも１つにおいて分離されている場合に限って、保証される可能性がある。周波数分割多元接続（ＦＤＭＡ）、時分割多元接続（ＴＤＭＡ）、空間的分離／隔離などの、ネットワーク通信リンクへの共有アクセスのためのリソース割当てを提供するためのいくつかの技術が、ネットワーク通信を円滑にするために実施されることが可能である。例えば、通信直交性を提供するために周波数領域が利用されないＴＤＭＡシステムでは、時間領域および空間領域が、通信競合を回避するためにリソース割当てを提供する際に様々な伝送に関して調査される（例えば、ＴＤＭＡ動作および空間再使用オプションが、干渉回避のために調査される）ことが可能である。
【０００５】
ネットワーク通信を円滑にするためにリソースの割当て（例えば、前述したＴＤＭＡシステムの例におけるタイムスロットの割当ておよび／またはデータパスルーティング）を提供することは、一般に、任意の１つのネットワークリンクにおいて或る特定のノードのデータを通信する際に使用するために十分なデータ容量が利用可能かどうかを決定することほど簡単ではない。データ通信がそれについて提供されるアプリケーション（例えば、ＷｉＭｅｄｉａベースの超広帯域（ＵＷＢ）ネットワークにおけるストリーミングおよび／または高精細度マルチメディアサービス、参照により本明細書に組み込まれている、ＥＣＭＡ−３６８、「Ｈｉｇｈ  Ｒａｔｅ  Ｕｌｔｒａ  Ｗｉｄｅｂａｎｄ  ＰＨＹ  ａｎｄ  ＭＡＣ  Ｓｔａｎｄａｒｄ」、第２版、２００７年１２月を参照されたい）は、帯域幅消費型（bandwidth intensive）および遅延センシティブ（delay sensitive）である可能性があり、ゆえに、厳格なサービス品質（ＱｏＳ：quality of service）要件を有する。したがって、データパス上の各ノードのところに十分な利用可能なリソースを有するデータパスが、エンドツーエンド・データパスにわたってＱｏＳを保証するためのネットワークの複数のホップにわたるデータフローのＱｏＳ要件をサポートするのに必要とされる。
【０００６】
従来のソリューションは、ＷｉＭｅｄｉａベースのＵＷＢネットワークのプロトコルなど、分散型の媒体アクセス制御（ＭＡＣ）プロトコルに適していない、集中型の実装形態であるＴＤＭＡスケジューリングスキームを提案してきた。一部のそのような従来のソリューションは、ＱｏＳを意識したルーティングプロトコル（QoS aware routing protocols）の変形であるのに対して、他のそのような従来のソリューションは、所望されるフローをサポートする問題を解決しようとして、整数線形計画法（integer linear programming）を使用してきた。
【発明の概要】
【０００７】
本開示は、所望されるエンドツーエンド通信（エンドツーエンド・データフロー）を円滑にするためにデータパス上の各ノードにおいて十分な利用可能なリソースを有するマルチホップネットワークデータパスを識別するシステムおよび方法を対象とする。実施形態は、マルチホップデータパスの各ノードにおいてＱｏＳまたは他の通信要件を満たすためのリソース制約を識別するように機能する。したがって、本開示の実施形態は、エンドツーエンド・データパスの各ノードにおけるリソース利用可能性が、エンドツーエンド・データフローの通信要件を満たすことが可能か否かを決定する。例えば、ＴＤＭＡシステム構成では、ＱｏＳ要件などの通信要件が、特定のマルチホップデータパスにおいて使用される各ノードに対して課されるべきタイムスロット（リソース）制約をもたらす最小スループットメトリックを決定づけうる。本開示の実施形態による動作は、エンドツーエンド・データフローに適応するようにデータパス上の各ノードにおいて十分な利用可能なタイムスロットを有するマルチホップデータパスを識別する。
【０００８】
本開示の実施形態は、エンドツーエンド・データパスの各ノードにおけるリソース利用可能性が、エンドツーエンド・データフローの通信要件を満たすことが可能か否かを決定するために、分散型の方法で機能する。したがって、実施形態は、所望されるエンドツーエンド・データフローをサポートするのに適したデータパスを識別する際に使用するために、ネットワーク内でＱｏＳ情報などのリソース制約情報を伝播させる。そのような実施形態は、ＷｉＭｅｄｉａベースのＵＷＢネットワークのプロトコルなど、分散型のＭＡＣプロトコルに関して使用するのに適している。
【０００９】
マルチホップデータ通信リンクは、対応する上りリンクおよび下りリンクを利用してエンドツーエンド・データパスを完成させる、１つまたは複数の中間ネットワークノードを含む。一部の事例では、リソース要件は、各中間ノードにおいて上りリンクまたは下りリンクに関して、あるいは上りリンクおよび下りリンクに関して同時に、満たされない可能性がある。そのようなシナリオは、本開示の実施形態による所望されるエンドツーエンド・データフローをサポートしないものとして識別されるデータパスをもたらす。他の事例では、リソース要件は、各中間ノードにおいて上りリンクおよび下りリンクに関して、またさらに両方のリンクに関して同時に、満たされるが、各中間ノードにおける上りリンクと下りリンクとの間の任意のリソース割当ては、リンクのＱｏＳ要件または他の通信要件を満たさない可能性がある。したがって、本開示の実施形態は、通信要件を満たすエンドツーエンド・データフローを達成するためにリソースを割り当てるように動作可能なリソース割当てアルゴリズムを含む。実施形態のリソース割当てアルゴリズムは、各中間ノードにおいて上りリンクおよび下りリンクに関して、またさらに両方のリンクに関して同時に、リソース要件が満たされるときに、所望される条件が満たされるよう、利用可能なリソースの効率的な使用を確実にするように機能する。
【００１０】
例えば、エンドツーエンド・データパスのすべての中間ノードが、ＴＤＭＡシステム構成において、所望されるエンドツーエンド・データフローについて十分なリソース利用可能性を有すると決定され、したがって、そのデータパスは、所望されるエンドツーエンド・フローをサポートするものとして識別される可能性がある。しかしながら、これらの中間ノードに関係づけられた上りリンクおよび下りリンクにおけるタイムスロットの任意の割当ての結果、通信要件が満たされないことがあり得る。ゆえに、本開示の実施形態のタイムスロット割当てアルゴリズムは、通信要件を満たすエンドツーエンド・データフローを達成するようにタイムスロットを割り当てるように機能することが可能である。
【００１１】
本開示の実施形態は、ＱｏＳを意識したルーティングプロトコルなど、通信要件を意識したルーティングプロトコルに関連して、またはそのようなルーティングプロトコルの一部として利用される。したがって、本開示の実施形態は、複数のデータパスがリソース制約またはその他の通信要件を満たす、最良の利用可能なエンドツーエンド・データパスを決定するように機能することができる。
【００１２】
以上では、以下の本開示の詳細な説明をよりよく理解できるように、本開示の特徴および技術的利点をかなり広範に概説してきた。以下では、特許請求の範囲の主題を形成する本開示のさらなる特徴および利点について説明する。開示される概念および特定の実施形態は、本発明の同一の目的を果たす他の構造を修正または設計するための基礎として容易に利用され得ることが当業者には認識されよう。また、そのような等価な構造は、添付の特許請求の範囲に記載される本開示の趣旨および範囲を逸脱しないことも当業者によって認識されよう。本開示に特徴的であると考えられる新規の特徴は、その構成および動作方法の両方に関して、添付の図に関連して考慮されたときに、さらなる目的、および利点とともに、以下の説明からよりよく理解されるだろう。ただし、各図は、単なる例示および説明の目的で与えられるにすぎず、本開示の制限の定義としては意図されていないことが明確に理解されるべきである。
【００１３】
本開示のより完全な理解のために、次に、添付の図面と併せて解釈される以下の説明を参照する。
【図面の簡単な説明】
【００１４】
【図１】本開示の実施形態による動作のために適合されたネットワークを示す概略図。
【図２】本開示の実施形態による、所望されるエンドツーエンド・データフローを円滑にするためにデータパス上の各ノードにおいて十分な利用可能なリソースを有するマルチホップネットワークデータパスを識別する動作を示す高レベル流れ図。
【図３】ＴＤＭＡシステム構成の、要求される帯域幅と、ＰＨＹレートと、データフローフレームおよびスロット持続時間との間の関係を示す図。
【図４】Ｉ−ＡＣＫ通信技術に関するデータパケット構造を示す図。
【図５】Ｂ−ＡＣＫ通信技術に関するデータパケット構造を示す図。
【図６】本開示の実施形態によるリソース割当てを示す流れ図。
【図７】本開示の実施形態により適合されたプロセッサベースのシステムを示す図。
【発明を実施するための形態】
【００１５】
本開示の概念を理解することを助けるために、実施形態が、ＷｉＭｅｄｉａベースのＵＷＢネットワーク構成、ＷｉＭｅｄｉａ  ＭＡＣ、および／またはＴＤＭＡシステム構成に関連して以下で説明される。しかしながら、本開示の概念は、様々なネットワーク構成、プロトコル、およびリソース割当て技術に適用可能であることを理解されたい。例えば、本開示の実施形態は、任意の分散型のＴＤＭＡ  ＭＡＣに関連して提供されることが可能である。
【００１６】
図１は、本開示の実施形態による動作のために適合されたネットワーク１００の概略図を示す。ネットワーク１００は、パーソナルエリアネットワーク（ＰＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、イントラネット、エクストラネット、インターネット、無線ネットワーク、有線ネットワークなど、様々なネットワーク構成を備えることが可能である。図示される実施形態のネットワーク１００は、リンクＬ１〜Ｌ５を通じて通信状態にあるネットワークノードＮ０〜Ｎ５から成るネットワーク部分１０１を含む。ネットワークノードＮ０〜Ｎ５は、同一または異なるノード構成を有することができ、例えば、コンピュータ、携帯情報端末（ＰＤＡ）、電話、サーバ、ルータ、ゲートウェイ、スイッチ、マルチプレクサ、モデム、無線機、アクセスポイント、基地局などのうちの様々なものを備えることができる。ネットワークリンクＬ１〜Ｌ５は、銅線、光ファイバ線、エアインターフェース（例えば、無線周波数、赤外線など）、および／または同様のものなど、様々な媒体を利用することが可能である。したがって、リンクＬ１〜Ｌ５は、有線リンク、無線リンク、およびそれらの組合せを備えることが可能である。
【００１７】
ネットワークノードＮ０がネットワークノードＮ５とデータ通信状態にあるとすれば、エンドツーエンド・データパスが、リンクＬ１〜Ｌ５によって提供される。したがって、得られるエンドツーエンド・データフローは、マルチホップデータフローである。ネットワークノードＮ１〜Ｎ４は、上述のマルチホップデータフローにおける中間ネットワークノードを備える。
【００１８】
エンドツーエンド・データパスを提供する特定のリンクが示されているが、示されるネットワークにおいて他のリンクおよび／またはエンドツーエンド・データパスが提供されることも可能であることを理解されたい。例えば、ネットワーク１００の様々な追加のリンク（図示せず）が、ネットワークノードＮ０とＮ２の間、Ｎ１とＮ３の間、Ｎ３とＮ５の間などの、ネットワークノードのうちの特定のものの間で利用可能であり得る。さらに、追加のリンク（図示せず）を提供するために利用されることのできる、様々な追加のネットワークノード（やはり図示せず）が、ネットワーク１００内に存在することが可能である。しかしながら、本開示の概念の説明を簡単にするために、図１ではネットワークノードＮ０およびＮ５に関して単一のエンドツーエンド・データパスが示される。
【００１９】
図２は、一実施形態による、所望されるエンドツーエンド・データフローを円滑にするためにデータパス上の各ノードにおいて十分な利用可能なリソースを有するマルチホップネットワークデータパスを識別する動作の高レベル流れ図を示す。示された実施形態のブロック２０１において、所望されるエンドツーエンド・データフローをサポートするのに適したデータパスを識別する際に使用するために、リソース制約情報が、ネットワーク内で伝播される。例えば、ＱｏＳ情報は、ＱｏＳを意識したルーティングプロトコルによって、ネットワーク全体を通じて様々なネットワークノード（例えば、ネットワークノードＮ０〜Ｎ５）に伝播されることが可能である。ネットワークノードに伝播されるＱｏＳ情報には、これらに限るものではないが、要求されるアプリケーションスループット、遅延限界、ジッタ、許容可能な残留パケットロス率などを含めることができる。本開示の実施形態によるそのようなリソース制約情報の伝播は、エンドツーエンド・データパスの各ノードにおけるリソース利用可能性がエンドツーエンド・データフローの通信要件を満たすことが可能か否かを決定する分散型の方法の動作を円滑にする。
【００２０】
示された実施形態のブロック２０２において、エンドツーエンド・データパスの各ノードにおけるリソース利用可能性が、エンドツーエンド・データフローの通信要件を満たすことが可能か否かが決定される。ネットワークノードの１つまたは複数のセットが、それらの対応するリンクとともに、エンドツーエンド・データフローがそれについて所望される発信元と宛先の間にエンドツーエンド・データパスを提供するものとして識別されることができる。ネットワークノードのそのようなセットの各ノードにおけるリソース利用可能性は、その特定のエンドツーエンド・データパスの各ノードにおけるリソース利用可能性が、所望されるエンドツーエンド・データフローの通信要件を満たすことが可能か否かを決定するために、所望されるエンドツーエンド・データフローについてのリソース制約情報に関して分析されることができる。例えば、ＴＤＭＡシステム構成では、ＱｏＳ要件などの通信要件が、特定のマルチホップデータパスにおいて使用される各ノードに対して課されるべきタイムスロット（リソース）制約をもたらす最小スループットメトリックを決定づけうる。実施形態は、そのような情報を分析して、マルチホップデータパスの各ノードにおけるＱｏＳまたは他の通信要件を満たすリソース制約を識別する。例えば、本開示の実施形態は、エンドツーエンド・データフローに適応するようにデータパス上の各ノードにおいて十分な利用可能なタイムスロットを有する特定のマルチホップデータパスを選択するように機能する。
【００２１】
ネットワークノードのセットの各ノードにおけるリソース利用可能性の前述した分析は、発信元と宛先との間にエンドツーエンド・データパスを提供するネットワークノードの各セットの各ノード（または、少なくとも、ネットワークノードの複数のセット）におけるリソース利用可能性が、所望されるエンドツーエンド・データフローの通信要件を満たすことが可能か否かを決定するために、実施形態にしたがって繰り返される。したがって、本開示の実施形態のブロック２０２による動作は、複数のエンドツーエンド・パスがエンドツーエンド・データフロー通信要件を満たすことを決定することができる。
【００２２】
エンドツーエンド・データパスの中間ノードにおける発信元と宛先との間のデータフローは、対応する上りリンクおよび下りリンクを利用する。したがって、所望されるエンドツーエンド・データフローのリソース要件が、各中間ノードにおける上りリンクまたは下りリンクに関して、あるいは上りリンクと下りリンクに関して同時に、満たされないことが可能である。そのようなシナリオは、本開示の実施形態のブロック２０２における動作により、所望されるエンドツーエンド・データフローをサポートしないと決定されるデータパスをもたらす。所望されるエンドツーエンド・データフローに関するリソース要件が、各中間ノードにおいて上りリンクおよび下りリンクに関して、またさらに両方のリンクに関して同時に、満たされる場合、本開示の実施形態のブロック２０２における動作は、データパスが所望されるエンドツーエンド・データフローをサポートすると決定する。
【００２３】
示された実施形態のブロック２０３において、エンドツーエンド・データフローの通信要件を満たすことが可能なエンドツーエンド・データパスが選択され、エンドツーエンド・データパスのネットワークノード、およびそれらの関連リンクに関してリソースが割り当てられる。ブロック２０２において、複数のエンドツーエンド・データパス（例えば、ネットワークノードの異なるセット）が、エンドツーエンド・データフローの通信要件を満たすことが可能な各ノードにおけるリソース利用可能性を備えると決定された場合、ブロック２０３における動作は、所望されるエンドツーエンド・データフローを提供する際に使用するための最良のエンドツーエンド・データパスを選択するために、そのようなエンドツーエンド・データパスに関して可能性のあるリソース割当てを分析することができる。例えば、エンドツーエンド・データフローに関する可能なリソース割当てが、エンドツーエンド・データフローのために使用されるリソース（例えば、タイムスロット）の総数を最小限に抑える、（例えば、ＱｏＳ要件が満たされた状態で新たなフローがネットワークに受け入れられる可能性を高めるために）エンドツーエンド・データパス内の実質的にすべてのノードのところに最大数のリソース（例えば、タイムスロット）を残すなどの、エンドツーエンド・データパスとリソース割当てとの組合せを決定するために、分析されることができる。特定のエンドツーエンド・データパスを選択する際に、エンドツーエンド・データパスのネットワークノードにおける利用可能な電力など、追加的なまたは代替的な分析が利用されることもできる（例えば、他のファクタが存在しない状況で、より長い時間にわたって経路利用可能性を保証するために）。
【００２４】
本開示の実施形態は、所望されるエンドツーエンド・データフローに関して使用するための複数のエンドツーエンド・データパスを選択するように機能することが可能である。例えば、単一の「最良の」エンドツーエンド・データパスを選択するのではなく、開示の実施形態は、通信のフォールトトレランスのためなど、ロバストなルーティングを提供するなどのために、所望されるエンドツーエンド・データフローの通信要件を満たすことが可能な２つ以上のエンドツーエンド・データパスを選択することができる。
【００２５】
各中間ノードにおける上りリンクと下りリンクとの間の任意のリソース割当てが、リンクのＱｏＳまたは他の通信要件を満たさない可能性がある。したがって、本開示の実施形態によるブロック２０３における操作は、リソース割当てアルゴリズムを用いるなどして、通信要件を満たすエンドツーエンド・データフローを達成するようにリソースを割り当てる。
【００２６】
例えば、エンドツーエンド・データパスのすべての中間ノードが、ＴＤＭＡシステム構成における所望されるエンドツーエンド・データフローについて十分なリソース利用可能性を有すると決定され、したがって、データパスは、所望されるエンドツーエンド・データフローをサポートするものとして識別される可能性がある。しかしながら、上りリンクおよび下りリンクにおけるタイムスロットの任意の割当ては、通信要件が満たされないという結果をまねく可能性がある。したがって、本開示の実施形態のタイムスロット割当てアルゴリズムは、通信要件を満たすエンドツーエンド・データフローを達成するようにタイムスロットを割り当てるように機能することが可能である。
【００２７】
以上から、各中間ノードにおいて上りリンクおよび下りリンクに関して、またさらに両方のリンクに関して同時に、リソース要件が満たされるときに、所望される条件が満たされるよう、実施形態のブロック２０３における操作が、利用可能なリソースの効率的な使用を確実にすることがわかる。したがって、本開示の実施形態は、ＱｏＳを意識したルーティングプロトコルなど、通信要件を意識したルーティングプロトコルに関連して、またはそのようなルーティングプロトコルの一部として利用される。
【００２８】
図２についての以上の説明は、高いレベルで本開示の実施形態による動作を説明することを理解されたい。本開示の概念による動作を提供することに関するさらなる詳細が、以下で与えられる。
【００２９】
本発明の実施形態による、エンドツーエンド・データパスの各ノードにおけるリソース利用可能性がエンドツーエンド・データフローの通信要件を満たすことが可能か否かを決定する動作の提供に際して、Ｎを、発信元から宛先までのエンドツーエンド・データパス内のノードの数とし（例えば、図１に示されるエンドツーエンド・データパスでは、Ｎ＝６）、ｎ（Ｌ）を、エンドツーエンド・データパス内のリンクの数とする（例えば、図１に示されるエンドツーエンド・データパスでは、ｎ（Ｌ）＝５）。したがって、
【数１】
2014112852.tif 000003
【００３０】
Ｌijを、ノードＮiとＮjとの間のリンクとし、Ｒappを、（リンクあたりの）要求される帯域幅とし、Ｒijを、リンクＬijに関してサポートされ得る物理層（ＰＨＹ）レートとし、ｐijを、リンクＬijに関する、対応する物理層パケット誤り率（ＰＥＲ）とする。
【００３１】
図３は、ＷｉＭｅｄｉａ  ＵＷＢネットワークに関して利用され得るような、ＴＤＭＡシステム構成の、要求される帯域幅（Ｒapp）と、ＰＨＹレート（Ｒij）と、データフローフレームおよびスロット持続時間との間の関係を図示する。図３では、ＴSFは、ＷｉＭｅｄｉａスーパーフレーム持続時間であり、Ｔdは、予約の合計持続時間であり、したがって、媒体アクセススロット（ＭＡＳ）の数によって決まる。
【００３２】
以上から、
【数２】
2014112852.tif 000004
【００３３】
であり、ただし、ηは、リンクＬijに関するＭＡＣ効率（すなわち、ペイロード伝送の時間の割合）である。Ｔdについて解くと、以下が得られる。
【数３】
2014112852.tif 000005
【００３４】
ゆえに、リンクＬijに必要とされるＭＡＳの数は、次式によって与えられる。
【数４】
2014112852.tif 000006
【００３５】
以上では、ＴSF＝２５６ＴMASであると想定される。式（４）は、所望されるエンドツーエンド・データフローのそのホップをサポートするためにエンドツーエンド・データパスの中間ネットワークノードのそれぞれに必要とされるスロットの数を示す公式を与えることを理解されたい。
【００３６】
ＭＡＣ効率ηを推定するために、２つの例が以下で考慮される。第１の例は、中間確認応答（immediate acknowledgement）（Ｉ−ＡＣＫ）通信技術を使用するフローに関連したＭＡＣ効率を考慮し、第２の例は、ＷｉＭｅｄｉａ  ＵＷＢネットワークにおいて実施され得るような、ブロック確認応答（block acknowledgement）（Ｂ−ＡＣＫ）通信技術を使用するフローに関連したＭＡＣ効率を考慮する。
【００３７】
図４は、I−ＡＣＫ確認応答ポリシーに関するデータトランザクションシーケンスを示す。図４のデータパケット構造は、第１の物理層コンバージェンスプロトコル（physical layer convergence protocol）（ＰＬＣＰ）プリアンブルと、第１のＰＬＣＰヘッダと、ペイロードフレームと、短いフレーム間隔（short inter-frame space）（ＳＩＦＳ）と、第２の（ＡＣＫ）ＰＬＣＰプリアンブルと、第２の（ＡＣＫ）ＰＬＣＰヘッダと、第２の（ＡＣＫ）ＳＩＦＳとを備える。ＰＬＣＰプリアンブルが９．３７５ｕｓの持続時間であり、ＰＬＣＰヘッダが３．７５ｕｓの持続時間であり、ＳＩＦＳが１０ｕｓの持続時間である場合（ＷｉＭｅｄｉａ  ＵＷＢネットワーク構成の場合にあり得るように）、図４のデータパケット構造に関する合計のオーバーヘッドは、４６．２５ｕｓである。ゆえに、４８０Ｍｂｐｓで４０９６オクテット物理層サービスデータユニット（ＰＳＤＵ）伝送を想定すると、転送持続時間は、６９．３７５ｕｓであり、ＭＡＣ効率ηは、０．６である。５３．３Ｍｂｐｓで５１２オクテットＰＳＤＵ伝送を想定すると、転送持続時間は、７６．８７５ｕｓであり、ＭＡＣ効率ηは、０．６２４である。
【００３８】
次に図５を参照すると、Ｂ−ＡＣＫ確認応答ポリシーに関するデータトランザクションシーケンスが示されている。図５のデータパケット構造は、第１のＰＬＣＰプリアンブルと、第１のＰＬＣＰヘッダと、ペイロードフレームと、複数の最小フレーム間隔（ＭＩＦＳ）と、複数のバーストプリアンブルと、複数のＰＬＣＰヘッダと、複数のペイロードフレームと、ＳＩＦＳと、第２の（Ｂ−ＡＣＫ）ＰＬＣＰプリアンブルと、第２の（Ｂ−ＡＣＫ）ＰＬＣＰヘッダと、第２の（Ｂ−ＡＣＫ）ＳＩＦＳと、Ｂ−ＡＣＫ本体とを備える。例えば、バーストモードが、バーストプリアンブルおよび８つのバーストを伴って使用される事例を考える。第１のＰＬＣＰプリアンブル、ＰＬＣＰヘッダ、およびペイロードフレームの後に、それぞれが、ＭＩＦＳ、バーストプリアンブル、ＰＬＣＰヘッダ、ペイロードフレーム、ＳＩＦＳ、ＡＣＫ  ＰＬＣＰプリアンブル、ＡＣＫ  ＰＬＣＰヘッダ、およびＡＣＫ  ＳＩＦＳから成る７つのバーストが続く。第１のＰＬＣＰプリアンブルが９．３７５ｕｓの持続時間であり、第２〜第８のＰＬＣＰプリアンブルがそれぞれ５．６２５ｕｓの持続時間であり、８つのＰＬＣＰヘッダがそれぞれ３．７５ｕｓの持続時間であり、ＭＩＦＳがそれぞれ１．８７５ｕｓの持続時間であり、ＳＩＦＳが１０ｕｓの持続時間であり、Ｂ−ＡＣＫが１．８７５ｕｓの持続時間である場合（ＷｉＭｅｄｉａ  ＵＷＢネットワーク構成の場合にあり得るように）、図４のデータパケット構造に関する合計のオーバーヘッドは、１２６．８７５ｕｓである。ゆえに、４８０Ｍｂｐｓで４０９６オクテットＰＳＤＵ伝送を想定すると、転送持続時間は、５５５ｕｓであり、ＭＡＣ効率ηは、０．８１４である。
【００３９】
以上から、ほとんどのシナリオに関して、以下のことがわかる。
【数５】
2014112852.tif 000007
【００４０】
平均ＭＡＣ効率の控えめな推定η＝０．７をとり、この平均ＭＡＣ効率値を使用して式（４）を解くと、
【数６】
2014112852.tif 000008
【００４１】
が得られる。
【数７】
2014112852.tif 000009
【００４２】
であるものと仮定すると、
【数８】
2014112852.tif 000010
【００４３】
である。
【００４４】
式（６）および式（８）は、発信元と宛先との間にエンドツーエンド・データパスを提供するネットワークノードの各セットの各ノードにおけるリソース利用可能性が、所望されるエンドツーエンド・データフローの通信要件を満たすことが可能な場合、エンドツーエンド・パスの各ホップについて満たされるはずである。
【００４５】
ｘi,kが、ノードｉの第ｋのＭＡＳ利用可能性を表すものとする。したがって、
【数９】
2014112852.tif 000011
【００４６】
同様に、ｘj,kが、ノードｊの第ｋのＭＡＳ利用可能性を表すものとする。
【００４７】
Ｓij,kが、ノードｉとノードｊとの間のリンクＬijに関する第ｋのＭＡＳ利用可能性を表すものとする。したがって、
【数１０】
2014112852.tif 000012
【００４８】
である。
【００４９】
次式
【数１１】
2014112852.tif 000013
【００５０】
が、ノードｉとノードｊの両方においてリンクＬijに関して利用可能なＭＡＳの数を表すと仮定する。したがって、
【数１２】
2014112852.tif 000014
【００５１】
である。
【００５２】
発信元ネットワークノードおよび宛先ネットワークノードを除く、エンドツーエンド・データパスにおけるすべてのネットワークノードが、２つの同時予約をサポートすべきである。具体的には、これらのネットワークノードは、同時に、１つの予約を予約ターゲットとして、および別の予約を予約オーナーとして、サポートすべきである。ゆえに、ノードｉとノードｊとの間のＬij、およびノードｊとノードｈとの間のＬjhという２つのリンクを考慮すると、
【数１３】
2014112852.tif 000015
【００５３】
である。
【００５４】
中間ノードｊにおける利用可能なＭＡＳの総数は、以下を満たさなければならない。
【数１４】
2014112852.tif 000016
【００５５】
第１の予約について考慮されるＭＡＳは、第２の予約には利用可能ではない。ゆえに、各リンクにおけるＭＡＳは、互いに干渉しない。
【００５６】
式（１１）、（１２）、および（１３）は、所望されるエンドツーエンド・データフローがサポートされることになる場合に、エンドツーエンド・データフロー内の各中間ネットワークノードに関して満たされるべきリソース制約のセットを表す。したがって、前出の式（６）および（８）を満たすことに加えて、式（１１）、（１２）、および（１３）は、それぞれ、両方の予約をサポートするために、したがって、所望されるエンドツーエンド・データフローをサポートするために、中間ノードｊにおいて満たされなければならない。式（１１）および（１２）のうちの１つしか満たされない場合、そのことは、一方の予約だけがサポートされることができ、他方の予約はサポートされないことを意味する。式（１１）および（１２）の両方が満たされるが、式（１３）は満たされない場合、両方の予約は、独立（stand-alone）ベースではサポートされることができるが、２つの同時予約は、したがって、所望されるエンドツーエンド・データフローは、サポートされることができない。ノードｉおよび／またはノードｈがまた中間ノードでもある場合、同一の実行可能性チェックが、また、それらのノードにおいて実行されることになる。
【００５７】
実施形態による動作に際して、ネットワークノードは、それが２ホップ近隣内でそのネットワークノード自体にとって利用可能であると見なすＭＡＳのリストを送る。例えば、ＥＣＭＡ−３６８仕様に従う動作では、分散型の予約プロトコル（ＤＲＰ）利用可能性情報要素（ＩＥ）が、ビーコンフレームにおいてＤＲＰ利用可能性ＩＥにおける利用可能なＭＡＳのリストを送ることによってＭＡＳの現在の利用についてのネットワークノードによる認識を示すために、そのネットワークノードによって使用されることができる。そのような情報を使用して、エンドツーエンド・データパスにおけるネットワークノードは、リソース制約（例えば、式（１１）、（１２）、および（１３）に示される）が満たされるか否かを評価することが可能である。
【００５８】
３つの式（１１）、（１２）、および（１３）のすべてが個々に満たされるときでさえ、Ｌij上およびＬjh上の２つの予約の間のスロットの任意の割当てが、両方の予約の要件を満たさない可能性がある。図６に示されるリソース割当て方法は、本開示の実施形態に従って、Ｌij上およびＬjh上の２つの予約の間のスロットの割当てが両方の予約の要件を満たすことを確実にするために用いられる。
【００５９】
図６に示される実施形態のブロック６０１において、所望されるエンドツーエンド・データフローをサポートするために利用可能な十分なリソースを有するものとして識別されたエンドツーエンド・データパスの中間ネットワークノードが、リソース割当てのために選択される。ブロック６０２において、セットＳij−Ｓij∩Ｓjhからのスロットが、選択されたネットワークノードのリンクＬijに割り当てられる。ブロック６０３において、リンクＬijに関する通信要件が、ブロック６０２において割り当てられたスロットによって満たされると判定された場合、リンクＬijに対する割当ては完了であり、示された実施形態による処理は、ブロック６０５に進む。しかし、ブロック６０３において、リンクＬijに関する通信要件が、ブロック６０２において割り当てられたスロットによって満たされないと判定された場合、処理は、リンクＬijに対するさらなるスロット割当てのためにブロック６０４に進む。ブロック６０４において、リンクＬijのための残りのスロットが、セットＳij∩Ｓjhから割り当てられる。
【００６０】
ブロック６０５において、セットＳjh−Ｓij∩Ｓjhからのスロットが、選択されたネットワークノードのリンクＬjhに割り当てられる。ブロック６０６において、リンクＬjhに関する通信要件が、ブロック６０５において割り当てられたスロットによって満たされると判定された場合、リンクＬjhに対する割当ては完了であり、示された実施形態による処理は、ブロック６０８に進む。しかし、ブロック６０６において、リンクＬjhに関する通信要件が、ブロック６０５において割り当てられたスロットによって満たされないと判定された場合、処理は、リンクＬjhに対するさらなるスロット割当てのためにブロック６０７に進む。ブロック６０７において、リンクＬjhのための残りのスロットが、セットＳij∩Ｓjhから割り当てられる。
【００６１】
ブロック６０８において、さらなる中間ネットワークノードがリソース割当てのためにエンドツーエンド・データパス内に存在するか否かについての判定が行われる。さらなる中間ネットワークノードが存在する場合、示された実施形態による処理は、別の中間ネットワークノードの選択のためにブロック６０１に戻る。さらなる中間ネットワークノードが存在しない場合、示された実施形態による処理は、ブロック６０９に進み、エンドツーエンド・データパスに関するリソース割当てが終了される。
【００６２】
以上による動作をさらに説明するために、ＮMAS,ij＝１０、ＮMAS,jh＝８、ｎ（Ｓij）＝１２、ｎ（Ｓjh）＝８、およびｎ（Ｓij∩Ｓjh）＝２とする。したがって、ｎ（Ｓij∪Ｓjh）＝１２＋８−２＝１８である。式（１１）、（１２）、および（１３）のそれぞれが満たされる。しかし、リンクＬijのための１０のスロットが、１つまたは２つのスロットがＳij∩Ｓjhからであるように割り当てられる場合、リンクＬjhに関するスロット要件は、満たされることができない。図６に示されるスロット割当て方法は、所望されるエンドツーエンド・データフローの目標を達成する可能性を高め、および／または、図６に示されるスロット割当て方法は、所望されるエンドツーエンド・データフローの通信要件を満たすように、複数のエンドツーエンド・データパスが各ノードにおいてリソース利用可能性を提供できる場合に、所望されるエンドツーエンド・データフローを提供する際に使用するための特定のエンドツーエンド・データパスを選択する際に用いられることができる。
【００６３】
本開示の実施形態は、ＭＡＳの総数を最小限に抑えることが通信時間（air time）を最小限に抑えることと等価であるので、エンドツーエンド・データパスのすべてのリンクにわたって最小限の総数のＭＡＳを利用する通信要件を満たすリソース割当てを有する複数のエンドツーエンド・データパスのうちの特定のエンドツーエンド・データパスを選択するように、追加的にまたは代替的に機能する。すべてのリンクにわたるＭＡＳの総数、ＮTotalは、以下によって与えられる。
【数１５】
2014112852.tif 000017
【００６４】
すべてのリンクにわたって同一のＭＡＣ効率を想定すると、以下の式が最小にされるべきである。
【数１６】
2014112852.tif 000018
【００６５】
ここで、所望されるエンドツーエンド・データフローの通信要件を満たす複数のエンドツーエンド・データパスからの最良のエンドツーエンド・データパスを選択するために、Ｒ’ij＝Ｒij×（１−ｐij）である。
【００６６】
本明細書で説明される方法は、アプリケーションに応じて様々なコンポーネントによって実装されることができる。例えば、これらの方法は、ハードウェア、ファームウェア、ソフトウェア、またはそれらの任意の組合せにおいて実装されることができる。ハードウェア実装の場合、処理ユニットは、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ）、デジタルシグナルプロセッサ（ＤＳＰ）、デジタル信号処理デバイス（ＤＳＰＤ）、プログラマブル論理デバイス（ＰＬＤ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、プロセッサ、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子デバイス、本明細書で説明される機能を実行するように設計された他の電子ユニット、またはそれらの組合せ内に実装されることができる。
【００６７】
ファームウェアおよび／またはソフトウェア実装の場合、方法は、本明細書で説明される機能を実行するモジュール（例えば、プロシージャ、関数など）を用いて実装されることが可能である。命令を実体化する任意のマシン可読媒体が、本明細書で説明される方法を実装する際に使用されることが可能である。例えば、ソフトウェアコードが、メモリに格納され、プロセッサユニットによって実行されることが可能である。メモリは、プロセッサユニット内に実装されることができ、またはプロセッサユニットの外部に実装されることができる。本明細書で使用される「メモリ」という用語は、任意のタイプの長期、短期、揮発性、不揮発性、またはその他のメモリを指し、いずれか特定のタイプのメモリ、いずれか特定の数のメモリ、またはメモリがそれに格納されるいずれか特定のタイプの媒体に限定されるものではない。
【００６８】
ファームウェアおよび／またはソフトウェアにおいて実装される場合、機能は、コンピュータ可読媒体上に１つまたは複数の命令もしくはコードとして格納されることが可能である。例としては、データ構造で符号化されたコンピュータ可読媒体、およびコンピュータプログラムで符号化されたコンピュータ可読媒体が含まれる。コンピュータ可読媒体には、物理的なコンピュータ記憶媒体が含まれる。記憶媒体は、コンピュータによってアクセスされることができる任意の利用可能な媒体であることが可能である。限定するものではなく一例として、そのようなコンピュータ可読媒体は、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、電気的に消去可能なプログラマブル読み取り専用メモリ（ＥＥＰＲＯＭ）、コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）もしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、または命令もしくはデータ構造の形態で所望されるプログラムコードを格納するために使用されることができ、コンピュータによってアクセスされることができる他の任意の媒体を備えることが可能であり、本明細書で使用されるディスク（ｄｉｓｋ）およびディスク（ｄｉｓｃ）には、コンパクトディスク（ＣＤ）、レーザディスク（登録商標）、光ディスク、デジタル多用途ディスク（ＤＶＤ）、フロッピー（登録商標）ディスク、およびブルーレイディスクが含まれており、ここで、ディスク（ｄｉｓｋ）は、通常、データを磁気的に再生するのに対して、ディスク（ｄｉｓｃ）は、レーザを使用してデータを光学的に再生する。また、以上の組合せも、コンピュータ可読媒体の範囲内に含まれる。
【００６９】
コンピュータ可読媒体上の格納に加えて、命令および／またはデータは、通信装置に含まれる伝送媒体上の信号として提供されることも可能である。例えば、通信装置は、命令およびデータを示す信号を有するトランシーバを含むことが可能である。命令およびデータは、１つまたは複数のプロセッサに、特許請求の範囲で概要が述べられる機能を実施させるように構成される。
【００７０】
図７は、前述したコードセグメントの制御下で本明細書で説明される操作を提供するように本開示にしたがって適合されたプロセッサベースのシステム７００を示す。プロセッサベースのシステム７００は、図１のネットワークノードＮ０〜Ｎ５のいずれかのようなネットワークノード、あるいは１つまたは複数のネットワークノードに結合されたシステムを備えることが可能である。プロセッサ７０１は、システムバス７０２に結合される。プロセッサ７０１は、インテルコーポレーション（Intel Corporation）から入手可能なＰＥＮＴＩＵＭ（登録商標）プロセッサなどの汎用の中央処理装置（ＣＰＵ）、または特定用途向け集積回路（ＡＳＩＣ）、プログラマブルゲートアレイ（ＰＧＡ）などの専用プロセッサを備えることが可能である。しかし、本開示は、プロセッサ７０１が本明細書で説明される本発明の操作をサポートするのであれば、プロセッサ７０１のアーキテクチャによって制限されない。バス７０２は、ＲＡＭ、ＲＯＭ、フラッシュメモリ、光メモリ、磁気メモリなどの任意の適切なコンピュータ可読媒体を備えることが可能な、メモリ７０３に結合される。メモリ７０３は、本明細書で説明される操作を円滑にするために、ユーザデータ、システムデータ、リソース制約情報、プログラムコードなどを格納する。バス７０２は、また、入出力（Ｉ／Ｏ）インターフェース７０４およびネットワークインターフェース７０５に結合される。Ｉ／Ｏインターフェース７０４は、キーボード、キーパッド、ポインティングデバイス、ディスプレイデバイスなどを備えることができるような、様々な周辺装置、コンポーネント、デバイスなどのインターフェーシングを提供する。したがって、Ｉ／Ｏインターフェース７０４は、複数の個別のインターフェース、インターフェースプロトコル、などを備えることが可能である。ネットワークインターフェース７０５は、１つまたは複数の有線リンク、無線リンク、光ファイバリンクなどを備えることができるような、１つまたは複数のネットワークリンクとのインターフェーシングを提供することができる。したがって、ネットワークインターフェース７０５は、１つまたは複数のネットワークプロトコルにしたがって動作する単一のネットワークインターフェースまたは複数のネットワークインターフェースを備えることが可能である。
【００７１】
本開示およびその利点について詳細に説明してきたが、添付の特許請求の範囲によって定義される本開示の趣旨および範囲を逸脱することなく、ここにおいて様々な変更、置換、および修正が行われ得ることを理解されたい。さらに、本願の範囲は、本明細書で説明されるプロセス、マシン、製造、物質の組成、手段、方法、およびステップの特定の実施形態だけに限定されることは意図されていない。本発明の開示から当業者には容易に理解されるように、本明細書で説明される対応する実施形態と実質的に同一の機能を実行する、または実質的に同一の結果を達成する、現存するまたは後に開発される、プロセス、マシン、製造、物質の組成、手段、方法、またはステップが、本発明にしたがって利用されることが可能である。したがって、添付の特許請求の範囲は、その範囲内に、そのようなプロセス、マシン、製造、物質の組成、手段、方法、またはステップを含むことを意図している。
【図１】
2014112852.tif 000019
【図２】
2014112852.tif 000020
【図３】
2014112852.tif 000021
【図４】
2014112852.tif 000022
【図５】
2014112852.tif 000023
【図６】
2014112852.tif 000024
【図７】
2014112852.tif 000025
【手続補正書】
【提出日】平成26年1月20日(2014.1.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するための方法であって、前記方法は、ノードが実行し、
前記ネットワークのノードにリソース制約情報を伝播させること、
前記リソース制約情報を使用して、前記少なくとも１つのエンドツーエンド・データパスの各ネットワークノードにおけるリソース利用可能性が、前記エンドツーエンド・データフローの前記所望される通信属性を満たすことが可能か否かを決定すること、
前記エンドツーエンド・データフローを提供する際に使用するために、前記所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有すると決定された前記少なくとも１つのエンドツーエンド・データパスのうちのエンドツーエンド・データパスを選択すること、および
前記所望される通信属性を満たす前記エンドツーエンド・データフローを提供するために、前記選択されたエンドツーエンド・データパスの各ネットワークノードに通信リソースを割り当てること、を備える、方法。
【請求項２】
前記所望される通信属性は、所望されるサービス品質（ＱｏＳ）を備える、請求項１に記載の方法。
【請求項３】
エンドツーエンド・データパスを前記選択することは、
前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を最小限に抑えること、
前記選択されたエンドツーエンド・データパスにおけるすべてのノードに最大数の通信リソースを残すこと、および、
前記選択されたエンドツーエンド・データパスのネットワークノードの電力消費量を最小限に抑えること、
のうちの少なくとも１つに少なくとも部分的に基づいて、選択を行う、請求項１に記載の方法。
【請求項４】
前記通信リソースは、時分割多元接続（ＴＤＭＡ）ネットワーク通信プロトコルのタイムスロットを備える、請求項３に記載の方法。
【請求項５】
エンドツーエンド・データパスを前記選択することは、前記エンドツーエンド・データフローを提供するための複数のエンドツーエンド・データパスを選択することを備える、請求項１に記載の方法。
【請求項６】
エンドツーエンド・データパスを前記選択することは、
少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析して、前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を決定すること、および、前記所望されるエンドツーエンド・データフローのために使用される最小の総数の通信リソースを有するリソース割当ておよびエンドツーエンド・データパスを選択することを備える、請求項１に記載の方法。
【請求項７】
エンドツーエンド・データパスを前記選択することは、
前記少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析して、前記エンドツーエンド・データフローのために使用された場合に前記少なくとも１つのエンドツーエンド・データパス内のノードに残る通信リソースの数を決定すること、および、すべてのノードに最大数のスロットを残すエンドツーエンド・データパスおよびリソース割当てを選択することを備える、請求項１に記載の方法。
【請求項８】
通信リソースを前記割り当てることは、
前記エンドツーエンド・データフローの前記通信属性を満たすように前記選択されたエンドツーエンド・データパスの各中間ノードにおいて上りリンクと下りリンクとの間で通信リソースを割り当てることを備える、請求項１に記載の方法。
【請求項９】
通信リソースを前記割り当てることは、
前記選択されたエンドツーエンド・データパスの中間ネットワークノードに関して、
下りネットワークノードにおいて利用可能でない、前記中間ネットワークノードおよび上りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した上りリンクに通信リソースを割り当てること、
上りの要件が前記割当てによって満たされないままである場合、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記上りリンクに通信リソースを割り当てること、
前記上りネットワークノードにおいて利用可能でない、前記中間ネットワークノードおよび前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した下りリンクに通信リソースを割り当てること、および、
下りの要件が前記割当てによって満たされないままである場合、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記下りリンクに通信リソースを割り当てること、を備える、請求項１に記載の方法。
【請求項１０】
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するためのシステムであって、前記システムは、
メモリとプロセッサとを有するネットワークノードを備え、前記メモリは、隣接ネットワークノードに関するリソース制約情報を格納し、前記隣接ネットワークノードは、エンドツーエンド・データパスに関する上りネットワークノードと、前記エンドツーエンド・データパスに関する下りネットワークノードとを備え、前記メモリはさらに、前記エンドツーエンド・データパスの前記上りネットワークノードおよび前記下りネットワークノードに関する前記リソース制約情報を使用して、前記ネットワークノードにおけるネットワークリソース利用可能性が、所望されるエンドツーエンド・データフローの通信要件を満たすか否かを決定するように動作可能な前記プロセッサの動作を定義するコードを格納し、前記メモリはさらに、前記通信要件を満たす前記所望されるエンドツーエンド・データフローを達成するために前記ネットワークノードにおいてリソースを割り当てるように動作可能な前記プロセッサの動作を定義するコードを格納する、システム。
【請求項１１】
前記割り当てられたリソースは、時分割多元接続（ＴＤＭＡ）ネットワークプロトコルのタイムスロットを備える、請求項１０に記載のシステム。
【請求項１２】
前記ネットワークノードは、コンピュータ、携帯情報端末（ＰＤＡ）、電話、サーバ、ルータ、ゲートウェイ、スイッチ、マルチプレクサ、モデム、無線機、アクセスポイント、および基地局からなる群から選択されるノード構成を備える、請求項１０に記載のシステム。
【請求項１３】
メモリとプロセッサとを有する複数のネットワークノードを備えており、前記メモリは、隣接ネットワークノードに関するリソース制約情報を格納し、前記メモリはさらに、前記リソース制約情報を使用して、対応するネットワークノードにおけるネットワークリソース利用可能性が前記所望されるエンドツーエンド・データフローの通信要件を満たすか否かを決定するように動作可能な前記プロセッサの動作を定義するコードを格納し、前記メモリはさらに、前記通信要件を満たす前記所望されるエンドツーエンド・データフローを達成するために前記対応するネットワークノードにおいてリソースを割り当てるように動作可能な前記プロセッサの動作を定義するコードを格納する、請求項１０に記載のシステム。
【請求項１４】
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するためのシステムであって、
前記ネットワークのノードに関するリソース制約情報を使用して、前記少なくとも１つのエンドツーエンド・データパスの各ネットワークノードにおけるリソース利用可能性が、前記エンドツーエンド・データフローの前記所望される通信属性を満たすことが可能か否かを決定するための手段と、
前記エンドツーエンド・データフローを提供する際に使用するために、前記所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有すると決定された前記少なくとも１つのエンドツーエンド・データパスのうちのエンドツーエンド・データパスを選択するための手段と、
前記所望される通信属性を満たす前記エンドツーエンド・データフローを提供するために前記選択されたエンドツーエンド・データパスの各ネットワークノードに通信リソースを割り当てるための手段と、を備える、システム。
【請求項１５】
前記リソース制約情報を前記ネットワークの前記ノードに伝播させるための手段をさらに備える、請求項１４に記載のシステム。
【請求項１６】
前記通信リソースは、時分割多元接続（ＴＤＭＡ）ネットワーク通信プロトコルのタイムスロットを備え、前記リソース制約情報は、前記ＴＤＭＡ通信プロトコルのタイムスロットの利用可能性に関する情報を備える、請求項１４に記載のシステム。
【請求項１７】
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するためのコンピュータプログラムであって、
コンピュータに、前記ネットワークのノードに関するリソース制約情報を使用して、前記少なくとも１つのエンドツーエンド・データパスの各ネットワークノードにおけるリソース利用可能性が、前記エンドツーエンド・データフローの前記所望される通信属性を満たすことが可能か否かを決定させるためのコード、
前記コンピュータに、前記エンドツーエンド・データフローを提供する際に使用するために、前記所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有すると決定された前記少なくとも１つのエンドツーエンド・データパスのうちのエンドツーエンド・データパスを選択させるためのコード、および、
前記コンピュータに、前記所望される通信属性を満たす前記エンドツーエンド・データフローを提供するために前記選択されたエンドツーエンド・データパスの各ネットワークノードに通信リソースを割り当てさせるためのコード、を備えるコンピュータプログラム。
【請求項１８】
前記コンピュータに、エンドツーエンド・データパスを選択させるための前記コードは、前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を最小限に抑えること、前記選択されるエンドツーエンド・データパスにおけるすべてのノードに最大数の通信リソースを残すこと、および、前記選択されたエンドツーエンド・データパスのネットワークノードにおける利用可能な電力、のうちの少なくとも１つに少なくとも部分的に基づいて選択を行うように動作可能である、請求項１７に記載のコンピュータプログラム。
【請求項１９】
前記コンピュータに、エンドツーエンド・データパスを選択させるための前記コードは、
前記コンピュータに、少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析させるためのコードと、
前記コンピュータに、分析するための前記コードからの情報に少なくとも部分的に基づいて、前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を決定させるためのコードと、
前記コンピュータに、前記所望されるエンドツーエンド・データフローのために使用される最小の総数の通信リソースを有するエンドツーエンド・データパスおよびリソース割当てを選択させるためのコードと、を備える、請求項１７に記載のコンピュータプログラム。
【請求項２０】
前記コンピュータに、エンドツーエンド・データパスを選択させるための前記コードは、
前記コンピュータに、前記少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析させるためのコードと、
前記コンピュータに、分析するための前記コードからの情報に少なくとも部分的に基づいて、前記エンドツーエンド・データフローのために使用された場合に前記少なくとも１つのエンドツーエンド・データパス内のノードに残る通信リソースの数を決定するためのコードと、
前記コンピュータに、すべてのノードに最大数のスロットを残すエンドツーエンド・データパスおよびリソース割当てを選択させるためのコードと、を備える、請求項１７に記載のコンピュータプログラム。
【請求項２１】
前記コンピュータに、通信リソースを割り当てさせるための前記コードは、
前記コンピュータに、下りネットワークノードにおいて利用可能でない、中間ネットワークノードおよび上りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した上りリンクに通信リソースを割り当てさせるためのコードであって、上りの要件が前記上りリンクへのリソースの前記割当てによって満たされないままである場合、割り当てるための前記コードは、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記上りリンクに通信リソースを割り当てる、コードと、
前記コンピュータに、前記上りネットワークノードにおいて利用可能でない、前記中間ネットワークノードおよび前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した下りリンクに通信リソースを割り当てさせるためのコードであって、下りの要件が前記下りリンクへのリソースの前記割当てによって満たされないままである場合、割り当てるための前記コードは、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記下りリンクに通信リソースを割り当てる、コードと、を備える、請求項１７に記載のコンピュータプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００７１
【補正方法】変更
【補正の内容】
【００７１】
本開示およびその利点について詳細に説明してきたが、添付の特許請求の範囲によって定義される本開示の趣旨および範囲を逸脱することなく、ここにおいて様々な変更、置換、および修正が行われ得ることを理解されたい。さらに、本願の範囲は、本明細書で説明されるプロセス、マシン、製造、物質の組成、手段、方法、およびステップの特定の実施形態だけに限定されることは意図されていない。本発明の開示から当業者には容易に理解されるように、本明細書で説明される対応する実施形態と実質的に同一の機能を実行する、または実質的に同一の結果を達成する、現存するまたは後に開発される、プロセス、マシン、製造、物質の組成、手段、方法、またはステップが、本発明にしたがって利用されることが可能である。したがって、添付の特許請求の範囲は、その範囲内に、そのようなプロセス、マシン、製造、物質の組成、手段、方法、またはステップを含むことを意図している。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
分散型のマルチホップ時分割多元接続（ＴＤＭＡ）ネットワークにおいてエンドツーエンド・データパスを選択する方法であって、前記エンドツーエンド・データパスは、各ノードにおいて十分な利用可能なリソースを有する複数のエンドツーエンド・データパスから選択され、それによって、所望されるエンドツーエンド・データフローに関するサービス品質（ＱｏＳ）を保証し、前記方法は、
前記所望されるエンドツーエンド・データフローのために使用されるスロットの総数を最小限に抑えること、
前記選択されたエンドツーエンド・データパスにおける実質的にすべてのノードに最大数のスロットを残し、それによって、新たなデータフローが、それらのＱｏＳが満たされた状態で前記ネットワークに受け入れられる可能性を高めること、および、
前記選択されたエンドツーエンド・データパスにおける中間ネットワークノードの電力消費量を最小限に抑え、それによって、他のファクタが存在しない状況で、より長い時間にわたって経路利用可能性を保証すること、
のうちの少なくとも１つに少なくとも部分的に基づいて、前記所望されるエンドツーエンド・データフローのために少なくとも１つのエンドツーエンド・データパスを選択することを備える、方法。
［Ｃ２］
前記選択することは、ロバストなルーティングのために複数のエンドツーエンド・データパスを選択することを備える、［Ｃ１］に記載の方法。
［Ｃ３］
前記複数のエンドツーエンド・データパスに関してスロット割当てを分析して、前記所望されるエンドツーエンド・データフローのために使用されるスロットの総数を決定することをさらに備え、少なくとも１つのエンドツーエンド・データパスを前記選択することは、前記分析によって決定される前記所望されるエンドツーエンド・データフローのために使用される最小の総数のスロットを有するエンドツーエンド・データパスを選択する、［Ｃ１］に記載の方法。
［Ｃ４］
前記複数のエンドツーエンド・データパスに関してスロット割当てを分析して、前記所望されるエンドツーエンド・データフローのために使用された場合に前記エンドツーエンド・データパス内のノードに残るスロットの数を決定することをさらに備え、少なくとも１つのエンドツーエンド・データパスを前記選択することは、実質的にすべてのノードに最大数のスロットを残すエンドツーエンド・データパスを選択する、［Ｃ１］に記載の方法。
［Ｃ５］
前記所望されるエンドツーエンド・データフローのＱｏＳ要件を満たすように前記選択されたエンドツーエンド・データパスの各中間ノードにおいて上りリンクと下りリンクとの間でスロットを割り当てることをさらに備える、［Ｃ１］に記載の方法。
［Ｃ６］
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するための方法であって、
前記ネットワークのノードにリソース制約情報を伝播させること、
前記リソース制約情報を使用して、前記少なくとも１つのエンドツーエンド・データパスの各ネットワークノードにおけるリソース利用可能性が、前記エンドツーエンド・データフローの前記所望される通信属性を満たすことが可能か否かを決定すること、
前記エンドツーエンド・データフローを提供する際に使用するために、前記所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有すると決定された前記少なくとも１つのエンドツーエンド・データパスのうちのエンドツーエンド・データパスを選択すること、および
前記所望される通信属性を満たす前記エンドツーエンド・データフローを提供するために、前記選択されたエンドツーエンド・データパスの各ネットワークノードに通信リソースを割り当てること、を備える、方法。
［Ｃ７］
前記所望される通信属性は、所望されるサービス品質（ＱｏＳ）を備える、［Ｃ６］に記載の方法。
［Ｃ８］
エンドツーエンド・データパスを前記選択することは、
前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を最小限に抑えること、
前記選択されたエンドツーエンド・データパスにおける実質的にすべてのノードに最大数の通信リソースを残すこと、および、
前記選択されたエンドツーエンド・データパスのネットワークノードの電力消費量を最小限に抑えること、
のうちの少なくとも１つに少なくとも部分的に基づいて、選択を行う、［Ｃ６］に記載の方法。
［Ｃ９］
前記通信リソースは、時分割多元接続（ＴＤＭＡ）ネットワーク通信プロトコルのタイムスロットを備える、［Ｃ８］に記載の方法。
［Ｃ１０］
エンドツーエンド・データパスを前記選択することは、前記エンドツーエンド・データフローを提供するための複数のエンドツーエンド・データパスを選択することを備える、［Ｃ６］に記載の方法。
［Ｃ１１］
エンドツーエンド・データパスを前記選択することは、
少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析して、前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を決定すること、および、前記所望されるエンドツーエンド・データフローのために使用される最小の総数の通信リソースを有するリソース割当ておよびエンドツーエンド・データパスを選択することを備える、［Ｃ６］に記載の方法。
［Ｃ１２］
エンドツーエンド・データパスを前記選択することは、
前記少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析して、前記エンドツーエンド・データフローのために使用された場合に前記少なくとも１つのエンドツーエンド・データパス内のノードに残る通信リソースの数を決定すること、および、実質的にすべてのノードに最大数のスロットを残すエンドツーエンド・データパスおよびリソース割当てを選択することを備える、［Ｃ６］に記載の方法。
［Ｃ１３］
通信リソースを前記割り当てることは、
前記エンドツーエンド・データフローの前記通信属性を満たすように前記選択されたエンドツーエンド・データパスの各中間ノードにおいて上りリンクと下りリンクとの間で通信リソースを割り当てることを備える、［Ｃ６］に記載の方法。
［Ｃ１４］
通信リソースを前記割り当てることは、
前記選択されたエンドツーエンド・データパスの中間ネットワークノードに関して、
下りネットワークノードにおいて利用可能でない、前記中間ネットワークノードおよび上りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した上りリンクに通信リソースを割り当てること、
上りの要件が前記割当てによって満たされないままである場合、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記上りリンクに通信リソースを割り当てること、
前記上りネットワークノードにおいて利用可能でない、前記中間ネットワークノードおよび前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した下りリンクに通信リソースを割り当てること、および、
下りの要件が前記割当てによって満たされないままである場合、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記下りリンクに通信リソースを割り当てること、を備える、［Ｃ６］に記載の方法。
［Ｃ１５］
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するためのシステムであって、前記システムは、
メモリとプロセッサとを有するネットワークノードを備え、前記メモリは、隣接ネットワークノードに関するリソース制約情報を格納し、前記隣接ネットワークノードは、エンドツーエンド・データパスに関する上りネットワークノードと、前記エンドツーエンド・データパスに関する下りネットワークノードとを備え、前記メモリはさらに、前記エンドツーエンド・データパスの前記上りネットワークノードおよび前記下りネットワークノードに関する前記リソース制約情報を使用して、前記ネットワークノードにおけるネットワークリソース利用可能性が、所望されるエンドツーエンド・データフローの通信要件を満たすか否かを決定するように動作可能な前記プロセッサの動作を定義するコードを格納し、前記メモリはさらに、前記通信要件を満たす前記所望されるエンドツーエンド・データフローを達成するために前記ネットワークノードにおいてリソースを割り当てるように動作可能な前記プロセッサの動作を定義するコードを格納する、システム。
［Ｃ１６］
前記割り当てられたリソースは、時分割多元接続（ＴＤＭＡ）ネットワークプロトコルのタイムスロットを備える、［Ｃ１５］に記載のシステム。
［Ｃ１７］
前記ネットワークノードは、コンピュータ、携帯情報端末（ＰＤＡ）、電話、サーバ、ルータ、ゲートウェイ、スイッチ、マルチプレクサ、モデム、無線機、アクセスポイント、および基地局からなる群から選択されるノード構成を備える、［Ｃ１５］に記載のシステム。
［Ｃ１８］
メモリとプロセッサとを有する複数のネットワークノードを備えており、前記メモリは、隣接ネットワークノードに関するリソース制約情報を格納し、前記メモリはさらに、前記リソース制約情報を使用して、対応するネットワークノードにおけるネットワークリソース利用可能性が前記所望されるエンドツーエンド・データフローの通信要件を満たすか否かを決定するように動作可能な前記プロセッサの動作を定義するコードを格納し、前記メモリはさらに、前記通信要件を満たす前記所望されるエンドツーエンド・データフローを達成するために前記対応するネットワークノードにおいてリソースを割り当てるように動作可能な前記プロセッサの動作を定義するコードを格納する、［Ｃ１５］に記載のシステム。
［Ｃ１９］
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するためのシステムであって、
前記ネットワークのノードに関するリソース制約情報を使用して、前記少なくとも１つのエンドツーエンド・データパスの各ネットワークノードにおけるリソース利用可能性が、前記エンドツーエンド・データフローの前記所望される通信属性を満たすことが可能か否かを決定するための手段と、
前記エンドツーエンド・データフローを提供する際に使用するために、前記所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有すると決定された前記少なくとも１つのエンドツーエンド・データパスのうちのエンドツーエンド・データパスを選択するための手段と、
前記所望される通信属性を満たす前記エンドツーエンド・データフローを提供するために前記選択されたエンドツーエンド・データパスの各ネットワークノードに通信リソースを割り当てるための手段と、を備える、システム。
［Ｃ２０］
前記リソース制約情報を前記ネットワークの前記ノードに伝播させるための手段をさらに備える、［Ｃ１９］に記載のシステム。
［Ｃ２１］
前記通信リソースは、時分割多元接続（ＴＤＭＡ）ネットワーク通信プロトコルのタイムスロットを備え、前記リソース制約情報は、前記ＴＤＭＡ通信プロトコルのタイムスロットの利用可能性に関する情報を備える、［Ｃ１９］に記載のシステム。
［Ｃ２２］
所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有する少なくとも１つのエンドツーエンド・データパスを使用して、ネットワークにおいて前記所望される通信属性を有するエンドツーエンド・データフローを提供するためのコンピュータプログラム製品であって、前記コンピュータプログラム製品は、
コンピュータ実行可能コードを格納するコンピュータ可読媒体を備え、前記コンピュータ実行可能コードは、
前記ネットワークのノードに関するリソース制約情報を使用して、前記少なくとも１つのエンドツーエンド・データパスの各ネットワークノードにおけるリソース利用可能性が、前記エンドツーエンド・データフローの前記所望される通信属性を満たすことが可能か否かを決定するためのコード、
前記エンドツーエンド・データフローを提供する際に使用するために、前記所望される通信属性を満たすように、その各ネットワークノードにおいてリソース利用可能性を有すると決定された前記少なくとも１つのエンドツーエンド・データパスのうちのエンドツーエンド・データパスを選択するためのコード、および、
前記所望される通信属性を満たす前記エンドツーエンド・データフローを提供するために前記選択されたエンドツーエンド・データパスの各ネットワークノードに通信リソースを割り当てるためのコード、を含む、コンピュータプログラム製品。
［Ｃ２３］
エンドツーエンド・データパスを選択するための前記コードは、前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を最小限に抑えること、前記選択されるエンドツーエンド・データパスにおける実質的にすべてのノードに最大数の通信リソースを残すこと、および、前記選択されたエンドツーエンド・データパスのネットワークノードにおける利用可能な電力、のうちの少なくとも１つに少なくとも部分的に基づいて選択を行うように動作可能である、［Ｃ２２］に記載のコンピュータプログラム製品。
［Ｃ２４］
エンドツーエンド・データパスを選択するための前記コードは、
少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析するためのコードと、
分析するための前記コードからの情報に少なくとも部分的に基づいて、前記所望されるエンドツーエンド・データフローのために使用される通信リソースの総数を決定するためのコードと、
前記所望されるエンドツーエンド・データフローのために使用される最小の総数の通信リソースを有するエンドツーエンド・データパスおよびリソース割当てを選択するためのコードと、を備える、［Ｃ２２］に記載のコンピュータプログラム製品。
［Ｃ２５］
エンドツーエンド・データパスを選択するための前記コードは、
前記少なくとも１つのエンドツーエンド・データパスに関して通信リソース割当てを分析するためのコードと、
分析するための前記コードからの情報に少なくとも部分的に基づいて、前記エンドツーエンド・データフローのために使用された場合に前記少なくとも１つのエンドツーエンド・データパス内のノードに残る通信リソースの数を決定するためのコードと、
実質的にすべてのノードに最大数のスロットを残すエンドツーエンド・データパスおよびリソース割当てを選択するためのコードと、を備える、［Ｃ２２］に記載のコンピュータプログラム製品。
［Ｃ２６］
通信リソースを割り当てるための前記コードは、
下りネットワークノードにおいて利用可能でない、中間ネットワークノードおよび上りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した上りリンクに通信リソースを割り当てるためのコードであって、上りの要件が前記上りリンクへのリソースの前記割当てによって満たされないままである場合、割り当てるための前記コードは、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記上りリンクに通信リソースを割り当てる、コードと、
前記上りネットワークノードにおいて利用可能でない、前記中間ネットワークノードおよび前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した下りリンクに通信リソースを割り当てるためのコードであって、下りの要件が前記下りリンクへのリソースの前記割当てによって満たされないままである場合、割り当てるための前記コードは、前記中間ネットワークノード、前記上りネットワークノード、および前記下りネットワークノードに利用可能な通信リソースのセットから、前記中間ネットワークノードに関連した前記下りリンクに通信リソースを割り当てる、コードと、を備える、［Ｃ２２］に記載のコンピュータプログラム製品。
【外国語明細書】
2014112852000001.pdf