Commits

Anonymous committed 928f9b5

Added details on TCP cong control basics

Comments (0)

Files changed (6)

oppgave/chapter2.tex

     80's \citenp{cong-control-avoidance-jacobson:1988}.
 \end{enumerate}
 
+To meet the requirement for reliable transmission, the \Gls{TCP} header in each
+packet contains a fields for the sequence number of the payload and the length.
+This is used to keep track of what parts of the data stream has been sent and
+what has been verified as received by the receiver. It also has a
+Acknowledgement number which refers to the sequence number of the next expected
+data. If the sender notices that the ACK-number is not advancing, it will
+retransmit the data.
+
 \atodo[inline]{Add sections on different congestion control algorithms?}
 
 \subsection{Congestion Control mechanism}
 The congestion control mechanism in \gls{TCP} is the mechanism responsible for
 keeping the data flow in control to avoid overflowing the network. It is based
 on controlling the network resources with the goal of an optimal fair allocation
-for the network as a whole.
+for the network as a whole. The basis for the modern congestion control
+mechanisms in \gls{TCP} consists of the following (as described in
+\citerfc{rfc5681})
+
+\begin{enumerate}[leftmargin=1cm,itemindent=-5mm,label=\large\textbullet]
+  \litem{\Gls{slow-start}} The first phase of a TCP streams development is
+  controlled by \gls{slow-start}. In this phase the stream will build the
+  \gls{CWND} exponentially until it reaches the network limit. It keeps building
+  the \gls{CWND} until it experiences loss or the \gls{CWND} has reached the
+  \gls{slow-start} threshold.
+
+  \litem{\Gls{congestion-avoidance}} After the initial \gls{slow-start} phase,
+  the \gls{congestion-avoidance} phase controls the \gls{CWND}. This phase is
+  also referred to as the \gls{AIMD} algorithm described in
+  \citen{cong-control-avoidance-jacobson:1988}. In this phase the \gls{CWND} is
+  grown at a slow rate (additive increase) and reduced to half the send window
+  size (Multiplicative Decrease) in the case loss occurs.
+
+  \litem{\gls{fast-retransmit}} In the case of packet loss the sender must
+  retransmit the data at some point. To avoid having to wait for the RTO to
+  trigger, the \gls{fast-retransmit} algorithm will use duplicate \glspl{ACK} to
+  detect loss. If a packet is lost, the receiver notices a gap in the sequence
+  numbers of the received packets. For each subsequent packet received that is
+  not in-sequence on that connection, the receiver generates a \gls{dupACK},
+  until the missing segment is filled. With \gls{fast-retransmit} a
+  retransmission is triggered after three \glspl{dupACK} is received. To avoid
+  triggering a retransmission in case of packet duplication or when packets
+  arrive out of order (caused by different network routes), the limit is set
+  to three \glspl{dupACK}\citerfcp{rfc5681}.
+
+  \litem{\gls{fast-recovery}} When a retransmission is initiated by
+  \gls{fast-retransmit} the \gls{fast-recovery} handles sending new data until
+  an \gls{ACK} that acknowledges new data is received. Immediately after the
+  \gls{fast-retransmit}, the \gls{ssthresh} must be set to no more than what is
+  given in \cref{eqn:fast-recovery}, and the \gls{CWND} set to \gls{ssthresh}
+  plus 3*SMSS. When the first \gls{ACK} that acknowledges new data is received,
+  the \gls{CWND} set to \gls{ssthresh}. Given that the \gls{CWND} is set to
+  \gls{ssthresh} when new data is \gls{ACK}ed, \gls{congestion-avoidance} is used to
+  increase the \gls{CWND} further on.
+
+\end{enumerate}
+
+\begin{equation}
+ \label{eqn:fast-recovery}
+ ssthresh = max (FlightSize / 2,\hspace{1mm} 2*SMSS)
+\end{equation}
+
+\subsubsection{TCPs Exponential Backoff}
+
+With no packet loss, \gls{TCP} will not have any major drawbacks compared to
+\gls{UDP} speed-wise, but when packets are lost, \gls{TCP}'s behavior will have
+critical impact on the user experience. When a packet is sent, the \gls{RTO}
+defines for how long the sender will wait for an \gls{ACK} before the packet is
+retransmitted. Each time an \gls{RTO} is triggered, the \gls{RTO} timer is
+doubled. This is called the exponential backoff algorithm, and is part of the
+\gls{congestion-avoidance} techniques in \gls{TCP}. This makes the sender wait even
+longer before retransmitting packets that have not been \gls{ACK}ed, and if the
+retransmitted packet is lost as well, the \gls{RTO} timer is doubled again to
+further decrease the pressure on the network. This should have a positive effect
+on a congested network, at least that is the theory. However, performance
+analysis on the exponential backoff algorithm has shown contradictory results
+\citenp{performance-analysis-of-exponential-backoff-2005}.
+
+\feedback[inline]{Carsten: Not
+  everyone believes this today, was true for ultra-low-BW}
+
+
+Time-dependent \gls{thin-stream} services will contribute less to congestion
+than greedy streams due to the few and small packets, so the results of the
+exponential backoff can be said to make\feedback{Carsten: Meaning?} a
+disproportionate decrease in the service quality compared to the amount of
+traffic and congestion they produce.
+
+
+\subsubsection{Measuring fairness}
 
 A popular way of measuring fairness in networks is \gls{jains-fairness-index}
 (\cref{eqn:jains-fairness-index}). The fairness index is calculated by using the
 \end{enumerate}
 
 
