• Login
    View Item 
    •   Treasures Home
    • Electronic Theses and Dissertations
    • UTD Theses and Dissertations
    • View Item
    •   Treasures Home
    • Electronic Theses and Dissertations
    • UTD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Algorithms for Optimal Replica Placement in Data Centers

    Thumbnail
    View/Open
    ETD-5608-7379.52.pdf (1.007Mb)
    Date
    2017-08
    Author
    Mills, Kenneth Alex
    0000-0002-1782-6461
    Metadata
    Show full item record
    Abstract
    Abstract
    Owners of data centers are contractually obligated to provide high-availability service to their customers in the presence of ubiquitous hardware failures. Studies have indicated that co-occurring component failure is a key contributing factor towards unavailability in modern data centers [12]. Much effort has been made to produce quality statistical models of correlation among failures. In this dissertation we depart from this approach and provide a model which explicitly captures dependencies among system components. Our model consists of a directed graph wherein nodes represent hardware components and directed edges are used to connect nodes whose associated hardware components have a causal failure dependency. That is to say, failure in the source component may result in the compromised operation of the destination component. Given such a model, we consider how best to place r replicas of data in the data center so as to ensure as many replicas survive as possible. To this end, we cast our goals as combinatorial optimization problems for which we then provide algorithms or establish hardness. We consider several variations on the survivable replica placement problem. Motivated by their use in commercially-available systems for distributed storage, we first address the case wherein the graph is given as a tree. For this problem, we propose lexico-minimizing the failure aggregate, a novel vector-valued objective which closely matches our intuition concerning “good” replica placements. We provide an O(n+r log r) time dynamic programming algorithm for lexico-minimizing the failure aggregate. Next, we consider the problem of placing m replicated blocks of data, so as to optimize the placement of replicas for each block simultaneously. The complexity of this problem appears to be closely related to the skew, which we define to be the difference between the largest and smallest number of replicas among all blocks. We provide an algorithm whose running time grows like O(m^{0(δ2)), where δ is the skew, which is polynomial-time when the skew is a constant. We then consider models which are more complicated than trees. We prove that optimizing replica placement over natural extensions of our model to bipartite graphs is NP-hard, and further show that this implies NP-hardness for directed graphs in general. In light of these hardness results, we next consider classes of graphs which are computationally tractable. Specifically, we show that reliable replica placement is fixed-parameter tractable in a special class of multitrees. A multitree is a directed acyclic graph in which the set of all nodes that can be reached from any fixed node induces a subgraph which is a tree. We parameterize multitrees via their number of roots (i.e., nodes with in-degree zero), and prove that survivable replica placement is NP-hard even when restricted to multitrees with only three roots. We then design a polynomial time algorithm for a special class of multitrees with two roots, and show how to extend this algorithm to one which runs on multitrees with k roots in O(nr^{2k+2}) time, which is polynomial-time when both the number of roots and the number of replicas is fixed.
    URI
    http://hdl.handle.net/10735.1/5487
    Collections
    • UTD Theses and Dissertations

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of TreasuresCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Login

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV