JPH06511612A - 「高速回路」性を有するスイッチに対する待ち行列システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は、いくつかの端末装置のために働いて、該端末装置間の信号トラヒック のスイッチングを行うディジタルスイッチに関し、該トラヒックは論理的にデー タタイムスロットおよび制御パケットを存する制御タイムスロットに分割され、 前記ディジタルスイッチは、 前記データタイムスロットを受取るスイッチメモリと、該スイッチメモリ内の該 データタイムスロットの総合接続を容易ならしめる情報を含む制御メモリと、 前記制御タイムスロットおよびその中に存在する制御パケットを受取り、前記制 御メモリ内へ情報を書込み、呼出されたおよび呼出している前記端末装置へ肯定 応答パケットを送信する、制御メモリ端末と、該制御メモリ端末と協働してそれ ぞれの前記端末装置の実際の状態を記憶する占有／非占有メモリと、 を含む。

市場に対する考慮から、電話システムは、コスト的に通常の電話方式に向かう傾 向かあった。現在では、データ通信に関する新しい要求が、いかにますます強ま ってでいるかを知ることかできる。一方においては、これは、電話ネットワーク か統合影信号システム（第７）となる必要から［世界最大の分散形コンピュータ システム」となったことに、また他方では、現在実現されようとしている、例え ばｌ５ＤＮ（統合形サービスおよびデータネットワーク（Ｉｎｔｅｇｒａｔｅｄ 　５ｅｒｖｉｃｅｓ　ａｎｄ　ＤａｔａＮｅｔｗｏｒｋ））のような新しいサー ビスによる。このために、Ｘ、２５ネツトワークなとか用いられるようになった 。

上述のデータ通信サービスの予想される膨張にコスト的に最適に対応し、内部制 御プロセッサ間の通信のためのＴＬ話交換における「統合形制御ルート」を可能 ならしめるためには、次代のテレコミュニケーションシステムにおいて「高速回 路」性を有するスイッチを設置することか所望される。「高速回路」性を有する スイッチとは、該スイッチに接続されたノートか簡単な加入者線カードであるか 、または強力なプロセッサであるかに関係なく、該ノードか電光的速度で、要求 された動作を行いかつ肯定しＬ：答を送り返す該スイッチへの接続の要求を送信 しうへき該スイッチであることを意味する。その後には、該スイッチを通るルー トか確立され終わっている。「高速回路」性を有するスイッチの例は、ＰＣＴ／ ５Ｅ９２１００８１９に説明されている。このスイッチは、その性質により、高 性能のデータ通信スイッチとしても役立ちうる。

技術の現状 データ通イｇスイッチングにおける最も困難な問題の１つは、いくつかの送信機 か１つの受信機へ同時に、例えはスターネットワークにおいて送信しようとする 時、またはそれに対応して全てのノートか同じ媒体を共有しかつ同時に送信しよ うとする時のハス／リングにおいて、公平な分配を実現することである。バスに おける解決の例としては、例えはイルサネｙ　ｈ・ネットワークおよび「トーク ン」を挙げることかでき、これらは今後も用いられうる。

スターネットワークにおいては、前記問題は、通常スタ一点において全メッセー ジをバッファすることにより解決され、そのようにすれはそれは一時的な混雑を 許容しつるようになるか、結果として溢れを生じる。バッファリングは、中間な いし低伝送速度（約６４ｋｂ／ｓ）を有する以外のネットワークにおいてはさら に悪い結果しか与えない。

前述のＰＣＴ特許出願におけるもののようなスター接続されたスイッチにおいて も問題は存在するか、その場合は、全データメソセージ（コスト、ボリューム、 電力、およびデータレート）をバッファすることは、コスト上の理由て不可能で ある。

すなわちこれは、２つのノートか同し受信機へ送信しようとする場合に、第３ノ ートとの競争か行われうるという結果を与える。

本発明の目的は、いくつかの送信機か１つの受信機に同時に送信しようとしてい る時に公平な分配を実現する問題を、簡単かつ経済的な方法で解決することであ る。

本発明においては、この目的は、序論において示された種類のディジタルスイッ チにおいて、 前記制御メモリ端末および前記占有／非占有メモリに関連する待ち行列システム であって、該待ち行列システムか、 第１端末装置か、占有されている第２端末装置への接続を確立しようとする場合 に、 呼び要求の待ち行列への登録と、前記第１端末装置への肯定応答［接続要求を待 ち行列へ登録済みＪの送信とを行い、かつ前記第２端末装置からの切断要求を受 信した時に、 前記第４端末装置の前記第２端末装置への直接接続を行い、前記第１および第２ 端末装置へ、それぞれ情報「接続達成済み」および「要求達成済み」を含む肯定 応答の送信を行う、メモリ手段および制御論理装置を含む、前記待ち行列システ ムにより達成される。

ｌ実施例においては、前記スイッチは待ち行列メモリを含み、前記占有／非占有 メモリは、［占有され、かつ待ち行列に登録済み」という端末装置の状態コード と、前記待ち行列メモリに対する関連の第１ポインタと、のための場所を含む。

前記占有／非占有メモリ内のそれぞれの場所へは、１つまたはいくつかの待ち行 列場所か割当てられ、前記ポインタは、該占有／非占有メモリ内のアドレスによ り実現されつる。

別の実施例においては、前記待ち行列メモリは、共通リソースとして用いられる 。

その目的のために、ポインタか前記占有／非占有メモリに割当てられ、該占有／ 非占有メモリ内の場所に関連する端末装置の受信機のだめの前記待ち行列メモリ 内に記憶されている次の呼びを指示する。

好ましくは、前記待ち行列メモリは、呼びか割当てられるいくつかの呼び場所と して組織され、該割当てられる場所は、互いに、また前記占１！ｒ／非占有メモ リ内の前記場所に、リンクされて、可変長の待ち行列構造を構成する。

極めて好ましいさらにもう１つの実施例においては、前記待ち行列メモリは、い くつかの呼びバッファであって、それぞれが少なくとも２つの待ち行列場所を割 当てられる該いくつかの呼びバッファと、該少なくとも２つの待ち行列場所の状 態を示すマーカ領域と、を有する。

図面の説明 以下、本発明を実施例により、添付図面を参照しつつ詳細に説明する。添付図面 において、 第１図は、゛端末装置が接続されたディジタルスイッチの機能ブロック図であり 、第２図は、第１図のスイッチにおける制御および肯定応答パヶ引・の論理形式 第３図は、本発明の第１実施例における、占有／非占有メモリと、待ち行列メモ リとの配置を示し、 第４図は、本発明の第２実施例における、占有／非占有メモリと、待ち行列メモ リとの配置を示し、 第５図は、本発明の第３実施例における、占有／非占有メモリと、待ち行列メモ リとの配置を示し、 第６図は、第１図のスイッチの細部を示し、それは、占有／非占有メモリと、待 ち行列メモリと、か接続された制御メモリ端末の内部構造を示している。

大嬶便 第１図において、ディジタルスイッチは全体的に２によって示されている。スイ ッチ２に対しては、端末装置４人ないし４Ｍが接続さね、これらの端末装置は、 それらの送信側および受信側から接続されたものの双方が示されているが、同し 端末装置の送信側および受信側は一緒に１つの物理的装置を構成している。前記 スイッチは、例えはプロセッサユニットを含みうる端末装置４がらのトラヒック を物理的に集信すへく配置された、１つのマルチプレクサ６を含む。該トラヒッ クは、データタイムスロットと、制御タイムスロットとに論理的に分割され、該 データタイムスロットは前記集信後にさらに論理的に分離され、一方該制御卸タ イムスロットは結合せしめられて共通リソースを形成する。

デマルチプレクサ８は、前記データタイムスロットと、前記制御タイムスロット とを分離するように配置され、スイッチメモ１月０は該データタイムスロットを 受取る。制御メモ１月２は、スイッチメモ「月Ｏ内のデータタイムスロットの総 合接続を行う際に用いられる情報を含む。制御メモリ端末１４は、制御パケット を含む制御タイムスロットを受取り、情報を制御メモリ１２内へ書込み、また接 続か完了したか、または受信する端末装置は占有されているか、に関する情報を 仔する肯定応答バケツ１−を呼出しを行っている端末装置へ送信する。

第２図は、制御パケットおよび肯定応答パケットのそれぞれの外観を概略的に示 す。

第２図において、制御パケットは、動作の種類（接続または切断）を示す「動作 コード」と、「制御番号」と、アドレス指定された受信端末装置を示す「論理受 信機」と、アドレス指定された送信端末装置を示す「論理送信機」と、制御要求 を送信する端末装置の物理アドレスを示す「物理出所アドレス」と、を含む。

第２図において、肯定応答パケットは、最初の制御要求を送信した端末装置の物 理アドレスを示す「物理宛先アドレス」と、肯定応答の種類（それぞれの動作完 了、動作未完了）を示す１定応答コード」と、　「制御番号」と、を含む。

