A pool of modems is a time-shared resource: there are typically many
more potential users than can simultaneously connect. The most common
instance of modem pools is in telephone-modem-based Internet Service
Providers (ISPs), where modems accept user connections over the
telephone network. When all modems are occupied, no more connections
are allowed and the users attempting to connect receive a busy
signal. Although ISPs strive to avoid busy signals, this is not always
feasible. The most common line of defense is to keep a fixed ratio of
subscribers to modems, with a value of 10:1 sometimes considered safe
for avoiding busy signals. This policy, however, is hard to maintain
consistently (e.g., as usage patterns change in response to marketing
actions
) and cannot
always protect fully against busy signals. As an added measure, some
ISPs try to discourage subscribers from constant modem use by setting
usage limits and applying surcharges for exceeding them. An
additional widespread practice is to proactively disconnect users who
have been idle for some fixed time interval or users who have been
connected continuously for some period of time. Recently, Douglis and
Killian [DK99] improved over fixed idle timeout policies with
adaptive proactive disconnections of users. Their technique
varies the idle time threshold for disconnecting a user, based on the
user's past activity patterns.
Although all of the above techniques are valuable for certain
scenarios, they do not acknowledge that, in the most common case, the
cost of allowing a user to stay connected is a function of the current
load. ISPs typically suffer a cost for prolonged usage only
when the modem pool utilization has reached capacity. In other
words, it is commonly of no cost to ISPs to allow users to stay
connected when modems are available. The cost of telephone lines is
usually fixed for ISPs, regardless of usage. Also, the cost of local
phone calls in the US is commonly fixed (or zero) for users,
regardless of call duration. To the best of our knowledge, the only
policy in use that somewhat relates usage limits and current load is
the variable timeout policy: some ISPs have shorter timeouts for
pre-defined ``peak hours'' (e.g., 6pm to midnight). Nevertheless, more
sophisticated schemes are easy to implement and, as we argue,
inconvenience users much less.
In this paper, we examine the case of treating a modem pool as a replacement buffer. That is, users are not disconnected until all modems are occupied. When a new user attempts to connect with all existing modems occupied, there are two possible outcomes: either there are no ``idle'' users currently and the new user will be denied service (busy signal) or one of the idle users will be replaced (i.e., disconnected in favor of the new user). Strictly speaking, this approach is not easy to implement exactly, because busy signals are generated by the telephone network, not the ISP. Nevertheless, as we will explain, the policy can be easily approximated closely in an actual modem pool.
The interesting question in replacement scenarios is how to choose the user to replace. We examine three different replacement algorithms: LRU, CIRG, and RANDOM. The LRU algorithm replaces the user who has been inactive the longest. The CIRG algorithm (for Conditional Inter-Reference Gap) is novel and is inspired by Phalke's work on inter-reference gaps for access prediction in virtual memory systems [Pha95]. In intuitive terms, CIRG attempts to recognize access patterns for individual users and should be a good fit for the modem pool domain. Finally, the RANDOM algorithm selects any idle user for replacement. In Section 3 we discuss in detail the replacement problem for modem pools. The problem is related but different from replacement in other settings (e.g., virtual memory systems). The differences in the problem and in the expected access patterns (e.g., no spatial locality) guide the design of replacement algorithms and we explain what the characteristics of a good replacement algorithm should be.
For our experiments we used three extensive traces of user activity, which cover several distinct circumstances. The results of our simulations show that our approach is much less inconvenient to users than proactive disconnections after a fixed period of inactivity. Similar to the Douglis and Killian work [DK99], our metric for ``inconvenience'' counts ``faults'', that is, disconnections of users who are likely to want to be active again soon. In these terms, disconnecting users only when the modem pool is full results in an order of magnitude fewer faults than a fixed idle timeout policy. More interestingly, however, we show that the choice of replacement algorithm is important. RANDOM has a much higher cost (by over 20% and up to 1000%) than LRU. LRU, in turn, performs worse than CIRG, often by 10% or more. (Both LRU and CIRG turn out to be very good predictors of future idle times.) This shows that the naive approach of disconnecting any idle user when the load is high is far from ideal.
It is an interesting challenge to further quantify the benefits of our approach (or of any other approach to disconnecting idle users). The difficulty is that disconnecting users may encourage them to set up their connection so that it appears to be permanently active. For this reason, although we present results for a wide range of values, we concentrate on a range that guarantees a quality of service similar to that of the trace collection environment. (The natural assumption is that when users are not annoyed, they will not change their behavior.) We show that, for CIRG, good quality of service can be maintained with up to 13% fewer modems than a no-disconnections policy. This result shows that when there are not enough modems (e.g., due to a surge in subscriber numbers) the impact can be softened significantly using our technique.
Our experiments are interesting, however, regardless of the actual economics and current practices in the ISP business. What we are really demonstrating is the kind of activity patterns that the combination of human users and modern Internet tools (e.g., browsers, email clients, etc.) is expected to exhibit. In particular, we analyze which techniques work well for predicting future idle times. These results may be applicable to more contexts than telephone-modem-based ISPs--practically in every case a time-shared resource is accessed interactively by Internet users and we want to predict future inactivity times.