JP4598640B2

JP4598640B2 - 電気通信ネットワークにおける経路選択方法及び装置

Info

Publication number: JP4598640B2
Application number: JP2005282621A
Authority: JP
Inventors: ▲れい▼ 李; 陽春李; 仁山田; ▲しゅぬ▼ 陳
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2004-09-30
Filing date: 2005-09-28
Publication date: 2010-12-15
Anticipated expiration: 2025-09-28
Also published as: US20060067217A1; CN1756233A; US7616576B2; CN1756233B; JP2006109454A

Description

本発明は、電気通信ネットワークにおける経路選択方法及び装置に関し、特に、制御戦略及びネットワーク状態に基づき経路を選択する方法及び装置に関する。

ＭＰＬＳ（Ｍｕｌｔｉ−ＰｒｏｔｏｃｏｌＬａｂｅｌＳｗｉｔｃｈｉｎｇ）技術は明示的な経路（ｅｘｐｌｉｃｉｔｒｏｕｔｅ）を提供でき、明示的な経路を介してパケットを送信する。明示的な経路をＩｎｇｒｅｓｓノードにより指定することができる。ＭＰＬＳトラヒック・エンジニアリングを実施するために、適切な経路を選択して、ネットワーク負荷のバランスを保ち（即ち、負荷分散）、ネットワークリソースの利用率とトラヒック能力を最適化することが重要である。ネットワーク負荷のバランスを保つために、長い経路を選択することが必要となる場合がある。また、このような経路は最小ホップ数経路でなくてもよい。現行経路選択方式の共通の課題は、ホップ数への制限とネットワーク負荷の分散とのトレードオフを如何にとることである。今までの研究が示すように、帯域幅保証を要求するトラヒックについて、ネットワーク負荷に応じて、経路選択は２つの場合がある。負荷が重い場合は、ホップ数への制限は優先され、負荷が軽い場合は、ネットワーク負荷分散は優先され、ホップ数への制限はマイナーな要素となる。しかし、ベストエフォート（Ｂｅｓｔ−ｅｆｆｏｒｔ）トラヒックについては、バランスのとれたネットワーク負荷により、すべての利用可能な経路を充分に利用し、ネットワークのスループットを最大化することができるので、ネットワーク負荷のバランスを維持することは常に有利である。

上記のように、ホップ数への制限とネットワーク負荷（利用可能な帯域幅）分散とのトレードオフは、ネットワーク状態及びサービス要求に基づいて定めるべきである。しかし、従来の技術において、たとえば、「ｓｈｏｒｔｅｓｔ−ｗｉｄｅｓｔ」、「ｗｉｄｅｓｔ−ｓｈｏｒｔｅｓｔ」、「ｓｈｏｒｔｅｓｔ−ｄｉｓｔａｎｃｅ」などは、スタティックなトレードオフしか提供できない。「ｓｈｏｒｔｅｓｔ−ｗｉｄｅｓｔ」アルゴリズムには、まず、すべての利用可能な経路から利用可能な最大帯域幅を有する経路を選択し、そして、複数の経路は同じ利用可能な帯域幅を有する場合は、その中から最小のホップ数の経路を選択する。「ｗｉｄｅｓｔ−ｓｈｏｒｔｅｓｔ」アルゴリズムは同様な方法と採用している。すなわち、同じホップ数の経路が複数ある場合のみ、利用可能な帯域幅が考慮される。一方、「ｓｈｏｒｔｅｓｔ−ｄｉｓｔａｎｃｅ」アルゴリズムには、ホップ数への制限とネットワーク負荷分散とのトレードオフは完全にリンクコスト関数により定められる。

これらの方法は、ネットワークの管理者がネットワーク状態及びサービス要求に基づいてトラヒック・エンジニアリングを制御することができない問題がある。さらに、ネットワークの管理者の管理ポリシーをトラヒック・エンジニアリングに取り入れることができない。

本発明は、上記の問題点に鑑みてなされ、その目的は、ＭＰＬＳトラヒック・エンジニアリングにおいて、ネットワーク状態、サービス要求、及び管理ポリシーに基づいて簡単かつ効率的に経路を選択する方法及び装置を提供することにある。

本発明の第１の観点によれば、本発明の経路選択方法は、電気通信ネットワークにおいて経路を選択する方法であって、（ａ）制御戦略を策定し、当該制御戦略に応じて制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔを生成する工程と、（ｂ）ネットワーク状態に応じてネットワーク状態パラメータを生成する工程と、（ｃ）前記制御戦略パラメータ、前記ネットワーク状態パラメータ、及びネットワーク・トポロジー情報に基づいて、経路選択の候補となる各経路の経路コストを計算する工程と、（ｄ）前記選択候補経路のうち経路コストが最小となる経路を選択する工程とを有する。

