(57)【要約】【課題】デジタルデータネットワークにおけるメッセージフローを調整するシステムおよび方法を提供する。【解決手段】システム（１０）は、１つまたは２つ以上のスイッチングノード（１１）を含むネットワークによって相互接続された複数のコンピュータ（１２）を含んでいる。コンピュータ（１２）はその間に確立された仮想回線を利用してメッセージを転送する。ソースコンピュータおよびデスティネーションコンピュータ（１２）は、メッセージの送信および処理を、ラウンドロビン方式でそれぞれスケジュールする。それぞれの仮想回線に対してパス（１３）の一部を形成している各スイッチングノード（１１）も、仮想回線に対するメッセージをラウンドロビン方式で転送し、１つまたは２つ以上の仮想回線のデスティネーションコンピュータとしてのコンピュータは、受信したメッセージの処理をラウンドロビン方式でスケジュールする。【選択図】図１
2010081641.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介して仮想回線上のセルを受信するために構成されたデバイスであって、
前記仮想回線上で、前記デバイスにより受信されたセルを格納するために構成されたバッファと、
前記バッファのデータ占有レベルが第１のしきい値未満であるときは非フロー制御状態、
前記バッファのデータ占有レベルが前記第１のしきい値を超えかつ第２のしきい値未満であるときは第１の輻輳状態、および
前記バッファのデータ占有レベルが前記第２のしきい値を超えたときは第２の輻輳状態
にあるフロー制御回路と
を備え、前記フロー制御回路は、前記非フロー制御状態にある場合に、ラウンドロビン方式で、複数の仮想回線の状態をセットされた仮想回線フロー制御状態からクリアされた仮想回線フロー制御状態に変更するために構成されたことを特徴とするデバイス。
【請求項２】
少なくとも第１の通信リンクおよび第２の通信リンクに結合されたスイッチングノードであって、
前記第１の通信リンクから受信したデータを格納するために構成されたバッファストアと、
仮想回線のために前記バッファストアに格納されるデータが第１のしきい値レベルを超えた場合は、セットされた仮想回線フロー制御状態に入るために構成された入力ポートコントロールと
を備え、前記入力ポートコントロールは、(a)  出力ポート仮想回線利用数、(b)  前記バッファストアのセル占有レベル、および(c)  前記バッファストアに格納された前記仮想回線のセルの数に基づき前記セットされた仮想回線フロー制御状態に入るために構成されたことを特徴とするスイッチングノード。
【請求項３】
少なくとも１つの通信リンクを含むネットワークにより相互接続された少なくとも３つのデバイスを備えたシステムであって、各デバイスは前記ネットワーク上でメッセージを転送するためのネットワークインタフェースを含み、前記デバイスの少なくとも１つは、ソースデバイスとして、前記ネットワーク上で確立される少なくとも１つの仮想回線上でメッセージを送信し、前記デバイスの少なくとも他の１つは、デスティネーションデバイスとして、前記少なくとも１つの仮想回線上で前記メッセージを受信し、前記デバイスの少なくとも１つは、スイッチングノードとして、前記ソースデバイスおよび前記デスティネーションデバイスの間でメッセージを転送し、
前記デスティネーションデバイスのネットワークインタフェースは、前記少なくとも１つの仮想回線上で受信されたメッセージを格納するために構成されたバッファと、(i)  前記少なくとも１つの仮想回線上で受信されたメッセージにより占有される前記バッファの部分が選択された仮想回線フロー制御しきい値レベルを超えたときは、前記ソースデバイスへの通信リンクを介して転送するための、前記仮想回路に関連するセットされた仮想回線フロー制御メッセージを生成し、(ii)  メッセージにより占有される前記バッファの部分が選択されたリンクフロー制御しきい値レベルを超えたときは、前記通信リンクを介して送信するための、セットされたリンクフロー制御メッセージを生成するために構成されたデスティネーションフロー制御回路とを含み、
前記ソースデバイスのネットワークインタフェースは、前記少なくとも１つの仮想回線上でメッセージを送信するために構成された送信部と、(i)  前記少なくとも１つの仮想回線に関連するセットされた仮想回線フロー制御メッセージの、前記ソースデバイスによる受信に応答して、前記送信部が前記少なくとも１つの仮想回線上でメッセージを送信できないようにし、かつ(ii)  接続された前記通信リンク上での、セットされたリンクフロー制御メッセージの、前記ソースデバイスによる受信に応答して、前記送信部が前記通信リンクを介してメッセージを送信できないようにするために構成されたソースフロー制御回路とを含み、
前記スイッチングノードは、前記ソースデバイスおよび前記デスティネーションデバイスの間で前記少なくとも１つの仮想回線に対するパスの部分を形成し、前記スイッチングノードは、少なくとも２つの可能な状態のうちの１つの状態で動作し，かつリンクの輻輳測定基準に従って前記スイッチングノードが動作する状態を変更するために構成され、前記状態は、(i)  前記スイッチングノードが、如何なるセットされた仮想回線フロー制御メッセージも生成しない非フロー制御状態、および(ii)  前記スイッチングノードが、必要に応じて仮想回線の輻輳測定基準に従って、セットされた仮想回線フロー制御メッセージおよびクリアされた仮想回線フロー制御メッセージを生成する通常輻輳状態を含むことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般的にはデジタル通信システムの分野に関し、さらに具体的には、例えば、デジタルイメージ（画像）、オーディオおよびビデオ配信システムでのデジタルデータの通信とデジタルコンピュータシステム相互間の通信を容易化するデジタルネットワークに関する。さらに具体的には、本発明は、輻輳を防止し、データ損失を防止し、ネットワークを利用して情報を転送する複数のデバイス間で公平性を保つように、ネットワークを通る情報のフロー（流れ）を調整するフロー制御およびスケジューリング構成を目的としている。
【背景技術】
【０００２】
データとプログラムを含む情報を、デジタルコンピュータシステムや他のデジタルデバイス相互間で転送することを容易化するデジタルネットワークはすでに開発されている。種々タイプのネットワークは、種々の情報転送技法を使用して開発され、構築されている。周知のEthernetなどの、いくつかのネットワークでは、ネットワークに接続されたデバイスのすべてを相互接続するためにシングルワイヤが使用されている。この方法によると、施設内のネットワークの配線が単純化され、デバイスをネットワークに接続することが単純化されるが、ワイヤはメッセージの形をした情報を、一度に１つのデバイスからしか伝達できないために情報転送が全体的に低速になっている。この問題をある程度軽減するために、いくつかのEthernet設置施設では、ネットワークはいくつかのサブネットワークに分割され、各サブネットワークが別々のワイヤを有し、これらのワイヤはインタフェースで相互に接続されている。このような施設では、ワイヤはそこに接続されたデバイスのメッセージを同時に伝達できるために、同時に転送できるメッセージの数が増加している。２またはそれ以上のサブネットワーク内のワイヤが使用されるのは、あるワイヤに接続されたデバイスが別のワイヤに接続されたデバイスにメッセージを送信する必要があるときだけであるため、ワイヤに接続された他のデバイスはサブネットワークを利用できないようになっている。
【０００３】
この問題をさらに軽減するために、メッシュ（網）状のスイッチングノードを通してコミュニケーション（通信）が処理されるようにしたネットワークが開発されている。コンピュータシステムと他のデバイスは種々のスイッチングノードに接続されている。スイッチングノード自体はさまざまなパターンで相互接続されているために、デバイスのペア間で複数のパス (path) が利用できるので、あるパスが輻輳しているとき、別のパスが使用できるようになっている。このような構成では、ネットワークはEthernetネットワークよりも複雑化するが、特に、スイッチングノードとデバイスを相互接続する媒体として光ファイバが使用される場合には、情報転送レートを大幅に高速化することを可能にしている。この種のネットワークには次のような問題がある。すなわち、この種のネットワークでは、スイッチングノードまたはデバイスがネットワーク内の別のスイッチングノードまたはデバイスから情報を受信するとき、「フロー制御(flow-control)」情報を送信側スイッチングノードまたはデバイスに提供するメカニズムがないことである。このようにすると、ネットワークのコストは確かに低減されるが、輻輳を引き起こす原因になり、輻輳が起こると、スイッチングノードは送信能力以上の高速レートで情報を受信することになるか、あるいはデスティネーションデバイスは情報をバッファに格納し、情報を処理できる以上の高速レートで情報を受信することになっている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、通信ネットワークにおけるメッセージ転送をスケジューリングする新規で、改良されたシステムおよび方法を提供することを目的としている。
【課題を解決するための手段】
【０００５】
要約して簡単に説明すると、本発明の一実施形態によれば、少なくとも１つの通信リンクを含むネットワークによって相互接続された少なくとも２つのデバイスを含んでいるシステムが提供されている。各デバイスは、ネットワークを利用してメッセージを転送するためのネットワークインタフェースを装備している。これらデバイスの少なくとも１つは、ソースデバイス (source device) として、ネットワーク上に確立された１つまたは２つ以上の仮想回線 (virtual circuit) を利用してメッセージを送信し、他の前記デバイスの少なくとも１つは、それぞれの仮想回線のデスティネーションデバイス (destination device) として、仮想回線を利用してメッセージを受信する。デスティネーションデバイスのネットワークインタフェースは、デバイスがそのデスティネーションデバイスとなっているすべての仮想回線上で受信されたメッセージをバッファに格納するように構成されたバッファを含んでいる受信セクションと、デスティネーションフロー制御回路とを含んでいる。デスティネーションフロー制御回路は、(i) １つの仮想回線上で受信されたメッセージによって占有されている前記バッファの部分が、選択した仮想回線フロー制御しきいレベルを超えたときは、デバイスがデスティネーションデバイスとなっている仮想回線に関連する仮想回線フロー制御メッセージを生成して通信リンク上をその仮想回線に対するソースデバイスに転送し、および(ii) メッセージによって占有されている前記バッファの部分が、選択したリンクフロー制御しきいレベルを超えたときは、リンクフロー制御メッセージを生成して前記通信リンク上を送信するようになっている。ソースデバイスのネットワークインタフェースは、それがソースデバイスとなっている１つまたは２つ以上の仮想回線上にメッセージを送信するように構成された送信セクションと、ソースフロー制御回路とを含んでいる。ソースフロー制御回路は、(i) 仮想回線に関連する仮想回線フロー制御メッセージが前記ソースデバイスによって受信されると、それに応答して、送信セクションが仮想回線上にメッセージを送信することを禁止し、(ii) そこに接続された通信リンク上でリンクフロー制御メッセージがソースデバイスによって受信されると、それに応答して、送信セクションが通信リンク上にメッセージを送信することを禁止するようになっている。従って、デスティネーションデバイスは、仮想回線によるバッファ占有が仮想回線フロー制御しきいレベルを超えたとき、仮想回線に対して仮想回線フロー制御メッセージを送信することによって、いずれかの仮想回線に関連するメッセージによって占有されるバッファリソース量を制限し、すべての仮想回線の間でバッファリソースの公平性が有効に保たれるようにしている。さらに、デスティネーションデバイスは、リンクフロー制御メッセージを送信することによって、メッセージ損失の原因となるバッファのオーバフローを防止している。
【０００６】
別の実施形態では、ネットワークは、ソースデバイスとデスティネーションデバイスの間の１つまたは２つ以上の仮想回線に対するパスの一部を形成しているスイッチングノード (switching node) を含んでいる。スイッチングノードは、そのノードがそこに接続された通信リンク上のパスの一部を形成している、その仮想回線を利用してソースデバイスから送信されたメッセージを受信し、受信したメッセージを内部バッファに格納し（バッファリング）、およびバッファに格納されたメッセージをそこに接続された別の通信リンク上のその仮想回線を利用して送信するように接続され、その仮想回線に対するメッセージを、仮想回線上のそれぞれの下流側に転送するようにしている。スイッチングノードがその仮想回線上にメッセージを送信することになっている通信リンク上で、仮想回線に対する仮想回線フロー制御メッセージを受信した場合は、そのスイッチングノードは、仮想回線に対するメッセージをそこで受信することになっている通信リンク上に仮想回線フロー制御メッセージを転送することにより、その仮想回線フロー制御メッセージを仮想回線上の上流側に転送する。スイッチングノードが通信リンク上でリンクフロー制御メッセージを受信した場合は、そのスイッチングノードは、通信リンク上でメッセージを送信することを中止する。さらに、特定の仮想回線からのメッセージによるスイッチングノードのバッファの占有が選択した仮想回線しきいレベルを超えた場合は（このしきいレベルは、一実施形態では、スイッチングノードがそのパスの一部を形成している仮想回線の数に応じて変化する）、そのスイッチングノードは仮想回線フロー制御メッセージを生成し、スイッチングノードがその仮想回線に対してメッセージをそこで受信することになっている通信リンク上にそれを送信し、その仮想回線フロー制御メッセージを仮想回線上の上流側に転送することによって、その仮想回線に対するソースデバイスが仮想回線上にメッセージを送信するのを禁止する。スイッチングノードのバッファの占有が選択したリンクしきいレベルを超えた場合は、そのスイッチングノードはリンクフロー制御メッセージを生成し、スイッチングノードに接続されていて、スイッチングノードがそこでメッセージを受信する通信リンク上にそのメッセージを送信する。従って、スイッチングノードは、仮想回線によるバッファ占有が仮想回線フロー制御しきいレベルを超えたときは仮想回線に対して仮想回線フロー制御メッセージを送信することによって、いずれかの仮想回線に関連するメッセージによって占有されるバッファリソース量を制限し、すべての仮想回線の間でバッファリソースの公平性が有効に保たれるようにしている。さらに、スイッチングノードは、リンクフロー制御メッセージを送信することによって、メッセージ損失の原因となるバッファのオーバフローを防止している。
本発明は具体的には特許請求の範囲に記載されているが、本発明の上記および他の利点を理解しやすくするために、以下では、添付図面を参照して説明することにする。
【図面の簡単な説明】
【０００７】
【図１】本発明によるフロー制御構成が実装されているコンピュータネットワークを示す概略図である。
【図２】図１に示すコンピュータネットワークで使用されるコンピュータシステムを示す機能ブロック図である。
【図３】図１に示すコンピュータネットワークで使用されるスイッチングノードを示す機能ブロック図である。
【図４】本発明によるコンピュータシステムのオペレーションを示す詳細フローチャートである。
【図４Ａ】本発明によるコンピュータシステムのオペレーションを示す詳細フローチャートである。
【図５】図２に示すコンピュータネットワークで使用される受信スケジューラを示す機能ブロック図である。
【図６】図２に示すコンピュータネットワークで使用される送信スケジューラを示す機能ブロック図である。
【発明を実施するための形態】
【０００８】
図１は、データを表している信号を複数のデバイスの間で転送するための複数のスイッチングノード１１(1) 乃至１１(N)（１１(n) で総称する）を含んでいるコンピュータネットワーク１０を示す概略図であり、図１に示すように、デバイスはコンピュータ１２(1) 乃至１２(M)（１２(m) で総称する）で表されている。コンピュータ１２(m) は、従来と同じように、プログラム命令に従ってデータを処理し、処理済みデータを生成する。この処理の際、コンピュータ１２(mS)（下付き文字の”Ｓ”は「ソース」を表している）は、ソースコンピュータであるときは、データ、処理済みデータおよび/またはプログラム命令（以下では、これらは「情報」と総称することにする）を、別のデスティネーションコンピュータ１２(mD)（下付き文字の”Ｄ”は「デスティネーション」を表している）に転送する必要が起こることがあり、また、デスティネーションコンピュータは転送されてきた情報をそのオペレーションで使用する必要が起こることがある。各コンピュータ１２(m) は、全体を符号１３(p) で示している通信リンクを利用してスイッチングノード１１(n) に接続され、スイッチングノードとの間のデータの送受信を容易化している。スイッチングノード１１(n) はコンピュータ１２(m) からや、他のスイッチングノード１１(n) から送られてきたデータを受信し、バッファに格納し、転送することによって、コンピュータ１２(m) 間のデータ転送を容易化している。スイッチングノード１１(n) は、これも全体を符号１３(p) で示している通信リンクで相互接続され、その間のデータ転送を容易化している。通信リンク１３(p) は、都合の良いものであれば、どのデータ伝送媒体でも利用することが可能である。図１に示す各通信リンク１３(p) は双方向であることが好ましく、そのようにすると、スイッチングノード１１(n) は相互間に、および同一リンクを利用してそこに接続されたコンピュータ１２(m) との間で信号を送受信することができる。この双方向通信リンクを取り入れるために、通信リンク１３(p) ごとに別の媒体を設けると、各通信リンクは信号を単方向に転送することが可能になる。
【０００９】
一実施形態では、データは周知の  ”ＡＴＭ”（”Asynchronous Transfer Mode”：非同期転送モード）転送技法を使用して転送される。この技法は、C. Partridge著「ギガビットネットワーキング(Gigabit Networking)」（Reading MA: Addison Wesley Publishing Company, 1994）の主に第３章と第４章、およびD. McDysan他著「ATMの理論と応用(ATM Theory and Application)」(McGraw Hill, 1995) に詳しく説明されているので、ここで詳しく説明することは省略する。一般的に、ATM技法では、コンピュータ１２(m) とスイッチングノード１１(n) は、ネットワークを通してコンピュータ間に確立された「仮想回線(virtual circuit)」を利用してデータを固定長「セル(cell)」の形で伝送している。各仮想回線は、基本的に、ソースコンピュータ１２(mS) からデスティネーションコンピュータ１２(mD) へのパスを、１つまたは２つ以上のスイッチングノード１１(n) を通って、それぞれの通信リンク１３(p) を利用するように定義している。ATMデータ転送技法では、ある情報ブロックがソースコンピュータ１２(mS) からデスティネーションコンピュータ１２(mD) あてに、その間に確立された仮想回線を利用して転送されるとき、ソースコンピュータ１２(mS) はそのデータブロックを１つまたは一連の「セル」に割り当てて、通信リンク１３(p) 上をシリアルに伝送するようにする。ネットワーク１０を通して転送される各セルはヘッダ部分とデータ部分を含み、ヘッダ部分は、ネットワーク１０を通るセルの転送を制御するための仮想回線ID情報のほかに、プロトコルおよび他の制御情報（「メッセージ終わり(end of message - EOM)」フラグなど）も含んでいる。データ部分は、セルに入って転送されるデータブロックのデータを収めている。各セルのデータ部分はあらかじめ決めた固定長になっており、一実施形態では、48バイトになっている。ソースコンピュータ１２(mS) はデータをセルのデータ部分に埋め込むか（転送されるデータブロックが１つのセルに収容される場合）、あるいはブロックに含まれるデータ量が各セルのデータ部分のサイズの整数倍になっていない場合、一連のセルの最終セルに埋め込むことによって（転送されるデータブロックを収容するために複数のセルが必要な場合）、最終セルのデータ部分が必要とする長さを有するようにしている。データブロックを転送するために一連のセルが必要なときは、ソースコンピュータ１２(m) は、一連のセルのデータ部分が転送されるデータブロック内のデータの順序に一致するようにセルを送信する。さらに、これらのセルがデスティネーションコンピュータ１２(mD) に正しく転送されると、デスティネーションコンピュータはセルを同じ順序で受信することになる。一連のセルの中で、データブロックからの情報を収めている最終セルでは、ヘッダ部分のメッセージ終わりフラグがセットされるので、データブロックのデータを収めているセルのすべてを受信したことがデスティネーションコンピュータ１２(mD) に通知される。
【００１０】
本発明は、コンピュータ１２(m) とスイッチングノード１１(n) がネットワーク上のセルのフローを制御し、スイッチングノード１１(n) 側とデスティネーションコンピュータ側の双方で輻輳が起こるのを防止または低減するための構成を提供している。このような構成がないと、セル転送スループットが低下し、あるいはネットワーク上でセルが紛失するおそれがある。さらに、本発明は、コンピュータ１２(m) とスイッチングノード１１(n) によるオペレーションをスケジュールすることによって情報転送の公平性が全体的に保たれるようにすると共に、ネットワーク１０を通して確立された種々の仮想回線を利用した小さなメッセージの転送の遅れを妥当な範囲に留めるようにする構成を提供している。一般的に、フロー制御に関しては、コンピュータ１２(m) とスイッチングノード１１(n) は、フロー制御を２つのモードで実現している。本明細書では、一方は仮想回線フロー制御モード (virtual circuit flow control mode)、他方はリンクフロー制御モード (link flow control mode) と呼ぶことにする。仮想回線フロー制御モードでは、仮想回線に対してデスティネーションコンピュータ１２(mD) として動作しているコンピュータ１２(m) が余りに高速レートでその仮想回線に関連するセルを受信するために、処理できない場合には（これについては下述する）、仮想回線フロー制御モードで動作しているデスティネーションコンピュータ１２(mD) はセットされた仮想回線フロー制御ステートに入るので、仮想回線のフロー制御が可能になる。このオペレーションでは、デスティネーションコンピュータ１２(mD) はセットされた仮想回線フロー制御メッセージを生成し、仮想回線のパス上を上流側に、つまり、仮想回線のソースコンピュータ１２(mS) に向かってそのメッセージを伝送する。デスティネーションコンピュータ１２(mD) からソースコンピュータ１２(mS) へ向かう仮想回線のパス上の各スイッチングノード１１(n) も、その仮想回線に対してセットされた仮想回線フロー制御ステートに入る。仮想回線のソースコンピュータ１２(mS) がセットされた仮想回線フロー制御メッセージを受信すると、その仮想回線に関連するセルの送信を事実上停止する。
【００１１】
仮想回線のパス上の各スイッチングノード１１(n) は、例えば、余りに高速レートで仮想回線に関連するセルを受信するために、仮想回線のパス上を下流側に転送できない場合も（これについては下述する）、仮想回線フロー制御モードで動作しているとき、セットされた仮想回線フロー制御ステートに入って、セットされた仮想回線フロー制御メッセージを生成し、その仮想回線のパス上を上流側にそのメッセージを送信することができる。ソースコンピュータ１２(mS) に向かう仮想回線のパス上の上流側スイッチングノード１１(n)（存在する場合）とソースコンピュータ１1(mS) は上述したのと同じように動作する。
【００１２】
デスティネーションコンピュータ１２(mD) がその仮想回線のセルの受信を再開できるようになると、クリアされた仮想回線フロー制御ステートに入るので、クリアされた仮想回線フロー制御メッセージを生成し、その仮想回線のパス上を上流側にそのメッセージを伝送する。スイッチングノード１１(n) がクリアされた仮想回線フロー制御メッセージを受信したとき、自身がセットされた仮想回線フロー制御ステートになっていなければ、セットされた仮想回線フロー制御メッセージを、仮想回線のパス上を上流側に向かって、ソースコンピュータ１２(mS) に通じるパス上の上流側スイッチングノード１１(n)（存在する場合）に伝送するか、あるいは仮想回線のソースコンピュータ１２(mS) に伝送する。他方、スイッチングノード１１(n) がクリアされた仮想回線フロー制御メッセージを受信した場合、自身がセットされた仮想回線フロー制御ステートにあれば、クリアされた仮想回線フロー制御メッセージの転送を、セットされた仮想回線フロー制御ステートから出るまで延期し、この状態から出ると、クリアされた仮想回線フロー制御メッセージを仮想回線のパス上の上流側に転送する。ソースコンピュータ１２(mS) が、クリアされた仮想回線フロー制御メッセージを受信したとき、仮想回線に関連するセルを、仮想回線上の下流側に伝送することを再開することが可能になる。以上から理解されるように、スイッチングノード１１(n) がセットされた仮想回線フロー制御ステートにある間、クリアされた仮想回線フロー制御メッセージを仮想回線のパス上を下流側に転送することを延期できるようにすると、スイッチングノード１１(n) は、上流側スイッチングノード１１(n) またはソースコンピュータ１２(mS) がセルをそこに伝送することを再開することが可能になる前に、仮想回線のセルを転送できるので、仮想回線に対してバッファに格納しておく必要のあるセルの数が低減されることになる。
【００１３】
リンクフロー制御モードは、仮想回線ごとの単位ではなく、通信リンク単位で実現されている。従って、リンクフロー制御モードでは、コンピュータ１２(m) がそこに接続されたスイッチングノード１１(n) からセルを、余りに高速レートで受信しているために処理ができない場合には（これにつても下述する）、リンクフロー制御モードで動作しているコンピュータ１２(m) はセットされたリンクフロー制御状態に入るので、通信リンクのフロー制御が可能になる。このオペレーションでは、コンピュータ１２(m) はセットされたリンクフロー制御メッセージを生成し、そのリンクを利用してそこに接続されたスイッチングノード１１(n) にそのメッセージを送信する。スイッチングノード１１(n) はセットされたリンクフロー制御メッセージを受信すると、そのリンクを利用してセルをそこに送信することを停止する。同様に、各スイッチングノード１１(n) は、例えば、余りに高速レートでセルを受信しているため転送できない場合も（これについても下述する）、リンクフロー制御モードで動作しているとき、セットされたリンクフロー制御ステートに入って、それぞれのセットされたリンクフロー制御メッセージを生成し、他のスイッチングノード１１(n) またはそこに接続されていて、そこにセルを送信しているコンピュータ１２(m) にこれらのメッセージを送信する。これらのスイッチングノード１１(n) またはコンピュータ１２(m) がセットされたリンクフロー制御メッセージを受信したときも、それぞれのセットされたリンクフロー制御メッセージが送られてきたスイッチングノード１１(n) にセルを送信することを停止する。
【００１４】
コンピュータ１２(m) が通信リンク１３(p) を利用してスイッチングノード１１(n) からセルを受信することを再開できるようになると、クリアされたリンクフロー制御ステートに入って、クリアされたリンクフロー制御メッセージを生成し、スイッチングノード１１(n) にそのメッセージを送信する。スイッチングノード１１(n) がクリアされたリンクフロー制御メッセージを受信すると、コンピュータ１２(m) にセルを送信することを再開できるようになる。同様に、セットされたリンクフロー制御ステートで動作しているスイッチングノード１１(n) がセルを受信することを再開できるようになると、クリアされたリンクフロー制御ステートに入って、それぞれのクリアされたリンクフロー制御メッセージを生成し、スイッチングノード１１(n) および/またはそこに接続されたコンピュータ１２(m) にそのメッセージを送信することが可能になる。どちらの場合も、スイッチングノード１１(n) とコンピュータ１２(m) は、それぞれのクリアされたリンクフロー制御メッセージを受信すると、クリアされたリンクフロー制御メッセージが送られてきたスイッチングノード１１(n) またはコンピュータ１２(m) にセルを送信することを再開できるようになる。
【００１５】
仮想回線フロー制御モードとリンクフロー制御モードが別々になっていると、いくつかの利点が得られる。例えば、仮想回線フロー制御モードを使用すると、各デスティネーションコンピュータ１２(mD) が終端となっている仮想回線や、各スイッチングノード１１(n) がパスの一部となっているような仮想回線の間で、ネットワークを通るセル伝送バンド幅の公平性が全体的に保たれるようになる。また、仮想回線フロー制御モードを使用すると、過剰の輻輳が起こる可能性を低減することもできる。他方、リンクフロー制御モードを使用すると、過剰の輻輳が実際に起こったとき、そこに格納されているバッファにあふれを引き起こし、そのためにセルを紛失させるようなレートで、セルがコンピュータ１２(m) またはスイッチングノード１１(n) によって受信される可能性が防止され、あるいは少なくともその可能性が低減される。一実施形態では、種々のフロー制御メッセージ、すなわち、セットおよびクリアされた仮想回線フロー制御メッセージとセットおよびクリアされたリンクフロー制御メッセージは相対的に短いメッセージになっており、そこには、メッセージのタイプ、つまり、セットされた仮想回線フロー制御メッセージであるか、クリアされた仮想回線フロー制御メッセージであるか、セットされたリンクフロー制御メッセージであるか、クリアされたリンクフロー制御メッセージであるか、を示すメッセージタイプフラグとID部分が含まれている。ID部分があらかじめ決めた値、つまり、一実施形態では「ゼロ」になっているときは、そのメッセージは、メッセージタイプフラグの値に応じて、セットまたはクリアされたリンクフロー制御メッセージである。他方、ID部分があらかじめ決めた値とは別の値になっているときは、そのメッセージも、メッセージタイプフラグの値に応じて、セットまたはクリアされた仮想回線フロー制御メッセージであり、ID部分のその値は、そのメッセージがどの仮想回線と関連付けられているかを示している。セットおよびクリアされた仮想回線とリンクフロー制御メッセージは相対的に短いので、メッセージを転送するには、ネットワークを通る少量のバンド幅だけで十分である。
【００１６】
システム１０で使用されるフロー制御構成を詳しく説明する前に、システム１０の一実施形態で使用されるコンピュータ１２(m) とスイッチングノード１１(n) の構造と動作について説明することにする。図２は、ネットワーク１０に関連して使用されるコンピュータ１２(m) を示す機能ブロック図であり、図３は、ネットワーク１０に関連して使用されるスイッチングノード１１(n) を示す機能ブロック図である。一般的に、コンピュータ１２(m) は従来のどのタイプのコンピュータにすることも可能であり、その中には、従来のパーソナルコンピュータやコンピュータワークステーション、サーバコンピュータ、ミニまたはメインフレームコンピュータ、などが含まれている。図２に示すように、コンピュータ１２(m) は、プロセッサ２０、システムメモリ２１、大容量記憶サブシステム２２、入出力サブシステム２３およびネットワークインタフェース２４を搭載し、これらはすべて相互接続構成２５によって相互接続されている。一実施形態では、相互接続構成２５は従来のPCIバスを含んでいる。プロセッサ２０は、オペレーティングシステムの制御の下で１つまたは２つ以上のアプリケーションプログラムを処理する。ネットワーク１０を利用してデータが転送される特定のコネクションでは、
【００１７】
(i)  コンピュータ１２(m) がソースコンピュータ１２(mS) として動作しているときの転送では、プロセッサは、システムメモリ２１内にバッファ（単独には示していない）を設定し、デスティネーションコンピュータ１２(mD) となる他のコンピュータに転送されるデータブロックをそこにロードできるようになっている。
【００１８】
(ii) コンピュータ１２(m) がデスティネーションコンピュータ１２(mD) として動作しているときの転送では、プロセッサはシステムメモリ内にバッファ（これも単独には示していない）を設定し、ソースコンピュータ１２(mS) となる他のコンピュータから受信したデータブロックをそこに格納しておくことができる。説明したように、この一実施形態については、仮想インタフェースアーキテクチャ (Virtual Interface Architecture - VIA) 規格バージョン１(1997年12月16日)（Compaq Computer Corp.、Intel Corp、およびMicrosoft Corp発行）に記載されている。
【００１９】
大容量記憶サブシステムは、一般的に、プロセッサ２０によって処理可能な情報を長期間保存しておくことができる。大容量記憶サブシステム２２としては、ディスクまたはテープサブシステム、光ディスク記憶デバイス、CD-ROMのように、情報をそこにストアすることができ、および/またはそこから情報を取り出すことができるデバイスにすることができる。また、大容量記憶サブシステム２２は、オペレータによる取り外しと取り付けが可能である、取り外し可能記憶媒体を利用することが可能であるので、オペレータはプログラムとデータをコンピュータ１２(m) にロードし、処理済みデータをそこから取り出すことができる。
【００２０】
入出力サブシステム２３は、一般に、オペレータとデジタルコンピュータ１０とのインタフェースとなっている、オペレータ入出力サブシステムを含んでいる。具体的には、オペレータ入力サブシステムは、例えば、キーボードとマウスデバイスを含み、オペレータは対話方式で情報をデジタルコンピュータ１０に入力し、処理させることができる。さらに、オペレータ入力サブシステムは、オペレータがデジタルコンピュータ１０を制御できるようにするメカニズムを備えていることもある。オペレータ出力サブシステムは、ビデオディスプレイデバイスのように、デジタルコンピュータ１０が、マイクロコンピュータ１１の制御の下で、そこから処理結果をオペレータに表示するデバイスを備えることができる。さらに、ハードコピーでオペレータに出力するプリンタを備えることも可能である。
【００２１】
ネットワークインタフェース２４は、デスティネーションコンピュータ１２(mD) として動作する他のコンピュータに転送されるデータをシステムメモリ２１から取り出し、それからセルを生成し、生成されたセルを通信リンク１３(p) を利用して転送する。さらに、ネットワークインタフェース２４は、通信リンク１３(p) からセルを受信し、そこからデータを抽出し、そのデータをシステムメモリ２１内の該当バッファに転送し、そこにストアしておく。ネットワークインタフェース２４は複数のコンポーネントを含み、その中には、受信セクション３０、送信セクション３１、システムインタフェース回路３２およびフロー制御回路３３が含まれている。受信セクション３０は通信リンク１３(p) に接続され、通信リンクから送られてきたセルを受信し、受信したセルからのデータをバッファに格納し、システムインタフェース回路３２と協力して、バッファに格納されたデータを、相互接続構成２５を利用してシステムメモリ２１に転送し、コンピュータ１２(m) によって生成されるアプリケーションによる使用に備えてストアしておく。送信セクション３１はシステムインタフェース回路３２と協力して、システムメモリ２１から相互接続構成２５を利用して転送されるデータを取り出し、セルを生成し、そのセルを通信リンク１３(p) を利用して伝送する。一実施形態では、システムインタフェース回路３２はDMA（direct memory access）と同じように動作し、システムメモリ２１からデータを取り出し、送信セクション３１によって送信されるようにすると共に、受信セクション３０で受信されたデータをシステムメモリ２１に転送し、そこにストアしておく。システムインタフェース回路３２も、プロセッサ２０から制御情報を受信し、それを種々の制御レジスタ（図示せず）に格納しておくように動作する。制御レジスタは、受信セクション３０、送信セクション３１、フロー制御回路３３のオペレーションだけでなく、システムインタフェース回路３２自身のオペレーションも制御している。
【００２２】
上述したように、受信セクション３０は、コンピュータ１２(m) に接続された通信リンク13 (p) からセルを受信し、受信したセルからのデータをバッファに格納し、システムインタフェース回路３２と協力して、バッファに格納されたデータをシステムメモリ２１に転送し、そこにストアしておくように動作する。受信セクションはいくつかのコンポーネントを含み、その中には、ネットワーク受信インタフェース回路４０、受信バッファ４１、受信ホスト回路４２、受信スケジューラ４３および受信仮想回路制御回路４４が含まれている。ネットワーク受信インタフェース回路４０は”ＣＥＬＬＳ  ＩＮ”と名付けられたセルを、コンピュータ１２(m) に接続された通信リンク１３(p) から受信し、各セルのデータ部分内のデータを受信バッファ４１に格納しておく。上述したように、セルはネットワーク１０を通るように仮想回線上を伝送されるので、ネットワーク受信インタフェース回路４０は、特定の仮想回路に関連するセルからのデータを、受信バッファ４１に集約しておくのが一般である。一実施形態では、受信バッファ４１に格納されていて、特定の仮想回線に関連するデータはリンクリスト (linked list) にストアされ、ネットワーク受信インタフェース回路４０が特定の仮想回線に関連するセルを受信すると、そのセルからのデータを受信バッファに格納しておき、そのセルが関連付けられていた仮想回線に関連するリンクリストの最後にそのデータをリンクするようにしている。
【００２３】
受信仮想回線制御回路４４は、そこを通ってセルがネットワークインタフェース２４に送られてきた各仮想回線の情報をストアしておく。そのような情報としては、各々の仮想回線ごとに、送られてきたデータをストアしておくシステムメモリ２１内のロケーションを指すポインタと、仮想回線、およびその仮想回線に関連し、そのデータが現在受信バッファ４１に格納されている受信セルの数を示しているバッファ内セル数の値に関連するリンクリストがあれば、そのヘッドおよびテールのロケーションを指すポインタとが含まれている。受信バッファ４１が特定の仮想回線に関連するセルからの、どのデータも格納していない間は、受信仮想回線制御回路４４は仮想回線にリンクリストが存在しないことを示しているが、仮想回線に関連する少なくとも１つのセルからのデータが存在する間は、受信仮想回線制御回路４４は仮想回線のリンクリスト情報を収めている。以上から理解されるように、受信バッファ４１が特定の仮想回線に関連する１つのセルだけからのデータを格納しているときは、ヘッドポインタとテールポインタは同じロケーションを指している。つまり、そのデータをストアしている受信バッファ４１内のロケーションを指している。受信セルからのデータがネットワーク受信インタフェース回路４０にあって、そのデータが受信バッファ４１に格納されているときは、ネットワーク受信インタフェース回路４０は、受信仮想回線制御回路４４内の情報を使用して、仮想回線にリンクリストが存在するかどうかを判断することができる。受信仮想回線制御回路４４が仮想回線にリンクリストが存在しないことを示している場合は、ネットワーク受信インタフェース回路４０は、セルからのデータがストアされていた受信バッファ４１内のロケーションを指すポインタを、リンクリストのヘッドとテールの両ポインタとして受信仮想回線制御回路４４にロードし、バッファ内セル数の値をインクリメントすることができる。この条件では、バッファ内セル数の値は「１」になる。他方、リンクリストが存在することを受信仮想回線制御回路４４が示していれば、ネットワーク受信インタフェース回路４０はストアしたばかりのデータを、仮想回線に関連するリンクリストのテールにリンクし、仮想回線のほうは受信セルと関連付けられる。さらに、ネットワーク受信インタフェース回路４０は、受信仮想回線制御回路４４内のテールポインタを、ストアしたばかりのデータのロケーションをリンクリストの新しいテールとして指すように更新する。
【００２４】
受信ホスト４２はバッファ内データを受信バッファ４１から取り出し、システムインタフェース回路３１と協力して、そのバッファ内データを、相互接続構成２５を利用してシステムメモリ２１に転送してストアしておく。受信ホスト４２は受信仮想回線制御回路４４内の仮想回線情報も利用して、各特定仮想回線に関連していて、ストアのためにシステムメモリ２１に転送されるデータが、受信バッファ４１内のロケーションを判別する。具体的に説明すると、受信ホスト４２が特定の仮想回線の受信バッファ４１からデータを取り出して、システムメモリ２１に転送しようとするとき、その受信ホスト４２は、仮想回線のリンクリストのヘッドロケーションを指しているヘッドポインタを利用することができる。一実施形態では、ネットワークインタフェース２４は、１つのセルまたは複数セルのブロックからのバッファ内データを、相互接続構成２１を利用して一回の転送でシステムメモリ２１に転送することができる。いずれの場合も、受信ホスト４２がセルに関連する受信バッファからのデータを、そのセルの仮想回線に関連するリンクリストの先頭から取り出したあと、その受信ホストは受信回線制御回路４４によって維持されている仮想回線のヘッドポインタを、仮想回線のデータがストアされている次のロケーションがリンクリストの受信バッファ４１にあれば、そのロケーションを指すように更新し、仮想回線のバッファ内セル数の値をデクリメントする。取り出したばかりのデータがその仮想回線の最後のデータであれば、受信ホスト４２はバッファ内セル数の値をデクリメントすることにより、仮想回線に関連するリンクリストが受信バッファ４１に存在しないことを示すことができる。
【００２５】
受信スケジューラ４３は、ネットワーク受信インタフェース回路４０が受信ホスト４２と通信して、受信ホスト４２によって実行される上述のオペレーションのスケジューリングを制御できるようにする。また、受信スケジューラ４３は、プロセッサ２０が受信ホスト４２と通信して、コンピュータ１２(m) によって処理されるアプリケーションプログラムの制御の下で、受信ホスト４２によって実行される、ある種のオペレーションを制御し、例えば、それぞれの仮想回線に関連するセルに入って受信されたデータがシステムメモリ２１内のどのバッファにストアされるかを、受信ホスト４２に通知する。プロセッサ２０、ネットワーク受信インタフェース回路４０および受信ホスト４２に関連して受信スケジューラ４３によって実行されるオペレーションは、図５を参照して以下に説明されている。
【００２６】
上述したように、送信セクション３１はシステムインタフェース回路３２と協力して、相互接続構成２５を利用してシステムメモリ２１から送信されるデータを取り出し、セルを生成し、そのセルを通信リンク１３(p) 上を伝送する。送信セクション３１はいくつかのコンポーネントを含み、その中には、送信ホスト５０、送信バッファ５１、ネットワーク送信インタフェース回路５２、送信スケジューラ５３、および送信仮想回線制御回路５４が含まれている。
【００２７】
送信ホスト５０は、システムインタフェース回路３１と協力して、通信リンク１３(p) 上をセルに入れて送信されるデータを、システムメモリ２１から相互接続構成２５を利用して取り出し、それを（つまり、取り出したデータを）送信バッファ５１に格納する。送信仮想回線制御回路５４は各仮想回線の情報をストアするが、この情報の中には、送信されるデータがそれぞれの仮想回線に関して取り出されるシステムメモリ２１内のロケーションを指すポインタと、仮想回線ステータス（状況）情報が含まれている。受信バッファ４１と同じように、送信バッファ５１は、特定の仮想回線に関連するセルに入れて送信されるデータを集約してリンクリストに入れておき、送信仮想回線制御回路５４は、リンクリストのヘッドポインタとテールポインタ、および送信バッファが送信されるデータを格納しようとしている各仮想回線のバッファ内セル数の値もストアしている。従って、送信ホスト５０が転送されようとするデータで、特定の仮想回線に関連付けられていているデータを送信バッファ５１にストアするとき、送信仮想回線制御回路５４内の仮想回線の情報にアクセスし、仮想回線に関連する送信バッファにリンクリストが存在するかどうかを判断する。そのようなリンクリストが存在しないと送信ホスト５０が判断したときは、つまり、仮想回線に関連するバッファ内セル数の値が「ゼロ」の値になっているときは、その送信ホスト５０は、データがストアされている送信バッファ５１内のロケーションを指すポインタが、仮想回線のヘッドとテールの両ポインタとなるようにし、送信仮想回線制御回路５４内のバッファ内セル数の値をインクリメントすることができる。他方、送信バッファ５１にストアしたばかりのデータが送信される仮想回線にリンクリストが存在すると送信ホスト５０が判断したときは、その送信ホスト５０は、受信仮想回線制御回路４４によって維持されている仮想回線のテールポインタを、データがストアされていた送信バッファ５１内のロケーションを指すように更新し、仮想回線のバッファ内セル数の値をインクリメントする。
【００２８】
ネットワーク送信インタフェース回路５２は送信バッファ５１からデータを取り出し、”ＣＥＬＬＳ  ＯＵＴ”と名付けたセルをそのデータから生成し、コンピュータ１２(m) に接続された通信リンク１３(p) を利用して送信する。このオペレーションでは、ネットワーク送信インタフェース回路５２が特定の仮想回線に関連するデータを送信バッファ５１から取り出すとき、仮想回線に関連するリンクリストの先頭からデータを取り出し、このオペレーションでは、その特定仮想回線の送信仮想回線制御回路５４にストアされているリンクリスト情報、具体的にはヘッドポインタを使用する。ネットワーク送信インタフェース回路５２がセルに関連する送信バッファ５１からのデータを、そのセルの仮想回線に関連するリンクリストの先頭から取り出したあと、このネットワーク送信インタフェース回路５２は送信仮想回線制御回路５４によって維持されている仮想回線のヘッドポインタを、データが仮想回線に関してストアされている次のロケーションがリンクリストの受信バッファ４１にあれば、そのロケーションを指すように更新し、仮想回線のバッファ内セル数の値をデクリメントする。取り出したばかりのデータが仮想回線の最後のデータであれば、ネットワーク送信インタフェース回路５２は、バッファ内セル数の値をゼロにデクリメントすることにより、仮想回線に関連するリンクリストが送信バッファ５１にないことを示すことができる。
【００２９】
送信スケジューラ５３は、送信ホスト５０がネットワーク送信インタフェース回路５２と通信して、ネットワーク送信インタフェース回路５２によって実行される上述のオペレーションのスケジューリングを制御できるようにする。また、送信スケジューラ５３は、プロセッサ２０が送信ホスト５０と通信して、コンピュータ１２(m) によって処理されるアプリケーションプログラムの制御の下で送信ホスト５０による、ある種のオペレーションを制御し、例えば、それぞれの仮想回線に関連するセルに入れて送信されるデータが、システムメモリ２１内のどのバッファにストアされているかを送信ホスト５０に通知できるようにする。送信スケジューラ５３に関連してプロセッサ２０、送信ホスト５０およびネットワーク送信インタフェース回路５２によって実行されるオペレーションは、図６を参照して以下に説明されている。
【００３０】
本発明の一側面によれば、フロー制御回路３３は、以下に関連するいくつかのオペレーションを実行する。
【００３１】
(i)  送信セクション３１によるセルの伝送レートを制御する。
【００３２】
(ii) 送信セクションが仮想回線フロー制御メッセージとリンクフロー制御メッセージを、必要に応じて通信リンク１３(p) を利用して送信できるようにする。
【００３３】
上記 (i) に関しては、フロー制御回路３３は、
(a)  セットされた仮想回線フロー制御メッセージを受信したあと、クリアされた仮想回線フロー制御メッセージが受信されるまで送信セクション３１が特定の仮想回線に関連するセルを送信することを禁止する。セットされた仮想回線フロー制御メッセージを受信したあと、フロー制御回路３３は、送信ホスト５０がシステムメモリ２１からデータを取り出し、そのデータをその仮想回線を利用して送信することを禁止する（一実施形態では、ネットワーク送信インタフェース５２は、以前に取り出されたデータで、送信バッファ５１に格納されているデータのセルの送信を続けることが可能になっている）。
【００３４】
(b)  セットされたリンクフロー制御メッセージを受信したあと、クリアされたリンクフロー制御メッセージが受信されるまでネットワーク送信インタフェース５２がセルを通信リンク１３(p) を利用して送信することを禁止する。
【００３５】
上記 (ii) に関しては、フロー制御回路３３は、ネットワーク送信インタフェース５２によって送信されるセットおよびクリアされた仮想回線とリンクフロー制御メッセージを、受信バッファ４１に置かれている総データ量（以下では、「総受信バッファ占有レベル(total receive buffer occupancy level)」と呼ぶことにする）と特定の仮想回線の受信バッファ４１に格納されているデータ量（以下では、仮想回線ごとの受信バッファ占有レベル(per-virtual circuit receive buffer occupancy level)）と呼ぶことにする）に基づいて生成し、フロー制御回路３３は、受信仮想回路制御回路４４内の情報に基づいてデータ量を判断することができる。フロー制御回路３３によって実行されるある種のオペレーションは、図４に示すフロー図を参照して以下に説明されている。一般的に、フロー制御回路３３は４つのステート（状態）で動作するが、その４ステートとは、非フロー制御(non-flow controlled) ステート、通常輻輳(normal congestion) ステート、中輻輳(medium congestion) ステート、および高輻輳(high congestion) ステートである。これらのステートは、種々のしきい値を基準にした総受信バッファ占有レベルによって判断される。従って、フロー制御回路３３は、総受信バッファ占有レベルが相対的に低い「非フロー制御」しきい値以下にあれば、非フロー制御ステートで動作することになる。他方、フロー制御回路３３は、総受信バッファ占有レベルが非フロー制御しきい値と若干高い「輻輳モード」しきい値の間にあれば、通常輻輳ステートで動作し、総受信バッファ占有レベルが輻輳モードしきい値と相対的に高い「リンクモード」しきい値の間にあれば、中輻輳ステートで動作し、総受信バッファ占有レベルがリンクモードしきい値以上であれば、高輻輳ステートで動作することになる。フロー制御回路３３は、
(a)  非フロー制御ステートで動作しているときは、ネットワーク送信インタフェース回路５２がセットされた仮想回線またはリンクフロー制御メッセージを送信するのを禁止し、仮想回線ID順のラウンドロビン方式で、セットされた仮想回線フロー制御ステートにある仮想回線をクリアされた仮想回線フロー制御ステートにし、ネットワーク送信インタフェース回路５２がそのためにクリアされた仮想回線フロー制御メッセージを送信することを可能にする。
【００３６】
(b)  通常輻輳ステートで動作しているときは、
(I)  その仮想回線ごとの受信バッファ占有レベルが選択した仮想回線ごとの総受信バッファフロー制御しきい値以上にある各仮想回線については、仮想回線をセットされた仮想回線フロー制御ステートにし、ネットワーク送信インタフェース回路５２がそのためにセットされた仮想回線フロー制御メッセージを送信することを可能にする。しかし、
(II)  セットされた仮想回線フロー制御ステートにあるが、その仮想回線ごとの受信バッファ占有レベルが選択した仮想回線ごとの受信バッファフロー制御しきい値以下にある仮想回線については、仮想回線ID順のラウンドロビン方式で、仮想回線をクリアされた仮想回線フロー制御ステートにし、ネットワーク送信インタフェース回路５２がそのためにクリアされた仮想回線フロー制御メッセージを送信することを可能にする。
【００３７】
(c)  中輻輳ステートで動作しているときは、受信セクションがセルを受信するときの各仮想回線をセットされた仮想回線フロー制御モードにし、ネットワーク送信インタフェース回路５２がそのためにセットされた仮想回線フロー制御メッセージを送信するのを可能にする。
【００３８】
(d)  高輻輳ステートで動作しているときは、ネットワーク送信インタフェース回路５２がそのためにセットされたリンクフロー制御メッセージを送信することを可能にする。
フロー制御回路３３が高輻輳ステートから他のステートのいずれかにシーケンスした場合は、ネットワーク送信インタフェース回路５２がそのためにクリアされたリンクフロー制御メッセージを送信することを可能にする。通常輻輳ステートにあるとき、セットされた仮想回線フロー制御ステートにあるが、その仮想回線ごとの受信バッファ占有レベルが選択した仮想回線ごとの受信バッファフロー制御しきい値以下にある仮想回線を、仮想回線ID順のラウンドロビン方式でクリアされた仮想回線フロー制御ステートにシーケンスするようにすると、フロー制御回路３３は、仮想回線間である程度の公平性が得られるようにする。
【００３９】
クリアされた仮想回線とリンクフロー制御メッセージを生成し、送信するかどうかを判断するためにフロー制御回路３３によって実行されるオペレーションは、図４に示すフローチャートを参照して以下に説明されている。図４に示すように、フロー制御回路３３は、まず、仮想回線ポインタを設定し、初期化し（ステップ１００）、このポインタは、仮想回線をセットされた仮想回線フロー制御ステートからクリアされた仮想回線フロー制御ステートに仮想回線ID順のラウンドロビン方式でシーケンスするとき使用される。そのあと、フロー制御回路３３は、セットされた仮想回線フロー制御ステートにある仮想回線があるかどうかを判断する（ステップ１０１）。フロー制御回路３３がステップ１０１で否定の判断をしたときは、セットされた仮想回線フロー制御ステートからクリアされた仮想回線フロー制御ステートにシーケンスする必要のある仮想回線がないために、フロー制御回路３３はステップ１０１に戻ることになる。
【００４０】
他方、フロー制御回路３３がステップ１０１で肯定の判断をしたときは、セットされた仮想回線フロー制御ステートからクリアされた仮想回線フロー制御ステートにシーケンスする必要のある仮想回線があるために、フロー制御回路３３は、中または高輻輳ステートで動作しているかどうかを判断する（ステップ１０２）。フロー制御回路３３が高または中輻輳ステートで動作している間は、どの仮想回線もセットされた仮想回線フロー制御ステートからクリアされた仮想回線フロー制御ステートにシーケンスすることがないので、フロー制御回路がステップ１０２で肯定の判断をしたときは、ステップ１０１に戻ることになる。
【００４１】
他方、フロー制御回路３３がステップ１０２で否定の判断をしたときは、非フロー制御ステートまたは通常輻輳ステートで動作しているので、その仮想回線ごとの受信バッファ占有レベルが選択した仮想回線受信バッファフロー制御しきい値以下にある仮想回線を、仮想回線ID順のラウンドロビン方式でクリアされた仮想回線フロー制御ステートにシーケンスし、ネットワーク送信インタフェース回路５２がクリアされた仮想回線フロー制御メッセージを、それに対し送信することを可能にする。従って、フロー制御回路３３がステップ１０２で否定の判断をしたときは、ステップ１００で設定された仮想回線ポインタを、セットされた仮想回線フロー制御ステートにある、次の仮想回線を指すようにインクリメントする（ステップ１０３）。そのあと、フロー制御回路３３は非フロー制御ステートで動作しているかどうかを判断し（ステップ１０４）、動作していれば、仮想回線ポインタが指している仮想回線をクリアされた仮想回線フロー制御ステートに配置し（ステップ１０５）、ネットワーク送信インタフェース４２がクリアされた仮想回線フロー制御メッセージを、それに対して送信することを可能にする（ステップ１０６）。そのあと、フロー制御回路３３はステップ１０１に戻る。
【００４２】
ステップ１０４に戻って説明すると、フロー制御回路３３が非フロー制御ステートで動作していないと、そのステップで判断した場合は、通常輻輳ステートで動作している。従って、フロー制御回路３３は、仮想回線ポインタが指している仮想回線はその仮想回線ごとの受信バッファ占有レベルが、選択した仮想回線ごとの受信バッファ占有レベルしきい値以下にあるかどうかを判断することになる（ステップ１０７）。フロー制御回路３３がそのステップ１０７で肯定の判断をしたときは、ステップ１０５にシーケンスして、仮想回線ポインタが指している仮想回線をクリアされた仮想回線フロー制御ステートに配置し、そのあと、ネットワーク送信インタフェース４２がクリアされた仮想回線フロー制御メッセージを、それに対して送信することを可能にする（ステップ１０６）。他方、フロー制御回路３３がステップ１０７で否定の判断をしたときは、仮想回線ポインタが指している仮想回線の仮想回線ごとのバッファ占有レベルは選択したしきい値以上であるので、フロー制御回路３３は、仮想回線をクリアされた仮想回線フロー制御ステートに配置することなくステップ１０１に戻る。
【００４３】
図２に戻って説明すると、本発明の別の側面によれば、上述したように、受信スケジューラ４３は、ネットワーク受信インタフェース回路４０とプロセッサが受信ホスト４２と通信して、受信ホスト４２によって実行される種々のオペレーションのスケジューリングを制御することを可能にする。受信スケジューラ４３は、「ドアベル(doorbell)」タスク、高優先度データ転送タスク、およびメッセージ終わりデータ転送タスクといった、いくつかの高優先度クラスのタスクと、低優先度データ転送タスクといった、１つの低優先度クラスのタスクを用意している。一実施形態では、特定の仮想回線に関連するプロセッサ２０（図２）は、特定の仮想回線のために利用可能な制御情報があるとき、「ドアベル」メカニズムを利用して、受信ホスト４２または送信ホスト５０にシステムインタフェース３２を通してそのことを選択的に通知する。ドアベルメカニズムは、受信ホスト４２または送信ホスト５０の各々のためにワークキュー (work queue)（単独には示されていない）を選択的に用意し、プロセッサ２０は、システムメモリ２１にストアされている、それぞれの仮想回線の制御ブロック（これも単独には示されていない）を指すポインタをそのワークキューにロードする。各制御ブロック（前記のVIA規格では「記述子(descriptor)」と呼ばれている）は、仮想回線のための種々タイプのコマンドと制御情報を収めており、この中には、例えば、ネットワークインタフェース２４がそのデスティネーションとなっている仮想回線に関しては、仮想回線の受信セクション３０によって受信されたメッセージのデータがストアされるシステムメモリ２１内のそれぞれのバッファを指している１つまたは２つ以上のポインタが含まれており、あるいはネットワークインタフェース２４がそのデスティネーションとなっている仮想回線に関しては、仮想回線上を伝送されるデータを収容しているシステムメモリ２１内のそれぞれのバッファを指している１つまたは２つ以上のポインタが含まれている。プロセッサ２０は、制御ブロックを指しているポインタを、仮想回線に関連するワークキューにロードすることによって、受信ホスト４２が仮想回線に関連するドアベルタスクを実行できるようにする。特定の仮想回線に関連するドアベルタスクの実行中に、受信ホスト４２はワークキューに置かれている最初のポインタが指している制御ブロックからコマンドと制御情報を取り出し、その処理を行う。受信ホスト４２は、カレントドアベルタスクに関して実行される追加作業があれば、仮想回線に関連するドアベルタスクを使用可能にすることもできる。さらに、受信ホスト４２は、セットされたメッセージ終わりフラグに関連する受信バッファ４１からデータを仮想回線に対して転送していた場合、および仮想回線に関連するワークキューに後続制御ブロックを指すポインタが置かれている場合、仮想回線に関連するドアベルタスクを使用可能にすることができる。このようにすると、受信ホスト４２は、例えば、システムメモリ２１内の別のバッファを指しているポインタを取得し、そのバッファに仮想回線のデータをストアしておくことができる。
【００４４】
仮想回線に関連する高優先度データ転送タスクを使用すると、受信ホスト４２は、仮想回線のデータを受信バッファ４１からシステムメモリ２１に高優先度順に転送することができる。一般的に、受信ホスト４２は、あらかじめ決めたデータ量がその仮想回線の受信バッファ４１に累積されると、仮想回線のデータをシステムメモリ２１に転送する。一実施形態では、このあらかじめ決めた量は、受信ホスト４２が高優先度データ転送タスクに従ってデータを転送する場合、データブロックが相互接続構成２５上を効率よく転送されるように選択されている。高優先度データ転送タスクは、受信ホスト４２自身によって使用可能にすることができるが、ネットワーク受信インタフェース４０によって使用可能にされるのが一般的である。ネットワーク受信インタフェース４０が仮想回線に関連する高優先度データ転送タスクを使用可能にできるのは、受信バッファ４１内の仮想回線のリンクリストにセルからのデータをロードするとき、リンクリスト内のデータ量があらかじめ決めたしきい値にあるか、またはそれ以上になった場合である。さらに、受信ホスト４２は、仮想回線に対していずれかのタスクを実行したあと、受信バッファ４１内の仮想回線のリンクリストにデータがある場合、仮想回線に関連する高優先度データ転送タスクを使用可能にすることができる。
【００４５】
仮想回線に関連するメッセージ終わりデータ転送タスクを使用すると、受信ホスト４２は、仮想回線に対してセルが受信され、そのセルがメッセージの最後のセルであるとき、仮想回線のデータを受信バッファ４１からシステムメモリに高優先度順に転送することができる。メッセージ終わりデータ転送タスクは、受信バッファ４１に累積されたデータ量が高優先度データ転送タスクを使用するのに十分でない場合でも、メッセージ終わりに関するデータが確実にシステムメモリ２１に転送されるようにする。ネットワーク受信インタフェース４０は、受信バッファ４１内の仮想回線のリンクリストにセルからのデータをロードするとき、セルがセットされたメッセージ終わりフラグを含んでいた場合、仮想回線に関連するメッセージ終わりデータ転送タスクを使用可能にすることができる。さらに、受信ホスト４２は、仮想回線に対していずれかのタスクを実行したあと、受信バッファ４１に格納されている仮想回線のデータがセットされたメッセージ終わりフラグを含んでいたセルからのものであった場合、仮想回線に関連する高優先度データ転送タスクを使用可能にすることができる。
【００４６】
最後に、仮想回線に関連する低優先度タスクを使用すると、受信ホストは、仮想回線のデータを受信バッファからシステムメモリ２１に低優先度順に転送することができる。仮想回線に対して実行すべき高優先度タスクが受信ホスト４２にないときは、受信ホストは低優先度データ転送タスクを実行して、データを仮想回線のシステムメモリに転送する。以上から理解されるように、受信ホスト４２が仮想回線に対して低優先度データ転送タスクを使用して、しばらくの間データを転送していないと、仮想回線に対する十分なデータ量が受信バッファ４１に累積されるので、高優先度データ転送タスクを使用した転送が保証されることになる。ネットワーク受信インタフェース４０は、受信バッファ４１内の仮想回線のリンクリストにセルからのデータをロードするとき、仮想回線に関連する低優先度データ転送タスクを使用可能にすることができる。
【００４７】
一般的に、受信スケジューラ４３は、少なくとも１つのタスクが使用可能にされている仮想回線の中で、受信ホスト４２がどの仮想回線に対してタスクを実行すべきかを識別する。受信スケジューラ４３は、どの仮想回線に対して高優先度クラスのタスクが使用可能であるかを、仮想回線ID順のラウンドロビン方式で識別する。どの仮想回線に対しても高優先度クラスのタスクが使用可能になっていなければ、受信スケジューラ４３は、どの仮想回線に対して低優先度クラスのタスクがスケジュールされているかを、この場合も、仮想回線ID順のラウンドロビン方式で識別する。いずれの場合も、受信スケジューラ４３は、どの仮想回線に対してタスクが実行されるかを、そのIDで受信ホスト４２に知らせるようになっている。受信ホスト４２側は、通知された仮想回線に対して高優先度クラスのどのタスクを実行すべきかを、受信仮想回線制御回路４３に維持されているその仮想回線のカレントステートに基づいて判断し、そのタスクを実行することになる。仮想回線に対して実行すべき高優先度クラスのタスクがないと受信ホスト４２が判断した場合は、受信ホストは低優先度クラスのタスクを実行することになる。受信ホスト４２が通知された仮想回線に対して少なくとも１つのタスクを実行したあと、受信ホスト４２はそのことを受信スケジューラに通知し、さらに、仮想回線の、そのときのカレントステート（これは、タスクが実行されたあとの仮想回線のステートである）に応じて、その仮想回線に対して後続タスクを使用可能にすることができる。受信スケジューラ４３が、受信ホスト４２が通知された仮想回線に対してタスクを実行したとの通知をその受信ホスト４２から受け取ると、その受信スケジューラ４３は、タスクが使用可能にされる次の仮想回線を仮想回線ID順に通知し、そのあと上述したオペレーションが繰り返される。
【００４８】
上述したように、受信ホスト４２は、どの仮想回線に対してタスクを実行すべきかをそのIDで通知を受けたあと、どのタスクを実行すべきかを、通知された仮想回線のカレントステートから判断する。例えば、転送すべき仮想回線のデータが受信バッファ４２にあると受信ホスト４２が判断したとき、データをストアしておくシステムメモリ２１内のバッファを指すポインタを有しなければ、受信ホスト４２は、ポインタを取り出すためにドアベルタスクを実行する。そのあと、受信ホスト４２はドアベルタスク、高優先度データ転送タスク、メッセージ終わりデータ転送タスクのいずれかを、仮想回線のバッファに格納されているデータが、メッセージ終わりフラグがセットされていたセルと関連しているかどうかに応じて使用可能にする。他方、どの仮想回線に対してタスクを実行すべきかをそのIDで通知を受けたあと、受信ホストがデータをストアしておくシステムメモリ２１内のポインタを有していれば、受信ホストは１ブロックまでのデータを、システムインタフェース３２および相互接続構成２５上を経由してシステムメモリ２１に転送することを開始できる。そのあと、受信ホスト４２はドアベルタスク、高優先度データ転送タスク、メッセージ終わりデータ転送タスクのいずれかを、仮想回線のバッファに格納されたデータが、メッセージ終わりフラグがセットされていたセルと関連があるかどうかに応じて使用可能にすることができるが、そうしなくてもよい。
【００４９】
図５は、本発明の一実施形態で使用される受信スケジューラ４３を示す機能ブロック図である。図５に示すように、受信スケジューラ４３は、高優先度データ転送メモリ８０(1)、ドアベルメモリ８０(2)、メッセージ終わりデータメモリ８０(3) および低優先度データ転送メモリ８０(4) を含む複数のメモリ、メモリアクセスアービタ (memory access arbiter) ８１、タスクコントロール８２、および複数のマルチプレクサ８３および８４を搭載している。メモリ８０(1) 乃至８０(4) の各々は一連のビットを含み、ネットワークインタフェース２４がそのデスティネーションとなっている仮想回線ごとに１ビットが割り当てられている。一実施形態では、仮想回線IDは10ビットであるので、各メモリ８０(1) 乃至８０(4) は1024（つまり、210）ビットからなり、各ビットは、仮想回線が特定の符号化用に設定されているかどうかに関係なく、仮想回線IDの１つの取り得るバイナリ符号化と関連付けられている。この実施形態では、各メモリ内のビット(i)（インデックス”ｉ”  はゼロから1023までの範囲）は、ネットワークインタフェース２４がデスティネーションとなっているのときの、そのID用に仮想回線が設定されているかどうかに関係なく、ID “ｉ”  をもつ仮想回線と関連付けられている。メモリ８０(1) 乃至８０(4)内の「ｉ番目」ビットがセットされたときは、関連タスク（つまり、高優先度データ転送タスク、ドアベルタスク、メッセージ終わりデータ転送タスクまたは低優先度データ転送タスク）は「ｉ番目」仮想回線に対して使用可能にされる。
【００５０】
タスクコントロール８２はビットの状態を表す信号をメモリから受信し、RCV_HOST_CTRL受信ホスト制御信号のうち該当する信号を通して、どの仮想回線に対して受信ホスト４２にタスクを実行させるかを通知する。さらに、タスクコントロール８２は、メモリ８０(1) 乃至８０(4)の１つの中の、通知された仮想回線に関連するビットのリセットを行う。タスクコントロール８２がどの仮想回路であるかを、メモリ８０(1) 乃至８０(3)の１つの中の、仮想回線のビットがセットされていることに基づいて識別した場合は、タスクコントロール８２は、メモリ８０(1) 乃至８０(3)の１つの中の、仮想回線のビットがリセットされるようにするが、このリセットはメモリ８０(1) 乃至８０(3)の間で、ラウンドロビン方式で行われる。タスクコントロール８２は、HI_PRI_TASK_RST_REQ高優先度タスクリセット要求信号、DOORBELL_TASK_RST_REQドアベルタスクリセット要求信号、LOW_PRI_TASK_RST_REQ低優先度タスクリセット要求信号のうち該当する信号をアサートすることによって、このオペレーションを使用可能にし、その信号はマルチプレクサ８３によってマルチプレクサ８４の一方の入力に結合される。マルチプレクサ８４の方は、この信号をSEL_TASK_RST_REQ選択タスクリセット要求信号としてメモリアクセスアービタ８１に結合する。アービタがSEL_TASK_RST_REQ信号を選択したときは、メモリ８０(1) 乃至８０(3)のうちの、該当メモリの仮想回線のビットがリセットされる。
【００５１】
他方、タスクコントロール８２がどの仮想回線であるかを、メモリ８０(4) 内の仮想回線のビットがセットされていることに基づいて識別した場合は（これは、受信ホスト４２に低優先度データ転送タスクを実行させる場合である）、タスクコントロール８２は、メモリ８０(4) 内の仮想回線のビットがリセットされるようにする。タスクコントロール８２は、LOW_PRI_TASK_RST_REQ低優先度タスクリセット要求信号をアサートすることによって、このオペレーションを使用可能にし、この信号はマルチプレクサ８４の一方の入力に結合される。マルチプレクサ８４の方は、信号をSEL_TASK_RST_REQ選択タスクリセット要求信号としてメモリアクセスアービタ８１に結合する。アービタがSEL_TASK_RST_REQ信号を選択したときは、メモリ８０(4) の仮想回線のビットがリセットされる。
【００５２】
システムインタフェース３２を経由するプロセッサ２０からのドアベル要求に応答して、あるいはネットワーク受信インタフェース４０または受信ホスト４２からのドアベル要求に応答してメモリにアクセスして、メモリ内のビットのセットを容易にすることも、メモリアクセスアービタ８１によって制御される。ネットワーク受信インタフェース４０とシステムインタフェース３２からは、特定の仮想回線に対する、それぞれのNWK_RCV_INTF_REQ受信インタフェース、SYS_INTF_REQシステムインタフェース、およびRCV_VC_CTRL_REQ受信仮想回線制御セット要求をメモリアクセスアービタ８１に対して出して、その特定仮想回線に関連するメモリ８０(1) 乃至８０(4) の１つの中のビットをセットする。メモリアクセスアービタ８１がNWK_RCV_INTF_REQ、SYS_INTF_REQまたはRCV_VC_CTRL_REQ要求を選択したときは、メモリ８０(1) 乃至８０(4)の１つの中のビットがその特定仮想回線に対してセットされる。一般的に、ドアベルメモリ８０(2) 内のビットは、システムインタフェース３２からのSYS_INTF_REQに応答してセットされ、システムインタフェース３２の方は、プロセッサ２０からの要求に応答してドアベルタスクを使用可能にする。他方、高優先度データ転送メモリ８０(1)、メッセージ終わりデータ転送メモリ８０(3) または低優先度データ転送メモリ８０(4) 内のビットは、一般的には、ネットワーク受信インタフェース４０が特定仮想回線に関連する、１つまたは２つ以上のセルからのデータを受信バッファ４１にロードしたあとで、ネットワーク受信インタフェース４０からのNWK_RCV_INTF_REQ要求に応答してセットされる。さらに、メモリ８０(1) 乃至８０(3) のいずれかにあるビットは、受信ホスト４２からのRCV_VC_CTRL_SET_REQ要求に応答してセットされ、高優先度データ転送タスク、ドアベルタスクまたはメッセージ終わりデータ転送タスクを、それぞれ使用可能にすることができる。
【００５３】
以上から理解されるように、受信スケジューラ４３は仮想回線に関して仮想回線ID順のラウンドロビン方式でタスクを実行させるようにするので、受信スケジューラは、それぞれの仮想回線の間である程度の公平性を保つようにしている。さらに、タスクは、ネットワークインタフェース２４によって提供される種々のリソースが正しく使用されるような形で実行される。例えば、受信スケジューラ４３は、あらかじめ決めた最小データ量が転送ために受信されていない限り、受信ホスト４２が特定の仮想回線に関連するシステムメモリにデータを転送することを禁止しているのが通常で、このようにして相互接続構成２５が効率よく使用されるようにしている（これは、低優先度転送タスクの場合である）。しかし、受信バッファ４１が、少なくともあらかじめ決めた最小データ量を格納している場合は、受信スケジューラ４３は、仮想回線に関連するデータがシステムメモリ２１に転送されることを可能にする（これは高優先度転送タスクの場合である）。さらに、受信バッファ４１が仮想回線を利用したメッセージ終わり転送に関連するデータを格納している場合は、その仮想回線に対して受信された追加データがないか、あるいはその仮想回線に対して後続データが受信されるまで相対的に長い遅延があるために、受信スケジューラ４３は仮想回線に関連するデータがシステムメモリ２１に転送されることを可能にする（これも、高優先度転送タスクの場合である）。最後に、受信ホストに実行させる他のタスクがない場合は、受信スケジューラ４３は受信ホスト４２が低優先度転送を実行することを可能にする。
【００５４】
上述したように、送信スケジューラ５３は送信ホスト５０がシステムインタフェース３２およびネットワーク送信インタフェース回路５２と通信して、ネットワーク送信インタフェース回路５２によって実行される、上述のオペレーションのスケジューリングを制御することを可能にする。また、送信スケジューラ５３は、プロセッサ２０が送信ホスト５０と通信して、コンピュータ１２(m) によって処理されるアプリケーションプログラムの制御の下で送信ホスト５０によるある種のオペレーションを制御することも可能にし、例えば、それぞれの仮想回線に関連するセルに入って送信されるデータが、システムメモリ２１内のどのロケーションにストアされているかを送信ホスト５０に通知するようにする。
【００５５】
一般的に、送信スケジューラ５３は送信ホスト５０によるデータの取り出しを制御し、ネットワーク送信インタフェース５２によるその後の送信に備えてそのデータを送信バッファ５１に格納しておくようにする。さらに、上述したように、一実施形態では、特定の仮想回線に関連するプロセッサ２０（図２）は「ドアベル」メカニズムを利用して、特定の仮想回線に対して利用可能である制御情報があるとき、そのことを受信ホスト４２または送信ホスト５０に選択的に通知することにより、送信ホスト５０がシステムメモリ２１内の仮想回線の制御ブロック（個別には示されていない）から仮想回線の情報を選択的に取り出すことを可能にする。特定の仮想回線に関連するドアベルタスクの実行中に、送信ホスト５０は、受信ホスト４２に関して上述したのと同じように、仮想回線の制御ブロックからコマンドと制御情報を取り出し、その処理を行う。優先度順に、送信スケジューラ５３は送信ホスト５０が次のことを行うことを可能にする。
【００５６】
(i)  最高優先度順では、あらかじめ決めた数の仮想回線に関連するドアベルタスクを処理すること。この処理はドアベルタスクを実行しようとする仮想回線に対して仮想回線ID順のラウンドロビン方式で行われる。
【００５７】
(ii) 中間優先度順では、システムメモリからデータを選択的に取り出し、送信バッファ５１にストアしておくこと。この取り出しは、セットされた仮想回線フロー制御モードになっていないか、あるいはそうでなくても、あらかじめ決めた最大数の仮想回線に関して伝送が制限されない仮想回線に対して仮想回線ID順のラウンドロビン方式で行われる。
【００５８】
(iii) 最低優先度順では、システムメモリからデータを選択に取り出し、送信バッファ５１にストアしておくこと。この取り出しは、伝送が制限されていて、セットされた仮想回線フロー制御モードになっていない仮想回線に対して仮想回線ID順のラウンドロビン方式で行われる。
上記項目 (iii) に関して、伝送が制限されている仮想回線としては、伝送が特定の伝送レートに制限されている仮想回線がある。受信スケジューラ４３の場合と同じように、送信スケジューラ５３は特定の優先度レベル内にある仮想回線に関して仮想回線ID順のラウンドロビン方式で動作するので、送信スケジューラはその優先度レベルでオペレーションが実行される、それぞれの仮想回線の間で、ある程度の公平性を保証している。さらに、送信スケジューラ５３は、優先度レベル内のあらかじめ決めた最大数の仮想回線に関連するオペレーションを実行したあと、次に低い優先度レベルに移るので、送信スケジューラは異なる優先度レベルにある仮想回線の間で、ある程度の公平性を保証している。
【００５９】
送信スケジューラ５３の機能ブロック図は図６に示されている。図６に示すように、送信スケジューラ５３はドアベルメモリ９０(1)、２つの高優先度メモリ９０(2) と９０(3)、低優先度メモリ９０(4)、および送信タスクコントロール９１を含んでいる。メモリの各々は、それぞれのタスクを実行しようとする仮想回線のIDをストアしており、このIDは送信タスクコントロール９１が使用して、送信ホストがそれぞれのタスクを実行できるようにする。メモリ９０(1) 乃至９０(4) の各々は一連のビットを含み、ネットワークインタフェース２４がそのソースとなっている仮想回線ごとに１ビットが割り当てられている。一実施形態では、仮想回線IDは10ビットになっているので、各メモリ９０(1) 乃至９０(4)は1024（つまり、210）ビットを含み、各ビットは、仮想回線が特定の符号化用に設定されていたかどうかに関係なく、仮想回線IDの１つの取り得るバイナリ符号化と関連付けられている。この実施形態では、各メモリ内のビット（ｉ）（インデックス”ｉ”  はゼロから１０２３までの範囲）は、ネットワークインタフェース２４がそのソースとなっている、そのID用に仮想回線が設定されていたかどうかに関係なく、ＩＤ  “ｉ”  をもつ仮想回線と関連付けられている。
【００６０】
ドアベルメモリ９０(1) は、ドアベルタスクが処理されようとする仮想回線のIDをストアしている。受信スケジューラ４３側のドアベルメモリ８０(1) の場合と同じように、仮想回線と関連付けられている、送信スケジューラ５３側のドアベルメモリ９０(1) のビットは、プロセッサ２０からのその要求に応答してセットされ、ドアベルタスクが送信セクション３１によって実行されるようにする。送信ホスト５０が新しいメッセージのデータを取り出して、仮想回線上を送信しようとすると、送信タスクコントロール９１は高優先度メモリ９０(2) 内にある、仮想回線に関連するビットをセットする。送信しようとするメッセージが相対的に長いときは、送信ホスト５０がそのメッセージのデータの一部を取り出したあとで、送信タスクコントロール９１は高優先度メモリ９０(2) 内にある、仮想回線に関連するビットをリセットし、高優先度メモリ９０(3) 内にある、仮想回線に関連するビットをセットする。送信ホスト５０が、伝送レートが制限されている仮想回線のデータを取り出そうとしたときは、送信タスクコントロール９１は、低優先度メモリ９０(4) 内にある、仮想回線に関連するビットをセットする。
【００６１】
送信タスクコントロール９１はそれぞれのメモリ９０(1) 乃至９０(4) 内のビットを使用して、どの仮想回線に対してドアベルまたはデータ取り出しオペレーションが、各メモリ内で仮想回線ID順のラウンドロビン方式で実行されるのかを示すようにする。１つまたは２つ以上のビットがドアベルメモリ９０(1) 内でセットされ、プロセッサ２０がそれぞれの仮想回線に関連してドアベルタスクが実行されることを可能にしていた場合は、送信タスクコントロール９１は、送信ホスト５０およびシステムインタフェース３２と協力して、仮想回線の制御ブロックから情報を取り出し、ドアベルタスクを処理する。メッセージが仮想回線上を送信される場合は、仮想回線が伝送レート制限されていなければ、仮想回線に関連するビットが高優先度メモリ９０(2) 内でセットされ、仮想回線が伝送レート制限されていれば、低優先度メモリ９０(4) 内でセットされる。これらのオペレーションは、ドアベルメモリ９０(1) 内のそれぞれのビットが仮想回線ID順のラウンドロビン方式でセットされている仮想回線に対して繰り返される。
【００６２】
あらかじめ決めた数の仮想回線に対してドアベルメモリ９０(1) を使用して一連のドアベルタスクが処理されたあとで、メモリ９０(2) 乃至９０(4) のビットの中にセットされているビットがあり、データがシステムメモリ２１から取り出されて少なくとも１つの仮想回線に対して送信されようとしていれば、送信タスクコントロール９１は送信ホスト５０がそのオペレーションを開始できるようにする。一般的に、これらのオペレーションでは、送信タスクコントロール９１は、送信ホスト５０が一連の繰り返しで、高優先度メモリの１つ９０(2) または９０(3) に示されている、あらかじめ決めた数の仮想回線上を送信されるデータを取り出すことを可能にし、そのあとで、低優先度メモリ９０(4) に示されている、あらかじめ決めた数の仮想回線上を送信されるデータを取り出すことを可能にし、メモリ９０(2) と９０(3) はある繰り返しと次の繰り返しの間に交互に切り替わるようになっている。送信タスクコントロール９１は、一連のドアベルタスクが終わるたびに、送信ホスト５０が１つの繰り返しを実行できるようにする。各メモリ９０(2) 乃至９０(4) を使用して行われる取り出しに関しては、その取り出しは、各メモリ内の連続するビットを使用して仮想回線に対して仮想回線ID順のラウンドロビン方式で行われる。
【００６３】
以上から理解されるように、送信スケジューラ５３は、上述したように、どの仮想回線に対してデータが取り出されるのかを示し、送信ホスト５０は実際にデータ取り出しオペレーションを実行する。一般的に、データ取り出しオペレーションでは、仮想回線がセットされた仮想回線フロー制御モードにあるときは、上述したように、送信ホスト５０は仮想回線に対するどのデータも取り出さない。同様に、(i) 送信バッファ５１が仮想回線に関連する、あらかじめ決めた数の完成セルに関連するデータを収容しているか、あるいは(ii) 送信バッファ５１があらかじめ決めたデータ量を超えるデータを収容していると、送信ホストは、(ii) に関して、少なくとも一部のデータが１つまたは２つ以上の未完成セルと関連していない限り、仮想回線に対してどのデータも取り出さず、その場合には、送信ホスト５０はセルを完成するのに十分なデータだけを取り出す。その他の場合は、送信ホスト５０は、システムメモリ２１からあるブロックのデータを取り出し、そのサイズは、好ましくは、セル内のデータ量から、送信バッファ５１にすでに格納されている未完成セルのデータ量を差し引いた倍数になっており、ブロックのサイズは相互接続構成２５上を効率よく転送されるサイズになっている。
【００６４】
２つのメモリ９０(2) と９０(3) を使用して、どの非レート制限仮想回線に対してデータが送信のために取り出されるのかを識別するようにし、送信スケジューラ５３が連続する繰り返しでそれらのメモリ間を交互に切り替わるようにし、上述したように、送信ホスト５０にデータブロックを取り出させるようにすると、当然に理解されるように、相対的に短いメッセージに関連するセルは妥当なレイテンシで伝送されることになる。以上の結果、少なくとも交互に切り替わる繰り返しの間は、メモリ９０(2) は、どの仮想回線に対してデータが送信ホスト５０によって取り出されるのかを示すために使用される。上述したように、メモリ９０(2) は、少なくともメッセージ始まりのデータが、どの仮想回線に対して送信ホスト５０によって取り出されるのかを示している。仮想回線のメッセージが相対的に短ければ、送信ホスト５０は、仮想回線のビットがメモリ９０(2) にセットされている繰り返しの間に、そのメッセージのデータをすべて取り出すので、メッセージは他の仮想回線に関連する相対的に長いメッセージによって遅延されることがない。しかし、メッセージのデータ量が十分に大きいために繰り返しの間にそのデータを取り出すことができない場合は、メモリ９０(2) 内の仮想回線に関連するビットはリセットされるが、メモリ９０(3) 内の仮想回線に関連するビットはセットされ、その場合には、そのビットがメモリ９０(3) にセットされている仮想回線で仮想回線ID順のラウンドロビン方式で仮想回線がサービスを受けているとき、仮想回線に関連する、もっと多くのデータを取り出すことが可能になる。
【００６５】
図３は、図１に示すネットワーク１０で使用すると便利なスイッチングノード１１(n) を示す機能ブロック図である。図３に示すように、スイッチングノード１１(n) は、複数の入力ポート６０(1) 乃至６０(I)（全体を符号６０(i) で示している）、複数の出力ポート６１(1) 乃至６１(I)（全体を符号６１(i) で示している）、バッファストア６３およびバッファマネージャ６４を装備している。各入力ポート６０(i) は”ＣＥＬＬＳ＿ＩＮ”と名付けたセルを、コンピュータ１２(m) またはスイッチングノードから通信リンク１３(p) を利用して受信するように接続されている。各出力ポート６１(i) は”ＣＥＬＬＳ＿ＯＵＴ”と名付けたセルを、通信リンク１３(p) を利用してコンピュータ１２(m) またはスイッチングノードに送信するように接続されている。入力ポート６０(i) がスイッチングノードからセルを受信し、出力ポート６１(i) がセルをスイッチングノードに送信する場合、スイッチングノード１１(n) の入力ポート６０(i) がそこからセルを受信し、あるいはスイッチングノード１１(n) の出力ポート６１(i) がそこへセルを送信するスイッチングノードは、好ましくは、別のスイッチングノード１１（ｎ’）  （ｎ’≠n) になっているが、通信リンク１３(p) がスイッチングノード１１(n) のループバックコネクションとなっていれば、同一のスイッチングノード１１(n) であっても構わない。
【００６６】
各入力ポート６０(i) は、そこに接続された通信リンク１３(p) 上でセルを受信すると、そのセルをバッファストア６３に格納する。各入力ポート６０(i) は、実際にセルを受信し、それをバッファに格納してからセルがバッファストア６３に転送されて、そこに格納されるようにするセルレシーバ７０と、入力ポート６０(i)がそこでセルを受信する仮想回線に関する仮想回線情報を収めている入力ポートコントロール７１とを含んでいる。一実施形態では、セルレシーバ７０は、受信したセルのための内部「ダブルバッファ」構成（個別には示されていない）を備えている。具体的には、一方の内部バッファは、バッファストア６３に転送される前に受信したばかりのセルの少なくとも一部を収容しておくことができ、その間に、別のセルの一部は他方の内部バッファに受信されている。
【００６７】
セルレシーバ７０がセルを受信すると、入力ポートコントロール７１はそのセルをバッファストア６３に転送し、そこにストアしておく。一般的に、バッファストア６３は複数の”B”バッファBUF0 乃至BUF(B-1)（全体をBUF(b) で示している）から構成され、これらはバッファマネージャ６４内のバッファリンクヘッダ７５によってリンクリストに編成されている。バッファBUF(b) の各々は、１つのセルからの情報をストアすることができる。一般的に、バッファストア６３とバッファマネージャ６４はスイッチングノード１１(n) を通る仮想回線ごとに１つのリンクリストを提供し、さらにフリーリストを提供する。他方、バッファリンクヘッダ７５は複数のバッファヘッダBUF_HDR(0) 乃至BUF_HDR(B-1)（全体をBUF_HDR(b) で示している）を含み、その各々はバッファストア６３内の対応するインデックスをもつBUF(b) と関連付けられている。各入力ポート６０(i) の入力ポートコントロール７１は仮想回線情報ブロック（個別には示されていない）を維持しており、そこには、特に、ヘッドポインタとテールポインタを含むリンクリストヘッダとバッファカウント値が、入力ポート６１(i) がそのパスとなっている仮想回線ごとに、収められている。さらに、バッファマネージャ６４は、フリーリストのヘッドポインタとテールポインタを含むフリーリストポインタをもっている。
各リンクリストについて、
【００６８】
(i)  ヘッドポインタは次を指している。  
(a)  仮想回線のリンクリストの場合は、仮想回線のバッファストア６３に格納されている第１セルの情報を収めているバッファBUF(b) に関連するバッファヘッダBUF_HDR(b)、または
(b) フリーリストの場合は、フリーリスト内の第１バッファBUF(b) に関連するバッファヘッダBUF_HDR(b)。
【００６９】
(ii)  テールポインタは次を指している。
【００７０】
(a)  仮想回線のリンクリストの場合は、仮想回線のバッファストア６３に格納されている最終セルの情報を収めているバッファBUF(b’) に関連するバッファヘッダBUF_HDR(b’)、または
(b) フリーリストの場合は、フリーリスト内の最終バッファに関連するバッファヘッダBUF_HDR(b)。
【００７１】
(iii) バッファカウント値は、仮想回線のリンクリストの場合は、リンクリストにリンクされたバッファストア６３内のバッファの数を示している。
以上から理解されるように、ヘッドポイントが指しているバッファBUF(b) はテールポインタが指しているものと同じバッファBUF(b’) にすることができるが、そうでなくてもよい。ヘッドポインタが指しているバッファBUF(b) が、テールポインタが指している同じBUF(b’) であれば、バッファストア６３内のリンクリストに関連するバッファBUF(b) は１つになる。さらに、各バッファヘッダBUF_HDR(b) は、リンクリスト内の最終バッファヘッダを除き、リンクリスト内の次のバッファヘッダBUF_HDR(b”) を指している次ポインタを含んでいる。リンクリスト内の最終バッファヘッダ内の次ポインタは、リンクリストのリストヘッダを指していることもあれば、それがリンクリスト内の最終バッファヘッダであることを示している値を含んでいることもある。仮想回線に関連するリンクリストの場合には、バッファBUF(b”) は、スイッチングノード１１(n) によって受信され、その情報が同じ仮想回線のバッファBUF(b) にストアされているセルの後に続く次のセルの情報をストアしている。
【００７２】
一般的に、セルをバッファストア６３にストアするとき、入力ポートコントロール７１は、フリーリストのヘッドに置かれているバッファヘッダBUF_HDR(b) に関連するバッファBUF(b) にそのセルをストアし、フリーリストヘッダのヘッダポインタとバッファカウントをそれに応じて更新する。さらに、入力ポートコントロール７１は、
【００７３】
(i)  仮想回線の仮想回線情報ブロック内のバッファカウント値が非ゼロで、アクティブのリンクリストが仮想回線のバッファストア６３とバッファマネージャ６４にあることを示していれば、仮想回線の仮想回線情報ブロック内に維持されているテールポインタが指しているバッファヘッダの次ポインタを更新し、
【００７４】
(ii) セルがストアされているバッファBUF(B) に関連するバッファヘッダBUF_HDR(b) の次ポインタに値をロードし、それがリンクリスト内の最終バッファヘッダであることを示し、
【００７５】
(iii) 仮想回線に関連する仮想回線情報ブロックに維持されている、リンクリストヘッダ（必要に応じてヘッドポインタとテールポインタを含んでいる）とセルカウント値を更新する。
各仮想回線に対して入力ポートコントロール７１によって維持されている仮想回線情報ブロックは、仮想回線に関連するセルがどの出力ポート６１(i’) から送信されるのかも示しており、入力ポートコントロール７１は、リンクリストを確立したあと、その出力ポート６１(i’)から送信されるために仮想回線に対してセルが受信されたことも、出力ポート６１(i’)に通知する。
【００７６】
各出力ポート６１(i’)は、少なくとも１つのセルが、その出力ポート６１(i’)からセルが送信される仮想回線のバッファストア６３に格納されているとの通知を、入力ポート６０(i) の入力ポートコントロール７１から受信すると、それが接続されている通信リンク１３(p)が、クリアされたリンクフロー制御ステートになっていれば、仮想回線に関連するセルをバッファストア６３から取り出し、そのセルをそこに接続されている通信リンク１３(p) 上に送出するオペレーションを開始する。以上から理解されるように、出力ポート６１(i) が接続されている通信リンク１３(p) が、セットされたリンクフロー制御ステートになっていれば、出力ポート６１(i) は仮想回線に関連するセルを通信リンク上に送信することが禁止される。
【００７７】
各出力ポート６１(i) は出力ポートコントロール７２とセルトランスミッタ７３を含んでいる。出力ポートコントロール７２は、それぞれの入力ポート６０(i) の入力ポートコントロール７１から通知を受信する。これに応答して、通信リンク１３(p) が、セットされたリンクフロー制御ステートになっていれば、出力ポートコントロール７２は、入力ポートコントロール７１によって維持されている仮想回線の仮想回線情報ブロックにアクセスしてリンクリストのヘッドポインタを特定し、これによって仮想回線に関連するリンクリスト内の第１セルを特定し、そのセルがバッファストア６３から取り出され、セルトランスミッタ７３に転送され、その処理および送信が行われるようにする。従来と同じように、セルのヘッダ部分は送信前に更新しておく必要があるが、これはセルトランスミッタによって行われる。セルレシーバ７０の場合と同じように、一実施形態では、別のセルの一部がそこに接続された通信リンク１３(p) 上に送信される間、セルトランスミッタ７３は送信されるセルのための内部「ダブルバッファ」（個別には示されていない）を用意しており、具体的には、一方の内部バッファはバッファストア６３から取り出されるセルの一部を収容することができる。セルが送信のために取り出されると、出力ポートコントロール７２は入力ポートコントロール７１が、セルの取り出しを反映するように、仮想回線の仮想回線情報ブロックに維持されているセルカウントをデクリメントするのを許可することができる。仮想回線情報ブロック内のセルカウント値がデクリメントされたあとゼロになっていなければ、入力ポートコントロール７１は、仮想回線のリンクリスクがまだアクティブであることを出力ポートコントロール７２に通知する。さらに、入力ポートコントロール７１は、仮想回線情報ブロック内のヘッダポインタを、リンクリスト内の次のセルを指すように更新する。出力ポートコントロール７２は、バッファストア６３に格納されている、それぞれの仮想回線のセルが残っている限り、そこから送信される仮想回線すべてのセルの取り出しを仮想回線ID順のラウンドロビン方式で開始する。
【００７８】
以上から理解されるように、入力ポート６０(i) はセル以外のメッセージを受信することができる。具体的には、本発明によるセットおよびクリアされた仮想回線フロー制御メッセージと、セットおよびクリアされたリンクフロー制御メッセージを受信することができる。入力ポート６０(i) がセットされた仮想回線フロー制御メッセージを受信した場合は、スイッチングノード１１(n) はその仮想回線に対してセットされた下流側仮想回線フロー制御ステートに入り、その場合には、入力ポート６０(i) に関連する入力ポートコントロール７１は、仮想回線に対して維持されている仮想回線情報ブロック内の下流側仮想回線フロー制御ステートフラグ（別個には示されていない）をセットし、さらに、ソースコンピュータ１２(mS)、つまり、仮想回線のソースコンピュータ１２(mS) に向かう仮想回線のパス上の上流側スイッチングノード１１(n”) に接続されている該当出力ポート６１(i”) が、セットされた仮想回線フロー制御メッセージを通信リンク１３(p) 上に送信することを許可する。
【００７９】
上述したように、スイッチングノード１１(n) は、仮想回線に関連するセルが余りに高速レートで受信されるため仮想回線上の下流側に送信できないと判断したときは、セットされた仮想回線フロー制御ステートに入って、セットされた仮想回線フロー制御メッセージを生成し、仮想回線のパス上の下流側にそれを送信することもできる。これに関連して、仮想回線の仮想回線情報ブロックを維持している入力ポート６０(i) に関連する入力ポートコントロール７１は、ローカル仮想回線フロー制御フラグも維持しており、入力ポートコントロール７１はこのフラグをセットすることにより、仮想回線をセットされたローカル仮想回線フロー制御ステートに配置することができる。入力ポートコントロール７１がローカル仮想回線フロー制御フラグをセットすると、上流側スイッチングノード１１(n”) または仮想回線のソースコンピュータ１２(mS) に接続された出力ポート６０(i”) が、セットされた仮想回線フロー制御メッセージを通信リンク１３(p) 上に送信するのを許可することもできる。仮想回線に関連するパス上の下流側スイッチングノードまたは仮想回線に関連するデスティネーションコンピュータ１２(mD) に接続された出力ポート６１(i’) は、バッファストア６３に置かれている仮想回線に関連するセルを十分な数だけ取り出したあと、ローカル仮想回線フロー制御フラグをクリアして、仮想回線をクリアされたローカル仮想回線フロー制御ステートに置くことができる。
【００８０】
下流側仮想回線フロー制御フラグとローカル仮想回線フロー制御フラグは、スイッチングノード１１(n) による仮想回線の、クリアされた仮想回線フロー制御メッセージの送信または生成を制御するためにも使用される。これに関連して、
【００８１】
(i)  入力ポート６０(i) が仮想回線に関連するクリアされた仮想回線フロー制御メッセージを受信した場合は、下流側仮想回線フロー制御フラグをクリアすると、仮想回線をクリアされた下流側仮想回線フロー制御ステートに配置することができ、仮想回線もセットされた仮想回線フロー制御ステートになっていなければ、入力ポート６０(i) は、仮想回線に関連するパス上の上流側スイッチングノード、または仮想回線に関連するソースコンピュータ１２(mS) に接続された出力ポート６０(i”) が、クリアされた仮想回線フロー制御メッセージを生成し、送信することを許可することができる。
【００８２】
(ii)  仮想回線に関連するパス上の下流側スイッチングノード、または仮想回線に関連するソースコンピュータ１２(mS) に接続された出力ポート６１(i’) がローカル仮想回線フロー制御フラグをクリアし、仮想回線をクリアされたローカル仮想回線フロー制御ステートに配置し、仮想回線もセットされた下流側仮想回線フロー制御ステートになっていなければ、出力ポート６１(i’) は、仮想回線に関連するパス上の上流側スイッチングノード、または仮想回線に関連するソースコンピュータ１２(mS) に接続された出力ポート６０(i”) が、クリアされた仮想回線フロー制御メッセージを生成し、送信するのを許可することができる。
【００８３】
本発明によれば、入力ポート７１と出力ポートコントロール７２も、特定の仮想回線をセットおよびクリアされたローカル仮想回線フロー制御ステートに配置するべきかどうかの判断に関して、および特定の通信リンク１３(p) をセットまたはクリアされたリンクフロー制御ステートに配置するかどうかに関して、いくつかのオペレーションを実行する。最初に、ローカル仮想回線フロー制御ステートに関しては、仮想回線のローカル仮想回線フロー制御ステートをセットするか、クリアするかの判断は、次に基づいて行われる。
【００８４】
(i)  仮想回線に関連するパス上の下流側スイッチングノードまたは仮想回線に関連するデスティネーションコンピュータ１２(mD) に接続された出力ポート６１(i’) の出力ポート仮想回線利用数(utilization number)。
【００８５】
(ii)  バッファストア６３のセル占有レベル(cell occupancy level)。
【００８６】
(iii)  バッファストア６３に格納されている、仮想回線に関連するセルの数。
出力ポート６１(i’)の出力ポート仮想回線利用数は、出力ポート６１(i’)によって送信されるセルをバッファストア６３がストアしている仮想回線の数を示している。上述したように、出力ポート６１(i) は仮想回線のセルを仮想回線ID順のラウンドロビン方式で取り出すために、特定の出力ポート６１(i’)の出力ポート仮想回線利用数が増加すると、特定の仮想回線の取り出しと取り出しの間の時間が増加するので、バッファストア６３のセル占有レベル（上記項目(ii)）が増加し、特定の仮想回線に関連するセルの数（上記項目(iii)）も増加すると、望ましくない輻輳が発生することになる。
【００８７】
一実施形態では、出力ポートコントロール７２は、各出力ポート６１(i) に対して３つの出力ポート仮想回線利用レベル（上記項目(i)参照）、すなわち、低利用レベル、通常利用レベル、高利用レベルを定義している。出力ポート６１(i) によって送信されるセルをバッファストア６３がストアしている仮想回線の数が、
(a)  選択した低出力ポート利用しきい値以下であれば、出力ポートコントロール７２は、出力ポート６１(i) が低利用レベルにあると判断する。
(b)  選択した低出力ポート利用しきい値と選択した高出力ポート利用しきい値の間にあれば、出力ポートコントロール７２は、出力ポート６１(i) が通常利用レベルにあると判断する。
【００８８】
(c)  高出力ポート利用しきい値を越えていれば、出力ポートコントロール７２は、出力ポートが高利用レベルにあると判断する。
さらに、出力ポートコントロールは、１つのバッファ占有しきい値（上記項目(ii) 参照）と、３セットのバッファ格納セル「ウォータマーク(watermark)」レベル（上記項目(iii)参照）を定義している。各セットのバッファ格納セルウォータマークレベルは、バッファストア６３に格納されている、仮想回線に関連するセルがある数に達すると、仮想回線がセットされたローカル仮想回線フロー制御ステートに配置されることを示し、バッファ格納セル数がある数に達すると、仮想回線がクリアされたローカル仮想回線フロー制御ステートに配置されることを示している。バッファ格納セルウォータマークのセットは、低バッファ格納セルウォータマークレベル、中間バッファ格納セルウォータマークレベル、および高バッファ格納セルウォータマークレベルを含んでおり、これらは、その数に達すると仮想回線がセットされたローカル仮想回線フロー制御ステートに配置され、その数に達すると仮想回線がクリアされたローカル仮想回線フロー制御ステートに格納される、仮想回線に関連する両方のバッファ格納セル数が、連続的に大きくなることを定義している。
【００８９】
入力ポートコントロール７１は出力ポート仮想回線利用レベルとバッファ占有レベルを使用して、バッファ格納セルウォータマークのセットの１つを選択し、これは仮想回線をセットまたはクリアされた仮想回線フロー制御ステートに配置するべきかどうかを判断するために使用される。これに関連して、バッファストア６３のセル占有レベルが、各仮想回線についてバッファ占有しきい値以下であると出力ポートコントロール７２が判断したとき、
【００９０】
(i)  仮想回線に関連するセルを送信のために取り出す出力ポート６１(i’) に関連する仮想回線利用レベルが低利用レベルにあれば、入力ポートコントロール７１は高バッファ格納セルウォータマークレベルのセットを選択する。
【００９１】
(ii)  仮想回線に関連するセルを送信のために取り出す出力ポート６１(i’) に関連する仮想回線利用レベルが中間利用レベルにあれば、入力ポートコントロール７１は中間バッファ格納セルウォータマークレベルのセットを選択する。
【００９２】
(iii)  仮想回線に関連するセルを送信のために取り出す出力ポート６１(i’) に関連する仮想回線利用レベルが高利用レベルにあれば、入力ポートコントロール７１は低バッファ格納セルウォータマークレベルのセットを選択する。
他方、バッファストア６３のセル占有レベルが、各仮想回線についてバッファ占有しきい値にあるか、あるいはそれを越えていると入力ポートコントロール７１が判断したとき、
【００９３】
(iv)  仮想回線に関連するセルを送信のために取り出す出力ポート６１(i’) に関連する仮想回線利用レベルが低利用レベルにあれば、入力ポートコントロール７１は中間バッファ格納セルウォータマークレベルのセットを選択する。
【００９４】
(v)  仮想回線に関連するセルを送信のために取り出す出力ポート６１(i’) に関連する仮想回線利用レベルが中間利用レベルにあれば、入力ポートコントロール７１は低バッファ格納セルウォータマークレベルのセットを選択する。
【００９５】
(vi)  仮想回線に関連するセルを送信のために取り出す出力ポート６１(i’) に関連する仮想回線利用レベルが高利用レベルにあれば、この場合も、入力ポートコントロール７１は低バッファ格納セルウォータマークレベルのセットを選択する。
【００９６】
以上から理解されるように、仮想回線利用レベルが増加すると共に、仮想回線をセットされた仮想回線フロー制御ステートに配置するために必要とされる、仮想回線に関連するバッファ格納セルの数は少なくなる。しかし、バッファストア６３のバッファ占有レベルが増加してバッファ占有しきい値を越えると、バッファ格納セルウォータマークレベルが選択されるので、仮想回線をセットされた仮想回線フロー制御ステートに配置するために必要とされる、仮想回線に関連するバッファ格納セルの数は少なくなる。入力ポートコントロール７１は各仮想回線に対して選択されたバッファ格納セルウォータマークレベルセットの中のウォータマークレベルを使用して、仮想回線をセットまたはクリアされたローカル仮想回線フロー制御ステートに配置するために、ローカル仮想回線フロー制御フラグをセットするか、クリアするかを判断する。
【００９７】
一実施形態では、各バッファ格納セルウォータマークレベルセット内で、その数に達すると、仮想回線がクリアされたローカル仮想回線フロー制御ステートに配置される、バッファストア６３に格納されているセルの数を識別するバッファ格納セルウォータマークレベルは、その数に達すると、仮想回線がセットされたローカル仮想回線フロー制御ステートに配置される、バッファストア６３に格納されているセルの数を示しているバッファ格納セルウォータマークレベルよりも低くなっている。このようにすると、ある程度の「ヒステリシス」が得られるので、特定の仮想回線に関連するバッファストア６３に格納されているセルの数が該当ウォータマークレベルに近づいたときセルがスイッチングノード１１(n) によって取り出されて、送信される場合、特定の仮想回線に関連するローカル仮想回線フロー制御ステートが、セットされたステートとクリアされたステートの間で急激に切り替わることが有効に防止されることになる。
【００９８】
さらに、入力ポートコントロール７１は、スイッチングノード１１(n) またはそこに接続された特定の通信リンク１３(p) を、セットまたはクリアされたリンクフロー制御ステートにいつ移行させるかを判断し、その判断に応じて出力ポート６１(i) によるリンクフロー制御メッセージの送信を制御する。一般的に、入力ポート６０(i) の入力ポートコントロール７１は、
【００９９】
(i)  バッファストア６３のセル占有レベルが、選択したセットされたリンクフロー制御しきいレベルを超えるレベルに増加したときは、スイッチングノード１１(n) に接続された通信リンク１３(p) をセットされたリンクフロー制御ステートに配置し、その場合には、入力ポートコントロール７１は対応するインデックスをもつ出力ポート６１(i) が、セットされたリンクフロー制御メッセージを送信することを許可し、そのあと、
【０１００】
(ii)  スイッチングノード１１(n) をクリアされたリンクフロー制御ステートに配置し、
(a)  バッファストア６３のセル占有レベルが選択した、クリアされたリンクフロー制御しきいレベル以下のレベルに減少したときは、通信リンク１３(p) をクリアされたリンクフロー制御ステートに配置し、その場合には、入力ポートコントロール７１は、対応するインデックスをもつ出力ポート６１(i) が、クリアされたリンクフロー制御メッセージをスイッチングノード１１(n) またはそこに接続されたコンピュータ１２(m) に送信することを許可し、あるいは
(b)  仮想回線に関連付けられていて、それぞれの入力ポート６０(i) から受信されたバッファストア６３に格納されているセルの数があらかじめ決めた入力ポートごとのしきいレベルに等しいか、または低いときは、入力ポート６０(i) に接続された通信リンク１３(p) をクリアされたリンクフロー制御ステートに配置し、その場合には、入力ポート６０(i) の入力ポートコントロール７１は、対応するインデックスをもつ出力ポート６１(i) がスイッチングノード１１(n) またはそこに接続されたコンピュータ１２(m) にクリアされたリンクフロー制御メッセージを送信することを許可する。一実施形態では、入力ポートごとのしきいレベルはゼロになるように選択されている。
一実施形態では、セットされたリンクフロー制御しきいレベルは、クリアされたリンクフロー制御しきいレベルよりも大になっている。このようにすると、ある程度の「ヒステリシス」が得られるので、特定の仮想回線に関連するバッファストア６３に格納されているセルの数がセットされたリンクフロー制御しきいレベルに近づいたときセルがスイッチングノード１１(n) によって受信され、送信される場合、リンクフロー制御ステートが、セットされたステートとクリアされたステートの間で急激に切り替わることが有効に防止されることになる。
【０１０１】
バッファリンクヘッダ７５のほかに、バッファマネージャはアービタ７６も含んでおり、このアービタ７６は、入力ポートコントロール７１と出力ポートコントロール７２によるバッファストア６３へのアクセス、バッファマネージャ６４によって維持されているバッファリンクヘッダ７５へのアクセス、および入力ポート６１(i) の各々の入力ポートコントロール７１によって維持されている仮想回線情報へのアクセスをスケジュールする。一般的に、
【０１０２】
(i)  入力ポート６０(i) の入力ポートコントロール７１は、仮想回線に関連するセルを受信するとき、次のものにアクセスする必要がある。
(a)  バッファストア６３内のどのバッファBUF(b) にセルをストアしようとしているのかを識別するために、およびフリーリストのリンクリスト情報を更新するためにフリーリストについて、バッファマネージャ６４によって維持されているリンクリスト情報、
(b)  示されたバッファに受信セルをストアするためにバッファストア６３、
(c)  そこからリンクリスト情報を取り出し、そのリンクリスト情報、セルカウント値および仮想回線のフロー制御ステータスを更新するために、さらに、どの出力ポート６１(i) からセルが送信されるかを示すために、入力ポートコントロール７１によって維持されている仮想回線情報ブロック、および
(d)  受信セルがストアされたバッファをフロー制御のリンクリストにリンクするために、入力ポートコントロール７１によって維持されている仮想回線情報ブロック内のリンクリスト情報によって示されている、仮想回線に関連するリンクリストについてバッファマネージャによって維持されているリンクリスト情報。
【０１０３】
(ii)  出力ポート６１(i) の出力ポートコントロール７２は、仮想回線に関連するセルを送信しようとするとき、次のものにアクセスする必要がある。
(a)  リンクリスト情報を取り出し、リンクリスト情報とセルカウント値を含む情報を更新するために、さらに、仮想回線のフロー制御ステータスを必要に応じて更新するために、そこからセルが受信された仮想入力ポートコントロール７１によって維持されている仮想回線情報、
(b)  バッファから送信するためのセルを取り出すために、バッファストア６３、および
(c)  仮想回線のリンクリストからセルが送信されるバッファをデリンク(de-link)し、バッファをフリーリストにリンクするために、バッファマネージャによって維持されているリンクリスト情報。
【０１０４】
一般的に、アービタ７６は、入力ポート６１(i) の入力ポートコントロール７１と出力ポート６１(i) の出力ポートコントロール７２によるアクセス要求の仲裁を行う。このオペレーションでは、一実施形態によれば、アービタ７６は、一般的に入力ポートコントロール７１相互間にラウンドロビン方式で高い優先度をもたせ、出力ポートコントロール７２相互間にラウンドロビン方式で低い優先度をもたせるようにしている。
【０１０５】
本発明によれば、いくつかの利点が得られる。上述したように、本発明は、コンピュータと他のデバイス間でメッセージをネットワーク上に効率よく転送すると共に、ネットワークの輻輳が原因で起こるセル損失を防止する構成を提供している。ネットワークインタフェース２４の送信セクション３１によるデータ伝送は、コンピュータ１２(m) がそのソースとなっている仮想回線間で、仮想回線ID順のラウンドロビン方式で行われるので、本発明によれば、そこから延長された仮想回線間でかなりの公平性が得られ、仮想回線すべてに少なくとも一部のメッセージ転送バンド幅を効果的に保証し、仮想回線間のメッセージ転送レイテンシを制限するので、決定的なメッセージ転送レイテンシ特性が得られるようにしている。仮想回線間の公平性は、スイッチングノードが、仮想回線に対してそこで受信したセルからのデータを、仮想回線ID順のラウンドロビン方式で転送し、各デスティネーションコンピュータ側では、ネットワークインタフェースの受信セクション３１が、コンピュータ１２(m) がそのデスティネーションとなっている仮想回線上でそこで受信したセルからのデータを、仮想回線ID順のラウンドロビン方式でシステムメモリ２１に転送し、受信バッファ４１がいずれかの仮想回線からのデータで過負荷状態になる可能性を低減することによって、さらに向上されている。本発明によれば、スイッチングノード１１(n)、具体的には、バッファストア６３で使用されるメモリ量を低減化でき、望ましいメッセージ転送飽和特性が得られるので、システムコストを低減化することができる。
【０１０６】
上述したように、本発明によれば、「エンドツーエンド」仮想回線とリンクフロー制御のメカニズムが効率化されているので、ネットワークの輻輳が原因で起こるセル損失がされに防止される。仮想回線フロー制御に関しては、本発明によれば、それぞれのデスティネーションコンピュータとソースコンピュータ１２(m) 間の仮想回線を利用したセルの伝送を、仮想回線が仮想回線のセルを転送し、デスティネーションコンピュータが仮想回線を利用してセルを受信するパスを形成しているスイッチングノードの瞬時容量に基づいて制御するようにメカニズムが効率化されている。さらに、リンクフロー制御に関しては、本発明によれば、各通信リンク上のセルの伝送を、それぞれのリンクを利用してセルを受信するデバイスの瞬時容量に基づいて制御し、それぞれのリンクを利用してセルを受信するメカニズムが別になっている。仮想回線フロー制御は、仮想回線フロー制御が実現されているしきいレベルが、仮想回線のそれぞれを利用した転送レートが大きくなって、セルが転送される他の仮想回線が利用できるバンド幅が不当に制限されることがないように選択されているので、仮想回線間の公平性をさらに向上している。
【０１０７】
以上から理解されるように、上述してきたシステム１０、コンピュータ１２(m)およびスイッチングノード１１(n) は種々態様に変更することが可能である。例えば、以上から理解されるように、本発明によるシステム１０は、スイッチングノード１１(n) がなくても、複数のコンピュータ１２(m) を相互接続することにより、例えば、２つのコンピュータ１２(m) のネットワークインタフェース２４を相互接続し、これらが相互間でデータを転送するための仮想回線を確立できるようにすることによって構築することができる。さらに、以上から理解されるように、ゲートウェイ、ブリッジなどの他のタイプのコンピュータでネットワーク１０を他のネットワークに接続し、大容量記憶システムなどの、他のタイプのデバイスを、コンピュータ１２(m) について上述したのと同じように、メッセージのソースおよび/またはデスティネーションなどのネットワークに接続することも可能である。
【０１０８】
さらに、システム１０は、仮想回線間の優先度を１つとしてメッセージを転送するものとして説明してきたが、以上から理解されるように、システム１０は種々の優先度レベルを取り入れることが可能である。従って、例えば、タスクが実行される各仮想回線が識別されてから１つの仮想回線が識別されるようにする、ラウンドロビン方式によるのでは、ある仮想回線を特定する回数を他の仮想回線よりも多くして、これらの仮想回線（つまり、何度も識別される仮想回線）に高い優先度をもたせることが可能である。事実、仮想回線を特定する回数を多くすると、優先度レベルを複数にすることができる。
【０１０９】
さらに、システム１０は、一方では、新規の仮想回線とリンクフロー制御技法を含み、他方では新規のスケジューリング技法を含むものとして説明してきたが、以上から理解されるように、本発明によるシステムは、どの技法を取り入れることも可能であり、上述してきた利点の少なくともいくつかを得ることができる。
【０１１０】
上述してきたシステム１０では、ラウンドロビンスケジューリング技法を利用して、それぞれの受信スケジューラと送信スケジューラ４３および５３が、どの仮想回線に対してタスクを実行するかを、仮想回線ID順のラウンドロビン方式で特定するようにようしているが、以上から理解されるように、他のラウンドロビンID方式を使用することも可能である。例えば、それぞれのタスクで種々の仮想回線IDリストを使用することが可能であり、タスクが特定の仮想回線で可能にされたとき、仮想回線のIDをリストの終わりに付加することができる。この場合には、それぞれのスケジューラは、連続するエントリからの仮想回線を、リストの先頭から特定していくことができる。以上から理解されるように、ラウンドロビン技法をスケジューラ４３および５３で使用すると、ハードウェア設計が単純化されるが、仮想回線は、そのビットがそれぞれのメモリにセットされた直後にだけ、タスク処理のために特定されることになり、このことは仮想回線間の公平性を若干損なうことになる。他方、仮想回線IDリストは、タスクが可能にされる順に仮想回線に対してタスクが実行される可能性を大にするので、仮想回線間の公平性が増加するが、ハードウェア設計は若干複雑化する。
【０１１１】
さらに、ATMセルを使用したデータ転送に関して本発明を説明してきたが、以上から理解されるように、他のデータ転送技法を使用することも可能である。
【０１１２】
以上から理解されるように、本発明によるシステムは、その全体または一部を特殊目的コンピュータまたは汎用コンピュータ、あるいはその組み合わせで構築することが可能であり、その一部は適当なプログラムで制御することができる。どのプログラムも、その全体または一部をシステムの一部にすることも、適当な方法でシステム上に格納しておくことも可能であり、あるいはその全体または一部をネットワークまたは適当な方法で情報を転送する他のメカニズムを利用して、システムに送るようにすることも可能である。さらに、以上から理解されるように、システムは、システムに直接に接続されているか、あるいはネットワークまたは適当な方法で情報を転送する他のメカニズムを利用して情報をシステムに送ることができるオペレータ入力エレメント（図示せず）を使用するオペレータから与えられた情報によって操作し、および/または他の方法で制御することができる。
【０１１３】
上述してきた説明は本発明の特定の実施形態に限定されるが、以上から理解されるように、本発明を種々態様に変更または改良することにより、本発明の利点のすべてまたは一部を達成することができる。上記実施形態およびその変形または改良形態は請求項の対象になっており、これらは本発明の真の精神と範囲に属するものである。
【符号の説明】
【０１１４】
１０  ネットワーク
１１（１）〜１１（６）  スイッチングノード
１２（１）〜１２（８）  コンピュータ
１３（１）〜１３（１７）  通信リンク
２０  プロセッサ
２１  システムメモリ
２２  大容量ストア
２３  入出力
２４  ネットワークインタフェース
２５  相互接続構成
３０  受信セクション
３１  送信セクション
３２  システムインタフェース
３３  フロー制御
６０（１）  入力ポート
６１（１）  出力ポート
６３  バッファストア
６４  バッファマネージャ
【図１】
2010081641.tif 000003
【図２】
2010081641.tif 000004
【図３】
2010081641.tif 000005
【図４】
2010081641.tif 000006
【図４Ａ】
2010081641.tif 000007
【図５】
2010081641.tif 000008
【図６】
2010081641.tif 000009