Kapsayan Ağaç Protokolü

Ö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.

# 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

"""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ığı.