Re: Networking (was Re: [glob2-devel] Glob2 salvage proposal)

[Andrew Sayers]

On Mon, Oct 24, 2005 at 05:38:23PM +0100, Andrew Sayers wrote:
> *** Latency

A few more thoughts about latency in general.  So far as I can tell, the
current network implementation has two distinct concepts - latency and
delay.  I think the latency of a connection has to do with the number of
ticks ahead of time an order needs to be sent, while I'm fairly certain
that the delay has to do with slowing the game down to deal with slow
computers.  Search for "SDL_Delay" in Engine.cpp to have a look at
delays in use:
        
http://savannah.nongnu.org/cgi-bin/viewcvs/glob2/glob2/src/Engine.cpp?rev=1.138&content-type=text/vnd.viewcvs-markup
This means that ticks are effectively variable already, not hardwired to
40ms long.  This makes it seem to me like an even better idea to make
this better handled in the code, so users can change the pace of their
game manually.

Also, it seems that the current system requires all parties to agree on
the same amount of latency for the orders they send.  While this ensures
fairness in a few rare cases (e.g. if Alice can send data to Bob with
significantly less latency than Bob can send data to Alice), it's at the
price of significantly higher complexity.

I think I have the beginnings of a better system.  I'll use Alice and
Bob in my explanation - in a client/server model, Alice is acting as the
client and Bob the server.  Also, because the word "latency" is getting
a bit overloaded, I'll refer to the process of setting orders to be
executed some time in the future as "post-dating", and the number of
ticks by which Alice post-dates her messages as her "post-date".

I think it's reasonable to say that the optimal situation is one where
Alice's post-date is as low as possible, but Bob always receives
messages before he needs them.

So that Alice can decide on a good post-date, Bob sends her the
difference between the tick number of the last message he has received
and the tick he was about to execute when the orders were received, plus
one.  If he had to wait any amount of time for the orders, the number is
zero.

Alice stores an array of 256 excess latencies from Bob.  Every 256
ticks, she interrogates the array to see whether she needs to change how
far she post-dates her messages.

* If any tick has an excess latency of zero, she increases her post-date
  by 1.
* Otherwise, she finds the most and least latent messages.  If the
  highest latency is more than double the lowest latency, she decreases
  her post-date by 1.
* Otherwise, she keeps the current post-date

The general principle of this method is that short-term peaks and
troughs in network performance have only a limited impact, no matter how
severe, while long-term trends have a strong impact, no matter how
minor.

The second rule is based on some back-of-an-envelope statistics, and
strikes me as a decent approximation that will be easy to calculate.
The most important property is that, given fairly stable network
conditions, it should allow Alice and Bob to fairly quickly settle on a
constant, lowish, latency.  If anyone has a better idea, I'd be very
interested.

        - Andrew