صندوق الرموز

الموسوعة الحرة

خوارزمية دلو الرموز هي خوارزمية تُستخدم في شبكات تبديل الحزم وشبكات الاتصالات . يمكن استخدامها للتحقق من توافق عمليات نقل البيانات ، على شكل حزم ، مع الحدود المحددة لعرض النطاق الترددي ومعدل التدفق (مقياس لعدم انتظام أو تباين تدفق البيانات ). كما يمكن استخدامها كخوارزمية جدولة لتحديد توقيت عمليات النقل التي تتوافق مع الحدود المحددة لعرض النطاق الترددي ومعدل التدفق: انظر مُجدول الشبكة .

ملخص

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

  • قد يتم إسقاطها.
  • قد يتم وضعها في قائمة الانتظار للإرسال اللاحق عندما تتراكم رموز كافية في الحاوية.
  • قد يتم إرسالها، ولكن يتم وضع علامة عليها بأنها غير مطابقة، وربما يتم إسقاطها لاحقًا إذا كانت الشبكة مثقلة بالأحمال.

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

الخوارزمية

يمكن فهم خوارزمية دلو الرموز من الناحية المفاهيمية على النحو التالي:

  • تُضاف عملة رمزية إلى الدلو كل1/ر{\displaystyle 1/r}ثوانٍ.
  • يمكن أن يستوعب الدلو على الأكثرب{\displaystyle b}الرموز. إذا وصل رمز عندما يكون الوعاء ممتلئًا، يتم التخلص منه.
  • عند وصول حزمة بيانات ( وحدة بيانات بروتوكول طبقة الشبكة ) بحجم n بايت،
    • إذا كان هناك على الأقل n رمزًا في الحاوية، فسيتم إزالة n رمزًا من الحاوية، وسيتم إرسال الحزمة إلى الشبكة.
    • إذا كان عدد الرموز المتاحة أقل من n ، فلن تتم إزالة أي رموز من الحاوية، وتعتبر الحزمة غير متوافقة .

الاختلافات

يواجه مطورو هذه الخوارزمية على المنصات التي تفتقر إلى دقة الساعة اللازمة لإضافة رمز واحد إلى الحاوية كل1/ر{\displaystyle 1/r}قد يرغب المستخدم في النظر في صيغة بديلة. بافتراض إمكانية تحديث حاوية الرموز كل S مللي ثانية، فإن عدد الرموز التي يجب إضافتها كل S مللي ثانية =(ر*S)/1000{\displaystyle (r*S)/1000}.

ملكيات

المعدل المتوسط

على المدى الطويل، يكون ناتج الحزم المتوافقة محدودًا بمعدل الرموز المميزة.ر{\displaystyle r}.

حجم الانفجار

يتركم{\displaystyle M}ليكن معدل الإرسال الأقصى الممكن بالبايت/ثانية.

ثمتيالأعلى={ب/(م-ر) لو ر<م∞ خلاف ذلك {\displaystyle T_{\text{max}}={\begin{cases}b/(Mr)&{\text{ إذا كان }}r<M\\\infty &{\text{ خلاف ذلك }}\end{cases}}}هو الحد الأقصى لوقت الانفجار، أي الوقت الذي يكون فيه المعدلم{\displaystyle M}يتم استغلالها بالكامل.

وبالتالي فإن الحد الأقصى لحجم الدفعة هوبالأعلى=تيالأعلى*م{\displaystyle B_{\text{max}}=T_{\text{max}}*M}

الاستخدامات

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

تُستخدم خوارزمية دلو الرموز أيضًا في التحكم بتدفق عمليات الإدخال/الإخراج في قواعد البيانات. [ 1 ] لا يقتصر هذا التحكم على عمليات الإدخال/الإخراج في الثانية (IOPS) أو عرض النطاق الترددي، بل على توليفة خطية منهما. وبتعريف الرموز على أنها المجموع المعياري لوزن طلب الإدخال/الإخراج وطوله، تضمن الخوارزمية أن يظل المشتق الزمني للدالة المذكورة أقل من الحد الأدنى المطلوب.

مقارنة بالدلو المثقوب

تُشابه خوارزمية دلو الرموز خوارزمية دلو التسريب الموصوفة في المراجع [ 2 ] [ 3 ] [ 4 ] [ 5 ]. ويُشار إلى هذه النسخة المُشابهة من دلو التسريب في صفحة ويكيبيديا ذات الصلة باسم " خوارزمية دلو التسريب كمقياس" . وهي صورة معكوسة لخوارزمية دلو الرموز، حيث تُضيف الحزم المتوافقة سائلاً، يُعادل الرموز التي تُزيلها حزمة متوافقة في خوارزمية دلو الرموز، إلى دلو ذي سعة محدودة، ثم يُصرّف هذا السائل منه بمعدل ثابت، يُعادل عملية إضافة الرموز بمعدل ثابت.

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

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

مجموعة الرموز الهرمية

يُعد نظام التخزين الهرمي للرموز (HTB) بديلاً أسرع لنظام التخزين القائم على الفئات (CBQ) في لينكس . [ 6 ] وهو مفيد للحد من معدل التنزيل / الرفع لكل عميل بحيث لا يتمكن العميل ذو المعدل المحدود من استهلاك النطاق الترددي الإجمالي بالكامل.

ثلاثة عملاء يتشاركون نفس عرض النطاق الترددي الصادر.

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

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

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

انظر أيضاً

مراجع

  1. ↑ "تطبيق خوارزمية جديدة لجدولة عمليات الإدخال/الإخراج لأحمال العمل المختلطة للقراءة والكتابة" . 3 أغسطس 2022. تم الاطلاع عليه بتاريخ 4 أغسطس 2022 .
  2. ↑ تيرنر، ج.، اتجاهات جديدة في الاتصالات (أو أي طريق إلى عصر المعلومات؟) . مجلة IEEE للاتصالات 24 (10): 8-15. ISSN 0163-6804 ، 1986. 
  3. 1 2 أندرو س. تانينباوم، شبكات الحاسوب، الطبعة الرابعة ، ISBN 0-13-166836-6، برنتيس هول بي تي آر، 2003، صفحة 401.
  4. ↑ منتدى أجهزة الصراف الآلي، واجهة شبكة المستخدم (UNI)، الإصدار 3.1، رقم ISBN 0-13-393828-Xبرنتيس هول بي تي آر، 1995.
  5. ↑ ITU-T، التحكم في حركة المرور والتحكم في الازدحام في B ISDN ، التوصية I.371، الاتحاد الدولي للاتصالات، 2004، الملحق أ، الصفحة 87.
  6. ↑ "الصفحة الرئيسية لنظام لينكس HTB" . تم الاطلاع عليها بتاريخ 30-11-2013 .

للمزيد من القراءة

  • جون إيفانز، كلارنس فيلسفيلز (2007). نشر بروتوكول الإنترنت (IP) وبروتوكول MPLS لجودة الخدمة في الشبكات متعددة الخدمات: النظرية والتطبيق . مورغان كوفمان. ISBN 978-0-12-370549-5.
  • فيرغسون، ب.، وهيوستون، ج. (1998). جودة الخدمة: تقديم جودة الخدمة على الإنترنت وفي شبكات الشركات . جون وايلي وأولاده، رقم ISBN 0-471-24358-2.