Medición de la diferencia de tiempo entre dispositivos en red

Question

Estoy agregando multijugador en red a un juego que he hecho. Cuando el servidor envía un paquete de actualización al cliente, incluyo una marca de tiempo para que el cliente sepa exactamente cuándo esa información es válida. Sin embargo, la computadora del servidor y la computadora del cliente pueden tener sus relojes configurados en diferentes momentos (tal vez incluso unos pocos segundos de diferencia), por lo que la marca de tiempo del servidor debe traducirse a la hora local del cliente.

Entonces, me gustaría saber la mejor manera de calcular la diferencia de tiempo entre el servidor y el cliente. Actualmente, el cliente pings el servidor para un sello de tiempo durante la inicialización, toma nota de cuándo se envió la solicitud y cuándo fue respondida, y adivina que la marca de tiempo se generó aproximadamente a la mitad del recorrido. El cliente también ejecuta 10 de estas pruebas y toma el promedio.

Pero, el problema es que obtengo resultados diferentes en ejecuciones repetidas del programa. Dentro de cada conjunto de 10, cada medición rara vez diverge en más de 400 milisegundos, lo que podría ser aceptable. Pero si espero unos minutos entre cada ejecución del programa, los promedios resultantes pueden estar en desacuerdo hasta en 2 segundos, lo que no es aceptable.

¿Hay una mejor manera de descubrir la diferencia entre los relojes de dos dispositivos en red? ¿O hay al menos una forma de modificar mi algoritmo para obtener resultados más precisos?

Detalles que pueden o no ser relevantes: los dispositivos son iPod Touch que se comunican a través de Bluetooth. Estoy midiendo que los pings oscilan entre 50 y 200 milisegundos. No puedo pedirles a los usuarios que sincronicen sus relojes. :)

---

Actualización: Con la ayuda de las siguientes respuestas, escribí una clase objetivo-c para manejar esto. Lo publiqué en mi blog: http://scooops.blogspot.com/2010/09/timesync-was-time-sink.html

Answer 1

Recientemente tomé una clase de una hora sobre esto y no fue lo suficientemente largo, pero trataré de reducirlo para que apuntes en la dirección correcta. Prepárate para un poco de álgebra.

Vamos a igualar el tiempo según el servidor. Deje que c iguale el tiempo según el cliente. Deje d = s - c. d es lo que se agrega al tiempo del cliente para corregirlo a la hora del servidor, y es lo que tenemos que resolver.

Primero enviamos un paquete desde el servidor al cliente con una marca de tiempo. Cuando ese paquete se recibe en el cliente, almacena la diferencia entre la marca de tiempo dada y su propio reloj como t1.

El cliente luego envía un paquete al servidor con su propia marca de tiempo. El servidor envía la diferencia entre la marca de tiempo y su propio reloj al cliente como t2.

Tenga en cuenta que t1 y t2 incluyen el "tiempo de viaje" t del paquete más la diferencia de tiempo entre los dos relojes d.Suponiendo por el momento que el tiempo de viaje es el mismo en ambas direcciones, ahora tenemos dos ecuaciones con dos incógnitas, que pueden ser resueltos:

t1 = t - d 
t2 = t + d 
t1 + d = t2 - d 
d = (t2 - t1)/2 

El truco viene debido a que el tiempo de viaje no siempre es constante, como lo demuestra por tus pings entre 50 y 200 ms. Resulta más preciso usar las marcas de tiempo con el mínimo tiempo de ping. Esto se debe a que el tiempo de ping es la suma de la demora "bare metal" más cualquier demora que se aguarde esperando en las colas del enrutador. De vez en cuando, un paquete de la suerte pasa sin retrasos en la cola, por lo que utiliza ese tiempo mínimo como el tiempo más repetible.

También tenga en cuenta que los relojes funcionan a diferentes velocidades. Por ejemplo, puedo reiniciar mi computadora en casa al milisegundo y un día más tarde será 8 segundos más lenta. Eso significa que debes reajustar continuamente d. Puede usar la pendiente de varios valores de d calculados a lo largo del tiempo para calcular su deriva y compensarla entre mediciones, pero eso está más allá del alcance de una respuesta aquí.

Espero que las ayudas te dirijan en la dirección correcta.

Answer 2

Su algoritmo no será mucho más preciso a menos que pueda usar algunos métodos estadísticos. En primer lugar, 10 probablemente no sea suficiente. El primer y más simple cambio sería reunir 100 muestras de tiempo de tránsito y arrojar el x más largo y más corto.

Otra cosa para agregar sería que ambos clientes envían su propia marca de tiempo en cada paquete. Luego también puede calcular cuán diferentes son sus relojes y verificar la diferencia promedio entre los relojes.

También puede verificar las implementaciones STNP y NTP específicamente, ya que estos protocolos lo hacen específicamente.