cs398 Lecture Notes Spring 2000 Week 6, Thursday For today you should have written answers to questions 12, 13 and 14 at the end of Chapter 3. I will email the assignment for next time after class. Vocabulary ---------- As I understand it, and as I intend to use it: Switch: any kind of device that copies packets from one network to another without making any changes at the network protocol level Router: similar to a switch, except that it may make network protocol changes (i.e. from Ethernet to ATM) Repeater: brain-dead switch that forwards everything Bridge: a kind of switch with at least some of the following characteristics 1) sits on a broadcast medium like an Ethernet or wireless 2) infers network topology from traffic (also "learning bridge") 3) uses distributed algorithms to eliminate loops by deactivating edges 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! The Dave Cooley Show! --------------------- 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!