Yönlendirme Kararı

Buraya kadar verilen bütün kararlar aynı yerel ağın içinde verildi. Bir anahtar, çerçevenin hedefini kendi eşleştirme tablosunda arıyordu; bulduğunda çerçeveyi doğrudan o bağlantı noktasından çıkarıyor, bulamadığında taşırıyordu. Hedef her durumda doğrudan komşuydu: aynı yayın alanının içinde, bir adım ötede.

Hedef başka bir ağdaysa bu kurgu çalışmaz. Doğrudan komşu değildir, tabloda bir bağlantı noktası karşılığı yoktur ve taşırmak bir seçenek değildir — ağların ağı taşırılamaz. Karar artık “hangi bağlantı noktası” sorusuna değil, “kime vereyim” sorusuna yanıt vermek zorundadır. Bu dersin sorusu, o yanıtın nereden okunduğudur.

Karar Neye Bakar

Bir yönlendiricinin verdiği karara yönlendirme kararı (routing decision) denir ve tek bir çıktısı vardır: bir sonraki düğüm (next hop). Paketin hedef adresi girdidir, komşu düğümlerden biri çıktıdır. Yönlendirici hedefe giden yolun tamamını bilmez, bilmesi de gerekmez; yalnızca bir adımı bilir ve paketi oraya verir. Yolun kalanı sonraki düğümün sorunudur.

Kararın alındığı yer paketin kendisi değildir. Paket hedef adresini taşır, başka bir şey taşımaz; hangi komşunun o hedefe yaklaştığını söylemez. Bunu söyleyen şey cihazın kendi belleğindeki yönlendirme tablosudur. Tablo, hedef adres öneklerini bir sonraki düğümlere eşleyen bir satır kümesidir:

# ogretilen dokum, calistirilmamistir

yönlendirme tablosu — satırlar yazıldıkları sırada

  önek        uzunluk   bir sonraki düğüm
  1010            4     kuzey
  10110           5     batı
  101011          6     doğu
  (boş)           0     merkez
  10101100        8     yerel
  10100           5     güney

Bu döküm bir belirtim değil, bir cihazın belleğinin okunmuş hâlidir; çalıştırılmamıştır ve buradan bir sayı iddiası çıkmaz. Dikkat edilecek tek şey satırların sırasıdır: satırlar zamanla eklenmiştir, uzunluğa göre sıralı değildir. Sonuncu satır ilk satırdan daha uzun bir önek taşır.

Boş önek satırı özeldir: uzunluğu sıfırdır ve her adresle eşleşir. Bu satır varsayılan yoldur ve tablonun eksiklerini kapatır. Onun sayesinde tablo dünyanın bütün adreslerini saymak zorunda kalmaz.

En Uzun Önek Eşleme

Yukarıdaki tabloda bir adres birden çok satırla eşleşebilir. 10101100 ile başlayan bir adres beş satırın dördüne uyar. Hangisi kazanır?

Kural en uzun önek eşleme (longest prefix match) adını taşır: eşleşen satırlar arasından öneki en uzun olan seçilir. Gerekçe bilgi miktarıdır. Uzun önek daha dar bir adres kümesini kapsar, dolayısıyla o küme hakkında daha kesin bir bildirimdir. Kısa önek ise geniş bir kümeyi kaba bir yaklaşımla toplar. İki bildirim çeliştiğinde kesin olan tercih edilir.

Buradaki asıl nokta şudur: kural tablonun içinde yazmaz. Tablo yalnız satırları taşır; hangi satırın kazanacağını belirleyen kural cihazın belirtiminde durur. Aynı satır kümesini başka bir kuralla okuyan bir cihaz başka bir karar verir. En yaygın yanlış kural, satırları yazıldıkları sırada tarayıp ilk eşleşeni almaktır.

Tablo Bir Kopyadır

Linux Ağ Yönetimi ve Sorun Giderme kursunda yönlendirme tablosu tek bir makinenin yapılandırması olarak okunmuştu: bir dosya, bir komut çıktısı, o makineye ait bir gerçek. Burada tablo bir yapılandırma değil, paylaşılan bir gerçeğin kopyasıdır — ağın topolojisi tektir, ama her cihaz onun kendi kopyasını tutar ve kararını o kopyadan okur.

Kopyalar anlaştığı sürece bu ayrım görünmez. Görünür hâle geldiği an, topolojinin değiştiği ve kopyaların henüz güncellenmediği andır. Bütün kopyaların gerçeğe uyduğu duruma yakınsama (convergence) denir; kurs boyunca ölçülen şey yakınsamanın kendisi değil, yakınsamamış geçen süredir.

O sürede paketin üç kaderi vardır. Ulaştı: hedefine vardı. Kara delik (black hole): bir düğümün tablosu artık var olmayan bir komşuyu gösterdi, paket orada öldü. Döngü: tablolar paketi birbirine geri gönderdi, paket atlama sınırını yakana kadar dolaştı.

Ölçülen ağ sekiz düğümlüdür. Yedi bağ bir halka kurar, sekizinci bağ halkayı kesen bir kiriştir. Kiriş halkanın iki yakasını kısa devre yaptığı için tabloların çoğu ondan geçer; koptuğunda çok sayıda satırın kararı değişmek zorundadır. Gerçeğin kendisi — kâhin (oracle) — topolojiyi biz kurduğumuz için bilinir: her düğüm için her hedefe giden en kısa yolun ilk adımıdır.

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

• YL1 — Ağ sekiz düğümlü, dokuz bağlıdır; yedi bağ halkayı, dokuzuncu bağ halkayı kesen kirişi kurar. Topolojiyi kurgu ürettiği için kâhin bilinir.
• YL2 — Kâhin, her düğüm için her hedefe giden en kısa yolun ilk adımıdır ve ölçüm boyunca değiştirilmez. Gerçek her zaman en kısa yoldur.
• YL3 — Ölçülen kopma yalnız kirişin kaybıdır: bir bağ düşer, düğüm kaybı yoktur ve ağ bölünmez. Kopmadan sonra her hedefe hâlâ bir yol vardır.
• YL4 — Kırk kaynak–hedef çifti sabit bir tohumdan üretilir. Aynı çift birden çok kez çıkabilir ve ölçüm bu tekrarları ayrı paket sayar.
• YL5 — Atlama sınırı 12’dir; sınırı yakan paket döngü sayılır. Sekiz düğümlü ağda en uzun döngüsüz yol yedi adımdır, sınır bunun belirgin biçimde üstündedir.
• YL6 — Önek ölçümünde adres sekiz bitliktir ve uzayın tamamı taranır; örnek seçilmez. Tablo satırları yazıldıkları sırada durur.
• YL7 — Kümenin çözünürlüğü ölçüm bandının alt sınırıdır: kırk paketlik kümede ölçülebilen en küçük fark 1/40 = 0,025, adres uzayında 1/256’dır.

Aynı Tablo, İki Kural

Önce kuralın kendisi ölçülür. Yukarıdaki altı satırlık tablo iki farklı kuralla okunur ve sekiz bitlik adres uzayının tamamı taranır.

"""En uzun onek eslemesi: ayni tablo, iki okuma kurali.

Satirlar yazildiklari sirada durur, uzunluga gore sirali degildir.
Sekiz bitlik adres uzayinin tamami taranir; ornek secilmez.
"""
TABLO = [("1010", "kuzey"), ("10110", "batı"), ("101011", "doğu"),
         ("", "merkez"), ("10101100", "yerel"), ("10100", "güney")]
DUGUMLER = ("kuzey", "güney", "doğu", "batı", "merkez", "yerel")
ADRESLER = [format(a, "08b") for a in range(256)]


def en_uzun_onek(adres):
    secili = None
    for onek, dugum in TABLO:
        if adres.startswith(onek) and (secili is None or len(onek) > len(secili[0])):
            secili = (onek, dugum)
    return secili


def ilk_eslesen(adres):
    for onek, dugum in TABLO:
        if adres.startswith(onek):
            return (onek, dugum)
    return None


ayrisan = [a for a in ADRESLER if en_uzun_onek(a)[1] != ilk_eslesen(a)[1]]
print(f"tablo satırı {len(TABLO)} | adres uzayı {len(ADRESLER)} | "
      f"iki kuralın ayrıştığı adres {len(ayrisan)}")
print()
print(f"{'bir sonraki düğüm':>18s} {'en uzun önek':>13s} {'ilk eşleşen':>12s}")
for dugum in DUGUMLER:
    print(f"{dugum:>18s} {sum(en_uzun_onek(a)[1] == dugum for a in ADRESLER):13d}"
          f" {sum(ilk_eslesen(a)[1] == dugum for a in ADRESLER):12d}")
print()
for a in (ayrisan[0], ayrisan[8], ayrisan[11]):
    u, i = en_uzun_onek(a), ilk_eslesen(a)
    print(f"  {a} -> en uzun önek {u[1]} ({u[0]}), ilk eşleşen {i[1]} ({i[0]})")

tablo satırı 6 | adres uzayı 256 | iki kuralın ayrıştığı adres 12

 bir sonraki düğüm  en uzun önek  ilk eşleşen
             kuzey             4           16
             güney             8            0
              doğu             3            0
              batı             8            8
            merkez           232          232
             yerel             1            0

  10100000 -> en uzun önek güney (10100), ilk eşleşen kuzey (1010)
  10101100 -> en uzun önek yerel (10101100), ilk eşleşen kuzey (1010)
  10101111 -> en uzun önek doğu (101011), ilk eşleşen kuzey (1010)

İki kural 256 adresin 12’sinde ayrışıyor. Ayrışmanın yönü tek taraflı: satır sırasına göre okuyan cihaz kuzey’e 16 adres gönderiyor, en uzun öneke göre okuyan 4. Aradaki on iki adresin sekizi güney’e, üçü doğu’ya, biri yerel’e gitmesi gereken adreslerdir. merkez sütunu ikisinde de 232’dir: varsayılan yol her iki kuralda da son çare olarak kalır, çünkü hiçbir uzun önekle eşleşmeyen adresler için tek eşleşme odur.

batı sütunundaki 8 de ikisinde aynıdır ve bu bir tesadüf değil: 10110 öneki hiçbir kısa önekle çakışmaz, tabloda onu kapsayan başka satır yoktur. Ayrışma yalnız iç içe geçmiş öneklerde doğar. Tabloda iç içelik olmasaydı iki kural aynı kararı verirdi ve kuralın belirtimde yazılı olması gerekmezdi.

Kopmadan Önce ve Sonra

Şimdi kural sabitlenir ve tablo değişir. Üç kuşak yan yana konur: kopma yokken yakınsamış tablolar, kopma anında hâlâ eski olan tablolar, ve kopmadan sonra yeniden yakınsamış tablolar. Kırk paket her üçünde de aynı çiftler arasında yürütülür.

"""Tablo bir kopyadir: ayni kural, uc tablo kusagi.

Sekiz dugum, halkayi kesen b-f kirisi; olculen kopma o kirisin kaybi.
"""
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):
    """Paketi tablolara gore yurutur; kaderini, adimi ve olen dugumu dondurur."""
    k, u, gecilen, atlama = komsuluk(baglar), kaynak, [], 0
    while u != hedef:
        if atlama >= ATLAMA_SINIRI:
            return "dongu", atlama, u
        sonraki = tablolar.get((u, hedef))
        if sonraki is None or sonraki not in k[u]:
            return "kara delik", atlama, u
        if (u, sonraki) in gecilen:
            return "dongu", atlama, u
        gecilen.append((u, sonraki))
        u, atlama = sonraki, atlama + 1
    return "ulasti", atlama, None


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


eski, yeni = kahin(BAGLAR), kahin(KOPUK)
print(f"düğüm {len(DUGUMLER)} | bağ {len(BAGLAR)} | tablo satırı {len(eski)} | "
      f"ölçülen çift {len(ciftler())} | atlama sınırı {ATLAMA_SINIRI}")
print()
print(f"{'tablo kuşağı':<27s} {'ulaştı':>7s} {'döngü':>6s} {'kara delik':>11s} {'adım':>5s}")
for ad, tab, bag in (("yakınsamış, kopma yok", eski, BAGLAR),
                     ("kopma anı, tablolar eski", eski, KOPUK),
                     ("kopma sonrası, yakınsamış", yeni, KOPUK)):
    s, a = olc(tab, bag)
    print(f"{ad:<27s} {s['ulasti']:7d} {s['dongu']:6d} {s['kara delik']:11d} {a:5d}")
print()
degisen = sum(1 for anahtar in eski if eski[anahtar] != yeni[anahtar])
print(f"kopmadan sonra kararı değişmek zorunda olan satır: {degisen}/{len(eski)}")
olen = {}
for x, y in ciftler():
    kader, _, dugum = ilet(x, y, eski, KOPUK)
    if kader != "ulasti":
        olen[dugum] = olen.get(dugum, 0) + 1
print("paketin öldüğü düğüm:", dict(sorted(olen.items())))

düğüm 8 | bağ 9 | tablo satırı 56 | ölçülen çift 40 | atlama sınırı 12

tablo kuşağı                 ulaştı  döngü  kara delik  adım
yakınsamış, kopma yok            40      0           0    83
kopma anı, tablolar eski         26      0          14    61
kopma sonrası, yakınsamış        40      0           0    99

kopmadan sonra kararı değişmek zorunda olan satır: 11/56
paketin öldüğü düğüm: {'b': 6, 'f': 8}

Kopmanın Okunması

Üç satır üç ayrı şey söylüyor.

Yakınsamış ağda kırk paketin kırkı da ulaşıyor, toplam 83 adımla. Bu, tabloların gerçekle uyuştuğu durumdur ve ölçümün taban çizgisidir. Alt satır aynı sonucu kopmadan sonra veriyor: yine 40/40, ama 99 adımla. Kiriş gidince yollar uzuyor; on altı adımlık fark budur. Ağın kaybettiği şey bağlanabilirlik değil, kısalıktır — hiçbir paket kaybolmuyor.

Ortadaki satır ise arada geçen süredir. Tablolar hâlâ kirişi gösterirken 26 paket ulaşıyor, 14’ü kara deliğe düşüyor. Bu on dördü ölçülebilir bir paydır: kırk paketlik kümede 0,350, bandın alt sınırının on dört katı.

Toplam adımın burada 61’e düşmesi ilk bakışta iyi görünür ve tam da bu yüzden dikkat ister. Adım azaldı çünkü paketlerin üçte biri yola devam etmedi: kara deliğe düşen paket hemen ölür, geri kalan adımlarını harcamaz. Düşük adım sayısı burada bir başarı değil, bir kayıp imzasıdır.

Son iki satır arızanın nerede olduğunu söylüyor. Kopmadan sonra kararı değişmek zorunda olan satır sayısı 11; tablo elli altı satır taşıyor, yani satırların büyük çoğunluğu doğru kalıyor. Buna karşın on dört paket ölüyor. Sebep, ölen paketlerin hepsinin iki düğümde ölmesi: b’de altı, f’de sekiz. Bunlar kopan kirişin iki ucudur.

Buradan çıkan sonuç kursun eksenidir. Bir paketin kaderi çıktığı düğümün tablosunun doğru olmasına bağlı değildir. Kaynak düğümün satırı doğru olabilir; paket yolda, tablosu yanlış olan bir düğüme uğrar ve orada ölür. Karar zinciri boyunca en eski kopya sonucu belirler.

Özet

• Yönlendirme kararının girdisi paketin hedef adresi, çıktısı bir sonraki düğümdür; yönlendirici yolun tamamını değil yalnız bir adımı bilir.
• Karar iletide yazana değil cihazın kendi tablosuna bakılarak alınır; kararı belirleyen kural tabloda değil belirtimde durur.
• En uzun önek eşleme, eşleşen satırlar arasından en dar kümeyi seçer; satır sırasına göre okuyan bir kural aynı tabloda 256 adresin 12’sinde başka bir karar verir ve ayrışma yalnız iç içe geçmiş öneklerde doğar.
• Tablo bir yapılandırma değil, paylaşılan bir gerçeğin kopyasıdır; yakınsamış ağda kırk paketin kırkı ulaşır, kopmadan önce 83, kopmadan sonra 99 adımla.
• Kopma anında eski tablolarla 26 paket ulaşır, 14’ü kara deliğe düşer; adımın 61’e düşmesi kazanç değil, ölen paketlerin adım harcamamasıdır.
• Elli altı satırın yalnız 11’i yanlıştır, ama ölen on dört paketin hepsi kopan bağın iki ucunda ölür: kaderi belirleyen şey kaynağın kopyası değil, yol üzerindeki en eski kopyadır.

Sonraki Adım

Bu ölçümde tablolar iki kez elle kuruldu: bir kez kopmadan önceki gerçekten, bir kez kopmadan sonraki gerçekten. Aradaki geçişi kimse yapmadı — ikinci kuşak tablo ölçüme hazır biçimde verildi. Gerçek bir ağda o geçişi birinin yapması gerekir ve iki seçenek vardır: tabloyu bir yönetici yazar, ya da cihazlar birbirine anlatır. Sonraki ders bu iki seçeneği yan yana koyar ve şunu sorar: elle yazılmış bir tablo kopmayı ne zaman öğrenir, ve kara delik sayısı zamanla ne yapar?