JPH0744544B2 - 自己ルーチング機能付き相互接続網 - Google Patents
自己ルーチング機能付き相互接続網Info
- Publication number
- JPH0744544B2 JPH0744544B2 JP476193A JP476193A JPH0744544B2 JP H0744544 B2 JPH0744544 B2 JP H0744544B2 JP 476193 A JP476193 A JP 476193A JP 476193 A JP476193 A JP 476193A JP H0744544 B2 JPH0744544 B2 JP H0744544B2
- Authority
- JP
- Japan
- Prior art keywords
- output
- input
- cell
- cells
- network
- 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.)
- Expired - Lifetime
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/15—Interconnection of switching modules
- H04L49/1515—Non-blocking multistage, e.g. Clos
- H04L49/153—ATM switching fabrics having parallel switch planes
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/15—Interconnection of switching modules
- H04L49/1553—Interconnection of ATM switching modules, e.g. ATM switching fabrics
- H04L49/1561—Distribute and route fabrics, e.g. Batcher-Banyan
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/40—Constructional details, e.g. power supply, mechanical construction or backplane
- H04L49/405—Physical details, e.g. power supply, mechanical construction or backplane of ATM switches
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04Q—SELECTING
- H04Q11/00—Selecting arrangements for multiplex systems
- H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
- H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
- H04Q11/0478—Provisions for broadband connections
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5681—Buffer or queue management
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Use Of Switch Circuits For Exchanges And Methods Of Control Of Multiplex Exchanges (AREA)
Description
【０００１】 （目次） 産業上の利用分野 従来の技術（図２１） 発明が解決しようとする課題 課題を解決するための手段（図１） 作用（図１） 実施例 ・第１実施例の説明（図２〜図１７） ・第２実施例の説明（図１８〜図１９） ・第３実施例の説明（図２０） 発明の効果
【０００２】
【産業上の利用分野】本発明は、ＡＴＭ交換機に用いて
好適な自己ルーチング機能付き相互接続網に関する。通
信網の高速広帯域化の要求が高まり、次世代の通信方式
として非同期転送モード（ＡＴＭ）が注目されている。
このため、ハードウェアによって自律的にルーチングを
行なう自己ルーチング機能を有し且つ高速動作が期待で
きる相互接続網がＡＴＭ交換機を実現するものとして有
望視されている。
好適な自己ルーチング機能付き相互接続網に関する。通
信網の高速広帯域化の要求が高まり、次世代の通信方式
として非同期転送モード（ＡＴＭ）が注目されている。
このため、ハードウェアによって自律的にルーチングを
行なう自己ルーチング機能を有し且つ高速動作が期待で
きる相互接続網がＡＴＭ交換機を実現するものとして有
望視されている。
【０００３】しかし、自己ルーチング型相互接続網であ
るバッチャー・バンヤン網（ＢＡＴＣＨＥＲ・ＢＡＮＹ
ＡＮ網）では、バッチャーソーティング網とバンヤンル
ーチング網のステージ数がルーチング処理による潜伏時
間（ｌａｔｅｎｃｙ）を左右するため、よりＡＴＭ交換
機に適した、ステージ数の少ない、すなわち潜伏時間の
少ない自己ルーチング型相互接続網の出現が要請されて
いる。
るバッチャー・バンヤン網（ＢＡＴＣＨＥＲ・ＢＡＮＹ
ＡＮ網）では、バッチャーソーティング網とバンヤンル
ーチング網のステージ数がルーチング処理による潜伏時
間（ｌａｔｅｎｃｙ）を左右するため、よりＡＴＭ交換
機に適した、ステージ数の少ない、すなわち潜伏時間の
少ない自己ルーチング型相互接続網の出現が要請されて
いる。
【０００４】
【従来の技術】図２１はバッチャー・バンヤン網を示す
ブロック図であるが、この図２１において、７０はバッ
チャー・バンヤン網であり、このバッチャー・バンヤン
網７０は、入線数および出線数がそれぞれＮ（Ｎ＝
２n ：ｎは自然数）の自己ルーチング機能をもつもの
で、バッチャーソーティング網７１，比較／廃棄回路７
２，集線回路７３およびバンヤン網７４をそなえて構成
されている。
ブロック図であるが、この図２１において、７０はバッ
チャー・バンヤン網であり、このバッチャー・バンヤン
網７０は、入線数および出線数がそれぞれＮ（Ｎ＝
２n ：ｎは自然数）の自己ルーチング機能をもつもの
で、バッチャーソーティング網７１，比較／廃棄回路７
２，集線回路７３およびバンヤン網７４をそなえて構成
されている。
【０００５】ここで、バッチャーソーティング網７１
は、入出力数がＮであり、ｎ（ｎ＋１）／２ステージ
（但し、ｎ＝ｌｏｇ2 Ｎ）から成り、セルのソーティン
グを行なうものである。比較／廃棄回路７２は、入出力
数がＮであり、バッチャーソーティング網７１によって
ソーティングされたセルのアドレスを比較して、不適当
なセルを廃棄するものである。
は、入出力数がＮであり、ｎ（ｎ＋１）／２ステージ
（但し、ｎ＝ｌｏｇ2 Ｎ）から成り、セルのソーティン
グを行なうものである。比較／廃棄回路７２は、入出力
数がＮであり、バッチャーソーティング網７１によって
ソーティングされたセルのアドレスを比較して、不適当
なセルを廃棄するものである。
【０００６】集線回路７３は、入出力数がＮであり、廃
棄されたセルを補って、セルの集線を行なうものであ
る。バンヤン網７４は、入出力数がＮであり、並べられ
たセルをその宛先アドレス情報の大小を基に対応する出
線に出力するものである。このような構成により、バッ
チャーソーティング網７１で、入力されたセルをその宛
先アドレス情報の大小を基に並べ替える（これをソーテ
ィング作用という）。このとき、同一の宛先アドレスを
持つセルは連続して並ぶことになる。
棄されたセルを補って、セルの集線を行なうものであ
る。バンヤン網７４は、入出力数がＮであり、並べられ
たセルをその宛先アドレス情報の大小を基に対応する出
線に出力するものである。このような構成により、バッ
チャーソーティング網７１で、入力されたセルをその宛
先アドレス情報の大小を基に並べ替える（これをソーテ
ィング作用という）。このとき、同一の宛先アドレスを
持つセルは連続して並ぶことになる。
【０００７】次に、比較／廃棄回路７２で、セルのアド
レスを比較し、同一アドレスを持つセルのうち、ただ一
つを残して残りを廃棄する（これをブロッキング作用と
いう）。そして、セルの廃棄が行なわれた場合は、セル
の並びが不連続になっているので、集線回路７３を通し
てセルの並びを連続になるように詰める。こうして、宛
先アドレスによりソーティングされ、連続した並びに詰
められたセルの列をバンヤン網７４に入力することによ
り、宛先アドレスに対応する出線にセルを出力する（こ
れをルーチング作用という）。
レスを比較し、同一アドレスを持つセルのうち、ただ一
つを残して残りを廃棄する（これをブロッキング作用と
いう）。そして、セルの廃棄が行なわれた場合は、セル
の並びが不連続になっているので、集線回路７３を通し
てセルの並びを連続になるように詰める。こうして、宛
先アドレスによりソーティングされ、連続した並びに詰
められたセルの列をバンヤン網７４に入力することによ
り、宛先アドレスに対応する出線にセルを出力する（こ
れをルーチング作用という）。
【０００８】
【発明が解決しようとする課題】しかしながら、このよ
うな自己ルーチング機能付き相互接続網では、ルーチン
グ処理による潜伏時間（ｌａｔｅｎｃｙ）を左右するス
テージ数が、バッチャーソーティング網及びバンヤン網
では、合計ｎ（ｎ＋３）／２ステージとなっている。
うな自己ルーチング機能付き相互接続網では、ルーチン
グ処理による潜伏時間（ｌａｔｅｎｃｙ）を左右するス
テージ数が、バッチャーソーティング網及びバンヤン網
では、合計ｎ（ｎ＋３）／２ステージとなっている。
【０００９】したがって、情報１ビット当たりの処理時
間を１〔ｂｉｔ−ｔｉｍｅ〕とすると、１ステージ当た
り１〔ｂｉｔ−ｔｉｍｅ〕の処理時間を必要とするた
め、バッチャーソーティング網及びバンヤン網では、合
計ｎ（ｎ＋３）／２〔ｂｉｔ−ｔｉｍｅ〕の処理時間を
費やし、これが潜伏時間の大きな部分を占める。このた
め、高速広帯域通信を目的とするＡＴＭ交換機に応用す
る場合、従来のバッチャー・バンヤン網は比較的ステー
ジ数が多いため、ルーティング処理による潜伏時間が大
きくなるという課題がある。
間を１〔ｂｉｔ−ｔｉｍｅ〕とすると、１ステージ当た
り１〔ｂｉｔ−ｔｉｍｅ〕の処理時間を必要とするた
め、バッチャーソーティング網及びバンヤン網では、合
計ｎ（ｎ＋３）／２〔ｂｉｔ−ｔｉｍｅ〕の処理時間を
費やし、これが潜伏時間の大きな部分を占める。このた
め、高速広帯域通信を目的とするＡＴＭ交換機に応用す
る場合、従来のバッチャー・バンヤン網は比較的ステー
ジ数が多いため、ルーティング処理による潜伏時間が大
きくなるという課題がある。
【００１０】本発明は、このような課題に鑑み創案され
たもので、従来のバッチャー・バンヤン網に対して同等
の機能を保持しながら、より少ない潜伏時間でルーチン
グ処理を行なえるようにした、自己ルーチング機能付き
相互接続網を提供することを目的とする。
たもので、従来のバッチャー・バンヤン網に対して同等
の機能を保持しながら、より少ない潜伏時間でルーチン
グ処理を行なえるようにした、自己ルーチング機能付き
相互接続網を提供することを目的とする。
【００１１】
【課題を解決するための手段】図１は本発明の原理ブロ
ック図であるが、この図１に示すように、情報通信単位
であるセルについてその宛先アドレス情報を基に自律的
にセルのルーチングを行なう自己ルーチング機能をもっ
た入線数および出線数がそれぞれＮ（Ｎ＝２n：ｎは自
然数）の相互接続網は、２i （ｉは自然数）組並列に接
続されたＮ／２ i 入力Ｎ出力バッチャー・バンヤン網１
０−１〜１０−２i および出力インタフェース１５をそ
なえて構成されている。
ック図であるが、この図１に示すように、情報通信単位
であるセルについてその宛先アドレス情報を基に自律的
にセルのルーチングを行なう自己ルーチング機能をもっ
た入線数および出線数がそれぞれＮ（Ｎ＝２n：ｎは自
然数）の相互接続網は、２i （ｉは自然数）組並列に接
続されたＮ／２ i 入力Ｎ出力バッチャー・バンヤン網１
０−１〜１０−２i および出力インタフェース１５をそ
なえて構成されている。
【００１２】ここで、各Ｎ／２i 入力Ｎ出力バッチャー
・バンヤン網１０−１〜１０−２iは、バッチャーソー
ティング網１１−１〜１１−２i と比較／廃棄手段１２
−１〜１２−２i と集線手段１３−１〜１３−２i とバ
ンヤン網１４−１〜１４−２ i とをそなえている。バッ
チャーソーティング網１１−１〜１１−２i は、入出力
数がＮ／２i であり、（ｎ−ｉ）（ｎ＋１−ｉ）／２ス
テージから成り、セルのソーティングを行なうものであ
る。
・バンヤン網１０−１〜１０−２iは、バッチャーソー
ティング網１１−１〜１１−２i と比較／廃棄手段１２
−１〜１２−２i と集線手段１３−１〜１３−２i とバ
ンヤン網１４−１〜１４−２ i とをそなえている。バッ
チャーソーティング網１１−１〜１１−２i は、入出力
数がＮ／２i であり、（ｎ−ｉ）（ｎ＋１−ｉ）／２ス
テージから成り、セルのソーティングを行なうものであ
る。
【００１３】比較／廃棄手段１２−１〜１２−２i は、
入出力数がＮ／２i であり、バッチャーソーティング網
１１−１〜１１−２i でソーティングされたセルのアド
レスを比較して同一アドレスを持つセルのうちただ一つ
を残して残りに廃棄処理を施すものである。集線手段１
３−１〜１３−２i は、入出力数がＮ／２i であり、比
較／廃棄手段１２−１〜１２−２i を通じて入力されて
きたセルの並びが連続になるように詰めるものである。
入出力数がＮ／２i であり、バッチャーソーティング網
１１−１〜１１−２i でソーティングされたセルのアド
レスを比較して同一アドレスを持つセルのうちただ一つ
を残して残りに廃棄処理を施すものである。集線手段１
３−１〜１３−２i は、入出力数がＮ／２i であり、比
較／廃棄手段１２−１〜１２−２i を通じて入力されて
きたセルの並びが連続になるように詰めるものである。
【００１４】バンヤン網１４−１〜１４−２i は、入出
力数がＮであり、集線手段１３−１〜１３−２i から出
力されたセルについて、そのアドレス情報を基に対応す
る出線に出力するものである（請求項１，８）。上記の
比較／廃棄回路１２−１〜１２−２i については、隣接
する入力セルのアドレスを比較する比較手段と、該比較
手段で同一アドレスをもつと判定されたセルについては
１つのセルを除いて残りのセルに廃棄処理を施す廃棄処
理手段とで構成することができる（請求項２）。
力数がＮであり、集線手段１３−１〜１３−２i から出
力されたセルについて、そのアドレス情報を基に対応す
る出線に出力するものである（請求項１，８）。上記の
比較／廃棄回路１２−１〜１２−２i については、隣接
する入力セルのアドレスを比較する比較手段と、該比較
手段で同一アドレスをもつと判定されたセルについては
１つのセルを除いて残りのセルに廃棄処理を施す廃棄処
理手段とで構成することができる（請求項２）。
【００１５】このとき、該廃棄処理手段は、１つのセル
を除いて残りのセルについて、セル中のセル有効ビット
を無効にすることにより、廃棄処理を施すように構成さ
れていて（請求項３）、更に該廃棄処理手段が、該比較
手段からの比較結果をラッチするラッチ回路と、該ラッ
チ回路からの出力と入力セルとを受けて、セル有効ビッ
ト情報またはセル無効ビット情報を出力するゲート回路
と、セル中のセル有効ビット挿入位置タイミングで該ゲ
ート回路からの出力をセル中に挿入するセレクタとをそ
なえて構成されている（請求項４）。
を除いて残りのセルについて、セル中のセル有効ビット
を無効にすることにより、廃棄処理を施すように構成さ
れていて（請求項３）、更に該廃棄処理手段が、該比較
手段からの比較結果をラッチするラッチ回路と、該ラッ
チ回路からの出力と入力セルとを受けて、セル有効ビッ
ト情報またはセル無効ビット情報を出力するゲート回路
と、セル中のセル有効ビット挿入位置タイミングで該ゲ
ート回路からの出力をセル中に挿入するセレクタとをそ
なえて構成されている（請求項４）。
【００１６】さらに、該集線手段１３−１〜１３−２i
を、比較／廃棄手段１２−１〜１２−２i を通じて入力
されてきたセルが有効か無効かを判定する判定手段と、
該判定手段での判定結果に基づきセルの並びを連続にな
るように詰めるセル詰め手段とをそなえて構成すること
ができる（請求項５）。このとき、該判定手段が、セル
中のセル有効ビット情報をラッチするラッチ回路で構成
されるとともに、該セル詰め手段が、該ラッチ回路から
の判定結果に基づきセルの並びを連続になるように詰め
るセレクタ群を含んで構成される（請求項６）。
を、比較／廃棄手段１２−１〜１２−２i を通じて入力
されてきたセルが有効か無効かを判定する判定手段と、
該判定手段での判定結果に基づきセルの並びを連続にな
るように詰めるセル詰め手段とをそなえて構成すること
ができる（請求項５）。このとき、該判定手段が、セル
中のセル有効ビット情報をラッチするラッチ回路で構成
されるとともに、該セル詰め手段が、該ラッチ回路から
の判定結果に基づきセルの並びを連続になるように詰め
るセレクタ群を含んで構成される（請求項６）。
【００１７】また、各Ｎ／２i 入力Ｎ出力バッチャー・
バンヤン網１０−１〜１０−２i において、その集線手
段１３−１〜１３−２i のＮ／２i 出力がそのバンヤン
網１４−１〜１４−２i のＮ入力の一部として端から順
に入力され、該バンヤン網１４−１〜１４−２i の他の
入力は未接続状態になっている（請求項７）。ところ
で、出力インタフェース１５は、その出線毎に、各Ｎ／
２i 入力Ｎ出力バッチャー・バンヤン網のＮ出力を受け
る待ち行列式のバッファ回路をそなえるように構成され
てもよい（請求項９）。
バンヤン網１０−１〜１０−２i において、その集線手
段１３−１〜１３−２i のＮ／２i 出力がそのバンヤン
網１４−１〜１４−２i のＮ入力の一部として端から順
に入力され、該バンヤン網１４−１〜１４−２i の他の
入力は未接続状態になっている（請求項７）。ところ
で、出力インタフェース１５は、その出線毎に、各Ｎ／
２i 入力Ｎ出力バッチャー・バンヤン網のＮ出力を受け
る待ち行列式のバッファ回路をそなえるように構成され
てもよい（請求項９）。
【００１８】また、該出力インタフェース１５は、その
出線毎に、各Ｎ／２i 入力Ｎ出力バッチャー・バンヤン
網１０−１〜１０−２i のＮ出力を受け、同一の出力に
セルが重複して到着した場合は、いずれか一つを選択し
て他方を廃棄するような調停手段をそなえるように構成
されてもよい（請求項１０）。このとき、該調停手段
は、該Ｎ／２i 入力Ｎ出力バッチャー・バンヤン網１０
−１〜１０−２i のＮ出力を受け、同一の出力にセルが
重複して到着した場合は、特定のＮ／２i 入力Ｎ出力バ
ッチャー・バンヤン網からの出力を選択して他方を廃棄
するように構成することができ（請求項１１）、この場
合、該調停手段が、該特定のＮ／２i 入力Ｎ出力バッチ
ャー・バンヤン網からのセルの存在を判定する判定手段
と、該判定手段での判定結果に基づき該特定のＮ／２i
入力Ｎ出力バッチャー・バンヤン網からのセルが存在す
る場合にはこの特定のＮ／２i 入力Ｎ出力バッチャー・
バンヤン網からの出力を優先的に選択するセレクタとを
そなえて構成される（請求項１２）。
出線毎に、各Ｎ／２i 入力Ｎ出力バッチャー・バンヤン
網１０−１〜１０−２i のＮ出力を受け、同一の出力に
セルが重複して到着した場合は、いずれか一つを選択し
て他方を廃棄するような調停手段をそなえるように構成
されてもよい（請求項１０）。このとき、該調停手段
は、該Ｎ／２i 入力Ｎ出力バッチャー・バンヤン網１０
−１〜１０−２i のＮ出力を受け、同一の出力にセルが
重複して到着した場合は、特定のＮ／２i 入力Ｎ出力バ
ッチャー・バンヤン網からの出力を選択して他方を廃棄
するように構成することができ（請求項１１）、この場
合、該調停手段が、該特定のＮ／２i 入力Ｎ出力バッチ
ャー・バンヤン網からのセルの存在を判定する判定手段
と、該判定手段での判定結果に基づき該特定のＮ／２i
入力Ｎ出力バッチャー・バンヤン網からのセルが存在す
る場合にはこの特定のＮ／２i 入力Ｎ出力バッチャー・
バンヤン網からの出力を優先的に選択するセレクタとを
そなえて構成される（請求項１２）。
【００１９】
【作用】上述の本発明の自己ルーチング機能付き相互接
続網では、入線数をＮ／２i 入力に分割し、Ｎ／２i 入
力Ｎ出力バッチャー・バンヤン網１０−１〜１０−２i
に入力する。各Ｎ／２i 入力Ｎ出力バッチャー・バンヤ
ン網１０−１〜１０−２ i では、次のような作用を行な
う。
続網では、入線数をＮ／２i 入力に分割し、Ｎ／２i 入
力Ｎ出力バッチャー・バンヤン網１０−１〜１０−２i
に入力する。各Ｎ／２i 入力Ｎ出力バッチャー・バンヤ
ン網１０−１〜１０−２ i では、次のような作用を行な
う。
【００２０】まず、バッチャーソーティング網１１−１
〜１１−２i で、セルのソーティングを行ない、比較／
廃棄手段１２−１〜１２−２i で、バッチャーソーティ
ング網１１−１〜１１−２i でソーティングされたセル
のアドレスを比較して同一アドレスを持つセルのうちた
だ一つを残して残りに廃棄処理を施す。そして、集線手
段１３−１〜１３−２i で、比較／廃棄手段１２−１〜
１２−２i を通じて入力されてきたセルの並びが連続に
なるように詰める。その後は、バンヤン網１４−１〜１
４−２i で、集線手段１３−１〜１３−２i から出力さ
れたセルについて、そのアドレス情報を基に対応する出
線に出力する（請求項１）。
〜１１−２i で、セルのソーティングを行ない、比較／
廃棄手段１２−１〜１２−２i で、バッチャーソーティ
ング網１１−１〜１１−２i でソーティングされたセル
のアドレスを比較して同一アドレスを持つセルのうちた
だ一つを残して残りに廃棄処理を施す。そして、集線手
段１３−１〜１３−２i で、比較／廃棄手段１２−１〜
１２−２i を通じて入力されてきたセルの並びが連続に
なるように詰める。その後は、バンヤン網１４−１〜１
４−２i で、集線手段１３−１〜１３−２i から出力さ
れたセルについて、そのアドレス情報を基に対応する出
線に出力する（請求項１）。
【００２１】なお、比較／廃棄回路１２−１〜１２−２
i を比較手段と廃棄処理手段とで構成した場合（請求項
２）は、比較手段で、隣接する入力セルのアドレスを比
較し、廃棄処理手段で、該比較手段で同一アドレスをも
つと判定されたセルについては１つのセルを除いて残り
のセルに廃棄処理を施す。このとき、廃棄処理手段を、
１つのセルを除いて残りのセルについて、セル中のセル
有効ビットを無効にすることにより、廃棄処理を施すよ
うに構成し（請求項３）、更に該廃棄処理手段をラッチ
回路とゲート回路とセレクタとをそなえて構成した場合
（請求項４）は、ラッチ回路で、該比較手段からの比較
結果をラッチし、ゲート回路で、該ラッチ回路からの出
力と入力セルとを受けて、セル有効ビット情報またはセ
ル無効ビット情報を出力し、セレクタによって、セル中
のセル有効ビット挿入位置タイミングで、該ゲート回路
からの出力をセル中に挿入する。これにより、廃棄処理
手段によって、１つのセルを除いて残りのセルについ
て、セル中のセル有効ビットを無効にすることにより、
廃棄処理を施すことが行なわれる。
i を比較手段と廃棄処理手段とで構成した場合（請求項
２）は、比較手段で、隣接する入力セルのアドレスを比
較し、廃棄処理手段で、該比較手段で同一アドレスをも
つと判定されたセルについては１つのセルを除いて残り
のセルに廃棄処理を施す。このとき、廃棄処理手段を、
１つのセルを除いて残りのセルについて、セル中のセル
有効ビットを無効にすることにより、廃棄処理を施すよ
うに構成し（請求項３）、更に該廃棄処理手段をラッチ
回路とゲート回路とセレクタとをそなえて構成した場合
（請求項４）は、ラッチ回路で、該比較手段からの比較
結果をラッチし、ゲート回路で、該ラッチ回路からの出
力と入力セルとを受けて、セル有効ビット情報またはセ
ル無効ビット情報を出力し、セレクタによって、セル中
のセル有効ビット挿入位置タイミングで、該ゲート回路
からの出力をセル中に挿入する。これにより、廃棄処理
手段によって、１つのセルを除いて残りのセルについ
て、セル中のセル有効ビットを無効にすることにより、
廃棄処理を施すことが行なわれる。
【００２２】さらに、該集線手段１３−１〜１３−２i
を、ラッチ回路を有する判定手段とセレクタ群を含んだ
セル詰め手段とをそなえて構成した場合（請求項５，
６）は、判定手段で、比較／廃棄手段１２−１〜１２−
２i を通じて入力されてきたセルが有効か無効かを判定
し、セル詰め手段で、該判定手段での判定結果に基づき
セルの並びを連続になるように詰める。
を、ラッチ回路を有する判定手段とセレクタ群を含んだ
セル詰め手段とをそなえて構成した場合（請求項５，
６）は、判定手段で、比較／廃棄手段１２−１〜１２−
２i を通じて入力されてきたセルが有効か無効かを判定
し、セル詰め手段で、該判定手段での判定結果に基づき
セルの並びを連続になるように詰める。
【００２３】また、各Ｎ／２i 入力Ｎ出力バッチャー・
バンヤン網１０−１〜１０−２i において、その集線手
段１３−１〜１３−２i のＮ／２i 出力がそのバンヤン
網１４−１〜１４−２i のＮ入力の一部として端から順
に入力され、該バンヤン網１４−１〜１４−２i の他の
入力は未接続状態になっている（請求項７）。ところ
で、各Ｎ／２i 入力Ｎ出力バッチャー・バンヤン網１０
−１〜１０−２ i のＮ出力は出力インタフェース１５に
入力される（請求項８）が、この出力インタフェース１
５として、その出線毎に、待ち行列式のバッファ回路を
そなえた場合（請求項９）は、各Ｎ／２i 入力Ｎ出力バ
ッチャー・バンヤン網のＮ出力を受ける待ち行列式のバ
ッファ回路で受けて、Ｎ出力とする。
バンヤン網１０−１〜１０−２i において、その集線手
段１３−１〜１３−２i のＮ／２i 出力がそのバンヤン
網１４−１〜１４−２i のＮ入力の一部として端から順
に入力され、該バンヤン網１４−１〜１４−２i の他の
入力は未接続状態になっている（請求項７）。ところ
で、各Ｎ／２i 入力Ｎ出力バッチャー・バンヤン網１０
−１〜１０−２ i のＮ出力は出力インタフェース１５に
入力される（請求項８）が、この出力インタフェース１
５として、その出線毎に、待ち行列式のバッファ回路を
そなえた場合（請求項９）は、各Ｎ／２i 入力Ｎ出力バ
ッチャー・バンヤン網のＮ出力を受ける待ち行列式のバ
ッファ回路で受けて、Ｎ出力とする。
【００２４】また、該出力インタフェース１５を、その
出線毎に、調停手段をそなえるように構成した場合（請
求項１０）は、各Ｎ／２i 入力Ｎ出力バッチャー・バン
ヤン網１０−１〜１０−２i のＮ出力を調停手段で受
け、この調停手段によって、同一の出力にセルが重複し
て到着した場合は、いずれか一つを選択して他方を廃棄
する。このとき、該調停手段によって、同一の出力にセ
ルが重複して到着した場合は、特定のＮ／２i 入力Ｎ出
力バッチャー・バンヤン網からの出力を選択して他方を
廃棄することもできる（請求項１１，１２）。
出線毎に、調停手段をそなえるように構成した場合（請
求項１０）は、各Ｎ／２i 入力Ｎ出力バッチャー・バン
ヤン網１０−１〜１０−２i のＮ出力を調停手段で受
け、この調停手段によって、同一の出力にセルが重複し
て到着した場合は、いずれか一つを選択して他方を廃棄
する。このとき、該調停手段によって、同一の出力にセ
ルが重複して到着した場合は、特定のＮ／２i 入力Ｎ出
力バッチャー・バンヤン網からの出力を選択して他方を
廃棄することもできる（請求項１１，１２）。
【００２５】
【実施例】以下、図面を参照して本発明の実施例を説明
する。 （ａ）第１実施例の説明 図２は本発明の第１実施例を示すブロック図で、この図
２において、２０−１，２０−２はＮ／２入力Ｎ出力バ
ッチャー・バンヤン網であり、このＮ／２入力Ｎ出力バ
ッチャー・バンヤン網２０−１，２０−２は、自己ルー
チング機能をもつもので、２組並列に接続されており、
それぞれバッチャーソーティング網２１−１，２１−
２，比較／廃棄回路２２−１，２２−２，集線回路２３
−１，２３−２およびバンヤン網２４−１，２４−２を
そなえて構成されている。なお、Ｎ＝２n ，即ちｎ＝ｌ
ｏｇ2 Ｎ（ｎは自然数）である。
する。 （ａ）第１実施例の説明 図２は本発明の第１実施例を示すブロック図で、この図
２において、２０−１，２０−２はＮ／２入力Ｎ出力バ
ッチャー・バンヤン網であり、このＮ／２入力Ｎ出力バ
ッチャー・バンヤン網２０−１，２０−２は、自己ルー
チング機能をもつもので、２組並列に接続されており、
それぞれバッチャーソーティング網２１−１，２１−
２，比較／廃棄回路２２−１，２２−２，集線回路２３
−１，２３−２およびバンヤン網２４−１，２４−２を
そなえて構成されている。なお、Ｎ＝２n ，即ちｎ＝ｌ
ｏｇ2 Ｎ（ｎは自然数）である。
【００２６】まず、バッチャーソーティング網２１−１
は、Ｎ／２入力Ｎ／２出力で、ｎ（ｎ−１）／２ステー
ジから成り、セルのソーティングを行なうものである。
例えば、４×４（Ｎ＝８）のバッチャーソーティング網
２１−１の構成を示すと、図３のようになる。すなわ
ち、この４×４のバッチャーソーティング網２１−１
は、３つのステージからなり、各ステージは、２つの２
×２の単位スイッチ２１１で構成されている。
は、Ｎ／２入力Ｎ／２出力で、ｎ（ｎ−１）／２ステー
ジから成り、セルのソーティングを行なうものである。
例えば、４×４（Ｎ＝８）のバッチャーソーティング網
２１−１の構成を示すと、図３のようになる。すなわ
ち、この４×４のバッチャーソーティング網２１−１
は、３つのステージからなり、各ステージは、２つの２
×２の単位スイッチ２１１で構成されている。
【００２７】ここで、単位スイッチ２１１は、入力端Ａ
と入力端Ｂに入ってくる入力セルの宛先アドレスＤＡ
（図１３の（ａ）参照）を比較して、入力端Ａに入って
くるセルのアドレスＤＡが入力端Ｂに入ってくるセルの
アドレスＤＡと等しいか小さい場合（Ａ≦Ｂと表記）
は、図４（ａ）に示すように、各セルをクロスさせずに
ストレートで出力する一方、入力端Ａに入ってくるセル
のアドレスが入力端Ｂに入ってくるセルのアドレスＤＡ
よりも大きい場合（Ａ＞Ｂと表記）は、図４（ｂ）に示
すように、各セルをクロスさせて出力するものである。
と入力端Ｂに入ってくる入力セルの宛先アドレスＤＡ
（図１３の（ａ）参照）を比較して、入力端Ａに入って
くるセルのアドレスＤＡが入力端Ｂに入ってくるセルの
アドレスＤＡと等しいか小さい場合（Ａ≦Ｂと表記）
は、図４（ａ）に示すように、各セルをクロスさせずに
ストレートで出力する一方、入力端Ａに入ってくるセル
のアドレスが入力端Ｂに入ってくるセルのアドレスＤＡ
よりも大きい場合（Ａ＞Ｂと表記）は、図４（ｂ）に示
すように、各セルをクロスさせて出力するものである。
【００２８】このような動作を行なう単位スイッチ２１
１を図３に示すように接続することで、入線Ｉ0 〜Ｉ3
を通じて入ってくるセルをアドレスの小さい順に出力す
ることができる（図１４参照）。比較／廃棄回路２２−
１は、Ｎ／２入力Ｎ／２出力で、バッチャーソーティン
グ網２１−１でソーティングされたｎビットのセル宛先
アドレスを比較して、もし同一の宛先アドレスを持つセ
ルが存在した場合は、その中のただ一つを残して残りに
廃棄処理を施すものである。
１を図３に示すように接続することで、入線Ｉ0 〜Ｉ3
を通じて入ってくるセルをアドレスの小さい順に出力す
ることができる（図１４参照）。比較／廃棄回路２２−
１は、Ｎ／２入力Ｎ／２出力で、バッチャーソーティン
グ網２１−１でソーティングされたｎビットのセル宛先
アドレスを比較して、もし同一の宛先アドレスを持つセ
ルが存在した場合は、その中のただ一つを残して残りに
廃棄処理を施すものである。
【００２９】すなわち、この比較／廃棄回路２２−１
は、４入力タイプのものでは、図５に示すように、隣接
する入線間での比較・廃棄処理を行なうために、隣接す
る入線間に、それぞれ排他的論理和回路２２１，ＯＲゲ
ート２２２，ラッチ回路２２３，ＡＮＤゲート２２４，
セレクタ２２５をそなえている。ここで、排他的論理和
回路２２１は、隣接する入線からの信号を受けて各セル
のアドレスが同一かどうかを比較するもので、もし同じ
であれば、「０」出力を、違っていれば、「１」出力を
出す。これにより、排他的論理和回路２２１は、入力セ
ルのアドレスを比較する比較手段を構成する。
は、４入力タイプのものでは、図５に示すように、隣接
する入線間での比較・廃棄処理を行なうために、隣接す
る入線間に、それぞれ排他的論理和回路２２１，ＯＲゲ
ート２２２，ラッチ回路２２３，ＡＮＤゲート２２４，
セレクタ２２５をそなえている。ここで、排他的論理和
回路２２１は、隣接する入線からの信号を受けて各セル
のアドレスが同一かどうかを比較するもので、もし同じ
であれば、「０」出力を、違っていれば、「１」出力を
出す。これにより、排他的論理和回路２２１は、入力セ
ルのアドレスを比較する比較手段を構成する。
【００３０】ＯＲゲート２２２は、排他的論理和回路２
２１出力とラッチ回路２２３出力との論理和をとって、
その出力をラッチ回路２２３のデータ入力端（Ｄ入力
端）に供給するものである。ラッチ回路２２３は、Ｄフ
リップフロップからなり、そのＤ入力端にＯＲゲート２
２２出力を受け、そのリセット端にリセット信号（図１
３（ｄ）参照）を受け、そのクロック端にクロック信号
（図１３（ｃ）参照）を受け、その出力はＯＲゲート２
２２の入力にフィードバックされるとともに、ＡＮＤゲ
ート２２４に入力されるようになっている。これによ
り，排他的論理和回路２２１での比較結果をラッチする
ことができる。
２１出力とラッチ回路２２３出力との論理和をとって、
その出力をラッチ回路２２３のデータ入力端（Ｄ入力
端）に供給するものである。ラッチ回路２２３は、Ｄフ
リップフロップからなり、そのＤ入力端にＯＲゲート２
２２出力を受け、そのリセット端にリセット信号（図１
３（ｄ）参照）を受け、そのクロック端にクロック信号
（図１３（ｃ）参照）を受け、その出力はＯＲゲート２
２２の入力にフィードバックされるとともに、ＡＮＤゲ
ート２２４に入力されるようになっている。これによ
り，排他的論理和回路２２１での比較結果をラッチする
ことができる。
【００３１】なお、クロック信号は図１３（ｂ）に示す
システムクロックと同期している。ＡＮＤゲート２２４
は、ラッチ回路２２３出力と隣接する入線のうち入線番
号が大きい方の入線からの信号との論理積をとって、そ
の出力をセレクタ２２５に入力するものである。セレク
タ２２５は、ＡＮＤゲート２２４からの出力を入力端ａ
で受け、入線のうち入線番号が大きい方の入線からの信
号を入力端ｂで受け、ＡＣＴビットタイミング信号（図
１３（ｅ）参照；この信号は図１３からもわかるように
セル中のＡＣＴビット（セル有効ビット情報）挿入位置
で「１」となり、その他で「０」となる信号である。）
が「１」のときに、入力端ａの信号を出力し（図６
（ａ）参照）、ＡＣＴビットタイミング信号が「０」の
ときに、入力端ｂの信号を出力する（図６（ｂ）参照）
ものである。
システムクロックと同期している。ＡＮＤゲート２２４
は、ラッチ回路２２３出力と隣接する入線のうち入線番
号が大きい方の入線からの信号との論理積をとって、そ
の出力をセレクタ２２５に入力するものである。セレク
タ２２５は、ＡＮＤゲート２２４からの出力を入力端ａ
で受け、入線のうち入線番号が大きい方の入線からの信
号を入力端ｂで受け、ＡＣＴビットタイミング信号（図
１３（ｅ）参照；この信号は図１３からもわかるように
セル中のＡＣＴビット（セル有効ビット情報）挿入位置
で「１」となり、その他で「０」となる信号である。）
が「１」のときに、入力端ａの信号を出力し（図６
（ａ）参照）、ＡＣＴビットタイミング信号が「０」の
ときに、入力端ｂの信号を出力する（図６（ｂ）参照）
ものである。
【００３２】これにより、もし隣接する入線の各セルの
アドレスが同一であれば、ラッチ回路２２３は「０」と
なり、異なれば、ラッチ回路２２３は「１」となってい
るので、ＡＣＴビット挿入位置でのＡＮＤゲート２２４
出力を考えると、隣接する入線の各セルのアドレスが同
一であれば、「０」となり、異なれば、「１」となるこ
とがわかる。そして、セレクタ２２５は、ＡＣＴビット
タイミング信号が「１」のときに、入力端ａの信号を出
力するので、セレクタ２２５から出力されるセルは、隣
接するセルのアドレスが同一であれば、そのＡＣＴビッ
ト挿入位置が「０」に置換され、隣接するセルのアドレ
スが異なっていて、且つ、ＡＣＴビット＝「１」であれ
ば、そのＡＣＴビット挿入位置は「１」のままとなる。
アドレスが同一であれば、ラッチ回路２２３は「０」と
なり、異なれば、ラッチ回路２２３は「１」となってい
るので、ＡＣＴビット挿入位置でのＡＮＤゲート２２４
出力を考えると、隣接する入線の各セルのアドレスが同
一であれば、「０」となり、異なれば、「１」となるこ
とがわかる。そして、セレクタ２２５は、ＡＣＴビット
タイミング信号が「１」のときに、入力端ａの信号を出
力するので、セレクタ２２５から出力されるセルは、隣
接するセルのアドレスが同一であれば、そのＡＣＴビッ
ト挿入位置が「０」に置換され、隣接するセルのアドレ
スが異なっていて、且つ、ＡＣＴビット＝「１」であれ
ば、そのＡＣＴビット挿入位置は「１」のままとなる。
【００３３】このようにセルのＡＣＴビット挿入位置が
「０」になると、このセルはその後廃棄セルとして処理
されるのである。これにより、上記のＡＮＤゲート２２
４は、ラッチ回路２２３からの出力と入力セルとを受け
て、セル有効ビット情報またはセル無効ビット情報を出
力するゲート回路を構成し、セレクタ２２５は、セル中
のセル有効ビット挿入位置タイミングで、ＡＮＤゲート
２２４からの出力をセル中に挿入する回路として構成さ
れる。
「０」になると、このセルはその後廃棄セルとして処理
されるのである。これにより、上記のＡＮＤゲート２２
４は、ラッチ回路２２３からの出力と入力セルとを受け
て、セル有効ビット情報またはセル無効ビット情報を出
力するゲート回路を構成し、セレクタ２２５は、セル中
のセル有効ビット挿入位置タイミングで、ＡＮＤゲート
２２４からの出力をセル中に挿入する回路として構成さ
れる。
【００３４】例えば、図１５に示すように、入線Ｉ0 〜
Ｉ3 に対応するセルのアドレスＤＡがそれぞれ０，１，
１，５である場合は、入線Ｉ0 ，Ｉ1 ；Ｉ2 ，Ｉ3 間の
排他的論理和回路２２１は、それぞれ「１」出力を出
し、入線Ｉ1 ，Ｉ2 間の排他的論理和回路２２１は、
「０」出力を出し、これにより、入線Ｉ1 ，Ｉ3 用のセ
レクタ２２５は、セルのＡＣＴビット挿入位置を「１」
のままとし、入線Ｉ2 用のセレクタ２２５は、セルのＡ
ＣＴビット挿入位置を「０」に置き換える。その結果、
出線Ｏ0 ，Ｏ1 ，Ｏ3 からのセルは有効なセルとして出
力され、出線Ｏ2 からのセルは無効なセルとして出力さ
れる。
Ｉ3 に対応するセルのアドレスＤＡがそれぞれ０，１，
１，５である場合は、入線Ｉ0 ，Ｉ1 ；Ｉ2 ，Ｉ3 間の
排他的論理和回路２２１は、それぞれ「１」出力を出
し、入線Ｉ1 ，Ｉ2 間の排他的論理和回路２２１は、
「０」出力を出し、これにより、入線Ｉ1 ，Ｉ3 用のセ
レクタ２２５は、セルのＡＣＴビット挿入位置を「１」
のままとし、入線Ｉ2 用のセレクタ２２５は、セルのＡ
ＣＴビット挿入位置を「０」に置き換える。その結果、
出線Ｏ0 ，Ｏ1 ，Ｏ3 からのセルは有効なセルとして出
力され、出線Ｏ2 からのセルは無効なセルとして出力さ
れる。
【００３５】集線回路２３−１は、Ｎ／２入力Ｎ／２出
力で、比較／廃棄手段２２−１を通じて入力されてきた
セルの並びが連続になるように詰めるものであるが、こ
のために、図７に示すように、比較／廃棄回路２２−１
を通じて入力されてきたセルが有効か無効かを判定する
判定回路２３１と、この判定回路２３１での判定結果に
基づき、セルの並びを連続になるように詰めるセル詰め
回路２３２とをそなえている。
力で、比較／廃棄手段２２−１を通じて入力されてきた
セルの並びが連続になるように詰めるものであるが、こ
のために、図７に示すように、比較／廃棄回路２２−１
を通じて入力されてきたセルが有効か無効かを判定する
判定回路２３１と、この判定回路２３１での判定結果に
基づき、セルの並びを連続になるように詰めるセル詰め
回路２３２とをそなえている。
【００３６】例えば４入力タイプの集線回路２３−１で
は、図７に示すように、判定回路２３１が、セル中のセ
ル有効ビット情報をラッチする３つのラッチ回路２３１
１〜２３１３で構成されるとともに、セル詰め回路２３
２が、ラッチ回路２３１１〜２３１３からの判定結果に
基づき、セルの並びを連続になるように詰めるセレクタ
群２３２１を含んで構成される。
は、図７に示すように、判定回路２３１が、セル中のセ
ル有効ビット情報をラッチする３つのラッチ回路２３１
１〜２３１３で構成されるとともに、セル詰め回路２３
２が、ラッチ回路２３１１〜２３１３からの判定結果に
基づき、セルの並びを連続になるように詰めるセレクタ
群２３２１を含んで構成される。
【００３７】ここで、各ラッチ回路２３１１〜２３１３
は、Ｄフリップフロップからなり、そのＤ入力端に入線
Ｉ1 〜Ｉ3 の信号を受け、そのクロック端にクロック信
号（図１３（ｃ）参照）とＡＣＴビットタイミング信号
（図１３（ｅ）参照）との論理積信号（ＡＮＤゲート２
３３出力）を受け、その出力がセレクタ群２３２１を構
成するセレクタ２３２２に入力されるようになってい
る。これにより各ラッチ回路２３１１〜２３１３は、セ
ル中のセル有効ビット情報をラッチして、セルがもし無
効処理を施されていないものであれば、セレクタ信号
「１」をセレクタ２３２２に出力し、セルがもし無効処
理を施されているものであれば、セレクタ信号「０」を
セレクタ２３２２に出力することができる。
は、Ｄフリップフロップからなり、そのＤ入力端に入線
Ｉ1 〜Ｉ3 の信号を受け、そのクロック端にクロック信
号（図１３（ｃ）参照）とＡＣＴビットタイミング信号
（図１３（ｅ）参照）との論理積信号（ＡＮＤゲート２
３３出力）を受け、その出力がセレクタ群２３２１を構
成するセレクタ２３２２に入力されるようになってい
る。これにより各ラッチ回路２３１１〜２３１３は、セ
ル中のセル有効ビット情報をラッチして、セルがもし無
効処理を施されていないものであれば、セレクタ信号
「１」をセレクタ２３２２に出力し、セルがもし無効処
理を施されているものであれば、セレクタ信号「０」を
セレクタ２３２２に出力することができる。
【００３８】また、セレクタ群２３２１を構成するセレ
クタ２３２２は次のように配置されている。すなわち、
入線Ｉ0 に対応するラインにはセレクタはないが、入線
Ｉ1〜Ｉ3 に対応するラインに、それぞれ３つずつセレ
クタ２３２２が設けられている。各セレクタ２３２２
は、対応するラッチ回路２３１１〜２３１３出力が
「１」のときに、入力端ａの信号を出力し、対応するラ
ッチ回路２３１１〜２３１３出力が「０」のときに、入
力端ｂの信号を出力するものである。
クタ２３２２は次のように配置されている。すなわち、
入線Ｉ0 に対応するラインにはセレクタはないが、入線
Ｉ1〜Ｉ3 に対応するラインに、それぞれ３つずつセレ
クタ２３２２が設けられている。各セレクタ２３２２
は、対応するラッチ回路２３１１〜２３１３出力が
「１」のときに、入力端ａの信号を出力し、対応するラ
ッチ回路２３１１〜２３１３出力が「０」のときに、入
力端ｂの信号を出力するものである。
【００３９】したがって、もし入線番号の小さい方の入
線のセルが無効処理を施されたもの（ＡＣＴビットが
「０」のもの）である場合は、入線番号が大きい方の入
線でセルが有効なもの（ＡＣＴビットが「１」のもの）
がこの入線番号の小さい方の入線に対応する出線から出
力される。例えば、図１６に示すように、入線Ｉ1 とＩ
2 のセルが同一アドレスであったため、入線Ｉ2 のセル
が無効処理を施されたものである場合は、入線Ｉ0 とＩ
1とのセルは図１６の太線で示すように対応する出線Ｏ
0 とＯ1 とから出力されるが、入線Ｉ2 のセルは途中の
セレクタ２３２２でカットされ、入線Ｉ3 のセルが入線
Ｉ2 に対応する出線Ｏ2 から出力される。すなわち、各
ラインに設けられたセレクタ２３２２は出線側に近いも
のが最も優先度が高く、出線側から遠ざかるにつれて優
先度が下がっていく。これにより、セルの並びを入線番
号の小さい方に詰めることができる。
線のセルが無効処理を施されたもの（ＡＣＴビットが
「０」のもの）である場合は、入線番号が大きい方の入
線でセルが有効なもの（ＡＣＴビットが「１」のもの）
がこの入線番号の小さい方の入線に対応する出線から出
力される。例えば、図１６に示すように、入線Ｉ1 とＩ
2 のセルが同一アドレスであったため、入線Ｉ2 のセル
が無効処理を施されたものである場合は、入線Ｉ0 とＩ
1とのセルは図１６の太線で示すように対応する出線Ｏ
0 とＯ1 とから出力されるが、入線Ｉ2 のセルは途中の
セレクタ２３２２でカットされ、入線Ｉ3 のセルが入線
Ｉ2 に対応する出線Ｏ2 から出力される。すなわち、各
ラインに設けられたセレクタ２３２２は出線側に近いも
のが最も優先度が高く、出線側から遠ざかるにつれて優
先度が下がっていく。これにより、セルの並びを入線番
号の小さい方に詰めることができる。
【００４０】なお、セルの並びを入線番号の小さい方に
詰めることにより、入線番号の大きい入線対応の出線か
らは無効セルを出力しておく必要があるが、このため
に、図７に示すように、無効セル発生回路２３４が設け
られている。これにより、上記の例では、入線Ｉ3 に対
応する出線Ｏ3 からは無効セルが出力されることになる
（図１６参照）。
詰めることにより、入線番号の大きい入線対応の出線か
らは無効セルを出力しておく必要があるが、このため
に、図７に示すように、無効セル発生回路２３４が設け
られている。これにより、上記の例では、入線Ｉ3 に対
応する出線Ｏ3 からは無効セルが出力されることになる
（図１６参照）。
【００４１】また、図７において、２３５はセルをＡＣ
Ｔビット位置まで待機させておくバッファである。バン
ヤン網２４−１は、Ｎ入力Ｎ出力で、図８に示すように
集線回路２３−１のＮ／２出力をそのＮ入力のうち一方
の端から連続したＮ／２本分の入力に接続し、その他の
Ｎ／２本分の入力は未接続状態となっているもので、連
続して並んだ集線回路２３−１からのセルについて、そ
のアドレス情報を基に対応する出線に出力するものであ
る。
Ｔビット位置まで待機させておくバッファである。バン
ヤン網２４−１は、Ｎ入力Ｎ出力で、図８に示すように
集線回路２３−１のＮ／２出力をそのＮ入力のうち一方
の端から連続したＮ／２本分の入力に接続し、その他の
Ｎ／２本分の入力は未接続状態となっているもので、連
続して並んだ集線回路２３−１からのセルについて、そ
のアドレス情報を基に対応する出線に出力するものであ
る。
【００４２】例えば、８×８（Ｎ＝８）のバンヤン網２
４−１の構成を示すと、図９のようになる。すなわち、
この８×８のバンヤン網２４−１は、３つのステージか
らなり、各ステージは、４つの２×２の単位スイッチ２
４１で構成されている。ここで、単位スイッチ２４１
は、入力端Ａと入力端Ｂに入ってくる入力セルの宛先ア
ドレスＤＡ（図１３の（ａ）参照）のうち割り当てられ
たチェックビットによって、状態が決まるもので、両入
力端Ａ，Ｂのチェックビットの組み合わせによって、そ
の状態は図１０（ａ）〜（ｅ）のようになる。なお、ｘ
は無効セルのチェックビットである。
４−１の構成を示すと、図９のようになる。すなわち、
この８×８のバンヤン網２４−１は、３つのステージか
らなり、各ステージは、４つの２×２の単位スイッチ２
４１で構成されている。ここで、単位スイッチ２４１
は、入力端Ａと入力端Ｂに入ってくる入力セルの宛先ア
ドレスＤＡ（図１３の（ａ）参照）のうち割り当てられ
たチェックビットによって、状態が決まるもので、両入
力端Ａ，Ｂのチェックビットの組み合わせによって、そ
の状態は図１０（ａ）〜（ｅ）のようになる。なお、ｘ
は無効セルのチェックビットである。
【００４３】また、各ステージで、宛先アドレスＤＡの
どれをチェックビットにするかが異なる。例えば、第１
ステージでは、宛先アドレスＤＡの第１ビットをチェッ
クビットにし、第２ステージでは、宛先アドレスＤＡの
第２ビットをチェックビットにし、第３ステージでは、
宛先アドレスＤＡの第３ビットをチェックビットにする
（図１７参照）。
どれをチェックビットにするかが異なる。例えば、第１
ステージでは、宛先アドレスＤＡの第１ビットをチェッ
クビットにし、第２ステージでは、宛先アドレスＤＡの
第２ビットをチェックビットにし、第３ステージでは、
宛先アドレスＤＡの第３ビットをチェックビットにする
（図１７参照）。
【００４４】これにより、例えば入線Ｉ0 に宛先アドレ
スＤＡが「０」のものが入力され、入線Ｉ1 に宛先アド
レスＤＡが「１」のものが入力され、入線Ｉ2 に宛先ア
ドレスＤＡが「５」のものが入力され、入線Ｉ3 〜Ｉ7
に無効セルが入力された場合の動作例を示すと、図１７
のようになり、これから連続して並んだ集線回路２３−
１からのセルが、そのアドレス情報を基に対応する出線
Ｏ0 ，Ｏ1 ，Ｏ5 に出力されることがわかる。
スＤＡが「０」のものが入力され、入線Ｉ1 に宛先アド
レスＤＡが「１」のものが入力され、入線Ｉ2 に宛先ア
ドレスＤＡが「５」のものが入力され、入線Ｉ3 〜Ｉ7
に無効セルが入力された場合の動作例を示すと、図１７
のようになり、これから連続して並んだ集線回路２３−
１からのセルが、そのアドレス情報を基に対応する出線
Ｏ0 ，Ｏ1 ，Ｏ5 に出力されることがわかる。
【００４５】一方、Ｎ／２入力Ｎ出力バッチャー・バン
ヤン網２０−２におけるバッチャーソーティング網２１
−２，比較／廃棄回路２２−２，集線回路２３−２およ
びバンヤン網２４−２も、上記のＮ／２入力Ｎ出力バッ
チャー・バンヤン網２０−１におけるバッチャーソーテ
ィング網２１−１，比較／廃棄回路２２−１，集線回路
２３−１およびバンヤン網２４−１と同様の構成および
作用を有する。
ヤン網２０−２におけるバッチャーソーティング網２１
−２，比較／廃棄回路２２−２，集線回路２３−２およ
びバンヤン網２４−２も、上記のＮ／２入力Ｎ出力バッ
チャー・バンヤン網２０−１におけるバッチャーソーテ
ィング網２１−１，比較／廃棄回路２２−１，集線回路
２３−１およびバンヤン網２４−１と同様の構成および
作用を有する。
【００４６】また、これら２組のＮ／２入力Ｎ出力バッ
チャー・バンヤン網２０−１，２０−２の入力は、図２
に示すように、Ｎ本の入線全てをカバーするように接続
し、その出力は同一の宛先に割り当てられる出力を２本
組として、同一の出力にセルが重複して到着した場合を
考慮して、出力インタフェース２５を介して、出線に接
続する。
チャー・バンヤン網２０−１，２０−２の入力は、図２
に示すように、Ｎ本の入線全てをカバーするように接続
し、その出力は同一の宛先に割り当てられる出力を２本
組として、同一の出力にセルが重複して到着した場合を
考慮して、出力インタフェース２５を介して、出線に接
続する。
【００４７】すなわち、出力インタフェース２５は、２
組のＮ／２入力Ｎ出力バッチャー・バンヤン網２０−
１，２０−２のＮ出力を入力して、Ｎ出力とするもの
で、例えば図１１に示すように、この出力インタフェー
ス２５は、その出線毎に待ち行列式のバッファ回路２６
−１〜２６−Ｎをそなえるように構成する。ここで、バ
ッファ回路２６−ｉ（ｉ＝１〜Ｎ）は、各Ｎ／２入力Ｎ
出力バッチャー・バンヤン網２０−１，２０−２のｉ番
目の出力を受けて、セルをサービス時まで維持するよう
な待ち行列を形成するものである。
組のＮ／２入力Ｎ出力バッチャー・バンヤン網２０−
１，２０−２のＮ出力を入力して、Ｎ出力とするもの
で、例えば図１１に示すように、この出力インタフェー
ス２５は、その出線毎に待ち行列式のバッファ回路２６
−１〜２６−Ｎをそなえるように構成する。ここで、バ
ッファ回路２６−ｉ（ｉ＝１〜Ｎ）は、各Ｎ／２入力Ｎ
出力バッチャー・バンヤン網２０−１，２０−２のｉ番
目の出力を受けて、セルをサービス時まで維持するよう
な待ち行列を形成するものである。
【００４８】なお、出力インタフェース２５としては、
その他、同一の出力にセルが重複して到着した場合、い
ずれか一方を選択して他方を廃棄するような調停回路を
出線毎に設けることも可能である。この調停回路は、出
線毎に、例えばＮ／２入力Ｎ出力バッチャー・バンヤン
網２０−１，２０−２のＮ出力を受け、同一の出力にセ
ルが重複して到着した場合は、特定のＮ／２入力Ｎ出力
バッチャー・バンヤン網２０−１からの出力を選択して
他方を廃棄するような調停回路２７−１〜２７−Ｎとし
て構成される。
その他、同一の出力にセルが重複して到着した場合、い
ずれか一方を選択して他方を廃棄するような調停回路を
出線毎に設けることも可能である。この調停回路は、出
線毎に、例えばＮ／２入力Ｎ出力バッチャー・バンヤン
網２０−１，２０−２のＮ出力を受け、同一の出力にセ
ルが重複して到着した場合は、特定のＮ／２入力Ｎ出力
バッチャー・バンヤン網２０−１からの出力を選択して
他方を廃棄するような調停回路２７−１〜２７−Ｎとし
て構成される。
【００４９】この場合、調停回路２７−１〜２７−Ｎ
は、例えば図１２に示すように、特定のＮ／２入力Ｎ出
力バッチャー・バンヤン網２０−１からのセルの存在を
判定する判定回路２７１−１〜２７１−Ｎと、この判定
回路２７１−１〜２７１−Ｎでの判定結果に基づき特定
のＮ／２入力Ｎ出力バッチャー・バンヤン網２０−１か
らのセルが存在する場合にはこの特定のＮ／２入力Ｎ出
力バッチャー・バンヤン網２０−１からの出力（出線Ｉ
0A〜Ｉ7Aからの信号）を優先的に選択するセレクタ２７
２−１〜２７２−Ｎと、バッファ２７３−１〜２７３−
Ｎ，２７４−１〜２７４−Ｎとを出線毎にそなえて構成
される。
は、例えば図１２に示すように、特定のＮ／２入力Ｎ出
力バッチャー・バンヤン網２０−１からのセルの存在を
判定する判定回路２７１−１〜２７１−Ｎと、この判定
回路２７１−１〜２７１−Ｎでの判定結果に基づき特定
のＮ／２入力Ｎ出力バッチャー・バンヤン網２０−１か
らのセルが存在する場合にはこの特定のＮ／２入力Ｎ出
力バッチャー・バンヤン網２０−１からの出力（出線Ｉ
0A〜Ｉ7Aからの信号）を優先的に選択するセレクタ２７
２−１〜２７２−Ｎと、バッファ２７３−１〜２７３−
Ｎ，２７４−１〜２７４−Ｎとを出線毎にそなえて構成
される。
【００５０】ここで、判定回路２７１−１〜２７１−Ｎ
は、Ｄフリップフロップからなり、そのＤ入力端に特定
のＮ／２入力Ｎ出力バッチャー・バンヤン網２０−１か
らの信号を受け、そのクロック端にクロック信号（図１
３（ｃ）参照）とＡＣＴビットタイミング信号（図１３
（ｅ）参照）との論理積信号（ＡＮＤゲート２８出力）
を受け、その出力がセレクタ２７２−１〜２７２−Ｎに
入力されるようになっている。これにより各判定回路２
７１−１〜２７１−Ｎは、セル中のセル有効ビット情報
をラッチして、もし特定のバッチャー・バンヤン網２０
−１からのセルが存在する場合には、「１」をセレクタ
２７２−１〜２７２−Ｎに出力し、特定のバッチャー・
バンヤン網２０−１からのセルが存在しない場合には、
「０」をセレクタ２７２−１〜２７２−Ｎに出力するよ
うになっている。
は、Ｄフリップフロップからなり、そのＤ入力端に特定
のＮ／２入力Ｎ出力バッチャー・バンヤン網２０−１か
らの信号を受け、そのクロック端にクロック信号（図１
３（ｃ）参照）とＡＣＴビットタイミング信号（図１３
（ｅ）参照）との論理積信号（ＡＮＤゲート２８出力）
を受け、その出力がセレクタ２７２−１〜２７２−Ｎに
入力されるようになっている。これにより各判定回路２
７１−１〜２７１−Ｎは、セル中のセル有効ビット情報
をラッチして、もし特定のバッチャー・バンヤン網２０
−１からのセルが存在する場合には、「１」をセレクタ
２７２−１〜２７２−Ｎに出力し、特定のバッチャー・
バンヤン網２０−１からのセルが存在しない場合には、
「０」をセレクタ２７２−１〜２７２−Ｎに出力するよ
うになっている。
【００５１】また、セレクタ２７２−１〜２７２−Ｎ
は、バッチャー・バンヤン網２０−１からの出力を入力
端ａで受け、バッチャー・バンヤン網２０−２からの信
号を入力端ｂで受け、判定回路２７１−１〜２７１−Ｎ
からの選択信号が「１」のときに、入力端ａの信号を出
力し、選択信号が「０」のときに、入力端ｂの信号を出
力するものである。
は、バッチャー・バンヤン網２０−１からの出力を入力
端ａで受け、バッチャー・バンヤン網２０−２からの信
号を入力端ｂで受け、判定回路２７１−１〜２７１−Ｎ
からの選択信号が「１」のときに、入力端ａの信号を出
力し、選択信号が「０」のときに、入力端ｂの信号を出
力するものである。
【００５２】これにより、同一の出力にセルが重複して
到着した場合は、選択信号が「１」になるから、特定の
Ｎ／２入力Ｎ出力バッチャー・バンヤン網２０−１から
の出力（出線Ｉ0A〜Ｉ7Aからの信号）を選択して他方
（出線Ｉ0B〜Ｉ7Bからの信号）が廃棄される。上述の構
成により、Ｎ本の入線をＮ／２本ずつに分けて２組のＮ
／２入力Ｎ出力バッチャー・バンヤン網２０−１，２０
−２で、自律的にセルのルーチングを行なう。
到着した場合は、選択信号が「１」になるから、特定の
Ｎ／２入力Ｎ出力バッチャー・バンヤン網２０−１から
の出力（出線Ｉ0A〜Ｉ7Aからの信号）を選択して他方
（出線Ｉ0B〜Ｉ7Bからの信号）が廃棄される。上述の構
成により、Ｎ本の入線をＮ／２本ずつに分けて２組のＮ
／２入力Ｎ出力バッチャー・バンヤン網２０−１，２０
−２で、自律的にセルのルーチングを行なう。
【００５３】かかる作用を、バッチャー・バンヤン網２
０−１について説明すると、まず、バッチャーソーティ
ング網２１−１でセルの宛先アドレス毎の並べ替え（ソ
ーティング）を行なう。このとき、同一の宛先アドレス
を持つセルは、連続して並ぶことになる。例えば、図３
に示すような４×４（Ｎ＝８）のバッチャーソーティン
グ網２１−１において、図１４に示すように、入線Ｉ0
にアドレスＤＡ＝５のセルが入力され、入線Ｉ1 にアド
レスＤＡ＝１のセルが入力され、入線Ｉ2 にアドレスＤ
Ａ＝１のセルが入力され、入線Ｉ3 にアドレスＤＡ＝０
のセルが入力されたとすると、前述の説明から、このバ
ッチャーソーティング網２１−１は、セルを宛先アドレ
スの小さい順に並べ替える。また、同一の宛先アドレス
を持つセルについては、連続して並べる（図１４参
照）。
０−１について説明すると、まず、バッチャーソーティ
ング網２１−１でセルの宛先アドレス毎の並べ替え（ソ
ーティング）を行なう。このとき、同一の宛先アドレス
を持つセルは、連続して並ぶことになる。例えば、図３
に示すような４×４（Ｎ＝８）のバッチャーソーティン
グ網２１−１において、図１４に示すように、入線Ｉ0
にアドレスＤＡ＝５のセルが入力され、入線Ｉ1 にアド
レスＤＡ＝１のセルが入力され、入線Ｉ2 にアドレスＤ
Ａ＝１のセルが入力され、入線Ｉ3 にアドレスＤＡ＝０
のセルが入力されたとすると、前述の説明から、このバ
ッチャーソーティング網２１−１は、セルを宛先アドレ
スの小さい順に並べ替える。また、同一の宛先アドレス
を持つセルについては、連続して並べる（図１４参
照）。
【００５４】次に、比較／廃棄回路２２−１で隣り合っ
ているセルの宛先アドレスを比較し、同一宛先アドレス
を持つセルのうち、ただ一つを残して残りに廃棄処理を
施す。セルの廃棄処理が行なわれた場合、ソーティング
されたセルの並びが不連続になっているので、集線回路
２３−１を通してセルの並びを連続になるように詰め
る。
ているセルの宛先アドレスを比較し、同一宛先アドレス
を持つセルのうち、ただ一つを残して残りに廃棄処理を
施す。セルの廃棄処理が行なわれた場合、ソーティング
されたセルの並びが不連続になっているので、集線回路
２３−１を通してセルの並びを連続になるように詰め
る。
【００５５】例えば、上記の例を用いて更に説明する
と、バッチャーソーティング網２１−１で出線Ｏ0 〜Ｏ
3 に対応するセルのアドレスＤＡはそれぞれ「０」，
「１」，「１」，「５」となっているので、図１５に示
すように、比較／廃棄回路２２−１では、その入線
Ｉ0 ，Ｉ1 ；Ｉ2 ，Ｉ3 間の排他的論理和回路２２１
が、それぞれ「１」出力を出し、入線Ｉ1 ，Ｉ2 間の排
他的論理和回路２２１が、「０」出力を出す。これによ
り、入線Ｉ1 ，Ｉ3 用のセレクタ２２５は、セルのＡＣ
Ｔビット挿入位置を「１」のままとし、入線Ｉ2 用のセ
レクタ２２５は、セルのＡＣＴビット挿入位置を「０」
に置き換える。その結果、出線Ｏ0 ，Ｏ1 ，Ｏ3 からの
セルは有効なセルとして出力され、出線Ｏ2 からのセル
は無効なセルとして出力される。
と、バッチャーソーティング網２１−１で出線Ｏ0 〜Ｏ
3 に対応するセルのアドレスＤＡはそれぞれ「０」，
「１」，「１」，「５」となっているので、図１５に示
すように、比較／廃棄回路２２−１では、その入線
Ｉ0 ，Ｉ1 ；Ｉ2 ，Ｉ3 間の排他的論理和回路２２１
が、それぞれ「１」出力を出し、入線Ｉ1 ，Ｉ2 間の排
他的論理和回路２２１が、「０」出力を出す。これによ
り、入線Ｉ1 ，Ｉ3 用のセレクタ２２５は、セルのＡＣ
Ｔビット挿入位置を「１」のままとし、入線Ｉ2 用のセ
レクタ２２５は、セルのＡＣＴビット挿入位置を「０」
に置き換える。その結果、出線Ｏ0 ，Ｏ1 ，Ｏ3 からの
セルは有効なセルとして出力され、出線Ｏ2 からのセル
は無効なセルとして出力される。
【００５６】そして、集線回路２３−１では、例えば、
図１６に示すように、入線Ｉ1 とＩ 2 のセルが同一アド
レスであったため、入線Ｉ2 のセルが無効処理を施され
ているとして、入線Ｉ0 とＩ1 とのセルは図１６の太線
で示すように対応する出線Ｏ 0 とＯ1 とから出力される
が、入線Ｉ2 のセルは途中のセレクタ２３２２でカット
され、入線Ｉ3 のセルが入線Ｉ2 に対応する出線Ｏ2 か
ら出力される。これにより、セルの並びを入線番号の小
さい方に詰めることができる。なお、入線Ｉ3に対応す
る出線Ｏ3 からは無効セルが出力されることになる。
図１６に示すように、入線Ｉ1 とＩ 2 のセルが同一アド
レスであったため、入線Ｉ2 のセルが無効処理を施され
ているとして、入線Ｉ0 とＩ1 とのセルは図１６の太線
で示すように対応する出線Ｏ 0 とＯ1 とから出力される
が、入線Ｉ2 のセルは途中のセレクタ２３２２でカット
され、入線Ｉ3 のセルが入線Ｉ2 に対応する出線Ｏ2 か
ら出力される。これにより、セルの並びを入線番号の小
さい方に詰めることができる。なお、入線Ｉ3に対応す
る出線Ｏ3 からは無効セルが出力されることになる。
【００５７】その後は、上記のようにして、宛先アドレ
スによりソーティングされ、連続した並びに詰められた
セルの列が、バンヤン網２４−１に入れられて、宛先に
対応する出線に出力する。例えば、上記の例の続きとし
て、入線Ｉ0 に宛先アドレスＤＡが「０」のものが入力
され、入線Ｉ1 に宛先アドレスＤＡが「１」のものが入
力され、入線Ｉ2に宛先アドレスＤＡが「５」のものが
入力され、入線Ｉ3 〜Ｉ7 に無効セルが入力された場合
の動作例を示すと、図１７のようになる。これから連続
して並んだ集線回路２３−１からのセルが、そのアドレ
ス情報を基に対応する出線Ｏ0 ，Ｏ 1 ，Ｏ5 に出力され
ることがわかる。
スによりソーティングされ、連続した並びに詰められた
セルの列が、バンヤン網２４−１に入れられて、宛先に
対応する出線に出力する。例えば、上記の例の続きとし
て、入線Ｉ0 に宛先アドレスＤＡが「０」のものが入力
され、入線Ｉ1 に宛先アドレスＤＡが「１」のものが入
力され、入線Ｉ2に宛先アドレスＤＡが「５」のものが
入力され、入線Ｉ3 〜Ｉ7 に無効セルが入力された場合
の動作例を示すと、図１７のようになる。これから連続
して並んだ集線回路２３−１からのセルが、そのアドレ
ス情報を基に対応する出線Ｏ0 ，Ｏ 1 ，Ｏ5 に出力され
ることがわかる。
【００５８】一方、Ｎ／２入力Ｎ出力バッチャー・バン
ヤン網２０−２においても、同様の作用を行なう。この
ように、回路が２組あるので、同一の宛先に対応する出
線が２本になり、同時に２つまでの同一宛先アドレスを
持つセルがルーチングされる。そこで、出力インタフェ
ース２５では、２本の組になっているバンヤン網２４−
１，２４−２の出力を、例えばバッファ２６−１〜２６
−Ｎに接続してセルの待ち行列を形成し、一つの出線に
出力する。
ヤン網２０−２においても、同様の作用を行なう。この
ように、回路が２組あるので、同一の宛先に対応する出
線が２本になり、同時に２つまでの同一宛先アドレスを
持つセルがルーチングされる。そこで、出力インタフェ
ース２５では、２本の組になっているバンヤン網２４−
１，２４−２の出力を、例えばバッファ２６−１〜２６
−Ｎに接続してセルの待ち行列を形成し、一つの出線に
出力する。
【００５９】このようにこの第１実施例によれば、バッ
チャーソーティング網２１−１，２１−２の入出力数を
ＮからＮ／２にすることにより、従来のＮ入力Ｎ出力バ
ッチャー・バンヤン網よりｎステージ分のステージ数を
削減することができる。そのため、従来のバッチャー・
バンヤン網と比較して、ルーチング処理による潜伏時間
はｎ〔ｂｉｔ−ｔｉｍｅ〕短縮される。また、同時に２
つまでの同一宛先アドレスを持つセルのルーチングが可
能であるため、網の出力側で待ち行列を形成することに
より、セル廃棄率を改善できる。
チャーソーティング網２１−１，２１−２の入出力数を
ＮからＮ／２にすることにより、従来のＮ入力Ｎ出力バ
ッチャー・バンヤン網よりｎステージ分のステージ数を
削減することができる。そのため、従来のバッチャー・
バンヤン網と比較して、ルーチング処理による潜伏時間
はｎ〔ｂｉｔ−ｔｉｍｅ〕短縮される。また、同時に２
つまでの同一宛先アドレスを持つセルのルーチングが可
能であるため、網の出力側で待ち行列を形成することに
より、セル廃棄率を改善できる。
【００６０】なお、出力インタフェース２５として、出
線毎に、調停回路を設けた場合は、同一の出力にセルが
重複して到着した場合に、いずれか一方を選択して他方
を廃棄することが行なわれる。特に、図１２に示すよう
な調停回路２７−１〜２７−Ｎを用いた場合は、同一の
出力にセルが重複して到着した場合に、特定のＮ／２入
力Ｎ出力バッチャー・バンヤン網２０−１からの出力を
選択して他方を廃棄するような処理が施される。
線毎に、調停回路を設けた場合は、同一の出力にセルが
重複して到着した場合に、いずれか一方を選択して他方
を廃棄することが行なわれる。特に、図１２に示すよう
な調停回路２７−１〜２７−Ｎを用いた場合は、同一の
出力にセルが重複して到着した場合に、特定のＮ／２入
力Ｎ出力バッチャー・バンヤン網２０−１からの出力を
選択して他方を廃棄するような処理が施される。
【００６１】（ｂ）第２実施例の説明 図１８は本発明の第２実施例を示すブロック図で、この
図１８において５０−１〜５０−８はＮ／８入力Ｎ出力
バッチャー・バンヤン網であり、このＮ／８入力Ｎ出力
バッチャー・バンヤン網５０−１〜５０−８は、自己ル
ーチング機能を持つもので、８組並列に接続されてい
る。
図１８において５０−１〜５０−８はＮ／８入力Ｎ出力
バッチャー・バンヤン網であり、このＮ／８入力Ｎ出力
バッチャー・バンヤン網５０−１〜５０−８は、自己ル
ーチング機能を持つもので、８組並列に接続されてい
る。
【００６２】そして、各Ｎ／８入力Ｎ出力バッチャー・
バンヤン網５０−１〜５０−８は、それぞれ入出力数が
Ｎ／８のバッチャーソーティング網５１−１〜５１−８
と比較／廃棄回路５２−１〜５２−８と集線回路５３−
１〜５３−８と入出力数がＮのバンヤン網５４−１〜５
４−８とをそなえて構成されている。例として、Ｎ／８
入力Ｎ出力バッチャー・バンヤン網５０−１を構成する
各回路について説明する。
バンヤン網５０−１〜５０−８は、それぞれ入出力数が
Ｎ／８のバッチャーソーティング網５１−１〜５１−８
と比較／廃棄回路５２−１〜５２−８と集線回路５３−
１〜５３−８と入出力数がＮのバンヤン網５４−１〜５
４−８とをそなえて構成されている。例として、Ｎ／８
入力Ｎ出力バッチャー・バンヤン網５０−１を構成する
各回路について説明する。
【００６３】まず、バッチャーソーティング網５１−１
は、（ｎ−３）（ｎ−２）／２ステージから成り、セル
のソーティングを行なうものであるが、このバッチャー
ソーティング網５１−１も、前述の第１実施例と同様
に、各ステージ毎に、複数の２×２の単位スイッチをそ
なえた構成をしている。比較／廃棄回路５２−１は、バ
ッチャーソーティング網５１−１でソーティングされた
セルのアドレスを比較して、同一アドレスを持つセルの
うち、ただ一つのセルを残して残りに廃棄処理を施すも
のであるが、この比較／廃棄回路５２−１も、前述の第
１実施例と同様に、隣接する入線間での比較・廃棄処理
を行なうために、隣接する入線間に、それぞれ排他的論
理和回路，ＯＲゲート，ラッチ回路，ＡＮＤゲート，セ
レクタ等をそなえている。
は、（ｎ−３）（ｎ−２）／２ステージから成り、セル
のソーティングを行なうものであるが、このバッチャー
ソーティング網５１−１も、前述の第１実施例と同様
に、各ステージ毎に、複数の２×２の単位スイッチをそ
なえた構成をしている。比較／廃棄回路５２−１は、バ
ッチャーソーティング網５１−１でソーティングされた
セルのアドレスを比較して、同一アドレスを持つセルの
うち、ただ一つのセルを残して残りに廃棄処理を施すも
のであるが、この比較／廃棄回路５２−１も、前述の第
１実施例と同様に、隣接する入線間での比較・廃棄処理
を行なうために、隣接する入線間に、それぞれ排他的論
理和回路，ＯＲゲート，ラッチ回路，ＡＮＤゲート，セ
レクタ等をそなえている。
【００６４】集線回路５３−１は、比較／廃棄回路５２
−１て廃棄処理を施されたセルを補ってセルの並びを連
続になるように詰めるものであり、このために、この集
線回路５３−１も、前述の第１実施例と同様に、比較／
廃棄回路５２−１を通じて入力されてきたセルが有効か
無効かを判定する判定回路と、この判定回路での判定結
果に基づきセルの並びを連続になるように詰めるセル詰
め回路とをそなえている。
−１て廃棄処理を施されたセルを補ってセルの並びを連
続になるように詰めるものであり、このために、この集
線回路５３−１も、前述の第１実施例と同様に、比較／
廃棄回路５２−１を通じて入力されてきたセルが有効か
無効かを判定する判定回路と、この判定回路での判定結
果に基づきセルの並びを連続になるように詰めるセル詰
め回路とをそなえている。
【００６５】バンヤン網５４−１は、集線回路５３−１
からの並べられたセルをそのアドレス情報を基に対応す
る出線に出力するものであり、このバンヤン網５４−１
も、前述の第１実施例と同様に、各ステージ毎に、複数
の２×２の単位スイッチをそなえた構成をしている。な
お、このバンヤン網５４−１も、集線回路５３−１のＮ
／８出力がバンヤン網５４−１のＮ入力の一部として入
力され、他の入力は未接続状態となっているものであ
る。
からの並べられたセルをそのアドレス情報を基に対応す
る出線に出力するものであり、このバンヤン網５４−１
も、前述の第１実施例と同様に、各ステージ毎に、複数
の２×２の単位スイッチをそなえた構成をしている。な
お、このバンヤン網５４−１も、集線回路５３−１のＮ
／８出力がバンヤン網５４−１のＮ入力の一部として入
力され、他の入力は未接続状態となっているものであ
る。
【００６６】また、他のＮ／８入力Ｎ出力バッチャー・
バンヤン網５０−２〜５０−８におけるバッチャーソー
ティング網５１−２〜５１−８，比較／廃棄回路５２−
２〜５２−８，集線回路５３−２〜５３−８およびバン
ヤン網５４−２〜５４−８についても、上述のＮ／８入
力Ｎ出力バッチャー・バンヤン網５０−１におけるバッ
チャーソーティング網５１−１，比較／廃棄回路５２−
１，集線回路５３−１およびバンヤン網５４−１と同様
の構成，作用を有するものである。
バンヤン網５０−２〜５０−８におけるバッチャーソー
ティング網５１−２〜５１−８，比較／廃棄回路５２−
２〜５２−８，集線回路５３−２〜５３−８およびバン
ヤン網５４−２〜５４−８についても、上述のＮ／８入
力Ｎ出力バッチャー・バンヤン網５０−１におけるバッ
チャーソーティング網５１−１，比較／廃棄回路５２−
１，集線回路５３−１およびバンヤン網５４−１と同様
の構成，作用を有するものである。
【００６７】出力インタフェース５５は、各Ｎ／８入力
Ｎ出力バッチャー・バンヤン網５０−１〜５０−８のＮ
出力を入力してＮ出力とするものであり、この出力イン
タフェース５５は、その出線毎に各Ｎ／８入力Ｎ出力バ
ッチャー・バンヤン網５０−１〜５０−８のＮ出力を受
ける待ち行列式のバッファ５６−１〜５６−８（図１９
参照）をそなえているが、その他、出力インタフェース
５５に、その出線毎に、各Ｎ／８入力Ｎ出力バッチャー
・バンヤン網５０−１〜５０−８のＮ出力を受け、同一
の出力にセルが重複して到着した場合は、いずれか一つ
を選択して他方を廃棄するような調停回路をそなえるよ
うにしてもよい。
Ｎ出力バッチャー・バンヤン網５０−１〜５０−８のＮ
出力を入力してＮ出力とするものであり、この出力イン
タフェース５５は、その出線毎に各Ｎ／８入力Ｎ出力バ
ッチャー・バンヤン網５０−１〜５０−８のＮ出力を受
ける待ち行列式のバッファ５６−１〜５６−８（図１９
参照）をそなえているが、その他、出力インタフェース
５５に、その出線毎に、各Ｎ／８入力Ｎ出力バッチャー
・バンヤン網５０−１〜５０−８のＮ出力を受け、同一
の出力にセルが重複して到着した場合は、いずれか一つ
を選択して他方を廃棄するような調停回路をそなえるよ
うにしてもよい。
【００６８】そして、この場合の調停回路としては、Ｎ
／８入力Ｎ出力バッチャー・バンヤン網５０−１〜５０
−８のＮ出力を受け、同一の出力にセルが重複して到着
した場合は、特定のＮ／８入力Ｎ出力バッチャー・バン
ヤン網（例えば５０−１）からの出力をを選択して他方
を廃棄するような調停回路として構成される。この場合
の調停回路としては、前述の第１実施例と同様にして、
特定のＮ／８入力Ｎ出力バッチャー・バンヤン網からの
セルの存在を判定する判定回路と、この判定回路での判
定結果に基づき、特定のＮ／８入力Ｎ出力バッチャー・
バンヤン網からのセルが存在する場合には、この特定の
Ｎ／８入力Ｎ出力バッチャー・バンヤン網からの出力を
優先的に選択するセレクタとを出線毎にそなえるように
構成する。
／８入力Ｎ出力バッチャー・バンヤン網５０−１〜５０
−８のＮ出力を受け、同一の出力にセルが重複して到着
した場合は、特定のＮ／８入力Ｎ出力バッチャー・バン
ヤン網（例えば５０−１）からの出力をを選択して他方
を廃棄するような調停回路として構成される。この場合
の調停回路としては、前述の第１実施例と同様にして、
特定のＮ／８入力Ｎ出力バッチャー・バンヤン網からの
セルの存在を判定する判定回路と、この判定回路での判
定結果に基づき、特定のＮ／８入力Ｎ出力バッチャー・
バンヤン網からのセルが存在する場合には、この特定の
Ｎ／８入力Ｎ出力バッチャー・バンヤン網からの出力を
優先的に選択するセレクタとを出線毎にそなえるように
構成する。
【００６９】このような構成により、入線数ＮをＮ／８
入力に分割し、Ｎ／８入力Ｎ出力バッチャー・バンヤン
網５０−１〜５０−８に入力する。各Ｎ／８入力Ｎ出力
バッチャー・バンヤン網５０−１〜５０−８では次のよ
うな作用を行なう（例として、Ｎ／８入力Ｎ出力バッチ
ャー・バンヤン網５０−１を挙げる）。まず、バッチャ
ーソーティング網５１−１で入力されたセルをその宛先
アドレス情報を基に並べ替える。このとき、同一の宛先
アドレスを持つセルは連続して並ぶことになり、比較／
廃棄回路５２−１でセルのアドレスを比較し、同一アド
レスを持つセルのうちただ一つを残して残りに廃棄処理
を施す。このようにしてセルの廃棄処理が行なわれた場
合、セルの並びが不連続になっているので集線回路５３
−１を通してセルの並びを連続になるように詰める。こ
うして、宛先アドレスによりソーティングされ連続した
並びに詰められたセルの列をバンヤン網５４−１に入力
することにより、宛先アドレスに対応する出線にセルを
出力する。
入力に分割し、Ｎ／８入力Ｎ出力バッチャー・バンヤン
網５０−１〜５０−８に入力する。各Ｎ／８入力Ｎ出力
バッチャー・バンヤン網５０−１〜５０−８では次のよ
うな作用を行なう（例として、Ｎ／８入力Ｎ出力バッチ
ャー・バンヤン網５０−１を挙げる）。まず、バッチャ
ーソーティング網５１−１で入力されたセルをその宛先
アドレス情報を基に並べ替える。このとき、同一の宛先
アドレスを持つセルは連続して並ぶことになり、比較／
廃棄回路５２−１でセルのアドレスを比較し、同一アド
レスを持つセルのうちただ一つを残して残りに廃棄処理
を施す。このようにしてセルの廃棄処理が行なわれた場
合、セルの並びが不連続になっているので集線回路５３
−１を通してセルの並びを連続になるように詰める。こ
うして、宛先アドレスによりソーティングされ連続した
並びに詰められたセルの列をバンヤン網５４−１に入力
することにより、宛先アドレスに対応する出線にセルを
出力する。
【００７０】各Ｎ／８入力Ｎ出力バッチャー・バンヤン
網５０−１〜５０−８のＮ出力は、出力インタフェース
５５に入力され、Ｎ出力となる。その後、各Ｎ／８入力
Ｎ出力バッチャー・バンヤン網５０−１〜５０−８のＮ
出力は出力インタフェース５５の出線毎にそなえられた
待ち行列式のバッファ５６または調停回路で受けてＮ出
力とする。
網５０−１〜５０−８のＮ出力は、出力インタフェース
５５に入力され、Ｎ出力となる。その後、各Ｎ／８入力
Ｎ出力バッチャー・バンヤン網５０−１〜５０−８のＮ
出力は出力インタフェース５５の出線毎にそなえられた
待ち行列式のバッファ５６または調停回路で受けてＮ出
力とする。
【００７１】以上のように、この第２実施例によれば、
バッチャーソーティング網５１−１〜５１−８の入出力
数をＮからＮ／８にすることにより、３ｎ−３ステージ
分のステージ数を削減することができるため、従来のバ
ッチャー・バンヤン網と比較して、ルーチング処理によ
る潜伏時間を３ｎ−３〔ｂｉｔ−ｔｉｍｅ〕短縮でき
る。また、同時に８つまでの同一宛先アドレスを持つセ
ルのルーチングが可能であるため、網の出力側で待ち行
列を形成することにより、セル廃棄率を改善できる。
バッチャーソーティング網５１−１〜５１−８の入出力
数をＮからＮ／８にすることにより、３ｎ−３ステージ
分のステージ数を削減することができるため、従来のバ
ッチャー・バンヤン網と比較して、ルーチング処理によ
る潜伏時間を３ｎ−３〔ｂｉｔ−ｔｉｍｅ〕短縮でき
る。また、同時に８つまでの同一宛先アドレスを持つセ
ルのルーチングが可能であるため、網の出力側で待ち行
列を形成することにより、セル廃棄率を改善できる。
【００７２】（ｃ）第３実施例の説明 なお、更に一般化して、図２０に示すように、入出力数
がＮ／２i （ｉは自然数）のバッチャーソーティング網
１１−１〜１１−２i と比較／廃棄回路１２−１〜１２
−２i と集線回路１３−１〜１３−２i と、入出力数が
Ｎのバンヤン網１４−１〜１４−２i とからなるＮ／２
i 入力Ｎ出力バッチャー・バンヤン網１０−２i を、２
i 組並列に接続して、自己ルーチング機能付き相互接続
網を構成してもよく、この場合、各Ｎ／２i 入力Ｎ出力
バッチャー・バンヤン網１０−２ i において、その集線
回路１３−１〜１３−２i のＮ／２i 出力がそのバンヤ
ン網１４−１〜１４−２i のＮ入力の一部として入力さ
れ、バンヤン網１４−１〜１４−２i の他の入力は未接
続状態になっている。
がＮ／２i （ｉは自然数）のバッチャーソーティング網
１１−１〜１１−２i と比較／廃棄回路１２−１〜１２
−２i と集線回路１３−１〜１３−２i と、入出力数が
Ｎのバンヤン網１４−１〜１４−２i とからなるＮ／２
i 入力Ｎ出力バッチャー・バンヤン網１０−２i を、２
i 組並列に接続して、自己ルーチング機能付き相互接続
網を構成してもよく、この場合、各Ｎ／２i 入力Ｎ出力
バッチャー・バンヤン網１０−２ i において、その集線
回路１３−１〜１３−２i のＮ／２i 出力がそのバンヤ
ン網１４−１〜１４−２i のＮ入力の一部として入力さ
れ、バンヤン網１４−１〜１４−２i の他の入力は未接
続状態になっている。
【００７３】また、各Ｎ／２i 入力Ｎ出力バッチャー・
バンヤン網１０−２i のＮ出力を入力して、Ｎ出力とす
る出力インタフェース１５が設けられるが、この出力イ
ンタフェース１５は、その出線毎に、各Ｎ／２i 入力Ｎ
出力バッチャー・バンヤン網１０−２i のＮ出力を受け
る待ち行列式のバッファ回路をそなえているか、その出
線毎に、各Ｎ／２i 入力Ｎ出力バッチャー・バンヤン網
１０−２i のＮ出力を受け、同一の出力にセルが重複し
て到着した場合は、いずれか一つを選択して他方を廃棄
するような調停回路（この場合の調停回路は、例えば同
一の出力にセルが重複して到着した場合は、特定のバッ
チャー・バンヤン網からの出力を選択して他方を廃棄す
るような調停回路として構成される）をそなえているよ
うに構成する。
バンヤン網１０−２i のＮ出力を入力して、Ｎ出力とす
る出力インタフェース１５が設けられるが、この出力イ
ンタフェース１５は、その出線毎に、各Ｎ／２i 入力Ｎ
出力バッチャー・バンヤン網１０−２i のＮ出力を受け
る待ち行列式のバッファ回路をそなえているか、その出
線毎に、各Ｎ／２i 入力Ｎ出力バッチャー・バンヤン網
１０−２i のＮ出力を受け、同一の出力にセルが重複し
て到着した場合は、いずれか一つを選択して他方を廃棄
するような調停回路（この場合の調停回路は、例えば同
一の出力にセルが重複して到着した場合は、特定のバッ
チャー・バンヤン網からの出力を選択して他方を廃棄す
るような調停回路として構成される）をそなえているよ
うに構成する。
【００７４】これにより、この自己ルーチング機能付き
相互接続網では、入線数ＮをＮ／２ i 入力に分割し、Ｎ
／２i 入力Ｎ出力バッチャー・バンヤン網１０−１〜１
０−２i に入力する。各Ｎ／２i 入力Ｎ出力バッチャー
・バンヤン網１０−１〜１０−２i では、次のような作
用を行なう。例としてＮ／２i 入力Ｎ出力バッチャー・
バンヤン網１０−１を挙げると、まず、バッチャーソー
ティング網１１−１で入力されたセルをその宛先アドレ
ス情報を基に並べ替える。このとき、同一の宛先アドレ
スを持つセルは連続して並ぶことになり、比較／廃棄回
路１２−１でセルのアドレスを比較し、同一アドレスを
持つセルのうち、ただ一つを残して残りを廃棄する。セ
ルの廃棄が行なわれた場合、セルの並びが不連続になっ
ているので、集線回路１３−１を通してセルの並びを連
続になるように詰める。こうして、宛先アドレスにより
ソーティングされ、連続した並びに詰められたセルの列
をバンヤン網１４−１に入力することにより、宛先アド
レスに対応する出線にセルを出力する。
相互接続網では、入線数ＮをＮ／２ i 入力に分割し、Ｎ
／２i 入力Ｎ出力バッチャー・バンヤン網１０−１〜１
０−２i に入力する。各Ｎ／２i 入力Ｎ出力バッチャー
・バンヤン網１０−１〜１０−２i では、次のような作
用を行なう。例としてＮ／２i 入力Ｎ出力バッチャー・
バンヤン網１０−１を挙げると、まず、バッチャーソー
ティング網１１−１で入力されたセルをその宛先アドレ
ス情報を基に並べ替える。このとき、同一の宛先アドレ
スを持つセルは連続して並ぶことになり、比較／廃棄回
路１２−１でセルのアドレスを比較し、同一アドレスを
持つセルのうち、ただ一つを残して残りを廃棄する。セ
ルの廃棄が行なわれた場合、セルの並びが不連続になっ
ているので、集線回路１３−１を通してセルの並びを連
続になるように詰める。こうして、宛先アドレスにより
ソーティングされ、連続した並びに詰められたセルの列
をバンヤン網１４−１に入力することにより、宛先アド
レスに対応する出線にセルを出力する。
【００７５】その後、各Ｎ／２i 入力Ｎ出力バッチャー
・バンヤン網１０−１〜１０−２iのＮ出力は出力イン
タフェース１５に入力され、Ｎ出力となる。なお、各Ｎ
／２ i 入力Ｎ出力バッチャー・バンヤン網１０−１〜１
０−２i のＮ出力は、出力インタフェース１５の出線毎
にそなえられた待ち行列式のバッファ回路または調停回
路で受けて、Ｎ出力とする。
・バンヤン網１０−１〜１０−２iのＮ出力は出力イン
タフェース１５に入力され、Ｎ出力となる。なお、各Ｎ
／２ i 入力Ｎ出力バッチャー・バンヤン網１０−１〜１
０−２i のＮ出力は、出力インタフェース１５の出線毎
にそなえられた待ち行列式のバッファ回路または調停回
路で受けて、Ｎ出力とする。
【００７６】これにより、この場合も、前述の第１，第
２実施例とほぼ同様の効果ないし利点が得られる。
２実施例とほぼ同様の効果ないし利点が得られる。
【００７７】
【発明の効果】以上詳述したように、本発明の自己ルー
チング機能付き相互接続網によれば、入出力数Ｎに対し
て、従来のバッチャー・バンヤン網に比べて、ｉ（２ｎ
＋１−ｉ）／２ステージ少ない構成にできるため、ルー
チング処理による潜伏時間をｉ（２ｎ＋１−ｉ）／２
〔ｂｉｔ−ｔｉｍｅ〕短縮できるほか、同時に複数のセ
ルをルーチング可能であるため、網の出力側で待ち行列
を形成することにより、セル廃棄率の改善も可能とな
る。さらに、複数組の回路を並列接続する構造となって
いるために、障害発生時の影響を比較的小さい範囲にと
どめることが可能となり、通信網としての性能および実
用性の向上に寄与するところが大きい等、種々の利点が
得られる。
チング機能付き相互接続網によれば、入出力数Ｎに対し
て、従来のバッチャー・バンヤン網に比べて、ｉ（２ｎ
＋１−ｉ）／２ステージ少ない構成にできるため、ルー
チング処理による潜伏時間をｉ（２ｎ＋１−ｉ）／２
〔ｂｉｔ−ｔｉｍｅ〕短縮できるほか、同時に複数のセ
ルをルーチング可能であるため、網の出力側で待ち行列
を形成することにより、セル廃棄率の改善も可能とな
る。さらに、複数組の回路を並列接続する構造となって
いるために、障害発生時の影響を比較的小さい範囲にと
どめることが可能となり、通信網としての性能および実
用性の向上に寄与するところが大きい等、種々の利点が
得られる。
【図１】本発明の原理ブロック図である。
【図２】本発明の第１実施例を示すブロック図である。
【図３】バッチャーソーティング網の構成を示すブロッ
ク図である。
ク図である。
【図４】（ａ），（ｂ）はバッチャーソーティング網を
構成する単位スイッチの動作を説明する図である。
構成する単位スイッチの動作を説明する図である。
【図５】比較／廃棄回路の構成を示すブロック図であ
る。
る。
【図６】（ａ），（ｂ）は比較／廃棄回路を構成するセ
レクタの動作を説明する図である。
レクタの動作を説明する図である。
【図７】集線回路の構成を示すブロック図である。
【図８】集線回路とバンヤン網との接続関係を説明する
ブロック図である。
ブロック図である。
【図９】バンヤン網の構成を示すブロック図である。
【図１０】（ａ）〜（ｅ）はバンヤン網を構成する単位
スイッチの動作を説明する図である。
スイッチの動作を説明する図である。
【図１１】待ち行列式のバッファ回路を有する出力イン
タフェースを示すブロック図である。
タフェースを示すブロック図である。
【図１２】調停回路を有する出力インタフェースを示す
ブロック図である。
ブロック図である。
【図１３】（ａ）〜（ｅ）はセルフォーマットおよびタ
イミングを説明する図である。
イミングを説明する図である。
【図１４】バッチャーソーティング網の動作を説明する
ためのブロック図である。
ためのブロック図である。
【図１５】比較／廃棄回路の動作を説明するブロック図
である。
である。
【図１６】集線回路の動作を説明するブロック図であ
る。
る。
【図１７】バンヤン網の動作を説明するブロック図であ
る。
る。
【図１８】本発明の第２実施例を示すブロック図であ
る。
る。
【図１９】出力インタフェースを示すブロック図であ
る。
る。
【図２０】本発明の第３実施例を示すブロック図であ
る。
る。
【図２１】バッチャー・バンヤン網を示すブロック図で
ある。
ある。
１０−１〜１０−２i Ｎ／２i 入力Ｎ出力バッチャー
・バンヤン網 １１−１〜１１−２i ，２１−１，２１−２，５１−１
〜５１−８，７１ バッチャーソーティング網 １２−１〜１２−２i ，２２−１，２２−２，５２−１
〜５２−８，７２ 比較／廃棄手段 １３−１〜１３−２i ，２３−１，２３−２，５３−１
〜５３−８，７３ 集線手段 １４−１〜１４−２i ，２４−１，２４−２，５４−１
〜５４−８，７４ バンヤン網 １５，２５，５５ 出力インタフェース ２０−１，２０−２ Ｎ／２入力Ｎ出力バッチャー・バ
ンヤン網 ２６−１〜２６−Ｎ，５６−１〜５６−８ バッファ ２７−１〜２７−Ｎ 調停回路 ２８ ＡＮＤゲート ５０−１〜５０−８ Ｎ／８入力Ｎ出力バッチャー・バ
ンヤン網 ７０ Ｎ入力Ｎ出力バッチャー・バンヤン網 ２１１ 単位スイッチ ２２１ 排他的論理和回路 ２２２ ＯＲゲート ２２３ ラッチ回路 ２２４ ＡＮＤゲート ２２５ セレクタ ２３１ 判定回路 ２３２ セル詰め回路 ２３３ ＡＮＤゲート ２３４ 無効セル発生回路 ２３５ バッファ ２４１ 単位スイッチ ２７１−１〜２７１−Ｎ 判定回路 ２７２−１〜２７２−Ｎ セレクタ ２７３−１〜２７３−Ｎ，２７４−１〜２７４−Ｎ バ
ッファ ２３１１〜２３１３ ラッチ回路 ２３２１ セレクタ群 ２３２２ セレクタ
・バンヤン網 １１−１〜１１−２i ，２１−１，２１−２，５１−１
〜５１−８，７１ バッチャーソーティング網 １２−１〜１２−２i ，２２−１，２２−２，５２−１
〜５２−８，７２ 比較／廃棄手段 １３−１〜１３−２i ，２３−１，２３−２，５３−１
〜５３−８，７３ 集線手段 １４−１〜１４−２i ，２４−１，２４−２，５４−１
〜５４−８，７４ バンヤン網 １５，２５，５５ 出力インタフェース ２０−１，２０−２ Ｎ／２入力Ｎ出力バッチャー・バ
ンヤン網 ２６−１〜２６−Ｎ，５６−１〜５６−８ バッファ ２７−１〜２７−Ｎ 調停回路 ２８ ＡＮＤゲート ５０−１〜５０−８ Ｎ／８入力Ｎ出力バッチャー・バ
ンヤン網 ７０ Ｎ入力Ｎ出力バッチャー・バンヤン網 ２１１ 単位スイッチ ２２１ 排他的論理和回路 ２２２ ＯＲゲート ２２３ ラッチ回路 ２２４ ＡＮＤゲート ２２５ セレクタ ２３１ 判定回路 ２３２ セル詰め回路 ２３３ ＡＮＤゲート ２３４ 無効セル発生回路 ２３５ バッファ ２４１ 単位スイッチ ２７１−１〜２７１−Ｎ 判定回路 ２７２−１〜２７２−Ｎ セレクタ ２７３−１〜２７３−Ｎ，２７４−１〜２７４−Ｎ バ
ッファ ２３１１〜２３１３ ラッチ回路 ２３２１ セレクタ群 ２３２２ セレクタ
Claims (12)
- 【請求項１】 情報通信単位であるセルについてその宛
先アドレス情報を基に自律的にセルのルーチングを行な
う自己ルーチング機能をもった入線数および出線数がそ
れぞれＮ（Ｎ＝２n ：ｎは自然数）の相互接続網におい
て、 入出力数がＮ／２i （ｉは自然数）であり、（ｎ−ｉ）
（ｎ＋１−ｉ）／２ステージから成り、セルのソーティ
ングを行なうバッチャーソーティング網（１１−１〜１
１−２i ）と、 入出力数がＮ／２i であり、該バッチャーソーティング
網（１１−１〜１１−２i ）で、ソーティングされたセ
ルのアドレスを比較して、同一アドレスを持つセルのう
ち、ただ一つを残して残りに廃棄処理を施す比較／廃棄
手段（１２−１〜１２−２i ）と、 入出力数がＮ／２i であり、該比較／廃棄手段（１２−
１〜１２−２i ）を通じて入力されてきたセルの並びが
連続になるように詰める集線手段（１３−１〜１３−２
i ）と、 入出力数がＮであり、該集線手段（１３−１〜１３−２
i ）から出力されたセルについて、そのアドレス情報を
基に対応する出線に出力するバンヤン網（１４−１〜１
４−２i ）とからなるＮ／２i 入力Ｎ出力バッチャー・
バンヤン網（１０−１〜１０−２i ）を、 ２i 組並列に接続して構成したことを特徴とする、自己
ルーチング機能付き相互接続網。 - 【請求項２】 該比較／廃棄回路（１２−１〜１２−２
i ）が、 隣接する入力セルのアドレスを比較する比較手段と、 該比較手段で同一アドレスをもつと判定されたセルにつ
いては、１つのセルを除いて残りのセルに廃棄処理を施
す廃棄処理手段とで構成されたことを特徴とする、請求
項１記載の自己ルーチング機能付き相互接続網。 - 【請求項３】 該廃棄処理手段が、１つのセルを除いて
残りのセルについて、セル中のセル有効ビットを無効に
することにより、廃棄処理を施すように構成されている
ことを特徴とする、請求項２記載の自己ルーチング機能
付き相互接続網。 - 【請求項４】 該廃棄処理手段が、 該比較手段からの比較結果をラッチするラッチ回路と、 該ラッチ回路からの出力と入力セルとを受けて、セル有
効ビット情報またはセル無効ビット情報を出力するゲー
ト回路と、 セル中のセル有効ビット挿入位置タイミングで、該ゲー
ト回路からの出力をセル中に挿入するセレクタとをそな
えて構成されたことをことを特徴とする、請求項２記載
の自己ルーチング機能付き相互接続網。 - 【請求項５】 該集線手段（１３−１〜１３−２i ）
が、 該比較／廃棄手段（１２−１〜１２−２i ）を通じて入
力されてきたセルが有効か無効かを判定する判定手段
と、 該判定手段での判定結果に基づき、セルの並びを連続に
なるように詰めるセル詰め手段とをそなえて構成された
ことをことを特徴とする、請求項１記載の自己ルーチン
グ機能付き相互接続網。 - 【請求項６】 該判定手段が、セル中のセル有効ビット
情報をラッチするラッチ回路で構成されるとともに、 該セル詰め手段が、該ラッチ回路からの判定結果に基づ
き、セルの並びを連続になるように詰めるセレクタ群を
含んで構成されたことをことを特徴とする、請求項５記
載の自己ルーチング機能付き相互接続網。 - 【請求項７】 各Ｎ／２i 入力Ｎ出力バッチャー・バン
ヤン網（１０−１〜１０−２i ）において、その集線手
段（１３−１〜１３−２i ）のＮ／２i 出力がそのバン
ヤン網（１４−１〜１４−２i ）のＮ入力の一部として
端から順に入力され、該バンヤン網（１４−１〜１４−
２i ）の他の入力は未接続状態になっていることを特徴
とする、請求項１記載の自己ルーチング機能付き相互接
続網。 - 【請求項８】 各Ｎ／２i 入力Ｎ出力バッチャー・バン
ヤン網（１０−１〜１０−２i ）のＮ出力を入力して、
Ｎ出力とする出力インタフェース（１５）が設けられた
ことを特徴とする、請求項１記載の自己ルーチング機能
付き相互接続網。 - 【請求項９】 該出力インタフェース（１５）が、その
出線毎に、各Ｎ／２ i 入力Ｎ出力バッチャー・バンヤン
網（１０−１〜１０−２i ）のＮ出力を受ける待ち行列
式のバッファ回路をそなえていることを特徴とする、請
求項８記載の自己ルーチング機能付き相互接続網。 - 【請求項１０】 該出力インタフェース（１５）が、そ
の出線毎に、各Ｎ／２i 入力Ｎ出力バッチャー・バンヤ
ン網（１０−１〜１０−２i ）のＮ出力を受け、同一の
出力にセルが重複して到着した場合は、いずれか一つを
選択して他方を廃棄するような調停手段をそなえている
ことを特徴とする、請求項８記載の自己ルーチング機能
付き相互接続網。 - 【請求項１１】 該調停手段が、該Ｎ／２i 入力Ｎ出力
バッチャー・バンヤン網（１０−１〜１０−２i ）のＮ
出力を受け、同一の出力にセルが重複して到着した場合
は、特定のＮ／２i 入力Ｎ出力バッチャー・バンヤン網
からの出力を選択して他方を廃棄するように構成されて
いることを特徴とする、請求項１０記載の自己ルーチン
グ機能付き相互接続網。 - 【請求項１２】 該調停手段が、 該特定のＮ／２i 入力Ｎ出力バッチャー・バンヤン網か
らのセルの存在を判定する判定手段と、 該判定手段での判定結果に基づき、該特定のＮ／２i 入
力Ｎ出力バッチャー・バンヤン網からのセルが存在する
場合には、この特定のＮ／２i 入力Ｎ出力バッチャー・
バンヤン網からの出力を優先的に選択するセレクタとを
そなえて構成されていることを特徴とする、請求項１１
記載の自己ルーチング機能付き相互接続網。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP654692 | 1992-01-17 | ||
| JP4-6546 | 1992-01-17 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH05260080A JPH05260080A (ja) | 1993-10-08 |
| JPH0744544B2 true JPH0744544B2 (ja) | 1995-05-15 |
Family
ID=11641334
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP476193A Expired - Lifetime JPH0744544B2 (ja) | 1992-01-17 | 1993-01-14 | 自己ルーチング機能付き相互接続網 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5392279A (ja) |
| JP (1) | JPH0744544B2 (ja) |
Families Citing this family (38)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR960027803A (ko) * | 1994-12-13 | 1996-07-22 | 양승택 | 출력버퍼형 비동기 전송방식(atm) 스위치 |
| US6144986A (en) * | 1997-03-27 | 2000-11-07 | Cybersales, Inc. | System for sorting in a multiprocessor environment |
| US5987028A (en) * | 1997-05-12 | 1999-11-16 | Industrial Technology Research Insitute | Multiple channel ATM switch |
| US5940389A (en) * | 1997-05-12 | 1999-08-17 | Computer And Communication Research Laboratories | Enhanced partially self-routing algorithm for controller Benes networks |
| US6088353A (en) * | 1997-07-08 | 2000-07-11 | Lucent Technologies, Inc. | Sorting networks having reduced-area layouts |
| US6091723A (en) * | 1997-10-22 | 2000-07-18 | Lucent Technologies, Inc. | Sorting networks having improved layouts |
| US7382736B2 (en) * | 1999-01-12 | 2008-06-03 | Mcdata Corporation | Method for scoring queued frames for selective transmission through a switch |
| US6647011B1 (en) * | 1999-02-22 | 2003-11-11 | Marconi Communications, Inc. | Method and system for switching using an arbitrator |
| DE19961269A1 (de) * | 1999-12-18 | 2001-06-21 | Alcatel Sa | Netzwerkknoten zum Vermitteln von digitalen Informationen unterschiedlicher Protokolltypen |
| US6791977B1 (en) | 2000-10-17 | 2004-09-14 | Gennum Corporation | Reclocker circuit and router cell |
| US7236490B2 (en) * | 2000-11-17 | 2007-06-26 | Foundry Networks, Inc. | Backplane interface adapter |
| US7356030B2 (en) | 2000-11-17 | 2008-04-08 | Foundry Networks, Inc. | Network switch cross point |
| US6735218B2 (en) * | 2000-11-17 | 2004-05-11 | Foundry Networks, Inc. | Method and system for encoding wide striped cells |
| US7596139B2 (en) | 2000-11-17 | 2009-09-29 | Foundry Networks, Inc. | Backplane interface adapter with error control and redundant fabric |
| US7002980B1 (en) * | 2000-12-19 | 2006-02-21 | Chiaro Networks, Ltd. | System and method for router queue and congestion management |
| US7206283B2 (en) * | 2001-05-15 | 2007-04-17 | Foundry Networks, Inc. | High-performance network switch |
| US20120155466A1 (en) * | 2002-05-06 | 2012-06-21 | Ian Edward Davis | Method and apparatus for efficiently processing data packets in a computer network |
| US7187687B1 (en) * | 2002-05-06 | 2007-03-06 | Foundry Networks, Inc. | Pipeline method and system for switching packets |
| US7649885B1 (en) | 2002-05-06 | 2010-01-19 | Foundry Networks, Inc. | Network routing system for enhanced efficiency and monitoring capability |
| US7468975B1 (en) | 2002-05-06 | 2008-12-23 | Foundry Networks, Inc. | Flexible method for processing data packets in a network routing system for enhanced efficiency and monitoring capability |
| US20090279558A1 (en) * | 2002-05-06 | 2009-11-12 | Ian Edward Davis | Network routing apparatus for enhanced efficiency and monitoring capability |
| US7266117B1 (en) * | 2002-05-06 | 2007-09-04 | Foundry Networks, Inc. | System architecture for very fast ethernet blade |
| US6901072B1 (en) | 2003-05-15 | 2005-05-31 | Foundry Networks, Inc. | System and method for high speed packet transmission implementing dual transmit and receive pipelines |
| US7817659B2 (en) * | 2004-03-26 | 2010-10-19 | Foundry Networks, Llc | Method and apparatus for aggregating input data streams |
| US8730961B1 (en) | 2004-04-26 | 2014-05-20 | Foundry Networks, Llc | System and method for optimizing router lookup |
| US7657703B1 (en) * | 2004-10-29 | 2010-02-02 | Foundry Networks, Inc. | Double density content addressable memory (CAM) lookup scheme |
| US8448162B2 (en) | 2005-12-28 | 2013-05-21 | Foundry Networks, Llc | Hitless software upgrades |
| US20070288690A1 (en) * | 2006-06-13 | 2007-12-13 | Foundry Networks, Inc. | High bandwidth, high capacity look-up table implementation in dynamic random access memory |
| US7903654B2 (en) * | 2006-08-22 | 2011-03-08 | Foundry Networks, Llc | System and method for ECMP load sharing |
| US8238255B2 (en) * | 2006-11-22 | 2012-08-07 | Foundry Networks, Llc | Recovering from failures without impact on data traffic in a shared bus architecture |
| US8395996B2 (en) | 2007-01-11 | 2013-03-12 | Foundry Networks, Llc | Techniques for processing incoming failure detection protocol packets |
| US8271859B2 (en) * | 2007-07-18 | 2012-09-18 | Foundry Networks Llc | Segmented CRC design in high speed networks |
| US8037399B2 (en) * | 2007-07-18 | 2011-10-11 | Foundry Networks, Llc | Techniques for segmented CRC design in high speed networks |
| US8149839B1 (en) | 2007-09-26 | 2012-04-03 | Foundry Networks, Llc | Selection of trunk ports and paths using rotation |
| US8190881B2 (en) | 2007-10-15 | 2012-05-29 | Foundry Networks Llc | Scalable distributed web-based authentication |
| US8090901B2 (en) | 2009-05-14 | 2012-01-03 | Brocade Communications Systems, Inc. | TCAM management approach that minimize movements |
| US8599850B2 (en) | 2009-09-21 | 2013-12-03 | Brocade Communications Systems, Inc. | Provisioning single or multistage networks using ethernet service instances (ESIs) |
| US12068971B2 (en) * | 2022-02-25 | 2024-08-20 | Google Llc | Robust age-saturation mechanism for age-based arbitration in packet networks |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4516238A (en) * | 1983-03-28 | 1985-05-07 | At&T Bell Laboratories | Self-routing switching network |
| US4817084A (en) * | 1986-10-16 | 1989-03-28 | Bell Communications Research, Inc. | Batcher-Banyan packet switch with output conflict resolution scheme |
| DE3881813D1 (de) * | 1987-09-30 | 1993-07-22 | Siemens Ag | Sortiereinheit fuer einen vermittlungsknoten mit einer vielzahl von digitalen koppelfeldern fuer schnelle, asynchrone datenpaketvermittlungsnetze. |
| JPH0254653A (ja) * | 1988-08-19 | 1990-02-23 | Nippon Telegr & Teleph Corp <Ntt> | 自己ルーチング空間スイッチ網 |
| US4866701A (en) * | 1988-09-02 | 1989-09-12 | Bell Communications Research, Inc. | Packet switch with dynamic allocation of inputs |
| US4893304A (en) * | 1988-09-02 | 1990-01-09 | Bell Communications Research, Inc. | Broadband packet switch with combined queuing |
| JPH0360247A (ja) * | 1989-07-28 | 1991-03-15 | Nippon Telegr & Teleph Corp <Ntt> | 自己ルーチング通話路 |
| US5065394A (en) * | 1989-08-03 | 1991-11-12 | Pacific Bell | Packet routing switch |
| JPH03159338A (ja) * | 1989-11-17 | 1991-07-09 | Nippon Telegr & Teleph Corp <Ntt> | 自己ルーチングスイッチ網及びその網におけるスイッチ網増設方法 |
| JP2758697B2 (ja) * | 1990-06-08 | 1998-05-28 | 日本電気株式会社 | 多段接続スイッチ装置 |
| US5130976A (en) * | 1991-02-12 | 1992-07-14 | Bell Communications Research, Inc. | Batcher and banyan switching elements |
-
1993
- 1993-01-14 JP JP476193A patent/JPH0744544B2/ja not_active Expired - Lifetime
- 1993-01-15 US US08/004,996 patent/US5392279A/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US5392279A (en) | 1995-02-21 |
| JPH05260080A (ja) | 1993-10-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0744544B2 (ja) | 自己ルーチング機能付き相互接続網 | |
| Zegura | Architectures for ATM switching systems | |
| EP0138952B1 (en) | A self-routing switching network | |
| KR100211123B1 (ko) | 고속 패킷 스위칭을 위한 다단 상호 연결 망 | |
| EP0333226A2 (en) | Packet switching device | |
| JPH0637796A (ja) | パケット交換機の改良型マルチキャスト機構 | |
| Prakash et al. | A survey of multistage interconnection networks | |
| Hanawa et al. | Multistage interconnection networks with multiple outlets | |
| CN103546397A (zh) | 支持乱序的自路由Omega网络结构 | |
| Nesson et al. | ROMM routing: A class of efficient minimal routing algorithms | |
| Park et al. | The deflection self-routing Banyan network: A large-scale ATM switch using the fully adaptive self-routing and its performance analyses | |
| Tagle et al. | A high-performance fault-tolerant switching network for B-ISDN | |
| Mekkittikul et al. | Scheduling VOQ switches under non-uniform traffic | |
| US5034946A (en) | Broadband concentrator for packet switch | |
| US5612951A (en) | Output buffer type Asynchronous Transfer Mode(ATM) switch | |
| Geiselmann et al. | Hardware to solve sparse systems of linear equations over GF (2) | |
| Moravec | Fully interconnecting multiple computers with pipelined sorting nets | |
| Collier et al. | Path allocation in a three-stage broadband switch with intermediate channel grouping | |
| Josephs et al. | High-Level Design of an Asynchronous Packet-Routing Chip. | |
| Chen et al. | RC-BB switch: a high performance switching network for B-ISDN | |
| Kumar | Mathematical modelling and simulation of a buffered Fault Tolerant Double Tree Network | |
| Collier et al. | Cell-level path allocation in a three-stage ATM switch | |
| JP2895508B2 (ja) | セルスイッチ | |
| Itoh | A fault-tolerant switching architecture for ATM networks | |
| Mirfakhraei | Performance analysis of a large-scale switching system for high-speed ATM networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 19960416 |