JP2000201182A - ル―ティング装置およびル―ティング方法 - Google Patents

Abstract

(57)【要約】 【課題】 高速かつ高信頼のパケット転送を達成する。 【解決手段】 ネットワーク全体に周期的に配信され、
各ノードが同期して保持するリンクステート情報と各ノ
ードが局所的に管理するインタフェース情報をもとに任
意のインタフェース内に輻輳が発生した場合に当該イン
タフェースを避けてアダプティブにリルーティングパス
を設定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はＩＰネットワーク内
の各ノード（ルータ）に搭載するルーティングアルゴリ
ズムに利用する。本発明はダイナミックに変動するトラ
ヒック環境下でアダプティブに経路変更を行い輻輳ポイ
ントを回避したルーティングを行うことにより高速かつ
高信頼のパケット転送を可能とするルーティングアルゴ
リズムに使用する。特にネットワークが階層化された大
規模なＩＰネットワークで輻輳ポイントを回避してマル
チパスを設定し負荷分散を行いながらルーティングを行
うスケーラブルなパケット転送技術に関する。

【０００２】

【従来の技術】現在インターネットの世界で広く利用さ
れているルーティングアルゴリズムは大きく２つのタイ
プのプロトコルに分類される。そのうちの一つはリンク
ステート型プロトコルと呼ばれるものでＯＳＰＦがその
代表的な例である。このルーティングプロトコルでは、
各ノードが隣合うノードまでのリンクステート情報（リ
ンクコスト）をネットワーク全体に同期（ネットワーク
内の各ノードの保持するデータが完全に一致）して配信
する必要がある。

【０００３】このとき、ネットワーク内の各ノードは配
信されたリンクステート情報をもとにネットワークトポ
ロジーを計算し、ネットワーク内の全ノードがネットワ
ークトポロジーを反映した同一の有効グラフを共有す
る。各ノードはこの経路情報をもとに最小メトリック
（距離）を達成するルートを検索することで目的宛先ま
での最短ルートを計算し各宛先毎のネクストホップノー
ドを確定する。この過程では各ルータが完全に同期した
有効グラフを用いて最短ルートの計算を行うためにホッ
プバイホップでパケットを転送しても各ノードが転送す
るネクストホップノードは最短ルート上に一致して存在
する。このため同一の最短ルートを用いてパケットを目
的宛先まで転送することが可能である。

【０００４】二つ目の代表的なルーティングプロトコル
がパスベクトル型のルーティングプロトコルである。Ｂ
ＧＰがその代表的な例である。パスベクトル型のルーテ
ィングプロトコルではネットワーク内の各ノードは隣接
するノードまでの転送コストを隣接ノードに通知する。
通知を受けた隣接ノードは自分自身の隣接ノード迄の転
送コストを加算して次に隣接する隣接ノードまでトータ
ルのホップコストを通知する。この操作をネットワーク
全体に波及して行うと、各ノードは任意の宛先までのホ
ップコストと隣接するネクストホップノードアドレスを
決定することができる。

【０００５】

【発明が解決しようとする課題】リンクステート情報を
もとにルーティング経路を決定するリンクステート型ア
ルゴリズムでは各ルータが保持する有効グラフが同期し
ていることを前提としている。そのため各ルータが同期
していない有効グラフをもとに最短ルートを計算すると
各ノード間で計算する最短ルートの不一致が生じパケッ
ト転送時にループを形成してしまう問題が存在する。

【０００６】一方、高スループットかつ高信頼のルーテ
ィングを行うためにはダイナミックに変動するネットワ
ーク内の輻輳ポイントを避けたアダプティブなルーティ
ングが必要となる。このためネットワーク内で局所的
に、しかもダイナミックに変動するトラヒック状況をネ
ットワークに同期して配信するメトリックに反映させて
各ノードがルーティング経路を計算することが望まし
い。

【０００７】しかしながらネットワーク規模が大きくな
ると、トラヒックの変動周期よりもメトリック配信周期
の方が大きくなるので、各ルータ間でダイナミックに変
動するトラヒック負荷を反映したメトリックを計算しネ
ットワーク全体に同期して配信することは不可能とな
る。そのため負荷に対応したアダプティブな最短ルート
を探索することは困難である。さらに、このアルゴリズ
ムでは各ノード間のホップコストを反映したメトリック
情報をもとにして最小メトリックルートから最短ルート
を計算するため、計算される任意のノードから宛先ノー
ドまでのルートは最小コストルートのみとなる。したが
ってネットワークの負荷状態に関わらず唯一のパケット
転送ルートを用いてルーティングを行うために、ネット
ワーク内リソースを反映した負荷分散を意識したマルチ
パスルーティングが実現できない問題が存在する。

【０００８】また、パスベクトル型のルーティングプロ
トコルでもルーティングパスを決定する際にはネットワ
ーク全体に同期して転送コストが配信されることを前提
とするために、先に説明したリンクステート型のプロト
コルと同様に局所的に発生した輻輳ポイントを避けたア
ダプティブなルーティングが実現できない問題点が存在
する。

【０００９】さらに、パスベクトル型のルーティングプ
ロトコルを用いた場合にでもＡＳ間のルーティングを行
う場合にＡＳ内のトラヒック状況を考慮したルーティン
グを行うことが困難なので階層化したネットワーク間で
は固定ルートを選択してルーティングを行っている。こ
のためルート内のＡＳ内で輻輳が発生した場合にダイナ
ミックに迂回ルートを設定不能となりトラヒック集中ポ
イントでパケット廃棄が多発しネットワーク全体のスル
ープット特性を著しく劣化させる問題点が存在する。

【００１０】このため、階層化した大規模ＩＰネットワ
ークで高負荷時にアダプティブに迂回ルートを設定しマ
ルチパス環境下でネットワーク全体の負荷分散を実行で
きるスケーラブルなルーティングアルゴリズムが必要と
なる。

【００１１】本発明は、このような背景に行われたもの
であり、ネットワーク内でダイナミックに変動して発生
する輻輳ポイントを避けたアダプティブなルーティング
を実行することができるルーティング装置およびルーテ
ィング方法を提供することを目的とする。本発明は、ル
ープフリーのルーティングを実行することができるルー
ティング装置およびルーティング方法を提供することを
目的とする。本発明は、マルチパス環境下での負荷分散
を達成しルーティングを実行することができるルーティ
ング装置およびルーティング方法を提供することを目的
とする。本発明は、階層化されたＩＰネットワーク内に
おいても輻輳ポイントを避けたループフリーのマルチパ
スのルーティングが可能となるルーティング装置および
ルーティング方法を提供することを目的とする。本発明
は、大規模階層化された複雑なＩＰネットワークで高ス
ループットかつ高信頼のパケット転送を実現することが
できるルーティング装置およびルーティング方法を提供
することを目的とする。

【００１２】

【課題を解決するための手段】本発明は、ネットワーク
全体に周期的に配信され、各ノードが同期して保持する
リンクステート情報と各ノードが局所的に管理するイン
タフェース情報をもとに任意のインタフェース内に輻輳
が発生した場合に当該インタフェースを避けてアダプテ
ィブにリルーティングパスを設定できることを主要な特
徴とする。

【００１３】従来の技術とは、局所情報をもとにアダプ
ティブにルーティングを行ってもループフリーのリルー
ティング経路を設定できること、マルチパス環境下で負
荷分散を行いながらパケット転送を行なえること、階層
化されたＩＰネットワーク内でも輻輳ポイントを避けた
ループフリーのアダプティブなマルチパスルーティング
が可能なところが異なる。

【００１４】すなわち、本発明の第一の観点はルーティ
ング装置であって、ネットワーク内で同期して分配され
るグローバルなＩＰアドレスとノードの位置関係を記述
するノードトポロジー情報と各ノード毎に管理されノー
ド内のインタフェースを通じて転送されるトラヒック負
荷を反映したローカルな輻輳情報とにしたがって輻輳ポ
イントを避けたリルーティングパスを任意の宛先に対し
てループフリーに設定する手段を備えることを特徴とす
る。

【００１５】前記ループフリーに設定する手段は、ルー
プフリーなリルーティングパスの方向を示すルーティン
グベクトル情報を保持する手段を含むことが望ましい。
これにより、ループを形成してしまう可能性のあるリル
ーティングパスの設定を回避することができる。

【００１６】また、ループフリーなリルーティングパス
の中で最小メトリックを備えるパス順にリルーティング
経路を設定する手段を備えることが望ましい。

【００１７】さらに、最小メトリックパスおよびそれ以
外の複数のリルーティングパスのトラヒック負荷の情報
を保持する手段と、この保持する手段に保持された情報
にしたがって目的宛先までネットワーク内での負荷分散
を行いながらルーティングを実行する手段を備えること
が望ましい。これにより、輻輳の発生確率を低減させる
ことができる。

【００１８】このとき、前記ルーティングを実行する手
段は、リンクステート交換周期よりも小さい一定周期毎
に、実際に転送されるトラヒック負荷を反映した転送コ
ストにより前記トラヒック負荷の情報を更新する手段を
含むことが望ましい。これにより、最新のトラヒック負
荷の情報にしたがって、負荷分散を行いながらルーティ
ングを実行することができる。

【００１９】また、階層化されたＩＰネットワーク内に
おける階層間をまたがってループフリーでマルチパスを
設定し負荷分散を行いながらルーティングを実行する階
層間ルーティング実行手段を備えることが望ましい。こ
れにより、階層化されたＩＰネットワークにおいても本
発明ルーティング装置のルーティングアルゴリズムを用
いることができる。

【００２０】このとき、前記階層間ルーティング実行手
段は、自階層および自階層よりも上位または下位の階層
のトラヒック負荷および輻輳の情報を管理してルーティ
ングを実行する代表ノードを備えることが望ましい。こ
の代表ノードにより、各階層間に本発明ルーティング装
置のルーティングアルゴリズムを用いることができる。

【００２１】本発明の第二の観点はルーティング方法で
あって、ネットワーク内で同期して分配されるグローバ
ルなＩＰアドレスとノードの位置関係を記述するノード
トポロジー情報と各ノード毎に管理されノード内のイン
タフェースを通じて転送されるトラヒック負荷を反映し
たローカルな輻輳情報とにしたがって輻輳ポイントを避
けたリルーティングパスを任意の宛先に対してループフ
リーに設定することを特徴とする。

【００２２】このとき、ループフリーなリルーティング
パスの方向を示すルーティングベクトル情報にしたがい
リルーティングパスを任意の宛先に対してループフリー
に設定することが望ましい。また、ループフリーなリル
ーティングパスの中で最小メトリックを備えるパス順に
リルーティング経路を設定することが望ましい。

【００２３】最小メトリックパスおよびそれ以外の複数
のリルーティングパスのトラヒック負荷の情報にしたが
って目的宛先までネットワーク内での負荷分散を行いな
がらルーティングを実行することが望ましい。このと
き、リンクステート交換周期よりも小さい一定周期毎
に、実際に転送されるトラヒック負荷を反映した転送コ
ストにより前記トラヒック負荷の情報を更新することが
望ましい。

【００２４】階層化されたＩＰネットワーク内における
階層間をまたがってループフリーでマルチパスを設定し
負荷分散を行いながらルーティングを実行することもで
きる。このとき、自階層および自階層よりも上位または
下位の階層のトラヒック負荷および輻輳の情報を管理し
てルーティングを実行することが望ましい。

【００２５】

【発明の実施の形態】発明の実施の形態を図１を参照し
て説明する。図１は本発明ルーティング装置の要部ブロ
ック構成図を含むルーティングイメージを示す図であ
る。

【００２６】本発明はルーティング装置１０であって、
ネットワーク内で同期して分配されるグローバルなＩＰ
アドレスとノードの位置関係を記述するノードトポロジ
ー情報と各ノード毎に管理されノード内のインタフェー
スを通じて転送されるトラヒック負荷を反映したローカ
ルな輻輳情報とにしたがって輻輳ポイントを避けたリル
ーティングパスを任意の宛先に対してループフリーに設
定する手段であるルーティング部２０を備えることを特
徴とする。

【００２７】ルーティング部２０は、ループフリーなリ
ルーティングパスの方向を示すルーティングベクトル情
報を保持する。また、ループフリーなリルーティングパ
スの中で最小メトリックを備えるパス順にリルーティン
グ経路を設定する。さらに、ルーティング部２０は、最
小メトリックパスおよびそれ以外の複数のリルーティン
グパスのトラヒック負荷の情報を保持し、この保持され
た情報にしたがって目的宛先までネットワーク内での負
荷分散を行いながらルーティングを実行する。このと
き、ルーティング部２０は、リンクステート交換周期よ
りも小さい一定周期毎に、実際に転送されるトラヒック
負荷を反映した転送コストにより前記トラヒック負荷の
情報を更新する。

