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

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

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

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

Методи

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

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

Вектор растојание протоколите се засновани на пресметки на насоката и растојанието до било кој линк во мрежата. Насока најчесто значи скокот до наредната адреса и излезниот интерфејс. Растојание е мерката на чинење да се стигне до одреден јазел. Најевтината патека помеѓу два јазли е патеката со најмало растојание. Секој јазел има табела на минимални растојанија до секој јазел. Цената да достигне извесно одредиште е калкулирана користејќи различни метрики. 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:

Ќе го обележиме моменталното време (или итерација) во алгоритамот со Т, и ќе започнеме (време 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
Ниеден од овие насочувачи има нови најкратки патеки кои треба да ги испрати. Поради ова, никој од насочувачите не прима нова информација дека треба да ја промени насочувачката табела. По ова, алгоритамот завршува.