Bağlantı Durumu Protokolleri

Önceki dersin bütün kusurları tek bir yerden geliyordu: düğüm komşusunun kararını duyuyordu, komşusunun gördüğünü değil. Uzaklık dizisindeki bir sayı, komşunun kendi komşusundan duyduğu bir sayıya bir eklenerek üretilmişti; o sayının hangi yoldan geçtiği sıkıştırma sırasında kaybolmuştu.

Bağlantı durumu (link state) ailesi ödünü tersine çevirir. Komşuya gönderilen şey bir karar değil, ham bir olgudur: “şu bağ var ve ölçüsü şudur.” Olgu taşınırken değiştirilmez, özetlenmez, üzerine bir eklenmez. Her düğüm kendisine ulaşan olguları biriktirir ve en kısa yolu kendi hesaplar. Bu dersin sorusu, bu değiş tokuşun kaç tur kazandırdığı ve kazancın nereden geldiğidir.

Komşuya Gönderilen Şey

Uzaklık vektöründe bir düğüm sekiz satırlık bir ölçü dizisi gönderiyordu: her hedef için bir sayı. Bağlantı durumunda gönderilen şey çok daha küçüktür — düğüm yalnız kendi bağlarını bildirir.

# ogretilen dokum, calistirilmamistir

düğüm c'nin bildirimi

  bildiren   c
  komşu      b   ölçü 1
  komşu      d   ölçü 1

düğüm c'nin bildirimi, iki tur sonra elinde biriken veritabanı

  a–b   b–c   c–d   d–e   e–f   f–g   g–h   h–a

Fark bildirimin boyutunda değil, kimin adına konuştuğundadır. Uzaklık vektöründe c, h’ye dört adımda gidildiğini söylüyordu — bu c’nin kendi kararıydı ve h hakkında c’nin bilmediği bir şey içeriyordu. Bağlantı durumunda c yalnız kendi gördüğü iki bağı bildirir; h hakkında hiçbir şey söylemez, çünkü h hakkında hiçbir şey görmez.

Taşırma ve Topoloji Veritabanı

Bildirim komşuda durmaz. Alan düğüm onu kendi komşularına olduğu gibi iletir; Ağ Modelleri ve Protokoller kursunda kurulan taşırma düzeneğinin buradaki karşılığı budur. İletirken bildirimi değiştirmez, ölçüsüne bir eklemez, kendi adını yazmaz. Bildirim ağın içinde yayılırken aynı bildirim kalır.

Her düğüm gelen bildirimleri biriktirir. Biriken şeye topoloji veritabanı denir ve sonunda ağın bağ listesinden başka bir şey değildir. Veritabanı tamamlandığında düğümün elinde topolojinin kendisi vardır — kimsenin özetlemediği, kimsenin çiğnemediği hâliyle.

Bundan sonrası bir çizge hesabıdır. Düğüm kendisini kaynak alarak her hedefe giden en kısa yolu bulur ve yolun ilk adımını tablosuna yazar. Bu hesabın kendisi Algoritmalar müfredatındaki Çizge Algoritmaları kursunda kuruldu ve burada yeniden türetilmez; burada önemli olan hesabın nerede yapıldığıdır. Uzaklık vektöründe hesap dağıtıktı ve her düğüm komşusunun hesabının üstüne inşa ediyordu. Burada hesap yereldir: her düğüm aynı girdiden aynı sonucu bağımsız olarak çıkarır.

Bunun doğrudan bir sonucu vardır. Yanlış bir tablo artık yanlış bir hesaptan gelemez — hesap her yerde aynıdır. Yanlış tablo yalnız eksik girdiden gelir: veritabanı henüz dolmamıştır. Ölçüm bu eksikliği sayar.

Veritabanının Bedeli

Bu düzenek bedava değildir ve bedeli iki yerde toplanır.

Birincisi boyuttur. Uzaklık vektöründe bir düğümün tuttuğu şey hedef sayısı kadar satırdır; bağlantı durumunda tuttuğu şey ağın tamamıdır. Ölçülen ağda bu sekiz bağ demektir, ama bağ sayısı büyüdükçe her düğümün belleği ve her değişiklikte yaptığı hesap onunla büyür. Büyük ağların topolojiyi bölgelere ayırıp her bölgenin veritabanını kendi içinde tutmasının nedeni budur: hesabın girdisi küçültülür.

