Traffic Shaping - Queueing algorithms

Μία σύντομη εισαγωγή σε queueing algorithmsς και της εφαρμογής τους σε δίκτυα υπολογιστών.

1. FIFO

[1.1 Γενικά]

[1.2 Λειτουργία]

[1.3 pfifo_fast]

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

2. Stochastic Fairness Queueing (SFQ)

[2.1 Γενικά]

[2.2 Λειτουργία]

3. Random Early Detection (RED)

[3.1 Γενικά]

[3.2 Λειτουργία]

4. Αναφορές:

[1. FIFO]

[1.1 Γενικά]

Ο αλγόριθμος FIFO είναι ο ποιο απλός απ' όσους μπορούν να εφαρμοστούν για την διαχείριση της ουράς σε έναν network interface. Είναι ιδιαίτερα απλός και συνήθως αποτελεί την default αντιμετώπιση.

[1.2 Λειτουργία]

Η λειτουργία του βασίζεται στα εξής χαρακτηριστικά:

Υπάρχει μία ουρά με σταθερό μέγεθος σε bytes ή πακέτα.

Όσο η ουρά δεν είναι γεμάτη, κάθε πακέτο που έρχεται τοποθετείται στο τέλος της ουράς.

Όταν πρόκειται να σταλεί ένα πακέτο στο δίκτυο, επιλέγεται το πρώτο από την ουρά.

Όταν η ουρά είναι γεμάτη, κάθε πακέτο που έρχεται απορρίπτεται. Ο τρόπος αυτός ονομάζεται tail-drop.

[1.3 pfifo_fast]

Ο pfifo_fast αποτελεί μια παραλλαγή του FIFO. Ακολουθεί την ίδια λογική, αλλά χωρίζει την ουρά σε τρία bands. Στη συνέχεια, κάθε πακέτο που έρχεται τοποθετείται σε ένα από τα τρία bands, ανάλογα με την τιμή του TOS πεδίου. Το πεδίο αυτό έχει μέγεθος 4 bits, κάθε ένα από τα οποία έχει και άλλη σημασία:

--------------------------------------------------------------------------------

[IMG]

--------------------------------------------------------------------------------

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

--------------------------------------------------------------------------------

[IMG]

--------------------------------------------------------------------------------

Ποτέ δεν στέλνεται πακέτο από την band 1 όταν υπάρχει κάποιο στη band 0, ούτε από την band 2 όταν υπάρχει κάποιο στη band 1.

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

Το μόνο πλεονέκτημα του αλγόριθμου είναι η ταχύτητά και η απλότητά του. Στην πράξη δεν έχει καλά αποτελέσματα όταν υπάρχει συμφόρηση σε κάποια γραμμή, αλλά χρησιμοποιείται με επιτυχία σε γρήγορα interfaces όπου δεν παρατηρείται συμφόρηση.

[2. Stochastic Fairness Queueing (SFQ)]

[2.1 Γενικά]

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

[2.2 Λειτουργία]

Ο SFQ δημιουργεί πολλά slots του ενός πακέτου, στα οποία ταξινομεί τα πακέτα και στη συνέχεια επιλέγει το επόμενο από αυτά που θα σταλεί στο δίκτυο με κυκλικό (Round-Robin) τρόπο. Πιο συγκεκριμένα:

Δημιουργεί 128 διαφορετικά slots του ενός πακέτου.

Κάθε πακέτο το οποίο έρχεται κατευθύνεται ένα από αυτά.

Αν το slot είναι κατειλημμένο τότε το πακέτο απορρίπτεται, αλλιώς τοποθετείται μέσα σε αυτό.

Στη συνέχεια, όταν πρόκειται να δρομολογήσει ένα πακέτο στο δίκτυο, παίρνει το πρώτο που υπάρχει στην ``επόμενη'' ουρά.

Hashing

Η τοποθέτηση του κάθε πακέτου σε κάθε ένα από τα 128 slots γίνεται με την βοήθεια ενός αλγόριθμου hashing. Για τον υπολογισμού του hash key λαμβάνονται υπόψη:

Για IPv4 πακέτα:

: Η source IP address, η destination IP address και το πρωτόκολλο (TCP,UDP, ...).

Για IPv6 πακέτα:

: Η source IP address, η destination IP address και η τιμή ενός εσωτερικού pointer.

Για τα υπόλοιπα:

: Οι τιμές τριών εσωτερικών pointers.

Επίσης χρησιμοποιείται και ένας τυχαίος αριθμός ο οποίος προέρχεται από το δίκτυο και ο οποίος αλλάζει κάθε 10 δευτερόλεπτα -- το χρονικό διάστημα ονομάζεται perturb -- και είναι παραμετροποιήσιμο.

Ο σκοπός του hashing είναι να αναγνωρίζει flows και να τα διαχωρίζει, δίνοντας ίσες ευκαιρίες στους χρήστες του δικτύου, ακόμα και αν κάποιος δημιουργεί υπερβολική κίνηση. Λόγω του ότι τα hash keys δεν είναι μοναδικά, χρησιμοποιείται ο τυχαίος αριθμός που αναφέρθηκε, ο οποίος ουσιαστικά μεταβάλει τον αλγόριθμο κάθε 10 δευτερόλεπτα.

Αποστολή πακέτων

Η επιλογή του επόμενου πακέτου προς αποστολή γίνεται με κυκλικό τρόπο (Round-Robin), επιλέγοντας ένα πακέτο από την επόμενη στοίβα κάθε φορά. Με τον τρόπο αυτό, τα flows τα οποία παρουσιάζουν κίνηση μπορούν να δημιουργήσουν 128 φορές μικρότερο πρόβλημα στο δίκτυο.

Παράδειγμα

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

--------------------------------------------------------------------------------

[IMG]

--------------------------------------------------------------------------------

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

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

Το πρόβλημά του είναι το μικρό μήκος ουράς (μόλις 128 πακέτα), το οποίο οδηγεί σε πολύ μεγάλο αριθμό χαμένων πακέτων. Κάτι τέτοιο είναι αποδεκτό και ίσως και επιθυμητό σε περιπτώσεις όπου ένα flow/slot αντιστοιχεί σε έναν μόνο υπολογιστή του τοπικού δικτύου, αλλά δημιουργεί προβλήματα σε μεγαλύτερα δίκτυα.

[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), το οποίο υπολογίζεται με την άφιξη κάθε νέου πακέτου σύμφωνα με τον τύπο:

--------------------------------------------------------------------------------

[IMG]

--------------------------------------------------------------------------------

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

--------------------------------------------------------------------------------

[IMG]

--------------------------------------------------------------------------------

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

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

avg_p < min_q

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

min_q < avg_q < max_q

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

[IMG]

--------------------------------------------------------------------------------

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

[IMG]

--------------------------------------------------------------------------------

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

avg_q > max_q

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

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

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

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

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

[4. Αναφορές:]

Bert Hubert, Gregory Maxwell, Remco van Mook, Martijn van Oosterhout, Paul B Schroeder, Jasper Spaans, Pedro Larroy. Linux Advanced Routing & Traffic Control HOWTO,

Sally Floyd and Van Jacobson. Random Early Detection Gateways for Congestion Avoidance. University of California, 1993

Linux kernel 2.4.20 sources

Αρχική Σελίδα