JP2000236336A - 経路選択装置 - Google Patents

Abstract

(57)【要約】 【課題】 リンクが使用不能になった場合に、その情報
がエッジノードに伝搬されるまでの間に、エッジノード
が古いトポロジ情報でルーティングを行うと通信ができ
ない場合がある。 【解決手段】 リンクの使用可否状態を通信ノード間で
相互に通知し合うことにより、各通信ノードが持つ通信
網のトポロジ情報に反映させる。さらに、自通信ノード
に到来する転送すべきパケットがこれまで通過した通信
ノードおよびそれに直接接続するリンクおよび輻輳ある
いは故障リンクを取り除いた通信網のトポロジにより自
通信ノードに到来する転送すべきパケットの指定経路情
報を更新する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は通信網を構成する複
数の通信ノードを介して行われる通信に利用する。本発
明は通信網内における最短経路の選択に利用する。特
に、使用不能経路を迂回する最短経路の選択技術に関す
る。

【０００２】

【従来の技術】通信網を介して通信を行うためには、送
信端と受信端との間の経路を選択する必要がある。情報
転送方法として、回線交換とパケット交換（データグラ
ム）がある。回線交換の場合の経路の選択は、回線設定
時に、回線設定用信号にて通知される宛先アドレスを用
いて行われる。また、パケット交換の場合はパケットの
ヘッダにある宛先アドレスを用いて経路の選択が行われ
る。なお、パケット交換の場合でもデータグラムを用い
ずに仮想回線（バーチャルサーキット）を設定する場合
は経路の選択は回線設定時に行われる。

【０００３】回線交換およびパケット交換のいずれにつ
いても、経路を選択するタイミングに応じて二つの方法
に大別される。一つはホップバイホップに経路選択する
方法で、もう一つは通信網の送信端エッジノードで宛先
アドレスまでの経路を指定する方法である。ここで、ホ
ップバイホップとは、通信ノードにコネクション接続用
のセットアップメッセージを送り、この通信ノードはセ
ットアップメッセージに記載された帯域に余裕のある次
経路を順次選択する方法である。また、エッジノードと
は、送信端または受信端の通信ノードを指す。

【０００４】後者の方法をソースルーティングと呼び、
これを行うためには通信網のトポロジを送信端エッジノ
ードが知っていることが前提となる。ここで、ソースル
ーティングによる中継方法とは、ソースアドレスに続く
ルーティング情報により示されたブリッジおよびＬＡＮ
等を経由して中継する方法である。送信端のエッジノー
ドは通信網のトポロジ情報を元に宛先までの最短経路を
選択し、その経路を設定する。

【０００５】ソースルーティングの代表例として、ＡＴ
Ｍフォーラムで仕様が策定されたＰＮＮＩ(Private Net
work-Network Interface) がある。また、次世代のイン
ターネットプロトコルの標準であるＩＰｖ６でもソース
ルーティングが可能となるようにヘッダフォーマットが
決められている（文献名はＲＦＣ１８８３）。また、本
願出願人らの発明によるバースト回線交換網でも送信端
のエッジノードでソースルーティングを行う（特願平９
−３３４４４４号、本願出願時に未公開）。

【０００６】

【発明が解決しようとする課題】ソースルーティングを
行う場合には、送信側エッジノードは通信網のトポロジ
を知る必要があることは既に説明したとおりである。と
ころが、リンクの故障が発生し、その情報がエッジノー
ドへ伝搬するまでの間に、エッジノードが古いトポロジ
情報でルーティングを行うと通信ができない場合があ
る。また、経路上のリンクが他のユーザによって使用さ
れている場合には、そのリンクが使用可能となるまで待
たなければならない。

【０００７】このような場合に、通信を継続するために
は、経路上の途中の通信ノードで迂回経路を計算するこ
とが考えられる。従来の問題点を図５ないし図９を参照
して説明する。図５は従来の迂回路選択方法を示す図で
ある。図６は通信網の例を示す図である。図７は故障が
発生した通信網の例を示す図である。図８は他の通信網
の例を示す図である。図９は故障が発生した他の通信網
の例を示す図である。

