Page 1 CS162!Operating Systems and!Systems Programming!Lecture 13!Packet Switching"March 7, 2011!Ion Stoica!http://inst.eecs.berkeley.edu/~cs162!Lec 13.2!3/7! Ion Stoica CS162 ©UCB Spring 2011!Goals for Today"• Communication network taxonomy!– Circuit switching!– Packet switching!• Statistical multiplexing!Note: Some slides and/or pictures in the following are"adapted from notes by Vern Paxson, and Randy Katz."What Global (non-digital) Communication Network Do You Use Every Day?"Roughly speaking, how does it work?!Lec 13.4!3/7! Ion Stoica CS162 ©UCB Spring 2011!Postal System "• Write address"• Put stamp"• Close envelop"Drop letter"Take letter to local post office"• Verify postage"• “Route” letter "Take letter to destinationʼs postal office"Check destination address"Take letter to destination • Check address"• Open envelope"Page 2 Whatʼs Another Such Network That You Use Every Day?"Lec 13.6!3/7! Ion Stoica CS162 ©UCB Spring 2011!Examples of Other Information Networks"Fire signals Sending messages by birds Lec 13.7!3/7! Ion Stoica CS162 ©UCB Spring 2011!Other Network Examples"Lec 13.8!3/7! Ion Stoica CS162 ©UCB Spring 2011!• Communication networks can be classified based on the way in which the nodes exchange information:Taxonomy of Communication Networks!Communication NetworkPage 3 Lec 13.9!3/7! Ion Stoica CS162 ©UCB Spring 2011!• Communication networks can be classified based on the way in which the nodes exchange information:Taxonomy of Communication Networks!Communication NetworkBroadcastCommunication NetworkLec 13.10!3/7! Ion Stoica CS162 ©UCB Spring 2011!• Information transmitted by any node is received by every other node in the network!– Examples?!– Usually in LANs (Local Area Networks)!» E.g., Ethernet (classical), WiFi!» E.g., lecture! !• What problems does this raise?!• Problem #1: limited range!• Problem #2: privacy of communication!• Problem #3: coordinating access to the shared communication medium (Multiple Access Problem)!Broadcast Communication Networks !Lec 13.11!3/7! Ion Stoica CS162 ©UCB Spring 2011!• Communication networks can be classified based on the way in which the nodes exchange information:Taxonomy of Communication Networks!Communication NetworkSwitchedCommunication NetworkBroadcastCommunication NetworkLec 13.12!3/7! Ion Stoica CS162 ©UCB Spring 2011!• Information transmitted along a path of intermediary nodes (“routers” or “switches”)!• Basic issue: how the routers figure out the next hop along the path!Switched Communication Networks !Page 4 Lec 13.13!3/7! Ion Stoica CS162 ©UCB Spring 2011!• Communication networks can be classified based on the way in which the nodes exchange information:Taxonomy of Communication Networks!Communication NetworkSwitchedCommunication NetworkBroadcastCommunication NetworkCircuit-SwitchedCommunication NetworkLec 13.14!3/7! Ion Stoica CS162 ©UCB Spring 2011!Circuit Switching (e.g., Phone Network)"• Establish: source creates circuit to destination!– Nodes 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 done!Lec 13.15!3/7! Ion Stoica CS162 ©UCB Spring 2011!Circuit Switching"• Node (switch) in a circuit switching network!incoming links outgoing links Node How does the node connect the incoming link to the outgoing? Lec 13.16!3/7! Ion Stoica CS162 ©UCB Spring 2011!Telephone Network"• Alexander Graham Bell!– 1876: Demonstrates the telephone at US Centenary Exhibition in Philadelphia!Page 5 Lec 13.17!3/7! Ion Stoica CS162 ©UCB Spring 2011!17 Circuit Switching With Human Operator"Lec 13.18!3/7! Ion Stoica CS162 ©UCB Spring 2011!Telephone Network"• Almon Brown Strowger (1839 - 1902)!– 1889: Invents the “girl-less, cuss-less” telephone system -- the mechanical switching system!Lec 13.19!3/7! Ion Stoica CS162 ©UCB Spring 2011!Timing in Circuit SwitchingHost 1 Host 2 Switch 1 Switch 2 time Lec 13.20!3/7! Ion Stoica CS162 ©UCB Spring 2011!Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 timePage 6 Lec 13.21!3/7! Ion Stoica CS162 ©UCB Spring 2011!Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 Transmission delay time Lec 13.22!3/7! Ion Stoica CS162 ©UCB Spring 2011!Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 Transmission delay time Lec 13.23!3/7! Ion Stoica CS162 ©UCB Spring 2011!Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 propagation delay between Host 1 and Host 2 Transmission delay time Lec 13.24!3/7! Ion Stoica CS162 ©UCB Spring 2011!Timing in Circuit SwitchingInformation Circuit Establishment Transfer Host 1 Host 2 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 propagation delay between Host 1 and Host 2 Transmission delay timePage 7 Lec 13.25!3/7! Ion Stoica CS162 ©UCB Spring 2011!Timing in Circuit SwitchingInformation Circuit Establishment Transfer Circuit Teardown Host 1 Host 2 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 propagation delay between Host 1 and Host 2 Transmission delay time Lec 13.26!3/7! Ion Stoica CS162 ©UCB Spring 2011!Circuit Switching"• Node (switch) in a circuit switching network!incoming links outgoing links Node How do the black and red circuits share the outgoing link? Lec 13.27!3/7! Ion Stoica CS162 ©UCB Spring 2011!Circuit Switching: Multiplexing a Link"• Time-division!– Each circuit allocated certain time slots!• Frequency-division!– Each circuit allocated certain frequencies!time"frequency"time"Lec 13.28!3/7! Ion Stoica CS162 ©UCB Spring 2011!Time-Division Multiplexing/Demultiplexing"• Time divided into frames; frames into slots!• Relative slot position inside a frame determines to which circuit
View Full Document
Unlocking...