Uzaklık Vektörü Protokolleri

Önceki ölçümde haberin taşınması modellenmedi: duyan küme dışarıdan verildi ve duyan düğüm doğru tabloya bir anda vardı. Gerçekte bir düğümün komşusundan duyacağı şey topolojinin tamamı değildir; kimse komşusuna “ağ şöyle bağlı” diye bir harita göndermez.

En yalın protokol ailesi komşudan tek bir şey duyar: komşunun her hedefe kaç adım uzakta olduğunu. Bu ailenin adı uzaklık vektörü (distance vector) ailesidir ve bu dersin sorusu, bu tek sayının doğru tabloyu kurmaya yetip yetmediğidir.

Komşudan Duyulan Tek Şey

Bir düğüm komşularına bir liste gönderir: her hedef için bir yol maliyeti. Yol maliyeti burada adım sayısıdır. Liste komşunun kim olduğunu, hangi yoldan gidildiğini ya da ağın nasıl bağlı olduğunu söylemez — yalnız uzaklığı söyler.

# ogretilen dokum, calistirilmamistir

düğüm c, komşularına gönderdiği bildirim

  hedef   maliyet
  a             3
  b             1
  d             1
  e             2
  f             2
  g             3
  h             4

Bildirimi alan düğüm iki adım atar. Gelen her yol maliyetine bir ekler — komşuya ulaşmanın maliyeti bir adımdır. Sonra kendi tablosundaki yol maliyetiyle karşılaştırır ve daha küçük olanı alır; aldığında bir sonraki düğüm alanına o komşunun adını yazar.

Buradaki bilgi kısıtı ailenin tanımıdır. Düğüm c’nin bildirimini alan b, a’ya üç adımda gidildiğini öğrenir; hangi düğümlerden geçilerek gidildiğini öğrenmez. Bu, hesabı ucuzlatır: alınan bildirim topoloji değil, komşunun çoktan çiğnenmiş kararıdır. Düğüm kendi hesabını yapmaz, komşusunun hesabına bir ekler.

Yakınsama Burada Ne Demek

Kurs boyunca ölçülen şey yakınsamadır ve bu karşılık Sistem Tasarımına Giriş kursunda da kullanılmıştı. Orada yakınsayan şey kopya veri değerleriydi: aynı kaydın kopyaları bir süre farklı okunur, sonunda aynı değere varır ve gözlenen şey okunan değerdir. Burada yakınsayan şey veri değil yönlendirme tablosudur, gözlenen şey de okunan değer değil paketin kaderidir. Karşılık aynıdır, duyu ayrıdır; ikisi karıştırılmaz.

Yalnız İyileşmeyi Kabul Eden Kural

Kuralın ilk biçimi en yalınıdır: düğüm yalnız daha kısa bir yol duyduğunda tablosunu değiştirir. Gelen yol maliyeti elindekinden büyükse bildirimi atar. Bu kural sezgiseldir ve bir şeyi kesin olarak sağlar — tablo asla kötüleşmez.

Ölçümün ilk bölümü bu kuralı soğuk başlangıçtan izler: hiçbir düğümün elinde hiçbir şey yoktur, herkes yalnız kendi komşularını bilir ve tablolar turlarla dolar.

Ölçümün varsayımları:

• YL15 — Ağ, kâhin ve kırk çift önceki derslerdekiyle aynıdır. Birinci ve üçüncü bölümde kopan bağ yine halkayı kesen kiriştir.
• YL16 — Birinci bölümde başlangıç soğuktur: her düğümün kendine uzaklığı sıfır, ötekilere 99’dur ve hiçbir tablo satırı yoktur. Ölçülen şey sıfırdan kuruluş turudur.
• YL17 — Tur, bütün düğümlerin komşularından bildirim alıp tablolarını bir kez güncellemesidir; bildirimler eşzamanlı kabul edilir. Bir turun saniye karşılığı yoktur.
• YL18 — Yol maliyeti adım sayısıdır, her bağın maliyeti birdir. Yol maliyetinin tavanı 16’dır ve bu tavana varan girdi erişilemez sayılır; tavan sonsuzun sonlu karşılığıdır.
• YL19 — İkinci bölümde ölçülen kopma başkadır: d düğümüne giden iki bağ birden düşer ve d ağdan kopar. Geri kalan yedi düğüm birbirine bağlı kalır. Başlangıç bu bölümde soğuk değil, kopma öncesi gerçeğe yakınsamış tablodur.
• YL20 — Bekletme penceresi altı turdur ve yalnız bir girdi erişilemez hâle geldiğinde açılır; pencere boyunca o girdi için hiçbir bildirim kabul edilmez.
• YL21 — Kümenin çözünürlüğü kırk paket üzerinden 1/40 = 0,025’tir. İkinci bölümün penceresi on iki tur ve turda beş pakettir; oradaki küme altmış pakettir.

