• 1.- Técnicas Control de Flujo.
• 1.1.- Parada-y-Espera.
• Prestaciones.
• 1.2.- Ventana Deslizante.
• Prestaciones.
• 2.- Protocolos de Control de Errores.
• 2.1.- FEQ.
• 2.2.- ARQ.
• Parada-y-Espera.
• Ventana Deslizante- REJ.
• Ventana Deslizante- SREJ.
• 3- Prestaciones de ARQ.
• 3.1- Parada-y-Espera.
• 3.2- Ventana Deslizante- SREJ.
• 3.3- Ventana Deslizante- REJ.

       Cuando una trama llega a una máquina conectada a algún tipo de red, antes de pasar la información a niveles superiores, la capa de enlace realiza una serie de operaciones sobre la trama que ocupan un espacio en la memoria e implican  un tiempo, función de la máquina, de manera que el proceso de recepción no es instantáneo. 

       Esta limitación en el espacio de memoria hace que se presente un serio problema cuando un transmisor sistemáticamente quiere transmitir tramas a mayor velocidad que aquella con que puede recibirlas el receptor. Esta situación puede ocurrir fácilmente cuando el transmisor opera en una computadora rápida (o con baja carga) y el receptor en una máquina lenta (o con sobrecarga). El transmisor puede enviar tramas rápidamente hasta que satura al receptor, que comenzará a desechar aquellas a las que no pueda atender. 
 
 

       Para evitar esta situación se hace necesario llevar un control del flujo en el enlace, manejando la velocidad a la que el emisor envía las tramas para que no sature al receptor. Este control de la velocidad generalmente requiere algún mecanismo de realimentación, para que el transmisor pueda saber si el receptor puede mantener el ritmo o no. 

       La mayoría de las técnicas de control de flujo tienen un principio de funcionamiento igual: el protocolo contiene reglas bien definidas sobre el momento en que el transmisor puede enviar alguna trama, y generalmente estas reglas prohiben el envío de información hasta que el receptor no lo haya autorizado. 

Un protocolo de nivel de enlace que quiere enviar tramas eficientemente debe de alguna manera ser capaz de recuperar las tramas perdidas o descartadas. Esto se consigue normalmente usando una combinación de dos mecanismos fundamentales: acuses de recibo (acknoledgments) y temporizadores (timeouts). Un acuse de recibo, comunmente referido como ACK, es una pequeña trama de control con que el receptor informa al emisor de que ha recibido la transmisión. Si el emisor no recibe un ACK en un tiempo razonable la retransmite; este tiempo está  medido por un temporizador. 

       La estrategia general de usar ACKs y "timeouts" para implementar un envio eficiente se suele denominar automatic repeat request, normalmente abreviado ARQ. 

       Es la más simple de las técnicas. Los pasos que llevarían a cabo las dos máquinas en diálogo serían: 
 
 

       En la figura se representan cuatro diferentes escenarios que se pueden producir con este algoritmo básico. Esta figura es una línea de tiempos, y es una manera muy común de representar el comportamiento de un protocolo. El emisor está representado a la derecha, el receptor a la izquierda, y el tiempo transcurre de arriba a abajo. La figura (a) muestra la situación en que el ACK se recibe antes de que el timer expire. La (b) y (c) muestran el caso en que se pierden la trama original y el ACK respectivamente. En la (d) el timer expira demasiado pronto. 

De esta manera, cuando el emisor retransmite la trama 0, el receptor puede determinar que está viendo una segunda copia de la trama 0 y que no se trata de la primera copia de la trama 1, ignorándola (aunque si devuelve un ACK).

       La principal limitación del algoritmo de parada-y-espera es que el enlace está ocupado por una única trama cada vez, es decir, se está desaprovechando la capacidad del enlace. Consideremos, por ejemplo, un enlace de 1.5Mbps, y un tiempo de propagación de 45ms (round-trip time, RTT). Este enlace tiene un producto de retraso x ancho de banda de 67.5Kb, o aproximadamente 8KB. Como el emisor sólo puede enviar una trama cada 45ms, y asumiendo que el tamaño de la trama e de 1KB, esto implica una tasa de transmisión máxima de 1024 x 8/0.045 = 128Kbps, que es aproximadamente un octavo de la capacidad total del canal. Para hacer un uso más eficiente del canal sería pues deseable el transmitir más tramas antes de recibir acuse de las anteriores. 

       El significado del producto ancho de banda x retraso es que representa la cantidad de datos que pueden estar en tránsito por el enlace simultáneamente. Lo ideal sería mandar tramas sin esperar al primer ACK. Este principio de trabajo se denomina keeping de pipe full. El algoritmo de la siguiente sección es precisamente así. 

        Restringiéndonos al caso en que sólo se puede enviar una trama cada vez, encontramos dos posibles situaciones, definidas por el tiempo de transmisión y el tiempo de propagación: 
 
 

