CS/ECE 438: Communication Networks Fall 2006Problem Set 3 Due Wednesday, October 4All problems carry equal weight. Please justify your answers and show allyour work.1. Ethernet TimingThis problem is about the Ethernet/IEEE 802.11 access protocol. To bedefinite, suppose that if a host detects a transmission while it is trans-mitting a frame, then: (i) if the host has already transmitted the 64-bitpreamble, the host stops transmitting the frame and sends a 32-bit jam-ming sequence; (ii) else the host finishes transmitting the 64-bit preambleand then sends a 32-bit jamming sequence. Suppose the packets are 512bits long, which is the mimimum length allowed. Hosts A and B are theonly active hosts on a 10 Mbps Ethernet and the propagation time be-tween them is 20 µs, or 200 bit durations. Suppose A begins transmittinga frame at time t = 0, and just before the beginning of the frame reachesB, B begins sending a frame, and then almost immediately B detects acollision.(a) Does A finish transmitting the frame before it detects that there wasa collision? Explain.(b) What time does A finish sending the jamming signal? What timedoes B finish sending the jamming signal?(c) What time does A hear an idle channel again? What time does Bfirst hear an idle channel again?(d) Supp os e each host next decides to retransmit immediately after hear-ing the channel idle. After the resulting (second) collision: Whendoes A next hear the channel idle? When does B next hear thechannel idle?(e) Suppose after the second collision, A decides to wait 512 bit dura-tions to retransmit (if it hears silence after that long) and B decidesto retransmit immediately after hearin ga silent channel. Is the trans-mission of host B successful?NOTE: For simplicity, please ignore the 9.6 µs inter-frame wait time inthe Ethernet protocol.2. Multiple AccessSupp ose nodes A and B are ready to send a packet at the same time a thirdnode ends transmission on a 10 Mbps Ethernet. In the ith round afteri− 1 collisions have already occurred, the two nodes wait 0, 1, . . . , 2i−1− 1slots until the next attempt, all 2i−1choices having equal probability.1(a) Find the probability qiof a collision in the ith round, given that thereare collisions in the previous i − 1 rounds (i.e. q1= 1, q2= 1/2), forall i ≥ 1.(b) Find the probability pithat exactly i rounds are needed for the firstsuccess, and compute p1, p2, . . . , p5.(c) Now assume that after the first collision, node A “wins” the backoffand transmits successfully. After it is finished, both nodes try totransmit again (A has an infinite amount of traffic to send), causinga collision. After this collision, the A’s collision counter is at 1 andB’s is at 2. Compute the probability that A wins again.(d) Given that A “won” the first round, compute the probability that Acaptures the network for the next 10 frames.3. Token Ring Networks(a) In a token ring network, a station is allowed to hold the token forsome period of time, the token holding time, THT. Let RingLatencydenote the time it takes the token to make one complete rotationaround the network when none of the stations have any data to send.(Assume early token release for this subpart).i. In terms of THT and RingLatency, express the efficiency of thenetwork when only one nstation is active.ii. What setting of THT would be optimal for a network that onlyhad one station active (with data to send) at a time?iii. In the case where N stations are active, give an upper bound onthe token rotation time, TRT, for the network.(b) Consider a token ring with a data rate of 10 Mbps, a ring latency of150 µsec, and 1024-bit packets.i. Assuming only one host wants to transmit and the delayed tokenrelease scheme is used, what is the maximum effective through-put rate that can be achieved?ii. Now assume N hosts want to transmit on the token ring andthe token holding time (THT) is 500 µsec. What is the tokenrotation time?iii. Under the assumptions of part (2), and using the immediate re-lease scheme, what is the throughput rate that can be achieved?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 each bridge is its numbe r, i.e. B1 has ID 1.) List portsas pairs (bridge, network), i.e. (B1,A).2Figure 1: Bridged Network Configuration(b) Supp os e that a bridge broadcasts a state update (Y, d, X), where Yis the root ID, d is the distance to the root, and X is its own identity,to the network every 5 seconds. If B1 suffers a catastrophic failure,how long will it take to build a new tree?(c) List the ports that are not selected by the new spanning
View Full Document
Unlocking...