本発明の第２の観点によれば、本発明の経路選択装置は、電気通信ネットワークにおいて経路を選択する装置であって、制御戦略に応じて制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔを生成する制御戦略パラメータ生成手段と、ネットワーク状態に応じてネットワーク状態パラメータを生成するネットワーク状態パラメータ生成手段と、前記制御戦略パラメータ及び前記ネットワーク状態パラメータ、及びネットワーク・トポロジー情報に基づいて、選択の候補となる各経路の経路コストを計算する経路コスト計算手段と、前記選択候補経路のうち経路コストが最小となる経路を選択する経路決定手段とを有する。

本発明によれば、制御戦略に基づいてネットワークリソース及びサービス品質を最適化することができる。管理者は自己のトラヒック・エンジニアリング制御戦略を規定することが可能となり、また、管理者は統一的なトラヒック・エンジニアリング制御プラットフォームを介して、異なる制御戦略を配置することができる。

また、本発明において、制御戦略によりルーティング・アルゴリズム演算の複雑さが増えず、その複雑さは標準Ｄｉｊｋｓｔｒａアルゴリズムと同程度である。

また、異なる制御戦略に応じて、本発明を２つの種類のトラヒックのルーティングに適用することができる、即ち、帯域幅保証を要求するＱｏＳトラヒックとベストエフォート・トラヒックである。本発明において、これらの制御戦略の切り換えは簡単かつ効率である。

次に、添付した図面を参照しながら、本発明の実施形態を説明する。

本発明は、制御戦略に基づく経路選択方法及び装置を提供し、ＭＰＬＳラベル交換経路（ＬＳＰ：ＬａｂｅｌＳｗｉｔｃｈｅｄＰａｔｈ）の明示的な経路を計算する。本発明は、如何にネットワーク状態、サービス要求、及び管理ポリシーに基づいてトラヒック・エンジニアリングを制御するかという課題を解決し、具体的に、本発明は制御戦略を定義する方法及び当該方法を経路選択への適用を開示する。

本発明に係る経路選択装置は、ウエーブ・サーバーにおいて集中モードで実現されてもよく、また、個別ラベル・エッジ・ルーター（ＬＥＲ：ｌａｂｅｌｅｄｇｅｒｏｕｔｅｒ）において分散モードで実現されてもよい。本発明の原理に基づいて本発明の経路選択装置は容易に実現できる。

図２Ａはシステム２００Ａを示す概略図である。

システム２００Ａにおいて、本発明に係る経路選択装置は中央制御サーバーにおいて具現化される。

システム２００Ａは、中央制御サーバー２１０Ａとルーター２２０Ａ_１〜２２０Ａ_Ｎを含む。中央制御サーバー２１０Ａは戦略経路セレクター２１５Ａを含む。経路セレクター２１５Ａは本発明に係る経路選択装置として機能する。即ち、経路セレクター２１５Ａは、制御戦略に基づいてルートを計算し、これらルートをルーター２２０Ａ_１〜２２０Ａ_Ｎへ分配する。ルーター２２０Ａ_１〜２２０Ａ_Ｎは、ＭＰＬＳネットワーク全体のエッジ・ルーターであり、分散されたルートに基づいて明示的な経路をセットアップし、当該経路を経由してパケットを送る。

図２Ｂはシステム２００Ｂを示す概略図である。

システム２００Ｂにおいて、本発明に係る経路選択装置はエッジ・ルーターにおいて具現化される。

システム２００Ｂは、ルーター２２０Ｂ_１〜２２０Ｂ_Ｍを含む。ルーター２２０Ｂ_１〜２２０Ｂ_Ｍは、ネットワーク全体のエッジ・ルーターである。各ルーター２２０Ｂ_１〜２２０Ｂ_Ｍは、局所戦略経路セレクター２２５Ｂｉを含む。局所戦略経路セレクター２２５Ｂｉは本発明に係る経路選択装置として機能する。即ち、局所戦略経路セレクター２２５Ｂｉは、ネットワーク状態及び制御戦略に基づいてルートを計算する。エッジ・ルーター２２０Ｂ_１〜２２０Ｂ_Ｍは、局所戦略経路セレクター２２５Ｂｉにより計算されたルートに基づいて明示的な経路をセットアップし、当該経路を経由してパケットを送る。

次に、本発明の経路選択方法及び装置を説明する。

まず、制御戦略を策定するプロセスを説明する。

図１は、制御戦略を策定するプロセスを説明するフローチャートである。

ステップ１１０において、サービス要求に応じて、トラヒック・エンジニアリングの基本ポリシーを規定する。

トラヒック・エンジニアリングは能力が要求されるトラヒックに対するものである場合は、ネットワーク負荷のバランスを得るため、及びトラヒック能力要求を満たすため、制御戦略はＱｏＳルーティング（routing）方式を採用する。

トラヒック・エンジニアリングはベストエフォート・トラヒックに対するものである場合は、トラヒック・エンジニアリング制御戦略は動的負荷分散方式を採用し、ネットワークのスループットを最適化する。しかし、サービス品質に対する要求を保証しない。

続いて、ステップ１２０において、ステップ１１０にて規定されたトラヒック・エンジニアリングの基本ポリシーに応じて、ホップ数への制限と負荷分散とのトレードオフを定める。

トラヒック能力を要求するＱｏＳルーティング方式を採用する場合は、ホップ数への制限は優先的に考慮すべき要素である。その理由は、長い経路が余分なネットワークリソースを占用するので、利用可能なリソースが少なくなり、新たな接続を構築することができない恐れがある。

動的負荷分散方式を採用する場合は、最大リンク利用率を抑えるために、「再度の分散」（rebalancing）は重要な要素である。動的負荷分散方式においては、分散すべきトラヒックのルーティングについて、ホップ数の制限は設けられていない。

定めたトレードオフに応じて、処理は二つに分岐される。

ホップ数を制限することは必要である場合は、ステップ１３０に進み、負荷分散は優先的な要素である場合は、ステップ１４０に進む。

ステップ１３０において、ネットワーク・トポロジー及びサービス要求に応じて経路選択の制約条件を規定する。これらの制約条件として、たとえば、経路の長さ、経路の負荷などがある。

ステップ１４０において、リンク利用率の閾値を規定する。一部のリンクの利用率が閾値を超えた場合は、これらリンクを経由するＬＳＰには「混雑」が発生したという。これら混雑しているＬＳＰの負荷は他の経路へ分散される。

ステップ１５０において、後ほど説明する「制御戦略パラメータ生成手段３１０」は、ステップ１３０に得られた制約条件をパラメータ「Ｕｔｉｌ＿ｗｅｉｇｈｔ」に変換する。

ステップ１６０において、制御戦略パラメータ生成手段３１０は、ステップ１４０において得られたリンク利用率の閾値を制御パラメータＵｔｉｌ＿ｗｅｉｇｈｔに変換する。

図１に示す以上の各ステップを経て、制御戦略を制御パラメータＵｔｉｌ＿ｗｅｉｇｈｔに変換される。

図３は、本発明の一実施形態に係る経路選択装置３００の構成を示すブロック図である。

経路選択装置３００は、制御戦略に応じて制御戦略パラメータを生成する制御戦略パラメータ生成手段３１０、ネットワーク状態に応じてネットワーク状態パラメータを生成するネットワーク状態パラメータ生成手段３２０、制御戦略パラメータとネットワーク状態パラメータに応じて各経路候補のコストを計算する経路コスト計算手段３３０、及び経路候補のうち最小のコストを有する経路を選択する経路決定手段３４０を含む。

経路選択装置３００は本発明の経路選択方法を実行する。

経路選択装置３００において、制御戦略パラメータ生成手段３１０は、上記のように策定された制御戦略に応じて制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔを生成する。操作者は、任意の入力方法で、例えば、キーボードや、グラフィック・インターフェイスや、ファイルなどにより、制御戦略を制御戦略パラメータ生成手段３１０に入力する。制御戦略パラメータ生成手段３１０は、以下に述べる方法により制御戦略に応じた制御戦略パラメータを生成する。

経路コスト計算手段３３０は、以下３つの情報に基づいて各経路候補のコストを計算する。
１．ネットワーク・トポロジー・データベース３５０に記憶されたネットワーク・トポロジー情報
２. リンク状態データベースに記憶されたリンク状態情報
３．Ｕｔｉｌ＿ｗｅｉｇｈｔに含まれた制御戦略情報
経路コスト計算手段３３０は各経路候補のコストを計算した後、経路決定手段３４０は、最適な経路として最小のコストを有する経路を選択する。

経路選択装置３００は、図２Ａに示すように、中央制御サーバーにおいて具現化される場合は、ネットワーク・トポロジー・データベース３５０をネットワーク管理システムから入力し、或いは、手動で入力することができる。また、中央制御サーバーにネットワーク状態データベースを設けてもよい。ネットワーク状態データベースに、リンク利用率などのネットワーク統計データを記憶してもよい。これらデータはＳＮＭＰなどのネットワーク監視ツールにより収集される。これにより、本発明に係るネットワーク状態パラメータ生成手段３２０は構築される。

経路選択装置３００は、図２Ｂに示すように、個別のエッジ・ルーターに具現化される場合は、ネットワーク・トポロジー・データベース３５０及びネットワーク状態データベースは、トラヒック・エンジニアリング用のルーティング・プロトコール（例えば、ＯＳＰＦ−ＴＥ、或いは、ＩＳ−ＩＳ−ＴＥ）のネットワーク状態データベースとなる。これにより、本発明に係るネットワーク状態パラメータ生成手段３２０は構築される。

本発明において、Ｕｔｉｌ＿ｗｅｉｇｈｔは比例因子としてリンク及び経路のコスト計算に用いられる。この場合、異なるｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対は、異なるＵｔｉｌ＿ｗｅｉｇｈｔを用いることにより異なる制御戦略を採用する。

次に、本発明の経路選択方法をさらに説明する。

