Internet Addressing and Naming (Nick Feamster) January 23, 2008

Internet Addressing and Naming (Nick Feamster) January 23, 2008

Today: Addressing and Naming Internet Addressing – Step 1: Connecting a single network – Step 2: Connecting networks of networks IPv4 Addressing – – – – – Structure Scaling problems and CIDR (1994) Allocation and ownership Longest prefix match and Traffic Engineering Issues and design questions – More scaling problems and solutions Internet Naming – Today: DNS and the naming hierarchy – Research: Flat names Paper discussion: Jung et al. 2

Bootstrapping: Networks of Interfaces LAN/Physical/MAC address – Unique to physical interface (no two alike) – Flat structure datagram receiver link layer protocol sender frame frame adapter adapter Frames can be sent to a specific MAC address or to the broadcast MAC address What are the advantages to separating network layer from MAC layer? 3

ARP: IP Addresses to MAC addresses Query is IP address, response is MAC address Query is sent to LAN’s broadcast MAC address Each host or router has an ARP table – Checks IP address of query against its IP address – Replies with MAC address if there is a match Potential problems with this approach? Caching is key! – Try arp –a to see an ARP table 4

Interconnecting LANs: Bridging Receive & broadcast (“hub”) Learning Spanning tree (RSTP, MSTP, etc.) 5

Learning Bridges Bridge builds mapping of which port to forward packets for a certain MAC address If has entry, forward on appropriate port LAN B If no entry, flood packet A B C LAN A Potential problems with this approach? LAN C 6

Virtual LANs (VLANs) A single switched LAN can be partitioned into multiple “colors” Each color behaves as a separate LAN Better scaling properties – Reduce the scope of broadcast storms – Spanning tree algorithms scale better Better security properties 7

IPv4 Addresses: Networks of Networks Topological Addressing 32-bit number in “dotted-quad” notation – www.cs.duke.edu --- 152.3.140.5 130 207 7 36 10011000 00000011 10011000 00000101 Network (16 bits) Host (16 bits) Problem: 232 addresses is a lot of table entries Solution: Routing based on network and host – 152.3.0.0/16 is a 16-bit prefix with 216 IP addresses 8

Pre-1994: Classful Addressing 8 Class A 0 Network ID 16 24 32 Host ID /8 blocks (e.g., MIT has 18.0.0.0/8) Class B 10 /16 blocks (e.g., Duke has 152.3.0.0/16) Class C 110 /24 blocks (e.g., AT&T Labs has 192.20.225.0/24) Class D 1110 Multicast Addresses Class E 1111 Reserved for experiments Simple Forwarding: Address range specifies network ID length 9

Problem: Routing Table Growth Source: Geoff Huston Growth rates exceeding advances in hardware and software capabilities Primarily due to Class C space exhaustion Exhaustion of routing table space was on the horizon 10

Routing Table Growth: Who Cares? On pace to run out of allocations entirely Memory – Routing tables – Forwarding tables “Churn”: More prefixes, more updates 11

Possible Solutions Get rid of global addresses – NAT Get more addresses – IPv6 Different aggregation strategy – Classless Interdomain routing 12

Classless Interdomain Routing (CIDR) Use two 32-bit numbers to represent a network. Network number IP address Mask Example: BellSouth Prefix: 65.14.248.0/22 01000001 00001110 11111000 00000000 11111111 11111111 11111100 00000000 IP Address: 65.14.248.0 “Mask”: 255.255.252.0 Address no longer specifies network ID range. New forwarding trick: Longest Prefix Match 13

Benefits of CIDR Efficiency: Can allocate blocks of prefixes on a finer granularity Hierarchy: Prefixes can be aggregated into supernets. (Not always done. Typically not, in fact.) Customer 1 12.20.231.0/24 AT&T Customer 2 12.0.0.0/8 Internet 12.20.249.0/24 14

Forwarding: Longest Prefix Match Forwarding tables in IP routers – Maps each IP prefix to next-hop link(s) Destination-based forwarding – Each packet has a destination address – Router identifies longest-matching prefix forwarding table destination address 68.211.6.120 68.208.0.0/12 68.211.0.0/17 68.211.128.0/19 68.211.160.0/19 68.211.192.0/18 More on construction of forwarding tables in next lecture. 15

1994-1998: Linear Growth Source: Geoff Huston About 10,000 new entries per year 16

Around 2000: Fast Growth Resumes T. Hain, “A Pragmatic Report on IPv4 Address Space Consumption”, Cisco IPJ, September 2005 Claim: remaining /8s will be exhausted within the next 5-10 years. 17

