(57)【要約】【課題】マルチプロトコル・ラベル・スイッチング（ＭＰＬＳ）のネットワーク・チューニングのためのシステムおよび方法を提供する。【解決手段】一実施形態では、システムは、回避すべきエッジを条件として、定義済みのホット・ゾーンから経路を変更すべきラベル・スイッチ・パス（ＬＳＰ）を再帰的に識別するホット・ゾーン・クリア・サブシステムを含む。その実施形態では、システムは、ホット・ゾーン・クリア・サブシステムに結合され、経路変更を行うべきＬＳＰを順序付けて、移動シーケンスをもたらすＬＳＰ順序付けサブシステムをさらに含む。移動シーケンスは、ホット・ゾーンの負荷を削減するために利用可能である。【選択図】図１
2004336777.tif 000002
【特許請求の範囲】
【請求項１】
マルチプロトコル・ラベル・スイッチングのネットワーク・チューニングのためのシステムであって、
回避すべきエッジを条件として、定義済みのホット・ゾーンから経路を変更すべきラベル・スイッチ・パス（ＬＳＰ）を再帰的に識別するホット・ゾーン・クリア・サブシステムと、
前記ホット・ゾーン・クリア・サブシステムに結合され、前記経路変更を行うべきＬＳＰを順序付けて、移動シーケンスをもたらすＬＳＰ順序付けサブシステムであって、前記移動シーケンスが前記ホット・ゾーンの負荷を削減するために利用可能であるＬＳＰ順序付けサブシステムとを含むシステム。
【請求項２】
前記ホット・ゾーン・クリア・サブシステムは、定義済みの再帰深さを条件として前記ＬＳＰを再帰的に識別する、請求項１に記載のシステム。
【請求項３】
前記ホット・ゾーン・クリア・サブシステムは、前記負荷が定義済みのレベルに減少するまで前記ＬＳＰを再帰的に識別する、請求項１に記載のシステム。
【請求項４】
前記ＬＳＰ順序付けサブシステムは、
前記定義済みホット・ゾーン中の前記ＬＳＰのリンクの数、および
前記ＬＳＰの帯域のうち選択された１つに従って前記ＬＳＰを順序付ける、請求項１に記載のシステム。
【請求項５】
前記ＬＳＰは、
候補経路中において最大限に利用されたリンクへの負荷、
候補経路の長さ、および
前記ＬＳＰとのリンクの共有のうち選択された１つに従って選択された候補経路に、経路が変更される、請求項１に記載のシステム。
【請求項６】
前記候補経路の１つが、そのいずれかのリンクにおいて十分な解放帯域が不足している場合に、前記ホット・ゾーン・クリア・サブシステムは、前記候補経路の前記１つを含む第２の定義済みホット・ゾーンから経路を変更すべきＬＳＰを再帰的に識別する、請求項５に記載のシステム。
【請求項７】
前記ＬＳＰ順序付けサブシステムは、
利用可能性が最も低い帯域、
最大帯域、および
リンクの数のうち選択された１つに基づいて前記ＬＳＰを順序付ける、請求項１に記載のシステム。
【請求項８】
マルチプロトコル・ラベル・スイッチングのネットワーク・チューニングのための方法であって、
回避すべきエッジを条件として、定義済みのホット・ゾーンから、経路を変更すべきラベル・スイッチ・パス（ＬＳＰ）を再帰的に識別する工程と、
前記経路変更を行うべきＬＳＰを順序付けて、移動シーケンスをもたらす工程であって、前記移動シーケンスが前記ホット・ゾーンの負荷を削減するために利用可能である工程とを含む方法。
【請求項９】
前記再帰的に識別する工程は、定義済みの再帰深さを条件として実行される、請求項８に記載の方法。
【請求項１０】
前記再帰的に識別する工程は、前記負荷が定義済みのレベルに減少するまで実行される、請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、マルチプロトコル・ラベル・スイッチング（Ｍulti-Ｐrotocol Ｌabel Ｓwitching：ＭＰＬＳ）を対象とし、特に、ＭＰＬＳを使ったネットワーク・チューニングのためのシステムおよび方法を対象とする。
【背景技術】
【０００２】
マルチプロトコル・ラベル・スイッチング（ＭＰＬＳ）は、サービス・プロバイダにとっての主要技術として出現した。ＭＰＬＳについての主な応用例の１つとして、トラフィック・エンジニアリング（Ｔraffic Ｅnginerring：ＴＥ）（Ａｗｄｕｃｈｅらによる、「Ｒｅｑｕｉｒｅｍｅｎｔｓ  ｆｏｒ  ｔｒａｆｆｉｃ  ｅｎｇｉｎｅｅｒｉｎｇ  ｏｖｅｒ  ＭＰＬＳ」（ＩＥＴＦ  ＲＦＣ２７０２、１９９７年）を参照されたい）が挙げられる。ＭＰＬＳ  ＴＥの機能は、ラベル・スイッチ・パス（Ｌabel Ｓwitching Ｐath：ＬＳＰ）による経路指定の制御に柔軟性を提供するので魅力的である。
【０００３】
従来、ＴＥは、個々のＬＳＰの効率的な経路指定に焦点を当てている。しかし、ネットワーク・トラフィックが音声からデータに移っていくのにつれて（ネットワークの「チャーン(churn)」に加えて）、ネットワークの効率性の水準を維持または改善することますます難しくなりつつある。この状態は、データが、音声トラフィックの階層的な成長構造を欠いていることによって、さらに悪化している。したがって、サービス・プロバイダは、自分達のＭＰＬＳネットワークに対するネットワーク規模のエンジニアリングおよび管理のためのツールを求めている。
【０００４】
ＲＳＶＰ（Ａｗｄｕｃｈｅらによる、「Ｅｘｔｅｎｓｉｏｎ  ｔｏ  ＲＳＶＰ  ｆｏｒ  ＬＳＰ  ｔｕｎｎｅｌｓ」（ＩＥＴＦドラフト、１９９８年）を参照されたい）などの標準化シグナリング・プロトコルに関連して、ＭＰＬＳは、メーク・ビフォ・ブレーク(make-before-break)などの構成を用いた、中断のない再構成のためのインフラストラクチャを提供する。メーク・ビフォ・ブレークは、それだけでは無瞬断(hitless)のパケット配信を保証しない。しかし、ＴＣＰベースのアプリケーションなど、クライアント・サービスの障害許容力(resiliency)と結合すると、ほとんどのオペレーション・シナリオ(operation scenario)において、メーク・ビフォ・ブレークは中断のない再構成を保証する。
【０００５】
残念なことに、終端間の効率を改善するためにこの再構成可能性インフラストラクチャを利用しているネットワーク管理システムは皆無である。さらに、オンラインで、サービスの中断が全くなく動作するシステムは皆無である。無瞬断のネットワーク規模のエンジニアリングのプロセスを「ネットワーク・チューニング（Network Tuning）」と呼ぶことができる。ネットワーク・チューニングは、将来の非効率を防ぐための事前対策の場合、あるいは、障害など、特定のネットワーク・イベントに対する対応策の場合のいずれかであり得ることに注意されたい。ＴＥとは異なり、チューニングは、ラベル・スイッチング・パス（ＬＳＰ）ごとのパラメータ（例えば、帯域または経路）調整オペレーション(tweaking operation)ではなく、終端間ネットワーク・オペレーションを包含するものである。以下に記載の例は、この概念を説明する。
【０００６】
初めに図１を参照すると、６台のＩＰルータ、容量Ｂの７つのリンク、および容量Ｂ／２の３つのＬＳＰ  Ｌ１〜Ｌ３から成る、例示的ネットワークを示してある。ＡとＣの間に、帯域Ｂの新たなＬＳＰ  Ｌ４に対する要求があるとする。通常のＭＰＬＳネットワークでは、Ｃへの帯域が不十分なため、Ａはこの要求を拒否する。しかし、ネットワーク中には容量が十分にある。ただし、断片化されている。チューニング・インテリジェンスを備えたネットワーク管理システムであれば、その需要が満たされるように、トラフィックを事前にリエンジニアすることができる。
【０００７】
例えば、Ｌ２がＡ−Ｅ−Ｆを通るように、またＬ３がＡ−Ｂ−Ｄを通るように経路を変更することによって、Ａ−ＣにＬ４を供給することが可能になる。したがって、このようなオンライン・チューニングによって、それを行わなければ拒否されたはずの要求を満たすことができ、結局は、ネットワークの利用を改善し、また資本支出を削減する助けとなる。
【０００８】
しかし、何百ものノードおよびＬＳＰを有するネットワークのチューニングを基準化することは、容易ならないコンピュータ計算上の課題を呈する。さらに、ＭＰＬＳは、トラフィック再構成中の中断を最小限に抑えるために必要なメカニズムを提供するが、それをどのように利用したらよいかに関するインテリジェンスを提供することはない。ネットワーク・チューニングには、様々なＬＳＰの経路を決定する（フロー設計問題）だけでなく、より重要なこととして、いかなるサービスの中断をも防ぐ、ＬＳＰ経路変更の工程のシーケンスを引き出す（パス移動問題）ことも含まれる点に注意されたい。
【０００９】
このフロー設計問題に関する従来技術では、パスの移動を考慮することなく、最適なフローの割当てに焦点が当てられていた。このような例の１つが、本明細書に参照により組み込まれている、Ｅｌｗａｌｉｄらによる「Ｏｎｌｉｎｅ  ｔｒａｆｆｉｃ  ｅｎｇｉｎｅｅｒｉｎｇ  ｗｉｔｈ  ｄｅｓｉｇｎ−ｂａｓｅｄ  ｒｏｕｔｉｎｇ」（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＴＣ  Ｓｐｅｃｉａｌｉｓｔ  Ｗｏｒｋｓｈｏｐ，Ｗｕｒｚｂｕｒｇ，２００２年７月）、およびその中で参照されているその他の参考文献に記載されている。パス移動問題は、光ＷＤＭネットワークの状況において研究がなされている。本明細書に参照により組み込まれている、Ｒａｍａｍｕｒｔｈｙらによる「Ｖｉｒｔｕａｌ  Ｔｏｐｏｌｏｇｙ  Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ  ｏｆ  Ｗａｖｅｌｅｎｇｔｈ−ｒｏｕｔｅｄ  Ｏｐｔｉｃａｌ  ＷＤＭ  Ｎｅｔｗｏｒｋｓ」（ＩＥＥＥ  ＧＬＯＢＥＣＯＭ  Ｐｒｏｃｅｅｄｉｎｇｓ、２０００年）においては、フロー設計問題のためのＬＰ公式に再構成上の制約が追加されており、また、本明細書に参照により組み込まれている、Ｓｒｉｄｈａｒａｎらによる「Ｏｐｅｒａｔｉｎｇ  Ｍｅｓｈ−Ｓｕｒｖｉｖａｂｌｅ  ＷＤＭ  Ｔｒａｎｓｐｏｒｔ  Ｎｅｔｗｏｒｋｓ」（ＳＰＩ  Ｉｎｔ．Ｓｙｍｐ．Ｔｅｒａｂｉｔ  Ｏｐｔｉｃａｌ  Ｎｅｔｗｏｒｋｉｎｇ、２０００年１１月）では、ネットワークの最適化のためのＩＬＰ公式に、再構成コストが追加されている。しかし、両者の目的は再構成を最小限に抑えることであり、どの再構成も依然としてサービス中断の可能性があるままである。本明細書に参照により組み込まれている、Ｂａｌａらによる「Ｔｏｗａｒｄｓ  Ｈｉｔｌｅｓｓ  Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ  ｉｎ  ＷＤＭ  Ｏｐｔｉｃａｌ  Ｎｅｔｗｏｒｋｓ  ｆｏｒ  ＡＴＭ  Ｔｒａｎｓｐｏｒｔ」（ＩＥＥＥ  ＧＬＯＢＥＣＯＭ  Ｐｒｏｃｅｅｄｉｎｇｓ、１９９６年）では、元の構成および最適化された構成の結合をサポートするのに十分なリソースを前提とした、無瞬断の再構成を達成するための方法が提案されているが、この前提は、実際には無理である。
【非特許文献１】Ａｗｄｕｃｈｅらによる、「Ｒｅｑｕｉｒｅｍｅｎｔｓ  ｆｏｒ  ｔｒａｆｆｉｃ  ｅｎｇｉｎｅｅｒｉｎｇ  ｏｖｅｒ  ＭＰＬＳ」（ＩＥＴＦ  ＲＦＣ２７０２、１９９７年）
【非特許文献２】Ａｗｄｕｃｈｅらによる、「Ｅｘｔｅｎｓｉｏｎ  ｔｏ  ＲＳＶＰ  ｆｏｒ  ＬＳＰ  ｔｕｎｎｅｌｓ」（ＩＥＴＦドラフト、１９９８年）
【非特許文献３】Ｅｌｗａｌｉｄらによる「Ｏｎｌｉｎｅ  ｔｒａｆｆｉｃ  ｅｎｇｉｎｅｅｒｉｎｇ  ｗｉｔｈ  ｄｅｓｉｇｎ−ｂａｓｅｄ  ｒｏｕｔｉｎｇ」（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＴＣ  Ｓｐｅｃｉａｌｉｓｔ  Ｗｏｒｋｓｈｏｐ，Ｗｕｒｚｂｕｒｇ，２００２年７月）
【非特許文献４】Ｒａｍａｍｕｒｔｈｙらによる「Ｖｉｒｔｕａｌ  Ｔｏｐｏｌｏｇｙ  Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ  ｏｆ  Ｗａｖｅｌｅｎｇｔｈ−ｒｏｕｔｅｄ  Ｏｐｔｉｃａｌ  ＷＤＭ  Ｎｅｔｗｏｒｋｓ」（ＩＥＥＥ  ＧＬＯＢＥＣＯＭ  Ｐｒｏｃｅｅｄｉｎｇｓ、２０００年）
【非特許文献５】Ｓｒｉｄｈａｒａｎらによる「Ｏｐｅｒａｔｉｎｇ  Ｍｅｓｈ−Ｓｕｒｖｉｖａｂｌｅ  ＷＤＭ  Ｔｒａｎｓｐｏｒｔ  Ｎｅｔｗｏｒｋｓ」（ＳＰＩ  Ｉｎｔ．Ｓｙｍｐ．Ｔｅｒａｂｉｔ  Ｏｐｔｉｃａｌ  Ｎｅｔｗｏｒｋｉｎｇ、２０００年１１月）
【非特許文献６】Ｂａｌａらによる「Ｔｏｗａｒｄｓ  Ｈｉｔｌｅｓｓ  Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ  ｉｎ  ＷＤＭ  Ｏｐｔｉｃａｌ  Ｎｅｔｗｏｒｋｓ  ｆｏｒ  ＡＴＭ  Ｔｒａｎｓｐｏｒｔ」（ＩＥＥＥ  ＧＬＯＢＥＣＯＭ  Ｐｒｏｃｅｅｄｉｎｇｓ、１９９６年）
【非特許文献７】Ａｈｕｊａらによる「Ｎｅｔｗｏｒｋ  Ｆｌｏｗｓ：Ｔｈｅｏｒｙ，Ａｌｇｏｒｉｔｈｍｓ，ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ」（Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ、１９９３年）
【非特許文献８】Ｓｈｅｐｈｅｒｄらによる「Ｈａｒｄｎｅｓｓ  ｏｆ  Ｐａｔｈ  Ｅｘｃｈａｎｇｅ  Ｐｒｏｂｌｅｍ」（Ｐｅｒｓｏｎａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ）
【非特許文献９】Ｇａｒｅｙらによる「Ｃｏｍｐｕｔｅｒｓ  ａｎｄ  Ｉｎｔｒａｃｔａｂｉｌｉｔｙ  −  Ａ  Ｇｕｉｄｅ  ｔｏ  ｔｈｅ  Ｔｈｅｏｒｙ  ｏｆ  ＮＰ−Ｃｏｍｐｌｅｔｅｎｅｓｓ」（Ｆｒｅｅｍａｎ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ，１９７９）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
したがって、この技術分野では、ＭＰＬＳネットワークにおいて有効な、中断のないネットワーク・チューニングを達成するためのシステムおよび方法が必要とされている。
【課題を解決するための手段】
【００１１】
上述の従来技術の欠陥に対処するため、本発明は、ＭＰＬＳネットワーク・チューニングのためのシステムおよび方法を提供する。一実施形態では、本システムは、（１）回避すべきエッジを条件として、定義済みのホット・ゾーン(hot zone)から経路を変更すべきＬＳＰを、再帰的に識別するホット・ゾーン・クリア・サブシステム(hot zone clearing subsystem)と、（２）ホット・ゾーン・クリア・サブシステムに結合され、経路変更を行うべきＬＳＰを順序付けて、移動シーケンスをもたらすＬＳＰ順序付けサブシステムとを含む。移動シーケンスは、ホット・ゾーンの負荷を削減（恐らくゼロにまで）するために利用可能である。
【００１２】
本発明の一実施形態では、ホット・ゾーン・クリア・サブシステムは、定義済みの再帰(recursion)の深さを条件としてＬＳＰを再帰的に識別する。関連実施形態では、ホット・ゾーン・クリア・サブシステムは、負荷が定義済みのレベルに減少するまでＬＳＰを再帰的に識別する。
【００１３】
ＬＳＰ順序付けサブシステム(LSP ordering subsystem)は、（１）定義済みホット・ゾーン中のＬＳＰのリンクの数、および（２）ＬＳＰの帯域のうち選択された１つに従ってＬＳＰを順序付ける。もちろん、その他の順序付けヒューリスティックス(heuristics)も、本発明の広範な範囲に含まれる。
【００１４】
本発明の一実施形態では、ＬＳＰは、（１）候補経路中において最大限に利用されたリンクへの負荷、（２）候補経路の長さ、および（３）ＬＳＰとのリンクの共有のうち選択された１つに従って選択された候補経路に、経路が変更される。その他の経路変更ヒューリスティックスも本発明の範囲に含まれる。より詳細な実施形態では、候補経路の１つが、そのいずれかのリンクにおいて十分な帯域が不足している場合に、ホット・ゾーン・クリア・サブシステムは、候補経路の１つを含む第２の定義済みホット・ゾーンから経路を変更すべきＬＳＰを、再帰的に識別する。
【００１５】
本発明の一実施形態では、ＬＳＰ順序付けサブシステムは、（１）利用可能性が最も低い帯域、（２）最大帯域、および（３）リンクの数のうち、選択された１つに基づいてＬＳＰを順序付ける。もちろん、その他の順序付けヒューリスティックスも本発明の範囲に含まれる。
【００１６】
上記は、当業者が以下の本発明の詳細な説明をよりよく理解できるように、本発明の好ましく、選択可能な特徴をかなり概略的に説明したものである。本発明の特許請求の範囲の主題を形成する、本発明のさらなる特徴を以下に記載する。当業者は、本発明と同じ目的を実行するためのその他の構造を設計または修正するための基礎として、開示の概念および特定の実施形態を容易に使用できることを理解されたい。当業者はまた、そのような同等の構成が、一般的な形態の本発明の趣旨および範囲から逸脱しないことも理解されたい。
【００１７】
本発明をより完全に理解するために、添付の図面を参照しながら、以下の記載を参照していく。
【発明を実施するための最良の形態】
【００１８】
以下に、ネットワーク・チューニングにおけるアルゴリズム上の問題について説明する。これは、最終的にはホット・ゾーンのクリア、すなわち「ＨＺＣ」問題の定義に至る。最初に、実際に起こり得るネットワーク・オペレーションのシナリオの例を２つ挙げる。次いで、それらのシナリオを使って、本発明の記載の実施形態によって解決することが可能な、中心となるアルゴリズム上の問題を抽出する。
【００１９】
以下の２つのオペレーション上のシナリオ、およびそれらに対処するためのネットワーク管理システムについて考察してみよう。
【００２０】
（１）設定失敗のチューニング（ＳＦＴ）−これは、図１に示すケースであり、前に「発明の背景」の節で説明してある。ＬＳＰ設定が失敗した場合、チューニング・ツールの要件は、既存のトラフィックを再構成してその需要を満たすことであり、またそれをサービスの中断なしに行うことである。
（２）ホット・ゾーンのクリア（ＨＺＣ）−ネットワークの構成要素は、通常、ダウン時間（例えば、ソフトウェアのアップグレードのための）を必要とし、このダウン時間の間に、それらの構成要素を通過するトラフィックの経路変更を行わなければならない。今日行われている手動による経路変更は、煩わしく、しかも誤りが生じやすい作業である。これに代わるものとして、「ホット・ゾーン」（特定のノードまたはリンク）を選択して、そこを通過するトラフィックがクリアされるようにする機能があれば、オペレータにとっては魅力的なツールになるであろう。ＨＺＣに対する別のモチベーションとして、負荷のバランスをとることが挙げられる。ＨＺＣは、過度に混雑しているエリアをマークして、ＬＳＰのいくつかの経路変更を行うための方法をオペレータに提供する。クリアされるトラフィックが影響を受けないように、また、どこかに渋滞部分（ボトルネック(bottleneck)）を生じさせないように十分な配慮が必要であることに注意されたい。
【００２１】
ネットワーク・チューニングには、その他のいくつかのオペレーション・シナリオが該当する。しかし、ここではそのようなシナリオについて説明しない。当業者であれば、さらなる説明なしに、本明細書の教示をそれらのシナリオに容易に適用することができるからである。
【００２２】
ＨＺＣシナリオは、上記の２つの問題のうちより一般的なケースである。最初に、新しい要求に対して候補経路を選択し、次いで、その選択した経路上のエッジに対してＨＺＣオペレーションを実施することにより、ＳＦＴのケースをＨＺＣにマップすることができる。したがって、ここでは、ＨＺＣ問題が焦点となる。正式には、ＨＺＣ問題を以下のように述べることができる。
【００２３】
ＨＺＣの定義−Ｇ（Ｖ，Ｅ）を、Ｖ個のノードとＥ個のエッジを有するネットワークとする。クリアすべきエッジの集合Ｅｃ（ホット・ゾーン）がある（Ｅｃ⊂Ｅ）とすると、全てのエッジｅｉ（ｅｉ∈Ｅｃ）上の負荷がαまで低減され、またＥｃ中に含まれない全てのエッジｅｊ（ｅｊ∈（Ｅ−Ｅｃ）上の負荷がβよりも上に増加しないように、Ｅｃ中のエッジを通過するＬＳＰの経路を変更する。パラメータβは、好ましくは、渋滞部分が単にそのホット・ゾーンからどこかに移動するだけではないことを保証する。
【００２４】
概略的に、ＨＺＣは、２つの異なる最適化の問題を解決することを必要とする。第１は、標準トラフィック・フロー設計問題であり、この問題の目標は、終端間の需要マトリックス、および様々なリンク上で利用可能な、残っている帯域がある場合に、最適なＬＳＰ経路設計を決定することである。第２段階はパス移動問題であり、最適化されたＬＳＰトポロジがある場合に、現行のトポロジからその最適化されたトポロジへの最適な無瞬断のパス移動シーケンスを見つける。
【００２５】
残念なことに、これらの問題はともに、既知のＮＰ問題（NP-hard problem）に対応するものである。前者は、整数解を求める多品種フロー設計問題（multicommodity flow design problem with integer solution）（Ａｈｕｊａらによる「Ｎｅｔｗｏｒｋ  Ｆｌｏｗｓ：Ｔｈｅｏｒｙ，Ａｌｇｏｒｉｔｈｍｓ，ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ」（Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ、１９９３年）を参照されたい）の変形であり、後者は、設定順序付け問題（set-ordering problem）(Ｓｈｅｐｈｅｒｄらによる「Ｈａｒｄｎｅｓｓ  ｏｆ  Ｐａｔｈ  Ｅｘｃｈａｎｇｅ  Ｐｒｏｂｌｅｍ」（Ｐｅｒｓｏｎａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ）およびＧａｒｅｙらによる「Ｃｏｍｐｕｔｅｒｓ  ａｎｄ  Ｉｎｔｒａｃｔａｂｉｌｉｔｙ  −  Ａ  Ｇｕｉｄｅ  ｔｏ  ｔｈｅ  Ｔｈｅｏｒｙ  ｏｆ  ＮＰ−Ｃｏｍｐｌｅｔｅｎｅｓｓ」（Ｆｒｅｅｍａｎ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ，１９７９）を参照されたい）を縮小したものであり得る。どちらも、効果的な解決策を認めてはいない。後者の問題は特に解決するのが難しく、効果的な近似解法の望みがほとんどない。したがって、この２段階のアプローチは、無瞬断遷移が重要な要件であるオンラインの設定においては、限定的に役立つだけである。
【００２６】
その代わりとして、本明細書では、新規な統合ネットワーク最適化アルゴリズムを取り入れ、開示する。このアルゴリズムは、両方の問題に同時に対応し、また、それらの問題を扱いやすくするために近似ヒューリスティックスを使用している。以下にこのアルゴリズムについて説明する。また、この問題のＮＰ困難性を打破するために使用する、近似ヒューリスティックスについても説明する。
【００２７】
ＨＺＣ問題の目標は、選択されたホット・ゾーン中のリンクの負荷を、ネットワークの残りの部分に過負荷をかけることなく、所与の率だけ削減することである。これは、ホット・ゾーンを通過するＬＳＰの部分集合について、それらのＬＳＰのパスに対する制約を維持したまま、経路変更を行うことにより達成される。以下に、このアルゴリズムがどのように動作するかを示す例を記載して、このアルゴリズムを詳細に説明する。
【００２８】
図１に戻ると、ルータＡからＣまでのＬＳＰ  Ｌ４を帯域Ｂで設定する要求が、帯域不足のために失敗した。しかし、ＡからＣへのパスには十分な帯域がないとしても、ネットワーク全体には余分の帯域が十分にある。したがって、ＬＳＰ設定に対する需要を、ａ）Ｌ４を供給するための経路を選択すること、およびｂ）この経路に対してＨＺＣを実施することによって満たすことができる。選択された経路がＡ−Ｃであったと想定する。Ｌ４は、リンクＡ−Ｃの全帯域を必要とするため、そのリンク上の既存のＬＳＰ、すなわちＬＳＰ  Ｌ３について、強制的に経路変更が行われる。これによって、Ｌ３についてのＬＳＰ設定の副次的問題が生じ、その結果、その新しい経路Ａ−Ｂ−Ｄに対してＨＺＣが実施される。最終的に、この経路上のＬＳＰ、すなわちＬ２の経路が変更されて、遷移シーケンス（Ｌ２、Ａ−Ｅ−Ｆ）、（Ｌ３、Ａ−Ｂ−Ｄ）および（Ｌ４、Ａ−Ｃ）が完成する。Ｌ３については、代替経路（Ａ−Ｅ−Ｆ−Ｂ−Ｄ）が存在するが、それは、遅延やホップ・カウントなどの制約がある場合には、必ずしも候補経路にならないことがあることに注意されたい。
【００２９】
例では、ホット・ゾーンに対するＨＺＣの実施は再帰プロシージャであり、そのホット・ゾーンを通過するＬＳＰ  Ｌ４に加えて、そのホット・ゾーンを通過しないＬＳＰ（例えば、Ｌ２およびＬ３）の経路変更につながる場合があることを示している。以下に、このアルゴリズムについて詳細に説明する。
【００３０】
次に、図２を参照すると、全体を２００として表す、本発明の原理に従って構築したＭＰＬＳネットワーク・チューニングのためのシステムの一実施形態の構成図を示してある。システム２００は、ＨＺＣサブシステム２１０を含む。ＨＺＣサブシステム２１０は、回避すべきエッジを条件として、定義済みのホット・ゾーンから経路を変更すべきＬＳＰを、再帰的に識別する。システム２００は、ＬＳＰ順序付けサブシステム２２０をさらに含む。ＬＳＰ順序付けサブシステム２２０は、ＨＺＣサブシステム２１０に結合されており、経路変更を行うべきＬＳＰを順序付けて、移動シーケンスをもたらす。この移動シーケンスを利用して、ホット・ゾーンの負荷を削減（恐らくゼロにまで）することができる。
【００３１】
次に、図３を見ると、全体を３００として表す、本発明の原理に従って実行される、構築されたＭＰＬＳネットワーク・チューニングのための方法の一実施形態の流れ図を示してある。方法３００は開始ステップ３１０で開始し、この場合、ＬＳＰのホット・ゾーンの少なくとも一部をクリアすることが望ましい。方法３００はステップ３２０に進み、ここで、定義済みのホット・ゾーンから経路を変更すべきＬＳＰが、回避すべきエッジを条件として再帰的に識別される。方法３００はステップ３３０に進み、ここで、ステップ３２０で識別されたＬＳＰが「移動シーケンス」と呼ばれる順序付けられたリスト(orderedlist)中に記載される。この移動シーケンスを利用して、ホット・ゾーンの負荷を削減（恐らくゼロに）することができる。定義済みの再帰の深さに応じて、ステップ３２０、３３０が繰り返される。ステップ３３０からステップ３２０に戻っている二重破線は、この任意の再帰を表す。最大の再帰の深さに到達すると、方法３００は、ステップ３４０で終了する。
【００３２】
次に、図４を見ると、本発明の原理を実行する、開示のアルゴリズムを実施するソフトウェア・プログラム４００の擬似コード・リストを示してある。関数ＨＺＣは、ホット・ゾーンの負荷を削減するためにホット・ゾーン中のＬＳＰの経路を変更する再帰関数である。この関数への入力は、ホット・ゾーン中のリンクの集合、経路変更中に回避すべきエッジのリスト、現在の再帰の深さ、および負荷率αおよびβである。
【００３３】
出力は、ＬＳＰの元のパスから計算されたパスへの移動シーケンスを提供する、順序付けられたリストである。再帰の深さは、ステップ１４に示すようなパラメータの深さによって、ＭＡＸＤＥＰＴＨに限定される。ａｖｏｉｄＥｄｇｅｓリストを使って、どのＬＳＰもホット・ゾーン中のいかなるリンクも使わないようにし、また、ホット・ゾーン中のリンクを回避すべきリンクとしてマークすることによって経路変更を行う。ホット・ゾーン中の全てのリンクにかかる負荷が要求したαに下がるまで、入力リスト中のＬＳＰについて、１つずつ、ａｖｏｉｄＥｄｇｅｓを回避するよう経路変更が行われる。
【００３４】
再構成するためにＬＳＰを探索する順番は、最適な順番を決定することが指数関数的な複雑さを有するため、この問題の難しさを打破するためのヒューリスティックスである。ステップ４の関数ｓｏｒｔＬＳＰは、ＬＳＰを順序付けるのに本明細書に記載のヒューリスティックスの１つを使っている。ステップ８で関数ｔｒｙＴｏＭｏｖｅＬＳＰを呼び出すことにより、入力ＬＳＰを移動させるために実行する必要がある、ＬＳＰの経路変更のシーケンスが返される。このようなシーケンスが可能でない場合には、入力ＬＳＰは無視される。このアルゴリズムは、ホット・ゾーンの負荷が要求したレベルに下がると、または、経路変更を行うべきＬＳＰがなくなると、遷移シーケンスを出力して終了する。
【００３５】
関数ｔｒｙＴｏＭｏｖｅＬＳＰは、ａｖｏｉｄＥｄｇｅｓのリスト中のｅｄｇｅｓを回避しながら、単一のＬＳＰの経路を変更し、このＬＳＰの経路変更のために実行する必要がある一連のＬＳＰの経路変更を返す。ステップ１５で、サービスの要件を満たし、ａｖｏｉｄＥｄｇｅｓリストのリンクを回避する全ての可能な経路を、本明細書に記載の１組のヒューリスティックスに基づいてソートする。次いで、ステップ１８に示すように、それらの経路を探索して、どのリンクも付加率を超えないような、ＬＳＰを経路指定するのに十分な帯域を有する経路を見つける。経路が十分な帯域を持っていない場合には、ステップ２２のように、別のヒューリスティックスに基づいて、その経路上のリンクをソートする。その経路中のリンクをａｖｏｉｄＥｄｇｅｓリストに追加し、次いで、ソートした順番で各リンクに対してＨＺＣを実施し、再帰の深さを１だけ増分する。このＨＺＣから得られた遷移シーケンスをローカル・シーケンスのテールに追加する。
【００３６】
ＨＺＣがいずれかのリンクにおいて機能しなかった場合には、もうその経路をＬＳＰの経路変更に使うことができないため、ステップ３０で、この経路上のそれまでのリンクをクリアするためのなされた作業は全てロール・バックされる。次いで、次の候補経路を探索する。次の候補経路がリスト上の最後の経路である場合、ステップ１７で、ＬＳＰの経路変更が失敗したことを知らせるＮＵＬＬリストが返される。一方、ステップ３１のように、選択された経路上の全てのリンクについて、十分な帯域をクリアされた場合には、この経路がＬＳＰの新しい経路として追加され、そのＬＳＰの遷移がローカル・シーケンスに追加され、ローカル遷移シーケンスが返される。
【００３７】
以上からわかるように、ＨＺＣは再帰的プロセスであると言える。定義済みのホット・ゾーンのＨＺＣはＬＳＰの経路変更につながり、それがまたＬＳＰの候補経路のＨＺＣにつながり・・・というように繰り返すからである。この再帰のレベル（有利には、ＭＡＸＤＥＰＴＨによって制約される）は、ホット・ゾーンの内側からのトラフィックに加えて、ホット・ゾーンの外側のトラフィックがどれだけ経路変更されるかを決定する。当業者には、再帰のレベルが高いほどＨＺＣのフレキシビリティが大きくなることが明らかであろう。下記の実験１に示すように、このフレキシビリティのおかげで、このアルゴリズムの性能がその他の従来のアルゴリズムと比較して有利なものになっている。
【００３８】
２段階のフロー設計／パス移動のアプローチに対して、本明細書に記載のアルゴリズムは、検索を最小限にするためのインテリジェント・プルーニング・メカニズム(intelligent pruning mechanism)を用いたアプローチに基づく検索木を使用している。このアルゴリズムの実行時間に対して理論上の限度を与えることはできないとしても、このアルゴリズムは実際のところきわめて効率的である。
【００３９】
開示のアルゴリズムは、そのアルゴリズムの異なる段階において異なる近似ヒューリスティックスを使用する。以下に使用することができるヒューリスティックスについて説明し、それらの利点のいくつかを示す。
【００４０】
（１）ＳｏｒｔＬＳＰ−経路変更を行うべきＬＳＰが複数ある場合、ホット・ゾーン上の負荷を削減するために、経路変更の必要があるＬＳＰの数を最小限に抑えるようＬＳＰの経路変更の順番を決定しなければならない。この最適の決定はＮＰ問題であるため、何らかのヒューリスティックスを使ってＬＳＰを順序付ける。
（１ａ）ＭａｘＳｈａｒｅｄＬＳＰＦｉｒｓｔ−このヒューリスティックスは、最初に経路変更を行う必要がある、クリアすべきホット・ゾーン中の最大数のリンクを通過するＬＳＰを選択する。この単一のＬＳＰを移動させることによって、ホット・ゾーンから、その最大数のリンクにかかる負荷が削減されるとが想定される。したがって、移動しなければならないＬＳＰの数が少なくて済む。
（１ｂ）ＢｉｇｇｅｓｔＬＳＰＦｉｒｓｔ−このヒューリスティックスは、最初に、最大帯域を持つ、経路変更を行うべきＬＳＰを選択する。この単一のＬＳＰの経路を変更することによって、ホット・ゾーンから最大数のリソースが解放され、同じリソースを解放するために多くの小さいＬＳＰの経路変更を行うよりもよいと予想される。
【００４１】
（２）ＳｏｒｔＲｏｕｔｅ−あるＬＳＰの経路を変更する必要がある場合、そのＬＳＰに対して多くの候補経路の選択肢がある。候補経路を選択することによって何か重要なリソースが使われる場合があり、あるいは、その経路に対して実施されるＨＺＣオペレーションがより多くのＬＳＰの経路変更につながる場合があるため、候補経路の選択は将来の経路変更に影響を与える。
（２ａ）ＭｉｎＭａｘＵｓａｇｅ−容量いっぱい近くまで負荷がかかっているリンクの数が多い経路はできれば避けるべきである。その経路を選択することによって重要なリンクがブロックされる可能性があるためである。したがって、経路中の全リンクの最大使用量を最小限に抑える経路が経路指定のためには好ましい。
（２ｂ）ＳｈｏｒｔｅｓｔＲｏｕｔｅ−このヒューリスティックスは、経路変更に最短経路を選択することにより、そのＬＳＰによってｏｃｃｕｐｉｅｄされるリソースの数が削減され、それによってさらなる経路変更の成功の確率が高められることを前提としている。また、その経路に対するＨＺＣの場合、ホット・ゾーンのサイズが最小になり、したがって、経路変更を行うべきＬＳＰの数が削減される可能性がある。
（２ｃ）ＬｅａｓｔＤｉｓｒｕｐｔｉｖｅ−これは、最大数のリンクをＬＳＰの現在の経路と共有している経路を選択することによって、中断が削減される可能性があるという前提に基づいている。その経路に対してＨＺＣを実施しなければならない場合でも、ホット・ゾーンを形成するリンクの数が少なく、したがって、経路変更を行うべきＬＳＰの数が削減される可能性がある。この経路は、ホット・ゾーン中のすべてのエッジを回避するはずなので、ＬＳＰがほぼホット・ゾーンの内部にある場合には、その値を制約することができる。
開示のアルゴリズムは、ＭｉｎＭａｘＵｓａｇｅとＳｈｏｒｔｅｓｔＲｏｕｔｅヒューリスティックスの組合せを使って、探索する候補経路を順序付ける。
【００４２】
（３）ＳｏｒｔＬｉｎｋ−候補経路がＬＳＰを経路指定するのに十分な解放大域を持っていない場合、その候補経路中の全てのリンクに対してＨＺＣを実施しなければならない。リンクを処理する順番によって、その経路に対するＨＺＣオペレーションの成功または失敗が決まる可能性があり、また、その順番は、以下のヒューリスティックスに基づく場合がある。
（３ａ）ＭａｘＵｓａｇｅＦｉｒｓｔ−このヒューリスティックスは、利用可能な帯域が最も少ないリンクを、最初にクリアすべきであることを示している。このヒューリスティックスは、より多くのＬＳＰの経路変更を必要とする場合があり、他のリンクを最初にクリアすると、それらのＬＳＰの経路変更が難しくなる場合があるためである。単一のリンクのクリアの失敗は、その経路が経路変更に使用できないことを意味する。
（３ｂ）ＬｉｎｋＷｉｔｈＦａｔｔｅｓｔＬＳＰＦｉｒｓｔ−このヒューリスティックスは、最もｆａｔなＬＳＰの経路変更を最初に行う方がよいことを前提としている。より多くのリソースを必要とするファットなＬＳＰの経路変更の方が、シンなＬＳＰの経路変更よりも難しいからである。したがって、最大帯域のＬＳＰを有するリンクを最初にクリアすべきである。必要とされるこのリンクの負荷の減少が、そのＬＳＰの帯域よりも小さい場合、そのＬＳＰは経路変更の対象として考慮されないことに注意されたい。
（３ｃ）ＬｉｎｋＷｉｔｈＬｏｎｇｅｓｔＬＳＰＦｉｒｓｔ−このヒューリスティックスは前のものと同様であり、異なる点は、これが、短いＬＳＰよりも長いＬＳＰの経路変更の方がより難しいことを前提としていることである。したがって、長いＬＳＰはできるだけ早く経路を変更するべきであり、そのため、このＬＳＰを含むリンクは、ＨＺＣを優先的に行うべきである。開示のアルゴリズムは、単一のヒューリスティックスまたは上記の組合せを使って、以下に記載の結果を達成する。
【００４３】
開示のアルゴリズムは、検索木を使用しているので、木のサイズを制限して、実行時間のオーバヘッドを許容可能なものにできる点が有利である。開示のアルゴリズムは、好ましくはオンライン・プロセスとして動作するため、実行時間は重要である。以下に、実行時間の複雑さを改善するために使用される、３つの技術について記載する。
【００４４】
（１）制限された木の深さ−このアルゴリズムは、再帰の深さ（パラメータＤ）を制限することによって検索空間を削減する。Ｄ＝１の場合、ホット・ゾーンの外側のＬＳＰの経路変更が行われることはなく、一方Ｄ＞１は、ホット・ゾーンを通過するＬＳＰの経路変更を行うための十分なリソースを解放するために、ホット・ゾーン中にはないＬＳＰの経路変更を行わなければならない可能性があることを意味する。
（２）制限されたファンアウト(fan-out)−木のファンアウトは、各ＬＳＰについて探索される代替候補経路の数を制限することによって制御される。このアルゴリズムは、実行時間のオーバヘッドをさらに低減するために、ネットワーク中の全ての発信元−宛先の対について、ｋ個の候補経路の固定集合を予め計算する。
（３）ルートのキャッシュ−各ＬＳＰについての木の探索は候補経路に基づいているため、候補経路のｔｈｅ  ｃｏｍｍｏｎ  ｌｉｎｋｓ  ｐｒｅｆｉｘ  ｐｒｏｐｅｒｔｙを使って、アルゴリズムの実行時間を改善することができる。例示のネットワークにおけるルータＣからＦへのＬＳＰ要求を考察してみよう。最初に探索した候補経路がＣ−Ａ−Ｂ−Ｆであり、この経路に沿ったＨＺＣが失敗した（たとえば、木の深さの限界に到達した場合）と想定する。次に選択される候補経路がＣ−Ａ−Ｅ−Ｆの場合、最初の候補経路の状況におけるリンクＣ−Ａの探索は、依然として等しく有効である。したがって、前の探索の結果がキャッシュされることにより、候補経路が１より大きいサイズのｐｒｅｆｉｘｅｓを共有している場合に必ず必要とされる全作業が削減される。キャッシュによる節約は、探索しなければならない候補経路の数が多くなればなるほど改善される。キャッシュ・データの高速なルックアップは、トライ・ベース(trie-based)のインデックスを使って行われる。
【００４５】
以下に、上述のヒューリスティックスに基づいた開示のアルゴリズムの性能について説明し、また、その他のグローバル・フロー設計ベースの、実用性がより低いアプローチと比較する。
【００４６】
開示のアルゴリズムの性能について調べる。その目標は、特に実装の観点から、このアルゴリズム中で使用されているヒューリスティックスが、その性能およびスケーラビリティに与える影響を調査することである。最適な解決策はわかっていないため、フロー設計問題を解決するための多品種フロー（ＭultiＣommodity Ｆlow：ＭＣＦ）公式を使用したベンチマークに対する比較を行う。言い換えれば、ホット・ゾーンからの終端間の需要がある場合に、ＭＣＦ公式は、利用可能であれば、それらのための新しいフロー・パスを決定する。以下、このＭＣＦ公式を「理想的な解決策」と呼ぶ。
【００４７】
理想的な解決策は、様々な理由から非実用的であることに注意されたい。第１に、それは、パスの移動シーケンスなしに（全く存在しない場合もある）新しい経路を提供する。第２に、ＭＣＦ公式は、需要が複数のフローで分割されることを可能にし、したがって、それらを特定のフローにマッピングすることは、それだけで「ハードな」問題である。したがって、ホット・ゾーンからトラフィックを経路変更する開示のアルゴリズムの能力を比較するための、ホット・ゾーンからの経路変更が可能なフローに対する緩い理論上の限度を提供するためだけに理想的な解決策を使用する。
【００４８】
フロー設計問題のＭＣＦ公式は、リニア・プログラミング（ＬＰ）を使って近似値を得ることができる。ＲａｍａｍｕｒｔｈｙらによるＬＰ公式、ｓｕｐｒａを、以下のように適合化させることができる。
【数１】
2004336777.tif 000003
上式で、σは発信元−宛先の対であり、Ｒσは特定の対σに対して設定された候補経路であり、ｒはＲσに属する候補経路であり、Ｘｒはｒに属する合計フロー・ボリュームであり、λσは発信元−宛先の対σについてのホット・ゾーンからの合計フロー・ボリュームであり、Ｂｌは、リンクｌの合計帯域であり、ＨＺはホット・ゾーン内部のリンクの集合である。Ｃｌはリンク上のホット・ゾーンの外部のフローで用いられる帯域幅であり、αおよびβは下記に定める。
【００４９】
図５は、開示のアルゴリズムの性能を試験する際に利用されるシミュレーション・ネットワーク５００のマップを示す。このシミュレーション・ネットワーク５００は、４０個のノード、および１００の双方向リンクを有する。各リンクは、１０，０００ＭＢの帯域を持っている。ＬＳＰのサイズは、１００ＭＢから１，０００ＭＢの間で変わると想定する。この実験の目標は、ホット・ゾーンを完全にクリア（α＝０％）する一方、必要な場合には、ネットワークの残りの部分がその全容量まで負荷される（β＝１００％）ことを可能にする。主要性能基準値(primary performance metric)は、経路変更を行うべき帯域のパーセンテージとしての、ホット・ゾーンから実際に経路指定される合計帯域（ＴＢＲ）である。開示のアルゴリズムは、理想的な解決策とは異なり、無瞬断の遷移も保証するため、この基準値は、開示のアルゴリズムの効用の一部を捉えているにすぎない。以下に説明のグラフにおいて、ＮｅｔＬｏａｄはシミュレーション・ネットワーク５００上の平均負荷を指し、ＨＺＳｉｚｅは、合計リンクのパーセンテージとして指定された、ホット・ゾーンのサイズを指す。
【００５０】
開示のアルゴリズムの実行時間を制御するために、木の深さＤを３に制限し、発信元−宛先の対ｋごとの候補経路数を１０に制限する（理想的な解決策の場合と同じ）。上記の理想的な解決策の公式の場合、ホット・ゾーンの外側のＬＳＰを妨害することなく、ネットワークの残りの部分の上で動作し、したがって、Ｄ＝１で、開示のアルゴリズムと同等のアルゴリズムを試みる。
【００５１】
実験１−経路指定された全フロー
次に、図６Ａを参照すると、ＮｅｔＬｏａｄ＝６０％の場合のＴＢＲについて、開示のアルゴリズムと理想的な解決策を比較しているグラフ６００を示してある。開示のアルゴリズムについての２つの線６１０、６２０は、それぞれ、深さが３（Ｄ＝３）（線６２０）および深さが１（Ｄ＝１）（線６１０）の場合を表す。
【００５２】
予想されるように、ホット・ゾーンのサイズが増加すると、トラフィックの経路変更を行う能力が下がる。ホット・ゾーンのサイズが増加すると、理想的な解決策の性能（線６３０）は、実質的に開示のアルゴリズムの性能よりも低くなる。これは、開示のアルゴリズムが、無瞬断の移動を達成するのに加えて、より多くの要求の経路変更が可能であることを示す。この開示のアルゴリズムの優れた性能は、ホット・ゾーンからＬＳＰの経路を変更するための十分なリソースを解放するために、ホット・ゾーン中にはないＬＳＰの経路変更を行うことができるというその能力によるものである。したがって、ホット・ゾーンの外側のＬＳＰについては経路変更が全く行われない深さ１においては、理想的な解決策は開示のアルゴリズムよりも性能が優れている。理想的な解決策には多くの利点があるので（需要が分割できることなど）、これは驚くべきことではない。以下のいくつかの実験が実証するように、実行時間のオーバヘッドの増加が最小限度で、木をさらに深く探索することにより行われる余分のクリアが達成される。したがって、フロー設計段階と移動段階を結合するという欲張った戦略を使っているにもかかわらず、開示のアルゴリズムの性能は理想的な解決策の性能よりも勝ることが可能である。後で、その他の基準値についても開示のアルゴリズムの性能について検討する。
【００５３】
実験２−Ｄに対するアルゴリズムの感度
次に、図６Ｂを見ると、深さ（Ｄ）に対するアルゴリズムの感度を表すヒストグラム６４０を示してある。これからわかるように、図５のシミュレーション・ネットワーク５００は負荷が６０％であるため、帯域のほとんどが深さ１でクリアされる。しかし、ホット・ゾーンのサイズが増加すると、Ｄ＝２とＤ＝３の結合寄与が増加し始め、ＨＺＳｉｚｅ＝５％における０％からＨＺＳｉｚｅ＝２０％ではほぼ１５％にまでなる。これは、ホット・ゾーンが増加すると、単一のＬＳＰの経路変更を行うために、まずその他のＬＳＰの経路変更を行って十分な帯域を解放する必要があることを意味する。深さ２および３の寄与は量的には少ないが、しかし、これらの利得は達成するのが最も難しい（実験５）ことに注意されたい。したがって、ほとんどの場合、深さ１で十分なことが多く、ホット・ゾーンの帯域が重要なリソースである場合には、さらに深く進む必要がある。
【００５４】
実験３−ＮｅｔＬｏａｄに対する感度
図７Ａを見ると、ＮｅｔＬｏａｄおよびホット・ゾーンのサイズに対するネットワークの感度を表す、グラフ７００を示してある。図７Ａは、ＴＢＲが、ＨＺＳｉｚｅを増加させる関数およびＮｅｔＬｏａｄを増加させる関数の両方として減少することを示している。両方の要因が、トラフィックの再構成のために、図５のシミュレーション・ネットワーク５００中の利用可能な帯域を制限するため、これが予想される。しかし、サービス・プロバイダのネットワークの負荷は、一般に、予期せぬ障害のために十分な予備の容量を確保しておくために５０〜６０％に制限されていることに注意することが重要である。図７Ａからわかるように、６０％までの負荷については、開示のアルゴリズムは、ホット・ゾーンの８０％以上を、そのサイズが図５のシミュレーション・ネットワーク５００の２０％である場合でも、クリアすることができる。実際には、大規模なプロバイダ・ネットワーク上では、ホット・ゾーンのサイズは一般にこれよりもずっと小さく、この場合、その性能はさらにずっと魅力的なものである。
【００５５】
実験４−経路のキャッシュによる節約
上記に強調したように、前の探索から部分木の部分をキャッシュすることによって、実行時間コストを節約することができる。次に、図８Ｂを見ると、キャッシュによる開示のアルゴリズムの節約効果を表す、グラフ８３０を示してある。図８Ｂは、キャッシュによる節約を、このアルゴリズムによって探索されるＬＳＰの数の削減のパーセンテージで示しており、これは、直接、アルゴリズムの実行時間の節約につながる。図８Ｂは、ホット・ゾーンのサイズが小さい場合には、探索するＬＳＰが少ないほど節約の安定度が減ることを示している。たった１つのＬＳＰの違いでも、この節約に著しく寄与する可能性がある。
【００５６】
ホット・ゾーンのサイズが増加すると、キャッシュによる節約の平均も、５％前後から２０％にまで増加する。これは、ホット・ゾーンのサイズの増加に伴って、有効な解決策を見つけるためにより多くの検索を行わなければならないことによる。したがって、キャッシュによる実行時間の節約は、それが一番問題になるとき、すなわち、アルゴリズムの実行時間自体が増加するときに増加する。
【００５７】
最後の２つの実験では、直接オペレータに影響を与える、分かり易い要因、すなわち、達成される実行時間のチューニング・コストおよびネットワークの効率の向上が考慮される。
【００５８】
実験５−実行時間のオーバヘッド
次に、図７Ｂを見ると、実行時間コストに対するネットワークの感度を表す、グラフ７１０を示してある。図７Ｂは、開示のアルゴリズムが１５％のホット・ゾーン・サイズについて実行を完了するのに要する時間を示している。このグラフは、開示のアルゴリズムが実に高速に実行していることを示しており、深さ１については２、３秒以内で出力を配信している（ｘ軸を対数目盛で表し、曲線上の点は深さのレベルを表していることに注意されたい）。予想されるように、深さ２および３を探索するのにかかる時間は長くなるが、負荷の増加に伴ってより複雑な移動シーケンスが配信される。このグラフは、深さ１では、遷移のほとんどが急速に達成されるが、さらなる探索も実用的に実行可能であり、その完了に１０秒以上を必要とすることはめったにない。（これらの実験は、ＳｕｎＯＳ５．７を実行している、４，０９６ＭＢのメモリを備えたＳｕｎ  Ｕｌｔｒａ−４  Ｓｐａｒｃ上で実施された。）これは、開示のアルゴリズムが有効なオンライン・アルゴリズムであることを実証している。
【００５９】
実験６−資本支出の節約
サービス・プロバイダにとって主要な目標は、チューニングから期待できる効率性の向上である。これを、ネットワーク・チューニングを行った場合および行わない場合に、図５のシミュレーション・ネットワーク５００がどのように急速に成長するかを調べることによって研究する。リンクの負荷の閾値を６０％と想定する。実際のプロバイダ・ネットワークをシミュレートして、ある需要によって、この負荷閾値を超えるリンクの利用が生じた場合には、新たな並列リンクが供給されるものと想定する。
【００６０】
チューニングによって達成される改善を説明するために、同じ実験を、周期的にトリガされるＨＺＣで実行する。この場合、各リンクは、その容量の８０％までの負荷が可能である。リンクが８０％の負荷閾値を超えると、６０％を超える負荷を受けているリンクは全てホット・ゾーンとみなされ、これらの重い負荷のリンクに対してＨＺＣがトリガされる。ＨＺＣチューニングによって、いずれかリンクの利用を６０％未満にすることができなかった場合、前と同様、並列リンクが供給される。
【００６１】
次に、図８Ａを見ると、開示のアルゴリズムのネットワークの成長に対する効果を示す、グラフ８００を示してある。図８Ａは、ｘ軸上にトラフィック・ボリュームを示し、ｙ軸上に、そのトラフィックをサポートするのに必要なＯＣ−ＯＣ１９２インタフェース・カードの数によって表した、図５のシミュレーション・ネットワーク５００のサイズを示している。この図からわかるように、チューニングを行わない場合のネットワークの成長（線８１０）ははるかに急速であり、トラフィックの成長に対してほぼ直線的に成長している。一方、ＨＺＣチューニングは、それよりもはるか勾配がなだらかな成長を示している（線８２０）。
【００６２】
さらに、開示のアルゴリズムは、段階的な成長曲線（線８２０）からわかるように、可能な程度までハードウェアの供給を遅らせることによって、資本支出を節約することができる。このデータを別の観点から見て、同じネットワーク・ハードウェアについてサポートされるネットワークの容量を比較してみよう。その結果、同じネットワーク・インフラストラクチャについて、場合によっては、チューニングにより、図５のシミュレーション・ネットワーク５００が５０％増のトラフィック（例えば、３１８ポートの場合）を運ぶことが可能になることがわかる。これをネットワーキング・ハードウエアの金額的なコストの節約に換算すると、サービス・プロバイダにとって、著しい資本支出の節約になる。
【００６３】
本発明を詳細に説明したが、当業者は、最も一般的な形態での本発明の趣旨および範囲から逸脱することなく、本明細書に記載の様々な変更、代用、改変を施すことができることを理解されたい。
【図面の簡単な説明】
【００６４】
【図１】本発明の原理を適用できる例示的ネットワークを示す図である。
【図２】本発明の原理に従って構築されたＭＰＬＳネットワーク・チューニングのためのシステムの一実施形態の構成図である。
【図３】本発明の原理に従って実行されるＭＰＬＳネットワーク・チューニングのための方法の一実施形態の流れ図である。
【図４】本発明の原理を実行する開示のアルゴリズムを実施する、ソフトウェア・プログラムの擬似リストを示す図である。
【図５】開示のアルゴリズムの性能を試験する際に利用されるシミュレーション・ネットワークのマップを示す図である。
【図６】図６Ａは、実際に経路指定された合計帯域（ＴＢＲ）に関して、開示のアルゴリズムと理想的解決策を比較するグラフであり、図６Ｂは、深さ（Ｄ）に対するアルゴリズムの感度を示すヒストグラムである。
【図７】図７Ａは、ＮｅｔＬｏａｄおよびホット・ゾーンのサイズに対するネットワークの感度を表すグラフであり、図７Ｂは、実行時間コストに対するネットワークの感度を表すグラフである。
【図８】図８Ａは、ネットワークの成長に対する開示のアルゴリズムの効果を表すグラフであり、図８Ｂは、キャッシュによる節約を表すグラフである。
【図１】
2004336777.tif 000004
【図２】
2004336777.tif 000005
【図３】
2004336777.tif 000006
【図４】
2004336777.tif 000007
【図５】
2004336777.tif 000008
【図６】
2004336777.tif 000009
【図７】
2004336777.tif 000010
【図８】
2004336777.tif 000011