2-5-2 Random Early Detection (RED) ……………………………………………………………………………………..19
2-5-3 Weighted Random Early Detection (WRED) ………………………………………………………………19
2-6 انواع کلاسهای سرویس در شبکه های داده …………………………………………………………………………………………………20
2-7 سرویس های مجتمع ……………………………………………………………………………………………………………………………….21
2-8 RSVP…………………………………………………………………………………………………………………………………………………23
2-9 سرویس های تفکیک شده ……………………………………………………………………………………………………………………….24
2-10 نتیجه گیری …………………………………………………………………………………………………………………………………………25
فصل سوم:کنترل نرخ و مفهوم عدالت در شبکه های داده
3-1 مقدمه…………………………………………………………………………………………………………………………………………………….26
3-2 مفهوم کنترل نرخ و اهداف آن………………….. ……………………………………………………………………………………………..27
3-2-1 روشهای بر اساس پنجره ………………………………………………………………………………………………………………..27
3-2-2 روشهای بر اساس نرخ ……………………………………………………………………………………………………………………28
3-3 تقسیم بندی ترافیک های موجود در سطح شبکه ………………………………………………………………………………………….29
3-4 مفهوم عدالت در تخصیص نرخ در شبکه های داده ………………………………………………………………………………………31
3-4-1 مدل شبکه …………………………………………………………………………………………………………………………………..32
3-4-2 معیار عدالت حداکثر- حداقل………………………………………………………………………………………………………….33
3-4-3 معیار عدالت تناسبی ………………………………………………………………………………………………………………………34
3-4-4 معیار عدالت حداقل تأخیر بالقوه ………………………………………………………………………………………………………36
3-4-5 تخصیص پهنای باند وزن دهی شده ………………………………………………………………………………………………….36
3-4-6 معیار عدالت تناسبی????? ……………………………………………………………………………………………………………37
3-5 نتیجه گیری …………………………………………………………………………………………………………………………………………..38
فصل چهارم: بررسی روشهای تخصیص نرخ بهینه به کاربرهای سطح شبکه براساس دیدگاه جریان سیال
4-1 مقدمه…………………………………………………………………………………………………………………………………………………….39
4-2 طرح مسئله کنترل نرخ بصورت یک مسئله بهینه سازی عمومی………………………………………………………………………….42
4-2-1 الگوریتم گسترده و تکرری برای پاسخ………………………………………………………………………………………………45
4-3 کنترل نرخ در شبکه های کامپیوتری با استفاده ازمفهوم هزینه ………………………………………………………………………….46
4-3-1 الگوریتم Kelly برای حل مسئله شبکه…………………………………………………………………………………………….49
4-3-2 الگوریتم Kelly برای حل مسئله کاربر ……………………………………………………………………………………………50
4-3-3 بررسی پایداری سراسری الگوریتم ها ………………………………………………………………………………………………50
4-3-4 سرعت همگرائی ………………………………………………………………………………………………………………………….51
4-3-5 تأخیرهای زمانی …………………………………………………………………………………………………………………………..52
4-3-6 تطبیق کاربرها ……………………………………………………………………………………………………………………………..54
4-3-7 بهینه سازی همزمان مسیر و نرخ کاربرها ……………………………………………………………………………………………55

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

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

4-3-8 بررسی مسئله ورود و خروج کاربرها در سیستم ………………………………………………………………………………….57
4-4 نتیجه گیری…………………………………………………………………………………………………………………………………………….60
فصل پنجم : روشهائی برای حل مسائل بهینه سازی محدب مقید
5-1 مقدمه ……………………………………………………………………………………………………………………………………………………61
5-2 بهینه سازی محدب مقید ……………………………………………………………………………………………………………………………62
5-2-1 روش تصویر گرادیان …………………………………………………………………………………………………………………..63
5-2-2 الگوریتمهای تصویر گرادیان وزن دهی شده و نیوتن …………………………………………………………………………..65
5-2-3 بررسی همگرائی با استفاده از روش شیب ………………………………………………………………………………………….66
5-2-4 لم شیب ……………………………………………………………………………………………………………………………………..67
5-2-5 مفهوم سرعت همگرائی و مقایسه سرعت همگرائی الگوریتم ها …………………………………………………………….68
5-2-6 روش لاگرانژ ………………………………………………………………………………………………………………………………70
5-2-7 روش تابع جریمه ………………………………………………………………………………………………………………………….71
5-2-8 روش تابع سد ………………………………………………………………………………………………………………………………71
5-3 نتیجه گیری…………………………………………………………………………………………………………………………………………….72
فصل ششم : طراحی و پیشنهاد الگوریتمهای تخصیص نرخ بهینه بهبود یافته
6-1 مقدمه …………………………………………………………………………………………………………………………………………………..73

6-2 معیار عدالت تناسبی(?,?) ………………………………………………………………………………………………………………………74
6-3 الگوریتمهای پیشنهادی …………………………………………………………………………………………………………………………….76
6-3-1 الگوریتم I …………………………………………………………………………………………………………………………………82
6-3-2 الگوریتم II ……………………………………………………………………………………………………………………………….84
6-3-3 الگوریتم III ………………………………………………………………………………………………………………………………96
6-3-4 الگوریتم IV ……………………………………………………………………………………………………………………………100
6-4 پایداری الگوریتم های با عدالت تناسبی در حضور تأخیر زمانی …………………………………………………………………….102
6-5 نتیجه گیری…………………………………………………………………………………………………………………………………………..118
فصل هفتم : شبیه سازی کامپیوتری
7-1 مقدمه ………………………………………………………………………………………………………………………………………………….119
7-2 مقایسه الگوریتم های I الی IV با الگوریتمهای متعارف ……………………………………………………………………………….119
7-2-1 مثال اول …………………………………………………………………………………………………………………………………..120
7-2-2 مثال دوم …………………………………………………………………………………………………………………………………..129
7-2-3 مثال سوم ………………………………………………………………………………………………………………………………….140
7-2-4 مثال چهارم ……………………………………………………………………………………………………………………………….151
7-2-5 مثال پنجم (بررسی اثر متقابل گلوگاه ها)…………………………………………………………………………………………158
7-3 شبیه سازی ورود و خروج کاربرها …………………………………………………………………………………………………………..161
7-4 شبیه سازی معیارهای عدالت دیگر در الگوریتم فازی …………………………………………………………………………………..165
7-5 شبیه سازی واقعه گسسته………………………………………………………………………………………………………………………….166
7-5-1 بخش اول……………………………………………………………………………………………………………………………………168
7-5-2 بخش دوم……………………………………………………………………………………………………………………………………177
7-5-3 شبیه سازی الگوریتم سلسله مراتبی II در حضور ترافیک زمینه ……………………………………………………………..178
7-5-4 مقایسه الگوریتم فازی با Kelly………………………………………………………………………………………………………179
7-6 نتیجه گیری…………………………………………………………………………………………………………………………………………..179
فصل هشتم : نتیجه گیری و پیشنهادات
8-1 نتیجه گیری …………………………………………………………………………………………………………………………………………181
8-2 پیشنهادات …………………………………………………………………………………………………………………………………………..184
فهرست علائم اختصاری …………………………………………………………………………………………………………………………..186
مراجع ……………………………………………………………………………………………………………………………………………………..188
پیوستها
الف-ن) شکلهای تکمیلی مربوط به شبیه سازی کامپیوتری…………………………………………………….. ………………. CD ضمیمه
س) برخی برنامه های کامپیوتری مورد استفاده در شبیه سازی……………………………………………………………………. CD ضمیمه
چکیده:
هدف از انجام این رساله، ایجاد بهبود در نحوه عملکرد الگوریتم های تخصیص نرخ بهینه بر مبنای تابع سودمندی در شبکه های داده
می باشد. الگوریتم تخصیص نرخ بهینه بر مبنای تابع سودمندی در ابتدا توسط دکتر گلستانی مطرح گردید. سپس Kelly نشان داد که میتوان مسئله تخصیص نرخ بهینه را به دو زیر مسئله ساده تر تبدیل کرد که یکی توسط شبکه و دیگری توسط کاربرها حل میشود و نشان داد که مسئله شبکه در حقیقت، مسئله تخصیص نرخ با معیار عدالت تناسبی می باشد و دارای مزایای بسیاری از جمله شباهت با الگوریتم کنترل ازدحام در TCP/IP (روش AIMD ) می باشد و همچنین پایداری و همگرائی الگوریتم را بفرم ریاضی نشان داد. ولی در عین حال الگوریتم Kelly دارای برخی محدودیتها نیز می باشد که از آن جمله می توان به مشکل گسترش پذیری(Scalability) و سرعت همگرائی کم و سربارهای محاسباتی زیاد اشاره کرد. در این رساله، به معرفی دو الگوریتم سلسله مراتبی، یک الگوریتم فازی و یک الگوریتم ترکیبی فازی- سلسله مراتبی با هدف برطرف کردن نقائص فوق الذکر میپردازیم تا ضمن برقراری عدالت تناسبی (?,?) به روشهای تخصیص نرخ با سرعت های همگرائی بالاتر دست یابند. ضمناً بررسی ریاضی پایداری الگوریتمهای مطرح شده، بررسی رفتار الگوریتمهای سلسله مراتبی در حضور ترافیک زمینه با نرخ متغیر، و بررسی پدیده ورود و خروج کاربرها به سیستم از دیگر مواردی
می باشندکه در این رساله مورد بررسی قرار خواهند گرفت.
فصل اول
مقدمه
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 به شبکه های وسیعتر و ترجیح به استفاده از الگوریتم های ساده مقدماتی (با سرعت همگرائی کم) بدلیل حجم زیاد سربار محاسباتی ایجاد شده اشاره کرد.
در این رساله، با معرفی دو الگوریتم سلسله مراتبی، یک الگوریتم فازی و یک الگوریتم ترکیبی فازی- سلسله مراتبی با هدف برطرف کردن نقائص فوق الذکر و ضمن برقراری عدالت تناسبی (?,?) به روشهای تخصیص نرخ با سرعت های همگرائی بالاتر دست می یابیم و ضمناً به بررسی ریاضی پایداری الگوریتمهای مطرح شده می پردازیم.
الگوریتمهای سلسله مراتبی، بر اساس لینکهای گلوگاه6 موجود، شبکه را به دو سطح سلسله مراتب افراز می کنند. اینگونه الگوریتمها کاربرهای شبکه را بر اساس عبور دسته های کاربرها بطور مشترک از لینکهای گلوگاه به کاربرهای مجازی تفکیک می کنند. سپس عمل تخصیص نرخ به این کاربرهای مجازی بصورت مشترک و توسط گره های مرزی موجود در مرز میان دو سطح سلسله مراتب، انجام می پذیرد.

