fundamentos de telemáticadi002.edv.uniovi.es/~fcano/ft/teoria/tema4-nivel... · – control del...

Área de Ingeniería Temática - Departamento de Informática

Área de Ingeniería Temática Departamento de Informática

Fundamentos de Telemática

Tema 4 Nivel de enlace de datos

Parte 2

Raquel Blanco Aguirre [email protected]

Curso 2011-2012

http://www.uniovi.es/�


ÍNDICE

Parte 2 2.1. Control del flujo 2.2. Control de errores

2 Fundamentos de Telemática: Tema 4 – Nivel de enlace de datos (parte 2)


2.1.- CONTROL DE FLUJO

• Objetivo: evitar saturación del receptor por un emisor más rápido

• Se numeran las tramas y los asentimientos • En una comunicación bidireccional los asentimientos

pueden viajar junto con las tramas de datos (superposición)

• Parada y espera: para enviar la siguiente trama se debe recibir el asentimiento de la anterior

• Ventana deslizante: se pueden enviar varias tramas sin recibir los asentimientos de las anteriores (técnica de envío continuo o pipelining)



Control de flujo

• Parada y espera: – El origen transmite una trama – El destino recibe la trama y responde enviando un

asentimiento – El origen espera el asentimiento para transmitir la

siguiente trama – Control del flujo: el destino puede parar el flujo

reteniendo el envío de los asentimientos



Control del flujo

• Parada y espera:

5

Tiempo de transmisión de la trama Tiempo de

propagación

Expiración del temporizador

Se pierde la trama 0, A retransmite


Se pierde ACK 0, A retransmite

Tiempo de transmisión de ACK

B descarta la trama duplicada

Tiem

po

Fundamentos de Telemática: Tema 4 – Nivel de enlace de datos (parte 2)


Control del flujo

• Prestaciones de parada y espera: – Se pretende que el canal esté ocupado el mayor tiempo

posible. – Tiempo de transmisión: tiempo que tarda una máquina en

depositar una trama completa en el medio de transmisión. ttx = L / R

donde: – L es la longitud (nº de bits) de la trama – R es la velocidad de transmisión (bps)

– Tiempo de propagación: tiempo que tarda un bit en atravesar el medio de transmisión de un extremo a otro.

tprop = d / v donde:

– d es la longitud del enlace – v es la velocidad de propagación



Control del flujo

• Prestaciones de parada y espera: – Situación 1: ttx < tprop

• La trama se termina de transmitir antes de empezar a ser recibida en el destino

7

totalTiempo tramade TiempoU = ?? ¿¿



Control del flujo

• Prestaciones de parada y espera: – Situación 2: ttx > tprop

• La trama se está recibiendo en el destino cuando aún no se ha terminado de transmitir desde el origen

8

totalTiempo tramade TiempoU = ?? ¿¿



Control del flujo

• Prestaciones de parada y espera: – El tiempo total para enviar los datos de una trama se

define como: Ttotal = ttx + tprop + tprocT + tack + tprop + tprocA

donde: – ttx: tiempo de transmisión de la trama – tprop: tiempo de propagación de la trama/asentimiento – tprocT: tiempo de procesamiento de la trama – tack: tiempo de transmisión del asentimiento – tprocA: tiempo de procesamiento del asentimiento

– Normalmente tprocT, tack y tprocA se consideran despreciables respecto al resto de los términos, entonces:

Ttotal = ttx + 2tprop



Control del flujo

• Prestaciones de parada y espera: – La utilización de la línea o eficiencia es:

– Si definimos a = tprop/ttx

– La eficiencia es:

– En resumen: • Si ttx<tprop a >1 U pequeña (<33%) muy ineficiente • Si ttx>tprop a <1 U mayor (>33%) menos ineficiente

– Capacidad eficaz: tasa binaria real con la que se está transmitiendo por un enlace

Cef = U x R

10

proptx

tx

2tttU+

=

2a11U+

=



Control del flujo

• Ventana deslizante: – El emisor mantiene una lista con los W números de

secuencia de las tramas que puede transmitir Ventana emisora de tamaño W

– El receptor mantiene una lista con los W números de tramas que está autorizado a recibir Ventana receptora de tamaño W

– Como las tramas pueden perderse, el emisor guarda una copia de todas las tramas que están enviadas pero no asentidas por si hay que reenviarlas



Control del flujo

• Ventana deslizante: – Asentimientos:

• Cada asentimiento puede asentir a un grupo de tramas • Controlan el flujo y notifican el resultado de la

transmisión de una trama • RR n: el destino indica al origen que ha recibido bien

las tramas hasta la n-1 incluida y espera la n • RNR n: el destino indica al origen que se ha recibido

bien las tramas hasta la n-1 trama incluida, pero que no siga enviando más tramas por el momento



Control del flujo

