كوديل

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

CoDel ( اختصار لـ Controlled Delay ، وتُنطق " كودل ") هي خوارزمية لإدارة الطوابير النشطة (AQM) في توجيه الشبكات ، طوّرها فان جاكوبسون وكاثلين نيكولز ونُشرت في RFC8289. [ 1 ] صُممت هذه الخوارزمية للتغلب على مشكلة ازدحام المخزن المؤقت في أجهزة الشبكات ، مثل أجهزة التوجيه ، وذلك بوضع حدود للتأخير الذي تواجهه حزم البيانات أثناء مرورها عبر هذه المخازن . تهدف CoDel إلى تحسين الأداء العام لخوارزمية الكشف المبكر العشوائي (RED) من خلال معالجة بعض المفاهيم الخاطئة الأساسية عنها، كما لاحظها جاكوبسون، بالإضافة إلى كونها أسهل في الإدارة.

في عام ٢٠١٢، قام ديف تاهت وإريك دومازيت بكتابة تطبيق لـ CoDel لنواة لينكس ، وحصل على ترخيص مزدوج بموجب رخصة جنو العمومية العامة ورخصة BSD ثلاثية البنود . يُطلق على تحسين دومازيت لـ CoDel اسم FQ-CoDel ، اختصارًا لـ "Fair/Flow Queue CoDel". وقد اعتُمد لأول مرة كحل قياسي لإدارة قوائم الانتظار التلقائية وجدولة الحزم في عام ٢٠١٤ في إصدار OpenWrt 14.07 المسمى "Barrier Breaker". ومنذ ذلك الحين، انتقل كل من CoDel وFQ-CoDel إلى العديد من المشاريع اللاحقة مثل Tomato و dd-wrt و OPNsense وميزة "Smart Queues" من Ubiquiti .

نظرية

يعتمد CoDel على ملاحظات سلوك الحزم في الشبكات ذات التبديل الحزمي تحت تأثير مخازن البيانات المؤقتة . تتناول بعض هذه الملاحظات الطبيعة الأساسية للطوابير وأسباب تضخم المخزن المؤقت ، بينما تتعلق ملاحظات أخرى بنقاط ضعف خوارزميات إدارة الطوابير البديلة. طُوّر CoDel كمحاولة لمعالجة مشكلة تضخم المخزن المؤقت. [ 2 ]

ازدحام المخزن المؤقت

يتباطأ تدفق الحزم أثناء انتقالها عبر وصلة الشبكة بين شبكة سريعة وأخرى بطيئة، خاصةً في بداية جلسة TCP ، حيث يحدث تدفق مفاجئ للحزم وقد لا تتمكن الشبكة البطيئة من استيعابه بالسرعة الكافية. وُجدت المخازن المؤقتة لتخفيف هذه المشكلة من خلال توفير مكان للشبكة السريعة لتخزين الحزم التي ستقرأها الشبكة البطيئة بوتيرتها الخاصة. [ 3 ] بعبارة أخرى، تعمل المخازن المؤقتة كممتصات للصدمات لتحويل تدفقات الحزم المفاجئة إلى تدفقات سلسة وثابتة. مع ذلك، فإن سعة المخزن المؤقت محدودة. يُصمم المخزن المؤقت المثالي بحيث يستطيع التعامل مع تدفق مفاجئ للاتصالات ومطابقة سرعة هذا التدفق مع سرعة الشبكة البطيئة. في الوضع الأمثل، يتميز امتصاص الصدمات بتأخير مؤقت للحزم في المخزن المؤقت أثناء تدفق الإرسال، وبعد ذلك يختفي التأخير بسرعة وتصل الشبكة إلى حالة توازن في عرض الحزم ومعالجتها. [ 3 ]

تعتمد خوارزمية التحكم في ازدحام بروتوكول TCP على فقدان الحزم لتحديد عرض النطاق الترددي المتاح بين جهازين متصلين. تعمل هذه الخوارزمية على تسريع نقل البيانات حتى تبدأ الحزم بالفقدان، ثم تُبطئ معدل الإرسال. من الناحية المثالية، تستمر الخوارزمية في التسريع والإبطاء حتى تصل إلى حالة التوازن مع سرعة الرابط. لكي تعمل هذه الخوارزمية، يجب أن يحدث فقدان الحزم في الوقت المناسب حتى تتمكن من اختيار سرعة نقل مناسبة بشكل فوري. عند تخزين الحزم في مخزن مؤقت كبير جدًا، ستصل الحزم إلى وجهتها ولكن بزمن استجابة أطول ، ولكن دون فقدان أي حزم، وبالتالي لن يُبطئ بروتوكول TCP. في هذه الحالة، قد يقرر بروتوكول TCP أن مسار الاتصال قد تغير، فيُعيد البحث عن حالة توازن جديدة. [ 4 ] [ 5 ]

يُطلق على وجود مخزن مؤقت كبير وممتلئ باستمرار، مما يؤدي إلى زيادة تأخيرات الإرسال وتقليل التفاعل، خاصةً عند النظر إلى عمليتي إرسال أو أكثر متزامنتين عبر نفس القناة، اسم "تضخم المخزن المؤقت". وقد ينتهي الأمر أيضًا بعدم استخدام عرض النطاق الترددي المتاح للقناة، حيث قد لا يتم الوصول إلى بعض الوجهات السريعة بسبب امتلاء المخازن المؤقتة بالبيانات التي تنتظر التسليم إلى الوجهات البطيئة.

طوابير جيدة وطوابير سيئة

يميز CoDel بين نوعين من قوائم الانتظار: [ 3 ] [ 6 ] قائمة الانتظار الجيدة هي التي لا تعاني من تضخم المخزن المؤقت. لا تتسبب تدفقات البيانات المفاجئة إلا في زيادة مؤقتة في تأخير قائمة الانتظار، مما يحقق أقصى استفادة من وصلة الشبكة. أما قائمة الانتظار السيئة فتعاني من تضخم المخزن المؤقت، حيث تتسبب تدفقات البيانات المفاجئة في امتلاء المخزن المؤقت وبقائه ممتلئًا، مما يؤدي إلى انخفاض الاستخدام وارتفاع مستمر في تأخير المخزن المؤقت. ولكي يكون حل إدارة قوائم الانتظار النشطة (AQM) فعالًا ضد تضخم المخزن المؤقت، يجب أن يكون قادرًا على رصد حدوثه والاستجابة له من خلال تطبيق تدابير مضادة فعالة.

أكد فان جاكوبسون في عام 2006 أن الخوارزميات الحالية تستخدم وسائل غير صحيحة للتعرف على امتلاء المخزن المؤقت. [ 5 ] تقيس خوارزميات مثل RED متوسط ​​طول قائمة الانتظار، وتعتبرها حالة امتلاء للمخزن المؤقت إذا زاد المتوسط ​​بشكل كبير. أوضح جاكوبسون في عام 2006 أن هذا القياس ليس مقياسًا جيدًا، حيث يرتفع متوسط ​​طول قائمة الانتظار بشكل حاد في حالة حدوث تدفق مفاجئ للبيانات. يمكن أن تتلاشى قائمة الانتظار بسرعة (قائمة انتظار جيدة) أو تصبح قائمة انتظار ثابتة (قائمة انتظار سيئة). يمكن أن تتسبب عوامل أخرى في حركة مرور الشبكة أيضًا في نتائج إيجابية أو سلبية خاطئة، مما يؤدي إلى نشر تدابير مضادة دون داعٍ. اقترح جاكوبسون أن متوسط ​​طول قائمة الانتظار لا يحتوي في الواقع على أي معلومات على الإطلاق حول طلب الحزم أو حمل الشبكة. [ 3 ] [ 5 ] واقترح أن يكون المقياس الأفضل هو الحد الأدنى لطول قائمة الانتظار خلال نافذة زمنية متغيرة. [ 3 ]

الخوارزمية

استنادًا إلى فكرة جاكوبسون من عام 2006، طُوِّرت خوارزمية CoDel لإدارة قوائم الانتظار مع التحكم في الحد الأدنى للتأخير الذي تواجهه الحزم في نافذة المخزن المؤقت. والهدف هو إبقاء هذا الحد الأدنى للتأخير أقل من 5 مللي ثانية. إذا ارتفع الحد الأدنى للتأخير إلى قيمة عالية جدًا، تُحذف الحزم من قائمة الانتظار حتى ينخفض ​​التأخير إلى ما دون الحد الأقصى. [ 3 ] ويذكر نيكولز وجاكوبسون عدة مزايا لاستخدام هذا المقياس فقط: [ 3 ]

  • لا يتطلب CoDel أي معلمات. ومن نقاط ضعف خوارزمية RED (بحسب جاكوبسون) صعوبة تهيئتها، خاصة في بيئة ذات معدلات ربط ديناميكية.
  • يتعامل CoDel مع قوائم الانتظار الجيدة والسيئة بشكل مختلف. تتميز قوائم الانتظار الجيدة بانخفاض التأخيرات بطبيعتها، لذا يمكن لخوارزمية الإدارة تجاهلها، بينما تخضع قوائم الانتظار السيئة لتدخل الإدارة من خلال إسقاط الحزم.
  • يعتمد CoDel على معلمة يتم تحديدها محليًا بالكامل؛ وهي مستقلة عن تأخيرات الرحلة ذهابًا وإيابًا، ومعدلات الربط، وأحمال حركة المرور، وعوامل أخرى لا يمكن التحكم فيها أو التنبؤ بها بواسطة المخزن المؤقت المحلي.
  • لا يمكن تحديد الحد الأدنى للتأخير المحلي إلا عندما تغادر حزمة البيانات المخزن المؤقت، لذلك لا حاجة إلى تأخير إضافي لتشغيل قائمة الانتظار لجمع الإحصائيات لإدارة قائمة الانتظار.
  • تتكيف CoDel مع معدلات الربط المتغيرة ديناميكيًا دون أي تأثير سلبي على الاستخدام.
  • يُعد تطبيق CoDel بسيطًا نسبيًا، وبالتالي يمكن أن يغطي نطاقًا واسعًا من أجهزة التوجيه المنزلية منخفضة التكلفة إلى حلول التوجيه عالية الجودة.

لا يقوم CoDel بأي إجراء لإدارة المخزن المؤقت إذا كان الحد الأدنى للتأخير في نافذة المخزن المؤقت أقل من القيمة القصوى المسموح بها. كما أنه لا يقوم بأي إجراء إذا كان المخزن المؤقت فارغًا نسبيًا (إذا كان حجم البيانات فيه أقل من حجم وحدة النقل القصوى MTU ). [ 3 ] إذا لم تتحقق هذه الشروط، فإن CoDel يقوم بإسقاط الحزم بشكل احتمالي. [ 3 ]

تُحسب الخوارزمية بشكل مستقل عند كل قفزة في الشبكة . تعمل الخوارزمية على مدى فترة زمنية ، تبدأ بـ 100 مللي ثانية. يُرصد تأخير انتظار كل حزمة خلال القفزة. عند إخراج كل حزمة من قائمة الانتظار لإعادة توجيهها ، يُحسب تأخير الانتظار (مدة انتظار الحزمة في قائمة الانتظار). يُخزن أقل تأخير انتظار خلال الفترة الزمنية. عند إخراج آخر حزمة من قائمة الانتظار، إذا كان أقل تأخير انتظار خلال الفترة الزمنية أكبر من 5 مللي ثانية، تُسقط هذه الحزمة ويُقصر الفاصل الزمني المستخدم لمجموعة الحزم التالية. أما إذا كان أقل تأخير انتظار خلال الفترة الزمنية أقل من 5 مللي ثانية، تُعاد توجيه الحزمة ويُعاد ضبط الفاصل الزمني إلى 100 مللي ثانية.

عند تقصير الفاصل الزمني، يتم ذلك وفقًا للجذر التربيعي العكسي لعدد الفترات الزمنية المتتالية التي تم فيها إسقاط الحزم بسبب تأخير الانتظار المفرط. تسلسل الفترات الزمنية هو100{\displaystyle 100}،1002{\displaystyle {100 \over {\sqrt {2}}}}،1003{\displaystyle {100 \over {\sqrt {3}}}}،1004{\displaystyle {100 \over {\sqrt {4}}}}،1005{\displaystyle {100 \over {\sqrt {5}}}}...

نتائج المحاكاة

تم اختبار CoDel في اختبارات محاكاة أجراها نيكولز وجاكوبسون، عند قيم MTU ومعدلات ربط مختلفة، بالإضافة إلى اختلافات أخرى في الظروف. وبشكل عام، تشير النتائج إلى ما يلي: [ 3 ] [ 7 ]

  • بالمقارنة مع تقنية RED، تحافظ تقنية CoDel على تأخير الحزم أقرب إلى القيمة المستهدفة عبر نطاق عرض النطاق الترددي الكامل (من 3 إلى 100  ميجابت/ثانية). وتُظهر قياسات استخدام الوصلة باستمرار استخدامًا يقارب 100% من عرض النطاق الترددي للوصلة.
  • عند قيم MTU المنخفضة، تكون تأخيرات الحزم أقل منها عند قيم MTU المرتفعة. تؤدي قيم MTU المرتفعة إلى استخدام جيد للرابط، بينما تؤدي قيم MTU المنخفضة إلى استخدام جيد للرابط عند عرض نطاق ترددي منخفض، ويتدهور الاستخدام إلى متوسط ​​عند عرض نطاق ترددي مرتفع.

وقد تم إجراء المحاكاة أيضًا بواسطة جريج وايت وجوي بادن في شركة CableLabs . [ 8 ]

تطبيق

تم إنجاز تطبيق كامل لـ CoDel في مايو 2012، وأُتيح كبرنامج مفتوح المصدر . [ 3 ] تم تنفيذه ضمن نواة لينكس (بدءًا من الإصدار الرئيسي 3.5). [ 9 ] قام ديف تاهت بنقل CoDel إلى نواة لينكس 3.3 لمشروع CeroWrt ، الذي يُعنى، من بين أمور أخرى، بمشكلة تضخم المخزن المؤقت، [ 10 ] حيث خضع لاختبارات شاملة. بدأ CoDel بالظهور كخيار في بعض منصات إدارة النطاق الترددي الاحتكارية/الجاهزة للاستخدام في عام 2013. [ 11 ] تم دمج CoDel في فرعي الكود 11.x [ 12 ] و10.x [ 13 ] في FreeBSD في عام 2016. [ 14 ] يتم توزيع تطبيق له مع OpenBSD منذ الإصدار 6.2. [ 15 ]

الخوارزميات المشتقة

يُضيف بروتوكول Fair/Flow Queue CoDel (FQ-CoDel؛ fq_codel في نظام لينكس) ميزة إدارة تدفق البيانات إلى بروتوكول CoDel، مما يُتيح له التمييز بين الاتصالات المتزامنة المتعددة والعمل بكفاءة. ويُعطي هذا البروتوكول الأولوية للحزمة الأولى في كل تدفق، مما يسمح للتدفقات الصغيرة بالبدء والانتهاء بسرعة، وبالتالي الاستخدام الأمثل لموارد الشبكة. ويوصي فان جاكوبسون، أحد مُطوري CoDel، باستخدام fq_codel بدلاً من codel حيثما كان ذلك مُتاحًا. [ 16 ] نُشر بروتوكول FQ-CoDel في RFC8290. وقد كتبه كلٌ من تي. هويلاند-يورجنسن، وبي. ماكيني، ودي. تاهت، وج. جيتيس، وإي. دومازيت، وجميعهم أعضاء في مشروع "bufferbloat". [ 17 ]

تُعدّ خوارزمية "التطبيقات المشتركة المُحسّنة" (CAKE؛ sch_cake في نظام لينكس) مُنظِّمًا مُدمجًا لحركة البيانات وخوارزمية إدارة الازدحام التلقائي (AQM)، وقد طُرحت من قِبل مشروع bufferbloat عام 2018. وهي مبنية على خبرة استخدام fq_codel مع مُنظِّم حركة البيانات HTB (Hierarchy Token Bucket) . وتُحسِّن هذه الخوارزمية من أداء تطبيق htb+fq_codel في لينكس من خلال تقليل تصادمات التجزئة بين التدفقات، وتقليل استهلاك وحدة المعالجة المركزية في تنظيم حركة البيانات، بالإضافة إلى بعض التحسينات الأخرى. [ 18 ]

في عام ٢٠٢٢، استعرض ديف تاهت حالة تطبيقات fq_codel وsch_cake في بيئات التشغيل الفعلية. ووجد أنه على الرغم من تحوّل العديد من الأنظمة إلى أحدهما كبروتوكول إدارة الازدحام التلقائي الافتراضي، إلا أن العديد من التطبيقات تُظهر انحرافات مشكوك فيها عن المعيار. فعلى سبيل المثال، يتمتع تطبيق أبل لـ fq_codel (الافتراضي في نظام iOS) بعدد كبير جدًا من المستخدمين، ولكنه يفتقر إلى مكون "codel". كما أشار تاهت إلى النقص العام في تفريغ موارد الأجهزة، وهو ما ازداد أهميةً مع ازدياد حركة مرور الشبكة نتيجةً لجائحة كوفيد-١٩ . [ ١٩ ]

انظر أيضاً

