(57)【要約】【課題】  本開示は、ネットワークを再構成する方法を有する。【解決手段】  方法は、複数のネットワーク要求を集めるステップであって、前記複数のネットワーク要求の各々は、前記ネットワーク要求を該ネットワーク要求の現在の経路から新しい経路へ再ルーティングすることにより、可能なリソースリリースを有する、ステップを有する。方法は、再ルーティングされた場合にリソース競合を有しない最高リソースリリースを有する、前記複数のネットワーク要求のサブセットを選択するステップを更に有する。方法は、前記複数のネットワーク要求のサブセットを再ルーティングするステップと、前記複数のネットワーク要求のサブセットを再ルーティングするステップに応答して、再ルーティングされた要求によりもはや使用されないリソースをリリースするステップと、を更に有する。本開示は、関連するシステム及び装置を更に有する。【選択図】  図１
2014150533.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを再構成する方法であって、
複数のネットワーク要求を集めるステップであって、前記複数のネットワーク要求の各々は、前記ネットワーク要求を該ネットワーク要求の現在の経路から新しい経路に再ルーティングすることにより、可能なリソースリリースを有する、ステップと、
再ルーティングされた場合にリソース競合を有しない最高リソースリリースを有する、前記複数のネットワーク要求のうちのサブセットを選択するステップと、
前記複数のネットワーク要求のうちの前記サブセットを再ルーティングするステップと、
前記複数のネットワーク要求のうちの前記サブセットを再ルーティングするステップに応答して、再ルーティングされた要求によりもはや使用されないリソースをリリースするステップと、
を有する方法。
【請求項２】
前記ネットワーク要求を再ルーティングすることにより可能なリソースリリースを有する集めるべきネットワーク要求が存在しなくなるまで、前記集めるステップ、選択するステップ、再ルーティングするステップ、及びリリースするステップを繰り返すステップ、を更に有する請求項１に記載の方法。
【請求項３】
前記複数のネットワーク要求の前記サブセットは、１、２又は３個のネットワーク要求に限られる、請求項１に記載の方法。
【請求項４】
前記新しい経路は、前記ネットワーク要求の現在の経路及び利用可能リソースに基づく最短利用可能経路、又は最短経路に基づき決定される、請求項１に記載の方法。
【請求項５】
前記複数のネットワーク要求のサブセットを選択するステップは、
前記複数のネットワーク要求のうち最大リソースリリースを有する１つのネットワーク要求を繰り返し選ぶステップと、
次の繰り返しの前に、最後に選んだネットワーク要求の新しい経路に関連するリソースを予約するステップと、
を更に有し、
追加のネットワーク要求は、追加のネットワーク要求がリソースをリリースするために再ルーティングされなくなるまで、繰り返し選ばれる、請求項１に記載の方法。
【請求項６】
複数のネットワーク要求を集めるステップは、最短経路に限定され、
第１の要求の最短経路が利用可能か否かを決定するステップと、
前記第１の要求の最短経路が利用可能か否かの決定に基づき、前記第１の要求を該第１の要求の最短経路に再ルーティングするためにリソースリリースを計算するステップと、
第２の要求の最短経路が利用可能か否かを決定するステップと、
前記第２の要求の最短経路が利用可能か否かの決定に基づき、前記第２の要求を該第２の要求の最短経路に再ルーティングするためにリソースリリースを計算するステップと、
を有し、
前記複数のネットワーク要求のサブセットを選択するステップは、
前記第１の要求を再ルーティングするために計算されたリソースリリースと、前記第２の要求を再ルーティングするために計算されたリソースリリースとを比較するステップと、
前記複数のネットワーク要求の前記サブセットの中で、より高いリソースリリースを有する前記第１又は第２の要求を格納するステップと、
を有する、請求項４に記載の方法。
【請求項７】
最短経路に基づく要求の再ルーティングによりもはや使用されないリソースをリリースするステップの後に、前記集めるステップ、選択するステップ、再ルーティングするステップ、及びリリースするステップを繰り返すステップを有し、
複数のネットワーク要求を集めるステップは、最短利用可能経路に限定され、
第３の要求がより短い利用可能経路を有するか否かを決定するステップと、
前記第３の要求がより短い利用可能経路を有するか否かを決定するステップに基づき、前記第３の要求を該第３の要求のより短い利用可能経路に再ルーティングするためにリソースリリースを計算するステップと、
第４の要求がより短い利用可能経路を有するか否かを決定するステップと、
前記第４の要求がより短い利用可能経路を有するか否かを決定するステップに基づき、前記第４の要求を該第４の要求のより短い利用可能経路に再ルーティングするためにリソースリリースを計算するステップと、
を有し、
前記複数のネットワーク要求のサブセットを選択するステップは、
前記第３の要求を再ルーティングするために計算されたリソースリリースと、前記第４の要求を再ルーティングするために計算されたリソースリリースとを比較するステップと、
前記複数のネットワーク要求の前記サブセットの中で、より高いリソースリリースを有する前記第３又は第４の要求を格納するステップと、
を有する、請求項６に記載の方法。
【請求項８】
命令を有するコンピュータ可読媒体であって、前記命令は、プロセッサにより実行されると、
複数のネットワーク要求を集めるステップであって、前記複数のネットワーク要求の各々は、前記ネットワーク要求を該ネットワーク要求の現在の経路から新しい経路に再ルーティングすることにより、可能なリソースリリースを有する、ステップと、
再ルーティングされた場合にリソース競合を有しない最高リソースリリースを有する、前記複数のネットワーク要求のうちのサブセットを選択するステップと、
前記複数のネットワーク要求のうちの前記サブセットを再ルーティングするステップと、
前記複数のネットワーク要求のうちの前記サブセットを再ルーティングするステップに応答して、再ルーティングされた要求によりもはや使用されないリソースをリリースするステップと、
を実行する、コンピュータ可読媒体。
【請求項９】
前記ネットワーク要求を再ルーティングすることにより可能なリソースリリースを有する集めるべきネットワーク要求が存在しなくなるまで、前記集めるステップ、選択するステップ、再ルーティングするステップ、及びリリースするステップを繰り返すよう構成される、請求項８に記載のコンピュータ可読媒体。
【請求項１０】
前記新しい経路は、前記ネットワーク要求の現在の経路及び利用可能リソースに基づく最短利用可能経路、又は最短経路に基づき決定される、請求項８に記載のコンピュータ可読媒体。
【請求項１１】
前記複数のネットワーク要求のサブセットを選択するステップは、
前記複数のネットワーク要求のうち最大リソースリリースを有する１つのネットワーク要求を繰り返し選ぶステップと、
次の繰り返しの前に、最後に選んだネットワーク要求の新しい経路に関連するリソースを予約するステップと、
を更に有し、
追加のネットワーク要求は、追加のネットワーク要求がリソースをリリースするために再ルーティングされなくなるまで、繰り返し選ばれる、請求項８に記載のコンピュータ可読媒体。
【請求項１２】
複数のネットワーク要求を集めるステップは、最短経路に限定され、
第１の要求の最短経路が利用可能か否かを決定するステップと、
前記第１の要求の最短経路が利用可能か否かの決定に基づき、前記第１の要求を該第１の要求の最短経路に再ルーティングするためにリソースリリースを計算するステップと、
第２の要求の最短経路が利用可能か否かを決定するステップと、
前記第２の要求の最短経路が利用可能か否かの決定に基づき、前記第２の要求を該第２の要求の最短経路に再ルーティングするためにリソースリリースを計算するステップと、
を有し、
前記複数のネットワーク要求のサブセットを選択するステップは、
前記第１の要求を再ルーティングするために計算されたリソースリリースと、前記第２の要求を再ルーティングするために計算されたリソースリリースとを比較するステップと、
前記複数のネットワーク要求の前記サブセットの中で、より高いリソースリリースを有する前記第１又は第２の要求を格納するステップと、
を有する、請求項１０に記載のコンピュータ可読媒体。
【請求項１３】
最短経路に基づく要求の再ルーティングによりもはや使用されないリソースをリリースするステップの後に、前記命令は、前記集めるステップ、選択するステップ、再ルーティングするステップ、及びリリースするステップを繰り返すよう構成され、
複数のネットワーク要求を集めるステップは、最短利用可能経路に限定され、
第３の要求がより短い利用可能経路を有するか否かを決定するステップと、
前記第３の要求がより短い利用可能経路を有するか否かを決定するステップに基づき、前記第３の要求を該第３の要求のより短い利用可能経路に再ルーティングするためにリソースリリースを計算するステップと、
第４の要求がより短い利用可能経路を有するか否かを決定するステップと、
前記第４の要求がより短い利用可能経路を有するか否かを決定するステップに基づき、前記第４の要求を該第４の要求のより短い利用可能経路に再ルーティングするためにリソースリリースを計算するステップと、
を有し、
前記複数のネットワーク要求のサブセットを選択するステップは、
前記第３の要求を再ルーティングするために計算されたリソースリリースと、前記第４の要求を再ルーティングするために計算されたリソースリリースとを比較するステップと、
前記複数のネットワーク要求の前記サブセットの中で、より高いリソースリリースを有する前記第３又は第４の要求を格納するステップと、
を有する、請求項１２に記載のコンピュータ可読媒体。
【請求項１４】
前記複数のネットワーク要求の前記サブセットは、１、２又は３個のネットワーク要求に限られる、請求項８に記載のコンピュータ可読媒体。
【請求項１５】
プロセッサと、
命令を有するコンピュータ可読媒体と、
を有し、前記命令は、前記プロセッサにより実行されると、
複数のネットワーク要求を集めるステップであって、前記複数のネットワーク要求の各々は、前記ネットワーク要求を該ネットワーク要求の現在の経路から新しい経路に再ルーティングすることにより、可能なリソースリリースを有する、ステップと、
再ルーティングされた場合にリソース競合を有しない最高リソースリリースを有する、前記複数のネットワーク要求のうちのサブセットを選択するステップと、
前記複数のネットワーク要求のうちの前記サブセットを再ルーティングするステップと、
前記複数のネットワーク要求のうちの前記サブセットを再ルーティングするステップに応答して、再ルーティングされた要求によりもはや使用されないリソースをリリースするステップと、
を実行するよう構成される、システム。
【請求項１６】
前記新しい経路は、前記ネットワーク要求の現在の経路及び利用可能リソースに基づく最短利用可能経路、又は最短経路に基づき決定される、請求項１５に記載のシステム。
【請求項１７】
前記命令は、前記ネットワーク要求を再ルーティングすることにより可能なリソースリリースを有する集めるべきネットワーク要求が存在しなくなるまで、前記集めるステップ、選択するステップ、再ルーティングするステップ、及びリリースするステップを繰り返すよう更に構成される、請求項１５に記載のシステム。
【請求項１８】
前記複数のネットワーク要求のサブセットを選択するステップは、
前記複数のネットワーク要求のうち最大リソースリリースを有する１５つのネットワーク要求を繰り返し選ぶステップと、
次の繰り返しの前に、最後に選んだネットワーク要求の新しい経路に関連するリソースを予約するステップと、
を更に有し、
追加のネットワーク要求は、追加のネットワーク要求がリソースをリリースするために再ルーティングされなくなるまで、繰り返し選ばれる、請求項１５に記載のシステム。
【請求項１９】
複数のネットワーク要求を集めるステップは、最短経路に限定され、
第１の要求の最短経路が利用可能か否かを決定するステップと、
前記第１の要求の最短経路が利用可能か否かの決定に基づき、前記第１の要求を該第１の要求の最短経路に再ルーティングするためにリソースリリースを計算するステップと、
第２の要求の最短経路が利用可能か否かを決定するステップと、
前記第２の要求の最短経路が利用可能か否かの決定に基づき、前記第２の要求を該第２の要求の最短経路に再ルーティングするためにリソースリリースを計算するステップと、
を有し、
前記複数のネットワーク要求のサブセットを選択するステップは、
前記第１の要求を再ルーティングするために計算されたリソースリリースと、前記第２の要求を再ルーティングするために計算されたリソースリリースとを比較するステップと、
前記複数のネットワーク要求の前記サブセットの中で、より高いリソースリリースを有する前記第１又は第２の要求を格納するステップと、
を有する、請求項１６に記載のシステム。
【請求項２０】
最短経路に基づく要求の再ルーティングによりもはや使用されないリソースをリリースするステップの後に、前記命令は、前記集めるステップ、選択するステップ、再ルーティングするステップ、及びリリースするステップを繰り返すよう構成され、
複数のネットワーク要求を集めるステップは、最短利用可能経路に限定され、
第３の要求がより短い利用可能経路を有するか否かを決定するステップと、
前記第３の要求がより短い利用可能経路を有するか否かを決定するステップに基づき、前記第３の要求を該第３の要求のより短い利用可能経路に再ルーティングするためにリソースリリースを計算するステップと、
第４の要求がより短い利用可能経路を有するか否かを決定するステップと、
前記第４の要求がより短い利用可能経路を有するか否かを決定するステップに基づき、前記第４の要求を該第４の要求のより短い利用可能経路に再ルーティングするためにリソースリリースを計算するステップと、
を有し、
前記複数のネットワーク要求のサブセットを選択するステップは、
前記第３の要求を再ルーティングするために計算されたリソースリリースと、前記第４の要求を再ルーティングするために計算されたリソースリリースとを比較するステップと、
前記複数のネットワーク要求の前記サブセットの中で、より高いリソースリリースを有する前記第３又は第４の要求を格納するステップと、
を有する、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、コンピュータネットワーキングの分野に関し、より詳細には、ネットワーク再構成のシステム及び方法に関する。
【背景技術】
【０００２】
電気通信システム、ケーブルテレビシステム、データ通信ネットワークは、ネットワークを用いて、遠隔地点間で大量の情報を迅速に伝達できる。トラフィックは、このようなネットワークの種々の部分で動的に入ったり出たりする。さらに、このようなネットワークのトポロジは変化し、ネットワークの部分に障害が生じ得る。これが生じると、ネットワークは、ネットワークのリソース使用を最適化するために再構成され得る。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本開示は、ネットワーク再構成のシステム及び方法を提供する。
【課題を解決するための手段】
【０００４】
一実施形態では、ネットワークを再構成する方法は、複数のネットワーク要求を集めるステップであって、前記複数のネットワーク要求の各々は、前記ネットワーク要求を該ネットワーク要求の現在の経路から新しい経路へ再ルーティングすることにより、可能なリソースリリースを有する、ステップを有する。方法は、再ルーティングされた場合にリソース競合を有しない最高リソースリリースを有する、前記複数のネットワーク要求のサブセットを選択するステップを更に有する。方法は、前記複数のネットワーク要求のサブセットを再ルーティングするステップと、前記複数のネットワーク要求のサブセットを再ルーティングするステップに応答して、再ルーティングされた要求によりもはや使用されないリソースをリリースするステップと、を更に有する。
【図面の簡単な説明】
【０００５】
本開示並びにその特徴及び利点のより完全な理解のため、添付の図と共に以下の説明を参照する。
【図１】ネットワークを再構成するよう構成されるシステムの例示的な実施形態を示す。
【図２】再構成されるべきネットワークリンクのシステムの例示的な実施形態を示す。
【図３Ａ】ネットワークリンクのシステムの例示的な実施形態及び現在の要求を示す。
【図３Ｂ】ネットワークリンクのシステムの例示的な実施形態及び可能な再ルートを示す。
【図３Ｃ】再ルーティング後のネットワークリンクのシステムの例示的な実施形態を示す。
【図３Ｄ】前のコネクションがリリースされた後のネットワークリンクのシステムの例示的な実施形態を示す。
【図３Ｅ】ネットワークリンクのシステムの例示的な実施形態及び可能な再ルートを示す。
【図３Ｆ】再ルーティング後のネットワークリンクのシステムの例示的な実施形態を示す。
【図３Ｇ】前のコネクションがリリースされた後のネットワークリンクのシステムの例示的な実施形態を示す。
【図４Ａ】ネットワークリンクのシステムの別の例示的な実施形態及び現在の要求を示す。
【図４Ｂ】ネットワークリンクのシステムの別の例示的な実施形態及び可能な再ルートを示す。
【図４Ｃ】再ルーティング後のネットワークリンクのシステムの別の例示的な実施形態を示す。
【図４Ｄ】前のコネクションがリリースされた後のネットワークリンクのシステムの別の例示的な実施形態を示す。
【図４Ｅ】ネットワークリンクのシステムの別の例示的な実施形態及び可能な再ルートを示す。
【図４Ｆ】再ルーティング後のネットワークリンクのシステムの別の例示的な実施形態を示す。
【図４Ｇ】前のコネクションがリリースされた後のネットワークリンクのシステムの別の例示的な実施形態を示す。
【図５】ネットワークを再構成するよう構成されるシステムの例示的な動作を示す。
【図６Ａ】ネットワークを再構成するよう構成されるシステムの別の例示的な動作を示す。
【図６Ｂ】ネットワークを再構成するよう構成されるシステムの別の例示的な動作を示す。
【発明を実施するための形態】
【０００６】
本開示は、ネットワーク再構成のシステム及び方法に関する。要求のグループが集められ、各要求は、現在の経路から新しい経路への再ルーティングにより、可能なリソースリリースを有する。これらの要求のサブグループは、リソース競合を回避しながら、最高のリソースリリースを提供するために選択されても良い。次に、要求のサブグループは、それらの前の経路をリリースする前に、どの要求も中断されないように、再ルーティングされても良い。再ルーティングが生じた後に、もはや必要ないリソースは、リリースされても良い。次に、処理は、更なるリソースを解放するためにいかなる再ルーティングも生じなくなるまで、更なるリソースを解放するために反復的に繰り返されても良い。
【０００７】
図１は、ネットワークを再構成するよう構成されるシステムの例示的な実施形態を示す。システム１００は、ネットワークを再構成するよう構成されるネットワーク管理システム（NMS）１０２を有しても良い。NMS１０２は、ノード１１６のようなNMS１０２と通信するたの要素に関連して、このような再構成を生成するよう構成されても良い。NMS及びノード１１６は、例えば光ネットワーク、メッシュネットワーク、広域ネットワーク、ローカルエリアネットワーク、イントラネット、インターネット又はそれらの任意の組み合わせのようなネットワークを通じて任意の適切な方法で通信可能に結合されても良い。幾つかの実施形態では、NMS１０２は、管理又は制御プレーンを介してノード１１６と通信しても良い。例えば、NMS１０２は、管理プレーンのためのある手段を介して、ノード１１６と通信可能に結合されても良い。また、ノード１１６は、データプレーンの他の手段を介して互いに通信しても良い。或いは、NMS１０２及びノード１１６は、管理プレーン及びデータプレーンの両方のための同じ手段により結合されても良い。NMS１０２は、リンク１１２及び／又は特定のノード１１６へのアクセスを制御しても良く、ノード１１６の要求に割り当てられ得る１又は複数の利用可能なリソースを有しても良い。例えば、第１のノード１１６から第２のノードへの通信は、第３のノードを介して通信を実現しても良い。
【０００８】
リソースは、例えば、任意の適切な周波数区分、要領、記憶、光ライン、光路、波長チャネル、コンピューティングリソース、プロセッサ能力、ノード、ルータ、ポート、スイッチ、又はこれらの組み合わせを有しても良い。リソースは、システム１００により用いられるプロトコル又はサービスに従って、任意の適切な通信コネクションに割り当てられても良い。NMS１０２は、ノード１１６のネットワークリンク１１２のアクセスを制御して、ノード１１６によるネットワークリンク１１２の使用がNMS１０２により生成された経路及び割り当て又は経路により決定されるようにしても良い。
【０００９】
システム１００は、リンク１１２を介して情報又は「トラフィック」を通信しても良い。ここで、「トラフィック」は、システム１００で送信され、格納され又はソートされる情報を意味する。このようなトラフィックは、オーディオ、ビデオ、テキスト、及び／又は他の適切なデータをエンコードするよう構成された光又は電気信号を有しても良い。データは、リアルタイム又は非リアルタイムであっても良い。トラフィックは、OSI（Open  Systems  Interconnection）標準及びIP（InternetProtocol）を含むがこれらに限定されない任意の適切な通信プロトコルを介して通信されても良い。さらに、システム１００で通信されるトラフィックは、フレーム、パケットで構造化されるか又は非構造化ビットストリームを含むがこれらに限定されない任意の適切な方法で構造化されても良い。
【００１０】
NMS１０２は、コンピュータ、サーバ、モバイル装置、ルータ、ブレード、クラウドコンピューティング装置、埋め込み型コンピュータ、制御プレーン、又はボードのような任意の適切な方法で実装されても良い。NMS１０２は、メモリ１１０に通信可能に結合されるプロセッサ１０８を有しても良い。
【００１１】
ノード１１６は、例えば、リンク１１２を横切るべき情報の生成元又は消費先を有しても良い。ノード１１６は、特定の態様のリンク１１２又は他のノード１１６の要求又は必要を有しても良い。ノード１１６は、例えば、トラフィックを送信及び受信できる任意の適切なシステムを有しても良い。図示の実施形態では、各ノード１１６は、１又は複数の他のノード１１６にトラフィックを直接送信でき、１又は複数の他のノード１１６からトラフィックを直接受信できても良い。ノード１１６は、ノード及びリンク１１２の任意の組み合わせを介して、他のノードと間接的に通信しても良い。リンク１１２は、任意のシステム、装置、又はノード１１６を互いに通信可能に結合し対応するノード１１６間で情報を通信する装置を有しても良い。例えば、リンク１１２は、光ファイバ、イーサネット(登録商標)ケーブル、同軸ケーブル、ツイストペアケーブル、T１ケーブル、WiFi信号、Bluetooth(登録商標)信号又は他の適切な媒体を有しても良い。
【００１２】
システム１１０は特定の構成で図示されたが、システム１００及びNMS１０２は、任意の適切な数の又は種類のリンク１１２，ノード１１６、リソース１１４及びそれらの組み合わせを制御するよう構成されても良い。
【００１３】
NMS１０２は、経路計算エンジン１０４を有しても良い。経路計算エンジン１０４は、ノード１１６からの要求及びネットワークリンク１１２で利用可能なキャパシティが与えられると、種々のノード１１６にどんなアクセスが与えられるか、及び該アクセスがどのように生成されるか、を決定するよう構成されても良い。アクセスがどのように生成されるかの決定は、種々の中間ネットワーク装置を通るルート又はネットワークノード１１６の要求に対して取られる経路を有しても良い。経路計算エンジン１０４は、ネットワークリンク１１２へのアクセスを再ルーティングするよう構成されても良い。再ルーティングは、システム１００のリソースをより良い利用のために実行されても良い。より良い利用は、例えば、追加トラフィックのより良く収容するため、又は互いにブロックし得る要求の衝突を最小化するために、リソース使用を最小化することにより達成されても良い。再構成は、例えば、システム１００のネットワークトポロジの再構成、システム１００のネットワーク内の要素の障害、ネットワークトラフィックの変化、所定の時点、又は所定の時間期間の経過後、ネットワークリソースに対する要求の衝突、最適でないネットワーク要求の閾に達したこと、又は閾性能メトリックに達したこと、により行わせても良い。再ルーティングは、例えば、ノード１１６がネットワークリソースを利用できる新しい経路の計算を有しても良い。
【００１４】
経路計算エンジン１０４は、任意の適切な方法で実装されても良い。例えば、経路計算エンジン１０４は、ハードウェア、ソフトウェア、又はそれらの任意の適切な組み合わせにより実装されても良い。経路計算エンジン１０４は、プロセッサ１０８により実行されると経路計算エンジン１０４と関連して記載した動作を生じさせる、メモリ１１０に存在する命令を有しても良い。
【００１５】
プロセッサ１０８は、例えば、マイクロプロセッサ、マイクロコントローラ、デジタシグナルプロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（FPGA）又はプログラム命令を解釈し及び／若しくは実行し並びに／又はデータを処理するよう構成された任意の他のデジタル若しくはアナログ回路を有しても良いが、これらに限定されない。幾つかの実施形態では、プロセッサ１０８は、NMS１０２の動作の一部又は全部を実行するために、プログラム命令を解釈し及び／又は実行し、及び／又はメモリ１１０に格納されたデータを処理しても良い。メモリ１１０は、一部又は全部がアプリケーションメモリ、システムメモリ、又はそれらの両方で構成されても良い。メモリ１１０は、１又は複数のメモリモジュールを保持する及び／又は収容する任意のシステム、装置、又は機器を有しても良い。各メモリモジュールは、プログラム命令及び／又はデータをある期間の間保持するよう構成される任意のシステム、装置又は機器を有しても良い（例えば、コンピュータ可読媒体）。メモリ１１０は、非一時的であっても良い。NMS１０２の１又は複数部分又は機能は、メモリ１１０内に存在する命令をプロセッサ１０８により実行することにより実施されても良い。
【００１６】
図２〜４Gは、本開示の幾つかの実施形態を説明する。図２は、再構成されるべきリンクのシステムの例示的な実施形態を示す。図３A〜３Gは、本開示の一実施形態を通して、種々の段階の進捗を示す。図４A〜４Gは、本開示の代替の実施形態を通して、種々の段階の進捗を示す。
【００１７】
図２に示すように、○で囲んだA、B、C、D、Eはノード１１６ａ〜ｅを示し、それらの間の線はリンク１１２を表す。説明を目的として、５個のノードが示され、リンクは２つの要求のキャパシティを有する。例えば、リンクは、有限数の光波長を伝搬するキャパシティを有する光ファイバケーブルに沿った１０Ｇリンクであっても良い。任意の数及び種々のノード、リンク及び要求が用いられても良いことが理解される。特定の実施形態では、ノード及びリンクの数は非常に多く、例えば、市、州、地域又は国全体をカバーするネットワークであっても良い。図２〜４Ｇの理解の便宜のため、用語「ユニット」は、リンクのキャパシティを表すために用いられる。これは、情報を伝達するためにノード１１６及び／又はリンク１１２のキャパシティを制限し、ここに記載されるようにリソースに関連し得る任意の機能を有しても良い。例えば、ユニットは、光帯域幅、処理限度、又はここに記載する任意の他のリソースにより決定されても良い。ここで便宜上及び例示目的で、各リンク１１２は８ユニットのキャパシティを有し、各要求が４ユニットを必要とするとして記載される。キャパシティ及び要求の要件の任意の組み合わせ又は指定が用いられても良い。例えば、キャパシティは１０ユニットとして指定されても良く、第１の要求は３ユニットを要求し、第２の要求は５ユニットを要求しても良い。しかしながら、理解のため、上述の指定が用いられる。
【００１８】
図３A〜３Gは、本開示の例示的な実施形態を示す。本実施形態では、再ルーティングされている要求のための最短利用可能経路に基づき、要求が経路に沿って再ルーティングされる。図３Aは、リンクのシステムの例示的な実施形態及びそれらの関連する経路を示す。図３Aに示すように、３個の現在の要求が示される。前述のように、説明を目的として、要求は、各リンクの８ユニットのうち４個を必要とする。ノードAをノードEに接続する第１の要求３１０は、AからDへ、次にDからCへ、そしてCからEへとリンクを横切る。ノードBをノードEに接続する第２の要求３２０は、BからCへ、次にCからDへ、そしてDからEへとリンクを横切る。ノードCをノードDに接続する第３の要求３３０は、CからBへ、次にBからAへ、そしてAからDへとリンクを横切る。図３Aに示すように、AをDに、BをCに、DをDに接続する各リンクは、２つの要求を有する。したがって、これらのリンクには利用可能なリソースは存在しない。AをDに、DをEに、EをCに接続するリンクは、利用可能なリソースを有する。図３Aから分かるように、要求経路の幾つかは、理想的な構成ではない。例えば、各要求３１０、３２０、３３０は、より短い利用可能経路である。これらのより短い経路を用いることにより、これらの理想的でない構成により使用されているリソースはリリースされ得る。したがって、ネットワークを再構成することにより、リソースはより効率的に使用できる。これは、要求経路を再ルーティングすることにより達成され得る。
【００１９】
幾つかの実施形態では、リソースをリリースするために再ルーティングされ得る要求セットが集められても良い。これは、PossReroutedセットと呼ばれる。各要求について、これは、利用可能なリソースと要求の現在の経路との組み合わせに基づき決定されても良い。幾つかの実施形態では、これは、要求の再ルーティングの重複する可能性を生じ得る。例えば、２つの可能な再ルートがそれらの新しい経路で両方とも同じ利用可能なリソースを使用する必要がある場合、これら２つの可能な再ルートは、リソース衝突又はリソース競合を有する。PossReroutedは、最短利用可能経路、最短経路、又はそれらの組み合わせに基づき集められても良い。
【００２０】
図３Bは、ネットワークリンクのシステムの例示的な実施形態及びこれらのリンクを横切る要求の可能な再ルートを示す。第１の要求３１０は、第１の新しい経路３１５へ再ルーティングされても良い。第１の要求３１０は現在AからDへの経路を横切っているので、AからDへの特定のリンクの全てのリソースが使用されているとしても、第１の新しい経路３１５はAからDへのリンクを用いても良い。第１の新しい経路３１５は、DからEへのリンクが１つの追加要求経路のために利用可能なリソースを有するので、DからEへのリンクを横切るよう再ルーティングされても良い。第１の新しい経路３１５は、DからEへの利用可能なリソースを用いると同時に、DからCへ及びCからEへのリソースを効率的に解放し得る。ネットリソースのリリースは、４ユニットであり得る。
【００２１】
第２の要求３２０は、第２の新しい経路３２５へ再ルーティングされても良い。第２の要求３２０は現在BからCへの経路を横切っているので、BからCへの特定のリンクの全てのリソースが使用されているとしても、第２の新しい経路３２５はBからCへのリンクを用いても良い。第２の新しい経路３２５は、CからEへのリンクが１つの追加要求経路のために利用可能なリソースを有するので、CからEへのリンクを横切るよう再ルーティングされても良い。第２の新しい経路３２５は、CからEへの利用可能なリソースを用いると同時に、CからDへ及びDからEへのリソースを効率的に解放し得る。ネットリソースリリースは、４ユニットであり得る。
【００２２】
第３の要求３３０は、第３の新しい経路３３５へ再ルーティングされても良い。第３の新しい経路３３５は、CからEへ及びEからDへのリンクのために利用可能なリソースを用いても良い。第３の新しい経路３３５は、CからEは及びEからDへの利用可能なリソースを使用すると同時に、CからBへ、BからAへ、AからDへのリソースを効率的に解放しても良い。ネットリソースリリースは、４ユニットであり得る。
【００２３】
説明を目的として以上でノード間のリンク及びこれらのリンクのユニットが用いられたが、これらの例は限定ではない。むしろ、リソースのリリースは、ここに記載される任意のリソースを利用可能にすることに関連する。
【００２４】
本開示の特定の実施形態によると、可能な再ルートを有する要求の完全なセットが集められると（PossRerouted）、次に、該セットのサブセットが、実際に再ルーティングされるために選択される。このセットは、Reroutedと呼ばれる。このサブセットは、最高リソースリリースの取得に基づき選択されても良い。幾つかの実施形態では、Reroutedの選択は反復的に生じても良い。例えば、最高リソースリリースを有する要求が最初に選択され、該要求の再ルーティングに関連するリソースが予約されても良い。次に、次に高いリソースリリースを有する要求が選択され、最高リソースリリースを再ルーティングすることにより、該次に高い要求を再ルーティングするために必要なリソースが既に予約されているリソースを必要とするか否かに関し、言い換えると、次に高い要求が予約されたリソースとのリソース競合を有するかどうかの、決定が行われる。次に高いリソースリリースは、リソース競合を有する場合、セットReroutedに含まれなくても良い。この処理は、PossReroutedの各要求について繰り返されても良い。幾つかの実施形態では、リソースの予約は、最高リソースリリースを有する要求を再ルーティングするためのコネクションを実際に形成することを有しても良い。このような実施形態では、リソース競合は、既に再ルーティングされた要求により既に使用されているリソースを有しても良い。
【００２５】
図３Bの例示的説明を用いると、可能な再ルートの各々は、同数のリソースをリリースする。しかしながら、新しいコネクションが生成されると同時に現在のコネクションが維持されるので（これは、「make-before-break」又は「bridge  and  roll」と呼ばれる）、第３の新しい経路３３５は、第１及び第２の新しい経路３１５、３２５と衝突する。したがって、Reroutedの２つの可能なセットは、８ユニットのネットリソースリリースを有する｛第１の要求３１０、第２の要求３２０｝、及び４ユニットのネットリソースリリースを有する｛第３の要求３３０｝である。したがって、示した例では、セットReroutedは、新しい経路３１５及び３２５に対応する。
【００２６】
図３Cに示すように、サブグループReroutedがPossReroutedから選択されると、新しいコネクションが生成されても良い。上述のように、これは、新しいコネクションが生成されると同時に、前のコネクションが維持されるように行われても良い。したがって、ネットワークリソース使用が最適化されると同時に、各要求は満たされ維持され得る。図３Dに示すように、コネクションが生成された後、リソースがリリースされても良い。したがって、ノードの間の経路をルーティングを伴う新しい現在の要求の使用が確立される。しかしながら、更なるネットワークリソース最適化が達成でき、処理は、要求経路の再ルーティングの別の繰り返しを通じて送られる。
【００２７】
図３Eは、第２の繰り返しの間の、ネットワークリンクのシステムの例示的な実施形態及び可能な別経路を示す。第２の繰り返しの始めに、セットPossRerouted及びReroutedは、空にされても良い。第１の要求３１０は既に最短経路なので、第１の要求３１０を再ルーティングすることによりリソースはリリースされない。第２の要求３２０についても同様である。しかしながら、第３の要求３３０は、リソースをリリースするために再ルーティングされても良い。図３Eに示す例では、第３の要求３３０は、新しい経路３３５に再ルーティングされても良い。これは、ノードCとDとの間の利用可能なリソースを使用しながら、ノードDとD、BとA、AとDの間のリソースをリリースする。ネットリソースリリースは、８ユニットであり得る。したがって、セットPossReroutedは、｛第３の要求３３０｝のみを含む。さらに、サブセットReroutedは同じであり、第３の新しい経路３３５に対応する｛第３の要求３３０｝を含む。
【００２８】
図３Fに示すように、前のコネクションを維持しながら、セットReroutedの新しいコネクションが生成される。図３Gに示すように、新しいコネクションが生成された後に、前のコネクションがリリースされる。この反復処理を用いることにより、各要求を維持しながら計算の複雑性を最小化し、リリースが最適化され得ることが分かる。さらに、新しいコネクションが生成されながら、最初のコネクションを維持することにより、要求の間のリソース依存性が回避される。
【００２９】
本開示は、セットを生成するための要求を集めるときの種々の変形を含む。幾つかの実施形態では、セットPossReroutedは、新しい経路が最短経路のみである要求に限定されても良い。他の実施形態では、PossReroutedは、新しい経路が最短利用可能経路のみである要求に限定されても良い。更に別の実施形態では、PossReroutedは、最短経路又は最短利用可能経路であっても良い。例えば、ある反復のセットが最短経路に基づき要求を集めると、後者の反復のセットは、最短利用可能経路に基づき要求を集めても良い。
【００３０】
本開示は、Reroutedのセットを生成するために、PossReroutedの要求のサブセットの選択での変形も包含する。一実施形態では、Reroutedは、新しい経路へ再ルーティングできる要求がなくなるまで、最高リソースリリースを有する要求を反復的に選択することにより、選択されても良い。代替の実施形態では、Reroutedは、少数の要求、例えば３個の要求のうちの１つに制限されても良い。Reroutedを少数の要求に制限することは、リソースをより頻繁にリリースし得る。しかしながら、これは、再構成が追加の反復を通って進むので、PossReroutedの収集をより頻繁に生じさせる。Reroutedに対する数の制限は、リソースをリリースする頻度と利用可能なリソースに基づきPossReroutedを収集する頻度との間でバランスをとるよう選択されても良い。さらに、数の制限は、再構成が通る反復の数に渡り変化しても良い。例えば、第１の反復はReroutedを３個の要求に制限し、第２の反復はReroutedを５個の要求に制限し、等である。
【００３１】
図４A〜４Gは、図３A〜３Gと同様の再構成されるべきネットワークリンクのシステムの代替の例示的な実施形態を示す。しかしながら、図４A〜４Gは、PossReroutedが最短経路に限定される実施形態を示す。
【００３２】
図４Aに示すように、３個の現在の要求が示される。前述のように、説明を目的として、要求は、各リンクの８ユニットのうち４個を必要とする。ノードAをノードEに接続する第１の要求４１０は、AからDへ、次にDからCへ、そしてCからEへとリンクを横切る。ノードBをノードEに接続する第２の要求４２０は、BからCへ、次にCからDへ、そしてDからEへとリンクを横切る。ノードCをノードDに接続する第３の要求４３０は、CからBへ、次にBからAへ、そしてAからDへとリンクを横切る。図４Aに示すように、AをDに、BをCに、DをDに接続する各リンクは、２つの要求を有する。したがって、これらのリンクには利用可能なリソースは存在しない。AをDに、DをEに、EをCに接続するリンクは、利用可能なリソースを有する。
【００３３】
図４Bは、ネットワークリンクのシステムの代替の例示的な実施形態及び最短経路に基づきこれらのリンクを横切る要求の可能な再ルートを示す。第１の要求４１０は、AからEへの最短経路を表す第１の新しい経路４１５へ再ルーティングされても良い。第１の要求４１０は現在AからDへの経路を横切っているので、AからDへの特定のリンクの全てのリソースが使用されているとしても、第１の新しい経路４１５はAからDへのリンクを用いても良い。第１の新しい経路４１５は、DからEへのリンクが１つの追加要求経路のために利用可能なリソースを有するので、DからEへのリンクを横切るよう再ルーティングされても良い。第１の新しい経路４１５は、DからEへの利用可能なリソースを用いると同時に、DからCへ及びCからEへのリソースを効率的に解放し得る。ネットリソースのリリースは、４ユニットであり得る。
【００３４】
第２の要求４２０は、BからEへの最短経路を表す第２の新しい経路４２５へ再ルーティングされても良い。第２の要求４２０は現在BからCへの経路を横切っているので、BからCへの特定のリンクの全てのリソースが使用されているとしても、第２の新しい経路４２５はBからCへのリンクを用いても良い。第２の新しい経路４２５は、CからEへのリンクが１つの追加要求経路のために利用可能なリソースを有するので、CからEへのリンクを横切るよう再ルーティングされても良い。第２の新しい経路４２５は、CからEへの利用可能なリソースを用いると同時に、CからDへ及びDからEへのリソースを効率的に解放し得る。ネットリソースリリースは、CとDとの間の４ユニットであっても良い。
【００３５】
第１の要求４１０と第２の要求４２０とは既にCからDへのリンクに沿った全てのリソースを利用しているためにCからDへの最短経路は利用可能ではないので、第３の要求４３０は可能な再ルートを有しない。したがって、第３の要求４３０は、PossReroutedに含まれなくても良い。図４Bに示す例では、PossReroutedセットは｛第１の要求４１０、第２の要求４２０｝である。
【００３６】
本開示の特定の実施形態によると、PossReroutedが集められると、Reroutedが実際に再ルーティングされるために選択される。このサブセットは、最高リソースリリースの取得に基づき選択されても良い。本例では、第１の新しい経路４１５及び第２の新しい経路４２５はリソース衝突を生じず、最大リソースリリースを生成するので、ReroutedはPossReroutedと同じセットであっても良い。
【００３７】
図４Cに示すように、サブグループReroutedがPossReroutedから選択されると、新しいコネクションが生成されても良い。上述のように、これは、新しいコネクションが生成されると同時に、前のコネクションが維持されるように行われても良い。したがって、ネットワークリソース使用が最適化されると同時に、各要求は満たされ維持され得る。図４Dに示すように、コネクションが生成された後、リソースがリリースされても良い。したがって、ノードの間の経路をルーティングを伴う新しい現在の要求の使用が確立されても良い。しかしながら、更なるネットワークリソース最適化が達成でき、処理は、要求経路の再ルーティングの別の繰り返しを通じて送られても良い。
【００３８】
図４Eは、第２の繰り返しの間の、ネットワークリンクのシステムの例示的な実施形態及び可能な別経路を示す。第２の繰り返しの始めに、セットPossRerouted及びReroutedは、空にされても良い。第１の要求４１０及び第２の要求４２０は、既にそれらの最短経路にある。しかしながら、第３の要求４３０は、リソースをリリースするために再ルーティングされても良い。図３Eに示す例では、第３の要求４３０は、CとDとの間の最短経路を表す新しい経路４３５に再ルーティングされても良い。これは、ノードCとDとの間の利用可能なリソースを使用しながら、ノードDとD、BとA、AとDの間のリソースをリリースする。ネットリソースリリースは、８ユニットであり得る。したがって、セットPossReroutedは、｛第３の要求４３０｝のみを含む。さらに、サブセットReroutedは同じであり、新しい経路４３５に対応する｛第３の要求４３０｝を含む。
【００３９】
図４Fに示すように、前のコネクションを維持しながら、セットReroutedの新しいコネクションが生成される。図４Gに示すように、新しいコネクションが生成された後に、前のコネクションがリリースされる。
【００４０】
図３A〜３Gと４A〜４Gに示す実施形態で同じ最終結果が得られるが、ネットワークリソースを再構成するために異なる実施形態が使用されたことが理解される。例えば、図３A〜３Gでは、第１の反復のセットPossReroutedは｛第１の要求３１０、第２の要求３２０｝を含むが、図４A〜４Gでは、第１の反復のセットPossReroutedは｛第１の要求４１０、第２の要求４２０｝を含む。
【００４１】
図５は、ネットワークを再構成するよう構成されるシステムの例示的な動作を示す。動作５１０は、リソースをリリースする可能な再ルートを有する複数のネットワーク要求を収集するステップを含む。これらの要求は、セットPossibleReroutesに集められても良い。動作５２０は、リソース衝突を有しない最高リソースリリースに対応するネットワーク要求のサブセットを選択するステップを有する。この選択は、セットReroutesであっても良い、動作５３０は、動作５２０で選択されたネットワーク要求のサブセットを再ルーティングするステップを有する。例えば、セットReroutes内の各要求は、動作５３０でルーティングされても良い。動作５４０は、動作５３０で再ルーティングされたネットワーク要求によりもはや使用されないリソースをリリースするステップを有する。動作５５０により示すように、次に、これらの動作は繰り返され、新しくリリースされるリソースを用いる新しい経路に基づき追加リソースをリリースする。幾つかの実施形態では、それらは、新しい再ルートがリソースをリリースしなくなるまで、言い換えるとセットが空になるまで、繰り返される。
【００４２】
図６A、６Bは、最短経路及び最短利用可能経路の両方が使用されるネットワークを再構成するよう構成されるシステムの代替の例示的な動作を示す。先ず、動作は、要求を該要求の最短経路に再構成し、次に、要求を該要求の最短利用可能経路に再構成しても良い。図６Aに示される第１の部分は、最短経路部分と表される。図６Bに示される第２の部分は、最短利用可能経路部分と表される。図６A、６Bで一緒に動作するように示したが、各部分は独立に動作しても良い。さらに、２つの部分の順序は変更されても良く、２つの部分の中のループは処理全体が各部分を通る時を変更するように変更されても良い。
【００４３】
図６A、６Bに関連して、本開示を理解するために、変数が用いられても良い。しかしながら、これらは単なる説明であり限定ではないことが理解される。例えば、変数SP（最短経路及び最高リソースリリースを有する要求セットを表し、セットReroutesに対応する）、highestRel（要求を再ルーティングすることによる現在の最高リソースリリースを表す）、release（現在分析されている要求のリソースリリースを表す）、SP-Demand（最短経路に基づく最高リリースを有する要求を表す）、i（全ての要求を繰り返し通過するために用いられる）、n（合計要求数を表すために用いられる）、SAPs（最短利用可能経路及び最高リソースリリースを有する要求のセットを表し、セットReroutesに対応する）、SAP-Demand（最短利用可能経路に基づく最高リリースを有する要求を表す）が用いられても良い。
【００４４】
図６Aを参照すると、動作６０２で、再構成が開始しても良い。動作６０４で、セットSPは、空、ヌル集合、又はＳＰ＝｛｝に初期化されても良い。動作６０６で、highestRel、SP-Demand、i及びnを含む他の変数が初期化されても良い。動作６０８で、要求ｉが該要求の最短利用可能経路を有するか否かに関する決定が行われても良い。最短経路が利用可能ではない場合、処理は、動作６１６へ進んでも良い。最短経路が利用可能である場合、処理は動作６１０へ進んでも良い。動作６１０で、リソースリリースは、要求ｉを該要求の最短経路に再ルーティングするために決定されても良い。変数releaseは、決定されたリソースリリースに等しいセットであっても良い。動作６１２で、releaseがhighestRelより大きいか否かに関する決定が行われても良い。releaseがhighestRelより大きくない場合、処理は、動作６１６へ進んでも良い。releaseがhighestRelより大きい場合、処理は、動作６１４へ進んでも良い。動作６１４で、highestRelはreleaseの値に変更され、SP-Demandの値は要求ｉに変更されても良い。動作６１６で、iがnに等しいか否か、言い換えるとn個の要求のうちの全部が分析されたかどうかに関する決定が行われても良い。全ての要求が分析された場合、又はiがnに等しい場合、処理は動作６２０に進んでも良い。iがnに等しくない場合、処理は動作６１８へすすみ、動作６０８に戻り継続する前に、次の要求を分析するために、iが１だけ増大されても良い。
【００４５】
動作６２０で、SP-Demandが−１より大きいか否かに関する決定が行われても良い。言い換えると、最短経路のリソースリリースの利用可能な再ルートを有する要求が見つかったか否かに関する決定が行われても良い。SP-Demandが−１より大きい場合、処理は、動作６２２へ進んでも良い。動作６２２で、SP-Demandはその現在の経路からその最短経路へ再ルーティングされても良い。これは、SP-Demandの現在の経路のリソースをリリースすることなく生じても良い。新しいコネクションが生成されると、SP-DemandはセットSPに追加される。処理は、動作６０６に戻り、関連するリソースリリースを有する追加最短経路が利用可能かどうかを決定しても良い。SP-Demandが−１より大きくない場合、処理は、動作６２４へ進んでも良い。
【００４６】
動作６２４で、セットSPが空か否かに関して、言い換えると新しいコネクションを有するがリリースされるべきリソースを依然として有する最短経路が存在するかどうかに関して決定が行われても良い。SPが空ではない場合、処理は動作６２６にすすみ、SP内の要求によりもはや使用されないリソースがリリースされても良い。ここで、処理は、動作６０４へ進み、追加でリリースされるリソースで追加最短経路が利用可能かどうかを決定しても良い。SPが空である場合、文字Bで示すように、処理は動作６２８へ進む。
【００４７】
図６Bを参照すると、処理は動作６２８から来る。図６Bは図６Aと同様であるが、処理は、最短経路ではなく、最短利用可能経路に基づいても良い。動作６５４で、セットSAPは、空、ヌル集合、又はSAP＝｛｝に初期化されても良い。動作６５６で、highestRel、SAP-Demand、i及びnを含む他の変数が初期化されても良い。動作６５８で、要求ｉが該要求のより短い利用可能経路を有するか否かに関する決定が行われても良い。より短い経路が利用可能ではない場合、処理は、動作６６６へ進んでも良い。より短い経路が利用可能である場合、処理は、動作６６０へ進んでも良い。動作６６０で、リソースリリースは、要求ｉを該要求のより短い利用可能経路に再ルーティングするために決定されても良い。変数releaseは、決定されたリソースリリースに等しいセットであっても良い。動作６６２で、releaseがhighestRelより大きいか否かに関する決定が行われても良い。releaseがhighestRelより大きくない場合、動作は、動作６６６へ進んでも良い。releaseがhighestRelより大きい場合、処理は、動作６６４へ進んでも良い。動作６６４で、highestRelはreleaseの値に変更され、SAP-Demandの値は要求ｉに変更されても良い。動作６６６で、iがnに等しいか否か、言い換えるとn個の要求のうちの全部が分析されたかどうかに関する決定が行われても良い。全ての要求が分析された場合、又はiがnに等しい場合、処理は動作６７０に進んでも良い。iがnに等しくない場合、処理は動作６６８へすすみ、動作６５８に戻り継続する前に、次の要求を分析するために、iが１だけ増大されても良い。
【００４８】
動作６７０で、SAP-Demandが−１より大きいか否かに関する決定が行われても良い。言い換えると、再ルーティングによりリソースをリリースし得るより短い利用可能経路のリソースリリースを有する要求が見つかったか否かに関する決定が行われても良い。SAP-Demandが−１より大きい場合、処理は、動作６７２へ進んでも良い。動作６７２で、SAP-Demandはその現在の経路からその最短利用可能経路へ再ルーティングされても良い。これは、SAP-Demandの現在の経路のリソースをリリースすることなく生じても良い。新しいコネクションが生成されると、SAP-DemandはセットSAPに追加される。処理は、動作６５６に戻り、関連するリソースリリースを有する追加最短利用可能経路が利用可能かどうかを決定しても良い。SAP-Demandが−１より大きくない場合、処理は、動作６７４へ進んでも良い。
【００４９】
動作６７４で、セットSAPが空か否かに関して、言い換えると新しいコネクションを有するがリリースされるべきリソースを依然として有するより短い利用可能経路が存在するかどうかに関して決定が行われても良い。SAPが空ではない場合、処理は動作６７６にすすみ、SAP内の要求によりもはや使用されないリソースがリリースされても良い。ここで、処理は、動作６５６へ進み、新しくリリースされるリソースで追加最短利用可能経路が利用可能かどうかを決定しても良い。SAPが空である場合、処理は動作６７８へ進み、終了する。SAPが空ではない場合、文字Aで示すように、処理は動作６３０へ進む。動作６３０は、図６Aの動作６０４へ戻る。言い換えると、追加リソースが最短利用可能経路処理によりリリースされると、全体の処理は、最短利用可能経路処理に戻る前に、最短経路が利用可能にされたかどうかについて決定する。
【００５０】
上述のように、再ルーティングのセットの大きさを制限するために、図６A、６Bに示した動作の変更が可能である。例えば、図６Aで、SPの大きさは、少数（例えば１）に限定され、動作６２２の再ルーティングの後に、処理が動作６０６に戻るのではなく動作６２６へ進むようにしても良い。１より大きい数が用いられる場合、処理は、SPの大きさがその数に一致するまで進み、次に、動作６０６に戻って再ルーティングするのではなく、動作６２６へ進んでも良い。図６Bも同様であっても良い。例えば、SAPの大きさは、少ない数に限定されても良い。例えば、SAPの大きさが１に限定される場合、処理は、動作６５６に戻ってルーティングするのではなく、動作６７２から動作６７６へ進んでも良い。SAPの大きさが１より大きい場合、処理は、SAPの大きさが限定数に一致するまでループを続け、次に、処理は、全ての可能な再ルーティングが説明されるまでループバックするのではなく、動作６７６へ進んでも良い。
【００５１】
ここで、「又は」は、他に明示的に示されない限り又は文脈上特に示されない限り、包括的であり、排他的ではない。従って、本願明細書では、特に明示的に示されない限り又は文脈上別に示されない限り、「Ａ又はＢ」は「Ａ、Ｂ、又は両方」を意味する。更に、「及び」は、他に明示的に示されない限り又は文脈上特に示されない限り、結合及び幾つかの両方である。従って、本願明細書では、特に明示的に示されない限り又は文脈上別に示されない限り、「Ａ及びＢ」は「Ａ及びＢ、一緒に又は別々に」を意味する。
【００５２】
特定の実施形態は、ハードウェア、ソフトウェア、又はハードウェアとソフトウェアとの組み合わせとして実施されても良い。例として且つ限定ではなく、１又は複数のコンピュータシステムは、本願明細書に記載又は説明された１又は複数の方法の１又は複数のステップを実行するために、特定のロジック又はソフトウェアを実行してもよい。特定の実施形態を実施するソフトウェアは、適切な場合には、任意の適切なプログラミング言語（手続き型又はオブジェクト指向であっても良い）で、又はプログラミング言語の組み合わせで実装されても良い。種々の実施形態では、ソフトウェアは、コンピュータ可読記憶媒体に格納されても良い。適切な場合には、任意の適切な種類のコンピュータシステム（単独又は複数のプロセッサコンピュータシステム）又は複数のシステムが、特定の実施形態を実施するソフトウェアを実行しても良い。適切な場合には、汎用コンピュータシステムは、特定の実施形態を実施するソフトウェアを実行しても良い。特定の実施形態では、ロジックの部分は、１又は複数の機能を実施する間に、コンポーネントにより送信及び／又は受信されても良い。
【００５３】
ここで、コンピュータ可読記憶媒体という表現は、１又は複数の非一時的な有形のコンピュータ可読記憶媒体処理構造を包含する。例として且つ限定ではなく、コンピュータ可読記憶媒体は、適切な場合には、半導体に基づく又は他の集積回路（ＩＣ）（例えば、ＦＰＧＡ（field-progratnmable  gate  array）又はＡＳＩＣ（application-specific  IC））、ハードディスク、ＨＤＤ、ＨＨＤ（hybrid  hard  drive）、光ディスク、光ディスクドライブ（ＯＤＤ）、光磁気ディスク、磁気媒体、固体ドライブ（ＳＳＤ）、ＲＡＭドライブ、他の適切なコンピュータ可読記憶媒体、又はこれらの２つ以上の組み合わせを有してもよい。コンピュータ可読非一時的記憶媒体は、適切な場合には、揮発性、不揮発性又は揮発性と不揮発性との組合せであってもよい。
【００５４】
本開示は、任意の適切な記憶装置を実装する１又は複数のコンピュータ可読記憶媒体を包含する。適切な場合には、特定の実施形態では、コンピュータ可読記憶媒体は、１又は複数のプロセッサ部分、１又は複数のメモリ部分、これらの組み合わせを有しても良い。特定の実施形態では、コンピュータ可読記憶媒体はＲＡＭ又はＲＯＭを実装する。特定の実施形態では、コンピュータ可読記憶媒体は揮発性又は永久メモリを実装する。
【００５５】
本開示は、当業者が考え得る、本願明細書に記載された例である実施形態の全ての変更、代替、変形、選択肢、及び修正を包含する。同様に、適切な場合には、添付の特許請求の範囲は、当業者が考え得る、本願明細書に記載された例である実施形態の全ての変更、代替、変形、選択肢、及び修正を包含する。さらに、特定の機能を実行するよう、適応され、配置され、可能にされ、構成され、実行可能なように、動作可能なように、又は機能するようにされた装置又はシステム又は採用されている装置若しくはシステムの構成要素への添付の特許請求の範囲中の参照は、それ又は該特定の機能が作動され、オンに切り替えられ、又は解除されているか否かに拘わらず、該装置、システム又は構成要素がそのように適応され、配置され、可能にされ、構成され、使用可能にされ、動作可能にされ又は機能するようにされている限り、該装置、システム、構成要素を包含する。例えば、種々の実施形態は、上述のステップの全部、一部を実行しても良く、いずれも実行しなくても良い。種々の実施形態は、上述の機能を種々の順序で実行しても良い。
【００５６】
本発明は幾つかの実施形態と共に記載されたが、種々の変更、代替、変形、交換、変換、及び修正が当業者に示唆され、また、本発明は、このような全ての変更、代替、変形、交換、変換、及び修正を添付の特許請求の範囲の精神及び範囲として包含する。
【符号の説明】
【００５７】
１００  システム
１０２  NMS
１０４  経路計算エンジン
１０８  プロセッサ
１１０  メモリ
１１２  リンク
【図１】
2014150533.tif 000003
【図２】
2014150533.tif 000004
【図３Ａ】
2014150533.tif 000005
【図３Ｂ】
2014150533.tif 000006
【図３Ｃ】
2014150533.tif 000007
【図３Ｄ】
2014150533.tif 000008
【図３Ｅ】
2014150533.tif 000009
【図３Ｆ】
2014150533.tif 000010
【図３Ｇ】
2014150533.tif 000011
【図４Ａ】
2014150533.tif 000012
【図４Ｂ】
2014150533.tif 000013
【図４Ｃ】
2014150533.tif 000014
【図４Ｄ】
2014150533.tif 000015
【図４Ｅ】
2014150533.tif 000016
【図４Ｆ】
2014150533.tif 000017
【図４Ｇ】
2014150533.tif 000018
【図５】
2014150533.tif 000019
【図６Ａ】
2014150533.tif 000020
【図６Ｂ】
2014150533.tif 000021