JP3553398B2 - ルーティング装置およびルーティング方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明はＩＰネットワーク内の各ノード（ルータ）に搭載するルーティングアルゴリズムに利用する。本発明はダイナミックに変動するトラヒック環境下でアダプティブに経路変更を行い輻輳ポイントを回避したルーティングを行うことにより高速かつ高信頼のパケット転送を可能とするルーティングアルゴリズムに使用する。特にネットワークが階層化された大規模なＩＰネットワークで輻輳ポイントを回避してマルチパスを設定し負荷分散を行いながらルーティングを行うスケーラブルなパケット転送技術に関する。
【０００２】
【従来の技術】
現在インターネットの世界で広く利用されているルーティングアルゴリズムは大きく２つのタイプのプロトコルに分類される。そのうちの一つはリンクステート型プロトコルと呼ばれるものでＯＳＰＦがその代表的な例である。このルーティングプロトコルでは、各ノードが隣合うノードまでのリンクステート情報（リンクコスト）をネットワーク全体に同期（ネットワーク内の各ノードの保持するデータが完全に一致）して配信する必要がある。
【０００３】
このとき、ネットワーク内の各ノードは配信されたリンクステート情報をもとにネットワークトポロジーを計算し、ネットワーク内の全ノードがネットワークトポロジーを反映した同一の有効グラフを共有する。各ノードはこの経路情報をもとに最小メトリック（距離）を達成するルートを検索することで目的宛先までの最短ルートを計算し各宛先毎のネクストホップノードを確定する。この過程では各ルータが完全に同期した有効グラフを用いて最短ルートの計算を行うためにホップバイホップでパケットを転送しても各ノードが転送するネクストホップノードは最短ルート上に一致して存在する。このため同一の最短ルートを用いてパケットを目的宛先まで転送することが可能である。
【０００４】
二つ目の代表的なルーティングプロトコルがパスベクトル型のルーティングプロトコルである。ＢＧＰがその代表的な例である。パスベクトル型のルーティングプロトコルではネットワーク内の各ノードは隣接するノードまでの転送コストを隣接ノードに通知する。通知を受けた隣接ノードは自分自身の隣接ノード迄の転送コストを加算して次に隣接する隣接ノードまでトータルのホップコストを通知する。この操作をネットワーク全体に波及して行うと、各ノードは任意の宛先までのホップコストと隣接するネクストホップノードアドレスを決定することができる。
【０００５】
【発明が解決しようとする課題】
リンクステート情報をもとにルーティング経路を決定するリンクステート型アルゴリズムでは各ルータが保持する有効グラフが同期していることを前提としている。そのため各ルータが同期していない有効グラフをもとに最短ルートを計算すると各ノード間で計算する最短ルートの不一致が生じパケット転送時にループを形成してしまう問題が存在する。
【０００６】
一方、高スループットかつ高信頼のルーティングを行うためにはダイナミックに変動するネットワーク内の輻輳ポイントを避けたアダプティブなルーティングが必要となる。このためネットワーク内で局所的に、しかもダイナミックに変動するトラヒック状況をネットワークに同期して配信するメトリックに反映させて各ノードがルーティング経路を計算することが望ましい。
【０００７】
しかしながらネットワーク規模が大きくなると、トラヒックの変動周期よりもメトリック配信周期の方が大きくなるので、各ルータ間でダイナミックに変動するトラヒック負荷を反映したメトリックを計算しネットワーク全体に同期して配信することは不可能となる。そのため負荷に対応したアダプティブな最短ルートを探索することは困難である。さらに、このアルゴリズムでは各ノード間のホップコストを反映したメトリック情報をもとにして最小メトリックルートから最短ルートを計算するため、計算される任意のノードから宛先ノードまでのルートは最小コストルートのみとなる。したがってネットワークの負荷状態に関わらず唯一のパケット転送ルートを用いてルーティングを行うために、ネットワーク内リソースを反映した負荷分散を意識したマルチパスルーティングが実現できない問題が存在する。
【０００８】
また、パスベクトル型のルーティングプロトコルでもルーティングパスを決定する際にはネットワーク全体に同期して転送コストが配信されることを前提とするために、先に説明したリンクステート型のプロトコルと同様に局所的に発生した輻輳ポイントを避けたアダプティブなルーティングが実現できない問題点が存在する。
【０００９】
さらに、パスベクトル型のルーティングプロトコルを用いた場合にでもＡＳ間のルーティングを行う場合にＡＳ内のトラヒック状況を考慮したルーティングを行うことが困難なので階層化したネットワーク間では固定ルートを選択してルーティングを行っている。このためルート内のＡＳ内で輻輳が発生した場合にダイナミックに迂回ルートを設定不能となりトラヒック集中ポイントでパケット廃棄が多発しネットワーク全体のスループット特性を著しく劣化させる問題点が存在する。
【００１０】
このため、階層化した大規模ＩＰネットワークで高負荷時にアダプティブに迂回ルートを設定しマルチパス環境下でネットワーク全体の負荷分散を実行できるスケーラブルなルーティングアルゴリズムが必要となる。
【００１１】
本発明は、このような背景に行われたものであり、ネットワーク内でダイナミックに変動して発生する輻輳ポイントを避けたアダプティブなルーティングを実行することができるルーティング装置およびルーティング方法を提供することを目的とする。本発明は、ループフリーのルーティングを実行することができるルーティング装置およびルーティング方法を提供することを目的とする。本発明は、マルチパス環境下での負荷分散を達成しルーティングを実行することができるルーティング装置およびルーティング方法を提供することを目的とする。本発明は、階層化されたＩＰネットワーク内においても輻輳ポイントを避けたループフリーのマルチパスのルーティングが可能となるルーティング装置およびルーティング方法を提供することを目的とする。本発明は、大規模階層化された複雑なＩＰネットワークで高スループットかつ高信頼のパケット転送を実現することができるルーティング装置およびルーティング方法を提供することを目的とする。
【００１２】
【課題を解決するための手段】
本発明は、ネットワーク全体に周期的に配信され、各ノードが同期して保持するリンクステート情報と各ノードが局所的に管理するインタフェース情報をもとに任意のインタフェース内に輻輳が発生した場合に当該インタフェースを避けてアダプティブにリルーティングパスを設定できることを主要な特徴とする。
【００１３】
従来の技術とは、局所情報をもとにアダプティブにルーティングを行ってもループフリーのリルーティング経路を設定できること、マルチパス環境下で負荷分散を行いながらパケット転送を行なえること、階層化されたＩＰネットワーク内でも輻輳ポイントを避けたループフリーのアダプティブなマルチパスルーティングが可能なところが異なる。
【００１４】
すなわち、本発明の第一の観点はルーティング装置であって、ネットワーク内で同期して分配されるグローバルなＩＰアドレスとノードの位置関係を記述するノードトポロジー情報と各ノード毎に管理されノード内のインタフェースを通じて転送されるトラヒック負荷を反映したローカルな輻輳情報とにしたがって輻輳ポイントを避けたリルーティングパスを任意の宛先に対してループフリーに設定する手段を備えることを特徴とする。
【００１５】
前記ループフリーに設定する手段は、ループフリーなリルーティングパスの方向を示すルーティングベクトル情報を保持する手段を含むことが望ましい。これにより、ループを形成してしまう可能性のあるリルーティングパスの設定を回避することができる。
【００１６】
また、ループフリーなリルーティングパスの中で最小メトリックを備えるパス順にリルーティング経路を設定する手段を備えることが望ましい。
【００１７】
さらに、最小メトリックパスおよびそれ以外の複数のリルーティングパスのトラヒック負荷の情報を保持する手段と、この保持する手段に保持された情報にしたがって目的宛先までネットワーク内での負荷分散を行いながらルーティングを実行する手段を備えることが望ましい。これにより、輻輳の発生確率を低減させることができる。
【００１８】
このとき、前記ルーティングを実行する手段は、リンクステート交換周期よりも小さい一定周期毎に、実際に転送されるトラヒック負荷を反映した転送コストにより前記トラヒック負荷の情報を更新する手段を含むことが望ましい。これにより、最新のトラヒック負荷の情報にしたがって、負荷分散を行いながらルーティングを実行することができる。
【００１９】
また、階層化されたＩＰネットワーク内における階層間をまたがってループフリーでマルチパスを設定し負荷分散を行いながらルーティングを実行する階層間ルーティング実行手段を備えることが望ましい。これにより、階層化されたＩＰネットワークにおいても本発明ルーティング装置のルーティングアルゴリズムを用いることができる。
【００２０】
このとき、前記階層間ルーティング実行手段は、自階層および自階層よりも上位または下位の階層のトラヒック負荷および輻輳の情報を管理してルーティングを実行する代表ノードを備えることが望ましい。この代表ノードにより、各階層間に本発明ルーティング装置のルーティングアルゴリズムを用いることができる。
【００２１】
本発明の第二の観点はルーティング方法であって、ネットワーク内で同期して分配されるグローバルなＩＰアドレスとノードの位置関係を記述するノードトポロジー情報と各ノード毎に管理されノード内のインタフェースを通じて転送されるトラヒック負荷を反映したローカルな輻輳情報とにしたがって輻輳ポイントを避けたリルーティングパスを任意の宛先に対してループフリーに設定することを特徴とする。
【００２２】
このとき、ループフリーなリルーティングパスの方向を示すルーティングベクトル情報にしたがいリルーティングパスを任意の宛先に対してループフリーに設定することが望ましい。また、ループフリーなリルーティングパスの中で最小メトリックを備えるパス順にリルーティング経路を設定することが望ましい。
【００２３】
最小メトリックパスおよびそれ以外の複数のリルーティングパスのトラヒック負荷の情報にしたがって目的宛先までネットワーク内での負荷分散を行いながらルーティングを実行することが望ましい。このとき、リンクステート交換周期よりも小さい一定周期毎に、実際に転送されるトラヒック負荷を反映した転送コストにより前記トラヒック負荷の情報を更新することが望ましい。
【００２４】
階層化されたＩＰネットワーク内における階層間をまたがってループフリーでマルチパスを設定し負荷分散を行いながらルーティングを実行することもできる。このとき、自階層および自階層よりも上位または下位の階層のトラヒック負荷および輻輳の情報を管理してルーティングを実行することが望ましい。
【００２５】
【発明の実施の形態】
発明の実施の形態を図１を参照して説明する。図１は本発明ルーティング装置の要部ブロック構成図を含むルーティングイメージを示す図である。
【００２６】
本発明はルーティング装置１０であって、ネットワーク内で同期して分配されるグローバルなＩＰアドレスとノードの位置関係を記述するノードトポロジー情報と各ノード毎に管理されノード内のインタフェースを通じて転送されるトラヒック負荷を反映したローカルな輻輳情報とにしたがって輻輳ポイントを避けたリルーティングパスを任意の宛先に対してループフリーに設定する手段であるルーティング部２０を備えることを特徴とする。
【００２７】
ルーティング部２０は、ループフリーなリルーティングパスの方向を示すルーティングベクトル情報を保持する。また、ループフリーなリルーティングパスの中で最小メトリックを備えるパス順にリルーティング経路を設定する。さらに、ルーティング部２０は、最小メトリックパスおよびそれ以外の複数のリルーティングパスのトラヒック負荷の情報を保持し、この保持された情報にしたがって目的宛先までネットワーク内での負荷分散を行いながらルーティングを実行する。このとき、ルーティング部２０は、リンクステート交換周期よりも小さい一定周期毎に、実際に転送されるトラヒック負荷を反映した転送コストにより前記トラヒック負荷の情報を更新する。
【００２８】
また、本発明のルーティング装置１０は、階層化されたＩＰネットワーク内における階層間をまたがってループフリーでマルチパスを設定し負荷分散を行いながらルーティングを実行する。このとき、自階層および自階層よりも上位または下位の階層のトラヒック負荷および輻輳の情報をルーティング部２０により管理してルーティングを実行する代表ノードを備える。
【００２９】
【実施例】
提案するＡＭＲ（Ａｄａｐｔｉｖｅ Ｍｕｌｔｉｐａｔｈ Ｒｏｕｔｉｎｇ）アルゴリズムは各ノードがローカルに管理できるインタフェースコストｄｓｋ（ρ）とネットワーク全体が同期して管理する最短ルートコストＤｋｊを用いてルーティングを行う。各ノードが管理するインタフェースコストは
ｄｓｋ（ρ）＝ｄｓｋ（０）＋ＩＦ（ρ）
で与えられる。ここでｄｓｋ（０）は予めリンクステート情報交換時にネットワーク全体で同期して配信されるネクストホップコストで低負荷時にノードｓからネクストホップノードｋまでのリンクコストを表わす。
【００３０】
図２はインタフェースコスト（ＩＦ−ｃｏｓｔ）を示す図であり、横軸に負荷ρをとり、縦軸にインタフェースコストｄｓｋ（ρ）をとると、ＩＦ（ρ）はノードｓが管理するネクストホップノードまでのインタフェースコストを表し、図２に示すようにインタフェースに流入する負荷の関数となる。このコストは高負荷（ρ＞ρｔｈ）時には無限大に発散する。このようなネクストホップまでの輻輳情報を反映したコスト関数ｄｓｋ（ρ）と予めネットワークに同期して配信されるネクストホップから宛先までのコスト関数Ｄｋｊを用いて各ノードは最短コスト計算を行いルーティングを実行する。
【００３１】
ＦＯＲ ＡＬＬ ＰＯＳＳＩＢＬＥ ＲＯＵＴＥ
ＣＡＬＣＵＬＡＴＥ ＩＦ ＣＯＳＴ
ＩＦＣ〔ｋ〕←ｄｓｋ（ρ）＋Ｄｋｊ
ＳＥＬＥＣＴ ｋ ＴＨＡＴ ＭＩＮＩＭＩＺＥ ＩＦ ＣＯＳＴ
Ｎｅｘｔ ｈｏｐ←ｋ
このルーティングアルゴリズムを用いたルーティングイメージを図１に示す。図１はソースノードＳから宛先ノードＪ迄のルーティング例である。ネットワークに同期して配信されるメトリックをもとに計算される最短ルートはＳ→Ａ→Ｂ→Ｅ→Ｊであるが、ノードＢのインタフェースＢＥに輻輳が発生して一部のトラヒックがノードＢから直接Ｊに向かう例と、ノードＡのインタフェースＡＢに輻輳が発生してトラヒックの一部をＡ→Ｃ→Ｊと迂回させる例とを示している。このように各ノードがローカルなＩＦコストを計算し輻輳発生時にはアダプティブに迂回路を設定するためネットワーク全体で高スループットかつ高信頼のルーティングが可能となる。
（ループフリールーティング）
本発明のルーティングアルゴリズムでは各ノードがローカルなインタフェースコストをもとに自律分散的に輻輳を回避しながらルーティングを行うために輻輳ポイントを持つ複数のノードを通過した後で同一宛先を目指すパケットがループを形成する可能性が存在する。図３にノードＣとノードＦに接続されるリンクに輻輳が発生し、この輻輳ポイントを避けるために宛先ＪのパケットがループＡ→Ｃ→Ｆ→Ｓを形成する例を示す。このようなルーティングループの形成を防止するために本発明アルゴリズムではネットワーク内の各ノードが同期してルーティングベクトルを計算する。ルーティングベクトルは十分長い周期でネットワーク全体に同期して配備されるリンクステート情報から計算され、宛先毎にネットワーク内でルーティング時に許容される方向ベクトルをあらわしている。
【００３２】
したがって、輻輳回避時にこのルーティングベクトルに一致した方向にリルート経路を設定すればループを形成しないことを保証することができる。この方向ベクトルは任意の宛先Ｊを起点としてＪに到達する最短ルートを検出する逆方向のＤｉｊｋｓｔｒａのアルゴリズムを用いて計算される。図４にこの計算手法を用いて計算したルーティングベクトルを示す。この例では宛先Ｊをめざすルーティングべクトルをあらわしている。各ノードが同期してこの情報を保持している。図４におけるノードＡ、Ｂ、Ｃ、Ｓ、Ｅ、Ｆ、Ｇ、Ｊ間に記載された数字は、各ノード間の転送コストを反映したメトリックを示す。また、符号Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５は、ノードＪからのメトリックが小さい順に各ノードまでのパスをそれぞれ示す。
【００３３】
例えばノードＡからは宛先Ｊに向かうのにループフリーのルートは１）Ａ→Ｂ→Ｅ→Ｊ、２）Ａ→Ｂ→Ｊ、３）Ａ→Ｃ→Ｊの３種類のルートが存在することを示している。また、この計算手法によって計算されるルーティングベクトルを各ノードで独立して記述するために各ノードは隣接するノードまでのルーティングフラグを設定する。
【００３４】
図４には併せてノードＡ、Ｂが保持する宛先Ｊまでのｆｌａｇ情報を示す。フラグ値設定に当たってはパケット転送方路とルーティングベクトルが一致する場合にはｆｌａｇ←０、一致しない場合にはｆｌａｇ←∞を設定する。例えばノードＡが保持するフラグ情報は隣接ノードＢ、Ｃ迄はＡ→Ｂ：０、Ａ→Ｃ：０、Ｓ迄はループを形成する可能性があるのでＡ→Ｓ：∞と設定する。このように逆方向のＤｉｊｋｓｔｒａを用いた計算手法を用いれば任意の宛先Ｊを起点にして最短ホップノードを構成する隣接ノードを順次決定していくのでネットワークベクトルにはループが形成されないことを保証する。
【００３５】
また、逆方向のＤｉｊｋｓｔｒａ法を用いれば、最短パスを検索する上では同一のアルゴリズムとなるため、宛先Ｊまでの最短ルート候補が必ず包含されて計算されるのでこのルートベクトルにはネットワーク内の任意のノードＳから宛先Ｊまでの最短パスが必ず包含されることになる。これを比較するために順方向の最短ルート計算結果を図５に示す。図５におけるノードＡ、Ｂ、Ｃ、ＳＤ、Ｅ、Ｆ、Ｇ、Ｊ間に記載された数字は、各ノード間の転送コストを反映したメトリックを示す。また、符号Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６は、ノードＳＤからのメトリックが小さい順に各ノードまでのパスをそれぞれ示す。また、（ ）内の数字はノードＳＤから各ノードまでの累積メトリックを示す。図５では、ノードＳＤが各宛先ノードを目指すパケットを転送するときに使用するネクストホップノード情報を併せて示す。
【００３６】
これにより各ノードがこのネットワークベクトルを用いて最短ルートからの迂回路を形成しても迂回に伴ってループが形成されず、迂回した隣接ノードからは最小メトリックコストを持つルートにしたがってリルーティングされるので、リルーティングを実行してもデフォルトの最小コストに近いルートを通過して目的宛先までルーティングされることを保証している。
（本発明アルゴリズム）
本発明アルゴリズムはリンクステートプロトコルを基本とするルーティングアルゴリズムである。したがってＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ： 同一の管理者によって自動的にルーティングされる範囲） 内のネットワークトポロジーを把握するために各ノードはリンクステート情報を交換しノード間で完全に同期した有効グラフを形成する。本発明のアルゴリズムはこの有効グラフをもとに（１）自ノードと（２）隣接ノードから各宛先迄の最短ルートと（３）宛先までの迂回路を設定するルーティングベクトルを計算し、その結果を図１で説明したルーティング部２０に格納する。また、データベースを設け、ルーティングベクトルの計算結果をこのデータベースに格納しておき、各ノードに配信したり、各ノードからの要求にしたがって各ノードに転送するようにしてもよい。下記のアルゴリズム１．が各ノードが計算するリンク情報を記述する。
【００３７】
次に本発明アルゴリズムを実装したノードにパケットが到着した場合の処理をアルゴリズム２．以下に記述し、ノード内のパケットフローの概念図を図６に示す。ノードにパケットが到着するとパケットヘッダ内のＩＰアドレスから目的ホストに到着するための同一ＡＳ内の目的ノードを決定する。このとき、本発明アルゴリズムでは目的ノードに到達できるマルチルートのパスを選択しているのでノードで実測された転送コストを反映した分配率でマルチパスの中から転送パスを選択する（例えばコネクション毎に）。その後マルチパスで転送コストを反映した負荷分散が図れるようにパケットを転送する。
【００３８】
本発明アルゴリズムではマルチパスの候補を一定周期ΔＴ（＜＜リンクステート交換周期）毎に実際に転送されるトラヒック負荷を反映した転送コストで更新する。本発明アルゴリズムでは△Ｔ内の各インタフェースコストをモニタしてデフォルトルートのコストと比較する。この過程では各インタフェースコストの中から最小コストを持つものを選択する。選択されたインタフェースがデフォルトの最短パス上のインタフェースであればこのインタフェースには輻輳が発生していないことになるのでこのインタフェースを用いてパケットを転送する。このとき、デフォルトルート以外に転送ルートが存在する場合には転送ルート候補から削除する。選択されたインタフェースがデフォルトの最短ルートのインタフェースと異なるときには選択されたインタフェースをマルチルート転送の候補に加える。この場合は先に述べたコスト関数の定義によりデフォルトのインタフェースに輻輳が発生しているので、デフォルトルートからトラヒックを規定の分配率で迂回させる。
１．ＳＥＴ ＤＡＴＡＢＡＳＥ
ＦＯＲ ＡＬＬ ＤＥＳＴＩＮＡＴＩＯＮＳ
Ｃａｌｃｕｌａｔｅ Ｓｈｏｒｔｅｓｔ−Ｐａｔｈ
（Ｓｏｕｒｃｅ ｉ→Ｄｅｓｔｉｎａｔｉｏｎ ｊ）
Ｃａｌｃｕｌａｔｅ Ｓｈｏｒｔｅｓｔ−Ｐａｔｈ
（Ｎｅｘｔ−ｈｏｐ ｋ→Ｄｅｓｔｉｎａｔｉｏｎ ｊ）
Ｓｅｔ Ｒｏｕｔｉｎｇ−Ｖｅｃｔｏｒ（ｊ）
２．ＳＥＬＥＣＴ ＯＰＴＩＭＡＬ ＲＯＵＴＥ
ＦＯＲ ＥＡＣＨ ＰＡＣＫＥＴ ＣＯＭＭＩＮＧ
（ＡＤＲＥＳＳ ＲＥＳＯＬＵＴＩＯＮ）
Ｄｃｓ ＩＤ←Ａｄｒｅｓｓ Ｒｅｓｏｌｕｔｉｏｎ（ＩＰ Ａｄｒｅｓｓ）
（ＳＥＬＥＣＴ ＰＡＴＨ ＡＭＯＮＧ ＰＯＳＳＩＢＬＥ ＰＡＴＨＳ）
ＳＰ←Ｓｅｌｅｃｔ Ｐａｔｈ（Ｐｏｓｓｉｂｌｅ Ｐａｔｈ〔〕）
（ＤＩＳＴＲＩＢＵＴＥ ＰＡＣＫＥＴ）
Ｄｉｓｔｒｉｂｕｔｅ Ｐａｃｋｅｔ（ＳＰ）
（ＳＥＬＥＣＴ ＰＯＳＳＩＢＬＥ ＰＡＴＨ）
ＡＦＴＥＲ ＳＥＶＥＲＡＬ ＩＮＴＥＲＶＡＬ ＯＢＳＥＲＶＡＴＩＯＮ
ＦＯＲ ＡＬＬ ＤＥＳＴＩＮＡＴＩＯＮ
Ｄｅｆａｕｌｔ Ｒｏｕｔｅ←Ｓｈｏｒｔｅｓｔ−Ｐａｔｈ（Ｓｏｕｒｃｅ
ｉ→Ｄｅｓｔｉｎａｔｉｏｎ ｊ）
Ｓｅｌｅｃｔ Ｒｏｕｔｅ←Ｓｅｌｅｃｔ Ｍｉｎ Ｒｏｕｔｅ（ｊ）
ＩＦ Ｓｅｌｅｃｔ Ｒｏｕｔｅ ＥＱＵＡＬ ＴＯ Ｄｅｆａｕｌｔ Ｒｏｕｔｅ
Ｎｅｘｔ ｈｏｐ←Ｄｅｆａｕｌｔ Ｒｏｕｔｅ
Ｄｅｌｅｔｅ Ｅｘｔｒａ−Ｒｏｕｔｅ（Ｐｏｓｓｉｂｌｅ Ｐａｔｈ〔〕）
ＥＬＳＥ ＩＦ Ｓｅｌｅｃｔ Ｒｏｕｔｅ ＤＩＦＦＥＲ ＦＲＯＭ Ｄｅｆａｕｌｔ Ｒｏｕｔｅ
Ｎｅｘｔ ｈｏｐ←Ｍｕｌｔｉ Ｒｏｕｔｅ
Ａｄｄ Ｎｅｘｔ−Ｒｏｕｔｅ（Ｐｏｓｓｉｂｌｅ Ｐａｔｈ〔〕）
Ｓｅｌｅｃｔ Ｍｉｎ Ｒｏｕｔｅ（Ｐｏｓｓｉｂｌｅ Ｐａｔｈ〔〕）
Ｓｅｌｅｃｔ Ｍｉｎ Ｒｏｕｔｅ（Ｄｅｓ ＩＤ）
ＦＯＲ ＡＬＬ ＰＯＳＳＩＢＬＥ ＲＯＵＴＥ
ＣＡＬＣＵＬＡＴＥ ＲＯＵＴＥ ＣＯＳＴ
ＲＣ〔ｋ〕←ＩＦＣ〔ｋ〕＋ｆｌａｇ
←ｄｊｋ（ρ）＋Ｄｋｊ＋ｆｌａｇ
ＳＥＬＥＣＴ ｋ ＴＨＡＴ ＭＩＮＩＭＩＺＥ ＲＯＵＴＥ ＣＯＳＴ
Ｍｉｎ ｈｏｐ←ｋ
このような機構を用いることにより本発明アルゴリズムはネットワーク内の輻輳ポイントを回避してマルチルートで負荷分散を行いながらパケットを転送する。このため高スループットで低損失かつ低遅延のルーティングが可能となる。
（マルチパス階層化ルーティング）
次に、本発明アルゴリズムを階層化されたネットワークに適用する場合を考える。図７は階層化されたＩＰネットワークを示している。この例ではネットワークはＬｅｖｅｌ１〜Ｌｅｖｅｌ３までの３つの階層構造を持つ。
【００３９】
Ｌｅｖｅｌ３の階層では４つのノード１．０．０〜４．０．０が相互に接続されるネットワークを構成する。この階層下にはレベル２のノードが存在し、それぞれ（１．１．０〜１．３．０）〜（４．１．０〜４．４．０）のノードが存在し、図７に示すネットワークを構成する。レベル２の配下にも同様にレベル１のノードが存在し図７に示すネットワークを構成する。最上位のレベル３のネットワークでルーティングを行うためにレベル２のノード内で代表ルータが決定される。この代表ルータはレベル３階層のルーティング情報を保持し、レベル３のルーティング処理を行う。
【００４０】
図７の例ではネットワーク１．０．０内のレベル２のノード１．２．０、１．３．０に存在するノードがレベル３の代表ノードとなりレベル３のルーティング処理を担当する。以下同様に代表ルータが決定される。このようにｋ階層で代表ノードに選出されたノードはｋ＋１、ｋ階層のルーティング情報を管理しｋ＋１、ｋ階層のルーティングの処理を行う。代表ノード以外のノードはｋ階層内のみのルーティング情報を管理してｋ階層内に閉じたルーティング処理だけを担当する。このような階層化を行うことで各ノードが保持するルーティング情報を圧縮し各階層内のルーティング処理を高速化できる。また各階層に設置された代表ルータは上位階層のルーティング処理を行うために代表ルータ同士でリンクステート情報を交換する。
【００４１】
図８は階層化されたＩＰネットワークを示している。図８の例ではレベルｋのルーティングを行うためにレベルｋ＋１のノード（１．２．０，１．３．０）、（２．２．０，２．３．０）、（３．１．０）、（４．１．０，４．３．０）が代表ノードに選択されている。各レベル内では発明アルゴリズムが独立に動作しており同一レベル内で輻輳が発生するとアダプティブにマルチパスを設定して輻輳ポイントを回避する。また、代表ノードはレベルｋのルーティングを管理しているのでレベルｋ内で輻輳が発生するとレベルｋ内で迂回路を設定してマルチパスで輻輳ポイントを迂回する。このとき、同一のＡＳ内で宛先ノードＪに到達可能な別の代表ノードが存在する場合には当該ノードを迂回路に設定する。また、このとき、先に述べたルーティングべクトルを設定して代表ノード間ではループを構成しないように仮定しておく。
【００４２】
図８を用いてノード１．１．０がノード３．２．０を目指す場合のパケット転送を説明する。ノード１．１．０はパケットの宛先から同一ＡＳ内に目的ノードが存在しないことを判断してデフォルトで設定されている代表ルータ１．３．０にパケットを転送する。ノード１．３．０は代表ノードなのでレベルｋのルーティング情報を用いてパケットをノード２．０．０に転送する。ノード２．１．０は最短パスを用いてノード２．３．０にパケットを転送する。このとき、ノード２．３．０のインタフェースには輻輳が発生しているのでノード２．３．０はレベルｋのルーティング情報を用いてノード２．２．０を経由してノード４．０．０にトラヒックの一部を転送する。ノード４．１．０はレベルｋのルーティング情報をもとにノード４．３．０を経由してノード３．０．０に転送されノード３．１．０が３．２．０に転送する。このような転送プロトコルを用いるため、提案プロトコルは階層化したＩＰ網でマルチパスのルーティングが可能となる。
【００４３】
【発明の効果】
以上説明したように、本発明によれば、ネットワーク内でダイナミックに変動して発生する輻輳ポイントを避けたアダプティブなループフリーのルーティングが実行できる。この過程では負荷分散を達成するためにマルチパス環境でルーティングが可能である。さらに、本発明のルーティングアルゴリズムで提案される制御方法はネットワークの階層化に対してスケーラビリティを持つために階層化されたＩＰネットワーク内においても輻輳ポイントを避けたループフリーのマルチパスのルーティングが可能となる。この結果、本ルーティングアルゴリズムを用いれば大規模階層化された複雑なＩＰネットワークで高スループットかつ高信頼のパケット転送を実現できる。
【図面の簡単な説明】
【図１】本発明ルーティング装置の要部ブロック構成図を含むルーティングイメージを示す図。
【図２】インタフェースコストを示す図。
【図３】ノードＣとノードＦに接続されるリンクに輻輳が発生し、この輻輳ポイントを避けるために宛先ＪのパケットがループＡ→Ｃ→Ｆ→Ｓを形成する例を示す図。
【図４】ルーティングベクトルを示す図。
【図５】順方向の最短ルート計算結果を示す図。
【図６】ノード内のパケットフローの概念図。
【図７】階層化されたＩＰネットワークを示す図。
【図８】階層化されたＩＰネットワークを示す図。
【符号の説明】
１０ ルーティング装置
２０ ルーティング部
Ａ、Ｂ、Ｃ、Ｅ、Ｆ、Ｇ、Ｊ、Ｓ、ＳＤ、１．０．０、２．０．０、３．０．０、４．０．０、１．１．０、１．２．０、１．３．０、２．１．０、２．２．０、２．３．０、３．１．０、３．２．０、４．１．０、４．２．０、４．３．０、４．４．０ ノード
Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６ パス