İkincisi tazeliktir. Bildirim değiştirilmeden taşındığı için, ağda dolaşan eski bir bildirim yeni bir bildirimle karışabilir ve bir düğüm geçmişteki bir bağı bugünkü sanabilir. Bu yüzden her bildirim bir sıra numarası ve bir yaş taşır; düğüm aynı bildirenin iki bildirimini gördüğünde büyük numaralıyı tutar, yaşı dolanı düşürür. Bu iki alan, kopyaların anlaşmazlığını protokolün kendi içinde çözen tek düzenektir.

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

• YL22 — Ağ, kâhin ve kırk çift önceki derslerdekiyle aynıdır; ölçülen kopma yine halkayı kesen kirişin kaybıdır ve iki aile aynı topolojide ölçülür.
• YL23 — Bağlantı durumu ailesinde düğümün başlangıç bilgisi kendi bağlarıdır. Bu bilgi bir komşudan duyulmaz, doğrudan gözlenir; bağın ucundaki cihaz kendi arayüzünü görür.
• YL24 — Tur, her düğümün elindeki bağ kümesini bütün komşularına iletmesi ve gelenleri kendi kümesine katmasıdır. Bildirim taşınırken değiştirilmez.
• YL25 — Düğüm elindeki bağ kümesinden en kısa yolu kâhinle aynı yordamla hesaplar. Yordam her düğümde aynıdır; farklı çıkan tek şey girdidir. Eksik girdiyle çıkan tablo yanlış olur, yordam değil.
• YL26 — Uzaklık vektörü tarafı önceki dersin soğuk başlangıçlı kuralıdır: düğüm komşusunun ölçü dizisini duyar ve yalnız daha kısa yolu alır.
• YL27 — Taşınan girdi sayımında uzaklık vektörü her komşuya sekiz hedeflik dizisini, bağlantı durumu bildiği bağ kümesini gönderir. Model her turda taşırma yapar; gerçek protokoller değişiklik olmadıkça taşırmaz, bu yüzden sayım yalnız yakınsama penceresi için anlamlıdır.
• YL28 — Kümenin çözünürlüğü kırk paket üzerinden 1/40 = 0,025’tir.

Ölçüm

"""Baglanti durumu: komsuya karar degil ham bag bilgisi gonderilir.

Bolum 1 - iki ailenin tur basina paket kaderi yan yana.
Bolum 2 - dogru satir, bilinen bag ve o tura dek tasinan girdi.
"""
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")]
ATLAMA_SINIRI = 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 uzaklik_vektoru(baglar, tur):
    """Komsudan ozetlenmis olcu duyulur; yalniz daha kisa yol alinir."""
    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 ilk


def baglanti_durumu(baglar, tur):
    """Ham bag bilgisi degistirilmeden tasinir; dugum kendi hesaplar."""
    k = komsuluk(baglar)
    bilinen = {u: {(u, v) for v in k[u]} for u in DUGUMLER}
    tasinan = 0
    for _ in range(tur):
        tasinan += sum(len(bilinen[u]) * len(k[u]) for u in DUGUMLER)
        yeni = {u: set(bilinen[u]) for u in DUGUMLER}
        for u in DUGUMLER:
            for v in k[u]:
                yeni[u] |= bilinen[v]
        bilinen = yeni
    tablolar = {}
    for u in DUGUMLER:
        yerel = kahin([tuple(sorted(b)) for b in bilinen[u]])
        for (x, h), adim in yerel.items():
            if x == u:
                tablolar[(u, h)] = adim
    return tablolar, bilinen, tasinan


dogru = kahin(KOPUK)
k_kopuk = komsuluk(KOPUK)
uv_tur_girdi = sum(len(DUGUMLER) * len(k_kopuk[u]) for u in DUGUMLER)
print(f"düğüm {len(DUGUMLER)} | kopma sonrası bağ {len(KOPUK)} | tablo satırı "
      f"{len(dogru)} | ölçülen paket {len(ciftler())}")
print()
print(f"{'tur':>3s} | {'uzaklık vektörü: ulaştı':>23s} {'döngü':>6s} {'k.delik':>8s}"
      f" | {'bağlantı durumu: ulaştı':>23s} {'döngü':>6s} {'k.delik':>8s}")
for tur in range(6):
    uv = olc(uzaklik_vektoru(KOPUK, tur), KOPUK)
    bd = olc(baglanti_durumu(KOPUK, tur)[0], KOPUK)
    print(f"{tur:3d} | {uv['ulasti']:23d} {uv['dongu']:6d} {uv['kara delik']:8d}"
          f" | {bd['ulasti']:23d} {bd['dongu']:6d} {bd['kara delik']:8d}")

