CMSC 406, MSCS 560 Computer Networks

Homework Assignment # 3

Due October 6

1. Suppose stations A and B are attempting to transmit on an Ethernet. Each station has a

steady queue of frames ready to send; A’s frames will be numbered A1, A2, etc., and

B’s similarly. Let T = 51.2 ms be the exponential backoff base unit. Furthermore,

suppose A and B simultaneously attempt to send frame 1, they collide, and happen to

choose backoff times of 0 x T and 1 x T, respectively, meaning A wins and transmits,

while B waits. At the end of this transmission, B will attempt to retransmit B1 while A

will attempt to trnsmit A2. These attempts collide, but now A backs off for either 0 x

T or 1 x T, while B backs off for time equal to one of 0 x T...3 x T.

a) What is the probability that A wins the second backoff race immediately

after the first collision?

b) What is the probability that A wins the third backoff race after the first

collision, assuming it won the first and second?

c) Give a plausible estimate of the probability that A wins all the remaining

backoff races.

d) What happens to frame B1?

This scenario is known as the Ethernet capture effect.

2. Suppose the Ethernet transmission algorithm is modified as follows: after each

successful transmission attempt, a host waits one full time slot before attempting to

transmit, and otherwise backing off in the usual way.

a) Explain why the capture effect of the previous exercise is now much less likely.

b) Show how the strategy above can now lead to a pair of hosts capturing the

Ethernet, alternating transmissions, and locking out a third.

c) Propose an alternative approach, for example, by modifying the exponential

backoff. What aspects of a station’s history might be used as parameters to the

backoff?

3. Assume that a SONET receiver resynchronizes its clock whenever a 1-bit appears;

otherwise, the receiver samples the signal in the middle of what it believes is the bit’s

timeslot.

a) What relative accuracy of the sender’s and receiver’s clocks is required in order

to correctly receive 32 zero-bits in a row?

b) Consider a forwarding station A on a SONET STS-1 line, receving frames

from the downstream end B and retransmitting them upstream. What relative

accuracy of A’s and B’s clocks is required to keep A from accumulating more

than one extra frame per minute?

4. For a 100-Mbps token ring network with a token rotation time of 200 ms and which

allows each station to transmit one 1-KB packet each time it possesses the token,

calculate the maximum effective throughput rate that any one host can achieve. Do

this assuming (a) immediate release and (b) delayed release.

5. Suppose a 100 Mbps delayed-release token has 10 stations, a ring latency of 30 ms, and

an agreed upon TTRT of 350 ms.

a) How many synchronous frame bytes could each station send, assuming all are

allocated the same amount?

b) Assume stations A, B, C are in increasing order on the ring. Due to uniform

synchronous traffic, the TRT without asynchronous data is 300 ms. B sends

a 200 ms (2.5Kb) asynchronous frame. What TRT will A, B, and C then see

on their next measurement? Who may transmit an asynchronous frame next?

6. What is the remainder obtained by dividing x**7 + x**5 + 1 by the

generator polynomial x**3 + 1?

7. A 1 km long, 10 Mbps Ethernet has a propagation speed of 200 m/micro sec.

Data packets are 256 bits long, including 32 bits of header, checksum, and

other overhead. The first bit slot after a successful transmission is

reserved for the receiver to capture the channel to send a 32 bit

acknowledgement packet. What is the effective data rate, excluding

overhead, assuming that there are no collisions (e.g., urn protocol at

heavy load)?

8. Draw a timeline diagram for the sliding window algorithm with SWS =RWS = 3

frames, for the following two situations. Use a timeout interval of about 2 x RTT.

(a) Frame 4 is lost.

(b) Frames 4 - 6 are lost.

9. A large population of S-ALOHA users manage to generate 50 requests/sec,

including both originals and retransmissions. Time is slotted in units

of 40 msec.

(a) What is the chance of success on the first attempt?

(b) What is the probability of exactly k collisions and then a success?

(c) What is the expected number of transmission attempts needed?

10. For a token ring system, suppose that the destination station removes

the data frame and immediately sends a short acknowledgement frame to

the sender, rather than letting the original frame return to the sender.

How will this affect performance?

In Class Problem

Suppose that x bits of user data are to be transmitted over a k-hop path in a packet-

switched datagram network as a series of packets, each containing p data bits and h

header bits, with x >> p + h. The bit rate of the lines is b bits/sec and the

propagation delay is negligible. What value of p minimizes the total delay?