cs398 Lecture Notes Spring 2000 Week 4, Tuesday There was no reading assignment for today. For next time you should start Chapter 3. It's only 74 pages, a welcome relief after Chapter 2. As usual, you should start by reading the intro and by skimming all the section, so you have a high-level understanding of what the chapter is about. For next time, please make an outline of the chapter, explaining in your own words what each of the four sections is about. Also make a list of three questions that you think are interesting, that you don't know the answer to, and that will be answered in this chapter. Finally, read Section 3.1 in detail. ----- Today's topics 1) exam 2) MAC revisited Part One: Encoding, framing, error checking, reliable delivery (4 points) If you received the following NRZI signal on a wire, what would the corresponding message be? 01101101 01011011 (4 points) What is the 4B/5B signal for the following message? 10010011 (Just give me the 4B/5B; you don't have to convert to NZRI). 10011 10101 (4 points) Let's say we want to send the message 10011010 over a link that uses CRC error checking with the divisor polynomial . What is the signal that would be sent? remainder = 1 signal = 10011010 001 (4 points) With that divisor polynomial, is it possible to catch all possible two bit errors? Why or why not? Yes. The divisor polynomial contains three terms, so it catches all two bit errors. Note that "burst error" means several _consecutive_ errors. In a two-bit error, the bits need not be consecutive. (4 points) In a byte-based framing scheme with variable-length frames, what happens if one of the special characters appears in the message? Is it possible for a framing error to result? We have to byte-stuff an escape character. Framing errors are always possible, but they cannot result from the presence of a special character in a message. (4 points) In a byte-based framing scheme with fixed-length frames, what happens if one of the special characters appears in the message? Is it possible for a framing error to result? We do nothing. In general the receiver can identify the special character because they arrive periodically. But during an initial sync, it is possible for a special character in a message to cause a framing error. (4 points) If a 10 Mbps Ethernet used 4B/5B encoding instead of Manchester encoding, what would the effective bandwidth be (assuming that collision detection and everything else still works)? 4B/5B is 80% efficient compared with Manchester which is 50% efficient. So that's 60% better, which means the effective bandwidth would be 16 Mbps. (4 points) Let's say that you wanted to use concurrent logical channels to implement reliable transmission on a 100 Mbps Ethernet with a 50 us maximum propagation delay. If the average packet size is 625 bytes, how many logical channels should you provide? The delay-bandwidth product is (100 us) * (100 Mbps) = 10,000 bits Packet size is 5000 bits. So two packets in flight is sufficient to keep the pipe full. Part Two: Reading Comprehension Read the article from Scientific American and answer the following questions. True or false (12 points) Senator Shelby and Rep. Cramer believe that the Patent Office should not have issued McEwan's patent. True The Patent Office yielded to pressure from Congress and made a decision that is consistent with the findings of the congressional report. False Ralph Petroff invented wide-band pulsed radio-frequency radar, and invested millions of dollars of his own money in Time Domain. False In ultrawideband pulsed radar, the duration of the pulses is less than one nanosecond. True Time Domain lost the case because it could not prove that McEwan was aware of their work as ``prior art.'' False Wide-band pulsed radio-frequency radar is already legal, but the FCC has not decided whether ultrawideband pulsed radar is legal. True Short answer (4 points) When used for wireless communication (as opposed to radar detection), what kind of modulation does Fullerton's system use? It distinguishes between two ones and zeros by making the interval between pulses slightly longer or shorter. This is similar to both frequency and phase modulation. (4 points) Name two advantages of the McEwan system over conventional means of wireless communication. Low power consumption. Signal is stealthy. Many signals can operate in the same area without interfering. Part Three: Short answer questions Answer the following questions in 1-3 sentences. (4 points) What is the limiting factor that determines the baud rate for a given network? In other words, what would go wrong if we tried to run a network faster than its maximum baud rate? The limiting factor is the ability to distinguish between two signals with a very low error rate. If you push a network above its limit, the error rates climb quickly. (4 points) What is the primary advantage of SWS over Stop and Wait? Stop and Wait waits for each packet to be acknowledged before it sends the next, so it only sends one packet per round trip time. SWS keeps enough packets in flight so that the bandwidth of the network is fully utilized, which minimizes the total transfer time. (4 points) In an SWS scheme, why would the receiver refuse to accept a frame that is not in its current window? It may be a resend of a previously-received packet, which might be merely redundant, but it is also possible that it is a very old packet, from the previous revolution of the sequence numbers, so accepting it would be disastrous. Also, the receiver is contractually obligated to provide buffer space for packets in the window. It might not have sufficient additional buffer space for a packet outside the window. *Part Four: book problems Suppose the round trip time propagation delay for an Ethernet is 46.4 us. This yields a minimum packet size of 512 bits (464 bits corresponding to propagation delay + 48 bits of jam signal). (4 points) What happens to the minimum packet size if the delay time is held constant and the signaling rate rises to 100 Mbps? 46.4 us * 100 Mbps = 4640 bits 4640 bits + 48 bits = 4688 bits (4 points) What are the drawbacks to so large a minimum packet size? It imposes an overhead on small packets and wastes bandwidth. Consider a wireless LAN with a maximum distance of 15 m. (4 points) At what bandwidth would propagation delay (at a speed of 3 * 10^8 m/s) equal transmit delay for 125-byte packets? prop delay = 15 m / 3 * 10^8 m/s = 5 * 10^-8 s = 50 ns 125 bytes = 1000 bits 1000 bits / x b/s = 50 ns x = 2 * 10^10 bps = 20 Gbps (4 points) At 50 Mbps, for what packet size is the transmit delay equal to twice the propagation delay? 2 * prop delay = 100 ns = 0.1 * 10^-6 s x / 50 Mbps = 2 * prop x = 0.1 * 10^-6 s * 50 * 10^6 bps = 5 bits (4 points) What is the significance of the previous result for MAC? This is the minimum packet size required to do the kind of collision detection done on Ethernet and Aloha. I think I confused people with this question because you were thinking of wireless protocols like 802.11 that don't support collision detection. But not all wireless networks are like that. Sorry for the confusion, though. But first, we need to finish talking about MAC... Ethernet -------- Exponential backoff: 1) why make things random? To avoid pathological deterministic behavior. 2) why increase the delay with repeated failure? Acts as a simple form of congestion control. Sources sense load by frequency of collisions and throttle send rate when load is high. This system depends on well-behaved nodes. Bad guys can take unfair advantage. Sometimes a little randomness is not enough. See problem 37: A and B are sending streams of packets. Their first packets collide. They each choose a delay of either 0 or T. A wins (chooses 0), B loses (chooses T). A's packet takes exactly T, so A's second packet collides with B's first. a) What is the chance that B will lose again? A is choosing from 0, 1 B is choosing from 0, 1, 2, 3 8 possibilities -- A wins 5, B wins 1, 2 ties In the event of a tie, A still has better than 50/50, so as a lower bound, A wins 6 times out of 8 = 75% b) The next time around, A is choosing from 0, 1 B is choosing from 0, 1, 2, 3, 4, 5, 6, 7 16 possibilities -- A wins 13, B wins 1, 2 ties Now A's chances are better than 14/16 = 87.5% c) 15 * 31 * 63 ... -- -- -- 16 * 32 * 64 d) That frame ain't going nowhere. Token ring ---------- Question: to what degree are the following decisions arbitrary and to what degree are they dictated by characteristics of the underlying network? encoding: 802.5 and IBM... Manchester FDDI... 4B/5B (Page 133 interesting comment: 4B/5B is common on fiber) framing: 802.5 and IBM... illegal Manchester codes as control FDDI... 4B/5B control signals error checking: 802.5 and IBM... checksum FDDI... CRC (32 bit) reliability mechanism: 802.5 and IBM... dead man switches FDDI... 2nd fiber and optical bypasses MAC: token priorities: 802.5 and IBM... access control bits for priorities FDDI... synchronous and asynchronous traffic token maintenance: IBM uses a distributed algorithm to elect a monitor, but then the monitor acts as a central authority FDDI is completely distributed. Monitor activities are handled by bidding. Wireless -------- Spread spectrum sounds kind of cool. The article from SciAm seems to be an extreme form of spread spectrum wireless. Shannon's theorem: relationship between maximum theoretical bit rate and bandwidth/signal-to-noise C = B log2 ( 1 + S/N ) C = capacity in bits per second B = bandwidth in Hz S = average signal level N = average noise level Signal to noise ratios are given in dB = 10 * log10 (S/N) Converting dB to S/N is just algebra. Page 78 gives an example calculation using voice line as an example. Frequency hopping, direct sequence and chipping all sacrifice some available bandwidth for security. Side effect is that you can overlap signals in a collision domain with small probabilities of collision. Collision avoidance ------------------- New problems: 1) hidden nodes: A and C both want to talk to B, but they don't hear each other (nodes might send when they shouldn't) 2) exposed node: C hears B talking to A and doesn't know whether it is ok to talk to D (nodes might not send when they should) Solution: two-step protocol 1) send RTS (request to send) 2) get CTS (clear to send) 3) send Does this solve the problems? Hidden node: A and C send RTS in rapid succession, B replies to one (collision avoided, because RTS and CTS are smaller than the packets) A and C send at the same time, B doesn't reply, they try again after a random exponential delay Exposed node: C saw B's RTS but not the CTS from A, so it knows that it's signal will not reach A, so it can go ahead and send a RTS to D if D is in B's collision domain, it will not reply, otherwise C can go ahead and send to D Distribution system ------------------- This section belongs in the next chapter!