Claims (12)

1. ネットワーク内で同期して分配されるグローバルなＩＰアドレスとノードの位置関係を記述するノードトポロジー情報と各ノード毎に管理されノード内のインタフェースを通じて転送されるトラヒック負荷を反映したローカルな輻輳情報とにしたがって輻輳ポイントを避けたリルーティングパスを任意の宛先に対してループフリーに設定する手段を備え、
   前記ループフリーに設定する手段は、ループフリーなリルーティングパスの方向を示すルーティングベクトル情報にしたがいルーティングパスを設定する手段を含む
   ことを特徴とするルーティング装置。
2. ループフリーなリルーティングパスの中で最小メトリックを備えるパス順にリルーティング経路を設定する手段を備える請求項１記載のルーティング装置。
3. 最小メトリックパスおよびそれ以外の複数のリルーティングパスのトラヒック負荷の情報を保持する手段と、この保持する手段に保持された情報にしたがって目的宛先までネットワーク内での負荷分散を行いながらルーティングを実行する手段を備える請求項１記載のルーティング装置。
4. 前記ルーティングを実行する手段は、リンクステート交換周期よりも小さい一定周期毎に、実際に転送されるトラヒック負荷を反映した転送コストにより前記トラヒック負荷の情報を更新する手段を含む請求項３記載のルーティング装置。
5. 階層化されたＩＰネットワーク内における階層間をまたがってループフリーでマルチパスを設定し負荷分散を行いながらルーティングを実行する階層間ルーティング実行手段を備える請求項１記載のルーティング装置。
6. 前記階層間ルーティング実行手段は、自階層および自階層よりも上位または下位の階層のトラヒック負荷および輻輳の情報を管理してルーティングを実行する代表ノードを備える請求項５記載のルーティング装置。
7. ネットワーク内で同期して分配されるグローバルなＩＰアドレスとノードの位置関係を記述するノードトポロジー情報と各ノード毎に管理されノード内のインタフェースを通じて転送されるトラヒック負荷を反映したローカルな輻輳情報とにしたがって輻輳ポイントを避けたリルーティングパスを任意の宛先に対して、ループフリーなリルーティングパスの方向を示すルーティングベクトル情報にしたがいリルーティングパスをループフリーに設定することを特徴とするルーティング方法。
8. ループフリーなリルーティングパスの中で最小メトリックを備えるパス順にリルーティング経路を設定する請求項７記載のルーティング方法。
9. 最小メトリックパスおよびそれ以外の複数のリルーティングパスのトラヒック負荷の情報にしたがって目的宛先までネットワーク内での負荷分散を行いながらルーティングを実行する請求項７記載のルーティング方法。
10. リンクステート交換周期よりも小さい一定周期毎に、実際に転送されるトラヒック負荷を反映した転送コストにより前記トラヒック負荷の情報を更新する請求項９記載のルーティング方法。
11. 階層化されたＩＰネットワーク内における階層間をまたがってループフリーでマルチパスを設定し負荷分散を行いながらルーティングを実行する請求項７記載のルーティング方法。
12. 自階層および自階層よりも上位または下位の階層のトラヒック負荷および輻輳の情報を管理してルーティングを実行する請求項１１記載のルーティング方法。

Images