Насочувачки протокол за вектор на растојание

Од Википедија — слободната енциклопедија
Прејди на прегледникот Прејди на пребарувањето

Во теоријата за компјутерска комуникација поврзана со мрежите кои вклучуваат размена на пакети, вектор растојание(англ. distance-vector) рутирачкиот протокол е еден од двете најважни класи на рутирачките протоколи, другата класа е link-state протоколот. Вектор растојание рутирачките протоколи го користат Белман-Фордовиот алгоритам, Форд-Фулкерсоновиот алгоритам или DUAL FSM (кај CISCO системите) да калкулираат патеки.

Вектор растојание рутирачиот протокол бара рутерот да ги информира неговитe соседи за периодичните промени во топологијата. Споредено со link-state протоколите кои бараат да ги информира за сите промени во јазлите на мрежата, вектор растојание рутирачките протоколи имаат помала компјутерска комплексност и нема прекумерни пораки.

Терминот вектор растојание се однесува на фактот дека овој протокол манипулира со векторите на растојание до други јазли во мрежата. Вектор растојание алгоритамот е оригиналниот ARPANET рутирачи алгоритам и исто така во интернтетот е користен под името RIP(рутирачки интернет протокол).Примери за вектор растојание рутирачки протокот користат RIPv1 and RIPv2 and IGRP.

Методи[уреди | уреди извор]

Рутерите кои користат вектор растојание протокол немаат увид за целиот пат до одредена дестинација. Наместо тоа тие користат два методи:

  1. Насока во која рутерот или излезниот интерфејс кон кој пакетот треба да биде испратен
  2. Растојdние до неговата крајна дестинација


Вектор растојание протоколите се базирани на калкулации на насоката и растојанието до било кој линк во мрежата. Насока најчесто значи скокот до наредната адреса и излезниот интерфејс. Растојание е мерката на чинење да се стигне до одреден јазел. Најевтината патека помеѓу два јазли е патеката со најмало растојание. Секој јазел има табела на минимални растојанија до секој јазел. Цената да достигне одредена дестинација е калкулирана користејќи различни метрики. RIP користи број на скокови до деснинацијата додека IGRP зема предвид и други информации како задоцнување на јазли и пропусниот опсег кој ни е на располагање.

Надградбите се изведуваат периодично во вектор растојание протоколот каде сите или дел од рутирачките табели на рутерите се испраќаат до сите нивни соседи што се конфигурирани да го користат истиот вектор растојание рутирачки протокол. RIP поддржува вектор растојание рутирање помеѓу различни крос платформни вектори на растојание, додека IGRP е комерцијален вектор растојание рутирачки протокол за CISCO системите. Откако еден рутер ја има оваа информација тој е во состојба да ја промени својата рутирачка табела за да се прикажат промените и тогаш да се информираат соседи за промените. Овој процес е опишан како “ рутирање според гласини”, бидејќи рутерите се потпираат на информациите што ги добиваат од другите рутери и не може да одредат дали таа информација е валидна и точна. Постојат голем број на функции кои може да се користат за да им се помогне со нестабилните и неточни рутирачки информации.

EGP и BGP не се чисто вектор растојание рутирачки протоколи бидејќи вектор растојание протоколот ги калкулира патеките основани само на цени на линкови, додека BGP, на пример , вредноста на локалниот пат е приоритет во однос на цената на врската.

Проблем броење до бескрај[уреди | уреди извор]

Белман-Фордовиот алгоритам не го спречува настанувањето на рутирачките јамки и страда од проблемот броење до бескрај. Јадрото на проблемот броење до бескрај е ако А му кажува на Б дека некаде постои пат, не постои начин Б да знае дали е дел од тој пат. За да го видиме јасно проблемот, претставуваме подмрежа конектирана како A–B–C–D–E–F, и нека растојанието помеѓу рутерите биде бројот на скокови . Сега претпоставуваме дека А е недостапен. Во вектор-update процесот, B забележува дека патот до А, кој е со растојание 1, е недостапен - B не прима векторски update од А. Проблемот е дека B добива update од C, но C сеуште не е свесен за фактот дека А е недостапен па му кажува на B дека А е два скока од C што е погрешно. Ова полека се шири низ мрежата додека не достигне бескрај.

Работни околини и решенија[уреди | уреди извор]

Rip користи раздвоени хоризонти (англ. split horizon)со poison reverse техника да ја редуцира шансата да се формираат јамки и корист максимален број на скокови да го изброи проблемот броење до бескрај. Со овие мерења се избегнува формирањето на рутирачки јамки во некои, но не во сите случаи. Со зголемување на времето за чекање (одбивање на надградба на патеките за неколку минути по повлекување на патека) се избегнува формирање на рами во речиси сите случаи, но предизвикува значаен пораст во конвергенцното време.

