[ Homepage  | Biography  | Courses  | Members  | Publications  | Research/Funding  | Workshops/Presentations  ]

Dimensioning of Content Distribution Networks (CDNs)

Consider the following problem: a CDN operator has at its disposal a total storage capacity for S information objects. The target is to use this storage budget to selectively replicate information objects drawn from a set of available information objects, such that the average distance from all clients to all the requested objects be minimized. Producing the required object placement not only identifies the set of information object for each node but also returns the fraction of the total storage capacity that must be allocated to each node.

For the aforementioned problem we have developed exact and approximate algorithms for the cases of tree graphs and general graphs. We solve the tree case optimally in polynomial time and the general case approximately (within a constant factor of the optimal) in polynomial time. The solution comes through a two-step algorithm that solves a multi-commodity version of the single-commodity k-median problem of discrete location theory.

For the tree case, we have also developed heuristics that track closely the performance of the polynomial exact algorithm, but incur a much smaller complexity. The developed heuristics may additionally cater to load balancing. For more information, see [1], [2].

Distributed Selfish Replication

A commonly employed abstraction for studying the object placement problem for the purpose of Internet content distribution is that of a distributed replication group. We have considered the model of distributed replication group proposed by Leff, Wolf, and Yu (IEEE TPDS, 1993) and have extended it to the case that individual nodes act selfishly, i.e., cater to the optimization of their individual local utilities. Our main contribution has been the derivation of equilibrium object placement strategies that: (a) can guarantee improved local utilities for all nodes concurrently as compared to the corresponding local utilities under greedy local object placement; (b) do not suffer from potential mistreatment problems, inherent to centralized strategies that aim at optimizing the social utility. Such mistreatment problems arise when a centralized placement strategy uses the storage capacity of some nodes for storing locally irrelevant objects for the purpose of satisfying remote, rather than local, requests. Hijacking a node's storage can lower its local utility to a level that is worse than the greedy local one, thus prompting its withdrawal, which eventually leads to the break up of the group. We have developed a baseline computationally efficient algorithm for obtaining the aforementioned equilibrium strategies, and then extended it to improve its performance with respect to fairness. Both algorithms are realizable in practice through a distributed protocol that requires only limited exchange of information. Relevant publications [3], [4].

Meta Algorithms for Web Caches

Meta algorithms In a multi-level cache, a hit at level l leads to the caching of the requested object in all intermediate caches on the reverse path (levels l-1,...,1). We have shown that a simple modification to this de facto behavior, in which only the l-1 level cache gets to store a copy, can lead to significant performance gains. The modified caching behavior is called Leave Copy Down (LCD); it has the merit of being able to avoid the amplification of replacement errors and also the unnecessary repetitious caching of the same objects at multiple levels.

Simulation results under synthetic and trace-driven workloads show that LCD reduces the average hit distance as compared to other type of interconnections in both tandem and tree topologies.

For the case of LCD interconnected LRU tandems, we have construct an accurate approximate analytic model. The developed model presents several novel techniques for the analysis of interconnected caches, and gives a clear insight as to why the LCD interconnection yields an improved performance. Although initially motivated from web caching, LCD and its analysis are more general in scope, and apply to other applications of caching as well. For more information, see [5], [6].


[1]. N. Laoutaris, V. Zissimopoulos, I. Stavrakakis, "On the Optimization of Storage Capacity Allocation for Content Distribution," Computer Networks Journal, Vol. 47, No. 3, pp. 409-428, February 2005. [PDF]

[2]. N. Laoutaris, V. Zissimopoulos, I. Stavrakakis, "Joint Object Placement and Node Dimensioning for Internet Content Distribution," Information Processing Letters, Vol. 89, No. 6, pp. 273-279, March 2004. [PDF]

[3]. N. Laoutaris, O. Telelis, V. Zissimopoulos, I. Stavrakakis, "Distributed Selfish Replication," accepted in IEEE Transactions on Parallel and Distributed Systems, 2005.

[4]. N. Laoutaris, A. Panagakis, I. Stavrakakis, "Content Distribution through Autonomic Content and Storage Management," WAC 2004, Berlin, Germany, October 2004.

[5]. N. Laoutaris, H. Che, I. Stavrakakis, "The LCD Interconnection of LRU Caches and Its Analysis," accepted in Performance Evaluation, 2005. [PS]

[6]. N. Laoutaris, S. Syntila, I. Stavrakakis, "Meta Algorithms for Hierarchical Web Caches," IEEE IPCCC 2004, Phoenix, Arizona, April 2004.[PDF]