Computer Networking

Homework 7, 2 May 2013

This homework assignment has five questions; answer all of them. This assignment is due no later than 1:00 p.m. on Monday, 13 May.

Unless otherwise explicitly directed not to by a question, be sure to show your work, justify your answer, explain your reasoning.

If you mail in your assignment, please submit a printable document — a PostScript .ps or PDF .pdf document, for example — and not a source document — a Word .docx or Latex .tex document, for example.

  1. The biphase-mark data encoding always has a transition at the beginning of a bit interval. A 1 bit also has a transition in the middle of the interval; a 0 bit does not. For example, the biphase-mark encoding for 101 is

    biphase-mark 101

    Given the possibly noisy signal

    a biphase-mark signal

    comment on its fidelity to biphase-mark encoding, and describe, as best as possible, the bit string encoded.

    The obvious problem with the noisy signal is the missing transition at the start of the second bit interval. Assuming the missing transition is the first error to occur, adding a transition to the start of the second bit interval fixes the problem at one end of the interval, but causes a problem at the other:

    a revised biphase-mark signal

    But now there's no transition at the start of the third bit interval. Adding a transition at the middle of the second or the start of the third bit interval fixes that problem.

    a further revised biphase-mark signal

    Alternatively, the first error could have been the transition in the middle of the first bit interval. Removing that transition produces a valid signal with only one change.

    a re-revised biphase-mark signal

    All these answers are acceptable, but Occam’s razor favors the last answer.
  2. A random-access channel has propagation delay τ and three hosts, one, host A, at one end of C and the other two, B and C, at the other end:

    a small random-access channel

    Each host i has a packet for transmission at time ti : tA = 0, tB = τ/2 and tC = 3τ/2. Each packet takes 4τ time to transmit. Assuming that time increases horizontally to the right, diagram what happens to all three packets when all the hosts use
    1. ALOHA
    2. Nonpersistent CSMA
    3. CSMA/CD
    to transmit packets.

    aloha packet trace

    1. Host A begins transmitting its packet.
    2. Host B begins transmitting its packet, trashing it and A’s packet.
    3. Host C begins transmitting its packet, trashing it.
    4. Host A finishes transmitting its packet and waits for an acknowledgment, setting a time-out of length 2τ to end the wait.
    5. Host B finishes transmitting its packet and waits for an acknowledgment, setting a time-out of length 2τ to end the wait.
    6. Host C finishes transmitting its packet and waits for an acknowledgment, setting a time-out of length 2τ to end the wait.
    7. Host A’s acknowledgment time-out expires. A generates a random backoff of 1, and schedules a retransmission 1·4τ from now.
    8. Host B’s acknowledgment time-out expires. B generates a random backoff of 2, and schedules a retransmission 2·4τ from now.
    9. Host C’s acknowledgment time-out expires. C generates a random backoff of 3, and schedules a retransmission 3·4τ from now.
  3. Due to a cascading series of errors, some routers are advertising negative costs along links. The errors are so bad that some path between a source S and a destination D has a loop of total negative cost. Nevertheless, the routing algorithm is able compute a minimal-cost routes between S and D. What is the route cost, and how was did the routing algorithm find it?

    three

  4. Assuming that the round-trip transmission time of a network is 2 seconds, what transmission rate is needed to transmit a full maximum size TCP window before it would be possible to receive an acknowledgment to the first bytes in the window?

    four

  5. Where is the best possible place to insert a new node into a Chord ring (that is, where is the place where inserting a node would change the smallest number of finger tables)? Where is the worst possible place (that is, the place where inserting a node would change the largest number of finger tables)?

    five

This page last modified on 2013 May 24.