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.
