New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Special Topics

by: Alayna Veum
Alayna Veum

GPA 3.81

Yi-Luen Do

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Yi-Luen Do
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 8803 at Georgia Institute of Technology - Main Campus taught by Yi-Luen Do in Fall. Since its upload, it has received 31 views. For similar materials see /class/234005/cs-8803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

Similar to CS 8803 at

Popular in ComputerScienence


Reviews for Special Topics


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15
DNS Measurements Hua Huang C88803 NTM Outline quotDNS measurements at a root server Nevil Brownlee Kimberly Claffy and Evi Nemeth Proceedings of the IEEE GlobeCom San Antonio TX Nov 2001 quotDNS Performance and the Effectiveness of Caching J Jung and E Sit and H Balakrishnan and R Morris IEEEACM Transactions on Networking V10 n5 October 2002 quotDiversity in DNS Performance Measures R Liston and S Srinivasan and E W Zegura Proceedings Internet Measurement Workshop IMW Nov 2002 On the problem of optimization of DNS root servers placemen Tony Lee Bradley Huffaker Marina Fomenkov kc claffy Passive and Active Measurement Workshop PAM La J olla CA 2003 Outline quotDNS measurements at a root server Nevil Brownlee Kimberly Claffy and EVi Nemeth Proceedings of the IEEE GlobeCom San Antonio TX Nov 2001 Measurement Methodology Passive measurement Observe DNS traf c owing to and from F root name server F rootservers net located at PAIX Using tcpa ump to capture the entire DNS packets Data Collection Size Queries Distinct Q s DateTime Collection Length 36 GB 103 M 27 M 262 Jan 7 11 am 1 hour 59 GB 180 M 48 M 267 Jan 9 3 pm 2 hours 104 GB 291 M 45 M 155 Jan 8 1 pm 1 hour 338 MB 1 M 380 K 379 Jan 10 hourly 2M pkts 4 minus 690 MB 2 M 622 K 312 Jan 1217 1924 4M pkts 8 mins Access to a full set of error logs Denied attempts to dynamically update the root server Dropped queries that were received with source port 0 Query Rates Use netstat command to measure raw query rate Data 01062001 01162001 01252001 01312001 Work week query peak load 5000sec 93 of the queries were responded immediately 7 unanswered quires Quires from private address space no route back Malformed queries 0 256 queries speci ed in the header with only 1 query actually Big endian little endian byte order problem in the nameserver code on some NT4Win95Win98 machines Jan 7 2001 1 hr trace 78000 queries from 1400 distinct nameservers with this bug Errors Identi ed Repeated queries 0 Not understand referral or SER VFAIL responses Average 154 times per second 0 0 1202001 a single host repeated over 2 million times in an hour SERVFAIL Private address space RFC 1918 0 23 of queries arriving at F root have source IP in RFC 1918 space 0 7 queries ask for hostnames in RFC 1918 o 7 queries from an RFC 1918 address ask about such an address Invalid top level domains TLDs 0 01072001 trace 1 hr 165 of the servers asked only invalid queries 0 Spelling errors 0 Local nameserver add local domain to complete the name wwwbcsWSCOOPERWSCOOPER Until 255 characters long Errors Identi ed cont d Bogus A queries Over 14 of root server s query load is due to queries that violate DNS speci cation 1218 queries with an IP address as a target 0 Causes identi ed Win2K resolver library snow white virus winim39l virus OpenB SD resolver and some DSL modem boxes Source port zero Dynamic Updates Requests trying to update root servers 0 When Win2K was 1st released it ooded the root servers with requests to update the root zone Other Anomalies Denial of service attacks Use root as a re ector ooding the attack target with answers to questions it did not ask Scan the 1P space but did not reverse IP address bytes when querying for an associated hostname 199170021024 PTR 5411193155inaddrarpa Microsoft s DNS problem Put all of their externally Visible nameservers on the same subnet 01242001 router miscon guration at Microsoft caused load on root for MS names to increase from 0 to 25 Outline 0 quotDNS measurements at a root server Nevil Brownlee Kimberly Claffy and EVi Nemeth Proceedings of the IEEE GlobeCom San Antonio TX Nov 2001 quotDNS Performance and the Effectiveness of Caching J Jung and E Sit and H Balakrishnan and R Morris IEEEACM Transactions on Networking V10 n5 October 2002 Data Collection 3quot A Collection software quot Egg 53 Derived from Minshall s i tcpdprl39v utility 5 Both DNS traf c and its WHWM 39g driving TCP connections m 3 traces I J L t4 H u EHIHLL milsm 392 39 a Firm quot l3939quot39quot39H 39I39 JEIEIHFIIHI 39 e W LntESrZEJI ET m39yig mnll 2 00am 0 h JFquot m ILunqu II I l 1 Euuur 3 h u I IIsh39n39i39u LI i 3939 600pm 120400 121100 mm 1 KaistmayOI quot39 500am 010300011000 EMIHIIIL Tamil I It 1 Fig 2 Schematic topology of the traced networks a MIT LCS There are 24 internal subnetworks sharing the border router b KAIST The collection machine is located at a point that captures all DNS traffic but only international traffic of other types Terminology Loomp Entire process of translating a domain name for a client application Query A DNS request packet sent to a DNS server Response A packet sent by a DNS server in reply to a query packet Answer A response from a DNS server that terminates the lookup by returning a requested mapping or an error indication Zero answer Is authoritative and indicates no error but has no ANSWER AUTHORITY or ADDITIONAL records Results i anti 1 wire I III I may l SLICEE39LI39E IIEWEI39 que 11 nm nes queryquot mUFEES mm is aware TCI connections 39 L V M5151 M Hi i39u Table l Basin trace etetistiee The percentages are 1with respect to tetel numbeer Imkups in each lreee GDP Effect of Referrals on Latency I ratemit LIE 1 warm 2 referrals I13 werequot l1 ELEH I15 I14 1 13 ISLE 393391 4 Ell I I 1 1393 10 1mm mum 13mm Latency 1151 Latency distribution versus number of referrals for the mitdecOO trace Percentage of lookups involving various numbers of referrals of referrals mitj an00 mitdecOO kaist mayOl 0 7462 8117 8609 1 2407 1786 1043 2 116 087 210 3 011 007 038 4 004 003 100 Effect of NS Records Caching on Latency 1 m w gt H HE cache mi 39 F w 39 lg NS ma a mis ng f ML I 39139 quot 4quot 15 miss 1f the rst query packet 1s sent 05 to one of the root or gTLD servers LL 7 1 B M e I 3 and e11c1ts a referral M I F I hit otherwise U3 quoti D n 3 g 70 of lookups in MIT traces are hits 1 l39 39I E l K rl I 3 r u V i M m I r I 1 L1 10 1m 1005 mum lEEIEFL iJ lat n 39 main Distribution of latencies for lookups that do and do not involve querying root servers EDP Retransmission i dqx HA iv i titerquoti RH h z 39 3 J 39 I r 39 D m a u u as 51 K IZI 39 ma quot1 DNS name servers should give up sooner M 39 eg after 2 or 3 retransmissions 12 quot1aquot uz nm39arad mit Emu Anaviarasd vc39 quot mit39 nEIEI waiarra D I mi putquot Equmtarr39a l X 2 4 E E 10 TIE H MIMI uf twainanimus Cumulative distribution of number of retransmissions for answered topmost curves and unanswered lookups Negative Responses Breakdown of Negative Responses by Cause as percentage of All Negative Responses Cause mit jan00 mitdec00 Nonexistent name 82459 42 150066 32 No reverse map for PTR 79725 41 249236 54 No RBL or similar entry 11552 6 36955 7 Loopback 7368 4 11310 2 Other oneword names 4785 3 9718 2 Invalid characters in query 1549 1 5590 1 Negative caching is not working as well as it could be Servers should not forward queries for unquali ed names when resolving queries for the Internet class Interaction With Root Servers mit jan mit decljizi Root Lutnekups dull 132 Ij 1 Equot u 2 WA 539 IT 6491 3 Reel Errclre I52 If2l3939quot39 ujt 7393 EN Ij Lquot n gTL D LCILEIRLIIIIS 4 l Ij 151quot n 539 532 95 I El 39tugl gTL DI EI39IUI39e 266 ISL Iquot u li jill Elf1391quot Table The tetal number mquot leehups that centacted met and gTL D zerxn39uem and the total number Ellquot failure gheewere re ceived The percentages are the tetal number atquot leekups in the he 15 27 of lookups sent to root name servers resulted in negative responses mistyped names bare host names eg loopback etc Many of these are automatically generated by incorrectly implemented or con gured resolvers Effectiveness of Caching Tracedriven Simulation Algorithm 2 databases Name database TTL database Simulation run 1 Randomly divide TCP clients into groups of size s Each group has a simulated cache indexed by the domain name 2 For each new TCP connection nd which group the client belongs to check the cache entry hit if the entry is there miss otherwise Two issues Usefulness to share DNS caches among many client machines 0 The extent to which different clients look up the same names Impact of choice of TTL on caching effectiveness Effect of Sharing 0n Hit Rate r mam 31391quot 39 32 3 m iH rt ma my Nit4mm l may magnum 7 la Most of the bene ts of sharing are Obtained with as few as 10 or 20 clients per cache IHit ram 13 1 00 ED ED Impact of TTL on Hit Rate Impact of TTL on Hit Rate mitdec00 E a u u 393 39 E E2 ha 4 4 5 V439quot a f 5 f l39 5 l 3 gmupalze 1i vZI 7 gm size 25 M 39 amp i 12111i U A 754139 r x Av 7 4wquot 3 Lu L x J 11 r I maul r n H c 7 339 039 5W M100 500 209039 2511 am 3500 4WD 4500 5060 m SM Effect of TTL on the hit rate is noticeable only for TTL lt 1000 sec Single clients look up same server multiple times in quick succession GDF TCP Connection Interarrivals mitdec00 X all Fx 2 w 1 wl Xlk 39 a a029ggp M 414 1 02 mlt dmm waifFILM PIE 7 i n I r i i H001 ELM 01 1 1D WEI MUD mmmmmnmm lfk l l l l al Ijrnn Pareto interarrival dist W point mass att 0 ocltl 9 infinite mean limited additional bene ts from longer TTL Outline quotDNS measurements at a root server Nevil Brownlee Kimberly Claffy and EVi Nemeth Proceedings of the IEEE GlobeCom San Antonio TX Nov 2001 quotDNS Performance and the Effectiveness of Caching J Jung and E Sit and H Balakrishnan and R Morris IEEEACM Transactions on Networking V10 115 October 2002 quotDiversity in DNS Performance Measures R Liston and S Srinivasan and E W Zegura Proceedings Internet Measurement Workshop IMW Nov 2002 Diversity in DNS Performance Measures 0 Goal Investigate the degree to which metrics for widearea DNS performance differ across locations in the Internet Noncached domain names only 0 Users experience longest lookup times for noncached names 0 Metrics investigated Completion and success rates of lookups Mean response time for completed lookups Root and gTLD servers favored by the sites Observed fraction of names that are aliases Distribution of TTLs across names 0 Metrics expected to be invariant across locations Fraction of aliases TTL distribution Fraction of names that are successfully resolved Measurement Methodology 0 Measurement locations 75 different Internet locations in 21 countries and territories Various connection technologies DSL PPP cable modem gigabit Ethernet etc J an 2002 and late Marchearly April 2002 0 Domain name sample Obtained by crawling the web w Larbz n crawler 14983 names w unique secondlevel domains to ensure measurements for noncached names only 0 Tool named name server log each event during name resolution w time stamp 46 hrs of continuous operation to complete on each site Bandwidth consumption Incoming 5Kbps outgoing 700bps Completion and Success Rates 0 Successful return an answer WWW with no error 0 Complete return an answer Xaxis sites ordered by the no of successful lookups yaXis of completed and successful lookups 0 Successful lookups 2 clusters J an higher rate MarchApril 39 TimeSCDSitiVC 2 sites w slightly lower rates Possibly locationsensitive higher no of retries for 316 mins Mean Response Time XaXis sites ordered by MRTc yaxis mean response time for completed lookups sec Large disparity in overall performance among each sites maXlRTc minminlRTc 24 Possible factors Connectivity Loss rate Perceived performance of root and gTLD servers Location in the network relative to other name servers Connectivity Ht l 39 I I quot h II 39 III H I l I I l l 539 i an an mean WE39EFIZII EE39 IIITIE 0 mmpraeu mumps EEG I I I I I39ll Minimum TilTE cI39cci plated Inchunts Eh2 Lower MINc 9 higher bandwidth connection andor close proximity to the Internet Correlation p 062 Connectivity does not suf ciently account for the higher MRTc Loss Rate Prim Fawn Ti m r l cm Fl 9 Imam 522 u I I 1 I 1 i II I i I II II If I l l I I I In rnl m in run Total rmm man mini mum Correlation p 050 Assume that retries are a good measure of loss rate loss rate is not a major factor affecting lookup time Loss rate varies dramatically across sites WEI17 m 41m a 2 ml 0 mm H39T MT rip F o 3 I RootgTLD Server Performance IIIHIHIHIHHI ISPs Em Improve performance it provides from gTLD servers for noncached names P am L39g IIII 9139139339555 ETI i Hill EHEEH EB Percentage of lookups Where each type of server was queried Root 70 gTLD 600 Others 984 Worst performance Root 141 sec gTLD 089sec Network Location Relative to Other Servers Xaxis mean response time of I p 03990 last queryresponse pair yaXis mean response time for quotquot completed lookups sec 3 we I Fixed set of servers Assumptlon39 Last servers queried along the Response to the xed set of critical path servers indicating distance 498 servers W same set of IP addresses across all sites Root Server Interactions Root servers favored by each site Xaxis root servers A M yaxis sites A site favors a root server if it sends greater than 10 of its root queries to that root server Favored by many sites Favored by few or none of the sites ADHI CGJKLM gTLD Servers Interaction gTLD servers favored by each site Xaxis gTLD servers A M yaxis sites Favored by many sites H 1 Favored by few sites J M Higher preferences for More variation in favoring fewer root servers than gTLD servers from site to gTLD servers site than in root servers Aliases and CNAMEs CNAME Redirections Number of Mean number percentage of redirections X CNAMEs with X redirections 1 3810 963 2 138 35 3 877 02 4 1 003 No of Different CNAMEs per Aliases Number of different Ninnber of aliases with CNAME mappings X X different mappings 1 4230 936 2 269 59 3 13 02 10 1 1 1 1 15 1 19 1 About 3960 26 of the names in the data set were aliases varied slightly across sites May due to variation of no of completed lookups No of names that are aliases is not location sensitive TTLs of Completed Queries Ranges of no of TTLs in each bin across all sites as a of the no of TTLs in the bin XaXis bin yaXis range as a of the mean Bin chosen based on the modes of the distribution of TTLs for one site Range difference bW the max no of TTLs and quotquot IIIII VuJJIJJJIJJI quot39quot3939 lquotNZHIA21 23 J2i ikai HW quotquotquot quot39 39F39LIia eachb1n Extremely small variation in the range of TTLs in each bin Distribution of TTLs is invariant across sites Outline quotDNS measurements at a root server Nevil Brownlee Kimberly Claffy and Evi Nemeth Proceedings of the IEEE GlobeCom San Antonio TX Nov 2001 quotDNS Performance and the Effectiveness of Caching J Jung and E Sit and H Balakrishnan and R Morris IEEEACM Transactions on Networking V10 115 October 2002 quotDiversity in DNS Performance Measures R Liston and S Srinivasan and E W Zegura Proceedings Internet Measurement Workshop IMW Nov 2002 On the problem of optimization of DNS root servers placemen Tony Lee Bradley Huffaker Marina Fomenkov kc claffy Passive and Active Measurement Workshop PAM La J olla CA 2003 Methodology L iLl I I II I i i iFEIiJIIJI I F i I V E t r u I l lill lhur u klll39I EL LillLIJL i Fig 1 The geographic locations of DNS root servers Servers marked with currently do not have colocated CAIDA skilter monitors A and J were colocated Data collection skitter Hosts colocated W DNS servers Iteratively send 52byte ICMP echo request packets incrementally increasing TTL values until a packet reaches the target host Record intermediate router IP addresses and RTT to destination July 14 2002 July 20 2002 3 to 7 RTTs per day for each replying destination Target List Goal Representative One destination in each globally routable pre x from IP addresses sending messages to the DNS root servers 100K200K addresses Tool dnsstat Passively monitor DNS queries at 8 root servers for 24 hours A D E F H I K M 2M client addresses 52K routable pre xes out of 118K pre xes in BGP table from March 18 2002 To add destinations uniformly across the IPv4 space Split each 8 pre x into 2 9 pre x and search for a destination in each half Repeat With next level till 21 level Criteria to select among multiple destinations Prefer IP addresses from old DNS Clients list in their previous studies Prefer IP addresses seen by the largest no of DNS root servers 140K destinations RTT Analysis Assumptions Conclusion drawn from the sample of clients are representative of the global DNS system Target list is representative of the overall population of the root servers clients RTT collected by probe ICMP packets are approximately the same as DNS response times actually experienced by root servers clients Valid only if request processing time lt propagation time Client selects the best lowest RTT available root server MedianRTT is a stable and reliable metric of the proximity between two Internet hosts Signi cance of Individual Root Servers 33933 527 IA InA ZEJZ IPT EU I IIrrI l39t 39 un t iJx MMCE Hr1xllfvnl39n H H rum 1 i H hrrn Mam Jenny 7393 I n mu 1395 39393939393939 39 lzik im Iquot39 I nan hmc1 L s H umu M0 kn Fluid IiZ 411 in r nlllt l The faster the curve drops along XaXis the fewer clients of this root server are affected the smaller increase in latency clients would experience Fig 2 Increase of latency caused by a root server removal The curves are CCDFs of the number of clients xaXis closest latency ARTE ARTT RTTnanilowest RTTnlowesl yaXis count of clients for which the increase in latency due to removal of their best root server is greater than x M only root in Asia most clients 2 lOOms increase in latency if removed EorH 80 clients lt 20ms increase in latency if removed Root Server Clusters t v Lumup LIE West TI It39ll l39L 1 l El39UCIl quot lTlI39IIJCII mI39wjt distance between S I and S 2 Servers in Group 1 Europe is less For each client set cliemk similar to each other than those in k1 K Group 2 and3 US European servers are geographically 1 S1 52 D61 52 imRTTk mRTTk more spread out than US servers Root Server Clusters amp Their Clients Heslu mllom prclcrl39 A rajml servers Qn39uu ps M on Hm I39 mots 2 e rs 2454 739 2113 4394139 liurt 2 llH liusl J WV 39 iii a I I I g l 39 m I1 31 I J 73933 I II quot1 4f 1j39139Ai39 it I II 1 H39quotu 311 39 quotILl I I IUI391 II39IAJ39NaL 139 Itiiti39a393 l 131I Iti3939uu Table 11 Root families amp corresponding subsets of destinations Percentages are relative to the total of each column Divide all hosts in the target list into 4 subsets corresponding to 4 groups of root servers Associate a host with a given group if its median RTT is lowest to one of the root servers in this group Group 1 Europe is most underserved US servers are best candidates for relocation to other regions of the world Impact of a Root Server Relocation How would the relocation of existing root servers affect the DNS performance for different groups of clients Use backup server for the Kroot Kpeer located in Amsterdam Collect 1 week data for all 11 root servers and Kpeer in July 2002 Suppose Kpeer replace 5 service for client n will Improve if mRT T nKPeer lt m RTTnSz39 deteriorate if mRTTnKPeer gt m RTTnSz Impact of a Root Server Relocation Fig 4 Latency change caused by aroot server relocation Negative curve 0 RootE G andH are suitable 71 an lt MRTTnS for any for relocation Fig 5 Combined distributions of1atency change due to potential relocation ofroot nam ervers I 7 the fewest number of clients 7 the clients Whose connection to Whose RTT would ammonia ag5 avoid xeszl imy 7 Combined latency distributions y 39 are mostly below xaxis


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.