Marşrutlama alqoritmləri

Bu məqalə Marşrutlama alqoritmi məqaləsinə çox yaxındır və hər ikisinin eyni başlıq altında birləşdirilməsi mümkündür.

Kanal vəziyyəti alqoritmi (Link State routing)

Məsafə vektoru alqoritmi KV(kanal vəziyyəti) alqoritmi onu əvəz etməzdən əvvəl 1979-cu ilə kimi ARPANET-də istifadə olunurdu.Bu alqoritmin istifadəsinin azalmasına səbəs isə şəbəkə topologiyası dəyişdikdə alqoritmin yığılması üçün çox zaman tələb olunması idi.Nəticədə bu alqoritm KV alqoritmi ilə əvəz olundu.KV alqoritminin geniş şəbəkələrdə və bu gün istifadə etdiyimiz internetdə istifadə olunan İS-İS və OSPF növləri var.

Bu alqoritmin əsasında 5 əsas ideya durur.Marşrutlayıcı bu alqoritm ilə işləməsi üçün aşağıdakı idayaları tətbiq etməlidir.-

Qonşuları aşkar etmək və onların şəbəkə adresini öyrənmək
Qonşularının hər birinə məsafəni təyin etmək
Öyrəndiklərindən ibarət paket yaratmaq
Digər marşrutlayıcılara bu paketi göndərmək və onlardan paketləri qəbul etmək
Hər bir marşrutlayıcıya olan ən qısa məsafəni hesablamaq

Bu yolla bütün topologiya marşrutlayıcıları tanıyır.Dijkstra alqoritmi marşrutlayıcılar arasında olan ən qısa yolu tapmaq üçün istifadə olunur.Aşağıda dediklərimizi genişləndirək-

Qonşuların öyrənilməsi

Marşrutlayıcı işə başlayan zaman ilk olaraq qonşuları haqqında məlumatları öyrənir.Bu hər bir p-t-p xətti ilə xüsusi "SALAM" paketini göndərməklə olur.Sonra isə sonda olan marşrutlayıcının adını bildirdiyi cavab məktubunun göndərilməsini gözləyir.

İki və ya daha çox marşrutlayıcı genişyayımlı rabitəyə qoşulubsa,onda hal bir qədər daha mürəkkəb olur.Şəkil a-da A,C və F marşrutlayıcıları genişyayımlı lokal kompüter şəbəkəsinə birləşib.Və bu marşrutlayıcılar həmdə özləri də başqa marşrutlayıcılarla da əlaqədədirlər.Genişyayımlı lokal kompüter şəbəkəsi hər bir əlaqədə olan marşrutlayıcılara rabitəni təmin edir.Amma belə modelləmədə p-t-p əlaqələri topologiyanın ölçüsünü artırır və əsassız və lazımsız məktub və ya paketlərin göndərilməsinə səbəb olur.Lokal kompüter şəbəkələ modellərindən biri də onu özü daxilində bir düyüm kimi qəbul etməkdir.Biz şəkil b-də A,C və F düyünlərinə birləşmiş yeni və süni N düyününü yaradırıq.Və N burada marşrutlama protokolunda lokal kompüter şəbəkəsi rolunu oynayır.Və hər bir marşrut bu N düyümündən keçir.Misal üçün A-dan C-yə ANC xətti marşrutdur.

Rabitənin qiymətləndirilməsi

KV alqoritmini hər bir rabitə üçün ən qısa yolu və metrik qiymətini tələb edir.Bu qiymət avtomatik qeyd olunmalıdır və ya şəbəkə operatoru tərəfindən qiymətləndirilirməlidir.Adətən bu burada qiymət rabitənin zolaq genişliyinin tərs qiyməti kimi qeyd olunur.Misal üçün 1Gbit/s Ethernet 1 metrik, 100 Mgps isə 10 metrik qiymətləndirilir.Bu halda isə yüksək həcmli xətlər daha yaxşı seçim olur.

Əgər şəbəkə coğrafi olaraq müxtəlif yerlərdə yayılıbsa,rabitə gecikməsi qiymətləndirməyə təsir edir və bu zaman qısa xətlər daha yaxşı seçim ola bilər.Bu gecikməni müəyyənləşdirmək üçün bu xətt üzərindən ECHO paketi göndəmək lazımdır.Bu paketin geri dönüş vaxtını bu zamanı ikiyə bölməklə tapmaq olar.

KV paketlər düzəltmək

İlk olaraq informasiyanın alınıb verilməsi üçün bu informasiyanın toplanması lazımdır.Sonraki addımda hər bir marşrutlayıcının informasiyasından ibarət paket düzəltmək lazımdır. Paket göndərənin ilə başlayır və sıra nömrəsi,yaşı və qonşuların siyahısı ilə davam edir.Həmçinin qonşuya verilən qiymət də verilir.Misal olaraq aşağıdakı şəbəkəni göstərmək olar.KV paketlər düzəltmək asandır.Esas hissə onları nə zaman düzəltməyi müəyyən etməkdir.Bir variant sabit intervallarda periodik olaraq paketlərin düzəldilməsidir.Başqa bir variant isə informasiya bir xətt və ya qonşuya göndərilərkən və ya xüsusiyyətlərini əhəmiyyətli dərəcədə dəyişərkən paketləri yaratmaqdır.

Paketlərin paylanması

Alqoritmin ən maraqlı hissəsi isə paketlərin paylanmasıdır.Marşrutlayıcı hər bir paketi sürətli və düzgün bir şəkildə qəbul etməlidir.Əgər marşrutlayıcılar müxtəlif topologiya versiyalarını istifadə edirlərsə,onda bu marşrutlayıcılarda əlaqənin pozulması və digər problemləri yarada bilər.

İlk olaraq paylanma alqoritmlərinin sadə xüsusiyyətlərindən danışaq.Marşrutlayıcılardan KV paketlərin göndərilməsinin fundamental ideyası onları dalğa şəklində göndərməkdir.Dalğaları nəzarətdə saxlamaq üçün hər paket göndəriləndə sıra nömrəsi bir vahid artır .Marşrutlayıcı bildikləri paket və xəttləri yadda saxlayırlar və əgər eyni paket və ya onun sürəti gələrsə,onda bu paket qəbul olunmur.Əgər yeni paket gələrsə,onda gəldiyi xətt çıxmaqla bütün xəttlərə ötürülür. Əgər paket ən yüksək sıra nömrəsindən aşağı sıra nömrəsi ilə gələrsə,bu zaman köhnə verilən kimi qəbul olunub rədd edilir.

Alqoritmin bəzi problemləri də vard.Amma bu problemlər nəzərə alınmaqla idarə oluna bilir.İlki əgər sıra nömrəsi nəzərə alınan ən böyük ədədə bərabər olarsa,onda problem yaranacaq.Bunun üçün 32 bitlik sıra nömrəsindən istifadə etmək lazımdır.Belə halda belə şəraitin baş verməsi üçün 137 il lazım olacaq.

İkinci problem isə marşrutlayıcı sıfırlanarsa,bu zaman o sıra nömrəsinin yolunu itirəcək.Əgər sıfırdan başlayarsa bu zaman ondan sonraki sürət kimi rədd olunacaq.

Üçüncü problem isə sıra nömrələrində xəta ola bilər və qarışa bilər.Bu zaman nəzərə alınan sıra nömrəsi gələnə qədər paketlər köhnə verilən kimi rədd olunacaq.

Bu problemlərin həlli isə hər sıra nömrəsində sonra hər paketin yaşına daxil olub onu saniyədə bir vahid azaltmaqdır.Əgər yaş sıfra bərabər olarsa,onda marşrutlayıcı gələn informasiya rədd olunur.İlkin dalğa prosesində hər bir marşrutlayıcı tərəfindən yaş sahəsi azaldılır, belə olduqda heç bir paket itə və ya zamanı qeyd edilməmiş paket qəbul oluna bilməz

Şəkildə B marşrutlayıcısının verilənlər strukturu təsvir edilmişdir.Hər bir sətir son gələnlər və tam emal olunmamış olan paketlərə uyğundur.Cədvəldə paketin mənbəyi,sıra nömrəsi,yaşı və verilənləri qeyd olunub.Göndərmə bayrağı paketin hara göndərildiyini,ACK bayrağı isə onun hansı marşrutlayıcılarda tanınmalı olduğunu bildirir.

İerarxik marşrutlama alqortimi

Şəbəkənin ölçüsü böyüdükcə onun marşrutlama cədvəli də onunla birlikdə genişlənir.Ancaq marşrutlayıcının yaddaşını artırmaq sərfəli olmaya bilər.Verilənlərin yoxlanılması üçün CPU-nun yoxlama vaxtı artır.Status hesabatları üçün daha geniş zolaq genişliyi lazımdır.Müəyyən genişlənmədən sonra şəbəkələri telefon şəbəkələri kimi ierarxik hissələrə bölmək lazım gəlir.

İerarxik marşrutlamada biz marşrutlayıcıları region adlandıracağımız qruplara bölürük.Fərqli şəbəkələr bir-birinə qoşulduqda, şəbəkədə marşrutlayıcıları digərlərinin topoloji quruluşunu bilməkdən azad etmək üçün hər birini ayrı bir regiona aid etmək olar.Hər bir marşrutlayıcı öz regionu daxilində olan məlumatları bilir.

İki səviyyəli ierarxiyada region bölgülərə,bölgülər zonalara, zonalar qruplara bölünür.Çoxsəviyyəli şəbəkəyə Berkeley,Kariforniyadan marşrutlaşdırılan Malindi,Kenya paketini misal göstərmək olar. Berkeley marşrutlayıcısı məlumatı Los-Anceles marşrutlayıcısına göndərir.Sonra Nyu-York marşrutlayıcısına yönləndirilir. Nayrobi şəhərində olan marşrutlayıcıya bütün trafikləri yönləndirmək üçün New York yönləndiricisi proqramlaşdırılmış olur.

Şəkildə beş regionu olan ikisəviyyəli ierarxik şəbəkə göstərilmişdir.Burada ierarxiyadan istifadə etdikdə 17 marşrut sayı 7-yə düşür.Və Region 2-nin marşrutları 1C-3B və 1B-2A xətti üzrə paylanır.Amma marşrut sayının azalması yolun uzanmasına gətirib çıxara bilir.Misal üçün 1A -dan 5C-yə olan yol 1C-3B xətti ilə gedir.Amma 1B-2A daha qısa yoldur.Səbəbi isə marşrutllayıcıların çox hissəsinin 1C-2B yolundan istifadə etməsidir.Çünk burada bir regiondan söhbət gedir və daha çox marşrutlayıcı bu xəttdən istifadə edir.

Sual oluna bilər ki,şəbəkə böyüdükdən sonra neçə ierarxiyaya bölünməlidir.Bu marşrutlayıcıların sayından asılıdır.720 marşrutlayıcıdan ibarət şəbəkədə ierarxiya yoxdursa,bu zaman hər bir marşrutlayıcı üçün 720 cədvəl qurulmalıdır.Əgər 30 bölgüdən ibarət 24 regiona bölünsə,onda 53 marşrutlama cədvəli qurulmalıdır.Və optimal ierarxiya sayının düsturunu Kleinrock və Kamoun vermişdir- lnN.Burada N - marşrutlayıcıların sayıdır.

Genişyayımlı marşrutlama

Bir çox tətbiqetmədə hostlar məlumatı bütün digər hostlara da göndərməlidir.Bütün hostlara eyni zamanda paketləri göndərmək genişyayımlı marşrutlama adlanır.Genişyayımlı marşrutlama üçün bir çox metod var.

Bir genişyayım metodunda şəbəkədən hər bir təyinata paketi göndərmək üçün heç nə tələb olunmur.Bu yavaş metoddur və mənbədən bütün təyinatların siyahısı tələb olunur.Bu metod çox istifadə olunmasına baymayaraq praktikada çoxlu problemlər yaradır.Çoxtəyinatlı marşrutlama metodunda hır bir paketin təyinatları siyahısı və təyinatları göstərən bit xətirəsi olur.Paket marşrutlayıcıya çatdıqda marşrutlayıcı bütün lazımi çıxış xətlərinin müəyyən edilməsi üçün bütün istiqamətlərini yoxlayır. Marşrutlayıcı istifade edilen hər bir xətt üçün marşrutun sürətini yaradır və hər bir paketə ancaq bu xəttdə istifadə olunacaq təyinatları daxil edir.

Paketləri dalğalar şəklində yaymaq genişyayım metodlarından biridir.Hər bir mənbəyə bir sıra nömrəsi versək,onda paketlerin yayılması daha sadə olacaq.

İstifadə olunan mənbə

Andrew S. Tanenbaum, David J. Wetherall, Computer Networks, 5th edition, 2010.