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

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 για το οποίο προορίζονταν είναι κατειλημμένο.

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

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

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

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