Contents

1 TCP (Transmission Control Protocol) [5]

• Designed by Vint Cerf and Bob Kahn in 1981.
• Provides reliable, ordered, error-checked delivery of a stream of octets between programs running on the same or different hosts.

2 Servicios proporcionados

• Protocolo de transporte por excelencia en Internet [8, 1, 3].
• RFC’s 793 (principalmente), 854, 1122, 1323, 2018, 2581 y 2988.
• Transferencia fiable de datos (control de errores y de flujo) basado en un protocolo ARQ con pipelining (mezcla de GBN y SR).
• Es orientado a conexi’on (antes de transmitir ’esta se establece).
• Las conexiones son siempre unicast (entre dos procesos). No se puede realizar multicasting.
• Multiplexaci’on: el TCP distingue procesos dentro del mismo host a partir del puerto en el que escuchan y a qui’en estn escuchando.
• Control agresivo de la congesti’on (por el bien com’un).
• Full-duplex (comunicaci’on en ambos sentidos al mismo tiempo).
• Los procesos ven byte-streams, no datagramas o segmentos.

3 El contexto de trabajo

• Corre encima del IP (capa de red) lo que significa que los paquetes de datos se pueden perder, desordenar, duplicar y llegar con errores.
• Las latencias son muy variables lo que complica conocer la duraci’on de los temporizadores utilizados para conocer cundo hay que retransmitir los segmentos.
• Se implementa s’olo en los sistemas finales. Los routers no distinguen entre paquetes UDP o TCP (ellos ven datagramas, no conexiones).
• Supone que la red no proporciona informaci’on acerca de la congesti’on, lo que significa un ahorro considerable en la complejidad de los dispositivos de nivel 3 (routers) e inferiores.

4 Transmisin de datos

4.1 El segmento TCP

• Aunque las aplicaciones leen y escriben un flujo de bytes, el TCP agrupa los bytes en segmentos que son transmitidos como los datagramas UDP. Esto se hace para minimizar el overhead provocado por las cabeceras de los segmentos (20 bytes como mnimo).
• El tamao de cada segmento o MSS (Maxium Segment Size) depende de:
  1. El MTU (Maximum Transfer Unit)¹ de la red directamente conectada (en la que est el host). Si el tamao del segmento es ms grande que el MTU, el IP fragmentar los segmentos y si uno se pierde, el TCP tendra que retransmitir todo el segmento a nivel de transporte, no el sub-segmento (paquete) perdido a nivel de IP.
  2. El instante en que el emisor realiza un push del flujo (enviar ahora).
  3. Un tiempo mximo de espera.
• El formato del segmento TCP es:

• La pseudo-cabecera en TCP es idntica a la del UDP, excepto en que el campo PROTO$=6$.

4.2 EL proceso de desmultiplexacin

• Est basada en conexiones (par de puntos extremos), no en puertos.
• El TCP diferencia a un proceso dentro de un host a partir del par de puntos extremos

  (punto extremo origen, punto extremo destino)

  donde un punto extremo est formado por un par

  (IP del host, nmero de puerto).

• Por tanto, dos procesos distintos en un mismo host que usan en un mismo puerto pueden estar conectados a dos procesos distintos en otro host si estos utilizan puertos de salida diferentes. Esto puede ocurrir, por ejemplo, cuando un servidor est sirviendo concurrentemente a ms de un cliente usando un proceso distinto (ver el programa netstat de Unix).

4.3 Establecimiento de la conexin

Se utiliza el Algoritmo Three-Way Handshake:

• $x$ e $y$, los nmeros de secuencia inciales, suelen ser un nmeros aleatorios. Motivos:
  1. Para minimizar la probabilidad de que un segmento de una conexin anterior ya terminada y que se encuentra viajando por la red sea tomado errneamente por un segmento vlido de una conexin posterior entre los mismos puntos extremos [3].
  2. Para evitar el ataque del “nmero de secuencia” [6] que consiste en que un cliente “ilegal” puede suplantar a un cliente “legal” averiguando los nmeros de secuencia de los segmentos² , usando su IP y su puerto de salida. Tras la suplantacin el cliente “legal” podra acceder a datos restringidos o cerrar la conexin con el servidor.