1ª: antes de empezar a ser recibida, la trama ya se ha terminado de transmitir: Ttx < Tprop:

2ª: la trama está siendo recibida, y aún no se ha terminado de transmitir: Ttx > Tprop:

        U = nTtx / nTtrama = Ttx / Ttrama. 

        Ttrama = Ttx + Tprop + Tproc_trama + Tack + Tprop + Tproc_ack 

      Suponiendo que los tiempos de procesamiento (Tproc) y el tiempo de transmisión de la trama ack (Tack) son despreciables frente al resto, encontramos que: 

         Ttrama = Ttx + 2Tprop 

       El esquema de antes que da reducido y la eficiencia resulta: 
 

       Otra forma de expresar el parámetro a, recordando las definiciones de tiempo de propagación y tiempo de transmisión es: 
 

R,v y L son valores prefijados por el diseño; sin embargo la eficiencia es inversamente proporcional a la distancia.

       Por último, la eficiencia permite calcular la tasa binaria real con que se están transmitiendo y recibiendo datos por un enlace. Un canal puede ofrecer una capacidad determinada, pero quizá el protocolo no permita alcanzar esa cifra. Se define la capacidad eficaz como la tasa binaria conque los bits se desplazan por la línea: 

       Retomando el ejemplo del enlace que tenía un producto de ancho de banda x retraso de 8KB y las tramas de 1KB, se comprueba que la mejor utilización que se puede hacer del canal requiere que el emisor transmita la novena trama nada más recibir el acuse de recibo de la primera. 

       En este algoritmo el témino ventana de transmisión se refiere a un buffer en el cual se almacenan copias de las tramas enviadas, en espera de recibir el ACK correspondiente; si no llegan en el tiempo previsto, se realiza una nueva copia y se retransmite la trama. El número de secuencia de transmisión, N(S), es la posición que ocupa la trama enviada en el buffer. El número de secuencia viaja en la cabecera de la trama, dentro del campo de control. 

       Por ventana de recepción se entiende el buffer donde se almacenan las tramas que llegan a una máquina por alguno de sus enlaces. En este buffer esperan a ser procesadas, y a que se devuelva el acuse de recibo correspondiente a cada una de ellas, para que la máquina origen sepan que la transmisión ha llegado sin problemas a su destino. El número de secuencia de recepción, N(R), es la posición que ocupa la trama recibida en el buffer de recepción. 

       El tamaño de la ventana puede estar preestablecido, o puede negociarse durante el establecimiento de la conexión. En la figura se ilustra el mecanismo del algoritmo para una ventana de tamaño 4: 
 
 

En el campo de control de la trama habrá 0¡ñ bits que expresarán el número de secuencia.          El tamaño máximo de la ventana debe cumplir que :  W= 2n-1           Por ejemplo, para W=4, n>2

        El algoritmo de ventana deslizante es como sigue: primero el emisor asigna un número de secuencia a cada trama. El emisor controla tres variables: 
 

       El transmisor debe respetar la siguente inecuación:  UTE - UAR < TVT , o como mucho igual. Esta situación se ilustra en la figura: 

       Cuando llega un ACK , el emisor desplaza UAR a la derecha, permitiendo como consecuencia que se transmita otra trama. Además, el emisor asocia a cada trama que envía un timer, retransmitiendo la trama si el timer expira antes de que llegue su ACK correspondiente. Por tanto, estamos asumiendo que el emisor dispone de un buffer donde almacena TVT tramas, que pueden tener que ser retransmitidas. 

       Por su parte el receptor mantiene otras tres variables: 
 

       El receptor respeta la inecuación: UTA - STE < TVR, o igual como mucho. 

       Cuando se recibe una trama con número de secuencia N se comprueba si está dentro o fuera de la ventana, es decir, si N < STE o N > UTA la trama está fuera de la ventana y es descartanda. Si N > STE o N < UTA la trama se recibe y se guarda en la posición del buffer correspondiente. 

Ahora el receptor tiene que decidir si envía o no un ACK (RR o RNR), y que clase de ACK: 
 
 

En el último intercambio de tramas de la figura se ilustra como implementar un NACK: basta con dar acuse de la última trama que se recibió bien y solicitar el envío de la que no llego.

NOTACIÓN: una sóla trama puede poseer no sólo su propio número de secuencia, sino también información sobre el buffer de recepción de la máquina de la que procede, es decir,  lleva un acuse de recibo. Eso se expresa de la siguiente manera:
 

F(n,m) = f(n)  +  RR(m)

        Al igual que en caso del protocolo de parada-y-espera pueden ocurrir dos cosas: que el uso del canal sea eficiente o ineficiente. 
 
 

ENVIO CONTINUO.       El tamaño de la ventana es suficientemente grande, de manera que antes de llenarse e interrumpir la transmisión ya han comenzado a llegar ACKs. La condición de envío continuo    es :  N > 2a + 1  y :  U=1  La demostración es muy sencilla:

El tamaño de la secuencia es un N tal que:      N · Ttxtrama >= T1,siendo T1 el tiempo que tarda una trama y su ACK correspondiente en ser transmitidos.

       Pero también puede ocurrir que la ventana de transmisión esté llena y no lleguen los ACKs, por lo que la transmisión se interrumpe. La eficiencia es menor porque aunque las tramas se desplazan por el canal a igual velocidad que antes, este está vacío más tiempo: 
 

Se cumple que:  N < 1 + 2a      y :  U = N / ( 1+2a )

      Hay dos tipos de técnicas que se pueden ejecutar cuando surge un error: FEC y ARQ. En ambos casos el receptor es el encargado de tomar las decisiones pertinentes. 

Un primer paso común es detectar el error. Las técnicas para detectar errores se vieron ya en el tema 6. En general se emplea un código de redundancia cíclica (CRC).

       Para sistemas en que la información se desplaza en un sólo sentido (enlaces satélite,...). El receptor detecta el error y dependiendo de la clase que sea podrá corregirlo o no. La probabilidad de que haya error es entonces la probabilidad de que no se detecte combinado con el caso en que aún detectándolo no se pueda corregir. 

      Para sistemas en que la información circula en ambos sentidos. Si el receptor detecta un error solicita al origen que repita la transmisión.  La probabilidad de que haya error es igual a la probabilidad de no detectarlo. Existen tres tipos de ARQ basados en : parada y espera, y ventana deslizante (REJ y SREJ). Inconvenientes de ARQ son la necesidad de memoria y una lógica adicional para solicitar los reenvios cuando sea necesario (temporizadores...). 

         Parada-y-espera de ARQ está basada en la técnica de control de flujo de parada-y-espera descrita previamente en el  apartado 1.1  y representada en la figura. La estación fuente transmite una única trama y espera el ACK; ninguna otra trama puede ser transmitida hasta que no llegue la contestación de la estación destino. 
 

Dos tipos de errores característicos pueden ocurrir. Primeramente la trama que llega al destino es defectuosa o se ha perdido; el receptor detecta esta situación con las técnicas de detección de errores vistas antes y simplemente descarta la trama. Por su parte, para prevenir esta situación la fuente está preparada con un timer.               El segundo tipo de error consiste en que sea la trama de respuesta, ACK, la que se pierde. Como consecuencia la fuente no recibe el acuse de recibo y retransmite la misma trama que ya había sido recibida; para solucionarlo, y que el receptor reconozca cuando dos tramas similares se han enviado consecutivamente, las tramas cuentan en su cabecera con un bit que a modo de número de secuencia alterna el  valor 0 con  el 1.

         La principal ventaja de la parada-y-espera es su simplicidad. Su principal inconveniente la ineficiencia (ver sus prestaciones). La tecnica de control de flujo con ventana deslizante se puede adaptar para hacer un uso más eficiente del canal, por lo que a veces se denomina ARQ continuo. 

          Es la técnica más comúnmente usada en el control de errores con ventana deslizante. La fuente envia tramas consecutivamnete hasta un número fijado por el tamaño de la ventana, la posición de cada trama en la ventana está determinado por su número de secuencia (ver ventana de transmisión). Mientras que no haya errores el receptor reconocerá las tramas que le llegan (ver RR y RNR). Si detecta un error devuelve un ACK negativo (REJ=reject). La estación receptora descarta no sólo esta trama, sino todas las siguientes hasta que la primera llegue correctamente. La estación origen, cuando recibe un REJ debe retransmitir la trama errónea y todas las que iban a continuación. 

          La técnica de rechazo simple es útil en caso de que se produzca alguno de los siguientes errores: 
 

Trama dañada o perdida: Si la detecta el receptor, devuelve un REJ. Si se pierde se produce una alteración en el número de secuencia en recepción, y el destino devulve un REJ. Si se pierde y era la última el temporizador de la fuente se agota y pregunta por el estado (manda un RR). RR dañado o perdido: Si se recibe un RR posterior no hay problema. Si no, la fuente pregunta por el estado (RR). REJ dañado o perdido: Se pregunta por el estado.

          Con ARQ selectivo las únicas tramas que es necesario retransmitir son las defectuosads o perdidas, es decir, de las que se recibe un ACK negativo (que en este caso se denomina SREJ). 

          Esta técnica, por una parte parece más eficiente puesto que minimiza la utilización del canal. Por otro lado el buffer del receptor debe ser lo suficientemente grande como para guardar las tramas posteriores a la incorrecta hasta que ésta sea retransmitida. Además, el receptor debe de contar con la lógica suficiente para reinsertar la trama en su posición adecuada una vez retransmitida. El transmisor también requiere una lógica más compleja para ser capaz de selecionar una trama de la secuencia. Por estas razones, ARQ selectivo es mucho menos usado que el ARQ de rechazo simple. 

           Además de incrementarse la complejidad, el tamaño de la ventana se ve considerablemente reducido; volvamos al ejemplo del  número de secuencia de tres bits, y asumamos que el tamaño de la ventana conforme a lo visto en el anterior apartado es siete. Consideremos el siguiente caso: 
 

             Esta vez el problema es un solape entre las ventanas de transmisión y recepción.El problema se soluciona limitando el tamaño de la ventana a W=2^k-1. 
 

          Debido al diseño del sistema de transmisión se producirán errores, es decir, habrá uno o más bits de la trama que cambién su valor (ver apartado sobre perturbaciones en la transmisión del tema 2). Se definen las siguientes probabilidades: 

• p: probabilidad de que un sólo bit sea erróneo, también se denomina tasa binaria de error.
• Peb: probabilidad de error de bloque, es decir, de que una trama llegue con al menos un error.
• Pneb: probabilidad de que una trama llegue sin ningún error.

Peb = 1- (1-p)ⁿ

3.1- Parada-y-Espera.

          Si llamamos T al tiempo que tarda una trama en llegar a su destino más el que tarda su ACK correspondiente en llegar a la fuente, y tenemos en cuenta que al ser una técnica ARQ un error supone la retransmisión de la trama las veces que sea necesario (digamos Nr), el tiempo total que una trama tarda en ser transmitida correctamente es:

T_TOTAL = Nt * T

Si hay que retransitir muchas veces, por ejemplo n=16, se tira el enlace.          1-Peb es la probabilidad de que no halla error en la trama (lo que antes hemos llamado Pneb).

          Nt = 1*(1-Peb) + 2* Peb(1-Peb) + 3*Peb²(1-Peb) + ...+ n*Peb^n-1(1-Peb)= 1 / 1-Peb

3.2- Rechazo Selectivo con Envio Continuo.

             Siguiendo el mismo razonamiento conque finalizaba el apartado anterior, para hallar la eficiencia del ARQ con rechazo selectivo basta con dividir la fórmula de la eficiencia entre Nt = 1/1-Peb: 

En este caso el tiempo total TTOTAL empleado en transmitir la trama (la número 0 en el ejemplo) es el tiempo de transmisión tantas veces como haya sido necesario retransmitir.

3.3- Rechazo Simple con Envio Continuo.
            Los mismos razonamientos se pueden aplicar a este caso, sin embargo hay que poner especial atención en la aproximación de Nt. Ahora cada error hace que sea necesaria la retransmisión de K tramas en lugar de sólo una:
 
 

Nt = Si=1 f(i) Pebi-1 (1-Peb)

Donde f(i) es el número total de tramas a transmitir si la trama original tiene que ser transmitida i veces. f(i) se puede expresar como:         f(i)= 1+(i-1)K = (1-K) + Ki

            Sustituyendo una ecuación en la otra queda que: Nt = (1-Peb+KPeb)/1-Peb; por lo que sabemos ya de la técnica de rechazo simple K se puede aproximar a (1+2a) si N> 1+2a, o a N cuando N<1+2a: