RED(8) Linux RED(8)

tc-red - الگوریتم تشخیص زودهنگام تصادفی برای مدیریت صف

tc qdisc ... red limit bytes [ min bytes ] [ max bytes ] avpkt bytes [ burst packets ] [ ecn ] [ harddrop ] [ nodrop ] [ bandwidth rate ] [ probability chance ] [ adaptive ] [ qevent early_drop block index ] [ qevent mark block index ]

الگوریتم تشخیص زودهنگام تصادفی (Random Early Detection یا RED) یک qdisc بدون کلاس (classless) است که اندازه صف خود را به شکلی هوشمندانه مدیریت می‌کند. صف‌های معمولی صرفاً در هنگام پر شدن، بسته‌ها را از انتهای صف دور می‌ریزند (tail drop) که ممکن است رفتار بهینه‌ای نباشد. RED نیز دور ریختن از انتها را انجام می‌دهد، اما این کار را به شیوه‌ای تدریجی‌تر پیش می‌برد.

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

این روش مزایای متعددی نسبت به دور ریختن ساده از انتها دارد، در حالی که بار پردازشی سنگینی نیز تحمیل نمی‌کند. این سازوکار از ارسال‌های مجدد همگام (synchronous retransmits) پس از یک فوران یا جهش ناگهانی ترافیک (burst) که خود موجب ارسال‌های مجدد بعدی می‌شوند، جلوگیری می‌کند.

هدف این است که اندازه صف در حد کمی حفظ شود؛ این امر برای تعاملی بودن شبکه مفید است و همزمان از اختلال در ترافیک TCP/IP بر اثر دور انداختن‌های ناگهانی و بسیار زیاد پس از یک جهش ترافیکی جلوگیری می‌کند.

بسته به اینکه آیا ECN پیکربندی شده است یا خیر، علامت‌گذاری می‌تواند به معنای دور انداختن بسته یا صرفاً نشانه‌گذاری بسته به عنوان بیش‌ازحد مجاز (overlimit) باشد.

میانگین اندازه صف برای تعیین احتمال علامت‌گذاری استفاده می‌شود. این مقدار با استفاده از میانگین متحرک وزن‌دار نمایی (EWMA - Exponential Weighted Moving Average) محاسبه می‌شود که می‌تواند حساسیت کمتر یا بیشتری نسبت به جهش‌های ترافیکی داشته باشد.

هنگامی که میانگین اندازه صف کمتر از min بایت باشد، هیچ بسته‌ای هرگز علامت‌گذاری نمی‌شود. زمانی که از min فراتر رود، احتمال این کار به صورت خطی تا probability افزایش می‌یابد، تا زمانی که میانگین اندازه صف به max بایت برسد. از آنجا که probability معمولاً روی ۱۰۰٪ تنظیم نمی‌شود، ممکن است اندازه واقعی صف از max بایت نیز فراتر رود؛ بنابراین پارامتر limit برای تعیین یک بیشینه قطعی (سقف سخت) برای اندازه صف در نظر گرفته شده است.

