[ 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
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].
References
[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]