Page 1Peter A. Steenkiste, SCS, CMU1Lecture 11IP addressing – Router InternalsPeter SteenkisteDepartments of Computer Science andElectrical and Computer EngineeringCarnegie Mellon University15-441 Networking, Spring 2006http://www.cs.cmu.edu/~prs/15-441Peter A. Steenkiste, SCS, CMU2Outline● IP addressing● CIDR● ICMP● Router architecturePeter A. Steenkiste, SCS, CMU3Internetworking● Multiple networks connected by routers.● Networks share some features» IP protocol, addressing, ..● But differ in many other ways» Technology, ownerships, usage policies, scale, ..HostHostHostHostHostHostHostHostHostHostHostHostPeter A. Steenkiste, SCS, CMU4Hop-by-Hop PacketForwarding in the InternetEthernetEthernetWANWANMixedEthernetMixedEthernetHostHostHostHost7..321Peter A. Steenkiste, SCS, CMU5IP Packet Forwarding● Each packet has an IP destination address● Each router has forwarding table of destination Æ next hop» Similar to Ethernet bridges and switches» What is different???●Forwarding table is created by a routing protocol» Manual solution would be error-prone» How is this done for Ethernet??Peter A. Steenkiste, SCS, CMU6Global Address ExampleReceiverPacketRSender234123412341R2R3R1RRR Æ 3R Æ 4R Æ 3RPage 2Peter A. Steenkiste, SCS, CMU7Router Table Size● Simple solution: one entry for every host» Several 100M entries and growing» Sometimes called “flat” addressing●Solution: use hierarchical addressing» Similar to postal addresses, telephone numbers, …●One entry for every organization» Every host in organization shares prefix» Requires careful address allocation●But how do split up the address bit?Network ID Host IDPeter A. Steenkiste, SCS, CMU8Traditional AddressClasses in IP v4● Each host has an internet address.» Example: 128.2.209.19● Addresses are hierarchical.» address contains hint about location●Original design: 4 classes of networks.● IP address space was assigned by the Internet Assigned Numbers Authority (IANA).» See http://www.iana.orgtypetypenetworknetworkhosthostA 0 7 24B10 14 16C 110 21 8D 1110 28Peter A. Steenkiste, SCS, CMU9Motivation for Address Structure● Hierarchical structure gives a hint about the location that can be used to simplify routing.» Compare with postal addresses» Routing in core based on network identifier only– reduces the size of the routing tables» But what happens when your machine moves?●Can assign subnet address spaces that are appropriate for the size of the organizations.» Spaces can be managed independently» A small number of large spaces; many smaller spaces» But what happens when your organization grows?●Class D corresponds to multicast.» Flat address structurePeter A. Steenkiste, SCS, CMU10Original IP Route Lookup● Address would specify prefix for forwarding table» Simple lookup● www.cmu.edu address 128.2.11.43» Class B address – class + network is 128.2» Lookup 128.2 in forwarding table» Prefix – part of address that really matters for routing● Forwarding table contains» List of class+network entries» A few fixed prefix lengths (8/16/24)● Did we really solve the table size problem?» 2 Million class C networks!Peter A. Steenkiste, SCS, CMU11Routing based on Network IdentifierAN 2AN 2ISP 2ISP 2ISP 1ISP 1ISP 3ISP 3AN 4AN 4AN 1AN 1 AN 5AN 5AN 3AN 3HostHostHostHostHostHostHostHostHostHostHostHostNet.HostNet IDNet IDNet IDNet IDNextNextNextNextForwarding TablePeter A. Steenkiste, SCS, CMU12Subnetting● Hierarchy can be extended to more than two layers.● Makes it possible to break up a network in multiple subnets.» provides flexibility to manage networks» packet forwarding between subnets is also done using routers, I.e. same as in Internet● Provides autonomy.» subnets inside network are not visible outside the network● Example: CMU has a number of independently managed subnets.» E.g. computer science1 0Network HostNetwork HostSubNetSubnet 1Subnet 3Subnet 2Page 3Peter A. Steenkiste, SCS, CMU13Subnetting Example● Assume an organization was assigned address 150.100● Assume < 100 hosts per subnet● How many host bits do we need?» Seven●What is the network mask?» 11111111 11111111 11111111 10000000» 255.255.255.128Peter A. Steenkiste, SCS, CMU14IP Addressing: Problems● IANA was running out of class B addresses.» Class-based addressing does not use space efficiently» A networks too large; C networks too small●Routing tables in the network core grow too fast as a result of the success of the Internet.» Too many networks!●Running out of IP addresses: too many hosts.» 32-bit address is not sufficient on the long run●Combination of solutions:» Classless Inter-Domain Routing (CIDR)» Dynamic address assignment» Network Address translation (NAT)» IPv6 with 128 bit addressPeter A. Steenkiste, SCS, CMU15CIDR Addressing:Variable Length Network ID● Length of network address is variable and specified using a netmask.» Generalization of the idea of subnetting● Can make the address space just large enough» Can merge a group of adjacent class C addresses to form a larger network address» Can break up a class B address into multiple network addresses● Must now have the netmask to identify the network id.» Address class bits no longer usefulNetwork Hosts0Network Hosts11 0Network Hosts1 0248239Peter A. Steenkiste, SCS, CMU16CIDR Example● ISP is allocated 8 class C chunks, 200.10.0.0 to 200.10.7.255» Allocation uses 3 bits of class C space» Remaining 21 bits are network number, written as 200.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 forwarding●ISPs get block of addresses from Regional Internet Registries (RIRs) » ARIN (North America, Southern Africa), APNIC (Asia-Pacific), RIPE (Europe, Northern Africa), LACNIC (South America)Peter A. Steenkiste, SCS, CMU17CIDR Addressing:ISP-based Allocation● Service provider hands out network addresses to its customers from a large block assigned to it.» To senders, the customers of the ISP look like subnets in the ISP● Routing entries for the ISPs customers can be merged in many cases.» Packets should be forwarded to that ISP, which will then forward them to the customer» Only the destination ISP has to distinguish between its customersISP 4ISP 4ISPISPCustomer1Customer1HostHostCustomer2Customer2HostHostCustomer3Customer3HostHostISP 5ISP 5ISP 3ISP 3ISP
View Full Document