Marşrutlama alqoritmi

Optimallıq prinsipi

Spesifik alqoritmlərə başlamadan əvvəl, şəbəkə trafikini və ya topologiyasını nəzərə almadan optimal marşurtlar haqqında açıqlama verək. Bu açıqlama optimallıq prinsipi (Bellman, 1957) olaraq bilinir. Marşurtlayıcı (router) J , marşurtlayıcı İ-dən marşurtlayıcı K-a ən optimal yoldadırsa, onda J-dən K-a da ən optimal yolda eyni yoldan keçir. Bunu görmək üçün İ-dən J-ə r1 və marşurtun geri qalanına r2 marşurt bölünməsini edin. Əgər J-dən K-a r2-dən daha yaxşı bir yol varsa, onda İ-dən K-a marşurtu yaxşılaşdırmaq üçün r1-i seçirik.

Optimumluq prinsipi birbaşa nəticəsi olaraq, bütün mənbələrdən müəyyən bir hədəfə köklü bir ağac yaradıldığını görəbilirik. Belə bir ağaca istiqamətləndirici ağac deyilir və məsafə metriyi sıçramalarının sayı Şəkil 1(b) də göstərilmişdir. Bütün marşurtlama alqoritmlərinin məqsədi bütün marşurtlar üçün istiqamətləndirici ağacları kəşf etmək və istifadə etməkdir. 

Şəkil1. (a) Şəbəkə.(b)B marşurtu üçün istiqamətləndirici ağacdır.

İstiqamətləndirici ağacın bənzərsiz olmadığını unutmayın. Eyni yol uzunluqlarına sahib digər ağaclar da ola bilər. Bütün mümkün yolların seçilməsinə icazə versək, ağac DAG (Yönləndirilmiş Müstəqil Qraf-Directed Acyclic Graph) adı verilən daha ümumi struktur halına gəlir. DAG-ların dövrü yoxdur. Hər iki vəziyyətdə də istiqamətləndirici ağacları uyğun bir qısaltma olaraq istifadə edəcəyik. Hər iki vəziyyətdə yolların bir birinə qarışmadığı texniki ehtimalıyla əlaqəlidir. Bu səbəblə məsələn bir yoldakı bir nəqliyyat sıxlığı başqa keçid yoluna səbəb olmaz.

Bir istiqamətləndirmə ağacı əslində bir ağac olduğundan hərhansı bir dövr daxil deyil, bu səbəblə hər paket son və limitli sayda sıçramalarla göndərilir. Praktikada bu elə də asan deyil. Kanallar və marşurtlandırıcılar iş ərzində geri gələbilər və təkrar gedə bilər, bu səbəblə fərqli marşurtlandırıcılar mövcud topologiya haqqında fərqli fikirlərə sahib ola bilər. Optimumluq prinsipi və istiqamətləndirici ağacı digər marşurtlama alqoritmlərinin ölçüləbiləcəyi bir müqayisə nöqtəsi təmin edir.

Qısa yol alqoritmi

Şəbəkənin əskiksiz rəsmi verilən ən optimal yolları hesablamaq üçün sadə üsulla alqoritmləri marşurtlamaya başlayaq. Bütün marşurtlandırıcılar şəbəkənin bütün detallarını bilməsə də , tapmaq üçün dağınıq marşurtlama alqoritmi istifadə edir. İdeya şəbəkənin bir qrafını yaratmaqdır. Qrafın hər düyünü marşurtlandırıcını və hər kənar əlaqə xəttini və ya kanalı təmsil edir. Marşurtlandırıcı cütü arasında yolu seçmək üçün , alqoritm qrafda onlar arasında ən qısa yolu tapır.

Qısa yol alqoritm konsepsiyası bəzi açıqlamalara layiqdir. Yolun uzunluğunu ölçmək üçün sıçramaların sayını bilmək lazımdır. Bu metrikin istifadəsi , ABC və ABE bərabər uzunluqdadır (Şəkil 2). Başqa metrik isə kilometrlə ölçülən coğrafi uzunluqdur, hansı ki, ABC açıq-açıq ABE-dən uzundur. 

Şəkil 2.İlk 6 addım A ilə D arasında ən qısa yolu hesablamaqdır. Oxlar işləmə düyününü göstərir.

Bununla birlikdə sıçramalar və fiziki uzaqlıq xaricində bir çox başqa metrikdə mümkündür. Məsələn hər bir kənar saatlıq icralarla ölçülən standart bir test paketinin ortalama gecikməsi ilə etiketlənə bilər. Bu qraf etiketləmə ilə ən qısa yol, ən az sayda kənar və ya kilometr olan yolu deyil, ən sürətli olanıdır. Ümumi halda kənardakı etiketlər məsafə, ötürmə sürəti, ortalama trafik, əlaqə xərci , ölçülən gecikmə və digər faktorların funksiyası olaraq hesablana bilir. Ağırlıq funksiyasını dəyişdirərərək, alqoritm daha sonra bir çox kriteriyadan hərhansı birinə görə ölçülən "ən qısa" yolu və ya bir kriteriya kombinasiyasını hesablayır.

Bir qrafın iki düyünü arasında ən qısa yolu hesablamaq üçün bir çox alqoritm vardır. Bunlardan Dijkstra (1959)-a aiddir və bir mənbə ilə şəbəkədəki bütün hədəflər arasındakı ən qısa yolları tapır. Hər düyün ən yaxşı bilinən yol boyunca mənbə düyündən uzaqlığı ilə etiketlənmişdir. Məsafələr ötürmə sürəti və gecikmə kimi real miqdarlarla bağlıdırsa, neqativ olmamalıdır. Başlanğıcda heç bir yol bilinmir, bu səbəblə bütün düyünlər sonsuz olaraq etiketlənir. Bir etiket keçici və ya qalıcı ola bilir. Başlanğıcda bütün etiketlər keçici deyildir. Bir etiketin kəşfedildikdə, qalıcı hala gətirilir və bundan sonra heç bir zaman dəyişdirilmir.

Etiketləmə alqoritmini necə işlədiyini göstərmək üçün Şəkil 2-dəki istiqamətləndirilməmiş qrafa baxın A-dan D-ə ən qısa yolu tapmaq istəyirik. Əvvəlcə düyün A-nı işarələyirik. Sonra A-ya bitişik düyünlərin hər birini yoxlayırıq, hər birinin A-ya olan uzaqlığı ilə yenidən etiketliyirik. A-ya bitişik düyünlərin hər birini yoxladıqdan sonra bütün qrafda keçici olaraq etiketli bütün düyünləri yoxladıq və Şəkil 2 (b)-də göstərildiyi kimi ən kiçik etiketli qalıcı olanı yaradırıq. Bu yeni iş düyünü olur. İndi B-dən başlayıb bütün qonşu düyünləri yoxlayırıq. B üzərindəki etiketin bütünü və B-dən düşünüləcək düyünə olan uzaqlığı bu düyün üzərindəki etiketdən daha kiçiksə, düyünün yennidən etiketlənməsi üçün daha qısa bir yolumuz var. İş düyününə bitişik olan bütün düyünlər yoxandıqdan və mümkün olduğunca keçici etiketlər dəyişdirildikdən sonra bütün qraf ən kiçik dəyəri olan keçici olaraq etiketlənmiş düyün üçün axtarılır. Bu düyün qalıcı edilir və sonrakı tur üçün iş düyünü olur. Şəkil 2-də alqoritmin ilk altı addımı göstərilir.

Alqoritmin niyə işlədiyini görmək üçün şəkil 2 (c)-ə baxın. Bu nöqtədə sadəcə E ni qalıcı etdik. AXYZE (bəzi X və Y üçün) ABE-dən daha qısa bir yol olduğunu düşünək. İki ehtimal var: ya Z düyünü əvvəlcədən qalıcı hala gətirilmiş ya da hələ yaradılmamışdır. Varsa, E yoxlandı, bu səbəplə AXYZE yolu diqqətimizdən qaçmadı və bu səbəplə qısa yol ola bilməz. İndi Z-nin keçici olaraq etikletləndiyi vəziyyətini düşünün. Z-dəki etiket E-dəki dəyərdən böyük və ya bərabərsə, AXYZE ABE-dən daha qısa bir yol olmaz. Etiket E-ninkindən daha kiçiksə, E-nin deyil Z-nin əvvəl qalıcı olacağı və E-nin Z-dən yoxlanılmasına icazə verir. Bu alqoritm şəkil 3 də göstərilib.

Dalğa şəklində yayılma

Bir marşurtlama alqoritmi tətbiq edildikdə, hər marşurtlayıcı , şəbəkənin tam rəsmi deyil, lokal biliyə əsaslanan qərarlar verməlidir. Bəsit bir lokal üsul, hər gələn paketin gəldiyi xət xaricindəki hər gedən xətt üzərində göndərildiyi dalğadır. Təbii ki, dalğa əməliyyatını dayandırmaq üçün bəzi tədbirlər alınmayan vaxt ərzində dalğa əslində paketlərin sayını sonsuz sayda generasiya edir. Belə bir tədbirin alınması hər bir sıçramada azaldılan hər paketin başlığında olan və sayğac sıfıra yaxınlaşdıqda atılan bir sıçrama sayğacına sahib olmaqdır. İdeal olaraq sıçrama sayğacı mənbədən hədəfə gedən yolun nə qədər uzun olduğunu bilmirsə, sayğacı ən pis vəziyyətdə şəbəkənin tam diametrinə başlada bilər.

Sıçrama sayı ilə dalğalanma , sıçrama sayı artdıqca və marşurtlayıcılar daha əvvəl gördükləri paketləri çoxaltdıqca exponensial sayda təkrarlanan paketlər yarada bilir. Dalğalanmadan çıxmaq üçün daha yaxşı üsul marşurtlayıcıların hansı paketlərin dalğalanacağını təqib etmələrini təmin etmək və onları ikinci dəfə göndərməkdən qaçınmaqdır. Bu məqsədə çatmaq üçün bir yol , mənbə marşurtlayıcının, hostlarından aldığı hər paketə bir sıra nömrəsi qoymağını təmin etməkdir. Hər bir marşurtlayıcı mənbə marşurtlayıcı başına bir listə ehtiyac duyur, bu mənbədən hansı sıralamadakı nömrələrin görüldüyünü deyir. Listdə gələn bir paket varsa, dalğalanmır. 

//Şəkil 3
#define MAX NODES 1024 /* düyünlərin maksimum sayı */ 
#define INFINITY 1000000000 /* hər maksimum yoldan daha böyük bir ədəd*/ 
int n, dist[MAX NODES][MAX NODES]; /* dist[i][j] i dən jə olan uzaqlıq */
 void shortest path(int s, int t, int path[])
 { struct state { /* üzərində işlənilən yol */ 
int predecessor; /* əvvəlki düyün */ 	
int length; /* mənbədən bu düyünə olan uzunluq */ 
enum {permanent, tentative} label; /* etiket vəziyyəti */ 
} state[MAX NODES]; 
int i, k, min; 
struct state *p; 
for (p = &state[0]; p < &state[n]; p++) { /* vəziyyəti başlat*/ 
p->predecessor = −1;
 p->length = INFINITY;
 p->label = tentative;
 }
 state[t].length = 0; state[t].label = permanent;
 k = t; /* k ilk işləmə düyünüdür */ 
do { /* k-dan yaxşı yol varmı? */
 for (i = 0; i < n; i++) /* bu qrafın n düyünü var */ 
if (dist[k][i] != 0 && state[i].label == tentative) { 
if (state[k].length + dist[k][i] < state[i].length) { 
state[i].predecessor = k;
 state[i].length = state[k].length + dist[k][i]; 
} 
}
/* Ən kiçik etiketli keçici olaraq etiketlənmiş düyünü tapın */ 
k = 0; min = INFINITY;
 for (i = 0; i < n; i++) 
if (state[i].label == tentative && state[i].length < min) {
 min = state[i].length;
 k = i; 
} 
state[k].label = permanent;
 } while (k != s);
/*Yolu çıxış massivinə kopyalayın */ 
i = 0; k = s;
 do {path[i++] = k; k = state[k].predecessor; } while (k >= 0);
}

