The CIRG replacement algorithm (for Conditional Inter-Reference Gap) is a novel (to our knowledge) algorithm, loosely based on the Inter-Reference Gap model proposed by Phalke [Pha95]. The term ``inter-reference gap'' is a synonym for idle time in the user activity domain. The CIRG algorithm keeps per-user information about the most recently encountered idle times and uses it to predict future idle times. In particular, for each user, CIRG keeps a list, which we call idle. (We will later generalize this to multiple lists.) The first element of the list, idle(1) is the user's idle time before the user last became active. For i > 1, the i-th element of the list, idle(i), is the total idle time for a user the last time the user was idle longer than idle(i-1) time units. For example, the contents of the idle list could be:
2, 5, 13, ...
(with minutes as the time unit) meaning that the user was idle for 2
minutes before she last became active. The last time the user was idle
for more than 2 minutes, she stayed idle for 5 minutes. The last time
the user was idle for more than 5 minutes, she stayed idle for 13, and
so on.
Using the idle list and the current idle time, the CIRG algorithm
computes how long a user stayed idle the last time she was idle for as
long as now.
This is used as an estimate of the total idle time until a user will
next become active. In our example, given a current idle time of 7
minutes, CIRG will predict that the user will stay idle for another 6
minutes (for a total of 13). The user with the highest predicted future
idle time is the one to be replaced.
This scheme can easily be generalized to multiple lists. That is, with k lists, CIRG can
compute how long a user stayed idle the last k times she was idle
for as long as now. A reasonable estimate of future idle time will
then be the average of the predicted values from each of the k
lists. To keep the list lengths short, we can quantize the idle times
values (e.g., by rounding all idle times to the closest multiple of 2
minutes).
We have experimented with the CIRG algorithm in several different replacement settings. Overall, CIRG is, as expected, good for detecting regular patterns in behavior. CIRG is not an ideal algorithm for some settings (e.g., virtual memory replacement) because it keeps statistics in terms of time differences between accesses. (As we explain in [SKW99], inter-reference time is not a reliable metric of locality for modern programs because they may access vastly different amounts of memory in the same amount of time.) Nevertheless, we expected CIRG to be appropriate for the modem replacement domain, which deals with human users and real-time idleness.
An interesting aspect of CIRG is that, because it keeps statistics per user, it can recognize an arbitrary number of different periodic patterns. Thus, CIRG is a good algorithm for dealing with multiple different regular patterns. Such patterns could occur because of Internet tools pulling information (e.g., email clients downloading messages every 10 minutes, browsers updating the displayed stock prices page every 5 minutes, etc.). Patterns could also occur because of user habits (e.g., the user usually takes 5-10 minute breaks).