estructura de protocolo
Post on 02-Jul-2015
193 Views
Preview:
TRANSCRIPT
1
Ingeniería de protocolos
Tema 2. Estructura de un protocolo
Texto original: Mª del Carmen Romero (mcromero@dte.us.es)Parcialmente modificado: Jaime Benjumea (benjumea@dte.us.es)
2
Estructura de un protocolo
1. Introducción2. Los cinco elementos de un protocolo3. Servicio y entorno4. Vocabulario y formato de los mensajes5. Reglas de procedimiento6. Diseño de un protocolo estructurado7. Mecanismos básicos de los protocolos
3
d
A B
Introducción
Acuerdos sobre:- Inicio y final del intercambio de datos- Sincronización de emisores y receptores- Detección y corrección de errores de transmisión- Formateo y codificación de los datos
4
señal eléctrica
bits
símbolos/caracteres
campos de mensaje
tramas/paquetes
Introducción
Niveles de abstracción
5
Los cinco elementos de un protocolo
1. Servicio que proporciona el protocolo
2. Suposiciones sobre el entorno donde se ejecuta el protocolo
3. Vocabulario de los mensajes utilizados en el protocolo
4. Formato de los mensajes del vocabulario del protocolo
5. Reglas de procedimiento que controlan la consistencia del
intercambio de mensajes
6
Servicio y entorno
P2 P1 P1 P2
Canal virtual
P2 P1PoP1P2Pn Pn
Envolturas de datos
P1: Testeador + generador de paridad (8 bits)P2: Codificador + decodificador (7 bits)
• Virtual: es algo que parece que existe pero, en realidad, no existe.
• Transparente: es algo que, en realidad, existe pero que parece que no existe.
7
Servicio y entornoVentajas del diseño por niveles:- Ayuda a distinguir la estructura lógica del protocolo, al separar tareas de alto nivel de las de bajo nivel- Facilita la escalabilidad del protocolo
Actores del modelo de diseño:- Un nivel o capa define un grado de abstracción de un protocolo,agrupando funciones relacionadas y separando las independientes- Un interfaz separa (y une) dos niveles distintos de abstracción
A B
Nivel N+1
Nivel N-1
Nivel NProtocolo par Entidad par
Primitivas de servicio
Servicio
8
Usuario de servicio(Capa N)
Usuario de servicio(Capa N)
Suministrador del servicio (Capa N-1)
X.request
X.indication
X.responseX.confirm
Servicio y entorno
Usuario Usuario
DL-DATA.request(DATO)
Enlace
PH-DATA.ind(SEC,DATO)PH-DATA.req(SEC, ACK)
Enlace
DL-DATA.indication(DATO)
Medio físico
Transmisor Receptor
PH-DATA.req(SEC, DATO)PH-DATA.ind(SEC,ACK)
Primitivas:
- De petición de servicio- De indicación de servicio
- De respuesta (de entidad par)- De confirmación (del suministrador
del servicio)
Diagrama decorrelación de
primitivas
9
Vocabulario y formato de mensajes
- Se define para cada nivel- Dos tipos de protocolos en cuanto formato de mensajes:
- protocolo orientado a bitTx datos como flujo de bits sin longitud definida (flagsde inicio y fin). Ej: HDLC
- protocolo orientado a carácterTx datos en bloques de n bits (o múltiplos de n) (caracteres marcadores de inicio y fin). Ej: Carácter STX(Start of TeXt) y ETX (End of TeXt)
STX c1 c2 c3 cn ETX...
STX c1 c2 DLE cn ETX...DLE DLEDLECharacter stuffing
10
Vocabulario y formato de mensajes
- Formato = { cabecera, datos, cola }• cabecera = { tipo, destino, nº secuencia, longitud }
» tipo = { ack, nack, err }• cola = { checksum, dirección de retorno }
11
Estado i
Estado i+1
evento1[condicion1]/accion1
evento2[condicion2]/accion2
evento0[condicion0]/accion0
Reglas de procedimiento- Procesos concurrentes- Necesitamos herramientas más formales: diagrama temporal, máquina de estados finitas, ESTELLE...
12
Diseño estructurado de protocolos1. Simplicidad2. Modularidad3. Protocolos bien formados
- NO sobre-especificado- NO incompleto- Acotado- Autoestabilizado- Autoadaptable
4. Robustez- Evolución automática con la tecnología
5. Consistencia- Bloqueos- Bucles infinitos- Terminaciones impropias
13
Diseño estructurado de protocolosLas diez reglas de diseño:
1. Asegurarse de definir bien todos los aspectos del protocolo
2. Definir el servicio a realizar por cada nivel antes de elegir estructuras
3. Diseñar antes funcionalidad externa que la interna
4. Mantener el diseño simple
5. No conectar lo que es independiente
6. Obviar aquello que es innecesario
7. Validar el diseño antes de implementarlo
8. Implementar diseño, medir su rendimiento y optimizarlo
9. Comprobar que la versión final cumple los criterios de diseño
10. Nunca saltarse las 7 primeras reglas
14
Mecanismos básicos de los protocolos
1. Control de secuencia y control de errores- Redundancia- Tipos de códigos- Códigos de paridad- Corrección de errores (varios métodos)
2. Control de flujo- protocolo simple sin control de flujo- protocolo Xon-Xoff- protocolo de parada y espera- protocolo de parada y espera con timeout- protocolo de bit alternante- protocolos de ventana
15
Control de secuencia y de errores- Mayor número de errores debido a la comunicación que al hardware
P(circuitería)<10-15
P(F.O.) ≈10-9 P(coax.) ≈10 -6 P(tlf.) ≈10 -4 ó 10 -5
- Causas principales de error:- limitaciones en el ancho de banda del canal (distorsión lineal)- eco, ruido blanco, impulsos electromagnéticos... (no lineal)
- El efecto de esos ruidos se puede paliar hasta cierto punto conhardware y el resto por software (no se eliminan)
- El esquema de control de error debe ser adecuado a las característicasde la línea de comunicaciones:
. Si un canal sólo tiene inserciones, no sirve un protocolo queproteja contra eliminaciones
. Si un canal produce errores simples, puede ser más adecuadousar un protocolo más simple
. Si el error del canal es < que el de la circuitería, el mecanismode control sólo degrada rendimiento del sistema y disminuye fiabilidad del protocolo
16
Control de secuencia y de errores. Redundancia- Añadir información redundante a los mensajes - Dos formas de gestionar los errores:
- Control de errores hacia delante ð códigos correctores- Control de errores por realimentación ð códigos detectores
p≡probabilidad de error en la transmisión de un mensajef ≡fracción de errores que capta el método de controlerror residual=p·(1-f)
- Si p↓ ð no código corrector (ralentiza las comunicaciones)Si p↑ ð no código detector (las reTx también podrían ser erróneas)
- También depende del coste: si p↓ y coste de reTx↑ ð código corrector
- Sistema mixto: el receptor corrige los errores más frecuentes y solicita reTx de los mensajes alterados por errores menos frecuentes
17
Control de secuencia y de errores. Tipos de códigos• Códigos de bloque:
. palabras de código de misma longitud y codificación estática• Códigos de convolución:
. palabras de código dependen del mensaje actual y de anteriores, el codificador cambia su estado con cada mensajeprocesado, longitud de palabras suele ser constante
Se pueden clasificar en:ØCódigos lineales: combinación lineal de palabras válidasØCódigos cíclicos: rotación cíclica de código válidoØCódigos sistemáticos: mensaje original + bits de comprobación
Razón de código=d/(d+e)d ≡ nº de bits de informacióne ≡ nº de bits redundantes
18
Control de secuencia y de errores. Corrección de errores
• Los códigos se eligen de forma que haya varios bits de diferencia entre dos palabras válidas• Rxor reconstruye mensaje, asociándole la palabra de código más cercana• Razón de código de sistema corrector < razón de código de sistema detector• Se usa sistema corrector si hay:
– un retraso de transmisión alto– ausencia de canal de retorno– una tasa de errores alta
Código válido
Código alterado
19
Control de secuencia y de errores. Código corrector basado en paridad
LRC= Longitudinal Redundancy CheckVRC= Vertical Redundancy Check
d=28 bitse=12 bitsRazón de código=28/(28+12)=0.7
LRC
D = 1 0 0 0 1 0 0 0
A = 1 0 0 0 0 0 1 0
T = 1 0 1 0 1 0 0 1
A = 1 0 0 0 0 0 1 0
VRC 0 0 1 0 0 0 0 1
Permite la corrección de 1 bit
20
Control de secuencia y de errores. Método Van Lint
- n tiradas de una moneda por segundo.- canal de 2n bps.- tasa de errores de 2·10-2; p=0.02
q=0.98 (probabilidad no-error)ð cada par de tiradas se codifica con 4 bits.ð Z=q4+3*q3p (prob. de no-error nueva)
Resultado Código
XX 0000
CX 1001
XC 0111
CC 1110
Códigos válidos Resultado
0000 1000 0100 0010 XX
1001 0001 1101 1011 CX
0111 1111 0011 0101 XC
1110 0110 1010 1100 CC
en tr
ansm
isor
en r
ecep
tor
El código resiste errores en 1 bit de los 3 primeros de la palabra
W=1-Z=0.0212 (para DOS tiradas).Antes tenía P=p1+p2=0.04
üReduce a la mitad la probabilidad de error.
21
Control de secuencia y de errores. Distancia de Hamming
• Distancia de Hamming: diferencia de bits mínima entre dos palabras de un código.
• Si la distancia de Hamming de un código es n, se puede:– Detectar errores de hasta n-1 bits– Corregir errores de hasta (n-1)/2 bits
• ↑distancia de Hamming ð ↑fiabilidad de protocolo
XOR(2 palabras de código)
22
Control de secuencia y de errores. Código de Hamming
• Para que un código de k bits de datos y r bits redundantes sea capaz de corregir errores simples debe cumplir: • Los códigos que verifican lo anterior con r mínimo se denominan óptimos• Ejemplo: k=7 (ASCII), r mínimo / k+r+1≤ 2rð r=4 ð n=11‘a’≡ 1 1 0 0 0 0 1
1 2 3 4 5 6 7 8 9 10 111 1 0 0 0 0 1
Los bits redundantes ocupan las posiciones potencia de 2 (1,2,4,8), el resto son los bits de datos
rkrk krkr 212)1(2 <=++⇒<=++⋅ +
23
Control de secuencia y de errores. Código de Hamming (II)
1 2 3 4 5 6 7 8 9 10 11A B 1 C 0 0 0 D 1 0 0
A => Paridad: 1; 3; 5; 7; 11; 13... B => Paridad: 2 a 3; 6 a 7; 10 a 11;…C => Paridad: 4 a 7; 12 a 15; 20 a 23;…D => Paridad: 8 a 15; 24 a 31;…
Bit 3: A+B+C+D Bit 9: A+B+C+DBit 5: A+B+C+D Bit10: A+B+C+DBit 6: A+B+C+D Bit11: A+B+C+DBit 7: A+B+C+D
Cada bit de datos reales, está “protegido” por una serie de bits de paridad dependiendo de la posición que ocupe.
Consecuente con lo anterior, cada bit de paridad (A-D) se calcula teniendo en cuenta esta tabla.
24
Control de secuencia y de errores. Código de Hamming (II)
ð posición del error
XOR
1·20 +1·21 +1·23 +0·24 = 7
25
Control de secuencia y de errores. Ráfagas
• La mayor parte de las veces los errores no se producen
de forma aislada.• Mecanismos correctores tolerantes a ráfagas:
- Códigos de interlineado
- Reed-Solomon
• Se ha demostrado que en la mayoría de los casos es
mejor el control por realimentación (↑aprovechamiento del
canal y ↓error residual).
• k datos de n bits ð matriz kxn• se Tx por columnas ð corrige ráfagas ≤ k
• CDs, DVDs, códigos de barras, comunicaciones inalámbricas, comunicaciones satélite, TV digital, modemsde alta velocidad
26
Control de secuencia y de errores. Código de redundancia cíclica (CRC)
• Mensajes de n bits se tratan como polinomios de grado n-1: 101 = x2 + 1.
• El código de comprobación se obtiene dividiendo el polinomio del mensaje por un polinomio generador G => se halla el resto y se le añade al mensaje
• El mensaje recibido es correcto si el divisible por G. No se detecta el error cuando es divisible por G.
• Ejemplos de polinomios: – CRC-12: x12+x11+x3+x2+1
– CRC-16: x16+x15+x2+1
– CRC-CCITT: x16+x12+x5+1
• CRC-CCITT detecta:– Cualquier número impar de errores simples
– Todos los errores dobles
– Todas las ráfagas de 16 o menos bits
– El 99’997% de las ráfagas de 17 bits
– El 99’998% de las ráfagas de 18 o más bits
P·xr
GT=P·xr - R
Detecta ráfagas ≤ r
27
Control de secuencia y de errores. Checksum aritmético
• Método de Fletcher (1982)
• Sólo sumas y módulos, es simple, pero con buena detección de errores
• Inferior al CRC, detecta ráfagas de 1 a 14 bits (excepto de 8)
• Estandarizado como parte de protocolo estándar transporte (clase 4) de ISO
unsigned short cksum (register unsigned char *s, register int n){register int c0=0, c1=0;do{
c0 = (c0 + *s++) % 255;c1 = (c0 + c1) % 255;
}while (--n>0);return (unsigned short) (c1<<8+c0);
}
Menor carga de procesamiento Menor latencia
28
Control de flujo
• Objetivos:– Asegurarse que no se transmiten los datos
más rápido de lo que se puede procesar.– Optimizar el uso del canal.– Evitar saturar el canal.– Proteger la transmisión contra borrado,
inserción, duplicación y reordenamiento de mensajes.
29
Control de flujo
• Protocolo simple sin control de flujo• Protocolo Xon-Xoff• Protocolo de parada y espera• Protocolo de parada y espera con
timeout• Protocolo de bit alternante• Protocolo de ventana
30
Tx Rx
DL-DATOS.request /PH-DATOS.request
PH-DATOS.indication /DL-DATOS.indication
Transmisor Receptor
Control de flujo. Protocolo simple sin control de flujo
• OK si Rxor más rápido que Txorð se viola el principio “no hacer suposiciones de la velocidad relativa de procesos concurrentes”• Rx es más costoso que Tx
31
Control de flujo. Protocolo XON-XOFF
DL-DATOS.request / PH-DATOS.request
X-OFF / -
TransmisorTransmisor
Esperando
TxX-ON/-
NOTAS:
• X-OFF y X-ON son tramas de control que llegan a través de la primitiva PH-DATOS.indication.
• Mientras espero, los DL-DATOS.request no se pierden, se ponen en una FIFO.
• En el estado Tx, los DL-DATOS.request se obtienen de la FIFO.
32
Control de flujo. Protocolo Xon-Xoff
Elemento_procesado [n<=min] /Xon; DL-DATOS.indication; n--
Sólo procesando
(Xoff)
Rx yprocesandomensajes
PH-DATOS.indication [n<max]; n++ /Procesar_elemento
PH-DATOS.indication [n>max]; n++ / Xoff; Procesar_elemento
Elemento_procesado [n>min] / DL-DATOS.indication; n-- ReceptorReceptor
Elemento_procesado / DL-DATOS.indication; n--
NOTAS:
• Procesar_elemento: Inicia el procesado del dato recibido.
• Elemento_procesado: Indica que el dato anterior ya está procesado y se puede entregar al nivel de red.
• Si llegara algún dato mientras estado es x-off, se queda en la FIFO de PH_DATOS.indication.
•MAX y MIN son los valores de highwatermark y lowwatermark respectivamente.
33
Control de flujo
• Protocolo Xon-Xoff, características:– No requiere negociación previa.– Si se pierde Xoff ð el transmisor no para.– Si se pierde Xon ð bloqueo de los cuatro procesos.– Los dos anteriores se pueden solucionar, pero estos de aquí
no:• No se protege contra la saturación de forma efectiva.• No se protege contra la pérdida de mensajes.
34
Esperando
Transmisor
Tx
PH-DATOS.indication[CRC OK] / -
DL-DATOS.request/PH-DATOS.request
PH-DATOS.indication[CRC no OK] / -
Timeout / PH-DATOS.request
Control de flujo. Protocolo parada y espera con timeout y errores de canal
Rx
Receptor
PH-DATOS.indication [CRC OK] / DL-DATOS.indicationPH-DATOS.request
PH-DATOS.indication
[CRC no OK] / -
Recordar:
• Existen FIFOs, mientras espero, no se pierden datos.
• Los PH_DATOS.* llevan tanto datos como acks.
35
Control de flujo• Protocolo de parada y espera con timeout
– Desaparece problema de saturación en Rxor– Se desaprovecha el canal– Retraso de 2Tp+Ttx,dato+Ttx,ack por cada mensaje enviado
• Tp: tiempo de propagación.• Ttx,dato: Tiempo de transmisión del dato.• Ttx,ack: Tiempo de transmisión del ack.
– Protege contra la pérdida de tramas– En determinadas ocasiones, se pueden recibir
erróneamente datos duplicados aUna solución: numerar mensajes y ack’s.
36
Control de flujo• Protocolo de bit alternante
– Timeout + nº de secuencia de 1bit
• Problema si el ack tarda en llegar:
a(0)ack de a
b(1)
retrasoack de b
timeout
c(0)ack de b
c(0)
Transmisor Receptor
37
• Protocolo de ventana– En la fase de establecimiento de conexión se negocia tamaño de la ventana (W)– El Txor puede enviar W mensajes sin esperar acuse de recibo del Rxor– Optimiza canal en los que el tiempo de tránsito es alto– Control de error en ventana deslizante:
• Los reconocimientos tienen que numerarse, ACK1 significa que se recibió correctamente la 0
• Si se pierde un mensaje y llega el siguiente:– se rechaza: vuelta a atrás ó -se acepta: reTx selectiva
• Reconocimientos globales: ACK4 implica Rx OK de 1..3– Ventana de Tx: mensajes enviados pendientes de ack (de tamaño variable, pero
limitada a W)– Ventana de Rx: nºs de secuencia que Rxor espera Rx (de tamaño fijo)– Para el rango de los nºs de secuencia debe cumplirse:
• rango(nºs secuencia)=>K+N• donde K es el tamaño de la ventana de Rx y N el tamaño máximo de la ventana
de Tx• en caso contrario podrían darse duplicaciones
Control de flujo
38
Control de flujo. Protocolo de ventana con detección de errores
v ≡ nº de mensajes pendientes de ackN ≡ tamaño de la ventana de Txs ≡ nº de secuencia del último mensaje enviadoa ≡ nº de secuencia del mensaje más antiguo enviado y sin confirmardato[x] ≡ almacena el dato que fue enviado con nº de secuencia xd ≡ dato que se quiere enviarp ≡ nº de secuencia recibido en ackM ≡ rango de números de secuencia disponible
Acciones:pendiente[i] ≡ el mensaje con nº de sec i se apunta como enviado y pendiente de ackpendiente[i] ≡ el mensaje con nº de sec i se apunta como confirmado
v+ ≡ se incrementa en uno el nº de mensajes pendientes de confirmación
v- ≡ se decrementa en uno el nº de mensajes pendientes de confirmación
NotaciónNotación
39
Control de flujo. Protocolo de ventana con detección de errores
TransmisorTransmisor
Tx Límiteventana
1/1
Entradas1. DL-DATOS.request(d)[v< N-1]
(se quieren enviar datos y caben más mensajes en la ventana)2. DL-DATOS.request(d)[v= N-1]
(se quieren enviar datos y se llega al límite de la ventana)3. PH-DATOS.indication(ack,p)
(llega un acuse de recibo positivo del mensaje con nº sec p)
4. PH-DATOS.indication(-,p) no OK(llega una indicación errónea)
5 . Timeout de la trama p
(expira el temporizador de retransmisión)
Salidas1. PH-DATOS.request(d,s); v+ ; pendiente[s]; dato[s]=d; s=(s+1)%M
(envía dato con nº de sec s, incrementa el nº de mensajespendientes de confirmación, apunta el nº de sec como pendiente,almacena el dato enviado con ese nº de sec y se prepara elnº de sec para el siguiente mensaje)
2. para i desde a hasta p en módulo M hacer:v-; pendiente[i](decrementa el nº de mensajes pendiente de confirmación enfunción de los que se hayan confirmado y los marca comoconfirmados)
3. PH-DATOS.request(dato[p],p)(retransmite dato con sec=p)
4. Nada
3/2
4/4
5/3
2/1
5/3
4/4
3/2
40
ReceptorB
ACK1
ACK2
ACK3
ACK4
A0(n.seq=0)
TransmisorA
A1(n.seq=1)
A2(n.seq=2)
A3(n.seq=3)
A4(n.seq=4)
A5(n.seq=0)
A6(n.seq=1)
A7(n.seq=2)
Hasta que no llega el ack de A0, el emisorno puede seguir transmitiendo
Control de flujo. Protocolo de ventana
Se ha llegado al límite de la ventana de transmisión
Se “reutiliza” el número de secuencia
Recordemos que los ack indican el
número que espero (y no el recibido)
Ventana de Tx: 4
Ventana de Rx: 1
Núm. Seq: 4+1=5
41
A0 (nseq 0)
TransmisorA
ReceptorB
A1 (nseq 1)
A2 (nseq 2)
A3
B0
B1
B2
B3A4
A5
A6
A7
timeout
B0
B1
B2
B3
Se retransmite
A los acepta y piensa que los datos de la
ventana anterior han llegado bien
Control de flujo. Protocolo de ventana (errores)
W=4 (v. trans)
K=1 (v. recep)
¡Núm. Seq= 4!
42
A0
TransmisorA
ReceptorB
A1
A2
A3
B0
B1
B2
B3
A0
A1
A2
A3
timeout
B0
B1
B2
B3
Se retransmite
B los acepta y piensa que son los datos de la
ventana siguiente , y sin embargo, están duplicados
Control de flujo. Protocolo de ventana
top related