Yönlendirme Algoritmaları
Protokol kümelerindeki ağ katmanının (OSI’ nin 3. katmanı) en temel işlevi yönlendirmedir. Yönlendirme, bir düğümün, alıcı adresi içerisinde olan bir IP paketi, alıcısına en uygun yoldan ulaşması için, komşu düğüme geçirme mekanizmasıdır.
Bağlantılı düzende (connection oriented) çalışan bir ağda bu mekanizma, görüntü devre kurulurken en uygun komşuyu belirler ve veri paketleri hep aynı yörüngeden ilerlerler. Bağlantısız düzenli ağlarda bu mekanizma, her gelen pakette yeniden karar verir.
Algoritmalar, yönlendirme tablolarının güncellenmesi açısından statik ve dinamik, gerçekleştirilmesi açısından uzaklık vektörü (DVA) ve bağlantı durumu algoritması (LSA) olarak sınıflanmıştır:
Tablo Güncellenmesi:
·Statik
·Dinamik
Gerçekleştirilmesi:
·Uzaklık Vektörü Algoritması (Distance Vector Algortihm)
·Bağlantı Durumu Algoritması (Link State Algorithm)
Statik Algoritmalar
Ağ işletime alınmadan önce, yönlendirme bilgisi cihazlar üzerindeki yönlendirme tablolarına girilir ve değiştirilmediği sürece sabit kalır. Örneğin, eğ iyi yönlendirme kriteri için minimum iletim süresi göz önüne alınacaksa, ağın işletiminden önce her bir yöndeki iletim süresi hesaplanmalı ve yönlendirme algoritması iki uç arasında en kısa sürede iletimi gerçekleştiren yolları belirlemelidir.
Örneğin şekil-5.3.’de görülen örnek ağda düğümler arasında birden çok alternatif yol vardır ve iki düğüm arasındaki yol iletim süreleri (veya maliyetleri) kirişlerin ortalarında verilmiştir. Buna göre düğümler arasında en hesaplı yol maliyetleri hesaplanabilir. Örneğin A düğümü için en uygun yol aşağıdaki gibi hesaplanabilir:
·A ® B: 1
·A ® C: 2
·A® D: (A®C®D güzergâhından): 3
·A® E: (A®C®D®E güzergâhından): 4
·A® F: (A®C®D®E®F güzergâhından): 6
Şekil-5.3. Yönlendirme için maliyetler
Bu hesaba göre A düğümünün yönlendirme tablosu aşağıdaki gibi olur:
A düğümü Yönlendirme Tablosu
Alıcı Düğüm
Yönlendirilecek Yol
B B C C D C E C F B
Adaptif Algoritmalar
Düğümler eğ topolojisindeki değişiklikleri ve trafik yoğunluğunu izleyerek ağın o anki durumuna göre karar verirler. Bu yapıda düğümler periyodik olarak kendi durumlarını belirten durum paketleri komşularına geçirirler ve kendi yönlendirme tablolarını belirli aralıklarla güncellerler.
Adaptif yönlendirme kullanılmasının en olumlu yanı, geçici tıkanma sorunlarını kendiliğinden çözebilmesidir; aktarım için tek bir yol varsa ve yol kopmuşsa iletim elbette gerçekleşmez, ancak birden fazla yol varsa, hemen ikinci en uygun yol kullanılır.
Adaptif yönlendirme algoritmaları merkezi ve dağılmış denetimli olarak iki sınıfa yarılır. Yönlendirme algoritması, merkezi denetimli bir ağda, tek bir ağ denetim düğümünde koşar. Bu düğüm, durum paketleriyle gelen bilgiyi kullanarak yönlendirme algoritmasını koşturur ve her bir düğüme yönlendirme tablolarında yapması gereken güncellemeleri haber verir.
Uzaklık Vektörü Algoritması (Distance Vector Algortihm- DVA)
DVA algoritması, yönlendiriciler arasında uzaklık bilgisinin (veya atlama sayısının) metrik değer olarak kullanılmasına dayanır. Her yönlendiricide paketlerin gönderilebileceği diğer komşu yönlendiriciler için uzaklık vektör tablosu oluşturulur; en uygun yola bu vektöre dayanılarak karar verilir.
Uzaklık vektörü, komşu olan yönlendiricilere göre hesaplanır. Yönlendiriciler, kendi taraflarındaki yönlendirme tablosu bilgilerini, diğer tüm komşu yönlendiricilere yayma yoluyla bildirir ve her yönlendirici kendisine gelen yeni durumları tuttuğu tabloya yansıtır. Yansıtma işi oldukça hızlı yapılmalıdır.
Eğer bu algoritma merkez yönlendiricilerde kullanılıyorsa ve yansıtma yavaş olursa, merkez yönlendiriciler için hızlı uyarlama gereksinimi sağlanmamış olunur ve yönlendirmede sorunlar çıkabilir. Normalde olmayan yere yönlendirme yapılabilir veya olan bir bağlantıya, henüz güncelleme yapılmadığı için, yokmuş gibi görünerek yönlendirme yapılmayabilir. Bu algoritmada atlama sayısına dayanılarak en kısa yol kullanılır ve yönlendirme tablosunun güncellenmesi için yönlendiriciler arasındaki trafiğin bir miktar artmasına neden olur. Bu algoritmada güncelleme bilgisi yalnızca komşu yönlendiricilere yapılır; ancak gönderilen bilgi, genelde tüm yönlendirme tablosunun aktarılması şeklinde olur.
Bağlantı durumu algoritması (Link State Algorithm- LSA)
LSA algoritması, en uygun yolun belirlenmesi için kullanılan metrik değeri, uzaklık bilgisinin yanı sıra yönlendiricilere yapılmış olan bağlantıları da göz önüne alarak hesaplanır. Bu algoritmada, ağ içindeki bir yönlendirici ağın tüm topolojisi hakkında bilgi sahibidir. Herhangi bir yönlendirici, kendisine olan bağlantıda bir değişiklik olduğunu algıladığı zaman, bu değişikliği tüm ağa yayma yoluyla bildirir. Ancak bu yayma işlemi tüm yönlendirme tablosunun gönderilmesi şeklinde olmayıp yalnızca algılanan değişikliğin bildirilmesi şeklindedir. Uzaklık vektörü algoritmasında (DVA’ da) ise komşu düğümlere gönderilen yönlendirme tablosu bilgileri daha fazladır; genelde, yönlendirme tablosunun tamamı veya büyük bir kısmı gönderilir. Bu durum, uzaklık vektörü algoritmasının ağı daha fazla yüklemesi anlamına gelir; ancak gönderme işlemi yalnızca komşu düğümlere yapılır…
Bağlantı durumu algoritmasında, algılanan değişiklik ağdaki, yine bu algoritmayı koşturan tüm yönlendiricilere bildirilir; ancak değişikliği içeren paketin kısa olması ve algoritmanın uzaklık vektörü algoritmasına göre daha gerçekçi yönlendirme yapması nedeniyle daha çok merkez yönlendiricilerde kullanılmaktadır. Bu algoritma daha fazla işlem gücü gerektirdiğinden buna sahip yönlendiriciler daha güçlü donanıma sahip olmalıdır. Çünkü metrik değerin hesaplanması için daha çok parametre göz önüne alınmaktadır.
RIP, OSPF, IGP gibi birçok yönlendirme protokolü bu iki algoritmadan birine dayanır. Örneğin IP ağlarda oldukça fazla kullanılan RIP, uzaklık vektörü algoritmasına; OSPF ise, bağlantı durumu algoritmasına dayanır.