[Home] [Downloads] [Search] [Help/forum]


Register forum user name Search FAQ

Gammon Forum

[Folder]  Entire forum
-> [Folder]  MUDs
. -> [Folder]  General
. . -> [Subject]  Suggested protocol for server to client "out of band" messages

Suggested protocol for server to client "out of band" messages

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page


Pages: 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21 22  23  

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #300 on Thu 04 Mar 2010 05:46 AM (UTC)
Message
David Haley said:

By the way, it would be fairly easy, I think, to change the networking loop to not throttle everything at 0.25 seconds. I did that a while ago on my game. There's really no need for the server to sit there idle, so as long as you have time until the next 0.25s tick, you might as well look for and process data requests. A quarter of a second could be somewhat annoying especially when so easily avoided.


I've already rejigged the comms processing, because I was finding that if there was a command in the input buffer before the request for the hash, the command would be processed first, and maybe a second command, and finally it got to the hash request a couple of seconds later.

Reworking all that has removed that problem.

You are talking to someone who puts in timing messages for stuff like this, and then spends an entire morning puzzling out why a message takes 1.0 seconds to arrive when he expected it to arrive in 0.25 seconds.

As for the delay, remember this is a once-off, when you first enter an unknown room, or see an object or mob you never saw before. Unless you are charging around like a demented bull, it is probably right that you take a few seconds to stop and read stuff like that.

Another thing is you might *want* the throttling - remember it will slow down a denial-of-service attack, where someone gets his client to request tens of thousands of hashes in quick succession.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #301 on Thu 04 Mar 2010 05:52 AM (UTC)

Amended on Thu 04 Mar 2010 05:53 AM (UTC) by Nick Gammon

Message
David Haley said:

Well, that's not really how hash math works, and I agree that the chances are small, but I guess I don't see the point in adding that risk when it's so easy to reduce the probability by just adding a few characters.


According to:

http://www.answers.com/topic/birthday-problem

Answers said:

The birthday problem in this more generic sense applies to hash functions: the expected number of N-bit hashes that can be generated before getting a collision is not 2^N, but rather only 2^(N/2).


So according to that, a 40-bit hash only covers a 20-bit space (1,048,576 items) so perhaps you are right that by increasing to 48 bits we get to hash 2^24 items without too many problems (16,777,216 items).

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #302 on Thu 04 Mar 2010 05:55 AM (UTC)
Message
I appreciate all this feedback, with some help from my friends, and some experimental work, I think we will come out with a system that demonstrably works, and also has sound theory behind it.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Xtian   (53 posts)  [Biography] bio
Date Reply #303 on Thu 04 Mar 2010 06:46 AM (UTC)
Message
Hashes do have collisions. It's inherent to the concept. In my opinion it is not a good idea to add computational overhead to the server to try to work around this. Either we should find a sound way for the client to resolve collisions or the server should be advised to send over something that doesn't collide, but then is not a hash per se.

Sorry, I just dont like that server-side table that keeps track of all hashes. We should probably add rooms to your WoW items calculation (with the client keeping track of room name, exits, maybe mobs) and on a 1000x1000 grid which avalon.mud.de uses for outdoor areas this data quickly becomes huge.

I think we have these choices:
- ignore collisions. augmenting the number space will help and one could argue that we can more or less do this safely without a player ever encountering a collision
- keep using the hash for quick calculations but concat some additional information to make it unique or at least make a collison less probable: "room:"+hashvalue
- use something else to keep track of consistency server-side

