Bilgisayar Ağları VI (Computer Networks VI)

Veri bağlantı katmanı(Data Link Layer) gönderilecek verinin ağ ortamında nasıl iletileceğini, fiziksel adreslemeyi ve ağ topolojisini tanımlar. Fiziksel kabloda çarpışma olmadan veri iletimini sağlamak ya da verilerin bu medyaya nasıl konulacağı belirlemek ve yine verinin hatalara karşı kontrolünü yapmak, ağ üzerindeki diğer uç sistemlerin kimlik doğrulamalarını yapmak, anlık iletişimin kimin tarafından yapıldığını tespit etmek bu katmanın görevidir.

Ağ katmanda paketlere dönüştürülen datagram bu katmanda artık fiziksel ortama aktarılmadan önce son kez işlem görerek frame yapısına dönüştürülür. Frameler verileri belli bir kontrol içinde göndermeyi sağlayan yapılardır. Veri bağlantı katmanı üzerinden iletimi yapılan her paket, kaynak (source) ve hedef(destination) adreslerini içerir, yani her paket başlangıcı ve bitişi belli olacak şekilde özel bitlerle işaretlenir. Bu katmanda kullanılan protokollerden bazıları şunlardır: Seri hatlar üzerinde HDLC (High-Level Data Link Control):  IEEE 802.3/802.2, FDDI, PPP, X.25, Frame Relay, ATM ve IEEE 802.5/802.2

Ağdaki Link Yapısı Simülasyonu

MAC (Media Access Control (Ortam Erişim Kontrolü)) adresleri kullanılarak fiziksel bağlantılar arasında güvenli data iletimine imkan sağlar. MAC adresinin kullanımı sayesinde bilgisayarların aynı fiziksel bağlantıyı kullanmalarına ve birbirlerinde farklı şekilde tanımlanmalarına yardımcı olur. Her MAC adresi birbirlerinden farklı adreslere sahiptir. Ethernet kartlarına atanan donanım adresleri üretimleri sırasında atanır.

Hata denetimin yapılmasını sağlar. Katman üzerinden gönderilen her bir paket için akış kontrolü sağlar, CRC(Cyclic Redundancy Check) hata kontrolü bu katman üzerinde yapılır. Eğer paketlerin iletimi sırasında hata meydana gelmişse, oluşan hata üst katmana iletilir.

Fiziksel katman, ağ ortamını, gönderilecek verinin bitlere dönüşümünü ve ağ üzerinde  taşınmasını denetler ve yönetir. Bu görevini yerine getirirken de üst katmanlarla olan iletişimi ve gönderilen verinin nereye gitmesi gerektiğini belirleyemez. Bu işlemler Data Link(Veri Bağlantı) katmanı tarafından gerçekleştirilir. Bu katman gönderilecek bitleri organize eder ve gruplandırarak paket yapıya dönüştürür. IEEE standardına göre Data Link Katmanında oluşan iki alt katmanla yönlendirme gerçekleştirilir. Bunlar: Logical Link Control (LLC) ve Media Access Control (MAC).

Mantıksal Link Kontrolü (Logical Link Control(LLC))

Mantıksal Link Kontrolü alt katmanı mantıksal bir arabirimi noktası kullanarak üst katmanlarla olan iletişimi sağlar. Bozulmuş olarak giden paketlerin tekrar gönderilmesini sağlamak temel görevlerindendir. Flow Control yani alıcının işleyebileğinden fazla veri paketi gönderilerek boğulmasının engellenmesinden de LLC sorumludur. İlgili protokole özel mantıksal portlar oluşturur (Service AccessPoints, SAP). Verinin kapsüllenmesi sırasında ağ katmanlarından gelen veriye  hedef ve kaynak protokol bilgilerini (Destination Service Access Point - DSAP, Source Service Access Point - SSAP) ekler ve tekrar paketlediği veriyi bir alt katman olan Ortam Giriş Kontrol (Media Access Control-MAC) katmanına aktarır.  Böylece kaynak makinada ve hedef makinada aynı protokoller iletişime geçebilir

Ortam Giriş Kontrol (Media Access Control(MAC))
Ortam Giriş Kontrol alt katmanı, kullanılan teknolojiye  bağımlı olarak Fiziksel Katmanla olan iletişimi kurmaktadır. Bu katman veriyi hata kontrol kodu Cyclic Redundancy Code, hedef ve kaynak bilgisayarın MAC adresleri ile beraber çerçeve yapıya dönüştürür ve fiziksel katmana gönderir. Alıcıda da bu işlemleri tersine çevirip veriyi veri bağlantı içindeki ikinci alt katman olan LLC'ye aktarma görevi yine MAC alt katmanına aittir.

Ayrıca bilgisayarların ağ ortamına erişim sistemini de organize eder. İki çeşit ortama erişim kontrol protokolü vardır. Bunlar; Belirli (Deterministic) ve Belirsiz (Non-deterministic).

Belirli MAC Protokolleri (Deterministic MAC Protocols)
Sırayla ortama veri aktarımının yapılmasını sağlayan protokollerdir.
Belirsiz MAC Protokolleri (Non-deterministic MAC Protocols)
Bu tür protokoller ilk gelen ilk servisi alır yani (first come, first served) mantığıyla çalışır. Bundan dolayı ağda çarpışmaların olması muhtemeldir.

Anahtarlar ve Köprüler (Switches and Bridges)
Köprüler ve anahtarlar bu katmanda çalışır. Frame iletimi yapmaktadırlar. Anahtar ve köprü aygıtları Data Link katmanında çalışarak MAC adresine göre ağı filtrelemeyi sağlarlar. Ağda Hub aygıtlarının yerine anahtar kullanmanın başlıca nedeni collision domain adı verilen trafikteki çakışmanın önlenmesidir. Hub aygıtları çok fazla çatışmaya neden olurlar.

Dijital sinyallere dönüştürülen ve tek başına anlaşılamayan veri için bu sinyalleri anlaşılabilir hale dönüştürme işlemine çerçeve yapıya dönüştürme (framing) denir. Bu dönüştürme işlemi veri bağlantı katmanı tarafından yapılmaktadır. Frame yapıdan anlaşılabilecek bilgilerin bazıları:
1. Hangi bilgisayarların birbirleriyle iletişim kuracağı,
2. Bilgisayarların ne zaman iletişim kuracağı ve sona erdireceği,
3. İletişim sırasında gönderilen veride hata oluşup oluşmadığı,
4. İletişim kurulduktan sonra hangi bilgisayarın veri göndereceği şeklindedir.

Frame yapılarının temel olarak içeriği:

Data (Veri): Ağ katmanından gelen pakettir.

Header (Başlık): Adresleme gibi kontrol bilgilerini içeren  ve PDU (Protokol Data Unit-Protokol Veri Birimi) başında yer alan bölümdür.

Trailer (Kuyruk): PDU sonuna eklenmiş kontrol bilgisi içeren bölümdür.

Frame Yapısı
Frame formatı genel olarak şu alanlardan oluşmaktadır.
Frame Başlangıç Alanı: Yeni bir frame yapının gelmekte olduğunu belirten alandır.
Adres Alanı: Kaynak ve hedef bilgisayarların MAC adreslerinin bulunduğu alandır.
Frame Tipi ve Uzunluğu Alanı: Ağ katmanında kullanılan protokolün belirtildiği ve toplam frame uzunluğunun belirtildiği alandır.
Data Alanı: Ağ katmanından gelen paketin bulunduğu alandır.
FCS Alanı: Belirli bir algoritma kullanılarak hesaplanan ve frame yapının sağlam olarak ulaşıp ulaşmadığını tespit etmede kullanılan alandır.
Frame bitiş alanı: Frame yapının bittiğini belirten alandır.

Hata Kontrolü Yapıları (Error Control Structures)
Ağlar iki cihaz arasında kabul edilebilir doğrulukta veri transferi yapmak zorundadır. Veri iletişim sırasında bozulabilir. Bu nedenle bazı uygulamalar bozulmaları denetleme ve düzeltme gerektirir. Bazı uygulamalar ise belirli bir hata seviyesini tolere edebilir. Single Bit Error, sadece bir bitin değeri değişir. Burst Error, çok sayıda bitin değeri değişir. 1200 bps hızında iletişim yapılırken eğer 0,01 sn burst error (impulse noise) oluşmuşsa toplam 12 bit bozulur. Single bit error, genellikle seri veri iletişiminde oluşma olasılığı azdır. Burst error, en az iki veya daha fazla bit bozulur. Bozulan bitler art arda olmayabilir. 1kbps hızında iletişim yapılırken 1/100 sn impulse noise oluşursa, 10 bit bozulur. 1Mbps hızında iletişim yapılırsa toplam 10.000 bit bozulur. Hata denetimi ve düzeltmede redundancy temel yaklaşımdır. 

