Distance-vector Routing Protocol
Distance-vector Routing Protocol (mesafe-vektör yönlendirme protokolü) paket-anahtarlamalı ağlarla ilgili bilgisayar Iletişim(computer communication) kuramında yer alan iki ana sınıftan biridir. Diğeriyse bağlantı-durum (link-state) protokolüdür. Distance-vector yönlendirme protokolü yolların hesaplanmasında Bellman-Ford algoritmasını kullanır.
Distance-vector yönlendirme protokolü istekleri, periyodik olarak komşularının yönlendirme bilgisine ihtiyaç duyar. Bu bazen bir ağ topolojisinde bir seçim yapıldığında da gerekebilir.Bağlantı-Durum Protokolü ile karşılaştırılmak istenirse, Bağlantı-Durum protokolü içinde bulunduğu ağ topolojisinde tüm nodların(node) yönlendirme bilgisine ihtiyaç duyar. Distance-vector yönlendirme protokolü ise daha az hesaplama karmaşıklığına ve mesaj ek yüküne sahiptir.
Yönlendirici anlamına gelen Distance Vector yön ve mesafenin vektör ile tanımıdır. Yön basitçe yakındaki hop adres, çıkış arayüzü ve aynı zamanda bu hop adreslerin sayısıdır.
Distance-Vector yönlendirme protokolü kullanan yönlendiriciler bir hedefin tüm bilgilerine sahip değillerdir. Distance-Vector yönlendirme protokolü(bundan sonra DVRP diye anılacaktır) yerine iki yol kullanırlar:
- Arayuze iletilecek olan paketi veya yönü.
- Hedefe olan mesafeyi.
DVRP'ye örnek verecek olursak: RIPv1 ve v2(Bilgi Yönlendirme Protokolü) ve IGRP(İç geçit Yönlendirme Protokolü). EGP(Dış Geçit Protokolü) ve BGP(Sınır Geçit Protokolü) saf DVRP olup olmadıkları kesin değildir, çünkü bir DVRP yalnız bağlantı tabanlı yönlenmeleri hesaplar BGP'de ise bir ornek verilecek olursa, yerel bağlantı öncelik değeri bağlantı maliyeti üzerinden hesaplanır.
Yöntemler
Aynı temel özelliklere sahip farklı DV (Distance-Vector) tabanlı protokoller arasındaki yönlendirme gerektiren bir ağ için en iyi yol hesaplama metotları kullanılır.
Yönlendirme anlamına gelen DV mesafe ve yönün vektör ile tanımıdır. Yön basitçe yakındaki hop adres ve çıkış arayüzü, mesafe ise hopların adedidir.
DVP (distance-vector protokol)'yi kullanan yönlendiriciler hedefe olan tüm yolların bilgisine sahip değildir. DV yerine iki metot kullanırlar:
- Arayüze iletilecek olan paketi veya yolu,
- Hedefe olan uzaklığı.
DVP'nin isminden anlaşılacağı üzere bir ağdaki herhangi bir bağlantıya olan mesafeyi ve yönü hesaplama üzerine kurulmuştur. Ulaşılacak olan hedefin maliyeti değişken güzergâh ölçümleriyle hesaplanır. RIP (Yönlendirme Bilgisi Protokolü) hedefin hop adedini kullanır oysa IGRP mevcut bant genişliği ve nod gecikme bilgilerini de diğer hesaplardan alır.
Routerların bir kısmının veya tümünün aynı DVRP ile yapılandırılmış tüm komşularına yaptığı gönderilerin güncellemeleri DVP'de periyodik olarak yapılır. RIP çapraz-platform Dv yönlendirmesini destekler oysa IGRP ise bir Cisco Systems'in tescilli DVRP'sidir. Eskiden beri bir yönlendirici yansıma değişikliklerini ve bu değişiklikleri komşularına olan bilgisini tuttuğu yönlendirme tablomuzu düzenleyebilme bilgisine sahiptir. Bu süreç “söylenti ile yönlendirme” olarak tarif edilebilir, çünkü diğer yönlendiricilerden alınan bilgiye inanırlar. Aslında bu bilgi doğru ve geçerli ise bilginin hangi yönlendiriciden geldiği zaten belirlenemez. Bu gigi kararsızlık ve yanlış yönlendirme yapılmamasına yardım edebilecek bir sayıdır aslında.
Kısıtlamalar
Bellman-Ford algoritması meydana gelen yönlendirme looplarını ve sonsuza dek sayma probleminden bunların zarar görmelerini engelleyemez. Sonsuza dek sayma probleminin özü bir örnekle açıklamak gerekirse, A B'ye onun (yani B'nin) bir yola sahip olduğunu söylerse, A B'nin bu yolun en azından bir kısmına sahip olduğunu biliyor ve bu yol aslında B'ye ait değilse burada sonsuz bir dongü oluşacaktır. A B'ye sürekli söyleyecek B ise “benim yolum değil” mesajını döndürecektir... Problemde şüphesiz şu görünüyor: A-B-C-D-E-F arasında bağlı bir alt ağ olduğunu varsayarsak, yönlenmelerin sayısını ölçü olarak alalım. Şimdi A'nın aşağı gittiğini varsayarsak, vektör güncelleme sürecindeki B bildirimleri A'ya 1 mesafesinde yönlendirilecektir (aşağı). B A'dan vektör güncellemelerini alamaz. Problem şu, B C'den de güncellenebilir olsun, A'nın aşağıya olan hareketinin farkında olmayacaktır, öyle ki C B'ye A'nın C'den iki zıplamasını söylesin(C'den B'ye ve oradan A'ya), işte bu durum bir yanlıştır. Yavaşça ağda sonsuza ulaşana dek bu durum çoğalacaktır. (C algoritma içerisinde bir müdahaleyla bu durumdan kurtulabilir, Bellman Ford'un deyişiyle “rahat mülktür”tür. [yani algoritma değiştirilemez değildir.])
Kısmi Çözümler
RIP döngüsel ifadelerin kullanımını azaltmak için sonsuza dek sayma probleminin sayıcısı olan hopları, görüş bölme (Split Horizon) ve Poison Terslemesi(Poison Reverse) tekniklerini kullanır. Bütün bu önlem yapıları bazı yönlendirme döngülerinin oluşumunu önler,fakat hepsini önleyemez. Bir bekleme süresinin eklenmesi (yönlendirme yenilemesinden sonra yönlendirme güncellemeleri reddedilir) ile hemen hemen tüm döngülerin oluşması engellenir, fakat bunlar aynı zamanda kavuşma süresin de önemli artışlara neden olur. Bundan dolayı örgür-döngüye sahip DVRP olan EIGRP ve DSDV gelişti. Bunlar tüm durumlarda döngü oluşmasını önler fakat artan karmaşıklıklara göz yumulur, ayrıca OSPF olarak bilinen bağlantı-durum protokollerin bulunmasından sonra bu protokollerin yayılması da yavaşlamıştır.
Örnek
İçinde bulunduğumuz ağ A,B,C ve D olmak üzere 4 adet yönlendiriciden oluşsun:
Geçerli zaman veya iterasyonu T algoritması ile gösterelim ve ona doğrudan komşu olan her yönlendirici için yaratılan mesafe matrisleri tarafından bu algoritma başlatılsın (0 anında, T=0). Öyle ki yönlendirme tablolarımız aşağıdaki gibi olacaktır.(Tablolarda en kısa yollar yeşil renk ile yeni kısa yollar ise sarı renk ile vurgulanmıştır.)
| T=0 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bu noktada, tüm yönlendiriciler(A,B,C,D) kendi DV'leri için yeni kısa yollara sahiplerdir (bu mesafelerin listesi başka bir yönlendirici yardımıyla kendisinden komşusunadır).Onların her yeni DV yayını tüm komşularınadır: A -> B ve C'ye,B -> C ve A'ya, C A-B ve D'ye, D ise yalnızca C'ye. Öyle ki her komşu bu bilgiyi alır ve onun kullanacağı en kısa yolu yeniden hesaplarlar. Örneğin: C üzerinden D ile haberleşmeye çalışan A C'den yol mesafe bilgisiyle birlikte (burada 5) bir DV mesajı alıcaktır. C'ye olan kısa yolumuz 23, o zaman A C üzerinden D'ye gidebileceği en kısa mesafenin 23+5=28 olduğunu bilecektir. Burada A'nın diğer kısa yollar hakkında bilgisi olmadığı için, D'ye olan en kısa yolun C üzerinden olacağını tahmin edecektir. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| T=1 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Tekrar, tüm yönlendiriciler en kısa yol bilgilerine son iterasyonda(T=1) sahip olacaklar, tüm yayınları tüm komşularına ulaşacaktır; bu istemler her bir komşuya ulaşınca en kısa yol tekrar hesaplanır.... Örneğin: B üzerinden D ile haberleşmeye çalışan A B'den yol mesafe bilgisiyle birlikte (burada 7) bir DV mesajı alacaktır. B'ye olan kısayol 3 olduğuna göre,o zaman A D'ye olan uzaklığının 7+3=10 olduğunu bilecektir. Bu B üzerinden olan yol C üzerinden olandan daha kısadır (28->10), o halde yeni en kısa yolumuz bu olacaktır. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| T=2 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bu sefer, A ve D yönlendiricileri aralarındaki DV için yalnız bir tane en kısa yola sahip olacaklardır. Öyle ki onların komşularına yaptıkları yeni DV yayınları: A'nın yayını B ve C'ye, D'ninki ise C'yedir. Bu nedenle DV mesajlarını alan komşuları en kısa yolu yeniden hesaplarlar. Ancak, onların yönlendirme tablolarından herhangi bir en kısa yol bulunamaz ise, o zaman yönlendirme tablolarından bir seçim yapılamaz. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| T=3 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Yönlendiricilerin hiçbiri herhangi bir "en kısa yol"a sahip değildir. Bu nedenle, yönlendirilerin hiçbiri yönlendirme tablolarından yeni bilgi alamazlar. Böylece algoritma tamamlanır. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
İlave Bağlantılar
T=2 de B'den kaynaklanan hataları içerir.
Kaynakça ve Okunabilecek Kaynaklar
- "RFC1058 - Routing Information Protocol", C. Hedrick, Internet Engineering Task Force, June 1988 23 Mayıs 2010 tarihinde Wayback Machine sitesinde arşivlendi.
- "RFC1723 - RIP Version 2 Carrying Additional Information", G. Malkin, Internet Engineering Task Force, November, 1994 31 Ekim 2010 tarihinde Wayback Machine sitesinde arşivlendi.
- "RFC2453 - RIP Version 2", G. Malkin, Internet Engineering Task Force, November, 1998 24 Kasım 2009 tarihinde Wayback Machine sitesinde arşivlendi.
- "A Path-Finding Algorithm for Loop-Free Routing, J.J. Garcia-Luna-Aceves and S. Murthy, IEEE/ACM Transactions on Networking, February 1997
- "Detection of Invalid Routing Announcements in the RIP Protocol", D. Pei, D. Massey, and L. Zhang,, IEEE Global Communications Conference (Globecom), December, 2003
