Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-03-26
2001-07-17
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000
Reexamination Certificate
active
06262987
ABSTRACT:
FIELD OF THE INVENTION
This invention generally relates to translating-address bindings of Internet hosts, and more particularly to reducing latencies while translating the bindings.
BACKGROUND OF THE INVENTION
The Internet is a wide area network that connects computer systems (hosts) all over the world. Most of the hosts can be classified as server computers or client computers. The clients are mostly operated by end-users, while the servers provide various types of network services to the clients. In some cases, specialized work is performed by hosts called “proxy” servers. For example, gateways that connect intranets to the Internet typically include proxy servers that implement routers, fire-walls, tunnels, and the like. Many other types of proxy servers are known.
On the Internet, communications between Internet hosts requires the use of Internet Protocol (IP) addresses. Each communicated “packet,” whether a request or reply, includes a source address of the sending host and a destination address of the receiving host. In the current IP version 4, these addresses are 32 bits arranged as multiple fields. The addresses are often written in a numeric form like “10.80.16.4”. However, IP addresses in pure numeric form are hard for users to remember. Therefore, most user-visible forms of the addresses are represented as “names,” for example, “www.digital.com.” The association between a name and an address is known as a binding.
In order to translate between names and IP addresses, the Internet uses a Domain Name System (DNS). The DNS is a large, spatially distributed system with frequent updates while bindings are added, modified, or deleted. One step in almost all practical Internet operations is for a host to ask the DNS for a translation from a DNS name to an IP address. In some cases, the DNS is asked to translate from a known IP address to a corresponding DNS name.
Because DNS requests are frequent and may traverse long distances, the DNS includes a caching mechanisms. The cache will decrease the load on the Internet due to translation requests, and also make name look-ups quicker because the translations can be performed locally. To prevent the use of stale (out-of-date) cache entries, the DNS associates a “Time To Live” (TTL) value with each name-to-address binding. The TTL indicates the length of time that a particular binding is cached. After the TTL expires, the associated binding can be evicted from the cache.
While DNS caching does serve to eliminate a lot of the potentially necessary DNS requests, especially the transmission of many requests and responses over slow and costly wide area networks, there are still many circumstances when the latency of DNS look-ups is a significant performance problem due to cache misses. If there is a cache miss, the DNS has to go out on the network to load the cache with the required binding. A DNS cache incurs cache misses for the following reasons.
Traditional DNS caching can only result in a cache hit when a name translation is requested more than once. On the first request, the cache will not contain a cache entry. This is known as a “compulsory miss.” This is inherent in the way DNS caches operate. Because excessively long TTLs make it difficult for a system administrator to change name-to-address bindings for hosts, most TTLs are typically set to durations of between a few hours and a few days. This means that an infrequently requested name translation may result in a DNS cache miss because the TTL has expired, and the binding has been evicted. This is known as a “time-out miss,” and requires a time-consuming reload. In addition, the DNS cache may not be large enough to hold all of the possible name-to-address bindings. This may result in a “capacity miss.”
Of these three kinds of misses, capacity misses can be avoided by simply increasing the cache size. According to the latest survey available at “http://www.nw.com/zone/WWW/report.html,” the total number of DNS names reachable on the Internet is about 20 million, although this might be a significant underestimate. Even so, it would be relatively easy to cache one hundred million DNS translations on a single disk.
However, it is not nearly so easy to avoid compulsory or time-out misses. In order to avoid most compulsory misses, the DNS cache would have to be aware of most of the possible DNS names all of the time. In order to avoid time-out misses, the DNS cache would also have to probe the true DNS servers for each of the cached names at an interval commensurate with its TTL value. Should each DNS cache engage in this practice this would place an enormous load on the Internet and on the DNS servers.
In practice, the problem of DNS cache misses is most important at a site with a large fan-in or fan-out. For example, an HTTP “proxy” server must translate the DNS name to an IP address before each HTTP request can be forwarded. This adds latency to the forwarding path, increases the number of simultaneous operations in progress, and the number of operating system scheduling events per request. A large proxy deals with many servers, and so DNS caching tends to break down in this case.
In addition, a busy HTTP server may wish to keep an audit log based on host names. Therefore, the logging server has to do a reverse lookup, i.e., an address to name translation for each request. Experience has shown that this is prohibitively expensive when the host community is large because DNS caching is ineffective in this case. Therefore, most current HTTP servers keep their logs by IP address. The 32 bit addresses of the clients can be then post-processed into readable host name form, but this is still expensive, and the binding between host name and IP address sometimes changes before the post-processing can be performed, making the log inaccurate.
Another application where DNS cache misses might be important is in a large electronic mail (e-mail) server. Each e-mail message is addressed to one or more host names, and these host names must be translated to IP addresses before the server can deliver the mail. Also, many servers do reverse look-ups on arriving mail, so as to create an audit trail based on the host name of the server that sent the mail, i.e., the address in the “Received:” lines of an Internet e-mail header.
The HTTP proxy problem is the more severe because the translation is unavoidable and on the critical path for latency. Therefore, the invention disclosed below is primarily discussed with respect to HTTP proxies and servers, but the applicability of the invention to other Internet services, such as e-mail and FTP, etc. is quite similar.
In the prior art, most system operators have tried to resolve these problems by balancing the TTL value so that time-out misses are minimized without introducing excessive incoherency. Increasing the size of DNS caches can reduce capacity misses. However, no good solutions are known to the problem of compulsory misses at large sites.
Therefore, there is a need to reduce latencies associated with translating name-address bindings of Internet hosts, especially translations that suffer compulsory cache misses.
SUMMARY OF THE INVENTION
The invention provides a system and method for translating names and addresses of host computers connected by a network. A collecting site, either local or distributed, collects the names of a substantial number of all of the host computers. The collecting can be done by a “spider” or “crawler” (i.e., a system that locates as many Web pages as possible) of a search engine probing the network.
Name-address translations are obtained for each of the collected names. The names can be obtained using a standard Domain Name System (DNS).
The name-address bindings can be compressed, and optionally encrypted before they are transferred to one or more recipient computers (e.g., proxy servers). It may be preferable to use multicast transmission when there are multiple recipients. The recipient computers store the name-address bindings for all of the hosts in a cache memory.
Subsequently, the recipient computer receives tran
Olms Douglas
Oppenheimer Wolff and Donnelly LLP
Pizarro Ricardo M.
Sherry Leah
LandOfFree
System and method for reducing latencies while translating... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for reducing latencies while translating..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for reducing latencies while translating... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2567990