(07BJ) (05BR) (09BM)

Redes Redes de Computadores Redes y Sistemas Distribuidos

Tema 4 Funciones y protocolos del nivel de enlace

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 2.1 Sincronización de trama 2.2 Coordinación de la comunicación 2.3 Detección de errores 2.4 Control de flujo ([STA04] Capítulo 7) 2.4.1 Técnicas de control de flujo 2.4.2 Técnicas de recuperación de errores

3. Protocolo HDLC ([FOR07] Capítulo 11.6) 4. Protocolo PPP ([FOR07] Capítulo 11.7)

2

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 2.1 Sincronización de trama 2.2 Coordinación de la comunicación 2.3 Detección de errores 2.4 Control de flujo ([STA04] Capítulo 7) 2.4.1 Técnicas de control de flujo 2.4.2 Técnicas de recuperación de errores

3. Protocolo HDLC ([FOR07] Capítulo 11.6) 4. Protocolo PPP ([FOR07] Capítulo 11.7)

3

Tema 4 Funciones y protocolos del nivel de enlace

1. Introducción


Modelo OSI:

•

El nivel de enlace mejora el servicio básico de transmisión de datos proporcionado por el nivel físico


Objetivos:

• • • •

Resolver los problemas planteados por la falta de fiabilidad del servicio básico de transmisión de datos del nivel físico Definir reglas para iniciar y terminar el enlace Controlar la transferencia de información Detectar errores y recuperarse ante ellos


Servicios proporcionados por el nivel de enlace al nivel de red:

• • •

Sin conexión no fiable (sin asentimiento) Sin conexión fiable (con asentimiento) Servicio orientado a la conexión (con asentimiento) 4

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 2.1 Sincronización de trama 2.2 Coordinación de la comunicación 2.3 Detección de errores 2.4 Control de flujo ([STA04] Capítulo 7) 2.4.1 Técnicas de control de flujo 2.4.2 Técnicas de recuperación de errores

3. Protocolo HDLC ([FOR07] Capítulo 11.6) 4. Protocolo PPP ([FOR07] Capítulo 11.7)

5

Tema 4 Funciones y protocolos del nivel de enlace

2. Funciones del nivel de enlace


Funciones básicas de los protocolos del nivel de enlace

•

Sincronización de trama

• Delimitación del comienzo y fin de cada trama

•

Coordinación de la comunicación

• Compartición del enlace • •

•

Necesidad de un mecanismo de control de acceso al medio Necesidad de un esquema de direccionamiento físico

Detección de errores de transmisión

• Códigos detectores de errores (redundancia) • Códigos correctores de errores (redundancia)

•

Control de flujo

• Regulación del tráfico entre el emisor y el receptor

•

Control de errores

• Recuperación ante fallos (tramas erróneas, perdidas o duplicadas) 6

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 2.1 Sincronización de trama 2.2 Coordinación de la comunicación 2.3 Detección de errores 2.4 Control de flujo ([STA04] Capítulo 7) 2.4.1 Técnicas de control de flujo 2.4.2 Técnicas de recuperación de errores

3. Protocolo HDLC ([FOR07] Capítulo 11.6) 4. Protocolo PPP ([FOR07] Capítulo 11.7)

7

Tema 4 Funciones y protocolos del nivel de enlace

2.1 Sincronización de trama


Nivel físico:

• • •

Emisor: datos codificados transmitidos en serie Receptor: datos recuperados muestreando la señal recibida Sincronización de bit:

• Bit de comienzo mas elemento de parada por cada carácter • Esquema de codificación que facilita la sincronización


Nivel de enlace:

• •

Los datos de los niveles superiores se dividen en tramas Trama: delimitadores, control, datos y redundancia

• Delimitadores • • •

•

Caracteres o patrones de bits específicos • Limitan la naturaleza de los datos • Se requieren mecanismos de transparencia para evitarlo Violaciones de código Patrones de bits de código no usados (codificación por bloques)

• La redundancia se inserta al final de la trama

La utilización de tramas simplifica el control de acceso al medio, la detección de errores, y el control de flujo/errores 8

Tema 4 Funciones y protocolos del nivel de enlace

2.1 Sincronización de trama


Delimitadores de principio y fin con relleno de caracteres

• • • •

Principio de trama: carácter de inicio (STX o SOH) Fin de trama: carácter de fin (ETX o ETB) El receptor sabe donde comienza y finaliza cada trama Problema: los caracteres de control aparecen en los datos

• Ocurre cuando se transmiten datos binarios

•

Solución: caracteres de escape (DLE) para transparencia

• Se inserta un carácter de escape DLE delante de cada carácter de • •

inicio o de fin incluido en el campo de datos de la trama Los caracteres DLE incluidos en el campo de datos de la trama también se duplican Ejemplo:

• •

Datos: Trama:

a 9 STX ACK 2 6 DLE ETX 3 t y STX a 9 DLE STX ACK 2 6 DLE DLE DLE ETX 3 t y ETX

• En el peor caso, la eficiencia cae hasta el 50% 9

Tema 4 Funciones y protocolos del nivel de enlace

2.1 Sincronización de trama


Delimitadores de principio y fin con relleno de bits

• • • •

Sincronización independiente de la estructura de los datos Principio/fin de trama: patrón de bits (delimitador, flag o guión) El receptor sabe donde comienza y finaliza cada trama Problema: el delimitador aparece en la trama

• Ocurre en cualquier parte de la trama (control/datos/redundancia)

•

Solución: el emisor identifica el delimitador y lo modifica

• Ejemplo con 01111110 como guión de principio/fin de la trama: • • • •

El emisor evita más de cinco 1s consecutivos insertando un 0 El receptor analiza el bit que sigue a cinco 1s consecutivos • Si es un 0 lo elimina • Si es un 1 identifica el principio/fin de la trama Datos: 000111101111111100011111000110 Trama: 011111100001111011111011100011111000011001111110

• En el peor caso, la eficiencia cae hasta un 83,3% (5/6) 10

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 2.1 Sincronización de trama 2.2 Coordinación de la comunicación 2.3 Detección de errores 2.4 Control de flujo ([STA04] Capítulo 7) 2.4.1 Técnicas de control de flujo 2.4.2 Técnicas de recuperación de errores

3. Protocolo HDLC ([FOR07] Capítulo 11.6) 4. Protocolo PPP ([FOR07] Capítulo 11.7)

11

Tema 4 Funciones y protocolos del nivel de enlace

2.2 Coordinación de la comunicación


La compartición de un enlace conlleva la necesidad de un mecanismo de control para determinar quién usa el enlace
Los protocolos de coordinación tienen tres fases:

• • •

Establecimiento del enlace Transferencia de información (tramas) Terminación del enlace


Dos tipos básicos de coordinación:

•

Centralizada:

• Controlador central (o moderador) que determina el turno de transmisión de los interlocutores

•

•

•

Debe conceder el turno de transmisión de forma equitativa y/o gestionar prioridades Típica de los primeros sistemas de cómputo: controlador + terminales

Por contienda (o distribuida):

• No existe ningún controlador central • Los interlocutores pueden transmitir cuando lo deseen 12

Tema 4 Funciones y protocolos del nivel de enlace

2.2 Coordinación de la comunicación


Coordinación centralizada

• Selección (para envío)

• El controlador envía un mensaje de selección al terminal que responde indicando su disponibilidad mediante el envío de un reconocimiento • Si el enlace se establece, el controlador envía tramas y el terminal confirma su recepción mediante reconocimientos • Cuando el controlador termina de enviar todas las tramas, se termina el enlace • Selección rápida

• Sondeo (para recepción)

• El controlador interroga a los terminales para ver si tienen tramas que transmitir

• Sondeo por lista: el controlador interroga a los terminales •

siguiendo una lista ordenada Sondeo por grupos: los terminales están agrupados, y el controlador los interroga siguiendo una lista ordenada

13

Tema 4 Funciones y protocolos del nivel de enlace

2.2 Coordinación de la comunicación


Coordinación por contienda (o distribuida)

• •

Ni existe ningún controlador ni se usa testigo alguno Posibilidad de que se produzcan colisiones:

• Transmisión simultánea de dos o más tramas

•

Técnicas para evitar colisiones:

• Técnicas de auscultación (CSMA) • Técnicas de detección de colisiones (CSMA/CD)

•

Técnicas de recuperación ante posibles colisiones:

• Uso de plazos de espera aleatorios (para evitar que se produzcan bloqueos) asociados a tramas para gestionar las retransmisiones

•

Utilizada en redes de acceso múltiple (LAN):

• Contraste con el enfoque centralizado • Esquema de direccionamiento físico para determinar quién es el •

destinatario de cada trama Subcapa de control de acceso al medio (MAC, Media Access Control)

14

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 2.1 Sincronización de trama 2.2 Coordinación de la comunicación 2.3 Detección de errores 2.4 Control de flujo ([STA04] Capítulo 7) 2.4.1 Técnicas de control de flujo 2.4.2 Técnicas de recuperación de errores

3. Protocolo HDLC ([FOR07] Capítulo 11.6) 4. Protocolo PPP ([FOR07] Capítulo 11.7)

15

Tema 4 Funciones y protocolos del nivel de enlace

2.3 Detección de errores


Durante la transmisión pueden producirse errores que dan lugar a tramas erróneas:

•

Uso de información adicional (redundancia) para comprobar la integridad de las tramas


Si el nivel de enlace proporciona servicio fiable al nivel de red:

• •

Uso de asentimientos positivos o negativos (retransmisión) Tramas perdidas:

• Uso de temporizadores asociados a las tramas • Valor de los temporizadores: envío, proceso, asentimiento • Retransmisión de tramas cuando expira el temporizador

•

Tramas duplicadas:

• La retransmisión de tramas puede conllevar duplicidad • Uso de números de secuencia para etiquetar las tramas
La implementación de un servicio fiable está íntimamente relacionada con el control de flujo

16

Tema 4 Funciones y protocolos del nivel de enlace

2.3 Detección de errores


Tipos de errores:

• Errores aislados • Errores en ráfagas (bursts) • Más comunes en LANs
Códigos detectores de errores (redundancia)

17

Tema 4 Funciones y protocolos del nivel de enlace

2.3 Detección de errores


Problema 1. Si se transmiten tramas de 1000 bits, y la probabilidad de que se produzca un error es de 0,0001 por bit transmitido, ¿cuántas tramas erróneas recibirá el receptor en promedio?

• El 10% de las tramas contendrá un bit erróneo
Problema 2. ¿Cuántos bits se verán afectados por un pico de ruido impulsivo de 1 ms en una línea que transmite a 1 Mbps? ¿Y si transmite a 1 Gbps?

• Para 1 Mbps, se verán afectados 103 bits • Para 1 Gbps, se verán afectados 106 bits 18

Tema 4 Funciones y protocolos del nivel de enlace

2.3 Detección de errores


CRC (Cyclic Redundary Check)

• Método más comúnmente utilizado • Bloques de bits representan coeficientes (1s y 0s) de •

polinomios Una trama de k bits equivale a un polinomio de k términos, es decir, de grado k-1

• Ejemplo:

10100111 es el polinomio x7+x5+x2+x+1 (grado 7)

• Aritmética en módulo 2: suma y resta igual que XOR 19

Tema 4 Funciones y protocolos del nivel de enlace

2.3 Detección de errores


CRC (Cyclic Redundary Check)

• • •

Emisor y receptor acuerdan polinomio generador G(x) El bloque de bits de datos representa al polinomio M(x) Algoritmo:

• Agregar k-1 bits (grado de G(x)) a 0 a M(x) (extremo inferior) • Dividir el polinomio resultante por G(x) utilizando aritmética en • •

módulo 2 (el resto de la división es R(x)) La trama a transmitir, T(x), es igual M(x)0..k-1..0 XOR R(x) El receptor divide M(x)R(x) entre G(x), y obtiene un resto 0 si la trama llegó correctamente, o un resto ≠ 0 en caso contrario

20

Tema 4 Funciones y protocolos del nivel de enlace

2.3 Detección de errores


Ejemplo CRC:

• G(x) • M(x) • T(x)

= x3 + x2 + 1, es decir, 1101 = x5 + x2, es decir, 100100 = 100100 001
CRC

21

Tema 4 Funciones y protocolos del nivel de enlace

2.3 Detección de errores


CRC (Cyclic Redundary Check)

• •

• •

La elección de G(x) es crucial para que el método sea eficaz Algunos polinomios que son estándares internacionales:

• • • •

CRC-12: x12+x11+x3+x2+x+1 CRC-16: x16+x15+x2+1 CRC-CCITT: x16+x12+x5+1 (HDLC) CRC-32: x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 (IEEE 802)

Todos contienen el término x+1 como factor primo porque no hay polinomios con un número impar de términos divisibles por x+1 Un CRC de grado 16 captura: • Todos los errores simples y dobles • Todos los errores con un número impar de bits • Todos los errores en ráfagas con longitudes de hasta 16 bits • El 99,997% de los errores en ráfagas de 17 bits • El 99,998% de los errores en ráfagas de 18 o más bits 22

Tema 4 Funciones y protocolos del nivel de enlace

2.3 Detección de errores


Problema 3. Se desea transmitir el bloque de bits 10100001 con un CRC generado a partir del polinomio x3+1. ¿Cuál sería la trama transmitida? ¿Qué pasaría si el receptor recibe el bloque de bits 11000001?

23

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 2.1 Sincronización de trama 2.2 Coordinación de la comunicación 2.3 Detección de errores 2.4 Control de flujo ([STA04] Capítulo 7) 2.4.1 Técnicas de control de flujo 2.4.2 Técnicas de recuperación de errores

3. Protocolo HDLC ([FOR07] Capítulo 11.6) 4. Protocolo PPP ([FOR07] Capítulo 11.7)

24

Tema 4 Funciones y protocolos del nivel de enlace

2.4 Control de flujo


Regulación del flujo de datos entre emisor y receptor

• El flujo de datos no debe desbordar al receptor: • El receptor utiliza buffers (almacenamiento temporal) para almacenar los datos hasta que son procesados • Velocidad limitada de procesamiento de datos recibidos • Capacidad limitada de almacenamiento temporal • El receptor debe indicar cuándo se han alcanzado los límites

• Confirmación de las tramas (fiabilidad): • De forma individual o colectiva (confirmación múltiple) • Asentimiento positivo (ACK) o negativo (NAK)
Técnicas de control de flujo:

• Parada y espera (stop-and-wait) • Ventana deslizante (sliding window) 25

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 2.1 Sincronización de trama 2.2 Coordinación de la comunicación 2.3 Detección de errores 2.4 Control de flujo ([STA04] Capítulo 7) 2.4.1 Técnicas de control de flujo 2.4.2 Técnicas de recuperación de errores

3. Protocolo HDLC ([FOR07] Capítulo 11.6) 4. Protocolo PPP ([FOR07] Capítulo 11.7)

26

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Parada y espera (stop-and-wait)

• • •

• •

El emisor espera una confirmación por cada trama transmitida La siguiente trama se envía sólo cuando se recibe la confirmación El tiempo total para transmitir una trama incluyendo su confirmación

• tprop: • tframe: • tproc: • tack:

T = tprop + tframe + tproc + tprop + tack + tproc tiempo de propagación tiempo de enviar una trama tiempo de procesamiento de una trama o una confirmación tiempo de enviar una confirmación

Ventaja: simplicidad (cada trama se transmite y se confirma individualmente) Desventaja: ineficiencia (cada trama y su confirmación recorren todo el camino entre el emisor y el receptor antes de poder enviar la siguiente trama) 27

Tema 4

2.4.1 Técnicas de control de flujo

Funciones y protocolos del nivel de enlace


Parada y espera (stop-and-wait) T = tprop + tframe + tproc + tprop + tack + tproc

• La utilización o eficiencia de la línea se define como: U=

tinformación ttotal

=

• Si definimos a tcomo: a=

prop

t frame

n * t frame n * (2t prop + t frame )

U =

=

t frame 2t prop + t frame

1 1 + 2a

Máxima utilización de la línea

• a es constante en enlaces punto a punto (tprop y tframe •

son constantes) a es variable en enlaces multipunto

a=

D

Tiempo de Propagación RD = V = Tiempo de Transmisión L VL R

D = distancia del enlace V = velocidad de propagación L = longitud de la trama R = velocidad de transmisión 28

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Parada y espera (stop-and-wait)

29

Tema 4 Funciones y protocolos del nivel de enlace

2. Funciones del nivel de enlace


Problema 4. Se desea transmitir una serie de tramas de 1000 bits con un protocolo de nivel de enlace con control de flujo/errores mediante parada y espera. Calcula la eficiencia del enlace (sin errores) suponiendo una velocidad de transmisión de 1 Kbps y de 1 Mbps en los siguientes supuestos: (a) par trenzado de 1 Km, (b) cable coaxial de 200 Km, y (c) conexión por satélite de 50.000 Km.

• Sol.: • U = 0,999 / U = 0,990 • U = 0,998 / U = 0,333 • U = 0,750 / U = 0,003 30

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Ventana deslizante (sliding window)

•

El emisor puede enviar varias tramas antes de recibir una confirmación

• Permite aprovechar de forma más eficiente la capacidad del canal

•

El receptor confirma la recepción de tramas de vez en cuando

• •

La ventana (buffer) almacena un número determinado de tramas Esta técnica requiere un esquema de numeración de tramas para poder realizar un seguimiento de las tramas enviadas y recibidas:

•

• Una o más tramas pueden ser confirmadas en cualquier momento

• La numeración depende del tamaño de la ventana • Las tramas se numeran en módulo n, es decir, de 0 a n-1 • El tamaño máximo de la ventana es n-1 (¡¡¡ y no n !!!) Confirmación de las tramas:

• Confirmación de varias tramas (múltiple) con un único ACK • Los ACKs incluyen el número de la próxima trama esperada • Como máximo se pueden enviar n-1 tramas antes de recibir un ACK 31

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Ventana deslizante (sliding window)

• Ventana del emisor: • La ventana tiene inicialmente espacio para n-1 tramas • El tamaño de la ventana en cada momento equivale al número de tramas que se pueden enviar • Envío de una trama

• El límite izquierdo de la ventana avanza

• Recepción de un ACK • El límite derecho de la ventana avanza

32

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Ventana deslizante (sliding window)

• Ventana del receptor: • La ventana tiene inicialmente espacio para n-1 tramas • El tamaño de la ventana en cada momento equivale al número de tramas que se pueden aceptar • Recepción de una trama

• El límite izquierdo de la ventana avanza

• Envío de un ACK • El límite derecho de la ventana avanza

33

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Ventana deslizante (sliding window)

34

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Ventana deslizante (sliding window)

• ¿Por qué el tamaño máximo de la ventana es n-1? • La justificación se basa en la resolución de una posible ambigüedad en el asentimiento de las tramas • Ejemplo:

• Dada una ventana de tamaño 8 y numeración módulo 8 • Se envían las trama 0..7 y se envía un ACK 0 • El ACK 0 se pierde (no es reconocido como trama válida) • Se reenvían las tramas 0..7 pasado un cierto tiempo • ¿Cómo sabe el receptor que son tramas duplicadas?

• Transmisión full-dúplex • Cada interlocutor mantiene una ventana de emisión y otra de recepción (emisión y recepción simultáneas) • Optimización: superposición (piggybacking)

• Las confirmaciones se incluyen en las tramas de datos

35

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Ventana deslizante (sliding window)

• La utilización o eficiencia de la línea se define como: U =1

U =

si N ≥ 2a + 1

N 1 + 2a

si N < 2a + 1

• N es el tamaño máximo de la ventana (numeración t •

módulo N+1) y a = t prop frame N = 1  Parada y espera (stop-and-wait)

36

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Ventana deslizante (sliding window)

U =1

si N ≥ 2a + 1

37

Tema 4 Funciones y protocolos del nivel de enlace

2.4.1 Técnicas de control de flujo


Ventana deslizante (sliding window)

U =

N 1 + 2a

si N < 2a + 1

38

Tema 4 Funciones y protocolos del nivel de enlace

2. Funciones del nivel de enlace


Problema 5. Se desea transmitir una serie de tramas de 1000 bits con un protocolo de nivel de enlace con control de flujo/errores mediante ventana deslizante. Calcula la eficiencia del enlace (sin errores) en los siguientes supuestos: (a) enlace de 100 m, VT de 1 Gbps y N = 1, (b) enlace de 10 Km, VT de 100 Mbps y N = 7, y (c) enlace de 10.000 Km, VT de 1 Mbps y N = 127.

• Sol.:

• U = 0,5 • U = 0,63 •U=1 39

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 2.1 Sincronización de trama 2.2 Coordinación de la comunicación 2.3 Detección de errores 2.4 Control de flujo ([STA04] Capítulo 7) 2.4.1 Técnicas de control de flujo 2.4.2 Técnicas de recuperación de errores

3. Protocolo HDLC ([FOR07] Capítulo 11.6) 4. Protocolo PPP ([FOR07] Capítulo 11.7)

40

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Extensión del mecanismo de control de flujo para recuperación de errores (tramas perdidas o erróneas)
ARQ (Automatic Repeat reQuest)

• • • •

Cuando se recibe una trama errónea, se envía una trama NAK Las tramas especificadas por la trama NAK se retransmiten Se garantiza la robustez del mecanismo de control de flujo ante: • Tramas de datos perdidas o erróneas • Tramas de asentimiento (ACK o NAK) perdidas La recuperación de errores mediante ARQ se implementa junto con el control de flujo

• Parada y espera como: •

Parada y espera con ARQ (stop-and-wait ARQ)

• Ventana deslizante como (ventana deslizante con ARQ): • •

Vuelta atrás N (go-back-n) Rechazo selectivo (selective reject) 41

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Parada y espera con ARQ (stop-and-wait ARQ)

• El emisor guarda una copia de la última trama •

transmitida hasta que recibe el ACK correspondiente El receptor puede responder con un ACK o un NAK:

• Las tramas de datos y las tramas ACK se numeran con 0/1 alternativamente:

• Una trama de datos 0 se asiente mediante una trama ACK 1 y •

viceversa Permite identificar y descartar las tramas duplicadas

• Las tramas NAK no van numeradas:

• Asienten negativamente una trama de datos errónea • Indican la retransmisión de la última trama de datos

• El emisor dispone de un temporizador de forma que si no se recibe un asentimiento (ACK o NAK) antes de que expire, se retransmite la última trama de datos 42

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Parada y espera con ARQ (stop-and-wait ARQ)

• Funcionamiento normal

43

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Parada y espera con ARQ (stop-and-wait ARQ)

• Trama de datos perdida

44

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Parada y espera con ARQ (stop-and-wait ARQ)

• Trama ACK perdida

45

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Parada y espera con ARQ (stop-and-wait ARQ)

• ¿Por qué se numeran las tramas ACK?

46

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Ventana deslizante con ARQ

• •

El emisor guarda copias de las tramas transmitidas hasta que recibe el ACK correspondiente El receptor puede responder con un ACK o un NAK:

• Las tramas de datos, las tramas ACK y las tramas NAK están numeradas:

• •

•

Las tramas ACK llevan el número de la trama esperada Las tramas NAK llevan el número de la trama errónea y también sirven para confirmar positivamente todas las tramas anteriores a la errónea

El emisor también dispone de un temporizador de forma que si no se recibe un asentimiento (ACK o NAK) antes de que expire, se retransmiten las tramas pendientes de confirmación


Dos variantes en función del rechazo:

• •

Vuelta atrás N (go-back-n): rechazo de la trama errónea y subsiguientes Rechazo selectivo (selective reject): rechazo sólo de la trama errónea 47

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Vuelta atrás N (go-back-n)

• Trama de datos perdida

48

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Vuelta atrás N (go-back-n)

• Trama de datos errónea

49

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Vuelta atrás N (go-back-n)

• Trama ACK perdida

50

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Rechazo selectivo (selective reject)

• Difiere de vuelta atrás N en que: • El emisor debe disponer de un mecanismo de búsqueda que le permita seleccionar la trama cuya retransmisión fue solicitada (el receptor detectó una trama de datos perdida o errónea y solicitó su retransmisión mediante una trama NAK)

• El emisor sólo retransmite la trama de datos perdida o errónea • El receptor debe almacenar las tramas recibidas después de enviar un NAK hasta que la trama dañada sea reemplazada

• El receptor debe ser capaz de reordenar las tramas recibidas • El tamaño máximo de la ventana es ≤ (N+1)l2 51

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Rechazo selectivo (selective reject)

• Trama de datos errónea

52

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Rechazo selectivo (selective reject)

• ¿Por qué el tamaño máximo de ventana es ≤ (N+1)l2? • La justificación se basa en la resolución de una posible ambigüedad en el asentimiento de las tramas • Ejemplo:

• Dada una ventana de tamaño 7 y numeración módulo 8 • Se envían las trama 0..6 y se envía un ACK 7 • El ACK 7 se pierde (no es reconocido como trama válida) • Se reenvía la trama 0 pasado un cierto tiempo • ¿Cómo sabe el receptor que es una trama duplicada?

