Client assignment in content dissemination networks for dynamic data

Abstract

Consider a content distribution network consisting of a set of sources, repositories and clients where the sources and the repositories cooperate with each other for efficient dissemination of dynamic data. In this system, necessary changes are pushed from sources to repositories and from repositories to clients so that they are automatically informed about the changes of interest. Clients and repositories associate coherence requirements with a data item d, denoting the maximum permissible deviation of the value of d known to them from the value at the source. Given a list of <data item, coherence> served by each repository and a set of <client, data item, coherence> requests, we address the following problem: How do we assign clients to the repositories, so that the fidelity, that is, the degree to which client coherence requirements are met, is maximized?In this paper, we first prove that the client assignment problem is NP-Hard. Given the closeness of the client-repository assignment problem and the matching problem in combinatorial optimization, we have tailored and studied two available solutions to the matching problem from the literature: (i) max-flow min-cost and (ii) stable-marriages. Our empirical results using real-world dynamic data show that the presence of coherence requirements adds a new dimension to the client-repository assignment problem. An interesting result is that in update intensive situations a better fidelity can be delivered to the clients by attempting to deliver data to some of the clients at a coherence lower than what they desire. A consequence of this observation is the necessity for quick adaptation of the delivered (vs. desired) data coherence with respect to the changes in the dynamics of the system. We develop techniques for such adaptation and show their impressive performance.