制御メモリ端末は、制御パケットから「物理出所アドレス」を拾い、それを肯定 応答パケット内の「物理宛先アドレス」として用いる。「制御番号」は、もしい くつかの待ちかあった場合に、いずれの制御か行われるかを、制御を要求してい る端末装置か知りうるように、肯定応答により送り返される。

占有／非占有メモリ１６は制御メモリ端末１４と共に働き、それぞれの端末装置 の受信機の実際の状態に関する記憶情報を含む。

第２マルチブレクザ１８は、制御メモリ端末１４からの制御タイムスロツ１−と 、スイッチメモリＩＯからのデータタイムスロットとを、同し物理リソースに関 して挿入するように配置されている。第２デマルチブレクザ２０は、それぞれの 受信端末装置へのタイムスロットを分離するように配置され、一方、肯定応答パ ケットは、アドレス指定された端末装置へ送られる。

第１図のスイッチに関して上述されたこと、および以下の機能の説明は、ＰＣＴ ／ＳＥ　９２１００８１９にも記載されており、それからはさらに詳細な説明か 得られる。

１つの端末装置、例えば４Ａからは、スイッチメモ１月０による接続のための制 御パケットか送信される。この制御パケットは、マルチプレクサ６に至るまでの 総合接続されたデータと同じルートを用いる。該制御パケットは、そこで分離さ れ、さらに制御メモリ端末１４へ送られる。

該制御パケットはこの場合、定められたリンクを指示する関連のスイッチングデ ータによる接続を示す、動作コードを含む。制御メモリ端末Ｉ４は、動作要求お よび関連スイッチングデータを、スイッチメモ１月０により要求された接続の実 際の状態と比較する。それぞれの接続の実際の状態は、占有／非占有メモ１月６ 内に記憶されている。

もし占有／非占をメモ１月６か、接続要求において、アドレス指定された受信機 、例えば端末装置４Ｍか非占有であることを示せば、制御メモリ端末は、占有／ 非占有メモ１月６内の「非占有」状態を「占有」状態へ変化させ、新しい接続を 制御メモ１月２内へ書込み、それによってスイッチメモ１月０からの読取りに影 響を与えて、端末装置４Ａから端末装置４Ｍへの単向データルートか確立される ようにする。

制御端末１４は、次にマルチプレクサ１８を経て端末装置４Ａへ肯定応答を送信 し、後昔に接続要求か達成されたことを知らせる。

もし、ここで例えは端末装置４Ｂかリンクを端末装置４Ｍへ接続しようとすれば 、制御メモリ端末１４は、占有／非占有メモリ１６を経て端末装置４Ｍか占有さ れていることを知る。

本発明か処理しようとしているのは、この状況およびそれに起因する諸問題であ る。

上述のＰＣＴ／ＳＥ　９２１００８１９によれば、制御メモリ端末１４は端末装 置４Ｂへ、アドレス指定された受信機か占有されている旨の情報を含む肯定応答 パケットを送信する。その間接的結果として、端末装置４Ｂは後に接続を試みな くてはならない。

これは理想的な解決ではなく、それは、端末装置４Ｂか正に接続を試みようとす る時に、例えは端末装置４Ｃか割込めば、端末装置４Ｍか常に占有状態にあると いう不公平を生じうる。もう１つの欠点は、もし例えば端末装置４Ｂかその接続 要求を含む制御パケットを、該端末装置４Ｂか無準備状態にならないように高頻 度で繰返せば、制御メモリ端末１４か圧迫を受けることである。

本発明によれば、以下に詳述される「公平な待ち行列機能Ｊのためのシステムの 導入により、　「高速回路スイッチ」に伴うこれらの欠点は解消されつる。必要 な機能的追加は、第１図に全体的に２２によって指示されており、実施用メモリ と、ソフトウェアまたはハードウェアでありうる制御論理装置とにより構成され る。

以下の説明かられかるように、端末装置ｔＢにおける相違は、それが、上述の例 のように、端末装置へに既に接続されている端末装置Ｍへの接続を試みる時、メ ツセージの要求を待ち行列に登録され、肯定応答である「接続要求を待ち行列に 登録済み」を受けることである。

端末装置Ｍか切断要求を存する制御パケットを送信すると、制御メモリ端末１４ は直ちに端末装置Ｂを端末装置Ｍに接続し、かつ肯定応答を、Ｍ（ｒ要求達成済 み」）と、Ｂ（ｒ待ち行列に登録された接続要求達成済み」）との双方へ送る。