-\subsection{TCPs Exponential Backoff}
-
-With no packet loss, \gls{TCP} will not have any major drawbacks compared to
-\gls{UDP} speed-wise, but when packets are lost, \gls{TCP}'s behavior will have
-critical impact on the user experience. When a packet is sent, the \gls{RTO}
-defines for how long the sender will wait for an \gls{ACK} before the packet is
-retransmitted. Each time an \gls{RTO} is triggered, the \gls{RTO} timer is
-doubled. This is called the exponential backoff algorithm, and is part of the
-congestion avoidance techniques in \gls{TCP}. This makes the sender wait even
-longer before retransmitting packets that have not been \gls{ACK}ed, and if the
-retransmitted packet is lost as well, the \gls{RTO} timer is doubled again to
-further decrease the pressure on the network. This should have a positive effect
-on a congested network, at least that is the theory. However, performance
-analysis on the exponential backoff algorithm has shown contradictory results
-\citenp{performance-analysis-of-exponential-backoff-2005}.
-
-\feedback[inline]{Carsten: Not
-  everyone believes this today, was true for ultra-low-BW}
-
-
-Time-dependent \gls{thin-stream} services will contribute less to congestion
-than greedy streams due to the few and small packets, so the results of the
-exponential backoff can be said to make\feedback{Carsten: Meaning?} a
-disproportionate decrease in the service quality compared to the amount of
-traffic and congestion they produce.
-
-\subsection[TCP's Fast retransmit]{\acrshort{TCP}'s \gls{fast-retransmit}}
-
-If a packet is lost, the receiver notices a gap in the sequence numbers of the
-received packets. For each subsequent packet received that is not in-sequence on
-that connection, the receiver generates a \gls{dupACK}, until the missing
-segment is filled. With \gls{fast-retransmit} a retransmission is triggered
-after three \glspl{dupACK} is received\citerfcp{rfc5681}. In case some packets
-take different routes and therefore arrives out of order, the limit of three
-\glspl{dupACK} should \feedback[inline]{Your opinion about the truthfulness of
-  this statement remains unclear. By whose account should it?} be a fairly
-certain sign that a loss has occurred.
 
 \section{Thin stream modifications}
 
 
 In the most basic form, \gls{TCP} detects data loss by the lack of \glspl{ACK}.
 If an \gls{RTO} occurs, \gls{TCP} will expect that the packet was lost and needs
-a retransmission. The timer value depends on, among other things,
-estimations of the \gls{RTT} between the sender and receiver, also called
-\gls{srtt}. The greater the \gls{RTO} timer value, the longer it takes for a
-retransmission to be sent, and the data to arrive correctly at the
-receiver.
+a retransmission. The timer value depends on, among other things, estimations of
+the \gls{RTT} between the sender and receiver, also called \gls{srtt}. The
+greater the \gls{RTO} timer value, the longer it takes for a retransmission to
+be sent, and the data to arrive correctly at the receiver.
 
 The \gls{RDB} modifications which we call the \gls{rdb-prototype} modified the
 buffers in the \gls{tcp-output-queue} by prefixing the payload of previous

oppgave/chapter3.tex

 criteria that an \gls{RDB} stream can not get an advantage throughput-wise over
 a greedy \gls{TCP} stream in a congested network.
 
-Problems may arise with different congestion avoidance queuing mechanisms. In a
-\gls{ECN} scenario, the \gls{ECN} flag will be ACKed back to the sender which
-would let the sender do adjustments. However, with \gls{RED}, incoming packets
-are dropped before the queue is full by a probability function that depends on a
-random value and the amount of packets currently in the queue. A \gls{TCP}
-stream will react to the loss of one packet, but with a \gls{RDB} stream, the
-loss would be hidden by the next packet with redundant data. In this case
-\gls{RDB} would get an advantage over other streams.
+Problems may arise with different \gls{congestion-avoidance} queuing mechanisms.
+In a \gls{ECN} scenario, the \gls{ECN} flag will be ACKed back to the sender
+which would let the sender do adjustments. However, with \gls{RED}, incoming
+packets are dropped before the queue is full by a probability function that
+depends on a random value and the amount of packets currently in the queue. A
+\gls{TCP} stream will react to the loss of one packet, but with a \gls{RDB}
+stream, the loss would be hidden by the next packet with redundant data. In this
+case \gls{RDB} would get an advantage over other streams.
 
 A solution to this could be to restrict how the \gls{CWND} grows for \gls{RDB}
 streams. If data has been bundled, reduce the amount by which the \gls{CWND}
 \end{ccode}
 \captionof{codelisting}{Relevant code from the function \glsentryname{tcp-data-queue} in tcp_input.c}
 