【００２８】また、本発明のルーティング装置１０は、
階層化されたＩＰネットワーク内における階層間をまた
がってループフリーでマルチパスを設定し負荷分散を行
いながらルーティングを実行する。このとき、自階層お
よび自階層よりも上位または下位の階層のトラヒック負
荷および輻輳の情報をルーティング部２０により管理し
てルーティングを実行する代表ノードを備える。

【００２９】

【実施例】提案するＡＭＲ(Adaptive Multipath Routin
g)アルゴリズムは各ノードがローカルに管理できるイン
タフェースコストｄｓｋ（ρ）とネットワーク全体が同
期して管理する最短ルートコストＤｋｊを用いてルーテ
ィングを行う。各ノードが管理するインタフェースコス
トは ｄｓｋ（ρ）＝ｄｓｋ（０）＋ＩＦ（ρ） で与えられる。ここでｄｓｋ（０）は予めリンクステー
ト情報交換時にネットワーク全体で同期して配信される
ネクストホップコストで低負荷時にノードｓからネクス
トホップノードｋまでのリンクコストを表わす。

【００３０】図２はインタフェースコスト（ＩＦ−ｃｏ
ｓｔ）を示す図であり、横軸に負荷ρをとり、縦軸にイ
ンタフェースコストｄｓｋ（ρ）をとると、ＩＦ（ρ）
はノードｓが管理するネクストホップノードまでのイン
タフェースコストを表し、図２に示すようにインタフェ
ースに流入する負荷の関数となる。このコストは高負荷
（ρ＞ρｔｈ）時には無限大に発散する。このようなネ
クストホップまでの輻輳情報を反映したコスト関数ｄｓ
ｋ（ρ）と予めネットワークに同期して配信されるネク
ストホップから宛先までのコスト関数Ｄｋｊを用いて各
ノードは最短コスト計算を行いルーティングを実行す
る。

【００３１】ＦＯＲ ＡＬＬ ＰＯＳＳＩＢＬＥ ＲＯ
ＵＴＥ ＣＡＬＣＵＬＡＴＥ ＩＦ ＣＯＳＴ ＩＦＣ〔ｋ〕←ｄｓｋ（ρ）＋Ｄｋｊ ＳＥＬＥＣＴ ｋ ＴＨＡＴ ＭＩＮＩＭＩＺＥ ＩＦ
ＣＯＳＴ Ｎｅｘｔ ｈｏｐ←ｋ このルーティングアルゴリズムを用いたルーティングイ
メージを図１に示す。図１はソースノードＳから宛先ノ
ードＪ迄のルーティング例である。ネットワークに同期
して配信されるメトリックをもとに計算される最短ルー
トはＳ→Ａ→Ｂ→Ｅ→Ｊであるが、ノードＢのインタフ
ェースＢＥに輻輳が発生して一部のトラヒックがノード
Ｂから直接Ｊに向かう例と、ノードＡのインタフェース
ＡＢに輻輳が発生してトラヒックの一部をＡ→Ｃ→Ｊと
迂回させる例とを示している。このように各ノードがロ
ーカルなＩＦコストを計算し輻輳発生時にはアダプティ
ブに迂回路を設定するためネットワーク全体で高スルー
プットかつ高信頼のルーティングが可能となる。 （ループフリールーティング）本発明のルーティングア
ルゴリズムでは各ノードがローカルなインタフェースコ
ストをもとに自律分散的に輻輳を回避しながらルーティ
ングを行うために輻輳ポイントを持つ複数のノードを通
過した後で同一宛先を目指すパケットがループを形成す
る可能性が存在する。図３にノードＣとノードＦに接続
されるリンクに輻輳が発生し、この輻輳ポイントを避け
るために宛先ＪのパケットがループＡ→Ｃ→Ｆ→Ｓを形
成する例を示す。このようなルーティングループの形成
を防止するために本発明アルゴリズムではネットワーク
内の各ノードが同期してルーティングベクトルを計算す
る。ルーティングベクトルは十分長い周期でネットワー
ク全体に同期して配備されるリンクステート情報から計
算され、宛先毎にネットワーク内でルーティング時に許
容される方向ベクトルをあらわしている。

【００３２】したがって、輻輳回避時にこのルーティン
グベクトルに一致した方向にリルート経路を設定すれば
ループを形成しないことを保証することができる。この
方向ベクトルは任意の宛先Ｊを起点としてＪに到達する
最短ルートを検出する逆方向のＤｉｊｋｓｔｒａのアル
ゴリズムを用いて計算される。図４にこの計算手法を用
いて計算したルーティングベクトルを示す。この例では
宛先Ｊをめざすルーティングべクトルをあらわしてい
る。各ノードが同期してこの情報を保持している。図４
におけるノードＡ、Ｂ、Ｃ、Ｓ、Ｅ、Ｆ、Ｇ、Ｊ間に記
載された数字は、各ノード間の転送コストを反映したメ
トリックを示す。また、符号Ｐ１、Ｐ２、Ｐ３、Ｐ４、
Ｐ５は、ノードＪからのメトリックが小さい順に各ノー
ドまでのパスをそれぞれ示す。

【００３３】例えばノードＡからは宛先Ｊに向かうのに
ループフリーのルートは１）Ａ→Ｂ→Ｅ→Ｊ、２）Ａ→
Ｂ→Ｊ、３）Ａ→Ｃ→Ｊの３種類のルートが存在するこ
とを示している。また、この計算手法によって計算され
るルーティングベクトルを各ノードで独立して記述する
ために各ノードは隣接するノードまでのルーティングフ
ラグを設定する。

【００３４】図４には併せてノードＡ、Ｂが保持する宛
先Ｊまでのｆｌａｇ情報を示す。フラグ値設定に当たっ
てはパケット転送方路とルーティングベクトルが一致す
る場合にはｆｌａｇ←０、一致しない場合にはｆｌａｇ
←∞を設定する。例えばノードＡが保持するフラグ情報
は隣接ノードＢ、Ｃ迄はＡ→Ｂ：０、Ａ→Ｃ：０、Ｓ迄
はループを形成する可能性があるのでＡ→Ｓ：∞と設定
する。このように逆方向のＤｉｊｋｓｔｒａを用いた計
算手法を用いれば任意の宛先Ｊを起点にして最短ホップ
ノードを構成する隣接ノードを順次決定していくのでネ
ットワークベクトルにはループが形成されないことを保
証する。

【００３５】また、逆方向のＤｉｊｋｓｔｒａ法を用い
れば、最短パスを検索する上では同一のアルゴリズムと
なるため、宛先Ｊまでの最短ルート候補が必ず包含され
て計算されるのでこのルートベクトルにはネットワーク
内の任意のノードＳから宛先Ｊまでの最短パスが必ず包
含されることになる。これを比較するために順方向の最
短ルート計算結果を図５に示す。図５におけるノード
Ａ、Ｂ、Ｃ、ＳＤ、Ｅ、Ｆ、Ｇ、Ｊ間に記載された数字
は、各ノード間の転送コストを反映したメトリックを示
す。また、符号Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６
は、ノードＳＤからのメトリックが小さい順に各ノード
までのパスをそれぞれ示す。また、（ ）内の数字はノ
ードＳＤから各ノードまでの累積メトリックを示す。図
５では、ノードＳＤが各宛先ノードを目指すパケットを
転送するときに使用するネクストホップノード情報を併
せて示す。

【００３６】これにより各ノードがこのネットワークベ
クトルを用いて最短ルートからの迂回路を形成しても迂
回に伴ってループが形成されず、迂回した隣接ノードか
らは最小メトリックコストを持つルートにしたがってリ
ルーティングされるので、リルーティングを実行しても
デフォルトの最小コストに近いルートを通過して目的宛
先までルーティングされることを保証している。 （本発明アルゴリズム）本発明アルゴリズムはリンクス
テートプロトコルを基本とするルーティングアルゴリズ
ムである。したがってＡＳ(Autonomous System: 同一の
管理者によって自動的にルーティングされる範囲) 内の
ネットワークトポロジーを把握するために各ノードはリ
ンクステート情報を交換しノード間で完全に同期した有
効グラフを形成する。本発明のアルゴリズムはこの有効
グラフをもとに（１）自ノードと（２）隣接ノードから
各宛先迄の最短ルートと（３）宛先までの迂回路を設定
するルーティングベクトルを計算し、その結果を図１で
説明したルーティング部２０に格納する。また、データ
ベースを設け、ルーティングベクトルの計算結果をこの
データベースに格納しておき、各ノードに配信したり、
各ノードからの要求にしたがって各ノードに転送するよ
うにしてもよい。下記のアルゴリズム１．が各ノードが
計算するリンク情報を記述する。

【００３７】次に本発明アルゴリズムを実装したノード
にパケットが到着した場合の処理をアルゴリズム２．以
下に記述し、ノード内のパケットフローの概念図を図６
に示す。ノードにパケットが到着するとパケットヘッダ
内のＩＰアドレスから目的ホストに到着するための同一
ＡＳ内の目的ノードを決定する。このとき、本発明アル
ゴリズムでは目的ノードに到達できるマルチルートのパ
スを選択しているのでノードで実測された転送コストを
反映した分配率でマルチパスの中から転送パスを選択す
る（例えばコネクション毎に）。その後マルチパスで転
送コストを反映した負荷分散が図れるようにパケットを
転送する。

【００３８】本発明アルゴリズムではマルチパスの候補
を一定周期ΔＴ（＜＜リンクステート交換周期）毎に実
際に転送されるトラヒック負荷を反映した転送コストで
更新する。本発明アルゴリズムでは△Ｔ内の各インタフ
ェースコストをモニタしてデフォルトルートのコストと
比較する。この過程では各インタフェースコストの中か
ら最小コストを持つものを選択する。選択されたインタ
フェースがデフォルトの最短パス上のインタフェースで
あればこのインタフェースには輻輳が発生していないこ
とになるのでこのインタフェースを用いてパケットを転
送する。このとき、デフォルトルート以外に転送ルート
が存在する場合には転送ルート候補から削除する。選択
されたインタフェースがデフォルトの最短ルートのイン
タフェースと異なるときには選択されたインタフェース
をマルチルート転送の候補に加える。この場合は先に述
べたコスト関数の定義によりデフォルトのインタフェー
スに輻輳が発生しているので、デフォルトルートからト
ラヒックを規定の分配率で迂回させる。 １．ＳＥＴ ＤＡＴＡＢＡＳＥ ＦＯＲ ＡＬＬ ＤＥＳＴＩＮＡＴＩＯＮＳ Ｃａｌｃｕｌａｔｅ Ｓｈｏｒｔｅｓｔ−Ｐａｔｈ （Ｓｏｕｒｃｅ ｉ→Ｄｅｓｔｉｎａｔｉｏｎ ｊ） Ｃａｌｃｕｌａｔｅ Ｓｈｏｒｔｅｓｔ−Ｐａｔｈ （Ｎｅｘｔ−ｈｏｐ ｋ→Ｄｅｓｔｉｎａｔｉｏｎ
ｊ） Ｓｅｔ Ｒｏｕｔｉｎｇ−Ｖｅｃｔｏｒ（ｊ） ２．ＳＥＬＥＣＴ ＯＰＴＩＭＡＬ ＲＯＵＴＥ ＦＯＲ ＥＡＣＨ ＰＡＣＫＥＴ ＣＯＭＭＩＮＧ （ＡＤＲＥＳＳ ＲＥＳＯＬＵＴＩＯＮ） Ｄｃｓ ＩＤ←Ａｄｒｅｓｓ Ｒｅｓｏｌｕｔｉｏｎ
（ＩＰ Ａｄｒｅｓｓ） （ＳＥＬＥＣＴ ＰＡＴＨ ＡＭＯＮＧ ＰＯＳＳＩＢ
ＬＥ ＰＡＴＨＳ） ＳＰ←Ｓｅｌｅｃｔ Ｐａｔｈ（Ｐｏｓｓｉｂｌｅ Ｐ
ａｔｈ〔〕） （ＤＩＳＴＲＩＢＵＴＥ ＰＡＣＫＥＴ） Ｄｉｓｔｒｉｂｕｔｅ Ｐａｃｋｅｔ（ＳＰ） （ＳＥＬＥＣＴ ＰＯＳＳＩＢＬＥ ＰＡＴＨ） ＡＦＴＥＲ ＳＥＶＥＲＡＬ ＩＮＴＥＲＶＡＬ ＯＢ
ＳＥＲＶＡＴＩＯＮ ＦＯＲ ＡＬＬ ＤＥＳＴＩＮＡＴＩＯＮ Ｄｅｆａｕｌｔ Ｒｏｕｔｅ←Ｓｈｏｒｔｅｓｔ−Ｐａ
ｔｈ（Ｓｏｕｒｃｅｉ→Ｄｅｓｔｉｎａｔｉｏｎ ｊ） Ｓｅｌｅｃｔ Ｒｏｕｔｅ←Ｓｅｌｅｃｔ Ｍｉｎ Ｒ
ｏｕｔｅ（ｊ） ＩＦ Ｓｅｌｅｃｔ Ｒｏｕｔｅ ＥＱＵＡＬ ＴＯ
Ｄｅｆａｕｌｔ Ｒｏｕｔｅ Ｎｅｘｔ ｈｏｐ←Ｄｅｆａｕｌｔ Ｒｏｕｔｅ Ｄｅｌｅｔｅ Ｅｘｔｒａ−Ｒｏｕｔｅ（Ｐｏｓｓｉｂ
ｌｅ Ｐａｔｈ〔〕）ＥＬＳＥ ＩＦ Ｓｅｌｅｃｔ
Ｒｏｕｔｅ ＤＩＦＦＥＲ ＦＲＯＭ Ｄｅｆａｕｌｔ
Ｒｏｕｔｅ Ｎｅｘｔ ｈｏｐ←Ｍｕｌｔｉ Ｒｏｕｔｅ Ａｄｄ Ｎｅｘｔ−Ｒｏｕｔｅ（Ｐｏｓｓｉｂｌｅ Ｐ
ａｔｈ〔〕） Ｓｅｌｅｃｔ Ｍｉｎ Ｒｏｕｔｅ（Ｐｏｓｓｉｂｌｅ
Ｐａｔｈ〔〕） Ｓｅｌｅｃｔ Ｍｉｎ Ｒｏｕｔｅ（Ｄｅｓ ＩＤ） ＦＯＲ ＡＬＬ ＰＯＳＳＩＢＬＥ ＲＯＵＴＥ ＣＡＬＣＵＬＡＴＥ ＲＯＵＴＥ ＣＯＳＴ ＲＣ〔ｋ〕←ＩＦＣ〔ｋ〕＋ｆｌａｇ ←ｄｊｋ（ρ）＋Ｄｋｊ＋ｆｌａｇ ＳＥＬＥＣＴ ｋ ＴＨＡＴ ＭＩＮＩＭＩＺＥ ＲＯ
ＵＴＥ ＣＯＳＴ Ｍｉｎ ｈｏｐ←ｋ このような機構を用いることにより本発明アルゴリズム
はネットワーク内の輻輳ポイントを回避してマルチルー
トで負荷分散を行いながらパケットを転送する。このた
め高スループットで低損失かつ低遅延のルーティングが
可能となる。 （マルチパス階層化ルーティング）次に、本発明アルゴ
リズムを階層化されたネットワークに適用する場合を考
える。図７は階層化されたＩＰネットワークを示してい
る。この例ではネットワークはＬｅｖｅｌ１〜Ｌｅｖｅ
ｌ３までの３つの階層構造を持つ。

