Práctica 4: End-to-End (Teoría de las Comunicaciones)

Volver

Header

SrcPort
DestPort
SequenceNum
Acknowledgment
HdrLen
0
Flags
AdvertisedWindow
Checksum
UrgPtr
Options (variable)
Data

Connection Setup

$\longleftarrow$ SYN, SequenceNum = x
$\longrightarrow$ SYN + ACK, SequenceNum = y, Acknowledgment = x + 1
$\longleftarrow$ ACK, Acnkowledment = y + 1

Invariants

LastByteAcked $\leq$ LastByteSent
LastByteSent $\leq$ LastByteWritten
LastByteRead $<$ NextByteExpected
NextByteExpected $\leq$ LastByteRcvd + 1

Fórmulas

Flow Control

Invariants

LastByteRcvd - LastByteRead $\leq$ MaxRcvBuffer
$AdvertisedWindow=MaxRcvBuffer-((NextByteExpected-1)-LastByteRead)$
$LastByteSent-LastByteAcked\leq AdvertisedWindow$

EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked)
LastByteWritten - LastByteAcked $\leq$ MaxSendBuffer
(LastByteWritten - LastByteAcked) + y $>$ MaxSendBuffer

Original Algorithm

$EstimatedRTT=\alpha \times EsimatedRTT+(1-\alpha )\times SampleRTT$
$TimeOut=2\times EsimatedRTT$

Jacobson/Karels Algorithm

$Difference=SampleRTT-EsimatedRTT$
$EsimatedRTT=EsimatedRTT+(\delta \times Difference)$
$Deviation=Deviation+\delta (\left|Difference\right|-Deviation)$
$TimeOut=\mu \times EsimatedRTT+\phi \times Deviation$
Actually: $\mu =1\ and\ \phi =4$
Implementation:

{
  SampleRTT -= (EsimatedRTT >> 3);
  EsimatedRTT += SampleRTT;
  if (SampleRTT < 0)
  {
      SampleRTT = -SampleRTT;
  }
  SampleRTT -= (Deviation >> 3);
  Deviation += SampleRTT;
  TimeOut = (EstimatedRTT >> 3) + (Deviation >> 1);
}

Something

 When the application produces data to send

   if both the avaiable data and the window $\geq$ MSS

     send a full segment

   else

     if there is unACKed data in flight

       buffer the new data until an ACK arrives

     else

       send all the new data now

TCP Congestion Control

Formulas

$Power={\frac {Throughtput}{Delay}}$

Additive Increase / Multiplicative Decrease

$MaxWindow=MIN(CongestionWindow,AdvertisedWindow)$
$EffectiveWindow=MaxWindow-(LastByteSent-LastByteAcked)$
$Increment=MSS\times {\frac {MSS}{CongestionWindow}}$
$CongestionWindow+=Increment$

Slow Start

{
  int cw = state->CongestionWindow;
  int incr = state->maxseg;
  if (cw > state->CongestionThreshold)
  {
    incr = incr * incr / cw;
  }
  state->CongestionWindow = MIN(cw + incr, TCP_MAXWIN);
}