Synchronisation über Netzwerk

Hi,

ich habe N Simulationen mit gleichen Startbedingungen, die auf verschiedenen Rechnern ausgeführt werden und übers Netzwerk (python/twisted) miteinander kommunizieren. Jede Simulation rechnet in der Zeit delta_t einen Schritt. Wie kann ich sicherstellen dass die Simulationen alle möglichst gleichzeitig und gleich schnell ablaufen?

Christoph

Wie präzise soll das sein?

Eine einfache Methode wäre, sich auf die Systemzeit zu verlassen. Praktisch jeder aktuelle PC holt sich die Systemzeit von einem NTP-Server. Das heißt, die Systemzeiten auf den verschiedenen Clients sollten sich nur um Bruchteile von Sekunden unterscheiden, solange die NTP-Synchronisierung läuft (was zugegebenermaßen optimistisch ist).

edit: Das ist ein Problem aus dem Bereich "distributed algorithms". Es gibt mit Sicherheit Standard-Verfahren dafür. Ich habe mal vector clocks gesehen, aber die sind nicht ohne weiteres für die Art von Synchronisierung gedacht, die du suchst. Aber vielleicht findest du in der Richtung Referenzen, die dich weiterbringen.

Was ich ansonsten probieren würde, wäre einen beliebigen Teilnehmer zum Master zu deklarieren (dafür gibt's election algorithms). Alle anderen Teilnehmer müssen sich dann nur noch mit dem Master synchronisieren, und für "Client synchronisiert seine Uhr mit Master" gibt es fertige Algorithmen (z.B. NTP).

SeppJ

dfjkl schrieb:

Hi,

ich habe N Simulationen mit gleichen Startbedingungen, die auf verschiedenen Rechnern ausgeführt werden und übers Netzwerk (python/twisted) miteinander kommunizieren. Jede Simulation rechnet in der Zeit delta_t einen Schritt. Wie kann ich sicherstellen dass die Simulationen alle möglichst gleichzeitig und gleich schnell ablaufen?

Was hast du vor? Willst du allgemein mehr über parallele Simulationen und wie man sie möglichst effizient durchführt wissen? Oder weißt du das schon und hast ein konkretes Problem bei der Umsetzung?

Zum Thema allgemeine parallele Simulationen: Der Trick ist ganz einfach: Man gibt den verschiedenen Prozessen möglichst gleich große Stückchen vom Gesamtproblem. Diese Stückchen sollten groß genug sein, dass sie sehr viel länger daran zu rechnen haben als der Synchronisationsschritt dauert. Wie die Aufteilung konkret durchgeführt wird, kann man nicht allgemein beantworten. Es gibt verschiedene gängige Verfahren mit Vor- und Nachteilen, was am besten passt hängt von deinem Problem/Algorithmus ab.

Dadurch dass die Teilprobleme hinreichend groß sind, fallen Schwankungen in der Rechenzeit durch besonders einfache oder besonders schwer zu rechnende Teilstücke nicht so sehr ins Gewicht, da man davon ausgehen kann, dass ein hinreichend großes Teilproblem im Durchschnitt immer von allem etwas enthält. Ist das System insgesamt sehr heterogen kann das aber auch schiefgehen, dann muss man fortgeschrittenere Algorithmen verwenden (liegt dieser Fall bei dir vor?).

P.S.: Du machst die Simulation in Python und machst dir Sorgen um die Geschwindigkeit? Ich hätte da eine Idee, wie du deine Simulation sehr stark beschleunigen könntest. Fängt mit 'C' an...

Hi,

Was hast du vor?

Ein Spiel. Server und Clients simulieren die Spielwelt. Das bedeutet, sie müssen möglichst gleichzeitig gestartet werden und gleich schnell laufen. Über das Netzwerk werden nur Zustandsänderungen verteilt.

@Christoph: Obiges bedeutet auch, dass ich einen Master habe. Ebenfalls, dass die Genauigkeit nicht so groß sein sollte -- im Bereich von 10 ms bis 30 ms. Das ist in etwa der offset den ich bei ntp habe.

P.S.: Du machst die Simulation in Python und machst dir Sorgen um die Geschwindigkeit? Ich hätte da eine Idee, wie du deine Simulation sehr stark beschleunigen könntest. Fängt mit 'C' an...

ich mache mir keine Sorgen um die Geschwindigkeit, nur um die Synchronität.

Christoph

dfjkl schrieb:

@Christoph: Obiges bedeutet auch, dass ich einen Master habe. Ebenfalls, dass die Genauigkeit nicht so groß sein sollte -- im Bereich von 10 ms bis 30 ms. Das ist in etwa der offset den ich bei ntp habe.

Geringere Abweichungen als NTP wirst du kaum hinbekommen. NTP berücksichtigt bereits Dinge wie Netzwerklatenz, das ist kein ganz triviales Protokoll. Eine maximale Abweichung von 10ms finde ich schon sehr gut. Wie soll eine höhere Abweichung denn überhaupt stören können? Würde sie stören, könntest du sie ja detektieren, und damit auch beheben.

Richtig, das Verfahren setzt voraus, dass du einen Master hast. Aber um bei verteilten Algorithmen einen Master zu wählen, gibt es Standard-Algorithmen (such mal nach "leader election algorithm"). Es muss ja nicht immer derselbe Teilnehmer Master sein. Der Master sollte natürlich genügend Bandbreite besitzen. Das kann ich nicht beurteilen, weil du nicht gesagt hast, ob es um 10 Teilnehmer oder um 100000 geht.

Andererseits sagst du, dass es um Spiel geht, bei dem du einen zentralen Server und Clients hast. Warum genügt es dann nicht, dass die Clients sich mit dem zentralen Server synchronisieren?

rapso

dfjkl schrieb:

Hi,

Was hast du vor?

Ein Spiel. Server und Clients simulieren die Spielwelt. Das bedeutet, sie müssen möglichst gleichzeitig gestartet werden und gleich schnell laufen. Über das Netzwerk werden nur Zustandsänderungen verteilt.

kommt auf das spiel an, bei manchen spielen werden auch nur die eingangsdaten "verteilt".

@Christoph: Obiges bedeutet auch, dass ich einen Master habe. Ebenfalls, dass die Genauigkeit nicht so groß sein sollte -- im Bereich von 10 ms bis 30 ms. Das ist in etwa der offset den ich bei ntp habe.

normalerweise ist die latenz viel groesser als die zeit um die man asynchron laeuft, deswegen macht so ein unterschied nicht soviel aus.
ich weiss ehrlichgesagt kein szenario bei dem asynchronitaet der startzeit ein problem waere, manche spiele werden sogar auf dem server in der zukunft simuliert z.b. in Battlefield Bad Company 2 und alleine schon die asynchronitaet von minitoren wird dich bis zu 16.67ms kosten.

wenn du die spielart verraets, kann man dir besser helfen

Hi,

rapso schrieb:

wenn du die spielart verraets, kann man dir besser helfen

es geht um sowas wie ein RTS. Die mechanik wird eine relativ große Latenz erlauben, technologie ähnlich wie hier: http://www.gamasutra.com/view/feature/3094/1500_archers_on_a_288_network_.php

Es sollen, wie du korrekt gesagt hast, die Benutzereingaben -- genauer, alle nichtdeterministischen Zustandsänderungen -- an alle verteilt werden, die es betrifft.

Meta: Läuft heute eigentlich ein Wettbewerb wer dem OP am meisten in den Mund legen kann?

dfjkl schrieb:

Meta: Läuft heute eigentlich ein Wettbewerb wer dem OP am meisten in den Mund legen kann?

Nein, sondern der "Wer dem OP am meisten aus der Nase zieht"-Tag.

hustbaer

Vorweg: ich hab sowas noch nie gemacht, vielleicht stelle ich mir das zu einfach vor. Also...

Synchronisiere die Clients mit dem Master. Einfach über die ganz normalen Pakete die du so auch überträgst. Der Master kann dabei ja einfach immer seine eigene Zeit mitschicken. Wobei ich mit "Game-Time" arbeiten würde, also nicht Systemzeit sondern z.B. Millisekunden seit Server-Start oder seit Spiel-Start (idealerweise 64 Bit, damit der Server auch mal länger als 7 Wochen laufen kann, ohne dass man mit Überläufen klar kommen muss)

Wenn du am Client feststellst, dass die "eigene" Clock gegenüber der des Masters ständig in die gleiche Richtung driftet, dann rechnest du einen Korrekturfaktor für den Client aus, den er ab dem Moment in seine eigene Zeitberechnung mit einbezieht.

Wenn du zum Synchronisieren dabei nur Antworten auf Pakete erlaubst, die eine Round-Trip-Time von <= K * Durschnittliche-Round-Trip-Time haben (mit vielleicht K = 1.1 oder sowas), dann sollte auch sicher gestellt sein, dass du nie eine "schlechte" (=zu "alte") Zeit zum Synchronisieren nimmst. Zusätzlich erlaubst du einen bestimmten Fehler bevor du die Client-Zeit "re-synchronisierst", z.B. auch 1.x * Durschnittliche-Round-Trip-Time.

Wenn du dann re-synchronisieren musst, kannst du ein Limit für den Betrag setzen, z.B. max. +/- 1 Sekunde, wenn der Unterschied höher ist, dann kickst du den Spieler. Und du setzt die Client-Zeit nicht hart um, sondern verlangsamst bzw. beschleunigst die Client-Clock für ein paar Frames, bis du wieder auf dem richtigen Wert bist.

p.S.: vermutlich kann man mit ein paar ganz einfachen Formeln aus dem Bereich der Statistik hier auch einiges ausrichten. Also auch sehr geringe Offsets/Drifts feststellen und halbwegs gut korrigieren, so lange das Netzwerk halbwegs "gleichmässig" funktioniert. Wenn ich z.B. sehe dass ich in den letzten N Paketen eine Standardabweichung von nur 5ms in den Round-Trip-Times habe, dann kann ich mit geringeren "erlaubten Fehlern" arbeiten, als wenn ich 50ms Standardabweichung hätte. Oder so