relojes - dit.upm.esjoaquin/so/relojes/relojes.pdf · relojes 19 de noviembre de 2006 página: 1 de...
TRANSCRIPT
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:1 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
RelojesJoaquín Seoane [email protected]
Departamento de Ingeniería de Sistemas TelemáticosUniversidad Politécnica de Madrid
19 de noviembre de 2006
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:2 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
ÍndiceTiempo 3
Deriva (drift) y desviación (skew) 5
Consulta a un servidor de tiempo (Cristian) 14
Algoritmo de Berkeley 18
Difusión 20
NTP 21
Mantenimiento de la fecha y la hora 31
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:3 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Tiempo¿Cuánto tiempo ha transcurrido?
¿Tengo que actuar ya?
¿En que orden ocurrieron?
¿En que orden acordamos que ocurrieron?
¿Cuándo sucedió?
¿Cuándo lo hago?
¿Es confiable (eg. autenticación Kerberos)?
¿Pudo haber sido el causante?
Capítulo 11Colouris, 4aed.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:4 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Tipos de sincronización de relojes
Interna (patrón arbitrario):
• Sistemas de tiempo real.
• Análisis de rendimiento.
• Ordenación natural de eventos.
Externa (patrón universal):
• Relacionar con seres humanos.
• Forma indirecta de relacionar procesos desconocidos entre sí.
Lógica:
• Lo importante son las relaciones de causalidad.
• Las duraciones no interesan.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:5 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Deriva (drift) y desviación (skew)Los relojes tienen una deriva ρ | 1− ρ ≤ dR
dt≤ 1 + ρ
Que puede producir una desviación entre extremos de δ = 2ρ∆t
perfe
cto =
1
lento < 1
rápi
do >
1
δ
t
R
Reloj ρMuy malo 10−4
Malo 10−5
Bueno 10−6
Estabilizado 10−7
Atómico 10−13
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:6 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Periodo de resincronización
Resincronizar cada ∆t = δ/2ρ.
R
t
δ
δ/2ρ
Reloj 1 seg 1 mseg 1 µseg
Muy malo 1.4 horas 5 seg 5 msegMalo 14 horas 50 seg 50 msegBueno 5.7 días 14 horas 50 segEstabilizado 57 días 5.7 días 14 horasAtómico 158000 años 158 años 57 días
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:7 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Inversión de tiempo
298
299
303
302
301
300
304
305
300
301
302
303
304
305
306
307
308
309
311
310
300AJUSTE
310
309
308
307
306
305
304
303
302
301
308
307
309
310
311
300AJUSTE
298
299
300
301
302
303
304
305
306 Atrasar un reloj adelantado, puede invertirrelaciones de causalidad.
Adelantar uno atrasado falseará medidas deintervalos =⇒ corrección gradual.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:8 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Regulación de la frecuencia
tt1 t2 t3
R
t4
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:9 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Mantenimiento del reloj del sistema
Inicialmente: Copiar reloj hardware (CMOS) o externo.
Cada interrupción: eg: 10msIncrementar reloj del sistema en memoriaeg: 9999, 10000, 10001 µs (poca resolución).
Cada lectura: Leer reloj del sistema en memoria (poca resolución).
Mejora de resolución: Contador hardware de frecuencia controlada.
Ajuste: Cambiar frecuencia de contador.
Cada lectura: Leer reloj en memoria y sumar contador.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:10 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Realimentación
PLL
VCO
FILTRORI
ti
−
+
Eg.: fi= K (ti−Ri) + fo
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:11 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Observaciones sobre la regulación de frecuencia
K grande produce inestabilidad.
K pequeña produce lentitud.
La convergencia mejora introduciendo el error de frecuencia:+k2(ti − ti−1 −Ri + Ri−1)
La actuación sobre la frecuencia es discreta.
Limitar frecuencias, máxima y mínima.
El objetivo ti puede ser erróneo.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:12 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Primitiva en Linux
int adjtimex(struct timex *buf);
struct timex {int modes; /* valores a modificar */long offset; /* ajuste de hora (microseg) */long freq; /* ajuste de frecuencia (ppm escalada) */long maxerror; /* error maximo (microsegundos) */long esterror; /* error estimado (microsegundos) */int status; /* orden/estado del reloj */long constant; /* constante de tiempo del pll */long precision; /* precisión del reloj (microseg) (lectura) */long tolerance; /* tolerancia de la frecuencia del reloj (ppm) (lectura) */struct timeval time; /* hora actual (lectura) */long tick; /* microsegundos entre ticks del reloj */
};
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:13 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Valores a modificar
#define ADJ OFFSET 0x0001 /* ajuste de la hora */#define ADJ FREQUENCY 0x0002 /* ajuste de la frecuencia */#define ADJ MAXERROR 0x0004 /* error maximo de la hora*/#define ADJ ESTERROR 0x0008 /* error estimado de la hora */#define ADJ STATUS 0x0010 /* estado del reloj */#define ADJ TIMECONST 0x0020 /* constante de tiempo del pll */#define ADJ TICK 0x4000 /* valor tick*/#define ADJ OFFSET SINGLESHOT 0x8001 /* ajuste inmediato de hora */
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:14 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Consulta a un servidor de tiempo (Cristian)
I
To
d
T1 τ
Ts
CLIENTE SERVIDOR
To
To, Ts
τ1
Ajustar a Ts + τ ,pero τ es desconocido.
Estimamos τ como τe,suponiendo que es igual a τ1.
τe = (T1−T0−I)2 = d−I
2
τe = (T1−T0)2 = d
2 , si I = 0.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:15 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Acotación del error
τ
τ
τ
τ
min
min
I
I
d
d
τ = τmin
ε = τe − τmin = d−I2 − τmin
τ = d− I − τmin
ε = d−I−τmin−τe = d−I−τmin− d−I2 = d−I
2 −τmin
El error es menor con retardo menor.
Se pueden repetir medidas hasta obtener el error desea-do.
Si el retardo es el mínimo, el error es 0:ε = d−I
2 − τmin = 2τmin+I−I2 − τmin = 0
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:16 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Mensajes del Algoritmo de Christian
Retardo pequeño−→ datagramas.
Pérdida de datagramas:−→ consulta lleva T0.−→ respuesta lleva T0 y Ts.
Con los datgramas que llegan y T1 se obtiene ajuste y cota de error.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:17 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Discusión del Algoritmo de Christian
Punto único de fallo:
• Elección de sustituto.
• Considerar varios servidores.
◦ Promediar.
Vulnerable:
• Mal funcionamiento.
◦ Recortar desvíos excesivos.
• Traidores.
◦ Autentificación criptográfica.
¿Tráfico excesivo?.
• No escalable.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:18 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Algoritmo de BerkeleyMAESTRO ESCLAVOS
¿hora?
¿hora?
¿hora?
t1
t2
t3
o1,d1
o2,d2
o3,d3
DISCRIMINA
Y PROMEDIA
O´1
O´2
O´3
vale
vale
1. Obtiene desviación estimada, oi, y retardode ida y vuelta, di, de los esclavos.
2. Elimina desviaciones y retardos excesivos.
3. Calcula o como media de los oi válidos.
4. Manda a todos corregirse oi − o.
5. Espera confirmación.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:19 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Algoritmo de Berkeley
Consenso dictado por el maestro.
“Molesta” poco a los esclavos.
Menos tráfico que consulta activa:4× (N − 1)←→ 2×N × (N − 1)
Elección de maestro si se cae.
Al arrancar:
• Se ubica en el maestro.
• Se le pide la hora.
• Se pasa a modo esclavo.
Tolera relojes malos.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:20 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
DifusiónEl servidor activo difunde la hora periódicamente.
Los receptores acuerdan la misma hora (salvo latencia de interrupción).
ε = retardo + latencia de interrupción.
• Sin colisión→ pequeño, repetible, compensable.
• Con colisión→ repetición en seguida (detectada por hardware).
• Con pérdida→ solicitud de ajuste.
Descentralizable:
• Todos difunden.
• Todos aceptan la N2 orden (tolera N
2 − 1 incorrectos).
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:21 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
NTP
Internet:
• Retardos muy variables.
• Pérdidas de conectividad.
• Millones de máquinas.
• Inseguridad.
Solución:
• Filtrado y selección de fuentesmejores.
• Redundante.
• Escalable.
• Tolerante a ataques.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:22 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
red NTP
ESTRATO 1
(Secundarios)ESTRATO 2
(Primarios)
ESTRATO 3
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:23 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Modos NTP
Multicast 7−→ red local (poco preciso).Un servidor difunde periódicamente su hora.
Llamada a procedimiento 7−→ más preciso (Cristian).El cliente pide hora, pero no la da.
Simétrico 7−→ vigilancia mutua.Dos interlocutores están dispuestos a darse la hora mutuamente.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:24 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Asociaciones NTPPeriodo.
Historias (8 últimas muestras):
• Retardos.
• Desplazamiento.
• Alcanzabilidad.
Estadísticos.
...
...asoc1
...
...asoc2
...
...asoc3
...
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:25 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Medidas NTPTi−1
Ti − 2Ti − 1
Ti−2
TiTi−3
t t´Ti − 3
di = t + t′ = (Ti − Ti−3)− (Ti−1 − Ti−2)Ti−2 = Ti−3 + t + oi ∧ Ti = Ti−1 + t′ − oi
=⇒ oi = ((Ti−2 − Ti−3) + (Ti−1 − Ti) + t′ − t)/2oie = ((Ti−2 − Ti−3) + (Ti−1 − Ti))/2oie − di/2 ≤ oi ≤ oie + di/2 (despreciando τmin e I).
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:26 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Filtradooi−7 oi−6 oi−5 oi−4 oi−3 oi−2 oi−1 oi
di−7 di−6 di−5 di−4 di−3 di−2 di−1 di
o estimado (el de menor d).
No se utiliza para ajustar reloj local.
Se calcula la dispersión.
Se utitiza en el algoritmo de selección de referencia.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:27 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Dispersión de las muestras
Mide la fiabilidad (calidad) de las muestras.
Es proporcional a la medida de las diferencias entre los desplazamientos yel desplazamiento estimado, dando más peso a las mejores muestras:S =
∑7i=0 |oi − o0| × 0,75i
Sirve para calcular la dispersión de sincronización con la raíz:∑S
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:28 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
El paquete NTP
LI NV Modo Estrato Intervalo PrecisiónDistancia de sincronización
Dispersión de sincronización......
Tiempo origen (Ti−3)Tiempo recepción (Ti−2)
Tiempo envío (Ti−1)Número de clave
Firma digital
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:29 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Criteros de selección de par
Fiabilidad:
• Bajo estrato.
• Baja dispersión.
Exactitud:
• Bajo estrato
• Baja distancia.
FALSETICKERS
TRUECHIMERS
UTC
¡No algoritmo de promediado!
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:30 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Algoritmo de selección de par
Candidatos fiables:
• Ordenar por estrato y dispersión.
◦ Eliminar dispersiones excesivas.◦ Seleccionar cinco.
Candidatos exactos:
• Ordenar por estrato y distancia.
• Repetidamente.
◦ calcular: εj =∑m−1
i=0 |oj − ok| × 0,75k
◦ eliminar el mayor εj (empate−→ mayor j)
hasta que haya uno.
Índice
I
J
II
JJ
Página
Pantalla
Imprimir
Cerrar
Salir
Relojes
19 denoviembrede 2006
Página:31 de 31
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Mantenimiento de la fecha y la horaContador el núcleo: segundos atómicos desde la época.
• Unix – 1970 (NTP – 1900)
• Un segundo atómico = 9192631770 transiciones de Cs133.
Mide intervalos.
Permite calcular fecha y hora UTC a partir de:
• Huso horario.
• Regulaciones de ahorro de energía.
• Conocimiento de años bisiestos.
• Segundos insertados (leap seconds).