Home // AFIN 2013, The Fifth International Conference on Advances in Future Internet // View article

Competitive Algorithms for Online Data Placement on Uncapacitated Uniform Network

Authors:
Maciej Drwal

Keywords: online algorithms; network algorithms; wide-area networks

Abstract:
In this paper, we study the iterated problem of placing copies of data objects in a network of storage servers in order to serve request demands with minimal delay. We show how to compute the optimal sequence of decisions for two variants: in general, using dynamic programming algorithm, which requires exponential time, and for uncapacitated uniform network, which requires only polynomial time. For the latter case, we study online algorithms, which return new placement immediately after a new element of input sequence becomes available. We prove that the comeptitive ratio of the problem is bounded by 2. The paper is summarized with computational study, which compares the 2-competitive online algorithm with dynamic programming. Online distributed storage management becomes increasingly important issue in large-scale Internet applications due to the widespread of Content Devlivery Networks, as well as cloud computing and content-aware paradigms.

Pages: 43 to 49

Copyright: Copyright (c) IARIA, 2013

Publication date: August 25, 2013

Published in: conference

ISSN: 2308-4340

ISBN: 978-1-61208-300-1

Location: Barcelona, Spain

Dates: from August 25, 2013 to August 31, 2013