Ölçüm

"""Uzaklik vektoru: komsudan yalniz bir sayi duyulur.

Bolum 1 - soguk baslangic; dugum yalniz DAHA IYI bir yolu kabul eder.
Bolum 2 - kotu haber de kabul edilir; sonsuza sayma ve iki daraltma.
"""
TOHUM = 20260810
DUGUMLER = ["a", "b", "c", "d", "e", "f", "g", "h"]
BAGLAR = [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e"), ("e", "f"),
          ("f", "g"), ("g", "h"), ("h", "a"), ("b", "f")]
KOPUK = [b for b in BAGLAR if b != ("b", "f")]
YALITIK = [b for b in BAGLAR if b not in (("c", "d"), ("d", "e"))]
ATLAMA_SINIRI, SONSUZ, PENCERE = 12, 16, 12


def uretec(tohum):
    d = tohum % 2147483646 + 1

    def r(n):
        nonlocal d
        d = (d * 48271) % 2147483647
        return d % n
    return r


def komsuluk(baglar):
    k = {u: set() for u in DUGUMLER}
    for x, y in baglar:
        k[x].add(y)
        k[y].add(x)
    return k


def kahin(baglar):
    k, tablo = komsuluk(baglar), {}
    for kaynak in DUGUMLER:
        onceki, sira, gorulen = {}, [kaynak], {kaynak}
        while sira:
            yeni = []
            for u in sira:
                for v in sorted(k[u]):
                    if v not in gorulen:
                        gorulen.add(v)
                        onceki[v] = u
                        yeni.append(v)
            sira = yeni
        for hedef in DUGUMLER:
            if hedef == kaynak or hedef not in onceki:
                continue
            adim = hedef
            while onceki[adim] != kaynak:
                adim = onceki[adim]
            tablo[(kaynak, hedef)] = adim
    return tablo


def ilet(kaynak, hedef, tablolar, baglar):
    k, u, gecilen, atlama = komsuluk(baglar), kaynak, [], 0
    while u != hedef:
        if atlama >= ATLAMA_SINIRI:
            return "dongu", atlama
        sonraki = tablolar.get((u, hedef))
        if sonraki is None or sonraki not in k[u]:
            return "kara delik", atlama
        if (u, sonraki) in gecilen:
            return "dongu", atlama
        gecilen.append((u, sonraki))
        u, atlama = sonraki, atlama + 1
    return "ulasti", atlama


def ciftler(sayi=40, tohum=TOHUM):
    r, liste = uretec(tohum), []
    while len(liste) < sayi:
        x, y = DUGUMLER[r(8)], DUGUMLER[r(8)]
        if x != y:
            liste.append((x, y))
    return liste


def olc(tablolar, baglar, sayi=40):
    sayim = {"ulasti": 0, "dongu": 0, "kara delik": 0}
    for x, y in ciftler(sayi):
        sayim[ilet(x, y, tablolar, baglar)[0]] += 1
    return sayim


def yalniz_iyilesme(baglar, tur):
    """Komsunun uzaklik dizisi duyulur; yalniz daha kisa yol kabul edilir."""
    k = komsuluk(baglar)
    uzak = {(u, h): (0 if u == h else 99) for u in DUGUMLER for h in DUGUMLER}
    ilk = {}
    for _ in range(tur):
        yeni_uzak, yeni_ilk = dict(uzak), dict(ilk)
        for u in DUGUMLER:
            for v in sorted(k[u]):
                for h in DUGUMLER:
                    if uzak[(v, h)] + 1 < yeni_uzak[(u, h)]:
                        yeni_uzak[(u, h)] = uzak[(v, h)] + 1
                        yeni_ilk[(u, h)] = v
        uzak, ilk = yeni_uzak, yeni_ilk
    return uzak, ilk


def yeniden_hesap(baglar, tur, basla, geri_bildirmeme=False, bekletme=0):
    """Tablo her turda komsu bildirimlerinden yeniden kurulur; kotu haber de alinir."""
    k, izleme = komsuluk(baglar), []
    uzak, ilk = dict(basla[0]), dict(basla[1])
    donmus = {anahtar: 0 for anahtar in uzak}
    for _ in range(tur):
        yeni_uzak, yeni_ilk = dict(uzak), dict(ilk)
        for u in DUGUMLER:
            for h in DUGUMLER:
                if u == h or donmus[(u, h)] > 0:
                    continue
                en_iyi, secim = (1, h) if h in k[u] else (SONSUZ, None)
                for v in sorted(k[u]):
                    if geri_bildirmeme and ilk.get((v, h)) == u:
                        continue
                    maliyet = min(uzak[(v, h)] + 1, SONSUZ)
                    if maliyet < en_iyi:
                        en_iyi, secim = maliyet, v
                if en_iyi >= SONSUZ > uzak[(u, h)]:
                    donmus[(u, h)] = bekletme
                yeni_uzak[(u, h)], yeni_ilk[(u, h)] = en_iyi, secim
        for anahtar in donmus:
            donmus[anahtar] = max(0, donmus[anahtar] - 1)
        uzak, ilk = yeni_uzak, yeni_ilk
        izleme.append((dict(uzak), dict(ilk)))
    return izleme


dogru = kahin(KOPUK)
print("Bölüm 1 — soğuk başlangıç, yalnız daha kısa yol kabul edilir")
print(f"{'tur':>3s} {'ulaştı':>7s} {'döngü':>6s} {'kara delik':>11s} {'kâhinle aynı satır':>19s}")
for tur in range(6):
    ilk = yalniz_iyilesme(KOPUK, tur)[1]
    s = olc(ilk, KOPUK)
    esit = sum(1 for anahtar in dogru if ilk.get(anahtar) == dogru[anahtar])
    print(f"{tur:3d} {s['ulasti']:7d} {s['dongu']:6d} {s['kara delik']:11d}"
          f" {esit:16d}/{len(dogru)}")

basla = yalniz_iyilesme(BAGLAR, 8)
d_hedefli = [(x, y) for x, y in ciftler() if y == "d"]
print()
print(f"Bölüm 2 — d yalıtıldı, {PENCERE} turluk pencere, turda {len(d_hedefli)} paket")
print(f"{'daraltma':<28s} {'tavan turu':>10s} {'döngü':>6s} {'kara delik':>11s} "
      f"{'adım':>5s} {'tepe maliyet':>12s}")
for etiket, gb, bk in (("yok", False, 0), ("bekletme", False, 6),
                       ("geri bildirmeme", True, 0),
                       ("geri bildirmeme + bekletme", True, 6)):
    dongu = kara = adim = tepe = 0
    tavan = None
    for i, (uzak, ilk) in enumerate(yeniden_hesap(YALITIK, PENCERE, basla, gb, bk), 1):
        for x, y in d_hedefli:
            kader, a = ilet(x, y, ilk, YALITIK)
            dongu += kader == "dongu"
            kara += kader == "kara delik"
            adim += a
        tepe = max(tepe, max(uzak[(u, "d")] for u in DUGUMLER if u != "d"))
        if tavan is None and all(uzak[(u, "d")] >= SONSUZ for u in DUGUMLER if u != "d"):
            tavan = i
    print(f"{etiket:<28s} {tavan if tavan else '>' + str(PENCERE):>10} {dongu:6d} "
          f"{kara:11d} {adim:5d} {tepe:12d}")

print()
print("Bölüm 3 — kiriş koptu, her hedef erişilebilir kalıyor")
print(f"{'daraltma':<28s} {'yakınsama turu':>14s}")
for etiket, gb, bk in (("yok", False, 0), ("bekletme", False, 6),
                       ("geri bildirmeme", True, 0),
                       ("geri bildirmeme + bekletme", True, 6)):
    tur_sayisi = None
    for i, (uzak, ilk) in enumerate(yeniden_hesap(KOPUK, 20, basla, gb, bk), 1):
        if all(ilk.get(anahtar) == dogru[anahtar] for anahtar in dogru):
            tur_sayisi = i
            break
    print(f"{etiket:<28s} {tur_sayisi if tur_sayisi else '>20':>14}")

Bölüm 1 — soğuk başlangıç, yalnız daha kısa yol kabul edilir
tur  ulaştı  döngü  kara delik  kâhinle aynı satır
  0       0      0          40                0/56
  1       9      0          31               16/56
  2      20      0          20               32/56
  3      32      0           8               48/56
  4      40      0           0               56/56
  5      40      0           0               56/56

Bölüm 2 — d yalıtıldı, 12 turluk pencere, turda 5 paket
daraltma                     tavan turu  döngü  kara delik  adım tepe maliyet
yok                                 >12     60           0   202           13
bekletme                            >12     60           0   202           13
geri bildirmeme                     >12      5          55    59           16
geri bildirmeme + bekletme            6      5          55    41           16

Bölüm 3 — kiriş koptu, her hedef erişilebilir kalıyor
daraltma                     yakınsama turu
yok                                       2
bekletme                                  2
geri bildirmeme                           3
geri bildirmeme + bekletme                7

Dört Tur

Birinci bölüm ailenin temel sayısını veriyor. Soğuk başlangıçtan doğru tabloya dört turda varılıyor ve tur başına ulaşan paket 0, 9, 20, 32, 40 oluyor.

Sıfırıncı turda hiçbir paket ulaşmıyor: tablo boş olduğu için her paket ilk düğümde ölüyor, kırk kara delik. Uzaklık vektörü ağa hiçbir şey bilmeden başlar; komşusunun kim olduğunu bile tabloya yazmamıştır.

Sonraki turlarda kâhinle aynı olan satır sayısı 16, 32, 48, 56 diye ilerliyor: her tur tam on altı satır düzeliyor. Düzenlilik tesadüf değil, bildirimin doğasıdır. Bir turda bilgi tam olarak bir komşuluk adımı ilerler; birinci turda bir adımlık hedefler, ikinci turda iki adımlık hedefler doğru yazılır. Ağın çapı kaçsa yakınsama turu odur.

Ulaşan paket sayısının satır sayısından hızlı büyümemesi de anlamlıdır: bir paketin ulaşması için yol üzerindeki bütün satırların doğru olması gerekir. Otuz iki satır doğruyken bile sekiz paket ölür, çünkü o sekizinin yolunda henüz dolmamış bir satır vardır.

Kötü Haberi Öğrenmek

Birinci bölümün kuralı bir şeyi yapamaz: kötü haberi öğrenemez. Yalnız daha kısa yolu kabul eden bir düğüm, bir yolun uzadığını ya da yok olduğunu asla duyamaz — çünkü o haber tanımı gereği daha büyük bir yol maliyetiyle gelir ve kural onu atar.

Bu yüzden gerçek protokoller bir ödün verir: bir sonraki düğüm olarak seçilmiş komşudan gelen bildirim, kötü olsa bile kabul edilir. Ödün zorunludur; onsuz önceki dersteki statik rejimin körlüğü geri gelir.

Sonsuza sayma tam bu ödünden doğar. Bir hedef erişilemez olduğunda düğümler birbirinin eski yol maliyetini duyar, bir ekler ve yazar; komşusu da onunkini duyar, bir ekler ve yazar. Yol maliyeti turdan tura birer birer büyür ve tavana ulaşana kadar hiçbir düğüm hedefin gerçekten kaybolduğunu anlamaz. Bu davranışın adı **sonsuza sayma (count to infinity)**dır.

Sonsuza Sayma ve İki Daraltma

İkinci bölüm bu davranışı ölçüyor. d düğümü ağdan koptuğunda, daraltmasız kuralda tepe maliyet on iki turda ancak 13‘e çıkıyor — tavan olan 16’ya bile varamıyor. O pencerede d hedefli 60 paketin altmışı da döngüye giriyor ve 202 adım harcanıyor. Kara delik sayısı 0: hiçbir paket ölmüyor, hepsi dolaşıyor. Önceki derste kurulan okuma burada en saf hâliyle görünüyor — arıza kaybolan paket değil, dolan bağlardır.

Birinci daraltma geri bildirmeme (split horizon) adını taşır ve tek bir kuraldır: bir düğüm, bir hedefe giden yolu o yolun ilk adımı olan komşuya bildirmez. Gerekçe açıktır — o komşu zaten kendisi üzerinden gidiyordur, ona kendi yolunu geri satmak bir bilgi değil bir yankıdır. Ölçüm kazancı doğruluyor: döngü 60’tan 5’e, adım 202’den 59’a iniyor. Kara delik 55’e çıkıyor, yani paketlerin çoğu artık dolaşmak yerine hemen ölüyor.

Bu bir kayıp değildir. İki kaderde de paket hedefine varmaz, ama biri bir adımda ölür, öteki on iki adım ağ kaynağı harcar; adım sütunundaki düşüş bunu ölçüyor.

Geri bildirmeme yine de yetmiyor. tavan turu sütunu on iki turda hâlâ tamamlanmadığını söylüyor: iki düğümlü döngüleri kesiyor, ama halkanın kurduğu daha uzun döngüleri kesmiyor. Bir düğüm tavana varıyor, sonra henüz varmamış bir komşusundan eski bir yol maliyeti duyup geri iniyor.

İkinci daraltma bekletme (hold-down) budur: bir girdi erişilemez hâle geldiğinde düğüm o girdiyi bir pencere boyunca dondurur ve o hedef için hiçbir bildirimi kabul etmez. Pencere boyunca komşuların eski yol maliyetleri süzülüp gider. Ölçümde etkisi nettir: tavana varılan tur 6, adım 59’dan 41’e iniyor.

Ama bekletme tek başına hiçbir şey yapmıyor — ikinci satır daraltmasız satırla birebir aynı: 60 döngü, 202 adım. Sebep şudur: bekletme yalnız bir girdi erişilemez olduğunda açılır ve daraltmasız kuralda hiçbir girdi tavana varmadığı için pencere hiç açılmaz. Tetikleyicisi oluşmayan bir daraltma yoktur.

Üçüncü bölüm bedeli veriyor. Hedeflerin erişilebilir kaldığı sıradan bir kopmada daraltmasız kural 2 turda, geri bildirmeme 3 turda, ikisi birlikte 7 turda yakınsıyor. Bekletme burada iki kez zarar veriyor: geri bildirmeme geçici olarak bir girdiyi erişilemez gösteriyor, bekletme bu geçici bilgiyi doğru sanıp altı tur donduruyor. Kötü haberi hızlandıran her daraltma, iyi haberi yavaşlatır.

Özet

• Uzaklık vektörü ailesinde düğüm komşusundan yalnız bir yol maliyeti dizisi duyar; topolojiyi değil, komşusunun çoktan alınmış kararını öğrenir ve ona bir ekler.
• Soğuk başlangıçtan doğru tabloya dört turda varılır; tur başına ulaşan paket 0, 9, 20, 32, 40, doğru satır sayısı 0, 16, 32, 48, 56’dır — her tur bir komşuluk adımı ilerler.
• Yalnız daha kısa yolu kabul eden kural kötü haberi öğrenemez; bunu öğrenebilmek için verilen ödün sonsuza saymayı doğurur.
• Bir hedef erişilemez olduğunda daraltmasız kuralda on iki turluk pencerede 60 paketin altmışı da döngüye girer, 202 adım harcanır ve yol maliyeti tavana bile varamaz.
• Geri bildirmeme döngüyü 5’e, adımı 59’a indirir; bekletme eklendiğinde tavana 6. turda varılır ve adım 41’e iner, ama bekletme tek başına hiçbir şey yapmaz çünkü tetikleyicisi oluşmaz.
• Daraltmaların bedeli sıradan kopmada ödenir: yakınsama turu 2’den 3’e, ikisi birlikteyken 7’ye çıkar.

Sonraki Adım

Bütün bu kusurların tek bir kaynağı var: düğüm komşusunun kararını duyuyor, komşusunun gördüğünü değil. Yol maliyeti tek bir sayıya sıkıştığı için o sayının hangi yolu özetlediği kayboluyor; düğüm kendi adının o yolun içinde geçip geçmediğini bilemiyor ve daraltmalar bu bilgisizliği dışarıdan kapatmaya çalışıyor. Sonraki ders ödünü tersine çevirir: komşular birbirine karar değil ham bağ bilgisi gönderirse ve her düğüm en kısa yolu kendi hesaplarsa, kaç turda yakınsanır?