6.4 Porównanie algorytmów

Tabela: Porównanie algorytmów.

algorytm	średnia przepustowość [tx]	średni czas reakcji [s]	średnie opóźnienie [s]	procent cofnięć [%]	stabilność
naiwny	1,34	0,00	352,5	0	n
stałe okno (1,3 s)	4,71	0,60	11,3	0	t
dynamiczny	4,17	0,84	13,0	0	t
dynamiczny modyfikowany	4,46	0,73	10,9	69,8	t
adaptacyjny	3,17	0,32	223,9	0	n
adaptacyjny modyfikowany	3,47	0,27	206,0	121,5	n

Porównywane algorytmy bardzo różniły się między sobą zachowaniem. Wynikało to z różnic w ich złożoności i schematach postępowania. W tabeli 6.1 przedstawiliśmy wyniki testów algorytmów przy jednakowych danych wejściowych: obciążenie duże, długość transakcji 0,7 s, rozkład złożony. Porównując średnią przepustowość i czas reakcji można dostrzec pewną prawidłowość -- im większy czas reakcji (a zarazem średnia szerokość okna), tym wyższa przepustowość. Przyczyny tego zjawiska są opisane w punkcie 6.3.2.

Stabilność jest najważniejszą cechą algorytmu, ponieważ w rzeczywistym systemie transakcyjnym długość kolejki nie może przekroczyć pewnej granicy. Tym atrybutem charakteryzują się trzy algorytmy: ze stałym oknem, dynamiczny oraz dynamiczny modyfikowany. Pierwszy ze wspomnianych algorytmów jest stabilny tylko wtedy, gdy szerokość okna jest dostosowana do charakterystyki obciążenia (lub gdy jest odpowiednio większa). W systemie ze zmiennym obciążeniem (a taka jest większość systemów transakcyjnych) wytworzyłby zbyt duży czas reakcji w okresie małego obciążenia lub byłby niestabilny w czasie wysokiego obciążenia. Z kolei algorytm dynamiczny modyfikowany cechuje się zbyt dużą liczbą wycofanych transakcji, co przesądza o jego nieprzydatności. Pozostaje algorytm dynamiczny, który okazał się najlepszym z testowanych algorytmów. Jest uniwersalny -- potrafi automatycznie dostosować swoje zachowanie do charakterystyki obciążenia oraz utrzymuje przepustowość na poziomie zbliżonym do optymalnego.