Δίκτυα Υπολογιστών Κεφάλαιο 26 – Πρωτόκολλα πραγματικού χρόνου: Τεχνικές Χρονοπρογραμματισμού

Δημοσιεύτηκε από τον/την codebrakes στις

Δίκτυα Υπολογιστών
Κεφάλαιο 26 - Πρωτόκολλα πραγματικού χρόνου: Τεχνικές Χρονοπρογραμματισμού

Χαρακτηριστικά ροής δεδομένων

  1. Αξιοπιστία: Η αξιοπιστία είναι ένα χαρακτηριστικό που χρειάζεται μια ροή δεδομένων. Η έλλειψη αξιοπιστίας συνεπάγεται με απώλεια πακέτων και επιβεβαιώσεων. Παρόλα αυτά υπάρχουν εφαρμογές που δεν εφαρμόζουν τεχνικές αξιοπιστίας. Για παράδειγμα, η ύπαρξη αξιοπιστίας για υπηρεσίες όπως το ηλεκτρονικό ταχυδρομείο (e-mail), μεταφοράς αρχείων και πρόσβασης διαδικτύου είναι αρκετά σημαντική ενώ σε υπηρεσίες τηλεφωνίας η τηλεδιάσκεψης δεν αποτελεί σημαντικό παράγοντα.
  2. Καθυστέρηση από την πηγή στον προορισμό: Η καθυστέρηση είναι ένα από τα χαρακτηριστικά μιας ροής δεδομένων. Κάθε εφαρμογή μπορεί να διαχειριστεί τις καθυστερήσεις σε διαφορετικό βαθμό. Σε περιπτώσεις όπως η τηλεφωνία, τηλεδιασκέψεις και λειτουργίες απομακρυσμένου ελέγχου η καθυστέρηση πακέτων πρέπει να είναι σχετικά ελάχιστη. Σε περιπτώσεις όμως μεταφοράς αρχείων ή ηλεκτρονικού ταχυδρομείου (e-mail) η καθυστέρηση των πακέτων δεν αποτελεί μείζον πρόβλημα.
  3. Jitter: Με τον όρο Jitter αναφερόμαστε στην διακύμανση της καθυστέρησης πακέτων δεδομένων τα οποία ανήκουν στην ίδια ροή. Για παράδειγμα, έστω ότι έχουμε τέσσερα πακέτα τα οποία πρέπει να σταλθούν στις χρονικές στιγμές 0, 1, 2, 3. Για κάποιο λόγο όμως, φτάνουν στις χρονικές στιγμές 19, 20, 21, 22 αυτό σημαίνει ότι όλα τα πακέτα είχαν την ίδια καθυστέρηση, δηλαδή 19 “τμήματα” του χρόνου. Απ’ την άλλη, αν αυτά τα τέσσερα πακέτα φτάσουν στις χρονικές στιγμές 19, 23, 24 και 25, θα έχουν διαφορετική καθυστέρηση. Για εφαρμογές ήχου και video, η πρώτη περίπτωση (όπου έχουμε την ίδια χρονική καθυστέρηση) είναι αποδεκτή, η δεύτερη όμως (όπου έχουμε διαφορετική χρονική καθυστέρηση) δεν είναι αποδεκτή. Για αυτές της εφαρμογές, δεν έχει σημασία αν τα πακέτα φτάσουν με μικρή ή με μεγάλη καθυστέρηση, αρκεί μόνο να είναι η χρονική καθυστέρηση να είναι ίδια για όλα τα πακέτα. Υψηλό jitter σημαίνει ότι η διαφορά μεταξύ των καθυστερήσεων είναι μεγάλη, ενώ χαμηλό jitter δηλώνει μικρή καθυστέρηση.
  4. Εύρος ζώνης (Bandwidth): Κάθε διαφορετική εφαρμογή, απαιτεί και διαφορετικό εύρος ζώνης. Κατά την διάρκεια μιας τηλεδιάσκεψης, στέλνονται εκατομμύρια bits ανά δευτερόλεπτο για να ανανεωθεί μια έγχρωμη εικόνα, ενώ ο συνολικός αριθμός των bits σε ένα e-mail είναι λιγότερος από ένα εκατομμύριο.
  5. Κατηγορίες ροών (Flow classes): Βασιζόμενοι στα χαρακτηριστικά κάθε ροής, μπορούμε να κατατάξουμε τις ροές σε ομάδες, όπου κάθε ομάδα θα έχει παρόμοια χαρακτηριστικά. Η κατηγοριοποίηση αυτή δεν είναι επίσημη ή γενική. Ορισμένα πρωτόκολλα, όπως το ATM, έχουν καθορισμένες κατηγορίες.
  6. Τεχνικές βελτίωσης quality of service (QoS): Η ποιότητα υπηρεσιών μας εξασφαλίζει ότι οι απαιτήσεις ενός κόμβου ή μιας εφαρμογής θα ικανοποιηθούν από το δίκτυο. Θα αναφερθούμε σε 4 γνωστές μεθόδους οι οποίες είναι: χρονοπρογραμματισμό, την διαμόρφωση κίνησης (traffic shaping), τον έλεγχο αποδοχής (admission control) και της δέσμευσης των πόρων (resource reservation).
  7. Χρονοπρογραμματισμός (Scheduling): Σε ένα μεταγωγέα (switch) ή δρομολογητή (router) φτάνουν πακέτα από διαφορετικές ροές για επεξεργασία. Μια καλή τεχνική χρονοπρογραμματισμού αντιμετωπίζει όλα τα πακέτα με δίκαιο και σωστό τρόπο. Υπάρχουν μερικές τεχνικές χρονοπρογραμματισμού που έχουν σχεδιαστεί για να βελτιωθεί η ποιότητα της υπηρεσιών. Εμείς θα αναφέρουμε τρείς τεχνικές τον αλγόριθμο FIFO (FIFO Queuing), προτεραιότητας (Priority Queuing) και δίκαιης απονομής (Weighted Fair Queuing)


Τεχνικές χρονοπρογραμματισμού

FIFO – First-In-First-Out (Πρώτος-Μέσα-Πρώτος-Έξω): Στον αλγόριθμο FIFO τα πακέτα περιμένουν σε έναν buffer (ουρά) έως ότου ο κόμβος (router ή switch) είναι έτοιμος να τα επεξεργαστεί. Αν ο μέσος ρυθμός αφίξεως είναι μεγαλύτερος από τον μέσο ρυθμό επεξεργασίας, η ουρά θα γεμίσει και τα νέα πακέτα θα απορριφθούν. Ας πάρουμε ένα καθημερινό παράδειγμα, όταν θέλουμε να πάρουμε λεωφορείο περιμένουμε σε μια στάση λεωφορείων προκειμένου να σταματήσει, το ίδιο ακριβώς ισχύει και με τα πακέτα σε μια ουρά FIFO. Η εικόνα παρακάτω δείχνει την δομή με την οποία λειτουργεί ο αλγόριθμος FIFO.

Παράδειγμα λειτουργίας του αλγορίθμου FIFO

Priority Queuing: Στον αλγόριθμο προτεραιότητας τα πακέτα πρώτα χωρίζονται σε μια κλάση προτεραιότητας. Κάθε κλάση προτεραιότητας έχει την δική της ουρά. Όλα τα πακέτα που ανήκουν στην ουρά με την υψηλή προτεραιότητα επεξεργάζονται πρώτα. Τα πακέτα που ανήκουν στην ουρά με την χαμηλή προτεραιότητα επεξεργάζονται τελευταία. Να σημειώσουμε ότι στον αλγόριθμο FIFO και οι δύο ουρές εξυπηρετούνται έως ότου να αδειάσουν. Η εικόνα παρακάτω δείχνει την δομή με την οποία λειτουργεί ο αλγόριθμος προτεραιότητας.

Η ουρά προτεραιότητας παρέχει καλύτερη ποιότητα υπηρεσιών (QoS) από τον αλγόριθμο FIFO διότι η κίνηση υψηλότερης προτεραιότητας (όπως πολυμεσικά δεδομένα) μπορούν να φτάσουν στον προορισμό τους με ελάχιστη καθυστέρηση. Παρόλα αυτά υπάρχει ένα ενδεχόμενο μειονέκτημα. Αν υπάρχει συνεχόμενη ροή δεδομένων στην ουρά προτεραιότητας τα πακέτα που βρίσκονται στην ουρά χαμηλής προτεραιότητας μπορεί να μην αποκτήσουν ποτέ την δυνατότητα να επεξεργαστούν. Αυτή η συνθήκη ονομάζεται ατέρμονη αναμονή ή εμπλοκή (starvation).


Weighted Fair Queuing: Στον αλγόριθμο δίκαιης απονομής τα πακέτα κι εδώ ανατίθενται σε διαφορετικές κλάσεις και τοποθετούνται σε διαφορετικές ουρές. Παρόλα αυτά οι ουρές αποκτούν βαρύτητα με βάση την προτεραιότητα που έχουν οι ουρές, υψηλή προτεραιότητα σημαίνει και υψηλή βαρύτητα. Το σύστημα επεξεργάζεται κάθε πακέτο στην ουρά με την δομή round-robin με τον αριθμό του πακέτων να επιλέγεται από κάθε ουρά με βάση την κατάλληλη βαρύτητα.

Παράδειγμα λειτουργίας του αλγορίθμου δίκαιης απονομής

Για παράδειγμα, έστω ότι έχουμε βαρύτητες 3, 2 και 1. Θα επεξεργαστούν αρχικά τρία πακέτα από την πρώτη ουρά, δύο από την δεύτερη ουρά και ένα από την τρίτη ουρά. Αν το σύστημα δεν υποδείξει της προτεραιότητες στις κλάσεις, όλες οι βαρύτητες θα είναι ίσες. Με αυτόν τον τρόπο, έχουμε δίκαιη ανάθεση προτεραιότητας σε όλες τις ουρές. Η εικόνα παρακάτω δείχνει τον μηχανισμό του αλγορίθμου δίκαιης απονομής.

Η διαμόρφωση κίνησης (traffic shaping) είναι ένας μηχανισμός ο οποίος μας παρέχει την δυνατότητα διαχείρισης του ποσοστού και του ρυθμού με τον οποίο η κίνηση δεδομένων στέλνεται σε ένα δίκτυο. Υπάρχουν δύο τεχνικές για να διαμορφώσουμε την κίνηση δεδομένων η πρώτη είναι η τεχνική leaky bucket και η δεύτερη η token bucket.

Παράδειγμα τεχνικής Leaky Bucket

Μπορούμε λοιπόν να αναφέρουμε ότι το ίδιο ακριβώς συμβαίνει και στην τεχνική leaky bucket η οποία μπορεί να εξομαλύνει υπερβολικά μεγάλες κινήσεις δεδομένων. Τα υπερβολικά μεγάλα τμήματα αποθηκεύονται σε έναν κουβά και στέλνονται με έναν μέσο ρυθμό ταχύτητας. Η εικόνα δεξιά δείχνει την δομή με την οποία λειτουργεί η τεχνική Leaky bucket. Από την εικόνα συμπεραίνουμε ότι στο δίκτυο έχει εκχωρηθεί εύρος ζώνης 7 Mbps για έναν host. Η χρήση της τεχνικής Leaky bucket διαμορφώνει την εισερχόμενη κίνηση έτσι ώστε να προσαρμοστεί σε αυτό το εύρος ζώνης. Από την εικόνα βλέπουμε ότι ο host στέλνει ένα μεγάλο τμήμα δεδομένων με ρυθμό 20 Mbps για 2 δευτερόλεπτα, δηλαδή συνολικά 40 Mbits δεδομένων.


Ο host παραμένει αδρανής για 2 δευτερόλεπτα και στην συνέχεια στέλνει δεδομένα με ρυθμό 3 Mbps για 3 δευτερόλεπτα, δηλαδή συνολικά έστειλε 9 Mbits δεδομένων. Όλα αυτά τα Mbits που έστειλε ο Host κατά την διάρκεια αυτών των 7 δευτερολέπτων ήταν 49 Mbits. Η τεχνική του Leaky bucket εξομαλύνει την κίνηση στέλνοντας τα δεδομένα με ρυθμό 7 Mbps κατά την διάρκεια αυτών των 7 δευτερολέπτων. Χωρίς την τεχνική Leaky bucket, το αρχικό μεγάλο τμήμα μπορεί να δημιουργούσε πρόβλημα στο δίκτυο καταναλώνοντας μεγαλύτερο εύρος ζώνης από αυτό που έχει οριστεί για τον Host. Παρατηρούμε επίσης ότι αυτή η τεχνική μπορεί να αποτρέψει την συμφόρηση στο δίκτυο.


