--- title: 'Omurga–Yaprak Tasarımı' source: 'https://academia.sh/tr/kurslar/anahtarlama-ve-yonlendirme/omurga-yaprak-tasarimi' course: 'Anahtarlama ve Yönlendirme' language: tr updated: '2026-08-17T18:07:21+00:00' license: 'CC BY-SA 4.0' --- # Omurga–Yaprak Tasarımı Her yaprağın her omurgaya bağlandığı düzende iki yaprak arası adım sayısı omurga sayısından, yaprak çiftinden ve kopmadan bağımsız olarak 2'de sabit kalır; sabitliğin bedeli tablo satırıdır ve dört omurgada tek yol satırı 90'dan 156'ya, çok yol satırı 90'dan 468'e çıkar. Ö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. ```text # 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 ```python """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.