Internet DRAFT - draft-scharf-tcpm-reordering
draft-scharf-tcpm-reordering
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.
Scharf & Kiesel Expires January 16, 2014 [Page 1]
Internet-Draft HOL in TCP/SCTP July 2013
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
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Head-of-Line-Blocking in Transport Protocols . . . . . . . . 3
3.1. Classification of Message Delivery Modes . . . . . . . . 3
3.2. Potential Mitigation: Multiple TCP Connections . . . . . 3
3.3. Potential Mitigation: SCTP Multistreaming . . . . . . . . 4
3.4. Potential Mitigation: SCTP Unordered Transport . . . . . 4
4. Head-of-line Blocking for Media or Signaling Traffic . . . . 4
4.1. Model Assumptions . . . . . . . . . . . . . . . . . . . . 4
4.2. Modeling Error Detection in TCP and SCTP . . . . . . . . 5
4.3. HOL Effect for SCTP Multistreaming . . . . . . . . . . . 6
4.4. HOL for SCTP Unordered Transport . . . . . . . . . . . . 6
4.5. HOL for One or Multiple TCP Connections . . . . . . . . . 7
4.6. Resulting Application Delivery Time . . . . . . . . . . . 7
4.7. Numerical Results . . . . . . . . . . . . . . . . . . . . 7
5. Other Application Workloads . . . . . . . . . . . . . . . . . 8
6. Security Considerations . . . . . . . . . . . . . . . . . . . 8
7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 8
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 8
8.1. Normative References . . . . . . . . . . . . . . . . . . 8
8.2. Informative References . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9
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.
Scharf & Kiesel Expires January 16, 2014 [Page 2]
Internet-Draft HOL in TCP/SCTP July 2013
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
Scharf & Kiesel Expires January 16, 2014 [Page 3]
Internet-Draft HOL in TCP/SCTP July 2013
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
Scharf & Kiesel Expires January 16, 2014 [Page 4]
Internet-Draft HOL in TCP/SCTP July 2013
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)
Scharf & Kiesel Expires January 16, 2014 [Page 5]
Internet-Draft HOL in TCP/SCTP July 2013
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.
Scharf & Kiesel Expires January 16, 2014 [Page 6]
Internet-Draft HOL in TCP/SCTP July 2013
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].
Scharf & Kiesel Expires January 16, 2014 [Page 7]
Internet-Draft HOL in TCP/SCTP July 2013
+---------------+-----------+-------------+-----------+-------------+
| Packet loss | TCP (RTT | SCTP | TCP (RTT | SCTP |
| probability | 50ms) | unordered | 200ms) | unordered |
| | | (RTT 50ms) | | (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 |
+---------------+-----------+-------------+-----------+-------------+
Table 1: Average unidirectional data transfer latencies for VoIP
workload according to the model
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
Scharf & Kiesel Expires January 16, 2014 [Page 8]
Internet-Draft HOL in TCP/SCTP July 2013
[RFC0793] Postel, J., "Transmission Control Protocol", STD 7, RFC
793, September 1981.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[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
[Comnet2007]
Kiesel, S. and M. Scharf, "Modeling and performance
evaluation of transport protocols for firewall control",
Computer Networks 51(11), Aug. 2007.
[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.
Authors' Addresses
Michael Scharf
Alcatel-Lucent Bell Labs
Lorenzstrasse 10
Stuttgart 70435
Germany
Email: michael.scharf@alcatel-lucent.com
Scharf & Kiesel Expires January 16, 2014 [Page 9]
Internet-Draft HOL in TCP/SCTP July 2013
Sebastian Kiesel
University of Stuttgart, Computing Center
Allmandring 30
Stuttgart 70550
Germany
Email: ietf-tcpm@skiesel.de
Scharf & Kiesel Expires January 16, 2014 [Page 10]
