JPH06197130A - 高速パケット交換装置およびデータパケットの経路指定方法 - Google Patents

Abstract

(57)【要約】 【目的】 低コストの高速パケット交換装置および方法
を提供する。 【構成】 本発明は、入力ポートと出力ポートとの間に
直結された緩衝装置を含み、データパケットの高速生成
を行う。緩衝装置内記憶個所のポインタは、受信入力ポ
ートにおける入力パケットの告知を受信した時緩衝装置
管理回路により割当てられる。入力ポートは、パケット
がポインタで指定された記憶個所に受信された時、パケ
ットを送信する。データパケットが受信された後、入力
ポートは、ポインタとパケットのための宛先アドレスと
をルータに送信する。ルータは、宛先アドレスに基づい
て、複数の出力ポートのうち１個を選択する。ルータ
は、上記選択された出力ポートのための待ち行列内にポ
インタを待ち行列させる。次に、出力ポートは、記憶個
所を決定するポインタを使用して、緩衝装置からデータ
パケットを回復し送信する。送信完了後、出力ポート
は、ポインタを緩衝装置管理回路に戻す。本発明のパケ
ット交換装置は、隣接データパケットを同時に受信し経
路指定し送信する為、パイプライン化が可能である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、パケット交換通信網の
分野に関し、特に、分散処理交換システム内の制御ユニ
ット間でパケット交換制御データ情報を送受信する高速
パケット交換装置およびその方法に関する。

【０００２】

【従来の技術】パケット化されたデータは、電話網で伝
送されているので、電話網の速さ（帯域幅）を増大させ
る必要がある。現代の通信網は、発信元から宛先へデー
タパケットを経路指定するのに使用されるパケット交換
システムと同一速さである。従って、より広い帯域幅の
パケット交換システムが必要となる。

【０００３】交換システムは、データパケットおよび音
声呼を交換することができる速さを増すため、ますま
す、分散制御に拠るようになっている。分散制御交換シ
ステムは、概念的には、小さな通信網であるが、分散処
理装置間で制御情報を高速で伝達するためにパケット交
換を使用する。制御情報の高速伝達がなければ、交換装
置の容量は、一時に取扱われうる制御メッセージの数に
よって制限されることになる。これにより、電話網の隘
路となる。したがって、一般的には、電話網、特に、分
散処理交換システムは、いずれも、広帯域幅パケット交
換の必要がある。

【０００４】分散処理交換システムにおける制御情報の
伝送のため、これまで、種々のパケット交換システムが
試みられ、その成功の度合いは、様々であった。幾つか
のシステムは、処理装置間の全ての通信に使用される別
体の制御バスを備えていた。他のシステムは、分散型処
理装置と、制御情報を解釈し交換装置の全体機能を規制
する中央制御装置との間の専用通信路を使用している。
しかし、これら公知のシステムは、上記通信と規制の実
現のために複雑で時間のかかる動作を必要とする。この
ようなシステムは、分散型処理装置を規制するのに中央
制御装置に依存するため、分散処理の利点を完全利用す
ることができない。

【０００５】１９８２年３月３０日付でエッチ・ジェイ
・ボイシェル（H．J．Beuscher）その他に付与された米
国特許第４，３２２，８４３号の発明による制御情報通
信装置は、それ以前の制御情報通信装置の複雑さと時間
のかかる特質とを削減する利点がある。ボイシェル特許
の発明の一実施例によれば、制御ユニットは、複数の制
御語からなる制御メッセージ（パケット）により、或る
交換システム通信路を介して相互に通信する。システム
に組込まれた制御分散ユニットは、受信した制御語を制
御パケット内に蓄積し、このような全てのパケットを共
用メモリに記憶する。ついで、制御パケットは、制御パ
ケットをそれぞれ共用メモリからパケットヘッダによっ
て定めらる宛先制御ユニットへの後の伝送のため適切な
設備に移転させることにより、逐次的にパケット交換さ
れる。しかし、パケット交換機構の逐次性により、制御
パケットを交換する制御分散ユニットの容量が制限され
る。この容量制限は、システムの制御プロセッサが統合
デジタル通信サービス網（ＩＳＤＮ）の能力供給と結び
付いた機能を実現するのに使用されるとき、特に問題と
なる。

【０００６】上記問題の一つの可能な解決法は、１９８
９年４月１１日付で付与されたデブルラー（DeBruler）
その他の米国特許第４，８２１，２５９号に記載されて
いる。この特許発明証によれば、宛先制御ユニットへの
伝送のため、独立の通路を介してモジュール間制御パケ
ットを高速出力パケット通信路へ切換える、交換装置内
のモジュール間通信のためのパケット交換装置が開示さ
れている。デブルラー特許発明の一実施例に、環状パケ
ット交換装置が開示されている。この環状パケット交換
装置において、回線交換組織は、高速、かつ、多トーク
ン通過環により実時間制御される。

【０００７】しかし、デブルラーのシステムは、リンク
がまずモジュール間接続ユニットに入る時、パケット通
信路と回線通信路とを分離する必要がある為、また、こ
のシステムを介して通信する、分散処理交換装置の各モ
ジュールと各パケット・回線交換制御ユニットとに対し
て修正する必要がある為、現存の交換システムに適合さ
せるには、高価である。

【０００８】また、上記パケット交換装置のそれぞれ
は、入力ポートにおいて入力データパケットの緩衝記憶
処理を行う。このような緩衝は、データパケット交換装
置を介して送られる前に、データパケットを記憶するた
めに、少なくともパケット受信期間を必要とする。した
がって、パケットが交換される前に処理時間が必要とな
る。また、全データパケットが交換装置内を移動するに
は、時間がかかる。幾つかの代表例、例えば、デブルラ
ー特許によれば、データパケットは、出力ポートにおい
ても緩衝されるので、更に時間が必要となる。したがっ
て、交換の前および／または後でのパケットの緩衝は、
公知のパケット交換装置の性能低下を引起してしまう。

【０００９】

【発明が解決しようとする課題】従って、本発明の課題
は、分散処理交換システム内のプロセッサ間制御通信に
使用されるパケット交換設備の限定された容量を改良す
ることである。本発明の目的は、低コストの高速パケッ
ト交換装置を提供することである。

【００１０】

【課題を解決するための手段】本発明の低コストの高速
パケット交換装置は、データパケットの急速なスループ
ットを生じるために、複数個の入力ポートと複数個の出
力ポート間に直結された１個の緩衝装置を使用する。受
信中入力ポートでの入力データパケットの告知を受信し
た時、緩衝装置内記憶個所を示すポインタが緩衝装置管
理回路によって割り当てられ、上記受信中入力ポート
は、上記データパケットを、受信されたままの状態でポ
インタにより指定された記憶個所へ送信する。データパ
ケットが受信された後、入力ポートは、このデータパケ
ットのポインタと宛先アドレスとをルータに送信する。
このルータは、宛先アドレスに基づいて、上記複数個の
出力ポートのうち１個を選択する。ルータは、選択され
た出力ポートのための待ち行列に上記ポインタを登録す
る。これにより、出力ポートは、記憶個所を決定するポ
インタを使用して、緩衝装置からデータパケットを検索
し、このデータパケットを送信する。送信が完了した
後、出力ポートは、ポインタを緩衝装置管理回路に戻
す。

【００１１】本発明のパケット交換装置は、隣接するポ
ート上で同時に受信し、経路指定し、伝送するためにパ
イプライン化してもよい。本発明のパケット交換装置
は、一の基板上に実現可能である。これにより、他のモ
ジュールの修正を最小にして、現行の分散型制御交換シ
ステムへの適合を容易にする。

【００１２】

【実施例】図１は、分散処理交換システムの背景での本
発明の実施例を示すブロック線図である。分散処理交換
システムにおいて、本発明の高速パケット交換装置１０
は、発信元モジュールから宛先モジュールへの制御メッ
セージを含むパケットを送信するのに使用される。交換
システム４は、複数個のアクセスポートを通じて複数個
の利用者ステーション（例、利用者ステーション１２，
１４，１６および１８）に対して回線交換サービスとパ
ケット交換サービスとを行う複数個の交換モジュール
（例、交換モジュール１，２および３）からなる。本実
施例によれば、利用者ステーション１２，１４および１
８は、例えば、ＡＴ＆Ｔ ＩＳＤＮ７５０６または７５
０７電話のような電話ステーション装置である。利用者
ステーション１６は、当業者に公知のデータ端末であ
る。各利用者ステーションは、これと結び付いた、２本
の回線交換Ｂ通信路および１本のパケット交換Ｄ通信路
（代表的には、統合デジタル通信サービス網伝送路）内
の交換モジュール（例、交換モジュール３）に対して情
報送受信を行う。Ｂ通信路は、回線交換ユニット２０に
接続され、Ｄ通信路は、パケット交換ユニット２２に接
続されている。

【００１３】制御ユニット２４は、回線交換ユニット２
０による回線交換接続の確立とパケット交換ユニット２
２によるパケット交換接続の確立とを制御するのに使用
される。通信インタフェース２６は、プロセッサ間通信
のための通信規約処理を行う。

