Algoritmo de Checksum en Internet Mensaje una secuencia 16-bit integers; sum usando 16-bit aritmética complemento a uno; tomar el Ca1 del resultado.
u_short cksum(u_short *buf, int count) { register u_long sum = 0; while (count–) { sum += *buf++; if (sum & 0xFFFF0000) { /* carry occurred, so wrap around */ sum &= 0xFFFF; sum++; } } return ~(sum & 0xFFFF); }
Comprobación de sumas: comprobación de redundancia cíclica Ver datos de bits, D, como número binario. Escoge un patrón de r+1 bit (generador), G. Objetivo: escoger r CRC bits, R, como este. < D,R> división exacta entre G (módulo 2). El receptor conoce G, divide < D,R> entre G. si el resto no es cero: error detectado. Puede detectar todos los errores repentinos de menos de r+1 bits. Muy usado . D: bits de datos que se envían Patrónde bits bits d bits r R: bits de CRC
CRC : Cyclic Redundancy Check Agrego k bits de redundancia a un mensaje de n-bit Se debe buscar que k < < n Por ejemplo k = 32 y n = 12,000 (1500 bytes) Represento mensaje n-bit como un polinomio de grado n-1 MSG=10011010 as M(x) = x7 + x4 + x3 + x1 Sea k el grado de algún polinomio divisor Ejemplo : C(x) = x3 + x2 + 1
CRC (cont) TX P(x) que es divisible por C(x) Desplazo a la izquierda k bits, M(x)xk Saco el resto de M(x)xk / C(x) de M(x)xk Polinomio RX P(x) + E(x) E(x) = 0 implica no error Divido (P(x) + E(x)) por C(x); queda cero si: E(x) es cero (no error) o E(x) es exactamente divisible por C(x)
Ejemplo : C(x) = x4 + x + 1
Protocolos Punto a Punto Los mensajes llegan en "orden" Hay errores Como lograr una comunicación confiable ?? Que hacemos con el CRC ??
Detecto errores , timeout y RTX de tramas ..
Protocolos Punto a Punto (cont) Mecanismos fundamentales : Reconocimiento (ACK) y Timeouts Algunos autores esta estrategia general la denominan :
ARQ : Automatic Repeat Request
ACKs (Acknowledgements) y Timeouts
Protocolo Stop-and-Wait ( un bit número de secuencia) Problema: mantener el "pipe full" Ejemplo Enlace de 1.5Mbps x 45ms RTT = 67.5Kb (8KB) Si 1KB de tamaño de trama, dado que el emisor solo puede enviar una trama por cada RTT => 1/8 utilización del enlace (aprox. 182 Kbps) Sender Receiver Trama 0 ACK 0 Trama 1 ACK 1
Protocolo de ventana deslizante (Sliding Window) Permite múltiples "tramas en vuelo" (outstanding un-ACKed) sin su ACK Limite superior de tramas sin reconocimiento se denomina ventana (window)
SW: Emisor (TX) Asigna un numero de secuencia a cada trama (SeqNum) Mantiene tres variable de estado: send window size (SWS) last acknowledgment received (LAR) last frame sent (LFS) Mantiene invariante: LFS – LAR < = SWS
Avanza a la derecha LAR cuando ACK llega Debe mantener buffereados SWS frames (Gp:) < (Gp:) SWS (Gp:) LAR (Gp:) LFS (Gp:) ¦ ¦ ¦ (Gp:) ¦ ¦ ¦ (Gp:) –
SW: Receptor (RX) Mantiene tres variables de estado receive window size (RWS) largest frame acceptable (LFA) last frame received (LFR) Mantiene invariante: LFA – LFR < = RWS
Cuando llega trama con SeqNum : if LFR < SeqNum < = LFA => acepto if SeqNum < = LFR or SeqNum > LFA => descarto Envío ACKs acumulativos (?? ) (Gp:) RWS (Gp:) LFR (Gp:) LAF (Gp:) ¦ ¦ ¦ (Gp:) ¦ ¦ ¦ (Gp:) < (Gp:) –
SW: Receptor (cont ) ACKs acumulativos (?? ) Receptor cuando envia un ACK Sea SeqNumToAck el mayor SeqNum que no recibio ACK Todos los frames con SeqNum < = SeqNumToAck han sido RX
=> acumulativos Se setea LFR = SeqNumToAck LAF =LFR + RWS
Ejemplo Supongo LFR=5 ( ultimo ACK que envio fue para numero de secuencia 5) y RWS =4 LAF =LFR + RWS => LAF=9 Tramas 7 y 8 están buffereadas Sin embargo no se envía ACK porque aun no llego trama 6 7 y 8 se dice que llegaron fuera de orden ( técnicamente el RX puede reenviar un ACK 5)
Ejemplo (cont) Si llega la trama 6 , => ACK 8 LFR=8 LAF =LFR + RWS => LAF=12 Si la trama 6 se pierde , TIMEOUT y RTX
Que efecto produce la perdida de una trama ?? Pipe full ?
Material Complementario SubProtocolo PPP Ejemplo de CRC Eficiencia Ventana Deslizante Protocolos de ventana deslizante [1] Técnicas de identificación de tramas [1] Corrección de Errores
[1]Tanenbaum
Una clasificación de los protocolos de nivel de enlace? Orientados a Bytes ( BISYNC) Orientados a Bits ( ??)
Requisitos de diseño de PPP [RFC 1557] Enmarcado de paquetes: encapsulado de un datagrama de capa de red en un marco de enlace de datos. Soporta datos de la capa de red de cualquier protocolo de capa de red (no sólo IP) al mismo tiempo. Capacidad de desmultiplexar hacia arriba. Transparencia de bits: debe soportar cualquier patrón de bits en el campo de datos. Detección de errores (sin corrección). Pervivencia de la conexión: detecta un fallo de señal de enlace en la capa de red. Negociación de direcciones en la capa de red: punto final puede conocer/configurar las direcciones de la capa de red de los demás.
No se requiere para PPP Sin corrección o recuperación de errores. Sin control de flujo. Estropeado, entrega correcta. No necesita soportar enlaces multipunto (por ejemplo, elecciones)
La recuperación de errores , el control de flujo, la reordenación de datos están relegados a capas superiores.
Enmarcamiento de datos PPP Flag: delimitador (enmarcamiento). Dirección: no hace nada (sólo una opción). Control: no hace nada; en un futuro posible control de campos. Protocolo: protocolo de capa superior al que se entregan los marcos (por ejemplo, PPP-LCP, IP, IPCP, etc.). Protocolo Longitud variable ó ó Información Comprobación
Enmarcamiento de datos PPP Información: soporta datos de capas superiores. Comprobación: comprobación de redundancia cíclica para detectar errores. Dirección Protocolo Longitud variable ó ó Información Comprobación
Rellenado de bytes Requisito de "transparencia de datos": el campo de datos tiene que estar autorizado a incluir un patrón de flag < 01111110> Pregunta: ¿se han recibido < 01111110> datos o flag?
Emisor: "añade" extra < 01111110> byte tras cada < 01111110> byte de datos. Receptor: Dos 01111110 bytes en una fila: descarta el primer byte, continúa la recepción de datos. un 01111110: byte flag
Rellenado de bytes Patrón de byte flag en datos para enviar Patrón de byte flag más byte rellenados en datos transmitidos.
Protocolo de control de datos PPP Antes de intercambiar datos de la capa de red, los datos de enlace iguales deben: Configurar enlaces PPP (máxima longitud de marco, autentificación). Conocer/configurar información de capa de red. Para IP: soportar el protocolo de control IP (IPCP), mensajes (campo de protocolo: 8021) para configurar/conocer direcciones IP. Difunto Terminación Apertura Establecimiento del enlace Autentificación Configuración de la capa de red
Ejemplo CRC Se pide: D.2r XOR R = nG igualmente: D.2r = nG XOR R igualmente: si se divide D.2r entre G, necesitamos resto R. R = resto[ ] D.2r G
Perfomance del Protocolo de Ventana deslizante Sea un Host A, que usa protocolo de ventana deslizante, si debe transmitir un archivo de unos 10 GB con un Host B Window size = 64KB RTT de la red es de 1 segundo
Cual es la velocidad esperada con que el emisor envia datos? 64KB/s
Sliding Window Host A Host B ACK Window Size Round-trip time (1) RTT > Window size (Gp:) ACK (Gp:) Window Size (Gp:) Round-trip time (Gp:) (2) RTT = Window size
ACK (Gp:) Window Size
(Gp:) ???
Utilización vs RTT normalizado Fuente : Stallings W . Comunicaciones y Redes de Computadores- 7 Edición
Técnicas de identificación de tramas Contador de caracteres: posibles problemas por pérdida de sincronismo. Caracteres de inicio y final con caracteres de relleno: normalmente ASCII DLE STX para inicio y DLE ETX para final, con DLE de relleno. Secuencia de bits indicadora de inicio y final, con bits de relleno: normalmente 01111110; si en los datos aparecen cinco bits seguidos a 1 se intercala automáticamente un 0. Violaciones de código a nivel físico: se utiliza en algunas redes locales.
Protocolos de ventana deslizante El protocolo puede ser: Retroceso n: no se acepta una trama hasta haber recibido las anteriores Repetición selectiva: se admite cualquier trama en el rango esperado y se pide solo la que falta. Repetición selectiva es más complejo pero más eficiente, y requiere mas espacio en buffers en el receptor. Tamaño de ventana: Retroceso n: Número de secuencia – 1 Repetición selectiva: Número de secuencia/2
Corrección de Errores FEC (Forward Error Correction) Significa corrección de errores a posteriori y se utiliza en sistemas sin retorno o sistemas en tiempo real donde no se puede esperar a la retransmisión para mostrar los datos. Básicamente consiste en codificar en el transmisor cada bloque de k bits de la trama en palabras de n bits, siendo n>k. El receptor decodifica las palabras en los bloques originales aunque éstos tuviesen algún error.
Corrección de Errores FEC. Los bits añadidos, conocidos como de redundancia, hacen posible detectar errores y deducir el dato que se transmitió.
Corrección de Errores FEC Se dispone de los siguientes tipos: FEC a bloques. Sus variantes más usadas: BCH. RS (Reed Solomon). FEC convolucional. Aplica el algoritmo Viterbi.
Corrección de Errores FEC a bloques. Se denomina Distancia Hamming entre dos códigos al número de símbolos en que se diferencian. Peso de una palabra: número de unos que tiene. Distancia de hamming: Número de bits en que difieren dos palabras.
Corrección de Errores FEC a bloques. Distancia Hamming.
10001110 11100101 00111000 11110111 d=5 d=2 Peso de la suma de las 2 palabras. 10001110 11100101 + 00111000 +11110111 =10110110 (peso 5) =00010010 (peso 2)
Corrección de Errores FEC a bloque. Distancia Hamming. Cuanto mayor sea la distancia de hamming entre dos palabras, más difícil será que un error en la transmisión convierta una en la otra, ya que será necesario alterar d bits. Un código de distancia hamming d será capaz de detectar errores en d-1 bits. Un código de distancia hamming d será capaz de corregir errores en (d-1)/2 bits. Para corregir errores en d bits hará falta un código con distancia de hamming 2d+1.
Corrección de Errores FEC a bloques. Distancia Hamming. Códigos de control de paridad. Se añade un bit de paridad al final de la palabra de forma que el número total de unos, incluído el bit de paridad sea par (paridad par) o impar (paridad impar). Paridad par: 1011000 1 Paridad impar: 1101011 0 Este código tiene una distancia de hamming igual a 2, así que es capaz de detectar errores en 1 bit.
Corrección de Errores FEC a bloques. Distancia Hamming. Códigos de control de paridad. Si la transmisión se realiza por bloques, se pueden añadir bits de paridad adicionales.
Distancia de hamming 4. Puede corregir errores en 1 bit y detectar errores en 1, 2 ó 3 bits.
Corrección de Errores FEC a bloques. Distancia Hamming. Códigos de hamming. Son un subconjunto de los códigos de control de paridad, en los cuales se disponen los bits de paridad de forma que permitan localizar la presencia de errores en el mensaje. Su distancia de hamming mínima es 3. Para palabras de L bits, hace falta que R de esos bits sean de paridad para poder corregir un error en un bit, donde: L £ 2R – 1 R será el menor número entero que cumpla esta condición
Corrección de Errores FEC a bloques. Distancia Hamming. Códigos de hamming. Cada bit de paridad debe controlar un conjunto distinto de bits de información. Un error en un bits de información debe afectar a 2 o más bits de paridad. Para el cálculo de los bits de paridad sólo se pueden utilizar bits de información no se pueden incluir los otros bits de paridad. Ejemplo:
Corrección de Errores FEC a bloques. Distancia Hamming. Códigos de hamming. Código óptimo. Se numeran los bits de la palabra código empezando por 1.Los bits potencia de 2 serán de redundancia y el resto de datos. Cada bits de datos contribuye a varios bits de redundancia, que se determinan descomponiendo la posición del bit en suma de potencias de 2. Ejemplo: 11 = 1 + 2 + 8 Si se produce un error, el bit erróneo será el situado en la posición que se obtenga sumando las posiciones de los bits de redundancia incorrectos.
Corrección de Errores FEC a bloques. Distancia Hamming. Códigos de hamming. Código óptimo. Ejemplo de código óptimo para caracteres de 7 bits.
Corrección de Errores FEC a bloques. Código Hamming H. Usado en algunos radioenlaces digitales en la década de los '80. En particular la versión H(555,544).
Permite corregir 2 errores en la secuencia de 544 bits de información.
Corrección de Errores FEC a bloques. Código BCH. Bose-Chaudhuri-Hocquenghen. Es el código más conveniente para errores independientes. Los parámetros definidos son: Longitud del bloque: N=2M-1 M>=3 Bits de información: I=N-M.t Distancia mínima: d=2.t+1
Corrección de Errores FEC a bloques. Código BCH. Es usado por ejemplo en telefonía celular analógica AMPS en el canal de control bajo la versión BCH(48,36) y BCH(40,28).
En codificadores digitales de TV a 34Mb/s se utiliza el codec BCH(511,493) para corregir 2 errores por bloque.
Corrección de Errores FEC a bloques. Código RS. Reed-Solomon. Es una variante del BCH y la más apropiada para ráfagas de errores. Los parámetros definidos: Bits por símbolo: m Longitud del bloque: N=m.2m-1 Bits de información: (N-I)=m.2t Distancia mínima: d=m.(2.t+1)
Corrección de Errores FEC a bloques. Código RS. En general el número de errores corregidos son t ráfagas de m bits en una palabra de código.Por ejemplo: En RS(60,40) se corrigen 2 ráfagas de 4 bits errados. Una aplicación, entre otras, es en radioenlaces digitales de 140Mb/s en la versión RS(65/62) para corregir 4 errores en 4 bloques.
| Página siguiente |