Algorytm górnych węzłów
Algorytm top-nodes jest algorytmem zarządzania kalendarzem rezerwacji zasobów. Algorytm został opublikowany po raz pierwszy w 2003 roku i został udoskonalony w 2009 roku. Jest używany, gdy zasób jest współdzielony przez wielu użytkowników (np. przepustowość łącza telekomunikacyjnego lub pojemność dysku w dużym centrum danych ).
Algorytm umożliwia użytkownikom:
- sprawdzić, czy dana ilość zasobu jest dostępna w określonym czasie,
- zarezerwować określoną ilość zasobów na określony czas,
- usunąć poprzednią rezerwację,
- przesuwać kalendarz do przodu (kalendarz obejmuje określony czas i musi być przesuwany do przodu w miarę upływu czasu).
Zasada
Kalendarz jest przechowywany jako drzewo binarne , w którym liście reprezentują elementarne okresy czasu. Inne węzły reprezentują okres czasu objęty wszystkimi ich potomkami.
Okres czasu objęty rezerwacją jest reprezentowany przez zbiór „górnych węzłów”. Ten zestaw jest minimalnym zbiorem węzłów, które dokładnie pokrywają okres rezerwacji.
Węzeł drzewa binarnego jest „górnym węzłem” dla danej rezerwacji, jeśli
- wszyscy jego potomkowie znajdują się w okresie rezerwacji, oraz
- jest to węzeł główny lub co najmniej jeden element potomny węzła nadrzędnego jest poza okresem rezerwacji.
W każdym węźle przechowywana jest następująca wartość:
q(węzeł) = max(q(lewe dziecko), q(prawe dziecko)) + całkowita ilość zarezerwowanych zasobów dla wszystkich rezerwacji mających ten węzeł jako „węzeł górny”
(w celu optymalizacji kodu dwie części tej sumy są zwykle przechowywane oddzielnie).
Wydajność
Zaletą tego algorytmu jest to, że czas rejestracji nowej rezerwacji zasobu zależy tylko od wielkości kalendarza (nie zależy od całkowitej liczby rezerwacji).
Niech n będzie liczbą elementarnych okresów w kalendarzu.
Maksymalna liczba "górnych węzłów" dla danej rezerwacji to 2.log n.
- aby sprawdzić, czy ilość zasobów jest dostępna w określonym czasie: O (log n )
- aby zarezerwować ilość zasobów na określony czas : O (log n )
- aby usunąć poprzednią rezerwację : O (log n )
- aby przesunąć kalendarz do przodu: O (log n + M.log n)
gdzie M to liczba rezerwacji aktywnych w dodanych okresach kalendarzowych.
( M = 0, jeśli rezerwacje nie są dozwolone po zakończeniu kalendarza.)
Linki zewnętrzne
- (w języku francuskim) kod źródłowy C