(57)【要約】  本発明は、複数のタイプ１ノードと、複数のタイプ２ノードとを含むネットワーク内で使用するための経路選択表を決定するための方法および装置を含み、タイプ２ノードは、ネットワークの複数の宛先ノードの各々に関連する１つの次ホップノードを有するそれぞれのタイプ２経路選択表を使用する。方法は、タイプ１ノードおよびタイプ２ノードから、ネットワークの複数のリンクの各々に関連するリンク状態情報を取得することと、タイプ１ノードおよびタイプ２ノードからトラフィック測定情報を取得することと、リンク状態とトラフィック測定情報とを使用して、それぞれのタイプ１ノードに関するタイプ１経路選択表を決定することとを含む。タイプ１経路選択表は、実質的に調整された方法で、グループとして決定され、各タイプ１経路選択表は、宛先ノードの各々に関する複数の次ホップノードを含む。
2009532941.tif 000002
【特許請求の範囲】
【請求項１】
複数のタイプ１ノードと複数のタイプ２ノードとを含むネットワーク内で使用するために経路選択表を決定するための方法であって、それぞれのタイプ２経路選択表を使用するタイプ２ノードは、複数の宛先ノードの各々に関連する１つの次ホップノードを含み、前記方法は
タイプ１ノードおよびタイプ２ノードからネットワークの複数のリンクの各々に関連するリンク状態情報を取得することと、
タイプ１ノードおよびタイプ２ノードからトラフィック測定情報を取得することと、
リンク状態情報とトラフィック測定情報とを使用して、それぞれのタイプ１ノードに関する複数のタイプ１経路選択表を決定することとを含み、タイプ１経路選択表は、実質的に調整された方法で、グループとしてタイプ１ノードに関して決定されており、各タイプ１経路選択表は、宛先ノードの各々に関連する複数の次ホップノードを含む、方法。
【請求項２】
リンク状態情報がリンク重み情報とリンク容量情報とを含む、請求項１に記載の方法。
【請求項３】
トラフィック測定情報が、リンク利用情報と、注入されたトラフィック情報と、制御可能なトラフィック情報または制御不可能なトラフィック情報のうちの１つとを含む、請求項１に記載の方法。
【請求項４】
タイプ１経路選択表の各々を決定することが、
タイプ１ノードおよび前記複数のタイプ２ノードからの少なくとも１つの宛先ノードの各組合せに関して、タイプ１ノードによって注入されたトラフィック量を含む、注入されたトラフィック値を決定することと、
タイプ１ノードに結合された少なくとも１つのリンクの各々に関して制御不可能なトラフィック値を決定することと、
注入されたトラフィック値と制御不可能なトラフィック値とを使用してタイプ１経路選択表を決定することと
を含む、請求項１に記載の方法。
【請求項５】
タイプ１ノードおよび少なくとも１つの宛先ノードの各組合せに関して注入されたトラフィック値を決定することが、
タイプ１ノードおよび少なくとも１つの宛先ノードの各組合せに関して横断したトラフィック値を決定することであって、各横断したトラフィック値が、タイプ１ノードを横断する少なくとも１つの宛先ノード宛のトラフィック量を含むことと、
横断したトラフィック値を使用して注入されたトラフィック値を決定することと
を含む、請求項４に記載の方法。
【請求項６】
タイプ１ノードおよび少なくとも１つの宛先ノードの各組合せに関して注入されたトラフィック値を決定することが、
タイプ１ノードおよび少なくとも１つの宛先ノードの各組合せに関して横断したトラフィック値を決定することと、
タイプ１ノードから中間ノードを横断する少なくとも１つの宛先ノードまでのユニットフローのフラクションを含む第１のユニットフローフラクションを決定することと、
横断したトラフィック値と第１のユニットフローフラクションとを使用して、注入されたトラフィック値を決定することと
を含む、請求項４に記載の方法。
【請求項７】
タイプ１ノードに結合された少なくとも１つのリンクの各々に関して制御不可能なトラフィック値を決定することが、
少なくとも１つのリンクの各々に関して総フローを決定することと、
少なくとも１つのリンクの各々に関して第２のユニットフローフラクションを決定することと、
総フローと、第２のユニットフローフラクションと、注入されたトラフィック値とを使用して、制御不可能なトラフィック値を決定することと
を含む、請求項４に記載の方法。
【請求項８】
少なくとも１つのリンクの各々に関して総フローを決定することが、
複数のノードの各々からトポロジー情報を取得することと、
少なくとも１つのリンクの各々に関連するリンク重み情報を取得することと、
少なくとも１つのリンクの各々に関連するトポロジー情報と前記リンク重み情報とを使用して、少なくとも１つのリンクの各々に関して総フローを決定することと
を含む、請求項７に記載の方法。
【請求項９】
複数のタイプ１ノードと複数のタイプ２ノードとを含むネットワーク内で使用するための経路選択表を決定するための装置であって、タイプ２ノードは、複数の宛先ノードの各々に関連する１つの次ホップノードを含むそれぞれのタイプ２経路選択表を使用し、
タイプ１ノードおよびタイプ２ノードからネットワークの複数のリンクの各々に関連するリンク状態情報を取得するための手段と、
タイプ１ノードおよびタイプ２ノードからトラフィック測定情報を取得するための手段と、
リンク状態情報とトラフィック測定情報とを使用して、それぞれのタイプ１ノードに関する複数のタイプ１経路選択表を決定するための手段とを含み、タイプ１経路選択表が、実質的に調整された方法で、グループとしてタイプ１ノードに関して決定されており、各タイプ１経路選択表が、宛先ノードの各々に関連する複数の次ホップノードを含む、装置。
【請求項１０】
複数のタイプ１ノードと複数のタイプ２ノードとを含むネットワーク内の複数のタイプ１ノードのうちの１つでトラフィックを経路選択するための方法であって、タイプ２ノードは、複数の宛先ノードの各々に関連する１つの次ホップノードを含む、それぞれのタイプ２経路選択表を使用し、前記方法は
宛先ノードの各々に関連する複数の次ホップノードを含む、関連するタイプ１経路選択表を使用して、タイプ１ノードのうちの１つでトラフィックを経路選択することを含み、
タイプ１ノードのうちの１つに関連するタイプ１経路選択表を含む複数のタイプ１経路選択表が、タイプ１ノードおよびタイプ２ノードからのリンク状態情報とトラフィック測定情報とを使用して決定され、タイプ１経路選択表が、実質的に調整された方法で、グループとしてタイプ１ノードに関して決定されている、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信ネットワークの分野に関し、より詳細には、コネクションレス型ネットワーク内の経路選択に関する。
【背景技術】
【０００２】
コネクションレス型ネットワークの拡張性および回復性（ｒｅｓｉｌｉｅｎｃｙ）は、インターネットの偏在および急速な成長から明らかである。コネクションレス型ネットワークの成功にもかかわらず、多くのサービスプロバイダは、ネットワークトラフィックエンジニアリングなど、世界的な目的を達成するためにコネクション型ネットワークを使用する。これは主に、コネクション型ネットワーク内のトラフィック管理は、コネクションレス型ネットワーク内のトラフィック管理よりも操作的により簡単であるという事実による。具体的には、サービスプロバイダは、多くの場合、レイヤ１コネクションレス型ネットワークに関する世界的な目的を達成するためにレイヤ２コネクション型ネットワークを使用する。例は、インターネットプロトコル（ＩＰ）トラフィックを運ぶためのマルチプロトコルラベルスイッチング（ＭＰＬＳ）の使用である。
【０００３】
コネクション型ネットワークでは、トラフィックは、通常、所定の経路に沿って、発信元から宛先に経路選択される。これらの所定の経路は個々に確立および操作され得るため、ネットワーク内の変化するトラフィック条件に対応するために所定の経路を調整することが可能である。変化するトラフィック条件のこの対応は、所定の経路に関連するトラフィックに関してサービス保証の質を提供するために重要である。不利なことに、コネクション型ネットワークは、ネットワーク内で発生するトラフィックフローをサポートするための経路確立を要求し、コネクション型ネットワークのスケーリングを困難にする。さらに、ネットワーク内の故障は、復元経路の明示的な確立を要求し、それにより、コネクションレス型ネットワークの操作的な容易さを低減する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
コネクションレス型ネットワーキングの配備および拡張性の容易さにもかかわらず、コネクション型ネットワーキングを使用するのは、コネクションレス型ネットワークは、通常、最短経路、すなわち、ホップバイホップ経路選択を使用するという事実による。最短経路、すなわち、ホップバイホップ経路選択の使用は、（例えば、ＯＳＰＦなど、広く配備された経路選択プロトコルを使用して行われるような）最善努力の接続性を維持するために適しているが、サービスプロバイダにとって接続性を維持することは唯一の目的ではない。接続性を維持することに加えて、サービスプロバイダは、効率的なトラフィック管理、効果的な容量使用（例えば、いくつかのリンク上の混雑を回避し、一方、その他のリンクは依然として十分利用されない状態である）、および同様の目的を追求する。不利なことに、かかるネットワークの範囲にわたる目的は、コネクションレス型ネットワークで現在用いられている経路選択よりも、コネクション型ネットワークを用いて満たすほうがより容易であるものの、コネクション型ネットワークはコネクションレス型ネットワークほど拡張性がない。
【課題を解決するための手段】
【０００５】
先行技術における様々な欠陥は、複数のタイプ１ノードと複数のタイプ２ノードとを含むネットワーク内の使用のために経路選択表を決定するための方法および装置の発明を介して対処され、タイプ２ノードは、ネットワークの複数の宛先ノードの各々に関連する１つの次ホップノード（ｎｅｘｔ−ｈｏｐ  ｎｏｄｅ）を有するそれぞれのタイプ２経路選択表を使用する。方法は、タイプ１ノードおよびタイプ２ノードから、ネットワークの複数のリンクの各々に関連するリンク状態情報を取得することと、タイプ１ノードおよびタイプ２ノードからトラフィック測定情報を取得することと、リンク状態とトラフィック測定情報とを使用して、それぞれのタイプ１ノードに関するタイプ１経路選択表を決定することとを含む。タイプ１経路選択表は、実質的に調整された方法で、グループとして決定され、各タイプ１経路選択表は、宛先ノードの各々に関連する複数の次ホップノードを含む。
【０００６】
本発明の教示は、添付の図面と共に、以下の詳細な説明を考慮することによって容易に理解され得る。
【０００７】
理解を円滑にするために、可能な場合、図面に共通する同一要素を指定するために、同一の参照番号が使用されている。
【発明を実施するための最良の形態】
【０００８】
本発明は、通常、コネクション型ネットワーク内で達成されるトラフィック管理機能がコネクションレス型ネットワークで達成されることを可能にする。本発明は、ネットワーク内の標準ノード（例えば、標準ルータ）の一部をフレキシブルノード（すなわち、フレキシブルルータ）に置き換える。標準ルータは、標準トラフィック経路選択能力（すなわち、最短経路選択）を含む。標準ノードは、それぞれの標準ノードによって局所的に決定された経路選択表を使用して、所与の宛先ノードに関して次ホップノードを選択する。フレキシブルノードは、拡張トラフィック経路選択能力（例えば、トラフィックを宛先ノードに向けて経路選択するために２つ以上の次ホップノードから選択する際の追加の柔軟性）を含む。フレキシブルノードは、標準ノードおよびフレキシブルノードから取得された情報を使用して、コントローラによって中央で決定されたそれぞれの経路選択表を使用して、所与の宛先ノードに関して複数の次ホップノードのうちの１つを選択する。
【０００９】
本発明では、それぞれのフレキシブルノードに関連する経路選択表はコントローラによって決定される。コントローラは（例えば、１つまたは複数のプロトコルを使用して）標準ノードおよびフレキシブルノードからリンク状態情報を取得する。標準ノードおよびフレキシブルノードは、トラフィック測定を実行して、トラフィック測定情報をコントローラに提供する。コントローラは、それぞれのフレキシブルノードに関する経路選択表を決定するために、リンク状態とトラフィック測定情報とを使用する。コントローラは、実質的に調整された方法で、グループとしてフレキシブルノードに関する経路選択表を決定する。コントローラは、経路選択トラフィックに関してそれぞれのフレキシブルノードに経路選択表を配布し、それにより、それぞれのフレキシブルノードのグループの経路選択表の全域で調整された経路選択表変更を実施することによって、コントローラがネットワーク内のトラフィックを操作することを可能にする。
【００１０】
本発明は、コネクションレス型ネットワーキングの拡張性を維持すると同時に、ネットワークが不測のトラフィックパターンを処理することを可能にする。すなわち、本発明は、異なるトラフィックパターンに対応するために順応的かつ動的にネットワーク内の経路選択を変更することによってトラフィックを管理する能力を提供すると同時に、コネクションレス型ネットワークの回復性と拡張性とを維持する。一実施形態では、本発明は、コネクションレス型ネットワーク内で利用される既存のプロトコルへの修正が要求されないような方法で実施される。一実施形態では、本発明は、フレキシブルノードが標準ノードと共に途切れなく相互運用するような方法で実施される（すなわち、拡張フレキシブルノードは既存の標準ノードと後方互換性である）。
【００１１】
図１は、通信ネットワークのハイレベルのブロック図を示す。具体的には、図１の通信ネットワーク１００は、ネットワーク１１０とコントローラ１２０とを含む。図１で示されるように、ネットワーク１１０は、複数の標準ルータ（ＳＲ）１１２Ｓ１、１１２Ｓ３−１１２Ｓ８、１１２Ｓ１０−１１２Ｓ１３、および１１２Ｓ１５（集合的に、ＳＲ１１２Ｓ）と、複数のフレキシブルルータ（ＦＲ）１１２Ｆ２、１１２Ｆ９、および１１２Ｆ１４（集合的に、ＦＲ１１２Ｆ）とを含む。ＳＲ１１２ＳおよびＦＲ１１２Ｆは、集合的にルータ１１２として示されることが可能である。ＳＲ１１２ＳおよびＦＲ１１２Ｆは、一般に、それぞれ、タイプ２ノードおよびタイプ１ノードと呼ばれる場合がある。ルータ１１２は、ネットワーク１１０内で運ばれるトラフィックのために、発信元ノード、中間ノード、および宛先ノードとして動作する。明確にする目的で、各ルータ１１２は、整数を使用して識別され得る（例えば、それぞれ、１１２Ｓ１、１１２Ｓ３−１１２Ｓ８、１１２Ｓ１０−１１２Ｓ１３、および１１２Ｓ１５はノード１、３−８、１０−１３、および１５として示され、ＦＲ１１２Ｆ２、１１２Ｆ９、および１１２Ｆ１４はノード２、９および１４として示される）。
【００１２】
図１に示されたように、ルータ１１２は、複数の通信リンク（ＣＬ）１１４（集合的に、ＣＬ１１４）を使用して通信する。一実施形態では、ＣＬ１１４の各々は双方向通信リンクである。一実施形態では、ＣＬ１１４は、少なくとも１つの関連するリンクパラメータ（例えば、リンク重み、リンク容量、リンク帯域幅など、ならびに、それらの様々な組合せ）を有する。一実施形態では、明確にする目的で、ＣＬ１１４の各々は１に等しい関連するリンク重みを有すると仮定され得る。図１に示されたように、ＦＲ１１２Ｆは、複数の管理リンク（ＭＬ）１２２（集合的にＭＬ１２２）を使用して、コントローラ１２０と通信する。明確にする目的で、コントローラ１２０は、ＳＲ１１２Ｓと通信するとして示されないが、コントローラ１２０は、１つまたは複数のリンクを使用して直接的に、ＦＲ１１２Ｆおよび関連するＣＬ１１４など、ならびにそれらの様々な組合せを経由して間接的にＳＲ１１２Ｓと通信することが可能である。
【００１３】
ＳＲ１１２Ｓは、標準のホップバイホップパケット転送機構を利用するために動作可能な（本明細書で、標準ノード、非フレキシブルルータ、または非フレキシブルノードと呼ばれる場合がある）標準ルータを含む。ＳＲ１１２Ｓは、所与の宛先ノードのために単一の次ホップノードをサポートする（通常、非フレキシブルノード経路選択表またはタイプ２経路選択表と呼ばれる）経路選択表を利用する。一実施形態では、例えば、次ホップノードは、標準オープンショーテストパスファースト（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）（ＯＳＰＦ）ネットワーク内でのように計算され得る。一実施形態では、ＳＲ１１２Ｓは、ネットワーク１１０内のネットワーク情報（例えば、トポロジー情報、リンク状態情報、利用可能なリンク帯域幅情報など、ならびにそれらの様々な組合せ）をブロードキャストする。一実施形態では、例えば、ネットワーク情報は、ＯＳＰＦリンク状態広告（ＯＳＰＦ−ＬＳＡ）メッセージおよびＯＳＰＦトラフィックエンジニアリング（ＯＳＰＦ−ＴＥ）メッセージを使用して、ＳＲ１１２Ｓによってブロードキャストされる。１つのかかる実施形態では、ＳＲ１１２Ｓによってブロードキャストされたネットワーク情報のうちの少なくとも一部は、コントローラ１２０によって受信される。
【００１４】
ＦＲ１１２Ｆは、拡張パケット転送機構を利用するために動作可能な（本明細書で、拡張ノード、フレキシブルルータ、またはフレキシブルノードと呼ばれる場合がある）拡張ルータを含む。ＦＲ１１２Ｆは、所与の宛先ノードのために複数の次ホップノードをサポートする（通常、フレキシブルノード経路選択表またはタイプ１経路選択表と呼ばれる）拡張経路選択表を利用する。ＦＲ１１２Ｆによって使用される拡張経路選択表は、コントローラ１２０によって計算され得る。一実施形態では、ＦＲ１１２Ｆは、トラフィック測定情報を作成するためにトラフィック測定を実行する。１つのかかる実施形態では、トラフィック測定情報は、注入された（ｉｎｊｅｃｔｅｄ）トラフィック情報、制御不可能なトラフィック情報など、ならびにそれらの様々な組合せを含み得る。一実施形態では、ＦＲ１１２Ｆは、かかるトラフィック測定情報をコントローラ１２０に提供する。一実施形態では、ＳＲ１１２ＳはＦＲ１１２Ｆの存在を知らない。
【００１５】
一実施形態では、所与の宛先ノードに関して複数の次ホップが存在する場合、ＦＲ１１２Ｆは、事前に特定された方法で、複数の次ホップノードの全域で宛先ノードにトラフィックを分割することが可能である。複数の次ホップノードの全域で宛先ノードにトラフィックを分割するいくつかの方法が存在する。一実施形態では、複数の次ホップノードの全域でトラフィックを宛先ノードに分割することは、所与のトラフィックフローが複数の次ホップノードの全域で分割されないことを確実にするための方法で実行され得る。１つのかかる実施形態では、所与のトラフィックフローが複数の次ホップノードの全域で分割されないことを確実にするための方法で、複数の次ホップノードの全域で宛先ノードにトラフィックを分割するために少なくとも１つの追加のトラフィック測定が要求される。
【００１６】
図１に示されるように、コントローラ１２０は、ＦＲ１１２Ｆに関する経路選択表を決定する。一実施形態では、コントローラ１２０は、ＦＲ１１２Ｆに関する経路選択表を決定するために、ＳＲ１１２ＳおよびＦＲ１１２Ｆからのリンク状態情報とＦＲ１１２Ｆからのトラフィック状態情報とを利用する。一実施形態では、ＦＲ１１２Ｆに関する経路選択表の決定は、ＦＲ１１２Ｆの既存の経路選択表を動的に修正することを含む。ＦＲ１１２Ｆに関連する既存の経路選択表を動的に修正することは、コントローラ１２０がネットワーク１１０内のトラフィック条件を変更するためにＦＲ１１２Ｆを適合させることを可能にする。一実施形態では、コントローラ１２０は、ＦＲ１１２Ｆの全域で調整されたトラフィック経路選択変更を実施し、それにより、ネットワーク１１０内の変化するトラフィック条件に応答して、効果的なトラフィック経路選択管理（例えば、低い遅延、低いパケット損失など）を可能にする目的でＦＲ１１２Ｆの経路選択表の少なくとも一部を変更するためにＦＲ１１２Ｆの経路選択表を処理する。
【００１７】
特定数のＳＲ１１２ＳおよびＦＲ１１２Ｆを含めて、特定の構成を含むとして示され、説明されるが、本発明は、ＳＲ１１２ＳおよびＦＲ１１２Ｆの様々なその他の構成を有する通信ネットワーク内で使用されることが可能である。管理システムとして示されるが、一実施形態では、コントローラ１２０は、ルータの一部として実施され得る。一実施形態では、コントローラ１２０は、ＳＲ１１２Ｓのうちの１つまたはＦＲ１１２Ｆのうちの１つの一部として実施されることが可能であり、またはその代わりに、コントローラ１２０の機能性の一部は、ＳＲ１１２ＳもしくはＦＲ１１２Ｆの様々な組合せを通して分割されることが可能である。一実施形態では、コントローラ１２０は、ネットワーク１１０内のルータ（図示せず）として実施され得る。１つのかかる実施形態では、ルータは、フレキシブルノード経路選択表を計算するために状態メッセージを受信するようにだけ構成され得る（すなわち、ルータはネットワーク１１０内のトラフィックを経路選択しない）。
【００１８】
図２は、本発明の一実施形態による方法を示す。具体的には、図２の方法２００は、それぞれのフレキシブルノードに関連する経路選択表を決定するための方法を含む。複数のフレキシブルノードに関する経路選択表を決定することに関して説明されるが、方法２００は１つのフレキシブルノードを有するネットワークに関する経路選択表を決定するために使用されることが可能である。本明細書で、連続的に実行されるとして示され、説明されるが、当業者は、方法２００のステップのうちの少なくとも一部は、同時に、または図２で提示されたのと異なる順序で実行され得る点を理解されよう。方法２００は、ステップ２０２で始まり、ステップ２０４に進む。
【００１９】
ステップ２０４で、リンク状態情報は非フレキシブルノードおよびフレキシブルノードから受信される。一実施形態では、リンク状態情報は、通信リンクに関連するリンク重みを含む。１つのかかる実施形態では、リンク重みは、ＯＳＰＦリンク状態広告（ＯＳＰＦ−ＬＳＡ）メッセージを使用して受信され得る。一実施形態では、リンク状態情報は、通信リンクに関連するリンク容量（および／または利用可能なリンク帯域幅）を含む。１つのかかる実施形態では、リンク容量はＯＳＰＦトラフィックエンジニアリング（ＯＳＰＦ−ＴＥ）メッセージを使用して受信され得る。一実施形態では、リンク状態情報は、フレキシブルノードに関する経路選択表を決定するように構成されたセントラルコントローラ（例示的に、コントローラ１２０）によって受信される。
【００２０】
ステップ２０６で、トラフィック測定情報は、非フレキシブルノードおよびフレキシブルノードから受信される。一実施形態では、トラフィック測定情報は、リンク利用情報を含む。一実施形態では、リンク利用情報は、ネットワーク内のリンクの少なくとも一部の各々の利用の測定を含む。一実施形態では、各フレキシブルノードおよび非フレキシブルノードは、そのノードが直接的に接続されるリンクの各々に対するリンク利用を測定する。一実施形態では、リンク利用は、関連するリンクの総リンク容量の割合として表されることが可能である。一実施形態では、トラフィック測定情報は、注入されたトラフィック情報と制御不可能なトラフィック情報とを含む。
【００２１】
一実施形態では、注入されたトラフィック情報および制御不可能なトラフィック情報は、それぞれのフレキシブルノードによって決定される。注入されたトラフィック情報を決定するための例示的な方法は、本明細書において、図３、図４、図５および図６に関して示され、説明される。制御不可能なトラフィック情報を決定するための例示的な方法は、本明細書において、図３、図４、図５および図７に関して示され、説明される。一実施形態では、トラフィック測定情報は、フレキシブルノードに関する経路選択表を決定するように構成されたセントラルコントローラ（例示的に、コントローラ１２０）によって受信される。
【００２２】
ステップ２０８で、それぞれのフレキシブルノードに関連する経路選択表は、リンク状態情報およびトラフィック測定情報を使用して決定される。一実施形態では、それぞれのフレキシブルノードに関連する経路選択表は、グループとして一緒に決定され得る（すなわち、フレキシブルノードグループ内の各フレキシブルノードに関する各経路選択表は、そのフレキシブルノードグループ内の１つおきのフレキシブルノードに関して１つおきの経路選択表に関連するそれぞれの少なくとも１つの特性を考慮に入れて決定される）。一実施形態では、少なくとも１つの特性は、それぞれのフレキシブルノードに関して予め計算された経路選択表、そのグループ内の１つおきのフレキシブルノードに関する１つおきの経路選択表が決定される現在の処理、および同様の特性、パラメータ、および情報、ならびにそれらの様々な組合せを含み得る。
【００２３】
一実施形態では、フレキシブルノードは、１つのフレキシブルノードグループと関連づけられることが可能である。一実施形態では、フレキシブルノードは、複数のフレキシブルノードグループと関連づけられることが可能である。一実施形態では、セントラルコントローラ（例示的に、コントローラ１２０）は、どのフレキシブルノードがどの（１つまたは複数の）フレキシブルノードグループと関連づけられるかを表示するフレキシブルノードグループ会員情報を維持する。かかる実施形態では、フレキシブルノードグループ内のそれぞれのフレキシブルノードに関連する経路選択表は、フレキシブルノードの経路選択表を決定および設定することによって、コントローラがそれによりネットワーク内のトラフィックを操作することができるように調整された方法で決定され得る。
【００２４】
一実施形態では、フレキシブルノード経路選択表は、その宛先ノードに向かう、宛先ノードに関連するトラフィックを経路選択するためのフレキシブルノードによる選択のために利用可能な複数の次ホップノードに対する（非フレキシブルノードおよびフレキシブルノードを含む）各可能な宛先ノードの関連性を含む。一実施形態では、フレキシブルノード経路選択表は、各宛先ノードに関する各次ホップノードに関連する関連トラフィック分割フラクション（例えば、複数の経路の全域での所与の宛先ノード宛の分割トラフィックフロー）を含み得る。
【００２５】
ステップ２１０で、経路選択表は、それぞれのフレキシブルノードに通信される。ステップ２１２で、トラフィックは、非フレキシブルノードおよびフレキシブルノードによってネットワークを介して経路選択される。トラフィックは、所与の宛先ノードに関して１つの次ホップノードを識別する、局所的に決定された経路選択表を使用して、非フレキシブルノードによって経路選択される。トラフィックは、所与の宛先ノードに関して複数の次ホップノードを識別する、中央で決定された経路選択表を使用してフレキシブルノードによって経路選択される。ステップ２１４で、方法２００は終了する。
【００２６】
フレキシブルノードに関する経路選択表の決定を説明する際に明確にする目的で、以下の公式を考慮する。ネットワーク（例示的に、ネットワーク１１０）は、有向リンクＥ（例示的に、通信リンク１１４）のセットによって相互接続されたノードＮ（例示的に、ルータ１１２）のセットを含むと仮定する。ネットワークは、ｎ個のノードとｍ個のリンクとを含むと仮定する。Ｃ⊆Ｎがフレキシブルノードのセット（例示的に、ＦＲ１１２Ｆ）を示し、Ｄ＝Ｎ＼Ｃが非フレキシブルノードのセット（例示的に、ＳＲ１１２Ｓ）を示す表示法が定義される。ｗ（ｅ）がリンクｅ∈Ｅのリンク重み（例えば、ＯＳＰＦリンク重み）を示し、ｃ（ｅ）がリンクｅ∈Ｅのリンク容量（例えば、ＯＳＰＦリンク容量）を示す表示法が定義される。ｆ（ｅ）がリンクｅ∈Ｅ上のトラフィックフローを示す表示法が定義される。すべてのリンクｅ∈Ｅ上のトラフィックフローｆ（ｅ）は、ネットワーク情報配布プロトコル（例えば、ＯＳＰＦ−ＬＳＡ、ＯＳＰＦ―ＴＥなど）からコントローラ（例示的に、コントローラ１２０）に利用可能である。
【００２７】
Ｔｓｄが発信元ノードｓ∈Ｎから宛先ノードｄ∈Ｎへのトラフィックレートを表す表示法が定義される。ノードｕが非フレキシブルノードｕ∈Ｄまたはフレキシブルノードｕ∈Ｃであり得る表示法が定義される。Ｗｕｄが、フレキシブルノードｕ∈Ｃ上で発生するまたはフレキシブルノードｕ∈Ｃを通過する宛先ノードｄ∈Ｎに関する総トラフィック量を表す表示法が定義される。通常、Ｗｕｄ≧Ｔｕｄである点に留意されたい。一実施形態では、フレキシブルノードｕは、宛先ノードｄの各々に関して総トラフィック量Ｗｕｄを測定するために動作可能である。１つのかかる実施形態では、フレキシブルノードｕは、複数の知られている方法のうちの少なくとも１つを使用して、総トラフィック量Ｗｕｄを測定するために動作可能である。一実施形態では、すべての発信元／宛先ノードの対（ｓ、ｄ）に関するトラフィックレートＴｓｄは、コントローラによって知られていない。
【００２８】
一実施形態では、ネットワーク内の各ノードｎは、ネットワーク内の１つおきのノードへの最短経路を計算する。１つのかかる実施形態では、ノードｕ∈Ｎでの経路選択表は、ネットワーク内の各ノードへの最短経路上の次ホップを含む。この実施形態では、ＮＨ（ｕ、ｄ）がノードｕでの宛先ノードｄに関する次ホップノードを示す表記法が定義される。すなわち、この実施形態では、ＮＨ（ｕ、ｄ）は、ノードｕから宛先ノードｄまでの最短経路上の第１のノードを示す。明確にする目的で、次ホップノードはすべての非フレキシブルノードｕ∈Ｄに関して独自である、すなわち、ＮＨ（ｕ、ｄ）は各非フレキシブルｕ∈Ｄに関して１つの要素だけを有すると仮定される。
【００２９】
本明細書では、次ホップノードは各非フレキシブルノードｕ∈Ｄに関して独自である、すなわち、ＮＨ（ｕ、ｄ）は各非フレキシブルノードｕ∈Ｄに関して１つの要素だけを有する実施形態に関して主に説明されるが、様々なその他の実施形態では、複数の次ホップノードは各非フレキシブルノードｕに関して利用可能であり得る、すなわち、ＮＨ（ｕ、ｄ）は、各非フレキシブルノードｕ∈Ｄに関して１つまたは複数の要素を有する可能性がある。すなわち、一実施形態では、本発明は、ノード間に代替の最短経路が存在するネットワークに拡張可能である。この実施形態では、トラフィックは、代替の最短経路の間で分割され得る。１つのかかる実施形態では、トラフィックは、等価マルチパス（ｅｑｕａｌ  ｃｏｓｔ  ｍｕｌｔｉ−ｐａｔｈｓ）を使用して代替の最短経路の間で分割され得る。さらに、ＮＨ（ｕ、ｄ）は、本明細書では、すべての非フレキシブルノードｕ∈Ｄに関する最短経路に基づいて計算されているとして主に説明されるが、経路選択ループが存在しない限り、ＮＨ（ｕ、ｄ）は各フレキシブルノードｕ∈Ｃに関して任意に設定されることが可能である。
【００３０】
図３は、図１の通信ネットワークの最短経路ツリーのハイレベルのブロック図を示す。具体的には、図３は、図１の通信ネットワーク１００のノード１３への最短経路ツリー３００のハイレベルのブロック図を示す。図３に示されたように、実線として示される複数のリンク３１０（集合的に、リンク３１０）は、ノード１３への最短経路ツリー３００を表す。最短経路ツリー３００は、フレキシブルノードが非フレキシブルノードとして動作していた場合（すなわち、フレキシブルノードが、拡張された最短経路演算の代わりに標準の最短経路演算を利用していた場合）に生じることになる最短経路ツリーを含む点に留意されたい。図３に示されたように、破線として示される複数の代替のリンク３２０（集合的に、代替のリンク３２０）は、フレキシブルノードに関連する代替のリンクを表す。明確にする目的で、リンク３１０および代替のリンク３２０は、１に等しい関連するリンク重みを有すると仮定される。
【００３１】
図３に示されたように、各非フレキシブルノードｕ∈Ｄに関する次ホップノードＮＨ（ｕ、ｄ）は、ＮＨ（１、１３）＝２、ＮＨ（３、１３）＝２、ＮＨ（４、１３）＝９、ＮＨ（５、１３）＝１２、ＮＨ（６、１３）＝１０、ＮＨ（７、１３）＝１０、ＮＨ（８、１３）＝９、ＮＨ（１０、１３）＝１３、ＮＨ（１１、１３）＝１３、ＮＨ（１２、１３）＝１３およびＮＨ（１５、１３）＝１４を含む。図３に示されたように、フレキシブルノード２∈Ｃに関する次ホップノードＮＨ（ｕ、ｄ）は、ＮＨ（２、１３）＝５（代替の経路）とＮＨ（２、１３）＝１１（最短経路）とを含み、フレキシブルノード９∈Ｃに関する次ホップノードＮＨ（ｕ、ｄ）は、ＮＨ（９、１３）＝７（代替の経路）とＮＨ（９、１３）＝１０（最短経路）とを含み、フレキシブルノード１４∈Ｃに関する次ホップノードＮＨ（ｕ、ｄ）は、ＮＨ（１４，１３）＝１０（代替の経路）とＮＨ（１４、１３）＝１３（最短経路）とを含む。すなわち、フレキシブルノード２は、２個の異なる次ホップノード５および１１の全域でノード１３にトラフィックを分割することが可能であり、フレキシブルノード９は、２個の異なる次ホップノード７および１０の全域でノード１３にトラフィックを分割することが可能であり、フレキシブルノード１４は、２個の異なる次ホップノード１０および１３の全域でノード１３にトラフィックを分割することが可能である。
【００３２】
本発明を説明する際に明確にする目的で、フレキシブルノードのセットＣを考慮すると、発信元ノードｓから宛先ノードｄまでの経路ｓ＝ｕ０、ｕ１、ｕ２、．．．ｕｋ＝ｄが、ｊ＝１、２、．．．、ｋ（ｕｊ−１、ｕｊ）∈Ｅおよびｕｊ＝ＮＨ（ｕｊ−１、ｄ）に関して、ｕｊ−１∈Ｄである場合、実行可能な経路と呼ばれることになる第１の定義が定義される。ｕ１、ｕ２、．．．ｕｋが識別可能である実行可能な経路は、許容経路として示される。発信元ノードｓと宛先ノードｄの間の許容経路のセットはＰｓｄとして示される。すべての非フレキシブルノードに関する所与の宛先への次ホップが最短経路アルゴリズムによって与えられる場合、定義から経路は実行可能であり、実行可能経路がループレス（ｌｏｏｐｌｅｓｓ）である場合だけ実行可能経路は許容的である。したがって、発信元ノードｓと宛先ノードｄの間のすべてのトラフィックは、ｐ∈Ｐｓｄ上に経路選択されなければならない。
【００３３】
例えば、図３に示されたように、経路３−２−５−１２−１３は、発信元ノード３から宛先ノード１３までの許容経路である。しかし、この許容経路は、発信元ノード３から宛先ノード１３までの最短経路ではない。むしろ、発信元ノード３から宛先ノード１３までの最短経路は、発信元ノード３から宛先ノード１３まで３つのホップだけを要求する経路３−２−１１−１３である。経路３−６−１１−１３は、発信元ノード３から宛先ノード１３まで３つのホップだけを要求するが、非フレキシブルノードであるノード３に関する次ホップは、最短経路上の次ホップ、つまりノード２でなければならないため、経路３−６−１１−１３は許容的ではない。
【００３４】
本発明を説明する際に明確にする目的で、非フレキシブルノードでの最短経路の経路選択を考慮すると、フレキシブルノードを横断せずに発信元から宛先に移動するトラフィックは、制御不可能なトラフィックと呼ばれることになり、一方、フレキシブルノード（すなわち、フレキシブルノードはトラフィックのための発信元ノードである）上で発生するまたは宛先ノードに達する前に少なくとも１個のフレキシブルノードを横断するトラフィックは、制御可能なトラフィックと呼ばれることになる第２の定義が定義される。すなわち、制御可能なトラフィックは、少なくとも１つのフレキシブルノードを横断するパケットを含む。したがって、制御可能なトラフィックの経路を操作するために少なくとも１つの機会がフレキシブルノードに存在する。
【００３５】
例えば、ノード６からノード１３までのトラフィックは、経路６−１０−１３に沿って（オプションで、ＯＳＰＦによって）経路選択されるが、ノード６またはノード１０はフレキシブルノードでないため、ノード６からノード１３までのトラフィックは制御不可能なトラフィックである。同様に、（ノード５上で発生する）ノード５からノード１３までのトラフィックは、経路５−１２−１３に沿って経路選択されるが、ノード５またはノード１２はフレキシブルノードでないため、ノード５からノード１３までのトラフィックは制御不可能なトラフィックである。対照的に、ノード８からノード１３までのトラフィックはフレキシブルノード９を通過するため、ノード８からノード１３までのトラフィックは制御可能なトラフィックである。同様に、ノード１５からノード１３までのトラフィックは、フレキシブルノード１４を通過するため、ノード１５からノード１３までのトラフィックは制御可能なトラフィックである。
【００３６】
本発明を説明する際に明確にする目的で、（１）フレキシブルノードｕがそのパケットに関する経路選択経路（ｒｏｕｔｉｎｇ  ｐａｔｈ）（例えば、ＯＳＰＦ経路選択経路）上にあり、（２）パケットが任意のその他のフレキシブルノードを横断する前に、フレキシブルノードｕを横断する場合、パケットがフレキシブルノードｕ∈Ｃによって注入されると見なされる第３の定義が定義される。フレキシブルノードｕ∈Ｃによっていくつかの宛先ノードｄ∈Ｎに注入されるトラフィックはＩｕｄとして示される。すなわち、すべての制御可能なトラフィックに関して、制御可能なトラフィックを注入する独自のフレキシブルノードが存在する。ネットワークにトラフィックを注入するフレキシブルノードは、その注入されたトラフィックに関する発信元ノードであってよく、またはそうでなくてもよい。第３の定義の明細は、図４を参照して本明細書でさらに説明される。
【００３７】
図４は、図１の通信ネットワークのフレキシブルノードで独立して経路選択可能なトラフィックのハイレベルのブロック図を示す。一般に、図４は、図３の最短経路ツリー３００の部分のハイレベルのブロック図を示す。特に、図４は、宛先ノード１３に向けたフレキシブルノードの各々からのリンク３１０を除いて（すなわち、フレキシブルノード２からノード１１までの、フレキシブルノード９からノード１０までの、およびフレキシブルノード１４からノード１３までのリンクを除いて）、図３のリンク３１０の各々を示す。図４に示されたように、各ノードの隣の数は、宛先ノード１３に対してそのノードから発生したトラフィックレート（またはその代わりに、トラフィック量）を表す。図４に示されるように、各リンクの隣の数は、そのリンク上のトラフィックレート（すなわち、ノード１３に向かう最短経路ツリー内の各下流ノードに関連するトラフィックレートの組合せ）を表す。
【００３８】
本明細書で説明されるように、Ｔｓｄが発信元ノードｓ∈Ｎから宛先ノードｄ∈Ｎまでのトラフィックレートを表す表記法が定義される。図４に示されたように、ノード１は３のトラフィックレート（すなわち、（Ｔ１、１３）＝３）を有し、ノード３は４のトラフィックレート（すなわち、（Ｔ３、１３）＝４）を有し、ノード４は６のトラフィックレート（すなわち、（Ｔ４、１３）＝６）を有し、ノード５は１のトラフィックレート（すなわち、（Ｔ５、１３）＝１）を有し、ノード６は１のトラフィックレート（すなわち、（Ｔ６、１３）＝１）を有し、ノード７は６のトラフィックレート（すなわち、（Ｔ７、１３）＝６）を有し、ノード８は４のトラフィックレート（すなわち、（Ｔ８、１３）＝４）を有し、ノード１０は４のトラフィックレート（すなわち、（Ｔ１０、１３）＝４）を有し、ノード１１は２のトラフィックレート（すなわち、（Ｔ１１、１３）＝２）を有し、ノード１２は３のトラフィックレート（すなわち、（Ｔ１２、１３）＝３）を有し、ノード１４は２のトラフィックレート（すなわち、（Ｔ１４、１３）＝２）を有し、ノード１５は３のトラフィックレート（すなわち、（Ｔ１５、１３）＝３）を有する。
【００３９】
本明細書で説明されるように、（１）フレキシブルノードｕがそのパケットに関する経路選択経路上にあり、（２）パケットが任意のその他のフレキシブルノードを横断する前に、フレキシブルノードｕを横断する場合、パケットがフレキシブルノードｕ∈Ｃによって注入されると見なされる第３の定義が定義される。フレキシブルノードｕ∈Ｃによって宛先ノードｄ∈Ｎに注入されたトラフィックはＩｕｄとして示される。図４に示されたように、ノード１および３からノード１３までのトラフィックは、フレキシブルノード２によって注入される（すなわち、ノード１は３のトラフィックレートを提供し、ノード３は４のトラフィックレートを提供し、ノード２は２のトラフィックレートを提供するため、Ｉ２、１３＝９である）。図４に示されたように、ノード４および８からノード１３までのトラフィックは、フレキシブルノード９によって注入される（すなわち、ノード４は６のトラフィックレートを提供し、ノード８は４のトラフィックレートを提供し、ノード９は３のトラフィックレートを提供するため、Ｉ９、１３＝１３である）。図４に示されたように、ノード１５からノード１３までのトラフィックは、フレキシブルノード１４によって注入される（すなわち、ノード１５は３のトラフィックレートを提供し、ノード１４は２のトラフィックレートを提供するため、Ｉ１４、１３＝５である）。
【００４０】
すなわち、本明細書で説明されるように、すべての発信元／宛先ノードの対（ｓ、ｄ）に関してＴｓｄの値が知られている場合、Ｉｕｄの値は計算され得る。具体的には、すべての発信元／宛先ノードの対（ｓ、ｄ）に関してＴｓｄの値が知られている場合、Ｉｕｄの値は、フレキシブルノードの出口リンクを除外して、フレキシブルノードまたは宛先ノードに達するまで、経路選択プロトコル（例えば、ＯＳＰＦ）にすべての要求を経路選択させることによって計算され得る。フレキシブルノードで累積するトラフィックは、フレキシブルノードによって注入されるトラフィックである。図４に示されるように、Ｉ２、１３＝９、Ｉ９、１３＝１３、およびＩ１４、１３＝５である。しかし、Ｔｓｄ値は、コントローラ（例示的に、コントローラ１２０）に知られておらず、むしろ、一実施形態では、コントローラで利用可能な唯一の測定値はＷｕｄ値（すなわち、ノードｕ∈Ｃを通過する宛先ｄ向けのトラフィック）である。
【００４１】
本明細書で説明されるように、操作され得る唯一のトラフィックは、フレキシブルノードを横断するトラフィックであるため、一実施形態では、制御可能なトラフィックと制御不可能なトラフィックとは区別される。本明細書で説明されるように、Ｉｕｄはフレキシブルノードｕ∈Ｃによって宛先ノードｄ∈Ｎに注入されたトラフィックを示し、フレキシブルノードｕによって注入されたトラフィックは、許容経路ｐ∈Ｐｓｄのうちの１つに沿ってだけ宛先ノードｄに達することが可能である。ｇ（ｅ）がリンクｅ∈Ｅ上の制御不可能なトラフィックフローを示す表記法が定義される。本明細書で説明されるように、発信元／宛先トラフィックレート値Ｔｓｄが事前に知られている場合、ｇ（ｅ）は計算され得るが、発信元／宛先トラフィックレート値Ｔｓｄは事前に知られていない。
【００４２】
本明細書で説明されるように、一実施形態では、コントローラの目的は、リンクでのパケット遅延およびパケット損失が最小限に抑えられるように、制御可能なトラフィックを経路選択することである。一実施形態では、リンクでのパケット遅延およびパケット損失はリンク利用の増大する機能であるため、リンク利用はリンクでのパケット遅延およびパケット損失のための代理として使用されることが可能である。１つのかかる実施形態では、コントローラの目的は、ネットワーク内のリンクの最大利用を最小限に抑えることである。１つのかかる公式では、任意の所望されるレベルの精度に至るまで解かれ得る変数は、経路Ｐに関連する経路フローであり得る。１つのかかる公式では、経路Ｐに関連する経路フローは、ｘ（Ｐ）として示されることが可能である。１つのかかる実施形態では、コントローラは、（Θとして示される）コントローラが最大リンク利用を最小限に抑えることを試みる、以下の最適化問題を解く：
【数１】
2009532941.tif 000003
【００４３】
不等式の第１のセット（方程式１）は、リンク上の（（ｇ（ｅ）として示される）リンク上の制御不可能なフローと（Σｘ（Ｐ）として示される）リンク上の制御可能なフローの和である）総フローが、（Θとして示される）最大リンク利用と（ｃ（ｅ）として示される）リンク容量の積以下であることを確実にする。不等式の第２のセット（方程式２）は、フレキシブルノードに関連する、注入された総トラフィックがネットワーク内に経路選択されることを確実にする（すなわち、各フレキシブルノードｕ∈Ｃと（Σｘ（Ｐ）として示される）宛先ノードｄの間の許容経路Ｐｕｄのセット内の各許容経路Ｐに関するリンク上の制御可能なフローの和が、フレキシブルノードｕ∈Ｃによって（Ｉｕｄとして示される）宛先ノードｄ∈Ｎに注入されたトラフィック以上であることを確実にする）。
【００４４】
この最小／最大利用公式では、最大リンク利用Θの最適値は任意のリンクの最大利用であり、コントローラは最大リンク利用Θを最小限に抑えるための方法で公式を解くことを試みる。この公式では、最大リンク利用の最適値が１未満（Θ＜１）である場合、どのリンクも過剰利用されない。一実施形態では、最小／最大利用公式はコントローラによって解かれる。一実施形態では、この最適化問題を解いた後、コントローラは、各フレキシブルノードに関して、そのフレキシブルノードに関連する各次ホップノードと、各宛先ノードに関して、各次ホップノードに関連する各関連トラフィックフラクションとを決定する。
【００４５】
一実施形態では、コントローラは、各フレキシブルノード上の注入されたトラフィック値Ｉｕｄと、各リンク上の制御不可能なフローｇ（ｅ）とを使用してそれぞれのフレキシブルノードに関する経路選択表を決定する。一実施形態では、コントローラは、各フレキシブルノード上で注入されたトラフィック値Ｉｕｄと各リンク上の制御不可能なフローｇ（ｅ）とを決定する。一実施形態では、各フレキシブルノード上の注入されたトラフィック値Ｉｕｄおよび各リンク上の制御不可能なフローｇ（ｅ）は、ネットワーク情報（例えば、ネットワークトポロジー情報、リンク状態情報など）とトラフィック測定情報（例えば、フレキシブルノードによって行われ、フレキシブルノードからコントローラに送信された測定値）とを使用して決定されることが可能である。
【００４６】
図５は、本発明の一実施形態による方法を示す。具体的には、図５の方法５００は、それぞれのフレキシブルノードに関連する経路選択表を決定するための方法を含む。それぞれのフレキシブルノードに関する経路選択表を決定するように構成されたコントローラ上で実行される動作に関して説明されるが、一実施形態では、方法５００のステップのうちの少なくとも一部は、それぞれのフレキシブルノードによって実行されることが可能である。連続して実行されているとして示され、説明されるが、当業者は、方法５００のステップのうちの少なくとも一部は、同時に、または図５に提示されたのと異なる順序で実行され得る点を理解されよう。方法５００はステップ５０２で始まり、ステップ５０４に進む。
【００４７】
ステップ５０４で、トポロジー情報が取得される。一実施形態では、トポロジー情報は、コントローラに関連する少なくとも１つのデータベースから取得される。一実施形態では、トポロジー情報は、非フレキシブルノードおよびフレキシブルノードから受信される。ステップ５０６で、リンク状態メッセージが非フレキシブルノードおよびフレキシブルノードから受信される。一実施形態では、リンク状態メッセージは、ＯＳＰＦ−ＬＳＡメッセージを含む。ステップ５０８で、ネットワーク内の各リンクに関して（すなわち、各リンクｅ∈Ｅに関して）現在のリンク重みが決定される。ステップ５１０で、リンクトラフィックエンジニアリングメッセージが非フレキシブルノードおよびフレキシブルノードから受信される。一実施形態では、リンクトラフィックエンジニアリングメッセージは、ＯＳＰＦ−ＴＥメッセージを含む。ステップ５１２で、ネットワーク内の各リンクに関して（すなわち、各リンクｅ∈Ｅに関して）現在のリンク容量（例えば、利用可能な帯域幅）が決定される。
【００４８】
ステップ５１４で、各非フレキシブルノードによって実行された現在の経路選択は、トポロジー情報と、現在のリンク重みと、現在のリンク容量とを使用して決定される。示されないが、一実施形態では、各非フレキシブルノードによって実行された現在の経路選択は、それぞれの非フレキシブルノードによって利用される経路選択表を取得することによって決定されることが可能である。ステップ５１６で、各フレキシブルノードの現在の経路選択が決定される。一実施形態では、各フレキシブルノードの現在の経路選択は、各それぞれのフレキシブルノードに関連する、予め決定された経路選択表を使用して決定される（例えば、フレキシブルノードに関連して決定された経路選択表はコントローラによって記憶されることが可能である）。
【００４９】
ステップ５１８で、ネットワーク内の各リンクに関して総トラフィックフローｆ（ｅ）が決定される。一実施形態では、ネットワーク内の各リンクに関する総トラフィックフローｆ（ｅ）は、各非フレキシブルノードおよび各フレキシブルノードの現在の経路選択を使用して決定される。一実施形態では、現在のリンク重み（例えば、ＯＳＰＦ−ＬＳＡリンク重み）および現在のリンク容量（例えば、ＯＳＰＦ−ＴＥリンク容量）を考慮すると、コントローラは、すべての非フレキシブルノードに関して現在の経路選択を決定することが可能である。一実施形態では、コントローラはそれぞれのフレキシブルノードに関して経路選択表を計算したため、コントローラはすべてのフレキシブルノード（すなわち、各フレキシブルノード、複数の次ホップノードの各々、およびオプションで、各宛先ノードに関して、関連するトラフィックフラクション）に関する現在の経路選択を知っている。
【００５０】
ステップ５２０で、注入されたトラフィック値Ｉｕｄは、ネットワーク内の各宛先ノードｄ向けの（すなわち、各宛先ノードｄ∈Ｎ向けの）ネットワーク内の各フレキシブルノードｕに関して（すなわち、各フレキシブルノードｕ∈Ｃに関して）、決定される。一実施形態では、注入されたトラフィック値Ｉｕｄは、各フレキシブルノードによって決定され、処理されたトラフィック測定情報の一部としてコントローラに送信されることが可能である。一実施形態では、注入されたトラフィック値Ｉｕｄは、各フレキシブルノードからコントローラに送信された未加工のトラフィック測定情報を使用してコントローラによって決定されることが可能である。注入されたトラフィック値Ｉｕｄを決定するための例示的な方法は、本明細書で図６に関して示され、説明される。
【００５１】
ステップ５２２で、制御不可能なトラフィックフローｇ（ｅ）がネットワーク内の各リンクに関して決定される。一実施形態では、制御不可能なトラフィックフローｇ（ｅ）は、各フレキシブルノードによって決定され、処理されたトラフィック測定情報の一部としてコントローラに送信されることが可能である。一実施形態では、制御不可能なトラフィックフローｇ（ｅ）は、各フレキシブルノードからコントローラに送信された未加工のトラフィック測定情報を使用してコントローラによって決定されることが可能である。制御不可能なトラフィックフローｇ（ｅ）を決定するための例示的な方法は、本明細書で図７に関して示され、説明される。
【００５２】
ステップ５２４で、経路選択表はネットワーク内の各フレキシブルノードに関して決定される。一実施形態では、各経路選択表は、各非フレキシブルノードおよび各フレキシブルノードの現在の経路選択を使用して決定される。一実施形態では、各経路選択表は総トラフィックフローｆ（ｅ）と、注入されたトラフィック情報（Ｉｕｄ）と、制御不可能なトラフィック情報（ｇ（ｅ））とを使用して決定される。一実施形態では、各経路選択表は、調整された方法で、グループとしてそれぞれのフレキシブルノードの各々に関して決定される。この実施形態では、１つのフレキシブルノードに関する経路選択表の決定は、複数のその他のフレキシブルノード（例えば、ネットワーク内のすべてのその他のフレキシブルノード、同じフレキシブルノードグループに関連するその他のフレキシブルノード、複数のフレキシブルノードグループの全域のその他のフレキシブルノードなど、ならびにそれらの様々な組合せ）の各々に関する経路選択表の決定に、少なくとも一部基づく。ステップ５２６で、方法５００は終了する。
【００５３】
図６は、本発明の一実施形態による方法を示す。具体的には、図６の方法６００は、それぞれのフレキシブルノードに関して経路選択表を決定する際に使用されるように構成された、注入されたトラフィック値を決定するための方法を含む。フレキシブルノードに関して実行される動作に関して説明されるが、一実施形態では、方法６００のステップの少なくとも一部は、それぞれのフレキシブルノードに関する経路選択表を決定するように構成されたコントローラによって実行されることが可能である。連続して実行されているとして示され、説明されるが、当業者は、方法６００のステップの少なくとも一部は、同時に、または図６に提示されたのと異なる順序で実行され得る点を理解されよう。方法６００はステップ６０２で始まり、ステップ６０４に進む。
【００５４】
ステップ６０４で、フレキシブルノードｕ∈Ｃが選択される。ステップ６０６で、宛先ノードｄ∈Ｎが選択される。ステップ６０８で、フレキシブルノードｕは、宛先ノードｄに向けてノードｕを横断する（横断トラフィック値として示される）トラフィック量Ｗｕｄを測定する。横断したトラフィック値Ｗｕｄは、フレキシブルノードｕを横断する宛先ノードｄ宛のトラフィック量を示す。ステップ６１０で、どのトラフィックもフレキシブルノード順序内の後のフレキシブルノードからフレキシブルノード順序内の先のフレキシブルノードに流れないように、宛先ノードｄに向けてフレキシブルノードの順序が決定される。一実施形態では、フレキシブルノード順序は、トラフィックに関する経路選択ループが宛先ノードｄに流れるのを回避するために使用される。
【００５５】
ステップ６１２で、トラフィックフローユニットは、フレキシブルノードｕから宛先ノードｄに経路選択される。トラフィックフローのユニットは、任意のトラフィック量（例えば、パケット）を含み得る。ステップ６１４で、ユニットフローフラクションβｗ（ｕ、ｄ）は、フレキシブルノードｕから宛先ノードｄへのフレキシブルノード順序内の各フレキシブルノードｗに関して決定される。ステップ６１６で、注入されたトラフィック値Ｉｕｄは、フレキシブルノードｕと宛先ノードｄとに関して決定される。一実施形態では、注入されたトラフィック値Ｉｕｄは、（１）横断したトラフィック値Ｗｕｄと（２）フレキシブルノード順序内でフレキシブルノードｕよりも先に現れるすべてのフレキシブルノードｗ上のβｗ（ｕ、ｄ）Ｉｕｄの総和の間の差として計算される。
【００５６】
一実施形態では、
【数２】
2009532941.tif 000004
が、フレキシブルノード順序内でフレキシブルノードｕ∈Ｃがフレキシブルノードｖ∈Ｃよりも先に現れるという事実を示す表記法が定義され得る。フレキシブルノード順序内の第１のフレキシブルノードｕ∈Ｃの場合、宛先ノードｄ向けの注入されたトラフィック量は、フレキシブルノードｕ∈Ｃ上で発生するまたはフレキシブルノードｕ∈Ｃを横断する宛先ノードｄ∈Ｎに関する総トラフィック量に等しい（すなわち、Ｉｕｄ＝Ｗｕｄ）。フレキシブルノード順序内の第２のフレキシブルノードｖ∈Ｃの場合、フレキシブルノードｕから宛先ノードｄまでの１つのトラフィックユニットを経路選択して、フレキシブルノードｕ∈Ｃから、フレキシブルノードｖ∈Ｃを横断する宛先ノードｄまでのこのトラフィックユニットの（βｖ（ｕ、ｄ）として示される）トラフィックユニットフラクションを決定する。
【００５７】
この第２のフレキシブルノードｖの場合、宛先ノードｄ向けの注入されたトラフィック量は、フレキシブルノードｖ∈Ｃ上で発生するまたはフレキシブルノードｖ∈Ｃを横断する宛先ノードｄ∈Ｎに関する総トラフィック量と、（１）フレキシブルノードｕ∈Ｃから、フレキシブルノードｖ∈Ｃを横断する宛先ノードｄまでのトラフィックユニットのトラフィックユニットフラクション、および（２）フレキシブルノードｕ∈Ｃによって注入された、宛先ノードｄ向けの注入されたトラフィック量の積の間の差に等しい（すなわち、Ｉｖｄ＝Ｗｕｄ−βｖ（ｕ、ｄ）Ｉｕｄ）。このプロセスは、一般に、フレキシブルノード順序内のフレキシブルノードｗ∈Ｃに関して、フレキシブルノードｗ∈Ｃによって注入された宛先ノードｄに関して注入されたトラフィック量Ｉｗｄが
【数３】
2009532941.tif 000005
によって与えられるように反復され得る。
【００５８】
ステップ６１８で、（Ｉｕｄ値を計算するために）最終宛先ノードが考慮されたかどうかについて決定される。最終宛先ノードが考慮されていない場合、方法６００はステップ６２０に進む。ステップ６２０で、もう１つの宛先ノードｄ（すなわち、現在選択されたフレキシブルノードｕに関して予め処理されていない宛先ノード）が選択される。最終宛先ノードが考慮された場合、方法６００はステップ６２２に進む。ステップ６２２で、（Ｉｕｄ値を計算するために）最終フレキシブルノードが考慮されたかどうかが決定される。最終フレキシブルノードが考慮されていない場合、方法６００はステップ６２４に進む。ステップ６２４で、もう１つのフレキシブルノードｕ（すなわち、予め処理されていないフレキシブルノード）が選択される。ステップ６２０および６２４から、方法６００はステップ６０８に戻る。最終フレキシブルノードが考慮された場合、方法６００はステップ６２６に進み、ここで方法６００は終了する。
【００５９】
図７は、本発明の一実施形態による方法を示す。具体的には、図７の方法７００は、それぞれのフレキシブルノードに関する経路選択表を決定する際に使用するように構成された制御不可能なトラフィック値を決定するための方法を含む。フレキシブルノードに関して実行される動作に関して説明されるが、一実施形態では、方法７００のステップの少なくとも一部は、それぞれのフレキシブルノードに関する経路選択表を決定するように構成されたコントローラによって実行されることが可能である。連続して実行されているとして示され、説明されるが、当業者は、方法７００のステップのうちの少なくとも一部は、同時に、または図７で提示されたのと異なる順序で実行され得る点を理解されよう。方法７００は、ステップ７０２で始まり、ステップ７０４に進む。
【００６０】
ステップ７０４で、注入されたトラフィック値Ｉｕｄは、各宛先ノードｄ∈Ｎ向けの各フレキシブルノードｕ∈Ｃに関して決定される。一実施形態では、注入されたトラフィック値Ｉｕｄは、本明細書で図６に関して示され、説明された方法６００を使用して決定されることが可能である。ステップ７０６で、総トラフィックフローｆ（ｅ）は、ネットワーク内の各リンクに関して（すなわち、各ｅ∈Ｅに関して）決定される。一実施形態では、ネットワーク内の各リンクに関する総トラフィックフローｆ（ｅ）は、本明細書で図５の方法５００に関して示され、説明されるように、ネットワーク内の各非フレキシブルノードの現在の経路選択と各フレキシブルノードの現在の経路選択とを使用して決定されることが可能である。
【００６１】
ステップ７０８で、トラフィックフローユニットは、各宛先ノードｄ∈Ｎ向けの各フレキシブルノードｕ∈Ｃで注入される。ステップ７１０で、リンクｅ上で経路選択された、注入されたトラフィックフローユニットのユニットフローフラクションαｅ（ｕ、ｄ）は、各宛先ノードｄ∈Ｎ向けの各フレキシブルノードｕ∈Ｃに関して決定される。ユニットフローフラクションは、リンクｅ上で経路選択されるトラフィックフローユニトのフラクションを表す。ステップ７１２で、制御不可能なトラフィックフローｇ（ｅ）は、ネットワーク内の各リンクｅに関して決定される。一実施形態では、制御不可能なトラフィックフロー値ｇ（ｅ）は、注入されたトラフィック値Ｉｕｄと、総トラフィックフローｆ（ｅ）と、ユニットフローフラクションαｅ（ｕ、ｄ）とを使用して決定されることが可能である。１つのかかる実施形態では、制御不可能なトラフィックフロー値ｇ（ｅ）は、（方程式５に示されるように）（１）総トラフィックフローｆ（ｅ）と、（２）すべてのフレキシブルノードｕおよびすべての宛先ノード上の［αｅ（ｕ、ｅ）・Ｉｕｄ］の総和の差として計算され得る。ステップ７１４で、方法７００は終了する。
【数４】
2009532941.tif 000006
【００６２】
本明細書では、コントローラがネットワーク内の各通信リンクの最大リンク利用Θを最小限に抑えるためにトラフィックを経路選択する、フレキシブルノード経路選択表を決定するために使用されるトラフィック制御問題の特定の公式（すなわち、上で説明された最小／最大利用公式）に関して主に示され、説明されるが、一実施形態では、フレキシブルノード経路選択表を決定するために、様々なその他のトラフィック制御問題公式が構築され得る。１つのかかる実施形態では、実質的に類似のトラフィック制御問題の公式は、注入されたトラフィックを固定されたリンク容量に適合させる方法で、注入されたトラフィックをスケーリングすると同時に、通信リンクに関連するリンク容量を実質的に固定した状態で維持することを伴う。
【００６３】
このスケーリング公式の一実施形態では、コントローラの目的は、（λとして示される）ネットワークスループットを最大化することである。このスケーリング公式の一実施形態では、（例えば、プライマル／デュアルアルゴリズム（ｐｒｉｍａｌ−ｄｕａｌ  ａｌｇｏｒｉｔｈｍ）を使用して）任意の所望されるレベルの精度に至るまで解かれ得る変数は、（ｘ（Ｐ）として示される）経路Ｐに関連する経路フローを含む。このスケーリング公式では、ネットワークスループットλの最適値が１より大きい（λ＞１）場合、すべてのリンク利用が１未満であると同時に、現在のトラフィックはフレキシブルノードで経路選択されることが可能である。すなわち、このスケーリング公式に対する最適解は、最小／最大利用公式に対する最適解の逆である。一実施形態では、コントローラは、ネットワークスループットλを最大化することを試みるために以下の最適化問題を解く。
【数５】
2009532941.tif 000007
【００６４】
一実施形態では、このスケーリング公式はコントローラによって解かれる。一実施形態では、コントローラは、各フレキシブルノード上の注入されたトラフィック値Ｉｕｄと、各リンク上の制御不可能なフローｇ（ｅ）とを計算する。一実施形態では、各リンク上の制御不可能なフローｇ（ｅ）および各フレキシブルノード上の注入されたトラフィック値Ｉｕｄは、ネットワーク情報（例えば、ネットワークトポロジー情報、リンク重み情報、リンク容量情報、および非フレキシブルノードおよびフレキシブルノードの各々からコントローラによって受信された類似情報）と、フレキシブルノード情報（例えば、フレキシブルノードによって測定され、フレキシブルノードからコントローラに送信されたトラフィック測定情報）とを使用して計算され得る。
【００６５】
本明細書で説明されたこれまでの実施形態では、ネットワーク内のフレキシブルノードのそれぞれの数および位置は固定されたが、一実施形態では、ネットワーク内のフレキシブルノードのそれぞれの数および位置は選択されることが可能である。１つのかかる実施形態では、非フレキシブルノードのネットワークを考慮すると、非フレキシブルノードの一部はフレキシブルノードによる置換え（すなわち、置き換えるための非フレキシブルノードの数を決定すること、およびどの非フレキシブルノードを置き換えるかを決定すること）のために選択され得る。ネットワーク内のフレキシブルノードの数および位置の決定に続いて、コントローラは、ネットワーク内のトラフィックパターンに基づいてフレキシブルノードでトラフィックの経路選択を決定する（すなわち、フレキシブルノードに関連するフレキシブルノード経路選択表を決定する）ために動的な経路選択問題を解くことが可能である。
【００６６】
本明細書で説明されるように、フレキシブルノードを利用するネットワークは、フレキシブルノードに欠けるネットワークより性能が優れている。実際には、ネットワーク内の非フレキシブルノードの一部をフレキシブルノードと置き換えることによって達成されるネットワーク性能改善は、ネットワーク内のフレキシブルノードの数および位置に依存する。一般に、フレキシブルノードの位置の最適選択は、（事前に正確に知られていない）ネットワークトラフィック行列に依存する。一実施形態では、フレキシブルノードの位置は、ネットワークトラフィック行列から独立して選択されることが可能である。もう１つの実施形態では、フレキシブルノードの位置は、ネットワークトラフィック行列の推定に基づいて選択されることが可能である。
【００６７】
本明細書で説明されるように、一実施形態では、フレキシブルノードの位置は、ネットワークトラフィック行列の推定に基づいて選択されることが可能である。１つのかかる実施形態では、フレキシブルノードの位置の選択を簡素化するために様々な仮定が行われ得る。一実施形態では、フレキシブルノードの（ｈとして示される）数は知られていると仮定され得る。一実施形態では、（Ｔとして示され、Ｔｓｄは、発信元ノードｓ∈Ｎと宛先ノードｄ∈Ｎの間のトラフィックに関する仮のトラフィック行列を表す）仮のトラフィック行列は知られていると仮定され得る。一般に、ネットワーク内の実際のトラフィックは、仮のトラフィック行列Ｔから得られる。一実施形態では、仮のトラフィック行列Ｔは、ネットワーク内のｈ個のフレキシブルノードの配置を決定するために（すなわち、フレキシブルノードの位置を決定するために）使用されることが可能である。
【００６８】
一公式では、フレキシブルノードセットＣ上のトラフィック行列Ｔのスループットは、λＴが許容経路に沿ってネットワーク内で経路選択され得るように最大スカラλとして定義される。この公式では、スループットは、λ（Ｔ、Ｃ）として示され得る。Ｃ＝０がネットワーク内のどのノードもフレキシブルノードでない場合に対応し、Ｃ＝Ｎがネットワーク内の各ノードがフレキシブルノードである場合に対応する、１つのかかる公式では、λ（Ｔ、０）≦λ（Ｔ、Ｃ）≦λ（Ｔ、Ｎ）である。一実施形態では、λ（Ｔ、Ｎ）はネットワークに関する最大同時フロー問題を解くことによって計算され得る。一実施形態では、トラフィック行列Ｔおよびフレキシブルノードの数ｈを考慮すると、目的は（Ｃ：｜Ｃ｜＝ｈ）最大スループットλ（Ｔ、Ｃ）を決定することである。
【００６９】
一実施形態では、このスループット最大化公式を解くために増分グリーディ手法（ｉｎｃｒｅｍｅｎｔａｌ  ｇｒｅｅｄｙ  ａｐｐｒｏａｃｈ）が使用され得る。１つのかかる実施形態では、アルゴリズムはフレキシブルノードのセット（当初、空のセット）を定義し、アルゴリズムの各ステップで、フレキシブルノードのセットがｈ個のフレキシブルノードを含むまで、最大スループット増分を提供するフレキシブルノードがフレキシブルノードのセットに加えられる。一実施形態では、このスループット最大化公式は、任意の事前に特定された値εに関して、最適解の（１＋ε）範囲内の解を決定するために、組合せ完全多項式時間近似スキーム（Ｆｕｌｌｙ  Ｐｏｌｙｎｏｍｉａｌ  Ｔｉｍｅ  ａｐｐｒｏｘｉｍａｔｉｏｎ  Ｓｃｈｅｍｅ）（ＦＰＴＡＳ）を使用して解かれることが可能である。
【００７０】
目的が、λＴがネットワーク内で経路選択され得るようにλの最大値を決定することである一実施形態では、スループット最大化公式は、（方程式５の場合）すべてのｅ∈Ｅに関してｇ（ｅ）＝０であり、（方程式６の場合）ＩｓｄがＴｓｄによって置き換えられる（上で説明された）スケーリング公式に類似する。１つのかかる実施形態では、リンク重みＩ（ｅ）はリンクｅ∈Ｅと関連づけられることが可能であり、目的は、すべての発信元／宛先ノードの対の間の重みづけされた最短許容経路の和が１を超えるという制約に従ってΣｅｃ（ｅ）｜（ｅ）を最小限に抑えることである。
【００７１】
図８は、本明細書で説明される機能を実行する際に使用するのに適した汎用コンピュータのハイレベルのブロック図を示す。図８に示されたように、システム８００はプロセッサ要素８０２（例えば、ＣＰＵ）と、メモリ８０４（例えば、ランダムアクセスメモリ（ＲＡＭ）および／または読出し専用メモリ（ＲＯＭ））と、経路選択表制御モジュール８０５と、様々な入力／出力装置８０６（例えば、テープドライブ、フロッピー（登録商標）
ドライブ、ハードディスクドライブまたはコンパクトディスクドライブ、受信機、送信機、スピーカ、ディスプレイ、出力ポートと、（キーボード、キーパッド、マウスなどの）ユーザ入力装置を含むが、これらに限定されない記憶装置）とを含む。
【００７２】
本発明は、例えば、特定用途向け集積回路（ＡＳＩＣ）、汎用コンピュータまたは任意のその他のハードウェア均等物を使用して、ソフトウェアおよび／またはソフトウェアとハードウェアの組合せで実施されることが可能である点に留意されたい。一実施形態では、本経路選択表制御モジュールまたはプロセス８０５は、メモリ８０４内にロードされて、上で議論されたような機能を実施するために、プロセッサ８０２によって実行されることが可能である。したがって、本発明の（関連するデータ構造を含む）経路選択表制御モジュール８０５は、コンピュータ可読媒体またはキャリア（例えば、ＲＡＭメモリ、磁気または光ドライブもしくはディスケットなど）上に記憶されることが可能である。
【００７３】
本明細書では、それぞれの複数のフレキシブルノードに関して複数の経路選択表が決定され、フレキシブルノードの各々が１つのフレキシブルノードグループに属すネットワークに関して主に説明されるが、一実施形態では、経路選択表は、それぞれの複数の異なるフレキシブルノードグループに属す、それぞれの複数のフレキシブルノードに関して決定されることが可能である。一実施形態では、各フレキシブルノードグループ内のフレキシブルノードに関する経路選択表の決定は、それぞれのフレキシブルノードグループの各々の中で調整された方法で実行されることが可能であるが、各フレキシブルノードグループ内のフレキシブルノードに関する経路選択表の決定は、それぞれのフレキシブルノードグループの全域で調整された方法で実行されなくてもよい。
【００７４】
各フレキシブルノードグループ内のフレキシブルノードに関する経路選択表の決定がそれぞれのフレキシブルノードグループの各々の中で調整された方法で実行される一実施形態では、各フレキシブルノードグループ内のフレキシブルノードに関する経路選択表の決定は、フレキシブルノードグループの少なくとも一部の全域で、フレキシブルノードグループの様々な組合せなど、ならびにそれらの様々な組合せの全域で、調整された方法で実行されることも可能である。したがって、本発明は、フレキシブルノードのグループ化、フレキシブルノードグループ内の様々なフレキシブルノードに関する経路選択表の決定、フレキシブルノードグループの様々な組合せの全域での様々なフレキシブルノードに関する経路選択表の決定など、ならびにそれらの様々な組合せによって限定されることが意図されない。
【００７５】
本明細書では、（本明細書で非フレキシブルルータとも呼ばれる）標準ルータおよび（本明細書でフレキシブルルータとも呼ばれる）拡張ルータに関して主に説明されるが、本発明は、様々なその他のネットワーク要素に関して経路選択表を決定するために使用されることが可能である。したがって、フレキシブルルータは、本明細書で、タイプ１ルータ（またはその代わりに、タイプ１ノード）と呼ばれる場合もあり、非フレキシブルルータは、本明細書で、タイプ２ルータ（またはその代わりに、タイプ２ノード）と呼ばれる場合もある。したがって、本発明は、ネットワークの全域でトラフィックを経路選択することが可能な特定のタイプのネットワーク要素に限定されることが意図されない。
【００７６】
本明細書では、特定のネットワーク構成に関して主に説明されるが、本発明は、様々なその他のネットワーク構成を有するネットワーク内で使用されることが可能である。本明細書では、ＭＰＬＳ／ＩＰベースのネットワークに関して主に説明されるが、本発明は、様々なその他のプロトコル組合せを用いる通信ネットワーク内で使用されることが可能である。本明細書では、ルータに関して主に説明されるが、本発明は、様々なその他のノードタイプを含む通信ネットワーク内で使用されることが可能である。したがって、本発明は、ネットワーク構成、ネットワークプロトコル、ネットワークノードタイプ、および類似の構成可能なネットワークパラメータ、ならびにそれらの様々な組合せによって限定されることが意図されない。
【００７７】
本発明の教示を組み込む様々な実施形態が本明細書で示され、詳細に説明されるが、当業者は、これらの教示をさらに組み込む多くのその他の変更された実施形態を容易に工夫することが可能である。
【図面の簡単な説明】
【００７８】
【図１】通信ネットワークのハイレベルのブロック図である。
【図２】本発明の一実施形態による方法を示す図である。
【図３】図１の通信ネットワークの最短経路ツリーのハイレベルのブロック図である。
【図４】図１の通信ネットワークのフレキシブルノードで独立して経路選択可能なトラフィックのハイレベルのブロック図である。
【図５】本発明の一実施形態による方法を示す図である。
【図６】本発明の一実施形態による方法を示す図である。
【図７】本発明の一実施形態による方法を示す図である。
【図８】本明細書で説明される機能を実行する際に使用するのに適した汎用コンピュータのハイレベルのブロック図である。
【図１】
2009532941.tif 000008
【図２】
2009532941.tif 000009
【図３】
2009532941.tif 000010
【図４】
2009532941.tif 000011
【図５】
2009532941.tif 000012
【図６】
2009532941.tif 000013
【図７】
2009532941.tif 000014
【図８】
2009532941.tif 000015
【国際調査報告】
2009532941.tif 000016
2009532941.tif 000017
2009532941.tif 000018