Carrier Sense Multiple Access (CSMA)

Carrier Sense Multiple Access (CSMA) (Ανίχνευση Φέροντος)

• Όλοι οι κόμβοι "ακούν" ο ένας τον άλλο και διακρίνουν αν το κανάλι είναι κατειλημμένο με κάποια καθυστέρηση.
• Οι κόμβοι ξεκινούν τη μετάδοση πακέτων μόνο όταν το κανάλι είναι αδρανές.
• β είναι ο χρόνος για την αναγνώριση ότι το κανάλι είναι κενό (β <<1 μονάδα=μέσος χρόνος μετάδοσης πακέτου).
• t=tprop είναι η καθυστέρηση διάδοσης και ανίχνευσης σε δευτερόλεπτα.
• C είναι η χωρητικότητα καναλιού σε bits/sec.
• L είναι το μέσο μήκος πακέτου σε bits.
• (L/C = 1 μονάδα χρόνου = 1 σχισμή)
• Το CSMA είναι μια "ευγενική" μορφή του Aloha.
• Οι κόμβοι πριν μεταδόσουν ακούνε το κανάλι και αν είναι κενό μεταδίδουν, αλλιώς περιμένουν.
• Max Throughput of CSMA ≈ 1 / (1+2 βeff)

Maximum Propagation Delay

• Maximum propagation delay (tprop) είναι ο χρόνος που χρειάζεται ένα bit ενός frame να ταξιδέψει μεταξύ των δύο πιο απομακρυσμένων σταθμών.

Πολλαπλή Προσπέλαση με Ανίχνευση Φέροντος και Ανίχνευση Σύγκρουσης (CSMA with Collision Detection ή CSMA/CD)

• Το CSMA/CD χρησιμοποιείται ευρέως σε bus topology LANs (IEEE 802.3, Ethernet).
• Σε ένα δίαυλο, οι κόμβοι μπορούν να "ακούν" και να μεταδίδουν ταυτόχρονα.
• Η ανίχνευση σύγκρουσης είναι δυνατή μετά από μια καθυστέρηση διάδοσης (μικρή για τοπικά δίκτυα – LANs).
• Οι κόμβοι μεταδίδουν όταν ανιχνεύσουν ότι το κανάλι είναι αδρανές.
• Όταν 2 κόμβοι μεταδίδουν σχεδόν ταυτόχρονα, ανιχνεύουν τη σύγκρουση και σταματούν.
• Το Ethernet είναι ένα δημοφιλές πρωτόκολλο για LANs, χρησιμοποιεί επίμονο CSMA/CD χωρίς σχισμές με εκθετική οπισθοχώρηση (exponential backoff).

CSMA/CD Προσεγγιστική Ανάλυση

• Το πρωτόκολλο λέει ότι όλοι οι κόμβοι ακούνε τις μεταδόσεις στο κανάλι
• Όταν ένας κόμβος έχει ένα πακέτο να στείλει, αν το κανάλι είναι κενό μεταδίδει, αλλιώς περιμένει για έναν τυχαίο χρόνο (binary exponential backoff).
• Όταν ένας κόμβος αντιληφθεί σύγκρουση, σταματάει τη μετάδοση και περιμένει για έναν τυχαίο χρόνο μέχρι να ξαναπροσπαθήσει
• Αν τ είναι η μέγιστη καθυστέρηση διάδοσης στο καλώδιο, τότε αν γίνει μια σύγκρουση, μπορεί να πάρει μέχρι και 2τ sec μέχρι όλοι οι κόμβοι να αντιληφθούν και να σταματήσουν.

Slotted System

• Εξετάστε ένα σύστημα slotted με "mini-slots" διάρκειας 2τ.
• Εάν ένας κόμβος ξεκινήσει τη μετάδοση στην αρχή ενός mini-slot, είτε δεν συμβαίνει σύγκρουση και η υπόλοιπη μετάδοση δεν διακόπτεται, είτε συμβαίνει σύγκρουση, αλλά μέχρι το τέλος του mini-slot το κανάλι θα είναι πάλι αδρανές.
• Υποθέστε N χρήστες, καθένας προσπαθεί για μετάδοση κατά τη διάρκεια ενός ελεύθερου "mini-slot" με πιθανότητα p. P περιλαμβάνει νέες αφίξεις και επαναμεταδόσεις.
• P(i users attempt) = (N choose i) * p^i * (1-p)^(N-i)
• P(exactly 1 attempt) = P(success) = NP(1-p)^(N-1)
• Για μεγιστοποίηση της P(success): d/dp [NP(1-P)^(N-1)] = 0 => Popt = 1/N
• P(success) = NP(1-1/N)^(N-1) = (1-1/N)^(N-1)
• Pc = limit (N→∞) P(success) = 1/e
• Έστω X = Μέσος αριθμός slots ανά επιτυχημένη μετάδοση => E[X] = 1/Pc = e

Once a mini-slot has been successfully captured

• Once a mini-slot has been successfully captured, transmission continues without interruption.
• New transmission attempts will begin at the next mini-slot after the end of the current packet transmission.
• Έστω S = Μέσος χρόνος μεταξύ επιτυχημένων μεταδόσεων πακέτων.
• S = (e-1)2τ + DTP + τ όπου DTP είναι ο packet transmission time.
• Efficiency = DTP/S = DTP / (DTP + τ + 2τ(e-1))
• Έστω β = τ / DTP => Efficiency ≈ 1/(1+4.4β) = λ < 1/(1+4.4β) και β=τ*C/L
• Οι πιο ακριβείς αναλύσεις δίνουν λίγο διαφορετικό τύπο στην βιβλιογραφία.
• Στην πράξη δεν χρησιμοποιούνται σχισμές, και το CSMA/CD μπορεί να θεωρηθεί ένα σύστημα κρατήσεων όπου τα mini slots χρησιμοποιούνται για να κάνουν κρατήσεις για τα data packets.

