FQ-PIE(8) Linux FQ-PIE(8)

tc-fq_pie - کنترل‌کننده تناسبی انتگرالی ارتقایافته همراه با صف‌بندی جریان (FQ-PIE)

tc qdisc ... fq_pie [ limit PACKETS ] [ flows NUMBER ]
[ target TIME ] [ tupdate TIME ]
[ alpha NUMBER ] [ beta NUMBER ]
[ quantum BYTES ] [ memory_limit BYTES ]
[ ecn_prob PERCENTAGE ] [ [no]ecn ]
[ [no]bytemode ] [ [no_]dq_rate_estimator ]

الگوریتم FQ-PIE (برگرفته از Flow Queuing with Proportional Integral controller Enhanced یا صف‌بندی جریان با کنترل‌کننده تناسبی انتگرالی ارتقایافته) یک انضباط صفی است که صف‌بندی جریان را با طرح مدیریت فعال صف (AQM) الگوریتم PIE ترکیب می‌کند. FQ-PIE از تابع درهم‌سازی جنکینز (Jenkins hash function) برای رده‌بندی بسته‌های ورودی به جریان‌های گوناگون استفاده می‌کند و برای تخصیص سهمی عادلانه از پهنای باند به تمامی جریان‌های استفاده‌کننده از این qdisc به کار می‌رود. هر یک از این جریان‌ها توسط الگوریتم PIE مدیریت می‌شوند.

الگوریتم FQ-PIE از دو بخش منطقی تشکیل شده است: زمان‌بند (scheduler) که صف مورد نظر برای خروج بسته (dequeue) را انتخاب می‌کند، و مکانیسم مدیریت فعال صف PIE AQM که بر روی هر یک از صف‌ها کار می‌کند. بخش عمده کارکرد FQ-PIE مربوط به بخش زمان‌بندی است. تعامل میان زمان‌بند و الگوریتم PIE ساده و سرراست است.

در مرحله ورود به صف (enqueue)، از یک سازوکار مبتنی بر درهم‌سازی استفاده می‌شود که در آن جریان‌ها در تعدادی سطل (bucket) نگاشت می‌شوند و هر سطل صف اختصاصی خود را دارد. تعداد سطل‌ها قابل پیکربندی است و در حال حاضر در پیاده‌سازی به صورت پیش‌فرض برابر با ۱۰۲۴ است. درهم‌سازی جریان بر اساس ۵-تایی (5-tuple) شامل نشانی‌های IP مبدأ و مقصد، شماره پورت‌ها و شماره پروتکل IP انجام می‌گیرد. هنگامی که بسته با موفقیت در یک صف رده‌بندی شد، برای ورود به صف تحویل الگوریتم PIE داده می‌شود. سپس به انتهای صف انتخاب‌شده افزوده شده و شمارنده بایت صف به اندازه حجم بسته به‌روزرسانی می‌شود. اگر صف در حال حاضر فعال نباشد (یعنی در هیچ‌یک از فهرست‌های صف‌های جدید یا صف‌های قدیمی قرار نداشته باشد)، به انتهای فهرست صف‌های جدید اضافه شده و اعتبار (credits) آن با مقدار کوانتوم (quantum) پیکربندی‌شده مقداردهی اولیه می‌شود. در غیر این صورت، صف در فهرست فعلی خود باقی می‌ماند.

در مرحله خروج از صف (dequeue)، زمان‌بند ابتدا فهرست صف‌های جدید را بررسی می‌کند؛ برای صفی که در ابتدای این فهرست قرار دارد، اگر اعتبار منفی داشته باشد (یعنی پیش‌تر دست‌کم یک کوانتوم بایت از آن خارج شده باشد)، یک کوانتوم اعتبار بیشتر دریافت می‌کند، صف به انتهای فهرست صف‌های قدیمی منتقل می‌شود و این روال صف بعدی را انتخاب کرده و دوباره آغاز می‌گردد. در غیر این صورت، همان صف مجدداً برای خروج بسته انتخاب می‌شود. اگر فهرست صف‌های جدید خالی باشد، زمان‌بند به همین ترتیب در فهرست صف‌های قدیمی پیش می‌رود (بررسی اعتبارها، و یا انتخاب صف برای خروج بسته یا افزودن اعتبار و بازگرداندن صف به انتهای فهرست). پس از انتخاب صفی که باید بسته‌ای از آن خارج شود، الگوریتم PIE روی آن صف فراخوانی می‌شود.

در نهایت، اگر الگوریتم PIE بسته‌ای را بازنگرداند، آن صف باید خالی باشد و زمان‌بند یکی از دو کار زیر را انجام می‌دهد:

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

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

