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


   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

   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
   ( 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",
   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

         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

   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


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

8.2.  Informative References

              Kiesel, S. and M. Scharf, "Modeling and performance
              evaluation of transport protocols for firewall control",
              Computer Networks 51(11), Aug. 2007.

              Scharf, M. and S. Kiesel, "Head-of-Line Blocking in TCP
              and SCTP", Proc. IEEE Globecom 2006, Nov. 2006.

              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


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


Scharf & Kiesel         Expires January 16, 2014               [Page 10]