روش های کنترل ازدحام در لایه انتقال شبکه

روش های کنترل ازدحام در لایه انتقال شبکه

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

مفهوم کنترل ازدحام

کنترل ازدحام یا congestion control، در شبکه های کامپیوتری یعنی جلوگیری از تجمع داده های انتقالی در صف انتظار و جلوگیری از بین رفتن بسته ها و یا اطلاعات در زمان انتقال می باشد. این ازدحام وقتی اتفاق می افتد که داده ای ارسالی بیش از حد مجاز ظرفیت کانال باشد و روش های جلوگیری از ازدحام در شبکه بیشتر بر اساس کاهش نرخ ارسال داده ها از طرف فرستنده است.

دسته بندی روش های کنترل ازدحام در لایه انتقال

روش های کنترل ازدحام از لحاظ نوع بازخورد دریافتی از شبکه به سه گروه تقسیم می شوند که در ادامه این بخش هر گروه به اختصار شرح داده می شود و برای هر گروه چند نمونه از پروتکل های معروف بررسی می گردد.

1. کنترل ازدحام بر پایه مهلت زمانی
2. اجتناب از ازدحام بر پایه اعلان صریح ازدحام
3. اجتناب از ازدحام بر پایه تاخیر

1- کنترل ازدحام بر پایه مهلت زمانی

در این روش پس از ارسال داده و قبل از ارسال مجدد داده به میزان زمان که معمولا دو برابر حداکثر مدت زمان رفت و برگشت بسته است، صبر خواهیم کرد. در صورتی که پس از این زمان، تصدیق دریافت بسته ها از مقصد به دست فرستنده نرسد، به منزله وقوع ازدحام در شبکه تلقی شده و میزان داده ارسالی (پنجره ارسالی) در بازه ی زمانی بعدی کاهش می یابد.

روش های موجود جهت کنترل ازدحام بر پایه مهلت زمانی

1. الگوریتم TCP-Tahoe
2. الگوریتم TCP Reno
3. الگوریتم TCP NewReno

1- معرفی الگوریتم TCP-Tahoe

یکی از اولین راهکار هایی که توسط جاکوبسون ارائه گردید روش TCP-Tahoe می باشد و الگوریتمی که در این روش ارائه شده از بخش اساسی تشکیل یافته که در ادامه به هر کدام از آنها اشاره خواهیم کرد.

1. تخمین زمان ارسال مجدد (RTO) : عامل TCP پس از ارسال هر بسته زمان ارسال بسته را ثبت خواهد کرد. در صورتی که پس از گذشت یک زمان تخمینی تصدیق دریافت بسته دریافت نشود، فرض بر این است که بسته در جایی از مسیر به دلیل ازدحام ازدست رفته، لذا عاملی، بسته را مجددا ارسالی خواهد کرد که تخمین صحیح این زمان نیز از اهمیت بالای برخوردار می باشد.
2. در صورتیکه این زمان کوچک باشد باعت ارسال چند باره یک بسته خواهد شد، که موجب تشدید ازدحام می گردد و در صورت بزرگ بودن عاملی از دسته رفتن بسته ها بیشتر به طولی می انجامد و گذردهی جریان را کاهش خواهد داد.
3. بخش دوم در واقع بهبودی برای دسته اول است، هر چند به کمک RTO از دست رفتن بسته استاندارد، تنها راه برای تشخیصی از دست رفتن بسته دریافت نشدن Ack پس از گذر زمان RTO است، در حالی که از بسته های Ack تکراری را می توان به این منظور استفاده کرد.
4. به زبان ساده تر در صورت دریافت بسته های Ack تکراری می توان به سرعت بسته ای که از دست رفته را تشخیص داده و مجدا ارسال نمود. لازم به توضیح است که بسته ی Ack حداکثر پس از مدت زمان RTT به دست عاملی خواهد رسید.
5. آخرین و مهمترین بخش در این پروتکل، فاز آغاز آهسته (SS) و فاز جلوگیری از کنترل ازدحام (CA) است. در فاز آغاز آهسته عامل TCP سعی خواهد کرد که حداکثر ظرفیت کانال را شناسایی کند و در صورت وقوع ازدحام پنجره ارسال خود را به صورت ضربی کاهش می دهد، (اندازه پنجره ارسالی نصف خواهد شد.) و در فاز جلوگیری ازدحام اندازه پنجره ارسالی با رشد خطی افزایش خواهد یافت، در این فاز عاملی سعی خواهد کرد که گذردهی جریان TCP را افزایش دهد و بیشترین داده ممکن را قبل از وقوع ازدحام ارسال کند. در شکل زیر روش آغاز آهسته و فاز پرهیز از ازدحام در TCP-Tahoe نشان داده شده است.

