TCPM M. Scharf
Internet-Draft Alcatel-Lucent Bell Labs
Intended status: Informational S. Kiesel
Expires: January 16, 2014 University of Stuttgart
July 15, 2013

Quantifying Head-of-Line Blocking in TCP and SCTP
draft-scharf-tcpm-reordering-00

Abstract

In order to quantify the impact of head-of-line blocking on application latencies, this memo provides simple analytical models for a "back of the envelop" estimation of the delay impact for reliable transport over a single TCP connection, multiple TCP connections, multiple SCTP streams, and unordered transport.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on January 16, 2014.

Copyright Notice

Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved.

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.


Table of Contents

1. Introduction

The Transmission Control Protocol (TCP) [RFC0793] provides reliable in-order transport. If segments get lost due to congestion, the delivery delay inside one TCP connection is increased due to head-of-line blocking (HOL). There are several technique to mitigate HOL, e. g., using several TCP connections in parallel. An alternative is the Stream Control Transmission Protocol (SCTP) [RFC4960], since SCTP can provide partial-ordered or unordered reliable message delivery. While the reduction of HOL is a well-known feature of SCTP, there are only few studies that quantify the impact of this effect on end-to-end delays.

This document discusses the impact of HOL on TCP and SCTP in different usage scenarios. Simple analytical models quantify the additional delay on application data delivery caused by HOL. These models were originally published in [Globecom2006]. The original motivation was to study HOL effects on signaling applications with a high traffic load [Comnet2007]. But the model can also be applied to selected media transport use cases.

The analysis reveals the delaying impact of HOL is not large for moderate packet loss probabilities.

2. Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].

3. Head-of-Line-Blocking in Transport Protocols

3.1. Classification of Message Delivery Modes

The two classical Internet transport protocols Transmission Control Protocol (TCP) and User Datagram Protocol (UDP) either provide an ordered reliable service (TCP) or one that does not guarantee any ordered delivery and which is not reliable (UDP). However, reliability (i. e., protection against message loss) and ordered delivery (i. e., passing the messages to the receiving application in the same sequence as they were sent by the sender) are orthogonal features of a transport protocol. Many applications have high reliability requirements and thus need a reliable transport protocol, but some of these applications do not necessarily require an ordered delivery of their messages. With respect to ordering, the requirements of applications can be subdivided into three classes: (1) ordered, (2) partial-ordered, or (3) unordered delivery. In the second case, the transport protocol must preserve only the ordering relation for subsets of all messages.

Head-of-line blocking (HOL) can occur when transport protocols offer ordered or partial-ordered service: If segments get lost, subsequent messages have to wait for the successful retransmission in the receiver queue and are thus delayed. Due to real-time requirements, resequencing delays are critical for interactive media transport, and also e. g. for signaling protocols.

3.2. Potential Mitigation: Multiple TCP Connections

A potential approach to reduce head-of-line blocking in a single TCP connection is to use several parallel TCP connections between the same two end systems (e. g., [RFC2616]). If one connection is subject to head-of-line blocking, other connections can still deliver messages. For partial-ordered delivery, all messages that are in a causal relationship have to be transmitted via the same connection.

But the use of multiple TCP connection raises fairness issues. Furthermore, it has drawbacks compared to SCTP. There is more overhead, as each TCP connection must be established, maintained, and closed separately. Furthermore, each TCP connections has to recover from packet loss independently, whereas SCTP applies error recovery and congestion control mechanisms to the aggregated message flow.

3.3. Potential Mitigation: SCTP Multistreaming

SCTP is a message-oriented, general purpose transport protocol optimized for signaling transport. It allows to split one association into up to 65536 streams per association. Each user message is transmitted in one of these streams, and SCTP ensures in-order delivery only within the same stream. This is similar to using several parallel TCP connections, but avoids the drawbacks mentioned above (see e. g. [Comnet2007]).

3.4. Potential Mitigation: SCTP Unordered Transport

When sending messages in unordered mode, SCTP offers reliable transport, but delivers messages to the upper layer protocol as they arrive. This solution completely avoids head-of-line blocking. However, the upper layer protocol must have own mechanisms to deal with potentially reordered messages. This mode of operation is used, e. g., for SIP over SCTP [RFC2616].

4. Head-of-line Blocking for Media or Signaling Traffic

4.1. Model Assumptions

