cs398 Lecture Notes Spring 2000 Week 6, Tuesday For today you should have written answers to questions 1 and 10 at the end of Chapter 3. You should have read and thought about questions 2 through 9. And you should have prepared for the quiz! For next time, finish reading Chapter 3, and write answers for questions 12, 13 and 14. 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) Switches -------- 1) brain dead switch forward everything from one port to another (how is this different from a repeater?) 2) basic learning switch "If I know which port the sender is on and which port the receiver is on, I can tell whether I need to forward or not?" Every time a message arrives, I can tell that the sender is on the port the message came from. I can add an entry to a table. Since hosts move very occasionally, I should remove entries from the table periodically. If in doubt, forward. 3) loop-proof learning switch What if the network has a loop in it? (Why would it?) On startup, when everyone is forwarding everything, packets loop forever! Goal: reduce graph to a minimum spanning tree by removing edges. A bridge "removes an edge" by declining to forward a packet, even if it knows that the sender and receiver are on different ports. Challenge: need a DISTRIBUTED ALGORITHM for minimum spanning tree Characteristics of distributed algorithms 1) no centralized computation 2) all participants are symmetric (execute the same code) Intermediate goal: If all nodes (bridges) have unique ids, and if we all agree that one bridge is the "root" and if we all know our own distance from the root and the distance of our neighbors from the root THEN... Each bridge can decide independently whether it should forward packets from each of its ports to each of its ports. and The result will be a minimum spanning tree. (the fact that it is minimum is nice; the fact that it spans is necessary; the fact that it is a tree means that we have solved the problem -- no cycles) (Look at figure 3.13 on page 193) Here is a way of looking at this that is a little different from the book's presentation. The book takes the bridge's point of view -- to forward or not to forward. Let's take the packet's point of view. You are on a link that has more than one bridge attached. You know the distance of every bridge to the root. Which should you choose? What do you do if there is a tie? How much more complicated would this be if all the local networks had different performance characteristics? Distributing information ------------------------ Ok, that explains what the bridges do with information, and why it is optimal. How do the bridges _get_ the information in the first place. Periodic configuration messages. The root is the node with the lowest ID. Every node sends its neighbors a triplet with the following info: 1) who I think is the root 2) how far I am from the node I think is the root 3) who I am (my id) Look at a subgraph of Figure 3.13 with just B1, B2, B3, B5 During the first round, everyone thinks they're the root! Everyone sends (me, 0, me) When you get a configuration message, you do the following: 1) if the nominated root has a lower id than your current root, replace your root and recalculate your distance (you've just got word of a coup) 2) if the nominated root is the same as yours, but the distance is lower, update your distance (you've just found a shorter route to the root) 3) if the root and the distance are the same, but the sender has a lower id, start forwarding things to the new guy (the new route is no better, but we need to eliminate loops) So, after the first round, B2 and B5 accept B1 as their new king, but B3 still thinks B2 is the best thing since sliced bread. In the second round, B1 sends (B1, 0, B1) I am still the king, and I am zero distance from myself. B2 sends (B1, 1, B2) I am B2, and I proclaim my neighbor B1 the king. B5 sends (B1, 1, B5) I am B5, and I proclaim my neighbor B1 the king. B3 sends (B2, 1, B3) I am B3, and I think B2 is swell. After the second round, B2 finally realizes that B2 is not the true king. Furthermore, B2 realizes that when there is a packet on C, there is no reason to forward to A, and vice versa, so B2 declines to forward messages until the tables get updated, and that gets rid of the loop! Limitations of bridges ---------------------- 1) they don't scale The MST algorithm takes linear time (a number of rounds that is proportional to the diameter of the graph) Broadcast becomes infeasible/undesireable. 2) can't handle heterogeneity performance heterogeneity not too bad protocol heterogeneity is harder a) make bridges smarter, so they can read/write multiple protocols b) encapsulate the forwarding/routing level information within network level frames (Chapter 4) 3) transparency is a two-edged sword multiple hops masquerading as a single hop is a nice abstraction, but it hides details that affect design decisions at higher levels 1) possibility of dropped frames in bridges 2) more variability in latency 3) possible reordering This last point explains one of the confusing things about Chapter 2, which is that many link level protocols contain features to deal with these problems; problems that don't seem relevant at the link level, unless the link level is implemented by a network of links and bridges! Next time, ATM!