fbpx
Wikipedia

Marşrutlama alqoritmi

May 10, 2023

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

== 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 əksiksiz 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ə ehtiyyac 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.Orjinal 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. 

Xarici keçid.

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

May 10, 2023
marşrutlama, alqoritmi, məqalə, marşrutlama, alqoritmləri, məqaləsinə, çox, yaxındır, hər, ikisinin, eyni, başlıq, altında, birləşdirilməsi, mümkündür, məqaləni, vikiləşdirmək, lazımdır, lütfən, məqaləni, ümumvikipediya, redaktə, qaydalarına, uyğun, şəkildə, t. Bu meqale Marsrutlama alqoritmleri meqalesine cox yaxindir ve her ikisinin eyni basliq altinda birlesdirilmesi mumkundur Bu meqaleni vikilesdirmek lazimdir Lutfen meqaleni umumvikipediya ve redakte qaydalarina uygun sekilde tertib edin Optimalliq prinsipi Spesifik alqoritmlere baslamadan evvel sebeke trafikini ve ya topologiyasini nezere almadan optimal marsurtlar haqqinda aciqlama verek Bu aciqlama optimalliq prinsipi Bellman 1957 olaraq bilinir Marsurtlayici router J marsurtlayici I den marsurtlayici K a en optimal yoldadirsa onda J den K a da en optimal yolda eyni yoldan kecir Bunu gormek ucun I den J e r1 ve marsurtun geri qalanina r2 marsurt bolunmesini edin Eger J den K a r2 den daha yaxsi bir yol varsa onda I den K a marsurtu yaxsilasdirmaq ucun r1 i secirik Optimumluq prinsipi birbasa neticesi olaraq butun menbelerden mueyyen bir hedefe koklu bir agac yaradildigini gorebilirik Bele bir agaca istiqametlendirici agac deyilir ve mesafe metriyi sicramalarinin sayi Sekil 1 b de gosterilmisdir Butun marsurtlama alqoritmlerinin meqsedi butun marsurtlar ucun istiqametlendirici agaclari kesf etmek ve istifade etmekdir Sekil1 a Sebeke b B marsurtu ucun istiqametlendirici agacdir Istiqametlendirici agacin benzersiz olmadigini unutmayin Eyni yol uzunluqlarina sahib diger agaclar da ola biler Butun mumkun yollarin secilmesine icaze versek agac DAG Yonlendirilmis Musteqil Qraf Directed Acyclic Graph adi verilen daha umumi struktur halina gelir DAG larin dovru yoxdur Her iki veziyyetde de istiqametlendirici agaclari uygun bir qisaltma olaraq istifade edeceyik Her iki veziyyetde yollarin bir birine qarismadigi texniki ehtimaliyla elaqelidir Bu sebeble meselen bir yoldaki bir neqliyyat sixligi basqa kecid yoluna sebeb olmaz Bir istiqametlendirme agaci eslinde bir agac oldugundan herhansi bir dovr daxil deyil bu sebeble her paket son ve limitli sayda sicramalarla gonderilir Praktikada bu ele de asan deyil Kanallar ve marsurtlandiricilar is erzinde geri gelebiler ve tekrar gede biler bu sebeble ferqli marsurtlandiricilar movcud topologiya haqqinda ferqli fikirlere sahib ola biler Optimumluq prinsipi ve istiqametlendirici agaci diger marsurtlama alqoritmlerinin olculebileceyi bir muqayise noqtesi temin edir Mundericat 1 Qisa yol alqoritmi 2 Dalga seklinde yayilma 3 Mesafe Vektor Marsurtlama 4 Xarici kecid Qisa yol alqoritmi Redakte Sebekenin eksiksiz resmi verilen en optimal yollari hesablamaq ucun sade usulla alqoritmleri marsurtlamaya baslayaq Butun marsurtlandiricilar sebekenin butun detallarini bilmese de tapmaq ucun daginiq marsurtlama alqoritmi istifade edir Ideya sebekenin bir qrafini yaratmaqdir Qrafin her duyunu marsurtlandiricini ve her kenar elaqe xettini ve ya kanali temsil edir Marsurtlandirici cutu arasinda yolu secmek ucun alqoritm qrafda onlar arasinda en qisa yolu tapir Qisa yol alqoritm konsepsiyasi bezi aciqlamalara layiqdir Yolun uzunlugunu olcmek ucun sicramalarin sayini bilmek lazimdir Bu metrikin istifadesi ABC ve ABE beraber uzunluqdadir Sekil 2 Basqa metrik ise kilometrle olculen cografi uzunluqdur hansi ki ABC aciq aciq ABE den uzundur Sekil 2 Ilk 6 addim A ile D arasinda en qisa yolu hesablamaqdir Oxlar isleme duyununu gosterir Bununla birlikde sicramalar ve fiziki uzaqliq xaricinde bir cox basqa metrikde mumkundur Meselen her bir kenar saatliq icralarla olculen standart bir test paketinin ortalama gecikmesi ile etiketlene biler Bu qraf etiketleme ile en qisa yol en az sayda kenar ve ya kilometr olan yolu deyil en suretli olanidir Umumi halda kenardaki etiketler mesafe oturme sureti ortalama trafik elaqe xerci olculen gecikme ve diger faktorlarin funksiyasi olaraq hesablana bilir Agirliq funksiyasini deyisdirererek alqoritm daha sonra bir cox kriteriyadan herhansi birine gore olculen en qisa yolu ve ya bir kriteriya kombinasiyasini hesablayir Bir qrafin iki duyunu arasinda en qisa yolu hesablamaq ucun bir cox alqoritm vardir Bunlardan Dijkstra 1959 a aiddir ve bir menbe ile sebekedeki butun hedefler arasindaki en qisa yollari tapir Her duyun en yaxsi bilinen yol boyunca menbe duyunden uzaqligi ile etiketlenmisdir Mesafeler oturme sureti ve gecikme kimi real miqdarlarla baglidirsa neqativ olmamalidir Baslangicda hec bir yol bilinmir bu sebeble butun duyunler sonsuz olaraq etiketlenir Bir etiket kecici ve ya qalici ola bilir Baslangicda butun etiketler kecici deyildir Bir etiketin kesfedildikde qalici hala getirilir ve bundan sonra hec bir zaman deyisdirilmir Etiketleme alqoritmini nece islediyini gostermek ucun Sekil 2 deki istiqametlendirilmemis qrafa baxin A dan D e en qisa yolu tapmaq isteyirik Evvelce duyun A ni isareleyirik Sonra A ya bitisik duyunlerin her birini yoxlayiriq her birinin A ya olan uzaqligi ile yeniden etiketliyirik A ya bitisik duyunlerin her birini yoxladiqdan sonra butun qrafda kecici olaraq etiketli butun duyunleri yoxladiq ve Sekil 2 b de gosterildiyi kimi en kicik etiketli qalici olani yaradiriq Bu yeni is duyunu olur Indi B den baslayib butun qonsu duyunleri yoxlayiriq B uzerindeki etiketin butunu ve B den dusunulecek duyune olan uzaqligi bu duyun uzerindeki etiketden daha kicikse duyunun yenniden etiketlenmesi ucun daha qisa bir yolumuz var Is duyunune bitisik olan butun duyunler yoxandiqdan ve mumkun oldugunca kecici etiketler deyisdirildikden sonra butun qraf en kicik deyeri olan kecici olaraq etiketlenmis duyun ucun axtarilir Bu duyun qalici edilir ve sonraki tur ucun is duyunu olur Sekil 2 de alqoritmin ilk alti addimi gosterilir Alqoritmin niye islediyini gormek ucun sekil 2 c e baxin Bu noqtede sadece E ni qalici etdik AXYZE bezi X ve Y ucun ABE den daha qisa bir yol oldugunu dusunek Iki ehtimal var ya Z duyunu evvelceden qalici hala getirilmis ya da hele yaradilmamisdir Varsa E yoxlandi bu sebeple AXYZE yolu diqqetimizden qacmadi ve bu sebeple qisa yol ola bilmez Indi Z nin kecici olaraq etikletlendiyi veziyyetini dusunun Z deki etiket E deki deyerden boyuk ve ya beraberse AXYZE ABE den daha qisa bir yol olmaz Etiket E ninkinden daha kicikse E nin deyil Z nin evvel qalici olacagi ve E nin Z den yoxlanilmasina icaze verir Bu alqoritm sekil 3 de gosterilib Dalga seklinde yayilma Redakte Bir marsurtlama alqoritmi tetbiq edildikde her marsurtlayici sebekenin tam resmi deyil lokal biliye esaslanan qerarlar vermelidir Besit bir lokal usul her gelen paketin geldiyi xet xaricindeki her geden xett uzerinde gonderildiyi dalgadir Tebii ki dalga emeliyyatini dayandirmaq ucun bezi tedbirler alinmayan vaxt erzinde dalga eslinde paketlerin sayini sonsuz sayda generasiya edir Bele bir tedbirin alinmasi her bir sicramada azaldilan her paketin basliginda olan ve saygac sifira yaxinlasdiqda atilan bir sicrama saygacina sahib olmaqdir Ideal olaraq sicrama saygaci menbeden hedefe geden yolun ne qeder uzun oldugunu bilmirse saygaci en pis veziyyetde sebekenin tam diametrine baslada biler Sicrama sayi ile dalgalanma sicrama sayi artdiqca ve marsurtlayicilar daha evvel gordukleri paketleri coxaltdiqca exponensial sayda tekrarlanan paketler yarada bilir Dalgalanmadan cixmaq ucun daha yaxsi usul marsurtlayicilarin hansi paketlerin dalgalanacagini teqib etmelerini temin etmek ve onlari ikinci defe gondermekden qacinmaqdir Bu meqsede catmaq ucun bir yol menbe marsurtlayicinin hostlarindan aldigi her pakete bir sira nomresi qoymagini temin etmekdir Her bir marsurtlayici menbe marsurtlayici basina bir liste ehtiyac duyur bu menbeden hansi siralamadaki nomrelerin gorulduyunu deyir Listde gelen bir paket varsa dalgalanmir Sekil 3 define MAX NODES 1024 duyunlerin maksimum sayi define INFINITY 1000000000 her maksimum yoldan daha boyuk bir eded int n dist MAX NODES MAX NODES dist i j i den je olan uzaqliq void shortest path int s int t int path struct state uzerinde islenilen yol int predecessor evvelki duyun int length menbeden bu duyune olan uzunluq enum permanent tentative label etiket veziyyeti state MAX NODES int i k min struct state p for p amp state 0 p lt amp state n p veziyyeti baslat p gt predecessor 1 p gt length INFINITY p gt label tentative state t length 0 state t label permanent k t k ilk isleme duyunudur do k dan yaxsi yol varmi for i 0 i lt n i bu qrafin n duyunu var if dist k i 0 amp amp state i label tentative if state k length dist k i lt state i length state i predecessor k state i length state k length dist k i En kicik etiketli kecici olaraq etiketlenmis duyunu tapin k 0 min INFINITY for i 0 i lt n i if state i label tentative amp amp state i length lt min min state i length k i state k label permanent while k s Yolu cixis massivine kopyalayin i 0 k s do path i k k state k predecessor while k gt 0 Listin limitleri xaricinde boyumesini qabaqlamaq ucun her liste bir saygac yeni k ile genisledilmelidir yeni k ile kecen butun sira ededler gorulur Dalgalanma bir cox paketi gondermek ucun praktik deyildir ancaq bezi onemli istifadeleri vardir Birincisi bir paketin sebekedeki her duyune gonderilmesini temin edir Pakete ehtiyyac duyan tek bir hedef varsa bu bosa ola biler ancaq melumat yaymaq ucun effektivdir Simsiz kabellerde bir stansiya terefinden alina biler Ikinci olaraq dalgalanma boyuk olcude saglamdir Dalgalanma da teskiletme yolunda cox az sey teleb edir Bu dalgalanma daha effektiv ancaq tertibat yolunda daha cox ehtiyac duyulan diger marsurtlama alqoritmleri ucun bunovre olaraq istifade oluna biler Dalgalanma diger marsurtlama alqoritmlerinin qasilasdirila bileceyi bir metrik olaraq da istifade oluna biler Her ehtimal paralel olaraq secildiyinden dalgalanma her zaman en qisa yolu secer Neticede basqa hecbir alqoritm daha qisa bir gecikme yaratmaz Mesafe Vektor Marsurtlama Redakte Komputer sebekeleri dalgalanmaya gore daha qarisiq olan dinamik marsurtlama alqoritmlerini istifade edir ancaq kecerli topologiya ucun en qisa yollari tapmalari sebebiyle daha effektiv olurlar Iki dinamik alqoritm ozellikle de mesafe vektoru marsurtlamasi ve kanal veziyyeti marsurtlama en populyardir Bir mesafe vektoru marsurtlama alqoritmi her bir marsurtlayicinin her bir varis noqtesine en yaxsi bilinen mesafeyi veren bir cedveli vektoru saxlayan ve ora getmek ucun hansi elaqeni istifade etmesini temin edir Bu cedveller qonsularla informasiya alis verisinde olaraq yenilenir Sonunda her marsurtlayici her hedefe catmaq ucun en yaxsi elaqeni bilir Mesafe vektoru marsurtlama alqoritmi Bellman 1957 ve Ford ve Fulkerson 1962 inkisaf etdiren tedqiqatcilardan sonra esasen Belman Ford marsurtlama alqoritmi kimi yayilib Orjinal ARPANET marsurtlama alqoritmiydi ve Inetnete RIP adi altinda istifade edilirdi Mesafe vektor marsurtlamasinda her marsurtlayici sebekedeki her marsurtlayici ucun bir giris saxlayan ve terefinden indekslenmis bir marsurtlama cedveli saxlayir Bu giris iki bolumden ibaretdir o hedef ucun istifade olunacaq secim edilen geden xetti ve bu hedefe olan mesafeni texmin eden En qisa yollari hesablamaq ucun muzakire etdiyimiz kimi sicrama sayi olaraq ve ya basqa bir metrik istifade ederek olcule biler Marsurtlayicinin qonsularinin her birine mesafe e sahib oldugu dusunulur Metrik sicrarsa mesafe sadece bir sicrama mesafesindedir Metrik yayilma gecikmesidirse marsurtlayici birbasa alicini zaman stamplariyla gosterdiyi ve ola bildiyince suretli geri gonderdiyi ozel ECHO paketleriynen olcule bilir Misal olaraq gecikmenin istifade olundugu ve marsurtlayiciinin qonsularinin her birine olan gecikmeni bildiyini dusunek Her T msande bir defeher marcurtlayici her qonsusuna texmini gecikmelerin bir listini bir bir hedefe gonderir Hemcinin her qonsudan benzer bir list alir Bu cedvellerden birinin qonsusu X den geldiyini dusunek X in marsurtlayicini ne qeder muddet kecmesi lazim oldugunu texmin etmesi Marsurtlayici X in gecikmesinin m msan oldugunu bilirse X vasitesile marsurtlayiciya Xi m msan cinsinden cata bileceyini biler Her qonsu ucun bu hesablamani reallasdiraraq bir marsurtlayici hansi texminin en yaxsi gorunduyunu tapa biler ve bu texmini ve elaqeli marsurtlamani yeni marsurtlandirma cedvelinde istifade oluna biler Hesablamada kohne marsurtlama cedvelinin istifade olunmadigini unutmayin Bu yenileme prosesi Sekil 4 de gosterilir Bolum a bir sebeke gosterir b bolumunun ilk dord sutunu marsurtlayicinin qonsularindan gelen gecikme vektorlarini gosterir A B e 12 ms gecikme C e 25ms gecikme D e 40 ms gecikme verilir J qonsularina sirayla 8 10 12 ve 6 msan olaraq A I H ve K gecikmelerini olcdu ve ya texmin etdi Sekil 4 a Sebeke b A I H K dan girisler ve J ucu yeni marsurtlama cedveli J nin marsurtlayici G e olan yeni marsurtunu nece hesabladigini dusunun 8 ms de A a cata bileceyini bilir ve ayrica A 18 ms de G e cata bileceyini iddia edr bu sebeble J 26 msan lik gecikmeye guvene bileceyini bilir Benzer sekilde G I H veK uzerinden 41 31 10 18 6 12 ve 37 31 6 msan gecikmesini hesaplayir sirayla Bu deyerlerin en yaxsisi 18 dir bu sebeble marsurtlama cedvelinde G gecikmesinin 18 msan oldugu ve istifade oluna bilecek yolun H uzerinden oldugu bir giris eder Eyni hesablama diger butun hedefler ucun yeni marsurtlama ile reallasdirilir Cedvelin son sutununda gosterilen cedvel Xarici kecid RedakteComputer Networks 5th Edition paraqraf 5 2 1 5 2 2 5 2 3 5 2 4 Menbe https az wikipedia org w index php title Marsrutlama alqoritmi amp oldid 5996300, wikipedia, oxu, kitab, kitabxana, axtar, tap, hersey,

ne axtarsan burda

, en yaxsi meqale sayti, meqaleler, kitablar, oyrenmek, wiki, bilgi, tarix, seks, porno, indir, yukle, sex, azeri sex, azeri, seks yukle, sex yukle, izle, seks izle, porno izle, mobil seks, telefon ucun, chat, azeri chat, tanisliq, tanishliq, azeri tanishliq, sayt, medeni, medeni saytlar, chatlar, mekan, tanisliq mekani, mekanlari, yüklə, pulsuz, pulsuz yüklə, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, şəkil, muisiqi, mahnı, kino, film, kitab, oyun, oyunlar.