Ανάπτυξη Αλγορίθμων Εύρεσης Διαδρομών Σε Δίκτυα Πολλών Διαχειριστικών Περιοχών

Abstract

Βασικό κομμάτι στα προσανατολισμένα προς σύνδεση δίκτυα υψηλής ταχύτητας είναι η δυνατότητα τους να προσδιορίζουν ανθεκτικές συνδέσεις ώστε να καλύπτουν τις απαιτήσεις των χρηστών, διασχίζοντας διαφορετικές διαχειριστικές περιοχές. Οι αλγόριθμοι εύρεσης ανεξάρτητων διαδρομών οφείλουν να λάβουν υπ’ όψιν τους τις ανεπάρκειες των πρωτοκόλλων δρομολόγησης διά-περιοχών καθώς και την απροθυμία των διαχειριστών κάθε περιοχής να διαφημίσουν τη λεπτομερή εσωτερική δομή τους.Σε αυτή την εργασία προτείνουμε ένα μετρικό, τον δείκτη επικάλυψης ο οποίος ποσολογεί την επικάλυψη των διαδρομών οι οποίες περνούν μέσω δύο οποιονδήποτε ζευγαριών κόμβων συνόρων της ίδιας περιοχής, χωρίς να εκθέτει τις εσωτερικές λεπτομέρειες της περιοχής. Βασιζόμενοι στην έννοια αυτού του δείκτη, εισάγουμε μια τεχνική συνάθροισης τοπολογίας και έναν αλγόριθμο εύρεσης ανεξάρτητων διαδρομών σε δίκτυα πολλών διαχειριστικών περιοχών, με σκοπό την ανίχνευση ανθεκτικών συνδέσεων με κριτήριο τη διαθέσιμη χωρητικότητα. Η χρήση αυτής της μεθόδου, την οποία ονομάζουμε Full Mesh with Overlap Factor, εξασφαλίζει ότι οι προσδιορισμένες διαδρομές (α) αντιστοιχούν σε εφικτά και πραγματοποιήσιμα ανεξάρτητα ζεύγη διαδρομών διά-μέσου πολλών διαχειριστικών περιοχών. (β) έχουν πραγματικό ελάχιστο bandwidth μεγαλύτερο ή ίσο από την εκτίμηση που υπολογίζεται από τον αλγόριθμό μας. Εκτενείς προσομοιώσεις επιβεβαιώνουν ότι η μέθοδος Full Mesh with OF προσδιορίζει κατάλληλα ζευγάρια διαδρομών με υψηλή αναλογία επιτυχίας, βελτιώνοντας πολύ τις απλούστερες μεθόδους συνάθροισης, χωρίς να αυξάνει την πολυπλοκότητα υπολογισμού των διαδρομών και με την ελάχιστη ανταλλαγή πληροφοριών μεταξύ των διαφόρων περιοχών.