College of Computer & Information Science Fall 2004 Northeastern University Handout 13 CSU640: Network Fundamentals 4 December 2004

Sample Solution to Problem Set 4

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.

Answer: We first append four 0s (since the length of CRC generator is 5) to the message to obtain 111000110000. On dividing 111000110000 by 10011, we obtain a quotient of 11110010 and a remainder of 0110. Note that the remainder should be written as four bits since that is the degree of the CRC.

Thus, the message that is transmitted is 111000110110.

(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?

Answer: The received message is 011000110111. The receiver divides this message by the CRC code, which is 10011. The quotient obtained is 1101000 and the remainder obtained is 1111. Since the remainder is not 0, the receiver recognizes 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.

Answer:

Network SubnetNumber SubnetMask
LAN1 200.1.1.0  255.255.255.128
LAN2 200.1.1.128  255.255.255.192
LAN3 200.1.1.192  255.255.255.224

Note that for LAN3, a subnet mask of 255.255.255.192 would have also been fine.

(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.

Answer: Label the interfaces of R1 to LAN1, LAN2, and LAN3 as I1, I2, and I3, respectively.

SubnetNumber SubnetMask NextHop
200.1.1.0  255.255.255.128  I1
200.1.1.128  255.255.255.192  I2
200.1.1.192  255.255.255.224  I3
Default  R2

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

Answer: Note that we need to assign different IP addresses for the 3 different interfaces of router R1 attached to the three different LANs. What is done with the link to R2 depends on the nature of connection between R1 and R2.

Interface IP address
H1  200.1.1.1
H2  200.1.1.2
H3  200.1.1.129
H4  200.1.1.193
I1  200.1.1.3
I2  200.1.1.130
I3  200.1.1.194

(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.

Answer: H1 has a routing table that indicates that H2 is in LAN1 while for all other destinations, the packet has to to be forwarded to R1, in particular, the interface I1, the IP address of which is known to H1.

For packet P1, the packet flow is as follows.

1. H1 broadcasts an ARP request with source IP address 200.1.1.1, source Ethernet address ETH1, and destination IP address 200.1.1.2.

2. H2 responds with an ARP response with source IP address 200.1.1.2, source Ethernet address ETH2, destination IP address 200.1.1.1, and destination Ethernet address ETH1.

3. H1 sends a UDP packet with source IP address 200.1.1.1 and destination IP address 200.1.1.2. (The UDP header also includes port numbers and other fields that we do not have enough information to specify in this problem.) The packet is sent using the Ethernet protocol. In the Ethernet header, the source Ethernet address is ETH1, and the destination Ethernet address is ETH2.

For packet P2, H1 knows that the packet has to be sent to router R1 (or more precisely, the IP address of interface I1, which is 200.1.1.3). Let the Ethernet address of I1 be I1 ETH and that of I2 be I2 ETH. So we have the following flow of packets.

1. H1 broadcasts an ARP request with source IP address 200.1.1.1, source Ethernet address ETH1, and destination IP address 200.1.1.3.

2. Router R1 responds with an ARP response with source IP address 200.1.1.3, source Ethernet address I1 ETH, destination IP address 200.1.1.1, and destination Ethernet address ETH1.

3. H1 sends a UDP packet with source IP address 200.1.1.1 and destination IP address 200.1.1.129 (and appropriate port numbers and other fields). This is sent using the Ethernet protocol. In the Ethernet, the source Ethernet address is ETH1, the destination Ethernet address is I1 ETH (that of I1).

4. R1 looks up its routing table and figures out that the packet needs to be sent on interface I2 to IP address 200.1.1.129. However, it may not know the Ethernet address of this host. So R1 sends an ARP request on LAN2 with source IP address 200.1.1.130, source Ethernet address I2 ETH, and destination IP address 200.1.1.129.

5. H3 responds with an ARP response with source IP address 200.1.1.129, source Ethernet address ETH3, destination IP address 200.1.1.130, and destination Ethernet address I2 ETH.

6. R1 sends a UDP packet with source IP address 200.1.1.1 and destination IP address 200.1.1.129 (with the same port numbers and other information as was sent by H1). This packet is sent using the Ethernet protocol. In the Ethernet header, the source Ethernet address is I2 ETH, the destination Ethernet address is ETH3.

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.

Answer: A can choose 0 or 1; B can choose 0, 1, 2, or 3. A wins outright if the the pair (A’s choice, B’s choice) is among (0,1), (0,2), (0,3), (1,2), (1,3). There are 8 possible choices, 5 of which are wins for A. So there is a 5/8 probability for A to win the race.

(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.

Answer: A still chooses from 0 or 1; B, however, chooses from 0 through 7. Totally, there are 16 possible choices. We have to count the number of winning choices for A. If A chooses 0, then there are 7 choices for B that have A win; if A chooses 1, then there are 6 choices for B that have A win. So in all 13 of 16 choices make A win. Thus, the probability of A’s winning is 13/16.

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

Answer: We need to generalize the above calculation. Note that A always chooses from 0 or 1, while B chooses from 0 through 2^{i} − 1, for some i. In part (a) above, i was 2, while in part (b) i was 3.

For general i, there are 2 × 2^{i} = 2^{i+1} possible choices, since A has 2 choices and B has 2^{i}. If A chooses 0, then there are 2^{i} − 1 choices for B that have A win; if A chooses 1, then there are 2^{i} − 2 choices that have A win. Thus, there are 2^{i+1} − 3 choices that have A win. The probability of A winning in round i is

\frac{2^{i+1} − 3}{2^{i+1}} = 1 − \frac{3}{2^{i+1}} .

Note that if we plug in i = 2, we get 5/8, and if we plug in i = 3, we get 13/16, thus matching our answers for (a) and (b).

What we need to calculate is the probability that A repeatedly wins from round 4 onwards until round 16, after which B will drop the packet. We get

(1 − \frac{3}{2^{4+1}} )(1 − \frac{3}{2^{5+1}} )(1 − \frac{3}{2^{6+1}} ) ⋯ (1 − \frac{3}{2^{16+1}} )

= (1 − \frac{3}{32})(1 − \frac{3}{64})(1 − \frac{3}{128}) ⋯ ≈ 0.833 ≈ \frac{5}{6}.

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

Answer: After B tries and fails 16 times to transmit the first packet, B drops the packet and moves on to its second packet, with a fresh backoff counter set to 0.