مقاله بهینه سازی وزن های پروتکل مسیریابی OSPF با روشی مبتنی بر جستجوی تصادفی بازگشتی

word قابل ویرایش
14 صفحه
دسته : اطلاعیه ها
10700 تومان
107,000 ریال – خرید و دانلود

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

بهینه سازی وزن های پروتکل مسیریابی OSPF با روشی مبتنی بر جستجوی تصادفی بازگشتی

چکیده : در این پژوهش مساله ی بهینه سازی وزن های پروتکل مسیریابی OSPF، یکی از مشهورترین و پرکاربردترین پروتکل های درون درگاهی در اینترنت ، معرفی شده است و پس از پرداختن به فرمول بندی مساله [١] یک روش جستجوی مکاشفه ای مبتنی بر نمونه برداری تصادفی بازگشتی از فضای حالات [٣] برای حل این مساله طراحی و پیاده سازی شده و نتایج اجرای آن بر روی چند گراف تصادفی با نتیجه حاصل از حل مساله با برنامه ریزی خطی مقایسه شده است .
واژه های کلیدی: مسیریابی ، وزن هاOSPF ی، مهندسی ترافیک ، نمونه برداری تصادفی ، بهینه سازی غیرقطعی .

١- مقدمه
با گسترش اینترنت و توسعه سیستم های خودمختار در اواخر دهه ی هشتاد، کاستی پروتکل های مسیریابی نظیر RIP نمود بیشتری پیدا کرد.
با سریع تر شدن پردازنده ها و ارزان شدن سخت افزار نیاز به طراحی یک پروتکل بهینه ، گروه ٢IETF را بر آن داشت تا در این زمینه شروع به تحقیق نمایند. نتایج تحقیقات این گروه در سال ١٩٩٠ در قالب پروتکل مسیریابی OSPF ارایه شد و بسیاری از تولیدکنندگان مسیریاب از آن استقبال کردند و هم اکنون این پروتکل رایج ترین پروتکل مسیریابی درون درگاهی در اینترنت می باشد. OSPF یک پروتکل حالت پیوند است که در آن بسته های حالت پیوند که حاوی اطلاعات پیوندهای هر مسیریاب با مسیریاب های مجاورش می باشند از هر مسیریاب به همه ی مسیریاب های حاضر در آن شبکه به صورت سیل آسا ارسال می شود. هر مسیریاب با استفاده از اطلاعات بسته های حالت پیوندی که از سایر مسیریاب ها دریافت نموده بانک اطلاعاتی توپولوژی شبکه را می سازد. این بانک در واقع گراف جهت دار و وزن داری را مشخص می کند که راس های آن همان مسیریاب ها و یال های وزن دار آن پیوندهای فیزیکی بین مسیریاب ها می باشند. هر مسیریاب کوتاهترین مسیر تا دیگر مسیریاب ها را در این گراف محاسبه می کند و بسته های اطلاعاتی را همواره روی این مسیرها هدایت می نماید[۴]. پروتکل OSPF یک مسیریابی سلسله مراتبی دارد به این معنی که در آن مسیریاب های شبکه به تعدادی ناحیه دسته بندی می شوند که ارتباط آن ها از طریق ناحیه ای به نام ستون فقرات برقرار شده است .
در چنین شبکه ای برای ارسال یک بسته ابتدا باید یک مسیریابی در سطح ناحیه مبدا و سپس یک مسیریابی در سطح ستون فقرات و سپس یک مسیریابی دیگر در سطح ناحیه ی مقصد صورت گیرد. هر مسیریاب OSPF برای محاسبه ی کوتاهترین مسیرها منتهی به دیگر مسیریاب ها از الگوریتم دایجسترا بهره می گیرد که پیچیدگی زمانی این الگوریتم در (٢ ) می باشد. در این حالت مسیریابی سلسله مراتبی علاوه بر کاستن از طول جداول مسیریابی ، از n یعنی تعداد مسیریاب های هر ناحیه نیز می کاهد در نتیجه زمان محاسبه ی مسیرهای بهینه را کاهش می دهد.
۱-۱- وزن هاOSPF
پارامتری عددی که به هر پیوند اختصاص داده می شود وزن نامیده می شود و بیانگر هزینه استفاده از آن پیوند م باشد. مسیرهای بهینه بر اساس این وزن ها محاسبه می شوند. وزندهی که مسیریاب های شرکت Cisco به طور پیش فرض روی پیوندهای شبکه اعمال می کنند به نسبت عکس پهنای باند آنهاست ، یعنی هر چه پهنای باند پیوند کمتر باشد هزینه ی بالاتری به آن تخصیص می یابد. این وزندهی به این دلیل انتخاب شده که پیوندهای با پهنای باند بیشتر شانس بیشتری برای قرارگرفتن روی کوتاهترین مسیرهاOSPF ی داشته باشند و بار ترافیکی بیشتری روی آنها اعمال شود. این وزندهی اغلب بهینه نیست و می تواند منجر به ازدحام ترافیک روی بعضی از پیوندها شود.
در یک شبکه OSPF با توپولوژی و ظرفیت مشخص ، یافتن یک وزندهی بهینه برای پیوندها که ترافیک شبکه را به گونه ای متوازن روی آن توزیع نماید می تواند به صورت یک مساله ی بهینه سازی مطرح شود.
تابع هدف در این مساله ی بهینه سازی می تواند به گونه های مختلفی در نظر گرفته شود، به عنوان مثال میزان کل بسته های ناموفق می تواند یک معیار خوب برای تابع هزینه ی مسیریابی باشد، یا یک معیار ساده تر می تواند بر اساس ازدحام ترافیک روی پیوندهای شبکه تعریف شود.
همچنین برای داشتن تعریف دقیقی از مساله باید تخمینی از میزان تقاضاهای ارسال نقطه به نقطه داشته باشیم . در یک شبکه مشخص الگوی این تقاضاها به صورت دوره ای در حال تغییر است و با تغییر این الگو برای متعادل ماندن توزیع ترافیک شبکه باید وزندهی بهینه ی پیوندها بروزرسانی شود.
۱-۲- فرمول بندی مساله
گراف جهت دار و وزن دار که تابع به هر پیوند آن یک ظرفیت اختصاص می دهد به همراه ماتریس تقاضای داده شده اند. برای هر زوج میزان تقاضای ارسال برای هدایت از مبدا s به مقصد t م باشد.
اگر پس از مسیریابی همه ی تقاضاها، بار ترافیکی اعمال شده روی یال باشد و هزینه ی انتقال این ترافیک از طریق این یال باشد، می خواهیم وزندهی بهینه Wی را به گونه ای بیابیم که کل هزینه ی مسیریابی ناشی از این وزندهی یعنی تابع زیرکمینه باشد:

