Goals for Today Communication network taxonomy CS162 Operating Systems and Systems Programming Lecture 13 Circuit switching Packet switching Statistical multiplexing Packet Switching March 7 2011 Ion Stoica http inst eecs berkeley edu cs162 Note Some slides and or pictures in the following are adapted from notes by Vern Paxson and Randy Katz 3 7 Ion Stoica CS162 UCB Spring 2011 Lec 13 2 Postal System Verify postage Route letter Write address Put stamp Close envelop What Global non digital Communication Network Do You Use Every Day Drop letter Take letter to local post office Take letter to destination s postal office Roughly speaking how does it work Check address Open envelope 3 7 Page 1 Take letter to destination Ion Stoica CS162 UCB Spring 2011 Check destination address Lec 13 4 Examples of Other Information Networks What s Another Such Network That You Use Every Day Sending messages by birds 3 7 Other Network Examples Fire signals Ion Stoica CS162 UCB Spring 2011 Lec 13 6 Taxonomy of Communication Networks Communication networks can be classified based on the way in which the nodes exchange information Communication Network 3 7 Ion Stoica CS162 UCB Spring 2011 3 7 Lec 13 7 Page 2 Ion Stoica CS162 UCB Spring 2011 Lec 13 8 Taxonomy of Communication Networks Broadcast Communication Networks Information transmitted by any node is received by every other node in the network Communication networks can be classified based on the way in which the nodes exchange information Examples Usually in LANs Local Area Networks Communication Network E g Ethernet classical WiFi E g lecture Broadcast Communication Network 3 7 Ion Stoica CS162 UCB Spring 2011 3 7 Lec 13 9 Taxonomy of Communication Networks 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 Ion Stoica CS162 UCB Spring 2011 Lec 13 10 Switched Communication Networks Communication networks can be classified based on the way in which the nodes exchange information Communication Network Switched Communication Network Information transmitted along a path of intermediary nodes routers or switches Broadcast Communication Network Basic issue how the routers figure out the next hop along the path 3 7 Ion Stoica CS162 UCB Spring 2011 3 7 Lec 13 11 Page 3 Ion Stoica CS162 UCB Spring 2011 Lec 13 12 Circuit Switching e g Phone Network Taxonomy of Communication Networks Establish source creates circuit to destination Communication networks can be classified based on the way in which the nodes exchange information Nodes along the path store connection info Nodes generally reserve resources for the connection If circuit not available Busy signal Communication Network Transfer source sends data over the circuit Switched Communication Network No destination address since nodes know path Broadcast Communication Network Teardown source tears down circuit when done Circuit Switched Communication Network 3 7 Ion Stoica CS162 UCB Spring 2011 3 7 Lec 13 13 Circuit Switching Node Lec 13 14 Telephone Network Alexander Graham Bell Node switch in a circuit switching network incoming links Ion Stoica CS162 UCB Spring 2011 1876 Demonstrates the telephone at US Centenary Exhibition in Philadelphia outgoing links How does the node connect the incoming link to the outgoing 3 7 Ion Stoica CS162 UCB Spring 2011 3 7 Lec 13 15 Page 4 Ion Stoica CS162 UCB Spring 2011 Lec 13 16 Circuit Switching With Human Operator Telephone Network Almon Brown Strowger 1839 1902 1889 Invents the girl less cuss less telephone system the mechanical switching system 3 7 Ion Stoica CS162 UCB Spring 2011 17 3 7 Lec 13 17 Ion Stoica CS162 UCB Spring 2011 Timing in Circuit Switching Host 1 Switch 1 Switch 2 Timing in Circuit Switching Host 2 Host 1 Switch 1 Switch 2 Circuit Establishment time 3 7 Ion Stoica CS162 UCB Spring 2011 Lec 13 18 Host 2 propagation delay between Host 1 and Switch1 time 3 7 Lec 13 19 Page 5 Ion Stoica CS162 UCB Spring 2011 Lec 13 20 Timing in Circuit Switching Host 1 Switch 1 Switch 2 Timing in Circuit Switching Host 2 Host 1 Switch 1 Transmission delay propagation delay between Host 1 and Switch1 Circuit Establishment time 3 7 Ion Stoica CS162 UCB Spring 2011 time 3 7 Lec 13 21 Ion Stoica CS162 UCB Spring 2011 Timing in Circuit Switching Host 1 Switch 1 Switch 2 Host 2 Host 1 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 Circuit Establishment propagation delay between Host 1 and Host 2 propagation delay between Host 1 and Host 2 Information time Ion Stoica CS162 UCB Spring 2011 Host 2 Transmission delay propagation delay between Host 1 and Switch1 Transfer 3 7 Lec 13 22 Timing in Circuit Switching Transmission delay Circuit Establishment Host 2 Transmission delay propagation delay between Host 1 and Switch1 Circuit Establishment Switch 2 time 3 7 Lec 13 23 Page 6 Ion Stoica CS162 UCB Spring 2011 Lec 13 24 Timing in Circuit Switching Circuit Switching Node switch in a circuit switching network Host 1 Switch 1 Host 2 Switch 2 incoming links Node outgoing links Transmission delay propagation delay between Host 1 and Switch1 Circuit Establishment Transfer propagation delay between Host 1 and Host 2 Information How do the black and red circuits share the outgoing link time Circuit Teardown 3 7 Ion Stoica CS162 UCB Spring 2011 3 7 Lec 13 25 Each circuit allocated certain time slots Frequency division Frames Each circuit allocated certain frequencies frequency Slots 0 1 2 3 4 5 time Lec 13 26 Time Division Multiplexing Demultiplexing Circuit Switching Multiplexing a Link Time division Ion Stoica CS162 UCB Spring 2011 0 1 2 3 4 5 Time divided into frames frames into slots Relative slot position inside a frame determines to which circuit data belongs E g slot 0 belongs to red circuit Requires synchronization between sender and receiver surprisingly non trivial In case of non permanent circuits time Need to dynamically bind a slot to a circuit How to do this If sender does not send data the circuit s capacity is lost 3 7 Ion Stoica CS162 UCB Spring 2011 3 7 Lec 13 27 Page 7 Ion Stoica CS162 UCB Spring 2011 Lec 13 28 Administrivia Midterm next lecture Wednesday March 9th Closed book one page cheat sheet both sides Midterm Topics Everything up to last lecture excluding Introduction to Networking March 2nd Review session Today 6 8pm 306 Soda Hall 5min Break 3 7 Ion Stoica CS162 UCB Spring 2011 3 7 Lec 13 29 Ion Stoica CS162 UCB Spring
View Full Document
Unlocking...