JPS58150349A

JPS58150349A - パケツト通信ネツトワ−ク

Info

Publication number: JPS58150349A
Application number: JP57032786A
Authority: JP
Inventors: Shoichi Takeuchi; 彰一竹内
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1982-03-02
Filing date: 1982-03-02
Publication date: 1983-09-07

Abstract

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

Description

【発明の詳細な説明】この発明祉パケット通信方式において情報パケットを目
的地に送るパケット通信ネットワークに係シ、特にその
スイッチの不良な時の動作に関するものである。

オ１図は従来のパケット通信ネットワークの一例を示す
ブロック結線図である。は１Ｆｉ１６人力１６出力のパ
ケット通信ネットワークスイッチ１２）Ｈこのネットワ
ークを構成する２人力２出力のネットワークスイッチで
ある。

一般に？入力２Ｎ出力のネットワークは、縦方向に２Ｎ
−１個、横方向にＮ段の２人力２出力ネットワークスイ
ッチ（２１を配列することによシ得られる。

各段の間の結線パターンについて一般の２　人力２Ｎ　
　出力のネットワークを想定して説明する。説用土の都
合のため、各段に入力側から０，１，２゜・・・、Ｎ−
１，と番号をつける。また各段を構成する２人力２出力
ネットワークスイッチ（２）についても、上から顔にＯ
から２　−１までの番号を割シ当でそれを２進数で表示
する。第１図の２人力２出力ネットワークスイッチ（２
）の枠の内にはこの２進数字が書いである。

今オｉ段目にある２人力２出−カネットワークスイッチ
（２）を（ＰＬ、　Ｐｔ−□・・・−・・・・Ｐｌ）ｉただしｔ
＝Ｎ−１、Ｐ、＝０あるいＦｉｌコと表わすことにすると、段の間の結線法則は次のように
なる。

オｉ段目の２人力２出力ネットワークスイッチ（２）の
（ＰＬ、　ＰＬ、−０・・・Ｐｌ）、についてその上か
ら出る出力縁はオ（ｉ◆ｌ）段目の（Ｐ、　、・・・Ｐ
Ｌｍ＋１＋’　ｅ　Ｐｔ−ｔ　　・・・Ｐｇ　）ｉｌｌ
　　、その１から出る出力線はオ（ｉｌｌ）段目の（Ｐ
ｔ・−・ＰＬ−ｉ。□、　ｌ　、　Ｐｌ、、４・−Ｐ、
）０、へそれぞれ接続される。たとえば第１◆１１図でｉ＝ｔのｒｏｏｌＪで表わされているネットワー
クスイッチ（２）を考えると、＃Ｎ−１＝３であシ屹＝
ｒｏＪ、　Ｐｚ−１＝ｒｌＪｔ　ＰＬｍｒＯＪであるか
ら、その上から出る出力線は第１図でｉｌｌ（ｉ＝１）
段目の（ＰＬ、　−・Ｐｔ−１ヤｔ＃　０＃　Ｐ　・ｙ
Ｒ）ｉｌｌに接続される゛が、−１ｔ　＝　３．　ｔ−ｉ＋１＝３であるからＰＬｍ　−”
　Ｐｔ−１＋ｘは仁の場合Ｆｉ１個のｈビットを意味し
これはｒＯＪであり、またｔ−Ｌ＝２で’ｆｆ１−１−
”はこの場合は１個のｈビットを意味しこれはｒｘＪで
おるから（Ｐ、、−・・Ｐｚ−ｔ＋ｔｔｏ、Ｐｔ−□、
・・・ｈ）ｉ＊ｘは第２段目のｒｏｏｘ　Ｊで表わされ
るネットワークスイッチ（２）であり、同様に下から出
る出力線が接続される（Ｐ　、・・・Ｐｔ−１＋１＊　
ｌ　。

ＰＬ−１１・・・ｆ’ｋ）ｉや、は第２段目のｒｏ’ｔ
ｌ」で表わされるネットワークスイッチ（２）である。

第２図ＩＩ′ｉ２人力２出力ネットワークスイッチ（２
；の１例を示す結線状態図で第２図（ａ）は直通状態、
第２図（ｂ）は交差状態を示している。

次に動作について説明する。一般にパケット通信方式で
は、通信単位扛パケットと呼ばれ、その中に発信地と目
的地のアドレスを含んでおシ、パケット通信ネットワー
クを構成する各ネットワークスイッチ（２１は、これら
のアドレスを参照して適邑な経路選択を行い、正しい方
向にデータを転送する。説明の都合上２Ｎ本の入力及び
２Ｎ　本の出力のそれぞれのアドレスを、Ｏから２Ｎ　
−１″＆での２進数で表現する。第１図には、１６人力
、１６出力のパケット通信ネットワークスイッチ（１）
の場合の入力ｍ１出力線のアドレス管示しである。図の
左端には入力線のｏｏｏｏ〜１１１１のアドレスを、図
の右端には出力線のｏｏｏｏ〜１１１１のアドレスを示
しである。

一般に２Ｎ　　入力、２Ｎ　出力のネットワークにおい
て、パケットの発信地アドレスが％　５Ｎ−１ｅ　５Ｎ
−１ｔ＋＋−−、Ｓ＠　　、目的アドレスがＤＮ−１ｅ
　ＤＮ−２ｅ　”’　＋　Ｉ）ｌ）　＋（ただしＳｔ　
、　Ｄｉは１あるいは０である）として、各ネットワー
クスイッチ（２１における経路選択アルゴリズムについ
て説明する。オｉ番目のスイッチ（２）でこのパケット
を前段から受けとったものが、このパケットの目的地ア
ドレスのＤＮ−１１ビツトがＯであるときＫＦｉ、この
パケットを上側の出力線に、ｌであるときには下側の出
力線に送出する。

一般に２Ｎ　入力２′　出力のネットワークの任意の発
信地、目的地の組に対して、それらをつなぐ経路がネッ
トワークの中に常に友だ１つ存在することが証明されて
おり、上記のアルボ１）ズムがその経路を与えるもので
あることも証明されている。

また、上記のアルゴリズムは、目的地アドレスのみを使
用し、発信地アドレスを使用しないものになっている。

ネットワーク全体は、常に複数のパケットを受は入れる
ことができ、それらは目的地アドレスに従って、ネット
ワーク中を独立に流れる。２つのパケットが１つの２人
力２出力のネットワークスイッチ（２）を共有できる形
態に第２図に示す２つの場合に限られている。

第２図（ａ）では２つのパケットは平行してネットワー
クスイッチ（２１の中を通過し、２２図伽）では交差し
て通過する。これら以外の形でネットワークスイッチ１
２）を通過しようとする２つのパケット扛、一方が他方
のパケットが通過するまで待たされる。

従来のパケット通信ネットワークは、上記のように発信
地と目的地を結ぶ経路が常に１つに固定されておシ、ま
た、１つの２人力２出力のネットに◆１ワークスイッチ（２）が２　　通シの発信地と目的地を
結ぶ経路の１部として使われるため、２人力２出力のネ
ットワークスイッチ（２）の故障により多くのパケット
交換が不能になったシ、また、長大なパケットの転送時
に他の多くのパケットの処理が長時間待た市れるなどの
欠点があった。

この発明は、上記のような従来装置の欠点を除去するた
めになされたもので、故障したネットワークスイッチや
パケット転送に占有されているネットワークスイッチを
回避してパケットを目的地に転送することのできるパケ
ット通信ネットワークを得ることを目的とするものであ
る。

第３図はこの発明の一実施例を示すブロック結線図でＴ
ｏシ、（１１は上記第１図の同一符号と同−又は相当部
分を示すものである。

（３０）はパケット通信ネットワークスイッチ（１）を
構成する２人力２出力のネットワークスイッチ、（３１
）は入力され良パケットをネットワークの状態に応じて
縦方向に再配置する入力パケット再配置装置、（３２）
はネットワークスイッチ（３０）の各々の状態を検出す
るネットワーク状態検出装置、（３３）は入力パケット
の目的地アドレスを調べて直接ネットワークスイッチ（
３０）に出力したシ、隣接するスイッチに出力し＋、ｂ
するパケット再配置用スイッチである。第４図はパケッ
ト再配置用スイッチ（３３）の−例を示すブロック結線
図である。図において（４１）は隣接するパケット再配
置用スイッチ（３３ンから来たパケット金上下いづれか
へ分配するデータ分配器、（４２）、（４３）Ｆｉ外部
からの入力パケットとデータ分配器（４１ンからの入力
パケットとの衡突を回避するためのアービタ（ａｒｂｉ
ｔｅｒ　）、（４４）はここからパケットを直接ネット
ワークにｉカする場合に転送不能な目的地アドレスを生
成する到達不能目的地アドレス生成器、（４５）、（４
６）は到達不能アドレス生成器（４４）で生成されたア
ドレスと入力パケットの目的地アドレスを比較して一致
しない場合にはネットワークスイッチ（１）に出力し、
一致した場合には、隣接するパケット再配置用スイッチ
（３３）に転送する目的地アドレス検査器、（４７）は
２つの目的地アドレス検査器（４５）　、　（４６）か
らのパケットの衝突を回避する九めのアービタである。

第３図には１６人力１６出力パケット通信ネットワーク
を示し念が“、この発明は一般の２１ｉ人カ２Ｎ出力パ
ケット通信ネットワークに問題なく拡張できる。

パケット通信ネットワークスイッチ（１）を構成する２
人力２出力のネットワークスイッチ（３０）の各段にお
ける番号付けはさきに第１図について説明した通シとし
、同様の番号付けをパケット再配置用スイッチ（３３）
についても行う。またパケット通信ネットワークスイッ
チ（１）の入力線及び出力線ノアドレスも前述のように
付け、同様のことを六方パケット再配置装ｆ　（３１）
　Ｋついて吃行う。以上の番号付けの結果を第３図に示
しである。

次に動作について一般の２ｖｉ人カ２ＮｗＪのパケット
通信ネットワークを想定して説明する。ネットワーク状
態検出装ｆ　（３２）は、ネットワークを構成する２人
力２出力のネットワークスイッチ（３０）の状態を監視
し、故障スイッチや長大なパケットの転送に占有されて
いるスイッチを検出する。今このようなネットワークス
イッチ（３ｏ）が、オｉ段で検出されたとする。このネ
ットワークスイツｆ（３０）のアドレスの２進数表現を
次のように表す。

Ｄｔ　ｇ　＝＝・Ｄｚ−ｉ　４１　ｓｚ　−Ｓｉ　＋　
まただしｔミドｌ、Ｄｊ、５ｊ＝ｏある四おこのとき、
発信地アドレス８ｔ−８ｉ＋□Ａ１・・・人、。

目的地アドレスＤｔ・・・Ｄ□−ｔ＋ＩＢＡ−ｉ−・・
Ｂ、を持っパケットの転送が、この障害したネットワー
クスイッチ（３０）のため不可能になる。ただしＡｊ　
（ｊ＝ｏ、・・・、１）Ｂｊ（ｊ−０，−・１−１　）
はそれぞれ０でもｌでも良いドントケアビットである。

左ｌビットに１．右Ｌ−１◆五ビットに０をもつ長さｔ
÷１ビットのビット列を目的地アドレスに対するマスク
と呼ぶ。マスクは目的地アドレスと同じ長さを持ちドン
トケアビットに対応する部分に０．それ以外の部分に１
が設定されている。ネットワーク状態検出装置（３２）
は入力パケット再配置装置（３１）の中のアドレス８ｔ
・”　Ｓｉ　＊　Ｉ　Ａｉ・・・Ａ、をもつパケット再
配置用スイッチ（３３）にこの目的地アドレスＤｔ−・
Ｄｔ−ｉ＋ｔＢｔ−ｉ　−Ｂｅとこれに対するマスフを
転送する。パケット再配置用スイッチ（３３）の中の到
着不能目的地アドレス生成器（４４）はこのようなアド
レスとマスク対を複数個記憶できる機能をもっているも
のとする。

一方、外部からの入力パケットは、その発信地アドレス
と同一の入力線から入カッくケラト再配置仮置（３１）
に入り、パケット再配置スイッチ（３３）に送られる。

入力パケットは、了−ビタ（４２）　、　（４３）のい
づれかを通り、目的地アドレス検査器（４５）　、（，
４Ｓ）に送られる。目的地アドレス検査器（４５）、（
４６）は、到達不能アドレス生成器（４４）に格納され
ている到達不能目的地アドレス、マスクの対の各々に対
して、入力パケットの目的アドレスと到達不能目的地ア
ドレスがマスクに示されているドントケアピットを除い
て完全に一致するかどうかを調べる。

もし、ドントケアピットを除いて完全に一致するアドレ
ス゛が到達不能アドレス生成器（４４）にあった場合に
は、その入力パケットは、今それが置かれている入力線
に対応する発信地から、直接ネットワークスイッチ（１
）を通じて目的地に転送することは不可能であるので、
発信地を変更するためにアービタ（４７）を経由して、
隣接するパケット再配置用スイッチ（３３）に転送され
る。もしすべての到達不能アドレスマスク対の中に一致
するものがなかった場合には、そこから目的地へ転送可
能なので、パケットは直接ネットワークスイッチ＋１１
へ出力すれる。

また、指定され九目的地へ到達不能でおるため隣接する
パケット再配置用スイッチ（３３）へ転送され九パケッ
トは、そのスイッチの中のデータ分配器（４１）　ｔ−
通じてアービタ（４２）　、　（４３）のいずれかに分
配され、前に述べたことと同じ処理を受ける。

この発明は、以上説明したとおりネットワークの状態を
検出しパケットの発信元を動的に変更する装置を設ける
ことによシ故陣中や長時間占有されているネットワーク
を回避して動作し、ネットワークの利用効率を向上させ
るという効果がある。

【図面の簡単な説明】

第１図は従来のパケット通信ネットワークの一例を示す
ブロック結ＩＩ図、第２図は２人力２出力ネットワーク
スイッチの１例を示す結線状態図、第３図はこの発明の
一実施例を示すブロック結線図、第４図はパケット再配
置用スイッチの一例を示すブロック結１１１１ｍである
。図において（１）は１６人力１６出力のノ（ケラト通信
ネットワークスイッチ、（３０）はネットワークスイッ
チ（３１）は入力パケット再配置装置、（３２）はネッ
トワーク状態検出装置、　（３Ｂ）はノ（ケラト再配置
用スイッチでおる。なお各図中同一符号は同−ｔたは相当部分を示すものと
する。代理人葛野信− 第１図第２図（０）（ｂ）

Claims

【特許請求の範囲】Ｎを正の整数とするとき２°　個の発信地と、同数の着
信地λの間でＮ段２Ｎ−１行に配列された２人力２出力
ネットワークスイッチを経て、情報パケットの交換を行
うパケット通信ネットワークにおいて、上記２人力２出
力ネットワークスイッチの各スイッチの状態を検出する
ネットワーク状態検出装置と、上記２　個の発信地からの情報パケットを入力し発信地
の配列順序をそのままの順序又は再配置した配列順序で
出力する入力パケット再配置装置と、この入力パケット
再配置装置の出力線を上記Ｎ１１２’−”行の２人力２
出力ネットワークスイッチの最初の段の入力線にそれぞ
れ対応して接続する手段と、上記ネットワーク状態検出
装置が回−避すぺきスイッチとして検出した２人力２出
力ネットワークスイッチの関連する発信地情報に従って
上記入力パケット再配置装置における配列順序変更を制
御する手段とを備え喪ことを特徴とするパケット通信ネ
ットワーク。