15-441 Computer NetworkingReviewBridge ReviewWhat problems NOT solved by bridging?Switch/Router OverviewControl PlanesHierarchical AddressingIP Address Classes (Some are Obsolete)IP Address Problem (1991)Classless Inter-Domain Routing (CIDR) – RFC1338CIDR ExampleIP Addresses: How to Get One?Slide 13CIDR IllustrationWhat is the downside with CIDR?How To Do Longest Prefix MatchHost Routing Table ExampleRouting to the NetworkRouting Within the SubnetSlide 20Aside: Interaction with Link LayerSlide 22Internet ProtocolIP Service ModelIPv4 Header FieldsSlide 26Slide 27IP Delivery ModelIP FragmentationReassemblyFragmentation Related FieldsIP Fragmentation Example #1IP Fragmentation Example #2IP Fragmentation Example #3IP ReassemblyFragmentation and Reassembly ConceptsFragmentation is HarmfulInternet Control Message Protocol (ICMP)IP MTU Discovery with ICMPSlide 40Slide 41Slide 42Important Concepts15-441 Computer NetworkingLecture 9 – IP Packets9-26-06 Lecture 9: IP Packets 2Review•What problems does repeater solve?•What problems does bridge solve?9-26-06 Lecture 9: IP Packets 3Bridge Review•Problems solved •Physical reach extension•Multiple collision domains•How to move packets among collision domains? •forwarding table •How to fill the forward table•Learning bridge•How to avoid loops•Spanning trees9-26-06 Lecture 9: IP Packets 4What problems NOT solved by bridging? •Table size explosion •Single spanning tree for the network•Large convergence time9-26-06 Lecture 9: IP Packets 5LLSwitch/Router OverviewTwo key functions: •Control plane: Filling the forwarding tables consistently in all switches•Data plane: Switching packets from incoming to outgoing link by looking up the tableinput portoutput portLine CardLine CardLine Card9-26-06 Lecture 9: IP Packets 6Control Planes •What is the Ethernet control plane? •IP control planes: routing protocol•RIP, OSPF, BGP•This lecture is on data planes: how to switch packets9-26-06 Lecture 9: IP Packets 7Hierarchical Addressing•Flat would need switch table entry for every single host… way too big•Hierarchy much like phone system…•Hierarchy•Address broken into segments of increasing specificity•412 (Pittsburgh area) 268 (Oakland exchange) 8734 (Seshan’s office)•Pennsylvania / Pittsburgh / Oakland / CMU / Seshan•Route to general region and then work toward specific destination•Fixed boundary or dynamic boundary?9-26-06 Lecture 9: IP Packets 8IP Address Classes(Some are Obsolete)Network ID Host IDNetwork ID Host ID8 16Class A320Class B10Class C110Multicast AddressesClass D1110Reserved for experimentsClass E1111249-26-06 Lecture 9: IP Packets 9IP Address Problem (1991)•Address space depletion•In danger of running out of classes A and B•Why?•Class C too small for most domains•Very few class A – very careful about giving them out•Class B – greatest problem•Class B sparsely populated •But people refuse to give it back•Large forwarding tables•2 Million possible class C groups9-26-06 Lecture 9: IP Packets 10Classless Inter-Domain Routing(CIDR) – RFC1338•Allows arbitrary split between network & host part of address •Do not use classes to determine network ID•Use common part of address as network number•E.g., addresses 192.4.16 - 192.4.31 have the first 20 bits in common. Thus, we use these 20 bits as the network number 192.4.16/20•Enables more efficient usage of address space (and router tables) How?•Use single entry for range in forwarding tables•Combined forwarding entries when possible9-26-06 Lecture 9: IP Packets 11CIDR Example•Network is allocated 8 class C chunks, 200.10.0.0 to 200.10.7.255•Allocation uses 3 bits of class C space•Remaining 20 bits are network number, written as 201.10.0.0/21•Replaces 8 class C routing entries with 1 combined entry•Routing protocols carry prefix with destination network address•Longest prefix match for forwarding9-26-06 Lecture 9: IP Packets 12IP Addresses: How to Get One?Network (network portion):•Get allocated portion of ISP’s address space:ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... ….. …. ….Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/239-26-06 Lecture 9: IP Packets 13IP Addresses: How to Get One?•How does an ISP get block of addresses?•From Regional Internet Registries (RIRs) •ARIN (North America, Southern Africa), APNIC (Asia-Pacific), RIPE (Europe, Northern Africa), LACNIC (South America)•How about a single host?•Hard-coded by system admin in a file•DHCP: Dynamic Host Configuration Protocol: dynamically get address: “plug-and-play”•Host broadcasts “DHCP discover” msg•DHCP server responds with “DHCP offer” msg•Host requests IP address: “DHCP request” msg•DHCP server sends address: “DHCP ack” msg9-26-06 Lecture 9: IP Packets 14CIDR IllustrationProvider is given 201.10.0.0/21201.10.0.0/22 201.10.4.0/24 201.10.5.0/24 201.10.6.0/23Provider9-26-06 Lecture 9: IP Packets 15What is the downside with CIDR? 201.10.0.0/21201.10.0.0/22201.10.4.0/24201.10.5.0/24 201.10.6.0/23 or Provider 2 addressProvider 1 Provider 2201.10.6.0/239-26-06 Lecture 9: IP Packets 16How To Do Longest Prefix Match128.2/16101619128.32/16128.32.130/240 128.32.150/24default0/00•Traditional method – Patricia Tree•Arrange route entries into a series of bit tests•Worst case = 32 bit tests•Problem: memory speed is a bottleneck•How to do it faster? Bit to test – 0 = left child,1 = right child9-26-06 Lecture 9: IP Packets 17Host Routing Table Example•From “netstat –rn”•Host 128.2.209.100 when plugged into CS ethernet•Dest 128.2.209.100 routing to same machine•Dest 128.2.0.0 other hosts on same ethernet•Dest 127.0.0.0 special loopback address•Dest 0.0.0.0 default route to rest of Internet•Main CS router: gigrouter.net.cs.cmu.edu (128.2.254.36)Destination Gateway Genmask Iface128.2.209.100 0.0.0.0 255.255.255.255 eth0128.2.0.0 0.0.0.0 255.255.0.0 eth0127.0.0.0 0.0.0.0 255.0.0.0 lo0.0.0.0 128.2.254.36 0.0.0.0 eth09-26-06 Lecture 9: IP
View Full Document
Unlocking...