Yönlendirme algoritmaları

Ağ katmanının ana görevi, kaynak makineden hedef makineye paketleri göndermektir. Gönderilen bu paketler, hedef makineye ulaşana kadar, değişik algoritmalar yardımıyla birçok düğümden geçerler. Verinin iletim ortamından hedefe ulaşmasını sağlayan bu yönlendirme algoritmalarından hangisinin kullanılacağına ağ katmanı karar verir. Bir yönlendirme protokolü, yönlendirme tablosunu yol bilgisi ile doldurur. Yönlendirme tablolarında, ağ katmanında tanımlanan yönlendirilmiş protokol IP, IPX gibi paketlerin bilgileri saklanır. Seçilen yönlendirme protokolü bu yönlendirme tablolarını kullanarak paketleri hedefine ulaştırır. Bir yönlendirme protokolü aşağıdakileri sağlamalıdır:

• Yönlendirme tablosunu dinamik olarak öğrenmek ve yönlendirme tablosunu ağdaki tüm alt ağlara giden yol bilgisi ile doldurmak
• Alt ağlara giden birden fazla yol bilgisi varsa yönlendirme tablosuna en iyi yol bilgisini koymak
• Tablodaki yol bilgilerinden geçerli olmayanları tespit edip tablodan çıkarmak
• Yönlendirme tablosundan bir yol bilgisi çıkartılırsa, bu bilgi için diğer komşu yönlendiricilerden kullanılacak başka bir yol bilgisi aramak
• En hızlı şekilde tablonun güncelliğini sağlamak
• Yönlendirmelerde döngü oluşmasını engellemek

Yönlendirme protokolleri yönlendirme tablolarını güncel ve kullanışlı yol bilgisi ile doldurur ve bu bilgiler sayesinde paket iletimini gerçekleştirirler. Bu işlem yolda bir adres arayan yolcu gibi düşünülebilir. Yolcunun elinde adres vardır ve yol üzerinde adrese ulaşabileceği yönleri gösteren tabelalar bulunur. Yolcu bu tabelaları takip ederek gitmek istediği yere ulaşır. Ancak yol üzerindeki tabelalar yanlış yerleştirilirse yolcu istediği noktaya ulaşamayacaktır. Bu tabelaları yerleştiren yol görevlisi bunların doğru olduğunu garanti etmelidir. Yönlendirme protokolleri bu yol bilgilerini yönlendirme tablosunda tutar ve doğruluğunu sağlar. Yönlendirme protokolleri birçok yönlendirme algoritması kullanır. Bunlar aşağıda açıklanmaktadır.

En etkili kural (Optimality Principle)

Yönlendiricinin ağdaki diğer yönlendiricilere ulaşabileceği en az hop sayısının olduğu yönlendirme algoritmasıdır. Her yönlendirici için bir derinlik ağacı ile belirlenir, bu ağacın derinliği en az olacak biçimde ayarlanır.

En kısa yol Yönlendirmesi (Shortest Path Routing)

Bu algoritmada ağ içerisindeki herhangi bir yönlendirici ağın tüm topolojisine sahiptir. Bunu Dijkstra’nın en kısa yol algoritması ile sağlar. Bu algoritmada, öncelikle bir yönlendirici kendisine komşu olan düğümleri listeler, her yönlendirici aynı işlemi yapar ve kendinden bir yönlendirici daha ilerleyerek bu işlem tekrarlanır ve tüm ağ topolojisinin bilgileri toplanır. Yönlendirme tablosu yol durumuna göre kendini yeniler ve güncelliğini korur.

En kısa yol seçimi için metrik değerleri kendimiz belirleriz bu bağlantı hızı, en düşük hop sayısı gibi değerler olduğu için, ağ içerisinde bazı bağlantıların kullanım maliyeti fazla olabileceğinden bu bağlantılar ölçüm dışında tutulur. Örneğin bir firma karasal hatlar yanında uydu hatları kullanıyorsa karasal hatlar sadece kendilerine tahsis edilirken uydu hatlarının aktardığı veri başına ücret ödediğinden uydu hatlarını acil durumlar için kullanır. Normal trafiği buradan kullanmaz.

Sel Yönlendirmesi (Flooding)

Bu algoritma da gelen paketlerin, paketin geldiği yol hariç diğer bir yönlendirilebilen yollara gönderilmesidir. Bu işlem su baskını benzeri, akan suyun açıklık bulduğu tüm yollara dağılması gibidir. Sabit bir algoritmadır. Bu yöntemde paketler sürekli olarak ağda dolaşır. Bunu önlemek için bazı yöntemler kullanılır. Paket başlığında her düğümde 1 azaltılan bir hop sayacı kullanılır. Ne zaman bu sayaç sıfır olursa paket silinir. Diğer bir yöntem de, yönlendiricilerin gönderdikleri paketleri bir saklayıcıda saklamasıdır. Aynı paket alındığında bu paket için tekrar gönderilme işlemi gerçekleşmeyecektir. Pratik bir yöntem değildir. Ama yönlendirici veritabanlarının değiştirilmesinde bu yöntem tercih edilebilir.

