2.6 Αλγόριθμοι προώθησης multicast πακέτων

 1.Flooding (πλημμύρα, υπερχείλιση). Αυτός ο αλγόριθμος είναι ο πιο απλός αλγόριθμος προώθησης. Όταν ένας δρομολογητής λαμβάνει ένα πακέτο multicast, ο multicast δρομολογητής αποφασίζει αν έχει ξανασυναντήσει αυτό το πακέτο πρόσφατα ή όχι. Αν το έχει ξαναδεί απλά απορρίπτει το πακέτο. Αν είναι η πρώτη φορά που το συναντά τότε το πακέτο προωθείται προς όλα τα σημεία εκτός από αυτό από το οποίο προήλθε. Αυτός ο αλγόριθμος εγγυάται ότι όλοι οι δρομολογητές λαμβάνουν το πακέτο. Αυτός ο αλγόριθμος είναι πολύ απλός στην εφαρμογή του. Ο δρομολογητής δεν χρειάζεται να συντηρεί περίπλοκους πίνακες δρομολόγησης πακέτων. Χρειάζεται απλά να κρατάει μία λίστα των πιο πρόσφατων πακέτων που συνάντησε. Αυτή η απλοϊκότητα ωστόσο παραγκωνίζεται από την αδυναμία της κλιμάκωσης του αλγορίθμου. Αυτός ο αλγόριθμος δεν θα δουλέψει σε WAN αφού δημιουργεί πολλά αντίγραφα του πακέτου και κίνηση σε όλες τις διαδρομές του δικτύου κάτι που εύκολα μπορεί να οδηγήσει σε συμφόρηση στο δίκτυο. Επίσης η μνήμη του δρομολογητή χρησιμοποιείται ανεπαρκώς αφού ο δρομολογητής πρέπει να δημιουργεί μία ξεχωριστή εισαγωγή στον πίνακα πρόσφατων πακέτων για κάθε διαφορετικό πακέτο.

 2.Spanning Trees - Constrained Steiner Trees (απλωμένα δέντρα). Η κατασκευή δέντρων είναι μία δημοφιλής και αποδοτική λύση δρομολόγησης. Τα multicast πακέτα εκπέμπονται παράλληλα στους διάφορους δρομολογητές κατά μήκος των κλάδων ενός δέντρου. Ο αριθμός των αντιγράφων ενός πακέτου μειώνεται καθώς η ανάγκη για αντίγραφο δημιουργείται στις διχάλες των κλάδων του δέντρου. Αυτά τα δέντρα έχουν σχεδιαστεί ειδικά για ελάχιστη δυνατή καθυστέρηση στην διαδρομή. Ο μέσος όρος καθυστέρησης μιας διαδρομής είναι ο μέσος όρος των ελαχίστων καθυστερήσεων από την πηγή προς κάθε προορισμό ενός multicast γκρουπ. Ένα Constrained Steiner (CST) είναι το χαρακτηριστικό παράδειγμα για αυτό. Είναι ένα δέντρο με περιορισμένη καθυστέρηση με ελάχιστο κόστος. Κατά την κατασκευή του CST, θεωρούμε ότι η πηγή έχει όλες τις πληροφορίες που χρειάζονται για την κατασκευή του δέντρου. Αυτό οδηγεί στο να χρησιμοποιούνται τα CST σαν μία υποδιαίρεση στην τοπολογία του Internet.

 Κατά την κατασκευή ενός CST το πρώτο βήμα είναι να αποφασιστεί η φτηνότερη διαδρομή από την πηγή προς κάθε προορισμό. Κάθε διαδρομή ελαχιστοποιεί τον μέσο όρο καθυστέρησης και πρέπει να έχει καθυστέρηση μικρότερη από την οριακή καθυστέρηση. Το επόμενο βήμα είναι να κατασκευαστεί το δέντρο. Ο CST αλγόριθμος κατασκευάζει το φτηνότερο δέντρο ενώ ταυτόχρονα διατηρεί τις καθυστερήσεις κάτω από τον οριακό περιορισμό. Μία μέθοδος για την κατασκευή αυτού του δέντρου είναι με το μοίρασμα των διαδρομών. Με τη χρήση αυτής της μεθόδου είναι δυνατό να βρεθούν διαδρομές οι οποίες έχουν καθυστέρηση πολύ μικρότερη από το όριο της καθυστέρησης που τίθεται κατά την σχεδίαση αλλά αντισταθμίζεται από ένα πιο ακριβό δέντρο. Με λίγα λόγια o CST αλγόριθμος κατασκευάζει ένα δέντρο στο οποίο υπάρχει μόνο μία διαδρομή μεταξύ οποιωνδήποτε δύο δρομολογητών σε υποδίκτυα του Internet.

 Όταν ένα multicast πακέτο εισέρχεται στον δρομολογητή, ο δρομολογητής απλά προωθεί το πακέτο σε όλους τους κλάδους του δέντρου εκτός από τον κλάδο από τον οποίο προήλθε το πακέτο. Αυτή η μέθοδος εγγυάται ότι κανένα πακέτο δεν θα ξανακάνει κάποιο κύκλο και ότι τα πακέτα θα φτάσουν σε όλους τους δρομολογητές του δέντρου.

 3.Reverse Path Broadcasting (εκπομπή ανάστροφης διαδρομής). Αυτός ο αλγόριθμος δημιουργεί ένα δέντρο για κάθε πιθανή πηγή σε ένα υποδίκτυο. Αυτά τα δέντρα θα χρησιμοποιηθούν από το υποδίκτυο το οποίο είναι άμεσα συνδεδεμένο στην πηγή. Έτσι υπάρχει ένα δέντρο για κάθε ενεργό ζευγάρι πηγής - γκρουπ. Αυτός είναι ένας ακόμα σχετικά απλός αλγόριθμος. Όταν ένα πακέτο multicast φτάνει στον δρομολογητή, αυτός αποφασίζει την πηγή του πακέτου. Αν το πακέτο φτάνει στον σύνδεσμο που ο δρομολογητής θεωρεί σαν την πιο γρήγορη διαδρομή προς την πηγή τότε το πακέτο προωθείται προς όλους τους δρόμους εκτός από τον κλάδο από τον οποίο προήλθε το πακέτο. Αλλιώς το πακέτο απορρίπτεται.

 Με σκοπό να μειωθεί ο αριθμός των διπλών πακέτων, υπάρχει μία βελτιωμένη έκδοση αυτού του αλγόριθμου. Ο τοπικός δρομολογητής αποφασίζει αν οι δρομολογητές που βρίσκονται πιο κάτω από αυτόν τον θεωρούν ως την ταχύτερη διαδρομή προς την πηγή του πακέτου. Το πακέτο τότε προωθείται μόνο προς τους δρομολογητές οι οποίοι θεωρούν τον τοπικό δρομολογητή ως τον πατρικό σύνδεσμο και πηγή του πακέτου. Είναι περιττό να προωθηθεί το πακέτο προς δρομολογητές οι οποίοι δεν θεωρούν τον τοπικό router ως πηγή του πακέτου αφού αυτοί οι δρομολογητές θα απορρίψουν το πακέτο. Αυτή η βελτίωση δουλεύει καλά με ένα πρωτόκολλο link-state (κατάστασης σύνδεσης) αφού ο κάθε δρομολογητής διατηρεί πληροφορίες για ολόκληρο το πεδίο δρομολόγησης.

 4.Truncated Reverse Path Broadcasting (διακεκομμένη εκπομπή ανάστροφης διαδρομής). Αυτός ο αλγόριθμος δημιουργήθηκε με σκοπό να βελτιωθεί ο RPB ως προς τους περιορισμούς του. O RPB δεν λαμβάνει υπ’όψιν του τα μέλη που περιέχει ένα γκρουπ όταν δημιουργεί τα δέντρα πηγής - γκρουπ. Έτσι υπάρχουν φορές που προωθούνται multicast πακέτα σε γκρουπ που δεν έχουν μέλη για τα συγκεκριμένα πακέτα. To TRPB χρησιμοποιεί το IGMP για να αποφασίσει για την συμμετοχή των μελών στα γκρουπ σε κάθε υποδίκτυο. Το TRPB αποφεύγει την προώθηση πακέτων σε υποδίκτυα που δεν έχουν μέλη για το συγκεκριμένο γκρουπ. Έτσι το δέντρο θεωρείται περικεκομένο από τον δρομολογητή αν το υποδίκτυο δεν έχει καθόλου μέλη για το γκρουπ.

 5.Reverse Path Multicasting (πολλαπλή εκπομπή ανάστροφης διαδρομής). Αυτός ο αλγόριθμος είναι ένα βελτιωμένος αλγόριθμος ως προς το RPB και το TRPB. Το RMP φτιάχνει ένα δέντρο το οποίο εκτείνεται μόνο στα υποδίκτυα τα οποία έχουν μέλη και στους δρομολογητές και υποδίκτυα τα οποία είναι στην πιο κοντινή διαδρομή προς υποδίκτυα με μέλη από γκρουπ. Το δέντρο αυτό περικόπτεται ώστε τα πακέτα να προωθούνται μόνο στους κλάδους των υποδικτύων με κόμβους μέλη.

 Όταν ένας multicast δρομολογητής λαμβάνει ένα πακέτο για ένα συγκεκριμένο ζεύγος πηγής - γκρουπ, το πρώτο πακέτο προωθείται ακολουθώντας τον TRPB αλγόριθμο προς όλους τους δρομολογητές του διαδικτύου. Αυτό εξασφαλίζει ότι όλοι οι δρομολογητές που είναι στην άκρη των κλάδων του δέντρου λαμβάνουν το πρώτο πακέτο. Αν υπάρχει ένα μέλος του γκρουπ σε υποδίκτυο του ακριανού δρομολογητή τότε το πακέτο προωθείται με βάση τις πληροφορίες από το IGMP. Αν δεν υπάρχει κανένα μέλος σε υποδίκτυο του ακριανού δρομολογητή τότε ο δρομολογητής στέλνει ένα μήνυμα prune (περικοπής). Αυτό ενημερώνει τον αμέσως από πάνω δρομολογητή ότι δεν πρέπει να προωθηθούν άλλα πακέτα αυτού του γκρουπ στον ακριανό δρομολογητή. Ο router που προηγείται του ακραίου και λαμβάνει το μήνυμα διακοπής αποστολής των πακέτων πρέπει να διατηρήσει τις πληροφορίες αυτού του μηνύματος. Αν ο δρομολογητής λάβει μηνύματα prune από όλους τους δρομολογητές που βρίσκονται από κάτω του τότε θα στείλει ένα αντίστοιχο μήνυμα στον πατρικό του router και επαναλαμβάνεται η ίδια διαδικασία. Τελικά με αυτά τα μηνύματα περικοπής δημιουργείται ένα multicast δέντρο που περιέχει μόνο κλάδους οι οποίοι είναι ενεργά μέλη.

 Αφού η συμμετοχή σε ένα γκρουπ είναι δυναμικής φύσεως, το multicast δέντρο ανανεώνεται σε τακτά χρονικά διαστήματα. Ο κάθε δρομολογητής καθαρίζει τα μηνύματα διακοπές από την μνήμη του και τότε το πρώτο πακέτο που θα λάβει θα το προωθήσει προς όλους τους δρομολογητές που βρίσκονται από κάτω του. Αυτό προκαλεί ένα νέο κύμα μηνυμάτων διακοπής που δημιουργούν ένα νέο multicast δέντρο.

 6.Shortest Path Trees (Δέντρα της μικρότερης διαδρομής). Τα δέντρα της ελάχιστης διαδρομής είναι ένα παράδειγμα ενός μη περιορισμένου αλγορίθμου multicast δρομολόγησης. Ο αλγόριθμος SPT κατασκευάζει ένα εκτεινόμενο δέντρο από την πηγή προς όλα τα μέλη που είναι προορισμοί για τα πακέτα μειώνοντας ένα δεδομένο κόστος όπως οι καθυστερήσεις από άκρη σ’ άκρη ή ο αριθμός των hops χωρίς να υπολογίζεται η ποιότητα των απαιτήσεων της υπηρεσίας. Για να μειωθεί η συνάρτηση του κόστους χρησιμοποιείται ένας αλγόριθμος όπως αυτός των Bellman - Ford. Και πάλι αυτοί οι αλγόριθμοι μπορούν να δεχτούν επεμβάσεις επιτρέποντας τον διαμοιρασμό συνδέσμων (links) και έτσι να μειώσουν το κόστος των SPT.

 7.Core Based Trees (δέντρα βασισμένα σε πυρήνα). Τα δέντρα αυτά διαφέρουν από τους υπάρχοντες αλγορίθμους δρομολόγησης στο ότι χτίζουν ένα δέντρο παράδοσης το οποίο μοιράζεται από όλες τις πηγές ενός γκρουπ αντί για ένα δέντρο για κάθε ζεύγος πηγής γκρουπ. Έτσι η κίνηση του multicast διακινείται πάνω στο ίδιο δέντρο ανεξάρτητα από την πηγή.

Ο CBT αλγόριθμος έχει έξι κύριους σχεδιαστικούς σκοπούς.

Πρώτον θα πρέπει να ακολουθεί τις απαιτήσεις του Host Group μοντέλου, δηλαδή: οι αποστολείς δεν χρειάζεται να είναι μέλη του γκρουπ, τα γκρουπ μπορούν να έχουν όσα μέλη θέλουν, η λίστα των μελών είναι δυναμική και αυτόνομη, δεν υπάρχουν τοπολογικοί περιορισμοί για να γίνει κάποιος κόμβος μέλος ενός γκρουπ και τα γκρουπ μπορεί να είναι μόνιμα ή προσωρινά.

Δεύτερον το CBT είναι κλιμακωτό. Χρησιμοποιεί λίγη μνήμη, έχει λίγες απαιτήσεις σε εύρος ζώνης και μικρές απαιτήσεις σε επεξεργαστική ισχύ από τους πόρους των multicast δρομολογητών όταν εφαρμόζεται σε ευρύτερα τοπολογικά δίκτυα.

Τρίτον το CBT είναι ένας ισχυρός αλγόριθμος multicast. Καθώς τα δέντρα γίνονται μεγαλύτερα, η τοποθέτηση του πυρήνα γίνεται με γνώμονα την βέλτιστη σταθερότητα για το δέντρο διανομής των πακέτων.

Τέταρτο το CBT προσφέρεται για “αόρατη” δρομολόγηση της multicast ροής και για διευθυνσιοδότηση σε δρομολογητές που δεν ανήκουν στο CBT δέντρο. Έτσι οι διευθύνσεις multicast αναγνωρίζονται μόνο αν ο δρομολογητής είναι μέλος του γκρουπ, όταν δηλαδή ανήκει στο δέντρο CBT για αυτό το γκρουπ. Οι δρομολογητές που ανήκουν στο δέντρο CBT χρειάζεται μόνο να γνωρίζουν ποιοι είναι οι δρομολογητές που βρίσκονται από πάνω και από κάτω τους στο δέντρο.

Πέμπτο το CBT είναι αλγόριθμος δρομολόγησης ανεξάρτητα από ποιο πρωτόκολλο χρησιμοποιείται σε ένα δίκτυο. Έτσι μπορεί να εγκατασταθεί οπουδήποτε επιτρέποντας και εσωτερική δρομολόγηση multicast δεδομένων.

Έκτο το CBT είναι ανεξάρτητο από κάθε καινούρια δομή ΙΡ διευθυνσιοδότησης.

Ένα δέντρο CBT μπορεί να έχει ένα μόνο πυρήνα ή και περισσότερους ανάλογα με το μέγεθος του γκρουπ. Όταν ένας κόμβος επιθυμεί να γίνει μέλος ενός γκρουπ, στέλνει μία αίτηση για συμμετοχή προς το δέντρο πυρήνα του γκρουπ. Αυτή την αίτηση την επεξεργάζονται όλοι οι ενδιάμεσοι δρομολογητές προσδιορίζοντας από ποιο σημείο προήλθε η αίτηση και καθορίζουν το CBT δέντρο διανομής για αυτό τον κόμβο. Αν ένας κόμβος επιθυμεί να γίνει πηγή για ένα γκρουπ, αλλά δεν είναι μέλος αυτού του γκρουπ τότε στέλνει σε απλά ΙΡ πακέτα unicast τα δεδομένα προς τον κεντρικό δρομολογητή. Όταν το πακέτο φτάσει σε ένα δρομολογητή ο οποίος είναι μέλος του CBT δέντρου, από εκεί και πέρα εκπέμπεται πολλαπλά σαν multicast πακέτο μέχρι το τέλος της διαδρομής. Αυτό εγγυάται την προώθηση του πακέτου προς όλα τα μέλη ενός γκρουπ. Όλα τα πακέτα περικλείονται μέσα σε μία ΙΡ unicast διεύθυνση και διακινούνται με χρήση των κλασσικών ΙΡ αλγορίθμων. Όλα τα μηνύματα και τα πακέτα προωθούνται προς τον πυρήνα του δέντρου ή προς ένα από τους πυρήνες αν αναφερόμαστε σε δέντρο με παραπάνω από έναν κεντρικούς κλάδους. Αυτό εξασφαλίζει την σωστή διανομή των πακέτων σε όλους τους δρομολογητές που βρίσκονται στο δέντρο.

Previous Contents Up Next