وبلاگ

 بطور کلی، کیفیت سرویس1 عبارتست از قابلیتی که شبکه در تمیز گذاری بین انواع سرویسها و کلاسهای ترافیکی دارا می باشد بنحوی که کاربرانی که در یک کلاس ترافیکی قرار گرفته اند، بسته به نوع نیاز خود، عملکرد متفاوتی از شبکه را نسبت به انواع دیگر مشاهده کنند. از جمله راه های حمایت از کیفیت سرویس می توان به انواع روش های کنترل نرخ و کنترل ازدحام2 اشاره نمود.
روش های کنترل نرخ و کنترل ازدحام در شبکه های کامپیوتری به منظور کنترل ترافیک در شبکه ها و تقسیم پهنای باند با در نظر گرفتن معیار عدالت3 مفروض به کار می روند.
كنترل نرخ عبارتست از مجموعه ای از روش های مورد استفاده شبكه برای كنترل نرخ ورودی به شبكه در حالی که كنترل ازدحام عبارتست از اعمال پاره ای از كنترل ها بر روی ورودی هائی كه باعث پر شدن بافرهای شبكه شده اند.
در یک تقسیم بندی عمومی، كنترل ازدحام در شبكه های مخابراتی داده به دو روش صورت می گیرد. روش های براساس پنجره كه در آنها تعداد بسته های موجود در شبكه با كنترل هوشمندانه یک پنجره به نام پنجره ازدحام4، در حدی معین تنظیم می گردد [6,5,4,3,2,1] و روش های بر اساس نرخ كه در آنها به
 
