cs349 Lecture Notes Fall 2000 Week 5, Friday There was no assignment for today. For next Friday, read Chapter 3 and write answers for questions 1, 10, 12 and 13 at the end of the Chapter. -------------------- Exam 1 Solutions Excuse the residual latexisms. 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? {\tt 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 $M = $ {\tt 10011010} over a link that uses CRC error checking with the divisor polynomial $C(x) = x^3 + x + 1$. What is the signal $T$ that would be sent? remainder = 1 signal = 10011010 001 (4 points) With that divisor polynomial, $C(x) = x^3 + x + 1$, 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. (4 points) In a byte-based framing scheme with variable-length frames, what does the encoder do if one of the special characters appears in a message? Is it possible for a special character in a message to cause a framing error? The encoder has 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 simple byte-based framing scheme (not SONET) with fixed-length frames, what happens if one of the special characters appears in the message? Is it possible for a special character in a message to cause a framing error? The encoder does 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) Basic Ethernet has a signal rate of 20 Mbps, but because it uses Manchester encoding, the effective bandwidth is 10 Mbps. If it used 4B/5B encoding, what would the effective bandwidth be (assuming that collision detection and everything else still works)? 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 $\mu$s 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 Sliding Windows 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 a Sliding Window 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: homework problem reprise (4 points) Suppose the round trip time propagation delay for a 10 Mbps Ethernet is 51.2 $\mu$s. What determines the minimum packet size? Answer by completing this sentence: ``The minimum packets size has to be big enough to guarantee that...'' ...the sender is still transmitting when the jamming signal arrives, which makes it possible for both parties to detect the collision. (4 points) Ignoring the jamming signal, what is the minimum packet size for this network? 51.2 us * 10 Mbps = 512 bits. (4 points) If we switch to a 100 Mbps Ethernet, and increase the size of the minimum packet accordingly, are we likely to increase or decrease the frequency of collisions? Why? Actually, either answer is possible. I gave fill credit for any argument that made sense. If most packets are smaller than the minimum size, then the new, increased size means that there is more total traffic in the network, so there might be more collisions. But it is more likely that the total amount of traffic stays more or less the same, in which case the higher bandwidth means that the utilization of the network goes down, so there would be fewer collisions. Consider a wireless LAN with a maximum distance of 45 m. (4 points) At what bandwidth would propagation delay (at a speed of $3 \times 10^8$ m/s) equal transmit delay for 250-byte packets? 2000 b 45 m ------ = ------------- x b/s 3 x 10 ^8 m/s x = 13.3 Gbps or 13,333 Mbps 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. Chapter 3 --------- Problems with LANs 1) limited number of hosts 2) limited geographical distances 3) contention between hosts Switched networks are scalable in all these ways. Each switch contains multiple inputs and outputs. Model: workstation with more than one network card. packets arrive on one card; the task is to forward them to the next card Notice that what we called a frame last chapter has become a packet now! There is some logic to this -- a packet is more abstract than a frame. When a message crosses a switch, it is no longer carried by the same frame, but it is carried by the same packet. Fundamental problem: how does the switch know which output link to put a packet on? 1) connectionless (aka datagrams) every packet contains enough info to get there sender knows nothing 2) connection-oriented (aka virtual circuits) two phase -- setup is like connectionless, then data is sent with minimal information sender knows something 3) source routing packet contains _all_ the routing info sender knows everything