原文

原文出处

Introduction

Hi, I’m Glenn Fiedler and welcome to Networking for Game Programmers.

In the previous article, we added our own concept of virtual connection on top of UDP. In this article we’re going to add reliability, ordering and congestion avoidance to our virtual UDP connection.

The Problem with TCP

Those of you familiar with TCP know that it already has its own concept of connection, reliability-ordering and congestion avoidance, so why are we rewriting our own mini version of TCP on top of UDP?

The issue is that multiplayer action games rely on a steady stream of packets sent at rates of 10 to 30 packets per second, and for the most part, the data contained is these packets is so time sensitive that only the most recent data is useful. This includes data such as player inputs, the position, orientation and velocity of each player character, and the state of physics objects in the world.

The problem with TCP is that it abstracts data delivery as a reliable ordered stream. Because of this, if a packet is lost, TCP has to stop and wait for that packet to be resent. This interrupts the steady stream of packets because more recent packets must wait in a queue until the resent packet arrives, so packets are received in the same order they were sent.

What we need is a different type of reliability. Instead of having all data treated as a reliable ordered stream, we want to send packets at a steady rate and get notified when packets are received by the other computer. This allows time sensitive data to get through without waiting for resent packets, while letting us make our own decision about how to handle packet loss at the application level.

It is not possible to implement a reliability system with these properties using TCP, so we have no choice but to roll our own reliability on top of UDP.

Sequence Numbers

The goal of our reliability system is simple: we want to know which packets arrive at the other side of the connection.

First we need a way to identify packets.

What if we had added the concept of a “packet id”? Let’s make it an integer value. We could start this at zero then with each packet we send, increase the number by one. The first packet we send would be packet 0, and the 100th packet sent is packet 99.

This is actually quite a common technique. It’s even used in TCP! These packet ids are called sequence numbers. While we’re not going to implement reliability exactly as TCP does, it makes sense to use the same terminology, so we’ll call them sequence numbers from now on.

Since UDP does not guarantee the order of packets, the 100th packet received is not necessarily the 100th packet sent. It follows that we need to insert the sequence number somewhere in the packet, so that the computer at the other side of the connection knows which packet it is.

We already have a simple packet header for the virtual connection from the previous article, so we’ll just add the sequence number in the header like this:

   [uint protocol id]
   [uint sequence]
   (packet data…)

Now when the other computer receives a packet it knows its sequence number according to the computer that sent it.

Acks

Now that we can identify packets using sequence numbers, the next step is to let the other side of the connection know which packets we receive.

Logically this is quite simple, we just need to take note of the sequence number of each packet we receive, and send those sequence numbers back to the computer that sent them.

Because we are sending packets continuously between both machines, we can just add the ack to the packet header, just like we did with the sequence number:

    [uint protocol id]
    [uint sequence]
    [uint ack]
    (packet data…)

Our general approach is as follows:

• Each time we send a packet we increase the local sequence number




• When we receieve a packet, we check the sequence number of the packet against the sequence number of the most recently received packet, called the remote sequence number. If the packet is more recent, we update the remote sequence to be equal to the sequence number of the packet.




• When we compose packet headers, the local sequence becomes the sequence number of the packet, and the remote sequence becomes the ack.

This simple ack system works provided that one packet comes in for each packet we send out.

But what if packets clump up such that two packets arrive before we send a packet? We only have space for one ack per-packet, so what do we do?

Now consider the case where one side of the connection is sending packets at a faster rate. If the client sends 30 packets per-second, and the server only sends 10 packets per-second, we need at least 3 acks included in each packet sent from the server.

Let’s make it even more complex! What if the packet containing the ack is lost? The computer that sent the packet would think the packet got lost but it was actually received!

It seems like we need to make our reliability system… more reliable!

Reliable Acks

Here is where we diverge significantly from TCP.

What TCP does is maintain a sliding window where the ack sent is the sequence number of the next packet it expects to receive, in order. If TCP does not receive an ack for a given packet, it stops and resends a packet with that sequence number again. This is exactly the behavior we want to avoid!

In our reliability system, we never resend a packet with a given sequence number. We sequence n exactly once, then we send n+1, n+2 and so on. We never stop and resend packet n if it was lost, we leave it up to the application to compose a new packet containing the data that was lost, if necessary, and this packet gets sent with a new sequence number.

Because we’re doing things differently to TCP, its now possible to have holes in the set of packets we ack, so it is no longer sufficient to just state the sequence number of the most recent packet we have received.

We need to include multiple acks per-packet.

How many acks do we need?

As mentioned previously we have the case where one side of the connection sends packets faster than the other. Let’s assume that the worst case is one side sending no less than 10 packets per-second, while the other sends no more than 30. In this case, the average number of acks we’ll need per-packet is 3, but if packets clump up a bit, we would need more. Let’s say 6-10 worst case.

What about acks that don’t get through because the packet containing the ack is lost?

To solve this, we’re going to use a classic networking strategy of using redundancy to defeat packet loss!

Let’s include 33 acks per-packet, and this isn’t just going to be up to 33, but always 33. So for any given ack we redundantly send it up to 32 additional times, just in case one packet with the ack doesn’t get through!

But how can we possibly fit 33 acks in a packet? At 4 bytes per-ack thats 132 bytes!

The trick is to represent the 32 previous acks before “ack” using a bitfield:

    [uint protocol id]
    [uint sequence]
    [uint ack]
    [uint ack bitfield]
    <em>(packet data…)</em>

We define “ack bitfield” such that each bit corresponds to acks of the 32 sequence numbers before “ack”. So let’s say “ack” is 100. If the first bit of “ack bitfield” is set, then the packet also includes an ack for packet 99. If the second bit is set, then packet 98 is acked. This goes all the way down to the 32nd bit for packet 68.

Our adjusted algorithm looks like this:

• Each time we send a packet we increase the local sequence number




• When we receive a packet, we check the sequence number of the packet against the remote sequence number. If the packet sequence is more recent, we update the remote sequence number.




• When we compose packet headers, the local sequence becomes the sequence number of the packet, and the remote sequence becomes the ack. The ack bitfield is calculated by looking into a queue of up to 33 packets, containing sequence numbers in the range [remote sequence - 32, remote sequence]. We set bit n (in [1,32]) in ack bits to 1 if the sequence number remote sequence - n is in the received queue.




• Additionally, when a packet is received, ack bitfield is scanned and if bit n is set, then we acknowledge sequence number packet sequence - n, if it has not been acked already.

With this improved algorithm, you would have to lose 100% of packets for more than a second to stop an ack getting through. And of course, it easily handles different send rates and clumped up packet receives.

Detecting Lost Packets

Now that we know what packets are received by the other side of the connection, how do we detect packet loss?

The trick here is to flip it around and say that if you don’t get an ack for a packet within a certain amount of time, then we consider that packet lost.

Given that we are sending at no more than 30 packets per second, and we are redundantly sending acks roughly 30 times, if you don’t get an ack for a packet within one second, it is very likely that packet was lost.

So we are playing a bit of a trick here, while we can know 100% for sure which packets get through, but we can only be reasonably certain of the set of packets that didn’t arrive.

The implication of this is that any data which you resend using this reliability technique needs to have its own message id so that if you receive it multiple times, you can discard it. This can be done at the application level.

Handling Sequence Number Wrap-Around

No discussion of sequence numbers and acks would be complete without coverage of sequence number wrap around!

Sequence numbers and acks are 32 bit unsigned integers, so they can represent numbers in the range [0,4294967295]. Thats a very high number! So high that if you sent 30 packets per-second, it would take over four and a half years for the sequence number to wrap back around to zero.

But perhaps you want to save some bandwidth so you shorten your sequence numbers and acks to 16 bit integers. You save 4 bytes per-packet, but now they wrap around in only half an hour.

