Loading article…
スライディングウィンドウ プロトコルは、パケット ベースのデータ転送 プロトコルの機能です。スライディング ウィンドウ プロトコルは、データ リンク層( OSI レイヤー 2 ) や転送制御プロトコル( TCP ウィンドウ処理など) など、パケットの信頼性の高い順序どおりの配信が求められる場合に使用されます。また、チャネルに高遅延が含まれる可能性がある場合に効率を向上させるためにも使用されます。
パケットベースのシステムは、データのバッチであるパケットと、受信側が正しく受信したことを確認できる追加データ(チェックサムなど) を送信するというアイデアに基づいています。このパラダイムは、新しいパケットの入力を許可し、すでに確認済みのパケットを拒否するために横にスライドするウィンドウに似ています。受信側がデータを検証すると、確認信号(ACK) を送信側に送り返し、次のパケットを送信できることを示します。単純な自動再送要求プロトコル (ARQ) では、送信側はパケットを送信するたびに停止し、受信側が ACK を返すのを待ちます。これにより、一度に 1 つのパケットしか送信できないため、パケットが正しい順序で到着することが保証されます。
ACK 信号を受信するのにかかる時間は、パケットを送信するのに必要な時間に比べてかなり長い場合があります。この場合、全体的なスループットは理論上可能な範囲よりはるかに低くなる可能性があります。これに対処するために、スライディング ウィンドウ プロトコルでは、ウィンドウと呼ばれる選択した数のパケットをACK を待たずに送信できます。各パケットはシーケンス番号を受け取り、ACK はその番号を返します。プロトコルはどのパケットが ACK されたかを追跡し、受信されるとさらにパケットを送信します。このようにして、ウィンドウは転送を構成するパケットのストリームに沿って スライドします。
スライディング ウィンドウは、多くのプロトコルの重要な部分です。これは、パケットが順序どおりに到着しないことを本質的に許容する TCP プロトコルの重要な部分であり、また、XMODEMなどのウィンドウのないプロトコルと比較して効率を向上させる方法として、UUCP-gやZMODEMなどの多くのファイル転送プロトコルにも使用されています。SEAlinkも参照してください。
基本的な考え方
概念的には、送信の各部分 (ほとんどのデータ リンク層ではパケット、TCP ではバイト) に一意の連続したシーケンス番号が割り当てられ、受信側はそれらの番号を使用して受信したパケットを正しい順序に配置し、重複したパケットを破棄して、欠落したパケットを識別します。これの問題は、必要なシーケンス番号のサイズに制限がないことです。
スライディング ウィンドウ プロトコルでは、任意の時点で送信または受信できるパケットの数に制限を設けることで、固定サイズのシーケンス番号を使用して無制限の数のパケットを通信できます。送信側でのウィンドウという用語は、受信側によってまだ確認応答されていないパケットの合計数の論理的な境界を表します。受信側は、各確認応答パケットで、現在の最大受信側バッファ サイズ (ウィンドウ境界) を送信側に通知します。TCP ヘッダーは、16 ビット フィールドを使用して、受信側ウィンドウ サイズを送信側に報告します。したがって、使用できる最大のウィンドウは 2 16 = 64 キロバイトです。
スロースタート モードでは、送信機は低いパケット数で開始し、受信機から確認応答パケットを受信した後、各送信のパケット数を増やします。受信されたack パケットごとに、ウィンドウは 1 パケットずつ (論理的に) スライドし、1 つの新しいパケットを送信します。ウィンドウしきい値に達すると、送信機は受信した ack パケット 1 つにつき 1 つのパケットを送信します。
ウィンドウ制限が 10 パケットの場合、スロー スタート モードでは、送信機は 1 つのパケットの送信を開始し、続いて 2 つのパケット (2 つのパケットを送信する前に、1 つのパケット ack を受信する必要があります)、続いて 3 つのパケットの送信というように、10 パケットまで送信を続けることができます。ただし、10 パケットに達した後は、それ以降の送信は 1 つの ack パケットを受信するごとに 1 つのパケットの送信に制限されます。シミュレーションでは、ウィンドウが ack パケットを受信するたびに 1 パケットの距離だけ移動しているように見えます。受信側でも、ウィンドウはパケットを受信するたびに 1 つのパケットだけ移動します。
スライディング ウィンドウ方式により、ネットワーク上のトラフィックの輻輳が回避されます。送信側と受信側の TCP がパケット バッファのスライディング ウィンドウを実装しているため、アプリケーション層はネットワーク トラフィックの輻輳の問題を心配することなく、TCP に送信するデータを提供し続けます。ウィンドウ サイズは、ネットワーク トラフィックに応じて動的に変化することがあります。
スループットを最大限に高めるには、送信側がスライディング ウィンドウ プロトコルによって 1往復遅延時間(RTT) より早く送信を停止しないようにすることが重要です。確認応答を待つために停止する前に送信できるデータ量の制限は、通信リンクの帯域幅遅延積よりも大きくする必要があります。そうでない場合、プロトコルによってリンクの 有効帯域幅が制限されます。
モチベーション
エラー制御のための自動再送要求に基づく通信プロトコルでは、受信側は受信したパケットを確認する必要がある。送信側が妥当な時間内に確認応答を受信しない場合は、データを再送信する。
確認応答を受け取らない送信機は、受信機が実際にパケットを受信したかどうかを知ることができません。送信中にパケットが失われたか破損した可能性があります。エラー検出メカニズムによって破損が明らかになった場合、パケットは受信機によって無視され、否定応答または重複した確認応答が受信機によって送信されます。受信機は、確認応答をまったく送信しないように設定されている場合もあります。同様に、受信機は通常、確認応答が受信されているかどうかについて確信がありません。確認応答は送信されたが、伝送媒体で失われたか破損した可能性があります。この場合、受信機は、データが継続的に再送されるのを防ぐために再送を確認する必要がありますが、それ以外の場合は無視する必要があります。
プロトコル操作
送信機と受信機には、それぞれ現在のシーケンス番号n tとn rがあります。また、送信機と受信機にはそれぞれウィンドウ サイズw tとw rがあります。ウィンドウ サイズは変化する可能性がありますが、より単純な実装では固定されています。処理を進めるには、ウィンドウ サイズが 0 より大きくなければなりません。
一般的な実装では、n t は次に送信されるパケット、つまりまだ送信されていない最初のパケットのシーケンス番号です。同様に、n r はまだ受信されていない最初のパケットです。両方の数値は時間とともに単調に増加し、常に増加します。
受信側は、これまで受信した最高のシーケンス番号も記録しておくことができます。変数n s は、受信した最高のシーケンス番号のシーケンス番号より 1 大きい値です。パケットを順番にのみ受け入れる単純な受信側 ( w r = 1) の場合、これはn rと同じですが、 w r > 1 の場合は大きくなります。違いに注意してください。n r未満のパケットはすべて受信され、 n s を超えるパケットは受信されておらず、n rと n s の間では、いくつかのパケットが受信されています。
受信側はパケットを受信すると、変数を適切に更新し、新しいn rで確認応答を送信します。送信側は、受信した最高の確認応答n aを記録します。送信側は、 n aまでのすべてのパケットが受信されたことを認識していますが、 n aとn sの間のパケット、つまりn a ≤ n r ≤ n sについては不明です。
シーケンス番号は常にn a ≤ n r ≤ n s < n t ≤ n a + w tという規則に従います。つまり、
- n a ≤ n r : 送信側が受信する最高の確認応答は、受信側が受信する最高のn rよりも高くすることはできません。
- n r ≤ n s : 完全に受信されたパケットの範囲は、部分的に受信されたパケットの終わりを超えて拡張することはできません。
- n s < n t : 受信した最高パケットは、まだ送信されていない最高パケットよりも高くなることはできません。
- n t ≤ n a + w t : 送信される最高のパケットは、受信される最高の確認応答と送信ウィンドウのサイズによって制限されます。
送信機の操作
送信機は送信するデータがあるときはいつでも、最新の確認応答n aより最大w t 個のパケットを送信できます。つまり、n t < n a + w tである限り、パケット番号n t を送信できます。
通信エラーがない場合、送信機はすぐに送信したすべてのパケットの確認応答を受信し、n a はn tと等しくなります。妥当な遅延後にこれが発生しない場合は、送信機はn aとn tの間のパケットを再送信する必要があります。
合理的な遅延を定義するための手法は非常に複雑になる可能性がありますが、それらは効率にのみ影響します。スライディング ウィンドウ プロトコルの基本的な信頼性は、詳細には依存しません。
受信機の操作
番号xのパケットを受信するたびに、受信機はそれが受信ウィンドウn r ≤ x < n r + w r内にあるかどうかを確認します。(最も単純な受信機は、 1 つの値n r = n sのみを追跡する必要があります。) ウィンドウ内にあれば、受信機はそれを受け入れます。番号がn rの場合、受信シーケンス番号は 1 増加し、さらに連続するパケットが以前に受信され保存されていた場合は、さらに増加する可能性があります。x > n rの場合、パケットは先行するすべてのパケットが受信されるまで保存されます。[1] x ≥ n s の場合、後者はn s = x +1 に更新されます。
パケットの番号が受信ウィンドウ内にない場合、受信側はそれを破棄し、n rまたはn s を変更しません。
パケットが受け入れられたかどうかに関わらず、受信側は現在のn r を含む確認応答を送信します。(確認応答にはn rとn sの間に受信された追加のパケットに関する情報も含まれる場合がありますが、これは効率性を高めるためだけのものです。)
送信されないパケットを受信する心配はないので、受信ウィンドウw rを送信ウィンドウw tより大きくしても意味がないことに注意してください。有効な範囲は 1 ≤ w r ≤ w tです。
シーケンス番号の範囲が必要です
これまでのところ、プロトコルは、シーケンス番号が無制限のサイズで増加し続けるかのように説明されています。ただし、メッセージで完全なシーケンス番号x を送信するのではなく、有限のNに対してx mod Nのみを送信することも可能です。( N は通常、2 の累乗です。)
たとえば、送信機はn aからn tまでの範囲の確認応答のみを受信します。 n t − n a ≤ w tが保証されるため、任意の時点で到着する可能性のあるシーケンス番号は最大でw t +1 個です。したがって、 N > w tである限り、送信機はシーケンス番号を明確にデコードできます。
受信側では、より強い制約が課せられます。プロトコルの動作は、受信側が新しいパケット (受け入れて処理する) と古いパケットの再送信 (破棄して最後の確認応答を再送信する) を確実に区別できるかどうかに依存します。これは、送信側のウィンドウ サイズがわかっていれば実行できます。x という番号のパケットを受信した後、受信側はx < n a + w t、つまりn a > x − w tであることがわかります。したがって、x − w tという番号のパケットは、二度と再送信されません。
将来私たちが受け取る最小のシーケンス番号はn s − w tです。
受信側は、送信側のn a が、これまでに送信された最高の確認応答であるn rより大きくなることはないことも知っています。したがって、受信側が確認できる最大のシーケンス番号は、n r + w t ≤ n s + w tです。
したがって、受信機が一度に受信できるシーケンス番号は2 w t通りあります。したがって、 N ≥ 2 w tである必要があると思われるかもしれません。ただし、実際の制限はそれよりも低くなります。
さらに、受信側はシーケンス番号が低すぎる ( n r未満) か高すぎる ( n s + w r以上) かを区別する必要がないこともわかります。どちらの場合も、受信側は確認応答を再送信する場合を除いてパケットを無視します。したがって、N ≥ w t + w rであることだけが必要です。 w r < w tであることが一般的であるため(たとえば、以下の Go-Back-N を参照)、これにより、固定のN内でより大きなw t が許可されます。
例
最もシンプルなスライディングウィンドウ：停止して待機
一般的にはスライディング ウィンドウ プロトコルとは区別されますが、ストップ アンド ウェイト ARQプロトコルは、実際にはスライディング ウィンドウ プロトコルの最も単純な実装です。送信ウィンドウは 1 パケットで、受信ウィンドウは 1 パケットです。したがって、N = 2 個の可能なシーケンス番号 (便宜上、1ビットで表されます) が必要です。
曖昧さの例
送信機は、奇数と偶数のマークが付いたパケットを交互に送信します。確認応答も同様に、奇数と偶数です。送信機が奇数パケットを送信した後、奇数確認応答を待たずに、次の偶数パケットをすぐに送信したとします。すると、「次は奇数パケットを期待しています」という確認応答を受信する可能性があります。この場合、送信機は困惑します。受信機は両方のパケットを受信したのか、それともどちらも受信しなかったのか?
戻るN
Go-Back-N ARQ は、w t >1 であるが、w r =1 に固定されているスライディング ウィンドウ プロトコルです。受信側は、シーケンス内の次のパケット以外のパケットの受信を拒否します。パケットが転送中に失われた場合、失われたパケットが再送信されるまで、後続のパケットは無視されます。最小損失は 1往復時間です。このため、パケット損失が頻繁に発生するリンクでは非効率的です。
曖昧さの例
HDLCで一般的な 3 ビットのシーケンス番号を使用するとします。この場合、N =2 3 =8 となります。w r =1 なので、w t ≤7に制限する必要があります。これは、7 つのパケットを送信した後、8 つの結果が考えられるためです。0 から 7 までのパケットが正常に受信された可能性があります。これは 8 つの可能性であり、送信側は確認応答でそれらすべてを区別するのに十分な情報を必要とします。
送信機が確認応答を待たずに 8 つのパケットを送信した場合、停止して待機する場合と同様の難問に陥る可能性があります。確認応答は、8 つのパケットがすべて正常に受信されたことを意味するのか、それともどれも受信されなかったことを意味するのか?
選択的繰り返し
スライディング ウィンドウ プロトコルの最も一般的なケースは、選択的繰り返し ARQです。これには、現在のn rよりも高いシーケンス番号を持つパケットを受け入れ、ギャップが埋められるまでそれらを保存できる、はるかに高性能な受信機が必要です。
ただし、利点は、送信機に再送信が必要であることを通知する前に、1 ラウンドトリップ時間後に続く正しいデータを破棄する必要がないことです。したがって、信頼性が低いリンクや帯域幅遅延積が高いリンクに適しています。
ウィンドウ サイズw rは、許容できる連続したパケット損失数よりも大きくする必要があります。したがって、小さい値が一般的です。w r =2 が一般的です。
曖昧さの例
非常に普及しているHDLC プロトコルは3 ビットのシーケンス番号を使用し、選択的繰り返しのオプション規定を備えています。ただし、選択的繰り返しを使用する場合は、n t + n r ≤ 8 という要件を維持する必要があります。w r が 2 に増加する場合は、w tを6に減らす必要があります。
w r =2であると仮定します が、 HDLC の go-back-N バリアントで通常使用されるように、 w t =7 で変更されていない送信機が使用されるものとします。さらに、受信機がn r = n s =0 で始まると仮定します。
ここで、受信側が次の一連のパケット (すべて 8 を法とする) を見たとします。
- 0 1 2 3 4 5 6 (一時停止) 0
w r =2 であるため 、受信側は最後のパケット 0 (一連のパケット 8 であると想定) を受け入れて保存し、パケット 7 の再送信を要求します。ただし、送信側が確認応答を受信できず、パケット 0 を再送信した可能性もあります。後者の場合、受信側は間違ったパケットをパケット 8 として受け入れることになります。
解決策は、送信側がw t ≤6 に制限することです。この制限により、受信側は、すべての確認応答が失われた場合、送信側はパケット 5 の後に停止していることがわかります。受信側はパケット 6 を受信すると、送信側がパケット 0 の確認応答を受信した (送信側のn a ≥1) と推測できるため、次の番号 0 のパケットはパケット 8 である必要があります。
拡張機能
プロトコルを拡張する方法は多数あります。
- 上記の例では、パケットが送信中に順序変更されないことを前提としています。パケットは送信中に失われる可能性はありますが (エラー検出により破損は損失と同等になります)、順序が乱れることはありません。距離を制限できる限り、プロトコルを拡張してパケットの順序変更をサポートすることができます。シーケンス番号係数Nは、最大順序変更距離によって拡張する必要があります。
- 一時停止があった場合に最終的に確認応答が送信される限り、すべてのパケットを確認しなくてもかまいません。たとえば、TCP は通常、2 パケットごとに確認応答します。
- パケット シーケンスにギャップが検出された場合は、すぐに送信機に通知するのが一般的です。HDLC には、このための特別な REJ (拒否) パケットがあります。
- 送信ウィンドウ サイズと受信ウィンドウ サイズは、その合計がNの制限内である限り、通信中に変更できます。通常、送信ウィンドウ サイズと受信ウィンドウ サイズにはそれぞれその制限を尊重する最大値が割り当てられますが、特定の時点での動作値は最大値よりも小さくなる場合があります。具体的には、次のようになります。
- 飽和や輻輳を回避するために、リンクの速度に合わせて送信速度を遅くするために送信ウィンドウのサイズを小さくするのが一般的です。
- 選択的繰り返しの一般的な簡略化の 1 つは、いわゆる SREJ-REJ ARQ です。これはw r =2 で動作し、ギャップに続くパケットをバッファリングしますが、失われたパケットは 1 つだけ許可されます。そのパケットを待機している間、w r =1 であり、2 番目のパケットが失われた場合、それ以上のパケットはバッファリングされません。これにより、完全な選択的繰り返しプロトコルのパフォーマンス上の利点のほとんどが、より簡単な実装で得られます。
参照
参考文献
- ^ピーターソン、ラリー・L. & デイビー、ブルース・S. "[ 1 ]", モーガン・カウフマン、2000年。ISBN 1-55860-577-0
- Comer, Douglas E.「TCP/IP によるインターネットワーキング、第 1 巻: 原理、プロトコル、アーキテクチャ」、Prentice Hall、1995 年。ISBN 0-13-216987-8
外部リンク
- RFC 1323 - 高性能のための TCP 拡張
- TCP ウィンドウ スケーリングと壊れたルーター、2004 年