Bağlantı durumu yönlendirmesi, her yönlendiricinin mahallesinin bilgilerini ağlar arası ağdaki diğer yönlendiricilerle paylaştığı bir tekniktir. Bağlantı Durumu Yönlendirmesinin iki aşaması vardır.
Reliable Flooding (Güvenilir)
- Başlangıç durumu: Her düğüm, komşularının maliyetini bilir.
- Son durum: Her düğüm tüm grafiği bilir.
Route Calculation
Her düğüm, tüm düğümlere en uygun rotaları hesaplamak için Dijkstra‘nın grafik üzerindeki algoritmasını kullanır.
- Bağlantı durumu yönlendirme algoritması, Dijkstra’nın ağdaki bir düğümden diğer her düğüme giden en kısa yolu bulmak için kullanılan algoritması olarak da bilinir.
- Dijkstra’nın algoritması bir yinelemelidir ve algoritmanın kth yinelemesinden sonra en düşük maliyetli yolların k hedef düğüm için iyi bilinmesi özelliğine sahiptir.
Bazı gösterimleri açıklayalım:
- c (i, j): i düğümünden j düğümüne bağlantı maliyeti. İ ve j düğümleri doğrudan bağlantılı değilse, c (i, j) = ∞ olur.
- D (v): Kaynak koddan hedef v’ye, şu anda en düşük maliyetli olan yolun maliyetini tanımlar.
- P (v): Önceki düğümü (v’nin komşusu) kaynaktan v’ye mevcut en düşük maliyetli yolla birlikte tanımlar.
- N: Ağda bulunan toplam düğüm sayısıdır.
Algoritma
<strong>Başlatma</strong>
N = {A} // <strong>A bir kök düğümdür</strong> .
tüm düğümler için v,
eğer A'ya bitişik v ise
D (v) = c (A, v),
aksi takdirde D (v) = sonsuz <strong>döngü</strong>
D (w) minimum olacak şekilde w'nin N'de olmadığını bulun.
N'ye w ekleyin N'ye
değil w'ye bitişik tüm v'ler için D (v) güncelleyin:
D (v) = min (D (v), D (w) + c (w, v))
N'deki tüm düğümlere kadar