Figure 1. Release/recode-decision based on
image size and access frequency.
![[Figure 1]](decision.gif)
In this paper we address a set of modifications to classical proxy caching algorithms which allow the implementation of a soft caching proxy system. Changes to replacement algorithms are detailed and image size and recoding issues are discussed. We also present our working soft caching testbed based on the Squid proxy, detail the modifications we have made and present the experiences obtained.
The explosive growth in Internet traffic has made it critical to look for ways of accommodating the increasing number of users while preventing excessive delays, congestion and widespread blackouts. This has led to a great deal of effort being devoted to studying web caching techniques [1]. While caching is useful both at the server (for example some pages might be kept in RAM memory) and the client (where recently accessed files are saved to disk), we concentrate here on proxy based caching. In this environment clients can designate a host to serve as a proxy for all or some of their requests. The proxy acts as a cache by temporarily storing on local disks, or memory, objects which were requested by the clients.
Current design efforts are based on the assumption that object integrity has to be preserved, i.e. objects cannot be modified. Thus an object is either present or not in the cache, but cannot be available in part. Here we propose that caching proxies should be able to perform recoding of the images in the cache so that lower resolution versions of the images can be stored and made available to the clients. We call this strategy Soft Caching [5, 16], since we now allow a lower resolution version of an image object to be stored; a soft decision is made (how many bits to use for a certain image) instead of a hard one (is the image left in the cache or not).
In our framework, specific caching strategies are derived for images and other media objects, for which preserving the object integrity is not completely necessary. While incomplete delivery of text data may render it useless, for images it may be sufficient to provide the end user with a lower resolution version of the image stored at the remote server, especially if this can be done in significantly less time than it would take to download the full resolution image. This is one of the reasons for the continuing popularity of progressive image formats such as Progressive JPEG [7] nowadays, or pyramids [8] and wavelets [9] in the near future.
When access occurs over a fast link progressive transmission may not offer significant advantages, but over a slow link a progressive format allows a usable, albeit reduced resolution, picture to be available even if the transfer is terminated early. This allows users to stop the transfer when a sufficient quality image has been downloaded. A study of such a multi-resolution imaging system under simple assumptions can be found in [10, 11] and motivates the advantages in terms of average access delay of using a progressive transmission.
If the proxy has a lower resolution version of the requested image but the image quality is too low, the user can always request the original image from the server by using the standard method of the browser for by-passing caches (e.g. Shift-Reload in Netscape). Currently this means transferring all of the original image from the server to the client, so the price to pay for the better resolution is an increased download time.
As progressive image formats and transmission methods that enable the transfer of partial objects, such as the range-request method of HTTP/1.1 [18], become more widespread, the reloading of the whole image can easily be avoided. The benefits on the user-proxy link are still the same and even when the user wants to see all of the image, only the bits that are needed to complete the image need to be requested from the origin server, thus reducing the load on the backbone.
Real-time distillation [12, 13] has been proposed to allow proxies to extract (distill) a low resolution image to serve it to slow clients (e.g. clients connected to the network via dial-up). While this approach is similar in philosophy, we consider here a more general case where a shared resource (the cache memory) is taken into account and other configurations are considered (including for example a fast local network and a remote access to the server). Recently, two commercial systems based on the real-time distillation framework [2, 3] have come to the market.
This paper is organized as follows. Section 2 addresses the modifications to existing systems that are required by soft caching. In section 3 we present our soft caching testbed. Section 4 sets directions for future work. Finally, section 5 concludes the paper.
While most of the general principles of proxy caching are directly applicable to soft caching, an efficient soft caching system must also consider the effects of image recoding in its algorithms.
Given the advantages (minimization of average access time) of progressive transmission [10, 11], our goal is to find simple, yet efficient ways to improve existing caching algorithms to make them benefit from the advantages of soft caching.
We will first discuss issues related to recoding and image size and then we will present the modifications to existing cache replacement algorithms.
An important factor in a soft caching system is the number of recoding levels or the number of different representation levels an object can have in the proxy.
Having many recoding levels reduces the potential benefits from soft caching since an image can remain in the cache for a long time even though it will not be used. Having fewer recoding levels would get rid of the unneeded images quicker but could also reduce the quality of the useful images faster. Also, the smaller the number of levels, the less we use CPU-time to recode the image during its stay in the cache.
To get more insight into the number of levels needed, we took 800 unrecoded JPEG-images and recoded them through all the 10 levels that we use. The images were mostly small photographic images, resolution about 300x200 pixels and average size around 12 KB. Some of the images were much larger (1500x1000, 400 KB or even larger) and a significant part of them were non-photographic graphical images such as buttons and toolbars. Table 1 presents the savings obtained in going from a higher recoding level to a lower one.
| Level | Percentage from previous level | Percentage from original image |
|---|---|---|
| Full | 100 % | 100 % |
| 9 | 64.7 % | 64.7 % |
| 8 | 92.6 % | 59.9 % |
| 7 | 92.7 % | 55.5 % |
| 6 | 95.5 % | 53.0 % |
| 5 | 71.0 % | 37.6 % |
| 4 | 71.3 % | 26.8 % |
| 3 | 86.0 % | 23.1 % |
| 2 | 85.4 % | 19.7 % |
| 1 | 55.2 % | 10.9 % |
From the results in table 1 we clearly see that having 10 recoding levels is an overkill. Going from level 8 to level 7 and on to level 6 does not offer much new savings in file size and the degradation in visual quality is almost non-perceptible. So a user who finds level 8 acceptable will also find level 6 acceptable with a very high probability. A similar argument holds for levels 4, 3 and 2.
For most photographic images the level where coding artifacts start to appear is level 5 or 6. Non-photographic images usually degrade faster, quality becoming objectionable around level 7 and degrading completely at level 5. This is because JPEG has not been designed to compress such images.
These findings would imply that a good number of recoding levels would be 4 or 5. These would be situated at the full level and approximately at levels 8, 6, 3 and possibly level 1. Although at the first level no details of the image can be seen, it still gives an overall view of the contents of the image. In some situations, such as browsing an image database, this might be enough information to make the decision whether to load more or not.
Since a significant, and certainly a fast growing part of the images consists of navigation buttons and other such non-photographic images which do not take well to recoding, something should be done about them.
A simple way is to look only at the image size and make decisions based on that. Recoding an image of size 2 KB at full resolution to level 6 would save us about 1 KB of disk space but would also use CPU-power doing that. It is therefore not efficient to recode small images for two reasons:
Where to set the threshold of small image? Our sample of 800 images had an average size of 12 KB and we have observed that most non-photographic images tend to be under 5 KB in size. Therefore a threshold of around 10 - 15 KB would be a good choice. It would not waste time and effort on small images but would still give all the benefits for larger images.
Cache replacement strategies in the context of WWW proxies have been extensively studied [6, 14, 15]. The popular Least Recently Used (LRU) [19] algorithm has been found to yield suboptimal performance and many better algorithms have been proposed. An algorithm that takes into account the number of references, object size and download speed has been found to yield good and robust performance [15].
The main difference between a soft and a hard caching system is the existence of partial objects in the soft caching system. Initial simulations would seem to indicate that a strategy that takes into account the fact that the image has been recoded yields better performance (shorter average transmission time, higher hitrate) than a strategy which ignores the state of the object.
How to account for recoding in the replacement algorithm? In an algorithm based on access times, such as LRU, we will need to adjust the object's access time or look also at the recoding time. Otherwise, an object that was chosen for removal would get chosen again after recoding as it would still be the least recently used.
A simple strategy would be to set the access time of an image which has just been recoded to the current time, in this way we will increase its priority in terms of the LRU algorithm. This tends to favor the lower resolutions too much compared to their utility since images that have been recoded several times may potentially remain in the cache for a long period even if they have been accessed just once. A better strategy would set the access time to the old access time plus some fraction of the time elapsed between the last real access and the recoding instant based on the current recoding level.
Instead of modifying the access time, we could use the time when the object was recoded as a secondary key. We mark the time when an object is recoded and when the same object is selected for eviction the next time, we check if it has been accessed since it was recoded. If not, then it is released but if it has been accessed, we recode it again and set the recoding time accordingly. This is also known as the ``second chance'' algorithm [19].
For algorithms which are based on the size of the object and throw out the largest ones, using the actual size of the object would favor recoded objects over untouched ones. Since the quality of recoded images is inferior to that of the unrecoded ones this is not desirable. We should therefore use in the algorithm an estimated size which is calculated as the actual size plus a fraction of the difference between the original and actual sizes.
No matter what strategy is used to choose the objects to be evicted, we must decide whether the object should be released or recoded. The correct decision depends on the current state of the object as well as on general parameters such as number of recoding levels. This decision should carefully weigh the potential benefits gained (shorter transmission time, smaller size) if the image is recoded against the CPU-cost of doing so. If these benefits seem too small as is often the case for very small images, then the image should be released from the cache instead of wasting resources in recoding it.
Figure 1 depicts this decision based on image size and access frequency. A small image could be smaller than 15 KB and a frequently referenced image an image that has been referenced at least twice.
Figure 1. Release/recode-decision based on
image size and access frequency.
The two entries marked with an asterisk(*) need special attention. Assuming that users are using browser caches, a frequently referenced object in a proxy cache is referenced by different users who will possibly have very different opinions about image quality. If we do not have progressive transmission, we should release frequently referenced small documents and the frequently referenced large images should only be recoded a few times in order to minimize the additional waiting time due to the retrieval of the whole object when the quality is not sufficient. With progressive transmission however, we can recode both these types of images since no unnecessary bits need to be transmitted.
After the object has been recoded we will need to update the changes (new size, recoding time) into the internal data structures. When the object is released, no special procedures are needed.
All in all, the modifications needed to convert a classical proxy to a soft caching proxy are small and limited mostly to the replacement algorithm. The actual recoding can and should be done in a separate program which is called by the proxy when recoding services are needed.
As our testbed for studying soft caching in practice, we have chosen the freely available Squid proxy [4]. We are currently using the version 1.1.20.
We run two proxies simultaneously on two different machines. One of them has been modified and the other one is a stock 1.1.20 Squid. The modified one handles only requests to JPEG-images while the normal one handles all other requests (HTML, text, GIF, FTP, etc.). This setup gives us more control over the behavior of the soft caching proxy (amount of cache, different replacement policies, etc.) without having to worry about the modifications having unexpected effects on other object types. To configure the browser to use these two proxies, we use the automatic proxy configuration feature of Netscape, where the browser loads at startup a small piece of JavaScript-code which sets the proxies for JPEG-images and all other objects. The browser makes the choice of proxy based on the URL of the object and in some cases we have observed URLs ending in the suffix .jpg which did not contain JPEG-images, so all our modifications must also verify that the data being handled is a JPEG-image.
As the format for recoded images we have chosen Progressive JPEG. It has the advantage of being supported by the browser and the freely available Independent JPEG Group's library [17] provides us with almost all the functionality we need to recode JPEGs to a coarser representation. Some JPEG-images on the Web are already in the progressive format, but most of them are sequential JPEGs. Therefore when the image is recoded for the first time it must also be transformed from the sequential format to the progressive format.
We have implemented the main recoder as an external process (recoder daemon), like the unlinkd-process of Squid. In the main code the only major modifications concern the function storeGetSwapSpace in file store.c. Here Squid cleans out objects when the cache swap size has gone over the high watermark. In our case, we simply added a call to a new function which handles the recoding. Some minor modifications, such as adding information about the recoding level to logfiles, were also needed in some places.
We did not touch the normal expiry mechanism (function storeMaintainSwapSpace) since the objects that are released there are expired (either real or estimated) and recoding them would serve no purpose.
To make matters simpler, we recode only images that are on the disk, i.e. the ``hot'' objects that Squid keeps in memory are not touched. Also, should it happen so, that an image that has been handed to the recoder becomes ``hot'' and gets swapped into memory then we simply discard the recoded result when it is available.
When the Squid's LRU-algorithm has determined the images to release, our modifications work as follows:
The recoding function forwards the recoding request to the recoder daemon which then handles the details of recoding.
Because the recoding is not instantaneous, we will need to estimate the amount of disk space freed. Otherwise, Squid would keep on sending images to the recoder, since the replacement algorithm tries to free enough space to make the swap size go under a configured threshold.
As the estimate we have chosen 10% of the actual object size, a value which is rather conservative in most cases and therefore should guarantee that after the recoding the swap size is below the configured maximum. Also it has the added benefit of recoding a bit more images then necessary which increases the probability of a user seeing a recoded image thus giving us more data on the visual quality of recoded images.
After the object has been recoded, the above estimate is corrected to the actual value of disk space freed. We also update the time when the object was last referenced. We have chosen to update the reference time to current time, i.e. make it look like the object was just accessed. This tends to keep the images in the cache and thus increases the chances of a user seeing a recoded image. In a production version this could be done in a more optimal way.
We have been running our modified proxy in our lab and are thus far satisfied with the results. The modifications are stable, reasonably fast and the users are happy with the system.
Images where the recoding effects are clearly visible have occasionally been encountered but mostly the image quality has been satisfactory. This may in part be due to the equipment used, mostly Sun workstations with 8 bit graphics cards, where the dithering algorithm of Netscape results in images of such a low quality that recoding cannot be seen before the last few levels.
With a 24 bit graphics card and a good monitor the recoding effects start to appear after a couple of recodings and become clearly visible after five recodings (at least to someone who knows what sort of artifacts to look for).
We have also run an experiment where we gave the same set of images to a normal Squid and our ``soft'' Squid and recorded the number of images in the cache during the experiment. Both proxies started with an empty cache and were given a URL every two seconds. The cache size was set to 20 MB and the high and low watermarks to 19 and 15 MB respectively. The results of this experiment are plotted in Figure 2.
Figure 2. Comparison of the number of images
in a soft and a normal cache
![[Figure 2]](contents.gif)
From the figure we see that at first the two proxies behave identically but when the swap space is full and a lot images need to be released, the soft proxy can keep more images in the cache. At any given moment, the soft proxy has all the images that the normal one has plus recoded versions of the images that the normal proxy has recently thrown away.
Due to the fast rate of requests, the normal expiry mechanism of Squid does not get a chance to work and this results in the saw-tooth curve for the normal Squid. Since we have not modified the expiry mechanism, it would not have an effect on the results.
Currently when a user requests a reload on a recoded image, the whole image is transferred from the origin server. For normal JPEG-images this is the only way of doing it but if the original image is in the progressive JPEG -format then it would be enough to transfer only the missing bits. As Squid already implements HTTP/1.1-protocol, we can use it to study the advantages progressive transmission in a real-life setup by implementing range-requests for objects already in the progressive format.
When we have more experimental data on the visual quality of recoded images we will formulate a probabilistic model of user behavior that we will integrate into the replacement strategy. We will also do more detailed studies on how to include recoding levels into the different existing replacement policies.
To accommodate soft caching, existing cache replacement algorithms have to be modified to take into account the fact that only a part of the object may be available. A decision whether to recode the object or release it must be made based on cache parameters. Based on experimental data we have studied both the number of recoding levels and image sizes and have found good values to be used in a real soft caching system.
We have presented our working soft caching system based on the freely available Squid proxy. We described the modifications necessary for achieving the desired functionality and presented our experiences obtained in using our modified proxy.