Bölüm 22:Hata Sezme ve CRC

Çerçeve 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. Çerçevenin 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 kitabın sonunda 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 çerçevede 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 kodlaması ve Reed-Solomon kodlaması; 1-2 bitlik hataları anlayıp düzeltebiliyorlar.

Asıl kazanç hızda. Alıcı hatayı yerinde düzelttiği için bir gidiş-dönüş süresi 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. Fiziksel katmanın çözümü, denetim bitlerini ekledikten sonra bitleri karıştırmak. 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. Bu yüzden akış kontrolüyle birlikte çalışıyor. 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 hata tam olarak bunu yapıyor: 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 çerçevede 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 çerçevede 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, bir tümleyen toplamını alıyor ve sonucu 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. Toplamları 2BF3 çıkıyor. Şimdi birinci kelimeyi bir artır, ikinciyi bir azalt. İkisi de değişti, sonuç 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: taşıma katmanı yazılımda çalışıyor ve ucuz bir hesap seçiyor. IPv6 başlığında bu alan hiç yok; yönlendiricide işlemeyi hızlandırmak için kaldırılmış ve koruma alt ile üst katmanlara bırakılmış.

Çerçevenin sonundaki dört bayt

Bağ katmanı 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 bağ katmanındaki IEEE protokollerinde ortak. Her standart iki şeyi garanti ediyor: r+1 bitten kısa bütün patlamalar ve tek sayıda bit hatasının hepsi kesin yakalanıyor. Daha uzun patlamalar da yüksek olasılıkla seziliyor. 32 bitlik artıklıkta kaçırma olasılığı %0,0000000233’e iniyor.

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

Ethernet çerçevesinin son alanı FCS (frame check sequence, çerçeve denetim dizisi). 32 bit, yani 4 bayt, ve 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 çerçeve başlangıç sınırlayıcısı, hesaba katılmıyor. Kapsülleme merdiveninde bu alanı adlandırmış ama içini boş bırakmıştım.

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

Hesap tutmazsa çerçeve düşürülüyor ve arayüzün 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 çerçevedeki veri ancak üst katmanda güvenilir bir protokol varsa kurtarılıyor. Bağ katmanı hatayı tespit ediyor, telafi etmiyor.

Yol üstünde iki tuzak var. Bir anahtar çerçeveyi tamponuna alıp CRC’sini denetledikten sonra iletiyorsa bozuk çerçeve orada duruyor; hedef adresi okur okumaz iletiyorsa CRC’ye hiç bakılmadan bozuk çerçeve yayılabiliyor. Bu tercihin adını anahtarı açtığımızda koyacağız. İkinci tuzak da anahtarın elinde: çerçeveye bir etiket eklendiğinde FCS baştan hesaplanıyor.

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

Peki, ne öğrendik?

• 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 gidiş-dönüş süresini 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 çerçeveye ekleniyor ve alıcıda kalanın sıfırdan farklı çıkması hatayı ele veriyor.

Çerçevenin 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?