• Los dos primeros segmentos son de control, ninguno puede transportar datos. El tercero s puede transportar datos [4]. A partir del tiempo en lnea azul, los procesos pueden emitir y recibir segmentos normales con datos.

4.4 Transmisin de datos urgentes

• Existen situaciones donde los datos deben entregarse a la aplicacin receptora lo antes posible. TCP indica esto en sus segmentos activando el flag URG.
• El tratamiento de los segmentos urgentes se produce slo entre las capas de transporte del emisor y del receptor. El IP es ajeno y trata por igual a todos los segmentos, independientemente de si el flag URG est activado o no.
• Cuando dicho flag est activado, UrgPtr indica hasta qu parte de los datos a partir del comienzo de los datos son de carcter urgente.
• Cuando llega un segmento con el flag UGR activado hasta el receptor, la parte urgente de ste es entregado al proceso receptor lo antes posible.

4.5 Cierre de la conexin

• Generalmente es el cliente el que cierra la conexin. Esto se hace con el Algoritmo Four-Way Handshake:

• El cliente, tras la emisin del segundo ACK espera tpicamente 2 MSL³ ($2\times 60$ segundos en la mayora de las implementaciones [7, 2]) que es intervalo de tiempo en el cual podra recibirse otro ACK+FIN del servidor si el ACK del ciente se perdiera y no llegara al servidor.

  Si esto ltimo ocurriera, el servidor reenviara el ACK+FIN y si este se retrasara lo suficiente, otra aplicacin en el host cliente podra establecer una nueva conexin con la aplicacin servidora, usando el mismo puerto de salida. Si a continuacin llegara el ACK+FIN retrasado, dicha conexin se cerrara puesto que el cliente considera que el servidor desea cerrar la conexin [7].

4.6 El diagrama de estados

• Frecuentemente se representa mediante una mquina de estados finita donde los nodos son estados y las transiciones se etiquetan mediante evento/accin.
• Los eventos pueden estar provocados por la llegada de nuevos segmentos con informacin de control (SYN, FIN, etc.) o porque la aplicacin local realiza una llamada al TCP (Apertura Pasiva, Cierre, etc.).
• No siempre que se produzca un evento necesariamente se genera una salida. En este caso slo cambiamos de estado.
• En rojo aparecen las transisiones normalmente seguidas por el cliente y en verde las seguidas por el servidor.

5 Control de flujo y de errores

• El TCP utiliza 2 colas circulares (ventanas deslizantes organizadas en bytes) en cada host, una para transmitir y otra para recibir.
• La estructura de la cola de emisin es la siguiente:

  

• La estructura de la cola de recepcin es:

  

• El control de flujo lo realiza el receptor controlando el tamao de la ventana emisora del emisor (campo Window).
• Cuando la ventana emisora del emisor se hace 0, el proceso emisor se bloquea, lo que significa que el receptor no va a recibir ms datos, al menos temporalmente.⁴ Como el emisor no recibe un segmento de control del receptor si ste no le enva un segmento con Window $>0$, el emisor peridicamente trata de enviarle 1 byte de datos al receptor. Mientras el receptor no puede recibir ms datos, un segmento con Window $=0$ es enviado. Sin embargo, cuando el receptor puede recibir datos, este campo es $>0$ y la ventana del emisor es ampliada.

5.1 El tamao de las ventanas