print()
print(f"{'tur':>3s} {'UV doğru satır':>14s} {'BD doğru satır':>14s} "
      f"{'BD bilinen bağ':>14s} {'BD taşınan':>11s} {'UV taşınan':>11s}")
for tur in range(6):
    uv = uzaklik_vektoru(KOPUK, tur)
    bd, bilinen, tasinan = baglanti_durumu(KOPUK, tur)
    bag = {len({tuple(sorted(b)) for b in bilinen[u]}) for u in DUGUMLER}
    print(f"{tur:3d} {sum(1 for a in dogru if uv.get(a) == dogru[a]):11d}/56"
          f" {sum(1 for a in dogru if bd.get(a) == dogru[a]):11d}/56"
          f" {min(bag):8d}/{len(KOPUK):<5d} {tasinan:11d} {uv_tur_girdi * tur:11d}")

düğüm 8 | kopma sonrası bağ 8 | tablo satırı 56 | ölçülen paket 40

tur | uzaklık vektörü: ulaştı  döngü  k.delik | bağlantı durumu: ulaştı  döngü  k.delik
  0 |                       0      0       40 |                       9      0       31
  1 |                       9      0       31 |                      20      0       20
  2 |                      20      0       20 |                      32      0        8
  3 |                      32      0        8 |                      40      0        0
  4 |                      40      0        0 |                      40      0        0
  5 |                      40      0        0 |                      40      0        0

tur UV doğru satır BD doğru satır BD bilinen bağ  BD taşınan  UV taşınan
  0           0/56          16/56        2/8               0           0
  1          16/56          32/56        4/8              32         128
  2          32/56          48/56        6/8             128         256
  3          48/56          56/56        8/8             288         384
  4          56/56          56/56        8/8             512         512
  5          56/56          56/56        8/8             768         640

Her Turda Önde

Üst tablo iki aileyi aynı kopmada, aynı kırk paketle yan yana koyuyor. Bağlantı durumu doğru tabloya üç turda varıyor, uzaklık vektörü dört turda. Ve fark yalnız bitiş noktasında değil: bağlantı durumu her turda öndedir. Sıfırıncı turda 9’a karşı 0, birinci turda 20’ye karşı 9, ikinci turda 32’ye karşı 20.

Sıfırıncı tur en çok şey söyleyen satırdır. Hiçbir bildirim henüz gönderilmemiştir ve bağlantı durumu yine de 9 paketi ulaştırır. Sebep varsayım YL23’tür: düğümün kendi bağları bir komşudan duyulmaz, doğrudan görülür. Bağın ucundaki cihaz o bağın var olduğunu protokolsüz bilir. Uzaklık vektöründe bu bilgi de bir turluk bildirim bekler, çünkü orada tabloya yazılan şey duyulan bir ölçüdür.

Döngü sütunu her iki ailede de baştan sona 0’dır. Bu bir tesadüf değil, soğuk başlangıcın sonucudur: iki kural da yalnız daha kısa yolu kabul ediyor ve hiçbir tablo satırı yanlış bir komşuyu göstermiyor — henüz hiçbir şey göstermiyor. Yanlış yön için önce bir yön yazılmış olması gerekir; boş satır kara delik üretir, döngü üretmez.

Fark Nerede

Alt tablo kazancın kaynağını arıyor ve ilk bakışta beklenen yanıtı vermiyor.

Doğru satır sütunları her iki ailede de turda tam on altı satır ilerliyor: uzaklık vektörü 0, 16, 32, 48, 56; bağlantı durumu 16, 32, 48, 56. Artış hızı aynı. İki aile de turda bir komşuluk adımı ilerliyor, çünkü bilgi ikisinde de bir turda bir bağ geçiyor. Ne bağlantı durumu daha hızlı yayılıyor, ne uzaklık vektörü daha yavaş.

İki dizi arasındaki tek fark başlangıç noktasıdır. Bağlantı durumunun dizisi uzaklık vektörünün dizisinin bir tur kaydırılmış hâlidir. Kazanılan tur, kazanılan hız değil, kazanılan baştır.

