Αποδοτικοί Αλγόριθμοι Σχεδίασης Δικτύων Επικοινωνιών Με Έμφαση Στην Ποιότητα Υπηρεσίας

Abstract

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