protocol.html

/**
@page Protocol Protocol


@section Introduction Introduction
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.


@section IOTTLU Implications of the transport layer used
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.

@subsection ServicesOffered Services offered
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 @ref Limitations.

@subsection Limitations 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.


@section Packet-formats Packet formats
Framework packets consists of the five fields shown in figure @ref The-header-format.

<DIV align="center">
@anchor The-header-format
<TABLE>
<CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG>
The header format of framework packets.</CAPTION>
<TR><TD>
<DIV ALIGN="CENTER">
<IMG
 WIDTH="514" HEIGHT="86" ALIGN="BOTTOM" BORDER="0"
 SRC="images/img1.png"
 ALT="\includegraphics[%
scale=0.69]{/tmp/lyx_tmpdir15948UmioPa/lyx_tmpbuf0/_home_emanuel_DIKU_DataNet_dataNet_Report_figs_PacketHeader}">
</DIV>
<P></TD></TR>
</TABLE>
</DIV>

<P>
The main functions and formats of the fields are as follows:
<P>

<UL>
<LI>R<SMALL>ELIABLE</SMALL>: 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.
</LI>
<LI>T<SMALL>YPE</SMALL>: 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 <I>receiver</I> 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 <I>receiver</I> 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 <I>receiver</I> field in a right way.
</LI>
<LI>P<SMALL>RIORITY</SMALL>: 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.
</LI>
<LI>R<SMALL>ECEIVER</SMALL>: This field has the size and type of 1 unsigned
integer. If the value of the <I>type</I> 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 @ref 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.
</LI>
<LI>S<SMALL>EQUENCE </SMALL>N<SMALL>UMBER</SMALL>: 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. 

</LI>
<LI>D<SMALL>ATA:</SMALL> 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 @ref Limitations. The framework
expect all incoming data to be in network byte order.
</LI>
</UL>


@subsection DataFormats Data formats
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 manual<A NAME="tex2html2" HREF="#foot46"><SUP>1</SUP></A>.
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.

@section Connection Connection
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.


@subsection Handshaking Handshaking
To establish connection between a client and a game server the handshaking
protocol shown on figure @ref The-handshaking-phase is used.

<DIV ALIGN="CENTER">
@anchor The-handshaking-phase
<TABLE>
<CAPTION ALIGN="BOTTOM"><STRONG>Figure 2:</STRONG> The handshaking phase. </CAPTION>
<TR><TD>
<DIV ALIGN="CENTER">
<IMG
 WIDTH="456" HEIGHT="313" ALIGN="BOTTOM" BORDER="0"
 SRC="images/img2.png"
 ALT="\includegraphics[%
scale=0.62]{/tmp/lyx_tmpdir15948UmioPa/lyx_tmpbuf0/_home_emanuel_DIKU_DataNet_dataNet_Report_figs_HandShakingProtocol}">
</DIV>

<P></TD></TR>
</TABLE>
</DIV>

The client initiates the handshaking with a request, which is the
packet called I<SMALL>NIT </SMALL>P<SMALL>ACKET</SMALL> on figure @ref 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 I<SMALL>NIT </SMALL>P<SMALL>ACKET</SMALL> 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 D<SMALL>ISCONTINUE</SMALL>

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 I<SMALL>NIT </SMALL>P<SMALL>ACKET</SMALL> with a S<SMALL>ETUP
</SMALL>D<SMALL>ESCRIPTION</SMALL> 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 D<SMALL>ISCONTINUE</SMALL> message. If it can conform to the setup described
by the server it will reply the S<SMALL>ETUP </SMALL>D<SMALL>ESCRIPTION</SMALL> message
with a R<SMALL>EADY</SMALL> message letting the server know that the client
is now ready to receive packets from the server.

<UL>
<LI>I<SMALL>NIT </SMALL>P<SMALL>ACKET:</SMALL> The fields of the I<SMALL>NIT </SMALL>P<SMALL>ACKET</SMALL> should
have the following values: <I>Reliable</I> = 1, <I>Type</I> = 0, <I>Priority</I>
= 0, <I>Receiver</I> = 10001, <I>Sequence Number</I> = any unsigned
integer value and <I>Data</I> = any data value(s).
</LI>
<LI>D<SMALL>ISCONTINUE:</SMALL> From server to client. The fields of this packet
should have the following values: <I>Reliable</I> = 1, <I>Type</I>
= 0, <I>Priority</I> = 0, <I>Receiver</I> = 10002, <I>Sequence
Number</I> = any unsigned integer value and <I>Data</I> = any data value(s).
</LI>
<LI>S<SMALL>ETUP </SMALL>D<SMALL>ESCRIPTION:</SMALL> <I>Reliable</I> = 1, <I>Type</I> = 0,
<I>Priority</I> = 0, <I>Receiver</I> = 10003, <I>Sequence Number</I>
= any unsigned integer value and <I>Data</I> = 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.
</LI>
<LI>D<SMALL>ISCONTINUE:</SMALL> From client to server. The fields of this packet
should have the following values: <I>Reliable</I> = 1, <I>Type</I>
= 0, <I>Priority</I> = 0, <I>Receiver</I> = 10004, <I>Sequence
Number</I> = any unsigned integer value and <I>Data</I> = any data the
client wishes the framework to deliver to the game on the server.
</LI>
<LI>R<SMALL>EADY:</SMALL> <I>Reliable</I> = 1, <I>Type</I> = 0, <I>Priority</I>
= 0, <I>Receiver</I> = 10005, <I>Sequence Number</I> = any unsigned
integer value and <I>Data</I> = no data.
</LI>
</UL>

@subsection States States
On figure @ref 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.


@subsection HeartBeats Heartbeats
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 @ref 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 <I>Reliable</I> = 1, <I>Type</I> = 0, <I>Priority</I>
= 0, <I>Receiver</I> = 30001, <I>Sequence Number</I> = any sequence
number will do.


@subsection CloseDownConnection Close down of connection
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.


@section Guarantees Guarantees

@subsection Guarantees-packets packets
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 @ref The-reception-of.
Sending packets unreliably guarantees that the packet will be delivered
at most once.
To send a packet unreliably the <I>Reliable</I> field of the packet
header should be set to 0.


<DIV ALIGN="CENTER">
@anchor The-reception-of
<TABLE>
<CAPTION ALIGN="BOTTOM"><STRONG>Figure 3:</STRONG>
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.</CAPTION>
<TR><TD>
<DIV ALIGN="CENTER">
<IMG
 WIDTH="476" HEIGHT="50" ALIGN="BOTTOM" BORDER="0"
 SRC="images/img3.png"
 ALT="\includegraphics[%
scale=0.82]{/tmp/lyx_tmpdir15948UmioPa/lyx_tmpbuf0/_home_emanuel_DIKU_DataNet_dataNet_Report_figs_UreliableDiscard}">
</DIV>
<P></TD></TR>
</TABLE>
</DIV>



@subsection Reliablepackets Reliable packets
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.



<DIV ALIGN="CENTER"><A NAME="130"></A>
<TABLE>
<CAPTION ALIGN="BOTTOM"><STRONG>Figure 4:</STRONG>
The buffering of reliable packets. Reliable packets are buffered
until they are ready for delivery to ensure they are delivered in
the right order.</CAPTION>
<TR><TD>
<DIV ALIGN="CENTER">
<IMG
 WIDTH="480" HEIGHT="82" ALIGN="BOTTOM" BORDER="0"
 SRC="images/img4.png"
 ALT="\includegraphics[%
scale=0.82]{/tmp/lyx_tmpdir15948UmioPa/lyx_tmpbuf0/_home_emanuel_DIKU_DataNet_dataNet_Report_figs_RealiableNoDiscard}">
</DIV>
<P></TD></TR>
</TABLE>
</DIV>

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 <I>Reliable</I>
should be set to 1.



@subsubsection Acknowledgements Acknowledgements
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 @ref 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.


<DIV ALIGN="CENTER">
@anchor Format-of-an
<TABLE>
<CAPTION ALIGN="BOTTOM"><STRONG>Figure 5:</STRONG>
Format of an acknowledgement packet. Only
the fields filled out will be used - the rest of the fields are ignored
by the framework.</CAPTION>
<TR><TD>

<DIV ALIGN="CENTER">
<IMG
 WIDTH="474" HEIGHT="57" ALIGN="BOTTOM" BORDER="0"
 SRC="images/img5.png"
 ALT="\includegraphics[%
scale=0.85]{/tmp/lyx_tmpdir15948UmioPa/lyx_tmpbuf0/_home_emanuel_DIKU_DataNet_dataNet_Report_figs_AckPacket}">
</DIV>

<P></TD></TR>
</TABLE>
</DIV>


@subsubsection Timeouts Timeouts
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
<A NAME="tex2html7" HREF="#foot142"><SUP>2</SUP></A> 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.

@subsection Queues
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 @ref Packet-formats), then
we look at the ID of the receiving object (receiver on figure @ref 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.


@subsection SequenceNumbering Sequence numbering

@subsubsection Unreliable-Packets Unreliable packets
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
@ref Unreliable-Packets where we guaranteed at-most-once delivery for
unreliable packets sent with the same priority. 

@subsubsection ReliablePackets Reliable packets
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 @ref sequenceno. The clients use the same
sequencing scheme, however the clients only have one ``client''
which is the server.

<P>

<DIV ALIGN="CENTER">
@anchor sequenceno
<TABLE>
<CAPTION ALIGN="BOTTOM"><STRONG>Figure 6:</STRONG>
Reliable packets are given a sequence number
depending on the priority they have and the client they are destined
for.</CAPTION>
<TR><TD><IMG
 WIDTH="542" HEIGHT="83" BORDER="0"
 SRC="images/img6.png"
 ALT="\begin{figure}\begin{center}\begin{tabular}{\vert&gt;{\raggedright }p{1.8cm}\vert&gt;{...
...&amp;
...&amp;
150485\tabularnewline
\hline
\end{tabular}\end{center}\par\end{figure}"></TD></TR>
</TABLE>
</DIV>

@subsubsection SequenceNumberWrap Sequence number wrap
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.


<HR>
<H4>Footnotes</H4>

<A NAME="foot46"></A><A
 HREF="#tex2html2"><SUP>1</SUP></A> http://www.cplusplus.com/doc/tutorial/variables.html

<A NAME="foot142"></A><A
 HREF="#tex2html7"><SUP>2</SUP></A> Precision here meaning the number RTTs to calculate the average on.

*/

---