11Midterm ReviewEE 122: Intro to Communication NetworksFall 2006 (MW 4-5:30 in Donner 155)Vern PaxsonTAs: Dilip Antony Joseph and Sukun Kimhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements / Pending Questions• Homework #3 out - due Nov 6– Note, due date a week later than originally announced– Homework #4 to be out Nov 6, tentatively due Nov 27• Additional office hours– Sukun this week: Friday 4-5PM– Me next week: Monday 1:30-3:30PM• Physical-layer design issues: EE 121 (Spring ‘07)• Identifier for electing a Spanning Tree root– Switch’s MAC address + configurable priority knobs– (thanks to Gene Zhang & Wikipedia & Mike Bennett)• How does switch know when spanning tree done?– It doesn’t, it just uses what it currently has3Robust Spanning Tree Algorithm• Algorithm must react to failures– Failure of the root node Need to elect a new root, with the next lowest identifier– Failure of other switches and links Need to recompute the spanning tree• Root switch continues sending messages– Periodically reannouncing itself as the root (1, 0, 1)– Other switches continue forwarding messages• Detecting failures through timeout (soft state)– Switch waits to hear from others– Eventually times out and claims to be the rootSee Section 3.2.2 in the textbook for details and another example4Moving From Switches to Routers• Advantages of switches over routers– Plug-and-play– Fast filtering and forwarding of frames• Disadvantages of switches over routers– Topology restricted to a spanning tree– Large networks require large ARP tables– Broadcast storms can cause the network to collapse– Can’t accommodate non-Ethernet segments (why not?)5Comparing Hubs, Switches & Routershubs switches routers traffic isolation no yes yes plug & play yes yes no optimized routing no no yes cut-through yes yes no 6Midterm Review• In-class next Monday• Closed book• You can have one regular-sized (8.5”x11”) sheet ofpaper with notes on both sides• No PDAs, calculators, electronic/Internet gadgets,smart cell phones, jeweler’s loupes, etc.• No Blue Books - all answers on exam sheets• Ensure legibility (pencil + eraser)27Fundamental Challenges for Networking• Speed-of-light• Desiring a pervasive global network• Need for it to work efficiently/cheaply• Failure of components• Enormous dynamic range– “no such thing as typical”• Disparate parties must work together• Rapid growth/evolution• Crooks & other bad guys8• Communication networks can be classified based onthe way in which the nodes exchange information:Taxonomy of Communication NetworksCo m munica t io nNe t workSwit che dCo m munica t io nNe t workBro adc astCo m munica t io nNe t workCirc uit -Swit che dCo m munica t io nNe t workPa c ke t -Swit che dCo m munica t io nNe t workDa t a gram Ne t w orkVirt u al Circ uitNe t work9Circuit Switching (e.g., Phone Network)• Establish: source creates circuit to destination– Node along the path store connection info– Nodes generally reserve resources for the connection– If circuit not available: “Busy signal”• Transfer: source sends data over the circuit– No destination address, since nodes know path• Teardown: source tears down circuit when doneincoming links outgoing linksNode10Timing in Circuit SwitchingInformationCircuit Establishment Transfer Circuit Teardown Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1propagation delay between Host 1 and Host 2Transmission delaytime11Time-Division Multiplexing/Demultiplexing• Time divided into frames; frames into slots• Relative slot position inside a frame determines to which conversation databelongs– E.g., slot 0 belongs to orange conversation• Requires synchronization between sender and receiver—surprisinglydifficult!• In case of non-permanent conversations– Need to dynamically bind a slot to a conversation– How to do this?• If a conversation does not use its circuit the capacity is lost!Frames0 1 2 3 4 5 0 1 2 3 4 5Slots = 12Packet 1Packet 2Packet 3Packet 1Packet 2Packet 3Timing of Datagram Packet SwitchingPacket 1Packet 2Packet 3processingdelay ofPacket 1 atNode 2Host 1 Host 2Node 1 Node 2propagationdelay betweenHost 1 and Node 1 transmission time of Packet 1at Host 1313Packet-Switching vs. Circuit-Switching• Critical advantage of packet-switching over circuitswitching: Exploitation of statistical multiplexing• Another: since routers don’t know about individualconversations, when a router or link fails, it’s easy to failover to a different path• A third: easier for different parties to link their networkstogether because they’re not promising to reserveresources for one another• However, packet-switching must handle congestion:– More complex routers– Harder to provide good network services (e.g., delay andbandwidth guarantees)• In practice, sometimes combined, e.g., IP over SONET14Protocol Standardization• Ensure communicating hosts speak the sameprotocol– Standardization to enable multiple implementations– Or, the same folks have to write all the software• Standardization: Internet Engineering Task Force– Based on working groups that focus on specific issues– Produces “Request For Comments” (RFCs) Promoted to standards via rough consensus and running code– IETF Web site is http://www.ietf.org– RFCs archived at http://www.rfc-editor.org (perHomework #1)• De facto standards: same folks writing the code– P2P file sharing, Skype, <your protocol here>…15Layering: A Modular Approach• Paritition the system– Each layer solely relies on services from layer below– Each layer solely exports services to layer above• Interface between layers defines interaction– Hides implementation details– Layers can change without disturbing other layersLink hardwareHost-to-host connectivityApplication-to-application channelsApplication16Drawbacks of Layering• Layer N may duplicate lower level functionality– E.g., error recovery to retransmit lost data• Layers may need same information– E.g., timestamps, maximum transmission unit size• Strict adherence to layering may hurt performance– E.g., hiding details about what is really going on• Some layers are not always cleanly separated– Inter-layer
View Full Document
Unlocking...