Fast growth resumes Significant contributor: Multihoming Dot-Bomb Hiccup Rapid growth in routing tables Source: Geoff Huston 18

Multihoming Can Stymie Aggregation Verizon does not “own” 12.20.0.0/16. Must advertise the more specific route. AT&T 12.20.249.0/24 Verizon 12.20.249.0/24 12.20.249.0/24 Mid-Atlantic Corporate Federal Credit Union (AS 30308) “Stub AS” gets IP address space from one of its providers One (or both) providers cannot aggregate the prefix 19

Hacky Hack: LPM to Control Traffic 10 10 .1.0 .0 .1 / .0 .0 16 /1 7 Traffic for 10.1.0.0/17 6 1 / 0 .0 . 1 . 10 /17 0 . .0 1 . 10 A B D 10. 1.0 .0/1 10. 1.1 28. 6 0/1 7 6 1 / .0 /17 0 . .0 .1 8 0 1 12 . .1 0 Traffic for 1 C 10.1.128.0/17 20

The Address Allocation Process IANA AfriNIC http://www.iana.org/assignments/ipv4-address-space APNIC ARIN LACNIC RIPE Duke Allocation policies of RIRs affect pressure on IPv4 address space 21

/8 Allocations from IANA MIT, Ford, Halliburton, Boeing, Merck Reclaiming space is difficult. A /8 is a bargaining chip! 22

Address Space Ownership % whois -h whois.arin.net 130.207.7.36 [Querying whois.arin.net] [whois.arin.net] OrgName: Georgia Institute of Technology OrgID: GIT Address: 258 Fourth St NW Address: Rich Building City: Atlanta StateProv: GA PostalCode: 30332 Country: US NetRange: 130.207.0.0 - 130.207.255.255 CIDR: 130.207.0.0/16 NetName: GIT NetHandle: NET-130-207-0-0-1 Parent: NET-130-0-0-0-0 NetType: Direct Assignment NameServer: TROLL-GW.GATECH.EDU NameServer: GATECH.EDU Comment: RegDate: 1988-10-10 Updated: 2000-02-01 RTechHandle: ZG19-ARIN RTechName: Georgia Institute of TechnologyNetwork Services RTechPhone: 1-404-894-5508 RTechEmail: [email protected] OrgTechHandle: NETWO653-ARIN OrgTechName: Network Operations OrgTechPhone: 1-404-894-4669 - Regional Internet Registries (“RIRs”) - Public record of address allocations - ISPs should update when delegating address space - Often out-of-date 23

Do Prefixes Reflect Topology? Date: Sat, 11 May 2002 17:34:39 -0400 (EDT) Subject: BGP and aggregation To: [email protected] I have transit in 2 cities.I've been using non-contiguous IPs, so there's been no opportunity for aggregation. Having just received my /20 from ARIN, I'm trying to plan my network. Let’s say I split the /20 into 2 /21's, one for each city Missed opportunities for aggregation: non-contiguous prefixes Multiple geographic locations within the same prefix 24

Two Problems 10.1.0.0/16 10.1.0.0/16 10.1.0.0/16 IP space Geography Close/Identical Far Far Close/Identical 192.168.0.0/16 Problem Too Coarse-grained Too Fine-grained Case #1 [coarse-grained]: single prefix, multiple locations contiguous prefixes, multiple locations Case #2 [fine-grained]: discontiguous prefixes, same location 25

Case #1: Coarse-Grained Prefixes Location 1 Traffic for Location 1 10.1.0.0/16 10.1.0.0/17 A 10.1.0.0/16 10.1.0.0/16 10.1.128.0/17 B C 10.1.0.0/16 Location 2 Traffic does not enter AS as intended. Routing table entries map poorly to reachability. 27

Case #2: Fine-Grained Prefixes A 10.1.0.0/16 10.3.0.0/16 10.5.0.0/16 B 10.1.0.0/16 10.3.0.0/16 10.5.0.0/16 Single geographic location Inflation of routing table size. Increased routing table churn. 30

Take-home lessons Case #1: Coarse-grained prefixes – Negative effects on traffic control – Poor correlation with actual reachability – Finding: Single prefixes and contiguous prefixes can span very large distances – Potential for aggregation overstated 10.1.0.0/16 10.1.0.0/16 Case #2: Fine-grained prefixes – Causes many routing table updates 10.1.0.0/16 – Inflates routing table size – Finding: 70% of discontiguous prefix pairs from common AS and location – Changes to routing granularity warranted 192.168.0.0/16 31

IPv6 and Address Space Scarcity 128-bit addresses – Top 48-bits: global routing prefix – 16-bit subnet Identifier: aggregation within an AS – 64-bit Interface ID: 48-bit Ethernet 16 more bits 32

