The general research of this work is to make proxy caching more efficient in the GroupWare environment where the web pages being fetched by some group members, or potentially to being fetched by some group members may be interest for other group members. The specific problem that our research focuses at is how to do efficient prefetching and caching in conditions when each already fetched web presentation includes pointers to potential follow-up presentation. Existing approaches base their prefetching and caching on the information how frequently some presentation is used, volume of presentation and time to being fetched, who is who in GroupWare hierarchy, what are the keywords involved in currently opened document or hints from the system administrators. Our approach utilizes temporal locality; under the term temporal local web presentations we imply those which are found in the list of the replaced from the cache, characterized with the relative impact factor (i.e. how often were they read when they were in the cache). We demonstrate that our approach is better then existing ones with doing following:

1. analytical analysis to show upper bound in our approach compared with existing approaches;
2. simulation analysis to estimate expected performances;
3. Implementation of proxy sublayer, which includes the proposed solution as well as the existing solutions in a way which enables testing in the real environment.

Growth of popularity of World Wide Web resulted in frequent redundant accesses to popular Internet resources. Caching reduces accesses moving the most popular objects closer to the user. The main goal of the caching is to do following:

1. minimize the number of bytes that travel over the Internet conserving Internet bandwidth;
2. minimize the number of hits to popular Web servers;
3. minimize the time that end users wait for an object to load.

Since caching storage space is limited, some objects are removed. Removing policy selects what will be kept in cache, and what will be removed, optimizing one or more previously mentioned goals. It is important to chose right removing policy to achieve maximum cache performance. Optimization of one goal may impact others. Prefetching minimizes the time that end users wait for an object to load.

There are few parameters which are of interest in caching: volume of an object, time that it takes to fetch an object (to the proxy server and from the server to the end user), and probability of repeating access to the same object. Volume of an object is known before fetching. Times can be estimated knowing average transfer rate over connections from proxy to server and from end user to proxy. Estimation of probability of the repeating access to the same object requires to be acquainted with nature of requests. There is no exact way to do requested. On the other hand it is very important to estimate probability which will be closer to the real situation to make all calculations worth. The field of this research is estimation of probability, which will lead to achieving better performance of caching and prefetching.

Removal polices, such as the first in, first out (FIFO), least recently used (LRU), least frequently used (LFU), removal policy proposed by Pitkow/Recker[PR94] base their predictions of future accesses to objects using frequency and/or recency rates of prior object accesses. As proposed in [WAS96] removing policy can be viewed as a sorting problem and objects are sorted and putted in a queue for removal. To achieve better performance, the second key can be added. Cost for fetching and storing objects is usually taken as the second key. It is implemented in proxy caching that estimates page load delay [WA97], algorithms explained, analyzed and referenced in [Par96] and others.

Proposed algorithms do not predict when will occur next access to some object. Some algorithms suppose that time till next equals previous delay between accesses. Since time access patterns can be more complex than this one, some advance in this direction could be done.

Existing predicting mechanisms do not predict the time of the next access. They are usually based on assumption that more valuable are those objects that are in trend (LRU) or that are of greater need (LFU) or that are required recently (FIFO). By predicting the time of next access, more sophisticated heuristics could be employed. Proposed predicting mechanism should have enough information to use more than one possible characteristic in prediction. Thus, delays between previous n accesses are being tracked in the history register (HR). Each object has it’s own history register which addresses one entry in access delay table (ADT) that contains all possible delays for this state. Some heuristics can chose next most possible delay (e.g., the worst case, or first larger then time passed since last access). Parameters that characterize work of the algorithm are:

1. the organization of the HR,
2. the window width (should it be of equal width or variable dependently on the expiration date of the object),
3. the window pane width (should all panes be of equal width or longer for earlier accesses),
4. the mapping between HR and ADT entry (should it be 1-1 or n-1),
5. when to follow transitions from state to state (in real-time or on demand),
6. implied heuristics (ranking of possible accesses found in ADT by best-case, worst-case, average-case, LRU).

These parameters will be examined during simulation.

Figure 1 Example: HR points to appropriate entry in ADT. All predictions are made according to delays found for that entry. When different delay found for this object it is recorded in the entry and HR is directed to other entry

The example is shown on the Figure 1. Each D t units of time 0 or 1 is shifted in from the left according to access to the object. In HR it is found that all possible delays are less or equal one or two D t. So, prediction is based on this information. When 6D t delay found in the pattern, addressed entrance in ADT is modified and HR directed to new entrance. All objects that address the previously addressed entrance in ADT, could have new future. If found that there were no accesses longer than 2D t it is supposed that next access will occur after 6D t.

Since this function returns exact time of next access, more quality in caching is expected. This function will be referenced as TDT (time delay tracking).

Approximation of this algorithm will track previous n delays between accesses (classified in 10 categories - states). Analyzing traces, probabilities of transiting from state to state will be found. The next state will be predicted as state found in file’s history with the highest probability of being the next one.

If some improvement is found, the proposed algorithm will be simulated.

Temporal locality on the Web is caused by repeated access of one or more user to the single object. If repeated access is located in short time interval it is supposed that next access will occur in near future. If some kind of rule could be found in access pattern, more qualitative prediction could be performed [PR94] . Knowing the time of next access can be used in numerous ways. Objects that have expiration time smaller than time of next access can be purged to free space for incoming documents. Objects that will never be accessed also can be purged. Object that have known but distant access time can be purged, but prefetched before needed. The question is: is it reasonable to expect some periodical behavior of accesses?

Examined traces are obtained from NLANR (National Laboratory for Applied Network Research) with a grant from the National Science Foundation (grants NCR-9616602 and NCR-9521745).

They are collected during 4 days. The time is classified in 10 categories. Each category has 10% of all requests made during that period. Table 1 presents those intervals.

The idea is to see the relation between previous and next delay. It is assumed that the state is assigned to the file according to class of previous delay. Next state is class of a next delay. Figure 2 presents the probability of transiting from current state to another one.

Figure 2 The probability of transiting from current to another state. State 10 is never reached. State 11 presents infidelity

There is high probability that the next state will be the same as previous. Also, there is high probability that the file will not be accessed (state 11).

The Figure 3 shows the probability that the next state is one of previous all, 10, 9...1 states.

Figure 3 The probability of guessing next access based on delays between previous accesses.

This shows that there can be found some rule for predicting next state.

Simulation will compare the hit rate and weighted (byte) hit rate of proposed algorithm with following ones:

1. LRU
2. LRU min
3. LFU
4. FIFO

All caches have the same storage space. Accuracy of predicting next state will be also measured.

Maximum delay between repeated request: 343966 seconds

TODO!

Since work is in progress we have no implementational analysis.

Results of the experiment have to show benefits of using proposed algorithms. Second, it is important to find conditions under which proposed algorithms improve existing situation. Also it is important to find appropriate parameters used in prediction (e.g., window and pane width, weighting time delays, …).