Systems and methods of providing DNS services using separate answer and referral caches

• US 20040267907A1
• Filed: 06/26/2003
• Published: 12/30/2004
• Est. Priority Date: 06/26/2003
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Nominum Incorporated (Akamai Technologies, Inc.)
• Inventors: Gustafsson, Andreas
• Granted Patent: US 7,769,826 B2
• Time in Patent Office: Days
• US Class Current: 709/219
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/58 Caching of addresses or names
• CPC Class Codes: H04L 67/2885 Hierarchically arranged intermediate devices, e.g. for hierarchical caching
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Systems and methods of determining DNS information, such as an IP address, associated with a domain name. The methods using a cache segregated to store various domain name system (DNS) data in different data structures. The data structures are configured for minimization of data retrieval times. In some embodiments, answer information is stored in a hash table. In these and other embodiments, times required to search for answers are essentially constant as a function of the number of labels comprising the domain name.

Claims

1. A caching server comprising:

an answer cache configured to access answer information through a flat data structure;

a referral cache configured to store referral information; and

computer instructions configured to translate a domain name into DNS information by examining the answer cache and, responsive to the results of examining the answer cache, examining the referral cache.

2. The caching server of claim 1, wherein the flat data structure is a hash table.

3. The caching server of claim 1, wherein the flat data structure includes pointers to a tree data structure.

4. The caching server of claim 1, wherein the flat data structure includes pointers to a tree data structure, and the tree data structure is configured to store answer information and referral information.

5. The caching server of claim 1, wherein the flat data structure includes pointers to a tree data structure, and the tree data structure is included in the referral cache.

6. The caching server of claim 1, wherein the caching server is also an authoritative server.

7. The caching server of claim 1, wherein the caching server is also a web server.

8. The caching server of claim 1, wherein the referral cache is further configured to store the referral information in a hierarchical data structure.

9. The caching server of claim 1, wherein the DNS information includes an IP address.

10. The caching server of claim 1, wherein the DNS information includes an Mx record.

11. A computer readable medium having stored thereupon computer code configured to determine DNS information associated with a domain name, the computer code comprising:

a code segment configured to receive a request for the DNS information corresponding to a domain name;

a code segment configured to examine a first cache to find the DNS information, the first cache including a flat data structure and configured to store the DNS information or a pointer to the DNS information; and

a code segment configured to initiate a search of a second cache if the DNS information is not found by examining the first cache, the second cache configured to store data referring to further locations on a computer network wherein the DNS information may be found.

12. The computer readable medium of claim 11, wherein the DNS information includes an IP address.

13. A computer network comprising:

means for receiving a request for DNS information corresponding to a domain name;

means for examining a first cache to find the DNS information, the first cache configured to store the DNS information or a pointer to the DNS information; and

means for searching a second cache if the DNS information is not found by examining the first cache, the second cache configured to store data referring to further locations on the computer network wherein the DNS information may be found.

14. The computer network of claim 13, further including means for storing data in the first cache such that a time required to examine the first cache is essentially constant as a function of a number of labels comprising the domain name.

15. The computer network of claim 13, further including means for storing data in the first cache such that a time required to examine the first cache is essentially constant as a function of a size of the first cache.

16. The computer network of claim 14, wherein the DNS information includes an IP address.

17. A computer network comprising:

a computing system configured to access a component of the computer network using a domain name;

a caching server including a first data structure configured for translating the domain name into DNS information, and means for examining the first data structure in a time that is essentially constant as a function of a number of labels comprising the domain name; and

a second data structure configured for translating the domain name into DNS information.

18. The computer network of claim 17, wherein the DNS information includes an IP address or an MX record.

19. A method of determining DNS information, the method comprising:

receiving a request for DNS information corresponding to a domain name;

examining an answer cache for answer information, the answer cache including a hash table configured to store the answer information or to store a pointer to the answer information; and

searching a tree data structure if the DNS information is not found by examining the answer cache.

20. The method of claim 19, wherein the hash table is configured to store the pointer to the answer information.

21. The method of claim 19, wherein the answer cache does not include a tree data structure.

22. The method of claim 19, wherein the tree data structure is configured to store referral data and is included in a referral cache.

23. The method of claim 19, wherein the tree data structure is configured to store pointers to referral data.

24. The method of claim 19, wherein the DNS information includes an IP address.

25. The method of claim 19, wherein the hash table is configured to store the answer information.

26. A method of determining DNS information, the method comprising:

receiving a request for DNS information corresponding to a domain name;

examining an answer cache to find answer information, responsive to the received request, the answer cache including a flat data structure; and

responsive to the examination of the answer cache, searching a referral cache.

27. The method of claim 26 wherein the flat data structure is configured to store the answer information.

28. The method of claim 26, wherein the flat data structure is configured to store a pointer to the answer information.

29. The method of claim 26, wherein the flat data structure is a hash table.

30. The method of claim 26, wherein a time required to examine the answer cache is essentially constant as a function of a number of labels comprising the domain name and essentially constant as a function of a size of the answer cache.

31. The method of claim 26, wherein the referral cache includes a hierarchical data structure.

32. The method of claim 26, wherein the DNS information includes an IP address.

33. A method of storing data in a cache, the method comprising:

requesting DNS information;

receiving data in response to the request;

classifying the response received; and

storing the data received in either a referral cache or an answer cache based on the classification.

34. The method of claim 33, wherein the answer cache includes a flat data structure.

35. The method of claim 33, wherein the answer cache includes a hash table.

36. The method of claim 33, wherein the response received is stored in a caching server.

37. The method of claim 33, wherein the DNS information includes a numerical address.

38. The method of claim 33, wherein the answer cache is configured to store answer information and the referral cache is configured to store referral information.

39. The method of claim 33, wherein the answer cache is configured to store answer information and the referral cache is configured to store referral information, and the answer cache and the referral cache have different data structures.

40. A method of caching DNS information, the method comprising:

requesting DNS information;

receiving data in response to requesting DNS information;

classifying the response received as an answer response or a referral response;

storing the response received in either a referral cache or an answer cache based on the classification, the answer cache including a flat data structure;

receiving a request for DNS information corresponding to a domain name;

examining the answer cache to find answer information, responsive to the received request; and

responsive to the examination of the answer cache, searching the referral cache.

41. The method of claim 40, wherein the referral cache includes a hierarchical data structure.

42. The method of claim 40, wherein the received request for DNS information includes a request for an IP address.