【０００８】図５において、通信ノードＡからＣへの最
短経路上に通信ノードＢがある。図中では通信ノード
Ａ、Ｂ、Ｃのみを表記しているが、それら以外の通信ノ
ードを表記していない。ここで、通信ノードＢから通信
ノードＣへの最短経路は通信ノードＡからＣへの最短経
路の一部をなす。ここで、通信ノードＢから通信ノード
Ｃへ向けたリンクが使用できない場合には、通信ノード
Ｂは通信ノードＢとＣの間の第二最短経路を計算し、そ
の経路を選択することが考えられる。しかしながら、こ
の方法では以下に示すように閉じた経路ができてしまい
所望の宛先アドレスまで到達できない場合がある。

【０００９】図６は通信ノードＡから通信ノードＬとリ
ンク１からリンク１６とからなる網である。各リンクの
長さは同じであるとして、通信ノードＡから通信ノード
Ｅまでの経路選択を考えると、最短経路はＡ−Ｂ−Ｃ−
Ｄ−Ｅである。送信側エッジノードである通信ノードＡ
はこの最短経路を選択して通信を開始する。ここで、図
７に示すように、通信ノードＢと通信ノードＣとを結ぶ
リンク３が輻輳もしくは故障で使用できなかった場合に
は、通信ノードＢは通信ノードＥまでの最短経路である
リンク３が使用できないので、通信ノードＢから通信ノ
ードＥまでの第二最短経路であるＢ−Ｆ−Ｇ−Ｄ−Ｅを
選択し直す。

【００１０】次に、通信ノードＦに来たときに、通信ノ
ードＦと通信ノードＧとを結ぶリンク８が使用できない
場合には、通信ノードＦは通信ノードＦから通信ノード
Ｅまでの第二最短経路であるＦ−Ｈ−Ｂ−Ｃ−Ｄ−Ｅを
選択し直す。ところが、通信ノードＢと通信ノードＣと
を結ぶリンク３は使用できないので、通信ノードＢまで
戻ったときに、再度通信ノードＦへの経路を選択してし
まい、閉じた経路ができてしまう。

【００１１】図８はもう一つの例であり、図６の網から
通信ノードＧとリンク８とリンク９とを取り除いたもの
である。この例では、図９に示すように、通信ノードＢ
でリンク３が使用できないことが判った時点で、通信ノ
ードＦへの経路を選択するが、通信ノードＦではリンク
３が使用できないことを知らないと、第二最短経路であ
るＦ−Ｈ−Ｂを選択してしまい図９に示すように閉じた
経路ができてしまう。このように閉じた経路ができてし
まうのは、経路選択を行う通信ノードがその通信ノード
に直接接続されているリンク以外の状態を知らないため
に起こるのである。

【００１２】本願出願人は、特願平１０−１１２３４７
号（本願出願時に未公開、以下、先願という）により、
各通信ノードが相互にリンクの輻輳および故障などによ
るリンクの使用可否状態を通知し合い、通信網のトポロ
ジを仮想的に再現し、送信端の通信ノードは、この仮想
的に再現された通信網のトポロジにしたがって最短経路
を選択する経路選択装置を提案したが、本願において、
輻輳または故障の発生を知ることなく送信端の通信ノー
ドが最短経路を選択した場合に、上記閉じた経路が発生
することを回避する技術についてさらに詳細な提案を行
なうことにした。

【００１３】本発明は、このような背景に行われたもの
であって、リンクの輻輳または故障発生時点から各通信
ノード相互間にその情報が伝達されるまでの信号伝搬遅
延時間内であっても目的の宛先への経路を選択すること
ができる経路選択装置を提供することを目的とする。

【００１４】

【課題を解決するための手段】本発明は、リンクの使用
可否状態をノード間で相互に通知し合うことにより、リ
ンクが輻輳や故障で使用不能になった場合に、そのこと
を各ノードが持つ網のトポロジ情報に反映させる。送信
側のエッジノードは経路情報を作成する際に、網のトポ
ロジ情報からそのリンクを取り除いた仮想の網を構成
し、最短経路を計算する。

【００１５】また、リンクが使用不能となった情報がエ
ッジノードに伝わるまでの間、一時的に不通の経路を計
算してしまう場合があるので、その場合に備えて、経路
上の途中のノードでも同様に仮想網を作成し、宛先まで
の最短経路を再度計算する。その経路上のリンクが使用
不能であることを知ると、そのノードは網のトポロジ情
報からそのリンクを取り除いた仮想の網を構成し、その
仮想の網から、送信者と受信者との間の経路情報のう
ち、送信側からそのリンクまでの挟まれた全てのノード
とそれらノードに直接接続されたリンクを取り除く。そ
のようにしてできた仮想の網において、その使用不能と
なったリンクの直前のノードから宛先までの最短経路を
計算する。その経路情報で送信者と受信者との間の経路
情報のうち、その使用不能となったリンクの直前のノー
ドから宛先までの経路情報を新しく計算した経路情報で
置き換えて経路選択を継続していく。

【００１６】すなわち、本発明は経路選択装置であっ
て、複数の通信ノードと、この複数の通信ノード間を相
互に接続する複数のリンクとを備え、前記通信ノード
は、自己に接続されたリンクの使用可否状態を通信の有
無にかかわらず判定する手段と、この判定する手段の判
定結果を前記複数の通信ノード間で相互に通知し合う手
段と、この通知し合う手段により通知された使用可否状
態にしたがって通信網のトポロジを仮想的に再現する手
段とを備え、送信端の通信ノードは、前記再現する手段
により仮想的に再現された通信網上で当該送信端から受
信端に至る経路を選択する手段と、この選択する手段に
より選択された経路の情報にしたがって転送すべきパケ
ットに書込まれる指定経路情報を生成する手段とを備え
た経路選択装置である。

【００１７】ここで、本発明の特徴とするところは、前
記通信網のトポロジを仮想的に再現する手段は、自通信
ノードに到来する転送すべきパケットがこれまでに通過
した通信ノードおよびそれに直接接続するリンクおよび
輻輳あるいは故障リンクを取り除いた通信網のトポロジ
を仮想的に再現するトポロジ更新手段を含み、このトポ
ロジ更新手段の更新結果にしたがって自通信ノードに到
来する転送すべきパケットの前記指定経路情報を更新す
る手段を備えたところにある。

【００１８】前記通信網のトポロジを仮想的に再現する
手段は、前記リンクの使用可否状態が変更になった都度
そのトポロジを更新する手段を含む構成としたり、ある
いは、前記通信網のトポロジを仮想的に再現する手段
は、前記リンクの使用可否状態の変更にかかわらずその
トポロジを周期的に更新する手段を含む構成とすること
により、仮想的に再現された通信網のトポロジを実際の
通信網と同じくすることができる。

【００１９】前記経路を選択する手段は、中継の通信ノ
ード数の少ない経路から順に選択する手段を含むことに
より、最短経路を選択することができる。

【００２０】

【発明の実施の形態】発明の実施の形態を図１および図
２を参照して説明する。図１は本発明実施例の経路選択
装置の要部ブロック構成図である。図２は本発明第一実
施例を説明するための通信網の故障例を示す図である。

【００２１】本発明は、図２に示すように、複数の通信
ノードＡ〜Ｌと、この複数の通信ノードＡ〜Ｌ間を相互
に接続する複数のリンク１〜１６とを備え、通信ノード
Ａ〜Ｌは、自己に接続されたリンクの使用可否状態を通
信の有無にかかわらず判定する手段である使用可否判定
部２１と、この使用可否判定部２１の判定結果を複数の
通信ノードＡ〜Ｌ間で相互に通知し合う手段である使用
可否通知部２２と、この使用可否通知部２２により通知
された使用可否状態にしたがって通信網のトポロジを仮
想的に再現する手段である仮想通信網構成部２３とを備
え、送信端の通信ノードＡは、仮想通信網構成部２３に
より仮想的に再現された通信網上で当該送信端から受信
端に至る経路を選択する手段である経路選択部２４と、
経路選択部２４により選択された経路の情報にしたがっ
て転送すべきパケットに書込まれる指定経路情報を生成
する手段である指定経路情報生成部２５とを備えた経路
選択装置である。

