[要約] RFC 6937は、TCPのための比例減少制御（PRR）アルゴリズムに関するものであり、輻輳制御の改善を目的としています。PRRは、パケットロスの原因を特定し、適切な速度で送信速度を減少させることで、ネットワークの効率を向上させます。
Internet Engineering Task Force (IETF) M. Mathis
Request for Comments: 6937 N. Dukkipati
Category: Experimental Y. Cheng
ISSN: 2070-1721 Google, Inc.
May 2013
Proportional Rate Reduction for TCP
TCPの比例レート削減
Abstract
概要
This document describes an experimental Proportional Rate Reduction (PRR) algorithm as an alternative to the widely deployed Fast Recovery and Rate-Halving algorithms. These algorithms determine the amount of data sent by TCP during loss recovery. PRR minimizes excess window adjustments, and the actual window size at the end of recovery will be as close as possible to the ssthresh, as determined by the congestion control algorithm.
このドキュメントでは、広く展開されている高速復旧アルゴリズムとレート半減アルゴリズムの代替として、実験的な比例レート削減（PRR）アルゴリズムについて説明します。これらのアルゴリズムは、損失回復中にTCPによって送信されるデータの量を決定します。 PRRは過剰なウィンドウ調整を最小限に抑え、回復の最後の実際のウィンドウサイズは、輻輳制御アルゴリズムによって決定されるssthreshに可能な限り近くなります。
Status of This Memo
本文書の状態
This document is not an Internet Standards Track specification; it is published for examination, experimental implementation, and evaluation.
このドキュメントはInternet Standards Trackの仕様ではありません。試験、実験、評価のために公開されています。
This document defines an Experimental Protocol for the Internet community. This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Not all documents approved by the IESG are a candidate for any level of Internet Standard; see Section 2 of RFC 5741.
このドキュメントでは、インターネットコミュニティの実験プロトコルを定義します。このドキュメントは、IETF（Internet Engineering Task Force）の製品です。これは、IETFコミュニティのコンセンサスを表しています。公開レビューを受け、インターネットエンジニアリングステアリンググループ（IESG）による公開が承認されました。 IESGによって承認されたすべてのドキュメントが、あらゆるレベルのインターネット標準の候補になるわけではありません。 RFC 5741のセクション2をご覧ください。
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6937.
このドキュメントの現在のステータス、エラータ、およびフィードバックの提供方法に関する情報は、http：//www.rfc-editor.org/info/rfc6937で入手できます。
Copyright Notice
著作権表示
Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved.
Copyright（c）2013 IETF Trustおよびドキュメントの作成者として識別された人物。全著作権所有。
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
この文書は、BCP 78およびこの文書の発行日に有効なIETF文書に関するIETFトラストの法的規定（http://trustee.ietf.org/license-info）の対象となります。これらのドキュメントは、このドキュメントに関するあなたの権利と制限を説明しているため、注意深く確認してください。このドキュメントから抽出されたコードコンポーネントには、Trust Legal Provisionsのセクション4.eに記載されているSimplified BSD Licenseのテキストが含まれている必要があり、Simplified BSD Licenseに記載されているように保証なしで提供されます。
Table of Contents
目次
1. Introduction ....................................................2
2. Definitions .....................................................5
3. Algorithms ......................................................6
3.1. Examples ...................................................6
4. Properties ......................................................9
5. Measurements ...................................................11
6. Conclusion and Recommendations .................................12
7. Acknowledgements ...............................................13
8. Security Considerations ........................................13
9. References .....................................................13
9.1. Normative References ......................................13
9.2. Informative References ....................................14
Appendix A. Strong Packet Conservation Bound ......................15
This document describes an experimental algorithm, PRR, to improve the accuracy of the amount of data sent by TCP during loss recovery.
このドキュメントでは、損失回復中にTCPによって送信されるデータ量の精度を向上させるための実験的アルゴリズムPRRについて説明します。
Standard congestion control [RFC5681] requires that TCP (and other protocols) reduce their congestion window (cwnd) in response to losses. Fast Recovery, described in the same document, is the reference algorithm for making this adjustment. Its stated goal is to recover TCP's self clock by relying on returning ACKs during recovery to clock more data into the network. Fast Recovery typically adjusts the window by waiting for one half round-trip time (RTT) of ACKs to pass before sending any data. It is fragile because it cannot compensate for the implicit window reduction caused by the losses themselves.
標準の輻輳制御[RFC5681]では、TCP（および他のプロトコル）が、損失に応じて輻輳ウィンドウ（cwnd）を減らす必要があります。同じドキュメントで説明されているFast Recoveryは、この調整を行うための参照アルゴリズムです。その明言された目標は、ネットワーク内により多くのデータを記録するために回復中にACKを返すことに依存することにより、TCPの自己クロックを回復することです。 Fast Recoveryは通常、データを送信する前に、ACKのラウンドトリップ時間（RTT）の半分が経過するのを待つことでウィンドウを調整します。損失自体によって引き起こされる暗黙的なウィンドウの縮小を補償できないため、脆弱です。
RFC 6675 [RFC6675] makes Fast Recovery with Selective Acknowledgement (SACK) [RFC2018] more accurate by computing "pipe", a sender side estimate of the number of bytes still outstanding in the network. With RFC 6675, Fast Recovery is implemented by sending data as necessary on each ACK to prevent pipe from falling below slow-start threshold (ssthresh), the window size as determined by the congestion control algorithm. This protects Fast Recovery from timeouts in many cases where there are heavy losses, although not if the entire second half of the window of data or ACKs are lost. However, a single ACK carrying a SACK option that implies a large quantity of missing data can cause a step discontinuity in the pipe estimator, which can cause Fast Retransmit to send a burst of data.
RFC 6675 [RFC6675]は、ネットワークで未解決のバイト数の送信側の推定である「パイプ」を計算することにより、選択的確認応答（SACK）[RFC2018]による高速リカバリをより正確にします。 RFC 6675では、パイプがスロースタートしきい値（ssthresh）（輻輳制御アルゴリズムによって決定されるウィンドウサイズ）を下回らないように、必要に応じて各ACKでデータを送信することにより、高速復旧が実装されます。これにより、データまたはACKのウィンドウの後半全体が失われたとしても、大きな損失がある多くの場合、タイムアウトからファストリカバリが保護されます。ただし、大量の欠落データを意味するSACKオプションを運ぶ単一のACKは、パイプ推定器でステップの不連続を引き起こし、高速再送信でデータのバーストを送信する可能性があります。
The Rate-Halving algorithm sends data on alternate ACKs during recovery, such that after 1 RTT the window has been halved. Rate-Halving is implemented in Linux after only being informally published [RHweb], including an uncompleted document [RHID]. Rate-Halving also does not adequately compensate for the implicit window reduction caused by the losses and assumes a net 50% window reduction, which was completely standard at the time it was written but not appropriate for modern congestion control algorithms, such as CUBIC [CUBIC], which reduce the window by less than 50%. As a consequence, Rate-Halving often allows the window to fall further than necessary, reducing performance and increasing the risk of timeouts if there are additional losses.
レート半減アルゴリズムは、回復中に代替ACKでデータを送信します。そのため、1 RTTの後でウィンドウが半減されます。 Rate-Halvingは、未完成のドキュメント[RHID]を含め、非公式に公開された[RHweb]の後でのみLinuxに実装されます。レート半減はまた、損失によって引き起こされる暗黙的なウィンドウ削減を適切に補償せず、正味の50％ウィンドウ削減を想定しています。これは、作成時に完全に標準でしたが、CUBIC [CUBIC]などの最新の輻輳制御アルゴリズムには適していません。 ]、ウィンドウを50％未満縮小します。その結果、レート半減によりウィンドウが必要以上に下がることがよくあり、パフォーマンスが低下し、追加の損失がある場合はタイムアウトのリスクが高まります。
PRR avoids these excess window adjustments such that at the end of recovery the actual window size will be as close as possible to ssthresh, the window size as determined by the congestion control algorithm. It is patterned after Rate-Halving, but using the fraction that is appropriate for the target window chosen by the congestion control algorithm. During PRR, one of two additional Reduction Bound algorithms limits the total window reduction due to all mechanisms, including transient application stalls and the losses themselves.
PRRは、これらの過剰なウィンドウ調整を回避して、リカバリーの最後に、実際のウィンドウサイズがssthresh（輻輳制御アルゴリズムによって決定されるウィンドウサイズ）に可能な限り近くなるようにします。レートハービングの後にパターン化されますが、輻輳制御アルゴリズムによって選択されたターゲットウィンドウに適した割合を使用します。 PRR中、2つの追加のリダクションバウンドアルゴリズムの1つが、一時的なアプリケーションのストールや損失自体を含むすべてのメカニズムによるウィンドウの総リダクションを制限します。
We describe two slightly different Reduction Bound algorithms: Conservative Reduction Bound (CRB), which is strictly packet conserving; and a Slow Start Reduction Bound (SSRB), which is more aggressive than CRB by, at most, 1 segment per ACK. PRR-CRB meets the Strong Packet Conservation Bound described in Appendix A; however, in real networks it does not perform as well as the algorithms described in RFC 6675, which prove to be more aggressive in a significant number of cases. SSRB offers a compromise by allowing TCP to send 1 additional segment per ACK relative to CRB in some situations. Although SSRB is less aggressive than RFC 6675 (transmitting fewer segments or taking more time to transmit them), it outperforms it, due to the lower probability of additional losses during recovery.
2つのわずかに異なるリダクションバウンドアルゴリズムについて説明します。コンサバティブリダクションバウンド（CRB）は、厳密にパケットを保存します。スロースタートリダクションバウンド（SSRB）。これは、CRBよりも最大でACKあたり1セグメントだけアグレッシブです。 PRR-CRBは、付録Aで説明されている強力なパケット保護限界を満たしています。ただし、実際のネットワークでは、RFC 6675で説明されているアルゴリズムほどには機能しません。RFC6675は、非常に多くのケースでより攻撃的であることが証明されています。 SSRBは、状況によっては、TCPがCRBに比べてACKごとに1つの追加セグメントを送信できるようにすることで妥協点を提供します。 SSRBはRFC 6675よりも攻撃的ではありませんが（送信するセグメント数が少ないか、送信に時間がかかる）、リカバリ中に追加の損失が発生する可能性が低いため、パフォーマンスが優れています。
The Strong Packet Conservation Bound on which PRR and both Reduction Bounds are based is patterned after Van Jacobson's packet conservation principle: segments delivered to the receiver are used as the clock to trigger sending the same number of segments back into the network. As much as possible, PRR and the Reduction Bound algorithms rely on this self clock process, and are only slightly affected by the accuracy of other estimators, such as pipe [RFC6675] and cwnd. This is what gives the algorithms their precision in the presence of events that cause uncertainty in other estimators.
PRRと両方のリダクションバウンドの基礎となる強力なパケット保護の境界は、Van Jacobsonのパケット保護の原則に基づいてパターン化されています。可能な限り、PRRおよびリダクションバインドアルゴリズムはこのセルフクロックプロセスに依存しており、パイプ[RFC6675]やcwndなどの他の推定量の精度による影響はわずかです。これは、他の推定量に不確実性を引き起こすイベントが存在する場合にアルゴリズムに精度を与えるものです。
The original definition of the packet conservation principle [Jacobson88] treated packets that are presumed to be lost (e.g., marked as candidates for retransmission) as having left the network. This idea is reflected in the pipe estimator defined in RFC 6675 and used here, but it is distinct from the Strong Packet Conservation Bound as described in Appendix A, which is defined solely on the basis of data arriving at the receiver.
パケット保存の原則[Jacobson88]の元の定義では、失われたと推定される（たとえば、再送信の候補としてマークされている）パケットを、ネットワークを離れたものとして扱いました。このアイデアは、RFC 6675で定義され、ここで使用されているパイプエスティメータに反映されていますが、付録Aで説明されている強力なパケット保護境界とは異なります。
We evaluated these and other algorithms in a large scale measurement study presented in a companion paper [IMC11] and summarized in Section 5. This measurement study was based on RFC 3517 [RFC3517], which has since been superseded by RFC 6675. Since there are slight differences between the two specifications, and we were meticulous about our implementation of RFC 3517, we are not comfortable unconditionally asserting that our measurement results apply to RFC 6675, although we believe this to be the case. We have instead chosen to be pedantic about describing measurement results relative to RFC 3517, on which they were actually based. General discussions of algorithms and their properties have been updated to refer to RFC 6675.
コンパニオンペーパー[IMC11]で提示され、セクション5にまとめられている大規模測定研究で、これらのアルゴリズムと他のアルゴリズムを評価しました。この測定研究は、RFC 3517 [RFC3517]に基づいており、RFC 6675に置き換えられています。 2つの仕様のわずかな違い、およびRFC 3517の実装に細心の注意を払っていたため、測定結果がRFC 6675に適用されると無条件に断言するのは快適ではありません。代わりに、RFC 3517に関連する測定結果を説明することについて、知識を深めることを選択しました。アルゴリズムとそのプロパティの一般的な説明は、RFC 6675を参照するように更新されました。
We found that for authentic network traffic, PRR-SSRB outperforms both RFC 3517 and Linux Rate-Halving even though it is less aggressive than RFC 3517. We believe that these results apply to RFC 6675 as well.
本格的なネットワークトラフィックの場合、PRR-SSRBはRFC 3517よりも攻撃的ではありませんが、RFC 3517とLinux Rate-Halvingの両方を上回っています。これらの結果はRFC 6675にも適用されると考えています。
The algorithms are described as modifications to RFC 5681 [RFC5681], "TCP Congestion Control", using concepts drawn from the pipe algorithm [RFC6675]. They are most accurate and more easily implemented with SACK [RFC2018], but do not require SACK.
アルゴリズムは、パイプアルゴリズム[RFC6675]から引き出された概念を使用して、RFC 5681 [RFC5681]、「TCP輻輳制御」への変更として説明されています。これらは最も正確で、SACK [RFC2018]でより簡単に実装できますが、SACKは必要ありません。
The following terms, parameters, and state variables are used as they are defined in earlier documents:
以下の用語、パラメーター、および状態変数は、以前のドキュメントで定義されているとおりに使用されます。
RFC 793: snd.una (send unacknowledged)
RFC 793：snd.una（未確認で送信）
RFC 5681: duplicate ACK, FlightSize, Sender Maximum Segment Size (SMSS)
RFC 5681：ACK、FlightSize、Sender Maximum Segment Size（SMSS）の重複
RFC 6675: covered (as in "covered sequence numbers")
RFC 6675：対象（「対象シーケンス番号」の場合と同様）
Voluntary window reductions: choosing not to send data in response to some ACKs, for the purpose of reducing the sending window size and data rate
自発的なウィンドウの削減：送信ウィンドウのサイズとデータレートを削減する目的で、一部のACKに応答してデータを送信しないことの選択
We define some additional variables:
追加の変数をいくつか定義します。
SACKd: The total number of bytes that the scoreboard indicates have been delivered to the receiver. This can be computed by scanning the scoreboard and counting the total number of bytes covered by all SACK blocks. If SACK is not in use, SACKd is not defined.
SACKd：スコアボードが受信者に配信したことを示す合計バイト数。これは、スコアボードをスキャンして、すべてのSACKブロックがカバーする合計バイト数をカウントすることで計算できます。 SACKが使用されていない場合、SACKdは定義されません。
DeliveredData: The total number of bytes that the current ACK indicates have been delivered to the receiver. When not in recovery, DeliveredData is the change in snd.una. With SACK, DeliveredData can be computed precisely as the change in snd.una, plus the (signed) change in SACKd. In recovery without SACK, DeliveredData is estimated to be 1 SMSS on duplicate acknowledgements, and on a subsequent partial or full ACK, DeliveredData is estimated to be the change in snd.una, minus 1 SMSS for each preceding duplicate ACK.
DeliveredData：現在のACKが受信者に配信したことを示す合計バイト数。リカバリ中でない場合、DeliveredDataはsnd.unaの変更です。 SACKを使用すると、snd.unaの変更とSACKdの（符号付き）変更に加えて、DeliveredDataを正確に計算できます。 SACKを使用しないリカバリでは、DeliveredDataは重複する確認応答で1 SMSSであると推定され、後続の部分的または完全なACKでは、DeliveredDataはsnd.unaの変化から先行する各重複ACKの1 SMSSを引いたものであると推定されます。
Note that DeliveredData is robust; for TCP using SACK, DeliveredData can be precisely computed anywhere in the network just by inspecting the returning ACKs. The consequence of missing ACKs is that later ACKs will show a larger DeliveredData. Furthermore, for any TCP (with or without SACK), the sum of DeliveredData must agree with the forward progress over the same time interval.
DeliveredDataは堅牢であることに注意してください。 SACKを使用するTCPの場合、DeliveredDataは、返されるACKを検査するだけで、ネットワークの任意の場所で正確に計算できます。欠落したACKの結果として、後のACKはより大きなDeliveredDataを表示します。さらに、TCPの場合（SACKの有無にかかわらず）、DeliveredDataの合計は、同じ時間間隔でのフォワードプログレスと一致する必要があります。
We introduce a local variable "sndcnt", which indicates exactly how many bytes should be sent in response to each ACK. Note that the decision of which data to send (e.g., retransmit missing data or send more new data) is out of scope for this document.
ローカル変数「sndcnt」を導入します。これは、各ACKに応答して送信する必要があるバイト数を正確に示します。送信するデータの決定（たとえば、欠落しているデータの再送信や新しいデータの送信など）は、このドキュメントの範囲外であることに注意してください。
At the beginning of recovery, initialize PRR state. This assumes a modern congestion control algorithm, CongCtrlAlg(), that might set ssthresh to something other than FlightSize/2:
リカバリの開始時に、PRR状態を初期化します。これは、ssthreshをFlightSize / 2以外に設定する可能性がある最新の輻輳制御アルゴリズムであるCongCtrlAlg()を想定しています。
ssthresh = CongCtrlAlg() // Target cwnd after recovery
prr_delivered = 0 // Total bytes delivered during recovery
prr_out = 0 // Total bytes sent during recovery
RecoverFS = snd.nxt-snd.una // FlightSize at the start of recovery
On every ACK during recovery compute:
回復計算中のすべてのACKで：
DeliveredData = change_in(snd.una) + change_in(SACKd)
prr_delivered += DeliveredData
pipe = (RFC 6675 pipe algorithm)
if (pipe > ssthresh) {
// Proportional Rate Reduction
sndcnt = CEIL(prr_delivered * ssthresh / RecoverFS) - prr_out
} else {
// Two versions of the Reduction Bound
if (conservative) { // PRR-CRB
limit = prr_delivered - prr_out
} else { // PRR-SSRB
limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS
}
// Attempt to catch up, as permitted by limit
sndcnt = MIN(ssthresh - pipe, limit)
}
On any data transmission or retransmission:
データの送信または再送信：
prr_out += (data sent) // strictly less than or equal to sndcnt
We illustrate these algorithms by showing their different behaviors for two scenarios: TCP experiencing either a single loss or a burst of 15 consecutive losses. In all cases we assume bulk data (no application pauses), standard Additive Increase Multiplicative Decrease (AIMD) congestion control, and cwnd = FlightSize = pipe = 20 segments, so ssthresh will be set to 10 at the beginning of recovery. We also assume standard Fast Retransmit and Limited Transmit [RFC3042], so TCP will send 2 new segments followed by 1 retransmit in response to the first 3 duplicate ACKs following the losses.
これらのアルゴリズムを説明するために、2つのシナリオの異なる動作を示します。TCPで単一の損失または15回の連続した損失のバーストが発生しています。すべてのケースで、バルクデータ（アプリケーションの一時停止なし）、標準の加法乗法減数（AIMD）輻輳制御、およびcwnd = FlightSize = pipe = 20セグメントを想定しているため、リカバリの開始時にssthreshは10に設定されます。また、標準の高速再送信と制限付き送信[RFC3042]も想定しているため、TCPは2つの新しいセグメントを送信し、その後、損失に続く最初の3つの重複ACKに応答して1つの再送信を送信します。
Each of the diagrams below shows the per ACK response to the first round trip for the various recovery algorithms when the zeroth segment is lost. The top line indicates the transmitted segment number triggering the ACKs, with an X for the lost segment. "cwnd" and "pipe" indicate the values of these algorithms after processing each returning ACK. "Sent" indicates how much 'N'ew or 'R'etransmitted data would be sent. Note that the algorithms for deciding which data to send are out of scope of this document.
以下の各図は、0番目のセグメントが失われた場合のさまざまな回復アルゴリズムの最初のラウンドトリップに対するACKごとの応答を示しています。一番上の行は、ACKをトリガーする送信セグメント番号を示し、失われたセグメントをXで示します。 "cwnd"と "pipe"は、返される各ACKを処理した後のこれらのアルゴリズムの値を示します。 「送信済み」は、「N'ew」または「R」で送信されたデータの量を示します。送信するデータを決定するアルゴリズムは、このドキュメントの範囲外であることに注意してください。
When there is a single loss, PRR with either of the Reduction Bound algorithms has the same behavior. We show "RB", a flag indicating which Reduction Bound subexpression ultimately determined the value of sndcnt. When there are minimal losses, "limit" (both algorithms) will always be larger than ssthresh - pipe, so the sndcnt will be ssthresh - pipe, indicated by "s" in the "RB" row.
単一の損失がある場合、いずれかの縮約バインドアルゴリズムを使用したPRRは同じ動作をします。最終的にsndcntの値を決定したリダクションバインド部分式を示すフラグ「RB」を表示します。損失が最小の場合、「制限」（両方のアルゴリズム）は常にssthresh-pipeよりも大きくなるため、sndcntはssthresh-pipeとなり、「RB」行の「s」で示されます。
RFC 6675 ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 cwnd: 20 20 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 pipe: 19 19 18 18 17 16 15 14 13 12 11 10 10 10 10 10 10 10 10 sent: N N R N N N N N N N N
RFC 6675 ack＃X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 cwnd：20 20 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11パイプ：19 19 18 18 17 16 15 14 13 12 11 10 10 10 10 10 10 10 10送信：NNRNNNNNNNN
Rate-Halving (Linux) ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 cwnd: 20 20 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11 pipe: 19 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11 10 sent: N N R N N N N N N N N
レート半減（Linux）ack＃X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 cwnd：20 20 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11パイプ：19 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11 10送信：NNRNNNNNNNN
PRR ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 pipe: 19 19 18 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 10 sent: N N R N N N N N N N N RB: s s
PRR ack＃X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19パイプ：19 19 18 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 10送信：N N R N N N N N N N N RB：s s
Cwnd is not shown because PRR does not use it.
CRRはCwndを使用しないため、Cwndは表示されません。
Key for RB s: sndcnt = ssthresh - pipe // from ssthresh b: sndcnt = prr_delivered - prr_out + SMSS // from banked d: sndcnt = DeliveredData + SMSS // from DeliveredData (Sometimes, more than one applies.)
RBのキーs：sndcnt = ssthresh-pipe // ssthreshからb：sndcnt = prr_delivered-prr_out + SMSS //バンクからd：sndcnt = DeliveredData + SMSS // DeliveredDataから（場合によっては、複数適用される）
Note that all 3 algorithms send the same total amount of data. RFC 6675 experiences a "half window of silence", while the Rate-Halving and PRR spread the voluntary window reduction across an entire RTT.
3つのアルゴリズムすべてが同じ合計量のデータを送信することに注意してください。 RFC 6675では「沈黙の半分の時間枠」が発生しますが、Rate-HalvingおよびPRRは任意のウィンドウ削減をRTT全体に分散します。
Next, we consider the same initial conditions when the first 15 packets (0-14) are lost. During the remainder of the lossy RTT, only 5 ACKs are returned to the sender. We examine each of these algorithms in succession.
次に、最初の15個のパケット（0-14）が失われたときの同じ初期条件を検討します。非可逆RTTの残りの期間中、送信者に返されるACKは5つだけです。これらの各アルゴリズムを続けて調べます。
RFC 6675 ack# X X X X X X X X X X X X X X X 15 16 17 18 19 cwnd: 20 20 11 11 11 pipe: 19 19 4 10 10 sent: N N 7R R R
RFC 6675 ack＃X X X X X X X X X X X X X X X 15 16 17 18 19 cwnd：20 20 11 11 11 pipe：19 19 4 10 10 sent：N N 7R R R
Rate-Halving (Linux) ack# X X X X X X X X X X X X X X X 15 16 17 18 19 cwnd: 20 20 5 5 5 pipe: 19 19 4 4 4 sent: N N R R R
レート半減（Linux）ack＃X X X X X X X X X X X X X X X 15 16 17 18 19 cwnd：20 20 5 5 5 pipe：19 19 4 4 4 sent：N N R R R
PRR-CRB ack# X X X X X X X X X X X X X X X 15 16 17 18 19 pipe: 19 19 4 4 4 sent: N N R R R RB: b b b
PRR-CRB ack＃X X X X X X X X X X X X X X X 15 16 17 18 19パイプ：19 19 4 4 4送信：N N R R R RB：b b b
PRR-SSRB ack# X X X X X X X X X X X X X X X 15 16 17 18 19 pipe: 19 19 4 5 6 sent: N N 2R 2R 2R RB: bd d d
PRR-SSRB ack＃X X X X X X X X X X X X X X X 15 16 17 18 19パイプ：19 19 4 5 6送信：N N 2R 2R 2R RB：bd d d
In this specific situation, RFC 6675 is more aggressive because once Fast Retransmit is triggered (on the ACK for segment 17), TCP immediately retransmits sufficient data to bring pipe up to cwnd. Our measurement data (see Section 5) indicates that RFC 6675 significantly outperforms Rate-Halving, PRR-CRB, and some other similarly conservative algorithms that we tested, showing that it is significantly common for the actual losses to exceed the window reduction determined by the congestion control algorithm.
この特定の状況では、（セグメント17のACKで）高速再送信がトリガーされると、TCPはすぐに十分なデータを再送信してパイプをcwndに送信するため、RFC 6675はより積極的です。私たちの測定データ（セクション5を参照）は、RFC 6675がレート半減、PRR-CRB、および私たちがテストした他の同様の保守的なアルゴリズムを大幅に上回っていることを示しており、実際の損失は、輻輳制御アルゴリズム。
The Linux implementation of Rate-Halving includes an early version of the Conservative Reduction Bound [RHweb]. In this situation, the 5 ACKs trigger exactly 1 transmission each (2 new data, 3 old data), and cwnd is set to 5. At a window size of 5, it takes 3 round trips to retransmit all 15 lost segments. Rate-Halving does not raise the window at all during recovery, so when recovery finally completes, TCP will slow start cwnd from 5 up to 10. In this example, TCP operates at half of the window chosen by the congestion control for more than 3 RTTs, increasing the elapsed time and exposing it to timeouts in the event that there are additional losses.
LinuxのRate-Halvingの実装には、保守的削減限界[RHweb]の初期バージョンが含まれています。この状況では、5つのACKがそれぞれ1つの送信（2つの新しいデータ、3つの古いデータ）をトリガーし、cwndは5に設定されます。ウィンドウサイズが5の場合、失われた15のセグメントすべてを再送信するには3往復かかります。レート半減は回復中にウィンドウをまったく上げないため、回復が最終的に完了すると、TCPはcwndの開始を5から10まで遅くします。この例では、TCPは輻輳制御によって選択されたウィンドウの半分で動作し、3を超えます。 RTT、経過時間を増やし、追加の損失がある場合はタイムアウトにさらします。
PRR-CRB implements a Conservative Reduction Bound. Since the total losses bring pipe below ssthresh, data is sent such that the total data transmitted, prr_out, follows the total data delivered to the receiver as reported by returning ACKs. Transmission is controlled by the sending limit, which is set to prr_delivered - prr_out. This is indicated by the RB:b tagging in the figure. In this case, PRR-CRB is exposed to exactly the same problems as Rate-Halving; the excess window reduction causes it to take excessively long to recover the losses and exposes it to additional timeouts.
PRR-CRBは保守的な削減限界を実装します。総損失によりパイプがssthreshを下回るので、送信された総データprr_outが、ACKを返すことによって報告されたレシーバーに配信された総データに従うようにデータが送信されます。送信は、prr_delivered-prr_outに設定されている送信制限によって制御されます。これは、図のRB：bタグで示されています。この場合、PRR-CRBはレート半減とまったく同じ問題にさらされます。過剰なウィンドウの削減により、損失を回復するのに非常に長い時間がかかり、追加のタイムアウトにさらされます。
PRR-SSRB increases the window by exactly 1 segment per ACK until pipe rises to ssthresh during recovery. This is accomplished by setting limit to one greater than the data reported to have been delivered to the receiver on this ACK, implementing slow start during recovery, and indicated by RB:d tagging in the figure. Although increasing the window during recovery seems to be ill advised, it is important to remember that this is actually less aggressive than permitted by RFC 5681, which sends the same quantity of additional data as a single burst in response to the ACK that triggered Fast Retransmit.
PRR-SSRBは、回復中にパイプがssthreshに上昇するまで、ACKごとにウィンドウを1セグメントずつ増やします。これは、このACKでレシーバーに配信されたと報告されたデータよりも1大きい制限を設定し、回復中にスロースタートを実装し、図のRB：dタギングで示されることによって達成されます。リカバリ中にウィンドウを増やすことはお勧めできないようですが、これは実際にはRFC 5681で許可されているよりも攻撃的ではないことを覚えておくことが重要です。RFC5681は、高速再送信をトリガーしたACKに応答して単一のバーストと同じ量の追加データを送信します。
For less extreme events, where the total losses are smaller than the difference between FlightSize and ssthresh, PRR-CRB and PRR-SSRB have identical behaviors.
総損失がFlightSizeとssthreshの差よりも小さい極端でないイベントの場合、PRR-CRBとPRR-SSRBの動作は同じです。
The following properties are common to both PRR-CRB and PRR-SSRB, except as noted:
次のプロパティは、注記がない限り、PRR-CRBとPRR-SSRBの両方に共通です。
PRR maintains TCP's ACK clocking across most recovery events, including burst losses. RFC 6675 can send large unclocked bursts following burst losses.
PRRは、バースト損失を含むほとんどの回復イベントにわたってTCPのACKクロッキングを維持します。 RFC 6675は、バースト損失に続いて、クロックされていない大きなバーストを送信できます。
Normally, PRR will spread voluntary window reductions out evenly across a full RTT. This has the potential to generally reduce the burstiness of Internet traffic, and could be considered to be a type of soft pacing. Hypothetically, any pacing increases the probability that different flows are interleaved, reducing the opportunity for ACK compression and other phenomena that increase traffic burstiness. However, these effects have not been quantified.
通常、PRRは自発的なウィンドウ削減を完全なRTT全体に均等に分散します。これは一般にインターネットトラフィックのバースト性を低減する可能性があり、一種のソフトペーシングと見なすことができます。仮説上、どのペーシングでも、異なるフローがインターリーブされる可能性が高くなり、ACK圧縮やトラフィックのバースト性を増加させる他の現象の機会が減少します。ただし、これらの効果は定量化されていません。
If there are minimal losses, PRR will converge to exactly the target window chosen by the congestion control algorithm. Note that as TCP approaches the end of recovery, prr_delivered will approach RecoverFS and sndcnt will be computed such that prr_out approaches ssthresh.
損失が最小限の場合、PRRは輻輳制御アルゴリズムによって選択されたターゲットウィンドウに正確に収束します。 TCPが回復の終わりに近づくと、prr_deliveredはRecoverFSに近づき、sndcntはprr_outがssthreshに近づくように計算されることに注意してください。
Implicit window reductions, due to multiple isolated losses during recovery, cause later voluntary reductions to be skipped. For small numbers of losses, the window size ends at exactly the window chosen by the congestion control algorithm.
リカバリ中の複数の孤立した損失による暗黙的なウィンドウの削減により、その後の自発的な削減がスキップされます。損失が少ない場合、ウィンドウサイズは、輻輳制御アルゴリズムによって選択されたウィンドウで終了します。
For burst losses, earlier voluntary window reductions can be undone by sending extra segments in response to ACKs arriving later during recovery. Note that as long as some voluntary window reductions are not undone, the final value for pipe will be the same as ssthresh, the target cwnd value chosen by the congestion control algorithm.
バースト損失の場合、リカバリ中に後で到着するACKに応答して追加のセグメントを送信することにより、以前の自発的なウィンドウ削減を元に戻すことができます。一部の自発的なウィンドウ削減が元に戻されない限り、パイプの最終値は、輻輳制御アルゴリズムによって選択されたターゲットcwnd値であるssthreshと同じになることに注意してください。
PRR with either Reduction Bound improves the situation when there are application stalls, e.g., when the sending application does not queue data for transmission quickly enough or the receiver stops advancing rwnd (receiver window). When there is an application stall early during recovery, prr_out will fall behind the sum of the transmissions permitted by sndcnt. The missed opportunities to send due to stalls are treated like banked voluntary window reductions; specifically, they cause prr_delivered - prr_out to be significantly positive. If the application catches up while TCP is still in recovery, TCP will send a partial window burst to catch up to exactly where it would have been had the application never stalled. Although this burst might be viewed as being hard on the network, this is exactly what happens every time there is a partial RTT application stall while not in recovery. We have made the partial RTT stall behavior uniform in all states. Changing this behavior is out of scope for this document.
いずれかのリダクションバウンドを使用したPRRは、アプリケーションがストールしている場合、たとえば、送信アプリケーションが送信用のデータを十分に速くキューに入れない場合や、レシーバーがrwnd（レシーバーウィンドウ）の進行を停止する場合などの状況を改善します。リカバリの早い段階でアプリケーションがストールすると、prr_outはsndcntによって許可された送信の合計より遅れます。ストールのために送信されなかった送信機会は、銀行の自発的なウィンドウ削減のように扱われます。具体的には、これらはprr_delivered-prr_outを大幅に正にします。 TCPがまだ回復している間にアプリケーションが追いつくと、TCPは部分的なウィンドウバーストを送信して、アプリケーションが停止することがなかったはずの場所に正確に追いつきます。このバーストはネットワーク上でハードであると見なされる場合がありますが、これはまさに、リカバリ中でないときに部分的なRTTアプリケーションがストールするたびに発生することです。すべての状態で部分的なRTTストールの動作を均一にしました。この動作の変更は、このドキュメントの範囲外です。
PRR with Reduction Bound is less sensitive to errors in the pipe estimator. While in recovery, pipe is intrinsically an estimator, using incomplete information to estimate if un-SACKed segments are actually lost or merely out of order in the network. Under some conditions, pipe can have significant errors; for example, pipe is underestimated when a burst of reordered data is prematurely assumed to be lost and marked for retransmission. If the transmissions are regulated directly by pipe as they are with RFC 6675, a step discontinuity in the pipe estimator causes a burst of data, which cannot be retracted once the pipe estimator is corrected a few ACKs later. For PRR, pipe merely determines which algorithm, PRR or the Reduction Bound, is used to compute sndcnt from DeliveredData. While pipe is underestimated, the algorithms are different by at most 1 segment per ACK. Once pipe is updated, they converge to the same final window at the end of recovery.
リダクションバウンドを使用したPRRは、パイプ推定器のエラーの影響を受けにくくなっています。リカバリ中は、パイプは本質的にエスティメータであり、不完全な情報を使用して、SACKされていないセグメントが実際に失われているか、ネットワーク内で単に順序が狂っているかを推定します。状況によっては、パイプに重大なエラーが発生する可能性があります。たとえば、並べ替えられたデータのバーストが失われ、再送信のマークが付けられると時期尚早に想定される場合、パイプは過小評価されます。 RFC 6675の場合と同様に、伝送がパイプによって直接規制されている場合、パイプ推定器のステップの不連続によりデータのバーストが発生し、パイプ推定器が数回のACKで修正されるとデータのバーストが取り消されなくなります。 PRRの場合、パイプは、DeliveredDataからsndcntを計算するために使用されるアルゴリズム（PRRまたはリダクションバウンド）を決定するだけです。パイプは過小評価されていますが、アルゴリズムはACKごとに最大で1セグメント異なります。パイプが更新されると、回復の最後に同じ最終ウィンドウに収束します。
Under all conditions and sequences of events during recovery, PRR-CRB strictly bounds the data transmitted to be equal to or less than the amount of data delivered to the receiver. We claim that this Strong Packet Conservation Bound is the most aggressive algorithm that does not lead to additional forced losses in some environments. It has the property that if there is a standing queue at a bottleneck with no cross traffic, the queue will maintain exactly constant length for the duration of the recovery, except for +1/-1 fluctuation due to differences in packet arrival and exit times. See Appendix A for a detailed discussion of this property.
リカバリ中のすべての状況と一連のイベントでは、PRR-CRBは送信されるデータを厳密に制限して、受信者に配信されるデータの量以下にします。この強力なパケット保護限界は、一部の環境で追加の強制的な損失を引き起こさない最も攻撃的なアルゴリズムであると私たちは主張します。クロストラフィックのないボトルネックにスタンディングキューが存在する場合、パケットの到着時間と終了時間の違いによる+ 1 / -1の変動を除いて、キューは回復期間中正確に一定の長さを維持するという特性があります。 。このプロパティの詳細については、付録Aを参照してください。
Although the Strong Packet Conservation Bound is very appealing for a number of reasons, our measurements summarized in Section 5 demonstrate that it is less aggressive and does not perform as well as RFC 6675, which permits bursts of data when there are bursts of losses. PRR-SSRB is a compromise that permits TCP to send 1 extra segment per ACK as compared to the Packet Conserving Bound. From the perspective of a strict Packet Conserving Bound, PRR-SSRB does indeed open the window during recovery; however, it is significantly less aggressive than RFC 6675 in the presence of burst losses.
強力なパケット保護限界は多くの理由で非常に魅力的ですが、セクション5にまとめた測定は、それがあまり積極的ではなく、RFS 6675と同じように機能しないことを示しています。 PRR-SSRBは、TCPがパケット保護境界と比較してACKごとに1つの追加セグメントを送信できるようにする妥協案です。厳密なパケット保存限界の観点から見ると、PRR-SSRBは実際に回復中にウィンドウを開きます。ただし、バースト損失が存在する場合、RFC 6675よりも大幅に攻撃的ではありません。
In a companion IMC11 paper [IMC11], we describe some measurements comparing the various strategies for reducing the window during recovery. The experiments were performed on servers carrying Google production traffic and are briefly summarized here.
関連するIMC11ペーパー[IMC11]では、リカバリ中にウィンドウを縮小するためのさまざまな戦略を比較するいくつかの測定について説明します。実験は、Googleの本番トラフィックを伝送するサーバーで実行されました。
The various window reduction algorithms and extensive instrumentation were all implemented in Linux 2.6. We used the uniform set of algorithms present in the base Linux implementation, including CUBIC [CUBIC], Limited Transmit [RFC3042], threshold transmit (Section 3.1 in [FACK]) (this algorithm was not present in RFC 3517, but a similar algorithm has been added to RFC 6675), and lost retransmission detection algorithms. We confirmed that the behaviors of Rate-Halving (the Linux default), RFC 3517, and PRR were authentic to their respective specifications and that performance and features were comparable to the kernels in production use. All of the different window reduction algorithms were all present in a common kernel and could be selected with a sysctl, such that we had an absolutely uniform baseline for comparing them.
さまざまなウィンドウ縮小アルゴリズムと広範な計測機能がすべてLinux 2.6に実装されました。私たちは、CUBIC [CUBIC]、制限付き送信[RFC3042]、しきい値送信（[FACK]のセクション3.1）など、ベースLinux実装に存在するアルゴリズムの統一セットを使用しました（このアルゴリズムはRFC 3517には存在しませんでしたが、同様のアルゴリズムRFC 6675）に追加され、再送検出アルゴリズムが失われました。 Rate-Halving（Linuxのデフォルト）、RFC 3517、PRRの動作はそれぞれの仕様に準拠しており、パフォーマンスと機能は本番環境で使用されているカーネルと同等であることを確認しました。さまざまなウィンドウ削減アルゴリズムはすべて共通のカーネルに存在し、sysctlで選択できるため、それらを比較するための完全に均一なベースラインがありました。
Our experiments included an additional algorithm, PRR with an unlimited bound (PRR-UB), which sends ssthresh-pipe bursts when pipe falls below ssthresh. This behavior parallels RFC 3517.
私たちの実験には、パイプがssthreshを下回ったときにssthresh-pipeバーストを送信する追加のアルゴリズム、無制限の境界を持つPRR（PRR-UB）が含まれていました。この動作はRFC 3517に対応しています。
An important detail of this configuration is that CUBIC only reduces the window by 30%, as opposed to the 50% reduction used by traditional congestion control algorithms. This accentuates the tendency for RFC 3517 and PRR-UB to send a burst at the point when Fast Retransmit gets triggered because pipe is likely to already be below ssthresh. Precisely this condition was observed for 32% of the recovery events: pipe fell below ssthresh before Fast Retransmit was triggered, thus the various PRR algorithms started in the Reduction Bound phase, and RFC 3517 sent bursts of segments with the Fast Retransmit.
この構成の重要な詳細は、CUBICがウィンドウを30％しか削減しないことです。これは、従来の輻輳制御アルゴリズムで使用される50％の削減とは対照的です。これは、パイプが既にssthreshを下回っている可能性が高いため、高速再送信がトリガーされた時点でRFC 3517およびPRR-UBがバーストを送信する傾向を強調します。正確には、この状態が回復イベントの32％で観察されました。高速再送信がトリガーされる前にパイプがssthreshを下回り、さまざまなPRRアルゴリズムが削減バインドフェーズで開始され、RFC 3517が高速再送信でセグメントのバーストを送信しました。
In the companion paper, we observe that PRR-SSRB spends the least time in recovery of all the algorithms tested, largely because it experiences fewer timeouts once it is already in recovery.
コンパニオンペーパーでは、PRR-SSRBがテストされたすべてのアルゴリズムの回復に費やす時間が最も短いことを観察しています。
RFC 3517 experiences 29% more detected lost retransmissions and 2.6% more timeouts (presumably due to undetected lost retransmissions) than PRR-SSRB. These results are representative of PRR-UB and other algorithms that send bursts when pipe falls below ssthresh.
RFC 3517では、PRR-SSRBと比較して、失われた再送信の検出が29％増加し、タイムアウトが2.6％増加しています（失われた再送信が検出されなかったためと考えられます）。これらの結果は、パイプがssthreshを下回ったときにバーストを送信するPRR-UBおよびその他のアルゴリズムを表しています。
Rate-Halving experiences 5% more timeouts and significantly smaller final cwnd values at the end of recovery. The smaller cwnd sometimes causes the recovery itself to take extra round trips. These results are representative of PRR-CRB and other algorithms that implement strict packet conservation during recovery.
レート半減では、タイムアウトが5％増加し、リカバリの最後に最終的なcwnd値が大幅に小さくなります。 cwndが小さいと、リカバリ自体に余分なラウンドトリップが発生することがあります。これらの結果は、PRR-CRBと、リカバリ中に厳密なパケット保存を実装するその他のアルゴリズムを表しています。
Although the Strong Packet Conservation Bound used in PRR-CRB is very appealing for a number of reasons, our measurements show that it is less aggressive and does not perform as well as RFC 3517 (and by implication RFC 6675), which permits bursts of data when there are bursts of losses. RFC 3517 and RFC 6675 are conservative in the original sense of Van Jacobson's packet conservation principle, which included the assumption that presumed lost segments have indeed left the network. PRR-CRB makes no such assumption, following instead a Strong Packet Conservation Bound in which only packets that have actually arrived at the receiver are considered to have left the network. PRR-SSRB is a compromise that permits TCP to send 1 extra segment per ACK relative to the Strong Packet Conservation Bound, to partially compensate for excess losses.
PRR-CRBで使用される強力なパケット保護境界は多くの理由で非常に魅力的ですが、測定では、データのバーストを許可するRFC 3517（および暗黙のRFC 6675）ほど強力ではなく、パフォーマンスが低いことが示されています損失のバーストがあるとき。 RFC 3517とRFC 6675は、Van Jacobsonのパケット保存原理の本来の意味で保守的であり、失われたと推定されるセグメントが実際にネットワークを離れたという仮定が含まれていました。 PRR-CRBはそのような仮定を行わず、代わりに、実際に受信側に到着したパケットのみがネットワークを離れたと見なされる強力なパケット保護境界に従います。 PRR-SSRBは、過剰な損失を部分的に補償するために、TCPが強力なパケット保護限界に関連してACKごとに1つの追加セグメントを送信できるようにする妥協案です。
From the perspective of the Strong Packet Conservation Bound, PRR-SSRB does indeed open the window during recovery; however, it is significantly less aggressive than RFC 3517 (and RFC 6675) in the presence of burst losses. Even so, it often outperforms RFC 3517 (and presumably RFC 6675) because it avoids some of the self-inflicted losses caused by bursts.
強力なパケット保護限界の観点から見ると、PRR-SSRBは実際に回復中にウィンドウを開きます。ただし、バースト損失が存在する場合、RFC 3517（およびRFC 6675）よりも大幅に攻撃的ではありません。それでも、バーストによって引き起こされる自己による損失の一部を回避するため、RFC 3517（およびおそらくRFC 6675）よりもパフォーマンスがよくなります。
At this time, we see no reason not to test and deploy PRR-SSRB on a large scale. Implementers worried about any potential impact of raising the window during recovery may want to optionally support PRR-CRB (which is actually simpler to implement) for comparison studies. Furthermore, there is one minor detail of PRR that can be improved by replacing pipe by total_pipe, as defined by Laminar TCP [Laminar].
現時点では、PRR-SSRBを大規模にテストおよび展開しない理由はありません。リカバリ中にウィンドウを上げることの潜在的な影響を心配している実装者は、比較調査のためにPRR-CRB（実際には実装がより簡単）をオプションでサポートすることができます。さらに、Laminar TCP [Laminar]で定義されているように、パイプをtotal_pipeで置き換えることで改善できるPRRの1つのマイナーな詳細があります。
One final comment about terminology: we expect that common usage will drop "Slow Start Reduction Bound" from the algorithm name. This document needed to be pedantic about having distinct names for PRR and every variant of the Reduction Bound. However, we do not anticipate any future exploration of the alternative Reduction Bounds.
用語についての最後のコメント：一般的な使用法では、アルゴリズム名から「スロースタートリダクションバウンド」が削除されると予想されます。このドキュメントでは、PRRとリダクションバウンドのすべてのバリアントに明確な名前を付ける必要があります。ただし、代替の削減範囲の今後の調査は予定されていません。
This document is based in part on previous incomplete work by Matt Mathis, Jeff Semke, and Jamshid Mahdavi [RHID] and influenced by several discussions with John Heffner.
このドキュメントは、Matt Mathis、Jeff Semke、Jamshid Mahdavi [RHID]による以前の不完全な作業に一部基づいており、John Heffnerとのいくつかの議論の影響を受けています。
Monia Ghobadi and Sivasankar Radhakrishnan helped analyze the experiments.
Monia GhobadiとSivasankar Radhakrishnanが実験の分析を支援しました。
Ilpo Jarvinen reviewed the code.
Ilpo Jarvinenがコードをレビューしました。
Mark Allman improved the document through his insightful review.
Mark Allmanは、洞察に満ちたレビューを通じてドキュメントを改善しました。
PRR does not change the risk profile for TCP.
PRRはTCPのリスクプロファイルを変更しません。
Implementers that change PRR from counting bytes to segments have to be cautious about the effects of ACK splitting attacks [Savage99], where the receiver acknowledges partial segments for the purpose of confusing the sender's congestion accounting.
PRRをバイト数のカウントからセグメントに変更する実装者は、ACK分割攻撃[Savage99]の影響に注意する必要があります。この場合、受信者は送信者の輻輳アカウンティングを混乱させる目的で部分的なセグメントを確認します。
[RFC0793] Postel, J., "Transmission Control Protocol", STD 7, RFC 793, September 1981.
[RFC0793] Postel、J。、「Transmission Control Protocol」、STD 7、RFC 793、1981年9月。
[RFC2018] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP Selective Acknowledgment Options", RFC 2018, October 1996.
[RFC2018] Mathis、M.、Madhavi、J.、Floyd、S。、およびA. Romanow、「TCP選択的確認応答オプション」、RFC 2018、1996年10月。
[RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion Control", RFC 5681, September 2009.
[RFC5681] Allman、M.、Paxson、V。、およびE. Blanton、「TCP Congestion Control」、RFC 5681、2009年9月。
[RFC6675] Blanton, E., Allman, M., Wang, L., Jarvinen, I., Kojo, M., and Y. Nishida, "A Conservative Loss Recovery Algorithm Based on Selective Acknowledgment (SACK) for TCP", RFC 6675, August 2012.
[RFC6675] Blanton、E.、Allman、M.、Wang、L.、Jarvinen、I.、Kojo、M。、およびY. Nishida、「TCPの選択的確認応答（SACK）に基づく保守的な損失回復アルゴリズム」、 RFC 6675、2012年8月。
[RFC3042] Allman, M., Balakrishnan, H., and S. Floyd, "Enhancing TCP's Loss Recovery Using Limited Transmit", RFC 3042, January 2001.
[RFC3042] Allman、M.、Balakrishnan、H。、およびS. Floyd、「Enhancing TCP's Loss Recovery Using Limited Transmit」、RFC 3042、2001年1月。
[RFC3517] Blanton, E., Allman, M., Fall, K., and L. Wang, "A Conservative Selective Acknowledgment (SACK)-based Loss Recovery Algorithm for TCP", RFC 3517, April 2003.
[RFC3517] Blanton、E.、Allman、M.、Fall、K。、およびL. Wang、「A Conservative Selective Acknowledgement（SACK）-based Loss Recovery Algorithm for TCP」、RFC 3517、2003年4月。
[IMC11] Dukkipati, N., Mathis, M., Cheng, Y., and M. Ghobadi, "Proportional Rate Reduction for TCP", Proceedings of the 11th ACM SIGCOMM Conference on Internet Measurement 2011, Berlin, Germany, November 2011.
[IMC11] Dukkipati、N.、Mathis、M.、Cheng、Y。、およびM. Ghobadi、「TCPの比例レート削減」、第11回ACM SIGCOMM会議のインターネット測定2011、ベルリン、ドイツ、2011年11月。
[FACK] Mathis, M. and J. Mahdavi, "Forward Acknowledgment: Refining TCP Congestion Control", ACM SIGCOMM SIGCOMM96, August 1996.
[FACK] Mathis、M.、J。Mahdavi、「Forward Acknowledgement：Refining TCP Congestion Control」、ACM SIGCOMM SIGCOMM96、1996年8月。
[RHID] Mathis, M., Semke, J., and J. Mahdavi, "The Rate-Halving Algorithm for TCP Congestion Control", Work in Progress, August 1999.
[RHID] Mathis、M.、Semke、J。、およびJ. Mahdavi、「TCP輻輳制御のレート半分アルゴリズム」、作業中、1999年8月。
[RHweb] Mathis, M. and J. Mahdavi, "TCP Rate-Halving with Bounding Parameters", Web publication, December 1997, <http://www.psc.edu/networking/papers/FACKnotes/current/>.
[RHweb] Mathis、M。およびJ. Mahdavi、「境界パラメータを使用したTCPレートハービング」、Web出版、1997年12月、<http://www.psc.edu/networking/papers/FACKnotes/current/>。
[CUBIC] Rhee, I. and L. Xu, "CUBIC: A new TCP-friendly high-speed TCP variant", PFLDnet 2005, February 2005.
[CUBIC] Rhee、I。およびL. Xu、「CUBIC：新しいTCP対応の高速TCPバリアント」、PFLDnet 2005、2005年2月。
[Jacobson88] Jacobson, V., "Congestion Avoidance and Control", SIGCOMM Comput. Commun. Rev. 18(4), August 1988.
[Jacobson88] Jacobson、V。、「輻輳回避および制御」、SIGCOMM Comput。コミュ。 1988年8月、Rev。18（4）。
[Savage99] Savage, S., Cardwell, N., Wetherall, D., and T. Anderson, "TCP congestion control with a misbehaving receiver", SIGCOMM Comput. Commun. Rev. 29(5), October 1999.
[Savage99] Savage、S.、Cardwell、N.、Wetherall、D。、およびT. Anderson、「TCP輻輳制御と受信機の誤動作」、SIGCOMM Comput。コミュ。改訂29（5）、1999年10月。
[Laminar] Mathis, M., "Laminar TCP and the case for refactoring TCP congestion control", Work in Progress, July 2012.
[Laminar] Mathis、M。、「Laminar TCP and the case for refactoring TCP congestion control」、Work in Progress、2012年7月。
PRR-CRB is based on a conservative, philosophically pure, and aesthetically appealing Strong Packet Conservation Bound, described here. Although inspired by Van Jacobson's packet conservation principle [Jacobson88], it differs in how it treats segments that are missing and presumed lost. Under all conditions and sequences of events during recovery, PRR-CRB strictly bounds the data transmitted to be equal to or less than the amount of data delivered to the receiver. Note that the effects of presumed losses are included in the pipe calculation, but do not affect the outcome of PRR-CRB, once pipe has fallen below ssthresh.
PRR-CRBは、ここで説明する、保守的で哲学的に純粋で、美的に魅力のある強力なパケット保護限界に基づいています。ヴァンジェイコブソンのパケット保護の原理[Jacobson88]に触発されましたが、欠落しており、失われたと推定されるセグメントの扱い方が異なります。リカバリ中のすべての状況と一連のイベントでは、PRR-CRBは送信されるデータを厳密に制限して、受信者に配信されるデータの量以下にします。推定損失の影響はパイプの計算に含まれますが、パイプがssthreshを下回ると、PRR-CRBの結果には影響しません。
We claim that this Strong Packet Conservation Bound is the most aggressive algorithm that does not lead to additional forced losses in some environments. It has the property that if there is a standing queue at a bottleneck that is carrying no other traffic, the queue will maintain exactly constant length for the entire duration of the recovery, except for +1/-1 fluctuation due to differences in packet arrival and exit times. Any less aggressive algorithm will result in a declining queue at the bottleneck. Any more aggressive algorithm will result in an increasing queue or additional losses if it is a full drop tail queue.
この強力なパケット保護限界は、一部の環境で追加の強制的な損失を引き起こさない最も攻撃的なアルゴリズムであると私たちは主張します。他のトラフィックを運んでいないボトルネックにスタンディングキューがある場合、キューは、パケットの到着の違いによる+ 1 / -1の変動を除いて、リカバリの全期間にわたって正確に一定の長さを維持するという特性があります。と終了時間。あまり積極的でないアルゴリズムは、ボトルネックでキューの減少につながります。フルドロップテールキューの場合、これ以上積極的なアルゴリズムを使用すると、キューが増加したり、追加の損失が発生したりします。
We demonstrate this property with a little thought experiment:
少し考えた実験でこの特性を実証します。
Imagine a network path that has insignificant delays in both directions, except for the processing time and queue at a single bottleneck in the forward path. By insignificant delay, we mean when a packet is "served" at the head of the bottleneck queue, the following events happen in much less than one bottleneck packet time: the packet arrives at the receiver; the receiver sends an ACK that arrives at the sender; the sender processes the ACK and sends some data; the data is queued at the bottleneck.
順方向パスの単一のボトルネックでの処理時間とキューを除いて、両方向にわずかな遅延があるネットワークパスを想像してください。わずかな遅延とは、ボトルネックキューの先頭でパケットが「処理」されると、次のイベントが1つのボトルネックパケット時間よりもはるかに短い時間で発生することを意味します。受信者は送信者に到着するACKを送信します。送信者はACKを処理してデータを送信します。データはボトルネックでキューに入れられます。
If sndcnt is set to DeliveredData and nothing else is inhibiting sending data, then clearly the data arriving at the bottleneck queue will exactly replace the data that was served at the head of the queue, so the queue will have a constant length. If queue is drop tail and full, then the queue will stay exactly full. Losses or reordering on the ACK path only cause wider fluctuations in the queue size, but do not raise its peak size, independent of whether the data is in order or out of order (including loss recovery from an earlier RTT). Any more aggressive algorithm that sends additional data will overflow the drop tail queue and cause loss. Any less aggressive algorithm will under-fill the queue. Therefore, setting sndcnt to DeliveredData is the most aggressive algorithm that does not cause forced losses in this simple network. Relaxing the assumptions (e.g., making delays more authentic and adding more flows, delayed ACKs, etc.) is likely to increase the fine grained fluctuations in queue size but does not change its basic behavior.
sndcntがDeliveredDataに設定されていて、他にデータの送信を妨げているものがない場合、ボトルネックキューに到着したデータは、キューの先頭で提供されたデータを正確に置き換え、キューの長さは一定になります。キューがドロップテールでフルの場合、キューは完全にフルのままになります。 ACKパスでの損失または並べ替えは、キューサイズのより大きな変動を引き起こすだけですが、データの順序が正しいかどうかに関係なく、ピークサイズを上げません（以前のRTTからの損失回復を含む）。追加のデータを送信するより積極的なアルゴリズムは、ドロップテールキューをオーバーフローさせ、損失を引き起こします。あまり積極的でないアルゴリズムは、キューを埋め尽くします。したがって、sndcntをDeliveredDataに設定することは、この単純なネットワークで強制的な損失を引き起こさない最も積極的なアルゴリズムです。仮定を緩和すると（たとえば、遅延をより確実にし、フローを追加したり、ACKを遅延させるなど）、キューサイズの細かい変動を増やす可能性がありますが、基本的な動作は変わりません。
Note that the congestion control algorithm implements a broader notion of optimal that includes appropriately sharing the network. Typical congestion control algorithms are likely to reduce the data sent relative to the Packet Conserving Bound implemented by PRR, bringing TCP's actual window down to ssthresh.
輻輳制御アルゴリズムは、ネットワークを適切に共有することを含む最適のより広い概念を実装することに注意してください。典型的な輻輳制御アルゴリズムは、PRRによって実装されたパケット保存境界に関連して送信されるデータを削減し、TCPの実際のウィンドウをssthreshに下げる可能性があります。
Authors' Addresses
著者のアドレス
Matt Mathis Google, Inc. 1600 Amphitheatre Parkway Mountain View, California 94043 USA
Matt Mathis Google、Inc. 1600 Amphitheatre Parkway Mountain View、California 94043 USA
EMail: mattmathis@google.com
Nandita Dukkipati Google, Inc. 1600 Amphitheatre Parkway Mountain View, California 94043 USA
Nandita Dukkipati Google、Inc. 1600 Amphitheatre Parkway Mountain View、California 94043 USA
EMail: nanditad@google.com
Yuchung Cheng Google, Inc. 1600 Amphitheatre Parkway Mountain View, California 94043 USA
Yuchung Cheng Google、Inc. 1600 Amphitheatre Parkway Mountain View、California 94043 USA
EMail: ycheng@google.com