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,
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.
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.