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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو
Random Early Detection algorithm en.svg

تشخیص زودهنگام تصادفی ازدحام (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 را در برابر این حملات بالا می برد.

منابع[ویرایش]

  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. Unknown parameter |month= ignored (help); More than one of |تاریخ بازبینی= and |accessdate= specified (help)
  2. (2010-12-17)Gettys, Jim (2010). "RED in a Different Light". Retrieved 2010-12-27. Unknown parameter |month= ignored (help)
  3. Jacobson, Van; Nichols, Kathy; Poduri, Kedar (1999). "RED in a Different Light". Retrieved 1999-09-30. Unknown parameter |month= ignored (help); Check date values in: |تاریخ بازبینی= (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. Unknown parameter |month= ignored (help); Check date values in: |year= / |date= mismatch (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. Unknown parameter |month= ignored (help); More than one of |تاریخ بازبینی= and |accessdate= specified (help)
  7. Srikant (2008). "The Mathematics of Internet Congestion ControlManagement". Birkhäuser. ISBN 978-0-8176-3227-4. Unknown parameter |Rayadurgam= ignored (help)

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

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