-\subsubsection{TCP Friendly Rate Control (TFRC)}
-\gls{TFRC} defined in \citerfc{rfc5348}. \atodo[inline]{Check if this is relevant?}
-
 \section{RDB implementation}\label{sect:implementation-details}
 
 The new \gls{RDB} implementation is modeled after the suggestion by Ilpo
 \end{enumerate}
 
 
+\subsubsection{TCP Friendly Rate Control (TFRC)}
+\gls{TFRC} defined in \citerfc{rfc5348}. \atodo[inline]{Check if this is relevant?}
+
 \subsubsection{Modify slow start threshold}
 The congestion control module operation entry point \code{.ssthresh} is used to
 retrieve the slow start threshold. The ssthresh implementation for reno can be
 instead of to half as is done in \gls{tcp-reno}
 (\cref{code-tcp-cong-ssthresh-to-half-lineref} of
 \namecref{code-tcp-cong-ssthresh} \labelcref{code-tcp-cong-ssthresh}).
+This is the same as is TCP nice \citen{cong-control-advancements-in-lunux-2006}.
 
 \codebox{%
 listing and comment, % Override default value (listing only)

oppgave/glossaries.tex

 \newacronym{QOS}{QOS}{Quality of service}
 \newacronym{MTU}{MTU}{Maximum Transmission Unit}
 \newacronym{RTO}{RTO}{retransmission timeout}
+\newacronym{AIMD}{AIMD}{Additive Increase Multiplicative Decrease}
+
 
 % --------------------------
 % ----  TCP specific   -----
 \newacronym{ECN}{ECN}{Explicit Congestion Notification}
 \newacronym{dupACK}{dupACK}{Duplicate Acknowledgement}
 
+\newglossaryentry{ssthresh} {%
+  name={ssthresh},%
+  description={The slow start threshold for the \gls{CWND}. When the \gls{CWND}
+    is greater or equal to this value, congestion avoidance is used},%
+}
+
+
 \newglossaryentry{thin-linear-timeout} {%
   name={Linear Retransmission Timeout},%
   description={is a tcp option in the Linux Kernel implemented and suggested in
 }
 
 \newglossaryentry{slow-start} {%
-  name={TCP Slow-start},%
+  name={slow-start},%
   description={is an algorithm which is used to grow the congestion window after
     a loss event},%
 }
 
+\newglossaryentry{congestion-avoidance} {%
+  name={congestion avoidance},%
+  description={is a phase uses the \gls{AIMD} algorithm to control the \gls{CWND}},%
+}
+
 \newglossaryentry{fast-recovery} {%
   name={Fast Recovery},%
-  description={is a variation to the slow start algorithm used after a fast
-    retransmit},%
+  description={is a variation to the congestion control algorithms that handles
+    the sending of new data after a \gls{fast-retransmit}},%
 }
 
 \newglossaryentry{fast-retransmit} {%

oppgave/include/pdfstyle.sty

     pdfsubject={\thesistitle},
     pdfcreator={\authorname},
     pdfproducer={\authorname},
-    pdfkeywords={TCP} {Netorking}{Linux kernel},
+    pdfkeywords={TCP}{Netorking}{Linux kernel},
     %bookmarksopen={true},
     %bookmarksopenlevel={1},
   }
 citecolor=black,  % Color of citations
 linktoc=all,
 plainpages=false,
-pagebackref=false,
-backref=false,
+%pagebackref=true,
+%backref=true,
 urlcolor=black]{hyperref}   % Reference package, must be before cleveref
 \usepackage[all]{hypcap}    % Link to figures (\ref{label}) go to the image,
                             % and not the caption (Default value is true)
 % #################################
 % ########  Begin content  ########
 \begin{document}
-\pagenumbering{Roman}
 \hypertarget{coverpage}{}
+\bookmark[dest=coverpage,level=0]{Master's Thesis}
+
 \ififorside
 %\uiosloforside[kind=\thesistype, author=\authorname]
-\bookmark[dest=coverpage,level=0]{UIO}
+
+\pagenumbering{Roman}
 
 \maketitle
 \tableofcontents

oppgave/references.bib

  keywords = {BEB, backoff algorithm, exponential backoff, medium access delay, performance analysis, throughput, primary},
 }
 
-% Detection of Duplicate Packets: tools.ietf.org/html/rfc2883#section-5
+@inproceedings{cong-control-advancements-in-lunux-2006,
+ title = {Congestion control advancements in {L}inux},
+ author = {Mcdonald, Ian and Nelson, Richard},
+ booktitle = {Linux {C}onf {AU}},
+ keywords = {aimd, avoidance, bic, ccid, congestion control, dccp, h-tcp, linux, netem, ostra, tcp, tcp-hybla, tcpdump, vegas, westwood},
+ month = jan,
+ year = {2006}
+}