(57)【要約】      （修正有）【課題】モバイルＶＰＮサービスで帯域幅保証されたサービスを少ない費用で提供するための方法を提供する。【解決手段】１組のＶＰＮ顧客、各ＶＰＮ顧客に関連する少なくとも１つのモバイル・アクセス・ポイント（ＭＡＰ）および少なくとも１つの顧客構内機器（ＣＰＥ）、ならびにＭＡＰとＣＰＥの間のＶＰＮトンネリングを行う少なくとも１つのＩＰサービス・ゲートウェイ（ＩＰＳＧ）を特定することを含み、各ＭＡＰは、各ＩＰＳＧから地理的に遠隔である。選択されたＩＰＳＧ上でＶＰＮ顧客にサービス提供を行うことからもたらされる総利益を最大化するように、ＩＰＳＧのサブセットが選択される。すべての顧客からの総利益は、各顧客からの利益の合計を含み、ただし、各顧客に関して、顧客利益は、重み付けされた収益から費用を引いたものに等しく、１つの顧客当たりの費用は、ＭＡＰからＣＰＥまでの総帯域幅費用、およびＩＰＳＧを配置する費用を含む。【選択図】図２
2004260833.tif 000002
【特許請求の範囲】
【請求項１】
１組の仮想プライベート・ネットワーク（ＶＰＮ）顧客、各ＶＰＮ顧客（２２０）に関連する少なくとも１つのモバイル・アクセス・ポイント（ＭＡＰ）（２０８）および少なくとも１つの顧客構内機器（ＣＰＥ）（２２２）、ならびにＭＡＰとＣＰＥの間のＶＰＮトンネリングを円滑にするための少なくとも１つのＩＰサービス・ゲートウェイ（ＩＰＳＧ）（２０６）を特定する工程（７０２〜７０６）であって、
各ＭＡＰが、各ＩＰＳＧから地理的に遠隔である工程（７０２〜７０６）と、
選択されたＩＰＳＧ上でＶＰＮ顧客のサブセットにサービス提供を行うことからもたらされる総利益（９２０）を最大化するようにＩＰＳＧのサブセットを選択する工程（７０８〜７１４）であって、
すべての顧客からの前記総利益が、各顧客（ｌ）からの利益の合計（９１８）を含み、ただし、各顧客利益（Ｕｌ）が、重み付けされた収益（γＶｌ）から費用（Ｃｌ）を引いた結果（Ｕｌ＝γＶｌ−Ｃｌ）に等しく、１つの顧客当たりの前記費用が、前記ＭＡＰから前記ＣＰＥまでの総トンネル帯域幅費用（ＣｌＣ）（９１２）、およびＩＰＳＧノードを配置する（ｐｒｏｖｉｓｉｏｎ）費用（ＣｌＶ）（９１４）を含み、γが、顧客１に関する総費用と比べた収益の相対的重みを表す工程（７０８〜７１４）とを含む方法。
【請求項２】
前記総トンネル帯域幅費用が、前記ＭＡＰと前記配置された（ｐｒｏｖｉｓｉｏｎｅｄ）ＩＰＳＧの間の動的トンネル帯域幅費用（９０８）、および前記配置されたＩＰＳＧと前記ＣＰＥの間の静的帯域幅費用（９１０）を含み、複数のＭＡＰからのトラフィックが前記配置されたＩＰＳＧを経由して前記ＣＰＥに達する事例中でも、前記配置されたＩＰＳＧと前記ＣＰＥの間で単一のトンネルしか確立されない請求項１に記載の方法。
【請求項３】
前記配置されたＩＰＳＧが複数のＣＰＥにトラフィックを送信する事例において、前記サービス提供費用が１回だけカウントされる請求項１に記載の方法。
【請求項４】
１つの顧客ｌ当たりの前記費用（９１６）が、
【数１】
2004260833.tif 000039
によって算出され、ただし、ｃｌｉｊが、ＭＡＰノードｉからＩＰＳＧノードｊにトラフィックを送信することに関連する帯域幅費用（９０４）であり、ｄｌｊｋが、前記ＩＰＳＧノードｊから前記ＣＰＥノードｋにトラフィックを送信することに関連する帯域幅費用（９０６）であり、βが、前記共用静的トンネルに関する重み付け係数を表し、ｆｊが、前記ＩＰＳＧノードｊを使用することに関連するサービス提供費用であり、ｙｌｊが、サービス提供を受ける顧客が自らのＣＰＥの少なくとも１つにトラフィックを送信するのにＩＰＳＧ  ｊが用意されている（ｐｒｏｖｉｓｉｏｎｅｄ）かどうかを表す２値変数であり、αが、総帯域幅費用に上乗せしたサービス提供費用に関する重み付け係数である請求項１に記載の方法。
【請求項５】
ＭＡＰノードｉからＩＰＳＧノードｊにトラフィックを送信することに関連する前記帯域幅費用（ｃｌｉｊ）（９０４）が、前記ＭＡＰノードｉと前記ＩＰＳＧノードｊの間の単位帯域幅費用（ａｉｊ）と、ＩＰＳＧノードｊを経由して前記ＭＡＰノードｉから前記ＣＰＥノードｋに向かわせられるトラフィックの合計
【数２】
2004260833.tif 000040
の積を含み、ＩＰＳＧノードｊからＣＰＥノードｋにトラフィックを送信することに関連する前記帯域幅費用（ｄｌｊｋ）（９０６）が、前記ＩＰＳＧノードｊと前記ＣＰＥノードｋの間の単位帯域幅費用（ｅｌｊｋ）と、ＩＰＳＧノードｊを経由してＭＡＰノードｉから前記ＣＰＥノードｋに向かわせられるトラフィックの総量
【数３】
2004260833.tif 000041
の積を含む請求項４に記載の方法。
【請求項６】
ＭＡＰノードｉから前記ＩＰＳＧノードｊへのトラフィックの前記総量
【数４】
2004260833.tif 000042
が、前記ＭＡＰノードｉと前記ＩＰＳＧノードｊの間の総帯域幅容量（ｇｉｊ）以下であり、前記ＩＰＳＧノードｊから前記ＣＰＥノードｋへのトラフィックの前記総量
【数５】
2004260833.tif 000043
が、前記ＩＰＳＧノードｊと前記ＣＰＥノードｋの間の総帯域幅容量（ｈｌｊｋ）以下である請求項４に記載の方法。
【請求項７】
１組の仮想プライベート・ネットワーク（ＶＰＮ）顧客（２２０）、各ＶＰＮ顧客（２２０）に関連する少なくとも１つのモバイル・アクセス・ポイント（ＭＡＰ）（２０８）および少なくとも１つの顧客構内機器（ＣＰＥ）（２２２）、ならびにＭＡＰとＣＥＰの間のＶＰＮトンネリングを円滑にするための少なくとも１つのＩＰサービス・ゲートウェイ（ＩＰＳＧ）（２０６）を特定するための手段であって、
各ＭＡＰが、各ＩＰＳＧから地理的に遠隔である手段と、
選択されたＩＰＳＧ上でＶＰＮ顧客のサブセットにサービス提供を行うことからもたらされる総利益（９２０）を最大化するようにＩＰＳＧのサブセットを選択するための手段（７０８〜７１４）であって、
すべての顧客からの前記総利益が、各顧客（ｌ）からの利益の合計（９１８）を含み、ただし、各顧客利益（Ｕｌ）が、重み付けされた収益（γＶｌ）から費用（Ｃｌ）を引いた結果（Ｕｌ＝γＶｌ−Ｃｌ）に等しく、１つの顧客当たりの前記費用が、前記ＭＡＰから前記ＣＰＥまでの総トンネル帯域幅費用（ＣｌＣ）（９１２）、およびＩＰＳＧノードを配置する（ｐｒｏｖｉｓｉｏｎ）費用（ＣｌＶ）（９１４）を含み、γが、顧客１に関する総費用と比べた収益の相対的重みを表す手段（７０８〜７１４）とを含む仮想プライベート・ネットワーク（ＶＰＮ）システム・アーキテクチャ。
【請求項８】
ＶＰＮ顧客（２２０）のサブセットの顧客構内機器（ＣＰＥ）（２２２）と少なくとも１つのモバイル・アクセス・ポイント（ＭＡＰ）（２０８）の間で仮想プライベート・ネットワーク（ＶＰＮ）トンネリングをサポートする複数のＩＰサービス・ゲートウェイ（ＩＰＳＧ）のそれぞれを用意する（ｐｒｏｖｉｓｉｏｎ）工程（３０２〜３１４）を含む方法であって、
前記ＭＡＰのそれぞれが、前記複数のＩＰＳＧから地理的に遠隔であり、ＶＰＮ顧客の前記サブセットのモバイル・ノード（２３０）までのＶＰＮトンネリングをサポートする方法。
【請求項９】
各顧客に関して、選択されたＩＰＳＧ上で前記顧客にサービス提供を行うことからもたらされる総利益（５０２〜５１０）を最大化するようにＩＰＳＧのサブセットを選択する工程をさらに含む方法であって、
すべての顧客からの前記総利益（５１０〜５１２）が、各顧客からの利益の合計を含み、ただし、各顧客に関して、利益（Ｇ）が重み付けされた収益（γＲ）から費用（Ｃ）を引いた結果に等しく（Ｇ＝γＲ−Ｃ）、
１つの顧客当たりの前記費用（５０８〜５１２）が、前記ＭＡＰから前記ＣＰＥまでの総トンネル接続費用（ＣＣ）、およびＩＰＳＧノードを用意する（ｐｒｏｖｉｓｉｏｎ）ことの現在の費用（ＣＶ）を含み、１つの顧客当たりの前記費用が、
【数６】
2004260833.tif 000044
によって算出され、ただし、Ｃｉｊ（５０２）が、ＭＡＰノードｉからＩＰＳＧノードｊにトラフィックを送信することの費用であり、Ｘｉｊｋが、ＭＡＰ  ｉからＣＰＥノードｋへのトラフィックに関してＭＡＰ  ｉからＩＰＳＧ  ｊまでの動的トンネルが確立されるかどうかを表す２値変数（５０４）であり、ｄｊｋが、前記ＩＰＳＧノードｊから前記ＣＰＥノードｋにトラフィックを送信することの費用（５０６）であり、ｚｊｋが、ＩＰＳＧノードｊからＣＰＥノードｋまでの共用静的トンネルが確立されるかどうかを表す２値変数（５１６）であり、βが、前記共用静的トンネルに関する重み付け係数（５０８）を表し、ｆｊが、前記ＩＰＳＧノードを使用したサービス提供費用（５０２）であり、ｙｊが、サービス提供を受ける顧客が自らのＣＰＥの少なくとも１つにトラフィックを送信するのに前記ＩＰＳＧ  ｊが用意されるかどうかを表す２値変数（５１６）であり、αが、総接続費用（５１２）に上乗せされたサービス提供費用に関する重み付け係数である請求項８に記載の方法。
【請求項１０】
ＶＰＮ顧客（２２０）のサブセットの顧客構内機器（ＣＰＥ）（２２２）と少なくとも１つのモバイル・アクセス・ポイント（ＭＡＰ）（２０８）の間でＶＰＮトンネリングを前記ＩＰＳＧのそれぞれがサポートする複数のＩＰサービス・ゲートウェイ（ＩＰＳＧ）（２０６）を含む仮想プライベート・ネットワーク（ＶＰＮ）システム・アーキテクチャ（２００）であって、
前記ＭＡＰのそれぞれが、前記ＩＰＳＧから地理的に遠隔であり、前記少なくとも１つのＭＡＰが、ＶＰＮ顧客の前記サブセットの対応するＩＰＳＧとモバイル・ノード（ＭＮ）（２３０）の間のＶＰＮトンネリングをサポートするアーキテクチャ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想プライベート・ネットワーク（ＶＰＮ）サービスに関する。より具体的には、本発明は、ＶＰＮサービスを利用してモバイル・デバイスに接続を提供するためのサービスに関する。
【背景技術】
【０００２】
（相互参照）
本出願は、参照により内容の全体が本明細書に組み込まれている２００３年２月２６日に出願した、本出願と同じ所有者に所有される米国特許出願第１０／３７４，９４０号の一部継続出願であり、同出願の優先権を主張する。
【０００３】
仮想プライベート・ネットワーク（ＶＰＮ）は、共用される公共データ網にわたって企業ネットワーク・リソースを拡張する費用対効果が高く、セキュアなやり方である。ＶＰＮの最も一般的な用途は、企業の複数の地理的に分散した拠点を互いに接続すること（イントラネット／エクストラネットＶＰＮとして知られる）、および企業リソースに対するアクセスを遠隔ユーザに提供すること（遠隔アクセスＶＰＮとして知られる）である。詳細には、仮想プライベート・ネットワーク（ＶＰＮ）は、トンネリング・プロトコルおよびセキュリティ手続きの使用を介してプライバシーを保って企業の拠点とユーザの間でデータ・トラフィックを伝送するために公共ネットワークを使用するオーバーレイ・ネットワークである。
【０００４】
ネットワーク・ベースのＶＰＮモデルでは、イントラネット／エクストラネットＶＰＮが、企業の顧客構内機器（ＣＰＥ）を企業顧客に用意された１つまたは複数のＶＰＮ認識ネットワーク要素と互いに接続することによって生成される。遠隔アクセスＶＰＮが、ユーザが属する企業顧客に用意されたＶＰＮ認識ネットワーク要素まで遠隔ユーザの接続をトンネリングすることによって生成される。ＶＰＮ認識ネットワーク要素は、次に、トンネル連結を使用して、その接続を適切なＣＰＥまでトンネリングする。１つのそのようなＶＰＮ認識ネットワーク要素が、ＩＰサービス・ゲートウェイ（ＩＰＳＧ）と呼ばれるサービス・スイッチである。ＩＰＳＧは、それぞれが数名のエンド・ユーザを有するいくつかの企業ＶＰＮ顧客にサービスを提供することができる。
【０００５】
ユーザまたは拠点からセキュアな企業リソースまでＶＰＮをセットアップする基本的な方法は、基礎にあるセキュアでない共用ネットワーク上で両者の間にセキュアなデータ接続をセットアップすることである。ＩＰＳＧは、通常、ユーザ／拠点からＩＰＳＧ自体までのトンネルと、ＩＰＳＧから企業までの別のトンネルの２つのセキュアなトンネルをセットアップする。また、ＩＰＳＧは、両終端、すなわち、ユーザ／拠点および企業との別個の独立したセキュリティ関連を維持することも担う。データは、ＩＰＳＧを介して連結されたトンネルを通って終端間で流れる。ネットワーク・ベースのＶＰＮモデルでは、ネットワークは、単に管路として作用するだけでなく、ＶＰＮサービスも可能にすることに留意されたい。さらに、ＩＰＳＧは、トンネル連結ポイントからの他の付加価値サービスも可能にすることができる。例には、ＶＰＮトンネルに関するより良好なＱｏＳ保証、ユーザ間のサービス差別化、企業イントラネットからインターネット・トラフィックの負担を軽減すること等が含まれる。
【０００６】
ＩＰＳＧサービス提供（ｐｒｏｖｉｓｉｏｎｉｎｇ）プロセスにより、ＩＰＳＧにおいて円滑にされる顧客のそれぞれに関する経路指定機構の仮想インスタンスが生成される。可能な一実施形態では、各インスタンスは、顧客特有の経路指定アルゴリズムを実行する別個の（仮想）ルータであることが可能である。他の実施形態では、各インスタンスは、区分化された経路指定テーブルにおける別々の顧客特有の経路エントリであることが可能である。このため、各経路指定インスタンスは、相当な量のコンピューティング・リソースを必要とする。さらに、すべてのインスタンスがＩＰＳＧの共有リソースを共用するので、ＩＰＳＧ上でサービス提供が行われることが可能なＶＰＮ顧客の数が制限される。ＩＰＳＧがサポートすることができるトンネルの数にも同様の制約が課せられている。さらに、物理リソース制約に起因して、より多くの設定（ｐｒｏｖｉｓｉｏｎ）を伴ってＩＰＳＧを構成することにより、扱うことができるトンネルの数が少なくなり、その逆も同様である。顧客ごとのＩＰＳＧサービス提供は、このプロセスの複雑さのために、通常、静的に行われ、ＩＰＧＳ設定は、頻繁には変更されない。
【０００７】
現在、遠隔アクセスＶＰＮは、大方、ダイヤルアップ線、ＤＳＬ線、およびケーブル−モデム線などの有線アクセスを使用して遠隔の場所から企業に接続するエンド・ユーザに限定されている。第２．５世代無線技術および第３世代無線技術における高速無線データ・サービスの出現とともに、モバイル・ノードからのＶＰＮ使用（つまり、モバイルＶＰＮサービス）が、急激に増大している。
【０００８】
モバイル・データ・サービスを可能にするため、ネットワーク・サービス・プロバイダ（ＮＳＰ）は、自らのネットワークの端部に無線アクセス・デバイスを設置する。無線−パケット網間ゲートウェイ（すなわち、モバイル・アクセス・ポイント（ＭＡＰ））が、アクセス・デバイスをデータ網に接続する。データ・セッションをセットアップするのに、モバイル・エンド・ユーザ（以降、「モバイル・ノード」（ＭＮ）と呼ぶ）はまず、ＭＡＰに接続しなければならず、次に、ＭＡＰが、適切に設定された（ａｐｐｒｏｐｒｉａｔｅｌｙ  ｐｒｏｖｉｓｉｏｎｅｄ）ＩＰＳＧを介して宛先ＣＰＥに向けてセッションを経路指定する。ＭＮを起点としてＭＡＰに至り、ＩＰＳＧを経由して企業ＣＰＥに至るモバイル・データ・セッションが、ネットワーク・ベースのモバイルＶＰＮサービスの基礎である。現在、ＩＰＳＧとＭＡＰは、ネットワーク内で並置され、ＩＰＳＧ／ＭＡＰは、無線−パケット網間ゲートウェイ機能を行ってＭＮの接続を終端させるとともに、その他のＩＰＳＧ特有の機能も行う。
【０００９】
図１は、従来技術のモバイルＩＰネットワーク１００の高レベル・ブロック図を描いている。このようなシナリオでは、ＭＮには、ＩＰＳＧを選択する自由がなく、代わりに、ＭＮのデータ・セッションは、ＭＮが現在、ローミングしている区域にサービスを提供するＩＰＳＧに引留（ａｎｃｈｏｒ）される。ＶＰＮサービスは、ＭＮがデータ・セッションを開始して初めて、開始されることが可能になることに留意されたい。
【００１０】
例示的なネットワーク１００は、インターネットなどのバックボーン・ネットワーク１０２、複数の企業ネットワーク１２０１乃至１２０ｒ（まとめて企業ネットワーク１２０）、およびネットワーク・サービス・プロバイダ（ＮＳＰ）１０１を含む。企業ネットワーク１２０はそれぞれ、少なくとも１つの顧客構内機器（ＣＰＥ）１２２、および複数のモバイル・ノード（ＭＮ）１３０１乃至１３０ｍ（まとめてＭＮ１３０）を含む。この例では、対応するイントラネット拠点１２０をそれぞれが有する３つのＶＰＮ顧客Ａ、Ｂ、およびＣが存在する。顧客Ａは、２つのＣＰＥ１２２１１および１２２１２を有し、他方、顧客ＢおよびＣはそれぞれ、１つのＣＰＥ１２２２１および１２２ｒｋを有する。
【００１１】
ＮＳＰ１０１は、複数のＩＰＳＧ１０６１乃至１０６ｑ（まとめてＩＰＳＧ１０６）を有するネットワーク・サービス・プロバイダ・アクセス網１０４を含む。図１に示すとおり、ＩＰＳＧ１  １０６１が、顧客Ａ  １２０１に用意され、ＩＰＳＧ２  １０６２が、顧客Ｂ  １２０２およびＣ  １２０ｒ（ここでｒは、例として、３に等しい）に用意され、ＩＰＳＧ３  １０６３が、３つすべての顧客Ａ  １２０１、Ｂ  １２０２、およびＣ  １２０３に用意されているという具合である。これは、ＩＰＳＧ１  １０６１が顧客Ａに関する経路指定インスタンス、ならびにＣＰＥＡ１  １２２１１およびＣＰＥＡ２  １２２１２とのセキュリティ関連を有することを暗黙に示す。セキュリティ関連は、ＩＰＳＧ１  １０６１と顧客Ａに関するＣＰＥの間でセキュアにパケットをトンネリングするのに使用される（つまり、顧客Ａに関するＣＰＥは、あらかじめ確立されたセキュアなトンネルを有する）。同様な関連が、他のＩＰＳＧに関しても成り立つ。顧客Ａに属するＭＮ１３０１がＩＰＳＧ１  １０６１によるサービスを受ける区域にローミングした場合、そのＭＮは、ＩＰＳＧ１  １０６１と成功裡にデータ・セッションを開始する。その後、ＭＮは、ＣＰＥＡ１  １２２１１に対するＶＰＮ接続を要求する。ＩＰＳＧ１は、ＭＮ１３０１とＩＰＳＧ１  １０６１の間でセキュアなトンネルを構築し、例としてＩＰＳＧ１  １０６１とＣＰＥＡ１  １２２１１の間であらかじめ確立されたトンネルにそのトンネルを連結することにより、その要求に応える。
【００１２】
その後、このＭＮ１３０１がＩＰＳＧ２  １０６２によるサービスを受ける区域にローミングした場合、ＩＰＳＧ２  １０６２とデータ・セッションが再確立される。ただし、ＭＮがＶＰＮサービスを要求した際、ＩＰＳＧ２  １０６２は、そのようなＶＰＮサービスを提供することができない。とうのは、ＩＰＳＧ２  １０６２は、顧客Ａに合わせて設定されて（ｐｒｏｖｉｓｉｏｎｅｄ）いないからである。つまり、ＩＰＳＧ２  １０６２は、セキュアな仕方でＣＰＥＡ１  １２２１１に論理接続されていない。後に、このＭＮがＩＰＳＧ３  １０６３によるサービスを受ける区域にローミングした場合、再びＩＰＳＧ３  １０６３とデータ・セッションが再確立される。ＭＮ１３０１がＶＰＮサービスを要求した場合、ＩＰＳＧ３  １０６３は、そのＶＰＮセッションを提供することができる。というのは、ＩＰＳＧ３  １０６３は、顧客Ａに合わせて設定されている（ｐｒｏｖｉｓｉｏｎｅｄ）からである。
【００１３】
現在、「一様サービス提供（ｐｒｏｖｉｓｉｏｎ）」と呼ばれる１つの解決策では、ＩＰＳＧ、ＩＰＳＧ１  １０６１、ＩＰＳＧ３  １０６３、およびＩＰＳＧ５  １０６ｑ＝５に加えて、ＮＳＰは、ＩＰＳＧ２  １０６２およびＩＰＳＧ４  １０６４も顧客Ａに用意する。第１の一様サービス提供解決策は、ネットワーク内のすべてのＩＰＳＧ１０６が、ＮＳＰのすべての顧客に用意されることを暗黙に示す。これは、ユーザの移動性のために、つまり、任意の顧客に属するＭＮが、任意のＩＰＳＧ１０６によるサービスを受ける区域にローミングし、サービスを要求する可能性があるために必要とされる。したがって、顧客のサブセットだけにしかサービスを提供しないことを先験的に前提とすることができるＩＰＳＧ１０６は存在しない。
【００１４】
例えば、ＮＳＰが「Ｎ」個のＩＰＳＧを有し、それぞれが、最大で「Ｍ」個の異なるサービス提供をサポートすることができるものと想定する（ＩＰＳＧごとにサービス提供が行われることが可能なＶＰＮ顧客の数は制限されていることを想い起こされたい）。したがって、ＮＳＰ１００が提供することができる異なるサービス提供の総数は、Ｍ×Ｎである。ただし、この解決策では、各ＩＰＳＧ１０６が、すべてのＶＰＮ顧客に対してまったく同じ仕方で設定されなければならない。実際には、すべてのＶＰＮ顧客に、すべてのＩＰＳＧ１０６上でサービス提供が行われなければならず、これにより、サポートされるＶＰＮ顧客の総数がＭ個だけに制限される。したがって、この接続解決策は、加入済みＶＰＮ顧客の数に合わせて拡張されない。ただし、これは、自宅ＶＰＮおよびイントラネット／エクストラネットＶＰＮからの遠隔アクセスＶＰＮなどの非モバイルのＶＰＮサービスに関しては問題ではない。というのは、ＮＳＰは、いずれの顧客がいずれのＩＰＳＧに接続するかを先験的に知っており（顧客の地理的場所から）、関連するサブセットのＶＰＮ顧客だけを有するようにＩＰＳＧを静的に設定する（ｐｒｏｖｉｓｉｏｎ）ことができるからである。
【００１５】
「トンネル切替え」と呼ばれる第２の解決策は、ＩＰＳＧが、顧客のサブセットに用意されることを可能にする。例えば、ＩＰＳＧ２  １０６２が、ＩＰＳＧ１  １０６１のような顧客Ａに用意されたＩＰＳＧにＭＮのデータ・セッションをトンネリングする。トンネル切替え解決策は、各ＩＰＳＧ１０６が、その他のＩＰＳＧによって行われるサービス提供を認識し、ＭＮの身元を検出し、セッションを適切なＩＰＳＧ１０６にトンネル切替えすることを必要とする。あるケースでは、この方法は、ＭＮ１３０を適切に設定されたＩＰＳＧ１０６に接続するのに複数のトンネルを使用する結果になることに留意されたい。
【００１６】
第２のトンネル切替え解決策は、各ＩＰＳＧがＶＰＮ顧客のサブセットを有するように設定し（ｐｒｏｖｉｓｉｏｎ）、ＭＮがローミングする区域内のＩＰＳＧから適切に設定されたＩＰＳＧにＭＮのデータ・セッションをトンネル切替えすることを介して移動性をサポートする。つまり、トンネル切替え解決策は、エンド・ユーザを適切なＩＰＳＧ１０６に接続するのに２つまたはそれより多くトンネルを使用することにより、接続を維持する。
【００１７】
ＭＮ−ＩＰＳＧ−ＣＰＥ接続を提供するためのトンネル切替えの第２の解決策は、より多くのＶＰＮ顧客を扱うためにＩＰＳＧがより多くのトンネルをサポートしなければならず、これにより、ＩＰＳＧ１０６ごとに行うことができるサービス提供の数が少なくなるため、拡張性がない。さらに、ＩＰＳＧの間でトンネル切替えを行うことにより、ＮＳＰネットワーク内で接続の望ましくない宛先変更がもたらされ（通常、「ドッグレッグ化（ｄｏｇ−ｌｅｇｇｉｎｇ）」として知られる）、これにより、ネットワーク・リンクの非効率な使用がもたらされる。
【特許文献１】米国特許出願第１０／３７４，９４０号
【発明の開示】
【発明が解決しようとする課題】
【００１８】
従来の技術に関連する従来の欠点が、ネットワーク・ベースのモバイル仮想プライベート・ネットワーク（ＶＰＮ）サービスにおいて接続を最適に提供するための方法および装置の本発明によって克服される。装置は、サブセットのＶＰＮ顧客の顧客構内機器と少なくとも１つのモバイル・アクセス・ポイント（ＭＡＰ）の間で仮想プライベート・ネットワーク（ＶＰＮ）トンネリングをサポートする複数のＩＰサービス・ゲートウェイ（ＩＰＳＧ）のそれぞれを設置する（ｐｒｏｖｉｓｉｏｎ）ことを含む。ＭＡＰは、複数のＩＰＳＧから地理的に遠隔であり、ＭＡＰのそれぞれが、サブセットのＶＰＮ顧客のモバイル・ノードに対するＶＰＮトンネリングをサポートする。
【課題を解決するための手段】
【００１９】
一実施形態では、第１の方法は、各顧客に関して、選択されたＩＰＳＧ上で顧客にサービス提供を行うことからもたらされる総利益を最大化するようにＩＰＳＧのサブセットを選択することを含み、すべての顧客からの総利益は、各顧客からの利益の合計を含み、各顧客利益（Ｇ）は、重み付けされた収益から費用を引いたものに等しい。重み付けされた収益は、収益、および費用と比べた収益に対する相対重み係数γを含み、だだし、γは、ネットワーク・サービス・プロバイダが、顧客の費用に基づいて価格を調整することを可能にする。さらに、顧客当たりの費用は、ＭＡＰからＣＰＥまでの総トンネル接続費用、およびＩＰＳＧノードを設置する（ｐｒｏｖｉｓｉｏｎ）現在の費用を含み、総トンネル接続費用は、ＭＡＰと設置されたＩＰＳＧの間の動的トンネル接続費用、および設置されたＩＰＳＧとＣＰＥの間の静的トンネル接続費用を含む。
【００２０】
第２の実施形態では、ネットワーク・ベースのモバイルＶＰＮサービスにおいて帯域幅保証されたサービス提供を提供するための方法、および仮想プライベート・ネットワーク（ＶＰＮ）システム・アーキテクチャが提供される。方法およびシステム・アーキテクチャは、１組のＶＰＮ顧客、少なくとも１つのモバイル・アクセス・ポイント（ＭＡＰ）、および各ＶＰＮ顧客に関連する少なくとも１つの顧客構内機器（ＣＰＥ）、ならび各ＭＡＰが各ＩＰＳＧから地理的に遠隔であるＭＡＰとＣＰＥの間でＶＰＮトンネリングを円滑にするための少なくとも１つのＩＰサービス・ゲートウェイ（ＩＰＳＧ）を特定することを含む。ＩＰＳＧのサブセットが、選択されたＩＰＳＧ上でＶＰＮ顧客のサブセットにサービス提供を行うことからもたらされる総利益を最大化するように選択される。すべての顧客からの総利益は、各顧客（ｌ）からの利益の合計を含み、ただし、各顧客に関して、利益（Ｕｌ）は、重み付けされた収入（γＶｌ）から費用（Ｃｌ）を引いたものに等しく（Ｕｌ＝γＶｌ−Ｃｌ）、顧客当たりの費用は、ＭＡＰから前記ＣＰＥまでの総トンネル帯域幅費用（Ｃｌｃ）、およびＩＰＳＧノードを設置する（ｐｒｏｖｉｓｉｏｎ）費用（Ｃｌｖ）を含む。
【００２１】
本発明の教示は、添付の図面と併せて以下の詳細な説明を考慮することにより、容易に理解することができる。
【発明を実施するための最良の形態】
【００２２】
理解を容易にするため、可能な場合、図に共通する同一の要素を示すのに同一の符号を使用している。
本発明は、モバイル仮想プライベート・ネットワーク（ＶＰＮ）に関する階層式ネットワーク・アーキテクチャにおいてＶＰＮ認識デバイスを提供するための方法および装置を提供する。本明細書で説明する方法は、ＶＰＮトンネルが確立されるリンクの費用、トンネルを確立する費用、ＩＰサービス・ゲートウェイ（ＩＰＳＧ）などのＶＰＮ認識デバイス上でＶＰＮ顧客にサービス提供を行う費用、および耐障害性のためのＩＰＳＧサービス提供の冗長性を考慮に入れる。
【００２３】
図２は、本発明の例示的なモバイルＩＰネットワーク２００の高レベル・ブロック図を描いている。例示的なネットワーク２００は、インターネットなどのバックボーン・ネットワーク２０２、複数の企業ネットワーク２２０１乃至２２０ｒ（まとめて、企業ネットワーク２２０）、サービス・プロバイダ２０１（例えば、ネットワーク・サービス・プロバイダ（ＮＳＰ））、および複数のモバイル・ノード（ＭＮ）２３０１乃至２３０ｍ（まとめてＭＮ２３０）を含む。
【００２４】
企業ネットワーク２２０は、少なくとも１つの顧客構内機器２２２をそれぞれが有するイントラネット／エクストラネット・ネットワークであることが可能である。この例では、対応するイントラネット拠点２２０をそれぞれが有する３つのＶＰＮ顧客Ａ、Ｂ、およびＣが存在する。顧客Ａは、２つのＣＰＥ２２２１１および２２２１２を有し、他方、顧客ＢおよびＣはそれぞれ、１つのＣＰＥ２２２２１および２２２ｒｋを有する。ＣＰＥ２２２は、通常、他の従来の顧客ネットワーク機器のなかでもとりわけ、顧客エッジ・ルータ、または層２トンネリング・プロトコル（Ｌ２ＴＰ）ネットワーク・サーバを含む。
【００２５】
サービス・プロバイダ２０１は、複数のＩＰサービス・ゲートウェイ（ＩＰＳＧ）２０６１乃至２０６ｑ（まとめてＩＰＳＧ２０６）、ならびにＩＰＳＧ２０６とは別の離れた、ネットワーク２０４の端部に位置する複数の無線アクセス・デバイス２０８を有するネットワーク・サービス・プロバイダ・アクセス網２０４を含む。つまり、モバイル・データ・サービスを可能にするため、ＮＳＰ２０１は、自らのネットワーク２０４の端部に無線アクセス・デバイス２０８を設置する。
【００２６】
一実施形態では、無線アクセス・デバイス２０８は、アクセス・デバイスをデータ網に接続するのに使用される、以降、モバイル・アクセス・ポイント（ＭＡＰ）と呼ぶ無線−パケット網間ゲートウェイである。したがって、ＣＤＭＡ２０００アーキテクチャにおけるパケット・データ・サービス提供（ｓｅｒｖｉｎｇ）ノード（ＰＤＳＮ）、またはＵＭＴＳアーキテクチャにおけるゲートウェイＧＰＲＳサポート・ノード／サービス提供ＧＰＲＳサポート・ノード（ＧＧＳＮ／ＳＧＳＮ）が、ＭＡＰの役割をすることが可能である。データ・セッションをセットアップするのに、モバイル・ノード（ＭＮ）２３０を利用するモバイル・エンド・ユーザはまず、ＭＡＰ２０８に接続しなければならず、次に、ＭＡＰが、適切に設定された（ｐｒｏｖｉｓｉｏｎｅｄ）ＩＰＳＧを介して宛先ＣＰＥに向けてそのセッションを経路指定する。したがって、ネットワーク・ベースのモバイルＶＰＮサービス・モバイル・データ・セッションは、ＭＮ２３０を起点としてＭＡＰ２０８に至り、次に、特定のＩＰＳＧ２０６を経由して企業ＣＰＥ２２２に至る。
【００２７】
図２のネットワーク・ベースのＶＰＮアーキテクチャでは、ＭＡＰ２０８は、ＩＰＳＧ２０６とは別個に、階層式に配置される。詳細には、ＭＡＰ２０８は、ある区域にサービスを提供し、その区域内のすべてのＭＮ２３０は、顧客関連に関わらず、データ・セッションを開始するのにＭＡＰ２０８に接続する。各ＩＰＳＧ２０６は、企業ＶＰＮ顧客のサブセットだけに関して静的に設定される（ｐｒｏｖｉｓｉｏｎｅｄ）。ＩＰＳＧ２０６ごとのサブセットは、各顧客に少なくとも１つのＩＰＳＧが用意される（ｐｒｏｖｉｓｉｏｎｅｄ）ように選択される。
【００２８】
図２の例示的な実施形態では、ＩＰＳＧ１  ２０６１およびＩＰＳＧ５  ２０６ｑ＝５がＶＰＮ顧客Ａ  ２２０１に用意され、ＩＰＳＧ２  ２０６２、ＩＰＳＧ３  ２０６３、およびＩＰＳＧ４  ２０６４が、ＶＰＮ顧客Ｂ  ２２０２に用意されている。同様に、ＩＰＳＧ２  ２０６２およびＩＰＳＧ５  ２０６５がＶＰＮ顧客Ｃ  ２２０ｒ＝３に用意されている。顧客Ａを宛先とするモバイル・トラフィックは、ＭＮ２３０の位置に依存して、ＭＡＰ２０８によってＩＰＳＧ１  ２０６１またはＩＰＳＧ５  ２０６５に向かわせられる。各ＩＰＳＧ２０６は、３つのＶＰＮ顧客２２０のサブセットをサポートするだけでよい。
【００２９】
ＩＰＳＧは、仮想経路指定インスタンス、およびサービス提供を受ける各ＶＰＮ顧客２２０とのセキュリティ関連を維持する。各ＭＡＰ２０８は、顧客−ＩＰＳＧ間マッピングの単純でかなり静的なリストを保持する。このリストは、新規の顧客２２０がＮＳＰによって提供されるＶＰＮサービスに加入した場合にだけ変更され、そのような場合は、非常に稀であることに留意されたい。ＭＮ２３０がそれぞれのＣＰＥ２２２に対するＶＰＮ接続を要求した際、ＭＡＰ２０８は、ＭＮが属する顧客を特定し、その顧客に用意された適切なＩＰＳＧ２０６にその接続を経路指定し、かつ／またはトンネル切替えする。
【００３０】
詳細には、ＭＮ２３０は、例えば、従来のネットワーク・アクセス識別子（ＮＡＩ）および／またはアクセス・ポイント名（ＡＰＮ）を使用して特定される。ＭＡＰは、ＭＮとの接続セットアップ時中にＭＮ２３０のＮＡＩ／ＡＰＮを抽出する。ＭＡＰは、１つのＣＰＥ２２２だけしか存在しない場合、ＮＡＩ／ＡＰＮから直接に宛先ＣＰＥ２２２を特定することができる。複数のＣＰＥ２２２が存在する場合、ＭＡＰは、サービス・プロバイダ２０１の認証−許可−アカウンティング（ＡＡＡ）サーバからＭＮ２３０の選好するＣＰＥ２２２を特定することができる。
【００３１】
例示として、顧客Ａに属するＭＮ２３０１がＭＡＰ１  ２０８１によるサービスを受ける区域内にローミングした場合、ＭＡＰ２０８１は、ＭＮ２３０１が属する顧客を特定し、その顧客に用意された適切なＩＰＳＧ２０６に接続を経路指定し、かつ／またはトンネル切替えする。この例では、接続は、ＩＰＳＧ１  ２０６１に経路指定される。ＩＰＳＧ１  ２０６１は、ＭＮ２３０１とＩＰＳＧ１  ２０６１の間でセキュアなトンネルを構築し、ＩＰＳＧ１  ２０６１と、例えば、ＣＰＥＡ１  ２２２１１の間であらかじめ確立されたトンネルにそのトンネルを連結することにより、その要求に応える。
【００３２】
ＭＮ２３０１が、ＭＡＰ２  ２０６２によるサービスを受ける区域内にローミングした場合、接続もＩＰＳＧ１  ２０６１に経路指定される。同様に、ＭＮ２３０１が、ＭＡＰ３  ２０６３またはＭＡＰ４  ２０６４によるサービスを受ける領域内にローミングした場合、接続も、ＩＰＳＧ１  ２０６１またはＩＰＳＧ５  ２０６ｑ＝５に経路指定される（図２に接続を示していない）。
【００３３】
したがって、本発明の一態様は、ＭＡＰ２０８がユーザの移動性に対処する一方で、ＩＰＳＧ２０６がＶＰＮサービスを提供してサービスから移動性を分離することである。これは、機能の自然な分割である。というのは、ＩＰＳＧは、静止した場所に関するサービスをサポートするように設計されており、他方、ＭＡＰは、動的な切替えおよび経路指定を提供することによって移動性を扱うように設計されているからである。
【００３４】
前述の手法は、ＭＮ−ＩＰＳＧ−ＣＰＥ接続問題に関する拡張性の問題を解決する。サービス提供における拡張性には、すべての顧客に関して少なくとも１つのサービス提供が存在するようにＩＰＳＧごとにＶＰＮ顧客のサブセットを割り振ることによって対処が行われる。各顧客にすべてのＩＰＳＧ上でサービス提供が行われなければならない既存のアーキテクチャと比べて、階層式手法は、当然、より高い拡張性を提供する。トンネル切替え、および関連するドッグレッグ化は、ＩＰＳＧ２０６に対してＭＡＰ２０８を別個に、階層式に配置することによって解決される。この階層式設計では、ＭＡＰ２０８は、トンネル切替え／トラフィック宛先変更機能を提供する。したがって、ＭＡＰ２０８は、インターネット・トラフィックからイントラネットＶＰＮトラフィックを分離し、ＶＰＮトラフィックを適切なＩＰＳＧ２０６に向かわせ、インターネット・トラフィックをＮＳＰネットワーク２０４内の適切なインターネット・プロキシに向かわせることができる。この付加価値のインターネット・トラフィック負荷を減らすサービスにより、ＭＡＰ２０８とＩＰＳＧ２０６が並置された既存のアーキテクチャと比べて、ＮＳＰ２０１、および顧客のための帯域幅が効果的に節約される。
【００３５】
したがって、ＮＳＰネットワーク接続を確立するため、各ＶＰＮ顧客が、ＩＰＳＧ２０６のサブセットにマップされる。１つの解決策は、１つのＩＰＳＧ２０６上にできる限り多くの顧客をマップ／設定し（ｐｒｏｖｉｓｉｏｎ）、現在のＩＰＳＧ２０６がいっぱいになった場合にだけ、第２のＩＰＳＧ２０６を使用することである。ただし、この技術は、リソースを十分に利用しない。つまり、この技術は、ホット・スポットを生じさせ、ネットワークの全体的な性能を低下させる。
【００３６】
代替として、本発明の実施形態では、すべてのＩＰＳＧ２０６が、等しく用意され（ｐｒｏｖｉｓｉｏｎｅｄ）／利用される一方で、将来の顧客を含める余地も存在するように、各顧客に関して最適な仕方でＩＰＳＧ２０６のサブセットが選択される。各顧客に用意するＩＰＳＧ２０６の最良のセットを特定することには、ＶＰＮトンネルが確立されるリンクの費用、トンネルを確立する費用、ＩＰＳＧ２０６上でＶＰＮ顧客にサービス提供を行う費用、および耐障害性のためのＩＰＳＧ設定の冗長性などの様々な要因が含まれる。
【００３７】
図３は、リンク費用に基づいて仮想プライベート・ネットワーク（ＶＰＮ）サービスを提供するための方法の流れ図３００を描いている。方法３００は、工程３０１で開始し、工程３０２に進み、ネットワーク・サービス・プロバイダ（ＮＳＰ）２０１が、例えば、大都市の様々な箇所に、州全体にわたって、かつ／または全国にわたってなど、様々な地理的区域にわたって複数のＩＰＳＧ２０６を戦略的に配置する。工程３０４で、ＮＳＰ２０１は、ＭＡＰ２０８がＩＰＳＧ２０６とは別に離れて配置されるように、様々な地理的区域にわたって複数のモバイル・アクセス・ポイント（ＭＡＰ）２０８を配置する。
【００３８】
次に、方法３００は、工程３０６に進み、ネットワーク・ノードの数と位置が特定される。ＮＳＰ２０１がネットワーク内にノードを配備した際、各ＩＰＳＧ２０６および各ＭＡＰ２０８の数と位置が特定される。さらに、顧客の数、およびそれぞれのイントラネット２２０およびＣＰＥ２２２も特定される。また、ノード間のホップ・カウントも特定され、ＭＮ２３０からＣＰＥ２２２までの終端間ホップ・カウントも特定することができるようになる。ノードおよびホップ・カウントが特定されると、方法３００は、工程３０８に進む。
【００３９】
工程３０８で、ＮＳＰ２０１は、各顧客２２０（すなわち、ＣＰＥ２２２）と少なくとも１つのＩＰＳＧ２０６の間の接続を選択的に提供する。つまり、顧客に用意される特定のサブセットのＩＰＳＧ２０６を解決する判定が行われる。各顧客にサービスを提供する複数のＩＰＳＧ２０６のサブセットを選択することは、図５に関連して以下により詳細に説明する費用解析アルゴリズムに基づく。工程３１０で、ＮＳＰ２０１が、各ＭＡＰ２０８と少なくとも１つのＩＰＳＧ２０６の間の接続を選択的に提供する。また、ＭＡＰ２０８をサポートするＩＰＳＧ２０６を選択することも、図５に関連して以下により詳細に説明する費用解析に基づく。次に、方法３００は、工程３１２に進む。
【００４０】
工程３１２で、選択されたＩＰＳＧ２０６が、顧客に関する仮想経路指定インスタンスおよびセキュリティ関連を備える（ｐｒｏｖｉｓｉｏｎｅｄ）。工程３１４で、備えのある（ｐｒｏｖｉｓｉｏｎｅｄ）ＩＰＳＧ２０６を使用して顧客の対応するＣＰＥ２２２までＶＰＮトンネルを確立する。詳細には、ＶＰＮトンネルが、モバイル・ノード２３０にサービスを提供するＭＡＰ２０８、および顧客特有のＩＰＳＧ２０６を介して、モバイル・ノード２３０からそれぞれのＣＰＥ１２２まで確立されることが可能である。次に、方法３００は、工程３９９に進み、ユーザが、ＶＰＮセッションに参加し、方法３００が終了する。
【００４１】
図４は、単一の顧客に関する第１の無向グラフ４００の概略図を描いている。詳細には、図４は、１組のノードおよび１組のリンクを有する第１の無向グラフ４００の概略図を描いており、図３の方法３００を理解するのに適している。ネットワークは、例として、それぞれｐｉ、ｑｊ、およびｒｋとして表される「ｉ」個のＭＡＰ２０８、「ｊ」個のＩＰＳＧ２０６、および所与の顧客に関する「ｋ」個のＣＰＥ２２２を含む。図４の例示的なグラフ４００では、ネットワーク４００は、ｐ１およびｐ２で表される２つのＭＡＰ２０８１および２０８２、ネットワーク４００内のｑ１、ｑ２、およびｑ３で表される３つのＩＰＳＧ２０６１、２０６２、および２０６３、および顧客に関するｒ１およびｒ２で表される２つのＣＰＥ２２２１および２２２２を有する単一の顧客２２０を含む。さらに、複数のモバイル・ノード２３０１乃至２３０ｍ（ここで、ｍは、１より大きい整数である）がＭＡＰ２０８に結合されているのを例示している。具体的には、ＭＮ１  ２３０１乃至ＭＮ３  ２３０３がＭＡＰ  Ｐ１  ２０８１に対する接続を有し、他方、ＭＮ４  ２３０４およびＭＮｍ  ２３０ｍが、ＭＡＰ  Ｐ２  ２０８２に対する接続を有する。
【００４２】
複数のＶＰＮ顧客がバッチで考慮され、利益を最大化するそのバッチに用意される最良の１組のＩＰＳＧが特定されることに留意されたい。各顧客に関して、顧客のイントラネット内のＣＰＥ、およびＮＳＰネットワーク内のＩＰＳＧおよびＭＡＰのすべてが考慮される。
【００４３】
ＩＰＳＧ２０６、ＭＡＰ２０８、および顧客のＣＰＥ２２２のネットワークが、無向グラフＧ＝（Ｖ，Ｅ）としてモデル化されており、ここで、Ｖはノードのセットであり、Ｅはリンクのセットである。Ｖの中のグラフ・ノードは、ＣＰＥ２２２、ＩＰＳＧ２０６、およびＭＡＰ２０８だけに対応する。Ｅの中のグラフ・リンクは、対応するＭＡＰとＩＰＳＧの間の選択されたパスに対応するＭＡＰ２０８とＩＰＳＧ２０６の間のリンクとして分類することができ、ＩＰＳＧ２０６とＣＰＥ２２２の間のリンクは、両者の間の選択されたパスに対応する。特定の経路指定目的に基づく経路指定アルゴリズムにより、選択されたパスが計算される。経路指定目的は、ホップ・カウントに基づく最短パスであること、またはネットワーク・リンクに割り当てられた費用に基づく最低費用パスであることが可能であり、両方とも、オープン・ショーテスト・パス・ファースト（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）（ＯＳＰＦ）によって計算することができる。また、経路指定目的は、ＡＴＭ  ＶＣまたはＭＰＬＳラベル・スイッチ・パスなどのトラフィック工学パスであることも可能である。本発明の階層式アーキテクチャでは、トラフィックは、ＭＡＰ２０８およびＩＰＳＧ２０６を介してＭＮ２３０からＣＰＥ２２２に流れる。したがって、それらの間のリンクだけが考慮される。
【００４４】
図３を参照すると、工程３０８で、ＩＰＳＧ２０６のサブセットが、各顧客に関して選択されている。物理ネットワーク・リンク上のＶＰＮトンネルの確立は、リンクに関連するある費用を被る。次に、グラフ内の２つのノード間のリンクの費用が、対応するネットワーク・ノード間のＶＰＮトンネルの計算された費用になる。実際には、ＶＰＮ顧客の要件に応じて、リンク費用は、他のリンク費用測定技術のなかでもとりわけ、基礎にある物理ネットワーク内のホップ数、または物理リンクの帯域幅容量の割合であることが可能である。本発明を理解するため、リンク費用は、物理リンクの帯域幅容量を使用してリンク費用を計算することではなく、ＭＡＰとＣＰＥの間の最適な接続（すなわち、ホップ数）に関連して説明する。
【００４５】
同一の顧客に関してＩＰＳＧとＣＰＥの間で１つのＶＰＮトンネルだけが確立されるので、各顧客に関してＩＰＳＧからＣＰＥへのリンクの費用が一度だけ考慮される。例えば、図４を参照すると、ＩＰＳＧ  ｑ３  ２０６３が、それぞれのリンクｐ１ｑ３およびｐ２ｑ３を介してＭＡＰ  ｐ１  ２０８１およびＭＡＰ  ｐ２  ２０８２から形成された２つのトンネルを有することが可能である。ただし、ＣＰＥ  ｒ２  ２２２２に接続するＭＮに関してＩＰＳＧ  ｑ３  ２０６３とＣＰＥ  ｒ２  ２２２２の間で１つの共用トンネルだけが利用されている。
【００４６】
図５は、図３の方法に従ってＶＰＮ顧客にサービス提供を行うＩＰサービス・ゲートウェイ（ＩＰＳＧ）のサブセットを選択するのに適した方法５００の流れ図を描いている。詳細には、方法５００は、図３の工程３０８を提供するのに適している。方法５００は、工程５０１で開始し、工程５０２に進み、所定のネットワーク・パラメータが特定される。詳細には、所定のネットワーク・パラメータには、すべてのＭＡＰのセット（Ｐ）、すべてのＩＰＳＧのセット（Ｑ）、すべての顧客ＣＰＥのセット（Ｒ）、各ＭＡＰ２０８から各ＩＰＳＧ２０６にトラフィックを送信する費用（ｃｉｊ）、各ＩＰＳＧ２０６から各ＣＰＥ２２２にトラフィックを送信する費用（ｄｊｋ）、およびＩＰＳＧノード（ｊ）２０６を使用するための現在の費用（ｆｊ）が含まれる。
【００４７】
工程５０４で、ＭＡＰ（図４のｐｉ）とＩＰＳＧ（図４のｑｉ）の間におけるのと同様に、動的トンネル接続費用（ＣＣ１）が定式化される。さらに、工程５０６で、ＩＰＳＧ（図４のｑｉ）とＣＰＥ（図４のｒｋ）の間におけるのと同様に、静的トンネル接続費用（ＣＣ２）が定式化される。
【００４８】
詳細には、接続費用は、ＶＰＮトンネルに関連して考慮することができる。顧客のユーザからＣＰＥまでのすべてのセッションに関して、ＭＡＰからＩＰＳＧまでＶＰＮトンネルが確立される。ＭＡＰからＩＰＳＧまでのＶＰＮトンネルは、「動的トンネル」と呼ばれる。というのは、ＶＰＮトンネルは、通常、ユーザによって「オンザフライ」で確立されるからである。ただし、ＩＰＳＧからＣＰＥまでのトラフィックは、「静的トンネル」と呼ばれる１つのトンネル上に集められる。この場合、ＩＰＳＧからＣＰＥまでの費用は、一度限り、全体的な接続費用の中に含められる。簡明にするため、および本発明の理解のため、ＩＰＳＧの最適化および選択は、単一の顧客に関して定式化され、次に、複数の顧客に関して生成される。
【００４９】
サービス・プロバイダ利益は、所与のＶＰＮ顧客にサービス提供を行うのに最適なＩＰＳＧを選択することによって最大化することができる。利益（Ｇ＝γＲ−Ｃ）は、重み付けされた収益（γＲ）と費用（Ｃ）の差であり、ここで、顧客に関する収益（Ｒ）は、顧客にサービス提供が行われることが可能である場合、固定の値であり、γは、費用と比べた収益に課される相対的重みであることに留意されたい。
【００５０】
費用は、いくつかの成分を有し、前述したとおり、各顧客にサービス提供を行うＩＰＳＧの最良セットを特定することは、ＶＰＮトンネルが確立されるリンクの費用、トンネルを確立する費用、ＩＰＳＧ上でＶＰＮ顧客にサービス提供を行う費用、および耐障害性のためのＩＰＳＧサービス提供の冗長性を計算に入れることを含む。言い換えれば、Ｐの中のすべてのＭＡＰ  ｉおよびＲの中のすべてのＣＰＥ  ｋに関して、利益が最大化されるように、Ｑの中のＩＰＳＧ  ｊが選択されてｉとｊの間の固有の動的トンネル、およびｊとｋの間の共用静的トンネルが確立される。
【００５１】
図４を参照すると、Ｐは、すべてのＭＡＰ２０８のセットであり、Ｑは、すべてのＩＰＳＧ２０６のセットであり、Ｒは、顧客に関するすべてのＣＰＥ２２２のセットである。２値変数ｘｉｊｋ∈｛０，１｝は、ノードｉ∈Ｐとノードｊ∈Ｑの間の動的トンネルが、ＭＡＰ  ｉからＣＰＥ  ｋ∈Ｒへのトラフィックに関して使用されるかどうかを表す。２値変数ｚｊｋ∈｛０，１｝は、ＩＰＳＧ  ｊからＣＰＥ  ｋへの共用静的トンネルが確立されるかどうかを表す。ここで、ノードｉからノードｊにトラフィックを送信する費用は、ｃｉｊであり、ノードｊからノードｋにトラフィックを送信する費用は、ｄｊｋである。
【００５２】
単一の顧客に関して、動的トンネル接続費用（例として、ＭＡＰとＩＰＳＧの間のホップ・カウント費用である）は、
【数７】
2004260833.tif 000003
である。同様に、静的トンネル接続費用（例として、ＩＰＳＧとＣＰＥの間のホップ・カウント費用である）は、
【数８】
2004260833.tif 000004
である。
【００５３】
工程５０８で、総トンネル接続費用（ＣＣ）が定式化される。総接続費用は、動的トンネル接続費用と静的トンネル接続費用の合計ＣＣ＝ＣＣ１＋βＣＣ２であり、ここで、βは、静的トンネル接続費用に課される相対的重みである。静的トンネル接続費用に課される相対的重みβに影響を与える要因には、アクセス網を介する費用に上乗せしたコア・ネットワークを介してデータをトランスポートする費用が含まれる。
【００５４】
工程５１０で、ＩＰＳＧノード（ｊ）を設置する現在の費用ＣＶが定式化される。２値変数ｙｊ∈｛０，１｝は、顧客が自らのＣＰＥの少なくとも１つにトラフィックを送信するようにＩＰＳＧ  ｊが用意される場合、１であり、それ以外では、０である。パラメータｆｊが、例として、ＩＰＳＧノードｊを使用する現在の費用として用いられている。所与の顧客に関して、任意のＩＰＳＧにおいて、せいぜい１つのサービス提供が考慮されている。したがって、ｆｊは、一度に１つの顧客だけが考慮される場合、固定の値を有し、サービス提供費用は、
【数９】
2004260833.tif 000005
である。
【００５５】
工程５１２で、顧客に関する総費用が定式化される。詳細には、総費用は、Ｃ＝ＣＣ＋αＣＶであり、ここで、αは、サービス提供費用に課される相対的重みである。サービス提供費用に課される相対的重みαに影響を与える要因には、ネットワーク・サービス・プロバイダの接続費用に上乗せしたサービス提供費用の重要度が含まれる。
【００５６】
工程５１４で、利益が定式化される。詳細には、利益は、Ｇ＝γＲ−Ｃである。簡明にするため、収益Ｒ＝１である。したがって、顧客にサービス提供を行うことに関する利益「Ｇ」は、Ｇ＝γ−Ｃであり、ここで、γは、総費用と比べた収益に課せられる相対的重みである。重み付け係数γは、基本的に、ネットワーク・サービス・プロバイダが、顧客に関する総費用に基づいて価格を調整することを可能にする。
【００５７】
工程５１６で、所与のパラメータｃｉｊ、ｄｊｋｆｊ、ｆｊ、α、β、およびγ、２値変数Ｘｉｊｋ、Ｚｊｋ、およびｙｊが、以下のとおり表現される最適化問題定式に対する解として算出される。
【数１０】
2004260833.tif 000006
ただし、
【数１１】
2004260833.tif 000007
【００５８】
数式（３）は、数式（２）の展開したバージョンであることに留意されたい。数式（７）は、ＭＡＰから出る厳密に１つのリンクが１つのＣＰＥに向かうように選択されることを指定しており、ＭＡＰからＣＰＥへのトラフィックが、１つのＩＰＳＧだけに送られることを暗示していることにさらに留意されたい。数式（８）は、複数のＭＡＰからのトラフィックがＩＰＳＧを経由してＣＰＥに到達する場合でも、ＩＰＳＧとＣＰＥの間に１つだけのトンネルが確立されるという条件を指定している。つまり、
【数１２】
2004260833.tif 000008
それ以外の場合
【数１３】
2004260833.tif 000009
数式（１０）および（１１）は、条件（８）と等価である。というのは、ｚｊｋが目的関数Ｇの中にあり、ｘｉｊｋ＝０，∀ｉ∈Ｐである場合、Ｇを最大化するのに、ｚｊｋ＝０が選択されなければならないからである。
【００５９】
数式（９）で表現される条件は、ＩＰＳＧが、複数のＣＰＥにトラフィックを送信するように構成され（ｐｒｏｖｉｓｉｏｎｅｄ）ていても、サービス提供費用を計算する目的で、ＩＰＳＧは、単一のサービス提供として考慮されなければならない。つまり、
【数１４】
2004260833.tif 000010
それ以外の場合
【数１５】
2004260833.tif 000011
【００６０】
数式（１２）および（１３）は、数式（９）で表現される条件と等価である。というのは、ｙｊが、目的関数Ｇの中にあり、ｚｊｋ＝０，∀ｋ∈Ｒである場合、Ｇを最大化するのに、ｙｊ＝０が選択されなければならないからである。工程５１８で、方法５００が終了する。
【００６１】
サービス提供費用が算出されると、顧客にＩＰＳＧの特定のサブセットを用意する（ｐｒｏｖｉｓｉｏｎ）ことの利益Ｇを計算することができる。具体的には、利益は、収益からサービス提供費用を引いたものに等しいＧ＝λ−Ｃ。言い換えれば、モバイル・ノード２３０とＣＰＥ２２２の間の接続を最適化することができる。というのは、ノード間の費用（すなわち、ホップ・カウント）とＩＰＳＧを用意する費用の合計が、顧客２２０にＩＰＳＧ２０６の特定のサブセットを用意することによって最小限に抑えられるからである。
【００６２】
複数の顧客のケースでは、各顧客に関する利益の合計が最大化され、各顧客に関する利益は、前述した単一の顧客の場合とまったく同じやり方で計算される。ネットワーク内のすべてのＭＡＰ２０８およびすべてのＩＰＳＧ２０６が、すべての顧客の間で共用される。ただし、各顧客は、ＣＰＥの独自のセットを有する。
【００６３】
単一の顧客のケースでは、各ＩＰＳＧ  ｊにおけるサービス提供費用ｆｊが固定値を有し、サービス提供容量に達したＩＰＳＧは、考慮されず、これは、ｆｊ＝∞に設定することと等価である。複数の顧客が考慮される場合、ＩＰＳＧ  ｊ上でサービス提供を受けるすべての顧客に関してｆｊに固定値が割り当てられる。ただし、各ＩＰＳＧにおいて複数の顧客がサービス提供を受けることが可能であるため、サービス提供を受ける顧客の数が、各ＩＰＳＧのサービス提供容量を超えないように注意を払わなければならない。さらに、複数の顧客が同時に考慮される場合、ネットワーク内ですべての顧客にサービス提供が行われてはならない。最大の利益をもたらす顧客に優先順位が与えられなければならない。顧客が拒否される２つのケースが存在する。１つのケースは、ネットワーク内のいずれのＩＰＳＧ上にもサービス提供容量が残されていない場合であり、もう１つのケースは、その顧客にサービス提供を行うことが、負の利益、つまり損失をもたらす場合である。基本的に総利益を最大化するため、顧客のサブセットにサービス提供が行われる。残りの顧客は、サービス提供容量に達したか、または顧客が利益ではなく損失をもたらすという理由で拒否される。
【００６４】
複数のＶＰＮ顧客に関する最適化問題は、以下のとおり説明することができる。Ｔを考慮されるべきＶＰＮ顧客のセットとし、｜Ｔ｜＝Ｌとする。ＰをすべてのＭＡＰのセット、ＱをすべてのＩＰＳＧのセット、Ｒをすべての顧客に関するすべてのＣＰＥのセットとし、ここで、Ｒ＝｛Ｒ１，Ｒ２，．．．，Ｒｌ，．．．，ＲＬ｝であり、ＲＩは、顧客ｌ∈Ｔに関するＣＰＥのセットである。ｗｌをネットワーク内で顧客ｌにサービス提供が行われるべきかどうかを指定する２値変数とする。サービス提供を受ける各顧客ｌに関して、Ｐの中のすべてのノードｉ、およびＲｌの中のすべてのノードｋが、すべての顧客に関する総利益が最大化されるようにＱの中のＩＰＳＧノードｊを選択して、ｉとｊの間の固有のトンネル、およびｊとｋの間の共用トンネルを確立する。言うまでもなく、サービス提供を受けない顧客に関して、費用は０である。
【００６５】
図６は、複数の顧客に関する第２の無向グラフ６００の概略図を描いている。図６は、２つのＣＰＥ２２２をそれぞれが有する２つの顧客２２０が例として示されていることを除けば、図４と同じである。詳細には、ネットワーク６００は、例として、それぞれｐｉ、ｑｊ、およびｒｋで表される、「ｉ」個のＭＡＰ２０８、「ｊ」個のＩＰＳＧ２０６、および所与の顧客に関する「ｋ」個のＣＰＥ２２２を含む。図６の例示的なグラフ６００では、ネットワーク６００は、ｐ１およびｐ２で表される２つのＭＡＰ２０８１および２０８２、ネットワーク４００内のｑ１、ｑ２、およびｑ３で表される３つのＩＰＳＧ２０６１、２０６２、および２０６３、ならびに２つの顧客２２０１および２２０２を含む。各顧客は、例として、第１の顧客２２０１に関するｒ１１およびｒ１２で表されるＣＰＥ２２２１１および２２２１２、ならびに第２の顧客２２０２に関するｒ２１およびｒ２２で表されるＣＰＥ２２２２１および２２２２２のような２つのＣＰＥを有する。さらに、複数のモバイル・ノード２３０ｍが、ＭＡＰ２０８に結合されているのを例示している。具体的には、ＭＮ１  ２３０１乃至ＭＮ３  ２３０３は、ＭＡＰ  Ｐ１  ２０８１に対する接続を有し、他方、ＭＮ４  ２３０４およびＭＮｍ  ２３０ｍは、ＭＡＰ  Ｐ２  ２０８２に対する接続を有する。
【００６６】
顧客ｌ∈Ｔに関して、ＭＡＰ  ｉからＣＰＥ  ｋ∈Ｒｌへのトラフィックに関してノードｉ∈Ｐとノードｊ∈Ｑの間のトンネルが使用されるかどうかが、２値変数ｘｌｉｊｋ∈｛０，１｝で表される。ＩＰＳＧ  ｊからＣＰＥ  ｋへの共用トンネルが確立されるかどうかを表すのに２値変数ｚｌｊｋ∈｛０，１｝が使用される。ノードｉからノードｊにトラフィックを送信することの費用は、ｃｉｊである。この費用は、すべての顧客に関して同じであり、したがって、インデックスｌは必要ないことに留意されたい。ノードｊからノードｋにトラフィックを送信することの費用は、ｄｌｊｋである。
【００６７】
２値変数ｙｌｊ∈｛０，１｝は、顧客ｌがトラフィックを自らのＣＰＥの少なくとも１つに送信するようにＩＰＳＧ  ｊが用意されている（ｐｒｏｖｉｓｉｏｎｅｄ）場合、１であり、それ以外の場合、０である。各ＩＰＳＧ上でサービス提供を受けることが可能な顧客の最大数としてパラメータＰＣＡＰを使用し、顧客ｌがノードｊを使用する費用としてパラメータｆｊを使用する。ＩＰＳＧ  ｊのサービス提供容量に達しない限り、各顧客に関するサービス提供費用は同じであり、したがって、インデックスｌは必要ない。
【００６８】
考慮されている単一の顧客ｌ∈Ｔに関して、動的トンネル接続費用（ＭＡＰからＩＰＳＧまでの費用である）は、
【数１６】
2004260833.tif 000012
である。共用静的トンネル接続費用（ＩＰＳＧからＭＡＰまでの費用である）は、
【数１７】
2004260833.tif 000013
である。したがって、総接続費用は、ＣｌＣ＝ＣｌＣ１＋βＣｌＣ２であり、ここで、βは、静的トンネル接続費用に課される相対的重みである。顧客ｌに関するサービス提供費用は、
【数１８】
2004260833.tif 000014
である。したがって、顧客ｌに関する総費用は、Ｃｌ＝ＣｌＣ＝αＣｌＶであり、ここで、αは、サービス提供費用に課される相対的重みである。サービス提供を受ける各顧客に関する収益は、同じであるものと想定される。したがって、サービス提供を受けない各顧客に関する収益と費用はともに、ゼロである。したがって、利益は、Ｇｌ＝γｗｌ−Ｃｌであり、ただし、γは、費用と比べた収益に課せられる相対的重みである。したがって、最適化問題定式は、以下のように明示することができる。
【数１９】
2004260833.tif 000015
ただし
【数２０】
2004260833.tif 000016
数式（１７）は、数式（１６）の展開されたバージョンであることに留意されたい。単一の顧客に関する定式と比べると、各ＩＰＳＧ  ｊ上のサービス提供の総数が容量ＰＣＡＰを超えてはならないことを指定する条件（２５）が追加されている。さらに、顧客にサービス提供が行われるかどうかを指定する新しい２値変数ｗｌが導入され、顧客にサービス提供が行われる場合にだけ、ＭＡＰから出る厳密に１つのリンクがその顧客に関する１つのＣＰＥに向かい、それ以外の場合、いずれのＭＡＰから出るリンクも選択されず、ＩＰＳＧはまったく用意されないことを指定するように条件（２２）が変更されている。
【００６９】
前述した整数プログラミング問題を解決するため、接続費用ｃｉｊ、ｄｊｋ、およびサービス提供費用ｆｊに適切な値を割り当てる必要がある。費用計算は、ＮＳＰの設計目的に合うように適合させることができる。これにより、前述の定式が極めて一般的になり、ＶＰＮ顧客に関する接続を保証することに加え、異なるシナリオに関して使用することができる。
【００７０】
接続費用は、ＮＳＰが制御することを望むパラメータに相関する。ＮＳＰ２０４は、ＶＰＮ顧客２２０からの特別な要件を満たして、その顧客のユーザを遠隔の負荷の軽いＩＰＳＧ２０６に切り替えることによってＮＳＰ２０４に関する総費用を低減することができる場合でも、それを行わないようにする必要がある可能性がある。例えば、東海岸の企業イントラネットにアクセスしようと試みている東海岸のＭＮ２３０が西海岸のＩＰＳＧに切り替えられることは、この解決策で総費用が最小限に抑えられる場合でも行われてはならない。制約を考慮に入れるため、ＭＡＰからＣＰＥまでに許されるホップの数、およびグラフのリンク費用が以下のとおり変更される。
ｃｉｊ＞Ｌ１ｍａｘ、∀ｉ∈Ｐ、かつ∀ｊ∈Ｑである場合、ｃｉｊ＝∞  （２６）
ｄｌｊｋ＞Ｌ２ｍａｘ、∀ｊ∈Ｑ、∀ｋ∈Ｒ、かつ∀ｌ∈Ｔである場合、ｄｊｋ＝∞  （２７）
ただし、Ｌ１ｍａｘおよびＬ２ｍａｘはそれぞれ、ＭＡＰ２０８とＩＰＳＧ２０６の間のトンネルに関して許される最大ホップ数、およびＩＰＳＧ２０８とＣＰＥ２２２の間のトンネルに関して許される最大ホップ数である。
【００７１】
一度に単一の顧客が考慮される場合、サービス提供費用は、オプションとして、各ＩＰＳＧにおけるサービス提供の既存の数を反映するように設定することができる。例えば、サービス提供費用ｆｊ＝ｃａｐｊ＝／ａｖａｉｌｊであり、ここで、ｃａｐｊは、ＩＰＳＧ  ｊの容量であり、ａｖａｉｌｊ＝は、残されている可用なサービス提供の数である。この費用割当てにより、すべてのＩＰＳＧ２０６にわたってＩＰＳＧごとのサービス提供の数の均一な配分がもたらされる。
【００７２】
ただし、複数の顧客が同時に考慮される場合、異なる顧客に関するサービス提供費用は、整数プログラミング・プログラムへの有効な入力であるためには同一でなければならない。一般性を損じることなく、すべての顧客に関するＩＰＳＧ  ｊに関してｆｊ＝１に設定される。
【００７３】
費用計算段階は、顧客特有の要件を考慮に入れる。費用計算段階の後、従来の整数プログラミング・パッケージ（例えば、ＬＰＳＯＬＶＥおよびＣＰＬＥＸ）を使用して、ＩＰＳＧ選択問題を解決することができる。
【００７４】
トンネリングＩＰＳＧに障害が生じた場合、少なくとも第２のＩＰＳＧが冗長性を提供するように用意されていることを確実にする耐障害性を提供することができる。一実施形態では、反復に最低限度が課せられる。耐障害性を提供するため、すべての顧客に関して、ＭＡＰからＣＰＥへの各トラフィック・セッションは、Ｎ＞１個のＩＰＳＧを経由するオプションを有していなければならない。Ｎ−１個のＩＰＳＧに障害が生じた場合、それでも、機能しているＩＰＳＧを使用してトラフィック・セッションを確立することができる。耐障害性の考慮を伴わない条件（２２）で提供される定式に対する唯一の変更は、条件（２２）を
【数２１】
2004260833.tif 000017
で置き換えることだけである。
【００７５】
条件（２８）は、サービス提供を受ける各顧客ｌ∈Ｔに関して、別個のＩＰＳＧ２０６をそれぞれが経由するＮ個の接続が、ＭＡＰ２０８とＣＰＥ２２２の間で確立されていなければならないことを指定している。ＭＡＰとＣＰＥの各ペアは、Ｎ個のＩＰＳＧのセットの使用を必要とし、そのＩＰＳＧセットは重なり合うことが可能であるため、したがって、顧客ｌに関して使用されるＩＰＳＧの総数は、Ｎに等しいか、またはＮより大きい。言い換えれば、この定式は、各顧客に用意されるＩＰＳＧの最小数を指定している。
【００７６】
第２の実施形態では、反復に厳密な限度が課せられる。耐障害性を考慮する別のやり方は、各顧客が、自らのすべての接続に関して正確にＮ個だけのＩＰＳＧを使用できることを要求することである。これは、以下のとおり、１つまたは複数の条件が定式に追加されることを必要とする。
【数２２】
2004260833.tif 000018
【００７７】
条件（２９）は、サービス提供を受ける顧客ｌに関するすべての接続に関して、正確にＮ個のＩＰＳＧノードが使用できることを指定している。
したがって、２つのネットワーク要素、すなわち、ＭＡＰ２０８およびＩＰＳＧ２０６を使用する階層式アーキテクチャが、モバイルＶＰＮサービスを提供することを例示している。ネットワーク要素を最適に使用するため、ネットワークの設計に影響を与えるいくつかの費用が特定されている。詳細には、一実施形態では、ＶＰＮトンネルが確立されるリンクの総接続費用、ならびに各顧客にＩＰＳＧを用意する（ｐｒｏｖｉｓｉｏｎ）費用を最小限に抑えるため、モバイルＶＰＮ顧客にＩＰＳＧが用意される（ｐｒｏｖｉｓｉｏｎｅｄ）。
【００７８】
つまり、モバイルＶＰＮサービスを提供するＮＳＰに関する利益を最大化するために、異なるＩＰＳＧ２０６上にＮＳＰの複数の顧客を最適に設定する（ｐｒｏｖｉｓｉｏｎ）することができる。そのような最適化は、ＶＰＮセッションが確立されるリンクの費用、およびＩＰＳＧ２０６上で顧客にサービス提供を行う費用を考慮に入れる。
【００７９】
本発明の第２の実施形態では、ＶＰＮ顧客が、帯域幅の限られたネットワーク内の異なるＩＰＳＧ２０６上に最適に設定される（ｐｒｏｖｉｓｉｏｎｅｄ）。詳細には、図１〜６に関連して前述したのと同じアーキテクチャを使用して、ＮＳＰの利益を最大化することを、ネットワークの帯域幅制約に基づいて決定することができる。ＮＳＰの利潤性を最大化することのそのような決定は、図７〜９に関連して以下に説明するとおり、顧客の帯域幅要件、必要とされる帯域幅を割り振ることの費用、リンクの容量制約、およびＩＰＳＧ上で顧客にサービス提供を行うことの費用を考慮に入れる。
【００８０】
具体的には、ＮＳＰの企業顧客に属するモバイル・ユーザが、そのユーザが位置する区域をカバーするＭＡＰ２０８とのデータ接続を開始する。ユーザは、次に、顧客の所在地の１つに配置された特定のＣＰＥ２２２とのＶＰＮセッション（すなわち、トンネル）を開始する。前述したとおり、このセッションは、企業へのセキュアな接続が必要とされる際にユーザによって動的ＶＰＮトンネルを介して開始され、ユーザがもはやその要件を有さなくなった際、解体される。このＶＰＮセッション要求は、対応するＭＡＰ２０８により、その顧客に用意されている（ｐｒｏｖｉｓｉｏｎｅｄ）ＩＰＳＧ２０６に転送される。ＩＰＳＧ２０６は、そのＶＰＮセッションを終端させ、そのセッションからの／そのセッションへのトラフィックを、ＩＰＳＧ２０６からＣＰＥ２２２までの静的ＶＰＮトンネル（すなわち、寿命の長いあらかじめ開始されているＶＰＮセッション）を介して適切なＣＰＥ２２２に転送する。これは、顧客のＭＮ２３０からＣＰＥ２２２へのすべてのＶＰＮセッションに関して、対応するＭＡＰ２０８を介してＩＰＳＧ２０６までＭＮ２３０によって動的トンネルが確立されることを意味する。ただし、ＩＰＳＧ２０６からＣＰＥ２２２へのトラフィックは、１つの静的トンネル上に集められる。中間で、ＩＰＳＧが、動的トンネルと静的トンネルのペアの間で転送されるトラフィックに付加価値サービスを提供する。階層式アーキテクチャに関連して前述したとおり、各顧客には、ＩＰＳＧのサブセットだけが用意され（ｐｒｏｖｉｓｉｏｎｅｄ）、それらのＩＰＳＧだけが、顧客のユーザにモバイルＶＰＮサービスを提供することができる。
【００８１】
このシナリオでは、帯域幅が制約されたネットワークにおけるＩＰＳＧ２０６サービス提供問題は、次のとおり定義することができる。特定のモバイルＶＰＮ顧客を考慮されたい。ＮＳＰは、その顧客のユーザにモバイルＶＰＮサービスを提供することによってある額の収益を実現する。ただし、このサービスを提供することに関連する費用も存在する。その顧客に関して、ＮＳＰによって解決されるべき問題は、（ａ）その顧客に用意するＩＰＳＧのサブセットを選択すること、および（ｂ）各ＭＡＰ２０８に関して、その顧客のユーザからＭＡＰ２０８に届くトラフィックのうちどれだけが、ネットワーク帯域幅容量が制限されているという制約の下で、そのサブセットの中のＩＰＳＧ２０６のそれぞれに宛先変更されるべきかを決定することである。目的は、モバイルＶＰＮサービスを提供することによってＮＳＰによって獲得される利益（収益から費用を引いたもの）が最大化されるように、問題（ａ）および（ｂ）に対する解決を見出すことである。より一般的な問題は、すべての顧客にモバイルＶＰＮサービスを提供することによってＮＳＰによって獲得される総利益が最大化されるように解決を見出すことである。
【００８２】
本発明を理解する目的で、ＮＳＰは、モバイルＶＰＮサービスを提供することによって顧客から固定額の収益を実現するものと想定する。サービスを提供することに関連する費用は、（ｉ）サービス提供費用と呼ばれるＩＰＳＧ２０６上で顧客にサービス提供を行うことに関連する固定費用、および（ｉｉ）送信されるトラフィックの量（単位／秒、例えば、Ｍｂｉｔ／秒の）に相関する、動的チャネルを介してＭＡＰ２０８からＩＰＳＧ２０６に、またはＩＰＳＧ２０６からＭＡＰ２０８にトラフィックを送信すること、および静的チャネルを介してＩＰＳＧ２０６からＣＰＥ２２２に、またはＣＰＥ２２２からＩＰＳＧ２０６にトラフィックを送信することに関連する可変の費用（すなわち、帯域幅費用）として列挙することができる。
【００８３】
ＭＡＰ２０８をＩＰＳＧ２０６に接続する論理リンク、およびＩＰＳＧ２０６をＣＰＥ２２２に接続する論理リンクは、ある容量（単位／秒（例えば、Ｍｂｉｔ／秒）の）を有する。ＭＡＰによってＩＰＳＧに送信されるトラフィック、および同様にＩＰＳＧによってＣＰＥに送信されるトラフィックは、基礎にあるリンク容量を超えることができない。論理リンクは、対応するペアの要素（すなわち、ノード）間のパスを提供する１組の物理リンクを表すものと想定される。さらに、各ＩＰＳＧは、顧客の数に関して扱うことができるある数のサービス提供に制限される。これは、ＩＰＳＧが顧客のそれぞれのために確保しておく必要があるリソースのためである。
【００８４】
ＭＡＰおよびＩＰＳＧは、ＮＳＰによって既に配備されており、ＭＡＰおよびＩＰＳＧの数と場所は、ネットワーク計画プロセス中に選択されているものとさらに想定する。また、ＮＳＰは、任意のＭＡＰ２０８が任意のＩＰＳＧ２０６に到達することができ、任意のＩＳＰＧ２０６が任意のＣＰＥ２２２に到達することができるようにネットワーク接続を提供するものと想定する。ＭＡＰ２０８とＩＰＳＧ２０６の間の（論理）リンク上の容量、同様にＩＰＳＧ２０６とＣＰＥ２２２の間の（論理）リンク上の容量は、通常、そのペアの要素間のパス上のボトルネックの物理リンクによって決まる。この容量情報は、先験的にＮＳＰに用意されているものと想定する。
【００８５】
さらに、ＭＮ２３０は、ネットワーク・アクセス識別子（ＮＡＩ）および／またはアクセス・ポイント名（ＡＰＮ）の一般的な方法を使用して特定されるものと想定する。ＭＡＰ２０８は、ＭＮとのデータ接続セットアップ時中にＭＮのＮＡＩ／ＡＰＮを抽出する。１つだけのＣＰＥが存在する場合、ＭＡＰ２０８は、ＮＡＩ／ＡＰＮから宛先ＣＰＥ２２２を特定することができる。複数のＣＰＥ２２２が存在する場合、ＭＡＰ２０８は、認証−許可−アカウンティング（ＡＡＡ）・サーバ（図示せず）からＭＮの選好するＣＰＥを特定することができる。ＭＡＰ２０８が、ＭＮ２３０からのＶＰＮセッション要求をＩＰＳＧ２０６に宛先変更した際、ＭＮとＩＰＳＧの間で動的トンネルが確立される。この時点で、ＩＰＳＧ２０６は、ＭＮ２３０が接続することを要望しているＣＰＥ２２２を認識する。この時点以降、ＭＮ２３０から動的トンネル上でトラフィックが受信されたときはいつでも、ＩＰＳＧ２０６は、そのトラフィックを静的トンネルを介してそのＣＰＥ２２２に向けて転送する。したがって、ＭＮ２３０とＣＰＥ２２２の間で終端間のデータ接続が確立される。安定した状態では、ＮＳＰは、ＭＡＰにおいてデータ接続を確立して特定のＣＰＥにトラフィックを送信する顧客のすべてのユーザ（ＭＮ）にサービスを提供するのにどれだけの帯域幅が必要とされるかの推定を有する。
【００８６】
図７は、帯域幅制約に基づいて仮想プライベート・ネットワーク（ＶＰＮ）サービスを提供するための方法７００の流れ図を描いている。図７は、図２、４、および６と併せて見なければならない。方法７００は、工程７０１で開始し、工程７０２に進み、ネットワーク・サービス・プロバイダ（ＮＳＰ）２０１が、例えば、大都市の様々な箇所に、州全体にわたって、かつ／または全国にわたってなど、様々な地理的区域にわたって複数のＩＰＳＧ２０６を戦略的に配置する。
【００８７】
企業顧客は、ＶＰＮサービスに契約する際、自らのＣＰＥの場所をＮＳＰに提供する。ＮＳＰは、顧客要求を２つのやり方で処理することができる。単純な手法では、ＮＳＰは、図８に関連して以下に説明するとおり、顧客要求を１回につき１つづつ処理することができる。この手法は、局所最適を達するが、大域的な最適を保証することができない。つまり、この手法は、ＮＳＰに関する利益を最大化するようにすべての顧客に最適にサービス提供が行われることを保証することができない。もう１つの手法は、図９に関連して以下に説明するとおり、一度に複数の顧客を考慮することである。複数の顧客を伴う定式は、大域的な最適を達するので、単一の顧客の定式は、複数顧客手法の特殊ケースと考えることができる。
【００８８】
工程７０４で、ＮＳＰ２０１は、図３の工程３０２および３０４に関連して前述したとおり、モバイル・アクセス・ポイント（ＭＡＰ）２０８がＩＰＳＧ２０６とは別に離れて（すなわち、遠隔に）配置されるように、複数のＭＡＰ２０８を様々な地理的区域にわたって配置する。
【００８９】
方法７００は、次に、工程７０６に進み、ネットワーク・ノードの数と場所が特定される。ＮＳＰ２０１がネットワーク内にノードを配備した際、各ＩＰＳＧ２０６および各ＭＡＰ２０８の数と場所が特定され、顧客の数、および顧客のそれぞれのイントラネット２２０およびＣＰＥ２２２の数も特定される。また、ＭＮ２３０からＣＰＥ２２２までの終端間帯域幅容量を特定することができるように、ノード間の帯域幅も特定される。ノード間の接続は、ホップ・カウントに基づく最短パスであること、またはネットワーク・リンクに割り当てられた費用に基づく最低費用のパスであることが可能であり、このどちらも、オープン・ショーテスト・パス・ファースト（ＯＳＰＦ）によって計算することができることに留意されたい。ノード、およびノード間の帯域幅容量が特定されると、方法７００は、工程３０８に進む。
【００９０】
工程７０８で、ＮＳＰ２０１は、各顧客２２０（すなわち、ＣＰＥ２２２）と少なくとも１つのＩＰＳＧ２０６の間で接続を選択的に提供する。つまり、特定の顧客に用意される（ｐｒｏｖｉｓｉｏｎｅｄ）ＩＰＳＧ２０６の特定のサブセットを解決する決定が行われる。選択された顧客２２０にサービスを提供する複数のＩＰＳＧ２０６のサブセットを選択することは、図８に関連して以下により詳細に説明する費用解析アルゴリズムに基づく。各顧客ＣＰＥ２２２と少なくとも１つのＩＰＳＧ２０６の間で接続が提供されると、方法７００は、工程７１０に進む。工程７１０で、ＮＳＰ２０１は、各ＭＡＰ２０８と少なくとも１つのＩＰＳＧ２０６の間の接続を選択的に提供する。ＭＡＰ２０８をサポートするＩＰＳＧ２０６の選択も、やはり図８に関連して以下により詳細に説明する費用解析に基づく。方法７００は、次に、工程７１２に進む。
【００９１】
工程７１２で、選択されたＩＰＳＧ２０６が、顧客に関する仮想経路指定インスタンスおよびセキュリティ関連を備える（ｐｒｏｖｉｓｉｏｎｅｄ）。工程７１４で、備えのある（ｐｒｏｖｉｓｉｏｎｅｄ）ＩＰＳＧ２０６を使用して顧客の対応するＣＰＥ２２２までＶＰＮトンネルを確立する。詳細には、ＶＰＮトンネルが、モバイル・ノード２３０にサービスを提供するＭＡＰ２０８、および顧客特有のＩＰＳＧ２０６を介して、モバイル・ノード２３０からそれぞれのＣＰＥ２２２まで確立されることが可能である。方法７００は、次に、工程７９９に進み、方法７００が終了して、ユーザが、ＶＰＮセッションに参加することができる。
【００９２】
図４を参照すると、ＩＰＳＧ２０６、ＭＡＰ２０８、および顧客のＣＰＥ２２２のネットワークが、再び無向グラフＧ＝（Ｖ，Ｅ）としてモデル化されており、ここで、前述したとおり、Ｖはノードのセットであり、Ｅはリンクのセットである。詳細には、図４は、顧客に関する例示的なグラフ・モデルを示している。２つのＭＡＰ、ｐ１およびｐ２、ネットワーク内の３つのＩＰＳＧ、ｑ１、ｑ２、およびｑ３、ならびに顧客に関する２つのＣＰＥ  ｒ１およびｒ２が存在する。Ｖの中のグラフ・ノードは、ＣＰＥ２２２、ＩＰＳＧ２０６、およびＭＡＰ２０８に対応する。Ｅの中のグラフ・リンクは、次の２つのカテゴリに入る。すなわち、（１）ＭＡＰとＩＰＳＧの間のリンクが、ＭＡＰとＩＰＳＧの間の論理リンクに対応し、（２）ＩＰＳＧ２０６とＣＰＥ２２２の間のリンクが、ＩＰＳＧとＣＰＥの間の論理リンクに対応する。前述したとおり、論理リンクは、対応する要素間のパスを形成する１組の物理リンクを表す。このパスは、ホップ・カウントに基づく最短パスであること、またはネットワーク・リンクに割り当てられた費用に基づく最低費用のパスであることが可能であり、このどちらも、ＯＳＰＦによって計算することができる。また、パスは、ＡＴＭ、ＶＣ、ＭＰＬＳラベル・スイッチ・パスなどのトラフィック工学パスであることも可能である。
【００９３】
リンクの容量は、そのリンクに対応するパス上のボトルネックの物理リンクの容量である。階層式アーキテクチャでは、トラフィックは、ＭＡＰ２０８およびＩＰＳＧ２０６を介してＭＮ２３０からＣＰＥ２２２に流れる。したがって、ＭＡＰ２０８とＩＰＳＧ２０６の間のリンク、およびＩＰＳＧ２０６とＣＰＥ２２２の間のリンクだけが、モデルにおいて考慮される。それぞれｐｉ、ｑｊ、およびｒｋで表されるＩ個のＭＡＰ、ネットワーク内のＪ個のＩＰＳＧ、および所与の顧客に関するＫ個のＣＰＥが存在するものと想定する。
【００９４】
前述のモデルに基づき、ＩＰＳＧサービス提供問題に対する解決は、１組のモバイルＶＰＮ顧客を考慮して、（ａ）顧客のそれぞれに用意する（ｐｒｏｖｉｓｉｏｎ）ＩＰＳＧ２０６の最良セットを計算し、（ｂ）特定のＣＰＥを宛先としてＭＡＰ２０８において受信された顧客に関するトラフィックのフロー（単位／秒の）が、どのように分割され、顧客が設定されている（ｐｒｏｖｉｓｉｏｎｅｄ）ＩＰＳＧ２０６のセットに送信されるかを決めることによって決めることができる。解決はまず、図８に関連して以下に説明するとおり、単一の顧客に関して定式化される。次に、解決は、図９に関連して以下に説明するとおり、複数の顧客を取り入れるように拡張される。
【００９５】
図７を参照すると、工程７０８で、各顧客に関してＩＰＳＧ２０６のサブセットが選択される。物理ネットワーク・リンクを介するＶＰＮトンネルの確立は、そのリンクに関連するある費用を被る。この第２の実施形態では、グラフ内の２つのノード間のリンクの費用は、対応するネットワーク・ノード間のＶＰＮトンネルの計算された費用となる。この第２の実施形態では、リンク費用は、図１〜６の第１の実施形態に関連して説明した基礎にある物理ネットワーク内のホップ数ではなく、物理リンクの帯域幅容量の割合に関連する。したがって、リンク費用は、物理リンクの帯域幅容量に関連して説明する。
【００９６】
同一の顧客に関してＩＰＳＧとＣＰＥの間で１つだけのＶＰＮトンネルが確立されるので、ＩＰＳＧからＣＰＥまでのリンクの費用は、各顧客に関して一回だけ考慮される。例えば、図４を参照すると、ＩＰＳＧ  ｑ３  ２０６３は、それぞれのリンクｐ１ｑ３およびｐ２ｑ３を介してＭＡＰ  ｐ１  ２０８１およびｐ２  ２０８２から形成された２つのトンネルを有することが可能である。ただし、ＣＰＥ  ｒ２  ２２２２に接続するＭＮに関してＩＰＳＧ  ｑ３  ２０６３とＣＰＥ  ｒ２  ２２２２の間で１つの共用トンネルだけが利用される。
【００９７】
図８は、図７の方法７００に従って帯域幅容量に基づいて単一のＶＰＮ顧客にサービス提供を行うＩＰサービス・ゲートウェイ（ＩＰＳＧ）のサブセットを選択するのに適した方法８００の流れ図を描いている。図８は、図４と併せて見なければならない。方法８００は、工程８０１で開始し、工程８０２に進み、所定のネットワーク・パラメータが特定される。詳細には、所定のネットワーク・パラメータには、すべてのＭＡＰのセット（Ｐ）、すべてのＩＰＳＧのセット（Ｑ）、すべての顧客ＣＰＥのセット（Ｒ）、ＭＡＰ  ｉとＩＰＳＧ  ｊの間の帯域幅容量（ｇｉｊ）、ＩＰＳＧ  ｊとＣＰＥ  ｋの間の帯域幅容量（ｈｊｋ）、ＭＡＰ  ｉとＣＰＥ  ｋの間の帯域幅要件（ｂｊｋ）、ＭＡＰ  ｉとＩＰＳＧ  ｊの間のリンク上の単位帯域幅費用（ａｉｊ）、ＩＰＳＧ  ｊとＣＰＥ  ｋの間のリンク上の単位帯域幅費用（ｅｊｋ）、ＩＰＳＧノードを使用することの現在の費用（ｆｊ）が含まれる。
【００９８】
さらに、工程８０２で、整数変数および２値変数が特定される。整数変数（Ｓｉｊｋ）は、ＩＰＳＧ  ｊを経由してＭＡＰ  ｉからＣＰＥ  ｋに向かわせられるトラフィックの量を指定するのに使用され、２値変数ｙｊ∈｛０，１｝は、顧客が自らのＣＰＥの少なくとも１つにトラフィックを送信するのにＩＰＳＧ  ｊが用意されるか（ｐｒｏｖｉｓｉｏｎｅｄ）どうかを指定する。
【００９９】
詳細には、図４に示すとおり、ＰをすべてのＭＡＰのセット、ＱをすべてのＩＰＳＧのセット、Ｒを顧客に関するすべてのＣＰＥのセットとする。整数変数ｓｉｊｋを使用して、ＩＰＳＧ  ｊ∈Ｑを経由してＭＡＰ  ｉ∈ＰからＣＰＥ  ｋ∈Ｒに向かわせられるトラフィックの量を指定する。ＭＡＰ  ｉ∈ＰとＩＰＳＧ  ｊ∈Ｑの間のリンク上の容量はｇｉｊ単位／秒であり、ＩＰＳＧ  ｊ∈ＱとＣＰＥ  ｋ∈Ｒの間のリンクの容量はｈｊｋ単位／秒であり、ＭＡＰ  ｉ∈ＰからＣＰＥ  ｋ∈Ｒへのトラフィックに関する帯域幅要件はｂｉｋ単位／秒であり、ただし、単位／秒は、例として、Ｍｂｉｔ／秒またはＭｂｙｔｅ／秒であるものと想定する。また、ＭＡＰ  ｉからＩＰＳＧ  ｊまでのリンク上の単位帯域幅費用（１単位／秒）はａｉｊであり、ＩＰＳＧ  ｊからＣＰＥ  ｋまでのリンク上の単位帯域幅費用はｅｊｋであるものと想定する。
【０１００】
工程８０４で、各ＭＡＰ２０８から各ＩＰＳＧ２０６にトラフィックを送信する費用（ｃｉｊ）が、単一の顧客に関して定式化される。詳細には、ＭＡＰ  ｉ∈ＰからＩＰＳＧ  ｊ∈Ｑへのトラフィックに関する帯域幅要件は、
【数２３】
2004260833.tif 000019
である。したがって、ＭＡＰ  ｉとＩＰＳＧ  ｊの間の帯域幅費用は、
【数２４】
2004260833.tif 000020
である。
【０１０１】
同様に、工程８０６で、各ＩＰＳＧ２０６から各ＣＰＥ２２２にトラフィックを送信することの費用（ｄｊｋ）、およびＩＰＳＧノード（ｊ）２０６を使用することの現在の費用（ｆｊ）が、単一の顧客に関して定式化される。詳細には、ＩＰＳＧ  ｊ∈ＱからＣＰＥ  ｋ∈Ｒへのトラフィックに関する帯域幅要件は、
【数２５】
2004260833.tif 000021
である。したがって、ＩＰＳＧ  ｊとＣＰＥ  ｋの間の帯域幅費用は、
【数２６】
2004260833.tif 000022
である。
【０１０２】
工程８０８で、動的トンネル帯域幅費用（ＣＣ１）が、ＭＡＰ（図４のｐｉ）とＩＰＳＧ（図４のｑｊ）の間におけるのと同様に定式化される。具体的には、動的トンネルの帯域幅費用は、
【数２７】
2004260833.tif 000023
である。さらに、工程８１０で、静的トンネル帯域幅費用（ＣＣ２）が、ＩＰＳＧ（図４のｑｊ）とＣＰＥ（図４のｒｋ）の間におけるのと同様に定式化される。具体的には、静的トンネルの帯域幅費用は、
【数２８】
2004260833.tif 000024
である。
【０１０３】
サービス・プロバイダの利益は、所与のＶＰＮ顧客にサービス提供を行う最適なＩＰＳＧを選択することによって最大化することができる。利益（Ｕ＝γＲ−Ｃ）は、重み付けされた収益（γＲ）と費用（Ｃ）の差であり、ただし、顧客に関する収益（Ｒ）は、顧客がサービス提供を受けることができる場合、固定値であり、γは、費用と比べた収益に課せられる相対的重みである。
【０１０４】
総費用は、いくつかの成分を有し、前述したとおり、ＶＰＮトンネルが確立されるリンクの帯域幅に関する費用、トンネルを確立する費用、ＩＰＳＧ上でＶＰＮ顧客にサービス提供を行う費用、および耐障害性のためのＩＰＳＧサービス提供における冗長性を考慮に入れることを含め、各顧客にサービス提供を行うＩＰＳＧの最良セットを特定することなどである。言い換えれば、Ｐの中のすべてのＭＡＰ  ｉおよびＲの中のすべてのＣＰＥ  ｋに関して、利益が最大化されるように、Ｑの中のＩＰＳＧ  ｊが選択されて、ｉとｊの間の固有の動的トンネル、およびｊとｋの間の共用静的トンネルが確立される。
【０１０５】
工程８１２で、総トンネル帯域幅費用（ＣＣ）が定式化される。総帯域幅費用は、動的トンネル帯域幅費用と静的トンネル帯域幅費用の合計ＣＣ＝ＣＣ１＋βＣＣ２であり、ここで、βは、静的トンネルの帯域幅費用に課される相対的重みである。静的トンネル帯域幅費用に課せられる相対的重みβに影響を与える要因には、アクセス網を介する費用に上乗せしたコア・ネットワークを介してデータをトランスポートする費用が含まれる。これは、ＩＰＳＧからＣＰＥまでの接続がコア・ネットワークを介し、ＭＡＰとＩＰＳＧの間の接続がアクセス網を介するためである。
【０１０６】
工程８１４で、ＩＰＳＧノード（ｊ）を設置する（ｐｒｏｖｉｓｉｏｎ）ことの現在の費用ＣＶが定式化される。２値変数ｙｊ∈｛０，１｝は、顧客が自らのＣＰＥの少なくとも１つにトラフィックを送信するのにＩＰＳＧ  ｊが用意される（ｐｒｏｖｉｓｉｏｎｅｄ）場合、１であり、それ以外の場合、０である。パラメータｆｊを例として、ＩＰＳＧノードｊを使用することの現在の費用として使用している。所与の顧客に関して、任意のＩＰＳＧにおいてせいぜい１つのサービス提供が考慮されている。したがって、ｆｊは、一度に１つだけの顧客が考慮される場合、固定値を有し、サービス提供費用は、
【数２９】
2004260833.tif 000025
である。
【０１０７】
工程８１６で、顧客に関する総費用が定式化される。詳細には、総費用は、Ｃ＝ＣＣ＋αＣＶであり、ここで、αは、サービス提供費用に課せられる相対的重みである。サービス提供費用に課せられる相対的重みαに影響を与える要因には、ネットワーク・サービス・プロバイダの帯域幅費用に上乗せしたサービス提供費用の重要度が含まれる。
【０１０８】
工程８１８で、利益が定式化される。詳細には、利益は、Ｕ＝γＶ−Ｃである。簡明にするため、収益Ｖ＝１である。したがって、顧客にサービス提供を行うことに関する利益「Ｕ」は、Ｕ＝γ−Ｃであり、ここで、γは、総費用と比べた収益に課せられる相対的重みである。重み付け係数γは、基本的に、ネットワーク・サービス・プロバイダが、顧客に関する総費用に基づいて価格を調整することを可能にする。
【０１０９】
工程８２０で、所与のパラメータｇｉｊ、ｈｊｋ、ｂｉｋ、ａｉｊ、ｅｊｋ、ｆｊ、α、β、およびγ、整数変数ｓｉｊｋ、および２値変数ｙｊが、以下のとおり表現される最適化問題定式に対する解として算出される。
【数３０】
2004260833.tif 000026
ただし
【数３１】
2004260833.tif 000027
【０１１０】
数式（３２）は、数式（３１）の展開されたバージョンであることに留意されたい。数式（３５）は、ＣＰＥ  ｋを宛先とするＭＡＰ  ｉにおける顧客に関するトラフィックを分割し、複数のＩＰＳＧを介して転送することができることを指定していることにさらに留意されたい。条件（３６）および（３７）は、ＭＡＰ  ｉからＩＰＳＧ  ｊまでの動的トンネルの帯域幅費用、およびＩＰＳＧ  ｊからＣＰＥ  ｋまでの静的トンネルの帯域幅費用をそれぞれ定義している。条件（３８）および（３９）は、動的トンネルおよび静的トンネルに関して、それぞれ帯域幅制約を指定する。さらに、数式（４０）は、複数のＣＰＥにトラフィックを送信するようにＩＰＳＧが構成されている（ｐｒｏｖｉｓｉｏｎｅｄ）場合でも、サービス提供費用を計算する目的で、ＩＰＳＧは、１つだけのサービス提供と見なされるべきであるという条件を指定している。つまり、
【数３２】
2004260833.tif 000028
それ以外の場合
【数３３】
2004260833.tif 000029
である。
数式（４１）および（４２）は、条件（４０）と等価である。というのは、ｂｉｋ≧ｓｉｊｋ∀ｉ∈Ｐ、ｊ∈Ｑ、ｋ∈Ｒであるので、ｓｉｊｋ＞０である場合、ｙｉ＝１である限り、条件（４０）は満たされる。さらに、ｙｊが目的関数Ｕの中にあるので、ｓｉｊｋ＝０、∀ｉ∈Ｐ、∀ｋ（Ｐである場合、利益Ｕを最大化するのに、ｙｊ＝０が選択されなければならないからである。工程８９９で、方法８００は終了する。
【０１１１】
サービス提供費用が算出されると、ＩＰＳＧの特定のサブセットを顧客に用意する（ｐｒｏｖｉｓｉｏｎ）ことに関する利益Ｕを計算することができる。具体的には、利益は、収益からサービス提供費用を引いたものに等しいＵ＝λ−Ｃ。言い換えれば、モバイル・ノード２３０とＣＰＥ２２２の間の接続を最適化することができる。というのは、ノード間の費用（すなわち、帯域幅制約）とＩＰＳＧを用意する費用の合計が、顧客２２０にＩＰＳＧ２０６の特定のサブセットを用意する（ｐｒｏｖｉｓｉｏｎ）ことによって最小限に抑えられるからである。
【０１１２】
複数の顧客のケースでは、各顧客に関する利益の合計が最大化され、ただし、各顧客に関する利益は、前述した単一の顧客のケースとまったく同じやり方で正確に計算される。ネットワーク内のすべてのＭＡＰ２０８およびＩＰＳＧ２０６が、すべての顧客の間で共用される。ただし、各顧客は、ＣＰＥの別個のセットを有する。
【０１１３】
単一の顧客のケースでは、各ＩＰＳＧ  ｊにおけるサービス提供費用ｆｊは固定値を有し、サービス提供容量に達したＩＰＳＧは考慮されず、これは、ｆｊ＝∞に設定することと等価である。複数の顧客が考慮される場合、ｆｊには、ＩＰＳＧ  ｊ上でサービス提供を受けるすべての顧客に関する固定値が割り当てられるが、各ＩＰＳＧにおいて複数の顧客がサービス提供を受けることが可能であるため、サービス提供を受ける顧客の数が各ＩＰＳＧのサービス提供容量（ＰＣＡＰ）を超えないように注意を払わなければならない。さらに、複数の顧客が同時に考慮される場合、ネットワーク内ですべての顧客にサービス提供が行われるべきではない。最大の利益を提供する顧客に優先順位が与えられなければならない。顧客が拒否される３つの事例が存在する。１つのケースは、ネットワーク内のいずれのＩＰＳＧにもサービス提供容量が残っていない場合である。別の事例は、ＭＡＰの１つまたは複数からの顧客の帯域幅要件がネットワーク容量を超えた場合に生じ、別の第３のケースは、顧客にサービス提供を行うことにより、負の利益（すなわち、損失）がもたらされる場合に生じる。基本的に、総利益を最大化するように顧客のサブセットにサービス提供が行われる。残りの顧客は、サービス提供容量に達した、または顧客が利益ではなく損失をもたらすという理由で拒否される。
【０１１４】
図６を参照すると、図４に示した単一の顧客ではなく、２つのＣＰＥ２２２をそれぞれが有する２つの顧客２２０が示されている。ネットワーク６００は、例として、それぞれｐｉ、ｑｊ、およびｒｋで表される「ｉ」個のＭＡＰ２０８、「ｊ」個のＩＰＳＧ２０６、および所与の顧客に関する「ｋ」個のＣＰＥ２２２を含む。ネットワーク６００は、ｐ１およびｐ２で表される２つのＭＡＰ２０８１および２０８２、ネットワーク６００内のｑ１、ｑ２、およびｑ３で表される３つのＩＰＳＧ２０６１、２０６２、および２０６３、ならびに２つの顧客２２０１および２２０２を含むことを想い起こされたい。各顧客は、例として、第１の顧客２２０１に関するｒ１１およびｒ１２で表されるＣＰＥ２２２１１および２２２１２、ならびに第２の顧客２２０２に関するｒ２１およびｒ２２で表されるＣＰＥ２２２２１および２２２２２のような２つのＣＰＥを有する。さらに、複数のモバイル・ノード２３０ｍがＭＡＰ２０８に結合されているのを例示している。具体的には、ＭＮ１  ２３０１乃至ＭＮ３  ２３０３がＭＡＰ  ｐ１  ２０８１に対する接続を有し、他方、ＭＮ４  ２３０４およびＭＮｍ  ２３０ｍが、ＭＡＰ  ｐ２  ２０８２に対する接続を有する。顧客１に関して、２つのＣＰＥは、ｒ１１  ２２２１１およびｒ１２  ２２２１２であり、顧客２に関して、２つのＣＰＥは、ｒ２１  ２２２２１およびｒ２２  ２２２２２である。
【０１１５】
図９は、図７の方法７００に従って帯域幅容量に基づいて複数のＶＰＮ顧客にサービス提供を行うＩＰサービス・ゲートウェイ（ＩＰＳＧ）のサブセットを選択するのに適した方法９００の流れ図を描いている。図９は、図６と併せて見なければならない。方法９００は、工程９０１で開始し、工程９０２に進み、所定のネットワーク・パラメータおよび変数が特定される。
【０１１６】
詳細には、｜Ｔ｜＝ＬであるようにＴを考慮されるべきモバイルＶＰＮ顧客のセットとし、ただし、Ｌは、ＶＰＮ顧客の数を表す。図６に例示するとおり、ＰをすべてのＭＡＰのセット、ＱをすべてのＩＰＳＧのセット、Ｒをすべての顧客に関するすべてのＣＰＥのセットとし、ここで、Ｒ＝｛Ｒ１，Ｒ２，．．．，ＲＩ，．．．，ＲＬ｝であり、ＲＩは、顧客ｌ∈Ｔに関するＣＰＥのセットである。ｗｌをネットワーク内で顧客ｌにサービス提供が行われるべきかどうかを指定する２値変数とする。複数のモバイルＶＰＮ顧客に関する最適化問題定式化は、サービス提供を受ける各顧客ｉに関して、Ｐの中のすべてのノードｉ、およびＲｌの中のすべてのノードｋが、すべての顧客に関する総利益が最大化されるようにＱの中のＩＰＳＧノードｊを選択して、ｉとｊの間の固有の（動的）トンネル、およびｊとｋの間の共用（静的）トンネルを経由してトラフィックを送信することを指定することができる。言うまでもなく、サービス提供を受けない顧客に関して、費用は０である。
【０１１７】
顧客ｌ∈Ｔに関して、整数変数ｓｌｉｊｋを使用して、ＩＰＳＧ  ｊ∈Ｑを経由してＭＡＰ  ｉ∈ＰからＣＰＥ  ｋ∈Ｒｌに向かわせられるトラフィックの量が指定される。つまり、ｓｌｉｊｋは、ＩＰＳＧ  ｊを経由してＭＡＰ  ｉからＣＰＥ  ｋに向かわせられるトラフィックの量を表す。パラメータｇｉｊおよびｈｌｊｋはそれぞれ、ＭＡＰ  ｉとＩＰＳＧ  ｊの間の帯域幅容量、およびＩＰＳＧ  ｊとＣＰＥ  ｋの間の帯域幅容量を表す。パラメータｂｌｉｋは、ＭＡＰ  ｉとＣＰＥ  ｋの間の帯域幅要件を表す。ＭＡＰ  ｉ∈ＰとＩＰＳＧ  ｊ∈Ｑの間のリンク上の容量は、ｇｉｊ単位／秒であり、ＩＰＳＧ  ｊ∈ＱとＣＰＥ  ｋ∈Ｒｌの間のリンクの容量は、ｈｌｊｋ単位／秒であり、ＭＡＰ  ｉ∈ＰからＣＰＥ  ｋ∈Ｒｌへのトラフィックに関する帯域幅要件は、ｂｌｉｋ単位／秒であり、ただし、単位／秒は、例として、Ｍｂｉｔ／秒またはＭｂｙｔｅ／秒であるものと想定する。また、ＭＡＰ  ｉからＩＰＳＧ  ｊまでのリンク上の単位帯域幅費用（１単位／秒）はａｉｊであり、ＩＰＳＧ  ｊからＣＰＥ  ｋまでのリンク上の単位帯域幅費用はｅ１ｊｋであり、ＩＰＳＧノードを使用することの現在の費用は、ｆｊであるものと想定する。
【０１１８】
２値変数ｙｌ∈｛０，１｝は、顧客ｌがトラフィックを自らのＣＰＥの少なくとも１つに送信するようにＩＰＳＧ  ｊが用意されている（ｐｒｏｖｉｓｉｏｎｅｄ）場合、１であり、顧客１にＩＰＳＧ  ｊが用意されていない場合、０である。２値変数ｗｌ∈｛０，１｝は、ネットワーク内で顧客ｌにサービス提供が行われる場合、１であり、それ以外の場合、０である。ＰＣＡＰは、各ＩＰＳＧ上でサービス提供を受けることが可能な顧客の最大数を表し、ｆｊは、顧客ｉがノードｊを使用する費用を表す。ＩＰＳＧにおける各顧客に関するサービス提供費用は、同一であるものと想定する。方法９００は、次に、工程９０４に進む。
【０１１９】
工程９０４で、各ＭＡＰ２０８から各ＩＰＳＧ２０６までの動的トンネルに沿ってトラフィックを送信することの費用（ｃｌｉｊ）が、各顧客ｌに関して算出される。詳細には、ＭＡＰ  ｉ∈ＰからＩＰＳＧ  ｊ∈Ｑへのトラフィックに関する帯域幅要件は、
【数３４】
2004260833.tif 000030
である。したがって、ＭＡＰ  ｉとＩＰＳＧ  ｌの間の各顧客１に関する帯域幅費用は、
【数３５】
2004260833.tif 000031
である。
【０１２０】
同様に、工程９０６で、各ＩＰＳＧ２０６から各ＣＰＥ２２２までの静的トンネルに沿ってトラフィックを送信することの費用（ｄｌｊｋ）、およびＩＰＳＧノード（ｊ）２０６を使用することの現在の費用（ｆｊ）が、各顧客ｌに関して算出される。詳細には、ＩＰＳＧ  ｊ∈ＱからＣＰＥ  ｋ∈Ｒｌへのトラフィックに関する帯域幅要件は、
【数３６】
2004260833.tif 000032
である。したがって、ＩＰＳＧ  ｊとＣＰＥ  ｋの間の各顧客ｌに関する帯域幅費用は、
【数３７】
2004260833.tif 000033
である。したがって、パラメータｃｌｉｊおよびｄｌｊｋはそれぞれ、ノードｉからノードｊにトラフィックを送信することの帯域幅費用、およびノードｊからノードｋにトラフィックを送信することの帯域幅費用を表す。
【０１２１】
工程９０８で、動的トンネルの総帯域幅費用（ＣＣ１）が、ＭＡＰ（図６のｐｉ）とＩＰＳＧ（図６のｑｊ）の間におけるのと同様に定式化される。具体的には、動的トンネルの帯域幅費用は、
【数３８】
2004260833.tif 000034
である。さらに、工程９１０で、静的トンネル帯域幅費用（ＣｌＣ２）が、ＩＰＳＧ（図６のｑｉ）とＣＰＥ（図６のｒｌｋ）の間におけるのと同様に定式化される。具体的には、静的トンネルの帯域幅費用は、
【数３９】
2004260833.tif 000035
である。
【０１２２】
サービス・プロバイダ利益は、サービス提供を受けるＶＰＮ顧客の最適なセットを選択し、それぞれの選択されたＶＰＮ顧客にサービス提供を行う最適なＩＰＳＧを選択することによって最大化することができる。利益（Ｕｌ＝γＶｌ−Ｃｌ）は、重み付けされた収益（γＶｌ）と費用（Ｃｌ）の差であり、ただし、顧客に関する収益（Ｖｌ）は、顧客がサービス提供を受けることができる場合、固定値であり、γは、費用と比べた収益に課せられる相対的重みである。
【０１２３】
総費用（Ｃｌ）は、いくつかの成分を有し、前述したとおり、ＶＰＮトンネルが確立されるリンクの帯域幅に関する費用、各トンネルを確立する費用、ＩＰＳＧ上で各ＶＰＮ顧客にサービス提供を行う費用、および耐障害性のためのＩＰＳＧサービス提供における冗長性を考慮に入れることを含め、各顧客にサービス提供を行うＩＰＳＧの最良セットを特定することなどである。言い換えれば、各顧客ｌに関して、Ｐの中のすべてのＭＡＰ  ｉおよびＲｌの中のすべてのＣＰＥ  ｋに関して、利益（Ｕｌ）が最大化されるように、Ｑの中のＩＰＳＧ  ｊが選択されて、ｉとｊの間の固有の動的トンネル、およびｊとｋの間の共用静的トンネルが確立される。
【０１２４】
工程９１２で、総トンネル帯域幅費用（ＣｌＣ）が定式化される。総帯域幅費用は、動的トンネル帯域幅費用と静的トンネル帯域幅費用の合計ＣｌＣ＝ＣｌＣ１＋βＣｌＣ２であり、ここで、βは、静的トンネルの帯域幅費用に課される相対的重みである。静的トンネル帯域幅費用に課せられる相対的重みβに影響を与える要因には、アクセス網を介する費用に上乗せしたコア・ネットワークを介してデータをトランスポートする費用が含まれる。
【０１２５】
工程９１４で、ＩＰＳＧノード（ｊ）を設置する（ｐｒｏｖｉｓｉｏｎ）ことの現在の費用ＣｌＶが定式化される。２値変数ｙｌｊ∈｛０，１｝は、顧客ｌが自らのＣＰＥの少なくとも１つにトラフィックを送信するのにＩＰＳＧ  ｊが用意される（ｐｒｏｖｉｓｉｏｎｅｄ）場合、１であり、それ以外の場合、０である。パラメータｆｊを例として、ＩＰＳＧノードｊを使用することの現在の費用として用いている。所与の顧客に関して、任意のＩＰＳＧにおいてせいぜい１つのサービス提供が考慮されている。したがって、ｆｊは、固定値を有し、サービス提供費用は、
【数４０】
2004260833.tif 000036
である。
【０１２６】
工程９１６で、顧客に関する総費用が定式化される。詳細には、総費用は、Ｃｌ＝ＣｌＣ＋αＣｌＶであり、ここで、αは、サービス提供費用に課せられる相対的重みである。サービス提供費用に課せられる相対的重みαに影響を与える要因には、ネットワーク・サービス・プロバイダの帯域幅費用に上乗せしたサービス提供費用の重要度が含まれる。
【０１２７】
工程９１８で、利益が定式化される。一般に、利益は、Ｕｌ＝γＶｌ−Ｃｌである。一般性を損なうことなく、サービス提供を受ける各顧客に関する収益は同一であるものと想定する。当然、サービス提供を受けない各顧客に関して収益と費用はともにゼロである。収益Ｖｌ＝ｗｌであり、ここで、ｗｌは、ネットワーク内で顧客ｌ∈Ｔがサービス提供を受けるかどうかを表す。したがって、顧客にサービス提供を行うことに関する利益「Ｕｌ」は、Ｕｌ＝γｗｌ−Ｃｌであり、ここで、γは、総費用と比べた収益に課せられる相対的重みである。重み付け係数γは、基本的に、ネットワーク・サービス・プロバイダが、顧客に関する総費用に基づいて価格を調整することを可能にする。
【０１２８】
工程９２０で、所与のパラメータｂｌｉｋ、ａｉｊ、ｅｌｊｋ、ｇｉｊ、ｈｌｊｋ、ｆｊ、α、β、γおよびＰＣＡＰ、整数変数ｓｌｉｊｋ、２値変数ｙｌｊおよびｗｌが、以下のとおり表現される最適化問題定式に対する解として算出される。
【数４１】
2004260833.tif 000037
ただし
【数４２】
2004260833.tif 000038
【０１２９】
数式（４６）は、数式（４５）の拡張されたバージョンであることに留意されたい。数式（５０）は、顧客にサービス提供を受ける場合にだけ顧客の帯域幅要件が満たされる必要があるという事実を反映していることにさらに留意されたい。条件（５１乃至５４）は、前述した単一の顧客定式と同様である。条件（５５）および（５６）が追加されて、顧客ｌがＩＰＳＧ上でサービス提供を受けることは、その顧客に関するいくらかのトラフィックがそのＩＰＳＧを介してＣＰＥに送信される場合に限って行われることを指定している。条件（５７）は、顧客に関して、ＩＰＳＧを介して何らかのトラフィックが送信される場合、顧客が、そのＩＰＳＧ上でサービス提供を受けなければならないことを指定している。条件（５８）が追加されて、各ＩＰＳＧ  ｊ上のサービス提供の総数が、ＩＰＳＧ  ｊの容量ＰＣＡＰを超えることができないことを指定している。条件（２６）が追加されて、顧客ｌがサービス提供を受けない場合、ｙｌｊが０になるように強制されることを確実にしている。
【０１３０】
図８および９の工程８２０および９２０の整数プログラミング問題を解決するため、単位帯域幅費用ａｉｊ、ｅｌｊｋ、およびサービス提供費用ｆｊに適切な値を割り当てる必要がある。この費用割当ては、ＮＳＰの設計目的に合うように適合させることができる。これにより、定式化が極めて一般的になり、異なるシナリオに関して使用することができる。例えば、ＮＳＰは、ＶＰＮ顧客からの特別な要件を満たして、その顧客のユーザを遠隔の負荷の軽いＩＰＳＧに切り替えることによってＮＳＰに関する総費用を低減することができる場合でも、それを行わないようにすることを望むものと想定する。より具体的には、顧客の要件は、東海岸の企業イントラネットにアクセスしようと試みている東海岸のＭＮが、対応するＭＡＰによって西海岸のＩＰＳＧに宛先変更されることが、その宛先変更で総費用が最小限に抑えられる場合でも行われるべきでないことであるものと想定する。その制約を考慮に入れるのに、西海岸のＩＰＳＧにＭＡＰを接続するリンク（パス）に関する帯域幅容量を０に設定すること、またはそのリンク上の単位帯域幅費用を無限大に設定することができる。例えば、ＶＰＮ顧客に関して、東海岸のＭＡＰ  ｉおよび西海岸のＩＰＳＧ  ｊを所与として、ａｉｊ＝∞であるか、またはｇｉｊ＝０であるように入力パラメータを割り当てることができる。
【０１３１】
単一の顧客が考慮される場合、各ＩＰＳＧにおけるサービス提供の既存の数を反映するようにサービス提供費用を設定するオプションを有する。例えば、ｆｊ＝ｃａｐｊ／ａｖａｉｌｊを使用することができ、ここで、ｃａｐｊは、ＩＰＳＧ  ｊの容量であり、ａｖａｉｌｊは、残っている可用なサービス提供の数である。この費用割当てにより、すべてのＩＰＳＧにわたってＩＰＳＧごとのサービス提供の数の均一な配分がもたらされる。ただし、複数の顧客が考慮される場合、異なる顧客に関するサービス提供費用は、整数プログラミング・プログラムに対する有効な入力であるためには同一でなければならない。一般性を損なうことなく、すべての顧客に関するＩＰＳＧ  ｊに関してｆｊ＝１に設定される。
【０１３２】
リンクに関する単位帯域幅費用は、そのリンクによって表されるパス上のホップ・カウントに正比例することを反映するために、ＭＡＰノードｉからＩＰＳＧノードｊまでのホップ数、およびＩＰＳＧノードｊからＣＰＥノードｋまでのホップ数にそれぞれ単位帯域幅費用ａｉｊおよびｅｌｊｋが割り当てられる。帯域幅要求と帯域幅容量の間の関係を例示するため、その値の範囲を制限する。帯域幅要求ｂｌｉｋには、範囲［０，ｍ］内のランダムな整数が割り当てられ、ただし、ｍは、１より大きい整数に等しい。帯域幅容量ｇｉｊには、範囲［Ｇ，Ｇ＋ｍ］内のランダムな整数が割り当てられ、ただし、Ｇ＞０は、ｂｌｉｋの範囲に対するｇｉｊの範囲上の移動である。同様に、帯域幅容量ｈｌｊｋには、範囲［Ｈ，Ｈ＋ｍ］内のランダムな整数が割り当てられ、ただし、Ｈ＞０は、ｂｌｉｋの範囲に対するｈｌｊｋの範囲上の移動である。費用および容量の割当て段階は、顧客特有の要件を考慮に入れる。これが行われると、ＣＰＬＥＸなどの整数プログラミング・パッケージ（すなわち、線形プログラミング問題、混合整数プログラミング問題、２次プログラミング問題を解決するための）を使用して特定のパラメータ設定に関する解を生成することができる。
【０１３３】
したがって、本発明は、ネットワーク・ベースのモバイルＶＰＮサービスを提供するための階層式アーキテクチャを提供する。階層式アーキテクチャにより、モバイル・ユーザにデータ接続を提供するモバイル・アクセス・ポイント（ＭＡＰ）が、モバイルＶＰＮサービスを提供するＩＰサービス・ゲートウェイ（ＩＰＳＧ）から物理的に分離していることが要求される。階層式アーキテクチャにより、ネットワーク内のリソースのより効率的な使用が可能になる。階層式アーキテクチャに基づき、ＩＰＳＧ上でモバイルＶＰＮ顧客にサービス提供を行うことの問題を、そのようなサービスを提供することによってネットワーク・サービス・プロバイダ（ＮＳＰ）によって実現される利益が最大化されるように解決することができる。モバイルＶＰＮサービスを提供することの費用には、被る帯域幅の費用、ならびにＩＰＳＧ上で顧客にサービス提供を行うことの費用が含まれる。ＮＳＰが直面する制約には、サービス・プロバイダ・ネットワークの一部を形成するデバイスを接続するリンク上の帯域幅制限、およびＩＰＳＧ上でサービス提供を受けることが可能な顧客の最大数の制限が含まれる。整数プログラミング定式化を使用して、モバイルＶＰＮ顧客にサービス提供を行うことの以上の問題に対処する。定式化は一般的であり、ネットワーク・トポロジおよび他のパラメータの実際的な構成を解決するために使用することができ、様々なＮＳＰ要件が考慮されることを可能にする。結果は、モバイルＶＰＮアーキテクチャの設計の見通しをもたらし、設計プロセスに関わるトレードオフに役立ち、そのトレードオフを実証する。
【０１３４】
本発明の教示を組み込んだ様々な実施形態を本明細書で詳細に示し、説明してきたが、当分野の技術者は、これらの教示をやはり組み込んだ多くの他の様々な実施形態を用意に考案することができよう。
【図面の簡単な説明】
【０１３５】
【図１】例示的な従来技術のモバイルＩＰネットワークを描いた高レベル・ブロック図である。
【図２】本発明の例示的なモバイルＩＰネットワークを描いた高レベル・ブロック図である。
【図３】リンク費用に基づいて仮想プライベート・ネットワーク（ＶＰＮ）サービスを提供するための方法を描いた流れ図である。
【図４】単一の顧客に関する第１の無向グラフを描いた概略図である。
【図５】図３の方法による単一のＶＰＮ顧客にサービス提供を行う（ｐｒｏｖｉｓｉｏｎ）ＩＰサービス・ゲートウェイ（ＩＰＳＧ）のサブセットを選択するのに適した方法を描いた流れ図である。
【図６】複数の顧客に関する第２の無向グラフを描いた概略図である。
【図７】帯域幅制約に基づいて仮想プライベート・ネットワーク（ＶＰＮ）サービスを提供するための方法を描いた流れ図である。
【図８】図７の方法に従って帯域幅容量に基づいて単一のＶＰＮ顧客にサービス提供を行う（ｐｒｏｖｉｓｉｏｎ）ＩＰサービス・ゲートウェイ（ＩＰＳＧ）のサブセットを選択するのに適した方法を描いた流れ図である。
【図９】図７の方法に従って帯域幅容量に基づいて複数のＶＰＮ顧客にサービス提供を行う（ｐｒｏｖｉｓｉｏｎ）ＩＰサービス・ゲートウェイ（ＩＰＳＧ）のサブセットを選択するのに適した方法を描いた流れ図である。
【図１】
2004260833.tif 000045
【図２】
2004260833.tif 000046
【図３】
2004260833.tif 000047
【図４】
2004260833.tif 000048
【図５】
2004260833.tif 000049
【図６】
2004260833.tif 000050
【図７】
2004260833.tif 000051
【図８】
2004260833.tif 000052
【図９】
2004260833.tif 000053