1 1 EE 122: Networks & Protocols Ion Stoica TAs: Junda Liu, DK Moon, David Zats http://inst.eecs.berkeley.edu/~ee122/fa09 (Materials with thanks to Vern Paxson, Jennifer Rexford, and colleagues at UC Berkeley) 2 Goals for Today’s Class Type of Networks And the key concept of multiplexing What is a Protocol? 3 What Global (non-digital) Communication Network Do You Use Every Day? Roughly speaking, how does it work? 4 What’s Another Such Network That You Use Every Day? 5 Communication networks can be classified based on the way in which the nodes exchange information:Taxonomy of Communication Networks Communication Network6 Communication networks can be classified based on the way in which the nodes exchange information:Taxonomy of Communication Networks Communication NetworkBroadcastCommunication Network2 7 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 8 Communication networks can be classified based on the way in which the nodes exchange information:Taxonomy of Communication Networks Communication NetworkSwitchedCommunication NetworkBroadcastCommunication Network9 Information transmitted along a path of intermediary nodes (“switches” or “routers”) Basic issue: how the switches figure out the next hop along the path Switched Communication Networks 10 Communication networks can be classified based on the way in which the nodes exchange information:Taxonomy of Communication Networks Communication NetworkSwitchedCommunication NetworkBroadcastCommunication NetworkCircuit-SwitchedCommunication Network11 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 12 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?3 Telephone Network Alexander Graham Bell 1876: Demonstrates the telephone at US Centenary Exhibition in Philadelphia 14 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 16 Timing in Circuit SwitchingHost 1 Host 2 Switch 1 Switch 2 time 17 Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 time 18 Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 Transmission delay time4 19 Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2 Switch 1 Switch 2 propagation delay between Host 1 and Switch1 Transmission delay time 20 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 21 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 time 22 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 23 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? 24 Circuit Switching: Multiplexing a Link Time-division Each circuit allocated certain time slots Frequency-division Each circuit allocated certain frequencies time frequency time5 25 Time-Division Multiplexing/Demultiplexing 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 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! Frames 0 1 2 3 4 5 0 1 2 3 4 5 Slots = 26 5 Minute Break Questions Before We Proceed? 27 Communication networks can be classified based on the way in which the nodes exchange information:Taxonomy of Communication Networks Communication NetworkSwitchedCommunication NetworkBroadcastCommunication NetworkCircuit-SwitchedCommunication NetworkPacket-SwitchedCommunication Network28 Packet Switching Data sent as chunks of formatted bit-sequences (Packets) Packets have following structure: Header and Trailer carry control information (e.g., destination address, checksum) Each packet traverses the network from node to node along some path (Routing) based on header info Usually, once a node receives the entire packet, it stores it (hopefully briefly) and then forwards it to the next node (Store-and-Forward Networks) Header Data Trailer (sometimes) 29 Packet Switching Node in a packet switching network incoming links outgoing links Node Memory 30 Packet Switching: Multiplexing/Demultiplexing Data from any flow can be transmitted at any given time Single flow can use the entire link capacity if it is alone How to tell them apart? Use meta-data (header) to describe data Note: for packet switching we use flow (instead of
View Full Document