Πώς εφαρμόζεται ο λογαριθμικός αλγόριθμος back-off σε στρώση MAC για να αποφευχθεί η σύγκρουση;

Ο λογαριθμικός αλγόριθμος backoff στο στρώμα MAC, που χρησιμοποιείται κυρίως σε πρωτόκολλα CSMA/CA (CARIER Sense Multiple με αποφυγή σύγκρουσης), όπως το Wi-Fi (802.11), στοχεύει στην επίλυση συγκρούσεων εισάγοντας μια τυχαιοποιημένη καθυστέρηση πριν από την επαναπροσδιορισμό ενός πλαισίου. Είναι "λογαριθμικό" επειδή το φάσμα πιθανών καθυστερήσεων αυξάνεται εκθετικά με κάθε διαδοχική σύγκρουση. Δείτε πώς εφαρμόζεται:

1. Ανίχνευση σύγκρουσης:

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

2. Αρχικοποίηση μετρητή Backoff:

* Αρχικοποιείται ένας μετρητής backoff. Η αρχική τιμή είναι συνήθως `cwmin` (ελάχιστο παράθυρο διαμάχης), μια σταθερή τιμή που ορίζεται από το πρότυπο (π.χ. 31 σε περίπου 802.11 διαμορφώσεις). Αυτός ο μετρητής αντιπροσωπεύει τον αριθμό των χρονικών υποδοχών που ο κόμβος πρέπει να περιμένει πριν επιχειρήσει αναμετάδοση. Μια υποδοχή χρόνου είναι ένα σύντομο, προκαθορισμένο διάστημα.

3. Τυχαίο backoff:

* Ένας τυχαίος αριθμός παράγεται ομοιόμορφα μεταξύ 0 και της τρέχουσας τιμής του μετρητή backoff (`cw`). Αυτός ο τυχαίος αριθμός καθορίζει τη συγκεκριμένη καθυστέρηση πριν από την αναμετάδοση. Αυτή η τυχαιότητα βοηθά στην αποφυγή επίμονων συγκρούσεων που θα μπορούσαν να συμβούν εάν όλοι οι κόμβοι αναμεταδίδονται ακριβώς την ίδια στιγμή.

4. Μείωση του μετρητή Backoff:

* Ο κόμβος περιμένει τον τυχαίο αριθμό χρονικών υποδοχών. Κατά τη διάρκεια αυτής της περιόδου αναμονής, ο κόμβος συνεχίζει να αισθάνεται το κανάλι. Εάν το κανάλι είναι σαφές, μειώνει τον μετρητή backoff σε κάθε χρονική στιγμή μέχρι να φτάσει το μηδέν.

5. Αναμετάδοση:

* Όταν ο πάγκος backoff φτάσει στο μηδέν, ο κόμβος προσπαθεί να επαναμεταδοτήσει το πλαίσιο.

6. Ανάλυση σύγκρουσης:

* Εάν συμβεί μια άλλη σύγκρουση, το παράθυρο διαμάχης (`cw`) διπλασιάζεται (ή αυξάνεται σύμφωνα με έναν συγκεκριμένο αλγόριθμο εντός του προτύπου), μέχρι μέγιστη τιμή (` cwmax`). Αυτό εξασφαλίζει ότι οι κόμβοι εξαπλώνονται από τις προσπάθειές τους για ένα μεγαλύτερο χρονικό διάστημα, μειώνοντας την πιθανότητα περαιτέρω συγκρούσεων.

7. Εκθετικό backoff:

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

8. Παράδειγμα:

Ας πούμε ότι το `cwmin` είναι 31 και το` cwmax` είναι 1023.

* 1η σύγκρουση: `Cw` =31. Τυχαία καθυστέρηση:0-31 Χρονικές υποδοχές.

* 2η σύγκρουση: `Cw` =63 (διπλασιάστηκε). Τυχαία καθυστέρηση:0-63 Χρονικές υποδοχές.

* 3η σύγκρουση: `Cw` =127. Τυχαία καθυστέρηση:0-127 χρονικές υποδοχές.

* ... και ούτω καθεξής, μέχρι να φτάσει το `cw` 'cwmax' ή το πλαίσιο μεταδίδεται με επιτυχία.

Λεπτομέρειες εφαρμογής (802.11 Παράδειγμα):

Η ακριβής υλοποίηση ποικίλλει ελαφρώς ανάλογα με το συγκεκριμένο πρότυπο 802.11 (π.χ., 802.11a, 802.11b, 802.11g, 802.11n, 802.11ax). Οι λεπτομέρειες θα ενσωματωθούν στο υλικολογισμικό ή στο πρόγραμμα οδήγησης της κάρτας διασύνδεσης ασύρματου δικτύου (NIC). Αυτές οι λεπτομέρειες περιλαμβάνουν:

* Ειδικές τιμές των `cwmin` και` cwmax '.

* Ο ακριβής αλγόριθμος για τον διπλασιασμό ή την αύξηση του παραθύρου διαμάχης.

* Μηχανισμοί για τη διαχείριση διαφόρων τύπων σφαλμάτων και συνθηκών καναλιού.

Στην ουσία, ο λογαριθμικός αλγόριθμος backoff αποτελεί βασικό στοιχείο στην κατασκευή του CSMA/CA αποτελεσματική στη διαχείριση της ταυτόχρονης πρόσβασης σε ένα κοινό ασύρματο μέσο, στην αποφυγή καταστροφικών συγκρούσεων και στην αποτελεσματική επικοινωνία.