حداکثر ظرفیت صف بر حسب تعداد بسته‌ها است. هنگامی که صف به این حد برسد، بسته‌های ورودی دور ریخته (drop) می‌شوند. مقدار پیش‌فرض ۱۰۲۴۰ بسته است.

تعداد جریان‌هایی است که بسته‌های ورودی به آن‌ها رده‌بندی می‌شوند. به دلیل ماهیت تصادفی درهم‌سازی، ممکن است چندین جریان مختلف به یک خانه یکسان نگاشت شوند. جریان‌های جدیدتر نسبت به جریان‌های قدیمی‌تر اولویت دارند. این پارامتر تنها در زمان بارگذاری قابل تعیین است زیرا باید برای جدول درهم‌سازی حافظه تخصیص یابد. مقدار پیش‌فرض ۱۰۲۴ است.

تاخیر صف مد نظر است که الگوریتم PIE تلاش می‌کند آن را حفظ کند. مقدار پیش‌فرض تاخیر هدف ۱۵ میلی‌ثانیه (15ms) است.

بازه زمانی است که در آن احتمال دور ریختن (drop probability) سیستم محاسبه می‌شود. مقدار پیش‌فرض ۱۵ میلی‌ثانیه (15ms) است.

پارامترهای alpha و beta برای کنترل احتمال دور ریختن انتخاب می‌شوند. این مقادیر باید در بازه میان ۰ تا ۳۲ قرار داشته باشند.

پارامتر quantum بیانگر تعداد بایت‌هایی است که می‌توان پیش از تعویض به صف بعدی در طرح چرخشی کسری (Deficit Round Robin)، از یک صف خارج کرد.

حداکثر حافظه کلی مجاز برای بسته‌های تمامی جریان‌ها است. مقدار پیش‌فرض ۳۲ مگابایت (32Mb) است.

آستانه احتمال دور ریختن است که پایین‌تر از آن، بسته‌ها به جای دور انداخته شدن علامت‌گذاری ECN دریافت می‌کنند. مقدار پیش‌فرض ۱۰٪ است. تنظیم این پارامتر نیازمند فعال بودن ecn است.

این گزینه دارای همان معنا و مفهوم در pie است و می‌تواند برای علامت‌گذاری بسته‌ها به جای دور انداختن آن‌ها به کار رود. اگر ecn فعال شده باشد، می‌توان از noecn برای غیرفعال کردن آن استفاده کرد و برعکس.

برای مقیاس‌بندی احتمال دور ریختن به نسبت اندازه بسته استفاده می‌شود. bytemode برای فعال کردن حالت بایتی و nobytemode برای غیرفعال کردن آن به کار می‌رود. به صورت پیش‌فرض، bytemode غیرفعال است.

گزینه dq_rate_estimator می‌تواند برای محاسبه تاخیر صف با استفاده از قانون لیتل (Little's Law) به کار رود، و no_dq_rate_estimator می‌تواند برای محاسبه تاخیر صف با استفاده از برچسب زمان (timestamp) استفاده شود. به صورت پیش‌فرض، dq_rate_estimator غیرفعال است.

# tc qdisc add dev eth0 root fq_pie
# tc -s qdisc show dev eth0
qdisc fq_pie 8001: root refcnt 2 limit 10240p flows 1024 target 15.0ms tupdate
16.0ms alpha 2 beta 20 quantum 1514b memory_limit 32Mb ecn_prob 10
 Sent 159173586 bytes 105261 pkt (dropped 24, overlimits 0 requeues 0)
 backlog 75700b 50p requeues 0
  pkts_in 105311 overlimit 0 overmemory 0 dropped 24 ecn_mark 0
  new_flow_count 7332 new_flows_len 0 old_flows_len 4 memory_used 108800
# tc qdisc add dev eth0 root fq_pie dq_rate_estimator
# tc -s qdisc show dev eth0
qdisc fq_pie 8001: root refcnt 2 limit 10240p flows 1024 target 15.0ms tupdate
16.0ms alpha 2 beta 20 quantum 1514b memory_limit 32Mb ecn_prob 10
dq_rate_estimator
 Sent 8263620 bytes 5550 pkt (dropped 4, overlimits 0 requeues 0)
 backlog 805448b 532p requeues 0
  pkts_in 6082 overlimit 0 overmemory 0 dropped 4 ecn_mark 0
  new_flow_count 94 new_flows_len 0 old_flows_len 8 memory_used 1157632

tc(8), tc-pie(8), tc-fq_codel(8)

RFC 8033: https://tools.ietf.org/html/rfc8033

الگوریتم FQ-PIE توسط Mohit P. Tahiliani پیاده‌سازی شده است. لطفاً گزارش‌های اشکال و بازخوردها را به فهرست پستی شبکه لینوکس به نشانی <netdev@vger.kernel.org> ارسال کنید.

23 January 2020 iproute2