制御戦略に基づく経路選択方法の目的は、経路選択を通じてネットワーク管理者に所望の制御戦略をＭＰＬＳトラヒック・エンジニアリングに適用することにある。制御戦略は、管理者がネットワーク・トポロジー、サービス要求、及び管理ポリシーに基づいて規定される。適切な制御戦略を用いることにより、制御戦略に基づく経路選択方法は、サービス要求のあるトラヒックに対するＱｏＳルーティング方式、及び、ベストエフォート・トラヒックに対する動的負荷分散方式に対応することが可能となる。

本発明に係る制御戦略に基づく経路選択方法の基本概念は、Ｕｔｉｌ＿ｗｅｉｇｈｔをリンク利用率の比例因子として、リンクのコストの計算に用いることである。

リンクコストは以下の式を用い計算する。

ここで、Ｃ_ｌｉｎｋはリンクコストであり、Ｕ_ｌｉｎｋはリンク利用率である。

第１の実施形態
次に、本発明の第１の実施形態を説明する。

第１の実施形態において、本発明の経路選択装置はＱｏＳルーティング方式に対応する、制御戦略に基づく経路選択方法を実行する。

まず、帯域幅保証（ＱｏＳルーティング）を要求するトラヒックに本発明を適用する場合を説明する。

ＱｏＳルーティングにおいて、最小のホップ数を有する経路（以下、最小ホップ数経路という）は十分な帯域幅を有せず、トラヒックの帯域幅要求を満足できない場合は、通常長い経路を選択してトラヒックをルーティングする。今までの研究によれば、長い経路は多くのネットワークリソースを占用するので、長い経路を選択することは利用可能なリソースを新たなトラヒックへ割り当てることに影響を及ぼす。そこで、ＲＦＣ２３８６において、リソースをある接続のトラヒックに割り当てる際に、リソース全体の割り当て状況を考慮しなければならないと提案されている。リソースをある接続に割り当てるか否かを決定する原則として、同じリソースを要求するトラヒックに拒否されえることにより生じる損失を考慮するうえ、所定のＱｏＳのトラヒックをルーティングする「コスト」は、得られる利益を超えてはならない。このような「高いレベルの受付制御（admission control）」メカニズムの目的は、ＱｏＳトラヒック・ルーティングによるネットワークコストが得られる利益を超えないことを保証することにある。

本発明の一応用例として、制御戦略に基づく経路選択装置は「高いレベルの受付制御」を実行し、Ｕｔｉｌ＿ｗｅｉｇｈｔパラメータを用い、ネットワーク状態及び制御戦略に基づいて適切な経路を選択する。

本発明をＱｏＳルーティングに適用する場合は、各利用可能な経路について最大リンク利用率を求める。ある経路の最大リンク利用率はこの経路における各リンクの利用率として設定される。

ネットワークはアイドル状態である場合、あるｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対の中に、最小ホップ数経路のホップ数がｎである。この経路のコストの最大値は以下の式によりにより表される。

このｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対について、ホップ数がｎ＋ｍ（ｍ≧０）である一つの経路候補が存在する。この経路候補は負荷を有しない場合、そのコストが最も小さい値、即ち、ｍ＋ｎである。負荷分散に用いられる経路の条件としては、その経路のコストは最小ホップ数経路のコスト以下である。よって、受け入れ可能な経路候補の余分なホップ数の上限は以下の式により定められる。

最大リンク利用率がＵである経路候補が存在する場合、この経路候補が選択される条件は以下の式に示される。

経路候補の最大リンク利用率の上限は以下の式により定められる。

ｍの不等式を用いて、経路の長さに基づいて、ある経路候補を受け入れ可能であると認める条件を設定することができる。各経路候補の最大リンク利用率の上限はＵ_ｍａｘの不等式を用いて定めることができる。Ｕｔｉｌ＿ｗｅｉｇｈｔを調整することにより、これらの上限値を制御戦略に応じて制御することができる。

Ｕｔｉｌ＿ｗｅｉｇｈｔの値は以下の式に示される。

ここで、ｎは最小ホップ数経路のホップ数であり、ｍ≧０、０≦Ｕ_ｍａｘ＜１。

このようなＵｔｉｌ＿ｗｅｉｇｈｔを用いると、ホップ数がｎ＋ｍで、最大リンク利用率はＵ_ｍａｘである経路候補のコストは最小ホップ数経路のコストと同じである。この種の経路候補は「ワースト」経路候補と呼ぶ。ここで、前述した一つのｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対に対して一つの利用可能な経路を有する仮定し、この経路を経路Ａと呼ぶ。また、経路Ａのホップ数はｎ＋ｈで、最大リンク利用率はＺであるとする。このように定義されたＵｔｉｌ＿ｗｅｉｇｈｔによると、経路Ａのコストは以下の式に示される。

経路Ａは負荷分散に適している場合は、そのコストは最小ホップ数経路の最大コスト以下でなければならない。即ち、以下の式のようになる。

経路Ａは「ワースト」経路候補より長い、即ち、ｈ＞ｍである場合は、以下の式が得られる。

よって、以下の式が得られる。

これにより、経路Ａの最大リンク利用率の上限が得られる。即ち、Ｚ＜Ｕ_ｍａｘである。

言い換えれば、経路候補は「ワースト」経路より長い場合は、その経路候補を負荷分散に適用するための条件は、その経路候補の最大リンク利用率が「ワースト」経路の最大リンク利用率より小さいことである。また、Ｕ_ｍａｘとｍが与えられた場合、経路候補の長さの範囲は以下の式に示される。

長さがｎ＋ｍより長い経路について、その経路を負荷分散に適用するための条件は、その経路の最大リンク利用率はＵ_ｍａｘより小さいことである。

このように、ネットワークリソースの分配は制御される。

図４は一応用例を示す概略図である。

図４において、本発明を適用し、制御戦略に基づいて負荷分散を行う。トラヒックがノードＡからノードＢへ伝送される。ここで、この一対のノード間のすべてのトラヒックは最小ホップ数経路を経由して伝送されるとする。ネットワークの特徴量およびトラヒック分布によれば、次のような制御戦略を策定することができる。即ち、経路候補（最小ホップ数経路以外の経路）は、最大リンク利用率が８０％より低く、かつ、その余分なホップ数は１以下である場合のみ、選択経路として選択される。

現行のＱｏＳルーティング・アルゴリズムは、このような制御戦略を取り込むことができない。本発明の実施形態において、ｎ＝１、ｍ＝１、Ｕ_ｍａｘ＝０．８としてＵｔｉｌ＿ｗｅｉｇｈｔを計算することができる。このようなＵｔｉｌ＿ｗｅｉｇｈｔを用い、例えば、経路Ａ−Ｃ−Ｂの最大リンク利用率は８０％より低ければ、経路Ａ−Ｃ−Ｂは選択される。また、例えば、経路Ａ−Ｄ−Ｅ−Ｂの最大リンク利用率は６０％より低ければ、経路Ａ−Ｄ−Ｅ−Ｂは選択される。その他の場合は、トラヒックの伝送は拒否される。以上の例から分かるように、本発明の方法において、最大リンク利用率の相違により、最小ホップ数経路は制限される。以上の例には、少なくとも２０％の帯域幅は、将来ノードＡとノードＣ或いはノードＣとノードＢを接続するために保留される。同一のネットワークについて、制御戦略を変更して将来の接続に帯域幅を保留しようとする場合、新たなより小さいＵ_ｍａｘを決め、Ｕｔｉｌ＿ｗｅｉｇｈｔを再び計算し、この値をｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対に割り当てればよい。

即ち、Ｕｔｉｌ＿ｗｅｉｇｈｔを利用することにより、ホップ数と最大リンク利用率に基づいて、最小ホップ数経路以外の経路を選択する際の下限値を決めることができる。「ワースト」経路より長い経路（ｍと記す）が選択される条件としては、その経路の負荷は「ワースト」経路の負荷（Ｕ_ｍａｘと記す）より小さいことである。

Ｕｔｉｌ＿ｗｅｉｇｈｔを「ｓｈｏｒｔｅｓｔ−ｄｉｓｔａｎｃｅ」ルーティング・アルゴリズムに適用すれば、ｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対間のスループットは、最小ホップ数経路の帯域幅により制限されることはなくなり、同時に、ネットワークリソースの最小ホップ数経路以外の経路への分配は、ネットワーク状態及び制御戦略に基づいて動的に制御される。

管理者の要求に応じて、同じ制御戦略をネットワーク全体に適用してもよく（この場合、ｎはネットワークにおける最小ホップ数経路の平均ホップ数として定義される）、或いは、異なる制御戦略を個別のｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対にそれぞれ配置してもよい。さらに、単一のｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対の場合でも、マルチレベルのＱｏＳルーティングに対応するように、管理者は異なる制御戦略を優先順位の異なるトラヒックに配置してもよい。

第２の実施形態
第２の実施形態において、本発明の経路選択装置は動的負荷分散方式に対応する制御戦略に基づいた経路選択方法を実行する。

ベストエフォート・トラヒックについての動的負荷分散方式に本発明を適用する場合は、動的負荷分散方式はリンクの混雑を解消することを目的とするので、Ｕｔｉｌ＿ｗｅｉｇｈｔの定義は多少異なる。動的負荷分散方式において、リンク利用率の閾値が規定される。一部のリンクの利用率が閾値を超えた場合は、これらリンクを経由する経路には「混雑」が発生したという。これら混雑している経路における一部の負荷は他の経路候補へ分散され、リンクの利用率を閾値以下に下げる。従って、動的負荷分散方式に対応する経路選択方法において、経路候補はリンク利用率閾値を超えたリンクを経由しないことは重要である。そうでなければ、混雑の問題を解消できない。しかし、現行の「ｓｈｏｒｔｅｓｔ−ｄｉｓｔａｎｃｅ」ルーティング・アルゴリズムには、ユーザー指定の閾値は考慮されないので、経路候補が利用率閾値を超えたリンクを経由することは避けられない。

