Here is the final assessment paper for your reference.
In Question 1, we explore a taxonomy of in-game actions and try to discover why some actions are more sensitive to delay and consistency, while some are not. Here, we introduce two new notions, precision and deadline, or an action. In Part (a) and (b), you are asked to give two examples, one for high-precision, loose-deadline (HP-LD) action, and the other for low-precision, tight-deadline (LP-TD) action. Most of you got these questions correct. My favorite example for LP-TD: player is on-fire and need to jump into the river.
Next, you are asked to explain the relationship between precision and tolerable response time, and between deadline and tolerable response time. Many of you answered that there is no relationship between precision needed for the action and the tolerable response time. In fact, the higher the precision needed, the lower the tolerable response time is. Case in point: have you tried clicking on a few target pixels on screen when your mouse cursor movement is delayed after you move the mouse? It is really annoying. Most of you got the relationship between deadline and tolerable response time correct though (loose deadline means higher tolerable response time).
Finally, in Question 1, you are asked to explain what type of actions is good for short-circuiting, which reduces response time and increases inconsistency. About half got this correct: LP-TD. Since low precision is needed, inconsistency is tolerated, but low response time is good for tight-deadline action.
For Question 2, if you understand the question and DDM, the first two parts are giveaways. SL will never overlap with UR, and SR will never overlap with UL. On the other hand, SLR will always overlap with ULR.
Next, you are asked to sketch a recursive algorithm. The idea is basically, to call split() on S and U to partition the input into six partitions. The pairs in SLR will always overlap with ULR. For the rest, we recursively call DDM on the following pairs: SL and (UL union ULR), SR and (UR union ULR), and SLR and (UL union UR). There is no need to consider those that never overlaps. Some of you got partial credits because you only recusrively call DDM on SL and UL, and SR and UR.
Now, for Question 3, Part (a) is mostly a give away: delayed ack is implemented in the receiver only; fast retransmission and exponential backoff on the sender only; and redundant data bundle needs to be implemented on both sides (since receiver needs to make sense of the bundled data from the sender). Part (b) is also quite straightforward. If the NIC sleeps for too long, it could cause the connection to idle for more than RTO, and the connections’ congestion window resets. If it sleeps even longer, the TCP connection might time out and three way handshake is needed to reestablish the connection. Either way, the connection restarts from slow-start phase again.
Question 4 receives several answers that do not use virtual network coordinates and got 0. For the rest, as long as you explain how players can establish its network virtual coordinate (by obtaining a few landmarks from the server, measuring RTT to them, then reporting the RTT or coordinate back to the server) and how the server does matchmaking (by clustering the players using distance computed from the coordinate), you get 15.
Finally, Question 5 is the one that stumped most of you. The answer can be summarized in two words: frontier region. If two players have no chance of entering each other AOI, there is no need to exchange position update, and this can be achieved through frontier region.
It is disappointing that many of you answered: if two players are not in each other’s AOI, then there is no need to exchange position update. The problem is that, if two nodes do not know the latest position of each other, how do they know that they are in each other’s AOI or not? A similar answer is that two players are very far apart, then they do not have to exchange position update. But did not explain “how far”, nor did the answers explain how can a node know if the other node is far, without know its latest position!
The other popular answer that received a small partial credit is that, if two players (say, A and B) have a common neighbor (C), then they need not exchange position update, since C can tell A and B when A and B enters each others’ AOI. This is correct but incomplete. If A, B, and C are mutually enclosing neighbor of each other, then by this rule, they would not exchange position update so C would not know A and B’s latest positions!
I am, however, quite delighted that a few of you came up with an unexpected answer that is correct: if A is moving away from the last know position of B, it need not update B (and vice versa). The rational is that if A and B are not in each other AOI’s to begin with, then this movement would never cause A and B to enter each other’s AOI.
I hope you had fun answering the paper, which ties up quite a few disparate ideas together, and learn something new in the process. Cheers.
May 10, 2015 at 3:13 am
Hi prof Ooi,
Your paper is definitely one of the most enjoyable exams I have taken in NUS. (preparation is not enjoyable though)
I would like to have a question about 3a (iv). Data bundle is surely required server to change its implementation, but for client is it a must to do so?
Yes it would make sense that client need to double check which packet is already received and throw away those which are already acked. However, maybe the process can be done at the application layer, which require no changes on the TCP stack?
My idea is the network layer should only concern about the TCP header and should not look inside the payload of the packet.
However, your answer also make sense, as the protocol change is supposed to be transparent from the application POV.
August 23, 2015 at 8:51 am
Since we have sequence numbers for the payload at the TCP layer (which is at the transport, not network, layer BTW), the transport layer is able to check for duplicates easily. At the application layer, we can only check for content duplicates, which may or may not be possible. The application, for instance, would have to add in their own application-level sequence numbers. This would add the message overhead. Further, the OS has to copy many redundant data from kernel space to user space.
(Sorry for the 3.5 months latency. I did not check back on this site after the class is over).
May 10, 2015 at 3:25 am
For the first question, doesn’t the relationship between precision and max delay depend on the design of the game itself?
In my opinion, the degree of dependence varies from games to games, greatly depend on the network design of the game itself. Hence I think both answers are correct?
For example, precision in many RTS games such as StarCraft/WarCraft/Age of Empire (Dota 1 included) is not relevant to the delay, as long as you click on the unit on time?
August 23, 2015 at 9:03 am
The delay (or response time) in this question refers to the time between user input (e.g., clicking on a unit) to the time the results of the action is seen (e.g., attacks the unit). So this is a function of the networking component design. Precision, however, is a function of the game design.
In the case of RTS, when precision is needed (e.g., to attack a unit that appears several pixels wide on screen), high response time makes the game less playable (e.g., you need to move the mouse on the unit, but the unit is moving).