Ogólny algorytm szybkości komórek

Ogólny algorytm szybkości transmisji danych (GCRA) to algorytm planowania typu przeciekowego zasobnika dla programu planującego sieć , który jest używany w sieciach w trybie transferu asynchronicznego (ATM). Służy do pomiaru taktowania komórek w kanałach wirtualnych (VC) i/lub ścieżkach wirtualnych (VP) w stosunku do przepustowości i limitów jittera zawartych w kontrakcie ruchu dla VC lub VP, do którego należą komórki. Komórki, które nie są zgodne z ograniczeniami określonymi w umowie o ruchu drogowym, mogą zostać ponownie ustawione w czasie (opóźnione) w kształtowaniu ruchu lub mogą zostać porzucone (odrzucone) lub obniżone w priorytecie (zdegradowane) w policji drogowej . Niezgodne komórki, które mają zmniejszony priorytet, mogą następnie zostać porzucone, zamiast komórek o wyższym priorytecie, przez dalsze komponenty w sieci, które doświadczają przeciążenia. Alternatywnie mogą dotrzeć do miejsca docelowego (zakończenie VC lub VP), jeśli jest dla nich wystarczająca przepustowość, mimo że są to komórki nadmiarowe z punktu widzenia umowy: patrz kontrola priorytetów.

GCRA jest podawany jako odniesienie do sprawdzania ruchu na połączeniach w sieci, tj. kontroli parametrów użytkowania/sieci (UPC/NPC) na interfejsach użytkownik-sieć (UNI) lub interfejsach międzysieciowych lub interfejsach sieć-sieć (INI/NNI ) . Jest również podawany jako odniesienie dla taktowania przesyłanych komórek (ATM PDU Data_Requests) do sieci ATM przez kartę interfejsu sieciowego (NIC) w hoście, tj. po stronie użytkownika UNI. Zapewnia to, że komórki nie zostaną następnie odrzucone przez UPC/NCP w sieci, tj. po sieciowej stronie UNI. Ponieważ jednak GCRA jest podany tylko jako odniesienie, dostawcy sieci i użytkownicy mogą użyć dowolnego innego algorytmu, który daje ten sam wynik.

Opis GCRA

Rysunek 1: Równoważne wersje ogólnego algorytmu częstości komórek

GCRA jest opisana przez ATM Forum w swoim User-Network Interface (UNI) oraz przez ITU-T w zaleceniu I.371 Kontrola ruchu i kontrola przeciążenia w B-ISDN . Oba źródła opisują GCRA na dwa równoważne sposoby: jako wirtualny algorytm planowania i jako algorytm nieszczelnego wiadra w stanie ciągłym (rysunek 1).

Opis nieszczelnego wiadra

Opis algorytmu cieknącego wiadra może być łatwiejszy do zrozumienia z perspektywy koncepcyjnej, ponieważ opiera się na prostej analogii do wiadra z wyciekiem: patrz rysunek 1 na stronie cieknącego wiadra . Jednak w literaturze doszło do zamieszania co do zastosowania analogii nieszczelnego wiadra do stworzenia algorytmu, który przeszedł do GCRA. GCRA należy traktować jako wersję nieszczelnego wiadra jako licznika, a nie nieszczelnego wiadra jako kolejki .

Jednakże, chociaż zrozumienie tego nieszczelnego opisu zasobnika może przynieść korzyści, niekoniecznie skutkuje to najlepszym (najszybszym) kodem, jeśli zostanie zaimplementowany bezpośrednio. Świadczy o tym względna liczba czynności do wykonania na schematach blokowych dla obu opisów (rysunek 1).

Opis algorytmu nieszczelnego wiadra w stanie ciągłym jest podany przez ITU-T w następujący sposób: „Nieszczelne wiadro w stanie ciągłym można postrzegać jako wiadro o skończonej pojemności, którego rzeczywista zawartość wypływa z ciągłą szybkością 1 jednostki zawartości na jednostkę czasu i której zawartość jest zwiększana o przyrost T dla każdej zgodnej komórki... Jeżeli w chwili przybycia komórki zawartość zasobnika jest mniejsza lub równa wartości granicznej τ , wówczas komórka jest zgodna, w przeciwnym razie komórka jest niezgodna Pojemność kubełka (górna granica licznika) wynosi ( T + τ )”. Warto zauważyć, że ponieważ wyciek wynosi jedną jednostkę zawartości na jednostkę czasu, przyrost dla każdej komórki T i wartość graniczna τ są w jednostkach czasu.

Biorąc pod uwagę schemat blokowy algorytmu nieszczelnego wiadra w stanie ciągłym, w którym T jest interwałem emisji, a τ jest wartością graniczną: Kiedy przybywa komórka, stan wiadra jest obliczany na podstawie jego stanu, kiedy przybyła ostatnia spełniająca wymagania komórka , X , i ile wyciekło w przedziale, t _a – LCT . Ta bieżąca wartość koszyka jest następnie zapisywana w X' i porównywana z wartością graniczną τ . Jeżeli wartość w X' nie jest większa niż τ , komórka nie dotarła za wcześnie i jest zgodna z parametrami umowy; jeśli wartość w X' jest większa niż τ , to nie jest zgodna. Jeśli jest zgodny, to jeśli jest zgodny, ponieważ było późno, tj. kubeł jest pusty ( X' <= 0), X jest ustawiany na T ; jeśli było wcześnie, ale nie za wcześnie, ( τ >= X' > 0), X jest ustawione na X' + T .

W ten sposób schemat blokowy naśladuje bezpośrednio analogię nieszczelnego wiadra (używanego jako licznik), przy czym X i X ' działają jako odpowiednik wiadra.

Opis harmonogramu wirtualnego

Wirtualny algorytm planowania, choć nie jest tak wyraźnie powiązany z tak łatwo dostępną analogią, jak nieszczelny wiadro, daje lepsze zrozumienie tego, co robi GCRA i jak można go najlepiej wdrożyć. W rezultacie bezpośrednia implementacja tej wersji może skutkować bardziej zwartym, a przez to szybszym kodem niż bezpośrednia implementacja opisu cieknącego zasobnika.

Opis algorytmu planowania wirtualnego jest podany przez ITU-T w następujący sposób: „Algorytm planowania wirtualnego aktualizuje teoretyczny czas przybycia (TAT), który jest„ nominalnym ”czasem przybycia komórki, przy założeniu, że komórki są wysyłane w równych odstępach w interwale emisji T odpowiadającym szybkości komórki Λ [= 1/ T ], gdy źródło jest aktywne. Jeżeli rzeczywisty czas nadejścia komórki nie jest „za wcześnie” w stosunku do TAT i tolerancji τ powiązany z szybkością komórki, tj. jeśli rzeczywisty czas dotarcia jest późniejszy niż jego teoretyczny czas dotarcia pomniejszony o wartość graniczną (t _a > TAT – τ ), wówczas komórka jest zgodna; w przeciwnym razie komórka jest niezgodna”. Jeśli komórka jest niezgodna TAT pozostaje niezmieniona. Jeśli komórka jest zgodna i dotarła przed TAT (odpowiednik tego, że wiadro nie jest puste, ale jest mniejsze niż wartość graniczna), to następny TAT komórki to po prostu TAT + T. Jednakże, jeśli komórka przybywa po swoim TAT , to TAT dla następnej komórki jest obliczany na podstawie czasu przybycia tej komórki, a nie jej TAT . Zapobiega to gromadzeniu się kredytu w przypadku przerwy w transmisji (odpowiednik sytuacji, gdy wiadro staje się mniej niż puste).

Ta wersja algorytmu działa, ponieważ τ określa, o ile wcześniej komórka może dotrzeć, niż gdyby nie było jittera: patrz nieszczelny wiadro: tolerancja zmienności opóźnienia . Innym sposobem, aby to zobaczyć, jest to, że TAT reprezentuje, kiedy wiadro zostanie opróżnione, więc czas τ przed tym jest, kiedy wiadro jest dokładnie napełnione do wartości granicznej. Tak więc, w obu poglądach, jeśli przybywa więcej niż τ przed TAT , jest za wcześnie, aby się dostosować.

Porównanie z pojemnikiem na tokeny

GCRA w przeciwieństwie do implementacji algorytmu token bucket nie symuluje procesu aktualizacji zasobnika (wycieku czy regularnego dodawania tokenów). Zamiast tego za każdym razem, gdy komórka przybywa, oblicza ilość, o jaką wycieknie wiadro od czasu ostatniego obliczenia jego poziomu lub kiedy wiadro zostanie opróżnione (= TAT ). Zasadniczo polega to na zastąpieniu procesu wycieku zegarem (czasu rzeczywistego), który prawdopodobnie ma już większość implementacji sprzętowych.

To zastąpienie procesu RTC jest możliwe, ponieważ komórki ATM mają stałą długość (53 bajty), stąd T jest zawsze stałą, a obliczenie nowego poziomu zasobnika (lub TAT ) nie obejmuje żadnego mnożenia ani dzielenia. W rezultacie obliczenia można wykonać szybko w oprogramowaniu i choć więcej działań jest podejmowanych, gdy nadejdzie komórka niż wiadro tokenów, pod względem obciążenia procesora wykonującego zadanie, brak osobnego procesu aktualizacji więcej niż to rekompensuje. Co więcej, ponieważ nie ma symulacji aktualizacji zasobnika, nie ma żadnego obciążenia procesora, gdy połączenie jest w stanie spoczynku.

Jeśli jednak GCRA miałaby być używana do ograniczania przepustowości, a nie liczby pakietów/ramek, w protokole z pakietami o zmiennej długości (jednostki PDU warstwy łącza), wiązałoby się to z mnożeniem: w zasadzie wartość dodana do zasobnika (lub zgodnie z TAT) dla każdego zgodnego pakietu musiałoby być proporcjonalne do długości pakietu: mając na uwadze, że przy GCRA zgodnie z opisem woda w wiadrze ma jednostki czasu, w przypadku pakietów o zmiennej długości jednostki musiałyby mieć jednostki, które są iloczynem długość i czas pakietu. Stąd zastosowanie GCRA do ograniczenia przepustowości pakietów o zmiennej długości bez dostępu do szybkiego, sprzętowego mnożnika (jak w układzie FPGA ) może nie być praktyczne. Jednak zawsze można go użyć do ograniczenia szybkości pakietu lub komórki, o ile ich długości są ignorowane.

Podwójny kontroler wyciekającego wiadra

Wiele implementacji GCRA może być zastosowanych jednocześnie do VC lub VP, w podwójnej nieszczelnej wiadro kontroli ruchu lub funkcji kształtowania ruchu, np. zastosowane do VC o zmiennej przepływności (VBR). Może to ograniczyć komórki ATM w tym VBR VC do Sustained Cell Rate (SCR) i Maximum Burst Size (MBS). W tym samym czasie funkcja nadzoru ruchu podwójnego wyciekającego zasobnika może ograniczyć szybkość komórek w seriach do wartości Peak Cell Rate (PCR) i maksymalnej tolerancji zmienności opóźnienia komórek (CDVt): patrz Traffic Contract#Traffic Parameters .

Rysunek 2: Przykładowe taktowanie komórek na połączeniu VBR

Można to najlepiej zrozumieć, gdy transmisja na VBR VC ma postać komunikatów o stałej długości (CPCS-PDU), które są przesyłane z pewnymi stałymi interwałami lub czasem między komunikatami (IMT) i zajmują pewną liczbę komórek, MBS, nieść je; jednakże opis ruchu VBR i użycie podwójnego nieszczelnego wiadra nie ogranicza się do takich sytuacji. W tym przypadku średnia szybkość komórek w przedziale IMT to SCR (=MBS/IMT). Poszczególne komunikaty mogą być przesyłane w PCR, która może mieć dowolną wartość pomiędzy szerokością pasma łącza fizycznego (1/ δ ) i SCR. Pozwala to na przesłanie komunikatu w okresie krótszym niż interwał komunikatu IMT, z przerwami między wystąpieniami komunikatu.

Rycina 3: Algorytm referencyjny dla Sustainable Cell Rate (SCR) i Peak Cell Rate (PCR) dla CLP = 0 + 1 przepływ komórek

W podwójnym nieszczelnym zasobniku jeden zasobnik jest stosowany do ruchu z interwałem emisji równym 1/SCR i wartością graniczną τ _SCR , która daje MBS, czyli liczbę komórek w wiadomości: patrz nieszczelny zasobnik#Maksymalny rozmiar wybuchu . Drugi przedział ma przedział emisji 1/PCR i wartość graniczną τ _PCR , która pozwala na CDV do tego punktu na ścieżce połączenia: patrz nieszczelny wiadro#Tolerancja zmienności opóźnienia . Komórki są następnie przepuszczane w PCR, z jitterem τ _PCR , aż do maksymalnej liczby komórek MBS. Następna seria komórek MBS zostanie następnie dopuszczona przez uruchomienie MBS x 1/SCR po pierwszej.

Jeśli komórki przybywają w serii z szybkością wyższą niż 1/PCR (komórki MBS przybywają w mniej niż (MBS - 1)/PCR - τ _PCR ) lub więcej niż komórki MBS docierają do reakcji PCR lub serie komórek MBS docierają bliżej niż IMT, podwójne nieszczelne wiadro wykryje to i opóźni (kształtowanie) lub odrzuci lub pozbawi priorytetu (nadzorowanie) wystarczającą liczbę komórek, aby połączenie było zgodne.

Rycina 3 przedstawia algorytm referencyjny dla kontroli SCR i PCR dla obu wartości priorytetu utraty komórek (CLP) 1 (niski) i 0 (wysoki) przepływów komórkowych, tj. gdzie komórki z obiema wartościami priorytetu są traktowane tak samo. Podobne algorytmy referencyjne, w których komórki o wysokim i niskim priorytecie są traktowane inaczej, podano również w załączniku A do I.371.

Zobacz też