【００３９】Ｌｅｖｅｌ３の階層では４つのノード１．
０．０〜４．０．０が相互に接続されるネットワークを
構成する。この階層下にはレベル２のノードが存在し、
それぞれ（１．１．０〜１．３．０）〜（４．１．０〜
４．４．０）のノードが存在し、図７に示すネットワー
クを構成する。レベル２の配下にも同様にレベル１のノ
ードが存在し図７に示すネットワークを構成する。最上
位のレベル３のネットワークでルーティングを行うため
にレベル２のノード内で代表ルータが決定される。この
代表ルータはレベル３階層のルーティング情報を保持
し、レベル３のルーティング処理を行う。

【００４０】図７の例ではネットワーク１．０．０内の
レベル２のノード１．２．０、１．３．０に存在するノ
ードがレベル３の代表ノードとなりレベル３のルーティ
ング処理を担当する。以下同様に代表ルータが決定され
る。このようにｋ階層で代表ノードに選出されたノード
はｋ＋１、ｋ階層のルーティング情報を管理しｋ＋１、
ｋ階層のルーティングの処理を行う。代表ノード以外の
ノードはｋ階層内のみのルーティング情報を管理してｋ
階層内に閉じたルーティング処理だけを担当する。この
ような階層化を行うことで各ノードが保持するルーティ
ング情報を圧縮し各階層内のルーティング処理を高速化
できる。また各階層に設置された代表ルータは上位階層
のルーティング処理を行うために代表ルータ同士でリン
クステート情報を交換する。