【００１４】各交換モジュールは、２５６個のタイムス
ロット（入力側時間多重化リンク）と２５６個のタイム
スロット（出力側時間多重化リンク）によって、モジュ
ール間接続ユニット２８に接続されている。パケット通
信路は、入力／出力側時間多重化回線上のタイムスロッ
トからなる。図１によれば、２５６個のタイムスロット
（ＴＳ）フレーム内に示されハッチングを施した３個の
タイムスロットは、交換モジュール３と高速パケット交
換装置との間のパケット通信路を構成する。回線交換さ
れた経路は、通信インタフェース２６と高速パケット交
換装置１０との間にクリア通信路を与える初期化時に永
続的に設定される。交換モジュール２および３から延び
たパケット通信路は、高速パケット交換装置上の同一ポ
ートに至る回線交換経路を有する。実施例によれば、高
速パケット交換装置上の各ポートは、最高３２本のパケ
ット通信路を取扱う能力を有する。入力側パケット通信
路に受信されたパケットは、回線交換組織内で交換され
る。

【００１５】例えば、スイッチフックから送受器を取外
した（これにより、電話機１８は、パケット交換ユニッ
ト２２へメッセージを送信する）電話機１８の利用者に
よって、電話呼出しが電話機１８から電話機１２へ発信
される。メッセージＩ応答して、パケット交換ユニット
２２は、制御ユニット２４に、電話機１８の送受器が取
外されたことを報せる。制御ユニット２４は、回線交換
ユニット２０をして電話機１８へダイヤル音を送信させ
る。ついで、電話機１８の利用者は、数字を入力する。
この数字は、パケット交換ユニット２２を介して制御ユ
ニット２４へ送信される。制御ユニット２４は、電話機
１８から集められた数字の数字分析を行い、結果とし
て、上記呼が交換モジュール１に接続された電話機１２
宛であることを決定する。

【００１６】制御ユニット２４は、交換モジュール１内
の制御ユニット（図示せず）ためのメッセージを書式化
し、交換モジュール１に、電話機１２が使用中であるか
否かの判定を要求することが必要であることを、交換モ
ジュールに報せる。制御ユニット２４は、メッセージを
書式化し、これを通信インタフェース２６を介して送信
する。通信インタフェース２６は、メッセージを標準通
信規約によりパッケージ化し、回線交換ユニット２０を
介して送信する。モジュール間接続ユニット２８内の回
線交換ユニット２０と回線交換組織３０とは、上記メッ
セージを永続接続された経路を介して高速パケット交換
装置１０のポートＮに送信する。高速パケット交換装置
１０は、後述するように、パケット交換装置１０内の経
路を介してメッセージを送り、回線交換組織３０内に戻
す。回線交換組織３０は、コネクタＡを介してメッセー
ジを交換モジュール１に送信する。交換モジュール１
は、回線交換組織３０、高速パケット交換装置１０、お
よび、回線交換組織３０からコネクタＣまでの経路を介
して同様に応答する。メッセージは、コネクタＣから、
回線交換ユニット２０と通信インタフェース２６とを通
って、制御ユニット２４に達する。呼出し処理は、電話
機１８と電話機１２とが接続されるまで、上記の通り行
われる。

【００１７】図２は、本発明の高速パケット交換装置１
０の実施例を示すブロック線図である。高速パケット交
換装置１０は、１個の緩衝装置２００と、緩衝装置２０
０に対するアクセス（利用特権）を有する複数個のパケ
ット受信器２０２、および、緩衝装置２００に対するア
クセスを有する複数個のパケット送信器２０４とを含
む。緩衝装置２００は、多数の固定長記憶個所として組
織されている。ポインタは、緩衝装置２００内の記憶個
所のアドレスを含む。自由緩衝装置記憶個所のポインタ
は、緩衝装置管理回路２０６内に記憶される。

【００１８】パケットトラヒックは、入力ポート１〜Ｎ
において、１個以上のタイムスロットからなるパケット
通信路を介してパケット交換装置１０に送信される。受
信器２０２は、緩衝装置管理回路２０６からポインタを
得て、入力パケットをポインタアドレスから始まる緩衝
装置記憶個所に書込む。パケットが緩衝装置２００に書
込まれた後、パケットの宛先を含む、パケットからの経
路指定バイトがポインタと一緒にルータ２０８へ送信さ
れる。ルータ２０８は、後述するように、論理経路指定
バイトを物理パケット通信路番号に写像する検索表を含
む。ついで、ルータ２０８は、パケットが経路指定され
た物理パケット通信路用のＴＸポインタ先入れ先出し待
ち行列（図１１に関連して後述される）にポインタをプ
ッシュする。パケット送信器２０４は、先入れ先出し待
ち行列からポインタをポップし、緩衝装置２００からデ
ータを読出し、このデータを適切な出力ポート通信路を
介して送信する。パケットが送信された後、ポインタ
は、パケット送信器２０４によって緩衝装置管理回路２
０６に戻される。これにより、ＲＡＭ型緩衝装置が他の
パケットに対して解放される。

【００１９】データ流れ パケット通信路は、回線交換組織から複数個の入力ポー
ト１〜Ｎを介してパケット交換装置内に入る。各入力ポ
ートは、複数個の多重タイムスロットからなる。各入力
ポートについて、複数本のパケット通信路を取扱いうる
時間多重化パケット送信器２０２が存在する。各パケッ
ト送信器２０２は、時間多重化書込みバス２１０に接続
されている。該時間多重化書込みバス２１０を介して、
パケット送信器２０２は、受信したパケットデータを緩
衝装置２００に書込む。パケットデータは、時間多重化
読出しバスを介して緩衝装置２００から読出される。２
１０および２１２は、いずれも、アドレスとデータ情報
を送信する。緩衝装置２００に対して設けられた多重化
装置２１４は、与えられた演算に対していずれのバスが
アドレスを供給するかを選択する。多重化装置２１４と
書込み許可選択（図示せず）とは、時間多重化され、図
４に示されたタイミング図に関連する決定論的方法（後
述）で制御される。これにより、緩衝装置２００のため
の複雑な調停回路が避けられる利点がある。パケット送
信器２０４は、読出しバス２１２を介して、緩衝装置２
００からデータを読出し、出力ポートを介して、多重化
タイムスロットにより、回線交換組織へパケットを送信
する。

【００２０】パケット交換装置の実施態様は、パケット
送信器２０４とパケット受信器２０２の数と、入力ポー
トの多重化タイムスロットとが種々異なっていてもよ
い。本実施例を説明するために、４個のパケット受信器
２０２と４個のパケット送信器２０４とを備えるパケッ
ト交換装置について説明する。本実施例によれば、各入
力ポートと各出力ポートとは、２５６個のタイムスロッ
トを有する。

【００２１】各パケット受信器２０２と各パケット送信
器２０４とは、複数本のパケット通信路を取扱う。各パ
ケット通信路は、一群のタイムスロット（連鎖されたと
き、開放形システム相互接続水準１のパケットリンクを
構成する）を含む。説明のため、各パケット受信器２０
２と各パケット送信器２０４は、最高３１本のパケット
通信路を取扱うとする。各パケット通信路は、１個のポ
ートのみから出力されるタイムスロットからなる。した
がって、通信路は、複数個のポートに亘って分散される
ことがない。

【００２２】緩衝装置２００は、多数の固定長記憶個所
を含む。各固定長記憶個所は、交換装置が送受信しうる
最大パケットを緩衝しうる大きさである。説明のため、
最大パケットサイズは、５７６バイトとする。本実施例
によれば、緩衝装置２００内には、４５５個の緩衝記憶
域が存在する。５７６バイトのパケットサイズは、通信
規約ヘッダ情報に利用可能な、通信規約の幾つかの層に
ついて十分であることが判明している６４バイトを伴う
５１２バイトの利用者データフィールド長を取扱う。本
発明の好適な実施例によれば、緩衝装置２００は、高速
ＲＡＭからなる。

【００２３】制御流れ 緩衝装置管理回路２０６は、緩衝装置２００内の遊び記
憶個所に対してポインタの記憶域を与える。システム初
期化時には、交換装置内にパケットトラヒックが存在せ
ず、緩衝装置２００内の全記憶個所は、遊び状態であ
る。全ポインタは、緩衝装置管理回路２０６内で待ち行
列される。入力パケットがパケット受信器２０２により
検知された時、パケット受信器２０２は、ポインタを要
求する。ポインタは、ポインタ分散バス２１６を介して
送信される。パケット受信器２０２は、上記ポインタを
使用して、入力パケットデータの書込みのため、緩衝装
置２００内のアドレスを計算する。

【００２４】入力パケットが受信された時、パケット受
信器２０２は、パケット内の予め定められた定位置から
経路指定バイト（パケットの論理宛先）を抽出し、この
経路指定バイトを保持しジスタ内に保管する。パケット
受信器２０２が一のパケットの終了フラッグを受信した
とき、当業者に公知の整合性テストが行われ、経路指定
バイトおよびポインタがルータ２０８に送信される。

【００２５】ルータ２０８は、検索表を内蔵するＲＡＭ
を含む。検索表は、経路指定バイトに含まれた論理宛先
を物理パケット通信路番号に写像する。物理パケット通
信路番号は、その後、送信器（ＸＭＴＲ）ポインタ先入
れ先出しメモリ（図１１に関連して示されている）を選
択するのに使用される。送信器ポインタ先入れ先出し回
路は、各パケット送信器２０４に接続する各パケット通
信路について１個の先入れ先出しメモリを含む。説明の
ため、４個のパケット送信器２０４が存在するものと
し、各パケット送信器は、最高３１本のパケット通信路
を取扱うものとする。したがって、１２４個の使用可能
な送信器ポインタ先入れ先出しメモリが存在する。ルー
タ２０８は、パケット受信器２０２からポインタを通信
路番号によって経路指定表から選択された先入れ先出し
メモリにプッシュする。送信器ポインタ先入れ先出しメ
モリ内のポインタは、パケットが送信のため待ち行列を
形成していることを表現する。

【００２６】各パケット送信器２０４は、パケット通信
路が遊び状態のとき、このパケット送信器２０４のパケ
ット通信路と結び付いた送信器ポインタ先入れ先出しメ
モリに問合せる。ポインタは、先入れ先出しメモリ内で
待ち行列を形成しているときは、先入れ先出しメモリか
らポップされ、送信器ポインタバス２１８を介して、パ
ケット送信器２０４により読出される。パケット送信器
２０４は、ポインタに基づいて出力パケットのためのパ
ケットデータを読出す始点となる緩衝装置２００内アド
レスを計算する。パケットが完了したときは、パケット
送信器２０４は、ポインタ戻しバス２２０を介して、ポ
インタを緩衝装置管理回路２０６に戻し、他の待ち行列
したポインタのため送信器ポインタ先入れ先出しメモリ
に問合せる。ポインタが緩衝装置管理回路２０６に戻さ
れたとき、このポインタと結び付いた、緩衝装置２００
内記憶個所は、効果的に遊び状態とされ、他の入力パケ
ットによって使用可能となる。

【００２７】ポインタはポインタ戻しバス２２０を経る
代りに、ルータ２０８から分路ポインタ戻しバス２２４
を経て緩衝装置管理回路２０６に戻されてもよい。例え
ば、データパケットがパケット受信器２０２での整合性
テストに合格しなかったとき、または、宛先通信路につ
いての待ち行列が満杯のときは、ポインタは、ルータ２
０８から戻される。ポインタ戻しバス２２０および分路
ポインタ戻しバス２２４は、タイムスロット通信路シー
ケンサ２２２（制御回線、分り易くするため図示せず）
の制御を受けて、多重化装置２２６において多重化さ
れ、緩衝装置管理回路２０６に入力される。多重化装置
２２６の出力は、マイクロプロセッサインタフェースバ
ス２２７上の多重化装置出力端と接続する緩衝装置管理
回路２０６へ送信される。

【００２８】高速パケット交換装置１０の初期化は、マ
イクロプロセッサインタフェース２２８を介して、タイ
ムスロット通信路シーケンサ２２２、ルータ２０８およ
び緩衝装置管理回路２０６内のデータを初期化するマイ
クロプロセッサ（図示せず）により行われる。高速パケ
ット交換装置１０は、初期化後、マイクロプロセッサと
独立に動作する。当業者に公知の保守機能および誤り報
告も、マイクロプロセッサインタフェース２２８を介し
て行われる。

【００２９】タイムスロット通信路シーケンサ 図３は、本発明の実施例に従うタイムスロット通信路シ
ーケンサ２２２のブロック線図である。タイムスロット
通信路シーケンサ２２２は、アドレスとデータバスとに
よりシーケンサ制御回路ＲＡＭ３０２と結合したシーケ
ンサ制御回路３００を含む。シーケンサ制御回路３００
とシーケンサ制御回路ＲＡＭ３０２とは、一緒になっ
て、本発明の高速パケット交換装置１０を制御するため
のタイミング信号とタイムスロット通信路データとを供
給する。タイムスロット通信路シーケンサ２２２は、次
のタイムスロットがどのパケット通信路の一部であるか
について、パケット送信器２０４とパケット受信器２０
２とに動的に知らせるＴ−ＴＸバスとＴ−ＲＸバスとを
備えている。タイムスロットを通信路に写像するデータ
は、マイクロプロセッサインタフェース２２８を経て書
込み読出し自在のシーケンサ制御回路ＲＡＭ３０２に記
憶される。シーケンサ制御回路ＲＡＭ３０２は、本実施
例パケット交換装置１０の４個のポートのそれぞれの２
５６個のタイムスロットのそれぞれについて１個のデー
タバイトを含む。このデータは、タイムスロットがパケ
ット通信路の一部であるか否かを示し、さらに、このデ
ータは、いずれの通信路か、および、通信路の稼働状態
または待機状態を示す。回線交換組織３０（図１）内の
全ての接続は、双方向接続なので、パケット通信路は、
送受信のため同一のタイムスロットを使用し、これによ
り、送受信のため１個のシーケンサを使用することがで
きる。

【００３０】シーケンサ制御回路ＲＡＭ３０２は、全て
のタイムスロットが遊び状態、すなわち、パケット通信
路に関連しない状態となるように、初期化される。マイ
クロプロセッサは、通信路の一部である各タイムスロッ
トのためにパケット通信路番号をシーケンサ制御回路Ｒ
ＡＭ３０２に書込むことにより、パケット通信路を準備
する。パケット通信路は、与えられたポート上の１個の
タイムスロット、多数個のタイムスロット、または、全
てのタイムスロットでありうる。タイムスロットが書込
まれた後、論理経路指定バイトは、マイクロプロセッサ
によって、物理通信路と結びつけられる。本実施例によ
れば、論理経路指定バイトは、交換モジュール番号であ
る。

【００３１】フレームは、１度に送信される全２５６個
のタイムスロットの時間量である。例えば、本実施例の
ような遠距離通信系によれば、フレーム速度は、代表的
な場合、８ｋＨｚである。回線交換組織３０は、入力ポ
ートおよび出力ポート上のタイムスロットに高速パケッ
ト交換装置１０を同期させる８ｋＨｚの信号を供給す
る。シーケンサ制御回路３００は、フレーム毎に全ての
シーケンサ制御回路ＲＡＭ３０２内記憶個所を順番付け
る。

【００３２】各フレームが進行する期間中、シーケンサ
制御回路ＲＡＭ３０２の内容は、Ｔ−ＴＸバス３０８と
Ｔ−ＲＸバス３１０とを介して送信される。Ｎ番目のタ
イムスロットの期間中、Ｎ＋１番目のタイムスロット
は、ポート０から出発して各ポートについてＲＡＭから
読出される。図４から分るように、パケット送信器０が
タイムスロット２５４（補償済Ｌ０データ）を受信して
いる間、タイムスロット２５５についての制御データが
Ｔ−ＲＸバスにより送出される。シーケンサ制御回路Ｒ
ＡＭ３０２から出力されたデータは、出力ラッチ３０４
内でラッチされ、Ｔ−ＴＸバス３０８を駆動するのに使
用される。逐次的ＲＡＭ読出し動作により、Ｔ−ＴＸバ
ス３０８は、多重化される（図４中の軌跡により示され
ている）。

【００３３】回線交換組織３０のパイプライン構成によ
り、入力ポートでのタイムスロットは、出力ポートから
およそタイムスロット２個分遅延される。したがって、
パケット受信器２０２、および、関連のＴ−ＲＸバス３
１０も、その分遅延されなければならない。出力ラッチ
３０４から出力されたデータは、遅延回路３０６内で遅
延される。図４に示されているように（タイムスロット
２のＬ０データがＴ−ＴＸバスに現われたとき、タイム
スロット０のＬ０データは、ちょうどＴ−ＲＸバス上に
出力されたところである。

【００３４】シーケンサ制御回路は、各タイムスロット
について、Ｔ経路３１２信号とＴ−ＲＡＭ３１４信号を
送信する。Ｔ−ＲＡＭ３１４信号は、２Ｎ対１（本実施
例によれば、８対１）多重化装置２１４を制御すること
により、いずれのパケット送信器２０４またはパケット
受信器２０２が緩衝装置２００にアクセスするかを選択
する。図４に示された２Ｎ対１多重化装置の出力軌跡
は、緩衝装置の読出し・書込みサイクルがポートに割当
てられる方法を示す。Ｔ経路３１２信号は、パケット受
信器から延びたポインタ経路指定バイトバスに対して類
似の動作を行う。各パケット受信器から延びた全バス
は、タイムスロット毎に１回選択される。

【００３５】タイミング パケット受信器２０２、パケット送信器２０４、緩衝装
置２００およびルータ２０８は、タイムスロット通信路
シーケンサ２２２に制御されていることにより、常時、
多重化され、これにより、タイムスロット期間中、交換
装置の全構成要素の間で互いに同一のアクセスを可能と
する。図４に示されたタイミング図は、ＲＡＭ帯域幅が
１タイムスロット期間に亘って８ＲＡＭサイクル、すな
わち、４つの読出しサイクルと４つの書込みサイクルと
に分割される方法を示す。本パケット交換概念は、全ポ
ートの満杯状態の全通信路上の入出力トラヒックを取扱
うのに十分なデータと制御帯域幅とを有するように、各
パケット受信器２０２と各パケット送信器２０４とに備
える。後述するパケット交換装置について、６４メガビ
ット／秒のスループットが得られる。

【００３６】パケット交換装置１０を通るデータ流れ
は、パケット受信器２０２から出発する。このパケット
受信器２０２において、データは、緩衝装置に記憶され
る前に、通信規約処理が施される。３２ＭＨｚのシステ
ムクロックパルスは、８ｋＨｚの複数のフレームに分割
される。これらのフレームは、システム同期パルスによ
って特定される。各フレームは、２５６個のタイムスロ
ットを含む。Ｔ−ＲＸバス３１０（タイムスロット通信
路シーケンサから延びた）は、１〜２５５のタイムスロ
ットを含みうる論理パケット通信路によって現タイムス
ロットを特定する。論理パケット通信路は、隣接したタ
イムスロットを必要としない。この情報は、パケット受
信器２０２により、入力直列データに備えるため、上記
パケット通信路と結び付いた状態情報を受信するのに使
用される。

【００３７】パケット交換装置１０に受信されたデータ
は、入力ポート（１−Ｎ）により表現される。（スキュ
ー補償を原因とする（後述する））生じた再刻時遅延
後、Ｔ−ＲＸバス３１０に対するデータ関係は、補償済
Ｌ０データとして示されている。直列データは、ＲＡＭ
書込みバスによって示された４つのＲＡＭ書込みサイク
ルのうちの１つの準備のため、通信規約状態マシンによ
り処理される（図５に関連して後述される）。

【００３８】Ｔ−ＴＸバス３０８は、緩衝装置２００の
読出しの準備のため、状態情報を再呼出しするのに、パ
ケット送信器２０４が使用する論理パケット通信路によ
って、現タイムスロットを特定する。４つのＲＡＭ読出
しサイクルは、ＲＡＭ読出しバスにより表示されてい
る。ＲＡＭ書込みバスとＲＡＭ読出しバスとは、一緒に
なって、書込みおよび読出しアクセスが混交した２Ｎ対
１多重化装置２１４の出力を形成する。ＲＡＭアクセス
への決定論的手順を使用することにより、調停回路が不
要となる。緩衝装置２００から読出されたデータは、そ
の後、送信器により処理され、ついで、送信器０で示さ
れたリンクに逐次的に送信される。

【００３９】パケット受信器 図５は、本発明の実施例にかかるパケット受信器２０２
のブロック線図である。パケット受信器は、通信路状態
ＲＡＭ５００、アドレス状態マシン５０４および通信規
約状態マシン５０６を含む。各状態マシンは、状態変数
を保持するためのレジスタ５０２および５０３と、入力
データおよび状態変数を操作するための組合せ論理５１
２および５１４とを有する。パケット受信器２０２は、
１個のポートに備えられうる最大３１本の利用可能パケ
ット通信路のそれぞれについてハイレベルデータリンク
制御と（パケット受信器２００への）直接記憶呼出し
（ＤＭＡ）転送とを行う。図６および図７に示されてい
るように、パケット受信器２０２は、各パケット通信路
について、他のタイムスロット期間中に通信路状態ＲＡ
Ｍ５００に記憶される状態変数を含む時間多重化状態マ
シンである。

【００４０】各タイムスロットに先立って、通信路番号
がタイムスロット通信路シーケンサ２２２からＴ−ＲＸ
バス３１０を経てパケット受信器２０２に送信される。
この通信路番号は、通信路状態ＲＡＭ５００内に入るア
ドレス指標として使用され、ついで、レジスタ５０２お
よび５０３内へロードされる。タイムスロット期間中、
通信規約状態マシン５０６とアドレス状態マシン５０４
とは、当業者に公知のように、システムクロックによ
り、タイムスロット期間中に受信されたビットと同期さ
れる。状態マシンが稼動する結果として、データが緩衝
装置２００に書込まれ、ポインタが緩衝装置管理回路２
０６から獲得され、または、ルータ２０８へ出力される
か、または、何事も生じない。タイムスロットの終端に
おいて、当該パケット通信路に属する次のタイムスロッ
トに使用される新しい状態変数が通信路状態ＲＡＭ５０
０に記憶される。

【００４１】本実施例のパケット交換装置１０によれ
ば、回線交換組織３０から出力されたタイムスロットデ
ータは、出力クロックと位相が僅かにずれた状態で入力
ポートに刻時入力される。パケット交換装置１０は、出
力（伝送）クロックにより刻時される。スキュー補償回
路５１０は、クロックパルス間の位相差を無視しうる遅
い転送速度で並列バスにデータを桁送りすることによ
り、入力データを受信し、この入力データとクロックと
をパケット交換装置１０の残余部分とを整列させる。ス
キュー補償回路５１０の出力端に設けられたシフトレジ
スタは、正常な状態までビット転送速度を増大させる。
これにより、日付は、システムクロックにより通信規約
状態マシン５０６に刻時入力されうる。Ｔ−ＲＸバスデ
ータ３１０の時間多重化により、各パケット受信器２０
２のビット関係を時間的に互違いにする必要がある。デ
ータが通信規約状態マシンに刻時入力される前に、適切
な遅延量がスキュー補償回路５１０により挿入される。

【００４２】図５中、想像線で示されているように、発
信元を選択するために、多重化装置と一緒に他の直列デ
ータリンク入力が供給されてもよい。このような入力
は、１本以上のパケット通信路を付加プロセッサまたは
付加ゲートウェイからパケット交換装置内に合流させ
る。これにより、上記プロセッサまたはゲートウェイ
は、データパケットに応じて交換モジュールを接続する
ことができる。

【００４３】通信規約状態マシン 通信規約状態マシン内の組合せ論理は、パケット確定
（零ビット検出および未零ビット詰め）、パケット誤り
検査（巡回冗長検査）、パケット組立（経路指定バイト
抽出）および長さ検査の動作を行う。各動作は、当業者
に、公知のように、レジスタ５０２内に保持され、また
は、記憶されるデータに対して、組合せ状態マシンによ
り行われる。

【００４４】図６は、レジスタ５０２に保持された通信
規約状態マシンの状態変数のビット配列を示す。開始レ
ジスタ（ＳＲＥＧ）［７］は、これと関連する状態マシ
ンにより、パケットの開始および終了、放棄（ＡＢＯＲ
Ｔｓ）、および、有効データを検出するのに使用され
る。本実施例のパケット交換装置によれば、ハイレベル
データリンク制御手順が基本的リンクレベル機能を提供
するために選択された。（０１１１１１１０）というハ
イレベルデータリンク制御フラッグパターンは、パケッ
トの開始と終了とを特定するのに使用される。このパタ
ーンを唯一のものとするため、パケットが伝送されると
きは、５個の連続するパケットの後毎に、０が挿入され
る（詰められる）。したがって、ランダムなデータは、
フラッグが未完成のまま伝送されることがない。開始レ
ジスタ状態マシンは、零が後続する５個のパケットから
なるいずれかの場合を特定し、零が保持レジスタに刻時
入力されるのを禁止し、効果的に零詰めを阻止する。

【００４５】詰められていないビットが刻時入力される
各クロックサイクルの間、データが保持レジスタ［８］
内に詰められ、ビットカウンタ（ＨＯＬＤＣＮＴ）
［３］は、増分される。８ビットデータが刻時入力され
た後、データの結果バイトは、アドレス状態マシン５０
４によりデータ伝送路を経て、計算された書込み許可伝
送路を告知する通信規約状態マシン内組合せ論理によ
り、緩衝装置２００内記憶個所に書込まれる。上記結果
バイトがパケットの最初であるときは、定義により、宛
先バイトであり、宛先レジスタ［８］内に記憶される。
データが保持レジスタ［８］内に桁送りされ、各クロッ
クサイクルの巡回冗長検査が行われ、ハイレベルデータ
リンク巡回冗長検査保持レジスタ［１６］に記憶され
る。終了フロッグが受信されたとき、巡回冗長検査保持
レジスタ［１６］は、ハイレベルデータリンク制御手順
により定義されているように、妥当性が検査される。こ
れらの検査がいずれも不合格でないときは、宛先レジス
タ［８］内の宛先バイトは、ポインタバス上のポインタ
と一緒に、宛先バイト伝送路を介して、ルータ２０８に
送信される。

【００４６】アドレス状態マシン アドレス状態マシン内組合せ論理は、緩衝装置２００内
にポインタを記憶し、パケットバイトカウンタを増分
し、上記ポインタと上記パケットバイトカウンタとを使
用して、書込むべき次の緩衝装置内記憶個所を計算する
動作を行う。各動作は、当業者に公知の通り、組合せ状
態マシンにより、レジスタ５０３内に記憶されたデータ
に対して施される。

【００４７】図８は、アドレス状態マシン５０４内の組
合せ論理のために、レジスタ５０３内に記憶された状態
変数の配列を示す。新パケットの始まり、フラッグパタ
ーン（０１１１１１１０）を含まないデータバイトが受
信されたとき、開始レジスタ状態マシンにより検出され
る。このとき、ポインタ要求信号が伝送路５２０を介し
て緩衝装置管理回路に告知される。緩衝装置管理回路
は、ポインタ分散バス５２２を介してポインタを送信
し、伝送路５２４を介して有効信号を告知する。有効信
号に応答して、ポインタは、ポインタレジスタ［９］内
へ移動され、バイトカウンタ［１０］は、０にリセット
される。ポインタには、５７６（緩衝装置長さ）が乗じ
られ、ついで、緩衝装置２００に続くアドレス伝送路を
介して送信されるべきＲＡＭアドレスを形成するため、
バイトカウンタ［１０］に加えられる。書込み許可は、
アドレス状態マシンをしてバイトカウンタ［１０］を増
分させる。

【００４８】パケットの終了フラグが開始レジスタ状態
マシンにより検出されたとき、巡回冗長検査レジスタ
［１６］は、有効巡回冗長検査され、バイトカウンタ
は、過大規模パケットまたは過少規模パケットについて
検査される。これらの検査がいずれも不合格でないとき
は、宛先レジスタ［８］内の宛先［８］は、宛先バイト
バス上に出力され、出荷信号（図示せず）がアドレス状
態マシンに告知される。これにより、ポインタは、ポイ
ンタバスを介して出力し、有効ビットを設定し、ポイン
タと宛先バイトとをルータに刻時入力する。このとき、
パケット送信器は、１パケットの受信を完了し、次のパ
ケットの受信の開始に備える。

