شندکه در این رساله مورد بررسی قرار خواهند گرفت.
فصل اول
مقدمه
1-1 مقدمه

بطور کلی، کیفیت سرویس1 عبارتست از قابلیتی که شبکه در تمیز گذاری بین انواع سرویسها و کلاسهای ترافیکی دارا می باشد بنحوی که کاربرانی که در یک کلاس ترافیکی قرار گرفته اند، بسته به نوع نیاز خود، عملکرد متفاوتی از شبکه را نسبت به انواع دیگر مشاهده کنند. از جمله راههای حمایت از کیفیت سرویس می توان به انواع روشهای کنترل نرخ و کنترل ازدحام2 اشاره نمود.
روشهای کنترل نرخ و کنترل ازدحام در شبکه های کامپیوتری بمنظور کنترل ترافیک در شبکه ها و تقسیم پهنای باند با در نظر گرفتن معیار عدالت3 مفروض به کار می روند.
کنترل نرخ عبارتست از مجموعه ای از روش های مورد استفاده شبکه برای کنترل نرخ ورودی به شبکه در حالی که کنترل ازدحام عبارتست از اعمال پاره ای از کنترل ها بر روی ورودی هائی که باعث پر شدن بافرهای شبکه شده اند.
در یک تقسیم بندی عمومی، کنترل ازدحام در شبکه های مخابراتی داده به دو روش صورت می گیرد. روشهای براساس پنجره که در آنها تعداد بسته های موجود در شبکه با کنترل هوشمندانه یک پنجره به نام پنجره ازدحام4، در حدی معین تنظیم می گردد [6,5,4,3,2,1] و روشهای بر اساس نرخ که در آنها به
ترافیک موجود در شبکه بصورت جریان مایع نگاه کرده می شود و با الگوریتم های مشخص سعی در تخصیص نرخ به کاربرهای شبکه می گردد بنحوی که عدالت در تخصیص نرخ به کاربرها رعایت گردد[11,10,9,8,7].
معیارهای متعددی برای پیاده سازی این عدالت معرفی شده اند که از شاخص ترین آنها می توان معیارهای عدالت حداکثر- حداقل1، تناسبی2 و حداقل تأخیر بالقوه3 را نام برد[14,13,12].
Mo و Walrand در [13] به بررسی معیار عدالت (?,?) پرداخته اند و نشان داده اند که تمامی معیارهای عدالت مذکور را می توان بعنوان حالتهای خاص از معیار عدالت عمومی تر(?,?) بدست آورد.
با تحقیقاتی که در زمینه کنترل ازدحام و الگوریتم های تخصیص نرخ صورت گرفته است این نتیجه حاصل شده است که هرگونه الگوریتمی که بمنظور کنترل ازدحام یا تخصیص نرخ بکار می رود باید در حد امکان، بصورت توزیع شده در سطح شبکه قابل پیاده سازی باشد زیرا در غیر اینصورت اگر الگوریتم بصورت متمرکز پیاده سازی گردد، با بزرگ شدن ابعاد شبکه، بار محاسباتی قابل توجهی به پردازشگر مرکزی اعمال می گردد و بعلاوه در صورت بروز نقص در این پردازشگر، رفتار کل سیستم دچار اختلال و آشفتگی می گردد در حالی که در یک الگوریتم توزیع شده، مسئولیت تخصیص نرخ و کنترل ازدحام بر عهده تمامی گره های شبکه و کاربرهای انتهائی قرار می گیرد و ایجاد خطا و یا نقص در جزئی از این سیستم توزیع شده، تأثیر زیادی بر رفتار کل الگوریتم نخواهد داشت. بهمین دلیل محققینی از جمله Bertsekas [15] و Gallager [16] سعی در سوق دادن الگوریتم های تخصیص نرخ به سمت الگوریتم های توزیع شده و گسترده در سطح شبکه نموده اند.
ایده اولیه پیاده سازی مسئله کنترل نرخ بصورت یک مسئله بهینه سازی عمومی توسط S.J.Golestani مطرح گردیده است [17] و پس از او محققین بسیاری سعی در توسعه روشهای موجود برای دسترسی کاربرهای موجود در سطح شبکه به نرخ های بهینه و با روشهای توزیع شده نموده اند.
عمده کار این محققین را می توان بطور کلی به دو دسته عمده تقسیم بندی نمود. در دسته اول، محققینی مانند S. Low در [18,19] سعی نموده اند تا با استفاده از تئوری دوگانی4[15]، مسئله بهینه سازی را به یک مسئله گسترده در سطح شبکه مبدل کنند که در آن کاربرهای انتهائی و لینک های شبکه با تبادل پاره ای اطلاعات به یکدیگر قادر به حل مسئله بهینه سازی عمومی باشند و حتی این محققین در [18] به کمک روشهای ریاضی سعی در اثبات پایداری الگوریتم های توزیع شده خود نموده اند و در عمل نیز نحوه پیاده سازی اینگونه از الگوریتم ها در شبکه ATM 5 [21,20] و برای سرویس ABR موجود در آن با استفاده از امکاناتی که این سرویس در اختیار قرار می دهد مورد بررسی و آنالیز قرار گرفته است.

محققینی که در دسته دوم تقسیم بندی فوق قرار دارند سعی می کنند تا با استفاده از روشهای مبتنی بر تابع جریمه [15] به حل مسئله تخصیص بهینه نرخ با تئوری بهینه سازی عمومی بپردازند که از این جمله
می توان به تحقیقات صورت گرفته در [24,23,22,10,8,7] اشاره نمود.
البته لازم به توضیح است، محققینی نیز وجود دارند که با استفاده از روشهائی متفاوت با دو روش کلی فوق، سعی در حل مسئله بهینه سازی عمومی تخصیص نرخ نموده اند. بعنوان مثال Ba?ar et al. T. در [25] و R. Srikant et al. در [8] سعی کرده اند تا با کمک تئوری بازی1 مسئله بهینه سازی تخصیص نرخ را مورد تجزیه و تحلیل قرار دهند.
از مهمترین روشهای دسته دوم می توان به نتایج تحقیقات در [7] اشاره کرد. Kelly et al. در [7] سعی نموده اند علاوه بر پیاده سازی یک الگوریتم گسترده در سطح شبکه به معیار عدالت تناسبی دست پیدا کنند. از جمله مهمترین ویژگی های این معیار، نزدیکی آن با روش معروف کنترل ازدحام در اینترنت که توسط Jacobson et al. در [26] ارائه گردیده است، می باشد. از دیگر ویژگی های برجسته این الگوریتم، بررسی و اثبات پایداری آن با انتخاب توابع لیاپانوف مناسب می باشد.
از آنجائیکه تأخیر زمانی در الگوریتم Kelly کمتر مورد توجه واقع گردیده است، R.Johari و D.Tan تحقیقات دامنه داری را در [11] برای اثبات پایداری الگوریتم Kelly در حضور تأخیر و تحت شرایطی مشخص انجام داده اند و به نتایج قابل توجهی دست یافته اند و در نهایت، پایداری الگوریتم برای یک توپولوژی عمومی شبکه و تأخیرهای دلخواه ولی محدود توسط L. Massoulié در [27] و S.Deb و R.Srikant در[28] ارائه شده است.
مسئله ورود و خروج کاربرها در الگوریتم Kelly ، در [10] مورد بررسی قرارگرفته است.
یکی از موثرترین روشهای اعمال شده جهت پرهیز از بروز ازدحام و یا کنترل آن، استفاده از متدهای هزینه گذاری2 بر لینکهای شبکه به ازاء ترافیک عبور کننده از آنها می باشد [31,30,29] که در این روشها هر لینک به ازاء ترافیک تجمعی که از آن عبور می کند، هزینه ای را بر کاربرهای عبوری اعمال می کند و این هزینه با افزایش ترافیک تجمعی عبوری افزایش می یابد و بعنوان مثال در [7] از اینگونه روشهای هزینه گذاری بمنظور دستیابی کاربرهای الاستیک3 [32] موجود در شبکه به نرخ های عادلانه و بهینه استفاده شده است. اخیراً با توجه به رشد روز افزون برنامه های کاربردی موجود در اینترنت و نیاز به سرویس هائی که دارای کران های مشخص برای تأخیر (و یا تغییرات تأخیر4) می باشند توجه خاصی به اعمال روشهای مبتنی بر الگوریتم های بهینه سازی و هزینه گذاری بر ترافیک های بلادرنگ5 معطوف شده است و از آنجا که
یکی از بهترین روشهای دستیابی به کیفیت سرویس در اینترنت کنونی، استفاده از سرویسهای تفکیک شده1 [33] می باشد، اعمال روشهای هزینه گذاری بر سرویس های تفکیک شده[34] و هزینه گذاری براساس اولویت و هزینه گذاری بر ترافیکهای بلادرنگ با استفاده از مفهوم پهنای باند موثر2 [35] از
زمینه های تحقیقاتی مهم کنونی به شمار می روند و محققین بسیاری در سرتاسر جهان، مشغول به تحقیق در این زمینه می باشند.
1-2 تبیین موضوع
هدف از انجام این رساله، پیشنهاد و بررسی الگوریتم های تخصیص نرخ بهینه با عملکرد بهبود یافته بر مبنای تابع سودمندی3 در شبکه های داده می باشد.
یک الگوریتم تخصیص نرخ بهینه بر مبنای تابع سودمندی در ابتدا توسط دکتر گلستانی مطرح گردیده است سپس Kelly نشان داده است که میتوان مسئله تخصیص نرخ بهینه را به دو زیر مسئله تبدیل کرد که یکی توسط شبکه و دیگری توسط کاربرها حل میشود و نشان داده است که مسئله شبکه در حقیقت، مسئله تخصیص نرخ با معیار عدالت تناسبی می باشد و دارای مزایای بسیاری از جمله شباهت با الگوریتم کنترل ازدحام در TCP/IP (روش AIMD4 ) می باشد و از مبنای ریاضی قوی جهت اثبات پایداری و همگرائی الگوریتم، بهره مند است ولی در عین حال، دارای برخی نقاط کاستی نیز می باشد که از آن جمله می توان به عدم سهولت گسترش پذیری5 الگوریتم Kelly به شبکه های وسیعتر و ترجیح به استفاده از الگوریتم های ساده مقدماتی (با سرعت همگرائی کم) بدلیل حجم زیاد سربار محاسباتی ایجاد شده اشاره کرد.
در این رساله، با معرفی دو الگوریتم سلسله مراتبی، یک الگوریتم فازی و یک الگوریتم ترکیبی فازی- سلسله مراتبی با هدف برطر