Paging against a distribution and IP networking

In this paper we consider the paging problem when the page request sequence is drawn from a distribution and we give an application to computer networking. In the IF-paging problem the page interrequest times are chosen according to independent distributions. For this model we construct a very simple deterministic algorithm whose page fault rate is at most five times that of the best online algorithm (that knows the interrequest time distributions). We also show that many other natural algorithms for this problem do not have constant competitive ratio. In distributional paging the interrequest time distributions may be dependent, and hence, any probabilistic model of page request sequences can be represented. We construct a simple randomized algorithm whose page fault rate is at most four times that of the best online algorithm. The IF-paging problem is motivation by the following application to data networks. Next generation wide area networks are very likely to use connection-oriented protocols such as Asynchronous Transfer Mode. For the existing investment in current IP networks such as the Internet to remain useful, we must devise mechanisms to carry IP traffic over connection-oriented networks. A basic issue is to devise holding policies for virtual circuits carrying datagrams; for some connection-oriented networks the holding policy problem is exactly IP-paging. (C) 1999 Academic Press.