Principles of reliable data transfer

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

Principios de Transferencia de Datos Fiables

(Fig. 1) RDT: modelo del servicio e implementación del servicio.

El problema de implementar un servicio de transferencia de datos fiables no sólo aparece en la capa de transporte, sino también en la capa de enlace y en la de aplicación, lo que lo deja en el puesto número uno de los problemas más importantes que afectan a las redes.

Este servicio consiste en disponer de un canal fiable de transferencia, donde ninguno de los bits de datos transferidos han sido corrompidos ni perdidos, y se entregan en el orden en que fueron enviados. Es responsabilidad de un protocolo de transferencia de datos fiable llevar a cabo lo anteriormente mencionado. Dicha tarea es complicada, dado que la capa que se encuentra por debajo del protocolo de transferencia de datos puede no ser fiable.

En la Fig.1, sección "a.Servicio proporcionado", se puede observar como funciona de manera simple la transferencia de datos unidireccional mediante un canal fiable. Por otra parte en la sección "b.Implementación del servicio", se ilustrala interfaz del protocolo de transferencia. El proceso consiste en que el lado emisor del protocolo RDT será invocado desde la capa superior mediante la llamada rdt_enviar( ), que pasará los datos a la capa superior en el lado receptor. En el lado del receptor, rdt_recibir( ) será llamado cuando llegue un paquete desde el lado receptor del canal. Una vez que el protocolo RDT desea suministrar datos a la capa superior, lo hará llamando a entregar_datos( ). Como detalle cabe mencionar que ambos lados, emisor y receptor, además de intercambiar paquetes que contengan datos, también intercambian paquetes de control, haciendo una llamada a udt_enviar( ) (donde UDT hace referencia a una transferencia de datos no fiable [Unreliable data transfer]).

En esta sección se utilizará el término "paquete" en vez de "segmento", y se abarcará solo la transferencia de datos unidireccional (Emisor -> Receptor).


Construcción de un Protocolo de Transferencia de Datos Fiable (RDT)

Se examinará una serie de protocolos en los que su complejidad irá aumentando, es decir, se irán perfeccionando cada vez más para prevenir todos los posibles casos negativos que se puedan dar a la hora de la transferencia de datos. El último que se verá es el protocolo de transferencia de datos fiable sin defectos.

RDT sobre un Canal Totalmente Fiable: rdt1.0

(Fig. 2) Protocolo rdt1.0

Este es para el caso más simple, en el cual el canal subyacente es totalmente confiable porque no hay pérdida de datos ni errores. En este protocolo tan simple no existe ninguna diferencia entre una unidad de datos y un paquete. Todo el flujo de paquetes va del emisor al receptor, puesto que como se dispone de un canal que es completamente fiable, no se necesita que exista un feedback por parte del receptor. A su vez, éste puede recibir los paquetes a la misma velocidad de envío que realiza el emisor. En la figura 1 se pueden observar tres capas; para el protocolo rdt1.0 se ocupa la de aplicación (capa superior) y de transporte (capa inferior a la anterior).

  • El emisor de rdt acepta los datos de la capa superior a través del suceso rdt_enviar(datos), mediante la acción crear_paquete(datos) crea un paquete que contiene los datos y lo envía al canal. El suceso rdt_enviar(datos) resulta de la llamada del procedimiento rdt_enviar() hecha por la aplicación de la capa superior.
  • El lado receptor de rdt a través del sucedo rdt_recibir(datos) recibe un paquete del canal subyacente y pasa los datos a la capa superior mediante la acción entregar_datos(datos). En la práctica, el suceso rdt_recibir(paquete) resultaría de una llamada desde el protocolo de la capa inferior a través de rdt_recibir().








RDT sobre un Canal con Errores de Bit: rdt2.0

Este método contempla un modelo más realista del canal subyacente, en el que los bits de un paquete pueden ser corrompidos al ser transmitidos, propagados o cuando acceden al buffer. Sin embargo, en esta etapa aún se considerará que todos los paquetes transmitidos son recibidos, independiente de los errores de sus bits. Aquí se utilizan mensajes de control que permiten al emisor conocer qué es lo que el receptor ha recibido correctamente y qué es lo que ha recibido con errores, lo cual por consecuencia tendrá que reenviar.

(Fig. 3) Protocolo para un canal con errores del bit.
  • Ejemplo de lo anterior:

Un mensaje largo a través del teléfono, en la que la persona que escucha el mensaje podría decir "ok" después de cada frase que escuche, comprenda y apunte. Si la persona receptora no oye una frase, le pedirá al emisor que la repita. Este protocolo de dictado de mensajes utiliza tanto reconocimientos positivos ("ok") como reconocimientos negativos ("repita por favor").

