Omurga–Yaprak Tasarımı

Önceki ders üç düzeni aynı dokuz erişim anahtarı üzerinde ölçtü ve üç katmanlı düzende bir tutarsızlık bıraktı: aynı iki uç arasındaki adım sayısı, uçların hangi bloğa düştüğüne bağlıydı. Blok içindeki paket iki adım, bloklar arasındaki paket dört adım harcadı. Katmanlı düzenin örtük kabulü, trafiğin çoğunun yukarı akmasıydı — konaktan çıkıp ağın dışına giden, kuzey–güney yönlü trafik. O kabul doğruyken bloklar arası dört adım seyrek ödenir.

Kabul her zaman doğru değildir. Bir konağın konuştuğu şey ağın dışı değil, aynı ağdaki başka bir konaksa trafik yukarı değil yana akar. Bu dersin sorusu şudur: trafiğin çoğu yaprakla yaprak arasındaysa hangi düzen adım sayısını uçların yerinden bağımsız kılar, ve bunun bedeli nedir?

Doğu–Batı Trafiği

Ağdaki iki uç arasında, ağın dışına çıkmadan akan trafiğe doğu–batı trafiği (east–west traffic) denir. Karşıtı kuzey–güney trafiğidir: konaktan çıkıp çekirdeği aşan, ağın dışına giden akış.

Katmanlı tasarım kuzey–güney için kurulur. Bloğun dağıtım çifti, bloğun bütün trafiğini toplayıp çekirdeğe verir; çekirdek onu dışarıya taşır. Bu düzende doğu–batı trafiği bir istisna gibi işlenir: iki blok arasındaki her paket kendi dağıtım çiftine çıkar, çekirdeğe tırmanır, öteki dağıtım çiftine iner ve oradan yaprağa ulaşır. Ölçüm bunu önceki derste dört adım olarak saymıştı.

Sorun yalnız adım sayısı değildir. Blok içi paket iki, bloklar arası paket dört adım harcadığında iki uç arasındaki maliyet uçların nereye takıldığına bağlı olur. Bir konağı başka bir yaprağa taşımak, kimseyle konuşmasını değiştirmeden gecikmesini değiştirir.

Omurga ve Yaprak

Omurga–yaprak (spine–leaf) düzeni bu bağımlılığı yapısal olarak kaldırır. İki tür cihaz vardır. Yaprak konakların bağlandığı anahtardır. Omurga yalnız yaprakları bağlar ve hiçbir konak ona takılmaz. Kural tektir: her yaprak her omurgaya bağlanır, omurgalar birbirine bağlanmaz, yapraklar birbirine bağlanmaz.

Bu kuralın doğrudan sonucu şudur: bir yapraktan bir başka yaprağa giden her yol tam olarak iki adımdır — yaprak, omurga, yaprak. Başka uzunlukta bir yol yoktur, çünkü başka bir bağ yoktur.

# ogretilen dokum , calistirilmamistir

omurga–yaprak, 3 omurga
  omurga:   o1        o2        o3
  yaprak:   y1 y2 y3 y4 y5 y6 y7 y8 y9
  kural:    her y, her o'ya bağlı  (9 x 3 = 27 bağ)
            o–o bağı yok, y–y bağı yok

  y3 -> y8 için yollar:  y3-o1-y8   y3-o2-y8   y3-o3-y8
  hepsi 2 adım, hepsi eşit maliyetli

Üç yol da eşit uzunlukta olduğu için yaprak birini seçmek zorundadır. Seçim eşit maliyetli çoklu yol (equal-cost multipath) kuralıyla yapılır: yaprak, hedefe giden bütün eşit maliyetli bir sonraki düğümleri tablosunda tutar ve her akış için birini seçer. Aynı akışın bütün paketleri aynı seçimi alır. Akışın bölünmemesi kuralı Bağlantı Toplama dersinde kurulmuştu; orada seçim bir bağ demetinin bacakları arasındaydı, burada aynı kural yol üzerinde işler.

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

• TP9 — Dokuz yaprak (y1–y9) önceki dersin dokuz erişim anahtarıdır; kırk çift yalnız bunların arasında üretilir. Ölçülen şey bu yüzden tümüyle doğu–batı trafiğidir.
• TP10 — Omurga sayısı 1, 2, 3 ve 4 olarak denenir; her denemede yaprak sayısı sabittir. Karşılaştırma satırı olarak önceki dersin üç katmanlı düzeni aynı dokuz yaprakla yeniden kurulur.
• TP11 — Kâhin her hedef için en kısa yolun bütün ilk adımlarını verir; eşit maliyetli yollar teke indirilmez.
• TP12 — Akış seçimi akış numarasının eşit maliyetli aday sayısına bölümünden kalanla yapılır. Gerçek düzenekte seçim başlık alanlarının karmasıyla yapılır; ölçümde önemli olan seçimin akış başına sabit ve yollar arasında düzgün dağılmış olmasıdır.
• TP13 — Bütün bağların maliyeti birdir; ölçülen şey adımdır.
• TP14 — “Tek yol satırı” her hedef için bir kayıt sayar, “çok yol satırı” her eşit maliyetli bir sonraki düğüm için ayrı kayıt sayar. İkisi aynı tablonun iki muhasebesidir.
• TP15 — Kopma her düzende aynı biçimde uygulanır: bir yaprağın ilk omurgaya giden bağı kesilir (y7–o1). Üç katmanlı düzende karşılığı aynı yaprağın dağıtım bağıdır (d5–y7).
• TP16 — Kırk paketlik kümede ölçülebilen en küçük fark 1/40 = 0,025’tir; atlama sınırı 12’dir.

Ölçüm

"""Omurga-yaprak: iki yaprak arasindaki adimin sabitligi ve tablo satirina bedeli.

Bolum 1 - omurga sayisi degisirken adim, bag ve tablo satiri.
Bolum 2 - bir yaprak-omurga bagi koptugunda kopma ani ve yakinsamis hal.
"""
TOHUM = 20260810
ATLAMA_SINIRI = 12
YAPRAK = [f"y{i}" for i in range(1, 10)]
BLOK = {"d1": YAPRAK[0:3], "d2": YAPRAK[0:3], "d3": YAPRAK[3:6],
        "d4": YAPRAK[3:6], "d5": YAPRAK[6:9], "d6": YAPRAK[6:9]}