• El tamao inicial de la ventana se determina durante el establecimiento de la conexin.
• Cuando el factor de escala⁵ del campo Options es igual a 1, el tamao mximo de la ventana del emisor es de $64$ KB. Este lmite es demasiado bajo para la mayora de los enlaces de media y larga distancia (RTT $\ge 100$ ms) [7]:

  Enlace	Capacidad	$100$ ms $\times$ Capacidad
  T1	$1.5$ Mbps	$18$ KB
  Ethernet	$10$ Mbps	$122$ KB
  T3	$45$ Mbps	$549$ KB
  Fast Ethernet	$100$ Mbps	$1.2$ MB
  STS-3	$155$ Mbps	$1.8$ MB
  STS-12	$622$ Mbps	$7.4$ MB
  STS-24	$1.2$ Gbps	$14.8$ MB

• El receptor puede utilizar el factor de escala para aumentar hasta $2^{32}$ bytes el tamao de la ventana del emisor.

5.2 El tamao de los nmeros de secuencia

• TCP utiliza nmeros de secuencia de 32 bits y el tamao mximo de las ventanas del emisor y del receptor es de $2^{16}\times 2^{16}=2^{32}$ bytes. El primer factor $2^{16}$ est determinado por el campo Window (de 16 bits) y el segundo por un factor de escala presente en el campo Options (de 8 bits, aunque slo puede llegar a valer 16). Ntese que estando TCP basado en el protocolo ARQ con pipelining, excepto en el caso extremo se cumple siempre que la longitud de la secuencia de conteo es siempre superior al tamao mximo de la ventana emisora.
• Por desgracia esta condicin no es suficiente, pudindose dar el caso de que si la red retrasa suficientemente un segmento, ste puede “suplantar” a otro en un momento posterior de dicha u otra transmisin. Adems, este factor aumenta proporcionalmente con la tasa de transmisin de la red [3]. En otras palabras, teniendo en cuenta que el MSL $=60$ segundos, 32 bits son suficientes para la mayora de las situaciones, pero no para todas [7]:

  Enlace	Capacidad	Tiempo hasta wrap-around
  T1	$1.5$ Mbps	$6,4$ horas
  Ethernet	$10$ Mbps	$57$ minutos
  T3	$45$ Mbps	$13$ minutos
  Fast Ethernet	$100$ Mbps	$6$ minutos
  STS-3	$155$ Mbps	$4$ minutos
  STS-12	$622$ Mbps	$55$ segundos
  STS-24	$1.2$ Gbps	$28$ segundos

  
  Wrap-around = Situacin que se produce cuando el nmero de secuencia sobrepasa el lmite $2^{32}-1$ y comienza de nuevo por el principio.
• Para solucionar el problema, en el campo Options de los segmentos TCP se coloca una marca de tiempo. De esta forma el receptor puede saber cul de los dos segmentos que tienen el mismo nmero de secuencia es el ms viejo.

5.3 Retransmisin rpida

• El TCP no usa NAK’s. Sin embargo, cuando se pierde un segmento el emisor puede percatarse de ello antes de que expire su temporizador si recibe uno o ms ACK’s duplicados, es decir, cuando recibe un reconocimiento para un segmento que ya haba sido reconocido.
• En la prctica, cuando se reciben 3 ACK’s del mismo segmento no se espera a que expire el temporizador y se realiza una retransmisin rpida del segmento [3]. Los diseadores del TCP estimaron que esperar slo a una duplicacin del ACK podra fallar a la hora de estimar una prdida cuando en realidad lo que ha ocurrido es que un segmento ha adelantado a otro.

5.4 El sndrome de la ventana tonta

• Se genera con frecuencia cuando conectamos un emisor rpido a un receptor lento.
• El receptor consume los datos byte a byte, y con cada uno de ellos enva un segmento de confirmacin al emisor. El resultado es que los segmentos enviados slo contienen un byte de datos lo que consume muchos recursos de la red.⁶
• La misma situacin aparece si el emisor es demasiado ansioso y no espera a tener suficientes datos antes de enviarlos.
• Para prevenirlo:
  1. El receptor tratar de evitar el anunciar ventanas pequeas. En la prctica espera a recibir
     $$min\left(Window∕2,\text{MSS}\right)\text{bytes},$$

     donde Window es el tamao actual de la ventana del receptor. Esto implica que los ACK’s pueden retrasarse indefinidamente lo que supone un problema para el emisor (para el clculo del time-out) y para la red (por las retransmisiones innecesarias debidos a dichos retrasos). En la prctica el TCP limita el retraso mximo de un ACK a $500$ ms.

  2. El emisor tratar de evitar el usar segmentos pequeos (tinygrams), es decir, acumular datos hasta generar segmentos iguales al MSS mientras no reciba un ACK. As, si la aplicacin emisora es el cuello de botella y la aplicacin receptora no est ansiosa (no enva ACK’s constantemente), el tamao de los segmentos ser grande. A este procedimiento se le conoce como Algoritmo de Nagle.

6 Control de la congestin

• Si el TCP percibe que la red se est congestionando disminuye la tasa de transmisin y viceversa.
• Un emisor generalmente no conoce dnde ni por qu se est produciendo la congestin. Simplemente experimenta un incremento en los RTT’s y tal vez reciba algn paquete ICMP para informar de esta situacin. Ante ello, el TCP debe reducir la tasa de transmisin [3].
• Si la congestin se hace ms severa los routers comienzan a descartar paquetes. El TCP debe percatarse de este problema y no retransmitirlos hasta que la congestin cese.
• Por este motivo, el tamao de la ventana emisora no slo depende de lo que indica el receptor (control del flujo), sino que tambin va a tener en cuenta el nivel de congestin.
• En la prctica, el tamao de la ventana emisora $SenderWindowSize$ va a ser igual al menor del tamao indicado por el receptor Window y un valor $CongestionWindowSize$ impuesto por el nivel de congestin de la red, es decir,
  $$SenderWindowSize=min\left(Window,CongestionWindowSize\right).$$

  El valor $CongestionWindowSize$ se calcula siguiendo las siguientes reglas:

  1. Modo de arranque (relativamente) lento en el que se duplica $CongestionWindowSize$ con cada ACK recibido. Este modo se utiliza desde que desaparece la situacin de congestin hasta que se alcanza la mitad del anterior valor de $CongestionWindowSize$ (que en la grfica se llama Threshold).
  2. Modo de prevencin de la congestin en el que $CongestionWindowSize$ crece en un MSS por cada ACK recibido. Este modo perdura hasta que se pierde un segmento[1].
  3. Cuando se detecta la prdida de un segmento por triple ACK recibido, entonces $CongestionWindowSize\leftarrow CongestionWindowSize∕2$ (este hecho no se muestra en la grfica).
  4. Cuando se detecta la prdida de un segmento porque expira su temporizador, entonces $CongestionWindowSize\leftarrow 1$ (este hecho se muestra en la grfica).

6.1 El tamao de los time-outs

• Cada vez que se enva un segmento, el TCP arranca un temporizador y espera el correspondiente ACK. Si se termina el tiempo antes de que se confirme positivamente el segmento (recurdese que no se utilizan confirmaciones negativas), el TCP asume que dicho segmento se perdi o corrompi, y lo retransmite.
• El problema radica en que las redes IP poseen latencias muy variables debido a su tamao, heterogeneidad, variacin de la carga, nivel de congestin, etc. Por este motivo el TCP utiliza un algoritmo adaptativo para calcular los time-outs.

6.1.1 El algoritmo original

Estima el RTT como

donde:

$EstimatedRTT$

es la estimacin del RTT,

$SampleRTT$

es la medida del ltimo RTT (medido como la diferencia en tiempo entre el instante en que se enva el segmento hasta que se recibe su confirmacin) y

$\alpha$

es un nmero entre $0$ y $1$ de tal forma que si $\alpha \approx 0$ entonces tiene mayor peso la ltima medida del RTT, y si $\alpha \approx 1$ entonces $EstimatedRTT$ es menos dependiente de $SampleRTT$. La especificacin original del TCP recomienda que $0.8\le \alpha \le 0.9$.

Finalmente, la estimacin para el time-out es

6.1.2 El Algoritmo de Karn/Partridge

El algoritmo original no funciona correctamente cuando ocurre una retransmisin. En esta situacin, el emisor no puede saber si el ACK recibido se corresponde con la primera o la segunda transmisin (problema de la ambigüedad del ACK). Si supone que es con la primera y no ocurre as, el $SampleRTT$ medido sera demasiado largo. Si supone que es con la segunda y esto no es cierto, el clculo es demasiado corto. Grficamente:

Ambos errores son perjudiciales para el clculo del $TimeOut$:

• Si el $SampleRTT$ (y por lo tanto el $TimeOut$) es ms grande de lo que debiera ser, las retransmisiones ocurrirn con un periodo superior. As, el siguiente $SampleRTT$ tras una retransmisin tender a crecer, y as sucesivamente. En consecuencia, un $TimeOut$ excesivamente grande provoca a la larga una infrautilizacin de los enlaces.
• Si el $SampleRTT$ (y por lo tanto el $TimeOut$) es errneamente pequeo, el emisor retransmitir innecesariamente antes de recibir el correspondiente ACK. Esto provocar de nuevo que el $SampleRTT$ sea errneamente pequeo y as sucesivamente hasta llegar a una situacin de equilibrio donde en promedio cada segmento se retransmite 1 vez. Por tanto, un $TimeOut$ excesivamente pequeo incrementar la congestin de los enlaces.

La solucin:

Estimar el RTT slo para los segmentos que no son retransmitidos acarrea un nuevo problema. Supongamos que debido a un aumento en la carga de la red o de la congestin, el RTT aumenta por encima del time-out, lo que provoca una retransmisin. Como el TCP va a ignorar el RTT de los segmentos retransmitidos, nunca va a actualizar la estimacin para el RTT mientras las latencias sigan siendo altas y el ciclo continuar. Por este motivo, adems:

El motivo de este aumento exponencial del time-out obedece a que normalmente un aumento en las latencias se debe a problemas de congestin y ante esta situacin lo mejor es disminuir rpidamente la frecuencia de las retransmisiones.

6.1.3 El Algoritmo de Jacobson/Karels

• El algoritmo bsico no funciona cuando los niveles de congestin son altos, ya que las latencias son muy variables.
• La mejora propuesta por Jacobson y Karels consiste en tener en cuenta adems la desviaci’on estad’istica de los RTT’s, no slo su media. Intuitivamente, si la desviaci’on es baja, entonces el ’ultimo $SampleRTT$ es una medida fiable. Por otra parte, una desviaci’on alta significa que el ’ultimo $SampleRTT$ no deber’ia ser considerado con tanto peso a la hora de calcular $TimeOut$.
• De esta forma, el clculo actual del time-out en el TCP en la inmensa mayor’ia de los sistemas operativos es
  $$\begin{array}{ccc}\multicolumn{3}{c}{\text{/* Compute the statistical deviation */}}\\ \hfill Diff& \hfill \leftarrow \hfill & SampleRTT-EstimatedRTT,\hfill \\ \hfill DevRTT& \hfill \leftarrow \hfill & DevRTT+\rho \times \left(\left|Diff\right|-DevRTT\right),\hfill \\ \hfill & \hfill \hfill & \hfill \\ \multicolumn{3}{c}{\text{/* Compute the estimated RTT */}}\\ \hfill EstimatedRTT& \hfill \leftarrow \hfill & EstimatedRTT+\delta \times Diff,\hfill \\ \hfill & \hfill \hfill & \hfill \\ \multicolumn{3}{c}{\text{/* Compute the time-out */}}\\ \hfill TimeOut& \hfill \leftarrow \hfill & EstimatedRTT+4\times DevRTT,\hfill \end{array}$$

  donde:

  • $0\le \delta \le 1$ es un factor que mide lo que $Diff$ afecta al nuevo clculo del RTT y
  • $0\le \rho \le 1$ es otro factor que hace lo mismo con la desviacin estadstica del RTT.

• Un ejemplo real [3]:

  

References