Επόμενο  Προηγούμενο  Περιεχόμενα

3. Random Early Detection (RED)

3.1 Γενικά

Ο αλγόριθμος αυτός είναι μία άλλη αντιμετώπιση της FIFO ουράς. Σκοπός του είναι να μην αφήσει την FIFO ουρά να γεμίσει, απορρίπτοντας επιλεκτικά πακέτα όταν χρειάζεται.

3.2 Λειτουργία

Η απόρριψη των πακέτων γίνεται στατιστικά, όταν το μέσο μέγεθος της ουράς ξεπεράσει κάποιο όριο.

Ο αλγόριθμος δέχεται τις εξής παραμέτρους:

Minimum queue length: (min_q)

Το μέσο μέγεθος της ουράς το οποίο πρέπει να ξεπεραστεί πριν αρχίσει ο αλγόριθμος να εξετάζει πιθανή απόρριψη πακέτων.

Maximum queue length: (max_q)

Το μέσο μέγεθος της ουράς κάτω από το οποίο προσπαθεί να την κρατάει πάντα ο αλγόριθμος. Ονομάζεται και soft limit.

Queue limit: (qlim)

Το απόλυτο μέγιστο μέγεθος της ουράς. Αν το φτάσει τότε ο αλγόριθμος μετατρέπεται σε FIFO. Ονομάζεται και hard limit.

Average packet size: (avg_p)

Το μέσο μέγεθος του κάθε πακέτου. Με βάση αυτό γίνεται ο υπολογισμός όλων των υπόλοιπων.

Burst size: (burst)

Το μέγιστο επιτρεπόμενο μέγεθος των bursts , ώστε να μην απορρίπτονται πακέτα όταν δεν υπάρχει πραγματική συμφόρηση.

Ο αλγόριθμος δεν αναγνωρίζει flows όπως κάποιοι άλλοι και στηρίζεται στην τυχαία επιλογή πακέτων. Η λειτουργία του βασίζεται στο μέσο μέγεθος της ουράς (avg_q), το οποίο υπολογίζεται με την άφιξη κάθε νέου πακέτου σύμφωνα με τον τύπο:

όπου cql είναι το τρέχον μέγεθος της ουράς (current queue length), m είναι ο χρόνος κατά τον οποίο η ουρά δεν είναι άδεια και W είναι μία τιμή που υπολογίζεται ως συνάρτηση των burst, min_q και avg_p έτσι ώστε να ισχύει:

Το W ονομάζεται και βάρος της ουράς (Queue Weight) και υποδηλώνει το κατά πόσο επηρεάζουν το avg_q οι νέες τιμές της. Όσο μεγαλύτερο είναι το W, τόσο μεγαλύτερη σημασία έχουν προσωρινές αυξομειώσεις της ουράς -- δηλώνει το κατά πόσο πρέπει να ``θυμάται'' ο αλγόριθμος τα παλαιότερα μεγέθη της ουράς.

Η μεταχείριση του κάθε πακέτου μεταβάλλεται ανάλογα με το avg_q:

• avg_p < min_q

  Το πακέτο δεν επηρεάζεται.

• min_q < avg_q < max_q

  Στο πακέτο αποδίδεται μια πιθανότητα p_b:

  όπου max_p είναι η μέγιστη επιθυμητή τιμή του p_b. Ταυτόχρονα υπάρχει ένας counter ο οποίος αυξάνεται με κάθε πακέτο όταν το avg_q βρίσκεται σε αυτά τα όρια. Στη συνέχεια υπολογίζεται η πιθανότητα απόρριψης p_a:

  Τέλος χρησιμοποιείται ένας τυχαίος αριθμός R, μεταξύ των 0 και 1, σύμφωνα με τον οποίο απορρίπτεται το πακέτο αν ο R είναι μικρότερος του p_a.

• avg_q > max_q

  Το πακέτο απορρίπτεται.

Επειδή η απόρριψη των πακέτων γίνεται με στατιστικό τρόπο, τα flows τα οποία δημιουργούν μεγαλύτερη κίνηση έχουν περισσότερες πιθανότητες να χάσουν πακέτα μιας και στέλνουν δεδομένα ποιο συχνά στο δρομολογητή.

Πλεονεκτήματα/Μειονεκτήματα

Ο RED αποτελεί μια πολύ καλή λύση για την αντιμετώπιση της συμφόρησης του δικτύου ενώ ταυτόχρονα βοηθάει το TCP/IP να βρει σχετικά σύντομα το σωστό ρυθμό αποστολής δεδομένων.

Λόγω του ότι δεν αναγνωρίζει flows δεν έχει τη δυνατότητα να παρέχει μεγάλη δικαιοσύνη κάτι το οποίο δεν αποτελεί και σκοπό του.

Επόμενο  Προηγούμενο  Περιεχόμενα