Our framework is built on top of the UDP protocol. By doing this we are able to make use of this protocol's error detection service. But in order to offer the services we wish to we need to build some additional services on top of the UDP protocol. We will in this part of the report give a description of these services.
As described in the report we have chosen to build our framework on top of the UDP transport layer protocol. This choice has the following implications on the building of our framework.
UDP offers no guarantees other than error detection but does have a low header overhead and allows us to build on top of it with almost no restrictions except those described in section Limitations.
We have no flow control, congestion control, reliability or error correction. Furthermore the limit on a UDP datagram's size is 65507, or 64K-8-20. 8 for the UDP packet header and 20 for the IP-headers. This puts a restriction on the size of data sent with this protocol in one packet to 65507 bytes.
Framework packets consists of the five fields shown in figure The-header-format.
Figure 1: The header format of framework packets.
|
|
The main functions and formats of the fields are as follows:
-
RELIABLE: This field has the size and type of 1 byte or 8 bits. This field decides whether or not the packet should be sent reliable. If the value of this field is 1-255 reliable transfer should be used. Reliable transfer means that delivery of this packet is required. If the value is set to 0 this packet will be sent unreliable.
-
TYPE: This field has the size and type of 1 byte. This lets us know what kind of object the receiver is. If the value is zero it is a system packet intended for the framework. What the framework is to do with this packet will be decided by the receiver field. If the values of this field is set to 1 the packet is intended for a plug-in. Which plug-in the packet should be delivered to is decided by the receiver field. If the value of the field is 2 this packet is a create-object-packet. If the value is 3 the packet is a destroy object packet. Values from 4-255 can be used in any way the user of the framework wishes. This field will not make any sense to the framework unless it is combined with the receiver field in a right way.
-
PRIORITY: This field has the size and type of 1 byte. Decides which priority the packet should be given. 0 for highest and 255 for lowest priority - any number between 0 and 255 can be used. An example of queue is that a packet with a priority of 0 is put in the very front of the queue - or at least right after all the other priority 0 packets. The dispatcher at the receiving end grabs the priority 0 packet as soon as it realizes that such a packet exists in the in-queue.
-
RECEIVER: This field has the size and type of 1 unsigned integer. If the value of the type field is between 4 and 255 this field lets the framework know which data object to deliver the packet to. If the value of the type field is 0, meaning this packet is a system packet, the value of the receiver field has the following meanings: 10001 means that this a handshake initialisation packet sent from a client to server requesting the server to connect. 10002 is one of two replies the server framework can give the client on this initial request. 10002 means that the client is not welcome to connect to the server. 10003 is the second possible reply to 10001
- a value of 10003 means that this packet contains a description of the server framework setup. To a 10003 message the client can reply in two ways. With a 10004 message which lets the server know that the client framework cannot conform to the setup of the server and will disconnect. A 10005 message means that the client can match the setup of the server and that it is now ready to receive packets. For more information on the handshaking procedure please see section Handshaking. A value of 20001 is used for acknowledgement packets and finally a value of 30001 is used for framework heartbeats allowing the client framework to stay connected with the server framework.
-
SEQUENCE NUMBER: This field has the size and type of an unsigned integer. Sequence numbers are assigned in increasing order to all packets. They are assigned by priority meaning that each priority have their own channel. For reliable packets they are further more assigned by the client, so the receiving client has a chance of knowing which sequence number to expect next for a given priority.
-
DATA: The data segment may contain all types of data. However the maximum size of the data segment is 65496 bytes since 12 bytes are used by the framework packet header; therefore we get 65507-12. 65507 is the number deduced in section Limitations. The framework expect all incoming data to be in network byte order.
All data received by the framework will be expected being in network byte order and the framework will make sure to convert it into host byte order before delivering it. The fundamental data types are those used in the C++ programming language which are described in the C++ reference manual1. All data sent from the framework are also sent in network byte order.
The maximum size of a framework packet is limited to 65507 (header included) due to the use of UDP as the underlying transport layer.
Although the GaNeF protocol is built on top of the UDP protocol it is not connectionless. Connection between client and server is established, maintained and closed down. This section will go through the various phases of the client/server connection.
To establish connection between a client and a game server the handshaking protocol shown on figure The-handshaking-phase is used.
Figure 2: The handshaking phase.
|
The client initiates the handshaking with a request, which is the packet called INIT PACKET on figure The-handshaking-phase. It is possible for the game developer to send some data along with this initial request - this data is what we call tagalong on the diagram and the framework will ask the game for this data. Such data could for instance be the client's user name and password which would then be delivered to the game at the server side of the framework along with the initial packet. The server can reply to the INIT PACKET in two ways. The first is by telling the client that it is not possible for it to connect to this server at this time; this message is the first DISCONTINUE
message shown on the figure (again it is possible for the game developer to send some data along with this message). If the server accepts the client it will reply the INIT PACKET with a SETUP DESCRIPTION packet containing a description of the server's setup. The client can reply to this message in one of two ways. If it cannot conform to the description given by the server it will reply with a DISCONTINUE message. If it can conform to the setup described by the server it will reply the SETUP DESCRIPTION message with a READY message letting the server know that the client is now ready to receive packets from the server.
-
INIT PACKET: The fields of the INIT PACKET should have the following values: Reliable = 1, Type = 0, Priority = 0, Receiver = 10001, Sequence Number = any unsigned integer value and Data = any data value(s).
-
DISCONTINUE: From server to client. The fields of this packet should have the following values: Reliable = 1, Type = 0, Priority = 0, Receiver = 10002, Sequence Number = any unsigned integer value and Data = any data value(s).
-
SETUP DESCRIPTION: Reliable = 1, Type = 0, Priority = 0, Receiver = 10003, Sequence Number = any unsigned integer value and Data = the first unsigned int of the data field should tell the client how long the server will wait before the client will be disconnected. That is, this value tells the client at which rate it should send heart beats. The next value should also be an unsigned int. This integer tells the client how many unique plug-in IDs it should read from the packet. The next values read from the packet will be plug-in IDs of type unsigned integer. Any data after the plug-in IDs will be considered data sent from the client game to the game engine running on the server and will therefore be forwarded to the server framework's game.
-
DISCONTINUE: From client to server. The fields of this packet should have the following values: Reliable = 1, Type = 0, Priority = 0, Receiver = 10004, Sequence Number = any unsigned integer value and Data = any data the client wishes the framework to deliver to the game on the server.
-
READY: Reliable = 1, Type = 0, Priority = 0, Receiver = 10005, Sequence Number = any unsigned integer value and Data = no data.
On figure The-handshaking-phase we see a description of the states the client enters as the handshaking phase evolves. These are states used and maintained inside the framework Mainly for the server and client to know in which way to handle the packets on their incoming socket.
After the connection has been established the connection needs to be maintained. This is done by the client sending heartbeats to the server. As mentioned in section Handshaking the server will disconnect the client if it has not heard anything from it during the period of time stated in the SETUP DESCRIPTION message. In this implementation the client sends heartbeats to the server after half of that period of time has passed. The syntax of a heart beat packet is Reliable = 1, Type = 0, Priority = 0, Receiver = 30001, Sequence Number = any sequence number will do.
When a client wishes to disconnect it can just stop sending packets to the server. When this happens the server will timeout the client and disconnect then it. This also means that if the game developer wishes to send some data from the client to the server on disconnect, he has to do so explicitly; that is, he cannot do it by sending a message along with any disconnect message sent between the frameworks as he was able to during the connection establishment.
Our framework makes no guarantee on delivery when packets are sent unreliably. It works by best effort and sends unreliable packets by UDP. However, it does guarantee that the unreliable packets which arrives in the other end are delivered in the order they were sent. Packets arriving out of order on the receiving side are simply discarded. Please see figure The-reception-of. Sending packets unreliably guarantees that the packet will be delivered at most once. To send a packet unreliably the Reliable field of the packet header should be set to 0.
Figure 3: The reception of unreliable packets at the receiver. The number indicates a packet's sequence number. Packets marked with an arrow will be discarded on the receiving side since they arrive out of order.
|
|
Our framework can guarantee delivery of packets if they are sent reliably. When packets are sent reliable It also guarantees that the packets are delivered in the same order as they were sent. Sending a packet reliable also means that the packet is guaranteed to be delivered exactly once at the receiving side.
Figure 4: The buffering of reliable packets. Reliable packets are buffered until they are ready for delivery to ensure they are delivered in the right order.
|
|
This is done by storing packets temporarily in a buffer until all preceding packets have been received. When all these packets have been received the packets waiting are marked as being ready for delivery and thereby delivered when the main loop of the game is ready for this. To send a packet reliably the packet header field Reliable should be set to 1.
Whenever the framework receives a reliable packet it lets the sender know that is has received this packet by sending by an acknowledgement. An acknowledgement packet has the format shown on figure Format-of-an. In our implementation acknowledgement packets are sent unreliable. This can be done so because if the acknowledgement packet is lost during transfer the sender of the original reliable packet will notice this and resend the packet. In this case we can re-acknowledge the packet. Also, if we sent the acknowledgement packet reliable we would enter a never-ending loop where acknowledgement packets are acknowledged with acknowledgements which again are acknowledge with acknowledgements and so forth.
Figure 5: Format of an acknowledgement packet. Only the fields filled out will be used - the rest of the fields are ignored by the framework.
|
A possibly lost packet is discovered by the framework by timeouts. All packets sent reliable are given a timeout. The timeout is calculated as the average round trip time (RTT) multiplied by a factor chosen by the game developer. A RTT is the time passed from when a reliable packet has been sent until we have received its acknowledgement. The calculation of the average timeout is done with a precision 2 decided by the game developer. When a timeout occurs the packet in question is resent by the framework. Please note that no negative acknowledgements are sent back to the game.
At both the sending and the receiving side we maintain queues. At the sending side for packets waiting to be sent and on the receiving side for packets waiting to be delivered. These queues are implemented in such a way that hey have influence on in which order packets are sent or delivered. Firstly packets which the lowest priority are sent/delivered first. Then we we look at the sequence number of the packet, then the type (this means that e.g. system packets are sent/delivered before other types of packets, see section Packet formats), then we look at the ID of the receiving object (receiver on figure The-header-format) and finally we look at how this packet is to be sent to (client ID) this last check is only relevant on the server since this last values always will be the same on the clients, namely 0. This scheme means that we cannot allow packets with different priority to use the same sequencer since this would cause the packets to be delivered out of order (because high priority packets are delivered first. Therefore we maintain a channel for each priority so that each priority is given its own sequencer. Furthermore, on the server side each client is also given its own sequencer.
We also allow for unreliable packets to be replaced by newer packets in the queue. This will happen if an unreliable packet arrives at the queue with the same priority, type, receiver and client ID as an existing. If this is the case, we assume that this packet is a newer update of the same type to the client in question - this is valid for both in- and out-queues. The sequence number is irrelevant in this, since unreliable packets are given a sequence number the moment they are sent, and therefore all have the same sequence number when in the out-queue.
All unreliable packets sent by the framework with the same priority share the same sequencer. For every unreliable packet sent the unreliable sequence number is increased by one. For the server this means that if it sends an unreliable packet with sequence number J to client X with priority U, the next unreliable packet it will send will have sequence number J+1 - if this packet is also sent to client Y and has priority U. This conforms with the description given in section Unreliable packets where we guaranteed at-most-once delivery for unreliable packets sent with the same priority.
The scheme for reliable packets is a little more complex. The server assigns sequencers to the clients in the following way. For each priority a packet can have it receives on sequencer. This means that each client are assigned 256 sequencers for priority 0 through 255. So at any given time each of the priorities may have a different sequence number as shown on figure sequenceno. The clients use the same sequencing scheme, however the clients only have one ``client'' which is the server.
Figure 6: Reliable packets are given a sequence number depending on the priority they have and the client they are destined for.
|
|
As the framework is implemented wraps are not handled. Wraps occur when sequence numbers become too large to fit within the data type they are represented with. For sequence numbers in the framework, which are represented by unsigned integers, their maximum value is 4,294,967,295. This means that the framework can send 1000 packets per second before the sequence number wraps after 49.7 days given that the same priority and reliability is used for all packets - in our framework this would lead to a in communication since lower sequence numbers are not accepted. If we assume that all priorities are used equally, the number of days is 12725.8 before the first sequence number wraps.
Footnotes
1 http://www.cplusplus.com/doc/tutorial/variables.html
2 Precision here meaning the number RTTs to calculate the average on.
Generated on Mon Feb 6 12:24:58 2006 for Ganef by
1.4.4
