Capa de enlace
1
Capa de enlace
• Se encarga de lograr una comunicación
eficiente y confiable entre dos máquinas
adyacentes.
• Adyacentes significa conectadas mediante
un “cable”
• Los problemas son:
– errores del medio físico
– retardo de los canales
2
Objetivos de la capa de enlace
•
•
•
•
Brindar servicios a la capa de red
Entramado
Control de errores
Control de flujo
3
Servicios a la capa de red
• Servicio de transferencia de datos de la
capa 3 de una máquina origen a la capa
3 de otra destino
• Basados en la estructura de capas
miramos como si habláramos a través
de la capa 2
4
Capa de enlace
5
Servicios más razonables
– sin conexión ni confirmación
• cuando hay baja tasa de error
• cuando datos atrasados son peores que datos erróneos
(tiempo real=voz, video)
• uso en LANs
– sin conexión con confirmación
• en casos de canales con muchos errores (sistemas
inalámbricos)
– con conexión y confirmación
• se sabe si los mensajes llegan o no
• se numeran y se hacen llegar en orden
• se asegura que llegan solo una vez
6
Ejemplo de conexión entre
enrutadores
7
Entramado
• La capa 2 para dar el servicio a la capa
de red debe valerse de la capa física
• Como hay errores en la capa física hay
que detectar y eventualmente corregir
errores
• División en tramas y hacer una suma de
comprobación de cada una
• La división en tramas no es tan sencilla
8
Métodos de entramado
• Conteo de caracteres
– corrupción en el encabezado de la trama
– no se puede re-sincronizar
• Caracteres de delimitación
– muy pensado para caracteres de 8 bits en ASCII
• Banderas de delimitación
• Violaciones del código de línea de la capa
física
9
Conteo de caracteres
10
Caracteres de principio y fin
11
Banderas e inserción de bits
12
Control de errores
• Detectar errores en la trama recibida
• Eventualmente comunicar a la entidad par
la existencia de errores
– reconocimientos positivos o negativos
• Temporizadores
– para tramas que nunca llegan
– pueden generar duplicados
• Números de secuencia
– para evitar duplicados
13
Códigos correctores y detectores
de error
• Qué es un error ?
– Una trama tiene m bits y se agregan r bits de
redundancia o de chequeo
– Los datos a transmitir serán n = m + r
• Distancia de Hamming es el número de bits
en que difieren dos palabras del código
• La mínima es la distancia del código
• En general hay 2m mensajes válidos pero no
14
todos los 2n lo son
Códigos correctores y detectores
de error (2)
• La detección y corrección se basa en la
distancia de Hamming del código
– Para detectar d errores necesito un código de
distancia d+1
– Para corregir d errores necesito un código de
distancia 2d+1
• Ej: un bit de paridad agregado a los datos
– es de distancia 2, un error invalida la palabra
– sirve para detectar errores simples
15
Códigos correctores y detectores
de error (3)
• Si queremos un código para corregir
errores simples con n = m + r
– Si invertimos cada uno de los n bits de una
palabra de código tenemos n palabras de código
ilegales a distancia 1 de la correcta
– Entonces cada uno de los 2m mensajes legales,
debe tener n+1 palabras dedicadas que puedan
ser unívocamente asignadas a él
– (n+1) 2m <= 2n => (m + r +1) <= 2r
16
– dado m hay un límite inferior para r
Códigos de Hamming
• Ejemplo real del límite teórico
• Las posiciones 2i son ocupadas por los bits
de chequeo (1,2,4,8, etc)
• Las restantes se ubican los datos
• Ejemplo:
– Palabras de 7 bits, se codifican en 7+4=11 bits
ya que 7+4+1 <= 24 (menos de 4 no cumple)
17
Códigos de Hamming (2)
• Palabra 1011001 queda ab1c011d001
• hay unos en posición 3,6,7 y 11
– 11=1011
–
7=0111
–
6=0110
–
3=0011
– suma=1001=dcba
• transmito 10100111001
• en recepción sumo el índice de los que tienen 1 y si
da 0 está bien, sino tengo la ubicación del error
18
Códigos de Hamming
19
Ráfagas y Matrices
• Hamming funciona para errores de un bit
• Hay una “pisada”para que sirvan para
errores en ráfagas
• Agrupar en forma de matriz y mandar por
columnas
• Consideraciones:
– largo de la ráfaga
– el mensaje llega retardado
20
Códigos detectores de error
• Si la tasa de error es baja conviene detectar
y retransmitir a corregir
• En trama de 1000 bits se necesitan 10 bits
de test para corregir y alcanza con un bit
para detectar
• Si tengo tasa de error de 10-6
– con corrección: 10*1000=10000 bits de mas
– con detección y retransmisión: envió
1*1000+1001=2001 bits de mas
21
Códigos detectores de error
• El problema con lo anterior es que con 1 bit
la probabilidad de detección de una ráfaga
es 0.5
• Se pueden hacer matrices que mejora
• Se usan en general códigos polinómicos
llamados también códigos de redundancia
cíclica (CRC)
22
Códigos polinómicos
• Se tratan los mensajes de bits como
coeficientes de un polinomio
• Si tengo un mensaje de k bits, ck-1..c0 lo
puedo ver como un polinomio:
– ck-1xk-1+ck-2xk-2+...+c0x0
• Tengo un polinomio de grado k-1
• Ej: 110001 se representa como x5+x4+x0
23
Códigos polinómicos (2)
• La aritmética se hace en módulo 2, no hay
acarreos y tanto la suma como la resta son
idénticas al XOR
• Ejemplos
• División
24
Códigos polinómicos (3)
• El transmisor y receptor deben ponerse de
acuerdo en el uso del llamado polinomio
generador G(x)
• Los coeficientes más y menos significativos
de G(x) deben ser 1
• El mensaje de m bits se representa como
M(x) y la trama a transmitir es más larga
que el largo de G(x)
25
Códigos polinómicos (4)
• La idea es agregar una suma de
comprobación al final de la trama de modo
tal que el polinomio representado por el
conjunto sea divisible entre G(x)
• El receptor divide lo que recibe entre G(x),
si el resto es 0 no hay errores. Si es distinto
de 0 es porque hubo errores en la
transmisión
26
Códigos polinómicos (5)
• El algoritmo es:
– Si r es el grado de G(x), agrego r bits en 0 en la
parte menos significativa de la trama. Lo que
tengo entonces es la representación de xr M(x)
– Divido xr M(x) entre G(x) con aritmética
módulo 2 y obtengo un resto R(x) (con menos
de r bits)
– Resto a R(x) a xr M(x) y el resultado es lo que
se transmite T(x) que obviamente es divisible
27
entre G(x)
Códigos polinómicos
28
Códigos polinómicos (6)
• Analicemos la potencia del método
• Supongamos que hay un error y el receptor
recibe T(x)+E(x) donde E(x) es el error y
tiene un 1 en cada bit que se invirtió
• El receptor divide [T(x)+E(x)]/G(x) y como
T(x)/G(x) = 0, el resultado es E(x)/G(x)
• Solo se escapan los patrones de error que
correspondan a un polinomio divisible entre
29
G(x)
Códigos polinómicos (7)
• Si hay un error simple, E(x)=xi (*)
– lo detectamos si G(x) tiene más de dos términos
• Si hay dos errores, E(x)=xi+xj=xj(xi-j+1)
– si G(x) no es divisible por x (*)
– lo detectamos si G(x) no divide a xk+1 para
cualquier k<i-j (largo de la trama)
– Hay polinomios de bajo grado que cumplen
• Ej. x15+x14+1 no divide xk+1 para k<32768
30
Códigos polinómicos (8)
• Si hay un número impar de bits con error,
E(x) contiene un número impar de términos
– no hay polinomios con esta característica (mod
2) que sean divisibles entre x+1. Detectamos
esto si G(x) tiene a x+1 como factor
• Si hay una ráfaga de largo <=r es detectada
– Ráfaga de largo k es xi(xk-1+...+1)
– Si G(x) tiene x0 no divide a xi entonces si k-1<r
nunca será divisible
– Si k=r+1 solo será divisible si la ráfaga=G(x) 31
Códigos polinómicos (9)
• Hay polinomios estandarizados:
– CRC-12
x12+x11+x3+x2+x1+1 (carácter=6)
– CRC-16
x16+x15+x2+1 (carácter=8)
– CRC-CCITT x16+x12+x5+1 (carácter=8)
• Los de 16bits detectan los siguientes errores
•
•
•
•
•
100% simples y dobles
100% los de número impar de bits
100% de ráfagas de largo 16 o menos
99.997% de ráfagas de 17 bits
99.998% de ráfagas de 18 o más bits
32
Descargar

Capa de enlace