Internet DRAFT - draft-deng-dns-authority-server-placement
draft-deng-dns-authority-server-placement
DNSOP G. Deng
Internet-Draft N. Kong
Intended status: Informational S. Shen
Expires: January 5, 2015 CNNIC
July 4, 2014
Approach on optimizing DNS authority server placement
draft-deng-dns-authority-server-placement-00
Abstract
The geographical distribution of DNS authority servers highly affects
the DNS query latency and financial costs. This document proposes an
approach on optimizing the geographical placement of DNS authority
servers so that the DNS query latency is highly reduced while the
financial cost is within its budget.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 5, 2015.
Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
Deng, et al. Expires January 5, 2015 [Page 1]
Internet-Draft dns authority server placement July 2014
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November
10, 2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s) controlling
the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other
than English.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4
2. Use cases and scenarios . . . . . . . . . . . . . . . . . . . 4
2.1. Geographically distributing all authority servers . . . . 4
2.2. Geographically distributing newly-added authority servers 4
2.3. Readjusting geographical distribution of all authority
servers . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Authority server placement approach . . . . . . . . . . . . . 5
3.1. Problem statement . . . . . . . . . . . . . . . . . . . . 5
3.2. Optimization goals . . . . . . . . . . . . . . . . . . . 6
3.2.1. Minimizing the average Domain Name Resolution Delay . 6
3.2.2. Minimizing the maximal Domain Name Resolution Delay . 6
3.3. Authority server placement algorithm . . . . . . . . . . 6
3.3.1. Best Efficiency Server Placement Algorithm . . . . . 6
3.3.2. Best Fairness Server Placement Algorithm . . . . . . 8
3.4. Discussion . . . . . . . . . . . . . . . . . . . . . . . 8
4. IANA consideration . . . . . . . . . . . . . . . . . . . . . 8
5. Security considerations . . . . . . . . . . . . . . . . . . . 8
6. References . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.1. Normative References . . . . . . . . . . . . . . . . . . 9
6.2. Informative References . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9
1. Introduction
Domain Name System [RFC1035] is one of the most important components
of Internet infrastructure and enables the association of the human
memorable domain names and their corresponding information like
routable IP addresses. It is revealed by Google that in average
Internet users need hundreds of DNS lookups to be done in a typical
browsing day [BROWSE]. Even for one page, multiple domain name
Deng, et al. Expires January 5, 2015 [Page 2]
Internet-Draft dns authority server placement July 2014
resolutions are needed since contents from many other domains are
incorporated to one page. So the quality of service (QoS) of other
Internet applications highly depends on the DNS system.
Also, with the development of telecommunication access technology,
the network latency but not the bandwidth gradually becomes the main
impediment for improving the QoS of web service, for the bandwidth
price is becoming lower and lower. Moreover, for web service
providers, their revenue and profit are greatly affected by network
latency [Web.Latency]. For instance, Amazon estimates that the
Internet latency inversely correlates with revenue and profit, and
every 100 milliseconds increase in latency cuts profits by 1%. So
shortening DNS query latency is an efficient way for improving the
QoS of other Internet applications. Here the DNS query latency is
defined as the time difference between the time when a stub resolver
sends a DNS query and receives the corresponding response.
Nowadays, due to security threat like DDOS and the deployment of
DNSSEC ([RFC4033] [RFC4034] [RFC4035]), the processing capacicy of
DNS authority servers needs to be increased and at the same time more
bandwidth resource has to be added. And the launch of new gTLDs
means that more DNS authority servers need to be deployed in the DNS
hierarchy. However, to the best of our knowledge, there is still no
rigorous authority server placement method yet and thus DNS operation
engineers only rely on their personal experiences, which may lead to
sub-optimal authority server distribution and thus long DNS query
latency and high financial costs.
Fundamentally, there are two ways to shorten the DNS query latency;
one is shortening the processing latency on DNS servers (both
authority and recursive servers); the other is reducing the network
latency between authority and recursive servers as well as that
between stub and recursive servers. The processing latency on one
authority server usually relates to the rate of incoming DNS queries
(whose unit is query per second, QPS for short) and specifically
larger the QPS is, longer the processing latency is. For network
latency, since recursive servers are usually very near to stub
resolvers, we just take the network latency between authority and
recursive servers into consideration. For simplicity, we define
Domain Name Resolution Delay (DNRD) as the difference between the
time when one DNS recursive server sends one DNS query to and
receives the corresponding response from a specific authority server.
Then DNRD is almost the Round-Trip Time (RTT) between the DNS
authority servers (of root domain, top level domain, second level
domain et al.) and DNS recursive servers, plus the processing latency
of that DNS query on the authority server. Finally, the main object
of this document is to minimize the DNRD by reasonably select the
location of authority servers without the financial costs exceeding
Deng, et al. Expires January 5, 2015 [Page 3]
Internet-Draft dns authority server placement July 2014
their budget. The financial costs of operating authority servers
mainly consist of two parts: one is the fixed expense including
equipment purchase cost, room rental cost, et al; the other is
variable expense such as bandwidth rental cost, electricity fees, et
al. Usually, different locations have different price level and then
different geographical distribution of the same authority servers
leads to different financial costs.
1.1. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
2. Use cases and scenarios
Fundamentally, there are three main use cases on DNS authority server
placement.
2.1. Geographically distributing all authority servers
DNS system works in a decentralized fashion and a new DNS zone can be
created through the delegation from its parental domain. Several (or
tens of even hundreds of ) authority servers having the authority for
such new DNS zones have to be deployed for providing authoritative
resolution service. For instance, due to the launch of new gTLDs,
many authority servers have been being deployed. When the financial
cost upper bound is given, the question is where to geographically
place these authority servers so that the DNRD is minimized on the
condition that the financial cost is within its upper bound. Here,
at least two questions should be answered. One is which potential
locations should be selected as actual locations; the other is how
many authority servers should be placed on each actual location.
2.2. Geographically distributing newly-added authority servers
For some existing DNS zones, there are some running authority servers
already. However, due to the reason like further reducing the DNRD
or decreasing the financial cost, more authority servers will be
added without changing the location of already deployed authority
servers. Then the location of newly-added authority servers has to
be carefully selected to reduce the DNRD as much as possible with a
decreased budget.
Deng, et al. Expires January 5, 2015 [Page 4]
Internet-Draft dns authority server placement July 2014
2.3. Readjusting geographical distribution of all authority servers
Since now the authority servers are geographically placed by
operation engineers by their personal experience, the authority
server placement method may not be optimal. Then the DNRD may be too
long and the financial cost may be too high, which calls for
readjusting the geographical distribution of all currently deployed
authority servers so that the DNRD is shortened and at the same time
the financial cost is reduced.
3. Authority server placement approach
3.1. Problem statement
The problem of authority server placement is like this: given a set
of potential locations (which number in thousands even tens of
thousands) for placing authority servers, which locations (which
usually number in less than ten or tens) should be selected to obtain
a relatively low DNRD without the financial cost exceeding its upper
bound. Towards this problem, at least two questions should be
answered. One is which locations should be selected as the actual
location for placing authority servers? The other is how many
authority servers should be deployed on each selected location.
Here, we assume the authority servers are homogeneous and thus have
the same processing capacity. And multiple even tens of authority
servers can be deployed at the same location for the convenience on
DNS operation and zone file synchnization.
To answer these two questions, at least the following three kinds of
data should be provided. The first is those relating to the DNS
recursive servers, such as RTT between those potential locations and
DNS recursive servers and the query rate of each DNS recursive
servers. The second is those relating to the financial cost, like
the bandwidth price, the electricity price, the room rent price,
equipment maintenance price on each potential location and as well as
the authority server purchase price and the total financial budget.
The third is those relating to the authority server, such as the
capacity of each authority server (whose unit can be handled queries
per minute or hour) and the processing latency which relates to the
QPS of the authority server. Since the number of recursive servers
is very large, it is better to only choose a small part of recursive
servers according to some policies (such as randomization or only
choosing top N recursive servers) and just to measure the RTT between
those selected recursive servers and potential locations.
With all above input data, the authority server placement approach
should output one specific authority server placement scheme with
lowest DNRD on condition that the actual financial cost is within its
Deng, et al. Expires January 5, 2015 [Page 5]
Internet-Draft dns authority server placement July 2014
budget. In fact, the authority server placement problem is one kind
of optimization problem and thus some approximate optimization
algorithm such as simulated-annealing algorithm [SA] can be used to
solve this problem.
3.2. Optimization goals
Fundamentally, the goal of the authority server placement is: 1).
Minimizing the average DNRD on the condition that the financial cost
does not exceed its upper bound; 2). Minimizing the maximal DNRD
with the financial cost within its upper bound.
3.2.1. Minimizing the average Domain Name Resolution Delay
Average DNRD is calculated by averaging all DNRDs between authority
servers and recursive servers which here only refers to those
selected ones but not all the recursive servers just as mentioned
before. The efficiency of a given DNS zone can be evaluated by its
average DNRD. Specifically, lower the average DNRD is, better the
efficiency is. Theoretically, when the financial cost is given,
there is at least one DNS authority server placement scheme making
the average DNRD be the minimal.
3.2.2. Minimizing the maximal Domain Name Resolution Delay
Minimizing the average DNRD may shorten the DNRD of a large part of
recursive servers but may prolong that of a small part of recursive
servers with a high probability, so this strategy (namely Minimizing
the average DNRD) does improve the efficiency but may not obtain good
fairness. Towards this issue, the goal of authority server placement
can be transferred from minimizing the average DNRD into minimizing
maximal DNRD. Then the difference between the largest and smallest
DNRD experienced by recursive servers is minimized, which means the
recursive servers get almost the same DNRD and thus the fairness is
achieved.
3.3. Authority server placement algorithm
3.3.1. Best Efficiency Server Placement Algorithm
The input of this algorithm is as follows:
1. The data relating to DNS recursive servers:
1). The RTT between potential locations of authority servers and
selected recursive servers. Here, the RTT data can be obtained
through the network measurement technology like PING or TRACEROUTE
[RFC4560].
Deng, et al. Expires January 5, 2015 [Page 6]
Internet-Draft dns authority server placement July 2014
2). The average query rate (whose unit can be queries per minute or
hour) of each recursive servers, which can be obtained from the log
of DNS recursive servers.
2. The data relating to financial cost:
1). The bandwidth price of each potential location.
2). The electricity price of each potential location.
3). The room rent price of each potential location.
4). The equipment maintenance price at each potential location.
5). The price of one authority server.
6). The total financial budget.
3. The data relating to authority servers:
1). The processing capacity of the authority server, like maximum
QPS of one authority server.
2). The processing latency which relates to the QPS of the authority
server.
The output of this algorithm is as follows:
1). The potential locations that is selected as the actual location
to place authority servers;
2). The number of authority servers placed on each selected
authority server location.
3). The recursive servers that each authority server serves.
4). The bandwidth should be purchased for each actual location of
authority servers.
The methods used for solving this algorithm:
Enumeration can be used to generate the best output; however,
enumeration will lead to very high computational complexity which
make this intuitive idea impossible.
Some approximate optimization algorithm such as simulated-annealing
algorithm [SA] can be used to obtain an output (that may not be the
best one but we can accept) with a much lower computational
Deng, et al. Expires January 5, 2015 [Page 7]
Internet-Draft dns authority server placement July 2014
complexity compared with the enumeration. However, the performance
of this kind of algorithms like simulated-annealing algorithm is not
as good as we expected, thus the improvement of such algorithms is
highly needed.
In fact, the problem of DNS authority server placement is NP-hard.
For instance, the computational complexity of selecting 50 locations
from 1000 potential locations is about C(1000, 50) which is as large
as 10^64!
3.3.2. Best Fairness Server Placement Algorithm
Best efficiency means the maximal DNRD is minimized. So the object
of this algorithm is to make the maximal DNRD be as small as possible
on condition that the financial cost does not exceed its upper bound.
The input and output of this algorithm is the same as the above
algorithm except the optimization object of this algorithm is to make
the maximal DNRD be the lowest one. And of course some approximate
optimization algorithms like simulated-annealing algorithm [SA] can
be used to reduce the computational complexity.
3.4. Discussion
Above two server placement algorithms are applicable for those three
mentioned scenarios. In the scenario two, only the location of one
part of authority servers but not all needs to be fixed while in
scenario one and three, the location of all authority servers needs
to be fixed. So the algorithm used in scenario two can be seen as
one specific case used in scenario one and three. Specifically,
adding some restriction conditions to the algorithm used in scenario
one and three can form the algorithm used in scenario two. In a
word, the input and output of algorithms for these three scenarios
are exactly the same, though the method of solving server placement
algorithm in scenario two is a little different from that in scenario
one and three.
4. IANA consideration
This document does not call for changes or additions to any IANA
registry.
5. Security considerations
TBD.
Deng, et al. Expires January 5, 2015 [Page 8]
Internet-Draft dns authority server placement July 2014
6. References
6.1. Normative References
[RFC1035] Mockapetris, P., "Domain names - implementation and
specification", STD 13, RFC 1035, November 1987.
[RFC4033] Arends, R., Austein, R., Larson, M., Massey, D., and S.
Rose, "DNS Security Introduction and Requirements", RFC
4033, March 2005.
[RFC4034] Arends, R., Austein, R., Larson, M., Massey, D., and S.
Rose, "Resource Records for the DNS Security Extensions",
RFC 4034, March 2005.
[RFC4035] Arends, R., Austein, R., Larson, M., Massey, D., and S.
Rose, "Protocol Modifications for the DNS Security
Extensions", RFC 4035, March 2005.
[RFC4560] Quittek, J. and K. White, "Definitions of Managed Objects
for Remote Ping, Traceroute, and Lookup Operations", RFC
4560, June 2006.
6.2. Informative References
[BROWSE] "A DNS number for faster browsing", December 2009,
<http://www.infoq.com/news/2009/12/Public-DNS-Google>.
[SA] "simulated-annealing algorithm", December 2009,
<http://en.wikipedia.org/wiki/Simulated_annealing>.
[Web.Latency]
Flach, Tobias., Dukkipati, Nandita., and Andreas. Terzis,
"Reducing Web Latency: the Virtue of Gentle Aggression",
September 2013, <Proceedings of ACM SIGCOMM 2013>.
Authors' Addresses
Guangqing Deng
CNNIC
4 South 4th Street, Zhongguancun, Haidian District
Beijing, Beijing 100190
China
Phone: +86 10 5881 3430
Email: dengguangqing@cnnic.cn
Deng, et al. Expires January 5, 2015 [Page 9]
Internet-Draft dns authority server placement July 2014
Ning Kong
CNNIC
4 South 4th Street, Zhongguancun, Haidian District
Beijing, Beijing 100190
China
Phone: +86 10 5881 3147
Email: nkong@cnnic.cn
Sean Shen
CNNIC
4 South 4th Street, Zhongguancun, Haidian District
Beijing, Beijing 100190
China
Phone: +86 10 5881 3038
Email: shenshuo@cnnic.cn
Deng, et al. Expires January 5, 2015 [Page 10]
