Желілік маршруттау хаттамалары: Link State протоколы (OSPF, IS-IS) – желі топологиясын құрып, ең үздік маршрутты анықтайды. Компьютерлік желілерде маңызды!
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Маршрутизациялық протоколдар класы
Class of routing protocols
Желілік жағдайды анықтайтын маршрутизациялық протоколдар – компьютерлік байланыс желілерінде пакеттік коммутация үшін қолданылатын маршрутизациялық протоколдардың екі негізгі класының бірі, екіншісі – қашықтық векторлық маршрутизациялық протоколдар. Желілік жағдайды анықтайтын маршрутизациялық протоколдардың мысалдары – Open Shortest Path First (OSPF) және Intermediate System to Intermediate System (IS IS). Желілік жағдайды анықтайтын протокол желідегі әрбір коммутациялық түйінмен орындалады (яғни, пакеттерді жіберуге дайын түйіндер; Интернетте бұлар маршрутизаторлар деп аталады). Желілік маршрутизацияның негізгі түсінігі – әрбір түйін желіге қосылу картасын граф түрінде құрастырады, онда қай түйіннің қай түйінмен байланысы бар екені көрсетіледі. Содан кейін әрбір түйін желідегі кез келген мүмкін пунктке дейінгі ең жақсы логикалық жолды дербес есептейді. Ең жақсы жолдардың әрбір жиынтығы әрбір түйіннің маршрутизациялық кестесін құрайды. Бұл қашықтық векторлық маршрутизациялық протоколдардан өзгеше, олар әрбір түйіннің маршрутизациялық кестесін көршілерімен бөлісу арқылы жұмыс істейді, ал желілік жағдайды анықтайтын протоколда түйіндер арасында тек байланысқа қатысты ақпарат ғана жіберіледі. Желілік жағдайды анықтайтын алгоритмдер кейде әр маршрутизатордың "өзінің көршілері туралы әлемге хабарлауы" ретінде бейресми сипатталады.
Link state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance vector routing protocols. Examples of link state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS IS). The link state protocol is performed by every switching node in the network (i. e., nodes which are prepared to forward packets; in the Internet, these are called routers). The basic concept of link state routing is every node constructs a map of the connectivity to the network, in the form of a graph, showing which nodes are connected to which other nodes. Each node then independently calculates the next best logical path from it to every possible destination in the network. Each collection of best paths will then form each node's routing table. This contrasts with distance vector routing protocols, which work by having each node share its routing table with its neighbors, in a link state protocol the only information passed between nodes is connectivity related. Link state algorithms are sometimes characterized informally as each router, "telling the world about its neighbors."
Тарих
Компьютерлердің алғашқы адаптивті маршруттау желісі деп саналатын, оның негізінде байланыс жағдайының маршруттау жүйесі қолданылған, 1976-1977 жылдары Бернард Дж. Харрис басқаратын Plessey Radar тобы жобалап, іске асырды; жоба британ армиясы үшін "Wavell" – компьютерлік басқару және бақылау жүйесі үшін жасалған. Бірінші байланыс жағдайының маршруттау тұжырымы 1979 жылы Джон М. Маккуиллан (содан кейін Bolt, Beranek and Newman) желі жағдайлары өзгерген кезде маршруттарды жылдам есептеу механизмі ретінде жариялады, бұл тұрақты маршруттауға алып келеді. BBN Technologies компаниясының кейінгі жұмыстары желіні аймақтарға бөлу арқылы иерархиялық жүйеде (яғни, желі аймақтарға бөлінген) байланыс жағдайы техникасын қалай қолдануға болатынын көрсетті, сонда әрбір коммутациялық түйінге бүкіл желінің картасы емес, тек ол кіретін аймақтардың картасы ғана қажет. Бұл техника кейіннен заманауи IS-IS және OSPF байланыс жағдайы маршруттау протоколдарында қолдануға бейімделді. Cisco әдебиеті Enhanced Interior Gateway Routing Protocol (EIGRP) протоколын "гибридтік" протокол деп атайды, тіпті ол топологиялық карталардың орнына маршрут кестелерін таратады. Дегенмен, ол OSPF сияқты, жүйе іске қосылғанда маршрут кестелерін синхрондандырады және топология өзгерген кезде ғана нақты жаңартуларды жібереді. 2004 жылы Радия Перлман 2-ші қабаттағы кадрларды жіберу үшін маршруттау көпірлері немесе Rbridges деп аталатын құрылғыларды пайдаланып байланыс жағдайы маршруттауын қолдануды ұсынды. Интернет-инженерлік тобы осы мақсатқа жету үшін Lots of Links (TRILL) протоколының мөлдір өзара байланысын стандарттады. Соңғы кезде бұл иерархиялық техника Optimized Link State Routing Protocol (OLSR) протоколын пайдалана отырып, сымсыз торлы желілерге де қолданылды. Қосылыстың сапасы әртүрлі болатын жағдайларда, қосылыстың сапасын жақсырақ қосылыстарды таңдау үшін пайдалануға болады. Бұл радиожиілікпен хабарласуды қолданатын кейбір жедел маршруттау протоколдарында қолданылады.
What is believed to be the first adaptive routing network of computers, using link state routing as its heart, was designed and implemented during 1976 1977 by a team from Plessey Radar led by Bernard J Harris; the project was for "Wavell" a system of computer command and control for the British Army. The first link state routing concept was published in 1979 by John M. McQuillan (then at Bolt, Beranek and Newman) as a mechanism that would calculate routes more quickly when network conditions changed, and thus lead to more stable routing. Later work at BBN Technologies showed how to use the link state technique in a hierarchical system (i. e., one in which the network was divided into areas) so that each switching node does not need a map of the entire network, only the area(s) in which it is included. The technique was later adapted for use in the contemporary link state routing protocols IS IS and OSPF. Cisco literature refers to Enhanced Interior Gateway Routing Protocol (EIGRP) as a "hybrid" protocol, despite the fact it distributes routing tables instead of topology maps. However, it does synchronize routing tables at start up as OSPF does, and sends specific updates only when topology changes occur. In 2004, Radia Perlman proposed using link state routing for layer 2 frame forwarding with devices called routing bridges or Rbridges. The Internet Engineering Task Force has standardized the Transparent Interconnection of Lots of Links (TRILL) protocol to accomplish this. More recently, this hierarchical technique was applied to wireless mesh networks using the Optimized Link State Routing Protocol (OLSR). Where a connection can have varying quality, the quality of a connection can be used to select better connections. This is used in some ad hoc routing protocols that use radio frequency transmission.
Карталарды тарату
Бұл сипаттама ең қарапайым конфигурацияны ғана қамтиды, яғни аймақтар жоқ, сондықтан барлық түйіндерде бүкіл желінің картасы болады. Иерархиялық жағдай біршама күрделірек; әртүрлі протоколдардың сипаттамаларын қараңыз. Бұрын айтылғандай, байланыс күйі алгоритмінің бірінші негізгі кезеңі – әрбір түйінге желі картасын беру. Бұл бірнеше қосымша қадамдар арқылы іске асырылады.
This description covers only the simplest configuration; i. e., one with no areas, so that all nodes have a map of the entire network. The hierarchical case is somewhat more complex; see the various protocol specifications. As previously mentioned, the first main stage in the link state algorithm is to give a map of the network to every node. This is done with several subsidiary steps.
Әрбір тораптың көршілерін анықтау
Біріншіден, әрбір түйін толыққанды жұмыс істейтін байланыстар арқылы өзге қандай порттарға қосылғанын анықтауы керек; ол үшін қолжетімділік протоколын пайдаланады, ол әрбір тікелей байланысты көршісімен мерзімді және жеке-жеке іске қосылады.
First, each node needs to determine what other ports it is connected to, over fully working links; it does this using reachability protocol it runs periodically and separately with each of its directly connected neighbours.
Картаны құру
Соңында, желідегі әрбір түйінен алынған толық сілтеме күйі туралы хабарламалар жинағы болғанда, әрбір түйін желінің картасы үшін граф құрайды. Алгоритм сілтеме күйі туралы хабарламалар жинағын қарап шығады; әрбір хабарлама үшін, ол хабарлама жіберген түйінен, сол хабарламада көршілер деп көрсетілген барлық түйіндерге дейін желі картасында сілтемелер жасайды. Егер екі түйіннің арасындағы байланыс туралы мәліметтер сәйкес келмесе, онда сілтеме дұрыс деп есептелмейді; яғни, егер бір түйін екінші түйінмен байланысқаны туралы хабарласа, ал екінші түйін бірінші түйінмен байланысқаны туралы хабарламаса, онда қателік бар және бұл сілтеме картаға қосылмайды.
Finally, with the complete set of link state advertisements (one from each node in the network) in hand, each node produces the graph for the map of the network. The algorithm iterates over the collection of link state advertisements; for each one, it makes links on the map of the network, from the node which sent that message, to all the nodes which that message indicates are neighbors of the sending node. No link is considered to have been correctly reported unless the two ends agree; i. e., if one node reports that it is connected to another, but the other node does not report that it is connected to the first, there is a problem, and the link is not included on the map.
Осы кезең туралы ескертулер
Түйін мен оның көршілері арасындағы байланыста өзгеріс болған кезде, көршілер туралы ақпаратты беретін желі жағдайы туралы хабарлама қайта есептеледі және желіде таратылады; мысалы, егер сілтеме жұмыс істемей қалса. Мұндай кез келген өзгеріс әрбір түйіннің өз көршілерімен іске асыратын қолжетімділік протоколы арқылы анықталады.
The link state message giving information about the neighbors is recomputed, and then flooded throughout the network, whenever there is a change in the connectivity between the node and its neighbors; e. g., when a link fails. Any such change will be detected by the reachability protocol which each node runs with its neighbors.
Маршруттау кестесінің есептеуі
Бастапқыда айтылғандай, байланыс жағдайы алгоритмінің екінші негізгі кезеңі – карталарды қарап шығу арқылы маршрут кестелерін құру. Бұл да бірнеше қадамдар арқылы жасалады.
As initially mentioned, the second main stage in the link state algorithm is to produce routing tables, by inspecting the maps. This is again done with several steps.
Ең қысқа жолдарды есептеу
Әрбір түйін карта бойынша алгоритмді дербес іске қосып, желідегі өзінен басқа әрбір түйінге ең қысқа жолды анықтайды; көбінесе Дикстра алгоритмінің бір түрі қолданылады. Бұл әрбір жолдың байланыс құнына негізделген, оған қол жетімді өткізу қабілеті де кіреді. Түйін екі дерек құрылымын сақтайды: «аяқталған» түйіндерді қамтитын ағаш және үміткерлер тізімі. Алгоритм екі құрылымды бос күйден бастайды; содан кейін өзінің түйінін бірінші құрылымға қосады. Ашкөз алгоритмнің түрі келесі әрекеттерді қайталап орындайды:
Each node independently runs an algorithm over the map to determine the shortest path from itself to every other node in the network; generally some variant of Dijkstra's algorithm is used. This is based around a link cost across each path which includes available bandwidth among other things. A node maintains two data structures: a tree containing nodes which are "done", and a list of candidates. The algorithm starts with both structures empty; it then adds to the first one the node itself. The variant of a greedy algorithm then repetitively does the following:
Түйінге тікелей байланысты барлық көрші түйіндер ағашқа қосылады (егер олар бұрыннан ағашта немесе үміткерлер тізімінде болмаса). Қалғандары екінші (үміткерлер) тізімге қосылады. Үміткерлер тізіміндегі әрбір түйін ағаштағы барлық түйіндермен салыстырылады. Ағаштағы түйіндерге ең жақын үміткер түйін ағашқа көшіріліп, тиісті көрші түйінге қосылады. Түйін үміткерлер тізімінен ағашқа көшірілген кезде, ол үміткерлер тізімінен алынып тасталады және алгоритмнің келесі итерацияларында қарастырылмайды. Жоғарыдағы екі қадам үміткерлер тізімінде түйіндер қалғанша қайталанады. (Егер түйіндер қалмаса, желідегі барлық түйіндер ағашқа қосылған болады.) Бұл процедура желідегі барлық түйіндерді қамтитын ағашпен аяқталады, ал алгоритм іске қосылған түйін ағаштың түбірі болады. Осы түйіннен кез келген басқа түйінге дейінгі ең қысқа жол ағаштың түбірінен қажетті түйінге жету үшін өтілетін түйіндер тізімімен көрсетіледі.
All neighbour nodes which are directly connected to the node are just added to the tree (excepting any nodes which are already in either the tree or the candidate list). The rest are added to the second (candidate) list. Each node in the candidate list is compared to each of the nodes already in the tree. The candidate node which is closest to any of the nodes already in the tree is itself moved into the tree and attached to the appropriate neighbor node. When a node is moved from the candidate list into the tree, it is removed from the candidate list and is not considered in subsequent iterations of the algorithm. The above two steps are repeated as long as there are any nodes left in the candidate list. (When there are none, all the nodes in the network will have been added to the tree.) This procedure ends with the tree containing all the nodes in the network, with the node on which the algorithm is running as the root of the tree. The shortest path from that node to any other node is indicated by the list of nodes one traverses to get from the root of the tree, to the desired node in the tree.
Маршруттау кестесін толтыру
Ең қысқа жолдарды анықтағаннан кейін, келесі қадам – маршрут кестесін толтыру. Кез келген мақсаттық түйін үшін, сол мақсатқа дейінгі ең жақсы жол – бұл тамыр түйінінен бастап, ең қысқа жол ағашының мақсаттық түйінге қарай бағытталған тармағы бойынша жасалатын алғашқы қадам. Маршрут кестесін жасау үшін ағашты аралап өту жеткілікті, әр тармақтың басындағы түйіннің идентификаторын есте сақтап, кездесетін әр түйін үшін маршрут кестесіне жазба енгізу қажет.
With the shortest paths in hand, the next step is to fill in the routing table. For any given destination node, the best path for that destination is the node which is the first step from the root node, down the branch in the shortest path tree which leads toward the desired destination node. To create the routing table, it is only necessary to walk the tree, remembering the identity of the node at the head of each branch, and filling in the routing table entry for each node one comes across with that identity.
Алгоритмді оңтайландыру
Жоғарыда сипатталған алгоритм түсінуді жеңілдету үшін мүмкіндігінше қарапайым етіп жасалды. Іс жүзінде, көптеген оңтайландырулар қолданылады.
The algorithm described above was made as simple as possible, to aid in ease of understanding. In practice, there are a number of optimizations which are used.
Қиссалық қайта есептеу
Қосылым картасы өзгерген сайын ең қысқа жол ағашын қайта есептеу және маршрут кестесін қайта құру қажет. BBN Technologies компаниясының зерттеулері картадағы нақты өзгеріске ықпал ететін ағаштың тек сол бөлігін ғана қайта есептеуге мүмкіндік берді. Сонымен қатар, маршрут кестесі ең қысқа жол ағашы есептелген кезде-ақ толтырылады, оны жеке операция ретінде жасаудың қажеті жоқ.
Whenever a change in the connectivity map happens, it is necessary to recompute the shortest path tree, and then recreate the routing table. Work by BBN Technologies discovered how to recompute only that part of the tree which could have been affected by a given change in the map. Also, the routing table would normally be filled in as the shortest path tree is computed, instead of making it a separate operation.
Балық көзінің бағыты
Fisheye State Routing (FSR) арқылы LSA-лар олардың таралуын шектеу және басқару хабарламаларынан туындайтын артық шығындарды азайту үшін әртүрлі өмір сүру уақытымен (time to live) жіберіледі. Осы принцип Hazy Sighted Link State Routing Protocol протоколында да қолданылады.
With Fisheye State Routing (FSR) the LSA are sent with different time to live values to restrict their diffusion and limit the overhead due to control messages. The same concept is used also in the Hazy Sighted Link State Routing Protocol.
Ақаулық режімдері
Егер барлық түйіндер бірдей картадан жұмыс істемесе, маршрут циклдары пайда болуы мүмкін. Бұл ең қарапайым жағдайда, екі көрші түйіннің әрқайсысы екіншісін белгілі бір мақсатқа жетудің ең жақсы жолы деп есептейтін жағдай. Осы мақсатқа бағытталған кез келген пакет екі түйіннің арасында айналып, соның нәтижесінде цикл құрайды. Екіден астам түйінге қатысты маршрут циклдары да болуы мүмкін. Мұның себебі, әрбір түйін өзінің ең қысқа жол ағашын және маршрут кестесін басқа түйіндермен ешқандай байланыссыз есептейді. Егер екі түйін әртүрлі карталармен жұмыс бастаса, маршрут циклдарының пайда болуына әкелетін жағдайлар туындауы мүмкін. Кейбір жағдайларда, көп бұлтты ортада айырмашылық циклдары қосылуы мүмкін. Интерфейс протоколы арқылы өзгермелі кіру түйіндері бір мезгілде кіру түйінінің туындауы мүмкін проблеманы да шеше алады.
If all the nodes are not working from exactly the same map, routing loops can form. These are situations in which, in the simplest form, two neighboring nodes each think the other is the best path to a given destination. Any packet headed to that destination arriving at either node will loop between the two, hence the name. Routing loops involving more than two nodes are also possible. This can occur since each node computes its shortest path tree and its routing table without interacting in any way with any other nodes. If two nodes start with different maps, it is possible to have scenarios in which routing loops are created. In certain circumstances, differential loops may be enabled within a multi cloud environment. Variable access nodes across the interface protocol may also bypass the simultaneous access node problem.
Оптимизацияланған байланыс күйін маршруттау протоколы
Оптимизацияланған байланыс күйі маршрутизациялау протоколы (OLSR) – мобильді желілерге (сондай-ақ басқа сымсыз желілерде де қолданылуы мүмкін) арналған, өте тиімді байланыс күйі маршрутизациялау протоколы. OLSR проактивті, яғни алдын ала жұмыс істейді және байланыс күйі туралы ақпаратты желіге тарату үшін "сәлемдесу" (hello) және топологиялық басқару (TC) хабарламаларын пайдаланады. "Сәлемдесу" хабарламалары арқылы әрбір түйін екі қадамдық көршілер туралы ақпаратты анықтайды және көп нүктелі релелердің (MPR) жиынтығын сайлайды. Көп нүктелі релелер (MPR) OLSR-ді басқа байланыс күйі маршрутизациялау протоколдарынан ерекшелендіреді. Түйіндер топологиялық ақпаратты желідегі барлық түйіндерге қатысты ең қысқа маршруттарды есептеу үшін қолданады.
The Optimized Link State Routing Protocol (OLSR) is a link state routing protocol optimized for mobile ad hoc networks (which can also be used on other wireless ad hoc networks). OLSR is proactive and uses hello and topology control (TC) messages to discover and disseminate link state information into the mobile ad hoc network. Using hello messages, each node discovers two hop neighbor information and elects a set of multipoint relays (MPRs). MPRs make OLSR distinct from other link state routing protocols. Individual nodes use the topology information to compute next hop paths regarding all nodes in the network using shortest hop forwarding paths.