Archived

This topic is now archived and is closed to further replies.

blacknull

how to implement a guaranteed mechanism with UDP?

Recommended Posts

it seemed that every commercial online game use UDP with a guaranteed mechanism, but how to implement this mechanism? the client send a packet with a unique id to server, and the server response a packet with the same id? thanks... We Create World.

Share this post


Link to post
Share on other sites
You are basically correct.

To over-simplify a very deep subject, consider the following:

When you recieve a UDP packet, you know the senders address. This identifies which client sent the packet. For each client, you will have a queue of packets received. Part of this queue mechanism is a list of "out of order" packets. Another part would be the list of ordered packets, which the server reads and processes. Each time you recieve a packet, you check a sequence number (you will have to provide this as part of your packet data) to see which list it is placed into. As you recieve packets, you send an ACK packet to the sender telling him that you received the message (return the sequence number so he can dequeue the appropriate message on his side).

example: you recieve some packets with the following sequence numbers in this order: 10, 4, 1, 2, 3, 6, 7, 5

packets 10 and 4 would be placed on the unordered list as they are received. packet 1 and 2 would be placed on the ordered list as they are received. When packet 3 arrives, it is placed on the ordered list, and 4 is moved from unordered to ordered. Then 6 and 7 are placed on the unordered list until 5 arrives, allowing 6 and 7 to be moved to the ordered list. 10 remains on the unordered list until packets 8 and 9 come along... maybe they got lost? As each packet is recieved, send an ACK to the client. After a timeout the client will resend unACKed packets.

This is ONE way to order your packets and "guarantee" that they get delivered. Remember that anytime you send a packet that MUST be received on the other side of the network, you need to keep a copy of the packet in your own output queue so you can resend the packet should you not receive an ACK. This is known as a "store and forward" process.

So to sum it briefly, you have a send and receive queue for packets, and as one end of the network receives a packet, it sends an ACK so the packet can be deleted on the other end of the network. Remember also that not all data MUST be sent reliably. For a similar example of the above see Dan Royers examples in the book Advance 3D Programming with DirectX. If you have any questions let me know.

Tim/Fingh

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
For a deeper explanation of this topic, sign up for a Computer Science degree at your local university and then take the networking class. We spent many weeks on just this topic (but using an abstract protocol).

Like fingh says, it''s a complicated topic...

Share this post


Link to post
Share on other sites
Don''t worry about school there are many wonderful documents on the net about this topic. It''s really not that hard, just remember in your networking module if it''s not EXTREAMLY necessary that the information gets there don''t send a confirmation. IE if you''re moving the position of a player send it Unreliably because in a couple nano seconds you''ll be updating that anyways, but let''s say that person is firing there weapon then by all means send a confirmation.

-----------------------------------------------------------
"People who usualy use the word pedantic usualy are pedantic!"-me

Share this post


Link to post
Share on other sites
Some of the most intelligent and creative people have no University training at all.

For something as trivial as implementing a reliable UDP transfer mechanism you don''t need a CS degree. It is more or less common sense and a little bit of reading.

Dire Wolf
www.digitalfiends.com

Share this post


Link to post
Share on other sites
thanks for ur reply.
i do not wanna get a CS degree at this time anyway. :-) that cost too much time.
i''m writting an online game and implemented the msg system with tcp, but as u know, it''s too slow. so i plan to use UDP, and server each new client with a new thread.

i know the steps of server side:
1. Socket()
2. Bind()
3. RecvFrom()
4. Reply...

my question is: how to implement it just like tcp? we know that tcp got a concept of connection, so every client can exchange msg with server in this connection. but with udp, it seemed that all client must share a same udp receiver if use only one port. how can i implement multi udp receiver with just one port?



We Create World.

Share this post


Link to post
Share on other sites
recvfrom(...) takes a socket descriptor and sockaddr structure among other parameters. When the recvfrom operation completes, the sockaddr you passed into recvfrom will contain the ip-address and port of where the data came from. Since UDP sockets don''t require a connection, you simply create a socket, bind it to a local address/port, and start receiving data.

The client just calls sendto(...) and passes the address of the server/port in the sockaddr parameter.

If you have any more questions or need an example, let me know.

Dire Wolf
www.digitalfiends.com

Share this post


Link to post
Share on other sites
Blacknull, how many players are you supporting? A new thread for each client will really slow you down if you are planning on more than a few connections.

Dire Wolf is correct in that some people don't need university level education to be successful. However, if you intend to implement a "trivial" UDP transfer mechanism, you will likely end up with more headaches than it's worth. Just my opinion of course. A solid UDP-based network module should be anything but trivial. Hard? no. Trivial? I think not. To think otherwise you are kidding yourself.

Do you need a degree to do it? no, of course not. Is a degree beneficial? you bet. Unfortunately Dire Wolf is also right that in most cases the "common sense" methods actually work. The problem is that many times the most obvious way to do something is the biggest and slowest way to do it... That's where a good background in data structures and algorithm analysis comes into play - something you will get inherently with a CS degree.

Don't get me wrong, you CAN implement a trivial mechanism to use UDP. Just like you CAN use MFC to create a game (but no one does) That said, I would willingly help out the original poster with questions, regardless of the route he chooses to follow.

This isn't intended as a flame, I just would not want to dissuade anyone from getting a CS degree, or any degree for that matter.

Tim/Fingh

Edited by - fingh on August 17, 2001 4:31:28 PM

Share this post


Link to post
Share on other sites
I guess it depends on your area of expertise. To me, implementing a skeletal animation/IK system is more complex than implementing reliable UDP.

As I stated, most games utilize reliable UDP for certain messages only. Typically packets that tell clients to draw an effect, play a sound, or display a message (maybe from another person) tend to be marked as reliable. Movement packets don''t need to be reliable due to client-side prediction.

I agree with fingh that my remark about implementing UDP being trivial was a bit hasty. I don''t want to mislead anyone. Still, I''ve been doing network programming long enough that it seems relatively trivial to me. Also, please remember that I''m only speaking about non-sequential reliable UDP packets. When you begin to implement sequentially sequenced reliable UDP the complexity increases quite significantly.

Best regards,


Dire Wolf
www.digitalfiends.com

Share this post


Link to post
Share on other sites
as a matter of fact, my game got a record that serving 100 players at the same time. that means the server got 104 thread. 3 for mfc framework, 1 for listen socket, and 100 for client service. each service thread got a tcp socket connection. now i wanna change the tcp connection to reliable udp, and implement msg receiving and sending in each service thread.

Dire.Wolf, recvfrom(...) can get ip address info, so u maybe think this info can identify the player who sending this packet. but how about lan player? i mean the player connecting my server throught a gateway, they got only one ip....

and, the most important thing is: recvfrom(...) can only be called by one thread if we got only one port to use. we can''t call recvfrom(...) in each service thread, right? i think the implement steps just as follow.
1. call recvfrom(...) in a specified thread.
2. get the msg sender from ip address or id info in packet.
3. dispatch the msg to the thread which serve this sender.
4. the service thread process this msg and response.

what i worry about is the thread which call recvfrom(...), because all msg have to pass this gate, that means it will slow down my server for certain.

how can i avoid this situation?

We Create World.

Share this post


Link to post
Share on other sites
Blacknull,

recvfrom() can be called from any and all threads. It doesn''t matter that you have only one port. If you are worried about thread synchronization just use a critical section. Critical sections are fast.

I rarely use recvfrom in my programs. Typically I use WSARecvFrom (Win32 specific function) with overlapped I/O.

To avoid your gateway problem (are you thinking NAT?) the easiest way is to just include a 4-byte IP address in the message. No big deal there.

Maybe I''m missing your point.

Regards,



Dire Wolf
www.digitalfiends.com

Share this post


Link to post
Share on other sites
Dire Wolf,

Now I understand completely your point of view. It is sometimes hard to keep track of things in a forum that ranges in skill levels from complete novices to professional game developers. I am a network programmer by trade so I''m somewhat comfortable with material on this forum, but I am sure my questions in the graphics forums are quite "newbie". Anyways, I hope all of this information has helped you blacknull...

Tim/Fingh

Share this post


Link to post
Share on other sites
First of all, sending the IP address along in the packet does seem a bit dumb
With NAT, every connection gets a unique port, so you can tell different connections from the IP/port pair - that's how the TCP layer tells which packet belongs to which connection, so it can't be wrong.

Why do you want to use so many threads? It just unnecessarily increases the amount of system resources you use up (unless you got 70-100+ processors that is...
Just have any thread read a message from any client. You can use the IP address delivered by recvfrom(), and if you've got a sorted lookup array for all clients you can just do a binary search to get the client structures. You'll have to do that anyway (yes, there are ways of listening to packets from a specific IP address w/ UDP, but I don't think their overhead is worth it).

If you want to use threading consider that there are three different threading models (which I can think of right now, there are probably more):
- World partitioning. This really only applies to MMO games. The idea here is that you split your world into say 4 parts and have 4 threads where each thread handles one of the partitions. This is probably the simplest threading model and potentially the most efficient one too (because inter-thread issues are reduced to a minimum, thus reducing the pressure on caches and the memory bus)
- Worker threads. You have one thread which recvfrom()s from your UDP socket. When it gets a packet, it puts it into a queue, the request is dequeued by a worker thread. I really don't think this is a good approach, because you're doubling efforts. WinSock (or whatever the socket-implementation is) already implements a message queue, and you're just creating a second one, which means you've got more overhead.
- Free multithreading. Every thread recv()s from the same socket (or maybe from an I/O completion port or similar). When it receives a packet it rushes off to serve the request completely; when it's done, it recv()s again. Whether you send() update packets to players in those very same threads is up to you (I don't think it's a good idea as it could potentially open the door for floods). This model potentially includes one framework thread which occupies itself with time-based and non-player related events.

Generally I don't think that thread-bloating a program is a good idea, especially it's not a good idea for games. You just increase overhead for interthreadlocking, context switches and so on. The max. should really be the number of processors, and maybe 1,5-2x the number of processors if the threads might block or do costly I/O.

cu,
Prefect

One line of sourcecode says more than a thousand words.

Edited by - Prefect on August 20, 2001 1:36:25 PM

Share this post


Link to post
Share on other sites