【００４１】図８は階層化されたＩＰネットワークを示
している。図８の例ではレベルｋのルーティングを行う
ためにレベルｋ＋１のノード（１．２．０，１．３．
０）、（２．２．０，２．３．０）、（３．１．０）、
（４．１．０，４．３．０）が代表ノードに選択されて
いる。各レベル内では発明アルゴリズムが独立に動作し
ており同一レベル内で輻輳が発生するとアダプティブに
マルチパスを設定して輻輳ポイントを回避する。また、
代表ノードはレベルｋのルーティングを管理しているの
でレベルｋ内で輻輳が発生するとレベルｋ内で迂回路を
設定してマルチパスで輻輳ポイントを迂回する。このと
き、同一のＡＳ内で宛先ノードＪに到達可能な別の代表
ノードが存在する場合には当該ノードを迂回路に設定す
る。また、このとき、先に述べたルーティングべクトル
を設定して代表ノード間ではループを構成しないように
仮定しておく。

【００４２】図８を用いてノード１．１．０がノード
３．２．０を目指す場合のパケット転送を説明する。ノ
ード１．１．０はパケットの宛先から同一ＡＳ内に目的
ノードが存在しないことを判断してデフォルトで設定さ
れている代表ルータ１．３．０にパケットを転送する。
ノード１．３．０は代表ノードなのでレベルｋのルーテ
ィング情報を用いてパケットをノード２．０．０に転送
する。ノード２．１．０は最短パスを用いてノード２．
３．０にパケットを転送する。このとき、ノード２．
３．０のインタフェースには輻輳が発生しているのでノ
ード２．３．０はレベルｋのルーティング情報を用いて
ノード２．２．０を経由してノード４．０．０にトラヒ
ックの一部を転送する。ノード４．１．０はレベルｋの
ルーティング情報をもとにノード４．３．０を経由して
ノード３．０．０に転送されノード３．１．０が３．
２．０に転送する。このような転送プロトコルを用いる
ため、提案プロトコルは階層化したＩＰ網でマルチパス
のルーティングが可能となる。

【００４３】

【発明の効果】以上説明したように、本発明によれば、
ネットワーク内でダイナミックに変動して発生する輻輳
ポイントを避けたアダプティブなループフリーのルーテ
ィングが実行できる。この過程では負荷分散を達成する
ためにマルチパス環境でルーティングが可能である。さ
らに、本発明のルーティングアルゴリズムで提案される
制御方法はネットワークの階層化に対してスケーラビリ
ティを持つために階層化されたＩＰネットワーク内にお
いても輻輳ポイントを避けたループフリーのマルチパス
のルーティングが可能となる。この結果、本ルーティン
グアルゴリズムを用いれば大規模階層化された複雑なＩ
Ｐネットワークで高スループットかつ高信頼のパケット
転送を実現できる。

【図面の簡単な説明】

【図１】本発明ルーティング装置の要部ブロック構成図
を含むルーティングイメージを示す図。

【図２】インタフェースコストを示す図。

【図３】ノードＣとノードＦに接続されるリンクに輻輳
が発生し、この輻輳ポイントを避けるために宛先Ｊのパ
ケットがループＡ→Ｃ→Ｆ→Ｓを形成する例を示す図。

【図４】ルーティングベクトルを示す図。

【図５】順方向の最短ルート計算結果を示す図。

【図６】ノード内のパケットフローの概念図。

【図７】階層化されたＩＰネットワークを示す図。

【図８】階層化されたＩＰネットワークを示す図。

【符号の説明】

１０ ルーティング装置 ２０ ルーティング部 Ａ、Ｂ、Ｃ、Ｅ、Ｆ、Ｇ、Ｊ、Ｓ、ＳＤ、１．０．０、
２．０．０、３．０．０、４．０．０、１．１．０、
１．２．０、１．３．０、２．１．０、２．２．０、
２．３．０、３．１．０、３．２．０、４．１．０、
４．２．０、４．３．０、４．４．０ ノード Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６ パス

───────────────────────────────────────────────────── フロントページの続き Ｆターム(参考） 5K030 GA13 HC01 JL07 KA01 KA05 LB07 LC11 LE03 MA01 5K033 AA03 CB06 DA05 DB01 DB12 DB14 DB18 EA07 EB02 EC03 9A001 CC06 CC07 FF03 GG01 GG06 GG19

Claims (14)

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