(57)【要約】  様々な実施形態により、ネットワーク内における自己調節型の適応ルーティングを提供するための方法および装置がもたらされる。特に、１つまたは複数のパス選択値が、ネットワーク利用率の変更に適応可能であり、パス選択に関する第１の目標および第２の目標の影響のバランスを保つように構成されている。パス選択に関して第１および第２の目標の影響のバランスを保つことにより、従来のルーティング方法と比較すると、効率性の向上および収益生成能力の増大がもたらされ有利である。
2018517354.tif 000002
【特許請求の範囲】
【請求項１】
複数のリンクを介して相互に接続された複数のノードを通るパスを選択するための装置であって、
データ記憶装置と、
データ記憶装置に通信可能に接続されたプロセッサと
を備え、プロセッサが、
接続要求を受信し、
接続要求および第１の目標に基づいて、複数のリンクと関連付けられた第１の目標情報を更新し、
接続要求および第２の目標に基づいて、複数のリンクと関連付けられた第２の目標情報を更新し、
第１の目標情報に基づいて第１の利用率因子を決定し、
第２の目標情報に基づいて第２の利用率因子を決定し、
第１の利用率因子および第２の利用率因子に基づいて、１つまたは複数のパス選択値を決定するように構成され、
１つまたは複数のパス選択値が、第１の目標または第２の目標のどちらか一方へとパスの選択にバイアスをかけるように構成されている、装置。
【請求項２】
第１の目標がリンク利用率目標であり、第２の目標がネットワーク利用率目標である、請求項１に記載の装置。
【請求項３】
第１の目標情報の更新が、
接続要求および最小最大−パス分散アルゴリズムに基づいて、複数のリンクを通る第１の目標パスを決定し、
接続要求および最小ホップ−パス分散アルゴリズムに基づいて、複数のリンクを通る第２の目標パスを決定する
ようにプロセッサを構成することを含み、
第１の目標情報の更新が第１の目標パスにさらに基づき、
第２の目標情報の更新が第２の目標パスにさらに基づいている、請求項２に記載の装置。
【請求項４】
第１の利用率因子が、第１の目標情報と複数のリンクに関する実際のバンド幅割り当てとの間の関連にさらに基づき、
第２の利用率因子が、第２の目標情報と複数のリンクに関する実際のバンド幅割り当てとの間の関連にさらに基づく、請求項１に記載の装置。
【請求項５】
第１の利用率因子が、複数のリンクに関する実際のバンド幅割り当ての第１の最大リンク利用率、および、第１の目標情報と関連付けられた第２の最大リンク利用率にさらに基づき、
第２の利用率因子が、複数のリンクに関する実際のバンド幅割り当ての第１のネットワーク利用率、および、第２の目標情報と関連付けられた第２のネットワーク利用率にさらに基づき、
１つまたは複数のパス選択値が、第１の利用率因子と第２の利用率因子との比較に基づく第１のパス選択値を含む、請求項１に記載の装置。
【請求項６】
プロセッサが、
第２の接続要求を受信し、
１つまたは複数のパス選択値、および複数のリンクに関する実際のバンド幅割り当てに基づいてパスを選択するようにさらに構成されている、請求項１に記載の装置。
【請求項７】
パスの選択が、
ソースノードと宛先ノード間の複数の候補パスを決定し、
１つまたは複数のパス選択値、および複数の候補パスと関連付けられた複数のリンク利用率値に基づいて、候補パスに対応する複数のパスコストを決定し、
対応する最も低いパスコストを有する、複数の候補パスのうちの１つを選択するようにプロセッサを構成することを含む、請求項６に記載の装置。
【請求項８】
複数のリンクを介して相互に接続された複数のノードを通るパスを選択するための方法であって、
データ記憶装置に通信可能に接続されたプロセッサにおいて、接続要求を受信するステップと、
データ記憶装置と協働するプロセッサにより、接続要求および第１の目標に基づいて、複数のリンクと関連付けられた第１の目標情報を更新するステップと、
データ記憶装置と協働するプロセッサにより、接続要求および第２の目標に基づいて、複数のリンクと関連付けられた第２の目標情報を更新するステップと、
データ記憶装置と協働するプロセッサにより、第１の目標情報に基づいて第１の利用率因子を決定するステップと、
データ記憶装置と協働するプロセッサにより、第２の目標情報に基づいて第２の利用率因子を決定するステップと、
データ記憶装置と協働するプロセッサにより、第１の利用率因子および第２の利用率因子に基づいて１つまたは複数のパス選択値を決定するステップと
を含み、
１つまたは複数のパス選択値が、第１の目標または第２の目標のどちらか一方へとパスの選択にバイアスをかけるように構成されている、方法。
【請求項９】
接続要求が、ソースノード、宛先ノードおよびバンド幅要件を含み、複数のノードがソースノードおよび宛先ノードを含む、請求項８に記載の方法。
【請求項１０】
データ記憶装置と協働するプロセッサにより、第２の接続要求を受信するステップと、
データ記憶装置と協働するプロセッサにより、１つまたは複数のパス選択値、および複数のリンクに関する実際のバンド幅割り当てに基づいてパスを選択するステップとをさらに含む、請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、ネットワークを介してデータをルーティングするための方法および装置に関する。
【背景技術】
【０００２】
本節では、本発明をより容易に理解するのに役立つことができる諸態様について紹介する。したがって、本節の記述はこの観点から読むべきであり、何が従来技術であり、何が従来技術でないかについての承認として理解すべきではない。
【０００３】
いくつかの知られているルーティング方式において、ＩＰ／ＭＰＬＳネットワークは、Ｌａｂｅｌ  Ｓｗｉｔｃｈｅｄ  Ｐａｔｈをルーティングするために、Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ（ＯＳＰＦ）およびＩｎｔｅｒｍｅｄｉａｔｅ  Ｓｙｓｔｅｍ−ｔｏ−Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｓｙｓｔｅｍ（ＩＳ−ＩＳ）といったリンク状態のプロトコルを使用する。こうした解決策のうちの一部においては、パスは決定された最小のホップ数に基づいて選択され、こうした解決策のうちの他の解決策では、パスは決定された最小の最大リンク利用率に基づいて選択される。
【発明の概要】
【課題を解決するための手段】
【０００４】
以下の概要においていくつかの簡略化がなされているが、これは、様々な例示の実施形態のうちのいくつかの態様を強調し紹介しようとするものであって、こうした簡略化が本発明の範囲を限定しようとするものではない。当業者らが、本発明の概念を実施し利用することができるようにするのに十分な、好ましい例示的な実施形態の詳細な説明は、後の諸節に記載している。
【０００５】
様々な実施形態により、ネットワーク内における自己調節型の適応ルーティングのための方法および装置が提供される。特に、１つまたは複数のパス選択値が、ネットワーク利用率の変更に適応可能であり、パス選択に関する第１の目標および第２の目標の影響のバランスを保つように構成されている。パス選択に関して、第１および第２の目標の影響のバランスを保つことにより、従来のルーティング方法と比較すると、効率性の向上および収益生成能力の増大がもたらされ有利である。
【０００６】
第１の実施形態において、複数のリンクを介して相互に接続された複数のノードを通るパスを選択するための装置が提供される。この装置は、データ記憶装置、およびこのデータ記憶装置に通信可能に接続されたプロセッサを備える。プロセッサは、接続要求を受信し、接続要求および第１の目標に基づいて複数のリンクと関連付けられた第１の目標情報を更新し、接続要求および第２の目標に基づいて複数のリンクと関連付けられた第２の目標情報を更新し、第１の目標情報に基づいて第１の利用率因子を決定し、第２の目標情報に基づいて第２の利用率因子を決定し、第１の利用率因子および第２の利用率因子に基づいて１つまたは複数のパス選択値を決定するようにプログラムされている。ここで、１つまたは複数のパス選択値は、第１の目標または第２の目標のどちらか一方へとパスの選択にバイアスをかけるように構成されている。
【０００７】
第２の実施形態において、複数のリンクを介して相互に接続された複数のノードを通るパスを選択するための方法が提供される。この方法は、接続要求を受信するステップと、接続要求および第１の目標に基づいて複数のリンクと関連付けられた第１の目標情報を更新するステップと、接続要求および第２の目標に基づいて複数のリンクと関連付けられた第２の目標情報を更新するステップと、第１の目標情報に基づいて第１の利用率因子を決定するステップと、第２の目標情報に基づいて第２の利用率因子を決定するステップと、第１の利用率因子および第２の利用率因子に基づいて１つまたは複数のパス選択値を決定するステップとを含む。ここで、１つまたは複数のパス選択値は、第１の目標または第２の目標のどちらか一方へとパスの選択にバイアスをかけるように構成されている。
【０００８】
第３の実施形態において、複数のリンクを介して相互に接続された複数のノードを通るパスを選択するための非一時的なコンピュータ可読記憶媒体が提供される。この記憶媒体は、コンピュータによって実行されると、コンピュータに、接続要求を受信するステップと、接続要求および第１の目標に基づいて複数のリンクと関連付けられた第１の目標情報を更新するステップと、接続要求および第２の目標に基づいて複数のリンクと関連付けられた第２の目標情報を更新するステップと、第１の目標情報に基づいて第１の利用率因子を決定するステップと、第２の目標情報に基づいて第２の利用率因子を決定するステップと、第１の利用率因子および第２の利用率因子に基づいて１つまたは複数のパス選択値を決定するステップとを含む方法を実行させる命令を備える。ここで、１つまたは複数のパス選択値は、第１の目標または第２の目標のどちらか一方へとパスの選択にバイアスをかけるように構成されている。
【０００９】
上記の実施形態のいくつかにおいて、接続要求は、ソースノード、宛先ノード、およびバンド幅要件を含み、複数のノードはソースノードおよび宛先ノードを含む。
【００１０】
上記の実施形態のいくつかにおいて、第１の目標はリンク利用率目標であり、第２の目標はネットワーク利用率目標である。
【００１１】
上記の実施形態のいくつかにおいて、第１の目標情報を更新する場合、実施形態は、接続要求および最小最大−パス分散アルゴリズムに基づいて、複数のリンクを通る第１の目標パスを決定することをさらに含む。ここで、第１の目標情報の更新は、第１の目標パスにさらに基づく。
【００１２】
上記の実施形態のいくつかにおいて、第２の目標情報を更新する場合、実施形態は、接続要求および最小ホップ−パス分散アルゴリズムに基づいて、複数のリンクを通る第２の目標パスを決定することをさらに含む。ここで、第２の目標情報の更新は、第２の目標パスにさらに基づく。
【００１３】
上記の実施形態のいくつかにおいて、第１の利用率因子は、第１の目標情報と複数のリンクに関する実際のバンド幅割り当てとの間の関連にさらに基づき、第２の利用率因子は、第２の目標情報と複数のリンクに関する実際のバンド幅割り当てとの間の関連にさらに基づく。
【００１４】
上記の実施形態のいくつかにおいて、第１の利用率因子は、複数のリンクに関する実際のバンド幅割り当ての第１の最大リンク利用率、および、第１の目標情報と関連付けられた第２の最大リンク利用率にさらに基づき、第２の利用率因子は、複数のリンクに関する実際のバンド幅割り当ての第１のネットワーク利用率、および、第２の目標情報と関連付けられた第２のネットワーク利用率にさらに基づく。
【００１５】
上記の実施形態のいくつかにおいて、１つまたは複数のパス選択値は、第１の利用率因子と第２の利用率因子の比較に基づく第１のパス選択値を含む。
【００１６】
上記の実施形態のいくつかにおいて、実施形態は、第２の接続要求を受信すること、ならびに、１つまたは複数のパス選択値および複数のリンクに関する実際のバンド幅割り当てに基づいてパスを選択することをさらに含む。
【００１７】
上記の実施形態のいくつかにおいて、実施形態は、パスを選択する場合、ソースノードと宛先ノード間の複数の候補パスを決定すること、１つまたは複数のパス選択値、および複数の候補パスと関連付けられた複数のリンク利用率値に基づいて、候補パスに対応する複数のパスコストを決定すること、ならびに、最も低い対応するパスコストを有する、複数の候補パスのうちの１つのパスを選択することをさらに含む。
【００１８】
様々な実施形態が添付の図面に示されている。
【図面の簡単な説明】
【００１９】
【図１】自己調節型の適応ルーティングのためのシステム１００の一実施形態を含むネットワークを示す図である。
【図２】ネットワーク利用率を最大にすることが目標の、ノード（たとえば、図１のノード１５０）のネットワークおよびリンク（たとえば、図１のリンク１６０）にわたるパス選択を示す図である。
【図３】第１および第２の目標に基づきリンク（たとえば、図１のリンク１６０または図２のリンク２６０）によって相互に接続されたノード（たとえば、図１のノード１５０または図２のノード２５０）のネットワークにわたるパスを選択することと関連付けられた１つまたは複数のパス選択値を決定するための装置（たとえば、図１のＰＣＥ１３０）のための方法３００の一実施形態を示す流れ図である。
【図４】自己調節型の適応ルーティングを使用してパスを選択するための装置またはシステム（たとえば、図１のＰＣＥ１３０または図１のＰＣＥ１３０およびノード１５０のうちの１つまたは複数のノード）のための方法４００の一実施形態を示す流れ図である。
【図５】本明細書に記載の自己調節型の適応ルーティングシステムの一実施形態を、従来の条件付きショーテストパスファーストソリューションと比較した、６ノードトポロジーの例示的な結果を示す図である。
【図６】本明細書に記載の自己調節型の適応ルーティングシステムの一実施形態を、従来の条件付きショーテストパスファーストソリューションと比較した、５９ノードトポロジーの例示的な結果を示す図である。
【図７】図１のＰＣＥ１３０の１つまたはノード１５０の１つなど装置７００の一実施形態を概略的に示す図である。
【発明を実施するための形態】
【００２０】
理解を容易にするために、同一の参照番号が、実質的に同一もしくは類似の構造、または実質的に同一もしくは類似の機能を有する要素を指し示すために使用されている。
【００２１】
説明および図面は、本発明の原理を示しているにすぎない。したがって、本明細書では明示的に記載または示されていないが、当業者であれば、本発明の原理を具現化し、本発明の範囲内に含まれる様々な構成を考案することができるであろうことは理解されよう。さらに、本明細書で列挙されたすべての例は、主として、発明者らにより技術を増進させるためにもたらされた本発明の原理および概念を、読者が理解する助けとなるもっぱら教育的な目的で特に意図されたものであり、このすべての例は、制限なくこうした特に列挙された例および条件であると解釈すべきである。さらに、本明細書で使用する「または」という用語は、別段の指示（たとえば、「ｏｒ  ｅｌｓｅ  そうでなければ」または「ｏｒ  ｉｎ  ｔｈｅ  ａｌｔｅｒｎａｔｉｖｅ  または代替として」）がない限り、非排他的または、を指している。また、本明細書に記載の様々な実施形態は、いくつかの実施形態が１つまたは複数の他の実施形態と結合して新しい実施形態を形成することができるなど、必ずしも相互に排他的ではない。
【００２２】
様々な実施形態により、ネットワーク内における自己調節型の適応ルーティングを提供するための方法および装置が提供される。特に、１つまたは複数のパス選択値が、ネットワーク利用率の変更に適応可能であり、パス選択に関する第１の目標および第２の目標の影響のバランスを保つように構成されている。パス選択に関して、第１および第２の目標の影響のバランスを保つことにより、従来のルーティング方法と比較すると、効率性の向上および収益生成能力の増大がもたらされ、またサービスプロバイダは、インストールしたネットワーク容量を用いてより多くのサービス要求に対応できることにより、既存のネットワークでより多くの収益を上げ、かつ、リンクが輻輳する状態を緩和することによりサービス品質を向上させることができ有利である。
【００２３】
図１は、自己調節型の適応ルーティングのためのシステム１００の一実施形態を含むネットワークを示す。システム１００は、通信パスを介して２つのクライアント１２０−１、１２０−２（総称してクライアント１２０）の間をルーティングされるデータを含む。通信パスは、クライアント通信チャネル１２５−１および１２５−２（総称してクライアント通信チャネル１２５）、ならびに、１つまたは複数のリンク１６０−１から１６０−９（総称してリンク１６０）によって通信可能に接続された２つ以上のノード１５０−１から１５０−８（総称してノード１５０）を含むネットワーク１４０を備える。パス計算エンジン（ＰＣＥ）１３０は、接続要求を受信し（たとえば、クライアント１２０のうちの１つ、ノード１５０のうちの１つ、または説明を明瞭にするために図示しないが接続承認装置から）、ノードのネットワーク内（たとえば、２つ以上のノード１５０およびリンク１６０のうちの適切なリンク）でルーティングパス（たとえば、１つのクライアント１２０と別のクライアント１２０の間、または１つのノード１５０と別のノード１５０の間）を決定するためにルーティング情報を決定し、ルーティング情報をノード１５０のうちの適切なノードに伝える。ＰＣＥ１３０は、ＰＣＥ通信チャネル１３５を介してクライアント１２０またはノード１５０と通信を行う。
【００２４】
クライアント１２０は、１つまたは複数のクライアント通信チャネル１２５を介して、ネットワーク１４０上で情報を送受信することができる任意のタイプの通信デバイスを備えることができる。たとえば、通信デバイスは、シンクライアント、スマートフォン（たとえば、クライアント１２０−ｎ）、パーソナルまたはラップトップコンピュータ（たとえば、クライアント１２０−１）、サーバ、ネットワークデバイス、タブレット、テレビジョンセットトップボックス、メディアプレイヤなどとすることができる。通信デバイスは、例示のシステム内の他のリソースに依存して、処理または格納といったタスクの一部を実行し、または独立してタスクを実行することができる。２つのクライアントがここでは示されているが、システム１００は、より多くのクライアントを備えることができることを理解すべきである。さらに、任意の一時におけるクライアントの数は、クライアントが、動作中の様々な時刻にシステムに追加しまたは取り去ることができるために絶えず変化する。
【００２５】
通信チャネル１２５および１３５は、無線通信（たとえば、ＬＴＥ、ＧＳＭ（登録商標）、ＣＤＭＡ、ブルートゥース（登録商標））、無線ＬＡＮ通信（たとえば、ＷｉＦｉ）、パケットネットワーク通信（たとえば、ＩＰ）、ブロードバンド通信（たとえば、ＤＯＣＳＩＳおよびＤＳＬ）、ストレージ通信（たとえば、ファイバーチャネル、ｉＳＣＳＩ）、直接通信（たとえば、ＰＣＥ１３０およびノード１５０のうちの１つが同一の装置内にあるとき）など、１つまたは複数の通信チャネル上の通信をサポートする。単一の接続として描かれているが、通信チャネル１２５および１３５は、任意の数の通信チャネルまたは通信チャネルの組合せとすることができることを理解すべきである。
【００２６】
ＰＣＥ１３０は、接続要求を受信し（たとえば、クライアント１２０のうちの１つ、ノード１５０のうちの１つ、または説明を明瞭にするために図示しないが接続承認装置から）、ノードのネットワーク内（たとえば、２つ以上のノード１５０）でルーティングパス（たとえば、１つのクライアント１２０と別のクライアント１２０の間、または１つのノード１５０と別のノード１５０の間）を決定するためにルーティング情報を決定し、ルーティング情報をノード１５０のうちの適切なノードに伝えることができる任意の装置とすることができる。特に、ＰＣＥ１３０は、２つの目標に関連した情報を維持してネットワーク容量利用率を最適化し、目標情報に基づいて１つまたは複数のパス選択値を決定する。パス選択値は、パス選択を決定する際に使用されるように構成されている。目標は、（ｉ）効率を最適化すること（すなわち、たとえば、全体としてのネットワークバンド幅を最小化しようと試みること、または、平均的なリンク利用率もしくはネットワーク利用率を最小化しようと試みることによるなど、リソース使用を最小化しようと試みること）、（ｉｉ）利用率バランスをもたらすこと（すなわち、最大リンク利用率を最小化しようと試みることによって輻輳状態を回避するために任意のリンクの過負荷を避けようと試みること）、または（ｉｉｉ）同様なこと、といった任意の適切な目標とすることができる。目標情報は、たとえば、リンク割り当ておよび容量、ネットワーク割り当てマップなど関連する情報の表を維持するといった目標と関連付けられた任意の適切な情報とすることができる。いくつかの実施形態において、ＰＣＥ１３０は、リンク利用率目標とネットワーク利用率目標とのバランスを保つように構成されている。このバランスを取ることにより、輻輳したリンクを回避し、ネットワークのバンド幅消費を削減できるため有利である。
【００２７】
ネットワーク１４０は、任意の数のアクセスおよびエッジノード１５０、ネットワークデバイス（説明を明瞭にするために図示せず）、ならびに任意の数および構成のリンク１６０を備えている。さらに、ネットワーク１４０は、ＬＴＥ、ＧＳＭ、ＣＤＭＡ、ローカルエリアネットワーク（ＬＡＮ）、無線ローカルエリアネットワーク（ＷＬＡＮ）、広域ネットワーク（ＷＡＮ）、都市圏ネットワーク（ＭＡＮ）などの無線または有線ネットワークの任意の組合せおよび任意の数を含むことができることを理解すべきである。ノード１５０は、ＰＣＥ１３０と通信し、たとえば、ルータ、スイッチ、ゲートウエイ、モバイルパケットスイッチ（たとえば、パケット交換ＥＰＣ）などデータをルーティングできる任意のデバイスとすることができる。
【００２８】
ネットワーク１４０および適切な通信チャネルを介して、ＰＣＥ１３０とノード１５０のうちのノードとの間で通信するように示されているが、ＰＣＥ１３０は、任意の適切な通信ネットワークを経由してノード１５０のうちのノードと通信し、または同一の通信ネットワーク、もしくは１つまたは複数のノード１５０と同じ装置に存在することができることを理解すべきである。
【００２９】
いくつかの実施形態において、システム１００はソフトウェア定義ネットワーク（ＳＤＮ）である。いくつかの実施形態において、システム１００はＩＰ／ＭＰＬＳネットワークである。
【００３０】
図２は、ノード（たとえば、図１のノード１５０）およびリンク（たとえば、図１のリンク１６０）のネットワークにわたるパス選択を示している。ここではネットワーク利用率を最大化することが目標である。ネットワーク利用率を最大化することは、投資に対するリターンに直接関係し、サービスプロバイダの全体的な収益性に有利である。ネットワーク容量は、クライアント（たとえば、図１のクライアント１２０）によってなされたサービス要求に対して割り当てられた、有限のリソースであることを理解すべきである。各サービス要求は特定の量および値の項目を表すので、ネットワークが埋まるにつれて、後続のサービス要求を満たすことが次第に困難になる。本明細書に記載したように、ＰＣＥ（たとえば、図１のＰＣＥ１３０）は、リンク利用率などバランス目標、およびネットワーク利用率など効率性目標のバランスを取るように構成されている。
【００３１】
図２を参照すると、表１は所与のトポロジーおよびリンク利用率に対する、バランス目標と効率性目標のトレードオフの一例を示す。図２において、パスＰ１、Ｐ２、およびＰ３は、いくつかのノードおよびリンク２６０−１から２６０−９（総称してリンク２６０）を含むネットワークにおいて、ソースノード２５０−Ｓと宛先ノード２５０−Ｄの間でデータをルーティングするために選択することができる、３つの異なる可能性のあるパスを表す。値は、ノードを繋ぐリンクのリンク利用率を表す。たとえば、ノード２５０−Ｓと２５０−１の間のリンク利用率は０．３すなわち３０％である。図示されたノードはまとめてノード２５０とする。説明を明瞭にするために、個々のノードすべてに名前を付けているわけではないことを理解すべきである。
【表１】
2018517354.tif 000003
【００３２】
リンク利用率を最小化するアルゴリズムは、効率性に優先してバランスを選択することがあり、したがってパスが６つのホップを必要とするときでさえ、データをルーティングするためにパスＰ３を選択することがあることを理解すべきである。一方、ホップを最小化するアルゴリズム（たとえば、ＯＳＰＦおよびＩＳ−ＩＳネットワークにおける条件付きショーテストパスファースト（ＣＳＰＦ）ルーティングプロトコル）は、バランスに優先して効率性を選択することがあり、したがってリンク２６０−２のよりひどい輻輳（すなわち、６０パーセント）が、後続の要求に対してラインを締め出すリスクを生成することがあるとしても、パスＰ１を選択することがある。より長いルート（すなわち、より多くのホップ）はまた、ネットワーク利用率およびＲＯＩに否定的な影響を与えることがあることをさらに理解すべきである。
【００３３】
図３は、第１および第２の目標に基づきリンク（たとえば、図１のリンク１６０または図２のリンク２６０）によって相互に接続されたノード（たとえば、図１のノード１５０または図２のノード２５０）のネットワークにわたるパスを選択することと関連付けられた１つまたは複数のパス選択値を決定するための装置（たとえば、図１のＰＣＥ１３０）のための方法３００の一実施形態を示す流れ図を表す。この方法は、ステップ３０５で開始し、接続要求（図１のクライアント１２０のうちの１つ、または図１のノード１５０のうちの１つ、または図２のノード２５０から）を受信すること（ステップ３２０）、第１の目標および接続要求に基づいて第１の目標情報を更新すること（ステップ３３０）、第２の目標および接続要求に基づいて第２の目標情報を更新すること（ステップ３４０）、第１の目標情報に基づいて第１の利用率因子を決定すること（ステップ３５０）、第２の目標情報に基づいて第２の利用率因子を決定すること（ステップ３６０）、第１の利用率因子および第２の利用率因子に基づいて１つまたは複数のパス選択値を決定すること（ステップ３８０）、およびステップ２９５において終了することを含む。
【００３４】
方法３００において、ステップ３２０は接続要求（たとえば、図１のクライアント１２０のうちの１つ、または図１のノード１５０のうちの１つ、または図２のノード２５０から）を受信することを含む。特に、接続要求は、要求に関連したソースノード、宛先ノード、およびバンド幅といった情報を含む。たとえば、図２を参照すると、要求は、ノード２５０−Ｓ、ノード２５０−Ｄ、および１０ｍｂｓのバンド幅を識別することができる。接続要求は、たとえば、要求クライアントからの接続要求で、別の装置（たとえば、接続承認制御を実施する装置）からのメッセージで、または局所で（たとえば、ＰＣＥがノードまたは接続承認制御装置と同一の装置内にあるとき）など、任意の適切な方法で受信することができることを理解すべきである。
【００３５】
方法３００において、ステップ３３０は、第１の目標および接続要求に基づいて第１の目標情報を更新することを含む。特に、第１の目標情報は、第１の目標に基づく割り当てを使用して、ノードのネットワーク内のリンク（たとえば、図２のリンク２６０）のために確保されたであろうバンド幅のコピーである。
【００３６】
方法３００において、ステップ３４０は、第２の目標および接続要求に基づいて第２の目標情報を更新することを含む。特に、第２の目標情報は、第２の目標に基づく割り当てを使用して、ノードのネットワーク内のリンク（たとえば、図２のリンク２６０）のために確保されたであろうバンド幅のコピーである。
【００３７】
方法３００において、ステップ３５０は、第１の目標情報に基づいて第１の利用率因子を決定することを含む。特に、第１の利用率因子は、第１の目標に基づいて割り当てられると、ノードのネットワーク内のリンクの利用率を特徴付ける。
【００３８】
方法３００において、ステップ３６０は、第２の目標情報に基づいて第２の利用率因子を決定することを含む。特に、第２の利用率因子は、第２の目標に基づいて割り当てられると、ノードのネットワーク内のリンクの利用率を特徴付ける。
【００３９】
方法３００において、ステップ３８０は、第１の利用率因子および第２の利用率因子に基づいて１つまたは複数のパス選択値を決定することを含む。特に、１つまたは複数のパス選択値は、変化するネットワーク利用率に適応可能であり、パス選択に関する第１および第２の目標の影響のバランスを保つように構成されている。パス選択に関する第１および第２の目標の影響のバランスを保つことにより、ネットワーク内において自己調節型の適応ルーティングが得られることを理解すべきである。
【００４０】
ステップ３３０および３４０のいくつかの実施形態において、第１の目標はリンク利用率目標であり、第２の目標はネットワーク利用率目標である。
【００４１】
ステップ３３０のいくつかの実施形態において、第１の目標情報は、リンク利用率のバランスを保つこと（たとえば、最小最大−パス分散アルゴリズム）に基づく割り当てを使用して、ノードのネットワーク内のリンク（たとえば、図２のリンク２６０）のために確保されたバンド幅のコピーである。たとえば、新しいパスが、ノードのネットワーク内のリンクの最大リンク利用率を最小化するという目標に基づいて、後続の接続要求のために選択され、第１の目標情報が新しいパスにより更新される。
【００４２】
ステップ３４０のいくつかの実施形態において、第２の目標情報は、ネットワーク利用率（たとえば、最小ホップ分散アルゴリズム）に基づく割り当てを使用して、ノードのネットワーク内のリンク（たとえば、図２のリンク２６０）のために確保されたバンド幅のコピーである。たとえば、新しいパスが、接続要求を満足させるパスのホップ数を最小化するという目標に基づいて、後続の接続要求のために選択され、第２の目標情報が新しいパスにより更新される。
【００４３】
たとえば、図２および表２を参照すると、表はある時点における例示のシステムを記載している。例を進めると、１０ｍｂｓを必要とするソースノード２５０−Ｓと宛先ノード２５０−Ｄの間の接続を確立する要求が受信されたと仮定する（たとえば、ステップ３２０において）。
【００４４】
第１の目標情報は、最小最大−パス分散アルゴリズムを使用してパスを選択することに基づいて更新される。表において第１の目標情報（たとえば、ｆ（ｌ）（ｏｂｊ．１））を参照すると、０．４５のリンク利用率を有するリンク２６０−２上にあるパスＰ１上の最も高いリンク利用率、および、０．４５のリンク利用率を有するリンク２６０−９上にあるパスＰ２上の最も高いリンク利用率と比較して、パスＰ３上の最も高いリンク利用率は、０．４０のリンク２６０−５である）。Ｐ３は最も低い最大リンク利用率を有するので、第１の目標情報（たとえば、ｆ（ｌ）（ｏｂｊ．１））におけるパスＰ３のリンクは、受信された接続要求により更新される。たとえば、ｆ（ｌｉｎｋ２６０−３）（ｏｂｊ．１）は、２５０ＭＢＳから２６０ＭＢＳへ更新される。ｆ（ｌｉｎｋ２６０−４）（ｏｂｊ．１）は、３７５ＭＢＳから３８５ＭＢＳへ更新される。ｆ（ｌｉｎｋ２６０−５）（ｏｂｊ．１）は、２００ＭＢＳから２１０ＭＢＳへ更新される。ｆ（ｌｉｎｋ２６０−６）（ｏｂｊ．１）は、１５０ＭＢＳから１６０ＭＢＳへ更新される。ｆ（ｌｉｎｋ２６０−７）（ｏｂｊ．１）は、３７５ＭＢＳから３８５ＭＢＳへ更新される。ｆ（ｌｉｎｋ２６０−８）（ｏｂｊ．１）は、３７５ＭＢＳから３８５ＭＢＳへ更新される。
【００４５】
同様に、第２の目標情報は、最小ホップ−パス分散アルゴリズムを使用してパスを選択することに基づいて更新される。表１を参照すると、パスＰ２は５つのホップ、パスＰ３は６つのホップを有する一方、パスＰ１は３つのホップしか有しないのでパスＰ１が選択される。Ｐ１は最も少ないホップ数を有するので、第２の目標情報（たとえば、ｆ（ｌ）（ｏｂｊ．２））におけるパスＰ１のリンクは、受信された接続要求により更新される。たとえば、ｆ（ｌｉｎｋ２６０−１ｏｂｊ．２は、２７５ＭＢＳから２８５ＭＢＳへ更新される。ｆ（ｌｉｎｋ２６０−２ｏｂｊ．２は、３７５ＭＢＳから３８５ＭＢＳへ更新される。ｆ（ｌｉｎｋ２６０−３）（ｏｂｊ．２）は、２００ＭＢＳから２１０ＭＢＳへ更新される。
【表２】
2018517354.tif 000004
ここで：
−  Ｌｉｎｋは、図２のネットワーク内のリンクのリストである。
−  ∈ｐａｔｈは、図２のパスＰ１、Ｐ２またはＰ３における各リンクの構成メンバである。
−  ｆ（ｌ）（ａｃｔｕａｌ）は、図２に示すトラフィックの実際のネットワーク割り当てである。
−  ｆ（ｌ）（ｏｂｊ．１）は、リンク最適化目標（たとえば、最小最大−パス分散アルゴリズム）に基づいて、ネットワーク割り当てが接続をルーティングされたことを表す第１の目標情報のコピーである。
−  ｆ（ｌ）（ｏｂｊ．２）は、ネットワーク最適化目標（たとえば、最小ホップ−パス分散アルゴリズム）に基づいて、ネットワーク割り当てが接続をルーティングされたことを表す第２の目標情報のコピーである。
−  ｕ（ｌ）はリンク「ｌ」の容量である。
【００４６】
ステップ３５０および３６０のいくつかの実施形態において、第１の利用率因子は、第１の目標情報とトラフィックの実際のネットワーク割り当ての関連に基づき、第２の利用率因子は、第２の目標情報とトラフィックの実際のネットワーク割り当ての関連に基づいている。こうした実施形態のいくつかにおいて、第１の利用率因子は、実際のネットワーク割り当てが第１の目標情報によって表される第１の目標にいかに近いかに基づき、第２の利用率因子は、実際のネットワーク割り当てが第２の目標情報によって表される第２の目標にいかに近いかに基づいている。
【００４７】
第１の目標がリンク利用率目標であるステップ３５０のいくつかの実施形態において、第１の利用率因子は、ノードのネットワークにおけるリンクの最大リンク利用率値に基づく。こうした実施形態のいくつかにおいて、第１の利用率因子は、実際のネットワーク割り当てにおけるリンクの最大リンク利用率値、および、第１の目標情報におけるリンクの最大リンク利用率値に基づく。こうした実施形態のいくつかにおいて、第１の利用率因子は方程式［式１］に基づく。
【００４８】
［式１］  第１の利用率因子  ＝  ｍａｘ（ｕｔｉｌｉｚａｔｉｏｎ（ｌ）（ａｃｔｕａｌ））／ｍａｘ（ｕｔｉｌｉｚａｔｉｏｎ（ｌ）（ｏｂｊ．１））；∀ｌｉｎｋｓ  ｌ
ここで：
−  ｕｔｉｌｉｚａｔｉｏｎ（ｌ）（ａｃｔｕａｌ）は、トラフィックの実際のネットワーク割り当てにおけるリンク「ｌ」の実際のバンド幅利用率である。
−  ｕｔｉｌｉｚａｔｉｏｎ（ｌ）（ｏｂｊ．１）は、第１の目標情報におけるリンク「ｌ」のバンド幅利用率である。
−  ∀ｌｉｎｋｓ  ｌは、ノードのネットワークにおけるすべてのリンク「ｌ」に対して。
【００４９】
たとえば、表２を参照すると、第１の利用率因子は、０．６／０．４５＝１．３３である。その理由は、実際のネットワーク割り当てにおける最大リンク利用率は０．６（たとえば、リンク２６０−２は０．６のリンク利用率値を有する）であり、第１の目標情報における最大リンク利用率は０．４５（たとえば、リンク２６０−２および２６０−９は０．４５のリンク利用率値を有する）であるからである。第１の利用率因子は、第１の目標情報が更新される前に、または更新された後に、第１の目標情報の最大リンク利用率に基づくことができることを理解すべきである。
【００５０】
第２の目標がネットワーク利用率目標であるステップ３６０のいくつかの実施形態において、第２の利用率因子は、ノードのネットワークにおけるリンクのネットワーク利用率に基づく。こうした実施形態のいくつかにおいて、第２の利用率因子は、実際のネットワーク割り当てにおけるリンクのネットワーク利用率、および、第２の目標情報におけるリンクのネットワーク利用率に基づく。こうした実施形態のいくつかにおいて、第２の利用率因子は方程式［式２］に基づく。
［式２］
【数１】
2018517354.tif 000005
ここで：
−  ｆ（ｌ）（ａｃｔｕａｌ）は、トラフィックの実際のネットワーク割り当てにおいて、リンク「ｌ」に割り当てられた実際のバンド幅である。
−  ｕ（ｌ）はリンク「ｌ」の容量である。
−  ｕｔｉｌｉｚａｔｉｏｎ（ｌ）（ｏｂｊ．１）は、第１の目標情報におけるリンク「ｌ」のバンド幅利用率である。
−  ∀ｌｉｎｋｓ  ｌは、ノードのネットワークにおけるすべてのリンク「ｌ」に対して。
【００５１】
たとえば、表２を参照すると、第２の利用率因子は、０．３１５／０．２８１＝１．１２である。その理由は、実際のネットワーク割り当てにおけるネットワーク利用率は０．３１５（たとえば、６５００ＭＢＳの容量のうち２０５０ＭＢＳが割り当てられた）であり、第２の目標情報のネットワーク利用率は０．２８１（たとえば、６５００ＭＢＳの容量のうち１８２５ＭＢＳが割り当てられた）であるからである。第２の利用率因子は、第２の目標情報が更新される前に、または更新された後に、第２の目標情報のネットワーク利用率に基づくことができることを理解すべきである。
【００５２】
ステップ３８０のいくつかの実施形態において、第１のパス選択値（すなわち、α）は、第１の利用率因子および第２の利用率因子に基づく。こうした実施形態のいくつかにおいて、αは、対応する第１および第２の目標情報によって表される第１または第２の目標に対して、実際のネットワーク割り当てがどの程度近いかに基づいて適応可能なように調節される。こうした実施形態のいくつかにおいて、第１のパス選択値は方程式［式３］および［式４］に基づく。第１のパス選択値αは、パス選択アルゴリズムに基づき、適切な選択目標（たとえば、第１または第２の目標）に向けてパス選択アルゴリズムにバイアスをかけるように構成されていることを理解すべきである。
【００５３】
［式３］  ｉｆ（第１の利用率因子＋ｔｈｒｅｓｈｏｌｄ）＜第２の利用率因子；α＝α／Ｍ
［式４］  ｉｆ（第２の利用率因子＋ｔｈｒｅｓｈｏｌｄ）＜第１の利用率因子；α＝α＊Ｍ
ここで：
−  αは、第１の目標と第２の目標の間のバランスを表すパス選択値である。
−  ｔｈｒｅｓｈｏｌｄは、第１および第２の利用率因子がしきい値内にあるとき、αが変更されない任意選択のしきい値である。
−  Ｍは、αの変更を制御するためのパラメータである。任意の適切な値を使用することができる。たとえば、１．２の値は適切であると決定された。
【００５４】
方法３００のいくつかの実施形態において、１つまたは複数の第１の目標情報、第２の目標情報、第１の利用率因子、第２の利用率因子または１つもしくは複数のパス選択値は、管理的なリンクメトリクスまたは明確なルート制限にさらに基づく。たとえば、接続要求を５つ以下のホープに制限するメトリクスは、図２のパスＰ３を選択しないであろう。こうした実施形態のいくつかにおいて、メトリクスはデータのタイプに基づくことができる（たとえば、音声もしくはビデオなどリアルタイムデータまたは待ち時間に影響を受け易いデータは異なる扱いを受けることができる）。
【００５５】
図４は、自己調節型の適応ルーティングを使用してパスを選択するための装置またはシステム（たとえば、図１のＰＣＥ１３０、または、図１のＰＣＥ１３０およびノード１５０のうちの１つまたは複数のノード）のための方法４００の一実施形態を示す流れ図を表す。この方法は、ステップ４０５で開始し、接続要求を受信すること（ステップ４１０）、１つまたは複数のパス選択値を決定すること（ステップ４２０）、１つまたは複数のパス選択値を任意選択で配布すること（ステップ４４０）、１つまたは複数のパス選択値、およびリンク上のトラフィックの実際のネットワーク割り当て（たとえば、バンド幅）に基づいて、パスを選択すること（ステップ４６０）、パス選択に基づいてネットワーク利用率を更新すること（ステップ４８０）、およびステップ４９５で終了することを含む。
【００５６】
方法４００において、ステップ４１０は、本明細書で記載したように、特に図３のステップ３２０に示したように接続要求を受信すること（たとえば、図１のＰＣＥ１３０によって）を含む。
【００５７】
方法４００において、ステップ４２０は、本明細書で記載したように、特に図３のステップ３３０、３４０、３５０、３６０および３８０に示したように、１つまたは複数のパスセクション値を決定すること（たとえば、図１のＰＣＥ１３０によって）を含む。
【００５８】
方法４００は、ステップ４４０を任意選択で含む。ステップ４４０は、１つまたは複数のパス選択値を配布すること（たとえば、図１のＰＣＥ１３０によって）を含む。特に、ステップ４６０におけるパス選択が、ステップ４２０において１つまたは複数のパス選択値を決定した同一の装置によって実施されていない（たとえば、ＰＣＥ１３０の代わりに１つまたは複数のノード１５０によって）実施形態においては、１つまたは複数のパス選択値を決定した装置は、必要に応じて、パス選択値を配布する。配布は、たとえば、値を有するメッセージを送信する、または、ステップ４６０でパスを選択した装置によってアクセス可能な中央位置に、１つまたは複数のパス選択値を格納するといった、任意の適切な方法によって行うことができる。
【００５９】
方法４００において、ステップ４６０は、１つまたは複数のパス選択値、および、リンク上のトラフィックの実際のネットワーク割り当て（たとえば、バンド幅）に基づいて、パスを選択することを含む。いくつかの実施形態において、パス選択は、リンク利用率および１つまたは複数のパス選択値に基づくリンクコストを推定することに基づいている。これらの実施形態のいくつかにおいて、選択されたパスは、最も低い合計リンクコストを有するパスである。これらの実施形態のいくつかにおいて、パス選択は方程式［式５］、［式６］および［式７］に基づく。第１の目標がリンク利用率、第２の目標がネットワーク利用率であり、第１の目標情報が最小−最大アルゴリズムに基づいて更新され、第２の目標情報が最小−ホップアルゴリズムに基づいて更新される実施形態において、αが０に近づくにつれて［式５］は最小−ホップアルゴリズムと類似した働きをし、αが∞に近づくにつれて［式５］は最小−最大アルゴリズムと類似した働きを行うことに注意されたい。このように、適応的に自己調節を行うパス選択値αは、第１の目標と第２の目標間でパス選択のバランスを保つという目標を達成する。
【００６０】
［式５］
【数２】
2018517354.tif 000006
［式６］  ｃ（ｐ）＝Σｃ（ｌ）；∀ｌ  ∈ｐａｔｈ（ｐ）
［式７］  選択されたパス＝ｍｉｎ（ｃ（ｐ））；∀  ｐａｔｈｓ  ｐ
ここで：
−  ｃ（ｌ）は、リンク「ｌ」に関する要求をルーティングするコストである。
−  αは、第１の目標と第２の目標間のバランスを表すパス選択値である。
−  ｆ（ｌ）（ａｃｔｕａｌ）は、トラフィックの実際のネットワーク割り当てにおいてリンク「ｌ」に割り当てられた実際のバンド幅である。
−  ｕ（ｌ）は、リンク「ｌ」の容量である。
−  ｃ（ｐ）は、パス「ｐ」に関する要求をルーティングするコストである。
【００６１】
方法４００において、ステップ４８０は、パス選択に基づいてネットワーク利用率を更新する。たとえば、トラフィックの実際のネットワーク割り当ては、選択されたパスに基づいて更新される。図２および表２を参照すると、パスＰ２が選択されると、パスＰ２のためのｆ（ｌ）（ａｃｔｕａｌ）の値は、受信された接続要求によって更新される。たとえば、ｆ（ｌｉｎｋ２６０−３）（ａｃｔｕａｌ）は、２００ＭＢＳから２１０ＭＢＳに更新され、ｆ（ｌｉｎｋ２６０−４）（ａｃｔｕａｌ）は、３００ＭＢＳから３１０ＭＢＳに更新され、ｆ（ｌｉｎｋ２６０−７）（ａｃｔｕａｌ）は、３００ＭＢＳから３１０ＭＢＳに更新され、ｆ（ｌｉｎｋ２６０−８）（ａｃｔｕａｌ）は、３００ＭＢＳから３１０ＭＢＳに更新され、ｆ（ｌｉｎｋ２６０−９）（ａｃｔｕａｌ）は、２００ＭＢＳから２１０ＭＢＳに更新される。
【００６２】
発明者らは、６ノードおよび５９ノードのシステムについて分析を行い、本明細書に記載し、ベル研究所のスターアルゴリズムに組み込まれた自己調節型の適応ルーティングシステムの実施形態を、従来の条件付きショーテストパスファースト（ＣＳＰＦ）ソリューションと比較すると、図５および図６に示すように効率性が改善され、収益生成能力が向上したことを確認した。
【００６３】
主として、特定のシーケンスで描写され記載されているが、方法３００および４００で示されたステップは、任意の適切な順序で実施することができることを理解すべきである。さらに、１ステップによって識別されたステップはまた、シーケンスの１つまたは複数の他のステップで実施することができ、または、２つ以上の共通のアクションは１度だけ実施することができる。たとえば、図３のステップ３４０および３６０は、図３のステップ３３０および３５０の後で実施することができる。
【００６４】
上記の様々な方法のステップは、プログラム化されたコンピュータによって実施できることを理解すべきである。本明細書において、いくつかの実施形態はまた、プログラム記憶デバイス、たとえばデータ記憶媒体を取り扱うことを意図している。これらデバイスは、マシンまたはコンピュータ可読であり、マシンまたはコンピュータが実行できる命令のプログラムを符号化し、前記命令が前記上記の方法の一部またはすべてのステップを実施する。プログラム記憶デバイスは、たとえば、デジタルメモリ、磁気ディスクおよび磁気テープなど磁気記憶媒体、ハードドライブまたは光学的読み取り可能データ記憶媒体とすることができる。この実施形態はまた、上記の方法の前記ステップを実施するためにプログラムされたコンピュータを取り扱うことを意図している。
【００６５】
図７は、図１のＰＣＥ１３０の１つ、またはノード１５０の１つなど装置７００の一実施形態を概略的に示す。装置７００は、プロセッサ７１０、データ記憶装置７１１およびＩ／Ｏインターフェース７３０を備える。
【００６６】
プロセッサ７１０は、装置７００の動作を制御する。プロセッサ７１０は、データ記憶装置７１１と協働する。
【００６７】
データ記憶装置７１１は、プロセッサ７１０によって実行可能なプログラム７２０のうちの適切な１つを記憶する。データ記憶装置７１１はまた、第１または第２の目標、第１または第２の目標情報、１つまたは複数のパス選択値または必要に応じて似たようなものなど、プログラムデータを任意選択で記憶することができる。
【００６８】
プロセッサが実行可能なプログラム７２０は、Ｉ／Ｏインターフェースプログラム７２１、パス選択値決定プログラム７２３、またはパス選択プログラム７２５を含むことができる。プロセッサ７１０は、プロセッサが実行可能なプログラム７２０と協働する。
【００６９】
Ｉ／Ｏインターフェース７３０は、プロセッサ７１０およびＩ／Ｏインターフェースプログラム７２１と協働して、必要に応じて、かつ上で説明したように、図１の通信チャネル１２５または１３５にわたる通信をサポートする。
【００７０】
パス選択値決定プログラム７２３は、図３のステップ、または図４のステップ４１０および４２０を、必要に応じて、かつ上で説明したように実施する。
【００７１】
パス選択プログラム７２５は、上で説明したように、図４のステップ４４０、４６０および４８０を実施する。
【００７２】
いくつかの実施形態において、プロセッサ７１０は、プロセッサ／ＣＰＵコアなどリソースを、Ｉ／Ｏインターフェース７３０は、任意の適切なネットワークインターフェースを、またはデータ記憶装置７１１は、メモリもしくは記憶デバイスを備えることができる。さらに、装置７００は、１つまたは複数のサーバ、または、プロセッサ、メモリ、ネットワークインターフェースもしくは記憶デバイスなどの構成要素からなるブレードといった、任意の適切な物理的ハードウェア構成とすることができる。こうした実施形態のうちのいくつかにおいて、装置７００は、相互に遠隔にあるクラウドネットワークリソースを備えることができる。
【００７３】
いくつかの実施形態において、装置７００は仮想マシンとすることができる。こうした実施形態のうちのいくつかにおいて、仮想マシンは、異なるマシンからの構成要素を含むことができ、または地理的に分散していてもよい。たとえば、データ記憶装置７１１およびプロセッサ７１０は、２つの異なる物理的マシンに存在することができる。
【００７４】
プロセッサが実行できるプログラム７２０が、プロセッサ７１０に実装されるとき、プログラムコードセグメントがプロセッサと連携して、特定の論理回路に類似して動作する固有のデバイスを設ける。
【００７５】
本明細書においては、たとえば、プログラムおよび論理がデータ記憶装置内に記憶され、メモリが通信可能にプロセッサと接続されている実施形態に関して描写され、記載されているが、こうした情報は、任意の適切な構成のデバイスに通信可能に接続された、任意の適切な構成のメモリ、記憶装置またはデータベースを使用し、メモリ、記憶装置または内部もしくは外部データベースの任意の適切な組合せに情報を記憶し、または、任意の適切な数のアクセス可能な外部メモリ、記憶装置もしくはデータベースを使用して、任意の他の適切な方法（たとえば、任意の適切な数のメモリ、記憶装置またはデータベースを使用して）で記憶することができることを理解すべきである。したがって、本明細書で言及されるデータ記憶装置という用語は、メモリ、記憶装置およびデータベースのすべての適切な組合せを含むことを意図している。
【００７６】
説明および図面は、本発明の原理を示しているにすぎない。したがって、本明細書では明示的に記載または示されていないが、当業者であれば、本発明の原理を具現化し、本発明の趣旨および範囲内に含まれる様々な構成を考案することができるであろうことは理解されよう。さらに、本明細書で列挙されたすべての例は、主として、発明者らにより技術を増進させるためにもたらされた本発明の原理および概念を、読者が理解する助けとなるもっぱら教育的な目的で特に意図されたものであり、このすべての例は、制限なくこうした特に列挙された例および条件であると解釈すべきである。さらに、本明細書において本発明の原理、態様および実施形態、ならびにその特定の例を述べる記述は、それらの均等物を含むように意図されている。
【００７７】
「プロセッサ」として明示された任意の機能ブロックを含む、各図面で示された様々な要素の機能は、専用ハードウェア、および適切なソフトウェアと関連したソフトウェアを実行することができるハードウェアを使用して提供することができる。プロセッサによって提供される場合、機能は、単一の専用プロセッサ、単一の共有プロセッサまたは一部を共有することができる複数の個々のプロセッサによって提供することができる。さらに、「プロセッサ」または「コントローラ」という用語を明示的に使用することは、ソフトウェアを実行することができるハードウェアを排他的に指すと理解すべきではなく、デジタル信号プロセッサ（ＤＳＰ）ハードウェア、ネットワークプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ソフトウェアを記憶するためのリードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）および不揮発性記憶装置を制限なく暗黙的に含むことができる。従来型またはカスタムの他のハードウェアもまた含むことができる。同様に、各図面で示された任意のスイッチは概念的なものにすぎない。それらの機能は、プログラム論理の動作により、専用論理により、プログラム制御と専用論理の相互作用により、または手動にさえよって実行することができ、特別な技術が、文脈からより明確に理解できるように作成者によって選択可能である。
【００７８】
本明細書の任意のブロック図は、本発明の原理を具現化する説明的な回路を概念ビューで表していることを理解すべきである。同様に、任意の流れ図、フローダイアグラム、状態遷移図、擬似コードなどは、実質的にコンピュータ可読媒体に表すことができ、したがって、コンピュータまたはプロセッサが明示的に示されているかどうかにかかわらず、コンピュータまたはプロセッサによって実行される、様々なプロセスを表すことを理解すべきである。
【図１】
2018517354.tif 000007
【図２】
2018517354.tif 000008
【図３】
2018517354.tif 000009
【図４】
2018517354.tif 000010
【図５】
2018517354.tif 000011
【図６】
2018517354.tif 000012
【図７】
2018517354.tif 000013
【国際調査報告】
2018517354.tif 000014
2018517354.tif 000015
2018517354.tif 000016