(57)【特許請求の範囲】
【請求項１】
コンピュータネットワーク内における、第１のフラグを有する第１のネットワークエレメントから受信バッファおよび第２のフグを有する第２のネットワークエレメントへのデータ伝送の制御方法であって、
（ａ）前記第１のフラグの値が前記受信バッファがデータを受信するために使用可能であることを示す第１の値に等しい場合は、前記第１のネットワークエレメントから前記第２のネットワークエレメントへデータを伝送する段階と、
（ｂ）前記第１のフラグを、前記バッファがデータを受信するために使用可能でないことを示す第２の値に設定する段階と、
（ｃ）前記受信バッファ中にデータを受信する段階と、
（ｄ）前記受信バッファがデータの受信を完了し、前記受信バッファがデータを受信するために使用可能である場合、前記第２のフラグを前記第１の値に設定する段階と、
（ｅ）前記第２のフラグの値に等しい値を有する制御信号を発生する段階と、
（ｆ）前記制御信号を前記第２のネットワークから前記第１のネットワークに伝送する段階と、
（ｇ）前記第１のフラグを前記制御信号の値に等しく設定する段階と、を備えるデータ伝送の制御方法。
【請求項２】
さらに、
（ｈ）段階（ａ）から（ｇ）を繰り返す段階、
を含む請求項１に記載のデータ伝送の制御方法。
【請求項３】
コンピュータネットワークが、データ伝送エレメントによって決定される全ネットワークルーチング情報を有する発信元ノードルーチングネットワークである請求項１に記載のデータ伝送の制御方法。
【請求項４】
第１のネットワークエレメントおよび第２のネットワークエレメントがルータである請求項１に記載のデータ伝送の制御方法。
【請求項５】
前記段階（ｂ）が、
第１のレジスタを、前記第１のネットワークエレメントが前記第２のネットワークエレメントにデータ伝送を完了したが、データが前記第２のネットワークエレメントによって受信されたことを示す制御信号を受信しなかったことを示す第３の値に設定する段階と、
前記第１のレジスタが前記第３の値に等しいときに、前記第１のフラグを前記第２の値に設定する段階と、
をさらに含む請求項１に記載のデータ伝送の制御方法。
【請求項６】
前記段階（ｄ）が、
第２のレジスタを、前記第１のネットワークエレメントによって送信されたデータを前記第２のネットワークエレメントが受信したことを示す第４の値に設定する段階と、
第３のレジスタを、バッファがデータを受信するために使用可能であることを示す第５の値に設定する段階と、
前記第２のレジスタが前記第４の値に等しく、かつ前記第３のレジスタが前記第５の値に等しい場合は、前記第２のフラグを前記第１の値に設定する段階と、をさらに含む請求項１に記載のデータ伝送の制御方法。
【請求項７】
前記第３のレジスタを、バッファがデータを受信するために使用可能でないことを示す第６の値に設定する段階を、さらに含む請求項６に記載のデータ伝送の制御方法。
【請求項８】
前記第２のレジスタが前記第４の値に等しく、かつ前記第３の値が前記第６の値に等しい場合は、前記第２のフラグを前記第２の値に等しく設定する段階を、さらに含む請求項７に記載のデータ伝送の制御方法。
【請求項９】
前記段階（ｇ）が、
前記第２のフラグを、前記第２のフラグが前記第２の値に等しい場合は、前記第１のネットワークエレメントによって送信されたデータを前記第２のネットワークエレメントが受信したことを示す第８の値に設定する段階と、
前記第２のフラグが前記第２の値に等しい場合は、第４のレジスタを第７の値に設定する段階を、さらに含む請求項８に記載のデータ伝送の制御方法。
【請求項１０】
前記段階（ｆ）が、
前記第２のネットワークエレメント中のマルチプレクサの入力に前記制御信号を伝送する段階と、
前記第２のネットワークエレメントから前記第１のネットワークエレメントへ１つのデータも伝送されておらず、かつ前記制御信号が前記第２のネットワークエレメントから前記第１のネットワークエレメントに伝送されたデータよりも高プライオリティを有しているときには第３の値を有する第１の信号を発生する段階と、
前記第１の信号が前記第３の値を有する場合は、前記第２のネットワークエレメントから前記第１のネットワークエレメントに前記制御信号を伝送する段階と、
前記第１の信号が前記第３の値を有しない場合は、前記第２のネットワークエレメントから前記第１のネットワークエレメントに前記データを伝送する段階と、
をさらに含む請求項１に記載のデータ伝送の制御方法。
【請求項１１】
コンピュータネットワーク内における、第１のフラグを有する第１のネットワークエレメントから受信バッファおよび第２のフラグを有する第２のネットワークエレメントへのデータ伝送の制御方法であって、
（ａ）もし前記第１のフラグが前記受信バッファがデータを受信するために使用可能であることを示す第１の値に等しい場合は、前記第１のネットワークエレメントから前記第２のネットワークエレメントへデータを伝送する段階と、
（ｂ）前記第１のフラグを、前記バッファがデータを受信するために使用可能でないことを示す第２の値に設定する段階と、
（ｃ）前記受信バッファ中にデータを受信する段階と、
（ｄ）前記受信バッファがデータの受信を完了した場合は、前記第２のフラグを第２の値に設定する段階と、
（ｅ）前記第２のフラグの値に等しい値を有する制御信号を発生する段階と、
（ｆ）前記制御信号を前記第２のネットワークから前記第１のネットワークに伝送する段階と、
（ｇ）前記第１のフラグを前記制御信号の値に等しく設定する段階と、
（ｈ）前記第２のフラグが前記第２の値に等しく、かつバッファがデータを受信するために使用可能である場合は、前記第２のフラグを前記第１の値に設定する段階と、
（ｉ）前記第２のフラグの値に等しい値を有する前記制御信号を発生する段階と、
（ｊ）前記制御信号を前記第２のネットワークから前記第１のネットワークに伝送する段階と、
（ｋ）前記第１のフラグを前記制御信号の値に等しく設定する段階と、
からなるデータ伝送の制御方法。
【請求項１２】
さらに、
（ｌ）段階（ａ）から（ｋ）を繰り返す段階、
を含む請求項１１に記載のデータ伝送の制御方法。
【請求項１３】
コンピュータネットワークが、データ伝送エレメントによって決定される全ネットワークルーチング情報を有する発信元ノードルーチングネットワークである請求項１１に記載のデータ伝送の制御方法。
【請求項１４】
第１のネットワークエレメントおよび第２のネットワークエレメントがルータである請求項１１に記載のデータ伝送の制御方法。
【請求項１５】
前記段階（ｂ）が、
第１のレジスタを、前記第１のネットワークエレメントが前記第２のネットワークエレメントにデータ伝送を完了したが、データが前記第２のネットワークエレメントによって受信されたことを示す制御信号を受信しなかったことを示す第３の値に設定する段階と、
前記第１のレジスタが前記第３の値に等しいときに、前記第１のフラグを前記第２の値に設定する段階と、
をさらに含む請求項１１に記載のデータ伝送の制御方法。
【請求項１６】
コンピュータネットワーク内におけるデータ伝送制御システムであって、
第１のフラグを有する第１のネットワークと、
受信バッファと第２のフラグを有し、前記第１のネットワークに接続される第２にネットワークと、
を具備し、
前記第１のネットワークが、
前記第１のフラグの値が前記受信バッファがデータ受信のために使用可能であることを示す第１の値に等しい場合に、前記第１のネットワークからデータを伝送するための第１の伝送ユニットと、
第１のフラグを、バッファがデータを受信するために利用できない場合の第２の値とバッファがデータを受信するために利用できる場合の第１の値との一方に設定するための、前記伝送ユニットに接続される第１のバッファ状態ユニットと、
を含み、前記第２のネットワークが、
第１のネットワークから伝送されるデータを受信するための、前記伝送ユニットに接続される受信ユニットと、
受信バッファがデータ受信を完了し、受信バッファがデータを受信するために利用可能である場合に、前記第２のフラグを前記第１の値に設定するための、前記バッファに接続され、かつ前記受信エレメントに接続される第２のバッファ状態ユニットと、
前記第２のフラグの値に等しい値を有する制御信号を発生するための、前記第２のバッファ状態ユニットに接続される制御信号ジェネレータと、
前記第２のネットワークエレメントから前記第１のネットワークエレメントへ前記制御信号を伝送するための、前記制御信号ジェネレータに接続される第２の伝送ユニットと、
を含むデータ伝送制御システム。
【請求項１７】
前記コンピュータネットワークが、データ伝送エレメント中の全ネットワークルーチング情報を有する発信元ノードルーチングネットワークである請求項１６に記載のシステム。
【請求項１８】
前記第１のネットワークエレメントおよび前記第２のネットワークエレメントがルータである請求項１６に記載のシステム。
【発明の詳細な説明】
関連出願の相互参照
本願発明の主題は、下記に掲げる出願の主題と関連している。
出願番号＿＿＿＿＿、弁護士用ドケット番号２２６８、“非同期パケットスイッチング”の名称で、Ｔｈｏｍａｓ  Ｍ．Ｗｉｃｋｉ，Ｐａｔｒｉｃｋ  Ｊ．Ｈｅｌｌａｎｄ，Ｔａｋｅｓｈｉ  Ｓｈｉｍｉｚｕ，Ｗｏｌｆ−Ｄｉｅｔｒｉｃｈ  ＷｅｂｅｒおよびＷｉｎｆｒｉｅｄ  Ｗ．Ｗｉｌｃｋｅによって１９９６年２月２２日に出願、
出願番号＿＿＿＿＿、弁護士用ドケット番号２２６９、“ダイナミックなネットワーク・トポロジー探査のシステムおよび方法”の名称で、Ｔｈｏｍａｓ  Ｍ．Ｗｉｃｋｉ，Ｐａｔｒｉｃｋ  Ｊ．Ｈｅｌｌａｎｄ，Ｗｏｌｆ−Ｄｉｅｔｒｉｃｈ  ＷｅｂｅｒおよびＷｉｎｆｒｉｅｄ  Ｗ．Ｗｉｌｃｋｅによって１９９６年２月２２日に出願、
出願番号＿＿＿＿＿、弁護士用ドケット番号２２７０、“低い待ち時間，高いクロック周波数  プレジオ非同期  パケット基準  クロスバー・スイッチング・チップ・システムおよび方法”の名称で、Ｔｈｏｍａｓ  Ｍ．Ｗｉｃｋｉ，Ｊｅｆｆｒｅｙ  Ｄ．Ｌａｒｓｏｎ，Ａｌｂｅｒｔ  ＭｕおよびＲａｇｈｕ  Ｓａｓｔｒｙによって１９９６年２月２２日に出願、
出願番号＿＿＿＿＿、弁護士用ドケット番号２２７１、“パケットスイッチングネットワーク内のルーチングデバイス出力アクセス用調整装置および方法”の名称で、Ｊｅｆｆｒｅｙ  Ｄ．Ｌａｒｓｏｎ，Ａｌｂｅｒｔ  ＭｕおよびＴｈｏｍａｓ  Ｍ．Ｗｉｃｋｉ，によって１９９６年２月２２日に出願、
出願番号＿＿＿＿＿、弁護士用ドケット番号２２７２、“電圧の揺れを少なくし、かつ、内部のブロック化データパスを生じさせないクロスバースイッチおよびその方法”の名称で、Ａｌｂｅｒｔ  ＭｕおよびＪｅｆｆｒｅｙ  Ｄ．Ｌａｒｓｏｎによって１９９６年２月２２日に出願、
出願番号＿＿＿＿＿、弁護士用ドケット番号２２７５、“相互接続の障害検出およびその位置特定方法および装置”の名称で、Ｒａｇｈｕ  Ｓａｓｔｒｙ，Ｊｅｆｆｒｅｙ  Ｄ．Ｌａｒｓｏｎ，Ａｌｂｅｒｔ  Ｍｕ，Ｊｏｈｎ  Ｒ．Ｓｌｉｃｅ，Ｒｉｃｈａｒｄ  Ｌ．Ｓｃｈｏｂｅｒ，Ｊｒ．およびＴｈｏｍａｓ  Ｍ．Ｗｉｃｋｉによって１９９６年２月２２日に出願、
出願番号＿＿＿＿＿、弁護士用ドケット番号２２７７、“多重ワード通信におけるエラー検出方法および装置”の名称で、Ｔｈｏｍａｓ  Ｍ．Ｗｉｃｋｉ，Ｐａｔｒｉｃｋ  Ｊ．ＨｅｌｌａｎｄおよびＴａｋｅｓｈｉ  Ｓｈｉｍｉｚｕによって１９９６年２月２２日に出願、
出願番号＿＿＿＿＿、弁護士用ドケット番号２２７８、“正のソース帰還をそなえたクロック動作されるセンス増幅器”の名称で、Ａｌｂｅｒｔ  Ｍｕによって１９９６年２月２２日に出願、
参考として、上記の出願の全てを本願発明の全体に亘って取り入れている。
発明の背景
１．発明の分野
この発明は一般的にはネットワークデータ伝送の分野に係わり、特に分散型ネットワーク伝送プロトコルシステムおよび方法の分野に関する。
２．発明の背景の説明
コンピュータの端末（ノード）の間の効率的な信頼性のある情報の伝送に対しては種々の技術がある。このような１つの技術はパケットスイッチングである。パケットスイッチングにおいては、伝送（発信元）ノードはメッセージを（宛先）受信ノードに送信する。このメッセージは多数の可変サイズ部分に分割される。これらの部分はパケットと呼ばれる。各パケットはデータ部分、パケットヘッダおよびしばしば誤り検出情報、例えばパリティ情報を含む。データ部分は、ネットワーク中のより高いプロトコルレイヤ、例えばＯＳＩ参照モデルに記述されているようなアプリケーションレイヤ、プレゼンテイションレイヤ、セッションレイヤから他のプロトコル情報とともに送信されるべきメッセージ中の情報を含んでいる。パケットヘッダは、他の情報の間にパケットシーケンス中におけるパケットに位置に関する情報を含んでいる。
ネットワークのノード間でパケットを伝送するために、付加的な情報が要求される。この付加的な情報は、しばしばフレームヘッダ中に記憶される。フレームヘッダはパケットおよびパケットの結合に付加され、フレームヘッダはフレームと呼ばれる。各ネットワークはフレームのサイズを制限しているので、もしメッセージが単一のフレーム中に挿入するには大きすぎるときは、メッセージは２またはそれ以上のフレーム中に分離されることになる。フレームヘッダ中に含まれる情報はフレームに対する最終的な宛先ノードを識別するための情報を含んでいる。
フレームはルータを使用してネットワークを介して伝送される。例えば、フレームは第１のルータから第２のルータへ、第２のルータから第３のルータへ、そして第３のルータから宛先のノードへ伝送され得る。もし第１のルータにおける入力トラヒックの速度が第１のルータの最大フレーム伝送速度よりも大きければ、第１のルータ内のフレームバッファはいっぱいとなり、結局、第２のルータは第１のルータに一時的にデータの伝送を中止することを命令するか、受信されたフレームはバッファに以前に記憶されたフレームに上書きし、この上書きされたフレームは失われてしまうかのいずれかである。多くのシステムは、受信ルータ、例えば第２のルータが、伝送ルータに一時的に伝送を中止させる制御信号を伝送ルータに送信し得る伝送制御システムを採用する。
従来の伝送制御システムは、データフレームおよび制御信号の双方に対する単一の信号線または別個の制御信号線のいずれかを使用している。従来の伝送制御システムの例は、ＲＳ２３２伝送プロトコルである。ＲＳ２３２伝送プロトコルにおいて、伝送ネットワークエレメント、即ちルータは受信ネットワークエレメントに対してフレーム信号線を介してフレームを伝送する。もし受信ルータが伝送ルータにフレームの伝送を中止することを要求すれば、受信ルータは伝送オフ（ＸＯＦＦ）制御信号を発生し、フレーム信号線を介して伝送ルータにこの制御信号を送信する。
高周波数ネットワーク、例えば５００ＭＨｚにおいては、制御信号が伝送ルータに到達するために必要な時間はシステムに顕著な遅れをもたらす。特に、もし１本の信号線が受信ルータから伝送ルータへの制御信号の伝送に使用されたならば、もたらされる遅れは、ほぼ伝送ルータと受信ルータとの間の結合距離を伝播するために信号よって要求される時間に等しい。もし各クロックサイクルに対して１データビットが結合中の各信号線上に送信され、結合距離が約２メートル（２ｍ）であり、クロック周波数が５００ＭＨｚであれば、約３．３ビット（３．３ビット＝５００ＭＨｚ／３００ｋｍ／ｓ＊２ｍ）が、受信ルータが制御信号を送信する時間と伝送ルータが信号を受信する時間の間に伝送ルータによって各信号線上に送信される。さらに、信号線上に同数のビットが存在し、さらにＸＯＦＦ制御信号を伝送した後に約６．６ビットが受信ルータによって受信される。もし多数、例えば３２の信号線が接続上に存在すれば、伝送ルータに伝送の中止を命令した後に受信ルータによって約２１２ビット（６．６ビット＊３２信号線）が受信され得る。この２１２ビットは受信ルータ中のバッファに記憶されねばならず、そうでなければデータは失われるであろう。これらのビットを記憶するために、受信ルータはこれらのビットすべてを獲得するために余分のバッファを保持しなければならない。バッファは高価であり、バッファの非効率的な使用はネットワークの性能に対して重大な影響を有し得る。従って、少なくとも２１２ビットを記憶するために十分なバッファ領域を考慮しない設定は、システム資源の非効率的な使用である。この例においては、２１２バッファ領域は予約されており、受信ルータ中の残りのバッファ領域がいっぱいであるとき、データ受信ルータによるＸＯＦＦ制御信号の送信とデータ伝送ルータによるＸＯＦＦ制御信号の受信の間にデータ伝送ルータによって送信される全データを獲得し、バッファ領域に記憶することを確実にするために、受信ルータはＸＯＦＦ制御信号を伝送する。しかしながら、これら全ビットが必ずしもデータフレーム部ではない。しばしば、ビットのいくつかはデータフレームまたは制御信号が伝送されていないときにネットワークを介して伝送される“アイドル（idle）”ビットまたは他の“ガーベイジ（garbage）”ビットである。従って、これらのアイドルビットを記憶する必要はない。従って、アイドルビットが伝送されたときに、予約されたバッファ領域全部が使用されるわけではない。上述のように、バッファは高価であり、ＲＳ２３２伝送プロトコルはこれらのバッファの非効率的な使用となる。
ＲＳ２３２伝送プロトコルおよび１本の制御信号線を使用したときは、伝送ルータはＸＯＦＦ信号の受信後にデータ伝送を終了する。受信ルータにおいて十分なバッファが使用可能となれば、受信ルータは伝送オン（ＸＯＮ）信号を発生し、ＸＯＮ信号を伝送ルータに伝送する。ＸＯＮ信号の受信後に、伝送ルータはデータ伝送を再開するであろう。しかしながら、このシステムはＸＯＮ制御信号の伝送と第１のデータリンク受信との間の時間に等しいネットワーク内の遅れをもたらす。
もし、別個の制御信号線の代わりに、ネットワークがレシーバにより伝送される制御信号とトランスミッタにより伝送されるデータフレームの双方に対して一本のデータ線を使用するならば、受信ルータが制御信号を伝送するために伝送ルータは伝送を中止しなければならないので、システムの遅れはさらに増大する。従って信号が伝送ルータから受信ルータへ、そしてその逆方向に伝播するために必要な時間にほぼ等しい遅れ期間がネットワークに導入される。
必要なものは、（１）受信ルータ中のバッファを効率的に使用し、（２）制御信号によってもたらされるネットワーク遅れを最小とし、（３）制御信号の発生および伝送を強制可能であり、（４）同一のポートに伝送される他のフレームに制御信号を重畳し、（５）強い、即ち伝送誤りの回復が可能であり、（６）多重プライオリティレベル伝送フレームに適用可能であり、（７）レシーバ中のバッファ資源に対して適用可能なフロー制御プロトコルシステムおよび方法である。
発明の概要
本発明は、２つのネットワークエレメント間のデータ伝送の制御システムおよび方法である。伝送エレメントの第１のポートは、受信エレメントの第２のポートに接続される。第２のポートは、データが他のエレメントに伝送され得るまで一時的に伝送されたデータを記憶するためのバッファを含んでいる。方法は、受信エレメント中に、受信現状充満レジスタ（ＲＣＦＲ）、送信非受信レジスタ（ＳＡＮＲＲ）、バッファビジーレジスタ（ＢＢＲ）を含んでいる。伝送エレメントは受信エレメント中のバッファが使用可能であるかを決定するために、ＢＢＲを検査する。バッファの使用可能性は単一プライオリティプロトコルまたは多重プライオリティプロトコルを使用して決定され得る。もしバッファが使用可能であれば、伝送エレメントはデータフレームを受信エレメントに伝送し、フレームが伝送されたこと（そして確認は受信されていないこと）、選択されたバッファはいっぱいであること、およびバッファが空となるまでこのバッファには付加的なデータフレームは伝送されるべきではないことを示すためにＳＡＮＲＲおよびＢＢＲを設定する。
データが受信エレメントで受信されたとき、これは使用可能なバッファに伝送される。データがバッファによって受信されたとき、受信エレメントは、現状充満レジスタ（ＣＦＲ）中のビットおよび送信次メッセージレジスタ（ＮＭＴＳＲ）のビットを設定する。各ビットはバッファに関連づけられている。ＣＦＲ中の各ビットは関連バッファが空であるかを示す。制御信号、即ちバッファ状態メッセージ間で常時ＣＦＲが空でないならば、制御信号が伝送されたときに、仮にバッファが空であってもＮＭＴＳＲは設定されリセットされないという例外のもとに、ＮＭＴＳＲ中の各ビットは、前回の制御信号が伝送された時のＣＦＲレジスタの値を示す。制御信号は、ＮＭＴＳＲだけ、またはＮＭＴＳＲとＣＦＲの双方を含み得る。制御信号は、データ受信エレメントからデータ伝送エレメントに送信されるデータのように同一の信号線上に伝送される。データ受信エレメントは、同一の方向に送信されるフレームを制御信号に多重化することができる。
伝送エレメントが制御信号を受信したときに、ビットがＳＡＮＲＲ中で設定されたならば、そして制御信号のＮＭＴＳＲ部中の関連するビットが設定されたならば、伝送エレメントはＳＡＮＲＲ中のバッファに関連するビットをリセットする。ＲＣＦＲの値は、制御信号中のＣＦＲまたはＮＭＴＳＲのいずれかの値に等しく設定される。従って、伝送エレメントは、ＢＢＲ中の関連するビットの値をＳＡＮＲＲおよびＲＣＦＲの論理的ＯＲに等しく設定する。伝送エレメントは、データプライオリティの制限を条件としてＢＢＲによって示される受信エレメントにおいてバッファが使用可能であるときだけ、データを送信する、即ち伝送エレメントは、バッファが空であり、ＲＣＦＲがクリアされるまでデータを伝送しないであろう。
【図面の簡単な説明】
図１は、本発明の望ましい実施例による、ノード、ルータおよびリンクを含むネットワークの図である。
図２は、本発明の望ましい実施例による図１に描かれたネットワーク内の２つのルータの詳細図である。
図３は、本発明の望ましい実施例による図１に描かれたルータのより詳細な図である。
図４は、本発明の望ましい実施例によるデータ受信ルータ内の２つのレジスタを表す値を含むバッファ状態メッセージに応答するデータ伝送ルータ内のバッファの状態を示す状態線図である。
図５は、本発明の第２の実施例によるデータ受信ルータ中の１つのレジスタを表す値を含むバッファ状態メッセージに応答するデータ伝送ルータ内のバッファの状態を示す状態線図である。
図６は、本発明の望ましい実施例による伝送プロトコル技術のフロー線図である。
図７は、本発明の望ましい実施例によるバッファ状態メッセージ発生、伝送技術のフロー線図である。
図８は、本発明の望ましい実施例によるバッファ状態メッセージ受信技術のフロー線図である。
図９（ａ）−９（ｇ）は、本発明の望ましい実施例によるレジスタの値の例である。
望ましい実施例の詳細な説明
本発明の望ましい実施例は、図面を参照しつつ以下に説明されるが、同一の参照符号は同一のまたは機能的に同一のエレメントを表す。また図において、各参照符号の左側の数字は、その参照符号が最初に使用された図に対応する。
本発明は、（１）受信ルータ中のバッファを効率的に使用し、（２）制御信号によってもたらされるネットワーク遅れを最小とし、（３）制御信号の発生および伝送を強制することが可能であり、（４）同一ポートに伝送される他のデータフレームに制御信号を多重化し、（５）強い、即ち伝送誤りを回復することができ、（６）多重プレイオリティレベル伝送フレームに適用可能であり、（７）レシーバ中のバッファ資源装備に適用可能であるフロー制御プロトコルシステムおよび方法である。
図１は、本発明のノード、ルータおよびリンクを含むネットワークを示している。図１に示されているネットワークは８つのノード１０２、即ちＮｏｄｅＡ−Ｈ１０２Ａ−Ｈ、および７つのルータ１０４Ａ−Ｇを含んでいる。本発明の望ましい実施例によれば、ネットワークは分散メモリシステムである。即ち、このシステムは物理的に分散されているアーキテクチャを有しているが、メモリ（記憶素子）は論理的に共有されている。例えば、１つのノード、例えば１０２ＤはＮｏｄｅＤ１０２Ｄが局所的であるが実際物理的に異なる場所に配置され、異なるノード、例えばＮｏｄｅＡ１０２Ａに接続されていると信じるメモリ位置にアクセスをリクエストすることができる。リクエストしたノード（ＮｏｄｅＤ１０２Ｄ）はメモリの位置を認識し、ネットワークは迅速にデータを取り出す。分散されたメモリネットワークにおいて、重要な性能パラメータはネットワークの待ち時間である。ネットワークの待ち時間は、メモリリクエストが転送された時間から計測され、リクエストされたデータをリクエストノードに提供するために必要とされる時間である。
もしＮｏｄｅＤ１０２ＤがＮｏｄｅＡ１０２Ａ中に記憶されているデータを要求したならば、ＮｏｄｅＤ１０２Ｄはネットワークを介してデータリクエストを転送する。データリクエストは、例えばＮｏｄｅＤ１０２Ｄから第３のルータ１０４Ｅ、第２のルータ１０４Ｂ、第１のルータ１０４Ａを介してＮｏｄｅＡ１０２Ａに移動する。データはＮｏｄｅＡ１０２Ａに接続される記憶素子から取り出され、ＮｏｄｅＤ１０２Ｄにネットワークを介して送信される。上述のように、データはパケットとしてネットワークを介して送信される。ノード、例えばＮｏｄｅＡ１０２Ａはネットワークを介する通信路を決定し、このルーチング情報を各パケットのヘッダ中に記憶する。例えば、ＮｏｄｅＡ１０２ＡからＮｏｄｅＤ１０２Ｄに送信されるデータは、ＮｏｄｅＡ１０２Ａから第１のルータ１０４Ａへ、そして第１のルータ１０４Ａから第２のルータ１０４Ｂへ、第２のルータ１０４Ｂから第３のルータ１０４Ｅへ、そして第３のルータ１０４ＥからＮｏｄｅＤ１０２Ｄに送信するよう各パケットに指示するルーチング情報を有することができる。ネットワークの待ち時間はデータリクエストを送信するリクエストノードからデータを受信するリクエストノードの間の時間間隔であるので、各ルータ１０４によってもたらされる遅れの低減はネットワークの待ち時間を低減する。上述したように、各ルータ１０４は受信されるべきデータを一時的に記憶するためのバッファを含んでいる。ある実施例においては、ルータのポート当たり６つのバッファが存在し、ルータ上に６つのポートが存在する。各バッファの大きさは、最大パケット長さ、例えば１２９２ビットに等しい。しかしながら、上述のようにルータ１０４を設計したときに、価格は重要な考慮点である。各ルータ内でバッファの数の増加は高価なものであり、バッファが存在する集積回路上に大きさの制限があるのである状況においては不可能である。
ルータは相互に２重信号ライン１０６によって接続されている。各２重信号線１０６Ａは双方向への、即ち、第１のルータ１０４Ａの第２のポートから第１のルータ１０４Ａの第２のポートへのデータの同時転送を可能としている。２重信号線１０６Ａは、図２を参照しつつ以下により詳細に説明される。
図２は、図１に示されたネットワークにおける本発明の望ましい実施例にかかる２つのルータ１０４のより詳細な図である。２重信号線１０６Ａは、２つの信号線２１０、２１２によって表されている。各信号線は一方向性である。第１の信号線２１０は、第１のルータ１０４Ａのポート２  ２０２Ａから第２のルータ１０４Ｂのポート６  ２０２Ｂへ情報を転送する。第２の信号線２１２は、第２のルータ１０４Ｂのポート６  ２０２Ｂから第１のルータ１０４Ａのポート２  ２０２Ａへ情報を転送する。望ましい実施例において、各図示された信号線２１０、２１２は、ポート間でデータを並列に転送する４３本の信号線を含んでいる。各ルータ１０４は、それぞれがクロスバースイッチ２０６に接続される６つのポート２０２を含んでいる。さらに、各ポートは６つのアービタ２０４、即ちＡ１−Ａ６に接続され、各アービタ２０４はポートの１つの出力部と関連付けられている。例えば、第１のルータ１０４Ａ上のアービタ２  ２０４Ａは、ポート２  ２０２Ａの出力部に接続されている。ポート２  ２０２Ａの出力部は信号線２１０に接続されている。図２に示すように、各ポート、例えば第１のルータ１０４Ａのポート２  ２０２Ａおよび第２のルータ１０４Ｂのポート６  ２０２Ｂは、異なるルータ内の１つのポートだけに接続される。例えば、第１のルータ１０４Ａのポート２  ２０２Ａは第２のルータ１０４Ｂのポート６  ２０２Ｂに接続されて、第１のルータ１０４Ａのポート２  ２０２Ａは第２のルータ１０４Ｂのポート６  ２０２Ｂからのデータだけを受信し、第２のルータ１０４Ｂのポート６  ２０２Ｂへだけデータを転送し、第２のルータ１０４Ｂのポート６  ２０２Ｂは第１のルータ１０４Ａのポート２  ２０２Ａからのデータだけを受信し、第１のルータ１０４Ａのポート６  ２０２Ａへだけデータを転送する。アービタ２０４、クロスバースイッチ２０６およびポート２０２の動作は、図３−９を参照して以下により詳細に説明さされる。
図３は図１および２に図示された本発明の望ましい実施例にかかる第１のルータ１０４Ａおよび第２のルータ１０４Ｂのより詳細な図である。各ルータ１０４内の各ポート２０２はフロー制御レシーバ３０４、バッファアレイ３２２、変更ユニット３２６、マルチプレクサ（ＭＵＸ）３２８、データシンクロナイザ３２４、およびフロー制御トランスミッタ３０５を含んでいる。各フロー制御レシーバ３０４は、送信用非受信レジスタ（ＳＡＮＲＲ）３０８、受信現状充満レジスタ（ＲＣＦＲ）３１０およびバッファビジーレジスタ（ＢＢＲ）３１２に接続されるバッファ状態メッセージ（ＢＳＭ）レシーバ３０６を含んでいる。各フロー接続トランスミッタ３０５は次回送信メッセージレジスタ（ＮＭＴＳＲ）３１８および現状充満レジスタ（ＣＦＲ）３２０に接続されたＢＳＭジェネレータ３１６を含んでいる。ルータ１０４を参照して説明されているけれども、各ノード１０２もまたフロー制御レシーバ３０４Ａおよびフロー制御トランスミッタ３０５Ｂ中にレジスタを含んでいる。これらポート要素の動作は、上述のデータ転送例を参照して今から説明される。
もしＮｏｄｅＤ１０２ＤがＮｏｄｅＡ１０２Ａによって制御されるメモリ素子中に記憶されたデータをリクエストした場合は、ＮｏｄｅＤ１０２ＤはＮｏｄｅＡ１０２Ａに要求を転送する。ＮｏｄｅＡ１０２Ａはデータを取り出し、データパケットがネットワークを通過する通信路を決定し、上述したように各パケットのヘッダ中にこのルーチング情報を記憶する。第１のルータ１０４Ａは、ＮｏｄｅＡ１０２Ａからパケットの形式でデータを受信する。ＮｏｄｅＡ１０２Ａは、第１のルータ１０４Ａのポート３に接続される。従って、各フレームは、ポート３バッファアレイ３２２Ａ中のバッファに送信される。フレームヘッダ中のルーチング情報は、データがトラバース（traverse）すべき次のルータ９１０４を認識する。本実施例において、次のルータは第２のルータ１０４Ｂである。第１のルータ１０４Ａのポート２  ２０２Ａは、第２のルータ１０４Ｂのポート６  ２０２Ｂに接続される。従ってフレームヘッダ中のルーチング情報は、第１のルータ１０４Ａに対する出力ポートとしてポート２  ２０２Ａを認識する。この出力ポート情報は出力ポートに関連したアービタ２０４によって受信される。本実施例において、アービタ２  ２０４Ａは第１のルータ１０４Ａのポート２  ２０２Ａと関連付けられる。アービタ２  ２０４Ａはフロー制御レシーバ３０４Ａから受信ポートへのデータ伝送が実行されるかを示す信号を受信する。本実施例において、受信ポートは、第２のルータ１０４Ｂのポート６  ２０２Ｂである。そして、アービタ２  ２０４Ａは、ポート３バッファアレイ３２２Ａ中の第１のバッファに第１のバッファ中のデータをクロスバーマトリックス２０６に送信することをポート３のバッファアレイ３２２Ａに命令する信号を伝送する。アービタ２  ２０４Ａはまた、クロスバーマトリックス２０６にポート３バッファアレイ３２２Ａ中の第１のバッファを第１のルータ１０４Ａのポート２  ２０２Ａに接続させる信号をクロスバーマトリックス９０６に送信する。各アービタ２０４の動作は、全体として参照によって識別され組み込まれる１９９６年２月２２日にＪｅｆｆｒｅｙ  Ｄ．Ｌａｒｓｏｎ、Ａｌｂｅｒｔ  ＭｕおよびＴｈｏｍａｓ  Ｍ．Ｗｉｃｋｉによって出願された“パケットスイッチングネットワーク内のルーチングデバイス出力アクセス用調整方法および装置”と名付けられた系属中の特許出願により詳細に記述されている。同様に、各クロスバーマトリックス９２０６の動作は、全体として参照によって識別され組み込まれる１９９６年２月２２日にＡｌｂｅｒｔ  ＭｕおよびＪｅｆｆｒｅｙ  Ｄ．Ｌａｒｓｏｎによって出願された“電圧の揺れを少なくし、かつ、内部のブロック化データパスを生じさせないクロスバースイッチおよびその方法”と名付けられた系属中の特許出願により詳細に記述されている。
受信ポート（第２のルータ１０４Ｂのポート６  ２０２Ｂ）へのデータ伝送を実行し得るかを示すアービタ２  ２０４Ａへの信号の送信前に、フロー制御レシーバ３０４Ａは、変更ユニット３２６Ａにポート６バッファアレイ３２２Ｂ中の空のバッファ（受信バッファ）のアドレスを識別する信号を伝送する。フロー制御レシーバ３０４Ａ中のＢＢＲ３１２Ａは、第２のルータ１０４Ｂのポート６バッファアレイ３２２Ｂ中の各バッファに対する１ビットを含んでいる。ＢＢＲ３１２Ａ中の各ビットの値は、第２のルータ１０４Ｂのポート６バッファアレイ３２２Ｂ中の関連するバッファが空であることを第１のルータ１０４Ａが決定したかを示す。ＢＢＲ３１２Ａ中のビットをセットおよびリセットする方法は、図４−９を参照して以下に説明される。第１のルータ１０４Ａ中の変更ユニット３２６Ａは、第２のルータ１０４Ｂのポート６バッファアレイ３２２Ｂ中の空のバッファのアドレスを受信する。この空のバッファは受信バッファである。
アービタ２  ２０４Ａがクロスバースイッチ２０６Ａにポート３バッファアレイ３２２Ａ内の第１のバッファを変更ユニット３２６に接続することを命令したときに、アービタ２  ２０４Ａはまた、フロー接続レシーバ３０４Ａにフレームが伝送されたことを通知する信号をフロー制御レシーバ３０４Ａに送信する。パケットが受信バッファに転送されたこと、およびＳＢＭレシーバ３０６Ａがパケットの受信を認める信号を受信していないことを示すために、フロー制御レシーバ３０４Ａ中のＢＳＭレシーバ３０６Ａはポート６バッファアレイ３２２Ｂ中の受信バッファに関連するＳＡＮＲＲ３０８Ａ中のビットの値を変更する。以下に説明するように、ＢＢＲ３１２の値はＳＡＮＲＲ３０８ＡとＣＦＲ９３１０Ａの論理的ＯＲと等しい。ポート６バッファアレイ３２２Ｂ中の受信バッファに関連するビットの値は論理１に等しく設定されるので、ＢＢＲ３１２Ａ中の関連ビットもまた論理１に等しく設定される。このビットが論理１に等しいとき、ＢＢＲ９３１２Ａ中のこのビットがリセットされるまでフロー制御レシーバ３０４Ａから第１のルータ１０４Ａの変更ユニット３２６Ａに送信されるバッファアドレス信号は受信バッファを識別しない、即ちＢＢＲ３１２Ａがリセットされるまで受信バッファは“ビジー”として認識される。ポート６バッファアレイ３２２Ｂ中のすべてのバッファが、最近のＢＳＭ中の情報によって決定されたように、あるいは第１のルータ１０４Ａがパケットを第２のルータに転送したときにＳＡＮＲＲ３０８ＡとＢＢＲ３１２Ａの設定によるフロー制御レシーバ３０４Ａによって決定されるように空でなければ、ＢＢＲ３１２Ａ中の全ビットは論理１に等しく設定されるであろう。このような状況において、ＢＳＭレシーバ３０６Ａはアービタ２  ２０４Ａに通知し、ＢＢＲ３１２Ａ中の少なくとも１つのビットがリセットされるまでアービタ２  ２０４Ａはポート６  ２０２Ｂへのいかなる追加のパケット転送を許容しない。上記の説明は全パケットに対して単一の伝送プライオリティレベルだけが存在する状況を説明している。以下に説明するように、本発明は多重伝送プライオリティレベルを有するパケットをもサポートしている。
変更ユニット３２６Ａは、ポート３バッファアレイ３２２Ａからクロスバースイッチ２０６Ａを介してフレームを受信し、フロー制御レシーバ３０４Ａから受信バッファアドレスを受信する。変更ユニット３２６Ａは、第２のルータ１０４Ｂのポート２  ２０２Ａを識別するルーチング情報を削除することによってフレームヘッダを変更し、例えばフレームヘッダ中の残存するルーチング情報をシフトする。変更ユニット３２６Ａは、またフレームヘッダに受信バッファアドレスを加算する。変更ユニット３２６Ａは、２重信号線１０６Ａの信号線２１０を介して第２のルータ１０４Ｂにパケットを転送するＭＵＸ３２８Ａにパケットを転送する。
第２のルータ１０４Ｂ中のデーターシンクロナイザ３２４Ｂは、第１のルータ１０４Ａのポート２  ２０２Ａからデータを受信する。各ルータ１０４はクロック（図示せず）を含んでいる。データーシンクロナイザ３２４Ｂの１つの機能は、受信データを第２のルータ１０４Ｂ中の内部クロックと同期させることである。データーシンクロナイザ３２４Ｂの他の機能は、データパケットとデータ／状態制御信号を使用して第１のルータ１０４Ａから受信されるバッファ状態メッセージを区別することである。フレームヘッダ受信後、第２のルータは上述の方法によって第３のルータ１０４Ｅへの伝送を開始することができる。しかしながら、第３のルータ９１０４Ｅ中のポート４バッファアレイ中の全バッファが空でなければ、第２のルータ９１０４Ｂはポート６バッファアレイ９３２２Ｂ内に第１のルータ９１０４Ａから受信したデータの記憶を継続する。
データがポート６バッファアレイ３２２Ｂ内の受信バッファによって受信されたとき、ＢＳＭトランスミッタ３０５Ｂ中のＢＳＭジェネレータ３１６Ｂに通知される。フレームの一部が受信バッファによって受信されたことを示すために、ＢＳＭジェネレータ３１６Ｂは受信バッファに関連するＮＭＴＳＲ３１８Ｂ内のビットを論理１にセットする。さらに、受信バッファは空ではないことを示すために、ＢＳＭジェネレータ３１６ＢはＣＦＲ３２０Ｂ内の関連するビットを論理１にセットする。ＢＳＭトランスミッタ３０５ＢはＢＳＭを発生し、転送する。ＢＳＭの内容は図４−９を参照して以下に説明される。ＢＳＭは第１のルータ１０４Ａによって送信されたフレームが受信されたという確認を含み、またポート６バッファアレイ中のバッファの状態、即ち各バッファが空であるか否かの表示を含む。ＢＳＭジェネレータ３１６Ｂは第２のルータ１０４Ｂ内のＭＵＸ３２８Ｂの入力ポートにデータを伝送する。さらに、ＢＳＭジェネレータ３１６ＢはＢＳＭが第１のルータ１０４Ａに転送されることをリクエストする信号をアービタ６  ２０４Ｂに転送することができる。アービタ６  ２０４ＢはＭＵＸ３２８Ｂを制御する信号を発生する。この信号がアービタ６  ２０４Ｂによって送信されると、ＢＳＭが信号線２１２を介して第１のルータ１０４Ａのポート２  ２０２Ａに送信される。
ポート２  ２０２Ａ中のデータシンクロナイザ３２４Ａは、ＢＳＭを受信する。データシンクロナイザ３２４Ａは受信されたデータがＢＳＭであるかを決定し、フロー制御レシーバ３０４Ａ中のＢＳＭレシーバ３０６Ａにデータを送信する。フロー制御レシーバ３０４Ａは、受信されたＢＳＭに基づいてＳＡＮＲＲ３０８Ａ、ＲＣＦＲ３１０ＡおよびＢＢＲ３１２Ａを更新する。上述したように、これらのレジスタ中のビット値はＢＳＭレシーバ３０６Ａによって受信される。ＢＳＭレシーバ３０６Ａは、さらなるパケットが第２のルータ１０４Ｂのポート６  ２０２Ｂに送信され得るかを決定する。フロー制御レシーバ３０４Ａおよびフロー制御トランスミッタ３０５Ｂの動作は、図４−９を参照して以下にさらに詳細に記述される。
図４は、本発明の望ましい実施例による第２のルータ１０４Ｂ中のフロー制御トランスミッタ３０５Ｂ中のＮＭＴＲ３１８ＢおよびＣＦＲ３２０Ｂの双方を表す値を含むＢＳＭに応答する第１のルータ１０４Ａ中のフロー制御レシーバ３０４Ａ中のバッファの状態を描いた状態図である。本発明のフロー制御プロトコルの利点はそれが強いことである。即ち、フロー制御プロトコルは送信誤り、例えば失われたＢＳＭまたは失われたデータフレームを回復することが可能である。フレームが第１のルータ１０４Ａから第２のルータ１０４Ｂに転送されたときに、本発明に係るフロー制御プロトコルは５つのレジスタを利用する。これらのレジスタは、第１のルータ１０４Ａ中のフロー制御レシーバ３０４Ａ中のＳＡＮＲＲ３０８Ａ、ＲＣＦＲ３１０ＡおよびＢＢＲ３１２Ａならびに第２のルータ１０４Ｂ中のフロー制御トランスミッタ３０５Ｂ中のＮＭＴＳＲ３１８ＢおよびＣＦＲ３２０Ｂである。フロー制御プロトコルに関する以下の記述は、これら５つのレジスタを参照するであろう。上述したように、これら５つのレジスタのそれぞれはポート６バッファアレイ３２２Ｂ中の各バッファに関連したビットを含んでいる。１つの望ましい実施例において、ポート６バッファアレイ３２２Ｂは６つのバッファを含んでいる。図４および図５はこれら５つのレジスタのそれぞれの中の１ビットに対する状態線図を示す。従って、単一のバッファに対するフロー制御プロトコルがここに示されている。
ネットワークが初期化されたときに、フロー制御レシーバ３０４Ａ中のレジスタは状態IIIに関連した値に初期化される。即ちＲＣＦＲ＝１、ＳＡＮＲＲ＝０およびＢＢＲ＝１である。上述のように、ＢＳＭレシーバ３０６ＡはＢＢＲ３１２Ａの値をＲＤＦＲ３１０ＡとＳＡＮＲＲ３０８Ａの論理的ＯＲに等しく設定する。フロー制御レシーバレジスタ、即ちＳＡＮＲＲ３０８Ａ、ＲＣＦＲ３１０ＡおよびＢＢＲ３１２Ａは、それが最も保守的なフロー制御推定であるので、状態IIIに示された値に設定される。即ち、フロー制御レシーバレジスタが状態IIIにあるとき、状態IIIにあるときはＢＢＲ３１２Ａが受信バッファが空でないことを示す論理１に等しく設定されるので、フロー制御レシーバ３０４Ａはあらゆるデータが第２のルータ１０４Ａのポート６  ２０２Ｂに送信されることを防止する。以下に説明するように、もし受信バッファが空であれば、フロー制御プロトコルはフロー制御レシーバレジスタの状態を適切な状態を示すために変更する。上述のように、ＢＳＭはＮＭＴＳＲ３１８ＢおよびＣＦＲ３２０Ｂ内のビット値を含んでいる。この例に対して、ＢＳＭ＝１，０は、受信バッファに関連するＮＭＴＳＲ３１８Ｂ中のビットは論理１に等しい値を有し、受信バッファに関連するＣＦＲ３２０Ｂ中のビットは論理零に等しい値を有していることを示す。状態IIから状態IIIへ遷移後は、許容される２つのＢＳＭ値、即ちＢＳＭ＝１，１およびＢＳＭ＝１，０だけが存在する。この理由は、ＮＭＴＳＲ３１８Ｂは、（１）前回のＢＳＭで伝送されたＣＦＲ３２０Ｂの値、または（２）前回のＢＳＭ内のＣＦＲ３２０Ｂ中の関連するビットの値にかかわらずフレームが受信バッファによって受信されたときは少なくとも１つのＢＳＭに対する論理１のいずれかであるからである。状態IIIにあるときは、最後のＢＳＭ内のＣＦＲ３２０Ｂの値は論理１に等しいが、これはＲＣＦＲ３１０Ａがこの値を記憶するからである。従って次のＢＳＭ内のＮＭＴＳＲ３１８Ｂの値は、上記（１）および（２）に基づいて論理１に等しくなければならない。しかしながら、初期化手続の結果レジスタが状態IIIにあれば、ＢＳＭ＝０，０は有効であり、フロー制御レシーバ３０４Ａ中のレジスタを状態IIIから状態Ｉに遷移させる。
ＢＳＭ＝１，１は受信バッファが空ではないことを示す。従って、もしＢＳＭ＝１，１がフロー制御レシーバ３０４Ａによって受信されたならば、フロー制御レシーバ３０４Ａ内のレジスタは同一状態を維持する。ＢＳＭ＝１，０はフレームがポート６バッファアレイ３２２Ｂ内の受信バッファによって受信されたこと、第３のルータ１０４Ｅに伝送されたことを示す。従って、受信バッファは現在空である。もしＢＳＭ＝１，０が受信されれば、フロー制御レシーバ３０４Ａ内のレジスタは状態IIIから状態Ｉに遷移する。
状態Ｉにおいて、ＳＡＮＲＲ３０８Ａ、ＲＣＦＲ３１０ＡおよびＢＢＲ３１２Ａはすべて論理零に等しい。ＢＢＲ３１２Ａが論理零に等しいので、フロー制御レシーバ３０４Ａはアービタ２  ２０４Ａに受信バッファが空であることを通知する。以下に説明されるプライオリティの制限によって、フレームがポート３  ２０２Ａにおいて第２のルータ１０４Ｂのポート６  ２０２Ｂに伝送されることが可能であれば、アービタ２  ２０４Ａは、クロスバーマトリックス２０６Ａに対してポート３バッファアレイ３２２Ａ中の伝送バッファをポート２  ２０２Ａの変更ユニット３２６Ａに接続することを命じる。上述したように、アービタ２  ２０４Ａは、フロー制御レシーバ３０４Ａにデータは送信されていることを伝える信号もフロー制御レシーバ３０４Ａに伝送する。このとき、ＢＳＭレシーバ３０６ＡはＳＡＮＲＲ３０８Ａを論理１に等しく設定し、従ってＢＢＲ３１２Ｂを論理１に設定する。ＲＣＦＲ３１０Ａは変更されない。従って、データが第２のルータ１０４Ｂに伝送されたならば、フロー制御レシーバ３０４Ａ中のレジスタは状態IIに遷移する。状態Ｉである間にデータが送信されなければ、フロー制御レシーバ３０４Ａ中のレジスタは状態Ｉに維持される。
状態IIにおいて、ＳＡＮＲＲ３０８ＡおよびＢＢＲ３１２Ａが論理１に等しければ、ＲＣＦＲ３１０Ａは論理零に等しい。この状態において、フロー制御レシーバ３０４Ａ中のレジスタは、フレームがポート６バッファアレイ３２２Ｂ中の受信バッファに送信されたがフロー制御レシーバ３０４Ａは受信バッファがＢＳＭを介してフレームを受信した確認を受信していないことを示す。さらに、ＲＣＦＲ３１０Ａは最新のＢＳＭに基づき受信バッファが空であることを示す論理零に等しい。状態IIにあるとき、フロー制御レシーバ３０４Ａは、他のフレームが受信バッファに送信されることを許容しないであろう。もしＢＳＭ＝０，０が受信されれば、ＢＳＭは以前のＢＳＭが伝送されて以来データは受信バッファ内に受信されていないことを示すので、フロー制御レシーバ３０４Ａ中のレジスタは状態IIを維持する。もしＢＳＭ＝１，１が受信されれば、フロー制御レシーバ３０４Ａ中のレジスタは状態IIIに遷移する。ＢＳＭ＝１，１はいくらかのフレームデータが受信レジスタによって受信され、受信レジスタは空ではないことを示している。いくらかのフレームデータが受信されたので、ＳＡＮＲＲ３０８Ａは論理零にリセットされる。受信バッファが空なでのでＲＣＦＲ３１０Ａは論理１に設定される。状態IIIについての説明は、上記に与えられている。もしＢＳＭ＝１，０が受信されれば、フロー制御レシーバ３０４Ａ中のレジスタは状態Ｉに遷移する。状態IIにあれば、ＢＳＭ＝１，０はフレームデータは受信バッファによって受信されたこと、およびフレームはすでに第３のルータ１０４Ｅに伝送されたことを示す。従って、受信バッファは空である。フレームが受信バッファによって受信されたので、ＳＡＮＲＲ３０８Ａはリセットされる。受信バッファは空であるので、ＲＣＦＲ３１０Ａは論理零に等しく維持される。上述のように、状態Ｉにあるときは、フロー制御レシーバ３０４Ａはアービタ２  ２０４Ａに新しいフレームをポート６バッファアレイ３２２Ｂ中の受信バッファに伝送することを命令することができる。
上述したように、本発明に係るフロー制御プロトコル装置および方法は強い。即ち、プロトコルは伝送誤りを回復することができる。フロー制御プロトコルの時間切れ特徴は、ネットワークにＢＳＭまたはフレーム伝送誤りがなければバッファアレイ３２２中の利用可能なバッファの数を低減することができるフレーム伝送誤りを回復することを可能とする。フロー制御レシーバ３０４Ａ中のレジスタが状態IIにあり、第２のルータ１０４Ｂ内のフロー制御トランスミッタ３０５Ｂが、例えばＢ＝１，０を発生すれば、フロー制御レシーバ３０４Ａ中のレジスタは状態Ｉに遷移し、受信バッファは上述したように付加的なパケットを受信することが可能となる。しかしながら、ＢＳＭがフロー制御レシーバ３０４Ａによって受信されなかったならば、問題が発生する。フロー制御レシーバ３０４Ａ中のレジスタは状態IIにあるが、フロー制御トランスミッタ３０５Ｂはフロー制御レシーバ３０４Ａ中のレジスタは状態Ｉにあると考える。即ち、フロー制御トランスミッタ３０５Ｂは受信バッファが伝送されたフレームを受信したことおよび受信バッファが付加的なフレームを受信することが可能であることを示すＢＳＭ（ＢＳＭ＝１，０）を発生し、伝送した。受信バッファは空であり、新しいフレームが送信されないので、フロー制御トランスミッタ３０５ＢはＢＳＭ＝０，０に等しいＢＳＭだけを発生する。フロー制御レシーバ３０４Ａ中のレジスタは状態IIにあるので、ＢＳＭ＝０，０はこれらのレジスタの状態を変更しないであろう。従って、第１のルータ１０４Ａ中のフロー制御レシーバ３０４Ａは最早受信バッファを使用しないであろう。同様に、もし第１のルータ１０４Ａから伝送されたフレームが第２のルータ１０４Ｂによって受信されなければ、フロー制御レシーバ３０４Ａ中のレジスタは状態IIにあるが、第２のルータ１０４Ｂ中のフロー制御トランスミッタ３０５Ｂは、フレームが受信されなかったことを示すＢＳＭ＝０，０に等しいＢＳＭだけを発生する。
上述したように、バッファは高価な貴重な資源である。１つのバッファの喪失はネットワークの効率を低減する。本発明に係るフロー制御プロトコルは、バッファの喪失を避けるために時間切れ機構を導入する。時間切れ機構は、フロー制御レシーバ３０４Ａ中のレジスタが状態IIにある間に予め定めた最小量のクロックサイクルが発生したかを決定する。もし少なくともこの最小時間長の間レジスタが状態IIにあれば、フロー制御レシーバ３０４Ａはこのレジスタを状態Ｉにリセットし、誤りが発生したことを識別するために誤りカウンタ（図示せず）をインクリメントする。予め定められた数のクロックサイクルが発生したかを決定する１つの技術は、各バッファアレイ３２２中の各バッファに対するカウンタを使用することである。例えば、カウンタが受信バッファに対して満期となれば、フロー制御レシーバ３０４Ａはそのレジスタを状態IIから状態Ｉに遷移する。しかしながら、各カウンタに要求されるビット数は約１０または１１ビットである。各ルータ１０４が各関連バッファに対して１１ビットカウンタを有する要求は価格を増大し、ルータ１０４の潜在能力を減少する。望ましい実施例において、３６以上のバッファが各ルータ１０４に設置され得る。本発明は、特定のルータに設定されるすべてのバッファに対して１つの１０ビットカウンタを使用することによって、各バッファのそれぞれに対して１ビットフラグだけを使用することによってこの課題を解決する。１０ビットカウンタが、例えば、全論理１から全論理零に遷移し、フロー制御レシーバ１０４Ａ中の関連レジスタが状態IIにある各バッファに対してビットフラグが論理１に設定されたときに、１０ビットカウンタは連続的にクロックサイクルをカウントする。もしフロー制御レシーバ１０４Ａ中のレジスタが状態を変更したならば、１ビットフラグは論理零にリセットされる。しかしながら、レジスタの状態が次の１０ビットカウンタによる全論理零の遷移を変更しなければ、時間切れが発生するであろう。上述のように、時間切れが発生したときに、フロー制御レシーバ１０４Ａはそのレジスタを状態Ｉに遷移する。
図５は、本発明の第２の実施例に係る第２のルータ１０４Ｂ内のフロー制御トランスミッタ３０５Ｂ中のＮＭＴＳＲ９３１８Ｂだけを表す値を含むＢＳＭに応答する第１のルータ１０４Ａ内のフロー制御レシーバ３０４Ａ内のバッファ状態を示す状態図である。フロー制御レシーバ３０４Ａがどのように状態Ｉ、状態IIおよび状態IIIを解釈するかは上記図４を参照して記述される。もしＢＳＭがＮＭＴＳＲ３１８Ｂ内に値だけを表すならば、本発明に係るフロー制御プトコルは、ＢＳＭがＮＭＴＳＲ３１８ＢおよびＣＦＲ３２０Ｂの双方の値を表す状況とは相違して、ＢＳＭを解釈する。フロー制御レシーバ３０４Ａが初期化されたとき、フロー制御レシーバ３０４Ａ内のレジスタは状態IIIを示す値に設定される。もしＮＭＴＳＲ３１８Ｂ内の受信レジスタに関連するビットがＢＳＭに発生されたときに論理１に等しければ、ＢＳＭは論理１に等しい値を有する、即ちＢＳＭ＝１である。ＢＳＭ＝１は（１）以前のＢＳＭが送信されてからフレームデータが受信バッファによって受信されたこと、または（２）ＣＦＲ３２０Ｂによって示されるように以前のＢＳＭの送信時に受信バッファが空ではなかったことのいずれかを示す。もしＢＳＭ＝１がフロー制御レシーバ３０４Ａによって、そのレジスタが状態IIIにあるときに受信されたならば、これらのレジスタの値は変化しない。ＢＳＭ＝０は受信バッファが空であることを示す。ＢＳＭ＝０がフロー制御レシーバ３０４Ａによって受信されたときに、レジスタの状態は状態IIIから他のフレームが受信バッファに送信され得ることを示す状態Ｉに遷移する。
フロー制御レシーバ１０４Ａ中のレジスタの状態は、フレームがポート６バッファアレイ３２２Ｂ内の受信バッファに伝送されるまで状態Ｉを維持する。フレームが送信されたとき、フロー制御レシーバ３０４Ａ中のレジスタの状態は状態Ｉから状態IIに遷移する。もし状態IIである間にＢＳＭ＝０が受信されれば、状態の変化は発生しない。ＢＳＭ＝０は、以前のＢＳＭの伝送以後受信バッファによってデータは受信されなかったことを示す。ＢＳＭ＝１は、以前のＢＳＭの伝送以後受信バッファによっていくつかのフレームデータが受信されたことの確認である。従って、もしＢＳＭ＝１が受信されれば、フレームが受信バッファによって受信されたのでＳＡＮＲＲ３０８Ａはリセットされる。しかしながら、ＳＡＮＲＲ３０８Ａは受信バッファがデータを受信後少なくとも１つのＢＳＭに対して１に等しく設定されなければならないので、フロー制御レシーバ３０４Ａ中のレジスタが状態IIにあるときにＢＳＭ＝１が受信された場合は、ＢＳＭが送信されたときに受信バッファが空であるかの情報は識別され得ない。従って、ＳＡＮＲＲ３０８Ａ中の関連ビットはリセットされ、ＲＣＦＲ３０１Ａ中の関連ビットは論理１に設定される。ＢＳＭがＮＭＴＳＲ３１８Ｂだけを表すときは、ＢＳＭがＮＭＴＳＲ３１８ＢおよびＣＦＲ３２０Ｂの双方を表すときに可能なように、フロー制御レシーバ３０４Ａ中のレジスタは単一のＢＳＭに応答して状態IIから状態Ｉに遷移しない。ＢＳＭがＮＭＴＳＲ３１８Ｂだけを表すときに状態IIから状態Ｉに遷移するために、フロー制御レシーバは少なくとも２つのＢＳＭを受信しなければならない。第１のＢＳＭはレジスタの状態IIから状態IIIへの遷移を可能とし、第２のＢＳＭはレジスタの状態IIIから状態Ｉへの遷移を可能とする。しかしながら、もし時間切れが発生したならば、フロー制御レシーバ３０４Ａ中のレジスタは状態IIから状態Ｉへの遷移が可能である。時間切れの発生は、上記の図４を参照して説明される。フロー制御プロトコル装置および方法の動作は、以下に図６−９を参照してより詳細に説明される。
図６は、本発明に係る第１のルータ１０４Ａから第２のルータ１０４Ｂへのパケットの伝送に対するフロー制御プロトコルのフロー線図である。アービタ２  ２０４Ａは、第１のルータ１０４Ａのポート２  ２０２Ａを介して第２のルータ１０４Ｂのポート６  ２０２Ｂに送信されるデータが存在するかを６０２で決定する。６０２における送信すべきデータが存在するかの決定後、アービタ２  ２０４Ａはパケットのプライオリティを決定するためのフレームヘッダを検査する。望ましい実施例において、各フレームは３つのプライオリティ、即ち高、中、低プライオリティの１つを有している。第１のルータ１０４Ａ中のフロー制御レシーバ３０４Ａは６０６でポート６バッファアレイ３２２Ｂ中の空のバッファの数を決定する。１つのプライオリティプロトコルの例において、もしただ１つのバッファが空であれば、フロー制御レシーバは６０８でこのバッファを受信バッファとして選択し、上述のように受信バッファのアドレスを変更ユニット３２６Ａに送信する。フロー制御レシーバ３０４Ａは、第１のルータ１０４Ａから第２のルータ１０４Ｂへフレームを伝送するためにどのパケットプライオリティが要求されるかを６１０で決定する。例えば、ポート６バッファアレイ中で少なくとも１つのバッファが空であれば、フロー制御レシーバ３０４Ａは、高プライオリティフレームがポート６  ２０２Ｂに伝送されることができることを示す信号を高プライオリティ信号線を用いてアービタ２に伝送する。ポート６バッファアレイ中で少なくとも２つのバッファが空であれば、フロー制御レシーバ３０４Ａは、高プライオリティフレームまたは中プライオリティフレームがポート６  ２０２Ｂに伝送されることができることを示す信号を高プライオリティ信号線または中プライオリティ信号線を用いてアービタ２に伝送する。ポート６バッファアレイ中で少なくとも３つのバッファが空であれば、フロー制御レシーバ３０４Ａは、高プライオリティフレーム、中プライオリティフレームまたは低プライオリティフレームがポート６  ２０２Ｂに伝送されることができることを示す信号を高プライオリティ信号線、中プライオリティ信号線または低プライオリティ信号線を用いてアービタ２に伝送する。
アービタ２は６１４で、フレームが送信される十分なプライオリティを有するかを決定するために関連するプライオリティ信号線で受信される信号の値を有するフレームヘッダ中のフレームプライオリティを比較する。もしプライオリティ信号線がフレームが伝送され得ないことを示していれば、フレームは、フレームが送信され得る時間までポート３バッファアレイ３２２Ａ中に残留するであろう。もしプライオリティ信号線がフレームが送信され得ることを示しているならば、パケットは６１６において上述した方法で第２のルータ１０４Ｂのポート６  ２０２Ｂに伝送される。
第２のルータ１０４Ｂは６１８でパケットを受信する。データシンクロナイザ３２４Ｂがそれがデータパケットであることを決定後、データシンクロナイザ３２４Ｂは６２０で受信バッファ中のフレームを記憶する。データシンクロナイザはデータをポート６バッファアレイ３２２Ｂに送信する。ボール６バッファアレイ３２２Ｂ中のどのバッファが受信バッファであるかを決定するために、ポート６バッファアレイ３２２Ｂはフレームヘッダ中のバッファアドレスを読むことが可能であり、フレームヘッダ中にあるアドレスのバッファにフレームを多重化する。他の技術において、ポート６バッファアレイ３２２Ｂはパケットが受信される前に受信バッファを選択する。フレームが受信された時、それは直ちに予め選択されたバッファに送信される。フレームヘッダ中のバッファアドレスはバッファタグであり、６２４で実際のバッファアドレスと関連付けられる。ＢＳＭが発生されたとき、ＮＭＴＳＲ３１８ＢおよびＣＦＲ３２０Ｂ中のビットは実際のバッファアドレスの代わりにポート６バッファアレイ３２２Ｂ中のバッファのバッファタグアドレスに対応する。例えば、フロー制御レシーバ３０４Ａが受信バッファとして００１に等しいアドレスを有するバッファ１を選択したならば、このアドレスはフレームヘッダ中に記憶される。このフレームが第２のルータ１０４Ｂに伝送されたとき、データシンクロナイザ３２４Ｂはこのフレームをポート６バッファアレイ３２２Ｂに送信する。ポート６バッファアレイ３２２Ｂは、受信バッファとしてアドレス０１１を有するバッファ３を選択してもよい。フレーム中のデータはバッファ３に記憶される。しかしながら、ＢＳＭジェネレータ３１６ＢがＮＭＴＳＲ３１８ＢおよびＣＦＲ３２０Ｂを記憶したときに、バッファの状態はタグアドレス、即ち００１に対応したビット位置内に記憶される。従って、ＢＳＭが第１のルータ１０４Ａ中のフロー制御レシーバ３０４Ａによって受信されたときに、ＢＳＭ中のＮＭＴＳＲ３１８Ｂの値およびＣＦＲ３２０Ｂの値は、ＢＳＭレシーバ３０６Ａによって発生されたタグ値に対応している。
望ましい実施例において、フレームが第３のルータ１０４Ｅに送られることが可能でない限り、全フレームは受信バッファ内に記憶されない。このバーチャル・カット・スルー技術はフレームヘッダ内に全ルーチング情報を有することによって達成される。従って、いったん第２のルータ１０４Ｂがフレームヘッダを受信すると、第３のルータ１０４Ｅに接続される第２のルータ１０４Ｂ内の出力ポート、例えばポート２は既知であり、第２のルータ９１０４Ｂが全パケット体を受信する前に第２のルータ１０４Ｂは第３のルータ１０４Ｅに対するフレームヘッダの伝送を開始することが可能となる。
受信バッファがフレームの一部を受信した後、第２のルータ１０４Ｂ中のフロー制御トランスミッタ３０５ＢはＢＳＭジェネレータ３１６Ｂに受信バッファの状態を送信する。以前のＢＳＭが発生され、データが受信バッファで受信されたときに受信バッファが空であれば、ＮＭＴＳＲ３１８Ｂ中の関連するビットは６２６で論理１に等しく設定する。上述したように、フレームが第２のルータ１０４Ｂによって受信されたことの確認として機能するために、ＮＭＴＳＲ３１８Ｂ内のビットは少なくとも１つのＢＳＭに対して論理１の等値を維持する。さらに、受信バッファが空でないとき、ＣＦＲ３２０Ｂはまた６２８で論理１に設定される。しかしながら、もしＢＳＭが発生される前に受信バッファが空になれば、ＣＦＲ３２０Ｂは６３０で受信バッファが空であることを示す論理零にリセットされる。上述のように、ＮＭＴＳＲ３１８Ｂおよび多分ＣＦＲ３２０Ｂの内容はＢＳＭ中に含まれる。ＢＳＭの伝送および受信に関するより詳細な説明は図７−９を参照して以下に記述される。
図７は本発明に係るバッファ状態メッセージ発生および伝送技術のフロー線図である。データフレームが第２のルータ１０４Ｂから第１のルータ１０４Ａに伝送されなかったときは常に、即ちフレームが上記例に記載されたものから反対方向に伝送されたときは、フロー制御トランシミッタ３０５ＢはＢＳＭを伝送する。もし反対方向へのデータフローが重ければ、全データフレームが送信される後まで、ＢＳＭは送信されない。しかしながら、フロー制御トランシミッタ３０５Ｂがフロー制御レシーバ３０４Ａに直ちにＢＳＭを伝送することが重要である状況がある。この状況の一例は、バッファがポート６バッファアレイ３２２Ｂ中で使用可能となったときである。例えばフレームが送信されるようにポート６バッファアレイ３２２Ｂ内で十分なバッファが使用可能となることを待っている第１のルータ１０４Ａ中のバッファアレイ３２２中に記載されるパケットが存在するので、フロー制御レシーバ３０４Ａがバッファが使用可能となったことを示すＢＳＭを受信することは重要であるかもしれない。例えば、フロー制御レシーバ３０４Ａ内の情報がポート６バッファアレイ３２２Ｂ内で２つのバッファだけが使用可能であることを示していれば、上述のプライオリティプロトコルが使用されるならば、低プライオリティを有するフレームは第１のルータ１０４Ａから第２のルータ１０４Ｂのポート６  ２０２Ｂに送信され得ない。第３のバッファがポート６バッファアレイ３２２Ｂ内で使用可能となったときに、この情報はＢＳＭの形式でフロー制御レシーバ３０４Ａに伝送され得る。迅速なＢＳＭの伝送のために、フロー制御トランシミッタは第２のルータ１０４Ｂ中のアービタ６  ２０４ＢにＢＳＭが可能な限り迅速に伝送されることを要求する信号を送信する。アービタ６  ２０４Ｂは第２のルータ１０４Ｂ上のＭＵＸ３２８Ｂを制御する信号を発生する。この信号に応答して、例えば現在伝送中のフレームが完全に伝送された後に、ＭＵＸ３２８Ｂは信号線２１２上でＢＳＭを多重化することが可能である。
もし７０２でＢＳＭを送信すべき時間であれば、ＢＳＭジェネレータ３１６Ｂは７０４でＢＳＭを発生する。上述のように、ＢＳＭの内容はＮＭＴＳＲ３１８ＢまたはＮＭＴＳＲ３１８ＢとＣＦＲ３２０Ｂの双方であり得る。もしＣＦＲ３２０Ｂの値が論理零であり以前のＢＳＭが送信されて以後いくつかのデータがバッファ中に受信されたならば、バッファに関連するＮＭＴＳＲ３１８Ｂ内の値が上述したようにパケットが受信されたことを示すために論理１に等しく設定されるという例外の下に、ＮＭＴＳＲ３１８Ｂの内容は以前のＢＳＭ時のＣＦＲ３２０Ｂの内容に等しい。フロー制御トランシミッタ３０５Ｂは、７０６でＢＳＭパケットをＭＵＸ３２８Ｂに伝送する。そしてＭＵＸ３２８Ｂは７０８でＢＳＭを第１のルータ１０４Ａに伝送する。７０６でＢＳＭをＭＵＸ３２８Ｂに伝送した後、フロー制御トランシミッタ３０５Ｂは７１０でＮＭＴＳＲ３１８ＢをＣＦＲ３２０Ｂに等しく設定する。
図８は、本発明に係るバッファ状態メッセージ受信技術のフロー線図である。データシンクロナイザ３２４ＡがＢＳＭを受信し、ＢＳＭがデータフレームでなくバッファ状態メッセージであることを８０２で決定し、ＢＳＭをフロー制御レシーバ３０４Ａに送信する。フロー制御レシーバ３０４Ａは８０４で各バッファを選択し、各バッファに対して並列に図８の残りのステップを実行する。フロー制御レシーバ３０４Ａ中のＢＳＭレシーバ３０６Ａは８０６でＳＡＮＲＲ３０８Ａ中の各バッファに関連するビットが論理１に等しいかを決定する。もしＳＡＮＲＲ３０８Ａが論理１に等しければ、ＢＳＭレシーバ３０６Ａは８０８でＢＳＭのＮＭＴＳＲ３１８Ｂ部中の各バッファに関連するビットが論理１に等しいかを決定する。ＮＭＴＳＲ＝１であれば、ＳＡＮＲＲ３０８Ａは８１０で論理零に設定され、処理はステップ８１２に進む。もしＳＡＮＲＲ３０８Ａの値が論理零に等しいか、もしＮＭＴＳＲ３１８Ｂの値が論理零に等しければ、処理はステップ８１２に進む。もしＢＳＭがＮＭＴＳＲ３１８ＢおよびＣＦＲ３２０Ｂの双方を表すならば、ＲＣＦＲ３１０Ａ内の各ビットはステップ８１２でＣＦＲ３２０Ｂ内の関連するビットに等しく設定される。もしＢＳＭがＮＭＴＳＲ３１８Ｂだけを表すのであれば、ＢＳＭレシーバ３０６Ａは８１２でＲＣＦＲ３１０ＡをＢＳＭのＮＭＴＳＲ３１８Ｂ部内の関連するビットに等しく設定する。そしてＢＳＭレシーバ３０６Ａは８１４で、ＢＢＲ３１２Ａ内の各ビットをＳＡＮＲＲ３０８ＡおよびＲＣＦＲ３１０Ａ内の関連するビットの論理的ＯＲに等しく設定する。
図９（ａ）−９（ｇ）は、本発明に係るレジスタ値の例である。図９において、ＲＣＦＲ３１０Ａ、ＳＡＮＲＲ３０８ＡおよびＢＢＲ３１２Ａとラベル付けされた３つのレジスタは、パケットが第１のルータ１０４Ａから第２のルータ１０４Ｂに伝送されたときの、第１のルータ１０４Ａ中のフロー制御レシーバ３０４Ａ中のレジスタの値に対応している。ＣＦＲ３２０ＢおよびＮＭＴＳＲ３１８Ｂとラベル付けされた２つのレジスタは、パケットが第１のルータ１０４Ａから第２のルータ１０４Ｂに伝送されたときの、第２のルータ１０４Ｂ中のフロー制御トランスミッタ３０５Ｂ中のこれらのレジスタの値に対応している。図９（ａ）は、ルータ１０４が初期化されたときのレジスタの値を示している。図４および図５の状態線図に示されているように、ＲＣＦＲ３１０ＡおよびＢＢＲ３１２Ａ内の値は論理１に等しく設定されるが、残りのレジスタの値は論理零に設定されたままである。フロー制御トランスミッタ３０５Ｂは、上述したように第１のＢＳＭを発生し、それをフロー制御レシーバ３０４Ａに伝送する。第１のＢＳＭ受信後のレジスタの値は図９（ｂ）に示されている。第１のＢＳＭは、ＢＳＭのサイズに応じてＢＳＭ＝０，０またはＢＳＭ＝０のいずれかに等しい。いずれの状況であっても、フロー制御レシーバ３０４Ａのレジスタは状態IIIから状態Ｉに遷移する。この例の残りの部分は、上述したようにポート６バッファアレイ３２２Ｂ中の第１のバッファまたはタグ００１に関連するバッファを含む。第１のルータ１０４Ａはフレームを第２のルータ１０４Ｂに伝送する。フレーム伝送後のレジスタの状態は、図９（ｃ）に示されている。図９（ｃ）において、第１のルータ１０４Ａはフレームを送信したが確認信号を受信しなかったのでＳＡＮＲＲ３０８Ａは論理１に等しく設定される。ＳＡＮＲＲ３０８Ａは論理１に等しく設定されているので、ＢＢＲ３１２Ａもまた論理１に設定される。
フレームがポート６バッファアレイ３２２Ｂによって受信され、フロー制御トランスミッタはＮＭＴＳＲ３１８ＢおよびＲＣＦＲ３２０Ｂを更新した後、レジスタの値は図９（ｄ）に示される値となる。図９（ｄ）において、ＢＳＭがフロー制御レシーバ３０４Ａによって受信されていないので、ＳＡＮＲＲ３０８Ａ、ＲＣＦＲ３１０ＡおよびＢＢＲ３１２Ａの値は変化しなかった。しかしながら、第１のＢＳＭが送信された後にデータがポート６バッファアレイ３２２Ｂによって受信されたので、ＮＭＴＳＲ３１８Ｂ内の第１ビットは論理１に等しい。第１のバッファは空ではないので、ＣＦＲ３２０Ｂ内の第１ビットもまた論理１に設定される。しかしながら、第２のＢＳＭが送信される前に、パケットが第３のルータ１０４Ｅに伝送され、第１のバッファは空となる。従って、第２のＢＳＭが発生されたときのＣＦＲ３２０Ｂの値は、論理零に等しい。これは図９（ｅ）に示されている。レジスタの値が図９（ｅ）に示されているようであるときは、フロー制御トランスミッタ３０５Ｂは第２のＢＳＭを発生し伝送する。もし第２のＢＳＭがＮＭＴＳＲ３１８ＢおよびＣＦＲ３２０Ｂの双方を含むならば、フロー制御レシーバ３０４Ａ内のレジスタの値は第２のＢＳＭの受信後、図９（ｇ）に示すものとなる。図９（ｇ）において、ＳＡＮＲＲ３０８Ａ、ＲＣＦＲ３１０ＡおよびＢＢＲ３１２Ａ内の全ビットの値は論理零に等しくなる。ＣＦＲ３２０Ｂの値がＮＭＴＳＲ３１８Ｂ内に記憶されるのでフロー制御トランスミッタ３０５Ｂ中のレジスタの値もすべて零に等しい。これは、図４に示す状態IIから状態Ｉに遷移したフロー制御レシーバ３０４Ａ内のレジスタに等しい。もし第２のＢＳＭがＮＭＴＳＲ３１８Ｂだけを含むときは、フロー制御レシーバ３０４Ａが第２のＢＳＭを受信した後のレジスタの値は図９（ｆ）に示すものとなる。これは、図５に示す状態IIから状態IIIに遷移したフロー制御レシーバ３０４Ａ内のレジスタに等しい。以後は、フロー制御トランスミッタ３０５Ｂは、ＮＭＴＳＲ３１８Ｂの値だけを含む第３のＢＳＭを発生し伝送するであろう。第３のＢＳＭを受信後、レジスタの値は図９（ｇ）に示すようになる。これは図５に示す状態IIIから状態Ｉに遷移したフロー制御レシーバ３０４Ａ内のレジスタに等しい。
【図１】
0003739799.tif 000002
【図２】
0003739799.tif 000003
【図３】
0003739799.tif 000004
【図４】
0003739799.tif 000005
【図５】
0003739799.tif 000006
【図６（ａ）】
0003739799.tif 000007
【図６（ｂ）】
0003739799.tif 000008
【図７】
0003739799.tif 000009
【図８】
0003739799.tif 000010
【図９】
0003739799.tif 000011