Client-client sync proof

[catid]

-*BAD WORD*-o,

 

Snrrrub messaged me sometime last night that EkTed believes the algorithm in the position packet protocol for extrapolating the upper 16 bits from the lower 16 bits provided in the packet is b0rk. I found quickly that the problem of disproving this was worth solving.

 

Go here for the paper: Paper download

[Mr Ekted]

I said it was incomplete, and only in a trivial way. You could have fixed your code in less time than it took you to write that paper.

 

Let's just illustrate the 3 cases with specific examples. I am the client. I receive a position packet with a 16-bit timestamp that actually resolves to a true 32-bit timestamp. At the point that I receive the packet I need to use the server time (that I think it is) to determine the upper 16-bits. (let's just drop all the one-way and two-way latency stuff as it just clouds the issue)

 

0x0000ffff sent as 0xffff received at 0x00010008 becomes 0x0000ffff (-1)
0x00010001 sent as 0x0001 received at 0x0000ffff becomes 0x00010001 (+1)
0x00000fff sent as 0x0fff received at 0x00001008 becomes 0x00000fff (0)

 

How likely any case is to happen is irrelevant. They all CAN happen, and it's trivial to account for them.

 

Btw, the discussion with Snrrrub about this issue which occurred many months ago, was not an attempt to poke at MERV in any way. I was just passing on something that I thought was incorrect. In the end, we agreed to disagree.

[numpf]

aww how cute, catid recently took a discrete math course. Using QED doesn't make you look smart buddy, it makes you look like a pretentious re-*BAD WORD*-. Your "paper" is perhaps the most obtuse piece of garbage I've ever seen. Anyway, here is the code in merv being argued over (edit: the code in merv is what's in 1.34, meaning 1.34 is wrong. I do not know if Cont does the right thing or sticks to 100% 1.34 compatibility by using this incorrect code)

 

original:

Uint32 loword = getShort(msg, 2);
Uint32 timestamp = h->getHostTime() & 0x7FFFFFFF;

if ((timestamp & 0x0000FFFF) >= loword)
{
   timestamp &= 0xFFFF0000;
}
else
{
   timestamp &= 0xFFFF0000;
   timestamp -= 0x00010000;
}

timestamp |= loword;	// fill in the low word

 

corrected code by numpf:

Uint32 loword = getShort(msg, 2);
Uint32 timestamp = h->getHostTime() & 0x7FFFFFFF;
Uint32 ts_loword = timestamp & 0x0000FFFF;

timestamp &= 0xFFFF0000;

if (ts_loword >= loword)
{
   if (ts_loword - loword > 0x7FFF)
       timestamp += 0x00010000;
}
else
{
   timestamp -= 0x00010000;
}

timestamp |= loword;	// fill in the low word

If you wanted to be really picky you would say 0x7FFF should be higher, but that means you care about appropriately processing packets that are more than five MINUTES late, and that would make you a moron. This change is what catid wrote his "paper" instead of doing.

 

QED catid is a re-*BAD WORD*-.

 

-numpf

[catid]

0x00010001 sent as 0x0001 received at 0x0000ffff becomes 0x00010001 (+1)

0x00000fff sent as 0x0fff received at 0x00001008 becomes 0x00000fff (0)

 

The algorithm does not need to consider these first two, because they break one of the !@#$%^&*umptions made in designing it.

[catid]

0x0000ffff sent as 0xffff received at 0x00010008 becomes 0x0000ffff (-1)

 

LO(0x0000ffff) > LO(0x00010008) (correctly)--> HI(0x0000ffff) = HI(0x00010008) - 1

 

So none of these three cases proves that the algorithm is broken.

[catid]

Quot erat demonstrandum, numpf your mods are unnecessary. Please don't poke fun at MERV. It was an honest attempt to give something back to the community, before I knew how to program properly.

[numpf]

your responses are as obtuse as your "paper," I'm not going to read them. Do a mental trace of what would happen with ekted's case 2, which I'll clarify (I'm not sure you understand it given your replies):

 

Position packet is sent at server_time 0x00010001, meaning 0x0001 is in the packet. It is received by the client at what it calculates to be a server_time of 0x0000FFFF (Receiving a packet "earlier" than when it was sent is possible with latency problems during sync; you may have admitted that in your "paper" but I didn't bother reading that part).

 

Well -*BAD WORD*- it, since I got this far, I might as well finish the trace for you.

timestamp is initialized to 0x0000FFFF

loword in the pkt is 0x0001

 

the first condition passes, since 0xFFFF is (much) greater than 0x0001

 

timestamp ends up being 0x00000001

 

That's wrong. If you do the same trace in my code, timestamp will end up 0x00010001, which is correct.

 

 

I didn't poke fun at merv (but don't bait me), I edited specifically to state that merv just copies 1.34.

 

-numpf

[Yupa]

I've little knowledge of wtf you guys are discussing, but take it easy on someone who's given a lot more to this community than you, numpf.

[Mr Ekted]

I presented 3 valid cases for position packets and their interpretation. Your code only handles 2 of those cases. You are missing 1 case, which means, however small the chance, there are packets you receive which you mis-stamp with an error of over 10 minutes. I'm not talking about design !@#$%^&*umptions or equation rhetoric. I am talking about real world packets.

[Mr Ekted]

0x00010001 sent as 0x0001 received at 0x0000ffff becomes 0x00010001 (+1)

0x00000fff sent as 0x0fff received at 0x00001008 becomes 0x00000fff (0)

 

The algorithm does not need to consider these first two, because they break one of the !@#$%^&*umptions made in designing it.

So you admit you do not handle these perfectly valid cases?

[Mr Ekted]

I've little knowledge of wtf you guys are discussing, but take it easy on someone who's given a lot more to this community than you, numpf.

You are right Akai: numpf never wrote hacks for SS, or attacked servers, or subverted bans, or made threats. Clearly he is way behind.

[Yupa]

clearly

[numpf]

You are right Akai: numpf never wrote hacks for SS, or attacked servers, or subverted bans, or made threats. Clearly he is way behind.

actually, I think I remember making threats when I was mad at someone, maybe zippy :/

 

I've little knowledge of wtf you guys are discussing

then stfu?

 

-numpf

[catid]

Well, I do go out of my way to show that receiving a timestamp greater than a locally generated one is highly unlikely. There are several hurdles, which you can figure out from the inequality I derived last night:

 

[transit time] < 2/5*([local ping] – [remote ping]) - ([local one-way] - [remote one-way]),

 

[local ping] > [remote ping], implying on average only half the players could p!@#$%^&* this hurdle.

 

Note also that these bounds are taken...

 

[transit time] = [receive time] - [send time]

 

// From MERVBot, also part of original SubSpace algos.

if ((transit_time < 0) || (transit_time > 30000))

{

transit_time = 0;

}

else if (transit_time > 4000)

{

transit_time = 15;

}

 

So you see, it wouldn't matter anyway.

 

 

numpf: you are incorrect that the results are wrong

[Mr Ekted]

It's clear you have no idea what you are talking about. You make elaborate proofs to validate your code then you use phrases like "highly unlikely" to justify ignoring a flaw. I'll stick to real math thanks. I was trying to help you and anyone else who uses your core. If you or they do not want feedback, then you don't have to use it. But I presented what I did because it is true.

 

We can end it here in disagreement and let people do as they wish with MERV source, or we can keep having fun arguing. If anyone else is interested in understanding this issue, just ask.

[Mr Ekted]

numpf: you are incorrect that the results are wrong

You are not even able to take his sample data and "play computer" with your own source code?

[numpf]

numpf: you are incorrect that the results are wrong

holy -*BAD WORD*-ing -*BAD WORD*- you are totally -*BAD WORD*-ing braindead. You can disprove me in one of only two ways:

a) prove 0x00010001 == 0x00000001

prove the trace of ek's sample through your code does not yield the results I listed.

 

