(57)【要約】【課題】  競合問題の発生することのない、複数の送信機と受信機との間の通信を調節するシステムを提供すること。【解決手段】  このシステムは複数のセルを備え、ここで、各セルは、複数の送信機中の１つの送信機から受信機への通信を制御する。単一のトークンが、この複数のセルを通過するリングを通じて流れ、ここで、セル内のこのトークンの存在が、対応する送信機がこの受信機と通信し得ることを示す。このシステムは、さらに、複数の受信機、および、複数のトークンリングを備えてもよく、ここで、各トークンリングは、複数の送信機からそのトークンリングに対応する受信機への通信を制御するトークンリングセル中の対応する１つのトークンを通過させる。【選択図】  なし【特許請求の範囲】
【請求項１】
複数の送信機と受信機との間の通信を調節するシステムであって：
複数のセルであって、ここで、各セルが、複数の送信機中の１つの送信機から受信機への通信を制御する、セル；を備え、
ここで、該複数のセルが、該複数の送信機から該受信機への通信を調節するトークンリング中に配列され；そして
ここで、トークンリングセル内のトークンの存在が、対応する送信機が該受信機と通信し得ることを示す、システム。
【請求項２】
さらに：
複数の受信機；および
複数のトークンリングを備え、ここで、各トークンリングが、前記複数の送信機から前記トークンリングに対応する受信機への通信を制御するトークンリングセル中の対応する１つのトークンを通過させる、請求項１に記載のシステム。
【請求項３】
前記複数のセルがグリッド状に配列され、ここで、行が送信機に対応し、そして列が受信機に対応する、請求項２に記載のシステム。
【請求項４】
前記通信が：
電気的信号；
機械的信号；および
光学的信号の１つを含み得る、請求項１に記載のシステム。
【請求項５】
各セルが、対応する送信機からリクエスト信号を受信するように構成され、そして該リクエスト信号に応答して、該対応する送信機に、該セルが前記トークンを有する場合に該対応する送信機が送信を開始することを可能にする承認信号を発行するように構成される、請求項１に記載のシステム。
【請求項６】
各送信機が、前記リクエスト信号をリセットすることにより、前記受信機と通信するためにクリアランスをリリースするよう構成されるリセット機構をさらに備える、請求項５に記載のシステム。
【請求項７】
前記システムが、前記承認信号をリセットすることにより、前記クリアランスのリリースを確認するように構成される承認機構をさらに備える、請求項６に記載のシステム。
【請求項８】
前記トークンリング中の単一のトークンを初期化するように構成される初期化機構をさらに備える、請求項１に記載のシステム。
【請求項９】
前記システムが、非同期的に作動する、請求項１に記載のシステム。
【請求項１０】
前記システムが、前記送信機から前記受信機への通信を該受信機のリクエストで選択的に制限するように構成されるフロー制御機構をさらに備える、請求項１に記載のシステム。
【請求項１１】
複数の送信機と受信機との間の通信を調節する方法であって：
送信機からのリクエスト信号であって、受信機と通信することをリクエストする信号を複数のセル中の１つのセルにおいて受信する工程であって；
ここで、該複数のセルが、該複数の送信機から該受信機への通信を調節するトークンリング中に配列される工程；および
該リクエスト信号に応答して、該送信機に、該セル内にトークンの存在が検出される場合に該送信機が送信を開始することを可能にする承認信号を発行する工程、を包含する、方法。
【請求項１２】
前記複数のセルが複数のトークンリングを含み、各トークンリングが、前記複数の送信機から該トークンリングに対応する受信機への通信を制御するトークンリングセルの中の対応するトークンを通過させる、請求項１１に記載の方法。
【請求項１３】
前記送信機と受信機との間の通信を調節する複数のセルがグリッド状に配列され、ここで、行が送信機に、そして列が受信機に対応する、請求項１１に記載の方法。
【請求項１４】
前記通信が：
電気的信号；
機械的信号；および
光学的信号の１つを含み得る、請求項１１に記載の方法。
【請求項１５】
前記送信機が前記リクエスト信号をリセットするとき、該送信機が前記受信機と通信する許可を取り消す工程をさらに包含する、請求項１１に記載の方法。
【請求項１６】
前記送信機が前記受信機と通信する前記許可の取り消しを確認するための承認信号をリセットする工程をさらに包含する、請求項１５に記載の方法。
【請求項１７】
前記トークンリング中のトークンを初期化する工程をさらに包含する、請求項１１に記載の方法。
【請求項１８】
前記システムが、非同期的に作動する、請求項１１に記載の方法。
【請求項１９】
前記受信機のリクエストで、前記送信機から前記受信機への通信を選択的に制限することにより、通信のフローを制御する工程をさらに包含する、請求項１１に記載の方法。
【請求項２０】
マルチプロセッサシステムであって：
複数のプロセッサ；
該プロセッサと関連する複数の送信機；
該複数のプロセッサと関連する受信機；
複数のセルであって、各セルが、該複数の送信機中の１つの送信機から受信機への通信を制御する、セル；を備え、
ここで、該複数のセルが、該複数の送信機から受信機への通信を調節するトークンリング中に配列され；そしてトークンリングセル内のトークンの存在が、対応する送信機が該受信機と通信し得ることを示す、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
（政府のライセンス権利）
本発明は、米国国防総省国防高等研究事務局により授与された契約番号ＮＢＣＨ０２００５５の下、合衆国政府の支援でなされた。合衆国政府は、本発明において特定の権利を有する。
【０００２】
（発明の分野）
本発明は、通信ネットワークに関する。より詳細には、本発明は、複数の送信機と受信機との間の通信を調節するための方法および装置に関する。
【背景技術】
【０００３】
（関連分野）
現代のマルチプロセッサシステムは、代表的には、通信ネットワークを通じて互いに通信する複数のコンピューティングノードを含む。いくつかのマルチプロセッサシステムでは、これらの複数のノードの各々は、他の任意のノードと通信し得るが、各ノードは、任意の所定の時間に１つのノードのみと通信し得る。これは、潜在的に競合問題を引き起こし得る。なぜなら、複数ノードが、同時に共通のノードと通信することを希望し、そしてこの共通ノードは、任意の所定の時間に１つのノードのみと通信し得るからである。この問題は、通信媒体が、光学的、電気的または機械的のいずれであろうと、そのタイプにかかわらず存在することに注意のこと。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
これらのマルチプロセッサシステム中のノード間の通信を調節するために多くの異なるシステムが開発されており、そしてそのようにすることで、競合問題を取り扱う。不幸にも、多くのこれらのシステムは、所望されない副作用を有している。いくつかは、作動するのが複雑および高価であり、その一方、通信プロセス中に不必要な遅延を導入するものもある。
【０００５】
これ故、必要なのは、上記の問題なしにノード間のトラフィックを調節するための方法および装置である。
【課題を解決するための手段】
【０００６】
本発明によるシステムは、複数の送信機と受信機との間の通信を調節するシステムであって、複数のセルであって、各セルが、複数の送信機中の１つの送信機から受信機への通信を制御する、セルを備え、ここで、該複数のセルが、該複数の送信機から該受信機への通信を調節するトークンリング中に配列され、そして、トークンリングセル内のトークンの存在が、対応する送信機が該受信機と通信し得ることを示し、これにより、上記目的を達成する。
【０００７】
さらに、複数の受信機、および複数のトークンリングを備え、ここで、各トークンリングが、前記複数の送信機から前記トークンリングに対応する受信機への通信を制御するトークンリングセル中の対応する１つのトークンを通過させてもよい。
【０００８】
前記複数のセルがグリッド状に配列され、ここで、行が送信機に対応し、そして列が受信機に対応してもよい。
【０００９】
前記通信が、電気的信号、機械的信号、および光学的信号の１つを含み得る。
【００１０】
各セルが、対応する送信機からリクエスト信号を受信するように構成され、そして該リクエスト信号に応答して、該対応する送信機に、該セルが前記トークンを有する場合に該対応する送信機が送信を開始することを可能にする承認信号を発行するように構成されてもよい。
【００１１】
各送信機が、前記リクエスト信号をリセットすることにより、前記受信機と通信するためにクリアランスをリリースするよう構成されるリセット機構をさらに備えていてもよい。
【００１２】
前記システムが、前記承認信号をリセットすることにより、前記クリアランスのリリースを確認するように構成される承認機構をさらに備えていてもよい。
【００１３】
前記トークンリング中の単一のトークンを初期化するように構成される初期化機構をさらに備えていてもよい。
【００１４】
前記システムが、非同期的に作動してもよい。
【００１５】
前記システムが、前記送信機から前記受信機への通信を該受信機のリクエストで選択的に制限するように構成されるフロー制御機構をさらに備えていてもよい。
【００１６】
複数の送信機と受信機との間の通信を調節する方法であって、送信機からのリクエスト信号であって、受信機と通信することをリクエストする信号を複数のセル中の１つのセルにおいて受信する工程であって、ここで、該複数のセルが、該複数の送信機から該受信機への通信を調節するトークンリング中に配列される工程、および該リクエスト信号に応答して、該送信機に、該セル内にトークンの存在が検出される場合に該送信機が送信を開始することを可能にする承認信号を発行する工程、を包含し、それにより、上記目的を達成する。
【００１７】
前記複数のセルが複数のトークンリングを含み、各トークンリングが、前記複数の送信機から該トークンリングに対応する受信機への通信を制御するトークンリングセルの中の対応するトークンを通過させてもよい。
【００１８】
前記送信機と受信機との間の通信を調節する複数のセルがグリッド状に配列され、ここで、行が送信機に、そして列が受信機に対応してもよい。
【００１９】
前記通信が、電気的信号、機械的信号、および光学的信号の１つを含み得る。
【００２０】
前記送信機が前記リクエスト信号をリセットするとき、該送信機が前記受信機と通信する許可を取り消す工程をさらに包含してもよい。
【００２１】
前記送信機が前記受信機と通信する前記許可の取り消しを確認するための承認信号をリセットする工程をさらに包含してもよい。
【００２２】
前記トークンリング中のトークンを初期化する工程をさらに包含してもよい。
【００２３】
前記システムが、非同期的に作動してもよい。
【００２４】
前記受信機のリクエストで、前記送信機から前記受信機への通信を選択的に制限することにより、通信のフローを制御する工程をさらに包含してもよい。
【００２５】
マルチプロセッサシステムであって、複数のプロセッサ、該プロセッサと関連する複数の送信機、該複数のプロセッサと関連する受信機、複数のセルであって、各セルが、該複数の送信機中の１つの送信機から受信機への通信を制御する、セルを備え、ここで、該複数のセルが、該複数の送信機から受信機への通信を調節するトークンリング中に配列され；そしてトークンリングセル内のトークンの存在が、対応する送信機が該受信機と通信し得ることを示し、これにより、上記目的を達成する。
【００２６】
本発明の１つの実施形態は、複数の送信機と受信機との間の通信を調節するシステムを提供する。このシステムは、複数のセルを備え、ここで、各セルは、複数の送信機中の１つの送信機から受信機への通信を制御する。ここで、単一のトークンは、複数のセルを通過するリングを通じて流れ、ここで、セル内のこのトークンの存在が、対応する送信機がこの受信機と通信し得ることを示す。
【００２７】
この実施形態に対する改変では、このシステムはまた、複数の受信機を含む。各受信機は、上記複数の送信機とその受信機との間の通信を制御するそれ自身のトークンリングを有している。
【００２８】
さらなる改変では、上記複数のセルは、行が送信機に対応し、そして列が受信機に対応するグリッド状に配列され、それによって、このグリッド配列が、コンパクトな平面レイアウトを容易にする。
【００２９】
この実施形態の改変では、上記通信は、電気的信号、光学的信号、または機械的信号を含み得る。
【００３０】
この実施形態の改変では、各セルは、対応する送信機からリクエスト信号を受信するように構成され、そしてリクエスト信号に応答して、上記セルがトークンを有する場合に、この対応する送信機に、この対応する送信機が送信を開始することを可能にする承認信号を発行するように構成されている。
【００３１】
この実施形態に対する改変では、上記システムはまた、上記トークンリング中の単一のトークンを初期化するように構成されている初期化機構を含む。
【００３２】
この実施形態に対する改変では、上記システムは、非同期的に作動する。
【００３３】
この実施形態に対する改変では、各送信機は、上記リクエスト信号をリセットすることによって上記受信機と通信するためのクリアランスをリリースするように構成されるリセット機構を含む。
【００３４】
さらなる改変では、上記システムは、上記承認信号をリセットすることにより上記クリアランスのリリースを確認するように構成される承認機構を含む。
【００３５】
この実施形態の改変では、上記システムは、上記送信機から受信機への通信をこの受信機のリクエストで選択的に制限するように構成されるフロー制御機構を含む。
【発明の効果】
【００３６】
本発明により、作動するのが複雑または高価であることも、通信プロセス中に不必要な遅延を導入することもなく、競合問題を発生させないで、複数の送信機と受信機との間の通信を調節することができる。
【発明を実施するための最良の形態】
【００３７】
（詳細な説明）
以下の記載は、当業者が本発明を作製および使用することを可能にするために提示され、そして特定の用途およびその用件の文脈で提供される。開示された実施形態に対する種々の改変は、当業者に容易に明らかであり、そして本明細書で規定される一般的原理は、本発明の思想および範囲から逸脱することなく他の実施形態および用途に適用され得る。従って、本発明は、示される実施形態に制限されることは意図されず、本明細書に開示の原理および特徴と一致する最も広い範囲と一致すべきである。
【００３８】
（コントローラ）
図１は、本発明の実施形態によるコントローラ１００を図示する。本発明の１つの実施形態では、任意の送信機が任意の受信機に送信し得るが、コントローラ１００からクリアランスを得た後のみ、その送信が行われる。このクリアランスを得るために、送信機は、受信機のアドレスを特定しなければならず、そしてコントローラ１００からクリアランスをリクエストしなければならない。コントローラ１００のジョブは、任意の受信機について、任意の時間に多くとも１つの送信機がこの受信機に送信するためのクリアランスをもつことを確実にすることである。
【００３９】
コントローラ１００は、Ｎ個のトークンリングを用いて送信機にクリアランスを許可する。各受信機について１つのトークンリングが存在し、そして各トークンリングは、各送信機について１つのセルで、Ｎ個のセルのリングからなる。トークンは、各トークンリング内でセルからセルに循環する。送信機ｉは、受信機ｊに送るためのクリアランスを、リクエストおよび行き先アドレスをすべてのセル（ｉ、ｋ）（ｋ＝０、・・・、Ｎ−１）で送信することによってリクエストする。このトークンがセル（ｉ、ｊ）に到着し、そしてリクエストが行き先アドレスｊとともにペンディングしているとき、セルは、このリクエストを許可し、そして送信機ｉは、受信機ｊに送信し得る。送信の終了に際し、このトークンは、トークンリング中の次のセル（ｉ＋１、ｊ）に転送される。このトークンがセル（ｉ、ｊ）に到着し、そしてペンディングしているリクエストがないとき、このセルは、トークンリング中の次のセルにこのトークンを単に転送する。各トークンリング中には多くとも１つのトークンが存在するので、任意の時間に多くとも１つの送信機が、特定の受信機に送信するためのクリアランスを有し得る。さらに、このトークンは、リング中を移動するので、コントローラ１００は、そのトークンリングと関連する受信機に送信するためのクリアランスを発行するために、送信機間のラウンドロビンスキームを実装する。
【００４０】
本発明の１つの実施形態では、コントローラ１００は、すべての送信機への接続を有しているが、任意の受信機との接続はない。コントローラ１００は、ｉ＝０、１、・・・、（Ｎ−１）に対し、以下の接続を有している：
【００４１】
【表１】
2005136971.tif 000002
送信機ｉが受信機ｊに送信することを希望するとき、以下のアクションのシークエンスが起こる：
１．送信機ｉは、同時に：
−  アドレスＤをｊに、そして次にＲを１にセットし、受信機ｊに送信するためにクリアランスをリクエストする；および
−  必要であれば、そのレーザーを正しい周波数にセットする。
２．送信機ｉは、以下の両方が生じるまで待つ：
−  Ａ＝１、すなわち、送信するためのクリアランスを有する；および
−  そのレーザーが正しい周波数に変わる；
次いで、送信機ｉは、そのバケットを受信機ｊに送信する。
３．パケットの送信の終了に際し、送信機ｉは、Ｒを０にリセットし、そして次にコントローラ１００がＡを０にリセットするまで待つ。
【００４２】
アクション１〜３のシークエンスは、送信機ｉが任意の受信機に送信することを希望するごとに繰り返す。本発明の１つの実施形態では、送信機は厳密なリクエスト−承認プロトコルに固執することに注目のこと：送信前、リクエストＲをセットし、そして承認Ａがセットされるまで待つ；送信後、リクエストＲをリセットし、そして承認Ａがリセットされるまで待つ。
【００４３】
コントローラ１００は、セルのＮ×Ｎのアレイであり、行が送信機に対応し、そして列が受信機に対応する。セル（ｉ、ｊ）は、送信機ｉおよび受信機ｊに対応する。列中のすべてのセルは、トークンリングと呼ばれるリング状接続の一部である。図１は、Ｎ＝３に対するコントローラを示す。
【００４４】
任意の時間に、そして任意の受信機について、多くとも１つの送信機が、その受信機に送信するためのクリアランスを有し得る。コントローラ１００の機能は、同じ受信機に送信するためにクラアランスをリクエストするすべての送信機の中を調停することである。例えば、送信機ｉは、受信機ｊに送信するためのクラアランスを、最初、アドレス行き先Ｄをｊにセットすることによりリクエストする。アドレスビットが有効になった後、送信機ｉは、リクエストビット、すなわち、Ｒ＝１をセットする。すべてのセル（ｉ、０...Ｎ−１）は、このリクエストを、Ｄ＝ｊ、Ｒ＝１で送信機ｉから受信するが、セル（ｉ、ｊ）のみがこのリクエストを適正なリクエストとして解釈する。なぜなら、この行き先アドレスＤは、配線されたセルのインデックスｊに等しいからである。
【００４５】
互いの排除を達成するために、各トークンリングは、多くても１つのトークンを有している。初期には、各トークンリングにトークンはない。初期化の直後、コントローラは、信号Ｇｏ上に１の電圧遷移を提供することにより、各トークンリング中に正確に１つのトークンを起動する。次にこのトークンは、所定の時間に１より多いセル中にあることは絶対になく、セルからセルに、このトークンリングを通じて循環する。
【００４６】
トークンを受信するに際し、セル（ｉ、ｊ）は、次のセルにこのトークンを渡すことかまたはこのトークンを保持することと、送信機ｉにクリアランスを発行することとの間を調停する。セル（ｉ、ｊ）は、セル（ｉ、ｊ）がトークンを有し、行き先アドレスＤが受信機のインデックスｊ（ｊ＝Ｄ）に等しく、そしてリクエストビットＲがセットされる（Ｒ＝１）両方であるときのみ、送信機ｉにクリアランスを発行する。セルは、承認出力（Ａ＝１）をセットすることによりクリアランスを発行する。次にこの承認は、行のセルを通じて送信機に伝播する。セルの各行では、多くとも１つの承認が送信機に伝播する。なぜなら、多くとも１つのセルが承認を開始し、そして各送信機は、第１のリクエストのための送信が終了するまで、任意の受信機に送信のための第２のリクエストを決して送信しないからである。
【００４７】
送信機が、受信機ｊへの送信を終了したとき、この送信機は、リクエストビットＲをリセット（Ｒ＝０）することによりクリアランスをリリースする。コントローラは、このクリアランスのリリースを、承認ビットＡをリセット（Ａ＝０）することにより確認する。クリアランスのリリースの後、セル（ｉ、ｊ）は、トークンを、トークンリング中の次のセルに渡す。この構成は、受信機ｊに送信することを希望する送信機の中でラウンドロビンアクセスを実装する。
【００４８】
本発明のこの実施形態が作動するために、すべてのメッセージが任意の受信機に順番に到着することが重要である。メッセージは、順序が狂って到着し得る。例えば、送信機Ｔ０が遅いリンクを介して受信機Ｒにメッセージを送信し、そして次に送信機Ｔ１が高速リンクを介して受信機Ｒにメッセージを送信するとき、Ｔ０からのメッセージの一部分は、なお遷移中である。この場合、送信機Ｔ１からのメッセージの開始は、送信機Ｔ０からのメッセージの終わりの前に到着し得る。この問題を避けるためには、１つの送信機からのすべての信号が、次の送信機の最初の信号が到着し得る前に受信機に到着することが重要である。このようにして、任意の信号の送信機の同一性（アイデンティティ）は常に明確である。この要件は、任意の送信機から任意の受信機への光学的リンク上の総遅延における最大差異が、コントローラが１つの送信機から他の送信機へ送信すべきクリアランスをスイッチすることに要する時間より少ないことを確実にすることにより満たされ得る。
【００４９】
（アービター）
図２は、本発明の実施形態によるアービター２００を図示している。アービター２００は、重要セクションに入ることをリクエストする２つのプロセス間の互いの排除を実現する第１の要素である。本発明の１つの実施形態では、プロセスは、通信プロトコルとして理解され得る。
【００５０】
アービター２００の通信挙動は、２つのより小さな通信プロトコルの組み合わせである。１つの通信プロトコルは、端子Ｒｅｑ０およびＡｃｋ０に関係し、そして他方の通信プロトコルは、端子Ｒｅｑ１およびＡｃｋ１に関係する。各通信プロトコルは、レベルに基づく４相の信号伝達を反映する４つのイベントを有している。各プロトコルにおけるイベントは、以下のようである：
【００５１】
【表２】
2005136971.tif 000003
表２は、本発明の実施形態によるアービター２００のイベントおよびそれらに関連する意味を図示する。
【００５２】
ここで、↑は、立ち上がり遷移を意味し、そして↓は立ち下がり遷移を意味する。
【００５３】
アービター２００の両方のリクエスト−承認のペアのための通信プロトコルは、リクエストに続く承認の無限の繰り返しである。アービター２００のリクエスト−承認の各ペアは、２つの安定な初期状態（Ｒｅｑ、Ａｃｋ）＝（０、０）または（Ｒｅｑ、Ａｃｋ）＝（１、１）のいずれかで開始し得る；そして多くても１つのペアが状態（１、１）で開始し得る。プロトコルが初期状態（Ｒｅｑ、Ａｃｋ）＝（０、０）で開始するとき、このプロトコルは、重要セクションの外側にある。このプロトコルは、シークエンスＲｅｑ↑→Ａｃｋ↑→Ｒｅｑ↓→Ａｃｋ↓の繰り返しである。
【００５４】
プロトコルが初期状態（Ｒｅｑ、Ａｃｋ）＝（１、１）で開始するとき、このプロトコルは重要セクションの内側にある。後者の初期状態で開始すると、このプロトコルは、シークエンスＲｅｑ↓→Ａｃｋ↓→Ｒｅｑ↑→Ａｃｋ↑の繰り返しである。
【００５５】
（Ｒｅｑ０、Ａｃｋ０）に対する、および（Ｒｅｑ１、Ａｃｋ１）に対するこの２つのプロトコルは、非同期的かつ同時に作動する。アービター２００の機能は、多くても１つのプロトコルがその重要セクションにあることを確実にすることである。プロトコル（Ｒｅｑ０、Ａｃｋ０）は、Ａｃｋ０＝１のときその重要セクション内にある。プロトコル（Ｒｅｑ１、Ａｃｋ１）は、Ａｃｋ１＝１のときその重要セクション内にある。アービター２００は、出力Ａｃｋ０およびＡｃｋ１が両方１では決してないことを確実にする。例えば、プロトコル１がその重要セクション内にある、すなわち、Ｒｅｑ１＝１およびＡｃｋ１＝１であり、かつプロトコル０がＲｅｑ０を１にセットすることによりその重要セクションへのアクセスをリクエストする場合、アービター２００は、プロトコル１がその重要セクションをリリースするまでプロトコル０に対する認可をブロックする。
【００５６】
（トグル）
図３は、本発明の実施形態によるトグル３００を図示している。トグル３００は、１つの入力、ならびにｏｕｔＡおよびｏｕｔＢと表した２つの出力を有している。出力ｏｕｔＡは、黒丸でマークされ、この実施形態における特定の初期化を示す。
【００５７】
一般に、トグル３００の挙動は、以下のシークエンスによって説明され得、これは
【００５８】
【数１】
2005136971.tif 000004
を無限に繰り返す。
【００５９】
ここで、
【００６０】
【数２】
2005136971.tif 000005
は、電圧遷移（すなわち、立ち上がりまたは立ち下がり遷移）を示す。入力における任意の電圧遷移は、出力における電圧遷移に伝播し、ここで、遷移は、交互の出力で起こる。従って、入力におけるすべての立ち上がり遷移が１つの出力に伝播し、そしてすべての立ち下がり遷移は他方の出力に伝播する。
【００６１】
いくつかの可能な初期化が存在する。本発明の１つの実施形態では、トグル３００のすべての例について以下の初期化が用いられる：ｉｎ＝１、ｏｕｔＡ＝１、ｏｕｔＢ＝０。出力における第１の遷移は、黒点ｏｕｔＡを有する出力で生じる。初期化の後、以下の挙動を無限に繰り返す：ｉｎ↓→ｏｕｔＡ↓→ｉｎ↑→ｏｕｔＢ↑→ｉｎ↓→ｏｕｔＡ↑→ｉｎ↑→ｏｕｔＢ↓、ここで↑は立ち上がり遷移しを意味し、そして↓は立ち下がり遷移を意味する。
【００６２】
以下は、シークエンス中のトグル３００のすべての遷移を列挙する：
【００６３】
【表３】
2005136971.tif 000006
表３は、本発明の実施形態によるトグル３００の状態遷移を図示する。
【００６４】
（初期化モジュール）
図４Ａは、本発明の実施形態による初期化モジュール４００を図示している。初期化の後、トークンは、入力Ｇｏにおいて電圧を立ち上げ、そして次にこの電圧をハイに維持することによりトークンリング中に起動される。図４Ａ〜４Ｃにおいて、ノードにおけるデジット０または１は、その特定のノードがセットされなければならない初期値を示す。表示（０）または（１）は、ノードが初期化の後到達する値を表す。（０）または（１）で表されるノードは、初期にセットされる必要はない。
【００６５】
（セル）
図４Ｂは、本発明の実施形態によるセル（ｉ、ｊ）を図示する。「Ｄ＝ｊ？」と表されるコンパレータは、行き先アドレスＤとセルのインデックスｊとの間のコンパレータであり、ｊはコンパレータに配線されている。３２個の受信機の場合、Ｄは５ビットのアドレスとなる。このコンパレータの出力は、Ｄ＝ｊのとき１であり、そうでなければ０である。
【００６６】
最初に、アービター２００は、（Ｒｅｑ１、Ａｃｋ１）ペアに重要セクションへのアクセスを許可する。これは、送信機からの任意にリクエストが、アービター２００入力Ｒｅｑ０でブロックされることを意味する。本発明者らは、送信機からリクエストがないとき、セル（ｉ、ｊ）実装を通るトークンの伝播を最初に記載している。
【００６７】
図４Ｃは、本発明の実施形態によるセル（ｉ、ｊ）を通るトークンの伝播経路を図示している。トークンは、電圧遷移によりＴｉｎで到着する。初期には、これは立ち上がり電圧遷移である。トークンの到着後、ＸＯＲゲートは、アービター２００の入力Ｒｅｑ１を低下させ、それによって重要セクションをリリースする。アービター２００は、Ａｃｋ１を低下させることにより、重要セクションのリリースを承認する。Ａｃｋ１上の立ち下がり遷移は、トグル３００、戻りループ、およびＸＯＲゲートを通り、いくらかの遅延の後、アービター２００の入力Ｒｅｑ１に戻る。今回は、Ｒｅｑ１上の遷移は、立ち上がり遷移であり、重要セクションにアクセスするためのリクエストを意味する。戻りループを通じる伝播の前またはその間に、アービター２００の入力Ｒｅｑ０に到着する送信機からのリクエストがかない場合、アービター２００は、出力Ａｃｋ１を立ち上げることによりトークンリクエストＲｅｑ１を許可する。Ａｃｋ１上の立ち上がり遷移の後、トグル３００は、Ｔｏｕｔ上で遷移を引き起こし、それによってトークンを、トークンリング中の次のセルに転送する。
【００６８】
トークンがセル（ｉ、ｊ）に到着するとき、アービター２００は、このトークンが戻りループを通じて伝播する時間の間に、短時間で重要セクションをリリースする。この短時間のリリースの間に、アービター２００は、送信機の任意のリクエストを認可し得る。アービター２００がＡｃｋ０を１にセットすることにより送信機にクラアリンスを認可するとき、アービター２００は、送信機がクリアランスをリリースするまで、セル（ｉ、ｊ）実装を通るトークンのさらなる伝播をブロックする。このクリアランスのリリースに際し、アービター２００は、トークンリクエストを認可し、それは、次に、このトークンが次のセルに伝播することを引き起こす。Ｔｉｎにおけるトークンの到着が、立ち上がり遷移および立ち下がり遷移としてそれ自身を交互に表すことにも注目のこと。同様に、Ｔｏｕｔにおけるトークンの退去は、立ち上がり遷移および立ち下がり遷移としてそれ自身を交互に表す。ＴｉｎとＴｏｕｔにおける値が異なるとき、トークンはセル内側にある。
【００６９】
（タイミング図）
図５は、本発明の実施形態によるタイミング図を提示している。密な垂直線で満たされた４つの矩形は、任意の長さの期間であり得る。ＲＬは、戻りループ内の信号の値を表し、そしてＸｍｔは、送信機が受信機に送信するためのクリアランスを有するときを示す。
【００７０】
（フロー制御）
図６は、本発明の実施形態によるフロー制御を備えたコントローラ６００を図示する。しばしば、受信機は、制限されたバッファー能力を有し、そしてバッファーオーバーフローを防ぐために、このシステムは、フロー制御機構を必要とする。本発明の１つの実施形態では、このシステムは、各受信機からコントローラ６００を経由して送信機にＦＣと呼ばれる１ビットチャネルを用いることにより、フロー制御を達成する。このチャネルは、Ｘｏｎ／Ｘｏｆｆ信号伝達を用い、これは、受信機が、ＦＣを１にセットすること（Ｘｏｎ）によりデータを受信する準備ができていること信号伝達し得ること、および受信機が、ＦＣを０にリセットすること（Ｘｏｆｆ）によりまもなくあらゆるデータを受信することができなくなることを信号伝達し得ることを意味している。
【００７１】
ＸｏｎおよびＸｏｆｆを発行するときは、受信機次第である。送信機は、Ｘｏｆｆを受信した後、またはデータ損失の危険性があるとすぐに送信を休止しなければならない。ＸｏｎまたはＸｏｆｆを発行するときの決定は、受信機がフロー制御コマンドを送信する時間から、受信機でコマンドが有効になるまで（すなわち、データフローの開始または停止）の待ち時間に依存する。
【００７２】
受信機は、そのバッファー中の最高マークおよび最低マークに基づいてＸｏｎ／Ｘｏｆｆ決定をなし得る。最高マークの目的は、データ損失を防ぐことによる正確さであり、その一方、最低マークの目的は、受信機のスターベイションを防ぐことによる効率である。
【００７３】
システムにフロー制御を付加するに際し、コントローラ６００は、ここで、２つのタスクを有している。コントローラ６００の第１のジョブは、図１に図示されるような任意の送信機から任意の受信機へのデータのスイッチングを可能にすることである。コントローラ６００の第２のジョブは、任意の受信機からその目下の送信機へのフロー制御の信号伝達（ここで、フロー制御情報は、反対の方向に移動する）を容易にすることである。特に、コントローラ６００が、受信機からＸｏｎまたはＸｏｆｆ信号を受信するとき、コントローラ６００は、次にデータを受信機に送信している送信機へのＸｏｎ／Ｘｏｆｆ信号をリレーしなければならない。
【００７４】
図７は、本発明の実施形態によるフロー制御を備えたセル（ｉ、ｊ）を図示している。「ＡＭＰ」と表された箱は、増幅器を表している。受信機ｊは、受信機ｊと関連するトークンリングセルの列に沿って伝播する、ＦＣ．ｊと呼ばれる１ビット信号を発行する。ＦＣ．ｊ＝１は、受信機ｊがデータを受信する準備ができていることを意味する；ＦＣ．ｊ＝０は、受信機ｊがまもなくデータを受信しなくなることを意味する。
【００７５】
送信機ｉは、送信機ｉと関連するトークンリングセルの行に沿って伝播するＡ．ｉと呼ばれる１ビット信号を受信する。Ａ．ｉ＝１は、送信機ｉがデータを送信するためのクリアランスを有し、そして受信機がデータを受信する準備ができていることを意味し；Ａ．ｉ＝０は、送信機ｉが送信するためのクリアランスを有さないか、または受信機がまもなくデータを受信しなくなることを意味する。それ故、送信機についてＡ＝１は、それが送信し得ることを意味し、そしてＡ＝０は、それが送信することを待たなければならないことを意味する。各Ａ．ｉ信号は、エッジにおいて値０で開始し、そして行に沿って各セル中でＯＲ演算される。多くとも１つのセルが、Ａ．ｉを１にセットし、Ａ．ｉを０にリセットすることができる。
【００７６】
以下は、各送信機についてＲおよびＡの値の組み合わせ、およびそれらの意味である：
【００７７】
【表４】
2005136971.tif 000007
表４は、本発明の実施形態による送信機のＲおよびＡの値およびそれらに関連する意味を図示する。
【００７８】
コントローラ６００は、どの送信機が受信機に送信すべきクリアランスを有するのかを知っているので、コントローラ６００は、この知識を用いてＸｏｎ／Ｘｏｆｆを適正な送信機にリレーし得る。コントローラ６００の実装にフロー制御信号伝達の付加を実装することは、簡単である。例えば、コントローラ６００は、送信機のための新たな「送信すべきクリアランス」信号を、送信機のための古い「送信すべきクリアランス」信号と送信機が送信を希望する受信機のフロー制御信号との論理ＡＮＤとして規定し得る。
【００７９】
この実施形態にともなう１つの小さな問題が存在し得る。送信機が受信機にメッセージの終わりを送信するのとほぼ同時に、この受信機は、そのフロー制御を０にセットし得る。引き続き、送信機は、トークンリング中にトークンをリリースし、そして次のトークンリングセル中のアービターは、Ａｃｋ０を１にセットし得る。Ａｃｋ０の立ち上がりエッジは、入力ＦＣｉｎが０にリセットされるとほぼ同時に生じ得る。その結果、ほぼ同時に、ＡＮＤゲートの入力が反対の方向に変化し得、それは、ＡＮＤゲートの出力上に小パルスを生成し得る。短パルスにともなう任意の課題を避けるために、送信機は、このような短パルスを処理する回路を含み得る。
【００８０】
コンコローラー６００は、任意の送信機からリクエストを受信し、そして可能な限りすばやく送信するクリアランスを発行する。送信の間に、コントローラ６００は、受信機から適切な送信機にフロー制御情報を転送する。重負荷の下では、クリアランスを割り当てるスキームは、単純なラウンドロビンの割当てになる。コントローラ６００は、正しい待ち行列を維持し、ここで、任意の送信機は、二度目の受信機に送信するクラアランスを、その他のすべての送信機が、同じ受信機に送信すべきクリアランスを受信する機会を有した後にのみ、得ることができる。コントローラはまた、Ｘｏｎ／Ｘｏｆｆフロー制御を取り扱い得る。
【００８１】
本発明の実施形態の先行する説明は、例示および説明の目的にのみ提示されている。これらは、排他的であるか、または本発明を開示された形態に制限することは意図しない。従って、多くの変形例および改変例は、当業者に明らかである。さらに、上記の開示は、本発明を制限することは意図されない。本発明の範囲は、添付の請求項によって規定される。
【００８２】
（要約）
本発明の１つの実施形態は、複数の送信機と受信機との間の通信を調節するシステムを提供する。このシステムは複数のセルを備え、ここで、各セルは、複数の送信機中の１つの送信機から受信機への通信を制御する。単一のトークンが、この複数のセルを通過するリングを通じて流れ、ここで、セル内のこのトークンの存在が、対応する送信機がこの受信機と通信し得ることを示す。
【図面の簡単な説明】
【００８３】
【図１】図１は、本発明の実施形態によりコントローラを図示する。
【図２】図２は、本発明の実施形態によるアービターを図示する。
【図３】図３は、本発明の実施形態によるトグルを図示する。
【図４Ａ】図４Ａは、本発明の実施形態による初期化モジュールを図示する。
【図４Ｂ】図４Ｂは、本発明の実施形態によるセルを図示する。
【図４Ｃ】図４Ｃは、本発明の実施形態によるセルを通るトークンの伝播経路を図示する。
【図５】図５は、本発明の実施形態によるタイミング図を提示する。
【図６】図６は、本発明の実施形態によるフロー制御を備えたコントローラを図示する。
【図７】図７は、本発明の実施形態によるフロー制御を備えたセルを図示する。
【符号の説明】
【００８４】
１００  コントローラ
２００  アービター
３００  トグル
４００  初期化モジュール
６００コントローラ
【図１】
2005136971.tif 000008
【図２】
2005136971.tif 000009
【図３】
2005136971.tif 000010
【図４Ａ】
2005136971.tif 000011
【図４Ｂ】
2005136971.tif 000012
【図４Ｃ】
2005136971.tif 000013
【図５】
2005136971.tif 000014
【図６】
2005136971.tif 000015
【図７】
2005136971.tif 000016