شکل 1: روش آغاز آهسته و فاز پرهیز از ازدحام

2- معرفی الگوریتم TCP Reno

همانطور که در الگوریتم TCP Tahoe مشاهده شد در صورت از دست رفتن یک بسته، اندازه پنجره ارسال باز نشانی شده و مجددا از مقدار ۱ افزایش می یابد، این واکنش سخت گیرانه و انفجاری، گذردهی جریانی را که از الگوریتم Tahoe استفاده می کند، را کاهش می دهد. به عنوان مثالی شکل زیر را در نظر بگیرید، در صورتیکه نرخ ارسال ما ۴ برابر گذردهی مسیریاب باشد، گذردهی جریان را تا ۷۵ درصد کاهش را تجربه خواهد کرد.

شکل 2: افزایش نمای Packet Loss در صورت افزایش سربار مسیریاب

برای حل این مشکل جکوبسون دو مفهوم جدید را معرفی نمود :

1. وقوع ازدحام بزرگ : عدم دریافت تصدیق دریافت بسته ها (Ack) پس از گذشت یک بازه ی زمانی خاص (مانند: RTO و یا RTT) نشان می دهد که برای یک بازه ی زمانی محدود هیچکدام از بسته ها به مقصد نرسیده اند، می توان گفت که احتمالا شبکه شدیدا دچار ازدحام شده است، در چنین شرایطی، باز نشانی پنجره ارسال (آغاز آهسته با اندازه اولیه 1 واحد برای پنجره ارسال) معقول به نظر می رسد.
2. وقوع ازدحام کوچک : یک حالت کاملا متفاوت در شبکه دریافت بسته های Ack تکراری است. به عنوان نمونه دریافت 4 بسته Ack تکراری به این معناست که بسته ها به مقصد می رسند و گاها 1 یا 2 بسته از دست رفته اند، در چنین شرایطی خواهیم گفت که شبکه به صورت جزئی دچار ازدحام گردیده، زیرا توانایی انتقال بسته ها کاملا از بین نرفته و تعدادی از بسته ها به مقصد نرسیده اند. در چنین شرایطی الگوریتم Reno وارد فاز بازیابی سریع خواهد شد.

شکل 3: روش رشد و حرکت پنجره لغزان در TCP Reno

همانظور که در تصویر بالا مشاهده می شود، در صورت وقوع ازدحام کوچک، پنجره ارسال نصف خواهد شد و در ادامه تمامی بسته های که از دست رفته اند، ارسال می شوند، این فاز زمانی به پایان می رسد که دیگر ACK تکراری دریافت نشود، پس از پایان این فاز وارد فاز پرهیز از ازدحام خواهیم شد.

شکل 4: نمایش فاز های آغاز آهسته و پرهیز از ازدحام در پروتکل Reno

3- معرفی الگوریتم TCP NewReno

یکی از نقاط ضعف در فاز بازیابی سریع (FR) هنگامی است، که چندین بسته به صورت زنجیر ای از بین می روند که باعث افزایش زمان بازیابی خواهد شد. در شکل زیر فاز بازیابی سریع 3 مرتبه انجام شده و اندازه پنجره ارسال 3 مرتبه نصف گردیده است، در نتیجه گذردهی الگوریتم در محیط های که بارکاری بالای دارند، کاهش می یابد.

شکل 5: فاز بازیابی سریع در TCP Reno

