DNS Resolution with Renewal Using Piggyback

Baekcheol Jang
Department of Computer Science
Korea Advanced Institute of Science and Technology,
Guseong-dong Yuseong-gu,Taejon, Republic of Korea 305-701
Phone:+82-42-869-8718, Fax: +82-42-869-5554
Kilnam Chon
Department of Computer Science
Korea Advanced Institute of Science and Technology,
Guseong-dong Yuseong-gu,Taejon, Republic of Korea 305-701
Phone:+82-42-869-3554, Fax: +82-42-869-5554


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].


Figure 1: Example of Renewal Using Piggyback Mechanism.

2.1 PUP Mechanism

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.

2.2 RUP Message Format

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.

2.3 RUP Policies

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.

  1. RUP First-Stored-First-Piggyback (FSFP): Once the records are stored in the cache, their sequences are never changed, and the expired cached entries are piggybacked in the order of First-Stored-First-Piggyback.
  2. RUP Most-Recently-Used (MRU): Whenever a cached record is used, it is replaced to the top of stack. The expired cached entries are piggybacked on the order of the stack, Most-Recently-Used.
  3. RUP Most-Frequently-Used (MFU): Whenever a cached record is used, its number of hits is updated, and the cached records are sorted in the order of biggest number of hits, biggest the number of hits.
  4. RUP-Always: There is no limitation in the length of RUP message in this policy, all expired cached entries are piggybacked, and all TTL values of them are updated. This policy is valuable only as the theoretical upper bound of the performance of RUP.

3. Performance Evaluation

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. Resolution time varying TTL values for KAIST traces.

Figure 3. Resolution time varying TTL values for Yonsei University traces.

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.

4. Analysis

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.

  1. Resolution Time: By the premise, both approaches decrease resolution time to the similar extent.
  2. Query Traffic: While RUP reduces query traffic, the renewal needs additional query overheads. The additional queries of the renewal can be serious load on the Internet. Today, DNS traffic already takes considerable fraction of wide area Internet traffic in the side of packet [3].
  3. Bandwidth: To update an expired record, RUP consumes additional bandwidth (tens of byte) only for each record piggybacked in regular query and response, but the renewal consumes additional bandwidth (hundreds of byte) for an unsolicited query and its response.
  4. Processing Overhead: Both approaches need additional processing overheads of requesting and requested servers to update expired records. However, the overheads will much smaller than RTTs that will be saved by both approaches, and they can be disregarded.
  5. Deployment: Both approaches require only change on requesting server, and they can be easily deployed.

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.


  1. P. Mockapetris, Domain Names-Concepts and Facilities, RFC 1034, ISI, Nov. 1987.
  2. P. Mockapetris, Domain Names- Implementation and Specification, RFC 1035, ISI, Nov. 1987.
  3. S. McCreary and K. Claffy, Trends in Wide Area IP Traffic Patterns, ITC Specialist Seminar on IP traffic Modeling, Measurement, and Management, Sept. 2000.
  4. E. Cohen and H. Kaplan, Proactive Caching of DNS Records: Addressing a Performance Bottleneck, in proc. Symp. on Applications and the Internet(SAINT), Jan. 2001.
  5. A. Shaikh, R. Tewari, and M. Agrawal, On the Effectiveness of DNS-based Server Selection, in proc. IEEE INFOCOM, Apr. 2001.
  6. P. Albitz and C. Liu, DNS and BIND, O Reilly, Cambridge, MA, 4th edition 2001.