Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Reliable UDP and packet order


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 Pfaeff   Members   -  Reputation: 100

Like
0Likes
Like

Posted 08 May 2012 - 10:22 AM

Hi,

I have a working basic network communication via udp for my hack&slay RPG game. I implemented reliability using acks.
Messages will be resend, if the ack didn't arrive within 2*RTT. Everything seems to work pretty nicely, but there is still one problem to be solved: the case when reliable messages are received out-of-order, which will lead to inconsitencies among the players.

As far as I know there are two ways to solve this problem:
  • let all players live x ms in the past and hope that all necessary packets arrive during that time, if not, resynchronize the player, or kick him from the server
  • do a rollback and send anti-messages for any reliable messages that where sent (those might in return trigger more anti-messages and so on)

I don't like the second solution, because it is rather complicated to implement and anti-message introduce much extra traffic. So I would opt for the first method. Or are there other more suited techniques that I don't know about?

Greetings,
Pfaeff

Sponsor:

#2 Antheus   Members   -  Reputation: 2397

Like
1Likes
Like

Posted 08 May 2012 - 10:58 AM

if the ack didn't arrive within 2*RTT.


I'd start with 20*RTT. And if client cannot continue without receiving past ack, UDP is the wrong choice anyway, just use TCP. UDP is good choice if can ignore some lost packets without resending them.

Even on best networks, hiccups happen. And 20x over low-latency connection of 100ms is only 2 seconds. Spikes up to 5 seconds happen regularly. Then there's drift and spikes, maybe shared wifi and someone downloads something big-ish and stalls the others or just generally increases latency.

IMHO, unless you don't completely tolerate up to 1000ms latency, let alone disconnect those that exceed this, the protocol will be next to useless in real world.

it's true that dedicated players want to have <50ms ping, but for majority having reliable connection will be worth much more. Look at Minecraft, people are ecstatic over how nice it looks and how much fun it is, only to learn that for them it runs at 2-3 fps and takes 5 minutes to load.

because it is rather complicated to implement


Yes it is. And that's even without real world testing, which will throw even the best designs off.


For hack&slash, evented simulation over TCP on global scale works fine. 3 examples: Starcraft2, Diablo3, Realm of mad god.

Edited by Antheus, 08 May 2012 - 10:59 AM.


#3 Pfaeff   Members   -  Reputation: 100

Like
0Likes
Like

Posted 08 May 2012 - 12:26 PM

Thanks a lot, what you're saying about resending packets sounds reasonable.

I want to use UDP, because I plan on implementing some gameplay elements that require a bit more responsiveness. This project is also for me to learn some network programming, because I've never done such before. Even if UDP is overkill for my application (which might or might not be the case, but it gives me some tolerance), I will be able to apply those techniques to future projects that require a fast and responsive network system.

The problem I have is the following:
  • Let's say a player with 10 life drinks a potion at t0 and gains 10 additional life
  • That player gets hit for -10 life at t1
  • The first packet gets lost for one client and is resent some time later. For him the player will get hit and die, while for all other players he will be alive.

I know that this can be prevented if the server just sends the absolut life values for the players. In this case he will die either way, but a bit later for one of the players.
The thing is that I am not sure if that will always work. There might be other mechanics that I didn't think of for which no such simple solution exists.

Edited by Pfaeff, 08 May 2012 - 12:28 PM.


#4 ApochPiQ   Moderators   -  Reputation: 16414

Like
0Likes
Like

Posted 08 May 2012 - 01:38 PM