به جهت رفع این مشکل الگوریتم NewReno ارائه گردید. فلوید الگوریتم بازیابی سریع را اصلاح کرد، در شکل زیر الگوریتم اصلاح شده را مشاهده می کنید. با ذکر یک مثال این الگوریتم را شرح می دهیم، فرض کنید پنجر های به طول 100 بلوک از داده های بافر شده را ارسال نموده و قطع های از 10 بلوک داده از دست رفته است. برای جلوگیری از کاهش 10 باره پنجره ارسال در هنگام ورود به فاز بازیابی سریع تا هنگام دریافت تصدیق تمامی بلوک های داده موجود در این پنجره، از فاز بازیابی سریع (FR) خارج نخواهیم شد. به زبان ساده در صورت از دست رفتن بسته های یک پنجره فرض بر بروز ازدحام است و اندازه پنجره ارسال یک مرتبه به نصف تقلیل می یابد.

شکل 6: روش رشد و حرکت پنجره لغزان در TCP NewReno

2- اجتناب از ازدحام بر پایه اعلان صریح ازدحام

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

به کمک این روش برای ارسال پیام اخطار به فرستنده، بسته ها حذف نخواهند شد، بلکه با قرار دادن اطلاعاتی در سرآیند بسته ها به فرستنده در مورد میزان احتمال وقوع ازدحام اخطار خواهیم داد. در این روش گره های میانی شبکه نسبت به بار کاری و حداکثر ظرفیت شبکه آگاه و حساس هستند. در صورتیکه بار کاری ارتباط از یک آستانه خاص عبور کند، قبل از وقوع ازدحام به فرستنده ها درشبکه اطلاع داده می شود. هر فرستنده پس از دریافت پیام اخطار متناسب با سطح اخطار دریافتی پنجره ارسال خود را کاهش میدهد.

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

1. الگوریتم XCP
2. الگوریتم VCP
3. الگوریتم MLCP (کنترل ازدحام به کمک بازخورد چند سطحی)

1- معرفی الگوریتم XCP

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

در صورت افزایش تاخیر بازخورد، سیستم ناپایدار خواهد شد. در نتیجه در صورت افزایش بیش از حد تاخیر، باید سرعت ارسال داده را کاهش دهیم. سوال اساسی یافتن ارتباط بهینه بین میزان تاخیر و بازخورد است، که سیستم در حالت پایدار بماند. یکی دیگر از نکات مثبت در این روش، جدا شدن روش کنترل گذردهی از روش کنترل عدالت
است. جهت افزایش گذردهی، از میزان پهنای باند غیرفعال استفاده می شود، در حالیکه برای افزایش عدالت؛ پهنای باند جریان هایی که بیش از سهم عادلانه خود از پهنای باند در گلوگاه استفاده میکنند، اصلاح خواهند شد و در بازهای منصفانه قرار خواهند گرفت و پهنای باند آزاد شده به سایر جریانها اختصاص خواهد یافت. از دیگر مزایای این روش نگهداری وضعیت شبکه در بسته های هر جریان است، بنابراین مسیریاب نیازی ندارد که به ازاء هر جریان وضعیت را در داخل مسیریاب نگهداری نماید. بدین صورت تعداد جریان های که میتوان با این روش مدیریت کرد، افزایش خواهد یافت.

2- معرفی الگوریتم VCP

الگوریتم VCP با در نظر داشتن استانداردهای موجود در سرآیند لایه شبکه یک راهکار عملی ارائه می نماید در این روش با کمک گرفتن از دو بیت اعلان صریح ازدحام (که در سرآیند لایه IP قرار دارند.) به عنوان شناسه ای جهت تشخیص وضعیت ازدحام در شبکه، استفاده شده است. در اینجا خلاصه ای از چگونگی عملکرد این الگوریتم ارائه میشود. هر مسیریاب بارکاری را به صورت بلادرنگ محاسبه مینماید، گیرنده جریان TCP پس از دریافت بسته، بازخورد دریافت شده از مسیریاب را از آن خارج میکند و در قالب بسته Ack برای فرستنده جریان ارسال می نماید. بارکاری در سه سطح پایین، بالا و سربار بالا دسته بندی میگردد. سپس این سه سطح به صورت یک کد باینری  دو بیتی به عنوان بیت های ECN در سرآیند لایه IP قرار میگیرد. در ادامه فرستنده با توجه به بازخوردی که از شبکه دریافت میکند، سرعت افزایش و کاهش پنجره ارسال را تنظیم مینمایند. به عنوان مثال در وضعیت بارکاری پایین؛ پنجره ارسال به صورت ضربی افزایش خواهد یافت و یا در حالت بارکاری بالا؛ پنجره ارسال به صورت خطی افزایش می یابد و در صورت وقوع ازدحام و افزایش بیشتر بارکاری پنجره ارسال به صورت ضربی کاهش مییابد.

از مزایای این روش میتوان به عدم تغییر در سرآیند IP اشاره کرد. همچنین بار محاسباتی این روش در مسیریاب ها بسیار اندک است و نیاز به نگهداری وضعیت هر جریان در مسیریاب نیست. در ضمن میزان تغییرات در الگوریتم های TCP در سمت گیرنده و فرستنده بسیار جزئی است. در کنار این خصوصیات، گذردهی و عدالت در تسهیم منابع الگوریتم VCP تقریبا با پروتکل XCP برابری میکند.

3- معرفی الگوریتم MLCP (کنترل ازدحام به کمک بازخورد چند سطحی)

الگوریتم MLCP نیز همانند الگوریتم VCP از شناسه بارکاری که توسط مسیریاب ها محاسبه می شود، استفاده می نماید و گیرنده بسته داده اطلاعات بازخورد دریافتی از مسیریاب را در بسته های Ack قرار میدهد. الگوریتم کنترل جریان در فرستنده به کمک همین بازخورد نرخ ارسال داده (پنجره ارسال) را تنظیم مینماید. تفاوت این روش با پروتکل VCP در تعداد بیت هایی است که برای انعکاس وضعیت شبکه به دست فرستنده جریان میرسد، MLCP از 4 بیت برای سطوح مختلف ازدحام در شبکه استفاده می نماید. روش VCP در فاز پرهیز از ازدحام از روش AIMD استفاده میکند، در حالیکه MLCP از روش AIIIMD استفاده می نماید. در ادامه به اختصار به این مفاهیم و نتیجه استفاده از آنها اشاره شده است.

دلیل استفاده از 4 بیت برای تعیین سطوح ازدحام چیست؟ نتایج آزمایشات و شبیه سازی ها نشان داد که در صورت استفاده از 4 بیت می توان به گذردهی بسیار مطلوب و نزدیک به حالت بهینه دست یافت. در ضمن زمان همگرایی به سهم عادلانه و زمان مورد نیاز جهت کاهش نرخ ارسال در هنگام وقوع ازدحام کاهش خواهد یافت. در این روش نرخ ارسال با توجه به میزان پهنای باند آزاد و همچنین تاخیر بازخورد تعیین می شود، که از  “نوسانات شدید گذردهی” جلوگیری خواهد کرد. بارکاری در مسیریاب ها به صورت پویا و بر اساس RTT هر جریان محاسبه می گردد، به همین جهت تسهیم عادلانه پهنای باند در میان جریانهایی با RTT متفاوت با دقت  بیشتری انجام خواهد شد.

3- اجتناب از ازدحام بر پایه تاخیر

روشی که در بالا به آن اشاره شد، کارکرد بسیار موثری در کنترل ازدحام دارد، اما در مواقعی که داده بعد از عبور از شبکه های ناهمگن با معماری متفاوت به مقصد می رسند، نمی توان از اعلان صریح ازدحام استفاده کرد. دلیل این امر ساده است، ممکن است بازخورد ارسال شده از یک گره، برای منبع دیگر قابل درک نباشد، و عملکرد سیستم را با مشکل مواجه کند. از سوی دیگر در روش های کنترل ازدحام که بر پایه مهلت زمانی هستند، فرستنده ازدحام را پس از وقوع آن تشخیص میدهد، که در نتیجه آن اندازه پنجره ارسال خود را به نصف کاهش میدهد. در هنگام وقوع ازدحام عامل TCP به دلیل بی اطلاعی از میزان بارکاری شبکه بر شدت ازدحام می افزاید، این امر علاوه بر افزایش تاخیر صف و از بین بردن بسته ها، باعث کاهش شدید گذردهی خط هم خواهد شد. در بخش قبل به مسئله تغییرات دورهای نرخ ارسال، RTT ، گذردهی و طول صف اشاره شد.

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

روش های موجود جهت اجتناب از ازدحام بر پایه تاخیر

1. الگوریتم TCP DUAL
2. الگوریتم TCP Vegas
3. الگوریتم TCP Vegas+

1- معرفی الگوریتم TCP DUAL

الگوریتم TCP-Tahoe در جلوگیری از تشدید ازدحام در شبکه اینترنت سهم بسزایی را ایفا کرد. هر چند گذردهی شبکه به صورت قابل ملاحظه ای افزایش یافت، لیکن دامنه تغییرات گذردهی و دامنه تغییرات تاخیر بسیار بالا بود. مشکلاتی نظیر کاهش کارایی بافرها ، تغییرات تاخیر بالا و بالا بودن نرخ ازدست رفتن بسته ها همچنان پابرجا بود.

شکل 7: نمایش فازهای آغاز آهسته و پرهیز از ازدحام در TCP DUAL

وانگ و کراوکروفت پروتکل کنترل ازدحام TCP DUAL را معرفی کردند در شکل بالا ایده الگوریتم DUAL مشاهده می شود که فاز CA اصلاح شد است فرض کنید گیرنده TCP با دریافت هر بسته پیام Ack بدون تاخیر برای فرستنده ارسال می کند، ایده این روش در اینجاست؛ عامل با در نظرگرفتن “تغییرات RTT” (اختلاف زمان ارسال بسته و دریافت Ack) تخمینی از تاخیر صف بندی را بدست می آورد و در صورت افزایش RTT و گذر از یک آستانه، قبل از وقوع ازدحام و از دست رفتن بسته ها اندازه پنجره ارسال خود را کاهش میدهد. در واقع با استفاده از تاخیر صف بندی در شبکه آستانه ازدحام را پیش بینی نموده و از وقوع ازدحام پرهیز خواهد کرد.

الگوریتم DUAL نوسانات گذردهی کانال و همچنین نوسانات طول صف را مهار کرد. تلاش های صورت گرفته در مهار و کنترل بهینه منابع در این روش بسیار موثر هستند، اما متاسفانه به طور کامل مشکلات مذکور برطرف نگردید. همچنین تخصیص عادلانه منابع به کمک این روش به درستی صورت نمی پذیرد.

2- معرفی الگوریتم TCP Vegas

الگوریتم Vegas توسط Brakmo و Peterson ارائه گردید و ایده اصلی در این الگوریتم، بر پایه تخمین میزان بافر اشغال شده در مسیریاب استوار است. مشابه روش DUAL این الگوریتم هم بر پایه اندازهگیری RTT عمل می کند. کمینه RTT مشاهده شده در طول اتصال به معنای یک مقدار مرجع برای تشخیص حالت “فارغ از ازدحام” شبکه به کار می رود. به عبارت دیگر در صورت افزایش RTT در طول اتصال، این مسئله به عنوان افزایش طول صف و کم شدن فضای آزاد بافر در مسیریاب تفسیر می گردد. برخلاف الگوریتم DUAL در الگوریتم Vegas سعی شده که تعداد بسته های موجود در صف به صورت کمی تفسیر شده و یک مقدار قطعی و نه نسبی برای تعداد بسته های موجود در صف مسیریاب گلوگاه بدست آید.

الگوریتم TCP Vegas با ثابت نگه داشتن نرخ ارسال در ناحیه ای پایدار به نحوی بسیار موثر گذردهی جریان TCP را بهبود می بخشد. متاسفانه، تحقیقات اخیر نشان میدهد که جریان های Vegas در رقابت با جریان های Reno در کسب سهم عادلانه پهنای باند موفق نیستند. به عنوان مثال در شرایطی که چندین مسیر برای رسیدن به مقصد وجود دارد، الگوریتم در تخمین صحیح منابع آزاد شبکه دچار خطا خواهد شد. جریان های جدید به دلیل مشاهده ناصحیح minRTT سهم بیشتری از پهنای باند را اشغال می نماید.

3- معرفی الگوریتم TCP Vegas+

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

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