Κανάλια πολλαπλής πρόσβασης

Κανάλια πολλαπλής πρόσβασης

• Ο όρος "Multiaccess" σημαίνει ότι το φυσικό μέσο μοιράζεται από περισσότερους από δύο κόμβους.
• Ένας δέκτης μπορεί να "ακούσει" πολλούς πομπούς.
• Ένας πομπός μπορεί να "ακουστεί" από πολλούς δέκτες.
• Το κύριο πρόβλημα είναι η κατανομή του καναλιού μεταξύ των χρηστών, καθώς οι κόμβοι δεν γνωρίζουν πότε πρέπει να στείλουν οι άλλοι.
• Παραδείγματα τοπολογιών πολλαπλής πρόσβασης περιλαμβάνουν δορυφορικά δίκτυα, ασύρματα δίκτυα και LAN (Ethernet, Token Ring).
• Το upstream κανάλι είναι συνήθως πολλαπλής πρόσβασης.

Δύο κύριες μέθοδοι πρόσβασης

• Υπάρχουν δύο κύριες μέθοδοι πρόσβασης: μεθόδους δεσμευμένης πρόσβασης και μεθόδους πρόσβασης ανταγωνισμού.

Μέθοδοι δεσμευμένης πρόσβασης

• TDM ή FDM: Κάθε κόμβος λαμβάνει ένα σταθερό τμήμα της χωρητικότητας.
• Απαιτείται η γνώση του αριθμού των χρηστών, ο οποίος συνήθως πρέπει να είναι σταθερός.
• Πολύ αναποτελεσματικό για κανάλια πολλαπλής πρόσβασης με χαμηλή κίνηση.
• Συστήματα Polling: Ένας κύριος κόμβος κατανέμει κανάλια μεταξύ των κόμβων.
• Όταν ένας κόμβος δεν έχει δεδομένα, σπαταλάται χρόνος για ένα polling και μια απάντηση.
• Token Ring: Ένα token κυκλοφορεί και ένας κόμβος μπορεί να μεταδώσει μόνο εάν έχει το token.

Μέθοδοι πρόσβασης ανταγωνισμού

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

Ζητήματα για συστήματα ανταγωνισμού

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

Επίπεδο ελέγχου Data Link Control (DLC).

• Το επίπεδο ελέγχου Data Link (DLC) διαιρείται σε δύο υποεπίπεδα προσανατολισμένα στη λειτουργικότητα.
• Το επίπεδο Data Link περιέχει το Data Link Control (LLC) και το Multiple-Access Control (MAC).
• Το LLC ευθύνεται για τον έλεγχο σφαλμάτων και ροής.
• Το MAC είναι υπεύθυνο για τη διαμόρφωση, τις διευθύνσεις MAC και τον έλεγχο πολλαπλής πρόσβασης.

Υποθέσεις πολλαπλής πρόσβασης

• Slotted System: Κάθε πακέτο απαιτεί 1 μονάδα χρόνου (slot) για μετάδοση. Όλοι οι πομποί είναι συγχρονισμένοι και οι μεταδόσεις ξεκινούν στα όρια των slots.
• Perfect Reception ή Total Collision: Τα πιο σύνθετα μοντέλα θα περιελάμβαναν θόρυβο, σφάλματα και φαινόμενα capture.
• Reliable και Immediate Feedback: (idle, success, collision). Τα πιο σύνθετα μοντέλα θα επέτρεπαν εσφαλμένα ή καθυστερημένα feedback.
• Poisson Arrivals: Συνολικός ρυθμός άφιξης 2 < 1 πακέτο ανά slot (2/m ανά κόμβο).
• Πακέτα που συγκρούονται πρέπει να μεταδοθούν ξανά.
  • Πεπερασμένος αριθμός m πομπών με buffer = 1, ή άπειρος αριθμός πομπών (m = ∞).
  • Οι Backlogged πομποί δεν δέχονται νέα πακέτα.

Πρωτόκολλο Aloha με σχισμές (Slotted Aloha)

• Εάν ένα νέο πακέτο φτάσει κατά τη διάρκεια μιας σχισμής (slot), μεταδίδεται στην επόμενη.
• Εάν μια μετάδοση συγκρουστεί με μια άλλη, ο κόμβος γίνεται backlogged.
• Όσο ο κόμβος παραμένει backlogged, μεταδίδει σε κάθε σχισμή με πιθανότητα q, μέχρι η μετάδοση να γίνει επιτυχώς (και ο κόμβος βγαίνει από τη backlog κατάσταση).
• Η κατάσταση του συστήματος είναι ο αριθμός των backlogged κόμβων η.
• Το σύστημα μπορεί να αναπαρασταθεί από μια αλυσίδα Markoν με πιθανότητες μετάβασης Ρ.