これは、「占有され、かつ待ち行列に登録済み」という状態コードを占有／非占 有メモ１月６に追加し、また関連ポインタを、待ちメツセージが記憶されている 待ち行列メモリ２４に追加することによって、行われる。

この特別機能を「高速回路スイッチ」か要求する速度で管理するためには、さら に制御メモリ端末１４内に追加の論理装置か必要である。

第１実施例においては、占有／非占有メモ１月６内のそれぞれの場所に対し、１ つまたはそれ以上の待ち行列場所か割当てられつる。この場合は、待ち行列メモ リ２４に対するポインタの必要はない。そのわけは、そのようなポインタは、元 来占有／非占有メモリ１６内のアドレスによって表示されるものと理解されるか らである。占有／非占有メモリ１６内の１つの場所はまた、（第２図に関連して 上述された定義による）「論理受信機」をも表し、その場合、場所１は例えば端 末装置へを表し、場所２は端末装置Ｂを表し、なととなる。

第３図は、機能的に簡単なこの第１実施例における、占存／非占存メモリ１６お よび待ち行列メモリ２４の配置を示す。

占有／非占有メモ１月６は、いくつかの場所を含み、そのそれぞれが２６に示さ れている状態コードを存する。これらの状態コードは、　「非使用」、　「非占 有Ｊ、［占有され、かつ待ち行列に登録済み」、「占有され、かつ待ち行列に未 登録」である。「占有され、かつ待ち行列に登録済み」および［占有され、かつ 待ち行列に未登録」の状態をコードに直接述べることは、それが、待ち行列メモ リ２４内の２６に示されている機能［領域記述」内のポインタ値からもわかるの で、必要ではない。しかし、制御パケット内の動作コード（第２図参照）の１つ は、　［もし非占有ならば接続し、もし待ち行列における前方に何もなけれは待 ち行列に登録せよＪてありうるので、管理の観点からは、これを占有／非占有メ モ１６内の状態コート内に示すほうか有利である。

占有／非占有メモ１６内のそれぞれの場所２６は、ポインタ２８によって指示さ れているように、待ち行列メモリ２４内の自身の「呼び領域」　３０を指示し、 該「呼び領域ｊは、占有／非占有メモ１月６内の全ての場所２６に対して等しい 大きさであるあらかしめ定められた大きさを有する。それぞれの「呼び領域」３ ０内には、「領域記述Ｊ３１と、いくつかの「呼び」３２のための場所と、か含 まれている。それぞれの「呼び領域」は、３４に示されている「制御番号ｊ１「 論理送信機」、および「物理宛先アドレス」　（第２図参照）を含むいくつかの 呼び３２を記憶しうる。

「領域記述」のフィールド３２内の３６および３８には、それぞれ「インポイン タ」および［アウトポインタＪか記憶される。

インポインタ３６は、次の呼びかその呼び領域３０のとこへ記憶されるべきかを 指示する。インポインタ３６は、挿入の後にはＩステップたけステップせしめら れ、次の非占有場所を指示する。呼びの挿入においては、インポインタ３６がア ウトポインタ３８と同じ値を持っていないことかチェックされなくてはならない 。もしその場合であれば、サービスされなかった呼びが過剰書込みされないよう に、書込みか阻止されなくてはならない。この場合、制御メモリ端末１４は、受 信機か占有されていること、および待ち行列場所か得られないこと、を示す肯定 応答を送信する。

アウトポインタ３８は、受信機か切断された時に、とのメツセージが次にサービ スを受けるべきかを指示する。もし制御メモリ端末１４が、切断時に状態コート が待ち行列に登録済みであることを検出すれば、受信機のスイッチングデータは 、前記ポインタにより指示されている呼び領域３０の部分から読取られる。接続 の確立後、アウトポインタ３８は次の場所へステップせしめられる。その時、も しインポインタ３６かアウトポインタ３８に等しくなれば、制御メモリ端末１４ は、受信機の状態コートを「占有状態だか、待ち行列には未登録」へ変化せしめ る。もちろん、制御メモリ端末１６はまた、肯定応答を待ち行列登録端末装置へ 送信して、要求された接続か確立されたことを知らせる。「物理宛先アドレス」 　（第２図参照）は、呼び領域３０を指示する呼びから収集される。

呼び領域は循環バッファとして管理され、これはポインタが最後の場所に達した 時、それか最初の場所へステップせしめられることを意味する。

制御メモリ端末１４は、ポインタ３６．３８を、互いに、また呼び領域３０内の 最後の可能な場所と、比較して、上述の処理を行うための、制御論理装置（ソフ トウェアまたはバー１−ウェア）を含むへきである。

簡単な論理的具体化を意味する上述の実施例は、全ての受信機に対して一定の大 きさの呼び領域を確保することにより、待ち行列メモリの無駄な使用を生じつる 。こねは特に、接続された端末装置の少数のもののみがプロセッサユニットであ り、そのまたあるもののみか待ち行列作成機能を用いる必要がある場合に、そう である。

そのような場合に、待ち行列メモリを共通リソースとして用いる実施例は、メモ リ要求を大幅に削減し、前記機能の実施をより実際的なものになしつる。第４図 は、そのような実施例における占有／非占有メモリおよび待ち行列メモリの配置 を示す。

この実施例においては、ポインタ５４か占有／非占有メモリ１６に割当てられ、 このポインタは、占有／非占有メモ１月６内の場所に関連する端末装置の受信機 のための待ち行列メモリ２４内に記憶されている次の呼びを指示する。待ち行列 メモリ２４を、いくつかの「呼び場所」または呼びバッファ５２として組織し、 これらの呼び場所５２を呼びに割当て、該割当てられた場所を、互いに、また占 有／非占仔メモリ内の場所に、リンクさせれば、待ち行列作成構造は可変長に、 かつ前の実施例の機能的に簡単な具体化におけるよりもかなり少ないメモリ消費 により、構成されつる。

もちろん、例えば、前記簡単な具体化において、ある数の呼び場所が既製の待ち 行列作成構造に割当てられるようになっている、待ち行列作成構造の他の変種も また構成されうる。

ここで第４図を参照する。「もし非占有ならは接続し、もし待ち行列場所が得ら れれは待ち行列に登録せよ」という動作コートを存する制御パケットか制御メモ リ端末１４に到着した時、制御メモリ端末１４か占有／非占有メモ１月６を通常 のように読取り、受信機か占有されていることを見出すものとする。その場合は 、制御メモリ端末１４は待ち行列メモリ２２内のマーカ領域５０内において、呼 びバッファ５２の占有されていないものに対するマーカを探索する。マーカ領域 ５０内においては、それぞれのヒント位置は呼びバッファ５２のアドレスを表し 、その内容は非占有または占有を表す。

非占有バッファ５２か見出された時は、そこに呼びか記憶され、このバッファに 対するマーカは占有マークとされ、情報「待ぢ行列に登録済み」を含む肯定応答 か送信される。（もし非占有バッファか発見されなければ、情報「占有され、待 ち行列場所は？ＶられないＪを含む肯定応答か送信される。）前記バッファを呼 びリスト内へリンクさせるために、制御メモリ端末１４は、占存／非占存メモリ １６の、問題になっている場所に関連するインキューポインタ５４を読取る。こ のインキューポインタ５４は、この受信機に対する最後に記憶された呼びか見出 されるへきバッファ場所５２の、待ち行列メモリ２４内における絶対アドレスを 指示する。

もし、ちっと早く記憶された呼びか存在すれは（占有／非占有メモリ１６内にお ける状態は、「占有され、かつ待ち行列に登録済み」となり）、制御メモリ端末 １４は、新しい呼びか記憶されるへきバッファ場所５２の絶対アドレスを、最後 の呼びか記憶されている５６の正にその／１ツファ場所５２に書込み、その場所 ５６か新しい呼びの該バッファ場所５２を指示するようにする。

もし、も、つと早く記憶された呼びか存在しなけれは（占を／非占有メモ１月６ 内における状態は、「占有され、かつ待ち行列に未登録」となり）、制御メモリ 端末１４は、新しい呼びか記憶されるへきバッファ場所５２の絶対アドレスを、 占有／非占有メモリ１６に接続されている、同様に５４にあるアウトキューポイ ンタに対する場所に書込む。次に、前記呼びは、割当てられたバッファ５２内に 書込まれ、その場所５６はクリアされる。

占存／非占存メモ「月６内の非占有マークを存する待ち行列に登録された場所か 、切断要求に関連して読取られる時は、制御メモリ端末１４が、同様に５４にあ る該場所に属するアウトキューポインタを読取り、該ポインタは関連の受信機へ 供給される準備を完了したメツセージを指示する。アウトキューポインタ５４は 、前記呼びのための前記バッファ５２の絶対アドレスを指示する。切断の後、マ ーカ領域５０内の前記バッファ場所は、非占有マークを与えられ、非占有マーク のバッファ場所のためのリンクポインタ５６が、新しいアウトキューポインタと して書込まれる。もしリンクポインタ５６かゼロであるか、またはインキューポ インタかアウトキューポインタに等しければ、これは、それ以上の呼びか待ち行 列に登録されえないことを意味する。その場合制御メモリ端末１４は、やはり占 有／非占有メモ１月６内の状態を「占有され、かつ待ち行列に未登録」へ変化さ せる。

待ち行列メモリ２４を共通リソースとして管理する制御メモリ端末１４内の制御 論理装置を加速するためにハードウェアを追加して、マーカ領域５０内の非占有 バッファ５２を速やかに発見することかできる。この例にはｌ＼−ドウエア論理 装置かあり、これは、組合せ方法により支援されて変数内の最上位の１を発見す る。

第５図には、共通待ち行列リソース２４゛　がある数の呼びバッファ５２′　を 有する実施例か示されている。ことごとくの呼びバッファには、それぞれ２つの 待ち行列場所５２°　１および５２°、２か割当てられている。待ち行列に登録 される必要のある呼びか現れ、呼出された受信機に対する前の呼びが該待ち行列 内になければ、マーカ領域５０゛内において非占有呼びバッファ５２゛か探索さ れる。見出された呼びバッファのアドレスかポインタ５４′　として、占有／非 占有メモ１月６内の呼出された受信機の場所に書込まれ、前記呼びは待ち行列メ モリ２４゛内のマーカ場所に関連する場所に記憶される。マーカ場所内には、１ つの待ち行列場所のみか占有されていることを示すコードが書込まれる。もし同 じ受信機に対する新しい呼びが到着すれば、占有／非占有メモリ１６°は、既に 呼びが待ち行列に登録されていることを示す。そこで、その呼びは、他の待ち行 列場所内に記憶され、前記呼びバッファ５２′　に対するマーカの状態は、双方 の場所５２°、ｌおよび５２’、２が占有されていることと、最後に使用された 場所が待ち行列内の最後の場所であることと、を示すように変化せしめられる。

それぞれの呼びバッファのマーカ領域内に含まれる４ビツトは、以下のようにコ ーディングされるが、なお第５図も参照されたい。

待ち行列場所ｌのみか占有されている；待ち行列場所２のみか占有されている； 双方の待ち行列場所か占有され、待ち行列場所ｌが待ち行列内の最後の場所であ る。

双方の待ち行列場所か占有され、待ち行列場所２か待ち行列内の最後の場所であ る。

他のコードは、双方の場所か非占有であることを示す。別の他のコードは、呼び バッファ内の待ち行列場所の数を拡大するために用いられつる。

問題になっている受信機か非占有になり、占有／非占有メモリ１６’内の状態が 、待ち行列に登録された呼びが存在していることを示している時は、ポインタ５ ４′か読取られ、該ポインタにより待ち行列内の最初の場所として指示されてい る場所に記憶されている呼びか接続される。その後、マーカの状態は、場合に応 じて、双方の場所か非占有であること、または一方の場所のみが占有されている こと、を示すように変化せしめられる。もし最終結果として、双方の場所か非占 有になっていれば、占有／非占有メモ１月６°内の状態も「接続済みで、待ち行 列に未登録」に変化せしめられる。

第６図は、制御メモリ端末１４か占有／非占有メモ１月６および待ち行列メモリ ２４と共に、本質的に公知であるマイクロプロセッサ構造と、中央組合せ論理装 置としての演算装置６０と、システムバス６２．６４．６６により接続された諸 メモリおよび諸機能装置と、によりとのように内部的に設計されつるかを示す。

関連の制御装置７０を存するプログラムメモリ６８は、制御バス７２を経て、そ れぞれのプログラムステップにおける諸装置間の相互作用を制御する。上述され た、変数内の最上位の１を速やかに見出す装置は、７４によって示されている。

制御パケットのための呼びＦＩＦＯは７６によって示され、肯定応答パケットの ための肯定応答ＦＩＦＯは７８によって示されている。

行われる動作の流れは、矢印の方向かられかる。

その場合、待ち行列作成機能に関連する制御動作においては、以下の動作コード が可能である。

■、　もし非占有であれば接続し、もし占有ならは待ち行列に登録するな。

Ｚ　もし非占有であれば接続し、もし待ち行列内の前に呼びがなければ待ち行列 に登録せよ。

λ　もし非占有てあれは接続し、もし待ち行列場所が得られれば待ち行列に登録 せよ。

４、切断せよ（待ち行列に登録された呼びを接続せよ）。

５、待ち行列に登録された呼びを除去せよ。この指令は、待ち行列に登録された 呼びについて新しい接続かなされるべき時に、前述のように処理される。相違は 、接続がなされないことと、全呼び領域およびリンクされたリストが、占有／非 占有メモ１月６内の状態か［占有され、かつ待ち行列に未登録」にセットされる 前にクリアされることと、のみである。その後、適切な肯定応答「要求達成済み 」か送信される。

待ち行列作成機能に関連する以下の肯定応答が可能である。

１、接続を達成済み。

Ｚ　接続要求を待ち行列に登録済み。

３、待ち行列に登録された接続要求を達成済み。

４、要求を達成済み（切断せよ、待ち行列内の呼びを除去せよ）。

５、　占有され、待ち行列場所は得られない。

制御パッケージ　肯定応答パ・ンケージ

Claims (1)

1. 【特許請求の範囲】 １．いくつかの端末装置（４Ａ−Ｍ）のために働いて、該端末装置間の信号トラ ヒックのスイッチングを行うディジタルスイッチにおいて、該トラヒックは論理 的にデータタイムスロットおよび制御パケットを有する制御タイムスロットに分 割され、前記ディジタルスイッチが、前記データタイムスロットを受取るスイッ チメモリ（１０）と、該スイッチメモリ内の該データタイムスロットの総合接続 を容易ならしめる情報を含む制御メモリ（１２）と、 前記制御タイムスロットおよびその中に存在する制御パケットを受取り、前記制 御メモリ（１２）内へ情報を書込み、呼出されたおよび呼出している前記端末装 置へ肯定応答パケットを送信する、制御メモリ端末（１４）と、該制御メモリ端 末（１４）と協働してそれぞれの前記端末装置の実際の状態を記憶する占有／非 占有メモリ（１６）と、を含み、 前記制御メモリ端末（１４）および前記占有／非占有メモリ（１６）に関連する 待ち行列システムであって、該待ち行列システムが、第１端末装置（４Ｂ）が、 占有されている第２端末装置（４Ｍ）への接続を確立しようとする場合に、 呼び要求の待ち行列への登録と、前記第１端末装置への肯定応答「接続要求を待 ち行列へ登録済み」の送信とを行い、かつ前記第２端末装置からの切断要求を受 信した時に、 前記第１端末装置の前記第２端末装置への直接接続を行い、前記第１および第２ 端末装置へ、それぞれ情報「接続達成済み」および「要求達成済み」を含む肯定 応答の送信を行う、メモリ手段および制御論理手段を含むことを特徴とする、デ ィジタルスイッチ。 ２．待ち行列メモリ（２４）と、前記占有／非占有メモリ（１６）が、「占有さ れ、かつ待ち行列に登録済み」という端末装置の状態コードと、前記待ち行列メ モリに対する関連の第１ポインタ（２８）と、のための場所を含むことと、を特 徴とする、請求項１記載のディジタルスイッチ。 ３．前記占有／非占有メモリ（１６）内のそれぞれの場所に、１つまたはいくつ かの待ち行列場所が割当てられていることと、前記ポインタ（２８）が、該占有 ／非占有メモリ内のアドレスにより実現されていることと、を特徴とする、請求 項２記載のディジタルスイッチ。 ４．前記占有／非占有メモリ（１６）内のそれぞれの場所が、アドレス指定され る受信端末装置を表すことを特徴とする、請求項３記載のディジタルスイッチ。 ５．前記占有／非占有メモリ（１６）がいくつかの場所を含み、そのそれぞれが 「非使用」、「非占有」、「占有され、かつ待ち行列に登録済み」、および「占 有され、かつ待ち行列に未登録」を意味する状態コードを有することを特徴とす る、請求項４記載のディジタルスイッチ。 ６．前記待ち行列メモリ（２４）内において、次の呼びが記憶される場所と、受 信装置が切断された時に代わりに供給されるべき呼びと、をそれぞれ指示する第 ２および第３ポインタ（３６、３８）が、「占有され、かつ待ち行列に登録済み 」および「占有され、かつ待ち行列に未登録」の状態を指示することを特徴とす る、請求項５記載のディジタルスイッチ。 ７．前記待ち行列メモリ（２４）内における、最後に記憶された受信機の呼びが 見出されるべきバッファ場所（５２）の絶対アドレスと、関連する受信機に対し 供給される準備を完了した呼びのためのバッファ場所（５２）の絶対アドレスと 、をそれぞれ指示する第４および第５ポインタ（５４）が、「占有され、かつ待 ち行列に登録済み」および「占有され、かつ待ち行列に未登録」の状態を指示す ることを特徴とする、請求項５記載のディジタルスイッチ。 ８．前記占有／非占有メモリ（１６）内のそれぞれの場所が、待ち行列メモリ（ ２４）内の自身の呼び領域を指示し、該呼び領域が、該占有／非占有メモリ内の 全ての場所に対して同じであるあらかじめ定められた大きさを有し、かつ領域画 定のためのフィールド内に、制御番号、アドレス指定される送信端末装置、およ び最初の制御要求を送信した端末装置に対する物理宛先アドレス、を含むいくつ かの呼びを記憶しうることを特徴とする、請求項６または請求項７記載のディジ タルスイッチ。 ９．前記第２および第３ポインタ（３６、３８）が、前記待ち行列メモリ（２４ ）内の領域記述のための前記フィールド内に記憶されることを特徴とする、請求 項６および請求項８記載のディジタルスイッチ。 １０．前記第２および第３ポインタ（３６、３８）を、互いに、また前記呼び領 域内の最後の可能な場所と、比較するための、前記制御メモリ端末（１４）内の 制御論理装置（７０）を特徴とする、請求項９記載のディジタルスイッチ。 １１．前記待ち行列メモリ（２４）が共通リソースとして用いられることを特徴 とする、請求項１記載のディジタルスイッチ。 １２．前記占有／非占有メモリ（１６）に割当てられたポインタ（５４）が、該 占有／非占有メモリ内の場所に関連する端末装置の受信機のための前記待ち行列 メモリ（２４）内に記憶されている次の呼びを指示することを特徴とする、請求 項１１記載のディジタルスイッチ。 １３．前記待ち行列メモリ（２４）が、呼びが割当てられるいくつかの呼び場所 として組織され、該割当てられる場所が、互いに、また前記占有／非占有メモリ （１６）内の前記場所に、リンクされて、可変長の待ち行列構造を構成すること を特徴とする、請求項１２記載のディジタルスイッチ。 １４．前記待ち行列メモリ（２４）内に含まれるマーカ領域（５０）から非占有 の呼び場所を見出すためのハードウェア（７４）を特徴とする、請求項１３記載 のディジタルスイッチ。 １５．前記待ち行列メモリ（２４）が、いくつかの呼びバッファ（５２）であっ て、それぞれが少なくとも２つの待ち行列場所を割当てられる該いくつかの呼び バッファ（５２）と、該少なくとも２つの待ち行列場所の状態を示すマーカ領域 と、を有することを特徴とする、請求項１１記載のディジタルスイッチ。 １６．待ち行列に登録される必要のある呼びが現れた時、非占有の呼びバッファ を求めて前記マーカ領域の探索を行い、該探索の結果として見出された呼びバッ ファのアドレスを、ポインタとして前記占有／非占有メモリ内の呼出された受信 機に関連する場所に書込み、前記呼びを、前記待ち行列メモリ内の前記見出され た呼びバッファに関連する前記マーカ内の場所に関連する場所に記憶する、手段 を特徴とする、請求項１５記載のディジタルスイッチ。 １７．前記手段がさらに、ある呼びバッファに関連するマーカ場所を更新するコ ードを、該呼びバッファの待ち行列場所の状態に変化が起こる毎に、前記マーカ 領域内に書込む手段を含むことを特徴とする、請求項１６記載のディジタルスイ ッチ。 １８．呼びパッファが２つの待ち行列場所を有する場合に、該呼びバッファが該 呼びバッファに対して割当てられた４ビットを前記マーカ領域内に有し、該４ビ ットが以下のようにコーディングされていることを特徴とする、請求項１７記載 のディジタルスイッチ。 待ち行列場所１のみが占有されている；待ち行列場所２のみが占有されている； 待ち行列場所１および２が占有され、待ち行列場所１が待ち行列内の最後の場所 である；及び 待ち行列場所１および２が占有され、待ち行列場所２が待ち行列内の最後の場所 である。 １９．前記マーカ内の他のコードが、双方の前記場所が非占有であることを示す ことを特徴とする、請求項１８記載のディジタルスイッチ。 ２０．呼びバッファ内の待ち行列場所の数を２を超えて拡大するための、前記マ ーカ領域内の他のコードを特徴とする、請求項１８または請求項１９記載のディ ジタルスイッチ。