Computer Networking • CS 514

Test 1, 17 September 2014


This test has six questions. The test runs the entire class period, starting at 4:30 and ending at 6:20. When you finish the test, you may leave.

Always justify answers unless the question explicitly states it’s not necessary. Some questions require reasonable assumptions in order to be answered. In such cases the answer should clearly state the assumptions made.
  1. Keeping in mind that giving an example of X is not defining X, briefly (in one or two sentences, 25 to 30 words total) define:

    • Socket

    • Stateless protocol

    • Out-of-band signaling

    • Traffic intensity

    • Protocol layering


    Keeping in mind that giving an example of X is not defining X, briefly (in one or two sentences, 25 to 30 words) define:

    • Socket:
    A connection end-point provided by the Sockets library.

    • Stateless protocol:
    A protocol in which no state is kept between message sends.

    • Out-of-band signaling:
    A connection in which data and control information are sent along separate channels.

    • Traffic intensity:
    The ratio of input rates to output rates for a buffer.

    • Protocol layering:
    A mechanism for controlling complexity by factoring a protocol into simpler protocols arranged in stack.

  2. Why are DNS replies retrieved from the cache non-authoritative?


    An authoritative DNS reply comes from a DNS server maintaining the database supplying the reply. Unless the cache resides on the same system as the authoritative server, which seems unlikely, cache replies are not authoritative because the cache resides on a system that doesn’t maintain the database containing the reply.

  3. Show how to calculate the instantaneous throughput of an FTP session.


    A session’s instantaneous throughput is a unit of transfer divided by a unit of time. An FTP session has two connections: a persistent command connection and a transient data connection. The data connection’s instantaneous throughput is the ratio of the number of observed data units (bits or bytes, for example) over the observation time (a small fraction of the connection time; seconds or milliseconds, for example). The control connection’s instantaneous throughput is computed the same way, but is less useful given the intermittent, interactive communication over the connection.

  4. A DNS query can be iterative or recursive. In terms of the time it takes to get a response (assume all responses are successful), which query type which would you expect to be faster: iterative or recursive? Assume no replies are cached, and that network conditions are constant. Justify your answer.


    Iterative and recursive DNS queries send the same number of messages, so there’s no speed advantage there. In some sense recursive queries use shorter connections along the DNS hierarchy than do iterative queries, which cut across the hierarchy. It’s difficult to quantify the speed advantage for shorter connections, but perhaps reasonable to assume that one exists for recursive queries. On the other hand, recursive queries route through DNS root servers, which are performance bottlenecks on recursive queries. It also seems reasonable to assume the bottleneck penalty is greater than the short connection advantage. For these reasons, iterative queries are likely to be faster than recursive queries.

  5. A colleague of yours thinks SMTP would be better if it were implemented as a pull protocol. Describe one way in which your colleague’s pull SMTP would be better than the standard SMTP. Describe one way in which your colleague’s pull SMTP would be worse than the standard SMTP.


    Pull SMTP improves on SMTP by giving the receiving server the ability to decide from which senders it will accept mail.

    Pull SMTP has the disadvantage of needing to poll senders to see if they have any mail.

  6. Nim is a two-person game played as followed:

    1. Both players agree on the size of three penny piles, each pile containing at least one penny. The players also agree on which of them moves first.

    2. Player one picks one of the penny piles and removes at least one and at most all pennies from the pile.

    3. If all piles are gone, player one wins the game. Otherwise, go to the next rule.

    4. Player two picks one of the penny piles and removes at least one and at most all pennies from the pile.

    5. If all piles are gone, player two wins the game. Otherwise, go to rule two.

    Describe a protocol that would let two end-points play Nim over a network connection. Your protocol description should give the structure of the messages used and the sequence of messages exchanged during a game. You may make simplifying assumptions as needed as long as resulting protocol plays Nim as described above. Make sure you state your assumptions.


    Assume reliable, message-based communication. Also assume fair play and players that don’t make mistakes. All messages have the same format:

    1. A one-byte type field.
    2. A three-byte piles field. The value of the ith byte is the number of pennies in the ith pile.
    3. A one-byte coin-flip field.
    All bytes are interpreted as 8-bit unsigned integers. Assume there exists a set of named 8-bit constants. The phrase “an X message” means “a message in which the type field contains the 8-bit named constant X.”

    Nim play occurs two phases. The first phase sets up the game and the second phase plays the game.

    Phase one starts when player A sends a Hello message to player B; assume B does not simultaneously try to start a game with A. The piles field contains the values A wants to use to start the game. The coin-flip field contains a value randomly selected from the set {0, 1}. If B doesn’t want to play, it responds with a Stop message in which the piles and coin-toss fields are undefined. Receipt of a Stop message at any point during the protocol signals an immediate end to the communication.

    If A’s pile values are acceptable, B responds with a Hello message in which the pile values are the same as A’s Hello message and the coin-flip field contains a random choice from {0, 1}. If A’s pile values are unacceptable, B responds with a Hello message containing alternate pile values and a random choice from {0, 1}. The exchange of Hello messages continues until either both sides agree on pile values or one sends a Stop message.

    Assuming agreement, phase two starts. If the coin-flip value of the two most recent Hello messages are the same, then the side that sent the penultimate Hello message moves first; otherwise the side that sent the last Hello message moves first.

    A Move message reflects a Nim move. Two of the pile values in the message are the same as the values received in the most recent message of any kind, while the third pile contains a reduction in value as in Nim. The value of the coin-flip field is undefined. Move messages alternate between sides until a message containing all empty piles is sent, at which point the communication ends.


This page last modified on 2014 September 22.