Bu yazını oxumağa başlamazdan əvvəl, Bellman - Ford alqoritminə görə yolun hesablanması ilə bağlı materialla tanış olmağı məsləhət görürük.
Diffuziya yeniləmə alqoritmi (yayılmış yeniləmə alqoritmi -Dual), əvvəlcə yayılmış bir şəbəkədə həyata keçirilmə üçün nəzərdə tutulmuş iki alqoritmlərdən biridir. Bununla yanaşı, alqoritmin son avtomatında olan nailiyyət və topologiya haqqında məlumatı da aradan qaldırmasıdır. Burada müzakirə olunan digər alqoritmlər, protokolun həyata keçirilməsinin istəyi ilə məlumatların çıxarılmasını tərk edir və alqoritmin özündə alqoritmin işinin bu tərəfini nəzərə almır.
1993-cü ilə qədər, Bellman-Ford və Dijkstra bir neçə marşrutlaşdırma protokollarında paylanmış alqoritmlər kimi həyata keçirilmişdir. Bu erkən tətbiqlər və yerləşdirmə nəticəsində əldə edilən təcrübə, "ikinci dalğa" və şəbəkə keçid şəbəkələrində marşrutlaşdırma problemi ilə bağlı əks olunma probleminin və ikili işin görünüşünə səbəb oldu.
Dual paylanmış bir alqoritm kimi hazırlandığı üçün, işini şəbəkədəki işini təsvir etmək yaxşıdır. Bu məqsədlə 8 və 9-cu rəqəmlər istifadə olunur. İkili izah etmək üçün bu nümunə üç istiqamət axınında izləniləcək və sonra eyni təyinat maddələri üçün mövcudluq vəziyyətində dəyişikliklər emal olunur. Birinci misalda, alternativ bir yol olduqda, ancaq aşağı axan bir yol yoxdur, ikincisi alternativ bir yol və aşağı qonşu olduqda iddianı nəzərdən keçirəcəkdir.
Şəkil 8-də, baxımından D öyrənin a:
- A D-nin iki yolu öyrənir:
- A b yolunu B-yə tanımır, çünki B varisi kimi istifadə edir:
- Mövcud yolları müqayisə edir və döngəsiz ən qısa yolu seçir:
- Onların hər hansı birinin aşağı salınmasının olub olmadığını müəyyən etmək üçün qalan yolları yoxlayır:
Bunu bilir, çünki c 3-ə bərabər olan yerli metrikası ilə mar marşrutunu elan edir.
Bir topologiyası masasında yerli bir metrik c saxlayır.
Nəticə etibarilə, C-də yerli dəyəri və A-da yerli dəyərini bilir.
- 3 (c) = 3 (a dəyəri) = 3 (a), buna görə də bu yol döngə ola bilər, buna görə də C, C-nin məqsədəuyğunluğunun vəziyyətini təmin etmir. C aşağı axın qonşuları kimi etiketlənmir.
Dual-da aşağı axın qonşuları mümkün varislər adlanır. Tutaq ki, kanal [A, H] işləmir. Dual dövri yeniləmələrə etibar etmir, buna görə də etibarlı məlumatlarla başqa bir yeniləməni gözləyə bilməz. Əksinə, alternativ bir yolu fəal şəkildə izləməlidir. Beləliklə, bu, alternativ bir yolun yayılmış bir aşkarlanması prosesidir. Kanal [A, H] işləmirsə, yalnız D:
- Mümkün olan varislər üçün yerli masanız (aşağıya doğru qonşular) yoxlayır.
- Mümkün olan varislər yoxdur, buna görə də d döngəsiz bir alternativ yol tapmalıdır (varsa).
- D L döngələri olmadan alternativ bir yolun olub olmadığını müəyyən etmək üçün hər qonşuya sorğu göndərir.
- C-də:
- B-də:
- A bu cavabları alır:
Şəkil 9-da, təyinat (d) maddəsi H ilə birlikdə köçürüldü. Bu ikinci nümunədə istifadə ediləcəkdir.
Bu nümunədə mümkün bir varisi var (aşağı qonşu).
Diqqət nöqtəsindən D öyrənmək a:
- A D-nin iki yolu öyrənir:
- A B vasitəsilə heç bir yolu tanımır:
- Mövcud yolları müqayisə edir və döngəsiz ən qısa yolu seçir:
- Onların hər hansı birinin aşağı salınmasının olub olmadığını müəyyən etmək üçün qalan yolları yoxlayır:
Kanal [A, C] işləmirsə, sadəcə aşağıdakıları nəzərə alsaq:
- Mümkün bir varisi üçün yerli topologiyanın cədvəlini yoxlayır.
- Mümkün olan varis H-yə aiddir.
- A yerli masasını ən yaxşı şəkildə birləşdirir.
- Qonşularına bir yeniləmə göndərir, nailiyyətin dəyəri 3-dən 4-ə qədər dəyişdiyini qeyd etdi.
Görə biləcəyiniz kimi, mümkün bir varis olduqda, onsuz daha sürətli və daha asan olduqda emal. Marşrutlaşdırma protokolunun ikiqat (xüsusən EIGRP) istifadə edərək yerləşdirildiyi şəbəkələrdə əsas dizayn məqsədlərindən biri mümkün bir varis olmadığı halında yaranan istənilən sorğuların həcmini məhdudlaşdıracaqdır. Sorğu sahəsi, ikiqat alqoritmin necə tez başa çatdığını və buna görə də şəbəkənin nə qədər sürətlə necə başa çatdığını əsas müəyyənləşdirən amildir.
Şəkil 10 əsas bitmiş ikili maşın göstərir.
Marşruta daxil olan şeylər daha da pisləşir (marşrutun pozulması) ola bilər:
- Bağlı kanal və ya qonşunun uğursuzluğu
- Daha yüksək metrik ilə bir marşrut üçün bir yeniləmə əldə etmək
- Cari varisdən sorğu almaq
- Bir qonşudan yeni bir yol almaq
- Yeni bir qonşu tapıldı, həm də əldə edə biləcəyi marşrutlar
- Marşrut pisləşəndə bütün istəkləri qonşulara göndərin
