cs349 Lecture Notes Fall 2000 Week 4, Tuesday Exam next Tuesday. For today you should have answered questions 33, 36, 37 and 41 in Chapter 2. I will send the assignment for next time by email. 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. 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 Ethernet -------- CSMA/CD = carrier sense... nodes can distinguish between idle and busy link multiple-access... like a bus collision detect... if two nodes start transmitting at the same time, they can tell Great Ethernet mysteries 1) how does collision detection work? (if we could encode an extra bit on the network all the time, we would use it for data -- nothing is free) 2) why Manchester encoding? Arbitration ----------- Alternatives... If you can't detect collisions, then you need some form of bus arbitration. What wrong with the kind of bus arbitration they do on internal buses? It's centralized! Why are centralized solutions unacceptable in networks? The need for graceful degradation: if one of the devices in your machine breaks, it often doesn't matter if the rest of the machine keeps working if one node on a network goes down, it would be unacceptable for the whole network to come down (graceful degradation is the opposite of catastrophic failure) Wiring ------ Each node on an Ethernet has a transceiver, which connects the adaptor to the cable. "The wire" is actually a virtual wire that might be made up of thin coax, thick coax, twisted pair and repeaters, and hubs. The different kinds of wire all run at the same speed (10 Mbps for basic Ethernet), but have different maximum distances. 1) internal resistance dissipates the signal as heat 2) impedence dissipates the signal as E/M radiation (coax reduces this, as does twisting) 3) all the transceivers divert some of the signal But most importantly, The maximum distance determines the maximum delay, which determines the minimum message size. Collision domain ---------------- Every signal put on the wire goes to all the nodes, which means that if any two nodes put a signal on the wire at the same time, it will cause a collision. All the nodes that can collide with each other comprise a collision domain. Available bandwidth seen by any host depends on the number of hosts in the collision domain and the amount of traffic they generate. In practice, Ethernets seem to work well only up to loads of 30% (idle 70% of the time). Above that, the number of collisions significantly degrades performance. Look at the figure on page 118. What is the obvious improvement we might make in this design? 1) replace the repeaters with switches (what's the difference?) 2) hope for spatial locality in traffic patterns Encoding and framing -------------------- As I mentioned, Ethernet uses Manchester encoding, which is infuriatingly inefficient (the signal is twice as big as the message)! Why? Framing issues dominated by need for collision detection 1) 64 bit preamble 2) minimum 46 bytes data for minimum frame length 64 bytes 3) bit oriented framing, with a twist... (how do we detect the end?) (what if a preamble appears in the message?) 4) header contains src and dest addresses Ethernet addresses: unique 6-byte hardware ID (how many Ethernet cards can they make?) Adaptors are responsible for identifying frames addressed to them. (What do you call adapator that snags _all_ the frames?) (What are the implications for security within an Ethernet domain?) Arbitration ----------- No negotiation, just blast away. If detect interference, transmit jamming sequence and stop. In order to guarantee collision detection, A must transmit continuously for one (maximal) RTT (I don't quite see why this is true, but ok) and that's why they impose a maximum distance. 51.2 us at 10 Mbps = 512 bits.