IP: Network LayerOverviewGoals and TasksRoutingSwitchingSwitching (cont.)Datagram v/s Virtual CircuitIssuesBasic IdeasAddressingExamplesFlat AddressingHierachical AddressesInternetworkingLayers 2 and 3Class-Based AddressesAddressesScalability ProblemClassless Internet Domain Routing (CIDR)CIDR (cont.)CIDR (cont.)CIDRCIDR (cont.)CIDR - SubnetsCIDR (cont.) Direct DeliveryCIDR (cont.) Indirect DeliveryAssigning IP address (Ideally)DHCP – Dynamic Host Configuration ProtocolDHCP (cont.)NATOverviewExampleHow it worksRoutingRouting Sub-FunctionsHierarchical Routing The internet has many Administrative DomainsHierarchical Routing Border RoutersHierarchical Routing Interdomain & IntradomainTypes of Routing ProtocolOverviewOverviewLink State ProtocolsOverviewLink State AdvertisementsLink State PacketsLSP - ExampleLSP - ExampleLSP - ExampleLSP - ExampleSome IssuesDijkstraDijkstraDijkstraDijkstra - Forwarding TableDistance Vector ProtocolBellman-FordBellman-FordBellman-FordWhy does this compute shortest paths?Counting to InfinityBad News Travels Slowly…Bad News Travels Slowly…Asynchronous Bellman FordOscillationsOscillations - ExampleLink State vs. Distance VectorNo clear winnerIP: Network Layer Overview Addressing RoutingTOC –IPOverview Goals and Tasks Routing Switching Issues Basic ideasTOC – IP –OverviewGoals and Tasks Goals of Network Layer Guide packets from source to destination Use network links “efficiently” (e.g., prefer shorter and fasterroutes) Addressing Agree on addressing scheme to identify nodes IP addresses are location-based (similar to telephone numbers) This structure reduces the information routers must keep Different types of addresses Routing Routers exchange information to “learn” network topology Routers then calculate good routes to the different destinations Routers store the results of these calculations in “routing tables” Different routing algorithmsTOC – IP – Overview – Goals and TasksRouting Definition Finding path from source to destination Types: Path based on Flow “Type or Traffic” Source/Destination Destination Å InternetA (S Æ D): 1, 2, 3B (S Æ D): 1, 2, 3C (S Æ D): 1, 4, 5, 3A (S Æ D): 1, 2, 3B (S Æ D): 1, 2, 3C (S Æ D): 1, 4, 5, 3Voice (S Æ D): 1, 2, 3Data (S Æ D): 1, 4, 5, 3Voice (S Æ D): 1, 2, 3Data (S Æ D): 1, 4, 5, 31122445533SSDDS’S’D’D’(S Æ D): 1, 2, 3(S’ Æ D’): 1, 4, 5, 3(S Æ D): 1, 2, 3(S’ Æ D’): 1, 4, 5, 3(S Æ D): 1, 2, 3(S’ Æ D): 1, 2, 3(S Æ D): 1, 2, 3(S’ Æ D): 1, 2, 3TOC – IP – Overview – RoutingSwitching Definition Sending the bits along the path Approaches Circuit (Telephone; Lightwave) Packet Virtual Circuit (ATM) Datagram (Ethernet, IP) Notes A circuit or VC can be a link in an IP network An Ethernet LAN can be a link in an IP networkTOC – IP – Overview – SwitchingSwitching (cont.)Datagram v/s Virtual Circuit Datagram routing Each packet to be forwarded independently Virtual Circuit Each packet from same “flow” uses same route More state (pick the “right” granularity) QoS sensitive networks use VC’s and signaling Find a route that has the resources available for the connection. “Reserve” the resources before sending data packetsTOC – IP – Overview – SwitchingIssues Scalability [great in IP] Millions of nodes Routing tables should remain “small” Updates should be manageable Topology Changes [good in IP] Routers compute new routes as topology changes Changes should not affect most tables Performance [poor in IP] Link utilization should be well-balanced [not in practice] Updates should be fast [not always] Ideally, some flows would have a guaranteed rate [no] Network should detect configuration errors or other errors [no] Network should protect itself against attacks [no]TOC – IP – Overview – IssuesBasic Ideas Addressing Layer 2: Local scheme, typically flat Æ not scalable Layer 3: Location based and hierarchical Æ scalable Temporary addresses for mobile nodes Network Address Translation to reuse addresses Routing Route is based on destination only (roughly: shortest path) Network decomposed into domains Interdomain routing: Uses a path-vector algorithm Intradomain routing: Uses a link state or a distance vector algorithm Variations Multicast; P2P; Ad Hoc; Sensors; Content Distribution NetworksAddressing Examples Class-Based Addressing CIDR: Classless Interdomain Routing Assigning Addresses DHCP Network Address TranslationTOC – IP – AddressingExamples Flat Addressing Hierarchical Addressing Internetworking Layers 2 and 3TOC – IP – Addressing –ExamplesFlat Addressing331122554466ababcabcabbaba2: b3: a4: a5: a6: a2: b3: a4: a5: a6: a1: a3: b4: b5: b6: b1: a3: b4: b5: b6: b1: a2: b4: c5: c6: c1: a2: b4: c5: c6: c1: a2: a3: a5: c6: b1: a2: a3: a5: c6: b1: a2: a3: a4: a5: b1: a2: a3: a4: a5: bAddress Ports1: a2: a3: a4: a6: b1: a2: a3: a4: a6: bRouting Table: One per nodeDestination Æ Exit PortAddresses are arbitrary; not based on topology (e.g., Ethernet)N nodes Î N -1 entries in every routing table; not scalableTOC – IP – Addressing – Examples –FlatHierachical Addresses1.11.11.21.21.31.32.22.22.12.12.32.3ababcabcabbaba1.3: bDefault: a1.3: bDefault: a1.2: a1.3: bDefault: c1.2: a1.3: bDefault: c2.2: c2.3: bDefault: a2.2: c2.3: bDefault: a2.3: bDefault: a2.3: bDefault: a1.2: aDefault: b1.2: aDefault: b2.2: bDefault: a2.2: bDefault: aAddresses are arranged based on topology (e.g., IP)Few entries in each routing table; scalableTOC – IP – Addressing – Examples – HierarchicalInternetworkingRecall the basic internetworking scheme of IP:1.4x1.7y2.5z2.4u3.6v3.8w1.2t1.*: localDefault: y1.*: localDefault: y1.2: t1.7: y1.2: t1.7: yIPLocalx Æ y | 1.4 Æ 3.8 | dataz Æ u | 1.4 Æ 3.8 | datav Æ w | 1.4 Æ 3.8 | dataabda1.*: local4.*: bDefault: a1.*: local4.*: bDefault: a1.4: x1.7: y1.4: x1.7: yTOC – IP – Addressing – Examples – InternetworkingLayers 2 and 3EthernetSwitchEthernetSwitchRouterpPhy PhyPhy PhyPhyTransportApplicationPhyTransportApplicationPhy PhyDestination Address B Æ Local to port pLocal address B Æ Layer 2 address wPhy
View Full Document