(57)【要約】相互接続構造(200)は、複数の入力ポート(204)と複数の出力ポート(252)とを含み、メッセージMが、スイッチS(210,224)を通じて入力ポートから所定の出力ポートに送信される。スイッチSの設定が個々のメッセージが送信される前記所定の出力ポートに依存しないことが有利である。
2006508558.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力ポートと複数の出力ポートとを含む相互接続構造であって、
メッセージMが入力ポートから所定の出力ポートへスイッチSを通って送信され、
前記スイッチSの設定は、前記メッセージMが送信される前記所定の出力ポートに依存しないものである、相互接続構造。
【請求項２】
請求項１に記載の相互接続構造において、
前記スイッチSの設定がマスタークロックによって決定される、
ことを特徴とする相互接続構造。
【請求項３】
複数の入力ポートと複数の出力ポートとを含む相互接続構造であって、
メッセージMが入力ポートから所定の出力ポートへスイッチSを通って送信され、
前記メッセージMはヘッダセグメントとデータセグメントとから構成され、
前記スイッチSの設定は、前記メッセージMのヘッダセグメントに依存しないものである、相互接続構造。
【請求項４】
請求項３に記載の相互接続構造において、
前記スイッチSは、２つの別個のスイッチ区画であるスイッチ区画S1とS2とを含み、
前記メッセージMが入力ポートから出力ポートへ前記スイッチ区画S1とS2との両者を通って送信される、ことを特徴とする相互接続構造。
【請求項５】
請求項４に記載の相互接続構造において、
前記スイッチ区画SIとスイッチ区画S2との設定がマスタークロックによって制御される、ことを特徴とする相互接続構造。
【請求項６】
請求項５に記載の相互接続構造において、
マスタークロックによって制御された任意の時間間隔において、前記スイッチ区画S1とスイッチ区画S2の設定が同じである、
ことを特徴とする相互接続構造。
【請求項７】
請求項６に記載の相互接続構造において、
前記入力ポートに入力されたとき、前記メッセージMは複数のセグメントに分割され、各セグメントは、さらにサブセグメントに再分割される、
ことを特徴とする相互接続構造。
【請求項８】
請求項７に記載の相互接続構造において、
前記スイッチ区画S1と前記スイッチ区画S2とが複数の共有バッファを利用し、
前記共有バッファは、前記スイッチ区画S1から前記スイッチ区画S2にデータが移動するのに応じてデータを一時的に格納する、
ことを特徴とする相互接続構造。
【請求項９】
請求項８に記載の相互接続構造において、
メッセージMが前記スイッチ区画SIとスイッチ区画S2との間で移動するのに応じて、前記共有バッファは複数でありそれら各々における同じ相対位置に、前記メッセージセグメントのサブセグメントが格納される、
ことを特徴とする相互接続構造。
【請求項１０】
複数の入力ポートと複数の出力ポートとを含む相互接続構造であって、
入力ポートに接続されたロジックがメッセージMをデータ記憶装置Uに格納し、
前記相互接続構造の出力ポートOPに接続されたロジックは、前記データ記憶装置Uから前記出力ポートOPにメッセージMを移動するのに使用される、
相互接続構造。
【請求項１１】
請求項１０に記載の相互接続構造において、
メッセージMが前記データ記憶装置Uから前記出力ポートOPに送信されるときに通過する、スイッチS、をさらに含む、
ことを特徴とする相互接続構造。
【請求項１２】
請求項１１に記載の相互接続構造において、
前記メッセージMはヘッダセグメントとデータセグメントとから構成され、
前記スイッチSの設定は、前記メッセージMのヘッダセグメントに依存しないものである、相互接続構造。
【請求項１３】
請求項１２に記載の相互接続構造において、
前記スイッチSは、スイッチ区画S1とS2とから構成される、
ことを特徴とする相互接続構造。
【請求項１４】
請求項１３に記載の相互接続構造において、
前記スイッチ区画S1とS2との設定はマスタークロックによって制御され、前記スイッチ区画S1とS2との設定は、前記マスタークロックによって決定される各時間間隔は同じにされる、
ことを特徴とする相互接続構造。
【請求項１５】
複数の入力ポートと複数の出力ポートとを含む相互接続構造であって、
複数のメッセージMが、前記複数の入力ポートから前記複数の出力ポートへ送信され、
前記メッセージMの各々は、前記相互接続構造内における所定の状態を持ち、
前記相互接続構造は、
さらに、出力ポートOPに接続されたロジックを含み、このロジックは、前記出力ポートOPを目標とするメッセージMのために、前記相互接続構造内のメッセージMの前記状態を前記複数の入力ポートに知らせる、相互接続構造。
【請求項１６】
請求項１５に記載の相互接続構造において、
メッセージMが前記複数の入力ポートから前記複数の出力ポートに送信されるときに通過する、スイッチSを含み、
メッセージMがヘッダセグメントとデータセグメントとから構成され、
前記スイッチSの設定は、前記メッセージMのヘッダセグメントに依存しないものである、
ことを特徴とする相互接続構造。
【請求項１７】
請求項１６に記載の相互接続構造において、
前記スイッチSがスイッチ区画S1とスイッチ区画S2から構成され、
前記相互接続構造は、
さらに、前記スイッチ区画S1とスイッチ区画S2との設定を制御するマスタークロックを含む、
ことを特徴とする相互接続構造。
【請求項１８】
相互接続構造であって、
ロジックLが付いた少なくとも１つの入力ポートIPと、少なくとも１つの出力ポートとを持ち、
前記ロジックLが前記入力ポートIPに接続され、
前記相互接続構造は、
メッセージMを装置Bpに送信するための複数の出力ラインL0,L1〜Lj-1を持ち、
前期Bpを目標とするメッセージMが前記入力ポートIPに到着したとき、前記ロジックLが前記出力ラインのうちの１つに接続された出力ポートOPを選びメッセージMを受信する、
ことを特徴とする相互接続構造。
【請求項１９】
請求項１８に記載の相互接続構造において、
前期ロジックLは、所定の出力ポートOPにメッセージMを方向付ける、
ことを特徴とする相互接続構造。
【請求項２０】
請求項１９に記載の相互接続構造において、
前記ロジックLは、メッセージMを出力ポートOPに送信するために出力ポートOPに接続されたロジックL1に要求を出す、
ことを特徴とする相互接続構造。
【請求項２１】
請求項２０に記載の相互接続構造において、
前記ロジックLは、前記メッセージＭを受信するため出力ポートOPの可用性に関連する情報を持つ前記ロジックLに基づき、前記メッセージMのための目標として出力ポートOPを選択する、
ことを特徴とする相互接続構造。
【請求項２２】
複数の入力ポートと複数の出力ポートとを含む相互接続構造であって、
メッセージMが入力ポートから所定の出力ポートへ送信され、
前記相互接続構造が、
さらに制御データを生成するためのロジックを含み、
前記制御データは、
前記メッセージMを運ぶ経路とは別の前記相互接続構造内の経路で運ばれる、
相互接続構造。
【請求項２３】
請求項２２に記載の相互接続構造において、
前記メッセージMは、ヘッダセグメントとデータセグメントとを含み、
前記相互接続構造は、個々の出力ポートがメッセージMを受信することに利用可能であるか否かを示すアクセス情報を生成し、
前記制御データは、前記ヘッダ情報以外の情報と、前記アクセス情報以外の情報とを含む、
相互接続構造
【請求項２４】
相互接続構造の複数の別個の装置を通じて制御情報を送信する方法であって、
複数の入力ポートから複数の出力ポートにメッセージMを送信するステップと、
前記複数の入力ポートの１つであるBに接続されたロジックから制御情報を生成するステップと、
メッセージMとは別の経路で前記制御情報を前記複数の出力ポートの１つであるAに送信するステップと、
を含む方法。
【請求項２５】
請求項２４に記載の方法において、
さらに、マスタークロックで前記相互接続構造の設定を制御するステップ、
を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音声とビデオ通信システムおよびデータ／インターネット接続に適用可能な相互接続構造をコントロールする手段と方法とに関連する。より具体的には、本発明はインテリジェント制御によって共用メモリ相互接続スイッチ技術を目的とする。
開示したシステムおよび操作方法は、下記の特許および出願で開示した主題に関するものであり、これらの全体を参照によって本願に合体させるものとする。
1. 発明者、コークス  Ｓ.リードによる米国特許No.5,996,020「複数レベル最小ロジックネットワーク」
2. 発明者ジョンヘッセによる、米国特許No. 6,289,021「相互接続構造での使用のためのスケーラブルな少ない待ち時間スイッチ」
3. 発明者ジョンヘッセによる、米国特許出願シリアルNo. 09/693,359「複数のパスワームホール相互接続」
4. 発明者ジョンヘッセとコークスリードによる、米国特許出願シリアルNo09/693,357「スケーラブルなワームホールルーティングコンセントレータ」
5. 発明者ジョンヘッセとコークスリードによる、米国特許出願シリアルNo.09/693,603「並列コンピューティングと並列のメモリアクセスのためのスケーラブルな相互接続構造」
6. 発明者ジョンヘッセとコークスリードによる、米国特許出願シリアルNo. 09/693,358は「サービスの質(QoS)処理を利用しているスケーラブルな相互接続構造」
7. 発明者ジョンヘッセとコークスリードによる、米国特許出願シリアルNo. 09/692,073「複数の制御線を使って複数レベル最小ロジックネットワークのスループットを増大させるためのスケーラブルな方法と装置」
8、発明者ジョンヘッセとコークスリードによる、米国特許出願シリアルNo.xx/xxx、xxxは、「インテリジェント制御によるスケーラブルな輻輳フリーなスイッチシステムのための方法と装置」
【背景技術】
【０００２】
従来技術で見られる単純なデータパケットスイッチシステムは、Ｎ個の入力ポートI0,I1,…,IN-1をＮ個の出力ポートO0,O1,…,ON-1に接続するN×Nスイッチ構造S(しばしば、クロスバー)から成る。図１に示す一般的な構造では、クロスバー交換機104に入力するのを待っているパケットを保持する入力部に、IB0,IB1,…,IBN-1のバッファ102がある。幾つかの構造においては、OB0,OB1,…,OBN-1の出力バッファ106を持つこともある。さらに、クロスバーをコントロールする幾つかのロジック(図示せず)がある。
【０００３】
N個の入力ポートを持つ1つの単純な実施態様においては、スイッチをコントロールするラウンドロビン方法がある。ラウンドロビン手順は、最初に整数0,1,…,N-1を順番(sequence)P(0),P(1),…,P(N-1)に変える。そして、N×Nスイッチを設定するロジックは、最初に、入力ポートバッファIBp(o)でデータパケットを最初に検査し、スイッチを通して最も送りたいパケットpoを選ぶ。目標（宛先）出力ポートまたは目標出力ポートバッファが、パケットp0を受け取ることができるならば、ロジックはスイッチ接続を設定してpoをその目標に送信する。poの目標出力（即ち宛先）がpoを受けられる状態でない場合は、ロジックは、その目標へのIBp(0)において別のパケットp1をその目標に送信することを試みる。このプロセスは、1)IBp（o）においてパケットpnがその目標に送信可能であることがわかるまで、或いは、2)そのようなパケットが何もないと分かるまで続けられる。1)のケースでは、クロスバー接続が設定される。2)のケースでは、次のメッセージ送信期間にはIBP(0)からは何もメッセージを送信しないこととなる。この時点で、スイッチを通ってIBp(1)にあるパケットを送るようにロジックはスイッチを設定する。IBp(1)からパケットqをその目的地に送信する場合には、当該目的地がメッセージを受信する準備ができている状態にある必要がり、さらには、pとqとが同じ出力に送られるものでない必要がある。一般に、このプロセスは、バッファIBP(K)内のどのパケットも、IBP(J)からのパケットを受信するために既にスケジュールされた出力に送信されないという制約のもとで続行される（ここでJ＜Kである）。一旦、スイッチが完全に設定されると、パケットが送信され、手順は新たな順列Q(0),Q(1),…,Q(N-1)で繰り返される。新しい順列の理由は、シーケンスのうちの若いメンバーが後の方のメンバーより優先されることであり、公正のために、スイッチの設定毎に整数を再編成することが必要であることである。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来のメッセージ管理スキームには下記のような幾つもの欠点がある。
1) スイッチのセッティングに時間を浪費する。
2) スイッチのセッティングが最適ではない。
3) どの2つの出力ポートも同時に、同じ入力ポートから別個のメッセージを受け取ることができない。
セッティングが最適ではない例が、IBP(J)にある優先度の低いメッセージがIBP(K)にある優先度の高いメッセージをブロックしてしまうことである（ここでJ＜K）ケースである）。共用メモリスイッチシステムには様々な態様があるが、同じ3つの問題が、これらの態様の全てに存在する。欠点1,3を克服するシステムの例が「複数レベル最小ロジックネットワーク（MLMLネットワーク）」（発明＃１）であり、これは1999年11月30日にコークスS.リードによる特許No.5,996,020号である、これらの教示を参照によって本明細書に合体させるものとする。欠点1,3を克服するシステムの別の例が「「相互接続構造での使用のためのスケーラブルな少ない待ち時間スイッチ」（発明＃２）であり、これは1998年1月20日にジョンヘッセによって出願された米国特許出願シリアルNo.09/009,703号である。欠点２を克服するシステムは、ジョンヘッセとコークスリードによる、米国特許出願シリアルNo.xx/xxx、xxx「インテリジェント制御によるスケーラブルな輻輳がないスイッチシステムのための方法と装置」（発明＃８）である。このシステムは、発明＃１と＃２において説明されたタイプの相互接続構造を使う。発明#8におけるキーとなるアイデアは、共通の出力ポートを目標とするメッセージのすべてを一緒に考慮することによってデータスイッチへのパケット入力をコントロールすることである。
【０００５】
それは、欠点1、2、および3に打ち勝つ新規な技術を使用することが本発明の目的である。これらの技術は、発明＃８の、共通の出力ポートを目標（宛先）とするメッセージを比較することに基づき、システムのコントロールを確立するキーとなるアイデアを使う。しかしながら、本発明は自身のルーティングネットワークの使用を必要とせず、むしろ、新規なデータ管理技術に依存するものである。本発明が効果的にどのように共用メモリスイッチシステムを管理するかを示す。
【課題を解決するための手段】
【０００６】
発明の概要
本発明の1態様の概略図である図2を参照されたい。システムに入力されるデータは、1つのデータセグメントを共用メモリバッファのバンクに分散させる第１のN×NスイッチS１を通して供給される。それから、データは、データを出力データバッファに送信する2番目のN×NスイッチS2を通してこれらのバッファから送られる。本明細書中において後で説明するが、ある方法でデータを分散することで、どのメッセージをスイッチS2を通じて送信するのかを選択するために良い戦略をもたらすことを可能にする。さらに、SIとS2とのスイッチに関して時間を浪費しないデータ依存方法が提供できるように、クロックによって制御された体系的な方法でスイッチS1とS2は切り換える。
【０００７】
次の説明では、コントローラまたはバッファなどのN項目のシーケンスを使用する。これらのアイテムは、整数0、1、2を使って、ラベルをつけて、その結果、これらのシーケンスの1つが、X0,X1,X2,…,XN-1で示される。説明するのに便利なように時にはXJ+K或いはXJ-Kとすることもある（ここで、JとKのそれぞれは0からN-1の範囲にある整数である）。（Ｊ＋Ｋ）および（Ｊ−Ｋ）が0からN-1の範囲内に存在しなければならないため、モジュロＮ（mod N）演算を使用する。従って、“Ｊ＋Ｋ”および“Ｊ−Ｋ”が添字として使われる時には、「J+K」は、（Ｊ＋Ｋ＋Ｎ）モジュロNのための簡易な記載形式であり、「J-K」は（Ｊ−Ｋ＋Ｎ）モジュロNのための簡易な記載形式であると理解される。例えば 、N=8、J=5、およびK=7である場合、(J+K+L)mod N = (5+7+8)mod 8 = 4であり、(J-K+L)mod N = (5-7+8)mod 8 = 6である。
【０００８】
Ｎ個の入力のそれぞれは、ラインカード202に供給され、このカードはスイッチング（切り替え）システムへのエントリのためにデータを前処理する。ラインカードは、データをデータライン212を通じて入力コントローラ204(IC0,IC1,…,ICN-1)に送信する。入力コントローラは、パケットを長さSLビットのセグメントに分割し、それから、さらにセグメントを、各々が長さFLビットのN個のサブセグメント（フリット）に再分割する。SL=N・FLであり、これらの2つの値が、スイッチシステムのサイズとそれが処理するパケットのサイズに対して最適化されるように、FLとSLは選ばれる。入力コントローラは、ロジックとメモリバッファ(図2では示さず)とを含む。入力コントローラは多くの機能を実行する。それらはライン208を通じてフリットをS1-210に送信する。データはライン220を通ってS1から共有バッファ222(SB0,SB1,…,SBN-1)に移動する。所定の入力コントローラは共有バッファのすべてにおいてデータを格納する。実際には、各セグメントはN個のフリット（F0、F1,… ,FN-1で示す）から構成され、所定のメッセージセグメントのために、入力コントローラは、共有バッファのそれぞれに１つのフリット（サブセグメント）を置く。図2は、メッセージセグメ ントのフリットが共有バッファのそれぞれの中の同じ相対配置に記憶されている灰色領域234を示す。データは、共有バッファからライン228を通ってスイッチS2(224)に移動する。データは、その後、S2からライン230を通って出力コントローラ に進む。最後に、データは出力コントローラから相互接続ライン232を通じてラインカード202に移動する。
【０００９】
スイッチSIとS2は系統的な方法で動作する。この最も簡単な態様において、S1とS2がクロスバースイッチであると仮定する。この単純な実施態様では、データはビット直列か、或いはより広い経路で移動することができる。ここで説明する簡単な態様においては、データは直列ビットで移動する。時間の単位Tは、スイッチS1を設定し、それから入力コントローラからライン208、スイッチS1、およびライン220を通って共有バッファにFLビットから成るフリットを移動させる、クロックティックの数で定義される。スイッチS2を設定し、それから共有バッファからライン228、スイッチS2、およびライン230を通って出力データバッファまでフリットを移動するようにTがクロックティックを行うように、システムは設計されている。メッセージセグメントサイクルは、N個の時間間隔、長さTのそれぞれから構成されていて、[0, T]、[T, 2・T]… [(N-1)・T, N・T]によって識別される。[-T, 0]などのTのための負の係数は、説明しているものの１つ前のサイクルの時間間隔を示すために使われる。メッセージセグメントMが入力コントローラICKにあり、そして時間間隔[0,T]の間においては、入力コントローラICKがスイッチS1を通ってデータの最初のフリットをK番目の共有バッファSBKに送信するようにS1がセッティングされている。時間間隔[T, 2・T]の間に、ICKがS1を通ってデータの2番目のフリットを共有バッファSBK+1に送信するように、S1は設定されている。このプロセスは、時間間隔[(N-1)・T, N・T]まで続き、その際にはICKが、メッセージセグメントMのN番目であり最後のフリットを共有バッファSBK+(N-1)に送信する。このメッセージセグメントサイクルの終わりに、共有バッファのそれぞれはメッセージセグメントMのFLビット(1つのフリット)を含んでいる。
【００１０】
ある位置から別の位置までのデータの動きは表１のタイミングチャートにまとめてある。このタイミングチャートは、次の段落の中で議論されるそれらの制御信号を含むある制御信号の動きを示す。表１のタイミングチャートは、この特許の幾つかの部分で説明するデータと制御信号の動きをまとめたものである。
【００１１】
メッセージセグメントMを共有バッファに送信することに加えて、入力コントローラICKは、制御情報も送信する。ICKが時間間隔[0,T]、[T,2・T],…,[(N-1)・T,N・T]のそれぞれにおいてデータビットを送信するが、入力コントローラICKが、時間間隔[-T, 0]（これは、前回のサイクルの最後の間隔[(N-1)・T, N・T]を示すために使用される。）中だけSBKに制御情報パケット(CIP)を送信する。パケットCIPはICKからライン264を通してSBKに移動する。この制御情報パケットは以下のようなメッセージセグメントMについての情報を含んでいる。
1) 共有バッファでのMのフリットの相対的な記憶場所
2) Mの目標出力（宛先）
3)Mの優先度
4) 固有のメッセージ識別子
5)メッセージフラグの終了
制御情報は、メモリバッファSBKの予約された特別な位置に置かれる。
【００１２】
入力コントローラは、共有バッファへのデータの書き込みを指示する。出力コントローラは、共有バッファからのデータの読取りを指示する。入力コントローラと出力コントローラとは、共有バッファに制御情報を送信し、共有バッファから制御情報を受け取る。共有バッファに完全なメッセージセグメントを書き込むときにかかる時間N・Tの値はサイクル時間、またはセグメント挿入サイクル時間、または単にサイクルと称される。メッセージセグメント書き込み期間はサイクル期間と称される。メッセージセグメント書き込み期間は、[0,T]、[T,2・T],…,[(N-1)・T,N・T]時間間隔に分割される。
【００１３】
入力コントローラから出力コントローラへ、或いは、出力コントローラから入力コントローラへ制御情報を渡すのに使用されるラインのセット（組）を「制御経路」と称し、下記のもので構成される。
1)個々の入力コントローラをその対応する共有バッファに接続するラインのセット
2)共有バッファシステムのなかで通信を行うラインのセット
3) 個々の出力コントローラをその対応する共有バッファに接続するラインのセット
重要なことに、制御経路は、スイッチS1またはS2のどちらかを通らないことに注意されたい。2つの制御経路を図２に示す。１つの制御経路は、ライン264、ライン260、およびライン270からなり、入力コントローラICKが制御情報出力コントローラOCJに送信することを可能にするものである。もう１つの制御経路は、ライン266、ライン262、およびライン274からなり、出力コントローラOCJが制御情報を入力コントローラICKに送信することを可能にするものである。連続の時間間隔I0,I1,…,IN-1のシーケンスがあり、Pが時間間隔IMの最初にSBL+Mにある（ここでMが0からN-1の範囲の整数である）場合、入力コントローラICLで、或いは出力コントローラOCLで生起するパケットPが、共有バッファシステムで「伝播する」或いは浸透すると言われる。すべての制御情報が共有バッファシステムに浸透する(percolate)。
【００１４】
時間間隔[T, 0]の間に、入力コントローラICKは、メッセージセグメントMと関連づけられた制御情報パケットCIPをライン264を通してSBKに送信する。時間間隔[0, T]の間に、この制御情報パケットがSBKからSBK+1に送信され、また、SBKからOCKに送信される。時間間隔[T, 2・T]の間に、この同じ制御情報パケットは、SBK+1からSBK+2に送信され、また、SBK+1からOCK+1に送信される。サイクルの最後に、各出力コントローラがメッセージＭに関連する制御情報パケットを読み終えるように、このプロセスはサイクルの最初から最後まで続けられる。制御情報パケットは、共有バッファから出力コントローラにライン270を通って移動する。出力コントローラOCJが、出力ポートJを目標とするメッセージセグメントパケットのために制御情報パケットを読み出すとき、出力コントローラは、その出力制御バッファOCBJにこの情報を記憶する。現在の実施態様において、出力コントローラOCJが、Ｊとは別個の出力ポートを目標とするメッセージについての情報を捨てる。このようにして、各出力コントローラOCJは、出力Jを目標とする全てのメッセージの優先度と位置とを追跡することができる。出力コントローラOCJは、共有バッファSBJから当該セグメントのために制御情報パケットCIPを抽出する時間間隔に基づき、どの入力ポートが入力され与えられたセグメントがあるかを教えることができる。従って、例えば、第３の時間間隔[2・T, 3・T]においてSBJから読み取ったCIPは、時間間隔[-T, 0]、即ちK=J-2において、ICJ-2によってSBJ-2に最初にロードされていたものである。よって、制御情報パケットCIPが入力ポート情報を含む必要がないという利点がある。
【００１５】
出力コントローラOCJは共有バッファに挿入された各セグメントについてCIPを検査する。出力ポートJを目標（宛先）とするメッセージセグメントが共有バッファ内にあり、OCJがそのCIPを検査した場合には、時間間隔[0, T]において、OCJがこれらのメッセージセグメントの１つをその出力データバッファODBJに転送するのを開始する。出力コントローラは、より高い優先度メッセージを下位の優先度メッセージよりも優先するように選択して、どのメッセージを読むかについて妥当な決定をすることができる。時間の[0, T]の間に、OCJは、共有バッファSBJからICKによって送られたメッセージのフリットFPをその出力データバッファODBJ650に導く。ICKはフリットFPを共有バッファSBK+Pに置き、よって、J=K+P、P=J-Kであることに注意されたい。しかしながら、出力コントローラOCJがKの値を計算することができる。その理由は、OCJが以前に、ICKによってSBKに挿入された制御パケットを読み込んでいたからである。従って、OCJは、Pの値を計算することができる。このようにして、パケットセグメントは、FP,FP+1,…,FN-1,F0,F1,…,FP-1の順序で読み出される。出力コントローラOCJの仕事の１つが、適正な順序でセグメントのフリット（サブセグメント）を配置することである。
【００１６】
時間間隔[T, 0]において、OCJは、ライン266を通じて特別メモリ位置使用可能パケットMLAを、MLAで指定されたアドレスが現在のセグメント読み取りサイクルにおいて利用可能になるであろうことを示すSBJに送信する。MLA内の情報は、その入力ポート番号とその相対的な記憶装置アドレスの双方を与えるような、共有バッファ内のフリットの物理的な位置の完全な記述である。例えば、ポート番号Kと相対アドレスSAは、セグメントのフリットが、フリットメモリバンクMKのセットにおける、相対アドレスSAにある共有バッファのセットに置かれたことを示す。時間間隔[(K-J)・T, (K-J+1)・T]において、ICKは、アドレスSAが他のメッセージのために使用可能であろうこと示す、SBJからこのMLAパケットを読み出す(MILAは上述したようにCIPと同様の方法で共有バッファシステムの中でバッファからバッファに移動される)。指定されたポートがKである場合は、ICKは位置SAをその空きメモリ位置のリストに加える、さもなければ、ICKはMLAを無視する。
【００１７】
オーバフロー条件が差し迫っている時に、入力コントローラは、メッセージパケットを捨てる責任がある。このような条件は、複数の入力コントローラが複数の優先度の高いメッセージパケットを１つの出力ポートJに送信し、その一方で、ICKが複数の低い優先度のメッセージパケットをJに送信した場合に起こり得る。オーバフロー条件を処理する様々なスキームが可能である。この話題に関するさらなる議論は、入力コントローラの部分に含まれている。
【００１８】
本発明は、共有バッファの正しい物理データ記憶場所にメッセージサブセグメントを導く新規なスキームを持つ。記憶装置アドレスは、別個のチャネルにより送られ、データをS1から適切な記憶装置位置に導く共有バッファ内部のスイッチがメッセージの到着とちょうど同時に設定されるように、そのメッセージの前に届く。同様に、共有バッファからスイッチS2に出力されるべきサブセグメントのアドレスは、適切なデータサブセグメントをS2内に導くために、ちょうどの時間に到着する。ヘッダ情報も制御情報もS1またはS2を通過しないのに対して、データの全てがこれらのスイッチを通過する。各セグメントがN個のサブセグメント（フリット）に分解され、各メッセージの前部に同一のヘッダを配置することに時間が浪費されるため、共有バッファにおける制御情報やアドレスの別個の動きが重要であり利点である。
【発明を実施するための最良の形態】
【００１９】
詳細な説明
システム200の動作を理解するためには、入力コントローラ、出力コントローラ、共有バッファ、スイッチS1,S2の詳細な知識を持つ必要がある。データ伝送パケットのフォーマットおよびコンテンツ（内容物）を理解する必要があり、同様に、制御情報運搬パケットのフォーマットおよびコンテンツを理解する必要もある、
【００２０】
パケットのフォーマットおよびレイアウトの説明
本システムに入ってくるデータパケットは、セグメントに分解され、さらにはフリット（サブセグメント）に分解される。これらのフリットはシステムの中を移動し、セグメントに再組み立てされ、順番に再組み立てされて出力メッセージパケットとなる。フリットは、スイッチS1とS2とを通って入力ポートから出力ポートに導かれる。メッセージパケットにくわえて、システム内で場所から場所に送られる多数の制御情報パケットがある。制御情報パケットはスイッチS1とS2を通じて移動しない。システム200に示したコンポーネントを説明する前に、データ伝送パケットおよび制御パケットフォーマットを説明する。
【００２１】
図４Ａは、ラインカードによって受信されたままであり、入力コントローラに渡されるメッセージパケットのフォーマットを示す。メッセージパケットはヘッダとペイロード（データ搬送部）から成る。図４Ａは、また、このメッセージがどのようにセグメントとフリットに分解されるのかを示す。メッセージ長が、関連するセグメントの数Lを決定する。メッセージパケット400は、セグメントS0,S1,S2,…,SLに分解される。一連のセグメントにおける各セグメントSxは、N個のフリット、F0,F1,…,FN-1にさらに分解される。それぞれのフリットは、FLビットを含み、個々のセグメントは、SLビット（ここで SL=N・FLである）を含んでいる。
【００２２】
図４Ｂ−４Ｇは、この実施態様で参照する様々な制御パケットの構造を示す。以下はこれらの制御パケットの中に含まれるフィールドの簡単な説明である。
BIT：  1ビットのフィールドであり、パケットの存在を示すために１がセットされる。BITをゼロに変更することはパケットを「消去する」ことを意味する。
MTA：  メッセージ目標アドレス(すなわち入力メッセージパケットの宛先出力ポート)。MTAは入力メッセージパケットヘッダの中の情報から引き出される。
SA：  共有バッファシステムの中のフリットのセットのための相対的なセグメントアドレス。
SP：  入力メッセージのヘッダの中のサービスの質(QOS)値に基づくセグメント優先度。
MPID：与えられたメッセージパケットの各セグメントを識別するために入力コントローラによって選ばれたメッセージパケットID。
EOM：メッセージ終結インジケータ。完全なメッセージパケットが処理されていることを示すためにいくつかの制御パケットに含められている1つのビットフィールド。制御パケットがメッセージパケットのために最後のセグメントと関連づけられない限り(そのケースでは、１に設定される)、EOMは0に設定される。
LP：  制御パケットに関連付けられたセグメントが送られた入力ポートの番号。
OP：  制御パケットを送っている出力ポートの番号。
NUMx：  優先度Xを持っているセグメントの数。
【００２３】
コンポーネントおよびタイミングの説明
本発明を完全に理解するたまには、以下のことを深く理解する必要がある。
1)スイッチS1とS2の動作
2)入力コントローラの動作
3) 出力コントローラの動作
4) 共有バッファの構造および動作
5)システムのタイミング
これらのトピックのそれぞれを別個のセクションで説明する。入力コントローラと出力コントローラは、特許8における入力コントローラおよび出力コントローラの機能に類似した機能を持っている。本発明および前述した特許８によって提供される相互接続コントローラは、他で見られないインテリジェンスレベルを可能にする。この制御は、与えられた出力ポートを目標とする全てのメッセージを同時に検査し、データをルーティングするためにこの情報を使用することによって達成される。共有バッファは、特許の中心となる新規な共用メモリとロジックを構成している。本発明の重要な視点は新規のタイミングスキームである。システムを駆動するグローバルなクロックがある。メッセージパケットはセグメントに分解され、セグメントはさらにフリットと呼ばれるサブセグメントに分解される。フリットはFLビットから成り、セグメントは、SLビット（ここで、SL=N・FL）から成る。ある位置から別の位置までフリットが移動するには、Tクロックティックの時間を必要としている。グローバルなクロックGC（図には示さず）は時間を０に初期化する。これは順次にステップの時間をＮ・Ｔ（セグメントを動かすの要する時間量）まで計り、ゼロにリセットする。本明細書では、あるイベントが時間tで起こることを述べる場合には、イベントが起こる時に、tがグローバルクロックの設定であることを意味する。
【００２４】
スイッチＳ１、Ｓ２
本発明の新規で重要な機能は、データに依存する戦略ではなく中央のクロックによってリセットされるデータスイッチの存在である。時間間隔[0, T]において、S1を通って移動するデータはICKからSBKに移動し、S2を通って移動するデータはSBKからODBKに移動するように、その時間間隔の間にはスイッチS1とS2とが設定される。時間間隔、[T, 2・T]においては、データはS1を通ってICKからSBKK+1に移動し、データはS2を通ってSBK+1からODBKに移動する。時間間隔[M・T, (M+1)・T]の間、データはS1を通過してICKからSBK+Mに、S2を通過してSBK+MからODBKに移動するように、このようなスイッチパターンは続けられる。
【００２５】
入力コントローラ
図２は、インテリジェント制御によるスイッチシステム200を示す。メッセージパケットはラインカードLCK 202に入力する。メッセージパケットは、イーサネット（登録商標）、インターネットプロトコル、ソネットフレーム、およびATMを含むさまざまなフォーマットの1つとすることができる。ラインカードLCKは、メッセージパレットMPを図４Ａの形式で入力コントローラICKに送る。パケットMPはヘッダとペイロード（運搬部）から成る。ヘッダは、メッセージ目標アドレス（MTA）がそこから抽出されるような、最終宛先を含む情報を含んでいる。このヘッダは、また、セグメント優先度SPがそこから引き出されるような、サービスの質(QOS)情報を含んでいる。図3は、入力コントローラ204のコンポーネントを示すものであり、入力コントローラ204は、入力コントローラロジックICL 310、入力データバッファIDB 320、使用可能な共有バッファ記憶場所のリストASL 330、および使用可能なメッセージパケットIDのリストAMID 340から成る。入力コントローラICKは相互接続ライン212を通してラインカード(line card)からのメッセージを受け取り、ライン208を通してメッセージフリットをS1に送信する。入力コントローラは、制御情報パケットをライン264を通じてSBKに送信し、ライン274を通じてSBKから記憶装置場所使用可能情報を受信する。ラインカードからのメッセージMPの到着に応答して、入力コントローラICKは以下のような幾つかのタスクを実行する。
【００２６】
・図４Ａに示すように、ICK(パケットヘッダ情報を含む)に到着するメッセージパケットMPのデータは、メッセージパケットセグメントに分解される。セグメントは、全て同じ長さSLである。セグメントの数はMPの長さに依存する。セグメントはすべて受信データから成り、スイッチシステム200によって挿入されるヘッダ情報を持っていない。代わりに、図４Ｂで示すように、システム200を通り抜けてメッセージをルーティング（経路決定）するために必要である情報は、別個の制御情報パケットCIPに配置される。
【００２７】
・図４Ａに示すようにセグメントＳは、サブセグメント(フリット)、F0,F1,…,FN-1に分解される、各サブセグメントはそれぞれ長さFLである。
【００２８】
・セグメントアドレスSAは、セグメントSのための共有バッファ記憶場所に応じて選択される。このアドレスは、ASLに格納されている使用可能な共有バッファメモリ位置のリストから選ばれる。
【００２９】
・セグメントSのための優先度SPが選ばれる。この優先度の値は、少なくとも一部は、パケットMPのサービスの質に基づく。この優先度値は、共有バッファのその他のデータを含む、その他のファクターに依存させることもできる。
【００３０】
・固有のメッセージパケット識別子MPIDは、AMIDバッファからメッセージMPのために選ばれる。このメッセージ識別子を使用して、出力コントローラはセグメントを再組み立てしてメッセージパケットに変換する。
【００３１】
・各CIPの最後のフィールドは、メッセージ終結インジケータEOMである。これは、１ビットのフィールドであり、ここに１がセットされているときは与えられたセグメントが最後のセグメントであることを示し、それ以外の場合にはゼロがセットされている。このビットは、固有のメッセージパケット識別子がフリー（空き）であり他のパケットに再使用できることを出力コントローラに知らせる。
【００３２】
・フィールドMTA、SA、SP、MPID、およびEOMを含んでいる制御情報パケットCIPが構成される。CIPパケットは図４Ｂに示してある。
【００３３】
・時間間隔[0, T]において、SのフリットF0は、ライン208、スイッチS1、ライン220を通ってICKからSBKに送信され、フリットメモリバンクMKのセグメントアドレスSAで共有バッファに格納される。時間間隔[T, 2T]においては、SのフリットF1は、MKのアドレスSAでSBK+1に格納するためにライン208、スイッチS1、ライン220を通って送信される。このプロセスは、時間間隔[(N-1)・T, N・T]において、SのフリットFN-1がMKのアドレスSAで格納するためにSBK+N-lに送信されるまで続く。共有バッファの添字は、負でない整数であり、Nより小さい。その理由は、加算はmod Nで行われるからである。
【００３４】
・時間間隔[-T, 0]において、図５に示すように、CIPはライン264上でSBKの位置CMI530に送信される。
【００３５】
・時間間隔[QT, (Q+1)・T]においては、ICKが、MLAパケットについてSBKの特別な位置CM2(532)を検査する。MLAは、入力ポートIP番号、セグメントアドレスSA、メッセージ終結フラグEOMを含む。MLAパケットがCM2(すなわちBIT=1)に存在し、IPがKである場合、SAの値はMKにある。そのような値が存在する場合は、ICKはSAの値を、そのASLに加え、最初のビット(BIT)を０に変更することによって、MLAを「消去」する。さらに、IPがKである場合には、ICKは、EOMフィールドが１であるかどうかをチェックする。もしそうなら、別のメッセージパケットのためにMPIDの再使用を許すように、ICKはAMIDバッファを変更する。そのようなSA値が存在しない、或いは、その値がKと別個のLを持つバッファML中にある場合は、ICKはそのASLを修正せず、また、CM2の修正もしない。
【００３６】
・時間間隔[-T, 0]において、ICKは、SA（CIPのサブフィールドとしての）を、ライン264上でSBKに送信し、それは、時間間隔[0, T]においてSBKのロジックによって使用されるべきものであり、F0をその適切な記憶場所にルーティングするものである。時間間隔[-T, 0]は、前回のサイクルの中の最後の時間間隔を示すために使われる。従って、F0をSBKに送信する直前のクロックTにおいては、コントローラICKがF0のために記憶装置位置を準備する。
【００３７】
・どのようなスイッチシステムにおいても、データオーバフロー状況が起こるかもしれず、メッセージパケットが強制的に処分される。この発明の簡単な態様において、処分するためにメッセージパケットを選択する2つの方法を使用することができる。
1)数MAXを設定することができる。各入力コントローラと各出力コントローラとは、MAXサイクルよりも長くシステム内に残っているメッセージセグメントを捨てる。
2)入力コントローラICKが、そのラインカードからメッセージパケットを受け取り、その入力データバッファIDBKがほとんど満杯である場合、ICKは、入力メッセージパケットの優先度と、IDBKにおける処理されていないエントリのセットにおける最下位の優先度を持つものとを比較する。ICKは、それから、最も低い優先度を持つパケットを捨てるか、或いは、入ってくるパケット、即ちその入力データバッファにあるものを捨てる。未処理のエントリは、入力コントローラによって受け入れられているけれどもまだ共有バッファシステムにそのセグメントのいずれも送信されていないものであることに注意されたい。
【００３８】
・最初の追加の制御の実施態様において、出力ポートJでの輻輳のため、オーバフロー条件が入力コントローラICKで生じる場合には、ICKは、Jを目標とするそのメッセージパケットの優先度を増大させることによってこの状況を救うことができる。ICKは、Jのメッセージ目標アドレスMTA、変更されるパケットのメッセージパケットIDであるMPID、および当該パケットのための新しい優先度SPを指定する、変更優先度パケットCPK（図４Ｆに示す）を作成する。まだ送信されていないパケットのいずれかのセグメントのためにICKは優先度を更新し、制御経路（図に示さず）を介してCPKを出力コントローラに送信する。CPKは位置CM3を使って、共有バッファシステムに浸透する。変更優先度パケットを使う実施態様においては、ICKからSBKへの、SBJからOCJへの、そして共有バッファ間の追加ラインがある。各出力コントローラはCPKを試験し、OCJはCPKがポートJに向けられているものであることに注意するが、その一方で、他の出力コントローラは、そのパケットを無視するであろう。OCJは、その出力コントローラバッファのおける指定されたメッセージパケットのセグメントの全ての優先度を変更する。
【００３９】
・第２の追加の制御の実施態様では、入力コントローラICKは、オーバフローを避けるために部分的にしか処理されていないメッセージパケットを捨てることができる。これを行うため、ICKは、廃棄メッセージパケットDMK（図４Ｅを参照されたい。）を制御経路(図に示さず)経由で適切な出力コントローラに送信し、このパケットのセグメントがIDBKにおいて残存していても捨てる。位置CM4を使って、DMKパケットは、共有バッファシステムに浸透する。廃棄メッセージパケットを使っている態様においては、 ICKからSBKに、SBJからOCJに、および共有バッファの間に追加のラインがある。各出力コントローラOCJは、DMKパケットを読み、MTAがJではないならばそれを無視する。MTAがJである場合は、OCJは、供給されたMPIDおよび入力ポートKに関連付けられている全てのセグメントを削除し、要求されたメッセージパケットの削除を終える。
【００４０】
・さらに、入力コントローラによって実行される誤り検出、およびエラー修正機能を設けることもできる。
【００４１】
・また、入力コントローラは、その対応するラインカード(または、当該ラインカードを通過しない別個のライン)を通じて、情報を上流の装置の出力ポートに送信することができる。この情報は入力ポートのステータス（状態）を示す。上流のデバイスは、スイッチ200にデータのフローを調節するためにこの情報を使うことができる。別個のスイッチの間にある制御情報の経路は図２には示してない。この情報は、システム全体を通って上流に分散させることができる。
【００４２】
図６は、出力コントローラの主要なコンポーネントを示す。出力コントローラは、論理演算装置（ロジックユニット）OCL610、出力データバッファODB650、および出力制御パケット(OCP)を保持する出力制御バッファOCB620を含んでいる。OCPパケットは、CIPパケットの中で情報を使って、作られる。論理演算装置はOCPパケットの中の情報を入力として取得し、この情報に基づいて、共有バッファ222から出力データバッファ650への、および、出力データバッファからのラインカード202へのトラフィックの流れを管理する。ライン270はCIPパケットを配送し、ライン266はMLAパケットを送って共有バッファのあるメモリ位置がフリー（空き）であることを入力コントローラに通知する。前述した特許8のように、出力コントローラは、所定の出力ポート（この場合、出力データバッファおよびラインカードを含む）に接続（関連付け）されている。出力コントローラは、その接続されている出力ポートを目標とする全てのトラフィックを検査し、その出力ポートに接続されたラインカードへのデータの流入をコントロールする。同じ出力ポートを目標とする異なる入力ポートで2つ以上のメッセージの比較に基づいたメッセージのルーティングは、特許8だけでなく本発明の重要な機能である。これを可能にするためには、出力コントローラOCJは、出力ポートJを目標（宛先）にするトラヒックのすべてについて知らされる必要がある。出力コントローラに必要な情報は、制御情報パケットCIPの中に含まれている。ラインカードLCJを目標とするメッセージパケットMPが、システム外からラインカードLCKに届いた場合には、入力コントローラICKはメッセージを分割し、各メッセージセグメントに対応して、入力コントローラICKは、制御情報パケットCIPを作成する。各サイクルの最後の時間間隔の間には、ICKはCIPをSBKのCM1区画に配置する。入力コントローラICKが、形式[(N-1)・T, N・T]（イベントがその使用の前のサイクルにおける最後の時間間隔で起こったイベントであることを強調するために、[-T, 0]と呼ぶこともある。）における各サイクルの時間間隔でSBKの位置CM1に書き込む。出力コントローラは、入力コントローラが共有バッファのCM1セクションに配置した情報に基づき決定する。
【００４３】
出力コントローラOCJは以下を含む幾つかの機能を実行する。
・時間間隔[T, 2・T]の間において、出力コントローラOCJは、SBJの位置CM1から、制御情報パケットCIP（入力コントローラICJ-1により挿入される）を読む。時間間隔[2・T,  3・T]の間では、出力コントローラOCJは、SBJから、CIPパケット（入力コントローラICJ-2により挿入される）を読む。このプロセスは、時間間隔[(N-1)・T, N・T]において、出力コントローラOCJが、SBJの位置CM1から、ICJ-(N-1)により挿入されたCIPパケットを読むように続けられる。SBJ-(N-1)はSBJ+1であることに注意されたい。
【００４４】
・OCJが制御情報パケットCIPを読み、CIPのMTAフィールドがJであるたびに、OCJはCIPからの情報を図4Eに示したタイプの出力制御パケットOCPに置く。そのとき、出力コントローラはバッファOCB 620の中にこのOCPパケットを格納し、最初のビット(トラフィックビット)を0に変更することによって、CIPパケットを「消去する」。最も簡単な実施態様において、OCJは、メッセージの目標アドレスがJでないものを持つ制御情報パケットを無視する。
【００４５】
・時間（N-3）・Tにおいて、いずれかの制御情報パケットがOCJのOCBバッファにある場合、その後の時間間隔[(N-2)・T, (N-1)・T]において、出力コントローラOCJは、OCPパケットのうちのいずれか１つOCP*を選び出し、OCP*に関連付けられているイベント（事象）のシーケンスを始動させる。OCP*を選択したことの結果として、OCP*に関連付けられているセグメントが共有バッファからODBJに転送される。最も簡単な態様では、OCP*は、ODBJに送信されるために最も高い優先度のセグメントと関連づけられる。出力コントローラは、与えられたメッセージのセグメントを順番に送信させる。２つのメッセージが同じ最も高い優先度を持つ場合には、出力コントローラは、セグメントが共有バッファに入ってきた時間に基づきメッセージを選択することができる。
【００４６】
・時間間隔[](N-1)・T, N・T]において、OCJは、OCP*のSAフィールドを含むMLAパケットを作成し、ライン266を通じてそれをSBJのCM2フィールドに送る。法演算(modular arithmetic)を使用するため、[(N-1)・T, N・T]＝[-T, 0]であることに注意されたい。この操作の１つの目的は、位置SAにあるセグメントを次回のサイクルでODBJに送信させることである。この同じ時間間隔の間に、1CJが、SAフィールドを含むCIPを作成し、SBJのCM1フィールドにそれを送信することを思い出されたい。
【００４７】
・時間間隔[T, 0]において、OCJは、MLAパケット（図4Fで示す）中のKとSAの値をSBJのCM2フィールドに送信する（ここで、Kは、メッセージが処理されている入力コントローラの添字である）。この操作の目的は、ICKが別のメッセージセグメントのためにそのASLにおいてこのスペースを解放することを可能にすることである。
【００４８】
・この発明のいくつかの態様において、出力コントローラOCJはステータス情報を入力コントローラのすべてに送信する。OCJが入力コントローラに送信することができる４つのタイプのステータス情報がある。この情報は、出力ポートステータス（状態）パケットOPSJ（図４Ｇを参照されたい）の中で送信される。最初の情報のタイプは、番号NUM0,NUM1,…,NUML（ここでNUMXは、優先度Xを持つOCBJのメッセージセグメントの番号である）のシーケンスである。出力コントローラが送ることができる情報の第２のタイプは、OCJを目標とする共有バッファの中の様々な優先度のメッセージセグメントの番号についての情報（図４Ｇには示さず）を含むことができる。この2番目のタイプの情報は、OPSJパケットに含められているか、別個の制御パケットの中で送信することができる。出力コントローラが送ることができる3番目のタイプの情報は、ダウンストリーム入力ポートまたはダウンストリーム入力ポートコントローラ（通常、OCJと関連づけられた出力ポートからデータを受け取るもの）から受け取った情報である。3番目のタイプの情報は、ダウンストリーム（下流）バッファまたはネットワークシステム管理に有益なものなどのような他の情報のステータスを含むことができる。3番目のタイプの情報は、タイプ1またはタイプ2の情報と共に送信されることができ、或いは、別個のパケットで送信することもできる。出力コントローラが送ることができる4番目のタイプの情報は、最近出力ポートによって受け取られたメッセージの優先度と番号を一覧にしたものである。前と同じように、この情報はタイプ1、2、または3の情報と共に制御パケットの中で送信することができ、或いは、それは別個の制御パケットの中に入れて送信することもできる。4番目のタイプの情報はダウンストリーム入力ポートの予想される使用状態を示し、ダウンストリーム（下流）入力ポートがステータス情報をOCJに返信しないか、さもなければそれが適時にこの情報を送り返してこない時に有益である。入力コントローラは、各出力ポートがどれほど使用中であるかを教えるためにこの情報を使い、どのセグメントを送るべきかを選択するのにこの知識を使うことができる。出力ポートステータスパケットOPSJは、MLAパケットと同じ方法で制御経路（図には示さず）経由で送られる。タイプ2、3、または4の情報のための他の考えられる制御パケットは、追加のバッファ位置と制御ラインを必要とする場合もある（これらも図には示さず）。OPSJとその他の考えられる出力ポートステータスパケットは、図には示さない追加のラインと記憶装置バッファ位置CM5とを使って共有バッファシステムに浸透、即ち行き渡る。従って、各入力コントローラは、N個の時間間隔の中でOPSJまたは他の出力ポートパケットを読む機会を持つこととなる。
【００４９】
代替の実施態様に態様において、出力コントローラは、そのバッファ内のパケットセグメントを捨てる機能を持つ。この場合に、この操作を入力コントローラに知らせるために、出力コントローラは追加の制御パケットを生成する。
【００５０】
この情報なしで可能でない管理水準を達成するために、出力コントローラが入力コントローラに返信する情報によって、入力コントローラは、この情報なしではなし得ないような制御のレベルの実現を可能にする。特に、離れた装置であるダウンストリーム（下流）の入力ポートからのタイプ３の情報は、それ自体が、さらに下流にある別の離れた装置から受信した情報に基づかせることができる。このようにして、情報は、スイッチからスイッチへと上流に向かって移動することができる。この情報は、上流に分散させることができ、そして、これを使って、新規かつ斬新な制御のレベルをシステム全体にもたらすことができる。
【００５１】
共有バッファ
ラインカードは、データパケットの入力コントローラに送信する。入力コントローラは、スイッチS1を通じてデータを共有バッファに送信する。共有バッファは、スイッチS2を通じてデータを出力データバッファに送信する。図５は、共有バッファ222の詳細なブロック図である。N個の入力ポートを持つシステムは、N個の共有バッファを持つ。N個の共有バッファのそれぞれは、N個のフリットメモリバンクであるM0,M1,…,MN-1、２つの制御記憶装置エリアであるCM1(530)およびCM2(532)、ロジックユニットSBL520などを含む多くのコンポーネントを含む。メモリバンクMKは、入力ポートKを通ってシステム内に入ってきたデータのために予約されている。MKにあるデータは、どのような出力ポートをも目標（宛先）とすることができる。いくつかの実施態様では、N個のメモリバンクは等しいサイズを持つ。他の態様においては、違うメモリ容量を違う入力ポートに割り当てるようなメモリマネージャを設ける。この機能は、幾つかの入力ポートがデータラインと接続されない時、または、種々のデータラインが同じでないデータ転送速度でデータを受け取るときに有益である。個々のフリットメモリバンクMKの関連づけは、使用中でなく、新たなデータの格納に利用可能な、MKのアドレスのリストに相当する。この使用可能なアドレスのリストは、入力コントローラICKのASL330記憶装置に記憶する。記憶装置の場所CM1(530)は、１つの入力コントローラICKによって挿入される1つのCIPパケットを保持し、これは全ての出力コントローラによって読み出される。記憶装置の位置CM2 532は、一連のフリットメモリバンクM0,M1,…,MN-1(510)のうちのいずれか1つにおいて空きメモリ位置を示す、単一の空きメモリパケットMLAを保持する。CM2は、入力コントローラICKから生起するデータ項目を読み出すような、出力コントローラOCJから１つのデータ項目を受け取る。そして、OCJがMKの位置NMから項目を読む時に、OCJは、アドレスMPをCM2に挿入することによって、位置MPが新たなデータを保持するために空き（フリー）であることを示す。CM2は入力コントローラのすべてによって読まれて、1つの入力コントローラICKによって使われる。共有バッファSBKはロジックSBL520によって支配され、このロジックはライン260と262とを通じてSBK-1から制御情報を受け取り、ライン260と262とを通じてSBK+1に制御情報を送信する。このロジック（論理演算）装置は、ライン220を通してSBKの中に入るデータの格納をコントロールし、また、ライン228から外に出るデータの送信をコントロールする。論理演算装置SBL 520は、共有バッファデータ記憶領域の正しい位置SAIへのスイッチS1からのセグメントの流入をコントロールする。論理演算装置SBLは、共有バッファの中の正しい記憶場所SAOから出力データバッファまでのデータのフローをコントロールする。これらの正しい記憶場所はSAパケットとして共有バッファに渡される。
【００５２】
データと制御情報のタイミングは共有バッファの正しい操作には重要なものである。ライン220を通って 共有バッファSBLに到達するデータのフリットは、ライン260に到着するMLAパケットのSAフィールドによって決定される位置に格納される。時間間隔[-T, 0]において、次の時間０（セグメント送信サイクルの開始）のフリットF0の到着開始をスケジュールする入力コントローラICKは、ライン260上で到着するで記憶されるセグメントアドレスSAを含むCIPパケットをライン264を通じてSBKに送信する。このCIPパケットは位置CM1に格納される。時間0に、共有バッファ内部メモリスイッチは、次の到着データ（時間間隔[0, T]に到着しているフリットF0）をSBKのメモリバンクMKの記憶場所SAに次に到着するデータを置くために位置決めされる。時間間隔[0, T]において、F0がメモリバンクMKにおける記憶場所SAに到着している間に、SBKがSAをSBK+1にライン260を通じて送信する。2番目のフリットF1が、メモリバンクMKのアドレスSAにおいて記憶されるようにF1をならしめるSBK+1に到着する時には、このアドレスは適所にある。このプロセスは、メッセージの次のフリットを記憶する適切な時間にライン260上の共有バッファに到達するアドレスの適切な格納を続ける。セグメント全体を格納する場合は、新たなアドレスがライン264上の共有バッファに到達する。このようにして、最初のフリットのための記憶装置アドレスはライン264上に到着し、残存フリットのための記憶装置アドレスはライン260上で到着する。
【００５３】
図7は、共有バッファ全体にCIPパケットを浸透させる1つの方法の説明である。この実施態様において、CM1はシフトレジスタである。時間[T,  0]の間に、スイッチ704は閉まり、スイッチ706は開いているため、それゆえに、CIPパケットが入力コントローラからシフトレジスタCM1に流れる。全てのその他のセグメントを送信する時間間隔では、スイッチ704は開きスイッチ706は閉じる。すべての時間間隔の間に、CIPパケットは出力コントローラに移動する。このようにして、制御パケットは共有バッファ中を通って長いシフトシフトレジスタに浸透する。いくつかの態様において、図7で示すようにバスは広いものであるが、他の態様では、複数のシフトレジスタはデータを運び、ライン264と270はバスである。
【００５４】
時間間隔[-2・T, -T]の間に、出力コントローラOCJは、セグメント送信間隔[0, N・T]においてODBJに送信されるべき、共有バッファにあるセグメントがどれであるかを決定する。時間間隔[-T, 0]において、OBJは、選択したセグメントのアドレスSAを含むMLAパケットをライン266を通じて共有バッファSBJに送る。従って、時間0においては、このアドレスはSBJの位置CM2という適切な場所にある。時間間隔[0, T]の間において、SBJは、位置SAにあるフリットをODBJに送信する。また、この同じ時間間隔の間に、SBJは、ライン262を通じてMLAをSBJ+1送信する 。従って、時間Tには、アドレスSAがSBJ+1の場所CM2にあり、それゆえに、SBJ+1は、位置SAにあるフリットをライン228を通じてODBJに送信することができるようになる。セグメント全体が成功裏に共有バッファから出力データバッファODBJに送信されるまで、このプロセスが続く。
【００５５】
システム制御
入力コントローラは、ラインカードから共用データバッファへのデータの移動を管理する。出力コントローラは、共用データバッファからラインカードへのデータの移動を管理する。本システムの管理は、入力コントローラと出力コントローラとに接続された論理装置によって制御される。このロジックを効果的に機能させるために、制御情報を入力コントローラと出力コントローラの間でやりとりさせることが必要である。最も基本的なシステムでは、入力コントローラはセグメントを共用データスペースに置く。このデータに関して、入力コントローラは、制御情報パケットを出力コントローラに送信し、セグメントの位置とセグメントの優先度を出力コントローラに知らせる。この情報は、共有バッファ位置CM1に位置する制御パケットCIPに含まれている。出力コントローラは、セグメントの優先度に基づきそのコントローラを目標とするすべてのセグメントを認識することができ、出力コントローラは、共有バッファから最も高い優先度を持つパケットを取り出し、セグメントからメッセージパケットを再組み立てし、本システムからの出力としてラインカードにメッセージパケットを送信する。出力コントローラが共有バッファスペースからデータを取り出して削除したとき、共有バッファのスペースが開放されたことを入力コントローラに知らせなければならない。これは、共有バッファ位置CM2に格納されている制御パケットMLAを使って行われる。
【００５６】
幾つかのバッファがデータを同じ出力ポートに送信した場合に、本システムは輻輳する。輻輳を管理する方法は多数存在する。
【００５７】
最初の方法（方法１）では、入力コントローラの共有バッファスペースがいっぱいに(またはほとんどいっぱい)なり、入力コントローラの入力データもいっぱい(または、ほとんど、いっぱい)になり、入力コントローラが新しいデータを受け取る場合、入力コントローラは新しいデータNDを処分するか、その入力データバッファの中にある古いデータODをＮＤに置換することができる。ODが完全なメッセージを表しており、NDの優先度がODのものより高く、以前にODによって占められたスペースにNDが納まる場合に、この置換動作がおこなわれる。この方法では、古いデータが共有バッファには決して置かれないので、方法1の動作のもとでは制御情報を渡す必要が全くない。
【００５８】
2番目の方法（方法２）では、共有バッファスペースに置かれたメッセージパケットは、一定時間の間はスペースを占めることを許される。その時間の終わりに、メッセージパケットのすべてのセグメントは処分される。処分されたメッセージパケットは、入力コントローラバッファ内の幾つかのセグメント、出力コントローラバッファ内の幾つかのセグメント、および共有バッファ内の幾つかのセグメントを持つかもしれない。古いメッセージが処分される時に、入力コントローラと出力コントローラの間でコントロール情報を渡す必要は全くない。これは、入力コントローラと出力コントローラの両方が彼ら自身のバッファの中と共有バッファの中のデータ（そしてそのデータの生成時間）のすべてを認識しているためである。
【００５９】
オプションの3番目の方法（方法3）では、入力コントローラの共有バッファスペースがいっぱいに（または、ほとんどいっぱい）になり、また、入力コントローラの入力データバッファもいっぱいに（または、ほとんどいっぱい）なり、入力コントローラが新しいデータを受け取る場合に、入力コントローラは、共有バッファにすでにあるメッセージパケットMを処分することによって共有バッファデータスペースを解放できる。この動作が行われる場合には時に、M（入力コントローラバッファ、共用データバッファ、および出力コントローラデータバッファ内の）のすべてのセグメントは処分されなければならない。入力コントローラがSAをメッセージパケットの各セグメントに割り振り、共有バッファから削除されたセグメントのMLAパケットによって知らされるため、入力コントローラは、 メッセージパケットの全てのセグメントが位置する場所（図示していないメモリ位置）を追跡することができる。データが方法3を使って処分される時に、入力コントローラはその動作を出力コントローラに知らせなければならない。これは、DM制御パケットを出力コントローラに送信することによって達成される。このパケットは、位置CM4（図には示さず）の共有バッファに格納される。
【００６０】
オプションである４番目の方法では、入力コントローラバッファがいっぱいになり、入力コントローラの共有バッファスペースがいっぱいになるのにしたがい、入力コントローラは共有バッファスペース内にあるメッセージパケットの優先度を上げることができる。これを行うために、入力コントローラは、パケットの新しい優先度を目標とする（宛先の）出力コントローラに知らせなければならない。この情報は、共有バッファ位置CM3（図には示さず）に格納されるパケットCPに含まれている。
【００６１】
出力コントローラは、方法3と4を適用する時に適切な論理的決定にすることについて入力コントローラを補助することができる。これは、各出力コントローラが与えられた出力コントローラに目標とする、共有バッファスペース内のメッセージパケット（およびそれらの優先度）のすべてを入力コントローラに知らせることによって、達成される。この情報は制御パケットOPSで渡され、共有バッファスペース位置CM5（図には示さず）に置かれる。
【００６２】
システムタイミング
前述したように、タイミングは、システムグローバルクロック（図には示さず）によって制御される。基本のクロックタイムユニットはティックと称するものであり、Ｔを使ってある場所からある場所にデータを送るために必要なティックの数を表す。ある場所からある場所とは、例えば、入力コントローラから、ライン208、スイッチS1、およびライン220を通じて共有バッファへ、或いは、共有バッファｆからライン228、スイッチS2、およびライン230を通じて出力コントローラへなどである。セグメントはN個のフリットからなるため、セグメントがNフリットにより構成されているので、ある場所から他の場所にセグメントを動かすのにはN・Tクロックティックかかるというルールに従う。この点を考慮して、はじめにそれ自体をゼロにして時間N・Tまで逐次１ティックずつ進みN・Tの長さの時間サイクル繰り返し、またゼロにリセットされるように、グローバルクロックGCは設計されている。クロックサイクルは、N・T時間間隔[0, T]、[T, 2・T],…,[(N-1)T, N・T]に分割される。
【００６３】
システムのタイミングは、1つのクロックサイクル[0, N・T]の間のある位置からある位置へのデータのフローによって説明される。
１つのクロックサイクルの間に発生する２つのメインのプロセスがある。
1)メッセージセグメント１つまはたは複数の入力コントローラから共有バッファのセットに送られるセグメント挿入プロセス
2)１つまたは複数の出力コントローラが、それらを組み立ててメッセージセグメントに変換するために、共有バッファのセット（組）からそれらのそれぞれの出力バッファにフリットを送信するよう指示するセグメント取得プロセス
これらの２つのプロセスは同時に起こるが、明瞭化のための別々に説明する。各時間間隔のデータフローの詳細を示す表１を参照されたい。
【００６４】
セグメント挿入プロセス
各クロックの時間間隔[-2・T, -T]の間において、各入力コントローラは、その次に送信されるべきメッセージセグメントの選択を完了させる。前回の時間間隔[-T, 0]において、次のサイクルで送信する準備ができているメッセージセグメントを持つ各入力コントローラICKは、当該セグメントのための制御情報パケットCIPKをライン264を通じて共有バッファSBKに送信し、ここでそれはCM1に格納される。CIPKはサブフィールドとしてセグメントアドレスSAKを含むことに注意されたい。従って、次のクロックサイクルの時間間隔[0, T]にそれが到着したときに、SBKは、データの第１のフリットF0を格納するためのアドレスを持つ。
【００６５】
時間間隔[0,  T]において、次の3つのイベントが起こる。
1)このサイクル時間においてメッセージセグメントを送信する各入力コントローラICKが、ライン208、スイッチS1、ライン220を経由して第１のフリットF0をMKのアドレスSAKに格納するために共有バッファSBKに送信する。
2)制御情報パケットCIPKは、SBKからライン260を経由してSBK+1のCM1フィールドに移動される。従って、SAKはSBK+1の次のフリットをロードするための位置にある。
3)ICKはメモリ位置使用可能パケットMLAについてライン274を経由してSBKのCM2フィールドを検査する。セグメント取得プロセスでも説明するが、ICKが出力ポートKにデータ送信しなかったため、時間間隔[0, T]においてSBKで見つかったMLAは、時間間隔[-T,  0]の間にOCKによってそこに置かれたものである。
【００６６】
第２の時間間隔[T, 2・T]では、以下の同様のイベントが起こる。
1)メッセージセグメントを処理する各入力コントローラICKが第２のフリットF1を、ライン208、スイッチS1、ライン220を経由してSBK+1に送信する。F1は、SBK+1のMKのアドレスSAKに格納される。
2)制御パケットCIPK（SAKを含んでいる）は、SBK+1からライン260を通じてSBK+2のCM1フィールドに移動される。
3)ICKはメモリ位置使用可能パケットMLAについてライン274を経由してSBKのCM2フィールドを検査する。
ICKがMLAの入力ポート値IPがKであることを見つけた場合は、MLAにあるSAの値はICKの利用可能記憶装置位置バッファASLに属する。その後、ICKは将来の使用のために当該場所を開放し、第１のビット（トラフィックビット）をゼロに変更することによってMLAパケットを「消去」する。IPがKでない場合は、ICKはMLAを無視する。セグメント取得処理中の間、データは出力コントローラICJによってCM2に置かれるが、このことは後で説明する。第２の時間間隔ではSBKで見つかったMLAは、時間間隔[-T, 0]の間に出力コントローラK-1によって共有バッファSBK-1に最初は送られる。従って、表１はMLAK-1を使ってこの値を表している。
【００６７】
時間間隔[2・T, 3・T]から[(N-2)・T, (N-1)・T]までの間、第２の時間間隔で開始したプロセスが続く。従って、時間間隔N-1では下記のことが起こる。
1)ICKはフリットFN-2を208とS1とを経由してSBK+(N-2)に送信する。
2) SBK+(N-2)は、CIPKを260を経由してSBK+(N-1)に送信する。SBK+(N-1)はSBK-1であり、従ってCIPKが共有バッファの各々へ送信されることに注意されたい。
3)ICKは、MLAパケットがそのASLの値を開放するかについて274を経由してSBKを検査する。ここで、SBKは、ICK-(N-2)によって時間間隔[-T, 0]の間にSBK-(N-2)に置かれた値MLAK-(N-2)を含んでいる。
[(N-2)・T, (N-1)・T]の形式の各サイクル時間間隔にだけ次の追加プロセスが起こる。ICKが、次のクロックサイクルで処理する新たなメッセージセグメントの決定を完了し、そのASLからアドレスSAK*を選び、このセグメントのため制御情報パケットCIPK*を作る。
【００６８】
最後の時間間隔[(N-1)・T, N・T]では、以下のことが起こる。
1)ICKがメッセージセグメントの最後のフリットFN-1を208、S1、220を経由してSBK+(N-1)に送信する。
2)ICKが、次のサイクルの準備のためにSAK*を浸透させるSBKに、264を経由してCIPK*を送信する。
3)ICKが、そのASLに置かれているアドレスを開放するMLAパケットについて274を経由してSBKを検査する。
ここでSBKは値MLAK-(N-1)を含んでいる。この時点で、ICKは、JがKでない場合には、前回の最後の時間間隔の間に、OCJによってSBJに置かれた各MLAJを検査した後となっている。
【００６９】
セグメント取得（取り出し）プロセス
共有バッファからセグメントを取り出し、再組み立てのためにそれらを出力コントローラに送り、ラインカードに送り出すプロセスは、挿入プロセスと似ているものであり、それと同時に動作するものである。それは、前回のサイクルの時間間隔[-2・T, -T]に始まる。次のサイクルで処理するデータを持っている各出力コントローラOCJは、その出力制御バッファOCBからエントリの選択を完了し、それのためにメモリ位置利用可能パケットMLAJを構築する。MLAJは、セグメントを送った入力ポートIPの番号とセグメントのフリットが共有バッファSBのセットにおいて格納されている相対アドレスSAJの両方を含んでいる。
【００７０】
時間間隔[-T, 0]では、次のサイクルでデータを処理する各出力コントローラOCJが、そのMLAJパケットをライン266を経由してSBJのCM2フィールドに浸透させる。
【００７１】
時間間隔[0, T]では、以下の３つのイベントが起こる。
1)共有バッファSBJは、アドレスSAJ（MLAJの一部としてCM2に浸透されたものである）を使ってそのバッファからフリットFPを取り出し、FPをライン228、スイッチS2、ライン230を経由して出力データバッファODBJに送る。
2)SBJは、メモリ位置使用可能パケットMLAJ（SAJを含む）をライン266を経由してSBJ+1に送り、CM2フィールドに格納される。
3)出力コントローラOCJは、制御情報パケットCIPKについてライン270を経由してSBJのCM1フィールドを検査する。
セグメント挿入プロセスは、どのようにして制御情報パケットCIPKがICKによって時間間隔[-T, 0]に共有バッファSBKに挿入され、連続する時間間隔において残りの共有バッファSBK+1,SBK+2,…,SBN-1を通って順次に回っていくかを説明するものであることに注意されたい。結局、時間[0, T]のCM1のCIPは、そこにICJによって挿入されたものであり、ICJがデータを出力ポートJにデータを送信していないため無視されるものである。
【００７２】
時間間隔[T, 2・T]では、次の同様のイベントが起こる。
1)SBJ+1が、前回の時間間隔でMLAJの一部として渡されたSAJの値を使ってフリットFP+1を取り出し、それをライン228、スイッチS2、ライン230を経由してODBJに送る。
2)SBJは、MLAJをライン268を経由してSBJ+1に送る。
3)OCJは、新たなセグメントが出力ポートJに送信されているかどうかを調べるために制御情報パケットCIPJ-1（[-T, 0]において入力コントローラICJ-1によって挿入されたもの）についてライン270を経由してSBJのCM1フィールドを検査する。
そうである場合には、OCJがCIPJ-1にある情報から出力制御パケットOCPを構築し、それをそのODBの格納する。OCJはパケットの第１のビット（トラフィックビット）をゼロに変えることによってCIPJ-1を「消去」する。CIPJ-1のメッセージ目標アドレスMTAがJでなかった場合は、OCJは当該パケットを無視する。
【００７３】
第２の時間間隔で開始されたプロセスは、(N-1)番目の時間間隔まで続く。従って、[(N-2)・T, (N-1)・T]（これは次のサイクルの間隔[-2・T, -T]である）では次のことが起こる。
1)SBJ+(n-2)は、フリットFP+(N-2)を取り出し、相対アドレスSAJに格納するためにそれをライン228、スイッチS2、ライン230を経由してODBJに送信する。
2)SBJ+(N-2)は、MLJAをライン268を経由してSBJ+(N-1)に送信し、共有バッファの全体にわたるMLAJの回路が完成する。
3)OCJは、CIPJ-(N-2)についてライン270を経由してSBJのCM1フィールドを検査し、新たなセグメントが出力ポートJに送信されているのかどうかを確かめる。
これは、次のサイクルに対して時間間隔[-2,・T, -T]であるため、形式[(N-2)・T, (N-1)・T]を持つ各間隔だけで発生する次の追加のプロセスがある。そのプロセスとは、OCJが次の時間サイクルで取り出されるべきセグメントの選択を完了させ、このセグメントのためにMLAJ*パケットを構築することである。
【００７４】
サイクルの最後の時間間隔[(N-1)・T, N・T]（次のサイクルの間隔[-T, 0]である）の間では、次のことが起こる。
1)SBJ+(N-1)は、セグメントの最後のフリットFN-1を取り出し、それをライン228、スイッチS2、ライン230を経由して再組み立てのためODBJに送る。
2)OCJは、MLAJ*をライン266を経由してODBJに事前ロードする。
4)OCJは、どれがICJ+1によって送信されたかをCIPJ-(N-1)についてライン270を経由してSBJを検査する。
従って、このサイクルの間に、OCJが、時間間隔[0, T]に新たなセグメントを入力した入力コントローラのセットによって送られた全てのCIPが試験される。
【００７５】
バンヤン(Banyan)スイッチ実施態様
他の実施態様では、スイッチS1とS2とは、バンヤン(banyan)スイッチである。図８Ａに8×8のバンヤンスイッチを示す。バンヤンスイッチを使った場合は、それらを効果的にスイッチする簡便なアルゴリズムがある。時間間隔[0, T]では、バンヤンスイッチは図８Bに示すように全てバー（水平な棒）の位置にセットされる。時間間隔[T, 2・T]では、図８Ｃに示すように第１のレベルのスイッチはクロス（交差）の位置にセットされ、その他のレベルのものはバーの位置にセットされる。時間間隔[2・T, 3・T]では、第１のレベルのスイッチはバーの位置にセットされ、第２のレベルのスイッチはクロスの位置にセットされ、その他の全部のスイッチはバーの位置にセットされる。図８Ｂから図８Ｉに、８つのスイッチの設定を示す。一般的に、サイズ2N×2Nのバンヤンスイッチの場合には、スイッチは全て、第１の時間間隔の間はバーの位置に設定される。第１のレベルのスイッチは各新規の時間間隔の間は切り替わる。第２のレベルのスイッチは、スイッチは１回おきに切り替わる。次のレベルのスイッチでは、スイッチは４回ごとに切り替わる。プロセスはレベルＫになるまで続き、スイッチは２Ｋ−１回ごとに切り替わる。このプロセスによって、S1は、共有バッファの各々にメッセージセグメントのフリット1つを置き、S2は、共有バッファの各々からメッセージセグメントのフリット1つを移動させ取り除く。取り除かれるセグメントは順番ではない。このため、バンヤンスイッチの実施態様では、フリットをセグメントに再構成させるときに出力プロセッサは若干多くの仕事をこなせる。クロスバーネットワークに対するバンヤンネットワークの利点は、クロスバーネットワークのN２個のスイッチに比べて、バンヤンネットワークではNlog2(N)個のスイッチだけで足りる点である。
【００７６】
トランク出力ラインを伴うスイッチ
図９は、多数の入力ライン904と多数の出力ライン906を持つ装置Ａと複数の装置B0,B1,…,BM-1の装置構成を示すものである。装置B0,B1,…,BM-1は、装置Ａとは別にさらなる入力ラインを持つ。ある実施態様では、装置B0,B1,…,BM-1もスイッチである。装置Ａは図２に示したタイプのものにすることができ、或いは、その他の構成のものにすることもできる。例えば、スイッチＡは、合体させた前述の特許で説明したタイプにすることもできる。特に興味深いケースは、装置Ａを特許８，９で説明したタイプのスイッチングシステムにした場合である。スイッチＡから装置BPへの複数のラインを通るデータは、多数の方法で入力コントローラによって制御され得る。スイッチＡから装置BPへJ個のデータラインがある場合、これをL0,L1,…,LJ-1とする。図２に示すように、スイッチＡは、N個の入力コントローラIC0,IC1,..,ICN-1を持つ。BPを宛先とするデータパケットDPがスイッチＡの入力コントローラICKに到着したとき、入力コントローラICKは、DPの送信に使うためにJ個の伝送ラインL0,L1,…,LJ-1からどれかを選択する。データラインの適正な選択は、BPへの入力が不均衡な負荷を受けないようにし、BPへの入力が高いQOSメッセージの廃棄が強制されないようにすることが重要である。
【００７７】
その他の設定では、装置B0,B1,…,BM-1のうちのＧ個の複数の装置が宛先Ｄへデータを送信するうように位置決めされ、ここでＤは１つの装置或いは装置の集合である。この設定では、伝送ラインL0,L1,…,LJ-1は全て、宛先Ｄまで直接的か間接的かにデータを送る機能を持つ。従って、最初に設定のように、Ａに到着しＤを宛先とするメッセージＭは、伝送ラインL0,L1,…,LJ-1のいずれかを通ってDに到達することができる。繰り返すが、入力コントローラはL0,L1,…,LJ-1から１つの伝送ラインを選択する。
【００７８】
第１の実施態様では、入力コントローラは、各ラインを通じてほぼ同じ量のデータを送り、各ラインを通じて高いＱＯＳデータをほぼ同じ量、送信するシンプルな戦略を利用する。この戦略を実行するためには、入力コントローラは、最近送信したデータの記録を追跡・監視しなければならない。この最小限の戦略が他の戦略よりも好適であるということは全然なく、入力コントローラがJのトランクラインをBPに導く出力ポートの状態に基づき決定しない場合にトランクに負荷がかかり過ぎるという問題が依然として起こり得る。
【００７９】
第２の実態態様では、入力コントローラは、前述の特許９、１０で教示される技術を使用する。この実施態様では、入力コントローラは、メッセージを送信するためBへ特定のラインが接続されている出力コントローラの許可を要求する。この戦略は、第１の実施態様の戦略とともに使用することができる。即ち、入力コントローラは最近使われたものでないラインを選択し当該ラインに接続されている出力コントローラに要求を出す。
【００８０】
第３の実施態様では、入力コントローラはラインBPに接続されている出力ポートのすべての状態情報に基づき出力ポートを選択する。この状態を知る１つの方法は、出力ポート状態情報を受け取ることによるものである。本発明は、制御パケットOPSで渡されるものとしてこの状態情報を説明する。出力ポート状態に基づき、入力ポートは、送られるべき待ちメッセージの小さなキューを持つ出力ポートにデータを送る。
【００８１】
表１    タイミングチャート
時間間隔      生起場所    データ          経由          あて先      場所
前回のサイクル（一定の重要なトランザクションに示す）
[-2T. -T]：    ICKは次のセグメントを選びCIPKを構築する。
OCJは次のセグメントを選びMLAJを構築する。
-----------------------------------------------------------------
[-T,0]          ICK        CIPK            264          SBK        CM1
ICK        DMK                          SBK        CM3
ICK        CPK                          SBK        CM4
……・
OCJ        MLAJ            266        SBJ        CM2
OCJ        OPSJ                        SBJ        CM5
--------------------------------------------------------------------------------------------------------------
現在のサイクル
[0,T]          ICK        F0            208/S1/220      SBK        SAK(MK)
SBK        CIPK          260            SBK+1        CM1
SBK        DMK                          SBK+1        CM3
SBK        CPK                          SBK+1        CM4
SBK        MLAK        274             ICK          該当なし
SBK        OPSK                          ICK          該当なし
…・
SBJ        FP              228/S2/230     ODBJ        該当なし
SBJ        MLAJ            262           SBJ+1        CM2
SBJ        OPSJ                           SBJ+1        CM5
SBJ        CIPJ              270           OCJ        該当なし
SBJ        DMJ                             OCJ        該当なし
SBJ        CPJ                             OCJ        該当なし
-----------------------------------------------------------------
[T,2T]          ICK        F1            208/S1/220      SBK+1        SAK(MK)
SBK+1      CIPK          260            SBK+2        CM1
SBK+1      DMK                          SBK+2        CM3
SBK+1      CPK                          SBK+2        CM4
SBK        MLAK-1        274           ICK          該当なし
SBK        OPSK-1                        ICK          該当なし
…・
SBJ+1      FP+1            228/S2/230     ODBJ        該当なし
SBJ+1      MLAJ          262           SBJ+2        CM2
SBJ+1      OPSJ                         SBJ+2        CM5
SBJ        CIPJ-1          270           OCJ        該当なし
SBJ        DMJ-1                         OCJ        該当なし
SBJ      CPJ-1                             OCJ        該当なし
-----------------------------------------------------------------
…              …        …              …              …          …
…              …        …              …              …          …
[(N-2)T,(N-1)T]  ICK      FN-2          208/S1/220      SBK+(N-2)      SAK(MK)
SBK+(N-2)  CIPK          260            SBK+(N-1)        CM1
SBK+(N-2)  DMK                          SBK+(N-1)        CM3
SBK+(N-2)  CPK                          SBK+(N-1)          CM4
SBK      MLAK-(N-2)      274            ICK            該当なし
SBK      OPSK-(N-2)                      ICK          該当なし
[-2T,-T]      ICKが次のセグメントを選択しCIPK*を構築する。
…・
SBJ+(N-2)    FP+(N-2)        228/S2/230     ODBJ        該当なし
SBJ+(N-2)    MLAJ        262             SBJ+(N-1)        CM2
SBJ+(N-2)    OPSJ                          SBJ+(N-1)      CM5
SBJ        CIPJ-(N-2)-      270           OCJ        該当なし
SBJ        DMJ-(N-2)                       OCJ        該当なし
SBJ      CPJ-(N-2)                         OCJ        該当なし
[-2T,-T]      OCJが次のセグメントを選択しMLAJ*を構築する。
-----------------------------------------------------------------
[(N-1)T,NT]    ICK        FN-1          208/S1/220      SBK+(N-1)      SAK(MK)
[-T,0]       ICK      CIPK*          264            SBK            CM1
ICK      DMK*                          SBK            CM3
ICK      CPK*                          SBK            CM4
SBK      MLAK-(N-1)      274            ICK            該当なし
SBK      OPSK-(N-1)                      ICK          該当なし
…・
SBJ+(N-1)    FP+(N-1)        228/S2/230     ODBJ        該当なし
[-T,0]        OCJ      MLAJ*        266             SBJ            CM2
OCJ      OPSJ*                        SBJ            CM5
SBJ        CIPJ-(N-1)-      270           OCJ        該当なし
SBJ        DMJ-(N-1)                       OCJ        該当なし
SBJ      CPJ-(N-1)                         OCJ        該当なし
-----------------------------------------------------------------------------
【００８２】
表１：タイミングチャートの注
１．ICKはメッセージセグメントを共有バッファに挿入する一般的な入力コントローラを表す。OCJは共有バッファからメッセージセグメントを受信する一般的な出力コントローラを表す。
２．CIPK*、MLAJ*、DMK*、CPK*、およびOPSJ*は、次のサイクルで使用するためN個目の時間間隔でロードされる。
３．[x・T, (x+1)・T]は[x・T, (x+N)mod N・T, (x+1+N)mod N・T]の略式の表記法として使用するものである。
４．Tの負の値は、前回のサイクル（それらの使用に対して）の時間間隔を表す。
５．このタイミングチャートはクロスバースイッチの実施態様のためのものであり、バンヤンスイッチの実施態様のためには異なるタイミングチャートがある。
【図面の簡単な説明】
【００８３】
【図１】ラインカード、共有バッファ、スイッチ構造体、および出力バッファから成る一般的な従来技術のスイッチシステムの例を示す概略ブロック図である。
【図２】本発明による、ラインカード、入力コントローラ、入力スイッチS1、共有バッファ、出力スイッチS2、および出力コントローラを含む、インテリジェント共用メモリスイッチシステムを説明している概略ブロック図である。
【図３】本発明で使用される入力コントローラを説明している概略ブロック図である。
【図４Ａ】スイッチシステムの様々なコンポーネントの中で使用されるパケットのフォーマットを示す図である。
【図４Ｂ】スイッチシステムの様々なコンポーネントの中で使用されるパケットのフォーマットを示す図である。
【図４Ｃ】スイッチシステムの様々なコンポーネントの中で使用されるパケットのフォーマットを示す図である。
【図４Ｄ】スイッチシステムの様々なコンポーネントの中で使用されるパケットのフォーマットを示す図である。
【図４Ｅ】スイッチシステムの様々なコンポーネントの中で使用されるパケットのフォーマットを示す図である。
【図４Ｆ】スイッチシステムの様々なコンポーネントの中で使用されるパケットのフォーマットを示す図である。
【図４Ｇ】スイッチシステムの様々なコンポーネントの中で使用されるパケットのフォーマットを示す図である。
【図５】本発明の共有バッファの概略ブロック図である。
【図６】本発明で使用される出力コントローラの概略ブロック図である。
【図７】CIPパケットを運ぶシフトレジスタの説明図である。
【図８】S1またはS2の使用に適した設計であるバンヤンスイッチの説明図である。
【図９】スイッチB0,B1,…,BP,…,BM-1に対する複数の出力ラインを持つスイッチAの説明図である。
【図１】
2006508558.tif 000003
【図２】
2006508558.tif 000004
【図３】
2006508558.tif 000005
【図４Ａ】
2006508558.tif 000006
【図４Ｂ】
2006508558.tif 000007
【図４Ｃ】
2006508558.tif 000008
【図４Ｄ】
2006508558.tif 000009
【図４Ｅ】
2006508558.tif 000010
【図４Ｆ】
2006508558.tif 000011
【図４Ｇ】
2006508558.tif 000012
【図５】
2006508558.tif 000013
【図６】
2006508558.tif 000014
【図７】
2006508558.tif 000015
【図８Ａ】
2006508558.tif 000016
【図８Ｂ】
2006508558.tif 000017
【図８Ｃ】
2006508558.tif 000018
【図８Ｄ】
2006508558.tif 000019
【図８Ｅ】
2006508558.tif 000020
【図８Ｆ】
2006508558.tif 000021
【図８Ｇ】
2006508558.tif 000022
【図８Ｈ】
2006508558.tif 000023
【図８Ｉ】
2006508558.tif 000024
【図９】
2006508558.tif 000025
【国際調査報告】
2006508558.tif 000026