meta data for this page
  •  

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
courses:ct30a5002:assignment2 [2013/11/22 13:53]
julaakko [Virtual machine usage]
courses:ct30a5002:assignment2 [2014/12/02 17:36] (current)
julaakko
Line 1: Line 1:
 +Updates:
 +> 07.11.13: Additional return instructions and fixed link to paper + QIII unlagged link
 +> 20.11.13: Virtual machine instructions
 +> 21.11.13: Virtual machine instructions revised
 +> 22.11.13: Two different ways to use the virtual machines and additional notes for using it. Moved virtual machine instructions to page bottom.
 +> 22.11.13: Fixed link to Quake III Arena Game Structures paper.
 +> 18.11.14: Deadline + 1 week
 +> 02.12.14: Added link to Q3/ioquake3 academic articles
 +
 +====== Assignment 2 - EXTENDED DEADLINE 9.12.14 @ 10:00 (was 2.12) ======
 +
 +This assignment is about understanding others code while analyzing its operation. We've selected two fairly old examples, which are still in development;​ [[http://​ioquake3.org/​|ioquake3]],​ an open implementation of Id software'​s Id Tech 3 FPS engine and [[http://​freeciv.wikia.com/​wiki/​Main_Page|Freeciv]],​ an open implementation of strategy game Civilization (compatible with Civilization 2).
 +
 +In this assignment you'll have to look into the sources of both and to answer the questions and to think about the solutions. You are free to use any code analyzing software to help you in this work. Or do it from commandline by searching function usage, e.g., in source root <code bash>​find * -type f -exec grep -s -n -e "​function_call"​ {} +</​code>​
 +
 +===== Getting the source codes =====
 +
 +Source codes of both are publicly available from their source code repositories and many Linux distributions offer them too. The benefit of distribution provided sources are that from these you can build packages that can be easily installed. E.g. with Debian based distributions you can do this by running in the source code root directory: <code bash>​dpkg-buildpackage -rfakeroot -b -uc</​code>​
 +
 +==== ioquake3 ====
 +
 +ioquake3 source code is available on many Linux distributions,​ e.g. on Debian based systems you can get it simply: (**no superuser needed**)<​code bash>​apt-get source ioquake3</​code>​ In order to build the code you must install some libraries, with Debian based systems it is easy (as **superuser**):​ <code bash>​apt-get build-dep ioquake3</​code>​ But because of the licensing issues, in Debian/​Ubuntu the ''​zlib''​ library has been removed from the source, it might be more fluent to get the code from the git repository of ioquake3. To do this you'll need to first install git, on Debian based systems (as **superuser**):<​code bash>​apt-get install git</​code>​ And then get the code:<​code bash>git clone https://​github.com/​ioquake/​ioq3.git</​code>​ This will create a folder ''​ioq3''​ under the current working directory. The build-dependencies can be installed as for the sources provided by your Linux distribution.
 +
 +The code complies with plain ''​make''​ when you've installed the build-dependencies. For more details see the ''​README''​ in the git-sources.
 +
 +==== Freeciv ====
 +
 +Freeciv source code is available on many Linux distributions,​ e.g. on Debian based systems you can get it simply: (**no superuser needed**)<​code bash>​apt-get source freeciv</​code>​ In order to build the code you must install some libraries, with Debian based systems it is easy (as **superuser**):​ <code bash>​apt-get build-dep freeciv</​code>​In order to compile the code:<​code bash>​./​configure # in this case make runs this too - so not necessary
 +make</​code>​
 +
 +The sources might be outdated in some distributions,​ therefore, you can get the most recent ones from their SVN:<​code bash>svn checkout http://​svn.gna.org/​viewcvs/​freeciv/​trunk/​ freeciv</​code>​ Install the same dependencies as for the sources provided by your Linux distribution and compile with same instructions.
 +
 +===== The assignment tasks =====
 +
 +This assignment gives a total of 15 points. In following subsections the different tasks are specified. Some tasks are common for both sources (A. and D.) and some are source specific (B. and C.).
 +
 +==== A. Common assignment tasks (6p) ====
 +
 +These tasks are to for both sources.
 +
 +=== 1. The basic networking analysis (2p) ===
 +  * How the connection establishment works? Draw a MSC diagram of the connection procedure.
 +  * How the client activity is being checked at the server?
 +=== 2. Connection characteristics (2p) ===
 +  * How the connection characteristics are checked? ​
 +  * What connection characteristics are analyzed/​utilized?​
 +  * What kind of optimization techniques are used for packets that are sent? 
 +=== 3. Game states (2p) ===
 +  * What the game states sent to clients contain?
 +  * How these game states are being sent to clients?
 +  * How are the states being kept synchronized?​
 +
 +----
 +
 +==== B. ioquake3 assignment tasks (4p) ====
 +
 +These tasks are for ioquake3 source
 +
 +=== 1. What is the built in lag in quake3/​ioquake3 servers? (1p) ===
 +=== 2. How does the countermeasures for UDP spoofing attacks work? (1p) ===
 +=== 3. How does the client side prediction work? (2p) ===
 +
 +==== C. Freeciv assignment tasks (2p) ====
 +
 +These tasks are for Freeciv source.
 +
 +=== 1. Turn based communication (1p) ===
 +  * How the turn based approach works in Freeciv? How the progression of turns happens?
 +  * What kind of issues it can have with TCP connections?​
 +  * Draw a MSC diagram of an example situation.
 +=== 2. Server searching (1p) ===
 +  * How does the server searching work in Freeciv?
 +  * How it differs from the Quake3/​ioquake3 approach?
 +
 +----
 +
 +==== D. Own ideas (3p) ====
 +
 +=== 1. How would you implement the lag compensation into ioquake3 sources? (2p) ====
 +  * It is required to explain this with pseudo code and text. However, we do not restrict if you want to implement that into the sources.
 +  * NOTES:
 +    * It has been implemented to, e.g. [[http://​urbanterror.info|Urban Terror]] (an independent open source FPS, similar to Counter Strike) [[https://​github.com/​Barbatos/​ioq3-for-UrbanTerror-4|ioquake3 based engine]] and to [[https://​github.com/​zturtleman/​spearmint|Spearmint fork of ioquake3]]. ​
 +    * [[http://​www.ra.is/​unlagged/​|A helpful documentary of lag compensation implementation in Quake3]]. If you do not know how the lag compensation could be implemented use this example and write your solution based on it (1p), if you want a second point for this task, write a (brief) analysis about this solution (why it is good/bad).
 +
 +=== 2. Freeciv into "​RTS"​ (1p) ===
 +  * If the Civilization type games were made into RTS (Real Time Strategy) games, where turns happen in real time, what would have to be done for the existing implementation relying on TCP? What restrictions and challenges would it bring?
 +    * Do not think about the gameplay too much, focus on the networking.
 +  * You can get some ideas from [[http://​www.gamasutra.com/​view/​feature/​3094/​1500_archers_on_a_288_network_.php|1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond]].
 +
 +=== 3. Own contribution / bug fix (extra 1-3p) ===
 +  * If you notice that something is missing from the sources or you'd like some feature to be enhanced in some direction (or even new feature to be implemented) from the networking point of view additional point(s) can be given.
 +  * If you clearly see a bug that has not been reported - commit a bug report (or even fix it!) and points will be given.
 +===== What sources to look at =====
 +
 +To ease the workload, here are some hints you could use while doing this assignment. ​
 +
 +==== ioquake3 ====
 +
 +The code base is large, over 230k SLOC (Source lines of code) and there is no need to look every single file. The files you need to look at for the tasks:
 +<​code>​
 +qcommon/​qcommon.h
 +qcommon/​net_chan.c
 +qcommon/​net_ip.c
 +qcommon/​huffman.c
 +client/​cl_net_chan.c
 +server/​sv_client.c
 +server/​sv_net_chan.c
 +server/​sv_snapshot.c
 +</​code>​
 +
 +But you probably venture into other files too. The code structures of Quake III Arena are analyzed in a [[http://​caia.swin.edu.au/​reports/​110209A/​CAIA-TR-110209A.pdf|paper]] by Stefyn et. al. And further info about ioquake3 can be read from their [[http://​wiki.ioquake3.org/​Main_Page|wiki]] and a [[http://​wiki.ioquake3.org/​Academic_Articles|list of Q3/ioquake3 academic articles]].
 +
 +==== Freeciv ====
 +
 +<​code>​
 +common/​dataio.c
 +common/​dataio.h
 +common/​connection.c
 +common/​connection.h
 +common/​packets_gen.c
 +common/​packets_gen.h
 +common/​packets.h
 +client/​clinet.c
 +client/​clinet.h
 +client/​packhand.c
 +client/​packhand.h
 +client/​packhand_gen.c
 +client/​packhand_gen.h
 +client/​servers.c
 +client/​servers.h
 +server/​connecthand.c
 +server/​connecthand.h
 +server/​handchat.c
 +server/​handchat.h
 +server/​sernet.c
 +server/​sernet.h
 +utility/​netintf.c
 +utility/​netintf.h
 +</​code>​
 +
 +===== Additional return instructions =====
 +
 +In this assignment feel free to use any text editor you like (Word, LibreOffice,​ LyX, some TeX-editor, etc.) for writing the answers but __convert the document into **PDF**-format before submitting to the SVN__. I.e. only PDF-documents are accepted. Pseudocode can be written directly to the answer document but it can be put into separate files too. And of course, if you code something return these as usual.
 +
 +When you look some other information sources and learn from them (do not copy directly) reference them in your returned assignment (''​char style[] = "​free"''​). If you use the material that was given on this pages reference them too.
 +
 +Remember that this is an individual assignment - plagiarism will not be tolerated, all incidents are reported.
 +
 +===== Virtual machine usage =====
 +
 +There are also virtual Ubuntu images on 4 classroom 6218 computers (lut1813, lut1814, lut1815 and lut1816), where you can install packages and to e.g., sniff traffic of the games by using Wireshark. Details about virtual machine use:
 +  * Use VirtualBox, from commandline:​ <​code>​virtualbox</​code>​
 +  * The virtual images can be found from <​code>/​opt/​VirtualboxVM/​protocl\ design\ methods\ with\ games/</​code>​
 +  * **Option 1**
 +    - Open the folder with your file manager
 +    - Open VirtualBox virtual media manager (File->)
 +    - Drag the ''​.vdi''​ -file to VirtualBox virtual media manager and close it
 +    - Drag the ''​.vbox''​ -file to VirtualBox main window
 +    - Start the Virtual Ubuntu with correct settings
 +  * **Option 2**
 +    - Create new virtual machine
 +    - Set type to Linux and version to Ubuntu
 +    - Use an existing virtual hard drive (from ''/​opt/​VirtualboxVM/​protocl\ design\ methods\ with\ games/''​)
 +    - Create it
 +    - Go to Settings->​Network and select ''​Bridged adapter''​ for Adapter 1
 +    - See on the host machine which physical network adapter (ethX) hasn't got any IP address with <​code>​ifconfig</​code>​
 +    - Select that ethX as physical adapter to use
 +  * **NOTE: __the virtual images are writable by all users so changes to it are available for anyone who uses them__**
 +    * Additionally,​ other users can remove the changes - __virtual machines are not reliable for storing own data__
 +  * **NOTE: if you want to delete the virtual machine __always select keep the virtual file image__, otherwise __it will be deleted__ from that computer**
 +  * The password will be emailed to all of you
 +    * the user as sudo rights -you can install required packages to the virtual machine
 +      * E.g. with <​code>​sudo apt-get install packagename</​code>​
 +      * Or via synaptic
 +      * The changes will be set to that particular virtual machine on that computer
 +  * Computers are on University DMZ-network - no direct access to e.g. classroom computers (the 4 computers running virtual machines are on the same network)
 +  * If you need to find a package that has a specific file:<​code>​sudo apt-get install apt-file
 +apt-file update
 +apt-file search filename</​code>​
 +    * A list of packages which have matches will be provided
 +