CSE 588 Problem Set #1
Due Date: Friday, April 16


1. The book claims that the initial sequence numbers (ISN) of a TCP connection are chosen "randomly" by each end point.This is not quite true.Find out what TCP actually does to choose ISNs and briefly describe the algorithm.You might look this up in the TCP specification itself, as described in "Request for Comments 793" (RFC-793).To find an on-line copy, try your favorite search engine or go to http://www.ietf.org/, and follow links.

2. Hugh Hopeful is the President of JTBD (Just to Be Different) Network Company.After consulting marketing, Hugh decides to offer a new framing protocol where the user can specify their own flags to delineate the start and end of frames.One popular framing protocol is HDLC, which uses 01111110 as the start/stop signal; to prevent confusion, HDLC stuffs an extra 0 after every 5 bits in the user data that are all 1's.

Suppose the user provides an 8 bit flag of the form "aSbc" where a, b, and c are arbitrary bits, and S is an arbitrary 5 bit string.Hugh invents the following bit stuffing rule -- whenever you find the string S in the user data, an extra bit equal to the complement of b is stuffed after it.Notice that Hugh's rule gives exactly the HDLC bit stuffing rule.Can Alyssa P. Hacker find a flag that Hugh's stuffing rule will fail on? Explain.


3. Suppose a single sender and receiver connected to the same Ethernet are communicating using a sliding window protocol.Explain why we might see a collision on nearly every packet.

4. Ethernets use Manchester encoding.Why does this allow for collisions to be detected soon after they occur, without waiting for the CRC to be computed at the end of the packet?

5. Suppose we are only concerned with reducing the latency to transmit a packet over an unloaded store and forward network (for example, to download a page from a web server).Suppose each stage in the network has both a fixed overhead (o) to handle a packet (prepare it to be forwarded), and a bandwidth (b) to transmit the packet once the overhead has been paid.Explain why, as a function of (o), (b), and the packet size (s), it is sometimes more efficient to fragment the packet before sending it.

6. If fragmentation is considered harmful, why don't all networks support arbitrarily large packets?

7. A common mistake in implementing the alternating bit protocol is to have the receiver only acknowledge packets whose sequence number is expected. Explain how this strategy will cause the protocol to fail.

8. TCP uses a 16 bit checksum per segment, typically 576 bytes for Internet connections.As we noted in class, most link level protocols do their own bit error detection and correction. Is this really necessary -- what is the maximum link layer bit error rate you would be willing rely on TCP to catch?Defend your answer.

9. The Internet architecture supports "probe" packets - on receipt of a probe packet, the destination immediately transmits a response to the source.Further, routers will reply immediately back to the source when a packet's hop count reaches 0.Explain how a source can use the elapsed round-trip time for these probe packets to infer the bandwidth and delay of every link between the source and the destination. (First show how it can be done for the first hop, and then show how it can be done recursively.) Assume the rate and delay are the same in both directions.

10. For short connections (such as for web requests!), the overhead of TCP's three-way handshake can dominate the actual data transfer.Design a TCP-lite protocol that can send data directly without waiting for the handshake (even on the first connection between two hosts), or show why it can't be done.



Document converted from word 8 by MSWordView (mswordview 0.5.6)
MSWordView written by Caolan McNamara