ΑΛΓΟΡΙΘΜΟΙ ΔΡΟΜΟΛΟΓΗΣΗΣ ΜΗΝΥΜΑΤΩΝ ΣΕ ΔΙΑΣΥΝΔΕΔΕΜΕΝΑ ΔΙΚΤΥΑ: ΔΡΟΜΟΛΟΓΗΣΗ ΑΠΟΚΛΙΣΗΣ ΚΑΙ ΔΡΟΜΟΛΟΓΗΣΗ ΜΑΚΡΟΜΗΝΥΜΑΤΩΝ

Abstract

Η ΔΙΔΑΚΤΟΡΙΚΗ ΑΥΤΗ ΔΙΑΤΡΙΒΗ ΑΣΧΟΛΕΙΤΑΙ ΜΕ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΔΡΟΜΟΛΟΓΗΣΗΣ ΜΗΝΥΜΑΤΩΝ ΣΕ ΠΑΡΑΛΛΗΛΟΥΣ ΥΠΟΛΟΓΙΣΤΕΣ ΚΑΙ ΕΙΔΙΚΩΤΕΡΑ ΜΕ ΔΥΟ ΔΙΑΦΟΡΕΤΙΚΕΣ ΠΟΛΙΤΙΚΕΣ, ΤΗΝ ΔΡΟΜΟΛΟΓΗΣΗ ΑΠΟΚΛΙΣΗΣ ΠΑΚΕΤΩΝ ΚΑΙ ΤΗΝ ΔΡΟΜΟΛΟΓΗΣΗ ΜΑΚΡΟΜΗΝΥΜΑΤΩΝ. ΠΡΟΤΕΙΝΕΤΑΙ ΚΑΙ ΑΝΑΛΥΕΤΑΙ ΕΝΑΣ ΝΕΟΣ ΚΑΘΑΡΑ ΑΠΛΗΣΤΟΣ ΑΛΓΟΡΙΘΜΟΣ ΔΡΟΜΟΛΟΓΗΣΗΣ ΠΑΚΕΤΩΝ ΣΕΕΝΑ ΔΙΔΙΑΣΤΑΤΟ ΠΛΕΓΜΑ. ΚΑΘΕ ΚΟΜΒΟΣ ΤΟΥ ΠΛΕΓΜΑΤΟΣ ΣΤΕΛΝΕΙ ΕΝΑ ΠΑΚΕΤΟ ΣΕ ΚΑΠΟΙΟ ΤΥΧΑΙΟ ΚΟΜΒΟ ΠΡΟΟΡΙΣΜΟΥ. ΓΙΑ ΤΗΝ ΑΝΑΛΥΣΗ ΜΕΣΗΣ ΠΕΡΙΠΤΩΣΗΣ ΥΙΟΘΕΤΕΙΤΑΙ Η ΧΡΗΣΗ ΜΙΑΣ ΣΥΝΑΡΤΗΣΗΣ ΔΥΝΑΜΙΚΟΥ. ΣΤΗΝ ΔΙΔΑΚΤΟΡΙΚΗ ΑΥΤΗ ΔΙΑΤΡΙΒΗ, ΕΠΙΣΗΣ ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΜΙΑ ΣΕΙΡΑ ΑΠΟ ΤΑ ΑΠΟΤΕΛΕΣΜΑΤΑ ΓΙΑ ΤΗΝ ΑΠΟΔΟΣΗ ΔΙΑΦΟΡΕΤΙΚΩΝ ΥΛΟΠΟΙΗΣΕΩΝΑΜΕΣΩΝ, ΑΜΝΗΜΟΝΩΝ ΑΛΓΟΡΙΘΜΩΝ ΔΡΟΜΟΛΟΓΗΣΗΣ ΜΑΚΡΟΜΗΝΥΜΑΤΩΝ ΣΕ ΕΝΑ ΔΙΔΙΑΣΤΑΤΟ ΠΛΕΓΜΑ, ΧΡΗΣΙΜΟΠΟΙΩΝΤΑΣ ΜΟΝΟΠΑΤΙΑ ΚΑΜΠΗΣ. ΓΙΑ ΤΟΝ ΣΚΟΠΟ ΑΥΤΟ ΟΙ ΑΛΓΟΡΙΘΜΟΙ ΠΡΟΣΟΜΟΙΩΝΟΝΤΑΙ ΣΤΟ ΠΕΡΙΒΑΛΛΟΝ ΜΙΑΣ ΠΡΑΓΜΑΤΙΚΗΣ ΜΗΧΑΝΗΣ. ΜΕ ΤΗΝ ΒΟΗΘΕΙΑ ΤΗΣ ΠΡΟΣΟΜΟΙΩΣΗΣ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΡΕΑΛΙΣΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ ΓΙΑ ΤΗΝ ΣΥΓΚΡΙΣΗ ΤΩΝ ΔΥΟ ΔΙΑΦΟΡΕΤΙΚΩΝ ΤΕΧΝΙΚΩΝ ΔΡΟΜΟΛΟΓΗΣΗΣ ΜΗΝΥΜΑΤΩΝ ΠΟΥ ΑΝΑΦΕΡΟΝΤΑΙ ΕΔΩ. ΑΝ ΚΑΙ ΟΙ ΔΥΟ ΤΕΧΝΙΚΕΣ ΔΙΑΦΕΡΟΥΝ ΣΗΜΑΝΤΙΚΑ ΣΤΟΝ ΤΡΟΠΟ ΔΟΜΗΣΗ ΤΗΣ ΠΛΗΡΟΦΟΡΙΑΣ ΣΤΟ ΧΑΜΗΛΟΤΕΡΟ ΕΠΙΠΕΔΟ (ΜΑΚΡΟΜΗΝΥΜΑΤΑ, ΠΑΚΕΤΑ) ΤΑ ΑΠΟΤΕΛΕΣΜΑΤΑ ΠΟΥ ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΒΑΣΙΖΟΝΤΑΙ ΣΤΗΝ ΥΙΟΘΕΤΗΣΗ ΕΝΟΣ ΚΑΤΑΛΛΗΛΟΥ ΜΟΝΤΕΛΟΥ ΠΡΟΣΟΜΟΙΩΣΗΣ.

