Eşleştirme Tabloları

Önceki ders anahtarın tablosunu hazır kabul etti: sekiz adresin sekizi de doğru bacakla eşlenmişti ve tablo bu yüzden kırk çerçevenin kırkını da tek bacağa çıkardı. O varsayım altında tablo teslimi 280’den 40’a indirdi.

Gerçek bir tablo öyle başlamaz ve öyle kalmaz. Anahtar açıldığında tablo boştur; girdiler gözlem yoluyla dolar; hiç konuşmayan bir istasyonun girdisi hiç yazılmaz; ve bir kez yazılan girdi sonsuza kadar doğru kalmaz, çünkü istasyon başka bir bacağa taşınabilir. Bu dersin sorusu tablonun ne yaptığı değil, ne kadar yaşadığıdır.

Üç Ayrı Eksiklik

Bir tablo üç ayrı biçimde yetersiz kalır ve üçünün bedeli aynı değildir.

Öğrenilmemiş girdi. Adres tabloda hiç yoktur. Anahtar hedefin nerede olduğunu bilmez ve çerçeveyi gelen bacak dışındaki bütün bacaklara verir. Çerçeve hedefine ulaşır; bedel yalnızca gereksiz kopyalardır. Öğrenme düzeneğinin kendisi — kaynak adresin geldiği bacakla birlikte yazılması ve hedefi bilinmeyen çerçevenin taşırılması (flooding) — Ağ Modelleri kursundaki Ethernet ve MAC Adresleri dersinde kuruldu ve burada tekrarlanmaz.

Yaşlanmış girdi. Adres tabloda vardı, ama girdi konduğundan beri geçen süre girdinin ömrünü aştı ve girdi silindi. Sonuç öğrenilmemiş girdiyle aynıdır: taşırma, ulaşan çerçeve, gereksiz kopya. Ayrı sayılmasının nedeni farklı bir kaynaktan gelmesidir — biri hiç öğrenilmemiş olmaktan, öbürü unutulmuş olmaktan doğar.

Eskimiş girdi. Adres tabloda vardır, girdi tazedir ve yanlıştır. İstasyon başka bir bacağa taşınmış, tablo hâlâ eski bacağı göstermektedir. Anahtar bu durumda taşırmaz; emin adımlarla yanlış bacağa çıkar. Çerçeve orada kimseyi bulamaz ve kara deliğe düşer. Üç eksiklikten yalnız bu üçüncüsü çerçeveyi öldürür.

Ayrım şuraya varır: taşırma pahalıdır ama doğrudur, eskimiş girdi ucuzdur ve yanlıştır. Girdinin ömrü bu ikisi arasında bir seçimdir.

Taşırma Hangi Alanda İş Üretir

Taşırılan bir çerçeve, hedefi tek bir istasyon olmasına rağmen bütün bacaklara çıkar. Önceki dersin iki kapsamı burada ayrışır. Taşırma çarpışma alanını büyütmez: bacaklar hâlâ birbirinden yalıtılmıştır ve çıkan kopyalar birbiriyle çakışmaz. Taşırma yayın alanını kullanır: kopyalar tam olarak bir yayın çerçevesinin gideceği yere gider.

Sonuç şudur: öğrenilmemiş bir hedef, tek bir çerçeveyi geçici olarak bir yayın çerçevesine çevirir. Yayın alanı ne kadar büyükse taşırmanın bedeli o kadar büyür ve bu bedel taşırılan çerçeve sayısıyla çarpılır.

Bir istasyonun hiç konuşmaması bu bedeli kalıcı hâle getirir. Ölçümdeki h istasyonu hiç çerçeve göndermez; kaynak adresi hiçbir çerçevede görünmediği için tabloya hiç yazılmaz. Ona giden her çerçeve, ölçümün sonuna kadar taşırılır. Tablonun satır sayısı bu yüzden sekiz değil yedidir.

Tablo Bacağa Değil Adrese Bakar

Tablonun yönü ilk bakışta ters görünür: anahtarın sekiz bacağı vardır ama tablo bacakları değil adresleri sayar. Bir bacakta tek bir istasyon olmak zorunda değildir. O bacağa başka bir anahtar bağlıysa, arkasındaki bütün istasyonların adresleri aynı bacakla eşlenir; sanallaştırılmış bir konak da tek bir bacaktan birden çok adres gösterebilir.

Bunun iki sonucu vardır. Birincisi, tablonun satır sayısı bacak sayısıyla değil görülen adres sayısıyla büyür; ölçümdeki yedi satır sekiz istasyondan gelir, dokuz bacaktan değil. İkincisi, aynı adres iki bacakta birden görünemez: yeni bir gözlem geldiğinde girdi güncellenir, çoğaltılmaz. Bir adresin iki bacak arasında sürekli gidip gelmesi, tablonun kendisiyle çelişmesi değil, ağın çelişkili gözlem üretmesidir — kaynağı bu konunun ilerleyen bir dersinin konusudur.

Tablonun kapasitesi de sonludur. Girdi sayısı kapasiteyi aştığında bir girdi yer açmak için düşer ve düşen girdinin adresine giden çerçeveler taşırılır. Bu, ömrü kısaltmakla aynı sonucu verir; farkı, seçimin yönetici tarafından değil doluluk tarafından yapılmasıdır.

# ogretilen dokum, calistirilmamistir

eslestirme tablosu (an 12)
  adres  bacak  yazildigi an
  a      1      13
  b      2       9
  c      3      11      <- bu girdi an 12'de eskiyor
  d      4       8
  e      5      10
  f      6      12
  g      7       5
  (h icin satir yok: hic gonderim yapmadi)

an 12'de: c istasyonu bacak 3'ten bacak 9'a tasinir.
  an 15, hedef c -> tablo bacak 3 der -> kimse yok  -> kara delik
  girdi yaslanirsa      -> tasirma -> butun bacaklar -> ulasir
  c yeniden gonderirse  -> girdi bacak 9 olur       -> ulasir

Ölçümün Varsayımları

• AC8 — Sekiz istasyon dokuz bacaklı bir anahtara bağlıdır; dokuzuncu bacak boştur ve taşınmanın hedefidir. Kâhin yerleşimi biz kurduğumuz için bilinir ve her an hangi adresin hangi bacakta olduğunu söyler.
• AC9 — Kırk çerçeve tek bir üreteçten, tek bir modülüsle çekilir. Kaynağın hedefe eşit olduğu ve kaynağın sessiz istasyon olduğu çekilişler atılır; sessiz istasyon böylece hiç gönderim yapmaz.
• AC10 — Zaman birimi çerçevedir: girdinin yaşı, konduğu çerçeveden bu yana geçen çerçeve sayısıdır. Ömrü None olan rejimde girdi hiç silinmez.
• AC11 — Tablo yalnız kaynak adresten öğrenir ve her çerçevede önce öğrenme, sonra iletme yapılır. Bu sıra gerçek düzenekle aynıdır ve ölçümü etkiler: bir istasyonun kendi gönderimi kendi girdisini tazeler.
• AC12 — Taşınma rejiminde bir istasyon 12. çerçevede boş bacağa geçer ve bunu kimseye bildirmez. Tablo ancak iki yoldan düzelir: girdi yaşlanır ya da istasyon yeniden gönderim yapar.
• AC13 — Kader adları ortak tanımdakilerle aynıdır. Çerçeve hedefin gerçek bacağına bir kopya bırakıyorsa ulaştı, bırakmıyorsa kara delik sayılır. Tek anahtarlı bu kurguda döngü oluşamaz.
• AC14 — Kümenin çözünürlüğü kırk çerçevedir; ölçülebilen en küçük fark $1/40 = 0{,}025$’tir.

Ölçüm

"""Tablonun yasi: ogrenilmemis ve yaslanmis girdinin bedeli.

Ogrenme duzenegi Ag Modelleri kursunda kuruldu; burada olculen sey
girdinin ne kadar yasadigidir.
"""
TOHUM = 20260810
ISTASYONLAR = ["a", "b", "c", "d", "e", "f", "g", "h"]
BACAK = 9
SESSIZ = "h"
TASINAN, TASINMA_ANI = "c", 12


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

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


def cerceveler(sayi=40):
    r, liste = uretec(TOHUM), []
    while len(liste) < sayi:
        x, y = ISTASYONLAR[r(8)], ISTASYONLAR[r(8)]
        if x != y and x != SESSIZ:
            liste.append({"an": len(liste), "kaynak": x, "hedef": y})
    return liste


def kahin(an, tasinma):
    """Gercek yerlesim; tasinma aninda bir istasyon bos bacaga gecer."""
    yer = {a: i + 1 for i, a in enumerate(ISTASYONLAR)}
    if tasinma and an >= TASINMA_ANI:
        yer[TASINAN] = BACAK
    return yer


def olc(C, yas, tasinma):
    tablo, kader = {}, {"ulasti": 0, "kara delik": 0}
    tasir = {"ogrenilmemis": 0, "yaslanmis": 0}
    teslim = gereksiz = 0
    for c in C:
        yer = kahin(c["an"], tasinma)
        tablo[c["kaynak"]] = (yer[c["kaynak"]], c["an"])
        girdi = tablo.get(c["hedef"])
        taze = girdi is not None and (yas is None or c["an"] - girdi[1] < yas)
        if taze:
            cikis = [girdi[0]]
        else:
            tasir["yaslanmis" if girdi else "ogrenilmemis"] += 1
            cikis = [b for b in range(1, BACAK + 1) if b != yer[c["kaynak"]]]
        teslim += len(cikis)
        gereksiz += sum(1 for b in cikis if b != yer[c["hedef"]])
        kader["ulasti" if yer[c["hedef"]] in cikis else "kara delik"] += 1
    return tasir, kader, teslim, gereksiz, len(tablo)


C = cerceveler()
print(f"çerçeve {len(C)} | bacak {BACAK} | sessiz istasyon {SESSIZ}, hedef "
      f"olduğu çerçeve {sum(1 for c in C if c['hedef'] == SESSIZ)} | "
      f"taşırma tavanı {len(C) * (BACAK - 1)}")
BASLIK = (f"{'yaş':>5s} {'öğrenilmemiş':>12s} {'yaşlanmış':>9s} {'ulaştı':>6s} "
          f"{'kara delik':>10s} {'teslim':>6s} {'gereksiz':>8s} {'satır':>5s}")
for tasinma in (False, True):
    print()
    print("taşınma var" if tasinma else "taşınma yok")
    print(BASLIK)
    for yas in (None, 20, 10, 5, 2):
        t, k, te, g, n = olc(C, yas, tasinma)
        print(f"{str(yas):>5s} {t['ogrenilmemis']:12d} {t['yaslanmis']:9d} "
              f"{k['ulasti']:6d} {k['kara delik']:10d} {te:6d} {g:8d} {n:5d}")

çerçeve 40 | bacak 9 | sessiz istasyon h, hedef olduğu çerçeve 4 | taşırma tavanı 320

taşınma yok
  yaş öğrenilmemiş yaşlanmış ulaştı kara delik teslim gereksiz satır
 None           10         0     40          0    110       70     7
   20           10         0     40          0    110       70     7
   10           10         6     40          0    152      112     7
    5           10        14     40          0    208      168     7
    2           10        24     40          0    278      238     7

taşınma var
  yaş öğrenilmemiş yaşlanmış ulaştı kara delik teslim gereksiz satır
 None           10         0     37          3    110       73     7
   20           10         0     37          3    110       73     7
   10           10         6     38          2    152      114     7
    5           10        14     39          1    208      169     7
    2           10        24     40          0    278      238     7

Öğrenilmemiş Girdinin Değişmeyen Payı

Her iki tabloda da öğrenilmemiş sütunu 10’dur ve hiçbir ömür değeri onu değiştirmez. Bu sayı iki parçadan oluşur: tablonun boş başlamasından doğan ilk karşılaşmalar ve sessiz istasyona giden 4 çerçeve. İlk parça bir kez ödenir, ikinci parça ölçüm boyunca ödenir.

Sonuç önemlidir: girdinin ömrünü uzatmak öğrenilmemiş girdiyi azaltmaz. Ömür yalnız girdinin ne kadar yaşayacağını belirler, hiç yazılmamış bir girdiyi doğurmaz. Sessiz bir istasyonu tabloya sokmanın tek yolu onu konuşturmaktır. Tablo yalnız gözlemden beslendiği için, hiç gözlem üretmeyen bir uç tablonun görüş alanının tümüyle dışında kalır ve ona giden her çerçeve bu görüşsüzlüğün bedelini öder.

Ömrü sınırsız bırakan rejim 110 teslim veriyor; hepsi taşırılabilirse tavan 320’dir. Yani tablo, doğru çalıştığı hâliyle bile teslimin üçte birinden azını üretiyor — geri kalanı zaten tasarruf. Ömür kısaldıkça bu tasarruf eriyor: 10 çerçevelik ömürde teslim 152, 5’te 208, 2’de 278. Son satırda anahtar tavanın 0,869’una çıkmıştır; tablo neredeyse hükümsüzdür ve cihaz karar veren bir cihaz olmaktan çıkmıştır.

Ömrün İki Yönü

Alt tablo aynı ömür dizisini bir taşınmayla birlikte okuyor ve yön değişiyor.

Ömrü sınırsız bırakan rejimde 3 çerçeve kara deliğe düşüyor. Üçü de taşınmadan sonra, taşınan istasyon yeniden konuşmadan önce gönderilmiş çerçevelerdir; tablo o aralıkta emin ve yanlıştır. 20 çerçevelik ömür aynı sonucu veriyor, çünkü ölçüm bitmeden hiçbir girdi o yaşa ulaşmıyor: bir ömür değeri, ölçüm penceresinden uzunsa sınırsız ömürden ayırt edilemez.

10 çerçevelik ömürde kara delik 2’ye, 5’te 1’e, 2’de 0’a iner. Düzeltmeyi yapan şey bir bildirim değildir — kimse taşınmayı duyurmaz. Düzeltmeyi yapan şey unutmaktır: girdi silindiği anda anahtar yeniden bilmediğini kabul eder ve taşırır, taşırılan çerçeve de yeni bacağa uğradığı için ulaşır.

Bedel aynı satırlarda duruyor. Kara deliği 3’ten 0’a indirmek teslimi 110’dan 278’e çıkarıyor: bir çerçeveyi kurtarmanın bedeli ortalama elli altı fazladan kopyadır. Üç çerçeve kırk çerçevelik kümede 0,075’tir ve çözünürlüğün üç katıdır, yani ölçülebilir bir farktır; ama kaybı sıfırlamak için ödenen kopya, taşırma tavanının yarısından fazlasıdır.

Örüntü şudur: girdinin ömrü, yanlış bilme süresi ile bilmeme maliyeti arasında bir seçimdir. Uzun ömür tabloyu ucuzlatır ve yanılgıyı uzatır; kısa ömür yanılgıyı kısaltır ve tabloyu hükümsüzleştirir. İkisini birden sıfırlayan bir ömür yoktur, çünkü anahtarın taşınmayı öğrenmesinin tek yolu yeni bir gözlemdir ve gözlem gelene kadar geçen süre ölçülemez.

Ömür Tek Başına Seçilmez

Ölçümde tek bir ömür vardı, çünkü tek bir tablo vardı. Gerçek bir yolda aynı hedefe ait iki ayrı önbellek yan yana durur: anahtardaki eşleştirme tablosu, ve gönderen konaktaki adres çözümleme önbelleği. İkincisi Ağ Modelleri kursundaki ARP dersinde kuruldu ve burada tekrarlanmaz; burada önemli olan yalnız ömürlerinin birbirine göre seçilmesidir.

İki ömür eşit olmadığında bir bakışımsızlık doğar. Gönderen konak hedefin donanım adresini önbelleğinde tutmaya devam ederken anahtardaki girdi silinmişse, konak sorgu yapmadan çerçeve göndermeyi sürdürür ve anahtar her çerçeveyi taşırır. Hedef istasyon yalnızca yanıt veren bir uçsa — yani kendiliğinden konuşmuyorsa — girdisi yeniden yazılmaz ve taşırma sürekli hâle gelir. Ölçümdeki sessiz istasyonun kalıcı 10 payı bu durumun küçük bir örneğidir.

Kural şudur: anahtardaki girdinin ömrü, üst katmandaki adres önbelleğinin ömründen kısa seçilirse taşırma bir arıza değil, tasarımın olağan sonucu olur. Ters yönde seçildiğinde ise eskimiş girdinin ömrü uzar ve kara delik penceresi genişler. Ölçümün iki tablosu bu iki yönü ayrı ayrı gösteriyor; seçim ikisinin arasındadır.

Tablolar Birbirini Bilmez

Ölçüm tek bir anahtarla yapıldı ve bu, sonucu olduğundan iyimser gösterir. İki anahtar yan yana durduğunda ortada iki tablo vardır ve aralarında hiçbir eşitleme yoktur. Her anahtar yalnız kendi bacaklarından geçen çerçeveleri görür; kendi gördüğünü yazar, görmediğini bilmez. Bir anahtarın tazelediği girdi, öbüründe çoktan yaşlanmış olabilir.

Bu, tablonun bir kusuru değil tanımıdır: tablo paylaşılan bir gerçeğin yerel kopyasıdır. Kopyayı güncel tutan bir bildirim yoktur; güncelliği sağlayan tek şey aynı trafiği görmektir. Aynı trafiği görmeyen iki anahtar, aynı adres için farklı bacaklar gösterebilir.

Tek anahtarlı kurguda bunun bedeli görünmedi, çünkü ölçülen tek kader kara delikti: yanlış bacağa çıkan çerçeve orada bitiyordu. İki tablo olduğunda üçüncü bir kader açılır. Bir anahtar çerçeveyi ileri, öbürü geri gönderirse çerçeve ölmez; iki cihaz arasında gidip gelir. Döngü, tek bir tablonun yapabileceği bir şey değildir — en az iki tablonun anlaşmazlığıdır ve bu konunun ilerleyen bir dersinde ilk kez sayılacaktır.

Özet

• Tablo üç ayrı biçimde yetersiz kalır: öğrenilmemiş ve yaşlanmış girdi taşırmaya, eskimiş girdi kara deliğe yol açar; ilk ikisi pahalı ama doğru, üçüncüsü ucuz ve yanlıştır.
• Taşırma çarpışma alanını değil yayın alanını kullanır: taşırılan bir çerçeve tek bir hedefe gitmesine rağmen yayın çerçevesi gibi iş üretir.
• Öğrenilmemiş girdi sayısı bütün ömür değerlerinde 10 kalır; 4’ü hiç konuşmayan istasyona gider ve tablo bu yüzden sekiz değil 7 satırda kalır.
• Ömür kısaldıkça teslim 110, 152, 208, 278 diye büyür; son değer taşırma tavanı 320’nin 0,869’udur ve tabloyu hükümsüz bırakır.
• Taşınma rejiminde kara delik 3, 3, 2, 1, 0 diye iner; düzeltmeyi yapan şey bir bildirim değil, girdinin unutulmasıdır.

Sonraki Adım

Bu ölçümde taşırma hep aynı yere gitti: dokuz bacağın tümüne. Bunun nedeni sekiz istasyonun tek bir yayın alanında olmasıydı — önceki dersin ölçümünde de yayın alanı sayısı her rejimde birdi. Oysa taşırmanın bedeli doğrudan bu alanın büyüklüğüyle çarpılıyor. Sonraki ders alanı bölmeyi ölçer: aynı fiziksel anahtar üzerinde birden çok yayın alanı tanımlandığında taşırma kaç kopyaya iner, tablo kaç satıra çıkar ve bölütlemenin kendi ürettiği kara delik nereden gelir.