Select vs Polling

Soooooo... I'm guessing everyone else just polls their sockets? :D

What about a library:
RakNet?
enet?

To correctly answer this, we need to know a lot more about your requirements. There are a lot of considerations. You want low latency, but what is the expected/required throughput? And about reducing latency, what kind of game is it? What level of latency is acceptable?

Scalability is a good target, but at what level. Supporting more than 32 players on a single game server? Supporting a couple of hundred or more players across multiple independant servers? Supporting thousands or more players across a large cluster? It makes no sense to aim for the last one if your game is unlikely to progress beyond the first.

Anyway, on to your topic. The threaded solution you appear to be proposing sounds like a nightmare. Adding threading won't necessarily decrease latency. If your main game processing loop is operating at X hz, then you won't be able to react to the clients sooner than that, unless you can react to messages asynchonously WRT the main game loop.

You do get the benefit that sending to the different clients can be done in the background. You can go further, for example if you had a "double buffered" game state, your main thread can be running the game logic on the "back" game state buffer, while the network loop is informing the clients of the state of the "front" or "current" game state buffer. Again, this is context dependant - there is no one right answer.

If you are doing "serious" TCP work (for whatever definition of serious), I believe IOCP (or your platforms equivalent) is the way to go. I'd probably go with select() with the smallest timeout unless I had some hard data to prove I needed something more advanced.

Overengineering too early is an easy way of ensuring you never get the product to the point where it needs to scale. Writing scalable code doesn't always mean you have to be able to support a massive cluster from the start, it just means that you are careful not to put in any assumptions that will make it difficult to change the implementation later.

Finally, if latency is what you are worried about, why are you using TCP at all? Even a single lost packed will cause latency issues orders of magnitude longer than any processing delays you are likely to encounter. Reliable UDP can be managed with a single socket and will most likely experience less latency on the wire.

rip-off was right about almost everything.

The only thing he got a little wrong was the UDP vs. TCP issue. If you need any type of reliability do not use a reliable UDP system. There are many, many reasons why this type of system will not perform as well as TCP. For one nowadays the internet is tuned for TCP traffic, many ISPs will drop UPD traffic in favor of TCP traffic when under high load (they can't drop TCP because that would cause all sorts of pain). Also, think about resends. A reliable UDP system has to resend all the way from the server to the client. TCP does this in hardware from each node along the way so if the failure is at the last hop, that's the only resend.

If you're streaming data like audio or video then UDP is fine. Anything reliable should be TCP.

One other thing, if you're going to do an IOCP based network layer, its best to adopt that from the beginning due to the concurrency issues. Trying to add a highly concurrent network layer at any other time is asking for problems. Concurrency requires a lot of forethought and good design.

Quote:

Original post by Scythen TCP does this in hardware from each node along the way so if the failure is at the last hop, that's the only resend.

I am rather sure that this is not the case (unless I've misunderstood how TCP works from the bottom up).
Not even IP fragmentation (which indeed used to be done "by hardware") is not done on routers any more with the advent of IPv6.

But yes, TCP may negatively impact packet loss on UDP due to traffic shaping on some ISPs. This doesn't mean that UDP is inferior in any way, though. Depending on the needs, UDP can be far superior to TCP. As always, it depends what you need.

Quote:

I guess you would send an interrupt signal to select's thread and add him in?

I'm assuming you're using TCP. With UDP, you only need a single socket, so the problem is easily solved using other mechanisms (like a non-blocking socket).

First, how do you get the connected client? In most systems using select(), you select() on the accepting socket as well as any other socket. This means that the accepted client will be available in the thread calling select(), and the fd_set can be adjusted at that time. Also note that select() changes the input argument, so typically you re-construct the set of fds each time you call select anyway.

For writing, typically what you do is put the data you want to write into some queue specific to the client/socket. You then make select() only include the sockets that have non-empty output queues in the set of write descriptors. Again, this is typically constructed right before you call select() itself.

Select() was invented before threading was available on UNIX, so it's designed to make it possible to run a full application in a single thread (the main thread of the process). If you have timers that need to run every so often, even in the absence of I/O, then you should use the timeout to make sure you can tick your simulation or whatever.

If you use select() and recv()/send() to shuffle data to/from the application, but use another thread to do timers and simulation and message handling, then you have the problem of "how to wake up select() when I enqueue new data for writing on an output socket." There are two solutions to this problem:
1) Use a separate socket (from socketpair(), say) that you write a byte on when you want to wake select() up.
2) Use an acceptably short time-out on select(), which means that you will pick up the new outbound data at worst after the timeout has expired and you have looped back in the select() loop.

I would probably choose 2), with a timeout of perhaps 20 milliseconds or so. Note that, most of the time, the reading thread will get data from other clients, so the time until writable data actually is discovered by select() is generally lower than 20 milliseconds.

However, if your design is heavily threaded, I highly recommend using more thread-savvy approaches to I/O. On Windows, this means I/O completion ports with overlapped I/O, on UNIX this generally means one of the polls (epoll/kpoll). If you use boost::asio, it will choose the best available implementation for each platform.

Thanks for all the answers! I feel that I am learning something here.


> In most systems using select(), you select() on the accepting socket as well as any other socket.

*Reads man page for accept* Hey, that makes a lot of sense.


> You then make select() only include the sockets that have non-empty output queues in the set of write descriptors.

I had been considering using non-blocking sockets, and simply writing the data to them. If I ever send less than the message length, I would add the socket to writefds.


>Select() was invented before threading was available on UNIX, so it's designed to make it possible to run a full application in a single thread (the main thread of the process).

From man select_tut: select() can be used to solve many problems in a portable and efficient way that naive programmers try to solve in a more complicated manner using threads, forking, IPCs, signals, memory sharing, and so on.

They seem to suggest that it's better than using threads?


>If you use select() and recv()/send() to shuffle data to/from the application, but use another thread to do timers and simulation and message handling,

That's what I was thinking: have select run in a separate thread, and fire off events to my main program. If I have even a brief timeout for select in my main thread, it really starts eating into my processing time. Although, I guess I could call select with a timeout of zero. That would eliminate the need for another thread.


> If you need any type of reliability do not use a reliable UDP system.

Agreed.


> TCP does this in hardware from each node along the way so if the failure is at the last hop, that's the only resend.

Really? My understanding was that routers don't know about the transport layer.


> You want low latency, but what is the expected/required throughput?

4-5 KB/sec per client. I'm not considering more than 32 clients at this point.


>And about reducing latency, what kind of game is it? What level of latency is acceptable?

Well, it seems to me that whatever method of sending/receiving data I choose shouldn't be a significant source of latency. I would like to do it with as little latency as possible.

Right now I'm leaning towards calling select() on my main thread with a timeout of zero once per logic update.

Thanks for all the advice!

Quote:

They seem to suggest that it's better than using threads?

It's certainly simpler, because you don't need to worry about locking.

If you want to use threads to fill up all available cores, I suggest you use boost::asio, or another API that wraps around each kernel's native thread-aware I/O API. It really isn't that hard to use.

Here's what I recommend:
- use select(), don't poll
- pass in a timeout to select().
- use non-blocking i/o for all socket calls

I run my server loop at ~100Hz, so I pass in a timeout of 100ms to select. If someone tries to connect, they'll wait at most 0.1s before being picked up in the next select() call.

I wrote a wrapper on top of sockets to make my own use cases easier. You can see that code here: netlib (SourceForge)

Quote:

Original post by Scythen rip-off was right about almost everything. The only thing he got a little wrong was the UDP vs. TCP issue. If you need any type of reliability do not use a reliable UDP system. There are many, many reasons why this type of system will not perform as well as TCP. For one nowadays the internet is tuned for TCP traffic, many ISPs will drop UPD traffic in favor of TCP traffic when under high load (they can't drop TCP because that would cause all sorts of pain). Also, think about resends. A reliable UDP system has to resend all the way from the server to the client. TCP does this in hardware from each node along the way so if the failure is at the last hop, that's the only resend.

I believe you are mistaken. As the others have covered, TCP is between the end nodes, so a resend will be coming from the original host. The alternative would push too much state on intermediate nodes.

ISPs probably will drop UDP traffic under load, but they will almost certainly drop some portion of TCP. This is because TCP will "back off", whereas most UDP software will continue trying to pump packets into the system. If you want to reduce load, you will want to convince TCP to throttle itself. Plus, dropping a small proportion of TCP packets won't cause "all sorts of pain", as TCP should be able to handle this in small amounts.

In any case, if an ISP is under load you are going to struggle to meet your soft real time deadlines anyway.

Quote:

If you're streaming data like audio or video then UDP is fine. Anything reliable should be TCP.

Given that most "real time" games use UDP for networking, this is not a good rule of thumb. If all your data needs to be reliable and in-order, then its hard to beat TCP. But game protocols can be written to have mixed reliable/unreliable UDP protocol, which will (barring excessive packet shaping) perform with less latency than TCP.

TCP is really punishing for any kind of packet loss. Most custom hybrid UDP protocols are designed to deal with low levels of packet loss without noticeable affects on latency, and will do so rather well.

Quote:

One other thing, if you're going to do an IOCP based network layer, its best to adopt that from the beginning due to the concurrency issues. Trying to add a highly concurrent network layer at any other time is asking for problems. Concurrency requires a lot of forethought and good design.

This is true, but is a double edged sword. Unless you are experienced with large scale software design, you are almost certainly going to make a mistake anyway that will limit your scalability. It will be in the last place you look, some forgotten mutex on some piece of data you never thought would be accessed frequently. Bottlenecks are like that, its very difficult to eliminate all of them in advance.

However, you are correct. Doing this sooner is easier than doing it later. My heuristic is: if its a one-man side project, then YAGNI. If you are being paid for this, and the client expects the software to scale, then yes do it now.

Quote:

100 Hz ... 100ms

If you want to run at 100 Hz, you should have a timeout of 10 ms.

Quote:

If someone tries to connect, they'll wait at most 0.1s before being picked up in the next select() call.

Why do they have to wait at all? Put the accepting socket as part of readfds, and select will signal it as readable when someone is trying to connect.