Link-state routing protocol

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај

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 протокол.Индивидуалните јазли користат информации за топологијата за да се пресмета следната хоп патека во однос на сите јазли во мрежата.



Референци[уреди]

Шаблон:No footnotes

  • 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”, Infocom 2004.

Further reading[уреди]