Listin limitləri xaricində böyüməsini qabaqlamaq üçün, hər listə bir sayğac, yəni k ilə genişlədilməlidir, yəni k ilə keçən bütün sıra ədədlər görülür. Dalğalanma bir çox paketi göndərmək üçün praktik deyildir, ancaq bəzi önəmli istifadələri vardır. Birincisi, bir paketin şəbəkədəki hər düyünə göndərilməsini təmin edir. Paketə ehtiyac duyan tək bir hədəf varsa, bu boşa ola bilər, ancaq məlumat yaymaq üçün effektivdir. Simsiz kabellərdə bir stansiya tərəfindən alına bilər. İkinci olaraq dalğalanma böyük ölçüdə sağlamdır. Dalğalanma da təşkiletmə yolunda çox az şey tələb edir. Bu dalğalanma daha effektiv ancaq tərtibat yolunda daha çox ehtiyac duyulan digər marşurtlama alqoritmləri üçün bünovrə olaraq istifadə oluna bilər. Dalğalanma digər marşurtlama alqoritmlərinin qaşılaşdırıla biləcəyi bir metrik olaraq da istifadə oluna bilər. Hər ehtimal paralel olaraq seçildiyindən dalğalanma hər zaman ən qısa yolu seçər. Nəticədə başqa heçbir alqoritm daha qısa bir gecikmə yaratmaz.

Məsafə Vektor Marşurtlama

Kompüter şəbəkələri dalğalanmaya görə daha qarışıq olan dinamik marşurtlama alqoritmlərini istifadə edir, ancaq keçərli topologiya üçün ən qısa yolları tapmaları səbəbiylə daha effektiv olurlar. İki dinamik alqoritm özəlliklə də məsafə vektoru marşurtlaması və kanal vəziyyəti marşurtlama ən populyardır. Bir məsafə vektoru marşurtlama alqoritmi hər bir marşurtlayıcının hər bir varış nöqtəsinə ən yaxşı bilinən məsafəyi verən bir cədvəli (vektoru) saxlayan və ora getmək üçün hansı əlaqəni istifadə etməsini təmin edir. Bu cədvəllər qonşularla informasiya alış-verişində olaraq yenilənir. Sonunda hər marşurtlayıcı hər hədəfə çatmaq üçün ən yaxşı əlaqəni bilir.

Məsafə vektoru marşurtlama alqoritmi (Bellman 1957 və Ford və Fulkerson,1962)inkişaf etdirən tədqiqatçılardan sonra, əsasən Belman-Ford marşurtlama alqoritmi kimi yayılıb. Orijinal ARPANET marşurtlama alqoritmiydi və İnetnetə RİP adı altında istifadə edilirdi. Məsafə vektor marşurtlamasında hər marşurtlayıcı şəbəkədəki hər marşurtlayıcı üçün bir giriş saxlayan və tərəfindən indekslənmiş bir marşurtlama cədvəli saxlayır. Bu giriş iki bölümdən ibarətdir: o hədəf üçün istifadə olunacaq seçim edilən gedən xətti və bu hədəfə olan məsafəni təxmin edən. Ən qısa yolları hesablamaq üçün müzakirə etdiyimiz kimi sıçrama sayı olaraq və ya başqa bir metrik istifadə edərək ölçülə bilər. Marşurtlayıcının qonşularının hər birinə "məsafə" -ə sahib olduğu düşünülür. Metrik sıçrarsa, məsafə sadəcə bir sıçrama məsafəsindədir. Metrik yayılma gecikməsidirsə, marşurtlayıcı birbaşa alıcını zaman ştamplarıyla göstərdiyi və ola bildiyincə sürətli geri göndərdiyi özəl ECHO paketləriynən ölçülə bilir. Misal olaraq gecikmənin istifadə olunduğu və marşurtlayıcıının qonşularının hər birinə olan gecikməni bildiyini düşünək. Hər T msandə bir dəfəhər marçurtlayıcı hər qonşusuna təxmini gecikmələrin bir listini bir bir hədəfə göndərir. Həmçinin hər qonşudan bənzər bir list alır. Bu cədvəllərdən birinin qonşusu X-dən gəldiyini düşünək. X-in marşurtlayıcını nə qədər müddət keçməsi lazım olduğunu təxmin etməsi. Marşurtlayıcı, X-in gecikməsinin m msan olduğunu bilirsə, X vasitəsilə marşurtlayıcıya Xi+m msan cinsindən çata biləcəyini bilər. Hər qonşu üçün bu hesablamanı reallaşdıraraq, bir marşurtlayıcı hansı təxminin ən yaxşı göründüyünü tapa bilər və bu təxmini və əlaqəli marşurtlamanı yeni marşurtlandırma cədvəlində istifadə oluna bilər. Hesablamada köhnə marşurtlama cədvəlinin istifadə olunmadığını unutmayın.

Bu yeniləmə prosesi Şəkil 4 də göstərilir. Bölüm (a) bir şəbəkə göstərir. (b) bölümünün ilk dörd sütunu, marşurtlayıcının qonşularından gələn gecikmə vektorlarını göstərir. A, B-ə 12 ms gecikmə, C-ə 25ms gecikmə, D-ə 40 ms gecikmə verilir. J qonşularına sırayla 8, 10, 12 və 6 msan olaraq A, İ, H və K gecikmələrini ölçdü və ya təxmin etdi.

Şəkil 4. (a) Şəbəkə (b) A, İ, H, K dan girişlər və J üçü yeni marşurtlama cədvəli

J-nin marşurtlayıcı G-ə olan yeni marşurtunu necə hesabladığını düşünün. 8 ms də A-a çata biləcəyini bilir və ayrıca A, 18 ms-də G-ə çata biləcəyini iddia edr, bu səbəblə J 26 msan-lik gecikməyə güvənə biləcəyini bilir. Bənzər şəkildə G, İ, H vəK üzərindən 41 (31 + 10), 18(6 + 12), və 37(31 + 6) msan gecikməsini hesaplayır, sırayla. Bu dəyərlərin ən yaxşısı 18 dir, bu səbəblə marşurtlama cədvəlində G gecikməsinin 18 msan olduğu və istifadə oluna biləcək yolun H üzərindən olduğu bir giriş edər. Eyni hesablama digər bütün hədəflər üçün yeni marşurtlama ilə reallaşdırılır . Cədvəlin son sütununda göstərilən cədvəl. 

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.-

1. Qonşuları aşkar etmək və onların şəbəkə adresini öyrənmək
2. Qonşularının hər birinə məsafəni təyin etmək
3. Öyrəndiklərindən ibarət paket yaratmaq
4. Digər marşrutlayıcılara bu paketi göndərmək və onlardan paketləri qəbul etmək
5. 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əm də ö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ətlə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ətlə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.

Xarici keçid.

Computer Networks, 5th Edition, paraqraf 5.2.1, 5.2.2, 5.2.3, 5.2.4