Scheduling algorithms for a cache pre-filling content distribution network
Proceedings - IEEE INFOCOM - Tập 2 - Trang 940-949 vol.2
Tóm tắt
Cache pre-filling is emerging as a new concept for increasing the availability of popular Web items in cache servers. According to this concept, Web items are sent by a "push-server" to the proxy cache servers, usually through a broadcast-based or a multicast-based distribution mechanism. One of the most difficult challenges is to design the scheduling algorithm of the push-server. This algorithm needs to determine the "broadcast scheduling map", namely which Web items to broadcast and when. In this paper we study the approach where every constant period of time each proxy cache analyzes the requests it has received in the past and determines which Web item it prefers to receive by broadcast and when. We formalize a related problem, called the "cache pre-filing push" (CPFP) problem, analyze its computational complexity, and describe efficient algorithms to solve it.
Từ khóa
#Scheduling algorithm #Satellite broadcasting #Network servers #Availability #Costs #Web server #Internet #Algorithm design and analysis #Bandwidth #UnicastTài liệu tham khảo
wessels, 1997, Application of the Internet Cache Protocol (ICP)
10.1109/49.669043
hameed, 1997, Log-time algorithms for scheduling single and multiple channel data broadcast, Mobile Computing and Networking, 90
su, 1997, Broadcast scheduling for information distribution, INFOCOM, 109
10.1109/TCOM.1987.1096659
aksoy, 0, Data staging for on-demand broadcast, Proceedings of the 27'th VLDB Conference 2001
acharya, 1998, Scheduling on-demand broadcasts: New metrics and algorithms, Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom'98), 43, 10.1145/288235.288248
garey, 1979, Computers and Intractability A Guide to the Theory of NP-Completeness
cooper, 2001, Internet web replication and caching taxonomy, 10.17487/rfc3040
10.1287/ijoc.11.2.138
bar-yehuda, 1985, A local-ratio theorem for approximating the weighted vertex cover problem, Annals of Discrete Mathematics, 25, 27
10.1145/335305.335410
dykeman, 1986, Scheduling algorithms for videotex system under broadcast delivery, Proceedings of ICC, 1847
cormen, 1990, Introduction to Algorithms