(57)【特許請求の範囲】
【請求項１】
複数のフレーム送受信装置と、これら送受信装置間に配置したフレーム中継装置と、これらの装置間を接続するリンクとを有し、
前記フレーム送受信装置は、複数の出力リンクを有し、送信すべきフレームを形成して他の送受信装置に送信すると共に、送信されてくるフレームを受信し、
前記フレーム中継装置は、複数の出力リンクを有し、送信元のフレーム送受信装置から送信先のフレーム送受信装置に送信されるフレームを中継し、
送信元のフレーム送受信装置から送信先のフレーム送受信装置に向かう経路を送信元のフレーム送受信装置において指定することができるコネクションレス型フレーム中継ネットワークにおける経路制御方法において、
前記フレーム送受信装置、フレーム中継装置及び各リンクにそれぞれ予め割り当てたコストに基づいて送信元の送受信装置から送信先の送受信装置に至る複数の経路を計算する第１の経路計算工程と、
前記第１の経路計算工程により得られた経路に対応した１つ以上の出力リンクを送信元の送受信装置及び経路中に含まれるフレーム中継装置に設定する工程と、
前記第１の経路計算工程において得られた複数の経路の中から１つの経路を選択するための経路計算を行う第２の経路計算工程と、
前記第２の経路計算工程により選択された経路を実際に転送に用いる経路として送信元のフレーム送受信装置に設定する行程とを具え、
前記第１の経路計算行程において、各リンクに当該リンクが経路として選択された回数に対応した選択回数カウンタを設け、前記選択回数カウンタの値を用いるよう拡張したダイクストラアルゴリズムを一回以上動作させて、一つ以上の経路を計算することを特徴とする経路制御方法。
【請求項２】
前記第１の経路計算行程における拡張したダイクストラアルゴリズムは、前記選択回数カウンタが最小であるリンクを選択し、選択回数カウンタが最小であるリンクが複数存在する場合にはその中からコストが最小であるリンクを選択し、選択されたリンクのカウンタを増加させることを特徴とする請求項１に記載の経路制御方法。
【請求項３】
前記第１の経路計算行程における拡張したダイクストラアルゴリズムは、前記選択回数カウンタが閾値以下のリンクのみを用いて全てのフレーム送受信装置およびフレーム中継装置の接続構成を再構成して計算を行い、選択したリンクのカウンタを増加させることを特徴とする請求項１に記載の経路制御方法。
【請求項４】
前記第１の経路計算行程における拡張したダイクストラアルゴリズムは、各リンクのコストと選択回数カウンタとに基づいて一つのパラメータを算出し、経路上の各リンクの前記パラメータの合計が最小となるようリンクを選択し、選択したリンクのカウンタを増加させることを特徴とする請求項１に記載の経路制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はラベルスイッチングを用いてＩＰ−ＶＰＮ等のサービスを提供するＩＰＳ網等のコネクションレス転送網における制御方法に係わり、網構成を冗長化させて信頼性の向上を図る場合において、コネクションレス転送を行ってスケーラビリティを維持しつつ、複数経路から選択的に転送経路を設定することで、故障迂回の迅速化、トラヒック分散によるネットワーク利用効率の向上、帯域予約経路の分散化による品質の向上を図るネットワークの経路制御方法、経路計算方法、経路選択方法、帯域予約管理方法に関する。
【０００２】
【従来の技術】
コネクションレス型通信網においては、２つの端末装置間の経路を計算して、経路上のノードの設定を行う必要がある。従来、自律分散制御を行うネットワークでは、ルーチングプロトコルによりノード同士が自律的に網を構成すると共に固定的に与えられたリンクコストを交換し、各端末間の最短経路をダイクストラ（Ｄｉｊｋｓｔｒａ）の最短経路計算を用いて、宛て先のノードのアドレスに対して出力するべき１つリンクを決定している。
【０００３】
また、管理可能なネットワークにおいては、固定的に与えたリンクコストに基づき各端末間の最短経路をダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムによりサーバを用いて集中的に計算し、ネットワーク全体のノードに対して宛先のノードをアドレスに対して出力するべき１つのリンクを設定する方法が既知である。
【０００４】
さらに、故障迂回経路切替えのための経路変更方法として、故障が発生した場合に、各ノードまたは管理装置が故障を検出して、ネットワーク全体のルーチングを再計算し、全てのノードの転送テーブルの設定を変更する方法がある。
【０００５】
また、トラヒック分散等の用途において複数の経路を同時に用いるために、固定的なリンクコストに基づいて端末間の最短経路を計算する際に、コストが等しく最短である経路が複数存在する場合、これら複数の経路をノードとして設定する方法がある。
【０００６】
その他に、トラヒック分散、故障迂回の用途において前記フレーム中継ネットワークにおいて複数の経路を同時に用いる方法として、最短経路だけではなく明示的に示した経路を用いるために、最短経路以外の経路が必要となった際に要求を満たす経路を計算し、求められた経路上の全てのフレーム中継装置を指定してフレーム送受信装置間でシグナリングを行って、経路上の全てのノードの転送テーブルの設定を行い、特定のトラヒツクのみを指定したフレーム中継経路を経由させる方法がある。
【０００７】
また、帯域予約を行う場合の帯域予約方法として、予約を行うノード間において、経路計算によりあらかじめ決定された一つの経路を把握し、該経路上のリンクの帯域を確保する方法がある。
【０００８】
【発明が解決しようとする課題】
前記最短経路を計算して１つの経路のみを設定する方法では、各端末間の経路が一つのリンクを共有するので、トラヒックが集中してしまい、ネットワーク利用効率の低下および品質の劣化を招く問題がある。
【０００９】
また、前記最短経路を計算して経路を設定する方法では、固定的なリンクコストのみを用いて転送経路が決定されるため、変動するトラヒック量に対して適応的に経路を選択することができないという問題がある。
【００１０】
また、故障迂回の経路切替えのための経路変更方法については、ネットワーク規模の拡大に伴って再計算と再設定の量が著しく増大し、スケーラビリティが低下するだけでなく、切り替え時間の増大が発生するという問題がある。
【００１１】
さらに、前記コストが等しく最短である経路を複数用いる方法では、同一フローに属するトラヒツクが異なる経路を経由するため、送信先端未におけるパケットの到着順序の逆転や、品質制御のための経路上の帯域予約の困難が生じる等の問題がある。この問題を解消するため、各ノードにおいてフローと経路をマッピングする設定を行い、フローを識別して同一のトラヒックに属するパケットを同一の経路に転送する方法がある。しかしながら、この方法では、フロー数の増大に伴い各ノードにおけるフロー識別処理が増加し、スケーラビリティを低下させる問題がある。また、コストが等しく最短である複数の経路は、経路同士の独立性を考慮して計算されていないため、必ずしもトラヒック分散および故障迂回が可能な経路ではない問題がある。
【００１２】
また、前記明示的に示した経路を用いる方法では、送信側と受信側のフレーム送受信装置間にコネクション型の経路を設定するため、フレーム中継装置の転送テーブルが増大し、フレーム送受信装置の増加に対するスケーラビリティが低下する問題がある。さらに、最短経路以外の経路の必要が生じてからネットワーク全体に対して経路の再計算を行うため、ネットワークのノード数の増大に伴って計算時間が増大し、特に故障迂回に関して迅速な経路設定が困難となる問題がある。また、経路変更が発生する都度、新たに設定される経路上の全てのフレーム中継装置に対して設定を行うため、帯域予約を契機とした経路変更等が頻繁に発生する経路切替え設定に対するフレーム中継装置の処理コスト及び管理コストが増大する問題がある。
【００１３】
さらに、前記帯域予約方法においては、帯域予約を行う経路が一つに決定されているため、当該経路において予約可能な帯域がない場合、ネットワーク全体として予約可能な帯域があったとしても、当該経路とは別の経路を用いて予約を行うことができず、ネットワーク利用効率を低下させるという問題があった。
【００１４】
本発明は従来技術の問題点を解決するためになされたものであり、本発明の第一の目的は、トラヒック分散および故障迂回のための経路変更において、フレーム中継経路に対する設定変更を抑制し、経路再計算における計算量を抑制する経路制御方法を提供することである。
【００１５】
また、 本発明の第２の目的は、複数経路を用いてトラヒック分散を行うための経路制御において、コネクションレス型転送経路を計算し、経路を分散させるための独立性を考慮した複数の経路を計算する方法を提供することである。
【００１６】
また、本発明の第三の目的は、フロー毎の経路を確定させてパケットの到着順序逆転を防止するともに帯域予約を可能にし、帯域保証トラヒックの量に基づいて複数経路が用いられたトラヒック分散を行う経路決定と、ネットワーク利用効率の向上および品質の均等化を実現する帯域予約を行う経路制御方法、経路選択方法及び帯域予約管理方法を提供することである。
【００１７】
【課題を解決するための手段】
上記目的を達成する手段として、
任意の送信元フレーム送受信装置から任意の送信先フレーム送受信装置へ向う経路を制御する場合に、
フレーム送受信装置およびフレーム中継装置の接続構成と各リンクに付与されパラメータ（コスト）に基づいて一つ以上の経路を計算する第１の経路計算工程を実施し、実際に通信を行う一つの送信元フレーム送受信装置から一つの送信先フレーム送受信装置へ向かう一つ以上の経路の中から一つの経路を選択する第２の経路計算工程を実施し、第２の経路計算工程により選択された経路を実際に転送に用いる経路として送信元のフレーム送受信装置に設定する行程を実施し、第１の経路計算行程において、各リンクに当該リンクが経路として選択された回数に対応した選択回数カウンタを設け、選択回数カウンタの値を用いるよう拡張したダイクストラアルゴリズムを一回以上動作させて、一つ以上の経路を計算する。
【００１９】
また、経路を分散させるための独立性を考慮した複数の経路を計算する手段と以下の手段を設ける。
本発明のコストに基づいた一つ以上の経路の計算方法は、ダイクストラ（Ｄｉｊｋｓｔｒａ）アルゴリズムにおいて各リンクに選択回数カウンタを設けて拡張して、
選択回数カウンタが最小であるリンクを選択し、選択回数カウンタが最小であるリンクが複数存在する場合にはその中からコストが最小であるリンクを選択し、選択したリンクのカウンタを増加させ、
一回以上計算を行うことで一つ以上の経路を計算するようにしたものである。
【００２０】
本発明のコストに基づいた一つ以上の経路の計算方法は、ダイクストラ（Ｄｉｊｋｓｔｒａ）アルゴリズムにおいて各リンクに選択回数カウンタを設けて拡張して、
各リンクのコストと選択回数カウンタを基に一つのパラメータを算出し、
経路上の各リンクの前記パラメータの合計が最小となるようにしたものである。上記の一つ以上の経路を計算する手段は、いずれも経路を分散させるための独立性を考慮した複数の経路を計算する課題を解決するものであり、ネットワーク構成等により適宜選択的に使用可能。
【００２５】
【作用】
本発明による経路制御方法によれば、最初に同一のフレーム送受信間で複数の経路の計算を行って、フレーム中継装置に設定を行うため、フレーム送受信間で複数の経路をあらかじめ設定することが可能となる。また、実際に通信に行う際に、一つの送信元フレーム送受信装置から一つの送信先フレーム送受信装置へ向けた複数の経路の中から使用する経路を選択する計算を行うため、帯域予約可能な経路、トラヒックを分散させる経路、および故障を迂回する経路などの要求を満たす経路を選択することが可能となる。さらに、実際に通信を行う経路の設定は送信元フレーム送受信装置に付する経路の選択の設定のみであるため、フレーム中継装置に対する設定を抑制することが可能となる。
【００２６】
また、前記選択回数カウンタが最小であるリンクを選択し、選択回数カウンタが最小であるリンクが複数存在する場合にはその中からコストが最小であるリンクを選択し、選択したリンクのカウンタを増加させるよう拡張したダイクストラ（Ｄｉｊｋｓｔｒａ）アルゴリズムを利用した経路計算方法によれば、
全てのリンクのカウンタが等しい場合は最短経路を計算し、
複数の経路を計算する際には既に選択したリンクを避けて計算するため、実際に通信する際の経路選択において、トラヒック分散によるネットワーク利用効率向上および品質の均等化が可能な、経路同士の独立性が高い複数の経路を計算することが可能となる。
【００２７】
また、前記選択回数カウンタが閾値以下のリンクのみを用いて全てのフレーム送受信装置およびフレーム中継装置の接続構成を再構成して計算を行い、
選択したリンクのカウンタが等しい場合は最短経路を計算し、
全てのリンクのカウンタが等しい場合は最短距離を計算し、
複数の経路を計算する際には選択回数の少ないリンクのみで構成される経路を計算するため、実際に．通信する際の経路選択において、トラヒック分散によるネットワーク利用効率向上および品質の均等化が可能な、経路同士の独立性が高い複数の経路を計算することが可能となる。
【００２８】
また、前記各リンクのコストと選択回数カウンタを基に一つのパラメータを算出し、経路上の各リンクの前記パラメータの合計が最小となるようリンクを選択し、選択したリンクのカウンタを増加させるよう拡張したダイクストラ（Ｄｉｊｋｓｔｒａ）アルゴリズムを利用した経路計算方法によれば、
複数の経路を計算する際にリンクの選択回数を考慮に入れた経路計算を行って、実際に通信する際の経路選択において、トラヒック分散によるネットワーク利用効率向上および品質の均等化が可能な、経路同士の独立性が高い複数の経路を計算することが可能となる。
【００２９】
上記三つの方法いずれを用いても、経路同士の独立性が高い複数の経路を計算する、同様の作用を得ることができ、ネットワーク構成等に応じて適宜選択的に使用することが可能である。
【００３０】
また、前記帯域予約を基に複数経路の中から実際に通信に用いる経路を帯域保証トラヒックが予約する帯域と他の帯域保証トラヒックにより予約済みの帯域との合計がネットワーク内でより均等となるように一つの経路を選択する方法では、ネツトワーク内で帯域保証トラヒックが均等となるように帯域予約が行われ、ネツトワーク内の一部が局所的に幅輳することがなくなるため、転送品質を均等化することが可能となる。
【００３１】
また、前記帯域予約を基に複数経路の中から実際に通信に用いる経路を送信元フレーム送受信装置から送信先フレーム送受信装置までの各リンクのコストの合計が最小となる一つの経路を選択する方法では、
最短経路だけでなく設定されている経路の中で帯域予約が可能な最短の経路を選択するため、帯域予約の対象となる経路が増えることにより帯域予約の可能性が向上し、その結果ネットワーク利用効率を向上させることが可能となる。
【００３２】
また、前記任意のフレーム中継装置または任意のリンクが故障した場合に、該フレーム中継装置またはリンクを経由する経路について、前記フレーム中継装置に設定されている複数の経路の中から前記故障したフレーム中継装置またはリンクを経由せず、かつ前記任意のフレーム送受信装置へ向かう経路を選択する方法では、故障に関係する経路のみ変更を行うため、経路変更に関する経路の再計算・再設定処理を抑制することが可能となる。
【００３３】
また、本発明による経路計算方法の帯域予約管理工程において、経路選択方法により、複数の経路から選択された経路を用いて予約を行い、帯域保証トラヒックの分散により、ネットワーク利用効率の向上および品質の均等化が可能となる。
【００３４】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
図１は本発明による経路制御方法が適用されるネットワーク構成の一例を示すブロック図である。図１において、符号１及び２はパケット送受信装置を示し、符号３及び４はフレーム送受信装置を示し、符号５及び６はフレーム中継装置を示し、符号１０〜１４はリンクを示す。フレーム送受信装置３はフレーム出力リンク３０及び３１を有し、フレーム送受信装置４はフレーム出力リンク４３及び４４を有し、フレーム中継装置５はフレーム出力リンク５０、５２及び、５３を有し、フレーム中継装置６はフレーム出力リンク６１、６２及び６４を有する。
【００３５】
図２はパケット送受信装置が送信するパケットの一例を示す図である。ＩＰパケット２０は、ＩＰヘッダ２１を有し、ＩＰヘッダには送受信装置の識別子である送信先ＩＰアドレス２３、送信元ＩＰアドレス２４、上位プロトコル２５などを記述する。
【００３６】
図３はフレーム中継ネットワークで転送されるフレームの一例であるコアフレーム２６の構成を示す図である。コアフレーム２６はＩＰパケット２０にコアヘッダ２７が付加されたものであり、コアヘッダには、送信先フレーム送受信装置の識別子である送信先コアアドレス２８と、同一送信先フレーム送受信装置に村する複数の経路から一つの方路を特定するためのＲｏｕｔｅ  ＩＤ（２９）などを記述する。
【００３７】
パケット送受信装置１からパケット送受信装置２宛に送信されたパケットは、フレーム送受信装置３において、フレーム送受信装置４を送信先とするヘッダが付加されてフレームが構成され転送される。当該フレームはフレーム中継装置およびリンクを経由し、フレーム送受信装置４によって受信され、ヘッダが取り除かれてパケットに戻され、 パケットの送信先であるパケット送受信装置２に転送される。そして、当該パケットはパケット送受信装置２によって受信される。
【００３８】
図４はフレーム送受信装置３の一例の構成を示すブロック図である。フレーム送受信装置３はコアヘッダ付加部３３とコアフレーム中継部３５からなる。コアヘッダ付加部３３は、コアヘッダ生成テーブル３４に基づき、ＩＰパケット２０の送信先ＩＰアドレス２３からフレームの送信先コアアドレス２８を決定し、ポート番号２２、送信先ＩＰアドレス２４、上位プロトコル２５からトラヒックを識別してＲｏｕｔｅ  Ｉｄ（２９）を決定し、コアヘッダを生成してコアフレームを構成する。コアフレーム中継部３５は、コアフレームの送信先コアアドレス２８とＲｏｕｔｅ  ＩＤ（２９）から出力リンクを導く転送テーブル３６を有し、出力リンクを決定し、出力リンク選択部３７によりフレームを出力するリンクを出力リンク３０及び３１から選択し、コアフレーム２６を出力する。
【００３９】
図５はフレーム中継装置５の構成の例を示すブロック図である。フレーム中継装置はコアフレーム中継部５５を有し、このコアフレーム中継部５５は、ＩＰパケット２０を受信するコアフレーム受信５１と、転送テーブル５６と、出力リンクを選択する出力リンク選択部５７とを具える。このコアフレーム中継部５５において、コアフレームの送信先コアアドレス２８とＲｏｕｔｅ  ＩＤ（２９）から出力リンクを導く転送テーブル５６を形成し、出力リンクを決定し、出力リンク選択部５７によりフレームを出力するためのリンクを出力リンク５０、５２及び５３から選択し、コアフレーム２６を出力する。
【００４０】
図６は本発明の経路制御方法を実施するための経路制御処理装置の一例の構成を示すブロック図である。経路制御処理装置１００は、複数経路計算処理部１１０と、複数経路設定処理部１２０と、経路選択計算処理部１３０と、選択経路設定処理部１５０とを具える。複数経路計算処理部１１０はネットワーク構成情報２０１（ネットワーク接続構成、リンクコスト等を含む）を入力として、全ての送信元フレーム送受信装置と送信先フレーム送受信装置との組について、複数の経路を算出する計算を行う。算出された経路は、送信先フレーム送受信装置のコアアドレスとＲｏｕｔｅ  ＩＤとから出力リンクを導く転送テーブル３６及び５６として、複数経路設定処理部１２０によって送信元となるフレーム中継装置５及び６に対して設定される。
【００４１】
経路選択計算処理部１３０は、任意の送信元フレーム送受信装置から任意の送信先フレーム送受信装置へ向かう経路を、上記複数経路計算処理部１１０によって計算された複数の経路から一つの経路を選択する計算を行う。選択された一つの経路は、選択経路設処理１５０により、トラヒック識別情報から送信先コアアドレスとＲｏｕｔｅ  ＩＤを導くフレームヘッダ生成テーブルとして、送信元となるフレーム送受信装置３、４に対して設定される。
【００４２】
以下に本発明の経路計算方法の実施の形態をアルゴリズム表記によって説明する。下記のアルゴリズムにおいて、装置とはフレーム送受信装置ないしはフレーム中継装置を意味するものである。まず、アルゴリズムで用いるパラメータの定義を示す。
＜定義＞
Ｖ：全装置により構成される集合
Ｄ：各リンクの選択回数カウンタによってネットワーク構成を再構成した後にネットワークに含まれるリンクによって構成される集合
Ｅ：全リンクにより構成される集合
Ｔ：経路計算の出発点となるフレーム送受信装置ｖ１から他の全フレーム送受信装置までの経路に含まれるリンクによって構成される集合
Ｕ：経路計算の出発点となるフレーム送受信装置ｖ１から自身までの経路が未確定の装置によって構成される集合
ｄ（ｖ）：経路計算の出発点となるフレーム送受信装置ｖ１から装置ｖまでの経路に含まれる各リンクコストの合計
ｆ（ｖ）：経路計算の出発点となるフレーム送受信装置ｖ１から装置ｖまでの経路上における装置ｖの直前の装置
ｗ（ｖ，ｕ）：リンク（ｖ，ｕ）、すなわち装置ｖと装置ｕとの間のリンクのコスト
ｅｃ（ｖ，ｕ）：リンク（ｖ，ｕ）の選択回数カウンタ値
ｖｃ（ｖ）：装置ｖが保存する、フレーム送受信装置ｖ１から装置ｖまでの経路上のリンクにおいて装置ｖが接続するリンクのカウンタ値。
ｇ（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ））：リンク（ｖ，ｕ）のコストｗ（ｖ，ｕ）とカウンタ値ｅｃ（ｖ，ｕ）とによって計算されるパラメータ値
ｄｇ（ｖ）: 経路計算の出発点となるフレーム送受信装置ｖ１から装置ｖまでの経路に含まれる、ｇ（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ））によって計算される各リンクのパラメータの合計
【００４３】
次にアルゴリズムを以下に示す。
本発明の実施の形態として以下に示すダイクストラ（Ｄｉｊｋｓｔｒａ）を拡張したアルゴリズムは、多重辺のない単純グラフに対して適用する。多重グラフから単純グラフへの写像を得るための一計算例としては、２つのノードの全ての組について各ノード間にリンク（ｖ，ｕ）がｎ本（ｎ≧２）存在するとき、ｍｉｎ｛ｅｃ（ｖ，ｕ）｜∀ｅｃ（ｖ，ｕ）｝となる（ｖ，ｕ）をｖとｕの間のリンクとしてネットワーク構成を再構成することで単純グラフを得ることができる。
【００４４】
以下において、初めに各リンクに選択回数カウンタを設け、経路計算の出発点からの合計コストが最小のノードを選択し、該ノードとすでに経路が決定されたノードとの集合とが複数のリンクにより接続されている場合に、選択回数カウンタが最小となるリンクを選択する。尚、選択回数カウンタが最小となるリンクが複数存在する場合には、その中からコストが最小であるリンクを選択する。そして、選択したリンクのカウンタを増加させるよう拡張したダイクストラ（Ｄｉｊｋｓｔｒａ）アルゴリズムを利用した経路計算方法のアルゴリズム表記を以下に示す。
＜アルゴリズム１＞
【００４５】
【数１】
0003759416.tif 000002
【００４６】
上記のアルゴリズムにおいて、最初の「ｂｅｇｉｎ］はアリゴリムの先頭を示し、８番目の「ｅｎｄ」はあるアルゴリズムの終了を示す。「ｄ（ｖｌ）：＝０」は経路計算の出発点となるフレーム送受信装置ｖ１から装置ｖ１までの経路に含まれるリンクコストの合計を０に初期化することを意味する。「ｅｃ（ｅ）：０；」はリンクｅのカウンタを０に初期化することを意味する。また、アルゴリズム「ｆｏｒｋ：＝０  ｕｎｔｉｌ  ｋ＜計算する経路数ｄｏ」から７番目の「」までのｆｏｒループはｋを０で初期化し、式「ｋ＜計算する経路数」が成立する間、ｋを１ずつ増加させながらループ内の処理を繰り返し、ｖ１を経路計算の出発点とする経路をｋ個求める計算を行うことを意味し、ｆｏｒループ内にある２番目の「ｂｅｇｉｎ」はループ処理の先頭を示し、７番目の「ｅｎｄ」はループ処理の最後尾を示す。
【００４７】
「Ｔ：＝  φ；」は、Ｔを空集合で初期化することを意味する。
「Ｕ：＝Ｖ−｛ｖ｝」は、Ｕを全装置の集合Ｖから経路計算の出発点となるフレーム送受信装置ｖ１を除いた装置によって構成される集合で初期化することを意味する。
「ｄ（Ｖ）：＝  ∞；」は、フレーム送受信装置ｖ１から装置Ｖまでの経路に含まれるリンクコストの合計を無限大に初期化することを意味する。
「ｖｃ（Ｖ）：＝∞；」は、装置ｖが保持する、フレーム送受信装置ｖ１から装置ｖまでの経路上のリンクで装置ｖが接続するリンクのカウンタ値を無限大に初期化することを意味する
【００４８】
３番目の「ｂｅｇｉｎ」から１番目の「ｅｎｄ」までのループは、ｖ１に隣接する各装置について、アルゴリスム「ｄ（ｕ）：＝ｗ（ｖ１，ｕ）；」によって、フレーム送受信装置ｖｌから装置ｕまでの経路に含まれるリンクコストの合計ｄ（ｕ）にリンク（ｖｌ，ｕ）のコストｗ（ｖｌ，ｕ）を設定し、アルゴリスム「ｆ（ｕ）：＝ｖ１」によって、フレーム送受信装置ｖ１から装置ｕまでの経路上でｕの直前の装置をｖ１に設定していることを示す。
「ｗｈｉｌｅ  Ｕ≠φ  ｄｏ」は４番目の「ｂｅｇｉｎ」から４番目の「ｅｎｄ」までの処理をＵ≠φが成立する間、繰り返すループ処理を意味する。
「Ｕ：＝Ｕ−｛ｖ｝；」は選択された集合Ｕから除くことを意味する。
【００４９】
さらに、装置ｖに隣接する各装置ｕについて、
アルゴリスム「ｉｆ  ｖｃ（ｕ）＞ｅｃ（ｖ，ｕ）ｔｈｅｎ」によって、ｃ（ｖｃ）＞ｅｃ（ｖ，ｕ）が成立する場合は５番目の「ｂｅｇｉｎ」から２番目の「ｅｎｄ」の処理を行い、装置ｕはよりリンクカウンタ値の小さいリンク（ｖ，ｕ）を用いる経路に変更され、
アルゴリスム「ｄ（ｕ）：＝ｄ（ｖ）＋Ｗ（ｖ，ｕ９；」により装置ｖ１から装置ｕまでのリンクコストの合計が変更され、
アルゴリスム「ｆ（ｕ）：＝Ｖ；」により装置ｖｌから装置ｕまでの経路上の装置ｕの直前の装置が装置ｖであるように変更され、並びに、
「ｖｃ（ｕ）：＝ｅｃ（ｖ，ｕ）；」により装置ｕが保持する、装置ｕが接続すウンタ値が装置ｖと装置ｕの間のリンクカウンタ値ｅｃ（ｖ，ｕ）に変更されることを意味する。
【００５０】
また、アルゴリスム「ｅｌｓｅ  ｉｆ  ｖｃ（ｕ）＝ｅｃ（ｖ，ｕ）ｔｈｅｎ」によって、カウンタ値ｖｃ（ｕ）とリンクカウンタｅｃ（ｖ，ｕ）が等しい、つまりｖｃ（ｕ）＝ｅｃ（ｖ，ｕ）が成立する場合は６番目の「ｂｅｇｉｎ」から３番目の「ｅｎｄ」の処理を行い、
さらに加えて、ｄ（ｕ）＞ｄ（ｖ）＋Ｗ（ｖ，ｕ）が成立する場合には、装置ｕはよりリンクコストの合計が小さくなるリンク（ｖ，ｕ）を用いる経路に変更され、
アルゴリスム「ｄ（ｕ）：＝ｄ（ｖ）＋Ｗ（ｖ，ｕ）；」により装置ｖ１から装置ｕまでのリンクコストの合計が変更され、並びに、
アルゴリスム「ｆ（ｕ）：＝Ｖ；」により装置ｖｌから装置ｕまでの経路上の装置ｕの直前の装置が装置ｖであるように変更されることを意味する。
【００５１】
また、選択したリンクのカウンタを増加させるために、ｖに含まれる各フレーム送受信装置ｖについて、７番目の「ｂｅｇｉｎ」から６番目の「ｅｎｄ」の処理を行う。ここで、
アルゴリスム「ｕ：＝ｖ；」はｕをフレーム送受信装置ｖで初期化することを意味し、
アルゴリスム「ｗｈｉｌｅ  ｕ≠ｖ１  ｄｏ」は８番目の「ｂｉｇｉｎ」から５番目の「ｅｎｄ」のループ処理をｕ≠ｖ１が成立する間、繰り返すことを示す。
【００５２】
ループ処理では、
「Ｔ：＝Ｔ∪｛（ｆ（ｕ），ｕ）｝；］によって、装置ｕと経路上で装置ｕに至る直前の装置ｆ（ｕ）との間のリンク（ｆ（ｕ），ｕ）を算出した経路に含まれるリンクで構成される集合Ｔに加え、「ｕ：＝ｆ（ｕ）；」により装置ｕを経路上で装置ｕに至る直前の装置ｆ（ｕ）に改める。
ｕ≠ｖｌが成立する間、繰り返すことにより装置ｖから装置ｖ１までの経路上のリンクを全てＴに含めることを意味する。
「ｅｃ（ｅ）：＝ｅｃ（ｅ）＋１；」はＴに含まれる、経路として選択したリンクｅのカウンタを増加させることを意味する。
【００５３】
次に、上記アルゴリズムに基づく計算例を図面により説明する。以下、図１のネットワークにおけるフレーム送受信装置３からのフレーム送受を示す。尚、本計算例では、送信先フレーム送受信装置４を経路計算の出発点とするが、送信元フレーム送受信装置３を経路計算の出発点とすることもできる。
【００５４】
表１に図１に示す各リンクのコストを示す。
【００５５】
【表１】
0003759416.tif 000003
【００５６】
アルゴリズムの計算開始時においては、経路計算の出発点となる装置４のｄ（４）は０に初期化され、各リンクのカウンタも表２の値の通りに０に初期化される。
【００５７】
【表２】
0003759416.tif 000004
【００５８】
続いて、１つ日の経路の計算を行う。
各パラメータは初期化され表３の値をとる。
【００５９】
【表３】
0003759416.tif 000005
【００６０】
すなわち、集合ｕは送信先フレーム送受信装置４を除いた全装置を含み、フレーム送受信装置４からの経路上のリンクコストの合計値ｄ（３）、ｄ（５）、ｄ（６）は無限大に、各装置が経路上で直前に接続するリンクのカウンタ値であるｖｃ（３）、ｖｃ（４）、ｖｃ（５）、ｖｃ（６）は全て無限大に初期化される。
【００６１】
ｗｈｉｌｅループの実行の前に、送信先フレーム送受信装置４に隣接する装置パラメータが設定され、表４の値をとる。
【００６２】
【表４】
0003759416.tif 000006
【００６３】
すなわち、フレ−ム中継装置５については、
ｄ（５）には送信先フレーム送受信装置４との間のリンクコストである４が、
ｆ（５）には接続先である送信先フレーム送受信装置４の装置番号の４が、
ｖｃ（５）接続するリンクのカウンタ値０がそれぞれ設定される。
また、フレ−ム中継装置６については、
ｄ（６）には送信先フレーム送受信装置４との間のリンクコストである５が、
ｆ（６）には接続先である送信先フレーム送受信装置４の装置番号の４が、
ｖｃ（６）接続するリンクのカウンタ値０がそれぞれ設定される。
【００６４】
ｗｈｉｌｅループの第１回目の実行では、Ｕに含まれる装置３、５及び６のうちｄ（ｖ）が最小の装置５が選択され、経路の一部となり、集合ｕから除かれる。Ｕに含まれる装置３及び６のうち装置５に隣接する装置３及び装置６について「ｉｆ....」のアルゴリスムを実行する。
【００６５】
装置３については、
ｖｃ（３）は∞であり、ｅｃ（５，３）は１であるため、アルゴリスム「ｉｆｖｃ（ｕ）＞ｅｃ（ｖ，ｕ）  ｔｈｅｎ」が実行され、ｄ（３）についてはｄ（５）＋ｗ（５，３）の結果の６が設定され、ｆ（３）については５が設定され、ｖｃ（３）には１が設定される。
また、装置６については
ｖｃ（６）は０であり、ｅｃ（５，６）は０であるため、アルゴリスム「ｅｌｓｅ  ｉｆ  ｖｃ（）＞ｅｃ（ｖ，ｕ）  ｔｈｅｎ」が実行され、ｄ（６）は５、ｄ（５）は４、ｗ（５，６）は３であるため、アルゴリスム「ｉｆ  ｄ（ｕ）＞ｄ（ｖ）＋ｗ（ｖ，ｕ）ｔｈｅｎ」が実行されない。そして、パラメータは、表５の値となる。
【００６６】
【表５】
0003759416.tif 000007
【００６７】
ｗｈｉｌｅループの第２回目の実行において、Ｕに含まれる装置３及び６のうちｄ（ｖ）が最小の装置６が選択され、経路の一部となり、集合Ｕから除かれる。Ｕに含まれる装置で、装置６に隣接する装置３についてアルゴリスム「ｉｆ..... 」を実行する。ｖｃ（３）は１であり、ｅｃ（６，３）は０であるため、アルゴリスム「ｉｆ  ｖｃ（ｕ）＞ｅｃ（ｖ，ｕ）  ｔｈｅｎ」が実行される。また、ｖｃ（３）は１であり、ｅｃ（６，３）は０であるため、アルゴリスム「ｉｆ  ｖｃ（ｕ）＞ｅｃ（ｖ，ｕ）  ｔｈｅｎ」は実行されない。パラメータは表６の値となる。
【００６８】
【表６】
0003759416.tif 000008
【００６９】
ｗｈｉｌｅループの第３回目の実行では、Ｕに含まれるただ一つの装置３が選択され、経路の一部となり、集合ｕから除かれ、集合Ｕはφとなる。Ｕに含まれる装置は存在しないため、アルゴリスム「ｉｆ........」は実行されない。パラメータは、表７の値となる。以上でｗｈｉｌｅループが終了する。
【００７０】
【表７】
0003759416.tif 000009
【００７１】
次に、Ｖに含まれるフレーム送受信装置装置３、４については、
装置３については、
「ｗｈｉｌｅ  ｕ≠ｖｌ  ｄｏ」が実行され、第１回目のｗｈｉｌｅループにおいてＴに（５，３）すなわちリンク１０が加わり、第２回目のｗｈｉｌｅループで、Ｔに（４，５）すなわちリンク１３が加わりｗｈｉｌｅループ処理が終了する。
装置４については、
「ｗｈｉｌｅ  ｕ≠ｖｌ  ｄｏ」は実行されない。ここで、表８に示す通り、Ｔに含まれるリンク１０及び１３が求めた経路である。
【００７２】
【表８】
0003759416.tif 000010
【００７３】
リンク１０、リンク１３について表９に示す通りｅｃ（１０），ｅｃ（１３）がそれぞれ１に設定される。
【００７４】
【表９】
0003759416.tif 000011
【００７５】
続いて、２つ目の経路の計算を行う。各パラメータは初期化され表１０の値をとる。
【００７６】
【表１０】
0003759416.tif 000012
【００７７】
すなわち、集合Ｕは送信先フレーム送受信装置４を除いた全装置を含み、フレーム送受信４からの経路上のリンクコストの合計値ｄ（３），ｄ（５）、ｄ（６）は無限大に初期化され、各装置が経路上で直前に接続されるリンクのカウンタ値であるｖｃ（３），ｖｃ（４），ｖｃ（５），ｖｃ（６）はそれぞれ無限大に初期化される。
【００７８】
ｗｈｉｌｅループの実行の前に、送信先フレーム送受信装置４に隣接する装置のパラメータが設定され、表１１の値をとる。
【００７９】
【表１１】
0003759416.tif 000013
【００８０】
すなわち、フレーム中継装置５についは、
ｄ（５）には送信先フレーム送受信装置４との間のリンクコストである４が設定され、ｆ（５）には接続先である送信先フレーム送受信装置４の装置番号の４が設定され、ｖｃ（５）には接続するリンクのカウンタ値１が設定される。
また、フレーム中継装置６については、
ｄ（６）には送信先フレーム送受信装置４との間のリンクコストである５が設定され、ｆ（６）には接続先である送信先フレーム送受信装置４の装置番号の４が設定され、ｖｃ（６）には接続するリンクのカウンタ値０が設定される。
【００８１】
ｗｈｉｌｅループの第１回目の実行では、集合Ｕに含まれる装置３、５及び６のうちｄ（ｖ）が最小の装置５が選択され、経路の一部となり、集合Ｕから除かれる。Ｕに含まれる装置３及び６のうち装置５に隣接する装置３及び６についてアルゴリスム「ｉｆ........... 」を実行する。
【００８２】
装置３については、
ｖｃ（３）は∞であり、ｅｃ（５，３）は０であるため、「ｉｆ  ｖｃ（ｕ）＞ｅｃ（ｖ，ｕ）  ｔｈｅｎ」が実行され、ｄ（３）にｄ（５）＋ｗ（５，３）の結果の６が設定され、ｆ（３）には５が設定され、ｖｃ（３）には０が設定される。
また、装置６については
ｖｃ（６）は０であり、ｅｃ（５，６）は０であるため、「ｅｌｓｅ  ｉｆｖｃ（ｕ）＝ｅｃ（ｖ，ｕ）  ｔｈｅｎ」が実行され、ｄ（６）は５であり、ｄ５）は４であり、ｗ（５，６）は３であるため、「ｉｆ  ｄ（ｖ）＞ｄ（ｖ）＋ｗ（ｖ，ｕ）ｔｈｅｎ」は実行されない。パラメータは表１２に示す通りとなる。
【００８３】
【表１２】
0003759416.tif 000014
【００８４】
ｗｈｉｌｅループの第２回目の実行では、集合Ｕに含まれる装置３及び６のうちｄ（ｖ）が最小の装置６が選択され、経路の一部となり、集合Ｕから除かれる。Ｕに含まれる装置６のうち装置６に隣接する装置３についてアルゴリスム「ｉｆ........」を実行する。ｖｃ（３）は１、ｅｃ（６，３）は０であるため、「ｉｆ  ｖｃ（ｕ）＞ｅｃ（ｖ，ｕ）  ｔｈｅｎ」が実行され、ｖｃ（３）は０、ｅｃ（６，３）は０であるため、「ｅｌｓｅ  ｉｆ  ｖｃ（ｕ）＞ｅｃ（ｖ，ｕｔｈｅｎ」が実行され、ｄ（３）には６が設定され、ｄ（６）には８が設定され、ｆ（３）には６が設定され、ｖｃ（３）に０が設定される。パラメータは表１３に示す通りとなる。
【００８５】
【表１３】
0003759416.tif 000015
【００８６】
ｗｈｉｌｅループの第３回目の実行では、集合Ｕに含まれるただ一つの装置３が選択され、経路の一部となり、集合Ｕから除かれ、集合Ｕはφとなる。Ｕに含まれる装置はないため、アルゴリスム「ｉｆ........... 」は実行されない。パラメータは表１４に示す通りとなる。以上でｗｈｉｌｅループが終了する。
【００８７】
【表１４】
0003759416.tif 000016
【００８８】
次に、集合ｖに含まれるフレーム送受装置３及び４についてｗｈｉｌｅループを実行する。
装置３については、
「ｗｈｉｌｅ  ｕ≠ｖｌ  ｄｏ」が実行され、第１回目のｗｈｉｌｅループによりＴに（６、３）すなわちリンク１１が加わり、第２回目のｗｈｉｌｅループによりＴに（６、３）すなわちリンク１４が加わりｗｈｉｌｅループが終了する。
装置４については、
「ｗｈｉｌｅ  ｕ≠ｖｌ  ｄｏ」が実行されない。ここで、表１５に示す通り、Ｔに含まれるリンク１１及び１４が求めた経路となる。
【００８９】
【表１５】
0003759416.tif 000017
【００９０】
リンク１１及びリンク１４について、  ｅｃ（１１），ｅｃ（１４）に１が加算され、表１６に示す通りそれぞれ１及び１に設定される。
【００９１】
【表１６】
0003759416.tif 000018
【００９２】
以上で、フレーム送受信装置３からフレーム送受信装置４への２つの経路、
装置３→リンク１０→装置５→リンク１３→装置４と
装置３→リンク１１→装置６→リンク１４→装置４と
が求まった。これら２つの経路７１及び７２をとして図７に示す。
【００９３】
求めた２つの経路７１及び７２は、図６に示す本発明の経路制御方法の複数経路設定処理部１２０によって、送信元となるフレーム送受信装置３およびフレーム中継装置５及び６の転送テーブル３６及び５６に設定する。
【００９４】
さらに、以下に、各リンクに選択回数カウンタを設け、選択回数カウンタが閾値以下のリンクのみを用いて全てのフレーム送受信装置およびフレーム中継装置の接続構成を再構成して計算を行い、選択したリンクのカウンタを増加させるような拡張したダイクストラ（Ｄｉｊｓｔｏｒａ）アルゴリズムを利用した経路の計算方法のアルゴリズム表記を示す。
【００９５】
【数２】
0003759416.tif 000019
【００９６】
次に、上記アルゴリズムに基づく計算例を図面により説明する。
以下、図１のネットワークにおけるフレーム送受信装置３からフレーム送受信装置４への２つの経路を計算する例を示す。なお、本計算例では、送信先のフレーム送受信装置４を経路計算の出発点とするが、送信元のフレーム送受信装置３を経路計算の出発点とすることもできる。表１７に各リンクのコストを示す。
【００９７】
【表１７】
0003759416.tif 000020
【００９８】
アルゴリズムの計算開始時においては、表１８に示すように、経路計算の出発点となる装置４のｄ（４）は０に初期化され、各リンクのカウンタは０に初期化される。
【００９９】
【表１８】
0003759416.tif 000021
【０１００】
続いて、１つ目の経路の計算を行う。各パラメータは初期化され表１９の値をとる。すなわち、集合Ｕは送信先フレーム送受信装置４を除いた全装置を含み、フレーム送受信装置４から経路上のリンクコストの合計値ｄ（３）、ｄ（５）、ｄ（６）はそれぞれ無限大に初期化される。
【０１０１】
【表１９】
0003759416.tif 000022
【０１０２】
ｗｈｉｌｅループの実行の前に、計算回数ｋによってネットワーク構成が再構成された後、パラメータが設定され表２０の値をとる。すなわち、Ｄに含まれる各リンクｅについてｅｃ（ｅ）は０、ｋは−１であるため、「ｉｆ  ｅｃ（ｅ）＞  ｋ  ｔｈｅｎ」は実行されず、１回目の計算ではネットワーク構成は変更されない。
【０１０３】
【表２０】
0003759416.tif 000023
【０１０４】
フレーム中継装置５については、ｄ（５）には送信先フレーム送受信装置４との間のリンクコストである４が設定され、ｆ（５）には接続先である送信フレーム送受信装置４の装置番号の４が設定される。
また、フレーム中継装置６については、
ｄ（６）には送信先フレーム送受信装置４との間のリンクコストである５が設定され、ｆ（６）には接続先である送信フレーム送受信装置４の装置番号の４が設定される。
【０１０５】
ｗｈｉｌｅループの第１回目の実行では、集合Ｕに含まれる装置３、５及び６のうちｄ（Ｖ）が最小の装置５が選択され、経路の一部となり、集合Ｕから除かれる。集合Ｕに含まれる装置３及び６のうち、装置５に隣接する装置３及び６についてアルゴリスム「ｉｆ........」を実行する。
装置３については、
ｄ（３）は∞であり、ｄ（５）は４であり、Ｗ（５，３）は２であるため、「ｉｆｄ（ｕ）＞ｄ（Ｖ）＋Ｗ（Ｖ，ｕ）ｔｈｅｎ」が実行され、ｄ（３）にｄ（５）＋Ｗ（５，３）の結果の６が設定され、ｆ（３）には５が設定される。
装置６については、
ｄ（６）は５、ｄ（５）は４、ｗ（５，６）は３であるため、「ｉｆｄ（ｕ）＞ｄ（Ｖ）＋Ｗ（Ｖ，ｕ）ｔｈｅｎ」は実行されない。パラメータは、表２１の値をとなる。
【０１０６】
【表２１】
0003759416.tif 000024
【０１０７】
ｗｈｉｌｅループの第２回目の実行では、集合Ｕに含まれる装置３、５及び６のうちｄ（Ｖ）が最小の装置６が選択され、経路の一部となり、集合Ｕから除かれる。Ｕに含まれる装置で装置６に隣接する装置３についてアルゴリスム「ｉｆ..........」を実行する。ｄ（３）は６、ｄ（５）は５、ｗ（６，３）は３であるため、「ｉｆｄ（ｕ）＞ｄ（Ｖ）＋Ｗ（Ｖ，ｕ）ｔｈｅｎ」は実行されない。パラメータは、表２２の値となる。
【０１０８】
【表２２】
0003759416.tif 000025
【０１０９】
ｗｈｉｌｅループの第３回目の実行では、集合Ｕに含まれる装置３が選択され、経路の一部となり、集合Ｕから除かれ、集合Ｕはφとなる。Ｕに含まれる装置はないため、アルゴリスム「ｉｆ......」は実行されない。パラメータは、表２３の値となる。以上でｗｈｉｌｅループは終了する。
【０１１０】
【表２３】
0003759416.tif 000026
【０１１１】
次に、集合Ｖに含まれるフレーム送受信装置装置３、４については、
装置３については、
「ｗｈｉｌｅ  ｕ≠ｖ１  ｄｏ」が実行され、第１回目のｗｈｉｌｅループで、に（５，３）すなわちリンク１０が加わり、第２回目のｗｈｉｌｅループで、Ｔに（４，５）すなわちリンク１３が加わり、ｗｈｉｌｅループ処理が終了する。装置４について、
「ｗｈｉｌｅ  ｕ≠ｖ１  ｄｏ」が実行されない。ここで、表２４に示す通り、Ｔに含まれるリンク、１０、１３が求めた経路となる。
【０１１２】
【表２４】
0003759416.tif 000027
【０１１３】
リンク１０及びリンク１３について、表２５に示す通り、ｅｃ（１０）、ｅｃ（１３）が１に設定される。
【０１１４】
【表２５】
0003759416.tif 000028
【０１１５】
続いて、２つ目の経路の計算を行う。各パラメータは初期化された表２６の値をとる。すなわち、集合Ｕは送信先フレーム送受信装置４を除いた全装置、フレーム送受信装置４からの経路上のリンクコストの合計値ｄ（３）、ｄ（５）、ｄ（６）はそれぞれ無限大に初期化される。
【０１１６】
【表２６】
0003759416.tif 000029
【０１１７】
ｗｈｉｌｅループの実行の前に、計算回数ｋによってネットワーク構成が再構成された後、パラメータが設定され、表２７の値をとる。すなわち、ｋは０であるため、Ｄに含まれるリンク１０及び１３について、「ｉｆ  ｅｃ（ｅ）＞ｋｔｈｅｎ」が実行され、Ｄから除かれる。続いて、どのリンクとも接続していない装置５が集合Ｕから除かれる。
また、フレーム中継装置６については、
ｄ（６）には送信先フレーム送受信装置４との間のリンクコストである５が、ｆ（６）には接続先である送信先フレーム送受信装置４の装置番号の４がそれぞれ設定される。
【０１１８】
【表２７】
0003759416.tif 000030
【０１１９】
ｗｈｉ１ｅループの第１回目の実行では、
集合Ｕに含まれる装置３及び６のうちｄ（ｖ）が最小の装置６が選択され、経路の一部となり、集合Ｕから除かれる。Ｕに含まれる装置で、装置６に隣接する装置３についてはアルゴリスム「ｉｆ......」を実行する。ｄ（３）は∞、ｄ（６）は５、Ｗ（６，３）は３であるため、「ｉｆ  ｄ（ｕ＞ｄ（ｖ）＋ｗ（ｖ，ｕ）ｔｈｅｎ」が実行され、ｄ（３）にｄ（５）＋ｗ（６，３）の結果の８が設定され、ｆ（３）に６が設定される。パラメータは、表２８の値となる。
【０１２０】
【表２８】
0003759416.tif 000031
【０１２１】
ｗｈｉｌｅループの第３回目の実行では、集合Ｕに含まれるただ一つの装置３が選択され、経路の一部となり、集合Ｕから除かれ、集合Ｕはφとなる。Ｕに含まれる装置は存在しないため、アルゴリスム「ｉｆ........」は実行されない。パラメータは、表２９の値となる。以上でｗｈｌｌｅループが終了する。
【０１２２】
【表２９】
0003759416.tif 000032
【０１２３】
次に、集合Ｖに含まれるフレーム送受信装置、３、４について、
装置３については、
「ｗｈｉｌｅ  ｕ≠ｖｌ  ｄｏ」が実行され、第１回目のｗｈｉｌｅループで、Ｔに（６，３）すなわちリンク１１が加わり、第２回目のｗｈｉｌｅルーで、Ｔに（４，６）が加わり、ｗｈｉｌｅループ処理が終了する。
装置４については、
「ｗｈｉｌｅ  ｕ≠ｖ１  ｄｏ」が実行されない。ここで、表３０に示す通りＴに含まれるリンク、１１、１４が求めた経路である。
【０１２４】
【表３０】
0003759416.tif 000033
【０１２５】
リンク１１、リンク１４について、ｅｃ（１１）、ｅｃ（１４）に１が加算され、表３１に示す通りそれぞれ１に設定される。
【０１２６】
【表３１】
0003759416.tif 000034
【０１２７】
以上で、フレーム送受信装置３からフレーム装置４への２つの経路、
装置３→リンク１０→装置５→リンク１３→装置４と
装置３→リンク１１→装置６→リンク１４→装置４とが求まった。これら２つの経路は図７の通りとなる。
【０１２８】
求めた２つの経路は、本発明の経路制御方法の複数経路設定処理部１２０によっ送信元となるフレーム送受信装置３およびフレーム中継装置５、６の転送テーブルルにそれぞれ設定される。
【０１２９】
さらに、以下に、各リンクに選択回数カウンタを設け、各リンクのコストと選択回数カウンタ値を基に一つパラメータを算出し、経路上の各リンクのパラメータの合計が最小となるようリンクを選択し、選択したリンクのカウンタを増加させるよう拡張したダイクストラ（Ｄｉｊｋｓｔｏｒａ）アルゴリズムを利用した経路の計算方法のアルゴリズム表記を示す。
【数３】
0003759416.tif 000035
【０１３０】
次に、上記アルゴリズムに基づく１計算例を図面により説明する。以下、図１のネットワークにおけるフレーム送受信装置３からフレーム送受信装置４への２つの経路を計算する例を示す。なお、本計算例では、送信先フレーム送受信装置４を経路計算の経路計算の出発点とするが、送信元フレーム送受信装置３を経路計算の出発点とするもできる。
【０１３１】
ここでは、ｇ（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ））をｗ（ｖ，ｕ）＋２×ｅｃ（ｅ）として説明する。表３２に各リンクのコストを示す。
【０１３２】
【表３２】
0003759416.tif 000036
【０１３３】
アルゴリズムの計算開始時においては、経路計算の出発点となる装置４のｄｇ（４）は０に初期化され、各リンクのカウンタ値は、表３３の値の通り、０に初期化される。
【０１３４】
【表３３】
0003759416.tif 000037
【０１３５】
【表３４】
0003759416.tif 000038
【０１３６】
続いて、１つ目の経路の計算を行う。各パラメータは初期化され表３４の値をとる。すなわち、集合Ｕは送信先フレーム送受信装置４を除いた全装置を含み、フレーム送受信装置４からの経路に含まれるｇ（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ））によって計算される各リンクのパラメータの合計値ｄｇ（３）、ｄｇ（５）、ｄｇ（６）はそれぞれ無限大に初期化される。ｗｈｉｌｅループの実行の前に、送信先フレーム送受信装置４に隣接する装置のパラメータが設定され、表３５の値をとる。
【０１３７】
【表３５】
0003759416.tif 000039
【０１３８】
すなわち、フレーム中継装置５については、ｄｇ（５）には送信先フレーム送受信装置４との間のリンクコスト（４）とリンクカウンタ（０）により４が設定され、ｆ（５）には接続先である送信先フレーム送受信装置４の装置番号の４が設定される。
また、フレーム中継装置６については、
ｄｇ（６）には送信先フレーム送受信装置４との間のリンクコスト（５）とリンクカウンタ（０）により５が設定され、ｆ（６）には接続先である送信先フレーム送受信装置４の装置番号の４が設定される。
【０１３９】
ｗｈｉｌｅループの第１回目の実行では、集合Ｕに含まれる装置３、５及び６のうちｄ（Ｖ）が最小の装置５が選択され、経路の一部となり、集合Ｕから除かれる。Ｕに含まれる装置３及び６のうち、装置５に隣接する装置３及び装置６についてアルゴリスム「ｉｆ........」を実行する。
【０１４０】
装置３については、
ｄｇ（３）は∞、ｄ９く５）は４、ｇ（ｗ（５，３），ｅｃ（５，３）は２であるため、「ｉｆ  ｇ（ｕ）＞ｄｇ（ｖ）＋ｇ（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ）ｔｈｅｎ」が実行され、ｄ（３）にｄｇ（５）＋９（ｗ（５，３），ｅｃ（５，３））の結果の６が設定され、ｆ（３）に５が設定される。
また、装置６については、
ｄ（６）は５、ｄ（５）は４、ｇ（ｗ（５，６），ｅｃ（５，６））は３であるため、「ｉｆ  ｄｇ（ｕ）＞ｄｇ（ｖ）＋９（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ）ｔｈｅｎ」は実行されない。パラメータは、表３６の値となる。
【０１４１】
【表３６】
0003759416.tif 000040
【０１４２】
ｗｈｉｌｅループの第２回目の実行では、集合Ｕに含まれる装置３及び６のうちｄ（Ｖ）が最小の装置６が選択され、経路の一部となり、集合Ｕから除かれる。Ｕに含まれる装置で、装置６に隣接する装置３についてアルゴリスム「ｉｆ......」を実行する。ｄｇ（３）は６、ｄｇ（６）は５、ｇ（ｗ（６，３））は３であるため、「ｉｆ  ｄｇ（ｕ）＞ｄｇ（ｖ）＋ｇ（ｗ（ｖ，ｕ）．ｅｃ（ｖ，ｕ））ｔｈｅｎ」は実行されない。パラメータは、表３７の値をとる。
【０１４３】
【表３７】
0003759416.tif 000041
【０１４４】
ｗｈｉｌｅループの第３回目の実行では、集合Ｕに含まれるただ一つの装置３が選択され、経路の一部となり、集合Ｕから除かれ、集合Ｕはφとなる。Ｕに含まれる装置はないため、アルゴリスム「ｉｆ..........」は実行されない。パラメータは、表３８の値をとる。以上でｗｈｉｌｅループが終了する。
【０１４５】
【表３８】
0003759416.tif 000042
【０１４６】
次に、集合Ｖに含まれるフレーム送受信装置３、４について、
装置３については、
「ｗｈｉｌｅ  ｕ≠ｖ１  ｄｏ」が実行され、第１回目のｗｈｉｌｅループで、Ｔに（５，３）すなわちリンク１０が加わり、第２回目のｗｈｉｌｅループで、Ｔに（４，５）すなわちリンク１３が加わり、ｗｈｉｌｅループ処理が終了する。
装置４については、
「ｗｈｉｌｅ  ｕ≠ｖ１  ｄｏ」が実行されない。ここで、表３９に示す通り、Ｔに含まれるリンク１０、１３が求めた経路である。
【０１４７】
【表３９】
0003759416.tif 000043
【０１４８】
リンク１０及びリンク１３について表４０に示す通りｅｃ（１０）、ｅｃ（１３）が１に設定される。
【０１４９】
【表４０】
0003759416.tif 000044
【０１５０】
続いて、２つ目の経路の計算を行う。各パラメータは初期化され表４１の値をとる。すなわち、集合Ｕは送信先フレーム送受信装置４を除いた全装置に、フレーム受信装置からの経路に含まれる前記ｇ（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ））によって計算される各リンクのパラメータのの合計値ｄｇ（３）、ｄｇ（５）、ｄｇ（６）はそれぞれ無限大に初期化される。
【０１５１】
【表４１】
0003759416.tif 000045
【０１５２】
ｗｈｉｌｅループの実行の前に、送信先フレーム送受信装置４に隣接する装置のパラメータが設定され、表４２の値をとる。
【０１５３】
【表４２】
0003759416.tif 000046
【０１５４】
すなわち、フレーム中継装置５については、ｄｇ（５）には送信先フレーム送受信装置４との間のリンクコスト（４）とリンクカウンタ（１）により６が設定され、ｆ（５）には接続先である送信先フレーム送受信装置４の装置番号の４が設定される。また、フレーム中継装置６については、ｄｇ（６）には送信先フレーム送受信装置４との間のリンクコスト（５）とリンクカウンタ（０）により、５が設定され、ｆ（６）には接続先である送信先フレーム送受信装置４の装置番号の４が設定される。
【０１５５】
ｗｈｉｌｅループの第１回目の実行において、集合Ｕに含まれる装置３、５及び６のうちｄ（Ｖ）が最小の装置６が選択され、経路の一部となり、集合Ｕから除かれる。Ｕに含まれる装置３、５のうち装置６に隣接する装置３及び５についてアルゴリスム「ｉｆ......」を実行する。
装置３については
ｄｇ（３）は∞、ｄｇ（６）は５、ｇ（ｗ（６，３），ｅｃ（６，３））は３であるため、「ｉｆ  ｄｇ（ｕ）＞ｄｇ（Ｖ）＋ｇ（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ）ｔｈｅｎ」が実行され、ｄ（３）にｄｇ（６）＋ｇ（ｗ（６，３），ｅｃ（６，３））の結果の８が設定され、ｆ（３）に６が設定される。
また、装置５については、
ｄ（５）は６、ｄ（６）は４、ｇ（ｗ（６，５），ｅｃ（６，５））は３であるため、「ｉｆ  ｄｇ（ｕ）＞ｄｇ（Ｖ）＋ｇ（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ）ｔｈｅｎ」は実行されない。パラメータは、表４３の値をとる。
【０１５６】
【表４３】
0003759416.tif 000047
【０１５７】
ｗｈｉｌｅループの第２回目の実行では、集合Ｕに含まれる装置３及び５のうちｄ（Ｖ）が最小の装置５が選択され、経路の一部となり、集合Ｕから除かれる。Ｕに含まれる装置で装置５に隣接する装置３についてアルゴリスム「ｉｆ......」を実行する。ｄｇ（３）は８であり、ｄｇ（５）は６であり、ｇ（ｗ（５，３），ｅｃ（５，３））は４であるため、アルゴリスム「ｉｆ  ｄｇ（ｕ）＞ｄｇ（ｖ）＋ｇ（ｗ（ｖ，ｕ），ｅｃ（ｖ，ｕ））ｔｈｅｎ」は実行されない。パラメータは、表４４の値をとる。
【０１５８】
【表４４】
0003759416.tif 000048
【０１５９】
【表４５】
0003759416.tif 000049
【０１６０】
ｗｈｉｌｅループの第３回目の実行では、集合Ｕに含まれるただ一つの装置３が選択され、経路の一部となり、集合Ｕから除かれ、集合Ｕはφとなる。Ｕに含まれる装置はないため、アルゴリスム「ｉｆ........」は実行されない。パラメータは、表４５の値をとる。以上でｗｈｉｌｅループが終了する。
【０１６１】
次に、集合Ｖに含まれるフレーム送受信装置３、４について、
装置３については、
「ｗｈｉｌｅ  ｕ≠ｖ１  ｄｏ」が実行され、第１回目のｗｈｉｌｅループで、Ｔに（６，３）すなわちリンク１１が加わり、第２回目のｗｈｌｌｅループで、Ｔに（４，６）すなわちリンク１４が加わり、ｗｈｉｌｅループ処理が終了する。
装置４については、
「ｗｈｉｌｅ  ｕ≠ｖ１  ｄｏ」が実行されない。
ここで、表４６に示す通り、Ｔに含まれるリンク１１、１４が求めた経路である。
【０１６２】
【表４６】
0003759416.tif 000050
【０１６３】
リンク１１及び１４について、ｅｃ（１１）及びｅｃ（１４）に１が加算され、表４７に示す通りそれぞれ１、１に設定される。
【０１６４】
【表４７】
0003759416.tif 000051
【０１６５】
以上でフレーム送受信装置３からフレーム送受信装置４への２つの経路、
装置３→リンク１０→装置５→リンク１３→装置４と
装置３→リンク１１→装置６→リンク１４→装置４と
が求まった。２つの経路は図７の通りとなる。
【０１６６】
以下において、図７の２つの経路を用いて本発明の経路選択方法と帯域予約方法の実施の形態を説明する。経路７１は、装置３→リンク１０→装置５→リンク１３→装置４を示し、経路７２は、装置３→リンク１１→装置６→リンク１４→装置４を示している。本例では、リンク毎に予約可能帯域と予約済み帯域とを管理し、経路上の全てのリンクについて予約を行う帯域と予約済み帯域の合計が予約可能帯域以下の場合、該経路を選択して帯域予約可能であるとする。一方、経路上のリンクのうち一つでも予約を行う帯域と予約済み帯域の合計が予約可能帯域を超える場合は、該経路を選択した帯域予約をできないものとする。各リンクの予約可能帯域を表４８に示す。また、各リンクの予約済み帯域を表４９に示す。
【０１６７】
【表４８】
0003759416.tif 000052
【０１６８】
【表４９】
0003759416.tif 000053
【０１６９】
次に、表５０に示す予約８１〜予約８３を順次行う。ここで、本発明の経路選択方法のうち、帯域予約が可能な経路が複数ある場合には、送信元のフレーム送受信装置から送信先フレーム送受信装置までの各リンクのコストの合計が最小となる一つの経路を選択する方法を用いた実施の形態説明する。
【０１７０】
【表５０】
0003759416.tif 000054
【０１７１】
図８は経路選択方法のアルゴリスムを示している。予約８１で、５の帯域を予約する場合について説明する。まず、経路のうちの１つ、経路７１を選択する。経路上の全てリンクについて予約可能である。すなわち、
リンク１０：予約帯域（５）＋予約済み帯域（２０）＜予約可能帯城（６０）
リンク１３：予約帯域（５）＋予約済み帯域（２０）＜予約可能帯城（３０）
従って、経路７１を予約可能経路とする。
【０１７２】
次に、経路のうちの１つ、経路７２を選択する。経路上の全てリンクについて予約可能である。すなわち、
リンク１１：予約帯域（５）＋予約済み帯域（０）＜予約可能帯城（４０）
リンク１４：予約帯域（５）＋予約済み帯域（０）＜予約可能帯城（２０）
従って、経路７２を予約可能経路とする。
【０１７３】
次に、経路７１上の各リンクのコストの合計は６である。経路７２上の各リンクのコストの合計は８である。経路７１、経路７２ともに帯域予約が可能である。従って、リンクコストの合計が最小の経路７１を選択する。
【０１７４】
選択された経路７１は、本発明の経路制御方法の経路選択設定処理部１５０（図６）により、送信元フレーム送受信装置における帯域保証トラヒック９１と経路７１のマッピング情報として設定される。
【０１７５】
図９は帯域予約管理方法のアルゴリスムを示す。経路が選択された場合、帯域予約を受け付けて予約帯域を経路上の各リンクの予約済帯域に加算する。経路が選択されない場合、帯域予約を拒絶する。ここでは、前記経路７１が選択されたため、帯域予約を受け付けて経路７１上のリンク１０及び１３の予約済帯域に５の予約帯域を加算し、予約済帯域は表５１の通りとなる。
【０１７６】
【表５１】
0003759416.tif 000055
【０１７７】
続いて、予約８２で、２０の帯域を予約する場合について説明する。まず、経路のうちの１つ、経路７１を選択する。経路上の全リンクについて、予約可能である。すわわち、
リンク１０：予約帯域（２０）＜予約済み帯域（２５）＜予約可能帯域（６０）
リンク１３：予約帯域（２０）＜予約済み帯域（２５）＜予約可能帯域（３０）
である。したがって、経路７１を予約不可能とする。
【０１７８】
次に、経路７２を選択する。経路上の全リンクについて、予約可能である。すわわち、
リンク１１：予約帯域（２０）＜予約済み帯域（０）＜予約可能帯域（４０）
リンク１４：予約帯域（２０）＜予約済み帯域（０）＝予約可能帯域（２０）
である。したがって、経路７２を予約可能経路とし、選択する。
【０１７９】
選択された経路７２は、本発明の経路制御方法の経路選択設定処理１５０により、送信元フレーム送受信装置における、帯域保証トラヒック９２と経路７２のマッピング情報として設定される。
【０１８０】
帯域予約管理方法により、経路７２が選択されたため、帯域予約を受け付けて経路７２上のリンク１１及び１４の予約済帯域に２０の予約帯域を加算し、予約済帯域は表５２の通りとなる。
【０１８１】
【表５２】
0003759416.tif 000056
【０１８２】
続いて、予約８３で１０の帯域を予約する場合について説明する。まず、経路のうちの１つ、経路７１を選択する。経路上の全リンクについて、予約可能である。すわわち、
リンク１０：予約帯域（１０）＜予約済み帯域（２５）＜予約可能帯域（６０）
リンク１３：予約帯域（１０）＜予約済み帯域（２５）＜予約可能帯域（３０）
である。したがって、経路７１を予約不可能とする。
【０１８３】
次に、経路のうちの１つ、経路７２を選択する。経路上の全リンクについて、予約可能である。すわわち、
リンク１１：予約帯域（１０）＜予約済み帯域（２０）＜予約可能帯域（４０）
リンク１４：予約帯域（１０）＜予約済み帯域（２０）＜予約可能帯域（２０）
である。したがって、経路７２を予約不可能とする。
【０１８４】
経路７１、経路７２ともに帯域予約不可能である。したがって、経路を選択しない。帯域予約管理方法により、ここでは経路が選択されないため、帯域予約８３を拒絶する。
【０１８５】
以上により、帯域保証トラヒックと経路は表５３の通りにマッピングされる。
【０１８６】
【表５３】
0003759416.tif 000057
【０１８７】
次に、帯域予約が可能な経路が複数粗存在する場合、帯域保証トラフックが予約する帯域と他の帯域保証トラフックにより予約済みの帯域との合計がネットワーク内でより均等となるように１つの経路を選択する方法を用いた実施の形態を説明する。図１０は経路選択方法のアルゴリスムを示す。予約８１において５の帯域を予約する場合について説明する。上述した経路選択方法と同様に、経路７１及び７２と共に帯域予約が可能である。ここで、経路７１上のリンクの予約可能帯域から帯域予約済み帯域を減算した帯域は、
リンク１０：４０
リンク１３：１０
従って、予約可能帯域−帯域予約済み帯域が最小のリンクはリンク１３であり、その値は１０である。
【０１８８】
一方、経路７２上のリンクの予約可能帯域−帯域予約済み帯域は、
リンク１１：４０
リンク１４：２０
従って、予約可能帯域−帯域予約済帯域が最小のリンクはリンク１４であり、その値は２０である。従って、経路上で予約可能帯域−帯域予約済み帯域が最小のリンクであって、予約可能帯域−帯域予約済み帯域が最大となる経路７２を選択する。そして、選択された経路７２は、本発明の経路制御方法の経路選択設定処理部１５０により、送信元フレーム送受信それぞれにおける帯域保証トラフック９１と経路７２のマップング情報として設定される。
【０１８９】
本例では、帯域予約管理方法により経路７２が選択されたため、帯域予約を受け付けて経路７２上のリンク１１及び１４の予約済み帯域に５の予約帯域を加算し、予約済み帯域は表５４の通りとなる。
【０１９０】
【表５４】
0003759416.tif 000058
【０１９１】
続いて、予約８２において２０の帯域を予約する場合について説明する。この場合、経路７１及び７２共に帯域予約不可能である。従って、これらの経路は選択しない。ここでは、帯域予約管理方法により経路が選択されないため、帯域予約を拒絶する。以上により、帯域保証トラフックと経路は表５５の通りにマップングされる。
【０１９２】
【表５５】
0003759416.tif 000059
【０１９３】
次に、以下では、任意のフレーム中継装置または任意のリンクが故障した場合、該フレーム中継装置またはリンクを経由する経路について、前記フレーム中継装置に設定されている複数の経路の中から前記故障したフレーム中継装置またはリンクを経由せず、かつ前記任意の送信先フレーム送受信装置へ向かう経路を選択する経路選択方法の実施の形態について図を用いて説明する。図１１は経路選択方法の実施の形態を説明するブロック図である。経路が図１２に示す通りにフレーム中継装置に設定されており、トラヒックと経路は表５６の通りにマッピングされている場合において、フレーム中継装置６が故障した場合、フレーム中継装置６を経由する経路を検索する。経路７２について、Ｒｏｕｔｅ  ＩＤは２であるため、Ｒｏｕｔｅ  ＩＤが１である経路７１を選出する。経路７１は装置６を経由しないため、経路７１を選択する。使用されている経路７１、７３、７４のうちに装置６を経由する経路７４が存在するため、経路７４について、Ｒｏｕｔｅ  ＩＤは２であるが、Ｒｏｕｔｅ  ＩＤが１である経路７３を選出する。経路７３は装置６を経由しないため、経路７３を選択する。使用されている経路７１、７３の中に装置６を経由する経路が存在しないため、経路７１、７３に対するトラヒック９５、トラヒック９７のマッピングを設定する設定経路設定処理を行う。トラヒックと経路のマッピングは表５７の通りとなる。これにより、フレーム中継経路が経路７２から経路７１に、経路７４から経路７３に切り替わる。
【０１９４】
【表５６】
0003759416.tif 000060
【０１９５】
【表５７】
0003759416.tif 000061
【０１９６】
【発明の効果】
本発明によれば、トレヒック分散および故障迂回のための経路変更において、フレーム中継経路に対する設定変更を抑制し、経路再計算における計算量を抑制することが可能となる。
また、本発明によれば、複数経路を用いてトラヒック分散するための経路計算において、コネクションレス型転送の経路を計算し、経路を分散させるための独立性を考慮した複数の経路を計算することが可能となる。
さらに、本発明によれば、フロー毎の経路を確定させてパケットの到着順序が逆転を防止するとともに帯域予約を可能にし、帯域保証トラヒックの量に基づくことが可能となる。
【図面の簡単な説明】
【図１】  本発明による経路制御方法を実施するための一例としてのネットワークを示す線図である。
【図２】  パケット送受信装置が送信するパケットの一例を示す線図である。
【図３】  フレーム中継ネットワークにおいて転送されるコアフレームの一例を示す線図である。
【図４】  フレーム送受信装置の一例の構成を示す線図である。
【図５】  フレーム中継装置の一例の構成を示す線図である。
【図６】  本発明による経路制御方法を実施するための経路制御処理装置の一例の構成を示すブロック図である。
【図７】  設定された経路を示す線図である。
【図８】  本発明による経路選択方法のアルゴリスムを示す線図である。
【図９】  本発明による帯域予約管理方法のアルゴリスムを示す線図である。
【図１０】  本発明による経路選択方法を示す線図である。
【図１１】  一部のリンク又は装置が故障している場合の経路選択のアルゴリスムを示す線図である。
【図１２】  フレーム中継装置に設定されている経路を示す線図である。
【符号の説明】
１，２  パケット送受信装置
３，４  フレーム送受信装置
５，６  フレーム中継装置
５１  コアフレーム受信部
５６  転送テーブル
５７  出力リンク選択部
１００  経路制御処理部
１１０  複数経路計算処理部
１２０  複数経路設定処理部
１３０  経路選択計算処理部
１５０  選択経路設定処理部
【図１】
0003759416.tif 000062
【図２】
0003759416.tif 000063
【図３】
0003759416.tif 000064
【図４】
0003759416.tif 000065
【図５】
0003759416.tif 000066
【図６】
0003759416.tif 000067
【図７】
0003759416.tif 000068
【図８】
0003759416.tif 000069
【図９】
0003759416.tif 000070
【図１０】
0003759416.tif 000071
【図１１】
0003759416.tif 000072
【図１２】
0003759416.tif 000073