logo

Mesafe Vektör Yönlendirme Algoritması

    Uzaklık vektörü algoritması yinelemeli, eşzamansız ve dağıtılmıştır.
      Dağıtılmış:Her düğümün doğrudan bağlı komşularının bir veya daha fazlasından bilgi alması, hesaplama yapması ve ardından sonucu komşularına geri dağıtması şeklinde dağıtılır.Yinelemeli:Komşular arasında değiş tokuş edilecek daha fazla bilgi kalmayıncaya kadar süreci devam etmesi nedeniyle yinelemelidir.Asenkron:Tüm düğümlerinin birbiriyle kilit adımında çalışmasını gerektirmez.
  • Uzaklık vektör algoritması dinamik bir algoritmadır.
  • Esas olarak ARPANET ve RIP'te kullanılır.
  • Her yönlendirici, olarak bilinen bir mesafe tablosunu tutar. Vektör .

Uzaklık Vektör Yönlendirme Algoritmasının çalışmasını anlamak için Üç Anahtar:

    Tüm ağ hakkında bilgi:Her yönlendirici bilgisini tüm ağ üzerinden paylaşır. Yönlendirici ağ hakkında topladığı bilgileri komşularına gönderir.Yalnızca komşulara yönlendirme:Yönlendirici, ağ hakkındaki bilgisini yalnızca doğrudan bağlantısı olan yönlendiricilere gönderir. Yönlendirici, ağ hakkında sahip olduğu her şeyi bağlantı noktaları aracılığıyla gönderir. Bilgiler yönlendirici tarafından alınır ve bilgileri kendi yönlendirme tablosunu güncellemek için kullanır.Düzenli aralıklarla bilgi paylaşımı:Yönlendirici 30 saniye içinde bilgiyi komşu yönlendiricilere gönderir.

Mesafe Vektör Yönlendirme Algoritması

bırak dX(y) x düğümünden y düğümüne giden en düşük maliyetli yolun maliyeti olsun. En düşük maliyetler Bellman-Ford denklemiyle ilişkilidir,

 d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} 

Nerede minv tüm x komşular için alınan denklemdir. x'ten v'ye gittikten sonra v'den y'ye en düşük maliyetli yolu düşünürsek, yolun maliyeti c(x,v)+d olacaktır.içinde(y). x'ten y'ye en küçük maliyet minimum c(x,v)+d'diriçinde(y) tüm komşuları ele geçirdi.

Uzaklık Vektörü Yönlendirme algoritması ile x düğümü aşağıdaki yönlendirme bilgilerini içerir:

  • Her v komşusu için c(x,v) maliyeti, x'ten doğrudan bağlı komşu v'ye giden yol maliyetidir.
  • Uzaklık vektörü x, yani DX= [DX(y) : N cinsinden y], tüm varış noktalarına olan maliyetini içeren, N cinsinden y.
  • Komşularının her birinin uzaklık vektörü, yani Diçinde= [Diçinde(y) : x'in her v komşusu için N'de y.

Uzaklık vektörü yönlendirmesi, x düğümünün uzaklık vektörünün kopyasını tüm komşularına gönderdiği eşzamansız bir algoritmadır. X düğümü, komşu v vektörlerinden birinden yeni uzaklık vektörünü aldığında, v'nin uzaklık vektörünü kaydeder ve kendi uzaklık vektörünü güncellemek için Bellman-Ford denklemini kullanır. Denklem aşağıda verilmiştir:

başka java
 d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N 

X düğümü yukarıdaki denklemi kullanarak kendi uzaklık vektör tablosunu güncellemiş ve güncellenmiş tablosunu tüm komşularına göndererek kendi uzaklık vektörlerini güncelleyebilmelerini sağlamıştır.

Algoritma

 At each node x, <p> <strong>Initialization</strong> </p> for all destinations y in N: D<sub>x</sub>(y) = c(x,y) // If y is not a neighbor then c(x,y) = &#x221E; for each neighbor w D<sub>w</sub>(y) = ? for all destination y in N. for each neighbor w send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to w <strong>loop</strong> <strong>wait</strong> (until I receive any distance vector from some neighbor w) for each y in N: D<sub>x</sub>(y) = minv{c(x,v)+D<sub>v</sub>(y)} If D<sub>x</sub>(y) is changed for any destination y Send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to all neighbors <strong>forever</strong> 

Not: Uzaklık vektör algoritmasında, x düğümü, doğrudan bağlı düğümlerden birinde herhangi bir maliyet değişikliği gördüğünde veya bir komşudan herhangi bir vektör güncellemesi aldığında tablosunu günceller.

Bir örnek üzerinden anlayalım:

Bilgi Paylaşımı

Mesafe Vektör Yönlendirme Algoritması
  • Yukarıdaki şekilde her bulut ağı, bulutun içindeki sayı ise ağ kimliğini temsil eder.
  • Tüm LAN'lar yönlendiricilerle bağlanır ve A, B, C, D, E, F olarak etiketlenen kutularda temsil edilirler.
  • Uzaklık vektörü yönlendirme algoritması, her bağlantının maliyetinin bir birim olduğunu varsayarak yönlendirme işlemini basitleştirir. Bu nedenle iletimin verimliliği, hedefe ulaşan bağlantıların sayısıyla ölçülebilir.
  • Uzaklık vektörü yönlendirmede maliyet, atlama sayısına bağlıdır.
Mesafe Vektör Yönlendirme Algoritması

Yukarıdaki şekilde yönlendiricinin bilgiyi yakın komşulara gönderdiğini görüyoruz. Komşular bu bilgileri kendi bilgilerine ekleyerek güncellenen tabloyu kendi komşularına gönderirler. Bu şekilde yönlendiriciler kendi bilgilerinin yanı sıra komşuları hakkındaki yeni bilgileri de alırlar.

Yönlendirme Tablosu

İki süreç meydana gelir:

  • Tabloyu Oluşturmak
  • Tablonun Güncellenmesi

Tabloyu Oluşturmak

Başlangıçta her yönlendirici için Ağ Kimliği, maliyet ve sonraki atlama noktası gibi en az üç tür bilgiyi içeren yönlendirme tablosu oluşturulur.

Mesafe Vektör Yönlendirme Algoritması
    NET kimliği:Ağ Kimliği paketin son hedefini tanımlar.Maliyet:Maliyet, paketin oraya ulaşmak için geçmesi gereken atlama sayısıdır.Sonraki atlama:Paketin teslim edilmesi gereken yönlendiricidir.
Mesafe Vektör Yönlendirme Algoritması
  • Yukarıdaki şekilde tüm yönlendiricilerin orijinal yönlendirme tabloları gösterilmektedir. Bir yönlendirme tablosunda, ilk sütun ağ kimliğini, ikinci sütun bağlantının maliyetini temsil eder ve üçüncü sütun boştur.
  • Bu yönlendirme tabloları tüm komşulara gönderilir.

Örneğin:

 A sends its routing table to B, F &amp; E. B sends its routing table to A &amp; C. C sends its routing table to B &amp; D. D sends its routing table to E &amp; C. E sends its routing table to A &amp; D. F sends its routing table to A. 

Tablonun Güncellenmesi

  • A, B'den bir yönlendirme tablosu aldığında, bu bilgileri tabloyu güncellemek için kullanır.
  • B'nin yönlendirme tablosu paketlerin 1 ve 4 numaralı ağlara nasıl taşınabileceğini gösterir.
  • B, A yönlendiricisinin komşusudur, A'dan B'ye gelen paketler bir atlamada ulaşabilir. Yani B tablosunda verilen tüm maliyetlere 1 eklenir ve toplam, belirli bir ağa ulaşmanın maliyeti olacaktır.
Mesafe Vektör Yönlendirme Algoritması
  • Ayarlamadan sonra A, birleştirilmiş bir tablo oluşturmak için bu tabloyu kendi tablosuyla birleştirir.
Mesafe Vektör Yönlendirme Algoritması
  • Birleştirilmiş tablo bazı yinelenen veriler içerebilir. Yukarıdaki şekilde, A yönlendiricisinin birleştirilmiş tablosu kopya verileri içerir, dolayısıyla yalnızca en düşük maliyete sahip verileri tutar. Örneğin A, verileri ağ 1'e iki şekilde gönderebilir. İlki, sonraki yönlendiriciyi kullanmaz, bu nedenle bir atlama maliyeti vardır. İkincisi iki atlama gerektirir (A'dan B'ye, ardından B'den Ağ 1'e). İlk seçenek en düşük maliyete sahiptir, bu nedenle tutulur ve ikincisi bırakılır.
Mesafe Vektör Yönlendirme Algoritması
  • Yönlendirme tablosu oluşturma süreci tüm yönlendiriciler için devam eder. Her yönlendirici komşularından bilgi alır ve yönlendirme tablosunu günceller.

Tüm yönlendiricilerin son yönlendirme tabloları aşağıda verilmiştir:

Mesafe Vektör Yönlendirme Algoritması