(57)【要約】【課題】  通信システムにおいて、リンクコストを経路設定のパラメータとして用いつつ、負荷が集中しない経路設定方式を提供すること。【解決手段】  通信ノードにおける経路処理部において、パス経路設定に際して、リンクコストを初期値とし、当該リンクを通過するかあるいは通過することが見込まれるパス数に対して単調増加となる値（動的リンクコスト）をパラメータとする評価関数を用い、この評価関数が最小となるように、パスの経路設定を行う。これにより、パスの数あるいは所要帯域に依存して経路のコストを設定することができるので、特定の経路へのトラヒックの集中を防ぎ、ネットワーク全体の使用効率を高めることができる。【選択図】      図５
2007142609.tif 000002
【特許請求の範囲】
【請求項１】
複数の通信ノードが互いにリンクにより接続されてなる通信システムにおけるパス経路設定システムであって、
パス経路設定に際して、ノード間リンクを通過するあるいは通過することが見込まれるパス数またはパスの所要帯域とリンクコストとからなるパラメータを有する評価関数を用いて、経路設定をなす手段を含むことを特徴とするパス経路設定システム。
【請求項２】
前記評価関数は、前記パス数または前記パスの所要帯域に対し単調増加するコスト値（動的リンクコスト）をパラメータとするものであることを特徴とする請求項１記載のパス経路設定システム。
【請求項３】
前記評価関数は、前記所要帯域により重み付けられた実効パス数に対し単調増加するコスト値（動的リンクコスト）をパラメータとするものであることを特徴とする請求項１記載のパス経路設定システム。
【請求項４】
前記動的リンクコストは、ノード間リンクコストを初期値とすることを特徴とする請求項１〜３いずれか記載のパス経路設定システム。
【請求項５】
前記手段は、前記評価関数において、パス毎に前記動的リンクコストの累積値を最小化するようにしたことを特徴とする請求項１〜４いずれか記載のパス経路設定システム。
【請求項６】
前記パスの一端点となるノードは、前記パスを特定するパスＩＤと前記パスに関わる動的リンクコストの初期値とを含む経路探索情報を、パスの通過対象となる全ての隣接ノードに通知する手段を有することを特徴とする請求項１〜５いずれか記載のパス経路設定システム。
【請求項７】
前記パスの他端点となるノードは、到着した経路探索情報のうち、前記評価関数に基づいて、評価値が最小となる経路を選択し、かかる経路に対し経路確定情報を送出する手段を有することを特徴とする請求項１〜６いずれか記載のパス経路設定システム。
【請求項８】
各ノードは、前記評価関数に基づいて最小化評価する経路処理手段と、リンク対応に通過するあるいは通過が見込まれるパスの累積動的リンクコストを記録する経路テーブルとを有し、
前記経路処理手段は、受信された経路探索情報内のパスＩＤに基づいて受信リンクにおける動的リンクコストを算出し、この算出値を経路探索情報内の累積動的リンクコストに加算し、前記経路テーブル内の値と比較して新たに算出された累積動的リンクコストが小さい場合、その値を前記経路テーブルに登録・更新することを特徴とする請求項１〜７いずれか記載のパス経路設定システム。
【請求項９】
各ノードは、前記評価関数に基づいて最小化評価する経路処理手段と、リンク対応に通過するあるいは通過が見込まれるパスの累積動的リンクコストを記録する経路テーブルとを有し、
前記経路処理手段は、受信された経路探索情報内のパスＩＤ及び累積動的リンクコストを前記経路テーブル内の値と比較し、新たに算出された累積動的リンクコストが小さい場合、その値を前記経路テーブルに登録・更新すると共に、送出リンク対応に送出リンクにおける動的リンクコストを算出し、この算出値を累積動的リンクコストに加算し、加算された累積動的リンクコストを含む経路探索情報を、該送出リンクに送出することを特徴とする請求項１〜７いずれか記載のパス経路設定システム。
【請求項１０】
前記経路処理手段は、あるパスに対する累積動的リンクコストの登録・更新に際し、他のパスの累積動的リンクコストが変化する場合、該パスに対し変化した値を累積動的リンクコストとして前記経路テーブルに登録・更新することを特徴とする請求項９記載のパス経路設定システム。
【請求項１１】
各ノードは、前記経路テーブルに累積動的リンクコストが登録・更新された場合、経路探索情報が受信されたリンクを除くパスの通過対象となる全てのリンクに対し、登録・更新された累積動的リンクコスト及びパスＩＤを含む経路探索情報を送出することを特徴とする請求項９または１０記載のパス経路設定システム。
【請求項１２】
前記経路テーブルの初期値を他の経路アルゴリズムにより得られた経路情報に基づき設定することを特徴とする請求項９〜１１いずれか記載のパス経路設定システム。
【請求項１３】
設定の対象となるパスを複数のグループに分けて、グループ毎に経路設定を行うことを特徴とする請求項１〜１２いずれか記載のパス経路設定システム。
【請求項１４】
前記グループの各々における経路設定において、各リンクの見込まれるパスにより決定される動的リンクコストを固定することを特徴とする請求項１３記載のパス経路設定システム。
【請求項１５】
各リンクにおける見込まれるパスは、該リンクに既に設定されているパスと、新たに設定されようとするパスの集合体であることを特徴とする請求項１４記載のパス経路設定システム。
【請求項１６】
各リンクに見込まれるパス数は、該リンクに既に設定されているパスと、新たに設定されようとするパスの集合体のパス数であることを特徴とする請求項１４または１５記載のパス経路設定システム。
【請求項１７】
複数の通信ノードが互いにリンクにより接続されてなる通信システムにおけるパス経路設定方法であって、
パス経路設定に際して、ノード間リンクを通過するあるいは通過することが見込まれるパス数またはパスの所要帯域とリンクコストとからなるパラメータを有する評価関数を用いて、経路設定をなすステップを含むことを特徴とするパス経路設定方法。
【請求項１８】
前記評価関数は、前記パス数または前記パスの所要帯域に対し単調増加するコスト値（動的リンクコスト）をパラメータとするものであることを特徴とする請求項１７記載のパス経路設定方法。
【請求項１９】
前記評価関数は、前記所要帯域により重み付けられた実効パス数に対し単調増加するコスト値（動的リンクコスト）をパラメータとするものであることを特徴とする請求項１７記載のパス経路設定方法。
【請求項２０】
前記動的リンクコストは、ノード間リンクコストを初期値とすることを特徴とする請求項１７〜１９いずれか記載のパス経路設定方法。
【請求項２１】
前記ステップは、前記評価関数において、パス毎に前記動的リンクコストの累積値を最小化するようにしたことを特徴とする請求項７１〜２０いずれか記載のパス経路設定方法。
【請求項２２】
前記パスの一端点となるノードにおいて、前記パスを特定するパスＩＤと前記パスに関わる動的リンクコストの初期値とを含む経路探索情報を、パスの通過対象となる全ての隣接ノードに通知するステップを有することを特徴とする請求項１７〜２１いずれか記載のパス経路設定方法。
【請求項２３】
前記パスの他端点となるノードにおいて、到着した経路探索情報のうち、前記評価関数に基づいて、評価値が最小となる経路を選択し、かかる経路に対し経路確定情報を送出するステップを有することを特徴とする請求項７１〜２２いずれか記載のパス経路設定方法。
【請求項２４】
各ノードにおいて、前記評価関数に基づいて最小化評価する経路処理手段と、リンク対応に通過するあるいは通過が見込まれるパスの累積動的リンクコストを記録する経路テーブルとを設け、
前記経路処理手段は、受信された経路探索情報内のパスＩＤに基づいて受信リンクにおける動的リンクコストを算出するステップと、この算出値を経路探索情報内の累積動的リンクコストに加算するステップと、前記経路テーブル内の値と比較して新たに算出された累積動的リンクコストが小さい場合、その値を前記経路テーブルに登録・更新するステップとを有することを特徴とする請求項１７〜２３いずれか記載のパス経路設定方法。
【請求項２５】
各ノードにおいて、前記評価関数に基づいて最小化評価する経路処理手段と、リンク対応に通過するあるいは通過が見込まれるパスの累積動的リンクコストを記録する経路テーブルとを設け、
前記経路処理手段は、受信された経路探索情報内のパスＩＤ及び累積動的リンクコストを前記経路テーブル内の値と比較するステップと、新たに算出された累積動的リンクコストが小さい場合、その値を前記経路テーブルに登録・更新するステップと、送出リンク対応に送出リンクにおける動的リンクコストを算出するステップと、この算出値を累積動的リンクコストに加算するステップと、加算された累積動的リンクコストを含む経路探索情報を、該送出リンクに送出するステップとを有することを特徴とする請求項１７〜２３いずれか記載のパス経路設定方法。
【請求項２６】
前記経路処理手段は、あるパスに対する累積動的リンクコストの登録・更新に際し、他のパスの累積動的リンクコストが変化する場合、該パスに対し変化した値を累積動的リンクコストとして前記経路テーブルに登録・更新することを特徴とする請求項２５記載のパス経路設定方法。
【請求項２７】
各ノードにおいて、前記経路テーブルに累積動的リンクコストが登録・更新された場合、経路探索情報が受信されたリンクを除くパスの通過対象となる全てのリンクに対し、登録・更新された累積動的リンクコスト及びパスＩＤを含む経路探索情報を送出することを特徴とする請求項２５または２７記載のパス経路設定方法。
【請求項２８】
前記経路テーブルの初期値を他の経路アルゴリズムにより得られた経路情報に基づき設定することを特徴とする請求項２５〜２７いずれか記載のパス経路設定方法。
【請求項２９】
設定の対象となるパスを複数のグループに分けて、グループ毎に経路設定を行うことを特徴とする請求項１７〜２８いずれか記載のパス経路設定方法。
【請求項３０】
前記グループの各々における経路設定において、各リンクの見込まれるパスにより決定される動的リンクコストを固定することを特徴とする請求項２９記載のパス経路設定方法。
【請求項３１】
各リンクにおける見込まれるパスは、該リンクに既に設定されているパスと、新たに設定されようとするパスの集合体であることを特徴とする請求項３０記載のパス経路設定方法。
【請求項３２】
各リンクに見込まれるパス数は、該リンクに既に設定されているパスと、新たに設定されようとするパスの集合体のパス数であることを特徴とする請求項３０または３１記載のパス経路設定方法。
【請求項３３】
通信システムにおいて互いにリンクにより接続されてなる通信ノードであって、
パス経路設定に際して、ノード間リンクを通過するあるいは通過することが見込まれるパス数またはパスの所要帯域とリンクコストとからなるパラメータを有する評価関数を用いて、経路設定をなす手段を含むことを特徴とするノード。
【請求項３４】
通信システムにおいて互いにリンクにより接続されてなる通信ノードの経路設定動作をコンピュータにより実行させるためのプログラムであって、
パス経路設定に際して、ノード間リンクを通過するあるいは通過することが見込まれるパス数またはパスの所要帯域とリンクコストとからなるパラメータを有する評価関数を用いて、経路設定をなす処理を含むことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はパス経路設定システム及びその方法並びにそれに用いるノード及びプログラムに関し、特に複数の通信ノードがリンクにより互いに接続された通信システムにおいてパスの経路を設定するためのパス経路設定方式の改良に関するものである。
【背景技術】
【０００２】
通信フレーム上のラベル値で特定されるパスをベースとする経路制御を行うネットワークにつき説明する。図９のネットワークにおいて、ＶＬＡＮ（Virtual Local Area Network）タグを宛先ノードに対応付け、発ノードが異なっても、宛先が同じノードに至るパスに対して同じタグ値を与えるツリー形態のマージ型（中継ノードにおいて合体する形態）のパスを考える。例えば、宛先をノード４１とするパスは、発ノード１１，１２，１３いずれに対しても、同一のパス識別子であるパスＩＤ（＝Ｐ４１）で与えられる。
【０００３】
同様に、宛先をノード４２とする２つのマージ型のラベルパス（パスＩＤ＝Ｐ４２ａ，Ｐ４２ｂ）、宛先をノード４３とするマージ型のラベルパス（パスＩＤ＝Ｐ４３）を与える。ラベルパスは、宛先ノードをルート（Ｒｏｏｔ）ノードとするツリー形状の構成となる。
【０００４】
図９における各ノードの構成は、本発明によるノードの構成（図１）と同じであり、よって図１を参照して説明する。各ノードは、リンク６〜９により隣接ノードに接続されたスイッチ部３と、隣接ノードから供給される受信経路情報４を受信し、経路制御処理を行った後、受信されたリンクを除く全てのリンクに対し受信経路情報５を送出する経路処理部１と、経路情報を格納する経路テーブル２とを有する。本従来例に用いられる径路情報は、パスＩＤと累積リンクコストとからなる。
【０００５】
各パスにおいて、宛先ノードとなるルートノードが経路制御を起動する。上述のパスＩＤ＝Ｐ４１の場合、ルートノード４１は、「パスＩＤ＝Ｐ４１」と「初期化された累積リンクコスト＝０」とからなる経路情報を、全てのリンクに対して送出する。図９の構成では、経路情報はノード３１，４２に対し送出されることになる。ノード４２，４３も同様に、初期化された経路情報をノード４１，４３，３２及びノード４２，３３にそれぞれ送出する。
【０００６】
各ノードの経路処理部１における処理フローを、図１０を参照しつつ説明する。先ず、経路情報（受信経路情報４）を受信する（ステップＳ１）。そして、受信したリンク（リンク番号）に対応付けて経路情報を一時格納する（ステップＳ２）。この受信したリンクのリンクコストを読み出してこのリンクコストを受信経路情報４内の累積リンクコスト値に加算する（ステップＳ３）。そして、自ノードを含む新たな累積リンクコストを算出する（ステップＳ４）。
【０００７】
その後、受信経路情報４内のパスＩＤに関わる経路情報が経路テーブル２に登録済み否かをチェックする（ステップＳ５）。登録済みの場合には、累積リンクコストの登録値と、新規に算出された累積リンクコスト値とを比較する（ステップＳ６）。ステップＳ５のチェック結果が、経路テーブル２に未登録を示す場合、あるいはステップＳ６の比較結果が、新規累積リンクコスト値が登録済みの累積リンクコスト値より小さいことを示す場合、経路情報を経路テーブル２に新規に登録あるいは更新する（ステップＳ７）。
【０００８】
当該ノードがパスのエンドノード（この場合、パスの発ノード）かを判定し（ステップＳ８）、エンドノードでない場合には、登録・更新された経路情報を、送信経路情報５として、受信されたリンク以外のリンクに対し送出し（ステップＳ９）、一方、エンドノードである場合、登録・更新された経路情報を、経路確定情報として、受信されたリンクに送出する（ステップＳ１０）。
【０００９】
この、経路確定情報は、途中の中継ノードの経路テーブル２に登録された経路情報に基づいて経路をさかのぼり、宛先ノード（ツリーの根であるルート（ＲＯＯＴ）に相当）に至る。
【００１０】
なお、パス経路設定に関連する技術としては、下記の特許文献１〜５に開示の技術などが挙げられる。
【特許文献１】特開２００１−２４４９７４号公報
【特許文献２】特開２００２−２５２６３４号公報
【特許文献３】特開２００４−００７２０１号公報
【特許文献４】特開２００４−０２３４７３号公報
【特許文献５】特開２００４−１７２７０８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
図１１（ａ），（ｂ）に、設定されたツリー形状のマージ型パス（パスＩＤ＝Ｐ４１，Ｐ４３）及び（パスＩＤ＝Ｐ４２ａ，Ｐ４２ｂ）の構成を示す。ノード１１からノード４１へ至る経路（経路自身は、エンドノード４１側から決定されていく）において、図９では、太線のリンクをリンクコスト１、細線のリンクをリンクコスト４で示しているが、ノード２１−３１間のリンクのリンクコストは４であるのに対し、ノード２１−２２−３２−３１間の累積コストは３であるので、このパスは、ノード２２−３２のリンクを通過することになる。
【００１２】
同様にして、全てのパスは、図１１に示すように、ノード２２−３２のリンクを通過することになる。従って、このリンクにトラヒックが集中することなる。これは、各パスの経路を決定するに際して、リンクコスト値のみを用い、他のパスの使用状況を考慮して決定しないからである。例えば、ノード１１からノード４１へ、ノード１３からノード４３へ至るパスは、それぞれノード２１−３１間リンク、ノード２３−３３間リンクを通過するようにすれば、トラヒックが分散し、バッファ待ちを含む転送時間を短縮することができる。
【００１３】
本発明の目的は、リンクコストを経路設定のパラメータとして用いつつ、負荷が集中しない経路設定システム及びその方法を提供することである。
【課題を解決するための手段】
【００１４】
本発明による経路設定システムは、複数の通信ノードが互いにリンクにより接続されてなる通信システムにおけるパス経路設定システムであって、パス経路設定に際して、ノード間リンクを通過するあるいは通過することが見込まれるパス数またはパスの所要帯域とリンクコストとからなるパラメータを有する評価関数を用いて、経路設定をなす手段を含むことを特徴とする。
【００１５】
本発明による経路設定方法は、複数の通信ノードが互いにリンクにより接続されてなる通信システムにおけるパス経路設定方法であって、パス経路設定に際して、ノード間リンクを通過するあるいは通過することが見込まれるパス数またはパスの所要帯域とリンクコストとからなるパラメータを有する評価関数を用いて、経路設定をなすステップを含むことを特徴とする。
【００１６】
本発明による通信ノードは、通信システムにおいて互いにリンクにより接続されてなる通信ノードであって、パス経路設定に際して、ノード間リンクを通過するあるいは通過することが見込まれるパス数またはパスの所要帯域とリンクコストとからなるパラメータを有する評価関数を用いて、経路設定をなす手段を含むことを特徴とする。
【００１７】
本発明によるプログラムは、通信システムにおいて互いにリンクにより接続されてなる通信ノードの経路設定動作をコンピュータにより実行させるためのプログラムであって、パス経路設定に際して、ノード間リンクを通過するあるいは通過することが見込まれるパス数またはパスの所要帯域とリンクコストとからなるパラメータを有する評価関数を用いて、経路設定をなす処理を含むことを特徴とする。
【００１８】
本発明の作用を述べる。パス経路設定に際して、リンクコストを初期値とし、当該リンクを通過するかあるいは通過することが見込まれるパス数に対して単調増加となる値（動的リンクコスト）をパラメータとする評価関数を用い、この評価関数が最小となるようにすることにより、パスの経路設定を行うものである。パスの数あるいは所要帯域に依存して経路のコストを設定することができるので、特定の経路へのトラヒックの集中を防ぎ、ネットワーク全体の使用効率を高めることができる。
【発明の効果】
【００１９】
本発明によれば、パス数やパスの所要帯域などリンクの負荷に応じて、トラヒックが分散する方向で経路が設定されるので、ネットワーク全体の使用効率を高め、かつ各パスのエンド間の遅延時間特性を改善することができるという効果がある。また、本発明によれば、高速経路設定方式により得られた経路を暫定的に使用し、かつこの暫定経路を経路設定の初期状態とすることにより、経路設定までの待ち時間を短縮することができるという効果もある。
【発明を実施するための最良の形態】
【００２０】
以下に、本発明の実施の形態について詳述する。先ず、本発明の第１の実施の形態を説明する。本実施の形態に用いるノードの構成は、その機能ブロックを図１に示す様に、従来例で説明したノードと同一であり、経路処理部１と、経路テーブル２と、スイッチ部３とを有しており、あるリンク（図では、リンク６）からの受信経路情報４を入力として、他のリンク（図では、リンク７〜９）に対して送信経路情報５を出力するものである。
【００２１】
従来例のノードと相違する部分は、図２に示す経路情報の構成と、図５に示す経路処理部１における処理フローである。図２（ａ）に示す経路情報は、パスＩＤと、パス毎に管理される累積動的リンクコストと（累積パーパスリンクコスト（Per Path Lik Cost ）値）とを含む。なお、後述する他の実施の形態において用いられるフィールドを、オプションとして示している（パス数、帯域、重み付きパス数）。
【００２２】
図２（ｂ）は、経路テーブル２内の経路情報を示すものであり、リンク番号、パスＩＤ、累積動的リンクコスト値、パス数からなる。ここで、動的リンクコストとは、リンクコストに通過するパス数を乗じた値（リンクコスト×通過パス数）であり、累積動的リンクコストとは、経路上で累積された動的リンクコスト値である。この動的リンクコストを用いて、パスの最適化を図るのが本発明の特徴である。これは、コスト１の伝送路（４Ｇｂｐｓ）に４つのパスが存在する場合と、コスト４（１Ｇｂｐｓ）の伝送路に１つにパスが存在する場合と、同じコスト値を与えている。これは、パス当たりの帯域が共に１Ｇｂｐｓで同じというモデルに帰着させている。
【００２３】
ノード１１からノード４１へ至る経路設定につき説明する。経路は、ルートノードであるノード４１に近い部分から決定されていく。ノード４１からノード１１へ至る経路として、ノード３１，３２を経由するものを考える。ノード３３を経由するものも考えられるが、遠回りの経路で累積パーパスコストが高くなるので、説明を簡単にするために本説明では省略する。
【００２４】
図３を参照しつつノード１１からノード４１へ至る経路設定について説明する。ノード３１に、パスＩＤ＝Ｐ４１に関する最初の受信経路情報がノード４１より到着する。よって、ノード３１は、ノード３１−４１間の動的リンクコストを加算し、加算後の累積動的リンクコストＸを、ノード３２，２１に対し、送信経路情報として送出する。パスＩＤ＝Ｐ４１を含むノード２１−３１間リンクのパス数が、このときＭになったとすると、このリンクの動的リンクコスト＝リンクコスト値４×パス数Ｍとなる。ノード２１は累積動的リンクコスト＝Ｘ＋４×Ｍの送信経路情報をノード１１とノード２２に送出し、同時に、経路テーブル２２にも登録する。
【００２５】
その後、ノード２１は、ノード２２よりパスＩＤ＝Ｐ４１に関し累積動的リンクコストＹの経路情報を受信したとする（この経路情報は、ノード２２よりノード１２，２３にも通知される）。ノード２１では、ノード２２−２１間のリンクの動的リンクコスト＝（リンクコスト１）×（パスＩＤ＝Ｐ４１を含むパス数Ｎ）を加えた累積動的リンクコスト＝Ｙ＋１×Ｎと、経路テーブル２に登録されている値（Ｘ＋４×Ｍ）と比較する。登録されている値が大きくない場合、経路情報の更新は行わない。
【００２６】
登録されている情報が大きい場合は、ノード２２からの経路が選択され、累積動的スリンク値＝Ｙ＋１×Ｎとする送信経路情報が、経路テーブル２に更新・登録されると共に、ノード１１，３１に送出される。ノード１１には、先に通知された累積動的リンクコスト＝Ｘ＋４×Ｎの送信経路情報の更新として通知される。ノード２２には、更新された送信経路情報は通知されないので、先に通知した累積動的リンクコスト＝Ｘ＋４×Ｎの送信経路情報の抹消を通知する。
【００２７】
以上のようにして、リンクを通過するパス数に依存する動的リンクコストを定義し、経路設定を行う。この制御を繰り返し、パスＩＤ＝Ｐ４１の発ノードであるノード１１において、最終的に、累積動的リンクコストが最小となるリンクが決定され、経路確定情報が経路をさかのぼってルートノード（この場合ノード４１）に送出されることになる。
【００２８】
図４に、本発明により設定されたパス形態の一例を示す。同図（ａ）は、パスＩＤ＝Ｐ４１（実線），パスＩＤ＝Ｐ４３（点線）を、同図（ｂ）はパスＩＤ＝Ｐ４２ａ（実線），Ｐ４２ｂ（破線）を、それぞれ示している。図１１の従来技術を用いた場合との相違点は、図４（ａ）において、ノード１１からノード４１への経路及びノード２３からノード３３への経路が、ノード２２とノード３２の間リンクを経由せずに直接接続されている点である。図４（ｃ）に動的リンクコスト＝リンクコスト×通過パス数を示す。ノード２１とノード３１との直結リンクにおける累積動的リンクコスト＝４である。
【００２９】
これに対し、ノード２２，３２を経由する場合のノード２１とノード３１との間の累積動的リンクコストは、４＋４＋１＝９（第１項のノード２１−２２間の動的リンクコストは、通過パス数が４となるので、１×４＝４で与えられる）となる。従って、累積動的リンクコストを用いて経路設定を行うことにより、ノード２１−３１あるいはノード２３−３２への直結リンクが選択され、トラヒックを分散させることが可能となる。
【００３０】
図５に、本実施の形態に用いる経路処理部１における処理フローを示す。先ず、受信経路情報４を受信する（ステップＳ１１）。次に、受信したリンクに対応付けて経路情報を一時格納する（ステップＳ１２）。そして、受信したリンクの動的リンクコスト（＝リンクコスト×パス数）を計算する（ステップＳ１３）。この計算結果を、受信経路情報４内の累積動的リンクコストに加算し、自ノードを含む新たな累積動的リンクコストを算出する（ステップＳ１４）。
【００３１】
次に、受信経路情報４内のパスＩＤに関わる経路情報が経路テーブル２に登録済み否かをチェックする（ステップＳ１５）。登録済みの場合には、累積Per Path Link Costの登録値と、新規に算出された累積動的リンクコストとを比較する（ステップＳ１６）。累積Per Path Cost 値の更新は、パスの変更により、パスが減ったリンクに関わるパスに対しても行う。
【００３２】
ステップＳ１５のチェック結果が、経路テーブル２に未登録を示す場合、あるいはステップＳ１６の比較結果が、新規累積動的リンクコストが登録済みの累積動的リンクコストより小さいことを示す場合、経路情報を経路テーブル２に新規に登録あるいは更新する（ステップＳ１７）。
【００３３】
当該ノードがパスのエンドノード（この場合、パスの発ノード）かを判定し（ステップＳ１８）、エンドノードでない場合には、登録・更新された経路情報を、経路確定情報として、受信されたリンク以外のリンクに対し送出する（ステップＳ１９）。登録を抹消された経路に関する経路情報の通知も同時に行われる。更に、あるパスが新たに設定あるいは抹消されると、動的リンクコストが変化するので、同じリンクを共有する他のパスの累積動的リンクコストも変化する。従って、累積動的リンクコストが変化したパスに関しても、新たに経路情報を更新し、他のノードに通知する必要がある。
【００３４】
一方、エンドノードである場合には、登録・更新された経路情報を、経路確定情報として、受信されたリンクに送出する（ステップＳ２０）。この経路確定情報は、途中の中継ノードの経路テーブル２に登録された経路情報に基づいて経路をさかのぼり宛先ノード（ツリーの根に相当）に至る。
【００３５】
このようにして、本発明を用いれば、リンクコストが小さくても、通過するパス数が増加すると、動的リンクコスト（＝リンクコスト×パス数）が単調に増加するので、従来技術のように、リンクコストの小さいリンクにトラヒックが集中するという状況を回避できる。
【００３６】
なお、リンクあたりのパス数は、経路情報のやりとりで各ノードは自立的に管理できるが、より安定した動作を実現するために、オプションとして、転送されるリンクにおけるパス数を経路情報に含ませても良い。
【００３７】
また、本実施の形態では、動的リンクコストの計算は、リンクの受信側ノードで行っているが、送信側ノードで行う構成にしてもよい。その場合、受信経路情報４内の累積動的リンクコストは、受信されるリンクを含む累積値となる。従って、受信された累積動的リンクコストと経路テーブル２の経路情報内の累積動的リンクコストとの比較を行う。更に、送出リンク対応に動的リンクコストを算出し、その値を累積動的加算コストに加算して送信経路情報に記載して送信する。
【００３８】
次に、本発明の第２の実施の形態の説明を行う。先の第１の実施の形態では、全てのパスに対する経路設定制御を同時に行うために、経路設定の収束に時間がかかる可能性がある。例えば、全パス数Ｈに対し、その２乗のオーダかかるとすると、ｔ個のグループに分割して経路設定を行う方が、所要時間を短縮することができる。本例では、パス数がｈj （ｊ＝１，２，……，ｔ）個の複数のグループに分け、時間を分けてグループ毎に経路設定を行うものである。
【００３９】
図６（ａ）は、第１の実施の形態のように全体をひとまとめで経路設定を行う場合の時系列処理状態を示し、同図（ｂ）は、本例におけるグループに分割して行う場合の時系列処理状態を示す。本実施の形態での処理は、センタノード（図示せず）から、グループ毎にパスのルート（Ｒｏｏｔ）となるノードの経路処理部１に対し、初期化された経路情報の発行を指示することにより実現される。
【００４０】
次に、本発明の第３の実施の形態の説明を行う。先の第１及び第２の実施の形態に対する本例の違いは、経路処理部１での処理フローのステップＳ１９にあり、他は同じである。本例では、ステップＳ１９は、「エンドノードでない場合、登録・更新された経路情報を、送信経路情報として、受信されたリンク以外のリンクに対し送出する。登録を抹消された経路に関する経路情報の通知も同時に行われる。」となり、他のパス関わる経路情報の更新を不要とするものである。
【００４１】
本例では、最適化の木目の細かさを犠牲にする可能性はあるものの、よりシンプルで安定した経路設定制御を実現するものである。本例では、センタノード（図示せず）は、設定の対象となるパスのルートとなるノードに対して経路設定制御動作の開始を指示すると共に、各ノードに対し設定の対象となるパス数Ｎを通知する。
【００４２】
パスＩＤ＝Ｐ４１，Ｐ４２ａの２つの経路設定を例に、図７を用いて説明する。経路設定の対象となるパス数は２なので、図７（ａ）に示すように、全てのリンクコストに見込まれるパス数２を乗じた動的リンクコストを与える。これは、全てのリンクにこの２つのパスが設定された状況を想定し、この状況で、パスＩＤ＝Ｐ４１（実線），Ｐ４２ａ（点線）につき経路の設定を行う。
【００４３】
本例では、経路設定中にパス数の変動は生じないので、動的リンクコストの変動は生じず、パスの抹消の手続きは不要となる。図７（ｂ）に、次のステップとして、パスＩＤ＝Ｐ４２ｂとＰ４３の設定制御を示す。この場合のパス数は、最初のステップで設定されたパス数と見込まれるパス数２（パスＩＤ＝Ｐ４２ｂ，Ｐ４３）の和となる。ノード１１からノード２１へのリンクでは、パス数＝２＋２（Ｐ４１，Ｐ４２ａ）となり、ノード２３からノード３３へのリンクはパスＩＤ＝Ｐ４１，Ｐ４２ａのリンクとなっていないので、パス数＝０＋２となっている。
【００４４】
同様に、ノード３２からノード３３へのリンクではパス数＝０＋２、ノード３２からノード４２へのリンクでは、パス数＝１（Ｐ４２ａ）＋２となっている。この状況におけるＰ４２ｂ（実線），Ｐ４３（点線）の形状を同図に示す。この場合、Ｐ４３において、ノード１３を発ノードとする経路は、ノード２３，３３を経てノード４３に至る経路の累積動的リンクコストは、ノード２３−２２−３２−３３を経る経路よりも小さいので、経路として設定される。このように４個のパスを２個ずつ２回に分けてパスの経路設定を行う。
【００４５】
なお、センタノードから各ノードへの通知する情報は、経路設定の対象となるパスの数に加えて、パスＩＤを含めても良い。本例では、２回に分割して経路の設定を行っているが、各回の経路設定中にパス数が変化することはないので、ステップＳ１９での、「あるパスが新たに設定あるいは抹消されると、動的リンクコストが変化するので、同じリンクを共有する他のパスの累積動的リンクコストも変化する。従って、累積動的リンクコストが変化したパスに関しても、新たに経路情報を更新し、他のノードに通知する必要」がなくなるのである。
【００４６】
次に、本発明の第４の実施の形態を、図８を用いて説明する。先の第３の実施の形態との違いは、初期状態として、他の方法で設定された経路、例えば従来例で設定された経路（図１１）を用いることである。この経路に基づいて算出されたパス数および動的リンクコストが、経路テーブル２の初期状態として登録される。
【００４７】
図８（ａ）には、従来例で設定された経路における動的リンクコストと、パスＩＤ＝Ｐ４１（実線）及びパスＩＤ＝Ｐ４２ａ（点線）を示す。初期状態でパスＩＤ＝Ｐ４１，Ｐ４２ａが既に設定されているリンクではパス数は変化せず（パス数の第２項が０）、どちらか一方が設定されているリンクでは、新たに設定される可能性があるパス数は１なので、見込まれるパス数は１つ増加し、どちらのパスも設定されていないリンクのパス数は２つ増加する。
【００４８】
同図では、パス数＝（初期状態でのパス数＋Ｐ４１，Ｐ４２ａの設定で見込まれるパス数）で表現する。具体的には、ノード１１−２１間のリンクでは、初期状態では全てのパスが設定されているので、見込まれるパス数＝４＋０となり、ノード２３−３３のリンクでは初期状態ではパスが設定されていないので、見込まれるパス数＝０＋２となる。
【００４９】
また、ノード３１−４１のリンクでは、初期状態ではパスＩＤ＝Ｐ４１が既に設定されているので、見込まれるパス数＝１＋１となる。このパス数は、各リンクにおいて、設定されているパスから、再設定の対象となるパスに関わるパスの数だけ差し引き、その後再設定されるパス数（この場合２）を加えて見込まれるパス数としてもよい。
【００５０】
Ｐ４１，Ｐ４２ａのパス設定制御では、パスＩＤ＝Ｐ４１において、ノード２１−３１間の直結リンクが選択される。図８（ｂ）には、パスＩＤ＝Ｐ４１，Ｐ４２ａが設定された後の動的リンクコストと、その状況で設定されたパスＩＤ＝Ｐ４２ｂ（実線）及びＰ４３（点線）を示す。ノード２１−３１間のリンクでは、初期状態で設定されたパス数０、次のステップで設定されたパス数１に、今回設定の対象となるパス数２を加えた数が、見込まれるパス数＝０＋１＋２となっている。
【００５１】
ノード２３−３３間のリンクでは、設定済のパスが無いので、見込まれるパス数＝０＋０＋２となる。また、ノード３２−４２間リンクでは、初期状態で設定されたパス（Ｐ４２ａ，Ｐ４２ｂ）の数２と、次のステップで新たに設定されたパス数０と、今回設定の対象となるパス（Ｐ４２ｂ，Ｐ４３）のうち設定されていないパス（Ｐ４３）の数１を加えた値が、見込まれるパス数＝２＋０＋１として与えられる。同様にして、ノード３３−４３間リンクでは、見込まれるパス数＝１（Ｐ４３対応）＋０＋１（Ｐ４２ｂ対応）が与えられる。
【００５２】
このように、設定された動的リンクコストを用いてパスＩＤ＝Ｐ４２ｂ，Ｐ４３の設定を行うと、パスＩＤ＝Ｐ４３において、ノード２３−３３間の直結リンクが選択される。
【００５３】
このように、本例を用いて、トラヒックの分散をはかることができる。更に、本例では、従来方式で高速に暫定経路を設定し、その後時間をかけて本方式を実施することにより、経路設定のための待ち時間を小さくすることができる。また、従来方式を初期状態としているので、本方式により得られる結果は、従来方式よりも最適化されていることが保証される。更に、初期状態を設定するための経路制御のための経路テーブルと本発明による経路テーブルを兼用させても良い。
【００５４】
この第４の実施の形態は、第３の実施の形態の初期状態を他の経路設定方法により与えるというものであるが、別の実施の形態として、第１および第２の実施の形態の初期状態を他の経路設定方法により与えることも可能である。
【００５５】
以上の実施の形態では、宛先ノードをルートノードとするマージ型のパスで説明を行ったが、発ノードをルートノードとするマルチキャストツリー型のパスの設定できるし、またパスの端点ノードを一対構成とすることにより、途中でマージしないポイント−ポイント型のパスにも、本発明を適用することができる。
【００５６】
また、本説明では、パスの所要帯域に依存せず全てのパスを同じ扱いにしてパス数を扱っているが、動的リンクコスト＝リンクコスト×パスの所要帯域の総和としてもよい。パスそれぞれの所要帯域値は、所要帯域により重み付けられたパスとみなすことができるので、所要帯域の総和は、所要帯域に重み付けされた実効パス数とみなすことができる。
【００５７】
更には、パス経路設定時の評価関数として、動的リンクコスト＝リンクコスト×パス数、あるいは、リンクコスト×パスの所要帯域の総和を用いているが、一般的には、動的リンクコストを、リンクコストに依存した初期値を有し、パス数にあるいはパスの所要帯域に対し単調増加する関数を評価関数として与えれば良く、本発明は、その動的リンクコストの関数式を限定するものではない。
【００５８】
上記の各実施の形態におけるノードの経路処理部の動作は、予めその動作手順をプログラムとしてＲＯＭなどの記録媒体に記録しておき、これをコンピュータにより読取って実行させる様に構成できることは明白である。
【図面の簡単な説明】
【００５９】
【図１】本発明に用いるノードの構成を示すプロック図である。
【図２】本発明におけるパス経路情報（ａ）及びパスの経路テーブル（ｂ）を示す図である。
【図３】本発明による第１の実施の形態における経路設定状態を示す図である。
【図４】本発明による第１の実施の形態におけるパスの構成例を示す図である。
【図５】本発明による第１の実施の形態におけるノードの処理フローを示す図である。
【図６】本発明による第１及び第２の実施の形態における処理の時系列処理状態を示す図である。
【図７】本発明による第３の実施の形態におけるネットワークの動的リンクコスト及び設定パスを示す図である。
【図８】本発明による第４の実施の形態におけるネットワークの動的リンクコスト及び設定パスを示す図である。
【図９】従来技術及び本発明の実施例に用いるネットワークの構成を示す図である。
【図１０】従来技術におけるノードの処理フローを示す図である。
【図１１】従来技術を用いた場合の設定パスの構成を示す図である。
【符号の説明】
【００６０】
１  経路処理部
２  経路テーブル
３  スイッチ部
４  受信経路情報
５  送信経路情報
６〜１０  リンク
１１〜１３，
２１〜２３，
３１〜３３，
４１〜４３    ノード
【図１】
2007142609.tif 000003
【図２】
2007142609.tif 000004
【図３】
2007142609.tif 000005
【図４】
2007142609.tif 000006
【図５】
2007142609.tif 000007
【図６】
2007142609.tif 000008
【図７】
2007142609.tif 000009
【図８】
2007142609.tif 000010
【図９】
2007142609.tif 000011
【図１０】
2007142609.tif 000012
【図１１】
2007142609.tif 000013