SFB(8) Linux SFB(8)

tc-sfb - الگوریتم انضباط صف تصادفی منصفانه آبی (Stochastic Fair Blue)

tc qdisc ... blue rehash milliseconds db milliseconds limit packets max packets target packets increment float decrement float penalty_rate packets per second penalty_burst packets

الگوریتم آبی تصادفی منصفانه (Stochastic Fair Blue یا SFB) یک qdisc بدون کلاس (classless) برای مدیریت ازدحام بر اساس تاریخچه اتلاف بسته‌ها و میزان بهره‌برداری از پیوند (link utilization) است، در حالی که هم‌زمان تلاش می‌کند مانع از تأثیر نامطلوب جریان‌های ناپاسخگو (یعنی جریان‌هایی که به علامت‌گذاری ازدحام یا دور ریخته شدن بسته‌ها واکنش نشان نمی‌دهند) بر کارایی جریان‌های پاسخگو شود. برخلاف RED، که در آن احتمال علامت‌گذاری باید به‌صورت دستی پیکربندی شود، BLUE تلاش می‌کند تا احتمال بهینه علامت‌گذاری را به‌طور خودکار تعیین کند.

الگوریتم BLUE احتمالی را نگه‌داری می‌کند که برای علامت‌گذاری یا دور انداختن بسته‌هایی که قرار است در صف قرار گیرند استفاده می‌شود. اگر صف سرریز شود، احتمال علامت‌گذاری/دور انداختن افزایش می‌یابد. اگر صف خالی شود، این احتمال کاهش می‌یابد. الگوریتم Stochastic Fair Blue (SFB) برای محافظت از جریان‌های TCP در برابر جریان‌های ناپاسخگو طراحی شده است.

این پیاده‌سازی از SFB، تعداد ۸ سطح (level) را نگه‌داری می‌کند که هر کدام شامل ۱۶ سطل (bin) برای حسابرسی و آمارگیری است. هر جریان با استفاده از یک مقدار هش اختصاصی در هر سطح، به یک سطل از هر سطح نگاشت می‌شود.

هر سطل یک احتمال علامت‌گذاری را نگه‌داری می‌کند که بر اساس میزان اشغال سطل افزایش یا کاهش می‌یابد. اگر تعداد بسته‌ها از گنجایش آن سطل فراتر رود، احتمال علامت‌گذاری افزایش می‌یابد. اگر تعداد بسته‌ها به صفر برسد، این احتمال کاهش می‌یابد.

احتمال علامت‌گذاری بر پایه کمترین مقدار میان تمامی سطل‌هایی محاسبه می‌شود که یک جریان به آن‌ها نگاشت شده است؛ بنابراین، هنگامی که جریانی به علامت‌گذاری یا دور انداختن تدریجی بسته‌ها پاسخ ندهد، احتمال علامت‌گذاری آن به‌سرعت به مقدار ۱ می‌رسد.

در این حالت، نرخ ارسال آن جریان به penalty_rate بسته در ثانیه محدود (rate-limited) می‌شود.

به دلیل ماهیت عملکرد SFB، ممکن است جریان‌های پاسخگو تمامی سطل‌های خود را با یک جریان ناپاسخگو به اشتراک بگذارند، که باعث می‌شود جریان پاسخگو به‌اشتباه به‌عنوان جریان ناپاسخگو شناسایی شود.

احتمال شناسایی اشتباه یک جریان پاسخگو به تعداد جریان‌های ناپاسخگو (M) بستگی دارد و طبق رابطه زیر محاسبه می‌شود:

(1 - (1 - (1 / 16.0)) ** M) ** 8

بنابراین برای نمونه با ۱۰ جریان ناپاسخگو، تقریباً ۰٫۲٪ از جریان‌های پاسخگو به‌اشتباه شناسایی خواهند شد.

برای کاهش این اثر نامطلوب، SFB به‌صورت دوره‌ای عمل درهم‌سازی مجدد (re-hashing) را انجام می‌دهد تا از تداوم دسته‌بندی اشتباه در بازه‌های زمانی طولانی جلوگیری کند.

روش درهم‌سازی پیش‌فرض، در صورت امکان از آدرس‌های IP مبدأ و مقصد و شماره درگاه‌ها (port) استفاده می‌کند و از پروتکل‌های تونل‌زنی نیز پشتیبانی می‌نماید. همچنین امکان پیکربندی یک دسته‌بند (classifier) خارجی نیز وجود دارد.

بازه زمانی بر حسب میلی‌ثانیه که طی آن آشفتگی صف (queue perturbation) رخ می‌دهد تا از شناسایی نادرست و طولانی‌مدت جریان‌های پاسخگوی نامرتبط به عنوان بخشی از یک جریان ناپاسخگو جلوگیری شود. مقدار پیش‌فرض ۱۰ دقیقه است.
مدت‌زمان انتظار گرم‌سازی بافر مضاعف (Double buffering warmup wait time) بر حسب میلی‌ثانیه. برای جلوگیری از بین رفتن تاریخچه احتمالات در زمان اجرای درهم‌سازی مجدد (rehashing)، این پیاده‌سازی مجموعه دومی از سطوح/سطل‌ها را مطابق بخش ۴٫۴ مرجع SFB نگه‌داری می‌کند. در حالی که یک مجموعه برای مدیریت صف استفاده می‌شود، مجموعه دوم گرم‌سازی می‌شود: هر زمان که جریانی به عنوان ناپاسخگو تشخیص داده شود، احتمالات علامت‌گذاری در مجموعه دوم به‌روزرسانی می‌شوند. هنگامی که درهم‌سازی مجدد رخ می‌دهد، این سطل‌ها برای مدیریت صف به کار گرفته می‌شوند و تمام جریان‌های ناپاسخگو می‌توانند بلافاصله با محدودیت نرخ مواجه شوند. این مقدار مشخص می‌کند که چه مدت‌زمانی باید سپری شود تا گرم‌سازی مجموعه دوم آغاز گردد. مقدار پیش‌فرض یک دقیقه است و باید کمتر از مقدار rehash باشد.
محدودیت قطعی (Hard limit) روی اندازه واقعی (نه میانگین) کل صف بر حسب بسته. بسته‌های بیشتر دور ریخته می‌شوند. مقدار پیش‌فرض برابر با طول صف ارسال رابط شبکه‌ای است که qdisc به آن متصل شده است.
حداکثر طول صف یک سطل بر حسب بسته، پیش از آن‌که بسته‌ها دور ریخته شوند. این مقدار باید اندکی بزرگ‌تر از target باشد، اما نباید به مقادیری بیش از ۱٫۵ برابر مقدار target تنظیم شود. مقدار پیش‌فرض ۲۵ است.
طول میانگین مورد نظر برای سطل. اگر طول صف سطل به این مقدار برسد، احتمال علامت‌گذاری به میزان increment افزایش می‌یابد. مقدار پیش‌فرض به تنظیمات max بستگی دارد؛ با تنظیم max روی ۲۵، مقدار target به‌طور پیش‌فرض ۲۰ خواهد بود.
مقداری که برای افزایش احتمال علامت‌گذاری در زمان پر شدن بیش از حد صف استفاده می‌شود. باید بین ۰ و ۱٫۰ باشد. مقدار پیش‌فرض ۰٫۰۰۰۵۰ است.
مقداری که برای کاهش احتمال علامت‌گذاری در زمان خالی شدن صف استفاده می‌شود. باید بین ۰ و ۱٫۰ باشد. مقدار پیش‌فرض ۰٫۰۰۰۰۵ است.
حداکثر تعداد بسته‌های متعلق به جریان‌های شناسایی‌شده به‌عنوان ناپاسخگو که می‌توانند در هر ثانیه در صف قرار گیرند. با رسیدن به این تعداد، بسته‌های بعدی این جریان‌های ناپاسخگو دور ریخته می‌شوند. این مقدار را کسری معقول از پهنای باند آپ‌لینک خود تنظیم کنید؛ مقدار پیش‌فرض ۱۰ بسته احتمالاً بسیار کم است.
تعداد بسته‌هایی که یک جریان مجاز است از نرخ جریمه (penalty rate) فراتر رود پیش از آن‌که دور ریختن بسته‌ها آغاز شود. مقدار پیش‌فرض ۲۰ بسته است.

این qdisc آمارهای اضافی را از طریق خروجی tc -s qdisc ارائه می‌دهد. این آمارها عبارتند از:

تعداد بسته‌های دور ریخته‌شده پیش از آن‌که صف اختصاصی جریان پر شود.
تعداد بسته‌های دور ریخته‌شده به دلیل اعمال محدودیت نرخ (rate-limiting). اگر این مقدار بالا باشد، جریان‌های ناپاسخگوی زیادی از طریق sfb ارسال می‌شوند. در چنین شرایطی، بهتر است sfb درون یک qdisc دارای کلاس (classful) تعبیه شود تا بتوان چنین جریان‌هایی را با یک qdisc شکل‌دهی ترافیک (shaping) دیگر بهتر کنترل کرد.
تعداد بسته‌های دور ریخته‌شده به دلیل پر بودن صف اختصاصی جریان. مقدار بالای bucketdrop ممکن است نشان‌دهنده تعداد زیاد جریان‌های کوتاه‌مدت و تهاجمی باشد.
تعداد بسته‌های دور ریخته‌شده به دلیل رسیدن به حد آستانه (limit). این مقدار در حالت عادی باید ۰ باشد.
تعداد بسته‌های علامت‌گذاری‌شده با ECN.
طول طولانی‌ترین صف (مجازی) اختصاصی جریان در حال حاضر.
حداکثر احتمال دور ریختن بسته برای یک جریان. مقدار ۱ نشان می‌دهد که برخی جریان‌ها به عنوان ناپاسخگو شناسایی شده‌اند.

الگوریتم SFB به‌طور خودکار استفاده از اعلان صریح ازدحام (ECN) را فعال می‌کند. همچنین این پیاده‌سازی SFB، خود بسته‌ها را در صف قرار نمی‌دهد؛ بلکه بسته‌ها به صف درونی (inner qdisc که پیش‌فرض آن pfifo است) فرستاده می‌شوند. از آنجا که sfb وضعیت‌های صف مجازی را نگه‌داری می‌کند، qdisc درونی نباید بسته‌ای را که پیش‌تر در صف قرار گرفته است دور بیندازد. علاوه بر این، اگر صف یک سطل نرخ علامت‌گذاری بسیار بالایی داشته باشد، این پیاده‌سازی به جای علامت‌گذاری، شروع به دور ریختن بسته‌ها می‌کند؛ چرا که چنین وضعیتی نشان‌دهنده ازدحام شدید یا وجود یک جریان ناپاسخگو است.

برای اتصال به رابط شبکه $DEV با استفاده از گزینه‌های پیش‌فرض:

# tc qdisc add dev $DEV handle 1: root sfb

استفاده از آدرس‌های IP مقصد به‌تنهایی برای تخصیص بسته‌ها به سطل‌ها، با ایجاد آشفتگی در نتایج درهم‌سازی هر ۱۰ دقیقه:

# tc filter add dev $DEV parent 1: handle 1 flow hash keys dst perturb 600

tc(8), tc-red(8), tc-sfq(8)

W. Feng, D. Kandlur, D. Saha, K. Shin, BLUE: A New Class of Active Queue Management Algorithms, U. Michigan CSE-TR-387-99, April 1999.

این پیاده‌سازی SFB توسط Juliusz Chroboczek و Eric Dumazet ارائه شده است.

August 2011 iproute2