【００４９】パケット送信器 図１０には、本発明の実施例にかかるパケット送信器２
０４が示されている。パケット送信器２０４は、通信規
約状態マシン１０００、アドレス状態マシン１００２お
よび通信路状態ＲＡＭ１００４を含む。状態マシンのそ
れぞれは、組合せ論理と、組合せ論理に使用される変数
を記憶するレジスタとを含む。後述するように、各タイ
ムスロットについて１組の状態変数が存在する。各組の
状態変数は、他のタイムスロット期間中、通信路状態Ｒ
ＡＭ１００４に記憶される。

【００５０】パケット送信器２０４（パケット受信器２
０２と同様に）は、１個の出力ポートに設けられうる最
大３２本のパケット通信路のそれぞれについて、ハイレ
ベルデータリンク制御動作と直接記憶呼出し動作とを行
う。各タイムスロットに先立って、通信路番号がタイム
スロット通信路シーケンサからＴ−ＴＸバス３０８を経
て通信路状態ＲＡＭ１００４に送信される。この通信路
番号は、状態変数レジスタから状態変数を読出し、これ
らを通信規約状態変数レジスタ１００６とアドレス状態
レジスタ１００８とに書込むのに、通信路状態ＲＡＭ１
００４内でアドレス指標として使用される。タイムスロ
ット期間中、状態マシン１０００および１００２は、シ
ステムクロックによりタイムスロットの全ビットと一緒
に刻時入力される。状態マシンの稼動の結果として、緩
衝装置２００から読出されたハイレベルデータリンク制
御フラッグまたはデータは、送信されうるものとなり、
ポインタは、ルータ２０８から獲得され、または、緩衝
装置管理回路２０６へ解放されうる。タイムスロットの
終端において、新状態変数は、上記通信路に属する次の
タイムスロットに使用されるように、通信路状態ＲＡＭ
１００４に再び記憶される。

【００５１】タイムスロット整列 Ｔ−ＴＸバスデータ（３０８）の時間多重化性により、
各パケット送信器のビット関係を時間的に互違いとする
ことが必要となる。本実施例のパケット交換装置によれ
ば、回線交換組織３０（図１参照）内に送られたデータ
の各出力ポートは、互いに位相が一致することが要求さ
れる。タイムスロット整列論理１０１０は、全出力ポー
トに亘って、回線交換組織３０とのタイムスロット同期
を再確立するために、適切な遅延量を介して各送信器を
ステージする。

【００５２】通信規約状態マシンおよびアドレス状態マ
シン 通信規約状態マシン内の組合わせ論理は、パケットデー
タの零ビット詰め、パケットデータを活動的に送信して
いない時の検査の動作を行う。

【００５３】アドレス状態マシン１００２内の組合せ論
理は、緩衝装置記憶個所ポインタおよびバイトカウンタ
の記憶と、緩衝装置記憶個所ポインタと上記バイトカウ
ンタとを使用しての緩衝装置記憶個所アドレスの計算と
を行う。

【００５４】図８と図９とは、アドレス状態マシン１０
０２と通信規約状態マシン１０００とのための状態変数
を有するレジスタ配列を示す。タイムスロットの始まり
において、現通信路と結び付いた状態情報（Ｔ−ＴＸバ
ス３０８から得られた情報により定義される）は、通信
規約状態変数レジスタ１００６とアドレス状態レジスタ
１００８とにロードされる。モードＡ［１］によって定
義されたパケットモード（すなわち、パケット伝送中）
でなければ、新ポインタ要求が伝送路１０１２を介して
ルータ２０８へ送信される。ポインタがポインタバスを
介してルータ２０８から受信されたときは、このポイン
タは、アドレス状態レジスタ１０００８のポインタレジ
スタ［９］内にラッチされ、バイトカウンタ変数レジス
タ［１０］は、クリアされる。ポインタに５７６が乗じ
られ、ついで、バイトカウンタに加えられて、緩衝装置
２００から読出すＲＡＭアドレスを形成する。緩衝装置
２００から読出されたパケットデータは、ついで、通信
規約状態変数レジスタ１００６内にラッチされ、伝送デ
ータとして桁送り出される。

【００５５】送信器内の通信規約状態マシンの重要機能
は、パケット緩衝装置から読出されたパケットデータに
零ビット挿入を行うことである。ハイレベルデータリン
ク制御手順は、フラッグパターン（０１１１１１１０）
が唯一のものであるために、パケット直列データストリ
ーム内の連続した５ビット以下のビットが論理１である
ことを可能とする。パケット緩衝装置内に記憶されたパ
ケットデータが零詰めされていないときは、未加工デー
タである。ＲＡＭから読出されたデータが連続した６個
の論理１のビットを含むとすれば、状態マシンは、６番
目のビット位置に論理０を挿入（零詰め）してから、上
記６番目のビットを現実に送信する。１−カウンタ
［３］は、データが送信されたとき、零ビット詰めを行
うのに使用される。タイムスロットの終端において、全
てのデータビットが未だ送信されていない（零ビット詰
めのため）ときは、残りのデータビットは、保持レジス
タ［８］内に保持されているデータビットの数を示すの
に使用される保持カウンタ［４］により、保持レジスタ
［８］内にロードされる。タイムスロットの終端におい
て、バイトカウンタは、保持レジスタ［８］内に完全な
バイトが存在しない限り、増分され、現状態変数は、与
えられたパケット通信路に属する後続のタイムスロット
での再使用のため、通信路状態ＲＡＭ１００４に戻され
る。

【００５６】パケットの終端が検出されたとき、また
は、内在する誤りが検出されたとき、通信規約状態マシ
ン１０００がパケットモードから離れるであろうこと
と、現通信路に使用されたポインタが再使用のため緩衝
装置管理回路２０６に戻されることを示すのに、次のモ
ード変数Ａ［１］が使用される。同報通信ビット［２］
は、優先パケットが全ての稼動中通信路に同報通信され
るのを可能とするために備えられている。

【００５７】本実施例のパケット交換装置によれば、マ
イクロプロセッサの制御を受けて、全ての稼動中宛先に
パケットを生成する能力は、有用であることが認められ
る。この機能を実現するため、通信規約状態マシン１０
００は、特別の同報通信ＲＡＭまたは緩衝装置２００の
未使用部分に記憶された同報通信パケットを開始するた
め、各稼動中通信路（Ｔ−ＴＸバス３０８で定義され
る）をマークする能力を有する。通信規約状態マシン１
０００は、処理中のパケットを先取しない。パケットの
正規終了後、通信路が同報通信のためマークされるとす
れば、通信規約状態マシン１０００は、ルータに対して
新なポインタを要求する代りに、同報通信ＲＡＭにアク
セスし始め、その内容を上記通信路によって表わされる
宛先に通信する。同報通信が完了したとき、パケット送
信器２０４は、正常動作に戻り、ルータに対して新なポ
インタを要求する。同報通信を開始するのにポインタが
全く使用されていなかったので、ポインタは、パケット
送信器２０４から緩衝装置管理回路２０６に対して放出
される必要がない。

【００５８】上記機能は、本実施例において、パケット
のエンドポイント間の「ソフトスイッチ」を提供するの
に使用される。大部分の遠隔通信の場合と同様に、モジ
ュール間接続ユニットが、完全に二重化されているの
で、完全接続に対して２個の完全経路が得られる。

【００５９】本発明の高速パケット交換装置は、代表的
な場合、稼動／待機配置体で操作される。各サイドの稼
動／待機状態を変更する時のパケットデータ損失を最小
化するため、「サイド交換」が始まろうとし、それによ
り、パケット伝送を一時停止しようとすることを示す同
報通信メッセージが稼動中パケット交換スイッチから送
信される。これにより、パケット交換装置内に送信中の
データが停止され、宛先に送信されるべき移行中のパケ
ットに対して短時間待機した後、パケット交換装置内に
待ち行列を形成した全てのデータは、モジュール間接続
ユニットの２個の判部の稼動中待機状態が切替えられ時
に伝送される。この時、送信中の第２同報通信メッセー
ジは、切替えが完了したことを示す。これにより、正常
パケットトラヒックが再開されうる。このように同報通
信能力を使用することにより、稼動側が再伝送が必要と
なる待機状態へ格下げされた時、パケットが失われるの
を防止する。

【００６０】ルータ 図１１は、ルータ２０８のブロック線図である。ルータ
２０８の主要部は、経路指定ＲＡＭ１１００、先入れ先
出し指標ＲＡＭ・制御回路１１０２および伝送ポインタ
先入れ先出しＲＡＭ１１０４からなる。経路指定ＲＡＭ
１１００は、宛先を通信路へ写像する表内への指標とし
てパケット受信器２０２から受信された経路指定バイト
を使用する。このデータは、先入れ先出し指標ＲＡＭ・
制御回路１１０２に送信される。先入れ先出し指標ＲＡ
Ｍ・制御回路１１０２は、このデータを送信器ポインタ
先入れ先出しＲＡＭ１１０４内への指標として使用す
る。ついで、先入れ先出し指標ＲＡＭ・制御回路１１０
２は、パケット受信器２０２により送信されたポインタ
をして、送信器ポインタ先入れ先出しＲＡＭ１１０４内
のパケット送信器２０４のために待ち行列を形成させ
る。

【００６１】パケットがパケット受信器２０２により緩
衝装置２００に入力され書込まれた後、ルータ２０８
は、パケット受信器２０２により受信された緩衝装置ポ
インタを受信し、パケット内に受け入れられた宛先バイ
トに応答して、通信路による伝送のため、パケット送信
器２０４に送信する。パケット受信器２０２から受信さ
れた宛先バイトとポインタとは、Ｔ経路３１２により制
御される選択回路１１０６および１１０８により、多重
化されルータ２０８内へ入力される。各パケット受信器
２０２から延びたバスは、タイムスロット毎に１回選択
される。図１３のタイミング図に示されているように、
ポインタは、送信器０ポインタがまず有効となるように
して、互違いに有効となる。Ｔ経路３１２の信号は、上
述した順序で上記バスが選択されるようにする。

【００６２】選択された宛先バイトは、パケットの論理
宛先（すなわち、交換モジュール番号）を含み、経路指
定ＲＡＭ１１００をアドレス指定するのに使用される。
これにより、物理通信路番号が供給される。ポインタ
は、経路指定ＲＡＭ表引き中に、ポインタ有効ビットと
一緒にポインタラッチ１１１０に記憶される。

【００６３】ポインタ有効ビットおよび表引きの結果次
第で、以下の３つのうち１つが生じうる。ポインタの有
効ビットが告知され（パケットは、正確に受信されてい
るので）、表引きにより有効通信路番号が出力されてい
たときは、有効伝送路の告知により、アドレス多重化装
置１１１２は、経路指定ＲＡＭ１１００データを選択
し、ポインタは、書込み許可の告知により、通信路番号
の上位アドレスビットに応答して、送信器ポインタ先入
れ先出しメモリ１１０４にプッシュされる。ポインタの
有効ビットが告知され、表引きにより空値が出力された
（宛先バイトに応答する通信路が全く存在しないので）
ときは、アドレス多重化装置１１１２は、有り得る先入
れ先出しプッシュ動作のために、送信通信路を選択す
る。図１１に示されているように、正しさは、空検査回
路１１４およびアンドゲート１１６によって進行を阻止
される。ポインタは、分路ポインタ戻り路を経て緩衝装
置管理回路に戻される。これにより、緩衝装置は、解放
される。ポインタの有効ビットが告知されない（パケッ
トが受信されていないので）ときは、アドレス多重化装
置１１１２は、有り得る先入れ先出しプッシュ動作のた
め、送信通信路（Ｔ−ＴＸ）バスを選択する。

【００６４】送信器ポインタ先入れ先出しプッシュ動作 送信器ポインタ先入れ先出しＲＡＭ１１０４と先入れ先
出し指標ＲＡＭ・制御回路１１０２とは、一緒になっ
て、各パケット通信路毎に１個として、複数個の送信器
ポインタ先入れ先出しメモリを供給する。図１１に示さ
れた先入れ先出しＲＡＭ１１０４の組織は、各先入れ先
出し記憶域が最大３２個のポインタを緩衝しうることを
示している。先入れ先出し指標ＲＡＭ・制御回路１１０
２は、各送信器先入れ先出しメモリについて１個の制御
語を含む小容量高速ＲＡＭである。この制御語は、５ビ
ットプッシュポインタと５ビットポップポインタとを含
む。

【００６５】アドレス多重化装置１１１２の出力は、送
信器ポインタ先入れ先出しＲＡＭ１１０４に対して有効
先入れ先出しメモリを特定する上位アドレスビットを供
給する。プッシュポインタは、下位アドレスビットを供
給する。この時、ラッチに記憶されたポインタは、適切
な送信器ポインタ先入れ先出し待ち行列に書込まれる。
プッシュポインタは、増分され、再び、指標ＲＡＭに書
込まれる。

【００６６】書込み許可は、先入れ先出し指標ＲＡＭ・
制御回路１１０２内で生成される。このため、各プッシ
ュ動作に先立って、読出しポインタおよび書込みポイン
タに基づいて、先入れ先出しオーバラン試験がなされう
る。保留プッシュ動作が旧有効ポインタに上書きされた
ときは、プッシュ動作は、許容されず、ポインタは、分
路ポインタ戻りバスを経て緩衝装置管理回路２０６に戻
される。

【００６７】送信器ポインタ先入れ先出しメモリポップ
動作 先入れ先出しポップ動作により、先入れ先出しメモリか
らポインタが除去され、このポインタは、伝送のためパ
ケット発信通信路に送信される。上述の通り、プッシュ
動作が行われないときは、アドレス多重化装置１１１２
は、Ｔ−ＴＸ信号を選択する。図４に示されているよう
に、Ｔ−ＴＸ信号は、次のタイムスロットのための通信
路番号を含む。この通信路番号は、選択された通信路の
ための先入れ先出しメモリを選択する上位アドレスビッ
トとして使用され、選択通信路のための指標語として動
作する。指標ポップポインタは、先入れ先出しＲＡＭ１
１０４のための下位アドレスを供給する。送信器ポイン
タ先入れ先出しＲＡＭ１１０４から読出されたデータ
は、選択通信路により送信される次のパケットのための
ポインタである。

【００６８】パケット送信器２０４が新パケットの送信
の準備が整ったとき、緩衝装置２００は、ルータ２０８
に送信器ポインタ要求信号を告知する。上述の通り、ポ
ップ動作が保留中であって、選択された先入れ先出しメ
モリ内に少くとも１個のポインタが存在しているとき
は、先入れ先出し制御回路は、パケット送信器２０４に
有効信号を告知する。これにより、ポインタは、パケッ
ト送信器２０４によって読出される。ポップポインタ
は、増分され、再び、先入れ先出し指標・制御回路ＲＡ
Ｍ１１０２に書込まれる。

【００６９】ポップ動作の保留中、ポインタ要求は、な
いこともありうる。この場合には、ポップポインタは、
増分されず、有効信号は、告知されない。ポップ動作保
留中、先入れ先出し指標ＲＡＭ・制御回路１１０２内の
ポップポインタとプッシュポインタとは、同一である
（先入れ先出しメモリ内にポインタが存在しないことを
示す）ことが判明しうる。この場合は、ポップポインタ
は、増分されず、有効信号は、告知されない。

【００７０】ルータは、パイプライン化され経路指定Ｒ
ＡＭへのアクセス後、アドレス多重化装置１１１２出力
とＲＸポインタとは、ラッチされる。ポインタ先入れ先
出しメモリのプッシュまたはポップ動作が行われている
時、経路指定ＲＡＭ検索は、次の通信路のため行われて
いる。

【００７１】緩衝装置管理回路 図１２には、本発明の実施例にかかる緩衝装置管理回路
２０６が示されている。緩衝装置管理回路２０６は、送
信器ポインタ先入れ先出しメモリ１２００、先入れ先出
し制御回路１２０２およびポインタ監視回路１２０４を
含む。送信器ポインタ先入れ先出しメモリ１２００は、
システムにより使用されるまで、ポインタを記憶する。
先入れ先出し制御回路１２０２は、ポインタ要求に応答
し、ポインタをポインタ先入れ先出しメモリ１２００に
戻すことを要求する。ポインタ監視回路１２０４は、ポ
インタの妥当性を強化する。

【００７２】緩衝装置管理回路２０６は、パケット受信
器２０２により必要となるまで、ポインタ資源を記憶す
る。ポインタは、パケット交換装置１０により、緩衝装
置２００内の記憶個所を表現するのに使用される。ポイ
ンタは、システム初期化時に先入れ先出しメモリとして
編成されたＲＡＭ内にプロセッサインタフェース２２８
を経て記憶される。プロセッサインタフェース２２８
は、先入れ先出しメモリにプッシュされるポインタの数
をプログラムする柔軟性を与える。

【００７３】パケット受信器２０２から出力されたポイ
ンタへの要求は、ポインタ要求バスにより送信される。
これらの要求は、４対１多重化装置１２０６において多
重化され、ポインタ要求バスを介して先入れ先出し制御
回路１２０２へ送信される。先入れ先出し制御回路１２
０２は、ポインタ要求を受信し、ポップ動作をポップア
ドレスバスを介して送信器ポインタ先入れ先出しメモリ
１２００へ送信する。

【００７４】送信器ポインタ先入れ先出しメモリ１２０
０は、次の利用可能ポインタに基づいてポップ動作を行
い、ポインタバスを介してポインタを送信する。当業者
に公知の通り、奇偶検査がボックス１２０８内で行われ
る。また、ポインタは、有効ポインタ信号と一緒に、ポ
インタ分散バスを介して送信される。

【００７５】ポインタは、パケット送信器２０４または
ルータ２０８から送信されると、多重化装置２２６によ
り受信される。多重化装置２２６の出力は、図１４のタ
イミング図に示されているように、有効バス上の有効信
号と一緒にバスを介して送信される。奇偶と範囲外ポイ
ンタ値とは、ボックス１２１０内で検査される。この値
は、プロセッサインタフェースによりプログラム可能で
あり、本システム内で初期化されたポインタの数次第で
変化する。

【００７６】上記検査が完了した後、ポインタは、ポイ
ンタ監視回路１２０４内に移動される。ポインタ監視回
路１２０４は、緩衝装置の範囲内において１個以上の目
標ポインタを生成し、目標ポインタをポインタ監視回路
を巡るポインタと比較することにより、巡回ポインタの
妥当性を強化する。予め指定された時間内に、ポインタ
に出会わないときは、ポインタは、失われ、生成された
ポインタと交換されたと仮定される。ポインタが予め指
定された時間内に見出されたときは、ポインタに再び出
会うか否かを判定するため他のタイマが設定される。ポ
インタに再び出会うときは、全てのポインタが抑制され
る。一の予め指定された期間で検査されるポインタの数
がシステム過剰の関数であることが効果的である。本実
施例のポインタ監視回路は、本願と対応する米国特許出
願と同日付で米国特許庁に出願された係属中の米国特許
出願（整理番号：Ｃ．Ｇ．ＭｃＨａｒｇ５−２）の主題
である。上記検査の完了後、ポインタが表わす緩衝装置
の記憶個所が再使用されうるように、ポインタは、送信
器ポインタ先入れ先出しメモリ１２００へプッシュされ
る。