UC_KATMANLI = (YAPRAK + sorted(BLOK) + ["c1", "c2"],
               [(y, d) for d, ys in BLOK.items() for y in ys]
               + [(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 uzakliklar(dugumler, baglar):
    k, uzak = komsuluk(dugumler, baglar), {}
    for kaynak in dugumler:
        gorulen, sira, d = {kaynak}, [kaynak], 0
        uzak[(kaynak, kaynak)] = 0
        while sira:
            d, yeni = d + 1, []
            for u in sira:
                for v in sorted(k[u]):
                    if v not in gorulen:
                        gorulen.add(v)
                        uzak[(kaynak, v)] = d
                        yeni.append(v)
            sira = yeni
    return uzak


def kahin(dugumler, baglar):
    """Her hedef icin en kisa yolun ilk adimlarinin tamami (esit maliyetli)."""
    k, uzak, tablo = komsuluk(dugumler, baglar), uzakliklar(dugumler, baglar), {}
    for u in dugumler:
        for h in dugumler:
            if u == h or (u, h) not in uzak:
                continue
            tablo[(u, h)] = [v for v in sorted(k[u])
                             if uzak.get((v, h), 99) == uzak[(u, h)] - 1]
    return tablo


def ilet(akis, kaynak, hedef, tablolar, dugumler, baglar):
    """Esit maliyetli yollardan biri akis numarasina gore secilir."""
    k, u, gecilen, atlama = komsuluk(dugumler, baglar), kaynak, [], 0
    while u != hedef:
        if atlama >= ATLAMA_SINIRI:
            return "dongu", atlama
        aday = [v for v in tablolar.get((u, hedef), []) if v in k[u]]
        if not aday:
            return "kara delik", atlama
        sonraki = aday[akis % len(aday)]
        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 = YAPRAK[r(9)], YAPRAK[r(9)]
        if x != y:
            liste.append((x, y))
    return liste


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


def yuk(tablolar, dugumler, baglar):
    """Kirk akisin her bagi kac kez kullandigi; en yuklu bag dondurulur."""
    k, say = komsuluk(dugumler, baglar), {}
    for i, (x, y) in enumerate(ciftler()):
        u, atlama = x, 0
        while u != y and atlama < ATLAMA_SINIRI:
            aday = [v for v in tablolar.get((u, y), []) if v in k[u]]
            if not aday:
                break
            v = aday[i % len(aday)]
            bag = tuple(sorted((u, v)))
            say[bag] = say.get(bag, 0) + 1
            u, atlama = v, atlama + 1
    return max(say.values())


def omurga_yaprak(omurga):
    o = [f"o{i}" for i in range(1, omurga + 1)]
    return YAPRAK + o, [(y, s) for y in YAPRAK for s in o]


DUZEN = {f"omurga–yaprak, {s} omurga": omurga_yaprak(s) for s in (1, 2, 3, 4)}
DUZEN["üç katmanlı (01. ders)"] = UC_KATMANLI

print(f"{'düzen':<24s} {'düğüm':>5s} {'bağ':>4s} {'ulaştı':>6s} {'adım':>5s} "
      f"{'aralık':>6s} {'en yüklü bağ':>12s} {'tek yol':>7s} {'çok yol':>7s}")
for ad, (D, B) in DUZEN.items():
    t = kahin(D, B)
    s, a, (mn, mx) = olc(t, D, B)
    print(f"{ad:<24s} {len(D):5d} {len(B):4d} {s['ulasti']:6d} {a:5d} "
          f"{f'{mn}–{mx}':>6s} {yuk(t, D, B):12d} {len(t):7d} "
          f"{sum(len(v) for v in t.values()):7d}")

print()
print(f"{'düzen':<24s} {'kesilen':>7s} {'kopma anı':>18s} {'yakınsamış':>18s} "
      f"{'adım':>5s}")
print(f"{'':<24s} {'':>7s} {'ulaştı kara delik':>18s} {'ulaştı kara delik':>18s}")
for ad, (D, B) in DUZEN.items():
    kes = ("y7", "o1") if "omurga" in ad else ("d5", "y7")
    kopuk = [b for b in B if tuple(sorted(b)) != tuple(sorted(kes))]
    eski, yeni = kahin(D, B), kahin(D, kopuk)
    s0 = olc(eski, D, kopuk)[0]
    s1, a1, _ = olc(yeni, D, kopuk)
    print(f"{ad:<24s} {kes[0] + '–' + kes[1]:>7s} {s0['ulasti']:11d}"
          f"{s0['kara delik']:7d} {s1['ulasti']:11d}{s1['kara delik']:7d} {a1:5d}")

düzen                    düğüm  bağ ulaştı  adım aralık en yüklü bağ tek yol çok yol
omurga–yaprak, 1 omurga     10    9     40    80    2–2           14      90      90
omurga–yaprak, 2 omurga     11   18     40    80    2–2            9     110     198
omurga–yaprak, 3 omurga     12   27     40    80    2–2            6     132     324
omurga–yaprak, 4 omurga     13   36     40    80    2–2            5     156     468
üç katmanlı (01. ders)      17   31     40   138    2–4           11     272     500

düzen                    kesilen          kopma anı         yakınsamış  adım
                                  ulaştı kara delik  ulaştı kara delik
omurga–yaprak, 1 omurga    y7–o1          26     14          26     14    52
omurga–yaprak, 2 omurga    y7–o1          38      2          40      0    80
omurga–yaprak, 3 omurga    y7–o1          38      2          40      0    80
omurga–yaprak, 4 omurga    y7–o1          39      1          40      0    80
üç katmanlı (01. ders)     d5–y7          38      2          40      0   138

Adım Sabittir

aralık sütunu dört omurga–yaprak satırında da 2–2 yazıyor: kırk paketin en kısası da en uzunu da iki adım. Toplam adım dört düzende de 80’dir ve omurga sayısıyla hiç değişmiyor.

Bu sabitlik üç ayrı boyutta geçerlidir ve üçü de tabloda okunur. Yaprak çiftinden bağımsız: kırk çift dokuz yaprak arasından üretildi ve hiçbiri ikiden uzun bir yol bulamadı. Omurga sayısından bağımsız: bir omurgadan dört omurgaya çıkarken bağ sayısı dokuzdan otuz altıya çıktı, adım aynı kaldı. Kopmadan bağımsız: alt tabloda y7–o1 kesildikten sonra yakınsamış adım toplamı yine 80’dir.

Karşılaştırma satırı farkı veriyor. Üç katmanlı düzen aynı kırk paketi 138 adımda taşıyor ve aralığı 2–4. Aradaki 58 adımın tamamı bloklar arası trafiğin çekirdeğe tırmanmasından geliyor. Doğu–batı trafiği için katmanlı düzen yalnız daha yavaş değil, öngörülemezdir: maliyeti uçların hangi bloğa düştüğü belirler.

Sabitliğin kaynağı bir eniyileme değil, bir yokluktur. Omurgalar birbirine bağlanmadığı ve yapraklar birbirine bağlanmadığı için üç adımlık bir yol kurulamaz. Düzen kısa yolu seçmiyor; uzun yolu var etmiyor.

Sabitliğin Bedeli Tablo Satırıdır

Sağdaki iki sütun bedeli veriyor ve ikisi ayrı ayrı okunmalıdır.

Tek yol satırı her hedef için bir kayıt sayar: bir omurgada 90, iki omurgada 110, üç omurgada 132, dört omurgada 156. Artış düğüm eklemekten gelir; her yeni omurga hem kendisi bir hedef olur hem de herkesin tablosuna bir satır ekler.

Çok yol satırı asıl bedeldir. Yaprak, hedefe giden eşit maliyetli bütün bir sonraki düğümleri tutmak zorundadır; iki omurgada her uzak hedefin iki, dört omurgada dört kaydı olur. Sayı 90’dan 468’e çıkıyor — omurga sayısı dörde katlanırken satır 5,2 katına çıkıyor. Adım hiç değişmediği hâlde.

Kural şudur: omurga–yaprak düzeninde ölçek adımla değil satırla ödenir. Katmanlı tasarımda büyüme adımı uzatır ve tabloyu bloğun sınırında keser; omurga–yaprakta büyüme adımı hiç değiştirmez ve her yaprağın tablosunu genişletir. İki tasarım aynı kaynağı iki ayrı hesaba yazar.

Karşılaştırma satırı burada omurga–yaprağın lehinedir: üç katmanlı düzen 272 tek yol ve 500 çok yol satırı tutuyor, iki omurgalı düzen 110 ve 198. Üç katmanlı düzenin fazlası ara katmanın kendi düğümlerinden gelir — altı dağıtım ve iki çekirdek cihazı, hepsi birbirinin tablosunda.

Omurga Sayısı Neyi Değiştirir

Adım değişmiyorsa ikiden fazla omurga niye kurulur? Yanıt en yüklü bağ sütunundadır. Kırk akışın en çok yüklediği bağ, bir omurgada 14 akış taşıyor; iki omurgada 9, üç omurgada 6, dört omurgada 5. Omurga eklemek gecikmeyi değil yoğunluğu düşürür; akışlar paralel yollara dağılır.

İkinci yanıt alt tablodadır. Tek omurgalı düzen bir tasarım değildir: y7–o1 kesildiğinde 14 paket kara deliğe düşer ve tablolar yakınsadıktan sonra da 14 kalır, çünkü y7’nin başka yolu yoktur. İki omurgadan itibaren aynı kopma yakınsamadan sonra 0 kara delik bırakır; kopma anında kalan 2 paket, o anda o1’i seçmiş olan akışlardır. Dört omurgada bu sayı 1’e iner: kopan bağı kullanan akış oranı omurga sayısıyla azalır.

Bir uyarı gereklidir. Ölçüm bütün bağların maliyetini bir sayar ve bant genişliğini hiç görmez. Gerçek bir düzende yaprağın aşağı bakan toplam kapasitesi, yukarı bakan toplam kapasitesinden büyük olabilir; o durumda en yüklü bağ sütunu akış sayısını değil, akışların sığmadığı yeri gösterir. Bu ders o hesabı yapmaz; yalnız akışın kaç bağa dağıldığını sayar.

Özet

• Doğu–batı trafiği ağın içinde kalan trafiktir; katmanlı tasarım kuzey–güney için kurulur ve doğu–batı paketini çekirdeğe tırmandırır.
• Omurga–yaprak düzeninde her yaprak her omurgaya bağlanır, omurgalar ve yapraklar kendi aralarında bağlanmaz; bu yüzden iki yaprak arası her yol 2 adımdır.
• Sabitlik üç boyutta geçerlidir: yaprak çiftinden, omurga sayısından ve kopmadan bağımsız olarak toplam 80 adım; üç katmanlı düzen aynı kırk paket için 138 adım ve 2–4 aralık verir.
• Bedel tablo satırıdır: bir omurgadan dört omurgaya çıkarken tek yol satırı 90’dan 156’ya, çok yol satırı 90’dan 468’e çıkar.
• Omurga eklemek adımı değil yoğunluğu düşürür — en yüklü bağ 14 akıştan 5 akışa iner; tek omurgalı düzende kopma 14 paketi kalıcı olarak kaybettirir, iki omurgadan itibaren kayıp yakınsamayla 0’a iner.

Sonraki Adım

Omurga–yaprak düzeninde yedeklilik yapısaldır: hiçbir cihaz tek başına bir yolun sahibi değildir ve bir omurganın kaybı yalnız akışların dağılımını değiştirir. Ama yaprağa bağlı konak, ağın dışına giden paketini bir yola değil bir adrese yollar — varsayılan ağ geçidinin adresine. O adres tek bir cihazın üstünde durur ve o cihaz düştüğünde yedeklilik yapısal olmaktan çıkıp bir devralmaya dönüşür: adresin sahibi değişmelidir ve değişimi herkesin duyması gerekir. Sonraki ders devralma penceresinde paketin kaderini sayar ve kısmî bilginin döngü ürettiğini ikinci kez ölçer.