Analysis of complex Big Data systems and telecommunication networks
Creators: name: Μίχος, Σωτήριος Κ.
Publisher: name: Aristotle University of Thessaloniki
Year: 2020
Subjects: Κεντροποιημένο/αποκεντροποιημένο σύστημα κρυφής μνήμης
Υπολογιστική ανάλυση
Υπολογιστική βελτίωση
Κωδικοποίηση δικτύου
Centralized/decentralized coded caching
Computational analysis
Computational improvement
Network coding

description: Coded caching is the distribution of content across a telecommunication system using techniques from coding theory in order to create multicasting opportunities among the users receiving the content. This enables a multiplicative improvement over the classic uncoded caching with respect to the transmission rates required in the delivery phase of the content. Since its introduction, coded caching has drawn significant research interest and several different schemes have been proposed over the last years. In this work, we focus on the fundamental case of coded caching with uncoded prefetching, where each user's cache is filled with uncoded content during a prefetching stage and, during a later delivery phase, each user's request must be served in the most efficient way. This important case has recently received a complete information-theoretic characterization. However, reaching the information-theoretic optimality imposes a significant computational imbalance among the users. To this end, we aim at mitigating this imbalance by first performing a complete computational analysis of the two major forms of coded caching with uncoded prefetching, namely centralized and decentralized, and then proposing a new method for the delivery phase that achieves a significant improvement compared to the state of the art.
description: Τα συστήματα κωδικοποιημένης κρυφής μνήμης αναφέρονται στην διανομή περιεχομένου εντός ενός τηλεπικοινωνιακού συστήματος χρησιμοποιώντας τεχνικές από τη θεωρία κωδίκων με σκοπό να δημιουργηθούν ευκαιρίες πολύ-εκπομπής μεταξύ των χρηστών που λαμβάνουν το περιεχόμενο. Αυτό οδηγεί σε μια πολλαπλασιαστική βελτίωση σε σχέση με τα κλασσικά συστήματα μη-κωδικοποιημένης κρυφής μνήμης ως προς το ρυθμό εκπομπής που απαιτείται στη φάση παράδοσης του περιεχομένου. Από την ανάπτυξή του, τα συστήματα κωδικοποιημένης κρυφής μνήμης έχουν προσελκύσει σημαντικό ερευνητικό ενδιαφέρον και έχουν αναπτυχθεί πολλά διαφορετικά σχήματα στη διάρκεια των τελευταίων χρόνων. Σε αυτή την εργασία εστιάζουμε στη θεμελιώδη περίπτωση ενός συστήματος κωδικοποιημένης κρυφής μνήμης με μη-κωδικοποιημένη προανάκτηση, όπου στην κρυφή μνήμη κάθε χρήστη τοποθετείται μη-κωδικοποιημένο περιεχόμενο κατά τη διάρκεια της φάση προανάκτησης και, αργότερα, κατά τη φάση παράδοσης, το αίτημα κάθε χρήστη πρέπει να εξυπηρετηθεί με τον πιο αποδοτικό τρόπο. Αυτή η σημαντική περίπτωση έχει πρόσφατα δεχτεί έναν πλήρη πληροφοριοθεωρητικό χαρακτηρισμό. Όμως, η επίτευξη του πληροφοριοθεωρητικού βέλτιστου εισάγει μια σημαντική υπολογιστική ανισορροπία μεταξύ των χρηστών. Για το σκοπό αυτό, στοχεύουμε στη βελτίωση αυτής της ανισορροπίας αρχικά αναπτύσσοντας μια πλήρη υπολογιστική ανάλυση των δυο βασικών μορφών συστήματος κωδικοποιημένης κρυφής μνήμης, της κεντροποιημένης και της αποκεντροποιημένης μορφής, και στη συνέχεια προτείνοντας μια νέα μέθοδο για τη φάση παράδοσης η οποία πετυχαίνει σημαντική βελτίωση σε σχέση με τις μεθόδους που είναι διαθέσιμες στη βιβλιογραφία.