【００２２】ここで、本発明の特徴とするところは、仮
想通信網構成部２３は、自通信ノードに到来する転送す
べきパケットがこれまでに通過した通信ノードおよびそ
れに直接接続するリンクおよび輻輳あるいは故障リンク
を取り除いた通信網のトポロジを仮想的に再現し、指定
経路情報生成部２５は、仮想通信網構成部２３の更新結
果にしたがって自通信ノードに到来する転送すべきパケ
ットの前記指定経路情報を更新するところにある。

【００２３】本発明実施例では、仮想通信網構成部２３
は、リンク１〜１６の使用可否状態が変更になった都度
そのトポロジを更新する。他の例としては、リンク１〜
１６の使用可否状態の変更にかかわらずそのトポロジを
周期的に更新するようにしてもよい。経路選択部２４
は、中継の通信ノード数の少ない経路から順に選択す
る。

【００２４】また、パケットの通信は通信装置３０によ
って行われる。このとき、リンクの使用可否情報は通信
装置３０から使用可否判定部２１に入力される。また、
転送すべきパケットの宛先情報は通信装置３０から経路
選択部２４に入力される。また、使用可否通知部２２か
ら他の通信ノードへの使用可否通知情報は通信装置３０
を介して他の通信ノードに転送される。経路選択部２４
が転送すべきパケットの宛先情報にしたがって経路を選
択した後に、指定経路情報生成部２５は選択された経路
にしたがって指定経路情報を生成し、通信装置３０に入
力する。通信装置３０では、入力された指定経路情報に
より転送すべきパケットを転送する。また、この指定経
路情報も転送すべきパケットのヘッダ情報として転送さ
れる。

【００２５】

【実施例】（第一実施例）本発明第一実施例を図２およ
び図３を参照して説明する。図３は本発明第一実施例を
説明するための図である。図２では、図６の通信網にお
いて、通信ノードＢと通信ノードＣとの間のリンク３と
通信ノードＦと通信ノードＧとの間のリンク８が使用不
能となった場合に通信ノードＡから通信ノードＥへの経
路選択を行う場合を想定する。

【００２６】まず、平常時の動作としては、リンク３と
リンク８とが使用不能となったことは通信ノード間で相
互に通知し合うことにより、各通信ノードが持つ網のト
ポロジ情報に反映させる。リンクの使用不能となった情
報を網内の全てのノードに伝搬させるには、D.Bertseka
s とR.Gallagarらによる文献Data Networks(2nd ed.,Pr
entice Hall,1992) の5.3 節(p.p.418-433) の方法など
を用いることにより可能である。

【００２７】この方法をごく簡単に説明すると、ある通
信ノードの隣接するリンクに故障が発生した場合に、そ
の通信ノードはそのリンク番号をメッセージに入れ、故
障が発生したリンク以外のリンクに向けて同報する。そ
のメッセージを受信した前記通信ノードに隣接する通信
ノードは、そのメッセージを受信したリンク以外のリン
クに向けてそのメッセージを同報する。このとき、同一
情報を通知するメッセージが重複しないようにするた
め、メッセージにはメッセージ番号を付与し、メッセー
ジを識別し、既に受信したメッセージであれば、他の通
信ノードに同報しない。このように、故障リンクの情報
を通信網内に伝搬させる。

【００２８】このようにして得たリンクの使用不能であ
ることの情報を元に、ノードＡは完全な通信網のトポロ
ジ情報からリンク３とリンク８とを取り除いた仮想の通
信網のトポロジ情報を元に、ノードＡからノードＥまで
の最短経路を計算する。ノードＡでは経路情報としてＡ
−Ｂ−Ｈ−Ｉ−Ｊ−Ｋ−Ｌ−Ｄ−Ｅを作成して経路選択
を行う。これにより使用不能となったリンクを使用する
ことなく、最短の経路を選択することができる。

【００２９】次に、リンク３とリンク８とが使用不能と
なった後、この情報が通信ノードＡに伝搬されるまでの
間に、通信ノードＡは通信ノードＥまでの最短経路とし
てＡ−Ｂ−Ｃ−Ｄ−Ｅを選択してしまった場合について
説明する。