از جمله ویژگیهای الگوریتمهای سلسله مراتبی تخصیص نرخ مطرح شده در این رساله می توان به کاهش سربار محاسباتی و حجم عملیات مورد نیاز جهت تخصیص نرخ در سطح بالای سلسله مراتب اشاره کرد.
علاوه بر روشهای سلسله مراتبی تخصیص نرخ، با بکارگیری تکنیکهای فازی به افزایش سرعت همگرائی الگوریتمهای تخصیص نرخ متعارف پرداخته ایم. همچنین با بکارگیری روش ترکیبی سلسله مراتبی و فازی سعی کرده ایم که از ویژگیهای هردو روش سلسله مراتبی و فازی بهره ببریم.
بررسی رفتار الگوریتمهای سلسله مراتبی در حضور ترافیک زمینه با نرخ متغیر، و بررسی پدیده ورود و خروج کاربرها به سیستم از دیگر مواردی می باشندکه در این رساله مورد بررسی قرار خواهند گرفت.

1-3 ترتیب ارائه مطالب

در فصل دوم مفهوم کیفیت سرویس در شبکه های داده و روشهای مختلف زمانبندی مورد بررسی قرار خواهند گرفت. در فصل سوم به مسئله کنترل نرخ و روشهای دستیابی به آن در شبکه های داده
می پردازیم و معیار های مختلف برای برقراری عدالت در تخصیص نرخ به کاربرها در این فصل بررسی خواهند شد. در فصل چهارم ضمن مرور نتایج کارهای انجام شده قبلی، بیان شده است که مسئله تخصیص نرخ عادلانه و بهینه به کاربرهای شبکه را می توان به یک مسئله بهینه سازی عمومی مقید بر اساس محدودیت های مربوط به منابع شبکه تبدیل کرد. فصل پنجم به بررسی روشهای کلی برای حل مسائل بهینه سازی محدب مقید اختصاص یافته است که از این میان می توان به روشهای تصویر گرادیان1، تصویر جاکوبی2، لاگرانژ و … اشاره کرد[15]. در فصل ششم به ارائه و پیشنهاد چند الگوریتم تخصیص نرخ به کاربرهای سطح شبکه می پردازیم. این الگوریتم ها در نهایت به نقطه بهینه پاسخ همگرا می شوند. در این بخش، به بیان ریاضی مسئله پایداری الگوریتم های تخصیص نرخ خواهیم پرداخت.
همچنین، در فصل ششم مسئله ورود و خروج کاربرها به شبکه (با در نظر گرفتن توزیع های مشخص برای فرایند ورود و خروج) بررسی می شود.
در فصل هفتم با انجام شبیه سازی کامپیوتری بر روی چند توپولوژی دلخواه شبکه به بررسی نحوه عملکرد الگوریتم های مطرح شده در فصل پنجم و مقایسه نتایج حاصل با الگوریتمهای متعارف می پردازیم.
در خاتمه، در فصل هشتم ضمن مرور بر نتایج حاصله از این تحقیق به بیان راهکارهائی جهت ادامه آن خواهیم پرداخت.
فصل دوم
بررسی مفهوم کیفیت سرویس در شبکه های داده
2-1 مقدمه
بر اساس یک تعریف، مفهوم کیفیت سرویس در شبکه های کامپیوتری عبارتست از ” قابلیت کنترل مکانیسم های برخورد با ترافیک شبکه بقسمی که نیازمندی های سرویسها و کاربرهای مشخص، بر طبق سیاستهای شبکه تأمین گردد ” [45] .
نیازمندی های سرویس شامل پهنای باند مورد نیاز، تأخیر، تغییرات تأخیر و اتلاف1 قابل قبول سرویس می باشد. در یک شبکه با یک مجموعه از مکانیسم های QoS مفروض، یک موازنه بین Q وE وجود دارد. بعبارت دیگر، با افزایش هرکدام از این کمیتها، دیگری کاهش می یابد (شکل 2-1)).
شبکه ها ممکن است در نقاط مختلفی از این منحنی به کار گرفته شوند. مثلاً اغلب LAN های موجود در شبکه Microsoft قادر به ارائه کیفیت مناسب برای سرویس IP telephony هستند و بنابراین در نقطه P1 به کار گرفته شده اند.
برعکس، اغلب لینک های WAN بین المللی بعلت مسائل مربوط به هزینه از نظر کارآمدی مورد توجه قرار دارند و کیفیت مناسبی را برای سرویس IP telephony دارا نمی باشند و عملاً در نقطه P2 به کار گرفته شده اند [45] و باید توجه داشت که همانگونه که ذکر شد اغلب LAN هائی که با تمهیدات زیاد3
در نقطه P1 به کار گرفته شده اند از نظر کارآمدی وضعیتی نامناسب را دارا هستند. هدف کلی از ارائه مکانیسم های مختلف QoS افزایش کارآمدی مرتبط با یک شبکه خاص می باشد و هرچه مکانیسم کارآمدتر باشد عملکرد بهتری را برای شبکه بدست خواهد داد مطابق با شکل (2-2).

شکل 2-1: یک منحنی نوعی بیان کننده رابطه بین کیفیت و کارآمدی[45]

شکل2-2: تاثیر پیچیدگی مکانیسم QoS بر عملکرد شبکه[45]

2-2 مکانیسم های موجود در شبکه برای ایجاد QoS
بعضی از مکانیسم های بکار رفته برای برقراری QoS در شبکه ها به قرار زیر می باشند[45]:

* انواع مکانیسم های صف بندی1
* سرویس های مجتمع
* سیگنالینگ RSVP
* سرویس های تفکیک شده
* مدیریت پهنای باند زیر شبکه2 برای شبکه های 802
*
* QoS در لایه 2 بغیر از شبکه های 802 (…,ISSLOW1,ATM)

مکانیسم های صف بندی بکاررفته در شبکه ها به دو دسته عمومی کار مداوم2 و کار غیر مداوم3 تقسیم
می شوند.

2-3 روش های صف بندی با کار مداوم
در این نوع صف بندی تا زمانی که بسته ای برای ارسال وجود داشته باشد، پهنای باند تخصیص می یابد و یا بعبارت دیگر، پهنای باند، بلا استفاده نخواهد ماند.
در شکل(2-3)، ریل نشانگر ظرفیت موجود و هر واگن نشانگر یک بسته می باشد و همواره ظرفیت خط مورد استفاده قرار می گیرد. که دراین دسته می توان روش های صف بندی با اولویت مطلق4 و روش صف بندی عادلانه5 را نام برد. در روش اولویت مطلق به برخی ارتباط ها بطور مطلق و بدون شرط حق استفاده از منابع لینک را می دهند ولی در روش صف بندی عادلانه هر ارتباط بر حسب یک وزن خاص حق استفاده از منابع را دارد.
الگوریتم های صف بندی با کار مداوم از قبیل WFQ6، WRR7 ، FIFO8، GPS9 و … در روش مورد استفاده برای انتخاب صف مناسب با هم متفاوتند[36-42]. در ساده ترین نوع، از تقدم محض برای الگوریتم صف بندی استفاده می شود که در آن صف های با اولویت کمتر فقط وقتی سرویس دهی
می شوند که هیچ بسته ای در صف های با اولویت بالاتر موجود نباشد.
بر خلاف روش صف بندی FIFO و یا با اولویت مطلق که بصورتی ناعادلانه به تخصیص پهنای باند مابین جریان های عبوری می پردازد و در واقع در برهه های کوتاه زمانی ترافیکهائی که بیشتر ماهیت هجومی10 دارند بیشتر پهنای باند را به خود اختصاص می دهند تا ترافیکهای دارای الگوی ملایم، روش های صف بندی عادلانه دارای این قابلیت هستند که کرانهای مشخصی را از نظر تأخیر برای کلیه جریانهای عبوری تضمین کنند و در همه برهه های زمانی ظرفیت را بنحوی عادلانه مابین این جریانها به اشتراک بگذارند.
شکل2-3: شمائی از یک الگوریتم صف بندی با کار مداوم[45]
2-3-1 روش صف بندی FIFO