از آنجایی که ارسال اطلاعات روی خطوط پرترافیک شبکه کند می باشد و نیز خطر شکست ارسال را افزایش می دهد، تابع هزینه دراین مساله در بسیاری از تحقیقات تابعی خطی پاره ای و افزایشی در نظرگرفته می شود که در آن آهنگ رشد تابع بسته به میزان پر بودن یک خط بیشتر است [٢][١]، در این تحقیق برای سادگی و حفظ امکان مقایسه نتایج تابع هزینه مساله را به همین شکل در نظر گرفته ایم و هزینه ی استفاده از یال ها را به صورت (٣) قید می کنیم .
در این حالت اگر ارسال اطلاعات بین رئوس آزادانه باشد و هیچ شرطی روی انتخاب مسیرهای یکسان نداشته باشیم می توانیم مساله را به صورت زیر فرمول بندی کنیم و با روش برنامه ریزی خطی در زمان چندجلمه ای حل نماییم [۶]:

بخشی از ترافیک است که از یال a عبور می کند و شرط (۴) برای آن قید شده است که شار ترافیک ورودی و خروجی هر راس شبکه برابر می باشند.

۱-۳- پیچیدگی مساله با شرط اضافه شده به مسـاله در مسیریابی OSPF
الگـوریتم OSPF بسـته هـای اطلاعـاتی را روی کوتـاهترین مسـیرهای شبکه ارسال می کند در این حالت اگر بین دو راس شبکه بـیش از یـک مسیر کوتاهترین موجود باشد ترافیـک ارسـالی بـین ایـن مسـیرها بـه صورت تقریبا مساوی تقسیم می شود. به بیان ریاضـی بـرای هـر زوج از رئوس و هر دو یال خـارج شـونده از راس u که روی کوتاهترین مسیر موجود بین s و t می باشدداریم :

