1. INTRODUCTION

Translation of names to network addresses is an essential predecessor to communication in networked systems. The Domain Name System (DNS) performs this translation on the Internet and constitutes a critical component of the Internet infrastructure. While the DNS has sustained the growth of the Internet through static, hierarchical partitioning of the namespace and wide-spread caching, recent increases in malicious behavior, explosion in client population, and the need for fast reconfiguration pose difficult problems. The existing DNS architecture is fundamentally unsuitable for addressing these issues.  The foremost problem with DNS is that it is susceptible to denial of service (DoS) attacks. This vulnerability stems from limited redundancy in name servers, which pro-vide name-address mappings and whose overload, failure or compromise can lead to low performance, failed lookups and misdirected clients. Approximately 80% of the domain names are served by just two name servers and a surprising 0.8% by only one. At the network level, all servers for 32% of the domain names are connected to the Internet through a single gateway, and can thus be compromised by a single failure. The top levels of the hierarchy are served by a relatively small number of servers, which serve as easy targets for denial of service attacks. A recent DoS attack on the DNS crippled nine of the thirteen root servers at that time, while another recent DoS attack on Microsoft’s DNS servers severely affected the availability of Microsoft’s web services for several hours .DNS name servers are easy targets for malicious agents, partly because approximately 20% of name server implementations contain security flaws that can be exploited to take over the name servers.  Second, name-address translation in the DNS incurs long delays. Recent studies have shown that DNS lookup time contributes more than one second for up to 30% of web object retrievals. The explosive growth of the namespace has decreased the effectiveness of DNS caching.  The skewed distribution of names under popular domains, such as .com, has attended the name hierarchy and increased load imbalance. The use of short timeouts for popular map-pings, as is commonly employed by content distribution net-works, further reduces DNS cache hit rates. Further, manual configuration errors, such as lame delegations, can introduce latent performance problems.  Finally, widespread caching of mappings in the DNS prohibits fast propagation of unanticipated changes. Since the DNS does not keep track of the locations of cached map-pings, but relies on timeout-based invalidations of stale co-pies, it cannot guarantee cache coherency. Lack of cache coherency in the DNS implies that changes may not be visible to clients for long durations, effectively preventing quick service relocation in response to attacks or emergencies.

Fresh design of the legacy DNS provides an opportunity to address these shortcomings. A replacement for the DNS should exhibit the following properties.

High Performance: Decouple the performance of DNS from the number of name servers. Achieve lower latencies than legacy DNS and improve lookup performance in the presence of high loads and unexpected changes in popularity

 Resilience to Attacks: Remove vulnerabilities in the system and provide resistance against denial of service attacks through decentralization and dynamic load balancing. Self-organize automatically in response to host and network failures.

 Fast Update Propagation: Enable changes in name-address mappings to quickly propagate to clients. Support secure delegation to preserve integrity of DNS records, and prohibit rogue nodes from corrupting the system.

This paper describes Cooperative Domain Name System (CoDoNS), a backwards-compatible replacement for the legacy DNS that achieves these properties. CoDoNS com-bines two recent advances, namely, structured peer-to-peer overlays and analytically informed proactive caching. Structured peer-to-peer overlays, which create and maintain a mesh of cooperating nodes, have been used previously to implement wide-area distributed hash tables (DHTs). While their self organization, scalability, and failure resilience provide a strong foundation for robust large-scale distributed services, their high lookup costs render them inadequate for demanding, latency-sensitive applications such as DNS].  CoDoNS achieve high lookup performance on a structured overlay through an analytically-driven proactive caching layer.  This layer, called Beehive, automatically replicates the DNS mappings throughout the network to match anticipated demand and provides a strong performance guarantee. Specially, Beehive achieves targeted average lookup latency with a minimum number of replicas. Overall, the combination of Beehive and structured overlays provides the requisite properties for a large scale name service, suitable for deployment over the Internet.

2.        DNS: OPERATION AND PROBLEMS

2.1        Overview of Legacy DNS

