Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti mustaqil ish

Eng qisqa yo‘l algoritmi
Kompyuter tarmoqlarida eng qisqa yo'l algoritmlari marshrutlash narxini minimallashtirish uchun tarmoq tugunlari orasidagi optimal yo'llarni topishga qaratilgan. Ular grafik nazariyasida taklif qilingan eng qisqa yo'l algoritmlarining bevosita qo'llanilishidir. Eng qisqa yo'l marshrutlashda topologiya aloqa tarmog'i yo'naltirilgan vaznli grafik yordamida aniqlanadi. Grafikdagi tugunlar kommutatsiya komponentlarini belgilaydi va grafikdagi yo'naltirilgan yoylar kommutatsiya komponentlari orasidagi aloqani belgilaydi. Har bir yoy ma'lum bir yo'nalishda ikkita tugun o'rtasida paketni almashish narxini belgilaydigan vaznga ega. Informatika fanida nuqtalar to'plami orasidagi eng qisqa yo'lni topishni talab qiladigan bir qator muammolar mavjud. Ilovalar juda ko'p va oddiy - sun'iy yo'ldosh navigatsiyasidan Internet paketlarini marshrutlashgacha; Hatto elektron platadagi pinlarni ulash uchun zarur bo'lgan eng qisqa sim uzunligini topish ham eng qisqa yo'l muammosiga misoldir. Ushbu turdagi muammolar juda tez-tez yuzaga kelganligi sababli, yechim topish uchun ishlatilishi mumkin bo'lgan ba'zi standart algoritmlar mavjud. Ulardan biri Dijkstra algoritmi sifatida tanilgan. U 1956 yilda golland fizigi Edsger Deykstra tomonidan Rotterdamdan Groningengacha bo'lgan eng qisqa yo'lni qanday hisoblash mumkinligi haqida o'ylaganida ishlab chiqilgan.

Masofaviy-vektorli marshrutlash
TCP/IP stekining yo‘nalish axborotlari bilan almashishning hamma protokollari adaptiv protokollar sinfiga kiradi. Ular o‘z navbatida ikki guruhga bo‘lingan, ularning har biri quyidagi algoritmlar turi bilan bog‘langan:
- Masofa-vektor algoritmi (Distance Vector Algorithms, DVA);
- Aloqa xolati algoritmi (Link State Algorithms, LSA).
Masofa-vektor turidagi algoritmlarda marshrutizator vaqti-vaqti bilan va keng ogox qilingan holda tarmoq bo‘yicha o‘zidan to unga ma’lum bo‘lgan tarmoqlarga masofa vektorini yuboradi.

Masofaviy vektor marshrutlash protokollari kichik tarmoqlarda ishlash uchun mo'ljallangan (odatda 100 dan kam marshrutizator). Ularni sozlash odatda osonroq va ulanish holati protokollariga qaraganda kamroq texnik xizmat ko'rsatishni talab qiladi.
Masofa deganda odatda paket muvofiq tarmoqqa tushishdan oldin nechta oraliq marshrutizatorlar orqali o‘tishi tushiniladi. Nafaqat paket o‘tgan oraliq nuqtalar, u qo‘shni marshrutizatorlar orasida aloqa bo‘yicha o‘tgan vaqtini ham hisobga oluvchi boshqa metrika ham ishlatiladi. Qo‘shni marshrutizatordan vektorni qabul qilib har bir marshrutizator o‘zi bevosita (agar tarmoqlar uning portiga ulangan bo‘lsa) yoki qo‘shni marshrutizatorlarning o‘xshash elementlaridan bilib olgan unga ma’lum boshqa tarmoqlar to‘g‘risida axborotni vektorga qo‘shadi va tarmoq bo‘yicha vektorning yangi mazmunini jo‘natadi, oxir oqibat har bir marshrutizator inter tarmoqdagi tarmoqlar va qo‘shni marshrutizatorlar orqali ularga bo‘lgan masofa to‘g‘risida axborotni bilib oladi.
Ushbu misolda rasmda ko'rsatilganidek, X, Y va Z 3 marshrutizatorni ko'rib chiqamiz. Har bir marshrutizatorning marshrutlash jadvali mavjud. Har bir marshrutlash jadvali maqsad tugunlarigacha bo'lgan masofani o'z ichiga oladi.

Ko'rib turganimizdek, Y oraliq tugun (hop) bo'lsa, masofa X dan Z gacha kamroq bo'ladi, shuning uchun u X marshrutlash jadvalida yangilanadi.

Masofa-vektor algoritmlari uncha katta bo‘lmagan tarmoqlardagina yaxshi ishlaydi. Katta tarmoqlarda ular intensiv keng ogoxlantirish trafigi bilan aloqa liniyalarini sifatsiz qiladilar. Bundan tashqari bu algoritm konfiguratsiyaning o‘zgarishi har doim ham to‘g‘ri bajarilmaydi, chunki marshrutizatorlar armoqdagi aloqalar topologiyasi aniq tushunchaga ega emaslar, ular faqat vositachilar orqali olingan, umumlashgan axborotga – masofa-vektoriga egalar. Masofa-vektori protokoliga muvofiq marshrutizator ishi ko‘prik ishini eslatadi, chunki bunday marshrutizator tarmoqning aniq topologik sur’atiga ega emas.