Check out the new USENIX Web site. next up previous
Next: The CIRG Algorithm Up: Replacement Algorithms for Modem Previous: Replacement Algorithms for Modem

User Activity Patterns

The primary difference of the modem pool setting relative to a general replacement setting is the possibility of denial of service (that is, busy signals). Whereas replacement in general buffer management is based on always satisfying the incoming request, in modem pools it is better to sometimes deny requests. The reason is both subjective (because active users will get very annoyed at losing a resource that they claimed first) but also often objective: with dynamic IP address assignment, disconnections are costly as all existing TCP connections will be terminated. Overall, there is no compelling reason to always satisfy a request for connection in modem pools, unlike, for instance, buffer management in memory hierarchies. Hence, the modified replacement problem that we study, includes a ``minimum inactivity threshold'' parameter. A user can be replaced only if she has been idle for at least this much time. If no user can be replaced, incoming connection requests are denied.

The purpose of a replacement algorithm is to recognize regularities in the reference patterns and predict correctly which entities can be replaced with minimum cost. Thus, the unique characteristics of the modem pool domain influence the choice of a replacement algorithm. A characteristic of this domain is that there is no concept of spatial locality, or, in general, any way to associate the activity of two different users. ``Spatial locality'' refers to the observation that once an entity becomes active, other entities that are close to it in a well-defined space are likely to also become active soon. For instance, in virtual memory systems once a page is referenced, pages next to it, either in the address space, or in the recency space,gif are also likely to be referenced soon. No such inference can be drawn in the case of modem pools. Individual users are quite likely to have no interactions with one another and there is rarely reason for their inactivity patterns to be correlated. The lack of spatial locality means that replacement algorithms that may be successful in other domains are unsuitable for modem pools. For example, recently proposed algorithms for virtual memory replacement, like SEQ [GC97] (which detects regularities in the address space) or EELRU [SKW99] (which detects regularities in the recency space) are not appropriate for modem pool replacement.

The question then becomes, what kind of regularities are there in modem activity? Clearly, activity patterns are mainly dictated by human users but also Internet tools (e.g., email clients, browsers, etc.). It is interesting to examine whether strong regularities exist. For this, we consider the distributions of idle times before a user becomes active for the three traces of our study, shown in Figure 2.

   figure59
Figure 2: Idle time distributions for the three traces of our study. The left ends of all traces rise quickly and are excluded for clarity.

There are a few observations we can make. First, as expected, there is strong temporal locality exhibited by all traces: the number of times a connection is re-activated generally decreases very rapidly as a function of the idle time. A second observation is that there is evidence of programmatic (i.e., periodic) behavior in all traces. In the AT&T Labs trace, strong spikes of activity appear at 5 and 10 minutes of idle time. Additionally, strong activity is observed after 14 minutes of idle time, which is immediately before the inactivity timeout of 15 minutes for this service. Further activity, however, is evident for idle times (16 minutes) slightly longer than the disconnection timeout. This suggests that some users may have set their systems to reconnect immediately after a non-user-initiated disconnection. This is one of the features that may interact with our simulations and are discussed further in Section 4.1. The Telesys traces also exhibit periodic activity, for instance, every 10, 20, and 30 minutes. Activity after exactly 5 or 15 minutes of idle time could also be strong for the Telesys traces, but due to the trace granularity (2 minutes) it cannot be distinguished very well.

We see, therefore, that the AT&T Labs and Telesys workloads show evidence of both human and programmatic activity. Recall that ``workaholics'' (i.e., users who tend to be permanently connected) were excluded from the AT&T trace. Hence, it is reasonable to believe that the periodic activity observed is not just a response to the inactivity timeout of the system. Such periodic activity is significant (for instance, periodic stock price updates are often more important to home traders than any interactive traffic).

Overall, and quite expectedly, Figure 2 shows that human-produced activity has excellent temporal locality: a connection receiving only human input tends to stay inactive once it becomes inactive. Most of the activity seen after some inactivity seems to be programmatically produced because it coincides with easily identifiable time intervals. A good replacement algorithm should be able to perform well for both kinds of activity.


next up previous
Next: The CIRG Algorithm Up: Replacement Algorithms for Modem Previous: Replacement Algorithms for Modem

Yannis Smaragdakis
Tue Apr 25 15:09:47 EDT 2000