Elementary ve sliding window protokolleri: stop-and-wait, Go-Back-N, Selective Repeat

Önceki sayfada link katmanının hatayı nasıl fark ettiğini gördün. Fark etmek yetmez: bozuk çerçeve atılır, ve verinin yine de karşıya ulaşması gerekir. Bunun yolu ARQ (automatic repeat request): alıcı onay (ACK) yollar, gönderici onay gelmezse yeniden gönderir. Aynı fikirler 7. haftada TCP’de tekrar karşına çıkacak, o yüzden burada sağlam öğren.

Sınav soruları üç kalıptadır: verimlilik hesabı (utilization), “hangi çerçeveler yeniden gönderilir?” izi ve sıra numarası bit sayısı. Altın kurallar:

1. $U = N \cdot (L/R) / (RTT + L/R)$, 1’i geçemez. Stop-and-wait’te $N = 1$.
2. GBN alıcısı sıra dışını atar, SR alıcısı tamponlar.
3. GBN’de pencere $\le 2^k - 1$, SR’de $\le 2^{k-1}$.
4. RTT iki yönlüdür. Tek yön propagation verildiyse ikiyle çarp.

Elementary protokoller: adım adım

Ders kitapları güvenilir iletimi basitten karmaşığa giden bir protokol dizisiyle kurar. Her biri bir öncekinin varsaydığı bir kolaylığı kaldırır.

Neden sıra numarası? Senaryo: gönderici 0 numaralı çerçeveyi yollar, alıcı alır ve ACK yollar, ACK kaybolur. Gönderici timeout’ta 0’ı tekrar yollar. Sıra numarası olmasa alıcı bunu yeni veri sanar ve üst katmana iki kez teslim eder. Bir bit yeter: alıcı “şimdi 1 bekliyordum, bu 0 tekrar” der, atar ama yine ACK yollar.

TUZAK · tekrar gelen çerçeveye de ACK yolla. Alıcı tekrar çerçeveyi atar ama ACK’i yine yollamalı. Yollamazsa gönderici sonsuza kadar aynı çerçeveyi yeniden gönderir, çünkü ilk ACK zaten kaybolmuştu.

Stop-and-wait neden yavaş?

Gönderici bir çerçeve yollar, ACK gelene kadar bekler. Çerçevenin ilk biti $t = 0$‘da çıkar, son biti $L/R$‘de, ACK $RTT + L/R$ anında döner. Göndericinin gerçekten bit bastığı oran:

$U_{sender} = \frac{L/R}{RTT + L/R}$

Çözümlü örnek

$R = 100$ Mbps, $L = 10{,}000$ bit, $RTT = 20$ ms.

L/R = 10,000 / 10^8        = 0.1 ms
U   = 0.1 / (20 + 0.1)     = 0.004975   (yaklaşık %0.5)
throughput = U x R         = 497.5 kbps

100 Mbps’lik linkten yarım megabit bile geçmiyor. Sorun link değil, protokol.

$a$ parametresi

Bazı kitaplar $a = d_{prop}/d_{trans}$ tanımlar. ACK boyutu ve işlem süresi ihmal edilirse $RTT = 2 d_{prop}$:

$U_{SW} = \frac{1}{1 + 2a}$

Örnekte $d_{prop} = 10$ ms, $d_{trans} = 0.1$ ms, $a = 100$, $U = 1/201$. Aynı sayı.

Pipelining ve kayan pencere (sliding window)

Çözüm: ACK beklemeden birden fazla çerçeve gönder. Gönderici en fazla $N$ tane onaylanmamış çerçeveyi “yolda” tutabilir. Bu $N$, pencere boyutu (window size). Bir ACK gelince pencere ileri kayar.

$U = \min\left(1,\ \frac{N \cdot L/R}{RTT + L/R}\right)$

Aynı örnekte $N = 50$: $U = 50 \times 0.1 / 20.1 = 0.2488$. Tam verim için:

$N \ge \frac{RTT + L/R}{L/R} = \frac{20.1}{0.1} = 201$

Bu, 1. haftadaki bandwidth-delay product fikrinin çerçeve cinsinden halidir: boru dolu olmalı.

Göndericinin sıra numarası uzayı şöyle görünür:

 [ onaylandı ][ gönderildi, ACK bekliyor ][ gönderilebilir ][ henüz kullanılamaz ]
               ^ base                      ^ nextseqnum
               |<-------------- pencere N -------------->|

Pipelining iki farklı şekilde hatadan kurtulur: Go-Back-N ve Selective Repeat.

Go-Back-N (GBN)

• Alıcı penceresi 1. Alıcı sadece beklediği sıradaki çerçeveyi kabul eder. Sıra dışı gelen her şeyi atar.
• Kümülatif ACK (cumulative ACK). “ACK n” demek n’e kadar (n dahil) her şey alındı demek. Sıra dışı bir çerçeve gelince alıcı en son sıralı aldığı çerçevenin ACK’ini tekrar yollar.
• Tek timer, en eski onaylanmamış çerçeve için. Timeout’ta gönderici o çerçeveden başlayarak penceredeki hepsini yeniden gönderir. Adı buradan: N geri git.

İz: pencere 6, çerçeve 2 kayıp

Gönderici: 0  1  2  3  4  5
Kanal    : ok ok X  ok ok ok
Alıcı    : al al -  at at at        (beklenen hep 2)
ACK      : 0  1     1  1  1          (tekrar eden ACK1)
Timeout(2): yeniden gönder 2 3 4 5   -> 4 çerçeve

Artısı: alıcı basit, tampon yok. Eksisi: tek kayıp, arkasındaki doğru gelmiş çerçeveleri de çöpe atar. Hata oranı yüksek, pencere büyük linkte çok israf eder.

Selective Repeat (SR)

• Alıcı da pencere tutar ve sıra dışı ama pencere içindeki çerçeveleri tamponlar.
• Her çerçeve ayrı ayrı ACK’lenir (kümülatif değil).
• Her çerçevenin kendi timer’ı var. Sadece süresi dolan çerçeve yeniden gönderilir.
• Eksik çerçeve gelince alıcı tampondaki sıralı bloğu üst katmana birlikte verir.

Aynı iz, SR ile

Gönderici: 0  1  2  3  4  5
Kanal    : ok ok X  ok ok ok
Alıcı    : al al -  tampon tampon tampon
ACK      : 0  1     3  4  5
Timeout(2): sadece 2  -> 1 çerçeve
2 gelince: 2,3,4,5 sırayla teslim

Sıra numarası kaç bit olmalı?

Sıra numarası $k$ bitse değerler $0, 1, \ldots, 2^k - 1$ arasında döner.

GBN neden $2^k$ değil? Pencere $2^k$ olsaydı, gönderici 0..7’yi yollar, ACK’lerin hepsi kaybolur ya da hepsi gelir; iki durumda da alıcının bir sonraki beklediği 0’dır. Gönderici gelen “ACK 7”nin yeni pencere mi yoksa eski mi olduğunu ayırt edemez.

SR neden yarısı? Alıcının penceresi de ileri kayıyor. Gönderici ve alıcı pencereleri sıra uzayında çakışmamalı.

k = 2 (0..3), W = 3:
alıcı 0,1,2'yi aldı, ACK'ler kayboldu
alıcı penceresi şimdi {3, 0, 1}
gönderici eski 0'ı tekrar yollar -> alıcı YENİ 0 sanar, hatalı teslim

k = 2, W = 2:
alıcı penceresi {2, 3}, eski 0 dışarıda -> doğru şekilde atılır (ve ACK'lenir)

Çözümlü örnek: uydu linki

$R = 1$ Mbps, $L = 1000$ bit, tek yön propagation 270 ms.

L/R = 1 ms,  RTT = 540 ms
SW               : U = 1 / 541         = 0.00185
GBN, k=3 (N=7)   : U = 7 / 541         = 0.0129
Tam verim için   : N = 541
GBN bit sayısı   : 2^10 - 1 = 1023 >= 541  -> k = 10
SR  bit sayısı   : 2^10 = 1024 >= 541      -> k = 11

Hata olasılığıyla stop-and-wait

Her çerçeve bağımsız olarak $p$ olasılıkla bozuluyorsa bir çerçeve başına beklenen iletim sayısı:

$E[\text{iletim}] = \frac{1}{1-p}$

$p = 0.2$ için 1.25. Verim aynı oranda düşer. Gürültülü linkte GBN tek hatada birçok çerçeve tekrar ettiği için SR’nin avantajı büyür.

İPUCU · piggybacking. İki yönlü veri akışında alıcı ayrı bir ACK çerçevesi yollamak yerine ACK’i ters yöndeki kendi veri çerçevesinin başlığına koyar. Bant genişliği tasarrufu sağlar. TCP de böyle çalışır.

Güvenlik notu

Bu protokollerin hiçbiri karşı tarafın kim olduğunu doğrulamaz. Sıra numarası tahmin edilebilir olursa araya giren biri sahte bir çerçeveyi doğru sıra numarasıyla sokabilir. TCP’nin başlangıç sıra numarasını rastgele seçmesinin (7. hafta) bir sebebi budur.

Sık yapılan hatalar