أنظمة الأرتال المستخدمة في التحكم بازدحام الشبكات الحاسوبية

يجب على كل موجّهٍ وبغض النظر عن مدى بساطة أو تعقيد بقية آلية تخصيص الموارد، أن يطبِّق بعض أنظمة الأرتال التي تحكم كيفية تخزين الرزم مؤقتًا أثناء انتظار الإرسال. ويمكن عدُّ خوارزمية الرتل على أنها تخصيص لكلٍّ من حيز النطاق التراسلي لإرسال الرزم، ومساحة التخزين المؤقت لتجاهل الرزم، كما أنها تؤثر مباشرةً على زمن الانتقال الذي تتعرض له الرزمة من خلال تحديد المدة التي تنتظرها الرزمة حتى تُرسل. يقدِّم هذا القسم خوارزميتي أرتال شائعتين هما "الداخل أولًا، يخرج أولًا first-in, first-out"، أو اختصارًا FIFO والرتل العادل fair queuing أو اختصارًا FQ، ويحدّد هذا القسم العديد من الاختلافات المُقترحة.

رتل الداخل أولا يخرج أولا FIFO

ويُطلق عليه أيضًا رتل من يأتي أولًا يُخدَّم أولًا first-come, first-served أو اختصارًا FCFS. تُعَد فكرة رتل FIFO بسيطةٌ وهي على نحو أن الرزمة الأولى الواردة إلى موجّه هي الرزمة الأولى المُرسلة، وهذا موضحٌ في القسم (أ) من الشكل الآتي، والذي يُظهر أولًا رتل FIFO مع "فتحات" لاستيعاب ما يصل إلى ثمانية رزم. بما أن مقدار مساحة المخزن المؤقت في كل موجهٍ محدودة، فإذا وصلت رزمة وكان الرتل (مساحة المخزن المؤقت) ممتلئًا، فسيتجاهل الموجّه هذه الرزمة كما هو موضحٌ في القسم (ب) من الشكل الآتي، ويجري ذلك بغض النظر عن التدفق الذي تنتمي إليه الرزمة أو مدى أهمية الرزمة، ويسمى هذا أحيانًا "إسقاط الذيل tail drop"، حيث تُسقَط الرزم التي تصل إلى نهاية رتل FIFO.

من المُلاحظ أن إسقاط الذيل ونظام FIFO هما فكرتان منفصلتان، فنظام FIFO هو نظام جدولةٍ يحدد الترتيب الذي تُرسَل الرزم به؛ أما إسقاط الذيل فهو سياسة إسقاط تحدّد الرزم التي تُسقَط. بما أن نظام FIFO وإسقاط الذيل هما أبسط أمثلةٍ لنظام جدولة وسياسة إسقاط على التوالي، فسيُنظر إليهما أحيانًا على أنهما حزمة bundle تُسمى تطبيق رتل الفانيلا vanilla queuing implementation، حيث يُشار إلى هذه الحزمة غالبًا ببساطة على أنها رتل FIFO، بينما يجب أن تُسمى بصورةٍ أدق FIFO مع إسقاط الذيل. يقدّم القسم اللاحق مثالًا لسياسة إسقاطٍ أخرى تستخدم خوارزمية أعقد من "هل يوجد مخزنٌ مؤقتٌ متاح؟"، وذلك لتحديد موعد إسقاط الرزم. يمكن استخدام سياسة الإسقاط هذه مع نظام FIFO، أو مع أنظمة جدولةٍ أعقد.

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

يختلف الرتل ذو الأولوية priority اختلافًا بسيطًا عن رتل FIFO الأساسي، حيث تتمحور فكرته حول تمييز كل رزمةٍ بأولوية ويمكن حمل العلامة mark في عنوان IP على سبيل المثال، وهذا ما سنناقشه في قسمٍ لاحق. تطبّق الموجّهات بعد ذلك عدّة أرتال FIFO، ويكون لكل رتل صنف أولوية، حيث يرسل الموجّه دائمًا الرزم من الرتل ذي الأولوية العليا إذا كان هذا الرتل غير فارغٍ قبل الانتقال إلى الرتل ذي الأولوية التالية، وتبقى الرزم مُدارةً بطريقة FIFO ضمن كل أولوية. تخرج هذه الفكرة قليلًا عن نموذج تقديم أفضل جهد، لكنها لا تذهب إلى حد تقديم ضماناتٍ لأي صنف أولوية معينة، فهي تسمح فقط للرزم ذات الأولوية العالية بالتقدم إلى الأمام.

مشكلة الرتل ذي الأولوية هي أنه يمكن أن يُبقي جميع الأرتال الأخرى منتظرةً إلى أجلٍ غير مُسمّى؛ وهذا يعني أنه طالما أن هناك رزمةً واحدةً على الأقل ذات أولوية عالية في رتلٍ ذي أولوية عالية، فلن يجري تقديم الأرتال ذات الأولوية المنخفضة، وحتى يكون هذا قابلًا للتطبيق، فيجب أن تكون هناك قيودٌ صارمة على مقدار حركة المرور ذات الأولوية العالية المُدخلة إلى الرتل، كما يجب أن يكون واضحًا مباشرةً أنه لا يمكننا السماح للمستخدمين بضبط الرزم الخاصة بهم على أولوية عالية بطريقةٍ لا يمكن التحكم فيها؛ ولهذا يجب علينا إما منعهم تمامًا أو تأمين أحد أنواع "الصد pushback" للمستخدمين. إحدى الطرق الواضحة لفعل ذلك هي استخدام الاقتصاد، حيث يمكن للشبكة أن تتقاضى رسومًا أكبر لتقديم رزم ذات أولوية عالية أكثر من الرزم ذات الأولوية المنخفضة، ولكن هناك تحديات كبيرة أمام تطبيق مثل هذا المخطط في بيئةٍ لامركزية مثل الإنترنت.

تتمثل إحدى المواقف التي يُستخدَم فيها الرتل ذو الأولوية في الإنترنت؛ في حماية الرزم الأعلى أهميةً، مثل تحديثات التوجيه الضرورية لتثبيت جداول التوجيه بعد تغيير مخطط الشبكة topology، حيث يوجد غالبًا رتلُ خاصٌ لمثل هذه الرزم الممكن تحديدها من خلال قيمة محرف الخدمات المميزة Differentiated Services Code Point والمعروفة سابقًا باسم حقل TOS في ترويسة IP، وهذه في الواقع حالةٌ بسيطة لفكرة "الخدمات المميزة".

الرتل العادل

تكمن المشكلة الرئيسية لرتل FIFO بعدم تمييزه بين مصادر حركة المرور المختلفة، أو عدم فصله للرزم وفقًا للتدفق الذي تنتمي إليه، وهذه مشكلة على مستويين مختلفين، فليس واضحًا في المستوى الأول أن تكون أية خوارزمية للتحكم في الازدحام ومُطبَّقةٌ بالكامل في المصدر قادرةً على التحكم في الازدحام بصورةٍ مناسبة وبمساعدةٍ قليلة جدًا من الموجّهات؛ أما على مستوىً آخر، فبما أن آلية التحكم في الازدحام مُطبَّقةٌ بأكملها في المصادر ولا يوفر رتل FIFO وسيلةً لمراقبة مدى التزام المصادر بهذه الآلية، فمن الممكن لمصدرٍ (تدفقٍ) سيء التصرف التقاط جزءٍ كبيرٍ من سعة الشبكة عشوائيًا. من الممكن بالتأكيد لتطبيقٍ معين عدم استخدام بروتوكول TCP في الإنترنت، وبالتالي تجاوز آلية التحكم في الازدحام من طرفٍ إلى طرف (تطبيقاتٌ مثل الاتصال الهاتفي عبر الإنترنت تفعل ذلك اليوم)، فمثل هذا التطبيق قادرٌ على إغراق موجّهات الإنترنت برزمها الخاصة، مما يتسبب في التخلص من رزم التطبيقات الأخرى.