Mesafe Vektörü Yönlendirme (Distance Vector Routing)

Yönlendirme Bilgisi Protokolü (RIP) öncelikle kullanılan dinamik yönlendirme protokolüdür. Bu tip yönlendiriciler kendi yönlendirme tablolarını, bağlı oldukları yönlendiricilere bakarak dinamik şekilde oluştururlar. Her bir yönlendirici için hop değerine bir eklerler. Mesafe vektörü ile her bir yönlendirici kendi yönlendirme tablosunu dakikada bir kere güncelleyecektir.

Bu yöntemde her bir yönlendirici diğer ağlara ulaşmak için hop sayma bilgisini yakınındaki yönlendiricilerden alacaktır. Ancak aldığı bu bilgiler her zaman gerçeği yansıtmayabilir. Bu nedenle bazı durumlarda yanlış yönlendirme ve hop sayma bilgisi oluşabilir. Yönlendirme bilgisi ikince el bilgi olduğu için bu bilginin doğruluğu hiçbir zaman kanıtlanamayacaktır. Bu ise bir güvenlik açığı anlamına gelmektedir. Dolayısı ile çoğu kuruluş statik yönlendirme tablosu veya bağlantı durumu protokolü kullanır.

Bağlantı Durumu Yönlendirme (Link State Routing)

Bağlantı durumlu yönlendiriciler, birkaç önemli fark dışında mesafe vektörüne benzer işlev görürler. Bu yönlendiriciler öncelikle tabloları güncellerken birinci el bilgiler kullanılar. Bu sadece yönlendirme hatalarını elimine etmez, buluşma zamanını azaltarak sıfıra yaklaştırır. Bağlantı durumu yönlendirmede, yönlendirici A açıldığı zaman, bir RIP paketi olarak “hello” mesajı gönderir. Bu mesaj her porttan gönderilir. A yönlendiricisi B ve C'de cevap aldığında bir bağlantı kurulur. Bu bağlantı aşağıdaki bilgileri içerir.

• Yönlendiricinin adı veya kimliği
• Bağlı olduğu ağ'lar
• Her bir ağa erişim için gerekli hop sayısı veya maliyet
• Onun "hello" çerçevesine cevap veren her ağdaki diğer yönlendiriciler

Yönlendirici A'nın “hello” mesajını alan diğer yönlendiriciler bu mesajı yönlendiricilere kopyalarlar. Böylece ağdaki her aktif yönlendiricinin cevabı A'ya gelerek bir bağlantı kurulur. Bağlantı durumlu ağ faal olarak çalışırken, B ve C yönlendiricileri yeniden yönlendirme tablolarını oluşturmak yerine, A'dan bir bölüm kopyalarlar. Böylece zamandan tasarruf edilmiş olur. Eğer C yönlendiricisi normal olarak kapatılırsa, B'ye bir çerçeve gönderir. Bunun üzerine B, kendi tablosundan C'nin bilgisini siler ve A'ya da bu bilgiyi gönderir. Eğer C arızalanır ise, B'nin bunu anlaması için bir gecikme olur. Bundan sonra B tablosundan C'yi siler ve durumu A'ya bildirir. Her bir yönlendiricinin yönlendirme tabloları doğru ve şebekemiz güncelleme için minimum zaman gerektirir. Bağlantı durumunun maksimum büyüklüğü 127 olabilir.

Çoğu bağlantı durumlu yönlendirme protokolü, dinamik yönlendirme güncellemenin yapacağı kaynak için bir yetkilendirme seviyesi sağlar. Böylece bir parola ve kullanıcı adı ile yönlendirme protokolü daha güvenli hale gelir.

Hiyerarşik Yönlendirme (Hierarchical Routing)

Ağ büyüdükçe, buna orantılı olarak yönlendirme tablolarının genişlği artar. Sadece yönlendiricinin belleği değil işlemci gücünün yetersizliği yanında yönlendirme tablolarının birbirlerine transfer edilmesindeki gereken band genişliği ihtiyacı da artar. Bu nedenle yönlendirme, telefon iletişiminde olduğu gibi hiyerarşik şekilde yapılır.

Hiyerarşik yönlendirme yapıldığında her bir yönlendiricinin sorumlu olduğu yönlendirme bölgeleri belirlenir. Böylece her bir yönlendirici sorumlu olduğu bölgedeki alt ağlara yönlendirme yapar. Fakat diğer ağların yapısı hakkında bilgi sahibi değildir. Kendi yönlendirme bölgesine girmeyen paketleri bir üst yönlendiriciye gönderir.

