(57)【要約】  本発明の実施形態は、キューバッファ管理の方法を提供する。本発明の一実施形態では、インターネットプロトコルデータは、データソース装置で生成される。生成されたデータは、1つまたは複数のネットワーク装置に伝えられ、1つまたは複数のネットワーク装置で受信される。生成されたデータの部分は、生成されたデータのデータフローの向上をもたらすために、指定された基準に基づいて、選択的に削除される。指定された基準は、前回のドロップからの時間、前回のドロップからのパケット数、パケットプロトコル、パケットサイズ、およびその組合せから成るグループから選択される。本発明の一実施形態では、生成されたデータは、フロー制御可能なインターフェイスを介して伝えられる。
2010528506.tif 000002
【特許請求の範囲】
【請求項１】
インターネットプロトコルデータを1つまたは複数のネットワーク装置で受信するステップと、
前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するステップと、
を含み、
前記インターネットプロトコルデータは、データソース装置で生成され、前記1つまたは複数のネットワーク装置に伝えられ、
前記指定された基準は、前回のドロップからの時間、前回のドロップからのパケット数、パケットプロトコル、パケットサイズ、およびその組合せから成るグループから選択されることを特徴とする方法。
【請求項２】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項1に記載の方法。
【請求項３】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項1に記載の方法。
【請求項４】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項1に記載の方法。
【請求項５】
フロー制御可能なインターフェイスを介して伝えられるインターネットプロトコルデータを、1つまたは複数のネットワーク装置で受信するステップと、
前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するステップと
を含み、
前記インターネットプロトコルデータは、データソース装置で生成され、前記1つまたは複数のネットワーク装置に伝えられることを特徴とする方法。
【請求項６】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項5に記載の方法。
【請求項７】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項5に記載の方法。
【請求項８】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項5に記載の方法。
【請求項９】
データソース装置に通信可能に結合されるネットワーク装置であって、前記データソース装置で生成されたインターネットプロトコルデータを受信し、前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するように構成されており、前記指定された基準が前回のドロップからの時間、前回のドロップからのパケット数、パケットプロトコル、パケットサイズ、およびその組合せから成るグループから選択されるネットワーク装置、
を含むことを特徴とする装置。
【請求項１０】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項9に記載の装置。
【請求項１１】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項9に記載の装置。
【請求項１２】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項9に記載の装置。
【請求項１３】
データソース装置に通信可能に結合されるネットワーク装置であって、前記データソース装置で生成され、フロー制御可能なインターフェイスを介して伝えられるインターネットプロトコルデータを受信し、前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するように構成されているネットワーク装置
を含むことを特徴とする装置。
【請求項１４】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項13に記載の装置。
【請求項１５】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項13に記載の装置。
【請求項１６】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項13に記載の装置。
【請求項１７】
実行可能命令を提供する機械可読媒体であって、プロセッサによって実行されると、前記プロセッサに、
インターネットプロトコルデータを1つまたは複数のネットワーク装置で受信するステップと、
前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて前記データの部分を選択的に削除するステップと、
を含み、
前記インターネットプロトコルデータは、データソース装置で生成され、前記1つまたは複数のネットワーク装置に伝えられ、
前記指定された基準は、前回のドロップからの時間、前回のドロップからのパケット数、パケットプロトコル、パケットサイズ、およびその組合せから成るグループから選択される方法、
を実行させることを特徴とする機械可読媒体。
【請求項１８】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項17に記載の機械可読媒体。
【請求項１９】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項17に記載の機械可読媒体。
【請求項２０】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項17に記載の機械可読媒体。
【請求項２１】
実行可能命令を提供する機械可読媒体であって、プロセッサによって実行されると、前記プロセッサに、
フロー制御可能なインターフェイスを介して伝えられるインターネットプロトコルデータを、1つまたは複数のネットワーク装置で受信するステップと、
前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するステップと
を含み、
前記インターネットプロトコルデータは、データソース装置で生成され、前記1つまたは複数のネットワーク装置に伝えられる方法、
を実行させることを特徴とする機械可読媒体。
【請求項２２】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項21に記載の機械可読媒体。
【請求項２３】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項21に記載の機械可読媒体。
【請求項２４】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項21に記載の機械可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、通信ネットワークに関し、より詳細には、本発明は、データ通信システムのキューバッファを制御するための方法およびシステムに関する。
【背景技術】
【０００２】
キューバッファ管理の従来の方法は、フロー制御可能なインターフェイス(FCI)を実装することを含む。ネットワーク装置がFCIを介してデータソースを提供するホストに接続されているとき、ネットワーク装置内のキューが指定されたレベルを超えると、これらの装置の間のデータフローは、しばしば停止される。FCIは、万一ネットワーク装置のキューがオーバーフローした場合、データ損失を防ぐために実装される。ネットワーク装置とホストとの間のデータフローが停止されると、ネットワーク層の上のフロー制御がトランスポート層によって制御されるため、ホストにおけるネットワーク層は、データをキューに入れることが要求される。トランスポート層(TCP、UDPなど)およびトランスポートパラメータ(例えばrwin)によって、ホストにおいて、過度のキューイングが行われることが多い。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
こうしたシステムには、過度のキューイングに関連する欠点がある。1つの欠点は、過度のキューイングは、データがリンクを通って、データソースからデータの宛先(例えばネットワーク装置)へ、そしてデータソースに戻るために必要な時間の増加をもたらすことである。この時間は、既知であり、チャネルの往復時間(RTT)である。RTTの増加は、キューに入れられたデータ量×ネットワーク装置の最大出力レートに等しい。
【０００４】
図1は、従来技術よるFCIを実装するシステムおよびその欠点を示す。TCPデータの場合、RTTの増加、およびスループットの低減の根本的原因は、アップリンクの受信ウィンドウサイズが遠端サーバによって非常に大きく設定されていることである。RTTの増加は、複数のTCPセッションが1つのストリームに多重化されるTCPプロトコルより下のアップリンクのデータパスにおける過度のキューイングによってもたらされる(UDPデータの場合、過度のキューイングは、UDPストリームデータレートがネットワーク装置の出力レートを超えるときは必ず起こる)。
【０００５】
TCPストリームでのスループットの低減は、一般のTCP  FCIの以下のデータ通信プロセスのために起こる。アプリケーションは、データが送出され得るより速くデータをネットワーク装置に送信するため、図1に示されるように、データは、DL確認応答と共にキューに入れられる必要がある。キューに入れられたデータは、RTTの増加をもたらし、これは、遠端データソース(図示せず)へのDL  TCPの確認応答の遅延をもたらす。タイムリーなTCPの確認応答の欠如によって、遠端データソースは、データ送信レートを低下させる。
【課題を解決するための手段】
【０００６】
本発明の実施形態は、キューバッファの管理のための方法を提供する。本発明の一実施形態では、インターネットプロトコルデータは、データソース装置で生成される。生成されたデータは、1つまたは複数のネットワーク装置に伝えられ、1つまたは複数のネットワーク装置で受信される。生成されたデータの部分は、生成されたデータのデータフローの向上をもたらすために、指定された基準に基づいて、選択的にドロップされる。指定された基準は、前回のドロップからの時間、前回のドロップからのパケット数、パケットプロトコル、パケットサイズ、およびその組合せから成るグループから選択される。本発明の一実施形態では、生成されたデータは、フロー制御可能なインターフェイスを介して伝えられる。
【０００７】
他の利点および実施形態は、詳細な説明において説明される。
【０００８】
本発明は、本発明の実施形態を説明するために使用される以下の説明および添付の図面を参照することによって最もよく理解され得る。
【図面の簡単な説明】
【０００９】
【図１】従来技術によるFCIを実装するシステムおよびその欠点を示す図である。
【図１Ａ】一定の輻輳閾値のシミュレーションを示す図である。
【図２】本発明の一実施形態によるデータ通信システムを示す図である。
【図２Ａ】一定の輻輳閾値のシミュレーション-可変の出力DRを示す図である。
【図３】本発明の一実施形態によるデータ通信システムのキューバッファの管理を実施するためのプロセスを示す図である。
【図３Ａ】パケット間の最短時間無しの一定の輻輳閾値のシミュレーションを示す図である。
【図４】本発明の一実施形態によるキューバッファの管理のための方法のプロセスフロー図である。
【図４Ａ】一定の最短時間間隔のシミュレーションを示す図である。
【図５】本発明の一実施形態によるデータを伝えるために使用され得るデジタル処理システムの機能ブロック図である。
【図５Ａ】可変の出力レートによる一定の最短時間間隔のシミュレーションを示す図である。
【図６Ａ】一定の最小パケット間隔のシミュレーションを示す図である。
【図７Ａ】動的な輻輳制御のシミュレーションを示す図である。
【図８Ａ】動的な最短時間間隔のシミュレーションを示す図である。
【図９Ａ】UDPレート<物理出力レートによる輻輳のシミュレーションを示す図である。
【図１０Ａ】UDP>物理出力レートによるシミュレーションを示す図である。
【図１１Ａ】動的な2段階最短時間間隔機構(Dynamic 2 Stage Minimum Time Interval Mechanism)によるシミュレーションを示す図である。
【図１２Ａ】可変の出力レートによるDTSMを使用したシミュレーションを示す図である。
【図１３Ａ】可変の出力レートによる、UDPトラフィック無しのDTSMを使用したシミュレーションを示す図である。
【発明を実施するための形態】
【００１０】
データフローを向上するために、指定された基準に基づいて、受信されたデータが選択的に削除されるキューバッファの管理のための方法およびシステム。システムがFCIを実装する本発明の様々な実施形態では、指定された基準は、キュー深度、フィルタ処理されたキュー深度、前回データがドロップされてからの時間、前回データがドロップされてから受信されたデータの量、およびパケットベースのデータ通信を実施するシステムの場合、パケットサイズ、およびパケットプロトコルのうちの1つまたは複数を様々な組合せで含み得る。フロー制御不可の環境内で実施される本発明の様々な実施形態では、指定された基準は、前回データがドロップされてからの時間、前回データがドロップされてから受信されたデータの量、およびパケットベースのデータ通信を実施するシステムの場合、パケットサイズ、およびパケットプロトコルのうちの1つまたは複数を様々な組合せで含み得る。
【００１１】
本発明の様々な実施形態の以下の詳細な説明は、例示にすぎず、決して限定的なものではないことを、当業者であれば理解されよう。本発明の他の実施形態は、本開示の恩恵を受ける当業者であれば、容易に連想されよう。これらの特定の詳細は本発明の実施形態の実施に必要ではない場合があることは、当業者には明らかであろう。別の例では、よく知られている要素および装置は、本発明を不明瞭にするのを回避するために、ブロック図の形で示されている。実施形態の以下の説明では、実質的に同じ部分は、同じ参照番号で示される。
【００１２】
わかりやすくするために、本明細書に記載された実装の特徴のすべてが示され、記載されているわけではない。当然、こうした任意の実際の実装の開発において、開発者の固有の目的を達成するために、多数の実装固有の装置を作る必要があり、これらの固有の目的は、実装ごと、および開発者ごとに異なることを理解されたい。さらに、こうした開発努力は、複雑で、時間がかかるが、それにも関わらず、本開示の恩恵を受ける当業者にとっては、日常的な技術の仕事であることを理解されたい。
【００１３】
本発明の一実施形態によれば、様々なタイプのオペレーティングシステム、コンピューティングプラットフォーム、コンピュータプログラム、および/または汎用機を使用して、構成要素、プロセスステップ、および/またはデータ構造を実施し得る。さらに、本明細書に開示された発明の概念の範囲および意図から逸脱することなく、汎用性がより少ない装置も使用し得ることを、当業者であれば理解されたい。
【００１４】
本発明の特定の実施形態が示され、説明されているが、本明細書に開示された発明の概念から逸脱することなく、上述したものよりさらに多くの変形が可能であることは、本開示の恩恵を受ける当業者には今や明らかであろう。さらに、発明の態様は、単一の開示された実施形態の特徴のすべてにあるわけではない。したがって、詳細な説明に続く特許請求の範囲は、本明細書によってこの詳細な説明に明示的に組み込まれ、各請求項は、それ自体本発明の個別の実施形態として成立する。
【００１５】
図2は、本発明の一実施形態によるデータ通信システムを示す。図2に示されるシステム200は、データ(例えばインターネットプロトコルデータ)を生成するデータソース装置205を含む。生成されたデータは、データを受信する、例えばネットワーク装置210として示される1つまたは複数のネットワーク装置に伝えられる。ネットワーク装置は、当分野で知られている有線または無線の通信手段を介してデータソース装置に通信可能に結合される。本発明の一実施形態では、ネットワーク装置210は、例えばUSB、PCMCIA、ExpressCard、PCI Express Mini、Serialなど、FCIを介してデータソース装置205に通信可能に結合されている。
【００１６】
ネットワーク装置210は、例えば基準のRTT、出力データレート、およびキュー深度として示される指定された基準に基づいて、受信されたデータの部分を削除する(例えば、パケットをドロップする)かどうかを決定するキュー管理機能215を含む。
【００１７】
キュー管理機能215は、図2に示されるように、それを介してデータをドロップまたは削除することの決定が行われるマルチプレクサ220に結合される。
【００１８】
図3は、本発明の一実施形態によるデータ通信システムのキューバッファの管理を実施するためのプロセスを示す。本発明の代替実施形態は、依然としてネットワーク装置の最大出力レートを維持しながら、過度のキューイング問題を解決するキュー管理方法を提供する。
【００１９】
図3に示されるプロセス300は、動作305で開始し、データが、データソース装置から、キューバッファ管理方式を実装するネットワーク装置に受信される。
【００２０】
動作310で、受信されたデータが、指定された基準に基づいて評価される。指定された基準は、データ通信システムの静的および動的パラメータを含み得る。動的パラメータは、例えば出力データレート、RTT、およびキュー深度に応じて決まり得る、輻輳閾値、最短時間間隔、最小ドロップパケットサイズ、およびデータプロトコルなどを含み得る。
【００２１】
本発明の一実施形態では、データ通信前、またはデータ通信中に、指定された基準のうちの1つまたは複数が動的に決定され得る。本発明の様々な代替実施形態では、指定された基準のうちの1つまたは複数は、データ通信前、またはデータ通信中に、動的に決定され得る対応する値(例えば、バイト、秒など)を有する。
【００２２】
動作315で、データ通信システムのデータフローの向上のために、評価に基づいて、データの部分が選択的に削除される。
【００２３】
図4は、本発明の一実施形態によるキューバッファの管理のための方法のプロセスフロー図を示す。
【００２４】
図4に示されるように、本発明の一実施形態では、キュー管理プロセスは、推定チャネルRTT、推定出力データレート、および現在のキュー深度の入力信号を使用する。このプロセスは、キューにおけるデータの一部(例えばパケット)をプロトコルの次の層に送信すべきかどうかを決定する。
【００２５】
本発明の一実施形態では、キュー管理方法は、輻輳の徴候検出時に、輻輳ウィンドウを低下させ、したがって飛行中のデータの量または確認応答されていないデータの量を低下させるTCP輻輳制御機構より駆動される。飛行中のデータが少なければ少ないほど、データソースは、データをゆっくり送信することができる。送信側TCPスタックに輻輳を示すために実施され得る方法が2つあり、それは、パケットのドロップ、またはTCPヘッダーにおける明示的な輻輳通知フラグの設定である。その極めて基本的な形では、キューマネージャは、キュー深度を監視する。キュー深度が何らかの閾値(すなわち、本書における輻輳閾値)を超えると、それは、パケットをドロップする、または明示的な輻輳通知をトリガすることによって、TCP輻輳制御機構をトリガする。キュー深度は、パケットをドロップする前に、キュー管理システムが検討する必要がある多くの要因のうちの1つにすぎない。
【００２６】
本発明の一実施形態では、キュー管理システムへの入力は、リアルタイムの制御信号および調整可能な定数の組である。以下は、可変のシステムデータレートおよびRTTについて、キュー管理システムの制御に使用される基本的な調整可能な定数のリストである。
【００２７】
図4に示されるように、本発明の一実施形態による方法は、以下を含む1つまたは複数の調整可能なパラメータを使用し得る。
【００２８】
輻輳閾値:平均キュー長および現在のキュー長がこの閾値を超えると、パケットがドロップされる。
【００２９】
最短時間間隔:前回パケットがドロップされてからこの時間量が経過しない限り、パケットのドロップは検討されない。
【００３０】
最小パケット間隔:前回パケットがドロップされてからこれだけのパケットが送信されない限り、パケットのドロップは検討されない。
【００３１】
最小ドロップパケットサイズ:この定数は、パケットのドロップが検討されるべき最小サイズである。
【００３２】
ドロップのために検討されるトランスポートプロトコル:これは、データの削除(ドロップ)を決定する際に検討されるトランスポートプロトコルのリストを含む。TCPやUDPなど、いくつかのプロトコルが検討され得る。ICMP、RTPなど他のプロトコルは、ドロップのために検討され得ない。
【００３３】
付録Aとして含まれているのは、これらの基準、およびキューバッファ管理を実施し、データフローを向上させるために、情報を削除するかどうかを決定するのに有用な他の検討事項を実施するための方法例である。
【００３４】
再度図2を参照すると、データソース装置205およびネットワーク装置210は、当業者には理解されるように、様々なデジタル処理システム(DPS)のうちの任意のものであり得る。図5は、本発明の一実施形態によるデータを伝えるために使用され得るデジタル処理システムの機能ブロック図を示す。図5に示される処理システム500の構成要素は、例であり、1つまたは複数の構成要素が省略または追加され得る。例えば、1つまたは複数の記憶装置が処理システム500に使用されてもよい。
【００３５】
図5を参照すると、処理システム500は、バス501を介してメインメモリ504、静的メモリ506、大容量記憶装置507に結合されている中央処理装置502および信号プロセッサ503を含む。本発明の一実施形態によれば、メインメモリ504は、選択的な通信アプリケーションを格納し、大容量記憶装置507は、上述したように、様々なデジタルコンテンツを格納し得る。また、処理システム500は、バス501を介して入出力(I/O)装置525および音声装置526に結合され得る。バス501は、情報および信号を伝えるための標準システムバスである。CPU502および信号プロセッサ503は、処理システム500のための処理ユニットである。CPU502または信号プロセッサ503、またはその両方は、処理システム500のための情報および/または信号を処理するために使用され得る。CPU502は、制御ユニット531、演算論理ユニット(ALU)532、いくつかのレジスタ533を含み、これらは、情報および信号を処理するために使用される。信号プロセッサ503も、CPU502と似た構成要素を含み得る。
【００３６】
メインメモリ504は、例えば、CPU502または信号プロセッサ503によって使用される情報または命令(プログラムコード)を格納するためのランダムアクセスメモリ(RAM)または何らかの他の動的記憶装置であり得る。メインメモリ504は、CPU502または信号プロセッサ503による命令の実行中、一時変数または他の中間情報を格納し得る。静的メモリ506は、例えば、これもまたCPU502または信号プロセッサ503によって使用され得る情報または命令を格納するための読み取り専用メモリ(ROM)および/または他の静的記憶装置であり得る。大容量記憶装置507は、例えば、処理システム500のための情報または命令を格納するためのハードディスクドライブまたは光ディスクドライブであり得る。
【００３７】
[一般事項]
本発明の実施形態は、データ通信システムにおけるキュー管理を実施するための方法およびシステムを提供する。本発明の一実施形態では、インターネットプロトコルデータは、データソース装置で生成される。生成されたデータは、1つまたは複数のネットワーク装置に伝えられ、1つまたは複数のネットワーク装置で受信される。生成されたデータの部分は、生成されたデータのデータフローの向上をもたらすために、指定された基準に基づいて、選択的に削除される。本発明の一実施形態では、生成されたデータは、フロー制御可能なインターフェイスを介して伝えられる。
【００３８】
本発明の代替実施形態は、依然としてネットワーク装置の最大出力レートを維持しながら、過度のキューイング問題を解決するキュー管理方法を提供する。
【００３９】
本発明の実施形態は、例えばデータを伝える、バッファに入れる、処理するなど、様々な操作を含む。様々な実施形態では、記載した1つまたは複数の操作は、追加または削除され得る。例えば、ネットワーク装置が推定RTTおよび推定出力データレートを取得するために使用し得る代替の方法がいくつかある。RTTは、送信されたデータの確認応答にかかる時間を調べることによって測定され得る。データがネットワーク装置に入るときに暗号化されていると、このように計算されたRTTは、可能ではない。あるいは、ネットワーク装置が既知の静的IPアドレスまたはキューにあるIPアドレス群のいずれかへの低レートのpingを生成することができる場合、RTTを推定することが可能である。また、固定値の最悪の場合のRTTまたは一般のRTTの推定は、物理層のチャネル状態に基づいて行われ得る。出力データレートは、データがキューを出るレートを測定することによって計算され得る、かつ/または物理層チャネルへのアクセス許可によって決定され得る。
【００４０】
本発明の操作は、ハードウェア構成要素によって実行する、あるいは命令でプログラムされた汎用または専用のプロセッサまたは論理回路に操作を実行させるために使用され得る機械実行可能命令に組み込むことが可能である。あるいは、操作は、ハードウェアおよびソフトウェアの組合せによって実行され得る。本発明の実施形態は、本発明よるプロセスを実行するために、コンピュータ(または他の電子装置)をプログラムするために使用され得る命令を格納した機械可読媒体を含み得るコンピュータプログラム製品として提供され得る。機械可読媒体は、それだけには限定されないが、光ディスク、CD-ROM、および光磁気ディスク、ROM、RAM、EPROM、EEPROM、磁気または光カード、フラッシュメモリ、または電子命令を格納するのに適した他のタイプのメディア/機械可読媒体を含み得る。さらに、本発明は、コンピュータプログラム製品としてダウンロードすることも可能であり、この場合、プログラムは、搬送波または他の伝搬媒体に組み込まれたデータ信号によって、通信セル(例えばモデムやネットワーク接続)を介してリモートコンピュータから要求側コンピュータに転送され得る。
【００４１】
さらに、様々な実施形態を特定の文脈で記載しているが、本発明の実施形態は、複数のデータ標準を使用する様々な信号チャネルまたはマルチチャネルデータ転送システムに適用可能である。
【００４２】
本発明は、いくつかの実施形態に関して記載されているが、本発明は、記載した実施形態に限定されるのではなく、添付の特許請求の範囲の意図および範囲内で修正および変更を加えて実施することが可能であることを、当業者であれば理解されたい。したがって、この説明は、限定ではなく、例示として見なされるものとする。
【００４３】
「付録A」
【００４４】
[調整可能なパラメータ]
本発明の一実施形態では、キュー管理システムへの入力は、リアルタイムの制御信号および調整可能な定数の組である。以下は、可変のシステムデータレートおよびRTTについて、キュー管理システムの制御に使用される基本的な調整可能な定数のリストである。
・輻輳閾値:
平均キュー長および現在のキュー長がこの閾値を超えると、パケットがドロップされる。
・最短時間間隔:
前回パケットがドロップされてからこの時間量が経過しない限り、パケットのドロップは検討されない。
・最小パケット間隔:
前回パケットがドロップされてからこれだけのパケットが送信されない限り、パケットのドロップは検討されない。
・最小ドロップパケットサイズ:
この定数は、パケットのドロップが検討されるべき最小サイズである。
・ドロップのために検討されるトランスポートプロトコル:
これは、TCPやUDPなど、ドロップのために検討されるトランスポートプロトコルのリストを含む。ICMP、RTPなど他のプロトコルは、ドロップのために検討され得ない。
【００４５】
[ピークロードの検討]
任意選択で、キュー管理システムは、ピークの到着バーストによるパケットのドロップを防ぐための機構を含むべきである。IPデータトラフィックのバースト性のために、バーストが大きいトラフィックがキューに送信されることは一般的である。本発明は、トラフィックの任意のバーストによるパケットのドロップを回避すべきである。輻輳閾値がキュー長の瞬間測定およびフィルタ処理された(または平均または平滑化された)バージョンのキュー長の両方と比較される機構が実施されることが推奨される。
【００４６】
ピークロードにおけるパケットのドロップを回避するために使用され得る別の機構は、パケットのドロップ前のある期間の間、キュー長がCngThを超えることを必要とする。この機構の欠点は、性能を低下させる過度のキューイングへの作用の遅延が常に存在することである。
【００４７】
[制御パケットの検討]
確認応答または他の制御パケットは、TCPスタックにおいて輻輳制御アルゴリズムをトリガしないため、これらのドロップは、回避されるべきである。パケットを構文解析してパケットのタイプを決定することを使用して、制御パケットのドロップを無くすことが可能である。パケットは、暗号化された場合、構文解析することができない。この場合、パケットのサイズを使用して、パケットが確認応答であるか、他の小さい制御型パケット(ICMPも小さい傾向にある)であるかを決定することが可能である。理想的には、最大セグメントサイズに近いパケットのドロップのみが検討されるべきである。提示されたキュー管理システムにおける最小ドロップパケットサイズの定数を使用して、パケットのドロップが検討されるために必要な最小サイズを設定する。
【００４８】
本書に示したすべてのシミュレーション結果は、最小ドロップパケットサイズ=1200バイトと設定する。
【００４９】
[先頭対末尾のドロッピングの検討]
トリガに対するタイムリーなTCPの応答を助けるために、ドロップすべきパケットは、キューの前方、すなわちキューの先頭(ネットワーク装置から送出されようとしているパケット)からドロップされるべきである。キューの前方からパケットをドロップすることで、輻輳機構(TcpMaxDupAcks=2)を開始するために選択的ACK(SACK)をトリガするのに十分なデータがその後あることを保証しやすくなり、そうでない場合、TCPスタックは、パケットにおいてタイムアウトしなければならなくなり、これは、出力性能の低下をもたらすことになる。これを考えると、キューおよびキュー管理がMACまたは物理層にできるだけ近いことが最適である。キューの先頭からのドロップが最適であるが、キューのどこでドロップしてもよい。
【００５０】
本書に示されるすべてのシミュレーション結果は、先頭ドロッピング機構(head dropping mechanism)を使用する。
【００５１】
[静的なキュー管理の方法]
本セクションは、輻輳閾値、最短時間間隔、最小パケット間隔の制御信号に静的信号を使用するキュー管理システムについて説明する。したがって、図4Aに示される関数CongThFunc、MinTimeIntFunc、およびMinPacketIntFuncは、使用されない。動的なキュー管理システムについては、後述する。
【００５２】
[搬送閾値信号]
輻輳閾値は、パケットをいつドロップするかを決定するために使用される多くの制御信号のうちの1つである。他のパケットのドロップ条件が満たされたと仮定すると、上記のフロー図は、瞬間のキュー長およびフィルタ処理された(平滑化された)キュー長が輻輳閾値を超えると、パケットがドロップされることを示す。
【００５３】
輻輳閾値は、ある意味では、TCP輻輳ウィンドウ(cwin)を設定している。TCP輻輳ウィンドウが増大することができる最大値は、データを受信しているTCPスタックによって設定される受信ウィンドウ(rwin)によって設定される(RFC2581参照)。TCPスループットを最大にし、キューイングを最小にするために、rwinは、遅延帯域幅積(RTT*出力データレート)に設定されるべきである。同様に、キュー管理システムにおいて、輻輳閾値は、最適には、おおよそ遅延帯域幅積(DBP)に設定されるべきである。この閾値が設定されると、TCP輻輳ウィンドウは、DBPの2倍からDBPの1倍までの間で変化する。DBPに設定された輻輳閾値は、最大出力データレートが得られ、最小キューイングが起こる最適の時点である。
【００５４】
図1Aは、ネットワーク装置の出力レートが16kB/sに設定されており、チャネルRTTが0.4秒のキュー管理システムのシミュレーション結果を示す。輻輳閾値は、DBP(16*0.4=6.4kB)に設定される。キュー管理システムへの入力は、無限のデータソースを有する、したがって常にTCPスタックの範囲内で最大許容レートで送信しようと試みる単一のTCPデータストリームである。
【００５５】
シミュレーションパラメータ:
輻輳制御アルゴリズムパラメータ
6400  MAX_CngTh  最大輻輳閾値。
6400  MIN_CngTh  最小輻輳閾値
1200  DropSizeTh-ドロップサイズ閾値(バイト単位)。ドロップするパケットの最小サイズ。範囲300〜1500バイト。
0    MinPacketInterval-ドロップ間のパケットの最低数
1.3  MinDropInterval(秒)  パケットのドロップ間の最小時間量
物理層
16    出力データレート(KB/S)
【００５６】
図1Aから、TCPスロースタート機構が起こり、次いでTCP輻輳機構が引き継ぐことがわかる。TCP輻輳ウィンドウは、上述したように変化するように示される。出力データレートは、最大物理出力データレートに等しい。キューサイズは、〜6400バイトからゼロまでの間で変化し、これは、データの不足が起こることなく可能な最も低いキューサイズである。
【００５７】
輻輳閾値設定の検討:
輻輳閾値の設定が大きすぎる(DBPを超える)場合、過度のキューイングがもたらされる。輻輳閾値の設定が小さすぎる(DBP未満)場合、キューの出力データレートは、低下することになる。図2Aにおけるシミュレーション結果は、これらの影響を示す。同じキュー管理システムを図1Aに示すが、この場合、物理的な出力データレートを時間によって変化させることによって、異なるDBPを作り出す。
【００５８】
シミュレーションパラメータ:
輻輳制御アルゴリズムパラメータ
6400  CngTh  最大輻輳閾値
1200  DropSizeTh-ドロップサイズ閾値(バイト単位)。ドロップするパケットの最小サイズ。範囲300〜1500バイト。
0    MinPacketInterval-ドロップ間のパケットの最低数
1.3   MinDropInterval(秒)  パケットのドロップ間の最小時間量
出力データレート
16    開始レート(バイト/秒)
25    出力レートを変更する時間(秒)
8    変更レート(バイト/秒)
45    出力レートを変更する時間(秒)
32    変更レート(バイト/秒)
【００５９】
出力データレートが8kB/sに等しい期間の間、出力データレートは、8kB/sに等しいが、必要とするより多くのキューイングがある。出力データレートが32kB/sに等しい期間の間、キューが空のとき、出力データレートはドロップし、したがって32kB/s未満である。
【００６０】
[最短時間間隔]
最短時間間隔は、パケットをいつドロップするかを決定するために使用される多くの制御信号のうちの別の1つである。他のすべてのパケットのドロップ条件が満たされたと仮定すると、上記のフロー図は、前回のドロップからの時間が最短時間間隔より大きいときのみ、パケットがドロップされることを示す。最短時間間隔は、2つの目的を有し得る。第1は、別のパケットがドロップされる前にTCPスタックがパケットのドロップに反応するある時間を提供することである。第2の目的は、輻輳閾値の目的に似ており、パケットをドロップするために適した時間を設定することである。
【００６１】
最短時間間隔は、複数のパケットのドロップを防ぐために使用されるときだけ、TCPがパケットのドロップに反応するのにかかる時間に設定されるべきである。これは、結局、RTTの2倍+再試行がキューをトラバースするのにかかる時間長(この詳細は、以下のセクションで導出される)よりわずかに大きくなる。図1Aに示されるシミュレーションのパラメータを使用して、最短時間間隔の時間が以下で計算される。
【００６２】
2*0.4(RTT)+6400(ドロップが起こるときのQサイズ)/16000(出力レート)+0.1=1.3秒
【００６３】
この信号の使用は、重要であり、そうでない場合、キュー管理システムは、1つより多くのパケットをドロップする。図3Aは、一定の輻輳閾値による同じキュー管理システムを示すが、この場合、最短時間間隔は、ゼロに設定されている。
【００６４】
シミュレーションパラメータ:
輻輳制御アルゴリズムパラメータ
6400  CngTh  最大輻輳閾値。
1200  DropSizeTh-ドロップするパケットの最小サイズ。範囲300〜1500バイト。
0    MinPacketInterval-ドロップ間のパケットの最低数
0    MinDropInterval(秒)  パケットのドロップ間の最小時間量
物理層
16    出力データレート(KB/S)
【００６５】
このシミュレーションの出力は、複数のパケットがドロップされ、したがって、輻輳ウィンドウを思い切って低下させることによってTCPスタックが反応することを示す。次いで、これによってテータの不足が起こり、出力データレートが低下する。
【００６６】
第2の目的は、主に最短時間間隔に依存して、キューレベルを制御することである。この場合、輻輳閾値を、ほぼ任意の量に設定することが可能である。最適な最短時間間隔の計算は、最適な輻輳閾値計算よりわずかに複雑になる。
【００６７】
以下の変数は、最適な最短時間間隔を決定するために使用される式を導出するために使用される。
MaxQ=キューがDBP=RTT*DRになる最適な最大値
DR=出力データDR
Cwnd=輻輳ウィンドウ
RTT=往復時間
IPSegSize=IPパケットのサイズ
TCPSegSize=TCPパケットのサイズ
AcksPerSec=1秒当たり受信される確認応答
TimeToReduceCwnd=TCPスタックがドロップされたパケットのCwndの値を半分にするのにかかる時間
TimeToGrowQueue=キューをMaxQから増大させるのにかかる時間
TimeToGrowCWnd=TCPスタックがCWndをMaxQから2*MaxQに増大させるためにかかる時間
【００６８】
最適には、最短時間間隔は、キューがMaxQを満たすのにかかる時間+TCPスタックがパケットのドロップに反応する時間に等しい。
【００６９】
最短時間間隔=TimeToGrowQueue+TimeReduceCwnd
【００７０】
キューをMaxQまで増大させる時間は、TCPスタックが輻輳ウィンドウをMaxQから2*MaxQに増大させるのにかかる時間に等しく、したがって以下の通りである。
【００７１】
最短時間間隔=TimeToGrowCWnd+TimeReduceCwnd
【００７２】
TimeReduceCwndの計算:
TCPスタックがドロップされたパケットのCwndの値を半分にするのにかかる時間は、再試行からのackが受信されるのにかかる時間である。この時間は、以下に分けることが可能である。
【００７３】
SACKが受信されるのにかかる時間=RTT
再送信されたパケットが送信されるのにかかる時間=キューイング時間=MaxQ/DR
再送信されたパケットのAckが受信されるのにかかる時間=RTT
【００７４】
したがって、以下の通りである。
TimeReduceCwnd=RTT+MaxQ/DR+RTT=2*RTT+MaxQ/DR
MaxQ=DR*RTTを代入すると、
TimeReduceCwnd=2*RTT+DR*RTT/DR=3*RTT
【００７５】
TimeToGrowCWndの計算:
CwndをMaxQサイズから2*MaxQサイズに増大させるのにかかる時間量は、以下の通りである。
TimeToGrowCWnd=MaxQ/CwndGrowthRate
【００７６】
輻輳ウィンドウが増大するレートは、ackが受信されるときはいつでも、TCPSegSize^2/Cwndバイトに等しい。
CwndGrowthRate=(TCP SegSize^2/Cwnd)*AcksPerSec
AcksPerSec=DR/IPSegSize
【００７７】
上記の式は、Cwndが定数ではないという事実によって複雑になる。この式を簡単にするために、1.7*MaxQに等しい平均CWndを使用する。これをCwndに代入すると、以下の通りである。
CwndGrowthRate=TCPSegSize^2/(1.7*MaxQ)*DR/IPSegSize
簡略化すると、以下の通りである。
【００７８】
【数１】
2010528506.tif 000003
【００７９】
最短時間間隔の計算:
CwndGrowthRateおよびTimeReduceCwndに代入すると、以下の通りである。
【００８０】
【数２】
2010528506.tif 000004
【００８１】
MaxQ=DR*RTTを代入し、簡略化すると、以下の通りである。
【００８２】
【数３】
2010528506.tif 000005
【００８３】
以下の値を使用すると、
DR=16000バイト/sec
RTT=0.4秒
IPSegSize=1500
TCPSegSize=1450
最短時間間隔=1.7*16000*0.4y2*1500/(1450y2)+3*0.4=4.3秒となる。
【００８４】
一定の信号、最短時間間隔を主なドロップ基準として使用して、キュー管理システムがどのように働くかを示すために、シミュレーションを、パケット間の最短時間が4.3秒に設定された図4Aにおける結果として得られたシミュレーション出力で動作させた。
【００８５】
[シミュレーションパラメータ]
輻輳制御アルゴリズムパラメータ
3000  CngTh  最大輻輳閾値
4.3   MinDropInterval(秒)。パケットのドロップ間の最小時間量
物理層
16    出力データレート(KB/S)
【００８６】
シミュレーションは、輻輳閾値がわずか3000バイトに設定されている場合でさえ、ドロッピングは、4.3秒に設定された最短時間間隔によって限定されているため、キュー管理は、最適である(依然として使用可能なすべての出力データレートを使用しながらも、キューイングが最低)ことを示している。
【００８７】
静的な輻輳閾値を使用することと同様に、一定の最短時間間隔を使用することは、最適値に設定されていないとき、過度のキューイングを作り出す、または使用可能な全出力レートを使用しない。この影響を示すために、出力レートが16kB/sec、8kB/sec、および32kB/secと変わるシミュレーションが実行された。図5Aは、このシミュレーションの結果を示す。
【００８８】
シミュレーションパラメータ:
輻輳制御アルゴリズムパラメータ
3000  CngTh  最大輻輳閾値。
0    MinPacketInterval-ドロップ間のパケットの最低数
4.3   MinDropInterval(秒)  パケットのドロップ間の最小時間量
出力データレート
16    開始レート(KB/秒)
25    出力レートを変更する時間(秒)
8    変更レート(KB/秒)
45    出力レートを変更する時間(秒)
32    変更レート(KB/秒)
【００８９】
これらの結果は、静的な輻輳閾値が使用されるキュー管理システムに似ている。物理出力レートが8kB/sに等しい期間の間、キュー平均出力データレートは、8kB/sに等しいが、必要とするより多くのキューイングがある。物理出力レートが32kB/sに等しい期間の間、キューが空のとき、キュー平均出力レートはドロップし、したがって32kB/s未満である。
【００９０】
[最小パケット間隔]
最小パケット間隔は、パケットをいつドロップするかを決定するために使用される多くの制御信号のうちの別の1つである。他のすべてのパケットのドロップ条件が満たされたと仮定すると、上記のフロー図は、前回のドロップからのパケット数が最小パケット間隔より大きいときのみ、パケットがドロップされることを示す。この信号の使用は、最短時間間隔のものと同じである。これは、別のものをドロップするまで、TCPスタックがパケットのドロップに反応するのを待つために使用する、またはシステムの主な制御として使用することが可能である。一般に、キュー管理システムは、これらの機構の両方をサポートする必要はなく、実装の容易さに基づいて、どちらかを優先して選択することになる。最適な最小パケット間隔は、以下のように計算することが可能である。
最小パケット間隔=(パケット/秒)*最短時間間隔
最小パケット間隔=(DR/IPPacketSize)*最短時間間隔
【００９１】
図1Aに示されているシミュレーション結果からのシミュレーションパラメータを使用して、結果として得られた最小パケット間隔は、以下の通りである。
最小パケット間隔=(16000/1500)*4.3=46パケット
【００９２】
46に等しい固定値を使用して、シミュレーションを実行し、結果を図6Aに示した。
【００９３】
シミュレーションパラメータ:
輻輳制御アルゴリズムパラメータ
3000  CngTh  最大輻輳閾値。
46    MinPacketInterval-ドロップ間のパケットの最低数
0    MinDropInterval(秒)  パケットのドロップ間の最小時間量
物理層
16    出力データレート(KB/秒)
【００９４】
上記のシミュレーション結果は、輻輳閾値がわずか3000バイトに設定されている場合でさえ、ドロッピングは、46個のパケットに設定された最小パケット間隔によって限定されているため、キュー管理は、最適である(依然として使用可能なすべての出力データレートを使用しながら、キューイングが最低)ことを示している。
【００９５】
[複数のTCPストリームの検討]
本書で示されているシミュレーションはすべて、たった1つのTCPストリームについてのものであるが、キュー管理アルゴリズムはすべて、1つを超える並行TCPストリームで入ってくるデータストリームを適切にサポートするように調整することが可能である。
【００９６】
輻輳閾値信号が主なドロッピング基準として使用されると、アルゴリズムは、入力として複数のTCPストリームで十分合理的に動作する。これは、最も高いcwndを有するストリームが最も多くのデータを送信しており、最も多くのデータをキューに有しているため、システムが確率的にそこからパケットをドロップするので確かなことである。アルゴリズムが低レートのTCPストリームからパケットを不適切にドロップした場合、何らかの短期のキュー深度ピーキングがあり得るが、長期的には、これは均一になる。
【００９７】
最短時間間隔または最小パケット間隔が主なドロッピング基準として使用されると、アルゴリズムを調整する必要がある。最適なサイズのキュー(DR*RTT)を維持するために、ドロッピングのレートは、アクティブに送信するTCPストリームに比例する必要がある。したがって、最短時間間隔または最小パケット間隔は、アクティブに送信するTCPストリームの数によって調整される必要がある。アクティブなTCPストリームの数は、キューにおけるパケットのIPおよびTCPヘッダーを調べることによって容易に計算することが可能である。調整された最短時間間隔または最小パケット間隔により、このアルゴリズムは、アルゴリズムが低レートのTCPストリームからパケットを不適切にドロップした場合に何らかの短期のキュー深度ピーキングが起こり得る輻輳閾値信号に基づいたアルゴリズムと同様に動作する。
【００９８】
[プロトコル依存のドロッピング]
キュー管理システムが何らかのタイプの上位層のプロトコルのみをドロッピングのために検討することが望ましい場合がある。SIP、RTSP、RSPP、RTCPなど上位層の制御プロトコルは、ドロップされないことが望ましい候補のようである。というのは、それらは、トラフィックの大幅なスローダウンはもたらさず、エンドユーザ体験の大幅な低下をもたらし得るからである。すべてのUDPトラフィックもこの「非ドロップリスト」にあり得る。というのは、UDPトラフィックがTCPのように輻輳制御アルゴリズムによって応答することは、まずないからである。UDPレートが出力データレートより大きい場合、UDPパケットを除外することに関する問題が起こる。この場合、UDPパケットをドロップする必要がある。このケースを適切に処理するために、第2の組の閾値をアルゴリズム(UDP輻輳閾値)に追加することが可能であり、この閾値を超えると、TCPパケットよりもUDPパケットの方がドロップの対象となる。
【００９９】
[(VPN)暗号化の前の処理]
本書で提示される概念のいくつかは、サイズ、プロトコル、ポート番号など、何らかのキー属性を決定するために、キューマネージャがパケットを構文解析またはトラバースすることを必要とする。最適な性能をもたらすために、キューマネージャは、物理層のできるだけ近くに存在する必要がある(「先頭対末尾のドロッピング」セクション参照)。この位置にキューマネージャを配置することに関する問題は、VPNまたは他の暗号化が使用される場合、キューマネージャに到達すると、すべての情報が暗号化され、したがって、これらのキー属性を抽出することができないということである。
【０１００】
この問題の解決策は、VPNの前、しかしネットワーク層の後に存在する調整エンティティを追加することである。Microsoft Vista OSでは、これらのタイプのドライバは、フィルタドライバと呼ばれる。次いで、フィルタドライバは、キューマネージャがドロップを検討すべきパケットをマークすることになる。パケットのマーキングの方法は、何らかの帯域外シグナリングを介して、またはVPNまたは他の暗号化が暗号化しないパケットのフィールドのうちの1つを変更することによるものとすることができる。この機構は、本書の範囲外である。
【０１０１】
[動的なキュー管理システム]
ここまで、本書および提示したシミュレーション結果は、単に静的な方法での制御信号の使用を検討してきた。輻輳閾値など、重要なキュー管理制御信号を計算するためのランタイム関数の使用は、キュー管理システムが、物理層における変化および入ってくるトラフィックストリームに対する変更に適応するのを助ける。物理層の変化は、データレートおよび/またはRTTの変化を含み得る。入ってくるトラフィックストリームの変化は、入ってくるトラフィックレートおよび/またはプロトコルの組合せ(TCP対UDP他)を含み得る。輻輳閾値、最短時間間隔、および最小パケット間隔の制御信号を動的に計算するために使用され得る3つの関数(CongThFunc、MinTimeIntFunc、およびMinPacketIntFunc)が列挙されている。これらの関数の使用は任意選択である。簡潔にするために、またはシステムにおいて変化がほとんど予想されない場合、制御信号を、静的となるように選択することが可能である。キュー管理システムが適応することを期待された場合、上記に列挙された動的な制御信号関数のうちの1つまたは複数、またはすべてが使用されるべきである。キュー管理方法は、これらの関数のうちの全3つを使用することができるが、他の信号が固定された場合、これらのうちのいくつかのみを使用する可能性がある。以下のセクションでは、これらの関数を実施するための一般的な指針をいくつか説明する。
【０１０２】
[CongThFuncの説明]
上述したように、TCPスループットを最大にし、キューイングを最低限に抑えるために、輻輳閾値は、常にDBPに設定すべきである。多くのシステムでは、出力データレート、およびより小さい範囲では、RTTは、かなり変わり得るため、RTTの推定および出力データレートに基づく輻輳閾値の動的計算を使用することが有利である。
【０１０３】
キューからのデータのフローを測定する、またはチャネルの許可または信号状態など何らかの物理層情報を使用するなど、出力データレートを推定するために使用することが可能な機構がいくつかある。出力データレートの推定は、単に、物理的に接続された技術(GPRS、EDGE、またはWCDMA、1x、Ev/DO revOまたはrevA)に基づくことも可能である。どの方法が使用される場合でも、出力データレートの推定は、物理層の急速な変化が輻輳閾値への劇的な変更をもたらさないように、平滑化されるべきである。
【０１０４】
チャネルのRTTを推定するために使用することが可能な機構もいくつかある。TCPデータが送信された場合、遠端受信機が送信されたデータを確認応答するのにかかる時間として、RTTを計算することは、非常に簡単である。VPNが使用される場合、この測定は、暗号化層の上で行われる必要がある。RTTを推定するための別の方法は、Pingなど小さいパケットを既知のサーバに送信することである。この方法の欠点は、何らかのオーバーヘッドを作り出すこと、およびパケットが送信されているのと同じ場所までのRTTを測定しないことである。
【０１０５】
以下のシミュレーション結果は、輻輳閾値がDBP=RTT*出力データレートに動的に設定されるキュー管理システムのものである。他のすべての制御信号は、静的である。出力データレートは、データがキューを出るレートによって推定される。次いで、出力データレートは、単極IIR移動平均フィルタ(single pole IIR moving average filter)を使用してフィルタ処理される。このシミュレーションでは、RTTは、推定されるのではなく、何らかの値(EstRTT)に固定される。このシミュレーションでは、実際のRTTは0.4秒であるが、EstRTTは、0.4375秒に設定される。実際の物理データレートは、16kB/sから8kB/s、さらに32kB/sに変わる。キューに入ってくるデータは、単一のTCPストリームである。図7Aは、シミュレーションの結果を示す。
【０１０６】
シミュレーションパラメータ:
輻輳制御アルゴリズムパラメータ
3000    Start_CngTh  開始輻輳閾値
2      MinDropInterval(秒)  パケットのドロップ間の最小時間量
0.4375  EstRTT-CngThを計算するために使用される推定RTT=AveULDR*CongCtrlRTT
出力データレート
16      開始レート(KB/秒)
25      出力レートを変更する時間(秒)
8      変更レート(KB/秒)
45      出力レートを変更する時間(秒)
32      変更レート(KB/秒)
【０１０７】
上記の結果からわかるように、実際の物理データレートが16kB/sから8kB/s、さらに32kB/sに変わる場合でも、キューの出力データレートは、常に、物理データレートと等しい傾向にあり、任意のデータレートでの過度のキューイングはない。
【０１０８】
[MinTimeIntFuncの説明]
上述したように、キューサイズを制御するために、制御信号、最短時間間隔が主な信号として使用された場合、最短時間間隔は、次のように設定すべきである。
【０１０９】
【数４】
2010528506.tif 000006
【０１１０】
DR=出力データレート
【０１１１】
動的な輻輳閾値と同様に、最短時間間隔は、RTTの推定および物理出力データレートに基づいて動的に計算することも可能である。上記の計算は、複雑に見えるが、IPSegSizeおよびTCPSeqSizeが一定であることが多いので、次の通り簡略化される。
最短時間間隔=K*DR*RTT^2_+3*RT
式中、
K〜=1.7*IPSegSize/TCPSegSize^2
【０１１２】
RTTおよび出力データレートを推定するために、上述した同じ方法を使用することが可能である。
【０１１３】
以下のシミュレーション結果は、以下によって最短時間間隔が動的に計算されるキュー管理システムのものである。
最短時間間隔=K*DR*RTT^2_+3*RT
【０１１４】
他のすべての制御信号は、静的である。出力データレートは、データがキューを出るレートによって推定される。次いで、出力データレートは、単極IIR移動平均フィルタを使用してフィルタ処理される。このシミュレーションでは、RTTは、推定されるのではなく、何らかの値(EstRTT)に固定される。この場合、実際にはRTTは0.4秒であるが、EstRTTは、0.4375秒に設定される。実際の物理データレートは、16kB/sから8kB/s、さらに32kB/sに変わる。キューに入ってくるデータは、単一のTCPストリームである。図8Aは、シミュレーションの結果を示す。
【０１１５】
シミュレーションパラメータ:
輻輳制御アルゴリズムパラメータ
3000    Start_CngTh  開始輻輳閾値
2      MinDropInterval(秒)-パケットのドロップ間の初期最小時間量
0.4375  EstRTT-MinDropIntervalを計算するために使用される推定RTT
出力データレート
16      開始レート(KB/秒)
25      出力レートを変更する時間(秒)
8      変更レート(KB/秒)
45      出力レートを変更する時間(秒)
32      変更レート(KB/秒)
【０１１６】
上記の結果からわかるように、実際の物理データレートが16kB/sから8kB/s、さらに32kB/sに変わる場合でも、キューの出力データレートは、常に、物理出力データレートと等しい傾向にあり、過度のキューイングはない。
【０１１７】
[MinPacketIntFuncの説明]
MinPacketIntFuncは、最小パケット間隔制御信号を動的にするために使用される。上述したように、キューサイズを制御するために、制御信号、最小パケット間隔が主な信号として使用された場合、最小パケット間隔は、次のように設定すべきである。
最小パケット間隔=(DR/IPSegSize)*最短時間間隔
【０１１８】
【数５】
2010528506.tif 000007
【０１１９】
DR=出力データレート
【０１２０】
上記の式には変数しかないため、式は、次のように簡略化することが可能である。
最小パケット間隔=K1*DR^2*RTT^2+K2*RTT*DR
RTTおよび出力データレートを推定するために、上述した同じ方法を使用することが可能である。
【０１２１】
[TCP以外のトラフィックを検討する]
ここまで、すべてのシミュレーションへのキューへの入力は、単一のTCPストリームであった。以下のセクションでは、TCP IPトラフィックが従うものと同じ輻輳制御ルールに従わないUDPなどのIPトラフィックも含めた入力ストリームに対して、キュー管理システムがどのように反応するかを調べる。
【０１２２】
以下のシミュレーションは、輻輳閾値のみが動的であり、他のすべての制御信号が使用されるが、静的である、図7Aに示される同じキュー管理システムを使用する。キューへの入力データストリームは、6kB/秒のTCPデータストリームおよびUDPデータストリームであり、物理出力データレートは、8kB/sと32kB/sとの間で変化する。図9Aは、結果を示す。
【０１２３】
シミュレーションパラメータ:
UDPパラメータ
6000    UDP_DR-UDPデータレート(バイト/秒)
輻輳制御アルゴリズムパラメータ
3000    Start_CngTh  開始輻輳閾値
0      MinPacketInterval-ドロップ間のパケットの最低数
2      MinDropInterval(秒)-パケットのドロップ間の初期最小時間量
0.4375  EstRTT-MinDropIntervalを計算するために使用される推定RTT
出力データレート
16      開始レート(KB/秒)
60      出力レートを変更する時間(秒)
8      変更レート(KB/秒)
90      出力レートを変更する時間(秒)
32      変更レート(KB/秒)
【０１２４】
上記の結果は、キューの出力データレートが物理層の出力に等しい傾向にあり、これは良いが、48秒の時点および80秒の時点など、一部の例では、立て続けにドロップされるUDPパケットが多すぎるときに過度のキューイングが起こることを示す。最短時間間隔は、キューマネージャがパケットをより速くドロップすることを防いでいる。
UDPが物理出力データレートを超えて増加した場合、過度のキューイングの問題は、管理しにくくなる。以下は、上記と同じシステムのシミュレーションであるが、UDPデータレートは、18kB/sに設定され、この場合、物理出力データレートは、わずか16kB/sである。図10Aからわかるように、キューサイズは、キュー管理アルゴリズムが十分速くパケットをドロップしていないので、制御不能に増大する。
【０１２５】
次のセクションでは、この問題を修正するために実施することが可能なアルゴリズムへの追加について概説する。
【０１２６】
[プロトコル固有のドロッピングルール]
この問題の1つの解決策は、ドロッピングのためのプロトコル固有のルールを組み込むことである。例えば、最短時間間隔は、UDPパケット対TCPパケットで異なることになる。UDPパケットでは、最短時間間隔は、ゼロに近くなる可能性があり、またそうなるはずである。というのは、TCPパケットと異なり、輻輳制御の開始を待つ必要はないからである。また、輻輳閾値、最小パケット間隔、およびドロップサイズは、プロトコルによって異なり得る。この手法の主な欠点は、それが送信しているトランスポートプロトコルを決定するために、キュー管理システムがパケットを構文解析できることを必要とすることである。処理上の欠点の他に、VPNまたは他の暗号化が使用される場合、キュー管理システムは、プロトコルタイプを決定するために、パケットを構文解析することができない。上述したように、この暗号化問題の可能な解決策は、使用されるプロトコルを決定し、次いでパケットをそれに応じてマークするために、暗号化の前にフィルタドライバのようなエンティティを使用することである。
【０１２７】
[動的な2段階最小ドロップ間隔機構]
過度のキューイング問題を解決するための別の方法は、本書では「動的な2段階最小ドロップ間隔」またはDTSMと呼ばれる追加の論理をキュー管理方法に追加することである。DTSMの基本概念は、キューが輻輳閾値を過度に超えたとき、最小ドロップ間隔を低減することである。最小ドロップ間隔が低減されるべき量は、現在のキュー深度がどれだけ輻輳閾値を超えているかに関係する。推奨される方法は、輻輳閾値超過比(Congestion Threshold Exceed Ratio)(CngThExceedRatio)と呼ばれる新しい制御パラメータを定義することである。CngThExceedRatioは、最短時間間隔がゼロに等しい場合、キュー深度が輻輳閾値を超える可能性のあるパーセント単位の量である。以下の式は、さらに詳細および説明を追加する。
以下の通り仮定する。
【０１２８】
ベース最小ドロップ間隔:
キュー深度が輻輳閾値CngThExceedRatio未満であるときの最小ドロップ間隔:
最短時間間隔がゼロに等しい場合、キュー深度が輻輳閾値を超える可能性のあるパーセント単位の量。
キュー深度が輻輳閾値を超えると、最小ドロップ間隔は、次のように計算される。
最小ドロップ間隔=ベース最小ドロップ間隔*MinDropIntervalMultiplier
そうでない場合、
最小ドロップ間隔=ベース最小ドロップ間隔
【０１２９】
MinDropIntervalMultiplierを計算するために可能な方法は無限に存在する。以下は、計算の範囲である。
・MinDropIntervalMultiplier=1.0  キュー深度が輻輳閾値に等しい場合
・MinDropIntervalMultiplier=0.0  キュー深度が輻輳閾値*CngThExceedRatioに等しい場合
・MinDropIntervalMultiplierは、ExceedsRatioが増えるにつれて増加するはずである
ExceedsRatioは、キュー深度が輻輳閾値を超える割合であり、以下によって計算される。
【０１３０】
【数６】
2010528506.tif 000008
【０１３１】
MinDropIntervalMultiplierは、この簡単な線形補間式を使用して計算することが可能である。
MinDropIntervalMultiplier=1-ExceedRatio/CngThExceedRatio
あるいは、より複雑ではあるが、指数関係を使用してMinDropIntervalMultiplierを計算することができ、これは、以下によって得られる。
MinDropIntervalMultiplier=1-ExponentialBaseExceedRatio/CngThExceedRatio
【０１３２】
指数式は、キュー深度が輻輳閾値*CngThExceedRatioを超えるとき、負の数字を戻すことができるため、MinDropIntervalMultiplierは、0から1までの範囲に限定されなければならない。指数関数は、より多くの計算を要するが、誤ってパケットをドロップすることなく、より低いCngThExceedRatioを使用することができる。
【０１３３】
キュー深度が急速に変わり得るため、起こり得る過渡現象を取り除くために、計算された最小ドロップ間隔が平滑化され、またはフィルタ処理されることが推奨される。このフィルタ処理は、自然に起こり得るキュー深度におけるピークのために、最小ドロップ間隔を誤って低下させる可能性を小さくする。
【０１３４】
動的な2段階最小ドロップ間隔機構(DTSM)を使用して、いくつかのシミュレーションが行われた。示したすべてのシミュレーションは、ExponentialBase=4のMinDropIntervalMuitiplierの指数計算を使用している。CngThExceedRatioは、すべてのシミュレーションについて50%に設定されている。
【０１３５】
以下のシミュレーション結果は、図10Aに示したものと同じ入力データストリームおよび物理層パラメータを使用しており、ここでは、UDPレート=18kB/s、物理出力レート=16kB/sである。
【０１３６】
シミュレーションパラメータ:
UDPパラメータ
18      UDP_DR-UDPデータレート(キロバイト/秒)
輻輳制御アルゴリズムパラメータ
4000    Start_CngTh  開始輻輳閾値
1200    DropSizeTh-ドロップするパケットの最小サイズ。
2      MinDropInterval(秒)-パケットのドロップ間の初期最小時間量
0.4375  EstRTT-推定RTT
0.5     CngTh_Exceed_Ratio-MinDropIntervalがゼロに近づく場合、キュー深度が増大し得る最大パーセント
物理層
16      出力データレート(KB/秒)
【０１３７】
図11Aからわかるように、ここでキューイング深度は、TCPセッションがスロースタートの状態である開始時に、何らかの過度のキューイングが起こるだけで制御される。キューは、決して空ではないため、キューの出力レートが物理出力レートに等しいことは、驚きではない。図11Aは、スロースタート手順中、TCPが輻輳制御状態にあるときに比べて、UDPストリームがより大きい割合の物理出力レートを使用しており、TCPストリームが約3500kB/sを使用していることも示す。UDPレートが物理出力レートより大きいとき、TCP輻輳ウィンドウは、一般に、パケットの過度のドロッピングのために1セグメントに限定される。この小さい輻輳ウィンドウは、DBPの式に基づいてTCPレートを限定する(上記のシミュレーションではMTUSize/RTT 1450/0.4=3625B/s)。
【０１３８】
図12Aに示されている次のシミュレーション出力は、前と同じDTSMキュー管理システムを使用しているが、この場合、物理出力レートが16kB/sから8kB/s、さらに32kB/sに変わる。
【０１３９】
シミュレーションパラメータ:
UDPパラメータ
18      UDP_DR-UDPデータレート(キロバイト/秒)
輻輳制御アルゴリズムパラメータ
4000    Start_CngTh  開始輻輳閾値
2      MinDropInterval(秒)-パケットのドロップ間の初期最小時間量
0.4375  EstRTT-MinDropIntervalを計算するために使用される推定RTT
0.5     CngTh_Exceed_Ratio-MinDropIntervalがゼロに近づく場合、キュー深度が増大し得る最大パーセント
出力データレート
16      開始レート(KB/秒)
60      出力レートを変更する時間(秒)
8      変更レート(KB/秒)
90      出力レートを変更する時間(秒)
32      変更レート(KB/秒)
【０１４０】
上記のシミュレーション結果は、動的な輻輳閾値信号と組み合わせて、DTSMを追加することによって、様々な物理出力レートについて、キューイング深度が低減することを示す。
【０１４１】
DTSM方法には2つの既知の欠点がある。第1は、TCPスロースタート機構中、キュー管理システムが1つより多くのパケットを誤ってドロップすることである。TCPスタックが輻輳制御状態に移動した後、この方法は、1つだけパケットをドロップし、TCPスタックが応答するのを待つことによって、意図したように働く。第2の欠点は、物理出力レートが突然ドロップすると、DTSM方法は、1つを超えるパケットを誤ってドロップし得ることである。物理出力レートの突然のドロップによって、輻輳閾値は、突然ドロップし、これは、そのときの現在のキュー深度によって、現在のキュー深度が輻輳閾値をはるかに超える状況を作り出す可能性がある。この悪影響は、より大きいCngTh_Exceed_Ratioが使用される場合、最低限に抑えることが可能である。これら両方の負の影響を無くすには、100%を超えるCngTh_Exceed_Ratioが必要であるが、これは、当然キュー深度の増加を犠牲にする。
【０１４２】
これら2つの影響を示すために、図13Aにおける次のシミュレーション結果は、前のものと同じDTSMキュー管理システムを使用しているが、この場合、キューへの入力はTCPデータのみであり、UDPデータはない。
【０１４３】
シミュレーションパラメータ:
UDPパラメータ
0      UDP_DR-UDPデータレート(キロバイト/秒)
輻輳制御アルゴリズムパラメータ
4000    Start_CngTh  開始輻輳閾値
2      MinDropInterval(秒)-パケットのドロップ間の初期最小時間量
0.4375  EstRTT-MinDropIntervalを計算するために使用される推定RTT
0.5     CngTh_Exceed_Ratio-MinDropIntervalがゼロに近づく場合、キュー深度が増大し得る最大パーセント
出力データレート
16      開始レート(KB/秒)
60      出力レートを変更する時間(秒)
8      変更レート(KB/秒)
90      出力レートを変更する時間(秒)
32      変更レート(KB/秒)
【０１４４】
上記のシミュレーションの〜4秒の時点において、TCPスタックがスロースタート状態であるとき、複数のTCPパケットがドロップされる。これは、〜7秒の時点において、平均キュー出力レートの一時的なドロップをもたらす。
【０１４５】
第2の負の影響は、〜60秒の時点に示されており、ここで、物理出力レートは、16kB/sから8kB/sに変わる。この場合、キュー管理システムは、いくつかのTCPパケットを誤ってドロップしており、これによって、平均キュー出力レートにおける一時的な低下がもたらされることがわかる。
【０１４６】
CngTh_Exceed_Ratioを大きい値に設定することによって、過度のキューイングがもたらされるが、CngTh_Exceed_Ratioが非常に小さいと、図13Aに示されるように、誤ったパケットのドロップがもたらされる。極めて指数的な式を使用して最小ドロップ間隔を計算することによって、より低いCngTh_Exceed_Ratioを使用することができるが、これは、ある程度しか役に立たない。
【０１４７】
上記のキュー管理システムは、動的な輻輳閾値と共にDTSMを使用しているが、DTSMシステムは、上述した動的な最短時間間隔および最小パケット間隔システムと共に使用することも可能である。
【符号の説明】
【０１４８】
200  データ通信システム
205  データソース
210  ネットワーク装置
215  キュー管理機能
220  マルチプレクサ
500  処理システム
501  バス
502  CPU
503  信号プロセッサ
504  メインメモリ
506  静的メモリ
507  大容量記憶装置
525  入出力(I/O)装置
526  音声装置
531  制御ユニット
532  演算論理ユニット(ALU)
533  レジスタ
【図１】
2010528506.tif 000009
【図２】
2010528506.tif 000010
【図３】
2010528506.tif 000011
【図４】
2010528506.tif 000012
【図５】
2010528506.tif 000013
【図１Ａ】
2010528506.tif 000014
【図２Ａ】
2010528506.tif 000015
【図３Ａ】
2010528506.tif 000016
【図４Ａ】
2010528506.tif 000017
【図５Ａ】
2010528506.tif 000018
【図６Ａ】
2010528506.tif 000019
【図７Ａ】
2010528506.tif 000020
【図８Ａ】
2010528506.tif 000021
【図９Ａ】
2010528506.tif 000022
【図１０Ａ】
2010528506.tif 000023
【図１１Ａ】
2010528506.tif 000024
【図１２Ａ】
2010528506.tif 000025
【図１３Ａ】
2010528506.tif 000026
【手続補正書】
【提出日】平成22年1月22日(2010.1.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
インターネットプロトコルデータを1つまたは複数のネットワーク装置で受信するステップと、
前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するステップと、
を含み、
前記インターネットプロトコルデータは、データソース装置で生成され、前記1つまたは複数のネットワーク装置に伝えられ、
前記指定された基準は、前回のドロップからの時間、前回のドロップからのパケット数、パケットプロトコル、パケットサイズ、およびその組合せから成るグループから選択されることを特徴とする方法。
【請求項２】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項1に記載の方法。
【請求項３】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項1に記載の方法。
【請求項４】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項1に記載の方法。
【請求項５】
フロー制御可能なインターフェイスを介して伝えられるインターネットプロトコルデータを、1つまたは複数のネットワーク装置で受信するステップと、
前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するステップと
を含み、
前記インターネットプロトコルデータは、データソース装置で生成され、前記1つまたは複数のネットワーク装置に伝えられることを特徴とする方法。
【請求項６】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項5に記載の方法。
【請求項７】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項5に記載の方法。
【請求項８】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項5に記載の方法。
【請求項９】
データソース装置に通信可能に結合されるネットワーク装置であって、前記データソース装置で生成されたインターネットプロトコルデータを受信し、前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するように構成されており、前記指定された基準が前回のドロップからの時間、前回のドロップからのパケット数、パケットプロトコル、パケットサイズ、およびその組合せから成るグループから選択されるネットワーク装置、
を含むことを特徴とする装置。
【請求項１０】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項9に記載の装置。
【請求項１１】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項9に記載の装置。
【請求項１２】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項9に記載の装置。
【請求項１３】
データソース装置に通信可能に結合されるネットワーク装置であって、前記データソース装置で生成され、フロー制御可能なインターフェイスを介して伝えられるインターネットプロトコルデータを受信し、前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するように構成されているネットワーク装置
を含むことを特徴とする装置。
【請求項１４】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項13に記載の装置。
【請求項１５】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項13に記載の装置。
【請求項１６】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項13に記載の装置。
【請求項１７】
実行可能命令を提供する機械可読媒体であって、プロセッサによって実行されると、前記プロセッサに、
インターネットプロトコルデータを1つまたは複数のネットワーク装置で受信するステップと、
前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて前記データの部分を選択的に削除するステップと、
を含み、
前記インターネットプロトコルデータは、データソース装置で生成され、前記1つまたは複数のネットワーク装置に伝えられ、
前記指定された基準は、前回のドロップからの時間、前回のドロップからのパケット数、パケットプロトコル、パケットサイズ、およびその組合せから成るグループから選択される方法、
を実行させることを特徴とする機械可読媒体。
【請求項１８】
前記指定された基準のうちの1つまたは複数が動的に決定されることを特徴とする請求項17に記載の機械可読媒体。
【請求項１９】
1つまたは複数の指定された基準が、動的に決定される対応する値を有することを特徴とする請求項17に記載の機械可読媒体。
【請求項２０】
前記生成されたデータが暗号化され、前記指定された基準がパケットサイズを含むことを特徴とする請求項17に記載の機械可読媒体。
【請求項２１】
実行可能命令を提供する機械可読媒体であって、プロセッサによって実行されると、前記プロセッサに、
フロー制御可能なインターフェイスを介して伝えられるインターネットプロトコルデータを、1つまたは複数のネットワーク装置で受信するステップと、
前記インターネットプロトコルデータのデータフローの向上をもたらすために、指定された基準に基づいて、前記データの部分を選択的に削除するステップと
を含み、
前記インターネットプロトコルデータは、データソース装置で生成され、前記1つまたは複数のネットワーク装置に伝えられる方法、
を実行させることを特徴とする機械可読媒体。
【国際調査報告】
2010528506.tif 000027
2010528506.tif 000028