Un protocolo de ventana deslizante es una característica de los protocolos de transmisión de datos basados en paquetes . Los protocolos de ventana deslizante se utilizan cuando se requiere una entrega confiable de paquetes en orden, como en la capa de enlace de datos ( OSI capa 2 ), así como en el Protocolo de control de transmisión (TCP). También se utilizan para mejorar la eficiencia cuando el canal puede incluir una latencia alta .
Los sistemas basados en paquetes se basan en la idea de enviar un lote de datos, el paquete , junto con datos adicionales que permiten al receptor asegurarse de que se recibió correctamente, tal vez una suma de verificación . El paradigma es similar a una ventana que se desliza hacia los lados para permitir la entrada de paquetes nuevos y rechazar los que ya han sido reconocidos. Cuando el receptor verifica los datos, envía una señal de reconocimiento , o "ACK", de vuelta al remitente para indicarle que puede enviar el siguiente paquete. En un simple protocolo de solicitud de repetición automática (ARQ), el remitente se detiene después de cada paquete y espera a que el receptor reciba un ACK. Esto asegura que los paquetes lleguen en el orden correcto, ya que solo se puede enviar uno a la vez.
El tiempo que tarda en recibirse la señal ACK puede representar una cantidad significativa de tiempo en comparación con el tiempo necesario para enviar el paquete. En este caso, el rendimiento general puede ser mucho más bajo de lo que teóricamente es posible. Para solucionar esto, los protocolos de ventana deslizante permiten que se envíe un número seleccionado de paquetes, la ventana , sin tener que esperar un ACK. Cada paquete recibe un número de secuencia y los ACK devuelven ese número. El protocolo realiza un seguimiento de los paquetes que han recibido ACK y, cuando se reciben, envía más paquetes. De esta forma, la ventana se desliza a lo largo del flujo de paquetes que componen la transferencia.
Las ventanas corredizas son una parte clave de muchos protocolos. Es una parte clave del protocolo TCP, que inherentemente permite que los paquetes lleguen fuera de orden, y también se encuentra en muchos protocolos de transferencia de archivos como UUCP-g y ZMODEM como una forma de mejorar la eficiencia en comparación con los protocolos sin ventanas como XMODEM .
Concepto basico
Conceptualmente, a cada parte de la transmisión (paquetes en la mayoría de las capas de enlace de datos, pero bytes en TCP) se le asigna un número de secuencia consecutivo único, y el receptor usa los números para colocar los paquetes recibidos en el orden correcto, descartando los paquetes duplicados e identificando los que faltan. . El problema con esto es que no hay límite en el tamaño del número de secuencia que se puede requerir.
Al poner límites al número de paquetes que se pueden transmitir o recibir en un momento dado, un protocolo de ventana deslizante permite que se comunique un número ilimitado de paquetes utilizando números de secuencia de tamaño fijo. El término "ventana" en el lado del transmisor representa el límite lógico del número total de paquetes que aún no han sido reconocidos por el receptor. El receptor informa al transmisor en cada paquete de reconocimiento el tamaño máximo actual del búfer del receptor (límite de ventana). El encabezado TCP utiliza un campo de 16 bits para informar al remitente del tamaño de la ventana del receptor. Por lo tanto, la ventana más grande que se puede utilizar es 2 16 = 64 kilobytes.
En el modo de inicio lento, el transmisor comienza con un recuento bajo de paquetes y aumenta el número de paquetes en cada transmisión después de recibir los paquetes de reconocimiento del receptor. Por cada paquete de ack recibido, la ventana se desliza por un paquete (lógicamente) para transmitir un nuevo paquete. Cuando se alcanza el umbral de la ventana, el transmisor envía un paquete por un paquete de confirmación recibido.
Si el límite de la ventana es de 10 paquetes, en el modo de inicio lento, el transmisor puede comenzar a transmitir un paquete seguido de dos paquetes (antes de transmitir dos paquetes, se debe recibir un paquete de confirmación), seguido de tres paquetes y así sucesivamente hasta 10 paquetes. Pero después de alcanzar los 10 paquetes, las transmisiones adicionales se restringen a un paquete transmitido por un paquete de confirmación recibido. En una simulación, esto parece como si la ventana se moviera una distancia de paquete por cada paquete de confirmación recibido. En el lado del receptor, la ventana también mueve un paquete por cada paquete recibido.
El método de ventana deslizante garantiza que se evite la congestión del tráfico en la red. La capa de aplicación seguirá ofreciendo datos para su transmisión a TCP sin preocuparse por los problemas de congestión del tráfico de la red, ya que TCP en el lado del remitente y del receptor implementan ventanas deslizantes del búfer de paquetes. El tamaño de la ventana puede variar dinámicamente según el tráfico de la red.
Para obtener el mayor rendimiento posible , es importante que el protocolo de ventana deslizante no obligue al transmisor a dejar de enviar antes de un tiempo de retardo de ida y vuelta (RTT). El límite de la cantidad de datos que puede enviar antes de detenerse a esperar una confirmación debe ser mayor que el producto de retardo de ancho de banda del enlace de comunicaciones. Si no es así, el protocolo limitará el ancho de banda efectivo del enlace.
Motivación
En cualquier protocolo de comunicación basado en la solicitud de repetición automática para el control de errores , el receptor debe reconocer los paquetes recibidos. Si el transmisor no recibe un acuse de recibo dentro de un tiempo razonable, reenvía los datos.
Un transmisor que no recibe un acuse de recibo no puede saber si el receptor realmente recibió el paquete; puede ser que se haya perdido o dañado en la transmisión. Si el mecanismo de detección de errores revela corrupción, el receptor ignorará el paquete y el receptor enviará un acuse de recibo negativo o duplicado. El receptor también puede configurarse para no enviar ningún acuse de recibo. De manera similar, el receptor generalmente no está seguro de si se están recibiendo sus acuses de recibo. Puede ser que se envió un acuse de recibo, pero se perdió o se corrompió en el medio de transmisión. En este caso, el receptor debe acusar recibo de la retransmisión para evitar que los datos se reenvíen continuamente, pero de lo contrario debe ignorarlos.
Operación de protocolo
El transmisor y el receptor tienen cada uno un número de secuencia actual n t y n r , respectivamente. Cada uno de ellos también tiene un tamaño de ventana w t y w r . Los tamaños de las ventanas pueden variar, pero en implementaciones más simples son fijos. El tamaño de la ventana debe ser mayor que cero para que se realice algún progreso.
Como se implementa típicamente, n t es el siguiente paquete que se transmitirá, es decir, el número de secuencia del primer paquete aún no transmitido. Asimismo, n r es el primer paquete que aún no se ha recibido. Ambos números aumentan monótonamente con el tiempo; solo aumentan.
El receptor también puede realizar un seguimiento del número de secuencia más alto recibido hasta ahora; la variable n s es uno más que el número de secuencia del número de secuencia más alto recibido. Para receptores simples que solo aceptan paquetes en orden ( w r = 1), esto es lo mismo que n r , pero puede ser mayor si w r > 1. Tenga en cuenta la distinción: se han recibido todos los paquetes por debajo de n r , ningún paquete por encima Se han recibido n s , y entre n r y n s , se han recibido algunos paquetes.
Cuando el receptor recibe un paquete, actualiza sus variables apropiadamente y transmite un acuse de recibo con el nuevo n r . El transmisor realiza un seguimiento del reconocimiento más alto que ha recibido n a . El transmisor sabe que todos los paquetes hasta, pero sin incluir n una han sido recibidas, pero no está segura de paquetes entre n un e n s ; es decir, n a ≤ n r ≤ n s .
Los números de secuencia siempre obedecen la regla de que n a ≤ n r ≤ n s ≤ n t ≤ n a + w t . Es decir:
- n a ≤ n r : El mayor reconocimiento recibido por el transmisor no puede ser mayor que el mayor n r reconocido por el receptor.
- n r ≤ n s : El intervalo de paquetes completamente recibidos no puede extenderse más allá del final de los paquetes parcialmente recibidos.
- n s ≤ n t : El paquete más alto recibido no puede ser más alto que el paquete más alto enviado.
- n t ≤ n a + w t : El paquete más alto enviado está limitado por el reconocimiento más alto recibido y el tamaño de la ventana de transmisión.
Operación del transmisor
Siempre que el transmisor tenga datos para enviar, puede transmitir hasta w t paquetes antes del último acuse de recibo n a . Es decir, puede transmitir el número de paquete n t siempre que n t < n a + w t .
En ausencia de un error de comunicación, el transmisor pronto recibe un acuse de recibo de todos los paquetes que ha enviado, dejando n un igual a n t . Si esto no sucede después de un retraso razonable, el transmisor debe retransmitir los paquetes entre n a y n t .
Las técnicas para definir "demora razonable" pueden ser extremadamente elaboradas, pero solo afectan la eficiencia; la confiabilidad básica del protocolo de ventana deslizante no depende de los detalles.
Funcionamiento del receptor
Cada vez que se recibe un paquete numerado x , el receptor comprueba si cae en la ventana de recepción, n r ≤ x < n r + w r . (Los receptores más simples sólo tienen que realizar un seguimiento de un valor n r = n s .) Si cae dentro de la ventana, el receptor lo acepta. Si tiene el número n r , el número de secuencia de recepción aumenta en 1, y posiblemente más si se recibieron y almacenaron previamente más paquetes consecutivos. Si x > n r , el paquete se almacena hasta que se hayan recibido todos los paquetes anteriores. [1] Si x ≥ n s , este último se actualiza an s = x +1.
Si el número del paquete no está dentro de la ventana de recepción, el receptor lo descarta y no modifica n r o n s .
Tanto si el paquete fue aceptado como si no, el receptor transmite un acuse de recibo que contiene el n r actual . (El acuse de recibo también puede incluir información sobre paquetes adicionales recibidos entre n r o n s , pero eso solo ayuda a la eficiencia).
Tenga en cuenta que no tiene sentido tener la ventana de recepción w r más grande que la ventana de transmisión w t , porque no hay necesidad de preocuparse por recibir un paquete que nunca se transmitirá; el rango útil es 1 ≤ w r ≤ w t .
Se requiere rango de número de secuencia
Hasta ahora, el protocolo se ha descrito como si los números de secuencia fueran de tamaño ilimitado, en constante aumento. Sin embargo, en lugar de transmitir el número de secuencia completo x en mensajes, es posible transmitir solo x mod N , para algunos N finitos . ( N suele ser una potencia de 2 ).
Por ejemplo, el transmisor sólo recibirá acuses de recibo en el intervalo n un a n t , inclusive. Dado que garantiza que n t - n a ≤ w t , hay como máximo w t +1 posibles números de secuencia que podrían llegar en cualquier momento. Por tanto, el transmisor puede decodificar sin ambigüedades el número de secuencia siempre que N > w t .
El receptor impone una restricción más fuerte. El funcionamiento del protocolo depende de que el receptor sea capaz de distinguir de forma fiable los nuevos paquetes (que deberían aceptarse y procesarse) de las retransmisiones de paquetes antiguos (que deberían descartarse y retransmitirse el último acuse de recibo). Esto se puede hacer conociendo el tamaño de la ventana del transmisor. Después de recibir un paquete numerado x , el receptor sabe que x < n a + w t , entonces n a > x - w t . Por lo tanto, los paquetes numerados x - w t nunca se volverán a retransmitir.
El número de secuencia más bajo que recibiremos en el futuro es n s - w t
El receptor también sabe que el transmisor de n una no puede ser mayor que el máximo reconocimiento cada vez enviado, que es n r . Entonces, el número de secuencia más alto que podríamos ver es n r + w t ≤ n s + w t .
Por lo tanto, hay 2 w t números de secuencia diferentes que el receptor puede recibir en cualquier momento. Por tanto, podría parecer que debemos tener N ≥ 2 w t . Sin embargo, el límite real es menor.
La información adicional es que el receptor no necesita distinguir entre números de secuencia que son demasiado bajos (menores que n r ) o que son demasiado altos (mayores o iguales an s + w r ). En cualquier caso, el receptor ignora el paquete excepto para retransmitir un acuse de recibo. Por lo tanto, solo es necesario que N ≥ w t + w r . Como es común tener w r < w t (por ejemplo, ver Go-Back-N a continuación), esto puede permitir un w t mayor dentro de un N fijo .
Ejemplos de
La ventana deslizante más simple: parar y esperar
Aunque comúnmente se distingue del protocolo de ventana deslizante, el protocolo ARQ de detener y esperar es en realidad la implementación más simple posible del mismo. La ventana de transmisión es 1 paquete y la ventana de recepción es 1 paquete. Por lo tanto, se requieren N = 2 números de secuencia posibles (convenientemente representados por un solo bit ).
Ejemplo de ambigüedad
El transmisor envía alternativamente paquetes marcados como "pares" e "impares". Los reconocimientos también dicen "par" e "impar". Supongamos que el transmisor, habiendo enviado un paquete impar, no esperó un acuse de recibo impar y en su lugar envió inmediatamente el siguiente paquete par. A continuación, podría recibir un acuse de recibo que diga "esperando un paquete extraño a continuación". Esto dejaría al transmisor en un dilema: ¿ha recibido el receptor ambos paquetes o ninguno?
Go-Back-N
Go-Back-N ARQ es el protocolo de ventana deslizante con w t > 1, pero una w r = 1 fija . El receptor se niega a aceptar cualquier paquete que no sea el siguiente en secuencia. Si un paquete se pierde en tránsito, los siguientes paquetes se ignoran hasta que se retransmite el paquete faltante, una pérdida mínima de un tiempo de ida y vuelta . Por esta razón, es ineficaz en enlaces que sufren frecuentes pérdidas de paquetes.
Ejemplo de ambigüedad
Suponga que estamos usando un número de secuencia de 3 bits, como es típico para HDLC . Esto da N = 2 3 = 8. Dado que w r = 1, debemos limitar w t ≤7. Esto se debe a que, después de transmitir 7 paquetes, hay 8 resultados posibles: En cualquier lugar, se podrían haber recibido con éxito entre 0 y 7 paquetes. Son 8 posibilidades y el transmisor necesita suficiente información en el acuse de recibo para distinguirlas todas.
Si el transmisor envió 8 paquetes sin esperar el acuse de recibo, podría encontrarse en un dilema similar al caso de detener y esperar: ¿el acuse de recibo significa que los 8 paquetes se recibieron correctamente, o ninguno de ellos?
Repetición selectiva
El caso más general del protocolo de ventana deslizante es ARQ de repetición selectiva . Esto requiere un receptor mucho más capaz, que pueda aceptar paquetes con números de secuencia más altos que el n r actual y almacenarlos hasta que se complete el espacio.
Sin embargo, la ventaja es que no es necesario descartar los siguientes datos correctos durante un tiempo de ida y vuelta antes de que se pueda informar al transmisor de que se requiere una retransmisión. Por lo tanto, esto se prefiere para enlaces con baja confiabilidad y / o un producto de alto retardo de ancho de banda .
El tamaño de la ventana w r solo necesita ser mayor que el número de paquetes perdidos consecutivos que se pueden tolerar. Por tanto, los valores pequeños son populares; w r = 2 es común.
Ejemplo de ambigüedad
El protocolo HDLC extremadamente popular utiliza un número de secuencia de 3 bits y tiene una disposición opcional para la repetición selectiva. Sin embargo, si se va a utilizar la repetición selectiva, se debe mantener el requisito de que n t + n r ≤ 8; si w r aumenta a 2, w t debe reducirse a 6.
Suponga que w r = 2, pero se usa un transmisor sin modificar con w t = 7, como se usa típicamente con la variante go-back-N de HDLC. Además, suponga que el receptor comienza con n r = n s = 0.
Ahora suponga que el receptor ve la siguiente serie de paquetes (todos módulo 8):
- 0 1 2 3 4 5 6 (pausa) 0
Debido a que w r = 2, el receptor aceptará y almacenará el paquete final 0 (pensando que es el paquete 8 de la serie), mientras solicita una retransmisión del paquete 7. Sin embargo, también es posible que el transmisor no haya recibido ningún reconocimiento y ha retransmitido el paquete 0. En este último caso, el receptor aceptaría el paquete incorrecto como paquete 8.
La solución es que el transmisor limite w t ≤6. Con esta restricción, el receptor sabe que si se perdieran todos los reconocimientos, el transmisor se habría detenido después del paquete 5. Cuando recibe el paquete 6, el receptor puede inferir que el transmisor recibió el reconocimiento del paquete 0 (el transmisor n a ≥1) , por lo que el siguiente paquete numerado con 0 debe ser el paquete 8.
Extensiones
Hay muchas formas de ampliar el protocolo:
- Los ejemplos anteriores suponen que los paquetes nunca se reordenan en la transmisión; pueden perderse en tránsito ( la detección de errores hace que la corrupción sea equivalente a una pérdida), pero nunca aparecerán fuera de servicio. El protocolo se puede ampliar para admitir el reordenamiento de paquetes, siempre que se pueda limitar la distancia; el módulo de número de secuencia N debe expandirse por la distancia máxima de desorden.
- Es posible no reconocer cada paquete, siempre y cuando se envíe un reconocimiento eventualmente si hay una pausa. Por ejemplo, TCP normalmente reconoce cada segundo paquete.
- Es común informar al transmisor inmediatamente si se detecta una brecha en la secuencia del paquete. HDLC tiene un paquete REJ (rechazo) especial para esto.
- De transmisión y recepción tamaños de ventana se pueden cambiar durante la comunicación, siempre y cuando sus restos suma dentro del límite de N . Normalmente, a cada uno de ellos se les asignan valores máximos que respetan ese límite, pero el valor de trabajo en un momento dado puede ser menor que el máximo. En particular:
- Es común reducir el tamaño de la ventana de transmisión para ralentizar la transmisión para que coincida con la velocidad del enlace, evitando la saturación o la congestión .
- Una simplificación común de la repetición selectiva es la denominada SREJ-REJ ARQ. Esto opera con w r = 2 y almacena en búfer los paquetes siguiendo un espacio, pero solo permite un paquete perdido; mientras espera ese paquete, w r = 1 y si se pierde un segundo paquete, no se almacenan más paquetes. Esto brinda la mayor parte del beneficio de rendimiento del protocolo de repetición selectiva completo, con una implementación más simple.
Ver también
Referencias
- ^ Peterson, Larry L. y Davie, Bruce S. " Redes de computadoras: un enfoque de sistemas ", Morgan Kaufmann, 2000. ISBN 1-55860-577-0
- Comer, Douglas E. "Internetworking con TCP / IP, Volumen 1: Principios, protocolos y arquitectura", Prentice Hall, 1995. ISBN 0-13-216987-8
- Peterson, Larry L. y Davie, Bruce S. "Redes informáticas: un enfoque de sistemas", Morgan Kaufmann, 2000. ISBN 1558605142
enlaces externos
- RFC 1323 - Extensiones TCP para alto rendimiento
- Escalado de ventana TCP y enrutadores rotos , 2004
- Demostración de ventana deslizante (se requiere Flash )