This section analyzes the effect of head-of-line blocking for a traffic workload that consists of repeatedly sent single data segments. This send pattern is typical for low-bandwidh media applications or certain signaling traffic.

The model, which was originally published in [Globecom2006], considers partial-ordered data transmission over N > 1 SCTP streams, SCTP unordered mode and the usage of one or several TCP connections. It assumes that the path between the two endpoints has a constant unidirectional delay of L and thus a minimum round-trip time RTT = 2 L. The path is supposed to suffer from random, uncorrelated packet losses with loss probability p due to congestion. The model assumes that the data transport is application limited, i. e., the congestion window is large enough to always transmit data. This assumption is reasonable for low-bandwidth interactive media transport or signaling traffic and small values of p. The model does not apply to bulk data transport or senders that are limited by congestion control.

For simplicity, application messages are supposed to be sent with constant interarrival time d. Under the assumption that the total traffic is equally distributed over the N SCTP streams or TCP connections, the message load on each of them is 1/N of the overall workload, which is 1/d.

The following sections explain the model as published in [Globecom2006]. The model was validated with several real TCP and SCTP implementations in [Globecom2006] and with a more recent TCP stack in [Scharf2011]. The validation results show that the model provides a lower-bound for application latencies. Additional delay can be caused e. g. by congestion control. A simple, close-form model can hardly cover such complex effects. Still, the model gives a reasonable insight into the order of magnitude of HOL effects.

4.2. Modeling Error Detection in TCP and SCTP

TCP as well as SCTP can recover from packet loss by two mechanisms, which are used in a similar way in both protocols: The fast retransmit and the retransmission timeout. In the following, we explain their impact on end-to-end delays first for SCTP. Afterwards, we extend the model to address TCP.

An SCTP endpoint can detect packet loss if transmission sequence numbers (TSNs) are missing in the selective acknowledgments (SACKs). A SACK, which is sent upon the reception of a data chunk on any stream, contains missing TSN reports for all streams. An SCTP endpoint retransmits data when three subsequent SACKs include a missing report. The reliable data delivery is also ensured by a timeout mechanism: If the the oldest outstanding data chunk has not been acknowledged when the retransmission timeout expires, missing chunks are retransmitted. The timer is restarted whenever a new acknowledgment arrives.

As derived in [Globecom2006], the error detection time D in the sender is


      D = min( RTT + 3*d, RTO + max( RTT - d, 0 ) ) .    (1)

Therein, the parameter d is the inter-arrival time of application messages. This expression is an approximation only since more than one packet, the retransmission, or acknowledgments may get lost, too. This may trigger overlapping fast recovery periods or more complex retransmission scenarios, which are difficult to describe by a simple model. We neglect these effects since they hardly occur for small loss probabilities.

4.3. HOL Effect for SCTP Multistreaming

As further explained in [Globecom2006], in case of SCTP multistreaming, data chunks have to wait in a stream's resequencing queue until the retransmission arrives at the receiver. The waiting times w_n depend on the time D to detect the packet loss. The number of data chunks that have to be queued until the retransmission arrives is Q = floor( D / d / N). The resequencing delay of the first data chunk after the lost one is w_1 = D - N*d. The subsequent waiting times are w_2 = D - 2*N*d, ..., w_Q = D - Q*N*d. The mean waiting time is the sum of all w_i divided by the mean number of data chunks between two losses, which is 1/p. The mean increase of the unidirectional end-to-end delay is thus

            __ Q
            \                             Q (Q+1) 
      W = p /_     w_i = p ( (Q+1) * D - --------- * N * d ) .    (2)
               i=0                           2

4.4. HOL for SCTP Unordered Transport

Messages with the unordered flag set can be delivered to the upper layer protocol as they arrive. If all messages are sent in this mode, the mean resequencing delay just includes the error recovery of the lost segments:


      W = p * D .    (3)

The same result applies for partial-ordered transport over a sufficiently large number of streams, i. e., if the stream to be used for the next message transmission has already recovered from a potential previous loss (Q = 0). This is approximately fulfilled for N > M with M = ceil(D / d). In both cases head-of-line bocking can be avoided completely, i. e., Eq. (3) provides the theoretical minimum latency.

4.5. HOL for One or Multiple TCP Connections

From a theoretical point of view, the resequencing delay of one SCTP stream and one TCP connection should be mostly identical, since both protocols use similar error recovery algorithms. If several parallel TCP connections are used, each connection has an independent error recovery, i. e., acknowledgments only refer to data transmitted over the same connection. As a result, the time to trigger a fast retransmit is D = RTT + 3*d*N and increases with the number of connections N. The mean waiting time can obtained by substituting D in the SCTP result in Eq. (2) by


      D = min( RTT + 3*d*N, RTO + max( RTT - N*d, 0 ) ) .    (4)

A particularly important use case is transport over a single TCP connection (N = 1).

4.6. Resulting Application Delivery Time

In the considered scenario, the mean unidirectional end-to-end delay is


      T = RTT/2 + W ,    (5)

wherein W is given by the derived terms in the previous sections.

4.7. Numerical Results

The closed-form analytical models can be used to quantify the mean unidirectional delivery delay for any application data inter-arrival time d, network round-trip time RTT, and packet loss probability p. Example numerical results can be found in [Globecom2006], [Comnet2007], and [Scharf2011]. These publications also compare the analytical models with measurement results of selected TCP and SCTP stacks.

Table Table 1 lists some example results. The assumption is that a VoIP application sends messages with a packetization interval of 20ms, i. e., d = 20ms. The unidirectional average delivery delay is compared both for transport over a single TCP connection and for SCTP unordered delivery, which represents the theoretical minumum. The RTO is assumed to be one second [RFC6298].

Average unidirectional data transfer latencies for VoIP workload according to the model
Packet loss probability TCP (RTT 50ms) SCTP unordered (RTT 50ms) TCP (RTT 200ms) SCTP unordered (RTT 200ms)
0.0% 25ms 25ms 100ms 100ms
0.1% 25.36ms 25.11ms 101.82ms 100.26ms
1.0% 28.6ms 26.1ms 118.2ms 102.6ms
2.0% 32.2ms 27.2ms 136.4ms 105.2ms

The numerical results in Table Table 1 show that for a moderate RTT of 50 ms, the unidirectional delivery delay for a single TCP connections is larger than for SCTP unordered transport, but the absolute difference is small. Also, the maximum delay jitter D stays within a typical end-to-end delay budget of 200ms of VoIP. The HOL effect is more severe for long-distance links (RTT 200ms), but such a large absolute RTT will have other detrimental effects on latency-sensitive applications as well.

5. Other Application Workloads

TBD

6. Security Considerations

This document does not suggest to change TCP or SCTP. Therefore, it does not result in any additional security risks.

7. Conclusion

This document analyze the impact of head-of-line blocking (HOL) on TCP and SCTP and compares the use of one or several parallel TCP connections, SCTP multistreaming, or SCTP unordered mode, respectively. An simple analytical model estimates the average delivery delay for application messages in each case and thereby quantifies the delaying effect of HOL.

8. References

8.1. Normative References

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC0793] Postel, J., "Transmission Control Protocol", STD 7, RFC 793, September 1981.
[RFC2616] Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P. and T. Berners-Lee, "Hypertext Transfer Protocol -- HTTP/1.1", RFC 2616, June 1999.
[RFC4168] Rosenberg, J., Schulzrinne, H. and G. Camarillo, "The Stream Control Transmission Protocol (SCTP) as a Transport for the Session Initiation Protocol (SIP)", RFC 4168, October 2005.
[RFC4960] Stewart, R., "Stream Control Transmission Protocol", RFC 4960, September 2007.
[RFC6298] Paxson, V., Allman, M., Chu, J. and M. Sargent, "Computing TCP's Retransmission Timer", RFC 6298, June 2011.

8.2. Informative References

[Globecom2006] Scharf, M. and S. Kiesel, "Head-of-Line Blocking in TCP and SCTP", Proc. IEEE Globecom 2006, Nov. 2006.
[Scharf2011] Scharf, M., "Fast Startup Internet Congestion Control for Broadband Interactive Applications", Phd thesis, University of Stuttgart, Apr. 2011.
[Comnet2007] Kiesel, S. and M. Scharf, "Modeling and performance evaluation of transport protocols for firewall control", Computer Networks 51(11), Aug. 2007.

Authors' Addresses

Michael Scharf Alcatel-Lucent Bell Labs Lorenzstrasse 10 Stuttgart, 70435 Germany EMail: michael.scharf@alcatel-lucent.com
Sebastian Kiesel University of Stuttgart, Computing Center Allmandring 30 Stuttgart, 70550 Germany EMail: ietf-tcpm@skiesel.de