IP Addressing and ForwardingGoals of Today’s LectureIP Address (IPv4)Grouping Related HostsScalability ChallengeSlide 6Standard CS TrickHierarchical Addressing in U.S. MailHierarchical Addressing: IP PrefixesExpressing IP prefixesScalability ImprovedEasy to Add New HostsAddress AllocationClassful AddressingClassless Inter-Domain Routing (CIDR)CIDR: Hierarchal Address AllocationScalability: Address AggregationBut, Aggregation Not Always PossibleScalability Through HierarchyPre-CIDR (1988-1994): Steep GrowthCIDR Deployed (1994-1996): Much FlatterCIDR Growth (1996-1998): Roughly LinearBoom Period (1998-2001): Steep GrowthLong-Term View (1989-2005): Post-BoomObtaining a Block of AddressesFiguring Out Who Owns an AddressExample Output for 128.112.136.35Are 32-bit Addresses Enough?Hard Policy QuestionsPacket ForwardingHop-by-Hop Packet ForwardingSeparate Table Entries Per AddressSeparate Entry Per 24-bit PrefixSeparate Entry Classful AddressCIDR Makes Packet Forwarding HarderLongest Prefix Match ForwardingAnother reason FIBs get largeSimplest Algorithm is Too SlowPatricia Tree (1968)Even Faster LookupsWhere do Forwarding Tables Come From?How Do End Hosts Forward Packets?What About Reaching the End Hosts?ConclusionsIP Addressing and ForwardingCOS 461: Computer NetworksSpring 2009 (MW 1:30-2:50 in COS 105)Michael Freedmanhttp://www.cs.princeton.edu/courses/archive/spring09/cos461/1Goals of Today’s Lecture•IP addresses–Dotted-quad notation–IP prefixes for aggregation•Address allocation–Classful addresses–Classless InterDomain Routing (CIDR)–Growth in the number of prefixes over time•Packet forwarding–Forwarding tables–Longest-prefix match forwarding–Where forwarding tables come from2IP Address (IPv4)•A unique 32-bit number•Identifies an interface (on a host, on a router, …)•Represented in dotted-quad notation300001100 0010001010011110 0000010112 34 158 5Grouping Related Hosts•The Internet is an “inter-network”–Used to connect networks together, not hosts–Needs way to address a network (i.e., group of hosts)4hosthost hostLAN 1...hosthost hostLAN 2...router router routerWAN WANLAN = Local Area NetworkWAN = Wide Area NetworkScalability Challenge•Suppose hosts had arbitrary addresses–Then every router would need a lot of information–…to know how to direct packets toward every host5hosthost host...hosthost host...router router router1.2.3.4 5.6.7.8 2.4.6.8 1.2.3.5 5.6.7.9 2.4.6.91.2.3.41.2.3.5forwarding tableLAN 1LAN 2WAN WANa.k.a. FIB (forwarding information base)Scalability Challenge•Suppose hosts had arbitrary addresses–Then every router would need a lot of information–…to know how to direct packets toward every host•Back of envelop calculations–32-bit IP address: 4.29 billion (232) possibilities–How much storage?•Minimum: 4B address + 2B forwarding info per line•Total: 24.58 GB just for forwarding table–What happens if a network link gets cut?6Standard CS TrickHave a scalability problem?Introduce hierarchy…7Hierarchical Addressing in U.S. Mail•Addressing in the U.S. mail–Zip code: 08540–Street: Olden Street–Building on street: 35–Room in building: 208–Name of occupant: Mike Freedman•Forwarding the U.S. mail–Deliver letter to the post office in the zip code–Assign letter to mailman covering the street–Drop letter into mailbox for the building/room–Give letter to the appropriate person8???Hierarchical Addressing: IP Prefixes•IP addresses can be divided into two portions–Network (left) and host (right)•12.34.158.0/24 is a 24-bit prefix –Which covers 28 addresses (e.g., up to 255 hosts)900001100 0010001010011110 00000101Network (24 bits) Host (8 bits) 12 34 158 5Expressing IP prefixes1000001100 0010001010011110 0000010112 34 158 511111111 1111111111111111 00000000255255 255 0AddressMaskIP prefix = IP address (AND) subnet maskScalability Improved•Number related hosts from a common subnet–1.2.3.0/24 on the left LAN–5.6.7.0/24 on the right LAN11hosthost hostLAN 1...hosthosthostLAN 2...router router routerWAN WAN1.2.3.4 1.2.3.7 1.2.3.156 5.6.7.8 5.6.7.9 5.6.7.2121.2.3.0/245.6.7.0/24forwarding tableEasy to Add New Hosts•No need to update the routers–E.g., adding a new host 5.6.7.213 on the right–Doesn’t require adding a new forwarding-table entry12hosthost hostLAN 1...hosthosthostLAN 2...router router routerWAN WAN1.2.3.4 1.2.3.7 1.2.3.156 5.6.7.8 5.6.7.9 5.6.7.2121.2.3.0/245.6.7.0/24forwarding tablehost5.6.7.213Address Allocation13Classful Addressing•In the olden days, only fixed allocation sizes–Class A: 0*•Very large /8 blocks (e.g., MIT has 18.0.0.0/8)–Class B: 10*•Large /16 blocks (e.g,. Princeton has 128.112.0.0/16)–Class C: 110*•Small /24 blocks (e.g., AT&T Labs has 192.20.225.0/24)–Class D: 1110*•Multicast groups–Class E: 11110*•Reserved for future use•This is why folks use dotted-quad notation!14Classless Inter-Domain Routing (CIDR)15IP Address : 12.4.0.0 IP Mask: 255.254.0.000001100 0000010000000000 0000000011111111 1111111000000000 00000000Address Maskfor hosts Network Prefix Use two 32-bit numbers to represent a network. Network number = IP address + Mask Written as 12.4.0.0/15Introduced in 1993RFC 1518-1519CIDR: Hierarchal Address Allocation1612.0.0.0/812.0.0.0/1612.254.0.0/1612.1.0.0/1612.2.0.0/1612.3.0.0/16:::12.3.0.0/2412.3.1.0/24::12.3.254.0/2412.253.0.0/1912.253.32.0/1912.253.64.0/1912.253.96.0/1912.253.128.0/1912.253.160.0/19:::•Prefixes are key to Internet scalability–Address allocated in contiguous chunks (prefixes)–Routing protocols and packet forwarding based on prefixes–Today, routing tables contain ~200,000 prefixes (vs. 4B)Scalability: Address Aggregation17Provider 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/23ProviderRouters in rest of Internet just need to know how to reach 201.10.0.0/21. Provider can direct IP packets to appropriate customer.But, Aggregation Not Always Possible18201.10.0.0/21201.10.0.0/22201.10.4.0/24201.10.5.0/24201.10.6.0/23Provider 1 Provider 2Multi-homed customer (201.10.6.0/23) has two providers. Other parts of the Internet need to know how to reach these destinations through both providers.Scalability Through Hierarchy•Hierarchical addressing –Critical for scalable system–Don’t require everyone to know everyone else–Reduces amount of updating when something changes•Non-uniform hierarchy –Useful for heterogeneous networks of
View Full Document
Unlocking...