Web service speeds are often determined by DNS resolution time as well as content transmission time. In this paper, we propose and evaluate a scheme for reducing DNS resolution time by the renewal of expired cached records using piggyback message. The simulation results show that the proposed scheme improves DNS resolution with a suitable overhead.
Web, DNS, TTL, RTT, RUP, Piggyback, Renewal Using Piggyback
Today, Web is one of the most popular Internet applications [3]. However DNS resolutions, one of necessary predecessors of Web, frequently make Web access speeds prolong. It is because DNS databases are hierarchically distributed, and DNS resolutions can involve multiple remote name servers. As bandwidth increases and content transmission time decreases, the relative contribution of DNS resolutions in web service speed becomes higher.
To improve the DNS resolution, DNS has used a cache. It incorporates a passive caching mechanism where a local name server caches all the records that it receives in responses, and the records are available until their TTL values expire [1, 2]. According to DNS traces from Korea Advanced Institute of Science and Technology (KAIST), only a fraction of DNS resolutions (about 16.8%) were cache misses, but their latencies were much various (several ms ~ tens of second). Such unpredictable long latencies can become crucial overheads especially on interactive applications such as Web. However, there is an improvable possibility on DNS cache performance. In same traces, 74.8% of cache misses were expired misses. If we had extended their TTL values beforehand, the misses could have been removed. Cohen and Kaplan exploited the possibility and proposed a proactive caching mechanism, which increased cache hit rate by updating expired cached records using automatically generated unsolicited queries to their authoritative name servers [4]. Their premise, that user-time is valuable and a cache miss is costlier than a respective automatic query, is reasonable, but additional queries cannot be inevitable as they were seen in their simulation, and they can be significant load on the Internet [3].
This paper presents a DNS resolution time reduction scheme called Renewal Using Piggyback (RUP), which piggybacks the expired cached records on a regular DNS query instead of generating unsolicited queries. Simulation results show that RUP improves the performance of the passive caching to about 33% ~ 50% and needs only one 10th of TTL value compared to the passive caching. Although the proposed scheme consumes less than twice bandwidth as much as the passive caching, it is not big enough to affect the overall traffic in the Internet [3].
RUP exploits a regular DNS query for the renewal of expired cached records. That is, when a local name server sends a DNS query to an authoritative name server, expired cached records corresponding to the authoritative name server are piggybacked on the query. The authoritative name server sends a response, and updated records are piggybacked on the response. In RUP, the results of each query are cached and indexed per each authoritative name server. Once the records are updated, so are their TTL values, and they can be reused for their updated TTL durations. Figure 1 presents a simple example of RUP mechanism.
RUP messages can be designed using an ARCOUNT field and an additional record section of current DNS message format [1, 2]. In the RUP query message, expired cached records are piggybacked on the additional record section, and the number of the records is specified in the ARCOUNT field. In the RUP response message, updated records are piggybacked with existing additional records in the additional record section. The ARCOUNT field specifies the number of records in the additional record section. Messages carried by UDP in DNS are limited to 512 bytes, and longer messages are truncated [2]. BIND, the most popular name server software, transfers messages exceeding 512 bytes after truncation using TCP exchange [6]. To avoid such overhead, we limit the RUP query message to 512 bytes. DNS response messages less than 512 bytes should not also exceed 512 bytes by piggyback messages. The proposed RUP message format needs no modification of the current DNS message format, but it requires end-to-end changes and protocol support.
An alternative reducing such overhead is to send multiple questions in a query. The expired cached records are specified to questions in question section of a query. The requested server responds to the query with multiple answers in a response. BIND has not implemented the mechanism yet [6], but there clearly exist similar examples in the current specifications [1, 2]. If this mechanism is not customized to RUP, it can be less effective than the former. However, it is deployed and implemented easier than the former since it needs only changes at requesting servers. In our simulation, we assume the first approach.
To explore and maximize the RUP performance, we propose several RUP policies that determine which expired records would be piggybacked based on record access patterns in the DNS cache.
To compare performances of RUP policies with performance of the passive caching, we conducted a trace driven simulation based on two name server traces collected from KAIST and Yonsei University at Korea respectively in Novemver 2001 and February 2002. We built our own simulator, which specified the passive caching and each RUP policy. All the types of resolutions for the traces were involved in the simulation, but they were limited to the resolutions having had records in the answer sections of their responses. We assumed that there was no packet loss in network and no name server failure, and we did not apply name compression [1, 2]. All used parameter values such as latency and packet length were real values. The evaluation items consisted of resolution time, the numbers of queries and referrals, cache performance, bandwidth, and the number of piggybacked records.
Figure 2 and figure 3 provides the distribution of resolution times varying TTL for our traces obtained from the simulation. RUP-MRU and RUP-MFU, the best policies, improved resolution time of the passive caching to about 33% ~ 50%, and their resolution times were in close vicinity to the resolution time of RUP-Always, the theoretical upper bound of RUP. They also reduced query traffics of the passive caching to about 33% ~ 50%. There was relatively bigger reduction on the number of referrals (44% ~ 60%) than on the number of queries (33% ~ 50%). Especially, it means remarkable decrease of load on the root and TLD name servers. They requires only one 10th of TTL value compared to the passive caching. (See figure 2 and 3). It is expected to address the lowering of cache performance that will be caused by the low TTL value preference originating in several recent changes in the way DNS is used [5]. The allowance of low TTL values allocation also involves the potential improvement on cache coherency. Such improvements were based on the increase of cache hit rate (33% ~ 50%). Although the best policies consumed less than twice bandwidth as much as the passive caching did, bandwidth is not a particularly important issue in DNS today [3]. Besides, the numbers of piggybacked records were averages of only about 3.5 when TTL value is 100 seconds and only about 1.1 when 1,000 seconds. We believe that the similarity of the simulation results on both our traces showed the effectiveness of RUP.
Our analysis between RUP and renewal [4] is based on the premise that possibilities that records updated by both approaches are referred are more or less similar because their policies are based on record access patterns in a little same way.
It is much self-evident that RUP is more cost-effective than the renewal. However, to make more obvious the contribution of RUP, the premise should be proved in anyway. We leave the work as further research.
This paper proposed and evaluated RUP mechanism, which addressed a bottleneck point of Web service speed, DNS resolution. The evaluation showed improved DNS resolution time with reasonable overheads.