تشخیص زودهنگام تصادفی ازدحام

تشخیص زودهنگام تصادفی ازدحام (RED)، یا همان حذف زودهنگام تصادفی بسته ها یکی از الگوریتم‌های مدیریت فعال صف است. همچنین این الگوریتم یکی از الگوریتم‌های کنترل ازدحام به‌شمار می‌آید.^[۱]

در الگوریتم droptail رایج، یک روتر یا هر قطعه دیگر شبکه تا حد امکان بسته‌ها را بافر کرده و بعد از پر شدن بافر بسته‌های جدید را حذف می‌کند. اگر بافر همواره پر باشد، شبکه دچار ازدحام شده‌است. الگوریتم droptail فضای بافر را به صورت ناعادلانه‌ای بین جریان ترافیکی تقسیم می‌کند. همچنین droptail ممکن است منجر به پدیده همزمانی همگانی tcp شود؛ چرا که همه اتصالات TCP به صورت هم‌زمان "عقب نشینی" و به صورت هم‌زمان شروع به ارسال ترافیک می‌کنند. به این ترتیب شبکه ها به صورتی نوبتی کار می‌کنند و سپس دچار ازدحام می‌شوند. الگوریتم RED برای رفع این مشکلات به کار می‌رود.

عملکرد ویرایش

RED متوسط طول صف را پایش می‌کند و بسته‌ها را بر اساس احتمالات آماری حذف می‌کند یا زمانی که توام با ECN کار می‌کند بسته‌ها را علامت‌گذاری می‌کند. اگر بافر تقریباً خالی باشد، تمام بسته‌های ورودی وارد صف می‌شوند. با افزایش طول صف، احتمال حذف شدن بسته‌های ورودی نیز بیشتر می‌شود. وقتی بافر تقریباً پر شود، این احتمال به 1 میل می‌کند و تمام بسته‌های دریافتی حذف می‌شوند. RED عادلانه تر از droptail عمل می‌کند؛ چرا که تمایلی علیه ترافیک انفجاری که تنها از بخشی از پهنای باند استفاده می‌کند، ندارد. هرچه یک هاست ترافیک بیشتری ارسال کند، احتمال اینکه بسته‌هایش حذف شوند بیشتر می‌شود، زیرا احتمال حذف بسته یک هاست خاص به نسبت حجم داده‌ای است که در صف دارد. شناسایی زودهنگام به پیشگیری از پدیده همزمانی همگانی TCP کمک می‌کند.

مشکلات الگوریتم RED کلاسیک ویرایش

به گفته Van Jacobson "الگوریتم RED کلاسیک دو مشکل دارد".^[۲] پیشنهادهایی برای بهبود این الگوریتم مطرح شد و پیش‌نویسی ^[۳] نیز برای آن تهیه شد، ولی هیچگاه به مرحله چاپ یا بهره‌برداری فراگیر نرسید. البته تلاش‌هایی برای اتمام تحقیقات و برطرف کردن خطاها انجام شده‌است. RED محض کیفیت خدمات (QoS) را پشتیبانی نمی‌کند. RED وزن دار (WRED) و نیز (RED (RIO با ورودی و خروجی ^[۴] از تشخیص زودهنگام همراه با ملاحظات کیفیت سرویس پشتیبانی می‌کنند.

انواع دیگر ویرایش

RED )WRED وزن دار) ویرایش

مقاله اصلی: تشخیص تصادفی زودهنگام وزن دار ازدحام

در RED وزن دار می‌توان احتمالات مختلفی برای اولویت‌های مختلف یا صف‌های مختلف تعریف کرد.^[۵]

ARED ویرایش

الگوریتم RED سازگار یا RED فعال ^[۶]، تعیین می‌کند که RED چه عکس العملی در مقابل متوسط طول صف داشته باشد. اگر متوسط طول صف حول مینیمم آستانه در نوسان باشد، تشخیص زودهنگام نیاز نیست. اما اگر متوسط طول صف نزدیک به ماکزیمم آستانه باشد، تشخیص زود هنگام بسیار محافظه کارانه عمل می‌کند. این الگوریتم نرخ احتمال را بر اساس اینکه چه مقدار از ترافیک را حذف کرده‌است تغییر می‌دهد. برای کسب اطلاعات بیشتر در رابطه با این تکنیک ها، به Srikant ا ^[۷] مراجعه نمایید.

RRED ویرایش

مقاله اصلی: تشخیص زود هنگام تصادفی قدرتمند ازدحام

الگوریتم قدرتمند تشخیص زود هنگام تصادفی ازدحام (یا Robust Random Early Detection) به منظور بهبود گذردهی TCP در برابر حمله‌های DOS به ویژه Low-rate Denial-of-Service LDoS پیشنهاد شد. تحقیقات نشان می‌دهد که الگوریتم‌های مثل RED به دلیل طول صف متغیر TCP ناشی از حمله به صورت محسوسی در معرض خطر LDoS هستند. الگوریتم RRED به صورت چشمگیری کارایی TCP را در برابر این حملات بالا می برد.

منابع ویرایش

↑ Floyd, Sally (1993). "Random Early Detection (RED) gateways for Congestion Avoidance". IEEE/ACM Transactions on Networking (به انگلیسی). Jacobson, Van. pp. 397–413. doi:10.1109/90.251892. Retrieved 2008-03-16. {{cite web}}: Unknown parameter |month= ignored (help)
↑ (2010-12-17)Gettys, Jim (2010). "RED in a Different Light" (به انگلیسی). Retrieved 2010-12-27. {{cite web}}: Unknown parameter |month= ignored (help)
↑ Jacobson, Van; Nichols, Kathy; Poduri, Kedar (1999). "RED in a Different Light" (به انگلیسی). Retrieved 1999-09-30. {{cite web}}: Check date values in: |تاریخ بازبینی= (help); Unknown parameter |month= ignored (help)
↑ «An Approach to Service Allocation in the Internet». IETF. ۲۰۱۱-۰۵-۲۷. از پارامتر ناشناخته |نام خانوادگی 1= صرف‌نظر شد (کمک); پارامتر |first1= بدون |last1= در Authors list وارد شده‌است (کمک); پارامتر |first2= بدون |last2= در Authors list وارد شده‌است (کمک)^{^{[پیوند مرده]}}
↑ Chao, H. Jonathan (2001-08-01). "Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management". IEEE/ACM Transactions on Networking (به انگلیسی). Jacobson, Van. Retrieved 2008-03-16. {{cite web}}: Check date values in: |year= / |تاریخ= mismatch (help); Unknown parameter |month= ignored (help)
↑ Floyd, Sally (2008). "Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management" (به انگلیسی). Transactions on Networking. Retrieved 2001-08-01. {{cite web}}: Unknown parameter |month= ignored (help)
↑ Srikant (2008). "The Mathematics of Internet Congestion ControlManagement" (به انگلیسی). Birkhäuser. ISBN 978-0-8176-3227-4. {{cite web}}: Unknown parameter |Rayadurgam= ignored (help)

جستارهای وابسته ویرایش

پیوند به بیرون ویرایش

RED (Random Early Detection) Queue Management. Author: Sally Floyd
Guduz – A Simple Random Early Detection (RED) Simulator
Variants of RED. Author: Hei Xiao Jun
Recent Publications in Random Early Detection (RED) schemes بایگانی‌شده در ۱۷ سپتامبر ۲۰۱۶ توسط Wayback Machine

[1] Floyd, Sally (1993). "Random Early Detection (RED) gateways for Congestion Avoidance". IEEE/ACM Transactions on Networking (به انگلیسی). Jacobson, Van. pp. 397–413. doi:10.1109/90.251892. Retrieved 2008-03-16. {{cite web}}: Unknown parameter |month= ignored (help)

[2] (2010-12-17)Gettys, Jim (2010). "RED in a Different Light" (به انگلیسی). Retrieved 2010-12-27. {{cite web}}: Unknown parameter |month= ignored (help)

[3] Jacobson, Van; Nichols, Kathy; Poduri, Kedar (1999). "RED in a Different Light" (به انگلیسی). Retrieved 1999-09-30. {{cite web}}: Check date values in: |تاریخ بازبینی= (help); Unknown parameter |month= ignored (help)

[4] «An Approach to Service Allocation in the Internet». IETF. ۲۰۱۱-۰۵-۲۷. از پارامتر ناشناخته |نام خانوادگی 1= صرف‌نظر شد (کمک); پارامتر |first1= بدون |last1= در Authors list وارد شده‌است (کمک); پارامتر |first2= بدون |last2= در Authors list وارد شده‌است (کمک)^{^{[پیوند مرده]}}

[5] Chao, H. Jonathan (2001-08-01). "Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management". IEEE/ACM Transactions on Networking (به انگلیسی). Jacobson, Van. Retrieved 2008-03-16. {{cite web}}: Check date values in: |year= / |تاریخ= mismatch (help); Unknown parameter |month= ignored (help)

[6] Floyd, Sally (2008). "Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management" (به انگلیسی). Transactions on Networking. Retrieved 2001-08-01. {{cite web}}: Unknown parameter |month= ignored (help)

[7] Srikant (2008). "The Mathematics of Internet Congestion ControlManagement" (به انگلیسی). Birkhäuser. ISBN 978-0-8176-3227-4. {{cite web}}: Unknown parameter |Rayadurgam= ignored (help)

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]