O‘zbekiston respublikasi oliy va o‘rta maxsus ta’lim vazirligi m. Ulug‘bek nomidagi o‘zbekiston milliy universiteti nazarov xusanbek avazbek o‘G‘LI

2.4.1. Marshrutizatsiyalash turlarining klassifikatsiyasi

Yo‘naltiruvchi, odatda, bir necha mezonlarga muvofiq tasniflanadi. Marshrutlashni tarmoq ustida vaziyatga qarab farq qilishi bo‘lsa, odatda statik (turg‘un) axborot tarmog‘ining oqimini har bir yo‘nalish qidiruv vazifasi ko‘p marta yoki juda uzoq vaqt haqida ham hal bo‘ladi, yo‘l-yo‘riq va adaptiv marshrutlash ko‘rib chiqiladi.

Marshrut matritsalari qayerda hisoblanadiganligi va bu tugun uchun marshrutni qaror qabul qilinganligiga qarab, moslashtirilgan yo‘l-yo‘riq bilan quyidagilarni aniqlaymiz:
- markazlashgan marshrutlash, marshrut xaqida qaror tarmoqni boshqarish markazida yoki tarmoqni marshrutlash markazida qabul qilinadi;
- (markazlashmagan) yo‘l-yo‘riq, qaysi tarmoq barcha tugunlari aniqlaydigan qisqa yo‘llar, tugun o‘rtasidagi xizmat ma’lumotlar ma’lum algoritmlar almashishni foydalanib yo‘nalishlari tuguniga kiruvchi holatini aks ettiradi;
- izolyatsiyalangan usulda har bir tugunni uning qo‘shnilari bilan axborot almashish holda individual mezonlar bo‘yicha uzatish haqida qaror qabul qiladi;
- markazlashtirilgan va taqsimlangan marshrutning bu yoki shu kombinatsiyasini ifodalovchi aralash usul.
Yana bir muhim omil qaror tarmoq tugunlarida marshrutni o‘zgartirish amalga oshiriladi vaqtidir. Bunda dinamik boshqarishning
determinantlangan (xodisalar bo‘yicha) usulini ajratish mumkin, unda tarmoq yoki uskunalar nosozliklar uchastkalarida tarmoq tiqilishi qaydlangan marshrutlash, tarmoq boshlanganda faol nazorat usullari o‘zgartiriladi, va hokazo, vaqti-vaqti bilan operatorlar ularni statistik meyor bo‘yicha ajratishi mumkin. olis yo‘ldan yuborishdan oldingi xizmat chaqiriqlar yoki chaqiriqlar guruhiga yakunlari bo‘yicha doimiy sodir bo‘ladi.
Ta’kidlash joizki, tarmoq seksiyalarida haddan tashqari yuklamalar bo‘lishi, odatda uskunalarning ishdan chiqishiga (buzilishiga) qarama-qarshi ravishda ishlashga qobiliyatsiz deb aytiladi. Funksional raddiyalardan tarmoqning boshqaruvchi ta’sirga U(t+At) reaksiyasi sezilarli darajada bog‘liq (2.5-rasmga qarang).
Bu yerda, haddan tashqari hollarda statistika yig‘ish muhim usullari bo‘lib, hisoblash vaqt miqdori va yo‘l hisoblash algoritmi ishlashi hisoblash resurslari tarmoq nazorat qilish markazi va xizmat ma’lumot uchun uzatish kanalidan foydalaniladi. Agar bu xususiyatlar to‘g‘ri tanlanmagan bo‘lsa, tarmoq reaksiyasi kam bo‘lishi mumkin. Shu munosabat bilan, tarmoqni avtomatlashtirish darajasi ham muhim rol o‘ynaydi, marshrutlarni o‘zgartirishlar qo‘lda yoki avtomatik ravishda o‘zgartirilishi muximdir.
Tarqatish rejasini tuzatish haqida ma’lumot chaqiriqlar guruhi olingandan keyin amalga oshiriladi, bunda aralash yoki guruhiy bo‘lishi mumkin, har bir talabnoma olinganidan keyin amalga oshiriladi, determinant adaptiv marshrutlash usullari bitta bo‘lishi mumkin. Dinamik nazoratning taniqli bir martalik usullari to‘lqin uslubi, relyef usullari va matritsa uslubi guruhning deterministik usullari bilan bog‘liq. Yengil usullarda taqsimlangan mardrutlashni amalga oshiradi va matritsa uslubi – markazlashtirilgan bo‘ladi. Tarmoqdagi chaqiriqlarning taqsimlashning ma’lum statistik usullari inersiya va o‘yin uslubi bilan tushadigan usul hisoblanadi.
Paketlar kommutatsiyalanadigan tarmoqlarda marshrutlash strategiyasi tarmoqlarda tarqalgan marshrut uchun joriy kechikish (liniya bo‘yicha uzatish vaqti plyus xizmati tugunida kutish vaqti), joriy kutishga teng bo‘ladi va eng qisqa yo‘l tanlanadibor.
Murakkab marshrutga misol delta marshrutlashdir. Shu bilan SMC har bir manba-maqsad juftligi uchun bir qator muqobil yo‘llarni belgilaydi va uni tugunlarga yo‘naltiradi. Liniyalardagi o‘rtacha kechikishlar har bir tugundan SMC ga uzatiladi. Berilgan manba maqsad juftlik uchun muqobil yo‘llar o‘rtasidagi sekinlashuviga farq 8 doirasida bo‘lsa, SMC deb manbai ko‘rsatmalarni yubora olmaydi va montaj qilish xavfsiz holatga yo‘l-yo‘riq ishlaydi. Agar kechikish o‘zgarishi 8dan oshsa, SMC bu tugunni kichikroq kechikish bilan ishlatishni taklif qiladi.
Har qanday marshrutlash yo‘nalishi uchun marshrutlarni hisoblash uchun algoritmlarning ikkita asosiy sinfi ishlatiladi:
- eng qisqa yo‘lni aniqlovchi algoritmlar, bu ma’lum bir manba-manzil juftini eng maqbul yo‘lni (eng qisqa yo‘l bilan berilgan) tanlashni ta’minlaydi;
- mumkin bo‘lgan marshrutlarni tanlash uchun extimolli algoritmlar (muqobil) kamaytirish (maksimallashtirish) manba manzil juft hisobga butun tarmog‘ida manba joyga barcha juftlarni o‘rtasidagi tarmog‘ini kirib o‘rtacha yuklanishni marshrutlash tanlanganda, berilgan mezonda aniqlanadi. Bunday holda, ma’lum bir manba-juftlik juftligi uchun bir necha marshrutlar tanlov ehtimoli bilan aniqlanadi.
Eng qisqa yo‘llar aniqlash uchun algoritmlar asosan ikki usul ishlatiladi: tugunlar va shaxobchalarni raqamlash usuli va matritsa usullari. Tugunlar va shaxobchalarni raqamlash usullari, odatda, iteratsion usullardir va berilgan tugundan tarmoqning boshqa barcha tugunlari qisqa yo‘lni aniqlash imkonini beradi. Matritsa usullari bir vaqtning o‘zida, tarmoq shaxobchalari vaznlari matritsalari ustidani operatsiyalar yordamida, tarmoq barcha tugun o‘rtasidagi eng qisqa yo‘lni topish imkonini beradi. Paketli kommutatsiya tarmoqlarida yana ikkita usul, yuqoridagi usullarini turlari bo‘lgan, eng ko‘p qo‘llanadigan usullar bo‘ldi: Ford va Falkerson usuli va Diykstra usuli.
Tugunlari va shaxobchalarni raqamlash, birinchi bo‘lib Floyd tomonidan taklif etilgan algoritmlari sinflaridir, raqamlash va tarqatilgan marshrut uchun taalluqli Ford va Fulkerson algoritm usullari jeb ataldi. Bu iterativ algoritm bitta tugun uchun barcha kommutatsiya uzeliga eng qisqa yo‘lni topish. teng uzunligi bir nechta yo‘ldan shu algoritm bilan (vazn) yo‘llar notekis yuklanishiga olib kelishi mumkin. Ushbu nuqson Floydning o‘zgartirilgan algoritmida yo‘qoladi.
Diykstrning algoritmi matritsa usuliga taaluqlidir va va iteratsion usullarga mutanosibdir. Ushbu algoritm markazlashtirilgan marshrutizatsiyani qo‘llab-quvvatlaydi, uning ishlashi uchun tayanch yoki ABM yoki TMU ma’lumotlari mavjud tarmoq tuzilishi haqida to‘liq ma’lumot beradi.
Marshrutlarni ehtimolli (muqobil) tanlash algoritmlari, qoida tariqasida, tarmoq shaxobchalari bo‘yicha ko‘p maxsulotli oqimni optimal taqsimlash masalalarini yechish usuliga olib keladi. Bunday masalalarini yechish uchun turli iteratsion algoritmlar qo‘llaniladi. Ulardan biri – oqimlarni deviatsiyalash usuli
(M. Gerla, 1973), uning uchun hisoblashning nisbatan kichik miqdori, lekin juda sekin yaqinlash- bilan tavsiflanadi. Ekstremal oqimlari usuli asosidagi yana bir algoritmi gradiyent turidagi usul yoki iteratsiyani tezlashtirish uchun ishlatiladi.