خوارزمية معدل الخلية العامة

قد يكون الوصف باستخدام خوارزمية الدلو المثقوب أسهل فهمًا من الناحية المفاهيمية، إذ يعتمد على تشبيه بسيط بدلو مثقوب: انظر الشكل 1 في صفحة الدلو المثقوب . مع ذلك، ثمة لبس في الأدبيات العلمية حول تطبيق تشبيه الدلو المثقوب لإنتاج خوارزمية، وهو ما انعكس على خوارزمية GCRA. ينبغي اعتبار خوارزمية GCRA بمثابة نسخة من الدلو المثقوب كمقياس، لا كطابور .

مع ذلك، ورغم وجود مزايا محتملة في فهم وصف "الدلو المتسرب"، إلا أن تطبيقه المباشر لا يؤدي بالضرورة إلى أفضل (أسرع) كود برمجي. ويتضح ذلك من خلال العدد النسبي للإجراءات المطلوب تنفيذها في مخططات التدفق للوصفين (الشكل 1).

يُقدّم الاتحاد الدولي للاتصالات (ITU-T) وصفًا لخوارزمية الدلو المُسرّب ذي الحالة المستمرة على النحو التالي: "يمكن اعتبار الدلو المُسرّب ذي الحالة المستمرة دلوًا ذا سعة محدودة، حيث يتسرب محتواه ذو القيم الحقيقية بمعدل مستمر قدره وحدة واحدة من المحتوى لكل وحدة زمنية، ويزداد محتواه بمقدار T لكل خلية مُطابقة... إذا كان محتوى الدلو عند وصول خلية ما أقل من أو يساوي القيمة الحدية τ ، فإن الخلية مُطابقة؛ وإلا، فإن الخلية غير مُطابقة. سعة الدلو (الحد الأعلى للعداد) هي ( T + τ )"  . ^{[ 2 ]} تجدر الإشارة إلى أنه نظرًا لأن التسرب هو وحدة واحدة من المحتوى لكل وحدة زمنية، فإن الزيادة لكل خلية T والقيمة الحدية τ تُقاس بوحدات زمنية.

بالنظر إلى مخطط تدفق خوارزمية الدلو المتسرب ذات الحالة المستمرة، حيث T هي فترة الانبعاث و τ هي القيمة الحدية: عند وصول خلية، تُحسب حالة الدلو من حالته عند وصول آخر خلية مطابقة، X ، ومقدار ما تسرب خلال الفترة، t _a – LCT . تُخزن قيمة الدلو الحالية في X' وتُقارن بالقيمة الحدية τ . إذا كانت قيمة X' أقل من τ ، فإن الخلية لم تصل مبكرًا جدًا، وبالتالي فهي مطابقة لمعايير العقد؛ أما إذا كانت قيمة X' أكبر من τ ، فهي غير مطابقة. إذا كانت مطابقة، فإذا كانت مطابقة لأنها وصلت متأخرة، أي الدلو فارغ ( X' ≤ 0)، تُعيّن قيمة X إلى T ؛ أما إذا كانت مبكرة، ولكن ليس مبكرًا جدًا ( τ ≥ X' > 0)، فتُعيّن قيمة X إلى X' + T.

وبالتالي فإن مخطط التدفق يحاكي تشبيه الدلو المتسرب (المستخدم كمقياس) بشكل مباشر، حيث يعمل X و X' كنظير للدلو.

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

يُقدّم الاتحاد الدولي للاتصالات (ITU-T) وصفًا لخوارزمية الجدولة الافتراضية على النحو التالي: "تُحدّث خوارزمية الجدولة الافتراضية وقت الوصول النظري (TAT)، وهو وقت الوصول "الاسمي" للخلية بافتراض إرسال الخلايا على فترات متساوية بفاصل زمني T يُقابل معدل الخلية Λ [= 1/ T ] عندما يكون المصدر نشطًا. إذا لم يكن وقت الوصول الفعلي للخلية "مبكرًا جدًا" بالنسبة إلى وقت الوصول النظري (TAT) والتفاوت τ المرتبط بمعدل الخلية، أي إذا كان وقت الوصول الفعلي بعد وقت الوصول النظري مطروحًا منه القيمة الحدية (t _a > TAT – τ )، فإن الخلية تُعتبر مُطابقة؛ وإلا، فإن الخلية تُعتبر غير مُطابقة"  . ^{[ 2 ]} إذا كانت الخلية غير مُطابقة، فإن وقت الوصول النظري (TAT) يبقى دون تغيير. أما إذا كانت الخلية مُطابقة، ووصلت قبل وقت الوصول النظري (TAT) الخاص بها (أي أن الحاوية ليست فارغة ولكنها أقل من القيمة الحدية)، فإن وقت الوصول النظري (TAT) للخلية التالية هو ببساطة TAT + T. مع ذلك، إذا وصلت خلية بعد وقت الاستجابة المحدد لها ، يُحسب وقت الاستجابة للخلية التالية بناءً على وقت وصول هذه الخلية، وليس وقت الاستجابة المحدد لها . وهذا يمنع تراكم الرصيد عند وجود فجوة في الإرسال (أي عندما يصبح الرصيد أقل من فارغ).

يعمل هذا الإصدار من الخوارزمية لأن τ يحدد مدى إمكانية وصول الخلية مبكرًا مقارنةً بما لو لم يكن هناك تذبذب: انظر إلى "الدلو المتسرب: تحمل تباين التأخير" . بمعنى آخر، يمثل TAT الوقت الذي سيفرغ فيه الدلو مجددًا، لذا فإن الوقت τ قبل ذلك هو الوقت الذي يكون فيه الدلو ممتلئًا تمامًا إلى القيمة القصوى. وبالتالي، في كلتا الحالتين، إذا وصلت الخلية قبل TAT بأكثر من τ ، فإنها تكون مبكرة جدًا للامتثال.

على عكس تطبيقات خوارزمية دلو الرموز ، لا تحاكي خوارزمية GCRA عملية تحديث الدلو (التسريب أو إضافة الرموز بانتظام). بل تقوم، في كل مرة تصل فيها خلية، بحساب مقدار التسريب الذي سيحدث في الدلو منذ آخر حساب لمستواه، أو متى سيفرغ الدلو مجددًا (أي وقت الاستجابة ). وهذا يعني استبدال عملية التسريب بساعة (في الوقت الحقيقي)، والتي من المرجح أن تكون موجودة بالفعل في معظم تطبيقات الأجهزة.

يُمكن استبدال هذه العملية بساعة الوقت الحقيقي (RTC) لأن خلايا ATM لها طول ثابت (53 بايت)، وبالتالي فإن T ثابت دائمًا، ولا تتضمن عملية حساب مستوى الحاوية الجديد (أو TAT ) أي عمليات ضرب أو قسمة. ونتيجةً لذلك، يُمكن إجراء الحساب بسرعة في البرنامج، ومع أن عدد الإجراءات المتخذة عند وصول خلية جديدة يفوق عدد الإجراءات التي تتخذها حاوية الرموز، إلا أن عدم وجود عملية تحديث منفصلة يُعوّض ذلك تمامًا من حيث الحمل على المعالج الذي يُنفّذ المهمة. علاوةً على ذلك، ولعدم وجود محاكاة لتحديث الحاوية، لا يوجد أي حمل على المعالج على الإطلاق عندما يكون الاتصال في حالة سكون.

مع ذلك، إذا استُخدمت خوارزمية GCRA لتقييد عرض النطاق الترددي، بدلاً من معدل الحزم/الإطارات، في بروتوكول ذي حزم متغيرة الطول ( وحدات بيانات بروتوكول طبقة الربط )، فسيتطلب ذلك عملية ضرب: أي أن القيمة المضافة إلى قيمة "الوعاء" (أو إلى زمن الاستجابة) لكل حزمة مطابقة يجب أن تتناسب مع طول الحزمة. فبينما تُقاس قيمة "الوعاء" في خوارزمية GCRA كما وُصفت، بوحدات زمنية، فإن الحزم متغيرة الطول يجب أن تُقاس بوحدات ناتج ضرب طول الحزمة في الزمن. لذا، قد لا يكون تطبيق خوارزمية GCRA لتقييد عرض النطاق الترددي للحزم متغيرة الطول عمليًا دون توفر مُضاعِف سريع للأجهزة (كما في مصفوفة البوابات المنطقية القابلة للبرمجة FPGA ). مع ذلك، يمكن استخدامها دائمًا لتقييد معدل الحزم أو الخلايا، طالما تم تجاهل أطوالها.