Yönlendirme algoritmaları: Dijkstra ve Bellman-Ford

Bir önceki haftada router’ın iletim tablosuna bakıp paketi ilettiğini gördük. Peki o tabloyu kim dolduruyor? Yönlendirme algoritmaları (routing algorithms). Bu, ağ katmanının kontrol düzlemi (control plane): ağı bir çizge (graph) gibi görüp her hedefe en düşük maliyetli yolu (least-cost path) bulmak. Sınavda iki tablo doldurma sorusu çıkar: Dijkstra tablosu ve distance-vector güncellemesi. Altın kurallar:

1. Dijkstra her adımda N’ dışındaki en küçük mesafeli düğümü ekler. Komşu olup olmadığı önemsiz.
2. Eklenen düğümün komşularını güncelle: $D(v) = \min(D(v),\ D(w) + c(w,v))$.
3. İletim tablosu sadece ilk atlamayı (next hop) tutar.
4. Bellman-Ford: $D_x(y) = \min_v \{c(x,v) + D_v(y)\}$, $v$ komşular.
5. DV’de kötü haber yavaş yayılır (count-to-infinity).

Ağ çizge olarak

Router’lar düğüm, bağlantılar kenar. Her kenarın bir maliyeti (cost) var: gecikme, ters bant genişliği ya da yönetici kararı. Bir yolun maliyeti kenar maliyetlerinin toplamıdır.

Link-state: Dijkstra algoritması

Her router bağlantı durumlarını (link-state packets) bütün ağa yayar. Herkes aynı haritaya sahip olur ve Dijkstra’yı kendisi koşar.

Gösterim: $D(v)$ kaynaktan $v$‘ye şu ana kadar bilinen en düşük maliyet, $p(v)$ o yoldaki öncül düğüm, $N'$ kesinleşmiş düğümler.

Başla: N' = {kaynak}; her v için D(v) = c(kaynak,v) (komşu değilse sonsuz)
Döngü: N' dışındaki en küçük D(w)'yi seç, N'ye ekle
       w'nin N' dışındaki her komşusu v için:
           D(v) = min( D(v), D(w) + c(w,v) )
Bitiş: bütün düğümler N' içinde

Örnek: kaynak A. Kenarlar:

A-B 4   A-C 1   B-C 2   B-D 5   C-D 8
C-E 10  D-E 2   D-F 6   E-F 3

Tabloda her hücre D,p biçiminde. * o düğümün kesinleştiğini gösterir.

adım  N'       B      C      D      E      F
0     A        4,A    1,A    inf    inf    inf
1     AC       3,C    *      9,C    11,C   inf
2     ACB      *      *      8,B    11,C   inf
3     ACBD     *      *      *      10,D   14,D
4     ACBDE    *      *      *      *      13,E
5     ACBDEF   *      *      *      *      *

Adım 1’de C (1) eklendi: B için $1 + 2 = 3 < 4$, öncül C oldu. Adım 2’de B (3) eklendi: D için $3 + 5 = 8 < 9$. Adım 3’te D (8): E için $8 + 2 = 10 < 11$. Adım 4’te E (10): F için $10 + 3 = 13 < 14$.

Sonuç ve A’nın iletim tablosu:

TUZAK · doğrudan bağlantı her zaman en kısa değil. A-B doğrudan 4, ama A-C-B 3. Tabloyu doldururken ilk satırdaki değerleri “kesin” sanma; düğüm ancak N’ye eklendiğinde kesinleşir.

İPUCU · next hop’u bulmak. Öncül zincirini geri izle: F’nin öncülü E, E’nin D, D’nin B, B’nin C, C’nin A. Kaynağa varmadan önceki son düğüm (C) next hop’tur.

Karmaşıklık. n düğüm için n - 1 tur, her turda en küçüğü bulmak için tarama: $O(n^2)$. Salınım (oscillation): maliyet trafik yüküne bağlıysa herkes aynı anda ucuz yola geçer, o yol pahalanır, herkes geri döner. Çözüm: router’ların hesap zamanlarını rastgele kaydırmak.

İPUCU · sınavda tabloyu hızlı doldurmak. Her satırda üç iş yap: (1) N’ dışındaki en küçük değeri daire içine al, (2) o düğümü N’ kümesine yaz, (3) sadece onun komşularının hücrelerini güncelle, diğer hücreleri aynen kopyala. Eşitlik olursa hangisini seçtiğin sonucu değiştirmez, ama tutarlı ol (genelde alfabetik). Değişmeyen hücreyi yeniden hesaplamaya çalışmak zaman kaybıdır.

