Transcript Evaluation of the Proximity betw Web Clients and their Local DNS

Evaluation of the Proximity
between Web Clients and their
Local DNS Servers
Z. Morley Mao
UC Berkeley ([email protected])
Chuck Cranor, Fred Douglis, Michael Rabinovich,
Oliver Spatscheck, and Jia Wang
AT&T Labs--Research
Motivation

Content Distribution Networks (CDNs)


Try to deliver content from servers close to
users
Current server selection mechanisms


Uses Domain Name System (DNS)
Assumes that clients are close to their local
DNS servers – “orginator problem”
Verify the assumption that clients are close to
their local DNS servers
Measurement setup

Three components

1x1 pixel embedded transparent GIF image


A specialized authoritative DNS server


<img src=http://xxx.rd.example.com/tr.gif height=1
width=1>
Allows hostnames to be wild-carded
An HTTP redirector


Always responds with “302 Moved Temporarily”
Redirect to a URL with client IP address embedded
Embedded image request
sequence
1. HTTP GET request for the image
Client
[10.0.0.1]
2. HTTP redirect to
IP10-0-0-1.cs.example.com
Redirector for
xxx.rd.example.com
Content server for the image
4. Request to resolve IP10-0-0-1.cs.example.com
Local DNS server
5. Reply: IP address of content server
Name server for
*.cs.example.com
Measurement impact


Image (43 Byte) embedded at the end
of the page, requested last
Keynote measurement
Average download latency (sec)
Location
Without image
With image
World wide
US
1.17
1.04
1.31
1.14
Increased
overhead
12%
10%
Measurement Data
Site
Participant
1
2,3
4
att.com
Personal pages
(commercial domain)
AT&T research
5-7
University sites
8-19
Personal pages
(university domain)
Image hit
count
20,816,927
Duration
1,743
212,814
3 months
3 months
4,367,076
3 months
26,563
3 months
2 months
Measurement statistics
Data type
Unique client-LDNS associations
HTTP requests
Unique client IPs
Unique LDNS IPs
Client-LDNS associations where
Client and LDNS have the same IP address
Count
4,253,157
25,425,123
3,234,449
157,633
56,086
Top 10 busy ASes by request
count
AS number
Organization
Request count
7018
AT&T
876,741
701
UUNET
779,618
6172
@Home
614,341
5074
AT&T BMGS
239,989
1
BBN Planet
225,368
1239
Sprint
153,225
2688
IBM
145,158
3356
Level 3
143,823
4355
Earthlink
110,716
7015
RoadRunner
107,115
Proximity metrics:
1. AS, 2. network clustering

AS clustering


Observes if client and LDNS belong to the
same AS
Network clustering


Network cluster based on BGP routing
information using longest prefix match
Observes if client and LDNS belong to the
same network cluster
Proximity metric:
3. traceroute divergence
Probe machine
a
b
1
2
3
•Use the last point of
divergence
•Traceroute divergence:
Max(3,4)=4
1
2
3
4
client
Local DNS server
Proximity metric:
4. Roundtrip time correlation



Correlation between message
roundtrip times from a probe site to
the client and its LDNS server
The probe site represents a potential
cache server location
A crude metric, highly dependent on the
probe site
Aggregate statistics of
AS/network clustering
Metrics

AS clustering
# client
clusters
9,215
# LDNS
clusters
8,590
Total #
clusters
9,570
Network clustering
98,001
53,321
104,950
About 12,000 Ases


Observed close to 80% total ASes
440,000 unique prefixes

25% of all possible network clusters
Proximity analysis results:
AS, network clustering
Metrics
Client IPs
HTTP requests
AS cluster
64%
69%
Network cluster
16%
24%




AS clustering: coarse-grained
Network clustering: fine-grained
Most clients not in the same routing entity as
their LDNS
Clients with LDNS in the same cluster slightly
more active
Proximity analysis results:
Traceroute divergence

Probe sites:





NJ(UUNET), NJ(AT&T), Berkeley(calren),
Columbus(calren)
Sampled from top half of busy network clusters
Median divergence: 4
Mean divergence: 5.8-6.2
Ratio of common to disjoint path length

72%-80% pairs traced have common path at least
as long as disjoint path
Improved local DNS
configuration

For client-LDNS associations not in the
same cluster, does there exist a LDNS in
client’s cluster?
Metrics
Client IPs
Original Improved
HTTP requests
Original Improved
AS cluster
64%
88%
69%
92%
Network cluster
16%
66%
24%
70%
Clients using multiple LDNS

A single client IP can be associated using
multiple LDNS







First LDNS times out, second contacted
LDNS assigned dynamically through DHCP server
LDNS configuration with multiple IPs
Client IP reused by different users
Client IP is the address of NAT or proxy
Misconfiguration
Majority of clients are associated with a single
LDNS – 78%
Clients using 10 or fewer LDNS
# clients
(% total)
# LDNS
(avg # NAC)
% total HTTP
requests
% associations in
client’s NAC
2,524,939 (78.1) 1 (1)
51.8
20.3
522,228 (16.1)
2 (1.6)
22.4
12.1
123,524 (3.8)
3 (2.1)
10.4
6.6
41,422 (1.3)
4 (2.5)
4.9
4.7
13,469 (0.4)
5 (2.9)
2.5
4.9
4,555 (9.1)
6 (3.3)
1.8
6.7
1,590 (0.049)
7 (4.1)
1.3
9.9
713 (0.022)
8 (4.7)
0.7
13.6
461 (0.014)
9 (5.5)
0.7
14.2
273 (0.008)
10 (6.1)
0.5
14.0
Client IPs using large number
of LDNSs

Common domain names: (30-241 LDNS)

*.MIL, apnc*, *bbnplanet.com, *hsacorp.net,
*webcache.rcn.net, cache*.webcache.rcn.net,
cache0*.proxy.aol.com, cache.brightok.net,
cache*.ruh.isu.net.sa, *.onenet.net,
hh*.direcpc.com, cob-cache.r.state.mn.us,
mango.arctic.net, netcache.net.ca.gov,
proxy.*.netsetter.com, *.nortelnetworks.com,
rad.afonline.net, *.prserv.net, *.cisco.com,
ss*.co.us.ibm.com, thing5.csc.com,
*.wwwcache.ja.net
Example client IP
using large number of LDNSs

Client




Belong to marketscore.com:



216.34.56.12 (proxy.sjc.netsetter.com)
Using 241 LDNS
753 requests
Offers free browser plug-in for web acceleration
Using client’s LDNS to do name resolution on behalf of
client?
HTTP headers:



Via header: NetCache Network Appliance
X-forwarded-for: 10.104.1.115, 10.104.1.31
Client-ip: client IP address (dialup customers)
Top LDNS serving most clients
DNS name
# clients served
Organization
Ns?.worldnet.att.net
68000
AT&T
Ns1.us.prserv.net
42000
IBM
Nscache3.eng00.mindspring.net
23000
mindspring
Rns2.earthlink.net
17000
Earthlink
Lax1-dns.lax.netzero.net
13000
netzero
Dns1.mtry01.pacbell.net
12000
Pac bell
Ns.mia.bellsouth.net
12000
Bellsouth
Dialcache040.ns.uu.net
11000
UUNET
Ns2.rc1.sfba.home.com
12300
@home
Examination of clients from
individual ASes
Organization (AS #) AS cluster
Network cluster
No. Reqs
AT&T (7018)
10%
4%
876,741
UUNET (701)
78%
9%
779,618
@Home (6172)
96%
1%
614,341
BBN (1)
63%
48%
225,368
Sprint (1239)
70%
37%
153,225
IBM (2688)
3%
0.5%
145,158
UCB (25)
98%
34%
38,196
MIT (3)
99%
99%
6,341
Cornell (26)
99%
46%
2,341
CMU (9)
99%
94%
4,090
UTAustin (18)
98%
70%
12,878
Impact on commercial CDNs


Impact on server selection accuracy
Look for clients



With LDNS responds to queries
With a cache server in client’s cluster
Whether directed to a cache server in a
different cluster? – “misdirected”
Impact on commercial CDNs
AS clustering
CDN
CDN X
CDN Y
CDN Z
Clients with CDN server in
cluster
1,679,515
1,215,372
618,897
Verifiable clients
1,324,022
961,382
516,969
Misdirected clients
(% of verifiable clients)
(% of clusters occupied)
809,683
(60%)
(92%)
752,822
(77%)
(94%)
434,905
(82%)
(94%)
Clients with LDNS not in
client’s cluster
(% of misdirected clients)
443,394
354,928
262,713
(55%)
(47%)
(60%)
Impact on commercial CDNs
Network clustering
CDN
CDN X
CDN Y
CDN Z
Clients with cache
server in cluster
264,743
156,507
103,448
Verifiable clients
221,440
132,567
90,264
Misdirected clients
(% of verifiable clients)
(% of clusters occupied)
154,198
(68%)
(77%)
125,449
(94%)
(82%)
87,486
(96%)
(93%)
Clients with LDNS not in
client’s cluster
(% of misdirected
clients)
145,276
116,073
84,737
(94%)
(93%)
(97%)
Why choosing a cache in a
different cluster?


Even when both client and LDNS are in the
same cluster?
Possible reasons

Load-balancing algorithms using different metrics




E.g., network access costs
Caches are different
Clustering too coarse-grained
CDN mapping inaccuracies?
Lessons from study of
commercial CDNs

AS hop count is a bad metric for
closeness evaluation



too coarse-grained
Maybe better choosing a geographically
closer cache server in a different AS
For load-balancing, fault-tolerance, CDNs
sometimes return cache servers in two
different Ases
Related work

Measurement methodology
1.
IBM (Shaikh et al.)

2.
Univ of Boston (Bestavros et al.)



Assigning multiple IP addresses to a Web server
Differences from our work:

3.
Time correlation of DNS and HTTP requests from DNS
and Web server logs
Our methodology: efficient, accurate, nonintrusive
Web bugs
Proximity metrics

Cisco’s Boomerang protocol: uses latency from
cache servers to the LDNS
Conclusion

Novel technique for finding client and local
DNS associations


DNS based server selection works well for
coarse-grained load-balancing



Fast, non-intrusive, and accurate
64% associations in the same AS
16% associations in the same NAC
Server selection can be inaccurate if server
density is high