This preview shows page 1-2-3-4-5-6-7-8-9-64-65-66-67-68-69-70-71-72-128-129-130-131-132-133-134-135-136 out of 136 pages.
Review Network FundamentalsAll You Need to Know in 1 SlideA More Conventional OverviewIP AddressingWhat is an Internetwork?Logical Structure of InternetInternet Protocol (IP)Problem 3: Internetwork DesignGetting to a DestinationAddressing in IPRouter Table SizeIP AddressesIP Address Classes (Some are Obsolete)Original IP Route LookupSubnet Addressing RFC917 (1984)SubnettingForwarding ExampleIP Address Problem (1991)IP Address Utilization (‘97)Important ConceptsClassless Inter-Domain Routing (CIDR) – RFC1338IP Addresses: How to Get One?IP ForwardingHost Routing Table ExampleRouting to the NetworkRouting Within the SubnetSlide 27Slide 28IP Packet FormatIP Service ModelIPv4 Header FieldsSlide 32Slide 33IP FragmentationReassemblyFragmentation and Reassembly ConceptsFragmentation is HarmfulInternet Control Message Protocol (ICMP)IP MTU Discovery with ICMPSlide 40IP RoutingSlide 42Graph ModelRoutes from Node AWays to Compute Shortest PathsOutlineDistance-Vector MethodDistance-Vector UpdateAlgorithmDistance Vector: Link Cost ChangesSlide 51Distance Vector: Split HorizonDistance Vector: Poison ReversePoison Reverse FailuresRouting Information Protocol (RIP)Slide 56Link State Protocol ConceptSending Link States by FloodingLink State CharacteristicsOSPF Routing ProtocolFlooding IssuesAdoption of OSPFComparison of LS and DV AlgorithmsSlide 64Slide 65Routing HierarchiesRouting HierarchyArea Hierarchy AddressingSlide 69A Logical View of the Internet?Internet’s Area HierarchyAS Numbers (ASNs)ExampleA Logical View of the InternetTransit vs. PeeringPolicy ImpactExternal BGP (E-BGP)ChoicesSolution: Distance Vector with PathInterconnecting BGP PeersHop-by-hop ModelExamples of BGP PoliciesBGP UPDATE MessagePath Selection CriteriaLOCAL PREFLOCAL PREF – Common UsesAS_PATHMulti-Exit Discriminator (MED)MEDSlide 90Decision ProcessSlide 92PerformanceSlide 94Flow Control and Error ControlA Naïve ProtocolAdding Flow ControlWindow Flow ControlBandwidth-Delay ProductDealing with Errors Stop and Wait CaseWhat is Used in Practice?Slide 102TCP PerformanceTCP Congestion ControlSingle TCP Flow Router without buffersSummary Unbuffered LinkSlide 107Slide 108Single TCP Flow Router with large enough buffers for full link utilizationSummary Buffered LinkLink-LayerSlide 112An Inter-networkInternetworking OptionsSwitch ArchitecturePacket Forwarding: Address LookupSlide 117EthernetEthernet MAC – Carrier SenseEthernet MAC – Collision DetectionEthernet MAC (CSMA/CD)Ethernet’s CSMA/CD (more)Ethernet Backoff CalculationCollisionsMinimum Packet SizeEthernet Collision DetectSlide 127ScaleSlide 129Problem 1 – Reconnecting LANsBuilding Larger LANs: BridgesTransparent BridgesFrame ForwardingLearning BridgesSpanning Tree BridgesPhysical-Layer (I’m tired, use Srini’s slides)1Review Network FundamentalsJeff Pang15-744 Networking, Spring 2005http://www.cs.cmu.edu/~dga/15-744/S07All slides stolen from Dave and Srini’s 15-441 class:http://www.cs.cmu.edu/~srini/15-441/F06/2All You Need to Know in 1 Slide email WWW phone...SMTP HTTP RTP...TCP UDP…IP ethernet PPP…CSMA async sonet... copper fiber radio...EthernetEthernetATMATMFramerelayFramerelayIP/SONETIP/SONETEthernetEthernetEthernetEthernet802.X802.XWirelessWirelessHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostHostTier 1 Tier 1Tier 2Tier 2Tier 2Tier 3The InternetBGPRIP, OSFPDistance VectorLink-StateEthernet, CSMA/CDBridges, Switches,Spanning TreeBandwidth x DelayTCP PerformanceModulationCodingFDMA, TDMAIP Blocks, CIDR, SubnetsLongest Prefix Match,Fragmentation, MTU3A More Conventional OverviewIP AddressingIP ForwardingIP Packet FormatIP RoutingPerformance CalculationsLink Layer StuffPhysical Layer Stuff4IP Addressing5What is an Internetwork?Multiple incompatible LANs can be physically connected by specialized computers called routersThe connected networks are called an internetwork»The “Internet” is one (very big & successful) example of an internetworkhosthost hostLAN 1...hosthost hostLAN 2...router router routerWAN WANLAN 1 and LAN 2 might be completely different, totally incompatible LANs (e.g., Ethernet and ATM)6Logical Structure of Internet»Ad hoc interconnection of networks–No particular topology–Vastly different router & link capacities»Send packets from source to destination by hopping through networks–Router connect one network to another–Different paths to destination may existhosthostrouterrouterrouterrouterrouterrouter7Internet Protocol (IP)Hour Glass Model»Create abstraction layer that hides underlying technology from network application software»Make as minimal as possible»Allows range of current & future technologies»Can support many different types of applicationsNetwork technologyNetwork applications email WWW phone...SMTP HTTP RTP...TCP UDP…IP ethernet PPP…CSMA async sonet... copper fiber radio...8Problem 3: Internetwork DesignHow do I designate a distant host?»Addressing / namingHow do I send information to a distant host?»What gets sent?»What route should it take?Must support:»Heterogeneity LAN technologies»Scalability ensure ability to grow to worldwide scalehosthost hostLAN 1...hosthost hostLAN 2...router router routerWAN WAN9Getting to a DestinationHow do you get driving directions?IntersectionsroutersRoadslinks/networksRoads change slowly10Addressing in IPIP addresses are names of interfaces»E.g., 128.2.1.1Domain Name System (DNS) names are names of hosts»E.g., www.cmu.eduDNS binds host names to interfacesRouting binds interface names to paths11Router Table SizeOne entry for every host on the Internet»440M (7/06) entries,doubling every 2.5 yearsOne entry for every LAN»Every host on LAN shares prefix»Still too many and growing quicklyOne entry for every organization»Every host in organization shares prefix»Requires careful address allocation12IP AddressesFixed length: 32 bitsInitial classful structure (1981) (not relevant now!!!)Total IP address size: 4 billion»Class A: 128 networks, 16M hosts»Class B: 16K networks, 64K hosts»Class C: 2M networks, 256 hostsHigh Order Bits0 10 110Format7 bits of net, 24 bits of host14 bits of net, 16 bits of host21 bits of net, 8 bits of hostClassABC13IP Address Classes(Some are Obsolete)Network ID Host IDNetwork ID Host ID8 16Class A320Class B10Class C110Multicast AddressesClass
View Full Document