11EE 122: Introduction ToCommunication NetworksFall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortizhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Some Questions & Answers• Q: Is the class full or can I enroll?• A: Class size: increased!Welcome to Daniel Killebrew,our new TA:• New section added: M 4-5PM, 299 Cory– But not next week (holiday)– Do attend one of the other sections next week (socketprogramming)• Q: Will the class be webcast?• A: No.23Goals for Today’s Class• Type of Networks– And the key concept of multiplexing• What’s a Protocol?4What Global (non-digital)Communication Network Do YouUse Every Day?Roughly speaking, how does it work?35What’s Another Such NetworkThat You Use Every Day?6• 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 w o rk47• 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 w o rkBro a d c a s tCo m m u n ica t io nNe t w o rk8• Information transmitted by any node isreceived 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 sharedcommunication medium (Multiple AccessProblem)Broadcast 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 w o rkSwit c h e dCo m m u n ica t io nNe t w o rkBro a d c a s tCo m m u n ica t io nNe t w o rk10• Information transmitted along a path ofintermediary nodes (“switches” or“routers”)• Basic issue: how the switches figure outthe next hop along the pathSwitched Communication Networks611• 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 w o rkSw it c h e dCo m m u n ica t io nNe t w o rkBro a d c a s tCo m m u n ica t io nNe t w o rkCirc u it -Swit c h e dCo m m u n ica t io nNe t w o rk12Circuit 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 done713Circuit 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 Philadelphia815Circuit Switching With Human OperatorTelephone Network• Almon Brown Strowger (1839 - 1902)– 1889: Invents the “girl-less, cuss-less” telephone system-- the mechanical switching system917Timing in Circuit SwitchingHost 1 Host 2Switch 1 Switch 2time18Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1time1019Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1Transmission delaytime20Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1Transmission delaytime1121Timing in Circuit SwitchingCircuit Establishment Host 1 Host 2Switch 1 Switch 2propagation delay between Host 1 and Switch1propagation delay between Host 1 and Host 2Transmission delaytime22Timing 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 delaytime1223Timing 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 delaytime24Circuit Switching• Node (switch) in a circuit switching networkincoming links outgoing linksNodeHow do the black and orange circuits share theoutgoing link?1325Circuit Switching: Multiplexing a Link• Time-division– Each circuit allocatedcertain time slots• Frequency-division– Each circuit allocatedcertain frequenciestimefrequencytime26Time-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 non-trivial!• 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 =14275 Minute BreakQuestions Before We Proceed?28• 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 w o rkSw it c h e dCo m m u n ica t io nNe t w o rkBro a d c a s tCo m m u n ica t io nNe t w o rkCirc u it -Swit c h e dCo m m u n ica t io nNe t w o rkPa c ke t -Sw it c h e dCo m m u n ica t io nNe t w o rk1529Packet 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) 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)HeaderDataTrailer (sometimes)30Packet Switching• Node in a packet switching networkincoming links outgoing linksNodeMemory1631Packet Switching: Multiplexing/Demultiplexing• Data from any conversation can be
View Full Document
Unlocking...