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

Link-state routing protocol е еден од дватe класи на насочувачки протоколи кои се користат во пакет преклопните мрежи за компјутерси комуникации, другиот протокoл е distance-vector routing protocol.Пример за Link-state routing protocol се OSPF и IS-IS. Link-state routing protocol се извршува на секоја промена на јазлите на мрежата. Основниот концепт на Link-state routing protocol е тоа што секој јазол конструира карта на поврзување на мрежата, во форма на графикон, покажувајќи кои јазли се поврзани со кои други јазли. Секој јазол потоа ја пресметува следната најдобра логичка патека до секое возможно одредиште во мрежата. колекцијата на најдобрите патеки потоа ќе формира насочувачка табела на јазол. Ова е во спротивност на distance-vector routing protocols, кој работи со тоа што секој јазол ја дели својата насочувачка табела со своите соседи. Во link-state protocol-от единствена информација која поминува помеѓу јазлите е connectivity related (поврзување). Link state алгоритмите понекогаш се одликуваат со ‘Each router tells the world about its neighbors’ или “Секој насочувач кажува на светот за својте соседи ”.

Историја

Првата adaptive routing мрежа која користена link-state protocol е дизајнирана во текот на 1976-1977 од страна на тимот од Plessey Radar предводен од Bernard J Harris. Проектот бил за "Wavell"-систем на компјутерска команда и контрола на британската армија. Првиот link-state protocol беше објавен во 1979 година од страна на John M. McQuillan, како механизам со кој ќе се пресметуваат правци побрзо кога условите на мрежата се менуваат и тоа да доведе до постабилно насочување. Подоцна работата на BBN технологијата покажа како да се користи link-state техниката во хиеархискиот систем. Оваа техника е подоцна адаптирана за употреба во современите link-state routing протоколи IS-IS и OSPF. Cisco литературата се однесува на EIGRP како хибриден протокол и покрај фактот што дистрибуира насочувачки табели, наместо топологијата. Сепак тоа не ги синхронизира насочувачките табели во страт како што OSPF го прави тоа, и праќа специфични ажурирања само кога дојде до промена на топологијата. Од неодамна оваа хиерархиска техника беше применета на безжични. Каде врската може да има различен квалитет, а квалитетот на врската може да се користи за избирање на подобри врски. Ова се користи во некои насочувачки протоколи кои користат радиофреквенции за пренос.

Distribution maps

Овој опис ја покрива само наједноставната конфигурација т.е она што е без област, така што сите јазли немаат мапа на целата мрежа. Хиеархискиот случај е малку покомплексен, видете различни протокол спецификации. Како што споменавме првата голема сцена на link-state алгоритмот е да им даде карта на мрежата на секој јазол.Ова е направено со неколку едноставни чекори за подружница.

Утврдување на соседите на секој јазол

Прво секој јазол мора да го утврди она со што со другите порти е поврзан, со целосни работни врски, тоа се прави со користење на едноставен reachability протокол со кој се извршуваат одделно секој од нејзините дирекно поврзани соседи.

Distributing the information for the map

Следно секој јазол периодично и во случај на поврзување ја менува направената кратка порака, link-state реклама, од која Идентификува јазол кој го создал Ги идентификува сите други јазли со кој тој е поврзан Вклучува реден број, кој се зголемува секој пат кога изворот јазол создава нова верзија на пораката. Со оваа порака тогаш е преплавена мрежата. Како неопходен претходник, секој јазол во мрежата, се сеќава за секојдруг јазол во мрежата, редниот број на последната link-state порака која што ја добил од тој јазол. Со тоа методот што се користи е едноставен. Почнувајќи од јазолот на изворно произведената порака, ја праќа копијата на сите свои соседи. Кога link-state рекламата е примена на еден јазол, тој изгледа како реден број кој го чува изворот кој води link-state рекламата. Ако оваа порака е понова(има поголем реден број), е зачувана и една копија се испраќа пак на секој од соседите на јазолот.Со оваа постапка се добива копија од најновата верзија на link-state рекламата на секој јазол за секој јазол во мрежата. Мрежнотот извршување на link state алгоритмите може да бидат поделени во хиеархија која го граничи опсегот на пат промените. Овие карактеристити за link state алгоритмите значат дека тие се подобри за поголеми мрежи.

