Homework4SolutionGuidelinesCSC401,Fall,2011

1. Consider the delay of pure ALOHA versus slotted ALOHA at low load. Which one is less? Explain your answer. 1. At low load, no collisions are likely. In slotted ALOHA we still need to wait for the next slot beginning time to transmit, so delay is higher. 2. Consider the delay of pure ALOHA versus slotted ALOHA at high load. Which one is less? Explain your answer. 2. The answer depends on how you interpret delay. At high load, collisions are likely. In slotted ALOHA we always need to wait for the next slot beginning time to transmit, so delay is always higher if by delay we mean the time an arriving packet has to wait to be attempted to be transmitted on the medium by ALOHA. But many fewer transmissions will be successful in unslotted ALOHA, due to the higher number of collisions. So if by delay we mean the time a packet is finally successfully transmitted, after initially arriving as a new packet, then the answer reverses. (This assumes, as is usual with ALOHA, that failed packets are retransmitted by some higher layer process after some interval.) 3. How long does a station, s, have to wait in the worst case before it can start transmitting its frame over a LAN that uses the basic bit-map protocol? 3. Assume each frame is d bits long. The worst case is: all stations want to send and s is the highest numbered station. Wait time is N + (N-1)*d bit times as follows: N bit contention period, and (N-1)*d bit (transmission of frames by all the other stations). You might also validly consider that the worst case is when the frame arrives at the MAC layer of station s just after its contention slot passed. In this case, it has to wait (N-1)d bit times for the current sequence of frames (every other station has frame to send), plus the above answer. This answer is also valid. 4. Two CSMA/CD stations are each trying to transmit a long stream of many frames). After each frame is sent, they contend for the channel, using the binary exponential backoff algorithm as described in Section 4.3.2 of the text. We denote by a round each calculation of the backoff period followed by transmission attempt by a station. Number rounds by how many collisions have occurred before that round Round 1 occurs after the first collision, there are two slots at which each station might try after waiting 0 slots (no wait) and after waiting 1 slot. Similarly the contention at Round i is over 2i slots (numbered from 0 to 2i -1). The contention period is the entire period between two successful frame transmissions.

(a) What is the probability that at round k for some k < 10, the contention has still not ended? (This question should be possible to answer from a straightforward consideration of the binary exponential backoff algorithm, and does not require any consideration of the efficiency calculation in Section 4.3.3.) (b) Why is the question less meaningful to ask for higher values of k ? 4. (a) At round i, the first station might pick the slot 0 with probability 1/2i, so might the second station. Therefore the probability of a collision by both stations picking this slot is 1/22i . However, this is true not only of slot 0, but every slot from 0 to 2i, so the total probability of collision at the i-th round is 1/2i . Clearly the probability of having k rounds, and the contention still not resolved, is the multiplication of the probabilities of collision at Round 1, Round 2, Round 3, Round k = 1/2(1+2++k) = 1/2k(k-1)/2 . (b) The probability of a collision at Round k should be frozen after k = 10, according to the details of the standard, so it does not fall into a nice form as above. 5. (Ungraded) Consider building a CSMA/CD network running at 1 Gbps over a 1-km cable with no repeaters. The signal speed in the cable is 200,000 km/sec. The minimum frame size is fixed at 2500 bytes. What is the limit imposed on the length of the maximum length of wiring that can be used by the logic of the CSMA/CD protocol? 5. For a 1 km cable, the one way propagation time is 5 sec, so 2 = 10 sec. To make CSMA/CD work, it must be impossible to transmit an entire frame in this interval (that is, the transmitter should still be transmitting the frame at the latest time when the collision can come back to it). At 1 Gbps, all frames shorter than 10,000 bit can be completely transmitted in under 10 sec, so the minimum frame is 10,000 bits or 1250 bytes. If the minimum frame size is fixed at 2500 bytes, the limit imposed on the length goes up to 2 km, thus the 1 km cable length is possible. 6. Ethernet frames must be at least 64 bytes long to ensure that the transmitter is still going in the event of a collision at the far end of the cable. Fast Ethernet has the same 64-byte minimum frame size but can get the bits out ten times faster. How is it possible to maintain the same minimum frame size? 6. The maximum wire length is fast Ethernet is only allowed to be 1/10 as long as in Ethernet. Thus decreases by a factor of 10 (since the propagation speed of the signal in the wire remains the same), just as decreased by a factor of 10 due to the faster transmission speed. Thus the protocol continues to work. 7. Consider the interconnected LAN shown in Slide 38 of the MAC lecture. Assume that hosts a and b are on LAN 1, c is on LAN 2, and d is on LAN 8. Initially, hash tables in all bridges are empty and the spanning tree shown in the Figure is used. Show how the

hash tables of different bridges change after each of the following events happen in sequence (i.e. first (a) happens, then (b) happens, and so on). (a) a sends to d (b) c sends to a (c) d sends to c (d) The bridge D malfunctions, and a new spanning tree is established by the bridges automatically by activating the minimum number of inactive bridges possible (e) d sends to a 7. (a) This first frame is forwarded by every bridge, because all hash tables are empty and no bridge has any information that will allow eliminating any transmissions. After this transmission, every bridge has an entry for destination a with appropriate port in its hash table. For example, Bridge B knows to repeat frames going to a on LAN 2 but not 3, E knows to repeat such frames on LAN 3 but not 6, etc. In your answer, you are expected to show the exact updates to the tables at various bridges (just show the mapping, you need not consider the hashing). (b) The second frame is seen by B, D and A, because these are the bridges connected to LAN 2 (where c is). It is not seen by any other bridge, because B, D do not repeat it on any LAN by the above logic, and A repeats it only on LAN 1. These three bridges now append an entry for c in their hash tables. (c) The third frame is seen by H, D, A and B. These bridges append an entry for d H notes that frames going to d must be repeated on LAN 8, and D notes that they must be repeated on LAN 5, etc. (d) Since bridges can only update their hash tables with information obtained by observing transmissions from various stations, a malfunction of a bridge does not change any hash table at any bridge. To reconnect the network, a single bridge is made active it can be either G or I, and your answer will differ based on which you assume. Lets assume for illustration that it is G. Note that at this point, the hash table of G is empty. (e) The last frame is seen by H, G, E, J, B, C, A. F does not see it, because C knows that frames to A need not be repeated on LAN 4. Of these, H does not change its hash entry for d. Bridges G, E, J and C append a new entry for d, Bridge B updates its hash table entry for d, and Bridge A does not change its hash entry for d. 8. To make VLANs, work, configuration tables are needed in the bridges. What if the VLANs of Figure 4-47 of the text used hubs rather than switches? Do the hubs need configuration tables, too? Why or why not? 8. No. Hubs just connect all the incoming lines together electrically. There is nothing to configure. No routing is done in a hub. Every frame coming into the hub goes out on all the other lines.

9. (Ungraded) In Figure 4-48 of the text, the switch in the legacy end domain on the right is a VLAN-aware switch. Would it be possible to use a legacy switch here? If so, how would that work? If not, why not? 9. It would work. Frames entering the core domain would all be legacy frames, so it would be up to the first core switch to tag them. It could do this by using MAC addresses or IP addresses. Similarly, on the way out, that switch would have to untag outgoing frames.