(57)【特許請求の範囲】
【請求項１】
端末装置、中継装置及びこれらの装置を多段に接続する複数のリンクを具えるコネクションレス型通信ネットワークにおける経路管理方法において、これらのリンクの経路を一元的に制御する経路制御装置を具え、該経路制御装置がネットワーク内の各端末装置間の経路を管理する場合、トラフィックを受信する着端末装置をルートとし、該着端末装置へトラフィックを送信する発端末装置をリーフとするツリーを計算し、端末装置間の経路は該着端末装置をルートとするツリーのブランチとして管理し、ブランチ毎に経路計算を行い、ネットワークのトラフィック情報が変化した場合に、ブランチ毎に経路を再計算してツリーに追加することを特徴とするコネクションレス型通信ネットワークにおける経路管理方法。
【請求項２】
端末装置、中継装置及びこれらの装置を多段に接続する複数のリンクを含むコネクションレス型通信ネットワークにおけるリンクの経路を一元的に制御する経路制御装置であって、ネットワーク内の各端末装置間の経路を管理する場合、トラフィックを受信する着端末装置をルートとし、該着端末装置へトラフィックを送信する発端末装置をリーフとするツリーを計算し、端末装置間の経路は該着端末装置をルートとするツリーのブランチとして管理し、ブランチ毎に経路計算を行い、ネットワークからのトラフィック情報が変化した場合に、ブランチ毎に経路を再計算してツリーに追加することを特徴とするコネクションレス型通信ネットワークの経路制御装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコネクションレス型通信ネットワークにおいて、トラフィックをネットワーク内に均一に分散するようにネットワーク内の経路を制御し、ネットワークの収容効率の向上及び輻輳の防止を行うためのトラフィック分散型の経路管理方法及びそれを実現するための経路制御装置に関するものである。
【０００２】
【従来の技術】
コネクションレス型ネットワークにおいて端末装置間の経路を設定する場合には、特定のリンク（物理的及び論理的伝送路）へのトラフィックの集中による輻輳の発生及びネットワークの収容効率の低下を回避するため、経路制御が必要になる。
【０００３】
この経路制御の従来の第１の方法として、装置間のリンク容量に基づくリンクの重み付けにより経路を計算するルーティングプロトコルOpen Shortest Path First (OSPF)を用いる方法がある。しかしながら、この方法では、実際のネットワーク上におけるトラフィックとリンク容量とは無関係であるにも拘わらず、容量の大きいリンクを優先させて経路が計算されるため、容量の大きいリンクに多くの経路が集中し、結果としてそのリンクのトラフィックが容量を超過し輻輳が発生することがあること、容量の小さいリンクが使用されないため、ネットワークの冗長性を活用できず、収容効率が低下することがあること、等の問題点がある。
【０００４】
従来の経路制御の第２の方法として、装置間のトラフィック情報によるリンクの重み付けによって経路を計算するOSPFを拡張した方法がある。この方法は、ネットワーク内の各中継装置が自装置に収容しているリンクのトラフィックを計測し、そのトラフィック情報を隣接装置へ順次通知することにより、ネットワーク全体にトラフィック情報を行き渡らせる方法である。しかしながら、この方法では、ネットワーク全体のトラフィック情報が整合するまでに相当の遅延が発生し、一時的にネットワークの経路制御が不安定になること、ネットワークの大規模化によりトラフィック情報の変動量及び通知対象装置の数が増大するため、遅延が増大し、ネットワークが不安定になる時間が増大すること、トラフィック情報の通知によるリンクの帯域消費も無視できないこと、等の問題点がある。
【０００５】
このトラフィック情報を用いる方法の一つの例として、トラフィック情報の変動に応じて最適な経路を再計算するOSPF Optimized Multipath (OSPF-OMP)を用いる方法がある。この方法では、トラフィック情報が変わる度に経路を再計算する。しかしながら、この方法では、上記の問題点に加えて、経路計算が振動して収束せずにネットワークが不安定になることがあること、各装置が計算した経路が他の装置に通知されないため、各装置が計算する同一着端末への経路がばらばらになり、経路の分岐、ループ等が生じることがあること、等の問題点がある。
【０００６】
トラフィック情報を用いる方法の他の例として、トラフィック情報が変化しても経路を再計算しないQuality of Service Extensions to OSPF (QOSPF)を用いる方法がある。この方法では、或る時点のトラフィック情報に基づいて経路を計算する。しかしながら、この方法では、トラフィックの変動に応じて経路の再構成を行うことができず、トラフィック情報を有効に活用することができないこと等の問題点がある。
【０００７】
【発明が解決しようとする課題】
本発明の目的は、上記の問題点に鑑み、特定のリンクへのトラフィックの集中による輻輳の発生及びネットワークの収容効率の低下を防ぐことができるトラフィック分散型の経路管理方法及びそれを実現するための経路制御装置を提供することにある。
【０００９】
【課題を解決するための手段】
本発明のコネクションレス型通信ネットワークにおける経路管理方法は、上記の目的を達成するため、リンクの経路を一元的に制御する経路制御装置を具え、該経路制御装置がネットワーク内の各端末装置間の経路を管理する場合、トラフィックを受信する着端末装置をルートとし、該着端末装置へトラフィックを送信する発端末装置をリーフとするツリーを計算し、端末装置間の経路は該着端末装置をルートとするツリーのブランチとして管理し、ブランチ毎に経路計算を行い、ネットワークのトラフィック情報が変化した場合に、ブランチ毎に経路を再計算してツリーに追加することを特徴とする。
【００１０】
このような本発明のコネクションレス型通信ネットワークにおける経路管理方法によれば、トラフィック情報の一元的管理手段及びツリーを用いる経路の一元的管理手段としての経路制御装置を具え、これにより、トラフィックを分散するような経路を、ネットワーク内にトラフィックの変動に応じて動的に且つ安定して設定し管理することができる。
【００１２】
本発明のコネクションレス型通信ネットワークの経路制御装置は、ネットワーク内の各端末装置間の経路を管理する場合、トラフィックを受信する着端末装置をルートとし、該着端末装置へトラフィックを送信する発端末装置をリーフとするツリーを計算し、端末装置間の経路は該着端末装置をルートとするツリーのブランチとして管理し、ブランチ毎に経路計算を行い、ネットワークからのトラフィック情報が変化した場合に、ブランチ毎に経路を再計算してツリーに追加することを特徴とする。
【００１３】
このような本発明の経路制御装置によるトラフィック情報の一元的管理においては、従来のようにネットワーク内の中継装置又は端末装置がトラフィック情報を相互にやり取りするのではなく、これらネットワーク内の中継装置又は端末装置がトラフィック情報を経路制御装置に通知し、経路制御装置が一元的にこれを管理して経路設定を行う。これにより、トラフィック情報をネットワーク内の全装置に伝播する必要がなくなり、トラフィック情報の収束時間を考慮する必要がなくなる。従って、本発明の経路制御装置によってトラフィック情報を管理することにより、トラフィック情報の安定性が増し、経路計算への適切なトラフィック情報の提供が可能となり、且つ、大規模ネットワークへの適用性が著しく向上する。
【００１４】
また、経路制御装置によるツリーを用いる経路の一元的管理においては、従来のようにネットワーク内の中継装置又は端末装置がそれぞれ隣接装置への経路を計算し設定するのではなく、経路制御装置が端末装置間の経路を一元的に計算して設定し、更に、同一端末装置を宛先とする経路を一括して、その宛先端末装置をルートとするツリーとして管理する。トラフィック情報の変化に応じてトラフィックを最適にするように経路を計算する場合、トラフィック情報が変化する度に最適経路が変化することにより、既存の経路と新規に計算した経路とが異なる場合に同一端末装置に対して複数の方路が発生してループが生じる可能性があるが、本発明の経路制御装置によれば、各端末装置をルートとするツリーとしてそれぞれの端末装置への経路を一元的に管理し、トラフィック情報の変化に応じて経路をツリーのブランチとして再計算し、ツリーに追加するので、上記のような問題の発生を防ぐことができる。ツリーの各ブランチはルートに対してのみ経路を持ち、ブランチ間の短絡経路は存在しない性質を持つ。従って、本発明の経路制御装置によって経路の一元的管理を行うことにより、経路の分岐、ループ等を発生させることなく、トラフィック情報等、動的に変化する経路の評価パラメータに対応し且つ変化に対応した最適な経路を、動的に且つ安定して計算及び管理することが可能になる。
【００１５】
【発明の実施の形態】
次に、図面を用いて本発明の実施例を説明する。図１は本発明を実施するネットワーク構成の例を示す図である。図中、10は経路制御装置、20、21、22、23は端末装置、30、31、32、33は中継装置、100、101、102、103、104、105はリンクである。ここでは、例えば端末装置20から端末装置22に宛てて送出されたパケットは、途中の中継装置及びリンクを経由して転送される。端末装置は、通信の始点又は終点となることを除き、パケット転送機構については中継装置と同等の機能を有する。
【００１６】
図２は、図１のネットワーク構成の例において、トラフィック情報の入力及び経路設定の動作を説明するための図である。図中、200は対象リンクを収容している中継装置又は保守者から経路制御装置10に対して通知されるトラフィック情報、201は経路制御装置10から中継装置に対して設定される経路情報である。トラフィック情報の取得方法としては、中継装置が実際のトラフィックを測定して得られる場合、保守者が加入者の契約帯域から推定して得る場合等、複数の取得方法があるが、本発明はトラフィック情報の取得方法に依存せず、いずれの取得方法でも用いることができる。
【００１７】
図３は、図１のネットワーク構成の例において、経路制御装置10が保持するリンク帯域情報テーブルの例を示す図である。リンク帯域情報とは、リンクの物理的又は論理的帯域情報であり、経路設定によって流れるトラフィックに応じて変化する。経路制御装置10は、保守者によって入力された管理対象のリンクの物理的又は論理的帯域情報を保持し、経路計算に利用する。
【００１８】
図４は、図１のネットワーク構成の例において、経路制御装置10が保持するトラフィック情報テーブルの例の一部を示す図である。トラフィック情報とは、端末装置間の経路毎に流れるトラフィックの流量である。経路制御装置10は、中継装置又は保守者から通知されたトラフィック情報を保持し、経路計算に利用する。
【００１９】
図５は、本発明における経路制御装置の経路制御処理フローを示す図である。経路制御装置は、中継装置からの通知、保守者からの通知又は他の方法により、各端末装置間のトラフィック情報及びリンク帯域情報を取得し、それぞれのテーブルを保持する（ステップ１）。
【００２０】
経路制御装置は、保守者によって指示された発端末装置から着端末装置への最適経路を計算する（ステップ２）。経路計算方法としては、経路上のリンク帯域の合計が最大になる経路を計算する方法、経路上のリンク帯域の最小値が最大になる経路を計算する方法等、種々の方法を適用することができる。なお、トラフィックに代表されるフローがより多く流れる経路としては、帯域が細いことによるボトルネックを防ぐために、経路上のリンクにおける帯域の最小値が最大である経路が適していると考えられる。これを計算するためのアルゴリズムについては後述する。
【００２１】
経路制御装置は、計算した経路を着端末装置を頂点とするツリーに結合して管理する（ステップ３）。ツリーとは閉路が存在しないネットワーク形状を指す。経路制御装置が着端末装置を頂点とするツリーに追加するアルゴリズムについては後述する。経路制御装置は、次に、リンクに対して経路が設定されたことに対応して、リンク帯域情報テーブルを更新する（ステップ４）。通常は、経路制御装置がリンク帯域からトラフィックを減算した値を新たなリンク帯域とする。
【００２２】
以下に、端末装置間の最適経路を計算する方法の一つであるリンク帯域最小値最大経路計算アルゴリズムを示す。図６はそのアルゴリズムのフロー図である。なお、以下のアルゴリズムにおいて装置とは、端末装置又は中継装置を示す。
【００２３】
＜定義＞
U:発端末装置からの最適経路が得られた装置により構成される集合
V:全装置により構成される集合
c(v):発端末装置v1から装置vまでの経路上のリンク帯域の最大値
w(v1,v2):リンク(v1,v2)のリンク帯域
【００２４】
＜アルゴリズム＞
【数１】
0003653206.tif 000002
【００２５】
以下に、経路上のリンク帯域の最小値が最大である経路を計算し、着端末装置を頂点とするツリーに追加するツリー計算アルゴリズムを示す。なお、以下のアルゴリズムにおいて装置とは、端末装置又は中継装置を示す。
【００２６】
＜定義＞
X:全端末装置により構成される集合
Y:全中継装置により構成される集合
x:Xに属する端末装置
y:Yに属する中継装置
Zx:xを頂点とするツリーに含まれる経路上に存在する装置の集合
BW(x1,x2):x1からx2への経路のトラフィック
c(y):発端末装置x1から中継装置yまでの経路上のリンク帯域の最大値
w(v1,v2):リンク(v1,v2)のリンク帯域
【００２７】
＜アルゴリズム＞
【数２】
0003653206.tif 000003
【００２８】
次に、図１のネットワークにおける端末装置20から端末装置22への経路を設定し、且つ、その後、端末装置21から端末装置22への経路を設定する場合の例を説明する。
【００２９】
先ず、経路制御装置10は、中継装置からの通知、保守者からの通知、又はその他何らかの方法により、リンク帯域情報及びトラフィック情報を取得する。取得した結果として、ここでは、リンク帯域情報として図３のテーブルを用い、トラフィック情報として図４のテーブルを用いるとする。
【００３０】
情報を取得した後、経路制御装置10は、端末装置20を発端末装置とし、端末装置22を着端末装置とする経路を計算する。前述のリンク帯域最小値最大経路計算アルゴリズムを使用する場合、端末装置20から端末装置22に至る複数の経路のうち、端末装置20→リンク100→中継装置30→リンク102→中継装置31→リンク104→中継装置33→リンク105→中継装置32→リンク106→端末装置22の経路が経路上のリンクのリンク帯域の最小値が最大であるため、最適経路として出力されるとする。
【００３１】
経路制御装置は、経路計算の後、端末装置20から端末装置22に至る経路を、端末装置22をルートとするツリーとする。また、端末装置20から端末装置22に至るトラフィックを経路上のリンクの帯域から減算してリンク帯域情報を更新する。更新されたリンク帯域情報は、例えば図７のテーブルに示すようになる。
【００３２】
経路制御装置は、次に、端末装置21を発端末装置とし端末装置22を着端末装置とする経路を計算する。前述のリンク帯域最小値最大経路計算アルゴリズム及びツリー計算アルゴリズムを使用する場合、端末装置21→リンク101→中継装置31までの経路が計算される。中継装置31以降は既存のツリーにより端末装置22までの経路が設定されているため、それ以上の経路は計算されない。従って、端末装置21→リンク101→中継装置31→リンク104→中継装置33→リンク105→中継装置32→リンク106→端末装置22の経路が最適経路として出力される。
【００３３】
この例で、仮にツリー計算アルゴリズムを使用せず、リンク帯域最小値最大経路計算アルゴリズムのみを使用して端末装置21から端末装置22に至る最適経路を計算するとすれば、端末装置21→リンク101→中継装置31→リンク102→中継装置30→リンク103→中継装置32→リンク106→端末装置22の経路が最適経路として計算される。この経路を上記の例で計算された端末装置20から端末装置22に至る経路が既に設定されているネットワークに対して設定すると、端末装置22に至る経路として、中継装置30においては、リンク102とリンク103とが二重に存在し、中継装置31においては、リンク102とリンク104とが二重に存在することになる。同一端末装置への経路が複数存在するような経路設定は、パケットの到着順序の逆転を生じさせ、ネットワークの不安定を引き起こすため、使用できない。
【００３４】
経路制御装置は、経路計算を行った後、最後に、端末装置22を頂点とするツリーに、前述の端末装置20から端末装置22を頂点とするツリーへの経路を追加する。また、端末装置21から端末装置22に至るトラフィックを経路上のリンクの帯域から減算し、リンク帯域情報を更新する。更新されたリンク帯域情報は、例えば図８のテーブルに示すようになる。
【００３５】
本発明の方法を実装した経路制御装置は、上記に示したように、リンク情報及びトラフィック情報を取得し管理し、端末装置間のトラフィックを最適化する経路を計算し、計算した経路を着端末をルートとするツリーに結合し、作成した経路を端末装置及び中継装置に設定する制御動作を行う。
【００３６】
上記実施例においては、端末装置間の経路計算における最適経路を計算するアルゴリズムとして、端末装置間に存在する複数の経路候補のうち端末装置間及び中継装置間を接続する各リンク帯域の容量の最小値を比較しこれが最大である経路を選択するアルゴリズムを用いる例を説明したが、最適経路計算アルゴリズムとして、上記の例とは異なるアルゴリズムを用いる場合であっても本発明を適用して経路を制御できる。このように、本発明は、ネットワークの状況、管理運用の意図等に適する任意の最適経路計算アルゴリズムを用いることができるという柔軟性を具えている。
【００３７】
【発明の効果】
以上説明したように、本発明によれば、コネクションレス型ネットワークにおいて、トラフィックがネットワーク内に均一に分散するようにネットワーク内の経路を制御することが可能になり、且つ、制御中に発生する可能性がある経路情報の収束遅延及び経路の振動を回避することが可能になる。このように、本発明は、トラフィック情報の高収束性及びネットワークの安定性を保持しながらネットワークの収容効率の向上及び輻輳の防止を行うトラフィック分散型の経路制御に必要不可欠な機能を提供することができるという効果を奏する。
【図面の簡単な説明】
【図１】  本発明を実施するネットワーク構成の例を示す図である。
【図２】  図１のネットワーク構成の例において、トラフィック情報の入力及び経路設定の動作を説明するための図である。
【図３】  図１のネットワーク構成の例において、経路制御装置が保持するリンク帯域情報テーブルの例を示す図である。
【図４】  図１のネットワーク構成の例において、経路制御装置が保持するトラフィック情報テーブルの例の一部を示す図である。
【図５】  本発明における経路制御装置の経路制御処理フローを示す図である。
【図６】  端末装置間の最適経路を計算するリンク帯域最小値最大経路計算アルゴリズムのフロー図である
【図７】  図３のテーブルから、図１の端末装置20→端末装置22のトラフィックを減算した後のリンク帯域情報テーブルの例を示す図である。
【図８】  図６のテーブルから、図１の端末装置21→端末装置22のトラフィックを減算した後のリンク帯域情報テーブルの例を示す図である。
【符号の説明】
10  経路制御装置
20、21、22、23  端末装置
30、31、32、33  中継装置
100、101、102、103、104、105、106、107  リンク
200  トラフィック情報
201  経路情報
【図１】
0003653206.tif 000004
【図２】
0003653206.tif 000005
【図３】
0003653206.tif 000006
【図４】
0003653206.tif 000007
【図５】
0003653206.tif 000008
【図６】
0003653206.tif 000009
【図７】
0003653206.tif 000010
【図８】
0003653206.tif 000011