Replication management and cache aware routing in information-centric networking

Abstract

Content distribution in the Internet places content providers in a dominant position, with delivery happening directly between two end-points, that is, from content providers to consumers. This model is driven by the underlying Internet routing paradigm, namely that of transferring datagrams from one routable endpoint to another. This location-centric model limits the ability to fully utilize resources that are available along the route from the provider to the consumer(s), such as storage (e.g., for caching) or computing (e.g., for re-encoding). Information-Centrism has been proposed as a paradigm shift from the host-to-host Internet to a host-to-content one, or in other words from an end-to-end communication system to a native distribution network. This trend has attracted the attention of the research community, which has argued that content, instead of end-points, must be at the center stage of attention. These efforts promise, among other things, more flexibility in adapting to new services, efficiency improvements on lower layers, and native multicast support. Given this emergence of information-centric solutions, the relevant management needs in termsof performance have not been adequately addressed, yet they are absolutely essential for relevant network operations and crucial for the information-centric approaches to succeed. Performance management and traffic engineering approaches are also required to control routing, to configure the logic for replacement policies in cache stores and to control decisions where to cache, for instance. Therefore, there is an urgent need to manage information-centric resources and in fact to constitute their missing management and control plane which is essential for their success as clean-slate technologies. In this thesis we aim to provide solutions to crucial problems that remain, such as the management of information-centric approaches which has not yet been addressed, focusing on the key aspect of route and cache management. Our main goal is to investigate and develop key network management functions for information-centric approaches related to route and cache management. Particularly, we have developed mechanisms that manage the routing processes by influencing the forwarding of interest/subscription packets and make caching decisions about where and which item to cache as well as influence the cache replacement policies. The aim is to improve the operations and overall utility of the network through extensive and novel usage of caching as an inherent architectural function. Both opportunistic in-network and service-specific managed caching (CDN-like replication) is of interest in addressing this challenge. We have also devised a set of caching solutions, evaluated through proper analytical models that not only dramatically improve the overall utility but also demonstrate the further potential of the architectural paradigm of information-centrism. In more details, we initially describe a three phase framework as a contribution to the problem of information replication. The objective of the proposed framework is to minimize the total traffic load in the network subject to installing a predefined number of replication devices, and given that each device has storage limitations. Particularly, we present and evaluate a new algorithm for the selection of the location in the network to install replication devices. We also propose two alternative off-line mechanisms for the assignment of the replicas of each information item among the selected replications devices. We also propose a distributed cache management architecture that dynamically (re-)assigns information items to caches in order to minimize the overall network traffic cost imposed by the user requests. In particular, we derive four distributed on-line intra-domain cache management algorithms, categorize them according to the level of cooperation needed and compare them in terms of performance, complexity, message overhead and convergence time. We derive also a lower bound of the overall network traffic cost for a certain class of network topologies and show that the proposed cache management algorithms perform closely to the derived lower bound. We also present and decompose an in-network opportunistic caching framework in a set of basic policies, present at each set the most known and propose an information-centric policy at each one of them. We further propose a stochastic model that captures the dynamics of the newly proposed policies and describe a prototype implementation of the proposed opportunistic caching mechanism which is also evaluated through Planetlab experiments. Moreover, we present an enhancement of the opportunistic caching mechanism to enable client mobility. Finally, we propose a new cache aware intra-domain routing scheme that dynamically computes the routes followed by each interest/subscription for each item and from each node in the network. Particularly, we present a dynamic programming (DP) approach for the computation of the minimum transportation cost paths based on the observed item request patterns in order to minimize the overall transportation cost imposed by the user requests.

