CS/ECE 438: Communication Networks Fall 2007Problem Set 2 Due Wednesday, October 31. Ethernet TimingThis problem is ab out the Ethernet/IEEE 802.3 access protocol. To be definite, suppose that if a hostdetects a transmission while it is transmitting a frame, then: (i) if the host has already transmitted the64-bit preamble, the host stops transmitting the frame and sends a 32-bit jamming sequence; (ii) elsethe host finishes transmitting the 64-bit preamble and then sends a 32-bit jamming sequence. Supposethe packets are 512 bits long, which is the minimum length allowed. Hosts A and B are the only activehosts on a 10 Mbps Ethernet and the propagation time between them is 25 µs, or 250 bit durations.Supp ose A begins transmitting a frame at time t = 0, and just before the beginning of the framereaches B, B begins sending a frame, and then almost immediately B detects a collision. NOTE: Forsimplicity, please ignore the 9.6 µs inter-frame wait time in the Ethernet proto col.(a) Does A finish transmitting the frame before it detects that there was a collision? Explain.(b) What time does A finish sending the jamming signal? What time does B finish sending thejamming signal?(c) What time does A hear an idle channel again? What time does B first hear an idle channel again?(d) Supp os e each host next decides to retransmit immediately after hearing the channel idle. Afterthe resulting (second) collision: When does A next hear the channel idle? When does B next hearthe channel idle?(e) Suppose after the second collision, A decides to wait 512 bit durations to retransmit (if it hearssilence after that long) and B decides to retransmit immediately after hearin ga silent channel. Isthe transmission of host B successful?2. Multiple AccessSupp ose nodes A and B are ready to send a packet at the same time a third node ends transmissionon a 10 Mbps Ethernet. In the ith round after i − 1 collisions have already occurred, the two nodeswait 0, 1, . . . , 2i−1− 1 slots until the next attempt, all 2i−1choices having equal probability.(a) Find the probability qiof a collision in the ith round, given that there are collisions in the previousi − 1 rounds (i.e. q1= 1, q2= 1/2), for all i ≥ 1.(b) Find the probability pithat exactly i rounds are needed for the first success, and computep1, p2, . . . , p4.(c) Now assume that after the first collision, node A “wins” the backoff and transmits successfully.After it is finished, both nodes try to transmit again (A has an infinite amount of traffic to send),causing a collision. After this collision, the A’s collision counter is at 1 and B’s is at 2. Computethe probability that A wins again.(d) Given that A “won” the first round, compute the probability that A captures the network for thenext 5 frames.3. Token Ring NetworksIn a token ring network, a station is allowed to hold the token for some period of time, the tokenholding time, THT. Let RingLatency denote the time it takes the token to make one complete rotationaround the network when none of the stations have any data to send.(a) In terms of THT and RingLatency, express the efficiency of the network when only one station isactive. Assume early release for the next few questions.(b) What setting of THT would be optimal for a network that only had one station ac tive (with datato send) at a time?(c) In the case where N stations are active, give an upper bound on the token rotation time, TRT,for the network.1B1B3B6B4B7B2B5ABCDEFGHIJFigure 1: Bridged Network Configuration(d) Let N = 100, THT = 1000 µs, and RingLatency = 200µs. Compute the efficiency of this networkif all N nodes are active and are using early release.(e) Compute the effic iency of the above network if delayed release is used.4. BridgesConsider the network configuration in Figure 1 for this question.(a) What ports would be not selected by the spanning tree algorithm? (The ID of e ach bridge is itsnumber, i.e. B1 has ID 1.) List ports as pairs (bridge, network), i.e. (B1,A).(b) To simplify thinking about the spanning tree problem, suppose that communication among bridgeshapp e ns in rounds. In each round, a bridge will forward the configuration message it receivedfrom the root in the previous round to all its other links, or, if it had not received this message,become root and send a new configuration message.Supp ose that bridge B1 fails at round 0 (i.e. it sent out its last message in round -1). How longwill it take for the network of bridges to form a new tree?(c) List the ports that are not selected by the new spanning
View Full Document
Unlocking...