Mesaj karmaşıklığı. LS’de her router kendi bağlantı durumunu bütün ağa yayar; n router ve E bağlantı için $O(nE)$ mesaj. DV’de mesajlar sadece komşular arasında gider, ama yakınsama süresi değişkendir ve döngüler oluşabilir. Sağlamlık açısından LS daha iyidir: her router kendi hesabını yaptığı için bir router’ın hatası sınırlı kalır.

Distance-vector: Bellman-Ford

Her router sadece mesafe vektörünü (distance vector) tutar: her hedefe tahmini maliyet. Komşularından vektör alınca kendi vektörünü Bellman-Ford denklemiyle yeniler:

$D_x(y) = \min_{v \in \text{komşular}(x)} \{\, c(x,v) + D_v(y) \,\}$

Vektör değiştiyse komşulara yollar. Değişmezse susar. Bu yüzden algoritma yinelemeli, asenkron ve dağıtıktır.

Örnek: dört düğüm, senkron turlar. Kenarlar: W-X 1, X-Y 3, W-Y 6, Y-Z 2, X-Z 9. Satırlar düğümün vektörü, sütunlar hedef W X Y Z.

t=0 (sadece doğrudan bağlantılar)
  D_W   0  1  6  inf
  D_X   1  0  3  9
  D_Y   6  3  0  2
  D_Z   inf 9 2  0
t=1
  D_W   0  1  4  8       Y: min(6, 1+3)=4   Z: min(inf, 1+9, 6+2)=8
  D_X   1  0  3  5       Z: min(9, 3+2)=5
  D_Y   4  3  0  2
  D_Z   8  5  2  0
t=2
  D_W   0  1  4  6       Z: min(1+5, 6+2)=6   (X'in yeni vektörü)
  D_X   1  0  3  5
  D_Y   4  3  0  2
  D_Z   6  5  2  0
t=3: hiçbir vektör değişmedi, yakınsadı

W’nin Z’ye en iyi yolu W-X-Y-Z, maliyet $1 + 3 + 2 = 6$. Bu bilgi iki turda geldi, çünkü üç atlamalık bir yol.

Count-to-infinity ve poisoned reverse

Maliyet düşerse haber hızla yayılır. Artarsa sorun çıkar. Örnek: A-B 2, B-C 1, A-C 30. Yakınsamış durumda $D_B(A) = 2$, $D_C(A) = 3$ (C, A’ya B üzerinden gidiyor). Şimdi A-B maliyeti 40 oldu.

B: min(40, 1 + D_C(A)=3) = 4     B, C'nin yolunun kendisinden geçtiğini bilmiyor
C: min(30, 1 + 4) = 5
B: min(40, 1 + 5) = 6
C: 7, B: 8, ...                  her turda 2 artış
...
B: 30, C: min(30, 31) = 30       C sonunda doğrudan bağlantıya geçti
B: min(40, 1 + 30) = 31          kararlı

Kararlı duruma 15 turda ulaşıldı (her turda önce B, sonra C güncelliyor). Bu sürenin neredeyse tamamında B ile C birbirini gösteren bir döngüdeydi. A-C bağlantısı olmasaydı sayılar sonsuza kadar tırmanırdı; adı oradan geliyor.

Poisoned reverse: C’nin A’ya yolu B’den geçiyorsa C, B’ye $D_C(A) = \infty$ der. B hemen $\min(40, 1 + \infty) = 40$ alır ve döngü oluşmaz. Ancak üç ya da daha çok düğümlü döngülerde bu hile yetmez. RIP bu yüzden sonsuzu 16 hop olarak tanımlar.

Hiyerarşik yönlendirme

Gerçek İnternette yüz milyonlarca router var; hepsi tek bir Dijkstra çalıştıramaz. Ayrıca her kurum kendi ağını kendi yönetmek ister. Çözüm: özerk sistemler (autonomous systems, AS). AS içinde intra-AS protokolü (OSPF, RIP), AS’ler arasında inter-AS protokolü (BGP) çalışır. Bunu bir sonraki sayfada işliyoruz.

Sık yapılan hatalar

S-T 3   S-U 7   T-U 2   T-V 6
U-V 1   U-W 8   V-W 2

P-Q 2   P-R 7   Q-R 1   R-T 3   Q-T 8