يمثّل الرتل العادل FQ خوارزميةً مصمَّمةً لمعالجة هذه المشكلة، حيث تتمحور فكرته في الاحتفاظ برتلٍ منفصلٍ لكل تدفقٍ يعالجه الموجّه حاليًا، ويخدّم الموجه بعد ذلك هذه الأرتال في نوعٍ من جولة روبن round-robin وهو تجوُّل دَوري موضحٌ في الشكل الآتي، حيث إذا أرسل التدفق الرزم بسرعةٍ كبيرة فسيمتلئ الرتل الخاص به، وعندما يصل رتلٌ إلى طولٍ معين، فستُهمَل الرزم الإضافية المُنتمية إلى رتل هذا التدفق، وبذلك لا يمكن لمصدرٍ معين زيادة حصته عشوائيًا من سعة الشبكة على حساب التدفقات الأخرى.

لاحظ أن رتل FQ لا يتضمن إخبار الموجّه لمصادر حركة المرور بأي شيء عن حالة الموجّه أو عن الطريقة المتّبَعة لحدّ سرعة إرسال مصدرٍ معين للرزم، لكن لا يزال رتل FQ مصممًا لاستخدامه جنبًا إلى جنب مع آلية التحكم في الازدحام من طرفٍ إلى طرف، وهو يفصل ببساطة حركة المرور، بحيث لا تتداخل مصادر حركة المرور ذات السلوك السيئ مع أولئك الذين يطبقون بأمانة الخوارزمية من طرفٍ إلى طرف. يفرض رتل FQ أيضًا العدل بين مجموعة التدفقات التي تديرها خوارزميةٌ جيدة السلوك للتحكم في الازدحام.

لا يزال هناك عددٌ متواضعٌ من التفاصيل التي يتعين عليك الحصول عليها بصورةٍ صحيحة. التعقيد الرئيسي هو أنه ليست الرزم التي تُعالَج على موجهٍ بالضرورة بنفس الطول، فمن الضروري مراعاة طول الرزمة لتخصيص حيز النطاق التراسلي للرابط الصادر بطريقةٍ عادلة؛ فإذا أدار الموجّه تدفقتين على سبيل المثال، أحدهما يحتوي على رزم بطول 1000 بايت والآخر رزم بطول 500 بايت (ربما بسبب التجزئة fragmentation الصاعدة من هذا الموجّه)، فإن تطبيق جولة روبن بسيطة للرزم من رتل كل تدفقٍ ستعطي التدفق الأول ثلثي حيز النطاق التراسلي للرابط، بينما يأخذ التدفق الثاني ثلث حيز النطاق التراسلي الخاص به فقط.

ما نريده فعليًأ هو تطبيق جولة روبن على بتٍ تلو الآخر bit-by-bit round-robin، بحيث يرسل الموجّه بتًا من التدفق 1، ثم بتًا من التدفق 2، وهكذا. من الواضح أنه من غير المجدي تداخل البتات من رزمٍ مختلفة، لذلك تحاكي آلية رتل FQ هذا السلوك من خلال تحديد وقت انتهاء إرسال رزمةٍ معينة إذا أُرسِلت باستخدام آلية "جولة روبن على بتٍ تلو الآخر" ثم استخدام وقت الانتهاء هذا لتتابع رزم الإرسال.

من أجل فهم خوارزمية تقريب "جولة روبن على بتٍ تلو الآخر"، افترِض سلوك تدفقٍ واحدٍ وتخيل ساعةً تدق مرةً واحدةً في كل مرةٍ يُرسَل فيها بتٌ واحد من جميع التدفقات النشطة (يكون التدفق نشطًا عندما يكون لديه بياناتٌ في الرتل)، وافترض أن يشير Pi إلى طول الرزمة i لهذا التدفق النشط، وSi إلى الوقت الذي يبدأ فيه الموجّه في إرسال الرزمة i، وFi إلى الوقت الذي ينتهي فيه الموجّه من إرسال الرزمة i، فإذا جرى الإعلان عن Pi من حيث عدد دقات الساعة اللازمة لإرسال الرزمة i (مع الأخذ بالحسبان أن الوقت يتقدم دقةً واحدةً في كل مرةٍ يحصل فيها هذا التدفق على قيمة 1 بت من الخدمة)، فمن السهل رؤية أن:

 Fi=Si+Pi

ولكن لمعرفة متى نبدأ في إرسال الرزمة i، فلابد من التمييز بين ما إذا كان وصول الرزمة قد حصل قبل أو بعد انتهاء الموجه من إرسال الرزمة i-1 من هذا التدفق، فإذا وصلت قبلها، فمن المنطقي أن يُرسَل البت الأول من الرزمة i مباشرةً بعد آخر بت من الرزمة i-1؛ ومن ناحيةٍ أخرى، من المحتمل انتهاء الموجّه من إرسال الرزمة i-1 قبل وصول الرزمة i بوقتٍ طويل، مما يعني وجود فترةٍ من الوقت كان خلالها رتل هذا التدفق فارغًا، وبالتالي لم تتمكن آلية round-robin من إرسال أي رزمةٍ من هذا التدفق. وعلى افتراض أن Ai يشير إلى وقت وصول الرزمة إلى الموجّه، فعندئذٍ ستكون Si=max(Fi-1,Ai)، وبالتالي يمكننا حساب:

Fi=max(Fi-1,Ai)+Pi

ننتقل الآن إلى الحالة التي يوجد فيها أكثر من تدفقٍ واحد، ونجد أن هناك مشكلةً في تحديد Ai، حيث لا يمكننا قراءة ساعة الحائط فقط عند وصول الرزمة. وكما هو مذكور أعلاه؛ نريد وقتًا للتقدم بدَقةٍ واحدة في كل مرةٍ تحصل فيها جميع التدفقات النشطة على بتٍ واحد من الخدمة في إطار آلية "جولة روبن على بتٍ تلو الآخر"، لذلك سنحتاج إلى ساعةٍ تتقدم ببطء أكثر عندما يكون هناك المزيد من التدفقات، إذ يجب أن تتقدم الساعة بدَقةٍ واحدة عند إرسال n بت إذا كان هناك n من التدفقات النشطة، وستُستخدَم هذه الساعة لحساب Ai.

نحسب الآن ومن أجل كل تدفقٍ Fi لكل رزمةٍ تصل باستخدام الصيغة أعلاه، ثم نتعامل مع كل Fi على أنه علامة زمنية timestamp، والرزمة التالية للإرسال هي دائمًا الرزمة التي تحتوي على أقل علامةٍ زمنية، أي الرزمة التي يجب أن تنتهي من الإرسال قبل جميع الرزم الأخرى.

لاحظ أن هذا يعني أن الرزمة يمكن أن تصل إلى تدفقٍ، ويمكن حشرها في الرتل أمام رزمةٍ أطول منها لأنها أقصر من رزمة من تدفقٍ آخر موجود بالفعل في الرتل في انتظار الإرسال، ولكن هذا لا يعني أن الرزمة الواصلة حديثًا يمكنها منع الرزمة التي يجري إرسالها حاليًا. إن هذا النقص في إجراءات المنع، هو الذي يحفظ تطبيق رتل FQ الموصوف للتو من محاكاة مخطط آلية "جولة روبن على بتٍ تلو الآخر" الذي نحاول تقريبه.