So how do we handle this wrap around case?

The trick is to realize that if the current sequence number is already very high, and the next sequence number that comes in is very low, then you must have wrapped around. So even though the new sequence number is numerically lower than the current sequence value, it actually represents a more recent packet.

For example, let’s say we encoded sequence numbers in one byte (not recommended btw. :)), then they would wrap around after 255 like this:

    … 252, 253, 254, 255, 0, 1, 2, 3, …

To handle this case we need a new function that is aware of the fact that sequence numbers wrap around to zero after 255, so that 0, 1, 2, 3 are considered more recent than 255. Otherwise, our reliability system stops working after you receive packet 255.

Here’s a function for 16 bit sequence numbers:

    inline bool sequence_greater_than( uint16_t s1, uint16_t s2 )
    {
        return ( ( s1 > s2 ) && ( s1 - s2 <= 32768 ) ) ||
               ( ( s1 < s2 ) && ( s2 - s1  > 32768 ) );
    }

This function works by comparing the two numbers and their difference. If their difference is less than ¹⁄₂ the maximum sequence number value, then they must be close together - so we just check if one is greater than the other, as usual. However, if they are far apart, their difference will be greater than ¹⁄₂ the max sequence, then we paradoxically consider the sequence number more recent if it is less than the current sequence number.

This last bit is what handles the wrap around of sequence numbers transparently, so 0,1,2 are considered more recent than 255.

Make sure you include this in any sequence number processing you do.

Congestion Avoidance

While we have solved reliability, there is still the question of congestion avoidance. TCP provides congestion avoidance as part of the packet when you get TCP reliability, but UDP has no congestion avoidance whatsoever!

If we just send packets without some sort of flow control, we risk flooding the connection and inducing severe latency (2 seconds plus!) as routers between us and the other computer become congested and buffer up packets. This happens because routers try very hard to deliver all the packets we send, and therefore tend to buffer up packets in a queue before they consider dropping them.

While it would be nice if we could tell the routers that our packets are time sensitive and should be dropped instead of buffered if the router is overloaded, we can’t really do this without rewriting the software for all routers in the world.

Instead, we need to focus on what we can actually do which is to avoid flooding the connection in the first place. We try to avoid sending too much bandwidth in the first place, and then if we detect congestion, we attempt to back off and send even less.

The way to do this is to implement our own basic congestion avoidance algorithm. And I stress basic! Just like reliability, we have no hope of coming up with something as general and robust as TCP’s implementation on the first try, so let’s keep it as simple as possible.

Measuring Round Trip Time

Since the whole point of congestion avoidance is to avoid flooding the connection and increasing round trip time (RTT), it makes sense that the most important metric as to whether or not we are flooding our connection is the RTT itself.

We need a way to measure the RTT of our connection.

Here is the basic technique:

• For each packet we send, we add an entry to a queue containing the sequence number of the packet and the time it was sent.




• Each time we receive an ack, we look up this entry and note the difference in local time between the time we receive the ack, and the time we sent the packet. This is the RTT time for that packet.




• Because the arrival of packets varies with network jitter, we need to smooth this value to provide something meaningful, so each time we obtain a new RTT we move a percentage of the distance between our current RTT and the packet RTT. 10% seems to work well for me in practice. This is called an exponentially smoothed moving average, and it has the effect of smoothing out noise in the RTT with a low pass filter.




• To ensure that the sent queue doesn’t grow forever, we discard packets once they have exceeded some maximum expected RTT. As discussed in the previous section on reliability, it is exceptionally likely that any packet not acked within a second was lost, so one second is a good value for this maximum RTT.

Now that we have RTT, we can use it as a metric to drive our congestion avoidance. If RTT gets too large, we send data less frequently, if its within acceptable ranges, we can try sending data more frequently.

Simple Binary Congestion Avoidance

As discussed before, let’s not get greedy, we’ll implement a very basic congestion avoidance. This congestion avoidance has two modes. Good and bad. I call it simple binary congestion avoidance.

Let’s assume you send packets of a certain size, say 256 bytes. You would like to send these packets 30 times a second, but if conditions are bad, you can drop down to 10 times a second.

So 256 byte packets 30 times a second is around 64kbits/sec, and 10 times a second is roughly 20kbit/sec. There isn’t a broadband network connection in the world that can’t handle at least 20kbit/sec, so we’ll move forward with this assumption. Unlike TCP which is entirely general for any device with any amount of send/recv bandwidth, we’re going to assume a minimum supported bandwidth for devices involved in our connections.

So the basic idea is this. When network conditions are “good” we send 30 packets per-second, and when network conditions are “bad” we drop to 10 packets per-second.

Of course, you can define “good” and “bad” however you like, but I’ve gotten good results considering only RTT. For example if RTT exceeds some threshold (say 250ms) then you know you are probably flooding the connection. Of course, this assumes that nobody would normally exceed 250ms under non-flooding conditions, which is reasonable given our broadband requirement.

How do you switch between good and bad? The algorithm I like to use operates as follows:

• If you are currently in good mode, and conditions become bad, immediately drop to bad mode




• If you are in bad mode, and conditions have been good for a specific length of time ’t’, then return to good mode




• To avoid rapid toggling between good and bad mode, if you drop from good mode to bad in under 10 seconds, double the amount of time ’t’ before bad mode goes back to good. Clamp this at some maximum, say 60 seconds.




• To avoid punishing good connections when they have short periods of bad behavior, for each 10 seconds the connection is in good mode, halve the time ’t’ before bad mode goes back to good. Clamp this at some minimum like 1 second.

With this algorithm you will rapidly respond to bad conditions and drop your send rate to 10 packets per-second, avoiding flooding of the connection. You’ll also conservatively try out good mode, and persist sending packets at a higher rate of 30 packets per-second, while network conditions are good.

Of course, you can implement much more sophisticated algorithms. Packet loss % can be taken into account as a metric, even the amount of network jitter (time variance in packet acks), not just RTT.

You can also get much more greedy with congestion avoidance, and attempt to discover when you can send data at a much higher bandwidth (eg. LAN), but you have to be very careful! With increased greediness comes more risk that you’ll flood the connection.

Conclusion

Our new reliability system let’s us send a steady stream of packets and notifies us which packets are received. From this we can infer lost packets, and resend data that didn’t get through if necessary. We also have a simple congestion avoidance system that drops from 30 packets per-second to 10 times a second so we don’t flood the connection.

译文

译文出处

源码下载

因 Gaffer On Games 的源码原下载地址失效, 所以特地补上.

请点击

原文

原文出处

Introduction

Hi, I’m Glenn Fiedler and welcome to Networking for Game Programmers.

In the previous article we sent and received packets over UDP. Since UDP is connectionless, one UDP socket can be used to exchange packets with any number of different computers. In multiplayer games however, we usually only want to exchange packets between a small set of connected computers.

As the first step towards a general connection system, we’ll start with the simplest case possible: creating a virtual connection between two computers on top of UDP.

But first, we’re going to dig in a bit deeper about how the Internet really works!

The Internet NOT a series of tubes

In 2006, Senator Ted Stevens made internet history with his famous speech on the net neutrality act:

“The internet is not something that you just dump something on. It’s not a big truck. It’s a series of tubes”

When I first started using the Internet, I was just like Ted. Sitting in the computer lab in University of Sydney in 1995, I was “surfing the web” with this new thing called Netscape Navigator, and I had absolutely no idea what was going on.

You see, I thought each time you connected to a website there was some actual connection going on, like a telephone line. I wondered, how much does it cost each time I connect to a new website? 30 cents? A dollar? Was somebody from the university going to tap me on the shoulder and ask me to pay the long distance charges? :)

Of course, this all seems silly now.

There is no switchboard somewhere that directly connects you via a physical phone line to the other computer you want to talk to, let alone a series of pneumatic tubes like Sen. Stevens would have you believe.

