====================================================================== CMSC 417-F02 NOTES ON CHAPTER 5: LINK LAYER AND LANS SHANKAR ---------------------------------------------------------------------- Link Layer provides frame transmission service between network layer entities connected by a physical medium. Network layer entities x1 x2 ... xN x1 x2 Link layer entities y1 y2 ... yN y1 y2 Physical medium |_____|________| |______| Physical medium can be - wire-line (coax, twisted pair, optical fiber, string, ...) or wireless (RF, laser, acoustic, ...) - point-to-point or broadcast - switched or non-switched There is really another layer, the "physical layer", between the link layer and the physical medium. But for convenience, we treat this physical layer as part of the link layer. ---------------------------------------------------------------------- Frame structure: - physical layer header repeated 01 pattern (to allow receiver to synchronize) - start frame delimiter pattern of bits that does not occur inside frame - control information for MAC and other link layer control - destination address MAC address (also called NIC address or physical address). - user data - error detection/correction bits - end frame delimiter Link Layer Functions - Framing: - header/trailer fields to demarcate frame and for rx to acquire synch - bit/byte stuffing to preserve uniqueness of header/trailer - Addressing: - physical address, separate from IP addresses - called MAC address in broadcast-type links (802.3, 802.11, ..) - Media Access Control (MAC): - sharing/scheduling mechanism to access the physical medium. - static, dynamic (polling or random access) - Reliable delivery: - additional mechanisms (seq numbers, acks, retransmissions) - needed for error-prone physical media (wireless,telephone, ...) - not needed for fiber, coax, ... - Flow control - Error detection/correction Fundamental differences between point-to-point link layer protocol and host-to-host transport layer protocol: - link layer protocol is implemented on separate hardware (adaptor), because timing is critical and appropriate analog signal has to be transmitted/received. - link layer channels may lose but do not reorder or duplicate, whereas transport layer channels can lose, reorder, and duplicate. - rtt is constant in link layer channels (no cross traffic), but not in transport layer channels (cross traffic, host loading) ---------------------------------------------------------------------- Bit-level synchronization Rx is always listening for incoming analog signal, say X(t), matching X(t) against shifted versions of expected analog signal, say Y(t), where the shifts range over small phase offsets (to account for differences in clock offsets and propagation delays) and frequency offsets (to account for relative drift between rx clock and tx clock). By the time the physicial layer header has completely arrived, Rx should have matched its clock to the transitions in X(t). ---------------------------------------------------------------------- Error detection/correction codes Basic idea is to tx redundancy bits along with data so that the rx can check the combination of data and redundancy bits for inconsistencies. Concepts - Dataword: sequence of bits representing the user data. Assume d bit datawords (so 2^d possible datawords). - Codeword: sequence of data bits augmented with redundancy bits Assume r redundancy bits, so codeword is n=d+r bits long. - Code is defined by a function F such that given any dataword A = , F(A) returns the corresponding codeword bits B = . [Typically, the first d bits of B are the same as A and the last r bits are the redundancy bits.] - Given a code F with d bit datawords and d+r bit codewords, a d+r bit word X is said to be a VALID codeword if there is a dataword Y such that X=F(Y)l. Note that there are 2^(d+r) words of length d+r bits, and only 2^d of these are valid codewords. - Given two n-bit words, X = and Y = , the HAMMING DISTANCE between X and Y is the number of positions in which X and Y differ, i.e., (X(0) xor Y(0)) + (X(1) xor Y(1)) + ... + (X(n-1) xor Y(n-1)) - A code F has a distance D if - For every two valid codewords X and Y, the Hamming distance between X and Y is at least D. - There are two valid codewords X and Y such that the Hamming distance between X and Y is D. - A code with distance D can detect errors of less than D bits. That is, there exists a function G such that for any valid codeword X, for any d+r bit word Y obtained by flipping less than D bits in X, G(Y) returns true if Y=X and false otherwise. - A code with distance D can correct errors of less than D/2 bits. That is, there exists a function G such that for any valid codeword X, for any d+r bit word Y obtained by flipping less than D/2 bits in X, G(Y) returns X. - To put this into practice, one needs F to have adequate distance and G to be easily computable (and this is the hard part). --- Parity bit ----------------------------------------------------- - Single bit so that #1's in codeword is always even (even parity scheme) or always odd (for odd parity scheme). - detects single-bit errors. - Can provide 2-bit detection or 1-bit correction when used in 2D layout of data. E.g., if data word has n*m bits, then D1,1 D1,2 ... D1,m | x1 D2,1 D2,2 ... D2,m | x2 .... | . .... | . Dn,1 Dn,2 ... Dn,m | xm ------------------------|---- y1 y2 ... yn | z where - xi is parity bit for Di,1, Di,2, ..., Di,m - yj is parity bit for D1,j, D2,j, ..., Dn,j - z is parity bit for x1,...,xm (or y1,...,yn) Does this correct all 2-bit errors? Does this detect all 3-bit errors? Does this detect all 4-bit errors? --- Checksum --------------------------------------------------------- - Assuming data word has n*m bits, treat data as n m-bit integers. Add them up. Code is the negative of the sum (e.g., in 1's complement). --- Cyclic Redundancy Code (CRC) ------------------------------------- Defined by a generator G, which is a sequence of bits starting with 1. Let r be the number of bits in G minus 1. Given a data word of , the code is the remainder of (D*2^r)/G (i.e., append r zeros to the right of D and divide by G (modulo 2)): ___________________________ g0 g1 ... gr | D1 D2 D3 ... Dd 0 0 ... 0 Tx transmits D followed by the r remainder bits. Rx divides received (d+r) bit string by G; remainder should be zero. ---------------------------------------------------------------------- MAC - Needed except for a link with exactly one transmitter (which is very rare even if there is only one transmitter of user data, because link control information usually flows in both ways) - Assume N transmitters sharing a medium. - Ideal: throughput of N shared equally among all active transmitters --- Static MAC methods ---------------------------------------------- - Each tx gets fixed share of link (eg, 1/N). Good when most stations are active and have constant bit rate traffic. Bad for bursty traffic. - TDM (time division multiplexing) Each link is divided in time into "frames", each with N slots. Tx i can send only in slot i. - FDM (frequency division multiplexing) Each link is divided in frequency into N bands. Tx i can send only in band i. - CDM (code division multiplexing) Each tx i is associated with a unique M digit "code word", say m_i = , where each digit is +1 and -1. The codes of different transmitters are "orthogonal". To transmit data word D = (D1, ..., Dd), tx i sends D1*m_i, D2*m_i, ..., Dd*m_i where Dj*m_i is m_i if Dj=1 and M zeros if Dj=0. A rx that wants to receive from tx i multiplies the received signal X(t) with m_i. It is ensured (through other means) that all transmitters have the same phase (coinciding bit transitions) and signal strength at the receiver. Given this, the result X(t)*m_i is the transmitted bit pattern if X(t) was sent by tx i, otherwise the result is zero. --- Dynamic: random access methods ---------------------------------- - Allow nodes to send as "whenever" they have something to send. Make them back-off if collision occurs. Good for light bursty traffic (i.e., few stations active at any time). Bad for CBR traffic and for large number of active stations. - Slotted ALOHA - ALOHA - CSMA/CD - CSMA/CA --- Dynamic: polling ------------------------------------------------- - Master node polls transmitters, giving them an opportunity to transmit. Good for heavy bursty traffic (i.e., when a station has something to send, it has a lot to send). Bad for CBR traffic and for light bursty traffic. --- Dynamic: polling with random access ------------------------------ ---------------------------------------------------------------------- ETHERNET ---------------------------------------------------------------------- 802.11 ----------------------------------------------------------------------