در این روش که به روش FCFS1 نیز موسوم است، بسته های ورودی به صف، به همان ترتیب ورود به صف، مورد سرویس دهی قرار می گیرند. این روش نیز از نظر پیاده سازی در سطح شبکه بسیار ساده است.
2-3-2 روش صف بندی با اولویت مطلق
در این روش، برای هر اولویت یک صف وجود دارد و تا زمانی که یک بسته در اولویت بالا وجود دارد بسته های موجود در اولویت پائین سرویس دهی نمی شوند. این روش نیز از نظر پیاده سازی بسیار ساده است و دارای پیچیدگی از O(1) می باشد. روش صف بندی با اولویت، روشی موثر برای برخورد با ترافیک های مهم می باشد.
اگر بسته های دریافت شده در صف با اولویت بالا دارای نرخی بیشتر یا مساوی با توان سرویس دهی رابط خروجی باشند، هیچگونه سرویس دهی به بسته های موجود در صف های با اولویت پائین صورت
نمی گیرد و این صف ها دچار فقر2 در سرویس دهی می شوند به همین منظور این روش سرویس دهی فقط در برخی موارد خاص یا برای سرویس های حیاتی و مهم در شبکه استفاده می شود.
یک کاربرد عمده این روش در ارسال اطلاعات کنترلی بین سوئیچهای شبکه می باشد. این روش
صف بندی میتواند به همراهی با روش های دیگر صف بندی مورد استفاده قرار گیرد. مثلاً
می توان از یک صف با اولویت بالا برای ارسال اطلاعات کنترلی شبکه استفاده کرد در حالی که چندین صف با اولویت پائین تر پهنای باند باقی مانده را بصورتی عادلانه مابین ترافیک خود تقسیم می کنند.
2-3-3 روش GPS
در حالت ایده آل، در این روش برای هر ارتباط یک صف جداگانه در نظر گرفته می شود سپس هر صف غیر خالی بترتیب بررسی شده و به مقداری بی نهایت کوچک سرویس دهی می شود. بنابراین در هر بازه زمانی حداقل یکبار به تمامی صف ها سرکشی شده و به آنها سرویس دهی می شود. ارتباط ها می توانند دارای وزن بوده و متناسب با این وزنشان سرویس دریافت کنند. سرویس دهنده از روی صف های خالی جهش می کند. این روش منجر به تقسیم عادلانه حداکثر-حداقل پهنای باند می شود.
فرض کنید در شکل(2-4)، سوئیچ دارای N ارتباط با وزنهای مساوی بوده که هر کدام با سرعتی معادل 1/N سرعت سرویس دهنده، داده برای بلوک زمان بندی1 ارسال می کنند. سرویس دهنده طبق قانون حداکثر-حداقل باید 1/N پهنای باند را به هر کدام تخصیص دهد. چون سرویس دهنده در هر بار سرویس به مقدار بی نهایت کوچک از هر ارتباط را سرویس می دهد به این هد ف نائل خواهد شد. حال اگر همه منابع بجز A بیش از سهم خود داده ارسال کنند و منبع A، با نرخی کمتر از سهم خود داده ارسال کند صف منبع A خالی خواهد شد. اگر این اتفاق افتاد، سرویس دهنده از روی صف خالی پرش کرده و به خاطر نحوه سرویس گردشی آن [38]، زمان ذخیره شده بین بقیه ارتباط ها بطور مساوی تقسیم خواهد شد.
اگر ارتباط B با نرخی بیش از حد سرویس 1/N ولی کمتر از میزان سرویسی که پس از خالی شدن صف A تحویل می گیرد، داده ارسال کند سرانجام صف آن نیز خالی خواهد شد. بنابراین بقیه ارتباط ها به جز B و A کمی بیشتر سرویس می گیرند که خود می تواند باعث خالی شدن صف های دیگر شود. بدین ترتیب ارتباط هائی که کمتر از سهمشان پهنای باند تقاضا می کنند به خواسته خود می رسند در حالی که بقیه ارتباط ها که تقاضائی بیش از سهم خود دارند پهنای باند مساوی دریافت می کنند. بنابراین طبق تعریف، GPS روشی برای رسیدن به تقسیم عادلانه حداکثر- حداقل است.
معمولاً عملکرد این روش بعنوان مرجع مقایسه برای دیگر روشها بکار می رود.
لازم به توضیح است که در معیار حداکثر-حداقل که سعی در حداکثر کردن حداقل سهم کاربر ناراضی دارد رعایت اصول زیر الزامی است:

* منابع به ترتیب میزان درخواستهای صعودی تخصیص می یابند.
* هیچ کاربری بیش از درخواست خود منبع در اختیارش قرار نمی گیرد.
* کاربرانی که به تقاضای خود نرسیده اند مقدار سهم مساوی از منبع دریافت می کنند.
* سهم کاربران ناراضی کمتر از سهم کاربران راضی نمی باشد.

اگر ارتباط ها وزن دار باشند، در هر دور سرویس GPS به هر ارتباط غیر خالی متناسب با وزنش سرویس داده می شود. گسترش بحث فوق نشان می دهد که GPS می تواند روشی برای دستیابی به تقسیم عادلانه وزن دار حداکثر-حداقل باشد.

شکل2-4: سرویس دهنده GPS

2-3-4 روش صف بندی Round Robin
ساده ترین مشابه سازی از GPS روش round-robin است که در آن به جای یک مقدار بی نهایت کوچک، یک بسته از هر ارتباط انباشته1 سرویس می گیرد.
در این روش بصورت دورانی از هر صف یک بسته برداشته می شود و این عمل بطور پیوسته تا اتمام
بسته ها تداوم می یابد. پیچیدگی این الگوریتم از مرتبه O(1) می باشد و در صورتی که مطابق شکل(2-5) بسته های موجود در صف ها دارای طول مساوی باشند. تأخیر حداکثر یک صف عبارت است از:

