Kommunikasiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

109 
Marshrutlashtirish algoritmlarini ifodalash uchun tarmoq graf sifatida 
qaraladi (9.2-rasm). Grafning tugunlari paketlarni harakatlanishi haqida qaror 
qabul qilinadigan marshrutizatorlar-nuqtalar, bu tugunlarni bog‘laydigan liniyalar 
(graflar nazariyasi terminologiyasiga muvofiq “qirralar” deyiladigan) esa 
marshrutizatorlar orasidagi fizik liniyalar hisoblanadi. Har bir aloqa liniyasiga bu 
liniya bo‘yicha paketning qayta uzatilishi “narxidan” iborat bo‘lgan qandaydir 
qiymat mos keladi. Narx liniyaning fizik uzunligiga (masalan,transokean kabeli 
bo‘yicha kadrni uzatilishi narxi quriuqlikda yotqizilgan qisqa kabel bo‘yicha 
uzatish narxidan qimmat bo‘lishi mumkin), liniya bo‘yicha ma’lumotlarni uzatish 
tezligiga yoki liniyaning moliyaviy narxiga bog‘liq bo‘lishi mumkin.
16
10.1-rasm. Tarmoqning abstrakt modeli. 
Tarmoqni graf ko‘rinishida ko‘rib chiqishda jo‘natuvchidan oluvchiga 
minimal narxdagi yo‘lni aniqlash masalasini yechish uchun shunday liniyalarning 
ketma-ketligini topish kerakki, bunda: 

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. 
16
James F. Kurose, Computer Networking ATop-Down Approach 6
th
Edition// 2013 by Pearson Education. 

110 
Masalan, 10.1-rasmda A (jo’natuvchi) va S (qabul qiluvchi) tugunlar 
orasidagi minimal narxli yo‘l ADEC marshrut hisoblanadi. 
Barcha 
marshrutlashtirish 
algoritmlarini 
ikkita 
global 
va 
markazlashtirilmagan sinflarga bo‘lish mumkin.
17

Global marshrutlashtirish algoritmi tarmoq haqidagi to‘liq ma’lumotlar 
yordamida jo‘natuvchidan oluvchigacha eng kam narxli yo‘lni topadi. 
Hisoblashlarning o‘zi qandaydir bitta kompyuterda 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’lumotlarga 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’lumotlarga 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 
protivopolojnыx konsax 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 insonning aralashuvi natijasida (masalan, tarmoq 
ma’muri marshrutizatorning ma’lumotlarini harakatlanishi 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. 
17
James F. Kurose, Computer Networking ATop-Down Approach 6
th
Edition// 2013 by Pearson Education 

111 
Marshrutlashtirish algoritmlarini tasniflashning uchinchi usuli algoritm o‘ta 
yuklanishga sezgirligi bo‘yicha aniqlanadi. O‘ta yuklanishga sezgir algoritmda 
liniyalarning narxlari mos liniyalardagi 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 yuklanishga 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. 
Marshrutlashning to'xtatilishi deyilganda, odatda paketning birlashgan 
tarmoqlar orqali manbadan to tayinlangan nuqtasigacha yurish uchun kerak bo'lgan 
vaqtning bir qismi tushuniladi. To'xtalish ko'pgina omillarga: tarmoqning 
oraliq kanallarining o'tkazish yo'li, paket borish yo'lida, xar bir marshrutizatorning 
portiga navbat. Tarmoqning oraliq xamma kanallarida tarmoqning ortiqcha 
yuklanishi va paket ko'chirilishi kerak bo'lgan fizik masofaga bog‘liq.O'tkazish 
yo'li, bironta kanal trafikining bor quvvatiga kiradi. Boshqa teng ko'rsatkichlarda, 
Ethernet 10Mb/s kanali, 64Kbayt/s li o'tkazish yo'lli xar qanday ijaraga olingan 
liniyaga nisbatan afzalliroq. Yo'nalish tanlashda marshrutizator va oxirgi tugun
ishi bo'lib, marshrutlash jadvalini qurish usuli xisoblanadi. Marshrutizatorlar
xizmat axborotlari bilan almashib avtomatik marshrutlash jadvalini tuzishadi.
Bu maqsadda, marshrutizatorlar orasida xizmat axborotlari bilan almashishning 
har xil protokollari ishlatiladi.Yuqorida ko'rsatilgan marshrutlash o'lchovlari va
algoritmlari asosida IP tarmoqlarida marshrutlash negizlari va algoritmlarini 
ko'rib chiqamiz. 

Download 11,41 Mb.