Contents

Introducci’on

• Los protocolos de solicitud de repetici’on autom’atica o protocolos ARQ (Automatic Repeat reQuest) retransmiten aquellos paquetes de datos que han llegado con errores.
• Utilizan c’odigos de detecci’on de errores.
• Nacieron como una alternativa automatizada a la “verificaci’on de eco”¹ [2].

1 El protocolo ARQ con parada y espera (stop and wait)

• Se trata del protocolo ARQ m’as sencillo. Se basa en las siguientes reglas:
  1. El emisor env’ia un paquete y espera a que el receptor confirme positiva o negativamente su recepci’on.
  2. El receptor env’ia un reconocimiento positivo² o ACK (ACKnowledgement) cuando el paquete ha llegado sin errores.
  3. El receptor env’ia un reconocimiento negativo o NAK (Negative AcKnowledgement) cuando el paquete ha llegado con errores, aunque esto es opcional³ .
  4. El emisor lanza un temporizador para cada paquete enviado con el objetivo de saber cu’anto tiempo debe esperar una confirmaci’on.

1.1 NAK vs s’olo-ACK

1.2 Numeraci’on de los paquetes

• Todos los paquetes deben ser enumerados para evitar duplicados.

1.3 Confirmaci’on de los paquetes duplicados

• Los paquetes duplicados deben confirmarse positivamente para evitar interbloqueos.

1.4 Numeraci’on de los paquetes de confirmaci’on

• Los paquetes de confirmaci’on deben enumerarse tambi’en para evitar la p’erdida de datos. En el ejemplo (izq), el primer “Datos 1” se pierde.

1.5 El protocolo falla si los paquetes se desordenan

• El enlace de transmisi’on debe ser punto a punto, es decir, los paquetes no pueden desordenarse [6].

1.6 Rendimiento pobre

• ARQ con parada y espera no es adecuado cuando los retrasos de extremo a extremo y las tasas de transmisi’on de los enlaces son altas [3, 5].

  

2 ARQ con retroceso a $n$ (go back $n$)

• En GBN, el emisor puede transmitir tantos paquetes ($n$) como sean necesarios para que no se tenga que esperar (dejando de transmitir datos) a un reconocimiento. A esto se le llama pipelining (v’ease el applet http://www.ace.ual.es/~vruiz/docencia/redes/teoria/applets/gbn.html).
• Ejemplo ($n=3$):

  

2.1 Longitud de la secuencia de conteo

• La longitud $l$ de la secuencia de conteo debe ser mayor que el n’umero de paquetes $n$ sin confirmar ($l>n$):

  

2.2 Tratamiento de los errores

• Un NAK$k$ significa que hay que retransmitir el paquete $k$ y siguientes.
• Ejemplo:

  

• Ejemplo:

  

• Los paquetes de datos que llegan fuera de secuencia, es decir, que no est’an precedidos de los paquetes anteriores, son descartados. Esto se hace porque de todas formas el emisor los va a retransmitir.

2.3 Confirmaci’on acumulativa

• Minimiza el n’umero de confirmaciones:
  1. Un ACK$k$ significa que todos los paquetes enviados antes que el $k$-’esimo paquete, junto con ’este paquete, han llegado con ’exito.
  2. Un NAK$k$ significa que todos los paquetes enviados antes que el $k$-’esimo han llegado con ’exito, pero el paquete $k$ debe ser retransmitido.

2.4 Piggybacking [6]

• En la pr’actica muchas veces tanto el emisor como el receptor son a su vez receptor y emisor (respectivamente). Una forma de disminuir el consumo de ancho de banda en este caso es transmitir las confirmaciones dentro de los paquetes de datos si estos se env’ian con la suficiente frecuencia.

3 ARQ con repetici’on selectiva (selective repeat o SR)

• GBN presenta un rendimiento pobre cuando los enlaces tienen altas tasas de transmisi’on, altas latencias y relativamente altas tasas de errores porque un error en un ’unico paquete de los que est’an viajando (que pueden ser muchos) implica la retransmisi’on de todos los que lo suceden en el enlace (que ya han sido transmitidos) [6].
• SR retransmite s’olo aquellos paquetes que han llegado con errores, es decir, cuando se recibe un NAK$k$ el emisor retransmite s’olo el paquete $k$. Ejemplo:

3.1 Longitud de la secuencia de conteo

• La longitud de la secuencia de conteo $l$ debe ser al menos el doble que el n’umero m’aximo $n$ de paquetes enviados sin confirmaci’on ($l\ge 2n$). En el ejemplo (izq.) A0 y B1 se duplican:

Tratamiento de los errores (otros ejemplos)

• Un NAK$k$ significa que hay que retrasmitir s’olo el paquete $k$:

4 Consideraciones sobre la eficiencia

4.1 Tasa de transmisi’on versus tasa de errores

• La tasa de transmisi’on se degrada al aumentar la tasa de errores [4]:

  

4.2 Latencia media versus tasa de errores

• La latencia media aumenta al aumentar la tasa de errores:

  

4.3 Tasa de transmisi’on versus tamaño del paquete

• La tasa de transmisi’on depende del tamaño del paquete [4]:

  

5 Soluci’on al desorden de los paquetes

• Es necesario utilizar secuencias de conteo suficientemente largas [1]. Por ejemplo, en TCP se utiliza $2^{32}$. Para el caso concreto del ejemplo planteado para parada y espera es suficiente contar hasta 3:

References