JPH0457428A - ノードにおけるネットワーク経路設定方式 - Google Patents

ノードにおけるネットワーク経路設定方式

Info

Publication number
JPH0457428A
JPH0457428A JP2168760A JP16876090A JPH0457428A JP H0457428 A JPH0457428 A JP H0457428A JP 2168760 A JP2168760 A JP 2168760A JP 16876090 A JP16876090 A JP 16876090A JP H0457428 A JPH0457428 A JP H0457428A
Authority
JP
Japan
Prior art keywords
message
node
search
sent
search message
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2168760A
Other languages
English (en)
Other versions
JP2875598B2 (ja
Inventor
Hiroaki Komine
浩昭 小峰
Takafumi Nakajo
中条　孝文
Keiji Miyazaki
宮崎　啓二
Takao Ogura
孝夫 小倉
Tetsuo Soejima
哲男 副島
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP16876090A priority Critical patent/JP2875598B2/ja
Priority to CA002045317A priority patent/CA2045317C/en
Priority to US07/720,916 priority patent/US5604868A/en
Priority to EP91110672A priority patent/EP0464680B1/en
Priority to DE69133470T priority patent/DE69133470T2/de
Publication of JPH0457428A publication Critical patent/JPH0457428A/ja
Application granted granted Critical
Publication of JP2875598B2 publication Critical patent/JP2875598B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/26—Route discovery packet
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/44—Distributed routing

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［目　次コ 概要 産業上の利用分野 従来の技術（第１１図） 発明が解決しようとする課題 課題を解決するための手段（第１，２図）作　用（第１
，２図） 実施例（第３〜１０図） 発明の効果 ［概　要］ リンクで接続される複数のノードを有するネットワーク
において、あるノードから経路の探索メツセージをフラ
ッディング方式により、送出し、この経路の他端に位置
するノードに到達すると、確認メツセージを送り返すこ
とにより、経路を設定するネットワーク経路設定方式に
関し、制御をノードに分散して、複雑且つ大容量なネッ
トワークにおいても、経路設定を速やかに行なえるよう
にするとともに、ノードが障害になった場合や複数リン
クに障害が起こった場合でも十分な対応ができるように
することを目的とし。
探索メツセージの伝播中に途中のノードで、それ以上メ
ツセージを伝播できなくなると、逆方向にキャンセルメ
ツセージを送出して、探索メツセージによって確保され
ているパスを解放するように構成する。
［産業上の利用分野コ 本発明は、リンクで接続される複数のノードを有するネ
ットワークにおいて、あるノー１−から経路の探索メツ
セージをフラッディング方式により、送出し、この経路
の他端に位置するノードに到達すると、確認メツセージ
を送り返すことにより、経路を設定するネットワーク経
路設定方式に関する。
近年、高度情報化により、ネットワークは多種多様なサ
ービスを提供する必要があり、またその形態も複雑にな
る。このため、経路設定や障害時における迂回路の設定
が迅速に処理される手段がネットワーク構成装置に必要
とされている。
で、各ノート１００との間は、図中点線で示すような制
御リンクで接続されている。
このような構成により、センタ局１０２が各ノード１０
０あるいはリンク１０１の状態を監視しておき、この監
視結果に基づいて、最適な経路が設定されるようになっ
ている。
ところで、障害発生時において、迂回経路の探索設定処
理をネットワーク中の各ノードに分散させるために、障
害の起こったリンクに接続されている２つのノード間で
メツセージを交換して経路を設定するフラッディング方
式が提案されている。
［従来の技術］ 第１１図は従来のネットワーク構成図であるが、この第
１１図において、１００はノードで、このノード１００
はそれぞれリンク１０１で相互に接続されている。なお
、ノード１００には、必要に応じて通信端末（図示せず
）が接続される。
また、１０２はセンタ局で、このセンタ局１゜２は、−
括してネットワークを運用管理するもの［発明が解決し
ようとする課題］ しかしながら、上記のような従来のセンタ局で一括して
運用・管理する方式では、制御信号がセンタ局に集中す
るため、ネットワークが複雑且つ大容量になってくると
、経路設定に時間を要するという問題点がある。
また、従来より提案されているフランディング方式を用
いた障害復旧処理では、ノードが障害になった場合や複
数リンクに障害が起こった場合に対応できないという問
題点がある。
本発明は、このような問題点に鑑みなされたもので、制
御をノードに分散して、複雑且つ大容量なネットワーク
においても、経路設定を速やかに行なえるようにすると
ともに、ノードが障害になった場合や複数リンクに障害
が起こった場合でも十分な対応ができるようにした、ネ
ットワーク経路設定方式を提供することを第１の目的と
している。
また、本発明は、同時に複数の経路設定要求があった場
合でも、十分に対応できるできるようにした、ネットワ
ーク経路設定方式を提供することを第２の目的としてい
る。
［課題を解決するための手段］ 第１図は第１の発明の原理説明図であるが、この第１図
において、１はノードで、各ノード１はリンク２で接続
されることにより、ネットワークを構成している。
また、このネットワークにおいては、あるノート１Ｓか
ら経路の探索メツセージをフラッディング方式により、
送出し、この経路の他端に位置するノード１Ｒに到達す
ると、確認メツセージを送り返すことにより、経路を設
定できるようになっている。
ところで、探索メツセージの伝播中に途中のノート１で
、それ以上メツセージを伝播できなくなると、逆方向に
キャンセルメツセージを送出して、探索メツセージによ
って確保されているパスを解放するように、各ノード１
が構成されている。
そして、キャンセルメツセージを受け取ったノード１で
は、探索メツセージを送出した全てのリンク２からのキ
ャンセルメツセージが送られてきたら、探索メツセージ
が送られてきた方向にキャンセルメツセージを送出する
ように構成されている。
さらに、探索メツセージの伝播中に途中のノード１で、
空き回線が確保できなくなると、逆方向にキャンセルメ
ツセージを送出して、探索メッセ−ジによって確保され
ているパスを解放するようにも構成されている。
また、探索メツセージの伝播中に通過ノード数が所定値
以上になると、逆方向にキャンセルメツセージを送出し
て、探索メツセージによって確保されているパスを解放
するように構成されている。
さらに、探索メツセージの伝播中に途中のノード１にお
いて、同一メツセージが先に到着している場合に、逆方
向にキャンセルメツセージを送出して、探索メツセージ
によって確保されているパスを解放するように構成され
ている。
第２図は第２の発明の原理説明図であるが、この第２図
においても、１はノードで、各ノード１はリンク２で接
続されることにより、ネットワークを構成している。
また、このネットワークにおいても、あるノード１Ｓか
ら経路の探索メツセージをフラッディング方式により、
送出し、この経路の他端に位置するノード１に到達する
と、確認メツセージを送り返すことにより、経路を設定
できるようになっている。
ところで、探索メツセージの伝播中に途中のノード１で
、異なる経路の探索メツセージが既に通過している場合
は、あとから来たメツセージをこのノード１内で待機さ
せ、先に通ったメツセージにより確保されているパスの
設定または解放が行なわれたら、待たせておいたメツセ
ージをこのノード１から取り出して送出するように構成
されている。
さらに、探索メツセージの伝播中に途中のノード１で、
異なる経路の探索メツセージが既に通過している場合に
、あとから来たメツセージをノード１内で待機させると
ともに、このメツセージを送ってきたノードに対し待ち
の状態であることを通知するようにも構成されている。
また、探索メツセージの伝播中に途中のノード１で、異
なる経路の探索メツセージが既に通過している場合に、
あとから来たメツセージをこのノード１内で待機させる
時間を制限し、指定した時間が経過すると、あとから来
たメツセージをキャンセルするように構成されている。
さらに、経過時間の測定を、メツセージが待っているノ
ード１で行なうか、障害を検出したノード１で行なうよ
うに構成されている。
また、探索メツセージの伝播中に途中のノード１で、異
なる経路の探索メツセージが既に通過している場合は、
あとから来たメツセージを順次このノード１内で待機さ
せ、先に通ったメツセージにより確保されているパスの
設定または解放が行なわれたら、待たせておいたメツセ
ージを優先順位類にこのノード１から取り出して送出す
るように構成されている。
［作　用］ 上述の第１の発明のネットワーク経路設定方式では、第
１図に示すように、探索メツセージの伝播中に途中のノ
ード１で、それ以上メツセージを伝播できなくなると、
逆方向にキャンセルメツセージを送出して、探索メツセ
ージによって確保されているパスを解放する。
そして、キャンセルメツセージを受け取ったノード１（
例えばＬＭ）では、探索メツセージを送出した全てのリ
ンク２からのキャンセルメツセージが送られてきたら、
探索メツセージが送られてきた方向にキャンセルメツセ
ージを送出する。
ところで、パスの解放態様は次のとおりである。
まず、探索メツセージの伝播中に途中のノード１で、空
き回線が確保できなくなると、逆方向にキャンセルメツ
セージを送出して、探索メツセージによって確保されて
いるパスを解放したり、探索メツセージの伝播中に通過
ノード数が所定値以上になると、逆方向にキャンセルメ
ツセージを送出して、探索メツセージによって確保され
ているパスを解放したり、探索メツセージの伝播中に途
中のノードにおいて、同一メツセージが先に到着してい
る場合に、逆方向にキャンセルメツセージを送出して、
探索メツセージによって確保されているパスを解放した
りするのである。
次に、第２の発明のネットワーク経路設定方式では、第
２図に示すように、探索メツセージの伝振巾に途中のノ
ード１（例えばＩＮ）で、異なる経路の探索メツセージ
が既に通過している場合は、あとから来たメツセージを
ノーＦＩＮ内で待機させ、先に通ったメツセージにより
確保されているパスの設定または解放が行なわれたら、
待たせておいたメツセージをこのノードＩＮから取り出
して送出する。このとき、待たせておいたメツセージを
優先順似顔に送出するようにすることもできる。
さらに、探索メツセージの伝播中に途中のノードＩＮで
、異なる経路の探索メツセージメツセージが既に通過し
ている場合には、あとから来たメツセージをこのノード
ＩＮ内で待機させるほか、このメツセージを送ってきた
ノード１Ｓに対し待ちの状態であることを通知する。
また、探索メツセージの伝播中に途中のノードＩＮで、
異なる経路の探索メツセージが既に通過している場合に
、あとから来たメツセージをこのノーＦＩＮ内で待機さ
せる時間を制限し、指定した時間が経過すると、あとか
ら来たメツセージをキャンセルする。このとき、経過時
間の測定は、メツセージが待っているノートＩＮで行な
うか、障害を検出したノード１Ｓで行なう。
［実施例コ 以下、図面を参照して本発明の詳細な説明する。
第３図は本発明の一実施例を示すネットワーク構成図で
あるが、この第３図において、１はノードで、各ノード
１はリンク２で接続されることにより、ネットワークを
構成している。そして、このネットワークにおいては、
あるノード１Ｓから経路の探索メツセージをフラッディ
ング方式により、送出し、この経路の他端に位置するノ
ード１Ｒに到達すると、確認メツセージを送り返すこと
により、経路を設定できるようになっている。
ところで、上記の各ノード１は、第４図に示すように、
通信制御部１１．メツセージ解析部１２゜メツセージ処
理部１３．メツセージ記憶部１４゜タイマ１５．メツセ
ージ送出部１６をそなえて構成されている。
ここで、通信制御部１１は、リンク２を通じて他のノー
ドとの通信のための制御を行なうものであるが、更に他
のノードからのメツセージを抽出したり、他のノードへ
のメツセージを挿入したりする機能も有している。
なお、他のノードからのメツセージという場合は、探索
メツセージやキャンセルメツセージを含み、他のノード
へのメツセージという場合は、確認メツセージやキャン
セルメツセージや待ちメツセージを含み、単にメツセー
ジという場合は、探索メツセージ、確認メツセージ、キ
ャンセルメツセージ、待ちメツセージを含んでいる場合
がある。
メツセージ解析部１２は、通信制御部１１で抽出された
他のノードからのメツセージについての解析を行なうも
のである。
メツセージ処理部１３は、メツセージ解析部１２にて解
析されたメツセージについて所要の種々の処理（後述）
を施すものである。
メツセージ記憶部１４は、複数のメツセージを記憶して
おくことができるもの（バッファ）で。
メツセージ処理部１３との間でメツセージの遺り取りを
するようになっている。
タイマ１５はメツセージをメツセージ記憶部１４に待機
させておく時間あるいはメツセージを送出してからの経
過時間を計測するために使用するものである。
メツセージ送出部１６は、メツセージ処理部１３からの
メツセージを通信制御部１１へ送出するものである。
ところで、このネットワークにおいては、あるノード１
から出された探索メツセージの伝播中に途中のノード１
で、それ以上メツセージを伝播できなくなると、メツセ
ージ処理部１３．メツセージ送出部１６を通じて逆方向
にキャンセルメツセージを送出して、探索メツセージに
よって確保されているパスを解放するように構成されて
いる。
また、キャンセルメツセージを受け取ったノード１では
、探索メツセージを送出した全てのリンクからのキャン
セルメツセージが送られてきたら、探索メツセージが送
られてきた方向にキャンセルメツセージを送出するよう
に構成されている。この場合は、キャンセルメツセージ
がメッセージ解析部１２を通じてメツセージ処理部１３
へ久方され、このメツセージ処理部１３で上記の判断を
して、全てのリンクからのキャンセルメツセージが送ら
れてきたら、メツセージ送出部１６を通じて探索メツセ
ージが送られてきた方向にキャンセルメツセージを送出
するのである。
さらに、探索メツセージの伝播中に途中のノードで、空
き回線（予備）が確保できなくなると、メツセージ送出
部１６を通じて逆方向にキャンセルメツセージを送出し
て、探索メツセージによって確保されているパスを解放
するように構成されている。
また、探索メツセージの伝播中に通過ノード数（ポツプ
数）が所定値以上になると、逆方向にキャンセルメツセ
ージを送出して、探索メツセージによって確保されてい
るパスを解放するように構成されている。この場合は、
メツセージ処理部１３で通過ノート数を所定値と比較し
ておき、通過ノード数が所定値以上であると、メツセー
ジ処理部１３．メツセージ送出部１６を通じて逆方向に
キャンセルメツセージを送出して、探索メツセージによ
って確保されているパスを解放するのである。なお、通
過ノード数が所定値より小さい場合は、探索メツセージ
に、通過ノード数を１だけインクリメントした情報を入
れる。
さらに、探索メツセージの伝播中に途中のノード１にお
いて、同一メツセージ［同−ＩＤ（識別し）を持ってい
るメツセージ］が先に到着している場合には、逆方向に
キャンセルメツセージを送出して、探索メツセージによ
って確保されているパスを解放するように構成されてい
る。この場合は、メツセージ処理部１３で、同一メツセ
ージが先に到着しているかどうかをＩＤ情報から判定し
、先に到着している場合には、メツセージ処理部１３、
メツセージ送出部１６を通じて逆方向にキャンセルメツ
セージを送出して、探索メツセージによって確保されて
いるパスを解放する。
また、探索メツセージの伝播中に途中のノード１で、異
なる経路の探索メツセージが既に通過している場合は、
あとから来たメツセージをノード内のメツセージ記憶部
１４で順次待機させ、先に通ったメツセージにより確保
されているパスの設定または解放が行なわれたら、メツ
セージ記憶部１４にて待たせておいたメツセージを、メ
ッセージ記憶部１４から優先順似顔または先着順に取り
出し、メツセージ処理部１３．メツセージ送出部１６を
通じて、送出するように構成されている。
さらに、探索メツセージの伝播中に途中のノード１で、
異なる経路の探索メツセージが既に通過している場合に
は、上記のようにあとから来たメツセージをノード１内
のメツセージ記憶部１４で順次待機させると同時に、こ
のメツセージを送ってきたノード１に対し待ちの状態で
あることを待ちメツセージとしてメツセージ処理部１３
．メツセージ送出部１６を通じて通知するように構成さ
れている。
また、探索メツセージの伝播中に途中のノード１で、異
なる経路の探索メツセージが既に通過している場合には
、あとから来たメツセージをメツセージ記憶部１４で待
機させる時間を制限し、指定した時間が経過すると、メ
ツセージ処理部１３の作用によりあとから来たメツセー
ジをキャンセルするようにも構成されている。
このとき、経過時間の測定を、メツセージが待っている
ノードで行なうか、障害を検出したノードで行なうよう
に構成されているが、かかる経過時間の測定はノード１
内のタイマ１５の情報を使用するのである。
次に、上記の機能を踏まえた本ネットワーク経路設定方
式についての概略動作を第５〜８図に示すフローチャー
トを用いて説明する。
まず、探索メツセージ処理について第５図を用いて説明
する。ステップＡ１で、ポツプ数（通過ノード数）が所
定値より大きいかどうかが判断され、もし小さければ、
次のステップＡ２で、同−ＩＤ（識別子）のメツセージ
が既に来ているかどうかの判断がなされ、来ていなけれ
ば、次のステツブＡ３で、送出できるリンクが存在する
かどうかが判定される。もしあれば、ステップＡ４で、
経路として設定する空き回線（予備）があるかどうかが
判定される。もしあれば１次のステップＡ５で、異なる
ＩＤのメツセージが先に到達しているかどうかが判断さ
れ、到達していなければ、ＮＯルートをとって、ステッ
プ八６で、探索メツセージを送出する。
もし、異なるＩＤのメツセージが先に到達していれば、
ステップＡ５でＹＥＳルートをとって、ステップＡ７で
、メツセージバッファ（メツセージ記憶部１４）にメツ
セージを格納してから、ステップＡ８で、待ちメツセー
ジを送出する。このとき、タイマ１５を起動しておくの
である（ステップＡ９）。
なお、上記のステップＡｌ、Ａ２でＹＥＳであるか、ス
テップＡ３．Ａ４でＮｏである場合、すなわち、ポツプ
数が所定値より大きい場合とか、同−ＩＤのメツセージ
が既に来ている場合とか、送出できるリンクが存在しな
い場合とか、経路として設定する空き回線がない場合は
、キャンセルメツセージ処理を行なう。なお、これらの
場合は、キャンセルメツセージを送出するのである（ス
テップＡ１１） ところで、あるノードにおいて複数のリンクが接続され
ている場合は、キャンセルメツセージ送出の前処理とし
て、探索メツセージを送出した全てのリンクからキャン
セルメツセージが来たかどうかの判断がなされる（ステ
ップＡ１０）。
なお、タイマ起動後に所要時間が経過してタイムアウト
した場合も、ステップＡｌｌのキャンセルメツセージ送
出処理が行なわれる。
また、キャンセルメツセージ処理の後は、経路設定メツ
セージ処理において、バッファ（メツセージ記憶部１４
）にメツセージがあるかどうかの判断なされる（ステッ
プＡ１４）。
なお、経路設定メツセージ処理において、ステップＡ１
４の処理の前には、経路設定メツセージ送出処理（ステ
ップＡ１２）やキャンセルメツセージ送出処理（ステッ
プＡ１３）がなされる。
そして、バッファ（メツセージ記憶部１４）にメツセー
ジがある場合は、ステップＡ１５において、優先順位の
高いメツセージをバッファから取り出すのである。なお
、取り出す順序は先着順でもよい。
更にその後は、中継ノード処理（第８図参照）を行なう
。
ところで、探索メツセージを送出するノートでの処理要
領は、第６図のようになる。まず、ステップＢ１で、探
索メツセージを送出すると、タイマ１５が起動せしめら
れ（ステップＢ２）、その後に、ステップＢ３で、経路
設定メツセージが到着しているかどうかが判断される。
もし、到着していれば、経路設定がなされ（ステップＢ
４）、到着していなければ、ステップＢ５で、キャンセ
ルメツセージが到着しているかどうかが判断される。到
着していなければ、ステップＢ６で、タイムアウトかど
うかが判断され、タイムアウトしていなければ、再度ス
テツブＢ３以降の処理を施す。
もし、タイムアウトすれば、ステップＢ７で、リトライ
するかどうかを判定し、もしリトライする場合は、ステ
ップＢ１へ戻る。もしリトライを行なわない場合は、終
了する。ここで、リトライとは、全ての容量（チャネル
分）が−度に設定できなかった場合は、残りの容量につ
いて経路設定処理を繰り返すことをいう。
次に、探索メツセージを受信するノートでの処理要領は
、第７図のようになる。まず、ステップＣ１で、探索メ
ツセージが到着したかどうかが判定され、到着している
場合は、ステップＣ２で、以前に到着したものと同じで
あるのかどうかが判断される。同じでなければ、ステッ
プＣ３で、経路設定メツセージを送出する。同しであれ
ば、ステップＣ４で、キャンセルメツセージを送出する
。
次に、中継ノード処理要領について、第８図を用いて説
明する。まず、入ってきたメツセージが探索メツセージ
かどうかが判定され（ステップＤ１）、もし探索メツセ
ージである場合は、ステップＤ２で、探索メツセージ処
理（第５図参照）を施す。もし、探索メツセージでない
場合は、経路設定メツセージかどうかが判定され（ステ
ップＤ３）、もし経路設定メツセージである場合は、ス
テップＤ４で、経路設定メツセージ処理（第５図参照）
を施す。また、経路設定メツセージでない場合は、キャ
ンセルメツセージであるかどうかが判定され（ステップ
Ｄ５）、もしキャンセルメツセージである場合は、ステ
ップＤ６で、キャンセルメツセージ処理（第５図参照）
を施す。
次に例えば、本実施例のネットワークにおいて、第９図
に示すように、リンク２′が障害を起こしたため、ノー
ドＩｓ、１Ｒ間に経路を設定する場合について説明する
と、次のようになる。まず、ノード１Ｓからこれに接続
されているリンクへ探索メツセージを送出する。このと
き、この探索メツセージの伝播中に途中のノード１で、
それ以上メツセージを伝播できなくなると、逆方向にキ
ャンセルメツセージを送出して、探索メツセージによっ
て確保されているパスを解放する。
かかるパスの解放態様は次のとおりである。
まず、探索メツセージの伝播中に途中のノード１で、こ
れ以上先にリンクがないからメツセージをこれ以上先に
送れない場合は、逆方向にキャンセルメツセージ（キャ
ンセルメツセージ■）を送出して、探索メツセージによ
って確保されているパスを解放する。
さらに、探索メツセージの伝播中に途中のノード１で、
空き回線が確保できなくなると、逆方向にキャンセルメ
ツセージ（キャンセルメツセージ■）を送出して、探索
メツセージによって確保されているパスを解放する。
また、探索メツセージの伝播中に通過ノード数が所定値
以上になると、逆方向にキャンセルメツセージ（キャン
セルメツセージ■）を送出して、探索メツセージによっ
て確保されているパスを解放する。
さらに、探索メツセージの伝播中に途中のノード１にお
いて、同一メツセージが先に到着している場合に、逆方
向にキャンセルメツセージ（キャンセルメツセージ■）
を送出して、探索メツセージによって確保されているパ
スを解放するのである。
ところで、キャンセルメツセージを受け取ったノード１
（例えばＬＭ）では、探索メツセージを送出した全ての
リンク２からのキャンセルメツセージ（キャンセルメツ
セージ■、■、■）が送られてきたら、探索メツセージ
が送られてきた方向（ノード１Ｓ側）にキャンセルメツ
セージ（キャンセルメツセージ■）を送出する。
次に、本実施例のネットワークにおいて、第１０図に示
すように、ノード１′が障害を起こしたため、このノー
ド１′につながっているノード１Ｓ、Ｉｓから異なった
探索メツセージＩ、ＩＩが出された場合について説明す
ると、次のようになる。
まず、各ノード１Ｓからこれに接続されているリンクへ
探索メツセージＩ、ＩＩがそれぞれ送出される。
そして、今、探索メツセージ■に着目すると、この探索
メツセージ■の伝播中に途中のノード１（例えばＩＮ）
で、異なる経路の探索メツセージ■が既に通過している
場合は、あとから来た探索メツセージ■をこのノーＦＩ
Ｎ内で待機させ、先に通った探索メツセージＩにより確
保されているパスの設定または解放が行なわれたら、待
たせておいた探索メツセージ■をこのノードＩＮから取
り出して送出することか行なわれるのである。
さらに、上記のように探索メツセージ■の伝播中に途中
のノードＩＮで、異なる経路の探索メツセージ■が既に
通過している場合には、あとから来た探索メツセージ■
をこのノーＦＩＮ内のメツセージ記憶部１４で待機させ
るほか、この探索メツセージ■を送ってきたノード１Ｓ
に対し待ちの状態であること（待ちメツセージ）を通知
する。
また、探索メツセージ■の伝播中に途中のノードＩＮで
、異なる経路の探索メツセージ■が既に通過している場
合には、あとから来た探索メツセージ■をこのノードＩ
Ｎ内で待機させる時間を制限し、指定した時間が経過す
ると、キャンセルメツセージをノード１Ｓへ送出して、
あとから来た探索メツセージ■をキャンセルする。この
とき、経過時間の測定は、メツセージが待っているノー
ドＩＮで行なうか、障害を検出したノード１ｓで行なう
。
なお、更に多く種類の異なった探索メツセージをノーＦ
ＩＮ内で待機させておく場合は、待たせておいたメツセ
ージを優先順似顔あるいは先着順に送出することもでき
る。
［発明の効果］ 以上詳述したように、第１の発明にかかるネットワーク
経路設定方式によれば、探索メツセージの伝播中に途中
のノードで、それ以上メツセージを伝播できなくなると
、逆方向にキャンセルメツセージを送出して、この探索
メツセージによって確保されているパスを解放すること
が行なわれるので、ノードでの分散処理によって、セン
タ局に処理が集中することがなくなり、更にキャンセル
メツセージによって探索メツセージにより確保されてい
て使用されないパスを解放することができるため、ネッ
トワークの有効利用が可能になる利点がある。
また、第２の発明にかかるネットワーク経路設定方式に
よれば、探索メツセージの伝播中に途中のノートで、異
なる経路の探索メツセージが既に通過している場合は、
あとから来たメツセージをこのノード内で待機させ、先
に通ったメツセージにより確保されているパスの設定ま
たは解放が行なわれたら、待たせておいたメツセージを
このノードから取り出して送出することか行なわれるの
で、同時に複数の経路設定要求があった場合でも、十分
に対応できる利点がある。
【図面の簡単な説明】
第１図は第１の発明にかかる原理説明図、第２図は第２
の発明にかかる原理説明図、第３図は本発明の一実施例
を示すネットワーク構成図、 第４図はノードの機能ブロック図、 第５〜８図はいずれも本発明の一実施例にかかる概略動
作を説明するためのフローチャート、第９，１０図はそ
れぞれ本発明の一実施例の作用説明図、 第１１１図は従来例のネットワーク構成図である。 図において、 １．１　’、ＬＭ、ＩＮ、１Ｒ，Ｉｓはノード、２．２
′はリンク、 １１は通信制御部、 １２はメツセージ解析部、 １３はメツセージ処理部、 １４はメツセージ記憶部、 １５はタイマ、 １６はメツセージ送出部である。

Claims (11)

    【特許請求の範囲】
  1. （１）リンク（２）で接続される複数のノード（１）を
    有するネットワークにおいて、あるノード（１Ｓ）から
    経路の探索メッセージをフラッディング方式により、送
    出し、該経路の他端に位置するノード（１Ｒ）に到達す
    ると、確認メッセージを送り返すことにより、経路を設
    定するネットワーク経路設定方式において、 該探索メッセージの伝播中に途中のノード（１）で、そ
    れ以上メッセージを伝播できなくなると、逆方向にキャ
    ンセルメッセージを送出して、該探索メッセージによっ
    て確保されているパスを解放することを 特徴とする、ネットワーク経路設定方式。
  2. （２）該キャンセルメッセージを受け取ったノード（１
    ）では、該探索メッセージを送出した全てのリンク（２
    ）からのキャンセルメッセージが送られてきたら、該探
    索メッセージが送られてきた方向にキャンセルメッセー
    ジを送出することを特徴とする、請求項１記載のネット
    ワーク経路設定方式。
  3. （３）該探索メッセージの伝播中に途中のノード（１）
    で、空き回線が確保できなくなると、逆方向にキャンセ
    ルメッセージを送出して、該探索メッセージによって確
    保されているパスを解放することを特徴とする、請求項
    １記載のネットワーク経路設定方式。
  4. （４）該探索メッセージの伝播中に通過ノード数が所定
    値以上になると、逆方向にキャンセルメッセージを送出
    して、該探索メッセージによって確保されているパスを
    解放することを特徴とする、請求項１記載のネットワー
    ク経路設定方式。
  5. （５）該探索メッセージの伝播中に途中のノード（１）
    において、同一メッセージが先に到着している場合に、
    逆方向にキャンセルメッセージを送出して、該探索メッ
    セージによって確保されているパスを解放することを特
    徴とする、請求項１記載のネットワーク経路設定方式。
  6. （６）リンク（２）で接続される複数のノード（１）を
    有するネットワークにおいて、あるノード（１）から経
    路の探索メッセージをフラッディング方式により、送出
    し、該経路の他端に位置するノード（１）に到達すると
    、確認メッセージを送り返すことにより、経路を設定す
    るネットワーク経路設定方式において、 該探索メッセージの伝播中に途中のノード（１）で、異
    なる経路の探索メッセージが既に通過している場合は、
    あとから来たメッセージを該ノード（１）内で待機させ
    、先に通ったメッセージにより確保されているパスの設
    定または解放が行なわれたら、待たせておいたメッセー
    ジを該ノード（１）から取り出して送出することを 特徴とする、ネットワーク経路設定方式。
  7. （７）該探索メッセージの伝播中に途中のノード（１）
    で、異なる経路の探索メッセージが既に通過している場
    合に、あとから来たメッセージを該ノード（１）内で待
    機させるとともに、このメッセージを送ってきたノード
    （１）に対し待ちの状態であることを通知することを特
    徴とする、請求項６記載のネットワーク経路設定方式。
  8. （８）該探索メッセージの伝播中に途中のノード（１）
    で、異なる経路の探索メッセージが既に通過している場
    合に、あとから来たメッセージを該ノード（１）内で待
    機させる時間を制限し、指定した時間が経過すると、あ
    とから来たメッセージをキャンセルすることを特徴とす
    る、請求項６記載のネットワーク経路設定方式。
  9. （９）経過時間の測定を、メッセージが待っているノー
    ド（１）で行なうことを特徴とする、請求項８記載のネ
    ットワーク経路設定方式。
  10. （１０）経過時間の測定を、障害を検出したノード（１
    ）で行なうことを特徴とする、請求項８記載のネットワ
    ーク経路設定方式。
  11. （１１）該探索メッセージの伝播中に途中のノード（１
    ）で、異なる経路の探索メッセージが既に通過している
    場合は、あとから来たメッセージを順次該ノード（１）
    内で待機させ、先に通ったメッセージにより確保されて
    いるパスの設定または解放が行なわれたら、待たせてお
    いたメッセージを優先順位順に該ノード（１）から取り
    出して送出することを特徴とする、請求項６記載のネッ
    トワーク経路設定方式。
JP16876090A 1990-06-27 1990-06-27 ノードにおけるネットワーク経路設定方式 Expired - Fee Related JP2875598B2 (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
JP16876090A JP2875598B2 (ja) 1990-06-27 1990-06-27 ノードにおけるネットワーク経路設定方式
CA002045317A CA2045317C (en) 1990-06-27 1991-06-24 Communication system using establishing network route
US07/720,916 US5604868A (en) 1990-06-27 1991-06-25 Communication system using establishing network route
EP91110672A EP0464680B1 (en) 1990-06-27 1991-06-27 Communication system using route setup procedure
DE69133470T DE69133470T2 (de) 1990-06-27 1991-06-27 Kommunikationssystem mit Prozedur zum Verbindungsaufbau

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP16876090A JP2875598B2 (ja) 1990-06-27 1990-06-27 ノードにおけるネットワーク経路設定方式

Publications (2)

Publication Number Publication Date
JPH0457428A true JPH0457428A (ja) 1992-02-25
JP2875598B2 JP2875598B2 (ja) 1999-03-31

Family

ID=15873930

Family Applications (1)

Application Number Title Priority Date Filing Date
JP16876090A Expired - Fee Related JP2875598B2 (ja) 1990-06-27 1990-06-27 ノードにおけるネットワーク経路設定方式

Country Status (5)

Country Link
US (1) US5604868A (ja)
EP (1) EP0464680B1 (ja)
JP (1) JP2875598B2 (ja)
CA (1) CA2045317C (ja)
DE (1) DE69133470T2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2012169791A (ja) * 2011-02-10 2012-09-06 Fujitsu Ltd 経路生成方法、中継装置、および経路生成プログラム

Families Citing this family (62)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7174352B2 (en) 1993-06-03 2007-02-06 Network Appliance, Inc. File system image transfer
US6138126A (en) * 1995-05-31 2000-10-24 Network Appliance, Inc. Method for allocating files in a file system integrated with a raid disk sub-system
US6604118B2 (en) 1998-07-31 2003-08-05 Network Appliance, Inc. File system image transfer
US5694546A (en) 1994-05-31 1997-12-02 Reisman; Richard R. System for automatic unattended electronic information transport between a server and a client by a vendor provided transport software with a manifest list
US5835005A (en) * 1994-07-13 1998-11-10 Omron Corporation Power-line data transmission method and system utilizing relay stations
US5867666A (en) 1994-12-29 1999-02-02 Cisco Systems, Inc. Virtual interfaces with dynamic binding
DE19528563C2 (de) * 1995-08-03 1997-11-06 Siemens Ag Verfahren zur Bewertung von mindestens zwei mehrteiligen Kommunikationsverbindungen zwischen zwei Kommunikationspartnern in einem Mehrknotennetzwerk
US6097718A (en) 1996-01-02 2000-08-01 Cisco Technology, Inc. Snapshot routing with route aging
US6147996A (en) 1995-08-04 2000-11-14 Cisco Technology, Inc. Pipelined multiple issue packet switch
US6917966B1 (en) 1995-09-29 2005-07-12 Cisco Technology, Inc. Enhanced network services using a subnetwork of communicating processors
US7246148B1 (en) 1995-09-29 2007-07-17 Cisco Technology, Inc. Enhanced network services using a subnetwork of communicating processors
US6182224B1 (en) 1995-09-29 2001-01-30 Cisco Systems, Inc. Enhanced network services using a subnetwork of communicating processors
US6091725A (en) 1995-12-29 2000-07-18 Cisco Systems, Inc. Method for traffic management, traffic prioritization, access control, and packet forwarding in a datagram computer network
US6035105A (en) 1996-01-02 2000-03-07 Cisco Technology, Inc. Multiple VLAN architecture system
US5870564A (en) * 1996-03-01 1999-02-09 Novell, Inc. Near-optimal path apparatus and method
US6308148B1 (en) 1996-05-28 2001-10-23 Cisco Technology, Inc. Network flow data export
US6243667B1 (en) 1996-05-28 2001-06-05 Cisco Systems, Inc. Network flow switching and flow data export
US6212182B1 (en) 1996-06-27 2001-04-03 Cisco Technology, Inc. Combined unicast and multicast scheduling
US6434120B1 (en) 1998-08-25 2002-08-13 Cisco Technology, Inc. Autosensing LMI protocols in frame relay networks
GB9616801D0 (en) * 1996-08-09 1996-09-25 Madge Networks Ltd Data communication network
DE69738175T2 (de) 1996-08-27 2008-01-31 Nippon Telegraph And Telephone Corp. Verbindungsübertragungsnetzwerk
US6067572A (en) * 1996-11-07 2000-05-23 Novell, Inc. Extrinsically influenced near-optimal path apparatus and method
KR100217719B1 (ko) * 1996-11-29 1999-09-01 윤종용 격자형 통신망 시스템에 있어서 통화경로 존재여부 계산방법 및 시스템
US6748446B2 (en) * 1996-11-29 2004-06-08 Canon Kabushiki Kaisha Communication method and apparatus with modification of routing path by intermediate relay apparatus
US6304546B1 (en) 1996-12-19 2001-10-16 Cisco Technology, Inc. End-to-end bidirectional keep-alive using virtual circuits
US6122272A (en) 1997-05-23 2000-09-19 Cisco Technology, Inc. Call size feedback on PNNI operation
US6356530B1 (en) 1997-05-23 2002-03-12 Cisco Technology, Inc. Next hop selection in ATM networks
US6862284B1 (en) 1997-06-17 2005-03-01 Cisco Technology, Inc. Format for automatic generation of unique ATM addresses used for PNNI
US6421349B1 (en) * 1997-07-11 2002-07-16 Telecommunications Research Laboratories Distributed preconfiguration of spare capacity in closed paths for network restoration
US6078590A (en) 1997-07-14 2000-06-20 Cisco Technology, Inc. Hierarchical routing knowledge for multicast packet routing
US6330599B1 (en) 1997-08-05 2001-12-11 Cisco Technology, Inc. Virtual interfaces with dynamic binding
US6377543B1 (en) 1997-08-13 2002-04-23 Telecommunications Research Laboratories Path restoration of networks
US6157641A (en) 1997-08-22 2000-12-05 Cisco Technology, Inc. Multiprotocol packet recognition and switching
US6512766B2 (en) 1997-08-22 2003-01-28 Cisco Systems, Inc. Enhanced internet packet routing lookup
US6212183B1 (en) 1997-08-22 2001-04-03 Cisco Technology, Inc. Multiple parallel packet routing lookup
US6343072B1 (en) 1997-10-01 2002-01-29 Cisco Technology, Inc. Single-chip architecture for shared-memory router
US7570583B2 (en) * 1997-12-05 2009-08-04 Cisco Technology, Inc. Extending SONET/SDH automatic protection switching
US6424649B1 (en) 1997-12-31 2002-07-23 Cisco Technology, Inc. Synchronous pipelined switch using serial transmission
US6111877A (en) 1997-12-31 2000-08-29 Cisco Technology, Inc. Load sharing across flows
US6457130B2 (en) 1998-03-03 2002-09-24 Network Appliance, Inc. File access control in a multi-protocol file server
US6317844B1 (en) 1998-03-10 2001-11-13 Network Appliance, Inc. File server storage arrangement
US6853638B2 (en) * 1998-04-01 2005-02-08 Cisco Technology, Inc. Route/service processor scalability via flow-based distribution of traffic
US6920112B1 (en) 1998-06-29 2005-07-19 Cisco Technology, Inc. Sampling packets for network monitoring
US6370121B1 (en) 1998-06-29 2002-04-09 Cisco Technology, Inc. Method and system for shortcut trunking of LAN bridges
US6377577B1 (en) 1998-06-30 2002-04-23 Cisco Technology, Inc. Access control list processing in hardware
US6308219B1 (en) 1998-07-31 2001-10-23 Cisco Technology, Inc. Routing table lookup implemented using M-trie having nodes duplicated in multiple memory banks
US6182147B1 (en) 1998-07-31 2001-01-30 Cisco Technology, Inc. Multicast group routing using unidirectional links
US6389506B1 (en) 1998-08-07 2002-05-14 Cisco Technology, Inc. Block mask ternary cam
US6101115A (en) 1998-08-07 2000-08-08 Cisco Technology, Inc. CAM match line precharge
US6404734B1 (en) 1998-10-06 2002-06-11 Telecommuncations Research Laboratories Scalable network restoration device
US6771642B1 (en) 1999-01-08 2004-08-03 Cisco Technology, Inc. Method and apparatus for scheduling packets in a packet switch
US7065762B1 (en) 1999-03-22 2006-06-20 Cisco Technology, Inc. Method, apparatus and computer program product for borrowed-virtual-time scheduling
US6757791B1 (en) 1999-03-30 2004-06-29 Cisco Technology, Inc. Method and apparatus for reordering packet data units in storage queues for reading and writing memory
US6603772B1 (en) 1999-03-31 2003-08-05 Cisco Technology, Inc. Multicast routing with multicast virtual output queues and shortest queue first allocation
US6760331B1 (en) 1999-03-31 2004-07-06 Cisco Technology, Inc. Multicast routing with nearest queue first allocation and dynamic and static vector quantization
US7320017B1 (en) * 2000-09-06 2008-01-15 Cisco Technology, Inc. Media gateway adapter
US7747757B2 (en) * 2000-11-17 2010-06-29 Computer Associates Think, Inc. Distributed network query
US6618388B2 (en) 2001-01-05 2003-09-09 Extreme Networks Method and system for VMAN protocol
US7076543B1 (en) 2002-02-13 2006-07-11 Cisco Technology, Inc. Method and apparatus for collecting, aggregating and monitoring network management information
US8611919B2 (en) 2002-05-23 2013-12-17 Wounder Gmbh., Llc System, method, and computer program product for providing location based services and mobile e-commerce
US10489449B2 (en) 2002-05-23 2019-11-26 Gula Consulting Limited Liability Company Computer accepting voice input and/or generating audible output
US7801021B1 (en) * 2002-07-01 2010-09-21 Cisco Technology, Inc. Generic routing encapsulation tunnel keepalives

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3155775A (en) * 1961-03-28 1964-11-03 Bell Telephone Labor Inc Alternate route trunk selection
US4399531A (en) * 1980-09-29 1983-08-16 Rockwell International Corporation Distributed digital data communications network
US4920529A (en) * 1987-02-27 1990-04-24 Hitachi, Ltd. Network control method and apparatus therefor
US4914571A (en) * 1987-06-15 1990-04-03 International Business Machines Corporation Locating resources in computer networks
CA1291549C (en) * 1987-11-06 1991-10-29 Wayne D. Grover Method and apparatus for self-healing and self-provisioning networks
US4939728A (en) * 1987-11-10 1990-07-03 Echelon Systems Corp. Network and intelligent cell for providing sensing bidirectional communications and control
US4873517A (en) * 1988-06-23 1989-10-10 International Business Machines Corporation Method for selecting least weight end node to end node route in a data communications network
US4912656A (en) * 1988-09-26 1990-03-27 Harris Corporation Adaptive link assignment for a dynamic communication network
US5101451A (en) * 1988-12-29 1992-03-31 At&T Bell Laboratories Real-time network routing
JP2837182B2 (ja) * 1989-08-04 1998-12-14 富士通株式会社 セルデータの伝送方法、送信要求処理方法及びスイッチ
US5245607A (en) * 1990-03-05 1993-09-14 At&T Bell Laboratories Data network message broadcast arrangement
US5282270A (en) * 1990-06-06 1994-01-25 Apple Computer, Inc. Network device location using multicast
JPH05167585A (ja) * 1991-12-16 1993-07-02 Nec Corp ローカルエリアネットワーク同報フレーム通信装置及び方法

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2012169791A (ja) * 2011-02-10 2012-09-06 Fujitsu Ltd 経路生成方法、中継装置、および経路生成プログラム

Also Published As

Publication number Publication date
EP0464680A3 (ja) 1995-03-01
CA2045317C (en) 1999-02-16
EP0464680A2 (en) 1992-01-08
US5604868A (en) 1997-02-18
DE69133470D1 (de) 2005-07-21
EP0464680B1 (en) 2005-06-15
DE69133470T2 (de) 2006-05-11
JP2875598B2 (ja) 1999-03-31
CA2045317A1 (en) 1991-12-28

Similar Documents

Publication Publication Date Title
JPH0457428A (ja) ノードにおけるネットワーク経路設定方式
US6282669B1 (en) Ethernet communication redundancy method
US9059961B2 (en) Creation and maintenance of self-organizing communication orbits in distributed networks
US5146452A (en) Method and apparatus for rapidly restoring a communication network
Kimbleton et al. Computer communication networks: Approaches, objectives, and performance considerations
US5862125A (en) Automated restoration of unrestored link and nodal failures
JPS59144242A (ja) リング通信システムにおいて局の配列を識別する方法
JPH02142237A (ja) ネットワーク障害回復方式
JPH0936910A (ja) パケット通信ネットワークにおける経路指定の管理
US20020147823A1 (en) Computer network system
US5528594A (en) Method and system for implementing sub-tokens on a token ring network
JPH11507487A (ja) 予備容量の実質的に同時の両方向リクエストを解決するためのシステム及び方法
JPH07202910A (ja) データ・パケットを送信する方法およびデータ処理システム
US7254329B2 (en) Method and system for multi-initiator support to streaming devices in a fibre channel network
WO1997024886A1 (en) Communications system and method providing optimal restoraton of failed paths
US6370654B1 (en) Method and apparatus to extend the fault-tolerant abilities of a node into a network
US20070133395A1 (en) Avoiding deadlocks in performing failovers in communications environments
US6556538B1 (en) Integration of a centralized network restoration system with a distributed network restoration system
CN104125301A (zh) 多线路数据传输方法
CN115643174A (zh) 一种流量编排方法、装置及其介质
AU718251B2 (en) Transmission line duplexing processing method and apparatus thereof, and recording medium for recording its processing procedure
JP2025526905A5 (ja)
CN116667907A (zh) 星间路由容错方法、装置、电子设备和存储介质
JPH0496447A (ja) バーチャルパス切り替え装置
Hargaden et al. Functions and operations of CEBus routers

Legal Events

Date Code Title Description
LAPS Cancellation because of no payment of annual fees