US 2003/0182269 A1Application
Method and apparatus for supporting duplicate suppression when issuing multicast queries using DNS-format message packets
Publication Date:2003-09-25
•21 Claims
•3 Drawing Sheets
Abstract
Domain Name System (DNS) Queries and DNS Responses both use the same packet format. The DNS packet format, defined by Internet Engineering Task Force (IETF) Protocol Standard 13 (RFC 1035) includes a header section, a question section, an answer section, an authority record section and an additional record section. In conventional DNS Queries, the header section and the question section are used; the answer section, authority record section and additional record section are empty. In the present invention, when issuing a query, the client places the question in the question section as usual, but then places all the answers it already knows into the (previously empty) answer section of the query. When receiving a query, a responder first checks to make sure that the answer it is about to give is not already included in the answer section of the query. If the answer is listed in the answer section of the query, it means that the client already has that information, and doesn't need to be told again. In this way, when a client issues its first multicast query, it may receive many responses. When the client issues a subsequent query, it indicates the list of responses it successfully received by listing them in the answer section, and then only receives responses that were missed the first time. In the normal course of operation, this means that by the second or third transmission of the query, no further responses are generated on the network, and the client can then issue occasional periodic queries without eliciting a flood of responses every time.
Metadata
Inventor
- Stuart Cheshire
Application Information
Application Number:US 10/102,174
Filing Date:2002-03-19
Priority Date:2002-03-19
Patent Drawings (3 sheets)
Description
Background
[0001] 1. Field of the Invention
[0002] The present invention relates to computer networks. More specifically, the present invention relates to a method and an apparatus that supports suppression of multiple identical replies when issuing repeated multicast queries using DNS-25 format message packets.
[0003] 2. Related Art
[0004] When a client is seeking information, and the source of the information is not known in advance, one common technique is to issue the query for that information using Internet Protocol (IP) Multicast, Ethernet Multicast, or some other technique that delivers the query to a set of machines that might potentially be able to provide that information. In some cases, more than one machine may have information to give in response to the query, resulting in multiple responses on the network. Furthermore, because packet-switching network technologies may occasionally lose or corrupt packets, it is customary for clients issuing such queries to transmit those query packets more than once, and combine the results, to reduce the risk that any particular query or response may be lost. When each multicast query can result in a large number of responses on the network, this can be inefficient.
[0005] What is needed is a method and an apparatus that allows a client to issue repeated multicast queries for the sake of reliability, without the inefficiency of receiving redundant identical replies every time.
Summary
[0006] Domain Name System (DNS) Queries and DNS Responses both use the same packet format. The DNS packet format, defined by Internet Engineering Task Force (IETF) Protocol Standard 13 (RFC 1035) includes a header section, a question section, an answer section, an authority record section and an additional record section. In conventional DNS Queries, the header section and the question section are used; the answer section, authority record section and additional record section are empty.
[0007] In the present invention, when issuing a query, the client places the question in the question section as usual, but then places all the answers it already knows into the (previously empty) answer section of the query. When receiving a query, a responder first checks to make sure that the answer it is about to give is not already included in the answer section of the query. If the answer is listed in the answer section of the query, it means that the client already has that information, and doesn't need to be told again. In this way, when a client issues its first multicast query, it may receive many responses. When the client issues a subsequent query, it indicates the list of responses it successfully received by listing them in the answer section, and then only receives responses that were missed the first time. In the normal course of operation, this means that by the second or third transmission of the query, no further responses are generated on the network, and the client can then issue occasional periodic queries without eliciting a flood of responses every time.
[0008] Hence, one embodiment of the present invention provides that for obtaining any information that may be represented using DNS Resource Records. The system operates by delivering a query asking for information identified by a DNS name, a query type and a query class to multiple entities. This query is contained within a packet that adheres to a format defined in Internet Engineering Task Force (IETF) RFC 1035. Moreover, the query includes an answer section containing a list of known answers to the query. In response to the query, the system receives zero or more responses to the query containing additional answers that are not in the list of known answers. This allows the system to add the additional answers to the list of known answers. Note that sending the list of known answers along with the query facilitates suppressing responses that include known answers.
[0009] In a variation on this embodiment, delivering the query involves performing a domain name system (DNS) multicast to deliver the query to the multiple entities.
Brief Description of the Figures
[0010] FIG. 1 illustrates a requesting entity coupled to a number of responding entities through a network in accordance with an embodiment of the present invention.
[0011] FIG. 2 illustrates a packet structure in accordance with an embodiment of the present invention.
[0012] FIG. 3 illustrates a resource record structure in accordance with an embodiment of the present invention.
[0013] FIG. 4 is a flow chart illustrating lookup of the set of (zero or more) address records that match a given name, in accordance with an embodiment of the present invention.
Detailed Description
[0014] The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.
[0015] The data structures and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as the Internet.
[0016] Clients and Servers
[0017] FIG. 1 illustrates a requesting entity 102 coupled to a number of service responding entities 104, 106 and 108 through a network 110 in accordance with an embodiment of the present invention.
[0018] Network 110 can generally include any type of wire or wireless communication channel capable of coupling together computing nodes. This includes, but is not limited to, a local area network, a wide area network, or a combination of networks. In one embodiment of the present invention, network 110 includes the Internet.
[0019] Requesting entity 102 and responding entities 104, 106 and 108 reside on computing devices attached to network 110. These computing devices can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance.
[0020] In the embodiment of the present invention illustrated in FIG. 1 , requesting entity 102 is a personal computer system and responding entities 104, 106 and 108 are printers. However, note that responding entities, 106 and 108 can generally include any type of entity that can provide an answer to a query.
[0021] During operation, requesting entity 102 sends a query over network 110 to obtain information. This process is described in more detail below with reference to FIGS. 2-4.
[0022] Packet Structure
[0023] FIG. 2 illustrates a packet structure for a standard protocol, such as DNS, in accordance with an embodiment of the present invention. As is illustrated in FIG. 2 , packet 200 includes a number sections, including a header section 202, a question section 203, an answer section 204, an authority section 205 an additional section 206.
[0024] The header section 202 is always present. Header section 202 includes fields that specify which of the remaining sections are present, and whether the packet contains a query or a response. Header section 202 also contains an identifier for a query. Note that this identifier is included in any responses to the query.
[0025] Question section 203 carries the query name and other query parameters. Answer section 204 carries resource records which directly answer the query. Authority section 205 carries resource records that describe other authoritative servers. Finally, additional section 206 carries additional resource records, which may facilitate using resource records in other sections.
[0026] Note that in the DNS protocol, a packet that contains a question does not contain answer records. The present invention makes an unconventional use of answer records by including them in a question packet to identify known answers to the query. This unconventional use of answer records reduces network traffic because known responses containing known answers are not sent over network 110. Only answers that are not contained in the question record will trigger responses.
[0027] Resource Record Structure
[0028] FIG. 3 illustrates a resource record structure for a protocol, such as DNS, in accordance with an embodiment of the present invention. In FIG. 3 , resource record 300 includes a name field 301, a type field 302, a class field 303, a time-to-live (TTL) field 304, and resource data length field 305 and associated resource data 306. Name field 301 is an extensible field that contains a name. Type field 302 identifies a resource type. Class field 303 identifies a name space. Time-to-live (TTL) field 304 indicates how long the resource record is valid. Resource data length field 305 indicates the length of the following resource data 306. Resource data 306 is a variable length string that describes the resource. The format of this information varies according to the type and class of the resource information.
Example: Duplicate Suppression During Address Record Lookup
[0029] In one example, the present invention supports duplicate suppression during address record lookup. FIG. 4 is a flow chart illustrating this process.
[0030] During operation, requesting entity 102 transmits a multicast query across network 110 asking for address record(s) associated with the name time.apple.com. (step 402). This query includes an answer section containing a list of known address records that match that name.
[0031] Next, a responding entity 104 receives the query (step 404) and examines the answer section (step 406). If responding entity 104 contains a locally known answer that is not included in the list of known answers in the answer section, responding entity 104 sends a response to requesting entity 102 containing an address record for the locally known address (step 408).
[0032] Next, requesting entity 102 receives responses to the query (step 410) and uses the responses to update its list of known address (step 412).
[0033] Requesting entity 102 can then select a specific address from the list of known address to initiate network communication with that host (step 414).
[0034] The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.
Claims
1. A method for obtaining information that may be represented using DNS resource records, comprising:
delivering a query asking for information identified by a DNS name, a query type and a query class to multiple entities;
wherein the query is contained within a packet that adheres to a format defined in Internet Engineering Task Force (IETF) RFC 1035;
wherein the query includes an answer section containing a list of known answers to the query;
receiving zero or more responses to the query containing additional answers that are not in the list of known answers; and
adding the additional answers to the list of known answers;
wherein sending the list of known answers along with the query suppresses responses that include known answers.
2. The method of claim 1, wherein delivering the query involves performing a domain name system (DNS) multicast to deliver the query to the multiple entities.
3. The method of claim 1, wherein the domain comprises a computer network.
4. The method of claim 1, wherein the domain comprises a wireless computer network.
5. A method for communicating information that may be represented using DNS resource records, comprising:
receiving a query sent to multiple entities asking for information identified by a DNS name, a query type and a query class;
wherein the query is contained within a packet that adheres to a format defined in Internet Engineering Task Force (IETF) RFC 1035;
wherein the query includes an answer section containing a list of known answers to the query; and
sending a response to the query if a locally known answer to the query does not appear in the list of known answers, so that the sender of the query can update the list of known answers to include the locally known answer;
whereby responses including known answers are suppressed.
6. The method of claim 5, wherein the domain comprises a computer network.
7. The method of claim 5, wherein the domain comprises a wireless computer network.
8. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for obtaining information that may be represented using DNS resource records, the method comprising:
delivering a query asking for information identified by a DNS name, a query type and a query class to multiple entities;
wherein the query is contained within a packet that adheres to a format defined in Internet Engineering Task Force (IETF) RFC 1035;
wherein the query includes an answer section containing a list of known answers to the query;
receiving zero or more responses to the query containing additional answers that are not in the list of known answers; and
adding the additional answers to the list of known answers;
wherein sending the list of known answers along with the query suppresses responses that include known answers.
9. The computer-readable storage medium of claim 8, wherein delivering the query involves performing a domain name system (DNS) multicast to deliver the query to the multiple entities.
10. The computer-readable storage medium of claim 8, wherein the domain comprises a computer network.
11. The computer-readable storage medium of claim 8, wherein the domain comprises a wireless computer network.
12. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for communicating information that may be represented using DNS resource records, the method comprising:
receiving a query sent to multiple entities asking for information identified by a DNS name, a query type and a query class;
wherein the query is contained within a packet that adheres to a format defined in Internet Engineering Task Force (IETF) RFC 1035;
wherein the query includes an answer section containing a list of known answers to the query; and
sending a response to the query if a locally known answer to the query does not appear in the list of known answers, so that the sender of the query can update the list of known answers to include the locally known answer; whereby responses including known answers are suppressed.
13. The computer-readable storage medium of claim 12, wherein the domain comprises a computer network.
14. The computer-readable storage medium of claim 12, wherein the domain comprises a wireless computer network.
15. An apparatus that obtains information that may be represented using DNS resource records, comprising:
a delivery mechanism that is configured to deliver a query asking for information identified by a DNS name, a query type and a query class to multiple entities;
wherein the query is contained within a packet that adheres to a format defined in Internet Engineering Task Force (IETF) RFC 1035;
wherein the query includes an answer section containing a list of known answers to the query;
a receiving mechanism that is configured to receive zero or more responses to the query containing additional answers that are not in the list of known answers; and
an updating mechanism that is configured add the additional answers to the list of known answers;
wherein sending the list of known answers along with the query suppresses responses that include known answers.
16. The apparatus of claim 15, wherein the delivery mechanism is configured to perform a domain name system (DNS) multicast to deliver the query to the multiple entities.
17. The apparatus of claim 15, wherein the domain comprises a computer network.
18. The apparatus of claim 15, wherein the domain comprises a wireless computer network.
19. An apparatus that communicates information that may be represented using DNS resource records, comprising:
a receiving mechanism that is configured to receive a query sent to multiple entities asking for information identified by a DNS name, a query type and a query class;
wherein the query is contained within a packet that adheres to a format defined in Internet Engineering Task Force (IETF) RFC 1035;
wherein the query includes an answer section containing a list of known answers to the query; and
a response mechanism that is configured to send a response to the query if a locally known answer to the query does not appear in the list of known answers, so that the sender of the query can update the list of known answers to include the locally known answer;
whereby responses including known answers are suppressed.
20. The apparatus of claim 19, wherein the domain comprises a computer network.
21. The apparatus of claim 19, wherein the domain comprises a wireless computer network.