Month: March 2008

It uses the layered service provider system I wrote about. For any UDP based application (actually with one line of code change it work with TCP too) it will add the desired attributes to the connection.

One big snag is how to implement an incoming bandwidth throttle. There are 3 ways data can come in, nonblocking, blocking, or with IO completion ports. Nonblocking is the easiest, I just stick the data into a buffer and return it when the user later calls recv or recvfrom again. Blocking is harder. I would have to put an infinite loop in the recvfrom call and not return until the required latency has elapsed. However, you can break out of the Windows version of recvfrom with a signaled event, and I have no idea how I’d hook into that event. IO completion ports is similar to nonblocking, but the buffer has to be added to from a worker thread elsewhere. If I can’t figure this out I’d have to drop the incoming bandwidth throttle. This would have been easier if I had implemented it at the NDIS level, although it would have been harder in other ways.

Another problem is the layered transport service provided by windows is DLL and registry based. So if you were to kill the program with end process, the DLL would not be uninstalled automatically when the process shuts down. If you were to then delete the program without uninstalling it that DLL would be stuck in your system, loading up the QoS emulator when you don’t want it. I’m not sure if the DLL can unregister itself in its own startup call. If I can, I will check for the program installation in startup, and have the DLL unregister itself if it looks like the program was uninstalled.

I’m not sure all this will work on Vista either. There was some crap in the Windows SDK documentation about security and various extra things you have to do in the installer, the registry, and the program itself. I only scanned over it in passing while looking for info on the Winsock debug/trace DLL system. I hope there’s code there I can just copy/paste.

This program has been very complicated and difficult to write, partly because I’ve never done anything like it before. It requires knowledge of threads, IO completion ports, sockets and socket properties, the registry, installation settings and permissions, interprocess communication, hooking in and debugging DLLs called by the system, and complicated associations between LSPs, the high level user-code, other LSPs, and the low level transport service provider. That article by Microsoft states “You will probably find that implementing an LSP is no longer a daunting and time-consuming task if you simply extend the layered sample” but if they consider that to be easy I’d hate to see what they consider hard.

Thanks to Jason King for help designing the GUI!

I was reading http://dewitters.koonsolo.com/gameloop.html where the author, Koen Witters, proposes a fixed-update game loop with a variable update render loop using interpolation to find out between-frame render positions. It’s a well written article and his solution is good for single player games.


const int TICKS_PER_SECOND = 25;
const int SKIP_TICKS = 1000 / TICKS_PER_SECOND;
const int MAX_FRAMESKIP = 5;

loops = 0;
while( GetTickCount() > next_game_tick && loops < MAX_FRAMESKIP) { update_game(); next_game_tick += SKIP_TICKS; loops++; } interpolation = float( GetTickCount() + SKIP_TICKS - next_game_tick ) / float( SKIP_TICKS ); display_game( interpolation ); }

However, this has problems with online games. In networking, you often need to extrapolate given a prior position and some amount of time to the current time. For example, I may get a position packet 208 milliseconds ago. If I were to update every 40 milliseconds (25 ticks per second), I would have 8 milliseconds leftover. This moves the problem of left-over ticks to your game objects.

You can either calculate partial ticks, in which case your game objects are slightly out of synch with the fixed-step simulation, or you can ignore them, and just use the least number of ticks you can fit in. If you get frequent updates this is OK, but for objects that are not updated frequently things can get out of place, and a lot faster than 2.4336088699783431e-13.

My solution is variable length game updates with variable length frame updates, with a frequency limit on game updates.

Variable length updates with variable length frame updates:


// Do not skip more than one second (due to debugging)
const int MIN_UPDATE_TIME=1000;
// Do not update more than every 10 milliseconds
const int MAX_UPDATE_TIME=10;
// How much time to render forward
float renderExtrapolationTime;

renderInterpolationTime = GetTimeMS() - lastGameUpdate;
display_game( renderExtrapolationTime );
elapsedGameTime=GetTimeMS()-lastGameUpdate;
}


One problem I had a couple of years ago was how to write an accurate internet simulator feature for RakNet. What I have in there now is what you find in your average games – a user can intentionally add latency to outgoing messages and can randomly drop packets to simulate packetloss. But this is not accurate and not very full-featured.

Here’s a better design:

Maximum outgoing bandwidth – Represents your network card’s ability to send data through the wire.
Maximum incoming bandwidth – As above, but for incoming data
One-way trip time – The minimum time a datagram would take to get to a remote system; the base speed of the network
Per-message additional trip time – On the internet, many people are sending messages, so there will be some delay between each of your messages as other messages goes out. So this number represents the rest of the internet using the router’s bandwidth too. The effect to the sender is that as you flood the connection, your ping goes up. This is what actually happens and is how flow control is accomplished in modern reliable packet implementations (the old way used sliding windows which controlled throughput based on how fast the other system acked your messages).
Maximum router queue – This represents how much average memory each router has. Go beyond this and you start getting packetloss.
Randomly dropped packets – Due to noise on the wire
Out of order packets – As above

The problem with hardcoding this in the user level network layer is that you have to implement a control interface (changable at runtime), you have to do it on both systems, and it can be complex to implement in every circumstance. So I’m writing a layered transport service provider. This is sort of like RakNet’s plugin system, but for Winsock, and it gives you the ability to override various network events with a procedure table. This is stored as a system DLL, and installed and uninstalled by an EXE. I will have this EXE double as a control panel and will use interprocess communication to have the EXE control the invoked DLL.

By the way, to say this is complicated is understating the issue. It’s about 1000 lines of code for the installer, 10,000 lines of code to properly create a plugin that does nothing but pass the data through. You have to understand overlapped events, IO completion ports, support for versions of winsock, an entirely different set of code to install the driver on Vista (plus permission sets), you have to use .def files for export, and more. The article that I’m going by is 8,500 words long (about 20 pages) and takes hours of study to understand well enough to do anything.

After going through all this I think Shunra is justified in charging $500 for their simulator. The solution is hard to write. However, Shunra doesn’t support loopback last I contacted them. My implementation does, so I think I can sell mine to gave developers and others that want a loopback solution. Plus I can put a nice GUI on it, so you can control what is going on at runtime.

I was updating the manual for RakNet and was reminded of how many data structures I’ve written for it.

From the manual:

DS_BinarySearchTree.h – Binary search tree, and an AVL balanced binary search tree.
DS_BPlusTree.h – BPlus tree for fast lookup, delete, and insert.
DS_BytePool.h – Returns data blocks at certain size thresholds to reduce memory fragmentation.
DS_ByteQueue.h – A queue specialized for reading and writing bytes.
DS_Heap.h – Heap data structure, includes both minheap and maxheap.
DS_HuffmanEncodingTree.h – Huffman encoding tree, used to find the minimal bitwise representation given a frequency table.
DS_HuffmanEncodingTreeFactory.h – Creates instances of the Huffman encoding tree.
DS_HuffmanEncodingTreeNode.h – Node in the Huffman encoding tree.
DS_LinkedList.h – Standard linked list.
DS_List.h – Dynamic array (sometimes improperly called a vector). Also doubles as a stack.
DS_Map.h – (Associative array) Ordered list with an per-element sort key.
DS_MemoryPool.h – Allocate and free reused instances of a fixed size structure, used to reduce memory fragmentation.
DS_OrderedChannelHeap.h – Maxheap which returns a node based on the relative weight of the node’s associated channel. Used for task scheduling with priorities.
DS_OrderedList.h – List ordered by an arbitrary key via quicksort.
DS_Queue.h – Standard queue implemented with an array
DS_QueueLinkedList.h – Standard queue implemented with a linked list
DS_RangeList.h – Stores a list of numerical values, and when the values are sequential, represents them as a range rather than individual elements. Useful when storing many values that are usually sequential.
DS_Table.h – Table with columns and rows, and operations on that table.
DS_Tree.h – Noncyclic graph
DS_WeightedGraph.h – Graph with weighted edges, used for routing via Dijkstra’s algorithm

Data structures is one of the few classes in college that has a significant real-world bearing. It’s one of the cornerstones of good design and optimization.

A few times I’ve been asked why I don’t just use STL.

1. STL can cause linker errors
2. STL uses exceptions.
3. STL doesn’t have every feature I need.
4. I don’t know how well STL is optimized, but I know exactly how well my code is optimized.
5. In college I was confused for months before I figured out when people said ‘vector’ they meant ‘dynamic array.’ It became a pet-peeve of mine.
6. In college I started writing my own data structures before I knew STL existed. None of my classes ever covered it And once I started I had momentum to keep going.
5. It’s something I find interesting and enjoy writing.

Aside from STL, of the game companies I’ve worked at, I’ve never seen any of them with as sophisticated a set of data structures as what I have in RakNet. When you need to process and track 30,000 messages a second you need heavy duty data structures like my memory-pool optimized B+ tree. Being able to support 30,000 messages vs. your standard game’s 20-30 messages a second is part of the polish you get with a dedicated mature library.