Προσαρμοστικός έλεγχος συμφόρησης και δικαιοσύνης σε δίκτυα υπολογιστών

Abstract

The expansion and growth of traffic in packet-switching networks, have established congestion control as a highly significant unit within network design. The congestion control mechanisms in the Internet, consist of a source algorithm that dynamically adjusts source rates and a link algorithm that updates a certain congestion measure at each link and feeds it back to the sources. To solve the issue, Reno which adapts heuristically to packet loss probability, was initially proposed. Simulations studies have demonstrated that it may be ill-suited for networks with large bandwidth-delay product. Research on the theoretical understanding of TCP congestion control, lead to the development of primal - dual algorithms, analyzed via an optimization based framework, which generalize the Additive Increase - Multiplicative Decrease congestion avoidance strategy, to large-scale networks. The introduction of new types of Internet services that require strict quality criteria, silently imply the existence of control algorithms capable of regulating the round trip time, avoiding either overflow or empty queues, while guaranteing fairness among sources. Control theoretic approaches implemented as congestion controllers in the routers, may be found in where local stability around an equilibrium is addressed, since linearized versions of the fluid flow model and queue dynamics are considered. Furthermore, owing to their implementation on the links, the total number of computations performed due to congestion control, should be kept to a minimum. The practical assumption that link algorithms are unavailable to the designer, lead alternatively to the design of congestion controllers operating in the source. However, certain key questions need to be carefully addressed, prior to implementation. Specifically: a) a model for the plant has to be devised, otherwise stability analysis is impossible; b) determining a desired and feasible system performance is a non-trivial task, owing to the highly uncertain and dynamically varying nature of the Internet; c) the controlled system should not be only stable, but additionally robustly stable against modeling imperfections, exogenous disturbances, delays and errors in interpreting the network produced congestion signals; d) the output of any proposed control scheme should be saturated. Fortunately, in the source control theoretic approaches, the simplicity constraint is relaxed. The thesis proposes a Neural Network Rate Control theoretic framework, addressing all four aforementioned key questions. It was comprised: i) an on-line desired round trip estimator, whose main objective was to output reliable, piecewise constant predictions of feasible round trip times; ii) an adaptive and saturated transmission rate controller, capable of robustly tracking the desired round trip time; iii) an adaptive and saturated number of communication channels controller, capable of achieving fairness in allocating network resources among competing sources at equilibrium; iv) a future path congestion level estimator. The notion of parallel operating communication channels was introduced in order to improve the throughput of the network. It was clearly shown that regulating round trip time to follow a piecewise constant profile, is equivalent to queueing delay and queue length regulation around a piecewise constant profile. Moreover, the resulted scheme still achieves small enough queues at equilibrium, to prevent large queueing delays and congestion collapse, though not zero to avoid link starvation.

Η επέκταση και η αύξηση της κυκλοφορίας του Διαδικτύου, έχουν καθιερώσει τον έλεγχο συμφόρησης ως ιδιαίτερα σημαντική μονάδα της σχεδίασης της λειτουργίας των δικτύων. Οι μηχανισμοί ελέγχου συμφόρησης, αποτελούνται από έναν αλγόριθμο ελέγχου, ο οποίος εκτελείται στην πηγή και προσαρμόζει δυναμικά τον ρυθμό μετάδοσης και έναν αλγόριθμο που εκτελείται στην σύνδεση και ενημερώνει μια μέτρηση της συμφόρησής της και την οποία στέλνει στις πηγές που την χρησιμοποιούν. Για την επίλυση του προβλήματος της συμφόρησης, αρχικά προτάθηκε το Reno που προσαρμόζει τον ρυθμό της πηγής σύμφωνα με την πιθανότητα απώλειας πακέτου. Προσομοιώσεις έχουν δείξει ότι είναι ακατάλληλο για δίκτυα με μεγάλο εύρος ζώνης. Η έρευνα για την θεωρητική κατανόηση του ελέγχου συμφόρησης στο TCP, οδήγησε στην ανάπτυξη δυικών αλγορίθμων, η ανάλυση των οποίων βασίζεται σε τεχνικές βελτιστοποίησης. Η εισαγωγή νέων τύπων υπηρεσιών Διαδικτύου που απαιτούν αυστηρά κριτήρια ποιότητας, συνεπάγεται την ύπαρξη αλγορίθμων ελέγχου ικανών να ρυθμίσουν τον χρόνο πλήρους περιφοράς πακέτου, αποφεύγοντας είτε υπερχειλισμένες είτε κενές ουρές αναμονής, ενώ εξασφαλίζουν την δικαιοσύνη μεταξύ των πηγών. Οι θεωρητικές προσεγγίσεις ελέγχου, οδήγησαν σε ελεγκτές συμφόρησης που εφαρμόζονται στις συνδέσεις, οι οποίοι όπως έχει αποδειχθεί παρουσιάζουν τοπική ευστάθεια γύρω από το σημείο ισορροπίας. Δεδομένου ότι εκτελούνται στις συνδέσεις, ο συνολικός αριθμός των υπολογισμών που εκτελούνται για τον έλεγχο της κυκλοφοριακής συμφόρησης, πρέπει να περιοριστεί στο ελάχιστο. Η λογική υπόθεση ότι οι αλγόριθμοι σύνδεσης δεν είναι διαθέσιμοι στον σχεδιαστή, οδήγησε εναλλακτικά στο σχεδιασμό ελεγκτών συμφόρησης πηγής. Ωστόσο, πριν από την εφαρμογή πρέπει να διευθετηθούν: 1) να σχεδιαστεί ένα μοντέλο της ελεγχόμενης διεργασίας, διαφορετικά είναι αδύνατη η ανάλυση ευστάθειας για μεγάλες μεταβολές, 2) ο καθορισμός μιας επιθυμητής αλλά και εφικτής απόδοσης του συστήματος δεν είναι μια απλή διαδικασία, λόγω της υψηλής αβεβαιότητας και δυναμικής φύσης του Διαδικτύου, 3) το ελεγχόμενο σύστημα δεν πρέπει να είναι μόνο ευσταθές, αλλά εύρωστα ευσταθές αναφορικά με ατέλειες της μοντελοποίησης, εξωγενείς διαταραχές και χρονικές καθυστερήσεις, 4) η έξοδος οποιουδήποτε προτεινόμενου σχήματος ελέγχου πρέπει να κινείται εντός αυστηρά προκαθορισμένων ορίων. Ο σχεδιασμός ελεγκτών συμφόρησης που λειτουργούν στην πηγή, δεν υπόκειται σε κανένα περιορισμό διατήρησης απλότητας. Το προσαρμοστικό σύστημα ελέγχου που προτείνει η διατριβή, αντιμετωπίζει και τα τέσσερα προαναφερθέντα βασικά ερωτήματα. Η δομή του αποτελείται από τέσσερις μονάδες: 1) εκτιμητή του επιθυμητού χρόνου πλήρους περιφοράς πακέτου, ο κύριος στόχος του οποίου είναι η παραγωγή αξιόπιστων και σταθερών κατά διαστήματα προβλέψεων του εφικτού χρόνου πλήρους περιφοράς πακέτου, 2) προσαρμοστικό ελεγκτή του ρυθμού μετάδοσης, με την έξοδό του να κινείται εντός αυστηρά προκαθορισμένων ορίων, ικανού να εξασφαλίσει ότι ο χρόνος πλήρους περιφοράς πακέτου κινείται σε μια μικρή γειτονιά του σήματος αναφοράς, που παρέχεται από την πρώτη μονάδα, 3) προσαρμοστικό ελεγκτή του αριθμού των καναλιών, με την έξοδό του να κινείται εντός αυστηρά προκαθορισμένων ορίων, ικανού να εξασφαλίσει δικαιοσύνη στο διαμοιρασμό των πόρων του δικτύου μεταξύ των ανταγωνιστικών πηγών στο σημείο ισορροπίας, 4) εκτιμητή του μελλοντικού επιπέδου συμφόρησης της διαδρομής. Η εισαγωγή των καναλιών επικοινωνίας γίνεται με στόχο την βελτίωση της ρυθμοαπόδοσης του δικτύου. Επιπλέον, το σύστημα επιτυγχάνει αρκετά μικρές ουρές αναμονής στο σημείο ισορροπίας, ώστε να αποφευχθούν μεγάλες καθυστερήσεις και καταστάσεις κατάρρευσης, αλλά και μη μηδενικές ώστε να αποφευχθεί η υπολειτουργία του δικτύου.