【００３０】通信ノードＡはリンク３とリンク８とが使
用不能となったことを知らないので、通信網のトポロジ
情報を用いて、ノードＡからノードＥまでの最短経路と
してＡ−Ｂ−Ｃ−Ｄ−Ｅを選択する。次に、パケットが
通信ノードＢまで来たときに、通信ノードＢはリンク３
が使用不能であることを知っているので、通信ノードＡ
とリンク２およびリンク３を取り除いた仮想網イメージ
を作成し、通信ノードＢから通信ノードＥまでの最短経
路を計算する。

【００３１】Ｂ−Ｆ−Ｇ−Ｄ−Ｅが仮想網での最短経路
であるので、オリジナルの経路情報Ａ−Ｂ−Ｃ−Ｄ−Ｅ
のうち、Ｂ−Ｃ−Ｄ−Ｅの部分をＢ−Ｆ−Ｇ−Ｄ−Ｅで
置き換えたものであるＡ−Ｂ−Ｆ−Ｇ−Ｄ−Ｅを新しい
経路情報とする。

【００３２】次に、図３に示すように、パケットが通信
ノードＦまで来たときに、通信ノードＦはリンク８が使
用不能であることを知っているので、通信ノードＡ、
Ｂ、リンク１、２、３、７、１０およびリンク８を取り
除いた仮想網イメージを作成し、通信ノードＦからＥま
での最短経路を計算する。Ｆ−Ｈ−Ｉ−Ｊ−Ｋ−Ｌ−Ｄ
−Ｅが仮想網での最短経路であるので、通信ノードＦに
到着した時点での経路情報Ａ−Ｂ−Ｆ−Ｇ−Ｄ−Ｅのう
ち、Ｆ−Ｇ−Ｄ−Ｅの部分をＦ−Ｈ−Ｉ−Ｊ−Ｋ−Ｌ−
Ｄ−Ｅで置き換えたものＡ−Ｂ−Ｆ−Ｈ−Ｉ−Ｊ−Ｋ−
Ｌ−Ｄ−Ｅを新しい経路情報とする。

【００３３】このようにして、リンク３とリンク８とが
使用不能でありかつその情報をそれぞれ、通信ノードＡ
と通信ノードＢとが知らなくても、通信ノードＡから通
信ノードＥまでの最短経路を選択することができる。

【００３４】（第二実施例）本発明第二実施例を図４を
参照して説明する。図４は本発明第二実施例を説明する
ための図である。本発明第二実施例は、図８に示した通
信網において、リンク３が使用不能となった後、この情
報が通信ノードＡに伝搬されるまでの間に、通信ノード
Ａは通信ノードＥまでの最短経路としてＡ−Ｂ−Ｃ−Ｄ
−Ｅを選択してしまった場合について説明する。

【００３５】通信ノードＡはリンク３が使用不能となっ
たことを知らないので、通信網のトポロジ情報を用い
て、ノードＡからノードＥまでの最短経路としてＡ−Ｂ
−Ｃ−Ｄ−Ｅを選択する。次に、パケットが通信ノード
Ｂまで来たときに、通信ノードＢはリンク３が使用不能
であることを知っているので、通信ノードＡとリンク２
およびリンク３を取り除いた仮想網イメージを作成し、
通信ノードＢから通信ノードＥまでの最短経路を計算す
る。

【００３６】Ｂ−Ｆ−Ｈ−Ｉ−Ｊ−Ｋ−Ｌ−Ｄ−Ｅが仮
想網での最短経路であるので、オリジナルの経路情報Ａ
−Ｂ−Ｃ−Ｄ−Ｅのうち、Ｂ−Ｃ−Ｄ−Ｅの部分をＢ−
Ｆ−Ｈ−Ｉ−Ｊ−Ｋ−Ｌ−Ｄ−Ｅで置き換えたものであ
るＡ−Ｂ−Ｆ−Ｈ−Ｉ−Ｊ−Ｋ−Ｌ−Ｄ−Ｅを新しい経
路情報とする。以降はその経路どおりにルーティングさ
れていく。

【００３７】このようにして、リンク３が使用不能であ
りかつその情報をそれぞれ、通信ノードＡと通信ノード
Ｂとが知らなくても、通信ノードＡから通信ノードＥま
での最短経路を選択することができる。

【００３８】（実施例まとめ）このように、従来の経路
選択装置では、途中のリンクが輻輳や故障で使用不能な
場合に閉じた経路ができる場合があった。これは経路選
択を行う通信ノードがその通信ノードに直接接続されて
いるリンク以外の状態を知らないために起きる。本発明
では、途中のリンクが輻輳や故障などで使用不能となっ
ている場合でも、それまでに通過した通信ノードとそれ
に関するリンクと使用不能となっていることが判ってい
るリンクを取り除いた仮想的な通信網で最短経路を選択
し直すことにより、途中のリンクが輻輳や故障などで使
用不能となっている場合でも、閉じた経路を選択するこ
となく、正しく目的の宛先への経路を選択できる。

【００３９】

【発明の効果】以上説明したように、本発明によれば、
リンクの輻輳または故障発生時点から各通信ノード相互
間にその情報が伝達されるまでの信号伝搬遅延時間内で
あっても目的の宛先への経路を選択することができる。

【図面の簡単な説明】

【図１】本発明実施例の経路選択装置の要部ブロック構
成図。

【図２】本発明第一実施例を説明するための通信網の故
障例を示す図。

【図３】本発明第一実施例を説明するための図。

【図４】本発明第二実施例を説明するための図。

【図５】従来の迂回路選択方法を示す図。

【図６】通信網の例を示す図。

【図７】故障が発生した通信網の例を示す図。

【図８】他の通信網の例を示す図。

【図９】故障が発生した他の通信網の例を示す図。

【符号の説明】

１〜１６ リンク ２０ 経路選択装置 ２１ 使用可否判定部 ２２ 使用可否通知部 ２３ 仮想通信網構成部 ２４ 経路選択部 ２５ 指定経路情報生成部 ３０ 通信装置 Ａ〜Ｌ 通信ノード

Claims (4)

【特許請求の範囲】
1. 【請求項１】 複数の通信ノードと、この複数の通信ノ
   ード間を相互に接続する複数のリンクとを備え、前記通
   信ノードは、自己に接続されたリンクの使用可否状態を
   通信の有無にかかわらず判定する手段と、この判定する
   手段の判定結果を前記複数の通信ノード間で相互に通知
   し合う手段と、この通知し合う手段により通知された使
   用可否状態にしたがって通信網のトポロジを仮想的に再
   現する手段とを備え、送信端の通信ノードは、前記再現
   する手段により仮想的に再現された通信網上で当該送信
   端から受信端に至る経路を選択する手段と、この選択す
   る手段により選択された経路の情報にしたがって転送す
   べきパケットに書込まれる指定経路情報を生成する手段
   とを備えた経路選択装置において、 前記通信網のトポロジを仮想的に再現する手段は、自通
   信ノードに到来する転送すべきパケットがこれまでに通
   過した通信ノードおよびそれに直接接続するリンクおよ
   び輻輳あるいは故障リンクを取り除いた通信網のトポロ
   ジを仮想的に再現するトポロジ更新手段を含み、 このトポロジ更新手段の更新結果にしたがって自通信ノ
   ードに到来する転送すべきパケットの前記指定経路情報
   を更新する手段を備えたことを特徴とする経路選択装
   置。
2. 【請求項２】 前記通信網のトポロジを仮想的に再現す
   る手段は、前記リンクの使用可否状態が変更になった都
   度そのトポロジを更新する手段を含む請求項１記載の経
   路選択装置。
3. 【請求項３】 前記通信網のトポロジを仮想的に再現す
   る手段は、前記リンクの使用可否状態の変更にかかわら
   ずそのトポロジを周期的に更新する手段を含む請求項１
   記載の経路選択装置。
4. 【請求項４】 前記経路を選択する手段は、中継の通信
   ノード数の少ない経路から順に選択する手段を含む請求
   項１記載の経路選択装置。