Hareketli İstasyonlarda Yönlendirme (Routing for Mobile Hosts)

Günümüzde milyonlarca insan, dünyanın neresinde olursa olsun kendi e-postalarını dosya sisteminden okumak için artan sayıda hareketli iş istasyonu kullanmaktadır. Bu hareketli iş istasyonları yönlendirme konusunda yeni bir problem ortaya çıkarmışlardır. Bu mimaride bir hareketli istasyonun değişmeyen sabit bir yerleşim konumu vardır. Bu konumun adresinden sabit konumun yeri belirlenir. Burada problem sabit yerleşik konum adresinden, hareketli istasyonun paketlerinin nasıl yönlendirileceğidir. Bir hareketli istasyon yabancı YAŞ girdiği zaman paketlerin yönlendirilmesi için aşağıdaki olaylar gerçekleşir.

• Yabancı YAŞ'deki yabancı etmen periyodik olarak varlığını ve adresini belirten paket broadcast eder. Gelen bir yabancı istasyon bu paketi arar.
• Hareketli istasyon yabancı etmen ile yerleşik adresini, veri katmanı adresi ve güvenlik bilgilerini kullanarak kendisini kayıt ettirir.
• Yabancı etmen, hareketli istasyonun yerleşik etmeni ile iletişim kurarak, yerini hareketli host'a bildirir. Hareketli etmenden gelen mesajlar, yabancı etmenin adresi ile birlikte yerleşik etmene ulaşır.
• Yerleşik etmen güvenlik bilgisini denetleyerek, yabancı etmeni bilgilendirir.
• Yabancı etmen, yerleşik etmenden olumlu mesaj almış ise, tablosuna hareketli hostun bilgisini ekleyerek onu kayıt eder.

Yayımlayarak Yönlendirme (Broadcast Routing)

Bazı uygulamalarda konaklar, birden fazla veya diğer bütün konaklara mesaj göndermek isteyebilirler. Örneğin bir servis hava raporlarını bütün bilgisayarlara yaymak isteyebilir. Bütün bilgisayarlara eşzamanlı olarak paket gönderme işlemine yayınlamak (broadcasting) adı verilir.

İlk yayınlama yöntemi, bir istasyonun bütün diğer istasyonların adreslerini toplayarak alt ağ'a paket yollamasıdır. İkinci yayınlama yöntemi ise, sel yayınlama (flooding) dır. Bu yöntemde her istasyon ile birebir bağlantı kurularak çok miktarda paket üretilerek gönderilir.

Üçüncü yöntem ise, çok varışlı yönlendirmedir. Bu yöntemde, her bir paket ya bütün varış konaklarının adresini ya da varış istasyonlarını gösteren bir bit haritası içerir. Yönlendirici paketi aldığı zaman, varış adresini test ederek paketlerin kopyalarını üreterek varış konaklarına iletilmek üzere her bir bağlantı hattına verir.

Dördüncü yöntemde bir tür kapsama ağacı niteliğinde olan ve her bir yönlendiricinin dağılım ağacı(sink tree) elde edilerek paketler gönderilir. Yönlendirici her bir hattındaki paketin en az bir adet host'a gideceğini bilir.

Son yayımlama algoritması ise, bir öncekinin davranışına bağlı olarak yönlendirme yapılan ters yol ileri göndermedir. Bu yöntemde yönlendirici kapsama ağacı hakkında bir şey bilmesede yönlendirme gerçekleşebilir. Gönderilen paketler alıcı tarafından tekrar kaynak yönlendiriciden gelen hat dışındaki diğer bütün hatlara dağıtılır.

Çoğa göndererek Yönlendirme (Multicast Routing)

Bazı uygulamalar, gruplar ile çalışırlar. Bu durumda, gönderilen mesajlar altağ'daki konakların bir grubuna adreslenir. Bu işleme multicasting, yönlendirmeye de multicast yönlendirme adı verilir. Multicast yönlendirme grup yönetimi gerektirir. Multicast yönlendirme için her bir yönlendirici diğer tüm yönlendiricileri içeren kendi kapsama ağacını hesaplar. 2 grup olduğu durumda her bir grup için hesaplanan kapsama ağaçları gösterilmiştir. Bir süreç bir gruba multicast paket gönderdiği zaman ilk yönlendirici kendi kapsama ağacını inceler ve gruptaki hostlara ait olmayan yolları budar.

Kaynaklar ve Dış bağlantılar

• GYTE Bilgisayar Ağları Ders Notları 1 Nisan 2010 tarihinde Wayback Machine sitesinde arşivlendi.
• Routing Algorithms 24 Kasım 2009 tarihinde Wayback Machine sitesinde arşivlendi.
• Andrew S. Tanenbaum, Computer Networks, Prentice Hall 2003.