İçindekiler
- Yönlendirme algoritmaları
- Uzaklık vektörü,
- En kısa yol
- Taşkın
- Bağlantı durumu
- Yönlendirme protokolleri
- RIP, OSPF, BGP
- IPv6 yönlendirme
Yönlendirme
IP ağları gibi datagram yapısına sahip ağlarda her bir paket için yönlendirme gereklidir. Yani ağ katmanında router, iletilmek istenen paketin hedef adresine bakmalı ve bu paketi iletebileceği en iyi yolu yönlendirme tabloları yardımıyla seçmelidir.
Bu açıdan yölendiricilerin hedefe giden uygun yolları belirleme sürecinde yönlendirme tabloları önem taşır. Asıl problem bu yönlendirme tablolarının nasıl oluşturulduğudur.
Kısaca, datagram ağlarında hedefe giden uygun yolun belirlenmesi için yönlendirme tablolarının oluşturulması ve bu tablolara bakılarak datagramın bir sonraki uygun düğüme aktarım işlevi yönlendirme (routing) olarak tanımlanabilir.
Ancak veri bağı katmanında benzer bir süreç gibi görünen switch ise iletim tabloları yardımıyla iletim (forwarding) yapar. Bu açıdan routing ile forwarding birbirine karıştırılmamalıdır.
Yönlendirme – Grafik Teorisi
Yönlendirmedeki temel problem, iki düğüm arasındaki en düşük maliyetli yolu bulmaktır.
Şekildeki ağın grafik gösteriminde A’dan F’ye kadar olan düğümler, kenar maliyetleri ile etiketlenmiştir.
Grafikteki her bağlantı iki düğüm arasındaki kenar maliyetlerini ifade etmektedir.
- Yönlendiriciler:{A, B, C, D, E, F}
- Bağlantılar={(A,B), (A,E), (A,F),…}
- Maliyet(Cost) = C(A,B) = 3
- A-C arası maliyet C(A,C) = C(A,E)+C(E,B)+C(B,C) = 1+1+4 = 6 birim
Algoritmalar–Uzaklık Vektör (Distance Vector)
Uzaklık vektör algoritmasındaki temel yaklaşım her düğüm, diğer tüm düğümlerle olan mesafaleri tanımladığı tek boyutlu (vektör) dizi oluşturur.
Bu tanımlar, komşu düğümlere dağıtılır.
Başlangıçta tüm düğümler kendilerine doğrudan bağlı komşularının uzaklıklarını bildiği varsayılır.
Bu maliyetler yönlendiricinin yapılandırılması sırasında ağ yöneticisi tarafından tanımlanabilir.
Bir düğüm eğer erişilemez ise maliyeti, sonsuz (∞) olarak atanır.
Uzaklık Vektör (Distance Vector)
Aşağıdaki network grafı için uzaklı vektör algoritması örneği;
Tüm düğümler arasındaki maliyet 1 birim olduğu için graf gösteriminde etiketlenmemiştir.
Tüm düğümler sadece komşu düğümleri ile olan mesafelerini tanımlarken, bağlı olmadığı düğümlerle olan mesafeleri sonsuz kabul edilir.
Başlangıçta genel görünümün aksine her düğüm sadece doğrudan bağlı olduğu komşuları ile bağlantı maliyetlerini içeren kayıtları bilmektedir.
Örnek ağ modelinde tüm düğümlerin birbirleri arasındaki bağlantı maliyeti 1 birim kabul edilirse, başlangıçta A düğümünde tanımlanan maliyet vektörü aşağıda görülmektedir.
Sonraki adımda her düğüm tanımladığı mesafe vektörünü kendisine doğrudan bağlı komşularına iletmektedir.
Örneğin F düğümü, A düğümüne, G’ye 1 birim maliyetle erişebileceğini bildirir. A, F’ye 1 birim maliyetle erişebileceğini bildiği için F’nin G’ye erişim maliyetine bu maliyete ekler. Yani G’ye erişim maliyetini 2 birim olarak hesaplar.
Benzer şekilde A, C’den D’ye 1 birim mesafe ile erişebildiğini öğrenir. C’ye olan maliyeti de ekleyerek D’ye 2 birim ile erişebileceğini hesaplar. Aynı şekilde C üzerinden B’ye 1 birim ile erişebileceğini öğrenir ve B’ye toplam maliyet 2 birim olarak hesaplanır ancak B’ye erişimin mevcut mesafe maliyeti daha iyi olduğu için bu bildirim dikkate alınmaz.
Son aşamada, bir ağdaki tüm düğümler için sonraki düğüm ve maliyet bilgilerini içeren yönlendirme tabloları güncellenmiş olur.
Bu algoritmada mesafe vektörlerinin dağıtımı birkaç saniye yada birkaç dakikada arasında tanımlanan belirli T-periyotlarda komşular arasında gerçekleşirken, bir yönlendiricinin tanımlarında ortaya çıkan değişimle de bu dağıtım tetiklenebilir (trigger).
Bu durum herhangi bir yönlendiricinin arızalanması durumunda sonsuza sayma problemine neden olabilir.
Bir yönlendiricinin arızalı olduğuna, belirli peryotlarla alınması gereken mesafe vektörlerinin gelemediği yada kontrol mesajlarına onay (ack) alınmadığı durumlarda karar verilir.
Bu durumda bir düğümün bir yönlendiricinin arızalı olduğuna karar vermesi sonrasında yönlendirme tablosunu güncelleyecek ve bu yeni bilgiyi komşularına iletecektir.
F düğümü, G’nin arızalı olduğunu algıladığında, G’nin mesafe tanımını, sonsuz olarak ayarlar ve bu vektörü komşusu olan A’ya iletir.
A düğümü, G’ye F üzerinden eriştiği için yönlendirme tablosunda G’yi sonsuz olarak günceller.
Ancak A’ya C üzerinden gelen mesafe tanımında C üzerinden G’ye, 2 birimlik yol, mevcut sonsuz tanımından daha iyi bir yol olduğu için A düğümü yönlendirme tablosunu G’ye C üzerinden 3 birim olarak günceller.
Benzer şekilde F düğümü de A üzerinden G’ye 4 birimle güncellenecektir ve sistem stabilize olacaktır.
Uzaklık Vektör – Sonsuza sayma
Örneğin E düğümünün arızalı olduğunu tespit eden A düğümü mesafe tanımını sonsuz olarak işaretleyecektir.
B düğümü A’dan sonsuz olarak gördüğü E düğümüne, C üzerinden 2 birimle erişebileceğini belirleyip E’nin mesafesini C üzerinden 3 birim olarak tanımlayacaktır.
B’deki bu tanım önce A düğümüne 4 birim olarak yansıyacak, ardından A üzerinden C düğümüne 5 birim şeklinde iletilecektir.
Sonraki adımda B’ye E düğümü için mesafe tanımı C üzerinden 5 birim olarak gelecek ve tablo C üzerinden 6 birim şeklinde güncellenecektir.
Ortaya çıkan bu durum sonsuza sayma olarak isimlendirilir.
Bu sorunun en basit çözümü maksimum atlama
mesafesini 16 gibi bir rakamla sınırlandırmaktır.
Diğer yöntem ise öğrendiği yönlendirme tanımını,
öğrendiği komşusuna göndermemektir. Yada bu
tanım komşu düğümden gelen negatif tanım olarak
tanımlanır.
Taşkın Algoritması (Flooding)
Bu algoritmadaki temel fikir, kendisine doğrudan bağlı tüm komşularına bağlantı durum bilgilerini göndermeye dayanır. Bu paketi alan diğer bir düğüm, paketi aldığı düğüm dışındaki diğer komşularına iletir. Bu bilgi akışı tüm ağı kapsayıncaya kadar devam edecektir.
Bir bağlantı durum paketi; NodeID, Komşu Bağlantı Maliyet Listesi, Sıra Numarası ve TTL değerlerini içerir. Durum paketleri listede bir değişim olduğunda yada belirli periyotlarla oluşturulmaya devam eder.
Bir yönlendiriciye, aynı komşusundan daha düşük yada aynı sıra numarasına sahip bir paket gelirse, iletilmeden atılır. Benzer şekilde TTL’si sıfıra ulaşan paket atılır.
En Kısa Yol Algoritması (Dijkstra’s Shortest path)
Taşkın algoritması bağlamında her düğüm komşusuyla olan maliyet listesini diğer düğümlerle paylaştığı için her bir düğüm mevcut ağın topolojisine hakimdir. Ancak bu topolojiye uygun en kısa yoların belirlenmesi gerekmektedir.
Bunun çözümü Dijkstra’s Shortest path algoritmasıdır. Algoritma Geçici ve Onaylanmış olmak üzere iki tane liste (Hedef, Maliyet, SonrakiDüğüm) tutar. Algoritmanın işlem adımları;
1.İlgili düğüm kendisi için Onaylanmış ve maliyeti sıfır olan bir kayıtla başlar.
2.Önceki adımda Onaylanmış listeye eklenen düğüm için doğrudan bağlı komşularının maliyetlerini içeren bağlantı durum paketleri çağrılır.
3.Gelen her komşu maliyetine, kendisi ile o bilginin geldiği komşu arasındaki maliyet de eklenerek yeni maliyet hesaplanır.
a.Eğer hesaplanan komşu Onaylı ve Geçici listede yoksa bu kayıt Geçici listeye eklenir.
b.Eğer Geçici listede var ve yeni maliyet daha düşükse kayıt değiştirilir.
4.Eğer Geçiçi liste boşsa bitirilir. Dolu ise geçici listedeki en düşük maliyetli düğüm Onaylı listeye alınır ve 2. adımdan işleme devam edilir.
Bağlantı Durum Algoritması (link-state)
Bu algoritma, taşkın (flooding) ve en kısa yol (Shortest path) algoritmalarının birlikte kullanıldığı algoritmadır.
Bu algoritma En kısa yol algoritmasının dinamik hali olarak da ifade edilebilir.
Belli periyotlarla bağlantı durum paketi (link-state packet – LSP) olarak isimlendirilen komşu düğümler için mesafe tanımlarının taşkın algoritması ile diğer düğümlere dağıtımı sonrasında en kısa yolların dijkstra algoritması ile belirlenmesine dayanır.
Modern anlamda OSPF ve IS-IS protokollerinde kullanılır.
YÖNLENDİRME PROTOKOLLERİ
RIP Protokolü
Routing Information Protocol (RIP), Unix sistemlerde kullanılan bir dahili (IGP) yönlendirme protokolüdür.
RIP, uzaklık-vektör algoritmasına dayanan bir protokoldür. Ağlar arası mesafe maliyetini atlama sayısına bakarak belirler.
Maksimum atlama mesafesini (maliyet), sonsuza sayma problemine düşmemek için 16 olarak kabul eder. 16 ve üzeri atlama mesafesine sahip yönlendiricileri ulaşılamaz olarak tanımlar ve 180 sn. bilgi alınamayan düğümler de ulaşılamaz olarak işaretlenir.
Uzaklık-vektör protokolüne uygun olarak 30 sn.’de bir komşular arası bilgi paylaşımı yapılır.
RIP Protokolü – Paket formatı
Command: 1->istek, 2->cevap
Family: Kimlik doğrulama için kullanılır
Yenileme Konusundan önce Ağ Katmanı 2 Konusu İçin – Tıklayınız