11Networks and ProtocolsEE 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 Berkeley2Some Questions & Answers• Q: Will there be reserved Lab times?A: We asked for these, but the scheduling folks areresisting.• Q: Can we do the projects in groups?A: The first two projects are to be done individually.We haven’t yet decided about the third project.• Q: What about the scheduling conflict with thefinals for CS 162 and CS 194?A: The instructors are aware of these and aretrying to work out a general solution. If need be,we will have an alternative time for those students.23Goals for Today’s Class• Type of Networks– And the key concept of multiplexing• What’s a Protocol?• Clients & Servers & Peer-to-Peer (time permitting)4• Communication networks can be classified based onthe way in which the nodes exchange information:Taxonomy of Communication NetworksCo m m u n ica t io nNe t wo rk35• Communication networks can be classified based onthe way in which the nodes exchange information:Taxonomy of Communication NetworksCo m m u n ica t io nNe t wo rkBro a d c a s tCo m m u n ica t io nNe t wo rk6• Information transmitted by any node isreceived by every other node in the network– Examples?– Usually in LANs (Local Area Networks) E.g., Ethernet, WiFi E.g., lecture!• What problems does this raise?• Problem #1: limited range.• Problem #2: coordinating access to the sharedcommunication medium (Multiple AccessProblem)Broadcast Communication Networks47• Communication networks can be classified based onthe way in which the nodes exchange information:Taxonomy of Communication NetworksCo m m u n ica t io nNe t wo rkSwit c h e dCo m m u n ica t io nNe t wo rkBro a d c a s tCo m m u n ica t io nNe t wo rk8• Information transmitted along a path ofintermediary nodes (“switches” or “routers”)• Basic issue: how the switches figure out thenext hop along the path• Example and properties of a global switchedcommunication network that you and millionsof others use every day?• Another example?Switched Communication Networks59• Communication networks can be classified based onthe way in which the nodes exchange information:Taxonomy of Communication NetworksCo m m u n ica t io nNe t wo rkSw it c h e dCo m m u n ica t io nNe t wo rkBro a d c a s tCo m m u n ica t io nNe t wo rkCirc u it -Swit c h e dCo m m u n ica t io nNe t wo rk10Circuit 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 done611Circuit Switching• Node (switch) in a circuit switching networkincoming links outgoing linksNodeHow does the node connect the incoming link tothe outgoing?Telephone Network• Alexander Graham Bell– 1876: Demonstrates the telephone at USCentenary Exhibition in Philadelphia713Circuit Switching With Human OperatorTelephone Network• Almon Brown Strowger (1839 - 1902)– 1889: Invents the “girl-less, cuss-less” telephone system-- the mechanical switching system815Timing in Circuit SwitchingHost 1 Host 2Switch 1 Switch 2time16Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1time917Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1Transmission delaytime18Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1Transmission delaytime1019Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1propagation delay between Host 1 and Host 2Transmission delaytime20Timing in Circuit SwitchingInformationCircuit Establishment Transfer Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1propagation delay between Host 1 and Host 2Transmission delaytime1121Timing 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 delaytime22Circuit Switching• Node (switch) in a circuit switching networkincoming links outgoing linksNodeHow do the black and orange circuits share theoutgoing link?1223Circuit Switching: Multiplexing a Link• Time-division– Each circuit allocatedcertain time slots• Frequency-division– Each circuit allocatedcertain frequenciestimefrequencytime24Time-Division Multiplexing/Demultiplexing• Time divided into frames; frames into slots• Relative slot position inside a frame determines to whichconversation data belongs– E.g., slot 0 belongs to orange conversation• Requires synchronization between sender andreceiver—surprisingly difficult!• 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 234 5 0 1 234 5Slots =1325• Communication networks can be classified based onthe way in which the nodes exchange information:Taxonomy of Communication NetworksCo m m u n ica t io nNe t wo rkSw it c h e dCo m m u n ica t io nNe t wo rkBro a d c a s tCo m m u n ica t io nNe t wo rkCirc u it -Swit c h e dCo m m u n ica t io nNe t wo rkPa c ke t -Swit c h e dCo m m u n ica t io nNe t wo rk26Packet 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 nodealong some path (Routing)• Once a node receives the entire packet, it stores it (briefly)and then forwards it to the next node (Store-and-ForwardNetworks)• Typically no capacity is allocated for packetsHeader DataTrailer (sometimes)1427Packet Switching• Node in a packet switching networkincoming links
View Full Document