本発明において、Ｕｔｉｌ＿ｗｅｉｇｈｔを採用し、ユーザー指定の閾値を経路選択に取り込む。

リンクコストは以下の式を用いて計算する。

当該式から分かるように、利用率が（１／Ｕｔｉｌ＿ｗｅｉｇｈｔ）より高いリンクについて、そのコストはＭａｘ＿ｃｏｓｔに設定される。ここで、Ｍａｘ＿ｃｏｓｔは非常に大きな数値である。

即ち、リンクの利用率に応じて、閾値を（１／Ｕｔｉｌ＿ｗｅｉｇｈｔ）とし、そして、一部のリンクの利用率が閾値以上になると、これらのリンクを経由する経路は、コストが高すぎることにより、負荷分散アルゴリズムに採用されない。Ｕｔｉｌ＿ｗｅｉｇｈｔを１／（Ｈｉｇｈ＿ｔｈｒｅｓｈｏｌｄ）とすることにより（ここで、Ｈｉｇｈ＿ｔｈｒｅｓｈｏｌｄは管理者が定義した負荷分散閾値である）、負荷分散アルゴリズムにおいて、利用率が閾値以下のすべての経路を利用してネットワークの混雑を解消することは保証される。

図５は制御戦略に基づく経路選択方法を用いて動的負荷分散を制御する応用例を示す概略図である。

図５において、管理者が指定した閾値は７０％であり、Ｕｔｉｌ＿ｗｅｉｇｈｔ＝１／０．７＝１．４３と設定することにより、リンク利用率が７０％を超えた経路は経路候補としないことが保証される。

以上、本発明をＱｏＳトラヒックとベストエフォート・トラヒックに適用する実施例を説明した。一方、ネットワークの規模が大きい場合は、ホップ数への制限は動的負荷分散を行う際に考慮すべき要素になる可能性がある。なぜなら、このようなネットワークにおいて、経路が長くなることに伴う伝播遅延の増加は、混雑を迂回することによって減少した待ち時間より長くなり、全体の時間遅延が大きくなる可能性がある。このようなネットワークに対して動的負荷分散を行う際に、ＱｏＳルーティングと同様な分析を行い、より小さなＵｔｉｌ＿ｗｅｉｇｈｔを採用し、ホップ数を制限してもよい。この場合は、動的負荷分散を適用するための条件は、ネットワークにおける最大リンク利用率は指定された閾値に達しており、かつ、ネットワークにおいて制御戦略に基づいて規定された制約条件を満たす経路が存在することである。

さらに、異なるリンクに異なるＵｔｉｌ＿ｗｅｉｇｈｔを指定することにより、制御戦略に基づくルーティング方法を容易に異なるレベルのトラヒックに配置することができる。例えば、ベストエフォート・トラヒックは動的負荷分散スキームにより制御され、高い優先順位のトラヒックはＭＰＬＳにおける明示的な経路を経由して伝送される。トラヒックの優先順位を考えると、高い優先順位のトラヒックは最小ホップ数経路を経由して伝送することは好ましい。この場合、ベストエフォート・トラヒックについて、最小ホップ数経路の負荷は軽くなるように、最小ホップ数経路のリンクに相対的に大きなＵｔｉｌ＿ｗｅｉｇｈｔを指定し、これによって、より広い帯域幅を高い優先順位のトラヒックに留保することができる。例えば、あるリンクはベストエフォート・トラヒックに利用されないように、当該リンクに対してＵｔｉｌ＿ｗｅｉｇｈｔ＝１０００と指定することができる。

本発明は、以下の付記を含む。

（付記１）
電気通信ネットワークにおいて経路を選択する方法であって、
（ａ）制御戦略を策定し、当該制御戦略に応じて制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔを生成する工程と、
（ｂ）ネットワーク状態に応じてネットワーク状態パラメータを生成する工程と、
（ｃ）前記制御戦略パラメータ、前記ネットワーク状態パラメータ、及びネットワーク・トポロジー情報に基づいて、経路選択候補となる各経路の経路コストを計算する工程と、
（ｄ）前記選択候補経路のうち経路コストが最小となる経路を選択する工程と
を有する
経路選択方法。

（付記２）
前記ネットワーク状態パラメータは、リンク利用率Ｕ_ｌｉｎｋであり、
前記経路選択方法は、
前記制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔ及び前記リンク利用率Ｕ_ｌｉｎｋに基づいて、経路に含まれる各リンクのリンクコストＣ_ｌｉｎｋを計算する工程と、
前記経路に含まれる各リンクのリンクコストＣ_ｌｉｎｋを累積し、前記経路コストとする工程と
をさらに有する
付記１に記載の経路選択方法。

（付記３）
ＱｏＳルーティングの場合は、以下の式により前記リンクコストＣ_ｌｉｎｋを計算する

