SEN2008 · 9. hafta · Midterm

Vize tekrar: ağ temellerinden TCP'ye

2-8. haftaların bütün formülleri tek tabloda, sınavda hangi sorunun hangi kalıba oturduğu ve karışık 12 soruluk deneme: Shannon, CRC, kayan pencere, alt ağ, parçalama, Dijkstra, Bellman-Ford, el sıkışma, cwnd, RTT tahmini.

Shannon capacityCRCutilizationslotted ALOHACIDRfragmentation offsetDijkstraBellman-Fordthree-way handshakeslow startcongestion avoidanceEWMATimeoutIntervalreceive window

Vize 2. haftadan 8. haftaya kadar olan ağ konularını kapsar. Güvenlik kısmı vizeden sonra başlıyor. Bu sayfa yeni bir şey öğretmez: bütün formülleri tek yerde toplar, her soru tipinin “tanıma işaretini” verir ve sonunda sınav provası yaptırır. Önce tabloları oku, sonra soruları kâğıt kalemle çöz, takıldığın konunun sayfasına geri dön.

Sınav stratejisi:

Önce birimleri yaz. Byte mı bit mi, km mi m mi, ms mi s mi. Puanların büyük kısmı birim hatasında gidiyor.
Formülü yaz, sonra sayıyı koy. Kısmi puan formülden gelir.
İz (trace) sorularında tablo çiz. Dijkstra, cwnd, GBN gibi sorularda her adımı bir satıra yaz.
Varsayımı belirt. “Tie broken alphabetically”, “cwnd capped at ssthresh” gibi şeyleri cevabına ekle.

Hafta hafta formül özeti

1-2. hafta: gecikme, katmanlar, fiziksel katman

Konu	Formül / kural	Tanıma işareti
Transmission	$d_{trans} = L/R$	“packet of L bits on a link of rate R”
Propagation	$d_{prop} = d/s$	“km long”, “propagation speed”
Çok link	$(N + P - 1)L/R$	“store-and-forward”, “P packets”
Trafik yoğunluğu	$La/R$	“packets arrive at rate a”
Kapsülleme verimi	veri / (veri + başlıklar)	“header overhead”
Nyquist	$2B\log_2 V$	“noiseless”, “levels”
Shannon	$B\log_2(1 + \text{SNR})$	“SNR”, “dB”, “noisy”
Baud	bit rate $=$ baud $\times \log_2 V$	“symbols per second”, “QAM”

Katmanlar ve PDU’lar: Application (message), Transport (segment), Network (datagram), Link (frame), Physical (bit). OSI’de ayrıca Presentation ve Session.

3. hafta: hata kontrolü ve kayan pencere

Konu	Prosedür	Tuzak
Parity	1’leri say, even/odd	Çift hata kaçar
2D parity	Satır ve sütun kesişimi hatalı bit	4 köşe dikdörtgen kaçar
Checksum	16 bit topla, elde başa, tersle	Elde atılmaz
CRC	$r$ sıfır ekle, XOR böl	Polinomdaki eksik dereceye 0 yaz
Hamming	$2^r \ge m + r + 1$ ; sendrom konumu verir	p1, p2, p4 konumları
Verim	$U = \min(1, N \frac{L/R}{RTT + L/R})$	RTT iki yönlü
Sıra no	GBN $2^k - 1$ , SR $2^{k-1}$	SR’de yarısı

GBN’de alıcı sıra dışını atar ve kümülatif ACK yollar; timeout’ta kaybolandan itibaren her şey yeniden gönderilir. SR’de alıcı tamponlar, her çerçeve ayrı ACK ve timer alır.

4. hafta: çoklu erişim ve Ethernet

Konu	Formül
Slotted ALOHA	$Ge^{-G}$ , max $1/e$ ; $Np(1-p)^{N-1}$
Pure ALOHA	$Ge^{-2G}$ , max $1/(2e)$
CSMA/CD min çerçeve	$L_{min} = 2 d_{prop} R$
Backoff	$K \in \{0..2^{\min(n,10)} - 1\}$ , $K \times 512$ bit süresi
Ethernet verimi	$1/(1 + 5 d_{prop}/d_{trans})$
Çerçeve	64 ile 1518 byte; payload 46 ile 1500

Switch kaynak MAC’ten öğrenir, hedefi arar: yoksa flood, aynı portsa filter, başka portsa forward. ARP isteği broadcast, cevabı unicast. Uzak hedefte hedef MAC gateway’in MAC’idir.

5-6. hafta: ağ katmanı

Alt ağ hesabı (a.b.c.d/n):
  maske        : n tane 1, kalanı 0
  blok boyu    : 256 - (ilginç oktetteki maske değeri)
  ağ adresi    : ilginç okteti blok boyunun katına aşağı yuvarla, sağı 0
  broadcast    : bir sonraki ağ adresi - 1
  host sayısı  : 2^(32-n) - 2
  b bit ödünç  : 2^b alt ağ

Parçalama (fragmentation):
  parça verisi : (MTU - başlık) aşağı 8'in katına
  offset alanı : parçanın verideki başlangıç byte'ı / 8
  MF           : son parça hariç 1
  toplam uzunluk alanı başlığı da içerir

Yönlendirme:

Link-state (Dijkstra, OSPF): her düğüm tüm haritayı bilir. Her adımda N’ dışındaki en küçük $D$ ‘yi ekle, komşularını $D(v) = \min(D(v), D(w) + c(w,v))$ ile güncelle.
Distance-vector (Bellman-Ford, RIP): her düğüm sadece komşularının vektörünü bilir. $D_x(y) = \min_v \{c(x,v) + D_v(y)\}$ . Kötü haber yavaş yayılır (count-to-infinity); poisoned reverse kısmi çözüm.
OSPF AS içi (intra-AS), link-state. BGP AS’ler arası (inter-AS), path-vector; politika ile karar verir.

7-8. hafta: taşıma katmanı

Konu	Kural
UDP başlığı	8 byte: src port, dst port, length, checksum
TCP başlığı	en az 20 byte; seq, ack, flags (SYN, ACK, FIN, RST), rwnd
Seq / ack	seq = segmentin ilk byte’ı; ack = beklenen sonraki byte
El sıkışma	SYN (x) → SYN-ACK (y, x+1) → ACK (x+1, y+1)
Akış kontrolü	rwnd $=$ RcvBuffer $-$ (LastByteRcvd $-$ LastByteRead)
Gönderim sınırı	LastByteSent $-$ LastByteAcked $\le \min(\text{cwnd}, \text{rwnd})$
Slow start	her RTT’de cwnd ×2, ssthresh’e kadar
Congestion avoidance	her RTT’de +1 MSS
Timeout	ssthresh = cwnd/2, cwnd = 1 MSS, slow start
3 dup ACK (Reno)	ssthresh = cwnd/2, cwnd = ssthresh (+3), fast recovery
Ortalama throughput	$\approx 0.75\,W/RTT$
RTT tahmini	Est $= (1-\alpha)$ Est $+ \alpha S$ ; Dev $= (1-\beta)$ Dev $+ \beta

TUZAK · SYN ve FIN birer sıra numarası tüketir. Veri taşımasalar da. El sıkışmadan sonra verinin ilk byte’ı ISN + 1’dir.

TUZAK · Tahoe ile Reno. Timeout’ta ikisi de cwnd’yi 1’e indirir. Fark sadece üç tekrar ACK’te: Tahoe yine 1’e iner, Reno yarıya iner ve congestion avoidance’tan devam eder. Sınavda hangisinin sorulduğunu ve kitabın “+3” kuralını kullanıp kullanmadığını soru metninden oku.

Çözümlü karma örnek: bir web isteğinin yolculuğu

Laptop (192.168.1.10/24) bir web sunucusuna bağlanıyor. Bütün haftaları bir arada gör:

1. Uygulama: HTTP isteği (message)
2. Transport: TCP el sıkışma (SYN, SYN-ACK, ACK), sonra segmentler; cwnd = 1 MSS ile başlar
3. Network: hedef IP alt ağımda mı? 192.168.1.0/24 dışında -> default gateway
4. Link: gateway MAC'i için ARP (broadcast istek, unicast cevap)
5. Ethernet çerçevesi: dst MAC = gateway, FCS = CRC-32
6. Switch: kaynak MAC'i öğrenir, çerçeveyi gateway portuna iletir
7. Router: IP başlığına bakar, en uzun önek eşleşmesi (longest prefix match), TTL - 1
8. Çekirdek: OSPF ile AS içinde, BGP ile AS'ler arasında yol bulunmuş
9. Her linkte: dtrans + dprop + kuyruk; darboğaz link throughput'u belirler

Vizeden sonra bu yolculuğun her adımına saldırgan gözüyle bakacağız: ARP spoofing (4), sahte IP (7), SYN flood (2), BGP hijacking (8).

Sık yapılan hatalar (bütün konular)

Yanlış düşünce	Doğrusu
Shannon’a dB’yi koymak	Önce $10^{dB/10}$
CRC’de üreteç uzunluğu kadar sıfır	Derece kadar ( $r$ )
$U = (L/R)/RTT$	Payda $RTT + L/R$
GBN alıcısı tamponlar	Atar; SR tamponlar
$L_{min} = d_{prop} R$	$2 d_{prop} R$
/n için host sayısı $2^{32-n}$	$-2$ (ağ ve broadcast)
Offset byte cinsinden yazılır	8 byte’lık birim: byte / 8
Dijkstra’da en ucuz komşuya git	Toplam yol maliyetine göre seç
ACK = aldığım son byte	Beklediğim sonraki byte
Slow start ssthresh’i aşar	ssthresh’e ulaşınca CA’ya geçer
UDP sıralı teslim eder	Sıra no ve ACK yok; güvenilmez

Kendini test et

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

Soru 1kolay

A channel has bandwidth 4 kHz and SNR = 30 dB. What is its Shannon capacity (nearest bps)?

Cevabı göster

39,869 bps

30 dB → oran $10^{3} = 1000$ . $C = 4000 \log_2(1001) \approx 4000 \times 9.967 = 39{,}869$ bps.

Soru 2orta

Compute the CRC bits for data 100101 with generator 1101, and give the transmitted bit string.

Cevabı göster

R = 100, sent 100101100

Derece 3, üç sıfır ekle: 100101000.1001⊕1101=0100 → sonraki bitlerle 1000⊕1101=0101 → 1011⊕1101=0110 → 1100⊕1101=0001, kalan son 3 bit 100.
Gönderilen 100101 + 100 = 100101100. Alıcı bunu 1101'e bölünce kalan 0 bulur.

Soru 3orta

A 10 Mbps link carries 1000-byte frames with RTT = 10 ms. What is the stop-and-wait utilization, and what is the smallest window that gives 100% utilization?

Cevabı göster

≈ 0.0741; 14 frames

$L/R = 8000/10^7 = 0.8$ ms. $U = 0.8 / (10 + 0.8) \approx 0.0741$ .
Tam verim: $N \ge 10.8/0.8 = 13.5$ , pencere tam sayı olmalı: $N = 14$ .

Soru 4orta

Host 172.16.45.130/21: what are its network address, broadcast address and number of usable host addresses?

Cevabı göster

172.16.40.0, 172.16.47.255, 2046

/21 → maske 255.255.248.0. İlginç oktet üçüncüsü, blok boyu $256 - 248 = 8$ .
45, 8'in katları arasında 40 ile 48 arası: ağ 172.16.40.0, broadcast bir sonraki bloğun bir eksiği 172.16.47.255.
Host biti $32 - 21 = 11$ : $2^{11} - 2 = 2046$ .

Soru 5orta

The network 200.10.20.0/24 must be divided into at least 6 equal subnets. What prefix length results, and how many usable hosts does each subnet have?

Cevabı göster

/27, 30 hosts

$2^b \ge 6$ → $b = 3$ bit ödünç ( $2^3 = 8$ alt ağ). Önek $24 + 3 = 27$ .
Kalan host biti 5: $2^5 - 2 = 30$ .

Soru 6zor

A 4000-byte IPv4 datagram (20-byte header, no options) must cross a link with MTU 1500 bytes. List each fragment's total length, offset field and MF flag.

Cevabı göster

1500/0/1, 1500/185/1, 1040/370/0

Taşınacak veri $4000 - 20 = 3980$ byte. Parça başına en fazla $1500 - 20 = 1480$ byte veri (8'in katı, uygun).
Parça 1: 1480 veri, uzunluk 1500, offset $0/8 = 0$ , MF=1.
Parça 2: 1480 veri, uzunluk 1500, offset $1480/8 = 185$ , MF=1.
Parça 3: $3980 - 2960 = 1020$ veri, uzunluk 1040, offset $2960/8 = 370$ , MF=0.

Soru 7zor

Run Dijkstra from node u on the graph below. In what order are nodes added to N', and what is the least-cost path from u to z with its cost? (Break ties alphabetically.)

edges (undirected, cost):
u-v 2   u-x 1   u-w 5
v-x 2   v-w 3   x-w 3
x-y 1   w-y 1   w-z 5
y-z 2

Cevabı göster

x, v, y, w, z; u-x-y-z, cost 4

Başlangıç: D(v)=2, D(w)=5, D(x)=1, D(y)=D(z)=∞.
x eklenir (1): D(w)=min(5, 1+3)=4, D(y)=1+1=2.
v ve y eşit (2), alfabetik v: güncelleme yok (v üzerinden w 5, x 3 daha kötü).
y eklenir (2): D(w)=min(4, 2+1)=3, D(z)=2+2=4.
w (3): D(z)=min(4, 3+5)=4 değişmez. Son z (4).
Yol geri izlenir: z←y←x←u, yani u-x-y-z, maliyet 4.

Soru 8orta

Node x has neighbors y, v and w with link costs c(x,y) = 2, c(x,v) = 7, c(x,w) = 1. They advertise distances to z of $D_y(z) = 5$ , $D_v(z) = 1$ , $D_w(z) = 9$ . Using Bellman-Ford, what is $D_x(z)$ and the next hop?

Cevabı göster

7, via y

$D_x(z) = \min\{c(x,y) + D_y(z),\ c(x,v) + D_v(z),\ c(x,w) + D_w(z)\}$ $= \min\{2 + 5,\ 7 + 1,\ 1 + 9\} = \min\{7, 8, 10\} = 7$ , sonraki atlama y.
En ucuz komşu (w) en iyi yol değil; komşu maliyeti ile komşunun bildirdiği mesafe birlikte toplanır.

Soru 9orta

A client chooses ISN 1000 and the server chooses ISN 5000. Give the (seq, ack) values of the SYN-ACK and of the final ACK of the handshake. If the client then sends 500 bytes of data starting right after the handshake, what is the sequence number of the next byte after that segment?

Cevabı göster

SYN-ACK (5000, 1001); ACK (1001, 5001); next 1501

SYN bir sıra numarası tüketir. İstemci SYN: seq=1000.
Sunucu SYN-ACK: seq=5000, ack=1001 (1000'i aldım, 1001 bekliyorum).
İstemci ACK: seq=1001, ack=5001.
Veri 1001'den başlar, 500 byte: 1001..1500. Sonraki byte 1501.

Soru 10zor

TCP Tahoe starts with cwnd = 1 MSS and ssthresh = 16. cwnd doubles each RTT in slow start (never above ssthresh) and grows by 1 MSS per RTT in congestion avoidance. A timeout occurs at the end of round 9. What is cwnd in rounds 9, 10, 13 and 14?

Cevabı göster

20, 1, 8, 10

Turlar: 1:1, 2:2, 3:4, 4:8, 5:16 (ssthresh'e ulaştı), 6:17, 7:18, 8:19, 9:20.
Timeout: ssthresh = 20/2 = 10, cwnd = 1.
10:1, 11:2, 12:4, 13:8, 14: 16 olacaktı ama ssthresh 10'u geçemez → 10, sonra 15:11.

Soru 11orta

EstimatedRTT = 200 ms, DevRTT = 20 ms, and a new SampleRTT = 240 ms arrives. With α = 0.125 and β = 0.25, updating EstimatedRTT first and then DevRTT with the new estimate, what is the new TimeoutInterval?

Cevabı göster

300 ms

$\text{Est} = 0.875 \times 200 + 0.125 \times 240 = 175 + 30 = 205$ ms. $\text{Dev} = 0.75 \times 20 + 0.25 \times |240 - 205| = 15 + 8.75 = 23.75$ ms. $\text{Timeout} = 205 + 4 \times 23.75 = 300$ ms.

Soru 12kolay

Which statement is FALSE?

A switch learns MAC addresses from the source field of incoming frames
An ARP request is broadcast and the reply is unicast
UDP provides reliable, in-order delivery using sequence numbers
Go-Back-N receivers discard out-of-order frames

Cevabı göster

C) UDP provides reliable, in-order delivery using sequence numbers

UDP'de sıra numarası, ACK, yeniden gönderme yok. Başlığı sadece 4 alan: kaynak port, hedef port, uzunluk, checksum (8 byte). Güvenilirlik isteyen ya TCP kullanır ya da uygulamada kendisi yapar.
Diğer üç ifade doğru.

Doğrulama: Bütün cevaplar node ile hesaplandı (verify/SEN2008/09.mjs): Shannon, mod-2 CRC bölmesi, stop-and-wait verimi, 32 bit maske işlemleriyle alt ağ, parçalama offset'leri, adım adım Dijkstra tablosu, Bellman-Ford denklemi, seq/ack aritmetiği, Tahoe cwnd simülasyonu ve EWMA.

Deftere not kartı

dtrans=L/R dprop=d/s (N+P-1)L/R La/R>1 -> sonsuz kuyruk throughput=min Nyquist 2B log2V Shannon B log2(1+SNR), SNR=10^(dB/10) CRC: r sıfır ekle, XOR böl, son r bit | checksum: topla, elde wrap, tersle Hamming: 2^r >= m+r+1, sendrom = hatalı bit konumu U = min(1, N(L/R)/(RTT+L/R)) GBN W<=2^k-1, SR W<=2^(k-1) slotted 1/e, pure 1/(2e), Np(1-p)^(N-1) Lmin = 2 dprop R /n -> host 2^(32-n)-2, blok = 256 - maske okteti parça veri = (MTU-20) aşağı 8'in katı, offset = byte/8, son parça MF=0 Dijkstra: en küçük D'yi ekle, komşuları güncelle DV: Dx(y)=min_v{c(x,v)+Dv(y)} SYN ve FIN birer seq tüketir; ack = beklenen sonraki byte slow start x2 (ssthresh'e kadar), CA +1, timeout: ssthresh=cwnd/2, cwnd=1 Reno 3 dupACK: ssthresh=cwnd/2, cwnd=ssthresh(+3), CA'dan devam Est=0.875Est+0.125S, Dev=0.75Dev+0.25|S-Est|, TO=Est+4Dev rwnd = RcvBuffer - (LastByteRcvd - LastByteRead); gönderim <= min(cwnd, rwnd)