Affiliations: Division of Advanced Computing, The Institute of High Performance Computing, 1 Science Park Road, #01-10 The Capricorn, Singapore 117528. E-mail: lixr@ihpc.a-star.edu.sg | Computer Networks and Distributed Systems (CNDS) Laboratory, Department of Electrical and Computer Engineering, The National University of Singapore, 10 Kent Ridge Crescent, Singapore 119260. E-mail: elebv@nus.edu.sg
Note: [] Coresponding author: Bharadwaj Veeravalli, Senior MIEEE, MIEEE-CS, Computer Networks and Distributed Systems (CNDS) Laboratory, Department of Electrical and Computer Engineering, The National University of Singapore, 10 Kent Ridge Crescent, Singapore 119260. E-mail: elebv@nus.edu.sg.
Abstract: In this paper, we address the issue of optimizing the per request cost and maximizing the number of requests that can be served by a networked system that demands staging of data at vantage sites. In order to provide a guaranteed Quality of Services, generation of multicast trees with end-to-end delay constraints is recommended to minimize the costs. Since such an issue has been proved to be NP-complete in a networked environment, we proposed two efficient and practically realizable heuristic algorithms, referred to as Source-Initiated Scheduling (SIS) algorithm and Client-Initiated Scheduling (CIS) algorithm to solve the problem in polynomial time. Both SIS and CIS algorithms judiciously combine the concept of QoS-constrained multicast routing and network caching, so that the copies of data to be staged can be dynamically cached in the network. These strategies are carefully designed to consider the underlying resource constraints imposed by the dynamic network environments, such as link bandwidth availability, data availability on the network, and the storage capabilities of a site. We analyze and quantify the performance under several influencing parameters such as link availability, cache capacity and the data availability. Simulation results show that both of the proposed algorithms are able to reduce the service cost and achieve a high acceptance ratio.
Keywords: Cache capacity, link bandwidth, QoS-constrained multicast routing, network caching