THIS THESIS INVESTIGATES THE CONCEPT OF ROUTING MESSAGES BETWEEN PROCESSORS OF PARALLEL COMPUTERS. HERE WE PRESENT RESULTS CONSERNING TWO OF THE MOST PROMISING TECHNIQUES WORMHOLE ROUTING AND DEFLECTION (OR HOT-PATATO) ROUTING. WE PROPOSE AND ANALYZE A GREEDY HOT-POTATO ROUTING SCHEME FOR THE 2-DIMENSIONAL MESH BY ASSUMING THAT EACH NODE SENDS A PACKET TO A RANDOM DESTINATION. BY EMPLOYING A POTENTIAL FUNCTION METHOD WE PROVIDE A BOUND FOR THE TERMINATION TIMEOF OUR ALGORITHM IN THE AVERAGE CASE. WE ALSO PRESENT A SERIES OF EXPERIMENTAL RESULTS FOR SEVERAL IMPLEMENTATIONS OF ONLINE, OBLIVIOUS WORMHOLE ROUTING ON A MESH- CONNECTED PROSSESOR NETWORK, USING ONE BEND PATHS. ALSO,WE COMPARE (VIA SIMULATIONS) SEVERAL ROUTING ALGORITHMS BASED ON THE TECHNIQUES OF WORMHOLE AND DEFLECTION ROUTING. WE MEASURE AND COMPARE THE ABOVE ROUTING POLICIESUNDER REAL CONDITIONS. ALTHOUGH THESE TWO TECHNIQUES DIFFER SIGNIFICANTLY INTHE LOW LEVEL STRUCTURE OF INFORMATION (WORMS, PACKETS) WE DERIVE REALISTIC RESULTS USING AN APPROPRIATE SIMULATION MODEL.