Στην παρακάτω εικόνα αποτυπώνεται μια απλή προσέγγιση του Leaky Bucket. Μια λοιπόν ουρά FIFO κρατάει τα πακέτα.

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

Εφαρμογή του αλγορίθμου Leaky Bucket

Το παραπάνω παράδειγμα αφορά έναν αλγόριθμο που βασίζεται σε μεταβλητό μήκος πακέτων:

  1. Ξεκινάει ένας μετρητής (από έναν x αριθμό) με το πρώτο τικ του ρολογιού
  2. Αν αυτός ο x αριθμός είναι μεγαλύτερος από το μέγεθος των πακέτων, στέλνει το πακέτο και μειώνει τον x αριθμό που βρίσκεται στον μετρητή αφαιρώντας από αυτόν το μέγεθος του πακέτου. Αυτό το βήμα επαναλαμβάνεται έως ότου ο αριθμός x είναι μικρότερος από το μέγεθος του πακέτου.
  3. Ο μετρητής επαναφέρεται πίσω στο 1ο βήμα
Σημαντική Παρατήρηση
Ένας αλγόριθμος leaky bucket διαμορφώνει μια μεγάλη κίνηση δεδομένων σε μια κίνηση δεδομένων σταθερού ρυθμού κι αυτό το κάνει υπολογίζοντας τον μέσο όρο του ρυθμού δεδομένων. Υπάρχει περίπτωση να απορρίψει πακέτα σε περίπτωση που ο «κουβάς» είναι γεμάτος.

Token Bucket: Η τεχνική leaky bucket είναι πολύ περιοριστική, δηλαδή δεν λαμβάνει υπόψιν τους αδρανείς hosts. Για παράδειγμα, αν ένας host δεν στέλνει τίποτα για ένα μεγάλο χρονικό διάστημα ο “κουβάς” αδειάζει. Όμως σε περίπτωση που ένας host έχει μεγάλα δεδομένα που θέλει να μεταδώσει, ο αλγόριθμος leaky bucket επιτρέπει στον ίδιο να τα στείλει μόνο σε έναν μέσο ρυθμό. Το χρονικό διάστημα που ο host είναι αδρανής, δεν λαμβάνεται υπόψιν. Από την άλλη μεριά, ο αλγόριθμος token bucket επιτρέπει σε έναν αδρανή host να συλλέξει tokens (μάρκες) για μελλοντική χρήση. Για κάθε τικ του ρολογιού, το σύστημα στέλνει x tokens στον κουβά του host. Το σύστημα αφαιρεί ένα token για κάθε τμήμα δεδομένων (ή byte) που στέλνεται. Για παράδειγμα, έστω ότι το x είναι 400 και ότι ο host είναι αδρανής 400 ticks, ο κουβάς έχει συλλέξει 160.000 tokens.

Με αυτόν τον τρόπο ο host μπορεί να καταναλώσει όλα αυτά τα tokens σε ένα tick στέλνοντας με την μια 160.000 τμήματα δεδομένων, ή μπορεί να στείλει 160 τμήματα δεδομένων ανά τικ σε 1000 τικ. Με απλά λόγια, ο host μπορεί να στείλει μεγάλα τμήματα δεδομένων αρκεί ο κουβάς να μην είναι άδειος. Η παρακάτω εικόνα δείχνει το παράδειγμα αυτό.

Εφαρμογή του αλγορίθμου Token Bucket

Η τεχνική token bucket μπορεί να εφαρμοστεί πολύ απλά με έναν μετρητή. Το token ξεκινάει από το μηδέν. Κάθε φορά που προστίθεται ένα token, ο μετρητής αυξάνεται κατά ένα. Κάθε φορά που στέλνεται ένα τμήμα δεδομένων ο μετρητής μειώνεται κατά ένα. Όταν ο μετρητής έχει την τιμή μηδέν, ο Host δεν μπορεί να στείλει δεδομένα.

Τελευταία ενημέρωση: 29/04/2018


0 σχόλια

Αφήστε μια απάντηση

Σύμβολο κράτησης θέσης avatar

Η ηλ. διεύθυνση σας δεν δημοσιεύεται. Τα υποχρεωτικά πεδία σημειώνονται με *