Wikiszótár

vezérjeles vödör algoritmus

Magyar

Kiejtés

  • IPA: [ ˈvɛzeːrjɛlɛʃ ˈvødør ˈɒlɡoritmuʃ]

Főnév

vezérjeles vödör algoritmus

  1. (matematika, algoritmusok) A vezérjeles vödör algoritmus egy hálózati forgalomszabályozási technika, amely szabályozza az adatátviteli sebességet. Az algoritmus célja, hogy korlátozza a forgalmat egy meghatározott sebességre, miközben lehetővé teszi a rövid ideig tartó csúcsterhelést.


Elmélet

  1. Vödör és vezérjelek:
    • Egy “vödör” tartalmazza a vezérjeleket (tokeneket), amelyek lehetővé teszik az adatcsomagok átvitelét.
    • Minden adatcsomag elküldéséhez egy vagy több vezérjel szükséges.
    • A vödör meghatározott sebességgel (pl. másodpercenként (r)) kap új vezérjeleket.
  2. Kapacitás:
    • A vödör maximális kapacitása ((B)) korlátozza a benne lévő vezérjelek számát. Ha a vödör megtelik, az új vezérjelek elvesznek.
  3. Csomagküldés:
    • Egy csomag akkor küldhető, ha a vödörben elegendő vezérjel van. Ha nincs elegendő vezérjel, a csomag várakozik vagy eldobásra kerül (a rendszertől függően).


Tulajdonságok

  • Sebességkorlátozás:
    • Az algoritmus korlátozza az átviteli sebességet (r)-re, de rövid ideig tartó csúcsterheléseket ((B)) is lehetővé tesz.
  • Rugalmasság:
    • Hatékonyan kezeli a váratlan terhelési csúcsokat, miközben biztosítja a folyamatos adatátviteli szabályozást.
  • Alkalmazás:
    • Hálózati forgalom korlátozása.
    • Szolgáltatásminőség (QoS) biztosítása.


Pszeudokód

TokenBucket(capacity, rate):
    vödör = capacity
    utolsó_frissítés = most()

    amíg van csomag:
        most = jelenlegi idő
        eltelt_idő = most - utolsó_frissítés
        új_vezérjelek = eltelt_idő * rate
        vödör = min(vödör + új_vezérjelek, capacity)

        ha csomag_súlya <= vödör:
            vödör = vödör - csomag_súlya
            engedélyezd a csomagot
        különben:
            várakozz
        utolsó_frissítés = most

Python implementáció

import time

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity  # A vödör maximális kapacitása
        self.rate = rate          # A vezérjelek érkezési sebessége (token/s)
        self.tokens = capacity    # Kezdetben tele a vödör
        self.last_refill_time = time.time()

    def allow_request(self, tokens_needed=1):
        # Frissítjük a vödörben lévő vezérjelek számát
        current_time = time.time()
        elapsed = current_time - self.last_refill_time
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last_refill_time = current_time

        # Ellenőrizzük, hogy van-e elég vezérjel a kérés teljesítéséhez
        if self.tokens >= tokens_needed:
            self.tokens -= tokens_needed
            return True
        else:
            return False

# Példa használat
bucket = TokenBucket(capacity=10, rate=5)  # 10-es kapacitású vödör, 5 vezérjel/másodperc

requests = [1, 2, 3, 4, 5]
for req in requests:
    if bucket.allow_request(req):
        print(f"{req} vezérjel kérése engedélyezve.")
    else:
        print(f"{req} vezérjel kérése megtagadva.")
    time.sleep(0.5)  # Várunk, hogy vezérjelek érkezzenek

Kimenet (időzítéstől függően): 

1 vezérjel kérése engedélyezve.
2 vezérjel kérése engedélyezve.
3 vezérjel kérése engedélyezve.
4 vezérjel kérése megtagadva.
5 vezérjel kérése megtagadva.

C++ implementáció

#include <iostream>
#include <chrono>
#include <thread>

using namespace std;
using namespace chrono;

class TokenBucket {
private:
    double capacity;
    double rate;
    double tokens;
    steady_clock::time_point last_refill_time;

public:
    TokenBucket(double cap, double r) : capacity(cap), rate(r), tokens(cap), last_refill_time(steady_clock::now()) {}

    bool allow_request(double tokens_needed = 1) {
        auto now = steady_clock::now();
        double elapsed = duration_cast<milliseconds>(now - last_refill_time).count() / 1000.0;

        tokens = min(capacity, tokens + elapsed * rate);
        last_refill_time = now;

        if (tokens >= tokens_needed) {
            tokens -= tokens_needed;
            return true;
        } else {
            return false;
        }
    }
};

int main() {
    TokenBucket bucket(10, 5);  // 10-es kapacitás, 5 vezérjel/másodperc

    double requests[] = {1, 2, 3, 4, 5};
    for (double req : requests) {
        if (bucket.allow_request(req)) {
            cout << req << " vezérjel kérése engedélyezve." << endl;
        } else {
            cout << req << " vezérjel kérése megtagadva." << endl;
        }
        this_thread::sleep_for(milliseconds(500));  // Várunk, hogy vezérjelek érkezzenek
    }

    return 0;
}

Kimenet (időzítéstől függően): 

1 vezérjel kérése engedélyezve.
2 vezérjel kérése engedélyezve.
3 vezérjel kérése engedélyezve.
4 vezérjel kérése megtagadva.
5 vezérjel kérése megtagadva.

Összegzés

A vezérjeles vödör algoritmus egy hatékony és rugalmas módszer a hálózati forgalom szabályozására. Pythonban és C++-ban is könnyen implementálható, és különféle rendszerekben, például API-k sebességkorlátozásában vagy hálózati forgalomszabályozásban alkalmazható.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=vezérjeles_vödör_algoritmus&oldid=3479484”