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 IP-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 algo- rithm whose page fault rate is at most four times that of the best online algorithm. The IP-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.