9-ma’ruza. Marshrutizatsiya algoritmlarning klassifikatsiyasi va ularga qoʼyiladigan talablar

9-ma’ruza. Marshrutizatsiya algoritmlarning klassifikatsiyasi va ularga qoʼyiladigan talablar

РЕЖА

• Мaршрутизация жараёни
• Маршрутизация алгоритмининг функциялари
• Маршрутизация алгоритмларига қўйиладиган талаблар
• Маршрутизация алгоритмларнинг классификацияси

Мaршрутизация - бу тaрмoқнинг турли сегментлaридa жoйлaшгaн oxирги тизимлaр ўртaсидa мaълумoтлaрини узaтишгa имкoн берувчи меxaнизм хисобланади. Маршрутизация жараёни тақсимланган характерга эга, ҳамда маршрутизация жадвали асосида қурилади.
Ҳар бир тармоқ тугуни ўз жадвалига эга бўлиб, унда қабул қилувчи тармоқ тугунига борувчи барча мавжуд йўналишлар кўрсатилади. Маршрутизация жадвалини шакллантириш ва янгилаш мос маршрутизация протоколлари ва алгоритмлари ёрдамида амалга оширилади.
Маршрутлаштириш алгоритмининг мақсади тармонинг X(t) ҳолатига боғлиқ равишда жорий бошқарувни аниқлаш ҳисобланади, бу деганда пакетларни кейинги узатиш йўналишлари тўплами тушунилади. Оқимларни бошқариш протоколига мувофиқ маршрутлаштириш алгоритми қуйидаги функцияларни бажаради:
алгоритм ишлатадиган тармоқ параметрларини ўлчаш ва баҳолаш;
хизмат маълумотларини (ХМ) тарқатиш тўғрисида қарор қабул қилиш;
маршрутлар жадвалларини ҳисоблаш;
қабул қилинган маршрутлар қарорларини амалга ошириш
Маршрутлаштириш алгоритмига талаблар
Тўғрилиги. Алгоритм ишлаш қобилиятига эга бўлиши ва мантиқий қарама-қаршиликларни ўз ичига олмаслиги керак.
Ҳисоблашнинг соддалиги. Алгоритмни амалга ошириш ахборот трафигига хизмат кўрсатишга жиддий таъсир кўрсатмаслиги учун минимал процессор, канал ва буфер ресурсларини талаб қилиши керак.
Трафик ва топологиянинг ўзгаришига мослашиши. Алгоритм шароитлар ўзгарганда етказиш янги маршрутлар тўпламини аниқлаши керак.
Барқарорлиги. Алгоритм шароитларнинг сезиларсиз ўзгаришларида кескин тебранишларсиз маълум бир ечимга яқинлашиши керак. Тенглиги. Алгоритм бир хил устуворликка эга бўлган барча фойдаланувчилар учун тенг шароитларни яратиши керак.
Оптималлиги. Алгоритм берилган сифат мезонига жавоб бериши керак.
Дейкстри алгоритми 1959 йилда голландиялик олим Э. Дейкстри томонидан ихтиро қилинган графлардаги алгоритм ҳисобланади. Графнинг битта баландлигидан бошқа баландликларигача энг қисқа йўлларни топади. Алгоритм фақат манфий вазнсиз графлар учун ишлайди. Алгоритм дастурлаш ва технологияларда кенг қўлланилади, масалан, у OSPF ва IS-IS маршрутизация протоколларида ишлатилади.