Yönlendirme Örnekleri

Önceki ders politikayı tek bir tablonun içinde uyguladı. Her düğümün bir tablosu vardı, her hedefin o tabloda tek bir satırı, ve politika o satırın hangi bir sonraki düğümü göstereceğini değiştirdi. Sınır ağ geçidi protokolü tabloyu yeniden yazdı ama tablonun sayısını değiştirmedi.

Bu dersin sorusu şudur: aynı cihaz birden çok tablo tutarsa ne olur? O zaman bir hedef adresi tek bir karara değil, kaç tablo varsa o kadar karara karşılık gelir — ve kararlar birbirini bilmez. Ölçülen şey bu ayrışmadır.

Bir Cihaz, Birden Çok Tablo

Yönlendirme örneği (routing instance), tek bir cihazın içinde tutulan bağımsız bir yönlendirme tablosudur. Üç parçası vardır: cihazın hangi bağlarını kullanabileceğini söyleyen bir bağ kümesi, o bağ kümesinden hesaplanmış bir tablo, ve gelen paketin hangi örneğe düşeceğini belirleyen bir bağlantı noktası eşlemesi.

Üçüncü parça dersin en kolay atlanan yeridir. Paketin hangi örneğe düştüğü adresinden okunmaz. Adres iki örnekte de aynıdır; ayrımı yapan şey paketin hangi bağlantı noktasından girdiğidir. Cihaz önce örneği seçer, sonra o örneğin tablosunda en uzun önek eşlemesini yapar. İki adım ayrıdır ve ikincisi birincisinden habersizdir.

# ogretilen dokum, calistirilmamistir

b düğümünün yönlendirme örnekleri

örnek     bağlantı noktası   hedef   bir sonraki düğüm
yonetim   1 2                e       f
yonetim   1 2                f       f
olcum     3 4                e       c
olcum     3 4                f       a
konuk     5                  e       f
konuk     5                  f       f

gelen paketin örneğe düşmesi
  bağlantı noktası 1 -> yonetim örneği -> hedef e için bir sonraki düğüm f
  bağlantı noktası 3 -> olcum örneği   -> hedef e için bir sonraki düğüm c
  hedef adresi ikisinde de aynıdır ve seçime hiç girmez

Ayrıştırmanın gerekçesi kapsamdır. Ölçüm trafiğinin yönetim trafiğiyle aynı yolu kullanması gerekmez; konuk trafiğinin kimi bağa hiç çıkmaması istenebilir. Bunu adres planıyla yapmak her düğümde ayrı bir süzgeç yazmak demektir; örnekle yapmak, bağ kümesini daraltıp tablonun kendisini hesaplatmak demektir.

Aynı Adres, İki Karar

Kurgu üç örnek kurar. yonetim cihazın bütün bağlarını kullanır. olcum kirişi (b–f) kullanmaz — o bağ bu örneğe eşlenmemiştir. konuk ise d–e bağını kullanmaz. Üç örnek de aynı sekiz düğümü, aynı hedefleri ve aynı en uzun önek eşleme kuralını kullanır; ayrıldıkları tek yer bağ kümesidir.

Sonuç b düğümünde görünür. Hedef e için yonetim örneği f’yi, olcum örneği c’yi gösterir. Aynı cihaz, aynı hedef, iki ayrı bir sonraki düğüm. İki karar da doğrudur; ikisi de kendi bağ kümesinin en kısa yoludur. Yanlış olan, birini ötekinin yerine kullanmaktır.

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

• YL68 — Topoloji 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.
• YL69 — Üç yönlendirme örneği kurulur ve yalnız bağ kümeleriyle ayrılırlar: yonetim dokuz bağın tümü, olcum kirişsiz sekiz bağ, konuk d–e bağı olmadan sekiz bağ. Örnek adları kurgudur.
• YL70 — Her örneğin tablosu kendi bağ kümesinden hesaplanır ve kâhinle aynı kuraldır: her hedefe giden en kısa yolun ilk adımı. Kâhin değiştirilmez.
• YL71 — Paket girdiği örneği bırakmaz. Bir örnekte iletilen paket, yolu boyunca yalnız o örneğin bağlarını ve yalnız o örneğin tablolarını görür.
• YL72 — Kırk kaynak–hedef çifti kurs çekirdeğinin üretecinden gelir; aynı çift birden çok kez çıkabilir ve her çıkışı ayrı bir pakettir. Atlama sınırı 12.
• YL73 — Tek tabloya indirgeme, yonetim örneğinin tablosunun ötekilerin bağ kümesinde kullanılmasıdır; bağ kümeleri indirgemede birleşmez, çünkü bir bağın bir örneğe eşlenmemesi fiziksel değil yönetimsel bir karardır.

Ölçüm

"""Yonlendirme ornekleri: ayni adres, ayni cihaz, iki ayri karar."""
TOHUM = 20260810
DUGUMLER = "abcdefgh"
BAGLAR = [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e"), ("e", "f"),
          ("f", "g"), ("g", "h"), ("h", "a"), ("b", "f")]
ORNEK = {"yonetim": BAGLAR,
         "olcum": [b for b in BAGLAR if b != ("b", "f")],
         "konuk": [b for b in BAGLAR if b != ("d", "e")]}
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):
    kom, u, yol, gecilen = komsuluk(baglar), kaynak, [kaynak], []
    while u != hedef:
        if len(yol) > ATLAMA_SINIRI:
            return "dongu", yol
        s = t.get((u, hedef))
        if s is None or s not in kom[u]:
            return "kara delik", yol
        if (u, s) in gecilen:
            return "dongu", yol
        gecilen.append((u, s))
        u = s
        yol.append(u)
    return "ulasti", yol


def olc(t, baglar):
    sayim, adim = {"ulasti": 0, "dongu": 0, "kara delik": 0}, 0
    for x, y in ciftler():
        kader, yol = ilet(x, y, t, baglar)
        sayim[kader] += 1
        adim += len(yol) - 1
    return sayim, adim


T = {ad: kahin(bag) for ad, bag in ORNEK.items()}
print(f"{'örnek':<9s} {'bağ':>4s} {'satır':>6s} {'ulaştı':>7s} {'döngü':>6s} "
      f"{'kara delik':>11s} {'adım':>5s}")
for ad, bag in ORNEK.items():
    s, a = olc(T[ad], bag)
    print(f"{ad:<9s} {len(bag):4d} {len(T[ad]):6d} {s['ulasti']:7d} "
          f"{s['dongu']:6d} {s['kara delik']:11d} {a:5d}")

print()
print(f"{'karşılaştırma':<20s} {'ayrışan satır':>14s} {'ilk adımı ayrışan paket':>24s}")
for x, y in (("yonetim", "olcum"), ("yonetim", "konuk"), ("olcum", "konuk")):
    satir = sum(1 for k in T[x] if T[x][k] != T[y][k])
    paket = sum(1 for c in ciftler() if T[x][c] != T[y][c])
    print(f"{x + ' – ' + y:<20s} {satir:14d} {paket:24d}")

print()
print("b düğümünün yönlendirme satırları")
print(f"{'hedef':>6s} {'yonetim':>8s} {'olcum':>6s} {'konuk':>6s}   durum")
for h in DUGUMLER:
    if h == "b":
        continue
    v = [T[ad][("b", h)] for ad in ORNEK]
    print(f"{h:>6s} {v[0]:>8s} {v[1]:>6s} {v[2]:>6s}   "
          f"{'ayrışıyor' if len(set(v)) > 1 else 'aynı'}")

print()
for n in (1, 2, 3):
    secili = list(ORNEK)[:n]
    ayri = sum(1 for k in T["yonetim"]
               if len({T[ad][k] for ad in secili}) > 1)
    print(f"örnek {n}: tutulan satır {n * 56}, en az iki örneğin ayrıştığı "
          f"satır {ayri}")

print()
print("tek tabloya indirgeme (yonetim tablosu kazanır)")
for ad in ("olcum", "konuk"):
    s, a = olc(T["yonetim"], ORNEK[ad])
    print(f"  {ad} bağ kümesinde: ulaştı {s['ulasti']}, döngü {s['dongu']}, "
          f"kara delik {s['kara delik']}, adım {a}")

örnek      bağ  satır  ulaştı  döngü  kara delik  adım
yonetim      9     56      40      0           0    83
olcum        8     56      40      0           0    99
konuk        8     56      40      0           0    91

karşılaştırma         ayrışan satır  ilk adımı ayrışan paket
yonetim – olcum                  11                       12
yonetim – konuk                   7                        6
olcum – konuk                    18                       18

b düğümünün yönlendirme satırları
 hedef  yonetim  olcum  konuk   durum
     a        a      a      a   aynı
     c        c      c      c   aynı
     d        c      c      c   aynı
     e        f      c      f   ayrışıyor
     f        f      a      f   ayrışıyor
     g        f      a      f   ayrışıyor
     h        a      a      a   aynı

örnek 1: tutulan satır 56, en az iki örneğin ayrıştığı satır 0
örnek 2: tutulan satır 112, en az iki örneğin ayrıştığı satır 11
örnek 3: tutulan satır 168, en az iki örneğin ayrıştığı satır 18

tek tabloya indirgeme (yonetim tablosu kazanır)
  olcum bağ kümesinde: ulaştı 26, döngü 0, kara delik 14, adım 61
  konuk bağ kümesinde: ulaştı 32, döngü 0, kara delik 8, adım 72

Ayrışmanın Ölçüsü

Üst tablo üç örneği yan yana koyuyor. Üçünde de kırk paketin kırkı ulaşıyor, döngü 0, kara delik 0. Ayrılan tek şey adımdır: yonetim 83, konuk 91, olcum 99. Kirişin çıkarılması d–e bağının çıkarılmasından pahalıdır, çünkü kiriş halkanın iki yakasını kısa devre yapan bağdır.

İkinci tablo ayrışmayı satır ve paket düzeyinde sayıyor. yonetim ile olcum 56 satırın 11’inde ayrışıyor ve bu ayrışma ölçülen kırk paketin 12’sinin ilk adımını değiştiriyor. yonetim ile konuk arasında sayılar 7 ve 6. En büyük ayrışma iki daraltılmış örnek arasındadır: olcum ile konuk 18 satırda ve 18 pakette ayrışıyor — hiçbiri ötekinin kullandığı bağı kullanmıyor.

Üçüncü tablo b düğümünün yedi satırını veriyor. Dördü üç örnekte de aynı: a, c, d ve h hedefleri için karar bağ kümesinden bağımsızdır. Üçü ayrışıyor. e hedefinde yonetim ve konuk f derken olcum c diyor; f hedefinde olcum a diyor, yani paketi halkanın öteki yakasından dolaştırıyor.

Ayrışmanın bir sonucu daha var. Bir bağ koptuğunda yakınsama yalnız o bağı kullanan örneklerde başlar. Kiriş koparsa yonetim örneğinin tablosu yeni tabloya, yani olcum örneğinin tablosuna dönmek zorundadır; ikisi arasındaki fark ölçülmüş durumda ve 11 satırdır. Aynı kopmada olcum örneği sıfır satır değiştirir, çünkü o bağ zaten kümesinde yoktur. Aynı cihaz aynı anda bir örnekte yakınsama turu harcarken öteki örnekte hiç harcamaz; ayrıştırma tabloyu ayırmadan önce arızanın kapsamını ayırır.

Buradaki gözlem kursun ölçü ekseninin bir başka biçimidir. Kurs boyunca tablolar anlaşmazlığa düştüğünde paketin başına gelen şey sayıldı; burada tablolar anlaşmıyor ve bu bir arıza değil. Ayrışma tasarımın kendisidir. Arıza, ayrışmanın kaldırıldığı yerde başlar.

Örnek Sayısının Bedeli

Dördüncü tablo satır sayısını veriyor. Sekiz düğüm ve yedi hedef, örnek başına 56 satır eder; iki örnek 112, üç örnek 168. Satır sayısı örnek sayısıyla doğrusal büyür.

Ayrışan satır aynı hızla büyümüyor. Tek örnekte 0, iki örnekte 11, üç örnekte 18. Üçüncü örnek tabloya 56 satır daha ekliyor ama ayrışmayı yalnız yedi satır artırıyor. Ters yönden okunduğunda: 56 satırın 38’i (56 eksi 18) üç örnekte de aynıdır ve 168 satırın 114’ü, aynı kararın üç kez yazılmış kopyasıdır.

Bedel budur. Ayrıştırma, kararı gerçekten ayrışan 18 satır için yapılır; kalan satırlar ayrıştırmanın taşıma masrafıdır. Bu masraf düğüm sayısıyla değil, hedef sayısı çarpı örnek sayısı ile büyür ve iki çarpanın ikisi de tasarım kararıdır.

Çakışan Adresler ve Paylaşılan Satırlar

Kurguda örnekleri ayıran şey bağ kümesidir. Çalışan ağlarda asıl gerekçe adresin kendisidir: iki örnek aynı adres öbeğini taşıyabilir ve o öbek iki ayrı yere gidebilir. Tek tablolu bir cihazda bu olanaksızdır, çünkü en uzun önek eşlemesi tek bir sonuç verir ve aynı önek iki satıra yazılamaz. Örnekler kısıtı kaldırır, çünkü eşleme örnek seçildikten sonra yapılır. Kurgunun düğüm adları çakışmıyor; çakışsalardı ölçüm değişmezdi, zaten örnek seçimi adrese hiç bakmıyor.

Bunun ikinci sonucu, bir satırın iki örnek arasında kasıtlı olarak paylaşılabilmesidir. Bütün örneklerden erişilmesi istenen ortak bir hizmet varsa, o hizmetin satırı ikinci örneğe kopyalanır ve ayrışma bir satır azalır. Son ölçüm bu işlemin sınırını veriyor: kopyalanan satırda bir sonraki düğümün o örnekte komşu olduğu doğrulanmazsa, kopyalanan her satır bir kara delik satırıdır.

Bölütlemenin bağlantı katmanındaki karşılığı kursun ağ cihazları konusunda kuruldu: sanal yerel ağ yayın alanını böler ve çerçeveyi etiketle ayırır. Ayrım tek cümleyle yazılabilir: sanal yerel ağ aynı yayın alanına kimin gireceğini, yönlendirme örneği ise hangi tablonun okunacağını belirler. Biri çerçevenin dolaştığı alanı, öteki paketin bakacağı satırı ayırır. İkisi bir arada kullanıldığında bir bağlantı noktası hem bir sanal yerel ağa hem bir yönlendirme örneğine eşlenir; eşlemelerden biri eksikse paket ya yanlış alana ya yanlış tabloya düşer.

Tek Tabloya İndirgeme

Son ölçüm masraftan kaçmayı deniyor: üç tablo yerine tek tablo tutulsa, yonetim örneğinin tablosu ötekilerin bağ kümesinde ne yapar?

olcum bağ kümesinde 26 paket ulaşıyor, 14’ü kara deliğe düşüyor, toplam adım 61. Gerekçe b düğümünün satırında yazılı: birleşik tablo hedef f için f‘yi gösteriyor, ama f bu örnekte b‘nin komşusu değil. Bir sonraki düğüm tabloda var, komşulukta yok — kursun kara delik tanımı tam olarak budur. konuk bağ kümesinde sayılar 32 ve 8. Adımın 83’ten 61’e inmesi burada da bir iyileşme değildir: ölen paket adım harcamayı bırakır ve düşük adım kaybın göstergesi olur.

Bu, ayrıştırmanın neden tabloyla birlikte bağ kümesini de ayırdığının yanıtıdır. Tabloyu paylaştırıp bağ kümesini ayrı tutmak, her düğümde bir sonraki düğümün var olduğunu ama erişilemediğini bildiren satırlar üretir. Tablo küçülür, paket ölür.

Özet

• Yönlendirme örneği üç parçadır: bağ kümesi, ondan hesaplanan tablo, ve gelen paketi örneğe düşüren bağlantı noktası eşlemesi. Paketin hangi örneğe düştüğü adresinden okunmaz.
• Aynı cihazda aynı hedef iki ayrı karara gider: b düğümü hedef e için yonetim örneğinde f’yi, olcum örneğinde c’yi gösterir; ikisi de kendi bağ kümesinin en kısa yoludur.
• Üç örnek kırk paketin kırkını da ulaştırır ve toplam adım sırasıyla 83, 99 ve 91’dir; ayrışma yonetim–olcum arasında 11 satır ve 12 paket, olcum–konuk arasında 18 satır ve 18 pakettir.
• Tutulan satır örnek sayısıyla doğrusal büyür (56, 112, 168) ama ayrışan satır büyümez (0, 11, 18); 168 satırın 114’ü aynı kararın kopyasıdır.
• Örnekler tek tabloya indirgendiğinde olcum bağ kümesinde 14 paket kara deliğe düşer: bir sonraki düğüm tabloda vardır ama o örnekte komşu değildir.

Sonraki Adım

Üç örnekte de karar her düğümde yeniden alındı. Paket b’ye geldi, b tablosuna baktı; c’ye geldi, c tablosuna baktı. Örnek sayısını üçe çıkarmak tutulan satırı üçe katladı ama bakış sayısını hiç değiştirmedi: kırk paket kaç adım attıysa o kadar arama yapıldı. Sonraki ders bu tekrarı ölçer. Karar yol boyunca her düğümde yeniden alınmak zorunda mıdır, yoksa bir kez alınıp paketin üzerinde taşınabilir mi, ve taşındığında kaç arama ile kaç satır arasında nasıl bir takas doğar.