Congestion control algorithms for background data transfers of minimal delay impact

Abstract

The thesis introduces congestion control algorithms for background data transfers which account for their impact on the average delay of the coexisting interactive traffic. The latter refers to flows associated with the transmission of delay-sensitive data, for which the instantaneous throughput is important. The former are indifferent to temporal throughput variations, provided some average performance guarantee. The model includes also long-lived (persistent) volume flows which (as the interactive) are out of the designer’s control. The proposed algorithms are motivated by means of two optimization problems, both capturing the pre-described time diversity. The resulting capacity allocations provide suitable incentive to background users for their adoption.The first considers long-lived background flows such as those for the Operating Systems updates. It determines their long-term throughput, while accounting the negative externalities of this magnitude on the average download times of interactive traffic. Two objective variations are formulated, which guarantee for the background users equal average throughput with the incumbent TCP, in the case of capacity scarcity or abundance respectively. Additionally, two implementation alternatives are explored for the optimal solution identification. The second considers dynamically arriving requests for background micro-files, modelling the case of cache updates. It aims to minimize the average delay of interactive traffic, while providing the desired average throughput for the background that serves the arriving demand. A set of optimal solutions is presented, under various assumptions on the level of available information and the considered network topology. The corresponding application-level congestion control algorithms implement the optimal solutions based only on end-to-end measurements and achieve significant improvement of the interactive delay. A common attribute of great importance for all algorithms, is the fact that they do not require any modifications on either the network or the transport layer of the existing internet infrastructure. For their theoretical comparative analysis, a Markovian methodology is followed. Flow-level simulated experiments provide further insights of their performance with respect to multiple parameters of the traffic mixture. Finally, packet-level experiments capture their performance in more detail, validate the theoretical results and evaluate the approaches proposed by related work.

Η διατριβή εισαγάγει αλγορίθμους ελέγχου συμφόρησης για την μετάδοση δεδομένων «φόντου», οι οποίοι έχουν τον ελάχιστο αντίκτυπο στην χρονική διάρκεια μετάδοσης δια-δραστικών δεδομένων. Τα δεύτερα σχετίζονται με εφαρμογές πραγματικού χρόνου, ευαίσθητες στην καθυστέρηση, για τις οποίες ο στιγμιαίος ρυθμός μετάδοσης είναι σημαντικός. Τα πρώτα εξυπηρετούν εφαρμογές που παρουσιάζουν χρονική ευελιξία ως προς την μετάδοση των δεδομένων τους. Σαν αποτέλεσμα οι αλγόριθμοι μετατοπίζουν χρονικά την μετάδοση του κύριου όγκου των δεδομένων φόντου σε στιγμές όπου η ζήτηση για δια-δραστικά είναι μειωμένη. Μία σημαντική διαφορά με την σχετική βιβλιογραφία, είναι ότι οι αλγόριθμοι ελέγχουν μόνο ένα μέρος από τα δεδομένα φόντου, ενώ τα υπόλοιπα όπως και τα δια-δραστικά θεωρούνται έξω από το πεδίο σχεδιασμού τους.Οι προτεινόμενοι αλγόριθμοι υποστηρίζονται από δύο προβλήματα βελτιστοποίησης τα οποία συμπεριλαμβάνουν την προαναφερθείσα χρονική διαφοροποίηση και καθορίζουν την κατανομή των πόρων μετάδοσης μεταξύ των διαφορετικών τύπων δεδομένων. Η εν λόγω κατανομή παρέχει κατάλληλα κίνητρα στους χρήστες δεδομένων φόντου ώστε να υιοθετήσουν τους αλγορίθμους.Το πρώτο πρόβλημα θεωρεί αρχεία φόντου μεγάλου μεγέθους, όπως αυτά για την ανανέωση των λειτουργικών συστημάτων. Καθορίζει τον μέσο ρυθμό μετάδοσής τους, συνυπολογίζοντας τον αντίκτυπο αυτού του μεγέθους στην χρονική διάρκεια μετάδοσης των δια-δραστικών δεδομένων. Δύο παραλλαγές της αντικειμενικής συνάρτησης διασφαλίζουν ίσο μέσο ρυθμό μετάδοσης με τον τωρινό εν λειτουργία αλγόριθμο (TCP), υπό συνθήκες όπου οι πόροι μετάδοσης είναι σε αφθονία ή σπανιότητα αντίστοιχα. Επιπλέον, δύο υλοποιήσεις προτείνονται και διερευνώνται ως προς την εύρεση της βέλτιστης λύσης. Το δεύτερο πρόβλημα θεωρεί δυναμικές αφίξεις αιτημάτων για την μετάδοση αρχείων φόντου μικρού μεγέθους, και μοντελοποιεί την ανανέωση του περιεχομένου σε μέσα αποθήκευσης κοντά στους χρήστες (cache update). Αντικειμενικός του στόχος είναι να ελαχιστοποιήσει τον μέσο χρόνο μετάδοσης των δια-δραστικών δεδομένων, ενώ παράλληλα να παρέχει τον απαραίτητο μέσο ρυθμό μετάδοσης στα δεδομένα φόντου που είναι ικανός να εξυπηρετήσει τον φόρτο τους. Η διατριβή παρουσιάζει ένα σύνολο από βέλτιστες λύσεις, ανάλογα με το επίπεδο πληροφορίας που είναι διαθέσιμο και την δικτυακή τοπολογία. Οι αντίστοιχοι αλγόριθμοι που υλοποιούν αυτές τις λύσεις είναι συμβατοί με την υπάρχουσα διαδικτυακή υποδομή, και πετυχαίνουν σημαντική μείωση του χρόνου μετάδοσης των δια-δραστικών αρχείων. Η διατριβή βασίζεται στην θεωρία Μάρκοφ για την θεμελίωση των βασικών ιδιοτήτων των αλγορίθμων. Επίσης, περιλαμβάνει προσομοιωμένα πειράματα σε επίπεδο ροής που προσφέρουν επιπλέον γνώση για την συμπεριφορά τους σε συνάρτηση με ποικίλες παραμέτρους του δικτύου. Τέλος, παρουσιάζει τα αποτελέσματα πειραμάτων σε επίπεδο πακέτου, τα οποία συμπεριλαμβάνουν τις λεπτομέρειες του δικτύου, σκοπεύοντας στην πιο αναλυτική αξιολόγηση των αλγορίθμων και την σύγκρισή τους με προτεινόμενους από την σχετική βιβλιογραφία.