Adres ve Ad Planlaması

Önceki üç ders topolojiyi bir çizge olarak ölçtü ve tablo satırı her ölçümde bir sütun olarak göründü: üç katmanlı düzende 272, dört omurgalı düzende 468. Her seferinde satır sayısını belirleyen şey topolojiydi.

Satır sayısını belirleyen ikinci bir şey daha vardır ve topolojiyle hiç ilgisi yoktur: hedeflerin nasıl adlandırıldığı. Aynı cihazlarda, aynı bağlarla, aynı sayıda alt ağla iki ayrı adres planı aynı tabloyu bambaşka sayıda satırla doldurur. Bu dersin sorusu, planın tabloya ne yaptığıdır.

Planın Tek Koşulu

Bir yönlendirme tablosu, komşu adresleri tek bir satırda özetleyebilir. Buna yol özetleme denir ve tek bir koşulu vardır: özetlenen aralıktaki bütün adresler aynı bir sonraki düğümden ulaşılabilir olmalıdır. Aralık hizalı olmalı ve içine başka bir yöne giden bir adres düşmemelidir.

Alt ağ maskesi, hizalama ve blok adımı hesabı Alt Ağlara Bölme ve Değişken Uzunluklu Alt Ağlar derslerinde kuruldu; burada tekrarlanmaz. Ölçülen şey hesabın kendisi değil, hesabın tablo satırına etkisidir.

Bir plan bu koşulu ya sağlar ya sağlamaz. Sağlayan plan adres uzayını topolojiyle aynı biçimde böler: her bloğa hizalı bir aralık, her aralığın içinde her yaprağa hizalı bir alt aralık, ve her ikisinde büyüme payı. Sağlamayan plan adresleri tek bir havuzdan yaratılma sırasına göre dağıtır.

# ogretilen dokum , calistirilmamistir

hizalı plan — 64 yuvalık uzay, dört blok, üçü kullanılıyor
  blok 0   yuva  0-15      y1: 0-3   y2: 4-7   y3: 8-11   12-15 büyüme payı
  blok 1   yuva 16-31      blok 2   yuva 32-47      blok 3   48-63 ayrılmış
  c1'in tablosu:  0-15 -> d1     16-31 -> d3     32-47 -> d5

büyüme sırasına göre plan — tek havuz, yaratılma sırası
  yuva 0 -> y1   yuva 1 -> y2   yuva 2 -> y3   yuva 3 -> y4   ...
  ardışık iki yuva ayrı bloklara düşer; özetlenecek aralık doğmaz

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

• TP27 — Topoloji birinci dersin üç katmanlı düzenidir: dokuz yaprak, üç blok, altı dağıtım ve iki çekirdek düğümü. Topoloji iki planda da aynıdır; değişen tek şey plandır.
• TP28 — Adres uzayı 64 yuvadır ve yuva bir alt ağı temsil eder. Hizalı planda her blok 16, her yaprak 4 yuva alır; yaprak başına k yuva kullanılır, kalanı büyüme payıdır.
• TP29 — Satır sayısı, bir düğümün tablosunu kaplayan en az sayıda hizalı önek olarak sayılır. Boş yuva bir öneğin içine düşebilir; başka yöne giden bir yuva düşemez.
• TP30 — Kâhin topolojiyi biz kurduğumuz için bilinir ve her düğüm için her yaprağa giden en kısa yolun ilk adımıdır. Paket en uzun önek eşlemeyle yürütülür.
• TP31 — Ad bölgesi sayısı, adlar plandaki sırayla dizildiğinde blok değiştirmeden sayılabilen en az aralık sayısıdır. Ad çözümlemenin kendisi Alan Adı Sistemi dersinin konusudur ve burada tekrarlanmaz.
• TP32 — Kırk paketlik kümede ölçülebilen en küçük fark 1/40 = 0,025’tir.

Ölçüm

"""Adres ve ad plani: planin tablo satir sayisina etkisi.

Bolum 1 - hizali plan ile buyume sirasina gore plan, yaprak basina 1-4 alt ag.
Bolum 2 - ozetin sahip olmadigi adresi duyurmasi.
"""
TOHUM = 20260810
YUVA = 64
YAPRAK = [f"y{i}" for i in range(1, 10)]
BLOK = {0: YAPRAK[0:3], 1: YAPRAK[3:6], 2: YAPRAK[6:9]}
DAGITIM = {"d1": 0, "d2": 0, "d3": 1, "d4": 1, "d5": 2, "d6": 2}
DUGUMLER = YAPRAK + sorted(DAGITIM) + ["c1", "c2"]
BAGLAR = ([(y, d) for d, b in DAGITIM.items() for y in BLOK[b]]
          + [(d, c) for d in sorted(DAGITIM) 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():
    k = {u: set() for u in DUGUMLER}
    for x, y in BAGLAR:
        k[x].add(y)
        k[y].add(x)
    return k


def kahin():
    """Her dugum icin her hedefe giden en kisa yolun ilk adimi."""
    k, tablo = komsuluk(), {}
    for kaynak in DUGUMLER:
        onceki, sira = {}, [kaynak]
        while sira:
            yeni = []
            for u in sira:
                for v in sorted(k[u]):
                    if v != kaynak and v not in onceki:
                        onceki[v] = u
                        yeni.append(v)
            sira = yeni
        for h in onceki:
            adim = h
            while onceki[adim] != kaynak:
                adim = onceki[adim]
            tablo[(kaynak, h)] = adim
    return tablo


def hizali(k):
    """Her blok 16, her yaprak 4 yuva; k tanesi dolu, kalani buyume payi."""
    return {16 * b + 4 * j + i: y for b, yapraklar in BLOK.items()
            for j, y in enumerate(yapraklar) for i in range(k)}


def buyume_sirasi(k):
    """Alt aglar yaratilma sirasina gore tek havuzdan verilir."""
    return {n: YAPRAK[n % 9] for n in range(9 * k)}


def onekler(u, plan, bas=0, boy=YUVA):
    """u dugumunun tablosunu kaplayan en az sayida hizali onek."""
    ic = {("yerel" if y == u else T[(u, y)])
          for yuva, y in plan.items() if bas <= yuva < bas + boy}
    if len(ic) < 2:
        return [(bas, boy, ic.pop())] if ic else []
    return (onekler(u, plan, bas, boy // 2)
            + onekler(u, plan, bas + boy // 2, boy // 2))


def ilet(kaynak, yuva, onek, komsu, gercek):
    """En uzun onek eslemeyle yurutur; varis gercek eve bakilarak sinanir."""
    u, atlama = kaynak, 0
    while atlama < 12:
        aday = [o for o in onek[u] if o[0] <= yuva < o[0] + o[1]]
        if not aday:
            return "kara delik"
        v = min(aday, key=lambda o: o[1])[2]
        if v == "yerel":
            return "ulasti" if gercek.get(yuva) == u else "kara delik"
        if v not in komsu[u]:
            return "kara delik"
        u, atlama = v, atlama + 1
    return "dongu"


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 bolge(plan):
    """Ad dizisinde blok degistirmeden sayilabilen en az bolge sayisi."""
    onceki, say = None, 0
    for _, y in sorted(plan.items()):
        b = next(i for i, ys in BLOK.items() if y in ys)
        if b != onceki:
            say, onceki = say + 1, b
    return say


def olc(plan, hedef=None, gercek=None):
    """Satirlar plandan, hedefler adres planindan, varis gercek evden."""
    hedef, gercek = hedef or plan, gercek or plan
    komsu = komsuluk()
    onek = {u: onekler(u, plan) for u in DUGUMLER}
    ilk, sayim = {}, {"ulasti": 0, "dongu": 0, "kara delik": 0}
    for yuva, y in sorted(hedef.items()):
        ilk.setdefault(y, yuva)
    for x, y in ciftler():
        sayim[ilet(x, ilk[y], onek, komsu, gercek)] += 1
    return sum(len(o) for o in onek.values()), len(onek["c1"]), sayim


T = kahin()
print(f"{'plan':<14s} {'yaprak başına':>13s} {'alt ağ':>6s} "
      f"{'toplam satır':>12s} {'c1':>3s} {'ad bölgesi':>10s} {'ulaştı':>6s}")
for ad, kur in (("hizalı", hizali), ("büyüme sırası", buyume_sirasi)):
    for k in (1, 2, 3, 4):
        plan = kur(k)
        satir, c1, s = olc(plan)
        print(f"{ad:<14s} {k:13d} {len(plan):6d} {satir:12d} {c1:3d} "
              f"{bolge(plan):10d} {s['ulasti']:6d}")

print()
ev = hizali(4)
tasinan = {yuva: ("y1" if y == "y9" else y) for yuva, y in ev.items()}
print(f"{'durum':<32s} {'toplam satır':>12s} {'c1':>3s} {'ulaştı':>6s} "
      f"{'kara delik':>10s}")
for ad, plan, ger in (("plan yerinde", ev, None),
                      ("taşındı, özet güncellenmedi", ev, tasinan),
                      ("taşındı, ayrı satır eklendi", tasinan, tasinan)):
    satir, c1, s = olc(plan, ev, ger)
    print(f"{ad:<32s} {satir:12d} {c1:3d} {s['ulasti']:6d} "
          f"{s['kara delik']:10d}")

plan           yaprak başına alt ağ toplam satır  c1 ad bölgesi ulaştı
hizalı                     1      9           73   3          3     40
hizalı                     2     18           73   3          3     40
hizalı                     3     27           73   3          3     40
hizalı                     4     36           73   3          3     40
büyüme sırası              1      9           90   6          3     40
büyüme sırası              2     18          171  12          6     40
büyüme sırası              3     27          249  17          9     40
büyüme sırası              4     36          335  24         12     40

durum                            toplam satır  c1 ulaştı kara delik
plan yerinde                               73   3     40          0
taşındı, özet güncellenmedi                73   3     38          2
taşındı, ayrı satır eklendi                76   4     40          0

Satır Sayısı Alt Ağ Sayısından Bağımsız Olabilir

Üst tablonun ilk dört satırı dersin tamamıdır. Hizalı planda alt ağ sayısı 9’dan 36’ya çıkarken toplam tablo satırı 73’te kalıyor. Dört katına çıkan bir ağ, tablosuna tek bir satır eklemiyor. Çekirdeğin tablosu 3 satırda duruyor: blok başına bir önek.

Alt dört satır aynı topolojiyi büyüme sırasına göre dağıtılmış adreslerle gösteriyor. Toplam satır 90, 171, 249, 335 diye tırmanıyor — alt ağ sayısıyla doğrusal. Otuz altı alt ağda fark 73’e karşı 335, yani 4,6 kat. Çekirdeğin tablosu 3 yerine 24 satır tutuyor.

Aradaki farkın kaynağı tek bir koşuldur. Hizalı planda bir bloğun bütün adresleri aynı bir sonraki düğümden ulaşılır, bu yüzden tek önek hepsini kaplar. Büyüme sırasına göre dağıtılan planda ardışık iki adres ayrı bloklara düşer; kaplanabilecek hiçbir aralık kalmaz ve tablo adres başına bir satıra iner.

ad bölgesi sütunu aynı hesabı adlarda tekrarlıyor. Hizalı planda adlar plandaki sırayla dizildiğinde 3 aralık çıkıyor — blok başına bir bölge. Büyüme sırasına göre dizilen adlarda sayı 3, 6, 9, 12 diye büyüyor. Ad planı ayrı bir tasarım değildir; adres planının aynı sorusudur ve aynı hesapla ölçülür.

Bir şey değişmiyor: ulaştı sütunu sekiz satırın sekizinde de 40. Plan paketi kaybettirmez, yalnız tabloyu büyütür. Planın bedeli gecikmede değil, taşınan durumdadır.

Özetin Sahip Olmadığı Adres

Alt tablo özetin tek zayıf noktasını ölçüyor. y9’a bağlı ağlar başka bir yaprağa taşınmış ve adresleri değişmemişse tablolar hiç değişmez — toplam satır yine 73, çekirdek yine 3. Ama kırk paketin 2’si kara deliğe düşer.

Sebep şudur: çekirdeğin 32-47 -> d5 satırı artık sahip olmadığı bir adresi duyuruyor. Özet, kapsadığı her adresin o yönde olduğunu söyler; taşınan ağ o yönde değildir. Özet yanlış değil, fazla kapsayıcıdır — ve fazla kapsayan bir doğru, bir yanlıştır.

Onarım son satırdadır. Taşınan ağ için ayrı ve daha dar bir satır eklenirse kırk paketin kırkı ulaşır; bedeli toplam 73’ten 76’ya, çekirdekte 3’ten 4’e çıkan satırdır. Üç satır küçük görünür, ama kural bellidir: her istisna bir satırdır ve istisnalar birikir. Plan, tabloyu büyümekten koruyan tek şeydir; korumayı sürdürmenin yolu ise taşınan ağı yeniden numaralandırmaktır.

Özet

• Yol özetlemenin tek koşulu, özetlenen aralıktaki bütün adreslerin aynı bir sonraki düğümden ulaşılabilir olmasıdır; plan bu koşulu ya sağlar ya sağlamaz.
• Hizalı planda alt ağ sayısı 9’dan 36’ya çıkarken toplam satır 73’te, çekirdeğin tablosu 3’te kalır.
• Büyüme sırasına göre dağıtılan planda aynı topoloji 90, 171, 249, 335 satır tutar; otuz altı alt ağda fark 4,6 kattır.
• Ad planı ayrı bir tasarım değildir: ad bölgesi sayısı hizalı planda 3’te kalır, büyüme sırasına göre dizilen adlarda 3’ten 12’ye çıkar.
• Taşınan tek bir ağ özeti sahip olmadığı adresi duyurur hâle getirir ve 2 paket kara deliğe düşer; ayrı satır eklemek onarır ama satırı 73’ten 76’ya çıkarır.

Kurs Kapanışı

Kurs tek bir soruyla açıldı: karar iletide yazandan değil cihazın kendi tablosundan okunuyorsa, ve o tablo paylaşılan bir gerçeğin kopyasıysa, kopyalar anlaşmadığı sürede pakete ne olur? On yedi ders bu soruyu on yedi ayrı anlaşmazlıkla sordu ve hepsinde aynı üç kaderi saydı.

ders	ölçülen anlaşmazlık	ulaşan	döngü ya da kara delik
Yineleyici, Hub ve Anahtar	tablonun hiç olmaması	40 çerçeve, 280 teslim	yok; 240 gereksiz kopya, 34 çakışma
Eşleştirme Tabloları	girdinin yaşı	110 teslim, ömür kısalınca 278	3 kara delik, ömür kısalınca 0
Sanal Yerel Ağlar	bölütün sınırı ile tablonun kapsamı	taşırma teslimi 280, 51, 8	kara delik 0, 23, 29, 32
Kapsayan Ağaç Protokolü	ağaç yenilendi, tablolar eski	ağaçta 40/40, 106 ve 129 adım	19 ve 20 kara delik; iki anahtar tazeleyince 10 döngü
Bağlantı Toplama	bacak eşlemesi ile bacağın durumu	8 akış bölünmeden dağıtılır	beş çerçevelik pencerede 2 kara delik
Yönlendirme Kararı	kopyanın yaşı ve okuma kuralı	yakınsamış 40/40, 83 ve 99 adım	kopma anında 14 kara delik
Statik ve Dinamik Yönlendirme	statik tablo kopmayı hiç duymaz	dinamikte iki turda 40	statikte 14 kara delik altı tur sabit; iki düğüm duyunca 6 döngü
Uzaklık Vektörü Protokolleri	komşunun kararının yaşı	0, 9, 20, 32, 40 — dört tur	erişilemez hedefte 60 paketin altmışı döngü; geri bildirmeme 5’e indirir
Bağlantı Durumu Protokolleri	veritabanının eksik girdisi	9, 20, 32, 40 — üç tur	döngü yok; yanlış tablo yalnız eksik girdiden
Sınır Ağ Geçidi Protokolü	politika ile en kısa yol	transit yasağında 40/40, 92 adım	duyuru kapanınca 14 kara delik; sızıntıda 7 paket sözleşme dışı
Yönlendirme Örnekleri	aynı hedefin iki örnekteki iki kararı	üç örnekte 40/40, 83, 99, 91 adım	tek tabloya indirgenince 14 kara delik
MPLS ve Etiket Anahtarlama	etiket yolu ile alttaki bağın durumu	40 tam bakış ve 43 etiket bakışı	kiriş kopup yol yenilenmeyince 14 kara delik
Kaplama Ağları	kaplamanın tablosu ile alt ağ düzeninin tablosu	iki katman yakınsamışken 40/40, kaplama 74 adım	alt ağ düzeni eskiyken 21 tünel kara deliği; tünel kalkıp iki uç duyunca 12 kaplama döngüsü
Katmanlı Tasarım	soğuk başlangıç ve en yoğun bağın kopması	üç tasarımda 40/40; 121, 80, 138 adım	düz zincirde 21 kalıcı kara delik
Omurga–Yaprak Tasarımı	bir yaprak–omurga bağının kaybı	40/40, 80 adım, her yol 2 adım	tek omurgada 14 kalıcı kara delik, ikiden itibaren 0
Yedeklilik ve Devralma	sanal adresin kimde olduğu	devretme varken 40/40	kimse duymayınca 40 kara delik; ikisi de eşini etkin sanınca 40 döngü
Adres ve Ad Planlaması	özetin kapsadığı ile sahip olduğu	73 satırla 40/40	taşınan ağda 2 kara delik

Tablo üç şeyi tekrar tekrar söylüyor. Kısmî bilgi, hiç bilgiden pahalı bir arıza üretir: kimsenin duymadığı kopma kara delik verir ve arıza bellidir; birkaç düğümün duyduğu kopma döngü verir ve tıkanıklık gibi görünür. Hiçbir cihaz tek başına bir paketi döngüye sokamaz: döngü en az iki tablonun anlaşmazlığıdır ve tablosu doğru olan bir düğümden çıkan paket de ölebilir. Ve yakınsama bir hız değil bir tur sayısıdır: kaç turda bittiği, bilginin ne kadar uzaktan taşındığına bağlıdır.

Bütün bu ölçümlerin ortak bir sessiz kabulü vardı. Bir bağ ya vardır ya yoktur; komşu ya duyar ya duymaz; çerçeve ya iletilir ya iletilmez. İki cihaz arasında bir kablo varsa o kablonun taşıdığı şey karşı tarafa ulaşır — kurs boyunca kopma dışında bunun tersi hiç düşünülmedi. Sonraki kurs bu kabulü kaldırır: kablosuz bir bağda iletilen çerçevenin varması bir kesinlik değil bir olasılıktır, ortam paylaşılır ve dinleyenin kim olduğu bilinmez. Kablolu bağın verili saydığı her şey orada yeniden sorulacak.