No Direct Connections

Instead your data is sent over Internet Protocol (IP) via packets that hop from computer to computer.

A packet may pass through several computers before it reaches its destination. You cannot know the exact set of computers in advance, as it changes dynamically depending on how the network decides to route packets. You could even send two packets A and B to the same address, and they may take different routes.

On unix-like systems can inspect the route that packets take by calling “traceroute” and passing in a destination hostname or IP address.

On windows, replace “traceroute” with “tracert” to get it to work.

Try it with a few websites like this:

    traceroute slashdot.org
    traceroute amazon.com
    traceroute google.com
    traceroute bbc.co.uk
    traceroute news.com.au

Take a look and you should be able to convince yourself pretty quickly that there is no direct connection.

How Packets Get Delivered

In the first article, I presented a simple analogy for packet delivery, describing it as somewhat like a note being passed from person to person across a crowded room.

While this analogy gets the basic idea across, it is much too simple. The Internet is not a flat network of computers, it is a network of networks. And of course, we don’t just need to pass letters around a small room, we need to be able to send them anywhere in the world.

It should be pretty clear then that the best analogy is the postal service!

When you want to send a letter to somebody you put your letter in the mailbox and you trust that it will be delivered correctly. It’s not really relevant to you how it gets there, as long as it does. Somebody has to physically deliver your letter to its destination of course, so how is this done?

Well first off, the postman sure as hell doesn’t take your letter and deliver it personally! It seems that the postal service is not a series of tubes either. Instead, the postman takes your letter to the local post office for processing.

If the letter is addressed locally then the post office just sends it back out, and another postman delivers it directly. But, if the address is is non-local then it gets interesting! The local post office is not able to deliver the letter directly, so it passes it “up” to the next level of hierarchy, perhaps to a regional post office which services cities nearby, or maybe to a mail center at an airport, if the address is far away. Ideally, the actual transport of the letter would be done using a big truck.

Lets be complicated and assume the letter is sent from Los Angeles to Sydney, Australia. The local post office receives the letter and given that it is addressed internationally, sends it directly to a mail center at LAX. The letter is processed again according to address, and gets routed on the next flight to Sydney.

The plane lands at Sydney airport where an entirely different postal system takes over. Now the whole process starts operating in reverse. The letter travels “down” the hierarchy, from the general, to the specific. From the mail hub at Sydney Airport it gets sent out to a regional center, the regional center delivers it to the local post office, and eventually the letter is hand delivered by a mailman with a funny accent. Crikey! :)

Just like post offices determine how to deliver letters via their address, networks deliver packets according to their IP address. The low-level details of this delivery and the actual routing of packets from network to network is actually quite complex, but the basic idea is that each router is just another computer, with a routing table describing where packets matching sets of addresses should go, as well as a default gateway address describing where to pass packets for which there is no matching entry in the table. It is routing tables, and the physical connections they represent that define the network of networks that is the Internet.

The job of configuring these routing tables is up to network administrators, not programmers like us. But if you want to read more about it, then this article from ars technica provides some fascinating insight into how networks exchange packets between each other via peering and transit relationships. You can also read more details about routing tables in this linux faq, and about the border gateway protocol on wikipedia, which automatically discovers how to route packets between networks, making the internet a truly distributed system capable of dynamically routing around broken connectivity.

Virtual Connections

Now back to connections.

If you have used TCP sockets then you know that they sure look like a connection, but since TCP is implemented on top of IP, and IP is just packets hopping from computer to computer, it follows that TCP’s concept of connection must be a virtual connection.

If TCP can create a virtual connection over IP, it follows that we can do the same over UDP.

Lets define our virtual connection as two computers exchanging UDP packets at some fixed rate like 10 packets per-second. As long as the packets are flowing, we consider the two computers to be virtually connected.

Our connection has two sides:

• One computer sits there and listens for another computer to connect to it. We’ll call this computer the server.


• Another computer connects to a server by specifying an IP address and port. We’ll call this computer the client.

In our case, we only allow one client to connect to the server at any time. We’ll generalize our connection system to support multiple simultaneous connections in a later article. Also, we assume that the IP address of the server is on a fixed IP address that the client may directly connect to.

Protocol ID

Since UDP is connectionless our UDP socket can receive packets sent from any computer.

We’d like to narrow this down so that the server only receives packets sent from the client, and the client only receives packets sent from the server. We can’t just filter out packets by address, because the server doesn’t know the address of the client in advance. So instead, we prefix each UDP packet with small header containing a 32 bit protocol id as follows:

    [uint protocol id]
    (packet data…)

The protocol id is just some unique number representing our game protocol. Any packet that arrives from our UDP socket first has its first four bytes inspected. If they don’t match our protocol id, then the packet is ignored. If the protocol id does match, we strip out the first four bytes of the packet and deliver the rest as payload.

You just choose some number that is reasonably unique, perhaps a hash of the name of your game and the protocol version number. But really you can use anything. The whole point is that from the point of view of our connection based protocol, packets with different protocol ids are ignored.

Detecting Connection

Now we need a way to detect connection.

Sure we could do some complex handshaking involving multiple UDP packets sent back and forth. Perhaps a client “request connection” packet is sent to the server, to which the server responds with a “connection accepted” sent back to the client, or maybe an “i’m busy” packet if a client tries to connect to server which already has a connected client.

Or… we could just setup our server to take the first packet it receives with the correct protocol id, and consider a connection to be established.

The client just starts sending packets to the server assuming connection, when the server receives the first packet from the client, it takes note of the IP address and port of the client, and starts sending packets back.

The client already knows the address and port of the server, since it was specified on connect. So when the client receives packets, it filters out any that don’t come from the server address. Similarly, once the server receives the first packet from the client, it gets the address and port of the client from “recvfrom”, so it is able to ignore any packets that don’t come from the client address.

We can get away with this shortcut because we only have two computers involved in the connection. In later articles, we’ll extend our connection system to support more than two computers in a client/server or peer-to-peer topology, and at this point we’ll upgrade our connection negotiation to something more robust.

But for now, why make things more complicated than they need to be?

Detecting Disconnection

How do we detect disconnection?

Well if a connection is defined as receiving packets, we can define disconnection as not receiving packets.

To detect when we are not receiving packets, we keep track of the number of seconds since we last received a packet from the other side of the connection. We do this on both sides.

Each time we receive a packet from the other side, we reset our accumulator to 0.0, each update we increase the accumulator by the amount of time that has passed.

If this accumulator exceeds some value like 10 seconds, the connection “times out” and we disconnect.

This also gracefully handles the case of a second client trying to connect to a server that has already made a connection with another client. Since the server is already connected it ignores packets coming from any address other than the connected client, so the second client receives no packets in response to the packets it sends, so the second client times out and disconnects.

Conclusion

And that’s all it takes to setup a virtual connection: some way to establish connection, filtering for packets not involved in the connection, and timeouts to detect disconnection.

Our connection is as real as any TCP connection, and the steady stream of UDP packets it provides is a suitable starting point for a multiplayer action game.

Now that you have your virtual connection over UDP, you can easily setup a client/server relationship for a two player multiplayer game without TCP.

译文

译文出处

源码下载

因 Gaffer On Games 的源码原下载地址失效, 所以特地补上.

请点击

原文

原文出处

Introduction

Hi, I’m Glenn Fiedler and welcome to Networking for Game Programmers.

In the previous article we discussed options for sending data between computers and decided to use UDP instead of TCP for time critical data.

In this article I am going to show you how to send and receive UDP packets.

BSD sockets

For most modern platforms you have some sort of basic socket layer available based on BSD sockets.

BSD sockets are manipulated using simple functions like “socket”, “bind”, “sendto” and “recvfrom”. You can of course work directly with these functions if you wish, but it becomes difficult to keep your code platform independent because each platform is slightly different.

So although I will first show you BSD socket example code to demonstrate basic socket usage, we won’t be using BSD sockets directly for long. Once we’ve covered all basic socket functionality we’ll abstract everything away into a set of classes, making it easy to you to write platform independent socket code.

Platform specifics

First let’s setup a define so we can detect what our current platform is and handle the slight differences in sockets from one platform to another:

    // platform detection

    #define PLATFORM_WINDOWS  1
    #define PLATFORM_MAC      2
    #define PLATFORM_UNIX     3

    #if defined(_WIN32)
    #define PLATFORM PLATFORM_WINDOWS
    #elif defined(APPLE)
    #define PLATFORM PLATFORM_MAC
    #else
    #define PLATFORM PLATFORM_UNIX
    #endif

Now let’s include the appropriate headers for sockets. Since the header files are platform specific, we’ll use the platform #define to include different sets of files depending on the platform:

    #if PLATFORM == PLATFORM_WINDOWS

        #include <winsock2.h>

    #elif PLATFORM == PLATFORM_MAC ||
          PLATFORM == PLATFORM_UNIX

        #include <sys/socket.h>
        #include <netinet/in.h>
        #include <fcntl.h>

    #endif

Sockets are built in to the standard system libraries on unix-based platforms so we don’t have to link to any additonal libraries. However, on Windows we need to link to the winsock library to get socket functionality.

Here is a simple trick to do this without having to change your project or makefile:

    #if PLATFORM == PLATFORM_WINDOWS
    #pragma comment( lib, "wsock32.lib" )
    #endif

I like this trick because I’m super lazy. You can always link from your project or makefile if you wish.

Initializing the socket layer

Most unix-like platforms (including macosx) don’t require any specific steps to initialize the sockets layer, however Windows requires that you jump through some hoops to get your socket code working.

You must call “WSAStartup” to initialize the sockets layer before you call any socket functions, and “WSACleanup” to shutdown when you are done.

Let’s add two new functions:

    bool InitializeSockets()
    {
        #if PLATFORM == PLATFORM_WINDOWS
        WSADATA WsaData;
        return WSAStartup( MAKEWORD(2,2),
                           &WsaData )
            == NO_ERROR;
        #else
        return true;
        #endif
    }

    void ShutdownSockets()
    {
        #if PLATFORM == PLATFORM_WINDOWS
        WSACleanup();
        #endif
    }

Now we have a platform independent way to initialize the socket layer.

Creating a socket

It’s time to create a UDP socket, here’s how to do it:

    int handle = socket( AF_INET,
                         SOCK_DGRAM,
                         IPPROTO_UDP );

    if ( handle <= 0 )
    {
        printf( "failed to create socket\n" );
        return false;
    }

Next we bind the UDP socket to a port number (eg. 30000). Each socket must be bound to a unique port, because when a packet arrives the port number determines which socket to deliver to. Don’t use ports lower than 1024 because they are reserved for the system. Also try to avoid using ports above 50000 because they used when dynamically assigning ports.

Special case: if you don’t care what port your socket gets bound to just pass in “0” as your port, and the system will select a free port for you.

    sockaddr_in address;
    address.sin_family = AF_INET;
    address.sin_addr.s_addr = INADDR_ANY;
    address.sin_port =
        htons( (unsigned short) port );

    if ( bind( handle,
               (const sockaddr) &address,
               sizeof(sockaddr_in) ) < 0 )
    {
        printf( "failed to bind socket\n" );
        return false;
    }

Now the socket is ready to send and receive packets.

But what is this mysterious call to “htons” in the code above? This is just a helper function that converts a 16 bit integer value from host byte order (little or big-endian) to network byte order (big-endian). This is required whenever you directly set integer members in socket structures.

You’ll see “htons” (host to network short) and its 32 bit integer sized cousin “htonl” (host to network long) used several times throughout this article, so keep an eye out, and you’ll know what is going on.

Setting the socket as non-blocking

By default sockets are set in what is called “blocking mode”.

This means that if you try to read a packet using “recvfrom”, the function will not return until a packet is available to read. This is not at all suitable for our purposes. Video games are realtime programs that simulate at 30 or 60 frames per second, they can’t just sit there waiting for a packet to arrive!

The solution is to flip your sockets into “non-blocking mode” after you create them. Once this is done, the “recvfrom” function returns immediately when no packets are available to read, with a return value indicating that you should try to read packets again later.

Here’s how put a socket in non-blocking mode:

    #if PLATFORM == PLATFORM_MAC ||
        PLATFORM == PLATFORM_UNIX

        int nonBlocking = 1;
        if ( fcntl( handle,
                    F_SETFL,
                    O_NONBLOCK,
                    nonBlocking ) == -1 )
        {
            printf( "failed to set non-blocking\n" );
            return false;
        }

    #elif PLATFORM == PLATFORM_WINDOWS

        DWORD nonBlocking = 1;
        if ( ioctlsocket( handle,
                          FIONBIO,
                          &nonBlocking ) != 0 )
        {
            printf( "failed to set non-blocking\n" );
            return false;
        }

    #endif

Windows does not provide the “fcntl” function, so we use the “ioctlsocket” function instead.

Sending packets

UDP is a connectionless protocol, so each time you send a packet you must specify the destination address. This means you can use one UDP socket to send packets to any number of different IP addresses, there’s no single computer at the other end of your UDP socket that you are connected to.

Here’s how to send a packet to a specific address:

    int sent_bytes =
        sendto( handle,
                (const char)packet_data,
                packet_size,
                0,
                (sockaddr)&address,
                sizeof(sockaddr_in) );

    if ( sent_bytes != packet_size )
    {
        printf( "failed to send packet\n" );
        return false;
    }

Important! The return value from “sendto” only indicates if the packet was successfully sent from the local computer. It does not tell you whether or not the packet was received by the destination computer. UDP has no way of knowing whether or not the the packet arrived at its destination!

In the code above we pass a “sockaddr_in” structure as the destination address. How do we setup one of these structures?

Let’s say we want to send to the address 207.45.186.98:30000

Starting with our address in this form:

    unsigned int a = 207;
    unsigned int b = 45;
    unsigned int c = 186;
    unsigned int d = 98;
    unsigned short port = 30000;

We have a bit of work to do to get it in the form required by “sendto”:

    unsigned int address = ( a << 24 ) |
                           ( b << 16 ) |
                           ( c << 8  ) |
                             d;

    sockaddr_in addr;
    addr.sin_family = AF_INET;
    addr.sin_addr.s_addr = htonl( address );
    addr.sin_port = htons( port );

As you can see, we first combine the a,b,c,d values in range [0,255] into a single unsigned integer, with each byte of the integer now corresponding to the input values. We then initialize a “sockaddr_in” structure with the integer address and port, making sure to convert our integer address and port values from host byte order to network byte order using “htonl” and “htons”.

Special case: if you want to send a packet to yourself, there’s no need to query the IP address of your own machine, just pass in the loopback address 127.0.0.1 and the packet will be sent to your local machine.

Receiving packets

Once you have a UDP socket bound to a port, any UDP packets sent to your sockets IP address and port are placed in a queue. To receive packets just loop and call “recvfrom” until it fails with EWOULDBLOCK indicating there are no more packets to receive.

Since UDP is connectionless, packets may arrive from any number of different computers. Each time you receive a packet “recvfrom” gives you the IP address and port of the sender, so you know where the packet came from.

Here’s how to loop and receive all incoming packets:

    while ( true )
    {
        unsigned char packet_data[256];

        unsigned int max_packet_size =
            sizeof( packet_data );

        #if PLATFORM == PLATFORM_WINDOWS
        typedef int socklen_t;
        #endif

        sockaddr_in from;
        socklen_t fromLength = sizeof( from );

        int bytes = recvfrom( socket,
                              (char)packet_data,
                              max_packet_size,
                              0,
                              (sockaddr)&from,
                              &fromLength );

        if ( bytes <= 0 )
            break;

        unsigned int from_address =
            ntohl( from.sin_addr.s_addr );

        unsigned int from_port =
            ntohs( from.sin_port );

        // process received packet
    }

Any packets in the queue larger than your receive buffer will be silently discarded. So if you have a 256 byte buffer to receive packets like the code above, and somebody sends you a 300 byte packet, the 300 byte packet will be dropped. You will not receive just the first 256 bytes of the 300 byte packet.

Since you are writing your own game network protocol, this is no problem at all in practice, just make sure your receive buffer is big enough to receive the largest packet your code could possibly send.

Destroying a socket

On most unix-like platforms, sockets are file handles so you use the standard file “close” function to clean up sockets once you are finished with them. However, Windows likes to be a little bit different, so we have to use “closesocket” instead:

#if PLATFORM == PLATFORM_MAC ||
    PLATFORM == PLATFORM_UNIX
close( socket );
#elif PLATFORM == PLATFORM_WINDOWS
closesocket( socket );
#endif

Hooray windows.

Socket class

So we’ve covered all the basic operations: creating a socket, binding it to a port, setting it to non-blocking, sending and receiving packets, and destroying the socket.

But you’ll notice most of these operations are slightly platform dependent, and it’s pretty annoying to have to remember to #ifdef and do platform specifics each time you want to perform socket operations.

We’re going to solve this by wrapping all our socket functionality up into a “Socket” class. While we’re at it, we’ll add an “Address” class to make it easier to specify internet addresses. This avoids having to manually encode or decode a “sockaddr_in” structure each time we send or receive packets.

So let’s add a socket class:

    class Socket
    {
    public:

        Socket();

        ~Socket();

        bool Open( unsigned short port );

        void Close();

        bool IsOpen() const;

        bool Send( const Address & destination,
                   const void  data,
                   int size );

        int Receive( Address & sender,
                     void * data,
                     int size );

    private:

        int handle;
    };

and an address class:

    class Address
    {
    public:

        Address();

        Address( unsigned char a,
                 unsigned char b,
                 unsigned char c,
                 unsigned char d,
                 unsigned short port );

        Address( unsigned int address,
                 unsigned short port );

        unsigned int GetAddress() const;

        unsigned char GetA() const;
        unsigned char GetB() const;
        unsigned char GetC() const;
        unsigned char GetD() const;

        unsigned short GetPort() const;

    private:

        unsigned int address;
        unsigned short port;
    };

Here’s how to to send and receive packets with these classes:

    // create socket

    const int port = 30000;

    Socket socket;

    if ( !socket.Open( port ) )
    {
        printf( "failed to create socket!\n" );
        return false;
    }

    // send a packet

    const char data[] = "hello world!";

    socket.Send( Address(127,0,0,1,port), data, sizeof( data ) );

    // receive packets

    while ( true )
    {
        Address sender;
        unsigned char buffer[256];
        int bytes_read =
            socket.Receive( sender,
                            buffer,
                            sizeof( buffer ) );
        if ( !bytes_read )
            break;

        // process packet
    }

As you can see it’s much simpler than using BSD sockets directly.

As an added bonus the code is the same on all platforms because everything platform specific is handled inside the socket and address classes.

Conclusion

You now have a platform independent way to send and receive packets. Enjoy :)

译文

译文出处

源码下载

因 Gaffer On Games 的源码原下载地址失效, 所以特地补上.

请点击

原文

原文出处

Introduction

Hi, I’m Glenn Fiedler and welcome to Networking for Game Programmers.

In this article we start with the most basic aspect of network programming: sending and receiving data over the network. This is perhaps the simplest and most basic part of what network programmers do, but still it is quite intricate and non-obvious as to what the best course of action is.

You have most likely heard of sockets, and are probably aware that there are two main types: TCP and UDP. When writing a network game, we first need to choose what type of socket to use. Do we use TCP sockets, UDP sockets or a mixture of both? Take care because if you get this wrong it will have terrible effects on your multiplayer game!

The choice you make depends entirely on what sort of game you want to network. So from this point on and for the rest of this article series, I assume you want to network an action game. You know, games like Halo, Battlefield 1942, Quake, Unreal, CounterStrike and Team Fortress.

In light of the fact that we want to network an action game, we’ll take a very close look at the properties of each protocol, and dig a bit into how the internet actually works. Once we have all this information, the correct choice is clear.

TCP/IP

TCP stands for “transmission control protocol”. IP stands for “internet protocol”. Together they form the backbone for almost everything you do online, from web browsing to IRC to email, it’s all built on top of TCP/IP.

If you have ever used a TCP socket, then you know it’s a reliable connection based protocol. This means you create a connection between two machines, then you exchange data much like you’re writing to a file on one side, and reading from a file on the other.

TCP connections are reliable and ordered. All data you send is guaranteed to arrive at the other side and in the order you wrote it. It’s also a stream protocol, so TCP automatically splits your data into packets and sends them over the network for you.

IP

The simplicity of TCP is in stark contrast to what actually goes on underneath TCP at the IP or “internet protocol” level.

Here there is no concept of connection, packets are simply passed from one computer to the next. You can visualize this process being somewhat like a hand-written note passed from one person to the next across a crowded room, eventually, reaching the person it’s addressed to, but only after passing through many hands.

There is also no guarantee that this note will actually reach the person it is intended for. The sender just passes the note along and hopes for the best, never knowing whether or not the note was received, unless the other person decides to write back!

Of course IP is in reality a little more complicated than this, since no one computer knows the exact sequence of computers to pass the packet along to so that it reaches its destination quickly. Sometimes IP passes along multiple copies of the same packet and these packets make their way to the destination via different paths, causing packets to arrive out of order and in duplicate.

This is because the internet is designed to be self-organizing and self-repairing, able to route around connectivity problems rather than relying on direct connections between computers. It’s actually quite cool if you think about what’s really going on at the low level. You can read all about this in the classic book TCP/IP Illustrated.

UDP

Instead of treating communications between computers like writing to files, what if we want to send and receive packets directly?

We can do this using UDP.

UDP stands for “user datagram protocol” and it’s another protocol built on top of IP, but unlike TCP, instead of adding lots of features and complexity, UDP is a very thin layer over IP.

With UDP we can send a packet to a destination IP address (eg. 112.140.20.10) and port (say 52423), and it gets passed from computer to computer until it arrives at the destination or is lost along the way.

On the receiver side, we just sit there listening on a specific port (eg. 52423) and when a packet arrives from any computer (remember there are no connections!), we get notified of the address and port of the computer that sent the packet, the size of the packet, and can read the packet data.

Like IP, UDP is an unreliable protocol. In practice however, most packets that are sent will get through, but you’ll usually have around 1-5% packet loss, and occasionally you’ll get periods where no packets get through at all (remember there are lots of computers between you and your destination where things can go wrong…)

There is also no guarantee of ordering of packets with UDP. You could send 5 packets in order 1,2,3,4,5 and they could arrive completely out of order like 3,1,2,5,4. In practice, packets tend to arrive in order most of the time, but you cannot rely on this!

UDP also provides a 16 bit checksum, which in theory is meant to protect you from receiving invalid or truncated data, but you can’t even trust this, since 16 bits is just not enough protection when you are sending UDP packets rapidly over a long period of time. Statistically, you can’t even rely on this checksum and must add your own.

So in short, when you use UDP you’re pretty much on your own!

TCP vs. UDP

We have a decision to make here, do we use TCP sockets or UDP sockets?

Lets look at the properties of each:

TCP:

• Connection based


• Guaranteed reliable and ordered


• Automatically breaks up your data into packets for you


• Makes sure it doesn’t send data too fast for the internet connection to handle (flow control)


• Easy to use, you just read and write data like its a file

UDP:

• No concept of connection, you have to code this yourself


• No guarantee of reliability or ordering of packets, they may arrive out of order, be duplicated, or not arrive at all!


• You have to manually break your data up into packets and send them


• You have to make sure you don’t send data too fast for your internet connection to handle


• If a packet is lost, you need to devise some way to detect this, and resend that data if necessary


• You can’t even rely on the UDP checksum so you must add your own

The decision seems pretty clear then, TCP does everything we want and its super easy to use, while UDP is a huge pain in the ass and we have to code everything ourselves from scratch.

So obviously we just use TCP right?

Wrong!

Using TCP is the worst possible mistake you can make when developing a multiplayer game! To understand why, you need to see what TCP is actually doing above IP to make everything look so simple.

How TCP really works

TCP and UDP are both built on top of IP, but they are radically different. UDP behaves very much like the IP protocol underneath it, while TCP abstracts everything so it looks like you are reading and writing to a file, hiding all complexities of packets and unreliability from you.

So how does it do this?

Firstly, TCP is a stream protocol, so you just write bytes to a stream, and TCP makes sure that they get across to the other side. Since IP is built on packets, and TCP is built on top of IP, TCP must therefore break your stream of data up into packets. So, some internal TCP code queues up the data you send, then when enough data is pending the queue, it sends a packet to the other machine.

This can be a problem for multiplayer games if you are sending very small packets. What can happen here is that TCP may decide it’s not going to send data until you have buffered up enough data to make a reasonably sized packet to send over the network.

This is a problem because you want your client player input to get to the server as quickly as possible, if it is delayed or “clumped up” like TCP can do with small packets, the client’s user experience of the multiplayer game will be very poor. Game network updates will arrive late and infrequently, instead of on-time and frequently like we want.

TCP has an option to fix this behavior called TCP_NODELAY. This option instructs TCP not to wait around until enough data is queued up, but to flush any data you write to it immediately. This is referred to as disabling Nagle’s algorithm.

Unfortunately, even if you set this option TCP still has serious problems for multiplayer games and it all stems from how TCP handles lost and out of order packets to present you with the “illusion” of a reliable, ordered stream of data.

How TCP implements reliability

Fundamentally TCP breaks down a stream of data into packets, sends these packets over unreliable IP, then takes the packets received on the other side and reconstructs the stream.

But what happens when a packet is lost?

What happens when packets arrive out of order or are duplicated?

Without going too much into the details of how TCP works because its super-complicated (please refer to TCP/IP Illustrated) in essence TCP sends out a packet, waits a while until it detects that packet was lost because it didn’t receive an ack (or acknowledgement), then resends the lost packet to the other machine. Duplicate packets are discarded on the receiver side, and out of order packets are resequenced so everything is reliable and in order.

The problem is that if we were to send our time critical game data over TCP, whenever a packet is dropped it has to stop and wait for that data to be resent. Yes, even if more recent data arrives, that new data gets put in a queue, and you cannot access it until that lost packet has been retransmitted. How long does it take to resend the packet?

Well, it’s going to take at least round trip latency for TCP to work out that data needs to be resent, but commonly it takes 2*RTT, and another one way trip from the sender to the receiver for the resent packet to get there. So if you have a 125ms ping, you’ll be waiting roughly 1/5th of a second for the packet data to be resent at best, and in worst case conditions you could be waiting up to half a second or more (consider what happens if the attempt to resend the packet fails to get through?). What happens if TCP decides the packet loss indicates network congestion and it backs off? Yes it actually does this. Fun times!

Never use TCP for time critical data

The problem with using TCP for realtime games like FPS is that unlike web browsers, or email or most other applications, these multiplayer games have a real time requirement on packet delivery.

What this means is that for many parts of a game, for example player input and character positions, it really doesn’t matter what happened a second ago, the game only cares about the most recent data.

TCP was simply not designed with this in mind.

Consider a very simple example of a multiplayer game, some sort of action game like a shooter. You want to network this in a very simple way. Every frame you send the input from the client to the server (eg. keypresses, mouse input controller input), and each frame the server processes the input from each player, updates the simulation, then sends the current position of game objects back to the client for rendering.

So in our simple multiplayer game, whenever a packet is lost, everything has to stop and wait for that packet to be resent. On the client game objects stop receiving updates so they appear to be standing still, and on the server input stops getting through from the client, so the players cannot move or shoot. When the resent packet finally arrives, you receive this stale, out of date information that you don’t even care about! Plus, there are packets backed up in queue waiting for the resend which arrive at same time, so you have to process all of these packets in one frame. Everything is clumped up!

Unfortunately, there is nothing you can do to fix this behavior, it’s just the fundamental nature of TCP. This is just what it takes to make the unreliable, packet-based internet look like a reliable-ordered stream.

Thing is we don’t want a reliable ordered stream.

We want our data to get as quickly as possible from client to server without having to wait for lost data to be resent.

This is why you should never use TCP when networking time-critical data!

Wait? Why can’t I use both UDP and TCP?

For realtime game data like player input and state, only the most recent data is relevant, but for other types of data, say perhaps a sequence of commands sent from one machine to another, reliability and ordering can be very important.

The temptation then is to use UDP for player input and state, and TCP for the reliable ordered data. If you’re sharp you’ve probably even worked out that you may have multiple “streams” of reliable ordered commands, maybe one about level loading, and another about AI. Perhaps you think to yourself, “Well, I’d really not want AI commands to stall out if a packet is lost containing a level loading command - they are completely unrelated!”. You are right, so you may be tempted to create one TCP socket for each stream of commands.

On the surface, this seems like a great idea. The problem is that since TCP and UDP are both built on top of IP, the underlying packets sent by each protocol will affect each other. Exactly how they affect each other is quite complicated and relates to how TCP performs reliability and flow control, but fundamentally you should remember that TCP tends to induce packet loss in UDP packets. For more information, read this paper on the subject.

Also, it’s pretty complicated to mix UDP and TCP. If you mix UDP and TCP you lose a certain amount of control. Maybe you can implement reliability in a more efficient way that TCP does, better suited to your needs? Even if you need reliable-ordered data, it’s possible, provided that data is small relative to the available bandwidth to get that data across faster and more reliably that it would if you sent it over TCP. Plus, if you have to do NAT to enable home internet connections to talk to each other, having to do this NAT once for UDP and once for TCP (not even sure if this is possible…) is kind of painful.

Conclusion

My recommendation is not only that you use UDP, but that you only use UDP for your game protocol. Don’t mix TCP and UDP! Instead, learn how to implement the specific features of TCP that you need inside your own custom UDP based protocol.

Of course, it is no problem to use HTTP to talk to some RESTful services while your game is running. I’m not saying you can’t do that. A few TCP connections running while your game is running isn’t going to bring everything down. The point is, don’t split your game protocol across UDP and TCP. Keep your game protocol running over UDP so you are fully in control of the data you send and receive and how reliability, ordering and congestion avoidance are implemented.

The rest of this article series show you how to do this, from creating your own virtual connection on top of UDP, to creating your own reliability, flow control and congestion avoidance.

译文

译文出处

项目越来越大，每次需要重新编译整个项目都是一件很浪费时间的事情。Research了一下，找到以下可以帮助提高速度的方法，总结一下。

tmpfs

有人说在Windows下用了RAMDisk把一个项目编译时间从4.

5小时减少到了5分钟，也许这个数字是有点夸张了，不过粗想想，把文件放到内存上做编译应该是比在磁盘

上快多了吧，尤其如果编译器需要生成很多临时文件的话。

这个做法的实现成本最低，在Linux中，直接mount一个tmpfs就可以了。而且对所编译的工程没有任何要求，也不用改动编译环境。

mount -t tmpfs tmpfs ~/build -o size=1G

用2.6.32.2的Linux Kernel来测试一下编译速度：

• 用物理磁盘：40分16秒

• 用tmpfs：39分56秒

呃……没什么变化。看来编译慢很大程度上瓶颈并不在IO上面。但对于一个实际项目来说，

编译过程中可能还会有打包等IO密集的操作，所以只要可能，用tmpfs是有

益无害的。

当然对于大项目来说，你需要有足够的内存才能负担得起这个tmpfs的开销。

make -j

既然IO不是瓶颈，那CPU就应该是一个影响编译速度的重要因素了。

用make -j带一个参数，可以把项目在进行并行编译，比如在一台双核的机器上，完全可以用make -
j4，让make最多允许4个编译命令同时执行，这样可以更有效的利用CPU资源。

还是用Kernel来测试：

• 用make： 40分16秒

• 用make -j4：23分16秒

• 用make -j8：22分59秒

由此看来，在多核CPU上，适当的进行并行编译还是可以明显提高编译速度的。但并行的任务不宜太多，一般是以CPU的核心数目的两倍为宜。

不过这个方案不是完全没有cost的，如果项目的Makefile不规范，没有正确的设置好依赖关系，并行编译的结果就是编译不能正常进行。如果依赖关系设置过于保守
，则可能本身编译的可并行度就下降了，也不能取得最佳的效果。

ccache

ccache用于把编译的中间结果进行缓存，以便在再次编译的时候可以节省时间。这对于玩Kernel来说实在是再好不过了，因为经常需要修改一些Kernel的代码，然后
再重新编译，而这两次编译大部分东西可能都没有发生变化。对于平时开发项目来说，也是一样。为什么不是直接用make所支持的增量编译呢？还是因为现实中，因
为Makefile的不规范，很可能这种“聪明”的方案根本不能正常工作，只有每次make clean再make才行。

安装完ccache后，可以在/usr/local/bin下建立gcc，g++，c++，cc的symbolic
link，链到/usr/bin/ccache上。总之确认系统在调用gcc等命令时会调用到ccache就可以了（通常情况下/usr/local/bin会在PATH中排在/usr/bin前面）。

继续测试：

• 用ccache的第一次编译(make -j4)：23分38秒

• 用ccache的第二次编译(make -j4)：8分48秒

• 用ccache的第三次编译(修改若干配置，make -j4)：23分48秒

看来修改配置（我改了CPU类型…）对ccache的影响是很大的，因为基本头文件发生变化后，就导致所有缓存数据都无效了，必须重头来做。但如果只是修改一些.
c文件的代码，ccache的效果还是相当明显的。而且使用ccache对项目没有特别的依赖，布署成本很低，这在日常工作中很实用。

可以用ccache -s来查看cache的使用和命中情况：

cache directory /home/lifanxi/.ccache

cache hit 7165

cache miss 14283

called for link 71

not a C/C++ file 120

no input file 3045

files in cache 28566

cache size 81.7 Mbytes

max cache size 976.6 Mbytes

可以看到，显然只有第二编次译时cache命中了，cache miss是第一次和第三次编译带来的。两次cache占用了81.7M的磁盘，还是完全可以接受的。

distcc

一台机器的能力有限，可以联合多台电脑一起来编译。这在公司的日常开发中也是可行的，因为可能每个开发人员都有自己的开发编译环境，它们的编译器版本一般
是一致的，公司的网络也通常具有较好的性能。这时就是distcc大显身手的时候了。

使用distcc，并不像想象中那样要求每台电脑都具有完全一致的环境，它只要求源代码可以用make -j并行编译，并且参与分布式编译的电脑系统中具有相同的编译
器。因为它的原理只是把预处理好的源文件分发到多台计算机上，预处理、编译后的目标文件的链接和其它除编译以外的工作仍然是在发起编译的主控电脑上完成，
所以只要求发起编译的那台机器具备一套完整的编译环境就可以了。

distcc安装后，可以启动一下它的服务：

/usr/bin/distccd –daemon –allow 10.64.0.0/16

默认的3632端口允许来自同一个网络的distcc连接。

然后设置一下DISTCC_HOSTS环境变量，设置可以参与编译的机器列表。

通常localhost也参与编译，但如果可以参与编译的机器很多，则可以把localhost从这个列表

中去掉，这样本机就完全只是进行预处理、分发和链接了，编译都在别的机器上完成。

因为机器很多时，localhost的处理负担很重，所以它就不再“兼职”编译了。

export DISTCC_HOSTS="localhost 10.64.25.1 10.64.25.2 10.64.25.3"

然后与ccache类似把g++，gcc等常用的命令链接到/usr/bin/distcc上就可以了。

在make的时候，也必须用-j参数，一般是参数可以用所有参用编译的计算机CPU内核总数的两倍做为并行的任务数。

同样测试一下：

• 一台双核计算机，make -j4：23分16秒

• 两台双核计算机，make -j4：16分40秒

• 两台双核计算机，make -j8：15分49秒

跟最开始用一台双核时的23分钟相比，还是快了不少的。如果有更多的计算机加入，也可以得到更好的效果。

在编译过程中可以用distccmon-text来查看编译任务的分配情况。distcc也可以与ccache同时使用，通过设置一个环境变量就可以做到，非常方便。

总结

• tmpfs： 解决IO瓶颈，充分利用本机内存资源

• make -j： 充分利用本机计算资源

• distcc： 利用多台计算机资源

• ccache： 减少重复编译相同代码的时间

这些工具的好处都在于布署的成本相对较低，综合利用这些工具，就可以轻轻松松的节省相当可观的时间。

上面介绍的都是这些工具最基本的用法，更多的用法可以参考它们各自的man page。

A fish flock AI Plugin for Unreal Engine 4
一个基于虚幻4的鱼群 AI 插件

this Plugin version can Run 2000+ fishes at the same time
这个插件版本可以同时运行 2000+ 条鱼儿

源码已放到fish

Video Preview 视频演示

Download

MyFish.exe (Win64)

. . .

在数据的加解密领域，算法分为对称密钥与非对称密钥两种。

对称密钥与非对称密钥由于各自的特点，所应用的领域是不尽相同的。

对称密钥加密算法由于其速度快，一般用于整体数据的加密，而非对称密钥加密算法的安全性能佳，在数字签名领域得到广泛的应用。

微型加密算法（TEA）及其相关变种（XTEA，Block TEA，XXTEA） 都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。

TEA是Tiny Encryption Algorithm的缩写，以加密解密速度快，实现简单著称。

TEA 算法最初是由剑桥计算机实验室的 David Wheeler 和 Roger Needham 在 1994 年设计的。

该算法使用 128 位的密钥为 64 位的信息块进行加密，它需要进行 64 轮迭代，尽管作者认为 32 轮已经足够了。

该算法使用了一个神秘常数δ作为倍数，它来源于黄金比率，以保证每一轮加密都不相同。

但δ的精确值似乎并不重要，这里 TEA 把它定义为 δ=「(√5 - 1)231」（也就是程序中的 0×9E3779B9）。

之后 TEA 算法被发现存在缺陷，作为回应，设计者提出了一个 TEA 的升级版本——XTEA（有时也被称为“tean”）。

XTEA 跟 TEA 使用了相同的简单运算，但它采用了截然不同的顺序，为了阻止密钥表攻击，四个子密钥（在加密过程中，原 128 位的密钥被拆分为 4 个 32 位的子密钥）采用了一种不太正规的方式进行混合，但速度更慢了。

在跟描述 XTEA 算法的同一份报告中，还介绍了另外一种被称为 Block TEA 算法的变种，它可以对 32 位大小任意倍数的变量块进行操作。

该算法将 XTEA 轮循函数依次应用于块中的每个字，并且将它附加于它的邻字。

该操作重复多少轮依赖于块的大小，但至少需要 6 轮。

该方法的优势在于它无需操作模式（CBC，OFB，CFB 等），密钥可直接用于信息。

对于长的信息它可能比 XTEA 更有效率。

在 1998 年，Markku-Juhani Saarinen 给出了一个可有效攻击 Block TEA 算法的代码，但之后很快 David J. Wheeler 和 Roger M. Needham 就给出了 Block TEA 算法的修订版，这个算法被称为 XXTEA。

XXTEA 使用跟 Block TEA 相似的结构，但在处理块中每个字时利用了相邻字。

它利用一个更复杂的 MX 函数代替了 XTEA 轮循函数，MX 使用 2 个输入量。

XXTEA 算法很安全，而且非常快速，非常适合应用于 Web 开发中。

TEA算法是由剑桥大学计算机实验室的David Wheeler和Roger Needham于1994年发明，

TEA是Tiny Encryption Algorithm的缩写，以加密解密速度快，实现简单著称。

TEA算法每一次可以操作64bit(8byte)，采用128bit(16byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。

为解决TEA算法密钥表攻击的问题，TEA算法先后经历了几次改进，从XTEA到BLOCK TEA，直至最新的XXTEA。

XTEA也称做TEAN，它使用与TEA相同的简单运算，但四个子密钥采取不正规的方式进行混合以阻止密钥表攻击。

Block TEA算法可以对32位的任意整数倍长度的变量块进行加解密的操作，该算法将XTEA轮循函数依次应用于块中的每个字，并且将它附加于被应用字的邻字。

XXTEA使用跟Block TEA相似的结构，但在处理块中每个字时利用了相邻字，且用拥有两个输入量的MX函数代替了XTEA轮循函数。

import struct  
  
_DELTA = 0x9E3779B9  
  
def _long2str(v, w):  
    n = (len(v) - 1) << 2  
    if w:  
        m = v[-1]  
        if (m < n - 3) or (m > n): return ''  
        n = m  
    s = struct.pack('<%iL' % len(v), *v)  
    return s[0:n] if w else s  
  
def _str2long(s, w):  
    n = len(s)  
    m = (4 - (n & 3) & 3) + n  
    s = s.ljust(m, "\0")  
    v = list(struct.unpack('<%iL' % (m >> 2), s))  
    if w: v.append(n)  
    return v  
  
def encrypt(str, key):  
    if str == '': return str  
    v = _str2long(str, True)  
    k = _str2long(key.ljust(16, "\0"), False)  
    n = len(v) - 1  
    z = v[n]  
    y = v[0]  
    sum = 0  
    q = 6 + 52 // (n + 1)  
    while q > 0:  
        sum = (sum + _DELTA) & 0xffffffff  
        e = sum >> 2 & 3  
        for p in xrange(n):  
            y = v[p + 1]  
            v[p] = (v[p] + ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))) & 0xffffffff  
            z = v[p]  
        y = v[0]  
        v[n] = (v[n] + ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[n & 3 ^ e] ^ z))) & 0xffffffff  
        z = v[n]  
        q -= 1  
    return _long2str(v, False)  
  
def decrypt(str, key):  
    if str == '': return str  
    v = _str2long(str, False)  
    k = _str2long(key.ljust(16, "\0"), False)  
    n = len(v) - 1  
    z = v[n]  
    y = v[0]  
    q = 6 + 52 // (n + 1)  
    sum = (q * _DELTA) & 0xffffffff  
    while (sum != 0):  
        e = sum >> 2 & 3  
        for p in xrange(n, 0, -1):  
            z = v[p - 1]  
            v[p] = (v[p] - ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))) & 0xffffffff  
            y = v[p]  
        z = v[n]  
        v[0] = (v[0] - ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[0 & 3 ^ e] ^ z))) & 0xffffffff  
        y = v[0]  
        sum = (sum - _DELTA) & 0xffffffff  
    return _long2str(v, True)  
  
if __name__ == "__main__":  
    print decrypt(encrypt('Hello XXTEA!', '16bytelongstring'), '16bytelongstring')

问题:

在内存管理中，“内零头”和“外零头”个指的是什么？在固定式分区分配、可变式分区分配、页式虚拟存储系统、段式虚拟存储系统中，各会存在何种零头？为什么？

解答：

在存储管理中，

内零头是指分配给作业的存储空间中未被利用的部分，

外零头是指系统中无法利用的小存储块。

• 1. 在固定式分区分配中，为将一个用户作业装入内存，内存分配程序从系统分区表中找出一个能满足作业要求的空闲分区分配给作业，由于一个作业的大小并不一定与分区大小相等，因此，分区中有一部分存储空间浪费掉了。

由此可知，固定式分区分配中存在内零头。

• 1. 在可变式分区分配中，为把一个作业装入内存，应按照一定的分配算法从系统中找出一个能满足作业需求的空闲分区分配给作业，如果这个空闲分区的容量比作业申 请的空间容量要大，则将该分区一分为二，一部分分配给作业，剩下的部分仍然留作系统的空闲分区。

由此可知，可变式分区分配中存在外零头。

• 1. 在页式虚拟存储系统中，用户作业的地址空间被划分成若干大小相等的页面，存储空间也分成也页大小相等的物理块，但一般情况下，作业的大小不可能都是物理块大小的整数倍，因此作业的最后一页中仍有部分空间被浪费掉了。

由此可知，页式虚拟存储系统中存在内零头。

• 1. 在段式虚拟存储系统中，作业的地址空间由若干个逻辑分段组成，每段分配一个连续的内存区，但各段之间不要求连续，其内存的分配方式类似于动态分区分配。

由此可知，段式虚拟存储系统中存在外零头。

详细解释

操作系统在分配内存时，有时候会产生一些空闲但是无法被正常使用的内存区域，这些就是内存碎片，或者称为内存零头，这些内存零头一共分为两类：内零头和外零头。

• 内零头是指进程在向操作系统请求内存分配时，系统满足了进程所需要的内存需求后，还额外还多分了一些内存给该进程，也就是说额外多出来的这部分内存归该进程所有，其他进程是无法访问的。

• 外零头是指内存中存在着一些空闲的内存区域，这些内存区域虽然不归任何进程所有，但是因为内存区域太小，无法满足其他进程所申请的内存大小而形成的内存零头。

页式存储管理的情况

页式存储管理是以页为单位（页面的大小由系统确定，且大小是固定的）向进程分配内存的，

例如：假设内存总共有100K,分为10页，每页大小为10K。
现在进程A提出申请56K内存，因为页式存储管理是以页为单位进程内存分配的，所以系统会向进程A提供6个页面，也就是60K的内存空间，那么在最后一页中进程只使用了6K，从而多出了4K的内存碎片，但是这4K的内存碎片系统已经分配给进程A了，其他进程是无法再访问这些内存区域的，

这种内存碎片就是内零头。

段式存储管理的情况

段式存储管理是段（段的大小是程序逻辑确定，且大小不是固定的）为单位向进程进行内存分配的，进程申请多少内存，系统就给进程分配多少内存，这样就不会产生内零头，但是段式分配会产生外零头。

例如：假设内存总的大小为100K，现在进程A向系统申请60K的内存，系统在满足了进程A的内存申请要求后，还剩下40K的空闲内存区域；这时如果进程B向系统申请50K的内存区域，而系统只剩下了40K的内存区域，虽然这40K的内存区域不归任何进程所有，但是因为大小无法满足进程B的要求，所以也无法分配给进程B，这样就产生了外零头。

请求段式存储管理是在段式存储管理的基础上增加了请求调段功能和段置换功能。
所以段式和请求段式存储管理会产生外零头

练习题

下面的内存管理模式中，会产生外零头的是(正确答案B, D)

A、页式
B、段式
C、请求页式
D、请求段式