و اگر یال (u,v) روی کوتاهترین مسیر از s به t نباشد داریم :

بااین شرط اضافه شده حتی یافتن یـک وزنـدهی نزدیـک بـه وزنـدهی بهینه ، مساله اNP-hard خواهد بود. این نتیجه برای دسته ای از توابع هدف شامل تابع هدف تعریف شده در رابط ه ی (٣) در قالـب قضـا ایی بیان و اثبات شده است [١][۵].
۲- روش تحقیق
در این تحقیق برای حل مساله ی مورد بحث از یک روش بهینه سازی غیرقطعی استفاده شده است . روش های بهینه سازی غیرقطعی به جای سعی در یافتن جواب بهینه ی عمومی که وقت گیر است به یافتن جوابی نزدیک به بهینه ی عمومی در محدوده ی زمانی تعیین شده اکتفا می کنند.
در الگوریتم مکاشفه ای این تحقیق با انجام نمونه برداریهایی تصادفی کاوش در فضای پارامتری را آغاز می کنیم و استخراج جواب بهینه را از نقطه ای واقع در یک ناحیه ی امیدبخش وسیع شروع می کنیم ، سپس با اعمال تغییرات متوالی در مختصات و وسعت این ناحیه سعی می کنیم به یک جواب بهینه ی محلی همگرا می شویم . دلیل ما برای بکارگیری این روش در حل مساله ی بهینه سازی وزن هاOSPF ی خصوصیات این الگوریتم می باشد که با نیازهای مساله ما مطابقت کامل دارد. در زیر به اختصار به این خصوصیات اشاره می کنیم :
کارایی بالا: از آنجا که شرایط یک شبکه پی درپی در حال تغییر است به الگوریتم جستجویی نیاز داریم که سریع باشد تا بتواند قبل از بروز تغییرات زیادی در وضعیت شبکه بهترین وزندهی را متناسب با وضعیت فعلی یافته و روی شبکه اعمال کند.
مقیاس پذیری با ابعاد زیاد: از آنجا که ممکن است گراف شبکه ی OSPF صدها یال داشته باشد، الگوریتم بهینه سازی به کار رفته با ید روی دامنه وسیعی از توابع هدف با تعداد پارامترهای زیاد عملکرد خوبی داشته باشد.

مقاومت در برابر خطا: رفتار شبیه سازی شده ی مسیریابی شبکه همواره با کمی انحراف از رفتار واقعی همراه است یعنی همیشه تقریبی از تابع هزینه ی مسیریابی در دست است ، درنتیجه پاسخ نهایی الگوریتم بهینه سازی باید نسبت به خطای این محاسبات حساسیت اندکی داشته باشد.
در تحقیقی که برای آزمودن میزان کارایی ، مقیاس پذیری و عدم حساست به خطا الگوریتم جستجوی تصادفی RRS انجام گرفته است از این الگوریتم برای بهینه سازی تابع Rastrigin استفاده شده است و نتایج حاصل وجود همگی این خصوصیات را در الگوریتم مذکور نشان داده است [٣]،این تابع به شکل کلی زیر باشد :

که در آن X بردارn بعدی از اعداد و A عددی ثابت می باشد. این تابع بهین ای محلی بسیاری دارد اما تنها یک جواب بهینه ی عمومی در نقطه ی دارد و یافتن ین بهینه ی عمومی در بین تعداد زیادی بهینه ی محلی کار دشواری به نظر می رسد.
در شکل ١ یک نمونه ی دو بعدی از این تابع نشان داده شده است .