En una red de computadores, este tipo de transferencia de datos fiable basados en tales retransmisiones se conocen como protocolos automatic repeat request (ARQ). En éstos, se requieren tres capacidades de protocolo adicionales para gestionar la presencia de errores de bit:

a) Detección de errores: Se necesita en primera instancia un mecanismo que permita al receptor detectar que se han producido errores de bit. UDP utiliza el campo de suma de comprobación de Internet precisamente para lograr lo anterior. Se requiere que el emisor envíe al receptor bits adicionales, junto con los bits de los datos originales que se desean transferir, y dichos bits también se tendrán en cuenta para el cálculo de la suma de comprobación del paquete de datos rdt2.0.

b) Realimentación del receptor: Dado que el emisor y el receptor normalmente se ejecutan en sistemas terminales diferentes, separados por miles de kilómetros por ejemplo, la única forma de que el emisor sepa lo que ocurre en el receptor es que éste envíe explícitamente información de realimentación al emisor (mensajes ACK, NAK por ejemplo). De forma similar, el protocolo rdt2.0 enviará paquetes ACK y NAK de vuelta desde el receptor al emisor. En principio, estos paquetes sólo necesitan tener una longitud de un bit; un valor 0 indicaría un reconocimiento negativo (NAK) y un valor 1 indicaría un reconocimiento positivo (ACK).

c) Retransmisión: Un paquete que se recibe con errores en el receptor será retransmitido por el emisor.

En la figura 3.10, el protocolo del lado emisor está a la espera de datos procedentes de la capa superior. Cuando se produce el suceso rdt_enviar(datos), el emisor creará un paquee (pqtenv) conteniendo los datos que van a ser transmitidos, junto con una suma de comprobación del paquete y luego el paquete se envía mediante la operación udt_enviar(pqtenv). El protocolo del emisor está a la espera de un paquete de reconocimiento positivo ACK o negativo NAK procedente del receptor:

  • Si se recibe un paquete ACK: Este suceso está dado por rdt_recibir(pqtrcb) && esACK(pqtrcb) en la figura 3. El emisor sabe que el paquete más recientemente transmitido ha sido recibido correctamente y, por tanto, el protocolo vuelve al estado de espera de datos procedentes de la capa superior.
  • Si se recibe un reconocimiento negativo NAK, el protocolo retransmite el último paquete y espera a recibir un mensaje ACK o NAK del receptor en respuesta al paquete de datos retransmitido.

Cabe destacar que el emisor no enviará ningún nuevo fragmento de datos hasta estar seguro de que el receptor ha recibido correctamente el paquete que actualmente envió. Debido a este comportamiento, los protocolos como rdt2.0 se conocen como protocolos de parada y espera (stop and wait protocol). En la figura, la notación rdt_recibir(pqtrcb) && corrupto(pqtrcb) corresponde al suceso en el que se ha recibido un paquete y resulta ser erróneo.

Hasta ahora pareciera como si el protocolo funcionara perfectamente, sin embargo, no se ha tenido en cuenta la posibilidad de que el paquete ACK o NAK pueda estar corrompido. Como mínimo se tendrá que añadir bits de suma de comprobación a los paquetes ACK y NAK para detectar esos errores. La dificultad está en que si un paquete ACK o NAK está corrompido, el emisor no tiene forma de saber si el receptor ha recibido o no correctamente el último fragmento de datos transmitido. Existen tres posibilidades para gestionar los paquetes ACK o NAK corruptos:

  • Por ejemplo, si una persona que está dictando el mensaje no entiende la respuesta "ok" o "por favor, repita" del receptor, probablemente diría "¿cómo dice?", lo cual introduce un nuevo tipo de paquete del emisor al receptor en el protocolo. Pero, ¿qué ocurriría si el "cómo dice" está corrompido también? El receptor no tendría ni idea de si esa frase formaba parte del dictado o era una solicitud de que repitiera la última respuesta, por lo que probablemente respondería con un "¿cómo dice usted?". Y bueno, esta respuesta también podría estar alterada y así sucesivamente, complicando el problema.
  • Una segunda opción consistiría en añadir los suficientes bits de suma de comprobación como para permitir al emisor no sólo detectar, sino también recuperarse de los errores de bit. De este modo se resuelve el problema inmediato de un canal que puede corromper los paquetes de datos, pero no perderlos.
  • Una tercera forma consistiría en que el emisor reenviara el paquete de datos actual al recibir un paquete ACK o NAK alterado. Sin embargo, este método introduce paquetes duplicados, por lo tanto, el receptor no puede saber si un paquete entrante contiene datos nuevos o es una retransmisión.

Una solución sencilla a este nuevo problema consiste en añadir un nuevo campo al paquete de datos y hacer que el emisor numere sus paquetes colocando un número de secuencia en este campo. Entonces el receptor comprobará ese número de secuencia para determinar si el paquete recibido es una retransmisión o no. Con un número de secuencia de 1 bit bastará. En este punto se está suponiendo que se dispone de un canal que no pierde datos y los paquetes ACK y NAK no tienen que indicar el número de secuencia del paquete que están confirmando.

RDT sobre un Canal con Pérdidas y Errores de Bit: rdt3.0

(Fig. 4) Lado emisor de rdt3.0

Ahora además de bits corrompidos, el canal subyacente también puede perder paquetes. Se debe detectar la pérdida de paquetes y qué hacer cuando se pierde uno.

  • Ejemplo:

El emisor transmite un paquete de datos y puede ocurrir que éste se pierda o el mensaje ACK del receptor para ese paquete le pase lo mismo. En cualquiera de los dos casos anteriores, al emisor no le llega ninguna respuesta del receptor. El emisor puede retransmitir el paquete si está dispuesto a esperar el tiempo suficiente como para estar seguro de que se ha perdido. Pero ¿de cuánto tiempo se estaría hablando para estar seguro de esto? La respuesta es que el emisor tiene que esperar al menos un tiempo igual al retardo de ida y vuelta entre el emisor y el receptor, más una cierta cantidad de tiempo que será necesaria para procesar un paquete en el receptor.

En muchas redes, este retardo máximo es difícil de estimar y de conocer con precisión, además que el protocolo debiera recuperarse de la pérdida de paquetes tan pronto como fuera posible. Por consecuencia, el método que se utiliza es que el emisor seleccione juiciosamente un intervalo de tiempo en el que sea probable que un paquete se haya perdido, aunque no se pueda asegurar aquello (si dentro de ese intervalo de tiempo no se ha recibido un ACK, el paquete se retransmite).

Desde el punto de vista del emisor, la acción para cualquier caso será la de retransmitir; ya sea porque se ha perdido un paquete de datos o un mensaje ACK, o simplemente los dos anteriores están retardados. La implementación de un mecanismo de retransmisión basado en el tiempo requiere un temporizador de cuenta atrás que pueda interrumpir al emisor después de que haya transcurrido un determinado tiempo. Es por eso que el emisor necesitará poder:

  • Iniciar el temporizador cada vez que envíe un paquete por primera vez o sea retransmisión.
  • Responder a una interrupción del temporizador ejecutando las acciones apropiadas.
  • Detener el temporizador.


Dado que los números de secuencia de los paquetes alternan entre 0 y 1, el protocolo rdt3.0 se denomina en algunos casos protocolo de bit alternante.


Protocolo de Transferencia de Datos Fiable con Procesamiento en Cadena

El protocolo rdt3.0 si bien funciona de manera adecuada, es muy difícil que logre satisfacer el rendimiento esperado, sobre todo para las redes de alta velocidad actuales. Este problema se basa principalmente porque el rdt3.0 es un protocolo de parada y espera. Es por eso que se propone la siguiente solución:

Protocolo de parada y espera y protocolo con procesamiento en cadena.


En lugar de operar en el modo parada y espera, el emisor podría enviar varios paquetes sin esperar a los mensajes de reconocimiento. Por ejemplo, si el emisor enviara cuatro paquetes antes de tener que esperar a los paquetes de reconocimiento, la utilización de aquel se cuadruplicaría en forma aproximada. Se utiliza la técnica de pepelining o procesamiento en cadena, que es cuando muchos paquetes están en tránsito entre el emisor y receptor y pueden verse como el relleno de un conducto (pipeline). Este tipo de procesamiento tiene las siguientes consecuencias en los protocolos de transferencia fiables:

  • Dado que cada paquete en tránsito sin estar contando las retransmisiones, tiene que poseer un número de secuencia único, es por esto que el rango de números de secuencia tiene que incrementarse. Es así como pueden coexistir varios paquetes en tránsito, que mediante reconocimiento, no han sido confirmados.
  • El emisor y receptor podrían tener que almacenar más de un paquete en buffer.

Como mínimo, el emisor tendrá en el buffer los paquetes que han sido transmitidos pero que todavía no han sido reconocidos y también puede ser necesario almacenar del receptor los paquetes recibidos correctamente.

  • El rango necesario de los números de secuencia y los requisitos de buffer dependerán de la forma en que un protocolo de transferencia de datos responda a la pérdida, corrupción o excesivo retardo de paquetes. Para la recuperación de errores en procesamiento en cadena existen dos métodos: retroceder N y la repetición selectiva.

Protocolo Go-Back-N (GBN)

Números de secuencia en el emisor en el protocolo Go-Back-N.

En este protocolo el emisor puede trasmitir varios paquetes sin esperar a que sean reconocidos, hasta un máximo de N paquetes no reconocidos en el canal.

Se define la base como el número de secuencia del paquete no reconocido más antiguo y signumsec como el número de secuencia del siguiente paquete a enviar, de esta manera se pueden identificar los cuatro intervalos en rango de los números de secuencia.

Si observamos la imagen de la derecha, se puede distinguir un primer intervalo [0,base-1] equivalente a los paquetes que han sido trasmitidos y reconocidos. Luego un segundo intervalo [base,signumsec-1] corresponde a los paquetes que han sido enviados pero todavía no reconocidos. Después tenemos el intervalo [signumsec,base+N-1] para paquetes enviados de forma inmediata desde la capa superior. Finalmente tenemos un último intervalo, con números de secuencia mayores o iguales que "base+N", los que no pueden ser utilizados hasta que un paquete no reconocido que este en el canal sea reconocido (paquete con secuencia igual a "base").

  • Ejemplo:

Se ejemplificará el funcionamiento del protocolo GBN para un tamaño de ventana con N = 4. En base a esto el emisor transmite los paquetes 0 a 3 iniciando sus respectivos "timers", y para poder continuar, debe esperar a que uno o más paquetes sean reconocidos por el receptor. A medida que se reciben los sucesivos ACK (ACK0 y ACK1, en nuestro caso) la ventana se desplaza hacia adelante y el emisor puede transmitir nuevos paquetes (pqt4 y pqt5, respectivamente). Si se pierde un paquete, como sucede con "pqt2", los paquetes siguientes (3,4 y 5) no se reciben en orden y son descartados por el receptor. Una vez acabado el "timer" del paquete 2, éste se vuelve a enviar, luego se envian el paquete 3, 4 y 5, dándose inicio a una nueva iteración, hasta que todos lo paquetes sean recibidos en orden.

A pesar de que el funcionamiento del protocolo GBN parece "tonto" por el hecho de descartar paquetes que han llegado al receptor, pero no en el orden correcto, nos permite asegurarnos de que los datos enviados lleguen de manera intacta al receptor.

Para un mejor entendimiento sobre éste protocolo recomendamos revisar el siguiente video: Go-Back-N - Youtube


Repetición Selectiva (SR)

Espacios de números de secuencia del lado emisor y del lado receptor en el protocolo SR

A pesar del "eficiente" funcionamiento del protocolo GBN, todavia presenta problemas de rendimiento en algunos escenarios, como por ejemplo cuando existe retardo en la transmisión de paquetes, en este caso, el protocolo GBN podría llegar a retransmitir una gran cantidad de paquetes de manera innecesaria.

El protocolo SR de repetición selectiva, evita las retransmiciones innecesarias, haciendo que el emisor retransmita solo los paquetes que se sospeche que llegaron con error al receptor (es decir, se perdieron o estaban corrompidos). Para ésto el receptor debera confirmar individualmente qué paquetes ha recibido correctamente.

Cabe mencionar que la visión que tienen el emisor y el receptor de lo que se ha recibido o no, no son idénticas, es decir que las ventanas del emisor y del receptor no siempre coinciden.

Para la realización de este protocolo, se usará una ventana de tamaño "N", al igual que en GBN. El receptor de SR confirmará que un paquete se ha recibido correctamente si éste llega en el orden correcto o no. Los paquetes no recibidos en orden son almacenados en un buffer hasta que se reciban los paquetes que faltan (paquetes con números de secuencia menores), momento en que se entregara un lote de paquetes a la capa superior.

  • Ejemplo:

Se ejemplificará el funcionamiento del protocolo GBN para un tamaño de ventana con N = 4. En base a esto el emisor transmite los paquetes 0 a 3 iniciando sus respectivos "timers". El pqt2 se pierde y el pqt3 llega al receptor, pero dado que falta un paquete previo, éste se almacena en un buffer. A medida que se reciben los sucesivos ACK (ACK0 y ACK1, en nuestro caso) la ventana se desplaza hacia adelante, y se envían los paquetes 4 y 5 respectivamente, los que también serán almacenados en un buffer hasta que los paquetes faltantes sean recibidos. Dado que el pqt2 se había perdido, el emisor espera hasta que el "timer" termine para poder reenviarlo. Una vez sucedido esto, y que pqt2 llega al receptor, éste entrega el pqt2 junto a los 3 paquetes almacenados en buffer a la capa superior. Ahora se desplaza la ventana a los $ paquetes siguientes y se da inicio a una nueva iteración, hasta que todos lo paquetes sean recibidos.

Para un mejor entendimiento sobre éste protocolo recomendamos revisar el siguiente video: Selective-Repeat - Youtube

Referencias

  • J. F. Kurose, K.W. Ross. Computer Networking A Top Down Approach, 5th Edition. 2.2 The World Wide Web: HTTP.

Enlaces Externos

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas