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
• 2. Terminology
• 3. Head-of-Line-Blocking in Transport Protocols
• 3.1. Classification of Message Delivery Modes
• 3.2. Potential Mitigation: Multiple TCP Connections
• 3.3. Potential Mitigation: SCTP Multistreaming
• 3.4. Potential Mitigation: SCTP Unordered Transport
• 4. Head-of-line Blocking for Media or Signaling Traffic
• 4.1. Model Assumptions
• 4.2. Modeling Error Detection in TCP and SCTP
• 4.3. HOL Effect for SCTP Multistreaming
• 4.4. HOL for SCTP Unordered Transport
• 4.5. HOL for One or Multiple TCP Connections
• 4.6. Resulting Application Delivery Time
• 4.7. Numerical Results
• 5. Other Application Workloads
• 6. Security Considerations
• 7. Conclusion
• 8. References
• 8.1. Normative References
• 8.2. Informative References
• Authors' Addresses

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].