Telekomunikatsiya tarmoqlarida axborot oqimi trafikini topologik optimlalaytirish texnologiyalari

Dinamik dasturlash usullari.

Axborot uzatishning eng qisqa yo'llarini topish muammolari dinamik dasturlashning uchta asosiy xususiyati bilan tavsiflanadi: ko'p yo'nalishli tanlov, qo'shimchalilik va tarixdan oldingi davrdan optimal yo'lning mustaqilligi. Haqiqatan ham, tarmoqdagi tugundan tugunga xabarlarni uzatish jarayonini o'rganish alohida bosqichlarga bo'linadi (ko'p tomonlama tanlov); bir necha shoxlardan tashkil topgan yo'lning uzunligi yig'indiga tenguzunliginbularX filiallari (mulkqo'shimchalar),Va,otdac, eng qisqaqo'yishb yuqish xabarlarVahnima-yokidayomonYo'qbog'liq danBormoq, QanaqasigaxabarlareurishO VBuTdayashil, AfaqatdanManzilIbuO tugun V tarmoqlar(mulk tarixdan oldingi mustaqillik) [2]. Amalda ular qo'llanilishini topdilar: Floyd-Uorshall usuli, Bellman-Ford usuli, shuningdek, kamroq ma'lum bo'lgan matritsa usuli.
Floyd-Uorshall usuli[3], asosiy chiziq va uchlik amal tushunchalariga asoslanib, vaznli yoʻnaltirilgan grafikning barcha uchlari orasidagi eng qisqa masofalarni topish uchun foydalaniladi. Ushbu usulning afzalliklari - amalga oshirish algoritmining soddaligi va barcha tarmoq tugunlari uchun marshrutlash ma'lumotlarini bir vaqtning o'zida olish imkoniyati, bu uni markazlashtirilgan tuzilmalarda qo'llashni maqsadga muvofiq qiladi. boshqaruv axborot oqimlar. Dasturiy ta'minotni amalga oshirishda ushbu usulning murakkabligi haqida gapiradigan bo'lsak, shuni ta'kidlash kerakki, uchta ichki halqa doimiy vaqt ichida bajariladigan operatsiyani o'z ichiga oladi, ya'ni algoritm kubik murakkablikka ega [4]. Hozirgi vaqtda tizimlardan foydalanishni tezlashtirish usullari mavjud
the usul, ruxsat berish kamaytirish murakkablik Bilan On3 oldin On3 log n , bu erda n - tarmoq tugunlari soni. Biz bit niqoblaridan foydalanish haqida gapiramiz (oraliq mahsulot bilan modelda
hisoblash natijalarini operativ xotirada saqlash) va mikroprotsessorlarning ixtisoslashtirilgan to'plamlari SSE (Streaming SIMD Extensions) kabi buyruqlar ishlash ustunligi xuddi shunday amalga oshirilgan taqdirda erishiladi bir xil ketma-ketliklar turli ma'lumotlar ustida operatsiyalar.
Bellman-Ford usuli[5] vaznli grafikdagi eng qisqa yoʻlni topish uchun ishlatiladi. Asosiy afzallik - salbiy og'irlikdagi qirralarga ega bo'lgan grafikdagi yo'lni hisoblash qobiliyati. Eng qisqa yo'lni hisoblash uchun bu usul faqat talab qiladi
n1 sikllar Lekin yoqilgan ushbu algoritmni mashq qiling mumkin
dan foydalaning va aniq n tsiklni ishga tushirish orqali salbiy tsikllarni kuzatish uchun. Agar oxirgi iteratsiyani bajarish paytidahar qanday cho'qqigacha bo'lgan eng qisqa yo'lning uzunligi qat'iy ravishda kamayadi, keyin grafik salbiy tsiklga ega. Grafikdagi o'zgarishlarni kuzatishingiz mumkin va ular tugagach, keyingi takrorlashlar ma'nosiz bo'ladi. Ushbu usul RIP (Routing Information Protocol) marshrutlash protokoli va uning modifikatsiyalarida qo'llaniladi va uning o'zgartirilgan ba'zi versiyalari katta hisoblash quvvatini talab qilmaydigan kichik tarmoqlarda (15 ish stantsiyasidan ko'p bo'lmagan) qo'llaniladi.
yo'llarni hisoblash, shuningdek, deyarli o'zgarmagan tuzilishga ega tarmoqlar uchun.
Matritsa usulieng qisqa ta'riflar Barcha tarmoq tugunlari orasidagi yo'llar Shimbel [6] tomonidan taklif qilingan va Otterman [7] tomonidan takomillashtirilgan. Tarmoqni to'liq topologik tahlil qilish imkoniyati tarmoqlarda ma'lumotlarni uzatish trafigini tashkil qilishda ushbu usulning keng amaliy qo'llanilishini ta'minladi.
Matritsa usuli bilan eng qisqa yo'llarni aniqlashda quyidagi amallar bajariladi: