Деректер желісінде маршруттау процесі

Кіріспе

Деректер байланыс желісінде жолдарды таңдау процесі. Пакеттік коммутациялық желілерде маршрутизация.

Маршрутизация – желіде немесе бірнеше желі арасындағы трафик үшін жолды таңдау процесі. Жалпы алғанда, маршрутизация көптеген желілерде қолданылады, соның ішінде тізбектік коммутациялық желілерде, мысалы, қоғамдық телефон желісінде (PSTN), және Интернет сияқты компьютерлік желілерде. Пакеттік коммутациялық желілерде маршрутизация – бұл желілік пакеттерді олардың бастапқы нүктесінен арналған жеріне, арнайы пакеттік жіберу механизмдері арқылы аралық желілік түйіндер арқылы бағыттайтын жоғары деңгейдегі шешім қабылдау. Пакеттік жіберу – желілік пакеттердің бір желілік интерфейстен екіншісіне өтуі. Аралық түйіндер әдетте маршрутизаторлар, шлюздер, қауіпті есіктер (firewall) немесе коммутаторлар сияқты желілік аппараттық құрылғылар болып табылады. Баламативті компьютерлер де пакеттерді жібереді және маршрутизацияны жүзеге асырады, бірақ оларда бұл міндет үшін арнайы оптимизацияланған жабдық жоқ. Маршрутизация процесі әдетте маршрутизация кестелерінің негізінде бағытты анықтайды. Маршрутизация кестелері әртүрлі желілік бағыттарға қатысты маршруттарды сақтайды. Маршрутизация кестелерін әкімшілер анықтай алады, желілік трафикті бақылау арқылы үйрене алады немесе маршрутизация протоколдарының көмегімен құра алады. Маршрутизация, терминнің тар мағынасында, көбінесе IP маршрутизациясын білдіреді және көпірлеуден (bridging) ажыратылады. IP маршрутизациясы желілік мекенжайлардың құрылымдалғандығын және ұқсас мекенжайлар желідегі жақындықты білдіреді деп есептейді. Құрылымдалған мекенжайлар бір маршрутизация кестесіне кіруге бірнеше құрылғыға бағытты көрсетуге мүмкіндік береді. Ірі желілерде құрылымды адрестеу (маршрутизация, тар мағынада) құрылымсыз адрестеуден (көпірлеу) артықшылық танытады. Маршрутизация Интернетте мекенжай берудің басым түріне айналды. Көпірлеу әлі де жергілікті желілерде кеңінен қолданылады.

Топологиялық үлестірілім

Статикалық маршрутизациялауда кіші желілер қолмен конфигурацияланған маршрутизация кестелерін қолдануы мүмкін. Ірі желілерде күрделі топологиялар болады, олар жылдам өзгеріп отыруы мүмкін, бұл маршрутизация кестелерін қолмен жасауды қиын етеді. Дегенмен, көпшілік коммутацияланған телефон желісінің (PSTN) көп бөлігі алдын ала есептелген маршрутизация кестелерін пайдаланады, егер ең тікелей маршрут бұғатталса, қосалқы маршруттар қарастырылады (PSTN-дегі маршрутизацияны қараңыз). Динамикалық маршрутизациялау осы мәселені маршрутизациялық протоколдар арқылы берілетін ақпарат негізінде маршрутизация кестелерін автоматты түрде құру арқылы шешуге тырысады, бұл желіге желілік ақаулар мен кедергілерден дерлік тәуелсіз түрде өтуге мүмкіндік береді. Динамикалық маршрутизациялау Интернетте басым. Динамикалық маршрутизация протоколдары мен алгоритмдерінің мысалдары: маршруттау туралы ақпарат протоколы (RIP), ең қысқа жолды бірінші табу (OSPF) және кеңейтілген ішкі шлюз маршрутизация протоколы (EIGRP).

Қашықтық векторлары алгоритмдері

Қашықтық векторлық алгоритмдер Беллман-Форд алгоритмін қолданады. Бұл тәсіл желідегі әрбір түйін арасындағы әрбір байланысқа құн мөлшерін тағайындайды. Түйіндер А нүктесінен В нүктесіне ең төменгі жалпы құн (яғни пайдаланылған түйіндер арасындағы байланыстардың құнының қосындысы) беретін жол арқылы ақпаратты жібереді. Түйін алғаш іске қосылғанда, ол тек тікелей көршілерін және оларға жетуге кеткен тікелей құнды ғана біледі. (Бұл ақпарат – бағыттар тізімі, әрқайсысына жетудің жалпы құны және онда жету үшін деректерді жіберуге келесі секіру – маршрут кестесін немесе қашықтық кестесін құрайды.) Әрбір түйін белгілі бір уақыт аралығында көрші түйіндерге өзі білетін барлық бағыттарға жетудің жалпы құны туралы ақпаратты жібереді. Көрші түйіндер бұл ақпаратты қарап, оны өздері білетін ақпаратпен салыстырады; егер жаңа ақпарат олардың білуін жақсартса, оны өз кестелеріне енгізеді. Уақыт өте келе желідегі барлық түйіндер барлық бағыттар үшін ең жақсы келесі секіруді және жалпы құнды анықтайды. Желідегі түйін жұмысын тоқтатса, оны келесі секіру ретінде пайдаланған түйіндер бұл жазбаны жойып, жаңартылған маршруттау ақпаратын барлық көрші түйіндерге жібереді, олар өз кезегінде осы процесті қайталайды. Соңында желідегі барлық түйіндер жаңартуларды алады және бұрынғы түйіннен өтетін жолдарды ескермей, барлық бағыттарға жаңа жолдарды табады.

Байланыс-күй алгоритмдері

Байланыс жағдайы алгоритмдерін қолданғанда, желінің графикалық картасы әрбір түйін үшін негізгі дерек болып табылады. Өз картасын жасау үшін, әрбір түйін желідегі басқа түйіндерге қосылу мүмкіндігі туралы ақпаратты таратады. Содан кейін әрбір түйін бұл ақпаратты тәуелсіз түрде картаға жинақтайды. Осы картаны пайдаланып, әрбір маршрутизатор Dijkstra алгоритмі сияқты стандартты ең қысқа жол алгоритмін қолдана отырып, өзінен басқа барлық түйіндерге дейінгі ең төмен құн жолын анықтайды. Нәтижесінде, ағымдағы түйінде тамырланған ағаш графигі пайда болады, яғни ағаштан түбірден кез келген басқа түйінге дейінгі жол сол түйінге жетудің ең төмен құнды жолы болып табылады. Бұл ағаш маршрут кестесін құруға пайдаланылады, ол ағымдағы түйінден кез келген басқа түйінге жету үшін ең жақсы келесі қадамды көрсетеді.

Оптимизацияланған байланыс күйін маршруттау алгоритмі

Мобильдік желілер үшін оңтайландырылған байланыс күйінің маршруттау алгоритмі – Оңтайландырылған Байланыс Күйінің Маршруттау Протоколы (OLSR). OLSR проактивті; ол Hello және Топологиялық Бақылау (TC) хабарламаларын қолданып, мобильді желі арқылы байланыс күйі туралы ақпаратты анықтап, таратуға пайдаланады. Hello хабарламаларын пайдалану арқылы әрбір түйін 2 қадамдық көрші туралы ақпаратты анықтайды және көп нүктелі релелердің (MPR) жиынтығын сайлайды. Көп нүктелі релелер (MPR) OLSR-ді басқа байланыс күйінің маршруттау протоколдарынан ерекшелендіреді.

Жол-вектор протоколы

Қашықтық векторы және байланыс күйі маршруттаулары – екі доменішілік маршруттау протоколы. Олар автономды жүйе ішінде қолданылады, бірақ автономды жүйелер арасында емес. Бұл маршруттау протоколдарының екеуі де үлкен желілерде тиімсіз болады және домен аралық маршруттауда қолданылмайды. Қашықтық векторы маршруттау доменде бірнеше секіруден асып кетсе, тұрақсыздыққа ұшырауы мүмкін. Байланыс күйі маршруттау маршруттау кестелерін есептеу үшін көп ресурстарды қажет етеді. Сонымен қатар, су тасқынына байланысты ауыр трафик пайда болады. Жол векторы маршруттау домен аралық маршруттау үшін қолданылады. Ол қашықтық векторы маршруттауға ұқсас. Жол векторы маршруттау әрбір автономды жүйедегі бір түйіннің (мүмкін көп болуы мүмкін) бүкіл автономды жүйеден әрекет ететінін болжайды. Бұл түйін «сөйлеуші түйін» деп аталады. Сөйлеуші түйін маршруттау кестесін жасайды және оны көршілес автономды жүйелердегі басқа сөйлеуші түйіндерге хабарлайды. Бұл идея қашықтық векторы маршруттауға ұқсас, бірақ әр автономды жүйедегі сөйлеуші түйіндер ғана бір-бірімен байланыса алады. Сөйлеуші түйін өз автономды жүйесіндегі немесе басқа автономды жүйелердегі түйіндердің метрикасын емес, жолын хабарлайды. Жол векторы маршруттау алгоритмі қашықтық векторы алгоритміне ұқсас, себебі әрбір шекаралық маршрутизатор өзінің көршісіне жете алатын бағыттарды хабарлайды. Дегенмен, бағыт пен бағытқа дейінгі қашықтық бойынша хабарлаудың орнына, желілер бағыт мекенжайлары және осы бағыттарға жету жолының сипаттамалары түрінде хабарланады. Осы уақытқа дейін басып өткен домендер (немесе конфедерациялар) бойынша көрсетілген жол, қолжетімділік туралы ақпарат өткен маршруттау домендерінің тізбесін тіркейтетін арнайы жол атрибутында сақталады. Маршрут – бұл бағыт пен осы бағыттың атрибуттарының жұптасуы, сондықтан бұл маршрут векторлық маршруттау деп аталады; маршрутизаторлар бағыттар жиынтығына бағыт беретін векторды алады.

Бірнеше агенттер

Кейбір желілерде маршруттандыру жолдарды таңдауға жауапты бірде-бір тұлға болмағандықтан күрделіленеді; оның орнына бірнеше тұлғалар жолдарды немесе тіпті бір жолдың бөліктерін таңдауға қатысады. Егер осы тұлғалар өз мақсаттарын оңтайландыру үшін басқа қатысушылардың мақсаттарымен қайшылыққа түсетін жолдарды таңдаса, қиындықтар немесе тиімсіздік туындауы мүмкін. Классикалық мысал – жол жүйесіндегі қозғалыс, онда әрбір жүргізуші өзінің саяхат уақытын барынша қысқартатын жолды таңдайды. Мұндай маршруттандыруда тепе-теңдікке қол жеткен жолдар барлық жүргізушілер үшін оңтайлыдан ұзақ болуы мүмкін. Атап айтқанда, Бресс парадоксы жаңа жолдың барлық жүргізушілердің саяхат уақытын ұзартатынын көрсетеді. Бір агенттік модельде, мысалы, терминалда автоматтандырылған бағытталатын көлік құралдарын (АЖК) маршруттау үшін, инфрақұрылымның бір бөлігін бір уақытта пайдалануды болдырмау үшін әр көлік үшін резервтер жасалады. Бұл тәсіл контекстілі маршруттау деп те аталады. Интернет автономды жүйелерге (АЖ) бөлінген, мысалы, интернет-қызмет көрсетушілер (ISP), олардың әрқайсысы өз желісіне қатысатын маршруттарды басқарады. Маршруттау бірнеше деңгейде жүзеге асады. Біріншіден, АЖ деңгейіндегі жолдар BGP протоколы арқылы таңдалады, ол пакеттер ағып өтетін АЖ тізбегін құрайды. Әрбір АЖ көрші АЖ ұсынатын бірнеше жолға ие болуы мүмкін, олардың арасынан таңдау жасалады. Бұл маршруттау шешімдері көбінесе осы көрші АЖ-термен бизнес қатынастармен байланысты, олар жол сапасына немесе кідіріске байланысты болмауы мүмкін. Екіншіден, АЖ деңгейіндегі жол таңдалғаннан кейін, көбінесе бірнеше маршрутизатор деңгейіндегі жолдар бар. Бұл екі ISP бірнеше қосылым арқылы байланысты болуы мүмкін. Маршрутизатор деңгейіндегі бір жолды таңдағанда, әрбір ISP трафикті өзінің желісі арқылы қашықтықты барынша азайтатын жолмен жіберуді қалайды – тіпті бұл жол мақсатқа дейінгі жалпы қашықтықты ұзартса да. Бұл практика "ыстық картоп маршруттау" деп аталады. Мысалы, екі ISP, А және В қарастырайық. Әрқайсысының Нью-Йоркте 5 мс кешігуі бар жылдам байланысы бар, сондай-ақ Лондонда 5 мс кешігуі бар байланысы бар. Екі ISP-нің де Атлантика арқылы екі желісін байланыстыратын байланысы бар делік. А желісінің 100 мс, ал В желісінің 120 мс кешігуі бар. А-ның Лондон желісіндегі бастапқы нүктеден В-нің Нью-Йорк желісіндегі мақсатқа хабарды маршруттағанда, А хабарды Лондондағы В-ге бірден жіберуді таңдауы мүмкін. Бұл А-ға оны қымбат Атлантикалық байланыс арқылы жіберудің қажеттілігін жояды, бірақ хабарлама 125 мс кешігуді сезінеді, ал басқа маршрут 20 мс-қа жылдам болар еді. Сонымен қатар, ұялы желілерде де ұқсас маршруттау қиындықтарын байқауға болады, онда әртүрлі пакеттер әртүрлі соңғы нүктелерге бағытталған, ал әр байланыс әртүрлі спектральді тиімділікке ие. Бұл жағдайда оңтайлы жолды таңдау кідіріс пен пакет қателіктерінің деңгейін ескеруді қамтиды. Бұл мәселені шешу үшін әрбір базалық станция үшін тәуелсіз бірнеше тұлғалар жолды таңдауда маңызды рөл атқарады, сонымен бірге жалпы желілік өнімділікті оңтайландыруға тырысады. 2003 жылғы Интернет маршруттарын зерттеуде көршілес ISP-лардың жұптары арасындағы жолдардың 30% -дан астамы ыстық картоп маршруттаудың салдарынан кешігудің ұлғаюын көрсетті, ал 5% жолдар кем дегенде 12 мс-қа кешіктірілді. АЖ деңгейіндегі жолды таңдаудың салдарынан туындаған кешігудің ұлғаюы, айтарлықтай болғанымен, негізінен BGP-нің кешігуді тікелей оңтайландыру механизміне ие болмауына байланысты болды, өзімшіл маршруттау саясатына емес. Сондай-ақ, тиісті механизм болған жағдайда ISP-лар ыстық картоп маршрутын пайдаланудың орнына кешігуді азайту үшін ынтымақтасуға дайын болады деп ұсынылды. Мұндай механизмді кейіннен сол авторлар жариялады, алдымен екі ISP үшін, содан кейін жаһандық жағдай үшін.

In some networks, routing is complicated by the fact that no single entity is responsible for selecting paths; instead, multiple entities are involved in selecting paths or even parts of a single path. Complications or inefficiency can result if these entities choose paths to optimize their own objectives, which may conflict with the objectives of other participants. A classic example involves traffic in a road system, in which each driver picks a path that minimizes their travel time. With such routing, the equilibrium routes can be longer than optimal for all drivers. In particular, Braess's paradox shows that adding a new road can lengthen travel times for all drivers. In a single agent model used, for example, for routing automated guided vehicles (AGVs) on a terminal, reservations are made for each vehicle to prevent simultaneous use of the same part of an infrastructure. This approach is also referred to as context aware routing. The Internet is partitioned into autonomous systems (ASs) such as internet service providers (ISPs), each of which controls routes involving its network. Routing occurs at multiple levels. First, AS level paths are selected via the BGP protocol that produces a sequence of ASs through which packets flow. Each AS may have multiple paths, offered by neighboring ASs, from which to choose. These routing decisions often correlate with business relationships with these neighboring ASs, which may be unrelated to path quality or latency. Second, once an AS level path has been selected, there are often multiple corresponding router level paths to choose from. This is due, in part, because two ISPs may be connected through multiple connections. In choosing the single router level path, it is common practice for each ISP to employ hot potato routing: sending traffic along the path that minimizes the distance through the ISP's own network—even if that path lengthens the total distance to the destination. For example, consider two ISPs, A and B. Each has a presence in New York, connected by a fast link with latency 5—and each has a presence in London connected by a 5 ms link. Suppose both ISPs have trans Atlantic links that connect their two networks, but A's link has latency 100 ms and B's has latency 120 ms. When routing a message from a source in A's London network to a destination in B's New York network, A may choose to immediately send the message to B in London. This saves A the work of sending it along an expensive trans Atlantic link, but causes the message to experience latency 125 ms when the other route would have been 20 ms faster. Additionally, a similar routing challenge can be observed in cellular networks, where different packets are destined for various endpoints, and each link exhibits varying spectral efficiency. In this context, the selection of the optimal path involves considering latency and packet error rate. To address this, multiple independent entities, one for each base station, play a crucial role in path selection while striving to optimize overall network performance. A 2003 measurement study of Internet routes found that, between pairs of neighboring ISPs, more than 30% of paths have inflated latency due to hot potato routing, with 5% of paths being delayed by at least 12 ms. Inflation due to AS level path selection, while substantial, was attributed primarily to BGP's lack of a mechanism to directly optimize for latency, rather than to selfish routing policies. It was also suggested that, were an appropriate mechanism in place, ISPs would be willing to cooperate to reduce latency rather than use hot potato routing. Such a mechanism was later published by the same authors, first for the case of two ISPs and then for the global case.

Жолдар талдауы

Интернет пен IP желілері бизнестің өте маңызды құралдарына айналғандықтан, желілердің маршруттау жағдайын бақылау техникалары мен әдістеріне деген қызығушылық күшейді. Бұрыс маршруттау немесе маршруттау мәселелері жұмыстың нашарлауына, тұрақсыздыққа немесе желінің тоқтауына себеп болады. Желіде маршруттауды бақылау маршрутталдыру талдау құралдары мен техникаларын пайдалану арқылы жүзеге асырылады.

Орталықтандырылған маршруттау

Логикалық орталықтандырылған басқаруға ие желілерде, мысалы, бағдарламалық түрде анықталатын желілерде, жаһандық және желілік деңгейдегі өнімділікті оңтайландыруға бағытталған маршруттау техникаларын қолдануға болады. Бұл тәсілді жеке оптикалық байланыстар арқылы әртүрлі географиялық орналасқан көптеген деректер орталықтарын басқаратын ірі интернет компаниялары қолданды, мысалы, Microsoft Global WAN, Facebook Express Backbone және Google B4. Оптимизацияға жататын жаһандық өнімділік өлшемдеріне желінің пайдалануын максималдау, трафик ағынының аяқталу уақытын қысқарту, белгілі бір мерзімге дейін жеткізілген трафик көлемін арттыру және ағындардың аяқталу уақытын төмендету кіреді. Жеке WAN желілеріндегі соңғы зерттеулер маршруттауды графтық оңтайландыру мәселесі ретінде модельдеуді қарастырады, барлық кезектерді соңғы нүктелерге жылжыту арқылы. Авторлар сондай-ақ, мәселені тиімді шешу үшін, өнімділікке минималды әсер ететін эвристикалық әдіс ұсынады.