【００７７】図１３には、緩衝装置管理回路２０６の出
力のタイミング図が示されている。緩衝装置管理回路２
０６から出力されたポインタは、パケットデータを記憶
するのに利用可能な諸資源を表現するのに使用される。
これらの資源は、「必要」毎基準で、各受信器がタイム
スロット毎に１個のポインタをラッチしうる多重化方法
で、ポインタ分散バスを介して受信器（図４）に分散さ
れる。

【００７８】図１４には、緩衝装置管理回路２０６の入
力のタイミング図が示されている。ルータ２０８から出
力されたポインタは、パケット送信器２０４により、送
信の準備が整った緩衝装置２００内で待ち行列を形成す
るパケットデータを表現するのに使用される。準備が整
った時、各パケット送信器２０４は、ルータ２０８に新
しいポインタを要求する。図５に示されているように、
ポインタは、パケット送信器２０４がタイムスロット毎
に１個のポインタをラッチする多重化方式で、送信器ポ
インタバスを経てパケット送信器２０４に分散される。
パケットデータが送信された後、ポインタは、ＴＸポイ
ンタ戻りバスを経て緩衝装置管理回路２０６に戻され
る。緩衝装置管理回路２０６に戻されるポインタのため
の他の資源は、ルータ２０８から延びた分路ポインタ戻
しバスから得られる。この経路は、誤りがパケット受信
器２０２またはルータ２０８から延びた経路で検出され
れば、使用される。この場合、誤りを含むパケットは、
落され、ポインタは、緩衝装置管理回路２０６に分路を
介して戻される。緩衝装置管理回路２０６に戻された全
てのポインタは、各タイムスロットに対して有り得る全
ての資源を表現するために多重化装置２２６において多
重化される１個の入力により送信される。

【００７９】

【発明の効果】本発明によれば、従来のように、分散処
理交換システム内のプロセッサ間制御通信に使用される
パケット交換装置の容量の限定を受けない低コストの高
速パケット交換装置が得られる。高速パケット交換装置
は、修正を最小にして、現行の分散型制御交換システム
への適合が容易である。

【図面の簡単な説明】

【図１】分散制御交換システムの背景での本発明の実施
例を示すブロック線図である。

【図２】本発明の実施例に従って組立てられた図１の高
速パケット交換装置を示すブロック線図である。

【図３】本発明の上記実施例に従う図２のタイムスロッ
ト通信路シーケンサの詳細ブロック線図である。

【図４】図２の高速交換パケット装置を通るデータタイ
ミングを示すタイミング図である。

【図５】本発明の上記実施例に従う図２のパケット受信
器のブロック線図である。

【図６】図５のパケット受信器の通信規約状態レジスタ
の様式の模式図である。

【図７】図５のパケット受信器のアドレス状態レジスタ
の様式の模式図である。

【図８】図１０のパケット送信器の通信規約状態レジス
タの様式の模式図である。

【図９】図１０のパケット送信器のアドレス状態レジス
タの様式の模式図である。

【図１０】本発明の上記実施例に従う図２のパケット送
信器のブロック線図である。

【図１１】本発明の上記実施例に従う図２のルータのブ
ロック線図である。

【図１２】本発明の上記実施例に従う図２の緩衝装置管
理回路のブロック線図である。

【図１３】図１２の緩衝装置管理回路の出力端における
タイミング図である。

【図１４】図１２の緩衝装置管理回路の入力端における
タイミング図である。

【符号の説明】

１ 交換モジュール ２ 交換モジュール ３ 交換モジュール １０ 高速パケット交換装置 ２０ 回線交換ユニット ２２ 回線交換ユニット ２４ 制御ユニット ２６ 通信インタフェース ２８ モジュール間接続ユニット ３０ 回線交換組織 ２００ 緩衝装置 ２０２ パケット送信器 ２０４ パケット受信器 ２０６ 緩衝装置管理回路 ２０８ ルータ ２１２ 読出しバス ２１８ 送信器ポインタバス ２２０ ポインタ戻しバス ３００ シーケンサ制御回路 ３０２ シーケンサ制御ＲＡＭ ５００ 通信路状態ＲＡＭ ５０２ レジスタ ５０３ レジスタ ５０４ アドレス状態マシン ５０６ 通信規約状態マシン ５２２ ポインタ分散バス １０００ 通信規約状態マシン １００２ アドレス状態マシン １００４ 通信路状態ＲＡＭ １００６ 通信規約状態変数レジスタ １００８ アドレス状態レジスタ １１００ 経路指定ＲＡＭ １１０２ 先入れ先出し指標ＲＡＭ・制御回路 １１０４ 伝送ポインタ先入れ先出しＲＡＭ １１１０ ポインタラッチ １１１４ 空検査回路 １２００ 送信器ポインタ先入れ先出しメモリ １２０２ 先入れ先出し制御回路 １２０４ ポインタ監視回路

───────────────────────────────────────────────────── フロントページの続き (72)発明者 クリストファー ジー．マッハーグ アメリカ合衆国 60190 イリノイ ウィ ンフィールド、ウォルナット ドライヴ 105、27 ダブリュ (72)発明者 トーマス エリソン ニューマン アメリカ合衆国 60187 イリノイ ウィ ートン、チェリー ストリート 817 (72)発明者 ケニス ニコラス スカフ アメリカ合衆国 60555 イリノイ ウォ ーレンヴィル、エメラルドグリーン ドラ イヴ 404ビー (72)発明者 ケニス エドワード ウェンランド アメリカ合衆国 60174 イリノイ セン トチャールズ、ウエストフィールド ドラ イヴ 800

Claims (28)

【特許請求の範囲】
1. 【請求項１】 発信元から宛先へデータパケットを経路
   指定し、上記データパケットは、宛先アドレスを有する
   高速パケット交換装置において、 複数個の入力ポートと、複数個の出力ポートと、上記複
   数個の入力ポートおよび上記複数個の出力ポートと接続
   された緩衝装置と、上記複数個の入力ポートおよび上記
   複数個の出力ポートと接続された緩衝装置管理回路と、
   上記複数個の入力ポートおよび上記複数個の出力ポート
   と接続されたルータとを含み、 上記緩衝装置管理回路は、上記複数個の入力ポートのう
   ちの１個でのデータパケットの受信の告知に応答して、
   上記緩衝装置内の記憶個所を選択し、上記複数個の入力
   ポートのそれぞれは、上記記憶個所を表現するデータの
   受信に応答し上記入力パケットを上記緩衝装置内記憶個
   所に送信する手段を有し、 上記ルータは、上記複数個の入力ポートから上記緩衝装
   置内記憶個所を表現するデータと上記宛先アドレスとを
   受信したことに応答し、上記宛先アドレスに応答して上
   記複数個の出力ポートのうち選択された１個に上記緩衝
   装置内記憶個所を表現する上記データを送信する手段を
   有し、 上記複数個の出力ポートのそれぞれは、上記緩衝装置内
   記憶個所を表現する上記データを受信したことに応答
   し、上記緩衝装置内記憶個所から上記データパケットを
   回復し、上記データパケットを送信し、上記緩衝装置内
   記憶個所を表現する上記データを上記緩衝装置管理回路
   に戻す手段を有することを特徴とする高速パケット交換
   装置。
2. 【請求項２】 上記複数個の入力ポートは、複数本の通
   信路からデータパケットを受信することを特徴とする請
   求項１記載の装置。
3. 【請求項３】 上記複数本の通信路のそれぞれは、１個
   以上のタイムスロットを含み、各入力ポートは、上記タ
   イムスロットのそれぞれの到着に応答して、上記緩衝装
   置内記憶個所を表現する上記データから得られた緩衝装
   置内記憶個所に、上記タイムスロット期間中に受信され
   たデータを送る手段を有することを特徴とする請求項２
   記載の装置。
4. 【請求項４】 上記複数個の入力ポートのそれぞれは、
   通信規約状態マシンとアドレス状態マシンとを含み、上
   記通信規約状態マシンは、各タイムスロット期間中、逐
   次的にデータを受信し、上記アドレス状態マシンで計算
   されたアドレスに基づいて、緩衝装置内記憶個所へ上記
   データを送信し、各データパケットについてのデータ
   は、上記緩衝装置に受入れられた順序で逐次的に記憶さ
   れることを特徴とする請求項３記載の装置。
5. 【請求項５】 上記複数個の入力ポートのそれぞれは、
   さらに、各通信路のために、上記通信規約状態マシンと
   上記アドレス状態マシンとについての情報を記憶する通
   信路状態緩衝装置を含むことを特徴とする請求項４記載
   の装置。
6. 【請求項６】 上記ルータは、上記宛先アドレスを上記
   複数個の出力ポートのうちの１個に写像する手段を有す
   ることを特徴とする請求項１記載の装置。
7. 【請求項７】 上記ルータは、上記緩衝装置内記憶個所
   を表現する上記データを、上記選択された出力ポートの
   ために待ち行列させる出力ポート先入れ先出しメモリを
   含むことを特徴とする請求項１記載の装置。
8. 【請求項８】 上記ルータは、上記宛先アドレスを上記
   複数個の出力ポートの１個に写像する検索表と、上記緩
   衝装置内記憶個所を表現する上記データを、上記選択さ
   れた出力ポートのために待ち行列させる出力ポート先入
   れ先出しメモリとを含むことを特徴とする請求項１記載
   の装置。
9. 【請求項９】 上記複数個の出力ポートは、複数本の通
   信路のうち選択された１本を通じてデータパケットを送
   信することを特徴とする請求項１記載の装置。
10. 【請求項１０】 上記複数本の通信路のそれぞれは、１
    個以上のタイムスロットを含み、上記１個の出力ポート
    は、上記タイムスロットのそれぞれの到着に応答して、
    各タイムスロット期間中、上記選択された通信路を通じ
    て上記緩衝装置から上記データパケットを送信すること
    を特徴とする請求項９記載の装置。
11. 【請求項１１】 上記複数個の出力ポートのそれぞれ
    は、通信規約状態マシンとアドレス状態マシンとを含
    み、上記通信規約状態マシンは、上記アドレス状態マシ
    ンにより計算されたアドレスに基づいて、上記緩衝装置
    内記憶個所からデータを得て、このデータを各タイムス
    ロットを通じて逐次的に送信することを特徴とする請求
    項１０記載の装置。
12. 【請求項１２】 上記複数個の入力ポートのそれぞれ
    は、さらに、各通信路のために、上記通信規約状態マシ
    ンと上記アドレス状態マシンとについての情報を記憶す
    る通信路状態緩衝装置を含むことを特徴とする請求項１
    １記載の装置。
13. 【請求項１３】 上記緩衝装置管理回路は、上記緩衝装
    置内記憶個所を表現する上記データを記憶する先入れ先
    出し待ち行列を含むことを特徴とする請求項１記載の装
    置。
14. 【請求項１４】 上記緩衝装置管理回路は、上記複数個
    の入力ポートに応答して、上記緩衝装置内記憶個所を表
    現する上記データのうち１個のデータを上記先入れ先出
    し待ち行列から除去し、さらに、上記緩衝装置内記憶個
    所を表現する上記データを送信する上記出力ポートに応
    答して、上記緩衝装置内記憶個所を表現する上記データ
    を上記先入れ先出し待ち行列に戻すことを特徴とする請
    求項１３記載の装置。
15. 【請求項１５】 発信元から宛先へデータパケットを経
    路指定する方法であって、上記データパケットのそれぞ
    れは、宛先アドレスとパケット信号の終端とを有し、上
    記パケット交換装置は、入力ポートと、複数個の出力ポ
    ートと、上記入力ポートおよび上記複数個の出力ポート
    と接続された緩衝装置と、上記緩衝装置内の記憶個所に
    対してポインタを割当て取去る緩衝装置管理回路と、上
    記複数個の出力ポートのうち１個を選択するルータ手段
    とを含む上記方法において、 上記入力ポートが、上記発信元からデータパケットを受
    信したことに応答して、上記緩衝装置管理回路にポイン
    タを要求するステップと、 上記緩衝装置管理回路が、上記ポインタ要求に応答し
    て、特定の緩衝装置内記憶個所に対応するポインタを割
    当てるステップと、 上記データパケットが上記発信元から受信された時上記
    入力ポートが、上記ポインタの受信に応答して、上記デ
    ータパケットを上記記憶個所から開始し上記緩衝装置に
    送信するステップと、 上記入力ポートが、上記パケット信号終端の受信に応答
    して、上記ポインタと上記宛先アドレスとを上記ルータ
    に送信するステップと、 上記ルータが、上記ポインタと上記宛先アドレスとの受
    信に応答して、上記複数個の出力ポートのうち１個を選
    択し、上記ポインタを上記選択された出力ポートに送信
    するステップと、 上記選択された出力ポートが、上記ポインタの受信に応
    答して、上記緩衝装置から上記データパケットを回復
    し、このデータパケットを上記宛先へ送信するステップ
    と、 上記選択された出力ポートが上記パケット信号終端の送
    信に応答して、上記ポインタを上記緩衝装置管理回路に
    戻すステップとからなることを特徴とするデータパケッ
    トの経路指定方法。
16. 【請求項１６】 上記データパケットを上記緩衝装置へ
    送信する上記ステップは、各スロット期間中に上記デー
    タパケットの一部を受信することにより、複数個のタイ
    ムスロット期間中に送信された、複数本の通信路上の上
    記データパケットを受信するステップと、上記データパ
    ケットに割当てられた上記ポインタに基づいて、上記デ
    ータを上記緩衝装置内の記憶個所に送信するステップと
    を含むことを特徴とする請求項１４記載の方法。
17. 【請求項１７】 上記複数個の出力ポートのうち１個を
    選択する上記ステップは、上記宛先アドレスを検索し、
    これにより上記選択された出力ポートを得るステップ
    と、上記出力ポートのため上記ポインタを待ち行列させ
    るステップとを含むことを特徴とする請求項１５記載の
    方法。
18. 【請求項１８】 上記緩衝装置から上記データパケット
    を回復し上記データパケットを送信する上記ステップ
    は、複数個のタイムスロット期間中に、複数本の通信路
    を通じて上記データパケットを送信するステップを含
    み、上記選択された出力ポートは、上記ポインタを使用
    して、上記緩衝装置から上記データパケットのためのデ
    ータを回復し、予め定められた通信路を通じて上記デー
    タパケットを送信することを特徴とする請求項１５記載
    の方法。
19. 【請求項１９】 ポインタを割当てる上記ステップは、
    先入れ先出し基準でポインタ待ち行列から上記ポインタ
    を選択するステップを含むことを特徴とする請求項１５
    記載の方法。
20. 【請求項２０】 上記全ステップは、パイプライン方式
    で行われることを特徴とする請求項１５記載の方法。
21. 【請求項２１】 発信元から宛先へデータパケットを経
    路指定し、上記データパケットが宛先アドレスを有する
    高速パケット交換装置において、 上記緩衝手段内での上記データパケットの記憶を制御す
    るポインタ制御手段と、 上記ポインタ制御手段の制御の下で、上記発信元からデ
    ータパケットを受信し上記緩衝手段へ送信する入力手段
    と、 上記データパケットを上記宛先へ送信し、上記ポインタ
    制御手段と上記経路指定手段とに応答して、上記複数個
    のデータパケットの宛先を決定する複数個の出力手段
    と、 上記ポインタ制御手段と上記宛先アドレスとに応答し
    て、上記複数個の出力手段のうち１個を選択する経路指
    定手段とを含むことを特徴とする高速パケット交換装
    置。
22. 【請求項２２】 上記入力手段は、複数本の通信路から
    データパケットを受信し、上記複数本の通信路のそれぞ
    れは、１個以上のタイムスロットを含み、上記入力手段
    は、上記タイムスロットのそれぞれの到着に応答して、
    各タイムスロット期間中に受信されたデータを上記デー
    タに固有の上記緩衝手段内記憶個所に送信することを特
    徴とする請求項２１記載の装置。
23. 【請求項２３】 上記入力手段のそれぞれは通信規約状
    態マシンで、 各タイムスロット期間中に逐次的にデータを受信する上
    記通信規約状態マシンとアドレス状態マシンとを含み、
    上記ポインタ制御手段から受信されたデータに基づいて
    上記アドレス状態マシンにおいて計算されたアドレスに
    基づいて、上記データを上記緩衝装置内記憶個所に送信
    することを特徴とする請求項２２記載の装置。
24. 【請求項２４】 上記経路指定手段は、上記宛先アドレ
    スを上記複数個の出力ポートのうちの１個に写像する手
    段を含むことを特徴とする請求項２１記載の装置。
25. 【請求項２５】 上記経路指定手段は、上記選択された
    出力手段のために、上記緩衝装置内記憶個所と上記宛先
    アドレスとを表現する上記データを待ち行列させる出力
    ポート先入れ先出しメモリを含むことを特徴とする請求
    項２１記載の装置。
26. 【請求項２６】 上記経路指定手段は、上記出力手段の
    うちの１個に上記宛先アドレスを写像するための検索表
    と、上記選択された出力手段のために、上記緩衝装置内
    記憶個所と上記宛先とを表現する上記データを待ち行列
    させる出力手段先入れ先出しメモリとを含むことを特徴
    とする請求項２１記載の装置。
27. 【請求項２７】 上記出力手段は、複数本の通信路のう
    ち選択された１本を介してデータパケットを送信し、上
    記１本の通信路は、上記宛先アドレスに従って選択さ
    れ、上記複数本の通信路のそれぞれは、１個以上のタイ
    ムスロットを含み、上記出力手段は、上記全タイムスロ
    ットのそれぞれの到着に応答して、各タイムスロット期
    間中、上記選択された通信路を通じて、上記緩衝装置か
    ら上記データパケットを送信することを特徴とする請求
    項２１記載の装置。
28. 【請求項２８】 上記緩衝装置制御回路は、ポインタを
    上記緩衝装置内記憶個所に記憶するための先入れ先出し
    待ち行列を含み、上記緩衝装置制御回路は、上記入力手
    段に応答して上記先入れ先出し待ち行列から上記全ポイ
    ンタのうち１個を除去し上記１個のポインタを上記入力
    手段に送信し、さらに、上記１個のポインタを送信する
    上記出力手段に応答し、上記１個のポインタを上記先入
    れ先出し待ち行列に戻すことを特徴とする請求項２１記
    載の装置。