付記２に記載の経路選択方法。

（付記４）
経路における最大リンク利用率を当該経路に含まれる各リンクのリンク利用率とする工程をさらに有する
付記３に記載の経路選択方法。

（付記５）
ベストエフォート・トラヒックについて動的負荷分散を行う場合は、以下の式により前記リンクコストＣ_ｌｉｎｋを計算する

ここで、Ｍａｘ＿ｃｏｓｔは所定の常数である
付記２に記載の経路選択方法。

（付記６）
所定の経路ホップ数閾値と所定のリンク利用率閾値のいずれかに基づいて、前記制御戦略パラメータを生成する
付記１に記載の経路選択方法。

（付記７）
ＱｏＳルーティングの場合は、以下の式により前記制御戦略パラメータを生成する

ここで、ｎは選択候補経路のうち、最小ホップ数経路のホップ数であり、ｍは前記経路ホップ数閾値とｎとの差であり、Ｕ_ｍａｘは前記リンク利用率閾値である
付記６に記載の経路選択方法。

（付記８）
ベストエフォート・トラヒックについて動的負荷分散を行う場合は、以下の式により前記制御戦略パラメータを生成する

Ｕｔｉｌ＿ｗｅｉｇｈｔ＝１／Ｕ_ｍａｘ

付記６に記載の経路選択方法。

（付記９）
次のいずれかの方法により、前記制御戦略を策定する：
ネットワーク全体について同じ制御戦略を採用する、または、
異なるｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対について、異なる制御戦略を採用する、または、
単一のｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対について、異なるレベルのトラヒックに対して異なる制御戦略を採用する
付記１に記載の経路選択方法。

（付記１０）
電気通信ネットワークにおいて経路を選択する装置であって、
制御戦略に応じて制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔを生成する制御戦略パラメータ生成手段と、
ネットワーク状態に応じてネットワーク状態パラメータを生成するネットワーク状態パラメータ生成手段と、
前記制御戦略パラメータ及び前記ネットワーク状態パラメータ、及びネットワーク・トポロジー情報に基づいて、選択の候補となる各経路の経路コストを計算する経路コスト計算手段と、
前記選択候補経路のうち経路コストが最小となる経路を選択する経路決定手段と
を有する
経路選択装置。

（付記１１）
前記ネットワーク状態パラメータ生成手段は、前記ネットワークにおける各リンクのリンク利用率Ｕ_ｌｉｎｋを監視し記録し、前記ネットワーク状態パラメータとして用い、
前記経路コスト計算手段は、前記制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔ及び前記リンク利用率Ｕ_ｌｉｎｋに基づいて、経路に含まれる各リンクのリンクコストＣ_ｌｉｎｋを計算し、前記経路に含まれる各リンクのリンクコストＣ_ｌｉｎｋを累積し、前記経路コストとする
付記１０に記載の経路選択装置。

（付記１２）
ＱｏＳルーティングの場合は、前記経路コスト計算手段は、以下の式により前記リンクコストＣ_ｌｉｎｋを計算する

付記１１に記載の経路選択装置。

（付記１３）
前記経路コスト計算手段は、経路における最大リンク利用率を当該経路に含まれる各リンクのリンク利用率とする
付記１２に記載の経路選択装置。

（付記１４）
ベストエフォート・トラヒックについて動的負荷分散を行う場合は、前記経路コスト計算手段は、以下の式により前記リンクコストＣ_ｌｉｎｋを計算する

ここで、Ｍａｘ＿ｃｏｓｔは所定の常数である
付記１１に記載の経路選択装置。

（付記１５）
前記制御戦略パラメータ生成手段は、所定の経路ホップ数閾値と所定のリンク利用率閾値のいずれかに基づいて、前記制御戦略パラメータを生成する
付記１０に記載の経路選択装置。

（付記１６）
ＱｏＳルーティングの場合は、前記制御戦略パラメータ生成手段は、以下の式により前記制御戦略パラメータを生成する

ここで、ｎは選択候補経路のうち、最小ホップ数経路のホップ数であり、ｍは前記経路ホップ数閾値とｎとの差であり、Ｕ_ｍａｘは前記リンク利用率閾値である
付記１２に記載の経路選択装置。

（付記１７）
ベストエフォート・トラヒックについて動的負荷分散を行う場合は、前記制御戦略パラメータ生成手段は、以下の式により前記制御戦略パラメータを生成する

Ｕｔｉｌ＿ｗｅｉｇｈｔ＝１／Ｕ_ｍａｘ

付記１２に記載の経路選択装置。

以上、本発明の好ましい実施形態を説明したが、本発明はこれらの実施形態に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の範囲に属する。

制御戦略を策定するプロセスを説明するフローチャートである。システム２００Ａを示す概略図である。システム２００Ｂを示す概略図である。本発明の一実施形態に係る経路選択装置３００の構成を示すブロック図である。一応用例を示す概略図である。制御戦略に基づく経路選択方法を用いて動的負荷分散を制御する応用例を示す概略図である。