IPv6: Claimed Benefits Larger address space Simplified header Deeper hierarchy and policies for network architecture flexibility Support for route aggregation Easier renumbering and multihoming Security (e.g., IPv6 Cryptographic Extensions) 33

IPv6: Deployment Options Routing Infrastructure IPv4 Tunnels Dual-stack Dedicated Links MPLS Applications IPv6-to-IPv4 NAPT Dual-stack servers 34

IPv6 Deployment Status Big users: Germany (33%), EU (24%), Japan (16%), Australia (16%) 35

IPv6 over IPv4 Tunnels One trick for mapping IPv6 addresses: embed the IPv4 address in low bits http://www.cisco.com/en/US/tech/tk872/technologies white paper09186a00800c9907.shtml 36

DNS: Mapping Names to Addresses .edu h c ate g . c c . .edu h www c ate g . w ll-g o r t NS www.cc.gatech.edu NS burdell.cc .g Client Local DNS resolver Recursive query atech.edu root, .edu troll-gw.gatech.edu A1 30 .20 7.7 .36 burdell.cc.gatech.edu Iterative queries Note the diversity of Georgia Tech’s authoritative nameservers 37

Some Record Types A NS MX CNAME TXT PTR AAAA SRV 38

Caching Resolvers cache DNS responses – Quick response for repeated translations – Other queries may reuse some parts of lookup NS records for domains typically cached for longer – Negative responses also cached Typos, “localhost”, etc. Cached data periodically times out – Lifetime (TTL) of data controlled by owner of data – TTL passed with every record What if DNS entries get corrupted? 39

Root Zone Generic Top Level Domains (gTLD) – .com, .net, .org, Country Code Top Level Domain (ccTLD) – .us, .ca, .fi, .uk, etc Root server ({a-m}.root-servers.net) also used to cover gTLD domains – Increased load on root servers – August 2000: .com, .net, .org moved off root servers onto gTLDs 40

Some Recent gTLDs .info general info .biz businesses .name individuals .aero air-transport industry .coop business cooperatives .pro accountants, lawyers, physicians .museum museums 41

Do you trust the TLD operators? Wildcard DNS record for all .com and .net domain names not yet registered by others – September 15 – October 4, 2003 – February 2004: Verisign sues ICANN Redirection for these domain names to Verisign web portal What services might this break? 42

Protecting the Root Nameservers Sophisticated? Why did nobody notice? gatech.edu. 13759 NS trollgw.gatech.edu. Defense Mechanisms Redundancy: 13 root nameservers IP Anycast for root DNS servers {c,f,i,j,k}.root-servers.net – RFC 3258 – Most physical nameservers lie outside of the US 43

Defense: Replication and Caching source: wikipedia 44

DNS Hack #1: Reverse Lookup Method – Hierarchy based on IP addresses – 130.207.7.36 Query for PTR record of 36.7.207.130.inaddr.arpa. Managing – Authority manages IP addresses assigned to it 45

DNS Hack #2: Load Balance Server sends out multiple A records Order of these records changes per-client 46

DNS Hack #3: Blackhole Lists First: Mail Abuse Prevention System (MAPS) – Paul Vixie, 1997 Today: Spamhaus, spamcop, dnsrbl.org, etc. Different addresses refer to different reasons for blocking % dig 91.53.195.211.bl.spamcop.net ;; ANSWER SECTION: 91.53.195.211.bl.spamcop.net. 2100 IN A 127.0.0.2 ;; ANSWER SECTION: 91.53.195.211.bl.spamcop.net. 1799 IN TXT "Blocked - see http://www.spamcop.net/bl.shtml?211.195.53.91" 47

Highlights from Today’s Paper Jung et al., DNS Performance and the Effectiveness of Caching, ACM IMC, 2001 Three different traces: One from MIT, Two from KAIST – Joint analysis of DNS and TCP What types of queries will this miss? 48

Highlights and Thought Questions Load-balancing with A-records does not incur penalty – – – – Lower TTLs for A records do not affect performance Wide-area traffic not greatly affected by short TTLs on A records DNS performance relies more on NS-record caching Sharing of caches among clients not effective. Why? Referrals responsible for client-perceived latency 50% of Lookups not associated with any TCP connection – 10% follow from a TCP connection. Why? Negative response caching doesn’t appear to be effective – What effect do DNSBLs have on this? Lots of junk DNS traffic – 23% of all DNS queries received no answer – Half of DNS traffic is for these unanswered queries – 15%-27% of traffic at the root is bogus 49