Sounds like you need guaranteed order of delivery, in which case UDP is the wrong tool for the job unless you want to basically reinvent TCP on top of it (which IMHO is usually a waste of time especially if you're new to networking).

I really suggest you look at TCP first. It's much easier to get a good model going that isn't open to all kinds of bugs and exploits due to dropped packets and such. And frankly it works fine and is plenty fast - many "Action Oriented" games use TCP for their network model with no real problems.

Once you're comfortable with basic networking you can look into reliable UDP models, but I don't recommend starting there.


This forum's FAQ has a lot of great material on this kind of thing, by the way; if you haven't browsed through there yet you really ought to.

#5 Antheus   Members   -  Reputation: 2397

Like
0Likes
Like

Posted 09 May 2012 - 08:50 AM

The problem I have is the following:

  • Let's say a player with 10 life drinks a potion at t0 and gains 10 additional life
  • That player gets hit for -10 life at t1
  • The first packet gets lost for one client and is resent some time later. For him the player will get hit and die, while for all other players he will be alive.

Make a drinking animation that lasts 1 second, where health is only restored after that one second. It will cover the latency and hint player that they are vulnerable.

The first packet gets lost for one client and is resent some time later.


"The packet ain't lost, it's restin'."


Each action, message, command, etc... has a timestamp of sorts.

Some actions, especially ones which are frequent, can be sent as "unreliable". For movement, they would arrive with following timestamps: 1,2,4,3,7,8,9,10. 3 would be discarded, since we already received 4. Packets 5 and 6 are pinnin' for the fjords, but since we received 7 and later, we don't care.

Now here's a catch - what about message 11? Was it sent? Was it lost? What about 12, 13, ....?

And what if now send an action message, such as picking up something - am I in range or not?

#6 Pfaeff   Members   -  Reputation: 100

Like
0Likes
Like

Posted 09 May 2012 - 02:42 PM

Sounds like you need guaranteed order of delivery, in which case UDP is the wrong tool for the job unless you want to basically reinvent TCP on top of it (which IMHO is usually a waste of time especially if you're new to networking).

I really suggest you look at TCP first. It's much easier to get a good model going that isn't open to all kinds of bugs and exploits due to dropped packets and such. And frankly it works fine and is plenty fast - many "Action Oriented" games use TCP for their network model with no real problems.

Once you're comfortable with basic networking you can look into reliable UDP models, but I don't recommend starting there.


This forum's FAQ has a lot of great material on this kind of thing, by the way; if you haven't browsed through there yet you really ought to.

I already did that, but when I was finished with the system based on TCP, I decided to try out UDP.

The problem I have is the following:

  • Let's say a player with 10 life drinks a potion at t0 and gains 10 additional life
  • That player gets hit for -10 life at t1
  • The first packet gets lost for one client and is resent some time later. For him the player will get hit and die, while for all other players he will be alive.

Make a drinking animation that lasts 1 second, where health is only restored after that one second. It will cover the latency and hint player that they are vulnerable.

The first packet gets lost for one client and is resent some time later.


"The packet ain't lost, it's restin'."


Each action, message, command, etc... has a timestamp of sorts.

Some actions, especially ones which are frequent, can be sent as "unreliable". For movement, they would arrive with following timestamps: 1,2,4,3,7,8,9,10. 3 would be discarded, since we already received 4. Packets 5 and 6 are pinnin' for the fjords, but since we received 7 and later, we don't care.

Now here's a catch - what about message 11? Was it sent? Was it lost? What about 12, 13, ....?

And what if now send an action message, such as picking up something - am I in range or not?

My current implementation supports unreliable messages and I plan on using them as you suggested. If the received message has an older "timestamp" as the most recently received message, the new one is simply discarded.

I think the problem of packet ordering is fundamental for every game and that is why I asked for methods to deal with it. Of course there are games in which such problems are not so much apparent and there are games where those problems can be circumvented using clever design of gameplay as described in my first post or in the example of Antheus. But there might be cases in which that won't work (none that I can think of atm though). If these cases are rare and isolated, a simple stop-and-wait strategy could work. Other cases might require some resynchronisation with the server, but I am not sure if more sophisticated methods may be required for my needs.

#7 clb   Members   -  Reputation: 1792

Like
1Likes
Like

Posted 09 May 2012 - 02:57 PM

To implement ordering guarantees to an UDP datagram stream, store a running "packet number" counter in each sent datagram. When receiving datagrams, you can examine the packet numbers to detect out of order receives. When you receive a datagram out of order, you generally have two choices:
- Queue up the datagram and wait for the earlier datagrams before processing the first datagram you received out of order. (This is what TCP does, and it causes head-of-line blocking and incurs additional latency)
- Immediately process the datagram and choose to discard the older datagrams in case they will be received in the future. This is called "latest data guarantee" messaging, because this method does not guarantee that all datagrams will be processed by the receiver, but that at least the most recent/newest version of the data will be seen by the receiver.

Another problem you will need to solve with UDP is accidental datagram duplication caused by the network. UDP does not guarantee that if you send one datagram, that the other end would receive at most one datagram, but instead, the datagram may get duplicated along the way, e.g. due to resends. When you have these unique packet number counters attached to datagrams, you can easily detect duplicate datagrams and discard them.

I have implemented an UDP-based game networking library, perhaps that is of help for reference: kNet over UDP documentation, source code that implements kNet over UDP.
Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS