.. include:: replace.txt

.. include:: replace.txt
.. highlight:: cpp

SACK option and TCP SACK implementation in |ns3|
------------------------------------------------

This chapter describes the SACK option and TCP SACK implementation in |ns3|. This implementation is contained in the following files:

.. sourcecode:: text

    src/internet/model/tcp-option-sack-permitted.{cc,h}
    src/internet/model/tcp-option-sack.{cc,h}
    src/internet/model/tcp-socket-base.{cc,h}
    src/internet/model/tcp-option.{cc,h}
    src/internet/model/tcp-scoreboard.{cc,h}
    src/internet/model/tcp-rx-buffer.{cc,h}
    src/internet/model/tcp-sack.{cc,h}

Model Description
*****************

SACK option implementation
==========================

TCP SACK extention [Mat96] addresses the catastrophic throughput degradation of TCP in the presence of multiple packet losses from a single window of data.  The SACK extension comprises of 2 options: SACK-permitted and SACK.  The SACK-permitted, defined in class :cpp:class:`TcpOptionSackPermitted`, is sent in a SYN segment to allow the SACK option usage during a connection lifetime.  The SACK option, defined in class :cpp:class:`TcpOptionSack`, is sent by a data receiver to inform the sender of non-contiguous blocks of data that have been received and queued in the receving buffer but cannot be acknowledged due to some missing segments. Each block is defined by two 32-bit unsigned integers specifying the left and the right edge of the block. Note that with the 40-byte TCP option limitation in addition to the presence of TCP Timestamp option, the maximum number of SACK blocks can be appended to each packet is 3. 

The class :cpp:class:`TcpSocketBase` handles the SACK-permitted and SACK option processing to enable the use of SACK mechanism by all TCP variants available in |ns3|. Before transmitting an ACK that does not acknowledge the highest sequence number received, a receiver tries to find all isolated data chunks in the receving buffer. This is done by calling ``TcpRxBuffer::GetIsolatedDataChunks ()`` from ``TcpSocketBase::ReceivedData ()``. The returned list of isolated data blocks is then sorted by an auxiliary routine ``TcpSocketBase::ArrageSackBlocks ()`` to make sure that the block containing the segment that triggers this particular ACK packet is at the front of the list. When the SACK list is ready and the ACK segment is constructed, ``TcpSocketBase::AddOptionSack ()`` is called, which in turn calls ``TcpHeader::AppendOption ()`` to append as many SACK blocks to the packet as possible. 

On the sender side, a scoreboard handled by the class :cpp:class:`TcpScoreBoard` is maintained to keep track of SACK information. When the sender receives an ACK with SACK option appended, the sender calls ``TcpScoreBoard::Update ()`` to turn on the SACK flag for all transmitted segments that are covered by the received SACK blocks.  When deciding on a packet for retransmission, the sender will skip segments with SACK flag set.  

TCP SACK implementation
=======================

The main TCP SACK implementation is located in :cpp:class:`TcpSack` featuring the conservative loss recovery algorithm based on SACK for TCP [Bla12]. 
Note that this algorithm has a different definition of a duplicate ACK when comparing to the conventional dupACK definition as in Tahoe, Reno, or NewReno, 
which requires the implementation to define a new routine ``TcpSack::SackDupAck ()`` to replace the regular ``TcpSocketBase::DupAck ()``. 
The heart of the algorithm is the `pipe` mechanism implemented in ``TcpSack::StartPipe ()`` routine, which allows additional data packet retransmissions
to recover multiple losses in a sending window and additional new segment transmission to fully utilize the available network bandwidth. 


References
==========

.. [Mat96] M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow, RFC 2018: TCP Selective Acknowledgment Options, October 1996. Available online at `<http://tools.ietf.org/html/rfc2018>`_.

.. [Bla12] E. Blanton, M. Allman, L. Wang, I. Jarvinen, M. Kojio, and Y. Nishida, RFC 6675: A Conservative Loss Recovery Algorithm Based on Selective Acknowledgment (SACK) for TCP, August 2012. Available online at `<https://tools.ietf.org/html/rfc6675>`_.

Validation
==========
The SACK option model is tested using :cpp:class:`TcpOptionTestSuite` class and :cpp:class:`TcpSackTestSuite` class defined in `src/internet/test/tcp-option-test.cc` and `src/internet/test/tcp-sack-test.cc`, respectively. These two test suites can be run using the following commands:

::

  $ ./waf configure --enable-examples --enable-tests
  $ ./waf build
  $ ./test.py -s tcp-option
  $ ./test.py -s tcp-sack
  
The TCP SACK model is tested using :cpp:class`Ns3TcpLossTestSuite` class defined in `src/test/ns3tcp-loss-test-suite.cc`, which can be run using the following command (after enabling tests):

::

  $ ./test.py -s ns3-tcp-loss

Example
=======
The SACK option and TCP SACK can be simulated using the example `tcp-variants-comparison.cc` located in ``examples/tcp``.