Katmanlı Tasarım

Buraya kadar topoloji verilmişti. Sekiz düğüm, dokuz bağ, halkayı kesen bir kiriş — bunlar kurgunun sabitiydi ve ölçülen şey topolojiye verilen yanıttı: hangi aile kaç turda yakınsıyor, kısmî bilgi hangi kaderi üretiyor, kaplama kendi tablosuyla alttakiyle nasıl çelişiyor.

Topolojinin kendisi de bir seçimdir. Seçim yakınsama turunu, adım sayısını ve kopmanın kaç satırı değiştirdiğini birlikte belirler. Bu dersin sorusu şudur: aynı erişim anahtarlarını üç ayrı düzende bağladığımızda paketin ödediği şey nasıl değişir?

Katmanın Taşıdığı Karar

Katmanlı tasarım (layered design) cihazları rolüne göre ayırır ve her role tek bir karar verdirir.

Erişim katmanı (access layer) konakların bağlandığı yerdir. Kararı yereldir: çerçeve bu anahtarın bir bağlantı noktasına mı gidiyor, yoksa yukarı mı? Dağıtım katmanı (distribution layer) bir bina, kat ya da bölütün tamamını toplar; kararı bloğun sınırındadır ve blok dışına giden her şey ondan geçer. Çekirdek katmanı (core layer) yalnız blokları birbirine bağlar; hiçbir konak ona bağlanmaz ve kararı en dar olandır.

İki katmanlı düzende dağıtım ile çekirdek aynı cihazda birleşir; bu birleşmenin adı çöken çekirdek (collapsed core) düzenidir. Katmansız düzen ise bir seçim değil, seçimin yokluğudur: yeni anahtar bir öncekine takılır ve ağ bir zincir olarak büyür.

Ölçüm için üç düzen kurulur. Üçünde de dokuz erişim anahtarı vardır ve konaklar yalnız onlara bağlıdır; değişen tek şey aralarındaki düzendir.

# ogretilen dokum , calistirilmamistir

düz zincir — 1 katman
  erişim:    e1 - e2 - e3 - e4 - e5 - e6 - e7 - e8 - e9

çöken çekirdek — 2 katman
  çekirdek:  c1 - c2
  erişim:    e1..e9, her biri hem c1'e hem c2'ye

üç katmanlı — 3 katman
  çekirdek:  c1 - c2
  dağıtım:   d1 d2 | d3 d4 | d5 d6, her biri hem c1'e hem c2'ye
  erişim:    e1 e2 e3 -> d1 d2
             e4 e5 e6 -> d3 d4
             e7 e8 e9 -> d5 d6

Katmanın Söz Verdiği ve Vermediği

Katmanlı tasarımın gerekçesi çoğu zaman “daha hızlı” diye özetlenir ve bu özet yanlıştır. Katman eklemek yolu uzatır: her yeni katman, bloklar arası her paketin geçmek zorunda olduğu iki cihaz daha demektir.

Katmanın söz verdiği başka bir şeydir: bir bloğun içindeki değişiklik blokta kalır. Söz adımda değil, tabloda ve kopmanın yayılımındadır. Ölçüm sözün iki yakasını da sayar.

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

• TP1 — Üç tasarımın da dokuz erişim anahtarı aynıdır ve kırk paket yalnız bu dokuzun arasında üretilir. Karşılaştırılan şey konak sayısı değil, aradaki düzendir.
• TP2 — Kâhin topolojiyi biz kurduğumuz için bilinir ve her düğüm için her hedefe giden en kısa yolun ilk adımıdır. Eşit uzunluktaki yollarda düğüm adının sırası belirler.
• TP3 — Bütün bağların maliyeti birdir; ölçülen şey bant genişliği değil adımdır.
• TP4 — Yakınsama sayacı soğuk başlangıçtan işler: sıfırıncı turda her düğüm yalnız kendi bağlarını bilir. Uzaklık vektörü ailesinde tur, komşunun uzaklık dizisinin öğrenilmesidir; bağlantı durumu ailesinde komşunun bildiği bağların öğrenilmesidir.
• TP5 — Kesilen bağ elle seçilmez: kırk paketin en kısa yollarını taşıyan en yoğun bağ sayılarak bulunur. Üç tasarımda da aynı ölçüt uygulanır.
• TP6 — Atlama sınırı 12’dir; bu sınırı yakan paket döngü sayılır.
• TP7 — Tablo satırı, bir düğümün bir hedef için tuttuğu tek bir kayıttır; üç tasarımın satır sayısı düğüm sayısıyla birlikte büyür.
• TP8 — Kırk paketlik kümede ölçülebilen en küçük fark 1/40 = 0,025’tir; bundan küçük bir fark iddia edilmez.

Ölçüm

"""Katmanli tasarim: katman sayisinin adima ve yakinsama turuna etkisi.

Bolum 1 - uc tasarim yakinsamis halde: adim, tablo satiri, en uzun yol.
Bolum 2 - soguk baslangictan yakinsama turu.
Bolum 3 - en yogun bag koptugunda paketin kaderi ve yeniden yakinsama.
"""
TOHUM = 20260810
ATLAMA_SINIRI = 12
ERISIM = [f"e{i}" for i in range(1, 10)]
BLOK = {"d1": ERISIM[0:3], "d2": ERISIM[0:3], "d3": ERISIM[3:6],
        "d4": ERISIM[3:6], "d5": ERISIM[6:9], "d6": ERISIM[6:9]}

TASARIM = {
    "düz zincir": (ERISIM,
                   [(f"e{i}", f"e{i + 1}") for i in range(1, 9)]),
    "iki katmanlı": (ERISIM + ["c1", "c2"],
                     [(e, c) for e in ERISIM for c in ("c1", "c2")]
                     + [("c1", "c2")]),
    "üç katmanlı": (ERISIM + sorted(BLOK) + ["c1", "c2"],
                    [(e, d) for d, es in BLOK.items() for e in es]
                    + [(d, c) for d in sorted(BLOK) for c in ("c1", "c2")]
                    + [("c1", "c2")]),
}


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

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


def komsuluk(dugumler, 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(dugumler, baglar):
    """Her dugum icin her hedefe giden en kisa yolun ilk adimi."""
    k, tablo = komsuluk(dugumler, 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, dugumler, baglar):
    k, u, gecilen, atlama = komsuluk(dugumler, 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 = ERISIM[r(9)], ERISIM[r(9)]
        if x != y:
            liste.append((x, y))
    return liste


def olc(tablolar, dugumler, baglar):
    sayim, adim, en_uzun = {"ulasti": 0, "dongu": 0, "kara delik": 0}, 0, 0
    for x, y in ciftler():
        kader, a = ilet(x, y, tablolar, dugumler, baglar)
        sayim[kader] += 1
        adim += a
        if kader == "ulasti":
            en_uzun = max(en_uzun, a)
    return sayim, adim, en_uzun


def uzaklik_vektoru(dugumler, baglar, tur):
    """Her turda dugum yalniz komsusunun uzaklik dizisini ogrenir."""
    k = komsuluk(dugumler, 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(dugumler, baglar, tur):
    """Turlarda topoloji tasinir; tam topolojiyi alan dugum dogru hesaplar."""
    k = komsuluk(dugumler, baglar)
    bilinen = {u: {tuple(sorted((u, v))) for v in k[u]} for u in dugumler}
    for _ in range(tur):
        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:
        gor = sorted({x for b in bilinen[u] for x in b})
        for (x, h), adim in kahin(gor, sorted(bilinen[u])).items():
            if x == u:
                tablolar[(u, h)] = adim
    return tablolar


def en_yogun(dugumler, baglar):
    t, say = kahin(dugumler, baglar), {}
    for x, y in ciftler():
        u = x
        while u != y:
            v = t[(u, y)]
            say[tuple(sorted((u, v)))] = say.get(tuple(sorted((u, v))), 0) + 1
            u = v
    return max(say, key=say.get)


print(f"{'tasarım':<14s} {'katman':>6s} {'düğüm':>5s} {'bağ':>4s} "
      f"{'tablo satırı':>12s} {'ulaştı':>6s} {'adım':>5s} {'en uzun':>7s}")
for i, (ad, (D, B)) in enumerate(TASARIM.items()):
    t = kahin(D, B)
    s, a, u = olc(t, D, B)
    print(f"{ad:<14s} {i + 1:6d} {len(D):5d} {len(B):4d} {len(t):12d} "
          f"{s['ulasti']:6d} {a:5d} {u:7d}")

print()
print(f"{'tur':>3s}" + "".join(f"{ad:>17s}" for ad in TASARIM))
print(f"{'':>3s}" + f"{'uv   bd':>17s}" * 3)
for tur in range(0, 9):
    satir = f"{tur:3d}"
    for ad, (D, B) in TASARIM.items():
        uv = olc(uzaklik_vektoru(D, B, tur), D, B)[0]["ulasti"]
        bd = olc(baglanti_durumu(D, B, tur), D, B)[0]["ulasti"]
        satir += f"{uv:12d}{bd:5d}"
    print(satir)

print()
print(f"{'tasarım':<14s} {'kesilen':>9s} {'kopma anı':>18s} "
      f"{'yakınsamış':>18s} {'uv/bd turu':>10s} {'değişen satır':>13s}")
print(f"{'':<14s} {'':>9s} {'ulaştı kara delik':>18s} {'ulaştı kara delik':>18s}")
for ad, (D, B) in TASARIM.items():
    kes = en_yogun(D, B)
    kopuk = [b for b in B if tuple(sorted(b)) != kes]
    eski, yeni = kahin(D, B), kahin(D, kopuk)
    s0 = olc(eski, D, kopuk)[0]
    s1 = olc(yeni, D, kopuk)[0]
    tur_bd = next(t for t in range(12) if olc(baglanti_durumu(D, kopuk, t),
                                              D, kopuk)[0] == s1)
    tur_uv = next(t for t in range(12) if olc(uzaklik_vektoru(D, kopuk, t),
                                              D, kopuk)[0] == s1)
    degisen = sum(1 for a in eski if a in yeni and eski[a] != yeni[a])
    print(f"{ad:<14s} {kes[0] + '–' + kes[1]:>9s} {s0['ulasti']:11d}"
          f"{s0['kara delik']:7d} {s1['ulasti']:11d}{s1['kara delik']:7d} "
          f"{f'{tur_uv}/{tur_bd}':>10s} {f'{degisen}/{len(eski)}':>13s}")

tasarım        katman düğüm  bağ tablo satırı ulaştı  adım en uzun
düz zincir          1     9    8           72     40   121       8
iki katmanlı        2    11   19          110     40    80       2
üç katmanlı         3    17   31          272     40   138       4

tur       düz zincir     iki katmanlı      üç katmanlı
             uv   bd          uv   bd          uv   bd
  0           0   13           0    0           0    0
  1          13   22           0   40           0   11
  2          22   26          40   40          11   11
  3          26   29          40   40          11   40
  4          29   34          40   40          40   40
  5          34   37          40   40          40   40
  6          37   38          40   40          40   40
  7          38   40          40   40          40   40
  8          40   40          40   40          40   40

tasarım          kesilen          kopma anı         yakınsamış uv/bd turu değişen satır
                          ulaştı kara delik  ulaştı kara delik
düz zincir         e5–e6          19     21          19     21        3/2          0/72
iki katmanlı       c1–e7          26     14          40      0        2/1        18/110
üç katmanlı        c1–d3          20     20          40      0        4/3        24/272

Adım Sayısı Katmanla Birlikte Artmaz

Üst tablo katmanın söz vermediği şeyi doğrudan gösteriyor. İki katmanlı düzen kırk paketi 80 adımda taşıyor ve en uzun yol 2: her paket yukarı çıkıp aşağı iniyor, hepsi bu. Üç katmanlı düzen aynı kırk paket için 138 adım harcıyor ve en uzun yol 4’e çıkıyor. Üçüncü katman, iki katmanlı düzenin üstüne 58 adım ekliyor.

Şaşırtıcı olan üst satırdır: düz zincir 121 adımda bitiriyor ve üç katmanlı düzenden daha az adım harcıyor. Nedeni dağılımdadır: zincirde komşu anahtarlar arasındaki paket tek adımda varır ve kırk paketin on üçü böyledir. Zincirin en uzun yolu 8 adımdır, yani en kötü durumu üç katmanlının iki katıdır; toplam adımı düşük tutan şey en kötü durum değil, ucuz yakın komşulardır.

Buradan çıkan kural şudur: katman sayısı adım sayısını iyileştirmez. İki katmanlı düzenin 80’i bir alt sınırdır, çünkü herhangi iki erişim anahtarı arasında zaten en az iki adım vardır. Üçüncü katman bu sayıyı yalnız büyütebilir.

Yakınsama Turu Katmanla Birlikte Küçülür

Orta tablo aynı üç düzeni soğuk başlangıçtan izliyor ve buradaki sıralama tersine dönüyor.

Düz zincirde bağlantı durumu ailesi kırk paketin kırkını 7. turda ulaştırıyor, uzaklık vektörü ailesi 8. turda. Bilgi zincir boyunca komşudan komşuya sürünüyor: e1’in e9’u öğrenmesi için haberin sekiz bağ geçmesi gerekiyor. İki katmanlı düzende bağlantı durumu ailesi 1. turda bitiriyor — bir erişim anahtarının komşusu çekirdektir ve çekirdek herkesi tanır, dolayısıyla tek tur bütün topolojiyi taşımaya yetiyor. Üç katmanlı düzen 3. turda yakınsıyor: haberin erişimden dağıtıma, dağıtımdan çekirdeğe ve oradan geri inmesi gerekiyor.

Sıfırıncı tur satırı ayrıca okunmalıdır. Düz zincirde bağlantı durumu ailesi 13 paketi daha ilk anda ulaştırıyor, çünkü o on üç paketin hedefi zaten komşudur ve düğüm kendi bağlarını baştan bilir. İki ve üç katmanlı düzenlerde aynı hücre 0’dır: katmanlı bir tasarımda hiçbir erişim anahtarı bir başkasının komşusu değildir. Katmanlaşmanın ilk bedeli budur — sıfırıncı turda hiçbir paket ulaşmaz.

İki aile arasındaki bir turluk fark üç düzende de sürüyor: bağlantı durumu ailesi her tasarımda uzaklık vektörü ailesinden bir tur önce bitiriyor.

Kopmanın Ödettiği

Alt tablo en yoğun bağı kesiyor ve üç düzenin verdiği yanıt birbirinden tamamen ayrı.

Düz zincirde kesilen bağ e5–e6 ve sonuç kalıcıdır: 21 paket kara deliğe düşer ve tablolar yakınsadıktan sonra da 21 kalır. Zincirde alternatif yol yoktur; kopma ağı iki parçaya ayırır ve doğru tablo hesaplamak bir işe yaramaz. Değişen satır sayısı 0/72 bunu söylüyor: hesaplanacak yeni bir yol yok. Zincirin ucuz adım sayısı buraya kadardır.

İki katmanlı düzende kesilen bağ c1–e7‘dir. Kopma anında eski tablolarla **26 paket ulaşır, 14’ü kara deliğe düşer**; tablolar yakınsadığında 40/40‘a dönülür ve toplam adım yine 80‘dir — kaybedilen hiçbir şey yoktur, çünkü e7’nin c2 üzerinden ikinci bir yolu vardır. Bağlantı durumu ailesi bunu 1 turda onarır. Bedel **110 satırın 18’inin** değişmesidir.

Üç katmanlı düzende kesilen bağ c1–d3‘tür; kopma anında 20 ulaşır, 20 kara deliğe düşer, yakınsama 3 tur alır ve sonuç yine 40/40. Asıl fark en sağdaki sütundadır: değişen satır **272’nin 24’ü**, yani yüzde 9. İki katmanlı düzende aynı oran 110’un 18’i, yani yüzde 16. Üçüncü katmanın satın aldığı şey budur: kopma daha çok satır içeren bir tabloda daha az satırı kıpırdatır, çünkü değişiklik bloğun sınırında durur.

Takas böylece açıktır. Katman eklemek adım, yakınsama turu ve tablo satırı ekler; karşılığında verdiği tek şey değişikliğin dar kalmasıdır. Dokuz erişim anahtarında bu takas üçüncü katmanı haklı çıkarmaz; çekirdeğin dokuz yerine doksan dokuz komşusu olduğunda çıkarır.

Özet

• Katmanlı tasarım cihazları role ayırır: erişim konağı toplar, dağıtım bloğu toplar, çekirdek yalnız blokları bağlar; iki katmanlı düzende son iki rol aynı cihazda birleşir.
• Aynı dokuz erişim anahtarında düz zincir 121, iki katmanlı düzen 80, üç katmanlı düzen 138 adım harcar; katman eklemek adım sayısını iyileştirmez.
• Yakınsama turu ters yönde çalışır: bağlantı durumu ailesi zincirde 7, iki katmanlıda 1, üç katmanlıda 3 turda yakınsar ve her tasarımda uzaklık vektörü ailesinden bir tur öndedir.
• Katmanlı düzende sıfırıncı turda hiçbir paket ulaşmaz; zincirde 13 paket ulaşır, çünkü hedefleri zaten komşudur.
• En yoğun bağ koptuğunda zincir 21 paketi kalıcı olarak kaybeder; iki ve üç katmanlı düzenler 40/40’a döner, ama değişen satır oranı sırasıyla 18/110 ve 24/272’dir — üçüncü katmanın satın aldığı şey dar kalan değişikliktir.

Sonraki Adım

Üç tasarımın da örtük bir kabulü vardı: paket erişimden yukarı çıkar, bir yerde döner ve aşağı iner. Kırk paketin kaynağı da hedefi de erişim anahtarlarındaydı, ama düzen yukarı çıkmaya göre kurulmuştu. Üç katmanlı düzende bunun bedeli göründü — bloklar arası her paket dört adım harcadı, blok içindekiler ise iki. Aynı iki uç arasındaki adım sayısı, uçların hangi bloğa düştüğüne bağlıydı. Sonraki ders trafiğin çoğunun yukarı değil yana aktığı durumu ele alır: her yaprağın her omurgaya bağlandığı bir düzende iki yaprak arasındaki adım sayısı sabit kalır, ve bu sabitliğin tablo satırına ödettiği ayrı ayrı sayılır.