Κατανεμημένη βελτιστοποίηση δικτυακών συστημάτων διομότιμης αρχιτεκτονικής σύγχρονου διαμοιρασμού βίντεο πραγματικού χρόνου

Abstract

Peer to peer live streaming is a network application where peers (users) contribute their upload bandwidth for the real time distribution of a video stream. The objective of this work is the optimization of this data diffusion with a distributed and self-organized architecture. Peers have heterogeneous and dynamic uploading bandwidth. This fact combined with the characteristics of the topology of the underlying network and the dynamic traffic conditions e.g. latency create a volatile and complex environment for P2P live streaming delivery which strongly affect the success of a P2P system measured by a number of performance metrics. The first important factor is the uploading bandwidth utilization that corresponds to the ability of the system to exploit as much as possible of the overall uploading bandwidth of the participating peers. The maximization of the upload bandwidth utilization increases the video playback delivery rate and ensures the stability of the distribution. Equally important parameter is the setup time defined as the time interval between the generation of a block from an origin server and its delivery to every peer in the system. Furthermore a P2P live streaming system has to remain stable and its delivery rate must remain high in a dynamic environment where peers arrive and depart randomly. Finally, fairness among nodes indicates the ability of the system to distribute continuously and uniformly the aggregate uploading bandwidth to the participating peers. This ensures that every peer will acquire a percentage of blocks above a critical threshold for an affordable video playback regardless the aggregate uploading bandwidth is not sufficient for the complete delivery of the video stream. For the development of the proposed system is required the creation of a content diffusion overlay (CDO). For every peer CDO defines the graph which includes the subset of adjacent participating peers (neighbors) that are connected with it. The optimization of the CDO and the fulfillment of the technical objectives is done with the use of a distributed optimization and maintenance algorithm (DOMA) that reorganizes the neighborhoods of CDO and so it keeps almost stable the attributes of the graph during peer arrivals and departures. It also ensures the high levels of bandwidth utilization. The algorithm based on a cost function denoted as energy function between two nodes and can represent for example the network latency between two nodes DOMA is executed between two neighbors that we note as initiators and their neighbors that we called satellites. Its purpose is to minimize the sum of the energy functions between initiators and satellites under the constraints on the number of neighbors that the graph structure implies. In p2p live streaming every user and/or content provider that generates a multimedia block stream is indicated as source. A P2P block exchange scheduling algorithm (P2P BESA) is also developed and it ensures the distribution of each block to every user and with low latency. The decision for the transmission of a block is done in three phases. In the first phase every peer acting as block sender issues tokens periodically proportional with its upload bandwidth. This ensures the maximization of the upload bandwidth of the participating peers and determines the data flows between participating peers. In the second phase each peer periodically is acting as receiver and requests a different block from each one of its potential senders. As potential senders we define the set of peers that have recently sent a token to it. This algorithm ensures the fast and complete diffusion of every block by also minimizing the idle bandwidth resources in the systems. Finally in the third phase before the transmission of each block each sender selects the destination peer according to the blocks that it misses and its upload bandwidth capabilities.

Η διδακτορική διατριβή έχει τίτλο «Κατανεμημένη βελτιστοποίηση δικτυακών συστημάτων διομότιμης αρχιτεκτονικής συγχρόνου διαμοιρασμού βίντεο πραγματικού χρόνου». Με τον όρο κατανεμημένη βελτιστοποίηση εκφράζεται η βελτιστοποίηση στα δικτυακά συστήματα όπου η συγκέντρωση των δεδομένων για τη διαχείριση και για τη λειτουργία υψηλής απόδοσης δεν γίνεται μέσω κάποιας κεντρικής οντότητας διαχείρισης στην οποία όλοι οι συμμετέχοντες κόμβοι αποστέλλουν τα απαραίτητα δεδομένα. Αντιθέτως κάθε κόμβος συλλέγει το «απαραίτητο» υποσύνολο των δεδομένων και λαμβάνει δυναμικά αποφάσεις για τη βέλτιστη λειτουργία ενός υποσυνόλου του όλου συστήματος. Διομότιμα ονομάζονται τα συστήματα όπου χωρίς να υπάρχει κάποιας μορφής ιεραρχία οι συμμετέχοντες κόμβοι οργανώνονται με σκοπό την παροχή μιας υπηρεσίας εφαρμογής και χρησιμοποιούν τους δικούς τους δικτυακούς υπολογιστικούς και αποθηκευτικούς πόρους τους οποίους αυτό διαχειρίζονται για την επίτευξη του σκοπού αυτού. Τέλος, ως σύγχρονος διαμοιρασμός βίντεο πραγματικού χρόνου ορίζεται η εφαρμογή κατά την οποία ένα αντικείμενο πολυμέσων που δημιουργείται σε πραγματικό χρόνο σε ένα σημείο του δικτύου διαμοιράζεται επίσης σε πραγματικό χρόνο στους συμμετέχοντες κόμβους. Περιληπτικά, στη συγκεκριμένη διδακτορική διατριβή μελετήθηκαν οι θεωρίες της βελτιστοποίησης και των κατανεμημένων αλγορίθμων με σκοπό την χρήση τους σε ένα διομότιμο σύστημα σύγχρονου διαμοιρασμού αντικείμενων. Επιπλέον, μελετήθηκε το περιβάλλον και οι συνθήκες λειτουργίας ενός τέτοιου συστήματος καθώς και τα χαρακτηριστικά του. Αποτέλεσμα της μελέτης αυτής είναι η εξαγωγή συμπερασμάτων σχετικά με τις απαιτήσεις που πρέπει να πληρούνται κατά τη δημιουργία ενός διομότιμου συστήματος συγχρόνου διαμοιρασμού αντικείμενων και οι τεχνικοί στόχοι που πρέπει αυτό να ικανοποιεί. Με αυτά τα κριτήρια σχεδιάστηκε η αρχιτεκτονική του συστήματος και ορίστηκαν τα προβλήματα που πρέπει να επιλυθούν. Για την λειτουργία ενός τέτοιου συστήματος ορίστηκαν οι ακόλουθες απαιτήσεις • Μεγιστοποίηση της χρήσης από το σύστημα του διαθέσιμου εύρους ζώνης των συμμετεχόντων κόμβων. Φυσικά οι κόμβοι έχουν ετερογενείς τιμές του διαθέσιμου εύρους ζώνης και μάλιστα με μεγάλη διασπορά • Ελαχιστοποίηση της καθυστέρησης από τη στιγμή δημιουργίας ενός αντικείμενου μέχρι τον διαμοιρασμό του σε κάθε συμμετέχοντα κόμβο • Ομοιόμορφη διαρκής κατανομή του συνολικού εύρους ζώνης του συστήματος στους συμμετέχοντες κόμβους • Ανεκτικότητα του συστήματος στη δυναμική συμπεριφορά των χρηστών που προκαλείται από εισόδους και εξόδους των χρηστών στο σύστημα σε μη προκαθορισμένες χρονικές στιγμές • Ικανότητα κλιμάκωσης του συστήματος σε αριθμό συμμετεχόντων χρηστών κάτι που επάγει την κατανεμημένη διαχείριση του συστήματος • Προσαρμογή του σχεδιαζόμενου συστήματος στην κίνηση του δικτύου στο οποίο αυτό επικάθεται και ανεκτικότητα του στις μεταβολές του εύρους ζώνης των συμμετεχόντων κόμβων • Ελαχιστοποίηση του φορτίου το οποίο εισάγει η λειτουργία του συστήματος στο δίκτυο.