Judging by your responses in this thread so far, you're firing up a new set of sophistimicated Latin acronyms for your proof of (a) in your new "paper."

 

-numpf

[catid]

Bah, fine, I'll spell it out for you.

 

The SubSpace hiword extrapolation code only produces "incorrect" -intermediary- values, but the final result will be the same.

 

(numpf, i will prove[a])

The one case you found that seems to fail:

 

[local time] < [remote time]

0xffff < 0x10008 will produce transit_time < 0, though it is not the actual transit time.

 

The bounds i mentioned earlier will set transit_time = 0, when the value is used for interpolation by the game physics. Thus, they are two ways of performing the same calculation.

 

 

Yes, the synchronization protocol makes some !@#$%^&*umptions in order to best approximate perfect sync, which is given by that handy inequality. If you set the two sides equal, it's perfectly in sync. Note that there are random variables inherent in the system, so terms such as "highly likely" are exactly what should be used in the places where I used them.

[catid]

The original -will- fail when the 32-bit ticker rolls over, specifically when the two timestamps straddle the discontinuity. I think if you want to improve on the original (well-tested) code, you should fix this problem as well.

[numpf]

alright, I see what you buried in your "paper." 1.34 calculates a possibly flawed timestamp, to calculate the transit time which it clamps (during which the possible flaw is factored out), which it uses to (re)calculate the timestamp for physics. My bad, I can't imagine why I didn't think of that.

 

However, if that's true, you wanna explain to me why transit time is clamped to 15 if it's over 4000? You don't see a problem with that?

 

Whatever the case kids, if you're going to do net sync in your own app, don't use SS as a model.

 

-numpf

[catid]

Feel the love. \=)

 

 

No idea why it sets that extra bound; that may have been a mistake. There are other, similar bounds set on the ping calculation code, though they are not as mysterious:

 

// slow pings get ignored until the next sec.chk

if (round_trip > syncPing + 1)

{

if (ticks - lastSyncRecv <= 12000)

return;

}

 

This is understandable, because we want to encourage that unsync. inequality to fail, which can be done if ping times best represent actual transit time.

 

// ping spikes get ignored

if (round_trip >= syncPing * 2)

{

if (ticks - lastSyncRecv <= 60000)

return;

}

 

This is done for the same reason. We'll only accept a much higher ping after one minute of spikeness (3 attempts). I think that it waits too long, personally.

 

I wrote the paper mainly to investigate the sync system. It may be valuable to someone writing a client.

[catid]

Oh! Well it might have been so that people who are unsync'd horribly for some reason aren't going to interpolate themselves off your screen (or radar). I bet 15 is some kind of "nice" value for the interpolation.

[numpf]

if I were going to write a client I wouldn't find your paper useful due almost entirely to your writing style. Anyone who wants authoritative and comprehensive information on how to sync should start here:

 

http://www.ntp.org/

 

and should never ever look at SS code.

 

are you just ignoring the problem of placing a physical event based on a wildly different origin time?

 

-numpf

[catid]

Well, to write a SubSpace client they'd need to know something about how best to sync using the information available. Some people might want to know how it works, not just that it works.

 

Actually the differences in clocks between server and two remote clients are neatly cancelled out in the calculations. JeffP's logic compacts nicely into an equation between each client's RTT ping and how long it !@#$%^&*umes the ping took to send one-way. I made a mistake when I said you can just set both sides of that unsync inequality equal to show it's perfectly sync'd. Here's the actual deviation from perfect sync:

 

2/5*([local ping] – [remote ping]) - ([local one-way] - [remote one-way]) = 0.

 

This implies that the two timestamps are equal, when the time it takes to transmit is zero. In other words, the difference in timestamps will be zero between the two clients. It's arguable whether or not JeffP made a good choice with these coefficients. In my paper, I say it could use some testing.

[numpf]

http://www.ntp.org/do-*BAD WORD*-entation.html

 

and its links have extensive do-*BAD WORD*-entation on how the protocol is implemented, and all the painful details of clock sync, down to resonator aging. Ignore SS.