Taşınan girdi sütunları da beklenenin tersini söylüyor. Bağlantı durumu kendi yakınsama turunda (üçüncü tur) 288 girdi taşımış; uzaklık vektörü kendi yakınsama turunda (dördüncü tur) 384. Yani daha erken yakınsayan aile daha az bilgi taşımış. Bilinen bağ sütunu bunu doğruluyor: bağlantı durumu düğümünün taşıdığı en büyük yük sekiz bağdır ve orada durur, çünkü ağın tamamı sekiz bağdır. Uzaklık vektörü ise her turda her komşuya sekiz hedeflik dizisini yeniden gönderir ve bu yük hiç azalmaz.

Dördüncü okuma buradan çıkar: fark bilgi miktarında değil, bilginin ne kadar uzaktan taşındığındadır. Uzaklık vektöründe bir düğümün h hakkında bildiği sayı, h’den başlayıp aradaki her düğümde yeniden hesaplanarak gelmiştir; her durakta bir toplama yapılmış ve o duraktan öncesi silinmiştir. Bağlantı durumunda h’nin bağları, h’nin ağzından çıktığı biçimde gelir; aradaki düğümler taşıyıcıdır, yorumcu değil. Yorumlanmayan bilgi, taşındığı mesafeden bağımsız olarak aynı bilgidir.

Beşinci tur satırı da dürüstlük gerektiriyor. Orada bağlantı durumunun taşıdığı girdi 768‘e çıkıp uzaklık vektörünü geçiyor. Bu, YL27’de yazılan model kısıtının sonucudur: ölçüm her turda taşırma yapıyor. Gerçek protokoller yakınsadıktan sonra bir değişiklik olmadıkça taşırmaz; sayım bu yüzden yalnız yakınsama penceresi için okunur.

İki Ailenin Ortak Vardığı Yer

Bütün bu farklara karşın iki aile aynı yere varıyor. Dördüncü turdan sonra her iki sütun da 56/56 doğru satır ve 40/40 ulaşan paket veriyor. Tablolar yalnız eşit derecede doğru değil, birbirinin aynısı: ikisi de kâhinin tablosudur.

Bunun nedeni yapısaldır. İki aile de aynı şeyi arıyor — en kısa yolu. Uzaklık vektörü onu komşularının ölçülerini toplayarak, bağlantı durumu topolojiyi kurup kendi hesaplayarak buluyor; ama aranan ölçüt tek. Ölçütü tek olan bir aramanın sonucu da tektir, ve bu yüzden iki ailenin ayrıldığı yer sonuç değil, sonuca varış süresi ve o süredeki paketin kaderidir.

Özet

• Bağlantı durumu ailesinde komşuya karar değil ham bağ bilgisi gönderilir; bildirim taşınırken değiştirilmez ve her düğüm en kısa yolu kendi hesaplar.
• Yanlış tablo yanlış hesaptan gelemez, çünkü hesap her düğümde aynıdır; yanlış tablo yalnız eksik girdiden gelir.
• Doğru tabloya üç turda varılır ve her turda uzaklık vektörünün önündedir: ulaşan paket 9, 20, 32, 40’a karşı 0, 9, 20, 32. Sıfırıncı turdaki 9 paket, düğümün kendi bağlarını protokolsüz bilmesinden gelir.
• Doğru satır artışı iki ailede de turda on altıdır; bağlantı durumunun dizisi uzaklık vektörünün bir tur kaydırılmış hâlidir. Kazanılan şey hız değil baştır.
• Yakınsama turunda taşınan girdi bağlantı durumunda 288, uzaklık vektöründe 384: erken yakınsayan aile daha az bilgi taşır. Fark bilgi miktarında değil, bilginin ne kadar uzaktan yorumlanmadan taşındığındadır.
• İki aile de dördüncü turdan sonra 56/56 doğru satıra ve 40/40 ulaşan pakete varır; tablolar birbirinin aynısıdır, çünkü ikisi de aynı ölçütü arar.

Sonraki Adım

Son bölümün bulgusu şudur: iki aile de en kısa yolu arıyordu ve ikisi de sonunda aynı tabloya vardı. Ölçüt tek olduğu için sonuç da tekti; aralarındaki bütün fark o sonuca varana kadar geçen turlara sıkışmıştı. Bu, ölçütün kendisinin hiç tartışılmadığı anlamına gelir — kısalık, sorgulanmadan iyi sayıldı. Oysa bir yol yalnız uzunluğuyla değerlendirilmez: kimin ağından geçtiği, kimin hattını doldurduğu ve kime ne kadara mal olduğu da yolun nitelikleridir. Sonraki ders şunu sorar: ya en kısa yol istenmiyorsa — tablo neye göre kurulur ve uzayan yol bir kusur mudur?