8 Ma'ruza. Tarmoq bog'lanishlari: “Kliyent- server” dasturlash modeli. Reja

Internet-tarmoqlardagi marshrutlashtirish
Marshrut bu jo'natuvchidan oluvchiga yo'lda yotadigan tugunlar ketma-ketligi hisoblanadi. Marshrulashtirish masalasi quyidai ikki vazifalarni o'z ichiga oladi:

1. 
   Marshrutni aniqlash;
   
2. 
   Tanlangan marshrut haqida tarmoqni ogohlantirish.
   

Marshrutni aniqlash ma'lumotlarni manzilga etkazish uchun ular orqali ma'lumotlar uzatiladigan tranzit tugunlar va ularning interfeyslari ketma-ketligini tanlanishini bildiradi. Agar o'zaro ta'sirlashuvchi tarmoq interfeyslari juftligi orasida ko'plab yo'llar mavjud bo'lsa, u holda qandaydir mezon bo'yicha bitta optimal yo'l tanlanadi.
Xost-manbadan xost-qabullagichga paketning yo'lini tanlanishi masalasi marshrutizator-manbadan marshrutizator-qabulagichga paketni tanlash masalasiga keltiriladi.
Istalgan marshrutlashtirish protokolining o'zagi marshrutizator-manbadan marshrutizator-qabulagichga paketni yo'lini aniqlaydigan algoritm (marshrutlashtirish algoritmi) hisoblanadi. Marshrutlashtirish algoritmining vazifasi oddiy: berilgan marshrutizatorlar va ularni bog'laydigan liniyalar ko'pligi uchun marshrutlashtirish algoritmi marshrutizator-manbadan marshrutizator-qabulagichga "optimal" yo'lni aniqlaydi. "Optimal" so'zi "minimal narxli" yo'lni bildiradi. Biz ko'ramizki, biroq amalda o'yinga xavfsizlik masalalari kabi strategik mulohazalar kiradi.
Marshrutlashtirish algoritmlarini ifodalash uchun tarmoq graf sifatida qaraladi (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.

2-rasm. Tarmoqning abstrakt modeli.

Tarmoqni graf ko'rinishida ko'rib chiqishda jo'natuvchidan oluvchiga minimal narxdagi yo'lni aniqlash masalasini echish uchun shunday liniyalarning ketma-ketligini topish kerakki, bunda:

• 
  yo'lning birinchi liniyasi manba bilan bog'langan;
  
• 
  yo'lning oxirgi liniyasi manzil bilan bog'langan;
  
• 
  ivai - 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, 2-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'natuvchidan oluvchigacha eng kam narxli yo'lni topadi. Hisoblashlarning o'zi qandaydir bitta kompyuterda amalga oshirilishi yoki turli joylarda ko'paytirilishi mumkin. Lekin bu erdagi 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 iterasion hisoblashlar va qo'shi tugunlar 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.
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.