JPH11501196A - ネットワークアダプターにおけるパケットの自動再送信のための方法及び装置 - Google Patents

Abstract

(57)【要約】 コンピュータネットワークアダプターによって実行される、複数の過剰衝突の生起によって送信が中断されたパケットの自動再送信を行う方法であって、(a)過剰衝突の回数が過剰衝突限界以下である場合、送信を停止し、実質的に直ちに再びそのパケットの送信を開始するステップ、及び(b)過剰衝突の回数が過剰衝突限界を超えた場合、送信を停止し、そのパケットを廃棄するステップを含む。これは、更に、送信バッファアンダーフロー状態による不成功の送信に含まれるパケットの自動再送信も行う方法であって、(a)送信を停止するステップ、及び(b)送信閾値を増加させて予め定められた回数まで、パケットの送信を再試行するステップを含む。送信閾値は、送信の開始の前に送信バッファに格納され、送信に含まれるパケットのデータのバイト数である。最初の送信の際には、アダプターは、送信バッファに格納されるべきパケットのバイト数について小さい数を要求することが望ましい。バッファアンダーフロー状態が生起した後には、アダプターは、実質的にパケットの大部分が送信のために送信バッファに入った後にのみ、アルゴリズムに従って再試行を行う。再試行が成功すれば、アダプターが中断を発行する必要はない。

Description

【発明の詳細な説明】 ネットワークアダプターにおけるパケット の自動再送信のための方法及び装置発明の分野 本発明は、イーサネットのようなローカルエリアネットワーク（ＬＡＮ）に関 し、更に特別には、ネットワーク上の通信を制御するネットワークアダプターに 関する。本発明の背景 イーサネットは、衝突検出を具えたキャリアセンスマルチプルアクセス（ＣＳ ＭＡ／ＣＤ）に好適なネットワークアクセスプロトコルを用いるＬＡＮに対して 通常用いられる名称である。ＣＳＭＡ／ＣＤプロトコルは、345 East 45th Stre et，New York，NY，10017 USA の Institute of Electrical and Electronics E ngineers,Inc によって発行されたＡＮＳＩ／ＩＥＥＥ Ｓｔｄ．８０２．３に 定められている。この標準は１０Mbps（メガビット／秒）ＣＳＭＡ／ＣＤチャネ ル（例えば、ネットワークバス）に適用されるが、本発明はこのようなチャネル に限定されるものではなく、例えば１００Mbpsにおける他のチャネル動作にも適 用できることが理解されるべきである。 チャネルアクセスに対するＣＳＭＡ／ＣＤルールの下では、ネットワークの全 てのノードが等しいアクセス優先権を持ち、チャネルが空くと同時に送信を開始 することができる。メッセージ送信を「希望する」いずれのノードも、送信の開 始の前にチャネルが空いていることを確かめるために、最初は「聴く」でなけれ ばならない。送信を希望するノードが、パケット間遅延と呼ばれる予め定められ た時間、即ち９．６マイクロ秒間他の送信を検出しない場合に送信を開始する。 ノードはメッセージ及び制御情報を、ネットワークシステム上に、予め定められ たサイズを持ち普通パケットと呼ばれるブロックとして送出する。 本発明の理解のために、一般的に直面する、過剰衝突及びネットワークアダプ ターバッファのアンダーフローを含む、潜在的にネットワークの性能を低下させ る事象又は状態について説明することが有用と思われる。 Ａ．衝突処理及び過剰衝突 １を超えるノードが同時にチャネル上にパケットを送信すると、その結果、信 号が干渉し正しくないものになり得る。このようなチャネル上へのパケットの同 時多重送信は「衝突」と呼ばれる。 一般的に、送信を開始したノードが衝突を検出した場合、「衝突ウィンドウ」 と呼ばれる予め定められた時間送信を続け、送信を希望する全てのノードが同様 に衝突を確実に検出するようにする。衝突を検出した後で衝突ウィンドウの間ノ ードが送信するものは、一般的には、例えば、ＣＳＭＡ／ＣＤプロトコルに従っ た「１」と「０」とで変化する３２ビットの「ジャム」と呼ばれる無意味のデー タである。全ての他の「アクティブ」ノード即ちデータパケットを送信した全て の他のノードが衝突を検出し、同様に３２ビットの「ジャム」を送信する。続い て衝突を検出した全てのノードが送信を停止する。 衝突に含まれたノードは、一般に「バックオフ」と呼ばれるパケット間遅延に 付加遅延を加えた時間、送信を停止する。バックオフは、一般的にはノードによ ってランダムに選択された種々の長さを持つため、衝突に含まれる他のノードに よって導入されたバックオフと異なる。それらのそれぞれのバックオフ時間が経 過した後、アクティブノードは、それらのそれぞれのパケットを再び送信するた めに再試行を行う。バックオフ時間が種々に異なるため、再試行が成功すること 即ち、ノードが他の衝突に遭遇しないことがある。 勿論、再送信の最初の試みが成功しないこともあり得る。送信の再試行は、次 に、送信が成功するまで、又は予め定められた最大数（例えばＣＳＭＡ／ＣＤプ ロトコルに従えば１６）の試行が終わり全てが衝突によって停止するまで、バッ クオフを挟んで繰り返される。送信が成功せずに送信試行の最大数に至った場合 は、当該ノードは「過剰衝突」を経験したといわれ、送信のために準備したパケ ットを廃棄する。過剰衝突状態はネットワークの上位プロトコルレイヤに報告さ れる。これは、上位ネットワークレイヤによる回復は長いタイムアウト（例えば 数秒）の後で行われ、実質的なパケット遅延を引き起こすので、システムの効率 の低下をもたらす。更に、これは、このようなイベントの処理がプロセッサ時間 を消費するので、システムの効率の低下をもたらす。 要するに、再試行と上位プロトコルレイヤの介入との間のバックオフ時間が導 入されたことにより、過剰衝突とそれに続く再試行が、関連するパケットの送信 のための長い待ち時間を持ち込み、システムの効率を低下させる。 Ｂ．ネットワークアダプター及びバッファアンダーフロー ネットワークの動作の問題は、ネットワークの個々のノード中に位置する例え ばイーサネットアダプターのようなネットワークアダプター中で起きる。ネット ワークアダプターは、一般的にはアダプターを含むホストノードとこれが接続さ れているネットワークシステムとの間の通信を管理する。 例えば、ネットワークアダプターは、ネットワークシステムに接続されたディ スク記憶装置とホストノードのメインメモリーとの間のデータの移動を管理する 。ディスク記憶装置から上りのデータが受信される場合は、ネットワークアダプ ターがそのデータをホストノードのメインメモリーに転送し、次の処理を待つこ とができる。転送を行うために、ネットワークアダプターは、ホストノードの構 成部分が接続されているシステムバスにアクセスしなければならない。同様に、 ネットワークアダプターは、データがメインメモリーからシステムバス上に取出 された後、ネットワークに下りのデータを転送する。 ネットワークシステム及びシステムバスは共用リソースと考えることができ、 種々の方向へのデータ転送を実現するためのアクセスを仲介することが要求され る。従って、ネットワークアダプターを介するデータ転送は、共用リソースの制 御を行うことを必要とする。これは、一般的に、(i)共用リソースに対するアク セスのための要求とそれに続くアクセスの許可、及び(ii)予め定められたサイズ のデータの、共用リソースへの又は共用リソースからの「バースト」を必要とす る。共用リソースはホストノードの他の部分のための動作を行うために占拠され ることがあるので、共用リソースを常に直ちに使用できるとは限らない。共用リ ソースへのアクセスの要求の発行とその共用リソースへのアクセスの許可との間 の時間は、リソースの「待ち時間」を構成する。一般的に、待ち時間は、例えば ネットワークシステム又はシステムバスのスループット及びそれらに接続された ユニット（例えば、ホストの構成部分）の数のような、リソースの特性に応じて システム毎に変わる。 変化し得る待ち時間を調整するため、ネットワークアダプターは、一般的に受 信及び送信の両パス中にバッファメモリーを具える。受信バッファは、ネットワ ークシステムとシステムバスとの間の受信パスに沿って設置され、例えばシステ ムバスのような共用リソースへのアクセスが得られてそれへの送信を開始するこ とができるまで、入来データを一時的に格納する。 送信バッファは、システムバスとネットワークシステムとの間の送信パスに沿 って設置され、下りのデータを一時的に格納する。ネットワークシステムへのア クセスが許可されると、ネットワークに対し、一般的に予め定められた一定のレ ートで、例えばパケットのようなデータブロックが送信されなければならない。 通常、例えばシステムバスへのアクセスがまだ許可されない時であっても、送信 バッファにより、送出されるべき下りのデータを当該レートの定常的な流れとす ることができる。 或る環境の下において、バッファアンダーフローと呼ばれる問題が生起する。 バッファアンダーフローは、送信バッファ中に要求された送信レートを維持する ために充分なデータが存在せず、且つ、このデータ不足を取り除くために、例え ばシステムバスのような共用リソースに対するアクセスが得られない場合に起き る。 バッファアンダーフローは更に、例えばシステムバスのような共用リソースか ら送信バッファに入るデータのレートが、ネットワークシステム向けのバッファ 中に存在するデータのレートより低い場合に起きる。この現象は、長いシステム バス待ち時間を持つノードで起こり得る。この現象は、システムバス上の機能の 「バースト的」性質のために、システムバスの平均スループットがネットワーク システムの最大スループットより大きい場合にさえも起きる。そのシステムが通 常は長い待ち時間を持たない場合でさえ、アダプターが長いシステムバス待ち時 間に遭遇する時間間隔が存在するのである。 アンダーフロー状態が生起した場合、一般的にはそのノードはパケット送信を 停止し、パケットの未送信部分を廃棄し、そのノードのプロセッサに中断信号を 送る。この中断は、アンダーフロー状態のために送信がアボートされたことを表 示する。上位ネットワークプロトコルレイヤは、アボートされたパケットの「受 信アクノリッジ」を見ないので、結局タイムアウトになり、上述のように、この 状態から回復するための動作を開始する。これらのための上位ネットワークプロ トコルレイヤの介入は、前述のように、時間を消費し（プロセッサ時間に関して ）システムの効率の低下を招き、（パケット遅延に関して）ネットワークの効率 の低下を招く。 バッファアンダーフローを避けるため、既知のネットワークアダプターは、「 送信閾値」と呼ばれる予め定められた量のデータが送信バッファに入った後にの み送信を開始する。送信閾値は、送信されるべきパケットの全バイト数、又は、 例えば、１５１８バイトパケットのうちの１２８バイトが既に送信バッファ中に あれば、閾値に到達したというように、実質的にバイト数として設定することが できる。不幸にもこの方法は送信の開始時点で送信遅延を加える。これは、少な くとも、獲得され送信バッファに格納されるべきデータの量のために必要とされ る時間の長さに等しい。これは、「内部送信遅延」と呼ばれる。この遅延は、ベ ンチマークドライバーがアダプター上で走行する時に得られる結果を悪くし、こ の遅延がパケット間ギャップより大きい場合には、明らかに特にネットワークの スループットに影響を与える。本発明の要約 本発明は、過剰衝突状態又はバッファアンダーフロー状態のような好ましくな い送信状態の時に、共用リソースに接続され且つ送信バッファを有するコンピュ ータネットワークアダプターによって実行される、パケットの自動再送信のため の方法に存在する。この場合、そのパケットに関して以前に遭遇した衝突の数が 過剰衝突限界以下の場合は、衝突の後実質的に直ちに続いて（バックオフなしに ）再送信が行われるように設計される。本質的に、この方法は、生起する全ての 衝突の検出及び各検出された衝突の衝突計数限界までのカウントを含む。衝突計 数限界に到達する毎に、この方法においては、過剰衝突の数を表示する「過剰」 衝突カウントを増す。この過剰衝突カウントが限界を超えた場合は、この方法に おいては、パケットの再送信を停止し、アダプターの送信バッファに格納されて いるパケットのデータを廃棄する。 過剰衝突限界は一定値とすることができ、また、ネットワークのトラヒック状 態に対応して動的に決定することもできる。 本発明は、送信バッファアンダーフローにより不成功の送信試行に含まれるパ ケットの自動再送信のために、コンピュータネットワークアダプターで実行され る方法に存在する。この場合、送信閾値が、初期の送信試行についての比較的小 さい値から再送信のためのより大きい値まで増加される。この方法は、一般的に 、(a)アンダーフロー状態が発生した場合に、送信バッファを停止し且つ送信さ れたパケットのフラグメントを受信端で「ラント」パケットとして廃棄するステ ップ、及び(b)更に高い送信閾値を用いて、Ｎ回の再試行の間に遅延又はバック オフの挿入なしに、選択された試行の数（「エントリー番号」即ち「Ｎ」）まで 、実質的に直ちにパケットの他の送信を再試行するステップを含む。 初期の送信試行のためには、アダプターは、送信バッファに格納されるべきパ ケットについては小さいバイト数だけ、即ち、送信閾値について小さい値（例え ば、４バイト）を要求することが望ましい。バッファアンダーフロー状態が生起 した後には、パケットの実質的に大部分が送信のために送信バッファにエントリ ーした後でのみ、このアダプターは本発明による再試行を試みる。この要求によ り、度々初期のアンダーフロー状態の原因になるピーク待ち時間を克服するよう にする。いずれかの再試行が成功すると、アダプターは、送信失敗を通知するた めの中断を発行する必要がなくなる。アルゴリズムは、アンダーフローパケット の送信の再試行をカウントすることができ、そのカウントをネットワーク又はシ ステムに対して、監視のために報告することができる。 更に特別には、共用リソースにデータを送信するために共用リソースに接続さ れたアダプターの動作について、本発明は、バッファアンダーフローが生起した 場合に、パケット送信及びパケット送信の自動再試行を行うための方法を提供す る。本発明による方法は、(A)予め定められた第１の量のデータが前記アダプタ ーの送信バッファに格納された後に送信を開始するステップ、(B)次にバッファ アンダーフロー状態が生起した場合は送信を停止し、第１の量のデータより多い 予め定められた第２の量のデータが送信バッファに格納された後にのみ再び送信 を開始するステップ、及び(C)ステップ(B)の後実質的に直ちに、再び送信を開 始し、パケットの送信の完了又は再試行の数即ちカウントに対して予め選択され た限界のいずれかに到達するまでの回数、ステップ(B)及びこのステップ(C)をこ の順序で繰り返すステップを含む。後者の場合、この方法では送信バッファ中の パケットのデータを廃棄し、アンダーフロー状態を表示する信号を発生する。 以下に説明する方法は、バッファアンダーフロー状態に続いて、及び過剰衝突 状態に続いて、パケットの自動再送信を行うことができる方法である。この観点 によれば、パケットの送信の間に送信バッファアンダーフロー状態が生起した場 合は、この方法においては、パケットの送信を停止し、パケットの第２の量のデ ータが送信バッファに格納された後にのみ再びそのパケットの送信を開始する。 第２のデータ量は、アンダーフロー状態を引き起こした送信が試行される前に送 信バッファに格納することが必要とされたデータ量より大きい。この方法では、 ネットワークのトラヒック状態に対応して、過剰衝突限界及び第２のデータ量の 両者を動的に決定することができる。これに代えて、過剰衝突限界及び第２のデ ータ量を予め一定値に定めておくことができる。 更に特別には、本発明によって提供される方法は、ネットワークアダプターに より、過剰衝突状態に続いてデータのパケットの自動再送信を実行することがで きる。パケットの送信は、予め定められたバイト数のパケットが送信可能になっ た後に開始される。衝突が検出されると、衝突カウントを増し、衝突カウントが 、本質的に「過剰衝突」を決める例えば１６のような予め定められた第１限界を 超えていない場合は、他の送信の試行が実行される。（勿論、アンダーフロー状 態のような他の状態が生起した場合には送信を中断することができるが、このよ うな他の状態は、この場合の範囲に入っていない。）衝突カウントが第１限界を 超えた場合は、この方法は複数のステップを実行する。第１に、再試行（ＲＮＥ Ｃ）カウントが第２限界を超えた場合はパケットの送信を停止し、第２に、ＲＮ ＥＣカウントが第２限界を超えない場合はＲＮＥＣカウントを増し、この方法は 増加されたＲＮＥＣカウントを用いて再び前のステップを実行する。このため、 本発明の送信開始ステップは、第１限界と第２限界との積、即ち、衝突カウント の最大値とＲＮＥＣカウントの最大値との積に等しい回数まで実行される。 従って、本発明は、再試行間のバックオフタイムを導入する必要性を除去し、 上位プロトコルレイヤの大部分の介入を除去するという方法で過剰衝突状態を取 扱うための優れたメカニズムを提供する。従って、本発明は、複雑なパケットの 送信のための長い待ち時間がなく、従来の技術の説明の中で上述したようなシス テムの効率を低下させることのない、自動送信を提供する。図面の簡単な説明 本発明の前記及び他の目的、利点及び特徴は、添付図面を用いて行われる以下 の本発明の詳細な説明を参照することにより、更に容易に理解されるであろう。 図面中、 図１は、本発明の実施例によるネットワークシステムに接続されるノードを表 すブロック図であり、 図２は、本発明の実施例による図１のアダプターにより実行することができる アンダーフロー状態に続く自動再送信のためのアルゴリズムのフローチャートで あり、且つ 図３は、本発明の実施例による図１のアダプターにより実行することができる 過剰衝突回復のためのアルゴリズムのフローチャートである。好ましい実施例の説明 図１は、ＬＡＮ又はディスク記憶装置のようなネットワーク12に接続された、 例えばコンピュータシステムであるノード10を示す。ノード10はネットワークア ダプター14、メインメモリー16、ＣＰＵ18、及び、全て例えばＰＣＩバスのよう なシステムバス22によって相互に接続された端子のような他の周辺ユニット20を 含む。アダプター14は、望ましくは双方向パス24を通してシステムバス22に接続 され、望ましくは双方向パス26を通してネットワークシステム12に接続される。 ネットワークシステム12は、ノード10のアダプター14と、例えば同様の構成でそ れに接続されている他のノード27のアダプター（図示せず）との間の、例えば高 帯域幅、半二重データ通信を受容するためのバストポロジーを実現することが望 ましい。これに代えて、アダプター14は、ネットワークシステム12に接続された ノード10,27 間の全二重通信を実現する構成であってもよい。 受信動作の間は、データはネットワーク12からアダプター14に転送され、結局 はメインメモリー16に転送されて処理を待つ。アダプター14とメインメモリー16 との間のデータ転送は、システムバス22上の直接メモリーアクセス（ＤＭＡ）転 送によって遂行される。ＤＭＡ転送は、システムバスへのアクセスの要求とそれ に続くアクセスの許可、及び、予め定められたサイズのデータの「バースト」を 含む。送信動作の間は、メインメモリー16から取出されたデータがアダプター14 からネットワークシステム12に転送される。ネットワークシステム12とアダプタ ー14との間のデータの転送は、例えば、個々のパケットについて固定レートで行 われる。 システムバス22は、アダプター14によりメインメモリー16に対して読出し及び 書込み転送を遂行するためのアクセスに、常に直ちに利用できるとは限らない。 バス22がそれに接続された他のユニットを含む他の動作を遂行するために占拠さ れることがあり、また、例えばユニット20のような他の部分が読出し又は書込み メモリー転送を行うことがある。そのため、システムバス22は（メインメモリー 16と同様に）共用リソースと考えられ、システムバス22へのアクセス要求の発行 とバスへのアクセスの許可との間の時間は、システムバス22の「待ち時間」を構 成する。 バスの待ち時間に対応するため、アダプター14は、バッファメモリー、好まし くはＦＩＦＯ（「ファーストイン、ファーストアウト」）送信バッファ30及びＦ ＩＦＯ受信バッファ32を具える。線26を通ってネットワークシステム12からアダ プター14に入ったデータは、受信ステートマシン36の制御の下で、ネットワーク インタフェース34を通って受信バッファ32に到達する。受信バッファ32は、アダ プター14がシステムバス22へのアクセスを得るまでデータを一時的に格納し、ア クセスを得た時に受信ＤＭＡ（直接メモリーアクセス）モジュール37が、受信Ｆ ＩＦＯバッファ32中のデータを「読出し」、メインメモリー16に書込み転送を行 う。この後、データは、システムバスインタフェース38及びシステムバス22を通 ってメインメモリー16に書込まれる。 ネットワークシステム12に送信されるべきデータは、送信ＤＭＡモジュール39 により、メインメモリー16から、システムバス22にアクセスしているシステムバ スインタフェース38上に読出され、このデータは送信バッファ30に置かれる。ア ダプター14がネットワークシステム12へのアクセスを獲得すると、データは、送 信ステートマシン40の制御の下にネットワークインタフェース34に送られ、次に ネットワークシステム12に送られる。アダプター14の各部分は内部バス35で相互 に接続されている。 ネットワークインタフェース34は、アダプター14がネットワークシステム12と の通信を行うために必要なタイミング及び電気的特性に確実に合致するために必 要な、通常のデータパスの論理的及び物理的コネクションを含む。例えばネット ワークインタフェース34は、例えばイーサネットのような適当なネットワーク12 のネットワークプロトコルを実行するための媒体アクセス制御装置（「ＭＡＣ」 ）を具えることができる。 システムバスインタフェース38は、アダプター14がシステムバス22上で通信を 行うために必要なタイミング及び電気的特性に確実に合致するために必要な、通 常のデータパスの論理的及び物理的コネクションを含む。例えばシステムバス22 は、例えばＰＣＩバスであってもよいし、インタフェース38は、例えばＰＣＩバ スインタフェースあってもよい。 アダプター14を通る双方向のデータの流れは、インタフェース38の調整機能に よって制御される。この調整機能は、ＤＭＡマシン37、39に代わって、通常の調 整プロセスのとおりにシステムバス22の制御のための調整を行う。受信及び送信 ステートマシン36、40を具えているので、調整モジュール38は、抵抗器及び直列 論理回路として構成された結合論理（図示せず）を含むことが望ましい。 ＤＭＡマシン37及び39は、送信及び受信バッファ30、32を通る、ネットワーク とシステムバス22との間のデータの双方向の流れを管理する。特に、送信ＤＭＡ マシン39は、システムバス上の読出し転送と共に、メインメモリー16からの下り データバーストの転送を開始する。これらの下りデータバーストは、一時的に送 信バッファ30に格納され、続いて送信ステートマシン40により、ネットワークシ ステム12上に送信される。受信ステートマシン36は、ネットワークシステム12か らの上りデータバーストを管理して一時的に受信バッファ32にデータを格納し、 受信ＤＭＡステートマシン37は、バスインタフェース38及びシステムバス22を介 してメモリー16にデータを移動させる。ステートマシン36、40によって遂行され る機能の例は、データをバッファに格納した後又はそれに先立って、ネットワー クシステム12への及びそれからのデータのビットストリームをバイト幅のワード に変換することである。 受信バッファ32に受信されたデータについての予め定められた閾値レベルに基 づいて、及び、システムバス22に対する獲得アクセスに基づいて、受信ステート マシン36は、予め定められたサイズの上りデータのバーストを、メインメモリー 16に向けた書込み転送として、システムバス22上への転送を開始する。データの バーストのサイズは、システムバスの特性によって変わり得る。システムバス22 上のバーストの間に転送されるデータの量は、一般的に、例えばパケットとして ネットワークシステム12上に転送されるデータのブロックより少ない。受信ＤＭ Ａマシン37及び送信ＤＭＡマシン39は、バス22上のデータの一つのバーストの各 転送について、システムバス22に対するアクセスを調整する必要がある。 ここで説明されていないステートマシン36、40、ＤＭＡマシン37、39、及びイ ンタフェースモジュール38の構成及び動作については、当業者にとって明らかで あり、ここに示されたようなもの以外は一般的なものである。 図２は、送信ステートマシン40で実行される、送信バッファアンダーフロー状 態の後における自動再送信のためのアルゴリズム100 を示す。 ブロック110 では、送信ステートマシン40は非アクティブ、即ちアイドルモー ドにある。ブロック110 は送信のための新しいパケットをフェッチする。ブロッ ク110 は更に、「NO OF RETRIES」と呼ばれる変数及び閾値を表す変数「Ｔ」 を含む変数を初期化する。NO OF RETRIESは、送信ステートマシン40が試行で きる再試行の組の数を表す。閾値「Ｔ」は、送信の開始が許可される前に送信バ ッファ30で利用できるものとして要求されるバイト数を表す。 これらの変数NO OF RETRIES 及びＴの両者は、アルゴリズム100 が実行され る特定のアダプターの個々の必要性を考慮して、プログラマブルである値を持つ ことが望ましい。本発明は、例えばNO OF RETRIES の値に、値１の限界を設け ることができる。これは、アンダーフロー状態が生起した時はいつでも、送信ス テートマシンが１組の追加の再送信を行うようにすることである。 変数Ｔは、最初は値Ｎ1 に設定することができ、アダプター14の動作中は例え ば三つの値Ｎ1 、Ｎ2 又はＮ3 のいずれかであると推定できるとする。ここで、 Ｎ1 は中間の値、Ｎ2 はＮ1 以下の値、及びＮ3 はＮ1 以上の値である（Ｎ2 ≦ Ｎ1 ≦Ｎ3 ）。Ｎ1 は例えば７２バイトである。Ｎ2 は例えば、送信バッファ30 中の最小アドレス可能ブロックデータ（即ち、一つのロングワード）に含まれる バイト数であり、従って送信ステートマシン40がそこからフェッチすることがで きる最小バイト数である。従ってＮ2 は４バイトのデータ程度であり得る。Ｎ3 はパケットの実質部分に等しく、例えば１２８バイトである。 ブロック112 は、閾値制御ビットが例えば論理HIGHに設定されているか否か、 及び、アンダーフローフラグが例えば論理LOW にクリアされているか否かの両者 を試験する。閾値制御ビットがセットされておりアンダーフローフラグがクリア されていると、ブロック114 で閾値Ｔを初期値Ｎ1 からＮ2 に減らす。即ち、送 信を開始するために送信バッファ30中に必要なバイト数を減らす。アンダーフロ ーフラグは、アンダーフローが生起したか否かを示す。これがセットされると、 以下に説明するように、アルゴリズム100 がＴの値を可能な最大値、即ちＮ3 に 変える。 ブロック114 の後、又はブロック112 の試験の結果が否定の（即ち閾値制御ビ ットがクリアされたか又はアンダーフローフラグがセットされた）場合、ブロッ ク116 で、閾値Ｔに到達するまで、即ち送信バッファ30が適用されるＴの値によ って決まる送信可能なバイト数を持つまで、送信ステートマシンを待たせる。次 に、ブロック118 で送信を開始する。 ブロック120 では、衝突ウィンドウが満了したか否かを試験する。衝突ウィン ドウはアダプターがネットワーク12上での衝突を監視する時間であり、時にはネ ットワークアキジションタイムと呼ばれる。衝突ウィンドウは、衝突ウィンドウ インジケーターと呼ばれる他の変数によって特定され、一般的にネットワークの 仕様によって決まるシステムパラメータを表す。１０Mbpsイーサネットネットワ ークにおいては、衝突ウィンドウインジケーターは５１．２マイクロ秒のネット ワークアキジションタイムを表す。 衝突ウィンドウインジケーターによって表される衝突ウィンドウが満了してい ない場合は、ブロック122 において、アンダーフロー状態が生起したことを示す アンダーフローフラグがセットされているか否かを試験する。上述のように、ア ンダーフロー状態は、送信バッファ30がネットワークのために必要とされる送信 レートに合致するに充分なパケットデータを持っていない時に生起する。アンダ ーフローフラグがセットされていない場合は、アルゴリズム100 はブロック120 に戻って衝突ウィンドウが満了したか否かを試験する。 一方、ブロック122 の試験においてアンダーフロー状態が生起したことが表示 されると、ブロック124 において、NO OF RETRIES が限界Ｒ、即ち１より少な いか否かを試験する。言い換えると、衝突ウィンドウの間にアンダーフロー状態 が生起し、再試行の回数がＲより少ない場合は、ブロック124 の試験は「ＹＥＳ 」であり、逆の場合は、ブロック124 の試験が「ＮＯ」である。 ブロック124 の試験の結果が肯定の場合は、アルゴリズム100 はブロック126 に進む。このブロックでは、NO OF RETRIES を例えば１だけ増加させる。この ように、ブロック126 を最初に通過した後はＲ＝１である。 ブロック128 では、アンダーフローフラグがセットされ、アンダーフロー状態 のパケットを再送信するための計画を進める。ブロック130 では、アンダーフロ ーフラグのセットに応答して閾値を値Ｎ3 に増加させる。続いて、アルゴリズム 100 はブロック112 に戻る。 ブロック120 の試験により衝突ウィンドウが満了したことが示されると、ブロ ック132 では、送信ステートマシンがパケットの送信を続ける。 試験間隔と呼ばれる予め選択された時間の後、ブロック134 ではアンダーフロ ー状態を試験し、衝突ウィンドウが満了した後にアンダーフローが生起したか否 かを決定する。そのようなアンダーフローが生起した場合は、ブロック136 でア ンダーフロー中断を宣言し、次にブロック138 でアンダーフローフラグをクリア する。ブロック138 に続いてアルゴリズム100 はブロック110 に戻る。ブロック 110 では、送信ステートマシン40がアイドルモードを再開し、このブロックに関 して上述のように、変数がリセットされる。 ブロック134 の試験においてアンダーフロー状態が生起していないことが表示 された場合は、次にブロック140 において、最終送信パケットが送られたか否か を試験することにより、パケット送信が完了したか否かを試験する。送信が完了 していない場合は、アルゴリズム100 はブロック132 に戻り、ここで送信が継続 される。一方、送信が完了した場合は、アルゴリズム100 はブロック138 に進み 、アンダーフローフラグがクリアされ、上述のように、次にブロック110 に進む 。 従って、アルゴリズム100 は、送信バッファ30に対してデータのアンダーフロ ーが生起した場合における自動再送信のための優れた技術を具え、システム効率 を改善することができ、データの待ち時間を低減することができる。 アルゴリズム100 は、衝突ウィンドウ間隔における送信の間にアンダーフロー が生起した場合にのみ、「自動再試行」を実行することが明確にされるべきであ る。本発明は、衝突ウィンドウ間隔の間及び後の両者を含む送信期間中のいずれ の時においても「自動再試行」を実行するように、更に一般的に実施することが できる。 図３は過剰衝突回復のためのアルゴリズム200 を示す。アルゴリズム200 は、 バッファアンダーフローに対する自動送信に関するアルゴリズム100 とは別個に 送信ステートマシン40によって実行される。即ち、当業者には明らかなように、 二つのアルゴリズム100，200は相互に統合することができる。アルゴリズム200 はブロック210 でスタートする。ここでは送信のための新しいパケットを待ち、 以下に説明するように、アルゴリズム200 で用いられる特別の変数「ＲＮＥＣ」 及び「Ｔ」を初期化する。 ブロック212 では閾値Ｔに到達したか否かを試験する。これは、ブロック116 に関して上述した方法と同じ方法で行われることが望ましい。この場合、閾値Ｔ はＮ1 に等しいこともあり得るし又は異なる値にセットされることもあり得る。 閾値Ｔに到達していない場合は、アルゴリズム200 は単に閾値に達するまでブロ ック212 の試験を繰り返す。ブロック212 では更に変数 COLLISION COUNT をゼ ロに初期化する。 他方、閾値Ｔに到達した場合は、ブロック214 では送信ステートマシン40がデ ータの送信を始める。ブロック215 では、ブロック120 に関して利点として上述 したように、衝突ウィンドウインジケーターを試験することにより、衝突ウィン ドウが満了したか否かを試験する。衝突ウィンドウが満了した場合は、アルゴリ ズム200 は、ブロック216 で送信を完了した後ブロック210 に戻り、新しいパケ ットに対して前述のステップを繰り返す。衝突ウィンドウが満了していない場合 は、ブロック217 で、送信に含まれたパケットに関して衝突が生起したか否かを 検出する。ブロック217 で衝突が検出されない場合は、アルゴリズム200 はブロ ック215 に戻る。 関連するパケットに関して衝突が検出される度に、ブロック218 で COLLISION C0UNT と呼ばれる変数を増し、ブロック219 で COLLISION COUNT の値を試験 する。 COLLISION COUNT の値が予め選択された限界、例えば適用する標準によ って設定された１６に到達した場合は、ブロック219 で、過剰回数の衝突が生起 したことが表示される。他方、 COLLISION COUNT が１６未満である限り、ブロ ック219 の試験は、過剰回数の衝突は生起していないことを表示する。 過剰衝突状態が生起していないことを表示するブロック219 の否定の結果に続 いて、ブロック220 では、好ましくはアルゴリズム100 のブロック140 に関する 方法と同じ方法により、送信か終了したか否かを試験する。送信が終了した場合 は、アルゴリズム200 はブロック214 に戻り、同一パケットの送信を再開する。 言い換えると、アルゴリズム200 では、例えば（１６回までの）ＣＳＭＡ／ＣＤ 通常送信再試行を行う。ブロック220 でまだ送信が終了していないことが表示さ れると、ブロック221 では、ブロック220 の試験が繰り返される前に、ビットタ イムのオーダだけ待機する。「ビットタイム」はチャネルを通して１ビット送信 するのに必要な時間であり、例えば、１００Mbpsで動作するチャネルについては １０ナノ秒（又は１０Mbpsチャネルについては１００ナノ秒）である。ブロック 221 の「待機」期間の間、「本発明の背景」の項で前述したように、ノードはジ ャムを送信する。 本発明によれば、ブロック219 で過剰衝突状態が生起したことが表示された場 合は、ブロック222-228 の後、「過剰衝突に対する再試行回数」（ＲＮＥＣ）と 呼ばれる回数の間、衝突が検出されず送信が成功するまで、又は、予め選択され たＲＮＥＣの限界に到達するまでの間、反復してブロック212-220 のステップが 繰り返される。例えば、 COLLISION COUNT 限界が１６であり、ＲＮＥＣ限界が ２の場合は、アルゴリズム200 はブロック212-220 を３２回まで繰り返す（１６ 回の繰り返しを２回繰り返す）。繰り返された衝突に関連するパケットの送信が 成功せずにＲＮＥＣ限界に到達した場合は、上述の従来技術と同様に、このアル ゴリズムはパケットを廃棄し、ブロック210 に戻り、新しいパケットを待つ。 更に特別な場合、ブロック219 の試験により過剰回数の衝突が生起したことが 表示された場合は、ブロック222 でＲＮＥＣ限界を獲得し、ブロック223 でＲＮ ＥＣが予め設定された限界より小さいか否かを試験する。ブロック223 の試験に おいてＲＮＥＣ限界に到達したことが示された場合は、上述のように、アルゴリ ズム200 は送信終了後ブロック210 に戻る。ブロック223 の試験においてＲＮＥ Ｃ限界に到達していないことが示された場合は、ブロック224 でＲＮＥＣカウン トを例えば１だけ増す。次に、ブロック226 により、ネットワークインタフェー ス34が、そのパケットを初めて送信されるべき新しいパケットのように取扱う。 ブロック228 では、過剰衝突に関連するパケットを再送信のために再び待つ。続 いてアルゴリズム200 はブロック212 に戻る。 従って、アルゴリズム200 は、過剰衝突回復のための優れた技術を具え、シス テム効率を改善することができ、データ待ち時間を低減することができる。ＲＮ ＥＣ限界は予めプログラムすることができ、又はトラヒック状態に応じて動的に 決定することもできる。言い換えれば、ネットワークが過密のピークの期間を経 験する時は、例えば、存在し得る高度の衝突状態に悪化させないように、アダプ ター14がＲＮＥＣ限界を減らすことができる。他方、他の時刻において、次のパ ケットの送信を成功させる可能性を増すために、及び、送信が成功するまでこの パケットの送信のために上位レイヤプロトコルが再スケジューリングを行う必要 性を除去することによってパケット待ち時間を減らすために、ＲＮＥＣ限界を増 加させることができる。ブロック222 では、予め設定されたＲＮＥＣ限界を獲得 するか、又は例えばネットワークステータスパケットから得られたネットワーク の状態情報に基づいてそれを計算する。他の特徴及び実施例 上記においては本発明の実施例を説明した。当業者にとっては、ここになされ た開示から種々の他の特徴及び実施例が明らかである。例えば、上述の実施例で は、パケットデータが送信バッファ中で上書きされない限り何時でも、アンダー フロー又は過剰衝突に対する再試行を行うことができるが、本発明においては、 送信衝突ウィンドウの間にアンダーフローが起きた場合にのみ実行できるように することができる。 更に、送信の成功の可能性を最適化するため、アンダーフロー又は衝突の履歴 情報、ネットワークトラヒック状態、及び／又はバス負荷状態に基づいて再試行 の最大数を計算するアルゴリズムを用いて本発明を実施することが可能である。 この点について、特に送信バッファアンダーフロー状態を考えることとする。 アンダーフローは、ホストシステムバスのピーク待ち時間が大きく、及び／又は システムバスのスループットが小さい時に起きる。従ってアンダーフローは主と してホストＣＰＵシステムバスに依存する。他方、ネットワークが輻輳し、Ｒが 高い値に設定されると、ネットワークに対する不必要な干渉が始まる。このため 、或る種のアプリケーションにおいては、ネットワークの高度の輻輳及び／又は 高度のホストＣＰＵバスの負荷の期間中に、Ｒについて、その値を減らすために （予め設定された一定値に代えて）動的に計算された値を用いることが合理的で ある。このため、ブロック124では、限界Ｒについて固定値を用いずに、NO OF RETRIES の試験においてその値を用いる前の上述の履歴情報に基づいてＲを計算 するとよい。 再試行が不成功に終わる状態を防ぐために、予め定められた不成功の再試行の 回数の後、次の再試行の前に計算された期間の遅延を挿入するような、バックオ フスケジュールを計算するためのアルゴリズムを用いることも可能である。 アンダーフロー又は過剰衝突について、再試行の開始時刻は、更に、送信バッ ファに直接メモリーアクセスした関連パケットのバイト数の関数である。この関 数は、（例えば、アンダーフローについては、パケットの少なくとも１６０バイ トがバッファ中に含まれるまで待つように）プログラムされた値とすることがで き、又は履歴からの学習できるようにすることもでき、又は再試行回数の関数で あってもよい。 このように、本発明は、パケットの損失を最小にすることができ、上位ネット ワークレイヤの介入なしにアンダーフロー又は過剰衝突を回復させることができ る。その結果、本発明は、一時的に発生するシステムバスの大きな待ち時間のた めにアンダーフロー又は過剰衝突が生起した場合においても、パケットを送出す るための、素早く簡潔な方法を提供する。本発明は更に、上位ネットワークレイ ヤの介入を避けることによって、平均パケット遅延を低減することができる。更 に本発明は、アンダーフローを避けるために従来技術では必要であった一般的に 大きい量のパケットの受信を待つ必要がないので、送信バッファへのパケット転 送のスタートから送信のスタートまでの遅延時間を一層短くすることができる。 本発明の特定の実施例について説明したが、この説明は、制限する意味に解釈 されるべきではない。当業者には、この説明から、本発明の開示された実施例及 び他の実施例の種々の変更が明らかであろう。従って、添付の請求の範囲がこの ような変更又は実施例を本発明の真の範囲の中に入れるようにカバーすることが 意図されている。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ベン−マイケル シモニ イスラエル国 90917 ギファット ゼー フ ミップ ストリート 13／３ (72)発明者 ハウィ ウィリアム アメリカ合衆国 マサチューセッツ州 01463 ペッペレル インディペンデント ロード 16 【要約の続き】 ムに従って再試行を行う。再試行が成功すれば、アダプ ターが中断を発行する必要はない。

Claims (1)

1. 【特許請求の範囲】 １．データを送信するために共用リソースに接続され且つ送信バッファを有する アダプターが動作し、パケット送信並びに選択的に過剰衝突状態及びバッファア ンダーフローを含む好ましくない送信状態の場合におけるパケット送信の自動再 試行を行う方法であって、以下のステップ、即ち 予め定められた第１の量のデータが前記アダプターの送信バッファに格納さ れた後に送信を開始するステップ、及び 過剰衝突状態は前記パケットの選択された送信試行回数の各々が前記パケッ トに関連して衝突を生ずる時に生起するものとし、送信開始ステップの後に過剰 衝突状態が生起したか否かを決定し、過剰衝突状態が生起した場合は過剰衝突カ ウントを更新し、及び (i) 前記過剰衝突カウントが過剰衝突限界以下の場合は送信を停止し、次に 実質的に直ちに、前記パケットの送信を繰り返し、及び (ii)前記過剰衝突カウントが過剰衝突限界を超えている場合は送信を停止し 、前記送信バッファに格納された前記パケットのデータを廃棄するステップ を含む方法。 ２．請求項１に記載の方法において、更に、以下のステップ、即ち 生起したいかなる衝突をも検出するステップ、 生起した前記衝突の各々を、衝突カウント限界までカウントするステップ、 前記衝突カウント限界に到達する度に、前記過剰衝突の数を表示するように 過剰衝突表示カウントを増すステップ を含む方法。 ３．請求項１に記載の方法において、前記共用リソースがコンピュータネットワ ークに接続され、更に、ネットワークのトラヒック状態に応じて、動的に過剰衝 突限界を決定するステップを含む方法。 ４．請求項１に記載の方法において、更に、送信バッファアンダーフロー状態に 続いてパケットの自動再送信を行う複数のステップを含み、このステップは、 前記パケットの送信中に送信バッファアンダーフロー状態が生起した場合、 前記パケットの送信を停止し、前記パケットの前記第１の量のデータより多い第 ２の量のデータが前記送信バッファに格納された後に再び前記パケットの送信を 開始するステップ を含む方法。 ５．請求項４に記載の方法において、前記共用リソースがコンピュータネットワ ークに接続され、更に、ネットワークのトラヒック状態に応じて、動的に前記過 剰衝突限界及び第２のデータ量を決定するステップを含む方法。 ６．過剰衝突状態に続くデータのパケットの自動再送信のための方法であり、ネ ットワークアダプターによって実現される方法であって、以下のステップ、即ち a)前記パケットの予め定められたバイト数が送信できる状態になった後でパ ケットの送信を開始するステップ、 b)衝突が検出された場合は衝突カウントを増し、この衝突カウントが予め定 められた第１限界を超えない場合は、送信を続けるステップ、 c)衝突カウントが前記第１限界を超えた場合は以下のステップ、即ち (i) 再試行（ＲＮＥＣ）カウントが第２限界を超えた場合は、前記パケット の送信を停止するステップ、及び (ii)ＲＮＥＣカウントが前記第２限界を超えない場合は、このＲＮＥＣカウ ントを増し、この増加したＲＮＥＣカウントを用いて再びステップ(a)-(c)を遂 行するステップ を含む方法。 ７．請求項６に記載の方法において、前記パケットの前記送信開始ステップが、 前記衝突カウントに対する前記第１限界と前記ＲＮＥＣカウントに対する前記第 ２限界との積に等しい回数まで遂行される方法。 ８．請求項６に記載の方法において、ステップ(b)が、衝突ウィンドウの間で衝 突が生起したか否かを決定し、この衝突状態が前記衝突ウィンドウの間に検出さ れた場合のみ、この衝突状態に基づいて前記パケットの送信を停止するステップ を含む方法。 ９．データを送信するために共用リソースに接続され且つ送信バッファを有する アダプターが動作し、パケット送信及びバッファアンダーフローのような好まし くない送信状態の場合におけるパケット送信の自動再試行を行う方法であって、 以下のステップ、即ち a)予め定められた第１の量のデータが前記アダプターの送信バッファに格納 された後に送信を開始するステップ、及び b)送信開始ステップの後、バッファアンダーフロー状態が生起した場合は送 信の停止を含むステップを遂行し、次に、第１の量のデータより多い予め定めら れた第２の量のデータが前記送信バッファに格納された後にのみ再び送信を開始 するステップ、及び c)ステップb)の後実質的に直ちに再び送信を開始し、第１状態は送信の完了 を含み且つ第２状態はステップb)が限界に到達するまでに繰り返される回数を含 むものとした場合、第１及び第２状態の一つが生起するまでの回数だけステップ b)及びこのステップc)を繰り返すステップ を含む方法。 10．請求項９に記載の方法において、前記限界が予め定められた固定値からなる 方法。 11．請求項９に記載の方法において、更に前記アダプターによって経験された従 前のアンダーフロー状態に基づいて計算される限界を含む方法。 12．データを送信するために共用リソースに接続され且つ送信バッファを有する アダプターが動作し、パケット送信及びバッファアンダーフローの場合における パケット送信の自動再試行を行う方法であって、以下のステップ、即ち a)送信を開始する前に前記送信バッファ中で必要とするバイト数を表示する 閾値変数Ｔを第１値Ｎ2 に設定するステップ、 b)前記アダプターが共用リソースに送信すべきパケットのデータを得るよう にし、このデータを前記送信バッファに格納するステップ、 c)前記パケットのＴバイトのデータが前記送信バッファに格納された後にの み、前記パケットの前記共用リソースへの送信を開始するステップ、及び d)前記パケットの送信の開始後、衝突ウィンドウを含む予め定められた時間 が満了したか否かを試験し、 (i) 衝突ウィンドウが満了した場合は、第１状態はバッファアンダーフロー 状態を含み第２状態は送信の完了を含むとして、第１及び第２状態の一つが生起 するまで送信を継続し、 (ii) 衝突ウィンドウが満了していない場合は、ステップ(d) を繰り返し、 (iii) ステップ(d)(i)でバッファアンダーフロー状態が生起し、且つ、再試 行カウントが予め定められた限界に到達した場合は、送信を停止し、前記状態を 表示するメッセージ信号を発生し、及び (iv) ステップ(d)(i)でバッファアンダーフロー状態が生起し、且つ、再試 行限界が前記予め定められた限界以下である場合は、ステップ(d)の前記送信を 反映するために前記再試行カウントを変更し、閾値変数を前記第１値Ｎ2 より大 きい第２値Ｎ3 に設定し、ステップ(b),(c) 及び(d)を繰り返す ステップを含む方法。