Yönlendirme Algoritmaları
Yönlendirme algoritmaları, paketlerin bir ağ içinde izlediği yolları hesaplamaktadır; bu genellikle, yönlendiriciler ve bağlantılardan oluşan bir graf üzerinde, ya küresel bir bağlantı durumu görünümü kullanarak ya da dağıtık, komşu-komşu mesafe-vektör hesaplamasıyla en düşük maliyetli rotaları bularak gerçekleştirilmektedir.
Tanım
Bir yönlendirme algoritması, ağırlıklı bir graf olarak modellenen bir ağ üzerinden en düşük maliyetli (veya başka şekilde tercih edilen) yolları belirleyen, yönlendiricilerin paketleri hedeflerine taşımak için kullandığı iletme kararlarını üreten bir prosedürdür.
Kapsam
Bu konu, iletme tablolarını dolduran algoritmaları kapsamaktadır: bağlantı maliyetleri olan bir ağın grafik modeli; küresel olarak paylaşılan bir topoloji ile Dijkstra'nın en kısa yol algoritmasını kullanan bağlantı durumu yönlendirmesi; komşu değişimleriyle dağıtık Bellman-Ford hesaplamasını kullanan mesafe-vektör yönlendirmesi; bunların yakınsama davranışları ve sonsuza sayma problemi gibi patolojileri; ve ölçeklenebilirlik için hiyerarşik yönlendirme. Algoritmaları soyut olarak ele almakta, somut protokolleri (OSPF, RIP, BGP) ve bunların alan içi/alanlar arası organizasyonunu yönlendirme protokolleri konusuna bırakmaktadır.
Temel sorular
- Bir ağ, yönlendirme için ağırlıklı bir graf olarak nasıl modellenmektedir?
- Bir bağlantı durumu algoritması, tam bir topoloji görünümünden en kısa yolları nasıl hesaplamaktadır?
- Bir mesafe-vektör algoritması, yalnızca komşu değişimlerini kullanarak nasıl yakınsamaktadır?
- Sonsuza sayma gibi yakınsama ve kararlılık problemleri nelerdir ve bunlar nasıl hafifletilmektedir?
- Yönlendirme neden hiyerarşik hale getirilmektedir ve bu, yol optimalitesini nasıl etkilemektedir?
Anahtar kavramlar
- ağırlıklı ağ grafiği
- en düşük maliyetli yollar
- bağlantı durumu yönlendirmesi
- Dijkstra algoritması
- mesafe-vektör yönlendirmesi
- Bellman-Ford denklemi
- sonsuza sayma problemi
- bölünmüş ufuk ve zehirli tersine çevirme
- hiyerarşik yönlendirme
Temel kuramlar
- Bağlantı durumu yönlendirmesi (Dijkstra)
- Her yönlendirici, bağlantı maliyetlerini yayarak tüm yönlendiricilerin tam topolojiyi paylaşmasını sağlamakta, ardından en kısa yolları hesaplamak için bağımsız olarak Dijkstra algoritmasını çalıştırmaktadır; bu hızlı ve öngörülebilir bir şekilde yakınsamakta ancak küresel bilgi alışverişi gerektirmektedir.
- Mesafe-vektör yönlendirmesi (Bellman-Ford)
- Yönlendiriciler, her hedefe olan mevcut en düşük maliyet tahminlerini komşularıyla değiş tokuş etmekte ve Bellman-Ford denklemi aracılığıyla güncellemektedir; hesaplama dağıtıktır ve yalnızca yerel bilgi kullanmaktadır ancak yavaş yakınsayabilir ve sonsuza sayma probleminden etkilenebilmektedir.
- Hiyerarşik yönlendirme
- Düz yönlendirme tüm İnternet'e ölçeklenmediği için, yönlendiriciler bölgelere (otonom sistemler) ayrılmakta, yönlendirme her bölge içinde yerel olarak ele alınmakta ve aralarında özetlenmektedir; bu, ölçeklenebilirlik ve idari özerklik karşılığında yol optimalitesinden bir miktar ödün vermektedir.
Klinik önem
Yönlendirme algoritmaları, trafiğin ne kadar verimli ve güvenilir bir şekilde aktığını belirlemektedir: bağlantı durumu algoritmaları, arızalardan sonra hızlı yakınsayan OSPF gibi iç protokollerin temelini oluştururken, mesafe-vektör fikirleri RIP'te ve BGP'nin yol-vektör yaklaşımında yer almaktadır. Yakınsama davranışlarını anlamak, kararlı ağlar tasarlamak ve bağlantı veya yönlendirici arızalarından sonra yönlendirme döngülerini ve yavaş kurtarmayı teşhis etmek için esastır.
Tarihçe
Yönlendirmenin kalbindeki en kısa yol algoritmaları, bilgisayar ağlarından önceye dayanmaktadır: Bellman ve Ford'un 1950'lerin sonlarındaki yönlendirme problemleri üzerine çalışmaları ve Dijkstra'nın 1959'daki en kısa yol algoritması. Paket ağları büyüdükçe, bunlar mesafe-vektör ve bağlantı durumu yönlendirmesine uyarlandı ve otonom sistemlere hiyerarşik yapılandırma, yönlendirmeyi küresel İnternet'e ölçeklenebilir hale getirdi.
Tartışmalar
- Bağlantı durumu ve mesafe-vektör yönlendirmesi
- Bağlantı durumu yönlendirmesi hızlı yakınsamakta ve sonsuza sayma problemini önlemekte ancak her yönlendiricinin tam topolojiyi tutmasını ve daha fazla hesaplama yapmasını gerektirmektedir; mesafe-vektör ise daha basit ve daha yereldir ancak yavaş yakınsayabilir ve geçici döngüler oluşturabilmektedir; gerçek ağlar her iki fikri de farklı ölçeklerde birleştirmektedir.
Öne çıkan isimler
- Edsger W. Dijkstra
- Richard Bellman
- Lester Ford
İlgili konular
Temel eserler
- dijkstra1959
- bellman1958
- kurose2021
Sıkça sorulan sorular
- Sonsuza sayma problemi nedir?
- Bu, bir bağlantı arızalandıktan sonra, yönlendiricilerin eski bilgileri değiş tokuş ederek ulaşılamayan bir hedefe olan mesafe tahminlerini yavaşça artırdığı, yanlışlıkla birbirleri aracılığıyla hala bir yol olduğuna inandığı bir mesafe-vektör patolojisidir. Hafifletmeler arasında bölünmüş ufuk, zehirli tersine çevirme ve maksimum mesafeyi sınırlama bulunmaktadır.
- Bağlantı durumu ve mesafe-vektör neden her ikisi de kullanılmaktadır?
- Farklı kapsamlar için uygundurlar. OSPF gibi bağlantı durumu protokolleri, tam topolojinin paylaşılmasının kabul edilebilir olduğu tek bir idari alan içinde hızlı, döngüsüz yakınsama sağlamaktadır. Mesafe-vektör ve yol-vektör yaklaşımları daha iyi ölçeklenmekte ve alanlar arasında daha az dahili ayrıntı ortaya koymaktadır, bu nedenle BGP ağlar arasında bir yol-vektör tasarımı kullanmaktadır.