(57)【特許請求の範囲】
【請求項１】
複数の経路指定ノードを含むコンピュータネットワークに接続して使用する経路指定ノードであって、該経路指定ノードは、選択される他の経路指定ノードに接続され、少なくとも幾つかの経路指定ノードは、複数の発信元の中の１つ又は複数の宛先の中の１つに接続され、各経路指定ノードは、発信元によって生成され、且つ複数の直列伝送されるセルを含むパケットの、それぞれの宛先への経路を指定し、
Ａ． ネットワーク内の他の経路指定ノードまたはパケットの宛先に伝送されるべきセルを、受け取り且つ一時記憶するバッファ、及び
Ｂ． バッファが選択的にセルを受け取り且つ一時記憶できるようにするバッファ制御であって、バッファ制御は、早期パケット廃棄制御装置を使用可能にし、該装置において、バッファが選択されたしきい値ナンバーのファイルを同時に一時記憶することに対応して、バッファが、早期パケット廃棄制御装置機構を使用可能にする前に、セルを受け取り始めなかったパケットに関連するセルを受け取り且つ一時記憶することを禁止し、以前の選択された時間周期中に、バッファがセルを提供するレートに対する情報に関連して、前記しきい値ナンバーを周期的に調整するバッファ制御、を具えており、
バッファ制御は、一時記憶されるセルに関連するしきい値ナンバーを、選択された時間周期中に、バッファが一時記憶するセルの数の選択された関数として周期的に調整することを特徴とする経路指定ノード。
【請求項２】
選択された関数は、平均する関数であり、バッファ制御は、一時記憶されるセルに関連するしきい値ナンバーを、選択された時間周期中に、バッファが一時記憶するセルの数の平均として周期的に調整する、請求項１に記載の経路指定ノード。
【請求項３】
バッファ制御は、
Ａ．しきい値を記憶するしきい値ストア、
Ｂ．選択された時間周期中にバッファが一時記憶するセル数の平均に等しい一時記憶されるセルの平均値を生成する占有統計ジェネレータ、
Ｃ．しきい値ストアが記憶するしきい値と一時記憶されるセルの平均値とを比較するコンパレータ、及び
Ｄ．占有統計ジェネレータが一時記憶されるセルの平均値を生成できるようにし、且つ、コンパレータがしきい値ストアによって記憶されるしきい値と一時記憶されるセルの平均値を比較できるようにすることを周期的に行なう制御モジュールであって、もし、一時記憶されるセルの平均値がしきい値ストアによって記憶されるしきい値よりも小さいと、コンパレータが判断するならば、一時記憶されるセルの平均値をしきい値ストアに記憶できるようにする制御モジュール、を具える、請求項２に記載の経路指定ノード。
【請求項４】
バッファ制御は、統計学的信頼性の評価値を生成する統計学的信頼性評価モジュールを含み、制御モジュールは、一時記憶されるセルの平均値をしきい値ストアに記憶できるようにするかどうかを判断する際に、統計学的信頼性の評価値を使用する、請求項３に記載の経路指定ノード。
【請求項５】
経路指定ノードが受け取る少なくとも幾つかのセルは、それぞれのセルがパケットの最後であることを示すパケット終了識別子を含み、バッファは、それぞれが１つのセルを記憶する一連の記憶場所を具え、さらに、バッファ制御は、パケット終了識別子を有するセルが記憶される記憶場所の最後についての第２の選択される関数に関連して、しきい値ナンバーを周期的に調整し、統計学的信頼性の評価モジュールは、パケット終了識別子を有するセルが記憶される記憶場所の最後についての分散に相当する分散値の関数として、統計学的信頼性の評価値を生成する、請求項４に記載の経路指定ノード。
【請求項６】
経路指定ノードが受け取る少なくとも幾つかのセルは、それぞれのセルがパケットの最後であることを示すパケット終了識別子を含み、バッファは、それぞれが１つのセルを記憶する一連の記憶場所を具え、さらに、バッファ制御は、パケット終了識別子を有するセルが記憶される記憶場所の最後についての第２の選択される関数に関連して、しきい値ナンバーを周期的に調整する、請求項２に記載の経路指定ノード。
【請求項７】
第２の選択される関数は、分散関数である、請求項６に記載の経路指定ノード。
【請求項８】
バッファ制御は、
Ａ．しきい値を記憶するしきい値ストア、
Ｂ．ｉ．選択された時間周期中にバッファが一時記憶するセル数の平均に等しい一時記憶されるセルの平均値を生成する一時記憶されるセルの平均統計ジェネレータ、
ｉｉ．パケット終了識別子を有するセルが記憶される記憶場所の最後についての分散に相当する分散値を生成する分散ジェネレータ、及び
ｉｉｉ．一時記憶されるセルの平均値と分散値の選択される関数として、合成統計値を生成する合成統計ジェネレータ、を含む占有統計ジェネレータ、
Ｃ．しきい値ストアが記憶するしきい値と合成統計値とを比較するコンパレータ、及び
Ｄ．統計ジェネレータが合成統計値を生成できるようにし、且つ、コンパレータがしきい値ストアによって記憶されるしきい値と合成統計値を比較できるようにすることを周期的に行なう制御モジュールであって、もし、合成統計値がしきい値ストアによって記憶されるしきい値よりも小さいと、コンパレータが判断するならば、合成統計値をしきい値ストアに記憶できるようにする制御モジュール、を具える、請求項６に記載の経路指定ノード。
【請求項９】
制御モジュールは、合成統計値をしきい値ストアに記憶できるようにするかどうかを判断する際に、分散値を使用する、請求項８に記載の経路指定ノード。
【請求項１０】
合成統計ジェネレータは、一時記憶されるセルの平均値と分散値の逆数との和として、合成統計値を生成する、請求項８に記載の経路指定ノード。
【請求項１１】
複数の経路指定ノードを含むコンピュータネットワークに接続して使用する経路指定ノードであって、該経路指定ノードは、選択される他の経路指定ノードに接続され、少なくとも幾つかの経路指定ノードは、複数の発信元の中の１つ又は複数の宛先の中の１つに接続され、各経路指定ノードは、発信元によって生成され、且つ複数の直列伝送されるセルを含むパケットの、それぞれの宛先への経路を指定し、
Ａ． ネットワーク内の他の経路指定ノードまたはパケットの宛先に伝送されるべきセルを、受け取り且つ一時記憶するバッファ、及び
Ｂ． バッファが選択的にセルを受け取り且つ一時記憶できるようにするバッファ制御であって、バッファ制御は、早期パケット廃棄制御装置を使用可能にし、該装置において、バッファが選択されたしきい値ナンバーのファイルを同時に一時記憶することに対応して、バッファが、早期パケット廃棄制御装置機構を使用可能にする前に、セルを受け取り始めなかったパケットに関連するセルを受け取り且つ一時記憶することを禁止し、以前の選択された時間周期中に、バッファがセルを提供するレートに対する情報に関連して、前記しきい値ナンバーを周期的に調整するバッファ制御、を具えており、
経路指定ノードが受け取る少なくとも幾つかのセルは、それぞれのセルがパケットの最後であることを示すパケット終了識別子を含み、バッファは、それぞれが１つのセルを記憶する一連の記憶場所を具え、バッファ制御は、パケット終了識別子を含むセルを記憶する記憶場所の最後についての選択された時間周期にわたっての平均に関連して、しきい値ナンバーを周期的に調整することを特徴とする経路指定ノード。
【請求項１２】
バッファ制御は、部分パケット廃棄装置を使用可能にし、該装置において、バッファが２番目に選択されたしきい値ナンバーのセルを同時に一時記憶することに対応して、バッファがセルを受け取り且つ一時記憶することを禁止し、もし、部分パケット廃棄装置が選択される数のセルを捨てるならば、早期パケット廃棄制御装置を使用可能にする、請求項１乃至１１の何れかに記載の経路指定ノード。
【請求項１３】
バッファ制御は、もし、部分パケット廃棄装置が、所定の部分パケット廃棄時間周期にわたって、選択される数のセルを捨てるならば、早期パケット廃棄制御装置を使用可能にする、請求項１２に記載の経路指定ノード。
【請求項１４】
バッファ制御は、もし、部分パケット廃棄装置が、選択される数のパケットに関するセルを捨てるならば、早期パケット廃棄制御装置を使用可能にする、請求項１２に記載の経路指定ノード。
【請求項１５】
複数の経路指定ノードを含んでおり、各経路指定ノードは、請求項１乃至１４の何れかに記載の経路指定ノードであるコンピュータネットワーク。
【請求項１６】
経路指定ノードを作動する方法であって、経路指定ノードは、複数の経路指定ノードを含むコンピュータネットワークに接続して使用し、選択される他の経路指定ノードに接続され、少なくとも幾つかの経路指定ノードは、複数の発信元の中の１つ又は複数の宛先の中の１つに接続され、各経路指定ノードは、発信元によって生成されるセルの、それぞれの宛先への経路を指定し、
Ａ． ネットワーク内の他の経路指定ノードまたはパケットの宛先に伝送されるべきセルを、バッファにて受け取り且つ一時記憶するステップ、及び
Ｂ． バッファがセルを受け取り且つ一時記憶できるように選択的に行なうステップであって、該プロセスにおいて、早期パケット廃棄制御装置を使用可能にし、該装置において、バッファが選択されたしきい値ナンバーのセルを同時に一時記憶することに対応して、バッファが、早期パケット廃棄制御装置機構を使用可能にする前に、セルを受け取り始めなかったパケットに関連するセルを受け取り且つ一時記憶することを禁止し、以前の選択された時間周期中に、バッファがセルを一時記憶するレートに相当する情報に関連して、前記しきい値ナンバーが周期的に調整されるステップ、を含んでおり、
しきい値ナンバーは、一時記憶されるセルに関連して、選択された時間周期中に、バッファが一時記憶するセルの数の選択された関数として周期的に調整されることを特徴とする方法。
【請求項１７】
選択された関数は、平均する関数であり、しきい値ナンバーは、一時記憶されるセルに関連して、選択された時間周期中に、バッファが一時記憶するセルの数の平均として周期的に調整する、請求項１６に記載の方法。
【請求項１８】
周期的に調整するステップは、
Ａ．しきい値を記憶するステップ、
Ｂ．選択された時間周期中にバッファが一時記憶するセル数の平均に等しい一時記憶されるセルの平均値を生成するステップ、
Ｃ．しきい値ストアが記憶するしきい値と一時記憶されるセルの平均値とを比較するステップ、及び
Ｄ．もし、一時記憶されるセルの平均値がしきい値ストアによって記憶されるしきい値よりも小さいならば、一時記憶されるセルの平均値をしきい値ストアに記憶できるようにするステップ、を含んでいる、請求項１７に記載の方法。
【請求項１９】
周期的に調整するステップは、さらに、統計学的信頼性の評価値を生成するステップと、一時記憶されるセルの平均値をしきい値ストアに記憶できるようにするかどうかを判断する際に、統計学的信頼性の評価値を使用するステップを含む、請求項１８に記載の方法。
【請求項２０】
経路指定ノードが受け取る少なくとも幾つかのセルは、それぞれのセルがパケットの最後であることを示すパケット終了識別子を含み、バッファは、それぞれが１つのセルを記憶する一連の記憶場所を具え、さらに、バッファ制御は、パケット終了識別子を有するセルが記憶される記憶場所の最後についての第２の選択される関数に関連して、しきい値ナンバーを周期的に調整し、統計学的信頼性の評価値は、パケット終了識別子を有するセルが記憶される記憶場所の最後についての分散に相当する分散値の関数として生成される、請求項１９に記載の方法。
【請求項２１】
経路指定ノードが受け取る少なくとも幾つかのセルは、それぞれのセルがパケットの最後であることを示すパケット終了識別子を含み、バッファは、それぞれが１つのセルを記憶する一連の記憶場所を具え、パケット終了識別子を有するセルが記憶される記憶場所の最後についての第２の選択される関数に関連して、しきい値ナンバーが周期的に調整される、請求項１７に記載の方法。
【請求項２２】
第２の選択される関数は、分散関数である、請求項２１に記載の方法。
【請求項２３】
部分パケット廃棄ステップを含み、該ステップにおいて、２番目に選択されたしきい値ナンバーのセルが一時記憶されている間、バッファは、その後に受け取られるセルを受け取り且つ一時記憶することが禁止され、早期パケット廃棄制御装置は、もし、部分パケット廃棄ステップの間に、選択される数のセルが捨てられるならば、使用可能となる、請求項１６に記載の方法。
【請求項２４】
早期パケット廃棄制御装置は、もし、部分パケット廃棄装置の間、所定の部分パケット廃棄時間周期にわたって、選択される数のセルが捨てられるならば、使用可能となる、請求項２３に記載の方法。
【請求項２５】
早期パケット廃棄制御装置は、もし、部分パケット廃棄ステップの間に、選択される数のパケットに関するセルが捨てられるならば、使用可能となる、請求項２３に記載の方法。
【請求項２６】
早期パケット廃棄制御装置は、もし、部分パケット廃棄ステップの間に、所定の部分パケット廃棄周期にわたって、選択される数のパケットに関するセルが捨てられるならば、使用可能となる、請求項２５に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的には、デジタル通信システムの分野に関し、より具体的には、例えば、デジタル画像、オーディオ及びビデオの分配システムにおけるデジタルデータの通信、並びにデジタルコンピュータシステム間のデジタルデータの通信を容易に行なうデジタルネットワークに関する。
【０００２】
【従来の技術及び発明が解決しようとする課題】
デジタルネットワークは、デジタルコンピュータシステム及びその他のデジタルデバイス間で、データ及びプログラムを含む情報を容易に転送すべく発展している。様々な種類のネットワークが、様々な情報転送技法を用いて発展し且つ実施されている。例えばよく知られているイーサネットのような幾つかのネットワークでは、一本のワイヤを用いて、そのネットワークに接続される全デバイスを相互に接続する。この技法は、施設内のネットワークの配線及びデバイスのネットワークへの接続を簡単にするが、該ワイヤがメッセージ形態である情報を一度に１つのデバイスからしか運べないから、概して情報転送が遅い。この問題をある程度緩和するために、イーサネットを導入する際に、ネットワークは、多数のサブネットワークに分割される。各サブネットワークは、分離したワイヤを有し、該ワイヤどうしを相互に接続するインターフェースを有する。このような導入をすることで、ワイヤに接続したデバイスに、ワイヤが複数のメッセージを同時に運ぶことができ、同時に転送され得るメッセージ数が増加する。あるワイヤに接続したデバイスが、別のワイヤに接続したデバイスにメッセージを送信する必要があるときのみ、２つまたはそれ以上のサブネットワークにおけるワイヤが使用され、該ワイヤに接続したその他のデバイスが該ワイヤを使用できないようにされる。
【０００３】
この問題を緩和するために、網目状の経路指定ノード（routing node）を介して通信を処理するネットワークが発展している。コンピュータシステム及びその他のデバイスは、様々な経路指定ノードに接続される。経路指定ノード自身が多数のパターンで相互に接続されていることから、対となるデバイス間で、多数の経路が利用可能であり、従って、もし、ある経路が混雑しているならば、別の経路が使用され得る。そのような構成によって、イーサネットネットワークよりも複雑なネットワークとなり得るが、情報転送レート（rate）を本質的により高くすることができ、とりわけ、光ファイバが経路指定ノードとデバイスを相互に接続する媒体として使用されると、情報転送レートをより高くすることができる。このようなネットワークにおいて生じ得る問題点は、経路指定ノードまたはデバイスが、ネットワーク上の別の経路指定ノードまたはデバイスから情報を受け取っているときに、伝送している経路指定ノードまたはデバイスに「フロー制御（flow-control）」情報を提供する機構を有さないことである。このことによって、ネットワークのコストは節減されるが、その一方で経路指定ノードが伝送できるレートよりも速いレートで情報を受け取るという、混雑（congestion）が生じ得る。
【０００４】
この問題は、ある種のネットワーク、すなわち、ＡＴＭ（「非同期転送モード」）技法に従って実行されるネットワークにおいて検討されている。このネットワークでは、データの「パケット」が、発信元のデバイスから１つまたはそれ以上の宛先のデバイスに、一連の「セル」で伝送される。経路指定ノードは、セルを伝送し得るよりも速く受け取るような混雑を検出すると、幾つかの機構を使用できる。そのような機構の１つは、「早期パケット廃棄（early packet discard）」という名称であり、もし適量の混雑が発生すれば使用され得る。該機構においては、経路指定ノードは、任意の新たなパケットに関するセルの受入れを素早く拒否するが、既に転送が始まっているパケットに関するセルを転送し続けるようにする。これにより、経路指定ノードから下流の混雑が緩和され、或いは少なくとも増加しなくなる。しかしながら、混雑は、ノードが「部分パケット廃棄（partial packet discard）」という名称の第２の機構を作動させる点まで、増加し続ける。部分パケット廃棄においては、経路指定ノードは、もし、増加する混雑により、転送が始まっているパケットの中のあるセルをドロップしなければならないならば、パケットの全セルが、宛先においてパケットを正確に再構築するために要求されるため、同じパケットからのセルをドロップし続けるだろう。もし、部分パケット廃棄機構が混雑により作動するならば、部分パケット廃棄によって混雑が減少するが、廃棄されたパケットは、どんな場合でも発信元によって再伝送されなければならない。従って、部分パケット廃棄機構が作動する前にセルを転送するために使用された経路指定ノードのリソースは、無駄になる。
【０００５】
【課題を解決する為の手段】
本発明は、調整可能なしきい値を有する早期パケット廃棄機構を含む新しく且つ改良されたデジタルネットワークを提供する。セルの輸送に関して早期パケット廃棄機構を作動するときに、該機構により、経路指定ノードが混雑の度合いを調整できるようになる。
【０００６】
簡単に説明すると、ある状況においては、本発明は、複数の経路指定ノードを含むコンピュータネットワークを提供し、各経路指定ノードは、選択される他の経路指定ノードに接続され、少なくとも幾つかの経路指定ノードは、複数のパケット発信元の中の１つ且つ／または複数のパケットの宛先の中の１つに接続される。各経路指定ノードは、パケット発信元によって生成され、且つ複数の直列伝送されるセルを含むパケットの、それぞれのパケット宛先への経路を指定する。少なくとも幾つかの経路指定ノードは、選択した混雑度（degree of congestion）を検出すると、「早期パケット廃棄制御装置（arrangement）」を使用可能にし、該装置において、受け取ったセルであって、該装置が使用可能になる前にセルを受け取らなかったパケットに関するセルを捨てる。経路指定ノードは、以前の選択された時間周期中のセルの受取りレート及び伝送レートに対応する情報に関連して、早期パケット廃棄制御装置が使用可能になる混雑度を周期的に調整する。
【０００７】
他の状況においては、本発明は、コンピュータネットワークに接続して使用するための経路指定ノードを提供する。コンピュータネットワークは、複数の直列伝送されるセルを含み且つ複数のパケット発信元が生成するパケットを、複数のパケット宛先のそれぞれに転送する複数の経路指定ノードを含む。経路指定ノードは、バッファとバッファ制御を具える。バッファは、ネットワーク内の他の経路指定ノードまたはパケットの宛先に伝送されるべきセルを受け取り且つ一時記憶する。バッファ制御は、バッファが選択的にセルを受け取り且つ一時記憶できるようにする。バッファ制御は、早期パケット廃棄制御装置を使用可能にし、該装置において、バッファが選択された数のセルを直ちに一時記憶するとき、バッファが、早期パケット廃棄制御装置機構を使用可能にする前に、セルを受け取り始めなかったパケットに関連するセルを一時記憶することを禁止する。バッファ制御は、以前の選択された時間周期中のセルの受取りレート及び伝送レートに対する情報に関連して、選択される数を周期的に調整する。
【０００８】
【効果】
上記のように構成されることにより、セルの輸送に関して早期パケット廃棄機構を作動するときに、該機構により、経路指定ノードが混雑の度合いを調整できる。従って、経路指定ノードのリソースが無駄になることを低減できる。
【０００９】
【発明の実施の形態】
図１は、多数のデバイス間のデータを表わす信号を転送する複数の経路指定ノード(11(1))〜(11(N))（一般的に、参照数字(11(n))によって示される）を含むコンピュータネットワーク(10)の概要図である。図１において、前記デバイスは、コンピュータシステム(12(1))〜(12(M))（一般的に、参照数字(12(m))によって示される）によって表わされている。コンピュータシステム(12(m))は、従来と同様、プログラム命令に従ってデータを処理し、処理されたデータを生成する。データ処理において、コンピュータシステム(12(mS))（添字の「Ｓ」は「発信元」を示す）は、発信元コンピュータシステムの如く、データ、処理されたデータ及び／またはプログラム命令（本願では、通常、これら全てを「情報」と呼ぶ）を、別の宛先のコンピュータシステム(12(mD))（添字の「Ｄ」は「宛先」を示す）に転送する必要があり得るし、該宛先のコンピュータシステム(12(mD))が、動作中に転送された情報を使用する必要があり得る。各コンピュータシステム(12(m))は、データの伝送または受取りを容易に行なうために、通信リンク（一般的に、参照数字(13(p))によって示される）を通して、経路指定ノード(11(n))に接続される。経路指定ノード(11(n))は、ノード(11(n))間でのデータ転送を容易に行なうために、通信リンク(13(p))によって相互接続される。通信リンク(13(p))は、任意の便利なデータ伝送媒体を利用し得る；ある実施形態では、各通信リンク(13(p))の伝送媒体は、１つまたはそれ以上の光ファイバリンク（fiber optic link）の中から選択される。各通信リンク(13(p))は、双方向性であり、経路指定ノード(11(n))が、互いのノード(11(n))間及び同様のリンクを通して接続されるコンピュータシステム(12(m))との信号を伝送し且つ受け取ることができるようにするのが望ましい；通信リンク(13(p))が光ファイバリンクである実施形態では、各通信リンク(13(p))に対して、２つの光ファイバが配備され、それぞれが光信号を一方向に容易に転送する。
【００１０】
ある実施形態では、ネットワーク(10)は、公知の「ＡＴＭ」（非同期転送モード）転送技法を用いてデータを転送する。該技法は、Ｃ．パートリッジ（Partridge）、「ギガビット・ネットワーキング」[Reading MA: Addison Wesley Publishing Company, 1994]、主に第３章と第４章、及びＤ．マクダイサン（McDysan）等、「ＡＴＭの理論と応用」[McGraw Hill,1995]に詳細に説明されているので、詳細は省略する。図２を参照すると、一般に、ＡＴＭ技法では、コンピュータシステム(12(m))及び経路指定ノード(11(n))は、固定長「セル」の形態で、データを伝送する。ＡＴＭのデータ転送技法では、パケット(20)を発信元コンピュータシステム(12(mS))から宛先のコンピュータシステム(12(mD))に伝送するために、ＡＴＭのデータ転送技法では、パケット(20)を発信元コンピュータシステム(12(mS))から宛先のコンピュータシステム(12(mD))に伝送するために、発信元コンピュータシステム(12(mS))が、データパケット(20)を、ＣＥＬＬ(1)〜ＣＥＬＬ(I)（一般的に、「ＣＥＬＬ(i)」）と表される複数の「セル」に割り当て、通信リンク(13(p))を通して直列に伝送して、そこからネットワーク(10)を通して転送し始める。各セルは、ヘッダ部ＨＤＲ(i)及びデータ部ＤＡＴＡ(i)を含んでおり、ヘッダ部ＨＤＲ(i)は、ネットワーク(10)を通してセルの転送を制御するために、パス識別子及び「仮想サーキット（circuit）」情報を含んでおり、そして、データ部ＤＡＴＡ(i)は、パケット(20)からのデータを含んでいる。各セルのデータ部ＤＡＴＡ(i)は、所定の固定長（ある実施例では、48バイト）を有し、従って、もし、パケット(20)におけるデータ量が各セルのデータ部ＤＡＴＡ(i)のサイズの整数倍でないため、最後のデータ部ＤＡＴＡ(i)が所望の長さを有すことが信頼できないならば、発信元コンピュータシステム(12(mS))は、最後のデータ部ＤＡＴＡ(i)にて、データを引き伸ばす（pad）だろう。
【００１１】
上述のように、発信元コンピュータシステム(12(mS))は、データパケット(20)から生成された一連のセルＣＥＬＬ(1)〜ＣＥＬＬ(I)を伝送し、ネットワーク(10)は、宛先のコンピュータシステム(12(mD))へ、セルを伝送順に引き渡すことができる。宛先のコンピュータシステム(12(mD))は、パケット(20)を再構築するために、発信元コンピュータシステム(12(mS))によって伝送されるセルの全てを受け取らなければならない。上述のＡＴＭ転送技法において、セルは、順番の情報を含まない。従って、宛先のコンピュータシステム(12(mD))は、セルを受け取る順番から、パケット(20)を再構築するべき適当な順番を決定する。最後のセルＣＥＬＬ(i)は、パケットの最後のセルであることを示すために、図２のＥＯＰで示されるパケットの終了設定フラグ（set end of packet flag）を含む。
【００１２】
さらに、上述のように、ヘッダ部ＨＤＲ(i)は、パス識別子及び「仮想サーキット」情報を含んでおり、両方ともネットワーク(10)を通してセルの転送を制御する。各経路指定ノード(11(n))は、次の経路指定ノードまたは宛先のコンピュータシステム(12(mD))に、セルを伝送するべき出力側通信リンクを特定するために、入力側通信リンクを通して受け取るセルＣＥＬＬ(p)のパス識別子及び仮想サーキット情報を使用する。パケット(20)に関連するセルＣＥＬＬ(i)のヘッダ部ＨＤＲ(i)における仮想サーキット情報は、同じであるが、異なるパケットに関するセルに関しては、異なるであろう。宛先のコンピュータシステム(12(mD))は、特定のパケット(20)に関して生成されたセルを、パケットのデータ順に受け取っているであろうが、幾つかの発信元コンピュータシステム(12(mS))を始発とするセルを、ネットワーク(10)から同時に受け取っているかもしれないし、インターリーブの方法でセルを受け取るかもしれない。各ＣＥＬＬ(i)における仮想サーキット情報によって、宛先のコンピュータシステム(12(mD))が、セルに関連するパケット(20)を決定することができるであろう。
【００１３】
ネットワーク(10)を構成している経路指定ノード(11(n))の全ては、通常、同じ構造を有しており、その構造を図３に沿って説明する。図３を参照すると、各経路指定ノード(11(n))は、入力インターフェース(30)、バッファ(32)及び出力インターフェース(34)を含み、これら全ては制御エレメント(35)の制御下にある。双方向の通信を容易に行なうために、入力インターフェース(30)及び出力インターフェース(34)は、通信リンク(13(p))の全てに接続される。そして該通信リンク(13(p))に対して経路指定ノード(11(n))が接続されて、ネットワーク(10)上の他の経路指定ノードまたは接続されるコンピュータシステム(12(m))の中の１つからの信号の受取り及び送信を容易に行えるようにしている。通信リンク(13(p))が光ファイバの形態である上述の実施例の場合では、入力インターフェース(30)は、経路指定ノード(11(n))が光信号を受け取るある一方の通信リンク、すなわち入力通信リンク(13(p)(i))に接続され、出力インターフェース(34)は、経路指定ノードが光信号を伝送する他方の通信リンク、すなわち出力通信リンク(13(p)(o))に接続される。各入力通信リンク(13(p)(i))は、ネットワーク(11)上のコンピュータシステム(12(m))または他の経路指定ノードが信号を伝送する出力通信リンクを構成し、且つ各出力通信リンク(13(p)(o))は、ネットワーク(11)上のコンピュータシステム(12(m))または他の経路指定ノードが信号を受け取る入力通信リンクを構成することが明らかであろう。
【００１４】
入力インターフェース(30)は、制御エレメント(35)の制御下にあり、セルＣＥＬＬ(n)の特徴となる光信号を、入力通信リンクから受け取り、電気的形態に変換して、一時記憶のためにバッファ(32)に供給する。バッファ(32)は、入力インターフェース(30)が全ての入力通信リンク(13(p)(i))から受け取る光学的セルに対応して生成する電気的形態のセルＣＥＬＬ(i)を、受け取り且つ一時記憶する単一バッファ（unitary buffer）を具え得る。或いは、バッファ(32)は、別々の出力通信リンク(13(p)(o))に対して割当てられ、夫々が、出力通信リンク(13(p)(o))の中の１つまたは選択されたサブセットから伝送されるセルＣＥＬＬ(i)を受け取り且つ一時記憶する複数のバッファ区分を具え得る。出力インターフェース(34)は、通常、伝送されるべきセルＣＥＬＬ(i)を、各出力通信リンク(13(p)(o))を通して、バッファにて受け取られ、且つロードされる順番に伝送する。出力インターフェース(34)は、バッファ(32)にて一時記憶されたセルＣＥＬＬ(i)を受け取り、この時点ではまだ電気信号の形態であるセルを、光学的形態に変換し、且つ、出力通信リンク(13(p)(o))を通して光信号をカップル（couple）する。出力インターフェース(34)によって伝送されるセルＣＥＬＬ(i)に対して、制御エレメント(35)は、伝送されるのに対応して、新しいパス識別子及び仮想サーキット識別子を有するヘッダ部ＨＤＲ(i)に更新し得る。
【００１５】
上述のように、制御エレメント(35)により、入力通信リンク(13(p)(i))から受け取られるセルＣＥＬＬ(i)は、バッファ(32)にて一時記憶されることができる。もし、入力バッファは、セルＣＥＬＬ(i)がバッファ(32)からドレインされ、出力通信リンク(13(p)(o))を通して転送されるよりも速く一杯になるならば、バッファ(32)は、オーバーフローとなり、この場合、その後に受け取られるセルは、一時記憶されないで、その代わりに失われるであろう。制御エレメント(35)は、バッファのオーバーフローの可能性に関連して、２つの機構を利用する。「早期パケット廃棄」として認識される一方の機構に従うと、制御エレメント(35)は、バッファ内容しきい値（buffer contents threshold value）を作り出す。本発明に従うと、バッファ内容しきい値は、以下に記載されるように調整され得る。バッファ(32)にて一時記憶されるセルＣＥＬＬ(i)の数が、バッファ内容しきい値よりも大きいならば、制御エレメント(35)は、バッファ(32)が、以前に一時記憶されることができたパケットに関連するセルＣＥＬＬ(i)を一時記憶し続けることを可能とするだろう。しかしながら、もし、そのような状態である間に、新たなパケットの最初のセルが受け取られるならば、制御エレメント(35)は、セルＣＥＬＬ(0)及び同じパケットに関してその後に受け取られるセルが、バッファ(32)にて一時記憶されることを禁止するだろう。
【００１６】
「部分パケット廃棄」として認識される第２の機構に従うと、もし、バッファ(32)が、早期パケット廃棄機構の適用にかかわらず、実際にオーバーフローするならば、制御エレメント(35)は、バッファが一杯である間、バッファ(32)がセルＣＥＬＬ(i)を一時記憶することを禁止し、該セルを捨てるようにするだろう。さらに、バッファ(32)にて一時記憶されるセルの数が、もはやオーバーフローしなくなるまで減らされた後も、制御エレメント(35)は、バッファ(32)がオーバーフロー状況にある間にセルが捨てられたパケットに関連するセルを、特に、それぞれのセルのヘッダ部ＨＤＲ(i)におけるパス識別子及び仮想サーキット識別子の情報を用いて、パケット終了フラグＥＯＰがセットされるセルを検出するまで捨て続ける。ＡＴＭ転送技法では、セルＣＥＬＬ(i)が、セル順に伝送され且つ受け取られることから、経路指定ノード(11(n))がパケットに関連するセルを捨て始めるとき、宛先にパケットを再構築するために要求されるセルの全てを提供しないことから、パケットに関連するその後のセルの転送は、経路指定ノードのリソースで無駄になるだろう。主な例外は最後のセルであり、というのは、パケット終了フラグＥＯＰの設定は、セルを受け取った宛先のコンピュータシステム(12(mD))が、そのセルがパケットに関して受け取る最後のセルであるということを知るからである。その後、宛先のコンピュータシステム(12(mD))及び発信元コンピュータシステム(12(mS))は、捨てられたパケットの再伝送を容易に行なうような、所定のエラー修復技術を利用するだろう。
【００１７】
早期パケット廃棄技法を使用することによって、制御エレメントは、セルが一時記憶するレートをある程度減少し、すでに転送を開始しているパケットに関連するセルＣＥＬＬ(i)の全てを転送できる程度に増加させるだろう。
【００１８】
上述のように、本発明に従って、早期パケット廃棄技法を作動する際に、経路指定ノード(11(n))の制御エレメント(35)は、固定のバッファ内容しきい値を使用せず、代りに経路指定ノード(11(n))を通じてのパケット及びセルの通信量に関連してバッファ内容しきい値を制御及び調整する。バッファ内容しきい値を制御及び調整する際において、制御エレメント(35)が行なう操作は、図４及び図５並びに図６〜図９のフローチャートと共に説明される。始めに図４及び図５を参照すると、これらの図は、バッファ(32)を概要的に表示している。従来と同様、バッファ(32)は、複数の記憶場所（別々には示していない）を具え、図４にて示される実施形態では、バッファ(32)の右側端部で示される出力端(40)での出力記憶場所「１」から、バッファ(32)の左側端部で示される入力端(41)での入力記憶場所「Ｂ」まで伸びている「Ｂ」記憶場所を含むように示される。セルは、入力インターフェース(30)から、入力端(41)に接続した１つまたはそれ以上の入力ライン(42)を通して、バッファ(32)に結合され、バッファ(32)から出力端(40)を通してドレインされ、１つまたはそれ以上の出力ライン(43)を通して、出力インターフェース(34)に転送される。図４において、セルが入力端(41)を通してバッファ(32)内にロードされるとき、以前にロードされ未だにドレインされていないセルのトップにパックされ（pack）、各セルがバッファからドレインされると、バッファ内のドレインされてないセルは、出力端(40)の方へ詰込まれるように、出力端(40)の方へシフトするだろう。
【００１９】
図４にて示されるように、「Ｅ」値、「Ｘ」値及び「Ｐ」値として特定される３つのパラメータは、本発明に従う早期パケット廃棄を理解することに関連して役立つ。図４にて示されるパラメータ「Ｅ」は、上述のバッファ内容しきい値に等しく、破線(44)は、バッファ(32)において、図４の出力端(40)からの「Ｅ」記憶場所を表わす位置を示す。従って、バッファ(32)は、破線(44)でのＥ番目の記憶場所を占めるのに十分な数のセルを含むとき、制御エレメント(35)は、早期パケット廃棄技法を作動する。パラメータ「Ｘ」は、「Ｅ番目の」記憶場所を越えたバッファの残り部分におけるバッファの数を特定し、どんな場合でも、「Ｂ−Ｅ」に等しい。「Ｘ」の値は、早期パケット廃棄技法の動作に続いて、バッファ(32)が一杯になって、部分パケット廃棄技法を作動し始める前に、バッファ(32)が入力されるセルを一時記憶する際に使用する記憶場所の数を意味するということが理解されるだろう。値「Ｐ」は、図４にて示される２番目の破線(45)から、バッファ主記憶装置(２)於ける最後の記憶場所まで広がる記憶場所の数を特定する。２番目の破線(45)は、パケットの最後設定フラグＥＯＰを有し、パケットに関して最後のセルであることを示すセルを含むバッファ(32)における最後の記憶場所を表わす。
【００２０】
制御エレメント(35)は、パラメータ「Ｅ」（すなわち、バッファ内容しきい値の現在の値）、「Ｘ」及び「Ｐ」（以下で説明されるように、蓄積できるメッセージ通信の統計量を用いて決定できる）の値を、「Ｂ」の値（バッファ(32)における記憶場所の数に等しい）と共に使用して、バッファ内容しきい値の値を調整し、特に図４にて示されるように増加して、制御エレメント(35)が早期パケット廃棄技法を作動する前に一杯になるバッファ(32)の部分を拡大する。上述のように、バッファ(32)におけるしきい線(44)と最後の「Ｂ番目の」記憶場所の部分は、早期パケット廃棄技法が作動した後に部分パケット廃棄技法に進む制御エレメント(35)の見込みを減少するために与えられる。従って、
(i)もし、バッファ(32)に一時記憶されるセルの数がバッファ内容しきい値よりも大きいならば、制御エレメント(35)は、早期パケット廃棄技法を作動し、且つ  (ii)もし、バッファ(32)が、早期パケット廃棄技法の下で、パケットに関するセルをまだ一時記憶しているならば（なぜなら、そのセルは、制御エレメントが早期パケット廃棄技法を作動したときに、一時記憶されているパケットに関連するものだからである）、パケット終了設定フラグＥＯＰを有するセル全てが、バッファ(32)の、破線(44)によって表わされるバッファ内容しきい値に相当する記憶場所を越えて、破線(45)によって表わされる記憶場所（すなわち、図４の値「Ｘ−Ｐ」は正である）以下の領域に割当てられ、
バッファ内容しきい値「Ｅ」は拡大されることができ、その結果、図４にて「Ｘ−Ｐ」で示される領域は、バッファ(32)の上端に位置付けられる。このことは、バッファ(32)が、早期パケット廃棄技法が作動するしきい点を越えて十分な空間を有して、少なくとも、早期パケット廃棄技法が作動する時に一時記憶されているパケットに関連する最後のセルに対して一時記憶できる。
【００２１】
図５もまた、上述したようなバッファ(32)を示し、図４と同様の参照記号を有するパラメータ「Ｅ」を示し、４番目のパラメータ、すなわちパラメータ「Ｄ」を示す。パラメータ「Ｄ」は、本発明についての早期パケット廃棄機構を理解することに関連して、特に、バッファ内容しきい値が減少できる場合に役立つ。特に、パラメータ「Ｄ」の値は、選択した時間周期の間ずっとセルを含む記憶場所の最大数に等しく、図５において破線(46)によって表わされる。もし、パラメータ「Ｄ」の値がパラメータＥの値（バッファ内容しきい値）よりも小さいならば、バッファ内容しきい値は、パラメータ「Ｄ」の値に等しくなるまで減少させることができ、パラメータ「Ｄ」の値を測定する際に起こり得る不正確さを反映するのに役立ち得る小さいマージン「δ」分増加させることが望ましい。もし、バッファ内容しきい値は、図５に関連して、上述のように減少されるならば、パラメータ「Ｘ」によって表わされ、バッファ内容しきい値に対応する記憶場所を越えて位置付けられる記憶場所の数が増加されるだろう。
【００２２】
制御エレメント(35)は、図４に関連して上述したように、バッファ内容しきい値を増加し得るし、図５に関連して上述したように、バッファ内容しきい値を減少し得る。その増減は、以下に記載されるように生成される一時記憶されたセル通信量の情報に関連する。バッファ内容しきい値を増加すると、制御エレメント(35)が早期パケット廃棄技法を作動する前に、バッファ(32)が一時記憶するセルの数を増加すること、及び、もしセルの通信量が増加するならば、部分パケット廃棄を避けるために、一時記憶に使用可能な量を減少することが理解されるであろう。他方、バッファ内容しきい値を減少すると、制御エレメントが早期パケット廃棄技法を作動する前に、バッファ(32)が一時記憶するセルの数を減少するだろう。このことは、制御エレメント(35)が早期パケット技法を比較的速く作動する見込みを増加し、それにより、パケットが捨てられる見込みを増加し得る。しかしながら、バッファ(32)の中のバッファ内容しきい値によって特定され、経路指定ノード(11(n))が既に一部を転送したパケットの中のセルに関して利用可能である記憶場所を越える部分において、一時記憶する量を増加し、それにより、バッファ(32)がオーバーフローし、且つ制御エレメントが部分パケット廃棄技法を作動しなければならない見込みを減少する。制御エレメント(35)は、バッファ内容しきい値の増加量または減少量を、図４及び図５に関連して上述された技法を用いて、決定され一時記憶されたセル通信量の情報に基づいて周期的に決定する。
【００２３】
ある実施形態における制御エレメント(35)は、以下のように、一時記憶されたセル通信量の情報を蓄積する。制御エレメント(35)は、バッファ(32)によってセルＣＥＬＬ(i)の一時記憶を制御することに加えて、周期的な時間インターバル「ｔ」において、（図５に関連して上述したパラメータＤに関連する）パラメータＤ（ｔ）、バッファ(32)にて一時記憶される最後のセルＣＥＬＬ(i)を含む記憶場所の識別、（図４に関連して上述したパラメータＰに関連する）パラメータＰ（ｔ）、及びバッファ(32)における、パケット終了フラグＥＯＰが設定される最後のセルＣＥＬＬ(i)を含む記憶場所の地点に関する値を決定する。さらに、制御エレメント(35)は、制御エレメント(35)が部分パケット廃棄技法に応答して捨てられるようにできるパケット数に相当するパラメータＰＰＤ（ｔ）に関する値を決定する。
【００２４】
一時記憶されたセルの蓄積された通信量の情報に対応して、制御エレメント(35)は、バッファ内容しきい値が調整されるべきかどうかを決定する。始めに、制御エレメント(35)は、バッファ内容しきい値が、パラメータＰＰＤ（ｔ）の値（すなわち、部分パケット廃棄技法に対応して捨てられるパケットの数）及びパラメータＰ（ｔ）の値の間で選択される関係に対応して、調整されるべきかどうかを決定し、特に、ある実施形態では、パラメータＰＰＤ（ｔ）の値がパラメータＰ（ｔ）の選択される割合よりも上であるかどうかを決定する。もしそうであるならば、制御エレメント(35)は、バッファ内容しきい値を、同じ実施形態において、パラメータＰＰＤ（ｔ）の値とパラメータＰ（ｔ）の値の関係に関連しても選択される量の分だけ減少する。
【００２５】
制御エレメント(35)は、もし、パラメータＰＰＤ（ｔ）の値が、選択されるレベルよりも小さく、バッファ内容しきい値が、パラメータＰＰＤ（ｔ）及びＰ（ｔ）の間の関係に対応して、調整されないと判定するならば、バッファ内容しきい値が、パラメータＤ（ｔ）、Ｐ（ｔ）及びバッファのサイズＢの間の関係に対応して、調整されるべきかどうかを決定する。始めに、制御エレメント(35)は、時間インターバルより短い周期「Ｋ」を通じての前記パラメータの値を測定し、パラメータＰ（ｔ）の平均値としての統計量ＰM（ｔ）、パラメータＰ（ｔ）の分散値としての統計量Ｐσ（ｔ）及びパラメータＤ（ｔ）の平均値としての統計量ＤM（ｔ）を生成する。制御エレメント(35)は、統計量Ｐσ（ｔ）の値、すなわちパラメータＰ（ｔ）の分散を検査して、パラメータＰ（ｔ）及びＤ（ｔ）並びに統計量ＰM（ｔ）及びＤM（ｔ）が、バッファ内容しきい値の調整を容易に行なうために、「信頼できる」かどうかを決定する。もし、分散の統計値Ｐσ（ｔ）が比較的小さいならば、時間インターバル「Ｋ」の間で測定されるパラメータＰ（ｔ）の値は、全て、その平均値である統計量ＰM（ｔ）に比較的密接しており、パラメータＰ（ｔ）及びＤ（ｔ）の値並びに統計量ＰM（ｔ）及びＤM（ｔ）は、バッファ内容しきい値を調整するために使用するのに十分「信頼できる」ことが示される。他方では、もし、分散の統計値Ｐσ（ｔ）が比較的大きいならば、時間インターバル「Ｋ」の間で測定されるパラメータＰ（ｔ）の値は、幅広く分布しており、パラメータの値及び統計量は、信頼できず、バッファ内容しきい値を調整するために使用されるべきではないことが示される。
【００２６】
もし、制御エレメント(35)は、分散の統計量Ｐσ（ｔ）によって、パラメータＰ（ｔ）及びＤ（ｔ）の値並びに統計量ＰM（ｔ）及びＤM（ｔ）がバッファ内容しきい値を調整するために使用するのに十分「信頼できる」ことが示されると、決定するならば、通常、図４及び図５と関連して上述されるような調整される値を生成する。特に、制御エレメント(35)は、始めに、バッファ内容しきい値を増加すべきかどうかを決定する。その決定を行なう際に、制御エレメント(35)は、Ｂ−［Ｘ−（ＰM（ｔ）＋Ｐσ（ｔ）））］の値を測定して、その測定値は、もしバッファ内容しきい値「Ｅ」の現在値よりも大きいならば、バッファ内容しきい値の現在値を更新するために使用される。値「［Ｘ−（ＰM（ｔ）＋Ｐσ（ｔ）））］」は、図４に関連して上述された値「Ｘ−Ｐ」と似ているが、エラーのマージンを与えるための平均統計量ＰM（ｔ）及び分散Ｐσ（ｔ）の和は、加数Ｐを代用することは、理解されるであろう。
【００２７】
制御エレメント(35)は、もしバッファ内容しきい値が増加されるべきでないと決定するならば、減少されるべきかどうかを決定するだろう。その動作において、制御エレメント(35)は、ＤM（ｔ）＋［１／Ｐσ（ｔ）］の値を生成し、その値は、もし、バッファ内容しきい値の現在値よりも小さいならば、バッファ内容しきい値の現在値を更新するために使用されるであろう。値「［１／Ｐσ（ｔ）］」は、図５に関連して上述されたマージン「δ」に対応することが理解されるであろう。
【００２８】
制御エレメントは、前記動作を周期的に実行して、バッファ内容しきい値を、以前の時間インターバルの選択される数「ｋ」によって定められるウィンドウを通して蓄積される一時記憶されたセルの通信量の情報に対応して、決定されるレベルに維持するだろう。制御エレメント(35)は、以前の時間インターバル「ｋ」によってそれぞれ定められる重複するウィンドウを通して蓄積される統計量を用いて、各時間インターバルの最後でバッファ内容しきい値を調整され、或いは、時間インターバル「ｋ」によって定められる重複しないウィンドウの最後で、バッファ内容しきい値を調整し得る。「ｋ」の値は、調整の敏感度レベルを決定し、「ｋ」の値が大きいと、最近のセル通信量の統計量に調整する敏感度を減少し、「ｋ」の値が小さいと、最近のセル通信量の統計量に調整する敏感度を増加することが理解されるであろう。さらに、もし、制御エレメント(35)が、重複しない技法を使用するならば、「ｋ」の値が大きいと、更新間の時間を増加し、「ｋ」の値が小さいと、更新間の時間を減少することが理解されるであろう。ある実施形態において、「ｋ」の値は、セルがネットワーク(10)を通してコンピュータシステム(12(m))間を転送されるラウンドトリップ時間（round trip time）の最大値を２倍して、ラインレートで割った値に相当するように選択され、その結果、バッファ内容しきい値に対する更新は、コンピュータシステム(12(m))によって作動され得るフロー制御装置によって引き起こされるセル通信量の変化も反映されるであろう。
【００２９】
このバックグランドで、バッファ(32)を制御する際に制御エレメント(35)によって実行される動作は、図６〜図９にて示されるフローチャートと関連して説明される。図６〜図９にて示される動作において、制御エレメント(35)は、一時記憶されるセルの通信量の集められる情報に関して、上述したような重複しないウィンドウ技法を利用すると仮定する。重複するウィンドウ技法を利用するための修正は、当該分野の専門家によって直ちに明らかとなるだろう。図６を参照すると、制御エレメント(35)は、始めに、バッファ内容しきい値の初期値を作り出す（ステップ100）。該初期値は、バッファ(32)における記憶場所の数「Ｂ」の所定の割合であると選択され、或いは、以前の他の同様のネットワークでの経験、または、もし制御エレメント(35)がネットワーク(10)に加えられている経路指定ノード(11(n))の一部であるならば、同じネットワーク(10)における他の経路指定ノードでの経験に対応して選択され得る。
【００３０】
バッファ内容しきい値の初期値を作り出してから、制御エレメント(35)は、インターバルカウンタを作り出し、それに「ｋ」に関して選択される値をロードする（ステップ101）。制御エレメント(35)は、全部のウィンドウに関して、一時記憶されるセルの通信量の情報を集める時を決定するために、インターバルカウンタを使用し、その後、バッファ内容しきい値を、調整するかどうか、どの程度調整するかを決定できる。さらに、制御エレメントは、部分パケット廃棄カウンタを作り出し、初期化する（ステップ102）。次に、制御エレメント(35)は、バッファ(32)が図３に関連して上述のように作動できるようにする（ステップ103）。ステップ103に関連する動作の間、制御エレメント(35)は、部分パケット廃棄技法に関連して、パケットを捨てることができるときにいつでも、部分パケット廃棄カウンタを増加する。
【００３１】
さらに、ステップ103に関連する動作の間、制御エレメント(35)は、所定の時間インターバルが終わったかどうかを周期的に判断し（ステップ104）、もしそうであれば、一時記憶されたセルの通信量の情報として、Ｐ（ｔ）及びＤ（ｔ）の値を決定し、且つ、部分パケット廃棄カウンタの値と同様にセーブする（ステップ105）。ステップ105に引続いて、制御エレメントは、インターバルカウンタを下げて（ステップ106）、インターバルカウンタがカウントアウトしたかどうかを判別する（ステップ107）。この時点で、制御エレメント(35)が全ウィンドウの一時記憶されたセルの通信量の情報を集めていない場合には、インターバルカウンタは、カウントアウトされないと仮定し、その場合、制御エレメントは、ステップ102に戻る。
【００３２】
制御エレメント(35)は、ステップ107において、インターバルカウンタがカウントアウトしたかどうかを決定するまで、ステップ102〜ステップ107を、複数の反復を通じて実行し、各反復において、Ｐ（ｔ）及びＤ（ｔ）の値と、一時記憶されたセルの通信量の情報のような部分パケット廃棄カウンタを決定し、インターバルカウンタを減少する。インターバルカウンタがカウントアウトすると、制御エレメントは、一連のステップ110〜118に進み、バッファ内容しきい値が更新されるべきかどうかを決定し、もしそうであれば更新する。始めに、制御エレメント(35)は、セーブされた一時記憶されるセルの通信量の情報Ｐ（ｔ）及びＤ（ｔ）に対応して、平均値ＰM（ｔ）及びＤM（ｔ）並びに分散Ｐσ（ｔ）を生成する（ステップ110）。次に、制御エレメントは、部分パケット廃棄カウンタに対してセーブされた値の和が、ＰM（ｔ）の値の選択された割合よりも大きいかどうかを判定し（ステップ111）、もしそうであれば、バッファ内容しきい値を下げて（ステップ112）、他のウィンドウの始まりで動作を再開するためにステップ101に戻る。
【００３３】
他方では、制御エレメント(35)は、もし、ステップ111において、部分パケット廃棄カウンタに対してセーブされた値の和が、ＰM（ｔ）の値の選択された割合ほど大きくないと判断するならば、ステップ113に進んで、分散の値Ｐ（ｔ）が、平均値ＰM（ｔ）及びＤM（ｔ）が信頼できることを示すほど十分に大きいかどうかを判定する。もしそうであるならば、ステップ114〜116を含むシーケンスに進んで、バッファ内容しきい値が増加されるべきかどうかを決定する。始めに、制御エレメント(35)は、Ｂ−［Ｘ−ＰM（ｔ）＋Ｐσ（ｔ）］の値を生成し（ステップ114）、その値が、バッファ内容しきい値の現在の値よりも大きいかどうかを判断する（ステップ115）。制御エレメントは、もし、ステップ115において正であると判断するならば、ステップ116に進んで、バッファ内容しきい値を、ステップ114にて決定した値に更新し、他のウィンドウの始まりで動作を再開するために、ステップ101に戻る。
【００３４】
最後に、もし、制御エレメント(35)は、ステップ115において、ステップ114にて決定した値がバッファ内容しきい値の現在値ほど大きくないならば、バッファ内容しきい値を増加することはなく、ステップ117〜119を含むシーケンスに進んで、バッファ内容しきい値が減少されるべきかどうかを判断するだろう。その動作において、制御エレメントは、ＤM（ｔ）＋［１／Ｐσ（ｔ）］の値を生成し（ステップ117）、その値がバッファ内容しきい値の現在値よりも小さいかどうかを判断する（ステップ118）。もし、制御エレメントが、ステップ118において正と判断するならば、制御エレメントは、ステップ119に進んで、バッファ内容しきい値を、ステップ118にて決定した値に更新する。ステップ119に引続いて、或いは、もし、制御エレメント(35)は、ステップ117にて生成した値が、バッファ内容しきい値の現在値よりも大きいならば、ステップ118に引続いて、制御エレメント(35)は、他のウィンドウの始まりで動作を再開するために、ステップ101に戻るだろう。
【００３５】
多数の変形が、経路指定ノード(11(n))及び制御エレメント(35)に対してなされ得ることは、理解されるだろう。例えば、制御エレメント(35)は、上述の情報の種類に代えて或いは追加して、様々な種類の一時記憶されたセルの通信量の情報と技法、統計量及びその他のものを利用できる。さらに、制御エレメント(35)は、セルの通信量に関して、平均及び分散のような統計学的測定を用いて、バッファ内容しきい値を調整するように説明してきたけれども、他の統計学的方法及び測定を利用するように見出すことができる。さらに、制御エレメントは、経路指定ノード(11(n))の動作中に、バッファ内容しきい値を調整するため、統計学的測定量を実際に生成する方法を使用するように、説明してきたけれども、制御エレメント(35)は、上述した統計学的技法を用いて生成され、バッファ内容しきい値をセル通信量の関数として認識される参照用テーブル等から、バッファ内容しきい値を得られることができることが理解されるであろう。
【００３６】
さらに、調整可能なバッファ内容しきい値を有する部分パケット廃棄技法及び早期パケット廃棄技法は、ＡＴＭ（非同期転送モード）のデータ転送技法を実行するネットワーク(10)のようなネットワークの他に、様々な種類のネットワークに有益であることが、理解されるであろう。
【００３７】
図１において、ネットワーク(10)は、コンピュータシステム(12(m))に接続されて、その間の情報を容易に転送するように示されているが、ネットワーク(10)は、限定はしないが、ビデオ情報、デジタル画像情報、音声情報等を生成し、受け取るデバイスを含む様々な種類の情報を転送する別種のデバイスに接続され得ることが理解されるであろう。
【００３８】
また、制御エレメント(35)は、デジタルハードウェア、（マイクロプロセッサのような）適当にプログラムされたデジタルコンピュータ、またはそれらの組合せを用いて実行され得ることは、当該分野の専門家によって理解されるであろう。
【００３９】
上記の説明は、本発明の特定の実施形態に限定されている。しかしながら、本発明に様々な変形及び修正を行なって、本発明の特徴の幾つかまたは全てを達成し得ることは、明らかであろう。特許請求の範囲の目的は、前記範囲及び本発明の真の精神及び範囲内に入るような他の変形及び修正をカバーする。
【図面の簡単な説明】
【図１】本発明に従って構築された経路指定ノードを含むコンピュータネットワークを示す概要図である。
【図２】メッセージパケットの構造と、その構成要素であり、図１にて示されるネットワーク上で転送されるメッセージセルを示す模式図である。
【図３】本発明に従って構築され、且つ図１にて示されるコンピュータネットワークにおいて使用される経路指定ノードを示すブロック図である。
【図４】図３におけるバッファの構造を示す概要図であって、しきい値を増やす方向に調整する前後の変化を示す図である。
【図５】図３におけるバッファの構造を示す概要図であって、しきい値を減らす方向に調整する前後の変化を示す図である。
【図６】本発明に従う経路指定ノードの動作を示すフローチャートの一部である。
【図７】本発明に従う経路指定ノードの動作を示すフローチャートの一部である。
【図８】本発明に従う経路指定ノードの動作を示すフローチャートの一部である。
【図９】本発明に従う経路指定ノードの動作を示すフローチャートの一部である。
【符号の説明】
(10)  ネットワーク
(11)  経路指定ノード
(12)  コンピュータシステム
(13)  通信リンク
(20)  パケット
(30)  入力インターフェース
(32)  バッファ
(34)  出力インターフェース
(35)  制御エレメント
【図１】
0003792782.tif 000002
【図２】
0003792782.tif 000003
【図３】
0003792782.tif 000004
【図４】
0003792782.tif 000005
【図５】
0003792782.tif 000006
【図６】
0003792782.tif 000007
【図７】
0003792782.tif 000008
【図８】
0003792782.tif 000009
【図９】
0003792782.tif 000010