میانگین اندازه صف که در آن علامت‌گذاری بسته‌ها ممکن می‌شود. مقدار پیش‌فرض برابر با max /3 است.
در این میانگین اندازه صف، احتمال علامت‌گذاری به بیشترین مقدار می‌رسد. برای جلوگیری از ارسال‌های مجدد همگام، این مقدار باید حداقل دو برابر min باشد، و برای مقادیر پایینِ min باید بیشتر در نظر گرفته شود. مقدار پیش‌فرض برابر با limit /4 است.
بیشینه احتمال علامت‌گذاری، که به صورت یک عدد اعشاری از 0.0 تا 1.0 مشخص می‌شود. مقادیر پیشنهادی 0.01 یا 0.02 (به ترتیب ۱ یا ۲ درصد) هستند. مقدار پیش‌فرض: 0.02
محدودیت سخت و قطعی بر روی اندازه واقعی (نه میانگین) صف بر حسب بایت. بسته‌های بعدی دور ریخته می‌شوند. باید بیشتر از max+burst تنظیم شود. توصیه می‌شود این مقدار چند برابر بیشتر از max تعیین گردد.
برای تعیین سرعت اثرگذاری اندازه واقعی صف بر میانگین اندازه صف استفاده می‌شود. مقادیر بزرگ‌تر محاسبه را کندتر و ملایم‌تر می‌کنند و امکان جهش‌های طولانی‌تری از ترافیک را پیش از شروع علامت‌گذاری فراهم می‌سازند. آزمایش‌های عملی از این دستورالعمل پشتیبانی می‌کنند: (min+min+max)/(3*avpkt).
بر حسب بایت مشخص می‌شود. همراه با burst برای تعیین ثابت زمانی در محاسبات میانگین اندازه صف استفاده می‌شود. مقدار 1000 یک مقدار مناسب است.
این نرخ برای محاسبه میانگین اندازه صف پس از مدتی بیکاری (idle time) خط استفاده می‌شود. باید برابر با پهنای باند رابط شبکه شما تنظیم شود. این به معنای آن نیست که RED برای شما شکل‌دهی ترافیک انجام می‌دهد! اختیاری است. مقدار پیش‌فرض: 10Mbit
همان‌طور که قبلاً اشاره شد، RED می‌تواند بسته‌ها را «علامت‌گذاری» کند یا «دور بریزد». اعلان صریح ازدحام (ECN) به RED اجازه می‌دهد به میزبان‌های راه دور اطلاع دهد که نرخ ارسال آن‌ها از پهنای باند در دسترس فراتر رفته است. میزبان‌هایی که قابلیت ECN ندارند، تنها با دور انداختن بسته می‌توانند مطلع شوند. اگر این پارامتر مشخص شود، بسته‌هایی که نشان می‌دهند میزبان آن‌ها از ECN پشتیبانی می‌کند، فقط علامت‌گذاری شده و دور ریخته نمی‌شوند، مگر اینکه اندازه صف به limit بایت برسد. استفاده از آن توصیه می‌شود.
اگر میانگین اندازه صف جریان از max بایت فراتر رود، این پارامتر به‌جای علامت‌گذاری ecn، دور انداختن بسته را اجباری می‌کند.
با این پارامتر، ترافیکی که باید علامت‌گذاری شود اما قابلیت ECN ندارد، در صف قرار می‌گیرد. بدون این پارامتر، چنین ترافیکی به صورت زودهنگام دور ریخته می‌شود (early-dropped).
(افزوده شده در linux-3.3) الگوریتم RED را در حالت تطبیقی قرار می‌دهد، همان‌طور که در نشانی http://icir.org/floyd/papers/adaptiveRed.pdf شرح داده شده است. 
هدف از Adaptive RED این است که 'probability' را به مقداری پویا بین 1% و 50% تبدیل کند تا به میانگین اندازه صف هدف برسد:
(max - min) / 2

برای نکات عمومی در مورد رویدادهای صف (qevents) به tc(8) مراجعه کنید. صف‌بندی RED از qeventهای زیر پشتیبانی می‌کند:

بلوک مرتبط زمانی اجرا می‌شود که بسته‌ها به صورت زودهنگام دور ریخته شوند (early-dropped). این شامل بسته‌های غیر ECT در حالت ECN نیز می‌شود.
بلوک مرتبط زمانی اجرا می‌شود که بسته‌ها در حالت ECN علامت‌گذاری شوند. 

# tc qdisc add dev eth0 parent 1:1 handle 10: red
 limit 400000 min 30000 max 90000 avpkt 1000
 burst 55 ecn adaptive bandwidth 10Mbit

tc(8), tc-choke(8)

Floyd, S., and Jacobson, V., Random Early Detection gateways for Congestion Avoidance. http://www.aciri.org/floyd/papers/red/red.html
برخی تغییرات در الگوریتم توسط Alexey N. Kuznetsov.
Adaptive RED : http://icir.org/floyd/papers/adaptiveRed.pdf

Alexey N. Kuznetsov <kuznet@ms2.inr.ac.ru>، Alexey Makarenko <makar@phoenix.kharkov.ua>، J Hadi Salim <hadi@nortelnetworks.com>، Eric Dumazet <eric.dumazet@gmail.com>.

این صفحه راهنما توسط bert hubert <ahu@ds9a.nl> نگهداری می‌شود.

13 December 2001 iproute2