افترض المثال الوارد في الشكل السابق لمعرفة كيفية عمل هذا التطبيق للرتل العادل بصورةٍ أفضل، حيث يوضح القسم (أ) من الشكل السابق أرتالًا لتدفقين؛ وتختار الخوارزمية كلا الرزمتين من التدفق 1 لإرسالهما قبل الرزمة في رتل التدفق 2، بسبب أوقات الانتهاء المبكرة لهما؛ أما في القسم (ب) من الشكل السابق، فقد بدأ الموجّه في إرسال رزمةٍ من التدفق 2 عند وصول رزمةٍ من التدفق 1. لا يمنع التطبيق رزمة التدفق 2، على الرغم من أن الرزمة التي تصل على التدفق 1 كانت ستنتهي قبل التدفق 2 إذا كنا نستخدم رتلًا عادلًا مثاليًا على بتٍ تلو الآخر bit-by-bit fair queuing.

هناك شيئان يجب ملاحظتهما حول الرتل العادل، أولها عدم ترك الرابط خاملًا أبدًا طالما أن هناك رزمةٌ واحدةً على الأقل في الرتل، ويُقال عن أي مخطط أرتال بهذه الخاصية أنه مُحافظ على العمل work conserving. أحد آثار الحفاظ على العمل هو أنه إذا شاركتَ رابطًا مع الكثير من التدفقات التي لا ترسل أي بياناتٍ بعد ذلك؛ فيمكنك استخدام سعة الرابط الكاملة للتدفق الخاص بك، وبمجرد أن تبدأ التدفقات الأخرى في الإرسال، فستبدأ في استخدام حصتها وستنخفض السعة المتاحة للتدفق الخاص بك.

الشيء الثاني الواجب ملاحظته هو أنه إذا حُمِّل الرابط بالكامل مع وجود n تدفقٍ ترسل بيانات، فلا يمكنك استخدام أكثر من ‎1/n ^th من حيز النطاق التراسلي للرابط، وإذا حاولت إرسال أكثر من ذلك، فستُسنَد علاماتٌ زمنية كبيرة بصورةٍ متزايدة إلى رزمك، مما يتسبب في بقائها في الرتل لفترةٍ أطول في انتظار الإرسال. سيحدث طفحان للرتل في النهاية على الرغم من أن قرار إسقاط الرزم الخاصة بك أو بشخصٍ آخر لا تحدده حقيقة أننا نستخدم الرتل العادل، بينما يُحدَّد ذلك من خلال سياسة الإسقاط حيث أن FQ هي خوارزمية جدولة، وهي مثل FIFO يمكن دمجها مع سياسات إسقاط متنوعة.

بما أن FQ يحافظ على العمل، فإن أي حيز نطاق تراسلي لا يستخدمه تدفقٌ هو حيز نطاقٍ تراسلي متاحٌ تلقائيًا للتدفقات الأخرى؛ وإذا كان لدينا أربعة تدفقات تمر عبر موجّه على سبيل المثال وكلهم يرسلون رزمًا، فسيستقبل كل تدفقٍ ربع حيز النطاق التراسلي، ولكن إذا كان تدفقٌ من هذه التدفقات خاملًا لفترةٍ طويلة بما يكفي لاستنزاف جميع رزمه من رتل الموجّه، فستتشارك التدفقات الثلاثة المتبقية حيز النطاق التراسلي المتاح، حيث سيتلقى كلٌ منها الآن ثلث حيز النطاق التراسلي. يمكننا التفكير في FQ على أنه يوفر حصةً دنيا مضمونةً من حيز النطاق التراسلي لكل تدفق، مع إمكانية الحصول على أكثر من ذلك إذا كانت التدفقات الأخرى لا تستخدم حصصها من حيز النطاق التراسلي.

يمكن تطبيق شكلٍ مختلف من رتل FQ، يُسمى "الرتل العادل الموزون weighted fair queuing" أو اختصارًا WFQ، والذي يسمح بإسناد وزنٍ لكل تدفق (رتل). يحدِّد هذا الوزن منطقيًا عدد البتات الواجب إرسالها في كل مرةٍ تُرسَل فيها خدمات الموجّه في الرتل، ويتحكم هذا الوزن بفعالية في النسبة المئوية لحيز لنطاق التراسلي للرابط الذي سيحصل عليه التدفق، كما يمنح FQ البسيط كل رتلٍ وزنًا قدره 1، مما يعني أنه منطقيًا يُرسَل بتًا واحدًا فقط من كل رتلٍ في كل مرة، وينتج عن ذلك حصول كل تدفق على 1 / nth من حيز النطاق التراسلي عند وجود n تدفق، ولكن قد يكون لرتلٍ واحدٍ وزن 2 مع رتل WFQ، ولرتلٍ آخر وزن 1، ولرتلٍ ثالث وزن 3. وبفرض احتواء كل رتلٍ دائمًا على رزمةٍ تنتظر إرسالها، فسيحصل أول تدفقٍ على ثلث حيز النطاق التراسلي المتاح، والتدفق الثاني على سدس حيز النطاق التراسلي المتاح، وسيحصل التدفق الثالث على نصف حيز النطاق التراسلي المتاح.

وصفنا آلية عمل WFQ من حيث التدفقات، ولكن يمكن تطبيقه على أصناف حركة المرور، حيث تُعرَّف هذه الأصناف بطريقةٍ أخرى مختلفةٍ عن التدفقات البسيطة، ويمكننا استخدام بعض البتات في ترويسة IP لتحديد الأصناف وتخصيص رتلٍ ووزنٍ لكل صنفٍ على سبيل المثال، وهذا هو بالضبط ما اُقترِح مثل جزءٍ من معمارية الخدمات المميزة التي ستُشرح لاحقًا.

نلاحظ أنه يتوجب على الموجّه الذي يطبّق رتل WFQ تعلُّم الأوزان الواجب إسنادها لكل رتلٍ من مكانٍ ما، إما عن طريق الضبط اليدوي، أو عن طريق نوعٍ من إصدار الإشارات من المصادر، حيث سنتجه نحو نموذجٍ قائم على الحجز في الحالة الثانية، ويوفّر إسناد وزنٍ لرتلٍ شكلًا ضعيفًا من الحجز لأن هذه الأوزان مرتبطة بصورة غير مباشرة فقط بحيز النطاق التراسلي الذي يستقبله التدفق، كما يعتمد حيز النطاق التراسلي المتاح للتدفق أيضًا على عدد التدفقات الأخرى التي تتشارك بالرابط على سبيل المثال. سنبحث في قسمٍ لاحق كيفية استخدام رتل WFQ على أنه أحد مكونات آلية تخصيص الموارد القائمة على الحجز.

أخيرًا، نلاحظ أن هذه المناقشة الكاملة لإدارة الأرتال توضح مبدأ تصميم نظام مهم يُعرف باسم فصل السياسة عن الآلية، حيث تتمثل الفكرة في عرض كل آليةٍ على أنها صندوقٌ أسود يوفر خدمةً متعددة الأوجه يمكن التحكم فيها بواسطة مجموعة من المقابض knobs، وتحدد السياسة إعدادًا معينًا لتلك المقابض ولكنها لا تعرِف أو تهتم بكيفية تنفيذ هذا الصندوق الأسود، كما تكون الآلية المعنية في هذه الحالة هي نظام الأرتال؛ أما السياسة فهي إعدادٌ معين لأي تدفقٍ يحصل على مستوى الخدمة مثل الأولوية أو الوزن. سنناقش بعض السياسات الممكن استخدامها مع رتل WFQ لاحقًا.

ترجمة -وبتصرّف- للقسم Queuing Disciplines من فصل Congestion Control من كتاب Computer Networks: A Systems Approach.