بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
مقايسه الگوريتم کنترل ازدحام TCP-Vegas با TCP-Reno و ارائه راهکاري نو براي ارسال داده در مبدأها
چکيده
کنترل ازدحام يکي از مسائل مهم در شبکه هاي کامپيوتري مي باشد. الگوريتم کنترل ازدحام TCP-Vegas در گامهاي اوليه ازدحـام را تشـخيص مي دهد و از وقوع آن پيشگيري مي کند ولي الگوريتم TCP-Reno بعد از وقوع ازدحام، وجود ازدحام را تشخيص داده و از ادامه ازدحام جلوگيري مي کند. بررسي ها نشان داده است ، که الگوريتم TCP-Vegas نسبت به TCP-Reno کاراتر است . در اين مقالـه الگـوريتم TCP-Vegas بهبـود داده شده ، با الگوريتم هاي کنترل ازدحام TCP-Vegas و TCP-Reno مقايسه مي شود. راهکار ارائه شده داراي بهـرهوري بـالا، نوسـانات کـم در طول پنجره ازدحام و تغيرات کم در طول صف مي باشد. نتايج بدست آمده از شبيه سازي الگـوريتم هـا در محـيط ٢-ns موفقيـت کامـل الگـوريتم پيشنهادي را نشان مي دهد.
کلمات کليدي
کنترل ازدحام، TCP-Vegas،TCP-Reno ، بهره وري
١- مقدمه
اينترنت شبکه اي است ، که کامپيوترهاي سراسر جهـان را بـه يکـديگر متصل مي کند. اين شبکه که مبتني بر پروتکل TCP.IP است ، بسته ها را به صورت سويچينگ بسته اي ارسال مي کند. اگر چه ريشه اين شبکه به NsFnet بر مي گردد، که تعداد گرههاي آن از تعداد انگشتان دسـت تجاوز نمي کرد، ولي در طي دو دهه گذشته ، رشد انفجاري آن با اتصال ميليونها ماشين به اين شبکه همراه شده است . شبکه اينترنت ، امروزه يک سيستم مطمئن تبادل اطلاعات براي صدها ميليون انسان مي باشد و به عنوان مهمترين نوآوري قرن اخير، روش زندگي مـا را تغييـر داده است . امـا وجـود پديـدهاي بنـام ازدحـام مشـکلاتي را بـراي اسـتفاده کنندگان از اينترنت براي تبادل داده ايجاد کرده است . ازدحـام زمـاني رخ مي دهد، که مجموع درخواست ها از يک منبع شـبکه (مـثلا پهنـاي باند يک اتصال ١١) فراتر از ظرفيت موجود باشد. نتيجه چنين وضـعيتي ، افــزايش تــاخير و احتمــال حــذف شــدن بســته و شــايد اضــمحلال ازدحام ٢٢باشد، که در چنين حالتي معمولا ظرفيت اتصالها بـه صـورت کامل اشغال مي باشند، ولي گذردهي فوق العاده پايين مي باشد. در ادامه مقاله در بخش دوم الگوريتم TCP-Vegasمورد بررسي قرار مي گيـرد.
در بخش سوم الگوريتم TCP-Reno ارزيابي مي شود. در بخش چهـارم الگوريتم پيشنهادي معرفي مي گردد و در بخش پـنجم جمـع بنـدي و نتيجه گيري بيان خواهد شد.
٢-الگوريتم TCP-Vegas
در مرحله شروع آهسته ، TCP-Vegas، پنجره ازدحـام خـود را بسـيار محتاطانه تر افزايش مي دهد. در TCP-Vegas، مبدأ، تاخير انتشار انتها بـه انتهـا را تخمـين مـي زنـد و آن را بعنـوان کمتـرين RTT در نظـر مي گيرد، سپس با استفاده از قانون ليتلز [١] تعداد بسته هاي بافر شده در طول مسير را با محاسبه حاصل ضرب تاخير صف انتهـا بـه انتهـا در نرخ ارسال به دست مي آورد. مبدأ سپس سعي مي کند، که اين کميـت را در محدوده قابل قبولي حفظ نمايد، اين محدوده توسط دو پارامتر α و β مشخص مي گردد. هدف اين است که همواره تعداد اندکي بسته در صف ها موجود باشد، تا هم اتصال ها داراي بهرهوري کامـل باشـد و هـم تاخير صف ها کوچک باشد. الگـوريتم TCP-Vegas از تـوان عمليـاتي واقعي و توان عملياتي مورد انتظار براي ارسال داده استفاده مي کند. توان عملياتي واقعي و توان عملياتي مورد انتظار طبق روابط (١) و (٢) محاسبه مي شود[٢]-[٥]و[٩].
اگر اختلاف بين توان عملياتي واقعي و توان عملياتي مورد انتظـار را ∆ و طول پنجره را W بناميم . بعد از رسيدن الگوريتم به مرحله پرهيـز از ازدحام طول پنجره ازدحام طبق رابطه (٣) محاسبه مي شود[٩].
اگر طبق محاسبات انجام شده با توجه به رابطه (٣) دادهي کمتـري در صف باشد، طول پنجره ازدحام بصـورت خطـي افـزايش مـي يابـد. اگـر دادهي بيشتري در صف موجود باشد و مقدار ∆ بزرگتر از β باشد طول پنجره کاهش بصورت خطي کاهش مي يابد در غيـر ايـن صـورت نـرخ ارسال خوب بوده و طول پنجره ازدحام ثابت نگه داشته مي شود.
TCP Vegas براي تخمين RTT بجاي دانه هاي درشت تايمر TCP از ساعت سيستم استفاده مي کند. تخمين دقيقتر RTT شـود موجب مـي تا ازدحام زودتر تشخيص داده شود، بنابراين TCP مي تواند هر بسته را به راحتي قبل از دريافت سه تا dupack انتقال مجدد دهد.
٣- الگوريتم TCP-Reno
اندازهگيريهايي که در مسـيريابهـا، سـتون فقـرات اينترنـت صـورت گرفته است ، نشان مي دهد، که حدود ٩٠% از ترافيک اينترنت را TCP Reno تشکيل مي دهد[٨]. مبدأ TCP Reno، با استفاده از الگـوريتم پنجره لغزان، بسته ها را ارسال مي کند. نرخ ارسال بسته بوسـيله انـدازه پنجره ازدحام کنترل مي گردد، که بيـانگر حـداکثر تعـداد بسـته هـايي است ، که قبل از دريافت ACK، قابل ارسال مـي باشـند. هنگـامي کـه پنجره ازدحام پر مي شود، مبدأ بايد قبل از ارسـال يـک بسـته جديـد، منتظر رسيدن ACK بماند. ايده کليدي اين الگوريتم ايـن اسـت ، کـه براي استفاده از پهناي باند خالي موجود، اندازه پنجره به صورت جمع شونده افزايش يابد، ولي به محض وقوع ازدحام، اندازه پنجره به صورت ضربي کاهش يابد. هر مبدأ با پنجرهاي به طول يـک بسـته ، ارتبـاط را شروع مي کند و با دريافت هر ACK، طول پنجره را يک واحد افـزايش مي دهد، اين امر منجر به دو برابـر شـدن طـول پنجـره در هـر RTT مي گردد و به شروع آهسته معروف اسـت . شـکل (١) تغييـرات طـول پنجره ازدحام را نشان مي دهد. در اين مرحله ، مبدأ بـه صـورت نمـايي نرخ ارسال خود را افزايش مي دهد و به سـرعت مـي توانـد پهنـاي بانـد موجود را پر نمايد. هنگامي که اندازه پنجره به حد آستانه شروع آهسته (ssThreshold) مــي رســد، مبــدأ وارد مرحلــه "پرهيــز از ازدحــام " مي گردد. در اين مرحله در هـر RTT طـول پنجـره تنهـا يـک واحـد افزايش مي يابد. يعني اگر براي همه بسـته هـاي ارسـال شـده در يـک پنجره، ACK دريافت شود، بازاي همه آنها، يک واحد به طـول پنجـره اضافه مي گردد.
هنگامي که مبدأ، از طريق دريافـت ACK هـاي تکـراري، گـم شـدن بســته اي را تشــخيص مــي دهــد، انــدازه پنجــره را نصــف و انــدازه ssThreshold را به روز رساني مي کند و با ارسال مجدد بسته گمشـده عمل بازيابي سريع را انجام مـي دهـد. اگـر گـم شـدن بسـته از طريـق Time-out شناسايي شود، در آن صورت اندازه پنجـره بـه يـک بسـته کاهش مي يابد و مبدأ دوباره وارد مرحله شروع آهسته مـي گـردد. ايـن نسخه از TCP داراي دو مشکل زير است :
الف ) اولين ايرادي که به اين الگوريتم وارد است ، اين است که بهره وري بالا تنها با صف هاي پر و زماني که شبکه در مرز ازدحام کار مـي کنـد، قابل حصول است و لذا با الگوريتم موجود بهره وري پايين مي آيد.
ب) گم شدن بسته مي تواند در اثر پديدههـايي غيـر از ازدحـام نيـز رخ دهد و لذا با مکانيزم موجود کارايي فوق العاده پايين مي آيد.
٤- الگوريتم پيشنهادي: استفاده از بهينه سازي اجتماع ذرات بدليل اينکه الگوريتم TCP-Vegas کاراترين الگوريتم کنتـرل ازدحـام است . در اين مقاله ما سعي کردهايم الگـوريتم TCP-Vegas را بهبـود داده و با الگوريتم هاي TCP-Vegas و TCP-Reno مقايسه کنيم . بـه دليل اينکه پارامترهاي α و β کميت هاي ثابتي هستند و در طول زمان تغيير نمي کنند، اين امر موجب شده تا الگوريتم TCP-Vegas حالـت پويايي نداشته باشد و بطور ايستا کار کند. شبکه اينترنت شبکه اي پويا مي باشد و پيوسته در حال تغيير است . براي اينکه بتوانيم ايـن پويـايي در الگوريتم TCP-Vegas باشد سعي کرديم مقادير α و βرا با توجـه به شرايط شبکه تغيير دهيم تا مقادير α و β حالت پويا داشته باشـند، تا بهرهوري الگوريتم را افزايش و از نوسانات آن کاسته شود.
الگـوريتم بهينـه سـازي اجتمـاع ذرات در سـال ١٩٩٥ توسـط آقايـان James Kennedy و Russell Eberhart ارائه شد، کـه يـک تکنيـک بهينه سازي قدرتمند مبتني بر قوانين احتمـال اسـت کـه از حرکـت و هوش دسته جمعي ذرات گرفته شده است . در اين روش ذرات در کنار هم در يک فضاي جستجو با حرکت هوشمندانه سـعي در پيـدا کـردن راه حل بهينه مي کنند[١٠,١١,١٢].
در الگوريتم PSO، دسته ذرات شـامل M ذره اسـت . هـر ذره در يـک فضاي N بعدي فعاليت مي کند. هر ذره "پرواز" خود را بر اساس تجربه پرواز خود و تجربه پرواز اعضـاي ديگـر تنظـيم مـي نمايـد. هـر ذره بـا استفاده از سرعت ، در مورد ميزان و جهت "پرواز" خود تصـميم گيـري مي کند، تا نقطه بهينه در فضـاي N بعـدي را دنبـال کنـد. موقعيـت و سرعت ذره i را در تکرار K مي توان به شکل فرمول ٣ و ٤ بيان کرد:
هر ذره براي يافتن راه حل بهينه در فضاي جستجو ادامه مي دهـد، تـا بهترين راه حل که تا آخرين مرحله بـه صـورت گروهـي بدسـت آمـده دست يابد. اين مقدار بهترين شخصي (Pi,best) ناميده مي شود و طبق فرمول پنجم قابل بيان است .
يکي ديگر از بهترين راهحل ها در الگـوريتم PSO وجـود دارد بهتـرين سراسري (Pg,best) است ، که از همسايگي تمامي ذرات بدست مي آيد و طبق رابطه (٦) قابل بيان است .
هدف اصلي PSO سرعت بخشيدن به ذرات در رسيدن به نقطه بهينـه سراسري و فردي است . سرعت و موقعيت ذره i در تکرار ١+K مطـابق با فرمول (٧) و (٨) محاسبه مي شود.
بترتيــب بــردار موقعيــت و ســرعت ذرات را تشــکيل مي دهند. w وزن لختي ، c1 و c2 اعداد ثابت مثبت هستند، که ضرايب شتاب گفته مي شود و r1 و r2 دو عدد تصادفي با توزيـع يکنواخـت در محدوده [١-٠] مي باشند.
در نسخه اصلي TCP-Vegas مقادير الفا و بتـا بـه صـورت ايسـتاتيک تعريف شدهاند(١=الفا و ٣=بتا). الگوريتم TCP-Vegas با ايـن مقـادير نمي تواند به کاراي بالا دست يابد. ليکن مـا الگـوريتم TCP-Vegas را بهبود داده ايم و آن را الگوريتم پيشنهادي مي ناميم ، که در آن مقادير α و β با توجه به شرايط شبکه ، RTT و... بصورت پويا تنظيم مـي شـوند.
الگوريتم پيشنهادي يک الگوريتم مبدأ است ، کـه شـرايط شـبکه را بـا استفاده از اندازهگيري RTT تخمين مي زند و سپس براي دست يابي به کارايي بالا بر روي مقادير α و β تصميم گيري مي کند. محاسبه سرعت α و β با استفاده از فرمول (٩) و (١٠) بدست مي آيد.
براي تعيين موقعيت بعدي α و β، سرعت بدست آمده از فرمـولهـاي (٧) و (٨) را با موقعيت يا همان مقادير قبلي α و β مطـابق بـا فرمـول (١١) و (١٢) جمــع مــي کنــيم . α و β محاســبه شــده جديــد بــراي تصميم گيري طول پنجره ازدحام بکار مي رود.
در هر مرحله RTT محاسبه مـي شـود. اگـر مقـدار RTTاي جديـد از مقادير قبلي RTT کمتر باشد به اين معني است ، که مقـادير اسـتفاده شده براي α و β در مرحله قبل مقادير مطلـوب بـودهانـد و بـه عنـوان مقادير محلي استفاده مي شوند. در
