Bölüm 24: Hata Sezme ve CRC

Frame hazır. Fabrikadan gelen MAC adresini başına yazdık, ama yolda bir bit ters dönerse bunu kimin fark edeceğini söylemedim.

Fark eden bir gözlemci yok. Frame’in sonuna eklenen küçük bir sayı var ve bütün iş onda. Peki dört bayt, 1.500 baytlık bir yükü nasıl koruyabiliyor?

Bir bit neden ters döner?

Telin üstündeki sinyal yol boyunca zayıflıyor. Üstüne bir de dışarıdan gelen elektromanyetik gürültü biniyor. Alıcı eşiğe yakın bir gerilim gördüğünde yanlış karar veriyor ve gönderilen sıfır, bir olarak okunuyor. Bit hatasının fiziksel sebebi bu iki etkinin toplamı.

Olasılık kanaldan kanala değişiyor ve fiberde diğer bütün ortamlardan çok daha düşük kalıyor. Yıldırım gibi atmosferik olaylar ise hem telli hem telsiz ortamda aynı şeyi yapıyor: art arda gelen bitleri topluca bozuyor. Bu kümeye patlama hatası deniyor. Ayrım yöntem seçimini belirliyor, çünkü tek bir biti koruyan hesap on bitlik bir patlamanın karşısında çaresiz kalıyor.

Sinyalin neden zayıfladığını ve gürültünün nereden geldiğini burada bırakıyorum; ortamın kendisine 55. bölümde bakacağız.

Bir şeyi de baştan sabitleyeyim. Hiçbir sezme yöntemi %100 güvenilir değil; her yöntem bazı hataları kaçırıyor, ama nadiren. Denetim alanı büyüdükçe hem sezme hem düzeltme gücü artıyor. Bedeli her frame’de taşınan fazladan bit.

Sezmek ile düzeltmek aynı iş mi?

Hata denetimi iki ayrı aşamada yürüyor. Önce saptama: bir bozulma var mı? Sonra düzeltme: bozulan neydi ve doğrusu neydi? İki büyük aile bu iki aşamayı farklı paylaştırıyor.

FEC (forward error correction, ileri yönlü hata düzeltme) ikisini birlikte yapıyor. Alıcı göndericiye hiçbir şey sormadan bozulan biti geri çeviriyor. Yaygın iki algoritması Hamming kodu ile Reed-Solomon kodu. İlki tek bitlik hatayı düzeltir; ikincisi bit yerine sembol düzeltir ve bu yüzden patlama hatalarına dayanır. CD’nin çiziğini, QR kodunun kirlenmiş köşesini ve eski uydu yayınlarını ayakta tutan kod odur.

Asıl kazanç hızda. Alıcı hatayı yerinde düzelttiği için bir RTT beklenmiyor. Derin uzay bağlantılarında bu belirleyici oluyor, çünkü orada bir sorunun cevabı dakikalarca yolda kalıyor. Gerçek zamanlı ses ve videoda da öyle.

Patlama hataları FEC’i zorluyor. Physical layer’ın çözümü, denetim bitlerini ekledikten sonra bitleri karıştırmak (interleaving). Tek bir gürültü patlaması artık komşu bitleri değil, birbirinden uzak bitleri vuruyor. Alıcı sırayı geri çevirince küme dağılmış oluyor.

ARQ (automatic repeat request, otomatik tekrar isteği) daha az iddialı. Bozulan paketi yeniden gönderiyor, o kadar. Bunun için alıcının geri bildirim göndermesi, göndericinin de paketleri numaralayıp birer kopyasını tutması gerekiyor; TCP’nin bunu nasıl yaptığını 67. bölümde göreceğiz. Veriyi paketlere bölmenin sebeplerinden biri de bu: bozulan tek paket yeniden gönderiliyor, koca dosya değil.

Bir kodun gücünü ölçen tek sayı

“Bu yöntem kaç bitlik hatayı yakalar?” sorusunun tahmine dayanmayan bir cevabı var ve tek bir büyüklüğe iniyor.

İki bit dizisi arasındaki Hamming uzaklığı, kaç konumda farklı olduklarıdır. 1011010 ile 1001110 arasındaki uzaklık ikidir; üçüncü ve beşinci bitler tutmuyor. Bir hatanın yaptığı da bu: diziyi kendisinden d uzaklıktaki başka bir diziye taşıyor.

Denetim biti eklediğinde bütün bit dizileri geçerli olmaktan çıkıyor; yalnızca bir kısmı geçerli kod sözcüğü oluyor. Kodun gücünü belirleyen şey, bu geçerli sözcüklerin birbirine ne kadar uzak durduğu. En yakın iki geçerli sözcük arasındaki uzaklığa kodun asgari uzaklığı (dmin) deniyor ve her şey ondan çıkıyor:

d bitlik hatayı SEZMEK için      dmin ≥ d + 1
d bitlik hatayı DÜZELTMEK için   dmin ≥ 2d + 1

İki formülün arasındaki fark, geometrik olarak düşününce kendiliğinden anlaşılıyor. Geçerli sözcükleri bir uzayda noktalar gibi düşün. Sezmek için, d bitlik bir hatanın seni başka bir geçerli noktaya düşürmemesi yeter; arada en az bir adım daha olmalı. Düzeltmek ise daha fazlasını istiyor: bozulmuş diziye en yakın geçerli noktanın tek olması gerekiyor, yani her noktanın çevresindeki d yarıçaplı kürelerin birbirine değmemesi. İki kat yer gerekiyor, formüldeki 2 katsayısı da oradan geliyor.

Şimdi tanıdık iki kodu ölç:

Tek eşlik bitinin dmin = 2 olması, iki geçerli sözcüğün en az iki bit farklı olması demek: bir bit çevirirsen mutlaka geçersiz bir diziye düşersin, bu yüzden hatayı görürsün. Ama hangi bitin ters döndüğünü söyleyemezsin: d + 1 = 2 sağlanıyor, 2d + 1 = 3 sağlanmıyor. Bu kitapta ilerideki her yöntemin gücü aynı cetvelle ölçülüyor.

Bedeli de aynı cetvelde okunuyor. Sözcükleri birbirinden uzaklaştırmanın tek yolu daha çok denetim biti eklemek, yani her frame’de daha az veri taşımak. Güvenilirlik ile verim aynı bütçeden besleniyor.

Saymak nereye kadar yetiyor?

En ucuz sezme tek bir bit ekliyor. Asenkron haberleşmede her karakterin yanına giden eşlik biti bu. Çift eşlikte bir’lerin sayısı çift olacak şekilde ayarlanıyor, tek eşlikte tek. Hangisinin kullanılacağına iki tarafın önceden karar vermesi gerekiyor.

Alıcının işi sayı saymak. Gelen bir’leri sayıyor; teklik ya da çiftlik tutmazsa bozulma var demektir ve karakter yeniden isteniyor. Bir baytlık 01001011 içinde dört tane bir var, o yüzden çift eşlikte eklenen bit sıfır oluyor. Bayt başına bir bit, yani %12,5 yük.

Kör noktası da aynı yerde duruyor. Çift sayıda bit ters dönerse toplam yine tutuyor ve hata görünmez kalıyor. Hatalar patlama hâlinde geldiğinde bu bir istisna olmaktan çıkıyor: tek eşlik bitiyle korunan bir frame’de sezilemeyen hata olasılığı %50’ye yaklaşabiliyor.

İki boyutlu eşlik bir kat yukarı çıkıyor. Veri satır ve sütunlara diziliyor, her satır ve her sütun için ayrı eşlik hesaplanıyor. Tek bit bozulduğunda bozuk satır ile bozuk sütunun kesişimi hatalı biti veriyor; alıcı onu çevirip düzeltiyor. İki bit bozulduğunda ise düzeltemiyor, yalnızca sezebiliyor. Pratikte kullanılmamasının sebebi bedeli: 4x4’lük bir matriste 16 veri biti için 9 eşlik biti gerekiyor, yani %56 yük.

Checksum aynı fikri bir adım ileri taşıyor. İnternet checksum veriyi 16 bitlik tamsayılar dizisi sayıyor, birler tümleyeni toplamını alıyor ve sonucun tersini denetim alanına yazıyor. Alıcı aynı hesabı yeniden yapıp karşılaştırıyor. Eşit değilse hata sezildi. Eşitse sezilmedi, ama yine de olmuş olabilir.

Zayıflığı gösterilebilir. Üç kelime al: E38F, A51C, 4B60. Birler tümleyeni toplamları D40C, tersi olan checksum da 2BF3 çıkıyor. Şimdi birinci kelimeyi bir artır, ikinciyi bir azalt. İkisi de değişti, checksum yine 2BF3 çıkıyor. Toplama değişmeli olduğu için kelimelerin sırasını bozmak da sonucu değiştirmiyor.

TCP ve UDP checksum yalnızca 16 bit yer kaplıyor. Yükü çok düşük, koruması da o oranda zayıf. Sebep tasarımda: transport layer yazılımda çalışıyor ve ucuz bir hesap seçiyor. IPv6 başlığında bu alan hiç yok; router’da işlemeyi hızlandırmak için kaldırılmış ve koruma alt ile üst katmanlara bırakılmış.

Frame’in sonundaki dört bayt

Data link layer aynı ödünleşimi ters yönde çözüyor. Hesap ağ kartının üstündeki özel donanımda çalışıyor, bu yüzden pahalı bir yöntem göze alınabiliyor. O yöntem CRC.

CRC (cyclic redundancy check, döngüsel artıklık denetimi) kodlarının öbür adı polinom kodları. Bit dizisi, katsayıları 0 ve 1 olan bir polinom gibi ele alınıyor. Gönderici ile alıcı önce r+1 bitlik bir üreteç deseninde anlaşıyor; desenin en soldaki biti 1 olmak zorunda ve deseni standart veriyor. Hesap mod-2 aritmetiğiyle yürüyor: elde ve borç yok, toplama ile çıkarma aynı işlem ve ikisi de bit bazında XOR.

Gönderici veriyi r bit sola kaydırıp üretece bölüyor. Kalan, veriye eklenen CRC bitleri oluyor:

D = 100110        veri, 6 bit
G = 1101          üreteç, r+1 = 4 bit   (r = 3)

100110000 ÷ G  ->  kalan 110
tele çıkan     ->  100110110
alıcıda kalan  ->  000

soldan dördüncü bit ters:  100010110  ->  kalan 011   (hata sezildi)

Alıcı ayrı bir hesap tutmuyor. Veriyi ve CRC bitlerini birlikte üretece bölüyor; kalan sıfırdan farklıysa hata var.

Uluslararası standartlarda 8, 12, 16 ve 32 bitlik üreteçler tanımlı. Ethernet’in seçtiği CRC-32’nin üreteci 33 bitlik sabit bir desen ve aynı desen data link layer’daki IEEE protokollerinde ortak. r bitlik bir CRC, r+1 bitten kısa bütün patlamaları kesin yakalıyor. Daha uzun patlamalar da yüksek olasılıkla seziliyor: 32 bitlik artıklıkta kaçırma olasılığı %0,0000000233’e iniyor. Ethernet’in deseni ayrıca en büyük frame boyuna kadar, frame’in neresine düşerse düşsün üç bite kadar her hatayı yakalıyor.

Üç yöntemi aynı hata patlaması üstünde karşılaştıralım:

Ethernet frame’inin son alanı FCS (frame check sequence, frame denetim dizisi). 32 bit, yani 4 bayt; içine CRC-32 sonucu yazılıyor. Hesap hedef adres, kaynak adres, tür alanı ve veri alanları üzerinden yapılıyor; baştaki 8 bayt, yani önsöz ile frame başlangıç sınırlayıcısı, hesaba katılmıyor. 20. bölümde encapsulation merdiveninde bu alanı adlandırmış ama içini boş bırakmıştım.

Bu dört baytın bedeli frame boyuna göre değişiyor. 1.518 baytlık dolu bir frame’de FCS’nin yükü %0,26 kalıyor. 64 baytlık en küçük frame’de aynı alan %6,25’e çıkıyor. Aradaki fark kabaca yirmi dört kat.

Hesap tutmazsa frame düşürülüyor ve interface’in hata sayacı bir artıyor. Üst katmana hiçbir şey çıkmıyor. Alıcı kart göndericiye ne ACK ne NAK yolluyor; Ethernet güvenilir değildir. Düşen frame’deki veri ancak üst katmanda güvenilir bir protokol varsa kurtarılıyor. Data link layer hatayı tespit ediyor, telafi etmiyor.

Yol üstünde iki tuzak var. Bir switch frame’i tamponuna alıp CRC’sini denetledikten sonra iletiyorsa bozuk frame orada duruyor; hedef adresi okur okumaz iletiyorsa CRC’ye hiç bakılmadan bozuk frame yayılabiliyor. Bu tercihin adını 27. bölümde switch’i açtığımızda koyacağız. İkinci tuzak da switch’in elinde: frame’e bir etiket eklendiğinde FCS baştan hesaplanıyor. Frame o anda zaten bozuksa ve switch onu denetlemeden etiketliyorsa, yeni ve kusursuz bir FCS bozuk içeriği aklamış oluyor.

Sayacı kendi makinende görebilirsin:

ip -s link show enp3s0
ethtool -S enp3s0 | grep -i crc

İlk komut RX satırının altında errors sütununu dökecek. İkincisi sürücünün tuttuğu ayrıntılı sayaçlardan rx_crc_errors benzeri bir satır verecek. Sayı artıyorsa kablo, konnektör ya da yakındaki bir gürültü kaynağı sorguya çekilir.

Özet

• Bozulmanın sebebi zayıflama ve gürültü: yıldırım gibi olaylar bitleri tek tek değil ardışık kümeler hâlinde deviriyor ve yöntem seçimini belirleyen şey bu.
• Saptama ile düzeltme ayrı işler: FEC ikisini birlikte yapıp RTT’yi kurtarıyor, ARQ ise yalnızca saptayıp bozulan paketi yeniden istiyor.
• Ucuz yöntemlerin kör noktası ölçülü: tek eşlik biti çift sayıda dönüşü, internet checksum birbirini telafi eden değişimleri kaçırıyor.
• CRC bölmeye dayanıyor: veri r bit kaydırılıp üretece bölünüyor, kalan frame’e ekleniyor ve alıcıda kalanın sıfırdan farklı çıkması hatayı ele veriyor.

Frame’in sonu artık dolu ve başındaki iki adres de yerinde. Peki oraya yazdığın MAC’i sen nereden buldun? Elinde hedefin IP adresi var; aradaki eşlemeyi kim yapıyor?