Electrical computers and digital processing systems: multicomput – Distributed data processing – Client/server
Reexamination Certificate
1998-06-05
2002-05-07
Rinehart, Mark H. (Department: 2152)
Electrical computers and digital processing systems: multicomput
Distributed data processing
Client/server
C709S219000
Reexamination Certificate
active
06385641
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is in the area of computer software and more particularly involves software to minimize user waiting for information transmitted over computer networks by anticipating user requests.
2. Description of Problem and Related Art
Due to the rapid growth of the World Wide Web (WWW), there has been a large increase in the amount of information transmitted over the Internet. However, the growth of Internet capacity is not keeping pace so that users often experience long delays in retrieving files from remote machines when running network related applications. Among these network applications, the most popular ones are web browsing and accessing email and news groups. Sometimes, the waiting does not end even when the files have been transferred to the local computer. For example, after an access, the client machine may need to decompress the received files, compile Java programs, etc. On the other hand, during the time interval between two network accesses users will be viewing the information just downloaded and the local computer is generally idle. The key idea of prefetching is to take advantage of these idle periods to fetch the files that will very likely be requested in the near future, so that the user's average waiting time can be reduced. More specifically, if we add some intelligence to the network applications so that whenever the user requests a block of information (a file, an email message, etc.), the system can estimate what additional information (files, messages, etc.)
1
will be needed in the next few user accesses and transmit some of them to the local computer beforehand, according to certain criteria. If the prefetched information is indeed requested, the user can access it with negligible delay. In addition, prefetch allows more time for sophisticated processing including encryption, compression, and compilation to be carried out at both server and client sites, so that data can be transmitted more efficiently and securely without increasing the delay to the user.
1
For simplicity, in the rest of this specification, we use the term “file” to represent a block of information whether it is a file, directory listing, web page, or other information requested by the user.
The idea of prefetching stems from the fact that, after retrieving a page from the remote server, a user usually spends some time viewing the page, and during this period the local computer as well as network link is generally idle. If we can take advantage of this phenomenon by fetching some files that will likely be accessed soon using the otherwise idle system, in other words, prefetching them to the local computer, then there will be no transmission delay when the user actually requests these files. In addition, prefetched files can immediately be processed if decryption or decompression is needed, or if any Java applets need to be handled. This allows further reduction in the delay of loading a page. These are some of the benefits of prefetching. However, the problem is, since the prediction can not be perfect, some of the prefetched files are never used and prefetching increases the system load. At some point, this increase in load may increase the delay of normal (nonprefetching) requests significantly and may eventually cause the overall system performance to degrade. Therefore, the key challenge in prefetching is to determine what to prefetch so that improvement in performance will occur.
If we knew exactly which files a user needed next, we would retrieve only those files in advance. Assuming that the prefetch operation always finishes before the user requests the next file, then we would enjoy zero latency with no extra bandwidth consumption. Unfortunately, in reality, some prefetched information may never be used resulting in wasted bandwidth and increased delay to normal (nonprefetch) requests. This indicates that the prefetch problem has two aspects. The first one is how to estimate the probability of each file being accessed in the near future. In general, this probability changes with time as the user issues new requests. The second aspect is how to determine which files to prefetch so that the overall system performance can be optimized relative to some criteria. Previous studies on Internet prefetch focus only on the first aspect of the problem and either use a fixed threshold or prefetch a fixed number of the most popular links on a page [2, 7, 8] In the prior art PeakJet prefetching software for web browsers all available links on a page being viewed are prefetched [9]. If everyone were to employ this method, there would be unacceptable surges in network traffic. In fact, prefetching without caution could be disastrous to the network.
BRIEF SUMMARY OF THE INVENTION
The prefetch scheme of the present invention consists of two modules: a prediction module and a threshold module. A simplified flow diagram is shown in FIG.
14
. The complete scheme works as follows. After a user's request for a new file is satisfied, the prediction module immediately updates a database of history information if needed, and computes the access probability for each candidate file, where the access probability of a file is an estimate of the probability with which that file will be requested by the user in the near future. Different applications may use different prediction algorithms in this module. Next the threshold module determines the prefetch threshold for each related server, which contains at least one candidate file with nonzero access probability. The threshold is determined in real time based on then current network conditions. The algorithm used in the threshold module is independent of the application. Finally, each file whose access probability exceeds or equals its server's prefetch threshold is prefetched. When prefetching a file, the file is actually downloaded if and only if no up-to-date version of the file is available on the local computer; otherwise no action is taken. Although web browsing is an important application for prefetching, the prefetch scheme of the present invention may be advantageously applied to any network application in which prefetching is possible. In general, for different applications, different prediction algorithms may be developed, while the same threshold algorithm can be employed throughout, with the same prefetching criteria always achieving the optimum performance.
To achieve high efficiency with prefetching, in the prediction module, one uses an algorithm to predict the access probability of each file as accurately as possible. In the threshold module, the prefetch threshold for each related server is computed. We have derived an upper bound for the prefetch threshold that is a function of system load, capacity, and cost of a time unit and a system resource unit to the user. Files with access probability greater than its server's prefetch threshold are prefetched. By doing so, a lower average cost can always be achieved. We tested the performance of our prediction algorithm for web browsing by setting the prefetch threshold at various values. The results show that generally, using the access probabilities from the client can ensure that a large portion of prefetched files are used, while the access probabilities from the server can help improve the number of user requests satisfied by the prefetched files.
Prefetch is a good approach to reduce latency for network applications. However, it must be implemented in a way such that the overall system performance can be improved, and the tradeoff between saving user's time and the bandwidth usage must be considered. Applications of this approach go beyond mere prefetching. In the case of a push server or push caching it is important to study overall efficiency. This means not only the percentage of the pushed files being used, but also, and more importantly, the impact of pushing on other users who are sharing the same network but may or may not be able to use these pushed files at all.
Jiang Zhimei
Kleinrock Leonard
Dawes Daniel L.
Myers Dawes & Andras LLP
Rinehart Mark H.
The Regents of the University of California
Thompson Marc D.
LandOfFree
Adaptive prefetching for computer network and web browsing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive prefetching for computer network and web browsing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive prefetching for computer network and web browsing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2875939