🚀 الگوریتم Leaky Bucket

🔹 تعریف:
الگوریتم Leaky Bucket یکی از الگوریتم‌های Traffic Shaping (شکل‌دهی به ترافیک شبکه) است که وظیفه دارد جریان داده‌ها در شبکه را کنترل و هموارسازی (regulate) کند.

در این روش، بسته‌های ورودی (packets) در یک بافر با اندازه‌ی ثابت (سطل) ذخیره می‌شوند و سپس با نرخ ثابتی از سطل خارج و به شبکه ارسال می‌گردند.
اگر بافر پر شود، بسته‌های اضافی دور انداخته می‌شوند (discarded).

📊 ویژگی‌ها:

✅ هموارسازی ترافیک ناگهانی (bursty traffic) با ارسال در نرخ ثابت
✅ حذف بسته‌های اضافی در صورت پر شدن بافر
مثال: اگر هاستی در حالت عادی با نرخ ۳ Mbps متعهد است، الگوریتم تضمین می‌کند حتی در زمان ارسال ناگهانی داده‌ها، نرخ خروجی از ۳ Mbps بیشتر نشود.

⚙️ نحوه‌ی کار الگوریتم Leaky Bucket:

الگوریتم Leaky Bucket معمولاً از یک صف (First In, First Out) FIFOبرای مدیریت بسته‌ها استفاده می‌کند.

🔸 برای بسته‌های با اندازه‌ی ثابت:
در هر تیک ساعت (Clock Tick)، تعداد ثابتی از بسته‌ها از صف حذف و ارسال می‌شوند.

🔸 برای بسته‌های با اندازه‌ی متغیر (Variable-size packets):
ارسال داده‌ها بر اساس یک نرخ ثابت بر حسب بایت یا بیت در ثانیه انجام می‌شود.

🧠 شبه‌کد الگوریتم برای بسته‌های با طول متغیر:

1️⃣ مقدار شمارنده (counter) را در هر تیک ساعت برابر n مقداردهی کن.
2️⃣ تا زمانی که n بزرگ‌تر از اندازه‌ی بسته‌ی موجود در سر صف است:
• بسته‌ای از ابتدای صف خارج کن (P)
• بسته P را به شبکه ارسال کن
• شمارنده را به اندازه‌ی سایز بسته کاهش بده
3️⃣ در تیک بعدی ساعت، مقدار شمارنده را مجدداً برابر n قرار بده و مرحله 1 را تکرار کن.


📦 مثال عددی:

فرض کنید:
n = 1000
و اندازه‌ی بسته‌های موجود در صف به ترتیب:
200, 400, 450 بایت هستند.

🔹 مرحله 1️⃣:
چون n > 200 → بسته ۲۰۰ بایتی ارسال می‌شود.
n = 1000 - 200 = 800

🔹 مرحله 2️⃣:
چون n > 400 → بسته ۴۰۰ بایتی ارسال می‌شود.
n = 800 - 400 = 400

🔹 مرحله 3️⃣:
چون n < 450 → الگوریتم در این تیک متوقف می‌شود.

در تیک بعدی ساعت، n مجدداً برابر ۱۰۰۰ شده و فرآیند از ابتدا تکرار می‌شود تا زمانی که همه‌ی بسته‌ها ارسال شوند.

🚀 Leaky Bucket Algorithm – C# Implementation

در ادامه‌ی توضیح الگوریتم، اینجا پیاده‌سازی کامل اون رو در زبان #C می‌بینیم 👇
💻 کد:

// C# Implementation of Leaking Bucket Algorithm
using System;

class LeakingBucket
{
    static void Main(string[] args)
    {
        int no_of_queries, storage, output_pkt_size;
        int input_pkt_size, bucket_size, size_left;

        // Initial packets in the bucket
        storage = 0;

        // Total number of times bucket content is checked
        no_of_queries = 4;

        // Total number of packets that can be accommodated in the bucket
        bucket_size = 10;

        // Number of packets that enter the bucket at a time
        input_pkt_size = 4;

        // Number of packets that exit the bucket at a time
        output_pkt_size = 1;

        for (int i = 0; i < no_of_queries; i++)
        {
            size_left = bucket_size - storage; // space left in the bucket

            if (input_pkt_size <= size_left)
            {
                storage += input_pkt_size;
            }
            else
            {
                Console.WriteLine("Packet loss = " + input_pkt_size);
            }

            Console.WriteLine($"Buffer size = {storage} out of bucket size = {bucket_size}");

            // Sending packets out of the bucket
            storage -= output_pkt_size;
        }
    }
}

🚀 Leaky Bucket Algorithm – Output & Comparison

💻 خروجی برنامه:

Buffer size= 4 out of bucket size= 10  
Buffer size= 7 out of bucket size= 10  
Buffer size= 10 out of bucket size= 10  
Packet loss = 4  
Buffer size= 9 out of bucket size= 10