cs349 Lecture Notes Fall 2000 Week 2, Friday For today you should have made a high-level pass through Chapter 2 and started to read it in detail. You should have written answers for questions 2, 3, 4, and 5 (this will be homework 4). Also, you should have read the Java socket tutorial and started Homework 3. For Tuesday, write answers to questions 8a and 15 on pages 156-158, and finish Homework 3. Bonus point for anyone who can find the sentence in Section 2.4 that contains a typo and therefore makes no sense. Chapter 2 --------- Overview: fundamental problem is getting data across a single link. 2.1 -- 2.5 talk about the general mechanisms used by network-level protocols 2.6 -- 2.8 look at network-level protocols for three link structures bus-like (Ethernet) token-ring (FDDI) wireless (no well-known names yet) 2.9 talks about the hardware-level interface (network cards and device drivers) What are the high-level concepts we want to get out of this chapter? 1) Encoding, framing, error detection/correction and reliable delivery, media access control. In each case there is a range of possible solutions. The best choice is determined by the characteristics of the network. 2) What are the characteristics of the example networks that drive their design? Did the engineers make appropriate choices? Encoding -------- Let's talk about guns. How can you send a signal with a gun? 1) x-gun salute, where x is the message. In effect, this is a unary code. 2) two, distinguishable guns? different frequencies, amplitudes? 3) synchronous codes -- sender and receiver share a clock during each clock cycle, there either is or is not a gunshot Framing ------- How do sender and receiver agree on packet boundaries? Error detection --------------- How does the network detect bit and burst errors? Reliable transmission --------------------- How does the network deal with errors when it finds them? Hardware model -------------- Hosts and internal nodes look, for now, like general-purpose workstation architecture. Later we will look at the performance issues that drive the design of switches and routers. Memory bandwidth tends to be the limiting factor (not CPU speed). Links are media capable of carrying signals. Signals ------- Modulation is how we take a single bit and represent it with a signal: 1) amplitude modulation: loud is 1, quiet is 0 2) frequency modulation: high pitch is 1, low pitch is 0 3) phase modulation: sin is 1, cos is 0 For this class, we'll just assume: 1) there are two distinguishable signals 2) for a given medium, there is a maximum speed at which we can run the signal such that the distinctions are still clear (with very low error rates). This speed is the baud rate. The book talks about a variety of existing technologies and their performance. This is interesting material and you should read it. Some things to get from it: 1) calibrate yourself: you should have an idea about what typical bandwidths are like for local, wide-area, and wireless networks. These estimates are useful for back of envelope evaluations of ideas. 2) the last mile problem: what are the options for bringing the network into homes, and what are the market forces that affect the current state of this market. 3) for institutions like Wellesley, what are the options (and costs)? Encoding -------- An obvious mapping of bits onto signals is NRZ, in which one of the distinguishable states is 0 and the other is 1. Problems: 1) for many kinds of signals, there is no way to distinguish between the two states in absolute terms, only in relative terms. That is, you need lots of samples of "high" and "low" to distinguish between them statistically. The threshhold between them has to be estimated dynamically, so if we don't see any zeros for a long time, we might start looking at some of the ones suspiciously. This happens with people, too. It's called baseline wander. When your sample is biased, your estimate of the mean is inaccurate. 2) clock recovery. the endpoints use state transitions to keep their clocks in sync. Too long without a transition and we lose it. Example: if receivers clock is 1% faster than senders, then 100 consecutive 1s will appear to be 101 This is an example of a hardware issue that cannot be hidden by abstraction, but it can be expressed abstractly with rule such as: for this medium and this modulation and this baud rate, it is not "safe" to send more than three consecutive zeros or three consecutive ones. (where does the magic number 3 come from?) Solutions: 1) NRZI (another dumb name). 0 = keep signal the same 1 = change the signal In terms of calculus, what are we doing to the signal? Now the only stationary signal is many consecutive zeroes. 2) Manchester encoding. Book's explanation is bad. Better to think of it as sending two bits of signal for every one bit of message (or two signals for every bit). The drawback is obvious. 3) 4B/5B (four bits of message per 5 bits of signal) There are 32 five-bit codes. Get rid of all the ones that have more than three consecutive zeros. Now get rid of all the ones that have more than 1 leading zero or more than two trailing zeros. What does that guarantee? Were there other alternatives for this choice? Can we send this message using NRZ? (Do problem 2 on page 156.) Framing ------- How do sender and receiver agree on frame boundaries? What information does the network level attach to frames? (What is the relationship between packets and frames?) This is not my favorite section of the chapter -- makes things more complicated than necessary. Taxonomy: 1) variable length frames a) byte oriented b) bit oriented 2) fixed length frames With variable length frames, you need either 1) a special end character (sentinel) or 2) a header that contains the length In either case, we need a special character to indicate the beginning of a frame. What if the special character appears in the text? Need to create an escape sequence. What if the escape code appears in the text? Need an escape sequence for the escape code. Bit and byte stuffing: escape sequences introduce additional bytes in the message (overhead) SONET: fixed length frames Special code appears at the beginning of every frame. Receiver expects to see the special code at regular intervals. (I couldn't make any sense of pages 90 and 91, but I found a web page for a class at WPI that was very helpful: http://ece.wpi.edu/courses/ee535/hwk8cd95/dks1/dks1.html Here's the relevant part... Line Rate SONET line rate is a synchronous hierarchy that is flexible enough to support many different capacity signals. The STS-1/OC-1 line rate was chosen to be 51.84 Mbps to accommodate 28 DS1 signals and 1 DS3 signal. Also three STS-1 signals fit perfectly into a STM-1 signal. The higher level signals are obtained by synchronous multiplexing lower level signals. This signal can be represented by OC-N, where N is an integer. Currently the values of N are 1, 3, 12, 48 and 192. For example, OC-48 has a rate of 2488.320 Mbps, 48 times of OC-1 rate. STS-N Frame The STS-N signal is formed by byte interleaving N STS-1 signals. The transport overhead channels of the individual STS-1 signals must be frame-aligned before interleaving. Every STS-1 signal will have a unique payload pointer to indicate the location of each SPE, therefore the associated STS SPEs are not required to be aligned. STS-Nc Frame Super rate services such as the broadband ISDN has a rate of higher than that of STS-1 rate. Therefore, STS-1s are concatenated to form a STS-Nc signal which will be multiplexed, switched and transported through the network as a signal entity. The STS-Nc SPE consists of N * 87 columns and 9 rows of bytes. There is only one set of STS-1 path overhead is needed in the STS-Nc SPE. The other N-1 column that normally would be used for path overhead can be used for normal payload. Let's look at the similarities and the differences between the STS-3 and STS-3c frames. Both STS-3 and STS-3c have the same rate (155.52 Mbps) Both have the same transport overhead STS-3 has three separable STS-1 payloads while STS-3c has a single payload STS-3 may drop/add part of the payloads while STS-3c has to add/drop the entire payload (What are the pros and cons of a larger unit of retransmission?) Framing errors -------------- A data corruption that breaks the frame sentinel based: loss or creation of sentinel character counter based: corruption of length field fixed size: accidental appearance of special code inside the frame Error detection --------------- How does the network detect bit and burst errors? (as opposed to what?) parity checking: count the number of 1s. bit-stuff its parity checksum: byte-stuff the sum (modulo 2^k) of each n bytes (Page 96: add the word "not") CRC --- What you need to know: 1) mapping back and forth between messages and polynomials M(x) contains n+1 bits, maps to nth order polynomial. C(x) is a kth order polynomial (k+1 bits) The thing we send is P(x), an (n+k+1)th order polynomial that is divisible by C(x). Receiver checks that P'(x) is still divisible by C(x). Given M and C, how do we construct P? 1) The remainder of B/C is B-C (if B and C are the same order) 2) B-C is B XOR C (same condition) Given these rules we can figure out how to do long division on binary polynomials. Now we have an algorithm for the sender: 1) T = multiply M by x^k 2) find the remainder when T/C 3) subtract the remainder from T to get P Why does this work? Choose C such that the probability that P+E is divisible by C is small for common forms types of E. P+E is divisible only if E is divisible. For example, if E = x^i, then E cannot be divisible by C, provided that the kth and 0th terms are 1. Similar results: 1) if C has a factor with at least three terms, then we catch all E = x^i + x^j 2) if C contains the factor (x+1), we catch any odd number of errors 3) for any C we can catch an error burst with fewer than k bits (and most with more) Error correction ---------------- Pros and cons of error detection vs. error correction. Link characteristic that determines preference? Reliable transmission --------------------- How does the network deal with errors when it finds them?