 |
スライディングウィンドウプロトコルは、パケットベースのデータ伝送プロトコルの機能です。スライディングウィンドウプロトコルは、データリンク層（OSI第2層）や伝送制御プロトコル（TCPウィンドウ処理など）など、パケットの信頼性の高い順序どおりの配信が求められる場合に使用されます。また、チャネルに高い遅延が発生する可能性がある場合の効率向上にも使用されます。
パケットベースのシステムは、データのバッチ（パケット）と、受信側が正しく受信したことを確認できる追加データ（チェックサムなど）を送信するというアイデアに基づいています。このパラダイムは、新しいパケットの受信を許可し、すでに確認応答されたパケットを拒否するために横にスライドする窓に似ています。受信側がデータを検証すると、確認応答信号（ACK）を送信側に送り返し、次のパケットを送信できることを知らせます。単純な自動再送要求プロトコル（ARQ）では、送信側はパケットを送信するたびに停止し、受信側がACKを返すのを待ちます。これにより、一度に1つしか送信できないため、パケットが正しい順序で到着することが保証されます。
ACK信号を受信するまでの時間は、パケットの送信に必要な時間と比較して、かなり長い場合があります。この場合、全体的なスループットは理論上可能な範囲をはるかに下回る可能性があります。この問題に対処するため、スライディングウィンドウプロトコルでは、ウィンドウと呼ばれる一定数のパケットをACKを待たずに送信できます。各パケットにはシーケンス番号が付与され、ACKはその番号を返します。プロトコルはどのパケットがACKされたかを追跡し、ACKを受信すると、さらにパケットを送信します。このように、ウィンドウは転送を構成するパケットのストリームに沿って 移動します。
スライディングウィンドウは多くのプロトコルの重要な構成要素です。TCPプロトコルの重要な構成要素であり、パケットの順序不同の到着を本質的に許容します。また、UUCP-gやZMODEMなどの多くのファイル転送プロトコルでも、 XMODEMなどのウィンドウを持たないプロトコルと比較して効率を向上させる方法として採用されています。SEAlinkも参照してください。
基本的な概念
概念的には、伝送の各部分（ほとんどのデータリンク層ではパケット、TCPではバイト）に一意の連続したシーケンス番号が割り当てられ、受信側はこれらの番号を使用して受信パケットを正しい順序に並べ、重複したパケットを破棄し、欠落したパケットを識別します。この方法の問題点は、必要なシーケンス番号のサイズに制限がないことです。
スライディングウィンドウプロトコルでは、ある時点で送受信できるパケット数に制限を設けることで、固定サイズのシーケンス番号を使用して無制限の数のパケットを通信できます。送信側における「ウィンドウ」という用語は、受信側がまだ確認応答していないパケットの総数の論理的な境界を表します。受信側は、各確認応答パケットにおいて、現在の最大受信バッファサイズ（ウィンドウ境界）を送信側に通知します。TCPヘッダーは、16ビットのフィールドを使用して受信側のウィンドウサイズを送信側に通知します。したがって、使用可能な最大ウィンドウは2の16乗= 64キロバイトです。
スロースタートモードでは、送信側は低いパケット数から開始し、受信側から確認応答パケットを受信すると、送信ごとにパケット数を増やしていきます。ACKパケットを受信するたびに、ウィンドウが（論理的に）1パケットずつスライドし、新しいパケットを1つ送信します。ウィンドウのしきい値に達すると、送信側はACKパケットを受信するたびに1パケットを送信します。
ウィンドウ制限が10パケットの場合、スロースタートモードでは、送信側は1パケットの送信を開始し、続いて2パケットの送信（2パケットの送信前に1パケットのACKを受信する必要がある）、さらに3パケットの送信と、10パケットまで送信を続けることができます。ただし、10パケットに達した後は、1つのACKパケットを受信するごとに1パケットの送信に制限されます。シミュレーションでは、これはウィンドウがACKパケットを受信するたびに1パケット分移動しているように見えます。受信側では、ウィンドウはパケットを受信するたびに1パケット分移動します。
スライディングウィンドウ方式は、ネットワーク上のトラフィック輻輳を回避します。送信側と受信側のTCPはパケットバッファのスライディングウィンドウを実装しているため、アプリケーション層はネットワークトラフィックの輻輳を気にすることなく、TCPにデータを送信できます。ウィンドウサイズはネットワークトラフィックに応じて動的に変化します。
スループットを最大限に高めるには、スライディングウィンドウプロトコルによって送信側が1往復遅延時間（RTT）より早く送信を停止させられないようにすることが重要です。確認応答を待つために停止するまでに送信できるデータ量の制限は、通信リンクの帯域幅遅延積よりも大きくする必要があります。そうでない場合、プロトコルはリンクの 実効帯域幅を制限してしまいます。
動機
誤り制御のための自動再送要求に基づくあらゆる通信プロトコルでは、受信側は受信したパケットに確認応答しなければなりません。送信側が妥当な時間内に確認応答を受信しない場合、データを再送信します
確認応答を受け取らない送信機は、受信機が実際にパケットを受信したかどうかを知ることができません。そのため、パケットが伝送中に失われたか破損した可能性があります。エラー検出メカニズムによって破損が明らかになった場合、受信機はそのパケットを無視し、否定応答または重複した確認応答を送信します。受信機が確認応答をまったく送信しないように設定されている場合もあります。同様に、受信機は通常、確認応答が受信されたかどうかについて確信がありません。確認応答は送信されたものの、伝送媒体で失われたか破損した可能性があります。この場合、受信機は、データが継続的に再送されるのを防ぐために再送を確認する必要があり、そうでない場合はデータを無視する必要があります。
プロトコル操作
送信機と受信機はそれぞれ現在のシーケンス番号ntとnrを持ちます。また、それぞれウィンドウサイズwtとwrを持ちます。ウィンドウサイズは変化する可能性がありますが、より単純な実装では固定されています。処理を進めるには、ウィンドウサイズが0より大きくなければなり ません
典型的な実装では、n tは次に送信するパケット、つまりまだ送信されていない最初のパケットのシーケンス番号です。同様に、n rは未受信の最初のパケットです。どちらの数値も時間とともに単調に増加し、常に増加し続けます。
受信側は、これまで受信した最大シーケンス番号も記録している場合があります。変数n s は、受信したパケットの最大シーケンス番号より1大きい値です。この値はn sを最大w r −1 だけ超える可能性があるため、パケットを順番にしか受信しない単純な受信側（w r = 1）の場合、これはn rと同じになります。違いに注意してください。n r より前のパケットはすべて受信済みであり、n sより後のパケットは受信されていません。また、 n rとn sの間には、いくつかのパケットが受信されています。したがって、n r ≤ n s ≤ n tとなります。
受信側はパケットを受信すると、変数を適切に更新し、新しいn rで確認応答を送信します。送信側は、受信した最大の確認応答n aを記録します。送信側は、 n aまでのパケット（ただしn aは含まない）を受信したことを認識しますが、 n aからn tまでの間のパケット（つまりn a ≤ n r ≤ n t ）については不明です。
シーケンス番号は常にn a ≤ n r ≤ n s ≤ n t ≤ n a + w tという規則に従います。つまり、
- n a ≤ 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 tは送信回数に応じて増加される。
通信エラーがない場合、送信機はすぐに送信したすべてのパケットに対する確認応答を受信し、n aはn tと等しくなります。妥当な遅延が経過しても確認応答を受信しない場合、送信機はn a番のパケットを再送信する必要があります。
「合理的な遅延」を定義する手法は非常に複雑になりがちですが、それらは効率性にのみ影響し、スライディングウィンドウプロトコルの基本的な信頼性は、その詳細には左右されません。同様に、送信側はn aとn tの間に追加のパケットを再送信することを選択する場合もありますが、この決定はプロトコルの正確性には影響しません。
受信側の操作
番号xのパケットを受信するたびに、受信側はそれが受信ウィンドウ（n r ≤ x < n r + w r ）内にあるかどうかを確認します。（最も単純な受信側ではw r = 1であり、1つの可能性のみを受け入れます。）ウィンドウ内に収まる場合、受信側はそれを受け入れます。番号が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である限り、送信機は確認応答シーケンス番号を一意にデコードできます。
受信側によってより強い制約が課される。プロトコルの動作は、受信側が新しいパケット（受信・処理されるべき）と古いパケットの再送（破棄され、最後の確認応答が再送されるべき）を確実に区別できるかどうかに依存する。これは、送信側のウィンドウサイズから送信側のn aを推測することで可能となる。番号xのパケットを受信した後、受信側はx < n t ≤ n a + w t、つまりn a > x − w tであることを認識している。したがって、番号x − w t以下のパケットは再送されない。
将来私たちが受け取る最小のシーケンス番号はn s − w tである。
受信側は、送信側のn aがこれまで送信された最大の確認応答（n r ）よりも大きくなることはないことも知っています。したがって、シーケンス番号n a + w t ≤ n r + 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ビットのシーケンス番号を使用し、オプションで選択的繰り返し機能を備えています。ただし、選択的繰り返し機能を使用する場合は、w t + w 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の制限値内であれば、通信中に変更できます。通常、送信ウィンドウサイズと受信ウィンドウサイズにはそれぞれ、その制限値を満たす最大値が割り当てられますが、特定の時点での動作値は最大値よりも小さくなる場合があります。具体的には、
参照
参考文献
- ^ピーターソン, ラリー・L. ;デイヴィー, ブルース・S. (2000).コンピュータネットワーク：システムアプローチ. モーガン・カウフマン. ISBN 1-55860-577-0。
- ダグラス・E・コーマー著『TCP/IPによるインターネットワーキング 第1巻：原理、プロトコル、アーキテクチャ』、プレンティス・ホール、1995年。ISBN 0-13-216987-8
外部リンク
- RFC 1323 - 高性能のためのTCP拡張
- TCPウィンドウスケーリングと壊れたルータ、2004年
