The topology aware file distribution problem

We present theoretical results for large-file distribution on general networks of known topology (known link bandwidths and router locations). We show that the problem of distributing a file in minimum time is NP-hard in this model, and we give an O(logn) approximation algorithm, where n is the number of workstations that require the file. We also characterize our method as optimal amongst the class of “no-link-sharing” algorithms.