ما هي خوارزمية Leaky Bucket في شبكات الحاسوب

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

مبدأ عمل خوارزمية Leaky Bucket

تعمل الخوارزمية بشكل مشابه للطريقة التي يحتفظ بها دلو تسرب الماء بالمياه، حيث يأخذ “Leaky Bucket” البيانات ويجمعها بأقصى سعة، كما يتم تحرير البيانات الموجودة في الحاوية فقط من الحاوية بمعدل وحجم معين للحزمة، وعند نفاد البيانات في “Bucket” يتوقف التسريب، أمّا إذا كانت البيانات الواردة تملأ الحاوية بشكل زائد فإنّ الحزمة تعتبر غير مطابقة ولا تتم إضافتها إلى الحاوية، كما تتم إضافة البيانات إلى الحاوية عندما تصبح المساحة متاحة للحزم المطابقة.

كما يمكن لخوارزمية “Leaky Bucket” أيضاً اكتشاف كل من الزيادة التدريجية والخطأ الدراماتيكي في الذاكرة من خلال مقارنة كيفية تجاوز متوسط، ​​ومعدلات الذروة للبيانات المحددة كميات الخلفية المقبولة وفي سياق أوسع يعتبر “Leaky Bucket” تشبيهاً لوصف كيفية عمل المدخلات والمخرجات في مجموعة متنوعة من أنظمة الأعمال والتكنولوجيا.

• “ATM” هي اختصار لـ “Asynchronous Transfer Mode”.

أساسيات خوارزمية Leaky Bucket

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

ومع وجود عدد كبير جداً من الزيارات ينخفض ​​الأداء بشكل حاد، كما يوجد نوعان من خوارزميات التحكم في الازدحام وهما خوارزمية “Leaky Bucket” وخوارزمية “Token bucket”، حيث في شبكات الحاسوب والاتصالات كان هناك دائماً اتجاه لمشكلات المرور أو الازدحام، والتي قد تكون نتيجة مرسلين أسرع وأجهزة استقبال بطيئة وأجهزة استقبال سريعة وأجهزة إرسال بطيئة أو كليهما، حيث أصبح التحكم في حركة المرور جزءاً ضرورياً من الشبكات والتواصل لضمان انتقال سلس بين المرسل والمستقبل والعكس صحيح.

وهناك نوعان من ضوابط الازدحام المروري أي خوارزمية “Leaky Bucket” وهو مصاغ من كيفية عمل دلو التسريب الفعلي، وفي خوارزمية “Token bucket” يكون لكلتا الطريقتين إيجابيات وسلبيات وأنماط تشغيل مختلفة، وفي خوارزمية “Leaky Bucket” هناك المفاتيح ذات الصلة التي يجب ملاحظتها:

• لم يتم تحديد الناتج عن طريق الإدخال باستثناء أنّ “Leaky” فارغ.

• يتدفق الناتج بمعدل ثابت بينما قد يختلف الإدخال.

كما تراقب الشبكة تدفقات حركة المرور بشكل مستمر للتأكد من أنّها تفي بحصة المرور الخاصة بهم وهذا ما يسمى الشرطة، وعند وصول الحزمة يتم فحصها للتأكد من موافقتها على الحصة وفي حالة انتهاك الشبكة إمّا أن تتجاهل الحزمة أو تضع عليها علامة تعطيها أولوية أقل، وعندما يكون هناك ازدحام يتم تجاهل الحزم الموسومة أولاً، كما يمكن استخدام خوارزمية “Leaky Bucket” لمراقبة معدلات وصول الحزم.

آلية عمل خوارزمية Leaky Bucket

تتحكم خوارزمية “Leaky Bucket” بشكل أساسي في المبلغ الإجمالي ومعدل حركة المرور المرسلة إلى الشبكة:

• لنفترض هناك “Bucket” به فتحة صغيرة في الأسفل، حيث معدل دخول البيانات في “Bucket” غير ثابت ويمكن أن يختلف ولكنه يتسرب من “Bucket” بمعدل ثابت.

• حتى الماء موجود في “Bucket” فإنّ معدل تسرب البيانات لا يعتمد على معدل إدخال البيانات إلى “Bucket”.

• إذا كان “Bucket” ممتلئاً فإنّ البيانات الإضافية التي تدخل في “Bucket” تخرج على الجانبين ويضيع.

• وهكذا ينطبق نفس المفهوم على الحزم في الشبكة، وكما أنّ البيانات تأتي من المصدر بسرعات متغيرة، وافترض أنّ أحد المصادر يرسل بيانات بسرعة “10 ميجابت في الثانية” لمدة “4 ثوانٍ”، ثم لا توجد بيانات لمدة “3 ثوان” وينقل المصدر البيانات مرة أخرى بمعدل “8 ميجابت في الثانية” لمدة ثانيتين، وبالتالي في فترة زمنية تبلغ “8 ثوانٍ”، تم إرسال “68 ميجابايت من البيانات”.

• وهذا هو السبب في أنّه إذا تم استخدام خوارزمية “Leaky Bucket” فسيكون تدفق البيانات “8 ميجابت في الثانية” لمدة “9 ثوانٍ”، وبالتالي يتم الحفاظ على التدفق المستمر.

تطور خوارزمية Leaky Bucket

يتم استخدام تطبيق “Leaky Bucket” للتحكم في معدل إرسال حركة المرور إلى الشبكة، كما تنفيذ “Leaky Bucket” في نفس “Bucket” الذي يحتوي على ثقب في الأسفل، كما أنّ “Bucket” به فتحة صغيرة في الأسفل وبغض النظر عن المعدل الذي يدخل به البيانات إلى “Bucket”، يكون التدفق الخارج بمعدل ثابت “r” عندما يكون هناك أي كمية البيانات في “Bucket” وصفر عندما يكون “Bucket” فارغاً، وأيضاً بمجرد امتلاء الحاوية تتسرب أي بيانات إضافية تدخلها على الجوانب وتُفقد أي لا تظهر في تيار الإخراج أسفل الفتحة.

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

كما يمكن تضمين هذا الترتيب في واجهة الأجهزة أو محاكاته بواسطة نظام التشغيل المضيف، حيث تم اقتراحه لأول مرة بواسطة “Turner (1986)” ويسمى خوارزمية “Leaky Bucket”، كما إنّه ليس سوى نظام انتظار خادم واحد مع وقت خدمة ثابت، حيث يُسمح للمضيف بوضع حزمة واحدة لكل علامة ساعة على الشبكة، وكما يمكن فرض ذلك بواسطة بطاقة الواجهة أو بواسطة نظام التشغيل.

تعمل هذه الآلية على تحويل التدفق غير المتكافئ للحزم من عمليات المستخدم داخل المضيف إلى تدفق متساوٍ للحزم على الشبكة، ممّا يؤدي إلى تجانس الرشقات وتقليل فرص الازدحام بشكل كبير حيث عندما تكون الحزم كلها بنفس الحجم وعلى سبيل المثال خلايا “ATM”، يمكن استخدام هذه الخوارزمية كما هو موصوف.

ومع ذلك عند استخدام حزم متغيرة الحجم فمن الأفضل غالباً السماح بعدد ثابت من البايت لكل علامة بدلاً من حزمة واحدة فقط وبالتالي إذا كانت القاعدة “1024 بايت” يمكن قبول حزمة واحدة بحجم “1024 بايت” على علامة وحزمتين بحجم “512 بايت” وأربع حزم سعة “256 بايت” وما إلى ذلك، أمّا إذا كان عدد البايتات المتبقية منخفضاً جداً يجب أن تنتظر الحزمة التالية حتى العلامة التالية.

يُعد تنفيذ خوارزمية “Leaky Bucket” أمراً سهلاً، كما يتكون “Leaky Bucket” من قائمة انتظار محدودة حيث عندما تصل الحزمة وإذا كان هناك مكان في قائمة الانتظار، يتم إلحاقها بقائمة الانتظار وخلاف ذلك يتم التخلص منه، كما أنّه في كل دقيقة على مدار الساعة يتم إرسال حزمة واحدة وما لم تكن قائمة الانتظار فارغة.