شکل ١. یک تابع Rastrigin دو بعدی
۲-۱- جستجوی تصادفی بازگشتی RRS
نمونه برداری تصادفی در یافتن نقاط خوب در گام های ابتدایی بسیار کارا م باشد. فرض کنید تابع هدف روی فضای پارامترD تعریف شده و داریم :

نسبت نقاطی از فضای پارامتری که مقدار تابع هدف در آن ها کمتر از yr می باشد را با تابع زیر نشان می دهیم :

اگر باشد، ناحیه ای با اندازه به صورت زیر قابل تعریف است که آن را ناحیه r -امیدبخش می نامیم :

فرض کنید پس از n نمونه برداری تصادفی یک توالی از نمونه ها به صورت در اختیارداریم ، از بین آن ها بهترین نمونه ای که تابع هدف را کمینه می کند نامیم . با فرض این که نمونه ها روی فضای پارامتری توزیع یکنواختی دارند احتمال این که در ناحیه r -امیدبخش باشد به صورت زیرخواهد بود:

زیرا احتمال این که هیچ کدام از این n نمونه ای در ناحیه r -امیدبخش نباشد است ، بنابراین داریم :

از این رابطه پیداست که برای هر احتمال ١>p با افزایش n،r به سمت صفر میل می کند و به سمت مجموعه ای محدود از نقاط بهینه ی عمومی میل خواهدکرد. از آنجا که با افزایش n کاهش r به صورت نمایی م باشد بنابراین نتیجه می گیریم نمونه برداری تصادفی با افزودن بر تعداد نمونه ها به بهینه ی عمومی همگرا می شود و سرعت همگرایی در گام های ابتدایی زیاد است .
در شکل ٢ نمودار تغییرات r برحسب n برای احتمال ٠.٩٩ رسم شده است . می بینیم که تنها با ۴۴ نمونه برداری به احتمال ٠.٩٩به نقطه ای در دست خواهیم یافت ، بدون آن که هیچ دانشی از تابع هدف داشته باشیم .

شکل ٢. نمودارکاهش نمایی r بر حسب تعداد نمونه برداریها
ازرابطه (١٣) تعداد نمونه برداری های لازم برای رسیدن به نقطه ای در ناحیه r -امیدبخش به دست می آید:

بنابراین الگوریتم ابتدا عدد نسبتا کوچک r و احتمال p را به دلخواه انتخاب می کند سپس ازرابطه ی (١۴) مقدار n، تعداد نمونه برداریهای لازم را محاسبه می نماید، سپس n نمونه برداری انجام می دهد و مقدار تابع هزینه در بهترین نمونه را به عنوان مقدار آستانه در نظر می گیرد. در نمونه برداریهای بعدی اولین نقطه ای که در قرار گیرد با احتمال p در قراردارد، زیرا
پس از یافتن این نقطه ۰ X، کاوش نقطه ای بهتر در همسایگی آن آغازمی شود. اگر چنین نقطه ای پس از n نمونه برداری تصادفی یافت نشد با افزودن به مقدار آستانه وسعت ناحیه ی امیدبخش کمی افزایش می یابد و مرحله ی کاوش برای رسیدن به نقطه ای بهتر واقع در ناحیه ی امیدبخش جدید تکرارمی شود.
این نکته اهمیت دارد که احتمال p درحدی باشدکه برای یافتن X0 نیازمند تعداد زیادی نمونه برداری نباشیم . همچنین مقدار r که مقدار و در نتیجه وسعت ناحیه را تعیین می کند نباید بزرگ باشد.
در این حالت همسایگی نقطه ی می تواند به این صورت تعریف شود که در آن D فضای پارامتری و بردارهای نقاط این فضا می باشند و در آن ها می باشد:

این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید
word قابل ویرایش - قیمت 10700 تومان در 14 صفحه
107,000 ریال – خرید و دانلود
سایر مقالات موجود در این موضوع
دیدگاه خود را مطرح فرمایید . وظیفه ماست که به سوالات شما پاسخ دهیم

پاسخ دیدگاه شما ایمیل خواهد شد