ترافیک موجود در شبكه بصورت جریان مایع نگاه كرده می شود و با الگوریتم های مشخص سعی در تخصیص نرخ به كاربرهای شبكه می گردد بنحوی كه عدالت در تخصیص نرخ به كاربرها رعایت گردد[11,10,9,8,7].
معیارهای متعددی برای پیاده سازی این عدالت معرفی شده اند كه از شاخص ترین آنها می توان معیارهای عدالت حداکثر- حداقل1، تناسبی2 و حداقل تأخیر بالقوه3 را نام برد[14,13,12].
Mo و Walrand در [13] به بررسی معیار عدالت (W,a) پرداخته اند و نشان داده اند که تمامی معیارهای عدالت مذکور را می توان بعنوان حالتهای خاص از معیار عدالت عمومی تر(W,a)  بدست آورد.
با تحقیقاتی كه در زمینه كنترل ازدحام و الگوریتم های تخصیص نرخ صورت گرفته است این نتیجه حاصل شده است كه هرگونه الگوریتمی كه به منظور كنترل ازدحام یا تخصیص نرخ بكار می رود باید در حد امكان، بصورت توزیع شده در سطح شبكه قابل پیاده سازی باشد زیرا در غیر اینصورت اگر الگوریتم بصورت متمركز پیاده سازی گردد، با بزرگ شدن ابعاد شبكه، بار محاسباتی قابل توجهی به پردازشگر مركزی اعمال می گردد و بعلاوه در صورت بروز نقص در این پردازشگر، رفتار كل سیستم دچار اختلال و آشفتگی می گردد در حالی كه در یک الگوریتم توزیع شده، مسئولیت تخصیص نرخ و كنترل ازدحام بر عهدة تمامی گره های شبكه و كاربرهای انتهائی قرار می گیرد و ایجاد خطا و یا نقص در جزئی از این سیستم توزیع شده، تأثیر زیادی بر رفتار كل الگوریتم نخواهد داشت. بهمین دلیل محققینی از جمله 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] از زمینه های تحقیقاتی مهم كنونی به شمار می روند و محققین بسیاری در سرتاسر جهان، مشغول به تحقیق در این زمینه می باشند.
2-1- تبیین موضوع
هدف از انجام این رساله، پیشنهاد و بررسی الگوریتم های تخصیص نرخ بهینه با عملکرد بهبود یافته بر مبنای تابع سودمندی3 در شبکه های داده می باشد.
یک الگوریتم تخصیص نرخ بهینه بر مبنای تابع سودمندی در ابتدا توسط دکتر گلستانی مطرح گردیده است سپس Kelly  نشان داده است که میتوان مسئله تخصیص نرخ بهینه  را به دو زیر مسئله تبدیل کرد که یکی توسط شبکه و دیگری توسط کاربرها حل میشود و نشان داده است که مسئله شبکه در حقیقت، مسئله تخصیص نرخ با معیار عدالت تناسبی می باشد و دارای مزایای بسیاری از جمله شباهت با الگوریتم کنترل ازدحام در TCP/IP (روش AIMD4 ) می باشد و از مبنای ریاضی قوی جهت اثبات پایداری و همگرائی الگوریتم، بهره مند است ولی در عین حال، دارای برخی نقاط کاستی نیز می باشد که از آن جمله می توان به عدم سهولت گسترش پذیری5 الگوریتم Kelly به شبکه های وسیعتر و ترجیح به استفاده از الگوریتم های ساده مقدماتی (با سرعت همگرائی کم) بدلیل حجم زیاد سربار محاسباتی ایجاد شده اشاره کرد.
در این رساله، با معرفی دو الگوریتم سلسله مراتبی، یک الگوریتم فازی و یک الگوریتم ترکیبی فازی- سلسله مراتبی با هدف برطرف کردن نقائص فوق الذکر و ضمن برقراری عدالت تناسبی (W,a) به روش های تخصیص نرخ با سرعت های همگرائی بالاتر دست می یابیم و ضمناً به بررسی ریاضی پایداری الگوریتمهای مطرح شده می پردازیم.
الگوریتمهای سلسله مراتبی، بر اساس لینکهای گلوگاه6 موجود، شبکه را به دو سطح سلسله مراتب افراز می کنند. اینگونه الگوریتمها کاربرهای شبکه را بر اساس عبور دسته های کاربرها بطور مشترک از لینکهای گلوگاه به کاربرهای مجازی تفکیک می کنند. سپس عمل تخصیص نرخ به این کاربرهای مجازی بصورت مشترک و توسط گره های مرزی موجود در مرز میان دو سطح سلسله مراتب، انجام می پذیرد.
از جمله ویژگیهای الگوریتمهای سلسله مراتبی تخصیص نرخ مطرح شده در این رساله می توان به کاهش سربار محاسباتی و حجم عملیات مورد نیاز جهت تخصیص نرخ در سطح بالای سلسله مراتب اشاره کرد.
علاوه بر روش های سلسله مراتبی تخصیص نرخ، با بکارگیری تکنیکهای فازی به افزایش سرعت همگرائی الگوریتمهای تخصیص نرخ متعارف پرداخته ایم. همچنین با بکارگیری روش ترکیبی سلسله مراتبی و فازی سعی کرده ایم که از ویژگیهای هردو روش سلسله مراتبی و فازی بهره ببریم.
بررسی رفتار الگوریتمهای سلسله مراتبی در حضور ترافیک زمینه با نرخ متغیر، و بررسی پدیدة ورود و خروج کاربرها به سیستم از دیگر مواردی می باشندکه در این رساله مورد بررسی قرار خواهند گرفت.
3-1- ترتیب ارائه مطالب
در فصل دوم مفهوم كیفیت سرویس در شبكه های داده و روش های مختلف زمانبندی مورد بررسی قرار خواهند گرفت. در فصل سوم به مسئله كنترل نرخ و روش های دستیابی به آن در شبكه های داده
می پردازیم و معیار های مختلف برای برقراری عدالت در تخصیص نرخ به كاربرها در این فصل بررسی خواهند شد. در فصل چهارم ضمن مرور نتایج کارهای انجام شده قبلی، بیان شده است که مسئله تخصیص نرخ عادلانه و بهینه به کاربرهای شبکه را می توان به یک مسئله بهینه سازی عمومی مقید بر اساس محدودیت های مربوط به منابع شبکه تبدیل کرد. فصل پنجم به بررسی روش های كلی برای حل مسائل بهینه سازی محدب مقید اختصاص یافته است که از این میان می توان به روش های تصویر گرادیان1، تصویر جاکوبی2، لاگرانژ و … اشاره کرد[15]. در فصل ششم به ارائه و پیشنهاد چند الگوریتم تخصیص نرخ به کاربرهای سطح شبکه می پردازیم. این الگوریتم ها در نهایت به نقطه بهینه پاسخ همگرا می شوند. در این بخش، به بیان ریاضی مسئله پایداری الگوریتم های تخصیص نرخ خواهیم پرداخت.
همچنین، در فصل ششم مسئله ورود و خروج کاربرها به شبکه (با در نظر گرفتن توزیع های مشخص برای فرایند ورود و خروج) بررسی می شود.
 در فصل هفتم با انجام شبیه سازی كامپیوتری بر روی چند توپولوژی دلخواه شبكه به بررسی نحوة عملكرد الگوریتم های مطرح شده در فصل پنجم و مقایسة نتایج حاصل با الگوریتمهای متعارف می پردازیم.
در خاتمه، در فصل هشتم ضمن مرور بر نتایج حاصله از این تحقیق به بیان راهكارهائی جهت ادامة آن خواهیم پرداخت.