Statik ve Dinamik Yönlendirme

Önceki ölçümde iki tablo kuşağı vardı ve ikincisi hazır verildi: kopmadan sonraki gerçek hesaplandı, tablolara yazıldı ve paketler öyle yürütüldü. Aradaki geçişi kimse yapmadı.

Gerçek bir ağda o geçişi birinin yapması gerekir ve yalnız iki yol vardır. Ya satırları bir yönetici elle yazar — buna statik yönlendirme denir — ya da cihazlar bağlarının durumunu birbirine anlatır ve tablolarını kendileri kurar; buna dinamik yönlendirme denir. Bu dersin sorusu hangisinin daha iyi olduğu değildir. Soru şudur: kopma olduğunda kaç tur sonra doğru tabloya varılır, ve varılmıyorsa kayıp zamanla ne yapar?

Yazmak ve Anlatmak

Statik yönlendirmede tablo bir yapılandırma metnidir. Yönetici her düğüm için her hedefin bir sonraki düğümünü yazar; cihaz bu satırları okur ve hiç sorgulamaz. Satırın doğru olup olmadığını denetleyen bir düzenek yoktur, çünkü cihazın karşılaştırabileceği ikinci bir kaynak yoktur.

# ogretilen dokum, calistirilmamistir

düğüm b için elle yazılmış satırlar

  hedef   bir sonraki düğüm
  a       a
  c       c
  d       c
  e       f
  f       f
  g       f
  h       a

Sekiz düğümlü ağda her düğüm için yedi satır yazılır ve e, f, g satırları kirişten geçer. Kiriş koptuğunda bu metin değişmez — dosyada yazan neyse cihaz onu okumaya devam eder.

Dinamik yönlendirmede tablo bir yapılandırma değil, bir anlaşmanın çıktısıdır. Cihazlar düzenli aralıklarla komşularına bildirimde bulunur, gelen bildirimlerden kendi satırlarını üretir ve bir bağ düştüğünde bunu komşularına söyler. Yöneticinin yazdığı şey satırlar değil, protokolün hangi bağlarda konuşacağıdır.

İki rejimin maliyeti farklı yerlere düşer. Statik rejimde maliyet yazma anındadır: sekiz düğümlü bir ağda her düğümün yedi hedefi vardır, toplam elli altı satır. Düğüm sayısı $n$ ise satır sayısı $n(n-1)$ ile büyür — otuz düğümde sekiz yüz yetmiş satır. Dinamik rejimde maliyet çalışma anındadır: cihazlar bildirim gönderir, gelen bildirimleri işler ve yakınsama boyunca tablolar bir süre yanlış kalır.

Yazma maliyetinin bir kısmı önceki dersteki varsayılan yolla kısaltılabilir. Bir düğüm komşularından biri dışındaki her hedefi tek bir boş önek satırına yığabilir; o zaman elle yazılan satır sayısı yediden ikiye iner. Ölçümde bu kısaltma kullanılmaz, çünkü ölçülen şey yazma emeği değil kararın doğruluğudur: varsayılan yol satır sayısını azaltır, kopmayı duyma yeteneğini değiştirmez. Kısaltılmış bir tablo da kopan bağı gösteriyorsa paketi yine oraya gönderir.

Statik Tablonun Kör Noktası

Statik bir tablo bir bağın koptuğunu hiçbir zaman öğrenmez. Bu bir gecikme değil, bir yokluktur: haberin ulaşacağı bir kanal tanımlanmamıştır. Cihaz kendi bağının düştüğünü görebilir, ama iki adım ötedeki bir bağın düştüğünü göremez ve satırı o bağı gösteriyorsa paketi oraya göndermeye devam eder.

Bunun ölçüme yansıyan sonucu şudur: statik rejimde kara delik sayısı zamanın işlevi değildir. Birinci turda kaç paket ölüyorsa yüzüncü turda da o kadarı ölür. Kayıp durmaz, birikir. Durması için ölçümün dışından bir olay gerekir: bir yöneticinin arızayı fark edip satırları yeniden yazması.

Dinamik rejimde ise haberin bir kanalı vardır. Kopan bağın iki ucu bunu doğrudan görür, komşularına söyler, onlar kendi komşularına söyler. Haber ağda bir dalga gibi yayılır ve her tur bir komşuluk adımı ilerler. Aşağıdaki ölçüm tam olarak bu dalgayı modeller.

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

• YL8 — Ağ, kâhin ve kırk çift önceki derstekiyle aynıdır: sekiz düğüm, dokuz bağ, halkayı kesen kiriş. Ölçülen kopma yine o kirişin kaybıdır.
• YL9 — Statik rejimde tablo ölçüm boyunca hiç değişmez. Yöneticinin arızayı fark edip müdahale etmesi ölçümün dışındadır; ölçülen şey müdahaleye kadar geçen süredir.
• YL10 — Dinamik rejimde haber kopan bağın iki ucundan başlar ve her turda bir komşuluk adımı ilerler. Haberi duyan düğüm tablosunu doğru hâline getirir; duymayan düğüm eski tablosunu olduğu gibi sürdürür.
• YL11 — Tur, bir düğümün komşularından bildirim alıp tablosunu güncellemesidir. Tur bir saat birimi değildir; karşılığı protokolün bildirim aralığıdır ve saniye cinsinden değişir.
• YL12 — Aynı kırk çift her turda yeniden yürütülür ve ölçüm turlar arasında bellek tutmaz; her tur o turun tablolarıyla bağımsız ölçülür.
• YL13 — Atlama sınırı 12’dir; sınırı yakan paket döngü sayılır.
• YL14 — Kümenin çözünürlüğü kırk paket üzerinden 1/40 = 0,025’tir; bundan küçük bir fark iddia edilmez.

Ölçüm

"""Statik ve dinamik: kopmayi duymayan tablo ile duyan tablo.

Statik rejimde tablo hic degismez. Dinamik rejimde haber kopan bagin
iki ucundan baslar ve her turda bir komsuluk adimi ilerler.
"""
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):
    """Her dugum icin her hedefe giden en kisa yolun ilk adimi."""
    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, adim = {"ulasti": 0, "dongu": 0, "kara delik": 0}, 0
    for x, y in ciftler(sayi):
        kader, a = ilet(x, y, tablolar, baglar)
        sayim[kader] += 1
        adim += a
    return sayim, adim


def kismi(eski, yeni, duyan):
    """Kopmayi yalniz duyanlar guncelledi; otekiler eski tablosunu surduruyor."""
    return {(u, h): (yeni if u in duyan else eski)[(u, h)] for (u, h) in eski}


def duyanlar(tur, baglar=KOPUK, kaynak=("b", "f")):
    """Haber kopan bagin uclarindan baslar, turda bir komsuluk adimi ilerler."""
    if tur <= 0:
        return set()
    k, kume, sinir = komsuluk(baglar), set(kaynak), set(kaynak)
    for _ in range(tur - 1):
        sinir = {v for u in sinir for v in k[u]} - kume
        kume |= sinir
    return kume


eski, yeni = kahin(BAGLAR), kahin(KOPUK)
degisen = [(u, h) for (u, h) in eski if eski[(u, h)] != yeni[(u, h)]]
print(f"tablo satırı {len(eski)} | kopmadan sonra elle düzeltilecek satır "
      f"{len(degisen)} | dokunulacak düğüm {len({u for u, _ in degisen})}")
print()
print(f"{'tur':>3s} {'duyan':>5s} | {'statik: ulaştı':>14s} {'döngü':>5s} {'k.delik':>7s}"
      f" {'adım':>4s} | {'dinamik: ulaştı':>15s} {'döngü':>5s} {'k.delik':>7s} {'adım':>4s}")
statik_kayip = dinamik_kayip = 0
for tur in range(6):
    s, sa = olc(eski, KOPUK)
    kume = duyanlar(tur)
    d, da = olc(kismi(eski, yeni, kume), KOPUK)
    statik_kayip += s["dongu"] + s["kara delik"]
    dinamik_kayip += d["dongu"] + d["kara delik"]
    print(f"{tur:3d} {len(kume):5d} | {s['ulasti']:14d} {s['dongu']:5d} "
          f"{s['kara delik']:7d} {sa:4d} | {d['ulasti']:15d} {d['dongu']:5d} "
          f"{d['kara delik']:7d} {da:4d}")
print(f"altı turda hedefine varmayan paket: statik {statik_kayip}, "
      f"dinamik {dinamik_kayip}")

print()
print(f"{'duyan küme':<22s} {'ulaştı':>7s} {'döngü':>6s} {'kara delik':>11s} "
      f"{'adım':>5s} {'tablosu doğruyken ölen':>23s}")
for ad, kume in (("kimse", set()),
                 ("yalnız b ve f", {"b", "f"}),
                 ("b, f ve komşuları", duyanlar(2)),
                 ("d dışında herkes", set(DUGUMLER) - {"d"}),
                 ("herkes", set(DUGUMLER))):
    tab = kismi(eski, yeni, kume)
    s, a = olc(tab, KOPUK)
    dogruyken = sum(1 for x, y in ciftler()
                    if ilet(x, y, tab, KOPUK)[0] != "ulasti" and x in kume)
    print(f"{ad:<22s} {s['ulasti']:7d} {s['dongu']:6d} {s['kara delik']:11d} "
          f"{a:5d} {dogruyken:23d}")

tablo satırı 56 | kopmadan sonra elle düzeltilecek satır 11 | dokunulacak düğüm 6

tur duyan | statik: ulaştı döngü k.delik adım | dinamik: ulaştı döngü k.delik adım
  0     0 |             26     0      14   61 |              26     0      14   61
  1     2 |             26     0      14   61 |              34     6       0   94
  2     6 |             26     0      14   61 |              40     0       0   99
  3     8 |             26     0      14   61 |              40     0       0   99
  4     8 |             26     0      14   61 |              40     0       0   99
  5     8 |             26     0      14   61 |              40     0       0   99
altı turda hedefine varmayan paket: statik 84, dinamik 20

duyan küme              ulaştı  döngü  kara delik  adım  tablosu doğruyken ölen
kimse                       26      0          14    61                       0
yalnız b ve f               34      6           0    94                       1
b, f ve komşuları           40      0           0    99                       0
d dışında herkes            40      0           0    99                       0
herkes                      40      0           0    99                       0

Düz Çizgi ile İnen Çizgi

Statik sütunu altı turun altısında da aynıdır: 26 ulaştı, 14 kara delik, 61 adım. Bu sabitlik ölçümün en önemli bulgusudur. Kayıp azalmıyor çünkü azalmasını sağlayacak bir olay yok; tablo kopmayı duymadı, duyacağı bir kanal da yok. Altı turda hedefine varmayan paket 84’e ulaşıyor ve bu sayı turla doğrusal büyümeye devam eder.

Dinamik sütunu iki turda kapanıyor: ikinci turda ulaşan 40’a çıkıyor ve orada kalıyor. Altı turdaki toplam kayıp 20. Aynı kopma, aynı topoloji, aynı kırk paket — fark yalnız haberin bir kanalı olup olmamasıdır.

Elle düzeltme maliyeti üst satırda duruyor. Elli altı satırın 11’i yanlış hâle geliyor ve bu on bir satır 6 ayrı düğüme dağılmış. Yönetici bir bağın koptuğunu öğrense bile düzeltmesi gereken şey tek bir satır değildir; altı cihaza dokunması, her birinde hangi satırların değişmesi gerektiğini yeniden hesaplaması gerekir. Sekiz düğümlük bir ağda bu iş bir oturumdur, otuz düğümlük bir ağda başka bir şeydir.

Kısmî Bilginin Bedeli

Alt tablo dinamik rejimin içine bakıyor ve orada beklenmedik bir şey var.

Kimse duymadığında 14 paket kara deliğe düşüyor, toplam 61 adım harcanıyor. Kopmayı yalnız b ve f duyduğunda kara delik sıfıra iniyor — ilk bakışta düzelme. Ama ulaşan sayısı 40 değil 34; kalan 6 paket döngüye giriyor ve toplam adım 61’den 94’e çıkıyor.

Bu satır kursun ikinci iddiasını ödüyor: kısmî bilgi, hiç bilgiden daha pahalı bir arıza üretir. Gerekçe kaderlerin doğasındadır. Kara deliğe düşen paket hemen ölür: bir düğüme varır, orada karşılığı olmayan bir komşu görülür ve paket atılır. Harcadığı kaynak yolun o noktasına kadar attığı adımlardır. Döngüye giren paket ise ölmez; atlama sınırını yakana kadar ağda dolaşır, her turda bağ kapasitesi ve işleme kapasitesi tüketir.

Ölçüm bunu adım sayısıyla söylüyor. Kayıp paket sayısı 14’ten 6’ya, yani yarıdan fazla inerken harcanan adım 61’den 94’e çıkıyor. Az sayıda paket, çok sayıda adım. Arızanın görünümü de değişiyor: kara delik bir kayıp gibi görünür ve bulunması görece kolaydır; döngü tıkanıklık gibi görünür, çünkü bağlar doludur ve paketler akmaktadır — yalnızca hiçbiri varmamaktadır.

Sağdaki son sütun bunun neden kaçınılmaz olduğunu söylüyor. yalnız b ve f satırında tablosu doğru olan bir düğümden çıkıp ölen 1 paket var. O düğüm kopmayı duymuştur, satırı gerçeğe uygundur, kararı kusursuzdur — ve paketi yine de kaybeder, çünkü paketi verdiği komşu duymamıştır. Buradan yapısal bir sonuç çıkar: hiçbir cihaz tek başına bir paketi döngüye sokamaz. İki tablonun paketi birbirine geri gönderdiği bu duruma yönlendirme döngüsü (routing loop) denir; ölçümdeki kader adı kısaca döngüdür. Bir cihazın kararının doğruluğu kendi tablosuna değil, komşusununkine bağlıdır.

Son iki satır bir başka şeyi gösteriyor. d dışında herkes duyduğunda sonuç 40/40 — hiç duymayan bir düğüm kaldığı hâlde. Sebep, ölçülen kırk çiftin hiçbirinin d’nin değişen satırlarına uğramaması. Kısmî bilgi her zaman arıza üretmez; arıza, eksik kalan bilginin paketin yoluna düşmesiyle doğar.

Ölçütle Seçim

İki rejim arasındaki seçim bu ölçümden okunabilir bir ölçüte dayanır ve ölçüt “hangisi daha gelişkin” değildir.

Statik yönlendirme, hedefe giden yol tekse doğru seçimdir. Tek çıkışı olan bir uç ağda alternatif yol yoktur; bir dinamik protokol koşsa bile keşfedeceği ikinci bir yol bulunmadığından kopma anında yapabileceği hiçbir şey yoktur. Böyle bir yerde protokolün bildirim trafiği ve durum tutması karşılıksız bir maliyettir.

Dinamik yönlendirme, yol sayısı birden çoksa karşılığını verir. Ölçümdeki halka tam da budur: kiriş koptuğunda her hedefe hâlâ bir yol vardır ve dinamik rejim onu iki turda bulur. Statik rejimin bulamamasının nedeni yolun yokluğu değil, yolu arayan bir düzeneğin yokluğudur.

İkisinin karışımı da bir seçenektir ve yaygındır: uç ağlara statik satır, çekirdeğe dinamik protokol. Ölçüt her iki durumda da aynıdır — bir bağ koptuğunda kaç turda doğru tabloya varıldığı ve o turlarda kaç paketin hedefine varmadığı.

Bu ölçüt statik rejim için de tanımlıdır, ama karşılığı protokolde değil insandadır. Statik bir ağın yakınsama süresi, arızanın fark edilmesiyle satırların yeniden yazılması arasında geçen süredir; ölçüm bunu YL9 ile dışarıda bıraktı. Dışarıda bırakılmasının nedeni, sürenin protokolden okunamamasıdır: bir bildirim aralığı gibi bir üst sınırı yoktur ve arızanın ne kadar sonra görüleceğine bağlıdır. Ölçümdeki düz çizgi tam olarak bu belirsizliği temsil eder — o çizgi kendiliğinden inmez.

Özet

• Statik tabloyu yönetici yazar ve maliyeti yazma anındadır; satır sayısı $n(n-1)$ ile büyür ve sekiz düğümde elli altı satırdır.
• Statik tablo kopmayı hiç duymaz: kara delik sayısı altı turun altısında da 14’te kalır ve altı turdaki toplam kayıp 84 pakete ulaşır, dinamik rejimde 20.
• Elle düzeltme tek satırlık bir iş değildir; elli altı satırın 11’i 6 ayrı düğümde yanlış hâle gelir.
• Kopmayı yalnız iki düğüm duyduğunda kara delik 0’a iner ama 6 paket döngüye girer ve adım 61’den 94’e çıkar: kısmî bilgi, hiç bilgiden daha pahalı ve daha zor görülen bir arıza üretir.
• Tablosu doğru olan bir düğümden çıkan 1 paket bile ölür; hiçbir cihaz tek başına bir paketi döngüye sokamaz, döngü en az iki tablonun anlaşmazlığıdır.
• Seçim ölçütü yol sayısıdır: tek yollu uç ağda statik satır yeterlidir, birden çok yollu ağda dinamik protokolün bulduğu turlar karşılığını verir.

Sonraki Adım

Bu ölçümde haberin taşınması modellenmedi. Duyan küme dışarıdan verildi ve duyan her düğüm doğru tabloya bir anda vardı; sanki bağ koptuğu an gerçeğin tamamı elindeymiş gibi. Gerçekte bir düğümün komşusundan duyacağı şey topolojinin tamamı değildir. En yalın protokol ailesi komşudan yalnız tek bir şey duyar: komşunun her hedefe kaç adım uzakta olduğunu. Sonraki ders bu tek sayının nasıl yayıldığını, doğru tabloya kaç turda vardığını ve bu yalınlığın hangi kusuru getirdiğini ölçer.