T3. NIVEL DE ENLACE DE DATOS

ÍNDICE „

„

„

„

Introducción

• • • •

Servicios proporcionados al nivel de red Entramado Control de errores Control de flujo

Detección de errores

• • •

Paridad Suma de bloque CRC

Casos de estudio:

• •

HDLC y familia ( PPP) Subnivel MAC. Estándar IEEE 802.X

Puentes y conmutadores.

Redes(4º) T3 Nivel Enlace de Datos

2

ÍNDICE „ „ „ „ „ „

„

Introducción Detección y corrección de errores. Control de flujo. Protocolo de ventana deslizante. Subnivel de acceso al medio. Casos de estudio:

• • •

Prot. derivados del HDLC Prot. PPP IEEE 802

Puentes y conmutadores

Redes(4º) T3 Nivel Enlace de Datos

3

INTRODUCCIÓN „ „ „ „

Objetivo: suministrar un transporte “fiable” de bits al nivel de red. Sólo se ocupa de equipos directamente conectados. Los bits llegan al destino en el mismo orden Los circuitos de comunicación:

• Cometen errores • Tasa de datos finita (Velocidad) • Retardo de propagación

Redes(4º) T3 Nivel Enlace de Datos

4

FUNCIONES „

Proporcionar servicios al nivel de red

„

Entramado de bits

„

Control de errores

„

Control de flujo

• Sin acuse, sin conexión • Con acuse, sin conexión • Con acuse orientado a conexión

• Contar caracteres • Caracteres de Inicio-Fin • Indicadores Inicio-Fin con relleno • Detección • Corrección

• Parada y Espera • Ventana deslizante

Redes(4º) T3 Nivel Enlace de Datos

5

Servicios para el nivel de red

Redes(4º) T3 Nivel Enlace de Datos

6

Servicios para el nivel de red „

Sin acuse y sin conexión

„

Con acuse y sin conexión

• Envío de tramas sin acuse de recibo • Ausencia de conexión • Baja tasa de errores • Tiempo real (voz) • LAN • El receptor produce un acuse de recibo por trama(s) • Ausencia de conexión • Alta tasa de errores • Sistemas inalámbricos

Redes(4º) T3 Nivel Enlace de Datos

7

Servicios para el nivel de red „

Con acuse orientado a conexión

• Emisor y receptor establecen una conexión previa a la transferencia de datos • Tramas numeradas • Se garantiza la recepción de cada trama y el orden de transmisión • Confiable

Redes(4º) T3 Nivel Enlace de Datos

8

Entramado de bits „ „ „

Se agrupa el flujo de bits en tramas y se añaden bits de control de errores. El destino comprueba si se ha producido error en la trama. Delimitación de trama:

• Contar caracteres: • •

- Un campo especifica el número de caracteres de la trama - Problema: la cuenta puede alterarse por error de transmisión Principio-fin. Bandera.

Redes(4º) T3 Nivel Enlace de Datos

9

Delimitación: Contar caracteres

Redes(4º) T3 Nivel Enlace de Datos

10

Delimitación: Caracteres de Inicio-Fin „

Comienzo de trama con DLE STX (ASCII) y fin de trama con DLE ETX (ASCII)

„

Problema de la transparencia: “Que los indicadores aparezcan como parte de los datos”

„

Solución: Inserción de carácter. Poner un DLE antes de cada DLE “accidental” de los datos. Desventaja: añade 8 (ó 7) bits (ASCII)

„

Redes(4º) T3 Nivel Enlace de Datos

11

Delimitación: Bandera o flag „ „

Tramas con número arbitrario de bits Cada trama comienza y termina con un patrón de bits, 01111110, byte indicador, bandera, flag... Flag 011111110

„

Flag 011111110

Permite encadenamiento de tramas. flag

„

Datos Trama

Datos Trama

flag

Datos Trama

flag

Problema de la transparencia.

Redes(4º) T3 Nivel Enlace de Datos

12

Delimitación: Bandera o flag „

Transparencia: Inserción de bit No se permite repetir el delimitador dentro de la trama

Redes(4º) T3 Nivel Enlace de Datos

13

Control de errores „ „

Detección de errores y Corrección de errores

“Siempre hay errores” Redes(4º) T3 Nivel Enlace de Datos

14

Control de errores Corrección de errores: mecanismo básico. ¿Cómo asegurar que las tramas son entregadas en orden al receptor y sin errores? • Realimentación del transmisor con acuse de recibo. • Añadir temporización (T0 >2 trecepción) „

- Transmitir la trama nuevamente, si se cumple el -

tiempo T0. Duplicidad, introducir números de secuencia de tramas de datos y acuse de recibo.

Redes(4º) T3 Nivel Enlace de Datos

15

Control de flujo „

Asegurar que el transmisor no sobrecarga al receptor.

„

Realimentación del transmisor.

„

Parada y espera (simplex)

• El transmisor envía una trama y espera un acuse de recibo del receptor antes de enviar la siguiente trama

• Problema: sólo una trama en transito; baja eficiencia

Redes(4º) T3 Nivel Enlace de Datos

16

Parada y espera

Redes(4º) T3 Nivel Enlace de Datos

17

Ventana deslizante „

Ventana deslizante (duplex)

• • • • • • • •

Dos estaciones A y B B reserva memoria temporal para n tramas A puede enviar n tramas sin confirmación Cada trama se etiqueta con un nº de secuencia, k bits B confirma una trama mediante un acuse de recibo que incluye el nº de secuencia de la siguiente trama que espera recibir. Es posible confirmar varias tramas simultáneamente, la actual y las anteriores A mantiene una lista (ventana de tramas) con los nº de secuencia que puede transmitir y B con los que espera recibir. Si en un tiempo prudencial (time-out) no se recibe el acuse de recibo, se reenvía la trama.

n ≤ 2k − 1

Redes(4º) T3 Nivel Enlace de Datos

18

Ventana deslizante

tprop α= tframe

Redes(4º) T3 Nivel Enlace de Datos

19

Ventana deslizante Tramas ya transmitidas

Número de secuencia de las tramas

Última trama confirmada

Tramas almacenadas temporalmente hasta que son confirmadas Ventana de tramas que se pueden transmitir

Última trama transmitida

La ventana se cierra por el límite inferior cuando se envían tramas

La ventana se abre por el límite superior cuando se reciben tramas

(a) Desde el punto de vista del transmisor Ventana de tramas que se pueden aceptar

Tramas ya recibidas

Última trama confirmada

Última trama recibida

La ventana se cierra por el límite inferior cuando se reciben tramas

(b) Punto de vista del receptor Redes(4º) T3 Nivel Enlace de Datos

La ventana se abre por el límite superior al enviar las ACKs

20

Ventana deslizante

Redes(4º) T3 Nivel Enlace de Datos

21

Control de errores „

„

¿Que es un error?

• Nº de bits de una trama: n=m+r

- m, bits de datos - r, bits de comprobación - n, palabra de código • Dadas dos palabras de código, es fácil determinar en cuantos bits difieren (XOR) Distancia de Hamming: nº de posiciones de bits en que difieren dos palabras de código

Redes(4º) T3 Nivel Enlace de Datos

22

Control de errores „

La detección y corrección de errores de un código depende de su distancia de Hamming.

• Detectar d errores requiere una distancia d+1 • Corregir d errores requiere una distancia 2d+1

„

Paridad: se considera un código en el que se agrega un solo bit de paridad a los datos.

• El bit de paridad se escoge de forma que el nº total de • •

unos de la palabra de código es par (o impar). Detecta errores individuales Sólo detecta 50% (nº impar bits de erróneos)

Redes(4º) T3 Nivel Enlace de Datos

23

Suma de bloque „ „

A cada carácter (n bits) se le añade un bit de paridad (transversal o de fila) A cada posición de bit del bloque se le añade un bit de paridad (longitudinal o de columna)

• Un carácter al final del bloque cuyos bits indican la paridad de cada columna del bloque.

„ „

Corrige hasta n bits y detecta el 50% restante. Ejemplo: Para transmitir una información se utiliza paridad de suma de bloque (par). Si al receptor le llega el siguiente bloque de información (en hexadecimal): A3 2D FC 24 17 0D E4 B8. Decir si es correcto, y en caso contrario, corregirlo.

Redes(4º) T3 Nivel Enlace de Datos

24

Solución al Ejemplo

Redes(4º) T3 Nivel Enlace de Datos

25

Código de Redundancia Cíclica (CRC) „ „

„ „

Detecta 99’98% Dado mensaje de k bits, el transmisor genera una secuencia de n bits, denominada secuencia de comprobación de la trama (FCS), de forma que la trama resultante, con n+k bits, sea divisible por algún número predeterminado. El receptor divide la trama recibida por ese nº y, si no hay resto en la división, no hay errores. Tratamiento de las cadenas de bits como representaciones de polinomios con coeficientes de 0 y 1.

• La cadena 110001 representa el polinomio x5+ x4+ x0

Redes(4º) T3 Nivel Enlace de Datos

26

Algoritmo (CRC) „

Definiciones:

„

Objetivo: T/P tenga resto cero

• T = trama de (k+n) bits a transmitir, con n