Content routing

Details Content routing Content routing

1999-09-03

2003-07-15

Marcelo, Melvin (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S235000, C709S203000, C709S217000, C709S228000

Reexamination Certificate

active

06594260

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to computer system networking and, more particularly, to routing methods and apparatuses for routing network connections based on the data to be transferred during the network connection.
BACKGROUND OF THE INVENTION
Web caches, the Internet equivalent of the caches built into microprocessors today, store copies of documents the caches expect will be requested soon. Web caches are useful for three main reasons. First, they alleviate Internet hot spots by reducing the load seen by busy servers and increasing the availability of popular documents. Second, they bring documents closer to the clients accessing them, thereby reducing the latency component of download time. Third, by reducing the number of times duplicate data is sent over network links, web caches reduce network bandwidth utilization. Cache location often determines which of these benefits is most important to the cache provider or owner. For caches connected to inexpensive high capacity networks, latency is the most critical measure of caching effectiveness. For caches connected to expensive transoceanic connections, reducing bandwidth is most important.
Evidence of the benefits of web caching can be seen in the performance statistics of currently deployed caches. Hit rates of up to 50% (and byte hit rates of up to 35%) have been reported. While this shows a clear benefit in terms of bandwidth savings, this single improvement is not enough. Cable modems and Asynchronous Digital Subscriber Line (ADSL) have created a market for fast, large caches that are also capable of increasingly better throughput and lower latency. Under the very best conditions these modem high-end caches can currently handle 60 megabits per second (Mb/s) and the minimum latency they induce is 20 milliseconds (ms).
An increasingly popular way of improving the performance of a web cache is to leverage the contents of other caches. By servicing each other's misses, a group of cooperating caches can increase the overall cache hit rate observed by their clients. Since reducing latency is also critical, a key challenge for such distributed web caching is the design of an efficient method of forwarding web requests through a number of caches.
A cache mesh is an interconnected group of caches that works together to form a very large disk capacity (multi-terabyte) distributed cache.
FIG. 1
shows an example of a subset of a cache mesh set up by UNINETT (the national research network of Norway). Cache meshes are most commonly deployed in regions separated from the bulk of the Internet by long-haul links, their purpose being to reduce the bandwidth usage across these expensive links. A cache mesh is formed by manually configuring a region of caches into an overlay network. Neighboring caches in this network, or mesh, exchange information about their contents using a specialized protocol, typically ICP (Internet Cache Protocol). This content information is then used to determine where to forward requests for documents that are not present locally. An effort is made to search a number of caches in the mesh before forwarding a request out over the long-haul link. This policy helps cache meshes accomplish their chief goal of reducing long-haul bandwidth. Despite this benefit, however, cache meshes remain hard to manage because of the difficulties of manual configuration.
Another option is to organize caches into transparent hierarchies. Using Web Cache Communication Protocol (WCCP) or a layer 4 switch, a web cache is installed at any network location to transparently intercept and service all web requests passing through that point. On a cache miss, the cache obtains the desired document by sending out a request addressed to the document's home server, causing this request to be picked up by the next upstream cache. So, in effect, each request travels up a hierarchy of caches rooted at the requested document's home server. Since caches do not need to know about each other in order to cooperate, a transparent web mesh can be created without any of the administrative work normally associated with cache meshes.
Although transparent hierarchies eliminate the problem of cache mesh management, they are not the final solution. Like cache meshes, transparent hierarchies suffer from the problem of long latency imposed by chains of TCP (Transmission Control Protocol) connections. Each cache between the client and the request's final destination must establish a TCP session with the requesting client or cache, read the request (URL), and then either service the request or create another TCP session with an upstream device. This results in the data travelling back to the client through a chain of TCP connections. For example,
FIG. 2
shows a client
502
requesting a web document from server
508
. Transparent caches
504
,
506
, and others are located on the network path between the client and the server. If none of these caches has the requested data, the client must establish a connection with cache
504
to request the data, cache
504
must establish a connection with cache
506
to request the data, cache
506
must do the same with the next cache, and so on until the request reaches the server
508
.
Not only do all these individual requests for the data hurt end-to-end reliability by introducing many single points of failure into the connection, but performance of the data transfer suffers because packets are effectively being forwarded through multiple slow transport-layer devices instead of only through faster IP routers. Each TCP endpoint in the chain significantly increases network latency, an increasingly important component of download time. The situation is especially unfortunate for the growing percentage of Web traffic that is not cacheable at all. In this case, users see increased browsing delay with no benefit.
The problem only worsens as caches are more widely deployed, increasing the size of cache meshes
etworks. For example, a typical network path may contain 10-20 hops. If a caching device were to exist at each hop and each device added a minimal 20 ms, the latency induced would be at least 360 ms for an 18 hop path. This is far greater than the time (about 100 ms) it would take to communicate directly with the server.
TCP chaining also exacerbates the already challenging problem of provisioning upstream caches located in or at the edge of the Internet backbone. Because such caches have to be able to keep up with the high speed/bandwidth links on which they sit, they have to be large and fast. This means that they are very expensive and physically large, requiring large amounts of expensive rack space. With TCP chaining in use, these caches would have to be TCP-level forwarders for every Web flow passing through. Not only is this unacceptable because of the latency issues discussed above, but no current caching solution/device could possibly do this fast enough to keep up with the OC3 and greater speeds of modern backbones.
Thus a need remains for a more efficient mechanism for forwarding web requests to different network elements.
SUMMARY OF THE INVENTION
The invention routes data requests based on their content. The client requesting the data sends a heads up packet (HUP) just before sending a setup packet requesting the network connection. The HUP identifies the data the client is requesting. A properly-equipped proxy device decodes the HUP and routes the setup packet according to the requested data. If the proxy device is aware of a network cache with the requested data, the proxy device forwards the setup and heads up packets to that cache. Otherwise, the proxy device forwards the setup and heads up packets in the direction of the server from which the client made the request.
HUPs are introduced without otherwise affecting the functionality of an network. It is important that a proxy device not equipped to decode HUPs not attempt to establish a connection with the client based on receipt of a HUP. The HUP is structured so that an unequipped proxy device will igno

Affiliated with

Also associated with

Rating

Content routing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Content routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content routing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3001473