===================================================
What the author learned (about UDP/IP and pthreads)
===================================================
August 1999
Chris Jang
cjang@ix.netcom.com


Note: I hope that some of this is useful to any programmer reading this.

      I've seen other game projects that emphasize client side graphics
      with networking added later. For me, LAN networking with a
      multi-threaded server was the easiest part of Kombatant. It took
      the least time and once working was stable on Linux and HP-UX.

      If you are doing UDP/IP networking with a multi-threaded server
      (the typical way to do things now) for the first time and haven't
      worked with UDP/IP and pthreads before, then maybe these questions
      and answers can save some time. I don't think this kind of stuff
      is commonly published. It isn't rocket science but takes a little
      experimentation to discover.


1. UDP recvfrom() errors may not drop datagrams!

Over a LAN, over 99% of packets can be expected to reach the destination. So
essentially UDP/IP is "reliable" (have not tried anything else besides IP).
But even if UDP/IP were truly reliable, there are still temporal paradoxes that
occur which are variants of the general's paradox.

Essentially, if the client sends a message to server, how long should the
client wait for the reply? After some period of time, the client must presume
the message to have been lost. But the message may not have been and then the
server reply will arrive later. This can lead to the following:

	a. server becomes very busy for a while
	b. client sendto()s request to server
	c. client request goes into server's receive socket buffer
	d. but server is still busy
	e. client recvfrom() on socket fails as there is nothing there yet
	f. server now services client request and sendto()s reply
	g. reply to client now goes in client socket buffer
	h. client resends last request to server in belief last time failed
	   due to timeout (but it didn't fail, just was slow in coming)
	i. server now replies to same request again, assumes client dropped
	   last one
	j. so now there are two identical server replies in client socket
	   buffer!

This can lead to lag if the client isn't aware of this effect. Robust
networking really requires a lot of strategies to minimize the above effect.


2. Receive the whole datagram at once if possible

Although UDP datagrams are read out of a socket buffer, the recvfrom() call
reads them out atomically. So you have to receive datagrams into a buffer at
least as large as the largest datagram message that will ever be received.
I've always kept datagram messages much smaller than 1500 bytes (typical MTU
for Ethernet?) to avoid any kind of packet fragmentation issues. If you need
to send messages larger than this, they probably should be broken up into
several smaller datagrams and reassembled end to end (and so avoiding
fragmentation at the UDP layer and other possible problems).


3. With pthreads, busy loops = 95% CPU, spin locks = 99% CPU (HP-UX experience)

If you find your pthreaded server is using 95% CPU time, then it's probably in
some kind of busy loop, repeatedly failing on some kind of I/O operation. But
it is doing some work on the I/O operation and giving up context to a system
call. That's what keeps the server from consuming 99% CPU time.

If your pthreaded server is using 99% CPU time, then it's probably in a spin
lock without an I/O operation. A common example of this is one thread reading
out of a message queue (not a System 5 message queue but a homebrewed linked
list with a mutex around it) that is empty. Locking the mutex and checking the
queue consumes almost no CPU and results in a spin lock. To get around this,
you'll have to use pthread_cond_wait and pthread_cond_signal. So the reading
thread waits on a conditional variable when there is nothing to read and do.
Whatever thread posts something to the message queue signals on the conditional
variable, so waking up the waiting thread. This CPU utilization should be less
than 1% at idle.


4. Use nanosleep() with pthreads

The calls sleep() and usleep() may conflict with pthreads in how they use
signals so should not be used in a multi-threaded server. (they cause problems
on HP-UX but not on Linux) The call nanosleep() is guaranteed not to conflict
with pthreads so this is the preferred way to implement delays.


5. Thread starvation results in socket errors (Linux experience)

A multi-threaded server will have at least two threads, one to handle socket
communications and one to update the game world. The thread reading on a UDP
socket can simply block. But the thread updating the game world can just run
in an endless loop updating the game world. This can cause problems for the
socket thread.

The game world update loop should have a nanosleep() call waiting for an
insignificant amount of time so as not to starve out the socket thread and
cause socket recvfrom() errors. The time may be some token duration like one
millisecond or less (processes are scheduled with 10 millisecond resolution?).
The nanosleep() call serves to give up context in some way that avoids the
socket recvfrom() errors on the other thread.