• Ventana deslizante:

13

(a) Desde el punto de vista del transmisor

Tramas ya transmitidas

Tramas almacenadas temporalmente hasta que son confirmadas

Número de secuencia de las tramas

Última trama confirmada

Ú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 ACKs

Ventana de tramas que se pueden transmitir

(b) Punto de vista del receptor

Última trama confirmada

Última trama recibida

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

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

Tramas ya recibidas

Tramas ya recibidas Ventana de tramas que se pueden aceptar



Control del flujo

• Ejemplo de envío mediante ventana deslizante

14

Sistema origen A Sistema destino B



Control del flujo

• Prestaciones de ventana deslizante: – Situación 1: el asentimiento llega antes de que el emisor agote su

ventana • Suponemos que ttx = 1 y tprop = a

• El emisor puede transmitir sin tener que parar • Si W ≥ 2a+1 U = 1



Control del flujo

• Prestaciones de ventana deslizante: – Situación 2: el emisor agota su ventana antes de la llegada del

asentimiento • Suponemos que ttx = 1 y tprop = a

• El emisor tiene que parar de transmitir. En un periodo de 2a+1 el canal se utiliza W unidades de tiempo.

• Si W < 2a+1

16

12aWU+

=



Control del flujo

• Resumen de prestaciones:

17

+<+

+≥= 12aW

12aW

12aW1U

Util

izac

ión

a



2.2.- CONTROL DE ERRORES

• Errores potenciales: – Tramas perdidas – Tramas dañadas

• Técnicas de control de errores: – Detección de errores: bits de paridad, códigos de

control de errores (CRC), envío de información redundante

– Detección de duplicados – Retransmisión tras expiración de un temporizador – Confirmación negativa y retransmisión

• Tasa de errores:


t

e

NNBER =

donde: - Ne es el nº de bits erróneos - Nt es el nº de bits transmitidos


Control de errores

• ARQ con parada y espera: – Basado en control de flujo mediante parada y espera – Temporizador para retransmisión de tramas no asentidas – Eliminación de duplicados

• ARQ con vuelta atrás N: – Basado en control de flujo mediante ventana deslizante – Receptor solicita retransmisión de trama dañada o perdida – Emisor repite trama solicitada y las que había enviado tras

ella – Eliminación de duplicados

• ARQ con rechazo selectivo: – Basado en control de flujo mediante ventana deslizante – Receptor solicita retransmisión de trama dañada o perdida – Emisor repite sólo la trama solicitada – Eliminación de duplicados



Control de errores

20

Tiempo de transmisión de la trama Tiempo de

propagación


Se pierde la trama 0, A retransmite


Se pierde ACK 0, A retransmite

Tiempo de transmisión de ACK

B descarta la trama duplicada

Tiem

po

4 retransmitida

Almacenados temporalmente por el receptor

AR

Q c

on p

arad

a y

espe

ra

Descartado por el receptor

4, 5 y 6 retransmitidas

AR

Q c

on v

uelta

at

rás

N

AR

Q c

on re

chaz

o se

lect

ivo



Control de errores

• Limitaciones en el tamaño de la ventana con ARQ con vuelta atrás N: – Si se utilizan k bits para el número de secuencia, el

tamaño máximo de la ventana es 2k-1 – ¿Por qué?

• Supongamos que se utilizan números de secuencia de 3 bits (0-7) y tamaño de ventana 8

• El emisor envía la trama 0 y recibe de vuelta un RR1 • A continuación el emisor envía las tramas 1,2,3,4,5,6,7,0 y

recibe de vuelta un RR1 • ¿Qué significa?

– A.- Las 8 tramas se han recibido correctamente y RR1 es un asentimiento acumulativo para todo el bloque de tramas

– B.- Las 8 tramas se han deteriorado y se está repitiendo el RR1 anterior



Control de errores

• Limitaciones en el tamaño de la ventana con ARQ rechazo selectivo: – Si se utilizan k bits para el número de secuencia, el

tamaño máximo de la ventana es 2k-1 – ¿Por qué?

• Supongamos que se utilizan números de secuencia de 3 bits (0-7) y tamaño de ventana 7

• El emisor envía las tramas 0 a 6 • El receptor recibe correctamente las 7 tramas y envía un RR7 • RR7 se pierde • El temporizador del emisor expira y retransmite todas las

tramas • El receptor esperaba las tramas 7, 0, 1, 2, 3, 4 y 5 • El receptor supone que la trama 7 se ha perdido y acepta las

tramas 0 a 5 como tramas nuevas



Control de errores

• Prestaciones : – Tasa binaria de error (P): probabilidad de que un sólo

bit sea erróneo – Probabilidad de error de bloque (Peb): probabilidad de

que la trama llegue con al menos un error

Peb = 1 – (1 – P)n