53

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Recuperación de errores con ARQ

• La utilización o eficiencia de la línea se define como: • Nr: número esperado de retransmisiones por trama • P: probabilidad que una trama sea errónea • Pk-1(1-P): probabilidad de que se necesiten k intentos para transmitir con éxito la trama

• Parada y espera con ARQ ∞ 1 1− P U= dónde N r = ∑ iP i −1 (1 − P) = (1 − P) −1 , es decir, U = N r (1 + 2a ) 1 + 2a i =1

• Ventana deslizante con ARQ Vuelta atrás N 1− P si N ≥ 2a + 1 1 + 2aP N( 1 − P) U= si N < 2a + 1 (1 + 2a)(1 − P + NP )

U=

Rechazo selectivo U = (1 − P ) si N ≥ 2a + 1

U=

N( 1 − P) si N < 2a + 1 1 + 2a

54

Tema 4 Funciones y protocolos del nivel de enlace

2.4.2 Técnicas de recuperación de errores


Recuperación de errores con ARQ

• N es el tamaño máximo de la ventana (numeración •

módulo N+1) y P = 10-3 N = 1  Parada y espera (stop-and-wait)

55

Tema 4 Funciones y protocolos del nivel de enlace

2. Funciones del nivel de enlace


Problema 6. Se desea transmitir una serie de tramas de 1000 bits por un enlace de 100 Km a 20 Mbps. Calcula la eficiencia del enlace si la tasa de errores por bit es de 0,00004 en los siguientes supuestos: (a) parada y espera (b) vuelta atrás N (N = 7), y (c) rechazo selectivo (N = 7).

• Sol.: • U = 0,046 • U = 0,258 • U = 0,320

56

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 3. Protocolos del nivel de enlace 3.1 Protocolo HDLC ([FOR02] Capítulo 11.4) 3.2 Protocolo PPP ([FOR02] Capítulo 15)

57

Tema 4 Funciones y protocolos del nivel de enlace

3. Protocolos del nivel de enlace


Características deseables de los protocolos del nivel de enlace:

• Independencia del nivel físico • Soporte de actividad bidireccional simultánea • Adaptación a diferentes aplicaciones/entornos • Eficiencia (relación entre los bits de información • •

transportados y los bits de control del protocolo) Robustez Fiabilidad

58

Tema 4 Funciones y protocolos del nivel de enlace

3. Protocolos del nivel de enlace


Tipos de protocolos del nivel de enlace:

• Conexión directa entre hosts • Enlace punto a punto entre dos DTEs • Extremo a extremo • Servicio orientado a conexión • Control de flujo: • Parada y espera (R↓): Kermit • Ventana deslizante (d↑ o R↑): HDLC (High-Level Data Link Control)

59

Tema 4 Funciones y protocolos del nivel de enlace

3. Protocolos del nivel de enlace


Tipos de protocolos del nivel de enlace:

• Controlador + terminales • Enlace multipunto • Un DTE maestro y varios DTEs esclavos

• Coordinación centralizada (sondeo/selección) • Extremo a extremo • Servicio orientado a conexión • Control de flujo: • Parada y espera (R↓): BSC (Binary Synchronous Control) • Ventana deslizante (d↑ o R↑): HDLC

60

Tema 4 Funciones y protocolos del nivel de enlace

3. Protocolos del nivel de enlace


Tipos de protocolos del nivel de enlace:

• Redes WAN • Enlace punto a punto • Significado local (entre DTE y DCE, o entre DCE y DCE) • Servicio orientado a conexión • Control de flujo: • PPP (Point-to-Point Protocol): basado en HDLC • Acceso doméstico (módems, ADSL) • Interconexión de routers

61

Tema 4 Funciones y protocolos del nivel de enlace

3. Protocolos del nivel de enlace


Tipos de protocolos del nivel de enlace:

• Redes LAN • Enlace multipunto • Extremo a extremo • d↓, R↑ y tasa de errores muy baja • Control de flujo en niveles superiores

• Protocolo dividido en dos subcapas (Ethernet): • LLC (Logical Link Control): basado en HDLC • MAC (Media Access Control): coordinación por contienda

62

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 3. Protocolos del nivel de enlace 3.1 Protocolo HDLC ([FOR07] Capítulo 11.6) 3.2 Protocolo PPP ([FOR07] Capítulo 11.7)

63

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Todos los protocolos del nivel de enlace actuales son subclases de HDLC o se basan en HDLC

• Comunicación semi-dúplex o full-dúplex • Diferentes tipos de hosts: estaciones primarias, secundarias y combinadas • Configuración del enlace: punto a punto y multipunto • Modos de operación: NRM, ARM y ABM

• Tramas monoformato: tramas I, tramas S y tramas U • Clases de procedimiento: subclases de HDLC • Interfaz del protocolo • Marco de referencia para el diseño de otros protocolos: • LLC, PPP, LAPB (X.25), LAPD (RDSI), 802.11 64

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Tipos de estaciones

• • •

Estación primaria: tiene el control total del enlace Estación secundaria: no puede controlar el enlace Estación combinada: actúa alternativamente como primaria y como secundaria


Configuración del enlace

•

Configuración no balanceada (o maestro/esclavo)

• Una estación primaria y una o varias estaciones secundarias • La estación primaria envía órdenes a las secundarias que responden • •

a la primaria Si sólo hay una estación secundaria, el enlace es punto a punto Si hay varias estaciones secundarias, el enlace es multipunto

•

Configuración balanceada

•

HDLC no soporta configuraciones balanceadas multipunto

• Dos estaciones combinadas • Enlace punto a punto 65

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC

66

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Modos de operación:

• Modo de respuesta normal (NRM, Normal Response Mode) • Configuración no balanceada punto a punto o multipunto • Una estación secundaria sólo puede transmitir cuando la estación primaria le da permiso para hacerlo (semi-dúplex)

• Modo de respuesta asíncrono (ARM, Asynchronous Response Mode)

• Configuración no balanceada punto a punto o multipunto (sólo una de las estaciones secundarias puede estar activa) • Una estación secundaria puede empezar a transmitir sin pedir el permiso de la estación primaria (full-dúplex)

• Modo balanceado asíncrono (ABM, Asynchronous Balanced Mode)

• Configuración balanceada punto a punto • Cualquiera de las dos estaciones combinadas puede transmitir en cualquier momento sin tener que solicitar el permiso de la otra estación (full-dúplex)

• Tanto en NRM como en ARM, todas las transmisiones son desde o hacia la estación primaria

67

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Formato de la trama

• Monoformato con campos de significado posicional • Delimitador de inicio y fin (01111110) con relleno de bits • Dirección (uno o más bytes) de la estación secundaria, o dirección de la estación combinada que desempeña el papel de estación secundaria • Control (uno o dos bytes) • Información (longitud máxima dependiente de implementación) • FCS (Frame Check Sequence): CRC-CCITT (dos bytes) o CRC-32 (cuatro bytes)

68

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Trama I (información)

• Datos e información de control asociada a los datos • Campo de control • N(S): número de la trama que se está enviando • N(R): número de la trama esperada • Las tramas I permiten la utilización de la técnica de superposición (piggybacking)

• Numeración módulo 8 ó 128 (modo extendido) • Variables asociadas: • V(S): número de la próxima trama a enviar • V(R): número de la próxima trama esperada

69

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Trama S (supervisión)

• Se utiliza para asentir, positiva o negativamente, •

cuando no se tienen datos que transmitir (control de flujo y recuperación de errores) Campo de control

• N(R): número de la trama esperada • Numeración módulo 8 ó 128 (modo extendido) • No contiene subcampo N(S) porque las tramas S no transportan datos • Subcampo Code: comando Code 00 01 10 11

Comando RR (Receive Ready) REJ (REJect) RNR (Receive Not Ready) SREJ (Selective REJect) 70

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Trama U (no numerada)

• Gestión del enlace • Campo de control • No contiene campos N(R) ni N(S) puesto que estas tramas no •

intervienen en el envío/recepción de datos Subcampo Code: hasta 32 órdenes/respuestas no numeradas

• • • •

Selección de modo de operación: SNRM(E), SARM(E), SABM(E) Intercambio de información: UI (trama de datos no numerada), UA (respuesta positiva a la selección del modo de operación) Desconexión: DISC (desconexión), DM (respuesta negativa a la selección del modo de operación) Misceláneas: FRMR (rechazar trama con formato incorrecto)

71

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Tramas I, S y U

• Campo de control • El subcampo P/F se usa para dos propósitos distintos: • Cuando está activo significa sondeo o final: • Sondeo cuando la trama la envía la estación primaria a una

•

estación secundaria (orden) • Final cuando la envía una estación secundaria a la estación primaria (respuesta) Mecanismo de punteo (checkpointing): • Permite asociar una respuesta (F) con la orden correspondiente (P)

72

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Utilización de las tramas S

• •

Una trama S se utiliza para asentir, positiva o negativamente, cuando no se tienen datos que transmitir (control de flujo y recuperación de errores) Su significado depende del subcampo Code y del contexto: • RR tiene 4 posibles usos:

• • • •

ACK: asiente tramas hasta N(R) – 1 sin piggybacking Sondeo: trama RR de primaria a secundaria con el bit P activo Respuesta negativa al sondeo: trama RR de secundaria a primaria con el bit F activo (si tuviera algo que transmitir enviaría una trama I, y no una S) Respuesta positiva a la selección: trama RR de secundaria a primaria con el bit F activo

• RNR tiene 3 posibles usos: • • •

ACK: asiente tramas hasta N(R) – 1 y solicita que no se envíen más hasta que envíe un RR Selección: trama RNR de primaria a secundaria con el bit P activo Respuesta negativa a la selección: trama RNR de secundaria a primaria con el bit F activo

• REJ: rechazo de la trama N(R) y subsiguientes • SREJ: rechazo selectivo de la trama N(R)

73

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC

Sondeo (RR,REJ,SREJ o trama I, mas P = 1)

Respuesta positiva al sondeo

Respuesta negativa al sondeo

Selección

Posible respuesta positiva a la selección

Respuesta negativa a la selección

74

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Clases de procedimiento

• Especificación precisa de las diferentes alternativas •

ofrecidas por HDLC Modo de operación (repertorio básico de órdenes y respuestas) con opciones UN Orden I RR RNR

Respuesta I RR RNR UA SNRM DM DISC FRMR Módulo 8

UA Orden I RR RNR

Respuesta I RR RNR UA SARM DM DISC FRMR Módulo 8

BA Orden I RR RNR

Respuesta I RR RNR UA SABM DM DISC FRMR Módulo 8 75

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Clases de procedimiento

•

Opciones Opción 2 3 4 7 8 9 10

•

Orden

Respuesta

REJ REJ SREJ SREJ UI UI Campo dirección extendido Quitar I Quitar I Campo control extendido

Descripción Rechazo simple (vuelta atrás N) Rechazo selectivo Información no numerada Direcciones multiocteto Sin respuestas I (el bit F no puede estar activo) Sin órdenes I (el bit P no puede estar activo) Módulo 128

Ejemplos

• UN 2,4 equivale a modo NRM con rechazo vuelta atrás N y tramas • •

no numeradas UA 2,9 equivale a modo ARM con rechazo vuelta atrás N y sin tramas I con bit P activo BA 3,8 equivale a modo ABM con rechazo selectivo y sin tramas I con bit F activo 76

Tema 4 Funciones y protocolos del nivel de enlace

P
UN 3,4 (sin errores) • t0/1/2: conexión A/B/C y envío información no numerada • t3: sondeo A • t4: sondeo B con envío de una trama de datos que envía, a su vez, tres tramas de datos • t5: envío de cinco tramas de datos a A • t6: P agota su ventana y selecciona a A para poder seguir enviando tramas • t7: sondeo C • t8: P solicita confirmación de tramas pendientes a A • t9: P confirma tramas pendientes de B • t10/11/12: desconexión A/B/C

3.1 Protocolo HDLC A

t0

B

A,SNRM,P A,UA,F B,SNRM,P B,UA,F

t1

C,SNRM,P C,UA,F G,UI

t2

t3

A,RR,0,P A,RR,0,F

t4

t5

t6

B,I,0,0,P B,I,0,1,* B,I,1,1,* B,I,2,1,F A,I,0,0,* A,I,1,0,* A,I,2,0,* A,I,3,0,* A,RNR,0,P A,RR,4,F A,I,4,0,* C,RR,0,P C,RR,0,F

t7 t8

A,RNR,0,P A,RR,5,F B,RNR,3,P B,RR,1,F

t9 t10 t11 t12

C

A,DISC,P A,UA,F B,DISC,P B,UA,F C,DISC,P C,UA,F

77

Tema 4 Funciones y protocolos del nivel de enlace

P
UN 2,4 (con errores) • t0/1/2: conexión A/B/C • t3: sondeo A con envío de una trama de datos que se pierde • t4: expira el timeout y P intenta averiguar el estado de A • t5: P recibe una trama ACK 1 y reenvía la trama de datos perdida en t6 • t7: sondeo B que envía dos tramas de datos • t8: la trama se pierde • t9: sondeo C • t10: sondeo A • t11: sondeo B, indicando la recepción previa de una trama fuera de secuencia, que reenvía la trama perdida y subsiguientes • t12: P confirma tramas pendientes de B • t13/14/15: desconexión A/B/C

3.1 Protocolo HDLC A

t0

B

A,SNRM,P A,UA,F B,SNRM,P B,UA,F

t1

C,SNRM,P C,UA,F

t2

t3 t4 t5 t6

A,I,0,0,* A,I,1,0,P timeout A,RNR,0,P A,RR,1,F A,I,1,0,P A,RR,2,F B,RR,0,P B,I,0,0,* B,I,1,0,F C,RR,0,P C,RR,0,F

t7 t8 t9 t10

A,RR,0,P A,RR,2,F

t11

B,REJ,0,P B,I,0,0,* B,I,1,0,F B,RNR,2,P B,RR,0,F

t12 t13 t14 t15

C

A,DISC,P A,UA,F B,DISC,P B,UA,F C,DISC,P C,UA,F

78

Tema 4 Funciones y protocolos del nivel de enlace

P
UN 2,4 (con errores) • t0/1/2: conexión A/B/C • t3: sondeo A con envío de una trama de datos que llega a B errónea • t4: expira el timeout y P intenta averiguar el estado de A • t5: P recibe una trama NAK 1 y reenvía la trama de datos errónea en t6 • t7: sondeo B que envía dos tramas de datos • t8: la trama se pierde • t9: sondeo C • t10: sondeo A • t11: sondeo B, indicando la recepción previa de una trama fuera de secuencia, que reenvía la trama perdida y subsiguientes • t12: P confirma tramas pendientes de B • t13/14/15: desconexión A/B/C

3.1 Protocolo HDLC A

t0

B

A,SNRM,P A,UA,F B,SNRM,P B,UA,F

t1

C,SNRM,P C,UA,F

t2

t3 t4 t5 t6

A,I,0,0,* A,I,1,0,P timeout A,RNR,0,P A,REJ,1,F A,I,1,0,P A,RR,2,F

t7 t8

B,RR,0,P B,I,0,0,* B,I,1,0,F C,RR,0,P C,RR,0,F

t9 t10

A,RR,0,P A,RR,2,F

t11

B,REJ,0,P B,I,0,0,* B,I,1,0,F B,RNR,2,P B,RR,0,F

t12 t13 t14 t15

C

A,DISC,P A,UA,F B,DISC,P B,UA,F C,DISC,P C,UA,F

79

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


BA 3,8 (con errores) • t0: conexión A/B • t18: B desea saber el estado de A e inicia un ciclo de punteo que también detecta la trama perdida pero más tarde que con el rechazo explícito • t20: A recibe una trama fuera de secuencia y envía una trama NAK 3 • t25: A desea terminar el enlace y se asegura de que no haya tramas en tránsito • t29: desconexión A/B
Con enlaces full-dúplex no se puede usar el número de trama esperada para detectar errores, ¿por qué?

A

t0 t1

B

B,SABM,P

B,UA,F

t2 t3

t5 B,I,0,0,P t7

t7

A,I,0,0,P t9 B,RR,1,F t10 A,I,1,1,* t12 A,I,2,1,* t14 A,I,3,1,* t16 A,I,4,2,* t18 A,I,5,2,P t20

B,I,1,0,*

A,RR,2,F

t14 t15

t18 B,I,2,3,* t20 B,SREJ,3,* t21 A,RR,3,F t23

t22 A,I,3,3,* t24

t25 B,RNR,6,P t26 t27 B,RR,3,F t28 t29 t30

B,DISC,P

B,UA,F

t31 t32

80

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Interfaz del protocolo

• Servicio orientado a la conexión (con asentimiento)

81

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


Interfaz del protocolo

82

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo HDLC


PROBLEMA 7 (Examen de Febrero de 2005). • Dos máquinas A y B se comunican sobre un enlace full-dúplex mediante un protocolo de nivel de enlace derivado de HDLC del tipo BA 3 (repertorio básico + rechazo selectivo con SREJ + numeración módulo 8), con las siguientes órdenes: SABM, DISC, I, RR, RNR; y respuestas: UA, DM, FRMR, I, RR, RNR. El tiempo de transmisión es de 2 ms para cada trama de información y de 1 ms para el resto. El tiempo de propagación es de 2 ms. El tiempo de procesamiento puede despreciarse. El contenido de cada trama debe especificarse mediante la siguiente nomenclatura: [DIRECCIÓN, COMANDO/RESPUESTAS, N(S), N(R), P/F]. Si algún campo no es aplicable, sustitúyalo por un asterisco.

• •

•

Dibuje un esquema detallado indicando las tramas que intercambian A y B si en t0 A inicia la transmisión de la trama de establecimiento de conexión. Dibuje un esquema detallado indicando las tramas que intercambian A y B, suponiendo que en t8 A comienza a transmitir 5 tramas de datos, que la segunda trama de datos que envía A se pierde, que en t9 B comienza a transmitir 2 tramas de datos, y que la segunda trama de datos que envía B llega a A errónea, hasta que todas las tramas de información son confirmadas.

Notas: Describa brevemente el significado de cada una de las instrucciones y respuestas que utilice. El bit P se activará sólo en las tramas de información cuando la estación no pueda enviar más tramas de información. La confirmación de tramas se realizará mediante piggybacking, es decir, sólo se enviarán tramas RR como respuesta a un ciclo P/F cuando la estación no pueda enviar más tramas de información.

83

A

Tema 4 Funciones y protocolos del nivel de enlace

B

3.1 Protocolo HDLC


PROBLEMA 7 (Examen de Febrero de 2005)

•

t0 t1

BA 3 (con errores)

• • • • • • • • • • • •

t0: conexión A/B t8: A comienza a transmitir t9: B comienza a transmitir t14: A no puede enviar más tramas de información e inicia un ciclo de punteo t15: A recibe una trama errónea y envía una trama NAK 1 en t16 t16: B recibe una trama fuera de secuencia y envía una trama NAK 1 t18: B cierra el ciclo de punteo con una trama ACK 1 t19: A recibe una trama NAK 1 y reenvía la trama errónea t19: B recibe una trama NAK 1 y reenvía la trama errónea iniciando un ciclo de punteo t21: A envía la última trama de datos iniciando un ciclo de punteo t23: A cierra el ciclo de punteo con una trama ACK 2 t25: B cierra el ciclo de punteo con una trama ACK 5

B,SAB

M,P

t3 t4 B,UA,F

t6 t8 t9

B,I,0,0,* t10

A,I,0,0,* t11

B,I,1,0,* t12

A,I,1,0,P t13

B,I,2,0,* t14 B,I,3,1,P A,SREJ,1,*

t16 t17 t19

t16 t17 t18 t19

t21

t21

B,I,1,1,*

B,SREJ,1,* B,RR,1,F A,I,1,1,P

B,I,4,1,P A,RR,2,F

t23 t24 t25 t26

B,RR,5,F

t28

84

Tema 4 Funciones y protocolos del nivel de enlace

Índice

1. Introducción 2. Funciones del nivel de enlace ([TAN03] Capítulo 3.1) 3. Protocolos del nivel de enlace 3.1 Protocolo HDLC ([FOR07] Capítulo 11.6) 3.2 Protocolo PPP ([FOR07] Capítulo 11.7)

85

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Necesidad de protocolos de nivel de enlace para comunicación full-dúplex sobre enlaces punto a punto

• • •

PPP sobre medio físico (módems) PPP sobre ATM (router ADSL) PPP sobre Ethernet (interconexión de routers)


PPP (Point-to-Point Protocol) soporta:

• • • • •

Diferentes protocolos de autenticación Múltiples protocolos del nivel de red de manera simultánea Asignación dinámica de direcciones de red Detección de errores (tramas PPP erróneas) Detección de fallos en el enlace y notificación al nivel de red


PPP no soporta ni control de flujo ni enlaces multipunto

86

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Diagrama de estados

87

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Estados

• Inactivo (Idle): el enlace no está siendo usado • Establecimiento del enlace (Establishing) • Negociación de opciones del protocolo de enlace mediante el protocolo de control del enlace LCP

• Autenticación (Authenticating) • Verificación de la identidad del usuario • PAP • CHAP

• Red (Networking) • Negociación de opciones del protocolo de red mediante el protocolo de gestión de red NCP • Transmisión de datos (paquetes del nivel de red)

• Terminación del enlace (Terminating)

88

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Formato de la trama

• Monoformato con campos de significado posicional • Delimitador de inicio/fin de HDLC (0111110) con relleno de caracteres (carácter ESC ó 01111101) • Dirección: fijo (11111111), es decir, no hay direcciones • Control: fijo (UI), es decir, transmisión no fiable • Protocolo: identifica el tipo de paquete del campo de datos

• Protocolo del nivel de red (IP, IPX, AppleTalk,…) o protocolo de gestión de otro protocolo (LCP, NCP,…)

• Información • FCS (Frame Check Sequence) de HDLC

89

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Protocolo LCP (Link Control Protocol)

• Las paquetes LCP van encapsulados dentro de las tramas PPP (Protocol: C02116)

• Establecimiento, configuración y terminación del enlace • Monitorización del estado del enlace

• Formato de los paquetes LCP • Código: tipo de paquete LCP • ID: correspondencia entre peticiones y respuestas • Longitud: tamaño total del paquete LCP

90

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Protocolo LCP (Link Control Protocol) Código 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08 0x09 0x0A 0x0B

Tipo de paquete Petición de configuración ACK de configuración NAK de configuración NAK de configuración Petición de terminación ACK de terminación Rechazo de código Rechazo de protocolo Petición de eco Respuesta de eco Petición de descarte

Descripción Lista de opciones de configuración Acepta las opciones propuestas Algunas opciones no son aceptables Algunas opciones no son reconocidas Solicita la terminación del enlace Acepta la terminación del enlace Código desconocido Protocolo desconocido Intercambio de paquetes (comprobación del enlace) Petición para descartar el paquete (comprobación local)

Opción más comunes Tamaño máximo del paquete Protocolo de autenticación Compresión del campo de protocolo Compresión del campo de control/dirección

Valor por defecto 1500 bytes Ninguno Desactivado Desactivado

91

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Autenticación

• PAP (Password Authentication Protocol)

92

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Autenticación

• CHAP (CHallenge Authentication Protocol)

93

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Protocolo NCP (Network Control Protocol)

• Conjunto de protocolos que permiten negociar opciones para diferentes protocolos del nivel de red

• Protocolo de control protocolo entre redes (IPCP, Internetwork Protocol Control Protocol)

• Gestión de direcciones IP dinámicas, tamaño máximo del paquete, compresión de los datos,…

• La trama IPCP va encapsulada dentro de la trama PPP (Protocol: 802116) • Formato de los paquetes IPCP:

94

Tema 4 Funciones y protocolos del nivel de enlace

3.1 Protocolo PPP


Ejemplo

LCP CHAP IPCP IP sobre PPP (002116)

95

Tema 4 Funciones y protocolos del nivel de enlace

Resumen


Sincronización de trama:

• Delimitadores de principio/fin de trama • Transparencia mediante relleno de caracteres/bits
Coordinación de la comunicación:

• Centralizada (selección y sondeo) • Por contienda
Detección de errores: CRC
Control de flujo y recuperación de errores:

• Parada y espera con ARQ (Automatic Repeat reQuest) • Ventana deslizante con ARQ • Vuelta atrás N (go-back-n) • Rechazo selectivo (selective reject) 96

Tema 4 Funciones y protocolos del nivel de enlace

Resumen


HDLC

• Tipos de estaciones: primarias, secundarias y • • • • •

combinadas Configuración del enlace: punto a punto y multipunto Modos de operación: NRM, ARM y ABM Tramas monoformato: tramas I, tramas S y tramas U Clases de procedimiento: subclases de HDLC Interfaz del protocolo


PPP

• Tramas monoformato • Diagrama de estados • Autenticación: PAP y CHAP • Protocolos LCP y NCP 97