cs398 Lecture Notes Spring 2000 Week 5, Thursday For today you should have made an outline of the chapter, explaining in your own words what each of the four sections is about. You should have made a list of three questions that you think are interesting, that you don't know the answer to, and that will be answered in this chapter. And you should have read Section 3.1 in detail. For next time, please write answers to questions 1 and 10 at the end of the chapter. You should also read and think about questions 2 through 9. ----- Today 1) conclusion to Chapter 2 2) starting on Chapter 3! Token ring ---------- Question: to what degree are the following decisions arbitrary and to what degree are they dictated by characteristics of the underlying network? encoding: 802.5 and IBM... Manchester FDDI... 4B/5B (Page 133 interesting comment: 4B/5B is common on fiber) framing: 802.5 and IBM... illegal Manchester codes as control FDDI... 4B/5B control signals error checking: 802.5 and IBM... checksum FDDI... CRC (32 bit) reliability mechanism: 802.5 and IBM... dead man switches FDDI... 2nd fiber and optical bypasses MAC: token priorities: 802.5 and IBM... access control bits for priorities FDDI... synchronous and asynchronous traffic token maintenance: IBM uses a distributed algorithm to elect a monitor, but then the monitor acts as a central authority FDDI is completely distributed. Monitor activities are handled by bidding. 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. Collision avoidance ------------------- New problems: 1) hidden nodes: A and C both want to talk to B, but they don't hear each other (nodes might send when they shouldn't) 2) exposed node: C hears B talking to A and doesn't know whether it is ok to talk to D (nodes might not send when they should) Solution: two-step protocol 1) send RTS (request to send) 2) get CTS (clear to send) 3) send Does this solve the problems? Hidden node: A and C send RTS in rapid succession, B replies to one (collision avoided, because RTS and CTS are smaller than the packets) A and C send at the same time, B doesn't reply, they try again after a random exponential delay Exposed node: C saw B's RTS but not the CTS from A, so it knows that it's signal will not reach A, so it can go ahead and send a RTS to D if D is in A's collision domain, it will not reply, otherwise C can go ahead and send to D (Why are the RTS and CTS frames less likely to collide than the packets themselves?) Distribution system ------------------- This section belongs in the next chapter! 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 Datagram network ---------------- Every packet contains the address of the destination Since it is globally unique, it is often big (32 - 128 bits) The switches have routing tables that map destination addresses to output ports. (What kind of optimizations are necessary?) Characteristics 1) host can send anywhere anytime, with no prior warning or setup 2) sender has no guarantee that the network can deliver 3) successive packets may follow different routes (routing tables are updated dynamically) 4) often robust against single failures, if there are alternate routes Virtual Circuits ---------------- Two step: 1) connection setup (signalling) setup packet gets routed just as in connectionless network as it goes, each switch chooses a locally unique VCI on the way back, the switches learn the VCI chosen by their successors 2) data transfer phase each packet now needs to contain only the circuit identifier, which is small. it gets changes as it passes from switch to switch 3) teardown (frees the VCIs) Characteristics 1) some delay for setup 2) smaller headers 3) single point of failure (for virtual circuit, anyway) 4) depends on connectionless mechanism for setup 5) switches and receiver have the opportunity to reserve resources for this circuit, which makes congestion impossible contention: one packet is delayed (queued) while another occupies a link congestion: the queue exceeds the available buffer space and packets are dropped VC can eliminate congestion, at the cost of underutilizing network capacity (since a data flow will seldom use all of its reserved resources all the time). VC + SWS gives hop-by-hop flow control (each node will not send until the receiver has available buffer space) The alternative is end-to-end flow control, in which the sender is the only node that throttles the flow, usually with the goal of saturating the bottleneck node. Source routing -------------- Sender has to tell every router which port to forward the packet on. Has to know the network topology. Has to stuff all that info into a (now variable-length) header on every packet. This does not scale to large networks. Nevertheless IP provides this mechanism 1) with up to 9 hops 2) routers are free to ignore it, and most do Performance issues ------------------ General-purpose hardware may not be appropriate for switches 1) bandwidth limit: half the speed of the I/O bus or half the memory bandwidth, whichever is less 2) throughput limit: throughput = number of packets per second * packet size for small packets, often limited by software speed (reading headers, looking up routing table, etc.) (this is the first definition we have seen. note that it is not the same as bandwidth -- a switch that is throughput limited will not saturate the bandwidth of the outgoing links)