Белешки за овој дел

Link-state пораките даваат информации за соседите, секогаш кога има промена во поврзаноста помеѓу јазол и неговиот сосед, на пример, кога врската не успее. Секоја таква промена ќе биде откриена од страна на reachability протоколот со кој секој јазол работи со своите соседи.

Пресметување на насочувачка табела

Како што беше првично спомнато, втората главна фаза на link-state алгоритмот е да се произведуваат насочувачките табели, од увидот во мапи. Ова е повторно направено со неколку чекори.

Пресметки на најкратките патеки

Генерално се користат некои варијанти на алгоритмот на Dijkstra. Ова се заснова околу еден линк преку патот кој го вклучува расположливиот опсег помеѓу другите работи. Во основа еден јазол одржува две податочни структури: дрво, што ги содржи јазлите кои се направени и список на кандидати. Алгоритмот започнува со двете структури кои се празни, потоа прво се додава првиот јазол. •Додава во секунда (кандидат) список на сите јазли кои се поврзани со јазол кој е додаден на дрво (со исклучок на сите јазли кои се веќе во или на дрво или на кандидатска листа). •Јалите на кандидатската листа се преместуваат на дрво. Повторете сè додека постојат јазли лево во списокот на кандидати (Кога нема повеќе сите јазли во мрежата ќе се додаваат во дрвото). Оваа процедура се завршува со дрво што ги содржи сите јазли во мрежата, со јазол на кој алгоритмот се извршува како корен на дрвото. Нај краткиот пат од јазолот до другите јазли е означен со списокот на јазли.

Пополнување на насочувачка табела

Со најкратката патека, пополнувањето на насочувачката табела е тривијална. За која било дадено јазолно одредиште, најдобриот пат за тоа одредиште е јазол кој е еден чекор од коренот јазол. За да се создаде насочувачка табела, потребно е само да одиме низ дрвото, сеќавајќи се на идентитетот на јазолот на секоја гранка, и пополнување на насочувачката табела за секоја јазол.

Оптимизации на алгоритмот

Алгоритмот што го опишавме погоре е направен многу едноставен. Во пракса постојат голем број на оптимизации кои се користат. Како и да е, кога има промени во поврзаноста на мапата, неопходно е да се ре-пресмета најкусиот пат до дрвото, а потоа се ре-создаваат на насочувачката табела.

Неуспешни режими

Ако сите јазли не работат на иста мапа, насочувањето може да формира јамки. Причината е доста проста, бидејќи секоја јазол ја пресметува неговата најкратка патека до дрвото и неговата насочувачка табела без интеракција на било кој начин со другите јазли,а потоа ако два јазли започнат со различни мапи, лесно е да има сценарија во кои насочувачките јамки се создадени.

Оптимизиран Link State Routing Protocol за Mobile ad-hoc мрежи

Link -state routing protocol е оптимизиран за Mobile ad-hoc мрежите, кои исто така може да се користа за безжични ad-hoc мрежи. OLSR е проактивен и се користи во Hello and Topology Control (TC) пораките за откривање и дистрибуирање на link state информациите во mobile ad-hoc мрежата. Користејќи Hello порака за секој јазол се откриваат информации за 2-hop соседи и се избира множество од MPRs. MPRs го прави OLSR единствен од другите link state routing протокол.Поединечните јазли користат информации за топологијата за да се пресмета следната хоп патека во однос на сите јазли во мрежата.

Наводи

• John M. McQuillan, Isaac Richer and Eric C. Rosen, ARPANet Routing Algorithm Improvements, BBN Report No. 3803, Cambridge, April 1978
• John M. McQuillan, Isaac Richer and Eric C. Rosen, The New Routing Algorithm for the ARPANet, IEEE Trans. on Comm., 28(5), pp. 711–719, 1980
• Josh Seeger and Atul Khanna, Reducing Routing Overhead in a Growing DDN, MILCOMM '86, IEEE, 1986
• Radia Perlman “Rbridges: Transparent Routing” Архивирано на 26 јули 2011 г., Infocom 2004.

Further reading

• Section "Link-State Versus Distance Vector" Архивирано на 14 декември 2010 г. in the Chapter "Routing Basics" in the Cisco "Internetworking Technology Handbook"