Sign in to follow this  

RUDP design problems...

This topic is 3741 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey guys, A little background first... I've recently written a small RUDP library. The library forms and keeps track of packets that contain both a reliable and an unreliable section. The unreliable portion is used to keep track of things like movement information while the reliable portion is used to track important game events. And now to the problem... I've built the reliable portion of the library to use a simple stop-and-wait wait method. My problem is that with the stop and wait method, the data transfer rate is greatly dependant on the rtt of the packets. Because I'm working with devices that have very limited resources (sometimes less than 1000kb of heap space), it's difficult for me to justify using a bloated sliding-window implementation. On the devices I'm working on, it's very possible to get rtts of 500ms or over. At 500ms rtt, I can only send about 2 packets every second. Unfortunatly, 2 packets a second isn't going to cut it for the RTS that I'm trying to implement. Does anyone of a method (other than sliding-window) to achieve a faster data rate?

Share this post


Link to post
Share on other sites
How large are the packets?

Taking into consideration the statistics of packet loss, you probably could assume that it'll be random, and on per-packet basis. So caching up to 5-10 packets before requesting lost packet again might be reasonable.

What doesn't add up is the transfer rate. If you only have 1Mb of heap, how much bandwidth does such a device have? If cell phone, those can be fast, but still not that fast.

The only other way is to design a lossy state update protocol, and not worry about packet loss. This might not be trivial, but everything is a trade-off. How big are your reliable packets?

Share this post


Link to post
Share on other sites
The packets can be anywhere between 21 bytes to whatever the MTU is on the device. Most of the devices I'm working on are 3G phones, so asfar as bandwith goes they're pretty up there.

I don't have "reliable packets". I have reliable sections on the packets I'm sending out. Reliable data is partitioned and sent out using a scheduler much like the scheduling done on an operating system. Certain things have to be sent out faster than other things (for example an enemy spawning at point X,Y is more critical to send out than a chat message from your friend, the chat message can wait a few seconds before it shows up).

I've done some benchmarking tests and generally packet-loss isn't a very big issue. When you say "caching up 5 to 10 packets", do you mean delaying sends and concatenating packet data together?

As far as having a lossy state update protocol, I don't think that'd fly well either. Simply because there'd be very serious synchronization issues. I can think up some cases where things would work out with a protocol like that, however there are simply too many other cases where it won't work.



Any other ideas?

Share this post


Link to post
Share on other sites
You don't need a sliding window; you can keep a fixed pipeline size. For example, you can decide that you want to send 3 packets without ack; then you can't send another packet until you get ack for the first packet. You can also implement selective ack (typically with a bit mask) of packets, so that you only resend the actually lost packets.

Share this post


Link to post
Share on other sites
So basically you're saying send out x packets and only expect an ack to come back if those packets were all recieved? otherwise resend those x packets? I still have that long delay of waiting for an ack with this method, although I'll be able to pump out more data.

Or are you talking about just implementing a sliding window with a fixed-size? (I'm not too sure if it'd be considered a sliding window if the window size isn't variable)

Both solutions seem acceptable at this point. A fixed-size window seems like it would feed me data at a steady pace, while the first method I mentioned above seems to be more of a burst and wait.

Are there any advantages to using one over the other?

Share this post


Link to post
Share on other sites
Ok, if you can send up to max MTU, then you need to set aside between 5-10kb for 10-20 packets.

I'd suppose this should provide you with more than enough buffer to handle out of order, or lost packets, if you use ack as suggested.

Too many packets, and you'll have hard time keeping up with the processing and updating.

Share this post


Link to post
Share on other sites
Quote:
you're saying send out x packets and only expect an ack to come back if those packets were all recieved?


No, I'm saying send out x packets, and expect one ack per packet that's received. Whenever you get one ack, you send an additional packet. This will let more than one packet be in transit at the same time, which increases throughput on high-latency connections. It's not a sliding window; it's a fixed window.

For an implementation trick that I like:

If your fixed window is less than or equal to 8 packets in size, you can ack or nak the last 8 packets when you ack a packet, by sending an ack for the last received packet id, and a bitmask of which packets before that you have also received. A 0 in some bit in that bitmask could cause the sender to re-send only that packet, in effect implementing selective acknowledgement.

Note that you can't extend the send window beyond 8 packets from the last un-acked packet, though, as there would be no way to ack the re-sent packets in that case.

You can of course use 16 bits for a 16-packet window, too.

Share this post


Link to post
Share on other sites

This topic is 3741 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this