Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1999-03-31
2002-12-31
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S119000, C711S118000, C709S220000, C709S221000, C709S226000, C709S223000
Reexamination Certificate
active
06502175
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to wide-area networks and, more specifically, to a method and appratus for determining an optimal location for caches in a wide-area network.
BACKGROUND OF INVENTION
Internet usage is expanding at a phenomenal rate. As Internet users become more sophisticated, their demands for information and network performance become greater and they become less tolerable of having to wait more than a few seconds for information to be transferred from a server. For world-wide-web (i.e., “WWW”) traffic, network performance depends on a number of factors. For example, server response time (i.e., the length of time it takes for a server to respond to a user's request) slows as the number of users (the terms user and client are used interchangeably herein) accessing the server increases. The type of information (text-only, video, etc.) requested also effects server response time, text-only data consuming less bandwidth and generally being transmitted more quickly than video data, for example. In addition, physical network limitations such as the user's modem speed, communication route between the user and server (i.e., how many hops the request from the user and information from the server must navigate), the location and number of routers and caches (i.e., network configuration), the speed of the line or link, and other physical factors, may effect server response time.
The case of optimizing performance for clients of a particular web-server is of particular interest both from the theoretical and practical points of view. Consider a popular server that gets many requests and responds with large quantities of data (like big software and news distribution servers). As the number of requests to the server and the data it provides increase, the performance of the server declines sharply. One way to address this problem is to replicate the server. However, explicit replication creates problems with managing the different copies of data maintained on the different servers and redirecting the client to different locations instead of being routed directly to the “original” server. Consequently, hardware and network management costs increase with this solution.
Another solution is to place more caches in the network. Caching improves network and system performance for world-wide-web (WWW) browsing by saving network bandwidth, reducing client access time, and alleviating server load. The way caches are currently deployed requires clients or caches to be cognizant of proximately located caches. This complicates network and system management and configuration.
Automatic caching is an attractive proposition. The question of where to locate caches in the network is an important one and one which may have a big impact on the overall improvement in network performance. If caches are located very close to the server, the server load may decrease but network congestion will remain a problem. Locating caches too close to the clients would require a large number of caches that would each be under-utilized.
Caches have historically been located at the network edges in the form of browser and proxy caches, at the ends of high latency links, or as part of cache hierarchies. Recently, it has been suggested that caches be placed inside the network, i.e., inside the network backbone, as opposed to at the network edges. Such cache placement has been shown to reduce network FTP (file transfer protocol) traffic. While offering some improvement in network performance, merely locating caches inside the network does not provide an optimal solution to network performance concerns. Moreover, the “in-network” approach, in and of itself, does not provide a method for optimizing network performance or gain (i.e., minimizing overall network traffic and/or reducing server response time or delay). Clearly, how well caching inside the network will work depends on where the caches are located, and how data is disseminated to them.
SUMMARY OF THE INVENTION
In view of the above-described shortcomings of the prior art, it is thus desirable to provide a method of determining locations for caches within a network that optimizes a predetermined network cost parameter.
In a first embodiment of the present invention, a so-called l-greedy algorithm is used to determine locations for k caches in a network having virtually any configuration. In a second embodiment of the present invention, a dynamic-programming algorithm determines optimal locations for k caches in a network for the traffic related to a single server. In accordance with the present invention, caches are preferably co-located with network routers and may be maintained by network providers. Thus, little or no change is required to the network infrastructure, except for the introduction of caches at the appropriate locations within the network. The present invention is particularly, although not exclusively, well-suited for a single web-server connected to a network, where the route from the server to the client forms a tree (with the server at the root of the tree).
In a first embodiment, the present invention provides a method of determining locations for k caches in a network. A network configuration is defined by a plurality of network connections, a plurality of nodes, and a plurality of servers and clients and network performance is determined by the interrelation therebetween and there among. The locations determined for k caches optimizes performance of a network cost parameter which is dependent upon the network configuration. The method comprises the steps of: selecting a placement parameter l that is greater than 0; assigning l caches to l arbitrary nodes in the network; selecting l caches from the network; assigning l+1 caches to every possible location in the network; computing and recording network performance data on the network cost parameter for each location and for each selection of l caches; determining a location where the network performance data on the network cost parameter is optimized; assigning l+1 caches to the previously determined location where the cost parameter is optimized; and repeating the previous steps for k−l iterations.
In a second embodiment of the present invention, a dynamic programming algorithm is used to determine the optimal location of a cache in a network having a single server. In this embodiment, the present invention uses a dynamic programming algorithm to compute the optimal cost C(i, {tilde over (k)}, s) to determine an optimal location for caches in a network having a single server, where i is a node, {tilde over (k)} is the number of optimally placed caches, and s is the distance between node i and the next cache in the network.
Other objects and features of the present invention will become apparent from the following detailed description, considered in conjunction with the accompanying drawing figures. It is to be understood, however, that the drawings, which are not to scale, are designed solely for the purpose of illustration and not as a definition of the limits of the invention, for which reference should be made to the appended claims.
REFERENCES:
patent: 5511208 (1996-04-01), Boyles et al.
patent: 5852717 (1998-12-01), Bhide et al.
patent: 5864852 (1999-01-01), Luotonen
patent: 5878218 (1999-03-01), Maddalozzo, Jr. et al.
patent: 5999734 (1999-12-01), Willis et al.
patent: 6038601 (2000-03-01), Lambert et al.
patent: 6058423 (2000-05-01), Factor
patent: 6189043 (2001-02-01), Buyukkoc et al.
Gwertzman, “The Case for Geographical Push-Caching,” Proceedings, Fifth Workshop on Hot Topics in Operating Systems, May 4-5, 1995, pp. 51-55.
Krishnan P.
Raz Danny
Shavitt Yuval
Gossage Glenn
Lucent Technologies - Inc.
LandOfFree
Method and apparatus for locating caches in a network to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for locating caches in a network to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for locating caches in a network to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980755