Η διαδικασία διανομής περιεχομένου στο Διαδίκτυο τοποθετεί τους παρόχους περιεχομένου σε δεσπόζουσα θέση, με την παράδοση του περιεχομένου να συμβαίνει μεταξύ δύο τελικών σημείων, δηλαδή, από τους παρόχους περιεχομένου στους καταναλωτές. Αυτό το μοντέλο οδηγείται από το υποκείμενο παράδειγμα δρομολόγησης του Διαδικτύου, δηλαδή της μεταφοράς πακέτων δεδομένων από το ένα τελικό σημείο στο άλλο. Αυτό το βασισμένο στην περιοχή (location-centric) μοντέλο περιορίζει τη δυνατότητα να αξιοποιηθούν πλήρως οι πόροι που είναι διαθέσιμοι κατά μήκος της διαδρομής από τον πάροχο στον καταναλωτή, όπως για παράδειγμα η προσωρινή δυνατότητα αποθήκευσης (caching). Τα δίκτυα που οργανώνονται με βάση το περιεχόμενο (Information-Centric Networks, ICN) έχουν προταθεί ως μια εναλλακτική της host-to-host επικοινωνίας σε μια host-to-content μορφή επικοινωνίας, ή με άλλα λόγια από την άκρο σε άκρο μορφή επικοινωνίας σε έναν εγγενή δίκτυο διανομής περιεχομένου. Η τάση αυτή έχει προσελκύσει την προσοχή της ερευνητικής κοινότητας, η οποία υποστηρίζει ότι το περιεχόμενο, αντί των τελικών σημείων, πρέπει να είναι στο επίκεντρο της προσοχής. Οι προσπάθειες αυτές υπόσχονται, μεταξύ άλλων, μεγαλύτερη ευελιξία για την προσαρμογή στις νέες υπηρεσίες, βελτίωση της απόδοσης στα κατώτερα στρώματα του δικτύου, και εγγενή υποστήριξη πολλαπλής διανομής (multicast). Με δεδομένη την εμφάνιση ICN λύσεων, οι σχετικές ανάγκες διαχείρισης όσον αφορά τις επιδόσεις δεν έχουν επαρκώς οριστεί, παρά το γεγονός ότι είναι απολύτως απαραίτητες για την σχετική λειτουργία του δικτύου και ζωτικής σημασίας για την επιτυχία των ICN προσεγγίσεων. Η έννοια της ροής, για παράδειγμα, είναι εντελώς διαφορετική στα ICN δίκτυα σε σύγκριση με το IP δίκτυο και θεμελιώδης έρευνα είναι αναγκαία, ώστε να γνωρίζουμε πώς χρησιμοποιείται το δίκτυο. Οι διάφορες προσεγγίσεις για την διαχείριση των επιδόσεων και της κυκλοφορίας οφείλουν για παράδειγμα να ελέγξουν τη δρομολόγηση, να ρυθμίσουν τη λογική των πολιτικών αντικατάστασης στις προσωρινές μονάδες αποθήκευσης και να ελέγξουν που αποθηκεύεται κάθε στοιχείο πληροφορίας. Ως εκ τούτου, υπάρχει επείγουσα ανάγκη για τη διαχείριση των πόρων των ICN δικτύων και στην πραγματικότητα να σχηματιστεί το επίπεδο διαχείρισης και το επίπεδο ελέγχου τα οποία είναι απαραίτητη για την επιτυχία του ως μια νέα μορφή τεχνολογίας. Η παρούσα εργασία στοχεύει να δώσει λύσεις σε κρίσιμα προβλήματα που παραμένουν, όπως η διαχείριση των ICN δικτύων η οποία δεν έχει ακόμη αντιμετωπιστεί, με επίκεντρο τα βασικά χαρακτηριστικά της διαχείρισης της δρομολόγησης και των τεχνικών προσωρινής αποθήκευσης. Ο κύριος στόχος μας είναι να διερευνήσουμε και να αναπτύξουμε βασικές λειτουργίες διαχείρισης των ICN δικτύων που σχετίζονται με τη δρομολόγηση και τη διαχείριση της προσωρινής αποθήκευσης. Συγκεκριμένα, έχουμε αναπτύξει μηχανισμούς που διαχειρίζονται τις διαδικασίες δρομολόγησης επηρεάζοντας τη διαβίβαση των interest/subscription πακέτων και παίρνουν αποφάσεις για το πού και ποιο κομμάτι πληροφορίας θα αποθηκευτεί στην προσωρινή μνήμη (cache), ενώ επίσης επηρεάζουν τις πολιτικές αντικατάστασης σε αυτή. Ο στόχος είναι να βελτιωθεί η λειτουργία και η συνολική χρησιμότητα των ICN αρχιτεκτονικών μέσα από τη χρήση της προσωρινής αποθήκευσης ως εγγενής αρχιτεκτονική λειτουργία. Τόσο ευκαιριακές μορφές προσωρινής αποθήκευσης όσο και υπηρεσίες διατήρησης αντιγράφων (CDN-like replication) εξετάζονται για την αντιμετώπιση αυτής της πρόκλησης. Έχουμε επινοήσει επίσης ένα σύνολο μηχανισμών προσωρινής αποθήκευσης, τους οποίους αξιολογούμαι μέσω κατάλληλων αναλυτικών μοντέλων, και οι οποίοι όχι μόνο βελτιώνουν σημαντικά τη συνολική ωφέλεια του δικτύου, αλλά και αποδεικνύουν την περαιτέρω δυναμική της συγκεκριμένης αρχιτεκτονικής που βασίζεται στο περιεχόμενο της πληροφορίας. Αρχικά περιγράφουμε ένα πλαίσιο τριών φάσεων ως συμβολή στο πρόβλημα της αντιγραφής πληροφοριών στα ICN (replication) δίκτυα. Ο στόχος του προτεινόμενου πλαισίου είναι να ελαχιστοποιηθεί το συνολικό φορτίο της κυκλοφορίας στο δίκτυο μέσα από την εγκατάσταση ενός προκαθορισμένου αριθμού συσκευών αντιγραφής, και δεδομένου ότι κάθε συσκευή έχει πεπερασμένη δυνατότητα αποθήκευσης. Συγκεκριμένα, παρουσιάζουμε και αξιολογούμε ένα νέο αλγόριθμο για την επιλογή των θέσεων του δικτύου για την εγκατάσταση των συσκευών αντιγραφής. Επίσης προτείνουμε δύο εναλλακτικούς off-line μηχανισμούς για την εκχώρηση των αντιγράφων κάθε στοιχείου πληροφορίας μεταξύ των επιλεγμένων συσκευών αντιγραφής. Προτείνουμε επίσης μια κατανεμημένη αρχιτεκτονική διαχείρισης των αντιγράφων της πληροφορίας που δυναμικά αναθέτει/αλλάζει τα αποθηκευμένα αντίγραφα, προκειμένου να ελαχιστοποιηθεί το συνολικό κόστος της κυκλοφορίας του δικτύου που προκύπτει από τα αιτήματα των χρηστών. Συγκεκριμένα, προτείνουμε τέσσερις κατανεμημένους on-line αλγορίθμους διαχείρισης μνήμης, τους κατηγοριοποιούμαι ανάλογα με το επίπεδο συνεργασίας που απαιτούν μεταξύ των κόμβων του δικτύου και τους συγκρίνουμε με βάση την απόδοση τους, την πολυπλοκότητα τους καθώς και τον χρόνος σύγκλισης. Επίσης υπολογίζουμε το κάτω όριο του συνολικού κόστους της κυκλοφορίας του δικτύου για μια ορισμένη κατηγορία τοπολογιών δικτύου και δείχνουμε ότι οι προτεινόμενοι αλγόριθμοι διαχείρισης των αντιγράφων της πληροφορίας αποδίδουν πολύ κοντά σε αυτό το κάτω όριο. Παρουσιάζουμε και αποσυνθέτουμε ένα πλαίσιο ευκαιριακής προσωρινής αποθήκευσης σε ένα σύνολο βασικών πολιτικών, παρουσιάζουμε σε κάθε υποσύνολο τις πιο γνωστές πολιτικές και προτείνουμε μια ICN πολιτική σε κάθε ένα από αυτά τα υποσύνολα. Παρουσιάζουμε επίσης ένα στοχαστικό μοντέλο που αποτυπώνει τη δυναμική των νέων προτεινόμενων πολιτικών και περιγράφουμε μια υλοποίηση του προτεινόμενου ευκαιριακού μηχανισμού αποθήκευσης τον οποίο αξιολογούμε πειραματικά στο πειραματικό δίκτυο PlanetLab. Επιπλέον προτείνουμε ένα νέο μηχανισμό δρομολόγησης που λαμβάνει υπόψη τις δυνατότητες της ευκαιριακής προσωρινής αποθήκευσης των κόμβων του δικτύου. Συγκεκριμένα παρουσιάζουμε έναν αλγόριθμο δυναμικού προγραμματισμού (DP) για τον υπολογισμό των διαδρομών ελάχιστου κόστους με βάση τα παρατηρούμενα μοτίβα που ακολουθούν οι επιθυμίες των χρηστών προκειμένου να ελαχιστοποιηθεί το συνολικό κόστος μεταφοράς της πληροφορίας στο δίκτυο που επιβάλλεται από τα αιτήματα τους.