The legacy DNS is organized as a static, distributed tree. The namespace is hierarchically partitioned into non-overlapping regions called domains. For example, cs.cornell.edu is a sub-domain of the domain cornell.edu, which in turn is a sub-domain of the top-level domain edu. Top-level domains are sub-domains of a global root domain .Domain names, such as www.cs.cornell.edu, belong to name-owners

Name Resolution in Legacy DNS:

Resolvers translate names to addresses by following a chain of

Delegations iteratively (2-5) or recursively (6-9).

Extensible data structures, called resource records, are used to associate values of different types with domain names.  These values may include the corresponding IP address, mail host, owner name and the like. The DNS query interface al-lows these records to be retrieved by a query containing a domain name and a type.

The legacy DNS delegates the responsibility for each do-main to a set of replicated name servers called authoritative name servers. The authoritative name servers of a domain manage all information for names in that domain, keep track of authoritative name servers of the sub-domains rooted at their domain, and are administered by namespace operators.  At the top of the legacy DNS hierarchy are root name servers, which keep track of the authoritative name servers for the top level domains (TLDs). The top-level domain namespace consists of generic TLDs (gTLD), such as .com, .edu, and .net, and country-code TLDs (ccTLD), such as .uk, .tr, and .in. Name servers are statically configured with thirteen IP addresses for the root servers. BGP-level anycast is used in parts of the Internet to reroute queries destined for these thirteen IP addresses to a local root server.  Resolvers in the legacy DNS operate on behalf of clients to map queries to matching resource records. Clients typically issue DNS queries to local resolvers within their own administrative domain. Resolvers follow a chain of authoritative name servers in order to resolve the query. The local resolver contacts a root name server to _nd the top-level domain name server. It then issues the query to the TLD name server and obtains the authoritative name server of the next sub-domain. The authoritative name server of the sub-domain replies with the response for the query. This process continues recursively or iteratively until the authoritative name server of the queried domain is reached. Figure 1 illustrates the different stages in the resolution of an example domain name www.cs.cornell.edu. While this figure provides a simple overview of the communication involved in name resolution, in practice, each query may trigger additional lookups to resolve intermediate name servers.

Pursuing a chain of delegations to resolve a query naturally incurs significant delay.  The legacy DNS incorporates aggressive caching in order to reduce the latency of query resolution. The resolver cache responses to queries they is-sue, and use the cached responses to answer future queries.  Since records may change dynamically, legacy DNS provides a weak form of cache coherency through a time-to-live (TTL) field. Each record carries a TTL assigned by the authoritative name server, and may be cached until TTL expires.

2.2        Problems with Legacy DNS

Failure Resilience - Bottlenecks

The legacy DNS is highly vulnerable to network failures, compromise by malicious agents, and denial of service at-tacks, because domains are typically served by a very small number of name servers. We first examine the delegation bottlenecks in DNS; a delegation bottleneck is the minimum number of name servers in the delegation chain of each do-main that need to be compromised in order to control that domain. Table 1 shows the percentage of domains that are bottlenecked on different numbers of name servers. 78.63% of domains are restricted by two name servers; the minimum recommended by the standard surprisingly, 0.82% of domains are served by only one name server. Even the highly popular domains are not exempt from severe bottlenecks in their delegation chains. Some domains (0.43%) spoof the minimum requirement by having two name servers map to the same IP address. Overall, over 90% of domain names are served by three or fewer name servers and can be disabled by relatively small-scale DoS attacks.

Failure and attack resilience of the legacy DNS is even more limited at the network level. We examined physical bottlenecks, that is, the minimum number of network gateways or routers between clients and name servers that need to be compromised in order to control that domain. We measured the physical bottlenecks by performing trace routes to 10,000 different name servers, which serve about  5,000

randomly chosen domain names, from fifty globally distributed sites on Planet Lab. Figure 2 plots the percentage of domains that have different numbers of bottlenecks at the network level, and shows that about 33% of domains are bottlenecked at a single gateway or router. While this number is not surprising - domains are typically served by a few name-servers, all located in the same sub-network. It highlights that a large number of domains are vulnerable to network outages. These problems are significant and affect many top level domains and popular web sites. Recently, Microsoft suffered a DoS attack on its name servers that rendered its services unavailable. The primary reason for the success of this attack was that all of Microsoft’s DNS servers were in the same part of the network. Overall, a large portion of the namespace can be compromised by infiltrating a small number of gateways or routers.

FIGURE-2

Failure Resilience - Implementation Errors

The previous section showed that legacy DNS suffers from limited redundancy and various bottlenecks. In this section, we examine the feasibility of attacks that target these bottle-necks through known vulnerabilities in commonly deployed name servers. Early studies identified several implementation errors in legacy DNS servers that can lead to compromise. While many of these have been fixed, a significant percentage of name servers continue to use buggy implementations. We surveyed 150,000 name servers to determine if they contain any known vulnerabilities, based on the Berkeley Internet Name Daemon (BIND) exploit list maintained by the Internet Systems Consortium (ISC).  Table 2 summarizes the results of this survey. Approximately 18% of servers do not respond to version queries, and about 14% do not report valid BIND versions. About 2% of name serves have the tsig bug, which permits a buffer overflow that can enable malicious agents to gain access to the system. 19% of name serves have the negcache problem that can be exploited to launch a DoS attack by providing negative responses with large TTL value from a malicious name server. Overall, exploiting the bottlenecks identified in the previous section is practical.

Table2-Vunrabilities in BIND

Performance - Latency

Name resolution latency is a significant component of the time required to access web services. . The low performance is due mainly to low cache hit rates, stemming from the heavy tailed, Zipf-like query distribution in DNS.  It is well known from studies on Web caching that heavy-tailed query distributions severely limit cache hit rates.  Wide-spread deployment of content distribution networks, which perform dynamic server selection, have further strained the performance of the legacy DNS. A study on impact of short TTLs on caching shows that cache hit rates decrease significantly for TTLs lower than fifteen minutes. Another study on the adverse effect of server selection reports that name resolution latency can increase by two orders of magnitude.

Performance - Misconfigurations

DNS performance is further affected by the presence of a large number of broken (lame) or inconsistent delegations.  In our survey, address resolution failed for about 1.1% of name servers due to timeouts or non-existent records, mostly stemming from spelling errors. For 14% of domains, authoritative name servers returned inconsistent responses; a few authoritative name servers reported that the domain does 334 not exist, while others provided valid records. Failures stemming from lame delegations and timeouts can translate into significant delays for the end-user. Since these failures and inconsistencies largely stem from human errors, it is clear that manual configuration and administration of such a large scale system is expensive and leads to a fragile structure.

Performance - Load Imbalance

DNS measurements at root and TLD name servers show that they handle a large load and are frequently subjected to denial of service attacks. A massive distributed DoS attack  in November 2002 rendered nine of the thirteen root servers unresponsive. Partly as a result of this attack, the root is now served by more than sixty name servers and is served through special-case support for BGP-level any-cast. While this approach fixes the superficial problem at the topmost level, the static DNS hierarchy fundamentally implies greater load at the higher levels than the leaves.  The special-case handling does not provide automatic replication of the hot spots, and sustained growth in client population will require continued future expansions. In addition to creating exploitable vulnerabilities, load imbalance poses performance problems, especially for lookups higher in the name hierarchy.

Update Propagation

Large-scale caching in DNS poses problems for maintaining the consistency of cached records in the presence of dynamic changes. Selection of a suitable value for the TTL is an administrative dilemma; short TTLs adversely affect the lookup performance and increase network load, while long TTLs interfere with service relocation. For instance, a popular on line brokerage firm uses a TTL of thirty minutes. Its users do not incur DNS latencies when accessing the brokerage for thirty minutes at a time, but they may experience outages of up to half an hour if the brokerage firm needs to relocate its services in response to an emergency.  Nearly 40% of domain names use TTLs of one day or higher, which prohibits fast dissemination of unanticipated changes to records.

3. COOPERATIVE DOMAIN NAMESYSTEM

3.1        Overview of Beehive

       CoDoNS derives its performance characteristics from a proactive caching layer called Beehive . Beehive is a proactive replication framework that enables prefix-matching DHTs to achieve O(1) lookup performance.  In these DHTs both objects and nodes have randomly assigned identifiers

       from the same circular space, and each object is stored at the nearest node in the identifier space, called the home node. Each node routes a request for an object, say 2101, by successively matching prefixes; that is, by routing the re-quest to a node that matches one more digit with the object until the home node, say 2100, is reached. Overlay routing by matching prefixes in this manner incurs O(logN) hops in the worst case to reach the home node. Figure 3 illustrates the prefix matching routing algorithm in Pastry. A routing table of O(logN) size provides the overlay node with pointers to nodes with matching prefixes. In a large system, logN translates to several hops across the Internet and is not sufficient to meet the performance requirements of latency critical applications such as DNS.  Beehive proposes a novel technique based on controlled proactive caching to reduce the average lookup latency of structured DHTs. Figure 3 illustrates how Beehive applies proactive caching to decrease lookup latency in Pastry. In the example mentioned above, where a query is issued for the object 2101, Pastry incurs three hops to find a copy of the object. By placing copies of the object at all nodes one hop prior to the home node in the request path, the lookup latency can be reduced by one hop. In this example, the lookup latency can be reduced from three hops to two hops by replicating the object at all nodes that start with 21.  Similarly, the lookup latency can be reduced to one hop by replicating the object at all nodes that start with 2. Thus, we can vary the lookup latency of the object between 0 and logN hops by systematically replicating the object more extensively. In Beehive, an object replicated at all nodes with i matching prefixes incurs i hops for a lookup, and is said to be replicated at level i.

Figure 3:

 Proactive Caching in Beehive: Caching an object at all nodes with i matching prefix digits ensures that it can be located in i hops. Beehive achieves O(1) average lookup time with minimal replication of objects.

The central insight behind Beehive is that by judiciously choosing different levels of replication for different objects, the average lookup performance of the system can be tuned to any desired constant. Naturally, replicating every object at every node would achieve O(1) lookups, but would incur excessive space overhead, consume significant band-width and lead to large update latencies. Beehive minimizes bandwidth and space consumption by posing the following optimization problem: minimize the total number of replicas subject to the constraint that the aggregate lookup latency is less than a desired constant C. For power-law (or Zipf-like) query distributions, Beehive analytically derives the optimal 335 closed-form solution to this problem. The derivation of the analytical solution is provided in; the final expression for the closed-form solution that minimizes the total number of replicas for Zipf-like query distributions with parameter  

 a < 1 is the following:

                                    x[i] = [ d[i]*(logN _ C)/(1+d+... ...      d(logN-1) )] 1/(1-a)

                                                      where d = b (1-a)/a

In this expression, b is the base of the underlying DHT and

x[i] is the fraction of most popular objects that get replicated  at level i.

This solution is immediately applicable to DNS, since DNS queries follow a Zipf-like distribution.  The analytical result provides several properties suited for latency-sensitive applications such as DNS. First, it succinctly captures the space-time tradeoff and enables applications to achieve any targeted average lookup latency by selecting an appropriate C. In CoDoNS, we set Beehive’s target as c = 0:5 hops, which means that a large percentage of requests are answered immediately without having to take any extra network hops. Second, it incurs minimal band-width and storage overhead by picking the optimal number of replicas required to achieve the target lookup performance. Further, replicating objects across several nodes balances the load on individual Beehive nodes, reduces hotspots and improves resilience against DoS attacks. Finally, the level of replication for each object can be used to quickly determine the location of all object replicas, and to update them when necessary.

Beehive nodes need to know only the Zipf parameter and the relative popularity rank of objects to apply the closed-form solution and determine the extent of replication for each object. Beehive employs a combination of local measurement and limited aggregation to estimate the Zipf parameter and the popularity ranks of objects. Beehive nodes locally measure the access frequency of each object, and periodically aggregate them with other nodes every aggregation interval. Each node aggregates values gathered from nodes one level higher in the routing table. Eventually, the aggregates trickle down through different levels of the routing table and reach the home node. The home node computes a final aggregate and propagates it to all replicas in the system. The Zipf parameter is locally derived from the aggregate access frequencies of the object and fed to the analytical model. Using these estimates, each Beehive node invokes the analytical model once every analysis interval and obtains the appropriate replication levels for objects it stores. The replication of these objects to the specified levels is then performed by the replication protocol. Replication in Beehive is controlled locally; that is, each node is responsible for replicating an object on nodes at most one hop away from itself. For example, the home node of a popular object replicates it at nodes that share one prefix less.  Those nodes then independently decide to replicate that object further to one more level. In the replication phase, each node exchanges messages with nodes in its routing table, which are one hop away from them, to push, delete, or up-date replicas for which they are responsible.  The aggregation and replication protocols enable Beehive to quickly detect changes in the demand for objects. Large changes in the popularity of domain names occur during denial of service attacks and ash crowds. Beehive nodes constantly monitor the access frequency of objects and ad-just the extent of replication. In response to DoS attacks, they promptly increase the number of replicas and spread the load among several nodes, curbing the attack.  Proactive replication also enables Beehive to rapidly push updates to all the replicas in the system. In general, pro-active propagation of updates demands expensive mechanisms to keep track of all the nodes where the object is cached. Beehive requires just a small integer, the replication level of an object, to determine the range of nodes with replicas of the object. An object at level i is replicated at all nodes with i matching prefix digits. For a level i object, the home node propagates updates to all the nodes at level i in the routing table. Those nodes in turn propagate updates to nodes at level i + 1. This recursive process disseminates the updates to nodes with i matching prefix digits. Nodes in the process of joining the DHT may miss the initial up-date propagation. Such nodes will receive the latest copy of the object in the next replication phase; they may in-cur a slight performance penalty, but will not serve stale data. Proactive update propagation obviates the need for timeout-based caching.

3.2        CoDoNS: Architecture

CoDoNS consist of globally distributed nodes that self organize to form a peer-to-peer network. We envisage that each institution would contribute one or more servers to CoDoNS, forming a large-scale, cooperative, globally shared DNS cache. CoDoNS provides query resolution services to clients using the same wire format and protocol as legacy DNS, and thus requires no changes to client resolvers.  CoDoNS decouples namespace management from query resolution of the legacy DNS. Name owners need only to purchase certificates for names from namespace operators and introduce them into CoDoNS; they do not need to provide dedicated hosts for serving those names. CoDoNS places no restrictions on the hierarchical structure of the names-pace and is agnostic about the administrative policies of the name owners. To the name owners, CoDoNS provides an interface consisting of insert, delete and update. CoDoNS  associates the node whose identifier is closest to the consistent hash of the domain name as the home node for that domain name. The home node stores a permanent copy of the resource records owned by that domain name and manages their replication. If the home node fails, the next closest node in the identifier space automatically becomes the new home node. CodoNS replicates all records on several nodes adjacent to the home node in the identifier space in order to avoid data loss due to node failures.  Replacing the DNS entirely with CoDoNS is an ambitious plan, and we do not expect name owners to immediately use CoDoNS for propagating their information. In order to al-low CoDoNS to gradually grow into a globally recognized system, we have incorporated compatibility to the legacy DNS. CoDoNS uses the legacy DNS to resolve queries for records not explicitly inserted by name owners. The home node retrieves resource records from the legacy DNS upon the first query for those records. The additional redirection latency only affects the first query issued in the entire sys-tem for a domain name. CoDoNS decreases the impact of query redirection on lookup performance, by bootstrapping the system with records obtained from legacy DNS name-servers through zone transfers or file transfers.

      Overall, query resolution in CoDoNS takes place as follows. Client sends a query in the wire format of the legacy DNS to the local CoDoNS server in the same administrative domain. The local CoDoNS server replies immediately if it has a cached copy of the requested records. Otherwise, it routes the query internally in the CoDoNS network using the under-lying DHT. The routing terminates either at an intermediate CoDoNS node that has a cached copy of the records or at the home node of the domain name. The home node retrieves the records from the legacy DNS, if it does not already have it, and sends a response to the first contacted CoDoNS server, which replies to the client. In the back-ground, CoDoNS nodes proactively replicate the records in based on the measured popularity. Figure 4 shows a typical deployment of CoDoNS and illustrates the process of query resolution.Clients generate a large number of queries for names in their local administrative domain. Since the home node of a name may be located in a different domain, local queries can incur extra latency and impose load on wide-area network links. CoDoNS support efficient resolution of local names through direct caching. Name owners can directly insert, up-date, and delete their records at CoDoNS servers in their administrative domain, and configure the local CoDoNS servers to use the direct cache for replying to local queries.

3.3        CoDoNS: Implementation

CoDoNS servers are layered on top of Pastry and Bee-hive. Each CoDoNS server implements a complete, recursive, caching DNS resolver and supports all requirements de-scribed in the specification. CoDoNS also supports inverse queries that map IP addresses to a domain name by inserting reverse address-name records into the DHT when name-address records are introduced.

Domain names in CoDoNS have unique 128 bit identifiers obtained through the SHA-1 hashing algorithm. The home node, the closest node in the identifier space, stores permanent copies of the resource records of the domain name and maintains their consistency in the system. Since CoDoNS does not associate TTLs with the records, the home nodes push the updates to all replicas in the system, which retain them until the replication level of the record is downgraded, or until an update is received. Name owners insert updated resource records into CoDoNS, and the home nodes proactively propagate the updates.

CoDoNS ensure the consistency of records obtained from the legacy DNS, CoDoNS by proactively refetching them.  The home node uses the TTL specified by the legacy DNS as the duration to store the records. It refetches the records from legacy DNS after TTL duration, and propagates the updated records to all the replicas if the records change.  Since CoDoNS performs the refetches in the background, its lookup performance is not affected. The TTL values are rounded up to a minimum of thirty seconds; records with lower TTL values are not placed into the system. Low TTL values typically indicate dynamic server-selection in legacy DNS. The home node prompts the server that injected the query to consult the legacy DNS server by issuing a special error-response. This redirection of queries for low-TTL records ensures that services that rely on dynamic server se-lection will continue to work, and reduces overhead on the CoDoNS home nodes.

The legacy DNS relies on error responses, called NXDO-MAIN responses, to detect names that do not exist. Since clients reissue a request several times when they do not receive prompt replies, the DNS specification recommends that resolvers cache NXDOMAIN responses. CoDoNS pro-vides complete support for negative caching as described in [1]. However, permanently storing NXDOMAIN responses could exhaust the capacity of the system, since an unlimited number of queries can be generated for non-existent do-mains. Hence, CoDoNS nodes cache NXDOMAIN responses temporarily and do not refresh them upon expiry.

3.4        Issues and Implications

CoDoNS decouples namespace management from the physical location of name servers in the network. Instead of re-lying on physical delegations to trusted hosts and assuming that Internet routing is secure, CoDoNS uses crypto-graphic delegations and self-verifying records based on the DNSSEC standard.

DNSSEC uses public key cryptography to enable authentication of resource records. Every namespace operator has a public-private key pair; the private key is used to digitally sign DNS records managed by that operator, and the corresponding public key is in turn certified by a signature from a domain higher up in the hierarchy. This process creates a chain of certificates, terminating at a small number of well-known public keys for globally trusted authorities. Since records are signed at the time of issue, the private keys need not be kept online. The signature and the public key are stored in DNS as resource records of type sig and key respectively. Clients can verify the authenticity of a resource record by fetching the sig record and the key record from the DNS.

The use of cryptographic certificates enables any client to check the verity of a record independently, and keeps peers in the network from forging certificates. To speed up certificate verification, CoDoNS servers cache the certificates along with the resource records and provide them to the clients. Existing clients that are not DNSSEC compliant need to trust only the local CoDoNS servers within their administrative domain, since CoDoNS servers internally verify data fetched from other nodes.

Codon authenticates name owners directly through certificates provided for every insertion, delete, and update.  Insertions simply require a signed resource record with a corresponding well-formed certificate. A version number associated with each record, signed by the owner and checked by every server ensures that old records cannot be reintroduced into the system. Deletions require a signed request that identifies the record to be expunged, while updates introduce a new signed, self-verifying record that replaces the now stale version.

Since CoDoNS removes authority from the identity and location of the server providing resource records and vests it with cryptographic keys, it provides a greater degree of freedom over namespace management. CoDoNS  enables multiple namespace operators to manage the same part of the name hierarchy. A domain owner can delegate management of the same sub-domain to multiple operators by endorsing their keys as being authoritative for that sub-domain.  Ideally, competing operators would preserve a single consistent namespace by issuing names out of a common, shared pool. In the presence of conflicting or inconsistent records, clients simply pick the records signed by an operator they trust, similar to the way they pick between separate sets of root servers today. Essentially, name owners have the ability to choose the namespace operator that will endorse their records based on price, service and functionality.  Since DNSSEC has not yet been widely deployed in the Internet, CoDoNS cannot rely on the legacy DNS to provide certificates for resource records. Consequently, CoDoNS uses its own centralized authority to sign resource records fetched from the legacy DNS. Queries to the legacy DNS are directed to a small pool of certifying resolvers, which fetch authoritative resource records from the legacy DNS, sign them, and append the sig records to the legacy DNS response. This approach requires trust to be placed in the certifying revolvers. Threshold cryptography can be used to limit the impact of adversaries on these resolvers until CoDoNS takes over completely. The certifying name resolvers ensure that CoDoNS participants cannot inject corrupted records into the system

4.        EVALUATION

4.1        Setup

Authors setup a peer-to-peer network of CoDoNS servers on globally distributed Planet Lab nodes. The We started the CoDoNS servers with no initial DNS records. After an initial quiescent period to stabilize Pastry, authors issue DNS requests from a real workload to the CoDoNS server at each node. During the experiment, authors measure the lookup latency of CoDoNS, and periodically record the load handled and overhead incurred by each node. authors also apply the same workload to the legacy DNS, and measure its performance.

4.2   Lookup Performance

Figure 5 shows the cumulative distribution of lookup latencies incurred by CoDoNS and the legacy DNS. Table 4 summarizes the results of Figure 5 by providing the median, mean, and the 90th percentile of the latency distribution. Authors aggregate the latency during the second half of the workload, allowing the first half to warm the caches of both CoDoNS and the legacy DNS. Note that the second half of the workload also contains DNS requests for domain names not present in the cache, and CoDoNS incurs the extra latency of redirecting these queries to the legacy DNS.  In order to study the impact of legacy DNS redirections on latency, authors separately evaluate the lookup performance of CoDoNS without redirections, by inserting the records at their home nodes before applying the work load. This study essentially evaluates the scenario after a complete take over of the legacy DNS by CoDoNS.

50% of the queries in CoDoNS are answered immediately by the local CoDoNS server without incurring network de-lay, since proactive replication pushes responses for the most popular domain names to all CoDoNS servers. Consequently, CoDoNS provides a significant decrease in median latency to about 2 milliseconds compared to about 39 milliseconds for the legacy DNS. The tail of the latency distribution indicates that cache misses leading to legacy DNS lookups have an impact on the worst-case lookup performance of CoDoNS. However, a complete take over from the legacy DNS would obviate the extra latency overhead. Overall, CoDoNS achieves low latencies in the mean, median, and the 90th percentile, for both deployment scenarios, with and without redirections to the legacy DNS.

Table-4

4.3        Flash crowd Effect

Next, Authors examine the resilience of CoDoNS to sudden upheavals in the popularity of domain names. To model a flash crowd effect, authors take the DNS workload and modify the second half to reflect large scale changes in the popularity of all domain names. Authors achieve this by completely reversing the popularities of all the domain names in the workload.  That is, the least popular name becomes the most popular name; the second least popular name becomes the second most popular name, and so on. This represents a worst case scenario for CoDoNS because records that are replicated the least suddenly need to be replicated widely, and vice versa, simulating, in essence, a set of ash crowds for the least popular records.

Figure 7 shows the median resolution latencies in CoDoNS during the ash-crowd effect introduced at the six hour mark. There is a temporary increase in the median latency of CoDoNS when ash-crowd effect starts. But, Beehive’s proactive replication in the background detects the changes in popularity, adjusts the number of replicas, and decreases the lookup latency. The latency of CoDoNS after popularity reversal quickly reaches the low values in Figure 6, indicating that CoDoNS has recovered completely from the worst-case, large scale changes in popularity.

4.4        Load Balance

      Authors evaluate the automatic load-balancing provided by proactive replication in CoDoNS by quantifying load balance using the coefficient of variation, defined as the ratio of the standard deviation of the load across all the nodes to the mean load. The overall average of query load is about 6:5 per second for the system.

Figure 8 shows the load balance in queries handled by Cordons servers, either from their internal cache or by querying the legacy DNS, for the duration of the workload. At the start of the experiment, the query load is highly unbalanced, since home nodes of popular domain names receive far greater number of queries than average. The imbalance is significantly reduced as the records for popular domains get replicated in the system. Even when a ash-crowd is introduced at the six hour mark, dynamic changes in caching keep the load balanced after a temporary increase in load variance. Overall, continuous monitoring and adaptation of proactive caching enable CoDoNS to respond to drastic changes in the popularity of names and handle ash crowds.  The network bandwidth and per-node storage costs incurred by proactive caching are modest. The average band-width consumed over the entire experiment was 12.2 KB/s per node (std. dev. 2.26 KB/s) for all network activities.  The average number of records per node was 4217 (std. dev.  348), a mere  10% of the total number of records. These records require, on average, 13 MB per node. These measurements indicate that CoDoNS distributes the load evenly across the system and incurs low uniform bandwidth and storage overhead at each node.

4.5        Update Propagation

       Next authors examine the latencies incurred by CoDoNS for proactive update propagation. Figure 9 shows the delay incurred for disseminating updates to resource records replicated at different levels. 98% of the replicas are updated within one second even for level-0 records, which are replicated at all nodes in the system. It takes a few seconds longer to update some replicas due to high variance in network delays and loads at some hosts. The latency to update 99% of replicas one hop from the home node is about one   second. Overall, update propagation latency in CoDoNS depends on the extent of replication of records. In the worst case, it takes logN hops to update all the nodes in the network. For a million node CoDoNS network, updating 99% of replicas would take far less than a minute for even the most popular domain names replicated throughout. This enables name owners to relocate their services without noticeable disruptions to their clients.

5. CONCLUSIONS

The Domain Name System is a critical component of the Internet. The growth of the Internet namespace, the explosion in the number of networked hosts, and the recent emergence of large-scale coordinated attacks have strained the hierarchical, static architecture of the legacy Domain Name System. DNS is vulnerable to DoS attacks, incurs high latencies for query resolution and update propagation, suffers from misconfigurations, and is difficult to administer.  

This paper proposes a novel alternative for DNS, called CoDoNS. CoDoNS retains the most successful parts of the DNS design; namely, the hierarchical partitioning of the namespace, the independent management of different parts of the hierarchy, and the general-purpose database inter-face. CoDoNS combines peer-to-peer overlay networks with analytically-informed proactive caching to provide an alter-native DNS infrastructure. It resists denial of service at-tacks, heals around failures, automatically distributes load, supports fast updates and adapts quickly to ash crowds. It decouples name service from the physical location of name-servers through cryptographic delegations, and creates a competitive marketplace for name services. Performance measurements from a deployment on Planet Lab using real DNS workloads indicate that CoDoNS can significantly improve the lookup performance of legacy DNS with modest storage and bandwidth overhead.

CoDoNS  provides a new platform for name owners to efficiently publish and manage their data. Our current implementation and deployment provides a simple incremental migration path from legacy DNS towards the performance and functionality offered by CoDoNS. During this process CoDoNS can serve as a safety net alongside legacy DNS.

6.      References and Further Readings

1. Internet Systems Consortium. BIND Vulnerabilities.  

      www.isc.org/sw/bind/bind-security.php, Feb 2004.  

2. ]E. Cohen and H. Kaplan. Proactive Caching of DNS Records:  Addressing a    Performance Bottleneck.  Symposium on Applications and the Internet, San   Diego-Mission Valley CA, Jan, 2001.

3. P. Mockapetris   Domain Names: Concepts and Facilities. RFC 1034, Nov 1987.

4. M. Castro, P. Druschel, A. Ganesh, A. Rowstron, and D. Wallach.  Secure

      Routing for Structured Peer-to-Peer Overlay Networks. Symposium on

           Operating Systems Design and Implementation, Boston MA, Dec 2002.