CSMA

• Μη-επίμονο CSMA: Το πακέτο γίνεται backlogged.
• Επίμονο CSMA: Μετάδοση μετά την εποχή με πιθανότητα 1.
• p-επίμονο CSMA: Μετάδοση μετά την εποχή με πιθανότητα ρ.

Παραδείγματα CSMA/CD

• Παράδειγμα 1 (Ethernet): Ρυθμός μετάδοσης = 10Mbps, Μήκος πακέτων = 1000 bits, Μήκος καλωδίου=1 km, τ = 5x10-6 sec, β=0.05, e=0.8
• Παράδειγμα 2 (GEO δορυφόρος): Καθυστέρηση διάδοσης = ¼ sec, β = 2500, e ≈ 0
• Το CSMA/CD είναι κατάλληλο μόνο για δίκτυα με μικρές καθυστερήσεις διάδοσης.

Switched LANs

• "Παραδοσιακό" Ethernet: Όλοι οι κόμβοι σε ένα bus, που σημαίνει μακρύ καλώδιο, χρησιμοποιούν CSMA/CD.
• "Hub" Ethernet: Οι κόμβοι συνδέονται σε ένα hub, το οποίο λειτουργεί ως επαναλήπτης, μπορεί να χρησιμοποιηθεί και στα 100 Mbps, πρωτόκολλο CSMA/CD.
• Ευκολότερο να αυξήσεις ή να μειώσεις τον αριθμό των χρηστών και να εντοπίσεις τυχόν भλάβες.
• Switched Ethernet: Δεν χρησιμοποιεί CSMA/CD, είναι εύκολο να αυξήσεις τον ρυθμό μετάδοσης (Gbit Ethernet, 10G Ethernet).
• Οι κόμβοι στέλνουν όποτε θέλουν, το switch αποθηκεύει τα πακέτα και τα στέλνει στον προορισμό.
• Τυπικά ένα switch έχει 20-40 ports και κάθε κόμβος μπορεί να στείλει στο full rate (1/10/100 Gbps).

Ethernet (IEEE 802.3)

• Εφευρέθηκε από τους Bob Metcalfe & David Bogs της Xerox.
• Είναι το πιο δημοφιλές πρωτόκολλο για LANs.
• Υπάρχουν 5 γενιές Ethernet (10Mbps, 100Mbps, 1Gbps, 10Gbps, 40Gbps)
• Τα παραδοσιακά Ethernet χρησιμοποιούν MAC frame.
• Preamble: 7 bytes (56 bits) εναλλασσόμενων 0s και 1s – receiver sync.
• SFD: Start of Frame Delimiter (10101011 – μοναδική αλληλουχία).
• Source Address, Destination Address: 48 bit μοναδικές διευθύνσεις.
• Length: Value up to 1500 bytes.
• Data, Preamble και SFD excluded.

Ελάχιστο και μέγιστο μήκος πλαισίου Ethernet

• Minimum payload length: 46 bytes
• Maximum payload length: 1500 bytes
• Minimum frame length: 512 bits ή 64 bytes
• Maximum frame length: 12,144 bits ή 1518 bytes
• Ελάχιστο μήκος λόγο του CSMA/CD: Το πλαίσιο πρέπει να διαρκεί αρκετά ώστε να "γεμίζει" το κανάλι, το κανάλι έχει ένα συγκεκριμένο μέγιστο μήκος.
• Μέγιστο μήκος για να εξασφαλίσει fair access: Ένας σταθμός δεν θα πρέπει να καταλαμβάνει το κανάλι υπερβολικά πολύ.
• Ethernet διευθύνσεις (ή MAC διευθύνσεις, ή hardware διευθύνσεις, ή layer 2 διευθύνσεις).
• Unicast: 48 bits long
• Broadcast: FF-FF-FF-FF-FF-FF

Conflicts and Vulnerable Time

• Ο επικίνδυνος χρόνος (vulnerable time) για το CSMA είναι 2 χ μέγιστος χρόνος διάδοσης
• Όσο μεγαλύτερος είναι ο χρόνος διάδοσης, τόσο χειρότερη είναι η απόδοση του πρωτοκόλλου.

CSMA/CD Collisions

• Question: How long does it take to detect a collision?
• Answer: In the worst case, twice the maximum propagation delay of the medium
• Note: τ = α = maximum propagation delay

Πως τα LANs χρησιμοποιούν hardware (ή physical) addresses

• Πως τα LANs χρησιμοποιούν hardware (ή physical) addresses για να φιλτράρουν τα πακέτα.
• Π.χ. Ethernet (τα πεδία είναι σε bytes, οι διευθύνσεις hardware διευθύνσεις, όχι IP διευθύνσεις.

Address Resolution Techniques

• Η ΙΡ διεύθυνση πρέπει να μετατραπεί σε hardware διεύθυνση για να σταλεί το πακέτο στο LAN.
• Χρησιμοποιούνται Table Lookup και ARP πρωτόκολλο.
• Εναλλακτικά χρησιμοποιείται κάποιος server για Address Resolution ή caching.