Single Bit Error Çalışma Simülasyonu

Burst Error Çalışma Simülasyonu

Gönderilen veriyle birlikte hata denetim ve düzeltme bitleri eklenir. Redundant bitler gönderme aşamasında eklenir, alıcı tarafında çıkartılır. Hata düzeltme hata denetlemeden çok daha zordur. Error detection(hata denetleme), hata olup olmadığına bakılır. Error correction(hata düzeltme), hata varsa düzeltme işlemi yapılır. Hata denetlemede hatanın boyutuyla ilgilenilmez. Hata düzeltmede tam olarak kaç bitte bozulma olduğunu bilmek zorunludur. Daha da önemlisi bitlerin pozisyonları da bulunmalıdır.

Forward error correction, alıcı tarafından redundant bitler kullanılarak mesajın tamamı tahmin edilmeye çalışılır. Retransmit ile alıcı hatayı denetler ve göndericiden mesajı tekrar göndermesini ister. Redundancy, farklı kodlama yöntemleri kullanılarak oluşturulur. Kodlama yöntemleri, iki grupta yapılır: blok kodlama(block codification) ve kıvrım kodlama(convolution codification).

Gönderici ve Alıcı Kodlama Simülasyonu 

Modüler aritmetikte, sınırlı aralıkta tamsayı kullanılır. İki tabanında aritmetikte toplama ve çıkarma işlemleri aşağıdaki gibi yapılır:

Toplama: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0

Çıkarma: 0 ‐ 0 = 0, 0 ‐ 1 = 1, 1 ‐ 0 = 1, 1 ‐ 1 = 0

Toplama ve çıkarma aynı sonucu verir ve XOR işlemiyle de gerçekleştirilirler. XOR işlemi aynı girişler için 0, farklı girişler için 1 sonucunu üretir.

Blok Kodlama (Block Codification)

Blok kodlamada mesaj k-bit bloklara (dataword) bölünür. Her bloğa r‐bit redundant bit eklenir. Oluşan n=k+r bit codeword olarak adlandırılır. Toplam 2k dataword ve 2n codeword üretilebilir. Ancak 2k adet codeword kullanılır.

Dataword ve Codeword Boyutları

Hata Denetimi (Error Detection)

İki durumda alıcı orijinal codeword’deki hatayı algılar. Alıcı geçerli codeword listesine sahiptir. Orijinal codeword geçerli olmayan bir tanesi ile değişir. Gönderici dataword kullanarak codeword oluşturur.

Blok Kodlama Hata Denetimi

Egzersiz

k = 2 ve n = 3 için aşağıdaki tablo dataword ve codeword listesini göstermektedir.

1. Gönderici 011 bit dizisini göndersin.

2. Alıcı 011 geldiğinde tabloda olduğu için geçerli olarak belirler.

3. İletim sırasında codeword bozulur ve alıcı 111 alırsa tabloda olmadığı için geçersiz olarak belirler.

4. Codeword bozulur ve alıcı 000 alırsa (sağdaki iki bit 0 olmuş) tabloda olduğundan geçerli olarak belirlenir. Aslında bozulan codeword’tür.

Dataword	Codeword
00	000
01	011
10	101
11	110

Hata Düzeltme (Error Correction)

Hata denetiminde alıcı sadece codeword’ün geçerli olup olmadığına bakar. Hata düzeltmede gereken redundant bit sayısı hata denetimine göre daha fazladır.

Blok Kodlama Hata Düzeltme

Egzersiz

Önceki tabloya iki bit redundant bit daha eklenirse aşağıdaki tablo oluşur.

1. 2‐bit dataword ve 3 bit redundant vardır.

2. Dataword 01 ise gönderen tablodan codeword olarak 01011 oluşturur.

3. Code bozulur ve alıcı 01001 alırsa önce tabloya bakılır ve olmadığı görülür.

4. Alıcı 1‐bit bozulma olduğunu tahmin eder ve ilk sıradan kontrol etmeye başlar. İlk sıradakiyle 2‐bit fark vardır.

5. İkinci satırdaki hariç diğerleriyle de 2‐bit farklıdır. İkinci satırdaki 1‐bit farklı olduğu için gelen codeword ikici satırdakiyle değiştirilir.

Dataword	Codeword
00	00000
01	01011
10	10101
11	11110

Hamming Uzaklığı (Hamming Distance)

Hamming distance iki word arasında farklı bit sayısını gösterir. x ve y word’leri arasındaki hamming distance d(x,y) şeklide gösterilir. Hamming distance XOR kapısıyla gerçekleştirilir. Elde edilen 1 sayısı hamming distance değerini gösterir.

d(000, 011) = 2  (000 XOR 011 = 011)

d(10101, 11110) = 3  (10101 XOR 11110 = 01011)

Gönderilen word ile alınan word arasındaki hamming distance, oluşan hatalı bit sayısını gösterir. Örneğin gönderilen 10101 ve alınan 11110 ise hatalı bit sayısı d(10101, 11110) = 3 olur.

Minimum Hamming Uzaklığı (Minimum Hamming Distance)

Tüm olası çiftler içinde en küçük Hamming distance değeridir. Aşağıdaki tablo için Hamming distance değerleri eşittir.
d(000, 011) = 2 d(000, 101) = 2 d(000, 110) = 2

d(011, 101) = 2 d(011, 110) = 2 d(101, 110) = 2

Bir kodlama yöntemi C(x,y) 3 parametreyle ifade edilir: codeword boyutu (n), dataword boyutu (k) ve minimum Hamming distance (dmin).

İlk tablodaki kodlama C(3,2) ve dmin = 2, ikinci tablodaki kodlamada C(5,2) ve dmin = 3 şeklinde gösterilir. İletişim sırasında s tane hata olursa, gönderilen ve alınan codeword’ler arasındaki Hamming distance s olur. Tüm durumlar için s tane hatayı algılamak için, tüm çiftler arasındaki minimum Hamming distance değerinin s+1 olması gerekir.

Egzersiz

Aşağıdaki tabloda minimum Hamming distance = 2’dir. 1‐bit hata denetimi garanti edilir. Eğer üçüncü satırdaki codeword gönderilirse ve 1‐bit hata olursa, alınan codeword tablodakilerin hiçbirisiyle aynı değildir. Eğer 2‐bit hata olursa, alınan hatalı codeword tablodaki codeword’lerden birisiyle aynı olabilir ve hata algılanamaz. 

Dataword	Codeword
00	000
01	011
10	101
11	110

Aşağıdaki tabloda minimum Hamming distance = 3’tür. 2‐bit hata denetimi garanti edilir. Eğer geçerli bir codeword gönderilirse ve 2‐bit hata olursa, alınan codeword tablodakilerin hiçbirisiyle aynı olmaz.

Aynı tabloda 3‐bit hataların bazıları da tabloda geçerli olan bir codeword oluşturabilir.

Dataword	Codeword
00	00000
01	01011
10	10101
11	11110

Hata Denetimi (Error Detection)

Aşağıdaki şekilde bir x codeword ve etrafında s yarıçapında codeword kümesi vardır. Tabloda minimum Hamming distance değeri s’den büyüktür. dmin = s + 1 Diğer geçerli olan tüm codeword’ler çemberin dışındadır.

Hamming Uzaklığı Hata Denetimi

Hata Düzeltme (Error Correction)

Alıcı aldığı codeword’ün geçersiz olduğunu algılarsa, tablodan hangi codeword’ün gönderildiğini bulmaya çalışır. Her geçerli codeword, kendi etrafında t yarıçapında bir çember oluşturur. Alıcı aldığı geçersiz codeword’ün hangi geçerli codeword’e ait çemberde olduğunu belirler. Belirlenen çemberin ortasındaki codeword gönderilen gerçek codeword olarak alınır. Hata düzeltmede dmin > 2t olmalıdır. 

dmin = 2t+1

Hamming Uzaklığı Hata Düzeltme

Lineer Blok Kodlama (Linear Block Codification)

İki codeword arasındaki XOR sonucu yine geçerli bir codeword oluşturursa bu kodlar lineer blok kodlardır. Lineer blok kod için minimum Hamming uzaklığı değeri 0’dan farklı geçerli codeword’lerdeki en az 1 sayısına eşittir. Simple parity‐check code, en yaygın kullanılan hata denetim kodudur. Bu kodlamada k‐bit dataword n codeword’e dönüştürülür. (n = k+1) Extra bit toplam 1 sayısını çift veya tek yapmak için kullanılır. Bu kodlamada dmin=2’dir ve hata düzeltme yapılamaz sadece 1‐bit hata denetimi yapılır.

Dataword	Codeword	Dataword	Codeword
0000	00000	1000	10001
0001	00011	1001	10010
0010	00101	1010	10100
0011	00110	1011	10111
0100	01001	1100	11000
0101	01010	1101	11011
0110	01100	1110	11101
0111	01111	1111	11110

4‐bit dataword’e 1‐bit parity biti eklenir. Parity bit 5‐bit codeword’deki 1 sayısını çift yapılır. Dataword’deki 4‐bit mod 2'ye göre toplanır. (r0 = a3+a2+a1+a0), r0 değeri gönderilene eklenir ve alıcıda (s0 = b3+b2+b1+b0+ r0) değeri hesaplanır. Alıcıda sonuç (syndrome) 0 ise accept, 1 ise hatalı ve atılır(discard).

Parity Check Gönderici Alıcı Simülasyonu 

İki boyutlu(Two‐dimensional) parity check yaklaşımında her satır ve sütun için 1‐bit parity bit eklenir. 3‐bit hata denetimi yapılabilir.

İki Boyutlu Parity Check Simülasyonu

Hamming kodları dmin=3 ile tasarlanır. 2‐bit hatayı denetler ve 1‐bit düzeltir. m >= 3 olmak üzere n=2m ‐ 1 ve k= n ‐ m’dir. r = m denetlenen bit sayısıdır. Aşağıdaki tabloda m=3 ise n=7 ve k=4 olur. Hamming kod C(7,4), dmin=3 olur.

Dataword	Codeword	Dataword	Codeword
0000	0000000	1000	1000110
0001	0001101	1001	1001011
0010	0010111	1010	1010011
0011	0011010	1011	1011100
0100	0100011	1100	1100101
0101	0101110	1101	1101000
0110	0110100	1110	1110011
0111	0111001	1111	1111111

Egzersiz

C(7,4), dmin=3 için r0=a2+a1+a0, r1=a3+a2+a1, r2=a1+a0+a3 ve alıcıda s0=b2+b1+b0+q0, s1=b3+b2+b1+q1, s2=b1+b0+b3+q2 ile 3 sonuç (syndrome) hesaplanır. r'ler hesaplanırken seçilen 3 data bit ve 1 parity bitindeki toplam 1 sayısı çift olmalıdır. Bu şartı sağlayan her kombinasyon seçilebilir.

3 bit syndrome ile 8 farklı durum oluşturulur. Bu durumlar hata durumunu ve hata varsa hatalı biti gösterir. 0100 dataword, codeword 0100011 olarak gönderiliyor. Codeword 0100011 olarak alındığında syndrome 000 olur ve hata yoktur. 0111 dataword, codeword 0111001 olarak gönderiliyor. Codeword 0011001 alınıyor. Syndrome 011 hesaplanır. Tabloya göre b2 hatalıdır. b2 0’dan 1’e değiştirilir ve dataword 0111 olur. 1101 dataword, codeword 1101000 olarak gönderiliyor. Codeword 0001000 alınıyor (2‐bit hatalı). Syndrome 101 hesaplanır. Tabloya göre b0 hatalıdır. b2 1’den 0’a değiştirilir ve dataword 0000 olur(yani yine hatalı).

Hamming kodları 1‐bit hata düzeltir ve 2‐bit hata denetler. Burst errorlarda denetlenebilir. Burst error oluşan kısım farklı codeword’lere dağıtılır.

Hamming Uzaklığı ve Burst Error Simülasyonu

Halkalı Kodlama (Cyclic Codification)

Halkalı kodlama özel lineer blok kodlardır. Her halkalı kod döndürülebilir. Döndükten sonra oluşan kod geçerli bir codeword’tür. 1011000 codeword left‐shift yapılırsa codeword 0110001 olur ve geçerlidir. Cyclic Redundancy Check(CRC), LAN ve WAN ağlarda kullanılır. Kodlayıcıda 4‐bit dataword (k=4) ve 7‐bit codeword (n=7). Dataword’ün sağ kısmına 000 eklenerek 7‐bit codeword elde edilmiştir. Generator dataword’ü belirlenmiş olan divisor ile mod 2’ye göre böler. Bölüm atılır ve kalan dataword’e eklenerek codeword oluşturulur.

CRC Gönderici Alıcı Simülasyonu

Alıcı gelen codeword’ü alır. Checker gelen bitlerin hepsini alır. Kalan tekrar oluşturulur ve kontrol edilerek s2s1s0 syndrome oluşturulur. Decision logic bloğunda, gelen 4‐bit dataword’ü kabul eder veya iptal eder.

CRC Kodlayıcı (CRC Encoder)

Kodlayıcı dataword’ü alır ve n‐k adet 0 ekler. Elde edilen 7‐bit divisor ile bölünür. Toplama ve çıkarma işlemleri XOR ile yapılır. Her aşamada dividen(0000) ile divisor(1011) XOR'lanır. Sonuçta kalan 3‐bit dataword’e eklenir ve codeword elde edilir.

CRC Kodlayıcı Aşamaları

CRC Kod Çözücü (CRC Decoder) 

Kod çözücü ile kodlayıcıda yapılan bölme işlemi aynen yapılır. Bölmeden kalan syndrome oluşturur. Syndrome 000 ise hata yoktur.

CRC Kod Çözücü Aşamaları

Polinomlar (Polynomials)

Bir model 0 ve 1'lerle birlikte polinom halinde gösterilebilir. 7‐bit model 3 terimle gösterilebilmiştir. Polinomun derecesi en yüksek dereceli terimin derecesine eşittir. Polinomlarda toplama ve çıkarma aynı şekilde yapılır. Aynı dereceli olan çiftler silinir. Aynı dereceli 3 terim varsa ikisi silinir üçüncüsü alınır. Çarpma ve bölmede üstler toplanır veya çıkarılır.

(x5+x3+x2+x)(x2+x+1) = x7+x6+x3+x

Polinom Aşamaları

Sola kaydırma yapılırken sağa 0 eklenir.

10011 (x4 + x + 1) sola 3 kaydırma yapılırsa 10011000 (x7+x4+x3) olur.

10011 (x4 + x + 1) sağa 3 kaydırma yapılırsa 10 (x) olur.

Polinom bölme işleminde bölünen ilk terimi bölenin ilk terimine bölünür (x6/x3=x3) ve sonuç divisor ile çarpılır.

Polinom Bölme Aşamaları

Tabloda CRC kodları ve kullanıldığı yerler verilmiştir.

Reed‐Solomon kodu günümüzde hata denetimi ve düzeltmesi için yaygın kullanılmaktadır

Checksum

Checksum İnternette yaygın kullanılmaktadır. Gönderilen sayıların toplamı alınır ve birlikte gönderilir. Alıcı gelen sayıları toplar ve gelen toplamla karşılaştırır. Aynı ise data alınır değilse atılır. Checksum’da toplama işlemi birin tümleyeni(one’s complement) aritmetiğiyle yapılır.

Egzersiz
(7,11,12,0,6) decimal sayıları alıcıya gönderilsin.

İnternette 16‐bit checksum kullanılır. Gönderen mesajı 16‐bit parçalara böler ve hepsini 1 tümleyene göre toplar. Toplamın tümleyeni alınır ve checksum elde edilir. Alıcı aynı işlemleri tekrarlar. Checksum değeri 0 olursa hata yoktur.

16-Bit Cheksum Aşamaları

Bir sonraki yazımda görüşmek üzere...