[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #304 on Thu 04 Mar 2010 08:59 AM (UTC)
Message
Xtian said:

Sorry, I just dont like that server-side table that keeps track of all hashes. We should probably add rooms to your WoW items calculation (with the client keeping track of room name, exits, maybe mobs) and on a 1000x1000 grid which avalon.mud.de uses for outdoor areas this data quickly becomes huge.


Well, WoW doesn't have rooms, it has coordinates. Let's be clear about this, hashes are for attributes, not things like unique room names. That is the job of the GUID - which I am implementing as a 64-bit field.

Your 1000x1000 grid of rooms simply becomes a unique identifier, like room.4543.3432. There is no hash and no possibility of collision there.

The hash is used for things like mob descriptions, so hopefully you aren't saying that Avalon has 1,000,000 different mobs. Even if it did, how would a player remember one from the other?

Remember, Git is used by the Linux developers to store their source. Now they are using a longer hash I admit, and we could always lengthen the hash. But when you get to a point where the likelihood of a collision is 1 in 10 billion, you can say that is good enough.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Xtian   (53 posts)  [Biography] bio
Date Reply #305 on Thu 04 Mar 2010 02:45 PM (UTC)
Message
Nick Gammon said:

But when you get to a point where the likelihood of a collision is 1 in 10 billion, you can say that is good enough.


Absolutely. But then we wouldn't need a server-side hash table?


Nick Gammon said:

Your 1000x1000 grid of rooms simply becomes a unique identifier, like room.4543.3432. There is no hash and no possibility of collision there.


But most of these rooms have different descriptions (in your first example you used a hash for a room description). Take a upper limit of between 10 and 100 identical permutations. That reduces the number of hashes. But if you add another attribute beside description, it goes up again. So, a million different hashes are easily generatable.

Ah, talking about scalability on the server side, we should also not forget scalability on the client side. If a user runs through 5 to 10 rooms per second, and most of these have mobs, he can quickly accumulate thousands of entries.
[Go to top] top

Posted by Xtian   (53 posts)  [Biography] bio
Date Reply #306 on Thu 04 Mar 2010 02:48 PM (UTC)
Message
I don't want to sound negavtive, I just want to throw in my computational concerns early. Before they arise on production systems.
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #307 on Thu 04 Mar 2010 06:39 PM (UTC)
Message
Nick Gammon said:
As for the delay, remember this is a once-off, when you first enter an unknown room, or see an object or mob you never saw before. Unless you are charging around like a demented bull, it is probably right that you take a few seconds to stop and read stuff like that.

Does the client start loading stuff as soon as it sees stuff to load, or when the player requests the information e.g. with a miniwindow mouseover?
If the information is requested as soon as possible, then I think you're right that the delay is ok.

Nick Gammon said:
Another thing is you might *want* the throttling - remember it will slow down a denial-of-service attack, where someone gets his client to request tens of thousands of hashes in quick succession.

Personally I don't like the idea of slowing everything down just to guard against a relatively unusual case. I agree that this case needs to be protected against, but you could do that by explicitly limiting the number of requests per player to, say, 20 (??) per second, rather than slowing everything down for everybody all the time.

<will post more soon, meeting time>

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Twisol   USA  (2,257 posts)  [Biography] bio
Date Reply #308 on Thu 04 Mar 2010 06:45 PM (UTC)

Amended on Thu 04 Mar 2010 06:46 PM (UTC) by Twisol

Message
It might be worth noting that WoW has throttling - X amount of requests every Y seconds - and nobody seems to have a problem with it. You just have to be conservative with your API calls when you write plugins, which is arguably a good thing, since it can promote better code design.

EDIT: I just noticed that this is exactly what you suggest in the second half of your response, heh. Oops.

'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
[Go to top] top

Posted by Xtian   (53 posts)  [Biography] bio
Date Reply #309 on Thu 04 Mar 2010 07:53 PM (UTC)
Message
In our experience 7-10 commands per seconds is a good value. After that incoming messages will be buffered and delayed.
But connections in char-mode will need a higher value if you count each incoming character as a command.
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #310 on Thu 04 Mar 2010 08:34 PM (UTC)
Message
Nick Gammon said:
So according to that, a 40-bit hash only covers a 20-bit space (1,048,576 items) so perhaps you are right that by increasing to 48 bits we get to hash 2^24 items without too many problems (16,777,216 items).

I would be tempted to use all characters from the md5 hash. "If it's good enough for git..." I was going to say that compression would probably help here, but maybe it wouldn't be too useful after all because hashes are not likely to be very repetitive. Even so, I'm much more worried about unintentional collisions than I am about sending a few more bytes.

Even with server-side detection of collided hashes, it's still only over one session. A MUD could have many sessions with reboots etc., so I'm not sure that would be enough.

That said, we cannot avoid collisions without removing the hashing entirely. Adding information like the type is dividing the space of probabilities into smaller spaces, but it's not going to fully solve the problem.

A nice feature of Nick's approach is that it is agnostic to the instance/model difference. You simply have attributes that change a lot and attributes that change less often. As soon as you start talking about instances and models, you must make assumptions about the relationship between these two. And as soon as you make these assumptions, you considerably reduce portability to other MUDs.



Here is an idea that can help sanity checking. You can include a (small) checksum of some sort in both the volatile and mostly-static sections. This checksum would need to be constructed from truly immutable attributes, because it would have to be the same for all objects that share the hashed attributes. So, you might have something like the object type and file on disk that it comes from.

Now, when you receive the hashed attributes, you simply compare the checksums. If they're equal, you can be pretty darn sure you got the right thing. If they're unequal, you know immediately that you had a hash collision.

Note the difference with simply cutting up hash spaces into sub-spaces based on type. In this case, we have a more active collision detection method. In order to have a collision, three things must happen at the same time:

1- The two attribute specification strings must hash to the same code.
2- The two things must have the same type.
3- The two things must come from the same file on disk.

Yes, we're not truly fixing the problem, but we're introducing much more active collision detection, and by verifying those two extra things (type and storage medium address) we're pinpointing to a much larger degree where these things are from.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Twisol   USA  (2,257 posts)  [Biography] bio
Date Reply #311 on Fri 05 Mar 2010 12:02 AM (UTC)
Message
Doesn't Git use SHA1, not MD5?

'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #312 on Fri 05 Mar 2010 12:11 AM (UTC)
Message
Oops sorry, yes. SHA1.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #313 on Fri 05 Mar 2010 01:03 AM (UTC)
Message
David Haley said:

Personally I don't like the idea of slowing everything down just to guard against a relatively unusual case. I agree that this case needs to be protected against, but you could do that by explicitly limiting the number of requests per player to, say, 20 (??) per second, rather than slowing everything down for everybody all the time.


Well I don't call processing things after 0.25 seconds "slowing everything down". And I already process requests in batches (10 I think at present), so there is extra throttling there.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #314 on Fri 05 Mar 2010 01:04 AM (UTC)
Message
Xtian said:

In our experience 7-10 commands per seconds is a good value. After that incoming messages will be buffered and delayed.
But connections in char-mode will need a higher value if you count each incoming character as a command.


10 commands per second? Per player? What on earth are they typing?

And I have no intention of supporting "character" mode. Certainly things may dribble in, but they only get processed when a newline arrives.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


614,844 views.

This is page 21, subject is 23 pages long:  [Previous page]  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21 22  23  [Next page]

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page

Go to topic:           Search the forum


[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]


Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at HostDash]