Εφαρμογή θεωρίας αλγορίθμων στο διαδίκτυο

Abstract

A linked decomposition of a graph with n nodes is a set of subgraphs covering the n nodes such that all pairs of subgraphs intersect; we seek linked decompositions such that all subgraphs have about square of root of n vertices, logarithmic diameter, and each vertex of the graph belongs to either one or two subgraphs. A linked decomposition enables many control and management functions to be implemented locally, such as resource sharing, maintenance of distributed directory structures, deadlock-free routing, failure recovery and load balancing, without requiring any node to maintain information about the state of the network outside the subgraphs to which it belongs. Linked decompositions also enable efficient routing schemes with small routing tables. Our main contribution is to show that ``Internet-like graphs'' (e.g. The preferential attachment model proposed by Barabasi and other similar models) have linked decompositions with the parameters described above with high probability; moreover, our experiments show that the Internet topology itself can be so decomposed. Our proof proceeds by analyzing a novel process, which we call Polya urns with the power of choice, which may be of great independent interest. In this new process, we start with n nonempty bins containing O(n) balls total, and each arriving ball is placed in the least loaded of m bins, drawn independently at random with probability proportional to load. Our analysis shows that in our new process, with high probability the bin loads become roughly balanced some time beforeO(n2+ε) further balls have arrived and stay roughly balanced, regardless of how the initial O(n) balls were distributed, where ε > 0 can be arbitrarily small, provided m is large enough. We also prove that if all bins start with at least c balls, then with high probability the bin loads become roughly balanced some time before O(n2), provided c is large enough.

Το διαδίκτυο αποτελεί το σημαντικότερο δίκτυο υπολογιστών παγκόσμιας κλίμακας με πάρα πολλές και σημαντικές εφαρμογές. Επειδή εξελίσσεται και εξαπλώνεται με γρήγορους ρυθμούς, δημιουργείται η ανάγκη εύρεσης νέων και ευέλικτων μεθόδων δρομολόγησης. Στη διατριβή προτείνουμε μια καινούρια προσέγγιση δρομολόγησης στο διαδίκτυο. Η προσέγγιση αυτή βασίζεται σε μια διαδικασία αποσύνθεσης του γραφήματος του διαδικτύου σε ένα σύνολο αλληλοεπικαλυπτόμενων υπογραφημάτων. Χαρακτηριστικό της είναι ότι οι διευθύνσεις των υπολογιστών δε χρειάζεται να εμπεριέχουν οποιαδήποτε βοηθητική ως προς τη δρομολόγηση πληροφορία. Επίσης, όταν οι αποσυνθέσεις ικανοποιούν κάποια επιθυμητά χαρακτηριστικά, τότε μπορούμε να εξασφαλίσουμε μικρή καθυστέρηση και μικρό μέγεθος πινάκων δρομολόγησης. Παρουσιάζουμε θεωρητικά αποτελέσματα για στοχαστικές διαδικασίες μοντελοποίησης του διαδικτύου, όπως αυτή του Barabasi, τα οποία αποδεικνύουν ότι μια επιθυμητή αποσύνθεση είναι εφικτή με μεγάλη πιθανότητα, γεγονός που θα επιβεβαιώσουμε και πειραματικά. Κατά την ανάλυση συνδέουμε το πρόβλημα εύρεσης επιθυμητών αποσυνθέσεων με μια παραλλαγή του προβλήματος των υδριών του Polya, στο οποίο σε κάθε βήμα επιλέγουμε ένα σύνολο από υποψήφιες υδρίες και ρίχνουμε την επόμενη μπάλα στην υδρία με το μικρότερο φόρτο. Η παραλλαγή αυτή, την οποία ονομάζουμε "Υδρίες του Polya με τη Δύναμη της Επιλογής", παρουσιάζει ανεξάρτητο ερευνητικό ενδιαφέρον. Αποδεικνύουμε, εκτός των άλλων, ότι, υπό γενικές συνθήκες, χρειάζεται σχεδόν τετραγωνικός ως προς τον αριθμό των υδριών χρόνος, για να έχουν όλες οι υδρίες παραπλήσιους φόρτους. Το αποτέλεσμα αυτό είναι ιδιαίτερα σημαντικό και είναι το κλειδί για να μεταφερθούμε στην περίπτωση εύρεσης αποσυνθέσεων σε Barabasi γραφήματα. Η προτεινόμενη αποσύνθεση εξετάζεται και σε πραγματικά στιγμιότυπα του διαδικτύου, όπως γραφήματα διασύνδεσης αυτόνομων συστημάτων. Προτείνουμε έναν ευρετικό αλγόριθμο εύρεσης αποσυνθέσεων, ο οποίος δίνει καλά αποτελέσματα στα εξεταζόμενα γραφήματα. Τέλος παραθέτουμε πειραματικά αποτελέσματα, τα οποία δείχνουν τη δυναμική της νέας προσέγγισης δρομολόγησης, όσον αφορά την πιθανή επιβάρυνση στη βέλτιστη καθυστέρηση, αλλά και κάποιες αδυναμίες, όσον αφορά τη συμφόρηση.