– donde n es el número de bits de la trama



Control de errores

• Prestaciones ARQ con parada y espera:

• donde Nt es el número de retransmisiones de cada trama y se calcula como:

– En definitiva, la eficiencia es:


2a1P-1U eb

+=

2a)(1N1U

t +=

ebP-11N =t


Control de errores

• Prestaciones ARQ con vuelta atrás N: – Situación 1: W ≥ 1+2a

– Situación 1: W < 1+2a


)WPP-2a)(1(1)P-W(1U

ebeb

eb

++=

eb

eb

2aP1P-1U

+=


Control de errores

• Prestaciones ARQ con rechazo selectivo: – Situación 1: W ≥ 1+2a

– Situación 1: W < 1+2a


2a1)P-W(1U eb

+=

ebP1U −=


Control de errores

• Utilización de la línea (P=10-3):

27

a


Util

izac

ión


Control de errores

• Códigos de detección de errores: – Código de redundancia cíclica (CRC)

• Códigos de corrección de errores: – Códigos de paridad – Códigos Hamming



Control de errores

• Código de redundancia cíclica (CRC) – Para un bloque de k bits se transmiten n bits, donde

(n-k) bits se utilizan para codificar un código de comprobación de trama (FCS)

– Se basa en el tratamiento de las cadenas de bits como si fueran representaciones de polinomios, con coeficientes de valor 0 y 1

– Un bloque de k bits se interpreta como un polinomio de orden k-1.

• Ejemplos: – 10010110 x7 + x4 + x2 + x1 – 10000001 x7 + 1 – 11101 x4 + x3 + x2 + 1



Control de errores

• Código de redundancia cíclica (CRC) – El emisor y el receptor utilizan un mismo polinomio

generador G(x) para calcular el CRC y determinar si hay o no hay error

– Procedimiento general: • Para enviar un mensaje de m bits se calcula una suma

de comprobación (FCS) de r bits • El polinomio formado por el mensaje más la suma de

comprobación (FCS) debe ser divisible por el polinomio generador

• El receptor divide el polinomio recibido entre el polinomio generador.

– Si el resto es 0 no hay error – En caso contrario hay error



Control de errores

• Código de redundancia cíclica (CRC) – Cálculo de la suma de comprobación:

• Sea M(x) el polinomio de grado m que representa al mensaje

• Sea G(x) el polinomio generador de grado r con r < n y con los bits más y menos significativos a valor 1

• Paso 1: Añadir r ceros al final del polinomio M(x) para que la longitud sea m+r, obteniendo un polinomio xrM(x)

• Paso 2: Dividir xrM(x) entre G(x) empleando división en módulo 2. El resto de la división es FCS

• Paso 3: Añadir FCS al final de M(x) para obtener el mensaje a transmitir T(x)

T(x) = xrM(x) + FCS



Control de errores

• Código de redundancia cíclica (CRC) – Ejemplo:

• Sea M(x) = 1101011011 x9+x8+x6+x4+x3+x1+1 • Sea G(x) = 10011 x4+x1+1 (grado 4) • Paso 1: Añadir 4 ceros al final del polinomio M(x)

xrM(x) = 11010110110000 • Paso 2: Dividir xrM(x) entre G(x)

• Paso 3: T(x) = xrM(x) + FCS = 11010110111110 32 Fundamentos de Telemática: Tema 4 – Nivel de enlace de datos (parte 2)

Resto

1 1 0 1 0 1 1 0 1 1 0 0 0 01 1 0 0 0 0 1 0 1 0

1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0

1 0 0 1 1


Control de errores

• Código de redundancia cíclica (CRC) – Ejemplo:

• El receptor recibe el bloque: 11010110111110 • El receptor divide el bloque recibido entre G(x)

• Como el resto 0 no se han producido errores en la transmisión


Resto

1 1 0 1 0 1 1 0 1 1 1 1 1 01 1 0 0 0 0 1 0 1 0

1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0

1 0 0 1 1


Control de errores

• Código de redundancia cíclica (CRC) – Permite detectar los siguientes tipos de errores:

• Todos los errores en un único bit • Todos los errores dobles, siempre que G(x) contenga al

menos tres unos • Cualquier número impar de errores, siempre que G(x)

contenga el factor (x+1) • Cualquier ráfaga de errores cuya longitud sea inferior a

la de G(x) (inferior, por tanto, a la longitud de la FCS) • La mayor parte de las ráfagas de mayor longitud

– Polinomios estandarizados: • CRC-12: x12 + x 11 + x3 + x 2 + x1 + 1 • CRC-16: x16 + x15 + x2 + 1 • CRC-CCITT: x16 + x12 + x5 + 1


fundamentos de telemáticadi002.edv.uniovi.es/~fcano/ft/teoria/tema4-nivel... · – control del...

Documents