(2-2)

که در آن N تعداد صف ها یا جریان ها و P بزرگترین اندازه بسته مورد سرویس دهی و r نرخ بیتی است که سرویس دهنده بر اساس آن سرویس دهی می کند.
یکی از معایب روش Round robin این است که در شبکه های Packet Switched که طول بسته ها متفاوت است سرویس دهی به بسته ها بطور عادلانه صورت نمی گیرد و بیشتر پهنای باند صرف سرویس دهی به صف های با بسته های با طول بزرگتر می شود.
شکل2-5: برقراری عدالت بین بسته های ورودی در حالتی که بسته ها طول مساوی دارند[45]
2-3-5 روش Bitwise Round Robin
اگر بر خلاف روش Round robin، واحد تخلیه شده از صف به جای بسته، بیت در نظر گرفته شود، به هر جریان مستقل از اندازه بسته ها 1/N ظرفیت اختصاص پیدا می کند و این همان ایده روش Bitwise Round Robin می باشد.
اگر چه سرویس دهی به یک بیت از هر ارتباط در عمل ناممکن بنظر می رسد ولی Keshav، Demres و Shenker در [37] تقریبی عملی برای پیاده سازی این الگوریتم ارائه کرده اندکه اساس روش صف بندی عادلانه ارائه شده در قسمت بعد می باشد.

2-3-6 روش عملی صف بندی عادلانه Bitwise Round Robin
در این روش، به هر بسته یک “زمان اتمام” نسبت داده می شود که در واقع زمانی است که بسته بطور کامل به روش Bitwise Round Robin بطور تئوری سرویس دهی می شود سپس بسته ها بر اساس زمان اتمام خود در یک لیست مرتب می گردند و بر اساس ترتیب، از لیست سرویس دهی می شوند
)شکل(2-6)(.
شکل2-6: سرویس دهی به بسته های با طول نامساوی [45]

بعلت نیاز به لیست برای مرتب کردن بسته ها پیچیدگی محاسباتی این روش از مرتبه O(log(N))
می باشد و بنابراین این الگوریتم را می توان در سوئیچ های سریع مورد استفاده قرار داد.

2-3-7 روش WRR

در این روش نیز بصورت دورانی از هر صف یک بسته برداشته می شود و این عمل بطور پیوسته تا اتمام بسته ها تداوم می یابد. همانگونه که قبلاً بیان شد، ساده ترین مشابه سازی از GPS روش round-robin است که در آن به جای یک مقدار بی نهایت کوچک، یک بسته از هر ارتباط انباشته سرویس می گیرد.

اگر ارتباط ها دارای وزن باشند از روش WRR که متناسب با وزن ارتباط به آن سرویس می دهد استفاده می شود. دو روش RR و WRR زمانی GPS را خوب تقریب می زنند که طول بسته ها ثابت باشد. اگر طول بسته ها ثابت نباشد سرویس دهنده WRR وزن هر ارتباط را به متوسط طول بسته های آن ارتباط تقسیم می کند تا وزنهای نرمالیزه شده بدست آیند.


پاسخ دهید