• Login
    View Item 
    •   eScholar Home
    • Faculty of Engineering & Applied Science
    • Doctoral Dissertations
    • View Item
    •   eScholar Home
    • Faculty of Engineering & Applied Science
    • Doctoral Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Coded caching for cache-aided communication and computing with nonuniform demands

    Thumbnail
    View/Open
    Deng_Yong.pdf (1.020Mb)
    Date
    2021-10-01
    Author
    Deng, Yong
    Metadata
    Show full item record
    Abstract
    In this dissertation, we consider the caching system of multiple cache-enabled users with nonuniform demands. We thoroughly characterize the structure of the optimal cache placement of the coded caching scheme (CCS).We show there are at most three file groups in the optimal placement and obtain the closed-form solution in each file grouping case. A simple algorithm is developed to obtain the final optimal cache placement, which only computes a set of closed-form solutions in parallel. We propose a tighter lower bound for caching and characterize the file subpacketization in the optimal CCS. Upon obtaining the optimal placement of the CCS, we characterize the memory-rate tradeoff for caching with uncoded placement. Focusing on the modified coded caching scheme( MCCS), we formulate a cache placement optimization problem to obtain the optimal placement. We present two lower bounds for caching with uncoded placement and compare them with the MCCS to characterize the memory-rate tradeoff and provide insights. We extend our study to accommodate both nonuniform file popularity and sizes and characterize the exact memory-rate tradeoff for two users. We then study the memory-rate tradeoff for decentralized caching. We formulate the cache placement optimization problem for the decentralized modified coded caching scheme (D-MCCS). To solve this non-convex problem, we develop a successive Geometric Programming (GP) approximation algorithm and a two-file-group-based low-complexity approach. We propose a lower bound for decentralized caching and compare it with the optimized D-MCCS to characterize the memory-rate tradeoff in special cases. Beyond caching problems, we consider the coded distributed computing (CDC) with arbitrary number of files of nonuniform popularity. We formulate a mixed-integer linear programming (MILP) problem that jointly optimizes the mapping and shuffling strategies to minimize the shuffling load. To solve this generally NP-hard problem, we propose a two-file-group-based low-complexity approach that achieves close shuffling load as conventional branch-and-cut method which has high computational complexity.
    URI
    https://hdl.handle.net/10155/1381
    Collections
    • Doctoral Dissertations [129]
    • Electronic Theses and Dissertations [1336]

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

     

    Browse

    All of eScholarCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

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