Peer-to-peer networking in BaroNET is a reality. A system has been created whereby two servers can connect and transmit necessary information between themselves. The architecture has been designed such that adding servers is a very easy task.
At this point, the servers do not control particular regions of the map, due to the significant modification to the map format which has not yet been finished. At this point, each server essentially "mirrors" the information on the others, which is a useful test in itself (i.e., testing the latency between servers which are logically very close to each other).
In an effort to make motion appear smoother, work has occured on speculative motion, which allows client computers to anticipate movement by other clients. Since some network connections, even direct connections, will naturally have higher latency than others, this will reduce the "jerkiness" or "jitter" caused by connections which receive packets at varying rates or in a "burst" pattern.
To achieve the objectives of the Wombat ConsortiumTM Virtual Reality
Gaming Environment, it has been necessary to develop a network protocol and
database system to transmit and store information vital to the game world.
As of December 19th, a major portion of our effort has been directed to ensuring
high-quality network interaction between multiple MargalisTM clients
on the same network; additionally, extensible bases for server architecture,
data transaction, message passing, information storage, and security have
been implemented. Finally, plans and a test-implementation of
bneth, an interpreter for a Scheme-like language, have been developed.
The overarching structure of the BaroNET network is client-server; this is done to avoid n2 transmission were each client to communicate with the others directly. However, the structure of the server is highly-threaded, so most efficient use of system resources can be made.
When a client opens a connection with a particular server, the connection engine of the server spawns a new thread, which I will term a co-client hereafter. This co-client is responsible for communicating directly with the client and sending requests to the server kernel to manipulate the database and send information to other co-clients which may correspond to clients in close proximity.
This particular co-client/kernel architecture was also employed to avoid
the problems inherent in building a serializable database with which the
various clients would communicate directly; since the BaroNET is intended
to be a large network of servers, each controlling a relatively small area,
the load of each server should be acceptable in this configuration.
This policy will be reviewed as time progresses, in case the situation or
our objectives change.
The network protocol used in both the Margalis client and in the BaroNET daemon is derived from the same source code. The underlying structure is based on Windows sockets; the source code architecture is object-oriented to hide the implementation details.
When a client wishes to contact a remote BaroNET server, it creates a new instance of the bnSocket class, which then initiates the connection using a stream socket and spawns two threads to control incoming and outgoing traffic, respectively. The socket object architecture is optimized for efficiency: there is no spin-locking, as both the incoming and outgoing threads will block until data is ready to be received or transmitted.
Data transmitted over the network is a stream which is organized into logical packets. Each logical packet consists of a 4-byte integer length and a corresponding byte stream of that length. Internally, the program keeps track of packets using a bnPacket object which contains the length and byte stream, among other data.
When the bnSocket is created and a connexion is established, the incoming data thread blocks using a select call on the associated socket. Once data is available, the thread is reactivated by the Windows kernel and proceeds to download as much information as is available in the socket, organizing the logical packets into explicit packets and placing them on the incoming data queue to be delivered to the main program. Once no more information is available, the thread again calls select to wait for more incoming data.
The outgoing data thread blocks on a semaphore which is signalled whenever a new packet is added to the outgoing queue by the main program. When the semaphore is signalled, the thread wakes up and enters a select-send loop in which the thread calls select to wait for a free output stream and then sends as much data as possible until the output stream is saturated; this loop is repeated until there are no more packets available to send, whereupon the outgoing thread again blocks on the semaphore. Once a packet has been sent completely, it is removed from the outgoing queue and subsequent packets are then sent.
In order to keep event-driven main programs from spinning on waiting for data to be delivered, each bnSocket object can be associated with a semaphore which is signalled whenever a new packet is ready to be delivered; this can be used to wake up the main thread whenever new data is waiting to be processed. Since any bnSemaphore can be used for this purpose, it can also be shared by other threads which also notify the main thread of events, allowing the main thread to block whenever no information is available to be processed.
Initially, the sockets hierarchy was not event-driven; it used spin-locking almost exclusively, which led to a rapid degradation of system resources almost immediately upon execution of any program using the subsystem. This was eventually changed, through some evolution, to the system currently employed. In reality, the output stream almost never overflows its buffer, so an output thread is probably not necessary; thus, although the performance of the network interface is exemplary in our limited testing scenarios, if the extra threads are seen to interfere greatly with server performance in the future, this feature will be reviewed.
Owing to the complexity of games based on this Wombat engine, the BaroNET
gaming protocol is designed to operate on high-speed networks only; while
this is currently a problem for most end-users, since modems are far too
slow, we are depending on the advancement of technology to the point where
end users will have high-speed connections.
Since the server is based on a co-client/kernel model, a message passing interface between the co-clients and the kernel is necessary to facilitate retrieval of information from the database and transmission of data between clients. The message passing interface (MPI) is based on the STL container queue and a Windows semaphore. Essentially, a thread with access to another thread's incoming message queue simply creates a message and pushes it onto the queue.
Messages are derived from the class bnMessage; this architecture is fully extensible, since each message passing queue (MPQ) simply passes pointers to messages, so the subtyping data is preserved; furthermore, each message is associated with an integer denoting the type of message (possibly a 1 to 1 map between bnMessage subtypes and integers, but not necessarily) and accessed using the virtual function bnMessage::Type(), so information about the class is available even in the absence of standard C++ subtyping data.
New message types must conform to some technical specifications regarding certain overloaded functions; once they conform to these specifications, however, they can contain any additional information required or desired. A thread creates a message m by allocating space on the heap (m=new X, where X is a subclass of bnMessage) and then sending the message by calling Y.Send(m), where Y is the desired MPQ. This places the message pointer on the queue.
When the receiver next checks the MPQ, it will find a new packet (or more specifically, a new packet pointer). It reads the new packet pointer using the function Y.Recv(m), and when it is done with the message m, disposes of it using the function Y.deleteMsg(m).
Since the MPI is such a convenient abstraction, it was also incorporated as the primary high-level interface for network communication. A subtype of bnMessage, bnMessageOS, is derived for all pertinent classes which must be sent over the network. Five functions used for encoding classes into octet streams and decoding octet streams into classes are then overloaded for each relevant class and linked together in a technical way beyond the scope of this document. This architecture is one implementation of a generic object encoder, and greatly facilitates the efficient transmission of object data over the network.
Messages are sent over the network using a static function
bnMessageOS::Send(skt,m), where skt is a bnSocket instance
and m is a bnMessageOS instance; messages are then received using
the static function bnMessageOS *bnMessageOS::Recv(skt) and decoded
using a program-specific loop which first divines the original class instance
by examining the bnMessageOS::Type() information and then hands further
action off to the specific class decoder. The received, encoded message,
when no longer needed, is destroyed using delete.
A database, designed to store any information needed by the game world, has
been designed to operate in the most efficient manner possible. Multiple
databases, perhaps to store different types of data, are possible, each based
on a similar structure:
|
|
The database is intended primarily to store encoded object data, which can be retrieved by the kernel and distributed to co-clients as necessary. Our motivation for using this structure is simple: BTrees minimize disk access, one of the major bottlenecks in any database. Furthermore, an extensible caching subsystem (epitomized by the object bnCache) based on the LRU (least-recently-used) algorithm has been implemented which can be used to cache arbitrary amounts and kinds of information from a particular series of files to reduce disk access to a minimum.
The client-server architecture we are attempting to employ tries to avoid most privileged-client-request structures in favor of a system in which the server controls access to the data intelligently. As will be covered in the security section, this is done mainly to avoid abuse of the system by overzealous players with too much computer experience.
Thus, in principle, a client does not "add information to the database;" rather, it makes its co-client aware of any changes in game status, which the server can then verify (if possible or necessary) and then input into the database. The co-client adds information to the database by tagging the data with a key (consisting of a major and minor number, a 64-bit combination), setting its revision number to 0, and sending an "add-to-database" message to the kernel. A co-client can update information in the database by sending an "add-to-database" request for a key which already exists in the database; however, before doing this, it must update the revision number.
A client which needs information about a particular area can send a request to the co-client to gather such information from the database. If the co-client deems this necessary, it can send a request to the kernel to gather the information from the database. If the client is requesting an update for certain information, it sends its old revision number along with the key requested; if the kernel sees that the old revision number matches the one in the database, it does not send this information to the co-client for transmission to the client, because that entry in the database has not been updated. If the revision number has changed, then the new information, including the new revision number, is transmitted.
The client ideally should never block on receiving data, because the co-client
can deny a request for such data. There are limited times, however,
in which the client must block: if, for instance, a user does an unpredicted
teleport from one location to another, it must wait for all local terrain
and object data to be transmitted before a screen in the new location can
be rendered; thus, in this case it must block, but it is assumed that the
co-client will grant a request of this kind for any correctly-operating client.
Security is a problem in any network game. Judging from the abuse done to the DiabloTM server by elements seeking to aggrandize themselves, apparently to enforce an artificial social order on that world's inhabitants, it was deemed necessary to provide the highest level of security possible to ensure that the security of privileged system commands would not be compromised.
One of the ideas we will attempt to implement is a variation on probabilistically-correct proofs. The idea here is for the server to periodically make requests for certain data which depend on the correctness of the client, and reject clients which do not pass these tests. Although this method is not foolproof, it will make hacking the client program extremely difficult.
Since it is possible, however unlikely, to modify the client in a way which escapes notice of the server, some commands will be protected. Whenever a system operator signs on, he will be required to enter a password, which will be retained by the client for the duration of the session. Each time the client attempts to perform a privileged command, the client will request a 64-bit RSA key from the server. The server will generate such a key and send it to the client. (In reality, new keys may be generated only every couple of minutes; this decreases server load, since a 64-bit RSA key is unlikely to be broken in a few minutes.) The client will encrypt the password and send it to the server along with the request, whereupon the server will perform the request if the client's password is correct.
Examples of privileged commands include: teleport (moving instantaneously to a remote location in the world), kill (causing the death of an animate), and eject (removing a player temporarily from the game). Security is obviously necessary in the presence of such commands.
One additional measure, difficult to thwart, is to simply update the client often, and change underlying protocols sufficiently to prevent reverse-engineering. One method which has been suggested is to update the client every couple of days, which should not be a problem on a high-speed network. When the client contacts the server to enter the game, the client will be updated if its last-modification date does not match that of the server. The client will spawn an update service client which will download the new Margalis executable and support files, and then re-load Margalis.
Since it is clearly possible to modify the client program to prevent download and to "trick" the server into thinking the client is up-to-date, the underlying network protocols can be changed often and enough that older clients are simply incompatible with the newer ones. Further, the addition of code to a Windows executable is a daunting task that even the most experienced of hackers would find challenging; to exploit this, we could add code which requires that "pings" of different kinds be sent every few seconds or minutes, the absence of which would warn the server that an incorrect client was attempting to communicate.
Since even the best hacker needs to be able to test his code, we can perform
the most draconian measure of all: the dreaded expulsion. If the server
notices that an incorrect client is trying to communicate with the server,
Big Brother will warn the offending user once; upon his second deviation,
he will be expelled permanently from the game and his registration
revoked. It will not be possible to play on a server without a
registration, since all character information will be contained there.
In order to facilitate the rapid expansion of the game logic without requiring constant recompilation and the necessary loss of continuity which that requires for players, most of the game logic will be written in a Scheme-like language called bneth. Although the details of Scheme interpreters are beyond the scope of this document, the environment model is fairly easy to describe.
An environment consists of a series of frames. There is a top-level frame which contains bindings from top-level variable names to data and which has no parent; subsequent frames also contain bindings from variable names to data, but also have parent frames whose data are also avaiable to objects with access to those frames, thus facilitating the idea of scope.
For example, the following code fragment:
(let* ((a 5)
(b (fun (a) (+ a 1))))
(b 2))
would produce a frame X containing the bindings a:5 and b:(fun...). Furthermore, when (b 2) is evaluated, a new frame Y is created, whose parent is X, and where the parameter a is bound to 2. Thus, when the expression (+ a 1) is evaluated, a is bound to 2 -- not 5 -- in Y, since the closest binding is used, and thus the expression evaluates to 3 instead of 6.
Garbage collection is an issue with any LISP or Scheme-like language.
Reference counters cannot be used in Turing-complete versions, since cycles
among frames can occur; thus, a method of cycle-detection or some other type
of garbage collection must be used. R&D into this is occuring at
this time.
Only time will tell what will become of this project. Although the code written to date is quite extensible by design, much work remains to be done before this game will be considered "finished." I accomplished more this semester than I had hoped, having started programming the Scheme-interpreter which was not scheduled until the winter break.
Next semester I hope to implement secure protocols and peer-to-peer interaction among servers, in addition to actually getting the server to do something other than simply passing messages around between clients. Will this project ever be "done"? It seems that our expectations grow at a faster rate than our code.
Kyle Rose
Friday 19 December 1997