(57)【要約】データ・パケットの待ち行列を管理する方法であって、前記データ・パケットは第一のパケット型のデータ・パケットおよび第二のパケット型のデータ・パケットを含む。本方法は、前記第一および第二のパケット型の受領されたパケットを順序付けられた諸グループの系列にグループ化し、各グループは少なくとも一つのパケットを含み；グループの前記系列の先頭における、第二のパケット型のパケットのみを含むグループの数を示すグループ・カウンタを維持し；パケットを送信する段階を含む。第二のパケット型のパケットが送信のために取り出し可能なのは、前記グループ・カウンタが、グループの前記系列の先頭における、第二のパケット型のパケットのみを含むグループの数が０より大きいことを示す場合に、しかしその場合にのみである。
2010539837.tif 000002
【特許請求の範囲】
【請求項１】
データ・パケットの待ち行列を管理する方法であって、前記データ・パケットは第一のパケット型のデータ・パケットおよび第二のパケット型のデータ・パケットを含み、当該方法は：
前記第一および第二のパケット型の受領されたパケットを順序付けられた諸グループの系列にグループ化し、各グループは少なくとも一つのパケットを含み；
グループの前記系列の先頭における第二のパケット型のパケットのみを含むグループの数を示すグループ・カウンタを維持し；
パケットを送信する段階を含み；
第二のパケット型のパケットが送信のために利用可能なのは、前記グループ・カウンタが、グループの前記系列の先頭における第二のパケット型のパケットのみを含むグループの数が０より大きいことを示す場合に、しかしその場合にのみである、方法。
【請求項２】
パケットの送信は、第一のパケット型の最初の受領されたパケットまたは第二のパケット型の最初の受領されたパケットのいずれかを送信することを含む、請求項１記載の方法。
【請求項３】
グループ・カウンタを維持することは、グループの前記系列の先頭における第二のパケット型のパケットのみを含むグループの数に等しいグループ・カウンタを維持することを含む、請求項１または２記載の方法。
【請求項４】
第一のパケット型の受領されたパケットの第一の待ち行列を維持し；
第二のパケット型の受領されたパケットの第二の待ち行列を維持することをさらに含み；
パケットの送信は、第一または第二の待ち行列のいずれかからのパケットを送信することを含む、
請求項１ないし３のうちいずれか一項記載の方法。
【請求項５】
第一のパケット型のパケットまたは第二のパケット型のパケットは、そのパケット型について十分な送信クレジットがある場合にのみ送信のために利用可能である、請求項１ないし４のうちいずれか一項記載の方法。
【請求項６】
各グループは、第一のパケット型のパケットおよび第二のパケット型のパケットを含む、請求項１ないし５のうちいずれか一項記載の方法。
【請求項７】
受領されたパケットを順序付けられた諸グループの系列にグループ化することが、受領された各パケットにグループ・タグを割り当てることを含み、単一のグループ内の各パケットは同じグループ・タグを割り当てられる、請求項１ないし６のうちいずれか一項記載の方法。
【請求項８】
順序付けられた諸グループの前記系列における隣り合うグループ内のパケットは異なるグループ・タグを割り当てられる、請求項７記載の方法。
【請求項９】
受領されたパケットに割り当てられるグループ・タグは、巡回カウンタの現在状態から生成される、請求項７または８記載の方法。
【請求項１０】
新しいグループ毎に前記巡回カウンタの値を変更することをさらに含む、請求項９記載の方法。
【請求項１１】
新しいグループ毎に前記巡回カウンタの値を変更することは、直前の受領されたパケットが第二のパケット型のパケットであった場合に第一のパケット型のパケットが受領されるときに前記巡回カウンタの値を変更し、それにより受領されたパケットが直前に受領されたパケットに割り当てられたグループ・タグとは異なるグループ・タグを割り当てられるようにすることを含む、請求項１０記載の方法。
【請求項１２】
前記変更は、前記巡回カウンタの値をインクリメントすることを含む、請求項１０または１１記載の方法。
【請求項１３】
送信されたパケットが第一のパケット型であり、第一のパケット型の次のパケットと異なるグループ・タグをもつ場合にグループ・カウンタの値を変更することをさらに含む、請求項７ないし１２のうちいずれか一項記載の方法。
【請求項１４】
前記変更は、グループ・カウンタの値を、送信されたパケットのグループ・タグと第一のパケット型の次のパケットのグループ・タグとの間の差の絶対値だけ変えることを含む、請求項１３記載の方法。
【請求項１５】
前記変更は、グループ・カウンタの値をインクリメントすることを含む、請求項１３または１４記載の方法。
【請求項１６】
送信されたパケットが第二のパケット型であり、第二のパケット型の次のパケットと異なるグループ・タグをもつ場合にグループ・カウンタの値を変更することをさらに含む、請求項７ないし１５のうちいずれか一項記載の方法。
【請求項１７】
前記グループ・カウンタの値の変更は、グループ・カウンタの値を、送信されたパケットのグループ・タグと第二のパケット型の次のパケットのグループ・タグとの間の差の絶対値だけ変えることを含む、請求項１６記載の方法。
【請求項１８】
前記変更は、グループ・カウンタの値をデクリメントすることを含む、請求項１６または１７記載の方法。
【請求項１９】
前記データ・パケットはさらに、第三のパケット型のデータ・パケットを含み、当該方法がさらに：
受領されたパケットを第二の順序付けられた諸グループの系列にグループ化し、その系列において各グループは第一のパケット型のパケットおよび第三のパケット型のパケットのみを含み；
グループの前記第二の系列の先頭における第三のパケット型のパケットのみを含むグループの数を示す第二のグループ・カウンタを維持することを含み；
第三のパケット型のパケットが送信のために利用可能なのは、前記第二のグループ・カウンタが、グループの前記第二の系列の先頭における第三のパケット型のパケットのみを含むグループの数が０より大きいことを示す場合に、しかしその場合にのみである、
請求項１ないし１８のうちいずれか一項記載の方法。
【請求項２０】
受領されたパケットを第三の順序付けられた諸グループの系列にグループ化し、その系列において各グループは第二のパケット型のパケットおよび第三のパケット型のパケットを含み；
グループの前記第三の系列の先頭における第三のパケット型のパケットのみを含むグループの数を示す第三のグループ・カウンタを維持することを含み；
第三のパケット型のパケットが送信のために利用可能なのは、前記第三のグループ・カウンタが、グループの前記第三の系列の先頭における第三のパケット型のパケットのみを含むグループの数が０より大きいことを示す場合に、しかしその場合にのみである、
請求項１９記載の方法。
【請求項２１】
請求項１ないし２０のうちいずれか一項記載の方法を実行するようコンピュータを制御するコンピュータ可読コードを担持する担体媒体。
【請求項２２】
データ・パケットの待ち行列を管理するコンピュータ装置であって：
プロセッサ可読命令を記憶するプログラム・メモリと；
前記プログラム・メモリに記憶されている命令を読み、実行するよう構成されているプロセッサとを有しており、
前記プロセッサ可読命令は請求項１ないし２０のうちいずれか一項記載の方法を実行するよう前記プロセッサを制御する命令を含む、装置。
【請求項２３】
データ・パケットの待ち行列を管理する装置であって、前記データ・パケットは第一のパケット型のデータ・パケットおよび第二のパケット型のデータ・パケットを含み、当該装置は：
前記第一および第二のパケット型の受領されたパケットを順序付けられた諸グループの系列にグループ化するよう構成されたグループ化機構を有し、各グループはいずれかのパケット型の少なくとも一つのパケットを含み；
当該装置はさらに：
グループの前記系列の先頭における第二のパケット型のパケットのみを含むグループの数を示すグループ・カウンタと；
パケットを送信するよう構成された送信機とを有し；
第二のパケット型のパケットが送信のために利用可能なのは、前記グループ・カウンタが、グループの前記系列の先頭における第二のパケット型のパケットのみを含むグループの数が０より大きいことを示す値を記憶している場合に、しかしその場合にのみである、装置。
【請求項２４】
前記送信機は、第一のパケット型の第一の受領されたパケットまたは第二のパケット型の第一の受領されたパケットのいずれかを送信するよう構成されている、請求項２３記載の装置。
【請求項２５】
前記グループ・カウンタは、グループの前記系列の先頭における第二のパケット型のパケットのみを含むグループの数に等しい値を記憶する、請求項２３または２４記載の装置。
【請求項２６】
第一のパケット型の受領されたパケットを記憶するよう構成された第一の待ち行列構造と；
第二のパケット型の受領されたパケットを記憶するよう構成された第二の待ち行列構造とをさらに有しており；
前記送信機は、第一の待ち行列構造または第二の待ち行列構造のいずれかからのパケットを送信するよう構成される、
請求項２３ないし２５のうちいずれか一項記載の装置。
【請求項２７】
第一のパケット型のパケットまたは第二のパケット型のパケットは、そのパケット型について十分な送信クレジットがある場合にのみ送信のために利用可能である、請求項２３ないし２６のうちいずれか一項記載の装置。
【請求項２８】
前記グループ化機構は、パケットを、第一のパケット型のパケットおよび第二のパケット型のパケットを含むグループにグループ化するよう構成されている、請求項２３ないし２７のうちいずれか一項記載の装置。
【請求項２９】
前記グループ化機構は、受領された各パケットにグループ・タグを割り当てるよう構成されており、単一のグループ内の各パケットは同じグループ・タグを割り当てられる、請求項２３ないし２８のうちいずれか一項記載の装置。
【請求項３０】
前記グループ化機構は、順序付けられた諸グループの前記系列における隣り合うグループ内のパケットに異なるグループ・タグを割り当てるよう構成されている、請求項２９記載の装置。
【請求項３１】
巡回カウンタをさらに有しており、前記グループ化機構は、受領されたパケットに割り当てられるグループ・タグが前記巡回カウンタの現在状態から生成されるよう構成されている、請求項２９または３０記載の装置。
【請求項３２】
前記巡回カウンタは、各新しいグループの始まりにおいてその値を変更するよう構成されている、請求項３１記載の装置。
【請求項３３】
前記巡回カウンタは、直前の受領されたパケットが第二のパケット型のパケットであった場合に第一のパケット型のパケットが受領されるときに、その値を変更するよう構成されており、それにより受領されたパケットが直前に受領されたパケットに割り当てられたグループ・タグとは異なるグループ・タグを割り当てられる、請求項３２記載の装置。
【請求項３４】
前記巡回カウンタは、新しいグループ毎にその値をインクリメントするよう構成されている、請求項３２または３３記載の装置。
【請求項３５】
前記グループ・カウンタは、送信されたパケットが第一のパケット型であり、第一のパケット型の次のパケットと異なるグループ・タグをもつ場合に、該グループ・カウンタの値を変更するよう構成されている、請求項２９ないし３４のうちいずれか一項記載の装置。
【請求項３６】
前記グループ・カウンタは、その値を、送信されたパケットのグループ・タグと第一のパケット型の次のパケットのグループ・タグとの間の差の絶対値だけ変えるよう構成されている、請求項３５記載の装置。
【請求項３７】
前記グループ・カウンタは、送信されたパケットが第一のパケット型であり、第一のパケット型の次のパケットと異なるグループ・タグをもつ場合に、該グループ・カウンタの値をインクリメントするよう構成されている、請求項３５または３６記載の装置。
【請求項３８】
前記グループ・カウンタは、送信されたパケットが第二のパケット型であり、第二のパケット型の次のパケットと異なるグループ・タグをもつ場合に、該グループ・カウンタの値を変更するよう構成されている、請求項２９ないし３７のうちいずれか一項記載の装置。
【請求項３９】
前記グループ・カウンタは、その値を、送信されたパケットのグループ・タグと第二のパケット型の次のパケットのグループ・タグとの間の差の絶対値だけ変えるよう構成されている、請求項３８記載の装置。
【請求項４０】
前記グループ・カウンタは、送信されたパケットが第二のパケット型であり、第二のパケット型の次のパケットと異なるグループ・タグをもつ場合に、該グループ・カウンタの値をデクリメントするよう構成されている、請求項３８または３９記載の装置。
【請求項４１】
前記データ・パケットはさらに、第三のパケット型のデータ・パケットを含み、前記グループ化機構はさらに：受領されたパケットを第二の順序付けられた諸グループの系列にグループ化するよう構成され、その系列において各グループは第一のパケット型のパケットおよび第三のパケット型のパケットのみを含み、当該装置はさらに：
グループの前記第二の系列の先頭における第三のパケット型のパケットのみを含むグループの数を示すよう構成された第二のグループ・カウンタを有し；
第三のパケット型のパケットが送信のために利用可能なのは、前記第二のグループ・カウンタが、グループの前記第二の系列の先頭における第三のパケット型のパケットのみを含むグループの数が０より大きいことを示す値を記憶している場合に、しかしその場合にのみである、
請求項２３ないし４０のうちいずれか一項記載の装置。
【請求項４２】
前記グループ化機構はさらに、受領されたパケットを第三の順序付けられた諸グループの系列にグループ化するよう構成されており、その系列において各グループは第二のパケット型のパケットおよび第三のパケット型のパケットを含み、当該装置はさらに：
グループの前記第三の系列の先頭における第三のパケット型のパケットのみを含むグループの数を示すよう構成された第三のグループ・カウンタを有し；
第三のパケット型のパケットが送信のために利用可能なのは、前記第三のグループ・カウンタが、グループの前記第三の系列の先頭における第三のパケット型のパケットのみを含むグループの数が０より大きいことを示す値を記憶している場合に、しかしその場合にのみである、
請求項４１記載の装置。
【請求項４３】
当該装置がソースからパケットを受領し、コンピュータ・ネットワーク内の宛先にパケットを転送するよう構成されたネットワーク要素である、請求項２３ないし４２のうちいずれか一項記載の装置。
【請求項４４】
当該装置がネットワーク・ルータである、請求項４３記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ・パケットの待ち行列を管理する方法に関する。より詳細には、これに限るものではないが、本発明は、データ・パケットの待ち行列を管理する方法であって、データ・パケットが第一の型および第二の型の両方のパケットを含む方法に関する。
【背景技術】
【０００２】
コンピュータ・ネットワークにおいて、データ・パケットは、ネットワーク・リンクが過負荷になるのを防ぐためにしばしば送り出される前に待ち行列に入れられる。たとえば、ネットワーク・ルータにおいて、パケットが送信されるのを許容するために前方のネットワーク・リンク上にクレジットが利用可能になるまで、パケットを待ち行列に入れておく必要がある。従来式のコンピュータ・ネットワークでは、待ち行列形成のために異なる要求をもつ異なるパケット型をもつことが知られている。特に、第一のパケット型が送出（onwards  transmission）について相対的により高い優先度である二つの異なるパケット型をもつことが知られている。
【０００３】
そのようなコンピュータ・ネットワークにおいて、二つの相異なるパケット型の予測不可能なシーケンスの待ち行列を管理するために、バイパス機能付き待ち行列（bypass  capable  queue）が実装されうる。第一の型のパケットは待ち行列から順に送信される必要があるが、第二の型についてクレジットが利用可能でない場合には第二の型のパケットを追い越し（overtake）てもよい。第二の型のパケットも待ち行列から順に送信される必要があるが、第一の型のパケットを追い越してはならない。
【０００４】
いずれかのパケット型が送信できる前に、そのパケットについての十分なクレジットが先へのネットワーク・リンク上で利用可能である必要がある。パケットが送信されてもよいのは、ルータまたは他のネットワーク要素が、そのパケット型についての十分なクレジットが利用可能であると識別する場合のみである。
【０００５】
データ・パケットの単一の待ち行列に、同じパケット型の待ち行列内のパケット間のリンクおよびパケット型間のリンクを設けることによって、バイパス機能付き待ち行列を実装することが知られている。リンクは、同じパケット型の待ち行列内の次のパケットおよび他方の型のパケットのグループをポイントする、各パケットと並んで記憶される二つのポインタの形を取ってもよい。パケットが送信のためにスケジューリングされるとき、それらのポインタは個々に更新される必要がある。これは、１型パケットのグループ内の最後のパケットである第一のパケット型のパケットが第二のパケット型のパケットを追い越す場合に特に複雑なプロセスである。さらに、パケットが送信されるたびにポインタ演算が計算上高価となるばかりでなく、このプロセスは誤りが起こりやすくもある。障害によってポインタが損なわれると、バイパス機能付き待ち行列を再確立することは難しいことがありうる。所与のパケット型の次のパケットへのポインタに基づく既知のバイパス機能付き待ち行列は、パケットが送信されるたびに著しい処理を必要とする。
【０００６】
バイパス機能付き待ち行列を実装する代替的なアプローチは、受領される各パケットを、タイムスタンプおよびパケット型の指標とともに記憶することである。どのパケットを送信するかを決定するとき、諸パケットについてのパケット・タイムスタンプおよびパケット型を比較することで、パケットが到着した相対的な順序および各パケット型のパケットが待ち行列内のどこに現れるかを決定できる。この既知のアプローチもまた、計算的に高価である。タイムスタンプ付けのさらなる問題は、タイムスタンプの相対順序を追跡することは、タイムスタンプが一巡して繰り返す（たとえば99から0に）ときに複雑になりうるということである。
【０００７】
各パケット型について別個の待ち行列をもつバイパス機能付き待ち行列を実装することが知られている。しかしながら、そのような既知のバイパス機能付き待ち行列では、相対的なパケット順序を保存するために、タイムスタンプ付けまたは別個のパケット待ち行列の間の何らかの代替的な形のリンクはいまだ必要とされる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本稿または他所において特定される従来技術の問題の一つまたは複数を解消または緩和することが、本発明の実施形態の一つの目的である。
【課題を解決するための手段】
【０００９】
本発明の第一の側面によれば、データ・パケットの待ち行列を管理する方法であって、前記データ・パケットは第一のパケット型のデータ・パケットおよび第二のパケット型のデータ・パケットを含み、当該方法は：受領されたパケットを順序付けられた諸グループの系列にグループ化し、各グループは少なくとも一つのパケットを含み；第二のパケット型のパケットのみを含むグループの系列の先頭におけるグループの数を示すグループ・カウンタを維持し；パケットを送信する段階を含み；第二のパケット型のパケットが送信のために利用可能なのは、前記グループ・カウンタが、第二のパケット型のパケットのみを含むグループの系列の先頭におけるグループの数が０より大きいことを示す場合かつその場合にのみである、方法が提供される。
【００１０】
本発明の上記第一の側面の一つの利点は、第一および第二のパケット型の相対的な順序付けを保存し、第一のパケット型のパケットが第二のパケット型のパケットを追い越すことを許容するバイパス機能付き待ち行列を実装するということである。バイパス機能付き待ち行列を実装する既知の諸方法が遭遇する複雑なポインタ操作またはタイムスタンプ付けのオーバーヘッドは回避される。
【００１１】
パケットの送信は、第一のパケット型の最初の受領されたパケットまたは第二のパケット型の最初の受領されたパケットのいずれかを送信することを含みうる。
【００１２】
グループ・カウンタを維持することは、第二のパケット型のパケットのみを含むグループの系列の先頭におけるグループの数に等しいグループ・カウンタを維持することを含みうる。
【００１３】
本方法はさらに：第一のパケット型の受領されたパケットの第一の待ち行列を維持し；第二のパケット型の受領されたパケットの第二の待ち行列を維持することを含んでいてもよく；パケットの送信は、第一または第二の待ち行列のいずれかからのパケットを送信することを含む。
【００１４】
第一のパケット型のパケットまたは第二のパケット型のパケットは、そのパケット型について十分な送信クレジットがある場合にのみ送信のために利用可能であってもよい。
【００１５】
各グループは、第一のパケット型のパケットおよび第二のパケット型のパケットを含みうる。
【００１６】
受領されたパケットを順序付けられた諸グループの系列にグループ化することは、受領された各パケットにグループ・タグを割り当てることを含み、単一のグループ内の各パケットは同じグループ・タグを割り当てられる。
【００１７】
順序付けられた諸グループの系列における隣接し合うグループ内のパケットは異なるグループ・タグを割り当てられうる。
【００１８】
受領されたパケットに割り当てられるグループ・タグは、巡回カウンタの現在状態から生成されてもよい。本方法はさらに、巡回カウンタの値を新しいグループ毎に変更することを含んでいてもよい。
【００１９】
新しいグループ毎に巡回カウンタの値を変更することは、直前の受領されたパケットが第二のパケット型のパケットであった場合に第一のパケット型のパケットが受領されるときに巡回カウンタの値を変更し、それにより受領されたパケットが直前に受領されたパケットに割り当てられたグループ・タグとは異なるグループ・タグを割り当てられるようにすることを含みうる。前記変更は、巡回カウンタの値をインクリメントすることであってもよい。
【００２０】
本方法はさらに、送信されたパケットが第一のパケット型であり、第一のパケット型の次のパケットと異なるグループ・タグをもつ場合にグループ・カウンタの値を変更することを含みうる。
【００２１】
前記変更は、グループ・カウンタの値を、送信されたパケットのグループ・タグと第一のパケット型の次のパケットのグループ・タグとの間の差の絶対値だけ変えることであってもよい。前記変更は、グループ・カウンタの値をインクリメントすることであってもよい。
【００２２】
本方法はさらに、送信されたパケットが第二のパケット型であり、第二のパケット型の次のパケットと異なるグループ・タグをもつ場合にグループ・カウンタの値を変更することを含みうる。
【００２３】
前記グループ・カウンタの値の変更は、グループ・カウンタの値を、送信されたパケットのグループ・タグと第二のパケット型の次のパケットのグループ・タグとの間の差の絶対値だけ変えることであってもよい。前記変更は、グループ・カウンタの値をデクリメントすることであってもよい。
【００２４】
前記データ・パケットはさらに、第三のパケット型のデータ・パケットを含んでいてもよく、本方法はさらに：受領されたパケットを第二の順序付けられた諸グループの系列にグループ化し、その系列において各グループは第一のパケット型のパケットおよび第三のパケット型のパケットのみを含み；第三のパケット型のパケットのみを含むグループの第二の系列の先頭におけるグループの数を示す第二のグループ・カウンタを維持することを含み；第三のパケット型のパケットが送信のために利用可能なのは、前記第二のグループ・カウンタが、第三のパケット型のパケットのみを含むグループの第二の系列の先頭におけるグループの数が０より大きいことを示す場合に、しかしその場合にのみである。
【００２５】
本方法はさらに、受領されたパケットを第三の順序付けられた諸グループの系列にグループ化し、その系列において各グループは第二のパケット型のパケットおよび第三のパケット型のパケットを含み；第三のパケット型のパケットのみを含むグループの第三の系列の先頭におけるグループの数を示す第三のグループ・カウンタを維持することを含み；第三のパケット型のパケットが送信のために利用可能なのは、前記第三のグループ・カウンタが、第三のパケット型のパケットのみを含むグループの第三の系列の先頭におけるグループの数が０より大きいことを示す場合に、しかしその場合にのみである。
【００２６】
本発明の第二の側面によれば、上記方法を実行するようコンピュータを制御するコンピュータ可読コードを担持する担体媒体が提供される。
【００２７】
本発明の第三の側面によれば、データ・パケットの待ち行列を管理する装置であって、プロセッサ可読命令を記憶するプログラム・メモリおよび前記プログラム・メモリに記憶されている命令を読み、実行するよう構成されているプロセッサとを有しており、前記プロセッサ可読命令は上記方法を実行するよう前記プロセッサを制御する命令を含む、装置が提供される。
【００２８】
本発明の第四の側面によれば、データ・パケットの待ち行列を管理する装置であって、前記データ・パケットは第一のパケット型のデータ・パケットおよび第二のパケット型のデータ・パケットを含み、当該装置は：受領されたパケットを順序付けられた諸グループの系列にグループ化するよう構成されたグループ化機構を有し、各グループはいずれかのパケット型の少なくとも一つのパケットを含み；当該装置はさらに、第二のパケット型のパケットのみを含むグループの系列の先頭におけるグループの数を示すグループ・カウンタと；パケットを送信するよう構成された送信機とを有し；第二のパケット型のパケットが送信のために利用可能なのは、前記グループ・カウンタが、第二のパケット型のパケットのみを含むグループの系列の先頭におけるグループの数が０より大きいことを示す値を記憶している場合に、しかしその場合にのみである、装置が提供される。
【００２９】
前記送信機は、第一のパケット型の第一の受領されたパケットまたは第二のパケット型の第一の受領されたパケットのいずれかを送信するよう構成されうる。
【００３０】
前記グループ・カウンタは、第二のパケット型のパケットのみを含むグループの系列の先頭におけるグループの数に等しい値を記憶しうる。
【００３１】
本装置はさらに：第一のパケット型の受領されたパケットを記憶するよう構成された第一の待ち行列構造と；第二のパケット型の受領されたパケットを記憶するよう構成された第二の待ち行列構造とを有していてもよく；前記送信機は、第一の待ち行列構造または第二の待ち行列構造のいずれかからのパケットを送信するよう構成される。
【００３２】
第一のパケット型のパケットまたは第二のパケット型のパケットは、そのパケット型について十分な送信クレジットがある場合にのみ送信のために利用可能であってもよい。
【００３３】
前記グループ化機構は、パケットを、第一のパケット型のパケットおよび第二のパケット型のパケットを含むグループにグループ化するよう構成されうる。
【００３４】
前記グループ化機構は、受領された各パケットにグループ・タグを割り当てるよう構成されていてもよい。単一のグループ内の各パケットは同じグループ・タグを割り当てられる。
【００３５】
前記グループ化機構は、順序付けられた諸グループの系列における隣接し合うグループ内のパケットに異なるグループ・タグを割り当てるよう構成されていてもよい。
【００３６】
本装置はさらに巡回カウンタを有していてもよく、前記グループ化機構は、受領されたパケットに割り当てられるグループ・タグが巡回カウンタの現在状態から生成されるよう構成されていてもよい。
【００３７】
前記巡回カウンタは、各新しいグループの始まりにおいてその値を変更するよう構成されていてもよい。
【００３８】
前記巡回カウンタは、直前の受領されたパケットが第二のパケット型のパケットであった場合に第一のパケット型のパケットが受領されるときに、その値を変更するよう構成されていてもよく、それにより受領されたパケットが直前に受領されたパケットに割り当てられたグループ・タグとは異なるグループ・タグを割り当てられる。
【００３９】
前記巡回カウンタは、新しいグループ毎にその値をインクリメントするよう構成されていてもよい。
【００４０】
前記グループ・カウンタは、送信されたパケットが第一のパケット型であり、第一のパケット型の次のパケットと異なるグループ・タグをもつ場合に、その値を変更するよう構成されていてもよい。
【００４１】
前記グループ・カウンタは、その値を、送信されたパケットのグループ・タグと第一のパケット型の次のパケットのグループ・タグとの間の差の絶対値だけ変えるよう構成されていてもよい。
【００４２】
前記グループ・カウンタは、送信されたパケットが第一のパケット型であり、第一のパケット型の次のパケットと異なるグループ・タグをもつ場合に、その値をインクリメントするよう構成されていてもよい。
【００４３】
前記グループ・カウンタは、送信されたパケットが第二のパケット型であり、第二のパケット型の次のパケットと異なるグループ・タグをもつ場合に、その値を変更するよう構成されていてもよい。
【００４４】
前記グループ・カウンタは、その値を、送信されたパケットのグループ・タグと第二のパケット型の次のパケットのグループ・タグとの間の差の絶対値だけ変えるよう構成されていてもよい。
【００４５】
前記グループ・カウンタは、送信されたパケットが第二のパケット型であり、第二のパケット型の次のパケットと異なるグループ・タグをもつ場合に、その値をデクリメントするよう構成されていてもよい。
【００４６】
前記データ・パケットはさらに、第三のパケット型のデータ・パケットを含んでいてもよく、前記グループ化機構はさらに：受領されたパケットを第二の順序付けられた諸グループの系列にグループ化するよう構成され、その系列において各グループは第一のパケット型のパケットおよび第三のパケット型のパケットのみを含み；本装置はさらに、第三のパケット型のパケットのみを含むグループの第二の系列の先頭におけるグループの数を示すよう構成された第二のグループ・カウンタを有し；第三のパケット型のパケットが送信のために利用可能なのは、前記第二のグループ・カウンタが、第三のパケット型のパケットのみを含むグループの第二の系列の先頭におけるグループの数が０より大きいことを示す値を記憶している場合に、しかしその場合にのみである。
【００４７】
前記グループ化機構はさらに、受領されたパケットを第三の順序付けられた諸グループの系列にグループ化するよう構成されていてもよく、その系列において各グループは第二のパケット型のパケットおよび第三のパケット型のパケットを含み；本装置はさらに、第三のパケット型のパケットのみを含むグループの第三の系列の先頭におけるグループの数を示すよう構成された第三のグループ・カウンタを有し；第三のパケット型のパケットが送信のために利用可能なのは、前記第三のグループ・カウンタが、第三のパケット型のパケットのみを含むグループの第三の系列の先頭におけるグループの数が０より大きいことを示す値を記憶している場合に、しかしその場合にのみである。
【００４８】
本装置は、ソースからパケットを受領し、コンピュータ・ネットワーク内の宛先にパケットを転送するよう構成されたネットワーク要素を有していてもよい。
【００４９】
本装置は、ネットワーク・ルータであってもよい。
【００５０】
本発明の諸実施形態について、ここで、単に例として、付属の図面を参照して説明する。
【図面の簡単な説明】
【００５１】
【図１】本発明の諸実施形態に基づく、パケットの待ち行列を管理するよう構成されたネットワーク要素を概略的に示す図である。
【図２】本発明のある実施形態に基づく、パケットがバイパス機能付き待ち行列から送信される際の待ち行列状態の変化を概略的に示す図である。
【図３】本発明のある実施形態に基づく、パケットがバイパス機能付き待ち行列から送信される際の待ち行列状態の変化を概略的に示す図である。
【図４】本発明のある実施形態に基づく、パケットがバイパス機能付き待ち行列から送信される際の待ち行列状態の変化を概略的に示す図である。
【図５】本発明のある実施形態に基づく、パケットがバイパス機能付き待ち行列から送信される際の待ち行列状態の変化を概略的に示す図である。
【図６】本発明のある実施形態に基づく、パケットがバイパス機能付き待ち行列から送信される際の待ち行列状態の変化を概略的に示す図である。
【図７】本発明のある実施形態に基づく、パケットがバイパス機能付き待ち行列から送信される際の待ち行列状態の変化を概略的に示す図である。
【図８】本発明のあるさらなる実施形態に基づく、パケットがバイパス機能付き待ち行列から送信される際の待ち行列状態の変化を概略的に示す図である。
【図９】本発明のあるさらなる実施形態に基づく、パケットがバイパス機能付き待ち行列から送信される際の待ち行列状態の変化を概略的に示す図である。
【図１０】本発明のあるさらなる実施形態に基づく、パケットがバイパス機能付き待ち行列から送信される際の待ち行列状態の変化を概略的に示す図である。
【図１１】本発明の諸実施形態に基づくバイパス機能付き待ち行列の実装を概略的に示す図である。
【図１２】本発明の諸実施形態に基づくバイパス機能付き待ち行列からパケットを送信するプロセスをフローチャートの形で概略的に示す図である。
【図１３】本発明の諸実施形態に基づくバイパス機能付き待ち行列にパケットを加えるプロセスをフローチャートの形で概略的に示す図である。
【図１４】障害条件のもとで、図２ないし図７のバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図１５】障害条件のもとで、図２ないし図７のバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図１６】障害条件のもとで、図２ないし図７のバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図１７】障害条件のもとで、図２ないし図７のバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図１８】図１４ないし図１７によって示されるのと同様の障害条件のもとで、本発明のあるさらなる実施形態に基づくバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図１９】図１４ないし図１７によって示されるのと同様の障害条件のもとで、本発明のあるさらなる実施形態に基づくバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図２０】本発明のあるさらなる実施形態に基づくバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図２１】本発明のあるさらなる実施形態に基づくバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図２２】本発明のあるさらなる実施形態に基づくバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図２３】本発明のあるさらなる実施形態に基づくバイパス機能付き待ち行列からパケットが送信される際の待ち行列状態の変化を概略的に示す図である。
【図２４】図２０ないし図２３のバイパス機能付き待ち行列にパケットが加えられる際の待ち行列状態の変化を概略的に示す図である。
【図２５】図２０ないし図２３のバイパス機能付き待ち行列にパケットが加えられる際の待ち行列状態の変化を概略的に示す図である。
【図２６】図２０ないし図２３のバイパス機能付き待ち行列にパケットが加えられる際の待ち行列状態の変化を概略的に示す図である。
【図２７】図２０ないし図２３のバイパス機能付き待ち行列にパケットが加えられる際の待ち行列状態の変化を概略的に示す図である。
【図２８】図２０ないし図２３のバイパス機能付き待ち行列にパケットが加えられる際の待ち行列状態の変化を概略的に示す図である。
【発明を実施するための形態】
【００５２】
まず図１を参照すると、この図は、本発明の諸実施形態に基づく、データ・パケットの待ち行列を管理する方法を実装するネットワーク要素１を概略的に示している。ネットワーク要素１は、コンピュータ２（または他のネットワーク要素）からネットワーク・リンク３に沿ってデータ・パケットを受領し、データ・パケットをネットワーク・リンク５に沿ってコンピュータ４（または他のネットワーク要素）に送信するよう構成されている。ネットワーク要素１は、本発明のある種の実施形態では、ネットワーク・リンク５が過負荷になるのを防ぐため、コンピュータ２から受領されるパケットを待ち行列に入れ、ネットワーク・リンク５上で十分なクレジットが利用可能になる際にコンピュータ４にパケットを送信するよう構成されうる。
【００５３】
図２は、単一のソース（コンピュータ２）から到着して単一の宛先（コンピュータ４）に送信されようとしている、ネットワーク要素１において受領される全パケットを描いている。しかしながら、本発明のある種の実施形態では、ネットワーク要素１はたとえば、複数のソースからパケットを受領し、受領したパケットを待ち行列に入れ、次いで複数の宛先にそれらのパケットを送信するよう構成されたスイッチであってもよい。すなわち、このネットワーク要素は複数の入力においてパケットを受領し、各入力が別個のソースに接続されていてもよく、あるいはこのネットワーク要素は単一の入力に接続され、その単一の入力が最終的に複数のソースに接続されているのでもよい。いずれの場合でも、いずれかの型の受領されたパケットは通例、各入力における同じ待ち行列に入れられる。ただし、ネットワーク要素１の複数のまたは全部の入力からのパケットが、複数のまたは全部の入力についての共通の入力待ち行列を使うことを除外するものではない。同様に、このネットワーク要素は、待ち行列からのパケットを、別個の宛先に接続された複数の出力上で送信してもよい。あるいはまた、このネットワーク要素は、待ち行列からのパケットを、最終的に複数の別個の宛先に接続されている単一の出力上で送信してもよい。
【００５４】
本発明の諸実施形態は、ネットワーク要素においてバイパス機能付き待ち行列を実装する単純化された方法に関する。バイパス機能付き待ち行列要件の一例は、ＰＣＩエクスプレス（PCIe）規格において定義されている。そのようなバイパス機能付き待ち行列形成要件は、二つの相異なるパケット型の予測不可能なシーケンスを生成しうる。それらのパケット型は、順序付きパケット（ordered  packets）およびバイパス可能パケット（bypassable  packet）として分類されうる。
【００５５】
所与のパケット型のパケットが送信できる前に、その特定のパケット型の送信を受け入れるために前方のネットワーク・リンク上に十分なクレジットが利用可能である必要がある。バイパス機能付き待ち行列の本記載においては送信クレジット（transmit  credit）の用語は、パケットを送信するパーミッションがあるか否かを意味して使われている。具体的には、順序付きパケットを送信するための十分な送信クレジットがありうる間、バイパス可能パケットを送信するための不十分な送信クレジットがあることもり、逆にバイパス可能パケットを送信するための十分な送信クレジットがありうる間、順序付きパケットを送信するための不十分な送信クレジットがあることもある。当技術分野で知られているように、各ネットワーク・リンクは各パケット型についてそれぞれのバッファをもち、特定のパケット型についてのクレジットが存在するのは、それぞれのバッファ内に十分なスペースがある場合であり、その場合のみである。
【００５６】
各トラフィック型内のパケットの相対的な順序付けは、保存されねばならない。バイパス可能パケットを送信するために十分な送信クレジットが利用可能でない場合は、順序付きパケットは一つまたは複数のバイパス可能パケットを追い越してもよい（順序付きパケットについての十分な送信クレジットが利用可能であるとして）。バイパス可能パケットは、いかなる順序付きパケットを追い越すことも防止される。換言すると、これは順序付きパケットがバイパス可能パケットよりも高い優先度をもち、そのためバイパス可能パケットを送信するために不十分な送信クレジットがある場合に、バイパス機能付き待ち行列において、順序付きパケットがバイパス可能パケットより先に送信のために考慮されうると見ることができる。これらの順序付けの原理は、次の４つの規則にまとめられる。
１．バイパス可能パケットは、前に待ち行列に入れられた順序付きパケットを追い抜いて（pass）はならない。
２．バイパス可能パケットは、前に待ち行列に入れられたバイパス可能パケットを追い抜いてはならない。
３．順序付きパケットは、前に待ち行列に入れられた順序付きパケットを追い抜いてはならない。
４．順序付きパケットは、前に待ち行列に入れられたバイパス可能パケットであって送信クレジットがないために先に進むことがブロックされているものを追い抜かねばならない（順序付きパケットを送信するための十分な送信クレジットがあれば）。
【００５７】
規則１ないし３への準拠は、各パケット型についてのパケット順序付けを保存する。規則４への準拠は、一つまたは複数の順序付きパケットを送信するための十分な送信クレジットがある場合、バイパス可能パケットのための送信クレジットがないために順序付きパケットの送信が防止されてしまう状況を防止する。
【００５８】
本発明の諸実施形態では、バイパス機能付き待ち行列は、二つの別個の待ち行列構造を使って実装される。一つの待ち行列は順序付きパケットを待ち行列に入れるためであり、一つの待ち行列はバイパス可能パケットを待ち行列に入れるためである。すなわち、別個の順序付きパケット待ち行列およびバイパス可能パケット待ち行列がまとまって単一のバイパス機能付き待ち行列をなす。パケットは、それぞれの順序付きパケット待ち行列またはバイパス可能待ち行列に、受領された順に入れられる。二つの待ち行列のそれぞれの中のパケットは、厳密に待ち行列に入れられた順序で、ネットワーク要素からの送信のために利用可能にされるよう進められる。これにより、上記の規則２および３への準拠が保証される。規則１および４への準拠は、受領されたパケットをグループ化することによって保証される。これについてこれから述べる。
【００５９】
連続的なグループの順序付きパケットがネットワーク要素（図１に示したネットワーク要素１のような）に到着する際、それらのパケットは共通のグループ・タグを割り当てられる。その連続的なグループの順序付きパケットに続いて到着する連続的なグループのバイパス可能なパケットにも同じグループ・タグが割り当てられる。順序付きパケットおよびバイパス可能パケットはそれぞれ順序付きパケット待ち行列またはバイパス可能パケット待ち行列に別個に格納される。各パケットに割り当てられるグループ・タグも、順序付きパケット待ち行列またはバイパス可能パケット待ち行列内で、そのパケットと一緒に格納される。あるグループ内の全パケットは同じグループ・タグを割り当てられ、隣り合うグループは異なるグループ・タグを割り当てられる。
【００６０】
バイパス可能パケットに続いて新しい順序付きパケットまたは順序付きパケットのグループが受領されるとき、グループ・タグは変化する。すなわち、受領されたパケットの型がバイパス可能パケットから順序付きパケットに変化するときにグループ・タグは更新される。だが、受領されたパケット型が順序付きパケットからバイパス可能パケットに変化するときには更新されない。ネットワーク要素に到着する最初のパケットがバイパス可能パケットである場合は、最初のグループはバイパス可能パケットのみを含むことになり、グループ・タグは、最初の順序付きパケットが到着するときに変わることになる。
【００６１】
最初のグループ以外のすべてのグループについて、パケットが受領されて待ち行列に入れられる際に、グループは、（順序付きパケット待ち行列に格納される）連続する順序付きパケットの集合およびそれに続く（バイパス可能パケット待ち行列に格納される）連続するバイパス可能パケットの集合によって定義される。しかしながら、順序付きパケットが上記規則４に従って、より早いバイパス可能パケットより先に送信される（よってその順序付きパケットはそのグループから除去される）場合、そのグループは縮小されてバイパス可能パケットのみを含むようになることがありうる。
【００６２】
グループ・タグは、小さな巡回的に反復する数であってもよい。たとえば、グループ・タグは交互のグループについての0または1であってもよいし（すなわち、1ビットのグループ・タグ）、グループ・タグはたとえば巡回的な2ビット・タグであってもよい。
【００６３】
待ち行列の対に関連付けられたグループ・カウンタが、順序付けられたグループの系列の先頭における、バイパス可能パケットのみを含むグループの数を追跡する。規則１への準拠を保証するため、バイパス可能待ち行列の先頭におけるパケットが送出のために取り出し可能になるのは、グループ・カウンタが0より大きいときのみである。グループ・カウンタが0より大きければ、少なくとも最初のグループはバイパス可能パケットのみを含み、よって最初のバイパス可能パケットより前に入れられた順序付きパケットはない。障害条件下では、グループ・カウンタが負の値になることが可能であるが、これについてはのちに説明する。したがって、グループ・カウンタは符号付き整数として格納される。
【００６４】
本発明のある実施形態では、グループ・カウンタは9ビット変数として実装される。よって、バイパス待ち行列の先頭における、バイパス可能パケットのみを含む512個までの別個のグループを追跡することが可能である。512個になった時点で、さらなるパケットが受領されることはできなくなる。設けられるクレジット限界に到達しているであろうからである。典型的には、内部スイッチ輻輳が存在するのでない限り、バイパス機能付き待ち行列内のパケットの数は小さい。待ち行列に入れられることのできるパケットの最大数はバッファ・サイズに依存し、バッファのサイズを超えない総合サイズの諸パケットを待ち行列に入れることが可能である。
【００６５】
ここで図２を参照すると、この図は、本発明のある実施形態に基づくバイパス機能付き待ち行列内の諸パケットについての待ち行列状態を概略的に示している。待ち行列状態は、表の形で示されており、待ち行列に入れられた諸パケットが別個の列で、そのパケットの型に依存して順序付きパケットの行またはバイパス可能パケットの行において示されている。バイパス機能付き待ち行列は順序付きパケットOおよびバイパス可能パケットBの両方を含み、それぞれ順序付きパケット待ち行列６またはバイパス可能パケット待ち行列７のいずれかの中に格納されている。添え字は、いずれの待ち行列であれパケットが受信される順序を（昇順で）示している。パケットの番号付けは純粋に図面を明確にする目的のためであって、実際にはパケットにシーケンシャルなパケット番号が割り当てられないことは理解されるであろう。よって、待ち行列の前面（つまり最初に受領され待ち行列に入れられたパケット）は右側であり、パケットは到着するにつれて待ち行列の左に追加されていく。
【００６６】
グループ・カウンタの現在状態が示されている。順序付きパケットOおよびバイパス可能パケットBがずらして表示されており、待ち行列の諸対を横断する各水平位置において、いずれかの種類の一つのパケットのみが位置されている（後述するパケットのグループ化を明確にするため）。各グループについてのグループ・タグ８が示されている（ただし、上記したように、割り当てられたグループ・タグは一般に、それぞれの待ち行列内で、グループ内の各パケットと一緒に記憶される）。図２に示すバイパス機能付き待ち行列のためのグループ・タグは1ビットの巡回数（つまり0または1）であり、隣り合うグループは異なるグループ・タグが割り当てられている。最初のグループ（最も右のグループ）はグループ・タグ0が割り当てられているが、代替的に、最初のグループがグループ・タグ1を割り当てられてもよい。
【００６７】
図２に示すバイパス機能付き待ち行列について、グループ・カウンタ９が示されている。グループ・カウンタ９は、最初のグループ（つまり最も早く受領されたパケットのグループ）がバイパス可能なパケットB0およびB1のみを含むので、1の値をもつ。結果として、ネットワーク要素（図１に示すネットワーク要素１のような）の出力において十分なバイパス可能パケット送信クレジットが利用可能であれば、バイパス可能待ち行列の先頭にある一つまたは複数のパケットが送信される。
【００６８】
パケットB0およびB1がこうして送信されると、バイパス機能付き待ち行列状態はその後図３に示すようになる。グループ・カウンタ９は今や値0にセットされる。もはやバイパス機能付き待ち行列の先頭にバイパス可能パケットのみを含むグループがないからである。グループ・カウンタ９を更新するプロセスは、図１２との関連で後述する。グループ・カウンタが0なので、上記の規則１に従って、バイパス可能パケットB4は送信のために取り出し可能ではない。グループ・カウンタ９が0であることは、バイパス機能付き待ち行列の先頭にバイパス可能パケットのみからなるグループがなく、したがって順序付きパケットO2およびO3が現在待ち行列に入れられているバイパス可能パケットのどれよりも先にネットワーク要素において受領されたという事実を反映している。
【００６９】
順序付きパケットO2およびO3について送信クレジットが利用可能であるとすると、これらのパケットは送信され、バイパス機能付き待ち行列状態は図４に示されるようになる。パケットO2およびO3およびB4からなる図３に示されたグループは今や、図４に示される待ち行列状態において、単一のバイパス可能パケットB4のみからなり、よってグループ・カウンタ９は1に戻る。したがって、パケットB4は今や送信のために利用可能である。しかしながら、この時点では、不十分なバイパス可能送信クレジットしかなく、したがって、上記の規則４に従って、バイパス機能付き待ち行列の先頭における閉塞を防止するために、順序付きパケットO5がバイパス可能パケットB4を追い越さなければならない（順序付きパケットを送信するために利用可能な十分な送信クレジットがあるとして）。
【００７０】
順序付きパケットO5が送信された後、バイパス機能付き待ち行列は図５に示されるようになる。今や、最初の順序付きパケットO9より前に二つのグループにおいて四つのバイパス可能パケットB4、B6、B7およびB8があり、よってグループ・カウンタ９は2に増加している。今、十分なバイパス可能送信クレジットが利用可能であるとすると、最初のバイパス可能パケットB4が送信され、待ち行列状態は図６に示されるようになり、グループ・カウンタ９は1に減らされる。パケットB6、B7およびB8が次いで送信され、待ち行列状態は図７に示されるようになり、グループ・カウンタ９は0に減らされる。今やグループ・カウンタ９が0まで減ったので、バイパス可能パケットB10が順序付きパケットを追い越すことを防ぐ（よって上記の規則１への準拠を保証する）ために、順序付き待ち行列の先頭のパケットO9のみが送信されうる。
【００７１】
上述したように、パケットがネットワーク要素において受領されるたびに、グループ・タグ８が新たに受領されたパケットに割り当てられ、そのパケットは順序付き待ち行列６またはバイパス可能待ち行列７のいずれかに適宜格納される。直前のパケットおよび現在受領されたパケットが同じ型であれば（すなわち、両方とも順序付きパケットまたは両方ともバイパス可能パケットであれば）、割り当てられたグループ・タグ８は直前のパケットについてと同じままである（すなわち、直前の受領されたパケットおよび現在受領されたパケットが同じグループに割り当てられる）。さらに上述したように、グループ・タグが変わるのは、バイパス可能パケットである直前のパケットから順序付きパケットである現在のパケットにパケット型の変化がある場合のみである。順序付きパケットである直前のパケットからバイパス可能パケットである現在のパケットにパケット型の変化がある場合にはグループ・タグは変化しない。
【００７２】
図８を参照すると、新たに受領されたデータ・パケットへのグループ・タグの正しい割り当てを容易にするために、二つのさらなる変数が維持され、新たなパケットが受領されるたびに更新される。最後パケット型変数１０ａは、最後に受領されたパケットが順序付きパケットであったかバイパス可能パケットであったかを示す。最後パケット・タグ変数１０ｂは、最後に受領されたパケットに割り当てられたグループ・タグを示す（0または1）。
【００７３】
最後パケット型１０ａおよび最後パケット・タグ１０ｂの変数は、パケットが待ち行列６、７の一方に追加されるときにのみ更新される。しかしながら、受領された最後のパケットが順序付きパケットであり、そのパケットが一つまたは複数の前に待ち行列に入れられたバイパス可能パケットより先にバイパス機能付き待ち行列から除去される場合、最後パケット型変数１０ａはバイパス可能に変更されねばならず、最後パケット・タグ変数１０ｂは、最終バイパス可能パケットのグループ・タグ８に一致するよう変更されねばならない。受領された最後パケットがバイパス可能パケットであった場合、そのパケットは、次に除去されることが可能なのは、それがバイパス機能付き待ち行列中の最後のパケットである（すなわち、他に順序付きパケットやバイパス可能パケットがない）場合のみである。したがって、最後のパケットが除去されると、バイパス機能付き待ち行列は空になり、それらの変数は新たなパケットが受領されるときに、後述するように再初期化されねばならない。
【００７４】
図８を参照すると、この図は図７に示される待ち行列状態を示しているが、最後パケット型および最後パケット・タグの変数１０ａおよび１０ｂのステータスをもそれぞれ示している。受領された最後パケットO12は順序付きパケットであり、グループ・タグ0をもつ。パケットO9が送信された後、待ち行列状態は図９に示されるようになる。
【００７５】
図９の待ち行列状態について、バイパス可能パケットB10について送信クレジットが利用不能である場合、順序付きパケットO11およびO12について送信クレジットが利用可能であれば、それらのパケットが送信され、待ち行列状態は図１０に示されるようになる。あるいはまた、両方のパケットO11およびO12を送信するのに不十分な順序付きパケット送信クレジットしかない場合には、パケットO11のみが最初は送信され、O12は後刻、さらなる順序付きパケットを送信するための十分な順序付きパケット送信クレジットがまたできたときに送信されてもよい。両方のパケットO11およびO12が送信される場合、図１０に示されるように、最後パケット・ステータスの変化を反映するために、最後パケット型変数１０ａはバイパス可能に変わり、最後パケット・タグ変数１０ｂは1に変わる。
【００７６】
ここで図１１を参照して、これから本発明のある実施形態に基づくバイパス機能付き待ち行列の実装について述べる。二つのランダム・アクセス・メモリ（RAM）構造が定義される：各順序付きまたはバイパス可能パケットの内容を記憶するデータRAM  １１と、データRAM  １１内のパケット内容へのポインタを含むパケット記述子１３を記憶する制御RAM  １２である。制御RAM  １２は、順序付きおよびバイパス可能データ待ち行列構造をも実装する。各パケット記述子１３は、データRAM  １１内のパケット内容へのポインタを記憶するのに加えて、各パケットに関係する他の情報を記憶する。すなわち、パケット記述子１３はグループ・タグ１４を含む。
【００７７】
前記バイパス機能付き待ち行列を実装するために、順序付きパケット待ち行列とバイパス可能パケット待ち行列との間のポインタまたは他のリンクを設けることは必要ない。各パケットについてのタイムスタンプも要求されない。前記バイパス機能付き待ち行列を実装するために要求される変数は、一連のレジスタに記憶される。本発明の代替的な実施形態では、変数およびパケット・データが記憶される仕方は変わってもよく、たとえば変数もレジスタでなくRAM内に記憶されてもよい。
【００７８】
二つの待ち行列先頭ポインタQueue  1およびQueue  2がレジスタ１５および１６にそれぞれ格納されている。待ち行列先頭ポインタQueue  1およびQueue  2は、それぞれ順序付き待ち行列およびバイパス可能待ち行列の先頭におけるパケット記述子１３をポイントする。各パケット記述子１３は、ある特定のパケットについてのパケット・データの最初の部分を含むデータRAM  １１内のセル１７へのポインタを記憶する。
【００７９】
そのパケットが単一セルの記憶容量より大きい場合には、データRAM  １１内のポイントされるセル１７は、第二のセル１７へのポインタをも含んでいてもよい。実際、パケットのサイズおよび各セルのサイズに依存して、単一パケットは何個のセル１７にまたがって記憶されてもよく、各セルと後続セルの間にリンクが設けられる。単一のパケットの一部を記憶する最後のセル１７は、さらなるセル１７へのポインタの代わりに「終了（END）」タグによって示される。単一のパケットを形成するセルがRAMの連続的なブロックをなす必要はないことは理解されるであろう。さらに、セルはデータRAM  １１内でいかなる特定の順序に配列される必要もない。
【００８０】
パケット記述子１３は、パケット・データの一部を記憶する最初のセル１７へのポインタおよびグループ・タグ１４を記憶することに加えて、ルーティング情報のような他の情報をも記憶してもよい。上述したように、各待ち行列内の最初のパケットについてのパケット記述子１３は、待ち行列先頭ポインタQueue  1またはQueue  2によってポイントされる。各パケット記述子１３はさらに、その待ち行列内の次のパケットについてのパケット記述子１３へのポインタを記憶する。制御RAM  １２内の各待ち行列についてのパケット記述子１３は、RAMの連続的なブロックに記憶される必要はなく、制御RAM中でいかなる特定の順序で記憶される必要もない。
【００８１】
最後パケット型および最後パケット・タグの変数はレジスタ１８および１９にそれぞれ記憶される。最後パケット型および最後パケット・タグの変数は、次にどのパケットを送信するかおよび新たなパケットが受領されるときにどのグループ・タグを割り当てるかを決定することにおいて使用される。これについては、それぞれ図１２および図１３のフローチャートとの関連で後述する。グループ・カウンタはレジスタ２０に記憶される。
【００８２】
ここで図１２を参照すると、この図は、前記バイパス機能付き待ち行列から次にどのパケットを送信するかを決定するプロセスをフローチャートの形で概略的に示している。本プロセスはステップS1において始まり、判断ステップS2に進み、この時点でグループ・カウンタの現在値が検査される。
【００８３】
グループ・カウンタが0より大きければ、少なくとも一つのバイパス可能パケットが送信のために利用可能である（それより早く待ち行列に入れられた順序付きパケットがないので）。もしそうであれば、プロセスは判断ステップS3に進み、バイパス可能パケットを送信するために十分な送信クレジットがあるかどうかを確認するために利用可能なバイパス可能送信クレジットが検査される。十分な送信クレジットが利用可能であれば、プロセスはステップS4に続き、ポインタQueue  2によってポイントされるバイパス可能待ち行列の先頭にあるバイパス可能パケットを送信する。ポインタQueue  2はステップS5でバイパス可能待ち行列内の次のパケットに更新される。送信されるパケットが最後のバイパス可能パケットであった場合、ポインタQueue  2はヌルまたはデフォルト値にセットされる。
【００８４】
判断ステップS6において、バイパス可能パケットが送信された後にグループ・カウンタを更新することが必要かどうかが判定される。バイパス可能パケットが送信されたとき、送信されたパケットおよびバイパス可能待ち行列内の次のバイパス可能パケットのグループ・タグが比較される。それらのグループ・タグが異なる場合、送信されたパケットは、バイパス機能付き待ち行列の先頭におけるグループ内の最後のパケットであったと推定できる。結果として、バイパス機能付き待ち行列の先頭におけるバイパス可能パケットのみを含むグループが一つ少なくなるので、ステップS7で、グループ・カウンタは、それらのグループ・タグの差の絶対値（すなわちモジュラス）だけデクリメントされる。プロセスは次いでステップS2に戻って送信されるべき次のパケットを決定する。
【００８５】
ステップS6においてグループ・タグの変化が検出されなければ、バイパス機能付き待ち行列の先頭の同じグループ内に他のバイパス可能パケットが残っていると想定でき、よってグループ・カウンタはデクリメントされない。プロセスはステップS2に戻って送信されるべき次のパケットを決定する。
【００８６】
ステップS3において、バイパス可能パケットを送信するために不十分なバイパス可能送信クレジットしかないと判定される場合、プロセスは判断ステップS8に進み、順序付きパケットを送信するために利用可能な十分な順序付き送信クレジットがあるかどうかの検査がなされる。あるいはまた、ステップS2でグループ・カウンタが0（または障害条件では負）であれば、プロセスは直接ステップS8に進む。ステップS8において、順序付きパケットを送信するために不十分な送信クレジットしかないと判定される場合、フローチャートを通じる現在のパス（current  pass）の間、送信されてもよいパケットはなく、プロセスはステップS2に戻る。この際、いくつかの実施形態では、不十分な送信クレジットしか利用可能でない間にグループ・カウンタを繰り返し検査することを防止するために、短い時間遅延S9を介する。
【００８７】
ステップS8において、順序付きパケットが送信されることができると判定される場合（かつ少なくとも一つの送信すべき順序付きパケットがある場合）、順序付きパケット待ち行列の先頭にある順序付きパケットがステップS10で送信される。ポインタQueue  1はステップS11で順序付き待ち行列内の次のパケットに更新される。送信されたパケットが最後の順序付きパケットであった場合、ポインタQueue  1はヌルまたはデフォルト値にセットされる。
【００８８】
判断ステップS12では、順序付きパケットが送信された後にグループ・カウンタを更新することが必要かどうかが判定される。順序付きパケットが送信されたときに送信されたパケットと順序付き待ち行列内の次の順序付きパケットのグループ・タグが比較される。それらのグループ・タグが異なれば、送信されたパケットはバイパス機能付き待ち行列の先頭にあるグループ内の最後の順序付きパケットであったと推定できる。結果として、グループ・カウンタはステップS13において、グループ・タグ間の差の絶対値だけインクリメントされる。これを行うのは、バイパス機能付き待ち行列の先頭にあるグループ内にそれ以上順序付きパケットがない場合、バイパス機能付き待ち行列の前面にバイパス可能パケットのみを含む少なくとももう一つのグループがあるはずだからである。グループ・タグに変化がなければ、バイパス機能付き待ち行列の先頭における同じグループ内に他の順序付きパケットが残っていると推定でき、よってグループ・カウンタはインクリメントされない。いずれにせよ、プロセスはステップS2に戻り、送信されるべき次のパケットを決定する。
【００８９】
図１３を参照すると、この図は、新たに受領されたパケットにグループ・タグを割り当て、最後パケット型および最後パケット・タグの変数を更新するプロセスをフローチャートの形で概略的に示している。プロセスは、新たなパケットが受領されるときにステップS20で始まる。判断ステップS21において、待ち行列先頭ポインタQueue  1およびQueue  2から、バイパス機能付き待ち行列が現在空であるかどうか（すなわち、新たに受領されたパケットが最初の受領されたパケットであるかどうか、あるいは順序付きパケット待ち行列またはバイパス可能パケット待ち行列がすでに少なくとも一つのパケットを含んでいるかどうか）が判定される。バイパス機能付き待ち行列が現在空であれば、ステップS22で、新たに受領されたパケットが任意のグループ・タグ（図１３では1と示されているが、いかなる値でもよい）を割り当てられる。最後パケット・タグ変数は割り当てられたグループ・タグにセットされる。
【００９０】
ステップS23において、新たなパケットがバイパス可能パケットであるかどうかが判定される。新たなパケットがバイパス可能パケットであれば、新たなパケットはバイパス可能パケットのみを含む単一のパケットからなるグループを形成するので、ステップS24で、グループ・カウンタは1にセットされる。ステップS24ではまた、最後パケット型変数がバイパス可能にセットされる。しかしながら、ステップS23において新たなパケットが順序付きパケットであると判定される場合、ステップS25においてグループ・カウンタは0にセットされる。ステップS25ではまた、最後パケット型変数が順序付きにセットされる。プロセスは次いでステップS20に戻り、次に受領されるパケットを待つ。
【００９１】
ステップS21においてバイパス機能付き待ち行列が空でない（すなわち、順序付き待ち行列またはバイパス可能待ち行列のいずれかにすでに少なくとも一つのパケットがある）と判定される場合、ステップS26において、新たなパケットがバイパス可能パケットであるかどうかが判定される。新たなパケットがバイパス可能パケットであれば、ステップS27において直前のパケットのグループ・タグ（最後パケット・タグ変数から決定される）が新たに受領されたパケットに割り当てられる。ステップS28では、最後パケット型変数がバイパス可能にセットされる。ステップS29では、最後パケット・タグ変数が、ステップS27で新たなパケットに割り当てられたグループ・タグにセットされる。
【００９２】
ステップS26において、新たなパケットが順序付きパケットであると判定される場合、ステップS30において、最後パケット型変数が検査される。最後パケット型変数がバイパス可能にセットされている場合、ステップS31で直前のグループ・タグ（最後パケット・タグ変数から決定される）がインクリメントされ、その新たな値が新たなパケットに割り当てられる。あるいはまた、最後パケット型変数が順序付きにセットされている場合、ステップS32で、直前パケットのグループ・タグ（最後パケット・タグ変数から決定される）が新たなパケットに割り当てられる。ステップS33において、最後パケット型変数が順序付きにセットされ、プロセスはステップS29に進む。最後パケット・タグ変数がセットされた後、プロセスはステップS20に戻って次に受領されるパケットを待つ。
【００９３】
図２ないし図１０との関連で上記したバイパス機能付き待ち行列は、グループ・タグを1ビット数（つまり0か1）として実装する。しかしながら、1ビットのグループ・タグを使うのでは、バイパス機能付き待ち行列の順序付けの完全性（integrity）が制御RAM  ２内のエラーを受けやすい。簡単な実施例では、あるパケットのパケット記述子においてエラーが検出される場合、そのパケットは破棄される。しかしながら、1ビットのグループ・タグでは、これはパケット順序付けについて深刻な影響をもつことがありえ、パケットが送信のために間違った時点にスケジュールされ、上記の規則１ないし４の一つを破ることになりうる。
【００９４】
図１４を参照すると、この図は、1ビットのグループ番号で実装される図２ないし図１０に示される待ち行列と同様のバイパス機能付き待ち行列を示している。バイパス機能付き待ち行列の先頭にバイパス可能パケットのみを含むグループはないので、グループ・カウンタ９は0である。
【００９５】
順序付きパケットO0が送信されれば（図１２のステップS10）、順序付きパケットO2についてのパケット記述子が制御RAM内に読み込まれ、順序付き待ち行列についての待ち行列先頭ポインタQueue  1はパケットO2についての記述子をポイントするよう変更される（ステップS11）。制御RAMにエラーがなければ、制御RAMから読み込まれたパケットO2のグループ・タグ８および送信されたパケットO0のグループ・タグ８が比較される（ステップS12）。パケットO0からパケットO2へのグループ・タグ８内の変化が検出され、今やバイパス機能付き待ち行列の先頭にバイパス可能パケット（B1）のみを含む新しいグループがあるという事実を反映するために、グループ・カウンタ９が1だけインクリメントされる（ステップS13）。
【００９６】
しかしながら、パケットO2についてのパケット記述子を読もうと試みる際に制御RAMの読み取り動作が失敗すると、パケットO2は破棄されて、次の順序付きパケット（O6）の詳細が代わりに読み込まれる。パケットO6は、パケットO2とは異なるグループにあり、よって異なるグループ・タグ８をもつ。1ビットのグループ・タグについては、パケットO6についてのグループ・タグ８は送信されたパケットO0についてのグループ・タグ８と同じである。結果として、ステップS12において、グループ・タグ８の変化が検出されない。結果として、グループ・カウンタ９は更新されず、よって待ち行列順序が事実上変更される。結果として得られる待ち行列状態は図１５に示されるようになる。パケットO2は破棄されている。順序付きパケット待ち行列６の先頭のパケットO6はパケットB1と同じグループ・タグをもつので、事実上、グループを移ったように見え、四つのバイパス可能パケットを追い越して今ではパケットB1と同じグループ内にある。グループ・カウンタ９は、パケットO0が送信されたときに誤ってインクリメントされ損なったので、0のままであり、その結果、パケットB1はいかなる状況のもとでもパケットO6が送信されるまで送信され得なくなる。バイパス機能付き待ち行列の順序付けが望ましくない仕方で代わってしまったことは明らかである。
【００９７】
図１５のポジションから続けて順序付きパケットO6が送信された場合、待ち行列状態は図１６に示されるようになる。パケットO6が送信されるとき、ステップS12において、送信された順序付きパケットから次の順序付きパケットO8までにグループ・タグ８の変化があるかどうかを確認するために検査が行われる。パケットO6はグループ・タグ1をもつ。パケットO8はグループ・タグ0をもつ。結果として、ステップS13において、グループ・カウンタ９は、二つのグループ・タグ８の間の差によって更新され、図１６に示されるように、グループ・カウンタは今では1になる。これは明らかに間違っている。図１６はバイパス機能付き待ち行列の先頭におけるバイパス可能パケットのみを含む三つのグループがあることを示しており、グループ・カウンタは3となるべきである。
【００９８】
ここでバイパス可能パケットB1が送信される場合（十分なバイパス可能送信クレジットが利用可能であるとして）、順序付けは図１７に示されるように一層損なわれる。パケットB1から次のバイパス可能パケットB3にかけてグループ・タグの変化があるので、これがステップS6で検出され、ステップS7でグループ・カウンタ９はデクリメントされて0に戻る。したがって、それ以上のバイパス可能パケットは送信できず、順序付けパケットO8およびO9が事実上、バイパス機能付き待ち行列の先頭に昇進される。
【００９９】
このような損壊を防止する一つのオプションは、制御RAM  １２の記憶を、パケット記述子１３内のグループ・タグ１４を、たとえパケット記述子１３の残りの部分が壊れていたとしても、正しく読めることが保証できるような仕方で実装することである。そうすればグループ・タグ１４は正しく追跡でき、もとの順序付けが維持できる。実質的にあらゆる障害がタグ複製（すなわち、各グループ・タグを制御RAM  １２内に複数回記憶しておくこと）で訂正できる。そうすれば特定のグループ・タグのあらゆるインスタンスを読み、多数決方式を実装することができる。この実装では、グループ・タグのいくつかのインスタンスが壊れている場合、グループ・タグのインスタンスの過半数が正しく読まれる限り、正しいグループ・タグが決定できる。しかしながら、実際上、この可能なアプローチは100%信頼できるとあてにすることはできないので、損壊を防ぐある代替的なオプションは、グループ・タグを、nを1より大きいとして、nビット・カウンタに拡張することである。
【０１００】
グループ・タグを生成するためにnビット・カウンタを使うと、あるパケットから次のパケットにかけてのグループ・タグの変化は、制御RAMエラーのために2n−1個を超えるパケットが破棄されるのでない限り、常に検出される。2ビットのグループ・タグについては、順序付けが壊れるまでに３個までのパケットを安全に破棄できる。3ビットのタグについては、損壊なしに７個までのパケットが破棄できる。破棄されたパケットが同じグループ・タグを共有する場合、損壊なしに一層多くのパケットを破棄できる。値n＝2が、複雑さと誤り検出能力の間の受け容れ可能な妥協点である。
【０１０１】
図１８は、2ビットのグループ・タグをもつバイパス機能付き待ち行列の待ち行列状態を示している。パケットO0が送信される場合、パケットO3、O4、O6およびO10のすべてが制御RAMエラーのために失われるのでない限り、待ち行列先頭レジスタQueue  1に進められる次に読まれる順序付きパケット記述子について、グループ・タグの変化が検出される（ステップS12）。パケットO3、O4、O6およびO10のすべてが失われる場合にのみ、パケットO0とパケットO12の間のグループ・タグの変化が検出され損なう（いずれもグループ・タグ0をもつ）。これほど多くのパケットが失われることは、制御RAMの破滅的な故障なしでは比較的ありそうもない。そのような破滅的な故障はいずれにせよ修復できない可能性が高い。
【０１０２】
しかしながら、制御RAMエラーのためにパケットO3およびO4のみが破棄される必要があったとしても、順序付きパケットO6が順序付き待ち行列の先頭に進められ、待ち行列ポインタQueue  1によってポイントされる。ステップS12では、O0のグループ・タグ（0）とO6のグループ・タグ（2）の間の変化が検出され、ステップS13ではグループ・タグの差の絶対値（2）がグループ・カウンタに加えられ、図１９に示されるような正しい待ち行列状態につながるであろう。図１９は、（一つのパケットしか送信されなかったが）グループ・カウンタが今では2であることを示しており、待ち行列に入れられている最初の順序付きパケットの前にバイパス可能パケットのみを含む二つのパケット・グループがあることを正しく示している。
【実施例】
【０１０３】
本発明のあるさらなる実施形態によれば、三つ以上の異なるパケット型についての順序付け規則への準拠を保証することができるバイパス機能付き待ち行列が提供される。PCIエクスプレス（Peripheral  Component  Interconnect  Express［周辺コンポーネント相互接続エクスプレス］、PCIe）規格は三つの異なるパケット型を定義している：ポスト（posted）、完了（completion）および非ポスト（non-posted）パケットである。この三つのパケット型は異なるレベルの優先度をもつ。ポスト・パケットは完了パケットより高い優先度であり、完了パケットは非ポスト・パケットより高い優先度である。パケットの優先度のこの相違は、次の順序付け規則によって表現できる：
１．非ポスト・パケットは前に待ち行列に入れられたいかなるパケットも追い越してはならない。
２．完了パケットは前に待ち行列に入れられたいかなる完了パケットやポスト・パケットも追い越してはならないが、前に待ち行列に入れられた非ポスト・パケットは追い越してもよい。
３．ポスト・パケットは前に待ち行列に入れられたいかなるポスト・パケットも追い越してはならないが、前に待ち行列に入れられた完了パケットや非ポスト・パケットは追い越してもよい。
【０１０４】
PCIe規格に準拠するバイパス機能付き待ち行列は、本発明のある実施形態によれば、各型のパケットが制御RAM内の別個のパケット待ち行列に（追加的な待ち行列を受け入れるためのさらなるレジスタに記憶される第三の待ち行列先頭ポインタQueue  3とともに）記憶されることを保証することによって実装できる。各パケット型を別個の待ち行列に記憶することは、各パケットの、同じ型の他のすべてのパケットに関する順序付けが維持されることを保証する。
【０１０５】
上記の規則に基づく三つの待ち行列の間の相対的な順序付けは、三つの別個のグループ・タグを割り当て、各タグが関連付けられたグループ・カウンタをもつことによって維持される。各パケットは受信される際に二つのグループ・タグを割り当てられ、これらのタグは制御RAM内のパケット記述子内に記憶される。第一のタグは、ポスト・パケットと完了パケットの間の順序付けを維持するために使われる。第二のタグは、ポスト・パケットと非ポスト・パケットの間の順序付けを維持するために使われる。第三のタグは、完了パケットと非ポスト・パケットの間の順序付けを維持するために使われる。各パケットは、そのパケットのパケット型に関係する二つのタグとともに記憶される。各グループ・タグについて別個のグループ・カウンタも維持される。
【０１０６】
ここで図２０を参照すると、この図は、それぞれポスト・パケット、完了パケット、非ポスト・パケットを保持する三つの別個の待ち行列３０〜３２から形成されるバイパス機能付き待ち行列についての待ち行列状態を示している。図２０にはまた、三つのグループ・タグ３３、３５、３７および三つのグループ・カウンタ３４、３６、３８も示されている。上述したように、グループ・タグ３３、３５、３７のそれぞれとグループ・カウンタ３４、３６、３８のそれぞれは、三つのパケット待ち行列３０〜３２のうちの二つにのみ関連する。グループ・タグまたはグループ・カウンタの前のプレフィクスPCは、ポストおよび完了パケット型の両方に関連することを意味する。プレフィクスPNは、ポストおよび非ポスト・パケット型の両方に関連することを意味する。プレフィクスCNは完了および非ポスト・パケット型の両方に関連することを意味する。
【０１０７】
図２ないし図１０および図１４ないし図１９についてと同様、各パケットに付されている添え字は、パケットがネットワーク要素において受領されて待ち行列に入れられた順序を定義する。ポスト・パケットはPで表され、完了パケットはCで表され、非ポスト・パケットはNで表される。二つのパケット型しかないバイパス機能付き待ち行列の例についてと同様、パケットが送信されうるのは、上記三つの規則に従ってそのパケットが送信のために利用可能でありかつそのパケット型について十分な送信クレジットが利用可能である場合のみである。十分な送信クレジットが利用可能であるとすると、ポスト・パケットは、どの時点でも、ポスト待ち行列３０から送信のために取り出し可能である。十分な送信クレジットが利用可能であるとすると、完了待ち行列３１から送信のためにパケットが取り出し可能であるのは、PCグループ・カウンタ３４の0より大きな値によって示されるところにより、それ以前のポスト・パケットがない場合のみである。非ポスト待ち行列３２から送信のためにパケットが取り出し可能であるのは、PNグループ・カウンタ３６およびCNグループ・カウンタ３８の0より大きな値によって示されるところにより、それ以前のポスト・パケットや完了パケットがない場合のみである。
【０１０８】
図２０に示される待ち行列状態において、PCグループ・カウンタ３４およびPNグループ・カウンタ３８がいずれも0であるので、ポスト・パケットP0のみが送信のために利用可能である。パケットP0が送信される場合、ポスト待ち行列３０の先頭における新しいパケット（P4）は異なるPCグループ・タグ値３３をもつので、PCグループ・カウンタ３４はインクリメントされる。さらに、パケットP4は異なるPNグループ・タグ３５をもつので、PNグループ・カウンタ３６もインクリメントされる。CNグループ・カウンタ３８はパケットP0の送信によって影響されない。待ち行列状態は、今や図２１に示されるようになる。
【０１０９】
図２１を参照すると、PCグループ・カウンタは0より大きいので、完了待ち行列３１からのパケットの送信が考慮されることができる。しかしながら、CNグループ・カウンタ３８がまだ0なので、非ポスト待ち行列３２からは完了パケットC1より前には何も送信され得ない。完了パケットC1は送信できる。ポスト・パケットP4も送信できる（これは二つの完了パケットおよび一つの非ポスト・パケットを追い越すことになる）。
【０１１０】
完了パケットC1が送信されるとすると、待ち行列状態は図２２に示されるようになる。完了先頭パケット（つまり完了待ち行列３１の先頭にあるパケット）C3は同じPCグループ・タグ３３をもち、よってPCグループ・カウンタ３４は影響されない。パケットC3は異なるCNグループ・タグ３８をもち、よってCNグループ・カウンタ３８はインクリメントされる。PNグループ・カウンタ３６は影響されない。
【０１１１】
PNグループ・カウンタ３６およびCNグループ・カウンタ３８の両方が0より大きいので、非ポスト・パケットN2が今や送信のために利用可能である。完了先頭パケットC3も、PCグループ・カウンタ３４が0でなく、該パケットは先に待ち行列に入れられた非ポスト・パケットを追い越すことが許されているので（非ポスト送信クレジットが不十分であるとして）利用可能である。最後に、他のいかなる型のパケットを送信するにも不十分な送信クレジットしかない場合には、先頭ポスト・パケットP4が送信できる。
【０１１２】
非ポスト・パケットN2が送信される場合、待ち行列状態は図２３に示されるようになる。新しい非ポスト先頭パケットN5は異なるPNグループ・タグをもち、よってPNグループ・カウンタ３６はデクリメントされて0に戻る。パケットN5はまた、異なるCNグループ・タグ３７をもち、よってCNグループ・カウンタ３８がデクリメントされて0に戻る。PCグループ・カウンタ３４はこの送信によって影響されない。
【０１１３】
最後の完了パケットが送信されると、さらなる完了パケットは待ち行列に入れられていないので、PCグループ・カウンタはデクリメントされて0になる。最後の非ポスト・パケットが送信されると、さらなる非ポスト・パケットが待ち行列に入れられていないので、PNグループ・カウンタおよびCNグループ・カウンタはデクリメントされて0になる。
【０１１４】
ここで図２４を参照すると、これは、最後のパケットが送信された後の待ち行列状態を示している。三つのグループ・カウンタ３４、３６、３８のすべては0である。三つのグループ・タグ３３、３５、３７は、最後のパケットが送信されたときのその値に依存して任意の値にある（あるいはデフォルト値に再初期化されることもできる）。
【０１１５】
新たな非ポスト・パケットN14が空のバイパス機能付き待ち行列に加えられる場合、待ち行列状態は図２５に示されるようになる。パケットN14は、後刻加えられるいかなるポスト・パケットまたは完了パケットよりも先行しなければならない。よって、PNグループ・カウンタ３６およびCNグループ・カウンタ３８の両方が1にセットされる。
【０１１６】
今、新たな完了パケットC15が加えられる場合、待ち行列状態は図２５に示されるようになる。完了待ち行列３１または非ポスト待ち行列３２のいずれかに加えられた直前のパケットは非ポスト・パケットN14であったので、新しいCNグループ・タグ３７がパケットC15に割り当てられねばならない。パケットC15は、後刻加えられるいかなるポスト・パケットよりも先行しなければならない。よって、PCグループ・カウンタ３４は1にセットされる。
【０１１７】
新たな非ポスト・パケットN16が加えられる場合、待ち行列状態は図２７に示されるようになる。次いでポスト・パケットP17が受領され、待ち行列状態は図２８に示されるようになる。ポストまたは完了待ち行列３０、３１のいずれかに加えられた直前のパケットは完了パケットC15であったので、新しいPCグループ・タグ３３が割り当てられねばならない。また、ポストまたは非ポスト待ち行列３０、３２のいずれかに加えられた直前のパケットは非ポスト・パケットN16であったので、新しいPNグループ・タグ３３が割り当てられねばならない。
【０１１８】
当業者には、本発明に基づくバイパス機能付き待ち行列内のパケット型の数を四つ以上のパケット型に増やしてもよいことは明白であろう（グループ・タグおよびグループ・カウンタの増加した数のぶんのコストはかかるが）。さらに、本稿の教示から、付属の請求項の範囲から外れない本発明の修正および応用が当業者には明白となるであろう。
【図１】
2010539837.tif 000003
【図２】
2010539837.tif 000004
【図３】
2010539837.tif 000005
【図４】
2010539837.tif 000006
【図５】
2010539837.tif 000007
【図６】
2010539837.tif 000008
【図７】
2010539837.tif 000009
【図８】
2010539837.tif 000010
【図９】
2010539837.tif 000011
【図１０】
2010539837.tif 000012
【図１１】
2010539837.tif 000013
【図１２】
2010539837.tif 000014
【図１３】
2010539837.tif 000015
【図１４】
2010539837.tif 000016
【図１５】
2010539837.tif 000017
【図１６】
2010539837.tif 000018
【図１７】
2010539837.tif 000019
【図１８】
2010539837.tif 000020
【図１９】
2010539837.tif 000021
【図２０】
2010539837.tif 000022
【図２１】
2010539837.tif 000023
【図２２】
2010539837.tif 000024
【図２３】
2010539837.tif 000025
【図２４】
2010539837.tif 000026
【図２５】
2010539837.tif 000027
【図２６】
2010539837.tif 000028
【図２７】
2010539837.tif 000029
【図２８】
2010539837.tif 000030
【国際調査報告】
2010539837.tif 000031
2010539837.tif 000032
2010539837.tif 000033