MPLS ve Etiket Anahtarlama

Önceki ders aynı cihazda üç yönlendirme örneği kurdu ve tutulan satırı 56’dan 168’e çıkardı. Değişmeyen bir şey vardı: karar her düğümde yeniden alınıyordu. Paket b’ye geldi, b hedefe baktı ve kendi tablosundan bir satır okudu; c’ye geldi, c aynı işi baştan yaptı. Örnek sayısı satırı üçe katladı ama bu tekrarı hiç değiştirmedi.

Bu dersin sorusu tekrarın kendisidir. Yakınsamış bir ağda yol boyunca alınan kararların hepsi aynı yolu verir; aynı sonuç beş düğümde beş kez hesaplanır. Karar bir kez alınıp paketin üzerinde taşınabilir mi, ve taşındığında ne kazanılır, ne ödenir?

Kararın Alındığı Yer

Her düğümde karar alan bir ağda işlem üç adımdır: paketin hedef adresini oku, tablodaki önekler arasında en uzun önek eşlemesini yap, çıkan satırdaki bir sonraki düğüme ilet. Üç adım da her düğümde yinelenir ve üçüncü adımın girdisi her seferinde aynıdır.

Etiket anahtarlama (label switching) bu yinelemeyi kaldırır. Yolun giriş düğümü kararı bir kez alır ve sonucu pakete kısa bir etiket olarak ekler. Ara düğümler hedef adresine hiç bakmaz; yalnız gelen etikete bakar, kendi etiket tablosundan çıkan etiketi ve bir sonraki düğümü okur, etiketi takas eder ve paketi iletir. Çıkış düğümü etiketi çıkarır ve paketi hedefine teslim eder.

Etiketin iki özelliği kritiktir. Etiket hedefi adlandırmaz, yolu adlandırır: aynı hedefe giden iki ayrı yolun iki ayrı etiketi olabilir. Ve etiket bağ başına anlamlıdır: 17 değerinin b–c bağındaki anlamı ile c–d bağındaki anlamı arasında hiçbir bağ yoktur, bu yüzden her düğüm etiketi takas etmek zorundadır.

# ogretilen dokum, calistirilmamistir

giriş düğümü (b)           ara düğüm (c)              çıkış düğümü (d)
  hedef             d        gelen etiket     17        gelen etiket      9
  yol           b-c-d        çıkan etiket      9        işlem       çıkar ve teslim et
  işlem      etiket ekle     bir sonraki       d
  etiket           17        işlem         takas

c düğümünün etiket tablosu       c düğümünün yönlendirme tablosu
  gelen  çıkan  bir sonraki        hedef  bir sonraki
     17      9            d            a            b
     23     41            b            d            d
     44      6            b            e            d

Sağdaki iki tablo dersin takasını gösteriyor. Yönlendirme tablosu hedef başına satır tutar; etiket tablosu yol başına satır tutar. Bir düğümden geçen yol sayısı hedef sayısından büyükse etiket tablosu yönlendirme tablosundan büyür.

Etiket tek bir değer olmak zorunda değildir. Pakete birden çok etiket yazılabilir; etiketler bir yığın oluşturur ve ara düğüm yalnız en dıştaki etikete bakar. Bu, önceki dersle doğrudan birleşir: dıştaki etiket yolu, içteki etiket paketin hangi yönlendirme örneğine ait olduğunu adlandırır. Ara düğümler örnekleri hiç bilmez; yalnız çıkış düğümü dış etiketi çıkarıp içtekine bakar ve paketi doğru örneğin tablosuna düşürür. Bir ağın ortasındaki düğümler böylece taşıdıkları trafiğin kaç örneğe ayrıldığını bilmeden onu taşıyabilir. Ölçüm yığının derinliğini saymaz; saydığı şey en dıştaki etiketin ürettiği bakıştır.

Yolun Kenardan Kurulması

Karar bir kez alındığında, o kararın en kısa yol olma zorunluluğu ortadan kalkar. Giriş düğümü etiketi hangi yola karşılık getireceğini seçebilir; ara düğümler zaten hedefe bakmadığı için seçimi sorgulamaz. Yol mühendisliği (traffic engineering) budur: yolu maliyet değil, yönetim seçer.

Kurguda bunun karşılığı kirişten kaçınmaktır. Kiriş halkanın iki yakasını kısa devre yaptığı için en kısa yolların çoğu ondan geçer ve tek bir bağ üzerinde yığılır. Etiket yolları kirişsiz halkanın en kısa yollarından kurulursa kiriş fiziksel olarak durmayı sürdürür, ama üzerinden paket geçmez.

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

• YL74 — 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.
• YL75 — İki rejim karşılaştırılır. Birincisinde her düğüm hedefe bakıp kendi tablosundan karar alır; ikincisinde yalnız giriş düğümü hedefe bakar, ara düğümler etikete bakar. Yol ikisinde de aynı tablodan türetilir; ayrılan tek şey kararın alındığı yerdir.
• YL76 — Bakış sayımı: her düğümde karar alan rejimde paketin attığı her adım bir tam tablo bakışıdır. Kenarda karar alan rejimde paket başına bir tam tablo bakışı ve kalan adım sayısı kadar etiket bakışı sayılır.
• YL77 — Yol mühendisliği rejiminde etiket yolları kirişsiz halkanın en kısa yollarından kurulur. Kiriş fiziksel olarak durur; yalnız hiçbir etiket yolu onu kullanmaz.
• YL78 — Etiket satırı sayımı: elli altı yolun her biri için yolun son düğümü dışındaki her düğümde bir satır tutulur. Yönlendirme tablosu ise düğüm başına yalnız hedef sayısı kadar satır tutar.
• YL79 — Son rejimde kiriş kopar ve etiket yolları yenilenmez; giriş düğümü eski kararını sürdürür, ara düğümler zaten hedefi bilmedikleri için hiçbir şey düzeltemez.
• YL80 — Kırk kaynak–hedef çifti kurs çekirdeğinin üretecinden gelir, her çıkış ayrı bir pakettir, atlama sınırı 12 ve kümenin çözünürlüğü 1/40 = 0,025’tir.

Ölçüm

"""Etiket anahtarlama: karar her dugumde mi, bir kez kenarda mi alinir."""
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")]
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 yol(kaynak, hedef, t, baglar):
    kom, u, y, gecilen = komsuluk(baglar), kaynak, [kaynak], []
    while u != hedef:
        if len(y) > ATLAMA_SINIRI:
            return "dongu", y
        s = t.get((u, hedef))
        if s is None or s not in kom[u]:
            return "kara delik", y
        if (u, s) in gecilen:
            return "dongu", y
        gecilen.append((u, s))
        u = s
        y.append(u)
    return "ulasti", y


def olc(t, baglar, kenar):
    """kenar=False: her dugumde tam tablo bakisi. kenar=True: bir kez kenarda."""
    sayim = {"ulasti": 0, "dongu": 0, "kara delik": 0}
    adim = tam = etiket = kiris = 0
    for x, y in ciftler():
        kader, iz = yol(x, y, t, baglar)
        k = len(iz) - 1
        sayim[kader] += 1
        adim += k
        tam += 1 if kenar else k
        etiket += max(k - 1, 0) if kenar else 0
        kiris += sum(1 for i in range(k)
                     if tuple(sorted((iz[i], iz[i + 1]))) == ("b", "f"))
    return sayim, adim, tam, etiket, kiris


TAM, MUH = kahin(BAGLAR), kahin(KOPUK)
REJIM = (("düğüm başına karar", TAM, BAGLAR, False),
         ("kenarda karar", TAM, BAGLAR, True),
         ("kenarda karar, yol mühendisliği", MUH, BAGLAR, True),
         ("kiriş koptu, etiket eski", TAM, KOPUK, True),
         ("kiriş koptu, düğüm başına karar", TAM, KOPUK, False))
print(f"{'rejim':<32s} {'ulaştı':>7s} {'döngü':>6s} {'kara delik':>11s} "
      f"{'adım':>5s} {'tam bakış':>10s} {'etiket bakışı':>14s} {'kiriş':>6s}")
for ad, t, bag, kenar in REJIM:
    s, a, tm, et, kr = olc(t, bag, kenar)
    print(f"{ad:<32s} {s['ulasti']:7d} {s['dongu']:6d} {s['kara delik']:11d} "
          f"{a:5d} {tm:10d} {et:14d} {kr:6d}")

print()
print(f"{'tablo':<26s} {'toplam satır':>13s} {'düğüm başına en çok':>21s}")
print(f"{'yönlendirme (hedef başına)':<26s} {len(TAM):13d} "
      f"{max(sum(1 for u, h in TAM if u == x) for x in DUGUMLER):21d}")
for ad, t in (("etiket, en kısa yol", TAM), ("etiket, mühendislik yolu", MUH)):
    satir = {u: 0 for u in DUGUMLER}
    for u in DUGUMLER:
        for h in DUGUMLER:
            if u == h:
                continue
            for v in yol(u, h, t, BAGLAR)[1][:-1]:
                satir[v] += 1
    print(f"{ad:<26s} {sum(satir.values()):13d} {max(satir.values()):21d}")

rejim                             ulaştı  döngü  kara delik  adım  tam bakış  etiket bakışı  kiriş
düğüm başına karar                    40      0           0    83         83              0     14
kenarda karar                         40      0           0    83         40             43     14
kenarda karar, yol mühendisliği       40      0           0    99         40             59      0
kiriş koptu, etiket eski              26      0          14    61         40             26      0
kiriş koptu, düğüm başına karar       26      0          14    61         61              0      0

tablo                       toplam satır   düğüm başına en çok
yönlendirme (hedef başına)            56                     7
etiket, en kısa yol                  110                    23
etiket, mühendislik yolu             128                    18

Bakışın Yeri Değişti, Sayısı Değişmedi

İlk iki satır aynı yolu iki ayrı biçimde yürütüyor. Kırk paket her ikisinde de 83 adım atıyor, kırkı da ulaşıyor, kiriş yükü ikisinde de 14 pakettir. Yol tıpatıp aynıdır ve bu kasıtlıdır: karşılaştırılan şey yol değil, kararın alındığı yerdir.

Değişen şey bakışın dağılımıdır. Her düğümde karar alan rejim 83 tam tablo bakışı yapar. Kenarda karar alan rejim 40 tam tablo bakışı ve 43 etiket bakışı yapar. Toplam bakış sayısı ikisinde de 83’tür; etiket bakış sayısını azaltmaz.

Kazanç bakışın türündedir. Tam tablo bakışı hedef adresini okumayı, önekler arasında en uzun eşlemeyi aramayı ve yedi satırlık bir tabloda gezinmeyi gerektirir. Etiket bakışı tek bir değerin doğrudan aranmasıdır; sıralama yoktur, önek yoktur, uzunluk karşılaştırması yoktur.

İkinci ve daha önemli kazanç kursun ölçü eksenindedir. Her düğümde karar alan rejimde yol boyunca k ayrı tablo kararı verir ve bu tabloların anlaşması gerekir. Kenarda karar alan rejimde yolu belirleyen tek bir tablodur; ara düğümlerin tabloları yolu değil, yalnız etiketin karşılığını taşır. Kursun üçüncü iddiası döngünün en az iki tablonun anlaşmazlığı olduğunu söylüyordu; etiket, anlaşması gereken tablo sayısını bire indirir.

Yükün Dağıtılması

Üçüncü satır yol mühendisliğini ölçüyor. Etiket yolları kirişten kaçındığında kırk paketin kırkı yine ulaşıyor, ama toplam adım 83’ten 99’a çıkıyor ve kirişten geçen paket sayısı 14’ten 0’a iniyor.

Takas açıktır: on altı fazladan adıma karşılık, tek bir bağ üzerindeki on dört paketlik yığılmanın kaldırılması. Bu kararı maliyet veremez, çünkü maliyetin bildiği tek şey yol uzunluğudur; kirişin kapasitesini, bedelini ya da paylaşıldığı başka trafiği bilmez. Bir önceki derste politikanın yolu uzatması bir kusur değildi; burada da değildir ve gerekçesi aynıdır: en kısa yol bir hedef değil, bir varsayılan değerdir.

Tablonun Bedeli

Alt tablo kararın kenara taşınmasının faturasını veriyor. Yönlendirme tabloları elli altı düğüm–hedef satırı tutuyor ve hiçbir düğümde 7’den fazla satır yok. Etiket tabloları aynı elli altı yol için 110 satır tutuyor ve en yüklü düğümde 23 satır birikiyor.

Örüntü tablodaki iki satırda okunur. Yönlendirme durumu hedef sayısıyla büyür; etiket durumu yol sayısıyla büyür ve yol sayısı hedef sayısından çok daha hızlı artar. Karar kenara taşındı, ama kararın durumu araya yayıldı.

Mühendislik yolları bu faturayı ilginç biçimde bölüyor: toplam satır 110’dan 128‘e çıkıyor, ama düğüm başına en çok satır 23’ten 18’e iniyor. Kiriş, üzerinden geçen bütün yolları iki düğümde yığıyordu; kirişten kaçınmak yolları uzatıp sayıyı büyütürken yükü de durumu da dağıtıyor. Bir bağdan kaçınmanın yalnız trafiği değil tablo yükünü de dengelediği yer burasıdır.

Kenarda Alınan Karar Kenarda Yenilenir

Son satır kopmayı ölçüyor. Kiriş koptuğunda ve etiket yolları yenilenmediğinde kırk paketin 26’sı ulaşıyor, 14’ü kara deliğe düşüyor, toplam adım 61’e iniyor. Tam tablo bakışı yine 40, etiket bakışı 26’ya iniyor — ölen paket bakış da harcamayı bırakır.

Beşinci satır aynı kopmayı her düğümde karar alan rejimde ölçüyor ve kader sayıları birebir aynı çıkıyor: 26 ulaştı, 14 kara delik, 61 adım. Şaşırtıcı değildir, çünkü iki rejim de aynı eski tabloyu ve aynı kopuk bağ kümesini kullanıyor. Ayrılan tek sütun bakış sütunudur: eski karar her düğümde yeniden alındığında 61 tam bakış, kenarda bir kez alındığında 40 tam bakış ve 26 etiket bakışı.

Kaderler aynı olsa da onarım aynı değildir. Her düğümde karar alan bir ağda tablolar birkaç yakınsama turunda kendini düzeltir ve düzeltme kopmanın yakınında başlar. Etiket yolunda ara düğümlerin düzeltebileceği hiçbir şey yoktur: hedefi bilmiyorlar, yalnız etiketin karşılığını biliyorlar. Onarım girişte olmak zorundadır ve giriş, kopmadan en uzak düğüm olabilir.

Kursun ölçü ekseni burada tersine döner. Kararı tek bir yere toplamak, o yerin anlaşmazlığını bütün yola yayar. Etiket, anlaşması gereken tablo sayısını bire indirir; karşılığında o tek tablonun eskimesi paketin tek arıza nedeni olur.

Özet

• Etiket anahtarlamada karar giriş düğümünde bir kez alınır ve pakete etiket olarak yazılır; ara düğümler hedefe hiç bakmaz, etiketi takas eder. Etiket hedefi değil yolu adlandırır ve bağ başına anlamlıdır.
• Bakış sayısı değişmez: aynı yol her düğümde karar alan rejimde 83 tam tablo bakışı, kenarda karar alan rejimde 40 tam bakış ve 43 etiket bakışı üretir. Değişen şey bakışın türü ve yolu belirleyen tablo sayısıdır.
• Etiket yolu en kısa olmak zorunda değildir: kirişten kaçan yollar adımı 83’ten 99’a çıkarır ve kirişten geçen paketi 14’ten 0’a indirir.
• Tutulan satır 56’dan 110’a çıkar; yönlendirme durumu hedef sayısıyla, etiket durumu yol sayısıyla büyür. Mühendislik yolları toplamı 128’e çıkarırken düğüm başına en çok satırı 23’ten 18’e indirir.
• Kiriş koptuğunda ve etiket yolu yenilenmediğinde 14 paket kara deliğe düşer. Aynı kopmada her düğümde karar alan rejim de 26 ulaştırıp 14’ünü kaybeder; ayrılan tek şey bakış dağılımı (61 tam bakışa karşı 40 tam ve 26 etiket) ve onarımın nerede başladığıdır — ara düğüm hedefi bilmediği için onarım girişte olmak zorundadır.

Sonraki Adım

Etiket 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ı. Peki iki düğüm arasındaki bağ fiziksel bir bağ değil de, başka bir ağın üzerinden kurulmuş mantıksal bir bağ olsaydı? Sonraki ders tünellerle kurulan mantıksal topolojiyi ölçer: böyle bir ağda tablo iki katmanda birden tutulur, iki katman ayrı ayrı yakınsar, ve paketin kaderi ikisinin birden anlaşmasına bağlıdır.