College of Computer & Information Science Fall 2004 Northeastern University Handout 11 CSU640: Network Fundamentals 15 November 2004

Problem Set 4 (due Wednesday, December 1)

1. (10 points) CRC code

Suppose we want to transmit the message 11100011 and protect it from errors using the CRC generator is 10011.

(a) Use long division to determine the message that should be transmitted.

(b) Suppose the leftmost bit and the rightmost bit of the message (that is sent) get inverted. What is the result of the receiver’s CRC calculation? Does the receiver recognize that an error has occurred?

2. (20 points) Addresses and packet headers

An organization has a network address of 200.1.1 and wants to form subnets for three departments, one connected through LAN1, another through LAN2, and a third through LAN3, as shown below. The first department has 100 hosts, the second has 52 hosts, and the third has 20 (not all hosts are shown).

(a) Give a possible arrangement of subnet masks to make the above organization possible.

(b) Draw the routing table stored at the router R1. The fields of the table are SubnetNumber, SubnetMask, and NextHop. Set the default entry to be R2.

(c) Choose IP addresses for all interfaces of H1, H2, H3, H4, and R1.

(d) Suppose host H1 wants to send packet P1 to H2 and packet P2 to H3 (using UDP, say), in that order. H1 does not know the Ethernet address of H2, H3, R1, and H4. H1 only knows the IP address of the other hosts and router. Show the flow of packets sent and received (including ARP request and reply packets) by H1. Specify the source and destination IP addresses, Ethernet addresses of the packets, and type of protocols that are used.

Assume that ETH1 is the Ethernet address of H1, ETH2 is the Ethernet address of H2, etc.

3. (20 points) Ethernet capture effect

Let A and B be two stations attempting to transmit on an Ethernet. Each has a steady queue of frames ready to send; A’s frames will be numbered A_{1}, A_{2}, and so on, and B’s similarly. Let T denote the exponential backoff base unit; this is the time taken to send 512 bits over the Ethernet channel. Suppose A and B simultaneously attempt to send frame 1, collide, and happen to choose backoff times of 0 × T and 1 × T, respectively, meaning A wins the race and transmits A_{1} while B waits. At the end of this transmission, B will attempt to retransmit B_{1} while A will attempt to transmit A_{2}. These first attempts will collide, but now A backs off for either 0 × T or 1 × T, while B backs off for time equal to one of 0 × T, …, 3 × T.

(a) Give the probability that A wins this second backoff race immediately after this first collision; that is, A’s first choice of backoff time is less than B’s.

(b) Suppose A wins this second backoff race. A transmits A_{3}, and when it is finished, A and B collide again as A tries to transmit A_{4} and B tries once more to transmit B_{1}. Give the probability that A wins this third backoff race immediately after the first collision.

(c) (Bonus problem) Give an approximate lower bound for the probability that A wins all the remaining backoff races.

(d) What then happens to the frame B_{1}?