Απόδοση του Slotted Aloha

• Απόδοση = (μακροπρόθεσμο) κλάσμα των επιτυχών σχισμών.
• Έστω ότι υπάρχουν m κόμβοι και ο καθένας στέλνει στην διάρκεια μιας σχισμής με μια μικρή πιθανότητα p, έτσι ώστε mp=G=συγκεκριμένο.
• G=συνολικός μέσος αριθμός προσπαθειών ανά σχισμή.
• Η πιθανότητα ένας συγκεκριμένος κόμβος να είναι επιτυχής είναι p(1-p)^(m-1).
• Η πιθανότητα κάποιος κόμβος να είναι επιτυχής είναι Psuccess = mp(1-p)^(m-1) = G(1-G/m)^(m-1) ≈ G(1-G/m)^m → Ge^(-G) όταν m → ∞.
• Poisson κατανομή με μέσο G για μια τ.μ. k
• Prob (k μεταδόσεις)= Gk 'e-G/k!, k=0,1,2,..... (εδώ είναι ο αριθμός των προσπαθειών σε 1 slot)
• E(k)=G
• Psuccess = Prob (k=1)= G'e-G
• Pidle= Prob (k=0) = e-G
• Pcollision=1 - G'e-G - e-G
• Η κατάσταση (αριθμός backlog χρηστών) αυξηθεί πέρα από το σημείο ασταθούς ισορροπίας, τότε τείνει να παει προς το άπειρο
• Αν διαλέξουμε μικρό q₁, τότε μειώνεται το backlog μετά το οποίο έχουμε αστάθεια (επειδή G(n)=x+nq₁), αλλά αυξάνεται η καθυστέρηση (ο μέσος χρόνος μεταξύ επαναπροσπαθειών είναι 1/q)
• Για G(n)=λ+nq=1 έχουμε το μεγαλύτερο throughput P success

Παράδειγμα (κυψελωτη τηλεφωνία)

• Στην κυψελωτή τηλεφωνία χρησιμοποιείται συχνά TDM (ή συνδυασμός FDM/TDM).
• Για το Control Channel χρησιμοποιείται το Slotted Aloha.
• Το Control Channel είναι η σχισμή 0.
• Τα Data Channels είναι οι σχισμές 1-15.

Pure (unslotted) Aloha

• Οι νέες αφίξεις μεταδίδονται άμεσα (δεν υπάρχουν σχισμές).
• Τα πακέτα μπορούν να έχουν μεταβλητά μήκη, αλλα για την ανάλυση του συστήματος θα υποθέσουμε ότι όλα τα πακέτα έχουν ίδιο μήκος και απαιτούν 1 χρονική μονάδα για να μεταδοθούν.
• Ένα backlogged πακέτο αναμεταδίδεται μετά από τυχαίο χρόνο τ με συνάρτηση f(t)= x. e-tx (E(τ)=1/x)
• Όπου x = ο ρυθμός αναμετάδοσης ανα backlogged node (σταθερα)
• Οι χρονικές στιγμές στις οποίες οι αναμεταδόσεις ξεκινούν είναι μια (χρονικά μεταβαλλόμενη) διαδικασία Poisson ρυθμού
• G(n) = λ + nx, όπου n = ο αριθμός των backlogged κόμβων
• Μια προσπάθεια μετάδοσης συγκρούεται με μια άλλη, αν η προηγούμενη δεν έχει τελειώσει ή η επόμενη ξεκινήσει πολύ νωρίς
• Pr (καμία άλλη προσπάθεια σε διάστημα 2 χρονικών μονάδων) = e-2G(n)
• Ρυθμαπόδοση(αριθμός επιτυχημένων μεταδόσεων ανά σχισμή) = = G(n)e-2G(n)
• Μέγιστη ρυθμαπόδοση (max throughput) = 1/(2e) (≈0.18) όταν G(n) = 1/2
• Τα θέματα ευστάθειας είναι παρόμοια με εκείνα του Aloha με σχισμές (slotted Aloha)
• Τα πλεονεκτήματα του «καθαρού» Aloha είναι η απλότητα, η δυνατότητα για άνισα μήκη πακέτων, και η έλλειψη ανάγκης συγχρονισμού.

Αλγόριθμοι διαμοιρασμού (Splitting Algorithms)

• Ένας πιο αποδοτικός τρόπος να χρησιμοποιηθεί το idle/success/collision feedback
• Ας υποθέσουμε προς στιγμην ότι μόνο 2 πακέτα εμπλέκονται σε μια σύγκρουση
• Υποθέτουμε ότι όλοι οι άλλοι κόμβοι «παραμένουν σιωπηλοί» μέχρι να διευθετηθεί η σύγκρουση, ενώ οι κόμβοι που ενέχονται στη σύγκρουση μεταδίδουν ο καθένας με πιθανότητα 1/2 μέχρι κάποιος να μεταδώσει με επιτυχία
• Στην επόμενη σχισμή, μετά από αυτή την επιτυχημένη μετάδοση, μεταδίδει ο άλλος κόμβος
• Ο αναμενόμενος αριθμός σχισμών μέχρι την πρώτη επιτυχημένη προσπάθεια είναι 2 και συνεπώς ο αναμενόμενος αριθμός σχισμών για να μεταδοθούν και τα δύο πακέτα είναι 3 σχισμές Σ2-(2-1) = 1/(1-1/2)2 - 1=3

Αλγόριθμοι δέντρου (Tree Algorithms ή Splitting Algorithms)

• Μετά από μια σύγκρουση, όλες οι νέες αφίξεις και όλα τα backlogged πακέτα, που δε συμμετείχαν στη σύγκρουση, περιμένουν.
• Τα πακέτα κάθε σύγκρουσης μπαίνουν είτε σε ένα σύνολο μετάδοσης είτε σε ένα σύνολο αναμονής
• Ο b αποφασίζει να περιμένει για τη διευθέτηση της σύγκρουσης
• Γενικά, κάθε κόμβος που περιμένει βρίσκεται σε μια στοίβα.
• Ο κόμβος κατεβαίνει 1 θέση στην στοίβα σε κάθε σύγκρουση και ανεβαίνει 1 θέση σε κάθε επιτυχημένη μετάδοση (success) ή κενό (idle).
• Η δεύτερη σύγκρουση μεταξύ των πακέτων a και c δεν είναι απαραίτητη. Γενικά, όταν μια σύγκρουση ακολουθείται από ένα idle slot, το υποσύνολο που περιμένει από την πρώτη σύγκρουση πρέπει να διαμοιραστεί ξανά

Οι καλύτεροι αλγόριθμοι με μορφή δέντρου έχουν μέγιστη ρυθμαπόδοση 0.4878

Σταθεροποιημένο καθαρό Aloha: 0.184 = 1/(2e) Σταθεροποιημένο Aloha με σχισμές: 0.368= 1/e

Αλγόριθμος με μορφή δέντρου (όπως αρχικά περιγράφεται): 0.434 Αλγόριθμος με μορφή δέντρου (μετά από τροποποίηση): 0.46 Ο καλύτερος αλγόριθμος διαμοίρασης: 0.4878 Άνω όριο (για άπειρο αριθμό κόμβων): 0.568

• Η πολυπλεξία με διαίρεση χρόνου (TDM) μπορεί να πετύχει ρυθμαποδόσεις μέχρι 1 πακέτο ανά σχισμή, αλλά η καθυστέρηση αυξάνεται γραμμικά με τον αριθμό των κόμβων.
• Η καθυστέρηση για το σταθεροποιημένο Aloha και για αλγόριθμους δέντρου είναι ουσιαστικά ανεξάρτητη του αριθμού των κόμβων

Πλεονέκτημα των ALOHA protocols:

• Χαμηλή καθυστέρηση όταν το φορτίο είναι μικρό (οπότε οι συγκρούσεις είναι σπάνιες)
• Αν ένας κόμβος έχει πλαίσια να στείλει, μπορεί να στέλνει συνέχεια στον πλήρη ρυθμό του καναλιού (R bps) εφόσον είναι ο μόνος κόμβος με πλαίσια. (στο TDM θα στέλνε με ρυθμο R/m)
• Απλό στην υλοποίηση (πχ, δεν απαιτείται master station)
• Εύκολο να μπουν και να βγουν κόμβοι στο δίκτυο

Μειονέκτημα

• Αν και οι m κόμβοι έχουν traffic, μπορει να συμβουν πολλές συγκρουσεις και ο ρυθμος που θα στειλει στην πράξη ο καθενας δεν θα είναι R/m bps (κατά μέσον όρο) αλλά 0.18 R/m bps (unslotted Aloha) ή 0.36 R/m bps (slotted Aloha)