JPH08237245A - 双方向メッシュ網 - Google Patents
双方向メッシュ網Info
- Publication number
- JPH08237245A JPH08237245A JP7331276A JP33127695A JPH08237245A JP H08237245 A JPH08237245 A JP H08237245A JP 7331276 A JP7331276 A JP 7331276A JP 33127695 A JP33127695 A JP 33127695A JP H08237245 A JPH08237245 A JP H08237245A
- Authority
- JP
- Japan
- Prior art keywords
- node
- communication
- packet
- performance parameter
- nodes
- 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.)
- Withdrawn
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
- H04L45/02—Topology update or discovery
- H04L45/06—Deflection routing, e.g. hot-potato routing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
- H04L12/2852—Metropolitan area networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
- H04L12/46—Interconnection of networks
- H04L12/4637—Interconnected ring systems
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Small-Scale Networks (AREA)
Abstract
(57)【要約】
【課題】 双方向メッシュ網（bidirectional mesh net
work、ＭＳＮ）、或は、双方向ＭＳＮ（bi−ＭＳＮ）と
も称される通信網が開示される。 【解決手段】 この双方向ＭＳＮは、おのおのが双方向
リンクによって互いに相互接続された複数のノードから
構成される複数の第一の通信ループ（水平ループ）を含
む。この双方向ＭＳＮは、さらに、おのおのが双方向リ
ンクによって互いに相互接続された複数のノードから構
成される複数の第二の通信ループ（垂直ループ）を含
む。各第二の通信ループは、各第一の通信ループに、第
二の通信ループと第一の通信ループの両方に共通なノー
ドの所で接続される。この共通ノード（及び、事実、こ
の双方向ＭＳＮ内の各ノード）は、パケットを第一の通
信ループから第二の通信ループに、或はこの逆方向に、
これらパケット内に含まれる宛先アドレスの関数として
転送するためのスイッチを含む。
work、ＭＳＮ）、或は、双方向ＭＳＮ（bi−ＭＳＮ）と
も称される通信網が開示される。 【解決手段】 この双方向ＭＳＮは、おのおのが双方向
リンクによって互いに相互接続された複数のノードから
構成される複数の第一の通信ループ（水平ループ）を含
む。この双方向ＭＳＮは、さらに、おのおのが双方向リ
ンクによって互いに相互接続された複数のノードから構
成される複数の第二の通信ループ（垂直ループ）を含
む。各第二の通信ループは、各第一の通信ループに、第
二の通信ループと第一の通信ループの両方に共通なノー
ドの所で接続される。この共通ノード（及び、事実、こ
の双方向ＭＳＮ内の各ノード）は、パケットを第一の通
信ループから第二の通信ループに、或はこの逆方向に、
これらパケット内に含まれる宛先アドレスの関数として
転送するためのスイッチを含む。
Description
【０００１】
【産業上の利用分野】本発明は、一般的には、通信網、
より詳細には、高いチャネル／帯域幅容量、高い効率、
故障耐性、及び網生存能力を持つ通信網に関する。
より詳細には、高いチャネル／帯域幅容量、高い効率、
故障耐性、及び網生存能力を持つ通信網に関する。
【０００２】
【従来の技術】通信サービスにおけるはてなき要求の結
果として、網技術は、以前は想像もしなかった新たな網
アーキテクチュア、及び通信メディアの混合の方向に向
かっている。現在、近い将来の実現を目指して、光ファ
イバ、同軸ケーブル、及びより対線を使用しての、音
声、対話ビデオ、及びパーソナル通信サービスを含む広
帯域マルチメディアサービスが計画されている。複数の
電話会社によって裁定されつつある何ビリオンドルもの
情報ハイウエイ契約がこの現実を立証するものである。
ただし、これら広帯域マルチメディアサービスは、高い
チャネル／帯域幅容量、高い効率、故障耐性、及び網生
存能力を有する通信網を要求するリアルタイムサービス
である。
果として、網技術は、以前は想像もしなかった新たな網
アーキテクチュア、及び通信メディアの混合の方向に向
かっている。現在、近い将来の実現を目指して、光ファ
イバ、同軸ケーブル、及びより対線を使用しての、音
声、対話ビデオ、及びパーソナル通信サービスを含む広
帯域マルチメディアサービスが計画されている。複数の
電話会社によって裁定されつつある何ビリオンドルもの
情報ハイウエイ契約がこの現実を立証するものである。
ただし、これら広帯域マルチメディアサービスは、高い
チャネル／帯域幅容量、高い効率、故障耐性、及び網生
存能力を有する通信網を要求するリアルタイムサービス
である。
【０００３】ローカルエリア網（ＬＡＮ）もマルチメテ
ィアに向かうこの傾向の影響を受けている。性能の理由
から、広帯域マルチメディア網（つまり、広帯域マルチ
メディアサービスをサポートする通信網）に接続するＬ
ＡＮは、非常に高速であることを要求される。従って、
市場は、典型的な１０Ｍｂｐｓ（メガビット／秒）から
１００Ｍｂｐｓ（或はそれ以上の）交換ＡＴＭ（非同期
転送ノード）或は同程度に高速なイサーネットに移行し
つつある。これに関しては、例えば、“What'sthe Succ
essor to 10-Mbit/s Ethernet? ”OEM Magazine、pp. 1
2-13、 May 1994 を参照されたい。ただし、マルチメデ
ィアサービスをサポートするためには、単に、ＬＡＮの
速度を増加するのでは充分でない。実際、ＬＡＮには、
リアルタイムにてデータを効率的に転送する能力に加え
て、知能及び生存能力等の通信網属性を有することが要
求される。
ィアに向かうこの傾向の影響を受けている。性能の理由
から、広帯域マルチメディア網（つまり、広帯域マルチ
メディアサービスをサポートする通信網）に接続するＬ
ＡＮは、非常に高速であることを要求される。従って、
市場は、典型的な１０Ｍｂｐｓ（メガビット／秒）から
１００Ｍｂｐｓ（或はそれ以上の）交換ＡＴＭ（非同期
転送ノード）或は同程度に高速なイサーネットに移行し
つつある。これに関しては、例えば、“What'sthe Succ
essor to 10-Mbit/s Ethernet? ”OEM Magazine、pp. 1
2-13、 May 1994 を参照されたい。ただし、マルチメデ
ィアサービスをサポートするためには、単に、ＬＡＮの
速度を増加するのでは充分でない。実際、ＬＡＮには、
リアルタイムにてデータを効率的に転送する能力に加え
て、知能及び生存能力等の通信網属性を有することが要
求される。
【０００４】ループアーキテクチュアを持つマンハッタ
ンストリート網 マンハッタンファイバデータ分散インタフェース（ルー
プアーキテクチュアを持つマンハッタンストリート網
（ＭＳＮ）、或は単に、マンハッタン網とも称される）
は、ローカルエリア網と使用されるために考案された網
である。このマンハッタン網については、多くの公にさ
れている資料、例えば、S.V. Kartalopoulos、 “The Ma
nhattan Fiber Data Distributed Interface Network A
rchitecture ”、 Proceedings of the Globecom '90 Co
nference、 San Diego、 Dec.2-5、 1990、 pp.141-145；N.
F. Maxemchuk、 “ Regular Mesh Topologies in Local
andMetropolitan Area Networks”、AT&T Bell Laborat
ories Technical Journal、Sept 1985 ；及び合衆国特許
第５，２８９，４６７号を参照すること。
ンストリート網 マンハッタンファイバデータ分散インタフェース（ルー
プアーキテクチュアを持つマンハッタンストリート網
（ＭＳＮ）、或は単に、マンハッタン網とも称される）
は、ローカルエリア網と使用されるために考案された網
である。このマンハッタン網については、多くの公にさ
れている資料、例えば、S.V. Kartalopoulos、 “The Ma
nhattan Fiber Data Distributed Interface Network A
rchitecture ”、 Proceedings of the Globecom '90 Co
nference、 San Diego、 Dec.2-5、 1990、 pp.141-145；N.
F. Maxemchuk、 “ Regular Mesh Topologies in Local
andMetropolitan Area Networks”、AT&T Bell Laborat
ories Technical Journal、Sept 1985 ；及び合衆国特許
第５，２８９，４６７号を参照すること。
【０００５】図１は一例としての４×４（４ノード×４
ノード）マンハッタン網１０２を示す。このマンハッタ
ン網１０２は、１６個のノード１０８を含むが、ここ
で、ここのノード１０８は、その（行、列）によって個
々に識別される。マンハッタン網１０２は、セットの水
平方向の平行ループ１０４と、セットの垂直方向の平行
ループ１０６を含むメッシュ網である。水平ループ１０
４は、垂直ループとノード１０８の所で交差し、これと
接続される。各ノード１０８は、二つの入力ポートと二
つの出力ポートを含む。各ノード１０８は、その任意の
入力ポートからデータパケットを受信し、データパケッ
トをその任意の出力ポートを介して送信する能力を持
つ。こうして、各ノード１０８は、データパケットを水
平ループ１０４から垂直ループ１０６に、或はこの逆方
向に、輸送する能力を持つ。
ノード）マンハッタン網１０２を示す。このマンハッタ
ン網１０２は、１６個のノード１０８を含むが、ここ
で、ここのノード１０８は、その（行、列）によって個
々に識別される。マンハッタン網１０２は、セットの水
平方向の平行ループ１０４と、セットの垂直方向の平行
ループ１０６を含むメッシュ網である。水平ループ１０
４は、垂直ループとノード１０８の所で交差し、これと
接続される。各ノード１０８は、二つの入力ポートと二
つの出力ポートを含む。各ノード１０８は、その任意の
入力ポートからデータパケットを受信し、データパケッ
トをその任意の出力ポートを介して送信する能力を持
つ。こうして、各ノード１０８は、データパケットを水
平ループ１０４から垂直ループ１０６に、或はこの逆方
向に、輸送する能力を持つ。
【０００６】マンハッタン網１０２は分散制御を持つ。
より具体的には、マンハッタン網１０２内の各ノード
は、パケットがどのようにルートされるべきか自律的に
決定する能力（つまり、パケットのルーティング能力）
を持つ。このために、マンハッタン網１０２は、パケッ
トを発信ノードから宛先ノードに、複数の潜在的に利用
可能な異なる経路を介して輸送するのに適する。ただ
し、マンハッタン網１０２内のループ１０４、１０６は
全て単方向であることに注意する。つまり、水平ループ
１０４内のデータの流れは、西から東（或はこの反対）
であり、垂直ループ１０６内のデータの流れは、北から
南（或はこの反対）である。（ここでは、北、南、東、
及び西の方向の約束は、説明の目的としてのみ使用され
ることに注意する。）
より具体的には、マンハッタン網１０２内の各ノード
は、パケットがどのようにルートされるべきか自律的に
決定する能力（つまり、パケットのルーティング能力）
を持つ。このために、マンハッタン網１０２は、パケッ
トを発信ノードから宛先ノードに、複数の潜在的に利用
可能な異なる経路を介して輸送するのに適する。ただ
し、マンハッタン網１０２内のループ１０４、１０６は
全て単方向であることに注意する。つまり、水平ループ
１０４内のデータの流れは、西から東（或はこの反対）
であり、垂直ループ１０６内のデータの流れは、北から
南（或はこの反対）である。（ここでは、北、南、東、
及び西の方向の約束は、説明の目的としてのみ使用され
ることに注意する。）
【０００７】
【発明が解決しようとする課題】マンハッタン網は、ロ
ーカルエリア網内で、データ配達能力がリアルタイム輸
送よりも重要とされる状況下において、二つ或はそれ上
のノード間での高速データ伝送のために使用するのには
非常に適する。ただし、新たな広帯域マルチメディアサ
ービスは、現存の単方向データサービスに加えて、音声
及び対話ビデオ／データサービスを要求する。効率的な
音声及び対話ビデオ／データサービスは、リアルタイム
データ処理、及び、極端に短い伝播遅延を必要とする。
これらサービスは、（蓄積転送通信と対比して）リアル
タイム通信と称される。マンハッタン網は、その単方向
特性のために、常に、最も効率的なルートを通じてパケ
ットを配達することはできない。例えば、ノード（２、
３）がパケットをノード（２、２）に送る場合は、この
パケットは、ノード（２、２）と（２、３）が互いにす
ぐ隣りにあるのに、ノード（２、２）に到達するために
ノード（２、４）と（２、１）を含む水平ループを完全
に一回りしなければならない。マンハッタン網は常にパ
ケットを最も効率的なルートを通じて配達できないため
に、マンハッチン網を使用した場合、リアルタイム通信
を保証することができない。このために、マンハッタン
網は、広帯域マルチメディアサービスを充分にサポート
することができない。
ーカルエリア網内で、データ配達能力がリアルタイム輸
送よりも重要とされる状況下において、二つ或はそれ上
のノード間での高速データ伝送のために使用するのには
非常に適する。ただし、新たな広帯域マルチメディアサ
ービスは、現存の単方向データサービスに加えて、音声
及び対話ビデオ／データサービスを要求する。効率的な
音声及び対話ビデオ／データサービスは、リアルタイム
データ処理、及び、極端に短い伝播遅延を必要とする。
これらサービスは、（蓄積転送通信と対比して）リアル
タイム通信と称される。マンハッタン網は、その単方向
特性のために、常に、最も効率的なルートを通じてパケ
ットを配達することはできない。例えば、ノード（２、
３）がパケットをノード（２、２）に送る場合は、この
パケットは、ノード（２、２）と（２、３）が互いにす
ぐ隣りにあるのに、ノード（２、２）に到達するために
ノード（２、４）と（２、１）を含む水平ループを完全
に一回りしなければならない。マンハッタン網は常にパ
ケットを最も効率的なルートを通じて配達できないため
に、マンハッチン網を使用した場合、リアルタイム通信
を保証することができない。このために、マンハッタン
網は、広帯域マルチメディアサービスを充分にサポート
することができない。
【０００８】
【課題を解決するための手段】概説すると、本発明は、
双方向メッシュ網（ＭＳＮ）、或はbi- ＭＳＮとも称さ
れる通信網に関する。この双方向ＭＳＮは、おのおのが
双方向通信リンクによって互いに相互接続された複数の
ノードから構成される複数の第一の通信ループ（水平ル
ープ）を含む。この双方向ＭＳＮは、さらに、おのおの
が双方向通信リンクによって互いに相互接続された複数
のノードから構成される複数の第二の通信ループ（垂直
ループ）を含む。各第二の通信ループは、各第二の通信
ループに、この第二の通信ループと第一の通信ループの
両方に共通なノードの所で接続する。この共通ノード
（及び、事実、双方向ＭＳＮ内の各ノード）は、パケッ
トを第一の通信ループから第二の通信ループに、或はこ
の逆方向に、それらパケット内に含まれる宛先アドレス
の関数として転送するためのスイッチを含む。尚、“A
Global Muiti-Satellite Network”という発明の名称
の、StamatiosV. Kartalopoulosによる合衆国特許出
願、Attorney Docket No. S.V. Kartalopulos 7(1470.0
710000）全体がここに参照の目的で編入されるものであ
る。本発明の他の特徴及び長所、並びに、本発明の様々
な実施例の構造及び動作が、以下に詳細に付録の図面と
の関連で説明される。図面中、同一の参照番号は、同一
或は機能的に類似する要素を示す。
双方向メッシュ網（ＭＳＮ）、或はbi- ＭＳＮとも称さ
れる通信網に関する。この双方向ＭＳＮは、おのおのが
双方向通信リンクによって互いに相互接続された複数の
ノードから構成される複数の第一の通信ループ（水平ル
ープ）を含む。この双方向ＭＳＮは、さらに、おのおの
が双方向通信リンクによって互いに相互接続された複数
のノードから構成される複数の第二の通信ループ（垂直
ループ）を含む。各第二の通信ループは、各第二の通信
ループに、この第二の通信ループと第一の通信ループの
両方に共通なノードの所で接続する。この共通ノード
（及び、事実、双方向ＭＳＮ内の各ノード）は、パケッ
トを第一の通信ループから第二の通信ループに、或はこ
の逆方向に、それらパケット内に含まれる宛先アドレス
の関数として転送するためのスイッチを含む。尚、“A
Global Muiti-Satellite Network”という発明の名称
の、StamatiosV. Kartalopoulosによる合衆国特許出
願、Attorney Docket No. S.V. Kartalopulos 7(1470.0
710000）全体がここに参照の目的で編入されるものであ
る。本発明の他の特徴及び長所、並びに、本発明の様々
な実施例の構造及び動作が、以下に詳細に付録の図面と
の関連で説明される。図面中、同一の参照番号は、同一
或は機能的に類似する要素を示す。
【０００９】
１．本発明の概要 本発明は、双方向メッシュ網（bidirectional mesh net
work、ＭＳＮ）、或は双方向ＭＳＮとも称される通信網
に関する。後に示されるように、本発明の双方向ＭＳＮ
は、高いチャネル／帯域幅容量、高い効率、故障耐性、
及び網生存能力を持つ。このために、この双方向ＭＳＮ
は広帯域マルチメディアサービス（例えば、リアルタイ
ム通信）をサポートする能力を持つ。
work、ＭＳＮ）、或は双方向ＭＳＮとも称される通信網
に関する。後に示されるように、本発明の双方向ＭＳＮ
は、高いチャネル／帯域幅容量、高い効率、故障耐性、
及び網生存能力を持つ。このために、この双方向ＭＳＮ
は広帯域マルチメディアサービス（例えば、リアルタイ
ム通信）をサポートする能力を持つ。
【００１０】図２は本発明の一つの実施例によるＮ×Ｎ
双方向ＭＳＮ２０２を示す。図２の特定の実施例におい
ては、ＭとＮは、両方とも、４である。ただし、ＭとＮ
は、他の値を取ることができ、ＭがＮと同一である必要
もない。図２に示される双方向ＭＳＮ２０２は、１６個
のノード２０８を持ち、個々のノード２０８は、個別に
その（行と列）によって識別される。双方向ＭＳＮ２０
２内のこれらノード２０８は、遠隔的に、プログラムし
たり再構成することが可能であり、こうして、双方向２
０２を知能網とすることができる。双方向ＭＳＮ２０２
は、セットの水平方向の平行ループ２０４とセットの垂
直方向の平行ループ２０６を含むメッシュ網である。こ
こで使用される水平及び垂直という用語は、解説の目的
のものであり、また、好ましい実施例を示すものである
ことに注意する。互いに交差するループ２０４と２０６
は、９０度以外の角度だけ互いにオフセットされること
も可能である。また、ループ２０４は、互いに厳密に平
行である必要もない。同様に、ループ２０６も互いに厳
密に平行である必要はない。
双方向ＭＳＮ２０２を示す。図２の特定の実施例におい
ては、ＭとＮは、両方とも、４である。ただし、ＭとＮ
は、他の値を取ることができ、ＭがＮと同一である必要
もない。図２に示される双方向ＭＳＮ２０２は、１６個
のノード２０８を持ち、個々のノード２０８は、個別に
その（行と列）によって識別される。双方向ＭＳＮ２０
２内のこれらノード２０８は、遠隔的に、プログラムし
たり再構成することが可能であり、こうして、双方向２
０２を知能網とすることができる。双方向ＭＳＮ２０２
は、セットの水平方向の平行ループ２０４とセットの垂
直方向の平行ループ２０６を含むメッシュ網である。こ
こで使用される水平及び垂直という用語は、解説の目的
のものであり、また、好ましい実施例を示すものである
ことに注意する。互いに交差するループ２０４と２０６
は、９０度以外の角度だけ互いにオフセットされること
も可能である。また、ループ２０４は、互いに厳密に平
行である必要もない。同様に、ループ２０６も互いに厳
密に平行である必要はない。
【００１１】各ノード２０８は４つの入力ポートを含
み、これらは、北入力ポート、南入力ポート、東入力ポ
ート、及び西入力ポートと称される。同様に、各ノード
２０８は、北出力ポート、南出力ポート、東出力ポー
ト、及び西出力ポートと称される４つの出力ポートを含
む。これら入力ポート及び出力ポートの名前はそれらが
接続されたリンクを識別する。例えば、ノード（２、
１）を考えると、北入力及び出力ポートは、ノード
（１、１）の真南に位置するリンクに接続される（この
リンクはノード（２、１）をノード（１、１）に接続す
る。同様に、この西入力及び出力ポートはノード（２、
４）の真東に位置するリンクに接続される（このリンク
はノード（２、１）をノード（２、４）に接続す
る））。
み、これらは、北入力ポート、南入力ポート、東入力ポ
ート、及び西入力ポートと称される。同様に、各ノード
２０８は、北出力ポート、南出力ポート、東出力ポー
ト、及び西出力ポートと称される４つの出力ポートを含
む。これら入力ポート及び出力ポートの名前はそれらが
接続されたリンクを識別する。例えば、ノード（２、
１）を考えると、北入力及び出力ポートは、ノード
（１、１）の真南に位置するリンクに接続される（この
リンクはノード（２、１）をノード（１、１）に接続す
る。同様に、この西入力及び出力ポートはノード（２、
４）の真東に位置するリンクに接続される（このリンク
はノード（２、１）をノード（２、４）に接続す
る））。
【００１２】各ノード２０８は、その任意の入力ポート
からデータパケットを受信し、その任意の出力ポートを
介してデータパケットを送信する能力を持つ。本発明の
双方向ＭＳＮ２０２においては、ノード２０８を互いに
接続するこれらリンクは、双方向である。このために、
各ノード１０８は、水平方向ループ１０４から垂直方向
ループ１０６にデータパケットを任意の方向に伝送する
能力を持ち、この逆も可能である。ノード（２、３）が
ノード（２、２）にデータパケットを送信する例を考え
る。この双方向ＭＳＮ内においてはリンクは双方向であ
るために、このデータ伝送は単一のリンクを通じて行な
われる（つまり、ノード（２、３）がこのデータパケッ
トをその西出力ポートを介して送信し、ノード（２、
２）がこのパケットをその東入力ポートを介して受信す
る）。この双方向２０２は、分散制御を持つ。より具体
的には、双方向ＭＳＮ２０２内の各ノード２０８は、パ
ケットがどのようにルートされるべきかに関して自律的
な決定を行なう（つまり、パケットの自律的なルート決
定能力を持つ）。各ノード２０８は、以下に説明される
他の機能を自律的に遂行する。
からデータパケットを受信し、その任意の出力ポートを
介してデータパケットを送信する能力を持つ。本発明の
双方向ＭＳＮ２０２においては、ノード２０８を互いに
接続するこれらリンクは、双方向である。このために、
各ノード１０８は、水平方向ループ１０４から垂直方向
ループ１０６にデータパケットを任意の方向に伝送する
能力を持ち、この逆も可能である。ノード（２、３）が
ノード（２、２）にデータパケットを送信する例を考え
る。この双方向ＭＳＮ内においてはリンクは双方向であ
るために、このデータ伝送は単一のリンクを通じて行な
われる（つまり、ノード（２、３）がこのデータパケッ
トをその西出力ポートを介して送信し、ノード（２、
２）がこのパケットをその東入力ポートを介して受信す
る）。この双方向２０２は、分散制御を持つ。より具体
的には、双方向ＭＳＮ２０２内の各ノード２０８は、パ
ケットがどのようにルートされるべきかに関して自律的
な決定を行なう（つまり、パケットの自律的なルート決
定能力を持つ）。各ノード２０８は、以下に説明される
他の機能を自律的に遂行する。
【００１３】２．双方向メッシュ網の機能と特徴 以下の節においては双方向ＭＳＮ２０２の通信機能及び
通信特性について説明される。 ２．１ 網の効率 以下の節においては、パケット配達能力、網伝播遅延、
網渋滞、及びフロー制御について説明される。 ２．１．１ 双方向ＭＳＮ内でのパケット配達能力 この節においては、データパケットの配達能力が本発明
の双方向ＭＳＮにおいては異なるルートが利用できると
いう観点から考察される。比較の目的のために、最初
に、Ｎ×Ｎマンハッタン網について考える。このマンハ
ッタン網内における発信ノードと着信ノードの間の同一
のノードを二度訪れること無しに可能なチャネル当りの
ルートの総数は、おおむねＮ！（Ｎ−１）である。
通信特性について説明される。 ２．１ 網の効率 以下の節においては、パケット配達能力、網伝播遅延、
網渋滞、及びフロー制御について説明される。 ２．１．１ 双方向ＭＳＮ内でのパケット配達能力 この節においては、データパケットの配達能力が本発明
の双方向ＭＳＮにおいては異なるルートが利用できると
いう観点から考察される。比較の目的のために、最初
に、Ｎ×Ｎマンハッタン網について考える。このマンハ
ッタン網内における発信ノードと着信ノードの間の同一
のノードを二度訪れること無しに可能なチャネル当りの
ルートの総数は、おおむねＮ！（Ｎ−１）である。
【００１４】次に、Ｎ×Ｎ双方向ＭＳＮについて考え
る。双方向ＭＳＮが双方向であるために、可能なルート
の数は、Ｎが増加すると（マンハッタン網と比較して）
より急速に増加する。例えば、２×２双方向ＭＳＮの場
合、可能なルートの数は８であり、３×３双方向ＭＳＮ
の場合は、可能なルートの数は本質的には１７６である
と推定され、４×４双方向ＭＳＮの場合は、可能なルー
トの数は１５９２であると推定される。
る。双方向ＭＳＮが双方向であるために、可能なルート
の数は、Ｎが増加すると（マンハッタン網と比較して）
より急速に増加する。例えば、２×２双方向ＭＳＮの場
合、可能なルートの数は８であり、３×３双方向ＭＳＮ
の場合は、可能なルートの数は本質的には１７６である
と推定され、４×４双方向ＭＳＮの場合は、可能なルー
トの数は１５９２であると推定される。
【００１５】図３は、双方向ＭＳＮのルーティング能力
とマンハッタン網（図３において“ＭＳＮとして示され
る）のルーティング能力の比較を示す。縦軸は対数であ
ることに注意する。これから、双方向ＭＳＮ内のノード
の数が増加すると、双方向ＭＳＮの配達能力は、急速に
指数関数的に増加することがわかる。これらルートの幾
つかは畳み込み関数であり、通常の状況下においては、
最適ではないように見える。ただし、幾つかのノードが
故障を持つ大きな網内においては、これら（畳み込み関
数の）絡み合った複雑なルートがパケット配達能力に大
きな役割を果す。
とマンハッタン網（図３において“ＭＳＮとして示され
る）のルーティング能力の比較を示す。縦軸は対数であ
ることに注意する。これから、双方向ＭＳＮ内のノード
の数が増加すると、双方向ＭＳＮの配達能力は、急速に
指数関数的に増加することがわかる。これらルートの幾
つかは畳み込み関数であり、通常の状況下においては、
最適ではないように見える。ただし、幾つかのノードが
故障を持つ大きな網内においては、これら（畳み込み関
数の）絡み合った複雑なルートがパケット配達能力に大
きな役割を果す。
【００１６】２．１．２ 終端から終端までの伝播遅延 双方向ＭＳＮ内の伝播遅延は、選択されたルート内に存
在するノード数、リンク当りに利用可能なタイムスロッ
トの数（時分割多重アクセス、つまり、TDMAが使用され
る場合）、及び異なる周波数帯域当りに使用されるタイ
ムスロットの数（周波数分割多重、つまり、FDMA、或は
符号化分割多重アクセス、つまり、CDMAが使用される場
合）、並びに、あるループから別のループへの伝送（つ
まり、水平ループから垂直ループへの、或は逆の方向へ
の伝送）の数に依存する。遅延を最小にするために、後
に詳細に説明されるように、本発明においては、最適な
ルートが（それが利用できる場合は）選択される。ここ
で、この最適なルートとは、パケットが水平ループから
垂直ループに向かって、或はこの逆方向に一度のみ移動
し、これらループ内に最小数のノードが存在するような
ルートである（ここでは、発信ノードと着信ノードは、
同一ノード内に存在しないものと想定される）。
在するノード数、リンク当りに利用可能なタイムスロッ
トの数（時分割多重アクセス、つまり、TDMAが使用され
る場合）、及び異なる周波数帯域当りに使用されるタイ
ムスロットの数（周波数分割多重、つまり、FDMA、或は
符号化分割多重アクセス、つまり、CDMAが使用される場
合）、並びに、あるループから別のループへの伝送（つ
まり、水平ループから垂直ループへの、或は逆の方向へ
の伝送）の数に依存する。遅延を最小にするために、後
に詳細に説明されるように、本発明においては、最適な
ルートが（それが利用できる場合は）選択される。ここ
で、この最適なルートとは、パケットが水平ループから
垂直ループに向かって、或はこの逆方向に一度のみ移動
し、これらループ内に最小数のノードが存在するような
ルートである（ここでは、発信ノードと着信ノードは、
同一ノード内に存在しないものと想定される）。
【００１７】２．１．３ 網渋滞とフロー制御 網渋滞とフロー制御は双方向ＭＳＮ内のリンクのチャネ
ル容量に依存する（リンクは双方向ＭＳＮ内で二つのノ
ードを接続する通信要素である）。双方向ＭＳＮ内のリ
ンクのチャネル容量を決定するためには、以下の網パラ
メータ：つまり、ノードｎ当りのチャネルの数（各ノー
ドはハブ或はサーバとして機能するものと想定され
る）、ループＮ当りのノード数、及び許容されるチャネ
ル閉塞パーセント、を知ることが必要である。双方向Ｍ
ＳＮ内にＮ個のノードを持つ一つのループのみが存在
し、各ノードがｎ個のチャネルを持ち、０％の閉塞が許
されるものと想定すると（最も基本的な網を想定する
と）、ノード間リンクのチャネル容量はｎ×Ｎ／２＋Ｉ
Net となり、ここで、ＩNet は、網間パラメータ通信に
要求される少数の追加チャネルの数である。各ノードが
同数のノードを持つ二つの平行ループＡとＢに対して
は、ループＢ上のトラヒックに加えて、ループＡの各ノ
ードからループＢのノードに５０％のトラヒックがパス
するものと想定すると、ループＢ内の最悪の場合のチャ
ネル容量は、３ｎ／２×Ｎ／２＋ＩNet となる。網内に
異なる数のループが使用され、また、異なる想定がなさ
れた場合の式は、当業者においては、上の説明から明ら
かになるものである。
ル容量に依存する（リンクは双方向ＭＳＮ内で二つのノ
ードを接続する通信要素である）。双方向ＭＳＮ内のリ
ンクのチャネル容量を決定するためには、以下の網パラ
メータ：つまり、ノードｎ当りのチャネルの数（各ノー
ドはハブ或はサーバとして機能するものと想定され
る）、ループＮ当りのノード数、及び許容されるチャネ
ル閉塞パーセント、を知ることが必要である。双方向Ｍ
ＳＮ内にＮ個のノードを持つ一つのループのみが存在
し、各ノードがｎ個のチャネルを持ち、０％の閉塞が許
されるものと想定すると（最も基本的な網を想定する
と）、ノード間リンクのチャネル容量はｎ×Ｎ／２＋Ｉ
Net となり、ここで、ＩNet は、網間パラメータ通信に
要求される少数の追加チャネルの数である。各ノードが
同数のノードを持つ二つの平行ループＡとＢに対して
は、ループＢ上のトラヒックに加えて、ループＡの各ノ
ードからループＢのノードに５０％のトラヒックがパス
するものと想定すると、ループＢ内の最悪の場合のチャ
ネル容量は、３ｎ／２×Ｎ／２＋ＩNet となる。網内に
異なる数のループが使用され、また、異なる想定がなさ
れた場合の式は、当業者においては、上の説明から明ら
かになるものである。
【００１８】２．２ 故障耐性 本発明の双方向ＭＳＮは故障耐性であり、単一、多重、
及びクラスタのノード故障に対して優れた網生存特性を
示す。このノード故障を生き残る能力は、双方向性の結
果としての優れた網ルーティング能力によって増強され
る。双方向ＭＳＮ内のノードの一つ或は複数のクラスタ
が故障した場合、この双方向ＭＳＮは影響を受けた地域
を回避し、影響を受けないノードを含む経路を介して二
つ或はそれ以上のノード間で通信を確立することができ
る。
及びクラスタのノード故障に対して優れた網生存特性を
示す。このノード故障を生き残る能力は、双方向性の結
果としての優れた網ルーティング能力によって増強され
る。双方向ＭＳＮ内のノードの一つ或は複数のクラスタ
が故障した場合、この双方向ＭＳＮは影響を受けた地域
を回避し、影響を受けないノードを含む経路を介して二
つ或はそれ以上のノード間で通信を確立することができ
る。
【００１９】例えば、図２に示される双方向２０２を考
える。一つ或は複数のリンクが故障した及び／或は一つ
或は複数のノード２０８が動作不能な故障状態下におい
ては、“問題”地域をバイパスする代替経路が選択され
る。例えば、ノード（２、３）が故障しているものと想
定する。任意の与えられた発信及び着信ノードに対し
て、ノード（２、３）を伴わない複数のルートが利用で
き、このために、ノード間の接続性が故障したノード
（２、３）によって悪影響を受けることはない。あるノ
ードがある経路（以降、元の経路と称される）が確立さ
れた後に故障したものと想定する。この場合、故障した
ノードに物理的に近い（元の経路内の）ノードによって
一つの代替経路が選択される（これについては後に詳細
に説明される）。従って、この双方向ＭＳＮは、故障の
回避に加えて、網自己治癒特性を示す。
える。一つ或は複数のリンクが故障した及び／或は一つ
或は複数のノード２０８が動作不能な故障状態下におい
ては、“問題”地域をバイパスする代替経路が選択され
る。例えば、ノード（２、３）が故障しているものと想
定する。任意の与えられた発信及び着信ノードに対し
て、ノード（２、３）を伴わない複数のルートが利用で
き、このために、ノード間の接続性が故障したノード
（２、３）によって悪影響を受けることはない。あるノ
ードがある経路（以降、元の経路と称される）が確立さ
れた後に故障したものと想定する。この場合、故障した
ノードに物理的に近い（元の経路内の）ノードによって
一つの代替経路が選択される（これについては後に詳細
に説明される）。従って、この双方向ＭＳＮは、故障の
回避に加えて、網自己治癒特性を示す。
【００２０】２．３ 大惨事の回避 本発明の双方向ＭＳＮは、優れた大惨事回避特性を示
す。ノードの一つ或は複数のクラスタが動作不能になっ
た場合を考える。この場合、この双方向ＭＳＮは、影響
を受けた地域をパイパスし、残された健康な網（まだ充
分な接続性が存在するものと想定する）を通じて通信を
確立する。
す。ノードの一つ或は複数のクラスタが動作不能になっ
た場合を考える。この場合、この双方向ＭＳＮは、影響
を受けた地域をパイパスし、残された健康な網（まだ充
分な接続性が存在するものと想定する）を通じて通信を
確立する。
【００２１】３．双方向メッシュ網 ここでは、本発明の双方向メッシュ網（双方向ＭＳＮ）
について詳細に説明される。ここでの説明においては、
図２の双方向ＭＳＮ２０２が参照されるべきである。
について詳細に説明される。ここでの説明においては、
図２の双方向ＭＳＮ２０２が参照されるべきである。
【００２２】３．１ 通信リンク 上に説明されたように、双方向ＭＳＮ２０２は、通信リ
ンクによって互いに接続された複数のノード２０８を含
む。通信リンクは、二つの隣接するノード２０８を（水
平方向或は垂直方向に）接続する通信要素である。これ
ら通信リンクは、周知の伝送媒体、例えば、光ファイ
バ、同軸ケーブル、より対線、無線、等を使用して実現
することができる。将来開発される伝送媒体も使用する
ことが可能である。どの伝送媒体を使用するかは個々の
実現に依存し、さらに、幾つかの要因、例えば、使用さ
れる伝送技法（TDMA、 FDMA、 CDMA、 等）、チャネル容
量、伝送速度、ノード間距離、等に依存する。
ンクによって互いに接続された複数のノード２０８を含
む。通信リンクは、二つの隣接するノード２０８を（水
平方向或は垂直方向に）接続する通信要素である。これ
ら通信リンクは、周知の伝送媒体、例えば、光ファイ
バ、同軸ケーブル、より対線、無線、等を使用して実現
することができる。将来開発される伝送媒体も使用する
ことが可能である。どの伝送媒体を使用するかは個々の
実現に依存し、さらに、幾つかの要因、例えば、使用さ
れる伝送技法（TDMA、 FDMA、 CDMA、 等）、チャネル容
量、伝送速度、ノード間距離、等に依存する。
【００２３】無線が使用される場合は、周波数、アクセ
ス方法、及びプロトコルが、標準のアクセス技法、例え
ば、TDMA、 FDMA、 CDMAを使用しての地上通信に対して割
り当てられる周波数に準拠することが要求される。これ
は、同軸ケーブルに対してもあてはまるものであるが、
ただし、同軸ケーブルの場合は、この媒体のタイプのた
めにより多くの柔軟性が存在する。光ファイバが使用さ
れる場合は、SONET （同期光網）などの標準に準拠する
高ビット速度が使用される。
ス方法、及びプロトコルが、標準のアクセス技法、例え
ば、TDMA、 FDMA、 CDMAを使用しての地上通信に対して割
り当てられる周波数に準拠することが要求される。これ
は、同軸ケーブルに対してもあてはまるものであるが、
ただし、同軸ケーブルの場合は、この媒体のタイプのた
めにより多くの柔軟性が存在する。光ファイバが使用さ
れる場合は、SONET （同期光網）などの標準に準拠する
高ビット速度が使用される。
【００２４】３．２ ノード 図４はノード２０８のブロック図である。各ノード２０
８は、４入力×４出力空間時間通信スイッチであるクロ
ス接続４０２を含む。パケットは、好ましくは、幾つか
の周知のパケット伝送標準、例えば、周知の非同期転送
モード（ＡＴＭ）及びSONET 標準に従ってクロス接続４
０２の各入力及び出力上に時分割多重（ＴＤＭ）化され
る。クロス接続４０２は、一つの北入力ポート４０４
Ａ、南入力ポート４０４Ｂ、西入力ポート４０４Ｃ、及
び東入力ポート４０４Ｄを含む。クロス接続４０２は、
さらに、一つの北出力ポート４０６Ａ、南出力ポート４
０６Ｂ、西出力ポート４０６Ｃ、及び東出力ポート４０
６Ｄを含む。上に説明されたように、これら入力及び出
力ポート４０４、４０６の名前は、それらが接続されて
いるリンクを識別する。
８は、４入力×４出力空間時間通信スイッチであるクロ
ス接続４０２を含む。パケットは、好ましくは、幾つか
の周知のパケット伝送標準、例えば、周知の非同期転送
モード（ＡＴＭ）及びSONET 標準に従ってクロス接続４
０２の各入力及び出力上に時分割多重（ＴＤＭ）化され
る。クロス接続４０２は、一つの北入力ポート４０４
Ａ、南入力ポート４０４Ｂ、西入力ポート４０４Ｃ、及
び東入力ポート４０４Ｄを含む。クロス接続４０２は、
さらに、一つの北出力ポート４０６Ａ、南出力ポート４
０６Ｂ、西出力ポート４０６Ｃ、及び東出力ポート４０
６Ｄを含む。上に説明されたように、これら入力及び出
力ポート４０４、４０６の名前は、それらが接続されて
いるリンクを識別する。
【００２５】クロス接続４０２は、任意の入力ポート４
０４を任意の出力ポート４０６に接続する能力を持つ。
例えば、クロス接続４０２は、西入力ポート４０４Ｃを
西出力ポート４０６Ｃに接続することができる。こうし
て、本発明は、ノードと網経路をテストする目的のため
のループバック網能力を提供する。クロス接続４０２
は、好ましくは、コンピュータソフトウエアに従って動
作する中央処理ユニット（ＣＰＵ）とされるコントロー
ラ４０８によって制御される。別の方法として、コント
ローラ４０８は、例えば、ハードウエア状態マシンを使
用しハードウエアにて実現することもできる。コントロ
ーラ４０８は、ノード２０８の全ての機能を制御する。
これら機能については後に説明される。これら機能の遂
行に当って、コントローラ４０８は、好ましくは、メモ
リ、例えば、ランダムアクセスメモリ（ＲＡＭ）内に格
納されたテーブルとされる性能パラメータマップ（perf
ormance parameter map 、ＰＰＭ）内に格納されたデー
タを参照する。
０４を任意の出力ポート４０６に接続する能力を持つ。
例えば、クロス接続４０２は、西入力ポート４０４Ｃを
西出力ポート４０６Ｃに接続することができる。こうし
て、本発明は、ノードと網経路をテストする目的のため
のループバック網能力を提供する。クロス接続４０２
は、好ましくは、コンピュータソフトウエアに従って動
作する中央処理ユニット（ＣＰＵ）とされるコントロー
ラ４０８によって制御される。別の方法として、コント
ローラ４０８は、例えば、ハードウエア状態マシンを使
用しハードウエアにて実現することもできる。コントロ
ーラ４０８は、ノード２０８の全ての機能を制御する。
これら機能については後に説明される。これら機能の遂
行に当って、コントローラ４０８は、好ましくは、メモ
リ、例えば、ランダムアクセスメモリ（ＲＡＭ）内に格
納されたテーブルとされる性能パラメータマップ（perf
ormance parameter map 、ＰＰＭ）内に格納されたデー
タを参照する。
【００２６】図５にはコントローラ４０８の指令によっ
てノード２０８によって遂行される機能が機能ブロック
図５０２との関連で説明される。ノード２０８は、３つ
の主要な機能：つまり、自己診断機能５１６、ＰＰＭ更
新機能５１８、及びパケットルーティング機能５２０を
遂行する。これら機能５１６、５１８、及び５２０は、
（図５に示されるように）互いに並列に遂行されるが、
ただし、直列に、或は互いに独立して遂行することもで
きる。自己診断機能５１６は定期的に遂行される。ステ
ップ５０４に示されるように、この自己診断機能５１６
は、パケットが入力ノード４０４の所に到着したとき入
力ノード４０４の性能パラメータを監視する動作を含
む。性能パラメータの監視は周知の動作である。この性
能パラメータとしては、パケットエラー率、渋滞パラメ
ータ、リンクとノードの保全性、遅延パラメータ等が含
まれる。これら性能パラメータは、各入力ノード４０４
（及び各入力ノード４０４と関連する通信回路）、及び
入力ノード４０４がそれに接続された通信リンクのチャ
ネルの通信保全性の尺度である。ステップ５０６に示さ
れるように、ノード２０８は、これら性能パラメータ及
びノード２０８の識別（例えば、アドレス）を含むパケ
ットを生成する。このパケットを生成する方法は、当業
者においては明白である。ノード２０８は、次に、この
性能パラメータパケットを双方向ＭＳＮ２０２を通じて
他のノードにブロードカストする（つまり、その全ての
出力ポートに送る）。
てノード２０８によって遂行される機能が機能ブロック
図５０２との関連で説明される。ノード２０８は、３つ
の主要な機能：つまり、自己診断機能５１６、ＰＰＭ更
新機能５１８、及びパケットルーティング機能５２０を
遂行する。これら機能５１６、５１８、及び５２０は、
（図５に示されるように）互いに並列に遂行されるが、
ただし、直列に、或は互いに独立して遂行することもで
きる。自己診断機能５１６は定期的に遂行される。ステ
ップ５０４に示されるように、この自己診断機能５１６
は、パケットが入力ノード４０４の所に到着したとき入
力ノード４０４の性能パラメータを監視する動作を含
む。性能パラメータの監視は周知の動作である。この性
能パラメータとしては、パケットエラー率、渋滞パラメ
ータ、リンクとノードの保全性、遅延パラメータ等が含
まれる。これら性能パラメータは、各入力ノード４０４
（及び各入力ノード４０４と関連する通信回路）、及び
入力ノード４０４がそれに接続された通信リンクのチャ
ネルの通信保全性の尺度である。ステップ５０６に示さ
れるように、ノード２０８は、これら性能パラメータ及
びノード２０８の識別（例えば、アドレス）を含むパケ
ットを生成する。このパケットを生成する方法は、当業
者においては明白である。ノード２０８は、次に、この
性能パラメータパケットを双方向ＭＳＮ２０２を通じて
他のノードにブロードカストする（つまり、その全ての
出力ポートに送る）。
【００２７】ＰＰＭ更新機能５１８は、ノード２０８が
他のノードから性能パラメータパケットを受信するたび
に遂行される。これはステップ５０８によって表わさ
れ、ここで、ノード２０８が他のノードから性能パラメ
ータパケットを受信する。ステップ５１０において、ノ
ード２０８は性能パラメータパケット内に含まれる情報
を使用してその性能パラメータマップ４１０を更新す
る。性能パラメータマップ４１０は、双方向ＭＳＮ２０
２内の各ノードに対するエントリを含む。これらエント
リはそれらのおのおののノードに対する性能パラメータ
情報を含む。こうして、ステップ５１０において、ノー
ド２０８は、性能パラメータパケット内に含まれる情報
を使用してＰＰＭ４１０内のその性能パラメータパケッ
トを発信したノード（つまり、“発信”ノード）に対応
するエントリを更新する。
他のノードから性能パラメータパケットを受信するたび
に遂行される。これはステップ５０８によって表わさ
れ、ここで、ノード２０８が他のノードから性能パラメ
ータパケットを受信する。ステップ５１０において、ノ
ード２０８は性能パラメータパケット内に含まれる情報
を使用してその性能パラメータマップ４１０を更新す
る。性能パラメータマップ４１０は、双方向ＭＳＮ２０
２内の各ノードに対するエントリを含む。これらエント
リはそれらのおのおののノードに対する性能パラメータ
情報を含む。こうして、ステップ５１０において、ノー
ド２０８は、性能パラメータパケット内に含まれる情報
を使用してＰＰＭ４１０内のその性能パラメータパケッ
トを発信したノード（つまり、“発信”ノード）に対応
するエントリを更新する。
【００２８】ＰＰＭ４１０に関して、機能するノードと
機能しないノード、入力ポート問題を持つノード、出力
ポート問題を持つノード（これは、問題とされるノード
の下流のノードと関連する性能パラメータ情報を参照す
ることによって決定することができる）、機能するリン
クと機能しないリンク（これは、問題とされるリンクに
接続されたノードと関連する性能パラメータ情報を参照
することによって決定することができる）等を識別する
ことができる。ＰＰＭ４１０の使用については後に詳細
に説明される。ステップ５１２において、ノード２０８
は、受信された性能パラメータパケットを双方向ＭＳＮ
２０２内の他のノードにブロードカストする。この方法
にて、、性能パラメータパケットが終極的には双方向Ｍ
ＳＮ２０２内の全てのノードによって受信される。パケ
ットルーティング機能５２０（フロー制御機能とも称さ
れる）は、ノード２０８がデータパケットを受信するた
びに遂行される。パケットルーティング機能５２０を遂
行している間に、ノード２０８は、受信されたパケット
をルートする最良の方法を、そのパケットの発信ノード
と宛先ノード、及びＰＰＭ４１０内に含まれる情報に基
づいて決定する。
機能しないノード、入力ポート問題を持つノード、出力
ポート問題を持つノード（これは、問題とされるノード
の下流のノードと関連する性能パラメータ情報を参照す
ることによって決定することができる）、機能するリン
クと機能しないリンク（これは、問題とされるリンクに
接続されたノードと関連する性能パラメータ情報を参照
することによって決定することができる）等を識別する
ことができる。ＰＰＭ４１０の使用については後に詳細
に説明される。ステップ５１２において、ノード２０８
は、受信された性能パラメータパケットを双方向ＭＳＮ
２０２内の他のノードにブロードカストする。この方法
にて、、性能パラメータパケットが終極的には双方向Ｍ
ＳＮ２０２内の全てのノードによって受信される。パケ
ットルーティング機能５２０（フロー制御機能とも称さ
れる）は、ノード２０８がデータパケットを受信するた
びに遂行される。パケットルーティング機能５２０を遂
行している間に、ノード２０８は、受信されたパケット
をルートする最良の方法を、そのパケットの発信ノード
と宛先ノード、及びＰＰＭ４１０内に含まれる情報に基
づいて決定する。
【００２９】次に、ノード２０８がパケットルーティン
グ機能５２０を遂行する方法について図６の流れ図６０
２との関連で詳細に説明される。流れ図６０２は、ステ
ップ６０４から開始され、ここで、制御は直ちにステッ
プ６０６に移る。ステップ６０６において、ノード２０
８は、パケットの宛先アドレスの両方の座標がそれ自身
の二つの座標と一致するか決定する（換言すれば、ノー
ド２０８は、それがパケットの宛先であるか決定す
る）。このパケットの宛先アドレスは、そのパケット自
身の中に含まれる。こうして、このステップにおいて、
ノード２０８は、そのパケットの（行、列）として表わ
されるその宛先アドレスを読み出す。ここで、この
（行、列）は、宛先アドレスの座標である。ノード２０
８は、この宛先アドレスをそれ自身のアドレスと比較
し、その宛先アドレスの行と列の座標がそれ自身のアド
レスの行と列の座標と一致するか決定する。これら座標
が一致する場合は、ノード２０８は、それがそのパケッ
トの宛先であると結論する。結果として、ノード２０８
は、そのパケットを受け取る（ステップ６０８；流れ図
６０２は、ステップ６２０によって示されるように、ス
テップ６０８の処理を終えると、完了する）。一致しな
い場合は、ノード２０８は、ステップ６１０を遂行す
る。
グ機能５２０を遂行する方法について図６の流れ図６０
２との関連で詳細に説明される。流れ図６０２は、ステ
ップ６０４から開始され、ここで、制御は直ちにステッ
プ６０６に移る。ステップ６０６において、ノード２０
８は、パケットの宛先アドレスの両方の座標がそれ自身
の二つの座標と一致するか決定する（換言すれば、ノー
ド２０８は、それがパケットの宛先であるか決定す
る）。このパケットの宛先アドレスは、そのパケット自
身の中に含まれる。こうして、このステップにおいて、
ノード２０８は、そのパケットの（行、列）として表わ
されるその宛先アドレスを読み出す。ここで、この
（行、列）は、宛先アドレスの座標である。ノード２０
８は、この宛先アドレスをそれ自身のアドレスと比較
し、その宛先アドレスの行と列の座標がそれ自身のアド
レスの行と列の座標と一致するか決定する。これら座標
が一致する場合は、ノード２０８は、それがそのパケッ
トの宛先であると結論する。結果として、ノード２０８
は、そのパケットを受け取る（ステップ６０８；流れ図
６０２は、ステップ６２０によって示されるように、ス
テップ６０８の処理を終えると、完了する）。一致しな
い場合は、ノード２０８は、ステップ６１０を遂行す
る。
【００３０】ステップ６１０において、ノード２０８
は、そのパケットの宛先アドレスの座標の一つがそれ自
身のアドレスの座標の一つと一致するか決定する。一致
が発見された場合は、ステップ６１２が遂行される。そ
うでない場合は、ステップ６１６が遂行される。例え
ば、ノード（２、３）が（４、３）の宛先アドレスを持
つパケットに対してステップ６１０を処理しているもの
と想定する。この場合、列の座標が一致し、このため
に、このノード（２、３）はステップ６１２を遂行す
る。一方、そのパケットの宛先アドレスが（４、４）で
あると想定すると、この場合は、一致は存在せず、この
ために、ステップ６１６が遂行される（これについては
後に説明される）。
は、そのパケットの宛先アドレスの座標の一つがそれ自
身のアドレスの座標の一つと一致するか決定する。一致
が発見された場合は、ステップ６１２が遂行される。そ
うでない場合は、ステップ６１６が遂行される。例え
ば、ノード（２、３）が（４、３）の宛先アドレスを持
つパケットに対してステップ６１０を処理しているもの
と想定する。この場合、列の座標が一致し、このため
に、このノード（２、３）はステップ６１２を遂行す
る。一方、そのパケットの宛先アドレスが（４、４）で
あると想定すると、この場合は、一致は存在せず、この
ために、ステップ６１６が遂行される（これについては
後に説明される）。
【００３１】ステップ６１２において、ノード２０８
は、宛先ノードへの直接経路が利用できるか決定する。
このパケットの宛先アドレスの座標の一つがノード２０
８のアドレスの座標の一つと一致するために、二つの経
路が存在することが保証される。ただし、これら経路の
一つ或は両方が介在するノード及び／或はリンク内の故
障のために利用できないことも考えられる。ノード２０
８は、ノード及びリンク内の故障を、そのＰＰＭ４１０
内に含まれる性能パラメータ情報を参照することによっ
て識別する。例えば、ノード（１、３）が（４、３）の
宛先アドレスを持つパケットに対してステップ６１２を
処理しているものと想定する。ノード（１、３）からノ
ード（４、３）に向けて二つの直接経路が存在する。第
一の経路は、ノード（１、３）から、ノード（２、
３）、ノード（３、３）、ノード（４、３）に延びる。
第二の経路はノード（１、３）からノード（４、３）に
延びる。これら経路の一つ或は両方が介在するノード及
び／或はリンク内の故障のために利用できない可能性が
考えられる。ノード（３、３）が故障しているものと想
定する。この場合、第一の経路は利用できない。ここ
で、さらに、ノード（１、３）と（４、３）との間のリ
ンクが故障していると想定する。この場合、第二の経路
も利用できない。
は、宛先ノードへの直接経路が利用できるか決定する。
このパケットの宛先アドレスの座標の一つがノード２０
８のアドレスの座標の一つと一致するために、二つの経
路が存在することが保証される。ただし、これら経路の
一つ或は両方が介在するノード及び／或はリンク内の故
障のために利用できないことも考えられる。ノード２０
８は、ノード及びリンク内の故障を、そのＰＰＭ４１０
内に含まれる性能パラメータ情報を参照することによっ
て識別する。例えば、ノード（１、３）が（４、３）の
宛先アドレスを持つパケットに対してステップ６１２を
処理しているものと想定する。ノード（１、３）からノ
ード（４、３）に向けて二つの直接経路が存在する。第
一の経路は、ノード（１、３）から、ノード（２、
３）、ノード（３、３）、ノード（４、３）に延びる。
第二の経路はノード（１、３）からノード（４、３）に
延びる。これら経路の一つ或は両方が介在するノード及
び／或はリンク内の故障のために利用できない可能性が
考えられる。ノード（３、３）が故障しているものと想
定する。この場合、第一の経路は利用できない。ここ
で、さらに、ノード（１、３）と（４、３）との間のリ
ンクが故障していると想定する。この場合、第二の経路
も利用できない。
【００３２】ステップ６１２において、ノード２０８が
宛先ノードへの直接経路が利用できると決定した場合
は、ステップ６１４が遂行される。ステップ６１４にお
いて、ノード２０８は、これら直接経路の一つを選択
し、次に、このパケットをこうして選択された直接経路
内の次のノードに送る。たった一つの直接経路が利用で
きる場合は、ノード２０８は、その経路を選択する。た
だし、両方の直接経路が利用できる場合は、ノード２０
８は、最良の経路を選択する。ここで、最良の経路と
は、発信ノードから宛先ノードまでの最短の伝播遅延が
達成される経路として定義される。この例においては、
この最良の経路は、最少数のノードを持つ経路である。
ノード（１、３）が（４、３）の宛先アドレスを持つパ
ケットに対してステップ６１２を処理する上の例におい
ては、最良の経路は、ノード（１、３）からノード
（４、３）への経路である。
宛先ノードへの直接経路が利用できると決定した場合
は、ステップ６１４が遂行される。ステップ６１４にお
いて、ノード２０８は、これら直接経路の一つを選択
し、次に、このパケットをこうして選択された直接経路
内の次のノードに送る。たった一つの直接経路が利用で
きる場合は、ノード２０８は、その経路を選択する。た
だし、両方の直接経路が利用できる場合は、ノード２０
８は、最良の経路を選択する。ここで、最良の経路と
は、発信ノードから宛先ノードまでの最短の伝播遅延が
達成される経路として定義される。この例においては、
この最良の経路は、最少数のノードを持つ経路である。
ノード（１、３）が（４、３）の宛先アドレスを持つパ
ケットに対してステップ６１２を処理する上の例におい
ては、最良の経路は、ノード（１、３）からノード
（４、３）への経路である。
【００３３】流れ図６０２は、ステップ６２０に示され
るように、ステップ６１４の処理が終ると、完了する。
一方、ステップ６１２において、ノード２０８が宛先ノ
ードへの直接経路が利用できないことを決定した場合
は、ステップ６１６が遂行される。ステップ６１６にお
いて、ノード２０８は、宛先ノードへの利用できる最良
の経路を識別及び選択する。この説明においては、宛先
ノードへの少なくとも一つの利用できる経路が存在する
ものと想定される。利用できる経路が存在しない場合
は、ノード２０８によって取られる動作は、そのパケッ
トのサービスタイプに依存する。そのパケットがリアル
タイムサービス（例えば、リアルタイム音声サービス）
を含む場合は、好ましくは、このパケットは脱落され、
接続が脱落される（ノード２０８は、これを報告するメ
ッセージを発信ノードに送る）。一方、そのパケットが
非リアルタイムサービス（例えば、蓄積転送によるデー
タ伝送サービス）を含む場合は、ノード２０８は、この
パケットをその待ち行列内に保存し、経路が利用できる
ようになってからこのパケットを再び送信する（ただ
し、ある時間量が過ぎてもパケットが利用できるように
ならない場合は、パケットは脱落される）。
るように、ステップ６１４の処理が終ると、完了する。
一方、ステップ６１２において、ノード２０８が宛先ノ
ードへの直接経路が利用できないことを決定した場合
は、ステップ６１６が遂行される。ステップ６１６にお
いて、ノード２０８は、宛先ノードへの利用できる最良
の経路を識別及び選択する。この説明においては、宛先
ノードへの少なくとも一つの利用できる経路が存在する
ものと想定される。利用できる経路が存在しない場合
は、ノード２０８によって取られる動作は、そのパケッ
トのサービスタイプに依存する。そのパケットがリアル
タイムサービス（例えば、リアルタイム音声サービス）
を含む場合は、好ましくは、このパケットは脱落され、
接続が脱落される（ノード２０８は、これを報告するメ
ッセージを発信ノードに送る）。一方、そのパケットが
非リアルタイムサービス（例えば、蓄積転送によるデー
タ伝送サービス）を含む場合は、ノード２０８は、この
パケットをその待ち行列内に保存し、経路が利用できる
ようになってからこのパケットを再び送信する（ただ
し、ある時間量が過ぎてもパケットが利用できるように
ならない場合は、パケットは脱落される）。
【００３４】次に、図７の流れ図７０１との関連で、ノ
ード２０８がステップ６１２を遂行する方法について詳
細に説明する。流れ図７０１は、ステップ７０２から開
始され、ここで、制御は直ちにステップ７０４に移る。
ステップ７０４において、ノード２０８は、等級（degr
ee）変数ｄをゼロに初期化する。ステップ７０６におい
て、ノード２０８は、宛先ノードへの等級ｄの全ての利
用可能な経路を識別する。経路は、それが０個のループ
間転送を伴う場合、等級０であると定義される。ループ
間転送とは、水平ループ２０４から垂直ループ２０６へ
の、或はこの逆への、パケットの転送である。例えば、
ノード（１、１）がノード（１、３）という宛先を持つ
パケットを発信するものと想定する。この場合、等級０
の二つの経路が存在する。第一の経路は、ノード（１、
１）からノード（１、２）、ノード（１、３）への経路
であり、第二の経路は、ノード（１、１）から、ノード
（１、４）、ノード（１、３）への経路である。ある経
路が、それが１つのループ間転送を伴う場合、等級１で
あると定義される。例えば、ノード（１、１）がノード
（４、４）を宛先とするパケットを発信するものと想定
する。この場合、等級１の複数の経路が存在する。第一
はノード（１、１）からノード（４、１）、ノード
（４、４）への経路であり、第二はノード（１、１）か
らノード（１、４）、ノード（４、２）への経路であ
り、第三の経路はノード（２、１）からノード（３、
１）、ノード（４、１）、ノード（４、２）、ノード
（４、３）、ノード（４、４）への経路である。当業者
においては理解できるように、追加の等級１の経路が存
在する。当業者においては、１より大きな等級の経路の
本質が上の説明から明らかになるものである。
ード２０８がステップ６１２を遂行する方法について詳
細に説明する。流れ図７０１は、ステップ７０２から開
始され、ここで、制御は直ちにステップ７０４に移る。
ステップ７０４において、ノード２０８は、等級（degr
ee）変数ｄをゼロに初期化する。ステップ７０６におい
て、ノード２０８は、宛先ノードへの等級ｄの全ての利
用可能な経路を識別する。経路は、それが０個のループ
間転送を伴う場合、等級０であると定義される。ループ
間転送とは、水平ループ２０４から垂直ループ２０６へ
の、或はこの逆への、パケットの転送である。例えば、
ノード（１、１）がノード（１、３）という宛先を持つ
パケットを発信するものと想定する。この場合、等級０
の二つの経路が存在する。第一の経路は、ノード（１、
１）からノード（１、２）、ノード（１、３）への経路
であり、第二の経路は、ノード（１、１）から、ノード
（１、４）、ノード（１、３）への経路である。ある経
路が、それが１つのループ間転送を伴う場合、等級１で
あると定義される。例えば、ノード（１、１）がノード
（４、４）を宛先とするパケットを発信するものと想定
する。この場合、等級１の複数の経路が存在する。第一
はノード（１、１）からノード（４、１）、ノード
（４、４）への経路であり、第二はノード（１、１）か
らノード（１、４）、ノード（４、２）への経路であ
り、第三の経路はノード（２、１）からノード（３、
１）、ノード（４、１）、ノード（４、２）、ノード
（４、３）、ノード（４、４）への経路である。当業者
においては理解できるように、追加の等級１の経路が存
在する。当業者においては、１より大きな等級の経路の
本質が上の説明から明らかになるものである。
【００３５】ループ間転送を遂行するために幾らかの処
理時間が必要となる。このため、伝播遅延を低減するた
めには、可能な限り最も少ないループ間転送を持つ経路
を選択することが要望される。換言すれば、本発明は、
パケットを宛先ノードに転送するために可能な最も小さ
な等級の経路を選択するように動作する（これがステッ
プ７０４においてｄがゼロに初期化される理由であ
る）。ステップ７０６において、ノード２０８は、宛先
ノードへの等級ｄの全ての利用できる経路を識別するこ
とに注意する。つまり、等級ｄの経路が存在する場合で
も、これらがノード及び／或はリンク内の故障のために
利用できないことも考えられる。さらに、ステップ７０
６において、ノード２０８は、等級ｄの経路を識別する
ときにそのパケットが受信されたループを考慮すること
に注意する。例えば、ノード（１、２）がループ２０４
Ａ上のノード（１、１）からパケットを受信し、このパ
ケットが宛先としてノード（４、４）を持つものと想定
する。ノード（１、２）にとっては、等級１の経路に
は、ノード（１、２）から、ノード（１、４）、ノード
（４、４）への経路が含まれる。ノード（１、２）か
ら、ノード（４、２）、ノード（４、４）への経路も、
一見したところ、等級１の経路であるように思える。た
だし、これは、実際には、これが、二つのループ間転
送、つまり、ノード（１、２）の所での水平ループ２０
４Ａから垂直ループ２０６Ｂへの第一の転送と、ノード
（４、２）の所での垂直ループ２０６Ｂから水平への第
二の転送を伴うために、等級２の経路である。
理時間が必要となる。このため、伝播遅延を低減するた
めには、可能な限り最も少ないループ間転送を持つ経路
を選択することが要望される。換言すれば、本発明は、
パケットを宛先ノードに転送するために可能な最も小さ
な等級の経路を選択するように動作する（これがステッ
プ７０４においてｄがゼロに初期化される理由であ
る）。ステップ７０６において、ノード２０８は、宛先
ノードへの等級ｄの全ての利用できる経路を識別するこ
とに注意する。つまり、等級ｄの経路が存在する場合で
も、これらがノード及び／或はリンク内の故障のために
利用できないことも考えられる。さらに、ステップ７０
６において、ノード２０８は、等級ｄの経路を識別する
ときにそのパケットが受信されたループを考慮すること
に注意する。例えば、ノード（１、２）がループ２０４
Ａ上のノード（１、１）からパケットを受信し、このパ
ケットが宛先としてノード（４、４）を持つものと想定
する。ノード（１、２）にとっては、等級１の経路に
は、ノード（１、２）から、ノード（１、４）、ノード
（４、４）への経路が含まれる。ノード（１、２）か
ら、ノード（４、２）、ノード（４、４）への経路も、
一見したところ、等級１の経路であるように思える。た
だし、これは、実際には、これが、二つのループ間転
送、つまり、ノード（１、２）の所での水平ループ２０
４Ａから垂直ループ２０６Ｂへの第一の転送と、ノード
（４、２）の所での垂直ループ２０６Ｂから水平への第
二の転送を伴うために、等級２の経路である。
【００３６】ステップ７０８によって示されるように、
等級ｄの経路が利用できない場合は、ステップ７１０が
遂行される。ステップ７１０において、ｄが１だけ増分
され、制御はステップ７０６に戻る。一方、等級ｄの一
つ或は複数の経路が利用できると決定された場合は、ス
テップ７１２が遂行される。ステップ７１２において、
ノード７１２が等級ｄのこれら利用可能な経路の一つを
選択する。たった一つの等級ｄの経路が利用できる場合
は、ノード２０８はその経路を選択する。ただし、一つ
以上の等級ｄの経路が利用できる場合は、ノード２０８
は、最良の経路を選択する。ここで、この最良の経路と
は、発信ノードから宛先ノードへの最短の伝播遅延を与
える経路として定義される。この例においては、最良の
経路は、最少数のノードを持つ経路である。
等級ｄの経路が利用できない場合は、ステップ７１０が
遂行される。ステップ７１０において、ｄが１だけ増分
され、制御はステップ７０６に戻る。一方、等級ｄの一
つ或は複数の経路が利用できると決定された場合は、ス
テップ７１２が遂行される。ステップ７１２において、
ノード７１２が等級ｄのこれら利用可能な経路の一つを
選択する。たった一つの等級ｄの経路が利用できる場合
は、ノード２０８はその経路を選択する。ただし、一つ
以上の等級ｄの経路が利用できる場合は、ノード２０８
は、最良の経路を選択する。ここで、この最良の経路と
は、発信ノードから宛先ノードへの最短の伝播遅延を与
える経路として定義される。この例においては、最良の
経路は、最少数のノードを持つ経路である。
【００３７】流れ図７０１は、ステップ７１４によって
示されるように、ステップ７１２がの処理が終ると、完
了する。図６に再び戻り、ステップ６１８において、ノ
ード２０８は、パケットをステップ６１６において選択
された経路内の次のノード（つまり隣接するノード）に
送る。流れ図６０２の動作は、ステップ６２０によって
示されるように、ステップ６１８が終ると、完了する。
上では本発明の様々な実施例が示されたが、これらは、
単に一例として示されたものであり、制限を目的とする
ものではないことを理解すべきである。従って、本発明
の幅及び範囲は上に説明の一例としての実施例の幾つか
に制限されるものではなく、特許請求の範囲及びこれら
の同等物によってのみ定義されるものである。
示されるように、ステップ７１２がの処理が終ると、完
了する。図６に再び戻り、ステップ６１８において、ノ
ード２０８は、パケットをステップ６１６において選択
された経路内の次のノード（つまり隣接するノード）に
送る。流れ図６０２の動作は、ステップ６２０によって
示されるように、ステップ６１８が終ると、完了する。
上では本発明の様々な実施例が示されたが、これらは、
単に一例として示されたものであり、制限を目的とする
ものではないことを理解すべきである。従って、本発明
の幅及び範囲は上に説明の一例としての実施例の幾つか
に制限されるものではなく、特許請求の範囲及びこれら
の同等物によってのみ定義されるものである。
【図１】ループアーキテクチュアを持つ従来のマンハッ
タンストリート網を示す。
タンストリート網を示す。
【図２】本発明の一つの好ましい実施例による双方向メ
ッシュ網を示す。
ッシュ網を示す。
【図３】双方向メッシュ網の配達能力を示すために使用
される図である。
される図である。
【図４】双方向メッシュ網の一部分を形成するノードの
ブロック図である。
ブロック図である。
【図５】図４のノードの機能図である。
【図６】各ノードが双方向メッシュ網を通じてパケット
をルートする方法を示す流れ図である。
をルートする方法を示す流れ図である。
【図７】各ノードが双方向メッシュ網を通じてパケット
をルートする方法を示す流れ図である。
をルートする方法を示す流れ図である。
Claims (19)
- 【請求項１】 通信網であって、この通信網が：双方向
通信リンクによって互いに相互接続された複数のノード
から構成される第一の通信ループ；及び双方向通信リン
クによって互いに相互接続された複数のノードから構成
される第二の通信ループを含み、前記第二の通信ループ
が前記第一と第二の通信ループの両方に共通なノードの
所で前記第一の通信ループに接続され；前記共通ノード
がパケットを前記第一の通信ループから前記第二の通信
ループへ、或は逆の方向に、前記パケット内に含まれる
宛先アドレスの関数として転送するためのスイッチを含
むことを特徴とする通信網。 - 【請求項２】 前記第一の通信ループが前記の第二の通
信ループと実質的に直角を形成することを特徴とする請
求項１の通信網。 - 【請求項３】 前記第一と第二の通信ループ内の各ノー
ドが：通信リンクに接続され、また前記第一及び第二の
通信ループ内の前記各ノードに隣接するノードに接続さ
れた複数の入力ポート；前記入力ポートの性能パラメー
タを監視するための手段；前記各ノードの識別子及び前
記性能パラメータを含む性能パラメータパケットを生成
するための手段；及び前記性能パラメータパケットを前
記第一及び第二の通信ループ内の他の全てのノードにブ
ロードカストするための手段を含むことを特徴とする請
求項１の通信網。 - 【請求項４】 前記第一及び第二の通信ループ内の各ノ
ードが：前記通信網内の他のノードから性能パラメータ
パケットを受信するための手段を含み、前記性能パラメ
ータパケットが前記他のノードに関する性能パラメータ
を含み、前記性能パラメータが前記他のノードと、前記
他のノードに接続された通信リンクの、通信保全性を示
し；各ノードがさらに性能パラメータマップ内の前記他
のノードに対応するエントリを前記性能パラメータパケ
ット内に含まれる前記性能パラメータに従って更新する
ための手段を含むことを特徴とする請求項１の通信網。 - 【請求項５】 前記各ノードがさらに：データパケット
を受信するための手段；前記通信網内のそれを通じて前
記データパケットをその宛先にルートするための経路を
前記性能パラメータマップ内に含まれる性能パラメータ
情報に従って選択するための手段；及び前記データパケ
ットを前記選択された経路内の次のノードに送るための
手段を含むことを特徴とする請求項４の通信網。 - 【請求項６】 通信網であって、この通信網が：おのお
のが双方向通信リンクによって互いに相互接続された複
数のノードから構成される複数の第一の通信ループ；及
びおのおのが双方向通信リンクによって互いに相互接続
された複数のノードから構成される複数の第二の通信ル
ープを含み；各第二の通信ループが各第一の通信ループ
に前記各第二の通信ループと前記各第一の通信ループの
両方に共通なノードの所で接続され；前記共通ノードが
パケットを前記各第一の通信ループから前記各第二の通
信ループに、或はこの逆方向に、前記パケット内に含ま
れる宛先アドレスの関数として転送するためのスイッチ
を含むことを特徴とする通信網。 - 【請求項７】 前記第一の通信ループが互いに実質的に
平行に配列され、前記第二の通信ループが互いに実質的
に平行に配列されることを特徴とする請求項６の通信
網。 - 【請求項８】 前記第一の通信ループが前記第二の通信
ループに実質的に直角に配列されることを特徴とする請
求項６の通信網。 - 【請求項９】 前記第一と第二の通信ループ内の各ノー
ドが：通信リンクに接続され、また前記第一及び第二の
通信ループ内の前記各ノードに隣接するノードに接続さ
れた複数の入力ポート；前記複数の入力ポートの性能パ
ラメータを監視するための手段；前記各ノードの識別子
及び前記性能パラメータを含む性能パラメータパケット
を生成するための手段；及び前記性能パラメータパケッ
トを前記第一と第二の通信ループ内の全ての他のノード
にブロードカストするための手段を含むことを特徴とす
る請求項６の通信網。 - 【請求項１０】 前記第一と第二の通信ループ内の各ノ
ードが：前記通信網内の他のノードから性能パラメータ
パケットを受信するための手段を含み、前記性能パラメ
ータパケットが前記他のノードに関する性能パラメータ
を含み、前記性能パラメータが前記他のノードと、前記
他のノードに接続された通信リンクの、通信保全性を示
し；各ノードがさらに性能パラメータマップ内の前記他
のノードに対応するエントリを前記性能パラメータパケ
ット内に含まれる前記性能パラメータに従って更新する
ための手段を含むことを特徴とする請求項６の通信網。 - 【請求項１１】 前記各ノードがさらに：データパケッ
トを受信するための手段；前記通信網内のそれを通じて
前記データパケットをその宛先にルートするための経路
を前記性能パラメータマップ内に含まれる性能パラメー
タ情報に従って選択するための経路選択手段；及び前記
データパケットを前記選択された経路内の次のノードに
送るための手段を含むことを特徴とする請求項１０の通
信網。 - 【請求項１２】 前記経路手段が：前記パケットの宛先
アドレスが前記各ノードのアドレスと一致するか否か決
定するための手段；前記パケットアドレスが前記各ノー
ドのアドレスと一致する場合、前記パケットを受け入れ
るための手段；前記パケットが受け入れられない場合、
前記パケット宛先アドレスの片方の座標が前記各ノード
のアドレスの対応する座標と一致するか決定するための
手段；前記パケット宛先アドレスの片方の座標が前記各
ノードのアドレスの対応する座標と一致する場合、前記
各ノードから前記パケットの宛先ノードに至る直接経路
が利用可能であるか前記性能パラメータマップ内に含ま
れる性能パラメータ情報に従って決定するための手段；
利用できる直接経路がある場合、一つの利用可能な直接
経路を選択するための直接経路選択手段；及び前記パケ
ットを前記選択された直接経路内の次のノードに送るた
めの手段を含むことを特徴とする請求項１１の通信網。 - 【請求項１３】 前記経路選択手段がさらに：直接経路
が利用できない場合、前記各ノードから前記宛先ノード
に延びる非直接経路を前記性能パラメータマップ内に含
まれる性能パラメータ情報に従って選択するための手
段；及び前記パケットを前記選択された非直接経路内の
次のノードに送るための手段を含むことを特徴とする請
求項１２の通信網。 - 【請求項１４】 おのおのが双方向通信リンクによって
互いに相互接続された複数のノードから構成される複数
の第一の通信ループと、おのおのが双方向通信リンクに
よって互いに相互接続された複数のノードから構成され
る複数の第二の通信ループから構成され、各第二の通信
ループが各第一の通信ループに、前記各第二の通信ルー
プと前記各第一の通信ループの両方に共通なノードの所
で接続される通信網の、共通ノード内で使用される、こ
の通信網内でパケットをルーティングするための方法で
あって、この方法が： （１）前記パケットの宛先アドレスが前記共通ノードの
アドレスと一致するか否か決定するステップ； （２）前記パケット宛先アドレスが前記共通ノードアド
レスと一致する場合、前記パケットを前記共通ノード内
に受け入れるステップ； （３）前記パケットが受け入れなかった場合、前記パケ
ット宛先アドレスの片方の座標が前記共通ノードアドレ
スの対応する座標と一致するか決定するステップ； （４）前記パケット宛先アドレスの片方の座標が前記共
通ノードアドレスの対応する座標に一致する場合、前記
共通ノードから前記パケットの宛先ノードに延びる直接
経路が利用できるか性能パラメータマップ内に含まれる
性能パラメータ情報に従って決定するステップ； （５）利用できる直接経路がある場合、一つの利用可能
な直接経路を選択するステップ；及び （６）前記パケットを前記選択された直接経路内の次の
ノードに送るステップを含むことを特徴とする方法。 - 【請求項１５】 前記ステップ（５）が：複数の経路が
利用できる場合、最少数のノードを含む直接経路を選択
するステップを含むことを特徴とする請求項１４の方
法。 - 【請求項１６】 さらに： （７）直接経路が利用できない場合、前記共通ノードか
ら前記宛先ノードに延びる非直接経路を前記性能パラメ
ータマップ内に含まれる性能パラメータ情報に従って選
択するステップ；及び （８）前記パケットを前記選択された非直接経路内の次
のノードに送るステップが含まれることを特徴とする請
求項１４の方法。 - 【請求項１７】 前記ステップ（７）が： （ａ）前記共通ノードから前記宛先ノードへの等級ｄの
全ての経路を識別するステップ； （ｂ）等級ｄの前記識別された任意の経路が利用できる
か前記性能パラメータマップ内に含まれる性能パラメー
タ情報に従って決定するステップ；及び （ｃ）前記等級ｄの経路の一つ或は複数が利用できる場
合、前記等級ｄの利用できる経路の一つを選択するステ
ップを含むことを特徴とする請求項１６の方法。 - 【請求項１８】 前記ステップ（ｃ）が：等級ｄの複数
の経路が利用できる場合、最少数のノードを含む一つの
利用できる等級ｄの経路を選択するステップを含むこと
を特徴とする請求項１７の方法。 - 【請求項１９】 前記ステップ（７）がさらに： （ｄ）等級ｄの経路が利用できない場合、ｄを１だけ増
分し、ステップ（ａ）−（ｃ）を反復するステップを含
むことを特徴とする請求項１７の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/360,517 US5606551A (en) | 1994-12-21 | 1994-12-21 | Bidirectional mesh network |
| US08/360517 | 1994-12-21 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH08237245A true JPH08237245A (ja) | 1996-09-13 |
Family
ID=23418313
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7331276A Withdrawn JPH08237245A (ja) | 1994-12-21 | 1995-12-20 | 双方向メッシュ網 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5606551A (ja) |
| EP (1) | EP0720332A3 (ja) |
| JP (1) | JPH08237245A (ja) |
| CA (1) | CA2161721A1 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005295236A (ja) * | 2004-03-31 | 2005-10-20 | Serukurosu:Kk | 通信装置 |
| JP2006311333A (ja) * | 2005-04-28 | 2006-11-09 | Fujitsu Ltd | 通信装置、通信ノードおよび通信方法 |
Families Citing this family (29)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5793842A (en) | 1995-02-27 | 1998-08-11 | Schloemer; Jerry R. | System and method of call routing and connection in a mobile (remote) radio telephone system |
| US5787403A (en) * | 1995-03-08 | 1998-07-28 | Huntington Bancshares, Inc. | Bank-centric service platform, network and system |
| US5996020A (en) * | 1995-07-21 | 1999-11-30 | National Security Agency | Multiple level minimum logic network |
| NZ313707A (en) * | 1995-07-28 | 1999-04-29 | British Telecomm | Packet routing comprising a packet, node and directional flag |
| JPH1056493A (ja) * | 1996-08-13 | 1998-02-24 | Nec Corp | 通信ネットワーク内における制御情報の転送装置 |
| US5959999A (en) * | 1996-09-20 | 1999-09-28 | Linkabit Wireless, Inc. | Providing control-function data in communication-data channel of a full-mesh satellite communication network by dynamic time-slot assignment in TDMA-frame communication channel |
| US5898827A (en) * | 1996-09-27 | 1999-04-27 | Hewlett-Packard Co. | Routing methods for a multinode SCI computer system |
| US6289021B1 (en) * | 1997-01-24 | 2001-09-11 | Interactic Holdings, Llc | Scaleable low-latency switch for usage in an interconnect structure |
| US6212360B1 (en) * | 1997-04-09 | 2001-04-03 | Ge Capital Spacenet Services, Inc. | Methods and apparatus for controlling earth-station transmitted power in a VSAT network |
| WO1999014915A2 (en) * | 1997-09-17 | 1999-03-25 | British Telecommunications Public Limited Company | Process scheduling in computer network |
| US6389453B1 (en) * | 1997-10-09 | 2002-05-14 | Mci Communications Corporation | Method and system for routing undirectional multicast data |
| US6219346B1 (en) * | 1997-12-02 | 2001-04-17 | At&T Corp. | Packet switching architecture in cellular radio |
| US6754207B1 (en) | 1998-01-20 | 2004-06-22 | Interactic Holdings, Llc | Multiple-path wormhole interconnect |
| US6853635B1 (en) | 2000-07-24 | 2005-02-08 | Nortel Networks Limited | Multi-dimensional lattice network |
| WO2002033898A2 (en) * | 2000-10-19 | 2002-04-25 | Interactic Holdings, Llc | Scaleable multiple-path wormhole interconnect |
| US7339947B2 (en) * | 2001-04-18 | 2008-03-04 | Skypilot Networks, Inc. | Network channel access protocol—frame execution |
| US8260896B2 (en) | 2007-02-02 | 2012-09-04 | Mwa Intelligence, Inc. | Monitoring business machines using a mesh network on field nodes |
| US7027413B2 (en) * | 2001-09-28 | 2006-04-11 | Sun Microsystems, Inc. | Discovery of nodes in an interconnection fabric |
| US7616961B2 (en) * | 2002-04-29 | 2009-11-10 | Harris Corporation | Allocating channels in a mobile ad hoc network |
| US20050068902A1 (en) * | 2003-07-09 | 2005-03-31 | Kamlesh Rath | Scalable broadband wireless mesh access network |
| US7336642B2 (en) * | 2003-08-07 | 2008-02-26 | Skypilot Networks, Inc. | Communication protocol for a wireless mesh architecture |
| US7656805B2 (en) * | 2004-05-26 | 2010-02-02 | Sun Microsystems, Inc. | Optimal communication path routing in a system employing interconnected integrated circuit technology |
| US8068507B2 (en) * | 2005-06-14 | 2011-11-29 | Interdigital Technology Corporation | Method and system for conveying backhaul link information for intelligent selection of a mesh access point |
| US8005100B2 (en) * | 2006-09-21 | 2011-08-23 | Active Control Technology Inc. | Network for confined hazardous or other extreme environments |
| US8045505B2 (en) | 2007-01-18 | 2011-10-25 | Science Applications International Corporation | Mechanism for automatic network formation and medium access coordination |
| US20100250784A1 (en) * | 2009-03-26 | 2010-09-30 | Terascale Supercomputing Inc. | Addressing Scheme and Message Routing for a Networked Device |
| US7957385B2 (en) * | 2009-03-26 | 2011-06-07 | Terascale Supercomputing Inc. | Method and apparatus for packet routing |
| US7957400B2 (en) * | 2009-03-26 | 2011-06-07 | Terascale Supercomputing Inc. | Hierarchical network topology |
| US9525638B2 (en) | 2013-10-15 | 2016-12-20 | Internap Corporation | Routing system for internet traffic |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4598400A (en) * | 1983-05-31 | 1986-07-01 | Thinking Machines Corporation | Method and apparatus for routing message packets |
| US4742511A (en) * | 1985-06-13 | 1988-05-03 | Texas Instruments Incorporated | Method and apparatus for routing packets in a multinode computer interconnect network |
| CA1252168A (en) * | 1985-07-24 | 1989-04-04 | Kenneth A. Bobey | Communications network |
| US4797882A (en) * | 1985-10-02 | 1989-01-10 | American Telephone And Telegraph Company, At&T Bell Laboratories | Mesh-based switching network |
| US5105424A (en) * | 1988-06-02 | 1992-04-14 | California Institute Of Technology | Inter-computer message routing system with each computer having separate routinng automata for each dimension of the network |
| GB8911395D0 (en) * | 1989-05-18 | 1989-07-05 | British Telecomm | Data communications network |
| US5175733A (en) * | 1990-12-27 | 1992-12-29 | Intel Corporation | Adaptive message routing for multi-dimensional networks |
-
1994
- 1994-12-21 US US08/360,517 patent/US5606551A/en not_active Expired - Lifetime
-
1995
- 1995-10-30 CA CA002161721A patent/CA2161721A1/en not_active Abandoned
- 1995-12-05 EP EP95308772A patent/EP0720332A3/en not_active Withdrawn
- 1995-12-20 JP JP7331276A patent/JPH08237245A/ja not_active Withdrawn
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005295236A (ja) * | 2004-03-31 | 2005-10-20 | Serukurosu:Kk | 通信装置 |
| JP2006311333A (ja) * | 2005-04-28 | 2006-11-09 | Fujitsu Ltd | 通信装置、通信ノードおよび通信方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| CA2161721A1 (en) | 1996-06-22 |
| US5606551A (en) | 1997-02-25 |
| EP0720332A2 (en) | 1996-07-03 |
| EP0720332A3 (en) | 1998-12-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5606551A (en) | Bidirectional mesh network | |
| US6728205B1 (en) | Method and apparatus for automatic protection switching | |
| Maxemchuk | Regular mesh topologies in local and metropolitan area networks | |
| Maxemchuk | Routing in the Manhattan street network | |
| US7729337B2 (en) | Protocol for the determination of network topology | |
| AU607571B2 (en) | Distributed load sharing | |
| US6711125B1 (en) | Provisioning networks for reliable quality of service | |
| US8547981B2 (en) | Self-routed layer 4 packet network system and method | |
| EP0844755A2 (en) | Trunk transmission network | |
| EP0233898A1 (en) | CONNECTING BROADCASTING NETWORKS. | |
| US8139478B1 (en) | Recovery method for an optical network | |
| CN114024969A (zh) | 一种负载均衡方法、装置和系统 | |
| US7414985B1 (en) | Link aggregation | |
| US6545977B2 (en) | Methods and apparatus for routing signals in a ring network | |
| US20020131409A1 (en) | Self-healing multi-level telecommunications network | |
| US7315517B2 (en) | Non-blocking WDM optical networks | |
| US5289467A (en) | Manhattan street network with loop architecture | |
| Brassil et al. | The Manhattan Street Network: a high performance, highly reliable metropolitan area network | |
| Novak et al. | Steiner tree based distributed multicast routing in networks | |
| Raghavendra et al. | Double loop network architectures-A performance study | |
| US7532584B2 (en) | Implementation of constraints to ensure deadlock avoidance in networks | |
| US7710878B1 (en) | Method and system for allocating traffic demands in a ring network | |
| Kos et al. | Topological planning of communication networks | |
| Krishnan et al. | Is there life beyond linear topologies? a comparison of DQDB and the manhattan street network | |
| Lee et al. | Flush optimizations to guarantee less transient traffic in Ethernet ring protection |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20030304 |