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

Abstract

Network planning is the use of scientific methods for optimizing the investment and for dimensioning network equipment in a unified way’ for a whole system, in order to meet realistic business objectives previously defined by the highest level authorities, according to International Telecommunication Union. The challenge of optimal planning is significantly increased in Next Generation Networks when traffic is actively segmented into different traffic classes. Utilizing Traffic Engineering along with effective optimization algorithms is the answer for network design in modem communication networks. Due to the NP-hard nature of network design problems, meta-heuristics provide a viable optimization alternative option. The dissertation focuses on the topological design and dimensioning of Layer-3 communication networks with Quality of Service considerations, utilizing particle swarm optimization. Initially, an instance of a real telecommunication best-effort network design problem is considered as a single objective optimization problem using two variations of Particle Swarm Optimization. Their effectiveness on solving the aforementioned problem is checked against the application of a genetic algorithm. The problem under consideration is expanded with Quality of Service constraints (i.e. delay). It is formulated as a bi-criteria optimization problem, where multi objective Particle Swarm Optimization is utilized as the optimization technique. Finally, the design of multiclass - tree-like distribution networks is considered. The target is to minimize network deployment cost and end-to-end delay in the network per traffic class, subject to pre-defined bounds. This is presented as two separate problems; i. a scheduling design and verification problem and ii. a topological design problem extended by including the scheduling configuration parameters in the optimization process. Whereas in literature mostly Priority Queuing systems have been considered in design efforts as such, the current work extends the problem by adopting class based weighted fair queuing with low latency queue as the scheduling policy. The choice of the scheduler for a multi-service communication network is validated by simulation of indicative distribution/aggregation broadband architecture. The topological design problem is formulated as a constrained multi-objective problem and multi objective Particle Swarm Optimization is applied. Its efficiency is evaluated against Non-dominated Sorting Genetic Algorithm II.

Σύμφωνα με την Διεθνή Ένωση Τηλεπικοινωνιών η σχεδίαση δικτύου ορίζεται ως η χρήση επιστημονικών μεθόδων για τη βελτιστοποίηση της επένδυσης και την διαστασιολόγηση του δικτυακού εξοπλισμού με ενιαίο τρόπο για όλο το σύστημα, με στόχο την αντιμετώπιση πραγματικών εμπορικών στόχων προκαθορισμένων από ανώτατα διοικητικά όργανα. Οι προκλήσεις αναφορικά με τη βέλτιστη σχεδίαση στα δίκτυα επικοινωνιών επόμενης γενιάς είναι σημαντικές, λαμβάνοντας ιδιαίτερα υπόψη την κατάτμηση της δικτυακής κίνησης σε διαφορετικές κλάσεις. Ο συνδυασμός «Διαχείρισης Κίνησης» με τη χρήση αποδοτικών αλγόριθμων βελτιστοποίησης αποτελεί τη λύση στα σύνθετα προβλήματα σχεδίασης τηλεπικοινωνιακών δικτύων. Τα προβλήματα όμως σχεδίασης δικτύου, είναι συχνά ΝΡ- δύσκολα καθιστώντας τους μετά-ευρετικούς αλγόριθμους βελτιστοποίησης κατάλληλους για την εφαρμογή τους σε αυτά. Η διατριβή πραγματεύεται προβλήματα τοπολογικής σχεδίασης και διαστασιολόγησης δικτύου επικοινωνιών επιπέδου-3 με τη χρήση στοχαστικού αλγόριθμου βελτιστοποίησης σμήνους σωματιδίων, με έμφαση στην ποιότητα υπηρεσίας του δικτύου. Αρχικά παρουσιάζεται η εφαρμογή του αλγόριθμου σε πραγματικό πρόβλημα σχεδίασης δικτύου επικοινωνιών «καλύτερης προσπάθειας». Το πρόβλημα μοντελοποιείται ως πρόβλημα βελτιστοποίησης μονού στόχου ενώ δύο παραλλαγές του αλγόριθμου βελτιστοποίησης σμήνους σωματιδίων εφαρμόζονται σε αυτό. Η αποδοτικότητά τους αξιολογείται έναντι των γενετικών αλγόριθμων. Ακολούθως, το πρόβλημα υπό εξέταση επεκτείνεται με την εφαρμογή περιορισμού αναφορικά με την ποιότητα υπηρεσίας του (δηλαδή την μέση καθυστέρηση). Μοντελοποιείται ως πρόβλημα βελτιστοποίησης δύο κριτηρίων, ενώ εφαρμόζεται πολυστοχική βελτιστοποίησης σμήνους σωματιδίων. Τέλος παρουσιάζεται η τοπολογική σχεδίαση δενδρικού IP δικτύου διανομής με τη χρήση πολλαπλών κλάσεων κίνησης. Στόχο αποτελεί η ελαχιστοποίηση του κόστους ανάπτυξης του δικτύου και της καθυστέρησης από άκρο σε άκρο ανά κλάση υπηρεσίας, με περιορισμό στη μέγιστη καθυστέρηση ανά διαδρομή. Για το σκοπό αυτό παρουσιάζονται τα εξής προβλήματα: α. επιλογής και επαλήθευση της χρήσης αλγορίθμου εκπομπής πακέτου στη σχεδίαση και β. τοπολογικής σχεδίασης περιλαμβάνοντας τις παραμέτρους ρύθμισης του αλγόριθμου εκπομπής στην διαδικασία βελτιστοποίησης. Το συγκεκριμένο πρόβλημα τοπολογικής σχεδίασης στη βιβλιογραφία έχει αντιμετωπιστεί με τη χρήση αλγόριθμου εκπομπής με αυστηρές προτεραιότητες. Στην τρέχουσα διατριβή η μελέτη του προβλήματος επεκτείνεται με την εφαρμογή αλγόριθμου εκπομπής βάσει κλάσεως, δίκαιης αναμονής με βάρη και ουρά χαμηλής προτεραιότητας. Η επιλογή του αλγόριθμου εκπομπής για ένα τηλεπικοινωνιακό δίκτυο πολλαπλών υπηρεσιών επαληθεύεται με προσομοίωση της λειτουργίας ενδεικτικής ευρυζωνικής αρχιτεκτονικής δικτύου συγκέντρωσης/διανομής. Το πρόβλημα μοντελοποιείται ως πρόβλημα πολυστοχικής βελτιστοποίησης με την εφαρμογή αλγόριθμου πολυστοχικής βελτιστοποίησης σμήνους σωματιδίων. Για την παρουσίαση της αποτελεσματικότητας της μεθόδου, η αποδοτικότητά του αλγορίθμου αξιολογήθηκε έναντι του γενετικού αλγόριθμου πολυστοχικής βελτιστοποίησης μη κυριαρχούμενης ταξινόμησης-ΙΙ.