مراجع

  1. ↑ نيكولز، ك .؛ جاكوبسون، ف .؛ ماكجريجور، أ.؛ إيينجار، ج. (يناير 2018). إدارة الطوابير النشطة ذات التأخير المُتحكم به . IETF . doi : 10.17487/RFC8289 . RFC 8289 .
  2. ↑ جو بروكماير (8 مايو 2012). "خبر سار لحل مشكلة تضخم المخزن المؤقت: كودل يقدم حلاً بدون أزرار" . ريد رايت ويب . مؤرشف من الأصل في 12 يوليو 2012. تم الاطلاع عليه في 16 أغسطس 2012 .
  3. 1 2 3 4 5 6 7 8 9 10 11 نيكولز، كاثلين ؛ جاكوبسون، فان (6 مايو 2012). "التحكم في تأخير قائمة الانتظار" . مجلة ACM Queue . 55 (7). منشورات ACM: 42-50 . doi : 10.1145/2209249.2209264 . S2CID 381738. تاريخ الاسترجاع: 12 أغسطس 2012 . 
  4. ↑ جاكوبسون، فان؛ كاريلز، إم جيه (1988). "تجنب الازدحام والتحكم فيه" (ملف PDF) . مجلة ACM SIGCOMM لمراجعة اتصالات الحاسوب . 18 (4): 314-329 . doi : 10.1145/52325.52356 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 22-06-2004.
  5. 1 2 3 جاكوبسون، فان (2006). "حديثٌ عن الطوابير. محاضرة أُلقيت في مختبرات لينكولن التابعة لمعهد ماساتشوستس للتكنولوجيا، ليكسينغتون، ماساتشوستس" (ملف PDF) . تم الاطلاع عليه بتاريخ 12 أغسطس 2012 .
  6. ^ إيلجيتش فان بيجنوم (2012/05/10). "يمكن لإدارة المخزن المؤقت لـ CoDel حل مشكلة اختناقات المخزن المؤقت للإنترنت" . آرس تكنيكا . تم الاسترجاع 2012/08/16 .
  7. ↑ نيكولز، كاثلين (يوليو 2012). "إدارة قائمة الانتظار النشطة بتقنية التأخير المُتحكم به (CoDel)" . شركة بولير. مؤرشف من الأصل في 22 أغسطس 2012. تم الاطلاع عليه في 12 أغسطس 2012 .
  8. ↑ غريغ وايت؛ جوي بادن (نوفمبر 2012). "دراسة أولية لتقنية Codel AQM في شبكة Docsis" (ملف PDF) . cablelabs.com . تاريخ الاسترجاع: 14 يونيو 2015 .
  9. ↑ جيتيس، جيم (22 مايو 2012). "إنجاز هام: CoDel متوفر في لينكس!" . خواطر جيتيس . تم الاطلاع عليه بتاريخ 12 أغسطس 2012 .
  10. ↑ "Cerowrt - نظرة عامة" . Bufferbloat . تم الاسترجاع في 24 يناير 2014 .
  11. ↑ "سجل تغييرات Procera Packetlogic" . proceranetworks.com . تم الاطلاع عليه بتاريخ 24-07-2013 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )
  12. ↑ truckman (2016-05-26). "استيراد Dummynet AQM الإصدار 0.2.1 (CoDel، FQ-CoDel، PIE وFQ-PIE)" .
  13. ↑ truckman (2016-06-10). "MFC Import Dummynet AQM الإصدار 0.2.1 (CoDel, FQ-CoDel, PIE و FQ-PIE)" .
  14. ↑ السعدي، رسول؛ أرميتاج، غرينفيل. "تطبيق AQM في FreeBSD" .
  15. ↑ "OpenBSD 6.2" . تم الاطلاع عليه بتاريخ 13 أكتوبر 2017 .
  16. ↑ "مقارنة أداء Codel و FQ Codel - Bufferbloat.net" . www.bufferbloat.net .
  17. ↑ تي. هويلاند-يورغنسن؛ بي. ماكيني؛ جيه. جيتيس؛ إي. دومازيت (يناير 2018). مُجدول حزم CoDel لقائمة انتظار التدفق وخوارزمية إدارة قائمة الانتظار النشطة . فريق عمل هندسة الإنترنت . doi : 10.17487/RFC8290 . ISSN 2070-1721 . RFC 8290 . تجريبي.
  18. ↑ "Cake - Bufferbloat.net" . www.bufferbloat.net .
  19. ↑ ديف تاهت (23 أبريل 2022). "حالة fq_codel و sch_cake عالميًا" . CeroWRT .