Scalable and efficient domain name resolution

SCALABLE AND EFFICIENT DOMAIN NAME RESOLUTION

0002A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND

00041. FIELD OF THE INVENTION This invention relates generally to enhanced domain name servers, and more particularly, to efficiently processing domain name queries in a network such as the Internet.

2. BACKGROUND

0006The Internet has brought about an information revolution through the

0007development of computerized information resources, on-line services and the World

0008Wide Web (WWW). The Internet is growing rapidly, with an ever increasing number

0009of computers and users being connected to the Internet daily.

0010In order for devices (computers, printers, and the like) on a network such as

0011the Internet to be able to communicate with each other, the devices need to know (or

0012be able to determine) each others^* addresses. Many distributive systems (e.g.. the

0013Internet) assign device names in the distributive system by a hierarchical naming

0014scheme known as domain names. An Internet domain name is generally a sequence

0015of domain labels separated by periods. For example, "a.ultradns.com" is a domain

0016name where "com^" is a top level domain name of a top level domain, "ultradns" is a second level domain name of a second level domain and "a" is a third level domain name of a third level domain. A device in a domain is labeled by the name of the device followed by the domain name. Thus, a device labeled "server" in the "a.ultradns.com" domain has the name, "server.a.ultradns.com". A device name is

0017also referred to as a domain name. The Domain Name System (DNS) is a distributed hierarchical database comprised of client/server transaction servers that provide a

0018mapping from domain names to associated information, e.g., to LP addresses.

0019While domain names partition a distributive system in a logical and

0020hierarchical manner, messages are transferred between devices of the DNS by

0021identifying devices using specific IP addresses. In the present Internet protocol, LP

0022addresses are thirty-two-bit numbers that are expressed as four eight-bit values (i.e., four numbers in the range 0 to 255) separated by periods, e.g., "121.121.122.2". IP addresses contain information such as a network identifier ("ID") of a device network

0023connection and a device ID. IP address are assigned by an address authority. The

0024addresses are assigned in blocks to authoritative address servers.

0025A comprehensive description of the operation of domain name servers and IP

0026addresses is given in DNS and BIND In A Nutshell, Paul Albitz and Cricket Liu,

0027O'Reilly & Associates, 1994, ISBN: 1-56582-010-4, which is incorporated herein by reference.

0028IP addresses also relate to each other in a hierarchical manner. Thus, the DNS

0029also provides a "reverse mapping" of IP addresses to domain names, by using a

0030representation of the IP address that follows the DNS indexing model. However, the

0031domain name hierarchy and the IP address hierarchy are not directly related to each other. While some name servers are also address servers, name and address servers do

0032not have to be the same device. Thus, it is possible for a server to have authority to resolve a domain name into a corresponding IP address of a device, the same name server may not be able to resolve the IP address to the corresponding domain name of

0033the same device. Thus, resolution of IP addresses to domain names follows a similar

0034process as resolving domain names to IP addresses except different servers may be

0035involved.

0036Because IP addresses are numerical and, unlike domain names, are assigned without regard to the logical and hierarchical organization of the DNS, domain names

0037are generally used in instructions for functions such as data transfers. Thus, a data

0038transfer instruction identifies the receiving device by its domain name. However, the

0039domain name must be translated into a corresponding IP address before the data transfer can occur.

0040Domain names are managed by authoritative devices called name servers. That is, domain name servers perform the task of converting names to IP addresses. Name

0041servers translate domain names into corresponding IP addresses and vice versa. When

0042a first device desires to transfer a message to a second device known only by its domain name, the first device must query a name server to acquire the corresponding

0043IP address to the known domain name of the second device.

0044It is estimated that by the year 2003, the number of domains on the Internet

0045will increase ten-fold, exceeding 150 million domains. Associated with this increase

0046in the number of domains will be an increase in user dissonance. Current

0047implementations of the Domain Name System are entirely inadequate and unable to

0048handle resultant DNS files' size or the magnitude and frequency of changes to these

0049DNS files. Even today, real problems exist with content access and/or content

0050distribution over the Internet. It is estimated that ten to thirty percent of Internet

0051connection events are unsuccessful or unsatisfactory. SUMMARY

0052The present invention provides a scalable and flexible platform for providing global directory services. In some embodiments, the invention uses redundant information servers to provide ubiquitous and high-performance access to directory services. This system of servers leverages the scalability and replication mechanisms provided by commercial database software. The DNS according to the present invention has an underlying modular design which allows additional wire-protocol services to be easily incorporated into the system, and allows additional modules to provide intelligent/dynamic responses by affecting changes in the data repository. In various aspects, the present invention:

0053• Supports large-scale service model better than alternative DNS servers.

0054• Integrates other Internet services, e.g. "whois", in a single data repository.

0055• Multi-threaded server provides scalability to exploit commercial-level hardware.

0056• Modular database implementation facilitates the addition of new features.

0057• Database replication provides for ease of management of distributed servers, and database backup features provide information integrity.

0058Globally distributed server replicas provide the reliability, throughput and low delay required to scale a large commercial service. The servers are tied together using advanced Internet routing mechanisms that are reactive to the state of individual server replicas.

0059Multiple servers provide increased system throughput, reliability in the event of server failure, reliability in the event of provider network failure and nearest server mechanics serve as basis for advanced redirection service. Embodiments of the present invention provide a DNS system based on an information-centric design, where multiple system components interact with system state that is maintained in the database. The database provides both the principle Internet information, and the required associations and configuration to specify the operation of the active components. The system allows for reduced operational staff requirements by supporting custom user-interface for direct management of user data, with integrated security and data validation to maintain data integrity.

0060The present invention also provides:

0061• Information update via multiple user-specific custom interfaces, program APIs, or Internet services such as dynamic DNS updates.

0062• Fine-granularity security based on association between login and information objects.

0063• Modular active components for reporting, billing and data integrity checking.

0064In one aspect, this invention provides a system for processing domain name

0065requests. The system includes a query mechanism constructed and adapted to (a)

0066obtain a user request for response information corresponding to a particular domain

0067name; and (b) provide complete response information in a single response to the user

0068request. The user request may be a domain name resolution request, in which case the

0069query mechanism provides an Internet Protocol (IP) address corresponding to the

0070domain name. The system accommodates user requests for other typed DNS data.

0071In some embodiments the a query mechanism is further constructed and adapted to provide the response depending on context information. The context

0072information may include at least one of (a) context information from the request; (b)

0073context information from the system; and (c) global context information. The context information may include address information indicating an address of the user; the local time; and/or the location of the system.

0074In some embodiments, the system has a data cache and the query mechanism

0075is further constructed and adapted to, upon receipt of a user request, first attempt to

0076find an answer to the user request in the data cache.

0077In some embodiments, the query mechanism is further constructed and adapted to (a) if the answer exists in the data cache and the answer is fresh, send the

0078answer directly from the cached data; and (b) if the answer exists in the data cache

0079and the answer is stale, or if the answer does not exist in the data cache, then acquire

0080the answer from a database; send the answer; and update the data cache to reflect the acquired answer.

0081Sometimes items in the data cache have a maximum lifetime which ranges from the time to live of the lowest resource record in a complete answer to the

0082maximum cache time value configured for the system as a whole.

0083In some embodiments, the query mechanism is further constructed and adapted to implement negative caching such that if a request is made for a host that

0084does not exist in an active domain, the negative response will be saved in the cache.

0085In another aspect, this invention is a method of providing an Internet Protocol

0086(IP) address of one of a plurality of devices on the Internet. The method includes

0087obtaining a user request for an IP address corresponding to a particular domain name;

0088and providing the IP address in a single response to the user request. The method

0089may include providing the IP address depending on context information. The context

0090information may include at least one of (a) context information from the user request;

0091(b) local context information; and (c) global context information. In yet another aspect, this invention is a system comprising a network of

0092distributed Domain Name Servers (DNSs), each DNS comprising a database; and a query mechanism constructed and adapted to obtain from the database a user request

0093for response information corresponding to a particular domain name; and to provide complete response information in a single response to the user request. The databases

0094in the network are replicated.

BRIEF DESCRIPTION OF THE DRAWINGS

0096The objects and advantages of the invention will be apparent upon consideration of the following detailed description, taken in conjunction with the

0097accompanying drawings, in which the reference characters refer to like parts throughout and in which:

0098FIGURE 1 provides an overview of embodiments of the present invention

0099operating within the Internet; and

0100FIGURE 2 depicts the logical structure of the database schema according to

0101embodiments of the present invention.

DETAILED DESCRIPTION

0103With reference to FIGURE 1, a Domain Name System (DNS) server 100

0104(DNSi) according to the present invention comprises a database 102 having a unique database schema and a complementary unique SQL interface 104. A query

0105mechanism 106 uses the SQL interface 104 to query the database 102 and to return

0106results to requesting users, e.g., user 108.

0107The present invention can be considered at two levels, namely at a server level

0108(e.g., DNSi 100) and at a system level (e.g., DNSi, DNS₂, ..., DNS„).

01091. Server-level: At the server level, this invention provides mechanisms that enable a DNS server (e.g., DNSj 100) according to the present invention to achieve sufficient performance (circa thousands of queries/second) even though the underlying data repository supports basic data retrieval at a rate of hundreds of queries/second. Features of this server level, discussed below in detail, include:

0110• Aggregate database queries

0111• Common case optimizations

0112• Data caching (and consequently-required cache invalidation mechanisms)

01132. System-level: At the system level, this invention provides mechanisms that enable a system of DNS servers (e.g., DNSi, DNS₂, ..., DNS_n in FIGURE 1) to provide enhanced/integrated management of information, and provides various levels of performance enhancement for incoming queries and internal transactions. Features of this system level, discussed below in detail, include:

0114• Modular data-centric design

0115• Database-layer synchronization

0116• Single IP address announcement of replicated servers

0117The server-level mechanisms according to the present invention enable the

0118DNS server to achieve a greater transaction throughput rate. The system-level

0119mechanisms work synergistically, and allow the DNS System according to the present

0120invention to provide a diverse set of features and benefits.

0121The server-level mechanisms according to the present invention enable the

0122modular data-centric design and database-layer synchronization. SERVER-LEVEL MECHANISMS

0123A name server response to a DNS query requires a complex set of calculations

0124that allow:

0125(a) different responses to be returned depending on the servers authority, (b) different answers depending on the existing domain name data, and

0126(c) the server to return an answer comprised of multiple inter-dependent sections.

0127Specifically, a DNS's response algorithm must consider at least the following:

0128• Three response sections: Answers, Authority, and Additional • CNAME (domain name alias) dereferencing

0129• Wild card matching (matching of leading superstrings)

0130• Iterative domain name search (matching the longest recognized domain name)

0131Conventional (prior art) DNS servers make many distinct queries to the data

0132repository in order to determine the correct records to include in a response.

0133Consequently, the transaction rate of the DNS server will be reduced by a similar

0134factor (e.g., if eight database queries are required, transaction rate will be reduced by

0135approximately a factor of eight). The DNS server according to the present invention

0136significantly reduce the average number of queries required to construct a DNS

0137response, as compared with conventional so-called "straight forward" algorithms that

0138depend on many distinct queries to the data repository.

0139Aggregate Database Queries

0140The DNS server according to the present invention uses compound database

0141queries so that a single query can return multiple component records required to

0142construct a DNS response. Moreover, database queries are correlated so that in

0143instances where multiple queries are required, subsequent queries can be optimized based on records retrieved by earlier database queries. The DNS query strategy according to the present invention:

0144(a) retrieves combinations of Answer, Authority, and Additional records in a single query, (b) retrieves available CNAME records along with

0145Answer! Authority/ Additional records, and (c) reduces iterative domain name search overhead by correlating records from different iterations. With this invention, the number of database queries required to construct a

0146complete DNS response can be as low as one. This is a considerably improvement when compared to a similar strategy based on simple database queries that would

0147require a separate query for each of Answers and Authority, and multiple queries for

0148Additional records.

0149Common Case Optimizations

0150In general, common case optimizations are effective in systems where there

0151are a number of distinct potential outcomes (a) with different probabilities of

0152occurrence, (b) requiring varying levels of incremental overhead, and (c) where a

0153determination can be made that a specific outcome has been reached, without an

0154exhaustive outcome analysis.

0155The present invention recognizes that common case optimization is applicable

0156to the DNS server database query strategy, and has identified two specific

0157optimizations based on knowledge of DNS protocols and the expected incoming

0158query stream. The DNS system according to the present invention implements these

0159optimizations by making the test for (and handling of) each case a separate code

0160segment, and promotes this code to handle the task prior to the execution of any general query code. Case #l:

0161The DNS server according to the present invention contains authoritative answer for a domain name query that is one label longer than the zone's domain name (e.g., with a zone name of "foo.com ", then an optimization is effective for

0162"www.foo. com " but not for "www. mkt.foo. com ").

0163Case #2:

0164The DNS server according to the present invention has delegated the next-

0165level subdomain name (e.g., the incoming query is for the domain name

0166"www.mkt.foo.com ", which is in the zone "foo.com ", then the optimization is

0167effective if the "mkt.foo.com " zone has been subdelegated).

0168The use of these specific optimizations does not preclude the development of

0169additional optimizations. The fundamental realization and requirements remain unchanged, allowing common case optimizations to be applied to outcomes based on

0170revised outcome probabilities. Specifically, further common case optimizations specified rely on restrictions

0171on the records in the database to guarantee the validity of the query response. For

0172example, a generalization of Case #1 (above) that optimizes for arbitrary length

0173domain name queries (e.g., the incoming query is for the domain name

0174"www.unit.mkt.foo.com " within the zone for "foo.com "). This case can be optimized

0175if no conflicting records are present, i.e., any record that could alter the precedence

0176made for the optimization case (e.g., an intervening NS record or wildcard record

0177associated with the domain name "mkt.foo.com " would have an impact on the above

0178example of "www. unit, mkt.foo. com " in zone "foo. com ").

0179Additionally, the DNS query strategy according to the present invention allows for flexible/dynamic optimization code to be constructed, where, e.g., a specific ordering of individual common case optimizations is associated with each zone, based on prior knowledge or statistics maintained about each zone. This technique can be applied so that the best strategy is selected at the granularity of each zone, each server, or any identifiable class of query stream.

0180Data Caching and Cache Invalidation

0181Dynamic data caching is a mechanism that has been applied to achieve performance in many types of systems, but has never before been use to provide a fast-access data repository of authoritative data within an Domain Name Server. The Domain Name System was designed with an integrated "time to live" (TTL) caching mechanism, and we note three example applications of caching elsewhere within the Internet and Domain Name System.

0182• Applications such as web browsers frequently maintain copies of DNS records obtained while processing HTTP requests, and use applicable DNS records for subsequent requests. This use of caching does not maintain authoritative data, nor does it directly effect the operation of a DNS server.

0183• Caching DNS servers (also known as recursive servers or "helper" servers)

0184provide a separate function from "hosting" DNS servers. Recursive servers act

0185on the behalf of an application (e.g., a user's web browser) and query a

0186hierarchical series of hosting DNS servers to obtain the required DNS

0187response. Information obtained in the course of a DNS query resolution may

0188be maintained and used to expedite subsequent DNS queries, until each

0189record's specified time-to-live has expired. This is a fundamental use within

0190the DNS, but only addresses the behavior of non-authoritative servers when

0191handling authoritative data. • Conventional primary DNS servers (e.g., as embodied by the "bind" server distribution) read all authoritative domain information into a computer memory directly from files, and answer queries based on a complete memory- resident copy of all domain information. Unlike the above caching examples,

0192this is not an application of dynamic caching, but is a static copy of DNS information that does not change or replace based on well-known caching

0193criteria such as frequency of use, nor does it embody any dynamic

0194mechanisms for maintaining cache consistency. There is no dynamic

0195mechanism for a "cache miss" that involves the standard alternative method of making a backup query to the primary (i.e., non-cache) repository.

0196According to embodiments of the present invention, the DNS server maintains an internal dynamic cache of recently-used authoritative DNS records taken from the

0197database repository. Two embodiments are specified: (1) where individual resource records are cached separately and subsequent DNS response are comprised of the individual records, and (2) where the entire response to a DNS query is cached as an

0198aggregate and are immediately available for a subsequent response, eliminating

0199overhead required to construct a complete response. The strategy for handling

0200incoming DNS queries includes an examination of the internal cache for efficient

0201access to data, and if not available, a subsequent query to the primary data repository (database) is made. These mechanisms are used for both "positive caching," i.e.,

0202when the data exists, and "negative caching," i.e., when the server can authoritatively

0203respond that the information does not exist.

0204The DNS server according to the present invention also embodies cache replacement mechanisms to control the amount of "stale" (infrequently used) data in the cache, and to allow for effective utilization of cache and system resources. Multiple embodiments exist to remove DNS data from the cache based on frequency or timeliness of use.

0205Cache Invalidation

0206A dynamic caching system must employ cache invalidation mechanisms to guarantee that information in the cache corresponds to the state of the primary data repository. This requires that data items are removed from (or replaced within) the cache when the corresponding information is changed within the primary data repository. This allows a DNS server according to the present invention to accurately reflect the correct information within the system.

0207The DNS server according to the present invention are embodied by a number of related cache invalidation mechanisms that address the complete range of transaction types that can be performed on the primary data repository, and the type of cache data that can be maintained in the system. The design space that defines the cache transactions of interest is represented by the Table below which specifies twenty four different cache invalidation transactions that can be addressed by the invention's cache invalidation strategy. Note that not every space need be addressed by a particular embodiment of the invention, and that some cache invalidation mechanisms will address multiple invalidation requirements.

0208<img file="WO0052594A2_D0001.tif" /> Multiple embodiments exist to remove DNS data from the cache based on frequency or timeliness of use.

0209Cache Invalidation

0210A dynamic caching system must employ cache invalidation mechanisms to guarantee that information in the cache corresponds to the state of the primary data repository. This requires that data items are removed from (or replaced within) the cache when the corresponding information is changed within the primary data repository. This allows a DNS server according to the present invention to accurately reflect the correct information within the system. The DNS server according to the present invention are embodied by a number of related cache invalidation mechanisms that address the complete range of transaction types that can be performed on the primary data repository, and the type of cache data that can be maintained in the system. The design space that defines the cache transactions of interest is represented by the Table below which specifies twenty four different cache invalidation transactions that can be addressed by the invention's cache invalidation strategy. Note that not every space need be addressed by a particular embodiment of the invention, and that some cache invalidation mechanisms will address multiple invalidation requirements.

0211<img file="WO0052594A2_D0002.tif" />

021214 Multiple invalidation mechanisms can be applied together, so that each addresses a subset of the potential cache interactions and requirements. Further, these mechanisms can embody varying criteria for timeliness of data invalidation, according to the importance assigned to each subset. For example, when caching entire DNS responses the data within an Answer section may be considered more critical than the data within an Authority section. In this case, mechanisms can be employed that immediately respond to updates to information in the Answer section, while other less timely mechanisms will eventually invalidate the records within the Authority section.

SYSTEM-LEVEL MECHANISMS

0214The system-level mechanisms according to the present invention work synergistically, enabling the DNS System according to the present invention to provide enhanced/integrated management of information, and to provide a range of performance enhancement for incoming queries and internal transactions.

0215• Modular data-centric design

0216• Database-layer synchronization

0217• Single IP address announcement of replicated servers

0218Modular Data-Centric Design

0219The DNS domain name server according to the present invention (e.g., DNSi

0220100 of FIGURE 1) separates the functionality of the standard monolithic Internet

0221server into two distinct components: a commercial database system as the data

0222repository, and a DNS wire-protocol server designed to answer queries based on

0223authoritative DNS data from the database component. This architectural choice

022415 provides for a clean modular design, which in turn provides a flexible and scalable platform that is leveraged to provide a diverse set of features and inventions.

0225• Data-Centric Modeling and Functional Server Module Extensions — The two- component design aliows for modular extensions to both the data model, and the functions (e.g., servers) that operate on the system. Embodiments of this invention include, but are not limited to, one or more user interfaces for data management, transaction processors to provide an extensible API for data management, Internet system monitors that can query external system status (e.g., webserver availability) and affect changes to the data repository, and servers for other Internet directory servers (e.g., whois, radius, etc).

0226• Integrated Access Control Mechanisms — Using a database repository for DNS information allows several principle objects (e.g., users and other network data schemas) to be modeled and managed. A significant feature of the DNS Domain Management System according to the present invention is the ability to control and delegate the many-to-many access patterns of users accessing domain name data.

0227• Query and Context Specific Responses — Conventional (prior art) DNS servers

0228take as input a <domain name, query type, query class> tuple, and return the

0229appropriate resource records. The DNS system according to the present

0230invention has revised the basic query/response transaction by incorporating additional fields within the data model such that the response to a query can be

0231based on additional criteria. These criteria can be comprised of information

0232obtained from the incoming query (e.g., source IP address), information

0233available to the local server (e.g., time of day or server identity), and similar context or query specific information.

023416 • Dynamically Configurable DNS Record Types — The DNS server according to the present invention allows new resource record types to be defined, and immediately incorporated into the system. Based on resource record templates included in the data model, the DNS server according to the present invention system can incorporate new record types in minutes without additional low- level code development. This is in contrast to the conventional (prior art), where deployment of a new resource record type requires considerable low- level program design and coding, and requires a new server binary be deployed on all applicable machines. Moreover, combined with context specific responses (above), domain administrators may define their own

0235"local" types that are specific to the answers returned for their DNS domain.

0236• Ability to deploy and maintain a state-of-the-art data management service based on commodity implementations of core database technologies. The conventional (prior art) systems for Domain Name System management

0237deploy integrated ad-hoc implementations of database technology, which lag

0238advanced database features and make it difficult to deploy new features based

0239on database technology advances.

0240Database-Layer Synchronization

0241The DNS system according to the present invention maintains data

0242consistency between multiple redundant servers (e.g., DNS , DNS ₂, ... , DNS,, in

0243FIGURE 1) by propagating changes to the managed data using database-level

0244transaction processing. This has advantages over conventional (prior art) consistency mechanisms, which are based on application-level transactions. These advantages

0245include:

024617 • Virtually immediate propagation of changes to Domain Name System information. This is particularly important when inaccurate information must be corrected, or when critical domain information changes frequently and changes must be visible quickly. For example, one of the most frequently changed zones, ".COM", also has the greatest number of records. Using conventional (prior art) systems, ".COM" has historically been restricted to a twelve-hour periodic updates. Using the DNS system of the present invention, changes to ".COM" are routinely propagated within 5-15 minutes.

0247• Ability to accept and propagate changes to Domain Name System information

0248from multiple servers, and consequently, the ability to make data management more reliable with better system availability and performance. This is in

0249contrast to conventional (prior art) DNS systems, which do not have the conflict resolution mechanisms required to support multiple sources of update

0250transactions.

0251Single IP Address Deployment for Replicated Servers

0252Globally distributed server replicas (e.g., DNSi, DNS₂, .... DNS„) provide the reliability, throughput and low delay required to scale a large commercial service.

0253The servers are tied together using advanced Internet routing mechanisms that are

0254reactive to the state of individual server replicas. In preferred embodiments, each

0255DNS system according to the present invention shares a common IP address and

0256supports a name server replica. The shared IP addresses are injected into the Internet

0257routing mesh by each server so that Internet routers will direct IP packets to the

0258nearest topological server. Each server replica is monitored for correct behavior, and

0259the EP route is withdrawn if the server no longer responds to DNS queries. This

0260mechanism provides the following benefits:

026118 • User DNS queries are directed to the nearest DNS replica minimizes the delay experienced for DNS resolution.

0262• Transitory server and network failures are transparent to a user's DNS query and application transaction. Servers that are not reachable or functional are invisible, and DNS queries arrive at the nearest functional server without experiencing the delay for standard DNS timeout and retransmission.

0263• The DNS system acquires user proximity information based on the server replica that receives the user DNS query. This information can be used to

0264provide proximity based responses to direct users to nearby application

0265servers.

IMPLEMENTATION

THE DATABASE

0268This section describes the unique database schema of the database 102.

0269OVERVIEW The database 102 according to preferred embodiments of this invention is

0270organized and structured according to the following unique database schema. The

0271database schema involves fourteen (14) tables. Only three (3) of these tables contain

0272actual data (i.e., DNS &amp; Contact), the other eleven (11) tables are needed to manage

0273the data. The schema allows management of who has access to which data, how can

0274they access it, who can create new data, and how they should be billed for use of the

0275system.

0276The data managed by the DNS Server 100 is (a) contact information, (b) zone

0277information, and (c) resource record information. Although zones and resource records are related, the system must have the ability to manage them distinctly. The

027819 reason for this is to enable targeting different users, some of which want to use the Server 100 to manage an entire zone for them, and some of which will just enter individual resource records (in a particular zone).

0279For any data that can put in the system, there are two access control mechanisms involved: (1) a mechanism that specifies whether the item can be put in (created) in the system, and (2) a mechanism that specifies how items can be accessed.

0280TABLE LIST &amp; SUMMARY

0281<img file="WO0052594A2_D0003.tif" />

028220 <img file="WO0052594A2_D0004.tif" />

TABLE SCHEMA

0284This section describes what information is in the tables and, in some cases, gives the formats and sizes of the data used in some embodiments of the present invention.

0285The LOGIN table describes identity within DNS system of the present invention. The table includes information on how to authenticate a user to system. The LOGIN Table is established via login/password, X.509, PGP, DNSSec, etc.

0286The following table summarizes the fields of the LOGIN table.

0287<img file="WO0052594A2_D0005.tif" />

0288The SYS_MGMT table (described below) provides a template about use, access, etc. It provides information about how the system is managed; who can access, modify, create new "objects", and information on how users are charged for

028921 access. The SYS MGMT table allows the DNS according to the present invention to be deployed in different ways (e.g., closed access at large companies versus open ISP access). Some preferred embodiments allow deployment of two object types to be created, namely contacts and zones. Both can be created by anyone. Contacts can be created at no charge; zones may or may not incur charges (perhaps per-user).

0290<img file="WO0052594A2_D0006.tif" />

0291The RR.TUMBO table represents DNS resource record (RR) information. This table is for the "index" or "lookup" of the incoming query, and contains columns for different parts of RR data section. Resource records are defined in RFC 1035 [Network Working Group Request for Comments: 1035, P. Mockapetris, ISI, November 1987] which is incorporated herein by reference.

0292<img file="WO0052594A2_D0007.tif" />

029322

0294<img file="WO0052594A2_D0008.tif" />

0295A "DNS lookup" in the RRJUMBO table uses (matches against) the following six values to find the requested DNS resource record:

02961. domain name (from dns query packet)

02972. dns type (from dns query packet)

029823 3. dns class (from dns query packet)

02994. server id (name/id of server answering query)

03005. time (current time of day at server)

03016. source IP address (from the EP packet)

0302Note that the use of the RRdata fields, fl ... f8, depends on the type of RR (e.g., MX records will use fl and f2, A records will only use fl, and SOA records will use fl - f7).

0303The RRJUMBO table is used to store data for multiple purposes: in addition to storing "live" domain records, "template" records are stored which embody the mechanism to provide configurable DNS records. Each DNS Resource Record type is represented by one or more template records in the RRJUMBO table which specify the format and structure of each record type.

0304The CONTACT Table contains information about a person, role, or organization (i.e., this is basically "whois" information). Note that the information in the CONTACT Table has nothing to do system login.

0305<img file="WO0052594A2_D0009.tif" />

0306The TYPE values for above "type" field (similar to RIPE-181) include: name

030724 email email-alt phone phone-alt fax-no nic-hdl nic-hdl-alt address (multiple-line text string) source (in case information came from another place) date-create date-update

0308The CONTACT ASSOC Table indicates association between contact information, and other data/items (e.g., zones or RRs)

0309<img file="WO0052594A2_D0010.tif" />

0310The ZONE table basic information about a group of related RRs.

0311<img file="WO0052594A2_D0011.tif" />

0312The ZONE_INTERFACE Table specifies external servers (i.e., servers that are not embodiments of the present invention) that must either be used as primary/master, or updated as secondary/slave.

031325

0314<img file="WO0052594A2_D0012.tif" />

0315The ZONE CNTL Table contains zone control information, similar to SOA parameters. This Table is used for database consistency (may not be needed with internal Oracle, however, can specify interface with external servers).

0316<img file="WO0052594A2_D0013.tif" />

0317The ZONE_MGMT table includes information about how a particular zone is managed; who can access, modify, create new "objects", and information on how the user is charged for access.

0318<img file="WO0052594A2_D0014.tif" />

031926

0320<img file="WO0052594A2_D0015.tif" />

0321The ZONE_SERVERS table is an auxiliary table listing zones for which the system is responsible. This table is used by servers to find zones for which they are authoritative.

0322<img file="WO0052594A2_D0016.tif" />

032327 The RR MGMT Table provides an access list for specific RRs.

0324<img file="WO0052594A2_D0017.tif" />

0325The BillingPolicy table (set by owner(s) of system or zone) contains information about how to bill for system use. The owner of system sets this up ahead of time, and the system enforces the various billing policies.

0326<img file="WO0052594A2_D0018.tif" />

0327Each zone may specify more than one policy. For example,:

0328<img file="WO0052594A2_D0019.tif" />

032928 <img file="WO0052594A2_D0020.tif" />

0330The BILLΓNGINFO Table contains information about who and when to bill for use.

0331<img file="WO0052594A2_D0021.tif" />

0332The USAGE HIST Table contains historical system/information usage information. Can attach to various objects: RRdata, Zone, Contact, etc. (Some preferred embodiments attach to RRs)

0333<img file="WO0052594A2_D0022.tif" />

0334Preferably use logging is (a) only turned on for some records, and (b) could be a "premium service". Must keep "current" usage for billing, but this feature is

0335"turned on".

033629 The EPv4Range Table contains CIDRized subnet masks, primarily used for address based (i.e., weak) authentication. This table is used for (a) handing out RRs based on srcipaddress, and (b) simple access control for updates to data (e.g., using dynamic updates as implemented).

0337<img file="WO0052594A2_D0023.tif" />

0338Example

0339<img file="WO0052594A2_D0024.tif" />

0340#1 allows small number of addresses; #2 prohibits small number of addresses; #3 allows all in range, with exceptions;

034130 The following section provides the database field formats and sizes for a preferred embodiment of the present invention. Some of the fields have common sizes:

0342256 char = dnames

034310 num = 32bit integers (e.g., EPv4addr and time in seconds)

034414 num = internal identifier

0345<img file="WO0052594A2_D0025.tif" />

0346<img file="WO0052594A2_D0026.tif" />

0347<img file="WO0052594A2_D0027.tif" />

034831

0349<img file="WO0052594A2_D0028.tif" />

0350<img file="WO0052594A2_D0029.tif" />

0351<img file="WO0052594A2_D0030.tif" />

0352<img file="WO0052594A2_D0031.tif" />

0353<img file="WO0052594A2_D0032.tif" />

035432 <img file="WO0052594A2_D0033.tif" />

0355<img file="WO0052594A2_D0034.tif" />

0356<img file="WO0052594A2_D0035.tif" />

0357<img file="WO0052594A2_D0036.tif" />

0358<img file="WO0052594A2_D0037.tif" />

0359<img file="WO0052594A2_D0038.tif" />

036033 <img file="WO0052594A2_D0039.tif" />

0361<img file="WO0052594A2_D0040.tif" />

0362<img file="WO0052594A2_D0041.tif" />

DESIGN CHOICES

0364Probably the least obvious design choice is the way that CONTACT is laid out. What would be more obvious/natural is to have one table row represent each particular contact record . However, this design breaks contact information into multiple fields, and represents each field as a row in the database. This method is more flexible (given the flexible nature of the data), and supports the association and efficient lookup of "ACCESS POLICY" to individual fields (e.g., to allow random people looking at a CONTACT record to see an email address but not see a phone number associated with that record).

0365THE SQL INTERFACE The SQL Interface 104 takes queries/requests for domain name/address resolution and returns the appropriate address and other information. The SQL

036634 implementing the interface 104 in a preferred embodiment is listed below (in the Table titled SQL Query).

EXAMPLE

0368Here is a sample query made by a user 108 of the DNS 100 according to the

0369present invention. The request is processed by the query mechanism 106 which uses

0370the SQL interface 104 to access the database 102.

0371Query: a.b. cd.wonk.com. <type> where the system knows that it has "wonk.com. ZONE"

0372Then, in the worst case, the system has to make the following queries into the

0373database 102: a.b. cd.wonk.com. <type> ## commonly returns ANSWER b. cd.wonk.com. NS ## commonly returns AUTH data

0374a.b. cd.wonk.com. NS ## common to indicate sub-delegation

0375*.b. cd.wonk.com. <type> b. cd.wonk.com. NS

0376*. cd.wonk.com. <type>

0377cd.wonk.com. NS

0378*.d.wonk.com. <type>

0379d.wonk.com. NS

0380*. wonk.com. <type>

0381This invention embodies a query strategy that significantly reduces the

0382average number of database queries required to complete a DNS query.

0383There are essentially two common cases:

0384(1) no sub-delegation — Query gets simple answer for foo.wonk.com

038535 (2) the system will end-up telling about sub-delegation — Query made for a.b. cd.wonk.com gets NS for d.wonk.com

0386In both of the common cases noted above, the answer "dname" is likely to be one component longer than the zone name. So, the system tests this before making the query (i.e., the system does not want to query for "a.b. cd.wonk.com",

0387"b.c.d. wonk.com", and "cd.wonk.com" just to finally say that the delegation is made at "d.wonk.com").

0388Consequently, the following query optimization (in the query mechanism 106) can be used: If the requested name is one component longer than zone name, then look for a quick answer.

0389This can be written as: if (shorten (req. dname) == ZONE) {

0390SQL (<req. dname>, <type> ## SQL (d. wonk. com, <type>, shorten (<req. dname>) , NS) ## wonk.com, NS) if (<type> found) return_answer ; save_NS_for_later () ;

0391SQL (req. dname, NS,

0392" *" + shorten (req. dname) , <type>) ; if (" *" found, return answer and my NS records) ; if (NS found, return authority) ; return (NXDOMAIN) ; }

0393If long request name, check for shortest delegation first. For example, if the request name is "a.b. cd.wonk.com", check if "d.wonk.com" has NS.

0394SQL (shorten. to_one_piece (<req. dname>) , NS) ; if (NS found) return;

0395If neither optimization worked then start with original question.

0396SQL (<req .name> , <type>,

039736 zone . name , NS) ; if (answer found) { return (answer + NS) ; } else { save_NS_for_later () ;

0398}

0399If no answer is found then loop through and look for NS delegations. for (working_name = req. dname, next__name = shorten (working_name) ; next ! = zone ; working_name = next_name, next_name = shorten (working_name)

0400⁾ {

0401SQL (working_name, NS) ; if (NS found) return,-

0402No delegation made.

0403Now loop looking for "*" records. for (working_name = shorten (req. dname) , next_name = shorten (working_name) ; next ! = zone ; working_name = next_name, next_name shorten (working name)

04045QL (^•>-.*" _|_ _WOrking_name, <type>; if (<type> found) { return (answer + save NS records!

0405return (NXDOMAIN) ; EXAMPLE

0406Give the example query "foo.bar.wonk.com. MX", call following SQL (Table XX) with following variables: req.namel = "foo.bar.wonk.com." req.name2 = " * . bar . wonk. com." req.name3 = "bar.wonk.com." req. type = 15 (this is the MX cype)

040737 req. class = 1 (this is the IN class) req. time = <current_time> req. server = <server ID#> req. ipaddr = <incoming pkt IP source>

SQL QUERY

0409SELECT * FROM rrjumbo, RR

0410The main "start with " clause gets the ANSWERS and AUTHORATATIVE, plus it gets any " * " records that exist.

START WITH (

0412(RR. dname = ^λreq. namel' AND ((RR.type = req . type' ) OR (RR.type = = 2) ) )

0413OR (RR. dname = ^λreq.name2' AND (RR.type = ^xreq. type' ) )

0414OR (RR. dname = ^Λreq.name3' AND (RR.type = 2

AND

0416RR. class = ^''req. class' AND substr (RR. time, req.time', 1) = 1 AND substr (RR. servers, ^λreq. server' , 1 ) = 1 AND

0417RR. active = 1 AND

0418RR . dead = 0 AND

0419This is part of main query, that handles the IPv4range

0420EXISTS (select * FROM ipv4range, IP WHERE RR.ipv4addr = IP.ipid AND IP. low <= req. ipaddr AND IP. high >= req. ipaddr AND IP. flag = 2 AND)

0421This part of query grabs ADDITIONAL records

CONNECT BY

0423PRIOR refl = dname AND type = 1 AND class = req. class' AND substr(time, ^λreq.time', 1) = AND substr (servers, ^Λreq. server' , ) = 1 AND active = 1 AND dead = 0 AND

0424Make certain ADDITIONAL RECORDS also have IPv4 permission

042538 <img file="WO0052594A2_D0042.tif" />

39 OTHER FEATURES

0427Building a modular system has allowed additional mechanisms to be incorporated easily into the system which can serve as the base for new features/uses.

0428CONFIGURABLE RESOURCE RECORD TYPES The DNS according to some embodiments of the present invention has over

0429thirty (30) defined resource record types, which provide data formats/fields for use by

0430different applications; current implementations hard-code the type definitions. Thus, the present invention offers users the ability to dynamically configure RR types, to

0431allow directory- enabled applications to be deployed and tested within short time

0432frames.

CONTEXT SENSITIVE (QUERY-SPECIFIC) ANSWERS

0434In the abstract, a directory service maps a query's incoming request (key) to an outgoing response (data indexed by the key). Using a relational database model gives

0435the present invention an effective mechanism to add other components to the lookup

0436key. In the DNS example, a different answer can be given depending on various context information: from the packet (IP address), from the machine (local time), and

0437from global system (which server location). Thus, for example, the system may

0438provide different answers at different times of day or to different geographic regions.

0439DYNAMIC DATA CACHE In some embodiments, the DNS server 100 incorporates a dynamic load-on-

0440demand cache algorithm which significantly enhances perfonnance by reducing the amount of data that must be retrieved from the database 102.

0441When an inbound query is received, the server 100 will first attempt to find

0442the answer in the data cache 110. If the answer exists and is fresh, the response will

044340 be sent directly from the cached data stored in data cache 110. If the answer exists in the cache 110 but is stale, or if the answer does not yet exist in the cache, the data will be acquired from the database 102, transmitted in the response, and then added to or

0444updated within the cache 110. In some embodiments, the cache is maintained in a

0445Most Recently Used order to optimize lookup times and facilitate cache management.

0446Items in the cache 110 have a maximum lifetime which ranges from the time to live (TTL) of the lowest resource record (RR) in the complete answer to the

0447maximum cache time value configured for the server as a whole. For records that

0448change frequently, the TTL value can be set to zero to ensure the data is never added

0449to cache and always retrieved from the database.

0450By setting a relatively short lifetime on data in the cache 110, the server 100 can provide maximum throughput while still offering near real-time propagation of zone changes. Because the cache is load-on-demand, the DNS daemon can be up and

0451ready to respond to queries within moments of execution.

0452In addition to normal caching of DNS response data, the cache algorithm is designed so that negative caching is also achieved. For example, if a request is made

0453for a host that does not exist in an active domain, the negative response will be saved

0454just like a valid response. If the server is for some reason hit with a barrage of

0455requests for this same invalid host, they can be filled using the negative response in

0456cache, once again eliminating unnecessary calls to the database.

0457Further, in some embodiments, a management thread is incorporated into the

0458cache design. This thread comes to life at a configurable interval and walks through

0459the RR data cache, deleting any stale entries that it encounters. This feature ensures

0460that the most active data is always the most readily available.

046141 in some embodiments, a cache invalidation mechanism is incorporated that is responsible for removing (or modifying) data within the dynamic cache so that the cache accurately and acceptably reflects changes made to the primary data repository.

0462IMPLEMENTATION DETAILS An embodiment of this invention has been implemented. The DNS server 100

0463was designed on top of and tightly integrated with the database 102. The database

0464102 was implemented using Oracle, however, care was taken to modularize the

0465database interface so that the system could easily be integrated with a database from a different vendor, such as Sybase or Informix. The server was developed using Gnu

0466C++ on a Linux platform. The server build process was later expanded to support both Linux and Solaris.

0467Implementations of the present invention can be written in any suitable high-

0468level computer language. Further, while aspects of the present invention have been implemented in software running on a computer system as described above, all

0469aspects of the present invention can also be implemented in hardware or in a combination of software and hardware. That is, although described with reference to

0470a particular system, the present invention operates on any computer system and can be

0471implemented in software, hardware or any combination thereof. When implemented

0472fully or partially in software, the invention can reside, permanently or temporarily, on

0473any memory or storage medium, including but not limited to a RAM, a ROM, a disk,

0474an ASIC, a PROM and the like.

0475While the above embodiments relate to domain name processing, one skilled

0476in the art will realize that domain names are merely one example of directory services, and that the present invention is applicable to other directory services.

047742 Thus are provided methods, systems and devices for scalable domain name resolution. One skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not limitation, and the present invention is limited only by the claims that follow.

047843