cs349 Lecture Notes Fall 2000 Week 3, Friday For next Tuesday, you should read about Ethernet and write answers for questions 33, 36, 37 and 41. CRC --- 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 T+E is divisible by C is small for common forms types of E. T+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? (what kind of errors? -- link model) Basic tool: automatic repeat request 1) receiver sends acknowledgements 2) sender retransmits after timeout (that's the "automatic" part) Stop and wait ------------- Sender sends one frame, waits for ACK. What are the possible outcomes? a) one frame, one ack (total = 2 RTT) b) frame lost, resend after timeout (total = timeout + 2 RTT) c) frame received, ACK lost, packet resent d) frame or ACK delayed, received after timeout How long should the timeout be? In both (c) and (d) the receiver gets the same packet twice in a row. How does it know whether it is a resend or a genuine duplicate? What is the primary problem with Stop and Wait? How can we calculate the number of frames necessary to keep the pipe full? What if frames are variable size? Sliding window -------------- Assume: 1) we know how many frames it takes to fill the pipe, and we want to make sure that under normal circumstances (no recent errors) it is full 2) the link delivers frames in order (cf. TCP reliable delivery) Sender: window consists of packets that have been sent, most of which have not been acknowledged LAR = last acknowledgement received LFS = last frame sent Start by sending enough frames to fill the pipe. When acknowledgements come in, tick them off. If the LAR gets incremented, we can send another frame. Receiver: window consists of the packets that we expect are probably in flight LFR: last frame received LAF: largest acceptable frame If we get a packet that is out of the acceptable window, we drop it: Primary reason: it might be a resend of a packet we already received Secondary reason: we want to maintain the invariant that there are at most SWS unacked packets in flight Variations: 1) selective ACKS: dumb name... ACK it when you get it (what's the advantage?) 2) cumulative ACKS: ACK 9 means we have received everything up to 9 (what's the advantage?) 3) negative ACKS: if we get 7 before 6, we NACK 6 (what's the advantage?) Handling of sequence numbers. Interesting. Read all about it. Concurrent Logical Channels --------------------------- I think this is very cool. The book's description is very terse. Assume that the bandwidth-delay product is 8 frame sizes. We want to be able to have 8 frames in flight at a time. We keep 8 stop-and-wait channels at the sender. Each keeps track of 1) busy or idle: that is, have you sent an unACKed frame? 2) sequence number of the current packet For each frame that needs to be sent 1) find an idle channel 2) send the packet with the channel number and the sequence number for that channel 3) set the channel to busy Receiver sends back an ACK with the channel and sequence numbers When the ACK comes in 1) check the sequence number for the appropriate channel 2) if it matches, set the channel to idle Overview of MAC --------------- 1) Ethernet: shared medium collision detection and probablistic, exponential backoff 2) Token ring: not physically a shared medium, but logically it is pass the conch 3) Wireless: definitely shared similar to Ethernet except topology is unpredictable hidden node problem