Во поново време голем број на на вектор растојание протоколи без јамки се развиени. Значајни примери се EIGRP, DSDV и Babel.Овие го избегнуваат формирањето на јамките во сите случаи, но негативно е тоа што имаат поголема комплексност.

Примери[уреди | уреди извор]

Во оваа мрежа имаме 4 рутери A, B, C, и D:

Networkabcd.svg

Ќе го обележиме моменталното време (или итерација) во алгоритамот со Т, и ќе започнеме (време 0, Т=0) преку создавање на матрици на далечина за секој рутер до неговите непосредни соседи. Како што ги формираме рутирачките табели, најкраткиот пат е означен со зелено, новиот најкраток пат го означуваме со жолта боја.. Сивите колони укажуваат на јазли кои не се соседи на моменталниот јазел и затоа не се смета за валидна насока во неговата табела. Црвената боја укажува за невалиден запис во табелата ,бидејќи тие референцираат на растојанија од јазелот кон себе, или преку себе.

T=0
од A via A via B via C via D
до A
до B 3
до C 23
до D
од B via A via B via C via D
до A 3
до B
до C 2
до D
од C via A via B via C via D
до A 23
до B 2
до C
до D 5
од D via A via B via C via D
до A
до B
до C 5
до D
Од оваа гледна точка, сите рутери имаат најкратки патеки за нивните вектори на растојание( листата од растојанија од нив до некој друг рутер преку некој сосед). Секој од нив го емитува овој нов вектор на растојание до сите негови соседи: A до B и C, B до C и A, C до A, B, и D, и D до C. Откако секој од овие соседи ќе ја добие информацијата, тие ги прекалкулираат најкратките патишта користејќи ги новодобиените информации.На пример:А прима ДВ од C кој што кажува дека постои пат преку C до D, со растојание (или цена ) 5. Бидејќи моменталниот најкраток пат до C е 23, тогаш А знае дека има пат до D што чини 23+5=28. Бидејќи нема пократки патеки за кои А е запознаена, во табелата поставуваме дека најкраток пат до D е преку C.Од оваа гледна точка, сите рутери (A,B,C, D) имаат нова најкратка патека.
T=1
од A via A via B via C via D
до A
до B 3 25
до C 5 23
до D 28
од B via A via B via C via D
до A 3 25
до B
до C 26 2
до D 7
од C via A via B via C via D
до A 23 5
до B 26 2
до C
до D 5
од D via A via B via C via D
до A 28
до B 7
до C 5
до D
Повторно, сите рутери во последната итерација(T=1)добиле нови најкратки патеки, така што сите ги испраќаат нивните вектор растојанија до нивните соседи. Ова поттикнува секој сосед повторно да ги пресмета најкратките растојанија. На пример: А прима ВР (вектор растојание) од B и ова и кажува на А дека има пат до B преку D со растојание (или цена )7. Бидејќи моменталниот најкраток пат до B е 3, тогаш А знае дека има пат до D што чини 7+3=10. Сега патот до D има цена 10(преку B ) и е пократок од веќе постоечкиот кој чини 28, па така станува најкраток пат до D.
T=2
од A via A via B via C via D
до A
до B 3 25
до C 5 23
до D 10 28
од B via A via B via C via D
до A 3 7
до B
до C 8 2
до D 31 7
од C via A via B via C via D
до A 23 5 33
до B 26 2 12
до C
до D 51 9 5
од D via A via B via C via D
до A 10
до B 7
до C 5
до D
Овој пат, само рутерите А и D имаат нови најктатки патеки за нивните вектор растојанија. Па тие ги испраќаат нивните нови вектор растојанија до нивните соседи. А испраќа до B и C,и D испраќа до C. Ова предизвикиува секој од соседите да добива нов ВР(вектор растојание)за да ги прекалкулира нивните најкратки патеки. Откако информацијата од ВР не дава никакви пократки патеки, тогаш тие веќе се во рутирачките табели и не се прават никакви промени во веќе постоечките табели.
T=3
од A via A via B via C via D
до A
до B 3 25
до C 5 23
до D 10 28
од B via A via B via C via D
до A 3 7
до B
до C 8 2
до D 13 7
од C via A via B via C via D
до A 23 5 15
до B 26 2 12
до C
до D 33 9 5
од D via A via B via C via D
до A 10
до B 7
до C 5
до D
Ниеден од овие рутери има нови најкратки патеки кои треба да ги испрати. Поради ова, никој од рутерите не прима нова информација дека треба да ја промени рутирачката табела. По ова, алгоритамот завршува.