Computer Network Midterm Exam

Directions: Write your name on the exam and on every page you submit. Write something for
every question. Students who do not write something for everything lose out over students who
write down wild guesses. You will get some points if you attempt a solution but nothing for a blank
sheet of paper. Write something down, even wild guesses. Problems take long to read but can be
answered concisely.

1, Overview, 40 points: Give the most important answer. 4 points apiece.

• a) Quality of Service and Layering: Increasingly, customers would like important traffic
(e.g., purchases) to be dropped less often that less important traffic (e.g., Peer to Peer).
Routers need to know the importance of a packet but this information originates from the
application layer. What needs to be changed to pass this information without violating strict
layering?

• b) Fundamental Limits: Assuming a bit width of 1 nsec and baseband encoding (1 = 4V,
0 = 0V), the highest frequency signal one could send is 0.5 G Hz. The bit pattern that causes
this is 0101. . .Why is it not sufficient for the wire to only carry 0.5 Ghz signals in order to
send at 1 Gbps as opposed to carrying all frequencies from 0 to 0.5 Ghz? You can answer
this by showing a bit pattern that causes a signal of frequency 0.25 Ghz.

• c) Coding: AMI is a baseband code in which a 0 is coded as 0V while a 1 is coded to
alternate between -1.5 and +1.5V. Why is 11111110 a good preamble for AMI though it is a
poor preamble for Manchester encoding?

• d) Media Fundamentals: Why baud rate (the signalling rate) can be different from the
bit rate.

• e) Media: Because radio ranges are approximate, it is hard to ensure that the 802.11
networks of neighboring homes do not overlap. What property of 802.11 should the home
owners exploit to minimize interference?

• f) Framing: If 11111111 is the flag used for a bit stuffing approach to framing, what is the
worst-case stuffing overhead? Explain.

• g) Sublayering in Data Links: Why framing is layered below error recovery in the Data
Link.

• h) End-to-end argument: In the Internet, people also want end-to-end integrity (i.e., a
guarantee that packets sent are not corrupted). TCP has an end-to-end checksum despite
the fact that each Data Link uses a CRC. Why?

• i) Performance measures: Companies like Walmart have found that the best way to
transfer large amounts of data between data centers across the country is to write the data
from Data Center 1 onto tape drives, and send the tape drives by UPS to Data Center 2.
Why does this technique work for Walmart but is not commonly used in networking?

• j) Sliding Window Protocols: In practice, why is rare to find a true Selective Reject
Protocol (for instance, even TCP SACK is an approximate selective reject protocol)?

2, Recovering Bits, Nyquist Limit: In HW 1, we showed that sending a bit every 1 usec
was possible without intersymbol interference. even though the output of a 1 lasts a long time (
say 4 usec). This is because the output had the right “shape” so that earlier bits are always at 0
Volts whenever later bits are sampled. However, the shape of the output is crucial. In the figure
below, suppose the output is as shown. Note that the output makes a swing down to -2.1 V at 3
usec and is back to 0 at 4 usec. With such an output intersymbol will take place when sending bits
every 1 usec. Assume the bits to be sent are 111. Write on back of paper if needed.

• (4 points) a) Suppose that the 3 bits are sent at times 0, 1, and 2 usec respectively. Draw a
picture of the waves corresponding to the first, second, and third bits on the picture above.
The first is drawn, draw the second as a dashed wave, and the third as a dotted wave.

• (4 points) b) Suppose that the 3 bits are sampled at times 1, 2, and 3 usec respectively. What
is the sampled value of the output in volts at these three sampled times?

• (2 points) c) Suppose the receiver declares the received bit to be a 1, when the voltage is
more than 2V, and to be a 0 otherwise. What 3 bits will the receiver physical layer output?

• (4 points) c) Describe (don’t draw) an example in which InterSymbol Interference occurs
even when sending once every 2 usec.

• (6 points) d) With this new shape, what is the fastest rate that the sender can send and
guarantee zero intersymbol interference. 2 points for the answer, and 4 points for a simple
argument that if you send at this rate, no matter what set of bits are sent in the past, there
will be zero interference when the current bit is sampled.

CSE123a Midterm Exam, Page 3

3, CRCs: While CRCs work well against errors, it is really easy to “hack” a CRC by finding
a second message that has the same CRC. Consider the message 4-bit message 1000 and the CRC
generator x^3 + x + 1.

• (6 points) a) First compute the message together with the CRC. Show your working so we
can give you partial credit.

• (2 points) b) Write down the polynomial corresponding to the message plus CRC.

• (4 points) c) What is a general strategy for a hacker to corrupt a message without changing
the CRC? (Hint: think of adding polynomials that are related in some way to the generator)

• (4 points) d) Based on your strategy in c), what polynomial should you add to change the
MSB (most significant bit) of the message from a 1 to a 0 without changing the CRC you
obtained in a)

• (4 points) e) What is the final bit pattern of the message you hacked?

4, Data Link Protocols on Synchronous Links revisited: Recall in HW 2 one of your
“extra” problems assume that the time taken for a message or ack is 0.5 time units. Further senders
send frames only at integer times like 0,1,2. When a receiver gets an error-free frame (sent at time
n) at time n+0.5, the receiver sends an ack back that arrives (if successful) just before time n+1.
Instead of using the standard alternating bit protocol, assume that sender and receiver use no
numbers in messages or acks. However, sender messages carry a single bit a, which which is set
to the value of a state variable ack received at the sender. The state variable ack received at the
sender is set to true at time n if and only if an ack was received in time period [n − 1, n].

• a), 5 points: Consider a message sent successfully by the sender at time n. The receiver gets
it at time n+0.5 and sends an ack that is lost. Thus ack received at time n+1 is false. Based
on this write a single If-then-else clause of pseudo-code to specify what the sender should do
(e.g., retransmit, send a new message) at time n + 1. Explain why briefly.

• b), 5 points: Based on the same example, write down 1 line of pseudo-code to specify what
the receiver does (e.g., deliver or drop message) when it receives (a,m) where a is the value of
the ack received flag when the sender sent (a,m). Justify your answer. Explain why briefly.

• c) 5 points: Now consider the case when sender and receiver start the protocol, and the
sender sends a single message that is not lost. Based on your code in b) what should the
value of ack received be initialized to at the sender. Explain why briefly.

• d) 5 points: Now consider the case when the sender and receiver start with the initialization
as in c). The first message sent at time 0 is lost. Any message sent at time 1 gets through.
Based on your code in a) and c) what goes wrong? What do you conclude about this protocol?