Jlantirish vazirligi toshkent axborot texnologiyalari universiteti urganch filiali
, agar ut = Uj bo'lsa yoki ularning umumiy uchi bo'lmasa
Download 401.28 Kb.
|
multimediya trafiklarini zamonaviy darajadagi marshrutizatsiyalash
- Bu sahifa navigatsiya:
- Masalaning qo‘yilishi
- Marshrutlash algoritmlari va protokollari.
|
0, agar ut = Uj bo'lsa yoki ularning umumiy uchi bo'lmasa.
quyidagicha aniqlangan C = (cij) (i = 1,2,..., n, j = 1,2,...,n) nxn -matritsa grafning qirralari qo‘shniligi matritsasi deb ataladi.
Ravshanki, sirtmoqsiz va karrali qirralarsiz graf qirralari qo‘shniligi matritsasi bosh diagonalga nisbatan simmetrik kvadrat matritsadir va uning bosh diagonali nollardan iborat. Insidentlik matritsalari. Uchlari 1,2va qirralari щ,и2,...,ип (n > 1) bo‘lgan belgilangan graf berilgan bo‘lsin. Bu grafning uchlariga satrlari, qirralariga esa ustunlari mos keluvchi va elementlari ko‘rinishda aniqlangan B = (by) (i = 1,2,..., m, j = 1,2,..., n) matritsa grafning insidentlik matritsasi deb ataladi. Endi uchlari 1,2va qirralari ui,u2,...,u„ (n > 1) bo‘lgan belgilangan sirtmoqsiz orgrafni qaraymiz. Elementlari ko‘rinishda aniqlangan B = (bij) (i = 1,2,...,m, j = 1,2,...,n) matritsaga grafning insidentlik matritsasi deb ataladi. teorema. Graflar (orgraflar) faqat va faqat insidentlik matritsalari bir-birlaridan satrlarining o'rinlarini va ustunlarining o'rinlarini mos almashtirishlar yordamida hosil bo 'lsagina izomorf bo'lishadi. Bajardi: bet: Kutliboyev T.Q. Masalaning qo‘yilishi Telekommunikatsiya tarmoqlari va tarmoq tugunlarining faoliyati samaradorligi asosan marshrutlash masalalarini echish bilan aniqlanadi. Odatda marshrutlash algoritmlari yoki amallari ikki bosqichni ko‘zda tutadi: Tayyorlov va marshrutlash jarayonining o‘zi. Tarmoqlarda marshrutlash masalalarini echish uchun yuqori o‘xshashlikka ega, biroq shu bilan birga tarmoqning notekis yuklashga olib keladigin taqsimlangan boshqaruvga asoslangan algoritmlar qoTlaniladi. Paketlarni uzatish samaradorligini ta’minlashga imkon beradigan, shuningdek mavjud taqsimlangan marshrutlash usullari bilan uyg‘unlashgan yangi metodlarga extiyoj paydo bo‘lmoqda. Bunday masalalarini echishi mumkin bo‘lgan yondashuvlardan biri tarmoq sigmentlarda garflar nazariyasi Deykstra algoritm asosida axborotlarni marshrutlash, taqsimlash vazifasini bajaruvchi mavjud marshrutlash algoritmlariga qo‘shimcha funksiyalarni kiritish bo‘lishi mumkin. Bunday yondashuvni amalga oshirishda, tarmoqdagi yuklamalarni muvozanatlovchi usullarini yaratishdagi quyidagi masalalarni amalga oshirish lozim bo‘ladi: marshrutlash jarayonining tavsifi; marshrutlash protokollari ; marshrutlash jarayonini graflarda ifodalash marshutlash masalalarida yuklamalarni taqsimoti; yuklama taqsimlashning mezonlari; dinamik marshrutlash usullari tadqiqi.
ТармоПда маршрутлаш меъзонлари тахлили. Marshrutlash - bu tarmoqlar orqali manba tugundan belgilangan tugungacha axborotlarning belgilangan yo‘nalish bo‘yicha uzatilishi tushuniladi. Bunda, yo‘nalish davomida bir necha tugun orqali ma’lumotlarni mashshrutlash mumkin. Marshrutlash ikkita asosiy vazifani bajaradi: marshrutlashning optimal traktlarini belgilash va tarmoq orqali axborot guruhlarini uzatish. Marshrutlash algoritmini ishlab chiqarishda bitta yoki bir nechta me’zonlar ko‘zda tutish mumkin: Optimallik. Oddiylik Sarf xarajatlar. Yashovchanlik 10.Stabillik. Optimallik sohaning eng umumiy maqsadi bo‘lib hisoblanadi. U marshrutlash algoritmining eng yaxshi yo‘nalishini tanlash qobiliyatini belgilab beradi. Oddiylik va sarf xarajatlar. Marshrutishlash algoritmlarini yaratishda oddiylikka erishishga xarakat qilinadi, ya’ni u o‘z funksional imkoniyatlarini dasturiy ta’minotni va ishlatish koeffitsiyentini minimal xarajatlar bilan samarali ta’minlashi kerak. Samaradorlik ayniqsa marshrutlash algoritmini amalga oshiruvchi dastur kompyuterda yoki fizik resurslari cheklangan tugunlarda ishlashi kerak bo‘lgan holda juda muxim bo‘ladi. Marshrutlash algoritmlari yashovchanlikka ega bo‘lishi kerak.
Boshqacha qilib aytganda ular turli sharoitlarda ya’ni qurilmalar buzilganda, yuqori yuklanish holatlarida va noto‘g‘ri foydalanishlarda aniq vazifalarni bajarishlari kerak. Marshrutlash algoritmlari turli me’zonlarni inobatga olgan holda ishlab chiqiladi. Murakkab marshrutlash algoritmlari yo‘nalish tanlaganlarida bir qancha me’zonlarga asoslanishi mumkin va ularni kombinatsiyalab, natijada bitta alohida koyeffitsiyent ko‘rsatkichiga keltirib soddalashtirish mumkin. Pastda marshrutlash algoritmi ishlatiladigan me’zonlar ko‘rsatilgan: Yo‘nalish uzunligi. Ishonchlilik. To‘xtalish. 10.0‘tkazish yo‘lining kengligi. Yuklanish. Aloqa tannarxi. Yo‘nalish uzunligi marshrutlash jarayonining umumiy ko‘rsatkichi xisoblanadi. Marshrutlashning ayrim protokollari tarmoq adminstratorlariga tarmoqning har bir kanaliga o‘z xolicha parametr tayinlashga imkon beradi. Bu xolda, traktning uzunligi bo‘lib, xisobga olingan xar bir kanal bilan bog‘liq, xarajat mablag‘i hisoblanadi. Marshrutlashning boshqa protokollari “uzatishlar soni” ni aniqlaydilar, ya’ni birlashgan tarmoqlar uskunalari (marshrutizatorga o‘xshagan) orqali manbadan to tayinlanish nuqtasi orasidagi yo‘lda paket bajarishi kerak bo‘lgan, o‘tishlar sonini tavsiflovchi ko‘rsatkich hisoblanadi.
Marshrutlash algoritmida ishonchlilik deganda tarmoqning xar bir kanalidagi ishonchlilika kiradi. Tarmoqning ayrim kanallari boshqalariga nisbatan ko‘proq rad etishi. Bir xil kanaldagi raddiyalarni, boshqalariga nisbatan tezroq bartaraf etish mumkin. 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. 0‘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. Marshrutlash algoritmlari va protokollari. Barcha mavjud tarmoqlar marshrutizatorlari va tarmoq tugunlarida
yaratilgan marshrutlash jadvallari asosida marshrutlash jarayonini boshqaradi. Asosan Floyd va Deykster yoki Belmann Ford algoritmlariga asoslangan algoritmlar asosida, marshrutizatorlarda avtomatik yoki tarmoq adminstratorlari tomonidan qo‘lda marshrutlash jadvallarini sozlash, tuzatish va qo‘shimchalar qo‘shish jaryonlari orqali marshrutlash jadvalini tuzish mumkin. Marshrutlash jadvali tuzishda marshrutizatorlar maxsus protokollari yordamida tarmoq topologiyasi to‘g‘risida ma’lumotlarni yig‘ib o‘zaro almashib turadilar. Bunday protokollarga marshrutlash protokollari deb ataladi. RIP, OSPF, NLSP marshrutlash protokollarini, IP, IPX tarmoq protokollaridan farqlash kerak. Ikkala tur protokollar OSI modelining tarmoq darajasi vazifalarini bajaradilar va paketlarni har xil tarmoq manzillariga yetkazib berishadi. Shu vaqtda birinchilari chida faqat xizmat axborotini yig‘ib uzatishadi, ikkinchilari esa kanal darajasi protokollari kabi foydalanuvchilar ma’lumotini uzatish uchun mo‘ljallangan. Marshrutlash protokollari tarmoq protokollarining transport vositasi sifatida .shlatishadi. Marshrutlash protokollari paketlari yo‘nalish ma’lumotlari bilan almashganda, tarmoq darajasi transport darajasi paketlarining ma’lumotlar maydonida joylashtiriladi. Shu sababdan paketlarni joylashtirish nuqtaiy nazaridan marshrutlash protokollarini rasmiy tarmoq darajaga nisbatan yuqoriroq iarajada deb qaralishi kerak. Marshrutizatorlar paketlarning marshrutlarini aniqlash uchun manzil advallariga murojaat qilganida, ularning murojaat uslublari ko‘prik va commutator bilan o‘xshashligini, ammo ular ishlatadigan adres jadvallarining strukturasi farq qilishini bilish mumkin. Jarayonda MAS-adreslar o‘rniga marshrutlash jadvalida intertarmoq ulanadigan tarmoq manzili ko‘rsatiladi. Marshrutlash jadvalining ko‘priklar manzil jadvalidan boshqa farqi bo‘lib, ularni tuzish usuli hisoblanadi. Lokal tarmoq ko‘priklari jadvalini qurish paytida, o‘zi orqali o‘tayotgan tarmoqning oxirgi tugunlari o‘zaroga uzatayotgan kadrlarini passiv nazorat qilib turgan vaqtda, marshrutizatorlar o‘z initsiatrivasi bilan
maxsus xizmat paketlarini almashadilar va intertarmoqdagi tarmoqlar, marshrutizatorlar va joriy tarmoqlarning marshrutizatorlar bilan bog‘lanishi to‘g‘risida qo‘shnilariga ma’lumot uzatadilar. Odatda, aloqaning nafaqat topologiyasi balki o‘tkazish qobiliyati va holati hisobga olinadi. Bu marshrutizatorlarga tarmoq konfiguratsiyasining o‘zgarishlariga tezroq moslashishga hamda, o‘z holli topologiyali tarmoqlarda paketlarni to‘g‘ri uzatishga imkon beradi. Marshrutlash protokollari yordamida marshrutizatorlar u yoki bu darajadagi tarmoq bog‘lanishlarining jadvalinini yaratadilar. Ushbu axborot asosida tarmoqning har bir nomeri uchun ma’qul bo‘lgan yo‘nalishni topish uchun, shu tarmoqqa jo‘natilayotgan paketlar keyingi marshrutizatorlarning qaysi biriga uzatilishi to‘g‘risida qaror qabul qilinadi va natijasi marshrutlash jadvaliga kiritiladi. Tarmoq konfiguratsiyasi o‘zgarganda maro‘rutlash jadvalidagi ayrim ma’lumotlar samarasiz bo‘lib qoladi. Bunday vaziyatlarda shu yo‘nalish bo‘yicha yuborilgan paketlar yo‘lda to‘xtab qolishi yoki yo‘qolishi mumkin. Marshrutlash protokoli qanchalik jadval ichidagi ma’lumotlarni tarmoqning oriy xolatiga moslashtira olishi butun tarmoqning ishlash sifatiga bog‘liq bo‘ladi. Optimal yo‘nalishni tanlash usuli va o‘z ishining boshqa xususiyatlari bilan ?arqlanib turuvchi xar xil algoritmlar asosan tuzilishi mumkin. Optimal yo‘nalish tanlashda, boshlang‘ich tugunidan to oxirgi tugungacha '30‘lgan marshrutizatorlarning butun ketma-ketligi emas, faqat keyingi yaqin marshrutizator aniqlangan. Ushbu algoritmga muvofiq marshrutlash taqsimlangan usul bo‘yicha amalga oshiriladi va har bir marshrutizator yo‘nalishining faqat bitta qadamini tanlash mumkin, butun yo‘nalishning tuzilishi, ushbu paket o‘tgan barcha marshrutizator ishlash natijasidan kelib chiqadi. Marshrutlashning bunday algoritmlari bir qadamli deyiladi. Bir qadamli marshrutlash usuliga teskari ko‘p qadamli yondoshish usuli ham mavjud. Bu usulga Source Routing - manbadan marshrutlash deyiladi. Bu
usulga ko‘ra, manba tarmoqdan yuborilayotgan paketda, u tarmoqdagi hamma oraliq marshrutizatorlari haqida to‘la yo‘nalish belgilanadi. Ko‘p qadamli marshrutlash usulidan foydalanilganda paketlar o‘tadigan oraliq marshrutizatorlarda marshrutlash jadvalini qurish va taxlil qilishga extiyoj qolmaydi. Bunday usul tarmoqda paketlarning o‘tishini tezlashtiradi, ammo marshrutizatorlarni yuklanishi ortadi, ya’ni bunda tarmoqning oxirgi tugunlariga katta yuklanish tushadi. Bu usul tarmoqlarda bugungi kunda taqsimlangan bir qadamli marshrutlashga qaraganda juda kam qo‘llaniladi. Yangi versiyasidagi IP protokollari klassik bir qadamli marshrutlash hamda manbadan marshrutlash usullarini ham qo‘llashi mumkin. Marshrutlash jadvalini tuzish usuliga qarab bir qadamli algoritmlar uchta sinfga ajratiladi: Download 401.28 Kb. Do'stlaringiz bilan baham: 
|