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 yonlendirme 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 metodları 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 metod 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üzergah ölçümleriyle hesaplanır. RIP (Yönlendirme Bilgisi Protokolü) hedefin hop adedini kullanır oysa IGRP mecvut 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ürec “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 yonlendiriciden geldiği zaten belirlenemez. Bu bigi kararsızlık ve yanlış yönlendirme yapılmamasına yardım edebilecek bir sayıdır aslınlında. Kısıtlamalar Bellman-Ford algoritması meydana gelen yönlendirme looplarını ve sonsuza dek sayma probleminden bunların zarar gormelerini 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 bi 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 soyleyecek 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, öyleki 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üdehaleyla bu durumdan kurtulabilir, Bellman Ford'un deyişiyle “rahat mülktür”tür. 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 gosterelim ve ona doğrudan komşu olan her yonlendirici için yaratılan mesafe matrisleri tarafından bu algoritma başlatılsın (0 anında, T=0). Öyleki 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.) | | | |- |colspan=5| 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önlendiri 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.Öyleki 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 | | | | |- |colspan=5| Tekrardan, 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 tekrardan 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 | | | | |- |colspan=5| Bu sefer, A ve D yönlendiricileri aralarındaki DV için yalnız bir tane en kısa yola sahip olacaklardır. Öyleki 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 | | | | |- |colspan=5| 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 * A Java applet implementing Distance Vector algorithm for pedagogical purposes T=2 de B'den kaynaklanan hataları içerir. Referanslar ve Okunabilecek Kaynaklar * "RFC1058 - Routing Information Protocol", C. Hedrick, Internet Engineering Task Force, June 1988 * "RFC1723 - RIP Version 2 Carrying Additional Information", G. Malkin, Internet Engineering Task Force, November, 1994 * "RFC2453 - RIP Version 2", G. Malkin, Internet Engineering Task Force, November, 1998 * "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
Kaynaklar
Vikipedi

Distance-Vector Routing Protocol

Distance-Vector Routing Protocol Hakkında Detaylı Bilgi

Kaynaklar

Görüşler ve Yorumlar