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

19,000تومان

توضیحات

مشاهده و دانلود چند صفحه اول :

دانلود متن كامل در

download-thesis.com

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

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

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

 

 

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

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

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

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

 

 

دانلود متن كامل در

download-thesis.com

فهرست مطالب

چکيده…..

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

1-1 مقدمه

1-3 تبيين موضوع.

1-2 ترتيب ارائه مطالب.

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

2-1 مقدمه

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

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

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

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

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

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

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

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

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

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

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

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

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

2-3-12 روش هاي Delay-EDD و Jitter-EDD …….16

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

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

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

2-5 روشهاي استفاده شده براي حذف كردن بسته ها ………18

2-5-1 Tail Dropping ………..19

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 معيار عدالت تناسبي(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 …………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 ضميمه

دانلود متن كامل در

download-thesis.com

دانلود متن كامل در

download-thesis.com

 

 

 

چکيده:

هدف از انجام اين رساله، ايجاد بهبود در نحوة عملکرد الگوريتم های تخصيص نرخ بهينه بر مبنای تابع سودمندی در شبکه های داده می باشد. الگوريتم تخصيص نرخ بهينه بر مبنای تابع سودمندی در ابتدا توسط دکتر گلستانی مطرح گرديد. سپس 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] و پس از او محققين بسياري سعي در توسعة روشهاي موجود براي دسترسي كاربرهاي موجود در سطح شبكه به نرخ هاي بهينه و با روشهاي توزيع شده نموده اند.

عمده كار اين محققين را مي توان بطور كلي به دو دسته عمده تقسيم بندي نمود. در دستة اول، محققيني مانند 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 به شبکه های وسيعتر و ترجيح به استفاده از الگوريتم های ساده مقدماتی (با سرعت همگرائی کم) بدليل حجم زياد سربار محاسباتی ايجاد شده اشاره کرد.

در اين رساله، با معرفی دو الگوريتم سلسله مراتبی، يک الگوريتم فازی و يک الگوريتم ترکيبی فازی- سلسله مراتبی با هدف برطرف کردن نقائص فوق الذکر و ضمن برقراری عدالت تناسبی (W,a) به روشهای تخصيص نرخ با سرعت های همگرائی بالاتر دست مي يابيم و ضمناً به بررسی رياضی پايداری الگوريتمهای مطرح شده مي پردازيم.

الگوريتمهای سلسله مراتبی، بر اساس لينکهای گلوگاه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).

 

 

 

 

 

دانلود متن كامل در

download-thesis.com

دانلود متن كامل در

download-thesis.com

دانلود متن كامل در

download-thesis.com

دانلود متن كامل در

download-thesis.com

دانلود متن كامل در

download-thesis.com

 

 

 

 

 مراجع

[1] Tanenbaum, A.S., Computer Networks, 3rd edition, Prentice Hall, New Jersey, 1996.

[2] Brakmo, L.,  TCP Vegas Release 0.8, Nov. 1994.

http://www.cs.arizona.edu/protocols

[3] Mitra, D. and Seery, J.B., “Dynamic adaptive window for high-speed data networks,” in Proc. ACM SIGCOMM’90 Conf., pp. 30-40, 1990.

[4] Mitra, D. and Seery, J.B., “Dynamic adaptive windows for high-speed data networks with multiple paths and propagation delays,” Computer Networks and ISDN Systems, (25), pp. 663-679, 1993.

[5] Floyd, S., “TCP and explicit congestion notification,” ACM Computer Communications Review, Vol. 24, No. 5, pp. 10-23, Oct. 1994.

[6] Fall, K. and Floyd, S., “Simulation-based comparison tahoe, reno and sack TCP,” ACM Compu. Commun. Rev., Vol. 26, No. 3, pp. 5-21, July 1996.

[7] Kelly, F.P., Maulloo, A.K. and Tan, D.K.H., “Rate control for communication networks: shadow prices, proportional fairness and stability,” J. Oper. Res. Soc., Vol. 49, No. 3, pp. 237-252, Mar. 1998.

[8] Kunniyur, S. and Srikant, R., “End-to-End Congestion Control Schemes: Utility Functions, Random Losses and ECN Marks,” IEEE INFOCOM  Mar. 2000.

[9] Fendick, K.W., Rodriguez, M.A. and Weiss, A., “Analysis of a rate-based feedback control strategy for long-haul data transport.” Performance Evaluation, Vol. 16, pp. 67-84, 1992.

[10] Tan, D.K.H., Mathematical Models of Rate Control for Communication Networks, Ph.D. dissertation, pp. 35-61, Cambridge university, Aug. 1999.

[11] Johari, R. and Tan, D., “End-to-End congestion control for the Internet: Delays and Stability,” IEEE Trans. On Networking, Vol.9, No.6, pp. 818-832, Dec. 2001.

[12] Massoulié, L. and Roberts, J., “Bandwidth sharing: objectives and algorithms,” in Proc. IEEE INFOCOM, Vol.3, 1999, pp. 1395-1403.

[13] Mo, J. and Walrand, J., “Fair End-to-End Window-Based Congestion Control,” IEEE Transactions on Networking, Vol. 8, No. 5, pp. 556-567, Oct. 2000.

[14] Hurley, P., Le Boudec, J.Y. and Thiran, P., “A note on the fairness of additive increase and multiplicative decrease,” in Proc. ITC-16, Edinburg, Scotland, pp. 467-478, June 1999.

[15] Bertsekas, D. and Tsitsiklis, J., Parallel and Distributed Computation. Englewood Cliffs, NJ: Prentice-Hall, 1989.

[16] Gallager, R.G. and Bertsekas, D., Data Networks, Prentice-Hall, NJ 1987.[17] Golestani, S.J., A Unified Theory of Flow Control and Routing in Data Communication Networks, Ph.D Dissertation, MIT, Jan. 1980.

[18] Low, S.H. and Lapsley, D.E., “Optimization flow control, I: basic algorithm and convergence.” IEEE/ACM Transcations on Networking, Vol. 7, No. 6, pp. 861-874, Dec. 1999.

http://www.ee.mu.oz.au./staff/slow/research/.

[19] Lapsley, D.E. and Low, S.H., “An optimization approach to ABR control.” In Proceedings of  the ICC, June 1998.

[20] Rohrs, C.E., Berry, R.A. and O’Halek, S.J., “A control engineer’s look at ATM congestion avoidance.” In Proc. IEEE Globecom’95, pp. 1089-94, Singapore, Nov. 1995.

[21] Sathaye, S., Traffic Management Specification version 4.0. ATM Forum Traffic Management Group, Oct. 1996.

[22] Golestani, S.J. and Bhattacharyya, S., “End-to-End Congestion Control for the Internet: A global optimization framework.” In Proc. Of International Conf. On Network Protocols(ICNP), Oct. 1998.

[23] Kelly, F.P., “Charging and rate control for elastic traffic.” European Transactions on Telecommunications, 8:33-37, 1997. http://www.statslab.cam.ac.uk/frank/elastic.html.

[24] La, R.J. and Anantharam, V., “Utility-Based Rate Control in the Internet for Elastic Traffic.” IEEE Trans. On Networking, Vol. 10, No. 2, pp. 272-286, Apr. 2002.

[25] Altman, E., Başar, T. and Srikant, R., “Nash Equilibria for Combined Flow Control and Routing in Networks: Asymptotic Behavior for a Large Number of Users,” IEEE  Transactions on Automatic Control, Vol. 47, No. 6, June 2002.

[26] Jacobson, V., “Congestion avoidance and control,” Comput. Commun.n Rev., Vol.18, No. 4, pp. 314-329, Aug. 1988.

[27] Massoulié, L., Stability of distributed congestion control with heterogenous feedback delays, Technical Report.

[28] Deb, S. and Srikant, R., Global Stability of Congestion Controllers for the Internet, Technical  Report, University of  Illinois at Urbana-Champaign.

[29] Gibbens, R.J. and Kelly, F.P., “Resource pricing and the evolution of congestion control,” Automatica, 1999.

[30] Mackie-Mason, J.K. and Varian, J.K., “Pricing Congestible Network Resources.” IEEE JSAC, Vol. 13, No. 7, pp. 1141-49, Sept. 1995.

[31] Paschalidis, I.C. and Tsitsiklis, J.N., “Congestion-Dependent Pricing of Network Services.” IEEE/ACM Trans. On Networking, Vol. 8, No. 2, pp. 171-184, Apr. 2000.

[32] Shenker, S., “Fundamental design issues for the future Internet,” IEEE J Selected Areas Commun., Vol.13, No.7, pp.1176-1188, Sept. 1995.

[33] Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z. and Weiss, W., “An Architecture for Differentiated Services.” Dec. 1998, [RFC 2475].

[34] Key, P.B., “Resource Pricing for Differentiated Services.” Microsoft Research, St. George House, Cambridge, U.K. Online available at:

http://research.microsoft.ir/users/pbk/

[35] Kelly, F.P., “Effective bandwidth at multi-class queues.” Queueing Systems, Vol. 9, pp. 5-16, 1991.

[36] Nagle, J., “On Packet Switches with Infinite Storage.” IEEE Transactions on Communications, Vol. 35, pp. 435-438, 1987.

[37] Demers, A., Keshav, S. and Shenker, S., “Analysis and Simulation of a Fair Queuing Algorithm.” SIGCOMM CCR 19, No. 4 (1989), pp. 1-12.

[38] Keshav, S., Engineering Approach to Computer Networking, An: ATM Networks, the Internet and the Telephone Network, Addison Wesley Professional, 1st Edition, 1997.

[39] Stiliadis, D. and Varma, A., “Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms” IEEE Transactions on Networking, Vol. 6, No. 3, pp. 611-624, 1996.

[40] Shreedhar, M. and Varghese, G., “Efficient Fair Queuing using Deficit Round Robin.” SIGCOMM CCR 25, No. 4, 1995.

[41] Ferrari, D. and Verma, D., “A scheme for real-time channel establishment in Wide Area Networks.” IEEE journal on selected areas in communications, Vol. 8, No. 3, pp. 368-379, 1990.

[42] Verma, D., Zhang, H. and Ferrari, D., “Guaranteeing delay jitter bounds in packet switching networks.” Tricomm’91, 1991.

[43] Floyd, S. and Jacobson, V., “Random Early Detection Gateways for Congestion Avoidance.” IEEE/ACM Transactions on Networking, Vol. 1, No. 4, pp. 397-413, 1993.

[44] RFC 1633, Braden, R., Clark, D. and Shenker, S., “Integrated Services in the Internet Architecture: an Overview.” June 1994.

[45] Bernet, Y., Networking Quality of Service and Windows Operating Systems, New Riders Publishing and Microsoft Corporation, 2001.

[46] Gerla, M. and Kleinrock, L., “Flow Control: A Comparative Study”, IEEE Trans. Commun. , Vol. COM-28, pp.553-574, Apr. 1980.

[47] Chiu, D.M. and Jain, R., “Analysis of the increase and decrease algorithms for congestion avoidance in computer networks.” Computer Networks and ISDN Systems , No. 17, pp. 1-14, 1989.

[48] Arulambalam, A. and Chen, X.Q., “Allocating fair rates for available bit rate service in ATM networks.” IEEE Communication Magazine, 1996, pp. 92-100.

[49] Hernandez-Valencia, E.J., Benmohamed, L., Chong, S. and Nagarajan, R., “Rate Control Algorithms for the ATM ABR Service.” Europ. Trans. Telecom. Vol. 8, pp. 7-20, 1997.

[50] Charny, A., An algorithm for rate allocation in packet-switching networks with feedback, Master’s thesis, MIT, Cambridge, MA, 1994.

[51] Jain, R., “Congestion control and traffic management in ATM networks: Recent advances and a survey,” Comput. Networks ISDN Syst. , Vol. 28, No. 13, pp. 1723-28, Oct. 1996.

[52] Mayer, A., Ofek, A. and Yung, M., “Approximating max-min fair rates via distributed local scheduling with partial information,” in IEEE Infocom’96, San Francisco, CA, USA, Mar. 1996, pp. 926-936.

[53] Hahne, E., “Round-robin scheduling for max-min fairness in data networks,” IEEE J. Select. Areas Commun., Vol. 9, pp. 1024-39, Sept. 1991.

[54] Floyd, S. and Jacobson, V., “Connection with multiple congested gateways in packet-switched networks, Part 1: One-way traffic,” ACM Comput. Commun. Rev., Vol. 21, No. 5, pp. 30-47, Aug. 1991.

[55] Mankin, A., “Random drop congestion control,” in Proc. SIGCOMM’90, Philadelphia, PA, pp. 1-7, Sept. 1990.

[56] Floyd, S. and Jacobson, V., “On traffic phase effects in packet switched gateways,” Internetworking: Res. and Experience, Vol. 3, No. 3, pp. 115-156, Sept. 1993.

[57] Jaffe, J.M., “Flow control power is non-decentralizable,” IEEE Trans. Commun., Vol. COM-29, pp. 1301-06, Sept. 1981.

[58] Shenker, S., “A theoretical analysis of feedback flow control,” in ACM SIGCOMM’90, Philadelphia, PA, pp. 156-165, Sept. 24-27, 1990.

[59] Jain, R., “Myths about congestion management in high-speed networks,” Internetworking: Res. and Experience, Vol. 3, pp. 101-113, 1992.

[60] Boutremans, C., Vojnovic, M. and Le Boudec, J.Y., “Global fairness of additive-increase and multiplicative-decrease with heterogenous round-trip times,” in IEEE Infocom’00, Tel Aviv, Israel, pp. 1303-12, Mar. 2000.

[61] Ramakrishnan, K.K. and Jain, R., “A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer,” in Proc. ACM SIGCOMM’88 Conf., pp. 303-313, 1988.

[62] Keshav, S., “A control theoretic approach to flow control,” in Proc. ACM SIGCOMM’91 Conf., pp. 3-15, Sept. 1991.

[63] Mitra, D., “Asymptotically optimal design of congestion control for high- speed data networks.” IEEE Transactions on Communications, Vol. 40, No. 2, pp. 301-311, Feb. 1992.

[64] Zhang, L., Deering, S., Estring, D., Shenker, S. and Zappala, D., “RSVP: A new resource reservation protocol,” IEEE Networks, Vol. 7, No. 5, Sept. 1993.

[65] Braden, B., et al. “Recommendations on queue management and congestion avoidance in the Internet. Internet Draft, March 1997.

[66] Bolot, J.C. and Shankar, A.U., “Dynamic behavior of rate-based flow control mechanisms.” ACM  SIGCOMM Comp. Commun. Rev., Vol. 20, pp. 35-49, 1990.

[67] Bonomi, F., Mitra, D. and Seery, J.B., “Adaptive algorithms for feedback-based flow control in high-speed wide-area networks.” IEEE J. Selected Areas Commun. , Vol. 13, pp. 1267-1283, 1995.

[68] Luenberger, D.G., Linear and Nonlinear Programming, 2nd Ed. Addison-Wesley Publishing Company, 1984.

[69] Zadeh, L.A., “Fuzzy Sets”, Inform. Control, pp.338-353, 1965.

[70] Takagi, T. and Sugeno, M., “Fuzzy Identification of Systems and its Applications to Modeling and Control.” IEEE Trans. on Systems Man and Cybernetics, Vol. 15, pp. 116-132, 1985.

[71] Lee, C.C., “Fuzzy Logic in Control Systems: Fuzzy Logic Controller-Part I”, IEEE Trans. On System, Man and Cybernetics , Vol.20, No.2, pp.404-418, Mar.1990.

[72] Bertsekas, D., Gafni, E. and Gallager, R.G., “Second Derivative Algorithms for Minimum Delay Distributed Routing in Networks.” IEEE Trans. On Communication, Vol. COM-32, No. 8, Aug. 1984, pp. 911-919.

[73] Papoulis, A., Probability, Random Variables, and Stochastic Processes, McGraw-Hill Series in Electrical Engineering, Second Edition, 1984.

[74] Vinnicombe, G., “On the stability of end-to-end congestion control for the Internet”, Technical Report CUED/F-INFENG/TR.398, Engineering Department,University of Cambridge, 2000. http://wwwcontrol.eng.cam.ac.uk/gv/internet.

Abstract

Improving the performance of the optimal rate allocation algorithms in data networks is the main objective of this thesis. The optimal utility-based rate allocation algorithm was introduced for the first time by Golestani. Afterwards, Kelly showed that the optimal rate allocation problem could be decomposed into two simpler sub-problems that are solved separately by users and network. He has shown that the network problem has the proportional fairness property and is similar to TCP/IP’s familiar AIMD method and he showed the stability of the proposed method using mathematical approaches. On the other hand the Kelly’s method has some limitations such as the scalability issue, the low convergence rate and the large computational overhead. In this thesis, two hierarchical methods, a fuzzy method and a mixed fuzzy-hierarchical method are introduced to overcome these limitations and achive high-speed rate allocation methods while having the (W,a) proportional fairness property. The stability analysis of the introduced algorithms, the behaviour of the hierarchical algorithms in the presense of the variable-rate background traffic and the users arrival and departure problem are also invistigated in this thesis.

 

1-Quality of Service (QoS)                                                                                                2-Congestion control

3-Fairness              4-Congestion window

1-Max-min                                                                                                                                   2-Proportional

3-Minimum potential delay                                              4-Duality theory

5-Asynchronous Transfer Mode

1-Game theory                   2-Pricing

3-Elastic                      

4-Delay jitter

5-Real time

1-Differentiated Services (DiffServ)               2-Effective Bandwidth

3-Utility function                                                                           

4-Additive Increase-Multiplicative Decrease

5-Scalability           6-Bottleneck

1-Gradient projection                                                                                                             

2-Jacobi projection

1-Loss                                                                                                         

2-Quality / Efficiency Product (Q×E)

3-Overprovisioning

دیدگاهها

هیچ دیدگاهی برای این محصول نوشته نشده است.

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

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

7 + = 12