SEN2008 · 4. hafta · Data Link Layer Concepts (II) : Channel allocation problem, multiple Access, Ethernet

Kanal tahsisi ve çoklu erişim: ALOHA, CSMA, CSMA/CD

Birçok düğüm tek bir yayın kanalını paylaşınca kim ne zaman konuşur? Statik tahsisin kusuru, pure ve slotted ALOHA verimliliği, CSMA/CD, minimum çerçeve boyu ve binary exponential backoff.

channel allocation problembroadcast channelmultiple access protocolFDMA / TDMAcollisionpure ALOHAslotted ALOHAvulnerable periodCSMACSMA/CDbinary exponential backoffminimum frame sizetaking-turns protocolspollingtoken passing

Ethernet’in ilk halinde, Wi-Fi’da, uydu linkinde ortak bir sorun var: birçok düğüm tek bir yayın kanalını (broadcast channel) paylaşıyor. İki düğüm aynı anda gönderirse sinyaller üst üste biner, ikisi de bozulur. Buna çarpışma (collision) denir. Çoklu erişim protokolü (multiple access protocol), kimin ne zaman göndereceğine merkezi bir otorite olmadan karar veren kurallar kümesidir.

Sınavda bu konu iki yerden vurur: ALOHA verimlilik hesabı ve CSMA/CD’de minimum çerçeve boyu. Altın kurallar:

Slotted ALOHA $1/e$ , pure ALOHA $1/(2e)$ . Pure’da tehlikeli aralık iki çerçeve süresi.
N düğüm, $p$ olasılık: başarı $= Np(1-p)^{N-1}$ .
$L_{min} = 2 d_{prop} R$ . Çarpışmayı gönderim bitmeden duymak zorundasın.
Backoff aralığı her çarpışmada ikiye katlanır.

Kanal tahsisi problemi

İdeal bir paylaşımlı kanal (hızı $R$ ) şunları sağlamalı:

Tek düğüm gönderiyorsa tüm $R$ ‘yi kullanabilsin.
$M$ düğüm gönderiyorsa her biri ortalama $R/M$ alsın.
Merkezi bir koordinatör olmasın (tek arıza noktası olmasın).
Basit ve ucuz olsun.

Statik tahsis neden kötü?

En basit çözüm kanalı sabit parçalara bölmek: FDMA (frekans) ya da TDMA (zaman). Her düğüm kendi dilimini kullanır. Sorun: düğüm sustuğunda dilimi boş gider, konuşan düğüm ise sadece $R/N$ alır. Kuyruk teorisinden basit bir model ortalama gecikmeyi verir:

$T = \frac{1}{\mu C - \lambda}$

Burada $C$ kanal kapasitesi (bps), $1/\mu$ ortalama çerçeve boyu (bit), $\lambda$ geliş hızı (çerçeve/s).

C = 100 Mbps, çerçeve 10,000 bit, lambda = 5000 çerçeve/s
mu C = 10^8 / 10^4 = 10,000 çerçeve/s
Tek kanal       : T = 1 / (10,000 - 5,000) = 0.2 ms
10 alt kanal    : her biri C/10 ve lambda/10
                  T = 1 / (1,000 - 500)    = 2 ms  (10 kat)

Statik bölmede gecikme $N$ katına çıkar. Bilgisayar trafiği patlamalı olduğu için dinamik paylaşım gerekir.

Protokol aileleri

Aile	Fikir	Örnek
Kanal bölme (channel partitioning)	Sabit dilimler	TDMA, FDMA, CDMA
Rastgele erişim (random access)	Herkes tam hızda gönderir, çarpışınca rastgele bekler	ALOHA, CSMA, CSMA/CD
Sıralı (taking turns)	Düğümler sırayla konuşur	Polling, token passing

ALOHA

Hawaii Üniversitesi’nde adalar arası radyo ağı için geliştirildi. Rastgele erişimin atasıdır.

Pure ALOHA

Düğümün çerçevesi olunca hemen gönderir. Çarpışırsa rastgele bir süre bekler, tekrar dener. Bir çerçevenin süresi $T$ olsun ve çerçevemiz $t_0$ ‘da başlasın.

     t0 - T           t0            t0 + T
       |--------------|---------------|
       bu aralıkta     bu aralıkta
       başlayan çarpar başlayan çarpar
       tehlikeli aralık (vulnerable period) = 2T

$G$ , çerçeve süresi başına ortalama deneme sayısı (yeni + tekrar) olsun. Denemeler Poisson dağılımlı varsayılırsa $2T$ aralıkta hiç başka deneme olmaması olasılığı $e^{-2G}$ :

$S_{pure} = G\,e^{-2G}, \qquad S_{max} = \frac{1}{2e} \approx 0.184 \text{ (G = 0.5'te)}$

Slotted ALOHA

Zaman çerçeve süresi uzunluğunda slotlara bölünür. Düğümler sadece slot başında gönderebilir. Çarpışma ancak aynı slotu seçenler arasında olur, tehlikeli aralık $T$ ‘ye iner:

$S_{slotted} = G\,e^{-G}, \qquad S_{max} = \frac{1}{e} \approx 0.368 \text{ (G = 1'de)}$

Kitapların diğer modeli $N$ düğüm ve her düğümün her slotta $p$ olasılıkla göndermesi:

$P(\text{başarılı slot}) = N p (1-p)^{N-1}$

En iyi $p = 1/N$ . $N \to \infty$ iken bu $1/e$ ‘ye yakınsar.

Çözümlü örnek

$N = 5$ , $p = 0.2$ :

başarı    : 5 x 0.2 x 0.8^4         = 0.4096
boş slot  : 0.8^5                   = 0.32768
çarpışma  : 1 - 0.32768 - 0.4096    = 0.26272
pure ALOHA aynı N, p : N p (1-p)^(2(N-1)) = 0.8^8 = 0.1678

1 Mbps’lik slotted ALOHA kanalında en iyi durumda faydalı throughput $10^6/e \approx 368$ kbps.

TUZAK · $G$ ile $S$ farkı. $G$ deneme yükü (çarpışanlar dahil), $S$ başarılı çerçeve oranı. $G$ 1’i geçebilir, $S$ asla geçemez. $G$ çok büyükse neredeyse her slot çarpışır, $S \to 0$ .

CSMA: göndermeden önce dinle

ALOHA kaba: kanal doluyken bile gönderir. CSMA (carrier sense multiple access) önce kanalı dinler.

1-persistent: kanal boşsa hemen gönder, doluysa boşalmasını bekle ve hemen gönder. Bekleyen iki düğüm boşalınca kesin çarpışır.
Non-persistent: kanal doluysa rastgele bekle, sonra tekrar dinle.
p-persistent: (slotlu) kanal boşsa $p$ olasılıkla gönder, $1-p$ ile bir slot ertele.

Dinlemek çarpışmayı bitirmez. Propagation gecikmesi yüzünden B, A’nın sinyali henüz ona ulaşmadığı için kanalı boş sanıp gönderebilir. Propagation ne kadar uzunsa (kablo uzun) çarpışma o kadar olasıdır.

CSMA/CD: gönderirken de dinle

Klasik Ethernet’in protokolü. CD (collision detection): düğüm gönderirken kanalı dinlemeye devam eder. Kendi sinyalinden farklı bir şey duyarsa:

Gönderimi hemen keser (bozuk çerçeveyi sonuna kadar göndermenin anlamı yok).
Herkesin fark etmesi için 48 bitlik bir jam sinyali yollar.
Binary exponential backoff ile rastgele bekler, sonra baştan dener.

Minimum çerçeve boyu

En kötü durum: A ve B kablonun iki ucunda. A göndermeye başlar. Sinyali B’ye varmadan hemen önce B de başlar. Çarpışmanın haberi A’ya $2 d_{prop}$ sonra döner. A o anda hâlâ gönderiyor olmalı, yoksa çarpışmayı kendi çerçevesine bağlayamaz:

$\frac{L}{R} \ge 2 d_{prop} \quad\Longrightarrow\quad L_{min} = 2\,d_{prop}\,R$

R = 10 Mbps, kablo 2500 m, s = 2 x 10^8 m/s
dprop = 2500 / 2e8 = 12.5 us
Lmin  = 2 x 12.5e-6 x 1e7 = 250 bit

Gerçek Ethernet tekrarlayıcı (repeater) gecikmelerini de hesaba katıp 512 bit (64 byte) seçti. Hızı 10 katına çıkarınca aynı 512 bit için izin verilen mesafe 10 kat küçülür: 10 Mbps’te 5120 m, 100 Mbps’te 512 m (sadece propagation hesabıyla).

Binary exponential backoff

$n$ . ardışık çarpışmadan sonra düğüm $K$ ‘yi rastgele seçer:

$K \in \{0, 1, \ldots, 2^{\min(n,10)} - 1\}, \qquad \text{bekleme} = K \times 512 \text{ bit süresi}$

Çarpışma	$K$ aralığı	10 Mbps’te en uzun bekleme	İki düğümün yine çarpışma olasılığı
1	0, 1	51.2 µs	1/2
2	0..3	153.6 µs	1/4
3	0..7	358.4 µs	1/8
10 ve sonrası	0..1023	52.4 ms	1/1024

16 denemeden sonra çerçeve bırakılır ve üst katmana hata bildirilir. Fikir: çarpışmalar yük çok demek; aralığı büyüterek yük arttıkça herkesi daha çok yayarsın.

Ethernet verimi

Çok düğümün hep gönderecek çerçevesi olduğu durumda yaklaşık:

$\text{verim} = \frac{1}{1 + 5\,d_{prop}/d_{trans}}$

dprop = 12.5 us
1500 byte çerçeve @10 Mbps : dtrans = 1200 us -> 1/(1 + 0.052) = 0.950
64 byte çerçeve   @10 Mbps : dtrans = 51.2 us -> 1/(1 + 1.22)  = 0.450

Çerçeve uzun, kablo kısa olunca verim 1’e yaklaşır.

Sıralı (taking-turns) protokoller

Polling: bir ana düğüm (master) sırayla her düğüme “gönderecek bir şeyin var mı?” diye sorar. Çarpışma yok, ama sorgulama gecikmesi var ve master çökerse ağ durur. Bluetooth böyle çalışır.
Token passing: özel bir jeton çerçevesi düğümden düğüme dolaşır; sadece jetonu tutan gönderir. Çarpışma yok, ama jeton kaybolursa ya da bir düğüm onu bırakmazsa sorun çıkar.

Kablosuz ortam: neden CD olmaz?

Wi-Fi’da düğüm gönderirken kendi güçlü sinyali, uzaktan gelen zayıf sinyali bastırır; çarpışmayı duyamaz. Ayrıca gizli terminal (hidden terminal) sorunu var: A ve C birbirini duymaz ama ikisi de B’ye gönderir. Bu yüzden 802.11, çarpışmayı tespit etmek yerine önlemeye çalışır (CSMA/CA): rastgele geri sayım, her çerçeveye ACK, isteğe bağlı RTS/CTS rezervasyonu.

İPUCU · güvenlik bağlantısı. Paylaşımlı ortamda her düğüm her çerçeveyi görür; kart sadece kendine geleni üst katmana verir. Kartı “promiscuous mode”a alan biri tüm trafiği okuyabilir. Paylaşımlı ve kablosuz ağlarda gizliliği sağlayan şey ortam değil, şifrelemedir.

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
Slotted ALOHA max 0.184	Slotted $1/e = 0.368$ , pure $1/(2e) = 0.184$ .
Pure ALOHA tehlikeli aralığı $T$	$2T$ : öncesi ve sonrası.
Başarı olasılığı $p(1-p)^{N-1}$	Bu belli bir düğüm için. Herhangi biri için $N$ ile çarp.
$L_{min} = d_{prop} R$	$2 d_{prop} R$ : haber geri dönmeli.
CSMA çarpışmayı tamamen önler	Propagation yüzünden yine çarpışma olur.
Backoff’ta $K \in \{0, \ldots, 2^n\}$	Üst sınır $2^n - 1$ , ve $n$ en fazla 10.
Hız artınca ağ çapı aynı kalır	Aynı $L_{min}$ için çap hızla ters orantılı küçülür.
Wi-Fi CSMA/CD kullanır	CSMA/CA; kablosuzda çarpışma tespiti pratik değil.

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1kolay

What is the maximum efficiency of slotted ALOHA as the number of nodes grows large?

$1/(2e) \approx 0.184$
$1/e \approx 0.368$
$0.5$
$1$

Cevabı göster

1/e \approx 0.368

Slotted ALOHA: $S = G e^{-G}$ , en büyük değer $G = 1$ 'de $1/e \approx 0.368$ .
Pure ALOHA'da tehlikeli aralık iki kat olduğu için $1/(2e) \approx 0.184$ .

Soru 2orta

In slotted ALOHA, 5 active nodes each transmit in a slot with probability $p = 0.2$ . What is the probability that a given slot is a success (exactly one transmission)?

Cevabı göster

0.4096

$S = N p (1-p)^{N-1} = 5 \times 0.2 \times 0.8^4 = 1 \times 0.4096 = 0.4096$ . $p = 1/N$ seçildiği için bu N = 5 için en iyi değer. N büyüdükçe $1/e$ 'ye iner.

Soru 3orta

Same setting (5 nodes, $p = 0.2$ ). What fraction of slots are idle, and what fraction contain a collision?

Cevabı göster

idle 0.32768, collision 0.26272

Boş slot: hiç kimse göndermiyor, $(1-p)^5 = 0.8^5 = 0.32768$ .
Çarpışma: geri kalan $1 - 0.32768 - 0.4096 = 0.26272$ .
Üç olasılığın toplamı 1 olmalı.

Soru 4orta

In pure ALOHA, the offered load is $G = 0.5$ frames per frame time. What is the throughput $S$ ?

Cevabı göster

≈ 0.184

Pure ALOHA: $S = G e^{-2G} = 0.5 \times e^{-1} \approx 0.184$ .
Bu aynı zamanda pure ALOHA'nın maksimumu: $G = 0.5$ 'te.
Slotted ALOHA'da aynı yükte $0.5 e^{-0.5} \approx 0.303$ olurdu.

Soru 5kolay

Why is the vulnerable period of pure ALOHA twice the frame time?

Because frames are twice as long as in slotted ALOHA
Because a frame collides with any other frame that starts within one frame time before or after it
Because the sender transmits each frame twice
Because acknowledgements take one frame time

Cevabı göster

B) Because a frame collides with any other frame that starts within one frame time before or after it

Çerçeve $t_0$ 'da başlıyor, süre $T$ . $[t_0 - T, t_0]$ arasında başlayan bir çerçevenin kuyruğu bizimkinin başına, $[t_0, t_0 + T]$ arasında başlayan ise bizimkinin kuyruğuna çarpar. Toplam $2T$ .
Slotlama başlangıçları hizaladığı için tehlikeli aralığı $T$ 'ye indirir ve verimi ikiye katlar.

Soru 6orta

A CSMA/CD network runs at 10 Mbps over a 2500 m cable with propagation speed $2 \times 10^8$ m/s. What is the minimum frame size (in bits) so that a collision is always detected while still transmitting?

Cevabı göster

250 bits

$d_{prop} = 2500 / (2 \times 10^8) = 12.5\ \mu s$ .
En kötü durumda çarpışmanın haberi $2 d_{prop}$ sonra gelir. Gönderici bu sürede hâlâ gönderiyor olmalı: $L_{min} = 2 d_{prop} R = 2 \times 12.5 \times 10^{-6} \times 10^7 = 250$ bit.

Soru 7zor

A 100 Mbps CSMA/CD segment has propagation speed $2 \times 10^8$ m/s and minimum frame size 512 bits. What is the maximum distance between two stations?

Cevabı göster

512 m

$L_{min} = 2 d_{prop} R \Rightarrow d_{prop} = 512 / (2 \times 10^8) = 2.56\ \mu s$ .
Mesafe $= 2.56 \times 10^{-6} \times 2 \times 10^8 = 512$ m.
Hız 10 kat artınca (10 Mbps'te 5120 m olurdu) aynı minimum çerçeve için ağ çapı 10 kat küçülür.

Soru 8orta

In Ethernet's binary exponential backoff at 10 Mbps, after the 3rd consecutive collision a node picks $K$ at random. What is the range of $K$ , and what is the longest possible wait?

Cevabı göster

K ∈ {0,...,7}; 358.4 µs

$n$ . çarpışmadan sonra $K \in \{0, 1, \ldots, 2^{\min(n,10)} - 1\}$ . $n = 3$ : $\{0, \ldots, 7\}$ .
Bekleme $K \times 512$ bit süresi. 10 Mbps'te 512 bit $= 51.2\ \mu s$ .
En uzun: $7 \times 51.2 = 358.4\ \mu s$ .

Soru 9zor

Two nodes have just collided for the 2nd time and both run binary exponential backoff. What is the probability that they collide again on their next attempt (they collide if they pick the same $K$ )?

Cevabı göster

1/4

2. çarpışmadan sonra her biri $K$ 'yi $\{0, 1, 2, 3\}$ 'ten bağımsız seçer.
Aynı değeri seçme olasılığı $\sum_{k} (1/4)(1/4) = 4 \times 1/16 = 1/4$ .
1. çarpışmadan sonra bu 1/2, 3.'den sonra 1/8 olur: her çarpışma riski yarıya indirir.

Soru 10orta

Using the approximation $\text{efficiency} = 1/(1 + 5\,d_{prop}/d_{trans})$ , what is Ethernet's efficiency when $d_{prop} = 12.5\ \mu s$ and frames are 1500 bytes at 10 Mbps?

Cevabı göster

≈ 0.950

$d_{trans} = 12000 / 10^7 = 1.2$ ms $= 1200\ \mu s$ . $5 d_{prop}/d_{trans} = 62.5 / 1200 \approx 0.052$ . $1/(1.052) \approx 0.950$ . Uzun çerçeve ve kısa kablo verimi 1'e yaklaştırır.

Soru 11zor

A link of capacity 100 Mbps carries frames with mean length 10,000 bits arriving at 5000 frames/s. Using the static-allocation queueing formula $T = 1/(\mu C - \lambda)$ , what is the mean delay on the full channel, and what is it if the channel is split statically into 10 equal FDM subchannels each receiving 1/10 of the traffic?

Cevabı göster

0.2 ms; 2 ms

$\mu C = 10^8 / 10^4 = 10{,}000$ çerçeve/s. $T = 1/(10000 - 5000) = 0.2$ ms.
10'a bölünce her alt kanal $C/10$ , trafik $\lambda/10$ : $T_N = 1/(1000 - 500) = 2$ ms, yani $N \cdot T$ .
Statik bölme gecikmeyi N katına çıkarır. Patlamalı trafikte dinamik paylaşımın gerekçesi bu.

Soru 12kolay

Which multiple access protocol is used by classic shared Ethernet, and which by Wi-Fi?

Ethernet: CSMA/CA; Wi-Fi: CSMA/CD
Ethernet: CSMA/CD; Wi-Fi: CSMA/CA
Both use token passing
Ethernet: slotted ALOHA; Wi-Fi: polling

Cevabı göster

B) Ethernet: CSMA/CD; Wi-Fi: CSMA/CA

Kablolu ortamda gönderirken dinleyip çarpışmayı fark etmek mümkün: CSMA/CD.
Kablosuzda kendi güçlü sinyalin zayıf gelen sinyali bastırır ve gizli terminal (hidden terminal) sorunu var, çarpışma tespit edilemez. Bu yüzden Wi-Fi çarpışmayı önlemeye çalışır (CSMA/CA, ACK, isteğe bağlı RTS/CTS).

Doğrulama: ALOHA verimleri, N düğümlü başarı olasılıkları, statik tahsis gecikmesi, CSMA/CD minimum çerçeve, Ethernet verim formülü ve backoff süreleri node ile hesaplandı (verify/SEN2008/04.mjs).

Deftere not kartı

Statik tahsis (FDM/TDM): T = 1/(muC - lambda), N parçaya bölünce N x T -> patlamalı trafikte kötü Slotted ALOHA: S = G e^-G, max 1/e = 0.368 (G=1) N düğüm: N p (1-p)^(N-1) Pure ALOHA: S = G e^-2G, max 1/(2e) = 0.184 (G=0.5) tehlikeli aralık 2T boş slot (1-p)^N ; çarpışma = 1 - boş - başarı CSMA: göndermeden dinle; propagation yüzünden yine çarpışır CSMA/CD: gönderirken dinle, çarpışınca kes + jam sinyali Lmin = 2 dprop R (çarpışmayı gönderim bitmeden duymak için) n. çarpışma: K in {0..2^min(n,10) - 1}, bekle K x 512 bit süresi (10M: 51.2 us) aynı K olasılığı: 1/2, 1/4, 1/8 ... Ethernet verimi = 1 / (1 + 5 dprop/dtrans) Sıralı (taking turns): polling (master sorar), token passing (jeton dolaşır) Kablolu: CSMA/CD Kablosuz (Wi-Fi): CSMA/CA (hidden terminal)