--- title: 'Kapsayan Ağaç Protokolü' source: 'https://academia.sh/tr/kurslar/anahtarlama-ve-yonlendirme/kapsayan-agac-protokolu' course: 'Anahtarlama ve Yönlendirme' language: tr updated: '2026-08-17T18:07:19+00:00' license: 'CC BY-SA 4.0' --- # Kapsayan Ağaç Protokolü Engellenmemiş bir halkada tek bir yayın çerçevesi on iki turda 142 kopya üretir ve durmaz; ağaçta 7 kopyada biter. Ağaç yeniden kurulduğunda tablolar eskiyse 20 paket kara deliğe düşer, tabloları yalnız iki anahtar tazelemişse 10 paket döngüye girer. Önceki ders iki anahtar arasına tek bir kablo koydu ve taşırılan her çerçeve o kabloyu bir kez geçip bitti. Yedeklilik istendiğinde ikinci bir kablo çekilir; iki anahtar iki ayrı yoldan birbirine bağlanır ve biri koptuğunda öbürü ayakta kalır. Bu, ağ tasarımının en eski ve en doğal isteğidir. İstek, taşırma ile bir araya geldiğinde bir arıza üretir. Taşırılan çerçeve birinci kablodan karşıya geçer, karşıdaki anahtar onu geldiği bacak dışındaki bütün bacaklara taşırır — ikinci kablo da bunların içindedir — ve çerçeve ilk anahtara geri döner. Geri döndüğünde ilk anahtar onu yeniden taşırır. Bu dersin sorusu, bu dönüşün nasıl durdurulduğu ve durdurma kararının paketin kaderine ne yaptığıdır. ## Çerçevede Sayaç Yoktur Yukarıdaki dönüşün neden kendiliğinden bitmediğini görmek için çerçeveye bakmak yeter. Bir Ethernet çerçevesinde hedef adresi, kaynak adresi, tür alanı, yük ve denetim dizisi vardır. **Kaç cihazdan geçtiğini sayan bir alan yoktur.** Ağ katmanı paketinde böyle bir alan bulunur ve Ağ Modelleri kursunda kuruldu; bağlantı katmanı çerçevesinde bulunmaz. Sonuç ikili değil, üçlüdür. Birincisi, dolaşan çerçeve hiçbir zaman **yaşlanarak** ölmez. İkincisi, halka üzerindeki her anahtar çerçeveyi her turda **çoğaltır**: gelen bir kopya, giden birden çok kopya doğurur. Üçüncüsü, aynı kaynak adresi farklı bacaklardan görüldüğü için her anahtarın eşleştirme tablosu tur başına yeniden yazılır — tablo, önceki derste ölçülen anlamda eskimiş değil, **kararsızdır.** Bu üçlü, döngünün neden kara delikten daha pahalı olduğunun ilk örneğidir. Kara delikte paket ölür ve iş biter; burada paket ölmez, çoğalır ve ağın taşıma kapasitesini kendisi tüketir. Dışarıdan bakan biri bunu bir tıkanıklık olarak görür. ## Protokolün Kararı Çözüm, fiziksel olarak halka olan bir topolojiyi mantıksal olarak **ağaç** hâline getirmektir. Ağaçta çevrim yoktur; çevrim yoksa dönüş de yoktur. Bunun için bazı bağların **engellenmesi** gerekir: bağ ayakta kalır, kablo takılıdır, ama üzerinden veri çerçevesi geçmez. **Kapsayan ağaç protokolü (spanning tree protocol)** bu ağacı anahtarların kendi aralarında kurmasını sağlar. Karar üç adımdadır. Anahtarlar önce bir **kök** seçer: her anahtarın bir tanımlayıcısı vardır ve en küçük tanımlayıcı kök olur. Sonra her anahtar köke giden en ucuz bacağını **kök bacağı** olarak işaretler. Son olarak her bağ üzerinde, o bağı köke daha ucuz bağlayan uç **atanmış** sayılır; öbür uç **engellenir.** Ağacın kendisinin nasıl kurulduğu bu dersin konusu değildir. Kapsayan ağaç kavramı ve açgözlü kurulumu Algoritmalar kursundaki Minimum Kapsayan Ağaç dersinde kuruldu; burada yeniden türetilmez. Burada ölçülen şey **protokolün kararı** ve o kararın paketlere ne yaptığıdır. ```text # ogretilen dokum, calistirilmamistir topoloji: a-b-c-d-e-f-g-h-a halkasi + b-f kirisi (8 dugum, 9 bag) kok: a bacak rolleri (kok a icin) b: kok bacagi -> a | atanmis -> c, f h: kok bacagi -> a | atanmis -> g c: kok bacagi -> b | atanmis -> d f: kok bacagi -> b | atanmis -> e d: kok bacagi -> c | d-e ENGELLI g: kok bacagi -> h | f-g ENGELLI protokol iletisi (anahtardan anahtara, veri degil) kok tanimlayicisi | koke maliyet | gonderen tanimlayici | bacak ``` Kök seçiminde tanımlayıcının küçüklüğü bir yetenek ölçüsü değildir; yalnızca bütün anahtarların aynı sonuca varmasını sağlayan bir sıralama kuralıdır. Kök nerede olursa olsun ağaç kurulur, ama ağacın **biçimi** köke bağlıdır ve yolların uzunluğu da öyle. ## Ölçümün Varsayımları - **AC22** — Topoloji ortak tanımın topolojisidir: sekiz anahtar, yedi bağdan bir halka (`a–b–c–d–e–f–g–h–a`) ve halkayı kesen `b–f` kirişi; toplam dokuz bağ. 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. - **AC23** — Kök `a`'dır ve ağaç kökten enine yürünerek kurulur: her anahtar köke en yakın bacağını tutar, kalan bağlar engellenir. En küçük kapsayan ağaç algoritması burada çalıştırılmaz; ağacın **sonucu** kullanılır. - **AC24** — Taşırma ölçümünde bir yayın çerçevesi kökten çıkar; her düğüm, çerçeveyi geldiği bacak dışındaki her bağa kopyalar. Durduran hiçbir düzenek yoktur çünkü çerçevede atlama sayacı yoktur. Ölçüm tur sınırıyla kesilir; kesilmesi çerçevenin durduğu anlamına gelmez. - **AC25** — Kırk kaynak–hedef çifti tek bir üreteçten, tek bir modülüsle çekilir; kaynağın hedefe eşit olduğu çekiliş atılır. Aynı kırk çift bütün rejimlerde kullanılır. - **AC26** — Kopan bağ `b–f` kirişidir. Kiriş halkanın iki yakasını kısa devre yaptığı için ağacın çoğu ondan geçer; koptuğunda çok sayıda anahtarın kararı değişmek zorundadır. - **AC27** — Beş rejim karşılaştırılır: ağaç kurulu ve kopma yok; bağ koptu ama ne ağaç ne tablo yenilendi; ağaç yenilendi ama tablolar eski; ağaç yenilendi ve tabloyu yalnız iki anahtar tazeledi; ağaç yenilendi ve bütün tablolar temizlendi. - **AC28** — Atlama sınırı 12'dir. Sınırı yakan ya da aynı bağdan ikinci kez geçen paket **döngü**, bir sonraki düğümü tabloda bulunmayan ya da artık komşu olmayan paket **kara delik** sayılır. - **AC29** — Kümenin çözünürlüğü kırk pakettir; ölçülebilen en küçük fark $1/40 = 0{,}025$. ## Ölçüm ```python """Kapsayan agac protokolunun karari: engellenen bag ve paketin kaderi. Agac, kokten enine yurunerek kurulur; en kucuk kapsayan agac algoritmasi Algoritmalar kursunda kuruldu ve burada yeniden turetilmez. """ 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")] KOPAN, KOK, ATLAMA_SINIRI = ("b", "f"), "a", 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 agac(baglar, kok=KOK): """Koke en yakin bacak tutulur, kalan bag engellenir.""" k, gorulen, sira, kalan = komsuluk(baglar), {kok}, [kok], [] while sira: yeni = [] for u in sira: for v in sorted(k[u]): if v not in gorulen: gorulen.add(v) kalan.append(tuple(sorted((u, v)))) yeni.append(v) sira = yeni return kalan 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): 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): sayim, adim = {"ulasti": 0, "dongu": 0, "kara delik": 0}, 0 for x, y in ciftler(): kader, a = ilet(x, y, tablolar, baglar) sayim[kader] += 1 adim += a return sayim, adim def kismi(eski, yeni, guncelleyen): """Yeni agaci yalniz bir kume duymustur; otekiler eskisini surdurur.""" return {(u, h): (yeni if u in guncelleyen else eski)[(u, h)] for (u, h) in eski if (u, h) in yeni} def tasir(baglar, kaynak, tur_siniri): """Yayin cercevesi: her dugum, geldigi bacak disindaki her baga kopyalar.""" k, dalga, kopya = komsuluk(baglar), [(kaynak, None)], 0 for _ in range(tur_siniri): yeni = [] for u, geldigi in dalga: for v in sorted(k[u]): if v != geldigi: kopya += 1 yeni.append((v, u)) dalga = yeni if not dalga: break return kopya, len(dalga) KOPUK = [b for b in BAGLAR if b != KOPAN] ESKI, YENI = agac(BAGLAR), agac(KOPUK) ESKI_KOPUK = [b for b in ESKI if b != KOPAN] print(f"bağ {len(BAGLAR)} | ağaç bağı {len(ESKI)} | eski ağacın engellediği " f"{[b for b in BAGLAR if tuple(sorted(b)) not in ESKI]}") print(f"kopan bağ {KOPAN} | yeni ağacın engellediği " f"{[b for b in KOPUK if tuple(sorted(b)) not in YENI]}") print() print(f"{'tur':>3s} {'halka kopya':>11s} {'ayakta':>6s} {'ağaç kopya':>10s} " f"{'ayakta':>6s}") for tur in (1, 2, 4, 6, 8, 10, 12): k1, a1 = tasir(BAGLAR, KOK, tur) k2, a2 = tasir(ESKI, KOK, tur) print(f"{tur:3d} {k1:11d} {a1:6d} {k2:10d} {a2:6d}") print() print(f"{'rejim':<32s} {'ulaştı':>6s} {'döngü':>6s} {'kara delik':>11s} " f"{'adım':>5s}") for ad, tab, bag in ( ("ağaç kurulu, kopma yok", kahin(ESKI), ESKI), ("bağ koptu, ağaç ve tablo eski", kahin(ESKI), ESKI_KOPUK), ("ağaç yeni, tablolar eski", kahin(ESKI), YENI), ("ağaç yeni, tablo iki anahtarda", kismi(kahin(ESKI), kahin(YENI), {"b", "f"}), YENI), ("ağaç yeni, tablolar temiz", kahin(YENI), YENI)): s, a = olc(tab, bag) print(f"{ad:<32s} {s['ulasti']:6d} {s['dongu']:6d} {s['kara delik']:11d} " f"{a:5d}") ``` ``` bağ 9 | ağaç bağı 7 | eski ağacın engellediği [('d', 'e'), ('f', 'g')] kopan bağ ('b', 'f') | yeni ağacın engellediği [('e', 'f')] tur halka kopya ayakta ağaç kopya ayakta 1 2 2 2 2 2 5 3 5 3 4 14 5 7 0 6 27 7 7 0 8 50 13 7 0 10 85 19 7 0 12 142 33 7 0 rejim ulaştı döngü kara delik adım ağaç kurulu, kopma yok 40 0 0 106 bağ koptu, ağaç ve tablo eski 21 0 19 70 ağaç yeni, tablolar eski 20 0 20 64 ağaç yeni, tablo iki anahtarda 25 10 5 100 ağaç yeni, tablolar temiz 40 0 0 129 ``` ## Engellemenin Karşılığı Üst tablo protokolün var olma nedenini veriyor. Dokuz bağlı halkada tek bir yayın çerçevesi dördüncü turda **14**, sekizinci turda **50**, on ikinci turda **142** kopya üretiyor ve o anda hâlâ **33** kopya yolda. Sayı büyümeyi sürdürüyor; ölçüm turu bitirdiği için duruyor, çerçeve durduğu için değil. Bir tek çerçeve, sekiz anahtarlı bir ağı tek başına doldurur. Ağaçta aynı çerçeve dördüncü turda **7** kopyada biter ve ayakta hiçbir kopya kalmaz. Yedi sayısı ağacın bağ sayısıdır ve tesadüf değildir: ağaçta her bağ tam bir kez, kökten uzağa doğru geçilir. **Taşırma bir ağaçta sonlu, bir çevrimde sonsuzdur** ve aradaki fark iki bağın engellenmesinden ibarettir. Bedel de aynı yerde durur. Dokuz bağın ikisi veri taşımaz; kablolar takılıdır, bacaklar ayaktadır, ama üzerlerinden çerçeve geçmez. Yedeklilik için çekilen kablo, yedeklilik ihtiyacı doğana kadar boş bekler. ## Engel Kalkana Kadar Alt tablo kirişin koptuğu andan yeni ağacın oturmasına kadar geçen süreyi beş adımda okuyor. **Ağaç kuruluyken** kırk paketin kırkı da ulaşıyor, **106** adım harcanıyor. Bu, engellemenin maliyetinin de göstergesidir: aynı kırk çift, bütün bağlar açık olsaydı daha kısa yollardan giderdi. Engelleme yolları uzatır ama hiçbir paketi kaybetmez. **Bağ koptuğunda ve kimse duymadığında** ulaşan **21**'e iner, **19** paket kara deliğe düşer. Adım **70**'e düşüyor — daha az adım, daha az iş değil, **erken ölüm** demektir. Kara deliğe düşen paket ilerlemeyi bırakır; harcamadığı adım, bir kazanç değil bir kayıptır. **Ağaç yeniden kurulup tablolar eski kaldığında** durum bir parça daha kötüdür: ulaşan **20**, kara delik **20**. Protokol topolojiyi düzeltmiştir, ama eşleştirme tabloları hâlâ eski ağacın bacaklarını göstermektedir. Yeni ağaç bir bağı açmış, bir başkasını engellemiştir; tablolar kapanmış bacağı gösterdiği sürece paket komşu olmayan bir yere yollanır ve orada biter. Bu, protokolün neden yalnız ağacı yeniden kurmakla yetinmediğinin gerekçesidir: topoloji değişimi bildirildiğinde tabloların **yaşı da kısaltılır**, böylece eski girdiler hızla düşer. **Tabloyu yalnız iki anahtar tazelediğinde** tablo ilk kez üçüncü kaderi üretiyor: **25** ulaşıyor, **5** kara deliğe düşüyor ve **10** paket **döngüye** giriyor. Adım **64**'ten **100**'e çıkıyor. İki anahtar yeni bacağı gösterirken komşuları eskisini gösterdiği için paket ileri gidip geri dönüyor ve atlama sınırını yakana kadar dolaşıyor. Buradan ortak tanımın ikinci iddiası okunur: **kısmî bilgi, hiç bilgiden daha pahalı bir arıza üretir.** Kimse duymadığında paket hemen ölüyordu; iki anahtar duyduğunda kara delik **20**'den **5**'e indi, ama **10** paket ölmek yerine dolaşmaya başladı ve adım **64**'ten **100**'e çıktı. Kaybedilen paket sayısı azaldı, harcanan iş arttı ve arıza **görünmez** hâle geldi — dolaşan paket bir hata değil, bir tıkanıklık gibi görünür. Üçüncü iddia da aynı satırdan okunur ve yapısaldır. **Hiçbir anahtar tek başına bir paketi döngüye sokamaz.** Döngü için biri paketi ileri, öbürü geri gönderen **en az iki tablo** gerekir; ilk üç rejimde bütün tablolar aynı ağacı gösterdiği için, yanlış olsalar bile döngü doğmadı. Döngü, tablonun yanlışlığından değil **tabloların anlaşmazlığından** doğar. **Bütün tablolar temizlendiğinde** kırk paketin kırkı yeniden ulaşıyor ve adım **129**'a çıkıyor. Kiriş gittiği için yollar uzamıştır; ama **hiçbir paket kaybolmaz.** Yakınsamanın tanımı budur: pahalı ama doğru. ## Özet - Bağlantı katmanı çerçevesinde atlama sayacı yoktur; çevrim içeren bir topolojide taşırılan çerçeve yaşlanarak ölmez, her turda çoğalır ve tabloları kararsız bırakır. - Kapsayan ağaç protokolü bir kök seçer, her anahtarın köke giden bacağını tutar ve kalan bağları engeller; halkada tek bir yayın çerçevesi on ikinci turda **142** kopyaya çıkarken ağaçta **7** kopyada biter. - Engellemenin bedeli boş bekleyen kablo ve uzayan yoldur: ağaçta kırk paket **106** adımda ulaşır, kopma sonrası yeni ağaçta **129** adımda — ama kırkı da ulaşır. - Kopmayı kimse duymadığında **19**, ağaç yenilenip tablolar eski kaldığında **20** paket kara deliğe düşer; adımın **70** ve **64**'e inmesi kazanç değil erken ölümdür. - Tabloyu yalnız iki anahtar tazelediğinde kara delik **5**'e iner ama **10** paket döngüye girer ve adım **100**'e çıkar: kısmî bilgi, hiç bilgiden pahalı bir arıza üretir. - Döngü tek bir tablonun yapabileceği bir şey değildir; en az iki tablonun anlaşmazlığıdır. ## Sonraki Adım Kapsayan ağacın yedekliliğe verdiği yanıt tek yönlüdür: ikinci bağ vardır, ama beklemektedir. Ölçümde iki bağ engellendi ve o iki bağın taşıma kapasitesi kopma anına kadar kullanılmadı. Buradan bir soru doğar: iki bağ aynı anda kullanılabilir mi? Çevrim yasağı bunu yasaklıyor gibi görünür, çünkü iki bağ iki yol demektir ve iki yol taşırılan çerçeveyi geri getirir. Sonraki ders bu yasağın etrafından dolaşan düzeneği ölçer: birden çok bağı **tek bir mantıksal bağ** sayan bir toplama, dağıtım kararının aynı akışı neden bölmediği, ve bir bacak düştüğünde kaç akışın taşındığı.