Декабрь 2020 17-қисм

Декабрь  2020  17-қисм

Тошкент

•  yo’lning birinchi liniyasi manba bilan bog’langan;

•  yo’lning oxirgi liniyasi manzil bilan bog’langan;

•  i va i - 1 nomerlarli barcha i liniyalar uchun o’sha bir tugun bilan bog’langan bo’lish;

•  minimal narxli yo’l uchun yo’lning barcha liniyalari narxlarining yig’indisi jo’natuvchi va 

oluvchi orasidagi barcha bo’lishi mumkin bo’lgan yo’llar bo’yicha minimal hisoblanadi.

Masalan, rasmda A (otpravitelem) va S (poluchatelem) tugunlar orasidagi minimal narxli yo’l 

ADEC marshrut hisoblanadi.

Barcha marshrutlashtirish algoritmlarini ikkita global va markazlashtirilmagan sinflarga bo’lish 

mumkin.

Global marshrutlashtirish algoritmi tarmoq haqidagi to’liq ma’lumotlar yordamida jo’natuvchi-

dan oluvchigacha eng kam narxli yo’lni topadi. Hisoblashlarning o’zi qandaydir bitta kompьyuter-

da amalga oshirilishi yoki turli joylarda ko’paytirilishi mumkin. Lekin bu yerdagi asosiy o’ziga 

xos xususiyat global algoritm tarmoqning topologiyasi va liniyalarning narxi haqida to’liq ma’lu-

motlarga ega bo’lishi hisoblanadi. Misol “Liniyalarning holatlariga asoslangan marshrutlashtirish 

algoritmi” hisoblanadi.

Markazlashtirilmagan marshrutlashtirish algoritmida eng kam narxli yo’lni hisoblash taqsimlan 

tarzda bajariladi. Hech bir tugun tarmoqning barcha liniyalari narxlari haqidagi to’liq ma’lumot-

larga ega bo’lmaydi. Dastlab har bir tugunga faqat unga to’g’ri ulangan liniyalarning narxi ma’lum 

bo’ladi. Keyin iteratsion hisoblashlar va qo’shi tugunlar (to yestь uzlami, naxodyaщimisya na pro-

tivopolojnыx kontsax napryamuyu prisoedinennыx k nemu liniy) bilan ma’lumotlarni almashlash 

yo’li bilan tugun oluvchigacha yoki oluvchilar guruhigacha eng kam narxli yo’lni aniqlaydi. Misol 

“Masofaviy-vektorli algoritm” hisoblanadi.

Bundan  tashqari,  barcha  marshrutlashtirish  algoritmlarini  statik  vadinamik  algoritmlarga 

bo’lish mumkin. Statik marshrutlashtirish algoritmida marshrutlar vaqt bo’yicha, ko’pincha inson-

ning aralashuvi natijasida (masalan, tarmoq ma’muri marshrutizatorning ma’lumotlarini harakat-

lanishi jadvalini qo’lda tahrir qilishi mumkin) juda sekin o’zgaradi. Dinamik algoritm davriy yoki 

topologiyaning yoki liniyalarning narxlarini o’zgarishiga javob tariqasida ishga tushishi mumkin.

Marshrutlashtirish algoritmlarini tasniflashning uchinchi usuli algoritm o’ta yuklanishga sez-

girligi bo’yicha aniqlanadi. O’ta yuklanishga sezgir algoritmda liniyalarning narxlari mos lini-

yalardagi o’ta yuklanishning joriy darajasini aks ettirish bilan dinamik o’zgaradi. Agar vaqtinchalik 

o’ta yuklangan liniya orqali yuqori narx hosil qilinsa, marshrutlashtirish algoritmi o’ta yuklangan 

liniyani aylanib o’tish marshrutlarini tanlashga harakat qiladi. Bugungi kunda Internetda o’ta yuk-

lanishga sezgir bo’lmagan algoritmlar (RIP, OSPF va BGP) qo’llaniladi, chunki liniyaning narxi 

o’ta yuklanishning joriy (yoki yaqinda bo’lib o’tgan) darajasini aks ettirmaydi.

Internetda faqat ikkita liniyalarning holatlariga asoslangan dinamik global algoritm va dinamik 

markazlashtirilmagan masofaviy-vektorli algoritmlar turlari ishlatiladi.