符号の説明

２００Ａ、２００Ｂ、４００、５００システム
２１０Ａ中央制御サーバー
２２０Ａ１〜２２０ＡＮルーター
２１５Ａ戦略経路セレクター
２２０Ｂ１〜２２０ＢＭルーター
２２５Ｂｉ局所戦略経路セレクター
経路選択装置３００
制御戦略パラメータ生成手段３１０
ネットワーク状態パラメータ生成手段３２０
経路コスト計算手段３３０
経路決定手段３４０

Claims

電気通信ネットワークにおいて経路を選択する方法であって、
（ａ）ＱｏＳルーティングとベストエフォートとのどちらに基づき前記経路を選択するかを示す制御戦略を策定し、当該制御戦略に応じて制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔを生成する工程と、
（ｂ）ネットワーク状態に応じてネットワーク状態パラメータを生成する工程と、
（ｃ）前記制御戦略パラメータ、前記ネットワーク状態パラメータ、及びネットワーク・トポロジー情報に基づいて、経路選択候補となる各経路の経路コストを計算する工程と、
（ｄ）前記選択候補経路のうち経路コストが最小となる経路をＤｉｊｋｓｔｒａアルゴリズムにより選択する工程と
を有し、
前記ネットワーク状態パラメータは、リンク利用率Ｕ _ｌｉｎｋであり、
前記経路選択方法は、
前記制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔ及び前記リンク利用率Ｕ _ｌｉｎｋに基づいて、経路に含まれる各リンクのリンクコストＣ _ｌｉｎｋを計算する工程と、
前記経路に含まれる各リンクのリンクコストＣ _ｌｉｎｋをＤｉｊｋｓｔｒａアルゴリズムにより累積し、前記経路コストとする工程と、
をさらに有する経路選択方法。
前記制御戦略がＱｏＳルーティングを示す場合は、以下の式により前記リンクコストＣ_ｌｉｎｋを計算する

請求項１に記載の経路選択方法。
経路における最大リンク利用率を当該経路に含まれる各リンクのリンク利用率とする工程をさらに有する
請求項２に記載の経路選択方法。
前記制御戦略がベストエフォートを示す場合は、以下の式により前記リンクコストＣ_ｌｉｎｋを計算する

ここで、Ｍａｘ＿ｃｏｓｔは所定の常数である
請求項１に記載の経路選択方法。
所定の経路ホップ数閾値と所定のリンク利用率閾値のいずれかに基づいて、前記制御戦略パラメータを生成する
請求項１に記載の経路選択方法。
前記制御戦略がＱｏＳルーティングを示す場合は、以下の式により前記制御戦略パラメータを生成する

ここで、ｎは選択候補経路のうち、最小ホップ数経路のホップ数であり、ｍは前記経路ホップ数閾値とｎとの差であり、Ｕ_ｍａｘは前記リンク利用率閾値である
請求項５に記載の経路選択方法。
前記制御戦略がベストエフォートを示す場合は、以下の式により前記制御戦略パラメータを生成し、

Ｕｔｉｌ＿ｗｅｉｇｈｔ＝１／Ｈｉｇｈ＿ｔｈｒｅｓｈｏｌｄ
Ｈｉｇｈ＿ｔｈｒｅｓｈｏｌｄは管理者が定義した負荷分散閾値である、
請求項５に記載の経路選択方法。
次のいずれかの方法により、前記制御戦略を策定する：
ネットワーク全体について同じ制御戦略を採用する、または、
異なるｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対について、異なる制御戦略を採用する、または、
単一のｉｎｇｒｅｓｓ−ｅｇｒｅｓｓ対について、異なるレベルのトラヒックに対して異なる制御戦略を採用する
請求項１に記載の経路選択方法。
電気通信ネットワークにおいて経路を選択する装置であって、
ＱｏＳルーティングとベストエフォートとのどちらに基づき前記経路を選択するかを示す制御戦略に応じて制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔを生成する制御戦略パラメータ生成手段と、
ネットワーク状態に応じてネットワーク状態パラメータを生成するネットワーク状態パラメータ生成手段と、
前記制御戦略パラメータ、前記ネットワーク状態パラメータ、及びネットワーク・トポロジー情報に基づいて、経路選択の候補となる各経路の経路コストを計算する経路コスト計算手段と、
前記選択候補経路のうち経路コストが最小となる経路をＤｉｊｋｓｔｒａアルゴリズムにより選択する経路決定手段と
を有し、
前記ネットワーク状態パラメータは、リンク利用率Ｕ _ｌｉｎｋであり、
前記経路コスト計算手段は、前記制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔ及び前記リンク利用率Ｕ _ｌｉｎｋに基づいて、経路に含まれる各リンクのリンクコストＣ _ｌｉｎｋを計算し、前記経路に含まれる各リンクのリンクコストＣ _ｌｉｎｋをＤｉｊｋｓｔｒａアルゴリズムにより累積し、前記経路コストとする、
経路選択装置。