- 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:
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) = ∞ 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ı
- 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.
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.
- 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 & E. B sends its routing table to A & C. C sends its routing table to B & D. D sends its routing table to E & C. E sends its routing table to A & 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.
- Ayarlamadan sonra A, birleştirilmiş bir tablo oluşturmak için bu tabloyu kendi tablosuyla birleştirir.
- 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.
- 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: