Kaplama Ağları

Önceki ders kararı kenara taşıdı, ama yol hâlâ ağın kendi bağlarından geçiyordu: b’den c’ye giden etiketli paket gerçekten b–c bağını kullandı. Etiket yolu adlandırıyordu ve adlandırdığı yol fizikseldi.

Bu dersin sorusu şudur: iki düğüm arasındaki bağ fiziksel bir bağ değil de, başka bir ağın üzerinden kurulmuş mantıksal bir bağ olsaydı ne olurdu? O zaman ortada tek bir tablo değil iki tablo olur, ikisi ayrı ayrı yakınsar, ve paketin kaderi ikisinin birden anlaşmasına bağlanır. Kursun ölçü ekseninin en uç biçimi budur.

Kaplama ve Alt Ağ Düzeni

Kaplama ağı (overlay network), tünellerle kurulan mantıksal bir topolojidir. Kaplamanın bir bağı, iki düğüm arasında doğrudan bir kablo olduğu anlamına gelmez; o iki düğümün birbirini komşu sayması anlamına gelir. Kaplamanın üzerinde durduğu gerçek bağ kümesine alt ağ düzeni (underlay) denir. (alt ağ tek başına adres öbeğini bölen kavram için ayrılmıştır; buradaki kavramın adı alt ağ düzenidir ve ikisi karıştırılmaz.)

Konteynerler kursu konteyner ağlarının kaplamasını kurmuştu; o yordam burada tekrarlanmaz. Burada kaplama bir mantıksal topoloji olarak ölçülür: kendi tablosu, kendi komşuluğu, kendi yakınsaması ve kendi atlama sayacı vardır.

# ogretilen dokum, calistirilmamistir

kaplama bağı   alt ağ düzenindeki yol   anlamı
  a-c            a-b-c                    a ile c kaplamada komşudur
  a-e            a-b-f-e                  a ile e kaplamada komşudur
  c-f            c-b-f                    c ile f kaplamada komşudur

tünellenmiş paket
  dış başlık   kaynak a   hedef c    <- alt ağ düzeni yalnız bunu okur
  iç başlık    kaynak a   hedef g    <- kaplama yalnız bunu okur
  yük          ...

a düğümünün iki tablosu
  kaplama tablosu              alt ağ düzeni tablosu
  hedef  bir sonraki           hedef  bir sonraki
  g      e                     c      b
  d      d                     e      b

Sağdaki iki tablo dersin tamamıdır. a düğümü kaplamada g hedefi için e’yi gösterir; e kaplamada komşudur ama alt ağ düzeninde üç adım uzaktadır. Paket a’dan çıkarken alt ağ düzeni tablosuna göre b’ye gider ve kaplama bunu hiç görmez. İki tablo aynı cihazın içindedir ve birbirini okumaz.

Bunun doğrudan bir sonucu vardır: bir kaplama adımı, alt ağ düzeninde birkaç adımdır. İki katmanın sayaçları ayrıdır ve ayrı sayılmak zorundadır.

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

• YL81 — Alt ağ düzeni kurs boyunca aynıdır: sekiz düğüm, a–b–c–d–e–f–g–h–a halkası ve halkayı kesen b–f kirişi.
• YL82 — Kaplama dokuz tünelden kurulur ve tünellerin hiçbiri alt ağ düzeninin bir bağıyla aynı değildir; her tünel alt ağ düzeninde iki ile dört adım arasında bir yola karşılık gelir.
• YL83 — İki katmanın tabloları ayrı hesaplanır ve birbirini görmez. Kural ikisinde de aynıdır: her hedefe giden en kısa yolun ilk adımı. Kâhin değiştirilmez.
• YL84 — Her katmanın kendi atlama sayacı vardır ve ikisinin sınırı 12’dir. Bir kaplama adımı içinde harcanan alt ağ düzeni adımları kaplama sayacına eklenmez.
• YL85 — Bir kaplama adımı ancak tünel alt ağ düzeninde teslim edildiyse atılmış sayılır; tünel teslim edilemezse paketin kaderi tünelin kaderidir.
• YL86 — Son iki rejimde kalkan kaplama bağı a–c tünelidir. Dördüncüsünde kalkışı yalnız a ve c duyar; öteki yedi düğüm eski kaplama tablosunu sürdürür.
• YL87 — Son iki rejimde alt ağ düzeninin tablosu kâhinin kendisidir: alt ağ düzeninde tek bir yanlış karar yoktur ve tek bir tünel teslim edilemez değildir.
• YL88 — Kırk kaynak–hedef çifti kurs çekirdeğinin üretecinden gelir, her çıkış ayrı bir pakettir ve kümenin çözünürlüğü 1/40 = 0,025’tir.

Ölçüm

"""Kaplama agi: kaplamanin tablosu ile alt ag duzeninin tablosu anlasmazsa."""
TOHUM = 20260810
DUGUMLER = "abcdefgh"
BAGLAR = [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e"), ("e", "f"),
          ("f", "g"), ("g", "h"), ("h", "a"), ("b", "f")]
KOPUK = [b for b in BAGLAR if b != ("b", "f")]
KAPLAMA = [("a", "c"), ("a", "d"), ("a", "e"), ("b", "d"), ("b", "g"),
           ("c", "f"), ("d", "h"), ("e", "g"), ("f", "h")]
ATLAMA_SINIRI = 12


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

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


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 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."""
    kom, t = komsuluk(baglar), {}
    for kaynak in DUGUMLER:
        onceki, sira, gorulen = {}, [kaynak], {kaynak}
        while sira:
            yeni = []
            for u in sira:
                for v in sorted(kom[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]
            t[(kaynak, hedef)] = adim
    return t


def ilet(kaynak, hedef, t, baglar):
    """Tek katmanda yurutur; kaderi ve attigi adimi dondurur."""
    kom, u, gecilen, atlama = komsuluk(baglar), kaynak, [], 0
    while u != hedef:
        if atlama >= ATLAMA_SINIRI:
            return "dongu", atlama
        s = t.get((u, hedef))
        if s is None or s not in kom[u]:
            return "kara delik", atlama
        if (u, s) in gecilen:
            return "dongu", atlama
        gecilen.append((u, s))
        u, atlama = s, atlama + 1
    return "ulasti", atlama


def kaplama_ilet(kaynak, hedef, ust, ust_bag, alt, alt_bag):
    """Her kaplama adimi bir tuneldir ve alt agda ayrica yurutulur."""
    kom, u, gecilen, ust_adim, alt_adim = komsuluk(ust_bag), kaynak, [], 0, 0
    while u != hedef:
        if ust_adim >= ATLAMA_SINIRI:
            return "kaplama dongusu", ust_adim, alt_adim
        s = ust.get((u, hedef))
        if s is None or s not in kom[u]:
            return "kaplama kara deligi", ust_adim, alt_adim
        if (u, s) in gecilen:
            return "kaplama dongusu", ust_adim, alt_adim
        kader, a = ilet(u, s, alt, alt_bag)
        alt_adim += a
        if kader != "ulasti":
            return "tunel " + kader, ust_adim, alt_adim
        gecilen.append((u, s))
        u, ust_adim = s, ust_adim + 1
    return "ulasti", ust_adim, alt_adim


def kismi(eski, yeni, duyan):
    """Kaplama bagininin kalktigini yalniz bir kume duymustur."""
    return {(u, h): (yeni if u in duyan else eski)[(u, h)]
            for (u, h) in eski if (u, h) in yeni}


def olc(ust, ust_bag, alt, alt_bag):
    sayim = {"ulasti": 0, "kaplama dongusu": 0, "kaplama kara deligi": 0,
             "tunel kara delik": 0, "tunel dongu": 0}
    ua = aa = 0
    for x, y in ciftler():
        kader, u_, a_ = kaplama_ilet(x, y, ust, ust_bag, alt, alt_bag)
        sayim[kader] += 1
        ua += u_
        aa += a_
    return sayim, ua, aa


UST, ALT, ALT_YENI = kahin(KAPLAMA), kahin(BAGLAR), kahin(KOPUK)
EKSIK = [b for b in KAPLAMA if b != ("a", "c")]
UST_YENI = kahin(EKSIK)
REJIM = (("iki katman da yakınsamış", UST, KAPLAMA, ALT, BAGLAR),
         ("alt ağ düzeni koptu, yakınsadı", UST, KAPLAMA, ALT_YENI, KOPUK),
         ("alt ağ düzeni koptu, tablo eski", UST, KAPLAMA, ALT, KOPUK),
         ("tünel kalktı, iki uç duydu",
          kismi(UST, UST_YENI, {"a", "c"}), EKSIK, ALT, BAGLAR),
         ("tünel kalktı, hepsi duydu", UST_YENI, EKSIK, ALT, BAGLAR),
         ("iki katman birden eski",
          kismi(UST, UST_YENI, {"a", "c"}), EKSIK, ALT, KOPUK))
OLCUM = [(ad, olc(ust, ubag, alt, abag)) for ad, ust, ubag, alt, abag in REJIM]

print(f"{'rejim':<32s} {'ulaştı':>7s} {'kaplama döngüsü':>16s} "
      f"{'tünel kara deliği':>18s}")
for ad, (s, ua, aa) in OLCUM:
    print(f"{ad:<32s} {s['ulasti']:7d} {s['kaplama dongusu']:16d} "
          f"{s['tunel kara delik']:18d}")

print()
print(f"{'rejim':<32s} {'kaplama adımı':>14s} {'alt ağ düzeni adımı':>20s}")
for ad, (s, ua, aa) in OLCUM:
    print(f"{ad:<32s} {ua:14d} {aa:20d}")

print()
print("tünelin alt ağ düzenindeki uzunluğu")
print(f"{'tünel':>6s} {'yakınsamış':>11s} {'kopma sonrası':>14s} {'eski tabloyla':>14s}")
for x, y in KAPLAMA:
    _, a0 = ilet(x, y, ALT, BAGLAR)
    k1, a1 = ilet(x, y, ALT_YENI, KOPUK)
    k2, a2 = ilet(x, y, ALT, KOPUK)
    print(f"{x + '-' + y:>6s} {a0:11d} {a1:14d} "
          f"{('kara delik' if k2 != 'ulasti' else str(a2)):>14s}")

rejim                             ulaştı  kaplama döngüsü  tünel kara deliği
iki katman da yakınsamış              40                0                  0
alt ağ düzeni koptu, yakınsadı        40                0                  0
alt ağ düzeni koptu, tablo eski       19                0                 21
tünel kalktı, iki uç duydu            28               12                  0
tünel kalktı, hepsi duydu             40                0                  0
iki katman birden eski                17                3                 20

rejim                             kaplama adımı  alt ağ düzeni adımı
iki katman da yakınsamış                     74                  188
alt ağ düzeni koptu, yakınsadı               74                  211
alt ağ düzeni koptu, tablo eski              40                  124
tünel kalktı, iki uç duydu                   77                  205
tünel kalktı, hepsi duydu                    97                  264
iki katman birden eski                       41                  134

tünelin alt ağ düzenindeki uzunluğu
 tünel  yakınsamış  kopma sonrası  eski tabloyla
   a-c           2              2              2
   a-d           3              3              3
   a-e           3              4     kara delik
   b-d           2              2              2
   b-g           2              3     kara delik
   c-f           2              3     kara delik
   d-h           4              4              4
   e-g           2              2              2
   f-h           2              2              2

Kaplama Kopmayı Görmez

İlk iki rejim kirişin kopmasını ölçüyor. Kırk paketin kırkı iki rejimde de ulaşıyor ve kaplama adımı ikisinde de 74. Kaplamanın tablosunda tek bir satır değişmedi; kaplama için hiçbir şey olmadı.

Alt ağ düzeni adımı 188’den 211’e çıkıyor. Üçüncü tablo yirmi üç fazladan adımın nereden geldiğini söylüyor: a-e tüneli üç adımdan dörde, b-g ve c-f tünelleri ikişer adımdan üçer adıma çıkıyor. Kirişi kullanan tüneller bunlardı; kiriş gidince alt ağ düzeni onları halkanın öteki yakasından kurdu.

Bu, kaplamanın en çok reklam edilen özelliğidir ve ölçüm onu doğruluyor: alt ağ düzeni kendini onardığı sürece kaplama kopmayı hiç görmez. Ama ölçüm bedeli de veriyor. Kaplamayı izleyen bir gözlemci yirmi üç fazladan adımı göremez, çünkü kendi sayacında hiçbir şey değişmemiştir. Katman, arızayı gizlerken maliyeti de gizler.

Doğru Tablo, Ölü Paket

Üçüncü rejim aynı kopmayı alt ağ düzeni yakınsamadan ölçüyor. Kaplamanın tablosu yine değişmedi, yine doğrudur; kırk paketin yalnız 19’u ulaşıyor ve 21’i tünel kara deliğine düşüyor.

Üçüncü tablonun son sütunu üç tüneli adlandırıyor: a-e, b-g ve c-f eski alt ağ düzeni tablosuyla teslim edilemiyor. Kaplama bu üç bağı hâlâ ayakta sayıyor ve paketleri onlara yolluyor.

İki katmanlı anlaşmazlığın ilk biçimi budur: üstteki tablo kusursuzdur ve paket ölür. Kaplamanın kendi ölçüsüne bakan bir denetim hiçbir arıza bildirmez — kaplama komşulukları tam, kaplama yolları geçerli, kaplama adımı beklenenden bile düşük (40, çünkü ölen paket adım harcamayı bırakır). Arıza bir katman aşağıdadır ve yukarısı ona bakamaz.

Alt Ağ Kusursuz, Kaplama Döngüde

Dördüncü rejim anlaşmazlığı ters çeviriyor. Bu rejimde alt ağ düzeninin tablosu kâhinin kendisidir: alt ağ düzeninde tek bir yanlış karar yoktur ve dokuz tünelin dokuzu da teslim edilebilir. Değişen tek şey kaplamadadır — a-c tüneli kalkmıştır ve bunu yalnız a ile c duymuştur.

Sonuç: kırk paketin 28‘i ulaşıyor, 12‘si kaplama döngüsüne giriyor. Kara delik sıfır. Beşinci rejim aynı tünel kalkışını herkes duyduğunda ölçüyor: 40 ulaşıyor, kaplama adımı 97’ye, alt ağ düzeni adımı 264’e çıkıyor.

Kursun ikinci iddiası burada bir katman yukarıda yeniden ödeniyor. Kısmî bilgi, tam bilgisizlikten pahalı bir arıza üretir: herkes duyduğunda kırk paket ulaşıyor, yalnız iki uç duyduğunda on iki paket ağda dolaşıyor. Ve üçüncü iddia da ikinci kez ödeniyor: on iki paketin hiçbirini tek bir tablo döngüye sokmadı. Döngü, iki kaplama tablosunun anlaşmazlığıdır — a tünelin kalktığını bilir, d bilmez ve paketi geri gönderir.

En keskin nokta şudur: alt ağ düzeni bu döngüyü göremez. Alt ağ düzeninin gördüğü şey, her biri ayrı ayrı geçerli olan tünel teslimleridir. a’dan d’ye giden tünel teslim edildi, d’den a’ya giden tünel de teslim edildi; ikisi de doğru. Döngü ancak iki teslimi yan yana koyan bir gözden görünür ve alt ağ düzeninde öyle bir göz yoktur.

İki Katman Birden

Altıncı rejim iki anlaşmazlığı üst üste koyuyor: a-c tüneli kalkmış ve bunu yalnız iki uç duymuş, aynı anda kiriş kopmuş ve alt ağ düzeninin tabloları eskimiş. Kırk paketin 17’si ulaşıyor — tek başına alt ağ düzeni arızasından (19) da, tek başına kaplama arızasından (28) da az.

Asıl gözlem kaderlerin dağılımındadır. Kaplama döngüsü 12’den 3’e, tünel kara deliği 21’den 20’ye iniyor. Döngüye girecek paketlerin çoğu daha ilk turda bir tünel kara deliğine düşüp ölüyor: alttaki arıza üsttekini gizliyor. Kaplamayı izleyen bir göz döngü sayısının düştüğünü görür ve bunu bir iyileşme sanabilir. Adım sayıları da aynı yöne işaret ediyor — kaplama 77’den 41’e, alt ağ düzeni 205’ten 134’e. Ağın en kötü durumu, bütün sayaçların en sakin göründüğü durumdur.

İki Sayaç, İki Tanı

Sayaçların ayrılığı tanıyı da ayırıyor. Döngüye giren rejimde kaplama 77 adım, alt ağ düzeni 205 adım harcıyor: kaplamadaki her adım alt ağ düzeninde ortalama iki buçuk adımın üzerindedir ve kaplama katmanındaki bir döngü alt ağ düzeninde bu katsayıyla büyür.

İki gözlemci iki ayrı şey görür. Kaplamayı izleyen sayaç döngüyü döngü olarak görür: paketler dolaşıyor, atlama sınırı yanıyor. Alt ağ düzenini izleyen sayaç yalnız yük artışı görür: bağlar üzerinde beklenenden çok paket var, hiçbir teslim başarısız değil. Ortak tanımın “döngü tıkanıklık gibi görünür” saptaması, iki katmanlı bir ağda hangi katmandan bakıldığına göre değişen bir saptamadır.

Bu, kaplamayı kullanmamak için bir gerekçe değildir; kaplamanın iki katmanı birden izlemeden kullanılamayacağı için bir gerekçedir. Tek katmanlı bir ağda tablo ile bağ kümesi aynı yerde durur ve arıza ikisinde birden görünür. Kaplamada ölçülen altı rejimin üçünde paket ölür ve üçünün belirtisi başkadır: biri yalnız kara delik, biri yalnız döngü, biri ikisi birden.

Özet

• Kaplama ağı tünellerle kurulan mantıksal bir topolojidir; kaplamanın bir bağı komşuluk bildirir, kablo bildirmez. Altındaki gerçek bağ kümesinin adı alt ağ düzenidir ve iki katmanın tabloları aynı cihazda dursa da birbirini okumaz.
• Alt ağ düzeni kendini onardığında kaplama kopmayı hiç görmez: kaplama adımı 74‘te kalır, alt ağ düzeni adımı **188’den 211’e** çıkar. Katman arızayı gizlerken maliyeti de gizler.
• Alt ağ düzeni yakınsamadan kaplama doğru tablosuyla çalışırsa 21 paket tünel kara deliğine düşer; kirişi kullanan a-e, b-g ve c-f tünelleri teslim edilemez. Üstteki tablo kusursuzdur ve paket ölür.
• Alt ağ düzeninde tek bir yanlış karar yokken kaplama tablolarının kısmî bilgisi 12 paketi döngüye sokar; herkes duyduğunda kırk paketin kırkı ulaşır. Döngü iki kaplama tablosunun anlaşmazlığıdır ve alt ağ düzeni onu göremez.
• Kaplamadaki 77 adım alt ağ düzeninde 205 adımdır; kaplamayı izleyen sayaç döngü görür, alt ağ düzenini izleyen sayaç yalnız yük artışı görür.
• İki katman birden eskidiğinde ulaşan paket 17’ye iner ama döngü 3’e düşer: alttaki kara delik üstteki döngüyü gizler ve en kötü durum sayaçlarda en sakin görünür.

Sonraki Adım

Buraya kadar bütün ölçümlerde topoloji verilmişti. Sekiz düğüm, dokuz bağ ve halkayı kesen bir kiriş baştan konmuştu; ölçülen şey hep ona verilen yanıttı — hangi tablo kaç turda yakınsıyor, hangi politika yolu ne kadar uzatıyor, hangi katman kopmayı görüyor. Topolojinin kendisi hiç sorgulanmadı. Oysa topoloji de bir seçimdir: hangi düğümün hangi düğüme bağlanacağı, kaç yedek yol bırakılacağı, bir kopmanın kaç düğümün tablosunu değiştireceği yazılırken kararlaştırılır. Sonraki konu bu seçimi ölçer ve seçimin doğrudan yakınsama turuna dokunduğunu gösterir.