دانلود رساله دکترا: طراحی الگوریتم های تخصیص نرخ بهینه بر مبنای تابع سودمندی در شبکه های داده
نوشته شده توسط : admin

دانشگاه صنعتی اصفهان

دانشکده برق و کامپیوتر

رساله دکترای مهندسی برق

عنوان:

طراحی الگوریتم های تخصیص نرخ بهینه بر مبنای تابع سودمندی در شبکه های داده

اساتید راهنما:

دکتر حسین سعیدی

دکتر فرید شیخ الاسلام

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

فهرست مطالب:

فهرست مطالب………………………………………………………………………………………….. هشت

چکیده……………………………………………………………………………………………………1

فصل اول : مقدمه

1-1 مقدمه ………………………………………………………………………………………………….2

1-3 تبیین موضوع………………………………………………………………………………………….5

1-2 ترتیب ارائه مطالب…………………………………………………………………………………6

فصل دوم : بررسی مفهوم کیفیت سرویس در شبکه های داده

2-1 مقدمه……………………………………………………………………………………………..7

2-2 مکانیسم های موجود در شبکه برای ایجاد QoS …………………………………………

2-3 روش های صف بندی با کار مداوم………………………………………………………………9

2-3-1 روش صف بندی FIFO…………………………………………………………………………..

2-3-2 روش صف بندی با اولویت مطلق………………………………………………………10

2-3-3 روش GPS……………………………………………………………………………………….

2-3-4 روش صف بندی Round Robin ………………………………………………………..

2-3-5 روش Bitwise Round Robin ……………………………………………………………

2-3-6 روش عملی صف بندی عادلانه Bitwise Round Robin …………………………….

2-3-7 روش WRR …………………………………………………………………………………

2-3-8 روش Deficit Round Robin (DRR) ………………………………………………

2-3-9 روش بهبود یافته DRR (DRR+) …………………………………………………….

2-3-10 روش صف بندی عادلانه وزن دهی شده (WFQ) ……………………………15

2-3-11 روش WF2Q ………………………………………………………………………….

2-3-12 روش های Delay-EDD و Jitter-EDD ……………………………………………

2-4 روش های صف بندی با کار غیر مداوم ……………………………………………17

2-4-1 روش Leaky Bucket ……………………………………………………………

2-4-2 روش Token Bucket ……………………………………………………………

2-5 روشهای استفاده شده برای حذف کردن بسته ها ………………………………..18

2-5-1 Tail Dropping ………………………………………………………………………

2-5-2 Random Early Detection (RED) ……………………………………………

2-5-3 Weighted Random Early Detection (WRED) ………………………….

2-6 انواع کلاسهای سرویس در شبکه های داده ……………………………………..20

2-7 سرویس های مجتمع ……………………………………………………………………21

2-8 RSVP……………………………………………………………………………………..

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 معیار عدالت تناسبی(W,a) ……………………………………………..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 معیار عدالت تناسبی(W,a) …………………………………………………..74

6-3  الگوریتمهای پیشنهادی ………………………………………………………….76

6-3-1  الگوریتم  I …………………………………………………………………..

6-3-2  الگوریتم II  …………………………………………………………………

6-3-3 الگوریتم III  ……………………………………………………………….

6-3-4  الگوریتم IV  ……………………………………………………………….

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……………………………………………

7-6 نتیجه گیری…………………………………………………………………….179

فصل هشتم : نتیجه گیری و پیشنهادات

8-1  نتیجه گیری …………………………………………………………………181

8-2  پیشنهادات …………………………………………………………………..184

فهرست علائم اختصاری …………………………………………………….186

مراجع ……………………………………………………………………………..188

چکیده:

هدف از انجام این رساله، ایجاد بهبود در نحوه عملکرد الگوریتم های تخصیص نرخ بهینه بر مبنای تابع سودمندی در شبکه های داده
می باشد. الگوریتم تخصیص نرخ بهینه بر مبنای تابع سودمندی در ابتدا توسط دکتر گلستانی مطرح گردید. سپس Kelly  نشان داد که میتوان مسئله تخصیص نرخ بهینه  را به دو زیر مسئله ساده تر تبدیل کرد که یکی توسط شبکه و دیگری توسط کاربرها حل میشود و نشان داد که مسئله شبکه در حقیقت، مسئله تخصیص نرخ با معیار عدالت تناسبی می باشد و دارای مزایای بسیاری از جمله شباهت با الگوریتم کنترل ازدحام در TCP/IP (روش AIMD ) می باشد و همچنین پایداری و همگرائی الگوریتم را بفرم ریاضی نشان داد. ولی در عین حال الگوریتم Kelly دارای برخی محدودیتها نیز می باشد که از آن جمله می توان به مشکل گسترش پذیری(Scalability)  و سرعت همگرائی کم و سربارهای محاسباتی زیاد اشاره کرد. در این رساله، به معرفی دو الگوریتم سلسله مراتبی، یک الگوریتم فازی و یک الگوریتم ترکیبی فازی- سلسله مراتبی با هدف برطرف کردن نقائص فوق الذکر میپردازیم تا ضمن برقراری عدالت تناسبی (W,a) به روشهای تخصیص نرخ با سرعت های همگرائی بالاتر دست یابند. ضمناً  بررسی ریاضی پایداری الگوریتمهای مطرح شده،  بررسی رفتار الگوریتمهای سلسله مراتبی در حضور ترافیک زمینه با نرخ متغیر، و بررسی پدیده ورود و خروج کاربرها به سیستم از دیگر مواردی
می باشندکه در این رساله مورد بررسی قرار خواهند گرفت.

فصل اول: مقدمه

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] به بررسی معیار عدالت (W,a) پرداخته اند و نشان داده اند که تمامی معیارهای عدالت مذکور را می توان بعنوان حالتهای خاص از معیار عدالت عمومی تر(W,a)  بدست آورد.

با تحقیقاتی که در زمینه کنترل ازدحام و الگوریتم های تخصیص نرخ صورت گرفته است این نتیجه حاصل شده است که هرگونه الگوریتمی که بمنظور کنترل ازدحام یا تخصیص نرخ بکار می رود باید در حد امکان، بصورت توزیع شده در سطح شبکه قابل پیاده سازی باشد زیرا در غیر اینصورت اگر الگوریتم بصورت متمرکز پیاده سازی گردد، با بزرگ شدن ابعاد شبکه، بار محاسباتی قابل توجهی به پردازشگر مرکزی اعمال می گردد و بعلاوه در صورت بروز نقص در این پردازشگر، رفتار کل سیستم دچار اختلال و آشفتگی می گردد در حالی که در یک الگوریتم توزیع شده، مسئولیت تخصیص نرخ و کنترل ازدحام بر عهده تمامی گره های شبکه و کاربرهای انتهائی قرار می گیرد و ایجاد خطا و یا نقص در جزئی از این سیستم توزیع شده، تأثیر زیادی بر رفتار کل الگوریتم نخواهد داشت. بهمین دلیل محققینی از جمله Bertsekas [15] و Gallager [16] سعی در سوق دادن الگوریتم های تخصیص نرخ به سمت الگوریتم های توزیع شده و گسترده در سطح شبکه نموده اند.

ایده اولیه پیاده سازی مسئله کنترل نرخ بصورت یک مسئله بهینه سازی عمومی توسط S.J.Golestani  مطرح گردیده است [17] و پس از او محققین بسیاری سعی در توسعه روشهای موجود برای دسترسی کاربرهای موجود در سطح شبکه به نرخ های بهینه و با روشهای توزیع شده نموده اند.

برای دانلود پایان نامه اینجا را کلیک کنید.





لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       
:: بازدید از این مطلب : 424
|
امتیاز مطلب : 0
|
تعداد امتیازدهندگان : 0
|
مجموع امتیاز : 0
تاریخ انتشار : یک شنبه 3 مرداد 1395 | نظرات ()
مطالب مرتبط با این پست
لیست
می توانید دیدگاه خود را بنویسید


نام
آدرس ایمیل
وب سایت/بلاگ
:) :( ;) :D
;)) :X :? :P
:* =(( :O };-
:B /:) =DD :S
-) :-(( :-| :-))
نظر خصوصی

 کد را وارد نمایید:

آپلود عکس دلخواه: